# Packet Forwarding Strategies in Multiagent Systems: An Evolutionary Game Approach

Authors: Yuanjie Li; Xiaojun Wu
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

In multiagent systems (MASs), agents need to forward packets to each other to accomplish a target task. In this paper, we study packet forwarding among agents using evolutionary game theory under the mechanisms of Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA). Packet forwarding among agents plays a key role to stabilize the whole MAS. We study the transfer probability of packet forwarding of agents at the idle state or the busy state and computer the probability of the packet forwarding for a MAS. When agents make their decisions to selectForward orNo-Forward strategy, a packet forwarding evolutionary game model is built to reflect the utilities of different packet forwarding strategies. Two incentive mechanisms are introduced into the game model. One is to motivate agents to strengthen cooperation; the other is to encourage agents to select theNo-Forward strategy to save energy while they are in the busy state. The parameter value that encourages an agent to select the No-Forward strategy is inversely proportional to the average probability of the packet forwarding. The replicator dynamics of agent packet forwarding strategy evolution are given. We propose and prove the theorems indicating that evolutionarily stable strategies (ESSs) can be attained. The results of simulation experiments verify the correctness of the proposed theorems and the effects of the two incentive mechanisms and the probability of packet forwarding, which assures the robustness of evolutionary stable points among agents in MASs.


---

## Body

## 1. Introduction

Multiagent systems (MASs) are computerized systems composed of multiple interacting intelligent agents that have limited energy and self-organization ability. To achieve a common goal, MASs require them to self-organize into a network and collaborate with one another [1]. MASs are used most often in the engineering and technology fields. Examples of applications are disaster response, mobile robots, spacecraft, and sensor network [2].The agents need to interact with each other as much as possible to accomplish a target task. Cooperation is a fundamental problem in the distributed control community; the agents must effectively cooperate with each other for mutual benefit [3, 4]. The cooperative results lie in the actions taken by the interacting agents. In the process of cooperation, agents transmit messages to each other through packet forwarding. We assume that all agents in MASs are rational and aim at maximizing their own profits. When packet forwarding will incur certain costs, each agent makes a decision whether to forward a packet or not according to its own benefit. Hence, the pack forwarding can be described as a game, where players are rational agents with selfish behaviors and the strategy of a player is toForward orNo-Forward a packet. Agents can make a decision to forward packets or not according to their benefits.As a mathematical tool, game theory mainly focuses on the competitive and cooperative relationship of the participants, and it has been widely applied in the field of cooperation. Typical examples of evolutionary games include repeated prisoners’ dilemma and snowdrift games [5–7]. In [8], Shen et al. compare different methods of games and regard the evolutionary game as a good method to solve the problem of node cooperation. In the evolutionary game process, the individuals maximize their utilities by selecting a higher gain strategy, the ratio of individuals who select the corresponding strategies tends to be stable, and the population ultimately will attain a dynamic equilibrium state. Thus, the study of this cooperative packet forwarding model and evolutionary game theory in MASs is appropriate.In the paper, using a Markov chain model, we calculate the probability of packet forwarding while agents are in idle or busy states and analyze the packet forwarding behaviors of the agents. We then build a packet forwarding strategies game model, which defines the payoffs of the different strategies. Moreover, we introduce two incentive mechanisms into the game, one to increase agent cooperation by selectingForward strategy and the other to increase agent noncooperation by selectingNo-Forward strategy while the agent is in the busy state. Furthermore, using replicator dynamics, we obtain and prove the evolutionary stability theorems and inferences, which establish the conditions to attain steady states for the packet forwarding strategies game. The main contributions of this paper are as follows:(1) The Markov chain model is used to calculate the probability of packet forwarding for an agent at the idle or busy state. We establish a packet forwarding strategies game model with two incentive mechanisms. One incentive mechanism is to promote cooperation among agents by forwarding packets and the other is to promote noncooperation among agents by selecting theNo-Forward strategy to save energy while the agent is in the busy state.(2) Replicator dynamics is used to prove the evolutionary stability theorems and inferences, which provide the conditions to attain stable states for the packet forwarding strategies game model in MASs.(3) The experiments verify the correctness of the provided theorems and inferences. Also, the experiments show the effects of two incentive mechanisms and the probability of packet forwarding of agents on the rate of convergence to stable states.The rest of the paper is organized as follows. We first discuss the related research in Section2 and set up a packet forwarding Markov model in Section 3. We propose an evolutionary game model of packet forwarding strategies and present the theorems including the conditions of ESSs in Sections 4 and 5. The simulation results are shown in Section 6 and, finally, Section 7 is the conclusion.


## 2. Related Work

In recent years, to provide an incentive for the agents/nodes to cooperate, two mechanisms have been devised: incentive mechanisms and punishment mechanisms, which incentivize agents/nodes to forward the others’ packets and punish misbehaving nodes. Most research involves strengthening packet forwarding among nodes/agents by setting up incentive-based systems [9, 10] or reputation-based systems [11, 12]. Most incentive-based mechanisms give a reward to nodes/agents for participating in packet forwarding [9]. In a reputation-based system, a node’s behavior is monitored and evaluated by its neighbors and each node is required to keep track of its neighbors’ reputation values, which are updated based on weighted calculations of the value of the node’s own observations and the value of the other nodes’ recommendations [12].Also packet forwarding strategies and cooperative strategies among nodes have been studied by different types of game theory in wireless networks, such as repeated games [13, 14], no-cooperation games [15–17], bargaining games [18], and evolutionary games [19–25].Zhu et al. [13] propose an adaptive repeated game scheme to ensure the cooperation among nodes in wireless networks and implement a self-learning algorithm to improve cooperation probabilities. The simulation results show that the selfish nodes are indeed more likely to cooperate with each other by the schemes above, but they may be unsuitable for MASs. To stimulate selfish nodes to cooperate, Xu et al. [17] propose a Win-Stay, Lose-Likely Shift (WSLLS) approach in a Prisoner’s Dilemma (PD) game and a utility-based function is applied to evaluate a player’s (i.e., node) performance. Experimental results show that the approach is effective in stimulating cooperation in different settings. Akkarajitsakul et al. [18] propose an approach to cooperatively forward packets based on coalition formation among mobile nodes. They use a bargaining game to find the most suitable probabilities in which each node would help other mobile nodes. They present a distributed algorithm to obtain the stable coalitions and they use a Markov-chain-based analysis to evaluate the stable coalitional structures that are obtained from the distributed algorithm. Performance evaluation results show that the mobile nodes with coalition formation have higher payoffs than mobile nodes acting alone.Among these methods of evolutionary game theory, some stimulation mechanisms are proposed to incentivize the nodes’ cooperation. Shen et al. [19] propose stimulating mechanisms to promote trust cooperation among nodes and analyze the dynamic evolutionary process of nodes selecting the trust strategy and derive several conditions with which the networks can attain the stable states. Li et al. [20], based on [19], consider a factor of packet loss in the data retransmission process and introduce a strategy adjustment mechanism into the evolutionary game process. This strategy adjustment mechanism compensates for the fact that the replicator dynamic model cannot reflect the requirements of individual strategy adjustments. The experiments show that the rate of convergence to reach the stable state of the strategy adjustment mechanism is faster than that of the normal replicator dynamic evolutionary method. Based on evolutionary game theory, Chen et al. [22] adopt a suitable dynamic incentive mechanism for WSNs, which emphasizes the nodes’ adjust strategies forwardly and passively. This mechanism enables the selfish nodes to cooperate with each other and keep the network normal.Among these methods of evolutionary game theory, some researchers study packet forwarding among nodes in different scenarios. Li et al. [23] study the adaptive packet forwarding of potential selfish nodes in mobile social networks (MSNs) and propose an incentive compatible multiple-copy packet forwarding (ICMPF) protocol to reduce the delivery overhead and to perpetuate a successful packet delivery. They design an evolutionary game model to guide the forwarding behavior of interaction nodes. Finally, they prove that the strategy dynamics eventually achieves the ESS and develop another strategy dynamics method which achieves the ESS. This method includes the nodes’ distributed learning algorithm. Considering the noisy observation of transmissions and the loss of packets, Tang et al. [24] study packet forwarding among cooperative nodes in a one-hop unreliable channel. Based on evolutionary game theory, they propose an indirect reciprocity framework and enforce packet forwarding strategies in mobile ad hoc networks (MANETs). They also analyze the evolutionary dynamics of cooperative strategies game model and calculate the threshold of cost-to-benefit ratio to ensure cooperation among nodes. Lastly, the proposed cooperative solution is verified by the numerical simulations. To enforce cooperation in the case of channel noise, Wang et al. [25] focus on one-hop information exchange and design a packet forwarding game model with imperfect private monitoring and propose a state machine-based strategy to reach Nash equilibrium which proved to be a sequential state with carefully designed system parameters.Compared to [19–25], our work is distinctive. Our packet forwarding strategy is derived partly from trust using game theory [19, 20]. Considering the packet forwarding randomness of an agent’s communication state, derived from the Markov model [26], we calculate the probability of packet forwarding of agents at the idle or busy state using properties of a Markov chain, build a packet forwarding game model with the probability of packet forwarding, and introduce two incentive mechanisms in the game model. One incentive mechanism is to promote agents to strengthen cooperation and the other is to encourage agents to selectNo-Forward strategy to save energy while they are in the busy state. We set the parameter value inversely proportional to the probability of packet forwarding. In contrast, there is only one simple incentive cooperation mechanism in [19, 20]. Furthermore, we consider the agent’s payoff impacted by the probability of packet forwarding, which is related to whether the agent’s communication state is idle or busy, while Wang et al. [25] consider only the impact of probability of packet loss on node payoff. Li et al. [23] and Tang et al. [24] calculate the payoffs of forwarding packets between nodes without taking into account the interaction cooperation of nodes, which is different from ours. Thus, our packet forwarding strategies game is different from the related literature described above.


## 3. Packet Forwarding Markov Model

### 3.1. Packet Forwarding Markov Chain

