Mobility-based d-hop clustering algorithm for mobile ad hoc networks

Mobility-based d-Hop Clustering Algorithm for Mobile Ad Hoc Networks
Agency for Science Technology and Research Abstract- This paper presents a mobility-based d-hop effective topology [1]. By organizing nodes into clusters,
clustering algorithm (MobDHop), which forms variable-
topology information can be aggregated. This is because the diameter clusters based on node mobility pattern in
number of nodes of a cluster is smaller then the number of nodes MANETs. We introduce a new metric to measure the
of the entire network. Each node only stores fraction of the total variation of distance between nodes over time in order to
network routing information. Therefore, the number of routing estimate the relative mobility of two nodes. We also estimate
entries and the exchanges of routing information between nodes the stability of clusters based on relative mobility of cluster
are reduced[3]. Apart from making large networks seem smaller, members. Unlike other clustering algorithms, the diameter
clustering in MANETs also makes dynamic topology appear less of clusters is not restricted to two hops. Instead, the diameter
dynamic by considering cluster stability when they form[2]. of clusters is flexible and determined by the stability of
Based on this criterion, all cluster members that move in a clusters. Nodes which have similar moving pattern are
similar pattern remain in the same cluster throughout the entire grouped into one cluster. The simulation results show that
communication session. By doing this, the topology within a MobDHop has stable performance in randomly generated
cluster is less dynamic. Hence, the corresponding network state scenarios. It forms lesser clusters than Lowest-ID and
information is less variable[3]. This minimizes link breakage MOBIC algorithm in the same scenario. In conclusion,
MobDHop can be used to provide an underlying hierarchical
Clustering algorithm in MANETs should be able to routing structure to address the scalability of routing
maintain its cluster structure as stable as possible while the protocol in large MANETs.
topology changes[1]. This is to avoid prohibitive overhead incurred during clusterhead changes. In this paper, we propose a Keywords: cluster, mobility-based clustering, mobile ad hoc
mobility-based d-hop clustering algorithm (MobDHop) that networks, MANET, mobility pattern.
forms d-hop clusters based on a mobility metric suggested by Basu et al.[8]. The formation of clusters is determined by the mobility pattern of nodes to ensure maximum cluster stability. 1. Introduction
We observe that mobile users in MANET may move in groups. This is known as group mobility[10]. Mobile hosts may be Mobile ad hoc network (MANET) consists of a number of involved in team collaborations or activities. They may have a wireless hosts that communicate with each other through multi- common mission (save victims that are trapped in collapsed hop wireless links in the absence of fixed infrastructure. They building), perform similar tasks (gather information of threats in can be formed and deformed spontaneously at anytime and a battlefield) or move in the same direction (rescue team anywhere. Some envisioned MANETs, such as mobile military designated to move towards east side of disaster struck area). networks or future commercial networks may be relatively large Therefore, our algorithm attempts to capture group mobility and (e.g. hundreds or possibly thousands of nodes per autonomous uses this information to form more stable clusters. system). The need to store complete routing details for an entire MobDHop, a distributed algorithm, dynamically forms network topology raises scalability issue. The flat hierarchy stable clusters which can serve as underlying routing adopted by most of the existing MANET routing protocols may architecture. First, MobDHop forms non-overlapping two-hop not be able to support the routing function efficiently since their cluster like other clustering algorithms. Next, these clusters routing tables could grow to an immense size if each node had a initiate a merging process among each other if they could listen complete view of the network topology. Therefore, clustering to one another through gateways. The merging process will only algorithms are proposed in MANETs to address scalability issue be successful if the newly formed cluster achieves a required by providing a hierarchical network structure for routing. level of stability. As mentioned, most of the existing clustering Clustering algorithms can be performed dynamically to algorithms form two-hop clusters which may not be too useful in adapt to node mobility[2]. MANET is dynamically organized very large MANETs. Therefore, MobDHop is designed to form into groups called clusters to maintain a relatively stable d-hop clusters that are more flexible in cluster diameter. The used to compute the relative mobility between neighboring diameter of clusters is adaptive to the mobility pattern of nodes, which determines the ALM of each node. network nodes. MobDHop is simple and incurs as low overhead All of the above algorithms create two-hop clusters in as possible. Information exchange during the formation of MANETs. They are more suitable for dense MANETs in which clusters, clusterhead changes and clusterhead handovers are kept most of the nodes are within direct transmission range of to minimum. The remainder of this paper is organized as follows: clusterheads. However, these algorithms may form a large We present an overview of clustering algorithms proposed for number of clusters in relatively large and sparse MANETs. MANETs in Section 2. Next, details of MobDHop are presented Therefore, two-hop clusters may not be able to achieve effective in Section 3. Section 4 discusses our simulation results and topology aggregation. . Amis et al. generalized the clustering analysis. Finally, we conclude in Section 5. heuristics so that an ordinary node can be at most d hops away from its clusterhead[9]. This algorithm allows more control and 2. Related Work
flexibility in the determination of clusterhead density. However, clusters are formed heuristically without taking node mobility A number of clustering algorithms have been proposed in and their mobility pattern into consideration. McDonald and literature such as Linked Cluster Algorithm (LCA)[4], Lowest- Znati[2] designed a (α,t)-clustering algorithm that adaptively ID Algorithm (L-ID)[5], Maximum Connectivity Clustering changes its clustering criteria based on the current node mobility. (MCC)[6], Least Clusterhead Change Algorithm (LCC)[7], and This algorithm determines cluster membership according to a cluster’s internal path availability between all cluster members 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 3.Mobility-based d-hop Clustering Algorithm
within a cluster are within direct transmission range of the clusterhead. Gateways are nodes that are located in the A successful dynamic clustering algorithm should achieve a overlapping region between clusters. Two clusters communicate stable cluster topology with minimal communications overhead with each other via gateways. Pair of nodes can act as gateways and computational complexity [2]. The efficiency of the if there are no nodes in the overlapping region. LCA was later algorithm is also measured by the number of clusters formed revised[5] to reduce the number of clusterheads. In the revised [11]. Therefore, the main design goals of our clustering 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 1. The algorithm minimizes the number of clusters by node declares itself to be a clusterhead if it has the lowest id among the non-covered nodes in its 1-hop neighborhood, known 2. The algorithm must be distributed and executed Parekh suggested MCC in which the clusterhead election is 3. The algorithm must incur minimal clustering overhead, be it based on degree of connectivity instead of node id[6]. A node is cluster formation or maintenance overhead. elected as a clusterhead if it is the highest connected node in all 4. Network-wide flooding must be avoided. of the uncovered neighboring nodes. This algorithm suffers from 5. Optimal clustering may not be achieved, but the algorithm dynamic network topology, which triggers frequent changes of must be able to form stable clusters should any exists. clusterheads. Frequent cluster reconfiguration and clusterhead MobDHop, we first make a few
LCC[7] is designed to minimize clusterhead changes. A 1. Two nodes are connected by bi-directional link (symmetric 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

Source: http://homepages.ecs.vuw.ac.nz/~winston/papers/WCNC2004-MobDHop.pdf