Game-Theoretic Based Distributed Scheduling Algorithms for Minimum Coverage Breach in Directional Sensor Networks

Abstract

A directional sensor network, where a lot of sensors are intensively and randomly deployed, is able to enhance coverage performances, since working directions can be partitioned into different K covers which are activated in a round-robin fashion. In this paper, we consider the problem of direction set K-Cover for minimum coverage breach in directional sensor networks. First, we formulate the problem as a game called direction scheduling game (DSG), which we prove as a potential game. Thus, the existence of pure Nash equilibria can be guaranteed, and the optimal coverage is a pure Nash equilibrium, since the potential function of DSGs is consistent with the coverage objective function of the underlying network. Second, we propose the synchronous and asynchronous game-theoretic based distributed scheduling algorithms, which we prove to converge to pure Nash equilibria. Third, we present the explicit bounds on the coverage performance of the proposed algorithms by theoretical analysis of the algorithms' coverage performance. Finally, we show experimental results and conclude that the Nash equilibria can provide a near-optimal and well-balanced solution.

1. Introduction

In recent years, wireless sensor networks (WSNs) have attracted much attention as the promising platform for many applications, such as environmental monitoring and battlefield surveillance [1]. As a fundamental problem for WSNs, coverage optimization has been explored thoroughly in networks based on an omnidirectional sensing model [2]. Recently, with the advent and introduction of video sensors, ultrasonic sensors, and infrared sensors, coverage control algorithms for directional wireless sensors networks (dWSNs) have become an active subject and the state of the art is well surveyed in [3].

Power conversation is still a critical issue in dWSNs since the directional sensors in the network are usually battery-powered and nonrechargeable devices. Therefore, designing coverage optimization algorithms with energy efficiency is quite challenging for successful applications of dWSNs. One approach to meeting these challenges is to partition the working directions of sensors into K covers. By activating a different cover at each time slot and cyclically shifting through these covers, thereby, the network's lifetime can be extended effectively by a factor of K [4].

Some efforts have recently been devoted to the research of coverage optimization with energy efficiency for directional sensor networks. For example, Ai and Abouzeid [5] proposed a directional sensing model, where a sensor is allowed to work in several directions, and the objective is to find a minimal set of directions that can cover all targets. Cai et al. [6] defined the multiple directional cover set problem of organizing the directions of sensors into a group of nondisjoint cover sets to extend the network lifetime, in order to maximize the network lifetime of a directional sensor network. The network lifetime is defined as the time duration when each target is covered by the working direction of at least one active sensor. Following the work in [6], Wen et al. [7] gave the method for prolonging the lifetime of networks based on the combination of equitable direction optimization algorithm and the neighbors sensing scheduling protocol.

Generally, the aforementioned work is mainly to maximize the network lifetime of directional sensor networks while covering all targets, which is quite strict for general coverage problems. Sometimes, due to energy constraint, coverage breach [8] (i.e., targets are not covered) may occur if available working directions in a cover are not enough to cover all the targets. Instead of finding the maximum number of directional covers for complete target coverage, the problem of direction set K-Cover for minimum coverage breach (dKC-MCB) is reduced to schedule the working directions into K covers (K is predefined) to minimize the coverage breach. Although considerable research work has been devoted to the problem of set K-Cover for minimum coverage breach in omnidirectional sensing model [4, 9, 10], to our knowledge, few research efforts have been devoted to the problem of dKC-MCB. Even Yang et al. [11] dealt with the problem of minimum coverage breach under lifetime constraints in directional sensor network by formulating the problem as an integer programming and solving the problem by centralized greedy algorithms.

Although the existing research works have achieved some success on coverage optimization with energy efficiency in directional sensor network, some challenges still remain unanswered, especially for the problem of dKC-MCB. As mentioned in the paper [11], since the directional sensors are energy constrained, distributed coverage optimization algorithms need to be exploited where a sensor takes coverage optimization decisions independently, based purely on communications with its neighbors.

Game theory [12] is a mathematical theory about modeling and analyzing the strategic interactions among intelligent, rational decision makers. Recently, game theory is beginning to emerge as a powerful tool for the design optimization algorithms that can be distributed across many decision makers [13]. The core advantages of game theory for distributed optimization lie in that it provides a hierarchical decomposition between the distribution of the optimization problem (game design) and the specific local decision rules (distributed algorithms). Particularly, if the game is designed as a potential game [14], then there is a possibility that local decision dynamics can achieve convergence to pure Nash equilibrium which coincides with a desirable outcome of the original optimization problem.

Inspired by the previous discussion, in this paper, the problem of dKC-MCB is formulated as a game. Two game-theoretic based distributed algorithms are proposed to solve the problem. Specifically, the principal contributions of this paper are as follows.

• (1)

We first formulate dKC-MCB as a game: directions scheduling game (DSG). Sensors, as players of the game, interact with each other. Each sensor makes decisions independently to maximize its individual coverage utility. The utility for a sensor is defined as the sum of the marginal coverage contribution of working directions to networks coverage.

(2)

We then prove that DSG is a potential game, whose potential function is the same as the optimization objective function of dKC-MCB. This correspondingly enables the design of a coverage optimization scheme that induces the equilibrium of a DSG consistence with the optimal coverage of the underlying network objective. Moreover, this consistency allows us to establish near-optimal performance for sensor dynamics applied to the original network coverage optimization, since the natural sensors' utility-update dynamics converge to a Nash equilibrium.

(3)

We propose the synchronous and asynchronous distributed scheduling algorithms, which are proved to converge to pure Nash equilibria. Further, we analyze the coverage performance of the distributed algorithms from the theoretic perspective. We then present the explicit bounds on the coverage performance of both synchronous and asynchronous distributed algorithms.

2. Preliminaries

Game theory [12] is a mathematical tool that analyzes the strategic interactions among rational decision makers. Three major components in a strategic-form game model $G=〈N,(A_i{)}_{i\in N},(u_i{)}_{i\in N}〉$ are as follows.

• (1)

N is a finite set of n players.

(2)

$\mathbf{A}=A_1\times A_2\times \cdots \times A_n$ , where $A_i$ is a finite set of actions (or pure strategies) available to player i. For any set X, let $\Pi (X)$ be the set of all probability distributions over X. Then the set of mixed strategies for player i is $s_i\in S_i=\Pi (A_i)$ . A mixed-strategy profile $\mathbf{s}\in S_1\times \cdots \times S_n$ is Cartesian product of the individual mixed strategy. A vector $\mathit{a}=(a_1,\dots ,a_n)\in \mathit{A}$ is called a pure-strategy profile, often denoted by $\mathbf{a}=(a_i,{\mathbf{a}}_{-i})$ , where $a_i$ is a strategy of player i and ${\mathbf{a}}_{-i}$ is the strategy vector of other n-1 players.

(3)

$u_i(\mathbf{a}):\mathbf{a}\mapsto \mathfrak{R}$ is a real value utility function of player i. The utility function $u_i(\mathbf{a})$ measures the outcome of a player at a profile a. In a game, a player chooses the proper actions against other players to maximize its individual utility.

A Nash equilibrium (NE) is a stable strategic profile where no player gets any incentive to unilaterally deviate from this profile. Thus, a Nash equilibrium in some sense is a reasonable outcome of a game. Following, we present the definition of a Nash equilibrium based on the definitions of the players' best response.

Definition 1 (see [12]).

A best response for a player i to a mixed-strategy profile ${\mathit{s}}_{-i}$ is a mixed strategy $s^{*}\in S_i$ such that $u_i(s_i^{*},{\mathbf{s}}_{-i})\ge u_i(s_i^{},{\mathbf{s}}_{-i})$ for all strategies $s_i^{}\in S_i$ .

Definition 2 (see [12]).

A best response for a player i to a pure-strategy profile ${\mathbf{a}}_{-i}$ is a pure strategy $a^{*}\in A_i$ such that $u_i(a_i^{*},{\mathbf{a}}_{-i})\ge u_i(a_i^{},{\mathbf{a}}_{-i})$ for all strategies $a_i^{}\in A_i$ .

Definition 3 (see [12]).

A mixed-strategy profile $\mathbf{s}=(s_1,\dots ,s_i,\dots ,s_n)$ is a Nash equilibrium, if, for all $i\in N$ , $s_i$ is a best response to the profile s.

Definition 4 (see [12]).

A pure-strategy profile $\mathbf{a}=(a_1,\dots ,a_i,\dots ,a_n)$ is a Nash Equilibrium, if, for all $i\in N$ , $a_i$ is a best response to the profile a.

With respect to the existence of Nash equilibria of a game, Nash [12] proved that every game with a countable number of players and strategy set at least has a mixed strategy Nash equilibrium. However, in general, mixed Nash equilibrium only implies stable probability distributions over profiles, not the fixed play of a particular joint action profile. This type of uncertainty is unacceptable in many applications, such as our direction scheduling scenario. Instead, in this paper, we focused on the game with pure Nash equilibria. However, pure Nash equilibria are not available in every game. Recently, potential games, which were introduced by Monderer and Shapley [14], received increasing attention since they possess some desirable properties for engineering application scenario [15, 16], such as admitting a pure-strategy NE and best response dynamics can achieve the convergence to a pure-strategy NE.

Definition 5 (see [14]).

A game $G=〈N,(A_i{)}_{i\in N},(u_i{)}_{i\in N}〉$ is a potential game if there exists a potential function $\Phi :\mathbf{A}\mapsto \mathfrak{R}$ such that, for for all $i\in N$ , all ${\mathbf{a}}_{-i}\in {\mathbf{A}}_{-i}$ and $a_i,a_i^{\prime }\in A_i$ :

$$\begin{array}{cc}& u_i\left(a_i^{\prime },{\mathbf{a}}_{-i}\right)-u_i\left(a_i,{\mathbf{a}}_{-i}\right)=\Phi \left(a_i^{\prime },{\mathbf{a}}_{-i}\right)-\Phi \left(a_i,{\mathbf{a}}_{-i}\right).\end{array}$$

(1)

In a potential game, the change in a player's payoff that results from a unilateral change in strategy equals the change in the potential function. When formula (1) is satisfied, the game is called a potential game with the potential function $\Phi (·)$ . In a potential game, the set of pure Nash equilibria can be found by locating the local optima of the potential function, since the incentives of all players are mapped into one function. Thus, we have the following theorem.

Theorem 6 (see [12]).

Every potential game with finite strategies space at least has a pure-strategy Nash equilibrium [14].

In addition to the existence of Nash equilibria, the quality of NE also needs to be considered. The concept of price of anarchy (PoA) [17] was introduced to measure the quality of Nash equilibria. Formally, let $\gamma (\mathbf{a}):\mathbf{a}\mapsto \mathfrak{R}$ be the social objective function and let ${\mathbf{a}}^{OPT}$ be a social optimum if and only if ${\mathbf{a}}^{OPT}=\arg \hspace{0.17em}{\max }_{\mathbf{a}\in \mathbf{A}}\gamma (\mathbf{a})$ .

Definition 7 (see [17]).

The price of anarchy of a game G is defined as $\text{PoA}(G)={\max }_{\mathbf{a}\in \mathbf{A}}(\gamma ({\mathbf{a}}^{\text{OPT}})/\gamma (\mathbf{a}))$ .

Intuitively, the PoA of a game is the ratio of the objective social value of the worst possible Nash equilibrium to the value of the social optimum.

3. Problem Statement

In this section, we formally give the definitions of the problem of direction set K-Cover for minimum coverage breach in DSNs. We consider a directional sensor network of n directional sensors and m targets. Let $S=\{s_1,\dots ,s_n\}$ and $O=\{o_1,\dots ,o_m\}$ denote the directional sensors and the target set, respectively. Let $D=\{D_1,\dots ,D_n\}$ be the set of directions of all sensors. Each sensor $s_i$ has a set of directions $D_i=\{d_{i,j}\hspace{0.17em}|\hspace{0.17em}j=\mathrm{1,2},\dots ,w\}$ . Without loss of generality, $l_i$ is the initial lifetime for each sensor $s_i$ , which is the time duration when the sensor is in the active state all the time. $t_k$ is the kth time slot of sensor networks and $\text{TL}={\sum }_{k=1}^K{t}_k$ is the total lifetime of sensor networks. Being similar to the problem of set K-Cover for minimum coverage breach defined in [2], the problem of dKC-MCB is formally identified as follows.

Definition 8.

A direction schedule of directional sensor networks is a set of ordered pairs, $(A_k,t_k)$ , $k=\mathrm{1,2},\dots ,K$ , in which $A_k\subset D$ is the set of working directions in time slot $t_k$ . At a time slot $t_k$ , any sensor $s_i$ has at most one working direction; that is, for all $i,k,\left|D_i\cap A_k\right|\le 1$ . Since the lifetime for each sensor is limited, for any sensor $s_i$ , one always has

$$\begin{array}{cc}& {{\displaystyle \sum }}_{k=1}^K{z}_{i,k}·t_k\le l_i,\hspace{1em}\{\begin{array}{cc}{z}_{i,k}=1,\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}\left|D_i\cap A_k\right|=1\hfill \\ z_{i,k}=0,\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}\left|D_i\cap A_k\right|=0.\hfill \end{array}\end{array}$$

(2)

Definition 9.

Assume that $(A_k,t_k)$ , $k=\mathrm{1,2},\dots ,K$ is a direction schedule. The total network lifetime is given by $\text{TL}={\sum }_{k=1}^K{t}_k$ . Let $F(A_k)$ be the set of coverage targets covered by the set of active directions $A_k$ in time slot $t_k$ . O is a target set. Total coverage breach is defined as ${\sum }_{k=1}^K{t}_k(\left|O\right|-\left|F(A_k)\right|)$ . An average coverage breach rate is defined as ${\sum }_{k=1}^K{t}_k(\left|O\right|-\left|F(A_k)\right|)/{\sum }_{k=1}^K{t}_k$ .

Based on the definitions of direction schedule and coverage breach, we give the definition of dKC-MCB.

Definition 10.

Give a positive integer K and network lifetime threshold $T_{\text{th}}>0$ , and construct a direction schedule $(A_k,t_k)$ , $k=\mathrm{1,2},\dots ,K$ , such that the network lifetime is not less than $T_{\text{th}}$ ; that is ${\sum }_{k=1}^K{t}_k\ge T_{\text{th}}$ and total coverage breach ${\sum }_{k=1}^K{t}_k(\left|O\right|-\left|F(A_k)\right|)$ is minimized. Equivalently, the problem of direction set K-Cover for minimum coverage breach is also defined to maximize ${\sum }_{k=1}^K{t}_k\left|F(A_k)\right|$ .

Based on the results in [11], we know that the problem of dKC-MCB is NP-complete.

4. Direction Scheduling Game

A direction scheduling game is a triple $\text{DSG}=〈S,(A_i{)}_{s_i\in S},(u_i{)}_{s_i\in S}〉$ .  S is a set of players, in which a player $s_i\in S$ is a directional sensor. $A_i$ is the set of direction scheduling strategies of $s_i$ . A strategy $a_i\in A_i$ is an allocation of working directions of $s_i\in S$ among the time slots and can be described as a set of ordered pairs $a_i=\{〈d_{i,j},t_k〉\hspace{0.17em}|\hspace{0.17em}{d}_{i,j}\in D_i,\mathrm{\hspace{0.17em}\hspace{0.17em}}k=\mathrm{1,2},\dots ,K\}$ . Due to the limitation of energy, a feasible strategy $a_i$ should satisfy the next properties. (1) For all $〈d_{i,j}\ne \varnothing ,t_k〉\in a_i$ , ${\sum }_{k=1}^K{t}_k\le l_i$ ; that is, whole working lifetime of the sensor $s_i$ is less than $l_i$ . (2) At a time slot $t_k$ , there is at most a working direction of $s_i$ . At a time, direction scheduling strategies of all sensors are composed of a direction scheduling profile, which is denoted by $\mathbf{a}=(a_1,\dots ,a_i,\dots ,a_n)$ . At the profile a, the coverage utility of a sensor $s_i$ is defined as follows.

Definition 11.

At a profile a and a time slot $t_k$ , the working direction of sensor $s_i$ is denoted by $d_{i,k}^{\mathbf{a}}\in D_i$ . If there is no working direction for $s_i$ at time slot $t_k$ , $d_{i,k}^{\mathbf{a}}=\varnothing$ . Given a profile a, the coverage utility of a sensor $s_i$ is denoted by $u_i(\mathbf{a})$ and then defined as follows:

$$\begin{array}{cc}& u_i\left(\mathbf{a}\right)={{\displaystyle \sum }}_{k=1}^K\left(F\left(A_k^{\mathbf{a}}\right)-F\left(A_k^{\mathbf{a}}\setminus \left\{d_{i,k}^{\mathbf{a}}\right\}\right)\right).\end{array}$$

(3)

Intuitively, the utility function is defined as the sum of marginal coverage contribution of the sensor's working directions to networks coverage. In a direction scheduling game, a sensor tries to activate its directions in time slots where the sensor obtains most marginal coverage contribution. Obviously, sensors interacted with each other by maximizing each individual utility. Thus, the game is actually a dynamical interaction process. Would the interaction dynamics finally terminate and converge to a pure Nash equilibrium? In order to answer this question, we discuss the mathematical properties of direction scheduling games.

In a direction scheduling game, the set of working directions $A_k$ in a time slot $t_k$ is determined by the profile a. Thus, at a profile a, the set of working directions in a time slot $t_k$ is denoted by $A_k^{\mathbf{a}}$ and the objective function of the problem of dKC-MCB is denoted by $Z(\mathbf{a})={\sum }_{k=1}^K{t}_k\left|F(A_k^{\mathbf{a}})\right|$ . In what follows, we prove that direction scheduling game is a class of potential games, the potential function of which is $Z(\mathbf{a})$ , that is, the objective functions of dKC-MCB.

Theorem 12.

A direction scheduling game is a potential game with the potential function $\Phi (\mathbf{a})=Z(\mathbf{a})$ .

Theorem 13.

A pure Nash equilibrium of direction scheduling game is a local optimal solution of the objective function $Z(\mathbf{a})={\sum }_{k=1}^K{t}_k\left|F(A_k^{\mathbf{a}})\right|$ .

Theorem 14.

An optimal solution of the problem of dKC-MCB is a pure Nash equilibrium of a direction scheduling game.

We give the proofs of Theorems 12, 13, and 14 in Appendices A.1, A.2, and A.3, respectively.

Some interesting mathematical properties for DSGs to solve the problem of dKC-MCB are well established by the results of Theorems 12, 13, and 14. Specifically, a DSG is proved to be a class of potential games by Theorem 12. From the previous result of Theorem 6, a DSG at least admits a pure Nash equilibrium. The connection between the solutions of dKC-MCB and pure equilibria of DSGs are described by Theorems 13 and 14. In particular, the consistence between the potential function and the objective function of dKC-MCB allows us to establish a near-optimal performance for local decision dynamics applied to the original network coverage optimization.

5. Distributed Scheduling Algorithms for Minimum Coverage Breach

In this section, based on the aforementioned properties of DSGs, we propose both synchronous and asynchronous distributed scheduling algorithms for the problem of dKC-MCB. From the perspective of game theory, both synchronous and asynchronous algorithms are actually some kind of best response dynamics of DSGs.

Specifically, n sensors are assumed to be randomly deployed in a target area. A sensor is supposed to know its location and be aware of the location of its neighbors through local communications. A sensor has a sensing range $R_s$ and a communication range $R_c$ . In this paper, we assume the communication range of a sensor node is at least as twice as the sensing range; that is, $R_c\ge 2R_s$ . Denote $S_i^u$ as the neighbors of a sensor $s_i$ . In particular, for a sensor $s_j\in S_i^u$ , the distance between $s_j$ and $s_i$ is less than $2R_s$ . Actually, the utility of a sensor $s_i$ depends on the strategies of the sensors within $S_i^u$ . In other words, $s_i$ obtains the sum of marginal coverage contribution only through local communications with the sensors within $S_i^u$ . Thus, both synchronous and asynchronous algorithms are based on local information.

In a synchronous distributed algorithm, at each time step, sensors are considered to be able to synchronize their actions with one another according to a system clock. We also propose an asynchronous distributed algorithm for the case that maintaining tight clock synchronization is sometimes difficult. In asynchronous distributed algorithm, each sensor maintains its individual time clock. At a time step, only one sensor has an opportunity to update its direction scheduling strategy.

5.1. Synchronous Distributed Scheduling Algorithm

At each time step of the synchronous distributed scheduling algorithm (SDA), all the sensors are assumed to be able to synchronize their actions with one another according to a system clock. The algorithm will terminate based on a mark $END=\neg (Updat{e}_1\vee \cdots \vee Updat{e}_n)$ .

Definition 15.

Let $Updat{e}_i$ be the mark of strategy update for a sensor $s_i$ . If a sensor $s_i$ is able to increase utility by updating its strategy, $Updat{e}_i$ is set to be true. Otherwise, $Updat{e}_i$ is set to be false. Thus, the termination mark of the algorithm is defined as the following Boolean symbol $END=\neg (Updat{e}_1\vee \cdots \vee Updat{e}_n)$ .

Specifically, if all the sensors send a message of update false to the system, the algorithm terminates. The synchronous distributed algorithm is shown in Algorithm 1.

Algorithm 1: Synchronous distributed algorithm (SDA).

Input: An initial strategy of $s_i$ ; A system time clock $t=0$ ; The mark of strategy update $Updat{e}_i\leftarrow true$ .

Output: A Nash equilibrium strategy of $s_i$  :  $a_i^{\mathrm{*}}$ .

(1) WHILE   $END=false$   DO

(2)   Communicate with $\forall s_j\in S_i^u$ to obtain the strategy of $s_j$ ;

(3)   Based on the definition of utility function, compute:

(4)    ${\mathrm{\Delta }}_i\left(\mathbf{a}\left(t\right)\right)=\underset{a_i^{\prime }}{\max }\left(u_i(a_i^{\prime },\mathbf{a}(t{)}_{-i})-u_i(a_i^{},\mathbf{a}(t{)}_{-i})\right)$

(5)   and $b{r}_i\left(\mathbf{a}\left(t\right)\right)=\underset{{a_i^{\prime }}_{}}{\arg \max }\left(u_i(a_i^{\prime },\mathbf{a}(t{)}_{-i})-u_i(a_i^{},\mathbf{a}(t{)}_{-i})\right)$ ;

(6)   IF   ${\mathrm{\Delta }}_i\left(\mathbf{a}\left(t\right)\right)>0$   THEN

(7)     Broadcasting ${\mathrm{\Delta }}_i\left(\mathbf{a}\left(t\right)\right)$ to $\forall s_j\in S_i^u$ ;

(8)     IF   ${\mathrm{\Delta }}_i(\mathit{a}(t))>\text{max}\left\{{\mathrm{\Delta }}_j\left(\mathbf{a}\left(t\right)\right)\hspace{0.17em}|\hspace{0.17em}\forall s_j\in S_i^u\right\}$   THEN

(9)        $a_i\left(t\right)\leftarrow b{r}_i\left(\mathbf{a}\left(t\right)\right)$ ; Sending $Updat{e}_i\leftarrow true$ to the system;

(10)     END  IF

(11)     ELSE

(12)      Broadcasting ${\mathrm{\Delta }}_i\left(\mathbf{a}\left(t\right)\right)=0$ to $\forall s_j\in S_i^u$ ; Sending $Updat{e}_i\leftarrow false$ to the system;

(13)    END  IF

(14)   END  WHILE

Theorem 16.

A synchronous distributed scheduling algorithm converges to a pure Nash equilibrium.

Proof.

First, we prove that, at a time step of Algorithm 1, if more than one sensor is able to increase utility by updating their strategies, these sensors should be independent of one another on utility.

Let $\mathbf{a}(t)$ be the profile in a time step t. Denote the maximal increment of utility of sensor $s_i$ at $\mathbf{a}(t)$ by ${\Delta }_i(\mathbf{a}(t))$ ; ${\Delta }_i(\mathbf{a}(t))={\max }_{a_i^{\prime }}(u_i(a_i^{\prime },\mathbf{a}{(t)}_{-i})-u_i(a_i,\mathbf{a}{(t)}_{-i}))\ge 0$ . When Algorithm 1 is not terminated, END is false. From the definition of END, there is at least one sensor updating its strategy. Assume that more than two sensors update strategies at the time step. From line 6 to 10 of Algorithm 1, two utility-dependent sensors are not able to update strategies at the same time step. Actually only the sensor of the highest increments on utility has an opportunity to update a strategy. In other words, when SDA algorithm proceeds, if more than one sensor updates strategies simultaneously, then these sensors should be independent of one another on coverage utility.

Second, we prove that when Algorithm 1 proceeds, the network coverage monotonically increases.

Since direction scheduling game is a potential game, as described in (1), the change in a sensor's utility that results from a unilateral change at a profile equals the change in a global potential function. Moreover, based on Theorem 12, the potential function of direction scheduling game is the same as the optimization objective function; that is, $\Phi (\mathbf{a})=Z(\mathbf{a})$ . Therefore, the increment in a sensor's utility that results from a unilateral change at a profile equals the increment in a network coverage.

If Algorithm 1 is not terminated, $\exists s_i\in S$ , ${\Delta }_i(\mathbf{a}(t))>0$ . Based on (1) and $\Phi (\mathbf{a})=Z(\mathbf{a})$ , ${\Delta }_i(\mathbf{a}(t))>0$ results in the increase of $\Phi (\mathbf{a})=Z(\mathbf{a})={\sum }_{k=1}^K{t}_k\left|F(A_k^{\mathbf{a}})\right|$ . Thus, network coverage monotonically increases. When there is more than one sensor that has opportunity to increase utility by updating strategies, from results of the first part of this proof, these sensors should be independent of one another on coverage utility. Thus, the increment of $Z(\mathbf{a})$ equals the sum of increment on utility resulting from the sensors updating strategies. Also, in this case, network coverage monotonically increases.

Since $Z(\mathbf{a})$ is finite, Algorithm 1 finally converges. At the time, no sensors are able to update strategies to increase utility; a pure Nash equilibrium is achieved.

5.2. Asynchronous Distributed Scheduling Algorithm

In the asynchronous distributed scheduling algorithm (ADA), we use the asynchronous time model [18], which is well matched to the distributed nature of sensor networks. In particular, each sensor $s_i$ has an independent clock $c{k}_i$ whose “ticks” are distributed as a rate 1 Poisson process. A mark of updating strategy $U{T}_i$ is set for each sensor $s_i$ to permit updating its strategy. $U{T}_i$ is set to be true when $c{k}_i$ ticks and to be false at other time. The asynchronous distributed algorithm is shown in Algorithm 2.

Algorithm 2: Asynchronous distributed algorithm (ADA).

Input: An initial strategy of $s_i$ ; $U{T}_i\leftarrow false$ ; The mark of strategy update $Updat{e}_i\leftarrow true$ .

Output: A Nash equilibrium strategy of $s_i$  :  $a_i^{\mathrm{*}}$ .

(1) WHILE   $END=false$ and $U{T}_i=true$   DO

(2)    Communicate with $\forall s_j\in S_i^u$ to obtain the strategy of $s_j$ ;

(3)    Based on the definition of utility function, compute:

(4)     ${\mathrm{\Delta }}_i\left(\mathbf{a}\right)=\underset{a_i^{\prime }}{\max }\left(u_i(a_i^{\prime },{\mathbf{a}}_{-i})-u_i(a_i^{},{\mathbf{a}}_{-i})\right)$

(5)    and $b{r}_i\left(\mathbf{a}\right)=\underset{{a_i^{\prime }}_{}}{\arg \max }\left(u_i(a_i^{\prime },{\mathbf{a}}_{-i})-u_i(a_i^{},{\mathbf{a}}_{-i})\right)$ ;

(6)    IF   ${\mathrm{\Delta }}_i\left(\mathbf{a}\right)>0$   THEN

(7)       $a_i\leftarrow b{r}_i\left(\mathbf{a}\right)$ ; Sending $Updat{e}_i\leftarrow true$ to the system;

(8)     ELSE

(9)     Sending $Updat{e}_i\leftarrow false$ to the system;

(10)     END  IF

(11)   END  WHILE

Theorem 17.

An asynchronous distributed scheduling algorithm converges to a pure Nash equilibrium.

Proof.

Assume that n sensors are deployed in a target area. Each sensor $s_i$ has an independent clock $c{k}_i$ whose “ticks” are distributed as a rate 1 Poisson process. $s_i$ has an opportunity to update its strategy when the mark $U{T}_i$ is true. Since tick times are exponentially distributed, independent among sensors and independent across time, the tick time model can be equivalently formulated in terms of a single global clock ticking according to a rate n Poisson process. By letting ${\{T_k\}}_{k\ge 0}$ denote the arrival times for this global clock, then the individual clocks can be generated from the global clock by randomly assigning each to the sensors according to a uniform distribution. Based on properties of the Poisson process, at each arrival time of ${\{T_k\}}_{k\ge 0}$ , there is only a sensor that has an opportunity to update its strategy.

Let $\mathbf{a}(t)$ be the profile in a time step t. Denote ${\Delta }_i(\mathbf{a}(t))$ as the maximal increment of utility of sensor $s_i$ at $\mathbf{a}(t)$ ; that is, ${\Delta }_i(\mathbf{a}(t))={\max }_{a_i^{\prime }}(u_i(a_i^{\prime },\mathbf{a}{(t)}_{-i})-u_i(a_i,\mathbf{a}{(t)}_{-i}))\ge 0$ . When Algorithm 2 proceeds, END is false. There is a sensor $s_i$ updating its strategy and ${\Delta }_i(\mathbf{a}(t))>0$ . Since direction scheduling game is a potential game, based on (1) and $\Phi (\mathbf{a})=Z(\mathbf{a})$ , ${\Delta }_i(\mathbf{a}(t))>0$ results in the increase of $Z(\mathbf{a})$ . Thus, network coverage monotonically increases with the execution of Algorithm 2. Since the coverage objective function $Z(\mathbf{a})$ is finite, Algorithm 2 finally converges. At the time, no sensors are able to update strategies to increase utility and a pure Nash equilibrium is achieved.

6. The Coverage Performance Analysis of Distributed Algorithms

A direction scheduling game is a potential game with potential function $\Phi (\mathbf{a})=Z(\mathbf{a})$ . Hence, network coverage strictly increases with execution of both synchronous and asynchronous distributed algorithms. Furthermore, both synchronous and asynchronous distributed algorithms finally converge to a stable profile, that is, a pure Nash equilibrium of direction scheduling game. Moreover, from the results of Theorem 16, the optimal solution of dKC-MCB is actually a pure Nash equilibrium of DSG. However, pure Nash equilibria are not unique for a DSG. Both synchronous and asynchronous distributed algorithms are not guaranteed to converge to optimal coverage. Thus, we should obtain explicit bounds on the coverage performance of both synchronous and asynchronous distributed algorithms. In terms of algorithmic game theory, we obtain the price of anarchy (PoA) [17] of direction scheduling game to analyze the coverage performance of proposed distributed algorithms.

Definition 18.

The price of anarchy of a direction scheduling game $\text{DSG}$ is defined as

$$\begin{array}{cc}& \text{PoA}\left(\text{DSG}\right)=\underset{{\mathbf{a}}^{*}\in \mathbf{A}}{\max }\frac{Z\left({\mathbf{a}}^{\text{OPT}}\right)}{Z\left({\mathbf{a}}^{*}\right)},\end{array}$$

(4)

where $Z(\mathbf{a})={\sum }_{k=1}^K{t}_k\left|F(A_k^{\mathbf{a}})\right|$ , that is, the objective function. ${\mathbf{a}}^{\text{OPT}}$ is the optimal solution of $Z(·)$ . ${\mathbf{a}}^{*}$ is a pure Nash equilibrium of a DSG.

Intuitively, a PoA is the ratio of optimal coverage and the worst possible Nash equilibrium coverage. Theorem 19 presents the explicit bounds on PoA of a DSG strongly depending on the submodularity [19] of coverage utility function of a DSG.

Theorem 19.

The upper bound of price of anarchy of a $DSG$ is 2.

We give the proof of Theorem 19 in Appendix B.

From the result of Theorem 19, we know that at least $1/2$ optimal coverage can be obtained when synchronous and asynchronous distributed algorithms terminate.

7. Simulation Results

In this section, we evaluate the coverage performances and convergence of SDA and ADA algorithms through simulations. There are two measures for the coverage performance of algorithms. The first is the average coverage rate (ACR) of coverage optimization algorithms. ACR is an average of the coverage rate (CR) of each time slot which is the ratio between the number of targets covered by sensor networks and the number of targets located in a target area. The second is the coverage stability (CS) of coverage optimization algorithms which is measured by the variance of CRs of all time slots. The convergence is evaluated by the speed of convergence of SDA and ADA algorithms to a pure Nash equilibrium.

7.1. Experimental Demonstration of the Coverage Optimization

As an intuitive demonstration of distributed algorithms, Figure 1 shows the snapshots of coverage results of a random deployment and a SDA algorithm. In order to make the results accessible to readers, the small-scale simulations parameters are used in the demonstration. In this demonstration, $K=3$ and each sensor has 7 sensing directions and can allocate at most 2 working directions into 3 time slots. The subfigures (a), (b), and (c) of Figure 1 show coverage results of random deployment in 3 different time slots. The subfigures (d), (e), and (f) of Figure 1 show coverage results in 3 different time slots when SDA algorithm converges to a pure Nash equilibrium. As we can see from the results shown in Figure 1, coverage results of SDA algorithm obviously outperform results of random deployment.

Figure 1

The snapshots of coverage results of the random deployment and the SDA algorithm.

7.2. Coverage Performance of the Distributed Algorithms

7.2.1. Average Coverage Rate of the Distributed Algorithms

In order to evaluate the effectiveness of algorithms, we compare the coverage performance of SDA and ADA algorithms with the RANDOM algorithm and MCBLC-G algorithm. In a RANDOM algorithm, each sensor allocates randomly working directions into time slots under the constraint of its lifetime. MCBLC-G is a centralized greedy algorithm for the problem of minimum coverage breach which is developed by Yang et al. in [11]. The experiments are set up by the following settings. The target area is a $10\times 10$ size area where 50 targets are randomly located. We evaluate the coverage performance of the SDA, ADA, RANDOM, and MCBLC-G algorithms by randomly deployed $n=\mathrm{100,125,150,175,200,225,250,275,300}$ sensors with $R_s=2$ in target area, respectively. Total lifetime TL is divided equally into 6 time slots; that is, $K=6$ . Each sensor at most chooses 3 time slots to allocate its working directions; that is, $l_i\le 3$ . In order to guarantee the reliability of simulations, for each value of n, we repeat the simulations by 50 times. The ACR is finally computed by $(({\sum }_{k=1}^K{t}_k\left|F(A_k^{\mathbf{a}})\right|)/K)/50$ .

Figure 2 shows coverage performances of the SDA, ADA, RANDOM, and MCBLC-G algorithms. As we can see from Figure 2, SDA, ADA, and MCBLC-G algorithms provide similar coverage performances which are obviously better than results of the RANDOM algorithm. However, MCBLC-G is a centralized algorithm and the SDA and ADA algorithms are distributed algorithms.

Figure 2

The comparison of coverage performance of SDA, ADA, RANDOM, and MCBLC-G algorithms.

Since the potential function of direction scheduling game coincides with the coverage objective function of the problem of dKC-MCB, the coverage of sensor network increases along with the each sensor's utility increasing when SDA and ADA algorithms proceed. We can see the results from Figures 3 and 4.

Figure 3

The increasing of coverage performance of SDA algorithms.

Figure 4

The increasing of coverage performance of ADA algorithms.

7.2.2. Coverage Stability of the Distributed Algorithms

The coverage stability is another important performance measure of coverage optimization algorithms. A coverage optimization algorithm with good coverage stability can guarantee well-balanced coverage performance for every time slot. Figure 5 shows the coverage rate variance of SDA, ADA, RANDOM, and MCBLC-G algorithms. As we can see from the results of Figure 5, RANDOM algorithm randomly allocates working directions into time slots. Coverage rates among time slots cannot be guaranteed well balanced. This results in a high coverage rate variance for RANDOM algorithm. MCBLC-G algorithm has a lower coverage rate variance than RANDOM. However, the coverage rate variance of MCBLC-G is influenced by the sequence of greedy selection of sensors. Compared with RANDOM and MCBLC-G algorithms, SDA and ADA provide well-balanced coverage performance.

Figure 5

The comparison of coverage stability of SDA, ADA, RANDOM, and MCBLC-G algorithms.

7.3. Convergence of the Distributed Algorithms

A SDA (ADA) algorithm terminates when the algorithm converges to a pure Nash equilibrium. The speed of convergence to a pure Nash equilibrium of a SDA (ADA) algorithm mainly depends on two factors: the first is the number of sensors deployed in a target area. The second is the number of time slots K. As shown in Figure 6, the number of iterations for SDA algorithm increases with the number of sensors deployed in a target area. At the same time, given the number of deployed sensors, the number of iterations for SDA algorithm increases with the number of time slots K. As the number of K increases, each sensor has more choices when it decides to allocate working directions. This leads to more complicated interactions among sensors and prolongs the convergence dynamics. Similar convergence results of ADA algorithm are shown in Figure 7.

Figure 6

Convergence speed of SDA algorithms.

Figure 7

Convergence speed of ADA algorithms.

8. Conclusions

Direction scheduling algorithms with energy efficiency are always important for directional sensor network. Since directional sensors are energy constrained, distributed direction scheduling algorithms need to be exploited where a sensor takes direction scheduling decisions independently, based purely on communications with its neighbors. In this paper, the problem of directional K-Cover for minimum coverage breach (dKC-MCB) is formulated as a game: direction scheduling game (DSG). Both synchronous and asynchronous game-theoretic based distributed algorithms are proposed for solving dKC-MCB, respectively. The coverage performance of distributed algorithms is analyzed from a theoretic perspective and the explicit bounds on the coverage performance are presented. Experimental results show that our proposed algorithms can provide a near-optimal and well-balanced solution to the problem of dKC-MCB.

Game theory, particularly potential game, is beginning to emerge as a powerful tool for the design and analysis of distributed optimization algorithm [13]. However, many research challenges still remain unanswered, especially for the development of a systematic methodology for the design of distributed optimization functions that satisfies virtually any degree of locality while ensuring the desirability of the resulting equilibria. As future research work, we plan to investigate a systematic approach to distributed optimization using the framework of potential games and apply this approach to solve various real application problems.