移动群智感知中基于社区的任务分发算法

doi:10.11959/j.issn.1000-436x.2019213

通信学报 ›› 2019, Vol. 40 ›› Issue (10): 42-54.doi: 10.11959/j.issn.1000-436x.2019213

移动群智感知中基于社区的任务分发算法

龙浩^1,², 张书奎¹(), 张洋¹, 张力¹

¹ 苏州大学计算机科学与技术学院，江苏苏州 215006
² 徐州工业职业技术学院信息与电气工程学院，江苏徐州 221002

修回日期:2019-08-23 出版日期:2019-10-25 发布日期:2019-11-07
作者简介:龙浩（1984- ），男，湖南长沙人，苏州大学博士生、讲师，主要研究方向为群智感知计算、数据挖掘、分布式计算。|张书奎（1966- ），男，内蒙古呼和浩特人，博士，苏州大学教授、博士生导师，主要研究方向为物联网、无线传感器网络、信息安全、群体感知计算、智能信息处理等。|张洋（1989- ），男，江苏苏州人，苏州大学硕士生，主要研究方向为物联网、信息安全、群体感知计算、智能信息处理等。|张力（1983- ），男，江苏镇江人，苏州大学博士生，主要研究方向为群智感知、数据挖掘、并行计算。
基金资助:
国家自然科学基金资助项目(61201212);江苏省高等学校自然科学研究面上项目(19KJB520061);徐州市应用基础研究计划基金资助项目(KC17074);苏州市融合通信重点实验室(SKLCC2013XX);江苏省青蓝工程人才培养计划(102508999008);苏州市重点产业技术创新前瞻性应用研究项目(SYG201730)

Task distribution algorithm based on community in mobile crowd sensing

Hao LONG^1,², Shukui ZHANG¹(), Yang ZHANG¹, Li ZHANG¹

¹ School of Computer Science and Technology,Soochow University,Suzhou 215006,China
² School of Information and Electrical Engineering,Xuzhou College of Industrial Technology,Xuzhou 221002,China

Revised:2019-08-23 Online:2019-10-25 Published:2019-11-07
Supported by:
The National Natural Science Foundation of China(61201212);The Natural Science Research Project (General Program) of Jiangsu Higher Education Institution(19KJB520061);Science and Technology Project of Xuzhou of China(KC17074);Suzhou Key Laboratory of Converged Communication(SKLCC2013XX);Blue Project of Jiangsu of China(102508999008);Prospective Application Foundation Research of Suzhou of China(SYG201730)

摘要/Abstract

摘要：

针对移动群智感知（MCS）任务分发的有效性和精准性问题，提出了基于社区的任务分发算法。为了解决所提问题，该方法首先通过计算移动节点间的最小生成树、连接参量、社区融合度，抽象和识别出节点的行为模式，将用户合理划分成不同的社区，然后计算感知任务与社区行为模式特征值的匹配度，根据匹配度由社区的中心节点完成任务的分发。仿真结果表明，与其他算法相比，所提方法有效地提高了任务分发的精确性和任务完成率，节约了任务完成的时间成本。

关键词: 移动群智感知, 社区, 行为模式, 任务分发, 匹配度

Abstract:

A community-based task distribution algorithm was proposed to solve the problem of the validity of mobile crowd sensing (MCS) task distribution.By calculating the minimum spanning tree (MST),the connection parameter (CP) and the community convergence degree (CI) between the mobile nodes,the behavior patterns of the users were abstracted and identified to rationally divide the nodes into different communities.Then,the eigenvalue matching degree of the community behavior patterns with the sensing task was calculated.According to the matching degree,the distribution of the corresponding tasks was completed by the central node of the community.The simulation results show that the proposed method can effectively improve the accuracy of the task distribution and the task completion rate,and save the time cost of the task completion.

Key words: mobile crowd sensing, community, behavior pattern, task distribution, matching degree

中图分类号:

TP393

龙浩, 张书奎, 张洋, 张力. 移动群智感知中基于社区的任务分发算法[J]. 通信学报, 2019, 40(10): 42-54.

Hao LONG, Shukui ZHANG, Yang ZHANG, Li ZHANG. Task distribution algorithm based on community in mobile crowd sensing[J]. Journal on Communications, 2019, 40(10): 42-54.

图/表 15

图1

图2

图3

图4

图5

表1

图6

图7

图8

图9

图10

图11

图12

图13

图14

参考文献 24

