## 4 Game Clustering Model
### Profit and Loss Analysis  
#### 4.2.1 Profit Model  
1. Invulnerability based on the number of shortest paths  
**Definition 1**. : _For a network with \(N\) nodes, if there are \(u_{0}(k_{min})\) shortest paths with the number of hops equaled \(k_{min}\) between node \(i\) and node \(j\), then the number of equivalent shortest paths between node \(i\) and node \(j\) is expressed as \(em_{ij}\), which can be computed by Equation (2)._  
\[\left\{ \begin{array}{l}u_{0}(k_{min})=\frac{(N-2)!}{(N-k_{min}-1)!}\\ u_{1}(k_{min})=\sum\limits_{t=1}^{k_{min}}\frac{(N-2)!}{(N-1)!}\\ em_{ij}=\frac{u_{0}(k_{min})}{u_{1}(k_{min})}\end{array} \right. \tag{2}\]  
where the number of hops \(k_{min}\leq N-1\), \(u_{1}(k_{min})\) refers to the number of paths in which the number of hops between nodes is less than \(k_{min}\) in the corresponding \(N\)-node fully-connected network, and \(t\) indicates an integer variable. Obviously, \(em_{ij}\in\) (0,1), in the condition that there is a direct edge between two nodes, \(em_{ij}\) is equal to 1. For any node \(i\) and node \(j\), if \(em_{ij}\) is equivalent to 1, the network is regarded as fully connected. The invulnerability of each cluster in the network is equal to the equivalent shortest path number of the cluster and is denoted as follows  
\[inv=\frac{\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}em_{ij}}{N(N-1)/2} \tag{3}\]  
where \(N\) signifies the number of nodes in a cluster, \(\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}em_{ij}\) is the sum of the number of equivalent shortest paths in the entire cluster, and \(N(N-1)/2\) is the number of node-to-node connections that can be established. For an incompletely connected network, the equivalent shortest path number \(inv\in\) (0,1), it can be easily noticed that the larger the \(inv\), the more compact the cluster structure and the more potent the invulnerability. **Definition 2**. : _For a network composed of \(\omega\) clusters, the invulnerability of the network can be measured by the weighted sum of the invulnerability per cluster. The invulnerability indicator of the network INV can be calculated as follows_  
\[INV=\sum_{m=1}^{\omega}\frac{N_{m}}{N}inv_{m} \tag{4}\]  
_where \(N_{m}\) is the number of nodes in the \(m\)th cluster, \(N\) is the number of nodes in the whole network, and \(inv_{m}\) is the invulnerability of the \(m\)th cluster._ \begin{table}
\begin{tabular}{c c c} \hline \hline
**Strategy** & \(D\) & \(ND\) \\ \hline \(D\) & \(V(i)-C_{CH}(i)\),\(V(i)-C_{CH}(i)\) & \(V(i)-C_{CH}(i)\),\(V(i)-C_{CM}(i)\) \\ \(ND\) & \(V(i)-C_{CM}(i)\),\(V(i)-C_{CH}(i)\) & 0,0 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Profit matrix. 2. Invulnerability based on connectivity The invulnerability measurement based on effectively connected clusters is defined as follows \[C=\frac{1}{\omega\sum_{m=1}^{\omega}\frac{N_{m}}{N}\delta_{m}l_{m}}\] (5) where \(\omega\) represents the number of the clusters in the network, \(N_{m}\) means the number of nodes in the \(m\)th cluster, \(N\) is the total number of nodes in the network, and \(l_{m}\) is the average length of the shortest path between any nodes in the \(m\)th cluster. \[\delta_{m}=\left\{ \begin{array}{ll}1&\text{Nodes of $N_{m}$ at least has one link with BS}\\ 0&\text{None of the nodes of $N_{m}$ has link with BS}\end{array} \right.\] (6)  
The invulnerability based on the number of shortest paths focuses on the survivability of the local network. On the other hand, the invulnerability based on connectivity is biased towards the destruction-resistant of the whole network. Thus, by combining the two indicators, the network invulnerability in the case that node \(i\) is elected as CH can be expressed as follows  
\[B_{i}=\lambda\times INV+(1-\lambda)\times C\,\ 0\leq\lambda\leq 1,\ 1\leq i\leq N \tag{7}\]  
In the study, the utility function of the game model is described as the quadratic function of the network invulnerability \(B(i)\) and the residual energy of the node \(E(i)\), then the utility function in the game model of CH selection is defined as  
\[\left\{