Efficient Power-aware Hybrid Routing Using Zoning for Ad Hoc Network

Jong Ho Lee and Hee Yong Youn School of Information and Communication Engineering Sungkyunkwan University Suwon, Korea
{glizid, youn}@ece.skku.ac.kr

Chansu Yu Department of Electrical and Computer Engineering Cleveland State University Cleveland, Ohio, 44115
[email protected]

Dongman Lee School of Engineering Information and Communication University Taejon, Korea
[email protected]

Abstract
A number of routing protocols have been proposed for mobile ad hoc networks. In this paper we propose a hybrid multiple zoning scheme minimizing the number of route request messages and nodes involved in the route discovery process by applying proactive routing between high power nodes and reactive routing between other nodes. Computer simulation using NS2 reveals that the proposed approach can significantly lower routing overhead compared to previous schemes. Also, the improvement gets more significant as the number of nodes in the network increases. Keywords: Ad hoc networks, flooding, hybrid multiple zone, power node, routing.

1 Introduction
Ad hoc network is a dynamic network composed by the nodes communicating with each other without any help of fixed infrastructure network. It consists of fixed and wired gateways, a group of mobile nodes, and a much smaller number of base stations or access points [1]. Ad hoc network is characterized by changing/unpredictable network topology, high degree of mobility, energy constrained mobile nodes, and bandwidthconstrained. Especially, high mobility causes large routing overhead due to continuous topology changes. The routing protocols used by ad hoc network need to emphasize convergence, bandwidth overhead, forwarding latency, and route and cache correctness [2]. Routing techniques that have been proposed for ad hoc network are classified into Proactive routing and Reactive routing. The proactive routing approach attempts to maintain up-to-date routing information from each node to every other node in the network. It requires each node to respond to the changes in network topology by propagating route updates throughout the network to maintain a consistent network view. As the mobility of the nodes increases, thus, the amount of routing packets increases because of periodic flooding of routing packets. With the reactive routing approach, when a source node wants to send a packet to a destination, it invokes the

route discovery mechanism to find a path to the destination. It thus requires a smaller number of routing packets than proactive routing. For large size network hierarchical routing can be used. Hierarchical routing is base on the idea of organizing the nodes in groups and assigning different functionalities to the group member nodes and nonmember nodes. A most popular way of building the hierarchy is to group the nodes geographically close to each other into explicit clusters. Each cluster has a node communicating with the nodes in different clusters on behalf of the nodes in a cluster. In this paper, we propose a hybrid routing strategy that capitalizes the advantages of both proactive routing and reactive routing mechanism to improve the communication quality while maintaining low routing overhead. Since each node has different bandwidth and energy in real environment, they are classified into two classes. Power nodes have large bandwidth and energy, and thus employ on-demand routing using zones. Normal nodes refer to the nodes that have smaller bandwidth and energy than Power nodes, and thus participate in routing with reduced routing overhead using Power nodes. Computer simulation using NS2 reveals that the proposed approach significantly improves data packet delivery ratio and routing overhead. The rest of the paper is organized as follows. In Section 2, the work related to routing protocols based on zoning and on-demand scheme is presented. In Section 3, we propose a hybrid routing protocol employing different classes of nodes. Section 4 presents the simulation model and performance of the proposed scheme, and compares it with earlier schemes. Finally, Section 5 presents the conclusion of the paper.

2 Related Work
In general, on-demand routing is preferred in ad hoc routing due to limited bandwidth and energy. Here we review some representative on-demand routing such as DSR(Dynamic Source Routing) [4], ZRP(Zone Routing Protocol) [5], and LAR(Location Aided Routing) [6].

