An Energy-Efficient CKN Algorithm for Duty-Cycled Wireless Sensor Networks

1. Introduction

Wireless sensor networks (WSNs) are normally powered by batteries with limited energy, which are difficult or impossible to be recharged or replaced. A common approach for saving the sensor nodes' energy is to select a subset of nodes to remain active/awake and let others go to sleep in a given epoch. Most of current literatures on sleep scheduling in WSNs are to achieve point coverage and/or node coverage problems [1]. Point coverage problem (also called spatial coverage) focuses on selecting a set of active nodes in an epoch so that every point of the deployment space is covered, while considering some optimization goals, for example, minimizing energy consumption [2], minimizing average event detection latency [3]. Node coverage problem (also called network coverage) focuses on choosing a set of active nodes, in which (1) they construct a connected backbone and (2) sleeping nodes are direct neighbors of at least one active node [4]. This node coverage problem is to ensure that any two nodes in the network can communicate with each other through the connected backbone.

The Connected K-Neighborhood (CKN) algorithm is a distributed sleep scheduling algorithm [1], which can reduce the number of active nodes efficiently. It keeps the network k-connected and optimizes the geographic routing performance. Supporting the geographic routing performance is not studied in any previous point coverage and node coverage researches. Although, the CKN algorithm performs well with the geographic routing protocols, the following questions are not addressed in paper [1]. (1) How frequently should the CKN algorithm be executed in the network so that it can really help to save energy, for each time executing the CKN algorithm also consumes energy? Intuitively, executing the CKN algorithm will consume a mass of energy with substantial data transmission to exchange local information between nodes and their neighbors, which influences the energy consumption distribution of network. (2) Do all active sensor nodes in the CKN algorithm [1] consume the energy uniformly in each epoch? We identify the nonuniform energy consumption problem, as shown in Figure 1. It is recognized that when executing the CKN algorithm in WSNs, sensor nodes with less residual energy are possible to be selected, which may result in that the energy of these sensor nodes can be fast consumed. The problem is caused by: the CKN algorithm chooses the active nodes absolutely based on the rank   s that are randomly given at the beginning of executing the CKN algorithm in each epoch. In other words, the CKN algorithm cannot ensure the network energy is balancedly consumed.

OPEN IN VIEWER

Figure 1

Nonuniform energy consumption problem. In (a), the black nodes represent the nodes which have more residual energy than those of node N 0 , the grey and white nodes have less energy than N 0 's, and the white node has the least energy. In (b), the green nodes represent the active nodes according to the CKN algorithm in a WSN, and the sensor nodes with less residual energy are selected.

Motivated by above two major issues, we conduct theoretical studies on two important questions based on the CKN algorithm. The first question is as follows. Is the CKN algorithm energy saving for any given value of k and the epoch? If not, how frequently should the CKN algorithm be executed so that the network is energy saving? In order to find out the relationship between the epoch and the energy consumption, we build a probabilistic model for the CKN algorithm to compute the probability that each random node goes to sleep and the expected total number of epochs during each node's lifetime. We formulate the lower bound of an epoch to keep the CKN algorithm energy efficient.

We address the second question based on the analysis for the first problem: How do we design a new sleep scheduling algorithm based on the CKN algorithm that can balance the energy consumption to prolong network lifetime further? Satisfying all those requirements that the CKN algorithm holds, a new decentralized sleep scheduling algorithm is challenging. In the light of the discussions for the question 1, we propose a new sleep scheduling algorithm, named energy-consumption-based CKN (EC-CKN), to prolong the network lifetime. The advantage of the EC-CKN algorithm over the original CKN algorithm is that it takes the nodes' residual energy information as parameter to decide whether a node to be active or sleep. The EC-CKN algorithm inherits all the major properties of the CKN algorithm, that is, solving the k-connected neighborhoods problem. Meanwhile, it also makes a significant new contribution to the energy efficiency by assuring the k-active neighbor nodes have more residual energy than other neighbor nodes in the current epoch. A theoretical analysis on the energy consumption of the EC-CKN algorithm is given to show the correctness of the new contribution.

The rest of the paper is as follows. Section 2 shows the network model. Section 3 presents the original CKN algorithm regulation and its properties. Section 4 builds a probabilistic model to compute the probability that a random node goes to sleep. Section 5 presents the EC-CKN algorithm. Section 6 demonstrates the properties of the EC-CKN algorithm. Section 7 shows the simulation results about the original CKN algorithm and the EC-CKN algorithm, comparing theoretical values and simulation results. Finally, Section 9 concludes the paper.

