A clustered routing protocol based on energy and link quality in WSNs①

Shang Xinna (商新娜), Chen Zhibo, Sun Guodong, Li Juhu

(*School of Information Science & Technology, Beijing Forestry University, Beijing 100083, P.R.China) (**College of Information Technology, Beijing Union University, Beijing 100101, P.R.China)

A clustered routing protocol based on energy and link quality in WSNs①

Shang Xinna (商新娜)***, Chen Zhibo②*, Sun Guodong*, Li Juhu*

(*School of Information Science & Technology, Beijing Forestry University, Beijing 100083, P.R.China) (**College of Information Technology, Beijing Union University, Beijing 100101, P.R.China)

Influenced by the environment and nodes status, the quality of link is not always stable in actual wireless sensor networks (WSNs). Poor links result in retransmissions and more energy consumption. So link quality is an important issue in the design of routing protocol which is not considered in most traditional clustered routing protocols. A based on energy and link quality’s routing protocol (EQRP) is proposed to optimize the clustering mechanism which takes into account energy balance and link quality factors. EQRP takes the advantage of high quality links to increase success rate of single communication and reduce the cost of communication. Simulation shows that, compared with traditional clustered protocol, EQRP can perform 40% better, in terms of life cycle of the whole network.

clustered routing protocol， link quality， energy balance

0 Introduction

Wireless sensor networks (WSNs) have a wide variety of applications in recent years. Most of the WSNs are deployed outdoors for scientific investigation, environment monitor, military affairs and so on. The batteries of nodes are finite and are difficult to be charged in such conditions. So saving energy is important in WSNs. There are three parts of consuming energy of nodes: communication, data processing and monitoring. Communication is the largest part in consuming energy. In WSNs, influenced by the environment and nodes status, the quality of link between two nodes is not always stable . If a node can not transmit data packets to its next node, it has to retransmit the data packet again and more energy will be consumed in communication part. How to improve the success rate of single transmission and decrease the communication count is one of the key considerations in routing design. A clustered routing protocol EQRP is designed which considers the energy-aware and link-quality in optimizing the cluster heads in WSNs. EQRP takes the advantage of high quality link to increase the success rate of single communication and reduce the cost of communication.

1 Related work

There are two main types of routing protocols in WSNs: flat routing protocol and hierarchical routing protocol. Nodes are equal and have same function in flat routing protocol such as Flooding, Spin and DD protocol. These protocols are fit for the networks with small number nodes. LEACH,TEEN,APTEEN and HEED are typical hierarchical routing protocols which divide the nodes into cluster head nodes and common nodes. The common nodes transmit data packets to cluster head nodes which then integrate the data and transmit it to sink node. These protocols show good performance in large scale networks. Most of WSNs have large range and hierarchical routing protocols have more notice than flat protocol. Although some questions of network performance and data transmission are solved partly in hierarchical routing protocols, other issues such as energy imbalance, uneven distribution of cluster head and transmission instability still exist.

Some improved optimization protocols are proposed in recent years. Ref.[1] puts forward a protocol named LEACH-ED. The main idea is to consider residual energy and distance between cluster-head nodes. But it does not limit the node count in clusters. Ref.[2] introduces LEACH-NOC which clusters the network and then chooses cluster head nodes within clusters by considering residual energy and position of nodes. LEACH-NOC optimizes the choosing of cluster head nodes within clusters, but the problem of the uniform distribution of the network is not solved. Routing protocol based on the ant colony algorithm is proposed in Ref.[3]. EETCA in Ref.[4] tried to avoid partial nodes evergy dissipation too fast. In Ref.[5], routing algorithm based on topology optimization control selects cluster head nodes by the weighted probability method to achieve energy balance between nodes. Link quality was considered in Refs[6,7]. A hierarchical routing protocol named L2PR in Ref.[6] considers the link quality into routing. In L2PR, nodes can forward data from multiple paths which can reach the robustness and balance of network. The drawback is that each node has to calculate and save the weight of different paths, since it can take a multi-forwarding mechanism as the source node.

All these routing protocols are suitable for some WSNs. No routing protocol can be perfect and be applied to all applications. Most of proposed algorithms do not consider the quality of link between nodes which leads to retransmission and consumption of energy. In this work, the unreliable link quality and energy saving in clustered routing protocol are focused.

2 Network model and assumption

2.1 Network model and assumption

Network with following characteristics is assumed.

(1) the network has N sensor nodes and each node has distinctive identities from 1 to n.

(2) All the nodes with limited energy do not move in network and have no position sensing capability.