2.1 Dynamic Source Routing The DSR uses source routing, i.e. each packet contains full route to destination and intermediate nodes do not have to make any routing decision. Source routing is a routing technique in which sender of a packet determines a complete sequence of nodes through which the packet is forwarded. DSR has two principal components: Route Discovery and Route Maintenance. A ROUTE REQUEST packet is used for route discovery. A ROUTE REPLY packet is generated from the destination or a connected node. To reduce the overhead for route discovery, the nodes maintain a cache of learned or overheard routes. Route Maintenance is the mechanism used to detect link failures, and ROUTE ERROR packet is used to notify the sender. The sender can then use another route stored in its cache or initiate Route Discovery. 2.2 Zone Routing Protocol The ZRP [5] is a hybrid routing protocol that combines proactive and on-demand routing strategy, and benefits from both of them. The basic idea is that each node has a predefined zone centered at itself in terms of the number of hops. For only the nodes within a zone, it uses proactive routing protocol to maintain routing information. The ZRP protocol consists of three components. Within a zone, proactive Intrazone Routing Protocol (IARP) is used to maintain routing information. IARP can be link state routing or distance vector routing depending on the implementation. For the nodes outside the zone, reactive Interzone Routing Protocol (IERP) is performed. IERP uses the route query (RREQ)/route reply (RREP) packets to discover a route in a way similar to typical on-demand routing protocols. IARP always provides a route to the nodes within the zone. When the intended destination is not found, the destination must be outside the zone. Thus, an RREQ packet is broadcast via the nodes on the border of the zone. Such broadcast is called Bordercast Resolution Protocol (BRP). Route queries are broadcast only from a nodes border nodes to other border nodes until it finds a path to the destination node. 2.3 Location Aided Routing The LAR [6] is a source-initiated on-demand routing protocol having features found in DSR and AODV [3]. DSR and AODV are based on variations of flooding. Flooding algorithm causes many redundant transmissions of route requests generated by the nodes located far away from the destination. Therefore, a new approach is required to reduce the number of nodes to whom the route request is propagated.

The LAR utilizes two physical zones, expected zone and request zone. Consider S that needs to find a route to D. Assume that S knows that D was at location L at time t0, and current time is t1. Then, from the viewpoint of S at time t1, the expected zone of D is the region that is expected to contain D at time t1. S can determine the expected zone based on the knowledge that D was at location L at time t0. If S knows that D travels with an average speed v, then S may assume that the expected zone is the circular region of radius v(t1 - t0), centered at location L. Expected zone is an estimate made by S to determine a region that potentially contains D at time t1. If S does not know the previous location of D, then S cannot reasonably determine the expected zone. Hence, the entire region that may potentially be occupied by the ad-hoc network is assumed to be the expected zone. In this case, the algorithm reduces to the basic flooding algorithm.

3 The Proposed Scheme

3.1 Basic Idea Data transmission needs route establishment between source and destination node. General routing protocols use packet flooding for route discovery, which significantly reduces the whole network performance. In on-demand routing, though, the number of routing packets due to route establishment is much smaller than that of table driven routing. The previous on-demand routing protocols assume that each node has equal resource and routing ability. However, all nodes have different energy, memory, and radio transmission range in real environment. Radio transmission distances of the nodes vary according to electric power of each node. Mobile node limits the radio transmission distance because of small electric power, and thus it handles long range communication by multihop routing. We, thus, propose to divide the nodes into two classes for route establishment which allows wider area routing than previous routing protocols. The higher class nodes use GPS information and have radio radius bigger than other nodes. We call them Power Nodes. The lower class nodes have smaller radio radius (e.g. such as handheld device) than Power Nodes. We call them Normal Nodes. Normal Node supports the routing with general on-demand protocol in small local zone. If network size increases, data transmission occurs between Power Nodes with confined routing zone. As we show later, this can reduce routing overhead and increase network performance.

