# Reference Point Group Mobility and Random Waypoint Models in

Authors: Geetha Jayakumar; Gopinath Ganapathi
Journal: Journal of Computer Systems, Networks, and Communications
 (2008)

---

## Abstract

Ad hoc networks are characterized by multihop wireless connectivity,
frequently changing network topology and the need for efficient
dynamic routing protocols plays an important role. We compare the
performance of two prominent on-demand routing protocols for mobile ad
hoc networks: dynamic source routing (DSR), ad hoc
on-demand distance vector routing (AODV). A detailed
simulation model with medium access control (MAC) and
physical layer models is used to study the interlayer interactions and
their performance implications. We demonstrate that even though DSR
and AODV share similar on-demand behavior, the differences in the
protocol mechanisms can lead to significant performance differentials.
In this paper, we examine both on-demand routing protocols AODV and
DSR based on packet delivery ratio, normalized routing load,
normalized MAC load, average end-to-end delay by varying the node
density, network loading, and mobility variations for reference point group mobility and random waypoint models. This
framework aims to evaluate the effect of mobility models on the
performance of mobile ad hoc networks (MANETs) routing
protocols. Our results show that the protocol performance may vary
drastically across mobility models and performance rankings of
protocols may vary with the mobility models used. This effect can be
explained by the interaction of the mobility characteristics with
the connectivity graph properties.


---

## Body

## 1. Introduction

Wireless technologies are without any doubt shaping
the beginning of the new millennium. Cellular networks (2/2.5/3 Generations)
have reached global coverage and wireless LANs are providing high speed internet
access to city center
and hot spot areas. The principle of computing anytime anywhere is becoming reality.
Consequently, there has been tremendous interest recently in the convergence of
wired (fixed) networks and mobile wireless and local wireless access systems
and networks. Beyond 3G (B3G) and 4G concepts have been the very hot subject of much research
and many standardization activities throughout the world. Many B3G/4G-related
technical committees are taking the initiative to produce enhanced proposals of
radio transmission technologies and wireless applications protocols [1].Computer network, traditionally viewed as
infrastructure of a fixed form, has evolved into combinations of wired and
wireless networks to suit today's need of mobile communication. As the mobility
of users continues to increase, a special type of network will be gaining more
and more attention which is mobile ad hoc network. Such research on the capacity of
wireless ad hoc networks and the popular IEEE 802.11 protocol typically assume
the use of omnidirectional antennas at all nodes [2]. Over the past few
years, considerable amount of research addressed the issues, such as, (a)
access, (b) routing, (c) transport layer protocols, (d) quality of service
provisioning, (e) self-organization, and (f) energy management. Recent research
includes understanding the cross-layer protocol interactions and new designs of
such protocols [3, 4].In a mobile ad hoc network, nodes do not rely on any
existing infrastructure. Instead, the nodes themselves form the network and communicate
through means of wireless communications. Mobility causes frequent topology changes
and may break existing paths. A routing protocol should quickly adapt to the
topology changes and efficiently search for new paths. On the other hand, the
limited power and bandwidth resources in mobile ad hoc networks make quick
adaptation very challenging [5].
Nodes will have to forward the network traffic on behalf of other nodes to allow
communication to take place between nodes that are out of each other immediate
radio range. Hence, routing of network traffic becomes a central issue in these
networks. The mobile ad hoc networks are envisioned to support dynamic and rapidly
changing multihop topologies
which are likely to be composed of relatively bandwidth constrained wireless links [6].
A generic framework to
systematically analyze the impact of mobility on the performance of routing protocols
for   MANET has become important. It is necessary to find
out what degree of mobility affects routing protocol performance. Many previous studies have used random waypoint
(RWP) as reference model [7]. Random
waypoint is a simple model that is easy to analyze and implement. This has
probably been the main reason for the widespread use of this model for
simulations. Further, the RWP model is not sufficient to capture some realistic
scenarios. In order to model the movements of nodes in a realistic terrain,
such as a battlefield or rescue operation, some sophisticated mobility models
such as reference point group mobility (RPGM) models find valuable application.In the RWP model, the nodes, that is,
mobile users, move along a zigzag path consisting of straight legs from one
waypoint to the next [8]. Mobility model such as RWP model is described on graphs based on road maps [9].For this purpose, numerous ad hoc routing protocols
have been proposed by the Internet Engineering Task Force (IETF) working group
MANET. These protocols have been evaluated through simulations in network
simulators like NS-2.


## 2. Background

