A Simulation Study on the Impact of Mobility Models on Routing Protocol Performance With

Unidirectional Link Presence

Megat Zuhairi1,2 1Systems and Networking Section

Universiti Kuala Lumpur Kuala Lumpur, 50250. Malaysia megatfarez@miit.unikl.edu.my

David Harle2 2Department of Electronics & Electrical Engineering

University of Strathclyde Glasgow, G1 1XW, United Kingdom

{megatfarez, d.harle}@eee.strath.ac.uk

I. INTRODUCTION A network of mobile nodes communicating via message

relaying technique without the need of a fixed infrastructure is known as a Mobile Adhoc Network (MANET). The lack of infrastructure means that routing decisions to be distributed among all participating nodes, and thus connectivity between nodes is extremely an important factor. Since links are radio signals, connectivity is heavily dependent on the signal to noise ratio (SNR), the transmission power, propagation delay, nodes mobility and etc. Such properties vary from one node to another. As a result, links are then asymmetric in nature and communication between source and destination node pairs may follow paths which are in fact unidirectional. Nevertheless, many proposed schemes ignore this issue and simply assume that all nodes are homogeneous, i.e. possess

similar characteristics. As a consequence, in real life situations such schemes may not perform as effectively as hoped. A substantive amount of research has been done, which investigates the use of unidirectional links and removing the assumption of an inherent symmetrical network. The results indicate there is potential gain in terms of network performance [1][2][3][4][5].

In addition, an important component which affects link connectivity is the node’s mobility pattern. The Random Way Point (RWP) [6] mobility model provides a simple method for nodes to randomly select destination. Nodes then move to that target with a constant speed chosen uniformly and randomly between a minimum and a maximum speed. However, this model is not realistic. In reality, a person in a building, at park, and shopping area generally does not move in a random fashion. In most cases, they rather follow a well defined path with speed and direction that is influenced by their past speed and direction. For instance, a moving vehicle accelerates and turns, which is dependent on its previous speed and direction. Therefore, sharp turns and sudden stops are not likely to occur. Previous research has shown that the choice of such model may be detrimental to the outcome drawn [7]. To obtain credible results, we evaluate the proposed scheme in further more realistic mobility models, which are Gauss Markov [8] and Reference Point Group Mobility (RPGM) [9] model and results obtained are compared to those obtained when using a RWP model.

The remainder of the paper is organised as follows: In Section II, an overview of the routing protocols that support unidirectional link is presented. Section III discusses the mobility model used. The proposed protocol is presented in Section IV. Evaluation methodology and simulation results are presented in Section V. Finally, Section VI concludes this paper.

II. OVERVIEW OF SCHEMES FOR ROUTING OVER UNIDIRECTIONAL LINK

A wide variety of routing protocols have been proposed for MANETs, however many simply ignore the presence of unidirectional links in the networks. As such, the implementation of these schemes often exhibits connectivity

This research work is jointfunded by MARA and Universiti Kuala Lumpur, Malaysia.

335978-1-61284-663-7/11/$26.00 ©2011 IEEE ICOIN 2011

issues, affecting network performance metrics such as packet delivery ratio, endtoend delay, and routing load. Ondemand routing protocols, such as Reverse Adhoc On Demand Distance Vector (RAODV) [10] and Dynamic Source Routing (DSR) [11] discover routes by using twoway independent flooding to find forward and reverse routes successively. This approach effectively avoids unidirectional links but results show that they incur high routing overheads; almost double that associated with single way flooding.

Venugopalan et al. [12] introduce a framework called Bidirectional Routing Abstraction (BRA) that provides a bidirectional abstraction of an asymmetric network to the routing protocol. In this technique, the scheme actively discovers and maintains reverse paths for unidirectional links. The core is an algorithm called Reverse Distributed BellmanFord Algorithm (RDBFA) that searches for reverse routes in a bounded area around each node. The proposed scheme is able to improved connectivity between nodes and provides reverse route forwarding for unidirectional links.

