Medicamentsen-ligne vous propose les traitements dont vous avez besoin afin de prendre soin de votre santé sexuelle. Avec plus de 7 ans d'expérience et plus de 80.000 clients francophones, nous étions la première clinique fournissant du
**acheter viagra** original en France à vente en ligne et le premier vendeur en ligne de Cialis dans le monde. Pourquoi prendre des risques si vous pouvez être sûr avec Medicamentsen-ligne - Le service auquel vous pouvez faire confiance.

## Hulk.bu.edu

A Mobility Based Metric for Clustering in Mobile Ad Hoc
Department of Electrical and Computer Engineering
Boston University, Boston, Massachusetts 02215, USA
Abstract– This paper presents a novel mobility metric for mobile ad hoc networks (MANET) that
is based on the ratio between the received power levels of successive transmissions measured at
any node from all its neighboring nodes. This mobility metric is subsequently used as a basis for
cluster formation which can be used for improving the scalability of services such as routing in
such networks. We propose a distributed clustering algorithm, MOBIC, based on the use of this
mobility metric for selection of clusterheads, and demonstrate that it leads to more stable cluster
formation than the Lowest-ID clustering algorithm ( “least clusterhead change” [3]) which is a well
known clustering algorithms for MANETs. We show reduction of as much as 33% in the number of
clusterhead changes owing to the use of the proposed technique. In a MANET that uses scalable
cluster-based services, the network performance metrics such as throughput and delay are tightly
coupled with the frequency of cluster reorganization. Therefore, we believe that since using MOBIC
results in a more stable configuration, it will directly lead to improvement of performance.

Keywords: Ad hoc networks, Mobility, Clustering.

1Proc. IEEE ICDCS 2001 Workshop on Wireless Networks and Mobile Computing, Phoenix, AZ, April 2001.

If an existing communication infrastructure is expensive or inconvenient to use or setup, or if
it is absent, mobile users with wireless connectivity can still communicate with each other by the
formation of an ad hoc network. Nodes in an ad hoc network can act as both hosts and routers since
they can generate as well as forward packets, respectively. Since there is no existing communication
infrastructure (e.g., a wired or a fixed wireless base station), ad hoc networks cannot rely on
specialized routers for path discovery and routing. Therefore, nodes in such a network are expected
to act cooperatively to establish the network “on-the-fly”. Such a network is also expected to
route traffic, possibly over multiple hops, in a distributed manner, and to adapt itself to the highly
dynamic state of its links and the mobility patterns of its constituent nodes.

Traditionally, the interest in such rapidly deployable network architectures has been for battlefield
and disaster relief situations2. Military applications such as voice and video communications in the
battlefield, and decentralized communication of maps and sensor data fuel research on such network
architectures. However, considerable interest in ad hoc networks has been shown recently in the
commercial sector owing to the miniaturization of computing devices and proliferation in their
numbers, and the increasing demand of people to stay connected all the time. The advent of low
power wireless communication technologies such as Bluetooth [1] and HomeRF [8] can propel ad
hoc networks to becoming an enabling platform for what is known as ubiquitous computing [22].

Communication between any two nodes in an ad hoc network might require the packets to
traverse multiple hops. Several protocols have been proposed in the literature for routing in mobile
Since the intermediate nodes may be mobile, node mobility can
cause frequent link failures and staleness of routes. That in turn can result in route errors and
trigger off a fresh route discovery process. In some cases, performing a local route repair may
be possible[12, 10]. In any case, the effectiveness of any routing algorithm in an ad hoc network
depends upon the timeliness and detail of topology information available. In such a scenario, the
availability of information which is valid for a longer duration of time is highly desirable.

With the increase in size of the networks, flat routing schemes do not scale well in terms of
performance. Routing schemes such as Dynamic Source Routing [12] which discover routes by
reactive flooding, and perform well for small networks, can result in low bandwidth utilization in
large networks with high load due to longer source routes (and thus, large byte overhead) [11].

Hence, some hierarchical organization is required in large ad hoc networks for solving this problem.

Several clustering strategies have been proposed with a focus on imposing a semi-hierarchical
structure upon nodes in an ad hoc network in order to increase scalability, improve bandwidth
utilization, and to reduce delays for route queries [4, 5, 15, 14].

2The first infrastructure of its type was the DARPA Packet Radio Network PRNET[13].

topologies [20, 10] is much more scalable than flat routing as it keeps the flooding traffic in check.

The basic step in clustering involves formation of easily manageable clusters of nodes.