The routing protocols for MANET can be broadly
classified as on-demand/reactive and periodic/proactive protocols. Reactive
routing protocols propagate route updates only when a route to a destination is
required. There are several reactive routing protocols available for ad hoc
networks, including dynamic
source routing (DSR) [10], ad hoc on-demand distance vector (AODV) [11], and so on. Reactive
routing protocols have been demonstrated
to perform better with significantly lower overheads than proactive routing
protocols in many scenarios [12] since they are able to react quickly to
topology changes, yet being able to reduce routing overhead in periods or areas
of the network in which changes are less frequent. In this section, we briefly
discuss the working of both on-demand routing protocols AODV and DSR. Their
respective performances are compared in Section 1. It has also been observed that under a given mobility pattern, routing
protocols like DSR and AODV perform differently.This is possibly because each protocol differs in the
basic mechanisms or “building blocks” it uses. For example, DSR uses route
discovery. To find out how, we need to investigate the effect of mobility on
some of these “building blocks” and how they impact the protocol performance as
a whole. It is necessary to systematically propose a framework to analyze the impact
of mobility on the performance of routing protocols in ad hoc networks. Through
this framework, we illustrate how modeling mobility is important in affecting
routing performance and understanding the mechanism of ad hoc routing protocols.
Our framework mainly focuses on the following aspects: mobility models, the
metrics for mobility and connectivity graph characteristics, the potential
relationship between mobility and routing performance, and the analysis of
impact of mobility on building blocks of ad hoc routing protocols.


### 2.1. Reactive Protocols

In contrast to table-driven routing protocols, all up-to-date routes are not maintained at
every node; instead the routes are created as and when required. When a node
requires a route to the destination, it invokes a route discovery mechanism to
find the path to the destination. The process is completed once a route is
found or all possible route permutations have been examined. Once a route has
been established, it is maintained by a route maintenance procedure until
either the destination becomes inaccessible along every path from the source or
until the route is no longer desired. This section discusses two on-demand
routing protocols.


### 2.2. AODV

AODV (see [11]) is an
improvement on the destination-sequenced distance vector (DSDV). AODV uses an
on-demand approach for finding routes. Since it is an on-demand algorithm, a
route is established only when it is required by a source node for transmitting
data packets and it maintains these routes as long as they are needed by the sources.
AODV uses a destination sequence number, created by the destination, to
determine an up-to-date path to the destination. A node updates its route
information only if the destination sequence number of the current received
packet is greater than the destination sequence number stored at the node. It indicates
the freshness of the route accepted by the source. To prevent multiple broadcast
of the same packet, AODV uses broadcast identifier number that ensures loop freedom
since the intermediate nodes only forward the first copy of the same packet and
discard the duplicate copies. To find a path to the destination, the source
broadcasts a route request (RREQ) packet across the network. This RREQ
contains the source identifier, the destination identifier, the source sequence
number, the destination sequence number, the broadcast identifier, and the time
to live field. Nodes that receive the RREQ find out whether they are the
destination or whether they have a fresh route to the destination, then they
respond to the RREQ by unicasting a route reply (RREP) back to the source node.Otherwise, the
node rebroadcasts the RREQ. When a node forwards an RREQ packet to its
neighbors, it also records in its tables the node from which the first copy of the
request came. This information is used to construct the reverse path for the
RREP packet. AODV uses only symmetric links because the route reply packet
follows the reverse path of route request packet. When a node receives an RREP
packet, information about the previous node from which the packet was received
is also stored in order to forward the data packets to this next node as the
next hop toward the destination. Once the source node receives an RREP, it can
begin using the route to send data packets. The source node rebroadcasts the
RREQ if it does not receive an RREP before the timer expires. It attempts
discovery up to some maximum number of attempts. If it does not discover a
route after this maximum number of attempts, the session is aborted. If the
source moves then it can reinitiate route discovery to the destination. If one
of the intermediate nodes moves then the moved node neighbor realizes the link
failure and sends a link failure notification to its upstream neighbors and so
on till it reaches the source upon which the source can reinitiate route
discovery if needed. The main advantage of AODV is that routes are obtained on demand
and destination sequence numbers are used to find the latest route to the
destination. One of the disadvantages of AODV is that intermediate nodes can
lead to inconsistent routes if the source sequence number is very old and the intermediate
nodes have a higher but not the latest destination sequence number, thereby
causing stale entries. Also multiple route reply (RREP) packets in
response to a single route request (RREQ) packet can lead to heavy
control overhead. Periodic hello messages also lead to unnecessary bandwidth
consumption.


### 2.3. DSR

