A Theoretic Approach for Prolonging Lifetime of Wireless Sensor Networks Based on the Coalition Game Model

Abstract

Energy consumption is one of the most important performance measures in wireless sensor networks (WSNs). In order to reduce energy consumption, some nodes in the network will work together as a coalition but will not work independently. In this paper, towards forming coalitions, an energy-efficient coalition game model is proposed based on the Markov process and from the theoretic point of view. First, we propose the performance measure of the Markov process states based on the concept of absorbing coefficient and bargaining set. Consequently, we give a simulation algorithm to calculate the absorbing coefficient and simulate the forming process of the coalitions. Moreover, to determine the strategies of coalitions to ensure the WSNs’ reachability, we give the genetic-algorithm based method for calculating the approximate Nash equilibrium. Experimental results show that our model can guarantee longer lifetime and effective reachability for WSNs.

1. Introduction

In recent years, wireless sensor networks (WSNs) have been paid much attention and widely used in many real world applications, such as disaster relief, environmental monitoring, and target tracking [1, 2]. Low energy consumption is a critical design requirement for most WSN applications, since the nodes in WSNs are small-sized and battery-powered [3]. Moreover, the applications of WSNs in different fields require different measures for the quality of services (QoS), such as delay, reachability, error-tolerance, among which reachability is a preliminary requirement of the network. Therefore, in this paper, we consider energy and reachability as the two representative measures of the WSN QoS.

It is worth noting that data transmission in WSNs makes a great impact on energy consumption [2]. In order to prolong the lifetime, each node may choose to send its own message groups as much as possible while not forwarding the message groups from the other nodes, although many message groups need to be forwarded to reach their destinations in a network. Thus, in the energy level of WSN nodes, it is necessary to make decisions for the number of message groups that will be sent and the number of message groups that will be forwarded, respectively, by the nodes, since the decision of one node will be affected by that of the other nodes. Meanwhile, to reduce the power consumption of WSN nodes is still the state-of-the-art topic with much attention, due to the more and more pervasive WSN applications and limited power supply by the small battery.

It is well known that game theory is the formal study of conflict and cooperation [4], and it is the study of decision-making where several players must make choices that potentially affect the interests of the others [5]. We note that data transmission among the nodes in a WSN concerns both conflicts and cooperation when sending or forwarding message groups, where some nodes in the WSN work together but do not work independently to reduce the energy consumption. Therefore, the data transmission in a WSN forms a game process intuitively according to the inherence of game theory. Based on the game theory, we are to save energy consumption of WSNs through changing data transmission strategies. For this purpose, it is desirable to develop the method for forming the energy-efficient game model and obtain the coalition strategies to ensure the WSN's reachability. These are exactly the problems that we will solve in this paper.

In the game theory, uncooperative games and cooperative games (coalition games) are two types in the game theory. Players in uncooperative games work independently, and they try to increase their own payoff as much as possible in a selfish manner. Contrarily, the players in coalition games work together as a whole to increase the payoff of the whole coalition. Accordingly, Nash equilibrium (NE) is the solution to uncooperative games in which each player takes the best strategy to reply with those of the others. NE means a relatively balanced state in which players will not change their strategies any more [4]. In cooperative games, Shapley value is a fair and unique payoff sharing method to determine how much a player gets based on the contribution of a player to the coalition.

Currently, game theory has been adopted as a certain underlying theoretic basis for WSN research. For example, Huang et al. [6] proposed the method for refining the location in WSNs based on the game theory, and the position of nodes can be adjusted by achieving the global Nash equilibrium. Specifically, there are also many energy-efficient algorithms based on the uncooperative games to prolong the lifetime of the WSNs [6–9], most of which reduce the energy consumption by finding the NE of a WSN. As a solution to the uncooperative games, NE is a balanced but not an optimum state. The strategies chosen in an NE are local optimal (just the optimum of one node), which will affect the extent of lifetime of the whole WSN.

Unlike the uncooperative way, players in cooperative games work together and try their best to improve the whole coalition's benefit [4]. In recent years, coalition game theory has been adopted for modeling WSNs or resource allocation [5]. Different approaches were given for MAC address assignment [10], sleep time allocation [11], transmission scheme [12], and routing protocol [13, 14]. But in these methods, the modeling and formation of cooperative collation for prolonging the lifetime of WSNs have not been concerned. Previously, we [15] gave the data transfer model of WSNs by incorporating Shapley value and Nash equilibrium, but the formation of coalitions has not been concerned as well. We [16] also proposed the energy-efficient coalition game model for WSNs, but the data transmission strategies have not been concerned. Zhang et al. [17] proposed a cooperative game theoretic approach for the optimal power control in wireless cooperative relay networks by defining the amount of energy willing to contribute for relaying purpose as the node strategy instead of focusing on data transmission in WSNs.

Therefore, it is expected theoretically that the optimal data transmission strategies of the coalitions could be ensured and the lifetime of WSNs could be prolonged by adopting the coalition game model. In this paper, we are to discuss an energy-efficient model and the corresponding data transmission strategies for WSNs based on the coalition game theory, assuming that there is no noise in the wireless environments.

To develop a WSN energy-efficient coalition game model from the theoretic point of view, it is desirable to solve the following problems:

• (i)

  how to measure the payoff of the coalitions?

• (ii)

  how to share the payoff of the coalitions?

• (iii)

  how to form the coalition based on the payoff and the sharing method?

• (iv)

  how to determine the data transmission strategies of the coalitions?

For the first problem, we start from the concept of coalition payoff as the quantitative description of the coalition performance when data are transmitted among the WSN nodes in a feasible cooperative manner. By analyzing the main influence factors of the coalition payoff, we gave the concepts of the energy level, distance cost, and proportion of the generated message groups. Then, we developed the formula for payoff calculation consequently.

For the second problem, the individual reward in a coalition depends on how the rewards are shared in the group [18]. As is known, Shapley value [19] is a commonly used reward sharing strategy in coalition games, in which each individual player gets the reward according to its contribution to the coalition. As the main advantage of Shapley value, the unique and fair solution can be provided for sharing the reward of the coalition. Thus, we adopted Shapley value as the measure of the reward sharing in a coalition.

For the third problem, we used a Markov process [20] to simulate the process of forming coalitions. Based on the idea of Bargaining set [21], we gave the concept of absorbing coefficient to measure the performance of the states in the Markov process. The larger the absorbing coefficient is, the more possibly the state will be chosen as the final state, from which all the WSN coalitions can be obtained.

For the fourth problem, we considered a WSN that may contain several coalitions, each of which is taken as a whole, since the nodes in a coalition work together. To determine the data strategies of coalitions to guarantee the reachability of the WSN, we solved the Nash equilibrium based on genetic algorithm [4].

To verify the feasibility of the model proposed in this paper, we implemented our method and made a simulation. Experimental results show that our model can guarantee a longer lifetime and effective reachability for WSNs.

The remainder of this paper is organized as follows: Section 2 introduces related work. Section 3 gives the coalition payoff function. Section 4 gives the energy-efficient coalition game model of WSNs. Section 5 gives the NE model to determine the data transmission strategies of coalitions. Section 6 shows experimental results and performance analysis. Section 7 concludes and discusses future work.

2. Related Work

Many energy-efficient algorithms of WSNs have been proposed in recent years. The method for improving energy efficiency in WSNs through scheduling and routing was given for environment monitoring applications [6]. Considering the remaining energy and the distribution of head nodes, distributed energy-economical routing (DEER) was designed [8]. By this method, extra message is transmitted in the WSN to find the head nodes that will increase the nodes’ energy consumption. The reachability cannot be guaranteed if any head node dries up its energy, since data transmission is determined by the head nodes in this model. Instead, in this paper, we will discuss the energy-efficient model by guaranteeing the reachability of message groups.

