基于遗传优化的WSNs多源单汇路由算法

GA-based algorithms for multiple sources to one sink routing in WSNs

针对无线传感器网络中的多源单汇路由问题,综合考虑无线传感器网络中链路带宽、延迟和路径节点最小剩余能量三种度量,建立了多源单汇路由问题的系统模型,将其转化为求解多约束最小Steiner树问题,已知该问题是NP难的问题,给出了基于遗传优化的求解算法,采用基于备选路径集的整数序列编码表示一棵生成树,设计相应的交叉和变异算子,以及对非法染色体进行修复的机制,最后在遗传算法的计算过程中选择合理的适应度函数,找到一棵满足多约束的能耗趋于最小且状态稳定Steiner树。理论分析和数值试验结果表明所提出的遗传求解算法收敛速度快、可靠性高,为无线传感器网络中的多源单汇路由提供了一种新的有效途径。

In order to solve the least energy-consumption multiple sources to one sink routing problem in wireless sensor networks with bandwidth and delay constraints, a system model for multiple sources to one sink routing problem is presented by transforming the problem to a Steiner tree problem, which has been proven to be a NP-complete problem. A GA-based algorithm is employed to solve this NP-complete problem. The algorithm adopts an integral serial coding scheme based on the preparative paths set to represent a tree structure. Relevant crossover and mutation operators and reparation operator for illegal chromosomes are given. Finally, during the processing of the genetic algorithm, with a reasonable fitness function, a Steiner tree at the near least energy-consumption and most stable state with the delay and bandwidth constraints could be obtained. Both theoretical analysis and simulation results demonstrate the proposed algorithm has fast convergence speed and high reliability, and provides an available new way to cope with multiple sources to one sink routing problem in WSNs.