The key feature
of DSR [10, 13] is the use of source routing. That is, the sender knows the
complete hop-by-hop route to the destination. These routes are stored in a route
cache. The data packets carry the source route in the packet header. When a
node in the ad hoc network attempts to send a data packet to a destination for
which it does not already know the route, it uses a route discovery process
to dynamically determine such a route. Route discovery works by flooding the
network with route request (RREQ) packets. Each node receiving an RREQ
rebroadcasts it, unless it is the destination or it has a route to the
destination in its route cache. Such a node replies to the RREQ with a route
reply (RREP) packet that is routed back to the original source. RREQ and RREP
packets are also source routed. The RREQ builds up the path traversed so far. The
RREP routes itself back to the source by traversing this path backwards, the route carried back by the RREP packet
is cached at the source for future use. If any link on a source route is
broken, the source node is notified using a route error (RERR) packet. The
source removes any route using this link from its cache. A new route discovery
process must be initiated by the source if this route is still needed. DSR
makes very aggressive use of source routing and route caching. No special
mechanism to detect routing loops is needed. Also, any forwarding node caches
the source route in a packet it forwards for possible future use. Several
additional optimizations have been proposed and have been evaluated to be very
effective by the authors of the protocol [14], as described in the following.
(i) Salvaging: an intermediate
node can use an alternate route from its own cache, when a data packet meets a
failed link on its source route. (ii) Gratuitous route repair: a source node receiving an RERR packet piggybacks
the RERR in the following RREQ. This helps cleaning up the caches of other nodes in the
network that may have the failed link in one of the cached source routes. (iii)
Promiscuous listening: when a node overhears a packet not addressed to itself, it checks if the
packet could be routed via itself to gain a shorter route. If so, the node
sends a gratuitous RREP to the source of the route with this new, better
route. Aside from this, promiscuous listening helps a node to learn different routes
without directly participating in the routing process.


## 2.1. Reactive Protocols

In contrast to table-driven routing protocols, all up-to-date routes are not maintained at
every node; instead the routes are created as and when required. When a node
requires a route to the destination, it invokes a route discovery mechanism to
find the path to the destination. The process is completed once a route is
found or all possible route permutations have been examined. Once a route has
been established, it is maintained by a route maintenance procedure until
either the destination becomes inaccessible along every path from the source or
until the route is no longer desired. This section discusses two on-demand
routing protocols.


## 2.2. AODV

AODV (see [11]) is an
improvement on the destination-sequenced distance vector (DSDV). AODV uses an
on-demand approach for finding routes. Since it is an on-demand algorithm, a
route is established only when it is required by a source node for transmitting
data packets and it maintains these routes as long as they are needed by the sources.
AODV uses a destination sequence number, created by the destination, to
determine an up-to-date path to the destination. A node updates its route
information only if the destination sequence number of the current received
packet is greater than the destination sequence number stored at the node. It indicates
the freshness of the route accepted by the source. To prevent multiple broadcast
of the same packet, AODV uses broadcast identifier number that ensures loop freedom
since the intermediate nodes only forward the first copy of the same packet and
discard the duplicate copies. To find a path to the destination, the source
broadcasts a route request (RREQ) packet across the network. This RREQ
contains the source identifier, the destination identifier, the source sequence
number, the destination sequence number, the broadcast identifier, and the time
to live field. Nodes that receive the RREQ find out whether they are the
destination or whether they have a fresh route to the destination, then they
respond to the RREQ by unicasting a route reply (RREP) back to the source node.Otherwise, the
node rebroadcasts the RREQ. When a node forwards an RREQ packet to its
neighbors, it also records in its tables the node from which the first copy of the
request came. This information is used to construct the reverse path for the
RREP packet. AODV uses only symmetric links because the route reply packet
follows the reverse path of route request packet. When a node receives an RREP
packet, information about the previous node from which the packet was received
is also stored in order to forward the data packets to this next node as the
next hop toward the destination. Once the source node receives an RREP, it can
begin using the route to send data packets. The source node rebroadcasts the
RREQ if it does not receive an RREP before the timer expires. It attempts
discovery up to some maximum number of attempts. If it does not discover a
route after this maximum number of attempts, the session is aborted. If the
source moves then it can reinitiate route discovery to the destination. If one
of the intermediate nodes moves then the moved node neighbor realizes the link
failure and sends a link failure notification to its upstream neighbors and so
on till it reaches the source upon which the source can reinitiate route
discovery if needed. The main advantage of AODV is that routes are obtained on demand
and destination sequence numbers are used to find the latest route to the
destination. One of the disadvantages of AODV is that intermediate nodes can
lead to inconsistent routes if the source sequence number is very old and the intermediate
nodes have a higher but not the latest destination sequence number, thereby
causing stale entries. Also multiple route reply (RREP) packets in
response to a single route request (RREQ) packet can lead to heavy
control overhead. Periodic hello messages also lead to unnecessary bandwidth
consumption.


## 2.3. DSR

