移动群智感知中预算受限的用户招募问题研究

发布时间：2018-01-29 02:28

本文关键词： 移动群智感知用户招募预算受限收益最大化贪心算法机会式招募离线算法在线算法　出处：《中国科学技术大学》2017年硕士论文　论文类型：学位论文

【摘要】：随着智能手机等移动电子设备的广泛使用,移动群智感知技术也得到发展,应用前景广阔。在移动群智感知中,感知平台需要招募大量用户来协同完成一项包含众多感知任务的复杂工作。如何恰当、高效地招募合适的用户是我们需要解决的首要问题。本文主要研究移动群智感知中预算受限的用户招募问题。不同于以往研究,本文中每个感知任务都是不可再分的,并且可以被多个用户执行,但是单个任务的收益是固定的,这使得我们的问题不同于0-1背包问题。此外,现有的工作主要研究预算不受限的招募问题,用户的开销是固定的,优化目标大多是总开销的最小化;本文中用户的开销根据执行任务的数量而定,感知平台的总开销不能超过给定预算,同时寻求总收益的最大化。为此,我们针对不同的场景,研究了两种不同的用户招募模型,并提出了相应的用户招募解决方案和算法:1.集中式确定型的用户招募问题。其中,用户的可执行任务集由自己决定,其开销则取决于可执行任务数,感知平台知晓全部用户的可执行任务集和开销。为此,我们对预算受限的收益最大化用户招募问题建立数学模型,证明了其NP-难解性,提出了一个集中式的贪心算法gPUR来求解该问题,并通过数学推导分析了该算法的性能保证,证明了该算法具有常数近似比。2.机会式概率型的用户招募问题。在该问题中,由于任务消息数据量大、蜂窝网络不可用等原因,集中式招募方案不适用。为此,我们首先设计了一种基于机会网络分发任务、利用历史概率信息招募用户的通用解决方案OTDURS。然后建立用户招募模型,并证明了问题的NP-难解性,最后设计了两种机会式概率型的用户招募算法,并分析了算法的计算复杂度。其中,离线招募算法FUR完全基于历史概率信息,执行贪心迭代,输出一个离线招募策略。而在线招募算法NUR中,感知平台利用D2D机会网络分发任务的同时招募用户。每次遇见一个新用户,都基于当前相遇用户的确定信息和其他用户的历史概率信息,执行招募算法,输出一个临时招募策略,并根据当前用户是否在临时招募策略中,即时决定是否招募该用户。我们对上述算法分别进行了大量的验证,并详细分析和比较了实验结果。结果表明,我们的算法相比多个参照算法具有更好的性能表现。
[Abstract]:With the wide use of mobile electronic devices such as smart phones, mobile group intelligence perception technology has been developed, and has a broad application prospect. Perception platform needs to recruit a large number of users to cooperate to complete a complex task involving a large number of perceptual tasks. The most important problem we need to solve is to recruit suitable users efficiently. This paper focuses on the problem of user recruitment with budget constraints in mobile swarm intelligence perception, which is different from previous research. Each perceptual task in this article is inseparable and can be performed by multiple users, but the benefits of a single task are fixed, which makes our problem different from the 0-1 knapsack problem. The existing work mainly studies the recruitment problem with unlimited budget. The user's cost is fixed, and the optimization goal is mostly to minimize the total cost. In this paper, the cost of users depends on the number of tasks performed, the total overhead of the aware platform can not exceed a given budget, while seeking to maximize the total revenue. For this reason, we aim at different scenarios. In this paper, two different user recruitment models are studied, and the corresponding solutions and algorithms of user recruitment are proposed: 1. The centralized deterministic user recruitment problem, in which the user's executable task set is determined by himself. The overhead depends on the number of executable tasks, and the aware platform knows the executable task set and the cost of all users. Therefore, we establish a mathematical model for the problem of maximizing the revenue of users with budget constraints. This paper proves its NP-insolvability, proposes a centralized greedy algorithm (gPUR) to solve the problem, and analyzes the performance guarantee of the algorithm by mathematical derivation. It is proved that the algorithm has a constant approximation ratio. 2. The opportunistic probabilistic user recruitment problem. In this problem, due to the large amount of task message data, the cellular network is not available. The centralized recruitment scheme is not applicable. To this end, we first designed an opportunity-based network distribution task. Using historical probability information to recruit users, a universal solution called OTDURS.Then, the model of user recruitment is established, and the NP-intractability of the problem is proved. Finally, two opportunistic probabilistic user recruitment algorithms are designed, and the computational complexity of the algorithm is analyzed. Among them, the offline recruitment algorithm FUR is based entirely on historical probability information and executes greedy iteration. An offline recruitment strategy is outputted. In the online recruitment algorithm NUR, the perceptual platform uses D2D opportunities to distribute tasks at the same time and recruits users at the same time, and meets a new user each time. Based on the information of the current meeting user and the historical probability information of other users, the recruitment algorithm is executed, a temporary recruitment strategy is output, and the current user is in the temporary recruitment strategy according to whether or not the current user is in the temporary recruitment strategy. Whether to recruit the user or not is immediately decided. We have carried out a large number of verification of the above algorithm, and analyzed and compared the experimental results in detail. The results show that. Our algorithm has better performance than multiple reference algorithms.
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TN929.5;TP301.6

【相似文献】