JCC  Vol.8 No.11 , November 2020
A New Energy-Efficient and Reliable Protocol for Stochastic WSNs Based on Back-Pressure and Entropy of Residual Energy
Abstract: In this paper, a new energy-efficient and reliable routing protocol is introduced for WSNs including a stochastic traffic generation model and a wakeup/sleep mechanism. Our objective is to improve the longevity of the WSNs by energy balancing but providing reliable packet transfer to the Base Station at the same time. The proposed protocol is based on the principle of the back-pressure method and besides the difference of backlogs, in order to optimize energy consumption, we use a cost function related to an entropy like function defined over the residual energies of the nodes. In the case of two-hop routing the optimal relay node is selected as the one which has maximum backlog difference and keeps the distribution of residual energy as close to uniform as possible where the uniformity is measured by the change of the entropy of the residual energy of the nodes. The protocol assumes Rayleigh fading model. Simulation results show that the proposed algorithm significantly improves the performance of traditional back-pressure protocol with respect to energy efficiency, E2E delay and throughput, respectively.

1. Introduction

Wireless sensors networks (WSNs) consist of small, cheap, and low powered nodes, each of them having a wireless radio transceiver, a limited processing unit, and application-specific sensors [1]. The nodes collect data from the sensing field and transmit the data in the form of packets. The packets are generated either in deterministic fashion or in a stochastic fashion. Nodes forward packets to the base station directly (single-hop scheme) or by relaying each other (multi-hop scheme). WSNs are used in smart IoT systems, intelligent transportation, biomedical systems, and any application concerning large-scale data acquisition.

Designing and operating of WSN should respect some constraints such as limited resources, limited energy, reliability of communications, and dynamic topology. Despite any limitations, the performance of any system should satisfy the minimum level of services and requirements, which are known as Quality-of-service (QoS); in the case of WSN, QoSs include reliability, energy efficiency, security, accuracy, delay and-so-forth.

The energy efficiency is a critical issue in WSNs because the nodes operate by batteries, which are difficult to be replaced, and the data is transmitted to the Base Station via unreliable radio channels where fading and noise corrupt them. Corrupted channels make the packet loss ratio high where the lost data means wasted energy. Several techniques are used to improve the energy efficiency of WSNs; they cover different aspects of the networking process such as radio optimizations, energy-efficient routing, data reduction, and battery repletion [2].

In WSNs using deterministic communication paradigm, nodes transmit the data according to a predefined schedule, where WSNs use stochastic communication paradigm; nodes randomly transmit data, such a scheme of data transmission used as an energy-efficient technique known as the ON-OFF (sleep/wake-up) scheme, likewise; some WSN stochastic applications require this paradigm such as surveillance and event-based applications. In the case of stochastic WSN, MAC manages to build in queues—like where the data is held before transmission.

Queueing theory is widely used in the design and analysis of WSNs [3]. In [4] queuing models are used to characterize end-to-end delays in WSNs. In [5] it is also used to detect and control the congestion of WSNs. Queuing theory is used in [6] to improve and analyze the energy efficiency of WSNs by controlling ON/OF schemes. Paper [7] uses queueing theory to improve the reliability by adjusting the arrival rate and service rate with queue length to prevent congestion which causes packet loss because of overflowing queues.

There are many routing protocols based on the Back-Pressure algorithm [8], where the WSNs are considered as a network of queues. The routing and forwarding decisions are made independently for each packet by computing the back-pressure weight for each outgoing link. The back-pressure weight is a function of the difference between the backlogs of both ends of the link, estimated link rate, and Link cost (Penalty) function, respectively.

In this paper, we propose (BPEEBP), a new energy-efficient and reliable routing algorithm which is based on back-pressure and the entropy of the residual energy. Besides the difference of the backlog of both ends of the link, BPEEBP uses a cost function depending on the change of entropy of the residual energy of the nodes, the higher this entropy is, the closer we get to uniform energy distribution among the nodes.

