Printer Friendly

Low overhead geometric on-demand routing protocol for mobile ad hoc networks.

1. Introduction

Mobile Ad Hoc network is a collection of many mobile nodes with wireless send-receiver devices, these nodes can dynamically form a temporary network without any centralized administration and no fixed infrastructures. MANET is considered as a multi-hop and self-organized network, it has dynamic topology, constrained wireless transmission bandwidth, constrained resource of mobile snode and other characteristics [1]. Due to multi-hop, the high mobility of mobile node and other characteristics, the traditional routing protocol based on the Internet can not used in MANET directly. Therefore, it is still an important issue to design an efficient, flexible and dynamic routing protocol in MANET.

At present, the routing protocols of the MANET mainly divide into two types: the proactive routing protocols and the reactive routing protocols [2,3]. The typical routing protocols include: DSDV (Highly Dynamic Destination Sequenced Distance Vector Routing), DSR (dynamic source routing), AODV (Ad Hoc On Demand Distance Vector Routing) and so on. DSDV is the proactive routing protocol, the theory of this type protocols is that each mobile node establishes and maintains a complete routing table which contains the route to each node, it can rapidly reflect the network topology, the delay of this type is smaller, but the routing overhead is larger, the efficiency of protocol is lower; DSR and AODV are the reactive routing protocols, the theory of this type's protocols is that each node do not maintain any information of the routing in advance, only when sending data to the destination node, the source node launches the routing searching process in the network to search and establish the corresponding routing, thus this way save some unnecessary routing overhead, but increases the packet transmission delay.

AODV is specifically designed for mobile Ad Hoc networks as a reactive routing protocol; it is simple, reliable and has the superior performance [4]. AODV is essentially a comprehensive routing protocol of DSR and DSDV. It uses the same routing discovery mechanism as DSR and hop-by-hop routing, the sequence numbers and the periodical updating mechanism in the maintenance phase of DSDV [5]. Being different from the DSDV which preserves a complete routing table, AODV reduces the number of routing broadcasting by establishing the on-demand routing; it is an important improvement of AODV on DSDV. Compared with DSR, the advantage of AODV is that the source routing is not contained in every data packet, this makes the overhead of routing protocols decrease correspondingly, and it also reduces the energy consumption of mobile nodes, and extends the living time of the network effectively.

On the whole, the performance of AODV is more superior, but in the intensive network, there are still many shortcomings. For example, using the flooding broadcasting method can cause a larger network load and routing overhead. Using the flooding broadcasting method can ensure that it has the maximum possibility to find the route in theory, but many unnecessary nodes are involved in forwarding process, this makes a large of redundant routing control packets existing in the network, which will cause 'broadcast storm' and transmission channel congestion [6,7]. Much redundant control packets will increase network load, the routing overhead. Meanwhile, they occupy a lot of network bandwidth and increase the average end-to-end latency. Overall, the flooding method reduces the whole performance of network. In order to solve the problems, we ameliorate the routing discovery process of AODV, and propose the improved geometric routing protocol--Geometric AODV (G-AODV).

The article is organized as follows. In section 2, we comment on some related work. Section 3 talks about the proposed improved algorithm which is based on the original algorithm AODV. Section 4 shows the results of simulation experiments obtained by using NS2 emulator, and analyzes the experimental results. Section 5 gives the summary and the future directions.

2. Related Work

In terms of the simple flooding method in the route discovery, for improving the flooding efficiency and reducing the route overhead, several routing protocols have been proposed to optimize the flooding broadcast algorithm. Our work presented in this paper is related to existing research on the flooding broadcast algorithm. We therefore comment on some of these algorithms in the following. G. X. Jiang et al [8] propose the efficient route broadcast algorithm to restrict flooding in the light of Euclidean distance, it uses the fewer forwarding node to cover the more nodes in the network. When the node wants to send the RREQ packet, another nodes which are in the cover area of this node are divided into inside and outside part, only the external nodes can forward the RREQ packet, thus, reduce the number of the forwarding nodes. DREAM (Distance Routing Effect Algorithm for Mobility) [9] uses the directed flooding technology to restrict the flooding area toward the destination node. When the node forwards RREQ packet, it will choose the forwarder node according to the location information of another nodes and the selected angle. This method only allows forwarding RREQ in some directions. Expanding ring search (ERS)[10] adds the TTL filed to the RREQ packet, it does not flood in the whole network to search the route, but expand the searching area gradually until find the destination node or the node which has the valid route to the destination node. When the destination node is the neighbour node of the source node or within the few hop area of the source node, this method is obvious. However, if the destination node is far from the source node, the source node needs to repeatedly send the RREQ packets, this method increases the routing overhead instead. In addition, every time the source node needs to wait for some time, until it ensure that it does not receive the RREP packet, the source node starts the next searching, increases the delay. SHIN K et al [11] presents a simple expanding ring search algorithm, it uses two-levels expand mechanism, and sets threshold value to TTL. When TTL value is greater than zero, if the destination node can be found, the broadcast will stop, otherwise, it will use the flooding broadcast method in the whole network to search the route, the threshold value L is the key.

