# Game theory-based Routing for Wireless Sensor Networks: A Comparative Survey
## 3 Game Theory-Based Routing Protocols in WSNs
### Routing Protocols Based on Evolutionary Games
#### 3.3.2 Energy-Efficient Routing Protocol Based on Evolutionary Game (EEREG)  
A WSN consists of more than hundreds, or sometimes even more than thousands, of battery-powered nodes. Increasing the network lifetime of a WSN is of utmost priority and careful attention should be paid to the energy efficiency of the network. It is inevitable in a typical WSN that certain nodes will run out of their energy earlier than the other nodes. In particular, nodes close to the sink nodes die earlier. This problem is known as the hotspot problem. It considerably affects the performance of the network. The performance deteriorates when nodes with low energy tend to become CHs in a clustering-based network. To deal with these problems, [PERSON] et al. designed a mathematical model, aiming to counter the hotspot problem by optimizing the cluster size, using an optimal cluster size (OCS) algorithm. Subsequently, an energy-efficient routing protocol based on evolutionary game (EEREG) theory was presented for terminating anarchism during CH selection [41]. In this routing protocol, a network sector is assumed to be divided into \(k\) annular sections. The sector encompasses an angle \(\theta\) at the center. The sink node is assumed to be at the center of the sector. Each ring has a width of \(d\) and the area of the sector is \(A\). Every node in the network is deployed randomly. The OCS algorithm presented in [41] was quite simple. The sensor nodes in the network periodically send \"hello\" packets to the sink nodes to inform them of their location and energy level. After receiving the \"hello\" packet, the sink node divides the area into \(k\) parts. Next, it calculates the cluster size. Finally, it broadcasts messages to all the sensor nodes to let them know the optimal cluster size. Furthermore, the number of clusters, along with the percentage of the CHs, could be obtained. The sensor nodes in a WSN expend energy while sensing, receiving, and transmitting data. The scheme designed in [41] considered energy expenditure for data transmission only. The energy required to transmit one bit of data from one node to another with a distance \(d\) is \(e_{tx}\), which is represented as:  
\[e_{tx}=E_{elc}+\varepsilon_{amp}.d^{\alpha}, \tag{30}\]  
where \(E_{elc}\) and \(\varepsilon_{amp}\) represent the energy consumption of the transmitter circuit and the transmitter amplifier, respectively, and \(\alpha\) is the propagation loss exponent value, which lies between 2 to 4. In a network area with \(N\) nodes, the CH election game based on evolutionary game theory is formulated as \(G\) (\(P\), \(S\), \(U\)). Here, \(P\) is the set of nodes, \(S\) is the strategy set, and \(U\) is the utility. \(P\) has two subsets: \(H\) and \(L\). \(H\) denotes a set with higher energy level and \(L\) denotes a set with a lower energy level. Usually, the nodes in set \(H\) are supposed to be CHs and broadcast an advertisement packet (\(ADV\)) to other CMs within the transmission range. Typically, the nodes with low energy would also try to send \(ADV\) messages. This is where EGT played an important role in [41], where evolutionary stable strategies hindered such a phenomenon by not allowing nodes with lower energy level to become CHs. To encourage nodes in set \(H\) to become CHs and discourage nodes in set \(L\) from being CHs, a utility function for any node \(i\) was formed as:  
\[u_{i}=r_{i}-p_{i}, \tag{31}\]  
where \(r_{i}\) and \(p_{i}\) denote the profit and penalty of node \(i\), respectively. The routing protocol mainly consists of three components: the optimal cluster size finding, cluster formation, and transmission of data. The first component (optimal cluster size determination) is achieved via the previously explained OCS algorithm. The last component (transmission of data) is the same as the existing clustering algorithms. The main contribution of the paper was in the energy-efficient and controlled cluster selection using game theory. When the energy level is congruent for all the nodes in the cluster, any node could be the CH.