Routing and broadcasting over sensor networks

Advances in micro-embedded computing systems, coupled with developments in wireless technology have enabled the deployment of large scale wireless and sensor networks for many important applications. These networks are characterized by local geographic connectivity among nodes and by very little computational and storage capabilities at each node. Moreover, data transfer is mainly through packet forwarding by intermediary nodes. Due to the nature of their connectivity, nodes may have extremely limited information about their network, possibly only of their one-hop neighbors. In such a scenario where the nodes may have limited/erroneous network state information, we study the two basic network primitives: (i) point-to-point routing and (ii) broadcasting. First, we study the problem of point-to-point routing in a network of nodes where each node has a corresponding destination to send/receive data. We consider geographic routing (routing based on the position of the nodes), as this routing scheme is scalable and of low complexity and well suited to operate over sensor networks. We study the effect of imperfect routing information on the path lengths of the individual routes. We provide error models for the routing errors and demonstrate routing strategies that achieve order-wise optimal delays even when only a small fraction of the nodes have any (possibly imperfect) geographic information. We characterize the throughput capacity of the network and show that for a class of progressive routing strategies with limited routing data, the throughput capacity is order-wise optimal. While much of the current research focuses on greedy routing in uniform sensor networks, we study routing in imperfect (anisotropic) networks where greedy geographic forwarding fails due to holes (nodes without any neighbors that are closer to the destination). We develop routing strategies in such networks that operate with geographic location at the nodes to achieve order-wise optimal delays while maximizing the network throughput capacity. These algorithms inherit the beneficial properties of geographic routing algorithms such as scalability and low complexity while providing near-optimal throughput and delay in a robust manner. We also study routing strategies in networks where the traffic demand may be non-uniform. Routing schemes such as geographic routing that minimize some metric of routing distance cause local points of congestion as they do not consider the traffic demands across different parts of the network and may concentrate traffic along some paths that lie across regions of higher demand. We design randomized routing schemes based on geographic routing that are shown to be able to support any traffic demand that is achievable (i.e. achievable by any other scheme). Second, we study the issue of broadcasting in networks with limited local information. We analyze broadcast schemes where nodes have little geographic information or state information (memory of transmitted packets). We demonstrate randomized broadcast algorithms that utilize the limited information and perform broadcasting with minimal transmission overheads. Further, we also study branching random walks in R[superscript d], in the context of broadcasting a message over a spatial network to understand the asymptotic distribution of the broadcast. We derive analytic results on the density of these branching processes