clustering algorithm known as Lowest-ID (clusterhead selection based on ID) has been proposed
in the past [4] and has been revisited later in the “multimedia multihop mobile networks” context
[5]. In [3], Chiang et al. have shown that the Lowest-ID algorithm performs better than the max-
connectivity algorithm3 in terms of stability of clusters (measured by the number of clusterhead
changes), and they have proposed a small change in the Lowest-ID algorithm to improve performance;
the improved version is referred to as LCC which stands for “Least Clusterhead Change”.

We believe that since mobility is the main cause for the changes in clusterheads and cluster
memberships, it is logical to have a mobility metric as a basis of cluster formation and clusterhead
selection. This paper presents a novel mobility metric that is based upon the ratio between the
successive measurements of received power at any node from its neighbors. We then present a
clustering algorithm, MOBIC, which is similar to the Lowest-ID algorithm, but it uses the new
mobility metric for cluster formation. We show by simulations that MOBIC results in more stable
cluster formation as it yields as much as 33% reduction in the number of clusterhead changes over
the Lowest-ID algorithm (actually its LCC variant).

The rest of the paper is organized as follows: in Section 2, some relevant background and a
summary of previous related work is presented. Section 3 describes the approach we have adopted
to calculate the mobility metric for each node and outlines the clustering algorithm that is based
upon this mobility metric. Section 4 includes a discussion of the results and comparison with
previous clustering algorithms. Some directions of future research have been discussed in Section
In any complex distributed system of nodes, clustering of nodes into groups results in simplification
of addressing and management of the nodes and also yields better performance since details about
the remote parts of the distributed system can be handled in an aggregate manner. Thus, imposition
of a hierarchical organization is beneficial for the management of a complex system, and results in
scalability of operations. The wired Internet, for example, cannot be managed without hierarchical
Essential services like routing are highly scalable owing to this
3clusterhead selection is done based on node degree [5]
The notion of cluster-based organization in the context of mobile multihop wireless networks
has been around for a long time. Ephremides et al. [4] introduced the idea through the concept
of a distributed “linked cluster architecture”, which was mainly used for hierarchical routing, and
for network adaptability to changes in connectivity. More recently, these ideas were revisited in the
context of a mobile multihop multimedia wireless network (also known as a MANET) [5, 20].

Lowest-ID clustering is one of the most popular clustering schemes used in the old [4] as well as
recent [5, 10] ad hoc networks literature. In [5], Gerla et al. propose a simple distributed clustering
algorithm that yields clusters that are at most two hops in diameter. In each cluster, exactly
one node, the one with the lowest ID among its neighbors, becomes a clusterhead, and maintains
cluster-memberships of other member nodes.

The Lowest-ID algorithm proceeds as follows and results in the formation of clusters which are
• Each node is given a distinct ID and it periodically broadcasts the list of its neighbors
• A node which only hears nodes with ID higher than itself is a “clusterhead” (CH).

• The Lowest-ID node that a node hears is its clusterhead, unless the Lowest-ID specifically
gives up its role as a clusterhead (deferring to a yet lower ID node).

• A node which can hear two or more clusterheads is a “gateway”.

• Otherwise, a node is an ordinary node.

A cluster is identified by its clusterhead’s ID. Figure 1 shows a schematic of the result of using
Lowest-ID clustering. There are 10 nodes with unique IDs (and with equal transmission radii) which
form a connected graph. After the Lowest-ID clustering algorithm is executed, three clusters are
formed, as depicted by the three dotted circles. The dark squares at the centers of the respective
circles are clusterhead nodes (1,2 and 4 in figure). The dark-colored circles which exist in the
overlap regions between circles (8 and 9 in figure) are gateway nodes, and the light-colored circles
In [5], an algorithm based on max-connectivity4 was also proposed, but it performed much worse
than the Lowest-ID algorithm in terms of stability of clusters. The stability of clusters was measured
by a metric, namely the average number of clusterhead changes per unit of time. We use the same
metric for the evaluation of our algorithm too in Section 4.2.

In [3], the lowest-Id algorithm was improved by its variant LCC (Least Clusterhead Change)
by imposing an additional rule on the clustering process: if a member (id = i) of cluster C moves
within range of another cluster C with higher ID, then do not perform reclustering unless i is the
clusterhead of C. This helps in drastically reducing the number of changes in clusterheads due
to reclustering. This approach too results in formation of clusters which are 2 hops in diameter
and converges in O(d) time, where d is the diameter of the network. The clusterhead takes the
responsibility of coordinating transmissions of packets and route discovery, and thus the network
does not have to depend on classic flooding for routing.

