基于KM算法的分布式无线节点任务分配方法

doi:10.13190/j.jbupt.2020-089

北京邮电大学学报 ›› 2020, Vol. 43 ›› Issue (6): 96-102.doi: 10.13190/j.jbupt.2020-089

基于KM算法的分布式无线节点任务分配方法

田兴鹏, 朱晓荣, 朱洪波

南京邮电大学通信与信息工程学院, 南京 210003

收稿日期:2020-07-23 发布日期:2020-11-30
通讯作者: 朱晓荣(1977-),女,教授,博士生导师,E-mail:xrzhu@njupt.edu.cn. E-mail:xrzhu@njupt.edu.cn
作者简介:田兴鹏(1995-),男,硕士生.
基金资助:
国家自然科学基金项目（61871237）；江苏省高校"青蓝工程"和江苏省重点研发计划项目（BE2019017）

Distributed Wireless Node Task Allocation Method Based on KM Algorithm

TIAN Xing-peng, ZHU Xiao-rong, ZHU Hong-bo

College of Telecommunications&Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China

Received:2020-07-23 Published:2020-11-30

摘要/Abstract

摘要： 单个节点无法满足各种新颖的应用程序对时延或能耗的要求，为此提出了一种分布式无线节点任务协同分配方法，通过利用周围节点的空闲资源，来降低所有节点处理任务的总时延或总能耗.首先根据层次分析法（AHP）综合任务的多维属性，如计算负载、最晚完成时间等，确定任务执行的优先级；然后建立时延和能耗的优化模型，并将其转化为二分图最大权值的匹配问题，采用Kuhn Munkras （KM）算法求解得到任务分配的最优解，实现终端节点在网络边缘高效地协同执行任务.仿真结果表明，该算法能够有效地降低任务处理的时延和能耗.

关键词: 任务分配, 异构网络, 层次分析法, KM算法

Abstract: Aiming at the fact that a single node cannot meet the delay or energy consumption requirements of various novel applications,a distributed wireless node task collaborative allocation method is proposed to reduce the total delay or total energy consumption of all node processing tasks by utilizing the idle resources of surrounding nodes. Firstly, according to the analytic hierarchy process (AHP),the priority of task execution is determined according to the multi-dimensional attributes of tasks, such as calculation load and latest completion time. Then, the optimization model of time delay and energy consumption is established, which is transformed into the problem of maximum weight matching of bipartite graph. The optimal solution of task allocation is obtained by using Kuhn Munkras(KM)algorithm, which realizes the efficient cooperation of terminal nodes at the edge of network. The simulation results show that the algorithm can effectively reduce the time delay and energy consumption of task processing.

Key words: task assignment, heterogeneous network, analytic hierarchy process, Kuhn Munkras algorithm

中图分类号:

TP393

田兴鹏, 朱晓荣, 朱洪波. 基于KM算法的分布式无线节点任务分配方法[J]. 北京邮电大学学报, 2020, 43(6): 96-102.

TIAN Xing-peng, ZHU Xiao-rong, ZHU Hong-bo. Distributed Wireless Node Task Allocation Method Based on KM Algorithm[J]. Journal of Beijing University of Posts and Telecommunications, 2020, 43(6): 96-102.

参考文献

