HM Medical Clinic

 

An enhanced performance clustering algorithm for manet

An Enhanced Performance Clustering Algorithm
for MANET
Roxana Zoican, Ph. D. POLITEHNICA University of Bucharest, Electronic and Telecommunication Faculty, Telecommunication Department, Iuliu Maniu 1-3, 77202, Bucharest 6 E- Mail : [email protected]
Abstract - Clustering of mobile nodes among separate domains consumption, to increase the effective network capacity, its
has been proposed as an efficient approach to mimic the security mechanisms and to reduce the end to end delay.
operation of the fixed infrastructure and manage the
resources in multi-hop networks. In this paper, it was
analyzed a weight-based clustering algorithm. This algorithm
II. OVERVIEW OF THE EXISTING ALGORITHMS is called Enhanced Performance Clustering Algorithm
(EPCA). It selects clusterhead according to its weight
computed by combining a set of system parameters and
A large number of approaches have been proposed for defines new mechanisms as cluster division, merging the election of clusterheads in mobile ad hoc networks. The
diminution and extension. EPCA was simulated and tested in Highest-Degree Clustering Algorithm (HDCA) uses the degree
real conditions in a campus environment.
of a node as a metric for the selection of clusterheads. The degree of a node is the number of neighbors each node has. The node Keywords: MANET, Clustering Algorithm, Weight, Election.
with maximum degree is chosen as a clusterhead; since the degree of a node changes very frequently, the CHs are not likely to play their role as clusterheads for very long. In addition, as the number of ordinary nodes in a cluster is increased, the throughput drops and system performance degrades. The Lowest-ID Recently, most research is focusing on clustering Algorithm (LID) chooses the node with the lowest ID as a in multi-hop networks in order to build a virtual backbone clusterhead, the system performance is better than HDCA in formed by a set of suitable representative nodes. The main terms of throughput. challenge is to elect the clusterheads (CHs) which However, those CHs with smaller IDs suffer from the guarantee the communications across the formed clusters. battery drainage, resulting short lifetime of the system. The The clusters are able to store minimum topology Distributed Clustering Algorithm (DCA) and Distributed information; each CH acts as a temporary base station Mobility Adaptive clustering algorithm (DMAC) are enhanced within its zone or cluster and communicates with other versions of LID; each node has a unique weight instead of just CHs. An example of multi-hop networks is a mobile ad hoc the node's ID, these weights are used for the selection of CHs. A network (MANET) characterized by a collection of node is chosen to be a clusterhead if its weight is higher than any wireless nodes that are arbitrary and randomly changing of its neighbor's weight; otherwise, it joins a neighboring their locations and capabilities without the existence of any clusterhead. The DCA makes an assumption that the network centralized entity. Therefore, any clustering scheme should topology does not change during the execution of the algorithm. be adaptive to such changes with minimum clustering Thus, it is proven to be useful for static networks when the nodes management overhead incurred by changes in the network either do not move or move very slowly. The DMAC algorithm, topology. Recent works suggest CH election exclusively on the other hand, adapts itself to the network topology changes based on nodes' IDs or location information; however and therefore can be used for any mobile networks. However, the these algorithms suffer from single point (CH) of assignment of weights has not been discussed in the both bottleneck especially in highly mobile environments, hence algorithms and there are no optimizations on the system initially elected CHs have to collect excessive amounts of parameters such as throughput and power control. information and soon reach battery exhaustion. Other Instead of static weights, MOBIC uses a new mobility works take into account additional metrics (such as energy metric, Aggregate Local Mobility (ALM) to elect CH. ALM is and mobility) and optimize initial clustering. However, in computed as the ratio of received power levels of successive many situations re-clustering procedure involves frequent transmissions (periodic Hello messages) between a pair of nodes, broadcasting of control packets even when network which means the relative mobility between neighboring nodes. topology remains unchanged. In addition, a topology Least Clusterhead Change Algorithm (LCC) allows minimizing control mechanism is required to mitigate the vulnerability clusterhead changes that occur when two CHs come into direct of such clusters due to node joining/leaving and link contact. In such a case, one of them will give up its role and failures. It aims to reduce interference and energy some of the nodes in one cluster may not be members of the 978-1-4244-5794-6/10/$26.00 2010 IEEE other CH's cluster. Therefore, some nodes must become CH while causing a lot of re-elections because of the propagation of such changes across the entire network. The Weighted Clustering Algorithm (WCA) is based on the use of a combined weight metric that takes into account several Ti is the received trust value from node i. parameters like the node-degree, distances with all its b- Nn: is the number of neighbors of a given node, neighbors, node speed and the time spent as a clusterhead. within a given radius. Although WCA has proved better performance than all the c- Power: this factor is the capability of a node to serve previous algorithms, it lacks a drawback in knowing the as long as possible weights of all the nodes before starting the clustering d- The Maximum of Nodes: as defined above, this process and in draining the CHs rapidly. As a result, the parameter is used in the election procedure to elect as clusterhead overhead induced by WCA is very high. the node which can handle the maximum of nodes. The Mobility-based d-hop Algorithm (MBCA) is e- Stability: this is a useful parameter when electing the based on the real distance between nodes. The estimated clusterhead. In order to elect the most stable node as clusterhead, value of the distance between nodes is calculated by avoiding frequent roaming, it was computed the stability using measuring the received signal strength taken from periodic the following metrics: beaconing or Hello messages used in some routing - Number of hops: the distance between two nodes A,B protocols. According to this estimated value it can be (DA,B), is the number of hops between them, which can be determined the stability of every node. The most stable obtained from the packets sent from one to other, or hello node is elected as clusterhead. message used in routing protocols. The possibility of obtaining the number of hops between two nodes is evident and simple within all existed routing protocols. III. ENHANCED PERFORMANCE CLUSTERING - Average distance: which is defined as the average of distances between node A and all its neighbours. A. Main Concepts ∑ A,n The main concepts used in EPCA are: a- The Upper Bound: represents the upper bound N is the degree of A of the number of nodes that can simultaneously be AD takes values between 1 and D and it defines the supported by a clusterhead. This value is defined according radius where there exists the great density of nodes. to the remainder of resources of the clusterhead. - Stability: is defined as the difference between two b- The Lower Bound: represents the lower bound measures of AD at t and t-1, it becomes large when the node goes of the number of nodes that belong to a given cluster before far from its neighbors or whenever its neighbors are going in proceeding to the extension or merging mechanisms. other direction than the one taken by the considered node. This c- Multi- hops Cluster: because one hop clusters value is compared with D and a node is considered as most stable are too small for large ad hoc networks, EPCA creates D if it has the less value of ST. d- Identity (ID): is a unique identifier for each STA= ADt - ADt-1 node in the network to avoid any spoofing attacks or perturbation in the election procedure. f- Weight Parameterss: each of the previous parameters e- Weight: each node is elected clusterhead is called partial weight. Since only a subset of these parameters according to its weight which is computed from a set of can be used according to the requirements of the network and the system parameters. The node having the greatest weight is underlying protocol, these factors provide more flexibility and elected as clusterhead. large scale of use to EPCA. Factors are given values between 0 and 1, so that the sum of factors is 1. B. Clusterhead Selection The following parameters define the criteria on n is the number of factors which EPCA rely to elect the clusterhead. g- Global Weight: using all parameters presented above a. Behaviour of neighbors: it measures how much every node in the network computes its global weight using any node in the network is trusted by its neighborhood. It's equation (5). Depending on this weight a given node can be defined as the average of trust values (Ti) received from elected as clusterhead or not. each neighboring node. There were denoted WB , WN , WP ,WM ,WS the partial weights and FB , FN , FP ,FM,FS are the weight factors corresponding respectively to Behaviour node, Nn, Power, Maximum of Nodes, and Stability. The global weight is cluster and aims to reduce the cluster radius from D to D-1, computed as follow: which means that beacons don't reach the boundaries of the cluster, resulting on the roaming of boundaries nodes to other clusters including new cluster creation. Cluster size reduction is executed whenever the merging procedure isn't successfully executed, thus the CH proceed to the The selection procedure of clusterheads is invoked extension of the radius of the cluster from D to D+1. whenever a neighborhood has no clusterhead, or whenever one of the clusterheads isn't able to achieve its IV. SIMULATION RESULTS responsibilities. The invocation of the election procedure doesn't mean that all clusterheads are replaced. Let's The performance of EPCA is evaluated using MANSim assume that a set of nodes desire to create or to maintain a simulator. There were implemented three algorithms (Highest clustering architecture, so they must collaborate to execute Degree Clustering Algorithm (HDCA), Mobility Based the following steps: Clustering Algorithm (MBCA) and Enhanced Performance Search of neighborhood stage: the purpose of this Clustering Algorithm (EPCA-sim). Simulation results are step is to get information about the neighborhood where the presented together with the results obtained in a real scenario election procedure is invoked. Thus nodes desiring to be (EPCA)., in our university campus. The scenarios were generated clusterhead send clusterhead_ready beacons within the using parameters listed in the table below. radius of D hops. Each node when receiving this beacon estimates a trust value and sends it back to the asking node. Parameters
After a discovery period Td, nodes having initiated this 650x650; 150x150 operation can derive from the received responses the Number of Nodes following information: -Degree: this is the number of received responses. Transmission range -Stability: calculated using equation (2) and (3). Max of nodes in a cluster -Trust value: computed using equation (1). Computing weight: after the search of Simulation time neighborhood stage, each node adds to the previous parameters the state of its battery and the maximum number For all the algorithms, the number of clusters is of nodes, then combines them with the corresponding relatively high when the transmission range is small or when the weight factors and computes the global weight using area is big. As shown in Figure 1, the number of clusters created equation (5). This weight is broadcasted within the same by the HDCA is very large. However MBCA and EPCA provide neighborhood. Using the different received weights, nodes less number of clusters because they create two hops clusters choose as clusterhead the node having the maximum covering large area compared to HDCA which creates one hop Whenever the previous steps are successfully achieved, each elected cluster head need to discover each other to elaborate a virtual network to ensure inter-cluster A cluster management procedure is defined to maintain the stability of clustering architecture. These actions mainly manage the increasing and decreasing number of nodes in clusters. As mentioned before a node can't serve for ever as CH, because it has limited resources. Whenever it becomes busy, the CH launches a cluster division procedure to divide the cluster into two small clusters with reasonable number of nodes. Therefore the CH broadcasts Number of nodes
Cluster_Division request to its CMs (Cluster Members). Whenever this request is received, each CM compute its weight and sends it back to the CH, which saves them. Fig. 1. 650x650 m2 area (transmission range of 150 m). Then the CH chooses as a new CH the farthest node with the maximum weight and sends him a grant response. Then the new CH begins sending beacons and creates its own cluster. This operation is executed after the division of the In Figure 2 there are compared EPCA, HDCA and As it can be observed, EPCA manages the increasing MBCA by modifying the cluster size from 2 to 3 hops for number of nodes in the network by creating more clusters. MBCA and EPCA because this parameter is configurable. This is done because the number of nodes in each It can be noticed that MBCA and HDCA keep the same cluster is limited, therefore when there are more nodes in the number of clusters for any number of nodes, to reach the network, the algorithm manage them by creating more clusters. threshold of 400 nodes per cluster. However the EPCA creates The real environment simulations confirm the predicted more clusters to manage the increasing number of nodes, and and simulated results with EPCA. the number of nodes in each cluster remains within the threshold of 20 nodes per cluster, which is reasonable in ad In this paper it was proposed a clustering algorithm called Enhanced Performance Clustering Algorithm. By including the security features through the use of voting mechanism to elect the most trusted node, it was also proposed to use certificate as identifier to avoid spoofing attacks. Another important advantage of this algorithm is that there were created D hops clusters, resulting on a less number of clusters which may also reduce the number of roaming requests, and management difficulties. Number of nodes
Simulation results and especially the results obtained in the real scenario indicated that the model agrees well with the Fig. 2. 150x150 m2 area (transmission range of 150 m and behavior of the algorithm. From the simulations made on the MBCA, it can be observed that for the transmission range of 150 m in
[1]. Agba L., Gagnon F., Kouki A., "Scenarios generator for ad hoc
small areas, the algorithm creates a very small number of networks," International Symposium on Industrial Electronics, Montreal, Canada, clusters. Obviously, this because CHs are mobile nodes, Jul. 2006 which can't support and serve a great number of nodes [2] Chatterjee M., Das S.K., Turgut D., "WCA: A Weighted (150 nodes) simultaneously. Clustering Algorithm for Mobile Ad Hoc Networks," Cluster Computing Journal, vol. 5, no. 2, Apr. 2002, pp. 193-204. From the simulations made on the HDCA, it can [3 Farid Jaddi, Béatrice Paillase. A Cluster Procedure for the Dynamic be noticed the same problems as for the MBCA, because it Source Routing Protocol in Ad hoc Networks.Med-Hoc-Net 2004, The Third doesn't make any assumption on the maximum number of Annual Mediterranean Ad Hoc Networking Workshop. nodes supported by a CH. Thus it creates small number of [4] I.I. ER, and Winston K. G. Seah, Mobility-based D-hop Clustering Algorithm for Mobile Ad hoc Networks. IEEE WCNC, Atlanta, USA, March 2004 clusters to manage the increasing number of nodes. However it creates more clusters for larger areas because the nodes are out of the transmission range of each other. The simulations made on the EPCA for different size of the area shown in Figure 3. Fig. 3. EPCA in different areas, (transmission range of 150m, and cluster size of 2 hops)

Program Guide

Table of Contents

Author Index

Keyword Index

View Full Page

Zoom Out

Source: http://www.gecad.isep.ipp.pt/confenerg/2010/melecon/papers/C2L-C06-3385.PDF