论文部分内容阅读
随着智能终端设备的计算、存储、通信等能力大幅提升,一种被称为移动群智感知的计算模式引起了学术界与工业界的极大关注。移动群智感知是通过无线网络将携带智能终端设备的多个移动用户联合起来,以便完成单个用户难以应对的大规模感知任务。由于移动群智感知具有低成本、普适性、高度灵活性等优势,因而其具有广泛的应用前景。然而,移动群智感知系统在处理用户的返回结果时将会涉及到大规模的数据分析,所以系统平台将面临着巨大的计算存储压力,尤其当任务发起者的数量增加时,平台的处境将更加困难。得益于边缘计算的发展,我们构建了基于边云的移动群智感知系统框架,平台可以借助网络边缘中的服务器(即边云节点)来完成对感知数据的处理和传输。在基于边云的移动群智感知系统中,最重要的模块就是如何从大量的用户候选者中选择合适的用户来执行任务(即用户招募),以及如何调度边云节点中的资源协作处理与传输移动用户的感知数据(即资源调度)。本文主要针对这两个方面展开研究。首先针对用户招募问题。一般而言,平台总是希望选择那些感知能力强的移动用户来执行任务,然而在实际场景中平台并不能事先获得用户的感知参数,这被称为“未知的用户”招募问题。我们采用强化学习领域中的组合多臂匪徒(即Combinatorial Multi-Armed Bandit)模型来形式化用户感知能力的学习过程,进而提出基于CMAB的未知用户招募机制。在此机制中,为了避免平台陷入两难的困境,即是否总是招募那些在之前表现“好”的用户,或者尝试一些暂时表现“不好”的用户以便探索出潜在的最优用户,我们首先扩展了基本的UCB(即Upper Confidence Bound)公式,从而可以更加精确地表示CMAB模型中用户感知质量的置信上限。然后,我们采取max{}函数来确定任务在每一轮次中的感知质量值。基于此,我们设计了针对所有任务的感知质量函数,从而提出了贪婪的用户招募策略,即总是选择可以最大化所提函数边际值的移动用户。大量的理论分析和基于真实数据集的实验仿真均证明了所提机制的高效性能。另一方面,在用户招募过程中,移动用户的感知质量值和成本值往往涉及其隐私信息,所以系统和用户之间总是存在着关于感知质量/成本值是否公开的争议。此外,系统还要满足任务发起者的特定要求,即每个任务的最终完成质量不低于特定的阈值。针对此问题,我们提出了可实现隐私保护的用户招募机制。在此机制中,为了实现平台能够以最小的成本来招募合适的用户,同时保证发起者对任务完成质量的要求,我们首先设计了一个效用函数,此效用函数将任务的完成质量和阈值限制结合起来。接着我们提出贪婪的用户招募策略,即总是选择能够以单位成本最大化效用函数边际值的用户。同时为了保证用户的隐私信息(感知质量和成本),我们将秘密分享技术结合到所提的贪婪策略中,从而提出安全的用户招募机制。我们通过严格的理论分析证明了所提机制在半诚实安全模型下的绝对安全性,并且大量的理论分析和实验仿真也验证了此机制的优越性能。在基于边云的移动群智感知系统中,如何高效地调度边云节点中的有限资源来协助处理用户的感知数据,从而可以最大化整个系统的性能是有挑战的。针对此问题,我们提出了面向边云的虚拟机资源调度机制。在此机制中,为了解决移动用户的(不同的)截止时间限制问题,我们首先生成一些虚拟的边云节点,从而把三层的系统框架转换成两层框架。同时,为了应对用户之间的竞争关系,以及用户可能会采取的策略性行为(即谎报信息以提高自己的收益),我们采用拍卖技术来分配边云节点中的虚拟机资源,其主要包含中标选择算法和支付值确定算法。具体而言,我们将中标选择问题模型化为带有多0-1背包限制的多对1的加权二分图匹配问题,然后我们总是选择带有最大权的边加入到分配方案中。针对支付值确定算法,我们根据Myerson定理设计了临界支付值的计算方式,从而可以保证系统的诚实性。我们通过理论分析和基于真实数据集的实验仿真验证了此机制的诚实性、个体理性、计算有效性等性质。移动用户在完成感知任务后,其需要将最终的感知结果上传给平台。一方面,用户可以通过蜂窝网来传输数据,但传输成本相对较高;另一方面,用户可以借助边云节点的通信能力来实现数据传输,边云节点的传输成本相对较低,但缺点是其传输容量是有限的,而且边云节点只有一定的概率能够提供数据传输服务。针对此问题,我们设计了边云资源受限的数据调度传输机制,其可以最小化用户的传输成本,同时满足用户的传输截止时间限制。具体而言,我们首先将此问题模型化为一个带有多0-1背包限制的优化问题,其中的背包相当于有传输容量限制的边云节点。因为每个数据项经过一个边云节点成功传输是一个概率性事件,所以我们允许一个数据项被调度到多个边云节点以提高其成功传输的概率。换言之,所有数据将共享一个组合概率优化目标。我们通过大量的理论分析和基于真实数据集上的实验仿真证明了所提机制的高效性能。