Packet forwarding among agents in MASs is not a deterministic process. The present value of the process is independent of all past values. The process is a no-after-effects process and hence has Markov properties.Time series of packet forwarding can be expressed by a Markov chain. Ift
1
<
t
2
…
<
t
n
⊂
Γ, then(1)
P
X
t
n
=
X
n
∣
X
t
n
-
1
=
X
n
-
1
,
…
,
X
t
1
=
X
1
=
P
X
t
n
=
X
n
∣
X
t
n
-
1
.In this section, we build a Markov model of packet forwarding among agents in MASs. Let us assume the following:(1) If an agent has a new packet to forward, it forwards it at the beginning of the next time-slot.(2) If an agent successfully forwards its packet, it can forward a new packet in the next time-slot.(3) If an agent detects a collision, it forwards its packet in each subsequent time-slot until the packet is successfully forwarded.With the assumptions, each agent is in either an idle state or a busy (backlogged) state. An agent is in the busy state if the number of packets that need to be transmitted exceeds its transmitting capacity, which leads to buffer overflow and loss of data packets. Furthermore, because agents have limited computing and communication capability with a multihop and many-to-one communication method, when the wireless communication channels present noise, or the network topology changes, or the packets suddenly increased because of an emergency, the agents may easily be in a busy state that will cause network delay and loss of data packets. The decision to forward the packet or not depends only on whether the agent is busy or not. Therefore, the packet forwarding decision in one time-slot for each agent is Markovian. Since agents always have packets to forward, the notations are shown in Table1.Table 1
Notations (1).
N
The number of agents in the MASs.
I and B
The idle and busy states of an agent, respectively.
P
I and P
B
The probabilities of packet forwarding of an agent at the idle state and the busy state, respectively.
α
The probability of packet forwarding at idle state of an agent. The probability of packet no forwarding at the idle state of an agent is1
-
α.
β
The probability of packet no forwarding at the busy (backlogged) state of an agent. The probability of packet forwarding at busy state of an agent is1
-
β
.
P
I
B
The state transition matrix of the Markov chain of an agent.Packet forwarding is regarded as a two-state Markov chain in MASs. The state transition diagram of the Markov chain is shown in Figure1. The arrows indicate the direction of the state transition, and the symbols on the edges indicate the transition probabilities.Figure 1
The state transition diagram of the Markov chain of an agent.The state diagram of a Markov chain describes the probability of all state transitions and their probabilities and is expressed in matrix form as follows [26]:(2)
P
I
B
=
α
1
-
α
1
-
β
β
.P
I
B is the state transition matrix of the Markov chain of an agent.


### 3.2. The Probability of Packet Forwarding

The issue is how to determine the probabilities of the other time-slots once the probability of the initial state is given.Suppose the initial probabilities of packet forwarding at the idle state and the busy state areP
I
t
0 and P
B
t
0.The initial state is expressed by the initial probability row vector, that is,(3)
P
t
0
=
P
I
t
0
P
B
t
0
.The probability of the next time-slot is(4)
P
t
1
=
P
t
0
P
I
B
=
P
I
t
0
P
B
t
0
α
1
-
α
1
-
β
β
.As time progresses from n to n+1, the general expression is(5)
P
t
n
+
1
=
P
t
n
P
I
B
.Another way to write these equations is(6)
P
t
n
+
1
=
P
t
n
P
I
B
=
P
t
n
-
1
P
I
B
P
I
B
.Now, letn
→
∞. The Markov convergence theorem says that the probability converges to a steady state and P
-
I and P
-
B are the eigenvectors of the unit eigenvalues of P
I and P
B, which are, using Mathematica software,(7)
V
-
I
B
=
P
-
I
P
-
B
=
1
-
β
2
-
α
-
β
1
-
α
2
-
α
-
β
.Notice that(8)
P
-
I
+
P
-
B
=
1
.P
-
I and P
-
B are the probabilities of packet forwarding of agents at the idle state and the busy state. The probability of packet forwarding of agents is simply denoted as P.


## 3.1. Packet Forwarding Markov Chain

Packet forwarding among agents in MASs is not a deterministic process. The present value of the process is independent of all past values. The process is a no-after-effects process and hence has Markov properties.Time series of packet forwarding can be expressed by a Markov chain. Ift
1
<
t
2
…
<
t
n
⊂
Γ, then(1)
P
X
t
n
=
X
n
∣
X
t
n
-
1
=
X
n
-
1
,
…
,
X
t
1
=
X
1
=
P
X
t
n
=
X
n
∣
X
t
n
-
1
.In this section, we build a Markov model of packet forwarding among agents in MASs. Let us assume the following:(1) If an agent has a new packet to forward, it forwards it at the beginning of the next time-slot.(2) If an agent successfully forwards its packet, it can forward a new packet in the next time-slot.(3) If an agent detects a collision, it forwards its packet in each subsequent time-slot until the packet is successfully forwarded.With the assumptions, each agent is in either an idle state or a busy (backlogged) state. An agent is in the busy state if the number of packets that need to be transmitted exceeds its transmitting capacity, which leads to buffer overflow and loss of data packets. Furthermore, because agents have limited computing and communication capability with a multihop and many-to-one communication method, when the wireless communication channels present noise, or the network topology changes, or the packets suddenly increased because of an emergency, the agents may easily be in a busy state that will cause network delay and loss of data packets. The decision to forward the packet or not depends only on whether the agent is busy or not. Therefore, the packet forwarding decision in one time-slot for each agent is Markovian. Since agents always have packets to forward, the notations are shown in Table1.Table 1
Notations (1).
N
The number of agents in the MASs.
I and B
The idle and busy states of an agent, respectively.
P
I and P
B
The probabilities of packet forwarding of an agent at the idle state and the busy state, respectively.
α
The probability of packet forwarding at idle state of an agent. The probability of packet no forwarding at the idle state of an agent is1
-
α.
β
The probability of packet no forwarding at the busy (backlogged) state of an agent. The probability of packet forwarding at busy state of an agent is1
-
β
.
P
I
B
The state transition matrix of the Markov chain of an agent.Packet forwarding is regarded as a two-state Markov chain in MASs. The state transition diagram of the Markov chain is shown in Figure1. The arrows indicate the direction of the state transition, and the symbols on the edges indicate the transition probabilities.Figure 1
The state transition diagram of the Markov chain of an agent.The state diagram of a Markov chain describes the probability of all state transitions and their probabilities and is expressed in matrix form as follows [26]:(2)
P
I
B
=
α
1
-
α
1
-
β
β
.P
I
B is the state transition matrix of the Markov chain of an agent.


## 3.2. The Probability of Packet Forwarding

The issue is how to determine the probabilities of the other time-slots once the probability of the initial state is given.Suppose the initial probabilities of packet forwarding at the idle state and the busy state areP
I
t
0 and P
B
t
0.The initial state is expressed by the initial probability row vector, that is,(3)
P
t
0
=
P
I
t
0
P
B
t
0
.The probability of the next time-slot is(4)
P
t
1
=
P
t
0
P
I
B
=
P
I
t
0
P
B
t
0
α
1
-
α
1
-
β
β
.As time progresses from n to n+1, the general expression is(5)
P
t
n
+
1
=
P
t
n
P
I
B
.Another way to write these equations is(6)
P
t
n
+
1
=
P
t
n
P
I
B
=
P
t
n
-
1
P
I
B
P
I
B
.Now, letn
→
∞. The Markov convergence theorem says that the probability converges to a steady state and P
-
I and P
-
B are the eigenvectors of the unit eigenvalues of P
I and P
B, which are, using Mathematica software,(7)
V
-
I
B
=
P
-
I
P
-
B
=
1
-
β
2
-
α
-
β
1
-
α
2
-
α
-
β
.Notice that(8)
P
-
I
+
P
-
B
=
1
.P
-
I and P
-
B are the probabilities of packet forwarding of agents at the idle state and the busy state. The probability of packet forwarding of agents is simply denoted as P.


## 4. Packet Forwarding Game Model of MASs

### 4.1. Network Model

#### 4.1.1. Network Model Environment

A multiagent system is a system that can accomplish a common goal with a number of mutually independent agents which possess the ability of self-organization, learning, and reasoning. It is critical that all agents have the independent ability to cooperate with each other, which ensures accomplishing the expected task for a multiagent system.When agents perform a task in a noisy environment, they may be disturbed by some external factors. The main reason for loss packet is network congestion during the packet forwarding process. Assume that all agents have the same communication status factors in the MASs and that all agents have the same probability of successfully forwarding and receiving packets at any one time.


#### 4.1.2. Packet Forwarding Strategy Description

Communication among agents depends on packet forwarding with each other, and each agent has two strategies to select:Forward orNo-Forward. In general, if an agent selects theForward strategy, this will help other agents forward packets so as to enhance cooperation with each other and obtain profit at the same time. However, if an agent selects theNo-Forward strategy, which will drop the packets that other agents forwarded, it may obtain gains for saving energy, but the behavior of dropping packets will result in a loss for the other agents. Table 2 displays the symbols used to describe this process.Table 2
Notations (2).
R
T
Gain obtained by an agent selectingForward strategy, which also helps other agents to forward a packet successfully.
R
D
The incentive for noncooperation, gain obtained by an agent selectingNo-Forward strategy to save energy while the agent is at the busy (backlogged) state.
R
C
Cooperation gain of an agent due to its opponent selecting theForward strategy and successfully forwarding a packet.
C
Cost caused by an agent forwarding others’ a packet or sending its own packet.
L
No cooperative loss of an agent for its opponent selectingNo-Forward strategy.
W
The incentive for cooperation while an agent selects theForward strategy. (W ≥ 0)


### 4.2. Packet Forwarding Game Model

When agents interact with each other in MASs, each agent can make a decision to select the strategy eitherForward orNo-Forwardaccording to its gains; that is, the agents can get different gains by selecting a different strategy during the interactive process.When two agents A and B transmit packets, each has two strategies:Forward andNo-Forward. The two-agent packet forwarding model is shown in Figure 2.Figure 2
Two-agent packet forwarding model.There are three situations of packet forwarding strategy between two agents: both interactive agents selectForward strategy, only one agent selectsForward strategy, or both interactive agents selectNo-Forward strategy. These situations are discussed in what follows.


#### 4.2.1. Two Interactive Agents Selecting theForwardStrategy