2. Network Model

2.1. Communication Network Model

A multihop sensor network is modeled by a graph G = ( S , E ) , where S = { s 1 , s 2 , … , s n } is the set of sensor nodes and E is the set of directed links. Each node has a uniform transmission radius of r t , and the necessary condition of ( s i , s j ) ∈ E is | s i - s j | ≤ r t and a node s j is the next hop of s i to the sink by the routing protocol. If ( s i , s j ) ∈ E , we use l i , j to denote ( s i , s j ) . Each node also has a uniform interference radius of r f . An node s j is interfered by the signal from s i , if | s i - s j | ≤ r f and s j is not the intended receiver. Let I i be the interference region that centers at s i with the interference radius r f . Each node is only equipped with a single radio interface and has the uniform initial energy ℰ 0 . The entire network lifetime is divided into epochs, and each epoch is T. At the beginning of each epoch, a node transmits packets in T 1 , and then it runs the sleep scheduling algorithm to decide the state of the next epoch in T 2 (where T = T 1 + T 2 ) as shown in Figure 2.

OPEN IN VIEWER

Figure 2

The lifetime of a node s u consists of many epochs. Each epoch includes packet transmission time and sleep scheduling algorithm's execution time.

2.2. Event Generation Model

Assume each node has a uniform sensing radius r s . Let C u denote the sensing region of the node s u , which centers at s u with the sensing radius r s . An event occurs when the sensing unit of a node s u picks up a signal with the power above a predetermined threshold within the sensing region C u [5]. Suppose the temporal event behavior over the entire sensing region, 𝒜, is a Poisson process with an average event rate λ. Let p X Y ( x , y ) denote an independent probability distribution of the spatial distribution of events. Let p e denote the probability that an event is detected by a node s u , given the fact that it occurred in 𝒜:

p e = ∫ C u p X Y ( x , y ) d x d y ∫ A p X Y ( x , y ) d x d y ,

(1)

where p X Y ( x , y ) is the spatial distribution of events that is characterized by an independent probability distribution. Let p m ( T , n ) denote the probability that n events occur in an epoch T at a node s u . Therefore, the probability of no events occurring in C u over an epoch T is given by

p m ( T , 0 ) = ∑ i = 0 ∞ e - λ T ( λ T ) i i ! ( 1 - p e ) i = e - p e λ T .

(2)

Let p m ( T ) denote the probability that at least one event occurs in an epoch T at a node s u :

p m ( T ) = 1 - p m ( T , 0 ) = 1 - e - p e λ T .

(3)

That is the probability of at least one event occurring at the node s u is an exponential distribution characterized by a spatially weighted event arrival rate λ u , u = λ × p e .

2.3. Buffer Analysis

Now, we consider two sources of traffic as an input to the buffer of each node [6].

Generated Packets

The sensing unit of a node senses events and generates packets as discussed in Section 2.2. These packets are generated packets. For a node s u , the rate of the generated packets is denoted by λ u , u .

Relay Packets

A node also receives packets from its upstream nodes and then forwards them to the sink node. (Along the data stream from a source node to the sink node by the routing protocol, downstream nodes are closer to the sink node, and receive packets sent by the node. Upstream nodes are far away from the sink node, and transmit packets to the node). These packets are referred as relay packets. The rate at which a node s u receives relay packets from a node s v is denoted as λ v , u .

Therefore, the input packet rate of s u 's buffer, λ u , can be written as

λ u = λ u , u + λ u , r = λ u , u + ∑ v ∈ N u in λ v , u ,

(4)

where λ u , r is the total relay packet rate at the node s u , 𝒩 u in is the set of nodes that have the node s u as the next hop, and λ v , u is the packet rate from the node s v to the node s u . Let γ u be the output rate of a node, which is given by

γ u = ( 1 + e u ) λ u ,

(5)

where e i is the packet error rate.

2.4. Channel and Energy Consumption Model

The energy consumption model characterizes energy consumption of a node in the network. Suppose there is no energy consumption when a node is sleep. If a node is active, we classify the energy consumption into three general categories.

(1) The Constant Energy Consumption

is the minimum energy needed to sustain a node when it is active without the packet transmission. It includes, for example, the battery leakage, energy consumed during the state transformation.

