Abstract- This paper presents a mobility-based d-hop clustering algorithm (MobDHop), which forms variablediameter clusters based on node mobility pattern in MANETs. We introduce a new metric to measure the variation of distance between nodes over time in o
d-hop clusters that are more flexible in cluster diameter. The diameter of clusters is adaptive to the mobility pattern of network nodes. MobDHop is simple and incurs as low overhead as possible. Information exchange during the formation of clusters, clusterhead changes and clusterhead handovers are kept to minimum. The remainder of this paper is organized as follows: We present an overview of clustering algorithms proposed for MANETs in Section 2. Next, details of MobDHop are presented in Section 3. Section 4 discusses our simulation results and analysis. Finally, we conclude in Section 5.
2. Related Work
A number of clustering algorithms have been proposed in literature such as Linked Cluster Algorithm (LCA)[4], Lowest-ID Algorithm (L-ID)[5], Maximum Connectivity Clustering (MCC)[6], Least Clusterhead Change Algorithm (LCC)[7], and MOBIC[8]. LCA[4] was developed for packet radio networks and intended to be used with small networks of less than 100 nodes. LCA organizes nodes into clusters on the basis of node proximity. Each cluster has a clusterhead, and all nodes
within a cluster are within direct transmission range of the
clusterhead. Gateways are nodes that are located in the overlapping region between clusters. Two clusters communicate with each other via gateways. Pair of nodes can act as gateways if there are no nodes in the overlapping region. LCA was later revised[5] to reduce the number of clusterheads. In the revised version of LCA, a node is said to be covered if it is in the 1-hop neighborhood of a node that has declared itself as clusterhead. A
node declares itself to be a clusterhead if it has the lowest id
among the non-covered nodes in its 1-hop neighborhood, known
as Lowest-ID algorithm.
Parekh suggested MCC in which the clusterhead election is based on degree of connectivity instead of node id[6]. A node is
elected as a clusterhead if it is the highest connected node in all of the uncovered neighboring nodes. This algorithm suffers from
dynamic network topology, which triggers frequent changes of
clusterheads. Frequent cluster reconfiguration and clusterhead
reselection incur prohibitive overhead.
LCC[7] is designed to minimize clusterhead changes. A
clusterhead change occurs when two clusterheads come within
range of each other, or a node becomes disconnected from any
cluster. When two clusterheads come into direct contact, one of
the clusterheads will give up its role. Some of the nodes in one cluster may not be members of the other clusterhead’s cluster. Therefore, one or more of those nodes must become a clusterhead. Such changes propagate across the network, causing a rippling effect of clusterhead changes. Basu et al.[8] propose a weight-based clustering algorithm, MOBIC, which is similar to L-ID. Instead of node ID, MOBIC uses a new mobility metric, Aggregate Local Mobility (ALM), to elect a clusterhead. The ratio between the received power
levels of successive transmissions between a pair of nodes is
used to compute the relative mobility between neighboring nodes, which determines the ALM of each node.
All of the above algorithms create two-hop clusters in MANETs. They are more suitable for dense MANETs in which most of the nodes are within direct transmission range of clusterheads. However, these algorithms may form a large number of clusters in relatively large and sparse MANETs. Therefore, two-hop clusters may not be able to achieve effective topology aggregation. . Amis et al. generalized the clustering heuristics so that an ordinary node can be at most d hops away from its clusterhead[9]. This algorithm allows more control and flexibility in the determination of clusterhead density. However, clusters are formed heuristically without taking node mobility
and their mobility pattern into consideration. McDonald and Znati[2] designed a (α,t)-clustering algorithm that adaptively
changes its clustering criteria based on the current node mobility. This algorithm determines cluster membership according to a cluster’s internal path availability between all cluster members over time. 3.Mobility-based d-hop Clustering Algorithm
A successful dynamic clustering algorithm should achieve a stable cluster topology with minimal communications overhead and computational complexity [2]. The efficiency of the algorithm is also measured by the number of clusters formed [11]. Therefore, the main design goals of our clustering algorithm are as follows:
1. The algorithm minimizes the number of clusters by considering group mobility pattern. 2. The algorithm must be distributed and executed asynchronously. 3. The algorithm must incur minimal clustering overhead, be it
cluster formation or maintenance overhead. 4. Network-wide flooding must be avoided.
5. Optimal clustering may not be achieved, but the algorithm must be able to form stable clusters should any exists. Before introducing MobDHop, we first make a few
assumptions on the network:
1. Two nodes are connected by bi-directional link (symmetric
transmission).
2. The network is not partitioned.
3. Each node can measure its received signal strength.
Through periodic beaconing or hello messages used in some routing protocols, a mobile node can estimate its distance to its neighbor based on the measured received signal strength from that particular neighbor. In the Friss transmission equation, the received power over a point-to-point radio link is given by: 2
Pλr=Pt*Gt*Gr* (4*π*d)2