Clustering of Nodes in Wireless Sensor Network (WSN): A Survey

Clustering of Nodes in Wireless Sensor Network (WSN): A Survey

Ms. Seema Dahiya

Ph.D Scholar SRM University

Abstract – Wireless sensor network (WSN) is a multi-hop self organization of network system that are formed through combination of large no of sensor nodes .A node is any point with in cluster head (CH) which can be any point in a cluster head. Clustering is an efficient method for solving energy consumption challenges with energy consumption nature of wireless sensors. It is the criteria for determining the overall cost, no. of required cluster head for optimum network usage and longevity for this reason it is widely exploited in wireless sensor network applications. The problem without cluster head was the battery near the sensor node drain faster near to sink

,which leads to decrease in power near the sink, So the paper proposed you to study cluster size, area it can sense, uniform dissipation by reconfiguration the cluster at interval in order to increase its lifetime by reducing energy consumption of WSN. So the paper is all about proposed energy efficient cluster considering nodes and residual electric power by comparing it for saving energy ultimately ,future scope of WSN is that for identifying and transmit data to cluster head, and from cluster head (CH) it transmit data to sink. In this way data is being transmitted from cluster head to sink. In between sensors sensors the communications are not allowed. So we define here regarding using tiny low-cost sensor and radio transceiver, a large number of sensors connected by radio waves can be deployed cheaply .so, we define energy efficient cluster and defining residual electric power by comparing it for saving energy ultimately in this paper . The rest of the paper is as follows .In section (II) we find the cluster size of random deployed WSNs. In section of object on the road in a rainy day. Which function as when receiver transmit line information from the road authority about the state of road including traffic jams, accidents and whether the car transmit information on the road authority regarding speed, distance travelled, and the other one can be moving the base station in wsn.

Index terms Cluster Head, Cluster Size, Nodes, Wireless Sensor Network (wsn), Sensors, Energy.

I. INTRODUCTION

Wireless sensor network (WSN) is formed through the arrangement of large no. of sensor nodes .In this the monitoring area exchange information with each other by using wireless communications. Sensor node collect data of the perception object within its region and transfer the data to the base station after transmission. In WSN when it transmit information then the sensor sense.

(III) We define energy-aware communication protocols. In section (IV) we define cluster algorithm based on communication facility with deterministic cluster size. In section (V) we define application oriented Re-clustering

Dr. Pawan Kumar Singh Asst. Prof., ECE SRM University

and cluster head (CH) Re-election. In section (VI) we define dynamic change method of cluster size in WSN. In section (VII) we concluded and remarks and future scope in WSN. In section (VIII) we acknowledges.

II CLUSTER SIZE OF RANDOMLY DEPLOYED HETROGENEOUS WSNS

Scalability and energy consumption are among the most important challenges for WSN applications. It can be defined by coverage and the connectivity of heterogeneous WSNs.

Coverage- a point is said to be covered if it is within the sensing range of at least one sensor and this coverage would be meaningful only when a sensor is able to transmit its data to the sinks.(2)

Transmission range two sensing range for full coverage is when the data is gather data about an entire region. Therefore we consider partial coverage of a randomly deployed mixture of cluster head (CH) and sensors.

Consist of two types of devices sensors cluster head.

NH cluster head and NS sensors are deployed randomly over a plan region.

Both NH and NS has sensing capability and their sensing range is rS .

Sensors can only transmit their sensing data to a cluster head and cluster heads transmit data to sink. Communication among sensors is not allowed.

Sensor can communicate with a NH if its within a communication range rt of cluster head i.e. NH. The NH is assumed to be connected to the sink.

ON THE BASIS OF COVERAGE CONNECTIVITY

1. Coverage

   Large area D covered N identical sensor scattered and only over the area according to Poisson point process suppose area sensed by each sensor on perfect disk with radius rs and is average no. of sensor

   Case1- probability of point D being covered Pcov = 1-e r2s (1)

   Case2- if the sensing region covered by any sensor was AS, the coverage probability

   would be-Pcov = 1-

   e

   -A

   s

   Case 3- when both sensor (NS) and cluster head (NH) having sensing capability N=NH+NS without connectivity, then coverage probability

   Pcov = 1-e-(NH+NS)r2s /D