(2) The Additional Energy Consumption

is the energy consumed by the data transmission during the sleep scheduling algorithm running time.

(3) The Conventional Energy Consumption

includes the receiving energy consumption and the transmitting energy consumption except the local information exchange in the sleep scheduling algorithm, which is based on the first-order radio model [7].

The energy loss is due to the channel transmission, ϵ amp is the transmit amplifier. And the transmitting energy consumption for a bit packet is

E t x = E + ϵ amp ⋅ r t 2 ,

(6)

and the receiving energy consumption is

E r x = E ,

(7)

where ℰ is energy consumed by the transmitter or receiver circuitry.

2.5. Lifetime Definition

There is no universally agreed definition of network lifetime as it depends on the specific application. The lifetime can be measured by the time when the first node exhausts its energy, or when a certain fraction of nodes is dead, or even when all nodes are dead. Alternately, it may be reasonable to measure the network lifetime by application-specific parameters, such as the time when the network can no longer relay sensory data packets. In this paper, we define the network lifetime is the time when the first sensor node run out its energy from the beginning. The general network lifetime is the exact individual lifetime of each active node [8].

Theorem 1.

For a sensor network, each node has nonrechargeable initial energy ℰ 0 , the average general network lifetime 𝔼 [ ℒ ] , is given by

E [ L ] = E 0 E c + λ r E [ E r x ] + γ E [ E t x ] ,

(8)

where E c is the constant energy consumption on the first died node, 𝔼 [ E r x ] is the expected receiving energy consumption, and 𝔼 [ E t x ] is the expected transmitting energy consumption.

Proof.

Suppose there are M independently and identically distributed trials on the same sensor network to record the network lifetime ℒ, the receiving energy consumption of each bit E r x , and the transmitting energy consumption of each bit E t x . For the mth trial ( 1 ≤ m ≤ M ), the total energy consumed by the first died node during the whole lifetime is

E 0 = E c L m + ∑ i = 1 N r x m E r x m ( i ) + ∑ i = 1 N t x m E t x m ( i ) ,

(9)

where N r x m is the number of bits to be received, and N t x m is the number of bits to be transmitted of the first died node during the network lifetime of the mth trial. Summing (9) up over the M trials and dividing both sides by M, we obtain

E 0 = 1 M ∑ m = 1 M L m [ ( ∑ m = 1 M N t x m ∑ m = 1 M L m ) × ( ∑ m = 1 M ∑ i = 1 N t x m E t x m ( i ) ∑ m = 1 M N t x m ) E c + ( ∑ m = 1 M N r x m ∑ m = 1 M L m ) × ( ∑ m = 1 M ∑ i = 1 r x E r x m ( i ) ∑ m = 1 M N r x m ) + ( ∑ m = 1 M N t x m ∑ m = 1 M L m ) × ( ∑ m = 1 M ∑ i = 1 N t x m E t x m ( i ) ∑ m = 1 M N t x m ) ] .

(10)

Note that lim M → ∞ ( ∑ m = 1 M N r x m ) / ( ∑ m = 1 M ℒ m ) = λ r is the average receiving rate and lim M → ∞ ( ∑ m = 1 M N t x m ) / ( ∑ m = 1 M ℒ m ) = γ is the average transmitting rate.

The average receiving energy consumed in the ith received bit can be written as

E [ E r x ] = lim ⁡ M → ∞ ∑ m = 1 M E r x m ( i ) X m ( i ) D r x ( i ) , 1 ≤ i ≤ N r x ,

(11)

where 𝒳 m ( i ) = 1 for 1 ≤ i ≤ N r x m and 0 otherwise. D r x ( i ) = ∑ m = 1 M 𝒳 m ( i ) is the total number of the occurrence of the ith received bit among the M trials, and N r x = max m { N r x m } is the maximum number of received bits during the network lifetime. The probability that the received bit chosen randomly happens to the ith received bit is given by

p r x ( i ) = lim ⁡ M → ∞ D r x ( i ) ∑ m = 1 M N r x m , 1 ≤ i ≤ N r x .

(12)

Averaging (11) over the received bit chosen randomly indexing i, the expected receiving energy consumption is defined as

E [ E r x ] ≜ E r x i { E [ E r x ( i ) ] } = lim ⁡ M → ∞ ∑ m = 1 M ∑ i = 1 N m E r x m ( i ) ∑ m = 1 M N r x m ,

(13)