[1]	吴垚, 曾菊儒, 彭辉 ,等. 群智感知激励机制研究综述[J]. 软件学报, 2016,27(8): 2025-2047.
	WU Y , ZENG J R , PENG H ,et al. Survey on incentive mechanisms for crowd sensing[J]. Journal of Software, 2016,27(8): 2025-2047.
[2]	OMOKARO O , PAYTON J . FlySensing:a case for crowdsensing in the air[C]// IEEE International Conference on Pervasive Computing ＆Communication Workshops, 2014: 545-550.
[3]	ZAPPATORE M , LONGO A , BOCHICCHIO M A ,et al. A crowdsensing approach for mobile learning in acoustics and noise monitoring[C]// ACM Symposium on Applied Computing. 2016: 219-224.
[4]	HU S . SmartRoad:smartphone-based crowd sensing for traffic regulator detection and identification[J]. ACM Transactions on Sensor Networks, 2015,11(4): 1-27.
[5]	WEI G , ZHANG B , CHENG L . Task assignment in mobile crowdsensing:present and future directions[J]. IEEE Network, 2018,PP(99): 1-8.
[6]	安健, 彭振龙, 桂小林 . 群智感知中基于公交系统的任务分发机制研究[J]. 计算机学报, 2019(2): 295-308.
	AN J , PENG Z L , GUI X L . Research on task distribution mechanism based on public transit system in crowd sensing[J]. Chinese Journal of Computers, 2019(2): 295-308.
[7]	刘琰, 郭斌, 吴文乐 ,等. 移动群智感知多任务参与者优选方法研究[J]. 计算机学报, 2017,40(8): 1872-1887.
	LIU Y , GUO B , WU W L ,et al. Multitask-oriented participant selection in mobile crowd sensing[J]. Chinese Journal of Computers, 2017,40(8): 1872-1887.
[8]	XIAO M J , WU J , HUANG L S ,et al. Online task assignment for crowdsensing in predictable mobile social networks[J]. IEEE Transactions on Mobile Computing, 2017,16(8): 2306-2320.
[9]	YU D H , ZHOU Z , WANG Y . Crowdsourcing software task assignment method for collaborative development[J]. IEEE Access, 2019,10(7): 35743-35754.
[10]	徐哲, 李卓, 陈昕 . 面向移动群智感知的多任务分发算法[J]. 计算机应用, 2017,37(1): 18-23.
	XU Z , LI Z , CHEN X . Multi-task assignment algorithm for mobile crowd sensing[J]. Journal of Computer Applications, 2017,37(1): 18-23.
[11]	杨玉仁, 张书奎, 龙浩 ,等. 群智感知中基于社交属性及有效用户计算的任务分发机制[J]. 计算机应用研究, 2019(5): 1493-1499.
	YANG Y R , ZHANG S K , LONG H ,et al. Task distribution mechanism based on social attribute and effective user calculation in crowd sensing[J]. Application Research of Computers, 2019(5): 1493-1499.
[12]	WANG L , YU Z , ZHANG D ,et al. Heterogeneous multi-task assignment in mobile crowdsensing using spatiotemporal correlation[J]. IEEE Transactions on Mobile Computing, 2018,18(1): 84-97.
[13]	张君涛, 赵智慧, 周四望 . 矢量任务地图:群智感知任务渐进式分发方法[J]. 计算机学报, 2017,40(8): 1946-1960.
	ZHANG J T , ZHAO Z H , ZHOU S W . Vector task map:progressive task allocation in crowd-sensing[J]. Chinese Journal of Computers, 2017,40(8): 1946-1960.
[14]	SAOUD B , MOUSSAOUI A . Community detection in networks based on minimum spanning tree and modularity[J]. Physica A:Statistical Mechanics ＆ Its Applications, 2016(460): 230-234.
[15]	吕少卿, 张玉清, 刘东航 ,等. 在线社交网络中 Spam 相册检测方案[J]. 通信学报, 2016,37(9): 82-91.
	LYU S Q , ZHANG Y Q , LIU D H ,et al. Detecting Spam albums in online social network[J]. Journal on Communications, 2016,37(9): 75-91.
