Mobility Based Cluster Head Selection Algorithm for Mobile Ad-Hoc Network

Published Online June 2014 in MECS

Mobile Ad-Hoc Network (MANET) [1] is basically a peer to peer network, which consist of moveable or mobile nodes interconnected by wireless links [2]. In a clustering scheme the mobile nodes in a MANET are divided into different groups, and they are allocated geographically adjacent into the same cluster according to predefined rules with different behaviors for nodes included in a cluster [3]. A typical cluster structure can be seen as the nodes are divided into a number of virtual groups based on certain rules [4]. Under a cluster structure, mobile nodes may be assigned a different status or function, such as cluster head, cluster gateway or a cluster member. It was observed that cluster architecture guarantees basic performance achievement in a MANET with a large number of mobile terminals. A cluster structure facilitates the spatial reuse of resources to increase the system capacity [4]. With the nonoverlapping multi cluster arrangement, two clusters may arrange in the same frequency or code set if they are not neighboring clusters. This can save much more resources that are used for retransmission, resulting from reduced transmission collision. The second benefit of cluster is in routing, because the set of cluster heads and cluster gateways can normally form a virtual backbone for intercluster routing, and thus the generation and spreading of routing information can be restricted in this set of nodes. A cluster structure also makes an Ad-Hoc network appear smaller and more stable in view for each mobile terminal.

Our aim in this paper is to provide an improved algorithm for cluster maintenance, which can be only achieved by a better head selection process. The rest of the paper is organized as follows: Section 2 gives an overview of routing protocols; Section 3 deals with cluster based routing protocols and proposed algorithm. Finally, the paper concludes with future research direction in section 4.

• II.    Related Work

AODV [6], DSDV [7], DSR [8] are commonly used routing protocol in MANET, a simulation study of the existing available routing protocol for wireless Ad-Hoc network was given by Mohamed et al in his paper [5], the simulation results in the paper show that AODV and DSDV can be used for most of the Ad-Hoc applications, which can deliver about 95% of data packets to the destination nodes. Another performance analysis of the three routing protocols in wireless mobile Ad-hoc networks was given in [9]. Ambhaikar in his paper [10] has analyzed that the performance of AODV protocol is better than the DSDV protocol. Considering the ability of AODV to maintain connection by periodic exchange of information, performance of AODV is better than the other two protocols. Karthiga in his paper [11] has observed that DSDV performance is best considering its ability to maintain connection by periodic exchange of information, which is required for TCP, based traffic. Routing protocols can be classified in to two categories, they are: single channel and multi channel routing protocols. Further single channel routing protocol can be classified as uniform and non uniform routing protocols.

Table I C omparative study of DSDV, DSR, AODV, CBRP

Protocol Property	DSDV	DSR	AODV	CBRP
Table driven/ Source Routing	Table driven	Source Routing	Source Routing	Source Routing
Need of Hello message	Yes	No	Yes	Yes
Route Discovery	Periodic	On Demand	On Demand	On Demand
Route mechanism/ Maintenance in	Route table With next hop	Complete Route cached	Route table with next hop	Route table with next hop
Network Overhead	High	Low	Medium	Medium
Node overhead	Medium	High	Medium	Less
Multi-hop Wireless Support	Yes	Yes	Yes	Yes
Loop free	Yes	Yes	Yes	Yes
Multiple Routes	No	Yes	No	Yes
Unidirectional link support	No	Yes	No	Yes
Network Suitable for	Less number of nodes	Up to 200 nodes	Highly Dynamic	Highly Dynamic
Route Maintenance	No	Yes	Yes	Yes
Reactive/ Proactive	Proactive	Reactive	Reactive	Reactive
Routing Overhead	Medium	Low	High	High
Packet size	Uniform	Non Uniform	Uniform	Uniform
Routing Philosophy	Flat	Flat	Flat	Hierarchical

Fig. 1: Taxonomy of Protocols

Uniform channel routing protocols can be divided into two main streams, topology based and destination based. On the other hand Non uniform channel routing protocol are categorized into three types, they are Hierarchical (CBRP [12]), Flat, and Geographical. Comprehensive literature surveys of available reactive and proactive protocol are given in next section, and Table 1 gives a comparative study of available routing protocol DSDV, DSR, AODV, CBRP.

