International Journal of Innovative Research in Computer and Communication Engineering

International Journal of Innovative Research in Computer and Communication Engineering

Menu

ISSN ONLINE(2320-9801) PRINT (2320-9798)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

Clustering & Cluster Head Selection Techniques in Mobile Adhoc Networks

V.Preetha1, Dr.K.Chitra2
  1. Research Scholar, Dept of Computer Science, Bharathiar University, Coimbatore, India
  2. Asst. Professor, Dept of Computer Science, Govt Arts College, Melur, Madurai DT, India
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering

International Journal of Innovative Research in Computer and Communication Engineering

Abstract

In Mobile adhoc Network (MANET) ,networks are formed on-the-fly and devices can leave and join the network during its lifetime. The network thus formed as a whole will be mobile and the devices in the network should be able to detect the presence of other devices and perform the necessary set-up to facilitate communications. Since MANET is considered as a group of mobile terminals, system performance is a challenging task. The throughput and delay factors at the time of mobility and scalability of MANETs is considered as an important feature for efficient processing.Clustering in MANET helps to ensure the performance of MANET to some extent. In the Clustered topology, cluster based routing protocols are used for well-organized routing in MANET. In a Cluster Structure, Cluster Head and Border nodes form a virtual backbone for routing among neighboring clusters. But the Cluster Head selection is an important criterion to be considered because the Cluster Head will be the co-coordinator in Clustered architecture. This comprehensive survey focuses mainly on the cluster Head selection methodology in recently proposed algorithms and the main objectives in choosing a specific node as a cluster head based on its ability in performing the role of the local coordinator, performing transmissions in both intra-cluster and inter-cluster arrangements.

Keywords
MANET, Cluster Based Routing Protocols, Clustering, Cluster Head

INTRODUCTION
A mobile ad hoc network (MANET) is a self-configuring infrastructure less network of mobile devices connected by wireless. These networks can be set up easily anywhere and at anytime. Each device in a MANET is free to move independently in any direction. It may frequently link with other devices. Since routing is an essential strategy, each device may act itself as a router by forwarding the traffic. The primary challenge in building a MANET is equipping each device to continuously maintain the information required to properly route traffic. Due to the advancement in mobile devices and handsets, the need of 802.11/Wi-Fi wireless networking is increasing rapidly. Hence MANETs have become an important research topic.
There are various routing protocols available for MANETs. Routing Protocols are divided into Proactive or table driven routing protocols and reactive or on-demand routing protocols. The communication overhead of link-based proactive routing protocols is O (n2), where n is the total number of mobile terminals in a network [1]. This means that the routing overhead of such an algorithm increases with the square of the number of mobile nodes in a MANET. For a reactive routing scheme, the disturbing RREQ (route request) flooding over the whole network and the considerable route setup delay become intolerable in case of mobility and scalability of MANET. Hence, a hierarchical architecture is essential for increasing the performance in Large Scale MANET. [2].
Since a cluster structure is a typical hierarchical architecture, Cluster based Routing protocols can be used for the routing in MANETs. The CBRP has the following features:
 It is a fully scattered operation
 It reduces the flooding traffic.
 It repairs the broken routes locally.
 It shortens the Sub Optimal routes. [3]
The routing protocol should be such that it can cope up with the changes in the network topology. So, by dividing the network into clusters, now the paths are recorded between clusters instead of between nodes and this increases the routes lifetime, so it decreases the amount of routing control overhead [4].
Clustering also increases the network capacity and reduces the routing overhead which brings more efficient and effective routing in MANET. Every clustering algorithm consists of two mechanisms, cluster formation and cluster maintenance. In cluster formation, cluster heads are selected among the nodes to form the hierarchical network.
This paper mainly focuses on the Cluster based approach for MANETs, Cluster Head selection Techniques based on different parameters and its objectives.

RELATED WORK
Clustering is a process that divides the network into interconnected substructures, called clusters. In a clustering scheme, all the mobile nodes in a MANET are grouped into different geographically distributed groups. Clustering in MANET guarantees many advantages when compared with traditional networks. But due to the unstable nature of MANET clustering in MANET is a difficult task. Cluster based routing protocols are used in clustering approach, but still there exists limitations besides the functionality of the Routing protocols. Clustering focuses on dividing the networks into clusters and to choose a particular node as a Cluster Head. Each cluster group will have a specific node elected as cluster head (CH).The Head node may be selected based on a specific metric or a combination of metrics. Some of the parameters may include the ID of a node, weight and density of a node, degree or mobility of a node etc. The other nodes in a group will communicate with the cluster Head. The cluster Head in a group may communicate with the Cluster Head of another cluster thereby decreasing the unnecessary traffic flow. If a node hears two or more Cluster Heads then it will be the gateway. A cluster is there-fore composed of a cluster head, gateways and member nodes. Clustering in MANET thus improves the efficiency and reduces the chances of interference thereby increasing the network throughput.
Jane Y.Yu and Peter H.J Chong [5] classified the clustering schemes of MANET under six categories as Dsbased, Low Maintenance, Mobility-aware, Energy Efficient, Load balancing and combined metrics based clustering. Cost comparison of the six clustering schemes and communication complexity are analyzed based on the ripple effect of re-clustering, stationary assumptions for cluster formation etc. Many researchers have focused the clustering schemes based on different metrics. Effective and reliable cluster head selection based on different protocols are analysed. Roberto Carlos Hincapi´e, and Laura Ospin [6] classified the Clustering Techniques for Mobile AdHoc Networks into eight categories as Lowest ID heuristic, Highest degree heuristic, k-CONID, Max-min heuristic (α,t)cluster framework , MobDhop , DMAC and WCA and explained their advantages and disadvantages. Many related works focused on the clustering techniques and algorithms ,network scalability in clustering methods ,fairness of choosing a particular node as a cluster head, stability of head node based on different metrics such as Energy, mobility,weight etc.Some of the routing schemes in MANET are analyzed with clustering and scalability issues are considered. Cluster based protocol based on hierarchical routing strategies are focused for efficient routing. Some of the researchers focused mainly on the cost factor based on the scalability and performance of the cluster. In [7] authors classified the clustering approaches based on its objectives and tabulated the advantages and drawbacks of the algorithms. It is obvious that all the above metrics and analysis criteria is based on the efficient routing based on clustering. Since the cluster head is the main role in clustering, various surveys paid attention to the reliable cluster head selection techniques based on a specific parameter.

PROPOSED WORK

Cluster Head:
As mentioned earlier, the cluster head plays the role of a coordinator within its substructure. Each CH acts as a temporary base station within its cluster and communicates with other CHs [8]. Cluster head (CH) election is the process to select a particular node within the cluster as a head node. The responsibility of the CH is to manage the nodes of its own cluster and to communicate with other Clusters. It can communicate with other clusters directly through the respective CH or through gateways. It can communicate by sending and receiving the data, compressing the data and transmitting the data to the other Cluster Heads.
Electing a specific node as a head node is not an easiest task. Depending on different factors such as geographical location of the node, stability, mobility of the node, energy, capacity and throughput of the node, trusted nodes etc the selection criteria may vary. But Cluster Head node may be a special mobile node with extra functions. The following figure represents the structure of a Cluster with Cluster head as the Special node and the cluster members(ordinary node) with white circles and the gateway nodes communicating between clusters.

Classification of Clustering Algorithms:
There are several algorithms in the literature for cluster heads election in mobile ad hoc networks: Lowest-ID [9], Highest-Degree [10], Distributed Clustering Algorithm [11], Weighted Clustering Algorithm (WCA) [12] and Distributed Weighted Clustering Algorithm (DWCA). Based on the hop distance between node pairs in a cluster, Clustering schemes can also be divided into 1-hop clustering and multi-hop clustering. In this paper, efforts have been made to discuss an extensive number of schemes proposed previously for CH election in MANET. CH selection techniques comparison is made in terms of parameters used and the objective of the selection procedure.
The cluster head selection procedure is taken as the main criteria and depending on the different parameters and objectives, the algorithm is classified under five categories. The algorithm is classified as Identifier-based, Connectivity based, Mobility based, Cost based, Power based algorithms as below :
image
The Identifier based algorithms are further classified into Lowest ID cluster algorithm (LIC) and Max-Min d-cluster formation algorithm.The cluster head selection procedure is based on the ID of the node.The Connectivity based algorithms are further classified into Highest connectivity clustering algorithm (HCC), K-hop connectivity ID clustering algorithm (KCONID). Adaptive cluster load balance method and Adaptive multihop clustering (With load balancing capabilities).The connectivity based method focuses mainly on the selection of a particular node as a head node based on the neighborhood connectivity. The connectivity based method with its load balancing efficiency calculates the efficient cluster head with the help of the number of mobile nodes connected. The mobility aware clustering is further classified into Mobility-based d-hop clustering algorithm, Mobility Based Metric for Clustering and Mobility Based framework for Adaptive Clustering. This approach focuses on the stability of a mobile node based on its speed, variance and selects the head which is more stable than the other nodes. The Low cost of maintenance clustering algorithm is classified into Least cluster change algorithm (LCC), Adaptive clustering for mobile wireless network and 3-hop between adjacent cluster heads (3-hBAC).This algorithm mainly focuses on the reduction of communication overhead caused by cluster maintenance. The method of selecting the cluster head is based on the ID.Depending on the cluster maintenance the cluster head selection is paid attention on the cluster formation phase and cluster maintenance phase. The power aware clustering is classified into Power-aware connected dominant set, clustering for energy conservation, Weighted clustering algorithm and Entropy-based Weighted clustering algorithm. Energy level is considered as the main criteria in this classification.

RESULTS
The classification results are tabulated as below based on the methodology of the cluster head selection procedure :
image
image
image

CONCLUSION AND FUTURE WORK
As MANETs have attracted more attention in recent years, much research has been addressing all kinds of issues related to them .Since a large-scale MANET cannot guarantee performance with a flat structure, many cluster hierarchy algorithms have been proposed to solve the scalability issue. In this article, we first provided fundamental concepts about MANET, importance of Hierarchical structure, cluster Based Routing Protocols, Clustering in MANET including the definition of cluster and clustering, importance of Cluster Head selection for a large dynamic MANET Clustering. Then we classified proposed clustering schemes into five categories based on their main objectives in choosing the Cluster Head Selection Procedure. With this survey we see that a cluster Head selection in MANET has many important issues to examine in the fairness of serving as cluster heads for a mobile node. Also, different types of clustering schemes may have a different focus and objectives such as Identifier –Based, connectivity –based, Mobilitybased, cost-based, and Power-aware based. Although each scheme is well suited for certain scenarios, based on its efficient Cluster Head it is not guaranteed that any one of them is the best for all situations. The future research will be focused on the more efficient and effective clustering schemes and a combination of different parameters in choosing the effective Cluster Head in Cluster Topology for MANETs.
 

Figures at a glance
Figure 1
Figure 1
 

References