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

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.

Keywords

• 无线网络
• 中心节点选举
• 动态规划