Lowest-ID clustering was generalized to a weight based clustering technique, referred to as DCA
(Distributed Clustering Algorithm) in [2]. In DCA, each node is assumed to have a unique weight
(hence the weights are totally ordered) instead of just the node ID, and the clustering algorithm
uses the weights instead of the IDs for the selection of clusterheads. However the technique of
assignment of weights has not been discussed.

Clustering algorithms that generate clusters which may be greater than two hops in diameter
have also been proposed in the literature [14, 20]. However, cluster maintenance is complicated and
difficult in such situations, especially under high mobility, and can result in high overhead. We do
not consider this class of algorithms in this paper.

Several attempts have been made in the recent past to characterize mobility as an inherent phenomenon
in a MANET [11, 9], and an attempt has been made to incorporate it into routing schemes [21].

However, little work has been done towards using mobility as the basis of clustering in ad hoc
networks. In [11], a mobility metric has been proposed which is intended to capture and quantify
the motion of nodes; the proposed metric is geometric in the sense that the speed of a node is
measured relative to the other nodes. The mobility measure between any pair of nodes is defined
4A node with highest node degree becomes the clusterhead
as their absolute relative speed taken as an average over time. For determining the relative speed
between any pair of nodes, a knowledge of the location coordinates is assumed for all nodes which
might be available through a GPS5 like scheme. In order to arrive at the aggregate mobility metric
for a particular scenario, the mobility measure is averaged over all pairs of nodes.

The above metric has certain deficiencies with respect to clustering: First, it assumes a GPS
like scheme for calculation of relative speeds; in an ad hoc network especially in the indoors, we
cannot assume the existence of GPS, and so we have to resort to other techniques for measuring
relative mobility. Secondly, it fails to reflect in the true sense the movement of the nodes in the
neighborhood of a particular node, since it is an aggregate measure taken over nodes in a given
scenario. Actually the authors designed this metric for characterizing three different scenarios: a
conference situation, a large event setting, and a disaster relief scenario. These scenarios were
ranked in ascending order of their aggregate mobility metric.

Thus, a global mobility metric such as the one described above fails to capture the local mobility
which is primarily responsible for cluster changes. At the same time the measurement of mobility
between pairs of nodes that are far apart may not be relevant for local cluster formation. Hence,
we focus on characterizing the local mobility of a nodes around a certain node in an efficient and
The mobility metric defined in [9] is not used as a basis for cluster formation. However, such
a mobility metric can be useful for predictive mobility management. The authors of that paper
propose a model for group mobility namely, the Reference Point Group Mobility Model (RPGM). In
RPGM, each group has a logical “center” and the center’s motion defines the entire group’s motion
behavior including location, speed, direction, acceleration etc. Usually the nodes are uniformly
distributed within the scope of a group. The RPGM model defines the motion of groups explicitly
by giving a motion path for each group. A path that a group will follow is given by defining a
sequence of check points along the path corresponding to given time intervals.

An associativity based routing (ABR) protocol that uses mobility for routing has been proposed
for mobile ad hoc networks [21]. ABR does not define a mobility metric but uses a route stability
metric that is used by the routing protocol. In a MANET where mobile hosts (MHs) are acting as
routers and where routes become stale by a MH’s movement, ABR employs a routing scheme where
a route is selected based on nodes having associativity states that imply a period of stability.

A framework for dynamically organizing mobile nodes in ad hoc networks into clusters has been
proposed in [16]. The focus of the authors in that work is on bounding the probability of path
availability. A mobility model was developed and used to derive expressions for the probability of
path availability as a function of time. The proposed mobility model is a random walk based model
Figure 2: Aggregate Relative Mobility Calculation
which assumes that if the distance between two nodes is less than a system dependent threshold,
then it is also possible to determine the conditional probability that the nodes will be within range
of each other at time t0 + t, given that they are located within range at time t0. However, we
believe this probability based model fails to capture the real mobility of any node with respect to
its neighbors and therefore it is not an adequate metric for clustering. Besides, it may be hard to
implement such a complex algorithm on a bunch of low power nodes in a purely distributed manner.

We can see that none of the metrics described in this section are suitable for characterizing the
relative mobility of nodes in a particular node’s neighborhood in a MANET. Hence, we feel that
there is a need to develop such a metric which can be used for clustering. In the next section, we
describe a metric for capturing the mobility in a given node’s local neighborhood, and then use it
In this section we describe our mobility metric and discuss how it can be used in formation of
clusters which are at most 2 hops in diameter (like lowest ID). The lowest ID algorithm (even its
LCC variant) does not couple the clustering process with the mobility of the nodes. If a node with
a low ID happens to be highly mobile, it will cause severe reclustering to happen periodically when
it moves into the transmission range of other clusterheads. In such occasions the lower ID node will
prevail and reclustering will happen.