Ko et al. [13] introduce an Early Unidirectional Link Detection (EUDA) scheme, a proactive method to detect unidirectional links. An estimated distance towards the sender is computed using information carried within a route request (RREQ) packets, e.g., transmitting power (Pt) of the sender, SNR threshold, receiver threshold (RXThresh) and total noise. Based on the estimated distance, the receiver node could determine if the link facing the sender is unidirectional. Although simulation results show improved performance, routing load is increased due to additional field requirements in control packets. Nonetheless, this scheme may only be suitable in a network with low nodes mobility.

In other research [3], the authors propose a reverse route search strategy to bypass the unidirectional links. Routes are created only via bidirectional links over several multipaths. Every node maintains multiple reverse paths in its routing table. When a route reply (RREP) packet fails to be delivered due to unidirectional link, the corresponding reverse path is erased and the RREP is retried along alternative reverse paths. If all alternative routes have been exhausted, the search backtracks to the previous hop and the same process is repeated until either one or more bidirectional paths are found. This technique is reliable but takes a significant time to discover a route and generates large link layer overheads.

In this paper, we present an improved scheme to our previous work, Dynamic Reverse Route AODV (DRAODV) [14]. It provides a more relaxed and efficient way for an ondemand routing protocol to support unidirectional links.

III. MOBILITY MODEL This section discusses the mobility models used in the

simulation experiment.

A. Random Waypoint Mobility Model In RWP, node behaviour e.g., current speed and direction

are not influenced by its past value. At initial phase, the nodes are randomly placed in bounded area. Each node is independent of other nodes in the network. Node chooses its mobility pattern based on random number, where a target is

determined as its next movement location. The velocity at which the node moves is determined by selecting uniformly a random number between the intervals defined between maximum speed (Vmax), and minimum speed (Vmin). A maximum pause time may be selected to introduce pause between turns. The node moves from one place to another in a straight line, where sharp turn may occur frequently.

B. GaussMarkov Mobility Model The GaussMarkov mobility model is proposed to

overcome the drawbacks of RWP. It is perhaps a more realistic model, where nodes determine their next vector to future location based on past speed and direction. Nevertheless, Gauss Markov model is not particularly common in simulation studies. This is due to its complexity in computation of nodal movement which means it is larger size of mobility model compared to RWP. To define a Gauss Markov mobility model, consider nodes placed in random locations in the network. The node is initially assigned with a mean speed and mean direction to determine future node movement. At every predetermined time interval, the node computes its next movement based on past speed and direction along with different seed to provide certain degree of randomness. The value of speed and direction at the nth instance can be calculated by the equation 1 and 2:

