Survey On Mobility Based Clustering Algorithms In MANET

Survey On Mobility Based Clustering Algorithms In MANET

Sapna Pal, S. P. Singh

Madan Mohan Malaviya Engineering College, Gorakhpur, India

Abstract

In the last few years, various efforts have been devoted to design efficient algorithms for clustering the wireless mobile ad-hoc networks (MANET) considering the network and node mobility characteristics. Clustering allows fast connection and better routing and topology management of MANET. In MANET each node is free to move randomly. There are numerous algorithms to construct clusters in MANET on the basis of different parameters. Because of the nodes mobility, the network topology will change over time. A node may join or leave an existing cluster at a time. Many methods have been developed to form stable clusters. In this paper, some of such methods are studied that have been developed for clustering and helpful for forming stable clusters. This paper could be helpful in relative analysis of different approaches clustering. The objective to this paper is to present the main concepts concerning clustering approaches in mobile ad hoc networks.

1. Introduction

   A mobile ad hoc network [8] is a collection of mobile nodes that dynamically form a network without any infrastructure or pre-defined topology. Mobile nodes are continuously moving in different direction with different speed. In this network environment, each node acts as an information source as well as a router to widen packets to its neighbors. The network is fully autonomous and can be formed at any time and also can be changed. It is characterized by limited battery power, limited bandwidth, frequent network topology changes, and rapid mobility.

   MANETs are proposed to function independent of the fixed infrastructure with the exception of a few stub gateways to provide access to the larger network. A MANET node is actually mobile and is itself a router with multiple wireless or wired connections. MANET is a wireless network in which all nodes can freely and arbitrary move in any direction with any velocity. They

   can be formed and deformed spontaneously at anytime and anywhere.

   Routing is challenging in Mobile Ad hoc Network due to the dynamic nature of the network topology because of mobility characteristics of nodes. There is a well-known method to reduce the amount of routing data exchanges and accordingly, to save the communication bandwidth and energy that method is clustering.

   Clustering is the process of dividing the nodes of a network into a few organized partitions called clusters [8]. Clustering creates a backbone network of nodes, providing scalability for large networks, and stability for dynamic networks. In Mobile Ad Hoc Networks (MANETs) clustering has many advantages compared to the traditional networks. But the highly dynamic and unstable nature of MANETs makes it difficult for the cluster based routing protocols to divide a mobile network into clusters and determination of cluster heads for each cluster. Clustering algorithm in MANETs should be able to maintain its cluster structure as stable as possible while the topology changes. Most clustering approaches for mobile ad hoc networks select a subset of nodes in order to form a network backbone that supports control functions. A set of the selected nodes are called clusterheads and each node in the network is associated with one. Clusterheads are connected with one another directly or through gateway nodes. The union of gateway nodes and clusterheads form a connected backbone. This connected backbone helps simplify functions such as channel access, bandwidth allocation, routing power control and virtual-circuit support.

   The objectives of clustering are to minimize the total transmission power aggregated over the nodes in the selected path, and to balance the load among the nodes for prolonging the network lifetime. Clustering is a sample of layered protocols in which a network is composed of several clusters of mobile nodes.

   In a cluster-based environment, there are some nodes in the network called clusterheads which have high processing speed and battery power than the other nodes. These clusterheads are responsible for cluster management and maintenance of the network.

   A clusterhead allocates the resources to all the nodes that belong to its cluster. In addition to controlling and managing its own cluster, it also communicates with other clusters. It maintains the information about every node within its cluster. Therefore, choosing the appropriate number of clusterheads that can use the network resources efficiently and adapt to the changing network conditions in MANETs is a challenging task. Due to mobility of the network, the nodes can go outside the transmission range of their clusterhead and move into another cluster thus changing their neighborhood. This can change the number of clusters and number of nodes in a cluster but this does not result in a change of the dominant set at all. Clustering of nodes in MANETs is one of the biggest challenges. Finding the optimal number of clusters that cover the entire network becomes essential and an active area of research. Although, several authors have proposed different techniques to find the optimal number of clusters, none of them addresses all the parameters of a mobile ad hoc network. Clustering has several advantages in MANETs. The system performance can be improved by allowing the reuse of resources due to clustering because each group of nodes can communicate with each other without affecting the other groups. Secondly, it optimally manages the network topology by dividing the task among specified nodes called clusterheads, which is very useful for network management and routing.

   There are some requirements of clustering in MANETs. The clustering algorithm must be distributed, since every node in the network has only local knowledge and communicates outside its group only through its clusterhead as in case of cluster-based routing. The algorithm should be robust as the network size increases or decreases; it should be able to adapt to all the changes. The clusters should be reasonably efficient i.e. the selected clusterheads should cover a large number of nodes as much as possible.

   Nodes in a cluster must be one of the following types [8]:

   Clusterhead (CH): An elected node that acts as the local controller for the cluster. The clusterhead's responsibilities may include: routing, relaying of inter- cluster traffic from cluster members, scheduling of intra-cluster traffic, and channel assignment for cluster members.

   Cluster Member: A normal node belonging to a cluster. Cluster members usually do not participate in routing, and they are not involved in inter-cluster communication.

   Gateway Node (CG): Cluster Gateway is a border node which is used to convey the routing information from one cluster to another. The clusterheads and

   gateway nodes form the backbone network. Gateway nodes selected among the border nodes. A border node is a mobile node which has at least one neighbor belonging to a different cluster. Border nodes are at the perimeter of the clusters. Gateway nodes are those nodes in a non-clusterhead state located at the periphery of a cluster. These types of nodes are called gateways because they are able to listen to transmissions from another node which belongs to a different cluster.

   In a dynamic network the mobility of nodes cannot be ignored. It has a vital role in maintaining the stable cluster structure. Thus we choose mobility of a node to be the deciding factor for initial cluster setup so that a better cluster stability can be achieved. A node with lower mobility has a higher chance of being a cluster head. The weights assigned to the nodes are reciprocal to their respective mobility. i.e. a node with lower mobility is assigned a higher weight and the node with higher mobility is assigned a lower weight. In these paper different types of mobility of nodes in mobile ad hoc network is studied. This paper presents different algorithm to make the cluster more stable.

