Addressing scalability in Mobile Ad hoc Networks

Abstract

Mobile Ad hoc Networks (MANETs) are wireless networks comprised of nodes which exhibit varying mobility and availability. Such networks are highly volatile, with network membership changing unpredictably over time. As Wifi-enabled mobile devices such as smartphones have become more ubiquitous and powerful, new applications which utilize ad hoc networking have emerged such as mobile multiplayer games and data sharing applications. Such applications currently work within single-hop distances, however, in the future multi-hop connections may be required in order to enable communication at increased distances. In such a scenario, routing protocols which can operate at high device densities and cope with large networks will be needed. The provision of routing information can, however, have a detrimental effect on application throughput and network scalability due to medium access limitations and radio interference. Attempting to provide relevant routing information without negatively impacting MANET usability represents a significant challenge. Existing approaches to routing in MANETs attempt to reduce these effects through the use of intelligent forwarding algorithms, flood propagation restrictions, dependence on geographical information or combinations of these approaches. These approaches are based upon wired network routing protocols which attempt to route packets to nodes with specific and unique identities or addresses. In a MANET, however, the identities of nodes may not be known in advance. Thus address or identity-based routing makes little sense in a MANET context. Additionally, the overheads generated by existing protocols when distributing routing information for every node or flooding queries throughout the network can have a significant negative impact on application throughput and network scalability. In recent years, new communication approaches have emerged, such as protocols designed to dynamically discover services and resources in the network. These protocols attempt to provide information regarding available services to interested clients. This function is necessary as uncertainties regarding network membership and node capability caused by mobility and limited battery capacity make the use static associations between services and specific node viii 0 addresses impractical. Existing works in the area of service discovery attempt to create a mapping between provided services and server node addresses which may then be used by an underlying routing protocol to route traffic between a client and a server. This approach generates significant communication overheads due to the use of both service and route discovery in the same network. More recent service discovery protocols attempt to reduce overheads by integrating directly with an existing routing protocol, in effect ’piggy-backing’ their service advertisement or query messages on routing messages. Such cross-layer approaches have reduced overheads compared with separated protocols, however they still have a significant negative impact on application throughput due to their reliance on an underlying routing protocol. In this thesis we discuss a new approach to improving scalability and usability for MANETs. Our protocol, Service Discovery Routing Protocol (SDRP), is designed to overcome the disadvantages posed by existing solutions in the service discovery space by reducing discovery overheads through the use of novel forwarding techniques and entirely removing reliance on an underlying routing protocol. In an SDRP-based network, server nodes advertise their services throughout the network using a modified version of the OLSR Multi-Point Relay (MPR) algorithm; an approach which significantly reduces overheads through the avoidance of flooding. Our selective forwarding algorithm, Reduced MPR (RMPR), uses bloom filters to facilitate forwarding node selection and entirely removes the use of periodic beacons in order to reduce network overheads. Crucially, unlike networks based on OLSR, in SDRP networks only nodes that provide services propagate routing information, rather than all nodes. This removal of support for address-based routing significantly reduces overheads while maintaining low end-to-end delay, allowing networks of increased density to be formed without negatively impacting application throughput. This thesis makes two key contributions: Firstly, a new forwarding algorithm called Reduced Multi-Point Relay which significantly reduces overheads when compared to the traditional approach. Secondly, a new routing protocol for MANETs called Service Discovery Routing Protocol based on service-oriented routing rather than address-based routing. SDRP utilizes Bloom Filters and the RMPR intelligent forwarding algorithm to significantly reduce overheads, thus improving network scalability; particularly in high node density scenarios.