移动感知器网络中基于随机游走和协作关系的任务分发算法

doi:10.3969/j.issn.0372-2112.2019.08.001

电子学报 ›› 2019, Vol. 47 ›› Issue (8): 1601-1611.DOI: 10.3969/j.issn.0372-2112.2019.08.001

• 学术论文 • 下一篇

移动感知器网络中基于随机游走和协作关系的任务分发算法

陶冶¹, 张书奎¹, 张力¹, 龙浩^1,2, 王进¹

1. 苏州大学计算机科学与技术学院, 江苏苏州 215006;
2. 徐州工业职业技术学院, 江苏徐州 221140

收稿日期:2018-09-09 修回日期:2018-12-11 出版日期:2019-08-25
- 通讯作者:
- 张书奎
- 作者简介:
- 陶冶男,1992年生于江苏泗阳,现为苏州大学计算机科学与技术学院硕士研究生,主要研究方向为群智感知、隐私保护等.E-mail:ytao@stu.suda.edu.cn;张力男,1980年生于安徽肥东,博士生,主要研究方向为物联网、无线传感器网络、智能信息处理、群智感知、信息安全等.E-mail:greenwuhu@126.com;龙浩男,1984年生于湖南长沙,博士生,主要研究方向为物联网、无线传感器网络、智能信息处理、群智感知、信息安全等.E-mail:longhhao@163.com;王进男,1985年生于安徽,博士,副教授,硕士生导师,主要研究方向为边缘计算,线性编码,信息安全,智慧城市等.E-mail:wjin1985@suda.edu.cn
- 基金资助:
- 预研基金 (No.61403120402）; 国家自然科学基金 (No.61672370）; 苏州市重点产业技术创新前瞻性应用研究项目 (No.SYG201730）; 江苏省高校自然科学基金 (No.16KJB520040）; 徐州市应用基础研究计划项目 (No.KC17074）; 江苏省青蓝工程人才培养计划; 苏州市融合通信重点实验室 (No.SKLCC2013XX）; 软件新技术与产业化协同创新中心部分资助

Task Distribution Algorithm Based on Random Walk and Cooperative Relationship in Mobile Sensor Networks

TAO Ye¹, ZHANG Shu-kui¹, ZHANG Li¹, LONG Hao^1,2, WANG Jin¹

1. School of Computer Science and Technology, Soochow University, Suzhou, Jiangsu 215006, China;
2. Xuzhou College of Industrial Technology, Xuzhou, Jiangsu 221140, China

Received:2018-09-09 Revised:2018-12-11 Online:2019-08-25 Published:2019-08-25

摘要/Abstract

摘要： 关于移动感知器网络中感知任务的分发问题，目前学术界已经有了诸多相关研究.然而，这些研究很少涉及到多个智能体协作完成复杂感知任务问题.针对这种情况，首先，通过分析移动感知器网络的结构特征、智能体相互之间、以及智能体和感知任务之间的关系，本文提出了智能体之间协作关系强度和智能体对感知任务适应度两个概念，并讨论了二者对于移动感知器网络中感知任务动态分发的作用.其次，在上述概念的基础上，将二者融合为偏好因子，提出了基于随机游走和协作关系的任务分发算法（TDCR，Task Distribution With Cooperative Relationship），通过该算法达到提高任务分发效率的目的.最后，将TDCR与Personal Rank算法（PR）、HITS算法对比分析，表明所提出的算法TDCR在任务分发效率和准确度等性能指标上有较好的提升.

关键词: 移动感知器网络, 智能体, 感知任务, 二分图, 任务分发

Abstract: There have been many studies on the distribution of sensing tasks in mobile sensor networks.However,these studies rarely involve the problem that many agents in a mobile sensor network cooperate to perform complex sensing tasks.In order to address this challenge,first,we combined the structural characteristics of mobile sensor networks,the relationship between agents,and the relationship between agents and sensing tasks.Then we proposed the strength of cooperation between agents and the fitness of agents to sensing tasks,and discussed their roles in the dynamic distribution of sensing tasks in mobile sensor networks.Second,based on the above concepts,the two were unified as preference factors.In order to achieve the goal of improving task distribution efficiency,a task distribution algorithm based on random walk and cooperative relationship was proposed.At last,the comparison with the Personal Rank(PR) algorithm and HITS algorithm shows that the proposed algorithm has superiority in task distribution efficiency and accuracy.

Key words: mobile sensor network, agent, sensing task, bipartite graph, task distribution

中图分类号:

TP393.04

陶冶, 张书奎, 张力, 龙浩, 王进. 移动感知器网络中基于随机游走和协作关系的任务分发算法[J]. 电子学报, 2019, 47(8): 1601-1611.

TAO Ye, ZHANG Shu-kui, ZHANG Li, LONG Hao, WANG Jin. Task Distribution Algorithm Based on Random Walk and Cooperative Relationship in Mobile Sensor Networks[J]. Acta Electronica Sinica, 2019, 47(8): 1601-1611.

参考文献

[1] Raghu K.Ganti,Fan Ye,Hui Lei.Mobile Crowdsensing:current state and future challenges[J].IEEE Communications Magazine,2011,49(11):32-39.
[2] 刘云浩.群智感知计算[J].中国计算机学会通信,2012,8(10):38-41. Yunhao Liu.Crowd sourcing computing[J].Communication of the CCF,2012,8(10):38-41.(in Chinese)
[3] Huadong Ma,Dong Zhao,Peiyan Yuan.Opportunities in mobile crowd sensing[J].IEEE Communications Magazine,2014,52(8):29-35.
[4] L G Jaimes,I J Vergara,A Raij.A location-based incentive algorithm for consecutive crowd sensing tasks[J].IEEE Latin America Transactions,2016,14(2):811-817.
[5] Prashanth Mohan,Venkata N.Padmanabhan,Ramachandran Ramjee.Nericell:Rich monitoring of road and traffic conditions using mobile smartphones[A].Proceedings of the 6th International Conference on Embedded Networked Sensor Systems[C].Raleigh:ACM,2008.323-336.
[6] Prabal Dutta,Paul M Aoki,Neil Kumar,et al.Common sense:Participatory urban sensing using a network of handheld air quality monitors[A].International Conference on Embedded Networked Sensor Systems[C].New York:ACM,2009.349-350.
[7] Sara Hachem,Vivien Mallet,Raphael Ventura,et al.Monitoring noise pollution using the urban civics middleware[A].IEEE First International Conference on Big Data Computing Service and Applications[C].USA:IEEE,2015.52-61.
[8] Villanueva F J,David Villa,Santofimia M J,et al.Crowdsensing smart city parking monitoring[A].2015 IEEE First International Conference on Big Data Computing Service and Applications[C].USA:IEEE,2015.751-756.
[9] Pryss R,Reichert Manfred,Herrmann Jochen,et al.Mobile corwd sensing in clinical and psychological trials-a case study[A].IEEE 28th International Symposium on Computer-Based Medical Systems[C].Brazil:IEEE,2015.23-24.
[10] 程如洪,肖明军.一种协作群智感知任务分配的贪心算法[J].小型计算机系统,2017,38(5):1039-1043. Ruhong Cheng,Mingjun Xiao.Greedy task assignment algorithm collaborative crowdsensing[J].Journal of Chinese Computer Systems,2017,38(5):1039-1043.(in Chinese)
[11] 张晓航,李国良,冯建华.大数据群体计算中用户主题感知的任务分配[J].计算机研究与发展,2015,52(2):309-317. Xiaohang Zhang,Guoliang Li,Jianhua Feng.Theme-aware task assignment in crowd computing on big data[J].Journal of Computer Research and Development,2015,52(2):309-317.(in Chinese)
[12] Foschini Luca,Cardone Giuseppe,Corradi Antonio,et al.Fostering participaction in smart cities:A Geo-social crowdsensing platform[J].IEEE Communications Magazine,2013,51(6):112-119.
[13] Cong Shi,Vasileios Lakafosis,Mostafa H.Ammar,et al.Serendipity:enabling remote computing among intermittently connected mobile devices[A].Proceedings of the thirteenth ACM international symposium on Mobile Ad Hoc Networking and Computing[C].USA:ACM,2012.145-154.
[14] Maotian Zhang, Panlong Yang,et al.Quality-aware sensing coverage in budget-constrained mobile crowdsensing networks[J].IEEE Transactions on Vehicular Technology,2016,65(9):7698-7707.
[15] Haiming Jin,Lu Su,Danyang Chen,et al.Quality of infomation aware incentive mechanisms for mobile crowd sensing systems[A].ACM International Symposium on Mobile Ad Hoc Networking & Computing[C].New York:ACM,2015.167-176.
[16] Kai Han,Chi Zhang,Jun Luo.Truthful scheduling mechanisms for powering mobile crowdsensing[J].Computers,IEEE Transactions on,2016,65(1):294-307.
[17] Mingjun Xiao,Jie Wu,Liusheng Huang,et al.Multi-task assignment for crowdsensing in mobile social networks[A].IEEE Conference on Computer Communications[C].Hong Kong:IEEE,2015.2227-2235.
[18] Layla Pournajaf,Li Xiong,Vaidy Sunderam,et al.Spatial task assignment for crowd sensing with cloaked locations[A].IEEE 15th International Conference on Mobile Data Management[C].Australia:IEEE,2014.73-82.
[19] Haoyi Xiong,Daqing Zhang,Leye Wang,et al.EMC³:Energy-efficient data transfer in mobile crowdsensing under full coverage constraint[J].IEEE Transactions on Mobile Computing,2015,14(7):1536-1233.
[20] Leye Wang,Daqing Zhang,Haoyi Xiong.EffSense:Energy-efficient and cost-effective data uploading in mobile crowdsensing[A].Proceedings of the 2013 ACM conference on Pervasive and ubiquitous computing adjunct publication[C].New York:ACM,2013.1075-1086.
[21] 刘建伟,黎海恩,等.概率图模型表示理论综述[J].电子学报,2016,44(5):1219-1226. Jianwei Liu,Haien Li,et al.A survey on the representation theory of probabilistic graphical model[J].Acta Electronica Sinica,2016,44(5):1219-1226.(in Chinese)
[22] 牛新征,牛嘉郡,苏大壮,等.基于加权内容-结构网络和随机游走的社团划分算法[J].电子学报,2017,45(9):2135-2142. Xinzheng Niu,Jiajun Niu,Dazhuang Su.Community detection based on weighted content-structural network and random walks[J].Acta Electronica Sinica,2017,45(9):2135-2142.(in Chinese)
[23] 方晨,张恒巍,王娜,王晋东.基于随机游走和多样性图排序的个性化服务推荐方法[J].电子学报,2018,46(11):2773-2780. Chen Fang,Hengwei Zhang,Na Wang,Jindong Wang.Personalized service recommendation method based on random walk and diversified graph ranking[J].Acta Electronica Sinica,2018,46(11):2773-2780.(in Chinese)
[24] Bingjing Cai,Haiying Wang,Huiru Zheng,Hui Wang.An improved random clustering algorithm for community detection in complex networks[A].IEEE International Conference on Systems,Man and Cybernetics[C].USA:IEEE,2011.2162-2167.
[25] Langville Amy N,Meyer Carl D,MA H.Deeper inside PageRank[J].Internet Mathematics,2004,1(3):335-380.
[26] Min Zhang,Weijian Luo,Xufa Wang.Differential evolution with dynamic stochastic selection for constrained optimization[J].Information Science,2008,178(15):3043-3074.
[27] Pei Xu,Ye Mao,Xue Li,et al.Object detection using voting spaces trained by few samples[J].Optical Engineering,2013,52(9):093105.
[28] Pei Xu,Ye Mao,Min Fu,et al.Object Detection Based on Several Samples with Trained Hough Spaces[M].Pattern Recognition, Berlin:Springer,2012:235-242.
[29] Taher H Haveliwala.Topic-sensitive pagerank:a context-sensitive ranking algorithm for web search[J].IEEE Transactions on Knowledge and Data Engineering,2003,15(4):784-796.
[30] Jon M Kleinberg.Authoritative sources in a hyperlinked environmet[J].Journal of the ACM,1999,46(5):604-632.
[31] 杨博,陈贺昌,朱冠宇,赵学华.基于超链接多样性分析的新型网页排名算法[J].计算机学报,2014,37(4):833-847. Bo Yang,Hechang Chen,Guanyu Zhu,Xuehua Zhao.A novel page ranking algorithm based on analyzing the diversity of inbound hyperlinks[J].Chinese Journal of Computers,2014,37(4):833-847.(in Chinese)
[32] Stanley Milgram.The small world problem[J].Psychology today,1967,2(1):60-67.
[33] Peking University open research data@re3data.org[DB/OL].http://service.re3data.org/repository/r3d100011589.2018-01-26.
[34] Peking University open research data platform@github[DB/OL].https://github.com/pengchengluo/Peking-University-Open-Research-Data-Platform.2018-01-26.
[35] Mikolajczy Krystian,Schmid Cordelia.A performance evalution of local descriptors[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(10):1615-1630.

移动感知器网络中基于随机游走和协作关系的任务分发算法

Task Distribution Algorithm Based on Random Walk and Cooperative Relationship in Mobile Sensor Networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	饶宁, 许华, 蒋磊, 宋佰霖, 史蕴豪. 基于多智能体深度强化学习的分布式协同干扰功率分配算法[J]. 电子学报, 2022, 50(6): 1319-1330.
[2]	张涛, 张文涛, 代凌, 陈婧怡, 王丽, 魏倩茹. 基于序贯博弈多智能体强化学习的综合模块化航空电子系统重构方法[J]. 电子学报, 2022, 50(4): 954-966.
[3]	肖硕, 黄珍珍, 张国鹏, 杨树松, 江海峰, 李天旭. 基于SAC的多智能体深度强化学习算法[J]. 电子学报, 2021, 49(9): 1675-1681.
[4]	陈健瑞, 王景璟, 侯向往, 方政儒, 杜军, 任勇. 挺进深蓝：从单体仿生到群体智能[J]. 电子学报, 2021, 49(12): 2458-2467.
[5]	贾枭, 席建祥, 刘光斌, 杜柏阳. 基于脉冲控制的时延异构多智能体编队控制[J]. 电子学报, 2018, 46(12): 2957-2963.
[6]	杨洪勇, 张玉玲, 寇光杰, 丁宏. 基于采样数据的时延多智能体系统的动态路径跟踪[J]. 电子学报, 2013, 41(9): 1760-1764.
[7]	朱旭, 闫建国, 屈耀红. 高阶多智能体系统的一致性分析[J]. 电子学报, 2012, 40(12): 2466-2471.
[8]	杨洪勇;田生文;张嗣瀛. 具有领航者的时延多智能体系统的一致性[J]. 电子学报, 2011, 39(4): 872-876.
[9]	刘春阳;谭应清;柳长安;马莹巍. 多智能体强化学习在足球机器人中的研究与应用[J]. 电子学报, 2010, 38(8): 1958-1962.
[10]	潘晓英;焦李成;刘芳. 粒度智能体进化分类算法[J]. 电子学报, 2009, 37(3): 628-633.
[11]	程玉胜;张佑生;胡学钢;章晓良. 基于任意分割的串行进位链规则获取的计算流程[J]. 电子学报, 2009, 37(12): 2797-2802.
[12]	李剑, 景博, 杨义先. 一种基于奖励机制的agent联盟形成策略[J]. 电子学报, 2008, 36(S1): 71-75.
[13]	周雅兰;王甲海;印鉴. 一种基于分布估计的离散粒子群优化算法[J]. 电子学报, 2008, 36(6): 1242-1248.
[14]	秦斌, 吴敏, 王欣, 阳春华. 基于多智能体强化学习的焦炉集气管压力多级协调控制[J]. 电子学报, 2006, 34(10): 1847-1851.
[15]	彭宇新;Ngo Chong-Wah;肖建国;. 一种基于二分图最优匹配的镜头检索方法[J]. 电子学报, 2004, 32(7): 1135-1139.