An agent might fail to transport packets due to the channel noise in MASs. Each packet forwarding strategy results in either success or failure. Suppose two agents, A and B, select one strategy. There are 4 different events in total. Table3 shows the gains of the agents at the probabilities of each event occurring.Table 3
Payoffs of two interactive agents selecting theForward strategy.
Serial number
A
B
Probability
A profit G(A)
B profit G(B)
Forward
Forward
P
1
1
1
P
2
R
T
+
R
C
+
W
-
2
C
R
T
+
R
C
+
W
-
2
C
2
1
0
P
(
1
-
P
)
R
T
+
W
-
2
C
R
C
+
W
-
2
C
3
0
1
P
(
1
-
P
)
R
C
+
W
-
2
C
R
T
+
W
-
2
C
4
0
0
(
1
-
P
)
2
W
-
2
C
W
-
2
CIn Tables3–5, the symbol P indicates the probability of packet forwarding of an agent, and 0 and 1 indicate failure and success, respectively.Table 4
Payoffs of only one agent selecting theForward strategy.
Serial number
A
B
Probability
A profit G(A)
B profit G(B)
Forward
No-Forward
P
1
1
1
P
2
R
T
+
W
-
2
C
-
L
R
C
-
C
+
R
D
2
1
0
P
(
1
-
P
)
R
T
+
W
-
2
C
-
L
R
C
-
C
+
R
D
3
0
1
P
(
1
-
P
)
W
-
2
C
-
L
-
C
+
R
D
4
0
0
(
1
-
P
)
2
W
-
2
C
-
L
-
C
+
R
DTable 5
Payoffs of two agents both selecting theNo-Forward strategy.
Serial number
A
B
Probability
A profit G(A)
B profit G(B)
No-Forward
No-Forward
P
1
1
1
P
2
-
C
+
R
D
-
C
+
R
D
2
1
0
P
(
1
-
P
)
-
C
+
R
D
-
C
+
R
D
3
0
1
P
(
1
-
P
)
-
C
+
R
D
-
C
+
R
D
4
0
0
(
1
-
P
)
2
-
C
+
R
D
-
C
+
R
DIn Table3, A and B both select theForward strategy. The expected payoff for each agent is the sum of each probability multiplied by its corresponding payoff [20]. Thus, the payoffs of agents A and B are equal, that is,(9)
∑
i
=
0
4
P
i
G
i
A
=
∑
i
=
0
4
P
i
G
i
B
=
P
R
T
+
P
R
C
+
W
-
2
C
.wherei is the serial number.


#### 4.2.2. Only One Agent Selects theForward Strategy

When two agents A and B interact, agent A selects theForward strategy, while agent B selects theNo-Forward strategy; but agent B can send its packets. Here, the selfish rational node is sending only its own packets without forwarding others’ packets. There are 4 different events in total as shown in Table 4.In Table4, only one agent selects theForward strategy. The expected payoff of each agent is the sum of each probability multiplied by its corresponding payoff [20]. Thus, the payoff of agent A selecting theForward strategy is(10)
∑
i
=
0
4
P
i
G
i
A
=
P
R
T
+
W
-
2
C
-
L
,and the payoff of agent B selecting theNo-Forward strategy is(11)
∑
i
=
0
4
P
i
G
i
B
=
P
R
C
+
R
D
-
C
,wherei is the serial number.


#### 4.2.3. Two Agents Both Selecting theNo-Forward Strategy

Two agents A and B select theNo-Forward strategy, but agents A and B can send their own packets. There are 4 different events in total as shown in Table 5.In Table5, two agents A and B both select theNo-Forward strategy. The expected payoff of each agent is the sum of each probability multiplied by its corresponding payoff [20]. Thus, the payoffs of agents A and B are equal, that is, (12)
∑
i
=
0
4
P
i
G
i
A
=
∑
i
=
0
4
P
i
G
i
B
=
-
C
+
R
D
.


### 4.3. Packet Forwarding Game

Definition 1.
The packet forwarding game in MASs is a quadrupleΓ
(
Ψ
,
N
,
Ω
,
U
), where
(1)Ψ is a population comprising an arbitrary number of individuals;
(2)N is the set of individuals in the population Ψ;
(3)Ω is a space of strategies from which an agent can select Ω
=
{
ω
1, ω
2
}
=
{
F
o
r
w
a
r
d
,
N
o
-
F
o
r
w
a
r
d
};
(4)U is the matrix of payoffs of all the participating individuals as shown in Table 6.Table 6
Payoff matrix.
Forward
No-Forward
Forward
P
R
T
+
P
R
C
+
W
-
2
C
P
R
T
+
W
-
2
C
-
L
No-Forward
P
R
C
+
R
D
-
C
-
C
+
R
D


## 4.1. Network Model

### 4.1.1. Network Model Environment

A multiagent system is a system that can accomplish a common goal with a number of mutually independent agents which possess the ability of self-organization, learning, and reasoning. It is critical that all agents have the independent ability to cooperate with each other, which ensures accomplishing the expected task for a multiagent system.When agents perform a task in a noisy environment, they may be disturbed by some external factors. The main reason for loss packet is network congestion during the packet forwarding process. Assume that all agents have the same communication status factors in the MASs and that all agents have the same probability of successfully forwarding and receiving packets at any one time.


### 4.1.2. Packet Forwarding Strategy Description

Communication among agents depends on packet forwarding with each other, and each agent has two strategies to select:Forward orNo-Forward. In general, if an agent selects theForward strategy, this will help other agents forward packets so as to enhance cooperation with each other and obtain profit at the same time. However, if an agent selects theNo-Forward strategy, which will drop the packets that other agents forwarded, it may obtain gains for saving energy, but the behavior of dropping packets will result in a loss for the other agents. Table 2 displays the symbols used to describe this process.Table 2
Notations (2).
R
T
Gain obtained by an agent selectingForward strategy, which also helps other agents to forward a packet successfully.
R
D
The incentive for noncooperation, gain obtained by an agent selectingNo-Forward strategy to save energy while the agent is at the busy (backlogged) state.
R
C
Cooperation gain of an agent due to its opponent selecting theForward strategy and successfully forwarding a packet.
C
Cost caused by an agent forwarding others’ a packet or sending its own packet.
L
No cooperative loss of an agent for its opponent selectingNo-Forward strategy.
W
The incentive for cooperation while an agent selects theForward strategy. (W ≥ 0)


## 4.1.1. Network Model Environment

A multiagent system is a system that can accomplish a common goal with a number of mutually independent agents which possess the ability of self-organization, learning, and reasoning. It is critical that all agents have the independent ability to cooperate with each other, which ensures accomplishing the expected task for a multiagent system.When agents perform a task in a noisy environment, they may be disturbed by some external factors. The main reason for loss packet is network congestion during the packet forwarding process. Assume that all agents have the same communication status factors in the MASs and that all agents have the same probability of successfully forwarding and receiving packets at any one time.


## 4.1.2. Packet Forwarding Strategy Description

Communication among agents depends on packet forwarding with each other, and each agent has two strategies to select:Forward orNo-Forward. In general, if an agent selects theForward strategy, this will help other agents forward packets so as to enhance cooperation with each other and obtain profit at the same time. However, if an agent selects theNo-Forward strategy, which will drop the packets that other agents forwarded, it may obtain gains for saving energy, but the behavior of dropping packets will result in a loss for the other agents. Table 2 displays the symbols used to describe this process.Table 2
Notations (2).
R
T
Gain obtained by an agent selectingForward strategy, which also helps other agents to forward a packet successfully.
R
D
The incentive for noncooperation, gain obtained by an agent selectingNo-Forward strategy to save energy while the agent is at the busy (backlogged) state.
R
C
Cooperation gain of an agent due to its opponent selecting theForward strategy and successfully forwarding a packet.
C
Cost caused by an agent forwarding others’ a packet or sending its own packet.
L
No cooperative loss of an agent for its opponent selectingNo-Forward strategy.
W
The incentive for cooperation while an agent selects theForward strategy. (W ≥ 0)


## 4.2. Packet Forwarding Game Model

When agents interact with each other in MASs, each agent can make a decision to select the strategy eitherForward orNo-Forwardaccording to its gains; that is, the agents can get different gains by selecting a different strategy during the interactive process.When two agents A and B transmit packets, each has two strategies:Forward andNo-Forward. The two-agent packet forwarding model is shown in Figure 2.Figure 2
Two-agent packet forwarding model.There are three situations of packet forwarding strategy between two agents: both interactive agents selectForward strategy, only one agent selectsForward strategy, or both interactive agents selectNo-Forward strategy. These situations are discussed in what follows.


### 4.2.1. Two Interactive Agents Selecting theForwardStrategy

An agent might fail to transport packets due to the channel noise in MASs. Each packet forwarding strategy results in either success or failure. Suppose two agents, A and B, select one strategy. There are 4 different events in total. Table3 shows the gains of the agents at the probabilities of each event occurring.Table 3
Payoffs of two interactive agents selecting theForward strategy.
Serial number
A
B
Probability
A profit G(A)
B profit G(B)
Forward
Forward
P
1
1
1
P
2
R
T
+
R
C
+
W
-
2
C
R
T
+
R
C
+
W
-
2
C
2
1
0
P
(
1
-
P
)
R
T
+
W
-
2
C
R
C
+
W
-
2
C
3
0
1
P
(
1
-
P
)
R
C
+
W
-
2
C
R
T
+
W
-
2
C
4
0
0
(
1
-
P
)
2
W
-
2
C
W
-
2
CIn Tables3–5, the symbol P indicates the probability of packet forwarding of an agent, and 0 and 1 indicate failure and success, respectively.Table 4
Payoffs of only one agent selecting theForward strategy.
Serial number
A
B
Probability
A profit G(A)
B profit G(B)
Forward
No-Forward
P
1
1
1
P
2
R
T
+
W
-
2
C
-
L
R
C
-
C
+
R
D
2
1
0
P
(
1
-
P
)
R
T
+
W
-
2
C
-
L
R
C
-
C
+
R
D
3
0
1
P
(
1
-
P
)
W
-
2
C
-
L
-
C
+
R
D
4
0
0
(
1
-
P
)
2
W
-
2
C
-
L
-
C
+
R
DTable 5
Payoffs of two agents both selecting theNo-Forward strategy.
Serial number
A
B
Probability
A profit G(A)
B profit G(B)
No-Forward
No-Forward
P
1
1
1
P
2
-
C
+
R
D
-
C
+
R
D
2
1
0
P
(
1
-
P
)
-
C
+
R
D
-
C
+
R
D
3
0
1
P
(
1
-
P
)
-
C
+
R
D
-
C
+
R
D
4
0
0
(
1
-
P
)
2
-
C
+
R
D
-
C
+
R
DIn Table3, A and B both select theForward strategy. The expected payoff for each agent is the sum of each probability multiplied by its corresponding payoff [20]. Thus, the payoffs of agents A and B are equal, that is,(9)
∑
i
=
0
4
P
i
G
i
A
=
∑
i
=
0
4
P
i
G
i
B
=
P
R
T
+
P
R
C
+
W
-
2
C
.wherei is the serial number.


