基于动态规划的无线传感器网络的路由算法

路由问题是无线传感器网络中的核心问题之一,其数据传送的多跳特点使得非常适合用动态规划的原理来设计传感器网络的路由算法.基于动态规划,通过节点跳数生成算法为传感器网络中的每个节点赋一个表示到Sink点跳数的节点跳数值,并分析了传感器网络的拓扑结构特点,然后给出了无线传感器网络中寻找从源到汇满足不同设计目标的最小跳数(MinH)、最小跳数最大剩余能量(MinHMaxRE)和最小跳数最小费用(MinHMinC)3种路由算法.探讨了最小跳数最小费用路由与最小费用路由之间的关系,并给出了判断最小跳数最小费用路径就是最小费用路径的一个充要条件.算法的能量消耗分析表明,所给路由算法能实现大幅度的能量节省.

Routing Algorithms of the Wireless Sensor Network Based on Dynamic Programming

Routing problem is one of the most important issues to the wireless sensor network. In sensor network, data is transmitted from source to sink node in a multi-hop mode, so dynamic programming principle lends itself well to design routing algorithms of sensor network. Based on dynamic programming, a hop value of each node that indicates the hop number needed to communicate with the sink is generated by a node hop number generation algorithm. As the topology of the sensor network is concerned, the difference between the hop values of each node and its neighbor is no more than 2. Then three algorithms, that is minimal hop routing, minimal hop with maximal residual energy routing and minimal hop with minimal cost routing algorithms, are presented in this paper, which can pick up the paths that meet different design target between the sink and the source node in wireless sensor network effectively. The relationship between minimal hop with minimal cost routing and minimal cost routing is studied. A necessary and sufficient condition that minimal hop with minimal cost routing is also minimal cost routing are given. Energy consumption analysis shows that the routing algorithms proposed can be energy saving to a great degree.