Wireless Sensor Network
Vol.5 No.2(2013), Article ID:27993,7 pages DOI:10.4236/wsn.2013.52004
Probabilistic Energy Value for Clustering in Wireless Sensors Networks
1Laboratory LETI, National School of Engineers of Sfax, University of Sfax, Sfax, Tunisia
2National Conservatory of Arts and Crafts, Center for studies in Computer Sciences and Communication, Paris, France
3ISSIG Higher Institute of Industrial Systems Gabes, University of Gabes, Gabes, Tunisia
Email: salim.el.khediri@gmail.com
Received January 9, 2013; revised February 9, 2013; accepted February 18, 2013
Keywords: Wireless Sensor Network; Clustering; Network Lifetime; Energy Thresh; Optimization
ABSTRACT
Wireless sensors networks consist of a number of sensors nodes connected through a wireless network that collect data to be treated locally or relayed to the sink node using multi-hop wireless transmission. Several solutions were proposed to minimize the amount of information flowing within the network. Clustering algorithms is one solution and mechanism that enables the creation of sensor’s clusters; each sensor is dominated by elected routers. In order to limit energy consumption, the clustering around the sensor is established: sensors linked to the router transmit relayed data thereafter outward. The number of messages sent and the transmission range are thus reduced. This article tackles this issue by unveiling proposed techniques in the same line of researches and proposing a clustering mechanism based on the amount of energy remaining in the sensors. The simulation results show that proposed method can achieve higher network lifetime by comparison to original LEACH.
1. Introduction
Wireless sensors networks may consist of a variable number even thousands of sensors nodes depending on the application (military, medical, etc.) which works in collaborative way. The energy and storage space in the sensor networks are two critical features [1]. In a network comprised of thousands of sensors, routing management and data exchange between sensors are intensiveness source in terms of energy and storage capacity. A sensor must store lots of information (oversized routing table in proactive protocols) to perform data routing. Researches and works in the field are trying to minimize energy consumption by splitting the network into groups to route captured information at different levels [2-4].
In heuristic approaches proposed for sensor networks, based on the clustering technique, the cluster members do not transmit their collected data directly, but instead it is forwarded to the base station corresponding to their cluster head. Consequently, the cluster heads are responsible for coordinating the cluster members, aggregating captured data, and then transmitting it to a remote base station directly or via a transmission mode multi-hop.
Therefore, since the cluster heads receive more packets and consume more energy to forward them within a long range. So, they are those whose energy is depleted most rapidly in clusters if they are elected for a long period. Therefore, other techniques should avoid the process of electing cluster heads, because they are constrained by energy and can quickly exhaust their batteries because of their high use. Thus, it can cause bottlenecks in clusters and subsequently trigger the process of reelection of cluster heads [5].
The selection of cluster head is the key issue in the clustering algorithm, which is also a multiple criteria in decision making procedure [6]. In this paper, we propose a new technique for the selection of the sensors cluster-heads based on the amount of energy remaining after each round [7,8]. As the minimum percentage of energy for the selected leader is determined in advance and consequently limiting its performance and nonstop coordination task, the new hierarchical routing protocol is based on an energy limit value “threshold” preventing the creation of a group leader, to ensure reliable performance of the whole network.
The remainder of the paper is organized as follows: Background and preliminaries is presented in Section 2. The synchronization approach based on clustering is described in Section 3. In Section 4, we discuss various simulations results using multiple sinks to balance the energy consumption of networks. Also, Discussion andopen issues for future studies is given. Finally, Section 5 concludes the paper.
2. Related Work
As Figure 1 exhibit, clustering algorithm can be classified into two major categories: distributed and centralized clustering. The first one is further classified into four sub types based on the cluster formation criteria and parameters used for cluster head election as identify based, neighborhood based, probabilistic, and iterative respectively. In probabilistic approaches for clustering wireless sensors networks rely upon prior assigned probability values for sensor node. The centralized clustering in this method, the base station BS node manages the clustering by utilizing a vector quantization (VQ) technique [9]. In the literature the centralized and probabilistic method are the most widely used in WSNs, also in our study we focused on them. In [10], Heinzelman et al. have proposed a distributed clustering algorithm called Low-Energy Adaptive Clustering Hierarchy (LEACH), for routing in homogeneous sensor networks. LEACH selects randomly the nodes cluster-heads and assigns this role to different nodes according to round-robin management policy to ensure fair energy dissipation between nodes.
In order to reduce the amount of information transmitted to the base station, the cluster-heads aggregate the data captured by the member nodes belonging to their own cluster, and then sends an aggregated packet to the base station. The protocol consists of two phases: The first is the set-up phase, and the second is the steady-state as illustrated in Figure 2.
In the first phase, cluster heads are selected and clusters are formed, and in the second phase, the data transfer to the base station is held. During the first phase, the process of electing cluster heads is triggered to select future cluster heads. Thus, a predetermined fraction of nodes connected as cluster heads according either 0 or 1. If the random number is less than a threshold T_{s} then the node becomes a cluster head in the current round, other-
Figure 1. Classification of clustering algorithms.
Figure 2. Time line operation of leach [5].
wise the node n is expected to join the nearest cluster head in its neighborhood. The threshold is set as:
(1)
where r is the current round number (starting from round 0), P the probability for each node to become cluster head and G the set of nodes that have not been cluster-head in the last 1/p round. The election probability of nodes G to become clusterheads increases in each round in the same epoch and becomes equal to 1 in the last round of the epoch.
However, while LEACH can increase the lifetime of the network, it has some limitations. LEACH assumes that all nodes can transmit data with great power to reach the base station and each node has a computing power enabling it to withstand various MAC layers. Therefore, LEACH is not suitable for networks deployed in large areas. In addition, LEACH randomly selects a list of cluster heads and there are no restrictions neither on their distribution nor on their energy level. Thus, the cluster heads can concentrate on one place and therefore there may be isolated nodes (without cluster head) that may occur. On the other hand, in LEACH, the aggregation of data is centralized and is performed periodically. However, in some cases, the periodic transmission of data may not be necessary, which exhausts rapidly the limited energy of sensors [10].
An improved version of LEACH called Multi-hop LEACH (LEACH-M) [11], in which members of a cluster may be more of a leap from their corresponding cluster-head and communicate with it in multi-hop fashion. Thus, they illustrate the cases in which M-LEACH outperforms LEACH. However, this proposed version requires each sensor must be able to aggregate data, which increases the overhead for all sensors. To improve this strategy, in [12], the authors have focused on heterogeneous sensor networks, in which two types of sensors are deployed: high capacity sensors (Super Sensor) and simple sensors. The sensors have large capacity processing capabilities and communicate very intensively and act as cluster-heads, while others are simple sensors with limited power, affiliated to the closest cluster-head in their neighborhood and communicate with it directly or in multi-hop.
LEACH-Centralized (LEACH-C) [13] is similar to the LEACH Protocol as far as formatting clusters at the beginning of each round is designed to improve the performance of LEACH. However, instead of nodes randomly self-selecting as a CH, a centralized algorithm is performed by the sink in LEACH-C. The sink collects location data from the nodes, and then broadcasts its decision of which nodes are to act as CHs back to the nodes. The overall performance of LEACH-C is better than LEACH by dispersing the cluster heads throughout the network. However, LEACH-C is sensitive to the sink location. Once the energy cost of communicating with the sink becomes higher than the energy cost for cluster formation, LEACH-C no longer provides good performance. Sinks may be located far from the network in most WSN applications. So, the dependence on the sink location is a major disadvantage of LEACH-C.
In a similar manner to LEACH-C, BCDCP [14] (BaseStation Controlled Dynamic Clustering Protocol) implies the sensors energy level sent to the base station to build homogeneous clusters during the installation phase (1st phase). The base station randomly selects the clusterheads while ensuring an even distribution of their locations in the area of interest in which they are deployed, and performs an iterative merger algorithm to find the optimal number of clusters. Then, determine the routes between clusters to-CH for routing data from a cluster-head to another, and creates a schedule for each cluster that diffuses into the network. During the second phase, the cluster-heads transmit data collected by the base station paths to cluster head. Nevertheless, BCDCP has the same limitations as LEACH-C since it uses a centralized architecture to elect cluster-heads.
In this new version of the LEACH protocol, the cluster contains; CH (responsible for sending data that are received by members of the cluster to the BS), Vice-CH (the node that will become a CH cluster in case of the death of CH) [4], cluster nodes (data collection from the environment and send it to CH). In the original protocol LEACH, the cluster head is still receiving data from cluster members, aggregating these information, and then sending them to the BS that may be located far from it. The CH will die sooner than other nodes in the cluster because of its operation of reception, transmission andsensing. When the CH dies, the cluster becomes useless because the data collected by the nodes of the cluster never reaches the base station.
V-Leach protocol [4], in addition to a CH in the cluster, there is a vice-CH which takes the role of CH when CH dies for the reasons cited above. By doing this, the data sent by nodes in the cluster can still reach the BS, and there is no need to elect a new CH every time whenever a CH dies. This will consequently extend the life span of the overall network [3].
3. Proposed Scheme
The clustering approach consists of dividing the network into a number of clusters, which are more homogeneous according to a specific metric or a combination of metrics, and therefore forming a virtual topology. Clusters are generally identified by a particular node called cluster-head. This allows for coordination among members of its cluster, to aggregate their collected data and then transmit it to the base station. The cluster-head is selected for this role based on a very particular metric or combination of metrics. This protocol is inspired from the idea Proposed in Leach [15].
3.1. Assumption
Some of the assumptions made in clustered for communicating in wireless sensor network are as following:
• The network is shaped by N sensors nodes deployed in square field and has designed cluster hierarchical topology.
• The base station is located outside the sensing field.
• Nodes are deployed randomly.
• The base station location is pre-determined.
• The cluster head nodes are cognizant of its members and can communicate directly with them.
• The cluster-head nodes communicate with their parent cluster-head, and finally every cluster-head node is communicate with base station.
• Each sensor node communicates with their respective cluster.
• 3.2. Proposed Algorithm
• The base station (BS) initiates the routing process.
• Election a cluster-head in each round with an energy value greater than ten percent of the residual value at each sensor.
• After selection of the head. Wait for member nodes.
• Create the table TDMA and sent it to members.
• Launch of the transmission phase.
• If the energy is less than its value in second steps, the process of LEACH will be launched.
Our approach is summarized in Figure 3.
3.3. Scheme for Radio Energy
The sensor network model applied in this paper is similar to those used in [16,17]. It is assumed that a fixed Base Station is located far away from the sensor nodes and all sensor nodes are immobile.
We adopt the energy model for free-space and multipath radio transmissions from (see Figure 4 and Table 1) [16].
Figure 3. Algorithm diagram.
(2)
where Eelec is the energy dissipated per bit to run the transmitter or receiver circuit, εfs and εmp depend on the transmitter amplifier model we use, and d is the distance between the sender and the receiver. By equating the two expression at d = d0, we have. To receive a K bits message the radio expends ERx(K) = Eelec*K.
The consumed power by sensor is that the consumed power by these captures units, treatment units and communication units. So the energy consumption formula is defined follows.
(3)
where:
• Ec/capture: Is the energy consumed by sensor during the capture unit activation. This energy depends primarily on the type of detected event (image,..) and of the tasks to be realized by this unit.
• Ec/treatment: is the energy consumed by the sensor during the activation of its treatment unit.
• Ec/communication: is the energy consumed by the sensor the activation of its communication unit.
The consumed energy by sensors during communication is larger those consumed by treatment unit and capture unit. Indeed, the transmission of a bit of information can consume as much as the execution of a few thousands instructions [18]. For that, we can neglect the energy of the capture unit, and the treatment unit compared to the energy consumed by the our approach is summarized in Figure 3
(4)
The communication energy breaks up into emission energy and reception energy:
(5)
Referring to [14], the transmission energy and recaption energy are defined as follows:
(6)
where:
• K: message length (bits).
• D: distance between transmitting node and receiving node
• l: of way loss exhibitor, l > = 2.
• Eelec: emission/reception energy, Eelec = 50 nJ/bit.
4. Experimentation and Analysis
Simulation Environment
In this section the performance of the modified protocol is demonstrated by numerical simulation. The proposed methods are compared to the conventional methods LEACH.
To assess the performance of proposed algorithm, we simulate O-Leach in square sized area of 100 m × 100 m. The nodes are randomly distributed over the field. This means that the horizontal and vertical coordinates of each sensor are randomly selected between 0 and the maximum value of the dimension. The sink is in the center and so; the maximum distance of any node from the sink is approximately 78 m. The energy value of a node is set to E Joules although this value is arbitrary for the purpose of this study.
Simulation is performed using Matlab-7, a discrete event network simulator. We have compared the performance of Optimization Leach with Leach protocols based on above energy and alive node. The basic parameters used are listed in Table 1.
Figure 5 illustrates the performance comparison Optimization leach (O-leach) to Low Energy Adaptive Clustering Hierarchy protocol (LEACH) in terms of energy consumption. As shown in Figure 5, energy consumption of O-leach is less than Leach. The reason is clear that the choice is made on a rotating basis in a more precise manner which allows the nodes capable of managing the role of a coordinator to perform on a rotating basis according to an energy limit criterion that allows more time to weak nodes to remain active cluster member managing less challenging tasks. Our proposed scheme reduces the number of choice of cluster not able to work as chief as compare to leach. In WSNs most of the energy is consumed for transmitting and receiving messages, therefore to limit the choice reduce the energy consumption for node in network and give more time for
Figure 4. Radio energy dissipation model [19,20].
Table 1. Simulation Parameters.
all networks.
It is observed from the graph in Figure 6 that the performance of our protocol compared to LEACH in terms of the number of alive nodes, all the node remain alive for 1125 rand, while the corresponding numbers for LEACH are 860. This is because LEACH treats all the nodes without discrimination. O-LEACH has longer stability period than LEACH just because of discriminating nodes according to their initial energy. Also we can see the intersection of the two curves (red and blue) in Figure 6 at the round 1140 after this round our scheme falling freely because the messages delivered by O-LEACH is more than LEACH. This means that O-LEACH is more efficient than LEACH. In addition after this intersection there is no guarantee that the alive nodes with leach works well.
Finally, the energy dissipation of the protocol under study over the number of rounds of operation has been obtained. Figure 6 clearly shows that optimization-Leach, has much more desirable energy expenditure than that of LEACH.
From the above analysis, it is found that O-Leach algorithm can achieve lower dissipation value of energy which is a little small but this value increases the stability of system than those of LEACH The above simulation results O-leach is able to save energy long time than leach. The main differences between the two approaches are illustrated in Table 2.
Figure 5. The energy dissipation.
Figure 6. Simulation rounds vs lifetime.
5. Comparaison between LEACH & O-LEACH
In this section we resume the performance of our scheme with an algorithm that has almost the same characteristics with him and represents a reference to the work of WSN, is LEACH [10].
6. Conclusions
Among the many difficulties in building a sensor network, a key challenge stands true: is the limited resource, which is mainly due to low storage capacity and limited battery life duration (1.2V) [21,22].
In this paper we have proposed an algorithm based on cluster topology to save energy consumed in the totality of network to increase its survival, reliability and efficiency. The critical analysis and simulation show that the proposed scheme is able to deliver inferior energy consumption relative to other works [9,10], which represents a reference in this line of research. We hope, the result of this paper would support other works to propose soluTable 2. Comparaison between LEACH & O-LEACH.
tions in making sensors networks even more reliable and efficient.
REFERENCES
- S. el khediri, N. Nasri and A. Kachouri, “Diverses Synchronization Issues in Wireless Sensors Networks,” 23rd International Conference of Microelectronics, Hammamet, 19-22 December 2011.
- W. R. Heinzelman and H. Balakrishnan, “An Application Specific Protocol Architecture for Wireless Microsensors Networks,” IEEE Transaction on Wireless Communication, Vol. 1, No. 4, 2002, pp. 660-670.
- K. Beydoun, “Conception d’un Protocole de Routage Hierarchique pour les Reseaux de Capteurs,” PhD. Thesis, L’U.F.R des Sciences et Techniques de l’Universite de Franche-Comte, Franche-Comte, 2009.
- M. B. Yassein, A. Al-zou’bi, Y. Khamayseh and W. Mardini, “Improvement on LEACH Protocol of Wireless Sensor Network (VLEACH),” International Journal of Digital Content Technology and Its Applications, Vol. 3, No. 2, 2009. doi:10.4156/jdcta.vol3.issue2.yassein
- K. Ramanan and E. Baburaj, “Data Gathering Algorithm for Wireless Sensors Networks: A Survey,” International Journal of Ad Hoc, Sensor and Ubiquitous Computing, Vol. 1, No. 4, 2010, pp. 102-114. doi:10.5121/ijasuc.2010.1410
- G. C. Gautam, T. P. Sharma, V. Katiyar and A. Kumar, “Time Synchronization Protocol for Wireless Sensors Networks Using Clustering,” IEEE International Conference on Recent Trends in Information Technology, Chenai, 3-5 June 2011.
- K. Baydoun, V. Fela and H. Guyennet, “Energy-Efficient WSN Infrastructure,” IEEE International Workshop on Distributed Collaborative Sensor Networks, Irvine, 19-23 May 2008.
- K. Baydoun, V. Fela and H. Guyennet, “Wireless Sensor Network Infrastructure: Construction and Evaluation,” IEEE International Conference on Wireless and Mobile Communications, Cannes, 23-29 August 2009.
- N. Shigei, H. Miyajima, H. Morishta and M. Maeda, “Centralized and Distributed Clustering Methods for Energy Efficient Wireless Sensor Networks,” Proceedings of the International MultiConference of Engineers and Computer Scientists, Hong Kong, 17-19 March 2009.
- W. R. Heinzelman, A. P. Chandrakasan and H. Balakrishnan, “Energy Efficient Communication Protocol for Wireless Microsensor Networks,” Proceedings of the IEEE Hawaii International Conference on System Sciences, Maui, 4-7 January 2000.
- V. Mhatre and C. Rosenberg, “Design Guidelines for Wireless Sensor Networks, Communication, Clustering and Aggregation,” Ad Hoc Networks Journal, Vol. 2, 2004, pp. 45-63. doi:10.1016/S1570-8705(03)00047-7
- X. Xuan, J. Chen, S. Zhen and Y. Kuo, “Optimal Hops- Based Adaptive Clustering Algorithm,” International Conference on Solid State Devices and Materials Science, Macao, 1-2 April 2012, pp. 1307-1314.
- P. T. Bhuvaneswari and V. Vaidehi, “Enhancement Technique Incorporated in LEACH a Survey,” Indian Journal of Science and Technology, Vol. 2, No. 5, 2009, pp. 36- 44.
- A. Jamle and E. Ahmed, “Data Aggregation in Wireless Sensor Networks Exact and Approximate Algorithms,” Workshop on High Performance Switching and Routing, Phoenix, 19-21 April 2004.
- G. Smaragdakis, I. Matta and A. Bestavros, “SEP: A Stable Election Protocol for Clusterd Hetergenous Wireless Sensor Networks,” 2nd International Workshop on Sensor and Actuator Network Protocols and Applications, Boston, 22 August 2004.
- V. Geetha, V. Kallapur and S. Tellajeera, “Clustering in Wireless Sensor Networks: Performance Comparaison of LEACH and LEACH-C Protocols Using Ns2,” 2nd International Conference on Computer, Communication, Control and Information Technology, 25-26 February 2012, Vol. 5, pp. 163-170.
- L. Dong, D. Song and X.-M. Wen, “An Energy Efficient Clustering Routing Algorithm for Wireless Sensor Networks,” The Journal of China Universities of Posts and Telecommunications, Vol. 13, No. 3, 2006, pp. 71-75. doi:10.1016/S1005-8885(07)60015-6
- R. G. Hamed and J. Karimpour, “Energy Balancing and Hierarchical Clustering Based Routing algorithm for Wireless Sensor Networks (EBHCR),” Australian Journal of Basic Applied Sciences, Vol. 5, No. 9, 2011, p. 1.
- G. J. Pottie and M. Younis, “Wireless Integrated Network Sensors,” Communications of the ACM, Vol. 43, No. 5, 2000, pp. 51-58. doi:10.1145/332833.332838
- W. N. Richard and A. Boukerche, “Mobile Data Collector Strategy for Delay-Sensitive Applications over Wireless Sensor Networks,” Computer Communication, Vol. 31, No. 5, 2008, pp. 1028-1039. doi:10.1016/j.comcom.2007.12.024
- X. Xuan, J. Chen, S. Zhen and Y. Kuo, “Optimal HopsBased Adaptive Clustering Algorithm,” International Conference on Solid State Devices and Materials Science, Macao, 1-2 April 2012, Vol. 25, pp. 1307-1314.
- G. Ran, H. Zhang and S. Gong, “Improving on LEACH Protocol of Wireless Sensor Networks Using Fuzzy Logic,” Journal of Information and Computational Science, Vol. 7, No. 3, 2010, pp. 767-775.