# Game theory-based Routing for Wireless Sensor Networks: A Comparative Survey
## 3 Game Theory-Based Routing Protocols in WSNs
### Routing Protocols Based on Cooperative Games
#### 3.1.3 Reliable Coalition Formation Routing (RCFR) for WSNs  
Reliable data delivery is challenging in WSNs. The routing protocol designed in [35] focused on this problem and ensured cooperation among nodes for reliable data delivery at a minimum routing cost. First, a coalitional game model was designed with a characteristic function based on performance metrics like packet forwarding rate and remaining energy. Subsequently, an algorithm with good convergence speed was designed to form coalition partitions in the game. Based on the coalitional game model, the authors finally designed a reliable coalition formation routing (RCFR) protocol that determines an appropriate route in the network on the basis of the lowest cost principle. The authors in [35] considered the sensor nodes in WSNs as playing a coalitional game. A characteristic function was defined, along with the establishment of the pay-off allocation method among the coalition members. The coalitional game model was formulated as \(\Gamma=<\)_A_, _U_\(>\), where _A_= {_a_\({}_{1}\), _a_\({}_{2}\),..., _a_\({}_{n}\)} is a set of players that interact with each other and form groups that cooperate in routing. \(U\) is the characteristic function. The strategy set consisted of two strategies. Assuming that the strategy set is \(\Gamma_{a_{i}}\)= {_join_, _not join_}, it referred to the strategies that a node may or may not join a certain coalition. A coalition set in [35] was denoted by \(S\), where _S_\(\subseteq\)_A_. The designed game had a frame work where it was assumed that time was divided into several slots. It was denoted by \(t_{K}\) (K = 0, 1, 2, 3.....). The characteristic function of coalition \(S\) at a time slot \(t_{K}\) was presented as:  
\[U\Big{(}S^{t_{K}}\Big{)}=\lambda|S|-f_{S}(PFR_{i},RCR_{i},RER_{i}), \tag{6}\]  
where \(\lambda\in(0,1]\) was used for adjustment, \(|S|\) represented the number of members in the coalition \(S\), and \(f_{S}\) was the function for calculating the cost. Then, \(PFR_{i},RCR_{i},\text{ and }RER_{i}\) presented the rate of packet forwarding, the rate of correctly reporting an event, and the rate of remaining energy for any node \(i\), respectively. The pay-off function for any coalition member \(a_{i}\in S\) at a time slot \(t_{K}\) was calculated as:  
\[\phi_{a_{i}}\Big{(}S^{t_{K}}\Big{)}=\frac{U\Big{(}S^{t_{K}}\Big{)}}{|S^{t_{K}}|}. \tag{7}\]  
In coalitional game theory, forming appropriate coalitions is crucial. Nodes with common interest form coalitions and perform reliable data delivery as groups. Starting from a certain time slot, the nodes conduct a normal routing and forwarding process. They also collect historical records of the performance of the nodes. At the end of certain time slots, the performance metrics are updated, and the characteristic function computed. For all the coalitions S (S \(\subset\) A), with a source and destination node, the coalition formation is performed. The following parameters are assumed in RCFR: the players (sensor nodes), \(A\) = \(\{a_{1}\), \(a_{2}\),..., \(a_{n}\}\); computed characteristic function = \(U\Big{(}S^{t_{K}}\Big{)}\); coalition partition, \(\theta^{*}=S^{r}_{1}\), \(S^{r}_{2}\),..., \(S^{r}_{k}\); strategy space, \(\Gamma=\Gamma_{1}\times\ldots\times\Gamma_{n}\); and routes from source to destination, \(R\)= \(\{r_{1}\), \(r_{2}\),..., \(r_{k}\}\). For each node \(a_{i}\) from set \(A\) and each route \(r_{i}\) from set \(R\), the pay-off could be calculated using (6). The node \(a_{i}\) joins a coalition that has a maximum pay-off using the _join_ strategy. The designed coalitional game model was merged with the ad hoc on-demand distance vector (AODV) routing protocol [55] to integrate a fully functional routing protocol.