3. The Design Scheme of the Improved AODV Routing Protocol--G-AODV

In Mobile Ad Hoc Networks, because AODV use the simple flooding algorithm to broadcast the control packets in the routing discovery process, this makes a large number of redundant control packets in the network, so the routing overhead is larger, especially in the intensive network environments. In the paper, We propose the G-AODV routing protocol which is based on geometric routing protocol, the protocol add some geometric information to optimize the AODV routing protocol, that is, using the geometric routing protocol optimize the flooding broadcasting algorithm in the routing discovery process, and limit the number of forward node in the network, thereby reduce the routing overhead in the network. In view of the GPS function is relatively common in the smart terminal; we assume that we adopt the GPS positioning tools to obtain the location of every mobile node in time.

The proposed G-AODV routing protocol is also composed of the route discovery process and the route maintenance process. In this paper, we mainly revises the routing discovery process of AODV, we increase the RANGE field (used to record the routing pipe radius) and the location coordinate of the node (whenever the node will starts a new routing or forwards the broadcast packet, the node add its location coordinates in the RREQ packet), the improved algorithm only makes that the nodes which is in the routing pipe and close to the destination node can forward the packets. In addition, the routing maintenance process is basically the same as AODV.

In the routing discovery process, G-AODV still relies on the intermediate nodes to establish and maintain a dynamic routing table. When the source node sends data to the destination node, if there is no valid route to the destination node in its routing table, the node will start the routing discovery process, and then establish a new routing. The source node forwards the Route Request packet (RREQ) to all its neighbour nodes within the transmission range. However, before sending out the RREQ packets, the node needs to determine which neighbour nodes are the qualified forwarders according to the geometric route in routing discovery process of GAODV. The geometric route algorithm for the node selections in the routing discovery process is described as follows.
Algorithm 1: the geometric route algorithm for the node
selections and the packet forwarding in the routing
discovery process

