Scalable ad-hoc routing: design and implementation (2008)

In ad hoc wireless networks, scalability issue associated with routing is particularly critical as node mobility, constrained resource (e.g., bandwidth and power), and unpredictable radio channel behavior impose additional challenges to growth. The routing protocols for ad hoc wireless networks have to adapt quickly to the frequent and unpredictable changes of topology and must be parsimonious of communications and processing resources. Moreover, performance of routing protocols for mobile ad hoc networks have been evaluated extensively through simulations because diversified network conditions can be more easily configured and reproduced in simulation than real system. However, simulation works must be validated via measurements because some of the mobility, propagation and control processing assumptions are often over-simplified.
This dissertation proposes and studies strategies for designing scalable routing protocols. First we proposed a hybrid Landmark routing scheme that smoothly integrates advantages of both proactive and on-demand scheme and thus achieves good scalability. We also propose an extension of the Optimized Link State Routing (OLSR) protocol with Fisheye Routing Protocol for mobile ad-hoc networks. The key idea of the extended protocol named Optimized Fisheye Link state Routing (OFLSR) is to use different frequencies for propagating the routing update packets to nodes at different hop distances by applying FSR concept into OLSR. Popular ad hoc routing protocols such as DSDV and AODV use predecessor based forwarding, namely, the packet is forwarded to the predecessor that advertised the shortest path to destination during the last update. However, if the predecessor moves, the routing table entry becomes invalid and predecessor based forwarding fails! To overcome the stale forward table problem, in this dissertation, we also present a novel packet forwarding scheme—Direction Forwarding Routing (DFR). Furthermore, for validating the performance of routing protocols, we have implemented two routing protocols: LANMAR and ODMRP, respectively, in real test-bed environments as well as experimental results for these implementations. The experiences and discoveries from these experiments have greatly enriched our understandings of ad-hoc routing protocols. We report the lessons learned from these experiments in the dissertation.
Careful tuning of the routing protocols to make them scalable and efficient still does not guarantee good performance with TCP, especially in mobile environments. To overcome this problem, the routing protocol must be robust to mobility. To this effect, Geo-routing has recently received attention in large scale, mobile systems as it does not require end-to-end path establishment and pre-computed packet forwarding routing structure at nodes. These properties make Geo-routing robust to highly dynamic route changes. For best performance, however, several parameters both in TCP and in the routing algorithms must be carefully tuned. In the thesis, we study the joint optimization of TCP and Geo-routing parameters to handle high speeds. We study the impact of critical system parameters (e.g., hello message exchange rate, delay timer in TCP for out-of-order delivery, etc) on the performance of both UDP and TCP. We improve hello message efficiency in Geo-routing by using an adaptive hello exchange scheme. Then, we fix the out-of-order problem in TCP by using a receiver-side out-of-order detection and a delayed ack strategy. We show that these parameter adjustments are critical for efficient TCP over Geo-routing in highly mobile applications. With these enhancements our TCP with Geo-routing solution easily outperforms TCP over traditional ad hoc routing schemes, such as AODV.