随着集成众多智能传感器和拥有移动计算能力的智能手机在生活中的应用越来越广泛[1],利用大量参与结点收集和分析感知数据的群智感知计算逐渐变为现实。群智感知计算中一个显著的特点是,参与结点自行决定是否参与群智感知计算,并在贡献感知数据后获取对应的报酬。如何在有限的预算约束和感知数据可能存在冗余的情况下[2],尽可能地吸引更多的参与结点收集和贡献感知数据是一个重要的问题。与此同时,参与结点对参与群智感知计算中的感知任务有一个决策的过程,参与结点形成的策略组合直接影响到群智感知计算的性能和收集到的感知数据的质量。本课题着重研究群智感知计算中的参与结点决策问题。与现有研究工作注重研究群智感知计算中的激励机制不同,本课题从参与结点的角度出发,基于参与结点的行为模式和博弈论中拥塞博弈(Congestion Game)模型,提出了感知任务选择(Sensing Process Participation,SPP)博弈。在此博弈中,每个参与结点通过判断自己的满意度来决定是否参与群智感知计算中的感知任务。满意的参与结点的数量越多,群智感知计算的工作性能就越高。如何求解感知任务选择博弈的社会最优被称为感知任务选择问题。本课题首先证明了感知任务选择问题是NP难的。其次,本课题提出分布式的感知任务选择算法,能够在线性时间内收敛到一个纯策略纳什均衡。每个参与结点能够独立地判断自己的满意度,并向平台提交更优响应更新,而无需与其他参与结点交换信息。在此基础上,本课题证明了感知任务选择博弈的两个性质,包括纯策略纳什均衡的存在性与无秩序代价(Price of Anarchy)。在参与结点的需求差异不大的一般情况下,纯策略纳什均衡能够达到近似社会最优的社会效益。本课题对长期运行并拥有大量参与结点和感知任务的群智感知计算系统进行了大量的仿真实验。仿真结果显示,本文提出的感知任务选择算法能够稳定地收敛到纯策略纳什均衡。在通常情况下,群智感知计算系统中大部分的参与结点是满意的。同时,感知任务选择算法能够良好地应对不同数量的参与结点和感知任务,具有较低的计算复杂度。
暂无评论