Int. J. Communications, Network and System Sciences, 2009, 2, 732-741
doi:10.4236/ijcns.2009.28084 blished Online November 2009 (http://www.SciRP.org/journal/ijcns/).
Copyright © 2009 SciRes. IJCNS
Pu
A Cooperative Location Management Scheme for Mobile
Ad Hoc Networks
Demin LI1, Jiacun WANG2, Liping ZHANG3, Hao LI1, Jie ZHOU4
1College of Information Science and Technology, Donghua University, Songjiang District, Shanghai, China
2Department of Software Engineering, Monmouth University, West Long Branch, NJ, USA
3College of Electronic and Electrical Engineering, Shanghai University of Engineering Science,
Songjiang District, Shanghai, China
4School of Science, Donghua University, Songjiang District, Shanghai, China
Email: deminli@dhu.edu.cn, jwang@monmouth.edu, zhangliping@sues.edu.cn, haoli@mail.dhu.edu.cn
Received July 8, 2009; revised August 17, 2009; accepted September 22, 2009
Abstract
A mobile ad hoc network (MANET) is a kind of wireless ad hoc network. It is a self-configuring network of
mobile routers connected by wireless links. Since MANETs do not have a fixed infrastructure, it is a chal-
lenge to design a location management scheme that is both scalable and cost-efficient. In this paper, we pro-
pose a cooperative location management scheme, called CooLMS, for MANETs. CooLMS combines the
strength of grid based location management and pointer forwarding strategy to achieve high scalability and
low signaling cost. An in-depth formal analysis of the location management cost of CooLMS is presented. In
particular, the total location management cost of mobile nodes moving at variable velocity is estimated using
the Gauss_Markov mobility model for the correlation of mobility velocities. Simulation results show
CooLMS performs better than other schemes under certain circumstances.
Keywords: Ad hoc Network, Grid, Home Region, Location Management, Forwarding Pointer, Cost Estimation
1. Introduction
Mobile ad hoc networks consist of wireless hosts that
communicate with each other in the absence of a fixed
infrastructure. Some examples of the possible uses of ad
hoc networks include soldiers on the battlefield, emer-
gency disaster relief personnel, and networks of laptops.
Routing a packet from a source to a destination in a mo-
bile ad hoc network is challenging because nodes in the
network may move and cause frequent and unpredictable
topological changes. Thus, when two nodes travel apart,
they may no longer have a direct link between them.
Likewise, if a node moves behind a hill, its links to its
neighbors may be severed because of fading. Other rea-
sons for changes in topology include jamming and the
entry of new nodes to the network or departure of the
existing nodes from the network.
Location management enables an ad hoc network to
track the locations of mobile terminals between call arri-
vals. Since mobile users are free to move within the cov-
erage area, the network can only maintain the approxi-
mate location of each user. When a connection needs to
be established for a particular user, the network has to
determine the user’s exact location within the defined
granularity. Location management for an ad hoc network
contains three components: location update, maintaining
home regions, and locating a node. The operation of in-
forming the home region about the current location of the
mobile user is known as location update or location reg-
istration, and the messaging cost, measured in packets
per second per node, of performing these activities is the
cost of location update. When a node moves from region
A into region B, it needs to inform nodes in region A of
its departure and meanwhile, it needs to inform nodes in
region B of its arrival. It also needs to collect location
information about all the nodes registered in region B.
The operation of these activities is known as maintaining
home regions, and the messaging cost of performing
these activities is the cost of maintaining home regions.
When a node receives a data packet for some destination,
it needs to find the current location of the destination
before sending packets to it. The operation of determin-
ing the location of the mobile user is called terminal lo-
cating or paging, and the messaging cost of performing
D. M. LI ET AL. 733
these activities is the cost of locating a node.
Several approaches have been proposed to address ad
hoc network routing and costs [1–6]. In [4] a scalable
routing protocol is presented. This protocol relies on a
location update mechanism that maintains approximate
location information for all nodes in a distributed pattern.
As nodes move, this approximate location information is
constantly updated. To maintain the location information
in a decentralized way, this paper maps a node ID to a
geographic sub-region of the network. Any node present
in this sub-region is then responsible for storing the cur-
rent location of all the nodes mapped to this sub-region.
In order to send packets to a node, the sender first que-
ries the destination’s sub-region for the approximate lo-
cation of the destination, and then uses a simple geo-
graphic routing protocol to forward the packets to the
destination’s approximate location. It is therefore easy to
see that the location update cost in this protocol is de-
pendent on the speed of node movement.
SLALoM, a grid based location management scheme,
scales well in large, mobile ad-hoc networks [5]. The
scheme divides a square into some unit regions which is
called order-1 squares. It then combines K2 of the order-1
squares to form order-2 squares. A node’s home region
will consist of an order-1 square. With some exceptions,
every node has a home region in each order-2 square. If
an original square area is A, every node has A/K2 home
regions. The scheme partitions those home regions into
near home region. By constructing the tree of home re-
gions of a node based on some rules, the location update
information of a node is easily disseminated by the span
tree. When a node moves from one order-1 to another, it
not only sends a message to its nearby home regions, but
also sends messages to the eight other home regions.
Hence the location management cost is increased.
A novel multi-level hierarchical grid location man-
agement protocol with only one home region for a node
that is called HGRID, for large scale ad hoc networks, is
introduced in [6]. The paper shows that the average per
node signaling cost in HGRID grows only logarithmi-
cally in the total number of nodes in a uniformly ran-
domly distributed network—a substantial improvement
over the signaling cost incurred by current location
management schemes. If S (source) and D (destination)
are co-located in the same grid, the location of D, as in-
dicated by the location reply, is accurate and S can for-
ward the data directly to D’s location. Otherwise, the
location is approximate, and S forwards the data packet
to the location server specified in the location reply.
When the data packet reaches the specified grid, the
server v that receives the packet checks its neighbor table
to see if D is co-located in the same grid. If so, the packet
is successfully forwarded to the destination. Otherwise,
the server searches for the D in its location database. By
construction, v must have an entry for D in its location
database. If v has accurate information about D, it further
forwards the packet to D, otherwise, the packet is for-
warded to the next location server which is in a level
lower than v in hierarchy, but has more accurate infor-
mation about D’s position. This process continues until
the packet reaches D, or it reaches a lower grid, and the
node that receives the packet drops it since it has no in-
formation about D. This can happen because D would
have left this grid, and D’s location update to its new
hierarchical leader failed to reach the leader before the
data packet was forwarded by the leader to D’s previ-
ously visited grid. Some times for location updating, the
mobile node may inform two or more leaders, and those
actions also increased the location management cost.
In order to decrease the location management cost, we
propose a cooperative location management scheme,
CooLMS, which is a nice integration of the grid model
and pointer forwarding strategy. Pointer forwarding
strategy was developed for location tracking in PCS
networks. It helps reduce the cost of location update be-
cause when a node changes its location, it doesn’t need
to update its location information in its home region. It
also helps reduce the cost of finding nodes because, with
a forwarding pointer in place, a node can find out the
location information of a destination node without the
communication to the home region of the destination
node. Pointer forwarding strategy has been recently
studied quite intensively. Some variations have been
proposed, such as a one-step painter forwarding strategy
[13], location tracking pointer forwarding [14], two-level
pointer forwarding strategy [15], K-step pointer for-
warding strategy [16], and a combination of local anchor
and forwarding pointer [17]. But to the best of our
knowledge, nobody has ever introduced the pointers for-
warding strategy into to the mobility management of
mobile ad hoc networks. With the adoption of the pointer
forwarding strategy, CooLMS reduces location update
costs significantly.
In addition to the new effective location management
scheme CooLMS, the paper also presents a more realistic
location management cost model. Considering mobile
users’ movement is generally confined to a limited geo-
graphical area, the motion velocity of a mobile node is
variable. Furthermore, the change of a mobile’s velocity
within a short time is limited due to physical restrictions.
Therefore, a mobile user’s future velocity is variable and
likely to be correlated with its past and current velocity.
The Gauss–Markov model [9] represents a wide range of
user mobility patterns, including, as its two extreme
cases, the random walk [10,11] and the constant velocity
fluid-flow models. Since it captures the essence of the
correlation of a mobile’s velocities in time, we use it to
specify the characteristics of mobile node movement.
C
opyright © 2009 SciRes. IJCNS
D. M. LI ET AL.
734
Considering the measurements of mobile motion velocity
are not necessarily consecutive, this paper presents an
approach to the total cost discrete estimation of variable
velocity mobile location management for ad hoc mobile
networks.
The rest of the paper is organized as follows. In Sec-
tion 2, we describe the cooperative location management
scheme, which is based on grids and pointer forwarding
strategy. In Section 3, we discuss the total cost of the
cooperative location management scheme under constant
velocity. Considering mobile users often travel at vari-
able velocity, total location management cost estimation
is presented based on a Gauss–Markov mobility model in
Section 4. Simulation results which compare the per-
formance of our CooLMS scheme with that of SLALoM
and HGRID schemes are presented in Section 5. Section
6 concludes the paper.
2. Cooperative Location Management
Scheme
In CooLMS, each node is assigned one and only one
home region. All nodes in a home region act as the loca-
tion server for any node in that region. This is different
from schemes that select a single node in a region as the
location server, in which the selected node can easily run
out of battery.
In this section, we introduce CooLMS and explain its
advantages over existing location management schemes.
2.1. Selection of Service Regions
We assume that mobile nodes are capable of knowing
u
Order 1 region
Order 2 region
Figure 1. The location server region of a node.
their current location, for example, using the Global Po-
sitioning System (GPS), and are equipped with radios
with certain transmission range. We also assume the
nodes move about in a square region of area A so as to
simplify the discussion. Our scheme, just like the one
reported in [5], divides the square into unit regions which
are called order-1 squares. It then merges every KK
order-1 square to form order-2 square. Figure 1 illus-
trates this idea, where solid line bordered squares are
order-2 squares and each order-2 square contains 33
order-1 squares.
Using a predefined function f, each mobile node is as-
signed a single home region based on its ID, which is an
order-1 region. The home region is also called service
region. Notice that our grid model is different from the
one proposed in SLALoM, in which every node has a
home region in each order-2 square, hence every node
has O(A/K2) home regions.
2.2. Location Management Process
The overhead cost of a location management scheme can
be divided into three parts: location update cost, location
maintenance cost and location finding cost. The location
update cost covers all the signaling messages that nodes
send to their home servers (in home region) whenever
they move to a new location. The location maintenance
cost covers all the signaling messages that nodes a) send
to their previous order-1 squares to inform them of their
departure, b) send to their current order-1 squares to in-
form them of their arrival, and c) collect as they are now
location servers for the nodes currently registered in their
order-1 squares. The location finding cost covers all the
signaling messages sent for locating a mobile node.
u
Home region
forwarding pointer
Figure 2. Home region and the forwarding pointer.
Copyright © 2009 SciRes. IJCNS
D. M. LI ET AL. 735
u
Home region
Foreign region
Figure 3. Home region and foreign region.
2.2.1. Assigning Home Regions
A predefined one-to-one mapping f is used by the
scheme to map the ID of a node to a region-1 square as
its home region. This mapping is known to every node,
so that each node can determine the home region of any
other node in constant time.
2.2.2. Maintaining Location with Forwarding
Pointers
When a node u is in the network and located in the or-
der-2 square of its home region, the home region knows
the exact location information of node u. But when the
node u moves to one of the eight sibling order-2 squares
of the order-2 square of its home region, the home region
may set a forwarding pointer to point to the order-1
square that node u arrives, as illustrated in Figure 2.
If node u is not in the eight order-2 squares nearby its
home region, the home region authorizes the order-2
square in which node u resides to select an order-1
square as its foreign region, as shown in Figure 3. The
home region of node u knows roughly (not exactly) the
location information of node u in this situation. Just like
the home region does, when the node u further moves to
one of the eight neighboring order-2 squares of the or-
der-2 square of its foreign region, the foreign region may
set a forwarding pointer to point to the order-1 square
that node u arrives.
2.2.3. Locating a Node
When a source node S wants to send data packets to a
destination node D, S finds the home region of D using
the D’s ID and mapping f. It then sends a query packet to
this home region to inquire of D’s location. Four cases
arise:
D
H
S
3
1 2
(a)
H
D
S
3
1
2
(b)
1
H
F
S
D
2
3
4
(c)
H
D
S
F
1
2
3
4
(d)
Figure 4. The location discovery process. (S: source node; D:
destination node; H: home region; F: foreign region; 1, 2, 3,
and 4: the order of the location discovery process)
C
opyright © 2009 SciRes. IJCNS
D. M. LI ET AL.
736
1) If D is in the order-2 square of its home region, S
requests the location information of destination node D,
the home region sends directly the location information
of node D to source node S, and S can send directly the
data packets to destination node D using this information,
as shown in Figure 4(a).
2) If D is in one of the eight neighboring order-2
squares to its home region order-2 square, S sends re-
quest to the home region of D. S can send directly the
data packets to destination node D using this information,
as shown in Figure 4(b)
3) If D is in the order-2 square of its foreign region,
the home region sends the location information of the
foreign region to source node S, and S requests D’s for-
eign region for D’s location information. After this process,
the data packets from S can be retransmitted by the home
region and foreign region to D, as shown in Figure 4(c).
4) If D is in one of the eight sibling order-2 squares to
its foreign region order-2 square, S sends data packets to
the foreign region, and the foreign region retransmit the
packets by forwarding pointer to destination node D, as
shown in Figure 4(d).
2.3. Forwarding Pointers
When mobile node u leaves the order-2 square of its
home region, the home region sets a forwarding pointer
pointing to the order-1 square where u arrives. The for-
warding pointer is called first class forwarding pointer,
and the order-1 square that node u arrive is called a for-
eign region. When u further moves to another sibling
order-1 square as shown in Figure 5, the previous order-1
square can generate a forwarding pointer pointing to the
new order-1 square where u is currently located; it
8 4
3
2
1
Home region
Foreign region
Figure 5. The process of setting up forwarding pointers.
de
process of setting up forwarding
po
the process that increasing the number of
fo
this section, we discuss how to evaluate the total loca-
rk under study is
in
notations in this section:
oesn’t need to inform its home region. This reduces th
updating and paging packets cost. We call the forwarding
pointer generated by order-1 squares the second class
forwarding pointer.
We illustrate the
inters in Figure 5. The square filled with horizontal
strips is the home region of node u, while the square
filled with vertical strips is its foreign region. The arrow
from the home region to the foreign region is the first
class pointer, while the arrows around the foreign region
are the second class forwarding pointers. If u moves
from the foreign region to the square numbered 4, a sec-
ond class forwarding pointer is set to indicate the current
location of u. Similarly, if it moves to the square num-
bered 5 from the one numbered 4, another second class
forwarding pointer is set pointing to the square numbered
5, and so on.
We see from
rwarding pointers will reduce the location updating
cost, but may also increase the paging cost. It is a trade-
off phenomenon in location management. If a node
moves across many region-2 square, we can further setup
forwarding pointers from one foreign region to another
around its home region, just like the process of set-
ting up forwarding pointers from one order-1 region to
another neighboring foreign region as shown in Figure 5.
We will discuss the optimal number of forwarding
pointers in Section 5.
3. The Cost of Cooperative Location
Management
In
tion management cost, which is measured in packets per
second per node to transfer. We assume that nodes dis-
tribute uniformly, move randomly and independently of
each other. Each node selects a direction to move, chosen
uniformly between [0, 2
]. Each node selects its speed,
chosen uniformly between [v-c, v+c] for some time t,
where the t is exponentially distributed with a mean of
.
After a mobile has traveled for time t, it selects another
direction, speed and time to travel. The mobility model
and the geographic routing algorithm, MFR (most for-
ward with fixed radius routing, which forwards packets
to the neighbor closest to the destination node) [12] is the
same as in [5] and [6], which allows us to compare our
scheme’s performance with [5] and [6].
We also assume that the ad hoc netwo
a rectangular region; all nodes in the network are
equipped with Global Positioning System (GPS) that
provides them with their current location; they are aware
of the identities of their neighbors; and each node has a
unique ID (such as an IP address). We use the following
Copyright © 2009 SciRes. IJCNS
D. M. LI ET AL. 737
g pointer number
is divided into
A area of the total networks
N number of nodes
M the threshold of forwardin
K network area A2
K
or
b b cost in a region
)
pdate message to ho
γ density of nodes in ad hoc networks
r
ion parameter of the data packet
tionedregions or squares. Based on the distribu-
tio
al to the number of transmissions
s proportional to the side of an order-1
der-1
squares
a area of a order-1 region
roadcast
v speed (meters per second
u cost of sending location ume
s
region
cost of collecting location information
average
radius of a node
z average distance for one hop of a node
λ Poisson distribut
arrive at
As mentioned in Section 2, the network area is parti-
into unit
n and mobility assumption made in the beginning of
the section, the size of the unit region is chosen so that its
average node density γ is approximately a constant. Thus,
the total area of the networks A = N/
, Woo and Singh [4]
noted the following:
1) The cost of broadcasting in an order-1 square by a
node, b, is proportion
needed to cover the said square. The latter is in turn pro-
portional to the area of the order-1 square divided by the
area covered by a single transmission, and also is the
location updating cost for just only time. Thus, b =
O(a/r2).
2) The distance a node u has to cover to cross an or-
der-1 square i
square. Thus, the number of order-1 squares that a node
crosses per second, is proportional to )/(
1avOn .
3) Similarly, the number of order-2 squares that a
node u crosses per second, can also be estimated by
)/()/( 12 aKvOKnOn  order-1 squares per second.
4) The cost of updating all severing region include
ns and order-1 squares estimated foreign regioby
)/()/(13aMvOMnOn .
3.1. Cost of Location Update
current region and en-
rs a new region, three cases of location update may
me region, the home region knows the exact lo-
eight order-2 squares of its home region
e home region
When a node u moves out of the
te
occur:
1) When the new region locates in the order-2 square
of its ho
cation information of node u. In this case, we only
broadcast the n1 order-1 nodes. The location update cost
is O(n1(b)).
2) When the node u moves to one of the other
neighboring
order-2 square, the home region may set a forwarding
pointer to point the order-1 square that node u arrives.
The location update cost is O(n2(b+K/z)).
3) When the node u is not in the nine order-2 squares
nearby its home region discussed above, th
authorizes the order-2 square where the node u locates to
select an order-1 square as a foreign region of the node u.
The home region of node u knows roughly the location
information of node u in this situation. Just like the home
region does, when the node u moves to one of the other
eight order-2 squares (not include the order-2 square the
foreign region locates) that neighbor to the order-2
square of its foreign region, the foreign region may set a
forwarding pointer to point to the order-1 square that
node u arrives. The location update cost is O(n3
(Ab/K2+A/K)).
So, the total location updating cost cu is given by
)(
))
11
))//()/()(( 2
321
NaNvKavav
KAKAbnzKbnbnOcu
()((
2
2222
MK
vN
MK
vN
K
v
vO
K
Kr
aM
z
r
aK
r
a
O



3.2. Cost of Maintaining Location Information
of
e existence of base stations. However, in mobile ad hoc
location server in the new order-1 region,
the
m
There is no such a cost in cell phone network because
th
networks, when a node moves from region A into region
B, it needs to inform nodes in region A that it has left and
meanwhile, it needs to inform nodes in region B of its
arrival. The nodes need to take three steps to maintain
location information, namely
1) Inform the original order-1 region of its depar-
ture;
2) Inform the new order-1 region of its arrival;
3) As a
cache the registration information of nodes in
region.
So the cost for maintaining nodes location information
c is
)())
2
((
))2(())(( 11 bnObbnOcm

2vO
r
a
a
v
O
3.3. Cost of Finding Nodes
might be zero or a con-
ant if either the node itself or one of its neighbors has
The cost of finding the location
st
the location information available in a cache, which
happens if there are several packets destined for the same
destination. In our analysis, however, we make the pes-
simistic assumption that the location information is not
cached; therefore, the source node needs to contact the
destination node’s home region to find the destination’s
location.
C
opyright © 2009 SciRes. IJCNS
D. M. LI ET AL.
738
from the four cases described in Subsection
2.
estination B, node A queries the home region of
t and sec-
The location finding process includes two situations
(combined
2.3)
1) When the source node A wants to send data packets
to its d
node B. If node B is in its home region, then node A di-
rectly sets up a linkage with node B. From Figure 4 (a)
we can deduce the cost is asymptotically to3d(S, H)/z,
where d(S, H) is the distance between the source node S
and the home region, and it is proportional to K. So we
know that the location finding cost is proportional to K.
Similarly, from Figure 4 (b) we can also conclude that
the location finding cost is proportional to K;
2) If node B is not in its home region, then node A sets
up a linkage through B’s home region, the firs
ond class forwarding pointers, and then sends packets
using this linkage. From Figure 4 (c) and (d), the location
finding cost is asymptotically to [2d(S, H) + d(S, F)]/z,
where the d(S, F)] is the distance between the source
node S and the foreign region, and it is proportional to K.
For forwarding pointer cost, we can easily get that it is
proportional to M and
.
So the average total cost of locating a node is
/(( zOc )/() zMOK
d
3.4. The Total Cost of Location Management
2
(1)
el Based Total
.1
during the
ourse of motion. We assume that mobile nodes move at
The total cost of location management
2
()
(2// (
totalum d
cNccc
OvNNMKN vNK vNKM

 
2
)/ ())vN KM
4. Gauss-Markov Mod
Location Management Cost Estimation
. Gauss – Markov Mobility Model 4
Mobile nodes often have to change speed
c
inconstant velocity and the velocity change follows a
Gauss–Markov process. According to [9], the 1-D dis-
crete version of the Gauss-Markov mobility model can
be described as:
1
2
1 nn vv
1)1(
 n
w

(2)
where is a node’s mobile velocity duri
period
n
v
,
ng the n-th
is the memory level, which reflects the rela-
tionshipetween 1n
v and n
v,
b
the mean of n
v,
2
the variance of v, and n
w an uncorrelated Gaus-
sian process with zerean, unit variance. n
w is inde-
dent of v.
Let
n
o m
pen n
nn vu ,2
1

, the Equat (2) can
be rewritten th
ion
ine following simple and clear form
n
unn wu
1 (3)
4.2. Total Location Manageme
al costs in-
maintaining
nt Cost
After we have estimated each of the individu
olved in location updating information, v
location information and finding the location information,
we can estimate the total cost of routing packets. Assume
that packets arrive at each node at a rate of λ packets per
second according to a Poisson process. Then the average
cost of routing N nodes can be calculated as (1). Recall
the assumption that mobile motion process is Gauss–
Markov. Let
nn uv (4)
We know from Section that the location updating cost
vKvOcu1
)(
, the maintaining location cost m
c
2
()Ov Kv
, and the finding node cost is constant 3
K.
st 321)(KvKKctotal 
So the total co
. Substit
we obtain
1
(
(
K
Kctotal

uting
v with (4),
3212
321
)()
))(
KKKuK
KuK
n
n


(5)
Let
21KK
321 )(KKK
(6)
Then it follows from (5) and (6) that
nn uc
Fr
where the is the initial value of. It results from
(7) that
(8)
Consider is an uncorrelated Gaussian
with zero munit variance, and is independent
of
(7)
om (3), we have
0
0)(
n
k
kn
kn wu

1
n
u
0
u n
u


])([
0
0
k
knn wuc
1n
kn
n
w
ean,
ea
process
n
w
n
v, then mn and variance of n
care given as

n
nuEc 0
2
22
1)1(
n
n2
0
222
1



k
k
n
Dc
Copyright © 2009 SciRes. IJCNS
D. M. LI ET AL.
739
When the memory level 10
, we have
 n
nEclim
2
22
1
lim
 n
nDc
We give approximate estimation of the total cost of
location management in this section, and we will give
some simulation results in the next section.
t the simulation results for
HGRID [6] in network time
elay and total location management cost, using OPNET
is operated in conjunction with IP as
th
5. Simulation Results
In this section, we presen
CooLMS, SLALoM [5] and
d
technology [18].
To compare the performance of these three schemes, a
location management layer was built in to the TCP/IP
protocol stack that
e network layer protocol. Main data structures [6] in
the location management layer consist of a location table
SLALoM
HGRID
CooLMS
(
2
)
16
14
Delay (/second)
12
10
8
6
4
2
0
0 500 1000
The Number of Nodes
1500 2000 2500 3000
(a) M=2 for time delay
SLAL oM
HGRID
CooLMS
(
3
)
0 500 1000
The Number of Nodes
1500 2000 2500 3000
Delay (/second)
16
14
12
10
8
6
4
2
0
0500 1000
The Number of Nodes
1500 2000 2500 3000
Delay (/second
)
16
14
12
10
8
6
4
2
0
SLALoM
HGRID
CooLMS
(
4
)
(c) M=4 for time delay
0500 1000
The Number of Nodes
1500 2000 2500 3000
Delay (/second)
16
14
12
10
8
6
4
2
0
SLALoM
HGRID
CooLMS
(
5
)
(d) M=5 for time delay
0500 1000
The Number of Nodes
1500 2000 2500 3000
Delay (/second)
16
14
12
10
8
6
4
2
0
SLAL o M
HGRID
CooLMS
(
6
)
(e) M=6 for time delay
Figure 6. Network time delay.
and a neighbor table. When a location server node re-
ceives a location update packet from a node, the current
location of that node is updated in the location table.
(b) M=3 for time delay
C
opyright © 2009 SciRes. IJCNS
D. M. LI ET AL.
740
MFR [12] without backward progression, in which pack-
ets are dropped if no forward progress can be made, was
implemented as the geographic routing algorithm.
We assume that nodes distribute uniformly, move ran-
domly and independently of each other. Each node se-
lects a direction to move, chosen uniformly between [0, 2π].
0 500 1000
The Number of Nodes
1500 2000 2500 300
0
Over head (/second)
100
200
300
400
500
600
700
800
900
1000
SLALo M
HGRID
CooLMS
0
(
2
)
(a) M=2 for overhead
Over head (/second)
700
800
900
0
100
200
300
400
500
600
0 500 1000
The Number of Nodes
1500 2000 2500 3000
1000
SLALoM
HGRID
CooLMS
(
3
)
(b) M=3 for overhead
Over head (/second)
0
100
200
300
400
500
600
700
800
900
1000
The Number of Nodes
0 500 1000 1500 2000 25003000
SLAL oM
HGRID
CooLMS
(
4
)
SLALoM
HGRID
CooLMS
(
5
)
The Number of Nodes
0500
1000 1500 2000 2500 3000
Over head (/second)
0
100
200
300
400
500
600
700
800
900
1000
(d) M=5 for overhead
SLALoM
HGRID
CooLMS
(
6
)
0500 1000
The Number of Nodes
1500 2000 2500 3000
Over head (/second)
0
100
200
300
400
500
600
700
800
900
1000
(e) M=6 for overhead
Figure 7. Location management overhead.
Each node selects its speed, chosen uniformly between [0,
10m/s] for some time t, where t is exponentially distrib-
uted with mean τ. After a mobile has traveled for certain
time t, it selects another direction, speed and time to
travel. The topology consists of from 50 to 3000 nodes.
When the number of nodes increase, the areanetwork
time delay and total location management cost. As
shown in Figure 6, there is a tradeoff between paging,
updating cost and network time delay. We can balance
the tradeoff by selecting the threshold of forwarding
pointer number. When threshold of forwarding pointer
number M = 3 and 4, the network time delay with
CooLMS is lower t SLALoM and
HGRID; when threshold of forwarding pointer number
M = 2 and 5, the network time delay with CooLMS is
between the networks with SLALoM and HGRID; When
threshold of forwarding pointer number M = 6, the net-
work time delay with CooLManet is higher than the
networks with SLALoM and HGRID.
Figure 7 shows that when the threshold of forwarding
pointer number M =3 and 4, the total location manage-
han the networks with
(c) M=4 for overhead
Copyright © 2009 SciRes. IJCNS
D. M. LI ET AL.
Copyright © 2009 SciRes. IJCNS
741
ment cost with CooLManet is lower than the networks
with SLALoM and HGRID; When the threshold of for-
warding pointer number M = 2 and 5, the total location
management cost with CooLMS is between the networks
with SLALoM and HGRID; When the threshold of for-
warding pointer number M = 6, the total location man-
agement cost with CooLManet is higher than the net-
works with SLALoM and HGRID.
We conclude from the simulation that using suitable
number of forwarding pointers including the first and
second pointers, the network time delay and location
management cost can be reduced significantly.
6. Conclusions
We proposed a coopanagement scheme,
CooLM com-
bines the strength of grid ased location management
] T.-W. Chen and M. Gerla, “Global state routing: A ne
for ad-hoc wireless networks,” Proceed-
ternational Communications Conference,
1998.
[3] Y.-B. Ko and N. H. Vaidya, “Location-aided routing
l Sym-
posium on Computers and Communications, pp. 525–530
] J. Zhou, B. Tang, and D. Li, “Partition digraph for loca-
date
der delay constraints,” ACM-Baltzer J. Wire-
Vol. 1, pp. 413–425, December 1995.
1] Y.-B. Lin, “Reducing location update cost in a PCS net-
4 1986.
ol. 15, No. 8, pp. 1455–1466, 1997
[18] http://www.opnet.com/solutions/network_rd/modeler.html.
erative location m
S, for mobile ad hoc networks. CooLMS
b
and cooperative location management to achieve low
signaling cost as well as high scalability. We also dis-
cussed the total cost estimation of mobile location man-
agement for ad hoc mobile networks with missing meas-
urements. Simulation results indicate that the network
time delay and location management cost can be reduced
significantly by using suitable number of forwarding
pointers. Practically, the CoolMS scheme is good for
networks used in metropolis areas where mobile users
typically travel across several location areas from home
to work on a daily basis.
Our future work includes location management for spe-
cial routing protocols and location management for QoS of
mobile decision support in ad hoc mobile network.
7. Acknowledgment
This work is partially supported by NSFC granted number
60874113 and 70271001; China Postdoctoral Fund granted
number 2002032191; Shanghai Fund of Science and Tech-
nology granted number 00JG05047; Shanghai Key Scien-
tific Research Project under grant number 05dz05036; and
2008 Fund of Engineering Research Centre of Digitized
Textile & Fashion Technology, Ministry of Education.
8. References
[1] J. Broch, D. A. Maltz, D. B. Johnson, Y.-C. Hu, and J.
Jetcheva, “A performance comparison of multi-hop wire-
less ad hoc network routing protocols,” Proceedings of
4th Annual Conference on Mobile Computing and Net-
working, Dallas, TX, October 25–30, 1998.
[2 w [1
routing scheme
ings of IEEE In
(LAR) in mobile ad hoc networks,” Proceedings of 4th
Annual Conference on Mobile Computing and Network-
ing, Dallas, TX, October 25–30, 1998.
[4] S. M. Woo and S. Singh, “Scalable routing protocol for
ad hoc networks,” Wireless Networks, Vol. 7, pp. 513–
529, 2001.
[5] C. Cheng, H. Lemberg, S. Philip, E. van den Berg, and
Tao Zhang, “SLALoM: A scalable location management
scheme for large mobile ad-hoc networks,” Proceedings
of IEEE Wireless Communications and Networking
Conference, Vol. 2, pp. 574–578, March 2002.
[6] S. J. Philip, J. Ghosh, and C. M. Qiao, “Performance
evaluation of a multilevel hierarchical location manage-
ment protocol for ad hoc networks,” Computer Commu-
nications, Vol. 28, pp. 1110–1122, 2005.
[7] S. M. S. Masajedian and H. Khoshbin, “Cooperative lo-
cation management method in next generation cellular
networks,” Proceedings of the Ninth Internationa
2004.
[8
tion area management in mobile computing environ-
ment,” International Journal of Nonlinear Sciences and
Numerical Simulation, Vol. 5, No. 4, pp. 393–396, 2004.
[9] B. Liang, and Z. J. Haas, “Predictive distance-based mo-
bility management for multidimensional PCS networks,”
IEEE/ACM Transactions on Networking, Vol. 11, No. 5,
pp. 718–732, 2003
10] J. S. M. Ho and I. F. Akyildiz, “Mobile user location up[
and paging un
less Networks,
[1
work,” IEEE/ACM Trans. Networking, Vol. 5, pp. 25–33,
February 1997.
[12] T.-C. Hou and V. O. K. Li, “Transmission range control in
multihop packet radio networks,” IEEE Transactions on
Communications, Vol. COM-34, No. 1, pp. 38–4
[13] K. Sue and C. Tseng, “One-step pointer forwarding strat-
egy for location tracking in distributed HLR environ-
ment,” IEEE Journal on Selected Areas in Communica-
tions, V
[14] Y. Lin and W. Tsai, “Location tracking with distributed
HLR’s and pointer forwarding,” IEEE Transaction on
Vehicular Technology, Vol. 47, No. 1, pp. 58–64, 1998
[15] W. Ma and Y. Fang, “Two-level pointer forwarding strat-
egy for location management in PCS networks,” IEEE
Transaction on Mobile Computing, Vol. 1, No. 1, pp.
32–45, 2002
[16] C.-M. Weng and C.-H. Chu, “K-step pointer forwarding
strategy for location tracking in distributed HLR envi-
ronment,” IEE Proceedings of Communications, Vol. 150,
No. 3, pp. 207–213, June 2003.
7] W. Ma and Y. Fang, “An efficient mobility management
scheme based on location anchoring and pointer for-
warding,” IEEE 58th Vehicular Technology Conference,
VTC’03-Fal1, Vol. 4, pp. 2764–2768,6-9 October 2003.