Challenges and Solutions for Location-based Routing in Wireless Sensor Networks with Complex Network Topology

Complex Network Topologies (CNTs)?network holes and cuts?often occur in practical WSN deployments. Many researchers have acknowledged that CNTs adversely affect the performance of location-based routing and proposed various CNT- aware location-based routing protocols. However, although they aim to address practical issues caused by CNTs, many proposed protocols are either based on idealistic assumptions, require too much resources, or have poor performance. Additionally, proposed protocols are designed only for a single routing primitive?either unicast, multicast, or convergecast. However, as recent WSN applications require diverse traffic patterns, the need for an uni?ed routing framework has ever increased.

In this dissertation, we address these main weaknesses in the research on location- based routing. We ?rst propose efficient algorithms for detecting and abstracting CNTs in the network. Using these algorithms, we present our CNT-aware location- based unicast routing protocol that achieves the guaranteed small path stretch with signi?cantly reduced communication overhead. We then present our location-based multicast routing protocol that ?nds near optimal routing paths from a source node to multicast member nodes, with efficient mechanisms for controllable packet header size and energy-efficient recovery from packet losses. Our CNT-aware convergecast routing protocol improves the network lifetime by identifying network regions with concentrated network traffic and distributing the traffic by using the novel concept of virtual boundaries. Finally, we present the design and implementation details of our uni?ed routing framework that seamlessly integrates proposed unicast, multicast, and convergecast routing protocols. Speci?cally, we discuss the issues regarding the implementation of our routing protocols on real hardware, and the design of the framework that signi?cantly reduces the code and memory size to ?t in a resource constrained sensor mote. We conclude with a proactive solution designed to cope with CNTs, where mobile nodes are used for ?patching? CNTs to restore the network connectivity and to optimize the network performance.