Clustering is a hierarchical type of routing in which paths are recorded between clusters instead of between nodes. There are several clustering algorithms based on dominating sets, they are: Lowest-ID Cluster algorithm (LIC), Max-Min d-cluster formation algorithm, Highest connectivity clustering algorithm (HCC), K-hop connectivity ID clustering algorithm (K-CONID), Adaptive cluster load balance method, Mobility-based d-Hop Clustering Algorithm (MobDHop), Load balancing Clustering (LBC), Power-aware connected dominant set, Weighted clustering algorithm (WCA), Distributed Weighted Clustering Algorithm, Efficient Weighted Distributed Clustering (CBMD), Mobility Based Metric for Clustering (MOBIC). A brief overview of each mechanism is discussed below:

• A.    Lowest-ID Cluster algorithm (LIC)

Lowest-ID cluster a-lgorithm [13] is a simple procedure whose objective is to simplify the cluster head selection procedure. Nodes are candidates to be cluster heads based on their node id. Few of the disadvantages are: many cluster heads are elected, reclustering procedure is followed when there is a node movement or a node dies in the network.

• B.    Max-Min d-cluster formation algorithm

Max-Min d-cluster formation algorithm [14] is used to overcome the disadvantages of LIC, generalizes the cluster definition to a collection of nodes that are up to d-hops away from cluster head. The metric considered in this algorithm is ‘size of the cluster’. This algorithm has few disadvantages, these are: load balancing, mobility, power metrics was considered, and how to select value of d is not specified.

• C.    Highest connectivity clustering algorithm (HCC)

Highest connectivity clustering algorithm [15] decreases the number of clusters, and considers cardinality of nodes as evaluation metrics. Advantages of HCC is that the no of nodes in a cluster increases but no of cluster in the node decrease. Limitation of HCC includes: no limit to the maximum no’s of nodes, cluster head becomes the bottleneck, flooding of control messages in the entire networks, and re-affiliation count is high.

• D.    K-hop connectivity ID clustering algorithm (K-

• CONID)

To get the advantages of LIC and HCC, K-hop connectivity ID clustering algorithm [16] is used, where size of the cluster is considered as metrics. By combining both LIC and HCC, can limit on number of clusters by using HCC as first criterion. Every node in K-CONID needs to maintain two parameters.

• E.    Load balancing Clustering (LBC)

Load balancing Clustering [17] considers energy level as metrics. The advantages of LBC includes: no cluster head bottleneck since the newly chosen mobile nod would be having good energy level, and its previous cluster head serving time is the shortest in its neighborhood.

• F.    Adaptive cluster load balance method

Adaptive cluster load balance method [18] is used to overcome the disadvantages of HCC and to achieve load balancing between various clusters by distributing resources to all clusters instead of few clusters. Load balancing can be achieved, but it cannot eliminate the tie between same nodes having same cardinality.

• G.    Weighted clustering algorithm (WCA)

Objective of weighted clustering algorithm [19] is to select cluster head which is not biased towards only a specific metrics like battery power, node degree, and mobility. So, selecting cluster head by considering more than one metric. In WCA, cluster head election algorithm is only invoked based on node mobility and when the current dominant set is incapable to cover all the nodes. Disadvantages of WCA are: knowing the weights of all nodes before starting the clustering process, and drains the cluster heads rapidly.

• H.    Mobility-based d-Hop Clustering Algorithm

(MobDHop)

The objective of mobility-based d-Hop clustering algorithm [20] is to form variable diameter clusters based on node mobility pattern to ensure maximum stability. MobDHop makes clusters more stable, and minimizes the number of clusters by considering group mobility pattern

• I.    Mobility Based Metric for Clustering (MOBIC):

MOBIC [21], [22] protocol proposes a local mobility metric for a cluster formation process. Moreover, clusters are formed in such a way that, mobile nodes with low speed relative to their neighbors have the chance to become cluster-heads. The aggregate mobility metric is computed over a small time period by calculating the variance of relative mobility between a node and all its neighbors. The only difference between Lowest-ID and MOBIC is that it uses mobility metric for cluster formation instead of ID information. In this protocol, the received power level of two successive hello message transmissions is measured by each node from its neighbor. First, the pair wise relative mobility metrics is computed and then aggregate relative mobility metric is computed before sending the next broadcast packet to its neighbors. In hello message every node broadcasts its own mobility metric to its 1-hop neighbors, and it is stored in the neighbors table of each neighbor with a timeout period. In such a way, every node receives the aggregate mobility values from its neighboring nodes, and then compares its own mobility value with those of its neighbors. The node having the lowest mobility value amongst all its neighbors is selected as cluster-head. Few important characteristics of MOBIC are as follow:

