基于李雅普诺夫优化的移动群智感知在线任务分配策略

doi:10.11896/jsjkx.221100179

计算机科学 ›› 2023, Vol. 50 ›› Issue (2): 50-56.doi: 10.11896/jsjkx.221100179

• 边缘智能协同技术及前沿应用 • 上一篇下一篇

基于李雅普诺夫优化的移动群智感知在线任务分配策略

常沙, 吴亚辉, 邓苏, 马武彬, 周浩浩

国防科技大学系统工程学院长沙 410005

收稿日期:2022-11-21 修回日期:2023-01-13 出版日期:2023-02-15 发布日期:2023-02-22
通讯作者: 吴亚辉(wuyahui@nudt.edu.cn)
作者简介:(changsha18@nudt.edu.cn)
基金资助:
国家自然科学基金(61871388)

Online Task Allocation Strategy Based on Lyapunov Optimization in Mobile Crowdsensing

CHANG Sha, WU Yahui, DENG Su, MA Wubin, ZHOU Haohao

College of Systems Engineering,National University of Defense Technology,Changsha 410005,China

Received:2022-11-21 Revised:2023-01-13 Online:2023-02-15 Published:2023-02-22
Supported by:
National Natural Science Foundation of China(61871388)

摘要/Abstract

摘要： 移动群智感知技术基于众包思想,募集移动感知设备对周围环境进行感知,能够使得环境感知和信息收集更加灵活、方便、高效。任务分配方案的合理性直接影响到感知任务能否成功,因此制定合理的任务分配方案是移动群智感知相关研究中的热点和重点。目前,移动群智感知系统中的任务分配方法多是离线的,针对的是单一类型的任务,但是在实际中,在线的、多类型的任务分配更贴近实际。因此,文中针对多类型任务,将移动群智感知技术应用于军事末端感知中,结合移动群智感知技术在军事领域的应用特点,对移动群智感知中的任务分配方法进行了研究,提出了面向系统效益的在线任务分配策略。文中建立了长期的、动态的在线任务分配系统模型,并以系统效益为优化目标,基于李雅普诺夫优化理论对问题进行了求解,实现了任务准入策略和任务分配方案的长期在线动态控制。实验结果表明,所提出的在线任务分配算法是有效可行的,能够在线、合理地分配到达移动群智感知系统的任务,保证任务队列的稳定性,且可以通过调整参数值增加系统效益。

关键词: 移动群智感知, 系统效益, 李雅普诺夫优化, 任务队列稳定性

Abstract: Based on the idea of crowdsourcing,mobile crowdsensing(MCS) collects mobile sensing devices to sense the surroun-ding environment,which can make environment sensing and information collection more flexible,convenient and efficient.Whe-ther the task allocation strategy is reasonable or not directly affects the success of the sensing task.Therefore,formulating a reasonable task allocation strategy is a hotspot and focus in the research of MCS.At present,most of the task allocation methods in MCS systems are offline and targeted at single type tasks.However,in practice,online multi-type task allocation is more common.Therefore,this paper studies the task allocation method in MCS for multiple types of tasks,and proposes an online task allocation strategy oriented to system benefits combined with the characteristics of MCS technology in the military field.In this paper,a long-term,dynamic online task allocation system model is established,and the problem is solved based on Lyapunov optimization theory with the system benefit as the optimization goal,so that the online dynamic control of task admission strategy and task allocation scheme is realized.Experiment shows that the online task allocation algorithm proposed in this paper is effective and feasible.It can reasonably allocate the tasks arriving at the MCS system online,ensure the stability of the task queue,and increase the system utility by adjusting the parameter value.

Key words: Mobile crowdsensing, System utility, Lyapunov optimization, Stability of task queue

中图分类号:

TP393

常沙, 吴亚辉, 邓苏, 马武彬, 周浩浩. 基于李雅普诺夫优化的移动群智感知在线任务分配策略[J]. 计算机科学, 2023, 50(2): 50-56. https://doi.org/10.11896/jsjkx.221100179

CHANG Sha, WU Yahui, DENG Su, MA Wubin, ZHOU Haohao. Online Task Allocation Strategy Based on Lyapunov Optimization in Mobile Crowdsensing[J]. Computer Science, 2023, 50(2): 50-56. https://doi.org/10.11896/jsjkx.221100179

参考文献