where 𝔼 [ E r x ( i ) ] is the average energy consumed in ith bit packet, 𝔼 r x i { · } denotes the expectation over the randomly chosen received packet indexing i.

Similarly, the expected transmitting energy consumption is

E [ E t x ] ≜ E t x i { E [ E t x ( i ) ] } = lim ⁡ M → ∞ ∑ m = 1 M ∑ i = 1 N t x m E t x m ( i ) ∑ m = 1 M N t x m ,

(14)

where 𝔼 [ E t x ( i ) ] is the average energy consumed in i th transmitted packet, 𝔼 t x ( i ) { · } denotes the expectation over the randomly chosen transmitted packet indexing i.

3. A Brief Description of CKN

In [1], the studied WSN is represented as an undirected communication graph G = ( S , E ) . N u is the set of s u 's neighbors. The connected K-neighborhood problem is defined as (i) each node has at least min { k , | N u | } active neighbors, which can be called awake neighbors; (ii) all active nodes are connected. To solve the problem, the authors developed a sleep scheduling algorithm: connected K-neighborhood (CKN).

In CKN, each node s u picks a random rank ran k u , broadcasts the ran k u , and collects its neighbors' ranks in R u . And then, s u broadcasts R u and collects R v from its neighbors, where s v ∈ N u . If s u or its neighbors has less than k neighbors, s u will remain awake. Otherwise, s u computes a subset C u of N u that is a set of nodes having rank < ran k u . “Before the node s u goes to sleep it needs to make sure that all nodes in C u are connected by nodes with rank < ran k u and each of its neighbors has at least k neighbors from C u ” [1].

The CKN algorithm has the following properties: first, each node s u (awake or not) with | N u | neighbors must have at least min { k , | N u | } awake neighbors in each epoch; second, there is the minimal average number of awake nodes per epoch; finally, awake nodes change from epoch to epoch. For any k ≥ 1 , there are more than 4 ( k + ln N ) neighbors for each node, where N is the number of nodes in the network. Then, with high probability, | CK N k | = O ( ln N ) · | OP T k | , where | CK N k | is the number of awake nodes by the CKN algorithm and | OP T k | is the number of awake nodes by an optimal algorithm that finds a minimum connected k-neighborhood as Figure 3.

OPEN IN VIEWER

Figure 3

Four examples of executing the CKN algorithm with different values for k. When k = 1 , a large number of sensor nodes can turn to sleep mode, but, when k = 8 , almost all sensor nodes have to be always-on. Here, black and unconnected sensor nodes are sleeping nodes.

4. Analysis of the CKN Algorithm

In this section, we build up a probabilistic model for the CKN algorithm to compute the probability that one node s u goes to sleep in each epoch. Based on the probability, we formulate the lower bound of an epoch to keep the CKN algorithm energy efficient.

For a homogeneous Poisson point process in two dimensions, the probability that a random node has n neighbors is [9]

P ( | N u | = n ) = ( ρ π r t 2 ) n n ! ⋅ e - ρ π r t 2 ,

(15)

E [ | N u | ] = ρ π r t 2 .

(16)

If there are at least k different paths connecting any two different vertices in the graph G, the graph is k-connected ( k = 1,2 , … ). The probability that the graph G is k-connected is

P ( G k ) = ( 1 - ∑ n k - 1 ( ρ π r t 2 ) n n ! ⋅ e - ρ π r t 2 ) N .

(17)

4.1. Sleep Probability in the CKN Algorithm

For the CKN algorithm, when a node s u has at least k neighbors, whether it goes to sleep is decided by two factors: (1) “any two nodes in C u are connected either directly or indirectly through s u 's 2-hop neighbors that have rank   less than ran k u ” and (2) “any node in N u has at least k neighbors for C u ” [1].

Lemma 2.

| C u | ~ B ( | N u | , p ) and | C u ′ | ~ B ( | N u ′ | , p ) are binomial distributions, where p is the probability that a node has rank < rank u .

Proof.

Let { ran k 1 , ran k 2 , … , ran k | N u | } be the random ranks for nodes in N u . Suppose ran k i ∈ ( 0,1 ) and i ∈ [ 1 , | N u | ] . Let

