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

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

School of Electronics and Information, Northwestern Polytechnical University, Xi'an 710072, China

Received: 19 May 2022

Abstract

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.

摘要

为了最小化网络中任意节点到达中心控制节点的最大加权响应时间, 提出了一种基于动态规划的中心控制节点选举算法。无线网络中的节点和链路的响应时间被建模为网络拓扑图中的节点权值和边权值, 进而最小化网络中任意节点到达中心控制节点的最大加权响应时间的中心控制节点选举问题被建模为K-中心问题, 其中K表示中心控制节点的个数。采用基于动态规划的插点法可求出任意2个点之间的最小加权响应时间, 所建模的K-中心问题被转化为若干个R-控制集问题。将若干个R-控制集问题转化为若干个0-1整数规划问题, 采用分支定界的方法逐个求解每个整数规划问题。给出了K=1时上述算法的简化实现方法, 证明了所提算法的最优性并分析了算法的复杂度。仿真结果表明, 所提算法选举的中心控制算法可最小化网络最大加权响应时间。