The basic idea in this paper is that the clustering process should be aware of the mobility of the
individual nodes with respect to its neighboring nodes. A node should not be elected a clusterhead
if it is highly mobile relative to its neighbors, since, in that situation, the probability that a cluster
will break and that reclustering will happen is high. Instead, we should attempt to select a node
that is less mobile relative to its neighbors for the role of a clusterhead.

The mobility metric proposed in this paper does not assume the availability of any absolute
It also does not assume availability of velocity
In the next two subsections, we describe our mobility metric and
how the clustering algorithm uses it for formation of stable clusters.

In our solution, in order to model mobility, we purport that the power level (received signal strength)
detected at the receiving node, RxP r, is indicative of the distance between the transmitting and
receiving node pairs. In the ideal situation, Friis’ free space propagation model is used, which uses
an inverse-square dependence of the ratio of received and transmit power on the physical distance
between the transmitter and the receiver, i.e. RxP r ∝ 1 [6]. But in real life, an exact calculation
of the distance between a transmitter and a receiver may not be possible from the measured signal
strengths owing to the complexities involved in accurate channel modeling. However, from the
ratio of RxP r between two successive packet transmissions (periodic “hello” messages) from a
neighboring node, we can get good knowledge about the relative mobility between the two nodes6.

Hence, we define the relative mobility metric, M rel(X), at a node Y with respect to X, in this
, then M rel(X) < 0, and a negative value of the relative mobility
metric between any two nodes will indicate that the two nodes are moving away with respect to
each other. On the other hand if RxP rnew > RxP rold, then M rel is positive (subscripts have been
omitted in order to reduce clutter), 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 M rel. This situation is
We calculate the aggregate local mobility value MY at any node Y by calculating the variance
(with respect to zero) of the entire set of relative mobility values M rel(X
Here, var0 denotes the variance with respect to zero (and not the mean of the sample) and is equal
to E[(M rel)2] which is is the expected value of the squares of the m relative mobility samples from
6We do not consider the effects of multipath, small-scale and large-scale fading in this study.

In this manner, any node Y which also acts as a receiver measures the power levels in successive
transmissions from all its neighbors and a variance of these values (with respect to zero) is a
representative value for the aggregate relative mobility metric MY for that node. The main rationale
behind calculating the variance of the relative mobility values with respect to each neighbor is that
a low value of MY indicates that Y is relatively less mobile with respect to its neighbors. On
the contrary, a high value of MY indicates that Y is highly mobile with respect to its neighboring
nodes. As we have mentioned before, we should favor the nodes that have a low variance in relative
mobilities with respect to its neighbors, for becoming clusterheads.

We believe that the variation in received signal power is a better indicator of mobility than pure
distance or speed owing to environmental characteristics. For example, the communication between
two nearby cars on a street with dense foliage is more likely to suffer from high attenuation of signal
strength than that between two cars that are farther away on a clear road. In reasonably short
time scales (a few seconds), the surrounding environment is unlikely to change by a great deal, so
the variation in received signal strength is a good index of local mobility.

The calculation of this mobility metric is a simple task that can be achieved in a distributed
manner, and the measurement of the incoming signal strength is easily possible with existing
hardware. Note that we only consider transmissions that are successfully received by the MAC
Since the calculation of the relative mobility metric M rel(X) needs two successive packet transmissions,
we require that the time interval after which the aggregate mobility metric MY is calculated at Y
should include two successive “hello” message transmissions from all Y’s neighbors. It is possible
that during that time interval, certain nodes move out of/come into range of node Y. We use a
heuristic to tackle this problem: nodes which do not participate in two successive transmissions
to node Y are excluded from the calculation. Thus, only those nodes which have been in the
neighborhood of Y for that particular time interval are considered for the mobility metric calculation.

This calculation is performed at every node, and thus, each node will maintain an aggregate relative
We intuitively expect that on average, MY would perform as a better metric if Y has more
neighboring nodes with mobilities in a given range. Although for sparsely connected topologies
and/or low transmission radii, the aggregate mobility calculation can be imprecise, we argue that
this yields a better picture of the aggregate behavior of nodes in the local neighborhood of Y in
moderately to highly dense topologies. In Section 4.2, we will demonstrate that this is indeed the
MOBIC - A Lowest Relative Mobility Clustering Algorithm
In order to use the mobility metric presented in the previous section for clustering, we propose
a distributed, lowest mobility clustering algorithm, MOBIC, which is similar in execution to the
Lowest-ID algorithm as described in Section 2.1, except that the mobility metric is used as a basis
of cluster formation instead of the ID information. We describe our algorithm in the following steps:
• All nodes send and receive “Hello” messages to/from their neighbors. Each node measures the
received power levels of two successive “Hello” message transmissions from every neighbor,
and then calculates the pairwise relative mobility metrics using (1). Before sending the next
broadcast packet to its neighbors, a node computes the aggregate relative mobility metric M
using (2). M is represented by a double precision floating point number.

• All nodes start in Cluster Undecided state. Every node broadcasts its own mobility metric,
M (initialized to 0 at the beginning of operations) in a “Hello” or “I’m Alive” message to
its 1-hop neighbors every Broadcast Interval (BI) period. It is then stored in the neighbor
table of each neighbor along with a timeout period (TP) set. This algorithm is executed in a
distributed manner. Thus, a node receives the aggregate mobility values from its neighboring
nodes, and then compares its own mobility value with those of its neighbors.

• If a node has the lowest value of M (aggregate relative mobility) amongst all its neighbors,
it assumes the status of a Cluster Head; otherwise it declares itself to be a Cluster Member.

This algorithm leads to the formation of clusters which are at most two hops in diameter. If a
node is a neighbor of two clusterheads, then it becomes a “gateway” node. If two neighboring
nodes in a Cluster Undecided state have the same value of M , we resort to comparison of IDs
• In case where the mobility metric of two clusterhead nodes is the same, and they are in
contention for retaining the Cluster Head status, then the selection of the clusterhead is
based on the Lowest-ID algorithm wherein the node with the lowest ID gets the status of the
Cluster Head. If a node with Cluster Member status with a low mobility moves into the range
of another Cluster Head node with higher mobility, reclustering is not triggered (similar to
• In a mobile scenario, if two nodes with status Cluster Head move into each other’s range,
reclustering is deferred for Cluster Contention Interval (CCI) to allow for incidental contacts
between passing nodes. If the nodes are in transmission range of each other even after the
CCI timer has expired, reclustering is triggered, and the node with the lower mobility metric
Theorem 1 MOBIC yields clusters of diameter ≤ 2 hops, and no two clusterheads are in range of
Proof: It has been shown in [2] that for a totally ordered weight distribution, a distributed algorithm
similar to Lowest-ID yields clusters which satisfy the above properties.

the weights (Aggregate Local Mobility Metric) may not be totally ordered and may be changing
If all nodes have different values of aggregate local mobility (M ), then the weights (mobility
metric) will be totally ordered and MOBIC will result in clusters which obey the above properties.

This situation is likely to happen most often since the nodes are mobile and the variance of relative
mobilities is being calculated using double precision arithmetic in every node’s local neighborhood.

However, if a few nodes within the transmission range of each other have the same value of M ,
then the weight function will be modified from M to {M ,ID}. Therefore, the augmented weights
will be totally ordered and the clustering process will generate clusters of diameters at most two
hops. If two or more clusterheads happen to come within range of each other, then the one with
the lowest weight retains the role of the clusterhead. Hence, no two clusterheads will be neighbors
A cluster-based routing protocol like CBRP [10] that runs on top of the Lowest-ID scheme can
also run on top of MOBIC with minimum changes. We have simulated both MOBIC and Lowest-ID
using the ns-2 network simulator, and have presented a comparative analysis in Section 4.2.

In this paper, we have not presented the performance analysis of any routing protocol that
can run on top of MOBIC, but we feel that more stable cluster formation can directly result in
significant improvement of performance.

670m x 670m50 NodesMax Speed = 20m/sConstant Mobility
Average Number of Clusterhead Changes (per second)
Figure 3: Number of CH Changes: Lowest-ID vs. MOBIC
The simulations were performed using the ns network simulator from UC Berkeley [17] with wireless
extensions from CMU [18]. The scenarios were randomly generated with input parameters such as
maximum speed, pause times, number of nodes, area etc. We implemented MOBIC using the
aggregate relative mobility metric that we proposed in Section 3.1. The details of the algorithm
have been provided in Section 3.2. The simulation parameters have been listed in Table 1. We
have compared the performance of MOBIC with the Lowest-ID algorithm with respect to a cluster
stability metric CS, which denotes the number of clusterhead changes in a given time period.

The aggregate mobility values (M ) were stamped onto each “hello” broadcast packet and sent
by the sender node to its neighbors. The receiver nodes in ns receive the packets and extract both
the aggregate mobility information (from the data part of the packet) as well as the RxP r of the
current packet (from the MAC layer). The relative mobility is calculated from two successive RxP r
values as described in Section 3.1. Then the M values are calculated by using (2) and stamped onto
the next broadcast packet. Once the M values of all neighbors are known, the clustering process is
executed. The byte overhead of the “hello” packets is increased by 8 bytes only7.

Figure 3 shows the comparison between the performance of Lowest-ID and MOBIC for a reasonably
mobile scenario with M axSpeed = 20 m/s and P T = 0 sec, i.e. constant mobility.

We note that for both Lowest-ID and MOBIC, the number of clusterhead changes first increases
with the increase in transmission range and then decreases. For small transmission ranges (T x ∼
10), most nodes remain out of each other’s range; there are severe disconnections in the topology
and therefore, there are fewer changes in the status of nodes.

As T x increases, more nodes will appear within transmission ranges of each other for short
periods of time. This results in clusterheads giving up their roles to other nodes (by lowest id
and mobility measurements in Lowest-ID and MOBIC, respectively), and hence the number of
clusterhead changes increases rapidly. However, for transmission ranges greater than 50 m, more
nodes are within range of other nodes for longer periods of time. Therefore, less number of clusters,
which are larger in size, are formed, and mobility of nodes does not cause them to frequently move
in and out of range of each other. Hence, the number of clusterhead changes decreases.

It is evident from Figure 3 that for moderate/high transmission ranges (> 100 m), MOBIC
outperforms the Lowest-ID clustering algorithm. In fact, beyond a transmission range of 125 m,
the reduction in the number of clusterhead changes is by about 100, 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 3) 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
Although MOBIC does not perform as well as Lowest-ID for lower values of T x ∼ 50 (since
clusters are broken up frequently, and the neighbor-set is changing frequently resulting in less
accurate calculations of the aggregate mobility metric M ), it does outperform the latter for medium
to high values of T x where the clusters are larger in size. As expected, our aggregate mobility metric
performs better if a node has more neighbors.

Figure 4 shows the variation in the number of clusters that are formed as a result of executing
both clustering algorithms. The number of clusters strictly decreases with increase in transmission
range. This is in accordance with our expectation since the nodes are uniformly distributed, and
increase in the transmission radius results in more nodes under the jurisdiction of a clusterhead,
and hence a less number of clusters. However, as T x increases even further (> 125 m), the rate of
reduction in number of clusters decreases due to the increase in overlap between adjacent clusters,
and this results in an increase in the number of nodes belonging to multiple clusters.

670m x 670m50 NodesMax Speed = 20m/sConstant Mobility
Figure 4: Number of Clusters: Lowest-ID vs. MOBIC
Average Number of Clusterhead Changes (per second)
Figure 5: Lowest-ID vs. MOBIC in a Larger Area
Another observation that we can make from Figure 4 is that there is little difference between
Lowest-ID and MOBIC with respect to the number of clusters metric. This is because both operate
on similar random movement patterns and fundamentally both are variations of a “local” weight
Next, we explore the effect of area density of nodes on the cluster stability metric. We simulated
both techniques on a scenario (1000m×1000m) with a larger area while keeping the other parameters
(average mobility patterns etc.) the same. In this case, the nodes are more sparsely distributed
than in the case presented in Section 4.2. Therefore, there are more clusterhead changes in the
Another observation is that the peak of the curve has shifted towards the right in this case as
compared to the 670m × 670m case. This can be attributed to the fact that uniformly distributing
the same number of nodes in a larger area results in the nodes being farther apart from each other
on average, and this means that a larger transmission radius is required to span the neighboring
nodes, the situation when the clusterhead changes start to diminish.

We can also see from Figure 5 that the transmission radius at which MOBIC starts to outperform
Lowest-ID is greater than the one in the previous case (670m × 670m). That is because a larger
radius is required to include the same number of neighbors that were deemed appropriate in the
previous case for good aggregate mobility characterization by the method described in Section 3.1.

It is for transmission ranges greater than this value that the mobility metric is able to capture the
local aggregate mobility and use it well for clustering. Since the nominal transmission radii for
radios used in such large open areas are usually in the range of 150 − 250 meters, MOBIC will
outperform Lowest-ID for these ranges.

A couple of more observations are noteworthy in Figures 3, 4, and 5. For the 670 × 670 case, the
number of clusterhead changes is maximum for a transmission radius, T x ≈ 50m, and the number
of clusters is approximately 35; and for the 1000×1000 case, the maximum is achieved at T x ≈ 75m
and the number of clusters is approximately the same as before. We see that for a constant number
of nodes (N = 50) if the areas are related by a factor of f = 1000×1000 ≈ 2.22 we get the same
number of clusters if the transmission radii are related by a factor of 75 = 1.49 ≈
Our tentative explanation for this phenomena is the following: suppose that Aov(T x, m) is the
total overlap area between clusters for the m × m region at the critical T x, and A(T x, m) is the
total area occupied by all clusters. The latter is proportional to m2 under uniform distribution of
nodes. Let C be the number of clusters. Now, A = CπT x2 − Aov which implies, Aov = CπT x2 − 1.

Our claim is that if the bounding area is scaled f times and the number of nodes is kept constant
(i.e., the node density changes), the maxima in clusterhead changes occurs when Aov is in a critical
range (i.e., it is not too low so that the clusters are mostly disconnected, neither is it high enough
for stable formation of clusters), and that is same for both scales. We see that C remains the same
We make a similar observation regarding the value of the transmission range where MOBIC
outperforms Lowest-ID. For the 670 × 670 case, this happens at T x ≈ 100m, and the number of
clusters is approximately 20; on the other hand, for the 1000 × 1000 case, MOBIC outperforms
Lowest-ID at T x ≈ 140m, and the number of clusters is approximately the same (∼ 20). Again the
transmission radii are approximately related by a factor 1.4 ≈
model for this scenario. However, our tentative explanation for this phenomena is the following:
MOBIC starts performing better than Lowest-ID when there are a critical number of neighboring
nodes around a clusterhead node. That critical number can be achieved by scaling the area covered
Number of Clusterhead Changes in 900 secs
Number of Clusterhead Changes in 900 secs
by the transmission range of a node by the same factor f and thus by scaling T x by
Exact correlation between the performance of clustering algorithms and the parameters such as
area, number of nodes, transmission radius, mobility speeds etc. can only be achieved by developing
an analytical model which will be a subject of future research.

Figure 6 shows the effect of varying mobility on the performance of MOBIC with respect to Lowest
ID. In Figure 6(a), we can see that for T x = 250 (a typical transmission range used in previous
simulation experiments conducted elsewhere [11]), and for the “always mobile” case (P T = 0),
MOBIC outperforms Lowest-ID by 50 − 100 clusterhead changes.

Even for highly mobile situations (M axSpeed = 30 m/s), MOBIC yields an appreciable gain
over Lowest-ID owing to its capability of adapting itself to the mobility of nodes. Expectedly, the
gains are slightly reduced for less mobile scenarios (with P T = 30 sec); but upon increasing the
speed, we observe that MOBIC manages to maintain its gains.

From the above results, we can easily conclude that MOBIC is highly suitable for stable cluster
formation in situations involving both low and high mobility. Since it is based on a relative mobility
measure in the neighborhood of every node, it adapts well to varying levels of mobility.

This paper is a part of our larger ongoing efforts in the area of Mobile Ad Hoc networks. Integrating
a mobility metric into clustering is the first step in this direction. Our future efforts will address
We plan to integrate the mobility metric with a cluster based routing protocol. This will not only
affect clustering (as we have shown in this paper) but will also affect the update intervals between
the “Hello” messages. Such a mobility adaptive cluster-based routing protocol will improve the
performance of the network under different levels of mobility.

The aggregate mobility metric that was introduced in this paper was computed by calculating
the variance of relative mobilities between a node and all its neighbors over a small time period. It
is possible that keeping some history information about the mobility values may yield more stable
metrics and can result in more stable clusters.

It is envisaged that the mobility metric will yield better results when mapped to specific scenarios
where the relative mobility between nodes does not differ significantly. Examples include cars
traveling on a highway or attendees in a conference hall. We plan to study the performance of the
mobility based clustering in these specialized scenarios.

Clustering is an important technique for imposing hierarchy and organization in a mobile ad hoc
network. It helps in reducing the complexity in management of information about the mobile
nodes, and therefore simplifies some essential processes such as routing and bandwidth allocation.

Mobility of nodes causes clusters to get disrupted and thus triggers reclustering. Therefore, the use
of mobility information for cluster formation is a reasonable proposition. In this paper, we presented
a new mobility metric for nodes in a MANET. It is simple to measure and does not assume any
We proposed a weight based clustering algorithm, MOBIC, which uses the proposed mobility
metric for formation of clusters that are at most two hops in diameter. Using ns-2 simulations,
we have demonstrated that the gains due to MOBIC are significant as compared to those of the
Lowest-ID algorithm. (MOBIC outperforms Lowest-ID by as much as 33% in number of clusterhead
changes) Therefore, we conclude that relative mobility is a better criterion for clustering the nodes
rather than plain IDs which are not representative of node mobility in a mobile ad hoc network.

[1] Bluetooth SIG Website. http://www.bluetooth.com/
[2] S. Basagni. “Distributed Clustering for Ad Hoc Networks,” Proceedings of the 1999
International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN’99),
Perth/Fremantle, Australia, June 1999, pp. 310–315.

