Microsoft word - 14. ok_revised-iran [regdone-3-5_374]_an innovative clustering method _13-04_ cr-s-r

International Journal of Computer Science and Telecommunications [Volume 3, Issue 5, May 2012] 80 An Innovative Clustering Method for MANET Based on Cluster Convergence Nima Karimi and Mohammad Shayesteh Abstract—Mobile Ad hoc Networks have special properties In wireless ad hoc network applications, such as and one of the most significant of those properties is nodes outdoor teaching and the communications in the disaster mobility which in part plays a considerable role in network's area (the scenes of a fire, the flood, the earthquake and so different parameters. Many efforts were made to make an on), a number of mobile hosts (MHs) are organized into infrastructure for these networks. In these infrastructures or several disjointed communication groups, which may clusters, a main node called clusterhead has a vital role in move together and overlap with each other. Members keeping the structure, routing and enhancing the efficiency of the network. In this article, an innovative clustering algorithm in within the same group have similar mobility patterns and mobile ad hoc networks is presented which has emphasis on a can directly communicate with each other. Members of a parameter that represents the convergence of the cluster with group communicate with other nodes outside its group predict mobility. In this method, three parameters ,Relative through the group clusterhead, which serves as a gateway speed, Ndm and battery power are used to calculate the primary to other groups. In the group mobility, the clusterhead weight of nodes, then a convergence coefficient can be achieved equips with two network interfaces, one is used for local using the strenght of received signals of neighbors and predicting networks and the other is used for external networks. The the nodes mobility . This value will be multiplied to the primary local networks mean wireless ad hoc networks that are weight of the nodes afterwards, so that the final weight can be used in a group or between overlapped groups. The computed. In simulation, the proposed algorithm has been compared with WCA, MOBIC and the Lowest_ID algorithm. external networks denote the Internet, 2G, GPRS, and The results of simulation reveal that the proposed algorithm achieves the goals. Clustering algorithms can be performed dynamically to adapt to node mobility [2]. MANET is dynamically Index Terms— Clustering Algorithm, Convergence, Cluster- organized into groups called clusters to maintain a head and Mobile Ad Hoc Network relatively stable effective topology [1]. By organizing nodes into clusters, topology information can be aggregated. This is because the number of nodes of a cluster is smaller than the number of nodes of the entire network. Each node only stores fraction of the total MANET is a multi-hop wireless network in which network routing information. Therefore, the number of Amobile nodes can freely move around in the network, routing entries and the exchanges of routing information leave the network and join the network. These mobile between nodes are reduced [3]. Apart from making large hosts communicate with each other without the support of any networks seem smaller, clustering in MANETs also makes preexisting communication infrastructure. Typically, if two dynamic topology appear less dynamic by considering nodes are not within mutual transmission range, they cluster stability when they form [2]. Based on this communicate through intermediate nodes relaying their criterion, all cluster members that move in a similar pattern remain in the same cluster throughout the entire infrastructure is provided by the nodes themselves. communication session. By doing this, the topology Through the nature of MANET, we have many within a cluster is less dynamic. Hence, the corresponding challenges. The most important challenges are stability, network state information is less variable [3]. This routing and scalability. Clustering is the most way to minimizes link breakage and packet loss. improve the stability, routing and scalability. Have Clustering is usually performed in two phases: knowledge about the changes of node's status, can present clustering set-up and clustering maintenance. In the useful information about the stability of it between its clustering set-up phase, clusterheads are chosen among neighbors. This information is effective in clustering the nodes in the network. The roles of clusterheads are approach and in cluster head selection. coordinators of the clustering process and relaying routers in data packet delivery. After electing clusterheads, other nodes affiliate with its neighbor clusterhead to form Nima Karimi is with Islamic Azad University of Bandar-abbas Branch, clusters. Nodes which are not clusterheads are called Iran (e-mail: [email protected]) Mohammad Shayesteh is with Islamic azad university of Banddar-abbas ordinary nodes. After the initial cluster set up, Branch, Iran (e-mail: [email protected]) reaffiliations among clusterheads and ordinary nodes are Journal Homepage: www.ijcst.org Nima Karimi and Mohammad Shayesteh 81 triggered by node movements, resulting reconfiguration of weight is. And the node with highest weight will be clusters. This leads to the second phase, the clustering elected as clusterhead. 4) The Distributed Clustering Algorithm (DCA) [8] and As election of optimal clusterheads is an NP-hard Distributed Mobility Adaptive clustering algorithm problem [4], many heuristic clustering algorithms have (DMAC) [9] are enhanced versions of LID; each node has been proposed [1]-[10]. To avoid excessive computation a unique weight instead of just the node's ID, these in the cluster maintenance, current cluster structure should weights are used for the selection of clusterheads. A node be preserved as much as possible. however, any is chosen to be a clusterhead if its weight is higher than clusterhead should be able to change its role to an any of its neighbor's weight; otherwise, it joins a ordinary node to avoid excessive power drainage. In this neighboring clusterhead. The DCA makes an assumption way, the overall lifespan of the system can be extended. that the network topology does not change during the The goal of this algorithm is to decrease the number of execution of the algorithm. Thus, it is proven to be useful cluster forming, maintain stable clustering structure and for static networks when the nodes either do not move or maximize lifespan of mobile nodes in the system. To move very slowly. The DMAC algorithm, on the other achieve these goals, we propose a new algorithm. In this hand, adapts itself to the network topology changes and algorithm, selection of a clusterhead is done during two therefore can be used for any mobile networks. However, stages. In the first, each node calculates its primary the assignment of weights has not been discussed in the weight by using a new presented weighted function. both algorithms and there are no optimizations on the second, each node predict mobility of its neighborhoods system parameters such as throughput and power control. to calculates its convergence coefficient. convergence 5) MOBIC [7] uses a new mobility metric Instead of coefficient will be multiplied to the primary weight of the static weights; Aggregate Local Mobility (ALM) to elect nodes afterwards, so that the final weight can be clusterhead. ALM is computed as the ratio of received computed. The result of simulation shows that the power levels of successive transmissions (periodic Hello proposed algorithm provides better performance than messages) between a pair of nodes, which means the WCA, MOBIC and Lowest_ID in terms of Clusterhead relative mobility between neighboring nodes. changes, Clusterhead lifetime and the average number of 6) The Weighted Clustering Algorithm (WCA) [4] is orphan clusters. based on the use of a combined weight metric that takes The rest of this paper is organized as follows. In into account several parameters like the node-degree, Section 2, we review several clustering algorithms distances with all its neighbors, node speed and the time proposed previously. Section 3 presents the proposed spent as a clusterhead. Although WCA has proved better algorithm for mobile ad hoc networks. The simulation of performance than all the previous algorithms, it lacks a the proposed algorithm is given in Section 4. Finally, drawback in knowing the weights of all the nodes before Section 5 concludes this paper. starting the clustering process and in draining the clusterheads rapidly. As a result, the overhead induced by II. RELATED WORK WCA is very high. Most of previous algorithms were using only one metric A large number of clustering algorithm have been for clustering purposes. Therefore, the resulted clustering topology fits just in terms of that specific metric [10]. As characteristic of mobile node in mobile ad hoc network to Mobile Ad Hoc networks are generally complex and choose clusterhead. We will give each of them a brief dynamic networks, existing of only one specific metric description as follows: can not reference the whole situation of the network. 1) Highest degree clustering algorithm [5] uses the Those types of clustering topologies which are optimal in degree of a node as a metric for the selection of terms of just one metric are suitable for particular clusterheads. The node with highest degree among its scenarios and have poor performance in other scenario. neighbors will be elected as clusterhead, and its neighbors For these reasons, we use different metrics in our will be cluster members. In this scheme, as the number of algorithm to select the clusterhead. On the other hand, in ordinary nodes in a cluster is increased, the throughput clustering approaches based on weighted functions such drops and system performance degrades. as WCA, efforts are concentrated to select the best node 2) The Lowest-Identifier algorithm (LID) [6] chooses among neighborhood nods by using of available metrics. the node with the minimum identifier (ID) as a In these methods, only those nodes are selected as clusterhead. The system performance is better than clusterhead which have better properties than other Highest-Degree heuristic in terms of throughput [4]. neighborhood nodes such as more rest battery power, However, since this heuristic is biased to choose nodes having more neighborhoods and less average distance with smaller IDs as clusterheads, those nodes with smaller from neighborhoods. but in most of them do not consider IDs suffer from the battery drainage, resulting short to the movement model of the clusterhead toward the lifetime span of the system. other nodes of the cluster. This factor causes the formed 3) Least Movement Clustering Algorithm [7]. In this clusters be unstable and increase the overload of cluster algorithm, each node is assigned a weight according to its reelection process. While in approaches within move mobility. The fastest the node moves, the lowest the sensitive clustering category such as MOBIC, clustering is done International Journal of Computer Science and Telecommunications [Volume 3, Issue 5, May 2012] 82 approaching/escaping to each other. in this approaches, • It must require a lower battery power for interaction the main parameter for clustering is the mobility of nodes and therefore other parameters such as the energy of the To meet the first condition, the amount of battery power battery, the number of neighborhoods and so on, are not is taken into account as one of the factors for calculation of weight. To meet the second condition, we can choose a In the proposed approach we present an optimal method node as a clusterhead, which has less distance with its without appearing previous methods problems by neighbors during neighborhood duration.with using of combining the useful characteristics of those methods in convergence coefficient we can achieve this goal. Higher order to reach to the goal of our algorithm. convergence coefficient means that in the future the average distance between clusterhead and its neighbors is III. THE PROPOSED ALGORITHM smaller than other node. The higher convergence In the algorithm presented in this paper, selection of a coefficient means that the less transmission power the clusterhead is done during the calculation of primary node requires for interaction and communication with its weight and final weight. In the first, each node calculates neighbors and as a result it consumes less battery power. its primary weight by using a new presented weighted The second parameter which causes the clusters be function. second, each node calculates its convergence unstable is the mobility of nodes. In the proposed coefficient with predict mobility of its neighborhood. algorithm for creating stable clusters, in the first, the Then based on the primary weight final weight is previous mobility of nodes intended, which is accessible calculated. Finlay the node with higher weight selected as by calculating parameter Relative speed. In the second, A. Setup Procedure convergence coefficient of nodes. First, we allocate IDs for the nodes. In the proposed The used parameters in weighted function for giving a algorithm, each node Ni (member or clusterhead) is primary weight to nodes (weightp) include: identified by a state such as: Ni (idnode , idCH , flag , - Battery remaining (Br): every node which wants to be Weightp), it also has to maintain a ‘node_table' wherein the clusterhead should have threshold power Bd. A the information of the local members is stored. However, clusterhead consumes more energy in a cluster comparing the clusterheads maintain another clusterhead information with an ordinary node. In addition, we prefer to choose a table ‘CH_table' wherein the information about the other more powerful node to play its role as a clusterhead clusterheads and member node is stored. because such a node looses its energy later results in the In complex networks, the nodes must coordinate late starting of new clusterhead selection process and between each other to update their tables. The Hello therefore increases the stability of clusters. Equation (1) messages are used to complete this role. A Hello contains the state of the node; it is periodically exchanged either shows that the each node how to calculate battery between clusterheads or between each clusterhead and its remaining of itself. members in order to update the ‘CH_tables' and the ‘node_tables' respectively. We define a flag for every node which determine their - Number of nodes moving towards a node (N role. The value of flag is 3 if the node is the clusterhead, is 1 if the node is an ordinary node, is 2 if the node is a - Relative speed (S): The relative mobility of the node gateway and is zero if the node has an undetermined with its neighbors, which means how long node has spent their time beside the node. A lower relative speed simply A. Weighted Function means that the neighbors of a certain node has spent a longer time in its transmission range, we conclude that the To enhance stability of clusters we must find out mentioned node has a more stable situation. The relative problems that cause stability to be decreased and as a speed is calculated by Eq. (2). result cause a cluster to disappear. If we know and solve these problems, we can enhance stability of the clusters as much as possible. The first parameter which causes clusters to disappear {n is the number of node's neighbors} is Excessive battery consumption at a clusterhead. In MANETs, the nodes not only bear the responsibility of Where SL is the signal strength of last packet reception, sending and receiving information, but also carry out SF is the signal strength of first packet reception, TL is routing for packages. As a result they consume a high rate the time of the last packet reception and TF is the time of the first packet reception. As a result a clusterhead must have the following Each node uses the above mentioned three parameters to calculate its primary weight (weightp). The Eq. (3) • It must have a high existence of battery power. shows how the nodes calculate weightp. Nima Karimi and Mohammad Shayesteh 83   
  N   (3) Table 1: Messages used in the algorithm In the Eq. (3), ci(s) are the weight factors of To update the tables of node , idCH , flag, B. The calculation of final Weight Best(idnode , idCH ) Offer the node to be After Each node calculate its primary weight, to get To affiliate a cluster final weight should calculate the convergence coefficient. The node accepts the For calculate the convergence coefficient we should first predict the neighbors mobility. We predict neighbors The CH accepts a mobility based on last two received signal power. For predicting the next signal power received by nodes, we The CH rejects a use linear extrapolation method. In this method in order to obtain the signal power at the time t+1, we use the powers The CH adds the node as of signal at the times t and t-1. Eq. (4) shows how to calculate the power of a signal received at the time t+1: The CH accepts the presence of a new CH in !"  P! +$%&'(%&)( * +P The CH notifies a CH After predicting the power of the received signal of all The node leaves the neighbors at the time t+1, we can calculate the convergence coefficient of this node by the Eq. (5): ignore any Join_Request received even if they are in the /   ∑ transmission range of the new entry node. This allows simplifying the management of the clusters. Each node use Eq. (6), for calculating the final weight In the case where the node receives a response according to convergence coefficient: (CH_Wel or CH_NWel ), it does not take immediately WeightF = C*weightp (6) any decision, this allows the node to be certain that it has received all the responses from all the neighboring clusterheads. The CH_Wel and CH_NWel messages do Neighbourhood selected as clusterhead. not indicate that the clusterhead has added the node to its In this way, we can select suitable clusterhead for all table; they just signify that the clusterhead is waiting for a nodes not only by considering the suitable condition of Join_Accept in order to add the node to its table. When clusterhead in the network but also with regarding to the the node receives multiple CH_Wels, Based on the node status comparing with the clusterhead. This leads to primary weight of clusterheads calculate the final weight better local selection of the clusterhead resulting in more of them and select the node with highest final weight as stable clusters creation preventing future cluster reform the clusterhead. After that, it sends a Join_Accept to the chosen clusterhead and waits for CH_ACK from this CH. Table 1 show the messages with its description used in The CH_ACK has to contain a confirmation that the idnode proposed algorithm. has been added to the CH_table. Thus the node can fully-define its state. The reason that we use four ways to C. New Arrival Nodes Mechanism confirm the joining procedure is to prevent other clusterheads that they can serve the entry node to add this Once a wireless node is activated, its idCH field is node to their tables and cause conflicts. equal to NULL since it does not belong to any cluster. In the case where the node was just receiving The node continuously monitors the channel until it CH_NWels, it considers these responses as rejection figures out that there is some activity in its messages from the clusterheads. This may occur when the neighbourhood. This is due to the ability to receive the clusterheads are saturated and decide to reject the signals from other present nodes in the network. The node adhesion of new nodes. When the number of attempts still has no stable state, thus its state is not full identified. reaches a certain value, the node prefers not to stay In this case, it broadcasts a Join_Request in order to join isolated, thus it declares itself as clusterhead. the most powerful clusterhead. Thus, it waits either for a CH_Wel or for a CH_NWel. D. Clusterhead Nodes Mechanism When the entry node does receive neither CH_Wel nor CH_NWel . If this persists for certain number of attempts, A clusterhead has an idnode field is equal to idCH field. the node declares itself as an isolated node, and restarts by As a clusterhead, the node calculates periodically its broadcasting a new Join_Request after a period of time. weight, thus it sends periodically Hello messages to its We note that just the clusterheads may response by a members and to the neighboring clusterheads in order to CH_Wel or CH_NWel; the ordinary members have to update the node_tables and CH_tables respectively. The International Journal of Computer Science and Telecommunications [Volume 3, Issue 5, May 2012] 84 clusterhead must monitor the channel for Leave, Hello current clusterheads weight, Member node get this and Join_Request messages. in the proposed algorithm decision by calculating the final weight of the new this operation is limited to clusterhead to allow easier clusterhead. it sends a Join_Request to the clusterhead management on clusters. which is Hello's source and continues as a member of the When the clusterhead receives a Join_Request current clusterhead until the reception of CH_ACK. In (idCH=NULL) from a new arrival node or a Join_Request this case, the node can send a Leave_Request to the last (full state) from a node which belongs to another cluster, clusterhead. This method allows us to minimize the the clusterhead can accept or reject the request basing on number of the formed clusters in the network. its capacities. This procedure gives more flexibility to the When the node member receives a CH_info message as members by allowing them to leave a weak clusterhead a result of the re-election procedure, thus it realizes that it and join another one which seems stronger than the is going to become the new clusterhead in the cluster. current clusterhead. It may not be possible for all the When a node member does not receive any message from clusters to reach the cluster size λ. We have tried to its clusterhead, it considers that the clusterhead has gone reduce the clusters formed by merging the clusters that brusquely down; in this case, the nodes have no choice have not attained their cluster size limit. However, in and must restart the clustering setup procedure. order not to rapidly drain the clusterhead's power by accepting a lot of new nodes, we define thresholds which IV. SIMULATION AND RESULTS allow the clusterhead to control the number of nodes inside its cluster. In this paper we use GloMoSim tool for simulation. The The re-election is not periodically invoked; it is simulation environment is a Mobile Ad Hoc Network performed just in case of a higher received weight, it consists of 20 to 100 nodes in an 800*800 area. We allows minimizing the generated overhead encountered in assume that each node will be activated by a 2.4GHz radio previous works As we explained above. the re-election frequency. The simulated area is considered as a two may not result a new clusterhead, it depends on the dimensional square and nodes move freely throughout the stability of the new node for playing the clusterhead's area. The movement of nodes has been simulated according to Random Waypoint model. In the proposed algorithm clusterhead will check In order to evaluate the performance and efficiency of regularly incoming messages from neighboring nodes. if the proposed algorithm, a set of simulations were operated clusterhead received a message that contains higher and duration of them was 1200 seconds. We select a set of primary weight from his weight, then it check the relative parameters to show the efficiency of our algorithm. Our mobility with the desired node, if its relative mobility to proposed algorithm was compared with WCA, MOBIC this node were in the first group and all of the cluster and Lowest_ID method which is the most famous members exist in neighboring of this node, assign clustering algorithms. These parameters include: clusterhead role to the desired node. The node does it with save the ID of this node in its CH_ID field. A. Clusterhead changes Then send a CH_info message to new clusterhead to Fig. 1, Fig. 2 and Fig. 3 show that the clusterhead declare that this node as a new clusterhead selected. Then changes in the proposed algorithm less than the WCA, copy their tables in to new clusterhead and send a MOBIC and Lowest_ID algorithms that leads to long life CH_change message to neighboring nodes to defines a of clusters so will have more stable clusters. The reason is new clusterhead. in This new approach selecting the new that the proposed algorithm selected such as the node as clusterhead is based on stability of it in the cluster. In this the clusterhead that have more Presence and battery case where a new clusterhead is elected, the procedure is power therefore more time is left as clusterhead. Fig. 1 soft and flexible in order not perturb the clusters while to shows the Average number of clusterhead changes against copying the databases from the old clusterhead to the new the speed of node, Fig. 2 shows the average number of clusterhead changes against the transmission range and Fig. 3 shows the count of clusterhead changes against the E. Member Nodes Mechanism number of nodes. After joining a cluster, the node declares itself as a member of this cluster. Hence, it calculates periodically B. Clusterhead lifetime its weight and sends periodically Hello messages to its Fig. 4 and Fig. 5 show that the clusterhead lifetime in clusterhead. As a member, this node should just handle the proposed algorithm higher than the WCA, MOBIC and the Hello, the CH_change and the CH_info messages. Lowest_ID algorithms. Fig. 4 shows the average lifetime This allows optimizing the resources (bandwidth, battery, of clusterhead against the speed of node and Fig. 5 shows etc) and minimizing the job of the nodes. When the node receives a Hello from its clusterhead, transmission range. the node has to update its node_table. When the node receives Hellos from the neighboring clusterheads, the C. The average number of clusters node has the possibility to migrate to another clusterhead if there is a Hello which has a higher weight than the As you can see in Fig. 6, the number of formed clusters is increased by increasing the number of nodes. Fig. 6 Nima Karimi and Mohammad Shayesteh 85 shows the average number of clusters against the number Fig. 4. Average lifetime of clusterhead vs. the speed of node Fig. 1. the Average number of clusterhead changes vs the speed of node 40 50 60 70 80 90 100110120130140150160 Transmission Range 40 50 60 70 80 90 100 110 120 130 140 150 160 Fig. 5. Average lifetime of clusterhead vs. the transmission range Transmission Range Fig. 2. the Average number of clusterhead changes vs. the transmission Our Algorithm,λ=20 Our Algorithm,λ=15 Our Algorithm,λ=20 Our Algorithm,λ=15 Fig. 6. Average number of clusters vs. the number of node Fig. 3. Count of clusterhead changes vs. the number of nodes D. The average number of orphan clusters As you can see in figure 7, the number of single node clusters or orphan clusters in our algorithm is less than International Journal of Computer Science and Telecommunications [Volume 3, Issue 5, May 2012] 86 WCA, MOBIC and the Lowest_ID algorithms. The reason C. E. Perkins, editor. Ad Hoc Networking. Addison-Wesley, is that in our algorithm, the clusterheads are selected from central safe area. Chatterjee, M., Das, S., and Turgut, D., "WCA: a weighted clustering algorithm for mobile ad hoc networks," Journal of Cluster Computing (Special Issue on Mobile Ad hoc Networks), 5, 2002, pp. 193-204. Gerla M., Tsai J. T. C., "Multicluster, Mobile, Multimedia Radio Network," ACM/Baltzer Wireless Networks Journal 95, vol. 1, Oct. 1995, pp. 255-265. Baker D.J., Ephremides A., "A distributed algorithm for organizing mobile radio telecommunication networks," Proceedings of the 2nd International Conference on Distributed Computer Systems, Apr. 1981, pp. 476-483. Basu P., Khan N., Little T. D. C. A mobility based metric for clustering in mobile Ad hoc networks[A]. proceedings of IEEE ICDCS 2001 Workshop on Wireless Networks and Mobile computing[C], phoenix, A Z, April 2001:413-418. Basagni S., "Distributed clustering for ad hoc networks," Architectures, Algorithms and Networks, Jun. 1999, pp. 310- 315. Basagni S., "Distributed and mobility-adaptive clustering for multimedia support in multi-hop wireless networks," Proceedings of Vehicular Technology Conference, VTC, vol. Fig. 7. Number of single node clusters or orphan clusters 2, fall 1999, pp. 889-893. Hui Cheng, Jiannong Cao, Xingwei Wang, Sajal K. Das, Stability-based Multi-objective Clustering in Mobile Ad Hoc Networks, The Third International Conference on Quality of Service in Heterogeneous Wired/Wireless Networks, August 7–9, 2006, Waterloo,Ontario, Canada 2006 ACM. In this paper, we have presented a new clustering algorithm in Mobile Ad Hoc Network. In this algorithm selection of a clusterhead is done during the weighted function. In the first, each node calculates its primary weight by using a new presented weighted function. In the second, each node calculates its convergence coefficient with predict neighborhoods mobility. A number of parameters of nodes were taken into consideration for assigning weight to a node. The proposed algorithm chooses the cluster-heads based on the information of neighbor nodes, and maintains clusters locally. Also it has a feature to control battery power consumption by switching the role of a node from a cluster-head to an ordinary node. We assumed a predefined threshold for the number of nodes to be created by a clusterhead, so that it does not degrade the MAC function and to improve the load balancing. We conducted simulation that shows the performance of the proposed enhancement clustering in terms of the average number of clusters formation, stability of clusters, and lifetime of a clusterhead. We also compared our results with the WCA, MOBIC and Lowest_ID. The simulation results show that our enhancement clustering algorithms C. R. Lin and M. Gerla. Adaptive clustering for mobile wireless networks. IEEE Journal on Selected Areas in Communications, 15(7):1265-1275, Sept. 1997. A. B. McDonald and T. F. Znati. A mobility-based framework for adaptive clustering in wireless ad hoc networks. IEEE Journal on Selected Areas in Communications, 17(8):1466-1486, Aug. 1999.

Source: http://www.ijcst.org/Volume3/Issue5/p14_3_5.pdf