The most important characteristics of mobile ad-hoc networks (MANETs) such as broadcast and multihop communication, limited resources (particularly energy) and physical proximity are often ignored in solutions being proposed for information lookup and distribution. Thus, many lookup approaches rely on unstructured algorithms using flooding techniques, while content distribution mechanisms frequently generate inefficient multicast trees without considering the presence of nodes that are involved only as relays and are not interested in the distributed content. In this chapter, the authors present a multicast algorithm designed to build efficient multicast trees in MANETs that strive to limit the number of relay nodes and transmissions required. This distribution infrastructure relies on a lightweight distributed hash table (DHT) specifically adapted to MANETs, and exploits the physical proximity of nodes and broadcast communication. The algorithmic efficiency and scalability are evaluated by means of simulations for various network sizes and configurations.
TopIntroduction
Wireless technologies have become ubiquitous, providing improved connectivity in urban areas and also allowing outlying areas to connect to information networks. Now almost everyone makes use of wireless technologies to surf the web using portable phones or computers. The well-known applications they rely on are spread over wide areas and the number of service access points has increased exponentially.
In addition to phone calls and web surfing, many other applications are available on wireless enabled devices. They may take the form of ad-hoc networks requiring no specific infrastructures such as access points, and where these devices produce a self-organized mesh network in which each node able to communicate directly with its closest physical neighbors.
Despite the various types of devices and communication standards on which they are based, networking infrastructures and devices are all subject to the same limitations. The main concerns are limited resources and energy, and also practicality, such as movement and deployment almost anywhere. Most often the devices are small, simple and battery powered, and make use of limited resources (i.e., memory and CPU). Related to these, communications generate non-negligible costs leading to an overall reduction in network lifetimes. At this time, communication between remote nodes requires multiple hops via relay nodes, because nodes can only communicate directly with their physical neighbors (i.e., the nodes located in its communication range), although they may listen to all the messages transiting within its physical neighborhood.
As new devices with ad-hoc networking capacities and enhanced resources become developed their use is extended well beyond original functions related to wide-area monitoring. New developments now allow information lookup and multicasting, requiring novel and efficient solutions.
The focus in this chapter is lookup and multicasting mechanisms able to efficiently locate and distribute information in mobile ad-hoc networks (MANETs). The basic concept applied to achieve these objectives involves peer-to-peer (P2P) paradigms, which can be roughly classified as either structured or unstructured.
Unstructured approaches such as Gnutella or KaZaA (Kirk, 2003; KaZaA, 2008) typically have neither control over topology nor file placement, meaning they often rely on locating data by simply flooding the network and thus overloading it. Unstructured approaches such as these have not been adapted for MANETs because locating the desired content involves too many transmissions and too much energy. Moreover, scaling them can prove difficult (Oliveira et al., 2005).
Structured solutions on the other hand consist of specialized placement algorithms designed to assign the responsibility for each content unit (file) to a specific node and then efficiently locate the files using directed search protocols, requiring only limited communication. They are mostly based on distributed hash tables (DHTs) that locate each item and node by means of a unique key identity, producing a logical space. The nodes are thus arranged according to their logical key and are only responsible for an item located at the smallest logical distance from them. Another feature is provided so that a node responsible for a specific key can be located without flooding and without producing false negatives (i.e., a search fails only if no matching file exists in the system).
Well known solutions developed, including the Chord (Stoica, Morris, Karger, Kaashoek, & Balakrishnan, 2001), Pastry (Rowstron & Druschel, 2001) or CAN (Ratnasamy, Francis, Handley, Karp, & Schenker, 2001) are not, however, suitable for ad-hoc networks, because they do not consider a node’s physical locations when creating the logical overlay network. Given this fundamental gap between logical and physical spaces, the ad-hoc network becomes overloaded because service messages need to maintain the logical neighborhood through expensive multiple hop paths, thus making simple mapping from a DHT design to ad-hoc networks unrealistic.