Reliability-Based Routing Algorithms for Energy-Aware Communication in Wireless Sensor Networks

In this chapter, some novel routing algorithms and packet forwarding strategies are presented forWireless Sensor Networks (WSNs). The new algorithms provide energy balancing under reliability constraints, as opposed to traditional wireless routing protocols (e.g. PEDAP, Directed Diffusion and LEACH), which fail to provide guarantees for reliable communication while attempting to achieve energy balancing. As reliable packet transfer to the Base Station (BS) is instrumental in many applications when there are no redundancies in the observed signals collected by the sensors, these new protocols can be of better use in real systems targeting such applications. Reliability is defined in terms of keeping the packet loss ration under a predefined threshold. The novel contribution of this chapter lies in developing new routing and packet forwarding mechanisms which can achieve energy balancing and reliable communication in WSNs. In order to provide energy balancing under such reliability constraints, first a randomized packet forwarding mechanism is introduced termed as “random shortcut” protocol. The performance of the new protocol is optimized by using large deviation theory. Secondly, new routing algorithms are developed which can select optimal paths to the BS ensuring minimum energy consumption and guarantee a given level of reliability at the same time. In this case, the wireless sensor network is modeled as a random graph, where optimal routes are found by the means of combinatorial optimization. The new algorithm OERA (Overall Energy Reliability Algorithm) selects a path which minimizes the overall energy needed to transfer a packet to the BS subject to a predefined reliability constraint, while algorithm BERA (Bottleneck Energy Reliability Algorithm) selects path over which the remaining energy of the bottleneck node (the one having the smallest energy) is maximized under the same constraint. It will be proven that these algorithms can find the optimal path in polynomial time and can be implemented in a distributed manner. The performance of the new methods compared to the traditional ones is also demonstrated by extensive numerical analysis and simulations.