# Sleep Control Game for Wireless Sensor Networks

Authors: Sang Hoon Lee; Hyeokman Kim; Lynn Choi
Journal: Mobile Information Systems
 (2016)

---

## Abstract

In wireless sensor networks (WSNs), each node controls its sleep to reduce energy consumption without sacrificing message latency. In this paper we apply the game theory, which is a powerful tool that explains how each individual acts for his or her own economic benefit, to analyze the optimal sleep schedule for sensor nodes. We redefine this sleep control game as a modified version of the Prisoner’s Dilemma. In the sleep control game, each node decides whether or not it wakes up for the cycle. Payoff functions of the sleep control game consider the expected traffic volume, network conditions, and the expected packet delay. According to the payoff function, each node selects the best wake-up strategy that may minimize the energy consumption and maintain the latency performance. To investigate the performance of our algorithm, we apply the sleep control game to X-MAC, which is one of the recent WSN MAC protocols. Our detailed packet level simulations confirm that the proposed algorithm can effectively reduce the energy consumption by removing unnecessary wake-up operations without loss of the latency performance.


---

## Body

## 1. Introduction

To reduce the energy consumption, each sensor node employs duty cycling where each node periodically sleeps [1]. Researches in earlier stage of duty cycling [1–4] assume that all the nodes in a network have the same static duty cycle whether or not nodes wake up at the same time. Since many applications of WSN assume random events [1–10], traffic varies each time. Therefore, it is hard for the static duty cycling to optimize wake-up schedule according to traffic condition. Dynamic duty cycle [5–10] allows each node to adjust its duty cycle on-demand. Therefore, nodes can reduce energy consumption for unnecessary wake-up operations if there is no traffic. However, the existing dynamic duty cycling schemes exploit a heuristic sleep control which may degrade energy efficiency and latency performance.In this paper, we mathematically model and analyze the duty cycling of nodes to improve the energy efficiency of a MAC protocol without sacrificing the message latency. The communication activity of nodes is similar to human economic activities since both activities aim to maximize benefits—network performance for nodes versus economic profit for human—without global information for the entire network or market. In this regard, we adopt the game theory, which is a powerful tool that explains how each individual acts for his or her own economic benefit, as a tool for modeling and analyzing the duty cycle operation of sensor nodes. Since the communication activity of each node prioritizes over communication activities of other nodes and each node operates independently, the communication activity of a node can be regarded as the noncooperative game [11]. We redefine a sleep control game as the modified version of the Prisoner’s Dilemma [11], which is one of the representative noncooperative games.In the sleep control game, each node decides whether or not it wakes up for the cycle. Therefore, each node selects its strategy based on the payoff function. And, the wake-up probability is the key for each node’s strategy in the sleep control game. Since the sleep state of a node affects both the energy consumption and the message latency, the wake-up probability of each node needs to consider the expected traffic volume, network conditions, and the expected packet delay, which are three components for the payoff function in the sleep control game. According to the payoff function, each node selects the best wake-up strategy which may minimize the energy consumption and maintain the latency performance. We show that the sleep control game is stable and it has Nash Equilibrium with the designed payoff function.To investigate the performance of our algorithm, we apply the sleep control game to X-MAC [4] which is one of the recent WSN MAC protocols that employs the static duty cycling. From our detailed packet level simulations [12], we find that nodes with our algorithm can stay on sleep state 2.19 times longer than nodes with X-MAC. By reducing unnecessary idle listening, our algorithm saves 62% of the average per-node energy consumption of X-MAC. Nevertheless, our algorithm shows comparable latency performance to X-MAC. This suggests that our algorithm based on the mathematical model can provide an optimal dynamic duty cycling without relying on a heuristic. And, we believe that this is the first analytic framework for dynamic duty cycling.


## 2. Backgrounds and Related Works

A game theory describes and analyzes decision making process. In this paper, we limit our discussion to noncooperative model: the interaction between rational decision makers. The term rational decision makers here refer to those who are selfish and act for their best interest. The model described above is referred to as a “game,” and the decision makers are called “players.” This situation could be seen as follows: players choose a strategy from predefined list of strategies that will maximize their profit. A utility function would be deployed by each player to analyze another player’s strategy selection. A normal form of a gameG is given by G
=
[
N
,
A
,
{
u
i
}
].N
=
{
1,2
,
3
,
…
} is the set of players (decision makers), A
i is the strategy set of player i, A
=
A
1
×
A
2
×
⋯
×
A
n is the Cartesian product of the set of strategies available to each player, and {
u
i
}
=
{
u
1
,
…
,
u
n
} is the set of utility functions that describes a measure of player’s benefit that each player i wishes to maximize. The utility function u
i of each player i depends on the previous strategy selection, a
i, and the other player’s strategy selections, a
-
i. a
i and a
-
i together make up a unique action tuple a, which represents the action of each player. Mathematically a is the best response by player i to a
-
i if a
∈
{
arg
⁡
max
⁡
u
i
(
a
i
,
a
-
i
)
}.From the outcome of this model, we can conclude that stable states exist in the model. We figure these states are the Nash Equilibria. A system would be in Nash Equilibria when any individual player cannot increase profit by choosing any other strategies. In other words, Nash Equilibria could be expressed as the consistent projection of the outcomes of which there would be no incentive for each individual player to choose different strategies to maximize its profit.However, although Nash Equilibria do exist in the model, Nash Equilibria do not mean the best outcome of a game. In many cases, Pareto optimality [11] is the representation of the efficiency of a product. An outcome could be expressed as Pareto optimal only when no other outcome can make every player well off while the outcome makes one player better off at least. Pareto optimality is formally defined as follows.For all strategiesa, there is no strategy b such that u
k
(
a
)
>
u
k
(
b
) for some k
<
N where N is the number of players.There have been a few studies that apply game theory to MAC protocol design [13–16]. They are interested in increasing the network throughput by improving the contention resolution algorithm in the traditional wireless communication environment such as ad hoc network [13] and WLAN [14–16]. Thus, they focus on the improvement of the communication performance rather than the energy efficiency.In WSNs, quite a few studies applied the game theory to the routing protocols [17, 18], power management techniques [19–24], and a backoff technique [25]. However, there is no game theoretic study for duty cycling of MAC protocols. Our sleep control game is the first study that applies the game theory to the duty cycle operations of MAC protocols. In the rest of this section we will review the state-of-the-art duty cycling techniques for WSNs.Researches in earlier stage of duty cycling [1–4] assume that all the nodes in a network have the same static duty cycle whether or not nodes wake up at the same time. Since many applications of WSN assume random events [1–10], traffic varies each time. Therefore, it is hard for the static duty cycling to optimize wake-up schedule according to traffic condition. Dynamic duty cycle [5–10] allows each node to adjust its duty cycle on-demand. Therefore, nodes can reduce energy consumption for unnecessary wake-up operations if there is no traffic.To our knowledge, AMAC [10] is the first sensor network MAC protocol that can support variable duty cycle operations. The main ideas underlying AMAC are twofold. First, each node can adjust the duration of the periodic interval depending on the network traffic. Second, a node can also adjust the duration of its active period depending on the traffic. This dynamic adjustment of both the active period and the periodic interval enables the duty cycle of each sensor node to adapt to the network traffic, resulting in significant energy savings for idle nodes and improved communication performance for busy nodes at the same time. However, the cycle time of a node needs to be adjusted according to a 2
n multiple of the minimum cycle time T. Since the latency requirement of a given application is not always a 2
n multiple of T, AMAC may overwork to guarantee the latency requirement.A few more recent schemes [7–9] have studied the use of dynamic duty cycle operations. In PL-MAC [7] each node can reduce its duty cycle if its remaining energy is not enough to guarantee the predefined lifetime. If the expected lifetime of a node is longer than the predefined lifetime, a node may increase its duty cycle to reduce the communication latency. D-RMAC [8] focuses on the traffic condition. If a packet starts being buffered as traffic increases, a source node may double its duty cycle by transmitting an extra control packet to notify new duty cycle information. While AMAC, PL-MAC, and D-RMAC assume synchronous scheduling, MaxMAC [9] applies dynamic duty cycling to asynchronous scheduling, where each node wakes up independently. Like AMAC, each node can adjust its duty cycle depending on traffic.While previous works [1–10] have focused on sensors’ communication, ACDA [26] claims that the energy consumption of each sensor such as a camera should be considered. Authors modeled and simplified the scheduling problem under the consideration. ACDA controls both the lengths of a cycle time and sensing time to maximize the network utilization under periodic sensing application scenarios while our algorithm assumes nonperiodic event detection scenarios.To exploit a heuristic sleep control, the schemes discussed so far require a predefined trigger condition such as traffic occurrence [8, 10], a packet rate [9], or the remaining energy [7]. Although these trigger conditions can be derived from a reverse engineering, it is very hard to prove that the trigger conditions should lead to an optimal wake-up schedule of sensor nodes.


