# 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.3 Game Theory-Based Energy-Efficient Clustering (GEEC)
The average revenue of nodes in class \(M\) thus was formulated as:  
\[\overline{U_{M}}=x(a+2\Delta-2y\Delta)+(1-x)(ya-\Delta). \tag{35}\]  
After stringent mathematical analysis, the replicator dynamic equation of class \(M\) nodes was formulated as:  
\[\frac{dx}{dt}=F(x)=x\big{(}U_{M-CH}-\overline{U_{M}}\big{)}. \tag{36}\]  
Like the nodes in class \(M\), the expected utility functions of class \(L\) nodes for two different strategies were determined by the following two expressions:  
\[U_{L-CH}=xb+(1-x)(b+\Delta), \tag{37}\]\[U_{L-CM}=x(b+2\Delta)+(1-x)(-\Delta), \tag{38}\]  
where \(b\) is the cost for \(L\) nodes becoming the CH. The average revenue for nodes falling under class \(L\) was:  
\[\overline{U_{L}}=y(b+\Delta-x\Delta)+(1-y)(bx+3x\Delta-\Delta). \tag{39}\]  
The replicator dynamic equation for nodes in class \(L\) was formulated as:  
\[\frac{dy}{dt}=G(y)=y\Big{(}U_{L-CH}-\overline{U_{L}}\Big{)}. \tag{40}\]  
The routing protocol was designed to have three phases: the initial, cluster formation, and data transmission phases. In the initial phase, all the nodes in a WSN transmit an initial message to the sink node, containing the information of node identity (ID) and residual energy \(E_{res}\). After this initial transmission of messages by the sensor nodes, the sink node sorts them based on the \(E_{res}\) value. It also generates an energy threshold value, \(E_{th}\). The sensor nodes, after determining the \(E_{th}\) value, classify themselves as either class \(M\) (class of nodes with more energy than the threshold) or class \(L\) nodes (class of nodes with less energy than the threshold). In the cluster formation phase, the nodes decide to become either the CH or the CM, based on the pay-off functions. When a node decides to become the CH, it sends out \(ADV\) messages that contain its ID and \(E_{res}\). The nodes that do not become CHs reply to the CHs by transmitting a join request. There can be a rare case when a node may not receive an \(ADV\) message. In that case, it would directly transmit data to the sink node. In the data transmission phase, all the CHs divide the time slots and announce them to the CMs. The CMs send the data to the CHs using TDMA and the cluster structure is maintained for a certain time. The CHs finally transmit the data to the sink. GEEC outsmarts LEACH and LEACH-Centralized (LEACH-C) in terms of network lifetime. Four parameters were introduced to compare the network lifetime with the LEACH protocol. They were: (1) the time taken for the first node to exhaust its energy, (2) the time taken for the first node to die, (3) the time taken for all the nodes to run out of energy, and (4) the number of nodes alive during simulation. These parameters were considered in the simulation study in [42]. In all cases, GEEC was identified to perform better. Technical strengths:  
* Introduces rationality to the low energy nodes;
* Pay-offs were considered differently for nodes with higher and lower energy levels. Technical weaknesses:
* Some nodes may not receive advertisement from the CHs resulting in clusters with one node that directly transmits to the sink node. Applications:
* Any kind of energy-efficient target tracking and environment monitoring. Possible future improvements:
* Energy threshold determination procedure can be elaborated for the betterment of the protocol.