2. Various Clustering Algorithms Based On Mobility

   1. Distributed Group Mobility Adaptive Clustering Algorithm (DGMA)

      Distributed group mobility adaptive clustering algorithm (DMGA) clustering scheme [1] is used for group mobility in MANETs. The revised SD is used as the mobility metric in DGMA to avoid capturing the instantaneous changes of speed and direction. This makes DGMA scheme more adaptive to the highly mobile environment. Coloring method is introduced in DGMA that a varieties of colors represent nodes in different roles. White indicates the initial color of each node or implies the node has not affiliated with any cluster. CHs are colored with red and cluster members are in yellow. We first introduce the terminology used in DGMA.

      1. T: the duration that two red nodes are directly connected.

      2. n1 : used by a red node to show the ratio of the number of one-hop white neighbors to the number of all one hop neighbors. n1_Input is the input threshold value of n1

      3. n2 : used by a white node to show the ratio of the number of one-hop white neighbors to the number of all one hop neighbors. n2_Input is the input threshold value of n2.

         DGMA clustering has two main processes: the nomination process and the cluster maintenance process. Each node maintains its own status and no centralized entity is responsible for the maintenance of a whole cluster. DGMA begins with the nomination process that has five steps:

         Step 1: Each node begins in white.

         Step 2: A white node, if not connecting with any red node, broadcasts a request to its directly connected neighbors to nominate a red node.

         Step 3: After feedback of individuals TSD from its neighbors, the applicant (node A) compares its TSD with the received TSD values from each of its white neighbors (node B)

         1. If TSD(A, t)< TSD(B, t), nomination process is terminated and it remains as a white node;

         2. If TSD(A, t)> TSD(B, t), continue until node A has compares with all its neighbors.

            Step 4: If the white node has the largest TSD among all of its white neighbors, it turns to red.

            Step 5: It broadcasts an invitation to its neighbors and the receivers in white change their color to yellow.

            For the maintenance process at a node, it is triggered upon detecting the updates of mobility information. Different maintenance steps will be executed according to a nodes color.

            For red nodes (i.e. CHs):

            1. If two red nodes are connected over a time T, the one with smaller TSD turns into yellow;

            2. If more than n1-Input of neighbors are white, i.e. n1

      n1-

      Input, it turns into white.

      For yellow nodes (i.e. member nodes):

      1. If a yellow node has a bigger TSD than any of connected red nodes, it turns itself into white; or

      2. If it fails to find any neighboring red node, it turns into white.

      For white nodes (i.e. free nodes):

      1. If there is a red neighbor that has a larger TSD value than this white nodes, it turns to yellow;

      2. Else, if the component of white nodes in the neighbor set is greater than n2-Input, i.e. n2 n2-Input, it triggers the cluster

      DGMA has a worst case time complexity of O(n) per node, where n is the number of nodes in the network. The proof of the complexity and correctness of the algorithms are omitted due to page limitation.

   2. Distributed MobilityAdaptive Clustering (DMAC)

      The Distributed MobilityAdaptive Clustering (DMAC) algorithm [2] is based on the concept of a clusterhead. This exposed node acts as a local

      coordinator within the cluster and can perform aggregation of topology information and exchange to neighboring clusters.

      When a node is added to the network, it executes an initialization process to determine its role, i.e., whether it should become a clusterhead or an ordinary node. This decision is based on weight wi of the node and the weights of its neighbors: the larger the weight of a node, the better it is suited as a clusterhead. It is assumed that each node has a different weight. A node decides to join a cluster if there is already a neighboring clusterhead with a higher weight; otherwise it decides to become a clusterhead itself. After making this decision, it immediately informs all its neighbors of its role. The algorithm is executed at each node and is message driven. The stable condition is defined by the following three properties; first, every ordinary node has at least one clusterhead as neighbor. Second, every ordinary node affiliates with the neighboring clusterhead with the largest weight. And, third, clusterheads cannot be neighbors.

      This clustering algorithm is a continuously running online process. As the mobile stations move around, they must decide to which cluster they currently belong and which role they have. In order to be adaptive to mobility, each node reacts to changes in the surrounding topology and it changes its status and cluster membership accordingly.

      This decision is based only on the local view of their neighborhood. Whenever a link failure happens, each node checks if its own role is clusterhead and if the other node belongs to its cluster. In this case, the clusterhead removes the node from its cluster. When the link of an ordinary node to its clusterhead fails, the ordinary node must determine its new role in the same way as it does during initialization.

   3. Mobility-based D-Hop Clustering Algorithm (MobDHop)

      A mobility-based d-hop clustering algorithm (MobDHop) [3] forms variable-diameter clusters based on node mobility pattern in MANETs. This algorithm introduces a new metric to measure the variation of distance between nodes over time in order to estimate the relative mobility of two nodes. We also estimate the stability of clusters based on relative mobility of cluster members. A node may become a clusterhead if it is found to be the most stable node among its neighborhood. Otherwise, it is an ordinary member of at most one cluster. When all nodes first enter the network, they are in nonclustered state. A node that is

      able to listen to transmissions from another node which is in different cluster is known as a gateway.

      We use the received signal strength measured at the arrival of every packet to estimate the distance from one node to its neighbor node. Measured signal strength of successive packets is used to estimate the relative mobility between two nodes.

      In this paper, proposed distributed clustering algorithm forms variable-diameter clusters that may change its diameter adaptively with respect to mobile nodes moving patterns. In this paper two mobility metrics based on the relative mobility concept is proposed: (a) variation of estimated distance between nodes over time and (b) estimated mean distance for cluster, in order to measure the stability of a cluster. These metrics are used to decide cluster memberships. Therefore, the formation of clusters is determined by the mobility pattern of nodes to ensure maximum cluster stability. To achieve the desired scalability, MobDHop forms variable-diameter clusters, which allows cluster members to be more than two hops away from their clusterhead. The diameter of clusters is dependent on the mobility behavior of nodes in the same cluster. It also creates lesser and more stable clusters in order to achieve high scalability. The clusterhead change is relatively low.

   4. A Mobility-Based Clustering approach to support moility management

      The clustering approach [4] proposed by Javad Akbari Torkestani and Mohammad Reza Meybodi is based on mobility concepts (individual mobility, group mobility) and the availability of position information via a reliable position locating system (i.e. GPS). Global Position System (GPS) accuracy will be increased and its card cost will be decreased.

      Thus, GPS cards will be mounted in every mobile node. The main idea of this algorithm is to combine both physical and logical partitions of the network, as well as the concept of relative mobility in order to improve the stability in the clustered topology. The mobility-based hierarchical clustering algorithm may result in variable-size clusters depending on the mobility characteristics of the nodes. Several groups can be hierarchically merged into one group depending on the mobility of each group.

      In the following we outline the main steps of the proposed algorithm in order to construct and maintain the various clusters.

      Step 1: Mobility Information Dissemination-Each node n periodically disseminates its velocity information to its neighboring nodes.

      Step 2: Calculation of Mobility Metrics-Upon reception of nodes n velocity information each node m calculates its relative velocity between itself and node n respectively. Then periodically (with period T) each node m calculates the relative mobility between itself and node n.

      Step 3: Initial (Tentative) Cluster Construction-Lets denote by Sm the set that includes node m and all the nodes from which node m receives mobility information.

      The mobility threshold is a design parameter of algorithm and can be used to control the stability of the generated clusters in different networks. Moreover, different mobility threshold parameters that may change dynamically and adaptively during the operation of the network can be used.

      Step 4: Cluster Merging-If a tentative clusterhead is to be included in another cluster according to step 3, then the child cluster joins into the parent cluster with its current cluster members. There is an upper bound (i.e. L hops) rule for merging. After merging the clusterheads, the highest-parent clusters head is selected cluster as the clusterhead of the new generated cluster.

      Step 5: Cluster Maintenance/Reconstruction-When a node m in cluster Ci moves into a cluster Cj, if a node n in the cluster Cj satisfies the condition: relative mobility between a pair of nodes during a time period < mobility threshold, and node n is the clusterhead of the cluster Cj then node m requests clustering to node n (no clusterhead change). If these conditions are not satisfied, node m repeats step 5 during its motion.

      In this paper, proposed cluster architecture consists of variable-size clusters that may change adaptively according to the nodes mobility. The proposed SBC algorithm uses a combination of both physical and logical partitions of the network, as well as the concept of relative mobility that characterizes the degree of mobility of a node with respect to its peers. This algorithm may control and affect the stability of the generated clusters is the mobility threshold.

   5. Mobility-Based Clustering (MBC)

      A mobility based distributed clustering algorithm [5] is proposed in the dynamic network in order to reduce the freezing time of motion of mobile nodes during the initial cluster setup. In this paper, there exists a bidirectional link Lij between the nodes i and j when the distance between the nodes dij < range t (transmission range) of the nodes. In the dynamic network the cardinality of the nodes V remains constant, but the cardinality of links L changes due to the mobility of the nodes.

      The algorithm works with the following assumptions:

      • Nodes in the network have equal transmission range

      • Every cluster head has the information regarding the weight of its member nodes.

      Basically, we consider the mobility of a node by taking the average of the distances covered by it in last n time slots.

      Thus, average Mobility M = Total distance (Dt)/ n Here, instead of taking the most recent mobility of a node a statistics of distances covered by it in last n unit of time is taken. The weight for individual node is inversely proportional to its mobility. That is a node with higher running average is given lower weight and a node with lower running average is given a higher weight.

      During the initial cluster setup phase every node broadcasts its ID along with its weight to the neighbors and stores the weights that it hears from other nodes within its transmission range. If it does not receive any weight higher than its own weight then it declares itself as a cluster head and the entire 1-hop uncovered neighbor nodes (i.e. whose role is not yet decided) become the members of the currently formed cluster. A lower ID node is preferred for cluster head in case of a tie in the weights of the nodes. This process is repeated till all the nodes are assigned with their role either as a head or a member of the cluster. This ensures a fast cluster setup with minimum freezing time of motion by the nodes. The steps of initial cluster formation in the network:

      Step 1: Detect the neighbors of individual node v (i.e. detect the nodes within its transmission range).

      Step 2: For individual v, compute the total distances covered by it in last n unit of time.

      Step 3: Compute the average mobility of individual node v.

      Step 4: Compute the weights of the nodes.

      Step 5: For node v, If Wv Wi where i neighbor (v), then Set head= v .And, If dist ( v, iuncovered ) vtrange then HEAD (iuncovered ) = v.

      Step 6: Repeat step 5 till all the nodes are covered with a status of either a cluster head or a member node.

      The link between every pair of nodes denotes that they are within the transmission range of each other and establish a bidirectional link among each other.

      This proposed algorithm reduces the freezing time of motion of mobile nodes during the initial cluster setup. A record of previous n set of movements of every node is used to predict their average mobility. Choosing low mobile nodes to act as cluster heads ensure better cluster stability as head nodes rarely move.

   6. Mobility and Energy Aware Clustering Algorithm (MEACA)

      Mobility and Energy Aware Clustering Algorithm (MEACA) [6] uses the node mobility and energy status to evaluate and select the most stable nodes to be the cluster heads. Besides, it avoids premature cluster head re-selection to stabilize the formed clusters.

      The objective of clustering algorithm is to form stable clusters in ad hoc networks, where the stableness is measured quantitatively by the cluster head lifetime and the cluster membership time.

      MEACA works in a distributed manner as in the lowest-ID algorithm. The nodes in the network have different priorities to become cluster head. They exchange their priority values to determine who will become the heads and who will become the members. Every node makes its own decision after having collected the priority values of all its neighbors.

      Because each node's priority value is globally deterministic, the nodes in the network are able to reach unanimous decisions on their roles, though each node decides independently.

      Unlike the lowest-ID algorithm that fixes a node's priority level beforehand, MEACA sets the priority using the node's mobility and energy status. For this purpose, each node has a mobility attribute and an energy attribute. Both are kept up to date. When determining its cluster head, a node selects in its neighborhood the node with the relatively lowest mobility and highest energy using these two attributes. The selected node could be one of its neighbors or the selecting node itself. After the cluster head has been determined, the member node registers itself with its clusterhead. Re-clustering takes place only when a member node has lost contact to its head or a head node ha lost contact to all its members. In other words, a node will not change its head and/or role as long as its current cluster remains valid.

      Here proposed the MEACA clustering algorithm uses the node mobility and energy information to stabilize the clusters. MEACA achieves longer lifetime of the cluster heads, longer membership time of the cluster members, and better algorithm scalability than the generalized lowest-ID algorithm, at the cost of slightly smaller cluster size.

   7. A Mobility-Based Cluster Formation Algorithm for Wireless Mobile Ad-Hoc Networks

      In this paper, proposed algorithm [7] is a mobility- based cluster formation algorithm MCFA in which the mobility parameters of the hosts are assumed to be random variables with unknown distributions. In the proposed clustering algorithm, the expected relative

      mobility of each host with respect to all its neighbors is estimated by sampling its mobility parameters in various epochs. MCFA is a fully distributed algorithm in which each mobile independently chooses the neighboring host with the minimum expected relative mobility as its clusterhead. This is done based solely on the local information each host receives from its neighbors and the hosts need not to be synchronized.

      In this algorithm, the expected relative mobility of each host with respect to all its neighbors is defined as a mobility criterion to find the most stable clusters against the network dynamics. Therefore, the proposed algorithm is composed of two main parts. The first part is the initial clustering which is performed as the network starts up, and the second one is the cluster maintenance which is performed whenever and wherever it is required. The relative mobility of each host with respect to all its neighbors is defined as its weight. It is assumed that the mobility characteristics of the host and so the weight associated with the host are random variables with unknown distribution parameters.

      In this algorithm, each host chooses its clusterhead based solely on the local information received from its neighboring hosts. To show the performance of the algorithm, we conducted several simulation experiments and compared the obtained results with the well known existing clustering methods.