The key feature
of DSR [10, 13] is the use of source routing. That is, the sender knows the
complete hop-by-hop route to the destination. These routes are stored in a route
cache. The data packets carry the source route in the packet header. When a
node in the ad hoc network attempts to send a data packet to a destination for
which it does not already know the route, it uses a route discovery process
to dynamically determine such a route. Route discovery works by flooding the
network with route request (RREQ) packets. Each node receiving an RREQ
rebroadcasts it, unless it is the destination or it has a route to the
destination in its route cache. Such a node replies to the RREQ with a route
reply (RREP) packet that is routed back to the original source. RREQ and RREP
packets are also source routed. The RREQ builds up the path traversed so far. The
RREP routes itself back to the source by traversing this path backwards, the route carried back by the RREP packet
is cached at the source for future use. If any link on a source route is
broken, the source node is notified using a route error (RERR) packet. The
source removes any route using this link from its cache. A new route discovery
process must be initiated by the source if this route is still needed. DSR
makes very aggressive use of source routing and route caching. No special
mechanism to detect routing loops is needed. Also, any forwarding node caches
the source route in a packet it forwards for possible future use. Several
additional optimizations have been proposed and have been evaluated to be very
effective by the authors of the protocol [14], as described in the following.
(i) Salvaging: an intermediate
node can use an alternate route from its own cache, when a data packet meets a
failed link on its source route. (ii) Gratuitous route repair: a source node receiving an RERR packet piggybacks
the RERR in the following RREQ. This helps cleaning up the caches of other nodes in the
network that may have the failed link in one of the cached source routes. (iii)
Promiscuous listening: when a node overhears a packet not addressed to itself, it checks if the
packet could be routed via itself to gain a shorter route. If so, the node
sends a gratuitous RREP to the source of the route with this new, better
route. Aside from this, promiscuous listening helps a node to learn different routes
without directly participating in the routing process.


## 3. Classification of Mobility Models

In general, the mobility models can be classified
according to the different kinds
of dependencies and restrictions that are considered.(i)
Random based: there are neither dependencies nor any other
restrictions modeled which are similar to RWP model.(ii)
Temporal dependencies: the actual movement of a node is
influenced by the movement of the past.(iii)
Spatial dependencies: the movement of a node is influenced
by the nodes around it, for example,
group mobility such as RPGM model.(iv)
Geographic restrictions: the area in which the node is
allowed to move is restricted.(v)
Hybrid characteristics: a combination of temporal dependencies,
spatial dependencies, and geographic restrictions is
realized [15].


## 4. Models

Random Waypoint Model
The random waypoint mobility model is simple and is widely used to evaluate the
performance of MANETs. The random waypoint mobility model contains pause time
between changes in direction and/or speed. Once a mobile node (MN) begins to move,
it stays in one location for a specified pause time. After the specified pause
time is elapsed, the MN randomly selects the next destination in the simulation
area and chooses a speed uniformly distributed between the minimum speed and
maximum speed and travels with a speedv whose value is uniformly chosen
in the interval (0,Vmax). Vmax is some parameter that can be set
to reflect the degree of mobility. Then, the MN continues its journey toward
the newly selected destination at the chosen speed. As soon as the MN arrives
at the destination, it stays again for the indicated pause time before
repeating the process [16].Reference Point Group Mobility Model (RPGM)
This model is described as another way to simulate
group behavior in [17], where each node belongs to a group where every node follows a logical center (group leader) that
determines the group's motion behavior. The nodes in a group are usually
randomly distributed around the reference point. The different nodes use their
own mobility model and are then added to the reference point which drives them
in the direction of the group. At each instant, every node has a speed and
direction that is derived by randomly deviating from that of the group leader.
This general description of group mobility can be used to create a variety of
models for different kinds of mobility applications. Group mobility as such can
be used in military battlefield communications. One example of such mobility is that a number
of soldiers may move together in a group. Another example is during disaster
relief where various rescue crews (e.g., firemen, policemen, and medical
assistants) form different groups and work cooperatively. The respective
functions of group leaders and group members are described as follows.


### 4.1. The Group Leader

The movement of group leader at time,t, can be represented by motion
vector Vgroupt. Not only it defines the motion of group leader itself, but also it provides the
general motion trend of the whole group. Each member of this group deviates from
this general motion vector Vgroupt by
some degree. The motion vector Vgroupt can be randomly chosen or carefully designed based on certain predefined
paths [18].


### 4.2. The Group Members