### 4.2.2. Only One Agent Selects theForward Strategy

When two agents A and B interact, agent A selects theForward strategy, while agent B selects theNo-Forward strategy; but agent B can send its packets. Here, the selfish rational node is sending only its own packets without forwarding others’ packets. There are 4 different events in total as shown in Table 4.In Table4, only one agent selects theForward strategy. The expected payoff of each agent is the sum of each probability multiplied by its corresponding payoff [20]. Thus, the payoff of agent A selecting theForward strategy is(10)
∑
i
=
0
4
P
i
G
i
A
=
P
R
T
+
W
-
2
C
-
L
,and the payoff of agent B selecting theNo-Forward strategy is(11)
∑
i
=
0
4
P
i
G
i
B
=
P
R
C
+
R
D
-
C
,wherei is the serial number.


### 4.2.3. Two Agents Both Selecting theNo-Forward Strategy

Two agents A and B select theNo-Forward strategy, but agents A and B can send their own packets. There are 4 different events in total as shown in Table 5.In Table5, two agents A and B both select theNo-Forward strategy. The expected payoff of each agent is the sum of each probability multiplied by its corresponding payoff [20]. Thus, the payoffs of agents A and B are equal, that is, (12)
∑
i
=
0
4
P
i
G
i
A
=
∑
i
=
0
4
P
i
G
i
B
=
-
C
+
R
D
.


## 4.2.1. Two Interactive Agents Selecting theForwardStrategy

An agent might fail to transport packets due to the channel noise in MASs. Each packet forwarding strategy results in either success or failure. Suppose two agents, A and B, select one strategy. There are 4 different events in total. Table3 shows the gains of the agents at the probabilities of each event occurring.Table 3
Payoffs of two interactive agents selecting theForward strategy.
Serial number
A
B
Probability
A profit G(A)
B profit G(B)
Forward
Forward
P
1
1
1
P
2
R
T
+
R
C
+
W
-
2
C
R
T
+
R
C
+
W
-
2
C
2
1
0
P
(
1
-
P
)
R
T
+
W
-
2
C
R
C
+
W
-
2
C
3
0
1
P
(
1
-
P
)
R
C
+
W
-
2
C
R
T
+
W
-
2
C
4
0
0
(
1
-
P
)
2
W
-
2
C
W
-
2
CIn Tables3–5, the symbol P indicates the probability of packet forwarding of an agent, and 0 and 1 indicate failure and success, respectively.Table 4
Payoffs of only one agent selecting theForward strategy.
Serial number
A
B
Probability
A profit G(A)
B profit G(B)
Forward
No-Forward
P
1
1
1
P
2
R
T
+
W
-
2
C
-
L
R
C
-
C
+
R
D
2
1
0
P
(
1
-
P
)
R
T
+
W
-
2
C
-
L
R
C
-
C
+
R
D
3
0
1
P
(
1
-
P
)
W
-
2
C
-
L
-
C
+
R
D
4
0
0
(
1
-
P
)
2
W
-
2
C
-
L
-
C
+
R
DTable 5
Payoffs of two agents both selecting theNo-Forward strategy.
Serial number
A
B
Probability
A profit G(A)
B profit G(B)
No-Forward
No-Forward
P
1
1
1
P
2
-
C
+
R
D
-
C
+
R
D
2
1
0
P
(
1
-
P
)
-
C
+
R
D
-
C
+
R
D
3
0
1
P
(
1
-
P
)
-
C
+
R
D
-
C
+
R
D
4
0
0
(
1
-
P
)
2
-
C
+
R
D
-
C
+
R
DIn Table3, A and B both select theForward strategy. The expected payoff for each agent is the sum of each probability multiplied by its corresponding payoff [20]. Thus, the payoffs of agents A and B are equal, that is,(9)
∑
i
=
0
4
P
i
G
i
A
=
∑
i
=
0
4
P
i
G
i
B
=
P
R
T
+
P
R
C
+
W
-
2
C
.wherei is the serial number.


## 4.2.2. Only One Agent Selects theForward Strategy

When two agents A and B interact, agent A selects theForward strategy, while agent B selects theNo-Forward strategy; but agent B can send its packets. Here, the selfish rational node is sending only its own packets without forwarding others’ packets. There are 4 different events in total as shown in Table 4.In Table4, only one agent selects theForward strategy. The expected payoff of each agent is the sum of each probability multiplied by its corresponding payoff [20]. Thus, the payoff of agent A selecting theForward strategy is(10)
∑
i
=
0
4
P
i
G
i
A
=
P
R
T
+
W
-
2
C
-
L
,and the payoff of agent B selecting theNo-Forward strategy is(11)
∑
i
=
0
4
P
i
G
i
B
=
P
R
C
+
R
D
-
C
,wherei is the serial number.


## 4.2.3. Two Agents Both Selecting theNo-Forward Strategy

Two agents A and B select theNo-Forward strategy, but agents A and B can send their own packets. There are 4 different events in total as shown in Table 5.In Table5, two agents A and B both select theNo-Forward strategy. The expected payoff of each agent is the sum of each probability multiplied by its corresponding payoff [20]. Thus, the payoffs of agents A and B are equal, that is, (12)
∑
i
=
0
4
P
i
G
i
A
=
∑
i
=
0
4
P
i
G
i
B
=
-
C
+
R
D
.


## 4.3. Packet Forwarding Game

Definition 1.
The packet forwarding game in MASs is a quadrupleΓ
(
Ψ
,
N
,
Ω
,
U
), where
(1)Ψ is a population comprising an arbitrary number of individuals;
(2)N is the set of individuals in the population Ψ;
(3)Ω is a space of strategies from which an agent can select Ω
=
{
ω
1, ω
2
}
=
{
F
o
r
w
a
r
d
,
N
o
-
F
o
r
w
a
r
d
};
(4)U is the matrix of payoffs of all the participating individuals as shown in Table 6.Table 6
Payoff matrix.
Forward
No-Forward
Forward
P
R
T
+
P
R
C
+
W
-
2
C
P
R
T
+
W
-
2
C
-
L
No-Forward
P
R
C
+
R
D
-
C
-
C
+
R
D


## 5. Evolutionary Game Theory Based Packet Forwarding

### 5.1. ESSs of Packet Forwarding Game

The dynamic evolutionary process can be described by many different dynamic replicator models. There is a very widely used and famous dynamic replicator model proposed by Taylor and Jonker [27]. In the evolutionary game process, the dynamic game has two mechanisms of selection and mutation [28] and more agents will select the selection mechanism which gets higher fitness in the prior game. Agents will select the mutation mechanisms randomly. The mutation receiving higher fitness will be continuously selected by agents in the game; otherwise the mutation will be eliminated. The replicator equation describes how the frequencies of a certain strategy changes over time. The nonlinear differential equation is given as follows [29]:(13)
F
x
i
=
d
x
i
d
t
=
x
i
U
ω
i
,
X
-
U
X
,
X
,whereU
ω
i
,
X indicates the total expected payoff of agents selecting the pure strategy ω
i and U
(
X
,
X
) indicates the average payoff of the entire population Ψ. U
X
,
X
=
∑
i
=
1
k
x
i
U
ω
i
,
X, where k is the number of pure strategies.Equation (13) indicates that if the payoff of an agent selecting strategy ω
i is more than the average payoff, the number of agents selecting the strategy ω
i will increase and the converse is also true. If the payoff of an agent with strategy ω
i is equal to the average payoff, the number of agents selecting the strategy ω
i will stay the same. As time passes, the population will attain an evolutionarily stable strategy (ESS), which is an equilibrium refinement of the Nash equilibrium. The population attaining evolutionary stable states shows that natural selection alone is sufficient to prevent mutant strategies from successfully invading.We have two strategies in the packet forwarding game model; we denoteX
t
=
(
x
,
1
-
x
) as the mixed-strategy for the population Ψ at time t, where x is the rate of agents selectingForward strategy (i.e., ω
1) and 1
-
x is the rate of agents selectingNo-Forward strategy (i.e., ω
2). According to (13), the expected payoff of agents selectingForward strategy is(14)
U
ω
1
,
X
=
∑
j
=
1
2
x
j
a
1
j
=
x
P
R
T
+
P
R
C
+
W
-
2
C
+
1
-
x
P
R
T
+
W
-
2
C
-
L
,and the expected payoff of agents choosingNo-Forward strategy is(15)
U
ω
2
,
X
=
∑
j
=
1
2
x
j
a
2
j
=
x
P
R
C
+
R
D
-
C
+
1
-
x
-
C
+
R
D
.The average payoff of the entire population Ψ is as(16)
U
X
,
X
=
∑
i
=
1
2
x
i
U
ω
i
,
X
=
x
U
ω
1
,
X
+
1
-
x
U
ω
2
,
XTherefore, from (13) to (16), the dynamic replicator equation ofForward strategy is(17)
F
x
=
d
x
1
d
t
=
x
U
ω
1
,
X
-
U
X
,
X
=
x
1
-
x
x
P
R
T
+
W
-
C
-
R
D
+
1
-
x
P
R
T
+
W
-
C
-
R
D
-
L
.Setting (17) equal 0, there are three solutions of the equation:(18)
x
1
∗
=
0
,
x
2
∗
=
1
,
x
3
∗
=
C
+
R
D
+
L
-
P
R
T
-
W
L
,
0
<
x
3
∗
=
C
+
R
D
+
L
-
P
R
T
-
W
L
<
1
.Theorem 2.
IfP
R
T
+
W
-
C
-
R
D
-
L
<
0 and P
R
T
+
W
-
C
-
R
D
>
0, then x
1
∗
=
0 and x
2
∗
=
1 are ESSs of the packet forwarding game.Theorem 3.
IfP
R
T
+
W
-
C
-
R
D
-
L
>
0, then x
2
∗
=
1 is the only ESS of the packet forwarding game.Theorem 4.
IfP
R
T
+
W
-
C
-
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 ifx
∗ is a stable state, then F
′
(
x
∗
) must be less than 0.
Becausex
1
∗
=
0 and x
2
∗
=
1 are two solutions of (17), we have F
(
x
1
∗
)
=
0 and F
(
x
2
∗
)
=
0.
Taking the derivative on both sides of (17), we get(19)
F
′
x
=
1
-
2
x
L
x
+
P
R
T
+
W
-
C
-
R
D
-
L
+
L
x
1
-
x
,and taking x
1
∗
=
0 and x
2
∗
=
1 into (19), we obtain(20)
F
′
0
=
P
R
T
+
W
-
C
-
R
D
-
L
,
(21)
F
′
1
=
-
P
R
T
-
W
+
C
+
R
D
.When P
R
T
+
W
-
C
-
R
D
-
L
<
0 and P
R
T
+
W
-
C
-
R
D
>
0, we can obtain(22)
F
′
0
=
P
R
T
+
W
-
C
-
R
D
-
L
<
0
,
F
′
1
=
-
P
R
T
-
W
+
C
+
R
D
<
0
.
According to the stability theory of the differential equation,x
1
∗
=
0 and x
2
∗
=
1 are the ESSs of the packet forwarding game. Thus, Theorem 2 is proved.
WhenP
R
T
+
W
-
C
-
R
D
-
L
>
0, we get(23)
F
′
0
=
P
R
T
+
W
-
C
-
R
D
-
L
>
0
,
F
′
1
=
-
P
R
T
-
W
+
C
+
R
D
<
-
P
R
T
-
W
+
C
+
R
D
+
L
<
0
.According to the stability theory of the differential equation, x
1
∗
=
1 is the only ESS of the packet forwarding game. Thus, Theorem 3 is proved.
WhenP
R
T
+
W
-
C
-
R
D
<
0, we can get (24)
F
′
1
=
-
P
R
T
-
W
+
C
+
R
D
<
0
,
F
′
0
=
P
R
T
+
W
-
C
-
R
D
-
L
<
P
R
T
+
W
-
C
-
R
D
<
0
.According to the stability theory of the differential equation, x
1
∗
=
0 is the only ESS of the packet forwarding game. Thus, Theorem 4 is proved.Theorem 5.
x
3
∗
=
(
C
+
R
D
+
L
-
P
R
T
-
W
)
/
L is not the ESS of the packet forwarding game.Proof.
Supposex
3
∗
=
(
C
+
R
D
+
L
-
P
R
T
-
W
)
/
L is the ESS of the packet forwarding game; then F
′
x
3
∗
<
0.
From (19) F
′
x
3
∗
=
F
′
(
C
+
R
D
+
L
-
P
R
T
-
W
)
/
L
=
L
x
3
∗
1
-
x
3
∗,
and due to (18), 0
<
x
3
∗
=
(
C
+
R
D
+
L
-
P
R
T
-
W
)
/
L
<
1, so we get 0
<
x
3
∗, and 0
<
1
-
x
3
∗; then F
′
x
3
∗
=
L
x
3
∗
1
-
x
3
∗>0. This is a contradiction to the assumption, so x
3
∗
=
(
C
+
R
D
+
L
-
P
R
T
-
W
)
/
L is not the ESS of the packet forwarding game.Inference 6.
IfP
>
(
C
+
R
D
+
L
-
W
)
/
R
T, agents are more likely to selectForward strategy, and if P
<
(
C
+
R
D
-
W
)
/
R
T, agents are more likely to selectNo-Forward strategy.Proof.
IfP
>
(
C
+
R
D
+
L
-
W
)
/
R
T, we get P
R
T
+
W
-
C
-
R
D
-
L
>
0. Then, from Theorem 3, we get that x
2
∗
=
1 is the only ESS of the packet forwarding game and agents are more likely to selectForward strategy. The same can be proved if P
<
(
C
+
R
D
-
W
)
/
R
T; agents are more likely to selectNo-Forward strategy.Under the conditions of Theorem2, in the initial state when the rate of agents selectingForward strategy is greater than x
3
∗
=
(
C
+
R
D
+
L
-
P
R
T
-
W
)
/
L, the rate of agents selectingForward strategy will eventually converge to 100%, or the rate of agents selectingForward strategy will eventually converge to 0%.Under the conditions of Theorem3, whatever strategy agent B selects, the total payoff of agent A selecting theForward strategy is always higher than that of selecting theNo-Forward strategy. Regardless of what the initial rate of selecting a strategy is, the MASs will eventually attain a stable state, in which all the agents select theForward strategy after evolution.Under the conditions of Theorem4, whatever strategy agent B selects, the payoff of agent A selecting theNo-Forward strategy is always higher than that of selecting theForward strategy. No matter what the initial rate of selecting a certain strategy is, the MASs will eventually attain a stable state, in which all the agents select theNo-Forward strategy after evolution. Under this condition, the Nash equilibrium is harmful to network communication of MASs.Under the conditions of Theorem5, agent B selects a strategy with which the game cannot attain the steady state. In this case, the strategy is subjected to mutations and disturbances and cannot be restored to its original state; hence, it cannot be an evolutionary stable strategy.Under the conditions of Inference6, if P
>
(
C
+
R
D
+
L
-
W
)
/
R
T, all the agents will forward packets as much as possible and the MASs will eventually attain a stable state, and if P
<
(
C
+
R
D
-
W
)
/
R
T, the MASs will eventually attain a stable state while all the agents will selectNo-Forward strategy.


### 5.2. The Analysis of the Packet Forwarding Game Model

From Theorem3, if P
R
T
+
W
-
C
-
R
D
-
L
>
0, then x=1 is the only ESS of the evolutionary game in MASs. Under this certain communication environment, we set P to a constant value. By increasing either R
T or W, or by decreasing either C, R
D, or L in the formula, we can meet the condition of Theorem 3, which forces agents to avoid selecting theNo-Forwardstrategy. As the value of W is increased to meet the condition of Theorem 3 (regardless of which strategy the agents select in the initial state) all of the agents will finally selectForward strategy and the system will attain a stable state.In the case that an agent’s communication environment is backlogged and the agent selectsForward strategy too frequently, the agent’ time and energy will be wasted; therefore, selectingNo-Forward strategy is favorable in this case. We give the agent incentive R
D for selectingNo-Forward strategy.From (7), P is the average probability of packet forwarding, P
=
(
1
-
β
)
/
(
2
-
α
-
β
). If α or 1
-
β is increased, P is increased. The positive changing relations among α
,
1
-
β, and P can be shown in Figure 3.Figure 3
The positive changing relations amongα
,
1
-
β, and P.There are many ways to improve the probability of packet forwarding in MASs, such as increasing bandwidth or frequency, improving the hardware or the transmission protocol algorithm, etc. From Theorem3, if the value of P is increased to meet the conditions of Theorem 3, that is, P
R
T
+
W
-
C
-
R
D
-
L
>
0, then agents will increasingly selectForward strategy and the MASs will attain the stable state more quickly. In this case, if we increase P, it will not affect the final evolutionary stable state, but it will improve the rate of convergence to the evolutionary stable state. On the contrary, if the value of P is increased, it is hard to meet the condition of Theorem 4, that is, P
R
T
+
W
-
C
-
R
D
<
0; then the MASs will attain the stable state x
1
∗
=
0 slowly. In this case, if we increase P, it will not affect the final evolutionary stable state, but it will reduce the rate of convergence to the evolutionary stable state.


## 5.1. ESSs of Packet Forwarding Game