[1] Satyanarayanan M, Chen Zhuo, Ha K, et al. Cloudlets:at the leading edge of mobile-cloud convergence[C]//International Conference on Mobile Computing. Austin:[s.n.], 2014:1-9.
[2] 董思岐, 李海龙, 屈毓锛, 等. 移动边缘计算中的计算卸载策略研究综述[J]. 计算机科学, 2019, 46(11):32-40. Dong Siqi, Li Hailong, Qu Yuben, et al. Survey of research on computation unloading strategy in mobile edge computing[J]. Computer Science, 2019, 46(11):32-40.
[3] Swan M. Sensor mania! the internet of things, wearable computing, objective metrics, and the quantified self 2.0[J]. Journal of Sensor & Actuator Networks, 2012, 1(3):217-253.
[4] Funai C, Tapparello C, Heinzelman W. Mobile to mobile computational offloading in multi-hop cooperative networks[C]//2016 IEEE Global Communications Conference. Washington, DC:IEEE, 2016:1-7.
[5] Funai C, Tapparello C, Heinzelman W. Computational offloading for energy constrained devices in multi-hop cooperativse networks[J]. IEEE Transactions on Mobile Computing, 2020, 18(1):60-73.
[6] Chen Xu, Pu Lingjun, Gao Lin, et al. Exploiting massive D2D collaboration for energy-efficient mobile edge computing[J]. IEEE Wireless Communications, 2017, 24(4):64-71.
[7] Fan Wenhao, Tang Bihua, Liu Yuanan. Application multi-partitioning for offloading computation to multiple computing resources around mobile terminals [J]. International Journal of Grid and Distributed Computing, 2016, 9(6):83-92.
[8] Wang Feng, Han Guangjie, Jiang Jinfang, et al. A task allocation algorithm based on score incentive mechanism for wireless sensor networks[J]. International Journal of Distributed Sensor Networks, 2015(5):5-17.
[9] Yin Xiang, Zhang Kaiquan, Li Bin, et al. A task allocation strategy for complex applications in heterogeneous cluster-based wireless sensor networks[J]. International Journal of Distributed Sensor Networks, 2018, 14(8):1-15.
[10] Pu Lingjun, Chen Xu, Mao Guoqiang, et al. An energy-efficient and deadline-aware hybrid edge computing framework for vehicular crowdsensing applications[J]. IEEE Internet of Things Journal, 2019, 6(1):84-99.
[11] Sahni Y, Cao Jiannong, Zhang Shigeng, et al. Edge Mesh:a new paradigm to enable distributed intelligence in internet of things[J]. IEEE Access, 2017, 5:16441-16458.
[12] Yang Jun, Zhang Hesheng, Ling Yun, et al. Task allocation for wireless sensor network using modified binary particle swarm optimization[J]. IEEE Sensors Journal, 2014, 14(3):882-892.
[13] Li Junjie. Analyzing key factors in taiwanese teachers teaching in China's mainland with analytic hierarchy process[J]. Journal of Interdiplinary Mathematics, 2018, 21(2):307-316.
[14] Bruff D. The assignment problem and the Hungarian method[J]. Notes for Math, 2005, 20(5):29-47.

[1]	张雨晴, 李云, 黄鸿锐, 庄宏成. 异构网络中任务卸载与资源分配联合优化算法[J]. 北京邮电大学学报, 2022, 45(2): 91-97.
[2]	潘子宇, 杨洁. 超密度异构蜂窝网络能效优化[J]. 北京邮电大学学报, 2021, 44(1): 20-25,58.
[3]	周平, 王泽胜, 殷波, 郭少勇. 基于层次分析法的云服务可用性评价方法[J]. 北京邮电大学学报, 2021, 44(1): 79-85.
[4]	马彬, 毛步绚, 谢显中. 自组织异构网络中降低阻塞的垂直切换算法[J]. 北京邮电大学学报, 2019, 42(2): 19-24.
[5]	陈昕, 温向明, 王鲁晗, 路兆铭. 5G中多接入边缘计算的联合部署架构设计[J]. 北京邮电大学学报, 2018, 41(5): 86-91,97.
[6]	安健, 桂小林, 何昌其, 吴若飚. 群智感知中基于层次分析法的众包机制[J]. 北京邮电大学学报, 2015, 38(5): 37-41.
[7]	姜海鸥, 宋美娜, 鄂海红, 邓江东. 运营支撑系统混合云迁移策略制定方法[J]. 北京邮电大学学报, 2014, 37(5): 1-5.
[8]	张鹤立, 纪红, 王永斌. 自组织异构网络中的资源优化配置[J]. 北京邮电大学学报, 2014, 37(2): 5-8,47.
[9]	王继红, 石文孝, 许银龙, 迟学芬. 延时拒绝模型下的异构无线网络接入选择[J]. 北京邮电大学学报, 2014, 37(1): 103-106.
[10]	葛海慧, 郑世慧, 陈天平, 杨义先. 信息安全威胁场景模糊风险评估方法[J]. 北京邮电大学学报, 2013, 36(6): 89-92,107.
[11]	张月莹, 王文博, 龙航, 刘飞, 郑侃. 面向用户体验的异构网络资源分配[J]. 北京邮电大学学报, 2012, 35(6): 116-120.
[12]	郑康锋1,2 ；王秀娟3 ；郭世泽2 ；杨义先1. 用户评价的信息系统服务质量评估模型[J]. 北京邮电大学学报, 2010, 33(1): 84-88.
[13]	吕镇邦;周　波. 基于Shapley熵和Choquet积分的层次化风险评估[J]. 北京邮电大学学报, 2009, 32(6): 83-87.
[14]	苏放甄雁翔景晓军. 模糊综合评判的融合网络2种丢包原因区分[J]. 北京邮电大学学报, 2009, 32(3): 60-64.
[15]	苏放范英磊. 基于Fuzzy模式识别的异构网络端到端丢包评判算法[J]. 北京邮电大学学报, 2007, 29(s1): 52-56.

基于KM算法的分布式无线节点任务分配方法

Distributed Wireless Node Task Allocation Method Based on KM Algorithm

RichHTML

PDF

PDF (Mobile)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价