Shortest Path in a Wireless Sensor Network with Multiple Sensor Failures
Abstract
This paper shows how a shortest path can be obtained in a wireless sensor network, between a source sensor and a destination sensor, in a hop-by-hop fashion, considering multiple sensor failures along the path of data transmission. A wireless sensor network consists of a number of sensors spread across a
geographical area; these sensors are distributed either randomly or systematically. Every sensor possesses the capability to communicate with other sensors, and each sensor possesses some level of intelligence to perform processing of the signals. Efficiency of a sensor network depends on the design of the network topology. The network must be continuously functional to perform the task; a major problem in wireless sensor networks is due to sensor failures. In order to remain functional in spite of sensor failures, it is required that an alternative shortest path is found to send and receive requests to fulfill the task. I addressed this problem by finding an alternative shortest path based on the hop count. I developed a web based application to simulate a network and find shortest paths in a network with multiple sensor failures. I performed an experimental analysis in finding the shortest path. When a source sensor has data to transmit to a destination sensor, it broadcasts a RREQ (Route Request) to its immediate neighbors. A route to the source is created at every sensor when a RREQ is received. If the receiving sensor has not received this RREQ before and if it is not the destination, then it broadcasts the RREQ to its immediate neighboring sensors. If the receiving sensor is the destination, it generates a RREP (Request Reply). The RREP is uni-cast to the source sensor in a hop-by-hop fashion and a shortest path is obtained. Broadcasting is stopped at the point where a destination sensor receives a RREQ and acknowledges by RREP. To obtain a new shortest path, one or more sensors in the previously obtained shortest path are failed and the algorithm continues from the point where it has broadcasted RREQ to the sensors in the network previously and a new shortest path is obtained.