【作者】 黄涛；

【导师】 朱斌；

【作者基本信息】 重庆大学 ， 信息与通信工程， 2019， 硕士

【摘要】 移动群智感知是指在特定的感知区域内,利用携带智能设备的移动用户协作完成个体难以解决的复杂任务。近年来,智能设备(手机、平板、车载终端等)集成了越来越多的传感器,具有存储、计算、感知和处理的强大性能,使得用户可以通过这些设备随时感知周围的信息。与传统的静态传感网不同,移动群智感知网络将携带智能设备的用户看作动态的传感节点,具有感知范围广、感知规模大、维护成本低等优点,在环境检测、智能交通、室内定位和智慧城市有广阔的前景和应用空间。其中,任务分配机制是移动群智感知网络研究的关键问题。任务分配的核心是携带智能设备的用户。在实际感知场景下,由于用户运动的不规则性,现有的任务分配策略不合理,面对复杂多变的任务需求,算法的适用性不高。因此,本文对移动群智感知网络中任务分配机制进行了研究,具体的研究内容和成果如下:(1)在任务分配者移动分配模型中,分配者将任务分配给移动过程中相遇的用户,用户完成任务以后通过和分配者的再次相遇返回感知结果。现有算法利用用户的相遇规律制定分配策略,用户自愿式参与感知过程,某些场景下用户可能分配到过多或过少的任务,缺乏实际应用性。因此,在现有算法基础上,本文以最小化任务平均完成时间为目标函数,设计了一种报酬激励的在线任务多级分配框架(Reward and Multi-stage Crowdsensing Task Assignment Framework,RM-CSTA)。任务分配者和用户通过斯坦克伯格博弈过程达到均衡:分配者最小化任务平均完成时间,用户最大化报酬收益。其中,用巴特沃斯低通滤波曲线作为博弈的报酬函数,完成任务的时间越少,得到的报酬越多。用户可以利用再分配策略减少完成任务的时间来提高自己的收益。随后给出了框架的任务分配算法(Multi-stage Online Task Assignment,MOTA)并作算法分析,真实场景和模拟场景下的仿真实验证明了MOTA算法的任务完成时间能够平均减少10%-15%。(2)优化后的算法可以应用在实际场景,算法的多级分配策略使得用户可以将任务分配给更多的用户从而可以提高算法的适用性。然而某些场景下,参与用户由于能力受限,或者遇不到别的用户导致不具备再分配条件时,MOTA算法的性能就会下降。因此,本文创新性地提出了基于社会网络的Social-MOTA任务分配算法对MOTA算法的多级分配策略进行了优化,结合用户的社会关系网络,提出了用户的能力阈值概念。用户在群智感知过程中可以根据自己的能力范围主动地优化分配到的任务子集,既提高了用户参与水平,又能一定程度上保证感知数据质量。理论分析证明了Social-MOTA算法更能适应在大范围、任务复杂的一般性感知场景下的任务分配问题;仿真结果表明Social-MOTA算法的任务完成时间比MOTA算法平均减少15%。更多还原

【Abstract】 Mobile crowdsensing refers to users carrying smart devices cooperate to accomplish a complex task,which is difficult for an individual to handle in a specific sensing area.In recent years,smart devices(mobile phones,tablets,vehicle terminals,etc.)have integrated more and more sensors,with powerful performances of storage,computing,sensing and processing,enabling users to perceive the surrounding information at any time through these devices.Different from the traditional static sensor network,mobile crowdsensing regards the user who carries the smart device as a dynamic sensor node,which has the advantages of wide sensing range,large sensing scale,low maintenance cost,etc.,having broad prospects and application space in environmental detection,intelligent transportation,indoor positioning and smart cities.Among them,the task assignment mechanism is a key issue in the research of mobile crowdsensing.The core of task assignment is the user who carries the smart device.In the actual perception scenario,due to the irregularity of user motion,the existing task assignment strategy is not reasonable.In the face of complex and varied task requirements,the applicability of the algorithm is not high.Therefore,this thesis studies the task assignment mechanism in mobile crowdsensing network,and the specific research contents and results are as follows:In the task assigner’s assignment model while moving,the assigner assigns tasks to the user he meets in the mobile process,and the user returns the perceived result through the encounter with the assigner again after completing the tasks.The existing algorithm utilizes the user’s encountering rules to formulate the assignment strategy,and the user participates in the sensing process voluntarily.In some scenarios,the user may be assigned too many or too few tasks,and the practicality is lacking.Therefore,based on the existing algorithms,this thesis designs a Reward and Multi-stage Crowdsensing Task Assignment Framework(RM-CSTA)with the goal of minimizing the average completion time of the task.The task assigner and the user achieve equilibrium through the Stackleberg process: the assigner minimizes the average completion time of the task,and the user maximizes the rewards.Among them,the Butterworth low-pass filter curve is used as the reward function of the game,and the less time to complete the task,the more rewards are obtained.The user can use the redistribution strategy to reduce the time for completing the task to improve his income.Then the task assignment algorithm(Multi-stage Online Task Assignment(MOTA)of the framework is given and the algorithm is analyzed.The simulation experiments in the real scenario and the simulation scenario prove that the task completion time of the MOTA algorithm can be reduced by an average of 10%-15%.(2)The optimized algorithm can be applied to the actual scenario and the multi-stage assignment strategy of the algorithm allows the user to assign tasks to more users,thereby improving the applicability of the algorithm.However,in some scenarios,the performance of the MOTA algorithm will decrease due to the limited capacity of the participating users or the failure to meet other users.Therefore,this thesis innovatively proposes a social-based task assignment algorithm to optimize the multi-stage assignment strategy of MOTA algorithm,combines the user’s social relationship network and the user’s ability threshold.In the process of crowdsensing,users can actively optimize the assigned subset of tasks according to their own capabilities,which can improve user participation and ensure the perceived data quality to a certain extent.Theoretical analysis proves that the Social-MOTA algorithm is more suitable for task assignment in general perception scenarios with large scope and complex tasks.The simulation results show that the task completion time of the Social-MOTA algorithm is reduced by about 15% compared with the MOTA algorithm.更多还原