北京邮电大学学报

  • EI核心期刊

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

• 论文 • 上一篇    下一篇

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

田兴鹏, 朱晓荣, 朱洪波   

  1. 南京邮电大学 通信与信息工程学院, 南京 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   

  1. College of Telecommunications&Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China
  • Received:2020-07-23 Published:2020-11-30

摘要: 单个节点无法满足各种新颖的应用程序对时延或能耗的要求,为此提出了一种分布式无线节点任务协同分配方法,通过利用周围节点的空闲资源,来降低所有节点处理任务的总时延或总能耗.首先根据层次分析法(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

中图分类号: