Cooperative packet-forwarding strategies in mobile ad hoc networks with unreliable channels: An evolutionary game approach

Abstract

In mobile ad hoc networks, network nodes accomplish a target task usually by cooperative packet forwarding from the source to the destination. It is a challenge to enforce their mutual cooperation for a node’s self-interest. In this article, we focus on cooperative packet forwarding in a one-hop unreliable channel, which leads to packet loss and retransmission. We model the process of packet forwarding with the nodes’ remaining energy and reputation value. We propose a packet-forwarding non-cooperative game model reflecting the utilities of different packet-forwarding strategies, in which an incentive mechanism is introduced to enforce cooperation of packet forwarding. Furthermore, we analyze the packet-forwarding game with replicator dynamics and derive and prove three theorems. If the conditions of the theorems are met, the evolutionarily stable strategies can be attained. Three inferences also reveal how convergence speed to evolutionarily stable states is affected by the cooperative incentive, the probability of successful packet transmissions, and the upper limit of the retransmission number. The simulation results support the proposed theorems and inferences. In addition, we show that our game model with a reputation value and the mechanism of incentive cooperation can improve the probability of successful packet transmissions, and reduce the network overhead.

Introduction

Mobile ad hoc networks (MANETs) are composed of multiple interacting nodes which have limited energy and self-organization ability. MANETs are generally used in the fields of military communications, rescue and disaster relief, and exploration in remote areas, and so on, and they have high flexibility, safety, and mobility. To achieve a common goal, MANETs require a collection of interacting nodes to self-organize into a network and to cooperate with one another, ensuring an operable communication. Among all cooperative behaviors, packet forwarding enlarges the data-transmission range beyond one-hop networks. However, the nodes usually have limited resources and selfish behaviors. When packet forwarding may pay certain costs, a rational node with selfish behaviors may be unwilling to forward packets according to its own benefit, which will damage the network communication performance.^1,2 Therefore, it is crucial to consider the mechanisms of packet forwarding among the nodes. The mechanism can encourage packet forwarding with a high probability of successful transmissions with unreliable channels and can reduce the energy consumption of the nodes and extend the MANETs’ life time.

Game theory is a widely adopted mathematical tool to study and analyze the strategic interactions among individual decision makers in decentralized networks, and it has been widely used in the field of wireless network communication. An evolution game takes the changing trends of the overall population as the research object, where the nodes of the MANETs are viewed as individuals, and all of the nodes in the MANETs are an overall population. After the continuous evolution of a population, a route-management system guides the individual nodes to make a decision about whether or not to forward a packet to maximize their utilities after observing other nodes’ strategies and the rate of individuals who select the strategy that has a higher gain will increase. Conversely, the rate of individuals who select the strategy that has a lower gain will correspondingly decrease. Thus, the rate of individuals who select their corresponding strategies remains a stable point, at which no individual nodes will change its forwarding strategy unilaterally.

In this article, fully considering the packet loss and retransmissions of the individual nodes, we study the problem of packet forwarding among one-hop nodes in unreliable channels. Since random noise affects the channels, we can think mobile nodes are bounded rational and aim at maximizing their own profit. As packet forwarding by nodes will produce certain costs, each node decides whether or not to forward a packet according to its own profit. Hence, the packet forwarding of nodes with selfish behaviors can be described as a game. Considering individual nodes’ bounded rational and the individual decision-making process of the individual nodes, we study the problem of packet forwarding among nodes by an evolutionary game which is more suitable for dealing with the decision-making problem of bounded rational individual participants. Therefore, it is very important for us to study the game model of packet forwarding of MANETs by evolutionary game theory.

The nodes have two strategies: Forward (F) or Discard (D). We focus on the one-hop packet-forwarding model in order to encourage selfish nodes to behave cooperatively. A selfish node will only send its own packets without forwarding others’ packets.

Over the past years, one of the most promising ways to encourage cooperation of autonomous nodes in MANETs is to use incentive mechanisms. The incentive mechanisms can be divided into two categories: credit-based ^3–6 and reputation-based^7–9 systems. Most credit-based mechanisms adopt virtual credits to reward nodes participating in packet forwarding. Seregina et al. ¹⁰ proposed a credit-based incentive mechanism for encouraging nodes to forward packets in two-hop delay tolerant networks. For reputation-based systems, a node’s reputation is evaluated by its neighbors, based on the node’s behavior. Using a reputation table, each node can distinguish misbehaving nodes from cooperative nodes. Almazyad ⁸ evaluated a node reputation by applying the hybrid method to choose the most reliable route, and this hybrid method can make data packets more likely to be delivered successfully to the intended destination in a hostile environment.

Many cooperative strategies have been studied, such as repeated games,^11,12 no-cooperation games,^13–16 stochastic games, ¹⁷ bargaining games, ¹⁸ and evolutionary games.^19–25 In wireless networks, Zhu et al. ¹¹ proposed an adaptive repeated game to ensure packet forwarding among nodes, and then they proposed a self-learning algorithm to increase the cooperation probabilities. Xu et al. ¹⁴ proposed a win-stay, lose-likely-shift (WSLLS) approach for stimulating cooperation of selfish nodes in a prisoner’s dilemma (PD) game, and a utility-based function was applied to evaluate a player’s (i.e. node) performance for a game. Akkarajitsakul et al. ¹⁸ proposed a bargaining game model to encourage cooperative packet forwarding based on a coalition formation among mobile nodes. With the approach, they found the most suitable probabilities in which the mobile nodes would help each other.

Among these methods of evolutionary game theory, some incentive mechanisms were proposed to encourage a node’s cooperative packet forwarding. Based on the trust incentive cooperation among sensor nodes, Li et al. ¹⁹ considered retransmission of packet loss and introduced a strategy-adjustment mechanism into the process of the evolutionary game. This mechanism of strategy adjustment can compensate for reflecting the requirements of individual strategy adjustments in a replicator dynamic model. Al-Jaoufi et al. ²¹ proposed a new model for a selfish node incentive mechanism with a forward game node for wireless sensor networks (WSNs) based on evolutionary game theory. They also analyzed evolutionary trends of trust relationships among nodes. The results of the simulations indicate that a WSN that uses an incentive mechanism can forward packets well while resisting any slight variations. Chen et al. ²² proposed a suitable dynamic incentive mechanism based on evolutionary game theory in WSNs, which highlights the nodes adjust strategies forwardly and passively and encourages the selfish nodes to cooperate with each other.

Some researchers studied packet forwarding based on evolutionary game theory in unreliable scenarios. Considering the packet loss in noisy channels, Tang et al. ²³ studied cooperative packet forwarding in a one-hop unreliable channel. They proposed an indirect reciprocity framework based on evolutionary game theory and enforced packet-forwarding strategies in MANETs. They then analyzed evolutionary dynamics of cooperative strategies and figured out the threshold of cost-to-benefit ratio to ensure the cooperation among nodes. However, they did not consider the impact of the incentive cooperation mechanism of nodes and set the upper limit of the retransmission number. Feng et al. ²⁴ proposed an incentive compatible multiple-copy packet forwarding (ICMPF) protocol to reduce the delivery overhead and to ensure a successful packet delivery in mobile social networks (MSNs). Furthermore, they built an evolutionary game model to encourage the forwarding behavior among nodes. At last, they proved that the strategy dynamics attained the evolutionarily stable strategy (ESS). However, they did not consider saving the nodes’ energy and set the upper limit of the retransmission number. Wang et al. ²⁵ provided a non-cooperative game model to enforce cooperation in noise channels and proposed a one-hop information exchange and built a packet-forwarding game model. A state machine-based strategy was proposed to reach Nash equilibrium, which is proved to be a continuous state with carefully designed system parameters. However, they did not consider the incentive cooperation mechanism and set the upper limit of the retransmission number.

Compared with few previous studies,^23–25 our work is different from the type of factors in the game and the process of the dynamics. Our ideas derive partly from the cooperation strategy model; ²³ however, considering the packet loss and retransmission and the incentive cooperation mechanism of nodes, we build a different packet-forwarding game model and introduce a different process of game evolution. In sum, we obtain different theorems and inferences compared to a previous study. ²³ Furthermore, for saving node energy, we set the upper limit of the retransmission number in MANETs, while Feng et al. ²⁴ and Wang et al. ²⁵ did not consider the problem of saving node energy. Overall, our work is different from the related aforementioned studies.

In MANETs, the characteristics of mobile nodes determine that their energy is limited, so the design of routing protocols needs to consider reducing the energy consumption to prolong the network life. Among these energy-efficient algorithms,^26–31 Zhou et al. ²⁹ proposed a systematic solution for content delivery over ultra-dense networks by integrating collaboration with intelligence. In particular, a collaborative video-scheduling scheme is developed to maximize the video quality as well as the energy efficiency and spectrum efficiency. Zhou et al. ³⁰ analyzed the relationship between the data processing and the energy consumption by investigating the content correlation of the captured data. By exploring the relationship among the coding, storage, and transmission, Zhou et al. ³¹ proposed an energy-efficient content-delivery system via a device-to-device communications for smart cities. Compared with few previous studies,^29–31 our work is distinguishable in energy-saving ways. By transmitting data packets to the routing nodes with high-reputation value, we increase channel stability, reduce the packet loss rate, and reduce the energy consumption. In addition, considering the packet loss and retransmission, we set a variable upper limit of the retransmission number according to the communication environment in order to save node energy. However, Zhou et al.^29,31 proposed a systematic solution for content delivery to save energy. Zhou et al. ³⁰ studied the energy efficiency by analyzing the relationship between the data processing and the energy consumption.

Our work is distinct from the aforementioned works in three ways. First, we model a packet-forwarding interaction process considering both packet loss and retransmission, and the reputation value of the nodes in unreliable channels. Second, we propose an incentive mechanism based on nodes’ reputation value to enforce cooperation. Third, we calculate the energy consumption of packet retransmission and introduce it into the game model.

The main contributions of this article are as follows:

1. We model a one-hop packet-forwarding interaction process considering both packet loss and retransmission and the reputation value of nodes with unreliable channels and calculate the energy consumption of packet retransmission.

2. We build a packet-forwarding game model by introducing the incentive mechanism to enforce cooperation among nodes. After analyzing the game model with replicator dynamics, we derive and prove the theorems indicating that ESSs can be attained. Inferences also reveal that the rate of convergence to evolutionarily stable states is affected by the cooperation incentive, the probability of successful packet transmissions, and the upper limit of the retransmission number.

3. The simulation experiments verify the theorems and inferences and prove that our model can improve the probability of successful packet transmissions, and reduce the network overhead.

The article is organized as follows: in section “Introduction,” we introduce the purpose of the research and the related work. In section “Packet-forwarding game model with unreliable channels,” we build a packet-forwarding game model reflecting utilities of different game strategies with the upper limit of the retransmission number N. In section “Evolutionary game theory–based packet forwarding,” we analyze the packet-forwarding game with replicator dynamic and obtain three theorems and three inferences. In section “Simulation experiments,” the simulation results are provided. Finally, section “Conclusion” offers conclusions.

Packet-forwarding game model with unreliable channels

Packet-forwarding strategies

For a MANET, a large number of self-organized nodes cooperate with each other to accomplish a certain task. Communication relies on packet forwarding of other relay nodes that forward packets for the providers to the destination. Because of forwarding a packet with certain costs, a relay node has two strategies to select from to maximize itself profit: Forward (F) and Discard (D). In general, if a node selects the Forward strategy, this will help the other nodes to forward packets and obtain gain and, in turn, improve its reputation value. On the contrary, if a node selects the Discard strategy, it will drop the other nodes’ packets, but the node may obtain a little gain for saving its energy. In this case, the other nodes will suffer a loss due to the discard. The notations are described in Table 1.

Table 1.

Notations in this paper.

Notations	Physical Meanings
$R_T$	Gain obtained by a node selecting the Forward strategy which also helps other nodes successfully forward a packet.
$R_D$	Gain obtained by a node selecting the Discard strategy, the node drops a provider‖s packet to save energy.
$R_C$	Cooperation gain of a node due to the next-hop relay selecting the Forward strategy and successful forwarding a packet.
$C$	Cost produced by forwarding a packet or sending a packet
$L$	Uncooperative loss of a node due to the next-hop relay selecting the Discard strategy
$\gamma T$	The incentive for cooperation, where $T$ is the reputation value of a node, $\gamma$ is an adjustment factor, and $\gamma T\ge 0$

The process of packet forwarding

At each time slot, a few nodes chosen from the population will form pairs to forward packets. ³² Within each pair, one node may act as a service provider or a relay as shown in Figure 1.

Figure 1.

Two nodes’ packet-forwarding model.

For Figure 1, when the provider forwards a packet to the relay, the relay receives the packet and returns a one-hop 1-ACK (acknowledgment character) to confirm that the provider has transmitted a packet successfully. When the retransmission timer expires, the provider has not received the one-hop 1-ACK of the packet that had once been forwarded, and it will transmit it again. After successfully receiving a packet, the relay will forward or discard a packet according to its remaining energy and the provider’s reputation value. Furthermore, after successfully receiving a packet from the relay, the receiver will actively send a two-hop 2-ACK to the provider to indicate that the relay has successfully forwarded its packet. The detailed process of packet retransmission within a pair of nodes is shown in Figure 2.

Figure 2.

The process of packets retransmission.

In Figure 2, the number N is the upper limit of the retransmission number. In wireless networks, data packets are easily lost due to the instability of wireless channels. In order to ensure the reliability of data transmission, the nodes need to retransmit the lost data packets, which will increase the energy consumption of the nodes and affect the network life. Therefore, setting the upper limit of the retransmission number of packets can reduce the energy consumption of nodes for packets retransmission, and ensure the recovery of lost packets in the wireless network. In this article, N changes constantly with the network channel environment.

In Table 2, $E_C$ represents the remaining energy of the node. When the remaining energy is limited, the node will reject to forward the other nodes’ packets due to insufficient energy. $T_{\mathrm{AB}}$ represents the reputation value of node B in node A’s reputation table.

Table 2.

The reputation matrix of a node.

	Node A	Node B	Node D	… …
Node A	$E_C$	$T_{\mathrm{AB}}$	$T_{\mathrm{AD}}$
Node B	$T_{\mathrm{BA}}$	$E_C$	$T_{\mathrm{BD}}$
Node D	$T_{\mathrm{DA}}$	$T_{\mathrm{DB}}$	$E_C$
… …

Energy consumption of packet retransmission

We assume that any node has the same probability $(q)$ of successful packet transmission at any one time with an unreliable channel. The successful transmission probability within the upper limit $N$ is $\theta =1-(1-q{)}^N$ . Within one interaction, the cost of a packet transmission failure $(E_F)$ is $\mathrm{NC}$ . The cost of a packet transmission success is $E_S$ , and $k$ is the number of retransmissions. $E_S$ is derived as follows

$$\begin{array}{cc}\multicolumn{1}{c}{E_S}& =\sum _{k=1}^N\mathrm{kC}\times P\{x=k|x\le N\}\hfill \\ \multicolumn{1}{c}{}& =\frac{\mathrm{qC}}{1-{(1-q)}^N}\sum _{k=1}^{N}k(1-q{)}^{k-1}\hfill \end{array}$$

(1)

where

$$P\{x=k|x\le N\}=\frac{P\{x=k,x\le N\}}{p\{x\le N\}}=\frac{{(1-q)}^{k-1}q}{1-{(1-q)}^N}$$

(2)

Substituting $\theta =1-(1-q{)}^N$ into $E_S$ and we get

$$E_S=\frac{\theta -\mathrm{Nq}+\mathrm{Nq}\theta }{q\theta }C$$

(3)

Packet-forwarding game model

When nodes transmit packets in MANETs with unreliable channels, data packet forwarding will consume the energy of nodes. We assume that the nodes are selfish and rational, and due to their limited energy, they will select Forward strategy or Discard strategy depending on which strategy can maximize gain. Each node will make a decision to select the best strategy between Forward and Discard strategy according to different gains of strategies. The three kinds of different situations on transmitting packet strategies are discussed as follows.

The probability of each event occurs, and the gains of the nodes are shown in Tables 3–5. In Tables 3–5, the symbol $P$ indicates the probability that each event occurs, and 0 and 1 means failure and success, respectively.

Table 3.

Payoffs of both interactive nodes selecting the Forward strategy.

Number	A forward/send	B forward/send	Probability $P$	A profit G(A)	B profit G(B)
1	1	1	${\theta }^2$	$R_T+R_C+\gamma T-2E_S$	$R_T+R_C+\gamma T-2E_S$
2	1	0	$\theta (1-\theta )$	$R_T+\gamma T-2E_S$	$R_C+\gamma T-2E_F$
3	0	1	$\theta (1-\theta )$	$R_C+\gamma T-2E_F$	$R_T+\gamma T-2E_S$
4	0	0	$(1-\theta {)}^2$	$W-2E_F$	$W-2E_F$

Table 4.

Payoffs of only one node selecting the Forward strategy.

Number	A forward/send	B send	Probability $P$	A profit G(A)	B profit G(B)
1	1	1	${\theta }^2$	$R_T+\gamma T-2E_S-2L$	$R_C-E_S+R_D$
2	1	0	$\theta (1-\theta )$	$R_T+\gamma T-2E_S-2L$	$R_C-E_F+R_D$
3	0	1	$\theta (1-\theta )$	$W-2E_F-2L$	$-E_S+R_D$
4	0	0	$(1-\theta {)}^2$	$W-2E_F-2L$	$-E_F+R_D$

Table 5.

Payoffs of both nodes selecting the Discard strategy.

Number	A send	B send	Probability $P$	A profit G(A)	B profit G(B)
1	1	1	${\theta }^2$	$-L-E_S+R_D$	$-L-E_S+R_D$
2	1	0	$\theta (1-\theta )$	$-L-E_S+R_D$	$-L-E_F+R_D$
3	0	1	$\theta (1-\theta )$	$-L-E_F+R_D$	$-L-E_S+R_D$
4	0	0	$(1-\theta {)}^2$	$-L-E_F+R_D$	$-L-E_F+R_D$

Both nodes select the Forward strategy

When two nodes A and B select the Forward strategy, each node has two actions: forward and send.

One node selects the Forward strategy

When one node A selects the Forward strategy, the node A has two actions: forward and send, while node B only has one action: send. Here, the rational node with selfish behavior is to send only its own without forwarding others’ packets.

Both nodes select the Discard strategy

When both nodes A and B select Discard strategy, each node only has one action: send.

In summary, the total expected payoff for each node is the sum of each probability multiplied by its corresponding payoff. ¹⁹ When both nodes A and B select the Forward strategy, the total payoffs are equal for nodes A and B, which is

$$\begin{array}{c}\sum _{i=0}^4{P}_i{G}_i(A)=\sum _{i=0}^4{P}_i{G}_i(B)\hfill \\ =\theta R_T+\theta R_C-2(1-\theta )E_F-2\theta E_S+\gamma T\hfill \end{array}$$

(4)

When only one node selects the Forward strategy, the total payoff of node A selecting the Forward strategy is

$$\sum _{i=0}^4{P}_i{G}_i(A)=\theta R_T-2(1-\theta )E_F-2\theta E_S+\gamma T-2L$$

(5)

The total payoff of node B selecting the Discard strategy is

$$\sum _{i=0}^4{P}_i{G}_i(B)=\theta R_T-(1-\theta )E_F-\theta E_S+R_D$$

(6)

When both nodes A and B select the Discard strategy, the total payoffs are equal for nodes A and B, which is

$$\sum _{i=0}^4{P}_i{G}_i(A)=\sum _{i=0}^4{P}_i{G}_i(B)=-(1-\theta )E_F-\theta E_S-L+R_D$$

(7)

here $i$ is a positive integer.

Definition 1

A packet-forwarding game in a MANET with an unreliable channel is a 3-tuple $\mathrm{\Gamma }(\mathrm{\Psi },\mathrm{\Omega },U)$ where:

1. Ψ is a population comprised of a large number of players;

2. Ω is a set of strategies from which a player can select. Here, $\mathrm{\Omega }=\{{\omega }_1,{\omega }_2\}=\{\mathrm{Forward},\mathrm{Discard}\}$ ;

3. U presents the payoffs matrix which is shown in Table 6. The payoffs matrix is formed from the payoffs of the game between the participating players.

Table 6.

Payoffs matrix.

	Forward	Discard
Forward	$\theta R_T+\theta R_C-2(1-\theta )E_F-2\theta E_S+\gamma T$	$\theta R_T-2(1-\theta )E_F-2\theta E_S+\gamma T-2L$
Discard	$\theta R_T-(1-\theta )E_F-\theta E_S+R_D$	$-(1-\theta )E_F-\theta E_S-L+R_D$

We will analyze the aforementioned payoffs matrix and derive and prove a series of theorems and inferences and explain their meanings.

Evolutionary game theory–based packet forwarding

ESSs of evolutionary game

The evolutionary process can be described by many different dynamic replicator models. A very widely used and famous dynamic replicator model was proposed by Taylor and Jonker ³³ in 1978, which can be used to describe the changing trends of the population’s behaviors. The replicator equation describes how the frequencies of a strategy changes over time. The nonlinear differential equation is given as follows ³⁴

$$F{x}_i=\frac{d{x}_i}{\mathrm{dt}}=x_i[U({\omega }_i,X)-U(X,X)]$$

(8)

where $U({\omega }_i,X)$ represents the total expected payoff of nodes selecting the pure strategy ${\omega }_i$ , and $U(X,X)$ represents the average payoff of the whole population $\mathrm{\Psi }$ and is described as $U(X,X)=\sum _{i=1}^k{x}_{i}U({\omega }_i,X)$ , where $k$ is the number of pure strategies.

The concept of ESS is central in evolutionary games. ³⁵ The ESS means that if the overwhelming majority of individuals choose evolutionarily stable strategies, then the small mutants cannot invade the population. In other words, under the pressure of natural selection, the mutant individuals either change their strategies to evolutionarily stable strategies or withdraw from the system and disappear in the process of evolution. If a population can eliminate the invasion of any small mutant population, then it is said that the population has reached an evolutionarily stable state. At this time, the strategies selected by the population are ESSs. It can be seen from the definition ³⁵ that when the system is in an evolutionarily stable state, unless there is a strong external impact, the system will not deviate. In this article, when a network system reaches an evolutionarily stable state, the nodes will take the optimal action rule against the perturbation effect and the performance of the wireless communications is observably improved by the optimal action in a packet-forwarding process with unreliable channels.

ESSs of packet-forwarding game

In the packet-forwarding game model, we have two strategies: Forward and Discard, we denote $X(t)=(x,1-x)$ as the mixed strategy for the population $\mathrm{\Psi }$ at time t, where $x$ is the rate of nodes selecting the Forward strategy (i.e. ${\omega }_1$ ), and $1-x$ is the rate of nodes selecting Discard strategy (i.e. ${\omega }_2$ ). According to equation (8), we can obtain the expected fitness of nodes selecting the Forward strategy as

$$\begin{array}{c}U({\omega }_1,X)\hfill \\ =\sum _{j=1}^2{x}_j{a}_{1j}=x(\theta R_T+\theta R_C-2(1-\theta )E_F-2\theta E_S+\gamma T)\hfill \\ +(1-x)(\theta R_T-2(1-\theta )E_F-2\theta E_S+\gamma T-2L)\hfill \end{array}$$

(9)

and the expected fitness of nodes selecting the Discard strategy as

$$\begin{array}{cc}\multicolumn{1}{c}{U({\omega }_2,X)}& =\sum _{j=1}^2{x}_j{a}_{2j}=x(\theta R_T-(1-\theta )E_F-\theta E_S\hfill \\ \multicolumn{1}{c}{}& +R_D+(1-x)(1-\theta )E_F-\theta E_S-L+R_D)\hfill \end{array}$$

(10)

The average fitness of the entire population $\mathrm{\Psi }$ is

$$U(X,X)=\sum _{i=1}^2{x}_{i}U({\omega }_i,X)=\mathrm{xU}({\omega }_1,X)+(1-x)U({\omega }_2,X)$$

(11)

Therefore, from equations (8)–(11), the dynamic replicator equation of Forward strategy is

$$\begin{array}{cc}\multicolumn{1}{c}{\mathrm{F}(x)}& =\frac{d{x}_1}{\mathrm{dt}}=x[U({\omega }_1,X)-U(X,X)]\hfill \\ \multicolumn{1}{c}{}& =x(1-x)\left[\begin{array}{c}x(\theta R_T-(1-\theta )E_F-\theta E_S+\gamma T-R_D)\hfill \\ \multicolumn{1}{c}{+(1-x)(\theta R_T-(1-\theta )E_F-\theta E_S+\gamma T-R_D-\mathrm{L})}\end{array}\right]\hfill \end{array}$$

(12)

Setting equation (12) equal to 0 allows us to get three solutions to this equation

$$\begin{array}{c}{x}_1^{*}=0\hfill \\ x_2^{*}=1\hfill \\ x_3^{*}=\frac{(1-\theta )E_F+\theta E_S+R_D+\mathrm{L}-\theta R_T-\gamma T}{L}\hfill \end{array}$$

(13)

Theorem 1

If $\theta R_T+\gamma T-(1-\theta )E_F-\theta E_S-R_D-\mathrm{L}<0$ and $\theta R_T+\gamma T-(1-\theta )E_F-\theta E_S-R_D>0$ , then both $x_1^{*}=0$ and $x_2^{*}=1$ are the ESSs of the packet-forwarding game.

Theorem 2

If $\theta R_T+\gamma T-(1-\theta )E_F-\theta E_S-R_D-\mathrm{L}>0$ , then $x_2^{*}=1$ is the only ESS of the packet-forwarding game.

Theorem 3

If $\theta R_T+\gamma T-(1-\theta )E_F-\theta E_S-R_D<0$ , then $x_1^{*}=0$ is the only ESS of the packet-forwarding game.

Proof

Mathematically, the stability theory of the differential equations implies that if $x^{*}$ is a stable state, then $\mathrm{F}\prime x^{*}$ must be less than 0.

Because $x_1^{*}=0$ and $x_2^{*}=1$ are two solutions of equation (12), we have $\mathrm{F}{x}_1^{*}=0$ and $\mathrm{F}{x}_2^{*}=0$ .

The derivative of $\mathrm{F}(x)$ in equation (12) can be written as

$$\begin{array}{cc}\multicolumn{1}{c}{\mathrm{F}\prime (x)}& =(1-2x)(\mathrm{Lx}+\theta R_T+\gamma T\hfill \\ \multicolumn{1}{c}{}& -(1-\theta )E_F-\theta E_S-R_D-L)+\mathrm{Lx}(1-x)\hfill \end{array}$$

(14)

Substituting $x_1^{*}=0$ and $x_2^{*}=1$ into (14) we get

$$\mathrm{F}\prime (0)=\theta R_T+\gamma T-(1-\theta )E_F-\theta E_S-R_D-L$$

(15)

$$\mathrm{F}\prime (1)=-\theta R_T-\gamma T+(1-\theta )E_F+\theta E_S+R_D$$

(16)

When $\theta R_T+\gamma T-(1-\theta )E_F-\theta E_S-R_D-L<0$ and $\theta R_T+\gamma T-(1-\theta )E_F-\theta E_S-R_D>0$ , we obtain

$$\begin{array}{c}\mathrm{F}\prime (0)=\theta R_T+\gamma T-(1-\theta )E_F-\theta E_S-R_D-L<0\hfill \\ \mathrm{F}\prime (1)=-\theta R_T-\gamma T+(1-\theta )E_F+\theta E_S+R_D<0\hfill \end{array}$$

(17)

From the aforementioned equations, according to the theorem of stability point of the differential equation, $x_1^{*}=0$ and $x_2^{*}=1$ are the ESSs of the packet-forwarding game. Thus, Theorem 1 is proved.

When $\theta R_T+\gamma T-(1-\theta )E_F-\theta E_S-R_D-\mathrm{L}>0$ , we get $\mathrm{F}\prime (0)=\theta R_T+\gamma T-(1-\theta )E_F-\theta E_S-R_D-L>0$ , and

$$\begin{array}{c}\multicolumn{1}{c}{\mathrm{F}\prime (1)=-\theta R_T-\gamma T+(1-\theta )E_F+\theta E_S+R_D}\\ \multicolumn{1}{c}{<-\theta R_T-\gamma T+(1-\theta )E_F+\theta E_S+R_D+L<0}\end{array}$$

According to the theorem of stability point of the differential equation, $x_1^{*}=1$ is the only ESS of the packet-forwarding game. Thus, Theorem 2 is proved.

When $\theta R_T+\gamma T-(1-\theta )E_F-\theta E_S-R_D<0$ , we get $\mathrm{F}\prime (1)=-\theta R_T-\gamma T+(1-\theta )E_F+\theta E_S+R_D>0$ , and

$$\begin{array}{c}\multicolumn{1}{c}{\mathrm{F}\prime (0)=\theta R_T+\gamma T-(1-\theta )E_F-\theta E_S-R_D-L}\\ \multicolumn{1}{c}{<\theta R_T+\gamma T-(1-\theta )E_F-\theta E_S-R_D<0}\end{array}$$

According to the theorem of stability point of the differential equation, $x_1^{*}=0$ is the only ESS of the packet-forwarding game. Thus, Theorem 3 is proved.

Theorem 1 indicates that when the initial rate of nodes selecting the Forward strategy is greater than $x_3^{*}=((1-\theta )E_F+\theta E_S+R_D+L-\theta R_T-\gamma T)/L$ , the nodes get more gain from selecting the Forward strategy than from selecting the Discard strategy; hence, more and more nodes will select the Forward strategy, and the rate of nodes selecting the Forward strategy will converge to 100%. If the initial rate of selecting the Forward strategy is less than $x_3^{*}$ , the nodes get more gain from selecting the Discard strategy than selecting the Forward strategy, the rate of selecting the Forward strategy will converge to 0% over time.

Theorem 2 indicates that whatever strategy is selected by a node, the gain of its next-hop relay node selecting the Forward strategy is always higher than that of selecting the Discard strategy. For example, when the network channel is stable, if a node needs to forward its important packets, such as emergency rescue information, the relay will get more reward by forwarding the important packets. If the reward is high enough to satisfy the condition of Theorem 2, the relay node can get more gain than Discard strategy, thus, the relay will always select Forward strategy, whether the provider node forwards its packets or not. Under the condition of Theorem 2, the Forward strategy is a strictly dominant strategy. In the end, the rate of nodes selecting the Forward strategy will be fixed at 100%. Theorem 3 is the opposite situation of Theorem 2.

The analysis of the packet-forwarding game

To ensure the communicating reliability of the MANETs and improve packet forwarding among nodes, we can adjust the control parameters to satisfy the conditions of Theorem 2 and avoid the conditions of Theorem 3.

Substitute $\theta =1-(1-q{)}^N$ , $E_F=\mathrm{NC}$ , and $E_S=((\theta -\mathrm{Nq}+\mathrm{Nq}\theta )/q\theta )C$ of section “Energy consumption of packet retransmission” into $\theta R_T+\gamma T-(1-\theta )E_F-\theta E_S-R_D-L$ and after simplification we obtain

$$\begin{array}{cc}\multicolumn{1}{c}{\theta R_T}& +\gamma T-(1-\theta )E_F-\theta E_S-R_D-L\hfill \\ \multicolumn{1}{c}{}& =\theta R_T+\gamma T-(1-\theta )\mathrm{NC}\hfill \\ \multicolumn{1}{c}{}& -\theta \frac{\theta -\mathrm{Nq}+\mathrm{Nq}\theta }{q\theta }C-R_D-L\hfill \\ \multicolumn{1}{c}{}& =\theta (R_T-\frac{C}{q})+\gamma T-R_D-L\hfill \end{array}$$

(18)

Inference 1

When $R_T-C/q<0$ and $\gamma T-R_D-L>-q{R}_T+C$ , if the upper limit of the retransmission number $N$ is reduced, a network is easier to converge to an evolutionarily stable state $x_2^{*}=1$ .

Proof

If the upper limit of the retransmission number $N$ decreases, then the value of $\theta =1-(1-q{)}^N>0$ decreases too, for $R_T-C/q<0$ , while the value of $\theta (R_T-(C/q))+\gamma T-R_D-L$ increases. If $N$ is set to the minimum value of 1 and we substitute $\gamma T-R_D-L>-q{R}_T+C$ into $\theta (R_T-(C/q))+\gamma T-R_D-L$ , we get

$$\theta (R_T-\frac{C}{q})+\gamma T-R_D-L>q(R_T-\frac{C}{q})-q{R}_T+C=0$$

(19)

from equation (18), we get

$$\begin{array}{cc}\multicolumn{1}{c}{\theta R_T}& +\gamma T-(1-\theta )E_F-\theta E_S-R_D-L\hfill \\ \multicolumn{1}{c}{}& =\theta (R_T-\frac{C}{q})+\gamma T-R_D-L>0\hfill \end{array}$$

(20)

According to Theorem 2, the networks can converge to an evolutionarily stable state $x_2^{*}=1$ . Inference 1 is proved.

Inference 1 indicates that if the upper limit of the retransmission number N becomes smaller, and the conditions of Theorem 2 are easily met, so it is easier to converge to the steady state $x_2^{*}=1$ . When N becomes smaller, and the number of packet retransmission will be reduced, thus, the nodes can save more energy and extend their life.

Inference 2

Improving the cooperative incentive $\gamma T$ can increase the rate of convergence to an evolutionarily stable state $x_2^{*}=1$ and reduce the rate of convergence to an evolutionarily stable state $x_1^{*}=0$ .

Proof

If the value of $\gamma T$ is increased, then the value $\theta R_T+\gamma T-(1-\theta )E_F-\theta E_S-R_D-L$ to increases, and it becomes easy to satisfy $\theta R_T+\gamma T-(1-\theta )E_F-\theta E_S-R_D-L>0$ , which is the condition of the Theorem 2, it can make networks converge to an evolutionarily stable state $x_2^{*}=1$ .

If the value of $\gamma T$ is increased, then the value $\theta R_T+\gamma T-(1-\theta )E_F-\theta E_S-R_D$ tends to increase, and it becomes difficult to satisfy $\theta R_T+\gamma T-(1-\theta )E_F-\theta E_S-R_D<0$ which is the condition of the Theorem 3, and it can make networks converge to an evolutionary stable state $x_1^{*}=0$ . Under the condition of Theorem 1, it can also be proved that inference 2 is correct. In a word, Inference 2 is proved.

Inference 2 indicates that if the nodes can get more gain by selecting Forward strategy than by selecting Discard strategy, improving the cooperation incentive will increase the profits of Forward strategy, which will promote more nodes to select Forward strategy, and increase the rate of convergence to an evolutionarily stable state $x_2^{*}=1$ . In turn, if the nodes can get more gains by selecting Discard strategy than by selecting Forward strategy, improving cooperation incentive will increase the profits of Forward strategy, which will reduce the nodes to select Discard strategy, and slow the rate of convergence to an evolutionarily stable state $x_1^{*}=0$ .

Inference 3

When $R_T-C/q>0$ , increasing the probability of successful packet transmissions $(q)$ promotes the rate of convergence to an evolutionarily stable state $x_2^{*}=1$ .

Proof

We know $q$ is the probability of successful packet transmissions, so $0<q<1$ , as the value of $q$ increases, then the value of $\theta =1-(1-q{)}^N>0$ and given the condition $R_T-c/q>0$ increases as well. From this, we can say that $\theta (R_T-C/q)>0$ and $\theta (R_T-C/q)+\gamma T-R_D-L$ increases as well, according to equation (18), and the value of $\theta R_T+\theta (E_F-E_S)-E_F+\gamma T-R_D-L=\theta (R_T-C/q)+\gamma T-R_D-L$ increases as well. It is easier to satisfy the condition of Theorem 2, it can promote the rate of convergence to an evolutionarily stable state $x_2^{*}=1$ . Inference 3 is proved.

Inference 3 indicates that when $R_T-C/q>0$ , the probability of successful packet transmissions $(q)$ is improved, and the conditions of Theorem 2 are easily met, so it is easier to converge to the steady state $x_2^{*}=1$ . When q is improved, and the packet loss rate is reduced, and the number of packet retransmission is reduced, the nodes can save more energy and extend their life. We can improve the probability of successful packet transmissions in MANETs by increasing channel reliability or by improving the transmission protocol algorithm.

Simulation experiments

The simulation experiments are divided into three parts in MATLAB 2015a.

1. The experiments in the first part are designed to verify Theorems 1–3.

2. The experiments in the second part are to investigate the effects of the parameters on the rate of convergence and verify the inferences.

3. The experiments in the third part are to compare the performances of packet-forwarding strategies of our model with that of Tang et al., ²³ in OPNET 14.5.

Verification experiments on Theorems 1–3

The experiment data settings are shown in Table 7. We set the parameters of groups 1 and 2 to satisfy the conditions of Theorem 1, groups 3 and 4 to satisfy the conditions of Theorems 2 and 3, respectively. The experimental results are shown in Figures 3–5, in which we can discover the changing trends of nodes’ evolution curves in MANETs.

Table 7.

Experimental data (1).

Number	Satisfy theorem	$q$	$R_T$	$R_D$	$C$	$L$	$N$	$\gamma T$
Group 1	Theorem 1	0.8	11.75	5	7	3	7	3
Group 2	Theorem 1	0.8	11.75	5	7	3	7	4
Group 3	Theorem 2	0.8	15	5	7	3	7	2
Group 4	Theorem 3	0.8	15	5	7	3	7	4

Figure 3.

The game evolutionary curves of Theorem 1.

Figure 4.

The game evolutionary curves of Theorem 2.

Figure 5.

The game evolutionary curves of Theorem 3.

In Figure 3, the red triangle curves and black square curves correspond to the groups 1 and 2 of the experimental data in Table 7, respectively. From equation (12), we can obtain the critical point of 0.333 and 0.6666, respectively. In the black triangle curve, we set the initial value as 0.334, which represents that the initial rate of the nodes selecting the Forward strategy is 33.4% in the MANETs. After playing the game approximately 45 times, the red triangle curve converges to 1. That is to say, the rate of nodes selecting the Forward strategy is stable at $x_2^{*}=1$ . Furthermore, when we set the initial value as 0.332, after playing the game approximately 100 times, the rate of nodes selecting the Forward strategy is stable at $x_1^{*}=0$ . In the black square curves, we set the initial values are 0.666 and 0.667, respectively. The black square curves converge to 0 or 1, respectively, after playing the games 90 times. Theorem 1 is verified.

In Figure 4, the broken black curve and the red solid curve correspond to the initial values 0.01 and 0.02, respectively. After playing the game more than 118 times, the rate of nodes selecting the Forward strategy is stable at $x_2^{*}=1$ . Thus, Theorem 2 is verified.

In Figure 5, the triangle curve and the square curve correspond to the initial values 0.9999 and 0.97, respectively. After playing the game more than 100 times, the rate of nodes selecting the Forward strategy is stable at $x_1^{*}=0$ . Thus, Theorem 3 is verified.

Experiments on the effect of factors

We study three important factors of inferences on evolutionarily stable states: the upper limit of the retransmission number $N$ , the cooperation incentive $\gamma T$ , and the probability of successful packet transmissions $q$ . The experimental data meet the conditions of the related Theorems and Inferences. Groups 1–3 vary the value of $N$ and keep the other parameter values the same; groups 4 and 5 and groups 6 and 7 vary the value of $\gamma T$ and keep the other parameters values the same, group 8 varies the value of $q$ and keep the other parameters values unchanged. The experimental data are shown in Table 8. The changing trends of evolution curves are shown in Figures 6–8.

Table 8.

Experimental data (2).

Number	Satisfy theorem	$q$	$R_T$	$R_D$	$C$	$L$	$N$	$\gamma T$
Group 1	Theorem 2	0.8	10.25	5	7	1	1	3
Group 2	Theorem 3	0.8	10.25	5	7	1	3	3
Group 3	Theorem 3	0.8	10.25	5	7	1	5	3
Group 4	Theorem 2	0.8	15	3	7	4	7	3
Group 5	Theorem 2	0.8	15	3	7	4	7	4
Group 6	Theorem 3	0.8	15	5	7	3	7	3
Group 7	Theorem 3	0.8	15	5	7	3	7	4
Group 8	Theorem 2	–	15	3	7	4	7	3

Figure 6.

Evolutionary curves of packet forwarding in terms of $N$ .

Figure 7.

Evolutionary curves of packet forwarding in terms of $\gamma T$ .

Figure 8.

Evolution curves of packet forwarding in terms of $q$ .

In Figure 6, group 1 meets the conditions of Theorem 2 and Inference 1, and groups 2 and 3 meet the conditions of Theorem 3 and Inference 1. The groups 2 and 3 correspond to the triangle and star curves of $N=3$ and $N=5$ , respectively. The initial rate of nodes selecting the Forward strategy is 1%. Obviously, the rate of the curve of $N=5$ converges faster than that of the curve of $N=3$ to $x_1^{*}=0$ . We can see that the smaller the upper limit of the retransmission number $N$ , the slower the rate of convergence to the evolutionary stable at $x_1^{*}=0$ . That is to say, it is easier to converge to the evolutionary stable at $x_2^{*}=1$ . When $N$ takes the minimum value of 1 in the first group of data, which corresponds to the square curve of $N=1$ , the square curve converges to the evolutionarily stable state $x_2^{*}=1$ .

Comparing the curves of the data of the three groups at the same parameters, if the upper limit of $N$ becomes smaller, it is easier to converge to the steady state $x_2^{*}=1$ . Thus, Inference 1 is verified.

Now we verify the correctness of Inference 2. In Figure 3, meeting the conditions of Theorem 1, the parameters of groups 1 and 2 in Table 7 are the same except the parameter of cooperative incentive γT. From Figure 3, we can see the speed of triangle curves tending to 1 is greater than that of square curve, while the speed tending to 0 is less than that of square curve, and the triangle curve and square curve correspond to $\gamma T=4$ and $\gamma T=3$ , respectively. In Figure 7, meeting the conditions of Theorem 2, the parameters of groups 1 and 2 in Table 8 are the same except the parameter of cooperative incentive γT. We can see the speed of broken curve tending to 1 is greater than that of solid curve, and the broken curve and the solid curve correspond to $\gamma T=4$ and $\gamma T=3$ , respectively. Similarly, meeting the conditions of Theorem 3, the speed of triangles curve tending to 0 is less than that of squares curve, and the triangles curve and the squares curve correspond to $\gamma T=4$ and $\gamma T=3$ , respectively. Thus, the inference 2 is verified.

In Figure 8, the eighth group parameters meet the conditions of Theorem 2 and Inference 3, and the initial rate of selecting the Forward strategy of nodes is 1%, for any $q\in (0,1)$ . We can see that all the curves will attain the stable state $x_2^{*}=1$ eventually. The curve of $q=0.2$ takes about 100 times of playing the game but the curve of $q=0.8$ only takes about 30 times of playing the game to converge to the stable state $x_2^{*}=1$ . From Figure 8, obviously, when the value $q$ increases from 0 to 1, a curve converges to the stable point $x_2^{*}=1$ faster. In sum, the greater the probability of successful packet transmissions $(q)$ is, the faster the MANETs will converge to the evolutionarily stable state $x_2^{*}=1$ . Thus, Inference 3 is verified.

Performance comparison

We compare the packet forwarding strategies (CPFS) proposed in this article with the algorithm of reputation enforcing evolutionary cooperation (AREEC) proposed by Tang et al. ²³ in terms of the probability of successful packet transmissions and network overhead.

• 1. The probability of successful packet transmissions.

The probability of successful packet transmissions refers to the ratio of the data received by the destination node to the data sent by the source node. The experimental results are shown in Figure 9.

Figure 9.

The rate of successful transmissions.

From Figure 9, we can see that our game model based on the mechanism of cooperation incentive can inhibit the selfishness of nodes to a certain extent, so it can improve the probability of successful packet transmissions compared with the algorithm of Tang et al.

• 2. Network overhead.

Network overhead is defined as the ratio of the total number of packets forwarded to the number of packets successfully forwarded. The experimental results are shown in Figure 10.

Figure 10.

Network overhead.

As can be seen from Figure 10, our algorithm (CPFS) is based on the reputation system to select the relay nodes, which are more trustworthy and willing to forward packets. Therefore, compared with the algorithm of Tang et al., our algorithm can reduce network overhead.

Conclusion

It is very important for a MANET with unreliable channels to forward packets. However, the limited energy and lack of central authority are likely to cause packet loss. In this article, we study the packet-forwarding strategies with unreliable channels based on evolutionary game. Considering the real network communication environment, we describe the detailed process of packet forwarding between a pair of nodes with the upper limit of the retransmissions number $N$ and have calculate the energy consumption of $k$ -times $(1\le k\le N)$ retransmissions. Considering the pack loss and data retransmissions and cooperation incentive mechanism, we build a packet-forwarding evolutionary game model in MANETs. Moreover, through the analysis of dynamic evolution, we draw the conditions of convergence to steady states and analyze the factors that affect the rate of convergence. Finally, the results of simulation experiments in MATLAB software have verified the effectiveness of the proposed theorems and inferences. In addition, the results of simulation experiments reveal how the rate of convergence to evolutionarily stable states is affected by three factors: cooperation incentive, the probability of successful packet transmissions, and the upper limit of the retransmission number. Compared to the algorithm of Tang et al., our model can improve the probability of successful packet transmissions and reduce the network overhead to a certain extent. Our game model provides a theoretical method to solve the problem of packet forwarding in unstable network environment.