[1]CUI L F,GUO Y H,SHAO P Z,et al.Enhancing situational awareness on the battlefield using spatio-temporal big data [J].National Defense Science & Technology,2021,42(2):127-132.
[2]CAPPONI A,FIANDRINO C,KANTARCI B,et al.A Survey on Mobile Crowdsensing Systems:Challenges,Solutions and Opportunities [J].IEEE Communications Surveys & Tutorials,2019,21(3):2419-2465.
[3]GANTI R K,FAN Y,LEI H.Mobile crowdsensing:currentstate and future challenges [J].IEEE Communications Magazine,2011,49(11):32-39.
[4]CHEN X,WANG L,LIU W,et al.On Present Situation of Mobile Edge Information Service Ability of the US Army [J].Electronics Optics & Control,2021,28(7):62-67.
[5]ZENG M Q,SHI K,CHEN J,et al.Research on Big Data Construction and Security of the U.S.Army [J].Communication Technology,2022,55(7):911-918.
[6]DUAN Y X,LIU C Y,WEI W F.Review of Key Technologies for Battlefield Situational Awareness [J].Fire Control & Command Control,2021,46(11):1-19.
[7]LIAO J H,WU Z W,LIU Y M,et al.Design and implementation of mobile crowdsensing platform [J].Journal of Zhejiang University,2020,54(10):1915-1922.
[8]CHEN Y Y,LV P,GUO D K,et al.A Survey on Task and Participant Matching in Mobile Crowd Sensing [J].Journal of Computer Science and Technology,2018,33(4):768-791.
[9]HU H,ZHANG Q,HU H Y,et al.Q-learning based sensingtask assignment algorithm for mobile crowd sensing system[J].Computer Integrated Manufacturing Systems,2018,24:1774-1783.
[10]RAY A,CHOWDHURY C,MALLICK S,et al.Designing Energy Efficient Strategies Using Markov Decision Process for Crowd-Sensing Applications [J].Mobile Networks and Applications,2020,25(11):932-942.
[11]XING Q,SUN X M,YUAN C M.Assignment mechanism for spatial tasks in mobile crowd sensing [J].Application Research of Computers,2020,37(3):868-871.
[12]LIU J X.Research on Task Assignment and Evaluation Method of Mobile Crowd Sensing for Quality Assurance[D].Harbin:Harbin University of Science and Technology,2021.
[13]LIU C H,ZHANG B,SU X,et al.Energy-Aware Participant Selection for Smartphone-Enabled Mobile Crowd Sensing [J].IEEE System Journal,2017,11(3):1435-1446.
[14]JIANG W J,LV S J,LIU Y H,et al.Task Distribution Method of Participatory Sensing Based on Urban Rail Transit [J].Journal of Electronics & Information Technology,2021,43(10):3035-3042.
[15]GUO H.Research on incentive mechanism and task assignment in mobile crowdsensing[D].Hefei:Hefei University of Techno-logy,2018.
[16]PENG S,GONG W,ZHANG B X,et al.AP-Assisted OnlineTask Assignment for Mobile Crowdsensing[C]//2019 IEEE Global Communications Conference.2019.
[17]HAN J Y,ZHANG Z Y,KONG D S.Distributed Multi-task Allocation Method for User Area in Mobile Crowd Sensing[J].Journal of Computer Applications,2020,40(2):358-362.
[18]GONG W,ZHANG B X,LI C.Location-Based Online Task Assignment and Path Planning for Mobile Crowdsensing[J].IEEE Transactions on Vehicular Technology,2018,68(2):1772-1783.
[19]NEELY J.Stochastic Network Optimization with Application to Communication and Queueing Systems [M].San Rafael,CA,USA:Morgan and Claypool Publishers,2010.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于李雅普诺夫优化的移动群智感知在线任务分配策略

Online Task Allocation Strategy Based on Lyapunov Optimization in Mobile Crowdsensing

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

Metrics

本文评价

推荐阅读 0

[1]	张翀宇, 陈彦明, 李炜. 边缘计算中面向数据流的实时任务调度算法 Task Offloading Online Algorithm for Data Stream Edge Computing 计算机科学, 2022, 49(7): 263-270. https://doi.org/10.11896/jsjkx.210300195
[2]	程文辉, 张乾元, 程梁华, 向朝参, 杨振东, 沈鑫, 张乃凡. 空地协同移动群智感知研究综述 Review of Mobile Air-Ground Crowdsensing 计算机科学, 2022, 49(11): 242-249. https://doi.org/10.11896/jsjkx.220400264
[3]	李建军, 汪校铃, 杨玉, 付佳. 基于CQPSO移动群智感知紧急任务分配方法研究 Emergency Task Assignment Method Based on CQPSO Mobile Crowd Sensing 计算机科学, 2020, 47(6A): 273-277. https://doi.org/10.11896/JsJkx.190700040
[4]	蔡威, 白光伟, 沈航, 成昭炜, 张慧丽. 移动群智感知中基于强化学习的双赢博弈 Reinforcement Learning Based Win-Win Game for Mobile Crowdsensing 计算机科学, 2020, 47(10): 41-47. https://doi.org/10.11896/jsjkx.200700070
[5]	翟书颖, 李茹, 李波, 郝少阳. 视觉群智感知应用综述 Survey on Applications of Visual Crowdsensing 计算机科学, 2019, 46(6A): 11-15.
[6]	李卓, 徐哲, 陈昕, 李淑琴. 面向移动群智感知的位置相关在线多任务分配算法 Location-related Online Multi-task Assignment Algorithm for Mobile Crowd Sensing 计算机科学, 2019, 46(6): 102-106. https://doi.org/10.11896/j.issn.1002-137X.2019.06.014
[7]	何欣,刘天须,丁爽,白琳. 混合群智感知中服务节点优化选择机制 Optimization Selection Mechanism for Service Nodes in Hybrid Crowd Sensing 计算机科学, 2017, 44(1): 113-116. https://doi.org/10.11896/j.issn.1002-137X.2017.01.022