x i = { 1 , if ran k u - ran k i > 0 , 0 , otherwise , p = p i ( x i = 1 ) = E ( P ran k u - ran k i > 0 ) = 1 2 , q = p i ( x i = 0 ) = 1 - p .

(18)

Let Z = ∑ i ∈ N u x i , and the probability z j = j is

p j = ( j | N u | ) ⋅ p j ⋅ q | N u | - j = ( j | N u | ) ⋅ p | N u | ,

(19)

where j ∈ [ 0 , | N u | ] and | C u | ~ B ( | N u | , p ) . Similarly, | C u ′ | ~ B ( | N u ′ | , p ) .

Theorem 3.

Under the CKN algorithm, the sleep probability of a node s u is

p s ( | C u | ) = Prob 1 ⋅ Prob 2 ,

(20)

and the awake probability is

p a ( | C u | ) = 1 - p s ( | C u | ) ,

(21)

where Pro b 1 , the probability a node s u satisfies the first condition, is defined as

Prob 1 ≜ ( 1 - e - ρ 1 π r t 2 ) | C u ′ | ,

(22)

and Pro b 2 , the probability s u satisfies the second condition, is defined as

Prob 2 ≜ P ( | C u | ≥ k + 1 ) ⋅ P ( G C u k ) ⋅ P ( C u N u - C u k ) .

(23)

Proof.

If s u and its neighbors have at least k neighbors, the two conditions deciding s u whether to sleep or not can be interpret as the following corresponding conditions: (1) the graph G C u ′ is connected, and (2) the graph G C u is k-connected and each node in the set N u - C u has at least k neighbors in C u .

The probability that the graph G C u ′ is k-connected is

Pro b 1 ≤ Prob ( G C u ′ is connected ) ≤ P ( | N u | min ⁡ ≥ 1 ) = ( 1 - e - ρ 1 π r t 2 ) | C u ′ | ,

(24)

where | N u | min is the minimum degree in the graph G C u ′ , and ρ 1 = | C u ′ | / ( 4 π t r 2 ) is the node density in the graph G C u ′ .

The probability of the condition (2) is

Pro b 2 = P ( | C u | ≥ k + 1 ) ⋅ P ( G C u k ) ⋅ P ( C u N u - C u k ) ,

(25)

where P ( G C u k ) , the probability that the graph G C u is k-connected, can be expressed as

P ( G C u k ) ≤ ( 1 - ∑ n = 0 k - 1 ( ρ 2 π r t 2 ) n n ! ⋅ e - ρ 2 π r t 2 ) | C u | ,

(26)

and P ( C u N u - C u k ) is the probability that a node s v ∈ ( N u - C u ) has at least k neighbors in C u , which is

P ( C u N u - C u k ) = ( 1 - ∑ n = 0 k - 1 ( ρ 2 π r t 2 ) n n ! ⋅ e - ρ 3 π r t 2 ) | N u - C u | ,

(27)

where ρ 2 = | C u | / ( π t r 2 ) , ρ 3 = ( | C u | + 1 ) / ( π t r 2 ) , and | N u - C u | is the number of the elements in the set N u - C u .

4.2. Energy Consumption of the CKN Algorithm

Based on the result of the probability a random node goes to sleep, we can now analyze the node energy consumption for two cases: (1) it runs the CKN algorithm; (2) it does not run the CKN algorithm.

Lemma 4.

When a node s u executes the CKN algorithm, its energy consumption is

E ckn ( s u ) = E c 1 + 2 ( E t x + | N u | ⋅ E r x ) ,

(28)

and the energy consumption of a node during each epoch is

E epoch ( s u ) = E c 2 + T 1 ( λ r E r x + γ E t x ) ,

(29)

where ℰ c 1 and ℰ c 2 are the constant energy consumptions of a node during the time of the CKN algorithm executed and an epoch, respectively.

Theorem 5.

Under the CKN algorithm, the lower bound of an epoch keeping the network energy efficient is

T ̲ ≥ E [ L ] ( E [ E ckn ] + p a ⋅ E [ E epoch ] ) E 0 ,

(30)

where 𝔼 [ ℰ ckn ] and 𝔼 [ ℰ epoch ] are the expectation energy consumption during the time of the CKN algorithm executed and the expectation of the energy consumption during an epoch.

Proof.

Suppose there are M i.i.d. trials on the same network that runs the CKN algorithm as the sleep schedule to record the network lifetime, ℒ ckn , and the epoch is T in each trial. For the mth trial, the total energy consumed by the first died node during the lifetime is

E 0 = N epoch m E ckn + ∑ i = 1 N epoch m E epoch m ( i ) ,

(31)

where 𝒩 epoch m is the number of epochs in the mth trial. Summing (31) up to the M trials and dividing both sides by M, we obtain

E 0 = 1 M [ E ckn ∑ m = 1 M N epoch m + ∑ m = 1 M ∑ i = 1 N epoch m E epoch m ( i ) ] .

(32)

Note that T lim M → ∞ ( 1 / M ) ∑ m = 1 M 𝒩 epoch m = 𝔼 [ ℒ ckn ] .

The average energy consumed in the ith epoch can be written as

E [ E epoch ] = lim ⁡ M → ∞ ∑ m = 1 M E epoch m ( i ) Y m ( i ) D epoch ( i ) , 1 ≤ i ≤ N epoch ,

(33)

where 𝒴 m ( i ) = 1 if 1 ≤ i ≤ 𝒩 epoch m and the node is awake in the ith epoch, and 0 otherwise. D epoch ( i ) = ∑ m = 1 M 𝒴 m ( i ) is the total number of the ith epoch that the node is awake among the M trials, and 𝒩 epoch = max m { 𝒩 epoch m } is the maximum number of epochs during the network lifetime. The probability that a randomly chosen awake epoch of a node happens to the ith epoch is given by

p a ( i ) = lim ⁡ M → ∞ D epoch ( i ) ∑ m = 1 M N epoch m = lim ⁡ M → ∞ 1 M ∑ m = 1 M p a ( m ) ,

(34)

where p a ( m ) is the nodes awake probability in the mth trial. Averaging (33) over the randomly chosen epoch indexing i, the expected ith epoch energy consumption except for the energy consumed by the CKN algorithm is defined as

E [ E epoch ] ≜ lim ⁡ M → ∞ ∑ m = 1 M E epoch m ( i ) Y m ( i ) N epoch m .

(35)

5. The Energy-Consumption-Based CKN Algorithm

We develop a new sleep scheduling algorithm to extend the network lifetime, which can still have all properties of the CKN algorithm.

A scalable distributed solution to the connected k-neighborhoods problem based on the nodes' current residual energy information is challenging for several reasons. First, a node can go to sleep assuming that there are at least k neighbors being awake to keep it k-connected. Second, the outcome of the algorithm must change over epochs so that all nodes have opportunities to sleep. Third, even though nodes decide to sleep or wake up based on their local information, the whole network must be globally connected. The aforementioned three challenges have been achieved by the CKN algorithm [1], which keep the network duty-cycled and connected k-neighborhood. Fourth, awake neighbors of any node s u have k-top residual. The last one makes sure the energy of the network consumed balancedly, which is the main strength that the EC-CKN algorithm has over the original CKN algorithm.

We address the challenges by proposing the EC-CKN algorithm. The pseudocode of Algorithm 1 depicts the EC-CKN algorithm, which is repeated in each epoch on each node. The algorithm takes an input parameter, k, the required minimum number of per node's awake neighbors. In EC-CKN algorithm, a node s u broadcasts its current residual energy information E ran k u (Step 1). It computes a subset E u of neighbors having E rank < E ran k u (Step 5). Before s u goes to sleep, it makes sure that any two nodes in E u are connected either directly or indirectly through the node that is in the s u 's 2-hop neighbors having E rank < E ran k u , and its neighbors have at least k neighbors from E u (Step 6). These requirements ensure that when a node has less than k neighbors, none of its neighbors goes to sleep, and when it has more than k neighbors, at least k neighbors decide to remain awake. Note that these requirements are easy to keep by computing locally with 2-hop neighborhood information. The current residual energy is exchanged in Steps 2 and 3.

Algorithm 1: Energy-consumption-based CKN (*run the following at each node s u *).

6. Properties of the EC-CKN Algorithm

This section analyzes the network lifetime, the awake probability, and the energy consumption of the network under the EC-CKN algorithm.

Proof.

Suppose N nodes are placed uniformly at random within a deployment area such that the average number of neighbors per node is ξ ≥ 4 ( k + ln N ) . Let δ = ( c k ln N ) / ξ , for constant c > 96 determined by the analysis. Consider executing the algorithm EC-CKN on the network, and let E ran k ( i ) * be the residual energy of the δth largest residual energy selected by a node in the ith epoch. We claim that, w.h.p., all nodes with residual energy < E ran k ( i ) * go to sleep. Because there are at most δ nodes with residual energy at least E ran k ( i ) * , we have the average number of the awake nodes in each epoch is

| EC | k ≤ δ = c k ln ⁡ N ξ .

(36)

And the average network lifetime under the algorithm EC-CKN can be written as

E [ L EC ] = N T E 0 | EC | k ⋅ E epoch + ( N - | EC | k ) ⋅ E EC ,

(37)

where ℰ EC = ℰ ckn is the energy consumed by executing the EC-CKN algorithm, and T is the length of an epoch. In comparison with the energy consumed by the awake nodes in an epoch, the energy consumed by the sleep nodes in an epoch is considered negligible:

E [ L EC ] ≈ N T ξ E 0 c k ln ⁡ N ⋅ E epoch .

(38)

For the algorithm EC-CKN, a node could have four states: Init, Awake, Sleep, and Dead. Let 𝒮 = { I n i t = 0 , A w a k e = 1 , S l e e p = 2 , D e a d = 3 } be the set of the node's states, and N s = | 𝒮 | is the capacity of the states. Nodes can turn into the states Awake, and Sleep from the states Init, Awake and Sleep, respectively. And the state Dead can be only transformed from the states Awake and Sleep. Figure 4 shows the states transition graph in the algorithm EC-CKN, in which vertices are the states of nodes and the weights of edges are the transition probability between the two states in the ith epoch.

OPEN IN VIEWER

Figure 4

The Markov state transition probability graph of the EC-CKN algorithm.

Theorem 7.

Under the algorithm EC-CKN, the difference of the energy consumption between nodes s u and s v in the ith epoch is

d n = { T 2 ( Λ E r x + Γ E t x ) , if n = 0 , T 2 p u a ( i - 1 ) ( Λ E r x + Γ E t x ) , otherwise ,

(39)

where Λ and Γ are both the Skellam distributions and p u a ( i - 1 ) is the average probability that a node is awake in the ( i - 1 ) -th epoch.

Proof.

Let 𝒮 u = { 𝒮 u 0 , 𝒮 u 1 , … , 𝒮 u i , … } denote the states of s u in epochs, and let the chain

d : d 0 , d 1 , … , d i , …

(40)

denote the difference between the energy consumed by nodes s u and s v in each epoch, where s v ∈ N u . d i = α ℰ v , epoch ( i ) - β ℰ u , epoch ( i ) , where ℰ u , epoch ( i ) and ℰ v , epoch ( i ) are the conventional energy consumption of nodes s u and s v if they are awake in the ith epoch. The factors α and β depend on the state of nodes s u and s v . If 𝒮 u i = 0 o r 1 , α = 1 , and if 𝒮 u i = 3 , α = 0 , which is the same with β.

Suppose there are M independently and identically distributed trials. For the mth trial ( 1 ≤ m ≤ M ), the difference between the energy consumption of the two nodes in the ith epoch is

d m i = α E v , epoch m ( i ) - β E u , epoch m ( i ) .

(41)

The average difference of energy consumption in the ith epoch can be defined as

d ( i ) = lim ⁡ M → ∞ T 2 M [ ∑ m = 1 M [ ( α N v , r x m , i - β N u , r x m , i ) E r x ] T 2 + ∑ m = 1 M [ ( α N v , t x m , i - β N u , t x m , i ) E t x ] T 2 ] ,

(42)

where N u , r x m , i and N u , t x m , i are the number of received bits and transmitted bits of the node s u in the ith epoch during the mth trial. T 2 is the time of the conventional data transmission time of each epoch. We discuss the difference between the energy consumption of two nodes in the following two cases.

Case 1 ( i = 0 ).

According to (33) and (14), we obtain

d ( 0 ) = T 2 [ ( λ v , r - λ u , r ) E r x + ( γ v - γ u ) E t x ] .

(43)

Case 2 ( i > 0 ).

According to (33) and (34), we obtain

d ( i ) = T 2 p u a ( i - 1 ) [ ( λ v , r - λ u , r ) E r x + ( γ v - γ u ) E t x ] ,

(44)

where p u a ( i - 1 ) is the expected probability that the node is awake in the ( i - 1 ) -th epoch.

Note for λ v , r and λ u , r are two independent Poisson distributions, Λ = λ v , r - λ u , r is the Skellam distribution. Similarly,  Γ = γ v - γ v is also the Skellam distribution.

Theorem 8.

Consider a random node s u , which has more than k neighbors, the probability that a node s u is awake in the ith epoch under the EC-CKN algorithm is

p a i = { p a ( | E u 0 | ) , if i = 0 , p a ( | E u i | ) , otherwise .

(45)

Proof.

We introduce a new chain

D : 0 , d 0 , D 0 , d 1 , D 1 , … , d i , D i , … ,

(46)

to denote the difference between the residual energy of the two nodes s u and s v , where s v ∈ s u . Then, we obtain

D i = { d 0 , if i = 0 , D ( i - 1 ) + d 0 , otherwise .

(47)

Therefore, the number of elements in the set E u i is | E u i | = | N u | ϱ i , where

ϱ ( i ) = { D 0 max ⁡ { d 0 } - min ⁡ { d 0 } if i = 0 , D i max ⁡ { D i } - min ⁡ { D i } otherwise .

(48)

Theorem 9.

Under the EC-CKN algorithm, the upper bound of the network lifetime is

L ̄ EC-CKN = E 0 min ⁡ ∑ i ∑ a σ i , a E epoch n ,

(49)

where σ i , a is the steady-state probability that the action a is chosen when the chain is in the state i under the policy 𝒦.

Proof.

Now, we construct a Markov State Decision chain for each node s u :

S u 0 , a 0 , S u 1 , a 1 , … , S u n , a n , … ,

(50)

where 𝒮 u 0 = 0 , and 𝒮 u n ∈ { 1,2 , 3 } denotes the state in the nth epoch ( n ≥ 1 ), and a n is the action under the state 𝒮 u n

a n = { E u , epoch n , if n = 0 or S u n = 1 , 0 , otherwise .

(51)

Let the policy 𝒦 = { κ u , i n ( a ) } denote the probability that the action a is chosen when 𝒮 u = i , which satisfies the following two conditions:

0 ≤ κ u , i ( a ) ≤ 1 , ∀ i , a , ∑ a κ u , i ( a ) = 1 , ∀ i .

(52)

Under the policy 𝒦, the sequence of states 𝒮 u n constitutes a Markov chain with the transition probability p u n ( 𝒦 , i , j ) , which can be written as

p u n ( K , i , j ) = p u { S u n + 1 = j | S u n = i } = ∑ a p u n ( i , j ) κ u , i ( a ) .

(53)

For the policy 𝒦, let σ i , a denote the steady-state probability that the chain is in the state i and the action a is chosen:

σ i , a = lim ⁡ n → ∞ P K { S u n = i , a n = a }

(54)

The vector σ = { σ i , a } satisfies

( i ) σ i , a ≥ 0 , ∀ i , a , ( ii ) ∑ i ∑ a σ i , a = 1 , ∀ i , a , ( iii ) ∑ a σ j , a = ∑ i ∑ a σ j , a p i , j , ∀ i , a , j ,

(55)

Equations (55)(i) and (55)(ii) are obvious, and (55)(iii) follows as the left-hand side equals the steady-state probability of being in the state j and the right-hand side is the same probability computed by conditioning on the state and action chosen one epoch earlier.

Suppose that a reward ℛ ( Y i n , a i n ) = a n is earned whenever the action a i n is chosen in the state i in the n'th epoch. Since ℛ ( Y i n , a i n ) denotes the reward earned at the epoch n, the expected average reward per epoch under the 𝒦 policy can be written as

E [ R ( K ) ] = lim ⁡ n → ∞ ∑ n ∑ i ∈ S R ( Y i n , a i n ) n = ∑ i ∑ a σ i , a i n R ( Y i n , a i n ) = ∑ i ∑ a σ i , a i a n .

(56)

Therefore, 𝔼 [ ℛ ( 𝒦 ) ] can be interpreted as the following linear program:

min ⁡ ∑ i ∑ a σ i , a R ( Y i n , a i n ) subject to σ i , a ≥ 0 , ∀ i , a , ∑ i ∑ a σ i , a = 1 , ∀ i , a , ∑ a σ j a = ∑ i ∑ a σ i , a p i , j , ∀ i , a , j ,

(57)

𝔼 [ ℛ ( 𝒦 ) ] is a special case of the linear programm and is solved by a standard linear linear programming algorithm known as the simplex algorithm. The simplex algorithm solves the linear program by moving from an extreme point of the feasibility region to a better extreme point until the optimal is reached. So we can figure out the lower bound and upper bound of the lifetime by the linear programming (57).