[3] C.-C. Chiang, H.-K. Wu, W. Liu, M. Gerla, “Routing in Clustered Multihop, Mobile Wireless
Networks with Fading Channel,” Proceedings of SICON 1997.

[4] A. Ephremides, J. E. Wieselthier, and D. J. Baker, “A Design Concept for Reliable Mobile
Radio Networks with Frequency Hopping Signaling,” Proceedings of the IEEE, Vol. 75, No. 1,
[5] M. Gerla and J. T.-C. Tsai, “Multicluster, Mobile Multimedia Radio Networks,” Wireless
[6] “The Mobile Communications Handbook,” Editor-in-Chief: J. D. Gibson, CRC Press Inc.,
[7] Z. J. Haas and M. R. Pearlman, “The Performance of the Zonal Routing Protocol in
Reconfigurable Wireless Networks,” IEEE JSAC - Issue on Ad Hoc Networks, June 1999.

[8] HomeRF Working Group Website. http://www.homerf.org
[9] X. Hong, M. Gerla, G. Pei and C.-C. Chiang, “A Group Mobility Model for Ad Hoc Wireless
Networks,” Proceedings of ACM/IEEE MSWiM ’99 Workshop, Seattle WA, August 1999.

[10] M. Jiang, J. Li and Y.C. Tay, “Cluster Based Routing Protocol,” IETF Draft, August 1999.