[16]	BULUT E , SZYMANSKI B K . Exploiting friendship relations for efficient routing in mobile social networks[J]. IEEE Transactions on Parallel ＆ Distributed Systems, 2012,23(23): 2254-2265.
[17]	XIONG P , ZHU T , NIU W ,et al. A differentially private algorithm for location data release[J]. Knowledge and Information Systems, 2016,47(3): 647-669.
[18]	REDDY S , ESTRIN D , SRIVASTAVA M . Recruitment framework for participatory sensing data collections[C]// Pervasive Computing,International Conference. ACM, 2010: 138-155.
[19]	SUN H , HUANG J , ZHANG X ,et al. IncOrder:incremental density-based community detection in dynamic networks[J]. Knowledge-Based Systems, 2014(72): 1-12.
[20]	HOSSEN M S , AHMED M T , RAHIM M S . Effects of buffer size and mobility models on the optimization of number of message copies for multi-copy routing protocols in scalable delay-tolerant networks[C]// International Conference on Innovations in Science. IEEE, 2017: 1-4.
[21]	张兴盛, 余敦辉, 张万山 ,等. 时空众包环境下时效均衡的在线任务分配算法[J]. 计算机应用, 2019,39(5): 1357-1363.
	ZHANG X S , YU D H , ZHANG W S ,et al. utility balanced online task assignment algorithm under spatial crowdsourcing environment[J]. Journal of Computer Applications, 2019,39(5): 1357-1363.
[22]	PAOLO B , ANTONIO C , LUCA F ,et al. Scalable and cost-effective assignment of mobile crowdsensing tasks based on profiling trends and prediction:the participact living lab experience[J]. Sensors, 2015,15(8): 18613-18640.
[23]	LAURILA J K , GATICA-PEREZ D , AAD I ,et al. The mobile data challenge:big data for mobile computing research[C]// Mobile Data Challenge by Nokia Workshop. IEEE, 2012: 1-8.
[24]	刘辉, 李盛恩 . 时空众包环境下基于统计预测的自适应阈值算法[J]. 计算机应用, 2018,38(2): 415-420.
	LIU H , LI S G . Adaptive threshold algorithm based on statistical prediction under spatial crowdsourcing environment[J]. Journal of Computer Applications, 2018,38(2): 415-420.

移动群智感知中基于社区的任务分发算法

Task distribution algorithm based on community in mobile crowd sensing

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献 24

相关文章 15

Metrics

推荐阅读 0

网络	n	m	k	minc	maxc	mu
a	10 000	98 325	20	20	100	0.1～0.8
b	10 000	98 135	20	10	50	0.1～0.8

[1]	高阳, 张宏莉. 基于随机游走的社区发现方法综述[J]. 通信学报, 2023, 44(6): 198-210.
[2]	刘树新,李星,陈鸿昶,王凯. 基于资源传输匹配度的复杂网络链路预测方法[J]. 通信学报, 2020, 41(6): 70-79.
[3]	毕俊蕾,李致远. 机会社交网络中基于时变兴趣社区的查询消息路由算法[J]. 通信学报, 2019, 40(9): 86-94.
[4]	刘媛妮,李垚焬,李慧聪,李万林,张建辉,赵国锋. 基于拍卖模型的移动群智感知网络激励机制[J]. 通信学报, 2019, 40(7): 208-222.
[5]	王丽娜,郭晓东,汪润. 面向中文用户评论的自动化众包攻击方法[J]. 通信学报, 2019, 40(6): 1-13.
[6]	史艳翠,王嫄,赵青,张贤坤. 基于局部扩展的社区发现研究现状[J]. 通信学报, 2019, 40(1): 149-162.
[7]	刘强,贾焰,方滨兴,周斌,胡玥,黄九鸣. 并行社区发现算法的可扩展性研究[J]. 通信学报, 2018, 39(4): 13-20.
[8]	彭颖,王淖,王高才. 移动社会网络中基于社区的最优能效路由策略研究[J]. 通信学报, 2017, 38(5): 128-144.
[9]	陈晶,万云. 社交网络中基于模块度最大化的标签传播算法的研究[J]. 通信学报, 2017, 38(2): 25-33.
[10]	邓琨,李文平,余法红,张健沛. 基于多核心标签传播的复杂网络重叠社区识别方法[J]. 通信学报, 2017, 38(2): 53-66.
[11]	曹玖新,陈高君,杨婧,朱子青,刘波. 基于社会属性的PSN消息路由算法[J]. 通信学报, 2015, 36(5): 13-22.
[12]	黄永锋,董永强,张三峰,吴国新. 基于社会特征周期演化的机会移动网络路由转发策略[J]. 通信学报, 2015, 36(3): 21-32.
[13]	郭昆,郭文忠,邱启荣,张歧山. 基于局部近邻传播及用户特征的社区识别算法[J]. 通信学报, 2015, 36(2): 68-79.
[14]	王桐,赵昕琳. 基于改进蛙跳算法的社区划分方法[J]. 通信学报, 2014, 35(Z2): 48-52.
[15]	王桐，赵昕琳. 基于改进蛙跳算法的社区划分方法[J]. 通信学报, 2014, 35(Z2): 8-52.