Exploiting wireless link dynamics

Efficient and reliable communication is the key to enable multihop wireless networks such as sensornets, meshnets and MANETs. Unlike wired networks, communication links in wireless networks are highly dynamic and pose additional challenges. Network protocols, besides establishing routing paths between two nodes, must overcome link dynamics and the resulting shift in the network topology. Hence, we need to develop efficient link estimation mechanisms, reliable routing algorithms, and stable addressing schemes to overcome these challenges inherent in wireless networks. The prevalent approach today is to use routing techniques similar to those in wired networks, such as tree construction: Link estimators identify neighbors with consistently high quality links based on a certain cost metric. Routing protocols conserve routing to a single path between two communication nodes by choosing the best sequence of nodes at each hop, as identified by the link estimator. In contrast, recent studies on opportunistic routing schemes suggest that traditional routing may not be the best approach in wireless networks because it leaves out a potentially large set of neighbors with intermediate links offering significant routing progress. Finegrained analysis of link qualities reveals that such intermediate links are bursty, i. e., alternate between reliable and unreliable periods of transmission. We propose unconventional yet efficient approaches of link estimation, routing and addressing in multihop wireless networks to exploit wireless link dynamics instead of bypassing them for the sake of stability and reliability. The goal is to maximize routing performance parameters, such as transmission counts and throughput, by exploiting the burstiness of wireless links while, at the same time, preserving the stability and reliability of the existing mechanisms. The contributions of this dissertation are manifold: Firstly, we develop relevant link estimation metrics to estimate link burstiness and identify intermediate links that can enhance the routing progress of a packet at each hop. Secondly, we propose adaptive routing extensions that enables the inclusion of such long-range intermediate links into the routing process. Thirdly, we devise a resilient addressing scheme to assign stable locations to nodes in challenging network conditions. Finally, we develop an evaluation platform that allows us to evaluate our prototypes across different classes of wireless networks, such as sensornets and meshnets, using a single implementation. The dissertation primarily focuses on the network layer of the protocol stack. Although the proposed approaches have a broader relevance in the wireless domain, the design choices for our prototypes are tailored to sensornets – a notoriously difficult class of multihop wireless networks. Our evaluation highlights the key achievements of this work when compared to the state-of-the-art: The proposed metrics identify bursty links in the network with high accuracy, the routing extensions reduce the transmission count in the network by up to 40%, and the addressing scheme achieves 3-7 times more stable addressing even under challenging network conditions.