International Journal of Innovative Research in Computer and Communication Engineering
MenuISSN ONLINE(2320-9801) PRINT (2320-9798)
ISSN ONLINE(2320-9801) PRINT (2320-9798)
B.Sindhuja1, Dr.J.Shanthini2
|
| Related article at Pubmed, Scholar Google |
Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering
Mobile Ad Hoc Networks (MANET) is a network composed of many nodes via wireless links which has dynamic topology in nature. Nodes of MANET are divided in to clusters for temporary communication from source to destination. Each node in a cluster is supervised by a leader node known as cluster head (CH). The works of cluster head is to maintain the affiliated node list and also to communicate with the other clusters. Maintaining of cluster head has some advantages like it allows fast communication, topology management, better routing. Cluster head improves the performance of network parameters like routing delay bandwidth consumption and throughput. For cluster head selection the parameters like mobility, connectivity, battery power etc. This paper presents the survey of different schemes for choosing the cluster head and comparison of weights that are given to different parameter factors and decisions are taken after calculating the weights of the nodes.
Keywords |
| Mobile Ad Hoc Networks, Clustering, Gateway, Cluster Head Election. |
INTRODUCTION |
| Ad hoc networks are wireless, infrastructure less, multi-hop, dynamic networks established by a collection of mobile nodes. Ad hoc networks are lacked in infrastructure, cost effectiveness and easiness in installation. The major issues in cluster based MANETs are topology assignment, mobility management, overhead of cluster head and frequent leader re-election. There are no stationary nodes or base stations, each node in the network act as the router that forwards the packet to other nodes. Due to the nodes heterogeneity nodes will have highly variable amount of resources and this produces the hierarchy in their roles inside the networks. Nodes with large computational and communication power, powerful batteries are suitable for MANET. |
| Cluster head selection leads to maintain the information related to the cluster. The information like list of nodes in a cluster and path to every node are informed. Electing the leader for a cluster is very important but sophisticated job. The factors like location of the node, mobility, energy and throughput are considered in electing the cluster head. Communication done with the node in the other cluster can be done directly by a cluster head or through gateways. |
A. Routing In Mobile Ad Hoc Networks: |
| Routing can be defined as the process of choosing the path to send the packet from source to destination among different networks. The reoccurring problem in mobile ad hoc network is routing, since each node act as the router. Every node in the network differs from one another in terms of energy, memory and mobility. The routing can be static or dynamic. |
| A1.Static Routing |
| The static routing is that configured manually on a router by network administrator. The routing table holds the information about the network and is connected directly to the router. |
| A2.Dynamic Routing |
| The routing makes use of the routing protocols to find the routes. It knows the path to reach the destination. |
CHARACTERISTICS OF ROUTING |
| The important characteristics of MANET are: |
| ïÃâ÷ Dynamic nature of the nodes |
| ïÃâ÷ Limited bandwidth |
| ïÃâ÷ The nodes uses the batteries so it limits the power usage |
| ïÃâ÷ Security issues |
| B1. Terminologies Used in Routing |
| The commonly used routing terminologies are briefed but they are not limited to, |
| i) Routing |
| It is process of communicating the data packets from one node to the other node within (or) outside its range of transmission. |
| ii) Router |
| It acts as a passage for directing the data packets among the network. |
| iii) Route Discovery |
| During communication when a source desires to establish a route to the destination, it searches across the network to find the destination (or) either an intermediate node containing the route to destination. |
| iv) Route Establishment |
| When a source wants to communicate with other nodes it broadcasts the requests all over the network and tries to communicate in order to transmit the data packets to destination. |
| v) Route Deletion |
| The route between the sender and the receiver are maintained until it is no longer needed in multicasting after which the route is removed using route deletion process. |
| vi) Routing Table |
| In MANET each and every node has the privilege to act as hosts and routers which periodically updates all the known routes for every other node into a table called the routing table. |
CLUSTERING SCHEMES |
A) Lowest-ID Clustering Algorithm (LIC) |
| In this algorithm each node is assigned a unique identifier (ID) and the clusters are formed based on the given steps: |
| 1. It broadcasts the ID to all the nodes including itself |
| 2. That node will hear the ID’s of all other nodes that are greater than the particular node |
| 3. The lowest ID node is considered to be the cluster-head, unless lowest ID gives up its role as a clusterhead |
| 4. Gateway is a node that has two or more cluster heads, otherwise the node is the ordinary node. |
| Major drawbacks of this algorithm are its bias towards nodes with smaller ids which may lead to the battery drainage of certain nodes, and it does not attempt to balance the load uniformly across all the nodes. |
B) Highest Connectivity Clustering Algorithm (HCC) |
| Each and every node will broadcast its ID to the neighbour nodes within the transmission range. This algorithm is also known as connectivity-based clustering algorithm; here the degree for each node is calculated. The node that contains the maximum number of neighbour is selected as the cluster head. Some disadvantages are |
| There will be fewer throughputs when the degree of the node increases because resources which are available to the cluster heads are shared between its neighbours. |
| There is no limit of nodes in the cluster |
| The re-affiliation count of nodes is high due to node movement |
C) Load Balancing Clustering (LBC) |
| It provides the balance of load on the elected cluster heads. It is desirable for the elected nodes to stay as a clusterhead up to some maximum specified amount of time, or budget. Budget is a user defined constraint placed on the heuristic and can be modified to meet the specific characteristics of the system. Two local variable are maintained physical Id (PID) - unique id for each node and virtual Id (VID). Initially, PID is same as VID. And then VID is modified with time because it is used as the cluster election heuristic. Mobile nodes having the highest IDs in their local area elected as cluster head first. LBC limits the maximum units that a node can serve as a clusterhead continuously by budget, so when its duration budget gets over, it resets its VID to 0 which is less than any other node and becomes a non-clusterhead node. When two cluster heads move into the range of each other, the one having higher VID wins the clusterhead role. When a clusterhead resigns, a non-clusterhead with the largest VID value in the neighbourhood can resume the clusterhead function. |
D) Power aware connected domain set` |
| It is the energy efficient clustering algorithm that reduces the size of the dominating set(DS) without affecting its functions. Here routing is based on the connected dominating set so it removes the unnecessary nodes. Based on the energy level of each host and node degree the dominating set is connected. Energy level is used as the metric for the clusterhead election. Nodes in the DS consume more energy than nodes outside the set because they handle extra responsibilities like updating routing information and handling of traffics. So, it is required to minimize the energy consumption of the DS. A mobile node can be deleted from the DS when its close neighbour set is covered by one or two dominating neighbors, and at the same time it has less remaining energy than the dominating neighbors. |
E) Weighted clustering algorithm (WCA) |
| The WCA is based on the use of a combined weight metric. For clusterhead election the metrics used are the number of neighbors, distance with all neighbors, mobility and cumulative time for which the node acts as the clusterhead. By rebroadcasting each node knows the weight values of all other nodes and information of other cluster heads in the system. So, there is high overhead induced by WCA. The disadvantage of WCA is, if a node moves into an area that is not covered by any clusterhead then the cluster set-up procedure is invoked again which causes reaffiliations. A Hello message contains its ID and position. Each node builds its neighbour list based on the Hello messages received. Each node calculates its weight value by following algorithm. |
| Step 1: Find the set of neighbors of each node v called N(v). (e.g. if the distance between v and v' is less than the transmission range of v then v' is neighbor of v). Set dv, the degree of v. |
| Step 2: Calculate the degree-difference for each node It is the pre-defined threshold means the number of nodes that a clusterhead can handle ideally. |
| Step 3: For every node, calculate the sum of the distances v D with all its neighbors. Then compute the running average of the speed for every node until current time T. This gives a measure of mobility v M where it defines the position of the node v at instant t. Compute the cumulative time v P during which a node v acts as cluster-head. v P indicates how much battery power has been consumed, which is assumed more for a cluster-head than an ordinary node. |
| Step 4: Calculate the combined Weight v W for each node v |
| Step 5: The node with the smallest v W is elected as cluster-head. And then all ordinary nodes of the selected clusterhead are not allowed to participate in the election process |
| Step 6: Repeat steps 2 to 5 for the remaining nodes which are not yet selected as a cluster-head or assigned to a cluster |
F) A Distributed Weighted Clustering Algorithm |
| It works same as WCA except that power management and distributed cluster set up is done by localizing configuration and reconfiguration of clusters. The consumed battery power is a better measure than the cumulative time during which the node acts as a clusterhead that is used in WCA because it reflects the actual amount of power usage. If there is insufficient battery power then lifetime of topology can be increase by switching the role of the clusterhead to an ordinary node. Two situation can invoke the cluster maintenance phase, when there is node movement outside of its cluster boundary and when there is excessive battery consumption at the clusterhead. When an ordinary node moves outside of its cluster boundary, it is required to find a new clusterhead to affiliate with. If it finds a new clusterhead, it hands over to the new one cluster. If not, it declares itself as a clusterhead. Each clusterhead updates the amount of consumed battery power when it sends and receives packets. If the amount of consumed battery power becomes more than a pre-defined threshold value then the clusterhead resigns and becomes an ordinary node. This algorithm provides better performance than WCA in terms of the number of reaffiliations, end-to-end throughput, overheads during the initial clustering set up phase, and the lifespan of nodes. |
G) An Efficient Weighted Distributed Clustering (CBMD) |
| It uses different weight function which takes into consideration the parameters: connectivity (C), residual battery power (B), average mobility (M), and distance (D) of the nodes to choose locally optimal cluster heads. Advantages of this clustering algorithm are load balancing between the clusters is achieved and less number of clusters formed by specifying the maximum and minimum number of nodes that a clusterhead can ideally handle. Furthermore, each mobile node starts to measure its weight after n (small integer in order to minimize the memory requirement) successive HELLO messages, where the result specifies the accurate value for the mobility and battery power. This algorithm is used to elect optimal cluster heads and divide optimal number of clusters without degrading the whole network performance, to satisfy the load balancing between clusters, to maximize the cluster stability and to reduce the communication overhead and minimizing the explicit control messages caused by cluster maintenance. |
COMPARATIVE ANALYSIS |
| Comparative analysis of certain techniques has been shown in the following Table |
 |
 |
CONCLUSION AND FUTURE WORK |
| Cluster based routing is a most convenient way for developing efficient routing scheme in MANET. But it has to deal with several problems like control overhead of cluster formation and maintenance, battery Power, stability of cluster, fairness, load balancing etc. So, to optimize the cluster head election algorithm and to perform efficient cluster based routing in MANET, it is necessary to consider all metrics rather than focusing on particular metric. |
References |
|