Probabilistic Energy Value for Clustering in Wireless Sensors Networks ()
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].
(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 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.