2. Connectivity-

If a sensor can reach the NH i.e. cluster head (CH) directly then it is said to be connected . Probability that sensor is within communication range of NH Pcon = 1-e-NHr2t /D Manuscript received November 19, 2007. The associate editor coordinating the review of this letter and approving it for publication was S. Buzzi.

C. Sevgi is with the Department of Computer Technology and Information Systems, Bilkent University, Ankara, Turkey (e-mail: csevgi@bilkent.edu.tr).

A. Kocyigit is with the Department of Information Systems, Middle East Technical University, Ankara, Turkey (e-mail: kocyigit@metu.edu.tr).

Digital Object Identifier 10.1109/LCOMM.2008.071942.

CLUSTER SIZE IN A HETROGENEOUS WSN

We consider that the part of sensing area covered by connected sensor in order to find actual coverage protocols. We defined a cluster size area covered by each cluster head to find the actual coverage.

H cluster

Pcov = 1-e-N S /D

Average no. of sensor connected to a single cluster head be ns, since NS sensor and NH cluster head over region D, ns can be found using-

ns = NS/NH (1-e-NHr2t/D)

In order to find the area covered by NH and ns sensor connected to it for simplicity, consider area covered by single cluster head (CH) over a region D (fig 1)

Since there is ns sensors in the communication range of cluster head, the number of sensor in the square CS, should be:

ns /CS = r2 / D D = CS

rs = point from the center is covered by NH point outside the inner circle can be converted by a sensors

III – ENERGY-AWARE COMMUNICATION PROTOCOL

Large portion of energy aware routing protocols for WSN are clusters based the problem without clustering was that as sensor node drain fast near the sink which in turn induces successive layer of node from sink. The exhaust their battery quickly .so , consider different strategy for limiting cost sensor, more reliable and long lasting sensors ability, energy efficient, data diffusion(6) , quick processing(8), media access control(7) for limiting the energy wastage.

We define two points for energy aware:-

1. Individual sensor node and information it collect is important. Application like Icy road conduction, Surveillance camera, structural health of buildings and bridges etc. here the sensor nodes are fixed though they may be moved in controlled direction remotely.

2. Individual sensor data is not important. Assembled data from a region or cluster is all that is to be delivered. The applications are mainly environmental monitoring for limate change or like, nodes may drift due to bad weather condition.

Fig -2 Frequency distribution of sensory node vs. the remaining battery power.

2 t MAIN GOAL OF WSN

t

* r t /ns CS = D ns/ r2

fig-1

1. Slower decrease of average battery power with time. connected to NH .

2. Lower variation of the distribution of remaining battery level.

Although all the energy aware protocol emphasis on slower decrease of average battery power with time (fig- 2), but in reality both are important.

DIFFERENT APPROACHES FOR ENERGY AWARE

If nodes do not always sends packets to their nearest nodes, but transmit different ratio of packets at different nodes could be made uniform.

If (CH) cluster heat collects packets from all members of the cluster and transmit to sink through immediate CH. Here the nodes near CH are overloaded. Some use LEACH protocols for dynamically change in cluster configuration, so that the load is uniformly shared by nodes over a long time.

Network model & assumptions

This model tells us that when each nodes are equidistance, then consider the distance between 2 nodes bed (fig-3). We assume that nodes can adjust the transmission power to transmit

Defining the constrained optimization problem

This model tell us that when we have N-mode places at equal distance d,node-1 sink node (fig-4).every node generate m packets different nodes of these

m packets are forwarded to different nodes towards sink

IV -CLUSTER ALGORITHM BASED ON COMMUNICATION FACILITY WITH DETERMINISTIC CLUSTER SIZE

With energy constraints nature of WSN the efficient use of battery power is important factor for wsn in order to increase the lifetime of wsn by changing the cluster size algorithm. As nodes exchange their information by wireless communication(9) from there the sensor node collect data and transfer it to base station .so, the energy and lifetime of sensor is maintained .whether if cluster size big(intra clustering collision) or cluster size small(inter cluster collision).