1: Get the RREQ packet information from the forward node F;
2: Compute the distance D1 from the neighbour nodes to the
destination node [S.sub.0], then compute the distance [D.sub.0] to the
routing vector [bar.[S.sub.1][S.sub.0]];
3: IF ([D.sub.0] > RANGE)
4: Discard the RREQ packet;
6: IF ([D.sub.1] < [absolute value of F[S.sub.0]])
7:    IF (The RREQ packet not in the node RAM)
8:       IF (The node is the destination node or it has a valid
9:       The node will sent back the RREP
                    Packet to the source node;
10:      Else
11:         Update the route;
12:      Add the forward node, the node coordinate and the
          distance from the node to the destination node [S.sub.0];
13:       Forward the RREQ packet;
14:       Keep the RREQ packet in the node RAM;
15:   Else
16:      Discard the RREQ packet;
17: Else
18:    Discard the RREQ packet;

For convenience, we use the example to illustrate the geometric route in the routing discovery process of GAODV. The basic principle that using the geometric route replaces the flooding algorithm in the route discovery process is described as follows. Assuming that there are some packets need to be sent from the source node [S.sub.1] to the destination node [S.sub.0], the node F is the intermediate node and receives the RREQ packet from other nodes. If the intermediate node F is the valid node to forward RREQ packets, node F will calculate the distance [absolute value of F[S.sub.0]] to the destination node [S.sub.0] according to the information of their location coordinates and put the distance [absolute value of F[S.sub.0]] in the corresponding field of RREQ packets, then it forwards the RREQ packet to its another neighbour nodes. All the neighbour nodes received RREQ from node F also will calculate the distance [D.sub.1] to the destination node [S.sub.0] and the angle a, the angle is formed by the line decided by the neighbour node to the destination node [S.sub.0] and the routing vector [S.sub.0][S.sub.1] decided by the destination node [S.sub.0] to the source node; these neighbour nodes will use their distances to the destination node [S.sub.0] and the angle a to compute the distance D0 to the routing vector [S.sub.0][S.sub.1] respectively. If D>RANGE, the neighbour nodes will simply discard the received RREQ packets, otherwise, the node will compare D1 and [absolute value of F[S.sub.0]]. If, the node will examine whether it is the destination node or it has a valid route to the destination node, if the node has a valid route, it will send back RREP to the last hop node F, and node F continues to forward the RREP along the reverse routing until the RREP packet arrives at the source node; otherwise, it will update the effective route to the source node, and record the source host, the IP address of the destination host, the serial number of the destination node, the last node F in their own routing tables, then it will forward RREQ sequentially, until the destination node receives RREQ or the intermediate nodes have the valid route to the destination node, the destination node or the intermediate nodes will sent back RREP to the source node by some intermediate nodes, the route is established; if [D.sub.1] > [absolute value of F[S.sub.0]], the node will directly discard RREQ packet.


As shown in Figure 1, the intermediate node F has four neighbor nodes, that is, A, B, E, D. In the routing discovery process of AODV, if they not only do not have the valid route to the destination node, but also they are not the destination nodes, they all can continue to broadcast RREQ packets. In the improved algorithm, first, because that the distance between node E and the routing vector is larger than RANGE, so node E will discard the information packet RREQ; second, although node A, B, D are all within the routing pipe, because the distance between them and the destination node [S.sub.0] is that [absolute value of D[S.sub.0]] > [absolute value of F[S.sub.0]], [absolute value of A[S.sub.0]] < [absolute value of F[S.sub.0]], [absolute value of B[S.sub.0]] < [absolute value of F[S.sub.0]], so only node A and node B can continue to forward RREQ packets.

From Figure 1 we can see, the forwarding nodes in the routing discovery process of AODV are all the nodes within the circular dotted line while the forwarding node of the proposed algorithm are within the area which is together surrounded by the routing pipe, the round dotted line and the arc solid lines and is close to the destination node. In this way, for the mobile Ad Hoc network with a large number of nodes, there is no doubt that the improved route protocol reduce the number of the forwarding nodes, reduce the network load and the energy consumption of the nodes, and increase the network utilization, extend the lifetime of network.

4. The Experimental Simulation

In this paper, we use the network simulator NS2 which is based on the UC Berkeley, and do the experimental simulations for the geometry-based AODV routing protocol (G-AODV). In the same simulation environment, we compare and analyze G-AODV routing protocol and the original AODV routing protocol in the Ad Hoc network.

4.1 The Simulation Environment

In this paper, the network topology of the simulation experiment is a network model which includes 40 nodes, each node randomly is distributed in the large planar area which is 600*600, and each node moves randomly in any direction within the speed of 10m/s.

The process of the simulation uses the data streams of the constant bit rate (CBR), every packet size is 512 bytes, the average sending rate of each node is 10pkts/s. We will set the simulation time 200s. The static time characterize the mobility of the scene, the longer static time shows that the mobility is less. In this paper, before we change the static time, we select the maximum speed of nodes is 10m/s. where, the static time is set to 20, 40, 60, 80, 100, 120, 140, 160, 180 and 200. With the changes of the static time, we observe and analyse the result of routing protocol.

4.2 The Performance Evaluating Indicator

In order to assess the performance of the original AODV and the improved G-AODV, we should utilize some different measurements. We mainly compare the two routing algorithms from the four aspects:

1. The data packet delivering rate: the ratio of the received data packets successfully and the delivered data packets.

2. The network end-to-end delay of network: it refers to the average time that a packet reaches the routing layer of destination node from the source node.

3. The routing overhead: It calculate the ratio of the total number of bytes in all the routing control packets (include RREQ, RREP, REPP) and the number of bytes in all packets.

4. The network load: It refers to the transmitted bytes of this time period and the length of this time period in a particular pair of nodes from the traced file in some time periods.


4.3 The results and analysis of simulation

We use "AODV" to mark the original AODV routing protocol and the improved AODV routing protocol--G-AODV is marked as "G-AODV" in the following diagrams.

1. The network packet delivering rate:

Figure 2 shows the data-packet delivering rate of AODV protocol and G-AODV routing protocols changes with the static time increasing. From the Figure 2 we can see, GAODV routing algorithm has a higher data-packet delivering rate than the traditional AODV routing protocol. This is mainly because in the G-AODV routing algorithm, the number of the forwarding nodes which participate in the routing discovery process of G-AODV routing algorithm are reduced, thus reduce the number of the redundant control packets and the possibility of collision in the network, ultimately the network packet delivering rate is improved.

2. The average end-to-end delay of network:

When calculating the average end-to-end delay, we use the static time as the abscissa, and to observe the average delay of each scene, as shown in Figure 3. We can see that the end-to-end delay of the improved routing algorithm G-AODV is smaller than the original AODV. We all know that the total average end-to-end delay includes two parts: the forwarding delay and the propagation delay. Because the number of the control packets which the node forward in the network are reduced, the total data packet forwarding delay is also reduced correspondingly, in this case, the forwarding delay has less effects on calculating the total average end-to-end delay, so we get the lower end-to-end delay in the simulation experiments.



3. The network load:

Figure 4 shows the network load of AODV protocol and G-AODV routing protocols changes with the static time increasing. From the Figure 4, we can see that as the static time increasing, the network load of G-AODV routing protocol is always lower than AODV routing protocol. This is mainly because the number of the forwarding nodes in the routing discovery process is reduced; this makes that the total number of data packets transmitted in the network decrease, so the network load is also reduced.


4. The routing overhead of network:

From the Figure 4, we can see that the network load of GAODV routing protocol is lower than AODV. From the Fig.5, we can see the routing overhead is also smaller. As is known to all, G-AODV routing protocol limit the number of the forwarding node in the discovery process, the reduced control packets lead to the total network load decreasing, but the reduced control packets change faster than the network load, so the routing overhead of G-AODV also reduce as the number of routing control packets significantly declining.

5. Conclusion

In this paper, on the basis of AODV routing protocol, we propose the improved routing protocol--G-AODV. The algorithm mainly utilizes some geometrical information to reduce the number of the forwarding nodes in the network, and makes the forwarding nodes limited in a local area. In intensive network, G-AODV has better overall performance, as can be seen from the simulation results. It reduces the network overhead and the network load effectively, meanwhile, the packet delivering rate and the end-to-end delay are also better than the original AODV. At present, the proposed routing protocols for Ad Hoc network have their own characteristics and the applying scope, it is still the key to find a routing protocol which can be applied to all various application environments and can be widely accepted.

6. Acknowledgment

The author would like to thank Chongqing Natural Science Foundation under Grant No.2008BB2085&No. 2009BB2081 and the Science and Technology Research Project of Chongqing Municipal Education Commission of China (KJ110504). The Project is also Sponsored in part by the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry.


[1] Latiff, L. A., Fisal, N. (2003). Routing Protocols in Wireless Mobile Ad Hoc Network-A Review. The 9th Asia-Pacific Conference on Communications, p.600-604, Malaysia, IEEE.

[2] Abolhasan, M., Wysocki, T., Dutkiewicz, E. (2004). A review of routing protocols for mobile ad hoc networks, Ad Hoc Networks, 2 (1) 1-22.

[3] Mahdipour, E., Rahmani, A. M., Aminian, E. (2009). Performance Evaluation of Destination-Sequenced Distance-Vector (DSDV) Routing Protocol. IEEE 2009 International Conference on Future Networks, p. 186-190, Washington, DC, USA, IEEE.

[4] Lan. D., Elizabeth, M. et al. (2005). AODV Implemention Design and Performance Evaluation, International Journal of Wireless and Mobile Computing (IJWMC).

[5] Boukerche, A. (2004). Performance Evaluation of Routing Protocols for Ad Hoc Wireless Networks, Mobile Networks and Applications, 9 (4) 333-342.

[6] Tseng, Y. C., Ni, S. Y. (2002). The broadcast storm problem in mobile ad hoc networks, Wireless Networks, 8 (2/3) 153-167.

[7] Cheng, Z., Heinzeiman, W. B. (2005). Flooding strategy for target discovery in wireless networks, Wireless networks, 11(5) 607-618.

[8] Jiang, G. X., Yi, M. (2009). Low overhead on-demand routing protocol for mobile ad hoc networks, Journal of Communications, 30 (7) 27-35, 2009.

[9] Camp, T., Boleng, J., Williams, B. et al, (2002). Performance Comparison of Two Location Based Routing Protocols, In: Proceedings of IEEE Infocom, p. 1678-1687, New York, USA, IEEE.

[10] Li, S., Hong, L. (2010). Algorithm of route discovery based on distance prediction in MANET[J]. Journal of Communications, 31(11) 180-187.

[11] Shin, K., Park, K., Chung, M. et al, (2007). Energy efficient route discovery for mobile HCI in ad hoc networks. in: Springrt-Verlag Lecture Notes in Computer Science, p. 635-644, Heidelberg, ACM.

Chang Su, Lili Zheng, Xiaohai Si, Fengjun Shang

Institute of Computer Science & Technology, Chongqing University of Posts and Telecommunications Chongqing, P. R. China

{changsu, shangfj}, {yunfanyunfan, sixhocean}
COPYRIGHT 2012 Digital Information Research Foundation
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2012 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Su, Chang; Zheng, Lili; Si, Xiaohai; Shang, Fengjun
Publication:Journal of Digital Information Management
Article Type:Report
Date:Apr 1, 2012
Previous Article:Research and practice of characteristic teaching resources sharing and interactive platform.
Next Article:A constrained optimization evolutionary algorithm based on membrane computing.

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |