移动群智感知中服务质量敏感的任务分配算法研究

发布时间：2018-02-21 16:29

本文关键词： 移动群智感知服务质量任务分配可变的任务灵活的报酬　出处：《中国科学技术大学》2017年硕士论文　论文类型：学位论文

【摘要】：移动群智感知是一种新兴的感知模式。它借助移动互联网进行通信,将携带了智能设备的用户看成移动传感器,通过他们的协作来完成一些传统网络难以解决的大规模感知任务。在决定是否利用移动群智感知完成大规模感知任务时,通常是以较高的质量和较低的代价作为重要依据。所以,如何解决在保证任务服务质量的同时最小化代价这一问题极具挑战意义。本文主要研究了移动群智感知中服务质量敏感的任务分配问题。由于参与用户的非专业性,任务的服务质量受用户感知习惯影响,所以如何保证任务的服务质量极其重要。基于这种情况,本文提出了两种不同的服务质量敏感的任务分配问题,并给出了相应的解决方案。本文的主要贡献如下:·我们以最小化代价的为优化目标,研究了服务质量敏感的任务分配问题。和已有工作不同的是,本文研究的是一种可变任务的分配问题,它包括两个部分:可变的任务和灵活的报酬。用户可以执行一个或者多个任务,而安排给每个用户的任务是可变的。用户获得的报酬与安排给他/她的任务有关。为了保证任务的服务质量,每个任务可能安排给多个用户。我们首先证明该问题是NP难的;然后基于贪心思想提出了一个服务质量敏感的任务分配算法;最后,通过近似比分析和实验仿真结果,我们证明了这个算法的具有较高的性能。·我们综合分析任务的特点和用户的感知习惯,抽象出一个多维服务质量敏感的任务分配问题。完成一个任务,需要满足多个服务质量要求。由于服务质量是多维的,简单的一维计算方法不再适用,所以我们首先定义了一些关于多维服务质量计算方法。其次,我们设计了一个关于多维服务质量的多维效用函数,并根据这个效用函数提出了一个贪心算法,该算法每次选择可以最大化任务的服务质量且代价最小的用户任务组合,直到所有的任务的服务质量都满足要求。最后,理论分析和仿真实验都表明了这个算法的优越性。本文研究的任务分配模型和报酬机制都具有很高的适应性,并且服务质量敏感的任务分配算法能够适应多种服务质量要求的移动群智感知系统,因而对移动群智感知的发展有很大意义。
[Abstract]:Mobile group intelligence perception is a new mode of perception. It uses the mobile Internet to communicate with users who carry smart devices as mobile sensors. Through their collaboration, we can accomplish some large-scale sensing tasks that are difficult to solve in traditional networks. When deciding whether to use mobile swarm intelligence to accomplish large-scale sensing tasks, Usually on the basis of higher quality and lower cost. It is very challenging to solve the problem of how to ensure the quality of service while minimizing the cost. In this paper, we mainly study the problem of task assignment which is sensitive to the quality of service in mobile swarm intelligence perception. The quality of service (QoS) of a task is influenced by user perceived habits, so how to ensure the QoS of a task is extremely important. Based on this situation, two different QoS sensitive task assignment problems are proposed in this paper. The main contributions of this paper are as follows: 路We study the QoS sensitive task assignment problem with the aim of minimizing the cost. This paper deals with a problem of assignment of variable tasks, which consists of two parts: variable tasks and flexible compensation. Users can perform one or more tasks. The tasks assigned to each user are variable. The remuneration received by the user is related to the task assigned to him or her. In order to ensure the quality of service of the task, each task may be assigned to more than one user. We first prove that the problem is NP-hard; Then, a QoS sensitive task assignment algorithm based on greedy idea is proposed. Finally, through approximate ratio analysis and experimental simulation results, We prove that the algorithm has high performance. 路We analyze the characteristics of the task and the user's perception habits, abstract a multi-dimensional QoS sensitive task assignment problem. Since the quality of service is multidimensional and the simple one-dimensional calculation method is no longer applicable, we first define some methods for computing the multi-dimensional quality of service. We design a multidimensional utility function about multidimensional quality of service and propose a greedy algorithm according to this utility function. The algorithm selects the user task composition which can maximize the quality of service of the task and has the lowest cost. Finally, theoretical analysis and simulation experiments show the superiority of the algorithm. The task assignment model and reward mechanism studied in this paper have high adaptability. Moreover, the QoS sensitive task assignment algorithm can adapt to the mobile swarm intelligence perception system with multiple QoS requirements, so it has great significance for the development of mobile swarm intelligence perception.
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TN929.5;TP212;TP301.6

【相似文献】