# A Game Theoretic Approach for Balancing Energy Consumption in Clustered Wireless Sensor Networks
## 4 Cluster Head Election Game
### Searching for the Equilibrium Strategy
Here \(P_{-i}^{NE}\) is the strategy combination of sensor nodes in set \(N_{G}\) excepting node \(i\). Hence, the strategy combination \(P^{NE}\) is a NE point of the CEG according to Definition 1. **Proposition 2**. : _The strategy combination \(P^{Z}=\{0,0,\ldots,0\}\) is not a NE point of the CEG._  
Proof. : Letting \({P_{-i}}^{Z}\) be the strategy combination of sensor nodes in set \(N_{G}\) excepting node \(i\), then the payoff of node \(i\) for the strategy combination \(({P_{-i}}^{Z},p_{i})\) can be calculated by:  
\[H_{i}\Big{(}{P_{-i}}^{Z},p_{i}\Big{)}=-\bigg{(}v_{i}-e_{i}\frac{E_{i}}{E_{\rm max }}\bigg{)}(1-p_{i})^{2}+v_{i}-e_{i} \tag{20}\]where \(v_{i}\) is the payoff when node \(i\) chooses the strategy \(ND\) while there exists at least one CH; \(e_{i}\) is the extra cost when node \(i\) chooses \(D\); \(E_{i}\) is residual energy of node \(i\); \(E_{\max}\) is the maximum residual energy of sensor nodes participated in the \(CEG\) and \(p_{i}\) is the probability of being a CH for node \(i\). \(\square\)  
Equation (20) shows that node \(i\) has incentives to enhance its own payoff by deviating from the strategy \(p_{i}=0\), that is \(P^{Z}\) is not a NE point according to Definition 1. Based on the above two propositions, we can conclude that there is at least one node that has a positive probability to be CH at the NE point \(P^{NE}\) which is given by Equation (15). In addition, the value of \(\Theta\) at this NE point is within the range (0, 1) according to Equations (13) and (14). However, how to calculate the probability of being a CH for each sensor node at the NE point of \(CEG\) still presents great challenges. We can first calculate the value of \(\Theta\) at the NE point, expressed as \(\Theta^{NE}\). And then we can calculate the probability to be CH at the NE point for each node based on Equations (13) and (14). For the purpose of searching the root of \(\Theta^{NE}\), we can employ a binary search algorithm or [PERSON]'s method to solve the following optimization problem:  
\[\min f(\Theta)=\left|\Theta-\prod_{i\in N_{G}}(1-p_{i}^{m}(\Theta))\right|,s.t.\Theta\in R,0<\Theta<1 \tag{21}\]  
where \(p_{i}^{m}\) is the optimal probability of being a CH for node \(i\) that can maximize its own payoff; \(\Theta\) is the multiple formative of probabilities not to be the CH for all sensor nodes and \(N_{G}\) is the set of sensor nodes that participated in the \(CEG\). Since the binary search method has lower complexity and higher convergence speed than [PERSON]'s method, it is more suitable for sensor nodes which have limited computation abilities. The details of the binary search method are as follows:  
* First step: Input the minimum value of \(\Theta\) (we denote it as \(min\)), the maximum value of \(\Theta\) (we denote it as \(max\)) and error precision \(err\);
* Second step: Calculate the expression \((min+max)/2\), and assign the result to \(\Theta\);
* Third step: If \(\mid max-min\mid<err\), or \(f^{\prime}(\Theta)<err\), terminate the iteration process and output the final result of \(\Theta\), which is denoted as \(\Theta^{NE}\); Otherwise, go to the next step;
* Forth step: If \(f(\Theta)f^{\prime}(min)>0\), assign the value of \(\Theta\) to \(min\); Otherwise, assign the value of \(\Theta\) to \(max\);
* Last step: Go to the second step to continue the iteration process until the maximal number of iterations is completed. During the above iteration process, the initial value of \(min\) is set to be 0.001, the initial value of \(max\) is 0.999, the value of \(err\) is 0.005 and the maximal number of iteration is 20. Finally, we give an example of the NE solution \(P^{NE}\) for our \(CEG\) as shown in Table 1. Here we only list the result for a \(CEG\) which contains in total 8 sensor nodes. These nodes are distributed in the same local area of the network and act as players to join in the same \(CEG\). Moreover, they hold different values about the distance to BS, number of neighbor nodes and residual energy.