We assume that the nodes generate packets randomly, subject to a stochastic model, and their activities are controlled by an ON/OFF scheme. As far as the radio propagation is concerned we assume the Rayleigh fading model. BPEEBP aims to increase longevity and guaranteeing a given level of reliability at the same time. The proposed protocol improves energy efficiency concerning the total consumed energy and enforcing uniform energy distribution among the nodes; thus eliminating the formation of the bottleneck nodes. Also, it is aware of influential issues such as the limited storage space of the node, end-to-end delay, and congestion occurrence.

The remainder of this paper is divided into six sections:

· In Section 2, we give an overview of the related work.

· In Section 3, we introduce our model for the WSN.

· In Section 4, a description of the routing protocol.

· In Section 5, we give the numerical results of a detailed performance analysis of the algorithms where their performances are compared with other protocols.

· In Section 6, we draw some conclusions and give remarks on the future work.

2. Related Work

The Back Pressure protocol developed to achieve energy efficiency and taking the data traffic into account was first proposed by L. Tassiulas and A. Ephremides in 1990. Some Back-pressure based protocols used in WSNs are centralized, where the routing and scheduling decisions are taken by the Base Station [9]. The shortest-path-aided back-pressure algorithm (SBA) introduced in [10] is a centralized protocol and it aims to reduce end-to-end (E2E) delay, not only the backlog difference and estimated link rate are taken into consideration, but also the number of hops from the source node to the destination.

Back-pressure Based Collection Protocol (BCP) is a distributed back-pressure based protocol [11], routing, and scheduling decisions are taken by the node itself, besides backlog, it uses the expected number of transmission (EXT) as a penalty (cost) function. BCP uses LIFO (last in, first out) queue structure to reduce E2E delay, it uses the floating-queue idea to solve the problem of the packets arrived early, these packets may be trapped at some relay nodes, by floating queues, they are discarded and moved to a virtual queue [11].

In traditional back-pressure algorithms, a small backlog difference may cause a selection of long paths but Packet-by-Packet Adaptive Routing and scheduling algorithm (PARN) addresses this issue [12]. An M-back-pressure mechanism is introduced where the link is scheduled to be active only if the difference between the length of the queues of the source node and the destination node is larger than (M > 1). But, this may increase E2E delay in case of light and moderate traffic. To solve this problem and to reduce queues complexity (i.e. the number of queues in each node), adaptive routing is proposed, where each node has an actual queue for each neighbor, and shadow queues for each node in the networks, shadow queues are just counters. The back-pressure of the links depends on the difference of the counters; packets are served from the real queue at the link in a first-in, first-out method (FIFO).

The protocols mentioned above aim at improving the E2E delay and reducing the complexity, but gradient assisted energy-efficient back-pressure scheduling algorithm (GRAPE) seeks to improve the energy efficiency of WSNs [13]. In GRAPE the weight of the link is determined on the basis of the differential backlogs for the source and the destination, the residual energy statues of the destination, and their gradient difference, where the gradient is the hop count between the node and the base station. In GRAPE nodes forward the packet to the neighbor which has higher residual energy and closer to the base station. Multi-factors back-pressure scheduling algorithm (MFBS) presented in [14] uses the same idea, but it takes the distance between nodes into account instead of the number of hops. But residual energy and the distance from the base station do not guarantee the absence of a bottleneck node, because they do not ensure a uniform distribution of residual energy.

Other researches improve the performance of backpressure by combing it with other techniques. NCBPR [15] combines backpressure with network coding; it uses network coding to reduce congestion, redundant data, where a backpressure algorithm is used for routing scheduling to guarantee load balancing among the nodes. BRPL [16] conglomerates backpressure algorithm and RPL (routing protocol for low-power and lossy networks), it switches between them based on the status of the network, routing decisions are taken depending on both gradients of the backlogs (related to back pressure); switching between them solve the problem of the poor performance of RPL in terms of network dynamics and throughput. Such algorithms are used in large scale IoT, they are complicated and difficult to be implemented in traditional WSNs.