1)1()1( 2

1 −−+−= − nxnn ssss ααα (1)

1)1()1( 2

1 −−+−+= − nxnn dddd ααα (2)

The instance of past speed ( 1−ns ) and past direction

( 1−nd ) at ( 1−n )th time interval influence the computation

of current speed ( ns ) and direction ( nd ) where 0 ≤ α ≤ 1. The value of α = 0 sets the mobility to be completely random whereas α = 1 generate nodes with linear mobility. The parameters s and d are constants representing the mean value of speed and direction as ∞→n ; where

1−nxs and

1−nxd are random variables from Gaussian distribution. In addition, a node’s next location is calculated based on the current location, speed and direction of movement. The following equations compute node location at nth time interval based on nodes position at (n1)th time interval:

111 .cos −−− += nnnn dsxx (3)

111 .sin −−− += nnnn dsyy (4)

C. Reference Point Group Mobility Model The RPGM model is based on the analysis that group

motion occurs frequently in MANETs. This model may represent the group movement of several rescue teams in a

336

disaster area such as earthquake, where each team movement is directly associated with the group leader movement.

The RPGM is a different entity compared to RWP and Gauss Markov. In this model, individual node movement is influenced by the group movement pattern. Nodes are clustered into groups and their random speed (Vnode(t)) and random direction (θnode(t)) revolve around a predefined individual reference point, which depends on the group motion vector (Vgroup(t), θgroup(t)). In order to control the deviation value of individual node’s speed and direction, a speed standard deviation (SSD) and angle standard deviation (ASD) must be defined. Thus the nodes movement can be calculated as follows:

max**.|||| VSSDrandVV groupnode += (5)

max**.|||| θθθ ASDrandgroupnode += (6) Vmax and θmax is the maximum limit of allowable speed

and turning angle for each node.

IV. OVERVIEW OF PROPOSED SCHEME This section first explains bidirectional route construction

in reactive based routing protocols. Then, their operation over unidirectional links is then explained. Finally, the proposed scheme is presented.

A. Bidirectional link construction In a reactive ondemand routing protocol e.g., AODV,

route construction typically is formed via bidirectional and symmetrical paths. Initially, the source node starts a route discovery by networkwide broadcast RREQ packet to the network. Intermediate nodes relay this message and record information obtained from RREQ message into their cache and routing table. Duplicate packets are simply discarded to minimize routing overhead and to avoid routing loops. Upon reception of the first RREQ packet, destination node sends a RREP packet, which will traverse back along the forward route whilst creating the reverse route. Analogous to forward path construction, when receiving RREP packets, each node updates its routing table with fresh information towards the destination.

B. Operation in the presence of unidirectional links In ideal case, where all links in the network are

symmetrical and bidirectional, ondemand routing protocol can be guaranteed to establish route with shortest hop and lowest delay. However, in the presence of unidirectional links, routing path construction may cause suboptimal network performance. For instance, in a sparse network with high number of unidirectional links, the chances of setting up forward route through unidirectional links can be very high. As a result, a RREP packet may not be able to reach the source using the reverse of the route created by RREQ. Refer to Figure 1, where node A is the source and node G is destination. Assuming RREQ packet from A reaches G via path ABEG.

Figure 1. Unidirectional link in MANET

The link (BE) is unidirectional, pointing to node E. Assuming the nodes are moving at a relatively low speed, route discovery will fail to construct a reverse route from G to A. Node E is able to receive packets from B but not vice versa, even though E has established a reverse route with B as the next hop candidate to reach A. Further attempts of RREQ broadcast by source will likely produce a similar result, hence increasing overall routing overhead.

Routing protocol such as AODVBlacklist [15] which implements a mechanism to avoid unidirectional link may be able to detect such link. Using network layer acknowledgement (ACK), each RREP packet received by node is returned with ACK to the sender. For instance, in Figure 1, as soon as node E transmits RREP to next hop B, it expects an immediate reply of ACK packet. However, upon a failure to receive ACK, node E will cache B in its blacklist set and remove the current entry from its routing table towards B. The system then waits for further attempt of RREQ discovery by source A. Node E, upon receiving another fresh copy of RREQ from node B, will discard it as node B has been blacklisted. This allows forward route to be constructed via a different path e.g. ACFG.

C. The backup routing strategy In light of the deficiencies of current solutions to the

unidirectional links problem, we propose a new scheme that computes an alternative path during RREQ instead of spontaneous reactive method using local broadcast mechanism [14]. As such, in the event of blocked reverse route, nodes may quickly recover lost RREP transmission and redirect them along the alternative path. The proposed idea is based on backup route table strategy which is rather common in ondemand routing protocol implementation. Based on simulation investigation, we have observed high RREQ packets generated during initial phase of route path construction. Most of these packets are simply discarded because they are denoted duplicate. Nevertheless duplicate packet could be utilised, as they may offer alternative path facing in the direction of the source. For instance in multipath routing, e.g. AOMDV [16], the scheme utilises redundant packets to construct multiple path to destination node. In the proposed scheme, we introduce a similar technique; however, unlike AOMDV, only a single routing path is maintained throughout communication.

To detect unidirectional links, the proposed scheme relies on network layer ACK. When a node discovers that a link is unidirectional by the absence of ACK packet, the node immediately switches to backup route table and lookup for alternative path to the source node. This technique benefits from RREQ broadcast discovery phase and, thus, does not

G

E

F

D

B

C

A

337

G

E

F

D

B

C

A

incur additional cost. The mechanism passively monitors each RREQ received. If a redundant packet is detected and the backup route table is empty, the node records the next hop information. Otherwise, it will be discarded. In addition, all duplicate packets are not forwarded to reduce network congestion. The alternative path is then kept for RREP_WAIT_TIME threshold, which is the duration a source node waits for a reply from destination node. To illustrate this idea, consider the scenario in Figure 2. Upon route discovery completion, each node will at least have one backup path pointing to source node A, resulting in a partial mesh structure. Table I and II show the routing entry for the primary and backup routing table respectively.

Figure 2. The primary and backup path

TABLE I. PRIMARY ROUTING TABLE

A B A A 1 C A A 1 D A B 2 E A B 2 F A C 2 G A E 3

TABLE II. BACKUP ROUTING TABLE

A B A C 2 C A B 2 D A C 2 E A D 3 F A D 3 G A F 3

At destination node G, when the first copy of RREQ is

received, the node will unicast RREP packets to node E along with RREP_NO_FLAG bit set. A copy of RREP packet is recorded prior to RREP transmission, which will be used for retransmission if the primary RREP forwarding fails. At an intermediate node, e.g. node E, the RREP content is checked against its primary routing table, where node B is found to be the next hop towards node A. Node E sends RREP to node B and waits for ACK packet. If ACK is not received within the time defined by ACK_WAIT_TIME (0.5 seconds), Node E caches B as an unreachable node. Node E then immediately consults the backup routing table and, if an entry is found, the RREP copy with flag set to ALT is retransmitted along the alternative path while the entry in the primary routing table is being removed. The recovered

RREP packet should exactly be similar to the lost RREP packet, thus containing same details (e.g. destination sequence number, route lifetime, timestamp, etc.). The source node A, upon receiving the RREP packet with flag set to ALT, will need to reconstruct the forward path. It propagates a REPAIR packet, unicast downstream towards the destination where details such as hop count and sequence number are updated along the forward path.

In this scheme, a path between the source and the destination is guaranteed to be created on first route discovery if there are sufficient alternative routes to complete the route construction. In a worst case scenario, where a reverse route could not be established via primary and alternative route, a subsequent RREQ broadcast is made by source node A until the maximum RREQ_RETRIES is reached.

V. EVALUATION METHODOLOGY AND SIMULATION To quantify the proposed scheme’s performance, we

compare it to AODV with blacklist mechanism (AODVBL) and DRAODV. As mentioned earlier, these schemes are considered using three different mobility models with maximum node speed of 12 m/s. To study the routing performance in network scenarios with unidirectional links presence, 5 set of nodes are assigned with reduced transmission range; only one group of nodes containing all bidirectional links. To do this, the default transmission range of 250m is reduced to 125m, which then is randomly assigned to the nodes in the network. Each set contains different number of unidirectional links. Table III shows the ratio of unidirectional links contains in each set.

TABLE III. RATIO OF UNIDIRECTIONAL LINKS IN EACH SET

Number of unidirectional links (%) 0 10 20 30 40 50

To ensure consistency, the same set of protocol

configuration parameters are used for all sets of experiment, given by Table IV.

TABLE IV. CONFIGURATION PARAMETERS OF MOBILITY MODELS

Number of nodes 50 50 50

Update frequency n.a. 2.5 s n.a.

Angle std deviation n.a. 45o n.a.

Speed std deviation n.a. 1.5 m/s n.a.

Maximum pause 20 s n.a. 20 s Number of Groups (2 nodes per group) n.a. n.a. 5 groups

Maximum distance n.a. n.a. 50 m

Uniform speed Yes No No

Cut off time 01000 s 01000 s 01000 s

Primary path Backup path

338

A. Traffic and Mobilty Models A constant bit rate (CBR) traffic connection using User

Datagram Protocol is used to simulate network load. Each CBR source generates a constant size packet (512 bytes) at a rate of 10 packets per second. The number of CBR connections between randomly chosen sourcedestination pairs is set to 10. Also, the CBR connection starttime is assigned randomly. To measure the performance with varying nodal mobility, 6 different node speeds are generated for each mobility model shown by Table IV. NS2 [17] and BonnMotion [18] provides scripts to generate these models. The experiments are simulated for 500 seconds and each data point are iterated and averaged over 20 runs. The simulated area is set to 1000 x 1000 m2.

B. Performance Metrics We consider two key performance metrics:

1) Packet delivery ratio (PDR); the ratio of number of packets delivered to destination to those generated by sources.