This work is supported by the Natural Science Foundation of China (Grant No. 60673163

Cluster size can be determined by using various algorithms-

1. LEACH(10) (lower energy adaptive clustering hierarchy) in this technique receiver signal strength to form cluster(11)

   .if node becomes cluster head(CH)then it gather data from nodes and transmit data to base station.

2. HEED(12) (hybrid energy efficient distributed protocol) enhanced version of LEACH in which the nodes are reduced in electing cluster head (CH), common nodes determine cluster head (CH).

3. PEGASIS (13) (power-efficient gathering in sensor information system) it uses only 1 nodes of channel to transmit to base station instead of multiple nodes, it avoids cluster formation.

4. WCA(14) (weight cluster algorithm) used for calculating no.of neighbor, transmission power, battery life and mobile rate of nodes.

5. TEEN(16) (Threshold sensitive energy) it is effective sensor network protocol, due to sudden change in the sensing attribute such as weight or condition.

Main aim is that each nodes to calculate CF (communication facility)(18) and CH (cluster head), communication facility intra and inter from lower CF and higher CF depends on two factors- Convenience of node communication with sink node directly.

Convenience of node provide to other node communication with sink

Calculation communication factor-

Each node exchange its CF (communication facility) so, S=n*p with base station and neighboring nodes.

Where n is the number of sensor node and p is optimizing size of the cluster size.

Node Combination Each node knows their Neighboring nodes and send message to nearest node in processing of clustering node with biggest CF (communication facility) and key node of communication nodes as shown in fig-5 , In cluster formation (only key node is active) , as F is key node and A,C,E,F as a Combinational nodes.

Fig-5 key node and combinational node.

V- APPLICATION ORIENTED RE-CLUSTERING AND CLUSTER HEAD RE-ELECTION

CH election(20) to be based on the energy of sensor nodes because a sensor node with high energy is availability might be poor in computation or has even weak wireless connectivity. The contacts are chosen for communication with nodes not in the immediate neighbored as shown in figure -6. Nodes in the immediate neighbored are consider neighbor or simultaneously run a multitude of application, each with its own requirements. None of the CH based on application specific criteria by depends on Bandwidth, reliability, neighborhood, memory and CPU power.

Fig. 6. A scenario for BS connection with CHs for the case of three clusters in CH Re-Election and Re-Clustering

So we define two application oriented on –

1. Re-clustering

2. Re-election

1. CH Re-election:- new CH is elected on permanent basis till it loses its capability for t host further application if CH fails then the new CH exchange resource list from previous CH. When application is being hosted on CH then a new web portal client with different criteria not satisfied by current CH then new application has to wait for current application to be over as shown in figure-7. If new CH has to execute previously request application then it could have hosted it either because we had a better alternative available with resource at least for that application and consequently it was elected previously as CH; it doesnt mean new cannot host if its objective function value remains above say 20% of optimized value of application, CH-reelection avoids repeated CH supplying for each incoming application and hence, exchange of extra information.

   Fig. 7.CH Re-Election

2. Re-clustering:- when a web portal (19) customer wants to execute an application on which cannot be executed on a single node due to extensive computation, we use re-clustering. In this whenever an application is requested by a web

portal client and CH simply looks for nodes that are within 20% regulation of optimized objective function value as shown in figure -8. This result in temporary cluster within the original cluster rides with maximum value of objective function is elected as temporary CH and is advertise on the temporary cluster members and update it resource list temporary CH loss functionality till current application is over.

1. One is hosted on temporary cluster another query is received by primary CH check whether the temporary node execute the application, and it saves the overhead of creating temporary cluster again and again; if none of the node in temporary cluster again and again ,if none of node in temporary cluster deems suitable for new application then group of new node which can satisfy new application is created to make another temporary cluster and new temporary CH.CH re-election & re- clustering is similar by the only different is in group of nodes. Instead of CH re-election, here it is assumed that all application requires a cluster for their efficient execution instead of only CH.

c)

Fig. 8.Re-Clustering.

Algorithm of CH Re-clustering and Re-Clustering algorithm.

Fig. 9. CH Re-Election and Re-Clustering algorithms.

