Graduate Exam Abstract

Dulanjalie Dhanapala

M.S. Final
July 10, 2009, 2.00 pm
Engineering E103
On Performance of Random Routing and Virtual Coordinate Based Routing in Wireless Sensor Networks

Abstract: Wireless Sensor Networks (WSNs) are large deployments of smart sensor devices, which are constrained by energy, memory and computational power, to monitor environmental or physical phenomena. Hence, they require suitable routing protocols that manage the information flow in an energy-efficient manner. Routing protocols can be divided primarily into two categories: address based and content based. The main focus of this thesis is on random routing and virtual coordinate based routing, where the former is a content based scheme while the latter is address based scheme. Random routing protocols, by which packets are forwarded to randomly selected neighbors, are mostly used in unstructured wireless sensor networks as querying or discovery methods. These packets are agents carrying information about events or queries seeking such information. Properties such as locality, simplicity, low-overhead, load balancing property and robustness of random routing are important attributes for routing in sensor networks. We propose a novel mathematical framework to derive the exact probability of a packet visiting a given node within any h-hops as well as the rendezvous probability of agents and queries within h-hops at a given node(s) in 2-D grid-based WSNs. It is then extended to a 3-D grid. Exact probabilities of agent meeting query is derived for a network without physical boundaries under different packet forwarding in lossy and lossless networks. Later the analysis is extended for a network with rectangular boundaries. The models are validated using Monte Carlo simulations. The utility of the model is demonstrated by determining the protocol parameters to optimize the performance of rumor routing protocol under fixed energy budget constraint. The exact solution presented, unlike existing models relying on asymptotic behavior, is applicable to small and medium-scale networks. Simulation results indicate that the model is a good approximation even for sparse arrays with 75 % node density. The model can be used to set parameters and optimize the performance of several classes of random routing protocols. Virtual Coordinate based Routing (VCR) is a class of simple scalable routing schemes for sensor networks. VCR does not rely on availability of geographical node location information but provide satisfactory performance compared to geographical routing. Multiple nodes with identical coordinates as well as the local minima encountered during routing, degrade the performance of VCR. Properties of virtual coordinate systems are analyzed to provide insight into the nature of virtual coordinate space. Bounds are derived for shortest path lengths between two nodes in coordinate space. Proper anchor placement that will provide unique coordinates to nodes and 100% greedy ratio in 1-D networks and 2-D grids are presented. A novel routing scheme, Convex Subspace Routing (CSR), is proposed. In contrast to existing VCR schemes that use backtracking or hill climbing techniques to overcome local minima, CSR avoids using anchors that cause local minima. CSR selects subsets of anchors dynamically to provide a convex distance function from source to destination. Consequently, it is less sensitive to anchor placement and over anchoring, and does not require tracking route history for backtracking. Performance of CSR is evaluated for different randomly deployed network configurations and performance is not sensitive whether anchors are placed at the boundary or anywhere in the network. Results for varying node densities and different numbers of anchors indicate that CSR significantly outperforms Logical Coordinate Routing (LCR), in terms of routability, number of hops used for routing, as well as energy consumption.

Adviser: Prof. Anura P. Jayasumana
Non-ECE Member: Prof. Indrakshi Ray (Computer Science)
Member 3: Prof. Edwin K. P. Chong (ECE)
Addional Members:


Program of Study: