基于动态规划的矿井无线再编程最优基站选址算法

摘要

The nodes of large-scale wireless network which widely used in safety-critical systems often update new code,the way of wireless reprogramming is efficiency and flexibility.The problem of selecting the optimal base station when nodes uniformly distributed in mine wireless network environment and all other nodes were reprogrammed efficiency.Firstly,the model of base station selecting was established by covering process of reprogramming.Then the problem was transformed into solving the minimum of longest non-cyclic path between node and base station in undirected circulant graph.Finally,the optimal algorithm based on dynamic programming which included optimal substructure and overlapping subproblems was proposed.Numerical analysis and experimental results show that the time consumption of proposed algorithm is more stable than other optimal algorithm when the complexity of network is increased sharply.%广泛应用于安全关键系统的大规模无线网络需动态更新节点程序,采用无线再编程方式进行程序更新,具有高效性及灵活性.研究在节点均匀分布的矿井无线传感器网络环境下,如何选取最优的基站使整个网络再编程代价最小.首先由网络节点程序更新的接力覆盖过程推导出基站选址模型,其次将其转化为求解连通简单图任意节点不循环最长最短通路的最小值问题,最后给出基于动态规划的最优算法,包括最优子结构和重叠子问题.数值结果表明,与其他最优算法相比,该算法在网络复杂度急剧增大时仍保持平稳的时间消耗.