基于压缩感知的移动群智感知任务分发机制

doi:10.11772/j.issn.1001-9081.2018071595

计算机应用 ›› 2019, Vol. 39 ›› Issue (1): 15-21.DOI: 10.11772/j.issn.1001-9081.2018071595

• 2018年全国开放式分布与并行计算学术年会(DPCS 2018)论文 • 上一篇下一篇

基于压缩感知的移动群智感知任务分发机制

宋子晖^1,2, 李卓^1,2, 陈昕²

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

收稿日期:2018-07-19 修回日期:2018-08-08 出版日期:2019-01-10 发布日期:2019-01-21
通讯作者: 李卓
作者简介:宋子晖(1993-),男,河南安阳人,硕士研究生,CCF会员,主要研究方向:移动群智感知;李卓(1983-),男,河南南阳人,副教授,博士,CCF会员,主要研究方向:移动无线网络、分布式计算;陈昕(1965-),男,江西南昌人,教授,博士,CCF会员,主要研究方向:网络性能评价、网络安全。
基金资助:
国家自然科学基金资助项目（61502040）；北京市属高校高水平教师队伍建设支持计划青年拔尖人才培育计划项目（CIT&TCD201804055）；北京信息科技大学“勤信人才”培养计划项目；网络文化与数字传播北京市重点实验室开放课题项目（ICDDXN001）。

Mobile crowdsensing task distribution mechanism based on compressed sensing

SONG Zihui^1,2, LI Zhuo^1,2, CHEN Xin²

1. Beijing Key Laboratory of Internet Culture and Digital Dissemination(Beijing Information Science and Technology University), Beijing 100101, China;
2. School of Computer Science, Beijing Information Science and Technology University, Beijing 100101, China

Received:2018-07-19 Revised:2018-08-08 Online:2019-01-10 Published:2019-01-21
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61502040), the Beijing Municipal Program for Top Talent Cultivation (CIT&TCD201804055), the Qinxin Talent Program of Beijing Information Science and Technology University, the Open Program of Beijing Key Laboratory of Internet Culture and Digital Dissemination (ICDDXN001).

摘要/Abstract

摘要：

针对移动群智感知任务中区域全覆盖感知成本过高问题，提出基于压缩感知的移动群智感知任务分发（CS-TD）机制。首先提出了感知任务整体成本模型，该模型综合考虑了参与感知任务的节点个数、节点的感知次数与数据上传次数；然后基于成本模型，分析感知节点的日常移动轨迹，结合压缩感知数据采集技术，提出了一种基于感知节点轨迹的压缩感知采样方法；其次通过区域全覆盖最少节点（RCLN）算法，选出最佳节点集合，对节点进行任务分配，利用压缩感知技术恢复节点数据；最后在多次感知任务的迭代中对感知节点的可信程度进行评定，保证任务方案的最优性。对CS-TD分发模型进行多次实验验证，与已有的CrowdTasker算法相比，CS-TD算法平均成本降低了30%以上。CS-TD模型能有效降低感知节点的消耗，能在全覆盖感知任务中降低整体感知成本。

关键词: 压缩感知, 移动群智感知, 任务分发, 区域覆盖, 移动轨迹

Abstract:

Since the cost of mobile crowdsensing in full coverage of area is excessively high, a Compressive Sensing-based 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 CrowdTasker 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.

Key words: Compressive Sensing (CS), mobile crowdsensing, task distribution, regional coverage, moving trajectory

中图分类号:

TP393.01

宋子晖, 李卓, 陈昕. 基于压缩感知的移动群智感知任务分发机制[J]. 计算机应用, 2019, 39(1): 15-21.

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.

参考文献

[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. iCrowd: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 people-centric sensing[C]//Proceedings of the 2011 Annual IEEE Communications Society Conference on Sensor. Washington, DC:IEEE Computer 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.(SONG Y, 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.(PAN L 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.)

基于压缩感知的移动群智感知任务分发机制

Mobile crowdsensing task distribution mechanism based on compressed sensing

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李卓, 宋子晖, 沈鑫, 陈昕. 边缘计算支持下的移动群智感知本地差分隐私保护机制[J]. 计算机应用, 2021, 41(9): 2678-2686.
[2]	沈子懿, 王卫亚, 蒋东华, 荣宪伟. 基于Hopfield混沌神经网络和压缩感知的可视化图像加密算法[J]. 计算机应用, 2021, 41(10): 2893-2899.
[3]	席雅睿, 乔志伟, 温静, 张艳娇, 杨雯晶, 闫慧文. 基于Chambolle-Pock算法框架的高阶TV图像重建算法[J]. 计算机应用, 2020, 40(6): 1793-1798.
[4]	徐志强, 蒋铁钢, 杨立波. 基于随机支撑挑选的广义正交匹配追踪算法[J]. 计算机应用, 2020, 40(4): 1104-1108.
[5]	杨立波, 蒋铁钢, 徐志强. 基于混合梯度的硬阈值追踪算法[J]. 计算机应用, 2020, 40(3): 912-916.
[6]	韩俊樱, 张振宇, 孔德仕. 移动群智感知中面向用户区域的分布式多任务分配方法[J]. 计算机应用, 2020, 40(2): 358-362.
[7]	高彦彦, 李莉, 张晶, 贾英茜. 结合梯度投影稀疏重构和复数小波的图像重构[J]. 计算机应用, 2020, 40(2): 486-490.
[8]	金鑫, 王涛春, 吕成梅, 王成田, 陈付龙, 赵传信. 移动群智感知中原始数据隐私保护算法[J]. 计算机应用, 2020, 40(11): 3249-3254.
[9]	宗春梅, 张月琴, 曹建芳, 赵青杉. 基于深度先验及非局部相似性的压缩感知核磁共振成像[J]. 计算机应用, 2020, 40(10): 3054-3059.
[10]	杨正清, 周朝荣, 袁姝. 移动群智感知系统中基于离散布谷鸟搜索算法的任务分配[J]. 计算机应用, 2019, 39(9): 2778-2783.
[11]	陈秀华, 刘慧, 熊金波, 马蓉. 移动群智感知中面向任务需求的用户选择激励机制[J]. 计算机应用, 2019, 39(8): 2310-2317.
[12]	杜小磊, 陈志刚, 张楠, 许旭. 基于压缩感知和深度小波网络的列车故障识别[J]. 计算机应用, 2019, 39(7): 2175-2180.
[13]	刘晓晖, 路利军, 冯前进, 陈武凡. 基于Moreau-包络的近似平滑迭代磁共振图像重建算法[J]. 计算机应用, 2018, 38(7): 2076-2082.
[14]	乔建华, 张雪英. 基于均衡分簇的无线传感器网络压缩数据收集[J]. 计算机应用, 2018, 38(6): 1691-1697.
[15]	金凤, 唐宏, 张进彦, 尹礼欣. 基于压缩感知的大规模MIMO系统导频优化及信道估计算法[J]. 计算机应用, 2018, 38(5): 1447-1452.