3. Discussion

   Each of the clustering algorithms described have some limitations in terms of various aspects. MobDhop algorithm is based on variation of estimated distance between nodes. This algorithm has a drawback, if a node runs out of energy it will transit packets at low power acting as a distanced node from its physically close neighbour. DMAC clustering algorithm is a message driven algorithm. In this algorithm as node density increases, cluster head may become overloaded. To solve this problem the number of node members should be limited and existing cluster should be split into several smaller clusters. The max-min d cluster method does not take account node mobility pattern. If node mobility pattern is considered maximum cluster stability can be ensured. In WCA, a high reaffiliation can be shown when nodes have high mobility. To solve this problem entropy based clustering can be proposed in order to improve network stability.

4. Conclusion and Future Scope

   Clustering algorithms help organize mobile nodes in mobile ad hoc networks in a group and facilitate routing to send packets other nodes in the network. Clustering can provide large-scale MANETs with a hierarchical network structure to facilitate routing operations. These clustering approaches are useful to create stable clusters to avoid frequent reclustering and also increase the cluster life.

   In this survey we have studied several clustering algorithms which help organize MANETs in a hierarchical manner and we have explained their advantages and disadvantages. Clustering methods improve network scalability, routing and topology management of MANET.

   In case of mobility based clustering approach, it is essential to take care of energy of mobile nodes because as mobile nodes are performing some special and extra responsibilities so they will be exhaust earlier than other nodes and re-clustering will be required.

