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

广泛应用于安全关键系统的大规模无线网络需动态更新节点程序,采用无线再编程方式进行程序更新,具有高效性及灵活性。研究在节点均匀分布的矿井无线传感器网络环境下,如何选取最优的基站使整个网络再编程代价最小。首先由网络节点程序更新的接力覆盖过程推导出基站选址模型,其次将其转化为求解连通简单图任意节点不循环最长最短通路的最小值问题,最后给出基于动态规划的最优算法,包括最优子结构和重叠子问题。数值结果表明,与其他最优算法相比,该算法在网络复杂度急剧增大时仍保持平稳的时间消耗。