In the game-theory-based topology control algorithm [9], the power of transmitting a message group was calculated. This method just gave the energy consumption of transmitting a message group in a NE, but the data transmission strategy of each node was not concerned. An optimal data transmission path for WSNs was given based on the Nash equilibrium [22, 23], but the NE-based path was not always optimal, since NE is frequently adopted to find a balanced state in uncooperative games. In addition, the path may not exist since finding an exact NE is generally in NP class. Therefore, we will establish the method in a cooperative manner in this paper.

Cooperative game theory has been widely used in communication networks [5] and specifically applied in WSN modeling and energy-efficient strategies [11–16]. Gharehehiran and Krishnamurthy [11] gave the dynamic coalition formation for efficient sleep time allocation in WSNs using the cooperative game theory. Wu et al. [12] gave the method for WSN transmission scheme based on coalition game model for energy-efficient objectives. Voulkidis et al. [13] gave a location-based routing protocol for energy efficiency in WSNs. These methods adopted coalition game theory as the basis for energy-efficient strategies but the corresponding coalition formation has not been concerned, which is exactly the basis of energy-efficient strategies upon the cooperative game theory and will be discussed in this paper. We proposed the routing coalition game method for data fusion in WSNs [14] and gave the data transfer model for WSNs by incorporating Shapley value and Nash equilibrium [15]. We proposed the energy-efficient coalition game model for WSNs [16], but the corresponding data transmission strategies have not been concerned. Zhang et al. [17] proposed a cooperative game theoretic approach for the optimal power control in wireless cooperative relay networks by defining the amount of energy willing to contribute for relaying purpose as the node strategy instead of focusing on data transmission in WSNs, which will be considered in this paper.

The models given in [7–9, 11–15, 23] could be used to reduce the energy consumption and prolong the lifetime of WSNs from various perspectives. The strategies chosen are local optimum since nodes in these models work independently. There is no information exchange among nodes for finding the global optimal strategies to reduce the energy consumption of the whole WSN as much as possible.

Generally, coalition games have been widely used in communication networks [19]. WSN coalitions will be formed at first and the nodes (members) in a coalition will work as a whole. Members in a coalition exchange their information to reduce the energy consumption of the whole coalition. In this paper we discuss the theoretic energy-efficient model to prolong the lifetime of WSNs and guarantee the reachability of message groups. We consider all nodes in a WSN as a whole to avoid the sensitivity of head nodes on reachability. All nodes in a coalition are cooperative to form a coalition game, under which we discuss the optimal strategies of data transmission of each node, so the casual or local optimum of the NE-based transmission strategies can be improved to a global optimum that can always be achieved. We discuss the formation of the coalition based on Bargaining set [21] and Markov process [20], and give a universal algorithm to ensure high efficiency and less lossless data transmission.

3. Payoff Function of WSN Coalitions

Based on the energy level, distance cost, and proportion of the generating message groups (PGMs), we will propose a coalition payoff function and give a simulation algorithm in this section.

3.1. Concept of Payoff Function of WSN Coalitions

The payoff function will be used as the measure of the performance of coalitions when data are transmitted among the WSN nodes in a feasible cooperative manner, and it is formed based on the absolute payoff and the relative payoff. Absolute payoff is the measure of the satisfactory degree of coalition members to their coalition and relative payoff is the measure of support degree from the other nodes that are not in the coalition.

We suppose that time is discrete and can be split into a series of equal time slots, denoted as $1,2,\dots$ . Some relevant concepts are introduced at first.

• (i)

  The energy level ( $L_{ik}$ ) is the measure of the transmission capability of coalition i in time slot k. $L_{ik}=1$ means that the energy of coalition is relatively sufficient in time slot k, when many message groups may be forwarded. On the contrary, if $L_{ik}$ is close to 0, then the coalition may choose to send its own message groups as much as possible.

• (ii)

  The definition of the distance cost (DC) is based on the distance and the fewest hops from the node to the sink. The longer the distance, the larger the distance cost, and the more hops to the sink, the larger the distance cost. DC in each time slot is a constant since the WSN has been deployed already.

• (iii)

  The PGM of coalition i at time slot k ( $P_{ik}$ ) is defined as the proportion of the message groups generated by the coalition to that generated by the whole network. The larger the PGM is, the superior the coalition will be, since the ultimate goal of WSN coalitions is to send its own message groups.

Based on the above concepts, we can calculate the absolute payoff of coalition i at time slot k (denoted by $\text{A}{\text{P}}_{ik}$ ), as the measure of the members’ satisfactory degree. The larger the absolute payoff is, the more satisfied the members feel with the coalition; that is, the members will be more willing to stay in current coalition and will not choose the other coalitions. Based on the concepts of the energy level, the distance cost, and the proportion of the generating message groups, we give the formula of the absolute payoff as follows:

$$\begin{array}{cc}& \text{A}{\text{P}}_{ik}=\frac{L_{ik}}{\text{DC}·P_{ik}}·\frac{g_{ik}}{r_{ik}+g_{ik}},\end{array}$$

(1)

where $r_{ik}$ is the number of the message groups that need to be forwarded by coalition i at time slot k, $g_{ik}$ is the number of the message groups generated by coalition i at time slot k, and $L_{ik}/(\text{DC}·P_{ik})$ means the average transmission capability of each hop with respect to the message group generated by coalition i.

The measure of the contribution of coalition i to the whole network at time slot t is given by the concept of the relative payoff. The larger the relative payoff is, the more the other nodes support the coalition. We give the formula of the relative payoff as follows:

$$\begin{array}{cc}& \text{R}{\text{P}}_{ik}=\frac{\text{A}{\text{P}}_{ik}}{{\sum }_{l=\mathrm{1}}^T\left(\text{A}{\text{P}}_{lk}\right)},\end{array}$$

(2)

where T is the number of coalitions in the present state.

Based on formula (1) and formula (2), we give the coalition payoff function $V(i)$ as follows:

$$\begin{array}{cc}& V\left(i\right)=\alpha \mu \left(\text{A}{\text{P}}_{ik}\right)+\beta \lambda \left(\text{R}{\text{P}}_{ik}\right),\end{array}$$

(3)

where both function $\mu ()$ and function $\lambda ()$ are convex functions, which are both derivable and strictly increasing. α and β are the importance measures of the absolute payoff and the relative payoff, respectively, with respect to the general payoff of coalition i, where $\alpha >0$ and $\beta >0$ .

3.2. Calculating Payoffs of WSN Coalitions

Based on the model given in Section 3.1, we will give a simulation algorithm for calculating the payoff function. It is known that the WSN has been deployed and the nodes in the network are intercommunicated. Each message group may be necessary to be forwarded to the sink, and the nodes in a WSN are connected to ensure the reachability of each message group to the sink. To complete the data transmission activity, each node has the obligation to accept the message groups from the other nodes, so we assume that a node in the network receiving messages from the other nodes is energy free.

For convenience, we make the following explanations for all the symbols used in Algorithm 1:

•  

  N: the number of nodes in the coalition,

•  

  M: the number of nodes in the network,

•  

  T: the number of coalitions in the present state,

•  

  D: the longest distance between a pair of nodes,

•  

  H: the largest number of the hops from the nodes to the sink,

•  

  $e_{ik}$ : the energy of node i in the present time slot,

•  

  $d_i$ : the distance from node i to the sink,

•  

  $h_i$ : the fewest hops from node i to the sink,

•  

  $g_i$ : the number of message groups generated by node i,

•  

  $r_i$ : the number of message groups that need to be forwarded by node i.

Algorithm 1: Calculating the payoff of WSN coalitions.

Input:

  (1) $p=\{e_{ik},d_i,h_i,g_i,r_i\}$ is the set of parameters of nodes that participate in this coalition;

  (2) α and β are the importance measures of the absolute payoff and relative payoff respectively

Output: The coalition payoff in present time slot

Steps:

Step  1. Calculate the energy level L of the coalition

   $e\leftarrow \mathit{0}$ // e is the present energy of the coalition

   $E\leftarrow \mathit{0}$ // E is the primary energy of the coalition when the network deployed

  For $i\leftarrow \mathit{0}$ to $N-\mathit{1}$ Do

     $e\leftarrow e+e_{ik}$

  End for

  For $i\leftarrow \mathit{0}$ to $N-\mathit{1}$ Do

     $E\leftarrow E+e_{i\mathit{1}}$

  End for

   $L\leftarrow e/E$

