As wireless sensor networks continue to grow in size, we are faced with the prospect of emerging wireless networks with hundreds or thousands of nodes. While earlier generations of such networks employed routing protocols that did not require a point-to-point routing primitive, geographic routing algorithms have recently been proposed as a new routing primitive for data-centric storage and for running more complex queries over such networks. We can expect an increasing demand for point-to-point routing in sensor networks in the future as data-centric applications and networks containing actuators become more common.

Although geographic routing algorithms have been available for several years, there are few known deployments of such algorithms in practice. To our knowledge, there are two main obstacles that stand in the way of deployment:

1. Practical Difficulties and Costs associated with Distributed Planarization; and

2. Unavailability of Location Information. 

We recently developed two new algorithms that are specifically designed to address these difficulties: Greedy Distributed Spanning Tree Routing (GDSTR) and Greedy Embedding Spring Coordinates (GSpring). GDSTR addresses the first problem by avoiding planarization and the issues associated with errors in localization, while GSpring is able to derive Euclidean coordinates that are optimized for geographic routing under conditions where obstacles are common and for sparse networks.

With GDSTR and GSpring, we believe that geographic routing is now truly practical in real (static) wireless networks. These algorithms with evaluated and compared to previous geographic routing algorithms in simulation. In this project, we plan to implement and deploy these geographic routing algorithms and compare them with traditional ad hoc routing algorithms like DSR, DSDV and AODV in a practical setting. While in theory, our geographic routing algorithms should be better, there are two main concerns which makes this an open question:

1. Relative costs of maintaining routing state. DSR, DSDV and AODV do not require much pre-computation while we need to first compute virtual coordinates before deploying a geographic routing algorithm. Also, when there is network churn, there is a need to maintain/repair the routing state for geographic routing algorithms. The relative costs between geographic routing algorithms when compared to traditional ad hoc routing algorithms is currently unclear.

2. Wireless model. In existing work on geographic routing, the simplifying assumption is made that two nodes are either able to communicate or they are not. In real radio networks, this assumption does not hope. The connectivity between nodes are often time-varying. This may have a significant effect on routing efficiency for geographic routing algorithms.

We hope to understand the relative tradeoffs between geographic routing algorithms and ad hoc routing algorithms like DSR, DSDV and AODV in the course of this project.
 

In addition, we also plan to investigate the following problems in this project:

• Geocast

• Load Balancing/Power-aware Geographic Routing

• Multi-path/Multi-homing Routing

• Geographic Routing for Mobile Nodes

• Geographic Routing for Heterogeneous Networks

• Multi-Dimensional Geographic Routing

• Application of Network Coding to Wireless Networks

$Date: 2008/01/01 06:35:12 $