Abstract-In this paper, we present an enhanced version of the routing protocol Landmark Ad Hoc Routing (LANMAR). LANMAR combines the features of Fisheye State Routing (FSR) and Landmark routing. The enhanced version features landmark election to cope with the dynamic and mobile environment. Other advantages of LANMAR include the use of landmarks for each logical group (e.g., a team of co-workers at a convention or a tank battalion in the battlefield) in order to reduce routing update overhead in large networks, and the exchanging of neighborhood link state only with neighbors. When network size grows, remote groups of nodes are "summarized" by the corresponding landmarks. As a result, each node will maintain accurate routing information about immediate neighborhood; at the same time it will keep track of the routing directions to the landmark nodes and thus, to remote groups. Simulation experiments show that the enhanced version suffers some performance degradation at steady state because of election overhead. However, it still provides an efficient and scalable routing solution in a mobile, ad hoc environment. Moreover, the election provides a much needed recovery from landmark failures. As the wireless and embedded computing technologies continue to advance, increasing numbers of small size and high performance computing and communication devices will be capable of tetherless communications and ad hoc wireless networking. An ad hoc wireless network is a self-organizing and self-configuring network with the capability of rapid deployment in response to application needs. An important characteristic which sets ad hoc networks apart from cellular networks is the fact that they do not rely on a fixed infrastructure. Ad hoc networks are very attractive for tactical communication in military and law enforcement. They are also expected to play an important role in civilian forums such as convention centers, conferences, and electronic classrooms. Node mobility/dynamics, potentially very large number of nodes, and limited communication resources (e.g., bandwidth and power) make routing in ad hoc networks extremely challenging. 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. Existing wireless routing schemes can be classified into two categories according to their design philosophy: (a) proactive (i.e., distance vector or link state based); and (b) reactive (i.e., on demand). Proactive schemes compute routes in the background, independent of traffic demands. Historically, the first type of routing scheme used in early packet radio networks such as the PRNET was the distance vector type [5]. The distance vector approach is simple but suffers from slow converThis work was supported in part by NSF under contract ANI-9814675, in part by DARPA under contract DAAB07-97-C-D321 and in part by Intel. gence and tendency of creating loops. These problems were later resolved by the Link State (LS) approach, which is widely used in wired nets (e.g., Internet [12] or ATM [l]). In Link State, global network topology information is maintained in all routers by the periodic flooding of link state updates by each node. Any link change triggers an immediate update. As a result, convergence to a new topology is faster and preventing loops is easier due to global topology knowledge. Unfortunately, excessive control overhead may be generated by LS dissemination especially when high mobility triggers frequent updates. Typically, when wireless network size and mobility increase (beyond certain thresholds), current "flat" proactive routing schemes (i.e., distance vector and link state) become infeasible because of line and processing O M . One way to solve this problem and generate scalable and efficient solutions is hierarchical routing. A hierarchical version of link state called HSR (Hierarchical State Routing) has proven to be quite effective in large wireless networks [lo]. HSR, however, requires complex bookkeeping of hierarchical addresses. A much simpler version of Link State with hierarchical "flavor" is Fisheye State Routing (FSR) [ 101. FSR uses the "fisheye" technique (first proposed by Kleinrock and Stevens [ 1 11 for visual displays) to reduce routing update overhead. In FSR, each node progressively slows down the update rate for destination with increasing hop distance. Thus, entries corresponding to nodes within a smaller scope are propagated to neighbors with a higher frequency. As a result, a considerable fraction of topology table entries (corresponding to remote destinations) are suppressed in a typical update, thus reducing line overhead. This approach produces accurate distance and path quality information about the immediate neighborhood of a node, with progressively less detail as the distance increases. As a packet approaches its destination, the route becomes more precise. As network size grows and mobility increases, however routes tend to become stale quickly and delays to nodes afar tend to grow large. Another recent approach to scalability and routing overhead problems is the reactive, on demand routing. Several schemes have been proposed including AODV [ 151, DSR [7], TORA [13] and ABR [17] etc. In these "reactive" protocols a node discovers a route "on demand", namely, it computes a route only when needed. Small Query/Reply packets are used to discover (possible more than one) route to a given destination. However, since a route has to be entirely discovered prior to the actual data packet transmission, the initial search latency may degrade the performance of interactive applications (e.g.,
Later, the same authors presented an enhanced version of LANMAR in REF .
Landmark routing for large ad hoc wireless networks
Globecom '00 - IEEE. Global Telecommunications Conference. Conference Record (Cat. No.00CH37137)
Globecom '00 - IEEE. Global Telecommunications Conference. Conference Record (Cat. No.00CH37137)
Computer Science