2) Normalised Routing Load (NRL); defined as the number of routing packets sent and forwarded per data packet.

C. Simulation Results The PDR performance at maximum node speed of 12 m/s

is shown in Figures 3, 4 and 5. Varying performance of routing protocols is observed from each mobility model. The RWP model, in Figure 4 has resulted in outstanding performance for the proposed scheme compared to other mobility models. On average, the proposed scheme’s PDR is increased as much as 6% as compared to DRAODV. On the other hand, the Gauss Markov model, illustrated in Figure 3, shows a gradual drop in routing performance, consistent with the increasing number of unidirectional links. The simulation outcome from using RPGM is surprisingly low, even at relatively low nodal speeds, i.e. 0m/s, 4m/s and 8m/s. The results however are not shown due to space constraints. As illustrated in Figure 5, PDR drops by as much as 20 points even without unidirectional links presence. The reason may be due to group motion behaviour. These nodes are not scattered randomly but rather clustered in groups. Within the group, nodes move randomly but are bounded by region defined by the group leader which acts as a reference point. As a result intragroup communication becomes less effective, resulting in poor routing performance; regardless, the proposed scheme show advantage.

Figure 6, 7, and 8 shows the NRL. Again, these figures clearly show the difference in terms of routing load observed from each mobility model. In Figure 6, the proposed scheme shows extreme reduction in terms of NRL as compared to RAODV and AODVBL. The effect of twoway flooding and blacklisting entry could be the reason for such increase. In addition, the proposed scheme has shown a similar performance when used with RWP, illustrated by Figure 7. And finally, as expected, all schemes perform moderately when tested with RPGM model, shown by Figure 8.