The dynamic evolutionary process can be described by many different dynamic replicator models. There is a very widely used and famous dynamic replicator model proposed by Taylor and Jonker [27]. In the evolutionary game process, the dynamic game has two mechanisms of selection and mutation [28] and more agents will select the selection mechanism which gets higher fitness in the prior game. Agents will select the mutation mechanisms randomly. The mutation receiving higher fitness will be continuously selected by agents in the game; otherwise the mutation will be eliminated. The replicator equation describes how the frequencies of a certain strategy changes over time. The nonlinear differential equation is given as follows [29]:(13)
F
x
i
=
d
x
i
d
t
=
x
i
U
ω
i
,
X
-
U
X
,
X
,whereU
ω
i
,
X indicates the total expected payoff of agents selecting the pure strategy ω
i and U
(
X
,
X
) indicates the average payoff of the entire population Ψ. U
X
,
X
=
∑
i
=
1
k
x
i
U
ω
i
,
X, where k is the number of pure strategies.Equation (13) indicates that if the payoff of an agent selecting strategy ω
i is more than the average payoff, the number of agents selecting the strategy ω
i will increase and the converse is also true. If the payoff of an agent with strategy ω
i is equal to the average payoff, the number of agents selecting the strategy ω
i will stay the same. As time passes, the population will attain an evolutionarily stable strategy (ESS), which is an equilibrium refinement of the Nash equilibrium. The population attaining evolutionary stable states shows that natural selection alone is sufficient to prevent mutant strategies from successfully invading.We have two strategies in the packet forwarding game model; we denoteX
t
=
(
x
,
1
-
x
) as the mixed-strategy for the population Ψ at time t, where x is the rate of agents selectingForward strategy (i.e., ω
1) and 1
-
x is the rate of agents selectingNo-Forward strategy (i.e., ω
2). According to (13), the expected payoff of agents selectingForward strategy is(14)
U
ω
1
,
X
=
∑
j
=
1
2
x
j
a
1
j
=
x
P
R
T
+
P
R
C
+
W
-
2
C
+
1
-
x
P
R
T
+
W
-
2
C
-
L
,and the expected payoff of agents choosingNo-Forward strategy is(15)
U
ω
2
,
X
=
∑
j
=
1
2
x
j
a
2
j
=
x
P
R
C
+
R
D
-
C
+
1
-
x
-
C
+
R
D
.The average payoff of the entire population Ψ is as(16)
U
X
,
X
=
∑
i
=
1
2
x
i
U
ω
i
,
X
=
x
U
ω
1
,
X
+
1
-
x
U
ω
2
,
XTherefore, from (13) to (16), the dynamic replicator equation ofForward strategy is(17)
F
x
=
d
x
1
d
t
=
x
U
ω
1
,
X
-
U
X
,
X
=
x
1
-
x
x
P
R
T
+
W
-
C
-
R
D
+
1
-
x
P
R
T
+
W
-
C
-
R
D
-
L
.Setting (17) equal 0, there are three solutions of the equation:(18)
x
1
∗
=
0
,
x
2
∗
=
1
,
x
3
∗
=
C
+
R
D
+
L
-
P
R
T
-
W
L
,
0
<
x
3
∗
=
C
+
R
D
+
L
-
P
R
T
-
W
L
<
1
.Theorem 2.
IfP
R
T
+
W
-
C
-
R
D
-
L
<
0 and P
R
T
+
W
-
C
-
R
D
>
0, then x
1
∗
=
0 and x
2
∗
=
1 are ESSs of the packet forwarding game.Theorem 3.
IfP
R
T
+
W
-
C
-
R
D
-
L
>
0, then x
2
∗
=
1 is the only ESS of the packet forwarding game.Theorem 4.
IfP
R
T
+
W
-
C
-
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 ifx
∗ is a stable state, then F
′
(
x
∗
) must be less than 0.
Becausex
1
∗
=
0 and x
2
∗
=
1 are two solutions of (17), we have F
(
x
1
∗
)
=
0 and F
(
x
2
∗
)
=
0.
Taking the derivative on both sides of (17), we get(19)
F
′
x
=
1
-
2
x
L
x
+
P
R
T
+
W
-
C
-
R
D
-
L
+
L
x
1
-
x
,and taking x
1
∗
=
0 and x
2
∗
=
1 into (19), we obtain(20)
F
′
0
=
P
R
T
+
W
-
C
-
R
D
-
L
,
(21)
F
′
1
=
-
P
R
T
-
W
+
C
+
R
D
.When P
R
T
+
W
-
C
-
R
D
-
L
<
0 and P
R
T
+
W
-
C
-
R
D
>
0, we can obtain(22)
F
′
0
=
P
R
T
+
W
-
C
-
R
D
-
L
<
0
,
F
′
1
=
-
P
R
T
-
W
+
C
+
R
D
<
0
.
According to the stability theory of the differential equation,x
1
∗
=
0 and x
2
∗
=
1 are the ESSs of the packet forwarding game. Thus, Theorem 2 is proved.
WhenP
R
T
+
W
-
C
-
R
D
-
L
>
0, we get(23)
F
′
0
=
P
R
T
+
W
-
C
-
R
D
-
L
>
0
,
F
′
1
=
-
P
R
T
-
W
+
C
+
R
D
<
-
P
R
T
-
W
+
C
+
R
D
+
L
<
0
.According to the stability theory of the differential equation, x
1
∗
=
1 is the only ESS of the packet forwarding game. Thus, Theorem 3 is proved.
WhenP
R
T
+
W
-
C
-
R
D
<
0, we can get (24)
F
′
1
=
-
P
R
T
-
W
+
C
+
R
D
<
0
,
F
′
0
=
P
R
T
+
W
-
C
-
R
D
-
L
<
P
R
T
+
W
-
C
-
R
D
<
0
.According to the stability theory of the differential equation, x
1
∗
=
0 is the only ESS of the packet forwarding game. Thus, Theorem 4 is proved.Theorem 5.
x
3
∗
=
(
C
+
R
D
+
L
-
P
R
T
-
W
)
/
L is not the ESS of the packet forwarding game.Proof.
Supposex
3
∗
=
(
C
+
R
D
+
L
-
P
R
T
-
W
)
/
L is the ESS of the packet forwarding game; then F
′
x
3
∗
<
0.
From (19) F
′
x
3
∗
=
F
′
(
C
+
R
D
+
L
-
P
R
T
-
W
)
/
L
=
L
x
3
∗
1
-
x
3
∗,
and due to (18), 0
<
x
3
∗
=
(
C
+
R
D
+
L
-
P
R
T
-
W
)
/
L
<
1, so we get 0
<
x
3
∗, and 0
<
1
-
x
3
∗; then F
′
x
3
∗
=
L
x
3
∗
1
-
x
3
∗>0. This is a contradiction to the assumption, so x
3
∗
=
(
C
+
R
D
+
L
-
P
R
T
-
W
)
/
L is not the ESS of the packet forwarding game.Inference 6.
IfP
>
(
C
+
R
D
+
L
-
W
)
/
R
T, agents are more likely to selectForward strategy, and if P
<
(
C
+
R
D
-
W
)
/
R
T, agents are more likely to selectNo-Forward strategy.Proof.
IfP
>
(
C
+
R
D
+
L
-
W
)
/
R
T, we get P
R
T
+
W
-
C
-
R
D
-
L
>
0. Then, from Theorem 3, we get that x
2
∗
=
1 is the only ESS of the packet forwarding game and agents are more likely to selectForward strategy. The same can be proved if P
<
(
C
+
R
D
-
W
)
/
R
T; agents are more likely to selectNo-Forward strategy.Under the conditions of Theorem2, in the initial state when the rate of agents selectingForward strategy is greater than x
3
∗
=
(
C
+
R
D
+
L
-
P
R
T
-
W
)
/
L, the rate of agents selectingForward strategy will eventually converge to 100%, or the rate of agents selectingForward strategy will eventually converge to 0%.Under the conditions of Theorem3, whatever strategy agent B selects, the total payoff of agent A selecting theForward strategy is always higher than that of selecting theNo-Forward strategy. Regardless of what the initial rate of selecting a strategy is, the MASs will eventually attain a stable state, in which all the agents select theForward strategy after evolution.Under the conditions of Theorem4, whatever strategy agent B selects, the payoff of agent A selecting theNo-Forward strategy is always higher than that of selecting theForward strategy. No matter what the initial rate of selecting a certain strategy is, the MASs will eventually attain a stable state, in which all the agents select theNo-Forward strategy after evolution. Under this condition, the Nash equilibrium is harmful to network communication of MASs.Under the conditions of Theorem5, agent B selects a strategy with which the game cannot attain the steady state. In this case, the strategy is subjected to mutations and disturbances and cannot be restored to its original state; hence, it cannot be an evolutionary stable strategy.Under the conditions of Inference6, if P
>
(
C
+
R
D
+
L
-
W
)
/
R
T, all the agents will forward packets as much as possible and the MASs will eventually attain a stable state, and if P
<
(
C
+
R
D
-
W
)
/
R
T, the MASs will eventually attain a stable state while all the agents will selectNo-Forward strategy.


## 5.2. The Analysis of the Packet Forwarding Game Model

From Theorem3, if P
R
T
+
W
-
C
-
R
D
-
L
>
0, then x=1 is the only ESS of the evolutionary game in MASs. Under this certain communication environment, we set P to a constant value. By increasing either R
T or W, or by decreasing either C, R
D, or L in the formula, we can meet the condition of Theorem 3, which forces agents to avoid selecting theNo-Forwardstrategy. As the value of W is increased to meet the condition of Theorem 3 (regardless of which strategy the agents select in the initial state) all of the agents will finally selectForward strategy and the system will attain a stable state.In the case that an agent’s communication environment is backlogged and the agent selectsForward strategy too frequently, the agent’ time and energy will be wasted; therefore, selectingNo-Forward strategy is favorable in this case. We give the agent incentive R
D for selectingNo-Forward strategy.From (7), P is the average probability of packet forwarding, P
=
(
1
-
β
)
/
(
2
-
α
-
β
). If α or 1
-
β is increased, P is increased. The positive changing relations among α
,
1
-
β, and P can be shown in Figure 3.Figure 3
The positive changing relations amongα
,
1
-
β, and P.There are many ways to improve the probability of packet forwarding in MASs, such as increasing bandwidth or frequency, improving the hardware or the transmission protocol algorithm, etc. From Theorem3, if the value of P is increased to meet the conditions of Theorem 3, that is, P
R
T
+
W
-
C
-
R
D
-
L
>
0, then agents will increasingly selectForward strategy and the MASs will attain the stable state more quickly. In this case, if we increase P, it will not affect the final evolutionary stable state, but it will improve the rate of convergence to the evolutionary stable state. On the contrary, if the value of P is increased, it is hard to meet the condition of Theorem 4, that is, P
R
T
+
W
-
C
-
R
D
<
0; then the MASs will attain the stable state x
1
∗
=
0 slowly. In this case, if we increase P, it will not affect the final evolutionary stable state, but it will reduce the rate of convergence to the evolutionary stable state.


## 6. Simulation Experiments

The experimental environment is MATLAB 2015a. The simulation experiments are divided into two parts.(1) The experiments in the first part are to verify the correctness of Theorems2–4.(2) The experiments in the second part are to confirm the effects of parametersW, R
D, and P.


### 6.1. Verification Experiment on Theorems2–4

We set parameters to meet the conditions of Theorems2–4 as shown in Table 7. The experimental results are shown in Figures 4–7, in which we can observe the changing trends of evolution curves of agents in MASs.Table 7
Experimental data (1).
Group number
Satisfy
P
R
T
R
D
C
L
W
Theorem
Group 1
Theorem2
0.8
12.5
5
7
3
4
Group 2
Theorem2
0.8
12.75
5
7
3
2.6
Group 3
Theorem3
0.8
15
5
7
3
2
Group 4
Theorem4
0.8
15
5
7
3
4
Group 5
Theorem5
0.8
5
1
3
2
1Figure 4
The evolution curves of the packet forwarding game (1).Figure 5
Evolution curves of the packet forwarding game (2).Figure 6
Evolution curves of the packet forwarding game (3).Figure 7
Evolution curves of the packet forwarding game (4).In Figure4, meeting the condition of Theorem 2, the parameters of two groups are related to the triangle curve with the critical point of 0.333 and the square curve with the critical point of 0.8. In the triangle curve, the value of (17) is initialized to 0.334. This denotes that 33.4% of the agents first selectForward strategy. The rate of agents selectingForward strategy is changed continuously. After playing the game approximately 30 times (triangle curve), all agents will eventually selectForward strategy. Furthermore, once the initial value of (17) is initialized by 0.332, the rate of agents selectingForward strategy will be fixed at 0% after playing the game approximately 40 times. This means all of the agents will eventually selectForward strategy. In the square curve, the initial value of (17) is initialized by 0.801 and 0.799. Experimental results confirm that when meeting the conditions of Theorem 2, both x
1
∗
=
0 and x
2
∗
=
1 are the ESSs of the packet forwarding game.In Figure5, the parameters of the third group meet the conditions of Theorem 3, and the values of (17) are initialized at 0.01 for the triangle curve, 0.02 for the square curve, and 0.03 for the star curve. When the rates of agents selectingForward strategy are 1%, 2%, or 3% in the initial state, after playing more than 120 times the rate of agents selectingForward strategy will be fixed at 100%. This means that all the agents will eventually selectForward strategy. Experimental results confirm that when meeting the conditions of Theorem 3, x
2
∗
=
1 is the only ESS of packet forwarding game.In Figure6, the parameters of the fourth group meet the conditions of Theorem 4, and the values of (17) are initialized at 0.9999 for the triangle curve, 0.97 for the star curve, and 0.8 for the square curve. When the rate of agents selectingForward strategy is 99.99%, 97%, or 80% in the initial state, after playing more than 70 times, the rate of agents selectingForward strategy will be fixed at 0%. This means that all the agents will eventually selectNo-Forward strategy. Experimental results confirm that when meeting the conditions of Theorem 4, x
1
∗
=
0 is the only ESS of packet forwarding game.In Figure7, the parameters of the fifth group meet the conditions of Theorem 5 and the value of (17) are initialized to 0.501 for the triangle curve, 0.5 for the square curve, and 0.499 for the vertical line curve. In the initial state, when the rate of agents selectingForward strategy is 50%, which is the correct critical point, we can see that the rate of agents selectingForward strategy cannot resist the small deviation from the disturbance and cannot converge to the state of stability. Therefore, Theorem 5 is verified.