The movement of group members is
significantly affected by the movement of its group leader. For each node,
mobility is assigned with a reference point that follows the group movement.
Upon this predefined reference point, each mobile node could be randomly placed
in the neighborhood.Formally, the motion vector of group
member,i, at time t, Vit, can be described as (1)Vit=Vgroupt+RMit, where the motion
vector RMit is a random vector deviated by group
member i from its own reference point. The vector RMit
is an independent identically distributed random process whose length is
uniformly distributed in the interval [0,rmax] (where rmax is maximum allowed distance deviation) and whose direction is uniformly
distributed in the interval [0,2π].Vgroupt is the motion vector for the
group leader; it is also the motion vector for the whole group. RMit is the random deviation vector for
group member i, and the final motion vector of group member i is represented by
vector Vit.With appropriate selection of
predefined paths for group leader and other parameters, the RPGM model is able
to emulate a variety of mobility behaviors.
RPGM model is able to represent various mobility scenarios including the
following.(i)
In-place mobility model: the entire field is divided into several
adjacent regions. Each region is exclusively occupied by a single group. One
such example is battlefield communication.(ii)
Overlap mobility model: different groups with different tasks
travel on the same field in an overlapping manner. Disaster relief is a good
example.(iii)
Convention mobility model: this scenario is to emulate the mobility behavior in the conference. The
area is also divided into several regions while some groups are allowed to
travel between regions.
In RPGM model, the vector RMi indirectly determine how much the motion
of group members deviate from their leader. The movement can be characterized
as follows: (2)|Vmember(t)|=|Vleader(t)|+random()*SDR*max_speed,θmember(t)=θleader(t)+random()*SDR*max_angle (see
[7]), where 0 < SDR, ADR < 1. SDR is the speed deviation ratio and
ADR is the angle deviation ratio. SDR and ADR are used to control the deviation
of the velocity (magnitude and direction) of group members from that of the
leader. By simply adjusting these two parameters, different mobility scenarios
can be generated.Because of the inherent characteristic of spatial dependency between nodes, the RPGM
model is expected to behave differently from the RWP model. We find
that RPGM incurs less link breakage and achieves a better performance for
various routing protocols than RWP model.We observe that the mobility models have various properties and exhibit different
mobility characteristics. As a consequence, we expect that mobility models
behave differently and influence the protocol performance in different ways. Therefore,
to thoroughly evaluate ad hoc protocol performance, it is imperative to use a
rich set of mobility models.
Each model has its own unique and specific mobility characteristics. Hence, a
method to choose a suitable set of mobility models is needed.


### 4.3. Simulation and Performance Metrics

For our scenario-based
experiments, we used the ns-2 simulator which is available as an open source
distribution [19]. For generating the scenarios, we used the mobility scenario
generation tool, BonnMotion. The radio model corresponds to the 802.11 WaveLAN,
operating at a maximum airlink rate of 2 Mbps. The media access control protocol
used is the IEEE 802.11 distributed coordination function (DCF). The traffic
pattern file was generated using “cbrgen.tcl” script, which is provided along
with the standard ns-2 distribution. We used constant bit rate (CBR) traffic
for our simulations.


### 4.4. Metrics

We have selected the packet delivery ratio, average end-to-end
delay, and protocol control overhead as a metric during the simulation in order to
evaluate the performance of the different protocols [20].
(a)
Packet delivery fraction (PDF): this is the ratio of total number of packets successfully
received by the destination nodes to the number of packets sent by the source
nodes throughout the simulation: (3)PDF=numberofreceivedpacketsnumberofsentpackets. This estimate gives us an idea about how successful the protocol is in delivering
packets to the application layer. A high value of PDF indicates that most of
the packets are being delivered to the higher layers and is a good indicator of
the protocol performance.(b)
Normalized routing load (NRL): this is calculated as the ratio between the number of routing
packets transmitted to the number of packets actually received (thus accounting
for any dropped packets): (4)NRL=numberofroutingpacketssentnumberofdatapacketsreceived. This metric gives an estimate of how efficient a routing protocol
is since the number of routing packets sent per data packet gives an idea of
how well the protocol maintains the routing information updated. The higher the
NRL, the higher the overhead of routing packets and consequently the lower the
efficiency of the protocol is.(c)
Average end-to-end delay (AED): this is defined as the average delay in transmission of a
packet between two nodes and is calculated as follows: (5)AED=∑i=0n(timepacketreceivedi−timepacketsenti)totalnumberofpacketsreceived. A higher value of
end-to-end delay means that the network is congested and hence the routing
protocol does not perform well. The upper bound on the values of end-to-end
delay is determined by the application.


## 4.1. The Group Leader

The movement of group leader at time,t, can be represented by motion
vector Vgroupt. Not only it defines the motion of group leader itself, but also it provides the
general motion trend of the whole group. Each member of this group deviates from
this general motion vector Vgroupt by
some degree. The motion vector Vgroupt can be randomly chosen or carefully designed based on certain predefined
paths [18].


## 4.2. The Group Members