(3) Sink node has fixed location and infinite energy.

(4) The network is sensitive to the incident and needs to ensure the success rate of the event monitoring.

(5)The nodes can collect monitoring data periodically.

The items from (1) to (3) are common characteristics of most WSNs. (5) indicates the special requirements in success rate of data forwarding.

2.2 Energy consumption model

In wireless sensor network, energy consumption is relatively small in addition to the energy consumed by the transmitting and receiving packets[8,9]. So most of the routing protocols only consider the energy consumption of the node transmitting packets (ETX) and receiving packets (ERX). When one node transmits k bit data to another node with distance d, ETXand ERXare calculated by

(1)

ERX(k)=ERX-elec(k)=kEelec

(2)

where d0is the threshold of distance. Eelecdenotes energy consumption in receiving and transmitting 1bit data. εfsand εmpdenote the power amplification factor in two energy consumptions modtively. EDAdenotes unit data fusion energy consumption. d0can be computed by

The energy consumption of node i is

E=ETX(k,d)+ERX(k)

(3)

2.3 Clustering mechanism in LEACH

LEACH[10]protocol is a typical clustering routing protocol, for which common nodes send data packets to their cluster head nodes, and then the cluster head nodes forward it to the sink node. The basic idea of the algorithm is to select the cluster head nodes randomly in the rounds. The energy load of the whole network is assigned to each sensor node, so as to reduce the network energy consumption and improve overall survival time. Every node generates a random number between 0 and 1. If the random number is greater than threshold T(n), the node will be cluster head. T(n) is calculated by

(4)

where p denotes the percentage of the cluster head nodes in total number of nodes, r is the round number of reselecting the cluster head nodes, G denotes the node set which have not been cluster head in recent 1/p rounds. The probability of the nodes becoming cluster head is related to the number of nodes, the proportion of the cluster head and the number of rounds.

The design of T(n) can ensure that each node can be a cluster head in a continuous 1/p round which leads to balancing the energy consumption. In the beginning of every round, the cluster head nodes broadcast message. Each common node may receive messages from many cluster head nodes. Then it chooses the nearest cluster head nodes and joins them into its cluster. This mechanism has the advantages of simple calculation, less interactive information and balanced energy consumption.

3 EQRP design

EQRP algorithm is the optimized enhanced algorithm based on the LEACH protocol. In LEACH, nodes become the cluster head randomly without consideration of their status. When a node with low energy and poor link quality becomes a cluster head, it will consume much energy and lead to faster death. EQRP algorithm takes into account the status of the nodes, depending on the integrated assessment of residual energy and link quality to optimize clustering of the nodes, balance the survival period of each node and greatly improve the life of the entire network.

3.1 Computation of the link quality factor

In actual wireless networks, nodes may not transmit data successfully at first time influenced by the environment and working status. Failure of the data transmission leads to retransmission which consumes more energy. If the nodes with stable link quality have more chance to be cluster head, more energy is saved by less retransmission[11,12].

The communication work of cluster head nodes is divided into two parts. one is responsible for communicating with common nodes within the cluster. The better link quality the cluster-head has, the less energy the cluster consumes. The second part is communication with sink nodes. Because the cluster head is responsible for forwarding all the data packets from nodes within the cluster, the amount of data transmitted is far greater than that within the cluster. So the link quality between sink nodes and cluster head is much greater than the impact of the link between the cluster head and the nodes within cluster. In practical applications, it is needed to make a weight of the link quality of every node to sink node, and then calculate the average link quality.

Let pijdenote the link quality between node i and node j and pij=pji. The expected transmission count(ETX) can be calculated as follows:

ETXij=1/pij

(5)

The link quality factor can be calculated as follows:

(6)

where pnis the average link quality factor of node n, pniis the link quality between node n to alive node i, and pnsis link quality between node n and sink node. λ is the weight of link quality to sink node. The value of λ depends on the number of cluster members and the degree of data fusion. Without data fusion effects, cluster heads will forward all the data packets received from cluster members to sink node. λ can be determined as the average number of members in the clusters. By introducing the average link quality of node n as the weight factor, the probability of a good link quality node becomes larger and the probability of data transmission is reduced. The data transmission of the whole network is reduced and the energy of the whole network is saved.

To illustrate pn, let us consider a scenario where 10 nodes are in a cluster with various link quality and λ=10 in Table 1.

Table 1 Average link quality with 10 nodes and λ=10

