On Demand Routing in Large Ad Hoc Wireless Networks with Passive ClusteringMario Gerla, Taek Jin Kwon and Guangyu PeiComputer Science DepartmentUniversity of California, Los AngelesLos Angeles, CA, 90095Abstract – This paper presents on-demand routing scalabilityimprovements achieved using a “passive” clustering. Any ondemand routing typically requires some form of flooding.Clustering can dramatically reduce transmission overhead duringflooding. In fact, by using clustering, we restrict the set offorwarding nodes during flood search and thus reduce the energycost and traffic overhead of routing in dynamic traffic andtopology environments. However existing “active” clusteringmechanisms require periodic refresh of neighborhood informationand tend to introduce quite a large amount of communicationmaintenance overhead. In this paper, we introduce a passiveclustering scheme which is mostly supported/maintained by userdata packets instead of explicit control packets. The passivescheme is consistent with the on-demand routing philosophy.Simulation results show significant performance improvementswhen passive clustering is used.1. INTRODUCTIONClustering in wireless ad hoc network has been investigatedin order to enhance network manageability, channel efficiency[1,4], energy efficient communication [2], and to providerouting or multicasting scalability [3]. Clustering isindispensable for hierarchical routing or multicasting protocolsrely on clustering for scalability. However clustering requireshigh refresh rate, and therefore even more overhead in realisticad hoc environments because of unreliable links and nodes.In this paper, we identify the limitations of conventionalclustering in a realistic wireless ad hoc environment, andprovide solutions which overcome such limitations by using anovel clustering protocol with a new clusterhead election rule.We call the clustering mechanism “passive clustering” becauseit does not require periodic, background protocol-dependentcontrol packets or signals. Improvements of an on-demandrouting (Ad Hoc On-Demand Distance Vector -AODV) will bepresented as a example of passive clustering application todemonstrate the effectiveness of clustering in large scale ad hocnetwork.2. CLUSTER LIMITATIONSUnlike in a simulation environment, global informationregarding node locations and adjacency relations is hard tocollect in a realistic wireless ad hoc network. The majorreason of the difficulties comes from unreliable and limitedlink capacity and from node mobility. Node locations andneighborhood information are keys for clustering; they dovary in time. Without the help of a special node- say“oracle”-which can listen or speak to all the nodes at thesame time, adjacency (neighborhood) information can onlybe collected by exchanging beacons or hello messages. Toensure the correct collection of neighborhood information,previous clustering solutions assume repeated broadcastingof the neighbor listIn this period of neighbor learning and initial clustering, itis essential that there is no mobility for proper convergence.The quasi-stationary assumption must hold during theadjacency information collecting period, initial clustering,and the re-clustering or clustering maintenance period. Thereason for the quasi-stationary assumption is obvious whenwe collect adjacency information. If there is motion, wemay have to deal with stale neighborhood information.Moreover, mobility causes adjacency relation changes,which may trigger re-clustering throughout the network.Figure 1 demonstrates the case. The dotted circles representsthe result of Lowest ID algorithm clustering [1] while node1 is out of node 3’s range. As node 1 becomes adjacent tonode 3, node 3 abdicates clusterhead’s role, and triggers a“chain reaction” causing a change in all clusterheads.Figure 1. Chain effect when node 1 approaches to 3.The quasi-stationary assumption is a necessity for stableoperation in previous clustering mechanisms in whichclusterhead election rules are weight driven (e.g. ID, degree)34567814and are strictly enforced all the time. In section 3, we willaddress a new clusterhead election rule which overcomes theseproblems and does not require the quasi-stationary assumption.In a wireless environment, it is hard to ensure that a node hascollected all the neighborhood information (a completeneighbor list) even without node death/birth or mobility. Byassuming uniform radio transmit power (symmetric links all thetime) and perfectly coordinated communications (no collision,nor hidden terminal problems, etc) to assume perfect receptionof entire neighbor lists, collecting the complete set of adjacencyinformation is then feasible.The isolation problem is another difficult problem to solve.The isolation problem refers to cluster disconnection whilethere is a feasible radio path. Figure 2 shows an example ofisolation. Lowest ID algorithm ends up with solid circledclusters, which do not provide connectivity between node 5,6and node 7,2. If node 6 were elected clusterhead, and node 7became a gateway, the four nodes would be connected in theclustered structure. With weight driven clustering (like lowestID), the problem can be solved only by using ad hoc extensionsof the basic algorithm. For example, 6 and 7 become “split”gateways and jointly provide the required connectivity.Figure 2. Isolation problemIn next chapter, we introduce a new clustering mechanism,which virtually eliminates all clustering line overheads, is freefrom quasi-stationary assumption, and can provide consistentsolutions to the isolation problem.3. PASSIVE CLUSTERINGPassive Clustering is a cluster formation protocol, which doesnot use dedicated, protocol specific control packets or signals.Conventional clustering algorithms require all participatingnetwork nodes to advertise neighbor information repeatedly. Inan ad hoc network, collecting the neighbor information usuallytakes O(k) communications where k is the possible maximumdegree. This overhead is considered expensive in ad hocwireless networks where bandwidth is limited.Even worse, all the existing clustering schemes require aninitial clustering phase prior to any network layer activities.With passive clustering, we can avoid both of the abovedisadvantages.The key idea beyond passive clustering is toopportunistically exploit the neighborhood informationcarried by data packets. For example, by monitoring MAClevel packets, which piggyback sender state, we
View Full Document
Unlocking...