Due to its bandwidth efficiency, multicast makes a group-centric communication more viable in wireless ad hoc networks with limited radio resources. PIM-SM, a de facto standard multicast protocol known for its high scalability, is a good fit for a large-scale ad hoc network. However, it does not provide a robust multicast communication under RP outage and host mobility. In this paper, we propose a robust way of configuring PIM-SM using Anycast RP in wireless ad hoc networks. We analyze the impact of cardinality and locations of anycast RPs on the network performance under node mobility. Based on these observations, we find metrics for near-optimal cardinality of anycast RPs and propose a novel RP selection scheme. The proposed scheme is proven to make PIM-SM robust against mobility while satisfying QoS requirements and maintaining the scalability of PIM-SM.

To build ad-hoc networks with hundreds or even thousands of nodes, the network must be split into relatively independent layer 3 clusters. There are currently no general approaches or methodologies for the creation of domains that take into account the following important engineering constraints: balanced domains, minimal inter-domain traffic, robust network design. Moreover, there is also no contribution that specifically addresses the problem of area formation for OSPF-based ad hoc networks. By assuming that the creation of layer 3 clusters is done after layer 2 topology management has set local radio parameters, we have re-formulated the problem at hand in a graph theoretic framework and found a strong connection between the problem of area design and a classical problem in graph theory, the graph partitioning (GP) problem. The limitation of GP algorithms (GPAs) is that they are OSPF-agnostic and, therefore, are not capable of solving the problem of robust backbone network (Area 0) design. We here propose a two-step approach for OSPF area design: the first step consists of an efficient GPA that will create areas (including a rough Area 0 design), and the second step consists of ad-hoc heuristics that are able to ameliorate the Area 0 design as well as factoring in OSPF specific metrics.

Hierarchical techniques have long been known to afford scalability in networks. By summarizing topology detail via a hierarchical map of the network topology, network nodes are able to conserve memory and link resources. Extensive analysis of the memory requirements of hierarchical routing was undertaken in the 1970s. However, there has been little published work that assesses analytically the communication overhead incurred in hierarchical routing. This paper assesses the scalability, with respect to increasing node count, of hierarchical routing in mobile ad hoc networks (MANETs). The performance metric of interest is the number of control packet transmissions per second per node (/spl Phi/). To derive an expression for /spl Phi/, the components of hierarchical routing that incur overhead as a result of hierarchical cluster formation and location management are identified. It is shown here that /spl Phi/ is only polylogarithmic in the node count.

The throughput of a mobile ad hoc network (MANET) is determined by the transceiver link capacity available at each node and the type of traffic pattern that is prevalent in the network. In order for a routing protocol to be scalable, its control overhead must not exceed transceiver link capacity. To achieve capacity compatible routing, hierarchical techniques may be employed. This paper describes how link state routing, with a single layer of hierarchy, provides sufficient scalability for MANETs where the traffic pattern consists of unicast communication between arbitrary pairs of nodes.

Numerous clustering algorithms have been proposed that can support routing in mobile ad hoc networks (MANET). However, there is very little formal analysis that considers the communication overhead incurred by these procedures. Further, there is no published investigation of the overhead associated with the recursive application of clustering algorithms to support hierarchical routing. This paper provides a theoretical upper bound on the communication overhead incurred by a particular clustering algorithm for hierarchical routing in MANET. It is demonstrated that, given reasonable assumptions, the average clustering overhead generated per node per second is only polylogarithmic in the node count. To derive this result, novel techniques to assess cluster maintenance overhead are employed.

A geography-based grid location service (GLS), proposed elsewhere, has resulted in a scalable location management service for mobile ad hoc networks (MANETs) where packet forwarding decisions are based on geographic position. A similarly scalable location management strategy has been devised for MANETs that employ hierarchical link state routing. Both approaches employ hierarchical principles to facilitate scalability. However, currently proposed approaches for hierarchical link state routing rely on a designated subset of nodes for location management. Such nodes represent potential sites of hot spot contention. In this paper, it is proposed that by applying the distributed database selection technique of GLS, a hierarchical location management scheme may be realized for MANETs based on link state routing that equitably distributes location server functionality among network nodes. Second, it is shown that location registration overhead per node for hierarchical location management is only logarithmic in the node count.

To discover a route to a peer node, an on-demand routing protocol may initiate a flood-search procedure known as route discovery. By selecting the correct query radius, the number of packet transmissions required for route discovery can be minimized. This paper presents methods to estimate the geographic radius (R/sub G/) and the number of currently active pairs of communicating nodes (P) in a mobile ad-hoc network. The methods are entirely distributed and incur little communication overhead. Network nodes can apply the estimated parameters to predict the probability mass function (PMF) of the route discovery hop distance. An accurate prediction of the PMF aids the selection of an appropriate query radius for the route discovery process. A computationally lightweight procedure to select an appropriate query radius, based only on an estimate of P, is also proposed. Simulation results show that this procedure facilitates a sensible tradeoff between the route request packet overhead and the route reply delay.