基于压缩感知的移动群智感知任务分发机制
|
摘要
针对移动群智感知任务中区域全覆盖感知成本过高问题,提出基于压缩感知的移动群智感知任务分发(CS-TD)机制。首先提出了感知任务整体成本模型,该模型综合考虑了参与感知任务的节点个数、节点的感知次数与数据上传次数;然后基于成本模型,分析感知节点的日常移动轨迹,结合压缩感知数据采集技术,提出了一种基于感知节点轨迹的压缩感知采样方法;其次通过区域全覆盖最少节点(RCLN)算法,选出最佳节点集合,对节点进行任务分配,利用压缩感知技术恢复节点数据;最后在多次感知任务的迭代中对感知节点的可信程度进行评定,保证任务方案的最优性。对CS-TD分发模型进行多次实验验证,与已有的Crowd Tasker算法相比,CS-TD算法平均成本降低了30%以上。CS-TD模型能有效降低感知节点的消耗,能在全覆盖感知任务中降低整体感知成本。
Since the cost of mobile crowdsensing in full coverage of area is excessively high, a Compressive Sensingbased mobile crowdsensing Task Distribution( CS-TD) mechanism was proposed. Firstly, an overall cost model of perceived task was proposed. In this model, the number of nodes participating in a perceived task, the number of nodes perceived and data uploaded were comprehensively considered. Then based on cost model, the daily movement trajectory of sensory node was analyzed, by combining with the compressed sensing data acquisition technology, a compressed sensing sampling method based on perceived node trajectory was proposed. Secondly, the optimal node set was selected by the Region Covers Least Nodes( RCLN) algorithm, the tasks were assigned to the nodes, and then the compressed sensing technology was used to recover node data. Finally, the trustworthiness of perceived node was evaluated in iteration of multiple perceived tasks to ensure the optimality of task plan. The CS-TD distribution model was tested several times. Compared with the existing Crowd Tasker algorithm, the average cost of CS-TD algorithm is reduced by more than 30%. CS-TD model can effectively reduce consumption of sensing node and reduce overall perceived cost in full coverage sensing task.
Since the cost of mobile crowdsensing in full coverage of area is excessively high, a Compressive Sensingbased mobile crowdsensing Task Distribution( CS-TD) mechanism was proposed. Firstly, an overall cost model of perceived task was proposed. In this model, the number of nodes participating in a perceived task, the number of nodes perceived and data uploaded were comprehensively considered. Then based on cost model, the daily movement trajectory of sensory node was analyzed, by combining with the compressed sensing data acquisition technology, a compressed sensing sampling method based on perceived node trajectory was proposed. Secondly, the optimal node set was selected by the Region Covers Least Nodes( RCLN) algorithm, the tasks were assigned to the nodes, and then the compressed sensing technology was used to recover node data. Finally, the trustworthiness of perceived node was evaluated in iteration of multiple perceived tasks to ensure the optimality of task plan. The CS-TD distribution model was tested several times. Compared with the existing Crowd Tasker algorithm, the average cost of CS-TD algorithm is reduced by more than 30%. CS-TD model can effectively reduce consumption of sensing node and reduce overall perceived cost in full coverage sensing task.
引文
[1]HU K,SIVARAMAN V,LUXAN B G,et al.Design and evaluation of a metropolitan air pollution sensing system[J].IEEE Sensors Journal,2016,16(5):1448-1459.
[2]MARJANOVIC M,GRUBESA S,ZARKO I P.Air and noise pollution monitoring in the city of Zagreb by using mobile crowdsensing[C]//Proceedings of the 2017 International Conference on Software,Telecommunications and Computer Networks.Piscataway,NJ:IEEE;2017:1-5.
[3]HO C J,VAUGHAN J W.Online task assignment in crowdsourcing markets[C]//Proceedings of the 2012 the National Conference on Artificial Intelligence.Los Angeles:AI Access Foundation,2012:45-51.
[4]ZHAO Q,ZHU Y,ZHU H,et al.Fair energy-efficient sensing task allocation in participatory sensing with smartphones[J].The Computer Journal,2017,60(6):850-865.
[5]ZHANG D,XIONG H,WANG L,et al.CrowdRecruiter:selecting participants for piggyback crowdsensing under probabilistic coverage constraint[C]//Proceedings of the 2014 ACM International Joint Conference on Pervasive and Ubiquitous Computing.New York:ACM,2014:703-714.
[6]XIONG H,ZHANG D,CHEN G,et al.CrowdTasker:maximizing coverage quality in piggyback crowdsensing under budget constraint[C]//Proceedings of the 2015 IEEE International Conference on Pervasive Computing and Communications.Piscataway,NJ:IEEE;2015:55-62.
[7]徐哲,李卓,陈昕.面向移动群智感知的多任务分发算法[J].计算机应用,2017,37(1):18-23.(XU Z,LI Z,CHEN X.Multitask assignment algorithm for mobile crowdsensing[J].Journal of Computer Applications,2017,37(1):18-23.)
[8]LIU Y,GUO B,WANG Y,et al.TaskMe:multi-task allocation in mobile crowd sensing[C]//Proceedings of the 2018 IEEE Transactions on Mobile Computing.Piscataway,NJ:IEEE,2018:403-414.
[9]XIONG H,ZHANG D,CHEN G,et al.i Crowd:near-optimal task allocation for piggyback crowdsensing[J].IEEE Transactions on Mobile Computing,2016,15(8):2010-2022.
[10]WANG L,ZHANG D,YANG D,et al.SPACE-TA:cost-effective task allocation exploiting intradata and interdata correlations in sparse crowdsensing[J].ACM Transactions on Intelligent Systems&Technology,2018,9(2):1-28.
[11]AHMED A,YASUMOTO K,YAMAUCHI Y,et al.Distance and time based node selection for probabilistic coverage in peoplecentric sensing[C]//Proceedings of the 2011 Annual IEEE Communications Society Conference on Sensor.Washington,DC:IEEEComputer Society,2011:134-142.
[12]赵东,马华东,刘亮.移动群智感知质量度量与保障[J].中兴通讯技术,2015,21(6):2-5.(ZHAO D,MA H D,LIU L.Quality measuring and assurance for mobile crowd sensing[J].ZTE Technology Journal,2015,21(6):2-5.)
[13]MATTHEW R,ZHANG Y,WALTER W,et al.Spatio-temporal compressive sensing and Internet traffic matrices(Extended Version)[J].IEEE/ACM Transactions on Networking,2012,20(3):662-676.
[14]石光明,刘丹华,高大化,等.压缩感知理论及其研究进展[J].电子学报,2009,37(5):1070-1081.(SHI G M,LIU D H,GAO D H,et al.Advances in theory and application of compressed sensing[J].Acta Electronica Sinica,2009,37(5):1070-1081.)
[15]宋洋,黄志清,张严心,等.基于压缩感知的无线传感器网络动态采样方法[J].计算机应用,2017,37(1):183-187.(SONGY,HUANG Z Q,ZHANG Y X,et al.)Dynamic sampling method for wireless sensor network based on compressive sensing[J].Journal of Computer Applications,2017,37(1):183-187.)
[16]KONG L,HE L,LIU X Y,et al.Privacy-preserving compressive sensing for crowdsensing based trajectory recovery[C]//Proceedings of the 2015 International Conference on Distributed Computing Systems.Piscataway,NJ:IEEE,2015:31-40.
[17]杨学峰,程耀瑜,王高.基于小波域压缩感知的遥感图像超分辨算法[J].计算机应用,2017,37(5):1430-1433.(YANG X F,CHENG Y Y,WANG G.Super-resolution algorithm for remote sensing images based on compressive sensing in wavelet domain[J].Journal of Computer Applications,2017,37(5):1430-1433.)
[18]WANG L,ZHANG D,PATHAK A,et al.CCS-TA:quality-guaranteed online task allocation in compressive crowdsensing[C]//Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing.New York:ACM;2015:683-694.
[19]HSIEH H P,LIN S D,ZHENG Y.Inferring air quality for station location recommendation based on urban big data[C]//Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM;2015:437-446.
[20]CANDES E J,TAO T.Decoding by linear programming[J].IEEE Transactions on Information Theory,2005,51(12):4203-4215.
[21]DAVENPORT M A.Random observations on random observations:Sparse signal acquisition and processing[D].Houston:Rice University,2010:1-187.
[22]王强,张培林,王怀光,等.压缩感知中测量矩阵构造综述[J].计算机应用,2017,37(1):188-196.(WANG Q,ZHANG P L,WANG H G,et al.Survey on construction of measurement matrices in compressive sensing[J].Journal of Computer Applications,2017,37(1):188-196.)
[23]潘立强,李建中,骆吉洲.传感器网络中一种基于时-空相关性的缺失值估计算法[J].计算机学报,2010,33(1):1-11.(PANL Q,LI J Z,LUO J Z.A Temporal and spatial correlation based missing values imputation algorithm in wireless sensor networks[J].Chinese Journal of Computers,2010,33(1):1-11.)
[2]MARJANOVIC M,GRUBESA S,ZARKO I P.Air and noise pollution monitoring in the city of Zagreb by using mobile crowdsensing[C]//Proceedings of the 2017 International Conference on Software,Telecommunications and Computer Networks.Piscataway,NJ:IEEE;2017:1-5.
[3]HO C J,VAUGHAN J W.Online task assignment in crowdsourcing markets[C]//Proceedings of the 2012 the National Conference on Artificial Intelligence.Los Angeles:AI Access Foundation,2012:45-51.
[4]ZHAO Q,ZHU Y,ZHU H,et al.Fair energy-efficient sensing task allocation in participatory sensing with smartphones[J].The Computer Journal,2017,60(6):850-865.
[5]ZHANG D,XIONG H,WANG L,et al.CrowdRecruiter:selecting participants for piggyback crowdsensing under probabilistic coverage constraint[C]//Proceedings of the 2014 ACM International Joint Conference on Pervasive and Ubiquitous Computing.New York:ACM,2014:703-714.
[6]XIONG H,ZHANG D,CHEN G,et al.CrowdTasker:maximizing coverage quality in piggyback crowdsensing under budget constraint[C]//Proceedings of the 2015 IEEE International Conference on Pervasive Computing and Communications.Piscataway,NJ:IEEE;2015:55-62.
[7]徐哲,李卓,陈昕.面向移动群智感知的多任务分发算法[J].计算机应用,2017,37(1):18-23.(XU Z,LI Z,CHEN X.Multitask assignment algorithm for mobile crowdsensing[J].Journal of Computer Applications,2017,37(1):18-23.)
[8]LIU Y,GUO B,WANG Y,et al.TaskMe:multi-task allocation in mobile crowd sensing[C]//Proceedings of the 2018 IEEE Transactions on Mobile Computing.Piscataway,NJ:IEEE,2018:403-414.
[9]XIONG H,ZHANG D,CHEN G,et al.i Crowd:near-optimal task allocation for piggyback crowdsensing[J].IEEE Transactions on Mobile Computing,2016,15(8):2010-2022.
[10]WANG L,ZHANG D,YANG D,et al.SPACE-TA:cost-effective task allocation exploiting intradata and interdata correlations in sparse crowdsensing[J].ACM Transactions on Intelligent Systems&Technology,2018,9(2):1-28.
[11]AHMED A,YASUMOTO K,YAMAUCHI Y,et al.Distance and time based node selection for probabilistic coverage in peoplecentric sensing[C]//Proceedings of the 2011 Annual IEEE Communications Society Conference on Sensor.Washington,DC:IEEEComputer Society,2011:134-142.
[12]赵东,马华东,刘亮.移动群智感知质量度量与保障[J].中兴通讯技术,2015,21(6):2-5.(ZHAO D,MA H D,LIU L.Quality measuring and assurance for mobile crowd sensing[J].ZTE Technology Journal,2015,21(6):2-5.)
[13]MATTHEW R,ZHANG Y,WALTER W,et al.Spatio-temporal compressive sensing and Internet traffic matrices(Extended Version)[J].IEEE/ACM Transactions on Networking,2012,20(3):662-676.
[14]石光明,刘丹华,高大化,等.压缩感知理论及其研究进展[J].电子学报,2009,37(5):1070-1081.(SHI G M,LIU D H,GAO D H,et al.Advances in theory and application of compressed sensing[J].Acta Electronica Sinica,2009,37(5):1070-1081.)
[15]宋洋,黄志清,张严心,等.基于压缩感知的无线传感器网络动态采样方法[J].计算机应用,2017,37(1):183-187.(SONGY,HUANG Z Q,ZHANG Y X,et al.)Dynamic sampling method for wireless sensor network based on compressive sensing[J].Journal of Computer Applications,2017,37(1):183-187.)
[16]KONG L,HE L,LIU X Y,et al.Privacy-preserving compressive sensing for crowdsensing based trajectory recovery[C]//Proceedings of the 2015 International Conference on Distributed Computing Systems.Piscataway,NJ:IEEE,2015:31-40.
[17]杨学峰,程耀瑜,王高.基于小波域压缩感知的遥感图像超分辨算法[J].计算机应用,2017,37(5):1430-1433.(YANG X F,CHENG Y Y,WANG G.Super-resolution algorithm for remote sensing images based on compressive sensing in wavelet domain[J].Journal of Computer Applications,2017,37(5):1430-1433.)
[18]WANG L,ZHANG D,PATHAK A,et al.CCS-TA:quality-guaranteed online task allocation in compressive crowdsensing[C]//Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing.New York:ACM;2015:683-694.
[19]HSIEH H P,LIN S D,ZHENG Y.Inferring air quality for station location recommendation based on urban big data[C]//Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM;2015:437-446.
[20]CANDES E J,TAO T.Decoding by linear programming[J].IEEE Transactions on Information Theory,2005,51(12):4203-4215.
[21]DAVENPORT M A.Random observations on random observations:Sparse signal acquisition and processing[D].Houston:Rice University,2010:1-187.
[22]王强,张培林,王怀光,等.压缩感知中测量矩阵构造综述[J].计算机应用,2017,37(1):188-196.(WANG Q,ZHANG P L,WANG H G,et al.Survey on construction of measurement matrices in compressive sensing[J].Journal of Computer Applications,2017,37(1):188-196.)
[23]潘立强,李建中,骆吉洲.传感器网络中一种基于时-空相关性的缺失值估计算法[J].计算机学报,2010,33(1):1-11.(PANL Q,LI J Z,LUO J Z.A Temporal and spatial correlation based missing values imputation algorithm in wireless sensor networks[J].Chinese Journal of Computers,2010,33(1):1-11.)