## 3. Sleep Control Algorithm

### 3.1. Sleep Control Game: Game Theoretic Model of Sleep Control

Consider that each node has a set ofN neighbor nodes in a contention based MAC protocol. We assume that each node independently controls its wake-up schedule and collects the network condition information within a single hop. The wireless channel is assumed to be error-free and packet loss is only due to collisions.We model the interaction among wireless sensor nodes as a noncooperative game since each node operates independently and prioritizes its communication over neighbor’s communications. Since each node is selfish and blind to the neighbor’s strategies, the interaction model is similar to the Prisoner’s Dilemma. We call the model as sleep control game.We define the sleep control game by using the expected message latency, node’s wake-up probability, contention measure, and the expected traffic volume. In practice, it is hard for a wireless sensor node to learn directly the wake-up probabilities of neighbors. Each node infers the neighbor’s wake-up probabilities by observing the network condition of the previous cycle. In addition, it is hard to predict an end-to-end packet delay from a source to a destination. However, each node can estimate the packet delay by itself. The expected message latency can be estimated by using the wake-up probability, contention measure, and the expected traffic volume.We assume that each node dynamically adjusts wake-up probability,w
i, in response to the expected latency performance, l
i. In other words, a next wake-up probability can be expressed as a function of a current wake-up probability and the expected latency performance. Hence, sleep control is a distributed, iterative feedback system mathematically given by(1)
w
i
t
+
1
=
F
i
w
i
t
,
l
i
t
,
l
i
t
=
M
i
w
t
,where w
i
(
t
) is the wake-up probability of node i at time t, w
(
t
)
=
[
w
i
(
t
)
] is the corresponding vector, and l
i
(
t
) is the expected packet latency on node i. Note that a packet latency on a node depends on the sleep states of a node and its neighbor nodes. Therefore, l
i
(
t
) is a function of the sleep states that can be expressed as the vector w
(
t
). Here, F
i models the sleep control algorithms and M
i models the latency update mechanisms. The expected packet latency is also affected by the traffic volume, which can be estimated from the buffer state and the event rate.We assume that (1) has equilibrium (
w
,
l
). The fixed point of (1) defines an implicit relation between the equilibrium wake-up probability w
i and the expected packet latency l
i:(2)
w
i
=
F
i
w
i
,
l
i
.IfF
i is continuously differentiable and ∂
F
i
/
∂
l
i
≠
0 in [
0,1
], then, by the implicit function theorem [27], there exists a unique continuously differentiable function f
i such that(3)
l
i
t
=
f
i
w
t
.We define the utility function of each nodei as(4)
U
i
w
i
=
∫
f
i
w
i
d
w
i
.Sincef
i
(
w
i
)
=
l
i
≥
0 and U
i
(
·
) is an integral, U
i
(
·
) is a monotonic function that is continuous and nondecreasing. It is reasonable to assume that f
i
(
·
) is a decreasing function—the larger the wake-up probability, the smaller the expected packet latency. This implies that U
i
(
·
) is strictly concave. With the above utility function, we define a sleep control game as follows.Definition 1.
A sleep control gameG is defined as a quadruple G
=
{
N
,
S
i
i
∈
N
,
u
i
i
∈
N
,
l
i
i
∈
N
}, where N is a set of players (sensor nodes). For a player i
∈
N, its own wake-up probability is its strategy S
i
=
{
w
i
∣
w
i
∈
[
α
i
,
β
i
]
} with 0
≤
α
i
≤
β
i
≤
1. Payoff function u
i
(
w
) can be expressed by using utility function U
i
(
w
i
) and the expected packet latency l
i
=
M
i
(
w
): (5)
u
i
w
=
U
i
w
i
-
ε
w
i
l
i
.
The latency affection factor,ε, indicates the impact of the single hop latency on the end-to-end message latency, which is a variable constant according to the network condition.The payoff function can be interpreted as the gain of utility from the packet latency discounted by the wake-up cost. One property of this game is that the computation of the payoff function does not require the explicit exchange of wake-up probability of each node among the nodes. Thus, this game can be played and implemented in a distributed manner. In addition, this game reduces the energy consumption and the bandwidth usage for transmitting control messages.Since the strategyw
i
∈
S
i is the wake-up probability of a node i, it is less than or equal to 1. The packet latency on node i is inversely proportional to w
i if there is no collision. Thus, the payoff function u
i
(
·
) has a nice economic interpretation: the gain of utility from the packet latency is discounted by the wake-up cost. The sleep control game regards (1) as the strategy update algorithm to find equilibrium. Therefore, we can specify the equilibrium properties of a sleep control algorithm by using the utility function U
i
(
w
i
) and the latency performance l
i. In other words, by exploiting these factors, we can define the sleep control game whose equilibrium determines the steady state properties such as the latency performance and the energy performance. (
F
,
M
) can specify the adaptation of the wake-up probability and suggest different strategies to approach the equilibrium of the game.


### 3.2. Analyzing Transmission Latency

