Task Distribution Algorithm Based on Random Walk and Cooperative Relationship in Mobile Sensor Networks
TAO Ye1, ZHANG Shu-kui1, ZHANG Li1, LONG Hao1,2, WANG Jin1
1. School of Computer Science and Technology, Soochow University, Suzhou, Jiangsu 215006, China;
2. Xuzhou College of Industrial Technology, Xuzhou, Jiangsu 221140, China
摘要 关于移动感知器网络中感知任务的分发问题，目前学术界已经有了诸多相关研究.然而，这些研究很少涉及到多个智能体协作完成复杂感知任务问题.针对这种情况，首先，通过分析移动感知器网络的结构特征、智能体相互之间、以及智能体和感知任务之间的关系，本文提出了智能体之间协作关系强度和智能体对感知任务适应度两个概念，并讨论了二者对于移动感知器网络中感知任务动态分发的作用.其次，在上述概念的基础上，将二者融合为偏好因子，提出了基于随机游走和协作关系的任务分发算法（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.
陶冶, 张书奎, 张力, 龙浩, 王进. 移动感知器网络中基于随机游走和协作关系的任务分发算法[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. 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.EMC3: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.
2019, Vol. 47 
