# A Game Theoretic Approach for Balancing Energy Consumption in Clustered Wireless Sensor Networks
## 4 Cluster Head Election Game
### Achieving the Maximum Payoff  
To avoid the case that no sensor nodes choose the strategy \(D\) when playing the \(CEG\), we assume that another chance will be given to all nodes to campaign for the CH when this case occurs for the first time. If still no sensor nodes choose \(D\), a penalty mechanism will be introduced to punish the selfish behavior of nodes. We adopt the mixed strategies for all sensor nodes, that is, any node \(i\) decides whether being the CH based on a probability \(p_{i}\). Then the payoff \(H_{i}\) for node \(i\) when playing the \(CEG\) can be expressed as follows:  
\[ \begin{split} H_{i}=&\ (v_{i}-e_{i})p_{i}+v_{i}(1-p_{i}) \left(1-\prod\limits_{j\
eq i,j\in N_{G}}\left(1-p_{j}\right)\right)+(v_{i}-e _{i})p_{i}\prod\limits_{j\in N_{G}}\left(1-p_{j}\right)\\ +& v_{i}(1-p_{i})\left(1-\prod\limits_{j\
eq i,j\in N _{G}}\left(1-p_{j}\right)\right)\prod\limits_{j\in N_{G}}\left(1-p_{j}\right) -b_{i}\prod\limits_{j\in N_{G}}\left(1-p_{j}\right)^{2}\\ & s.t.\left\{\begin{array}{l}b_{i}\in R,b_{i}>0\\ p_{i}\in R,0\leq p_{i}\leq 1\end{array}\right.\end{split}  \tag{6}\]  
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\); \(N_{G}\) is the set of sensor nodes participated in \(CEG\) and \(b_{i}\) is a positive penalty term inflicted on node \(i\). Equation (6) is a quadratic function depending on probability \(p_{i}\). Letting \(w_{i}\) be the coefficient of the quadratic term, we can express it as follows:  
\[w_{i}=\left(e_{i}-(v_{i}+b_{i})\prod\limits_{j\
eq i,j\in N_{G}}\left(1-p_{j} \right)\right)\prod\limits_{j\
eq i,j\in N_{G}}\left(1-p_{j}\right) \tag{7}\]  
where \(p_{i}\) is the probability of being the CH for node \(j\). Letting \(\Theta=\prod\limits_{i\in N_{G}}\left(1-p_{i}\right)\), then \(w_{i}\) can be simplified to:  
\[w_{i}=\left(e_{i}-(v_{i}+b_{i})\frac{\Theta}{1-p_{i}}\right)\frac{\Theta}{1-p _{i}} \tag{8}\]  
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\); \(b_{i}\) is a positive penalty term inflicted on node \(i\) and \(p_{i}\) is the probability of being a CH for node \(i\). According to the value of coefficient \(w_{i}\), the payoff function \(H_{i}\) may have two forms that are listed as follows:  
* \(H_{i}\) is a concave or linear function when \(w_{i}\geq 0\). Under this case, the maximum point of \(H_{i}\) is either \(p_{i}=0\) or \(p_{i}=1\);
* \(H_{i}\) is a convex function when \(w_{i}<0\). Under this case, the maximum point of \(H_{i}\) maybe exists within the open interval \((0,1)\). As for the first case, each node decides whether being a CH based on the probability \(p_{i}=0\) or \(p_{i}=1\) to maximize its own payoff. Which means pure strategy is adopted by sensor nodes under this case. Since we adopt mixed strategies for all nodes as aforementioned, we only consider the second case so that each node decides whether being a CH according to a probability within the range of \(0\) to \(1\). Then \(\Theta\) is positive and we have the following inequality:\[b_{i}>\frac{1-p_{i}}{\Theta}e_{i}-v_{i} \tag{9}\]  
where \(b_{i}\) is a positive penalty term inflicted on node \(i\); \(p_{i}\) is the probability of being a CH for node \(i\); \(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\) and \(\Theta\) is the multiple formative of probabilities not to be the CH for all sensor nodes. Since \(v_{i}>e_{i}>0\), we find a qualifying value of \(b_{i}\) which can be expressed as follows:  
\[b_{i}=\frac{1-p_{i}}{\Theta}e_{i}-e_{i}\frac{E_{i}}{E_{\max}}>0 \tag{10}\]  
where \(E_{i}\) is residual energy of node \(i\) and \(E_{\max}\) is the maximum residual energy of sensor nodes participated in the \(CEG\).