Figure 3. PDR with Gauss Markov Model

Figure 4. PDR with RWP Model

Figure 5. PDR with RPGM model

Figure 6. NRL with Gauss Markov model

339

Figure 7. NRL with RWP model

Figure 8. NRL with RPGM model

VI. CONCLUSION This contribution of this paper is twofold. First we

proposed a scheme to utilise duplicate packets to advantage and construct alternative path at each node during route request flooding. The route discovery incurs a huge amount of link bandwidth and additional routing overhead. We observed that many of the RREQ packets are simply discarded. These packets however, may contain alternative path pointing to the source. Hence, they may assist in reverse route construction. RREP packet drop will possibly cause another round of RREQ flooding; therefore when alternative paths are made available to these nodes, the success of RREP packet delivery may increase. This has been shown by the simulation results. The second contribution investigates the impact of mobility model on routing protocols performances i.e., PDR and NRL. To our expectation, the performances vary significantly amongst mobility models. In particular, all routing protocols, including the proposed scheme, shows less impressive performance when used with RPGM model. Nonetheless, the proposed scheme has shown promising results under reasonable mobility condition.

In conclusion, this shows that the selection of mobility models affects the applicability of the results obtained from the study. Generally, it is not sufficient to evaluate the performance of a routing protocol based only on a single