### 6.2. Experiments on the Effect of Parameters

We set many groups of parameters to meet the conditions of related Theorems. Groups 1-6 vary the value ofW and keep the other parameters values constant. Groups 7-14 vary the value of R
D and keep the other parameters values constant. Groups 13-14 vary the value of P and keep the other parameters values constant. The details are shown in Table 8. We illustrate the effects on the evolutionary process by the cooperation incentive W, the noncooperation incentive R
D, and the probability of packet forwarding P. We observe the changing trends of evolution curves of agents in MASs.Table 8
Experimental data (2).
Group number
Satisfy
P
R
T
R
D
C
L
W
Theorem
Group 1
Theorem2
0.8
12.5
5
7
3
3
Group 2
Theorem2
0.8
12.5
5
7
3
4
Group 3
Theorem3
0.8
18
3
8
4
3
Group 4
Theorem3
0.8
18
3
8
4
4
Group 5
Theorem4
0.8
9
4
8
4
3
Group 6
Theorem4
0.8
9
4
8
4
4
Group 7
Theorem2
0.8
12.5
6
7
3
4
Group 8
Theorem2
0.8
12.5
5
7
3
4
Group 9
Theorem3
0.8
15
3
8
4
4
Group 10
Theorem3
0.8
15
4
8
4
4
Group 11
Theorem4
0.8
8
8
8
4
4
Group 12
Theorem4
0.8
8
3
8
4
4
Group 13
Theorem3
-
18
3
8
4
3
Group 14
Theorem4
-
9
0.8
4
4
5In Figures8–10, the curves show the effects on the evolutionary process of packet forwarding by the cooperation incentive W.Figure 8
Evolution curves of the packet forwarding in terms ofW(1).Figure 9
Evolution curves of the packet forwarding in terms ofW(2).Figure 10
Evolution curves of packet forwarding in terms ofW(3).In Figure8, we can see that the critical initial value of packet forwarding evolution of agents is 0.666 if W
=
3 and 0.333 if W
=
4. This means that although the rate of agents selectingForward strategy decreases from 66.6% to 33.3% as the value of W increases from 3 to 4, x
1
∗
=
0
,
x
2
∗
=
1 will still be the ESSs of the packet forwarding game of MASs.In Figure9, when the rate of agents selectingForward strategy is 1% in the initial state, it takes about 110 times of playing the game if W
=
3 to reach the stable point x
2
∗
=
1, but it only takes about 40 times if W
=
4 to reach the same stable point. We can see from Figure 9, meeting the conditions of Theorem 3, the cooperation incentive is bigger and the rate of the MASs attaining the ESS is faster.In Figure10, when the rate of agents selectingForward strategy is 99% in the initial state, it takes more than 100 times of playing the game if W
=
3 to reach the stable point x
1
∗
=
0, but it takes more than 80 times if W
=
4 to reach the same stable point. We can see from Figure 10, satisfying the conditions of Theorem 4, the gain of agents selectingForward strategy is less than that ofNo-Forward strategy. However, the cooperation incentive will promote agents to cooperate and forward packets to each other and, in turn, slow the rate of attaining the evolutionary stable state of MASs.In Figures11–13, the curves show the effects on the evolutionary process of packet forwarding by the noncooperation incentives R
D.Figure 11
Evolution curves of the packet forwarding in terms ofR
D(1).Figure 12
Evolution curves of the packet forwarding in terms ofR
D(2).Figure 13
Evolution curves of the packet forwarding in terms ofR
D(3).In Figure11, we can see that the critical initial value of packet forwarding evolution of agents is 0.333 if R
D
=
5, while it is 0.666 if R
D
=
6. This means that although the value of R
D is increased from 33.3% to 66.6%, x
1
∗
=
0 and x
2
∗
=
1 will still be the ESSs of the packet forwarding game of MASs.In Figure12, when the rate of agents selectingForward strategy is 1% in the initial state, it takes more than 30 times of playing the game if R
D
=
3 to reach the stable point x
2
∗
=
1 but more than 45 times if R
D
=
4 to reach the same stable point. We can see from Figure 12, meeting the conditions of Theorem 3, that the noncooperation incentive is greater and the rate of the MASs attaining the ESS is slower.In Figure13, when the rate of agents selectingForward strategy is 99% in the initial state, it takes more than 100 times of playing the game if R
D
=
3 to reach the stable point x
1
∗
=
0 but more than 80 times if R
D
=
8 to reach the same stable point. We can see from Figure 13, meeting the conditions of Theorem 4, that the noncooperation incentive is greater and the rate of the MASs attaining the ESS is faster.From Figures12 and 13 we can see, under the same conditions, that the incentive for noncooperation R
D can increase the game playing times to attain the evolutionary stable state x
2
∗
=
1 and reduce the game playing times to attain the evolutionary stable state x
1
∗
=
0 in MASs. Our original intention is not to set the parameter R
D. Most of the time, the communication environment of agents is at the busy (backlogged) state. In this case, if agents selectForward strategy too frequently, they will consume their own energy without effectiveness, so the agent’s selectingNo-Forward strategy is favorable. In order to promote the agents noncooperation to selectNo-Forward strategy for saving energy, we should set the value of R
D to be inversely proportional to P (the probability of packet forwarding) in a multiagent management system. When P is small, that is to say the packet forwarding is backlogged, more agents selectNo-Forward strategy and save energy. When the problem of backlogged packets is resolved, P becomes bigger. At this time, we want more agents to selectForward strategy to get more gain and keep the network communication normal. We set the threshold value δ
,
0
<
δ
<
1, showing whether the network communication is backlogged or not. When P
>
δ, the network communication is idle, so we set the function as follows:(25)
R
D
=
k
δ
-
P
+
b
,
where
k
>
0
,
b
>
0In Figures14 and 15, the curves show the effects on the evolutionary process of packet forwarding by the probability of packet forwarding P in MASs.Figure 14
Evolution curves of the packet forwarding in terms ofP(1).Figure 15
Evolution curve of the packet forwarding in terms ofP(2).In Figure14, the thirteenth group of parameters meet the conditions of Theorem 3 and the values of (17) are initialized to 0.1, for any P
∈
0,1. From the curves, we can see that the packet forwarding game evolution will eventually attain stable state x
2
∗
=
1. Adjusting the value of P will not affect the final evolutionary stability, but it will affect the rate of attaining the stable state. The higher the value of P, the faster the rate of attaining the evolutionary stability in MASs.In Figure15, the fourteenth group of parameters meet the conditions of Theorem 4 and the values of (17) are initialized to 0.99, for any P
∈
0,1. From the curves, we can see that the packet forwarding game eventually attains x
1
∗
=
0 stable state. Adjusting the value of P will not affect the final evolutionary stability, but it will affect the rate of attaining the stable state. The higher the value of P, the slower the rate of attaining the evolutionary stability in MASs.In Figure16, as P changes, the value R
D will change according to (25), and we set δ
=
1
/
2, k
=
4, and b
=
2. The other data are the same as the fourteenth group in Table 8. The data meets the conditions of Theorem 4. We set the initial ratio of selecting theForward strategy as 99%; from Figure 16, we can see that when the value of P becomes smaller than about 0.8, the values of R
D will increase. This will promote more agents to select theNo-Forward strategy and improve the rate of eventually attaining stable state x
1
∗
=
0. When the value of P increases to about 0.8, the network communication becomes good and agents will change their strategyNo-Forward toForward and the packet forwarding game eventually attains the x
2
∗
=
1 stable state, which agrees with our original idea to describe the parameter R
D by (25). When the network is busy (backlogged), the agents selectNo-Forward strategy to save energy, and when the network becomes idle, the agents will selectForwardstrategy to keep the communication normal.Figure 16
Evolution curves of the packet forwarding in terms of P with no constantR
D.


## 6.1. Verification Experiment on Theorems2–4

We set parameters to meet the conditions of Theorems2–4 as shown in Table 7. The experimental results are shown in Figures 4–7, in which we can observe the changing trends of evolution curves of agents in MASs.Table 7
Experimental data (1).
Group number
Satisfy
P
R
T
R
D
C
L
W
Theorem
Group 1
Theorem2
0.8
12.5
5
7
3
4
Group 2
Theorem2
0.8
12.75
5
7
3
2.6
Group 3
Theorem3
0.8
15
5
7
3
2
Group 4
Theorem4
0.8
15
5
7
3
4
Group 5
Theorem5
0.8
5
1
3
2
1Figure 4
The evolution curves of the packet forwarding game (1).Figure 5
Evolution curves of the packet forwarding game (2).Figure 6
Evolution curves of the packet forwarding game (3).Figure 7
Evolution curves of the packet forwarding game (4).In Figure4, meeting the condition of Theorem 2, the parameters of two groups are related to the triangle curve with the critical point of 0.333 and the square curve with the critical point of 0.8. In the triangle curve, the value of (17) is initialized to 0.334. This denotes that 33.4% of the agents first selectForward strategy. The rate of agents selectingForward strategy is changed continuously. After playing the game approximately 30 times (triangle curve), all agents will eventually selectForward strategy. Furthermore, once the initial value of (17) is initialized by 0.332, the rate of agents selectingForward strategy will be fixed at 0% after playing the game approximately 40 times. This means all of the agents will eventually selectForward strategy. In the square curve, the initial value of (17) is initialized by 0.801 and 0.799. Experimental results confirm that when meeting the conditions of Theorem 2, both x
1
∗
=
0 and x
2
∗
=
1 are the ESSs of the packet forwarding game.In Figure5, the parameters of the third group meet the conditions of Theorem 3, and the values of (17) are initialized at 0.01 for the triangle curve, 0.02 for the square curve, and 0.03 for the star curve. When the rates of agents selectingForward strategy are 1%, 2%, or 3% in the initial state, after playing more than 120 times the rate of agents selectingForward strategy will be fixed at 100%. This means that all the agents will eventually selectForward strategy. Experimental results confirm that when meeting the conditions of Theorem 3, x
2
∗
=
1 is the only ESS of packet forwarding game.In Figure6, the parameters of the fourth group meet the conditions of Theorem 4, and the values of (17) are initialized at 0.9999 for the triangle curve, 0.97 for the star curve, and 0.8 for the square curve. When the rate of agents selectingForward strategy is 99.99%, 97%, or 80% in the initial state, after playing more than 70 times, the rate of agents selectingForward strategy will be fixed at 0%. This means that all the agents will eventually selectNo-Forward strategy. Experimental results confirm that when meeting the conditions of Theorem 4, x
1
∗
=
0 is the only ESS of packet forwarding game.In Figure7, the parameters of the fifth group meet the conditions of Theorem 5 and the value of (17) are initialized to 0.501 for the triangle curve, 0.5 for the square curve, and 0.499 for the vertical line curve. In the initial state, when the rate of agents selectingForward strategy is 50%, which is the correct critical point, we can see that the rate of agents selectingForward strategy cannot resist the small deviation from the disturbance and cannot converge to the state of stability. Therefore, Theorem 5 is verified.


