Coverage Capacity Optimization for Mobile Sensor Networks Based on Evolutionary Games

Abstract

The optimal and distributed provisioning of high coverage capacity in mobile sensor networks is known as a fundamental but hard problem. The situation is exacerbated in a mobile wireless setting due to the dynamic coverage of a mobile sensor network resulting from continuous movement of sensors. In this paper, we propose an optimization framework for maximizing the coverage capacity in mobile sensor networks that comprise both stationary sensors (SSs) and mobile sensors (MSs). Both the intracoverage capacity and the intercoverage capacity are jointly optimized by considering the control of the power and distance between MSs and SSs and the interference among MSs. We propose a new noncooperative control algorithm that iteratively solves intracoverage capacity optimization between MSs and SSs. We also further formulate intercoverage capacity as evolutionary coalition game and present a new cooperative interference control algorithm that iteratively solves intercoverage capacity optimization among MSs. We prove the existence of a solution for iteration control equation of the power and distance and the interference to maximize the coverage capacity. Finally, we assess the performance of the proposed algorithm and show that proposed control scheme can effectively improve the average coveragecapacity in mobile sensor networks.

1. Introduction

Mobile sensor networks have emerged as a practical solution for ubiquitous coverage in broadband wireless sensor networks. It can be mapped to sensor service platforms such as mobile robots [1, 2]. In this respect, next-generation mobile sensor networks will entail an important paradigm shift toward a multitier small hybrid infrastructure in which low-cost, low-power base stations such as mobile sensors are deployed for providing short-range transmission. The coverage nodes of a mobile sensor network resulting from continuous movement of sensors nodes at different locations communicate with each other over wireless links. An important consideration in the design of a mobile sensor network is the network's ability to efficiently support high-capacity multicast applications over mobile wireless links (e.g., video streaming). Mobile sensor networks can also play a vital role in homeland security; for instance, sensor nodes can be mounted on vehicles and will move to dynamically patrol and monitor the environment. This paper addresses coverage capacity optimization issues for such applications. A typical mobile sensor network with mixed mobile devices is shown in Figure 1.

Figure 1

Typical scene of mobile sensor networks.

In a stationary sensor network, its coverage area is determined by the initial configuration and does not change over time. In a mobile sensor network, previously uncovered areas become covered as sensors move through them and covered areas become uncovered as sensors move away. As a result, the areas covered by sensors change over time. The coverage of a mobile sensor network depends not only on the initial network configurations but also on the mobility behavior of the sensors. The wireless coverage established among radios has relatively low capacities because each wireless link capacity depends not only on its own transmission power and distance between MSs and SSs but also on the channel gain and mitigating interference among mobile sensors.

The design of mobile sensor networks for high-capacity involves at least two sets of technical challenges. The first set of challenges involves dynamic coverage ability in mobile sensor networks. The second set of challenges arises due to the presence of interferences and how effectively a sensor network can mitigate interferences. This paper addresses both sets of challenges together by considering joint optimization of coverage capacity about the control of the power and distance between MSs and SSs and the interference among MSs. We focus on achieving maximum coverage capacity and proposing a framework to model and solve this optimization problem of coverage capacity in an efficient and distributed manner.

The main contributions of this paper can be summarized as follows.

• (i)

We formulate the problem of the coverage capacity optimization as an evolutionary game control for the power and distance between MSs and SSs and the interference among MSs. The optimization controls for them are integrated in a framework that represents multiarea strategies, which strikes a balance between the maximization of coverage capacity and the minimization of interference at the physical layer.

(ii)

For the control of the power and distance between MSs and SSs, we propose a new noncooperative control algorithm that iteratively solves intracoverage capacity optimization between MSs and SSs. By deducing Jacobian matrix, we prove the existence of a solution for iteration equation of the power and distance to maximize the intracoverage capacity.

(iii)

For the control of the interference among MSs, we present a new cooperative interference control algorithm using evolutionary coalition game theory that iteratively solves intercoverage capacity optimization among MSs and eliminates interference by dynamics evolution. The replicator dynamics of interference cancellation evolving in MS coalitions is given. We prove the evolutionary coalition game globally converges to the optimal solution that maximizes the intercoverage capacity under Nash equilibrium conditions.

The remainder of this paper is organized as follows. We first discuss related work in Section 2; then we propose the joint optimization framework and control algorithm, together with evolutionary game theory, to solve the coverage capacity optimization problem in Sections 3, 4, and 5. Section 6 presents the simulation. Finally, Section 7 concludes this paper.

2. Related Works

Mobile sensor coverage related topics have become an active research area. In this section, we present a brief overview of the previous work on the coverage of both the stationary and mobile sensor networks. Mobile sensors are widely studied in sensor networks for coverage improvement [3–5], load balancing, or lifetime extension [6]. The relationship between coverage area and network connectivity is investigated in [7, 8]. Most of these approaches do not consider the optimization on the intracoverage capacity and intercoverage capacity that a mobile sensor can sense. In this paper, we study the possibility of using evolutionary game to optimize coverage capacity as complex mobile sensors. In [9], the authors considered the coverage of the area and the connectivity in an unreliable wireless sensor grid-network and derived the conditions for the sensing range to ensure that an area is fully covered. In [10], the authors proposed a novel energy-efficient coverage-time optimized dynamic clustering scheme that regulates cluster radii for balanced energy consumption among CHs to maximize coverage-time. In [11], the authors proposed a minimum-cost maximum-flow based schedule algorithm to determine a movement plan for the sensors in order to maximize the sensor network coverage and minimize the number of flips. In [12], the authors defined and derived several important coverage measures that include area coverage, detection coverage, and node coverage. The coverage problem is further formulated as an optimization problem which minimizes the variance of sensors in different areas in [13]. In [14], the authors formalized the tradeoff that exists between an all-static network and a network with mobile sensors, proved necessary conditions for coverage, and proposed a distributed relocation algorithm. In [15], the authors studied the dynamic aspects of the coverage of a mobile sensor network resulting from the continuous movement of sensors and the coverage measures related to the area coverage and intrusion detection capability of a mobile sensor network. In [16], the authors took energy-efficient factors into consideration and described the coverage and connectivity issues from three aspects: coverage deployment strategy, sleep scheduling mechanism, and adjustable coverage radius in wireless sensor networks. However, [14–16] do not provide bounds of the intracoverage capacity and the intercoverage capacity for fraction of area covered or maximum network utility.

In this paper, we show that the network can be completely covered by using evolutionary game. We give bounds on the maximum coverage capacity of mobile sensors. We also provide a distributed algorithm that can achieve the optimal solution, while the algorithm in [17] is a distributed coalition formation algorithm for interference alignment algorithm, with no guarantees of optimality for intercoverage capacity. The bound on maximum intracoverage capacity in this paper is based on the noncooperative game [18, 19]. The bound on maximum intercoverage capacity in this paper is based on the cooperative game [20, 21]. In this paper, we propose a new iterative algorithm using the game theory, and it converges relatively fast to optimize intracoverage capacity. We also propose evolutionary coalition game to optimize the intercoverage capacity in mobile sensor networks, where the intercoalition interference can be mitigated via a spatial interference alignment (IA) scheme because MSs cooperate to adjust the spatial structure of their transmitted signals so as to avoid interference among themselves [17, 22, 23].

3. Coverage Capacity with Mobile Sensor Networks

3.1. System Model and Joint Optimization Framework

We assume that there are $N^s$ stationary sensors uniformly and independently scattered in the network. The number of stationary sensors is $N_A^s$ in an area A, which will be Poisson distributed with mean $\gamma A$ [24], $X_A^p\{N_A^s=i\}=(\gamma A{)}^i{e}^{-\gamma A}/i!$ . We also assume that mobile sensors $N^b$ are uniformly and independently scattered in the network. The mobile sensors have the same coverage range as stationary sensors. We assume that the mobile sensors are provisioned with sufficient energy. Finally, our goal is to guarantee that the entire field is of maximization coverage capacity. Figure 2 shows the coverage capacity area in hybrid mobile sensor networks. We present a general framework to model and solve the problem of optimization of the intracoverage capacity and the intercoverage capacity in a multihop hybrid mobile sensor network. In our framework, the utility of the overall coverage capacity is maximized subject to two groups of constraints: (i) the dependence of intracoverage capacity between MSs and SSs; (ii) the dependence of intercoverage capacity among MSs.

Figure 2

The coverage area in mobile sensor networks.

Definition 1.

Coverage capacity: it is both the intracoverage capacity between MSs and SSs and the intercoverage capacity among MSs that are jointly optimized by considering the control of the power and distance, as well as the interference.

Definition 2.

Noncooperation area: let X be noncooperation coverage capacity area for intracoverage capacity between MSs and SSs. Let $G=(V,E)$ be the network topology. Let $c^p=\{c_i^p\}$ be the set of link capacity between MSs and SSs. Let u be the transmission probability from SS to MS. Let v be the listening probability from MS to SSs. Let a set of $(c^p,u,v)$ be the noncooperation coverage capacity area between MSs and SSs such that maximization of intracoverage transmission probability can support high intracoverage capacity.

Definition 3.

Cooperative area: let Y be cooperative coverage capacity area for intercoverage capacity among MSs. Let $c^s=\{c_i^s\}$ be the set of coverage capacity on each link among MSs. Let t be the transmission rate among MSs. Let $a=\{a_i\}$ be the set of cooperative strategies. The cooperative coverage capacity area is defined as a set of $(c^s,t,a)$ among MSs such that the interference detection and cooperative strategies can support high intercoverage capacity.

This paper adopts a network utility maximization approach. We consider a concave utility function [25]. We further assume that the utility is separable. For the rest of this paper, we adopt the following utility:

$$\begin{array}{cc}& U\left(r\right)={\displaystyle \sum }_i‍U_i\left(r_i\right)={\displaystyle \sum }_i‍\log \left(r_i\right).\end{array}$$

(1)

For a joint coverage capacity area $r_i$ , the coverage capacity maximization problem can be formulated as

$$\begin{array}{ll}& \underset{}{\text{maximize}}\hspace{1em}{\displaystyle \sum }_{i\in N}‍U\left(r\right)\\ \text{subject}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}\hspace{1em}\left(c^p,u,v\right)\in X,\\ \phantom{\text{iiiiiiiiiiiiiiiiiii}}\left(c^s,t,a\right)\in Y,\\ \phantom{\text{iiiiiiiiiiiiiiiiiii}}{\displaystyle \sum }_{i\in N^S}‍c_i^p\le C_l,\hspace{1em}{c}_i^s\le c_i^p,\hspace{0.17em}\hspace{0.17em}\forall l\in N^b,\end{array}$$

(2)

where the constraint $(c^p,u,v)\in X$ models the interdependence of the coverage capacity and the coverage transmission probability from SS to MS and listening probability from MS to SSs. The constraint $(c^s,t,a)\in Y$ models the interdependence of the coverage capacity and transmission rate and cooperative strategies to mitigate interference among MSs. The constraint ${\sum }_{i\in N^S}^{}{c}_i^p\le C_l$ reflects the fact that the aggregated flow rate at each link is bounded by the total link capacity of the mobile sensors. Here, i is the index of stationary sensor sessions, and l is the index of mobile sensors.

4. Intracoverage Capacity Optimization in Noncooperation Area

4.1. Noncooperative Evolutionary Game for Intracoverage Capacity

Intracoverage capacity is related to transmission probability and listening probability. We formulate the multichannel intracoverage capacity maximization problem as

$$\begin{array}{l}\underset{l,i}{\text{maximize}}\hspace{1em}{\displaystyle \sum }_{i\in M}‍U_i\left(r_i\left(u,v\right)\right)\hfill \\ \text{subject}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}\hspace{1em}{\displaystyle \sum }_{c\in N^S}‍u_c\le \mathrm{1},\hspace{1em}\hspace{1em}{\displaystyle \sum }_{c\in N^b}‍v_d\le \mathrm{1},\hfill \\ \phantom{}\mathrm{0}\le u_c,\hspace{1em}{v}_d\le \mathrm{1},\hspace{1em}\forall c\in N^s,\hspace{1em}\forall d\in N^b.\hfill \end{array}$$

(3)

Since the channels are orthogonal, MSs select listening channels for coverage SSs. In this case, the average receiving data rate of MSs can be simplified to

$$\begin{array}{cc}& r_i\left(v\right)={\mu }_i{v}_i{\displaystyle \sum }_{m\in M}‍\left({\displaystyle \prod }_{q\in m}‍v_q\right)\left({\displaystyle \prod }_{k\in N\setminus M,k\ne q}‍\left(\mathrm{1}-v_k\right)\right),\end{array}$$

(4)

where ${\mu }_i$ is the peak data rate for MS i in channels. We drop the transmission probability due to covering SSs by listening channels. When there are multiple mobile sensors in a mobile sensor network, they may compete with each other in terms of distance to provide coverage listening power opportunities for groups of SSs. We consider the cases that a MS has variable listening power opportunities for SSs. We model this competitive listening power provision as a noncooperative game in which the Nash equilibrium is considered as the solution. Therefore, the payoff of each of the mobile sensors is maximized on an individual basis, and all of them are satisfied with the solution. In addition, to achieve the Nash equilibrium in noncooperative game, an iterative algorithm is presented in which a mobile sensor gradually adjusts the listening distance and power based on the evolutionary game strategies.

Definition 4.

The noncooperative coverage game formulation for intracoverage capacity optimization can be described as follows: $\Omega =(H,A,P)$ .

H: the players in this game are the mobile sensor and the stationary sensor.

A: the strategy of each mobile sensor is to adjust shared listening power and the distance for each stationary sensor.

P: the payoff of each mobile sensor is determined from the intracoverage utility $U_i(D)=U_i+d_i{\sum }_{m\in M_i}‍n_i^m(D)$ , where $U_i$ is the intracoverage utility gained from transmission by the mobile sensor, $d_i$ is the distance from stationary sensor to a mobile sensor, and $D=[d_{\mathrm{1}},\dots ,d_i,\dots ,d_m]$ , and $n_i^m$ denotes the number of stationary sensors attaining listening power opportunities from mobile sensor i. In this case, a mobile sensor can vary the size of listening power opportunities to be offered to stationary sensors. This corresponds to the case that the mobile sensor has a flexible coverage requirement. Therefore, the amount of listening power offered to stationary sensors can be adaptively adjusted according to not only the requirement of stationary sensors but also the competition with other mobile sensors. Specifically, in this game, the strategy of each mobile sensor is the adjustable size of listening power $p_i$ and distance $d_i$ offered to stationary sensors. Therefore, the intracoverage utility of mobile sensor i is defined as

$$\begin{array}{cc}& U_i\left(P,D\right)=b_i\left(P_i-p_i\right)+d_i{{\displaystyle \sum }}_{m\in M_i}‍n_i^m\left(p_i^m,d_i^m\right),\end{array}$$

(5)

where $P_i$ is the total power that it owns, $p=[p_{\mathrm{1}},p_2,\dots ,p_m]$ denotes a vector corresponding to the power sizes offered by the mobile sensor.

4.2. Intracoverage Capacity Dynamics

At the evolutionary equilibrium, the number of stationary sensors attaining listening power opportunities from mobile sensor i is a function that relates to listening power size and distance vectors. Given the logarithmic utility function in ((1)), intracoverage utility of a mobile sensor can be rewritten as follows:

$$\begin{array}{l}{U}_i\left(p_i,d_i,p_{-i},d_{-i}\right)\hfill \\ \hspace{1em}=b_i\log \left(P_i-p_i\right)\hfill \\ \hspace{1em}\hspace{1em}+{\rho }_i{{\displaystyle \sum }}_{m\in M_i}‍n_i^m\left(p_i^m,d_i^m\right)\log \left(D_i-d_i\right),\hfill \end{array}$$

(6)

where $b_i$ and ${\rho }_i$ are the spectral efficiency of coverage of mobile sensor i. Both $p_{-i}$ and $d_{-i}$ denote the listening power sizes and the coverage distances that all mobile sensors except mobile sensor i offer to SSs. To obtain the Nash equilibrium of intracoverage capacity, the mobile sensors iteratively adjust the listening power size and the coverage distance according to the received data rate $r_i(v)$ . The mobile sensors communicate with SSs by using short-range radio transmissions. The received radio signal strength at MS j sent by SS i decays with the distance between them. This effect is described by the so-called path-loss model [25] that states that the mean value of the signal power at a receiving node j is related to the signal power of the transmitting node i; that is,

$$\begin{array}{cc}& P_{ij}=\frac{p_i}{c_i{d}_{ij}^{\alpha }},\end{array}$$

(7)

where $d_{ij}^{\alpha }$ is the Euclidean distance between nodes i and j, $p_i$ and $P_{ij}$ are the transmitted power and the received power, respectively, and $c_i$ is a constant whose precise value depends on a number of factors including the transmission frequency. MS i can establish a communication link with SS j and transmit data correctly to SS j provided that $P_{ij}\ge \kappa {\beta }_{\text{th}}$ with ${\beta }_{\text{th}}$ being an attenuation threshold and κ the noise level at SS j. Thus mobile sensor i that can get the coverage range is defined as

$$\begin{array}{cc}& d_i^t={\left(\frac{p_i}{{\omega }_i{\beta }_{\text{th}}\kappa }\right)}^{\mathrm{1}/{\alpha }_i},\end{array}$$

(8)

where ${\omega }_i$ is regulating factor. Let $p_i(t)$ and $d_i(t)$ denote the provision listening power size and the coverage distance for SSs at iteration t. The mobile sensor adjusts the provision listening power size and the distance in a direction, which results in a higher payoff for MSs. The relationship between the strategies in the current and the future iteration can be expressed as follows:

$$\begin{array}{l}{p}_i\left(t+\mathrm{1}\right)=p_i\left(t\right)+{\theta }_{i,p}\left(\frac{\partial U_i\left(P\left(t\right),D\left(t\right)\right)}{\partial p_i}\right),\hfill \\ d_i\left(t+\mathrm{1}\right)=d_i\left(t\right)+{\theta }_{i,d}\left(\frac{\partial U_i\left(P\left(t\right),D\left(t\right)\right)}{\partial d_i}\right),\hfill \end{array}$$

(9)

where ${\theta }_{i,p}$ and ${\theta }_{i,d}$ are the speed factors of adjustment for the listening power size and coverage distance offered by MSs, respectively.

Theorem 5.

For $d_i$ , when $\rho \to \mathrm{0}$ , $d_i$ converges to $D_i$ , and $b_i\to \mathrm{0}$ , $d_i$ will never converge to $D_i$ .

Proof.

Let $I_i^m={\sum }_{m\in M_i}^{}{n}_i^m(p_i^m,d_i^m)$ ; we can get

$$\begin{array}{l}\frac{\partial U_i\left(P\left(t\right),D\left(t\right)\right)}{\partial p_i}=\mathrm{0}=\frac{b_i}{P_i-p_i}+\frac{{\rho }_i{I}_i^m}{\left(D_i-d_i\right)}\frac{\partial d_i}{\partial p_i}\hfill \\ \phantom{\frac{\partial U_i\left(P\left(t\right),D\left(t\right)\right)}{\partial p_i}}=\frac{b_i}{P_i-p_i}+\frac{{\rho }_i{I}_i^m}{D_i-d_i}\frac{{\left(p_i\right)}^{\left(\mathrm{1}-{\alpha }_i\right)/{\alpha }_i}}{{\alpha }_i{\left({\omega }_i{\beta }_{\text{th}}\kappa \right)}^{\mathrm{1}/{\alpha }_i}}.\hfill \end{array}$$

(10)

$$\begin{array}{ll}& d_i=\frac{\left(P_i-p_i\right){\rho }_i{I}_i^m{\left(p_i\right)}^{\left(\mathrm{1}-{\alpha }_i\right)/{\alpha }_i}}{b_i{\alpha }_i{\left({\omega }_i{\beta }_{\text{th}}\kappa \right)}^{\mathrm{1}/{\alpha }_i}}+D_i.\end{array}$$

(11)

From ((11)), we can get the following conclusions: when $\rho \to \mathrm{0}$ , $d_i$ converges to $D_i$ , and $b_i\to \mathrm{0}$ , $d_i$ will never converge to $D_i$ .

By substituting ((11)) into ((8)), we can express the power as

$$\begin{array}{cc}& p_i\approx P_i-\frac{b_i{\alpha }_i}{{\rho }_i{I}_i^m}-D_i.\end{array}$$

(12)

According to ((12)), when the mobile sensor moves, the stationary sensors can be covered through adjusting the sizes of the listening power and distance in order to reduce interference among stationary sensors; we can get

$$\begin{array}{l}{p}_i\left(t+\mathrm{1}\right)\hfill \\ \hspace{0.5em}=\{\begin{array}{ll}{p}_i\left(t\right)\hfill & \hfill \\ \hspace{0.5em}+\hspace{0.17em}{\theta }_{i,p}\left(P_i\left(t\right)-\frac{b_i{\alpha }_i}{{\rho }_i{I}_i^m\left(t\right)}-D_i\left(t\right)\right),\hfill & p_i\left(t\right)>\mathrm{0}\hfill \\ \mathrm{0},\hfill & \text{else},\hfill \end{array}\hfill \end{array}$$

(13)

$$\begin{array}{l}{d}_i\left(t+\mathrm{1}\right)\hfill \\ \hspace{0.5em}=\{\begin{array}{ll}{d}_i\left(t\right)\hfill & \hfill \\ \hspace{0.5em}+(\phantom{{\left(p_i\left(t\right)\right)}^{\left(\mathrm{1}-{\alpha }_i\right)/{\alpha }_i}}{\theta }_{i,d}\left(P_i\left(t\right)-p_i\left(t\right)\right){\rho }_i{I}_i^m\left(t\right)\hfill & \hfill \\ \hspace{0.5em}\hspace{0.5em}\hspace{0.5em}\hspace{0.5em}\times {\left(p_i\left(t\right)\right)}^{\left(\mathrm{1}-{\alpha }_i\right)/{\alpha }_i})\hfill & \hfill \\ \hspace{0.5em}\times \hspace{0.17em}{\left(b_i{\alpha }_i{\left({\omega }_i{\beta }_{\text{th}}\kappa \right)}^{\mathrm{1}/{\alpha }_i}\right)}^{-1}\hfill & \hfill \\ \hspace{0.5em}+\hspace{0.17em}{D}_i\left(t\right),\hfill & d_i\left(t\right)>\mathrm{0}\hfill \\ \mathrm{0},\hfill & \text{else},\hfill \end{array}\hfill \end{array}$$

(14)

where $p_i(t+\mathrm{1})$ denotes the coverage power of the ith mobile sensor at the $(t+\mathrm{1})$ th iteration and $I_i^m(t)$ is the number of the stationary sensors attaining listening power from ith mobile sensor at the tth iteration, where $d_i(t+\mathrm{1})$ denotes the coverage distance of the ith mobile sensor at the $(t+\mathrm{1})$ th iteration. Moreover, the power and distance are always positive. Whenever this expression is negative, the covered power and distance will be zero.

4.3. Evolutionary Stability for Intracoverage Capacity Optimization

Having obtained the iterative algorithm, we then prove its convergence.

Theorem 6.

The Jacobian matrix will be nonzero if parameters $b_i$ , ${\rho }_i$ , and ${\alpha }_i$ are rationally set and the ratio between correlation coefficient $b_i$ and ${\rho }_i$ cannot be too large. Thus, the matrix can be nonsingular, which indicates that the solution for iteration equation of the power and distance to maximize the intracoverage capacity is the existence.

Proof.

If $p_i(t+\mathrm{1})$ and $d_i(t+\mathrm{1})$ converge to a fixed unique point, they need to satisfy the following two conditions: $f(p_i)=p_i(t+\mathrm{1})>\mathrm{0}$ , $f(d_i)=d_i(t+\mathrm{1})>\mathrm{0}$ .

If we want $f(p_i)>\mathrm{0}$ , it needs

$$\begin{array}{cc}& \frac{b_i}{{\rho }_i}<\frac{\left(P_i-D_i\right)}{{\alpha }_i}{I}_i^m.\end{array}$$

(15)

If we want $f(d_i)>\mathrm{0}$ , it needs

$$\begin{array}{cc}& \frac{b_i}{{\rho }_i}>\frac{\left(p_i-P_i\right)I_i^m{\left(p_i\right)}^{\left(\mathrm{1}-{\alpha }_i\right)/{\alpha }_i}}{D_i{\alpha }_i{\left({\omega }_i{\beta }_{\text{th}}\kappa \right)}^{\mathrm{1}/{\alpha }_i}}.\end{array}$$

(16)

When $P_i$ and $D_i$ are constant, $b_i/{\rho }_i$ should be limited. If the ratio is too great, the algorithm will not converge. Then, we discuss the monotonicity of the algorithm. The coverage distance difference can be defined as

$$\begin{array}{l}\Delta \left(d\right)=f\left(d_i\right)-f\left(\frac{\partial d_i}{\partial p_i}\right)\hfill \\ \phantom{\Delta \left(d\right)}=\frac{\left(P_i-p_i\right){\rho }_i{I}_i^m{\left(p_i\right)}^{\left(\mathrm{1}-{\alpha }_i\right)/{\alpha }_i}}{b_i{\alpha }_i{\left({\omega }_i{\beta }_{\text{th}}\kappa \right)}^{\mathrm{1}/\alpha }}+D_i\hfill \\ \phantom{\Delta \left(d\right)}\phantom{\Delta \left(d\right)}-\frac{P_i{\rho }_i{I}_i^m\left(\left(\mathrm{1}-{\alpha }_i\right)/{\alpha }_i\right)-{\rho }_i{I}_i^m\left(\mathrm{1}/\alpha \right){\left(p_i\right)}^{\left(\mathrm{1}-{\alpha }_i\right)/{\alpha }_i}}{b_i{\alpha }_i{\left({\omega }_i{\beta }_{\text{th}}\kappa \right)}^{\mathrm{1}/{\alpha }_i}}.\hfill \end{array}$$

(17)

Considering $\Delta (d)>\mathrm{0}$ , we solve ((17)) as

$$\begin{array}{cc}& \frac{b_i}{{\rho }_i}<\frac{I_i^m\left({\alpha }_i\left(\mathrm{1}-\mathrm{2}{P}_i\right)+P_i-\mathrm{1}\right){\left(p_i\right)}^{\left(\mathrm{1}-{\alpha }_i\right)/{\alpha }_i}}{D_i{\alpha }_i^{\mathrm{2}}{\left({\omega }_i{\beta }_{\text{th}}\kappa \right)}^{\mathrm{1}/{\alpha }_i}}.\end{array}$$

(18)

From ((18)), we can also get that $b_i/{\rho }_i$ cannot be too great to guarantee the convergence. We then prove the existence of a solution for the Nash algorithm algebraic equation to guarantee the existence of a unique solution for the power iteration equation. From ((12)), we can get

$$\begin{array}{l}{\eta }_i\left(p_i,d_i,p_{-i},d_{-i},b_i,{\rho }_i\right)\hfill \\ \hspace{1em}=-p_i+P_i-\frac{b_i{\alpha }_i}{{\rho }_i{I}_i^m}-D_i\hfill \\ \hspace{1em}=-p_i+P_i\hfill \\ \hspace{1em}\hspace{1em}-\frac{b_i{\alpha }_i}{{\rho }_i{\sum }_{m\in M_i}‍n_i^m\left(p_i^m,d_i^m\right)}-D_i=\mathrm{0}.\hfill \end{array}$$

(19)

According to the Implicit Function Theorem, the Jacobian matrix of partial derivative $\partial {\eta }_i/\partial p_i$ must be nonsingular at the point of existence:

$$\begin{array}{l}\frac{\partial {\eta }_i\left(p_i,d_i,p_{-i},d_{-i},b_i,{\rho }_i\right)}{\partial p_i}\hfill \\ \hspace{0.5em}=\left|\begin{array}{llll}\frac{\partial {\eta }_{\mathrm{1}}}{\partial p_{\mathrm{1}}}\hfill & \frac{\partial {\eta }_{\mathrm{1}}}{\partial p_{\mathrm{2}}}\hfill & \cdots \hfill & \frac{\partial {\eta }_{\mathrm{1}}}{\partial p_M}\hfill \\ \frac{\partial {\eta }_{\mathrm{2}}}{\partial p_{\mathrm{1}}}\hfill & \frac{\partial {\eta }_{\mathrm{2}}}{\partial p_{\mathrm{2}}}\hfill & \cdots \hfill & \frac{\partial {\eta }_{\mathrm{2}}}{\partial p_M}\hfill \\ \cdots \hfill & \cdots \hfill & \cdots \hfill & \cdots \hfill \\ \frac{\partial {\eta }_M}{\partial p_{\mathrm{1}}}\hfill & \frac{\partial {\eta }_M}{\partial p_{\mathrm{2}}}\hfill & \cdots \hfill & \frac{\partial {\eta }_M}{\partial p_M}\hfill \end{array}\right|\hfill \\ \hspace{0.5em}=\left|\begin{array}{lll}-\mathrm{1}-\frac{b_{\mathrm{1}}{\alpha }_{\mathrm{1}}}{{\rho }_{\mathrm{1}}{n}_{\mathrm{1}}^{\mathrm{1}}\left(\mathrm{1},d_{\mathrm{1}}^{\mathrm{1}}\right)}\hfill & \cdots \hfill & -\mathrm{1}-\frac{b_{\mathrm{1}}{\alpha }_{\mathrm{1}}}{{\rho }_{\mathrm{1}}{n}_{\mathrm{1}}^M\left(\mathrm{1},d_{\mathrm{1}}^M\right)}\hfill \\ -\mathrm{1}-\frac{b_{\mathrm{2}}{\alpha }_{\mathrm{2}}}{{\rho }_{\mathrm{2}}{n}_{\mathrm{2}}^{\mathrm{1}}\left(\mathrm{1},d_{\mathrm{2}}^{\mathrm{1}}\right)}\hfill & \cdots \hfill & -\mathrm{1}-\frac{b_{\mathrm{2}}{\alpha }_{\mathrm{2}}}{{\rho }_{\mathrm{2}}{n}_{\mathrm{2}}^M\left(\mathrm{1},d_{\mathrm{2}}^M\right)}\hfill \\ \cdots \hfill & \cdots \hfill & \cdots \hfill \\ -\mathrm{1}-\frac{b_M{\alpha }_M}{{\rho }_M{n}_M^{\mathrm{1}}\left(\mathrm{1},d_M^{\mathrm{1}}\right)}\hfill & \cdots \hfill & -\mathrm{1}-\frac{b_M{\alpha }_M}{{\rho }_M{n}_M^M\left(\mathrm{1},d_M^M\right)}\hfill \end{array}\right|.\hfill \end{array}$$

(20)

The value of the Jacobian matrix is relevant to $b_i/{\rho }_i$ . Because of the limit of convergence, the ratio between correlation coefficients $b_i$ and ${\rho }_i$ cannot be too large. According to the preceding conditions, the Jacobian matrix will be nonzero if parameters $b_i$ , ${\rho }_i$ , and ${\alpha }_i$ are rationally set. Thus, the matrix can be nonsingular. Therefore, we have proven the existence of a solution for the Nash algorithm algebraic equation. The detailed procedures for noncooperative coverage capacity optimization are described in Algorithm 1.

Algorithm 1: The algorithm of noncooperative coverage capacity optimization.

Denote M as the number of coalitions

For ( $j=\mathrm{1}$ , $j\le M$ , j++)

{Each coalition $S_j$ schedules one of its member links j

all MSs together construct a player set $O_j$

Initialize $p_i^{\mathrm{0}}$ = any feasible power allocation,

    $d_i^{\mathrm{0}}$ = any feasible coverage distances, $\forall i\in O_j$

 For ( $n=\mathrm{0}$ , $\hspace{0.17em}n\le number\_of\_iterations$ , $\hspace{0.17em}n$ ++)

   {Update $U^{\mathrm{*}}\left(\left(p_i^{\mathrm{*}},d_i^{\mathrm{*}},p_{-i}^{\mathrm{*}},d_{-i}^{\mathrm{*}}\right)\right)\leftarrow \max U_i\left(p_i,d_i,p_{-i},d_{-i}\right)$

    according to ((6))

    Update $p_i(t+\mathrm{1})$ according to ((13))

    Update $d_i(t+\mathrm{1})$ according to ((14))

    Update $\partial {\mathrm{\eta }}_i\left(p_i,d_i,p_{-i},d_{-i},b_i,{\mathrm{\rho }}_i\right)/\partial p_i$ according to ((20))

    Update $b_i(t+\mathrm{1})/{\mathrm{\rho }}_i(t+\mathrm{1})$

    If $\partial {\mathrm{\eta }}_i\left(p_i,d_i,p_{-i},d_{-i},b_i,{\mathrm{\rho }}_i\right)/\partial p_i\ne \mathrm{0}$

     Break

   }

}

In the preceding sections, the stationary sensors covered by different MSs are typically scheduled noncooperatively. Consequently, neighboring MSs can schedule their transmissions in the coverage over the same subcarrier, hence causing interference to one another and limiting the coverage performance for their stationary sensors. To solve this problem and mitigate MS-to-MS interferences, the MSs have an incentive to cooperate and coordinate their transmissions using advanced transmission techniques such as interference alignment. In this respect, the MSs evaluate the signal to interference plus noise ratio (SINR) over the subcarriers assigned to their stationary sensors. Successively, based on the estimated SINR, the MSs can decide whether to take action for cooperation, that is, forming a coalition to mitigate the intercoverage interference via a spatial interference alignment scheme.

5. Intercoverage Capacity Optimization in Cooperation Area

In this section, we formulate the problem of intercoverage capacity optimization among MSs as a coalitional game in partition form and we discuss its key properties. Finally, we propose a distributed algorithm that enables MSs to cooperate and reach a partition that lies in the evolutionary game. In a coalition formation game, the cost and coalitional structure for cooperation play important roles.

Definition 7.

A coalition formation game can be defined as transmitter cooperation $(N_r^b,\Gamma )$ coalitional game with transferable utility if for any two disjoint coalitions $S_{\mathrm{1}},S_{\mathrm{2}}\subset N_r^b$ , let $N_r^b$ be the player sets Γ is a characteristic function, $\Gamma (S_{\mathrm{1}}\cup S_{\mathrm{2}})\ge \Gamma (S_{\mathrm{1}})+\Gamma (S_{\mathrm{2}})$ .

Definition 8.

A payoff vector ${\theta }^v=({\theta }_{\mathrm{1}}^v,\dots ,{\theta }_M^v)$ , is said to be group rational for dividing the value v if the player can obtain the benefit and ${\sum }_{i=\mathrm{1}}^M{\theta }_i^v=\Gamma (N)$ .

Definition 9.

An imputation ${\theta }^v$ is said to be unstable through a coalition; that is, the players have incentive to form coalition. The set of stable imputations is called the core:

$$\begin{array}{l}Co=\{{\theta }^v:{\displaystyle \sum }_{i\in N}‍{\theta }_i^v=\Gamma \left(N_r^b\right),\hfill \\ \phantom{iiiiiiiiiiii}{\displaystyle \sum }_{i\in S}‍{\theta }_i^v\ge \Gamma \left(S\right),\forall S\subseteq N_r^b\}.\hfill \end{array}$$

(21)

Definition 10.

A collection of coalitions in the grand coalition $N_r^b$ denoted by S is defined as the set $S=\{S_{\mathrm{1}},\dots ,S_l\}$ of mutually disjoint coalitions $S_i$ of $N_r^b$ . If the collection spans all the players of $N_r^b$ , it is referred to as a partition of $N_T$ . A preference operator or comparison relation ⊳ is defined for comparing two collections $R=\{R_{\mathrm{1}},\dots ,R_l\}$ and $S=\{S_{\mathrm{1}},\dots ,S_p\}$ that are partitions of the same subset $A\subseteq N_r^b$ . Thus, $R⊳S$ implies that the way R partitions A is preferred to the way S partitions A. The comparison relation is defined as $R⊳S\iff \{{\theta }_j^v(R)\ge {\theta }_j^v(S)\forall j\in R,S\}$ .

The partition form enables accounting for the relationships of mutual interference between distinct coalitions in cooperation areas. By cooperative suppressing of the interference, each MS can increase its own individual rate and also the coalition partners. The sum rate of individual payoff of a MS i in coalition S over its active links is

$$\begin{array}{cc}& {\delta }_i\left(S,\overline{P_i}\left(i\right),N_T\right)={\displaystyle \sum }_{k=\mathrm{1}}^{L_i}‍R_{ik}\left(s_i,\overline{y_k},\overline{P_i}\left(i\right),N_T\right),\end{array}$$

(22)

where $\overline{y_k}$ denotes the signal at receiver k; the power needed to transmit a pilot tone [18] between a MS $i\in S$ and the MS $j\in S^{\prime }$ is

$$\begin{array}{cc}& \overline{P_i}\left(i\right)=\frac{{\lambda }_{\mathrm{0}}·{\sigma }^{\mathrm{2}}}{{\left|H_{ij}\right|}^2},\end{array}$$

(23)

where ${\lambda }_{\mathrm{0}}$ is the minimum SNR required at the potential coalition partner j, and $|H_{ij}{|}^{\mathrm{2}}$ represents the channel gain between the above MS i and j, over the common control channel. We characterize the individual payoff of MS i in coalition S as the sum coverage capacity over its active links; that is,

$$\begin{array}{cc}& c_i^s\left(S,\overline{P_i}\left(i\right),N_T\right)=\Theta \left(\frac{{\delta }_i\left(S,\overline{P_i}\left(i\right),N_T\right)}{\sqrt{M_R\log M_R}}\right),\end{array}$$

(24)

where $M_R$ denotes the number of SSs in cooperation areas. Next, given a partition $N_T$ , for any coalition S, the value function $C^s(S,N_T)$ can be defined as the sum of the individual coverage capacity payoffs achieved by each MS in the coalition, which can be expressed as follows:

$$\begin{array}{cc}& C^s\left(S,N_T\right)=\Theta \left(\frac{{\sum }_{i=\mathrm{1}}^{\left|S\right|}‍{\sum }_{k=\mathrm{1}}^{L_i}‍R_{ik}\left(s_i,\overline{y_k},\overline{P_i}\left(i\right),N_T\right)}{{\sum }_{i=\mathrm{1}}^{\left|S\right|}‍\sqrt{M_R^i\log M_R^i}}\right).\end{array}$$

(25)

The dependence of the coverage capacity on the actual partition implies that the proposed game is clearly in partition form as Definition 7. Given these definitions, we have a coalitional game in partition form $(S,N_T)$ among the MSs and our objective is to provide a distributed solution that allows the MSs to autonomously form coalitions to increase their revenue (i.e., their total coverage capacity), given the costs for cooperation as captured by utility function ((25)).

To solve the proposed MS coalition formation game in partition form, we will use the concept of an evolutionary game as introduced in [26], which is a suitable outcome of a coalition formation process that takes into account externalities across coalitions, which, in the considered game, are represented by effects of mutual interference between coalitions of MSs. We provide an interference alignment evolutionary game for MSs to form partition by selecting different strategies. We then, using the replicator dynamics, explore evolutionary stable strategies of the game to demonstrate the stability of partition form.

Definition 11.

An interference alignment evolutionary game (IAEG) is defined as 4-tuple $Z=(S,Q,A,U)$ , where S is a coalition partition composed of many MSs. Q is the set of individuals in the coalition partition S. A is the set of strategies, and $A=\{a_{\mathrm{1}},a_{\mathrm{2}}\}=\{IA,de\}$ . U is the payoff matrix and the value of each individual's payoff of MS in coalition S.

In the IAEG, each MS may select the strategy IA or defect (de). Selecting the strategy IA by a MS means that it will cooperate with its counterpart; selecting the strategy $de$ means noncooperation. Two MSs select the strategy IA to cooperate and help mitigate the intercoverage interference; thus its gain $c_i^s(S,\overline{P_i}(i),N_T)$ is improved. It also obtains the gain $c_i^s(S,\overline{P_i}(i),N_T)$ because its partners also select IA that will result in helping to mitigate the intercoverage interference. At the same time, one loses the utility for paying for the cost $\overline{P_i}(i)$ produced by the power consumption due to transmitting a pilot tone between a MS $i\in S$ and the $j\in S^{\prime }$ . The total payoff for each MS therefore is $c_i^s(S,\overline{P_i}(i),N_T)+U_i(p_i,d_i,p_{-i},d_{-i})-\overline{P_i}(i)$ . One sensor node selects the strategy IA whereas the other selects the strategy de. For one selecting the strategy IA, because its counterpart selecting the strategy de results in noncooperation, it loses the coverage capacity because it cannot mitigate the intercoverage interference. Its total payoff therefore is $U_i(p_i,d_i,p_{-i},d_{-i})\hspace{0.17em}-\hspace{0.17em}{C}_L$ . There are totally two strategies in the IAEG, so, let $\varpi (t)=\{\varpi ,\mathrm{1}-\varpi \}$ be the mixed strategy at time t in the coalition partition S, where ϖ denotes the rate of MSs selecting strategy $a_{\mathrm{1}}(IA)$ and $\mathrm{1}-\varpi$ denotes the rate of MSs selecting strategy $a_{\mathrm{2}}(de)$ . According to evolutionary game theory [26], MSs obtain the expected coverage capacity by selecting the strategy $IA$ , which is expressed by

$$\begin{array}{l}C\left(a_{\mathrm{1}},\varpi \left(t\right)\right)\hfill \\ \hspace{1em}=\varpi \left(c_i^s\left(S,\overline{P_i}\left(i\right),N_T\right)+U_i\left(p_i,d_i,p_{-i},d_{-i}\right)-\overline{P_i}\left(i\right)\right)\hfill \\ \hspace{1em}\hspace{1em}+\left(\mathrm{1}-\varpi \right)\left(U_i\left(p_i,d_i,p_{-i},d_{-i}\right)-C_L\right).\hfill \end{array}$$

(26)

MSs obtain the expected coverage capacity by selecting the strategy $de$ , which is expressed by

$$\begin{array}{l}C\left(a_{\mathrm{2}},\varpi \left(t\right)\right)\hfill \\ \hspace{1em}=\varpi \left(c_i^s\left(S,\overline{P_i}\left(i\right),N_T\right)+U_i\left(p_i,d_i,p_{-i},d_{-i}\right)-\overline{P_i}\left(i\right)\right)\hfill \\ \hspace{1em}\hspace{1em}+\left(\mathrm{1}-\varpi \right)\left(U_i\left(p_i,d_i,p_{-i},d_{-i}\right)\right).\hfill \end{array}$$

(27)

The average coverage capacity payoff of the whole coalition partition S is

$$\begin{array}{cc}& \bar{C}\left(a,\varpi \left(t\right)\right)=\varpi C(a_{\mathrm{1}},\varpi \left(t\right))+\left(\mathrm{1}-\varpi \right)C\left(a_{\mathrm{2}},\varpi \left(t\right)\right).\end{array}$$

(28)

The replicator dynamics equation of IAEG therefore is

$$\begin{array}{l}{\rm Y}\left(\varpi \right)=\varpi \left(C\left(a_{\mathrm{1}},\varpi \left(t\right)\right)-\bar{C}\left(a,\varpi \left(t\right)\right)\right)\hfill \\ \phantom{{\rm Y}\left(\varpi \right)}=\varpi (\varpi \left(\mathrm{2}{C}_L-U_i\left(p_i,d_i,p_{-i},d_{-i}\right)\right)\hfill \\ \phantom{\text{iiiiiiiiiiiiiiiiii}}-{\varpi }^{\mathrm{2}}\left(C_L+U_i\left(p_i,d_i,p_{-i},d_{-i}\right)\right)\hfill \\ \phantom{\text{iiiiiiiiiiiiiiiiii}}+U_i\left(p_i,d_i,p_{-i},d_{-i}\right)-C_L).\hfill \end{array}$$

(29)

Let ${\rm Y}(\varpi )=\mathrm{0}$ ; then ((29)) has two stable states at most; they are

$$\begin{array}{l}{\varpi }_{\mathrm{1}}^{*}=\mathrm{0}.\hfill \\ {\varpi }_{\mathrm{2}}^{*}=(\phantom{\sqrt{\mathrm{5}{U}_i^{\mathrm{2}}-}}\left(\mathrm{2}{C}_L-U_i\left(p_i,d_i,p_{-i},d_{-i}\right)\right)\mathrm{\hspace{0.17em}\hspace{0.17em}}\hfill \\ \phantom{\text{iiiiiiiiiii}}+\sqrt{\mathrm{5}{U}_i^{\mathrm{2}}\left(p_i,d_i,p_{-i},d_{-i}\right)-\mathrm{4}{U}_i\left(p_i,d_i,p_{-i},d_{-i}\right)C_L})\hfill \\ \phantom{\text{iiiiiiiii}}\times {\left(\mathrm{2}\left(C_L+U_i\left(p_i,d_i,p_{-i},d_{-i}\right)\right)\right)}^{-1}.\hfill \end{array}$$

(30)

According to characteristics of evolutionary stable strategy, a stable state must converge to a small disturbance, which is actually accordant to the requirements of the stable theorem of differential equation. That is, ${{\rm Y}}^{\prime }({\varpi }^{*})<\mathrm{0}$ must be satisfied when ${\varpi }^{*}$ is a stable state.

Theorem 12.

When $U_i(p_i,d_i,p_{-i},d_{-i})<C_L$ , both ${\varpi }_{\mathrm{1}}^{*}$ and ${\varpi }_{\mathrm{2}}^{*}$ are evolutionary stable strategies for MSs in IAEG, which satisfy $q({\varpi }_{\mathrm{1}}^{*})<q({\varpi }_{\mathrm{2}}^{*})$ , where $q({\varpi }_{\mathrm{1}}^{*})$ and $q({\varpi }_{\mathrm{2}}^{*})$ denote the probability of MSs selecting the strategy de and that of ones selecting the strategy IA, respectively.

Proof.

Calculating the derivative of ((29)), we get

$$\begin{array}{l}{{\rm Y}}^{\prime }\left({\varpi }^{*}\right)=\mathrm{2}\varpi \left(C_L-U_i\left(p_i,d_i,p_{-i},d_{-i}\right)\right)\hfill \\ +U_i\left(p_i,d_i,p_{-i},d_{-i}\right)-C_L\hfill \\ -\mathrm{2}{\varpi }^{\mathrm{2}}{U}_i\left(p_i,d_i,p_{-i},d_{-i}\right).\hfill \end{array}$$

(31)

$$\begin{array}{l}{{\rm Y}}^{\prime }\left(\mathrm{0}\right)=U_i\left(p_i,d_i,p_{-i},d_{-i}\right)-C_L<\mathrm{0}\hfill \\ \phantom{\text{iiiiiiii}}⟹U_i\left(p_i,d_i,p_{-i},d_{-i}\right)<C_L.\hfill \end{array}$$

(32)

$$\begin{array}{l}\mathrm{0}<{\varpi }_{\mathrm{2}}^{*}<(\mathrm{2}{C}_L-U_i\left(p_i,d_i,p_{-i},d_{-i}\right)\hfill \\ \phantom{\text{iiiiiiiiiiiiiiiiii}}+\mathrm{2}{U}_i\left(p_i,d_i,p_{-i},d_{-i}\right))\hfill \\ {\phantom{\text{iiiiiiiiiiiiiiii}}\times \left(\mathrm{2}{C}_L+\mathrm{2}{U}_i\left(p_i,d_i,p_{-i},d_{-i}\right)\right)}^{-1}<\mathrm{1}.\hfill \end{array}$$

(33)

According to ((31)), ((32)), and ((33)), both ${\varpi }_{\mathrm{1}}^{*}$ and ${\varpi }_{\mathrm{2}}^{*}$ are evolutionary stable strategies. What is more, according to ((33)), the probability of MSs selecting the strategy de is less than that of ones selecting the strategy IA; that is, $q({\varpi }_{\mathrm{1}}^{*})<q({\varpi }_{\mathrm{2}}^{*})$ . The detailed procedures for cooperative interference alignment are described in Algorithm 2.

Algorithm 2: The algorithm of distributed coalition formation algorithm for interference alignment in mobile sensor networks.

Initial state at the MS: the network is partitioned by $N_T=\{\mathrm{1},\dots ,N\}$ with

noncooperative coverage capacity optimization without interference alignment.

(1) Intercoverage interference discovery

 (a) Through RSSI measurements, each MS detects nearby stationary sensors

  activating on the same subchannel.

 (b) For each of the occupied subchannels, each MS sorts the interference

  degree from the stronger to the weaker.

(2) IA coalition Formation

for all the used subchannels do

 {each MS i computes the cost of cooperation with the MS j according to ((23))

 if $\mathrm{\Gamma }\left(S_{\mathrm{1}}\cup \left\{j\right\},N_T\right)\ge \mathrm{\Gamma }\left(S_{\mathrm{1}},N_T\right)$

   $\{S=S_{\mathrm{1}}\cup \left\{j\right\}$

   Update the optimal strategy $\mathrm{\Upsilon }({\mathrm{\varpi }}^{\mathrm{*}})$ with $\max C^s\left(S,N_T\right)$ according to ((29))

   MS selecting the strategy IA to form partitions according ${\mathrm{\varpi }}^{\mathrm{*}}$

  }

 if $U_i\left(p_i,d_i,p_{-i},d_{-i}\right)<C_L$

  {Evolve to stable state

   Break

  }

 }

According to Theorem 12, intercoverage capacity management must satisfy conditions of Theorem 12 that will promote sensor nodes to select the strategy $IA$ ; therefore, the stability of the network partition dictated by the evolutionary game is guaranteed by providing the highest achievable payoff of at the MSs in order to improve the intercoverage capacity optimization with interference alignment.

6. Simulation

The proposed model is simulated using MATLAB and NS2, and experiments have been performed in a 2.20 GHZ i3-2330 machine having 2 GB of memory. We conduct extensive simulations over sensor networks to evaluate their performances. In addition, we also implement flood protocol. We use a 50-node sensor network, in which sensors are evenly deployed in a $1200\times 1200$ region. The moving speed of each mobile sensor is 40 m/s. In simulations, when a coalition of the cooperation income rises with other members, a coalition takes action to evolution for cancellation interference among MSs. It includes four evolutionary states (Figure 3). Therefore, we defined the evolution rules as the merger and partition. Each rule is divided into three stages to accomplish evolution procedures, the coalition member of neighbor discovery, coalition formation, and transmission of information ω denotes evolutionary control parameters and ${\omega }_{\mathrm{1}}=b_{\mathrm{1}}/{\rho }_{\mathrm{1}}$ , ${\omega }_{\mathrm{2}}=b_{\mathrm{2}}/{\rho }_{\mathrm{2}}$ , ${\omega }_{\mathrm{3}}=b_{\mathrm{3}}/{\rho }_{\mathrm{3}}$ , and ${\omega }_{\mathrm{4}}=b_{\mathrm{4}}/{\rho }_{\mathrm{4}}$ denote the weight of four kinds of evolution. Dynamics equation is expressed as follows:

$$\begin{array}{cc}& \frac{d{r}_k\left(t\right)}{dt}={\omega }_{\mathrm{1}}{r}_{k+\mathrm{1}}-{\omega }_{\mathrm{3}}{r}_k\left(t\right),\hspace{1em}k=\mathrm{1}.\end{array}$$

(34)

Figure 3

Four evolutionary states in mobile sensor netwoks.

Case 1.

Coalition scale changes from 2 to 1 after 1-time partition in the speed υ in mobile sensor networks.

Case 2.

Coalition scale evolutes from 1 to 2 after 1 time of merger. In addition to the above, there are also two cases:

$$\begin{array}{l}\frac{d{r}_k\left(t\right)}{dt}={\omega }_{\mathrm{1}}{r}_{k+\mathrm{1}}\left(t\right)+{\omega }_{\mathrm{4}}{r}_{k-\mathrm{1}}\left(t\right)\hfill \\ \phantom{\text{iiiiiiiiiiiiii}}-{\omega }_{\mathrm{2}}{r}_k\left(t\right)-{\omega }_{\mathrm{3}}{r}_k\left(t\right),\hspace{1em}\mathrm{1}<k<m.\hfill \\ \frac{d{r}_k\left(t\right)}{dt}={\omega }_{\mathrm{4}}{r}_{k-\mathrm{1}}\left(t\right)-{\omega }_{\mathrm{2}}{r}_k\left(t\right),\hspace{1em}k=m.\hfill \end{array}$$

(35)

Case 3.

$m-1$ coalition evolutes m coalition after 1 merger.

Case 4.

The m coalition evolutes $m-1$ coalition through partition.

We first consider the network which comprises both stationary and mobile sensors. In the simulation, mobile nodes are uniformly scattered into the network with area of L. In Cases 1 and 2, the initial value of coverage capacity is 0.2. Figure 4 shows effect of ${\omega }_{\mathrm{1}}$ , ${\omega }_{\mathrm{3}}$ on the average coverage capacity in mobile sensor networks. When $t=0.3$ , ${\omega }_1=0.5$ , and ${\omega }_3=0.11$ , the average coverage capacity per coalition is increased up to 0.23 by using the proposed algorithm.

Figure 4

Effect of ${\omega }_1$ , ${\omega }_3$ on the average coverage capacity in Cases 1 and 2.

In Case 3, the initial value of coverage capacity is 0.2. Figure 5 shows effect of ${\omega }_{\mathrm{1}}$ , ${\omega }_{\mathrm{2}}$ , ${\omega }_{\mathrm{3}}$ , and ${\omega }_{\mathrm{4}}$ on the average coverage capacity in mobile sensor networks. When $t=\mathrm{0}$ , ${\omega }_1=0.35$ , ${\omega }_2=0.1$ , ${\omega }_3=0.12$ , and ${\omega }_4=0.42$ , the average coverage capacity per coalition increases. When $t=\mathrm{0.5}$ , the average coverage capacity per coalition is up to 0.23. However, when   ${\omega }_1=0.35$ ,   ${\omega }_2=0.3$ , ${\omega }_3=0.4$ , and ${\omega }_4=0.42$ , the average coverage capacity per coalition decreases. This is because four states simultaneously change and ${\omega }_{\mathrm{2}}$ , ${\omega }_{\mathrm{3}}$ have minor value. This suggests that states ② and ③ have smaller values of merger and partition, which makes the overall coverage capacity keep a high stable value.

Figure 5

Effect of ${\omega }_{\mathrm{1}}$ , ${\omega }_2$ , ${\omega }_3$ , and ${\omega }_4$ on the average coverage capacity in Case 3.

However, when ${\omega }_{\mathrm{2}}$ and ${\omega }_{\mathrm{3}}$ increase, such as ${\omega }_2=0.23$ , ${\omega }_3=0.22$ , which suggests that states ② and ③ have a lot of the frequency of the merger and partition in coalitions and make the overall coverage capacity keep low value. Figure 6 depicts the average individual MS coverage capacity payoff. Because the eliminating interference is critical for improving the intercoverage capacity among MSs. The cooperative game strategies lead to similar payoffs due to the low density of the interferences for a given subchannel. Conversely, for the considered larger network, the payoff of the average coverage capacity from coalition formation becomes relatively low due to high inter-MSs interference. When we increase the number of sensor to 80, the average coverage capacity from coalition formation is up to maximum 0.5. While the average coverage capacity for noncooperative coalition is up to maximum 0.27 reducing of 0.23 with respect to the cooperative case. From Figure 7, we can see that the power value of our algorithm can meet the threshold requirement, when the threshold is relatively small, which may mean that the MS is close to the stationary sensor. When ${\omega }_1=1.4,{\omega }_2=1.3$ , and ${\omega }_3=1.2$ , the convergence is relatively fast. There are several stationary sensors whose power exceeds threshold, which means that the power does not reach the lowest requirement; the MS has two choices: one is adjusting its coverage distance for the stationary sensors, and the other is properly changing its position to be close to the stationary sensors.

Figure 6

The average individual MS coverage capacity payoff for the cooperative intercoverage optimization.

Figure 7

Effects of the power and distance on coverage capacity.

Figure 8 depicts the average individual MS coverage capacity. The $\text{MS}\mathrm{1}\to \text{SS}\mathrm{2}$ denotes the coverage capacity from mobile sensor 1 to stationary sensor 2 that has more coverage capacity than $\text{MS}\mathrm{4}\to \text{SS}\mathrm{5}$ at time 30 s, since $\text{MS}\mathrm{1}$ coalition reached steady state via cooperative game. The $\text{MS}\mathrm{7}\to \text{SS}\mathrm{8}$ reached the first steady state at time 49 s and the second steady state at time 79 s and gained average maximum coverage capacity about 4.1 bps/s for two steady states.

Figure 8

The coverage capacity in cooperative areas.

7. Conclusions

In this paper, we have presented an optimization framework to improve intracoverage capacity and intercoverage capacity in a mobile sensor network. We formulated a coverage capacity maximization problem that jointly considered the power and distance control between MSs and SSs and an interference control among MSs. For the studied power and distance control problem between MSs and SSs based on noncooperative evolutionary game, our proposed algorithm reached a stable Nash equilibrium. For the studied interference control problem among MSs based on cooperative evolutionary game, the Nash equilibrium exists and the proposed algorithm reaches the stability. The numerical simulation results have shown that the proposed noncooperative strategy in noncooperation area can attain maximization intracoverage capacity gains, and the proposed cooperative strategy among MSs can improve intercoverage capacity gains.