mobility model. The RWP model gives rather random movement with uniform speed, and it may cause higher connection rate and less route breaks in a confined area. In contrast, the Gauss Markov model gives some realistic movement with predictable speed and turning angle. A node could moves and avoids making connection in a considerable longer time leading to more frequent route breaks.

REFERENCES [1] Jorjeta Jetcheva and David Johnson , “Routing characteristics of ad

hoc networks with unidirectional links,” IEEE ,2006. [2] Huda Al Amri, Mehran Abolhasan, and Tadeusz Wysocki

“Scalability of MANET routing protocols for heterogeneous and homogenous networks,” in Journal of Computer and Electrical Engineering, 2009.

[3] Mahesh Marina and Samir Das, “Routing Performance in the Presence of Unidirectional Links in Multihop Wireless Networks,” MOBIHOC 2002.

[4] Tomonori Asano, Hiroyuki Unoki, and Hiroaki Higaki, “LBSR: Routing Protocol for MANETs with Unidirectional Links,” IEEE 2004.

[5] Shinsuke Terada, Takumi Miyoshi, and Hiroaki Morino, “Adhoc routing protocols with flooding control using unidirectional links,” International Symposium on Personal Indoor and Mobile Radio Comm., 2007.

[6] Camp Tracy, Boleng Je, and Davies Vanessa, “A Survey of Mobility Models for Adhoc Network Research” Wireless Communication and Mobile Computing : Special issue on Mobile Adhoc Networking Research Trends and Applications 2002.

[7] Jungkeun Yoon, Mingyan Liu, Brian Noble, “Random Waypoint Considered Harmful”, 22nd INFOCOM Conference 2003.

[8] Liang Ben and Haas Zygmunt, “Predictive distancebased mobility management for PCS networks” Proc. of the IEEE Infocom 1999.

[9] Hong Xiaoyan, Gerla Mario, Pei Guangyu and Chiang ChingChuan, “A Group Mobility Model for Adhoc Wireless Networks” Proc. of the ACM Int. Workshop on Modelling and Simulation of Wireless and Mobile Systems (MSWiM) 1999.

[10] Chonggun Kim, Elmurod Talipov, and Byoungchul Ahn, “A Reverse AODV Routing Protocol in Adhoc Mobile Networks,” Emerging Directions in Embedded and Ubiquitous Computing, 2006.

[11] David Johnson, YihChun Hu and David Maltz, “The Dynamic Source Routing Protocol for Mobile Adhoc Networks for IPV4”, RFC 4728, Feb 2007.

[12] Venugopalan Ramasubramanian and Daniel Mossé, "BRA: A Bidirectional Routing Abstraction for Asymmetric Mobile Adhoc Networks" IEEE/ACM Transactions on Networking Vol 16 No 1 2008.

[13] YoungBae Ko, SungJu Lee, and JunBeom Lee, “Adhoc Routing with Early Unidirectionality Detection and Avoidance,” Personal Wireless Communication, 2004.

[14] Megat Zuhairi and David Harle, “Dynamic Reverse Route in Adhoc on Demand Distance Vector Routing Protocol” 6th International Conference on Wireless and Mobile Communications (ICWMC) 2010.

[15] Charles Perkins, Elizabeth BeldingRoyer, and Samir Das, “Adhoc on Demand Distance Vector (AODV) Routing“, IEEE RFC 3561, Jul, 2003.

[16] Mahesh Marina and Samir Das, “On Demand Multipath Distance Vector Routing in Adhoc Networks”, 9th Int. Conference on Network Protocols 2001.

[17] The Network Simulator – NS2 [Online]. Avaliable: www.isi.edu/nsnam/ns

[18] BonnMotion Mobility Scenario Tool. [Online]. Available: www.cs.unibonn.de/IV/BonnMotion/

340