[11] P. Johansson, T. Larsson, N. Hedman, B. Mielczarek and M. Degermark, “Scenario-based
performance Analysis of Routing Protocols for Mobile Ad Hoc Networks,” Proceedings of ACM
Mobicom 1999, Seattle WA, August 1999.

[12] D. B. Johnson and D. A. Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networks,”
Mobile Computing, edited by Tomasz Imielinski and Hank Korth, Chapter 5, Kluwer Academic
[13] J. Jubin and J. D. Tornow, “DARPA Packet Radio Network Protocols,” Proceedings of the
[14] P Krishna, N.H. Vaidya, M. Chatterjee, D.K. Pradhan, “A Cluster Based Approach for Routing
in Ad Hoc Networks,” ACM SIGCOMM Computer Communications Review (CCR), 1997.

[15] C. R. Lin and M. Gerla, “Adaptive Clustering for Mobile Wireless Networks,” IEEE JSAC,
[16] B. McDonald and T. F. Znati, “ A Mobility-Based Framework for Adaptive Clustering in
Wireless Ad Hoc Networks”, IEEE JSAC, Vol. 17, No. 8, August 1999.

[17] Network Simulator - ns-2. UC Berkeley. http://www-mash.cs.berkeley.edu/ns/
[18] Wireless and Mobility Extensions to the ns-2 Network Simulator. CMU Monarch Project.

