In Mobile Ad Hoc NETworks (MANETs) autonomous nodes act both as traffic originators and forwarders to form a multi-hop network. Out-of-range nodes are reachable through a process called routing, which is a challenging task due to the constraints of bandwidth and battery power. Stateless location-based routing schemes have been proposed to avoid complex route discovery and maintenance, whereby nodes make routing decisions based solely on the knowledge of their location, the location of their neighbors, and the location of the destination. Natural routing schemes based on these prerequisites suffer from problems like local maxima or loops. We mitigate those problems by proposing randomized routing algorithms, which outperform others in terms of the packet delivery ratio and throughput. The prerequisite for location-based routing is knowing the location of a node. Location information is more widely useful anyway for location-aware applications like security, health care, robotics, navigation etc. Locating a node indoors remains a challenging problem due to the unavailability of GPS signals under the roof. For this goal we choose the RSS (Received Signal Strength) as the relevant attribute of the signal due to its minimal requirements on the RF technology of the requisite modules. Then profiling based localization is considered that does not rely on any channel model (range-based) or the connectivity information (range-free), but rather exploits the context of a node to infer that information into the estimation. We propose a RSS profiling based indoor localization system, dubbed LEMON, based on low-cost low-power wireless devices that offers better accuracy than other RSS-based schemes. We then propose a simple RSS scaling trick to further improve the accuracy of LEMON. Furthermore, we study the effect of the node orientation, the number and the arrangement of the infrastructure nodes and the profiled samples, leading us to further insights about what can be effective node placement and profiling. We also consider alternate formulations of the localization problem, as a Bayesian network model as well as formulated in a combinatorial fashion. Then performance of different localization methods is compared and again LEMON ensures better accuracy. An effective room localization algorithm is developed, and both single and multiple channels are used to test its performance. Furthermore, a set of two-step localization algorithms is designed to make the LEMON robust in the presence of noisy RSS and faulty device behavior.

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 unified routing framework has ever increased. In this dissertation, we address these main weaknesses in the research on location- based routing. We first 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 significantly reduced communication overhead. We then present our location-based multicast routing protocol that finds 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 unified routing framework that seamlessly integrates proposed unicast, multicast, and convergecast routing protocols. Specifically, we discuss the issues regarding the implementation of our routing protocols on real hardware, and the design of the framework that significantly reduces the code and memory size to fit 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.

No description available.

No description available.

Wireless Sensor Networks (WSNs) continue to evolve as new applications emerge. In the recent past, WSNs were mostly single sink networks with a few number of homogeneous and static sensor nodes. Now, several applications require networks with multiple and moving sinks and targets as well as thousands of heterogeneous devices. However, the same constraints remain: sensor nodes continue to be very limited in resources, posing new challenges in the design of scalable and energy-efficient algorithms and communication protocols to support these new applications. This dissertation first addresses the problem of sink localization in large scale WSNs. A scalable and energy-efficient sink localization mechanism, called the Anchor Location Service (ALS), is introduced to support the use of location-based routing protocols. ALS avoids frequent and costly flooding procedures derived from the mobility of the sinks and targets, and utilizes face routing to guarantee the success of localization. The problem of topology control in heterogeneous environments is addressed next. A new topology control mechanism, the Residual Energy-Aware Dynamic (READ) algorithm, is devised to extend the lifetime of the network while maintaining connectivity. READ extends the lifetime of the network by assigning a more prominent role to more powerful devices. ALS and READ are evaluated and compared with other well-known protocols using analytical means and simulations. Results show that ALS provides a scalable sink location service and reduces the communication overhead in scenarios with multiple and moving sinks and targets. Results also show that READ increases both the network lifetime and the packet delivery rate.

No description available.