In WSNs, the packet latency is influenced by node’s buffer state, traffic volume, and the wake-up state of a receiver node. When a nodei transmits a packet p to node j, the packet latency l
i on node i is given by(6)
l
i
=
P
i
j
p
+
Q
i
p
, where P
i
j
(
p
) denotes the delay due to the sleep state of nodes i and j and Q
i
(
p
) denotes the delay due to transmission failure. If we assume that the probability for an event occurrence is δ, the probability that the packet p collides with another packet is given by(7)
C
p
=
1
-
1
-
δ
A
d
-
1
,
A
=
4
∫
0
r
∫
0
r
+
x
/
2
r
2
-
r
-
y
2
d
y
d
x
,where d denotes the node density, r denotes the transmission range of a node, and A denotes the average area of union of transmission range of adjacent two nodes. If we assume that each node transmits a single packet during a single cycle, packet p needs to be delayed for a single cycle when there is a collision. Therefore, the delay due to a collision, Q
i
(
p
), can be given by(8)
Q
i
p
=
T
+
∑
k
∈
N
,
k
≠
i
k
T
C
p
k
,where T denotes the minimum cycle time which is longer than the time to carry out a single packet transmission, which consists of the time for transmitting a data packet and control packets and the control time space such as Interframe Spacing.The sleep delay,P
i
j
(
p
), is influenced by two wake-up probabilities: sender’s wake-up probability w
i
(
t
) and receiver’s wake-up probability w
j
(
t
). Since two nodes must wake up for a successful communication, the probability for the occurrence of the sleep delay is (
1
-
w
i
(
t
)
w
j
(
t
)
). Therefore, P
i
j
(
p
) is given by (9)
P
i
j
p
=
T
m
+
1
-
w
i
t
w
j
t
,where m denotes the delayed cycle time due to the sleep state after the packet p arrives at node i.


### 3.3. Designing Payoff Function

Equation (1) defines the probability for a node to wake up by using the previous wake-up probability and the expected packet latency. If we do not consider the previous wake-up probability, the wake-up probability of each node may be biased toward 0 or 1. This will lead to long message latency due to sleep delay when the probability stands near 0. Or, it may lead to high energy consumption due to idle listening when the probability stands near 1. Therefore, we expend the wake-up probability for a node as(10)
w
i
t
+
1
=
1
,
P
i
t
=
1
,
F
i
w
i
t
,
l
i
t
,
P
i
t
=
0
.P
(
t
) denotes whether or not the node transmits a packet in the previous cycle. If P
(
t
) is 1, the node transmitted a packet. By considering the previous communication, we can effectively reduce the sleep delay when there is burst traffic or a message consists of multiple packets.By using (5) and (6), we can derive the payoff function as(11)
u
i
w
=
∫
f
i
w
i
d
w
i
-
ε
w
i
l
i
=
∫
l
i
t
d
w
i
-
ε
w
i
l
i
=
Q
i
p
w
i
+
T
m
+
1
w
i
-
w
i
2
w
j
2
-
ε
w
i
l
i
.According to (11), each node requires receiver’s wake-up probability w
j. However, it may be difficult for a node to directly acquire the wake-up probability of the receiver. Therefore, each node infers the neighbor’s wake-up probabilities by observing the network condition of the previous cycle. According to (10), if a node i overheard the node j’s communication in the previous cycle, i assumes that j should wake up in this cycle. On the other hand, if i slept or did not overhear j’s communication, i assumes that w
i
≈
w
j by assuming nodes are evenly deployed and event occurs randomly anywhere.


### 3.4. Equilibrium of Sleep Control Game

The wake-up probability needs to be stable and unique in order to find the best strategy. To verify the stability of wake-up probability, we should analyze the equilibrium of the sleep control game and show that the equilibrium is unique. By proving the following three theorems, we will show the existence (Theorem3) and the uniqueness (Theorems 5 and 7) of the equilibrium. We use the Nash Equilibrium [11] to find the equilibrium.We denote the strategy (wake-up probability) selection for nodei by w
i. We further denote the strategy selection for all nodes but node i by w
-
i
=
(
w
1
,
…
,
w
i
-
1
,
w
i
+
1
,
…
,
w
N
) and use (
w
i
,
w
-
i
) for the strategy profile (
w
1
,
…
,
w
i
-
1
,
w
i
,
w
i
+
1
,
…
,
w
N
) for all the nodes in a network. A vector of wake-up probability w
∗ is a Nash Equilibrium if, for all the nodes i
∈
N, u
i
(
w
i
∗
,
w
-
i
∗
)
≥
u
i
(
w
i
,
w
-
i
∗
) for all w
i
∈
S
i. We see that the Nash Equilibrium is a set of strategies for which no player has an incentive to change unilaterally.Assumption 2.
The utility functionU
i
(
·
) is continuously differentiable, strictly concave, and with finite curvatures that are bounded away from zero; that is, there exist some constants μ and λ, such that 1
/
μ
≥
-
1
/
U
i
′
′
(
w
i
)
≥
1
/
λ
>
0.Theorem 3.
Under Assumption2, there exists a Nash Equilibrium for sleep control game G.Proof.
Assumption2 is a standard assumption in economics. As shown in (4), U
i
(
·
) is strictly concave since we assume that f
i
(
·
) is a decreasing function. In other words, for any x and y in the interval and for any t in [
0,1
], U
i
(
·
) follows the strictly concave condition: U
i
(
t
x
+
(
1
-
t
)
y
)
>
t
U
i
(
x
)
+
(
1
-
t
)
U
i
(
y
). The strategy space [
0,1
] is a bounded closed set. In one-dimensional Euclidean space, a bounded closed set is a compact convex set. Since the strategy spaces S
i are compact convex sets, and the payoff functions are continuous and concave in w
i, there exists a Nash Equilibrium [11].
Since payoff functionu
i
(
·
) is concave in w
i, at the Nash Equilibrium, w
i
∗ satisfies(12)
U
i
′
w
i
∗
-
l
i
w
∗
w
i
-
w
i
∗
≤
0
,
∀
w
i
∈
S
i
.
Define a functionV
w
=
∑
i
∈
N
U
i
w
i
-
w
i
-
∏
i
∈
N
(
1
-
w
i
). Then, this equation becomes an optimality condition for the following optimization problem [28]:(13)
max
w
∈
S
1
×
S
2
×
⋯
×
S
N
⁡
V
w
.That is, the Nash Equilibria of the wake-up game are optimal points of problem (13).Assumption 4.
Letγ
(
w
)
=
∏
i
∈
N
(
1
-
w
i
) and denote the smallest eigenvalue of ∇
2
γ
(
w
) over w by v
m
i
n. Then, -
μ
-
v
m
i
n
<
0.Theorem 5.
Under Assumptions2 and 4, the sleep control game G has a unique Nash Equilibrium.Proof.
The Hessian of functionV
(
w
) is written as (14)
∇
2
V
w
=
diag
⁡
U
1
′
′
w
1
,
…
,
U
N
′
′
w
N
-
∇
2
γ
w
,where diag
⁡
(
[
U
1
′
′
(
w
1
)
,
…
,
U
N
′
′
(
w
N
)
]
)
≤
-
μ
I and ∇
2
γ
(
w
)
≥
v
m
i
n
I. Thus, under Assumption 4, (15)
∇
2
V
w
≤
-
μ
-
v
m
i
n
I
<
0
.
By second-order conditions [28], V
(
w
) is a strictly concave function over the strategy space. So, the optimization problem (13) has a unique optimal, and the sleep control game has a unique Nash Equilibrium.
The equilibrium condition (12) implies that, at the Nash Equilibrium, w
i
∗ either takes value at the boundaries of the strategy space [
0,1
]—that usually leads to the longest packet latency (selecting “0”) or to the most energy consumption (selecting “1”)—or satisfies(16)
U
i
′
w
i
∗
=
l
i
w
∗
.
We call a Nash Equilibrium a nontrivial equilibriumw
∗ if, for all nodes i, w
∗ satisfies (16). Otherwise, it is a trivial equilibrium. According to (16), at nontrivial equilibrium, (17)
Γ
i
w
i
∗
=
γ
w
∗
.
Note that (17) is independent of i. Thus, Γ
i
(
w
i
∗
)
=
Γ
j
(
w
j
∗
) for any i
,
j
∈
N.Assumption 6.
Γ
i
(
w
i
∗
)
=
(
1
-
w
i
)
(
1
-
U
i
′
(
w
i
)
), i
∈
N, are all strictly increasing or all strictly decreasing.Theorem 7.
If the control gameG has a nontrivial Nash Equilibrium, it must be unique.Proof.
Suppose that there are two nontrivial Nash Equilibriumsw
1 and w
2. From (17) we require that there exist γ
1
,
γ
2
>
0 such that, for all i,(18)
Γ
i
w
1
i
=
γ
1
,
Γ
i
w
2
i
=
γ
2
.
SinceΓ
i
(
w
i
) is one-to-one, γ
1
≠
γ
2. Without loss of generality, assume that Γ
i
(
w
i
) is increasing and γ
1
>
γ
2. Thus, w
1
>
w
2 for all i. By (16), U
i
′
(
w
1
i
)
=
l
i
(
w
1
)
>
l
i
(
w
2
)
=
U
i
′
(
w
2
i
), which contradicts the fact that U
i
′
(
w
i
) is a decreasing function. Thus, the sleep control game G has a unique nontrivial Nash Equilibrium.Each nodei can choose any utility function U
i
(
·
) as appropriate. If all the nodes have the same utility function, the system is said to have homogeneous users. If the nodes have different utility functions, the system is said to have heterogeneous users. The motivation for studying systems of heterogeneous users is to provide differentiated services to different wireless nodes. To this end, we further differentiate between symmetric and asymmetric equilibria as follows.A Nash Equilibriumw
∗ is said to be a symmetric equilibrium if w
i
∗
=
w
j
∗ for all i and j. Otherwise, it is an asymmetric equilibrium. Since by symmetry there must be multiple asymmetric Nash Equilibria if there exists any, the following result follows directly from Theorems 5 and 7.For a system of homogeneous users, suppose Assumption4 or Assumption 6 holds. If the sleep control game has a nontrivial Nash Equilibrium, it must be unique and symmetric. More generally, for a system with several classes of homogeneous users, under the same assumption, if the sleep control game has a nontrivial Nash Equilibrium, it must be unique and symmetric. This corollary guarantees the uniqueness of nontrivial Nash Equilibrium, and it guarantees maximum energy-delay product of nodes. This will facilitate the design of medium access control. Since at trivial Nash Equilibrium some player takes a strategy (wake-up probability) at the boundary of the strategy space, a trivial Nash Equilibrium usually has great unfairness or low payoff. So, nontrivial Nash Equilibrium is desired. If there is no nontrivial Nash Equilibrium, we may need to look for alternative solution other than the Nash Equilibrium. For example, we may use Nash bargaining framework in cooperative game theory [11] to derive a desired equilibrium solution.