3.2 Route Discovery and Maintenance With the proposed scheme each node decides itself as Power Node or Normal Node according to the resources (e.g. energy power, radio range, GPS communication). The Power Nodes broadcast their positions to surrounding nodes using RSP (Routing Search Packet). The RSP's destinations are on the broadcast address. The nodes receiving the RSP make routes to the Power Node through RSP Reply. If the Normal Nodes are not in 1-hop distance to the Power Node, other Normal Nodes deliver the RSP Reply to the Power Node. The Power Nodes maintain routing table to the Normal Nodes of its zone by proactive routing. A Normal Node finds the position of its initial Power Node through the Power Node's RSP. Then, when it becomes a sender, it transmits an RSP to it by bidirectional transmission. If a Power Node receives an RSP from a Normal Node, it checks the routing table. If the destination node is found in its routing table, it delivers the RSP to the destination node. A Normal Node receiving the RSP transmits an RSP Reply to the Power Node. Then, it forwards the RSP Reply to the source Normal Node. However, if a Power Node does not exist in the source Normal Nodes zone, it sends an RSP like a Power Node and composes a routing table. When an RSP is received by a Power Node for route establishment and there is no destination node in its own routing table, it receives the initial Power Node's information of the destination node by GPS and transmits the RSP to a Power Node close to the destination node. Here we define a rectangular shape area covering the sender Power Node and receiver Power Node, which is called request zone. If the forwarding nodes are Normal Nodes, large resources are wasted for packet forwarding. Therefore, we make subrequest zone using the Power Nodes existing between the sender Power Node and receiver Power Node. It can substantially reduce routing overhead because the number of nodes participating in packet forwarding becomes much smaller than previous routing schemes(e.g. LAR).

decides route table to the destination node using the route cache information of the received RSP Reply packet. When the source sends data packets to destination, each intermediate node sends AP (Acknowledgement Packet) to the preceding node. If AP is not received, the preceding node sends RFP (Route Fail Packet) to the source node, and then it needs to discover a route again. As shown in Figure 2, the proposed scheme uses smaller request zone than previous multiple zoning protocol [2]. Therefore, the number of nodes participating in route discovery is smaller which in turn lowers routing overhead. In earlier multiple zoning scheme of Figure 2(a), subrequest zones are made using fixed posts. Here packet transfer to other nodes in each zone is made by simple flooding. In the proposed hybrid multiple zoning of Figure 2(b), each Power Node has information on its own Normal Nodes and routing is possible with a smaller number of routing packets.
Request Zone Destination Request Zone Destination

Source

Fixed Nodes (a)

Source

Power Nodes (b)

Figure 2. Previous multiple zoning and proposed scheme: (a) Multiple zoning with 2 posts (b) Hybrid multiple zoning with 4 Power Nodes.

4 Performance Evaluation
The simulator for evaluating the proposed approach is implemented using the NS2 Simulator [7]. Here we simulate and compare four routing algorithms ZRP, LAR, multiple zoning, and the proposed hybrid multiple zoning. Initially, we assume that all nodes within the network know their current locations and the network has no transmission error. The nodes in the network are assumed to be randomly distributed in a 2000m x 2000m square region. We assume that each node has pause time (0, 30, 60, 120, 300, 600, or 900 seconds). For each simulation run, the nodes are generated with uniform distribution, and one Source and Destination pair are chosen randomly among them. The number of nodes in the network is 100, and 20 of them are Power Nodes. The number of source nodes is 27 and the number of source to destination communication is 40. Figure 3 shows the node participation ratio, which is the number of forwarding nodes over the total number of nodes in the network. ZRP divides the network into

Power Node Source

Destination

Figure 1. Hybrid multiple zoning. Figure 1 shows the proposed hybrid routing based on multiple zoning, where the source and destination are Normal Node. After route establishment, the source node