The movement of group members is
significantly affected by the movement of its group leader. For each node,
mobility is assigned with a reference point that follows the group movement.
Upon this predefined reference point, each mobile node could be randomly placed
in the neighborhood.Formally, the motion vector of group
member,i, at time t, Vit, can be described as (1)Vit=Vgroupt+RMit, where the motion
vector RMit is a random vector deviated by group
member i from its own reference point. The vector RMit
is an independent identically distributed random process whose length is
uniformly distributed in the interval [0,rmax] (where rmax is maximum allowed distance deviation) and whose direction is uniformly
distributed in the interval [0,2π].Vgroupt is the motion vector for the
group leader; it is also the motion vector for the whole group. RMit is the random deviation vector for
group member i, and the final motion vector of group member i is represented by
vector Vit.With appropriate selection of
predefined paths for group leader and other parameters, the RPGM model is able
to emulate a variety of mobility behaviors.
RPGM model is able to represent various mobility scenarios including the
following.(i)
In-place mobility model: the entire field is divided into several
adjacent regions. Each region is exclusively occupied by a single group. One
such example is battlefield communication.(ii)
Overlap mobility model: different groups with different tasks
travel on the same field in an overlapping manner. Disaster relief is a good
example.(iii)
Convention mobility model: this scenario is to emulate the mobility behavior in the conference. The
area is also divided into several regions while some groups are allowed to
travel between regions.
In RPGM model, the vector RMi indirectly determine how much the motion
of group members deviate from their leader. The movement can be characterized
as follows: (2)|Vmember(t)|=|Vleader(t)|+random()*SDR*max_speed,θmember(t)=θleader(t)+random()*SDR*max_angle (see
[7]), where 0 < SDR, ADR < 1. SDR is the speed deviation ratio and
ADR is the angle deviation ratio. SDR and ADR are used to control the deviation
of the velocity (magnitude and direction) of group members from that of the
leader. By simply adjusting these two parameters, different mobility scenarios
can be generated.Because of the inherent characteristic of spatial dependency between nodes, the RPGM
model is expected to behave differently from the RWP model. We find
that RPGM incurs less link breakage and achieves a better performance for
various routing protocols than RWP model.We observe that the mobility models have various properties and exhibit different
mobility characteristics. As a consequence, we expect that mobility models
behave differently and influence the protocol performance in different ways. Therefore,
to thoroughly evaluate ad hoc protocol performance, it is imperative to use a
rich set of mobility models.
Each model has its own unique and specific mobility characteristics. Hence, a
method to choose a suitable set of mobility models is needed.


## 4.3. Simulation and Performance Metrics

For our scenario-based
experiments, we used the ns-2 simulator which is available as an open source
distribution [19]. For generating the scenarios, we used the mobility scenario
generation tool, BonnMotion. The radio model corresponds to the 802.11 WaveLAN,
operating at a maximum airlink rate of 2 Mbps. The media access control protocol
used is the IEEE 802.11 distributed coordination function (DCF). The traffic
pattern file was generated using “cbrgen.tcl” script, which is provided along
with the standard ns-2 distribution. We used constant bit rate (CBR) traffic
for our simulations.


## 4.4. Metrics

We have selected the packet delivery ratio, average end-to-end
delay, and protocol control overhead as a metric during the simulation in order to
evaluate the performance of the different protocols [20].
(a)
Packet delivery fraction (PDF): this is the ratio of total number of packets successfully
received by the destination nodes to the number of packets sent by the source
nodes throughout the simulation: (3)PDF=numberofreceivedpacketsnumberofsentpackets. This estimate gives us an idea about how successful the protocol is in delivering
packets to the application layer. A high value of PDF indicates that most of
the packets are being delivered to the higher layers and is a good indicator of
the protocol performance.(b)
Normalized routing load (NRL): this is calculated as the ratio between the number of routing
packets transmitted to the number of packets actually received (thus accounting
for any dropped packets): (4)NRL=numberofroutingpacketssentnumberofdatapacketsreceived. This metric gives an estimate of how efficient a routing protocol
is since the number of routing packets sent per data packet gives an idea of
how well the protocol maintains the routing information updated. The higher the
NRL, the higher the overhead of routing packets and consequently the lower the
efficiency of the protocol is.(c)
Average end-to-end delay (AED): this is defined as the average delay in transmission of a
packet between two nodes and is calculated as follows: (5)AED=∑i=0n(timepacketreceivedi−timepacketsenti)totalnumberofpacketsreceived. A higher value of
end-to-end delay means that the network is congested and hence the routing
protocol does not perform well. The upper bound on the values of end-to-end
delay is determined by the application.


## 5. Description of the Scenarios