[19] 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, New
[20] R. Ramanathan and M. Steenstrup, “Hierarchically-Organized Multihop Mobile Networks for
Quality-of-Service Support,” Mobile Networks and Applications, Vol. 3, No. 2, Aug 1998.

[21] C-K. Toh, “Associativity-Based Routing for Ad-Hoc Mobile Networks,” International Journal
on Wireless Personal Communications, Vol. 4, No. 2, 1997.

[22] M. Weiser, “Some Computer Science Issues in Ubiquitous Computing,” Communications of
the ACM, Vol. 36, No. 7, pp. 75-85, July 1993.

Source: http://hulk.bu.edu/pubs/papers/2001/TR-01-15-2001.pdf

W O U N D C A R E Wound Care of a Diabetic Foot Ulcer Tom Wynn, RPh narrowing of the blood vessels in the feet and legs. Poor circu-lation in combination with the high-pressure areas on the bot- Chad Thompson, PharmD tom of the foot can lead to callous formation in the patientwho has diabetes. If not addressed, the callous can lead to anulcer. The ﬁnal stage can be gangrene o

Esperienza Professionale specifica in Chirurgia Toracica Videoassistita e Robotica Appartenenza a Società scientifiche Appartenenza a Consigli Direttivi Società Attività Chirurgica: casistica operatoria Partecipazioni a gruppi di studio e protocolli Pag. 8scientifici Premi Organizzazione di Congressi Nazionali Relazione su invito a Congressi Nazionali Partecipazione su