Step  2. Calculate the distance cost DC of the coalition

   $D_i\leftarrow \mathit{0}$ // $D_i$ is the whole distance from the coalition to the sink

   $H_i\leftarrow \mathit{0}$ // $H_i$ is the sum of the hops from the coalition to the sink

  For $i\leftarrow \mathit{0}$ to $N-\mathit{1}$ Do

     $D_i\leftarrow D_i+d_i$

  End for

  For $i\leftarrow \mathit{0}$ to $N-\mathit{1}$ Do

     $H_i\leftarrow H_i+h_i$

  End for

   $\text{DC}\leftarrow (D_i+H_i)/(N·(D+N))$

Step  3. Calculate the PGM (P) of the coalition

   $G_i\leftarrow \mathit{0}$ // $G_i$ is the message groups generated by the coalition

   $G\leftarrow \mathit{0}$ // G is the message groups generated by the network

  For $i\leftarrow \mathit{0}$ to $N-\mathit{1}$ Do

     $G_i\leftarrow G_i+g_i$

  End for

  For $i\leftarrow \mathit{0}$ to $M-\mathit{1}$ Do

     $G\leftarrow G+g_i$

  End for

   $P\leftarrow G_i/G$

Step  4. Calculate the absolute payoff P

   $R_i\leftarrow \mathit{0}$ // Message groups need to be forwarded by the coalition

  For $i\leftarrow \mathit{0}$ to $N-\mathit{1}$ Do

     $R_i\leftarrow R_i+r_i$

  End for

   ${\text{AP}}_i\leftarrow [L/(\text{DC}·P)]·[G_i/(R_i+G_i)]$

Step  5. Calculate the relative payoff RP

   (i) Calculate the sum of the absolute payoffs

     $\text{SA}\leftarrow \mathit{0}$

    For $y\leftarrow \mathit{0}$ to $T-\mathit{1}$ Do

      $\text{SA}\leftarrow \text{SA}+{\text{AP}}_y$

    End for

   (ii) Calculate the relative payoff

     $\text{RP}\leftarrow {\text{AP}}_i/\text{SA}$

Step  6. Calculate the payoff V of the coalition:

     $V\leftarrow \alpha \mu (\text{AP})+\beta \lambda (\text{RP})$

Step  7. Return V

The execution times of Steps 1, 2, 3, 4, and 5 are $O(N)$ , $O(N)$ , $O(N)+O(M)$ , $O(N)$ , and $O(T)$ , respectively, so the execution time of Algorithm 1 is $O(M)$ , where M is the number of the wireless sensor nodes that participate in the game process. Algorithm 1 is illustrated by the following example.

Example 1.

There are n nodes in the game activity and suppose nodes 1, 2, and 3 are the coalition members. The parameter sets of all nodes are $p_1=\{e_1,d_1,h_1,g_1,r_1\},\hspace{0.17em}{p}_2=\{e_2,d_2,h_2,g_2,r_2\},\dots ,\hspace{0.17em}{p}_n=\{e_n,d_n,h_n,g_n,r_n\}$ , respectively. The largest number of the hops from these nodes to the sink is H. The longest distance from all these nodes to the sink is D.

By Step 1~Step 3 of Algorithm 1, the energy level (L), distance cost (DC), and generating message group's proportion (P) of the coalition can be calculated, respectively, as

$$\begin{array}{cc}& L=\frac{{\sum }_{i=\mathrm{1}}^{\mathrm{3}}{e}_i}{{\sum }_{i=\mathrm{1}}^n{e}_i},\hspace{1em}\hspace{1em}\text{DC}=\frac{{\sum }_{i=\mathrm{1}}^{\mathrm{3}}(d_i+h_i)}{\mathrm{3}\times \left(D+N\right)},\hspace{1em}\hspace{1em}P=\frac{{\sum }_{i=\mathrm{1}}^{\mathrm{3}}{g}_i}{{\sum }_{i=\mathrm{1}}^n{g}_i}.\end{array}$$

(4)

Following, by Steps 4 and 5, the absolute payoff (AP) and the relative payoff (RP) of the coalition can be calculated. Then, by Step 6, the payoff of the coalition can be obtained ultimately.

4. Forming Energy-Efficient Coalitions for WSNs

In this section, we will use the Markov process to model the forming process of the state with the largest absorbing coefficient. The state is composed of several individuals or coalitions. We will give the Shapley value configuration as the sharing method of the coalitions, the transfer probability and the absorbing coefficient, and the simulation algorithm of the forming process of the state with the largest absorbing coefficient in Sections 4.1, 4.2, and 4.3, respectively.

4.1. Shapley Values Configuration in WSN Coalitions

The concept of Shapley value is given by Shapley [19], and it is a fair and unique payoff configuration of a coalition according to the contributions of the players in the coalition group. In our study, Shapley values will be adopted and calculated for each node to decide which WSN coalitions that this node will join into.

Let $N=\{\mathrm{1,2},\dots ,n\}$ be the set of nodes, which means that there are n players in this game activity. A game is a map from a set of all subsets of N to real numbers, that is, $2^N\to R$ , where each subset S of N is a coalition. Some of these coalitions will form a coalition profile $P=\{S_1,S_2,\dots ,S_m\}$ , which we will take as the Markov process states, and ${\bigcup }_{S_1}^{S_m}=N$ . $V(S)$ is the payoff achieved by the nodes in S, where V is the payoff function given in Section 3 and returned by Algorithm 1.

Let ${\phi }_i(V)$ be the Shapley value of player i, and the Shapley value can be calculated by the following formula [4]:

$$\begin{array}{cc}& {\phi }_i\left(V\right)={\displaystyle \sum }_S\frac{\left(\left|S\right|-\mathrm{1}\right)!\left(n-\left|S\right|!\right)}{n!}\left(V\left(S\right)-V\left(S-\left\{i\right\}\right)\right),\end{array}$$

(5)

where n is the number of the nodes that participate in the game activity, S represents the coalition containing player i, $\left|S\right|$ is the number of the players in coalition S, and $V(S-\{i\})$ is the payoff of the coalitions without player i.

In order to describe the Shapley value clearly, we present some notations at first. V is the payoff function, and $x_i$ is the payoff of node i obtained from the coalition. If all the nodes are willing to conform a coalition, then how to allocate the payoff is to be considered. A reasonable payoff configuration is to allocate the accordance with the contribution of nodes to the coalition, that is,

$$\begin{array}{cc}& x_{\mathrm{1}}=V\left(\left\{\mathrm{1}\right\}\right),\\ x_{\mathrm{2}}=V\left(\left\{\mathrm{1,2}\right\}\right)-V\left(\left\{\mathrm{1}\right\}\right),\dots ,x_n=V\left(N\right)-V\left(N-\left\{n\right\}\right).\end{array}$$

(6)

According to the conventions of the Shapley value, the payoff should be independent of the sequence of nodes. Therefore, the average contribution of the nodes is considered. There are $n!$ different sequences for n players, and we can obtain the average Shapley value of these $n!$ sequences as follows:

$$\begin{array}{cc}& {\phi }_i\left(V\right)=\frac{\mathrm{1}}{n!}{\displaystyle \sum }\left[V\left(S\right)-V\left(S-\left\{i\right\}\right)\right],\hspace{1em}i=\mathrm{1,2},\dots ,n,\end{array}$$

(7)

where $\sum \hspace{0.17em}$ is the sum of payoffs of every possible sequence. Formula (5) is the transmutation of formula (7).

Example 2.

