I

A Mobility Based Metric for Clustering in Mobile Ad Hoc Networks

Prithwish Basu Naved Khan Thomas D. C. Little
Department of Electrical and Computer Engineering
Boston University, Boston MA
I {pbasu,naved,tdcl} @?bu.edu
Abstract Several protocols have been proposed in the literature
for routing over multiple hops in MANETs, the notable
This paper presents a novel relative mobility metric f o r ones being AODV [16] and DSR [lo]. As the size of a
mobile ad hoc nehvorks (MANETs). It is based on the ratio MANET grows, flat routing schemes do not scale well
of power levels due to h x e s s i v e receptions at each node in terms of performance. Routing protocols such as DSR
from its neighbors. We propose a distributed clustering (Dynamic Source Routing) [ 101 which discover routes by
algorithm, MOBIC, based on the use of this mobility metric reactive flooding, and perform well for small networks,
I
f o r selection of clusterheads, and demonstrate that it leads can result in low bandwidth utilization in large networks
I
to more stable clusterf o y a t i o n than the “least clusterhead under high load due to longer source routes (and thus, a
change” version of the /well known Lowest-ID clustering large byte overhead) [9]. Hence, hierarchical organization
algorithm 131. We show reduction of a s much a s 33% in the is beneficial in large MANETs for solving this problem.
rate of clusterhead changes owing to the use of the proposed Several clustering strategies have been proposed for
technique. In a MANET that uses scalable cluster-based imposing a semi-hierarchical structure upon nodes in a
services, network performance metrics such a s throughput MANET in order to increase scalability in routing, improve
and delay are tightly coupled with the frequency of cluster bandwidth utilization, and to reduce delays for route
reorganization. Therefore, we believe that using MOBIC queries [4,5, 13, 12, 17, 81.
can result in a more stable configuration, and thus yield The primary step in clustering is the election of nodes
better pelformance. I called clusterheads and the formation of clusters around
them. A clustering algorithm known as Lowest-ID
(clusterhead selection based on a unique ID) has been
1. Introduction proposed in the past [4] and has been revisited later in the
“multimedia multihop mobile networks” context [5]. In
If an existing communication infrastructure is expensive [3], Chiang et al. have shown that the Lowest-ID algorithm
or inconvenient to use or setup, or if it is absent, mobile performs better than the max-connectivity algorithm
users with wireless connectivity can still communicate with (where clusterhead selection is done based on node degree
each other by the formation of a mobile ad hoc network [5]) in terms of stability of clusters, which is measured by
(MANET). Nodes in a MANET can act as both hosts and the rate of clusterhead changes. They have also proposed
routers since they can generate as well as forward packets, a small change in the Lowest-ID algorithm to improve
respectively. Since there is no existing communication performance; the improved version is referred to as LCC
infrastructure (e.g., a wired or a fixed wireless base station), which stands for “Least Clusterhead Change.”
nodes in a MANET arej expected to act cooperatively to We believe that since mobility is the main cause for
establish the network “on-the-fly’’ and route data packets the changes in clusterheads and cluster memberships, it
possibly over multiple hops. is logical to have a mobility metric as a basis of cluster
Traditional applications of such rapidly deployable formation and clusterhead selection. This paper presents a
network architectures are in battlefield and disaster novel mobility metric that is based upon the ratio between
relief scenarios, one of the first examples being the the successive measurements of received power at any
DARPA Packet Radio Network PRNET [ 111. However, node from its neighbors. We then present a variant of
considerable interest in MANETs has been shown recently the Lowest-ID algorithm called MOBIC, which uses the
in the commercial sector owing to the miniaturization new mobility metric for cluster formation. We show by
in size of computing devices, the proliferation in their simulations that MOBIC results in more stable cluster
number, and the increasing demand of people to stay formation as it yields as much as 33% reduction in the rate
connected all the time. The advent of low power wireless of clusterhead changes over the LCC algorithm.
communication technologies such as Bluetooth [ 11 can The rest of the paper is organized as follows: in Section
propel ad hoc networks to becoming an enabling platform 2, a summary of related work is presented. Section 3
€or what is known as pervasive computing. proposes a new mobility metric, and describes how it can

413
$10.000 2001 IEEE
0-7695-1080-9/01
be used for clustering. Section 4 describes some simulation depend on classic flooding for routing.
results. Section 5 concludes the paper and discusses some Lowest-ID clustering was generalized to a weight based
directions of future research. clustering technique, referred to as DCA (Distributed
Clustering Algorithm) in [2]. In DCA, each node is
2. Background and Related Work assumed to have a unique weight (hence the weights
are totally ordered) instead of just the node ID, and the
2.1. Clustering in MANETs clustering algorithm uses the weights instead of the IDS for
the selection of clusterheads. However the technique of
In any complex distributed system, clustering of nodes assignment of weights has not been discussed.
into groups results in simplification of addressing and In this paper, we do not investigate clustering algorithms
management and also yields better performance since that generate clusters which may be greater than two h.ops
details about the remote portions of the network can be in diameter (such as the ones proposed in [ 12, 171). Cluster
handled in an aggregate manner. For example, in the wired maintenance is complicated in such-schemes, especially in
Internet, essential services like addressing and routing are high mobility scenarios, and can result in much overhead.
highly scalable owing to hierarchical organization.
In the context of mobile multihop wireless networks, 2.2. Mobility Metrics
Ephremides et al. [4] introduced the notion of cluster-based
organization through the concept of a distributed In [9], a geometric mobility metric has been proposed to
“linked cluster architecture”, which was mainly used capture and quantify the relative motion of nodes. The
for hierarchical routing, and for network adaptability to mobility measure between any pair of nodes is defined as
changes in connectivity. More recently, these ideas were their absolute relative speed taken as an average over time.
revisited in the context of a MANET [5, 171. In order to arrive at the aggregate mobility metric for a
Lowest-ID clustering is one of the most popular particular scenario, the mobility measure is averaged over
clustering schemes used in the old [4] as well as recent all pairs of nodes. This metric has certain deficiencies with
[5, 81 ad hoc networks literature. In [ 5 ] , Gerla et al. respect to clustering: First, it assumes a GPS like scheme
propose a simple distributed clustering algorithm that for calculation of relative speeds; in a MANET, especially
yields clusters that are at most two hops in diameter. In in the indoors, we cannot assume the existence of CiPS,
each cluster, exactly one node, the one with the lowest ID and so we have to resort to other techniques for measuring
among its neighbors, becomes a clusterhead, and maintains relative mobility. Secondly, it is an “aggregate” mobility
cluster-memberships of other member nodes. metric and does not characterize the local movement of the
The Lowest-ID algorithm proceeds as follows and results nodes in the neighborhood of a particular node, which is
in the formation of clusters which are at most two hops the primary reason for clusterhead changes.
in diameter: ( I ) Each node is given a distinct ID and it The Reference Point Group Mobility Model (RPGM)
periodically broadcasts the list of its neighbors (including proposed in [7] was not used as a basis for cluster
itself). (2) A node which only hears nodes with ID higher formation, but can be useful for predictive group mobility
than itself is a “clusterhead” (CH). (3) The Lowest-ID node management. In RPGM, each group has a logical “center”
that a node hears is its clusterhead, unless the Lowest-ID and the center’s motion defines the entire group’s motion
specifically gives up its role as a clusterhead (deferring to behavior including location, velocity, acceleration etc.
a yet lower ID node). (4) A node which can hear two or An associativity based routing (ABR) protocol that uses
more clusterheads is a “gateway”; otherwise, a node is an mobility for routing has been proposed for MANETs [ 181.
ordinary node. ABR does not define a mobility metric but uses a route
In [3], the Lowest-ID algorithm was improved by its stability metric that is used by the routing protocol. [n a
variant, LCC (Least Clusterhead Change) by imposing an MANET where routes become stale by a mobile host’s
additional rule on the clustering process: if a member (ID movement, ABR employs a routing scheme where a route
= i) of cluster C moves within range of another cluster C’ is selected based on nodes having associativity states that
with higher ID, then do not perform re-clustering unless i imply a period of stability.
is the clusterhead of C. This helps in drastically reducing McDonald and Znati have proposed a framework for
the number of “clusterhead changes” due to re-clustering. dynamically organizing mobile nodes in a MANET into
This approach too results in formation of clusters which clusters but their focus in that work is on mathematical
are 2 hops in diameter and converges in O(d) time, where characterization of the probability of link and path
d is the diameter of the network. The clusterhead takes availability as a function of a random walk based mobility
the responsibility of coordinating transmissions of packets model [ 141. However, this probability based approach does
and route discovery, and thus the network does not have to not capture the relative mobility of any node with respect

414
 XI
x2 on the physical distance between the transmitter and the
receiver, i.e. & oc $ [ 6 ] . But in real life, an exact
@
,

\ /I@ M y = f(re1ative mobilities)

X

__-- - -.0 \ location

old RxPr ~
moved to new calculation of the distance between a transmitter and a
0::: - - - - _ _ _ _ _ _ _ _ _ _ receiver may not be possible from the measured signal
y newRxR powers owing to the complexities involved in accurate
channel modeling. However, from the ratio of RxPr
x4
between two successive packet transmissions (periodic
"hello" messages) from a neighboring node, we can get
Figure 1. Calculation of Aggregate Relative Mobility - good knowledge about the relative mobility between the
(a) "Hello" packet reception at Y from neighbors two nodes'. Hence, we define the relative mobility metric,
(b) Successive Rx Power Measurements at Y due to X M F 1 ( X ) ,at a node Y with respect to X as:
to its neighbors and therefore it is not an adequate metric
R x P T ~ ~ ~
for 2 hop clustering. M F l ( X ) = lolog,, (1)
We can see that none of the metrics described above RXPT~!~
are suitable for characterizing the relative mobility of
If R x P T ~ T < ~RxPr?!y, then h4F1(X)< 0, and
nodes in a particular node's neighborhood in a MANET.
a negative value of the relative mobility metric between
Hence, we feel that there is a need to develop such a metric
any two nodes will indicate that the two nodes are moving
which can be used for clustering. In the next section, we
away with respect to each other. On the other hand, if
propose a metric for capturing the mobility in every node's
neighborhood, and then use it for stable cluster formation.
R x P T ~ > ~RxPr0ld,
~ then Mrer is positive, and that
indicates that the nodes are moving closer to each other. For
a node with m neighbors, there will exist m such values for
3. Mobility Based 2-Hop Clustering MF1.This situation is depicted in Figure 1.
We calculate the aggregate local mobility value MY
In this section we describe our mobility metric and discuss at any node Y by calculating the variance (with respect
how it can be used in formation of clusters which are at to zero) of the entire set of relative mobility samples
most 2 hops in diameter. The Lowest-ID algorithm and its M F 1 ( X i ) where
, X i is a neighbor of Y :
LCC variant do not "couple" the clustering process with the
mobility of the nodes. If a node with a low ID happens to M y = w ~ T ~ { M F ; " ' ( X=~-?3[(hfF;"')2]
)}G~ (2)
be highly mobile, it will cause severe re-clustering to occur
periodically when it moves into the transmission range of In this manner, any node Y which also acts as a receiver
other clusterheads. In such occasions the lower ID node measures the power levels in successive transmissions from
will prevail and re-clustering will happen. all its neighbors and a variance of these values (with respect
The basic idea in this paper is that the clustering process to zero) is a representative value for the aggregate relative
should take into account the mobility of the individual mobility metric M y for that node. The rationale behind
nodes with respect to its neighboring nodes. A node should this calculation is that a low value of M y indicates that
not be elected a clusterhead if it is highly mobile relative to Y is relatively less mobile with respect to its neighbors,
its neighbors, since, in that situation, the probability that a On the contrary, a high value of MY indicates that Y
cluster will break and that re-clustering will happen is high. is highly mobile with respect to its neighboring nodes.
Instead, we should attempt to select a node that is less As mentioned earlier, the nodes that have low aggregate
mobile relative to its neighbors for the role of a clusterhead. relative mobility with respect to their neighbors, should be
The mobility metric proposed in this paper does not favored for becoming clusterheads. The calculation of this
assume the availability of any absolute location information mobility metric is a simple task that can be achieved in a
(e.g. GPS) at a node. It also does not assume availability of distributed manner, and the measurement of the incoming
velocity information at every node. signal power is easily possible with existing hardware.
Only transmissions that are successfully received by the
3.1. An Aggregate Local Mobility Metric MAC layer should be considered.
We believe that the variation in received signal power is
In our solution, in order to model mobility, we purport that a better indicator of mobility than pure distance or speed
the signal power detected at the receiving node, RxPT, owing to environmental characteristics. For example, the
is indicative of the distance between the transmitting and communication between two nearby cars on a street with
receiving node pairs. In the ideal situation, Friis' free space dense foliage is more likely to suffer from high attenuation
propagation model is used, which uses an inverse-square We do not consider the effects of multipath, and small-scale and large-
dependence of the ratio of received and transmit power scale fading in this study.

415
of signal strength than that between two cars that are farther 4. In case where the mobility metric of two clusterhead
away on a clear road. In reasonably short time scales (a few nodes is the same, and they are in contention for
seconds), since the surrounding environment is unlikely to retaining the Cluster-Head status, then the selection of
change significantly, the variation in received signal power the clusterhead is based on the Lowest-ID algorithm
is a good indicator of local mobility. wherein the node with the lowest ID gets the status of
Since the calculation of the relative mobility metric the Cluster-Head. If a node with Cluster-Member status
MZ;“’(X) needs two successive packet transmissions, we with a low mobility moves into the range of another
require that the time interval after which the aggregate Cluster-Head node with higher mobility, re-clustering is
mobility metric M y is calculated at Y should include two not triggered (similar to LCC [3]).
successive “hello” message transmissions from all Y’s 5. In a mobile scenario, if two nodes with status
neighbors. It is possible that during that time interval, Cluster-Head move into each other’s range, re-clustering
certain nodes move out of/come into range of node Y. We is deferred for Cluster-Contention-Interval (CCI) to allow
use a heuristic to tackle this problem: nodes which do for incidental contacts between passing nodes. If the nodes
not participate in two successive transmissions to node Y are in transmission range of each other even after the
are excluded from the calculation. Therefore, only those CCI timer has expired, re-clustering is triggered, and the
nodes which have been in the neighborhood of Y for that node with the lower mobility metric assumes the status of
particular time interval are considered for the mobility Cluster-Head.
metric calculation. This calculation is performed at every The following argument proves that MOBIC yields
node, and thus, each node will maintain an aggregate clusters of diameter <_ 2 hops, and no two clusterheads are
relative mobility metric. in range of each other: It has been shown in [2] that far a
totally ordered and static weight distribution, a distributed
3.2. MOBIC Clustering Algorithm algorithm similar to Lowest-ID yields clusters that satisfy
the above properties. In our case, however, the weights
In order to use the mobility metric presented in the previous (Aggregate Local Mobility Metric) may not be totally
section for clustering, we propose a two step distributed ordered and may be changing dynamically. If all nodes
clustering algorithm, MOBIC, which is similar in execution have different values of aggregate local mobility ( M ) ,
to the Lowest-ID algorithm as described in Section 2.1, then the weights (mobility metric) will be totally ordered
except that the mobility metric is used as a basis of cluster and MOBIC will result in clusters which obey the above
formation instead of ID. We describe our algorithm in the properties. This situation is likely to happen most often
following steps: since the nodes are mobile and the variance of relative
1. All nodes sendreceive “Hello” messages to/from their mobilities is being calculated using double precision
neighbors. Each node measures the received power levels arithmetic in every node’s local neighborhood.
of two successive transmissions from each neighbor, and However, if a few nodes within the transmission range
then calculates the pairwise relative mobility metrics using of each other have the same value of M , then the weight
(1). A node then computes the aggregate relative mobility function will be modified from M to ( M J D } . Therefore,
metric M using (2). the augmented weights will be totally ordered and the
2. All nodes start in Cluster-Undecided state. Every node clustering process will generate clusters of diameters at
broadcasts its own mobility metric, M (initialized to 0 at the most two hops. If two or more clusterheads happen to
beginning of operations) in a “Hello” message to its 1-hop come within range of each other, then the one with the
neighbors, once in every Broadcast-Interval (BI) period. It lowest weight retains the role of the clusterhead. Hence, no
is then stored in the neighbor table of each neighbor along two clusterheads will be neighbors in a stable state.
with a time-out period (TP) set. This algorithm is executed We have simulated both MOBIC and Lowest-ID
in a distributed manner. Thus, a node receives the M-values using the ns-2 network simulator, and have presented
from its neighbors, and then compares them with its own. a comparative analysis in Section 4.2. A cluster-based
3. If a node has the lowest value of M (aggregate relative routing protocol like CBRP [8] that runs on top of the
mobility) amongst all its neighbors, it assumes the status Lowest-ID scheme can also run on top of MOBIC with
of a Cluster-Head; otherwise it declares itself to be a minimum changes.
Cluster-Member. This algorithm leads to the formation
of clusters which are at most two hops in diameter. 4. Results and Discussion
If a node is a neighbor of two clusterheads, then it
becomes a “gateway” node. If two neighboring nodes in a 4.1. Simulation Environment and Parameters
Cluster-Undecided state have the same value of M, we
follow the Lowest-ID algorithm. The simulations were performed using the ns-2 network

416
 of each other for short periods of time. This results in
clusterheads giving up their roles to other nodes, and
Parameter Meaning Value hence the number of clusterhead changes increases rapidly.
N Number of Nodes 50 However, for transmission ranges greater than 50 m, more
mxn Size of the scenario 670 x 670 m a nodes are within range of other nodes for longer periods
I MaxSweed I MaximumSueed I 1.20.30dsec I of time. Therefore, less number of clusters, which are
larger in size, are formed, and mobility does not cause the
PT Pause Times 1 0.30sec nodes to frequently move in and out of range of each other.
Hence, the number of clusterhead changes decreases.
It is evident from Figure 2 that for moderate to high
9.4 h 1-1 transmission ranges (> 100 m), MOBIC outperforms
the Lowest-ID clustering algorithm. In fact, beyond a
transmission range of 125 m, the reduction in the rate
of clusterhead changes is by about 0.1 /sec. and for
T x = 250 m, MOBIC yields a gain of close to 33% over
Lowest-ID clustering. These large gains due to MOBIC
over Lowest-ID clustering (as depicted in Figure 2) can
be directly attributed to the following fact: in MOBIC,
nodes with the lowest relative mobility in a neighborhood
get chosen as clusterheads, the probability that they will
change clusters frequently is lower as compared to the
clusterheads in the Lowest-ID case.
01020 60 100
T”hk+I
125 150
(m)
175 200 225
I
250
ID for lower values of T x -
Although MOBIC does not perform as well as Lowest-
50 (since the neighbor set is
changing frequently resulting in less accurate calculations
Figure 2. CH Changes: Lowest-ID vs. MOBIC
of the aggregate mobility metric M ) , it outperforms the
simulator with wireless extensions [ 151. The scenarios latter for medium to high values of T x where the clusters
were randomly generated using the random waypoint are larger in size. Expectedly, A4 is a better metric if a node
model (inbuilt in ns-2) with input parameters such as has high degree.
maximum speed, pause times, number of nodes, area etc. The average number of clusters formed as a result of
We implemented MOBIC (details in Section 3.2) using executing both clustering algorithms strictly decreases
the aggregate relative mobility metric that we proposed with increase in T x . This is expected, since the nodes are
in Section 3.1. The simulation parameters have been uniformly distributed, and increase in the transmission
listed in Table 1 . Broadcast Interval (BI = 2sec), Time-out radius results in more nodes under the jurisdiction of a
Period (TP = 3sec), and Cluster Contention Interval (CCI clusterhead, and hence a less number of clusters. Also,
= 4sec) are additional parameters used in the simulations. there is little difference between Lowest-ID and MOBIC
Simulations were run for 900 seconds. We compared the with respect to the average number of clusters metric.
performance of MOBIC with the Lowest-ID algorithm This is because both were executed on the same random
with respect to a cluster stability metric CS, which denotes movement pattern.
the rate of clusterhead changes.
4.3. Variation in Degree of Mobility
4.2. Discussion of Results
Figure 3 shows the effect of varying mobility on the
Figure 2 shows the comparison between the performance of performance of MOBIC with respect to Lowest ID. In
’ Figure 3(a), we can see that for T x = 250 (a typical
Lowest-ID and MOBIC for a reasonably mobile scenario
with MaxSpeed = 20 m / s and PT = 0 sec, i.e. constant transmission range used in previous simulation experiments
mobility. We note that for both Lowest-ID and MOBIC, conducted elsewhere [9]), and for the “always mobile” case
the number of clusterhead changes first increases with the (PT = 0), MOBIC outperforms Lowest-ID by 50 - 100
increase in T x , and then decreases. For small values of T x clusterhead changes.
( w lo), most nodes remain out of each other’s range; there Even for highly mobile situations (MaxSpeed =
are severe disconnections in the topology and therefore, 30 m / s ) , MOBIC yields an appreciable gain over
there are fewer changes in the status of nodes. Lowest-ID owing to its capability of adapting itself to
As T x increases, more nodes will appear within range the mobility of nodes. Expectedly, the gains are slightly

417
 traveling on a highway and conference attendees in a hall.
67Om x 670m
50 md.3
Tx = 250m 6. References
-
s
i
4
0’3 -
[I] Bluetooth SIG Website. http: //www.bluetooth.com
[2] S. Basagni, “Distributed Clustering for Ad Hoc Networks,”
B Proc. I-SPAN ’99,Perth/Fremantle, Australia, June 1999, pp.
.:3 0.25 -
310-315.
U
F
[3] C.-C. Chiang, H.-K. Wu, W. Liu, M. Gerla, “Routing in
H Clustered Multihop, Mobile Wireless Networks with Fading
0.2 ~
Channel,” Proc. IEEE SICON ’97, Singapore, April 1997.
[4] A. Ephremides, J. E. Wieselthier, and D. J. Baker, “A
Design Concept for Reliable Mobile Radio Networks with
0 15-
5 10 15 20 25
Frequency Hopping Signaling,” Proceedings of the IEEE,
MaxSped (m.1eds’s.c) Vol. 75, No. 1, January 1987, pp. 56-73.
Figure 3. Effect of Varying Mobility [ 5 ] M. Gerla and J. T.-C. Tsai, “Multicluster,Mobile Multimedia
Radio Networks,” Wireless Networks I , 1995, pp. 255-265.
reduced for less mobile scenarios‘(with PT = 30 sec); [6] ‘The Mobile Communications Handbook,” Editor-in-Chief
but upon increasing the speed, we observe that MOBIC J. D. Gibson, CRC Press Inc., 1996.
[7] X. Hong, M. Gerla, G. Pei, and C.-C. Chiang, “A Group
manages to maintain its gains.
Mobility Model for Ad Hoc Wireless Networks,” Proc.
From the above results, we can conclude that MOBIC is ACM/IEEE MSWiM ’99, Seattle WA, August 1999.
suitable for stable cluster formation in situations involving [8] M. Jiang, J. Li, and Y.C. Tay, “Cluster Based Routing
both low and high mobility. Since it is based on a relative Protocol,” IETF Drafr, August 1999. Work in Progress.
mobility measure in the neighborhood of every node, it [9] P. Johansson, T. Larsson, N. Hedman, B. Mielczarek, and
adapts well to varying levels of mobility. M. Degermark, “Scenario-based performance Analysis of
Routing Protocols for Mobile Ad Hoc Networks,” F’roc.
5. Conclusions and Future Work ACM Mobicom 1999, Seattle WA, August 1999.
[IO] D. B. Johnson and D. A. Maltz, “Dynamic Source Routing
in Ad Hoc Wireless Networks,” Mobile Computing, eds.
Clustering imposes hierarchy and organization in a Tomasz Imielinski and Hank Korth, Chapter 5, Kluwer
MANET and therefore simplifies routing and bandwidth Academic Publishers, Boston, 1996.
allocation. Mobility of nodes causes clusters to get [ I I ] J. Jubin and J. D. Tomow, “DARPA Packet Radio Network
disrupted and thus triggers re-clustering. In this paper, Protocols,” Proceedings of the IEEE, January 1987.
we presented a new relative mobility metric for nodes in [I21 P Krishna, N.H. Vaidya, M. Chatterjee, D.K. Pradhan, “A
a MANET based on the ratio of the power levels due to Cluster Based Approach for Routing in Ad Hoc Networks,”
successive packet receptions at a node. We also presented a ACM Computer Communications Review (CCR), 1997.
weight based clustering algorithm, MOBIC, which uses the [I31 C. R. Lin and M. Gerla, “Adaptive Clustering for Mclbile
proposed mobility metric for formation of clusters that are Wireless Networks,” IEEE JSAC, Vol. 15, No. 7, September
at most two hops in diameter. Using ns-2 simulations, we 1997.
[ 141 B. McDonald and T. E Znati, “A Mobility-Based Framework
demonstrated that MOBIC outperforms Lowest-ID by as for Adaptive Clustering in Wireless Ad Hoc Networks”,
much as 33% in the rate of clusterhead changes. Therefore, IEEE JSAC, Vol. 17, No. 8, August 1999.
we conclude that relative mobility is a better criterion for [I51 Wireless and Mobility Extensions to the 13s-2
clustering rather than IDS which are not representative of Network Simulator - CMU Monarch Project.
node mobility in a MANET. http://monarch.cs.cmu.edu/cmu-ns.htm1
[I61 C. E. Perkins and E. M. Royer, “Ad hoc On-Demand
Future Work This work is a part of our ongoing research
Distance Vector Routing,” Proc. IEEE Workshop on Mobile .
efforts on MANETs. In future, we plan to integrate the Computing Systems and Applications, New Orleans, LA,
mobility metric with a cluster based routing protocol. February 1999, pp. 90-100.
This will not only affect clustering but will also affect [ 171 R. Ramanathan and M. Steenstrup, “Hierarchically-
the update intervals between the “Hello” messages. Such Organized Multihop Mobile Networks for Quality-of-
a mobility adaptive cluster-based routing protocol will Service Support,” Mobile Networks and Applications, Vol.
improve the performance of the network under different 3 , No. 2, August 1998.
levels of mobility. It will also be interesting to study the [ 181 C-K. Toh, “Associativity-Based Routing for Ad-Hoc Mobile
performance of mobility based clustering in specialized Networks,” International Journal on Wireless Personal
scenarios with different mobility patterns such as cars Communications, Vol. 4, No. 2, 1997.

418