Design of routing for scale-free and self-organizing mobile networks

In this dissertation we focus on scalable and resilient routing for multi hop mobile networks. The availability of small, affordable and high performance processors, sensors, storage elements and communication devices make autonomic mobile wireless networks that connect people to other people, services, devices and content, achievable in the near future. This scale-free and self-organizing networking infrastructure, the "Internet of Things", requires a new architecture. None of the existing or proposed design choices for routing protocols address the needs of the new architecture. The challenges are scalability for large networks, scarcity of bandwidth, frequent node and link failures due to mobility, QoS and security requirements for specific deployments. In our research we design routing protocols that have considerably lower control overhead and routing states than traditional protocols and hence are scale-free. All of the protocols we designed are resilient to node movements and link failures. The design choices have been made so that it is easy to deploy QoS solutions based on deployment requirements. Although designed for Mobile Ad Hoc Networks (MANETs), these protocols can be used as efficient routing protocols for the clean-slate architecture of the "Internet of Things".;Ordered Proactive Enclave-based Routing for Ad-hoc networks (OPERA), reduces control overhead by confining most of the control messages to a region of interest (ROI) formed around each active source-destination pair. OPERA uses source and destination labels of nodes to define the ROI and a topological sort of destination labels for loop freedom. The use of label spacing allows effective local repairs for link and node failures. OPERA-SNR uses the framework of OPERA and an SNR based link metric to implement a scalable and resilient QoS protocol. Link Vectors in Regions of Interest (LVRI) is a scalable link-state protocol that uses link-state signaling inside the region of interest. Each node in the ROI maintains the topology graph of the ROI. Hence, every node has paths to every other node in the ROI and this reduces the route establishment delay.;All of these protocols, however, use network wide flooding to establish the routes. Multi-label Automatic Routing (MAR) eliminates flooding completely by positional labels and Distributed Hash Tables (DHTs). MAR is the first compact routing protocol that attains a low path stretch (ratio of selected path length to the optimal path length) while maintaining a low routing state for mobile networks. MAR is also resilient to node movements in the network. In MAR, routing is automatic based on the labels of the nodes and DHT lookups and does not need a routing table unlike traditional routing protocols. Multi-root Automatic Incremental Routing (MAIR) augments the MAR protocol by assigning multiple positional prefix labels to every node with respect to multiple roots in the network and by forming a region of interest. The nodes in the ROI maintain the most recent node id to labels mapping of the destination. This significantly reduces the route establishment delay for the nodes inside ROI as the need for DHT lookup is eliminated.