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

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