WSN nodes are denoted as 1, 2, 3, and 4 that participate in the game activity. The payoff of the WSN coalitions is $V(\{1\})=v_1$ , $V(\{2\})=v_2$ , $V(\{3\})=v_3$ , $V(\{4\})=v_4$ , $V(\{\mathrm{1,2}\})=v_{12}$ , $V(\{\mathrm{1,3}\})=v_{13}$ , $V(\{\mathrm{1,4}\})=v_{14}$ , $V(\{\mathrm{2,3}\})=v_{23}$ , $V(\{\mathrm{2,4}\})=v_{24}$ , $V(\{\mathrm{3,4}\})=v_{34}$ , $V(\{\mathrm{1,2},3\})=v_{123}$ , $V(\{\mathrm{1,2},4\})=v_{124}$ , $V(\{\mathrm{1,3},4\})=v_{134}$ , $V(\{\mathrm{2,3},4\})=v_{234}$ , and $V(\{\mathrm{1,2},\mathrm{3,4}\})=v_{1234}$ . By formula (7), we can obtain

$$\begin{array}{l}{\phi }_{\mathrm{1}}\left(V\right)=\frac{\mathrm{0}!\mathrm{4}!}{\mathrm{4}!}\left(v_{\mathrm{1}}-\mathrm{0}\right)+\frac{\mathrm{1}!\mathrm{2}!}{\mathrm{4}!}\left(v_{\mathrm{12}}-v_{\mathrm{2}}\right)+\frac{\mathrm{1}!\mathrm{2}!}{\mathrm{4}!}\left(v_{\mathrm{13}}-v_{\mathrm{3}}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}+\frac{\mathrm{1}!\mathrm{2}!}{\mathrm{4}!}\left(v_{\mathrm{14}}-v_{\mathrm{4}}\right)+\frac{\mathrm{2}!\mathrm{1}!}{\mathrm{4}!}\left(v_{\mathrm{123}}-v_{\mathrm{23}}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}+\frac{\mathrm{2}!\mathrm{1}!}{\mathrm{4}!}\left(v_{\mathrm{124}}-v_{\mathrm{24}}\right)+\frac{\mathrm{2}!\mathrm{1}!}{\mathrm{4}!}\left(v_{\mathrm{134}}-v_{\mathrm{34}}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}+\frac{\mathrm{3}!\mathrm{0}!}{\mathrm{4}!}\left(v_{\mathrm{1234}}-v_{\mathrm{234}}\right)\\ \hspace{1em}\hspace{1em}=v_{\mathrm{1}}+\frac{\mathrm{1}}{\mathrm{12}}\left(v_{\mathrm{12}}-v_{\mathrm{2}}\right)+\frac{\mathrm{1}}{\mathrm{12}}\left(v_{\mathrm{13}}-v_{\mathrm{3}}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}+\frac{\mathrm{1}}{\mathrm{12}}\left(v_{\mathrm{14}}-v_{\mathrm{4}}\right)+\frac{\mathrm{1}}{\mathrm{12}}\left(v_{\mathrm{123}}-v_{\mathrm{23}}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}+\frac{\mathrm{1}}{\mathrm{12}}\left(v_{\mathrm{124}}-v_{\mathrm{24}}\right)+\frac{\mathrm{1}}{\mathrm{12}}\left(v_{\mathrm{134}}-v_{\mathrm{34}}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}+\frac{\mathrm{1}}{\mathrm{4}}\left(v_{\mathrm{1234}}-v_{\mathrm{234}}\right).\end{array}$$

(8)

Similarly, we can obtain ${\phi }_2(V)$ , ${\phi }_3(V)$ , and ${\phi }_4(V)$ , respectively.

4.2. Transfer Probability and Absorbing Coefficient

From the concept and the formula for calculating the Shapley values, we know that if a node wants to improve its payoff, the only thing is to leave the present coalition and join into another one. Here we suppose that every node is allowed to leave the present coalition and participate in any other ones if it wants. Which coalition does the node most wish to join into and how to measure this tendency? In order to address these problems, we give the concepts of transfer probability and absorbing coefficient in this subsection.

We adopt Markov process [21] to simulate the transfer process of coalition profiles. All WSN energy-efficient coalition profiles form the set of the Markov process states, $\mathrm{\Omega }=\{w_1,w_2,\dots ,w_n\}$ . First, we make the following assumptions.

• (i)

  Any of the future states is independent of the previous states and only related to the present state. Any state transfer process is said to be a stochastic process. “ $t_n=w_i$ ” means that the state is $w_i$ at time slot $t_n$ , that is, $P\{t_{n+1}=w_{n+1}\hspace{0.17em}|\hspace{0.17em}{t}_n=w_n,t_{n-1}=w_{n-1},\dots ,t_0=w_0\}=P\{t_{n+1}=w_{n+1}\hspace{0.17em}|\hspace{0.17em}{t}_n=w_n\}$ .

• (ii)

  The 1-step transfer probability $P\{t_n=w_k\hspace{0.17em}|\hspace{0.17em}{t}_{n-1}=w_l\}$ is denoted by $P_{lk}^{(1)}$ briefly, which represents the probability of transferring state $w_l$ to state $w_k$ .

It is known that the basic idea of the Bargaining set [21] is: if there is a player i who is not satisfied with the payoff of j in the current coalition, it will choose to form a new coalition without player j. From the concept of transfer probability and the idea of Bargaining set, we know that calculating $P_{lk}^{(1)}$ is based on the transfer factor ${\beta }_i(w_l\hspace{0.17em}|\hspace{0.17em}{w}_k)$ of node i. In this new coalition, player i will get more payoff and the other players will also get at least the same payoff as in the primary coalition. To find an exact optimal coalition by the concept of bargaining set is NP-hard [21]. Thus, to find the optimal coalition in a feasible time, we first define the transfer factor.

Definition 3.

Transfer factor ${\beta }_i(w_l\hspace{0.17em}|\hspace{0.17em}{w}_k)$ is the measure of the benefit obtained by the node i when transferring state $w_l$ to $w_k$ , defined as follows:

$$\begin{array}{cc}& {\beta }_i\left(w_l\hspace{0.17em}|\hspace{0.17em}{w}_k\right)=\{\begin{array}{cc}1\hfill & \text{If}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{player}\mathrm{\hspace{0.17em}\hspace{0.17em}}i\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{can}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{obtain}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{a}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{better}\mathrm{\hspace{0.17em}\hspace{0.17em}}\left(\text{or}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{at}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{least}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{the}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{same}\right)\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{ration}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{through}\hfill \\ \hfill & \text{transferring}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{state}\mathrm{\hspace{0.17em}\hspace{0.17em}}{w}_l\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{state}\mathrm{\hspace{0.17em}\hspace{0.17em}}{w}_k\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{and}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{the}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{rations}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{of}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{the}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{remainders}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{in}\mathrm{\hspace{0.17em}\hspace{0.17em}}{w}_k\hfill \\ \hfill & \text{are}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{not}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{less}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{than}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{that}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{in}\mathrm{\hspace{0.17em}\hspace{0.17em}}{w}_k\hfill \\ 0\hfill & \text{Otherwise}.\hfill \end{array}\end{array}$$

(9)

Then, $P_{lk}^{(1)}$ can be obtained based on the transfer factor as follows:

$$\begin{array}{cc}& P_{lk}^{\left(1\right)}=\frac{{\sum }_{i=\mathrm{1}}^n{\beta }_i\left(w_l\hspace{0.17em}|\hspace{0.17em}{w}_k\right)}{{\sum }_{w_j\in \mathrm{\Omega }}\left({\sum }_{i=\mathrm{1}}^n{\beta }_i\left(w_l\hspace{0.17em}|\hspace{0.17em}{w}_j\right)\right)}.\end{array}$$

(10)

We note that $P_{ij}^{(1)}\ge 0$ ( $w_i,w_j\in \mathrm{\Omega }$ ) and ${\sum }_{w_j\in \mathrm{\Omega }}^{}{P}_{ij}^{(1)}=1$ .

Based on the formula of 1-step transfer probability calculation, we give the m-step transfer probability $P_{ij}^{(m)}$ from state $w_i$ to state $w_j$ as follows:

$$\begin{array}{l}{P}_{ij}^{\left(m\right)}=P\left(m=w_j,\hspace{0.17em}\hspace{0.17em}k\ne w_j,\hspace{0.17em}\hspace{0.17em}k=\mathrm{1,2},\dots ,m-\mathrm{1}\hspace{0.17em}|\hspace{0.17em}{t}_{\mathrm{0}}=w_i\right),\\ \hspace{1em}\hspace{1em}\phantom{0000000000000000000000000000000000000}m\mathrm{\hspace{0.17em}\hspace{0.17em}}\ge \mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{2}.\end{array}$$

(11)

State i may reach state j by one step, two steps,…. The sum of all these transfer probabilities is denoted by $f_{ij}$ , and $f_{ij}={\sum }_{m=\mathrm{1}}^{\infty }{P}_{ij}^m$ . Thus, the concept of the absorbing coefficient of state $w_j$ is defined on the basis of $f_{ij}$ .

Definition 4.

The absorbing coefficient of state $w_j$ is defined as follows:

$$\begin{array}{cc}& \mathrm{AC}\left(j\right)={\displaystyle \sum }_{w_i\in \mathrm{\Omega }}{f}_{ij},\end{array}$$

(12)

where $f_{ij}$ is the sum of all transfer probabilities.

This means that $\mathrm{AC}(j)$ is exactly the measure of the performance of $w_j$ . A state with the maximal absorbing coefficient means that most states want to jump into this state, which is a reasonable state we can choose as our ultimate coalition profile. In this profile, each WSN node can get the best Shapley value payoff; that is, the nodes work in this profile can reduce energy consumption even more.

Following, we give an example to illustrate the above concepts.

Example 5.

Four nodes in the WSN participate in the game activity, denoted as 1, 2, 3, and 4. The Shapley value payoffs of those nodes in each state are $w_1=\{\mathrm{0.4,0.2,0.4}\}$ , $w_2=\{\mathrm{0.5,0.1,0.4}\}$ , $w_3=\{\mathrm{0.3,0.4,0.3}\}$ , and $w_4=\{\mathrm{0.3,0.5,0.2}\}$ , respectively.

According to Definition 3, the transfer factor of each node can be calculated as follows:

$$\begin{array}{cc}& {\beta }_{\mathrm{1}}\left(w_{\mathrm{1}}\hspace{0.17em}|\hspace{0.17em}{w}_{\mathrm{2}}\right)=\mathrm{1},\hspace{1em}\hspace{1em}{\beta }_{\mathrm{2}}\left(w_{\mathrm{1}}\hspace{0.17em}|\hspace{0.17em}{w}_{\mathrm{2}}\right)=\mathrm{0},\hspace{1em}\hspace{1em}{\beta }_{\mathrm{3}}\left(w_{\mathrm{1}}\hspace{0.17em}|\hspace{0.17em}{w}_{\mathrm{2}}\right)=\mathrm{1};\\ {\beta }_{\mathrm{1}}\left(w_{\mathrm{1}}\hspace{0.17em}|\hspace{0.17em}{w}_{\mathrm{3}}\right)=\mathrm{0},\hspace{1em}\hspace{1em}{\beta }_{\mathrm{2}}\left(w_{\mathrm{1}}\hspace{0.17em}|\hspace{0.17em}{w}_{\mathrm{3}}\right)=\mathrm{1},\hspace{1em}\hspace{1em}{\beta }_{\mathrm{3}}\left(w_{\mathrm{1}}\hspace{0.17em}|\hspace{0.17em}{w}_{\mathrm{3}}\right)=\mathrm{0};\\ {\beta }_{\mathrm{1}}\left(w_{\mathrm{1}}\hspace{0.17em}|\hspace{0.17em}{w}_{\mathrm{4}}\right)=\mathrm{0},\hspace{1em}\hspace{1em}{\beta }_{\mathrm{2}}\left(w_{\mathrm{1}}\hspace{0.17em}|\hspace{0.17em}{w}_{\mathrm{4}}\right)=\mathrm{1},\hspace{1em}\hspace{1em}{\beta }_{\mathrm{3}}\left(w_{\mathrm{1}}\hspace{0.17em}|\hspace{0.17em}{w}_{\mathrm{4}}\right)=\mathrm{0};\\ {\beta }_{\mathrm{1}}\left(w_{\mathrm{2}}\hspace{0.17em}|\hspace{0.17em}{w}_{\mathrm{1}}\right)=\mathrm{0},\hspace{1em}\hspace{1em}{\beta }_{\mathrm{2}}\left(w_{\mathrm{2}}\hspace{0.17em}|\hspace{0.17em}{w}_{\mathrm{3}}\right)=\mathrm{1},\hspace{1em}\hspace{1em}{\beta }_{\mathrm{3}}\left(w_{\mathrm{2}}\hspace{0.17em}|\hspace{0.17em}{w}_{\mathrm{4}}\right)=\mathrm{1}.\end{array}$$

(13)

Then, according to formula (10), the 1-step transfer probabilities can be obtained as follows:

$$\begin{array}{cc}& P_{\mathrm{21}}^{\left(\mathrm{1}\right)}=\frac{\mathrm{0}+\mathrm{1}+\mathrm{1}}{\mathrm{0}+\mathrm{1}+\mathrm{1}+\mathrm{0}+\mathrm{1}+\mathrm{0}+\mathrm{0}+\mathrm{1}+\mathrm{0}}=\frac{\mathrm{1}}{\mathrm{2}},\\ P_{\mathrm{23}}^{\left(\mathrm{1}\right)}=\frac{\mathrm{0}+\mathrm{1}+\mathrm{1}}{\mathrm{0}+\mathrm{1}+\mathrm{1}+\mathrm{0}+\mathrm{1}+\mathrm{0}+\mathrm{0}+\mathrm{1}+\mathrm{0}}=\frac{\mathrm{1}}{\mathrm{4}},\\ P_{\mathrm{24}}^{\left(\mathrm{1}\right)}=\frac{\mathrm{0}+\mathrm{1}+\mathrm{0}}{\mathrm{0}+\mathrm{1}+\mathrm{1}+\mathrm{0}+\mathrm{1}+\mathrm{0}+\mathrm{0}+\mathrm{1}+\mathrm{0}}=\frac{\mathrm{1}}{\mathrm{4}},\\ P_{\mathrm{12}}^{\left(\mathrm{1}\right)}=\frac{\mathrm{1}+\mathrm{0}+\mathrm{1}}{\mathrm{1}+\mathrm{0}+\mathrm{1}+\mathrm{0}+\mathrm{1}+\mathrm{0}+\mathrm{0}+\mathrm{1}+\mathrm{0}}=\frac{\mathrm{1}}{\mathrm{2}},\\ P_{\mathrm{13}}^{\left(\mathrm{1}\right)}=\frac{\mathrm{0}+\mathrm{1}+\mathrm{0}}{\mathrm{1}+\mathrm{0}+\mathrm{1}+\mathrm{0}+\mathrm{1}+\mathrm{0}+\mathrm{0}+\mathrm{1}+\mathrm{0}}=\frac{\mathrm{1}}{\mathrm{4}},\\ P_{\mathrm{14}}^{\left(\mathrm{1}\right)}=\frac{\mathrm{0}+\mathrm{1}+\mathrm{0}}{\mathrm{1}+\mathrm{0}+\mathrm{1}+\mathrm{0}+\mathrm{1}+\mathrm{0}+\mathrm{0}+\mathrm{1}+\mathrm{0}}=\frac{\mathrm{1}}{\mathrm{4}}.\end{array}$$

(14)

Consequently, based on the 1-step transfer probabilities, the 2-step transfer probabilities can be obtained as follows:

$$\begin{array}{cc}& P_{\mathrm{13}}^{\left(\mathrm{2}\right)}=\frac{\mathrm{1}}{\mathrm{2}}\times \frac{\mathrm{1}}{\mathrm{4}}=\frac{\mathrm{1}}{\mathrm{8}},\hspace{1em}\hspace{1em}{P}_{\mathrm{14}}^{\left(\mathrm{2}\right)}=\frac{\mathrm{1}}{\mathrm{2}}\times \frac{\mathrm{1}}{\mathrm{4}}=\frac{\mathrm{1}}{\mathrm{8}}.\end{array}$$

(15)

The state path of $P_{13}^{(2)}$ is “ $w_1\to w_2\to w_3$ ” and the state path of $P_{14}^{(2)}$ is “ $w_1\to w_2\to w_4$ .” Any other m-step ( $m\ge 1$ ) transfer probabilities can be calculated in the same way. Then, according to Definition 4, the absorbing coefficient can be calculated based on these transfer probabilities.

4.3. Finding WSN Coalitions

Based on the ideas given in Section 4.2, Algorithm 2 simulate the forming process of the state with the maximal absorbing coefficient.

Algorithm 2: Finding the maximum-absorbing coefficient state.

Input: The state space $\mathrm{\Omega }=\{w_{\mathit{1}},w_{\mathit{2}},\dots ,w_n\}$

Output: The maximum-absorbing coefficient state

Local variables:

   A: the matrix of the transfer probabilities ( $P_{ij}^{(1)}$ )

   $\mathrm{AC}(w_j)$ : the absorbing coefficient of state $w_j$

   M: the maximal number of the random samples, depending on the number of WSN

   coalition profiles. Without loss of generality, we assign 2000 to M as the upper bound

   of random samples

   $S_o$ : the original state

   $S_e$ : the ultimate state

   $S_c$ : the current state

   l: the order of the current state $S_c$

   α: a random number

   $r_t$ : the $t_{th}$ path from $S_{\mathit{0}}$ to $S_e$

   $P_t$ : the transfer probability on $r_t$

   $R_{jk}$ : the set of paths from $w_j$ to $w_k$

   $F_{jk}$ : the sum of transfer probability on all $r_t\in R_{jk}$

Steps:

Step  1. Calculate the matrix of transfer probabilities

            $A=\left[\begin{array}{cccc}{P}_{\mathrm{11}}& P_{\mathrm{12}}& \cdots & P_{\mathrm{1}\mathrm{n}}\\ P_{\mathrm{21}}& P_{\mathrm{22}}& \cdots & P_{\mathrm{2}\mathrm{n}}\\ ⋮& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}\\ P_{\mathrm{n}\mathrm{1}}& P_{\mathrm{n}\mathrm{2}}& \cdots & P_{\mathrm{n}\mathrm{n}}\end{array}\right]$