• •    If two neighboring nodes in a cluster is in undecided state and having the same value of aggregate relative mobility metric, then their IDs information is used and Lowest-ID algorithm is followed.

• •    If a node with Cluster Member status having low mobility moves into the range of another Cluster Head node which is having higher mobility, then re-clustering is not done.

• •    If two nodes with status Cluster Head move into each other’s range, re-clustering 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 Cluster Contention Interval timer has expired, re-clustering is triggered, and the node with the lower mobility metric selected as cluster head.

In case of particular scenarios where the relative mobility between nodes does not differ drastically, the mobility metric gives better results. A classification of available mobility model is given Fig. 3.

• III.    Cluster based Routing Protocol

Cluster based routing protocol (CBRP) [12] is an on-demand, hierarchical routing protocol that uses its cluster structure for routing, and where nodes are the basic elements to form a cluster. Every cluster has a cluster head, which acts as a controller within the substructure. Each cluster head acts as a temporary base station within its region or cluster, and communicates with other cluster head with the help of a gateway.

• A.    Terms used in CBRP

Cluster based routing protocol (CBRP) uses network architecture as shown in Fig. 2. CBRP uses the following terminologies:

• 1.    Cluster Head: A cluster head, serves as a local coordinator for its cluster, performing Inter-cluster routing, data forwarding and so on. In our selforganized clustering scheme the cluster head only serves the purpose of providing a unique ID for the cluster, limiting the cluster boundaries.

• 2.    Cluster Gateway: A cluster gateway is a node which resides between two clusters and it is a non cluster-head node with inter-cluster links, so it can access   neighboring clusters and forward

• 3.    Cluster Member (Node) : A cluster member is a node that is neither a cluster head nor a cluster gateway.

information between clusters.

Fig. 2: Structure of a cluster

• B.    Advantages and Disadvantage of CBRP

In CBRP, nodes of a wireless network are separated into several disjoint or overlapping clusters. In each cluster, one node becomes cluster head, which is responsible for routing process, and is capable to communicate with other cluster head through gateway nodes. A general structure of a cluster is shown in Fig. 1, where nodes 4, 7, 10 marked as back color are gateways. Each member node belongs at least to one cluster. If a new node joins or appears in the existing network, than that node is known as undecided member, that means that the node does not belong to any clusters. If a cluster head detects a bi-directional link to another cluster head (that has lower ID) for a threshold time period, than immediately, the cluster head changes its status as member [23]. CBRP uses cluster adjacency table (CAT) as data structure for storing neighboring clusters information [24], and there exit one bi-directional link or two opposite unidirectional link between two nodes of a clusters. A two-hop topology database is build from the information received by HELLO messages, which contains all of the nodes that are at most two hops away. Route discovery is done by using source routing. The routing process works in two phases: first, it discovers a route from a source node (say S1) to a destination node

(say D1), afterwards it routes the packets. In CBRP, only cluster heads are used to broadcast route request (RREQ), and gateway nodes are only used to collect them, and forward them to subsequently cluster head. This strategy reduces the network traffic. CBRP includes two mechanisms to improve a route, the first is ‘local repair’ and the second is ‘route shortening’. If a connection between two nodes fails, CBRP is intelligent enough to fix the route. Sometimes a node may find that a connection exist between itself and another succeeding node of the route that is not its direct successor respectively. This can be detected by investigating the information stored in the two-hop topology database. If so, it shortens the route by not including the redundant node from the route.

CBRP scheme is very useful in a situation where lots of devices want to share a common network within short area space where density is very high. In such case, CBRP is very effective due to its smaller cluster formation. Cluster approaches on routing in mobile ad-hoc networks are high-quality technique to reduce network traffic and routing drawbacks. Like other routing protocols, CBRP has few limitations compared to other routing protocols. If a cluster becomes too large, the overhead and operating cost per packet increases due to source routing.

Fig. 3: Classification of Mobility Model

• C.    Challenge of CBRP

• 1.    No centralized entity: The formation of cluster and communication between them depends on the selection of cluster heads.

• 2.    Mobile host is no longer just an end system.

• 3.    Acting as an intermediate system.

• 4.    Changing network topology over time: In cluster based routing protocol nodes are mobile and they can change their positions from time to time, so it may create another hazard, i.e. the network topology may also change in accordance with the change of cluster formations.

• 5.    Each and every node can be mobile: As it is well known that MANET consists of moveable nodes in the system so it is very difficult to keep track of these nodes. This creates another problem.

• D.    Algorithm overview: Clusterformation/ maintenance

