# Improved Proactive Routing Protocol Considering Node Density Using Game Theory in Dense Networks
## 3 Materials and Methods
### OLSR Improvement Selection
#### 3.2.1 Game Mathematical Model  
In this section, we propose describing the ad-hoc network using the game theory approach [18]. It is represented as:  
\[G=[N,\;\;S,\;\;U] \tag{1}\]  
where N is the set of nodes in the network, S is the strategy set and U is the utility function. Table 3 shows the similarity between a game and a wireless ad-hoc network.  
In this network, each node will receive the utility function and then evaluate a particular outcome depending on its strategy. All nodes aim to maximize or minimize the utility function. The utility function of the \(i\)th node is shown in Equation (2).  
\[U_{i}=\left\{\begin{array}{cc}G-f(c_{i});&\;\;if\;S_{i}=\textit{willingness\_always}\\ 0&\;\;if\;S_{i}=\textit{willingness\_never}\end{array}\right\} \tag{2}\]  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Degree of Willingness** & **Value** \\ \hline WILL\_NEVER & 0 \\ WILL\_LOW & 1 \\ WILL\_DEFAULT & 3 \\ WILL\_HIGH & 6 \\ WILL\_ALWAYS & 7 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Willingness and its values [8].  
Figure 1: HELLO message packet format in an OLSR network [8].  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Elements of a Game** & **Elements of the Wireless Ad-Hoc Network** \\ \hline Players & Node in the network \\  & We consider two strategies: \\ Strategy & _i.__willingness\_always_ \\  & _ii.__willingness\_never_ \\ Utility function & The node count after an elapsed period \\ \hline \hline \end{tabular}
\end{table}
Table 3: The duality of game and wireless ad-hoc network.  
where G is the gain received by nodes that the terminal count is above a certain threshold and f (c) is the cost function paid by node \(i\) which changes its willingness value. The cost function is assumed to be constant for all nodes in the network. Then, the utility matrix for any node is illustrated in Table 4.  
We use the mixed strategy of the Nash equilibrium [19]. If the probability of a player to choose _willingness_always_ is \(p\), then the probability to choose will_never is 1-\(p\). The probability of a player to choose _willingness_always_ will be  
\[p=1-\left(\frac{c}{G}\right)^{\frac{1}{N-1}} \tag{3}\]  
The probability is valid for the mixed strategy of the Nash equilibrium. The probability \(p\) depends on N, c and G. As N and c are constant, then \(p\) depends on G. The gain is dependent on the speed of the node at time \(t\) and the movement probability, which is based on the Random Waypoint model. The utility function is dependent on the number of nodes after an elapsed time. The maximum number of one-hop neighbours is set to be the threshold, T. This threshold value is the number of HELLO messages received from a node's one-hop neighbours which we call _node_density_. The threshold is set at a value of 0.25 of the total nodes in the network. This value was achieved after a series of iteration [20]. Each node will compare its value to the threshold and choose its strategy as follows:  
\[\begin{array}{l}\text{if }node\_density\geq\text{T then }\text{\emph{willingness }always}\text{ or }node\_density\text{ }<\text{T then }\\ \text{\emph{willingness\_never}}\end{array}\]  
In this paper, we consider a non-cooperative game where the players maximize the payoff and choose the best strategy individually and rationally.