Potential-Based Routing In Wireless Sensor Networks

Abstract

Recent advances in VLSI technology, and wireless communication have enabled the development of tiny, low-cost sensor nodes that communicate over short distances. These sensor nodes, which consist of sensing, data processing, and wireless communication capabilities, suggest the idea of sensor networks based on collaborative effort of a large number of sensor nodes. Sensor networks hold the promise for numerous applications such as intrusion detection, weather monitoring, security and tactical surveillance, distributed computing, and disaster management. Several new protocols and algorithms have been proposed in the recent past in order to realize these applications. In this thesis, we consider the problem of routing in Wireless Sensor Networks (WSNs). Routing is a challenging problem in WSNs due to the inherent characteristics which distinguish these networks from the others. Several routing algorithms have been proposed for WSNs, each considering a specific network performance objective such as long network lifetime (ChangandTassiulas,2004), end-to-end delay guarantees (T.Heetal,2003), and data fusion (RazvanCristescuetal,2005) etc. In this thesis, we utilize the Potential-based Routing Paradigm to develop routing algorithms for different performance objectives of interest in WSNs. The basic idea behind the proposed approach is to assign a scalar called the potential to every sensor node in the network. Data is then forwarded to the neighbor with highest potential. Potentials cause the data to flow along certain paths. By defining potential fields appropriately, one can cause data to flow along preferred paths, so that the given performance objective is achieved. We have demonstrated the usefulness of this approach by considering three performance objectives, and defining potentials appropriately in each case. The performance objectives that we have considered are (i) maximizing the time to network partition, (ii) maximizing the packet delivery ratio, and (iii) Data fusion. In an operational sensor network, sensor nodes’ energy levels gradually deplete, leading eventually to network partition. A natural objective is to route packets in such a way that the time to network partition is maximized. We have developed a potential function for this objective. We analyzed simple network cases and used the insight to develop a potential function applicable to any network. Simulation results showed that considerable improvements in time to network partition can be obtained compared to popular approaches such as maximum lifetime routing, and shortest hop count routing. In the next step, we designed a potential function that leads to routes with high packet delivery ratios. We proposed a “channel-state aware” potential definition for a simple 2-relay network and performed a Markov-chain based analysis to obtain the packet delivery ratio. Considerable improvement was observed compared to a channel-state-oblivious policy. This motivated us to define a channel-state-dependent potential function for a general network. Simulation results showed that for a relatively slowly changing wireless network, our approach can provide up to 20% better performance than the commonly-used shortest-hop-count routing. Finally, we considered the problem of correlated data gathering in sensor networks. The routing approach followed in literature is to construct a spanning tree rooted at the sink. Every node in the tree aggregates its data with the data from its children in order to reduce the number of transmitted bits. Due to this fact, the total energy cost of the data collection task is a function of the underlying tree structure. Noting that potential based routing schemes also result in a tree structure, we present a potential definition that results in the minimum energy cost tree under some special conditions. Specifically, we consider a scenario in which sensor nodes’ measurements are quantized to K values. The task at the sink is to construct a histogram of measurements of all sensor nodes. Sensor nodes do not directly send their measurements to sink. Instead, they construct a temporary histogram using the data from its children and forward it to its parent node in the tree. We present a potential definition that results in the minimum energy cost tree under some conditions on sensor nodes’ measurements. We include both the transmission energy cost as well as the energy cost associated with the aggregation process.