Routing has always been one of the key challenges in MANETs and the challenge becomes more difficult when the network size increases. Many routing protocols for MANETs have been proposed, which can be divided by flat routing and hierarchical routing. The protocol DSR [2] and AODV [3] are typically flat routing. However, when the network grows large and there are more mobile nodes in the network, it takes more size to keep the route path, as well as this path becomes so unstable that it will break at any time for flat routing. Some other routing algorithms for mobile ad hoc networks have been proposed to handle the mobile nodes. Position-based routing algorithms use some additional information about the physical position of the participating nodes through the use of the GPS or some other types of position service, which is not always available.

Compared to flat routing, hierarchical routing has at least four outstanding advantages. First, it can use different radio channels in different clusters which improve the system capacity greatly. Second, it reduces the route table largely. Third, it can handle mobile environment more efficiently because of group stability. Finally, it can support MANET with a large number of nodes. Cluster-head gateway switch routing protocol (CGSR) [4] is a traditional hierarchical routing using DSDV as an underlying protocol. In this modal, mobile nodes are partitioned into clusters and a cluster-head is elected using distributed algorithm and a node that is in the communication range of two or more cluster-heads is called a gateway node. All the packets will pass to cluster-heads and then to another cluster-heads or destination, which means that the nodes connect with each other through cluster-heads and gateway nodes. However, the maintenance of the cluster structure is difficult and its performance is largely affected by the cluster-heads and gateways. Based on [4], [5] and [6] both adopt a way used in mobile IP to track the mobility of nodes that the nodes register their current address to nodes acting as home agents. Since a node does not know which cluster a particular destination belongs to, except for those destinations within the same lowest level cluster and all home agents will advertise their (Hierarchy ID) HID's to the top level hierarchy, a source node will prefer to send packets to the home agent of the destination node, then the home agent transfer the packets to destination. Once source and destination have learned each other's hierarchical addresses, packets can be delivered directly without involving the home agent. It solves the problem that when nodes moves away how the route will be set up again. [7] provides a way named Cluster-based Multipath Dynamic Source Routing (CMDSR) to realize multipath transmission of packets, which make sufficient use of the link. Source node S sends a route request message (RREQ) to its cluster head, then the cluster head judge whether the destination node D is in the same cluster as the source node S. If as so, the cluster head informs the source node S to start the routing discovery procedure (using DSR), otherwise, the cluster forwards the RREQ message to the higher server cluster, the server cluster looks for which cluster the destination node D belongs to according to the network topology, then searches for a stable route as a queue directional guideline. However, they don't solve the problem of high overhead when dynamically maintain the hierarchy in mobile environments. At the same time, the cluster-heads will easily become the bottleneck of the whole network.

DSR over AODV Routing (DOA) [8] is a lightweight hierarchical routing protocol which divides route into segments that we can take it as one dimension hierarchy. At a higher level, DSR is being used as a global intersegment routing protocol while AODV is being used as intra-segment routing at a lower level. It claims that once a route broken happens, it can be fixed locally at the level of a segment. Although its overhead is lower than strict hierarchical routing, the waypoint nodes in higher level are as unstable as other nodes, which cause an intersegment route repair happen frequently. So its performance in MANET is still restricted. In this paper, we use the same hierarchical model in [6], while our main focus is on how to manage the cell (cluster) to make it more stable and maintain the overhead in a more acceptable level. Besides, we also manage to reduce the traffic through the cell-head to make it more sustainable.

                           Hierarchy Structure

[2] J. Broch, D. Johnson, and D. Maltz, "The dynamic source routing protocol for mobile ad hoc networks" IETF, Internet Draft, draft-ietfmanet-dsr-00.txt, Mar. 1998
[3] -, "Ad hoc on demand distance vector (AODV) routing," IETF, Internet Draft, draft-ietf-manet-aodv-00.txt, Nov. 1997.
[4] C.-C. Chiang, H.-K. Wu, W. Liu, and M. Gerla, "Routing in Clustered Multihop Mobile Wireless Networks with Fading Channel," Proc. Singapore Int'l Conf. Networks (SICON'97), pp. 197-211, Apr. 1997.

[5] G. Pei, M. Gerla, X. Hong, and C. Chiang. A wireless hierarchical routing protocol with group mobility. In Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), September 1999.

[6] A. Iwata, C.-C. Chiang, G. Pei, M. Gerla and T.-W. Chen, "Scalable routing strategies for ad hoc wireless networks," IEEE J. Select. Areas Commun., Vol. 17, No. 8, August 1999, pp. 1369-1379.

[7] Hui-Yao An; Ling Zhong; Xi-Cheng Lu; Wei Peng, A cluster-based multipath dynamic source routing in MANET Wireless And Mobile Computing, Networking And Communications, 2005.

[8] Rendong Bai and Mukesh Singhal, "DOA: DSR over AODV Routing for Mobile Ad Hoc Networks," IEEE Transactions on Mobile Computer, vol. 5, NO. 10, October 2006