Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (1): 18-23.DOI: 10.11772/j.issn.1001-9081.2017.01.0018

Previous Articles     Next Articles

Multi-task assignment algorithm for mobile crowdsensing

XU Zhe1, LI Zhuo1,2, CHEN Xin1   

  1. 1. School of Computer Science, Beijing Information Science and Technology University, Beijing 100101, China;
    2. Beijing Key Laboratory of Internet Culture and Digital Dissemination(Beijing Information Science and Technology University), Beijing 100101, China
  • Received:2016-08-01 Revised:2016-08-12 Online:2017-01-10 Published:2017-01-09
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61370065, 61502040), the Program for Excellent Talents in Beijing Municipality (2014000020124G099), the Open Program of the Beijing Key Laboratory of Internet Culture and Digital Dissemination (ICDD201406), the Program of Key Laboratory of Modern Measurement & Control Technology (Ministry of Education)/Beijing Key Laboratory of Electromechanical System Measurement and Control (KF20151123205).

面向移动群智感知的多任务分发算法

徐哲1, 李卓1,2, 陈昕1   

  1. 1. 北京信息科技大学 计算机学院, 北京 100101;
    2. 网络文化与数字传播北京市重点实验室(北京信息科技大学), 北京 100101
  • 通讯作者: 李卓
  • 作者简介:徐哲(1993-),男,山东阳谷人,硕士研究生,主要研究方向:移动群智感知;李卓(1983-),男,河南南阳人,讲师,博士,CCF会员,主要研究方向:移动无线网络、分布式计算;陈昕(1965-),男,江西南昌人,教授,博士,CCF会员,主要研究方向:网络性能评价、网络安全。
  • 基金资助:
    国家自然科学基金资助项目(61370065,61502040);北京市优秀人才培养资助青年骨干个人项目(2014000020124G099);网络文化与数字传播北京市重点实验室资助项目(ICDD201406);现代测控技术教育部重点实验室/机电系统测控北京市重点实验室资助项目(KF20151123205)。

Abstract: Data transmission based on opportunistic communication in mobile crowdsensing may take a long period of time. To address this issue, a new Hub-based multi-Task Assignment (HTA) algorithm was proposed. In this algorithm, some nodes were selected to perform as the hubs which could help the requester node to deliver the tasks, according to the different characteristics of the social relationship of the nodes in mobile networks. When the task requester encountered a hub node, the hub node itself and its slave nodes were assigned tasks. After that, the hub node would distribute the tasks to the salve nodes, and received the results from them. Simulations were conducted on The ONE simulator. Compared with the oNline Task Assignment (NTA) algorithm, HTA algorithm reduced the time cost by 24.9% on average and improved the task completion ratio by 150% on average. The experimental results demonstrate that HTA algorithm can accelerate the accomplishment speed of the task and reduce the time cost.

Key words: mobile crowdsensing, opportunistic communication, multi-task assignment, social relationship, hub node

摘要: 针对在移动群智感知中基于机会通信完成数据传输会消耗大量时间成本的问题,提出了一种基于中枢节点的多任务分发(HTA)算法。该算法利用节点在移动网络中社交关系属性不同的特点,通过中枢节点选择算法将部分节点作为中枢节点,并将其用于协助任务请求节点分发任务。在任务请求节点与中枢节点相遇时,同时给中枢节点本身和它的从属节点分配任务,并由中枢节点负责向从属节点分发任务与回收任务结果。基于The ONE模拟器进行实验,与在线任务分配(NTA)算法相比,HTA算法时间成本平均降低了24.9%,同时任务完成率平均提高150%。实验结果表明,HTA算法能够提高任务的完成速度,降低时间成本消耗。

关键词: 移动群智感知, 机会通信, 多任务分发, 社交, 中枢节点

CLC Number: