Paper Menu >>
Journal Menu >>
Wireless Sensor Network, 2011, 3, 54-60 doi:10.4236/wsn.2011.32006 Published Online February 2011 (http://www.SciRP.org/journal/wsn) Copyright © 2011 SciRes. WSN A Distributed Weighted Cluster Based Routing Protocol for MANETs Naveen Chauhan, Lalit Kumar Awasthi, Narottam Chand, Vivek Katiyar, Ankit Chugh Department of C omput er Science & Enginee r i ng , National Institute of Technology, Hamirpur, India E-mail: naveen@nitham.ac.in, nar.chand@gmail.com, lalit@nitham.ac.in, vivek.kat@gmail.com, ankit@nitham.ac.in Received January 10, 2011; January 14, 2011; February 17, 2011 Abstract Mobile ad-hoc networks (MANETs) are a form of wireless networks which do not require a base station for providing network connectivity. Many MANETs’ characteristics that distinguish MANETs from other wire- less networks also make routing a challenging task. Cluster based routing is a MANET routing schemes in which various clusters of mobile nodes are formed with each cluster having its own clusterhead which is re- sponsible for routing among clusters. In this paper we propose and implement a distributed weighted clus- tering algorithm for MANETs. This approach is based on combined weight metric that takes into account several system parameters like the node degree, transmission range, energy and mobility of the nodes. We have evaluated the performance of the proposed scheme through simulation in various network situations. Simulation results show that improved distributed weighted clustering algorithm (DWCAIMP) outperforms the original distributed weighted clustering algorithm (DWCA). Keywords: MANETs, Clustering, Routing, Wireless Communication, Distributed Clustering 1. Introduction MANETs are a form of wireless networks which do not require a base station for providing network con nectiv ity. In this networking concept, mobile devices form a tem- porary community without any planned installation, or human intervention. Each node acts as a host and a router at the same time. This means that each node participating in a MANET commits itself to forward data packets from a neighboring node to another until a final destination is reached. Mobile ad-hoc networks have many characteris- tics which distinguish them from other wireless networks. These factors are: no fixed network infrastructure, dy- namic network configuration, node mobility an d frequent node failure, low battery power, etc., which make routing in MANETs quite a challenging task. Various routing protocols have been proposed for MANETs with varying performance in different network con ditions [1]. Cluster based routing is one of the routing schemes for MANETs in which various clusters of mobile nodes are formed with each cluster having its own clusterhead which is responsible for routing between clusters. Clus- tering of nodes saves energy and communication band- width in ad-hoc networks. In this paper we discuss distributed weighted cluster- ing algorithm (DWCA) [2]. This approach is based on combined weight metric that takes into account several system parameters like the ideal node degree, transmis- sion range, energy and mobility of the nodes. Depending on specific applications some of these parameters can be used in the metric to determine the clusterhead . However more clusterheads lead to extra number of hops for a packet when it is to be routed from source to destination . On the other hand we can choose to have minimum number of clusterheads to maximize the resource utiliza- tion. Various parameters and their respective weights can be determined to arrive at an efficient weighted cluster based routing scheme. The rest of the paper is organised as follows. In Sec- tion 2 we give background information of MANETs and cluster based routing schemes. We have described pro- posed algorithm in Section 3. Performance evaluation and comparison bia simulation is presented in Section 4. Finally, Section 5 concludes the paper and talks about N. CHAUHAN ET AL. Copyright © 2011 SciRes. WSN 55 future work. 2. Background and Related Work 2.1. Mobile Ad-Hoc Networks Mobile ad-hoc networks (MANETs) are a form of wire- less networks which do not require a base station for providing network connectivity. It defines simple mecha- nisms which enable mobile devices to form a temporary community without any planned installation, or human intervention. Each node acts as a host and a router at the same time. This means that each node participating in a MANET commits itself to forward data packets from a neighboring node to another until a final destination is reached. In other words, the survival of a MANET relies on the cooperation between its participating members. MANETs have many advantages like low cost, on the fly deployment, etc [3]. 2.2. Routing in MANETs Routing is a very challenging task in mobile ad hoc net- works due to their peculiar characteristics like dynamic mobility, frequent disconnections, low bandwidth, low battery power, etc. Hence traditional routing protocols like RIP [4] cannot be used in mobile ad hoc networks. Various routing protocol schemes have been proposed for mobile ad hoc networks like table driven, source in- itiated on demand etc. and protocols like AODV [1], DSDV [5], DSR [6], ZRP [7], etc. 2.3. Cluster Based Routing One of the major problems of routing schemes in MA- NETs is the reduction of routing and other control in- formation overheads required for an autonomous organ- ization in the face of node mobility. Cluster based routing scheme provides a solution to this problem by organizing the nodes into clusters to reduce communica- tion overhead. Thus a virtual network infrastructure is created which resembles fixed network infrastructure. This is crucial for scalability of media access protocols, routing protocols and the security infrastructure besides the advantage of reducing communication and control overheads due to pre determined paths of communication through clusterheads. One node from each cluster acts as clusterhead. A clusterhead does all the resource alloca- tion to all nodes belonging to its cluster e.g. CBRP [8]. Some of the major issues to be handled by a cluster based routing protocol is the division of a dynamic mo- bile network into clusters and determination of cluster- heads for each cluster in the face of highly dynamic and unstable nature of MANETs [9]. Various cluster based routing schemes have been pro- posed in the literature. Some examples are: 1) Highest Degree Heuristic: The Highest Degree heu- ristic uses the degree of a node as a metric for the selec- tion of clusterheads. The degree of a node is the number of neighbor nodes. The node with maximum degree is chosen as a clusterhead. Any tie is broken by the node identifiers. In this scheme, as the number of ordinary nodes in a cluster is increased, the throughput drops and system performance degrades [10]. 2) Lowest ID Heuristic: The Lowest Identifier algo- rithm chooses the node with the minimum identifier (ID) as a clusterhead. The system performance is better than Highest Degree heuristic in terms of throughput [10]. However, since this heuristic is biased to choose nodes with smaller IDs as clusterheads, those nodes with smaller IDs suffer from the battery drainage, resulting short lifetime span of the system. 3) Distributed Clustering Algorithm: The Distributed Clustering Algorithm is a modified version of the Lowest Identifier algorithm. For each cluster, it chooses a node with locally lowest ID among all the neighbour nodes as a clusterhead. Every node can determine its cluster and transmits only one message during the algorithm [11]. Since it uses nod e ID for the selection of clusterheads, it inherits the drawbacks of the Lowest Identifier heuristic. 4) Weighted Clustering Algorithm (WCA): The WCA is based on the use of a combined weight metric that takes into account several system parameters like the node-degr ee, distances with all its neighbors, node speed and the time spent as a clusterhead. Each node obtains the weight values of all other nodes and information of other clusterheads in the system through rebroadcasting. As a result, the overhead induced by WCA is very high. If a node moves into a region that is not covered by any clusterhead, then the cluster set-up procedure is invoked throughout the whole system. This leads to overheads [10,12]. 5) Distributed Weighted Clustering Algorithm: This algorithm is an enhanced version of WCA to achieve distributed clustering set up and to extend lifetime span of the system. This algorithm differs from WCA in which it localizes configuration and reconfiguration of clusters and poses restriction on the power requirement on the clusterheads. This algorithm provides better per- formance than WCA in terms of the number of reaffilia- tions, end-to-en d throughput, o verheads during the initial clustering set up phase, and the minimum lifespan of nodes [13]. 6) Distributed Score Based Clustering Algorithm: In Distributed Scor e Based Clustering Algorithm (DSBCA) various important parameters for cluster heads selection N. CHAUHAN ET AL. Copyright © 2011 SciRes. WSN 56 are considered. These parameters are battery remaining, number of neighbors, number of members and stability of node. Each node calculates its score by using a for- mula that considers all the above parameters which is used in selection of clusterhead . This algorithm performs better than weighted clustering algorithm (WCA) and distributed weighted clust e ring algorithm (DWCA) [2]. Some other cluster based routing schemes have been given in [14-18]. 3. Proposed Algorithm In this section we present an improved distributed weighted clustering algorithm (DWCAIMP). This algo- rithm can be divided into three phases described as fol- lows. 3.1. Cluster Formation Initially each node is assigned a random ID value. It broadcasts its ID value to its neighbours and builds its neighbourhood table. Each node calculates its own weight based on the following factors: Node connectivity: The number of nodes that can communicate directly with the given node i.e. that are in its transmission range. Battery Power: The power currently left in each node. The energy is consumed by sending and re- ceiving of messages. Mobility: Running average of speed of each node. If mobility is less, the node is more suitable to be- come clusterhead. Distance: Sum of distance of the node from all its neighbours. After finding its own weight, each node broadcasts its weight to its neighbours. If it has maximum weight among its neighbours, it sets the clhead variable to 1, otherwise, the clhead variable is set to 0. The node with maximum weight broadcasts clhead message to other nodes. On receiving a clhead message, a node checks all the nodes from which it receives clhead message. The node with maximum weight becomes the clusterhead of that node. A node sends a unicast message to the clus- terheads. 3.2. Mobility Then we assign a random value between 0 and 1 to each node and a threshold value is taken. If the random value assigned to the node is greater than threshold value, the node becomes mobile, otherwise it remains stationary. When a node moves from one position to other in the random manner, its x and y parameters change. For ex- ample, if a node is to move in east direction, its position will change as 1; 0;xx yy The direction and the duration the node moves in a particular direction is random. On reaching new destina- tion, it joins the nearest clusterhead . 3.3. Cluster Maintenance Cluster maintenance is required when a node moves out of the range of its clusterhead, if a new node is added or the clusterhead fails. First case has been discussed earlier in the mobility handling section. In case a new node is added, it calculates its weight as discussed earlier. How- ever, even if its weight is more than the clusterhead, it does not immediately become the clusterhead and instead chooses the current clu sterhead its clusterhead. Th is is to reduce unnecessary overhead in selection of the cluster- head each time a new node is added. In case the cluster- head fails, the nodes attached to that clusterhead recal- culate their weights and select new clusterhead with the maximum weight. 3.4. The Algorithm The algorithm is described as follows: 3.4.1. Weight Cal c ulation Al gori thm 1) Find connectivity c for each node which is the number of neighbours of each node. 2) Find the energy remaining, e for each node. 3) Compute the mobility M for each node which is the running average of the sp eed until the current time t. 22 11 1 1T vtttt t MXXYY T 1) Compute the sum of di st ances wit h all its nei ghbours, d for each node. 2) Calculate the combined weight W as 123 4 WwcwewMwd 3.4.2. Clusterhead Selection Algorithm 1) Each node finds its neighbours and builds its neigh- bourhood table. 2) Each node calculates its weight by calling the wei- ght calculation algorithm given above. 3) Each node broadcasts its weight to its neighbours. If it has maximum weight among its neighbours, it sets the clhead variable to 1, otherwise, the clhead variable is set to 0. 4) The node with maximum weight broadcasts clhead message to other nodes. N. CHAUHAN ET AL. Copyright © 2011 SciRes. WSN 57 5) On receiving a clhead message a node checks all the nodes from which it receives clhead message. The node with maximum weight becomes the clusterhead of that node. 6) Then we assign a random value between 0 and 1 to each node and a threshold is taken. 7) If the random value assigned to the node is greater than threshold value, then set mobile = 1, otherwise 0. 8) If for a node clhead = 1, then set mobile = 0. 9) If mobile = 1, set value of direction randomly. In- crement or decrement the value of x and y depending upon the direction to show mobility. 10) In case a new node is added, it calculates its weight by calling weight calculation algorithm and re- peats steps 3, 4 and 5. 11) In case clusterhead fails, the algorithm is repeated. The flowchart for the above algorithm is given in Figure 1. 4. Simulation and Performance Analysis In this section we present the performance of the pro- posed algorithm (DWCAIMP) obtained by simulation using Omnet++. The measured performance of the pro- posed algorithm was compared with that of DWCA. The mobile network model assumed in this project consists of random number of mobile nodes with each node having fixed energy and random mobility. The number of nodes can be determined initially. The trans- mission range of each node can also be specified and each node can pass messages to all the nodes in its transmission range. The mobility has been provided by assigning a random value to each node. If the value of random number is greater than some specified value then the node is mobile otherwise it is stationary. A mobile node moves to some random direction for random inter- val and then changes its direction to a new random loca- tion. New nodes can also randomly be added to the net- work. Further each node starts with some energy and its energy decreases each time it passes a message. A node fails if its whole energy has been consumed. A failed node is represented as a black node. The network model is shown in the Figure 2. 4.1. Number of Clusterheads Formed vs Number of Nodes Figure 3 depicts the average number of clusters formed with respect to the total number of nodes in the MANET. As the node density increases, our algorithm produces constantly less clusters in comparison with the original algorithm. As a result, our algorithm gives better per- formance in terms of the number of clusters when the Figure 1. Algorithm flowchart. N. CHAUHAN ET AL. Copyright © 2011 SciRes. WSN 58 Figure 2. Network model. Figure 3. Number of clusterheads vs number of nodes. node density and node mobility in the network are high. 4.2. Number of Control Messages vs Number of Nodes Figure 4 shows the overhead of packets generated per node during the initial clustering set up phase. The over head increased as the number of nodes increases. Each node independently chose one of its neighbors with the highest score to be its cluster head and thus the cluster head selection was performed in a distributed manner with most recently gathered information of current state of the neighbors. 4.3. Number of Reaffiliations vs Number of Nodes Figure 5 describes the number of reaffilations that are done when a node becomes mobile. The nodes become mobile at a random value so this criteria is rather more for self evaluation. The purpose of this factor is that the reaffilations must not exceed the factor which increases network overhead and fails the meaning of clustering process. 4.4. Energy Left vs Number of Nodes Figure 6 shows the total remaining energy in the net- work. Initial energy is the total energy of all the nodes. N. CHAUHAN ET AL. Copyright © 2011 SciRes. WSN 59 Figure 4. Number of control messages vs number of nodes. Figure 5. Number of reaffiliations vs number of nodes. Figure 6. Remaining energy vs number of nodes. As the messages are passed, the energy of a node de- creases. Our protocol improves the original protocol in the sense that it reduces the energy consumption. As the number of nodes increases the number of messages in- creases and thus the energy consumed also increases. 5. Conclusion and Future Work In this paper we have proposed a distributed weighted clustering algorithm by making some modifications and improvements on existing algorith ms discussed in [2,13]. As demonstrated, our algorithm reduces the clusterhead formation and control messages overhead thus improving overall performance and reducing energy utilization. Since energy utilization is the most important criteria in cluster based routing schemes, our protocol provides better results than existing distributed clustering algo- rithm. In the future, some new parameters can be added into weight computation of nodes so as to give even better performance. Also, in this algorithm, the clusterhead selection is limited to single ho p neighbors. This protocol can be extended to includ e multi-hop or k-hop neighb ors. Since, the protocol has been tested on simulation envi- ronment, it can be implemented in a real ad-hoc system to evaluate its performance in real world scenarios. 6. References [1] C. Perkins and S. Das, “Ad hoc On-Demand Distance Vector (AODV) Routing,” Network Working Group, July 2003. [2] S. Adabi, S. Jabbehdari, A. Rahmani and S. Adabi, “A Novel Distributed Clustering Algorithm for Mobile Ad- hoc Networks,” Journal of Computer Science, Vol. 4, No. 2, 2008, pp. 161-166. doi:10.3844/jcssp.2008.161.166 [3] F. Baker “An outsider’s view of MANET draft-baker manet review,” Network Working Group, March 17, 2002. [4] C. Hendrik, “Routing Information Protocol,” RFC 1058, The Internet Society, June 1988. [5] C. E. Perkins and P. Bhagwat, “Highly Dynamic Destina- tion-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,” SIGCOMM’94 Proceedings of the conference on Communications Architectures, Protocols and Applications, Vol. 24, No. 4, 1994, pp. 234-244. [6] D. B. Johnson, D. A. Maltz, Y. C. Hu, “The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR),” Internet Draft, 16 April 2003. [7] Z. J. Haas, M. R. Pearlman and P. Samar, “The Zone Routing Protocol (ZRP) for Ad Hoc Networks,” Internet Draft, July 2002 [8] M. Jiang, J. Li and Y. C. Tay, “Cluster Based Routing Protocol (CBRP),” draft-ietf- manet-cbrp- spec-01.tx t, IETF, Internet draft version 01, July 1999. [9] L. Ramachandran, M. Kapoor, A. Sarkar and A. Ag- gar-wal, “Clustering Algorithms for Wireless Ad Hoc Networks,” In Proceeding: Workshop on Discrete Algo- rithms and Methods for Mobile Computing and Commu- N. CHAUHAN ET AL. Copyright © 2011 SciRes. WSN 60 nications, Boston, 2000, pp. 54-63. [10] M. Chatterjee, S. Das and D. Turgut, “WCA: A Weighted Clustering Algorithm for Mobile Ad Hoc Networks,” Journal of Cluster Computing (Special Issue on Mobile Ad hoc Networks), Vol. 5, 2002, pp.193-204. doi:10. 1023/A:1013941929408 [11] S. Basagni, “Distributed Clustering for Ad Hoc Net- works” In Proceedings: International Symposium on Parallel Architectures, Algorithms, and Networks, 1999, pp. 310-315. [12] M. R. Brust, A. Andronache and S. Rothkugel, “WACA: A Hierarchical Weighted Clustering Algorithm Opti- mized for Mobile Hybrid Networks,” The Third Interna- tional Conference on Wireless and Mobile Communica- tions, Guadeloupe, 4-9 March, 2007. doi:10.1109/ICW MC.2007.93 [13] W. Choi and M. Woo, “A Distributed Weighted Cluster- ing Algorithm for Mobile Ad Hoc Networks,” Proceed- ings of Advanced International Conference on Telecom- munications and International Conference on Internet and Web Applications and Services, 2006. doi:10.1109/ AICT-ICIW.2006.11 [14] M. E. Elhdhili, L. B. Azzouz and F. Kamoun, “Lowest Weight: Reactive Clustering Algorithm for Adhoc Net- works,” Personal Wireless Communications, Vol. 4217, 2006, pp. 135-146. doi:10.1007/11872153_12 [15] Y. Wang, H. R. Chen, X. Y. Yang and D. Y. Zhang, “WACHM: Weight Based Adaptive Clustering for Large Scale Heterogeneous MANET,” International Symposium on Communications and Information Technologies, Syd- ney, 2008, pp. i-liv. [16] X. Niu, Z. Tao, G. Wu, C. Huang and Li Cui, “Hybrid Cluster Routing: An Efficient Routing Protocol for Mo- bile Ad Hoc Networks,” IEEE International Conference on Communications, Vol. 8, 2006, pp. 3554-559. [17] C. R. Lin a nd M. Gerla, “Ad aptive Clustering for Mobile Wireless Networks,” IEEE Journal on Selected Areas in Communication, Vol. 15, No. 7, 1997, pp. 1265-1275. doi: 10.1109/49.6229 10 [18] S. K. Dhurandherl and G. V. Singh, “Power Aware Clus- tering Technique in Wireless Ad Hoc Networks,” Inter- national Symposium on Ad Hoc and Ubiquitous Comput- ing, 2006, pp. 75-80. doi:10.1109/ISAHUC.2006.4290 651 |