5. References

1. B Yan Zhang, Jim Mee Ng, A Distributed Group Mobility Adaptive Clustering Algorithm for Mobile Ad Hoc Networks 2008 IEEE, page no. 3161-3165.

2. Christian Bettstetter and Stefan Konig On the Message and Time Complexity of a Distributed MobilityAdaptive Clustering Algorithm in Wireless Ad Hoc Networks

3. Inn Inn ER, Winston K.G. Seah, Mobility-based d-Hop Clustering Algorithm for Mobile Ad Hoc Networks WCNC 2004 / IEEE Communications Society, page no. 2359-2364.

4. Beongku An and Symeon Papavassiliou, A mobility- based clustering approach to support mobility management and multicast routing in mobile ad-hoc wireless networks INTERNATIONAL JOURNAL OF NETWORK MANAGEMENT, Int. J. Network Mgmt 2001, page no. 387- 395;

5. Suchismita Chinara , Santanu Kumar Rath, Mobility Based Clustering Algorithm and the Energy Consumption Model of Dynamic Nodes in Mobile Ad Hoc Network IEEE computer society 2008, page no. 171-176

6. Yi Xu and Wenye Wang MEACA: Mobility and Energy Aware Clustering Algorithm for Constructing Stable MANETs

7. Javad Akbari Torkestani, Mohammad Reza Meybodi A mobility-based cluster formation algorithm for wireless mobile ad-hoc networks Springer 2011

8. Mobile Ad-hoc Networks (MANET), http://www.ietf.org/html.charters/manetcharter.html (2009- 11-12)