many zones, while each node has same ability (power, radio radius, and so on). Also, the size of zone is smaller than the proposed scheme, and it needs more forwarding nodes and routing packets than the proposed scheme. LAR, multiple zoning, and hybrid multiple zoning reduce the number of forwarding nodes using request zone approach. Notice from Figure 3 that the proposed hybrid multiple zoning scheme needs the smallest number of forwarding nodes using the Power Nodes. It covers larger network areas and transmits packets more stably. Multiple zoning and hybrid multiple zoning makes subrequest zones and the number of participating nodes is smaller than other protocols.
1 node participation ratio 0.8 0.6 0.4 0.2 0
0 30 60 120 300 Pause time(secs) 600 900 ZRP LAR Multiple Zoning with 2 posts Hybrid Multiple Zoning

ZRP 60000 LAR Multiple Zoning with 2 posts Hybrid Multiple Zoning 50000 40000 30000 20000 10000 0 0 30 60 120 300 600 900

routing overhead

Pause time (secs)

Figure 5. Comparison of routing overhead.

5 Conclusion
The proposed hybrid multiple zoning scheme for ad hoc networks applies proactive routing between the high power nodes and reactive routing between the normal nodes. Simulation results indicate that the proposed scheme significantly lower the routing overhead and improves communication efficiency compared to other previous schemes. More work will be needed for further improving the performances. Also, an efficient approach is needed which can utilize the existing routing information when some network links fail.

Figure 3. Comparison of node participation ratio. In Figure 4, data packet delivery ratios are compared. The proposed hybrid multiple zoning scheme uses Power Nodes that have larger radio radius than other nodes. It can thus make shorter route from the source to destination node than previous schemes. Therefore, even though some Power Nodes move to other positions, it still guarantees packet transmission using re-route establishment between the Power Nodes. Also observe that, as pause time increases, data packet delivery ratio becomes close to 1 because movement of nodes decreases and the network stabilizes. If node mobility increases, data packet delivery ratio decreases.
1 data packet delivery ratio 0.96 0.92 0.88 0.84 0.8 0 30 60 120 300 Pause time(secs) 600 900 ZRP LAR Multiple Zoning with 2 posts Hybrid Multiple Zoning

References
[1] X. Hong, K. Xu, M. Gerla, Scalable Routing Protocols for Mobile Ad Hoc Networks, IEEE Network, Volume: 16 Issue: 4, pp. 11-12, July-August 2002. [2] M. J. Suh, H. Y. Youn, J. H. Lee, H. Choo, Multiple Zoning with Multiple Posts for Efficient Routing in MANET, 2th International Conference on Computer and Information Science(ICIS 2002), pp. 831-836, August 2002. [3] C-K Toh Ad Hoc Mobile Wireless Networks, Prentice Hall PTR 2002. [4] D. B. Johnson and D. A. Maltz, Dynamic Source Routing in Ad Hoc Wireless Networks, Mobile Computing, T. Imielinski and H. Korth, Eds., Ch. 5, Kluwer, pp. 153181, 1996. [5] Z. J. Haas and M. R. Pearlman, The Performance of Query Control Schemes for the Zone Routing Protocol, ACM/IEEE Trans. Net., vol. 9, no. 4, pp. 42738, August 2001 . [6] Y.-B. Ko and N. H. Vaidya, Location-Aided Routing (LAR) in mobile ad hoc networks, Wireless Networks, Volume 6 Issue 4, pp. 307-321, July 2000. [7] The CMU Monarch Projects Wireless and Mobility Extensions to ns, The CMU Monarch Project, August 1999. Available from http://www.monarch.cs.cmu.edu/ [8] S. Corson, J. Macker, Routing Protocol Performance Issues and Evaluation Considerations, RPC-2501, January 1999. [9] I. Stjmenovic, Position-Based Routing in Ad Hoc Networks, IEEE Communications Magazine, Vol. 40, Issue. 7, pp. 128-134, July 2002.

Figure 4. Comparison of data packet delivery ratios. In Figure 5, the routing overheads are compared. Note that ZRP and hybrid multiple zoning use proactive routing in which routing table is constructed beforehand. Therefore, the number of routing packets is smaller than simple on-demand routing such as LAR and multiple zoning. As pause time increases, the routing overhead decreases as expected.