Multi-task assignment algorithm for mobile crowdsensing

doi:10.11772/j.issn.1001-9081.2017.01.0018

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 Zhe¹, LI Zhuo^1,2, CHEN Xin¹

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-09 Published:2017-01-10
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,2, 陈昕¹

1. 北京信息科技大学计算机学院, 北京 100101;
2. 网络文化与数字传播北京市重点实验室(北京信息科技大学), 北京 100101

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

Abstract

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:

TP393.01

XU Zhe, LI Zhuo, CHEN Xin. Multi-task assignment algorithm for mobile crowdsensing[J]. Journal of Computer Applications, 2017, 37(1): 18-23.

徐哲, 李卓, 陈昕. 面向移动群智感知的多任务分发算法[J]. 计算机应用, 2017, 37(1): 18-23.

References

[1] 赵东,马华东.群智感知网络的发展及挑战[J].信息通信技术,2014无卷号(5):66-70.(ZHAO D, MA H D. Development and challenges of crowd sensing networks[J]. Information and Communications Technologies, 2014(5):66-70.)
[2] DUTTA P, AOKI P, KUMAR N, et al. Common sense:participatory urban sensing using a network of handheld air quality monitors[C]//SenSys' 09:Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems. New York:ACM, 2009:349-350.
[3] KIM S, ROBSON C, ZIMMERMAN T, et al. Creek watch:pairing usefulness and usability for successful citizen science[C]//CHI' 11:Proceedings of the 2011 SIGCHI Conference on Human Factors in Computing Systems. New York:ACM, 2011:2125-2134.
[4] GANTI R, PHAM N, AHMADI H, et al. GreenGPS:a participatory sensing fuel-efficient maps application[C]//MobiSys' 10:Proceedings of the 8th International Conference on Mobile Systems, Applications, and Services. New York:ACM, 2010:151-164.
[5] SIMOENS P, XIAO Y, PILLAI P, et al. Scalable crowdsourcing of video from mobile devices[C]//MobiSys' 13:Proceedings of the 11th Annual International Conference on Mobile Systems, Applications, and Services. New York:ACM, 2013:139-152.
[6] RANA R K, CHOU C T, KANHERE S S, et al. Ear-phone:an end-to-end participatory urban noise mapping system[C]//Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks. New York:ACM, 2010:105-116.
[7] 陈翔,徐佳,吴敏,等.基于社会行为分析的群智感知数据收集研究[J].计算机应用研究,2015,32(12):3534-3541.(CHEN X, XU J, WU M, et al. Research of data collection technology in crowd sensing based on social behavior analysis[J]. Application Research of Computers, 2015, 32(12):3534-3541.)
[8] PELUSI L, PASSARELLA A, CONTI M. Opportunistic networ-king:data forwarding in disconnected mobile Ad Hoc networks[J]. IEEE Communications Magazine, 2006, 44(11):134-141.
[9] BULUT E, SZYMANSKI B K. Exploiting friendship relations for efficient routing in mobile social networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2012, 23(12):2254-2265.
[10] SRINIVASAN V, MOTANI M, OOI W T. Analysis and implications of student contact patterns derived from campus schedules[C]//Proceedings of the 12th Annual International Conference on Mobile Computing and Networking. New York:ACM, 2006:86-97.
[11] BIGWOOD G, HENDERSON T, REHUNATHAN D, et al. CRAWDAD dataset st_andrews_sassy[DS/OL].[2011-06-03] http://crawdad.org/st_andrews/sassy/20110603.
[12] XIAO M, WU J, HUANG L, et al. Multi-task assignment for crowdsensing in mobile social networks[C]//INFOCOM 2015:Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway, NJ:IEEE, 2015:2227-2235.
[13] ZHANG X, NEGLIA G, KUROSE J, et al. Performance modeling of epidemic routing[J]. Computer Networks, 2007, 51(10):2867-2891.
[14] FRENKIEL R H, BADRINATH B R, BORRAS J, et al. The infostations challenge:Balancing cost and ubiquity in delivering wireless data[J]. IEEE Personal Communications, 2000, 7(2):66-71.
[15] SPYROPOULOS T, PSOUNIS K, RAGHAVENDRA C S. Spray and wait:an efficient routing scheme for intermittently connected mobile networks[C]//Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking. New York:ACM, 2005:252-259.
[16] HUI P, CROWCROFT J, YONEKI E. BUBBLE rap:social-based forwarding in delay tolerant networks[C]//Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York:ACM, 2008:241-250.
[17] ALLAHVERDI A, NG C, CHENG T, et al. A survey of scheduling problems with setup times or costs[J]. European Journal of Operational Research, 2008, 187(3):985-1032.
[18] CHENG T, SIN C. A state-of-the-art review of parallel-machine scheduling research[J]. European Journal of Operational Research, 1990, 47(3):271-292.
[19] LENSTRA J K, SHMOYS D B, TARDOS É. Approximation algorithms for scheduling unrelated parallel machines[J]. Mathematical Programming, 1990, 46(1/2/3):259-271.
[20] KEMPE D, KLEINBERG J, TARDOS É. Maximizing the spread of influence through a social network[C]//Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2003:137-146.
[21] WANG Y, CONG G, SONG G, et al. Community-based greedy algorithm for mining top-k influential nodes in mobile social networks[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2010:1039-1048.
[22] EKMAN F, KERÄNEN A, KARVO J, et al. Working day movement model[C]//Proceedings of the 1st ACM SIGMOBILE Workshop on Mobility Models. New York:ACM, 2008:33-40.

Multi-task assignment algorithm for mobile crowdsensing

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 4

Recommended Articles

Metrics

[1]	Tingting LI, Junfeng CHU, Yanyan WANG. Group recommendation method based on implicit trust and group consensus [J]. Journal of Computer Applications, 2024, 44(2): 460-468.
[2]	CHEN Xiuhua, LIU Hui, XIONG Jinbo, MA Rong. Task requirement-oriented user selection incentive mechanism in mobile crowdsensing [J]. Journal of Computer Applications, 2019, 39(8): 2310-2317.
[3]	SONG Zihui, LI Zhuo, CHEN Xin. Mobile crowdsensing task distribution mechanism based on compressed sensing [J]. Journal of Computer Applications, 2019, 39(1): 15-21.
[4]	QIU Dehong, XU Fangxiang, LI Yuan. Constructing high-level architecture of online social network through community detection [J]. Journal of Computer Applications, 2015, 35(10): 2737-2741.