In this paper we are going to combine the backpressure protocol with energy balancing to prolong the life span of WSNs, energy balancing will be controlled by entropy like measure and predefined reliability level.

3. System Model

The proposed system is a WSN contains a number of nodes distributed randomly in the sensing field. The network is symbolized as a graph G ( V ; E ; D ) , where set V states the nodes V = | N | , while set E denotes the edges and D i j are the distances between the nodes. The energy needed to transmit a packet from node i to node j is calculated based on the Rayleigh fading model [1],

g i j = d i j α Θ σ Z 2 ln ( P i j ) . (1)


· d i j is the distance between node i and j.

· α is the large-scale path loss exponent (it is usually 2 - 6).

· Z 2 refers to the power of noise.

· Θ is the modulation and coding scheme constant.

· P i j is the probability of successful packet transfer between node i and j.

P i j characterises the reliability constraint, it depends on the predefined packet loss rate ( ε ), and the number of hops between the source and the BS. The

overall P i , r 1 , , B S is supposed to fulfill j = 0 m P l j l j + 1 = 1 ε , where m is the number

of relay nodes. Since the back-pressure algorithm defines the rout and the schedule for a single hop, then P i j = 1 ε .

The state of the energy in WSN at time instant t is described by an energy state vector c ( t ) = c 1 ( t ) , , c i , , c N ( t ) where c i ( t ) is the residual energy in node i at time instant t. We assume that the preliminary energy state at time instant 0 is uniform, i.e. c i ( 0 ) = A , where i = 1 , 2 , , N .

Our algorithm is a chain based algorithm; the base station constructs a set of chains cover all the nodes of WSN. The chains are constructed by the Dijkstra shortest path algorithm, and the BS has full vision of distance matrix between nodes, the distance between two nodes represents the weight of the corresponding edge in the graph of the network. The path from the source node i to the BS is described as a set of m relay nodes participating in the packet transfer, i B S = { i , r 1 , , r m , B S } .

WSN also represented as an open network of M\M\1 queues; each queue has two types of arrivals. First, external arrivals follow Poisson process at a rate of γ i ; they represent the generated packets by the node, the vector γ represents the generation rate of the chain. Second, internal arrivals represent the received packets from other nodes, where λ i is the total arrival rate of both external and external arrivals, the vector λ represents the mean arrival rate of the chain. The service rate μ i of the queue represents the transmission rate of the node i, as shown in Figure 1.

The queues length of the network at time instant t is represented as a queue length state vector q ( t ) = q 1 ( t ) , , q i ( t ) , , q N ( t ) , where q i ( t ) is the queue length of node i at time instant t. We assume that the nodes are symmetrical, they have the same generation and service rate. As the case in most of WSNs, we assume that the network is controlled by a wake-up scheme to achieve better energy efficiency. We selected scheduled rendezvous wakeup mechanisms; all

Figure 1. The node as a queue.

the nodes wake up together for the same period, they also return to sleep mode together for the same period too. This mechanism is used in IEEE 802.11 power saving mode (PSM), it is appropriate for a single hop network and when all the nodes are accessible for each other [17].

Theoretically, based on Jackson networks [18] [19], the total mean packet arrival rate to the queue of node i is:

λ i = γ i + j = 1 c λ j (2)

λ = γ ( I R ) 1 (3)

where I is the identity matrix, R is routing matrix, where R i j is the probability that a packet serviced by node i is sent to node j, and c is the length of the chain. If the average sleep period is β and α is the average wake up period, then the actual mean of arrival and service rates are

' λ i = β β + α λ i (4)

' μ i = β β + α μ i (5)

4. Routing with Energy Balancing

The Back-pressure algorithm was introduced in [8], it deals with both routing and scheduling (Forwarding) processes, in routing process the most effective path is defined, but in the scheduling process, the decision to activate the proposed route is taken. At time slot (t), Back-pressure algorithm calculates the weight of all possible outgoing links; it defines the link with maximum weight at time slot (t) as:

ω i , j ( t ) = m a x ( Δ Q i , j V θ i , j ) (6)

where Δ Q i , j is the differential backlog for both ends of the link, θ i , j is the cost function and V is a constant used to normalize the cost function, the tie is broken arbitrarily.

The link with maximum weight is activated under schedule π ( t ) based on the following optimization function:

π ( t ) = arg max π l ( ω i , j ( t ) r ¯ i . j ) (7)

where r ¯ i , j is the expected link rate and l is the set of all feasible schedules subject to link interference model, and ω i , j > 0 [11] [12].

There are attractive advantages of back-pressure algorithms such as, the optimality of the network throughput (the rate at which the base station receives the packets.), simplicity, adaptive resource allocation, and supporting of stateless and agile routing and scheduling [9]. But also there are some disadvantages such as, complexity (maintaining a large number of queues) and it may cause high E2E delay. A lot of researches have been carried out to improve the performance of the back-pressure algorithm in different network environments [12].

In this paper we extend the cost function of back pressure algorithm with a term depending on how uniform is the distribution of the residual energies of the node.

In our previous work [20], we showed that optimal path is the one over which a packet is sent to the BS where the minimum residual energy is maximum subject to the constraint that the packet will reach the BS successfully with a given probability, which means that the distribution of the residual energy falls close to uniform.

Thus, the path over which the packet is forwarded to the BS (denoted by ) is optimal if:

: max min i c i ( t + 1 ) (8)

subject to the constraint P i j = 1 ε .

We also introduced an entropy-like measure on the energy distribution, by which we can measure the uniformity of residual energy distribution. At instant t = 0 , all the nodes have the same level of residual energy, so, the entropy is maximum. We have to keep it as maximum as possible to get closer to uniform residual energy distribution, which means that we need the minimum change in the entropy. The entropy of the current energy distribution is:

H ( c ¯ ) = i = 1 N c i ( t ) j = 1 N c j ( t ) log j = 1 N c j ( k ) c i ( t ) . (9)

So, the gradient of the entropy is:

V ¯ = H ( c ¯ ) = H c 1 , H c 2 , , H c N . (10)

By solving the above equation, we can calculate the gradient of the entropy of the residual energy distribution on the relay nodes and the reset of nodes of the path, so, the changes of the entropy is [20]:

Δ H = V ¯ T Δ c ¯ ( t ) . (11)

where V is the gradient of the entropy, and Δ c i is: c i ( t + 1 ) c i ( t ) and c i ( t + 1 ) is calculated based on (1) and subject to predefined probability of successful packet transmission from node i to node j, P i j = 1 ε .

c i j ( t + 1 ) = c i j ( t ) ( d i j Θ σ Z 2 l n ( P i j ) ) (12)

In our algorithm for WSNs with stochastic packet generation, we propose back-pressure based algorithm, but the weight of the link will depend on the differential backlog for both ends of the link, and the change of the entropy of residual energy of the chain. The cost function θ i , j in (6) will be the change of the entropy δ H , the weight of the link increases as the differential backlog increases and the change of the entropy decreases, Equation (6) becomes:

ω i , j ( t ) = max ( Δ Q i , j ) min ( Δ H i , j ) (13)

At the end of each ON, the base station broadcast the vector of network energy status and the vector of queue lengths status, each node uses this information to decide its target. PBEEPB allows multiple instantaneous transmissions. Greedy LQF (longest queue’s length first) algorithm is used to schedule transmission links. Since each node has just one transceiver, receivers of higher priority transmitters (higher LQ) will be allocated as interfered and removed from available links. All the links have the same link weight.

5. Simulation and Performance Evaluation

We evaluate the performance of the proposed algorithm by comparing with traditional back-pressure and general performance of GRAPE. We used Matlab and Simulink (simevents) to model and simulate our system; each simulation lasts for 1000 units of time. The simulated network consists of 100 symmetrical nodes which are deployed randomly onto a grid of 100 × 100 according to the 2D normal distribution; the base station is selected randomly, a set of short paths are formed by the Dijkstra shortest path algorithm.

