Portal de Periódicos da CAPES

Load‐balanced energy efficient clustering protocol for wireless sensor networks

2016; Volume: 6; Issue: 3 Linguagem: Inglês

10.1049/iet-wss.2015.0069

2043-6394

Saman Siavoshi, Yousef S. Kavian, Hamid Sharif,

Molecular Communication and Nanonetworks

IET Wireless Sensor SystemsVolume 6, Issue 3 p. 67-73 Special Issue: Selected Papers from the 9th International Symposium on Communications Systems, Networks and Digital Signal Processing (CSNDSP 2014)Free Access Load-balanced energy efficient clustering protocol for wireless sensor networks Saman Siavoshi, Corresponding Author Saman Siavoshi siavoshisaman@gmail.com Faculty of Engineering, Shahid Chamran University of Ahvaz, Ahvaz, IranSearch for more papers by this authorYousef S. Kavian, Yousef S. Kavian Faculty of Engineering, Shahid Chamran University of Ahvaz, Ahvaz, IranSearch for more papers by this authorHamid Sharif, Hamid Sharif Department of Computer and Electronics Engineering, University of Nebraska, Lincoln, NE, USASearch for more papers by this author Saman Siavoshi, Corresponding Author Saman Siavoshi siavoshisaman@gmail.com Faculty of Engineering, Shahid Chamran University of Ahvaz, Ahvaz, IranSearch for more papers by this authorYousef S. Kavian, Yousef S. Kavian Faculty of Engineering, Shahid Chamran University of Ahvaz, Ahvaz, IranSearch for more papers by this authorHamid Sharif, Hamid Sharif Department of Computer and Electronics Engineering, University of Nebraska, Lincoln, NE, USASearch for more papers by this author First published: 01 June 2016 https://doi.org/10.1049/iet-wss.2015.0069Citations: 33AboutSectionsPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onFacebookTwitterLinkedInRedditWechat Abstract This paper introduces an innovative clustering protocol of load balancing which divides the whole network to the virtual circle with variable radiuses. The authors’ protocol uses an innovative architecture in intra cluster communication. In this protocol, radius of each virtual circle and the size of each cluster will increase with the increasing distance from the base station, in such way that cluster size of each circle will be different with the clusters of the other circles. In each cluster, leader nodes are responsible for collecting and compressing data from their ordinary neighbour nodes and sending them to head cluster. Simulation results demonstrate that proposed protocol increases network lifetime in comparison with protocols LEACH, TCAC and DSBCA by 73, 52 and 21%, respectively. It also makes energy efficiency and load balancing across the network. 1 Introduction Recent advances in hardware technology, has made possible the ability to produce small sensors with limited energy which are limited in terms of energy, computing power and wireless communication capabilities. Nodes sense various data from the environment and perform local processing, eventually send messages to the base station (BS) directly or through intermediate nodes. The ability to communicate directly with the natural phenomenon causes widespread development of wireless sensor networks (WSNs) in military, commercial, intrusion detection, industrial, healthcare, natural disasters and rescue operation affairs [1–3]. One of the major limitations of sensors is their low battery capacity that despite this limitation, so efficient using of energy sensors is very necessary. Sensors utilise the battery power to carry out operations of data collection, data evaluation and their communications and by the end of the battery power, the performance of these sensors will completely stop. This results in part of the network's information loss, also in most applications due to extensive area of evaluation and in some cases unsafe area there is no possibility of changing or recharging the battery of sensors [4, 5]. Therefore how to save energy is vital for the situations of WSNs, to minimise energy consumption some mechanisms such as timing radio, limited control packets, topology control integration or aggregating data is provided. Data aggregating involves combining data that belong to a single event. The main objective of aggregating is to increase the network lifetime by reducing resource consumption such as battery power or bandwidth. Considering that sending data has a large share in energy consumption, therefore using an appropriate routing mechanism can cause energy efficiency in network [6–8]. Routing is a challenging issue in designing WSNs, so that many of the studies that have been done in the area of routing protocols introduce WSNs in order to save the energy of nodes and increase the efficiency of routing. Clustering is a key technique for prolonging the lifetime of WSNs by reducing power consumption [9, 10]. The concept of hierarchical routing is used to increase energy efficiency in WSNs. In this approach, a number of nodes form a cluster, and data collection and data compression techniques are conducted by cluster head (CH) levels. These techniques will save energy sources because the amount of data sent to the BS is substantially reduced. In intra-cluster communications, the data transmission distance between the cluster-member nodes is reduced, in addition, the cluster-member nodes can go into sleep mode and save energy for a relatively long time [11]. One of the best known methods for routing is Clustering-based hierarchical routing. In this method, the entire network nodes are classified in the clusters and in each cluster one node is selected as cluster head, which is responsible for data aggregating and guiding them to the BS. Clustering methods provide a better possibility of rapid communication, scalability, routing and topology management [12–15]. One cluster head may be determined by the nodes in a cluster or have already been set by the network designer. Cluster head also may be identical to other nodes is in terms of resources and capabilities or be richer than other nodes. Cluster members may be fixed or variable. One cluster head can schedule activities within the cluster in a way that each node at any time other than the time allocated to it goes to sleep and to protect their remaining energy level [16–18]. In this paper, the energy efficient clustering protocol is introduced based on the virtual circles that with an innovative strategy in protocol architecture causes balancing of energy consumption throughout the network. In this algorithm, in each cluster, depending on cluster size, number of nodes is selected by local information and also using the appropriate criteria which are called leader nodes that are responsible for collecting and compression of data from ordinary nodes within their own leadership. Then they send these data to the cluster head and cluster heads, which have been selected with decentralised approach and appropriate measures will send data to the main station with a multi-hop perspective. The remaining of this paper is organised as follows: Section 2 reviews the related works. Section 3 describes the proposed protocol in details and Section 4 evaluates the proposed protocol performance. Finally, Section 5 concludes the paper. 2 Related works In recent years, many protocols in clustering based networks are proposed. These protocols are different according to the arrangement of nodes, methods that have been developed to solve the problem, network architecture which they follow, characteristics of cluster head nodes and operational models of network. The first and most famous proposed protocol to reduce energy consumption using adaptive clustering of nodes is low-energy adaptive clustering hierarchy (LEACH) [19] protocol. After this protocol, until today many and various clustering based protocols have been proposed that all of them attempt to overcome the challenges involved in this protocol of which [20–22] protocols can be noted. In this protocol, in each round cluster heads are selected, then the non-cluster head nodes give information to the nearest cluster head and the cluster head, after collection and compression of data, sends the ultimate data to the main centre for further processing. This protocol performs all steps of selecting cluster heads to data collection in a decentralised way. In this protocol, each node by generating a random number and comprising it with a threshold value decides that must be a cluster head in this round or not. Then all the nodes that have decided to be a cluster head will notify their decision to the entire network. Among the problems of this protocol the possibility to choose low-energy nodes as cluster head and the possibility of improper distribution of cluster heads can be pointed. Another problem is lack of this protocol longevity in large scale networks. Although the power efficient gathering in sensor information system (PEGASIS) [23] protocol does not be count as a clustering protocol, but its method for reducing energy consumption alike all clustering protocols is reducing the size of data sent to the centre by compression and elimination of redundant information. In this protocol, a chain is formed in the beginning of each round. Process of chains formation can be centralised as well as decentralised. Deficiency of this protocol is the assumption that all information of network has the ability to be compressed and converted into one data with an equal size to each of the nodes’ data. In addition delay of this protocol is also very much. A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks (HEED) [24] is also a clustering protocol, which uses multi-level energy feature to select the cluster head node. In fact, the combination of adjacent degree with neighbours and residual energy of each node is used to form clusters. In this algorithm, cluster heads are suitably distributed and sending data to the BS is performed in a multi-hop way. An energy efficient clustering scheme in wireless sensor networks (EECS) [25] protocol alleviates disadvantages of LEACH protocol to some extent. In this protocol, cluster head candidates with a constant and specific radius begin to compete with other candidates and among them, candidates with higher energy will be elected as cluster heads. Ordinary nodes also besides considering the distance to the cluster head employ the distance of cluster head to the centre as another criterion for selection of cluster head. Sending data from the cluster heads to the centre is done in a single hop way. Distribution of cluster heads in this protocol is appropriate. On the other hand, taking into consideration the residual energy criterion in the cluster head selection, possibility of selecting cluster heads with low energy level is very low. The disadvantage of this protocol is its high data overhead. Unequal cluster based routing protocol (UCR) [26] protocol is also one of the hierarchical clustering protocols. Cluster head selection process in this protocol is similar to EECS protocol with the difference that the radius of nodes’ candidacy is variable so that nodes farther away from the main centre have larger radiuses. Figure illustrates the method of doing this. The purpose of this process is that size of closer clusters to the centre be small so that intra-cluster energy in these clusters be less and since considering multi-hop communication between cluster heads imposes higher consumption loads on the cluster heads closer to the BS, total energy consumption of the nodes which is the total of inter- and intra-cluster energy consumptions and being cluster head, balances for all the nodes near or far to centre. In the topology-controlled adaptive clustering (TCAC) [27] protocol, the main objective is cluster heads proper distribution and load balancing on the cluster heads. The performance of this protocol is in a decentralised way. At first some of the nodes are randomly selected as the cluster head candidates, and then some of them by the same process as EECS protocol will be elected as cluster head. After this stage, cluster head nodes introduce themselves to the network with the carrier-sense multiple access (CSMA) protocol and ordinary nodes, using prioritised tables, choose their cluster head. After this step, cluster heads identify their members. Cluster heads send the final data in a single hop to the BS. This protocol creates a lot of overload data, because in the cluster selection process, each node must send the required information to its cluster head twice. In [28], based on multi-criteria optimisation technique clustering operation is performed. This protocol has used a decision matrix which specifies significance of each parameter in the calculations for determining the cluster head node with that. It considers parameters such as distance to the BS and the remaining energy for selecting cluster head node and nodes according to the criteria of the distance to the cluster head and energy will be connected to the cluster heads. Algorithm energy-balancing clustering approach for gradient-based routing (EBCAG) [29] works based on the gradient distance; in this method the nodes are divided into unequal clusters and each sensor node maintains a gradient value which in fact shows the minimum number of hops to the sink. Cluster size is also determined based on the value of the gradient cluster head node and the data that are collected from the cluster members must follow up in order to reduce the gradient while sending to the sink. Energy-aware clustering algorithm with non-uniform distributed nodes (EADC) [30] introduces an energy-aware clustering algorithm with non-uniform distributed nodes is introduced which balances energy consumption in the network by development of similar clusters as well as intra-/inter-cluster energy consumption. This protocol is made of three phases: in the information collection phase, each node sends its ID and remaining energy within a certain radius in a specified time. In the cluster head competition phase, any node, which fails to receive the head-msg message at a certain time sends a head-msg message and in the last phase which is called cluster formation, each non-cluster head node selects the nearest CH to send its data. In CHs selection, the residual energy of the node and average residual energy of the neighbouring nodes is considered as the criterion, and each CH considers the residual energy levels and the lower number of cluster members as the criteria for transferring data to another CH. In transferring the data to BS, if the distance is less than the certain threshold distance, then the CH sends its data directly, otherwise, it will use a multi-hop method. Local energy consumption prediction-based clustering protocol (LECP-CP) [31] introduces a local energy consumption prediction-based clustering protocol in which CHs compete based on the prediction of the local energy consumption. In this protocol, intra-cluster communication is performed directly, but inter-cluster communication is performed through a routing tree. In addition, this protocol considers a number of nodes that are directly in contact with BS as the child nodes, so that if the distance of the CH that wants to send its data to the BS is less than the threshold Euclidean distance is, it will send its data directly otherwise it will uses a multi-hop routing tree to send its data. The above process is called data transmission phase. Cluster setup phase is the initial phase of the protocol that consists of three sub-phases under which the nodes which are qualified to be selected as cluster head compete against one another. After the cluster heads are determined, the other clusters will join the nearest cluster head and form clusters. In [32], a multi-layer clustering routing algorithm is introduced that takes residual energy of the nodes and the distance between vehicular nodes and centre station as the criteria for establishment of WSN communications between roadside and vehicles or between vehicles to improve the balance of power consumption in this algorithm. In this algorithm, the cluster heads are always selected from among the recent non-cluster head nodes. In the initialisation phase, the nodes calculate the optimal communication radius and each node makes a list of the neighbouring nodes based on its information and a bottom-up approach is used to implement this list. In this protocol, depending on the level of nodes, direct or multi-hop communication will be used. In [33], a self-organising clustering algorithm is introduced. In this protocol for the uniformity of distribution a multi-layered structure by equal size clusters is used in each layer. Its structure is in such a way which clusters size, in layers closer to the BS is smaller. At first, some number of nodes are randomly assigned, among them, based on the distance to the BS and also the density of connections, temporary cluster head nodes are determined and among these candidates those who have a higher weight standard will be selected as cluster head. Cluster head nodes based on their threshold size either accepts the requesting nodes as member or refuses to accept them and finally the cluster head nodes, after data collection and compression, send data to the BS through a multi-hop perspective. In this protocol, once the network size is too large, naturally the last layer clusters become very large. This increases the distance travelled by the data, in intra cluster communication, therefore the energy loss is greater. 3 Protocol details The main idea behind this paper is to assign responsibilities to the sensor nodes according to their position in the network so that they can better perform their duty and be more effective in raising energy efficiency. Some nodes are selected as cluster head nodes from among the energetic nodes according to the value functions. In fact, the aim of labour division in this study is to distribute energy consumption among the cluster head nodes and their parent nodes. According to the strategy used in this study, the energetic nodes with proper positions are used as cluster head nodes and are changed cyclically just like many other clustering protocols, in addition appropriate nodes are selected according to three criteria including residual energy, the node's degree within an specified radius from the parent node, and the number of volunteer parent nodes within the above-mentioned radius, to reduce and balance energy consumption across the network through division of labour. In each continuous diphasic process, the protocol creates phased named setup and steady state. In the setup phase, the network graph has determined. In other words, other clusters, cluster heads and parent sensory nodes and the path between each node to BS has been determined. In the phase steady state, the network data matched by defined topology in the phase setup in the same process, collected from nodes and receive to the BS. 3.1 Network model and assumptions All considered assumptions in proposed protocol are as follows: All of the nodes are distributed randomly and uniformly. The BS is located the centre of the network. All nodes are homogeneous, this mean these are same in terms of resources, processing, communication, the initial energy and so on. All nodes are stationary after deployment and all of them sense the environment and do have data to send. The nodes are considered as dead when their energy is over. Sensor nodes are location–unaware that means they are not equipped with GPS or other similar equipment. A node can estimate the distance to another node based on the received signal power. This paper uses a simplified model used in [19] for communication energy consumption. If distance d (‘d’ is the distance between transmitter and receiver) smaller than threshold distance d0, free space channel model is used (energy disiption d2) otherwise this protocol uses or multi-path fading channel model (energy disiption d4). When a node sends a k -bit package to d distance, the energy consumption is computed as follows (1)In (1), Eelec is required energy to activate the electronic circuits and depends on digital coding modulation, filtering technique, spreading of the signal and amplifier energy, energy term is depends on the distance between sender and receiver and acceptable bit-error rate, Efs and EMp are required energies to send a bit in free space and multipath, respectively, d is the distance between sender and receiver, and d0 is the threshold distance that is computed with the following equation (2)When nodes receive a k -bit package, the consumption energy is computed with the following equation (3)In addition, energy for data aggregation by parent nodes and/or cluster head is computed with the following equation (4)In (4), n is the number of messages and EDA is the required energy to aggregate a bit. 3.2 Setup phase Setup phase consists of cluster head selection, leader node selection and next hop selection steps as follows. Fig. 1 demonstrates the multilayer architecture of the network operation considering three types of nodes. Fig. 1Open in figure viewerPowerPoint Multilayer structure of network 3.2.1 Step 1: cluster head selection Nodes monotony distribution is one of the needs of clustered WSNs application. Suitable distribution makes possibility to create balanced cluster heads, which have different advantages, for example: maximum intra-cluster delay is proportional with biggest cluster, so balanced cluster avoids delay increase. Energy avoids in disposing of fertility balance of cluster heads. Also avoid long distance communications between cluster head and its' staffs. Protocol helps to have suitable distribution of cluster heads. Suitable cluster heads distribution makes possibility for creating balanced clusters which have several advantages and avoid intra-cluster long distance communications. It also balances the loads on the cluster heads. The intended standards cause not to choose nodes, which are in unsuitable situations as cluster head because some of the nodes in some of net areas cannot be in a cluster centre because of their situation in the network, anyway (e.g. assume a square net area, the nodes in borders and corners are in such situation.) So utilises such nodes as cluster head cause the increase of intra-cluster energy. The receiver and the sender nodes consume much more energy than ordinary nodes. So giving two expensive spectrum synchronically to node especially in the network late age could finish all of the battery energy and non-operate the whole network. Therefore we attempt to choose parent nodes in each cluster in order to separate these two duties for productivity increase. We build two value functions in order to determine each sensory node competence for being cluster head or sender. We do this simply by nodes degree standard second power average of neighbour nodes on special ray and also distance to BS. Nodes with high degree are generally suitable for being cluster head. The advantage of this task is by less cluster head it could cover more nodes so as to avoid expensive communications. Prepensely, both reduce consumption and equipoising could increase lifetime. Starting of this step, BS broadcasts a HELLO-MSG message across the network that includes its ID and each node estimates its distance to the BS of dBS according to received signal strength and broadcasts an INITIAL-MSG message across the network that includes its ID and its distance to the main station and other nodes calculate their distance from that node. Then, each node calculates its cluster head RCH using the following equation (5)In (5), Rmin is the minimum cluster size and is considered as parameters of protocol, dBSmin is the distance between the nearest node and the BS and dBSmax is the distance between farthest node and BS. Then, each node determines a value amount using a value function in order to be selected as volunteer cluster head (6)In (6), α, β and γ are constant weights between zero and one where their sum is equal to one and are the same and adjustable for all nodes. Ndeg is the number of neighbouring nodes with RCH radius, MSDdeg is mean square of distance between neighbouring nodes RCH radius and dBS is the distance between each node and BS. It must be noted that expected value sets the total number of volunteer cluster heads over a certain amount, so the modified amount of FCH-value is obtained for each node, then, each node notices other nodes on modified numerical value with a message. Now, each node generates a random value between zero and one. If this value is less than its corrected and normalised value of FCH-value, then the node considers itself as candidate cluster head node. Each candidate cluster head node competes with other candidate cluster heads based on criteria of RCH radius and residual energy. Volunteers with more residual energy win in this competition and consider themselves as cluster head with a message containing their ID and broadcast code and announce network nodes their cluster head status and any non-cluster head node determines the nearest cluster head based on received signal strength. Fig. 2 describes cluster head selection flowchart for node i. Fig. 2Open in figure viewerPowerPoint Describes cluster head selection flowchart for node i 3.2.2 Step 2: Leader node selection Prepensely, the intra-cluster communication is an energy cluster depend on factors such as: (i) cluster size (it means the cluster zone's area) when the size of cluster is huge, so because of the relation between energy consumption in node radio with distance, there would be more expensive communications in the cluster and it means the intra-cluster energy increase. (ii) Centrality: if the receiver node gets closer to the central cluster, the second power average distance with it decreases and in this case the intra-cluster energy becomes small. Other factors like nodes' density also affect the intra-cluster energy. The intended standards cause not to choose nodes, which are in unsuitable situations as leader nodes. In this step, each non-cluster head node determines a value in order to be selected as volunteer leader node (7)In (7), Mdeg is the number of neighbouring nodes within leader radius, KLN is the number of nodes that are volunteer for leader node within leader radius. η and λ are constant weights between zero and one so that their sum is equal to one and are same and adjustable for all nodes. Now, each leader candidate node competes with other volunteers based on leader radius and its residual energy like previous step and volunteer with more energy is selected as leader node among them and announces its leadership with a message which contains its own ID and cluster head ID. Fig. 3 describes the leader node selection flowchart for node i. Fig. 3Open in figure viewerPowerPoint Describes leader node selection flowchart for node i 3.2.3 Step 3: Next hop selection In this step, the next hop is determined for each node in order to send data as shown in Fig. 4 If a cluster has no leader node based on lines 1–3, then each ordinary node will consider its cluster as next hop. According to lines 4–8, ordinary node selects the nearest node among cluster head nodes and leader node or nodes. According to lines 9 and 10, each leader node considers its cluster head as the next hop. According to lines 11 and 12, each cluster head node selects the nearest cluster head as its next hop in a circle with a smaller radius and closer to BS in order to send its data. After this step, each cluster head node sends a message in order to inform other leader nodes and ordinary nodes on TDMA program. Fig. 4Open in figure viewerPowerPoint Next hop selection algorithm 3.3 Steady-state phase At this phase, each cluster head node or leader node aggregates received data from ordinary nodes or other leader nodes with its own data. Then, cluster head nodes send data to BS with a multi-hop view. 4 Simulation results In this paper, we have focused on energy efficiency. We have used lifetime criteria in order to evaluate the protocol in terms of energy efficiency. There are different definitions for lifetime in the literature. In periodical aggregation applications, the appropriate definition of lifetime is a time when network starts for work to a round when the first node in network discharges energy and is called stability period. In addition, we evaluate proposed protocol with three protocols of LEACH, TCAC and a balanced clustering algorithm with distributed self-organisation for wireless sensor networks (DSBCA) based on other important criteria such as residual energy at the end of each round, network consumed energy, number of packets received by BS, instability period and percentage of residual energy after the death of the first node in order to examine and explain the proposed protocol accurately. All models and simulations in this section are prepared and conducted using MATLAB software. According to the comments, the technique proposed in this paper is scalable and can improve energy efficiency in networks with different sizes. It is worth to note that since network model is ad hoc, and arrangement and the position of nodes is completely random therefore, each simulation is repeated in 50 different arrangements in order to obtain accurate results, and the results are averaged. It must be mentioned that parameter values of LEACH, TCAC and DSBCA protocols are identical to values of [19, 27, 33]. Table 1 describes the details of simulation parameters. Table