In this paper, we have proposed a new algorithm i.e. simple and efficient, which maintain structure of a cluster. In this algorithm we are assuming existence of a cluster and a cluster head M1 as shown in Fig. 4. Let’s say, N1 is a new node that want to join the existing cluster, so N1sends a “hello” message to M1. Now there should be some protocol so that the new node N1 can be part of the existing cluster, or become a gateway if N1 is not a part of the existing cluster. N1 can be the cluster head or a normal node.

If N1 is not a cluster head, and there exist a ‘neighbor table’ in cluster head of another cluster (say Cluster B), then N1 can be referred with a copy of the neighbor table from the cluster head, this is similar like the concept of inheritance. The neighbor table can be maintained in an array. So there is no overhead of accessing data in the system. According to Fig. 4, in cluster A, there are three nodes present, namely S1, K1 and M1. In the first scenario, it is assumed that that M1 is the cluster head. Here neighbor table (NTABLE) is an array of neighbors organized in a table. NODEID is the identification number of a node in the cluster. NTABLE [0] is the location where the id of the existing cluster head in a cluster is stored. NODEID in the id of new node want to attach in the cluster. Here aggr_relative_mob function is used, which will calculate the aggregate relative mobility and return one integer number. We are assuming these are already initialized as the cluster in already formed.

Fig. 4: Structure of the preformed cluster

Here we proposed an algorithm below, which can determine the cluster head in a cluster. It can work even if there is no existence of cluster head in the cluster. From literature survey and theoretical analysis, it is expected that, the algorithm will work better than the other algorithm proposed by other researcher, like LEACH. In future, we will do simulation study on the algorithm, and will try to improve it, and also we will implement the algorithm as in paper [25, 26].

Algorithm:

K: inte-ger       /* number of nodes in the cluster */

NTABLE: array [1...k] /* neighbor table*/

NODEID: integer        /* identification number of a node in the cluster */

CLSHEAD: integer      /*temporary variable for holding the id of cluster head */

X: integer         /* acting as a flag: initialized by 0 */

J: integer aggr_relative_mob (NODEID) : integer

/* function which will calculate the aggregate relative mobility of a node */ integer aggr_local_mob (NODEID) : integer

/* function which will calculate the aggregate local mobility of a node */

Begin

• /* M1 receives a “hello” packet from node N1 */

For all (J=1to K) do

If (NODEID (N1) == NTABLE [J]) then

• X: =1 ; /* N1 is a member of that cluster*/ break;

End if

End for

CLRHEAD=NTABLE[0] /*copying the id of existing cluster head */

If X=0 then /* N1 is not a member of that cluster*/

• K :=K+1;

NTABLE [K]:= NODEID (N1);

If CLRHEAD = NULL /* There is no cluster head */

For all (J=1to K-1) do

If (aggr_local_mob

(NODEID(J))>aggr_local_mob

(NODEID(J+1))) then

CLRHEAD := NODEID(J)

End if

End for

Else If aggr_relative_mob(CLRHEAD) > aggr_relative_mob (NODEID (N1))

CLRHEAD := NODEID(N1)

/* Node M1 becomes a member of N1 and acts as a normal node in the cluster */

Else if aggr_relative_mob (CLRHEAD) = aggr_relative_mob (NODEID (N1))

If aggr_local_mob (CLRHEAD) < aggr_local_mob (N1)

CLRHEAD := NODEID(N1)

/* M1 becomes a member of N1 and acts as a normal node in the cluster */

End if

Else

/* Wait for the next event occurrence. */

End if

NTABLE[0] =CLRHEAD /*copying the id of existing cluster head from temporary variable*/

Else

• /* N1 is in the neighbor table. Wait for the next event

occurrence. */

End if

• IV. Conclution

As MANETs have attracted more attention in recent years, lots of research has been done addressing all kinds of issues related to them. Among them, cluster based routing is an important research issues and research associated with routing is always in focus. Dynamic routing plays an important role in the performance of a MANET. In this paper, we first discussed fundamental concepts about routing protocols including the definition of cluster and clustering, and then the necessity of clustering for a large dynamic MANET, and its side effects and cost of clustering. We also classified routing protocols, and then we proposed an algorithm for cluster formation and maintenance.

With this survey, readers can have a more comprehensive understanding of MANET clustering, especially those schemes discussed in this article. Although each scheme is well suited for certain scenarios, it is not guaranteed that any one of them is the best for all situations. We hope that this survey article can facilitate researchers to offer more efficient and effective clustering schemes for MANETs.