## 6.2. Experiments on the Effect of Parameters

We set many groups of parameters to meet the conditions of related Theorems. Groups 1-6 vary the value ofW and keep the other parameters values constant. Groups 7-14 vary the value of R
D and keep the other parameters values constant. Groups 13-14 vary the value of P and keep the other parameters values constant. The details are shown in Table 8. We illustrate the effects on the evolutionary process by the cooperation incentive W, the noncooperation incentive R
D, and the probability of packet forwarding P. We observe the changing trends of evolution curves of agents in MASs.Table 8
Experimental data (2).
Group number
Satisfy
P
R
T
R
D
C
L
W
Theorem
Group 1
Theorem2
0.8
12.5
5
7
3
3
Group 2
Theorem2
0.8
12.5
5
7
3
4
Group 3
Theorem3
0.8
18
3
8
4
3
Group 4
Theorem3
0.8
18
3
8
4
4
Group 5
Theorem4
0.8
9
4
8
4
3
Group 6
Theorem4
0.8
9
4
8
4
4
Group 7
Theorem2
0.8
12.5
6
7
3
4
Group 8
Theorem2
0.8
12.5
5
7
3
4
Group 9
Theorem3
0.8
15
3
8
4
4
Group 10
Theorem3
0.8
15
4
8
4
4
Group 11
Theorem4
0.8
8
8
8
4
4
Group 12
Theorem4
0.8
8
3
8
4
4
Group 13
Theorem3
-
18
3
8
4
3
Group 14
Theorem4
-
9
0.8
4
4
5In Figures8–10, the curves show the effects on the evolutionary process of packet forwarding by the cooperation incentive W.Figure 8
Evolution curves of the packet forwarding in terms ofW(1).Figure 9
Evolution curves of the packet forwarding in terms ofW(2).Figure 10
Evolution curves of packet forwarding in terms ofW(3).In Figure8, we can see that the critical initial value of packet forwarding evolution of agents is 0.666 if W
=
3 and 0.333 if W
=
4. This means that although the rate of agents selectingForward strategy decreases from 66.6% to 33.3% as the value of W increases from 3 to 4, x
1
∗
=
0
,
x
2
∗
=
1 will still be the ESSs of the packet forwarding game of MASs.In Figure9, when the rate of agents selectingForward strategy is 1% in the initial state, it takes about 110 times of playing the game if W
=
3 to reach the stable point x
2
∗
=
1, but it only takes about 40 times if W
=
4 to reach the same stable point. We can see from Figure 9, meeting the conditions of Theorem 3, the cooperation incentive is bigger and the rate of the MASs attaining the ESS is faster.In Figure10, when the rate of agents selectingForward strategy is 99% in the initial state, it takes more than 100 times of playing the game if W
=
3 to reach the stable point x
1
∗
=
0, but it takes more than 80 times if W
=
4 to reach the same stable point. We can see from Figure 10, satisfying the conditions of Theorem 4, the gain of agents selectingForward strategy is less than that ofNo-Forward strategy. However, the cooperation incentive will promote agents to cooperate and forward packets to each other and, in turn, slow the rate of attaining the evolutionary stable state of MASs.In Figures11–13, the curves show the effects on the evolutionary process of packet forwarding by the noncooperation incentives R
D.Figure 11
Evolution curves of the packet forwarding in terms ofR
D(1).Figure 12
Evolution curves of the packet forwarding in terms ofR
D(2).Figure 13
Evolution curves of the packet forwarding in terms ofR
D(3).In Figure11, we can see that the critical initial value of packet forwarding evolution of agents is 0.333 if R
D
=
5, while it is 0.666 if R
D
=
6. This means that although the value of R
D is increased from 33.3% to 66.6%, x
1
∗
=
0 and x
2
∗
=
1 will still be the ESSs of the packet forwarding game of MASs.In Figure12, when the rate of agents selectingForward strategy is 1% in the initial state, it takes more than 30 times of playing the game if R
D
=
3 to reach the stable point x
2
∗
=
1 but more than 45 times if R
D
=
4 to reach the same stable point. We can see from Figure 12, meeting the conditions of Theorem 3, that the noncooperation incentive is greater and the rate of the MASs attaining the ESS is slower.In Figure13, when the rate of agents selectingForward strategy is 99% in the initial state, it takes more than 100 times of playing the game if R
D
=
3 to reach the stable point x
1
∗
=
0 but more than 80 times if R
D
=
8 to reach the same stable point. We can see from Figure 13, meeting the conditions of Theorem 4, that the noncooperation incentive is greater and the rate of the MASs attaining the ESS is faster.From Figures12 and 13 we can see, under the same conditions, that the incentive for noncooperation R
D can increase the game playing times to attain the evolutionary stable state x
2
∗
=
1 and reduce the game playing times to attain the evolutionary stable state x
1
∗
=
0 in MASs. Our original intention is not to set the parameter R
D. Most of the time, the communication environment of agents is at the busy (backlogged) state. In this case, if agents selectForward strategy too frequently, they will consume their own energy without effectiveness, so the agent’s selectingNo-Forward strategy is favorable. In order to promote the agents noncooperation to selectNo-Forward strategy for saving energy, we should set the value of R
D to be inversely proportional to P (the probability of packet forwarding) in a multiagent management system. When P is small, that is to say the packet forwarding is backlogged, more agents selectNo-Forward strategy and save energy. When the problem of backlogged packets is resolved, P becomes bigger. At this time, we want more agents to selectForward strategy to get more gain and keep the network communication normal. We set the threshold value δ
,
0
<
δ
<
1, showing whether the network communication is backlogged or not. When P
>
δ, the network communication is idle, so we set the function as follows:(25)
R
D
=
k
δ
-
P
+
b
,
where
k
>
0
,
b
>
0In Figures14 and 15, the curves show the effects on the evolutionary process of packet forwarding by the probability of packet forwarding P in MASs.Figure 14
Evolution curves of the packet forwarding in terms ofP(1).Figure 15
Evolution curve of the packet forwarding in terms ofP(2).In Figure14, the thirteenth group of parameters meet the conditions of Theorem 3 and the values of (17) are initialized to 0.1, for any P
∈
0,1. From the curves, we can see that the packet forwarding game evolution will eventually attain stable state x
2
∗
=
1. Adjusting the value of P will not affect the final evolutionary stability, but it will affect the rate of attaining the stable state. The higher the value of P, the faster the rate of attaining the evolutionary stability in MASs.In Figure15, the fourteenth group of parameters meet the conditions of Theorem 4 and the values of (17) are initialized to 0.99, for any P
∈
0,1. From the curves, we can see that the packet forwarding game eventually attains x
1
∗
=
0 stable state. Adjusting the value of P will not affect the final evolutionary stability, but it will affect the rate of attaining the stable state. The higher the value of P, the slower the rate of attaining the evolutionary stability in MASs.In Figure16, as P changes, the value R
D will change according to (25), and we set δ
=
1
/
2, k
=
4, and b
=
2. The other data are the same as the fourteenth group in Table 8. The data meets the conditions of Theorem 4. We set the initial ratio of selecting theForward strategy as 99%; from Figure 16, we can see that when the value of P becomes smaller than about 0.8, the values of R
D will increase. This will promote more agents to select theNo-Forward strategy and improve the rate of eventually attaining stable state x
1
∗
=
0. When the value of P increases to about 0.8, the network communication becomes good and agents will change their strategyNo-Forward toForward and the packet forwarding game eventually attains the x
2
∗
=
1 stable state, which agrees with our original idea to describe the parameter R
D by (25). When the network is busy (backlogged), the agents selectNo-Forward strategy to save energy, and when the network becomes idle, the agents will selectForwardstrategy to keep the communication normal.Figure 16
Evolution curves of the packet forwarding in terms of P with no constantR
D.


## 7. Conclusion

The packet forwarding mechanism is an important aspect of intelligent task allocation and collaborative work research in MASs. In this paper, based on evolutionary game theory, we have studied packet forwarding strategy decisions and the evolutionary process. Considering the real network communication environment, we have explored the probability of packet forwarding while the agent is idle or busy (backlogged). While the agent is in a busy state, we have introduced a noncooperation incentive to encourage agents to select theNo-Forwardstrategy to save energy. Also, we have built a packet forwarding evolutionary game model in MASs. We have analyzed and proved the theorems indicating the conditions of attaining steady states and have analyzed the effects of the parameters on the rate of convergence to the ESSs. Lastly, the results of simulation experiments in MATLAB software have verified the effectiveness of the proposed theorems and the incentive mechanisms.We have established rules of packet forwarding decision-making in the process of dynamics evolution in MASs. In subsequent work, we can further study the relation between the value of noncooperation incentive of agents and the probability of agents in idle state. The packet forwarding strategy game model proposed provides a method of network safety.



---

*Source: 4965343-2018-07-08.xml*