论文部分内容阅读
随着智能手机等移动电子设备的广泛使用,移动群智感知技术也得到发展,应用前景广阔。在移动群智感知中,感知平台需要招募大量用户来协同完成一项包含众多感知任务的复杂工作。如何恰当、高效地招募合适的用户是我们需要解决的首要问题。本文主要研究移动群智感知中预算受限的用户招募问题。不同于以往研究,本文中每个感知任务都是不可再分的,并且可以被多个用户执行,但是单个任务的收益是固定的,这使得我们的问题不同于0-1背包问题。此外,现有的工作主要研究预算不受限的招募问题,用户的开销是固定的,优化目标大多是总开销的最小化;本文中用户的开销根据执行任务的数量而定,感知平台的总开销不能超过给定预算,同时寻求总收益的最大化。为此,我们针对不同的场景,研究了两种不同的用户招募模型,并提出了相应的用户招募解决方案和算法:1.集中式确定型的用户招募问题。其中,用户的可执行任务集由自己决定,其开销则取决于可执行任务数,感知平台知晓全部用户的可执行任务集和开销。为此,我们对预算受限的收益最大化用户招募问题建立数学模型,证明了其NP-难解性,提出了一个集中式的贪心算法gPUR来求解该问题,并通过数学推导分析了该算法的性能保证,证明了该算法具有常数近似比。2.机会式概率型的用户招募问题。在该问题中,由于任务消息数据量大、蜂窝网络不可用等原因,集中式招募方案不适用。为此,我们首先设计了一种基于机会网络分发任务、利用历史概率信息招募用户的通用解决方案OTDURS。然后建立用户招募模型,并证明了问题的NP-难解性,最后设计了两种机会式概率型的用户招募算法,并分析了算法的计算复杂度。其中,离线招募算法FUR完全基于历史概率信息,执行贪心迭代,输出一个离线招募策略。而在线招募算法NUR中,感知平台利用D2D机会网络分发任务的同时招募用户。每次遇见一个新用户,都基于当前相遇用户的确定信息和其他用户的历史概率信息,执行招募算法,输出一个临时招募策略,并根据当前用户是否在临时招募策略中,即时决定是否招募该用户。我们对上述算法分别进行了大量的验证,并详细分析和比较了实验结果。结果表明,我们的算法相比多个参照算法具有更好的性能表现。