Step  2. Calculate $\mathrm{AC}(w_k)$ , $w_k\in \mathrm{\Omega }$

  For each $w_k\in \mathrm{\Omega }$ Do

    $S_e\leftarrow w_k$ , $\mathrm{AC}(w_k)\leftarrow \mathit{0}$

   Calculate $f_{jk}$ :

     For each $w_j\in \mathrm{\Omega }$ Do

     Initialization:

       $t\leftarrow \mathit{1}$ , $S_o\leftarrow w_j$ , $l\leftarrow j$ , $r_t\leftarrow S_o$ , $p_t\leftarrow \mathit{1}$ , $R_{jk}\leftarrow \varphi$ , $F_{jk}\leftarrow \mathit{0}$

     For $m\leftarrow \mathit{1}$ to M Do

       Generate a random number

       If there is an m such that ${{\displaystyle \sum }}_{e=\mathit{1}}^m{P}_{le}<\alpha <{{\displaystyle \sum }}_{e=\mathit{1}}^{m+\mathit{1}}{P}_{le}$ Then

         $P_t\leftarrow P_t·P_{lm}$

       End if

        $l\leftarrow m$ , $S_c\leftarrow w_m$ , $r_t\leftarrow r_t\cup S_c$

       If $S_o=S_e$ Then

         $R_{jk}\leftarrow R_{jk}\cup r_t$ , $F_{jk}\leftarrow F_{jk}+P_t$ , $t\leftarrow t+\mathit{1}$

         $S_{\mathit{0}}\leftarrow w_j$ , $l\leftarrow j$ , $r_t\leftarrow S_o$ , $P_t\leftarrow \mathit{1}$

       End if

      End for m

     End for j

     $\mathrm{AC}(w_k)\leftarrow \mathrm{AC}(w_k)+F_{jk}$

  End for k

Step  3. Select the maximal-absorbing coefficient state from all $\mathrm{AC}(w_k)$ , $w_k\in \mathrm{\Omega }$

Step  4. Return the maximal-absorbing coefficient state

Clearly, the time complexity of Algorithm 2 is $O(M{n}^2)$ , where n is the number of states in Ω, and the value of M depends on the number of WSN coalition profiles (states). For example, there are four coalition profiles in the game process, and then each current state has four choices to move to the next step, so there are $4^3=64$ paths from the beginning state to the end state. Obviously, if M is large enough ( $M\ge 64$ ), each path between two states can be passed and the absorbing coefficient can be calculated exactly. Then the state with the maximal absorbing coefficient can be found correctly. The algorithm's execution time is sensitive to the coalition profiles due to the sampling method in Algorithm 2. Therefore, to improve the algorithm by adopting a more efficient sampling method is our future work.

5. Nash Equilibrium of WSN Coalitions

The state with a reasonable payoff configuration can be found according to the model given in Section 4. How to determine the data transmission strategies of the coalitions to guarantee the reachability of the WSN is considered in this section. For this purpose, a payoff function based on the data transmission strategy is given in Section 5.1, upon which an NE model is proposed in Section 5.2.

5.1. NE Payoff Function Based on Data Transmission Strategies

To measure the performance of the strategies chosen by the coalitions, we give an NE payoff function in this subsection. The strategy with the largest payoff is the optimal of the coalition. When each coalition chooses its optimal strategy, the coalition profile reaches a NE.

The coalition profile formed by Algorithm 2 can be denoted as $W=\{X_1,X_2,\dots ,X_l\}$ , where $X_i\hspace{0.17em}\hspace{0.17em}(i=\mathrm{1,2},\dots ,l)$ may be an individual node or a WSN coalition. Individual node is a special coalition with just one node. Based on the proportion of the message groups that have been sent or forwarded, we give the coalition payoff function for the NE model. This payoff function is composed of the absolute and the relative payoff formulas, where the former is the measure of the satisfactory degree of the coalition members to the present data transmission strategy, and the latter is the measure of the contribution of the coalition to the WSN with the present strategy.

The concept of energy level is the same as that in Section 3.1. The cooperative degree ( $C_i$ ) is the measure of the cooperation and

$$\begin{array}{cc}& C_i=\frac{{\sum }_{l=\mathrm{1}}^m{r}_l}{{\sum }_{l=\mathrm{1}}^m{a}_l},\end{array}$$

(16)

where m is the number of nodes in the coalition, $r_i$ is the number of the message groups forwarded by node i, and $a_i$ is the number of the message groups sent and forwarded by node i.

$C_i=1$ means that coalition i has high degree of cooperation. To balance the energy consumption and send its own message groups, the coalition will forward less message groups. On the other hand, if $C_i$ is close to 0, then coalition i will try to forward as much message groups as it can.

Based on the energy level and the cooperative degree, the absolute payoff is given to measure the satisfactory degree of the coalition members. The larger the absolute payoff is, the more satisfied the members feel with the strategy, the less possibly the members change their strategies in next time slot, and consequently the higher the WSN's reachability will be. The absolute payoff can be calculated as follows:

$$\begin{array}{cc}& {\text{NEA}}_i=C_i·\left(\mathrm{1}-L_i\right)·W_i+\left(\mathrm{1}-C_i\right)·\mathrm{\hspace{0.17em}\hspace{0.17em}}{L}_i·\mathrm{\hspace{0.17em}\hspace{0.17em}}{Q}_i,\end{array}$$

(17)

where $W_i$ is the proportion of the message groups sent and $Q_i$ is the proportion of that forwarded by coalition i. $W_i$ and $Q_i$ can be calculated, respectively, as follows:

$$\begin{array}{cc}& W_i=\frac{{\sum }_{l=\mathrm{1}}^m{s}_l}{{\sum }_{l=\mathrm{1}}^m{s}_l^{\prime }},\\ Q_i=\frac{{\sum }_{l=\mathrm{1}}^m{r}_l}{{\sum }_{l=\mathrm{1}}^m{r}_l^{\prime }},\end{array}$$

(18)

where $s_i$ is the number of the message groups forwarded, $r_i^{\prime }$ is the number of the message groups need to be forwarded by node i, and $s_i^{\prime }$ is the number of the message groups that need to be sent by node i.

How much is the contribution of the present strategy? We give the relative payoff ( ${\text{NER}}_i$ ) to measure this contribution as follows:

$$\begin{array}{cc}& \text{NE}{\text{R}}_i=\frac{{\text{NEA}}_i}{{\sum }_{l=\mathrm{1}}^T{\text{NEA}}_l},\end{array}$$

(19)

where T is the number of the coalitions in whole networks. The larger the relative payoff is, the more possibly the present strategy will be chosen.

Based on formula (17) and (19), we define the coalition payoff function $f_i$ as follows:

$$\begin{array}{cc}& f_i=a\mu \left({\text{NEA}}_i\right)+b\lambda \left({\text{NER}}_j\right),\end{array}$$

(20)

where both $\mu ()$ and $\lambda ()$ are convex, derivable, and strict increasing functions, $a>0$ and $b>0$ .

To ensure the validity of the NE payoff function, there also exists

$$\begin{array}{cc}& e_c\left(s_i+r_i\right)<E_i,\end{array}$$

(21)

where $e_c$ is the energy consumption for each message group and $E_i$ is the energy of coalition i, where $s_{ik}>0$ , $r_i>0$ , $s_i\le s_i^{\prime }$ , $r_i\le r_i^{\prime }$ .

5.2. Nash Equilibrium of WSN Coalitions

An NE [4] is a strategy profile in which the strategy of each player is the optimal reflection to that of all the other players. According to the payoff-function model given in Section 5.1, all WSN coalitions in the coalition profile want to improve their absolute payoffs ( ${\text{NEA}}_i$ ), which will affect the WSN's reachability. To guarantee the reachability of the WSN. The proportion of the message groups forwarded by coalition i (denoted by $a_{i2}$ ) must not be zero, since the transmission capability is finite and the energy is limited, the proportion of the message groups sent by coalition i (denoted as $a_{i1}$ ) may not be 1, and the NE is given to determine the values of $a_{i1}$ and $a_{i2}$ , where $a_{i1},a_{i2}\in [\mathrm{0,1}]$ , so that the optimal absolute payoff can be obtained to guarantee the WSN's reachability.

We know that the computation of finding an exact Nash equilibrium is generally in the class of NP [24]. To determine $a_{i1}$ and $a_{i2}$ in a feasible time, we give a genetic algorithm to compute an approximate NE in a space of discrete mixed degree. Some relevant concepts will be given at first [25].

Definition 6.

Let $\sigma =\{{\delta }_1,{\delta }_2,\dots ,{\delta }_k\}$ be a strategy profile. ${\delta }_i=\{a_{i1},a_{i2}\}$ , where $a_{i1}$ is the proportion of message groups sent by coalition i and $a_{i2}$ is the proportion of that forwarded by coalition i. The regret degree of strategies with respect to σ is denoted by ${\text{Reg}}_i(\sigma )$ , and ${\text{Reg}}_i(\sigma )=\max \{f_i({\sigma }_{-i},{\sigma }_i^{\prime })-f_i(\sigma )\}$ , where $f_i(\sigma )$ is the expected payoff of coalition i to the given strategy profile σ, ${\sigma }_{-i}$ is the strategy profile of coalitions except coalition i, and ${\sigma }_i^{\prime }$ is the other strategies of coalition i.

In this definition, ${\text{Reg}}_i(\sigma )$ means the gainable maximum expected payoff of coalition i when ${\delta }_i$ is deviated unilaterally in σ. Note that if the expected payoff cannot be improved by changing strategies unilaterally, coalition i will not change its strategy in σ, so ${\text{Reg}}_i(\sigma )\ge 0$ . Based on the definition of regret degree, we now define the approximate NE.

Definition 7.

Let G be an n-player game (all players are in coalitions). A strategy profile σ is an ε-Nash equilibrium of G, if ${\text{Reg}}_i(\sigma )\le \epsilon$ for player i, where ε is called the approximate degree.

We know that for any finite strategy game, there is an NE profile in a space of continuous mixed strategies. To reduce the computing scale, we discuss an NE in a space of discrete mixed strategies. $A_i=\{a_{i1},a_{i2}\}$ is the strategy set of coalition i, where $a_{i1}$ and $a_{i2}$ are the proportion of the message groups sent and forwarded, respectively, by coalition i. The discrete mixed strategies of player i are a function ${\delta }_i$ : $A_i\to [0,\tau ,2\tau ,\dots ,1]$ , where τ is called the discrete degree.

The sum of all the regret degrees in a strategy profile σ is denoted by $\text{Sreg}(\sigma )$ : $\text{Sreg}(\sigma )={\sum }_{l=1}^n{\text{Reg}}_l(\sigma )$ . For ${\text{Reg}}_i(\sigma )\ge 0$ , $\text{Sreg}(\sigma )\ge 0$ . If most of the coalitions will not change their present strategy, then $\text{Sreg}(\sigma )$ will be exactly a small value. When all the coalitions do not change current strategies, $\text{Sreg}(\sigma )$ will be 0.

In the genetic algorithm, a strategy profile will be taken as an individual and a population contains n $(n\ge 2)$ individuals. To distinguish each individual, $\text{Sreg}(\sigma )$ will be denoted by $\text{Sreg}({\sigma }_j)$ , where ${\sigma }_j$ is the jth individual of present population. Fitness is the measure of the superiority of an individual. An individual with a larger fitness has more chance to reproduce the next generation and its genes can be kept better. Based on $\text{Sreg}({\sigma }_j)$ , we give the concept of the fitness (denoted by $F({\sigma }_j)$ ).

Definition 8 ( $F({\sigma }_j)={1/(Sreg({\sigma }_j)+\mathrm{1})}^4$ is called the fitness).

Note that $F({\sigma }_j)=1$ if $\text{Sreg}({\sigma }_j)=0$ . That is, the strategy profile (individual) with fewer coalitions that change their strategies has larger fitness and the strategy profile can be kept with larger probability. In order to compare the fitness of individuals obviously, we give a new measure, denoted by $\text{Eval}({\sigma }_j)$ and calculated as

$$\begin{array}{cc}& \text{Eval}\left({\sigma }_j\right)=\frac{F\left({\sigma }_j\right)}{{\sum }_{l=\mathrm{1}}^{S}F\left({\sigma }_l\right)}.\end{array}$$

(22)

To illustrate the above concepts, we give the following example.

Example 9.

There are 3 coalitions in the network, where the strategy profile is $\sigma =\{\{a_{11},a_{12}\},\{a_{21},a_{22}\},\{a_{31},a_{32}\}\}$ . We can calculate the payoff of coalition 1, $f_1(\sigma )$ , in the strategy profile σ. Then, we just change the strategy of coalition 1 to get the new strategy profiles ${\sigma }_1,{\sigma }_2,\dots$ . The regret degree of coalition 1 can be calculated by ${\text{Reg}}_1(\sigma )=\max ((f_1({\sigma }_1)-f_1(\sigma )),(f_1({\sigma }_2)-f_1(\sigma )),\dots )$ . The regret degree of coalitions 2 and 3 can be calculated by the same way. Then, $\text{Sreg}({\sigma }_j)$ can be calculated, and $\text{Sreg}(\sigma )={\text{Reg}}_1(\sigma )+{\text{Reg}}_2(\sigma )+{\text{Reg}}_{\mathrm{3}}(\sigma )$ , upon which the fitness of σ can be calculated.

Based on the above relevant concepts and the NE payoff function, we give the genetic algorithm to calculate the approximate NE (see Algorithm 3).

Algorithm 3: Genetic algorithm for solving an approximate Nash equilibrium.

Input:

   $N=\{\mathit{1,2},\dots ,n\}$ : the set of the coalitions

   $\overrightarrow{A_i}=\{a_{i\mathit{1}},a_{i\mathit{2}}\}$ , $i\in \{\mathit{1,2},\dots ,n\}$ : the set of strategies of coalition i

   τ: the discrete degree

   ε: the approximate degree

Output: An ε-Nash equilibrium

Local variables:

   S: the number of individuals in a population

   P: the present population

   $P_{\text{new}}$ : the new population

   $P_c$ : the crossover probability

   $P_m$ : the mutate probability

Steps:

Step  1. Initialize population:

   Generate s individuals $\sigma j=\{\delta \mathit{1},\delta \mathit{2},\dots ,\delta k\}$ ( $j=\mathit{1,2},\dots ,s$ ), where ${\delta }_i=\{a_{i\mathit{1}},a_{i\mathit{2}}\}$

   ( $a_{i\mathit{1}},a_{i\mathit{2}}=l\tau$ , where $l=\mathit{0}$ , 1, …). The initial s-size population P is the set of these

   individuals

Step  2. Evaluate:

   For each individual ${\sigma }_j\in P$ , compute fitness $F({\sigma }_j)$ and $F({\sigma }_j)$ = (Sreg( ${\sigma }_j$ ) + 1)⁻⁴

Step  3. While Max $\{F({\sigma }_j)\}\le \epsilon$ Do

   Generate a new population $P_{\text{new}}$

   (i) Select

   Probabilistically select s members of P and add P to $P_{\text{new}}$ . The probability

    $P({\sigma }_j)$ of selecting individual ${\sigma }_j$ from P is given by

              $P({\sigma }_j)=\frac{F({\sigma }_j)}{{\sum }_{l=\mathrm{1}}^{S}F({\sigma }_l)}$         (*)

   (ii) Crossover

    Probabilistically select $s/\mathrm{2}\times P_c$ pairs of individuals from P, where $P_c=\mathit{0.8}$ .

    For each pair ( ${\sigma }_i$ , ${\sigma }_j$ ), produce two offsprings by the crossover operator and

    then add all offsprings to $P_{\text{new}}$

   (iii) Mutate

   Choose m members of $P_{\text{new}}$ with mutate probability $P_m=\mathit{0.05}$ . For each

   member, randomly select ${\sigma }_j$ and mutate ${\sigma }_j$ to a new individual ${\sigma }_j^{\prime }$

   (iv) Update

    $P\leftarrow P_{\text{new}}$

   (v) Evaluate

   For each ${\sigma }_j$ in P, compute $F({\sigma }_j)$

Step  4. Return the individual from P with the maximal fitness.

   The individual with the maximal fitness is the ε -NE strategy profile. Each

   coalition working in this profile can ensure the WSN's reachability and balance

   the energy consumption of the whole network.

6. Experimental Results

In this section, we present the results of simulation experiments. First, we will show the coalition profiles in different WSN environments. Second, we will show the comparison of energy consumption when the WSN nodes work in different ways. Third, we will show the error rate of NE based on the genetic algorithm and the arriving rate of the message groups when WSN works in the NE.

6.1. WSN Coalition Profile in Different Environment

According to Algorithm 2, we know that the execution time of the experiments is decided by the number of the states $(S)$ and the value of M. $S=2^n$ , $M\ge {(S-1)}^S$ where n is the number of the WSN nodes. Thus, the current model given in this paper is applicable to the small-size networks. We will take the WSN with fewer than 10 nodes in our simulation experiments. The environment is a $100\times 100$ square area, on which sensors are randomly deployed. The location of the sink is (100,100) in the square area. In order to simulate the realistic network, we make the following assumptions in our experiments.

• (i)

  The number of message groups generated by a node in a time slot is affected by its environment, which we will simply take as a random value between 0 and 1000.

• (ii)

  We will also take the number of the message groups that are required to be forwarded by a node as a random value between 0 and 1000.

• (iii)

  Before the network starts to send message, the energy of each node is 1.

• (iv)

  The energy consumption for sending a message group is $2\times {10}^{-10}$ ; that is, each node can send $5\times {10}^9$ message groups at most.

First, we give the network environment with 5, 7, and 9 nodes, respectively. The locations of nodes in each network are generated randomly. Figures 1, 2, and 3 show these networks and their coalition profile, respectively. In a coalition profile, an individual node is a special case of coalition. The nodes connected by lines are coalition members and will work as a whole.

Figure 1

WSN with 5 nodes and its coalition profile.

Figure 2

WSN with 7 nodes and its coalition profile.

Figure 3

WSN with 9 nodes and its coalition profile.

6.2. Comparisons of Energy Consumption

In this subsection, we give comparisons of energy consumption when the WSN nodes work in an ordinary way and that when they work in a cooperative way. In each test, we recorded the result by the average of five simulations.

Figures 4, 5, and 6 show the energy consumption based on the networks given in Figures 1, 2, and 3, respectively, which show the energy consumption when the nodes work alone and that when some nodes work together. It can be seen that the energy-efficient coalition game model proposed in this paper can save the energy consumption of WSN in some way. Based on the above experiment results, we can calculate the rates of lifetime prolonged by our model with different numbers of nodes, shown in Table 1.

Table 1

Rates of prolonged lifetime of WSNs with different nodes.

Number of nodes	Rate of prolonged lifetime
5	49.5%
6	50.2%
8	50.5%
9	51.0%
10	52.3%

Figure 4

Energy consumption of 5-node network shown in Figure 1.

Figure 5

Energy consumption of 7-node network shown in Figure 2.

Figure 6

Energy consumption of 9-node network shown in Figure 3.

It can be seen from Table 1 that the number of WSN nodes will not influence the prolonged lifetime rates greatly, and each coalition has obligation to forward the message groups of the other coalitions. To guarantee the WSN's reachability, the proportion of the message groups forwarded by coalitions should not be small. Therefore, the prolonged lifetime rates of different WSNs are about 50%.

6.3. Genetic Algorithm-Based Nash Equilibrium

In this subsection, we will show the arriving rates of the message groups when the WSNs work in the NE in Figure 7, from which we will check whether and how much the arriving rates can be guaranteed.

Figure 7

Arriving rate of message groups when WSN works in NE.

We tested the error rates of NE when it is approximated by different theoretic basis, where GA represents the genetic algorithm, IO represents the iterative optimization, and HC represents the hill-climbing, shown in Figure 8. It can be seen that the error rate of NE based on the genetic algorithm is little and acceptable. As well, we can conclude that calculating the approximate NE based on the genetic algorithm is feasible and the NE model guarantees the WSN's reachability.

Figure 8

Error rate of NE based on different theories.

To sum up, the experiment results shown above verify that the model proposed in this paper is feasible and effective to reduce the energy consumption and the WSN's reachability can be guaranteed. However, the proposed method in this paper is just the initial work for prolonging the lifetime of WSNs based on the coalition game model, and the concrete comparisons between our methods with those run in independent style are exactly our current studies and experiments.

7. Conclusions and Future Work

To reduce the energy consumption while guaranteeing the WSN's reachability, we proposed a theoretic energy-efficient model based on the coalition game and Nash equilibrium models. The process of forming the coalition game model is simulated by the Markov process based on the absorbing coefficient. Then, we gave an algorithm to calculate the absorbing coefficient and find the state with the largest absorbing coefficient. For the difficulty of calculating the exact Nash equilibrium, we gave a genetic algorithm to calculate the approximate Nash equilibrium.

The efficiency of Algorithm 1 for calculating the payoff of coalitions is sensitive to the WSN scale, and to improve the simulating algorithm by enlarging the number of the participating nodes is exactly our further work. It is necessary to make in-depth exploration of the feasibility with respect to realistic situations by comparing the performance of our method with that of the existing ones based on cooperative game theory and that of those with independent nodes. At the same time, the efficiency of Algorithm 2 for forming coalitions of WSNs is sensitive to the number of random samples, and to improve the algorithm by considering a more efficient sample approach is our future work as well.