The transmission energy will be calculated according to the Rayleigh fading model (3) under the following assumptions:

· Energy needed by the electronics will be neglecting Conditioning.

· All the nodes have 500 J initial energy.

· Θ = 10 6 .

· σ Z 2 = 0.1 .

· α = 2 .

· P i j is calculated based on reliability ( 1 ϵ ).

· Lifespan is the number of packets transmitted over the chain until the first node goes flat.

· The base station is accessible directly by all the node.

· The base station appears as a zero-length queue.

· Nodes generate packet stochastically with the same average rates γ follow a Poisson distribution with a mean of γ .

· All the nodes have the same service rate and the same link capacity.

We use the variance of consumed energy to express the uniformity of the distribution of consumed energy. Figure 2 shows the variance of different chain lengths, 5, 6, 7, 8 and 9. it shows that PBEEBP has lower variance than traditional back-pressure for all lengths of the chains (5, 6, 7, 8, 9). Figure 3 shows the total consumed energy by the nodes during the simulation period. The one can note that all the nodes consumed less energy when using PBEEPB in about 9%

In the second experiment, we study the effect of the utilization of nodes ( ρ i = γ i / μ i ), Figure 4 shows the relationship between the variance and the utilization. Figure 5 shows the relation between the total consumed energy by the nodes of the chain and different the utilization values 0 - 0.9, both figures show better performance for PBEEPB over the traditional back-pressure.

Figure 2. The variance of consumed energy vs length of the chain.

Figure 3. Total consumed energy vs length of the chain.

Figure 4. Total consumed energy vs utilization ρ .

Figure 6 shows that we still have a high packet delivery rate (throughput), there is about 16% enhancement in comparison with traditional pack-pressure by using PBEEPB. The figure shows the relation between the packet arrival rate at the base station and packet generation rate at the nodes.

Figure 7 shows that in the case of PBEEBP, better uniformity of distribution of consumed energy and better load balance among the nodes yields longer lifespan. We studied the lifespan in case of the traditional back-pressure algorithm and PBEEBP regarding different utilization values ρ (0.10.9); the figure shows that we have a significantly longer lifespan for all tested cases in about 50% in average.

The average of E2E delay has been enhanced in an average of 15% by using PBEEPB as shown in Figure 8.

Figure 5. Total consumed energy vs utilization ρ .

Figure 6. Throughput vs packet generation rate γ .

Figure 7. Lifespan vs utilization ρ .

Figure 8. Average delay time vs utilization ρ .

6. Conclusion

In this paper, we proposed a back-pressure-based protocol (BPEEBP). Proposed protocol maximizes the energy and traffic balance by minimizing the change of the entropy of the residual energy of the WSNs. It controls the distribution of the traffic and the residual energy subject to a predefined reliability constraint. We compared the performance of BPEEBP to the performance of traditional back-pressure algorithm and GRAPE. BPEEBP shows better performance regarding energy efficiency, E2E delay, and throughput. This work assumes symmetrical nodes regarding packet generation and service rates. In our next work, we will study the improvement of the cost function in case of unsymmetrical nodes.

Cite this paper: Almazaideh, M. and Levendovszky, J. (2020) A New Energy-Efficient and Reliable Protocol for Stochastic WSNs Based on Back-Pressure and Entropy of Residual Energy. Journal of Computer and Communications, 8, 1-13. doi: 10.4236/jcc.2020.811001.

[1]   Levendovszky, J., et al. (2008) Energy Balancing by Combinatorial Optimization for Wireless Sensor Networks. WSEAS Transactions on Communications, 7, 27-32.

[2]   Rault, T., Bouabdallah, A. and Challal, Y. (2014) Energy Efficiency in Wireless Sensor Networks: A Top-Down Survey. Computer Networks, 67, 104-122.