VI- DYNAMIC CHANGE METHOD OF CLUSTERSIZE IN WSN

Dynamic energy method develop on energy efficient routing protocol so evenly distribute the energy-efficient routing protocol .so, evenly distribution the energy loss among all the sensor node in the network

.so that it will not overlap sensor node that would run out of energy.

LEACH(11)(Based on clustering of sensor nodes

.however energy consumption of nodes tend to become uneven in LEACH as in LEACH when a node becomes a cluster head then it gather data from nodes and transmit to base station, cluster formation is changed periodically and cluster head (CH) is changed peiodically.

HEED(24) (extended version of LEACH in which information of residual electric power of nodes. By not

considering the adjacent nodes. Therefore cluster head doe not efficient cover the nodes in HEED (30).

HIT(27) (small transmission range and multihop communication, improve performance dynamics energy-efficient algorithm for adjacent nodes and residual electric power).

Due to SENSING, COMMUNICATION AND DATA PROCESSING

VII CONCLUSION

In this paper we have concluded that WSN is efficient way for finding out the energy conservation and we have finned out different way for finding out area and solving energy distribution.

Future scope of cluster using WSN is that we can detect the moving crowd in rainy

Areas or in that condition where manned vehicle can reach,

By moving the cluster head would be a further research for WSN.

VIII ACKNOWLEDGEMENT

The author would like to thank ciineyt sevgi and alyan kocyigit for giving us their view for determining cluster size, Yuhua Liu,jingju Gao for letting us know about different algo. for deterministic cluster size .

REFRENCE

1. H. Koskinen, On the coverage of a random sensor network in a bounded domain, in Proc. ITC Specialist Seminar on Performance Evaluation of Wireless and Mobile Systems, 2004.

2. H. Zhang and J. C. Hou, Maintaining sensing coverage and connectivity in large sensor nodes, Wireless Ad Hoc and Sensor Networks: An International Journal, vol. 1, pp. 89-124, Jan. 2005.

3. T. Meng and R. Volkan, Distributed network protocols for wireless communications. In the Proceedings of IEEE ISCAS, May 1998.

4. P. Levis, S. Madden, et.al.,, Tiny OS: An operating system for for Wireless Micro-sensor Networks. In Ambient Intelligence (New York, 2004), Springer-Verlag.

5. S. R. Madden, M. J. Franklin, J. M. Hellerstein, W. Hong,Tiny DB: An acquisitional Query Processing System for sensor networks. ACM transactions on Database Systems, Vol. 30, Issue. 1, pp. 122- 173, March 2005.

6. C. Intanagonwiwat, R. Govindan, and D. Estrin,

   Directed diffusion:A scalable robust communication paradigm for sensor networks. In the Proceedings of the Sixth Annual International Conference on Mobile computing and networks (MobiCOM 2000), Boston, Massachusetts, August 2000.

7. D. Braginsky, D. Estrin, Rumor Routing algorithm for sensor networks. In the Proceedings of Wireless Sensor Network Algorithms (WSNA02), pp. 22-30, Atlanta, Georgia, September 28, 2002.

8. W. Ye, and J. Heidemann, Ultra-low duty cycle MAC with scheduled channel polling. In the Proceedings of fourth International conferences on embedded networked sensor systems (SenSys06), pp. 321-334, 2006.

9. Alex Rogers, Esther David, and Nicholas R. Jennings, Self- Organized Routing for Wireless Microsensor Networks. IEEE trans. on SMC – Part A, Vol. 35, No. 3, May 2005

10. W. Heinzelman, A. Chandrakasan, H. Balakrishnan, Energy- efficient communication protocol for wireless microsensor networks, Proceedings of the 33rd International Conference on System Sciences(HICSS '00), January 2000.

11. Heinzelman W, Chandrakasan A, Balakrishnan H. Energy-Efficient communication protocol for wireless microsensor networks. In: Proc. of the 33rd Annual Hawaii Intl Conf. on System Sciences. Maui: IEEE Computer Society, 2000. 30053014.

12. Yuhua Liu, Haiyan Zhu, Kaihua Xu, Wei Teng. An Improved Route Repair Approach of Wireless Sensor Networks. Proceedings of the International Multi-Symposiumson in Computer and Computational Sciences (IMSCCS|06). IEEE Computer Society Order Number P2581 ISBN 0-7695-2581-4, Hangzhou, Zhejiang, China, 20-24 June 2006, PP. 662-665.

13. Younis O,Fahmy S.Distributed Clustering in Ad-hoc Sensor Networks:A Hybrid,Energy-Efficient Approach.In:Proceedings of IEEE INFOCOM,March 2004.

14. S.Lindsey and C.S. Raghavendra. Pegasis: Power efficient gathering in sensor information systems. In Proceedings of the IEEE Aerospace Conference, March 2002.

15. Mainak Chatterjee,Sajal K Das,Damla Turgut. WCA:A weighted clustering algorithm for mobile ad hoc networks[J].Journal of Cluster Computing,Special issue on Mobile Ad hoc Networking,2002, (5):193204.

16. Manjeshwar A, Grawal DP. TEEN: A protocol for enhanced

    efficiency in wireless sensor networks. In: Proc. of the 15th Parallel and Distributed Processing Symp. San Francisco:

    IEEE Computer Society, 2001. 20092015.

17. S. Bandyopadhyay, E.J. Coyle.An energy efficient hierarchical clustering algorithm for wireless sensor networks[A].Proc of IEEE INFOCOM'2003[C].California,US,2003.1713-1723.

18. Yuhua Liu, Jingju Gao, Longquan Zhu,Yugang Zhang " A Clustering Algorithm Based on Communication Facility in Wireless Sensor Network " Accepted to appear in the 2009 International Conference on Communications and Mobile Computing (CMC 2009) IEEE Computer

19. A. Akbar, A. Iqbal, and K. Kim, Binding Multiple Applications on Wireless Sensor Networks, Advances in Grid and Pervasive Computing, pp. 250258, 2006.

20. M. Raza, A. Akbar, and W. Mahmood, Optimal cluster head election for efficient resource discovery mechanism in wireless sensor

21. Y. Yin, J. Shi, Y. Li, and P. Zhang, Cluster head selection using analytical hierarchy process for wireless sensor networks, in 2006 IEEE 17th International Symposium on Personal, Indoor and Mobile Radio Communications, 2006, pp. 15.

22. C. Nam, H. Jeong, and D. Shin, The Adaptive Cluster Head Selection in Wireless Sensor Networks, in IEEE International Workshop on Semantic Computing and Applications. IEEE, 2008, pp. 147 149.

23. I. Gupta, D. Riordan, and S. Sampalli, Cluster-head election using fuzzy logic for wireless sensor networks, in Proceedings of the 3rd Annual Communication Networks and Services Research Conference, 2005.

24. O. Younis and S. Fahmy, HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks, IEEE Transactions on Mobile Computing, pp. 366379, 2004.

25. L. Buttyan´ and P. Schaffer, Panel: Position-based aggregator node election in wireless sensor networks, in Mobile Adhoc and Sensor Systems, 2007. MASS 2007. IEEE Internatonal Conference on. IEEE, 2008, pp. 19.

26. W. R. Heinzelman, A. Chandrakasan and H. Balakrish-nan: Energy- Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences, pp. 1-10, (2000).

27. B. J. Culpepper, L. Dung and M. Moh: Design and Analysis of Hybrid Indirect Transmissions (HIT) for Data Gathering in Wireless Micro

    Sensor Networks, ACM Mobile Computing and Communications Review, vol.3, pp.61-83, (2004).

28. Using Energy Metrics, IEEE Transactions on Parallel and Distributed Systems, vol.13, No.9, pp.924-935, (2002).

29. W. Choi, P. Shah and S. K. Das: A framework for energy-saving data gathering using two-phase clustering in wireless sensor networks, Proceedings of the First Annual International Conference on Mobile and Ubiquit-ous Systems: Networking and Services, pp.203-212, (2004).

30. J. Ushijima, M. Okino, T. Kato and S. Ito: Proposal and Evaluation of a Selecting Method of Landmark Nodes for Message Relaying over High Density Ad hoc Net-work, IEICE technical report 103(202), 93-96, (2003)