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.