[3]   Lall, S., Alfa, A.S. and Maharaj, B.T. (2016) The Role of Queueing Theory in the Design and Analysis of Wireless Sensor Networks: An Insight. 2016 IEEE 14th International Conference on Industrial Informatics (INDIN), Poitiers, 18-21 July 2016, 1191-1194.

[4]   Wu, G., et al. (2011) Queueing Theory-Based Path Delay Analysis of Wireless Sensor Networks. Advances in Electrical and Computer Engineering, 11, 3-8.

[5]   Liang, L.L., Gao, D.Y. and Leung, V.C.M. (2014) Queuebased Congestion Detection and Multistage Rate Control in Event-Driven Wireless Sensor Net-Works. Wireless Communications and Mobile Computing, 14, 818-830.

[6]   Byun, H. and Yu, J. (2013) Adaptive Duty Cycle Control with Queue Management in Wireless Sensor Networks. IEEE Transactions on Mobile Computing, 12, 1214-1224.

[7]   Martal, M., Busanelli, S. and Ferrari, G. (2009) Markov Chain-Based Performance Analysis of Multi-Hop IEEE 802.15.4 Wireless Net-Works. Performance Evaluation, 66, 722-741.

[8]   Tassiulas, L. and Ephremides, A. (1992) Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum throughput in Multihop Radio Networks. IEEE Transactions on Automatic Control, 37, 1936-1948.

[9]   Jiao, Z.Z., et al. (2016) Backpressure-Based Routing and Scheduling Protocols for Wireless Multihop Networks: A Survey. IEEE Wireless Communications, 23, 102-110.

[10]   Ying, L., et al. (2011) On Combining Shortest-Path and Back-Pressure Routing over Multihop Wireless Networks. IEEE/ACM Transactions on Networking (TON), 19, 841-854.

[11]   Moeller, S., et al. (2010) Routing without Routes: The Backpressure Collection Protocol. Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks, Stockholm, 12-16 April 2010, 279-290.

[12]   Athanasopoulou, E., Bui, L.X., Ji, T., Srikant, R. and Stolyar, A. (2013) Back-Pressure-Based Packet-by-Packet Adaptive Routing in Communication Networks. IEEE/ACM Transactions on Networking, 21, 244-257.

[13]   Jiao, Z.Z., et al. (2015) A Gradient-Assisted Energy-Efficient Backpressure Scheduling Algorithm for Wireless Sensor Networks. International Journal of Distributed Sensor Networks, 11, Article ID: 460506.

[14]   Alassery, F. (2016) A New Link Weight Factor in Backpressure Scheduling Algorithm for Energy-Efficient Design of Smart Wireless Sensor Networks. Smart Energy Grid Engineering (SEGE), Toronto, 21-24 August 2016.

[15]   Patriciello, N., et al. (2019) Towards Backpressure Routing in Wireless Mesh Backhauls for Dense LTE Deployments. 2019 IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), Barcelona, 21-23 October 2019, 282-287.

[16]   Tahir, Y., Yang, S. and McCann, J. (2018) BRPL: Backpressure RPL for High-Throughput and Mobile IoTs. IEEE Transactions on Mobile Computing, 17, 29-43.

[17]   Zheng, R., Hou, J.C. and Sha, L. (2003) Asynchronous Wakeup for Ad Hoc Networks. Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 1 June 2003, 35-45.

[18]   Bhatia, H., et al. (2008) A Queuing-Theoretic Framework for Modelling and Analysis of Mobility in WSNs. Proceedings of the 8th Workshop on Performance Metrics for Intelligent Systems, 19 August 2008, 248-253.

[19]   Ali, M.K.M. and Gu, H. (2009) A Performance Modelling of Wireless Sensor Networks as a Queueing Network with on and off Servers. Journal of Communications and Networks, 11, 406-415.

[20]   Almazaideh, M. and Levendovszky, J. (2020) Novel Reliable and Energy-Efficient Routing Protocols for Wireless Sensor Networks. Journal of Sensor and Actuator Networks, 9, 5.