Keywords
|
| wirelesssensor network, data aggregation,clustering algorithm |
INTRODUCTION
|
| In recent years, wireless sensor networks have gained worldwide attention due to the advances it has made in the field of wireless communication, information technologies and electronics. Due to energy constraints, a sensor node can communicate with other nodes that are within a small distance.Inorder to enable communication between sensors out of each other’s communication range, sensors form a multi-hop communication network. |
| Clustering sensor nodes is an effective technique for achieving multi-hop communication. Clustering facilitates distribution of control over the network. Each cluster has a cluster head (CH) which acts as a coordinator and also some member nodes. The CH gathers the data sent by its respective member nodes and transmit it to Base Station (BS) through other cluster heads. Because CHs often transmit data over longer distances, they lose more energy compared to the member nodes. So the network is re-clustered periodically in order to select energy-abundant nodes to serve as CHs,thus distributing the load uniformly on all the nodes. Besides achieving energy efficiency, clustering reduces network contention and packet collisions, resulting in better network throughput under high load. |
| In this paper we are going to discuss about various clustering algorithms used in WSN.The rest of this paper is organized in the following manner: Section II will introduce the main advantages and objectives of clustering. Section III will provide an overview of proposed algorithms and their limitations. We will conclude this paper with Section IV. |
ADVANTAGES AND OBJECTIVES
|
| Clustering protocols have a wide variety of advantages over flat routing protocol. This section summarizes its advantages as well as its objectives and is as follows: |
| More scalability: In clustering routing scheme, sensor nodes are grouped to form different clusters.The cluster heads are responsible for data aggregation, information dissemination and network management and the member nodes for events sensing and information collecting in their surroundings. Clustering topology can localize the route set up within the cluster and thus reduce the size of the routing table stored at the individual sensor node. Compared with a flat topology, this kind of network topology is easier to manage, and more scalable to respond to events in the environment. |
| Data Aggregation: Nodes in a close area usually share same data. In cluster algorithms, CH aggregates the data and transmits it to the BS. Aggregation consists of suppressing redundancy in different data messages. So data aggregation is a way to reduce energy consumption. |
| Maximizing of the Network Lifetime:WSNs are composed of large number of power constrained sensor nodes and this nodes die when it run out of energy. Utilizing clustering algorithm reduces the energy consumption and thus maximizes the network life cycle. |
A.Hierarchical schemes
|
1)LEACH
|
| Low-Energy Adaptive Clustering Hierarchy[11] is one of the most popular clustering approaches for Wasn’t is an application specific architecture. In LEACH, the nodes organize themselves into local clusters, with one node acting as the cluster head and others as member nodes. All member nodes transmit their data to their respective CH, and on receiving data from all member nodes the cluster head performs signal processing functions on the data (e.g., data aggregation),and transmits data to the remote BS. Therefore, being a CH node is much more energy intensive than being a member node[10]. |
| The main objective of leach is to select sensor nodes as cluster heads by rotation. In this way, the energy load of being a cluster head is evenly distributed among the nodes. The operation of LEACH is divided into rounds. Each round begins with a set-up phase followed by steady state phase. In the set-up phase the clusters are organized, while in the steadystate phase data is delivered to the BS. |
| Initially CH is selected, based on the signal energy of nodes. The nodes with the higher energy are selected as CH. Each sensor nodes generates a random number between 0 and 1 and compares it to a pre-defined threshold T(n).If random<T(n),the sensor node becomes CH in that round, otherwise it is member node. |
 |
