Informatica 34 (2010) 189-78 189
A Simulation Study on the Impact of Mobility Models on the Network Connectivity, Hop Count and Lifetime of Routes for Ad hoc Networks
Natarajan Meghanathan
Department of Computer Science
Jackson State University
Jackson, MS 39217, USA
E-mail: natarajan.meghanathan@jsums.edu
Keywords: mobile ad hoc networks, vehicular ad hoc networks, mobility models, route lifetime, hop count, connectivity, simulation
Received: September 23, 2009
The high-level contribution of this paper is a simulation-based analysis of the network connectivity, hop count and lifetime of the routes determined for ad hoc networks under the following four mobility models: Random Waypoint model, Gauss-Markov model, City Section model and the Manhattan model. Two kinds of routes are determined: routes with the minimum hop count and routes with the longest lifetime. Extensive simulations have been conducted for different conditions of network density and node mobility for each of the four mobility models and also for different values of the degree of randomness parameter for the Gauss-Markov mobility model. We arrive at rankings of the mobility models with respect to network connectivity, hop count of minimum hop routes, lifetime of minimum hop routes, lifetime of stable routes and the hop count of stable routes. We also observe a route lifetime-hop count tradeoff for all the four mobility models. The general trend of the results is: the more realistic and constrained is a mobility model, the larger is the number of hops in the minimum hop routes and smaller is the lifetime of the stable routes determined under the mobility model.
Povzetek: Opisana je analiza mrež s štirimi modeli mobilnosti: Random Waypoint, Gauss-Markov, City Section in Manhattan.
1 Introduction
A mobile ad hoc network (MANET) is a dynamically distributed system of mobile wireless nodes. The network bandwidth is limited and the transmitted signals are prone to interference and collision as the medium is shared. Since the nodes operate with limited battery power, the transmission range of a node is often limited. As a result, multi-hop routing is a common feature in MANETs. As the nodes move, there is unlikely to be a single fixed route throughout the duration of a source-destination session. MANET routing protocols proposed in the literature can be of two types [1]: proactive and reactive. Proactive routing protocols tend to predetermine routes between any pair of nodes in the network through periodic exchange of route-information bearing control packets among the nodes in the network. Reactive routing protocols use a broadcast query-reply cycle to determine routes between a pair of nodes only when required. In dynamic environments, reactive routing has been preferred over proactive routing as the on-demand routing protocols incur a relatively lower control overhead [2].
Vehicular ad hoc networks (VANETs) are one of the most promising application areas of MANETs. VANET communication is normally accomplished through special electronic devices placed inside each vehicle so
that an ad hoc network of the vehicles is formed on the road. A vehicle equipped with a VANET device should be able to receive and relay messages to other VANET-device equipped vehicles in its neighborhood. VANET applications can be broadly classified into two categories: safety applications and comfort applications [3]. An example of a safety application is on-board active safety systems to assist drivers with information (like accidents, road surface conditions, intersections, highway entries and etc) about the road ahead. Comfort applications are those applications that can provide non-critical services like weather information, gas station or restaurant locations, mobile e-commerce, Internet access, music downloads and etc.
VANETs resemble MANETs with respect to the dynamically and rapidly changing network topologies due to fast moving vehicles. However, the mobility of the vehicles is normally constrained by predefined roads and speed limitations. Mobility of the vehicles is also affected due to traffic congestion in the roads and the traffic control mechanisms (like stop signs and traffic lights). Route stability is an important design criterion to be considered in the design of MANET and VANET routing protocols. The routing protocols should be able to dynamically adapt to the rapidly changing network
208 Informatica 34 (2010) 207-221
N. Meghanathan
topologies while taking into consideration the layout of the roads. The commonly used route discovery approach of flooding the Route-Request (RREQ) packets can easily lead to congestion in the network and also consume the battery charge of the nodes. Frequent route changes can also result in out-of-order packet delivery, causing high jitter in multi-media, real-time applications. For safety applications, it is better to route all the critical data packets through the same path so that the receiver can reassemble the packets and get a consistent view of the network condition.
In an earlier work [4], we proposed an algorithm called OptPathTrans to determine the sequence of stable routes between a given source-destination pair over the duration of a communication session. Given the complete knowledge of the future topology changes over the entire duration of the communication session between a source s and destination d, algorithm OptPathTrans operates as follows: Whenever an s-d path is required at a time instant t, choose the longest-living s-d path from t. The above strategy is repeated over the duration of the s-d session. The sequence of such longest living stable paths is called the Stable Mobile Path (SMP). The performance of algorithm OptPathTrans has been largely studied under the commonly used Random Waypoint (RWP) mobility model [5] for MANETs. Note that throughout this paper, we use the terms 'path' and 'route' interchangeably. They mean the same. Similarly, the terms 'vehicle' and 'node' are used interchangeably, but mean the same.
In this paper, we study the performance of algorithm OptPathTrans with respect to the commonly used City Section mobility model [6] and the Manhattan mobility model [7] for VANETs, in addition to the Random Waypoint mobility model and the Gauss-Markov mobility model [8] used in MANETs. Most of the simulation studies in MANETs use the RWP model as the node mobility model. Even though the RWP model is easy to simulate, it has some unrealistic assumptions about node movement [9]: sharp turns and sudden stop. Sharp turns occur whenever a node changes its direction after travelling for a random amount of time and sudden stops occur when the node decides to stop at a particular time instant and changes directions. During a direction change, the speed chosen by a node is totally independent of the previous speed. The Gauss-Markov mobility model proposed by Liang and Haas [8] is more realistic compared to the RWP model. It eliminates the twin problems of sharp turns and sudden stops by considering the past speed and direction to influence the future speed and direction. But, the Gauss-Markov mobility model has been very rarely used in MANET simulation studies, mainly due to the relatively larger complexity involved in simulating it compared to the Random Waypoint model.
We use the OptPathTrans algorithm to compute the sequence of stable paths (the Stable Mobile Path) and the Dijkstra algorithm [10] to compute the sequence of minimum hop paths (called the Minimum Hop Mobile Path). For different conditions of network density and node mobility considered, we compute the Minimum
Hop Mobile Path and the Stable Mobile Path and rank the four mobility models (Random Waypoint mobility model, Gauss-Markov mobility model, City Section mobility model and the Manhattan mobility model) with respect to three critical metrics: (i) network connectivity (ii) path hop count and (iii) route lifetime. In all of the simulations, we observe a route lifetime - hop count tradeoff for each of the four mobility models considered. Routes with longer lifetime have larger hop count and routes with smaller hop count have shorter lifetime. We could not find any such comprehensive evaluation study in the literature about the impact of the four mobility models on the network connectivity, lifetime of stable paths and the hop count of minimum hop paths.
The rest of the paper is organized as follows: Section 2 briefly discusses the working of the Random Waypoint, City Section, Manhattan and the Gauss-Markov mobility models and also discusses the simulation methodology adopted for each model. Section 3 describes related work with regards to studying the impact of mobility models on the performance of the routing protocols. Section 4 provides an overview of the OptPathTrans algorithm used to determine the sequence of long-living stable paths in ad hoc networks. Section 5 illustrates the simulation results and compares the four mobility models with respect to the results obtained for network connectivity, route lifetime and hop count. Section 6 summarizes the results of the simulations and Section 7 concludes the paper.
2 Mobility models and their simulation methodology
In this section, we first provide a brief overview of the four mobility models studied in this paper. All the four mobility models assume the network is confined within fixed boundaries. The Random Waypoint mobility model assumes that the nodes can move anywhere within a network region. Under the Gauss-Markov mobility model, a node periodically updates its speed and direction of movement with a certain degree of Gaussian randomness and based on the past speed and direction of movement. The City Section and the Manhattan mobility models assume the network to be divided into grids: square blocks of identical block length. The network for these two VANET mobility models is thus basically composed of a number of horizontal and vertical streets. Each street has two lanes, one for each direction (north/ south direction for vertical streets, east/ west direction for horizontal streets). A node is allowed to move only along the grids of horizontal and vertical streets. For all the four mobility models, the mobility profile for each node, spanning the entire simulation time period, is created offline. The mobility profiles of the nodes are then input to the routing algorithm.
2.1 Random waypoint mobility model
Initially, the nodes are assumed to be placed at random locations in the network. The movement of each node is independent of the other nodes in the network.
A SIMULATION STUDY ON THE IMPACT...
Informatica 34 (2010) 207-221 213
The mobility of a particular node is described as follows: The node chooses a random target location to move. The velocity with which the node moves to this chosen location is uniform-randomly selected from the interval [vmin,...,vmax\. The node moves in a straight line (in a particular direction) to the chosen location with the chosen velocity. After reaching the target location, the node may stop there for a certain time called the pause time. The node then continues to choose another target location and moves to that location with a new velocity chosen again from the interval [vmin,.,vmax]. The selection of each target location and a velocity to move to that location is independent of the current node location and the velocity with which the node reached that location.
Simulation Methodology: The nodes are uniform-randomly distributed throughout the network. The mobility profile for a node is updated each time the node changes its direction and randomly chooses a new target location to move. The mobility profile for a node i comprises of a sequence of tuples, each of which contain
the following information: [ t°, tb , (x°, y °), (xb, yb ), vi b ] where t" is the time instant that node i is
intersection chooses a random target street intersection to move. The node then moves to the chosen street intersection on a path that will incur the least amount of travel time. If two or more paths incur the least amount of travel time, the tie is broken arbitrarily. After reaching the targeted street intersection, the node may stay there for a pause time and then again choose a random target street intersection to move. This procedure is repeated independently by each node.
Simulation Methodology: The nodes are uniform-randomly distributed on the street intersections. More than one node may be placed at a street intersection. The mobility profile for a node is updated each time the node moves from a street intersection to a randomly selected street intersection through a path that will incur the minimum number of street intersections. The mobility profile for a node i comprises of a sequence of tuples, each of which contain the following information:
r J a ,b ^a-b , „a „ a. , „b	n i	-¿a. ^
[ t, , t, , P, ( x, , yt X ( xt , yt X vi ] where tt is the time instant that node i is at street intersection ( x,a, y^ ) and chooses to move to a randomly selected street intersection ( xb, yb ) with a velocity v, through the
-b .
at location ( xa, y," ), changes its direction to move to a shortest path P, " that will have the mi"imum number of
randomly selected location ( xb, yb ) with a randomly street intersections between ( x", y,) and ( x,, y, ).
chosen velocity vi b e [vmin,...,vmax ] and reaches the
chosen location at time instant tb . The above process is
independently repeated for each node until the simulation time period. We assume the pause time for a node to be zero in all of our simulations. Whenever the routing algorithm needs to compute a graph at a particular time
instant, say ts, we determine the location of each node in the network using the mobility profile for the node. For example, to determine the location of node i at time
instant ts, we index into the sequence of tuples constituting the mobility profile of node i and choose the
entry whose two time instants t®, tb are such that t® < ts < tb . The location (x*, y *) of node i at time instantts is basically given by:
x, =
y =
l_l_l±_ * xb
tb - ta 1
t± -1
tb - ta
- * yb
+
+
tb - ts _* xa
tb - ta 1
tb - ts 11 11 * ya
tb - ta 1
Node i reaches (xb, yb ) at time instant tb . The above
process is independently repeated for each node until the simulation time period. We assume the pause time for a node to be zero in all of our simulations.
To determine the location of node i at time instant ts, we index into the sequence of tuples constituting the mobility profile of node i and choose the entry whose
two time instants ti, tb are such that ti < ts < tb . The
location (x*, y *) of node i then at time instant ts is determined as follows: Let the shortest path pi~b between street intersections (xi, yta) and
(xb, yb ) be represented as (x*, yi), (xf1, yf1),
(xf2,yf2), ......, (xfh,yfh),(xb,yb); where h is the
number of intermediate street intersections; kh k2, k3, ............fh are the intermediate street intersections
constituting the shortest path pi b and tf1, tf 2, ......,
tfh represent the time instants the node i is at these intermediate street intersections respectively. We find the two time instants tfl and tfl+1 such that tfl < ts < tfl+1
2.2 City section mobility model
Initially, the nodes are assumed to be randomly placed in the street intersections. Each street (i.e., one side of a square block) is assumed to have a particular speed limit. Based on this speed limit and the block length, one can determine the time it would take to move in the street. Each node placed at a particular street
where 1 < l < h. The location ( xi , yi ) of node i then at time instant ts is basically given by:
208 Informatica 34 (2010) 207-221
N. Meghanathan
X =
y; =
tf-	Al	* Xa+1	+	Al+1 ti	-tif
tkl+1 ti	¿kl -ti			t kl+1	kl - 1I
tif	kl	* y kl+1 si	+	~ .kl+1 ti	- tf
tkl+1 ti	M -ti			tkl+1	¿kl - ti
■* xkl
* yk
2.3 Manhattan mobility model
Initially, the nodes are assumed to be randomly placed in the street intersections. The movement of a node is decided one street at a time. To start with, each node has equal chance (i.e., probability) of choosing any of the streets leading from its initial location. After a node begins to move in the chosen direction and reaches the next street intersection, the subsequent street in which the node will move is chosen probabilistically. If a node can continue to move in the same direction or can also change directions, then the node has 50% chance of continuing in the same direction, 25% chance of turning to the east/north and 25% chance of turning to the west/south, depending on the direction of the previous movement. If a node has only two options (this occurs when the node is in one of the four bounding streets of the network), then the node has an equal (50%) chance of exploring either of the two options. If a node has only one option to move (this occurs when the node reaches any of the four corners of the network), then the node has no other choice except to explore that option.
Simulation Methodology. The mobility profile for a node is updated each time the node moves from a street intersection to an adjacent street intersection. The
movement is decided as follows. Let (x", y") be the
street intersection of node i at time instant t ".
Let SI - set " be the set of all neighbouring street
intersections of (x", y"). If there exists only one entry
in SI - seta , say SI - set " = [(xf, yf)], then the
adjacent street intersection (xf, yf ) to which node i
moves at time instant tf is basically (xf, yf). If there are two possible candidate adjacent street intersections in SI - set", say SI - seta = [(xf, yf), (xf, yf)],
then we generate a random numberri"from 0 to 1. If
r" < 0.5, then we assign (xf, yf ) = (xf, yf);
otherwise, we set (xf, yf ) = (xf, yf). If there are three possible candidate adjacent street intersections in SI - set" , say SI - set" = [(xf, yf), (xf, yf),
(xf, yf)], where let (xf, yf) be the street
intersection that is in the same axis as that of ( xia , yia )
and let (xf, yf) and (xf, yf) be the street intersections that are not in the same axis as that of
(x", y"). We generate a random number rf from 0 to 1. If r" < 0.5, then we assign (xf, yf ) = (xf, yf); if 0.5 < r" < 0.75, we assign (xf, yf ) = (xf, yf) and forrf > 0.75, we set (xf, yf ) = (xf, yf). We then add the tuple [ ta, tf, (x", y"), (xf, yf ), v,. ] to the mobility profile of node i, where v, is the velocity with
which node i moves from (x", y") to (xf, yf ). The
above process is independently repeated for each node until the simulation time period. We assume the pause time for a node to be zero in all of our simulations.
To determine the location of node i at time instant ts, we index into the sequence of tuples constituting the mobility profile of node i and choose the entry whose
two time instants t", tf are such that t" < ts < tf . The location (xf, y*) of node i at ts is basically given by.
xf =
y =
tf - ta
* xb
tb -1
tf - ta tb - ta 1
+
+
tb - tf _* xa
tb - ta 1
tb - tf ii_i±_ * ya
tb - ta 1
2.4 Gauss-Markov mobility model
Initially, the nodes are placed at random locations in the network. The movement of a node is independent of the other nodes in the network. Each node i is assigned a
mean speed, , and mean direction, of movement.
For every constant time period, a node calculates the speed and direction of movement based on the speed and direction during the previous time period, along with a certain degree of randomness incorporated in the calculation. The node is assumed to move with the calculated speed and in the calculated direction during every fixed time period. For a particular time
instant, tia+1, the speed and direction of a node i is
calculated as follows:
Sa+1 = a* Sa + (1 - a)* S W1 - a2 * SG (ta ) © a+1 = a* 0a + (1 - a)* ©~ + V 1 - a2 * © G (ta )
The parameter a (0 < a < 1) is used to incorporate the degree of randomness while calculating the speed and direction of movement for a time period. The degree of randomness decreases as we increase the value of a from 0 to 1. When a is closer to 0, the degree of randomness is high, which may result in sharper turns. When a is closer to 1, the speed and direction during the previous time period are given more importance (i.e., the model is more temporally dependent) and the node prefers to move in a speed and direction closer to what it has been using so far. Thus, the movement of a node gets more linear as the
value of a approaches unity. The terms SG (t * )and
a
A SIMULATION STUDY ON THE IMPACT...
Informatica 34 (2010) 207-221 213
® G (ta ) are random variables chosen independently by each node from a Gaussian distribution with mean 0 and standard deviation 1. If (x°, y°) are the co-ordinates of
node i at time instant t", the co-ordinates (x;a+1, y;a+1)
of the node at time instant tia+1 are given by:
Xa+1 = Xa + [Sa *cos(©a)] Ya+1 = Y a + [Sa * sin(©a)]
3 Related work
In addition to the mobility models described in Section 2, we now discuss few other relevant mobility models that have also been proposed for ad hoc networks. These include the Random Walk model [6], Random Direction model [6], Random Trip model [13], Freeway model [7] and the Random Point Group (RPG) model [6].
3.1 Review of other mobility models
The Random Walk model is a slight variation of the Random Waypoint model: a node moves in a randomly chosen direction and speed until the network boundary is reached. After reaching the network boundary, the node chooses another random direction and speed to move. The Random Trip mobility model is also a slight variation of the Random Waypoint mobility model: at a trip transition instant, a node selects a random direction, trip duration and speed and moves in the chosen direction with the chosen speed for the chosen trip duration. If the node reaches the boundary of the network during the trip, the node is reflected. After the expiration of the chosen trip duration, another set of random direction, trip duration and speed values is chosen and the movement is continued. In the Random Waypoint, Random Walk and Random Trip mobility models, the random speed selected by a node is chosen from a pre-specified range. In the Random Direction model, a node moves in a randomly chosen direction and travels to the border of the simulation area in that direction. As soon as the network boundary is reached, the node stops for a certain period of time and then moves by choosing another angular direction (between 0 and 180 degrees).
The Freeway model can be used to emulate the movement of nodes in a freeway. A freeway is assumed to comprise of one or more lanes, in both directions. The movement of a node is however restricted to a particular lane of the freeway and there can be no lane changes. The velocity of a node i at time instant t+1, V1t+lis dependent on the velocity of the node at time instant t, V- and the maximum possible acceleration/deceleration
for a unit time, ati. If node i travels behind node j and the distance between them at time instant t is within the
Safety Distance (SD), then V- < V'. Thus, the Freeway
1 j
model has high spatial and temporal dependence.
The RPG mobility model works as follows: Nodes move as a group with each group having a group leader (a logical centre for the group) whose movement determines the group's mobility pattern. Because of this property, the mobility pattern of the nodes under the RPG model is expected to have high spatial dependence. Initially, each group member is assumed to be uniform-randomly distributed in the neighbourhood of the group leader. For every time instant, the speed and direction of a node is derived by randomly deviating from that of the group leader.
3.2 Literature review
In [14], the authors study the impact of the three Randomness-based mobility models (Random Waypoint, Random Direction and the Random Walk models) on the minimum-hop based Ad hoc On-demand Distance Vector (AODV) [15] routing protocol. Simulation results show that AODV incurred the lowest hop count for its routes when simulated under the Random Waypoint mobility model. The Random Direction mobility model generated the maximum routing overhead (ratio of the number of control packets sent to the number of data packets sent) and the Random Waypoint model generated the minimum routing overhead. The Random Waypoint mobility model also yielded the maximum packet delivery ratio and throughput.
In [16], the authors compare the performance of the proactive Destination Sequenced Distance Vector (DSDV) routing protocol [17] and the on-demand Dynamic Source Routing (DSR) [18] and the AODV routing protocols with respect to the Random Waypoint and Random Trip mobility models. The end-to-end delay per data packet for all the three routing protocols was found to be lower when simulated with the Random Waypoint model compared to the Random Trip model.
In [19], the authors compare the performance of DSR and DSDV protocols under the Random Waypoint model, Random Point Group model, Freeway model and the Manhattan model. The throughput obtained with DSR was greater than that obtained with DSDV under all the four mobility models. For smaller node velocities, DSR yielded a higher throughput under the Freeway mobility model. For moderate and higher node velocities, DSR yielded a higher throughput under the Random Waypoint model, closely followed by the Manhattan model. As the mobility of the nodes increased, the throughput of both DSR and DSDV decreased drastically under the Freeway model.
In [20], the authors study the impact of the Random Waypoint model, the RPG mobility model and its variants on the performance of DSDV, AODV and DSR. DSR had the highest packet delivery ratio, followed by DSDV and then AODV. Routes under the RPG model are more likely to exist for a longer time as nodes are in the close vicinity of each other. Hence, the routing protocols incurred a lower routing overhead as well as a larger throughput with the RPG model compared to the Random Waypoint model. The packet delivery ratio of the routing protocols was strongly influenced by the
208 Informatica 34 (2010) 207-221
N. Meghanathan
distribution of the nodes within the network. There were erratic variations of the packet delivery ratios of the routing protocols with respect to the RPG model and its variants; whereas, there was less variation in the packet delivery ratios of the routing protocols under the Random Waypoint model. Under the Random Waypoint model, nodes are more likely to be homogeneously distributed throughout the network all the time.
In [21], the authors compare the performance of DSR, DSDV and the AODV under the Random Waypoint model, Freeway model, Manhattan model and the RPG model. Each of the three routing protocols achieved the highest throughput and the least overhead with the RPG model and incurred high overhead and low throughput with both the Freeway and Manhattan models. The relative rankings of the routing protocols with respect to different performance metrics varies with the mobility model used.
3.3 Motivation for our research
All of the above work study the performance impact of the mobility models on the minimum-hop based routing protocols. None of the work studied the performance impact of the mobility models on the stability-based routing algorithms and protocols. As a first step in this direction, in this paper, we study the impact of the Random Waypoint, City Section model, Manhattan and the Gauss Markov mobility models on the OptPathTrans algorithm (algorithm to find the sequence of most stable paths in an ad hoc network) and compare the performance with that of the algorithm to find the sequence of minimum hop paths. The next step in our research would be to study the impact of the four mobility models on the stable path MANET routing protocols such as the Flow-Oriented Routing Protocol (FORP) [22], Associativity Based Routing (ABR) protocol [23] and the Route-lifetime Assessment Based Routing Protocol (RABR) [24] and compare their performance with that of the minimum-hop based routing protocols such as DSR, AODV and DSDV.
4 Algorithm to determine the optimal number of path transitions
In this section, we briefly review the OptPathTrans algorithm, recently proposed by us in [4], to determine the optimal number of path transitions in ad hoc networks. The algorithm uses the notions of mobile graph to record the sequence of network topology changes and mobile path to record the sequence of paths in a mobile graph.
4.1 Mobile graph
A mobile graph [11] is defined as the sequence GM = G1G2 ... Gt of static graphs that represents the network topology changes over some time scale T. In the simplest case, the mobile graph GM = G1G2 ... GT can be extended by a new instantaneous graph GT+1 to a longer sequence
Gm = G1G2 ... Gt Gt+1, where GT+1 captures a link change (either a link comes up or goes down). But such an approach has very poor scalability. In this paper, we sample the network topology periodically for every 0.25 seconds, which could, in reality, be the instants of data packet origination at the source.
4.2	Mobile path
A mobile path [11], defined for a source-destination (s-d) pair, in a mobile graph GM = G1G2 ... GT is the sequence of paths PM = P1P2 ... PT, where Pt is a static path between the same s-d pair in Gi = (Vi, E), Vi is the set of vertices and Et is the set of edges connecting these vertices at time instant t. That is, each static path Pi can be represented as the sequence of vertices v0v1 ... vl, such that v0 = s and vl = d and (vj-1,vj) e Et for j = 1,2, ..., l. The timescale of T normally corresponds to the duration of a session between s and d.
The Stable Mobile Path (SMP) for a given mobile graph and s-d pair is the sequence of static s-d paths such that the number of route transitions (change from one static s-d path to another) is as minimum as possible. In other words, the constituent static paths of an SMP have the longest possible route lifetime. A Minimum Hop Mobile Path (MHMP) for a given mobile graph and s-d pair is the sequence of minimum hop static s-d paths. The SMP for an s-d pair on a given mobile graph is determined by using algorithm OptPathTrans. The MHMP for an s-d pair on a given mobile graph is determined by repeatedly running the minimum path weight Dijkstra algorithm on the static graphs. We follow the Least Overhead Routing Approach (LORA) [12] for ad hoc networks. Accordingly, a minimum hop s-d path determined by running Dijkstra algorithm on a static graph Gi is assumed to be used in the subsequent static graphs Gi+i, Gi+2, ...., as long as the path exists in these static graphs.
4.3	Algorithm OptPathTrans
Algorithm OptPathTrans (pseudo code given in Figure 1) operates on the following greedy strategy: Whenever a path is required, select a path that will exist for the longest time. Let GM = G1G2 ... GT be the mobile graph generated by sampling the network topology at regular instants tb t2, ..., tT of an s-d session. When an s-d path is required at sampling time instant t„ the strategy is to find a mobile sub graph G(i, j) = Gin Gm n ... n Gj such that there exists at least one s-d path in G(i, j) and no s-d path exists in G(i, j+1). A minimum hop s-d path in G(i, j) is selected. Such a path exists in each of the static graphs G, Gi+1, ..., Gj. If sampling instant tj+1 < tT, the above procedure is repeated by finding the s-d path that can survive for the maximum amount of time since tj+i. A sequence of such maximum lifetime static s-d paths over the timescale of a mobile graph GM forms the stabile mobile s-d path in GM. The run-time complexity of the algorithm is O(n2T), where n is the number of nodes in the network and T is the number of static graphs in a mobile graph (T is thus a measure of the timescale of
A SIMULATION STUDY ON THE IMPACT...
the network communication session between the source 5 and destination d).
Input: Gm = GiG2 ... GT, source s, destination d Output: PS	// Stable-Mobile-Path
Auxiliary Variables: i, j Initialization: i=1; j=1; PS = ®
Begin OptPathTrans
1	while (i < T) do
2	Find a mobile graph G(i, j) = Gi n Gi+1 n ... n Gj such that there exists at least one s-d path in G(i, j) and {no s-d path exists in G(i, j+1) or j = T}
3	PS=PS U {minimum hop s-d path in G(i, j) }
4	i = j + 1
5	end while
6	return PS
End OptPathTrans
Figure 1: Pseudo code for algorithm OptPathTrans.
5 Simulations
The network dimensions are 1000m x 1000m. The Random Waypoint and Gauss-Markov mobility models work by assuming an open network field without any grid constraints. For the City Section and Manhattan mobility models, we assume the network is divided into grids: square blocks of length (side) 100m. The network for the two VANET mobility models is thus basically composed of a number of horizontal and vertical streets. Each street has two lanes, one for each direction (north and south direction for vertical streets, east and west direction for horizontal streets). A node is allowed to move only along the grids of horizontal and vertical streets. The wireless transmission range of a node is 250m. The network density is varied by performing the simulations with 25 (low), 50 (moderate) and 75 (high) nodes. The node velocity values used for each of the four mobility models are 5 m/s (about 10 miles per hour), 15 m/s (about 35 miles per hour) and 30 m/s (about 65 miles per hour), representing levels of low, moderate and high node mobility respectively. For the Gauss-Markov mobility model, these velocity values represent the mean speed S for a node and for the other three mobility models, these values represent the velocity of every node in the network. Note that, in the case of the Random Waypoint model, for a given mobility level, we let all the nodes in the network to move in the same velocity by letting vmin = vmax. The pause time is 0 seconds; so, all the nodes are constantly in motion.
In the case of the Gauss-Markov mobility model, each node is assigned a random value for the mean direction of movement, ©, chosen from the range [0.360°]. When a node travels beyond the boundaries of the simulation field, the mean direction of movement of
Informatica 34 (2010) 207-221 213
the node is forced to flip 180 degrees so that the node can remain within the boundary of the simulation field. The constant time period for updating the speed and direction of movement of the nodes under the Gauss-Markov mobility model is 1 second.
We obtain a centralized view of the network topology by generating mobility trace files for 1000 seconds under each of the four mobility models. The network topology is sampled for every 0.25 seconds to generate the static graphs and the mobile graph. Two nodes a and b are assumed to have a bi-directional link at time t, if the Euclidean distance between them at time t (derived using the locations of the nodes from the mobility trace file) is less than or equal to the wireless transmission range of the nodes. Each data point in Figures 2 through 12 is an average computed over 5 mobility trace files and 20 randomly selected s-d pairs from each of the mobility trace files. The starting time of each s-d session is uniformly distributed between 1 to 20 seconds.
5.1 Performance metrics
The following performance metrics are evaluated:
•	Percentage Network Connectivity: Percentage network connectivity indicates the probability of finding an s-d path between any two nodes in the network for a given network density and level of node mobility. Measured over all the s-d sessions, this metric is the ratio of the number of static graphs in which there is an s-d path to the total number of static graphs in the mobile graph.
•	Average Route Lifetime: The average route lifetime is the average of the lifetime of all the static paths of an s-d session, averaged over all the s-d sessions.
•	Average Hop Count: The average hop count is the time averaged hop count of a mobile path for an s-d session, averaged over all the s-d sessions. The time averaged hop count for an s-d session is measured as the sum of the products of the number of hops for the static s-d paths and the corresponding lifetime of the static s-d paths divided by the number of static graphs in which there existed a static s-d path. For example, if a mobile path comprises of a 2-hop static path pj, a 3-hop static path p2, and a 2-hop static path p3, existing in static graphs 1-2, 3-5 and 6-10 respectively, then the time-averaged hop count of the mobile path would be (2*2 + 3*3 + 2*5) / 10 = 2.3.
Note that for a given condition of network density and node mobility, the values reported for the performance metrics under the Gauss-Markov mobility model in figures 7 through 12 are the average of the performance metric values obtained for different values of a.
214 Informatica 34 (2010) 207-221
N. Meghanathan
5.2 Impact of the degree of randomness parameter in the Gauss-Markov mobility model
In moderate and high-density networks, there is no significant influence of parameter a on network connectivity. As we add more nodes, randomness or the absence of it, has no significant impact on network connectivity. The network connectivity obtained in low-density networks seems to slightly depend on the value of a used. As seen in Figure 2, the highest network
connectivity for low-density networks is obtained when a = 0, corresponding to the scenario in which the mobility of the nodes is totally random and not dependent on the past history. As nodes move randomly without restricting to a fixed path, the connectivity of the nodes can be guaranteed for a longer time, especially in low-density networks. Otherwise, if nodes move on a linear path for a long time, it is likely that they fall out of the range of each other after a while, thus reducing the connectivity of any two nodes in the network. Nevertheless, the standard
2.1: Node Velocity = 5m/s	2.2: Node Velocity = 15m/s	2.3: Node Velocity = 30m/s
Figure 2: Gauss-Markov Model: Percentage Network Connectivity Vs Degree of Randomness
3.1: Node Velocity = 5m/s	3.2: Node Velocity = 15m/s	3.3: Node Velocity = 30m/s
Figure 3: Gauss-Markov Model: Average Hop Count per Minimum Hop Path Vs Degree of Randomness.
4.1: Node Velocity = 5m/s	4.2: Node Velocity = 15m/s	4.3: Node Velocity = 30m/s
Figure 4: Gauss-Markov Model: Average Lifetime per Minimum Hop Path Vs Degree of Randomness.
5.1: Node Velocity = 5m/s	5.2: Node Velocity = 15m/s 5.3: Node Velocity = 30m/s
Figure 5: Gauss-Markov Model: Average Lifetime per Stable Path Vs Degree of Randomness.
_ i ■
0 25nodes ED50nodes D75nodes
MlU
a = 0 a = 0.2 a = 0.4 a = 0.6 a = 0.8
6.1: Node Velocity = 5m/s	6.2: Node Velocity = 15m/s 6.3: Node Velocity = 30m/s
Figure 6: Gauss-Markov Model: Average Hop Count per Stable Path Vs Degree of Randomness.
A SIMULATION STUDY ON THE IMPACT...
Informatica 34 (2010) 207-221 213
deviation of the network connectivity in low-density networks is not more than 5% of the mean network connectivity obtained for different a values.
With respect to the influence of the degree of randomness parameter a on the hop count of the minimum hop paths, we observe that the maximum difference in the minimum hop count of the paths obtained for different values of a for a given condition of node mobility and network density is 0.3, while the average hop count of the paths under the Gauss-Markov model is in the range of 3.0 to 3.6. In more statistical terms, the standard deviation of the minimum hop counts is not even 3% of the average of the minimum hop counts obtained for different values of a. So, we can very well conclude that the degree of randomness in the Gauss-Markov model does not significantly influence the hop count of the minimum hop paths in the network. We also observe that the lifetime of the minimum hop paths do not significantly differ from each other for different values of a. Similar to the observation made for the hop count, the standard deviation of the lifetime of the minimum hop paths is not even 4% of the average of the lifetime of the minimum hop paths obtained for different values of a. The above observations are consistent with the simulation results obtained in [9], wherein it has been concluded that the degree of randomness parameter in the Gauss-Markov model has no significant influence on the throughput and end-to-end delay per data packet.
With respect to the influence of the degree of randomness parameter a on the lifetime of the stable paths, we observe that it is possible to determine long-living routes by adopting larger intermediate values of a (i.e., a values of 0.6 to 0.8), when the model is considered to give higher weight to the speed and direction of movement in the previous time period while determining the speed and direction of movement for the subsequent time period. But, there is still a degree of randomness associated with the determination of speed and direction (note that we are not letting a to approach 1). Such a small level of randomness is required to occasionally deflect nodes from their linear path so that the nodes continue to remain as neighbours with a larger probability and do not move far away from each other. If the nodes strictly take a linear path, it is possible for them to move away from each other relatively sooner. A certain degree of randomness is required for the nodes to get deflected and move in the vicinity of each other for relatively little longer. From Figures 6.1 through 6.3, we can observe that the lifetime of the stable routes determined with a value of 0.6 can be sometimes about 20% more than the lifetime of the stable routes determined with a value of 1.0. For lower values of a, the degree of randomness increases and the number of link changes increases significantly. Nevertheless, the lifetime of stable routes determined for lower values of a is not significantly lower than those obtained for a values in the range of 0.6 to 0.8 and is almost close to the lifetime values obtained when a is unity. The standard deviation of the lifetimes of stable routes is still below 10% of the mean of the lifetime of the stable routes
computed over the different values of a for a particular condition of network density and node mobility.
Similarly, the standard deviation of the hop counts of stable routes is within 10% of the mean of the hop counts of stable routes computed over different a values for a given network density and node mobility.
The above observations justify the usage of the average of the values of a performance metric for different values of a as a measure of the performance under the Gauss-Markov mobility model in figures 7 through 12 that compare the performance under the different mobility models.
5.3 Network connectivity
The Random Waypoint mobility model provided the maximum network connectivity for any combination of network density and node mobility. In low-density and moderate-density networks, for all levels of node mobility, the RWP model is the only mobility model to provide a connectivity of at least 90% and 99% respectively. In high-density networks, for any level of node mobility, each of the four mobility models provided connectivity of at least 99.5%. The following ranking can be observed for the four mobility models in decreasing order of network connectivity in low and moderate density networks: Random Waypoint model, City Section model, Gauss-Markov model and the Manhattan model. Note that the network connectivity values plotted in Figures 7.1 through 7.3 is an average of those obtained for the Minimum Hop Mobile Path and Stable Mobile Path.
In low density networks, the lower network connectivity obtained with the two VANET mobility models can be attributed to the constrained motion of the nodes only along the streets of the network. In the case of the Manhattan mobility model, the probabilistic nature of direction selection after reaching each street intersection is also a reason behind the lowest network connectivity observed for this mobility model among all the four mobility models. The number of nodes distributed in the streets of the network may not be sufficient enough to connect any pair of source-destination nodes all the time. In the case of the Gauss-Markov mobility model, the direction of movement of the nodes is restricted close to the initially assigned mean direction of movement. Note that, we assign each node a mean direction of movement randomly chosen from [0...3600]. But, still, when there are few nodes in the network, the restricted movement of the nodes close to the mean direction of movement is a limiting factor for network connectivity. As we increase the number of nodes in the network, both the VANET mobility models and the Gauss-Markov mobility model demonstrate a significant increase in network connectivity, for all levels of node mobility. This illustrates the fact that the randomness associated with the mobility models assures that any pair of nodes will remain connected, provided we have at least a reasonably larger number of nodes (like moderate density networks), irrespective of the different levels of node mobility.
208 Informatica 34 (2010) 207-221
N. Meghanathan
7.1: Node Velocity = 5m/s	7.2: Node Velocity = 15m/s	7.3: Node Velocity = 30m/s
Figure 7: Percentage Network Connectivity under the Different Mobility Models.
8.1: Node Velocity = 5m/s	8.2: Node Velocity = 15m/s	8.3: Node Velocity = 30m/s
Figure 8: Average Hop Count per Minimum Hop Path under the Different Mobility Models.
9.1: Node Velocity = 5m/s	9.2: Node Velocity = 15m/s	9.3: Node Velocity = 30m/s
Figure 9: Average Lifetime per Minimum Hop Path under the Different Mobility Models.
5.4 Minimum hop mobile path
We now discuss the time averaged hop count per minimum hop path (refer Figure 8) and the average route lifetime (refer Figure 9) of the minimum hop paths determined as the constituent paths of the Minimum Hop Mobile Path under the four mobility models.
5.4.1 Average hop count per minimum hop path
The average hop count per minimum hop path determined for the two VANET mobility models and the Gauss-Markov model is considerably larger than the hop count per minimum hop path determined for the Random Waypoint mobility model. The relatively larger hop count can be attributed to the constrained mobility of the nodes under these three mobility models. The minimum hop paths in the street networks are most likely not to exist on or close to the straight line between source and destination nodes. Similarly, due to the temporal dependency associated with the Gauss-Markov mobility model, one cannot always find minimum hop paths lying on a straight line connecting the source and destination nodes. Based on our observations in Figures 8.1 through 8.3, we can arrive at the following ranking of the four mobility models in the increasing order of the magnitude of the hop count for the minimum hop paths: Random Waypoint model, City Section model, Gauss-Markov model and the Manhattan model. This ranking holds
good for all the simulated conditions of network density and levels of node mobility.
For a given node velocity, the average hop count per minimum hop path under the City Section mobility model, Gauss-Markov mobility model and the Manhattan mobility model is respectively about 14%, 17% and 19% more than that incurred for the Random Waypoint mobility model in low-density networks. In moderate and high-density networks, the average hop count per minimum hop path under the City Section, Gauss-Markov and Manhattan mobility models is respectively about 18%, 25% and 40% more than that incurred for the Random Waypoint mobility model. We also observe that with increase in network density, the average hop count per minimum hop path for the Random Waypoint mobility model, City Section mobility model and the Gauss-Markov mobility model decreases (by a factor of 5%-10%). On the other hand, with increase in network density, the average hop count per minimum hop path for the Manhattan mobility model remained the same or even sometime increases up to 14%. This can be attributed to the significant increase in the network connectivity for the Manhattan mobility model with increase in network density, but at the cost of increase in hop count. Given the extremely constrained and random nature of node movement under the Manhattan mobility model, in order to connect the source and destination, more intermediate nodes have to be accommodated in the source-destination paths.
A SIMULATION STUDY ON THE IMPACT...
Informatica 34 (2010) 207-221 213
5.4.2 Average lifetime per minimum hop path
When we aim for minimum hop count in the paths and determine the Minimum Hop Mobile Path by repeated application of the Dijkstra algorithm on the static graphs, we observe that the minimum hop paths determined under the City Section mobility model are relative more stable (i.e., have a larger route lifetime) compared to the minimum hop paths determined under the other three mobility models. We even observe that the minimum hop paths determined under the Manhattan mobility model in low-density networks are relatively more stable than those determined under the Random Waypoint and the Gauss-Markov mobility models. In low-density networks, the average lifetime of the minimum hop paths determined under the Manhattan mobility model is only about 3% less than the average lifetime of the minimum paths determined under the City Section mobility model. But, as we increase the network density, the number of hops in the minimum hop paths determined under the Manhattan mobility model increased to provide better network connectivity. However, such minimum hop paths have been observed to be relatively unstable.
For a given level of node mobility, in low-density networks, the average lifetime of the minimum hop routes determined under the Manhattan model, Random Waypoint model and the Gauss-Markov model is about 3%, 10% and 25% less than the average lifetime of minimum hop routes determined under the City Section mobility model. But, as we increase the network density, we observe that the magnitude of this difference increases further. For a given level of node mobility, in moderate and high-density networks, the average lifetime of the minimum hop routes determined under the Manhattan model, Random Waypoint model and the Gauss-Markov model is about 10%-15%, 10%-15% and 30%-34% less than the average lifetime of minimum hop routes determined under the City Section mobility model. The relatively poor lifetime of minimum hop routes determined under the Gauss-Markov mobility model can be attributed to the temporal dependency of the nodes in choosing their direction of movement. When we attempt to optimize the number of hops, it may be possible to obtain paths with lower hop count. But, such paths may have links whose constituent nodes are on the verge of moving away from each other, travelling in different directions.
We also observe that with increase in network density, the average lifetime of the minimum hop routes decreases for all the four mobility models. This can be attributed to the decrease in the hop count of the minimum hop routes as we increase the number of nodes in the network. It gets possible to reduce the number of hops by choosing the intermediate nodes from a larger pool of available nodes. But, the physical distance between the constituent nodes of the links in such minimum hop paths tends to be close to or even more than 80% of the transmission range of the nodes at the time of route selection itself. Such routes are bound not to last longer. Thus, with a small reduction in the
minimum hop count of the paths, we incur a significant reduction in the lifetime of the minimum hop routes. Note that for the Manhattan mobility model, even though the hop count of the minimum hop routes increases with increase in network density, the lifetime of the minimum hop routes decreases with increase in network density. In the case of the Manhattan mobility model, the network connectivity was very low in low-density networks. So, as we increased the network density, the network connectivity improved but more intermediate nodes have to be added, even if we aim for minimum hop paths.
The following ranking can be assigned for the four mobility models in the decreasing order of lifetime of minimum hop routes for the different network densities, irrespective of the level of node mobility:
•	Low-density networks: City Section model, Manhattan model, Random Waypoint model, Gauss-Markov model
•	Moderate and High-density networks: City Section model, Random Waypoint model, Manhattan model and Gauss-Markov model
5.5 Stable mobile path
We now discuss the average route lifetime (refer Figure 10) per stable path and the time averaged hop count per stable path (refer Figure 11) as we determine the constituent stable paths of the Stable Mobile Path under all the four mobility models.
5.5.1 Average lifetime per stable path
For all the four mobility models, algorithm OptPathTrans was able to determine stable paths by adding more intermediate nodes to the path such that the average physical distance between the constituent nodes of the links in the stable path is only about 60%-70% of the transmission range of the nodes. Thus, the long-living routes are determined at the cost of an increase in the hop count. This is a tradeoff that cannot be avoided. We also observe that for each of the four mobility models, for a given level of node mobility, the lifetime of the stable routes increased as we increase the network density. This is because algorithm OptPathTrans gets a larger pool of nodes to select from by looking ahead at the future. Nevertheless, we do see an increase in the hop count of the stable routes in moderate and high-density networks vis-à-vis low-density networks, an observation again vindicating the tradeoff between route lifetime and hop count in ad hoc networks.
Overall, the lifetime of stable routes obtained under the Random Waypoint model was the largest in all of the simulated scenarios. This can be attributed to the unconstrained mobility of the nodes and algorithm OptPathTrans faces no restrictions in choosing the intermediate nodes that form the stable paths. With the other three mobility models, due to the constrained mobility of the nodes in one way or the other, algorithm OptPathTrans faces restrictions in choosing the intermediate nodes for the stable paths. As a result, the stable paths determined under these mobility models with restricted node movement have a relatively lower
208 Informatica 34 (2010) 207-221
N. Meghanathan
10.1: Node Velocity = 5m/s	10.2: Node Velocity = 15m/s	10.3: Node Velocity = 30m/s
Figure 10: Average Lifetime per Stable Path under the Different Mobility Models.
11.1: Node Velocity = 5m/s	11.2: Node Velocity = 15m/s	11.3: Node Velocity = 30m/s
Figure 11: Average Hop Count per Stable Path under the Different Mobility Models
lifetime when compared to those incurred under the RWP model.
The following rankings can be assigned for the four mobility models in the decreasing order of the lifetime of the stable paths for the different network density and node mobility scenarios:
•	High network density, High node mobility: Random Waypoint model, City Section model, Gauss-Markov model and Manhattan model
•	All other conditions of network density and node mobility: Random Waypoint model, City Section model, Manhattan model and Gauss-Markov model
In high-density networks with high level of node mobility, the Gauss-Markov model yielded stable routes with a slightly larger lifetime than the Manhattan mobility model. This can be reasoned as follows: In high-density networks, due to the temporal dependency on the direction of movement of the nodes, it is possible to find stable paths involving nodes that are travelling in the same direction or at least not moving away from each other. With the Manhattan model, it is less likely that the algorithm OptPathTrans can find nodes travelling in the same direction as the direction of movement of the nodes is probabilistically decided at each street intersection.
As we increase network density from low to high, the two VANET mobility models experience a relatively smaller increase in the lifetime of stable routes compared to the Random Waypoint and Gauss-Markov mobility models. This can be attributed to the constrained mobility of the nodes in the street networks. As discussed above, the Gauss-Markov model makes the most use of increase in the number of nodes in the network, as it becomes increasingly possible to find nodes travelling in a similar direction. Since the nodes moving under Gauss-Markov model are temporally dependent on the previous direction of movement and the mean direction of movement, algorithm OptPathTrans has good chance of finding a stable path that will involve nodes travelling in a similar direction and that the link between the
constituent nodes of such a path will exist for a relatively longer time.
5.5.2 Average hop count per stable path
As discussed in Section 4.5.1, algorithm OptPathTrans determines paths with a relatively longer lifetime than the minimum hop paths, but the hop count of such stable paths is larger than the minimum hop count possible for the same operating conditions of network density and node mobility. Such a lifetime-hop count tradeoff exists for all the four mobility models.
The hop count of the stable routes determined under the City Section mobility model is the smallest for most of the operating scenarios. The hop count of the stable routes determined under the Random Waypoint mobility model is larger than those determined under the City Section mobility model by at most 10%-15%. But as we observed in Section 4.5.1, algorithm OptPathTrans was able to find long-living routes under the Random Waypoint model. The lifetime of such stable routes can be as large as 30% compared to those incurred with the City Section mobility model. This observation again illustrates the tradeoff between lifetime and hop count. The hop count of the stable routes determined with the Gauss-Markov and the Manhattan mobility models are almost the same for most of the operating scenarios, with the Manhattan mobility model having a slightly larger hop count in networks with low node mobility. But the hop count of the stable routes determined under these two models is considerably larger than those determined under the City Section and the Random Waypoint mobility models.
As we increase the level of node mobility, the lifetime of the links decreases, forcing algorithm OptPathTrans to determine stable routes with a relatively smaller lifetime compared to those determined in networks of low node mobility. The hop count of the stable routes determined under conditions of high node mobility does mostly get smaller compared to those determined under conditions of low node mobility.
A SIMULATION STUDY ON THE IMPACT...
Informatica 34 (2010) 207-221 213
Nevertheless, as we increase the level of node mobility from 5 m/s to 30 m/s, for all of the four mobility models, the reduction in the hop count of stable paths is more in low-density networks compared to that incurred in high-density networks. This is because, as we increase the level of node mobility, the rate of decrease in the lifetime of stable routes in low-density networks is relatively larger than the rate of decrease of the lifetime of stable routes in high-density networks under each of the four mobility models.
involving those nodes. Of course, there is a corresponding increase in the hop count ratio for the Gauss-Markov mobility model in high-density networks. The increase in the lifetime ratio for the City Section and Manhattan mobility models is relatively modest and this can be attributed to the constrained mobility of the nodes in the street networks. Similar to the RWP model, the increase in the hop count ratio for the other three mobility models is also sub-linear compared to the increase in the lifetime ratio.
5.6 Route lifetime - hop count tradeoff
We observe a tradeoff between the objectives of optimizing the route lifetime and the hop count per path for all the four mobility models. Both of these performance metrics cannot be optimized at the same time. For a given simulation condition of network density and node mobility, the average hop count of a Minimum Hop Mobile Path is smaller than the average hop count of a Stable Mobile Path; the average route lifetime of a Stable Mobile Path is more than the average route lifetime of a Minimum Hop Mobile Path. We capture the route lifetime-hop count tradeoff in terms of the lifetime ratio and the hop count ratio. The lifetime ratio is the ratio of the average lifetime per stable path in the Stable Mobile Path to that of the average lifetime per minimum hop path in the Minimum Hop Mobile Path. The hop count ratio is the ratio of the average hop count per stable path in the Stable Mobile Path to that of the average hop count per minimum hop path in the Minimum Hop Mobile Path. The range of values of the lifetime ratios and hop count ratios observed for the four mobility models in low and high-density networks is illustrated in Figures 12.1 and 12.2.
One can observe from the figures that largest values for both the lifetime and hop count ratios are incurred with the Random Waypoint mobility model. This illustrates that under the Random Waypoint mobility model, it is possible to determine stable paths with relatively a very longer lifetime compared to the lifetime of the minimum hop paths, but there is a corresponding increase in the hop count of the stable paths. Nevertheless, the increase in the hop count ratio is not proportional and is sub-linear compared to the increase in the lifetime ratio. For example, the lifetime ratio for RWP model is in the range of 2.6-2.9 and 8.2-8.9 in low and high density networks respectively, where as the hop count ratio for the RWP model is in the range of 1.4-1.75 and 2.5-2.75 in low and high-density networks respectively.
The lifetime ratio for the Gauss-Markov mobility model is the lowest of all the four mobility models in low-density networks. But, in high-density networks, we observe that the lifetime ratio for the Gauss-Markov mobility model is above that of the City Section and Manhattan mobility models. This supports our earlier reasoning that in high-density networks, algorithm OptPathTrans manages to find more nodes travelling in the same direction under the Gauss-Markov mobility model and hence can find long-living stable paths
Figure 12.1: Lifetime Ratio.
Figure 12.2: Hop Count Ratio.
Figure 12: Route Lifetime - Hop Count Tradeoff.
208 Informatica 34 (2010) 207-221
N. Meghanathan
6 Summary of results
The performance of the Gauss-Markov mobility model for different values of the degree of randomness parameter a can be summarized as follows: In moderate and high-density networks, there is no significant influence of parameter a on network connectivity. The highest network connectivity for low-density networks is obtained when a = 0, corresponding to the scenario in which the mobility of the nodes is totally random and not dependent on the past history. The degree of randomness does not significantly influence the hop count and lifetime of the minimum hop paths in the network. We also observe that one can determine long-living routes by adopting larger intermediate values of a (i.e., a values of 0.6 to 0.8).
The following ranking can be observed for the four mobility models in the decreasing order of network connectivity in low and moderate density networks: Random Waypoint model, City Section model, Gauss-Markov model and the Manhattan model. In high-density networks, for any level of node mobility, all the four mobility models provided a connectivity of at least 99.5%. As we increase the number of nodes in the network, both the VANET mobility models and the Gauss-Markov mobility model demonstrate a significant increase in network connectivity, for all levels of node mobility.
The minimum hop paths in the street networks are most likely not to exist on or close to the straight line between the source and destination nodes. Similarly, due to the temporal dependency associated with the Gauss-Markov mobility model, one cannot find minimum hop paths lying on a straight line connecting the source and destination nodes. For any condition of network density and node mobility, we can arrive at the following ranking for the four mobility models in the increasing order of the magnitude of the hop count for the minimum hop paths: Random Waypoint model, City Section model, Gauss-Markov model and the Manhattan model.
The minimum hop paths determined under the City Section mobility model are relatively more stable (i.e., have a larger route lifetime) compared to the minimum hop paths determined under the other three mobility models. The following rankings can be assigned for the four mobility models in the decreasing order of lifetime of minimum hop routes for the different network densities, irrespective of the level of node mobility: (i) Low-density networks - City Section model, Manhattan model, Random Waypoint model, Gauss-Markov model and (ii) Moderate and High-density networks - City Section model, Random Waypoint model, Manhattan model and Gauss-Markov model.
The lifetime of stable routes obtained under the Random Waypoint mobility model was the largest in all of the simulated scenarios. The following rankings can be assigned for the four mobility models in the decreasing order of the lifetime of the stable paths for the different network density and node mobility scenarios: (i) High network density, High node mobility - Random Waypoint model, City Section model, Gauss-Markov
model and Manhattan model (ii) All other conditions of network density and node mobility - Random Waypoint model, City Section model, Manhattan model and Gauss-Markov model.
The hop count of the stable routes determined under the City Section mobility model is the smallest for most of the operating scenarios. The hop count of the stable routes determined under the Random Waypoint mobility model is larger than those determined under the City Section mobility model by at most 10%-15%. The hop count of the stable routes determined under the Manhattan and Gauss-Markov mobility models are closer to each other, but are considerably larger than those determined under the City Section and the Random Waypoint mobility models.
As we aim for stable routes, the increase in the hop count of the paths is only sub-linear to the increase in the lifetime compared with that of the minimum hop paths. The Random Waypoint model provided the maximum increase in the path lifetime as well as the maximum increase in the hop count vis-à-vis the minimum hop paths. The City Section and Manhattan mobility models provided only a modest increase in the path lifetime and also incurred only a correspondingly modest increase in the hop count compared with that of the minimum hop paths. The Gauss-Markov mobility model too provided only a modest increase in the path lifetime and hop count in low-density networks. But, as we increase the network density, the improvement in the path lifetime is significantly high accompanied by a reasonably larger increase in the hop count of the stable paths vis-à-vis the minimum hop paths.
7 Conclusions
In conclusion, the general trend is: the more realistic is a mobility model, the larger is the number of hops in the minimum hop routes and smaller is the lifetime of stable routes determined under the mobility model. The Random Waypoint model yielded the lowest hop count for minimum-hop routes and the largest lifetime for stable routes. On the other hand, more realistic mobility models such as the Gauss-Markov model and the Manhattan model yield a relatively larger number of hops for minimum-hop routes and a relatively smaller lifetime for stable routes.
We observe a tradeoff between the objectives of optimizing the route lifetime and the hop count per path for all the four mobility models. Both of these performance metrics cannot be optimized at the same time. For a given simulation condition of network density and node mobility, the average hop count of a Minimum Hop Mobile Path is smaller than the average hop count of a Stable Mobile Path; the average route lifetime of a Stable Mobile Path is more than the average route lifetime of a Minimum Hop Mobile Path.
References
[1] C. Siva Ram Murthy and B. S. Manoj, "Routing Protocols for Ad Hoc Wireless Networks," Ad Hoc
A SIMULATION STUDY ON THE IMPACT...
Wireless Networks: Architectures and Protocols, Chapter 6, Prentice Hall, June 2004.
[2]	J. Broch, D. A. Maltz, D. B. Johnson, Y. C. Hu and J. Jetcheva, "A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols," Proceedings of the 4th Annual ACM/IEEE Conference on Mobile Computing and Networking, pp. 85-97, Oct. 1998.
[3]	T. Taleb, M. Ochi, A. Jamalipour, K. Nei and Y. Nemoto, "An Efficient Vehicle-Heading Based Routing Protocol for VANET Networks," Proceedings of the IEEE International Wireless Communications and Networking Conference, pp. 2199-2204, April 2006.
[4]	N. Meghanathan and A. Farago, "On the Stability of Paths, Steiner Trees and Connected Dominating Sets in Mobile Ad Hoc Networks," Elsevier Ad Hoc Networks, Vol. 6, No. 5, pp. 744 - 769, July 2008.
[5]	C. Bettstetter, H. Hartenstein and X. Perez-Costa, "Stochastic Properties of the Random-Way Point Mobility Model," Wireless Networks, pp. 555 -567, Vol. 10, No. 5, September 2004.
[6]	T. Camp, J. Boleng and V. Davies, "A Survey of Mobility Models for Ad Hoc Network Research," Wireless Communication and Mobile Computing, Vol. 2, No. 5, pp. 483-502, September 2002.
[7]	F. Bai, N. Sadagopan and A. Helmy, "IMPORTANT: A Framework to Systematically Analyze the Impact of Mobility on Performance of Routing Protocols for Ad hoc Networks," Proceedings of the IEEE International Conference on Computer Communications, pp. 825-835, March-April, 2003.
[8]	B. Liang and Z. Haas, "Predictive Distance-based Mobility Management for PCS Networks," Proceedings of the IEEE International Conference on Computer Communications, Vol. 3, pp. 13771384, March 1999.
[9]	J. Ariyakhajorn, P. Wannawilai and C. Sathitwiriyawong, "A Comparative Study on Random Waypoint and Gauss-Markov Mobility Models in the Performance Evaluation of MANET," Proceedings of the International Symposium on Communications and Information Technologies, pp. 894-899, September 2006.
[10]	T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, "Single-Source Shortest Paths," Introduction to Algorithms, 2nd Edition, Chapter 24, MIT Press, 2001.
[11]	A. Farago and V. R. Syrotiuk, "MERIT: A Scalable Approach for Protocol Assessment," Mobile Networks and Applications, Vol. 8, No. 5, pp. 567 -577, October 2003.
[12]	M. Abolhasan, T. Wysocki and E. Dutkiewicz, "A Review of Routing Protocols for Mobile Ad hoc Networks," Elsevier Ad Hoc Networks, Vol. 2, No. 1, pp. 1-22, January 2004.
[13]	S. P. Chaudhri, J. Y. L. Boudec, M. Vojnovic, "Perfect Simulations for Random Trip Mobility Models," Proceedings of the 38th Annual
Informatica 34 (2010) 207-221 213
Symposium on Simulation, pp. 72-79, San Diego, USA, April 2005.
[14]	M. I. M. Saad and Z. A. Zukarnain, "Performance Analysis of Random-based Mobility Models in MANET Routing Protocol," European Journal of Scientific Research, Vol. 32, No. 4, pp. 444-454, 2009.
[15]	C. E. Perkins and E. M. Royer, "Ad hoc On-Demand Distance Vector Routing," Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, pp. 90-100, February 1999.
[16]	S. A. Kulkarni and G. R. Rao, "Mobility Model Perspectives for Scalability and Routing Protocol Performances in Wireless Ad hoc Networks," Proceedings of the First International Conference on Emerging Trends in Engineering and Technology, pp. 176 - 181, July 2008.
[17]	C. E. Perkins and P. Bhagwat, "Highly Dynamic Destination Sequenced Distance Vector Routing for Mobile Computers," ACM SIGCOMM, pp. 234 -244, October 1994.
[18]	D. B. Johnson, D. A. Maltz, and J. Broch, "DSR: The Dynamic Source Routing Protocol for Multi-hop Wireless Ad hoc Networks," Ad hoc Networking, edited by Charles E. Perkins, Chapter 5, pp. 139-172, Addison-Wesley, 2001.
[19]	B. Divecha, A. Abraham, C. Grosan and S. Sanyal, "Impact of Node Mobility on MANET Routing Protocols Models," Journal of Digital Information Management, Vol. 4, No. 1, pp. 19 - 23, February 2007.
[20]	G. Ravikiran and S. Singh, "Impact of Mobility Models on the Performance of Routing Protocols in Ad hoc Wireless Networks," Proceedings of the 59th IEEE Vehicular Technology Conference (VTC 2004-Spring), Vol. 4, pp. 2185 - 2189, May 2004.
[21]	F. Bai, N. Sadagopan and A. Helmy, "The IMPORTANT Framework for Analyzing the Impact of Mobility on Performance of Routing Protocols for Ad hoc Networks," Elsevier Ad hoc Networks, Vol. 1, No. 4, pp. 383 - 403, November 2003.
[22]	W. Su, S-J. Lee and M. Gerla, "Mobility Prediction and Routing in Ad hoc Wireless Networks," International Journal of Network Management, Vol. 11, No. 1, pp. 3-30, 2001.
[23]	C-K. Toh, "Associativity-based Routing for Ad hoc Mobile Networks," IEEE Personal Communications, Vol. 4, No. 2, pp. 103-109, 1997.
[24]	S. Agarwal, A. Ahuja, J. P. Singh and R. Shorey, "Route Lifetime Assessment Based Routing Protocol for Mobile Ad hoc Networks," Proceedings of the IEEE International Conference on Communications, pp. 1697-1701, June 2000.