一种基于动态规划的最小化最大加权响应时间的中心控制节点选举算法  

Central node selection algorithm of minimizing maximum weighted response time based on dynamic programming

作　　者：万柏麟 杨奇[1] 闫中江[1] 杨懋[1] 李波[1] WAN Bailin;YANG Qi;YAN Zhongjiang;YANG Mao;LI Bo(School of Electronics and Information,Northwestern Polytechnical University,Xi′an 710072,China)

机构地区：[1]西北工业大学电子信息学院,陕西西安710072

出　　处：《西北工业大学学报》2023年第1期73-80,共8页Journal of Northwestern Polytechnical University

基　　金：国家自然科学基金(61771392,61871322,61771390);航空科学基金(201955053002,201855533035)资助。

摘　　要：为了最小化网络中任意节点到达中心控制节点的最大加权响应时间,提出了一种基于动态规划的中心控制节点选举算法。无线网络中的节点和链路的响应时间被建模为网络拓扑图中的节点权值和边权值,进而最小化网络中任意节点到达中心控制节点的最大加权响应时间的中心控制节点选举问题被建模为K-中心问题,其中K表示中心控制节点的个数。采用基于动态规划的插点法可求出任意2个点之间的最小加权响应时间,所建模的K-中心问题被转化为若干个R-控制集问题。将若干个R-控制集问题转化为若干个0-1整数规划问题,采用分支定界的方法逐个求解每个整数规划问题。给出了K=1时上述算法的简化实现方法,证明了所提算法的最优性并分析了算法的复杂度。仿真结果表明,所提算法选举的中心控制算法可最小化网络最大加权响应时间。In order to minimize the maximum weighted response time for any node in the network to reach the central control node,a central control node election algorithm based on dynamic programming is proposed.Firstly,the response times of nodes and links in the wireless network are modeled as the node weights and edge weights in the network topology,and then the central control node election problem that minimizes the maximum weighted response time for any node in the network to reach the central control node is modeled as the central problem,where represents the number of central control nodes.Then,by using the interpolation method based on dynamic programming,the weighted response time between the two points can be obtained,and the K-central problem modeled is transformed into several R-control set problems.Then,several control R-set problems are transformed into several 0-1 integer programming problems,and each integer programming problem can be solved one by one by using the branch and bound method.Finally,a simplified implementation method based on the above algorithm is given when K=1,the optimality of the proposed algorithm is proved and the complexity of the algorithm is analyzed.Simulation results show that the proposed central control algorithm can minimize the maximum weighted response time of the network.

关 键 词：无线网络 中心节点选举 动态规划 

分 类 号：TN92[电子电信—通信与信息系统]