| Where P is the desired percentage of CHs,r is the current round, and G is the set of nodes that have not been elected as CHs in the last 1/P rounds. |
| LEACH is a completely distributed approach and requires no global information of network. LEACH can guarantee not only the equal probability of each node as CH, but also relatively balanced energy consumption of the network nodes. However, there exist a few disadvantages in LEACH as follows:1)LEACH assumes a homogenous distribution of sensor nodes in given scenario, which is not very realistic[12].2)Some clusters will be assigned with more number of nodes, this could makes CH nodes run out of energy quickly.3)CH has the extra burden of performing long range transmission to the distant BS,which results in too much energy consumption. |
| Various modifications have been made to the LEACH protocol, which form LEACH family, such as TL-LEACH [13], E-LEACH [14], M-LEACH [15], LEACH-C [16], V-LEACH [17], etc. |
2) HEED
|
| Hybrid Energy-Efficient Distributed clustering (HEED) [7], introduced by Younis and Fahmy, is a multi-hop WSN clustering algorithm which overcomes the shortcomings of unevenly distributed CH as enjoyed by the LEACH algorithm. HEED algorithm is distinguished from LEACH in CH selection mechanism. Residual energy of a node is introduced as a parameter in the CH election. In HEED, elected CHs have relatively high average residual energy compared to member nodes. |
| In initialization phase, nodes send the messages to compete with the initialized probability of CHprob. When the election of cluster head is completed, other nodes join into clusters by means of the information gathered in competing phase. Here, CHprobis described as , CHprob= max(Cprob+ Eresident/Emax ,pmin) where Cproband pmin are the whole network parameters affecting the convergence speed of the algorithm, Eresident/Emax is the ratio of the node residual energy and initial energy. |
| In HEED, CHs send the aggregated data to the BS in a multi-hop fashion rather than single-hop fashion of LEACH. This promotes more energy conservation and scalability in contrast with the single-hop fashion in the LEACH protocol. Even so, there are some problems in HEED algorithm as follows:1)The competition of cluster head may exclude some nodes from joining into any clusters[8].2)HEED needs several iterations to form clusters which include a lot of packet broadcast.3) The CH nodes closer to the BS consume much more energy due to the relaying network traffic near the BS.Hence the CH nodes closer to the BS may quickly exhaust battery. |
3) EECS
|
| In Energy Efficient Clustering Scheme[9] ,the CH candidates compete each other to become CH for a given round. This competition involves the broadcasting of residual energy to their neighboring candidates and if a given node does not find a node with more residual energy, it becomes a CH.Cluster formation in EECS is different from that of LEACH.In LEACH clusters are formed based on the minimum distance from nodes to their corresponding CH,whereas in EECS dynamic sizing of clusters is done based on the distance from BS. Clustering performed in this way, addresses the problem that clusters with a larger distance to the BS require more energy for transmission than those with a shorter distance, and bring about low message overheads and uniform distribution of CHs compared to LEACH. |
| However, there exist a few disadvantages in EECS as follows:1)Like LEACH it performs single-hop communication, hence CH have the extra burden of performing long range transmission to the distant BS,which results in too much energy consumption.2) EECS requires more global knowledge about the distances between the CHs and the BS, and the task of global data aggregation adds overheads to all sensor nodes. |
B. Heuristic Algorithms
|
1) LCA
|
| Linked Cluster Algorithm, was one of the very first clustering algorithms developed. It was initially developed for wired sensors, but later implemented in wireless sensor networks. This algorithm avoids communication collisions among nodes and uses TDMA frames for inter-node communication, with each frame having a slot for each node in the network for communication. In the Linked Cluster Algorithm [3], a node becomes the CH if it has the highest identity among all nodes within one hop of itself or among all nodes within one hop of one of its neighbors. In LCA, each node is assigned a unique ID number and has two ways of becoming a cluster head. The first way is, if the node has the highest ID number in the set including all neighbor nodes and the node itself. The second way, assuming none of its neighbors are cluster heads, then it becomes a cluster head. |
| Basically, the LCA approach was designed to be used in the networks with less than 100 nodes. In such small networks, the delay between the node transmissions is minor and may be accepted. It cannot be used in networks with larger number of nodes. . Another limitation of LCA is its relatively high control message overhead, because the nodes have to broadcast their nodes-heads list. Further, LCA does not consider the node mobility, adaptive transmission range, and power efficiency issues. |
2)LCA2
|
| LCA2 was proposed by P. Tsigas to eliminate the election of an unnecessary number of clusterheads, as in LCA[4][5]. In LCA2, they introduce the concept of a node being covered and non-covered. A node is considered covered if one of its neighbors is a CH. CHs are elected starting with the node having the lowest ID among non-covered neighbors,i.e., in LCA2 the node with the lowest id among all nodes that are neither a CH nor are within 1-hop of the already chosen CHs is elected as CH. The disadvantage of both of these linked cluster mechanisms is that the cluster head load is not uniformly distributed among all the nodes. |
3) HCN
|
| Highest-Connectivity Cluster Algorithm [1] is similar to LCA In this scheme, each node broadcast their number of neighboring nodes to the surrounding nodes..The result is that instead of looking at the ID number, the connectivity(number of links to its 1-hop neighbors) of a node is considered. The node with the highest connectivity (connected to the most number of nodes) is elected as CH, but in the case of a tie, the node with the lowest ID prevails. HCN incurs a higher message overhead because more information about connectivity is exchanged [2]. Thus, the throughput is low in HCN approach. |
C.Weighted Scheme
|
1) WCA
|
| The election of CH in Weighted clustering Algorithm[6] is based on node degree, node speed, distances with respect to a node’s neighbors, battery life, and the time spent as a cluster head. Each node broadcasts its weight value to all other nodes and a node is chosen to be cluster head if its weight is the highest among its neighbors; otherwise, it joins to a neighboring cluster. In order to save energy, size of the cluster is limited. This clustering algorithm tries to find a longlasting architecture during the first CH election. When a sensor loses the connection with any CH, the election procedure is invoked to find a new clustering topology. This is an important feature in power saving, as the re-election procedure, which consumes energy, occurs less frequently. The main drawback of WCA is that it needs to obtain the weight of the node and require each node to save all the information of nodes before initializing network, so excessive amounts of computing and communications may cause excessive consumption in clustering directly. In the process of aggregating and forwarding, the overhead may also give rise to excessive energy consumption and rapid death of cluster head node, incurring instability in the network topology. |
CONCLUSION
|
| In recent years, wireless sensor networks have gained worldwide attention due to the advances it made in many areas such as object tracking, intrusion detection, environmental monitoring and traffic control and so on. But the energy of network nodes is often limited, so the efficient use of energy is a must in WSN.Clustering nodes into groups not only saves energy but also reduces network contention when nodes communicate to their respective cluster-heads. |
| This paper summarizes only some of the cluster-based routing protocols used in WSN,since it is a vast area under research. This paper covers both the advantages and disadvantages of each protocol. Future perspectives of this work are focused towards modifying one of the above routing protocols such that the modified protocol could minimize more energy consumption for the entire system. |
| |
References
|
- P. Tsigas, “Project on Moblie Ad Hoc Networking and Clustering for the Course EDA390 Computer Communcation and DistributedSystems,”Manual for University Course.
- M. Gerla and J. T. C. Tsai. “Multi-cluster, Mobile, Multimedia Radio Network”, ACM/Baltzer Journal ofWireless Networks, vol. 1, no. 3, Sept. 1995, pp. 255-265.
- D. J. Baker and A. Epheremides, “The Architectural Organization of a Moblie Radio Network via a Distributed Algorithm,” IEEE Transactions on Communications, vol. Com-29, no. 11, November 1981.
- P. Tsigas, “Project on Moblie Ad Hoc Networking and Clustering for the Course EDA390 Computer Communcation and Distributed Systems,” Manual for University Course.
- Amis, R. Prakash, T. Vuong, and D. Huynh, “Max-Min D-Cluster Formation in Wireless Ad Hoc Networks,” IEEE INFOCOM, March 2000
- M. Chatterjee, S. K. Das, and D. Turgut, “WCA: A weighted clustering algorithms for mobile ad hoc networks,” Cluster Comput., vol. 5, no. 2,pp. 193–204, 2002.
- O. Younis and S. Fahmy, “HEED: A hybrid, energy-efficient, distributedclustering approach for ad hoc sensor networks,” IEEE Trans. MobileComput., vol. 3, no. 4, pp. 366–379, Dec. 2004.
- C. H. Lin and M. J. Tsai, “A comment on HEED: A hybrid, energyefficient,distributed clustering approach for ad hoc sensor networks,”IEEETrans. Mobile Comput., vol. 5, no. 10, pp. 1471–1472, Oct. 2006.
- Ye, M.; Li, C.; Chen, G.; Wu, J.”An energy efficient clustering scheme in wireless sensor networks”.Ad Hoc Sens. Wirel.Netw.2006, 3, 99–119.
- W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, “Energyefficient communication protocol for wireless micro sensor networks,”inProc.33rd Annu. Hawaii Int. Conf. Syst. Sci., Jan. 2000, pp. 1–10.
- W.B.Heinzelman,A.P.Chandrakasan, and H. Balakrishnan“An Application-Specific Protocol Architecture for WirelessMicrosensorNetworks”inIEEEtranscations on wireless communications,vol.1,no.4.oct 2002.
- MortazaFahimiKhatonAbad , Mohammad Ali JabraeilJamali“Modify LEACH Algorithm for Wireless Sensor Network”,in IJCSI Int. Conf ., Vol. 8, Issue 5, No 1, September 2011.
- Loscri, V.; Morabito, G.; Marano, S.A Two-Level Hierarchy for Low-Energy Adaptive Clustering Hierarchy. In Proceedings of the 2nd IEEE Semiannual Vehicular Technology Conference, Dallas, TX, USA, 25–28 September 2005; pp. 1809–1813.
- Fan, X.; Song, Y. Improvement on LEACH Protocol of Wireless Sensor Network.In Proceedings of International Conference on Sensor Technologies and Applications, Valencia, Spain, 14–20 October 2007, pp. 260–264.
- Mo Xiaoyan. Study and Design on Cluster Routing Protocols of Wireless Sensor Networks. Ph.D. Dissertation.Zhejiang University, Hangzhou, China, 2006
- Heinzelman, W.B.; Chandrakasan, A.P.; Balakrishnan, H.An application-specific protocol architecture for wireless microsensor networks. IEEE Trans. Wirel. Commun.2002, 1, 660–670.
- Yassein, M.B.; Al-zou’bi, A.; Khamayseh, Y.; Mardini, W”.Improvement on LEACH protocol of wireless sensor network (VLEACH).Int. J. Digit. Content Technol. Appl. 2009, 3, 132–136.
|
Menu