In this scenario, if the effect of other clustering factors is excluded and only the link quality is considered, node 9 whose average link quality is 0.91 should be the cluster head. Thus the expected transmission count ETX9=1/0.91=1.099. If node 6 with pn=0.80 becomes the cluster head, ETX4=1/0.80=1.25. Compared these two choices, percentage of energy savings is 13.7% ((1.25-1.099)/1.099×100%) .

3.2 Residual energy factor

In some improved clustering algorithms, the node residual energy is considered by using the ratio of residual energy and the initial energy of node as the weight to influence the clustering algorithm. But this weight will become smaller and smaller with the residual energy becomes less and less, which leads to the cluster threshold smaller[13,14]. After a certain time, total number of the cluster head nodes in whole network is not enough, because of too small threshold. In order to cope with this situation, improvement on the residual energy factor is made by adding a correction factor as

(7)

where Enis the residual energy factor, EnInitEnergyis the initial energy of node, EnLeftEnergyis the residual energy of node, rsdenotes the rounds in which node n is not continuously elected as cluster head. Once the node n is elected, rsis set to 0, p is the percentage of the cluster head in total number of nodes. The above equation illustrates that the more energy one node has, the more chance it can be cluster head by the ratio of residual energy and the initial energy.

3.3 Comprehensive algorithm

Based on the analysis of link quality factor and residual energy factor, the new clustering algorithm, EQRP is proposed which considers residual energy and link quality between nodes and their surrounding nodes. The improved clustering threshold formula is

(8)

where wnis the weight to reflect node n becomes cluster head. It is calculated by follows:

wn=En×ω+pn(1-ω)

(9)

where ω is the the proportion of the remaining energy factor. Weight w is a constant value to balance the residual energy and link quality with life cycle and stability.

4 Evaluation

100 wireless sensor nodes are placed randomly in a 100m×100m area. All the parameters are set in Table 2.

Table 2 Network parameters

4.1 Network description

To get accurate result, the same node distribution graph, the same sensor data sampling values and the same node link quality are used in every simulation for EQRP and LEACH. Once a cluster is established, it will keep stable for 10 hours. In this period, the node acquires data and sends data with an average interval of half an hour. The round number is noted in which the first node dies,10% nodes die, 50% nodes die and 90% nodes die. The remaining energy of the whole network and number of alive nodes after each round are noted too.

4.2 Performance evaluation indicators

(1) Network life cycle

From the beginning of the network runtime to the death of first node, this stage is known as the stability of the network runtime. The longer the stability of the network runtime is, the better performance the routing protocol has. So the death of first node is used as an indicator. The time from the deployment of the network to the failure of the network function caused by N nodes death is defined as the network life cycle.

The time of network function failure is related to the specific network. Generally the time of 10%, 50%, 90% death nodes are as the evaluation indicators.

(2) Network energy consumption

Network energy consumption is defined as the sum of the energy consumed by the network after a period of time. The energy consumption will be noted after every round to simplify comparison and be calculated as

(10)

where Ec(r) means the total energy consumption in r rounds. ECi(r) is the energy consumption of node i in r rounds.

(3) Energy balance

The energy consumption balance of the network is evaluated by energy variance which is calculated by the square of difference between the average value of the network energy and the single node’s energy. The smaller energy variance is, the better energy balance of the network is.

The average value of the network energy is defined as follows:

(11)

where Eavg(r) is the average network energy after r rounds. Ei(r) is the residual energy of node i after r rounds.

The energy variance is denoted as Esqr(r) and can be calculated as follows:

(12)

4.3 Simulation and discussion

(1) Network life cycle

Considering the retransmission by poor link quality, the comparison results of network life cycle are shown in Fig.1 and Fig.2.

Because of the consideration of link quality, the energy consumption of the whole network is relatively large due to retransmission, resulting that the occurrence time of the first death node is greatly advanced. It can be seen from Fig.1, all nodes’ death time is greatly delayed, and the life cycle of the whole network

Fig.1 Survival nodes number

Fig.2 Number of death nodes

is significantly improved. For example, the first death node occurs after 81 rounds in LEACH and 121 rounds in EQRP which has 40 rounds delay.

(2) Network energy consumption

Considering the link quality and comprehensive clustering algorithm, network energy consumption between LEACH and EQRP is shown as Fig.3.

(a)

(b) Fig.3 Comparison of energy consumption

As can be seen in Fig.3(a), the slope of the EQRP protocol is significantly less than the slope of the LEACH protocol, which shows that the energy consumption in EQRP is far slower than the LEACH protocol. In Fig.3(b), after 100 rounds of the network, the total energy consumption of the LEACH protocol is 19.68J and EQRP protocol is 12.57J which is reduced by 57%. In the first 400 rounds, the total energy consumption can also be reduced by 15%.

