群智感知系统中任务分配算法与激励机制的研究

作     者：方文凤 

作者单位：四川师范大学 

学位级别：硕士

导师姓名：刘莉

授予年度：2018年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 080202[工学-机械电子工程] 08[工学] 0835[工学-软件工程] 0802[工学-机械工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：群智感知 任务分配 激励机制 感知成本 拍卖理论 校园信息共享平台 

摘      要：随着内置高性能传感器的移动设备的广泛应用,新兴的群智感知技术逐渐成为实时感知、收集与共享信息的有效方式。不同于传统的静态传感器网络,群智感知无需部署大量传感器节点,它将普通用户随身携带的移动设备作为基本的感知单元,随时随地感知周围环境信息,实现感知任务的分发与感知数据的收集,是众包思想在移动数据感知领域的体现。任务分配与激励机制是群智感知研究中的关键问题,其中,任务分配是在一定约束条件下,选择合适的感知用户执行任务,以实现某种优化目标;激励机制则是借助合理的激励措施激励用户积极参与感知任务,以解决感知用户参与量不足等问题。本文针对最小化感知成本的任务分配问题以及基于拍卖的报酬激励机制设计问题展开研究,同时,结合研究成果,开发一套基于群智感知的校园信息共享平台。相应地,本文的主要研究工作如下:（1）在用户信息对称的情况下,研究最小化感知成本的任务分配问题。该问题针对现有研究的不足,增加考虑任务执行顺序与任务执行成本以计算感知成本,在用户可被分配多个任务的条件下,实现最小化感知成本的优化目标。通过复杂性分析可知,该问题属于NP-hard问题,在多项式时间内无法求得最优解,为此,分别采用贪婪算法、简单遗传算法、单亲遗传算法以及改进蚁群算法求取次优解。仿真结果表明,上述四种算法在感知成本与运行时间的表现上各具特点,可在实际应用中根据具体需求进行合理选择。（2）在用户信息非对称的情况下,结合拍卖理论设计报酬激励机制,以解决现有研究中单任务拍卖成本高、用户虚假报价以及平台预算有限等问题。该激励机制借助反向组合拍卖,首先,基于用户感知范围与预处理机制得到有效竞拍任务组与竞拍价;其次,采用决策方案中的次价拍卖机制以及相应约束条件确定获胜用户及其报酬;最后,理论与仿真结果表明,该机制激励相容、个体理性、预算可行以及计算有效,且具有较优的性能。（3）为实现校园信息的实时共享,结合前述任务分配算法与激励机制的研究成果,开发一套基于Android系统的群智感知校园信息共享平台。该平台的核心模块为算法实现模块,一方面,平台可通过任务分配模块选择合适的用户完成相应的信息任务;另一方面,可通过激励机制模块在竞拍用户中确定获胜用户及其奖励积分。本文的理论研究成果可以为群智感知相关研究工作提供参考价值,同时,结合理论成果开发的校园应用也具有一定的现实意义。