We consider different scenarios for our experiments,
in which the nodes are distributed over the simulation area. The scenarios
depict varying node densities, link changes, and mobility variations. To
thoroughly study the effect of mobility on MANET protocol performance, we need to
evaluate the protocols over a rich set of mobility models that span the design
space of the mobility metrics. The
scenarios are explained in the following sections.Thereference point group mobility (RPGM) model
[21] is used for modeling the scenario. In RPGM model, a cluster of nodes communicates in groups.
The velocity and direction of nodes within the group are determined by a “group leader” or
reference point. Since the group leader mainly decides the mobility of
group members, group mobility pattern is expected to have high spatial
dependence for small values of SDR and ADR. We define the parameters in this mobility model as shown in
Table 1.Table 1
Parameters for RPGM and random waypoint model-mobility variations.
ParametersValuesValuesMobility modelRPGMRandom waypointSimulation area1000 m× 1000 m1000× 1000Minimum node speed1 m/sUniform speed# of nodes2020Traffic typeCBR (constant bit rate)CBRPacket size512 bytes512 bytesConnection rate10 pkts/s10 pkts/sPause time25 s25 sNumber of connections55Maximum node speed10–15–20–25 m/s10–15–20–25 m/sSimulation time200 s200Distribution of nodes2 in each group 10 groups—ProtocolsAODV, DSRAODV, DSRProbability of group change0.05—Maximum distance to group center100 m—Standard deviation2.0—Inrandom waypoint model, a mobile node chooses a random destination at every instance and moves toward it
with a speed uniformly distributed [0,Vmax],
where Vmax is the maximum allowable speed for a node. After reaching the
destination, the node stops for a duration defined by the “pause time” parameter.
After this duration, it again chooses a random destination and repeats the
whole process again until the simulation ends.


### 5.1. Mobility Variations Results

The analysis of Figure1(a) shows that AODV and DSR
have similar performance outputs. From Figure 1(b), we infer that routing overheads
generated by AODV is greater than DSR. This can be attributed to more routing
updates needed in AODV. DSR uses source routing and also caches some routing
entries. The normalized medium access control (MAC) load for AODV is found to
be less when compared to DSR. This is because route errors (RERRs) (Figure 1(c))
are handled
differently in each protocol. RERRs are unicast in DSR and therefore contribute
to additional MAC overhead like route replies (RREPs). In AODV, RERRs are broadcast
like route requests (RREQs) and hence are less expensive. Consequently, when
the MAC overhead is factored, DSR is found to generate higher overall network
load than AODV in all scenarios despite having less routing overhead. The end-to-end
delay of AODV is less when compared to DSR (Figure 1(d)).(a)(b)(c)(d)


### 5.2. Node Density Results

In the second
experiment on RPGM model, we try to find the performance aspect when the node
density is varied within a fixed map area. The node density is incrementally adjusted
from 20–100 nodes within
the same map area of1000×1000 m. The simulation parameters are shown in Table 2. From Figure 2(a), we infer that DSR and AODV have similar results. The
routing overhead remains relatively low for DSR whereas for AODV it increases
tremendously. The network delay of AODV is less when compared to DSR.Table 2
Parameters for RPGM and random waypoint-node density variations.
ParametersValuesValuesMobility modelRPGMRandom waypointSimulation area1000 m× 1000 m1000 m× 1000 mMinimum node speed1 m/sUniform speedNumber of nodes20, 50, 80, 10020, 50, 80, 100Traffic typeCBR (constant bit rate)CBRPacket size512 bytes512 bytesConnection rate20 pkts/s20 pkts/sPause time20–30 s25 sNumber of connections55Maximum node speed10 m/s10 m/sSimulation time200 s200 sProtocolsAODV, DSRAODV, DSRDistribution of nodes2 in each group 10 groups—Probability of group change0.05—Maximum distance to group center100 m—Standard deviation2.0—(a)(b)(c)(d)


### 5.3. Network Loading Results

In the third set of
experiments of RPGM, we try to find the routing performance aspect when the
offered load increases. To do this, we increase the average connection load
offered by each connection starting at 20–60 pkts/s. The
same parameters are used, such as the type of traffic is constant bit rate (CBR)
and the nodes are pumping data as shown in Table3. Figure 3(a) shows that the
PDF of routing protocols have very close performance results when the network
loading is high. Overall, the protocols experience a drop in packet delivery
ratio as network loading increases. Figure 3(b) shows that DSR has less
overhead when compared to AODV. Figure 3(c) shows that DSR has a high-normalized
MAC load when compared to AODV. We see from Figure 3(d) that AODV has lowest
network latency in the RPGM model when network loading increases compared to
DSR.Table 3
Parameters for RPGM and random waypoint-network loading.
ParametersValuesValuesMobility modelRPGMRandom waypointSimulation area1000 m× 1000 m1000 m× 1000 mMinimum node speed1 m/sUniform speedNumber of nodes2020Traffic typeCBR (constant bit rate)CBRPacket size512 bytes512 bytesConnection rate20–30–40–50–60 pkts/s20–30–40–50–60 pkts/sPause time20–30 s25 sNumber of connections55Maximum node speed10 m/s10 m/sSimulation time200 s200 sDistribution of nodes2 in each group 10 groups—Probability of group change0.05—Maximum distance to group center100 m—Standard deviation2.0—(a)(b)(c)(d)


## 5.1. Mobility Variations Results