As the death nodes added, the number of survival nodes in LEACH protocol network is far less than the number in EQRP network. The advantage is that total energy consumption in EQRP protocol in the network is gradually reduced until the exhaustion of energy consumption of two networks.

(3) Energy balance

Considering the link quality and comprehensive clustering algorithm, network energy balance between LEACH and EQRP is shown in Fig.4.

Fig.4 Comparison of energy variance

In Fig.4, the horizontal coordinate indicates the network running time, the vertical axis means the energy variance value. As can be seen, the slope of the EQRP protocol is significantly less than that of the LEACH protocol, which indicates that the energy balance of the whole network is significantly better than that of the LEACH protocol.

5 Conclusion

This study introduces the clustering routing protocol EQPR which integrates link quality and residual energy factor as key metrics in clustering mechanism. The link quality factor makes the nodes with good link quality have more chances to be cluster head and the residual energy factor brings the energy balance of whole network. Simulations show that EQRP improves the life cycle and energy balance of the whole network. In the future, it is intended to extend this work into large scale WSNs and implement EQRP on real testbeds to evaluate its performance.

[1] Gu X P, Sun Y J, Qian J S. An improved clustering routing protocol for wireless sensor networks．Micro Electronics & computer,2009,26(3):34-37

[2] Zhang P， Xu Z F， Sun Y． New routing protocol on optimal number of clusters for wireless sensor network．Chinese Journal of Sensors and Actuators,2009,22(7):1013-1017

[3] Li Q， Zhang B H， Cui L G, et al． Immunizations on small worlds of tree-based wireless sensor networks． Chinese Physics B, 2012,21(5):1-9

[4] Jiang Y S， Li P， Ma C． An energy efficient topolopy control algorithm for wireless sensor networks．Transducer and Microsystem Technologics, 2014,33(2):146-149

[5] Hoon O， Han T D． A demand-based slot assignment algorithm for energy-aware reliable data transmission in wireless sensor networks． Wireless Networks,2012,18(5):523- 534

[6] Diallo C, Marot M, Becker M. Link quality and local load balancing routing mechanisms in Wireless Sensor Networks. In: Proceedings of the 6th Advanced International Conference on Telecommunications(AICT), Barcelona, Spain, 2010. 306-315

[7] Dimitrios J, Vergados, George I Stassinopoulos. Adaptive duty cycle control for optimal stochastic energy harvesting. Wireless Personal Communications,2013,68(1):201-212

[8] Li Q， Zhu Q X， Wang M W． Design of a distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks.Computer Communications, 2006,29(12):2230-2237

[9] Wang F, Liu J C. On reliable broadcast in low duty-cycle wireless sensor networks. IEEE Transactions on Mobile Computing, 2012,11(5):767-779

[10] Lindsey S， Raghavendra C，Krishna M． Data gathering algorithms in sensor networks using energy metrics． IEEE Transactions on Parallel and Distributed Systems,2011,13(9):924- 935

[11] Mao Y C， Wang J L，Wang K, et al． Hierarchical routing protocol based on link quality in wireless sensor network. Computer Science，2015,42(3):74-80

[12] Yuan Z W，Liang J J. Cumulative link quality routing algorithm research on WSN.Computer Engineering and Applications，2011,47(14):66-69

[13] Feng J， Wu C C. Multi-hop clustering routing algorithm for WSN based on energy consumption balance.Computer Engineering.2012,39(16):104-107

[14] Cao H Y， Yuan Y， Liu Z Q. Routing algorithm for WSNs based on residual energy of node and the maximum angle. Transducer and Microsystem Technologies, 2015,34(1):120-123

Shang Xinna, born in 1978. She is working toward the Ph.D degree at Beijing Forestry University. She received her B.S. and M.S. degree from China University of Petroleum in 2004 and 2001. Her research interests include the wireless sensor networks, data analysis and processing.

10.3772/j.issn.1006-6748.2017.01.012

①Supported by the National Natural Science Foundation of China (No. 61300180), Beijing Higher Education Young Elite Teacher Project (No. YETP1755), the Fundamental Research Funds for the Central Universities of China (No. TD2014-01), the Importation and Development of High-caliber Talents Project of Beijing Municipal Institutions (No. CIT&TCD201504039).

②To whom correspondence should be addressed. E-mail: zhibo@bjfu.edu.cn Received on Feb. 26， 2016