## 3.1. Sleep Control Game: Game Theoretic Model of Sleep Control

Consider that each node has a set ofN neighbor nodes in a contention based MAC protocol. We assume that each node independently controls its wake-up schedule and collects the network condition information within a single hop. The wireless channel is assumed to be error-free and packet loss is only due to collisions.We model the interaction among wireless sensor nodes as a noncooperative game since each node operates independently and prioritizes its communication over neighbor’s communications. Since each node is selfish and blind to the neighbor’s strategies, the interaction model is similar to the Prisoner’s Dilemma. We call the model as sleep control game.We define the sleep control game by using the expected message latency, node’s wake-up probability, contention measure, and the expected traffic volume. In practice, it is hard for a wireless sensor node to learn directly the wake-up probabilities of neighbors. Each node infers the neighbor’s wake-up probabilities by observing the network condition of the previous cycle. In addition, it is hard to predict an end-to-end packet delay from a source to a destination. However, each node can estimate the packet delay by itself. The expected message latency can be estimated by using the wake-up probability, contention measure, and the expected traffic volume.We assume that each node dynamically adjusts wake-up probability,w
i, in response to the expected latency performance, l
i. In other words, a next wake-up probability can be expressed as a function of a current wake-up probability and the expected latency performance. Hence, sleep control is a distributed, iterative feedback system mathematically given by(1)
w
i
t
+
1
=
F
i
w
i
t
,
l
i
t
,
l
i
t
=
M
i
w
t
,where w
i
(
t
) is the wake-up probability of node i at time t, w
(
t
)
=
[
w
i
(
t
)
] is the corresponding vector, and l
i
(
t
) is the expected packet latency on node i. Note that a packet latency on a node depends on the sleep states of a node and its neighbor nodes. Therefore, l
i
(
t
) is a function of the sleep states that can be expressed as the vector w
(
t
). Here, F
i models the sleep control algorithms and M
i models the latency update mechanisms. The expected packet latency is also affected by the traffic volume, which can be estimated from the buffer state and the event rate.We assume that (1) has equilibrium (
w
,
l
). The fixed point of (1) defines an implicit relation between the equilibrium wake-up probability w
i and the expected packet latency l
i:(2)
w
i
=
F
i
w
i
,
l
i
.IfF
i is continuously differentiable and ∂
F
i
/
∂
l
i
≠
0 in [
0,1
], then, by the implicit function theorem [27], there exists a unique continuously differentiable function f
i such that(3)
l
i
t
=
f
i
w
t
.We define the utility function of each nodei as(4)
U
i
w
i
=
∫
f
i
w
i
d
w
i
.Sincef
i
(
w
i
)
=
l
i
≥
0 and U
i
(
·
) is an integral, U
i
(
·
) is a monotonic function that is continuous and nondecreasing. It is reasonable to assume that f
i
(
·
) is a decreasing function—the larger the wake-up probability, the smaller the expected packet latency. This implies that U
i
(
·
) is strictly concave. With the above utility function, we define a sleep control game as follows.Definition 1.
A sleep control gameG is defined as a quadruple G
=
{
N
,
S
i
i
∈
N
,
u
i
i
∈
N
,
l
i
i
∈
N
}, where N is a set of players (sensor nodes). For a player i
∈
N, its own wake-up probability is its strategy S
i
=
{
w
i
∣
w
i
∈
[
α
i
,
β
i
]
} with 0
≤
α
i
≤
β
i
≤
1. Payoff function u
i
(
w
) can be expressed by using utility function U
i
(
w
i
) and the expected packet latency l
i
=
M
i
(
w
): (5)
u
i
w
=
U
i
w
i
-
ε
w
i
l
i
.
The latency affection factor,ε, indicates the impact of the single hop latency on the end-to-end message latency, which is a variable constant according to the network condition.The payoff function can be interpreted as the gain of utility from the packet latency discounted by the wake-up cost. One property of this game is that the computation of the payoff function does not require the explicit exchange of wake-up probability of each node among the nodes. Thus, this game can be played and implemented in a distributed manner. In addition, this game reduces the energy consumption and the bandwidth usage for transmitting control messages.Since the strategyw
i
∈
S
i is the wake-up probability of a node i, it is less than or equal to 1. The packet latency on node i is inversely proportional to w
i if there is no collision. Thus, the payoff function u
i
(
·
) has a nice economic interpretation: the gain of utility from the packet latency is discounted by the wake-up cost. The sleep control game regards (1) as the strategy update algorithm to find equilibrium. Therefore, we can specify the equilibrium properties of a sleep control algorithm by using the utility function U
i
(
w
i
) and the latency performance l
i. In other words, by exploiting these factors, we can define the sleep control game whose equilibrium determines the steady state properties such as the latency performance and the energy performance. (
F
,
M
) can specify the adaptation of the wake-up probability and suggest different strategies to approach the equilibrium of the game.


## 3.2. Analyzing Transmission Latency

In WSNs, the packet latency is influenced by node’s buffer state, traffic volume, and the wake-up state of a receiver node. When a nodei transmits a packet p to node j, the packet latency l
i on node i is given by(6)
l
i
=
P
i
j
p
+
Q
i
p
, where P
i
j
(
p
) denotes the delay due to the sleep state of nodes i and j and Q
i
(
p
) denotes the delay due to transmission failure. If we assume that the probability for an event occurrence is δ, the probability that the packet p collides with another packet is given by(7)
C
p
=
1
-
1
-
δ
A
d
-
1
,
A
=
4
∫
0
r
∫
0
r
+
x
/
2
r
2
-
r
-
y
2
d
y
d
x
,where d denotes the node density, r denotes the transmission range of a node, and A denotes the average area of union of transmission range of adjacent two nodes. If we assume that each node transmits a single packet during a single cycle, packet p needs to be delayed for a single cycle when there is a collision. Therefore, the delay due to a collision, Q
i
(
p
), can be given by(8)
Q
i
p
=
T
+
∑
k
∈
N
,
k
≠
i
k
T
C
p
k
,where T denotes the minimum cycle time which is longer than the time to carry out a single packet transmission, which consists of the time for transmitting a data packet and control packets and the control time space such as Interframe Spacing.The sleep delay,P
i
j
(
p
), is influenced by two wake-up probabilities: sender’s wake-up probability w
i
(
t
) and receiver’s wake-up probability w
j
(
t
). Since two nodes must wake up for a successful communication, the probability for the occurrence of the sleep delay is (
1
-
w
i
(
t
)
w
j
(
t
)
). Therefore, P
i
j
(
p
) is given by (9)
P
i
j
p
=
T
m
+
1
-
w
i
t
w
j
t
,where m denotes the delayed cycle time due to the sleep state after the packet p arrives at node i.


## 3.3. Designing Payoff Function

Equation (1) defines the probability for a node to wake up by using the previous wake-up probability and the expected packet latency. If we do not consider the previous wake-up probability, the wake-up probability of each node may be biased toward 0 or 1. This will lead to long message latency due to sleep delay when the probability stands near 0. Or, it may lead to high energy consumption due to idle listening when the probability stands near 1. Therefore, we expend the wake-up probability for a node as(10)
w
i
t
+
1
=
1
,
P
i
t
=
1
,
F
i
w
i
t
,
l
i
t
,
P
i
t
=
0
.P
(
t
) denotes whether or not the node transmits a packet in the previous cycle. If P
(
t
) is 1, the node transmitted a packet. By considering the previous communication, we can effectively reduce the sleep delay when there is burst traffic or a message consists of multiple packets.By using (5) and (6), we can derive the payoff function as(11)
u
i
w
=
∫
f
i
w
i
d
w
i
-
ε
w
i
l
i
=
∫
l
i
t
d
w
i
-
ε
w
i
l
i
=
Q
i
p
w
i
+
T
m
+
1
w
i
-
w
i
2
w
j
2
-
ε
w
i
l
i
.According to (11), each node requires receiver’s wake-up probability w
j. However, it may be difficult for a node to directly acquire the wake-up probability of the receiver. Therefore, each node infers the neighbor’s wake-up probabilities by observing the network condition of the previous cycle. According to (10), if a node i overheard the node j’s communication in the previous cycle, i assumes that j should wake up in this cycle. On the other hand, if i slept or did not overhear j’s communication, i assumes that w
i
≈
w
j by assuming nodes are evenly deployed and event occurs randomly anywhere.


## 3.4. Equilibrium of Sleep Control Game

The wake-up probability needs to be stable and unique in order to find the best strategy. To verify the stability of wake-up probability, we should analyze the equilibrium of the sleep control game and show that the equilibrium is unique. By proving the following three theorems, we will show the existence (Theorem3) and the uniqueness (Theorems 5 and 7) of the equilibrium. We use the Nash Equilibrium [11] to find the equilibrium.We denote the strategy (wake-up probability) selection for nodei by w
i. We further denote the strategy selection for all nodes but node i by w
-
i
=
(
w
1
,
…
,
w
i
-
1
,
w
i
+
1
,
…
,
w
N
) and use (
w
i
,
w
-
i
) for the strategy profile (
w
1
,
…
,
w
i
-
1
,
w
i
,
w
i
+
1
,
…
,
w
N
) for all the nodes in a network. A vector of wake-up probability w
∗ is a Nash Equilibrium if, for all the nodes i
∈
N, u
i
(
w
i
∗
,
w
-
i
∗
)
≥
u
i
(
w
i
,
w
-
i
∗
) for all w
i
∈
S
i. We see that the Nash Equilibrium is a set of strategies for which no player has an incentive to change unilaterally.Assumption 2.
The utility functionU
i
(
·
) is continuously differentiable, strictly concave, and with finite curvatures that are bounded away from zero; that is, there exist some constants μ and λ, such that 1
/
μ
≥
-
1
/
U
i
′
′
(
w
i
)
≥
1
/
λ
>
0.Theorem 3.
Under Assumption2, there exists a Nash Equilibrium for sleep control game G.Proof.
Assumption2 is a standard assumption in economics. As shown in (4), U
i
(
·
) is strictly concave since we assume that f
i
(
·
) is a decreasing function. In other words, for any x and y in the interval and for any t in [
0,1
], U
i
(
·
) follows the strictly concave condition: U
i
(
t
x
+
(
1
-
t
)
y
)
>
t
U
i
(
x
)
+
(
1
-
t
)
U
i
(
y
). The strategy space [
0,1
] is a bounded closed set. In one-dimensional Euclidean space, a bounded closed set is a compact convex set. Since the strategy spaces S
i are compact convex sets, and the payoff functions are continuous and concave in w
i, there exists a Nash Equilibrium [11].
Since payoff functionu
i
(
·
) is concave in w
i, at the Nash Equilibrium, w
i
∗ satisfies(12)
U
i
′
w
i
∗
-
l
i
w
∗
w
i
-
w
i
∗
≤
0
,
∀
w
i
∈
S
i
.
Define a functionV
w
=
∑
i
∈
N
U
i
w
i
-
w
i
-
∏
i
∈
N
(
1
-
w
i
). Then, this equation becomes an optimality condition for the following optimization problem [28]:(13)
max
w
∈
S
1
×
S
2
×
⋯
×
S
N
⁡
V
w
.That is, the Nash Equilibria of the wake-up game are optimal points of problem (13).Assumption 4.
Letγ
(
w
)
=
∏
i
∈
N
(
1
-
w
i
) and denote the smallest eigenvalue of ∇
2
γ
(
w
) over w by v
m
i
n. Then, -
μ
-
v
m
i
n
<
0.Theorem 5.
Under Assumptions2 and 4, the sleep control game G has a unique Nash Equilibrium.Proof.
The Hessian of functionV
(
w
) is written as (14)
∇
2
V
w
=
diag
⁡
U
1
′
′
w
1
,
…
,
U
N
′
′
w
N
-
∇
2
γ
w
,where diag
⁡
(
[
U
1
′
′
(
w
1
)
,
…
,
U
N
′
′
(
w
N
)
]
)
≤
-
μ
I and ∇
2
γ
(
w
)
≥
v
m
i
n
I. Thus, under Assumption 4, (15)
∇
2
V
w
≤
-
μ
-
v
m
i
n
I
<
0
.
By second-order conditions [28], V
(
w
) is a strictly concave function over the strategy space. So, the optimization problem (13) has a unique optimal, and the sleep control game has a unique Nash Equilibrium.
The equilibrium condition (12) implies that, at the Nash Equilibrium, w
i
∗ either takes value at the boundaries of the strategy space [
0,1
]—that usually leads to the longest packet latency (selecting “0”) or to the most energy consumption (selecting “1”)—or satisfies(16)
U
i
′
w
i
∗
=
l
i
w
∗
.
We call a Nash Equilibrium a nontrivial equilibriumw
∗ if, for all nodes i, w
∗ satisfies (16). Otherwise, it is a trivial equilibrium. According to (16), at nontrivial equilibrium, (17)
Γ
i
w
i
∗
=
γ
w
∗
.
Note that (17) is independent of i. Thus, Γ
i
(
w
i
∗
)
=
Γ
j
(
w
j
∗
) for any i
,
j
∈
N.Assumption 6.
Γ
i
(
w
i
∗
)
=
(
1
-
w
i
)
(
1
-
U
i
′
(
w
i
)
), i
∈
N, are all strictly increasing or all strictly decreasing.Theorem 7.
If the control gameG has a nontrivial Nash Equilibrium, it must be unique.Proof.
Suppose that there are two nontrivial Nash Equilibriumsw
1 and w
2. From (17) we require that there exist γ
1
,
γ
2
>
0 such that, for all i,(18)
Γ
i
w
1
i
=
γ
1
,
Γ
i
w
2
i
=
γ
2
.
SinceΓ
i
(
w
i
) is one-to-one, γ
1
≠
γ
2. Without loss of generality, assume that Γ
i
(
w
i
) is increasing and γ
1
>
γ
2. Thus, w
1
>
w
2 for all i. By (16), U
i
′
(
w
1
i
)
=
l
i
(
w
1
)
>
l
i
(
w
2
)
=
U
i
′
(
w
2
i
), which contradicts the fact that U
i
′
(
w
i
) is a decreasing function. Thus, the sleep control game G has a unique nontrivial Nash Equilibrium.Each nodei can choose any utility function U
i
(
·
) as appropriate. If all the nodes have the same utility function, the system is said to have homogeneous users. If the nodes have different utility functions, the system is said to have heterogeneous users. The motivation for studying systems of heterogeneous users is to provide differentiated services to different wireless nodes. To this end, we further differentiate between symmetric and asymmetric equilibria as follows.A Nash Equilibriumw
∗ is said to be a symmetric equilibrium if w
i
∗
=
w
j
∗ for all i and j. Otherwise, it is an asymmetric equilibrium. Since by symmetry there must be multiple asymmetric Nash Equilibria if there exists any, the following result follows directly from Theorems 5 and 7.For a system of homogeneous users, suppose Assumption4 or Assumption 6 holds. If the sleep control game has a nontrivial Nash Equilibrium, it must be unique and symmetric. More generally, for a system with several classes of homogeneous users, under the same assumption, if the sleep control game has a nontrivial Nash Equilibrium, it must be unique and symmetric. This corollary guarantees the uniqueness of nontrivial Nash Equilibrium, and it guarantees maximum energy-delay product of nodes. This will facilitate the design of medium access control. Since at trivial Nash Equilibrium some player takes a strategy (wake-up probability) at the boundary of the strategy space, a trivial Nash Equilibrium usually has great unfairness or low payoff. So, nontrivial Nash Equilibrium is desired. If there is no nontrivial Nash Equilibrium, we may need to look for alternative solution other than the Nash Equilibrium. For example, we may use Nash bargaining framework in cooperative game theory [11] to derive a desired equilibrium solution.


## 4. Simulation and Results

In this section we analyze the performance of our algorithm by applying the sleep control game to X-MAC [4] which is one of the representative WSN MAC protocols recently proposed. X-MAC exploits the asynchronous wake-up scheduling that nodes independently wake up with a static duty cycle. We implemented X-MAC and a modified version of X-MAC with our sleep control algorithm, on NS-2 [12]. With the detailed packet level simulations, we evaluate the performance of our algorithm from various perspectives: the energy consumption, the message delay, the network throughput, and the wake-up probability. The simulation parameters are shown in Table 1. We assume that a sink node locates at the center of the network field where 400 nodes locate randomly. We also assume that an event occurs at random position and the nearest node detects the event. In other words, we evaluate the performance of our algorithm under a nonperiodic event scenario model that can be applied to environmental monitoring applications such as fire surveillance, mechanical malfunctions, and biochemical hazard.Table 1
Simulation parameters.
Parameters
Topology of a network
400 random nodes
Simulation time
1 hour
Data packet size
100 bytes
Number of packets for an event
10 packets
Basic cycle time of X-MAC, 4T
300 ms (5% duty cycle)
Event rate
0.1% perT
Power consumption (Tx, Rx, idle)
30 mW, 15 mW, 15 mW
Latency affection factor,ε
1
Maximum distance from a sink node
10 hops


### 4.1. Wake-Up Probability

Figure1 shows the wake-up probability of a sensor node by varying the node cycle time. Since the basic cycle time of X-MAC is 4
T, a node with X-MAC has 3
T sleep period. In X-MAC, each node wakes up according to the predefined schedule. The wake-up probability of a node for each T is 0 or 1. Unlike X-MAC, X-MAC
G
a
m
e uses the probabilistic wake-up approach. Starting from a sleep state, the wake-up probability of a node is gradually increased until the node actually wakes up.Figure 1
The wake-up probability according to time elapse.According to the results, a node withX-MAC
G
a
m
e wakes up only 2 times during 20
T while a node with X-MAC wakes up 5 times. The average sleep period of X-MAC
G
a
m
e is 6.58
T while X-MAC has 3
T sleep period. In other words, X-MAC
G
a
m
e can reduce the number of unnecessary wake-up operations when there is no traffic.Note that a node withX-MAC
G
a
m
e maintains the wake-up state when the cycle time changes from 23
T to 37
T. These continuous wake-up states represent that the node participates in communications. The reason why the X-MAC
G
a
m
e node consumes 15
T cycles to deliver a single 10-packet message is that the node suffered from transmission failures and the sleep delay due to the sleep state of a receiver.


### 4.2. Latency Performance

Figure2 shows the network throughput as time passes. Since nodes which participate in communications wake up at every minimum cycle time T in X-MAC
G
a
m
e, X-MAC
G
a
m
e can deliver more packets than X-MAC during the same interval. It means that X-MAC
G
a
m
e can effectively deliver burst traffic while X-MAC suffers from the accumulation of the sleep delay. According to the results, both X-MAC and X-MAC
G
a
m
e show a uniform distribution of the network throughput since we generate events randomly over the simulation time. When there are multiple events, the throughputs of two protocols reached a peak, which is proportional to the number of simultaneous transmissions.Figure 2
The network throughput according to time elapse.Figure3 shows the average message latency according to the hop distance from a source to a destination. As shown in Figure 1, the average sleep period of X-MAC
G
a
m
e is 6.58
T while X-MAC has 3
T sleep period. This suggests that the sleep control game can substantially reduce the idle listening overhead as much as 54.5% by eliminating unnecessary wake-up operations. However, the average message latency of X-MAC
G
a
m
e is slightly longer than that of X-MAC. Since nodes in X-MAC
G
a
m
e can adjust their wake-up schedules according to the traffic condition, they can adaptively decide their wake-up either to reduce idle listening or to reduce the sleep delay depending on traffic.Figure 3
The average message latency according to hop counts.Figure4 shows the distribution of the packet latency of single hop communications. Since X-MAC uses asynchronous wake-up scheduling with 300 ms cycle time, the difference between the wake-up times of two nodes causes the packet latency to be concentrated at the interval between 0.3 s and 0.5 s. Except the first packet of a message, other packets may suffer from the buffering delay. Therefore, the buffering delay makes X-MAC to have the second major concentration interval of [0.6 s, 0.85 s].Figure 4
The distribution of the packet latency for a single hop communication.Like X-MAC,X-MAC
G
a
m
e has two concentration intervals: [0.1 s, 0.2 s] and [0.4 s, 0.7 s]. Since X-MAC
G
a
m
e nodes increase the sleep period when there is no traffic, the sleep delay before transmitting the first packet of a message increases. Therefore, the latencies for the first packet of a message concentrate on [0.4 s, 0.7 s]. In X-MAC
G
a
m
e, each node that participates in a communication wakes up at every minimum cycle time T until the communication ends. This continuous wake-up state results in shorter buffering delay than X-MAC. Therefore, the most of the packet latencies are distributed between 0.4 s and 0.7 s.When a source generates multiple messages, the latencies of the following messages can be reduced since nodes on the common routing path already wake up after reporting the first message. Therefore,X-MAC
G
a
m
e has the second concentration period of [0.1 s, 0.2 s]. This second concentration period may be dominant as the number of simultaneous events increases.According to the results of Figures3 and 4, X-MAC
G
a
m
e has comparable performance while it keeps lower duty cycle than X-MAC. Moreover, X-MAC
G
a
m
e can effectively deal with burst traffic, which is common traffic pattern in WSNs. This suggests that the sleep control game can effectively reduce energy consumption due to unnecessary wake-up operations without sacrificing the communication performance.


### 4.3. Energy Consumption

Figure5 shows the average per-node energy consumption as time passes. From our simulations we find that the communication traffic is not the dominant source of the energy consumption. Even with heavy traffic, idle listening is still the dominant energy waste source [1]. Our results show that X-MAC consumes 87.7% of the total dissipated energy for idle listening when the event rate is 0.1% per T. The energy consumption due to idle listening accounts for 73.7% of the total when we increase the event rate by 0.5% per T.Figure 5
The average energy consumption according to time elapse.When there is no traffic,X-MAC
G
a
m
e consumes only 31.1% energy of X-MAC. Since this result shows the accumulation of the average energy consumption, the slope of graph varies according to the duty cycle of a sensor node. In addition, the dynamic wake-up scheduling approach of X-MAC
G
a
m
e also reduces the energy consumption due to overhearing since the approach reduces the chance for adjacent nodes to wake up at the same cycle by waking up only the nodes in a communication path more frequently. When the event rate is 0.1% per T, X-MAC
G
a
m
e consumes additional 0.165 J per node to deliver the traffic while X-MAC requires 0.205 J per node. X-MAC
G
a
m
e can save 19.5% of the energy consumption for communications by removing energy wastes due to overhearing.


### 4.4. Impact of the Latency Affection Factor

Figure6 shows the average message latency as we vary the latency affection factor, ε. According to (18), the wake-up probability is inversely proportional to the latency affection factor. In other words, we can reduce the message latency by reducing the latency affection factor. However, if we reduce the factor, the wake-up probability increases, and nodes will consume more energy for idle listening.Figure 6
The average message latency according to the latency affection factor,ε.Figure7 shows the average energy consumption according to the latency affection factor. As we discussed above, the small latency affection factor increases the wake-up probability. Therefore, the number of wake-up operations and the average energy consumption per node increase.Figure 7
The average energy consumption according to the latency affection factor,ε.As shown in Figures6 and 7, there is a tradeoff between message latency and energy consumption. Figure 8 shows the energy-delay product according to the latency affection factor, ε. Note that the latency affection factor is influenced by various environmental conditions such as the number of neighbors, event rate, the performance requirements of an application, and channel quality. In our experiments, the optimal latency affection factor is 2.37 from the performance viewpoint. However, the optimal latency affection factor is not always the best selection. If we assume that the message latency requirement of an application is bigger than 10 s in these simulations, we can save more energy by setting ε as 4 while we do not violate the message latency requirement. Therefore, the reverse engineering approach would be suitable for adjusting the latency affection factor.Figure 8
Energy-delay product according to the latency affection factor.


## 4.1. Wake-Up Probability

Figure1 shows the wake-up probability of a sensor node by varying the node cycle time. Since the basic cycle time of X-MAC is 4
T, a node with X-MAC has 3
T sleep period. In X-MAC, each node wakes up according to the predefined schedule. The wake-up probability of a node for each T is 0 or 1. Unlike X-MAC, X-MAC
G
a
m
e uses the probabilistic wake-up approach. Starting from a sleep state, the wake-up probability of a node is gradually increased until the node actually wakes up.Figure 1
The wake-up probability according to time elapse.According to the results, a node withX-MAC
G
a
m
e wakes up only 2 times during 20
T while a node with X-MAC wakes up 5 times. The average sleep period of X-MAC
G
a
m
e is 6.58
T while X-MAC has 3
T sleep period. In other words, X-MAC
G
a
m
e can reduce the number of unnecessary wake-up operations when there is no traffic.Note that a node withX-MAC
G
a
m
e maintains the wake-up state when the cycle time changes from 23
T to 37
T. These continuous wake-up states represent that the node participates in communications. The reason why the X-MAC
G
a
m
e node consumes 15
T cycles to deliver a single 10-packet message is that the node suffered from transmission failures and the sleep delay due to the sleep state of a receiver.


## 4.2. Latency Performance

Figure2 shows the network throughput as time passes. Since nodes which participate in communications wake up at every minimum cycle time T in X-MAC
G
a
m
e, X-MAC
G
a
m
e can deliver more packets than X-MAC during the same interval. It means that X-MAC
G
a
m
e can effectively deliver burst traffic while X-MAC suffers from the accumulation of the sleep delay. According to the results, both X-MAC and X-MAC
G
a
m
e show a uniform distribution of the network throughput since we generate events randomly over the simulation time. When there are multiple events, the throughputs of two protocols reached a peak, which is proportional to the number of simultaneous transmissions.Figure 2
The network throughput according to time elapse.Figure3 shows the average message latency according to the hop distance from a source to a destination. As shown in Figure 1, the average sleep period of X-MAC
G
a
m
e is 6.58
T while X-MAC has 3
T sleep period. This suggests that the sleep control game can substantially reduce the idle listening overhead as much as 54.5% by eliminating unnecessary wake-up operations. However, the average message latency of X-MAC
G
a
m
e is slightly longer than that of X-MAC. Since nodes in X-MAC
G
a
m
e can adjust their wake-up schedules according to the traffic condition, they can adaptively decide their wake-up either to reduce idle listening or to reduce the sleep delay depending on traffic.Figure 3
The average message latency according to hop counts.Figure4 shows the distribution of the packet latency of single hop communications. Since X-MAC uses asynchronous wake-up scheduling with 300 ms cycle time, the difference between the wake-up times of two nodes causes the packet latency to be concentrated at the interval between 0.3 s and 0.5 s. Except the first packet of a message, other packets may suffer from the buffering delay. Therefore, the buffering delay makes X-MAC to have the second major concentration interval of [0.6 s, 0.85 s].Figure 4
The distribution of the packet latency for a single hop communication.Like X-MAC,X-MAC
G
a
m
e has two concentration intervals: [0.1 s, 0.2 s] and [0.4 s, 0.7 s]. Since X-MAC
G
a
m
e nodes increase the sleep period when there is no traffic, the sleep delay before transmitting the first packet of a message increases. Therefore, the latencies for the first packet of a message concentrate on [0.4 s, 0.7 s]. In X-MAC
G
a
m
e, each node that participates in a communication wakes up at every minimum cycle time T until the communication ends. This continuous wake-up state results in shorter buffering delay than X-MAC. Therefore, the most of the packet latencies are distributed between 0.4 s and 0.7 s.When a source generates multiple messages, the latencies of the following messages can be reduced since nodes on the common routing path already wake up after reporting the first message. Therefore,X-MAC
G
a
m
e has the second concentration period of [0.1 s, 0.2 s]. This second concentration period may be dominant as the number of simultaneous events increases.According to the results of Figures3 and 4, X-MAC
G
a
m
e has comparable performance while it keeps lower duty cycle than X-MAC. Moreover, X-MAC
G
a
m
e can effectively deal with burst traffic, which is common traffic pattern in WSNs. This suggests that the sleep control game can effectively reduce energy consumption due to unnecessary wake-up operations without sacrificing the communication performance.


## 4.3. Energy Consumption

Figure5 shows the average per-node energy consumption as time passes. From our simulations we find that the communication traffic is not the dominant source of the energy consumption. Even with heavy traffic, idle listening is still the dominant energy waste source [1]. Our results show that X-MAC consumes 87.7% of the total dissipated energy for idle listening when the event rate is 0.1% per T. The energy consumption due to idle listening accounts for 73.7% of the total when we increase the event rate by 0.5% per T.Figure 5
The average energy consumption according to time elapse.When there is no traffic,X-MAC
G
a
m
e consumes only 31.1% energy of X-MAC. Since this result shows the accumulation of the average energy consumption, the slope of graph varies according to the duty cycle of a sensor node. In addition, the dynamic wake-up scheduling approach of X-MAC
G
a
m
e also reduces the energy consumption due to overhearing since the approach reduces the chance for adjacent nodes to wake up at the same cycle by waking up only the nodes in a communication path more frequently. When the event rate is 0.1% per T, X-MAC
G
a
m
e consumes additional 0.165 J per node to deliver the traffic while X-MAC requires 0.205 J per node. X-MAC
G
a
m
e can save 19.5% of the energy consumption for communications by removing energy wastes due to overhearing.


## 4.4. Impact of the Latency Affection Factor

Figure6 shows the average message latency as we vary the latency affection factor, ε. According to (18), the wake-up probability is inversely proportional to the latency affection factor. In other words, we can reduce the message latency by reducing the latency affection factor. However, if we reduce the factor, the wake-up probability increases, and nodes will consume more energy for idle listening.Figure 6
The average message latency according to the latency affection factor,ε.Figure7 shows the average energy consumption according to the latency affection factor. As we discussed above, the small latency affection factor increases the wake-up probability. Therefore, the number of wake-up operations and the average energy consumption per node increase.Figure 7
The average energy consumption according to the latency affection factor,ε.As shown in Figures6 and 7, there is a tradeoff between message latency and energy consumption. Figure 8 shows the energy-delay product according to the latency affection factor, ε. Note that the latency affection factor is influenced by various environmental conditions such as the number of neighbors, event rate, the performance requirements of an application, and channel quality. In our experiments, the optimal latency affection factor is 2.37 from the performance viewpoint. However, the optimal latency affection factor is not always the best selection. If we assume that the message latency requirement of an application is bigger than 10 s in these simulations, we can save more energy by setting ε as 4 while we do not violate the message latency requirement. Therefore, the reverse engineering approach would be suitable for adjusting the latency affection factor.Figure 8
Energy-delay product according to the latency affection factor.


## 5. Conclusions

In this paper, we introduce a novel game theoretic MAC approach to improve the energy efficiency of WSNs. Our scheme adjusts nodes’ wake-up schedules dynamically by exploiting the wake-up probability based on the game theory, which is an efficient tool for analyzing the interaction between multiple independent rational players. To model the interaction between sensor nodes, we redefine a sleep control game as a modified version of the Prisoner’s Dilemma. Payoff function of the sleep control game considers the expected traffic volume, network condition, and the expected message latency.The major contribution of this paper is that it introduces a mathematical approach to control the duty cycle of a sensor node while the conventional researches exploit a heuristic approach. With the detailed packet level simulations, we confirm that the sleep control game can effectively reduce energy consumption without sacrificing the network performance. Furthermore, the sleep control game can effectively deal with burst traffic and it is also suitable for massive sensor network with inexpensive sensor nodes.



---

*Source: 3085408-2016-03-15.xml*