The analysis of Figure1(a) shows that AODV and DSR
have similar performance outputs. From Figure 1(b), we infer that routing overheads
generated by AODV is greater than DSR. This can be attributed to more routing
updates needed in AODV. DSR uses source routing and also caches some routing
entries. The normalized medium access control (MAC) load for AODV is found to
be less when compared to DSR. This is because route errors (RERRs) (Figure 1(c))
are handled
differently in each protocol. RERRs are unicast in DSR and therefore contribute
to additional MAC overhead like route replies (RREPs). In AODV, RERRs are broadcast
like route requests (RREQs) and hence are less expensive. Consequently, when
the MAC overhead is factored, DSR is found to generate higher overall network
load than AODV in all scenarios despite having less routing overhead. The end-to-end
delay of AODV is less when compared to DSR (Figure 1(d)).(a)(b)(c)(d)


## 5.2. Node Density Results

In the second
experiment on RPGM model, we try to find the performance aspect when the node
density is varied within a fixed map area. The node density is incrementally adjusted
from 20–100 nodes within
the same map area of1000×1000 m. The simulation parameters are shown in Table 2. From Figure 2(a), we infer that DSR and AODV have similar results. The
routing overhead remains relatively low for DSR whereas for AODV it increases
tremendously. The network delay of AODV is less when compared to DSR.Table 2
Parameters for RPGM and random waypoint-node density variations.
ParametersValuesValuesMobility modelRPGMRandom waypointSimulation area1000 m× 1000 m1000 m× 1000 mMinimum node speed1 m/sUniform speedNumber of nodes20, 50, 80, 10020, 50, 80, 100Traffic typeCBR (constant bit rate)CBRPacket size512 bytes512 bytesConnection rate20 pkts/s20 pkts/sPause time20–30 s25 sNumber of connections55Maximum node speed10 m/s10 m/sSimulation time200 s200 sProtocolsAODV, DSRAODV, DSRDistribution of nodes2 in each group 10 groups—Probability of group change0.05—Maximum distance to group center100 m—Standard deviation2.0—(a)(b)(c)(d)


## 5.3. Network Loading Results

In the third set of
experiments of RPGM, we try to find the routing performance aspect when the
offered load increases. To do this, we increase the average connection load
offered by each connection starting at 20–60 pkts/s. The
same parameters are used, such as the type of traffic is constant bit rate (CBR)
and the nodes are pumping data as shown in Table3. Figure 3(a) shows that the
PDF of routing protocols have very close performance results when the network
loading is high. Overall, the protocols experience a drop in packet delivery
ratio as network loading increases. Figure 3(b) shows that DSR has less
overhead when compared to AODV. Figure 3(c) shows that DSR has a high-normalized
MAC load when compared to AODV. We see from Figure 3(d) that AODV has lowest
network latency in the RPGM model when network loading increases compared to
DSR.Table 3
Parameters for RPGM and random waypoint-network loading.
ParametersValuesValuesMobility modelRPGMRandom waypointSimulation area1000 m× 1000 m1000 m× 1000 mMinimum node speed1 m/sUniform speedNumber of nodes2020Traffic typeCBR (constant bit rate)CBRPacket size512 bytes512 bytesConnection rate20–30–40–50–60 pkts/s20–30–40–50–60 pkts/sPause time20–30 s25 sNumber of connections55Maximum node speed10 m/s10 m/sSimulation time200 s200 sDistribution of nodes2 in each group 10 groups—Probability of group change0.05—Maximum distance to group center100 m—Standard deviation2.0—(a)(b)(c)(d)


## 6. Conclusion

(1)
In this study, analysis has been made on the
impact of mobility pattern on routing performance of mobile ad hoc network in a
systematic manner.(2)
It has been observed that the mobility pattern
influences the performance of MANET routing protocols. There is a very clear
trend between mobility metric, connectivity, and performance.(3)
It has been observed that with similar average
spatial dependency when the relative speed increases, the link duration
decreases and hence the routing overhead increases and throughput decreases.(4)
With similar average relative speed, it is found
that spatial dependence increases and the link duration increases and therefore,
the throughput increases and the routing overhead decreases.(5)
It has been observed that DSR and AODV achieve
the highest throughput and least overhead with RPGM when compared to  RWP
mobility models. This is because with similar relative speed, between random waypoint
and RPGM, high degree of spatial dependence for RPGM means higher link duration
and correspondingly higher path duration, which in turn will result in higher
throughput and lower routing overhead.(6)
RWP model is insufficient to capture the following mobility
characteristics such as temporal dependence and spatial dependence. This
reduces the throughput when compared to RPGM.(7)
From the results, it is analyzed that AODV has
better throughput and less delay in RPGM  model when
compared to RWP model. For circumstances such as military
operation, AODV may emerge as a better choice.(8)
Thus, it is necessary to conclude that
relative rankings of the protocols may vary with the mobility model used. This
clearly shows that mobility pattern influences the connectivity graph which in turn
influences the protocol performance.



---

*Source: 860364-2009-02-16.xml*