Abstract: Transceivers are the major energy consumption in a Wireless Sensor Network which is made of low-power, small in size, low cost and multi-functional nodes. These sensor nodes are operated by batteries which put significant constraint to the energy available to them. Each sensor node collects sensed data and forwards it to a single processing centre called the base station which uses all reported data to detect an event or determine the changes in an environment. In present study, we propose energy optimization in Wireless Sensor Networks (WSNs) using uniform distributed clustering algorithms. One of the algorithms distributes cluster heads uniformly in each cluster and each non-cluster head transmit its data to the cluster heads with short distance which reduces the communication distance of each node. Thus, minimizes the energy consumption of sensor nodes. The second algorithm generates cluster heads in hierarchical form in order to transmit the aggregate data to the base station. It was observed that there is increase in energy savings as we move from bottom up in the hierarchy. Both UDCA protocol and Low Energy Adaptive Cluster Hierarchy protocol (LEACH) were simulated. The simulation results show significant reduction in energy consumption of sensor nodes and cluster heads are more uniformly distributed among all nodes in UDCA compare with LEACH and extend the wireless sensor networks lifetime.
INTRODUCTION
With recent and continue advances in sensor technology, electronics and micro electro-mechanical system designs have assisted in the development of relatively inexpensive, small in size, low power sensor nodes. Sensor nodes are incorporated with sensing, processing and wireless communication (He et al., 2006). These are used to acquire data, process and communicate to the other sensors within the networks usually, through radio frequency channel (Rozyyev et al., 2011). Sensor nodes in most cases are immobile and they are more densely deployed to monitor particular area of interest than mobile ad-hoc networks. One of the advantages of wireless sensor networks is their ability to operate unattended in harsh environments where it may be difficult or dangerous for human being to reach (Sohrabi et al., 2000).
Sensor networks have a wide range of applications. Some of the application areas are home automation, in which sensor nodes and actuators are inserted into home appliances such as electric bulbs, refrigerators, micro-wave ovens. This makes it possible for end users to control these devices remotely. Environmental monitoring applications, sensor networks can be used to monitor changes in air, water and soil. Healthcare applications, they can be used to administer drugs in the hospitals, diagnose patients for diseases remotely, monitor both the medical staff and patients inside the hospitals. Other application areas include building security, earth movement prediction, weather and climate analysis and prediction and so on (Akyildiz et al., 2002).
Sensor nodes networks are powered by batteries which often deployed in remote areas, rough physical environments or some unreachable areas. It is expected that these batteries lasted for years before they can be replaced (Wang et al., 2007; Wang et al., 2011b). For example, in a battle field scenario, soldiers may not have time to change or recharge the batteries of their wireless devices and running out of batteries means a loss of all of their communication capacity (Yu et al., 2009). Therefore, it is necessary to minimize energy consumption of wireless sensor in order to increase network lifetime.
Energy efficiency is of primary importance in WSNs (Wang et al., 2011a). However, sensing, data processing and data communication are the main energy consumption in which data communication is a major source of energy consumption (Pottie and Kaiser, 2000). For instance, the energy used to transmit 1 kb of data by a radio communication to a distance of 100 m, the same amount of energy can be used by a 100 MHz processor to process 300000 kb of data in one second (Xin et al., 2008). In addition, if all data sensed by sensor nodes in WSNs are transmitted to the base station directly, the data will be too enormous and large amount of energy will be consumed during transmission (Lu et al., 2009).
For this reason, we need methods for combing data into high-quality information at the sensors or intermediate nodes which can reduce the number of data transmitted to the base station resulting in conservation of energy and good bandwidth utilization (Guo et al., 2010; Liu et al., 2010; Sabari and Duraiswamy, 2010).
In order to minimize the energy consumption of WSNs, a uniformly distributed cluster heads algorithms for WSNs have been proposed. In recent time, many clustering algorithms have been proposed with different protocols by different researchers, there still need to look for other techniques in which energy can be optimized in WSNs.
Some traditional clustering algorithms for wireless ad-hoc networks have been extensively discussed by Amis et al. (2000), Baker and Ephremides (1981) and Hong et al. (1999). However, these clustering algorithms are not suitable for sensor networks because in ad-hoc networks, the primary concern is quality of service (QoS) while energy efficiency is the secondary (Chen et al., 2008). While in sensor networks energy optimization and scalability are the primary concern for extending network lifetime.
However, energy efficient algorithm using Low Energy Adaptive Clustering Hierarchy (LEACH) was proposed by Heinzelman et al. (2002a). Other algorithms developed thereafter were based on this algorithm. The operation of LEACH is divided into rounds, each round begins with a set-up phase when the clusters are organized and cluster heads are determined. Follow by steady state phase where data are transmitted from cluster heads to the base station.
In order to determine the Cluster Heads (CHs), LEACH uses randomization technique based on probability (Heinzelman et al., 2002b). The cluster heads broadcast their new status to all sensors in the networks. Other nodes determine the cluster to join based on the received signal strength from these CHs. Each sensor node informs the appropriate CH that it will be a member of the cluster and the node clusters are organized.
During the steady phase, the sensor nodes begin to sense and transmit data to the CHs using Time Division Multiple Access (TDMA). Cluster heads collect data from sensor nodes, aggregate and send it to the base station for processing (Bandyopadhyay and Coyle, 2003).
Considering a single round of LEACH, a stochastic CH selection will not automatically lead to minimum energy consumption during the steady phase for data transfer of a given set of sensor nodes. Although, LEACH clustering terminates in a finite number of iteration but does not guarantee good CHs distribution. CHs may be chosen from one part of the network (Heinzelman et al., 2002b).
Finally, LEACH protocol is not suitable to networks deployed in large regions where we have thousands of sensor nodes.
Power-Efficient Gathering in Sensor Information System (PEGASIS) protocol was proposed by Lindsey and Raghavendra (2002). It is an improvement over LEACH. It allows only one CH to transmit to its local neighbor in the data aggregation phase instead of a node sending sensed data directly to its CH as in the case of LEACH.
The main idea of PEGASIS is to form a single chain among sensor nodes using Greedy algorithm. Each node in the chain acts as cluster head which receives data from a neighbor node, fuse it and send it to the next neighbor node closer to the base station. The algorithm make sure that only one node transmits data from source to the base station in any given transmission time frame. This ensures that only relevant data gets to the base station while all redundant data might have been removed down the chain. Energy efficiency is achieved with this approach, since each node acts as CH in the chain and responsible for data transmission to the base station. However, if a node dies within the chain, a new node will be selected based on calculation to avoid transmission failure. Selection of a new node as a result of dead of a node can bring significant overhead especially in a large network. PEGASIS approach avoid the clustering overhead of LEACH protocol but each sensor node needs to know the status of its neighbour so that it will have the knowledge where to send the data to.
The main objective of this study is to reduce energy consumption of sensor nodes within the network by:
| • | Developing an algorithm that will uniformly distribute cluster heads within the clusters so that non-cluster heads will transmit to the cluster heads with minimum distance |
| • | Developing an algorithm that will reduce communication distance among cluster heads in the hierarchy |
BASIC RADIO ENERGY MODEL
High amount of energy is consumed during communication (Stemm and Katz, 1997; Xin et al., 2008). Therefore, it is necessary to minimize number of communications of sensor nodes. Energy consumption for communication depends on various factors such as the transmit power level, hardware profile, packets size and distance (Zhou et al., 2008). Energy consumption of sensor node is due to data transmission and reception.
Fig. 1 is the radio energy consumption model as stated by Heinzelman et al. (2002a).
The energy consumed in transmitting one message of size k-bit over a transmission distance d is stated in Eq. 1 as:
| (1) |
| Fig. 1: | Radio energy consumption model |
Where:
| k | = | Length of the message |
| d | = | Transmission distance between transmitter and receiver |
| Eelec | = | Electronic energy |
| εamp | = | Transmission Amplifier |
| n | = | Path-loss component (2 = n = 4) |
Also, the energy consumed in the same message by the receiver is given by:
| (2) |
Hence, the total energy consumption when sensor receives a message and forwards it over to a distance d is given by:
| (3) |
THE PROPOSE ALGORITHMS
This algorithm uniformly distributes Cluster Heads (CHs) in each cluster so that energy consumption by each node when transmitting data to the CHs will be minimized.
The following assumptions are made about the Clustering algorithms and to simplify the analysis of the algorithm:
| • | At the initial stage (first round) all the sensor nodes in the network have the same energy and equal amount of energy is consumed during communication |
| • | The base station has all the information about location of each node |
| • | All sensor nodes and base station are stationary after deployment |
| • | Each sensor node has the probability (P) to become CH in the first round and after 1/P rounds; a node which has been CH is eligible to become CH |
| • | Every node determines its cluster to which it will belong to |
| • | CHs perform data reception, aggregation and transmission to the base station |
| • | Total number of 100 sensor nodes is deployed in the network |
Low Energy Adaptive Clustering Hierarchy (LEACH) algorithm: We are going to consider LEACH algorithm clusters formation and cluster heads selection since other algorithms were developed based on this algorithm (Chang and Kuo, 2006). Then our propose algorithms will be presented. LEACH algorithm is divided into rounds.
Round one (Setup Phase): At the Setup Phase clusters are organized and cluster heads are determined.
| Step 1: | The location information of all the sensor nodes in the network are collected by the base station and partitions it into different groups called clusters (assuming into 10 clusters). |
Each cluster below contains these sensor nodes in the set:
| • | Cluster1 = (S5, S13, S25,.....,S81) |
| • | Cluster10 = (S2, S45, S73,.....,S98) |
where, S denotes sensor node:
| Step 2: | At the current round, all the nodes have the same maximum energy. Each node has probability P to become Cluster Head (CH) in each cluster (Heinzelman et al., 2002b). Hence, CHs are chosen randomly from each cluster. |
| Step 3: | After CHs have been elected, each CH node broadcasts an advertisement message to the rest of the non-cluster head nodes in the cluster using Carrier Sense Multiple Access (CSMA) MAC Protocol. |
| Step 4: | Based on the received signal strength of the advertisement from each CH, each non-cluster head node determines which clusters it wants belong to, by choosing CH that requires minimum communication energy. |
| Step 5: | Each non-cluster node sends back message to the CHs about the cluster it wants to belong using CSMA MAC Protocol. |
| Step 6: | TDMA is set-up for each node to transmit by the CH and to turn-off radio components of each node at all time except during transmission to avoid data collision and to save energy. |
| Step 7: | The CHs receive data from each sensor node perform signal processing and send it to the base station where it will finally process and access by the users. |
IMPROVEMENT OVER LEACH ALGORITHM
New cluster head selection method: A new cluster head is chosen if the existing residual energy of the cluster heads in the current round is below the set threshold value.
If the following conditions hold:
| • | That sensor node has not become cluster head for the past (1/P) – 1 rounds |
| • | That the residual energy of a node is higher than the average energy of all the nodes in that clustering |
Then the probability of a node becoming cluster head is given as:
| (4) |
where, Erem is the remaining energy in node (I), Eavg is the average energy of all the nodes in a cluster g is the expected number of cluster head in each round N is the number of nodes in each cluster.
The essence of equation (1) is to make sure that nodes with morwe energy have stronger probability of becoming cluster heads than nodes with less energy.
In order for the CHs to distribute uniformly within the clusters, we introduced these rules.
| • | Every node must be k-hop from one CH |
| • | Every node that is k+1 from CH must turn-off its radio transmission when others nodes are transmitting |
These two rules absolutely help to achieve uniform distribution of CHs in each cluster, so that each node will transmit its sensed data to the CH with the minimum energy because the transmission distance has been reduced.
Inter-cluster communication: In order to the achieve energy efficiency, only cluster heads need to transmit sensed data by sensor nodes in to each cluster to the next cluster heads and finally to the base station. This reduces the amount of data received by the base station for processing, hence prolong the network lifetime in WSNs.
Algorithm for hierarchical clustering: The general procedure of the hierarchical clustering with 3 layers from bottom-up fashion is now described. This can also be extended to M layers.
Layer 1 is the lowest layer and layer 3 is the highest in the hierarchy as shown in Fig. 2 below.
| Fig. 2: | 3-Layer hierarchical clustering |
BASE STATION
At the lowest layer, layer one elects itself cluster heads (CHs), follow by layer 2 and layer 3.
Cluster heads election:
| Step 1: | A node at layer 1 elects itself to be a CH based on stochastic probability and announces its decision to all other nodes in the networks through broadcasting using CSMA MAC protocol. Each node that receives the message with minimum signal strength will join the cluster |
| Step 2: | Among the clusters in layer 1, CHs elect themselves at layer 2 CHs based on method used in layer 1 and broadcast their decisions. CHs at layer 3 will also be elected using the same method |
| Step 3: | After the formation of the hierarchical clustering and CHs have been selected for the clusters, sensor nodes at layer 1 begin to transmit their sensed data to the CHs. The CHs in layer 1 are able to communicate with each other to aggregate the data, removing the redundant and send it to CHs in layer 2 and from layer 2 to layer 3 |
| Step 4: | Finally, CH in layer 3 will further compress the data and transmit them to the base station where it will be accessible to the user to perform final processing on it to give useful information for decision making |
Significant amount of energy will be saved with this algorithm, because instead of each CH to transmit directly to the base station which is at a far distance. CHs will now communicate with each other via multi hops to aggregate data and the last CH(s) nearest to the base station will do final data transmission to the base station.
SIMULATION RESULTS AND ANALYSIS
In this section, we evaluate the performances of our propose algorithms through simulation. We simulated our proposed algorithm, Uniformly Distributed Clustering Algorithms (UDCA) and LEACH protocol in order to see the level of energy optimization that our protocol can achieve. 100 sensor nodes were randomly distributed over the sensor field of 100x100 m2 as shown in the Fig. 3 below and the base station is located far away from the sensor field. Each node started with an initial energy of 0.5J. Other parameters used for the test can be found by Heinzelman et al. (2002a).
Cluster head probability P used is 5% (0.05) which means about 5 sensor nodes in each round become cluster heads and fuse collected data to 5% of its initial size.
The main concern in this test is to prolong network lifetime. There is need to know number of Alive nodes, that is the time when the first node dies and time the last node dies during network runtime (number of rounds).
The performance of our algorithm, UDCA and LEACH protocol were examined in the simulation test based on number of sensor nodes that were alive after certain number of rounds.
From Fig. 4 above, it shows that time taken for the first node to die and time taken for the last node to die in UDCA is greater than LEACH protocol which means more number of nodes are Alive in UDCA than in LEACH after each round. This is achieved because sensor nodes in each cluster transmit their sensed data to the cluster heads with minimum energy due to short distance between them and cluster heads were uniformly distributed.
| Fig. 3: | 100 sensor nodes randomly distributed |
| Fig. 4: | The number of Alive nodes over the simulation time (No. of Rounds) |
| Fig. 5: | Total number of data transmitted to the base station after each round |
However, Fig. 5 shows the number of data sent to the base station through the cluster heads in hierarchical form.
The graph shows number of data sent by cluster heads to the base station is more in UDCA than LEACH in each round. The reason is that there are more Alive nodes and cluster heads in UDCA than LEACH to transmit data to the next cluster heads and finally to the base station. UDCA, unlike LEACH protocol its selection of cluster heads in a round does not base on random number generator.
CONCLUSION
In present study, energy optimization for WSNs using uniform distributed clustering algorithms called UDCA has been presented. UDCA partitioned the sensor field into different clusters, each cluster nodes transmits its data to the cluster heads with short distance. Nodes with maximum residual energy are elected as new cluster heads based on the algorithms for uniform energy distribution among all the nodes and aggregated data is transmitted by cluster heads to the base station. Simulation results showed that better performances of UDCA are achieved than LEACH protocol because the technique significantly minimizes total energy consumption among cluster member nodes due to short range communication. In UDCA, energy consumption is more uniformly distributed among all nodes and extends the lifetime of sensor nodes in the network.