Mixed and Continuous Strategy Monitor-Forward Game Based Selective Forwarding Solution in WSN

Abstract

Wireless sensor networks are often deployed in unattended and hostile environments. Due to the resource limitations and multihop communication in WSN, selective forwarding attacks launched by compromised insider nodes are a serious threat. A trust-based scheme for identifying and isolating malicious nodes is proposed and a mixed strategy and a continuous strategy Monitor-Forward game between the sender node and its one-hop neighboring node is constructed to mitigate the selective dropping attacks in WSN. The continuous game will mitigate false positives on packet dropping detection on unreliable wireless communication channel. Simulation results demonstrate that continuous Monitor-Forward game based selective forwarding solution is an efficient approach to identifying the selective forwarding attacks in WSN.

1. Introduction

Wireless sensor networks have been used in a wide range of applications such as military provision, environment monitoring, and man-unreachable circumstances [1–3]. Due to their shared medium, multihop relay, and lack of physical protection, nodes are vulnerable to various routing attacks, such as selective forwarding, black hole, wormhole, and sinkhole attacks. In these attacks, selective forwarding of packets [4] becomes an increasingly important concern as it is difficult to do with many current techniques in WSNs. As continuously misbehaving nodes in WSN will be distrusted and excluded from the network soon, a rational potential attacker will act normally most of the times, occasionally dropping packets. A number of literatures [5–9] are proposed to overcome this problem. However, this literalness focuses on cooperation among nodes in a WSN. In these researches, selfish nodes drop packets only to conserve their resources but not to damage the whole networks. References [10–21] proposed multipath schemes to eliminate the selective forwarding attack and enable energy to be balanced among these paths in a WSN. However, the adversary can overhear the communication between nodes in WSN and can modify routing control packets affecting the discovery of alternative paths and creating routing loops and dead ends. Multipath incurs more energy consumption than single-path routing. In particular, when a node is captured and compromised, all information of the node, including any security keys, becomes available to the attackers, and the adversary will have full control of the node. Game theory [22] is one of the effective mathematical methods to solve the attacker-defender interaction problems. And there is growing interest in using game to solve selective forwarding attack analysis problems. In [23], they analyze the collusion in selective forwarding attacks and propose a multiattacker repeated colluding game. They think the colluding attackers form a malicious group and the punishment to each colluding attacker is strongly related to the overall performance of this malicious group. In [24], the mixed strategy Nash equilibrium of the game provides the probability that the flooding packet would be forwarded by the receiver node. Here node i needs to make a decision whether to forward p or not. The number of players of the game is the number of nodes that receive p. Only a limited number of neighbors of the source node participate in forwarding. In [25], a stationary Markovian game model is utilized to optimize system performance in terms of throughput, delay, and power consumption cost. However, in Markov games, actions of players are determined based on the current state of the game, instead of considering the complete game history. In [26], they present a systematic study of collusion-resistant routing in noncooperative wireless ad hoc networks. In their model, each node in a path receives a payment from source node S for each forwarded packet. A central authority collects payments from the source node and guarantees secure distribution of payments to the forwarding nodes. And they assume that packet discarding and standby consume much less energy. However, this centralized mechanism and the above assumption are not suitable in WSN. Literature [27] proposed a generalized two-hop f-cast relay for packet routing, where f is replicated packet redundancy limit. They explore possible maximum throughput capacity of a node and determine the corresponding optimal setting of f to achieve it. Node's payoff is the achievable throughput capacity of its own traffic. And all nodes play the symmetric strategy profiles. Literature [6] proposes a model based on game theory and graph theory to investigate equilibrium conditions of packet forwarding strategies. In [28], they combine downstream assessments and end-to-end assessments to detect and mitigate collaborative Grey hole attacks. And a two-hop acknowledgment mechanism is integrated with forwarding assessments. However, in [6, 28], they assume the channel is error-free wireless and no per-link encryption. This does not meet the actual situation of most WSNs. In literature [29], they develop a channel aware detection (CAD) algorithm that can effectively identify the selective forwarding misbehavior from the normal channel losses. In [30], the authors proposed a packet forwarding framework based on each node's own past actions and its observation of other nodes. However, their objective is to maximize the node's own payoff, not to cause damage to other nodes. In literature [31], to obtain the trust value of the insider nodes along the route x, after every M data packets, the sender will generate a check packet and send it to destination node thought the route x. As this check packet passes through the route x, each insider node in x will attach its opinions about its upstream and downstream neighbors to the check packet. However, this mechanism cannot solve bad mouthing attack when nodes attach their opinions to the check packets. Selective dropping attack launched by insider node is still a problem that needs to be solved.

A repeated continuous noncooperative game based neighbor monitoring system to detect compromised nodes in selective forwarding attack in WSN is proposed in this paper. Based on the monitoring results, we can select more reliable cluster heads having sufficient residual energy and high trust level for data forwarding and data aggregation.

The rest of this paper is organized as follows. Game theory is introduced in Section 2. In Section 3, a mixed strategy Monitor-Forward game in WSN is constructed and simulated. In Section 4, a game with continuous strategy to mitigate false positives on packet dropping detection on unreliable wireless communication channel is constructed and simulated. Routing protocol without monitor mechanism and routing protocol with mixed strategy Monitor-Forward game and with continuous strategy Monitor-Forward game in a clustered WSN are all simulated and compared in Section 5. Finally, conclusions are drawn in Section 6.

2. Game Theory

Game theory is the study of problems of conflict and cooperation among independent decision-makers. Game theory is one of the effective mathematical methods to solve the attacker-defender interaction problems in WSN. In game theory, pure strategy means that the players choose strategies determinedly. However, in the real case, the rational node will change its strategy over time. In action decision of WSN, if the suspicious node $N_{s}$ always drops the packets, the attack will be detected quickly. If the monitoring node always monitors his neighbor node, too much energy will be consumed. As a result, rational suspicious node will selectively drop the packets it received with certain probability and pretends to be legitimate sometimes and the monitoring node will monitor its next hop node with certain probability also.

2.1. Mixed Strategy Nash Equilibrium

Mixed strategy allows a player to randomly select a pure strategy. We first construct the Monitor-Forward game as a mixed strategy game, in which the node's strategy is probability distribution over its pure strategy set. A pure strategy can be regarded as a degenerate case of a mixed strategy, in which that particular pure strategy is selected with probability 1 and every other strategy with probability 0.

A Nash equilibrium for a mixed strategy game is stable if a small change in probabilities for one player leads to a situation where two conditions hold: (i)

The player who did not change has no better strategy in the new circumstance.

(ii)

The player who did change is now playing with a strictly worse strategy.

2.2. Continuous Strategy Game

A continuous game allows more general sets of pure strategies, which may be uncountable infinite. It extends the notion of a discrete game, where the players choose from a finite set of pure strategies. In general, a game with uncountable infinite strategy sets will not necessarily have a Nash equilibrium solution. If, however, the strategy sets are required to be compact and the utility functions continuous, then a Nash equilibrium will be guaranteed.

The existence of a Nash equilibrium for any continuous game with continuous utility functions can be proven using Irving Glicksberg's generalization of the Kakutani fixed point theorem.

2.3. Repeated Game and QRE of a Repeated Game

In game theory, a repeated game is a special case of dynamic game which consists in some number of repetitions of some base game (called a stage game). It captures the idea that a player will have to take into account the impact of his current action on the future actions of other players; this is called his reputation.

The stage game in our repeated game in WSN is the 2-person games played by the suspicious node $N_{s}$ and the monitoring node $N_{m}$ . The formal definition is as follows.

Formal Definition. For G-period repeated game, at each period g, the moves during periods $1, \dots, g - 1$ are known to every player. Suppose δ is the discount factor. The total discounted payoff for each player is computed by

\begin{matrix} \sum_{g = 1}^{G} δ^{g - 1} U_{i} (g), \end{matrix}

(1)

where

U_{i} (g)

denotes the payoff to player i in period g.

If $G = \infty$ , the game is referred to as the infinitely repeated game. The average payoff to player i is then given by

\begin{matrix} {\bar{U}}_{i} = (1 - δ) \sum_{g = 1}^{\infty} δ^{g - 1} U_{i} (g) . \end{matrix}

(2)

In our model,

N_{m}

is player 1 and

N_{s}

is player 2. The player will get punishment from other players in the near future if it acts greedily. Therefore, the player (node

N_{m}

and node

N_{s}

) will focus more on the long-term overall utility than the one-shot utility on one stage of the game. From Folk Theorem, for an infinitely repeated game, if a feasible outcome gives each player better payoff, the Nash equilibrium can be obtained.

However, because of the limited energy of nodes in WSN, the Monitor-Forward game is indeed a random ended repeated Monitor-Forward game. Random repeated game is very different from finite games with definite end time in action or strategy choosing. But it is very similar to infinite games in strategy choosing. So, we can treat this game as infinite games in strategy analysis process.

In a multiround repeated game, the nodes will focus more on the long-term overall utility. Since the game is ended randomly, node's lifetime which is decided by the residual battery energy is important in the strategy choosing. Suppose ω denotes how long the suspicious node and monitoring node believe the repeated Monitor-Forward game will last. ω is denoted by a real number that lies in the interval $(0,1)$ . $ω_{0}$ is a threshold in the interval $(0,1)$ . In each stage of the repeated game, (1)

if $ω > ω_{0}$ —that is, the suspicious node $N_{s}$ and the monitoring node $N_{m}$ believe that the game will repeat for many stages—each node will always choose its mixed strategy based Nash equilibrium $x_{m}^{*}$ , $x_{s}^{*}$ to maximize the long-term overall utility in the future.

(2)

if $ω < ω_{0}$ , we think the residual battery energy of monitoring node $N_{m}$ or $N_{s}$ is not enough and Cluster Rotation Algorithm will be executed soon. To maximize its profit, $N_{s}$ will be violated from the Nash equilibrium strategy and choose to drop the packet fearlessly to maximize its one-shot utility in the current stage.

2.4. Quantal Response Equilibrium

With the Monitor-Forward game repeats, the nodes obtains more and more information of the other's misbehavior. We can obtain the Quantal response equilibrium (QRE) by utilizing the method in [32]. Players make choices based on a quantal-choice model and assume other players do so as well.

Quantal response equilibrium (QRE) is a solution concept in game theory. First introduced by Richard McKelvey and Thomas Palfrey, it provides an equilibrium notion with bounded rationality. In a quantal response equilibrium, players are assumed to make errors in choosing which pure strategy to play. The probability of any particular strategy being chosen is positively related to the payoff from that strategy. Quantal responses are smoothed-out best responses, in the sense that players are more likely to choose better strategies than worse strategies but do not play a best response with a probability one.

By far the most common specification for QRE is logit equilibrium (LQRE) [32]. In a logit equilibrium, player's strategies are chosen according to the probability distribution:

\begin{matrix} P_{i j} = \frac{\exp (λ E U_{i j} (P_{- i}))}{\sum_{k} \exp (λ E U_{i k} (P_{- i}))}, \end{matrix}

(3)

where

(i)

$P_{i j}$ is the probability of player i choosing strategy j;

(ii)

$E U_{i j} (P_{- i})$ is the expected utility to player i of choosing strategy j given other players are playing according to the probability distribution $P_{- i}$ ;

(iii)

λ is a rationality parameter which is nonnegative (sometimes written as $1 / μ$ ). As $λ \to 0$ , players become “completely irrational” and play each strategy with equal probability. As $λ \to \infty$ , players become “perfectly rational” and play approaches a Nash equilibrium. So LQRE will always be at least as good a fit as Nash equilibrium. Changes in the parameter can result in large changes to equilibrium behavior.

3. Mixed Strategy Game Based Monitoring Mechanism in WSN

3.1. A Monitoring Based Trust System

In WSNs, compromised nodes have legitimately registered into the network and the attackers can bypass the public key and private key system. A reputation-based trust system which maintains information about nodes' history behaviors is a necessary complement to the existing security mechanism.

Trust is a particular level of the subjective probability with which an agent assesses another node in a context such as data integrity, honesty, and packet forwarding. In this paper, we suppose that in a clustered wireless sensor network, the cluster heads aggregate and compress the data from the sensor nodes in the cluster and forward it to its next-hop cluster head or the base station and only the trust on selective forwarding context is considered in the Monitor-Forward game. Cluster heads are also in charge of trust values on data reliability of sensor nodes in these clusters. A distributed watch dog runs on every cluster head in WSN to monitor and record the packet forwarding behaviors of its next hop cluster head in the route to destination. Each cluster head node in WSN maintains its own neighbor set $N_{S}$ and a set of neighbor nodes towards the sink FN. FN is a subset of $N_{S}$ . It will select a node in FN with highest trust value on packet forwarding. If the suspicious node forwards the packet correctly, its trust value stored in the monitoring node will increase. Nodes with low trust value will then be excluded from the network. Node transceivers are supposed to be omnidirectional and neighboring overhearing is feasible in our model.

Each cluster head executes the trust model by monitoring its neighboring nodes' participation in the packet forwarding mechanism. If the node forwards the packet, it confirms that the node has acted in a benevolent manner and so its direct trust counter is incremented. If the forwarding node does not transmit the packet, its corresponding direct trust measure is decremented. In [33], after transmitting the packet, sending node must wait a trust update interval until the time it overhears the retransmission by its neighbor or the trust update interval has expired. This interval is related to the mobility and traffic of the network and can be set accordingly. If during the TUI the node is able to overhear its neighboring node retransmit the same packet, the sending node increases the trust value for that neighbor. In case no retransmission is heard and a time-out occurs when the TUI expires, the trust value for that neighbor is decremented. However, after transmitting the packet, the persistent monitoring of sending node would cost too much energy. In order to solve this problem, we propose a low cost game based monitoring mechanism to detect the compromised node.

3.2. A Monitor-Forward Game Based Monitoring Mechanism in WSN

In WSN, the sensor node consumes power for sensing, communicating, and data processing. More energy is required for communication than any other process. The transceiver of a node has four operational states that are transmit, receive, idle, and sleep. Most transceivers operating in idle mode consume almost equal power to operate in receive mode [34]. Thus, in a lot of literature, the transceiver is completely shut down when it is not transmitting or receiving rather than being in the idle or listening mode. In [33], to monitor the neighbor node, after transmitting the packet, sending node will not go to sleep but waits a trust update interval until it overhears the retransmission by its neighbor or the trust update interval has expired. However, if the trust update interval is too short, the transmission of its neighbor will be missed; if trust update interval is long, the persistent monitoring of node will cost a lot of energy.

By traffic analysis and statistical analysis executed in end nodes of a path [35], we can detects anomalies in network traffic and calculate probability of occurrence of attack on the path. However, which node in this path is malicious is not known. Nodes with monitoring mechanism can detect selective dropping attack of their neighboring node.

3.3. Formal Definition of the Game

The formal definition of the game is as follows.

Definition 1.

Let $G = 〈N, S, f〉$ be a game with two nodes in which (i)

$N = {N_{m}, N_{s}}$ is the set of players, where $N_{m}$ denotes the monitoring node and $N_{s}$ denotes the suspicious node;

(ii)

$S_{m}$ denotes the strategy set for the monitoring node;

(iii)

$S_{s}$ denotes the strategy set for the suspicious node;

(iv)

$S = S_{m} \times S_{s}$ is the set of strategy profiles of the game;

(v)

$f = (f_{m} (x), f_{s} (x))$ is the payoff function for $x \in S$ , where $x = (x_{m}, x_{s})$ , $x_{m} \in S_{m}$ , and $x_{s} \in S_{s}$ .

Let

x_{m}

be a strategy profile of node

N_{m}

and let

x_{s}

be a strategy profile of node

N_{s}

. Node

N_{m}

will obtain payoff

f_{m} (x)

when it chooses strategy

x_{m}

and

N_{s}

chooses strategy

x_{s}

resulting in strategy profile

x = (x_{m}, x_{s})

A strategy profile $x^{*} \in S$ is a Nash equilibrium (NE) if each rational node selects its best possible response to the other node's strategies provided that neither node can increase its utility by unilaterally changing its own strategy. That is,

\begin{matrix} f_{m} (x_{m}^{*}, x_{s}^{*}) \geq f_{m} (x_{m}^{}, x_{s}^{*}) x_{m} \in S_{m}, \\ f_{s} (x_{s}^{*}, x_{m}^{*}) \geq f_{s} (x_{s}^{}, x_{m}^{*}) x_{s} \in S_{s} . \end{matrix}

(4)

By traffic analysis and statistical analysis executed in end nodes of a path [36], we can detect anomalies in network traffic and calculate probability of occurrence of attack on the path. However, if the neighboring node forwards the packet to its coconspirators, monitoring mechanism without collusion considering will not detect this attack. Thus, nodes with normal reputation in a path whose attack probability is greater than a certain threshold will use two-stage dynamic game with collusion considering.

Considering the larger cost of collusion attack monitoring, the nodes in the path whose attack probability is below the threshold will play a simpler static game without collusion considering. We begin with the simpler Monitor-Forward game without collusion considering.

3.4. Pure Strategies Set of the Game

The static Monitor-Forward game without collusion considering is a simultaneous game. In this game, each player has a finite number of pure strategies. The suspicious node $N_{s}$ has two strategies: Forward Packet (F) and Drop Packet (D). That is to say, the strategies set of $N_{s} : S_{s} = {F, D}$ . The monitoring node $N_{m}$ has two strategies: Listen L time (L) and go to Sleep (S). The strategies set of $N_{m} : S_{m} = {L, S}$ , where L is the length of monitoring time. We set L which is equal to the average round-trip time (RTT) of one hop distance in WSN.

3.5. Mixed Strategy Nash Equilibrium of the Monitor-Forward Game

Suppose in this mixed strategy game the suspicious node's strategy is a probability distribution ${p, 1 - p}$ over its possible action set ${F, D}$ . Variables $p, 1 - p$ are the probabilities for the suspicious node adopting Forward Packet $(F)$ and Drop Packet $(D)$ , respectively. On the contrary, for the monitoring node, its strategy is a probability distribution ${h, 1 - h}$ , over its action set ${M, S}$ . Here $h, 1 - h$ are the probabilities of the monitoring node to adopt strategy Monitor L time $(M)$ and Sleep $(S)$ , respectively.

The payoff matrix of the game is shown in Table 1. In each cell of the matrix, the first number represents the payoff to the monitoring node, and the second number represents the payoff to the suspicious node.

Table 1

The payoff matrix of the static game.

	$N_{s}$ : F	$N_{s}$ : D
$N_{m}$ : M	$- l \cdot E_{monitor} + E_{forward}$ , $- E_{forward} + {l E}_{monitor}$	$C - l \cdot E_{monitor}$ , ${l E}_{monitor} - B$

$N_{m}$ : S	$E_{forward}$ , $- E_{forward}$	$- B$ , C

We define $E_{m o n i t o r}$ to be the battery power consumption of $N_{m}$ to monitor its next hop node $N_{s}$ for one RTT and l to be the multiple of average RTT of one hop transmission in WSN. Here, we set $l = 1$ . Define $E_{f o r w a r d}$ to be the energy consumption of $N_{s}$ to forward the packet it received to its next hop; B to be the punishment for the dropping packet of the $N_{s}$ , and C to be the adversary reward which means the suspicious node's illegal gain from the adversary of the network which has compromised these inside attackers. Generally, set $B > C$ .

The utility $Q_{m m}$ received by the monitoring node $N_{m}$ when it chooses monitoring strategy is as follows:

\begin{matrix} Q_{m m} = p (- l \cdot E_{m o n i t o r} + E_{f o r w a r d}) + (1 - p) (C - l \cdot E_{m o n i t o r}) . \end{matrix}

(5)

The utility received by the monitoring node when it chooses to sleep after transmitting is denoted by

Q_{m s}

\begin{matrix} Q_{m s} = p (E_{f o r w a r d}) + (1 - p) (- B) . \end{matrix}

(6)

Let

Q_{m s} = Q_{m m}

; we can obtain the value of p.

Similarly, the utility $Q_{S F}$ received by the suspicious node $N_{s}$ if it forwards received packet is as follows:

\begin{matrix} Q_{S F} = q (- E_{f o r w a r d} + l E_{m o n i t o r}) + (1 - q) (- E_{f o r w a r d}) . \end{matrix}

(7)

The utility received by the suspicious node if it drops its received packet is

\begin{matrix} Q_{S D} = q (l E_{m o n i t o r} - B) + (1 - q) (C) . \end{matrix}

(8)

Let

Q_{S F} = Q_{S D}

; q can be derived.

The mixed strategy allows a player to randomly select a pure strategy. And the Nash equilibrium of the game indicates the outcome in which neither suspicious node nor the monitoring node wants to unilaterally change its strategy.

3.6. Result of Simulation

As we have known, l is the multiple of average RTT of one hop transmission in WSN and we suppose $l = 1$ in the static game. For simplicity, we set $E_{m o n i t o r} = 2$ ; $E_{f o r w a r d} = 1$ . Figure 1 shows the payoff matrix of the Monitor-Forward game.

Figure 1

Payoff matrix the Monitor-Forward game.

Figure 1(a) shows the payoff matrix with $B = 1$ and $C = 2$ .

The Nash equilibrium is as follows:

$N_{m} : {h, 1 - h} = {1.00000,0.00000}$ . Expected payoffs = 0.

$N_{s} : {p, 1 - p} = {0.00000,1.00000}$ . Expected payoffs = 1.0.

Figure 1(b) shows the payoff matrix with

B = 4

and

C = 5

The Nash equilibrium is as follows:

The mixed strategy of $N_{m}$ is ${h, 1 - h} = {0.85714,0.14286}$ . Its expected payoffs = 1.0.

The mixed strategy of $N_{s}$ is ${p, 1 - p} = {1.0000,0.0000}$ . Its expected payoffs = −1.0.

If we set

B = C = 5

, the loss of the suspicious node is the same as the gain of the monitoring nodes; we call this game is a zero-sum game.

Figure 1(c) shows the payoff matrix with $B = C = 5$ . This is a zero-sum game too.

The Nash equilibrium is as follows:

$N_{m} : {h, 1 - h} = {0.7500,0.2500}$ . Expected payoffs = 1.0.

$N_{s} : {p, 1 - p} = {1.0000,0.0000}$ . Expected payoffs = −1.0.

Figure 1(d) shows the payoff matrix with

B = 7

and

C = 5

The Nash equilibrium is as follows:

$N_{m} : {h, 1 - h} = {0.6000,0.4000}$ . Expected payoffs = 1.0.

$N_{s} : {p, 1 - p} = {1.0000,0.0000}$ . Expected payoffs = −1.0.

From the above simulation results, we can see that higher punishment B will lead to smaller monitoring probability of the monitoring node

N_{m}

and smaller expected payoffs of the suspicious node

N_{s}

. However, in the real case, packet loss, data corruption, and variable propagation delays will lead to large amounts of false positives on packet dropping detection that rely on strict timing. Thus, too large B is not suitable for the unreliable wireless communication channel in WSN. The parameter setting should take the real-time channel quality into account. A balance between the severe punishment and avoiding false positives on packet dropping detection is needed.

3.7. QRE Simulation Result of the Repeated Game

We conducted an experiment with $E_{m o n i t o r} = 2$ , $E_{f o r w a r d} = 1$ , $l = 1$ , $B = 5$ , and $C = 5$ , where nodes played the Monitor-Forward game without collusion consideration illustrated in Figure 1(c); the QRE of repeated game is shown in Figure 2.

Figure 2

QRE of repeated game with $B = 5$ and $C = 5$ .

The experiment parameters are $E_{m o n i t o r} = 2$ , $E_{f o r w a r d} = 1$ , $l = 1$ , $B = 7$ , and $C = 5$ , where nodes played the Monitor-Forward game without collusion consideration illustrated in Figure 1(d) firstly. The QRE of the repeated game is shown in Figure 3.

Figure 3

QRE of repeated game with $B = 7$ and $C = 5$ .

By using the method described in detail in [32], we can obtain predicted frequencies of moves at each information set for any parameter, λ, of the AQRE model. Given a data set from the particular experimental game, the estimate, $\hat{λ}$ , is the value of λ that maximizes the likelihood of that data set.

4. Continuous Strategy Monitor-Forward Game in WSN

4.1. Unreliable Communication Channel

Because of the unreliable wireless communication channel in WSN, packet loss, data corruption, and variable propagation delays will lead to large amounts of false positives on packet dropping detection that rely on strict timing. Normal loss events such as medium access collision or bad channel quality will lead to normal loss rates which are not caused by malicious act. The normal loss rates $p_{i}$ can be computed by the following formula:

\begin{matrix} p_{i} = p_{b} + p_{m} - p_{b} \cdot p_{m}, \end{matrix}

(9)

where

p_{m}

denotes the packet loss rate due to bad channel quality and

p_{b}

denotes the packet loss rate due to medium access collisions. The detail computing of

p_{m}

and

p_{b}

can be found in literature [37]. Nodes may be considered to be compromised due to a packet propagation delay or normal packets loss. However, if the monitoring time is set as twice the RTT or longer, the power consumption will be significant. So, we construct a continuous game which allows players to choose a strategy from a continuous strategy set. Monitoring node has numerous possible actions to choose from in this continuous game.

4.2. Continuous Monitor-Forward Game in WSN

As previously mentioned, a mixed strategy Nash equilibrium is equilibrium where at least one player is playing a mixed strategy. In the continuous Monitor-Forward game $G = 〈N, S, f〉$ , suspicious node $N_{s}$ has two pure strategies: Forward Packet (F) and Drop Packet (D). That is to say, the strategies set of $N_{s}$ is $S_{s} = {F, D}$ . The monitoring node $N_{m}$ 's strategy is monitoring $l T$ time which is denoted by $M (l T)$ , where $M (l T)$ is continuous strategy. T denotes the average round-trip time (RTT) of one hop distance in WSN and l is the multiple of RTT. $l \in [0, k]$ , where K is the upper limit of l.

We should take into account of normal packet losses due to poor channel quality and medium access collisions by setting different k in the Monitor-Forward game. As wireless loss probability due to bad channel quality varies with the network status changing, k is dynamically adjusted with the normal loss rates in the game every time the game is played.

By the continuous game theory, we know that the utility functions of a player with continuous strategy are often expressed by a quadratic equation of a variable. As $E_{m o n i t o r}$ is the energy consumption of node $N_{S}$ monitoring its next hop last for one RTT, the utility of node $N_{m}$ due to monitoring is $- l^{2} * E_{m o n i t o r}$ . If $N_{s}$ forwarded the packet, node $N_{m}$ will gain $E_{f o r w a r d} * l$ , which is lost by node $N_{S}$ . If $N_{s}$ dropped the packet, node $N_{m}$ will punish $N_{s}$ with B and $N_{s}$ will obtain C from the opponent of $N_{m}$ . The gain of node $N_{m}$ from the punishment is in direct proportion to $l^{2} / k$ and the utility of $N_{m}$ from its opponent's award to $N_{s}$ is $C * k$ . So, we can define the utility function $f_{m} (x)$ , which is $f_{m} (x_{m}, x_{s})$ , of the monitoring node $N_{m}$ as

\begin{matrix} f_{m} = - l^{2} E_{m o n i t o r} + p \cdot (E_{f o r w a r d}) \cdot l + (1 - p) \cdot (\frac{{B \cdot l}^{2}}{k} - C \cdot k), \end{matrix}

(10)

where variables p,

1 - p

are the probabilities for the suspicious node adopting Forward Packet

(F)

and Drop Packet

(D)

, respectively. As we can see from this formula, the gain for monitoring is in proportion to the length of monitoring time l and the loss for short monitoring is in inverse proportion to l. When

l \to k

, we think the false positives on packet dropping detection are negligible;

B \cdot l^{2} / k \to B

Define the utility functions $f_{s} (x_{m}, x_{s})$ of $N_{s}$ as

\begin{matrix} f_{s} = \{\begin{cases} l^{2} E_{m o n i t o r} - \frac{B \cdot l^{2}}{k} + C \cdot k & x_{s} = D \\ - l E_{f o r w a r d} + l^{2} E_{m o n i t o r} & x_{s} = F . \end{cases} \end{matrix}

(11)

4.3. Best Response Function of the Continuous Game

A best response is the point at which each player in a game has selected the best response (or one of the best responses) to the other players' strategies.

To achieve a strategy Nash equilibrium, set

\begin{matrix} p \cdot E_{f o r w a r d} + (1 - p) \cdot C = - l E_{m o n i t o r} + p (E_{f o r w a r d}) + (1 - p) (\frac{B \cdot l}{k} - C \cdot (k - l)) \\ l E_{m o n i t o r} - \frac{B \cdot l}{k} + C \cdot (k - l) = - E_{f o r w a r d} + l E_{m o n i t o r} . \end{matrix}

(12)

In this continuous game, the best response of $N_{m}$ to $N_{s}$ 's strategies is setting monitoring time l which meets $f_{m} = \max (f_{m})$ and this can be substituted into its maximization problem.

We have known that

\begin{matrix} f_{m} = - l^{2} E_{m o n i t o r} + p \cdot (E_{f o r w a r d}) \cdot l + (1 - p) \cdot (\frac{B \cdot l^{2}}{k} - C \cdot k) . \end{matrix}

(13)

Then,

\begin{matrix} \max (f_{m} (l)) = \max ((- E_{m o n i t o r} + \frac{B}{k} - \frac{B \cdot p}{k}) \cdot l^{2} - (1 - p) C \cdot k + p \cdot E_{f o r w a r d} \cdot l) . \end{matrix}

(14)

For fixed p, if

- E_{m o n i t o r} + B / k - B \cdot p / k \geq 0

—that is,

p \leq 1 - E_{m o n i t o r} \cdot k / B — N_{m}

's best response is

l = k

If $p > 1 - E_{m o n i t o r} \cdot k / B$ , set the first partial derivative of the payoff function to be equal to zero with respect to $N_{m}$ 's strategy variable l:

\begin{matrix} \frac{\partial f_{m}}{\partial l} = 2 (- E_{m o n i t o r} + \frac{B}{k} - \frac{B \cdot p}{k}) \cdot l + p \cdot E_{f o r w a r d} = 0 . \end{matrix}

(15)

And we can find that

N_{m}

's best response function is

\begin{matrix} l (p) = \frac{(p \cdot E_{f o r w a r d})}{(2 * (E_{m o n i t o r} - B / k + B \cdot p / k))} . \end{matrix}

(16)

For

N_{s}

which have two discrete strategies, set

f_{s} (D) = f_{s} (F)

. That is,

\begin{matrix} l^{2} E_{m o n i t o r} - \frac{B \cdot l^{2}}{k} + C \cdot k = - l E_{f o r w a r d} + l^{2} E_{m o n i t o r}, l > 0 . \end{matrix}

(17)

Solve this equation:

\begin{matrix} l^{*} = \frac{(k \cdot (E_{f o r w a r d} + \sqrt{E_{f o r w a r d}^{2} + 4 \cdot B \cdot C}))}{(2 \cdot B)} . \end{matrix}

(18)

Feeding

l^{*}

into

N_{m}

's best response function, (

l^{*}, p^{*}

) is the Nash equilibrium of this continuous game.

4.4. Simulation of the Continuous Monitor-Forward Game

In this continuous game, we have known that $f_{m} = - l^{2} E_{m o n i t o r} + p \cdot (E_{f o r w a r d}) \cdot l + (1 - p) \cdot (B \cdot l^{2} / k - C \cdot k)$ . Set $E_{m o n i t o r} = 2$ , $E_{f o r w a r d} = 1$ , $B = 7$ , $C = 5$ , and $k = 2$ ; The payoff function of the monitoring node $N_{m}$ is illustrated as in Figure 4. $N_{m}$ 's payoff (in the y-axis) is a function of the length of monitoring time l that $N_{m}$ last (in the x-axis). Figures 4(a)–4(d) graphs this payoff function of $N_{m}$ on different forward probability p of the suspicious node $N_{s}$ to its next hop.

Figure 4

The payoff function of $N_{m}$ with continuous strategy.

$N_{m}$ 's best response function $l (p) = (p \cdot E_{f o r w a r d}) / (2 * (E_{m o n i t o r} - B / k + B \cdot p / k))$ is shown in Figure 5. The line in Figure 5 shows the length of monitoring time l that $N_{m}$ last (in the y-axis), as a function of the probability that $N_{s}$ plays “Forward” (shown in the x-axis).

Figure 5

$N_{m}$ 's best response to the probability p that $N_{s}$ plays “Forward”.

By setting $f_{s} (D) = f_{s} (F)$ , we can obtain

\begin{matrix} l^{*} = \frac{(k \cdot (E_{f o r w a r d} + \sqrt{E_{f o r w a r d}^{2} + 4 \cdot B \cdot C}))}{(2 \cdot B)} = 1.8392 . \end{matrix}

(19)

Feeding

l^{*}

into

N_{m}

's best response function,

(l^{*}, p^{*}) = (1.8392,0.4647)

is the Nash equilibrium of the continuous game.

As we can see, if the punishment B is small, the game will result in an equilibrium with low forward probability p of $N_{s}$ .

5. Simulation of a Routing Protocol with Monitor-Forward Game in a Clustered WSN

5.1. Simulation Setup

The routing protocol with mixed strategy Monitor-Forward game (MSMFM) and routing protocol with continuous strategy Monitor-Forward Game (CSMFM) are simulated in various setups using Matlab. 100 nodes are randomly distributed in an area of 100-by-100 meters and the base station is set in the center of the area.

Initial energy of each node is set to 0.5 joules. The election probability of a node to become cluster head is 0.1. The battery power consumption of $N_{m}$ to monitor its next hop node $N_{s}$ for one RTT is $E_{m o n i t o r} = 0.0000001$ joules. The energy consumption of $N_{s}$ to forward the packet it received to its next hop is $E_{f o r w a r d} = 0.00000005$ joules. The punishment B for the dropping packet of $N_{s}$ is set to 0.00000035 and the suspicious node's illegal gain C from the adversary of the network which has compromised inside attackers is 0.00000025. The game is repeated 9999 rounds. The traffic is generated randomly.

5.2. Simulation Numerical Analysis

The initial deployment of the routing protocol without monitor mechanism (WMM) is shown as in Figure 6(a). 100 nodes are randomly distributed in an area of 100-by-100 meters and the base station is set in the center of the area. r denotes the packet transmitting round in WSN. As we can see in Figure 6, the first node died in the round $r = 999$ and all nodes in the area died in the round $r = 4500$ .

Figure 6

The initial deployment and lifetime of WMM.

In the ideal case without normal loss, 15% of the cluster head nodes are randomly chosen as selective dropping attackers in the forwarding paths between source and destination pairs. The network lifetime using different protocols is illustrated in Figure 7.

Figure 7

Lifetime of the network.

The simulation results indicate that lifetimes of networks using MSMFM and CSMFM are shorter than WMM as they have monitor mechanism which consumes much energy. Compared with MSMFM, CSMFM which use continuous strategy extends the lifetime of the network, delays the first node's death time, and enhances the energy efficiency.

The packet forward probability without normal packet loss is shown in Figure 8. The Packet Delivery Radio of CSMFM and MSMFM is improved compared to WMM because they detect and isolate the attacker and forward the packets to the destination through a different secure path. Using WMM which have no monitor mechanism, there is a significant degradation in the Packet Delivery Radio with selective dropping attacks. Using MSMFM, the Packet Delivery Radio is improved to 85% in the case of 20% dropping and 65% in case of 50% dropping. Using CSMFM, the Packet Delivery Radio is improved to 88% in the case of 20% dropping and 70% in case of 50% dropping.

Figure 8

The packet forward probability without normal packet loss.

The curves in Figure 9 illustrate the performance of CSMFM, MSMFM, and WMM in the presence and absence of attacker(s) with normal losses. As the sum of false alarm and missed detection probabilities of CSMFM is degraded compared to MSMFM, the Packet Delivery Radio of CSMFM is increased. And the increased channel loss rate does cause more packet loss.

Figure 9

The performance of CSMFM, MSMFM, and WMM in the presence and absence of attacker(s) with normal losses.

6. Conclusion

Due to the resource limitations and open environments in WSN, traditional cryptography based security mechanisms such as authorization and authentication are not effective against insider attacks. To mitigate selective forwarding attacks launched by insider nodes in multihop communication, a repeated mixed strategy and an energy-efficient continuous strategy Monitor-Forward game between the sender node and its one-hop neighboring node in a cluster WSN are proposed and simulated. We propose a trust management mechanism to identify and isolate malicious nodes for the cluster wireless sensor networks. A distributed watch dog runs on every cluster head in WSN to monitor and record the packet forwarding behaviors of its next hop cluster head node. By this trust model, we can select more reliable cluster heads having sufficient residual energy and high trust level.

The main contributions of our work are as follows: (1)

We constructed and simulated a mixed strategy Monitor-Forward game, analyze the payoff matrix and mixed strategy Nash Equilibrium of the game with different parameters: B and C. The random ended repeated mixed strategy game and its quantal response equilibrium are discussed.

(2)

Because of the unreliable wireless communication channel in WSN, packet loss, data corruption, and variable propagation delays will lead to large amounts of false positives on packet dropping detection that rely on strict timing. We constructed and simulated a continuous game which allows players to choose a strategy from a continuous strategy set.

(3)

Routing protocol without monitor mechanism, routing protocol with mixed strategy Monitor-Forward game, and routing protocol with continuous strategy Monitor-Forward game in a clustered WSN are all simulated and analyzed with Matlab in various setups.

Game analyzing and simulation results demonstrate that game theory based framework is an efficient approach to identifying the selective forwarding attacks and increase the packets forward probability of the networks. Continuous strategy game will consume less battery energy and have less false alarms than mixed strategy game on unreliable channels.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgment

This paper is supported by the Fundamental Research Funds for the Central Universities (2014XT04).

References

Liu

Towards energy-fairness in asynchronous duty-cycling sensor networks

ACM Transactions on Sensor Networks 2012 10 3, article 38

10.1145/2490256

Liu

Wang

Liu

Does wireless sensor network scale? A measurement study on GreenOrbs

IEEE Transactions on Parallel and Distributed Systems 2013 24 10 1983 1993

10.1109/tpds.2012.216

2-s2.0-84883371380

Chen

Gao

Huang

Modified extended kalman filtering for tracking with insufficient and intermittent observations

Mathematical Problems in Engineering 2015 2015 9

10.1155/2015/981727

981727

Sun

H.-M.

Chen

C.-M.

Hsiao

Y.-C.

An efficient countermeasure to the selective forwarding attack in wireless sensor networks

Proceedings of the IEEE Region 10 Conference (TENCON '07)

October 2007

Taipei, Taiwan

1 4

Mukherjee

Chattopadhyay

Sanyal

D. K.

Neogy

Pal

A novel incentive based scheme to contain selective forwarding in wireless sensor network

Computer Information Systems and Industrial Management 2013 8104 301 312 Lecture Notes in Computer Science

10.1007/978-3-642-40925-7_28

Félegyházi

Hubaux

J.-P.

Buttyán

Nash equilibria of packet forwarding strategies in wireless ad hoc networks

IEEE Transactions on Mobile Computing 2006 5 5 463 476

10.1109/tmc.2006.68

2-s2.0-33645673382

Mukherjee

Dey

Mukherjee

Chattopadhyay

Sanyal

D. K.

Addressing forwarder's dilemma: a game-theoretic approach to induce cooperation in a multi-hop wireless network

Advances in Communication, Network, and Computing 2012 108

Berlin, Germany

Springer

93 98 Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering

10.1007/978-3-642-35615-5_14

Jakobsson

Hubaux

J.-P.

Buttyán

Wright

R. N.

A micro-payment scheme encouraging collaboration in multi-hop cellular networks

Financial Cryptography: 7th International Conference, FC 2003, Guadeloupe, French West Indies, January 27-30, 2003 2003 2742

Springer

15 33 Lecture Notes in Computer Science

Mukherjee

Chattopadhyay

Sanyal

D. K.

Neogy

Pal

A a novel incentive based scheme to contain selective forwarding in wireless sensor network

Computer Information Systems and Industrial Management 2013 8104

Springer

301 312 Lecture Notes in Computer Science

10.1007/978-3-642-40925-7_28

10.

Y. M.

Wong

V. W. S.

An energy-efficient multipath routing protocol for wireless sensor networks

International Journal of Communication Systems 2007 20 7 747 766

2-s2.0-34547266421

10.1002/dac.843

11.

Wang

Bulut

Szymanski

B. K.

Energy efficient collision aware multipath routing for wireless sensor networks

Proceedings of the IEEE International Conference on Communications (ICC '09)

June 2009

Dresden, Germany

IEEE

1 5

10.1109/icc.2009.5198989

2-s2.0-70449493154

12.

Radi

Dezfouli

Bakar

K. A.

Lee

Multipath routing in wireless sensor networks: survey and research challenges

Sensors 2012 12 1 650 685

10.3390/s120100650

2-s2.0-84863012027

13.

Qiao

Meshed multipath routing: an efficient strategy in sensor networks

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '03)

March 2003

New Orleans, La, USA

IEEE

1912 1917

10.1109/wcnc.2003.1200679

2-s2.0-77957963167

14.

Sohrabi

Gao

Ailawadhi

Pottie

G. J.

Protocols for self-organization of a wireless sensor network

IEEE Personal Communications 2000 7 5 16 27

2-s2.0-0034291065

10.1109/98.878532

15.

Ganesan

Govindan

Shenker

Estrin

Ganesan

Highly-resilient, energy-efficient multipath routing in wireless sensor networks

ACM SIGMOBILE Mobile Computing and Communications Review 2001 5 4 11 25

10.1145/509506.509514

16.

Intanagonwiwat

Govindan

Estrin

Directed diffusion: a scalable and robust communication in wireless sensor networks

Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking (Mobicom '99)

1999

174 185

17.

Zhong

Zhang

GRAdient broadcast: a robust data delivery protocol for large scale sensor networks

Wireless Networks 2005 11 3 285 298

10.1007/s11276-005-6612-9

2-s2.0-2442529460

18.

Shah

R. C.

Rabaey

J. M.

Energy aware routing for low energy ad hoc sensor networks

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '02)

March 2002

IEEE

350 355

10.1109/wcnc.2002.993520

2-s2.0-84907549442

19.

Vidhyapriya

Vanathi

P. T.

Energy efficient adaptive multipath routing for wireless sensor networks

IAENG International Journal of Computer Science 2007 34 1

20.

Huang

Fang

Multi constrained QoS multipath routing in wireless sensor networks

ACM Wireless Networks 2008 14 4 465 478

10.1007/s11276-006-0731-9

2-s2.0-46449105138

21.

Stavrou

Pitsillides

A survey on secure multipath routing protocols in WSNs

Computer Networks 2010 54 13 2215 2238

2-s2.0-77955467415

10.1016/j.comnet.2010.02.015

Zbl1208.68063

22.

Gibbons

Game Theory for Applied Economics 1992

Princeton, NJ, USA

Princeton University Press

23.

Hao

Liao

Adhikari

Sakurai

Yokoo

A repeated game approach for analyzing the collusion on selective forwarding in multihop wireless networks

Computer Communications 2012 35 17 2125 2137

2-s2.0-84866738779

10.1016/j.comcom.2012.07.006

24.

Naserian

Tepe

Game theoretic approach in routing protocol for wireless ad hoc networks

Ad Hoc Networks 2009 7 3 569 578

10.1016/j.adhoc.2008.07.003

2-s2.0-56449123247

25.

Afghah

Razi

Abedi

Stochastic game theoretical model for packet forwarding in relay networks

Telecommunication Systems 2013 52 4 1877 1893

10.1007/s11235-011-9471-y

2-s2.0-84879899119

26.

Zhong

A collusion-resistant routing scheme for noncooperative wireless ad hoc networks

IEEE/ACM Transactions on Networking 2010 18 2 582 595

10.1109/tnet.2009.2030325

2-s2.0-77951127884

27.

Liu

Jiang

Nishiyama

Miura

Kato

Kadowaki

Optimal forwarding games in mobile Ad Hoc networks with two-hop f-cast relay

IEEE Journal on Selected Areas in Communications 2012 30 11 2169 2179

10.1109/jsac.2012.121209

2-s2.0-84870266614

28.

Liu

Yin

Leung

V. C. M.

Cai

FADE: forwarding assessment based detection of collaborative grey hole attacks in WMNs

IEEE Transactions on Wireless Communications 2013 12 10 5124 5137

10.1109/twc.2013.121906

2-s2.0-84890127638

29.

Shila

D. M.

Cheng

Anjali

Mitigating selective forwarding attacks with a channel-aware approach in WMNs

IEEE Transactions on Wireless Communications 2010 9 5 1661 1675

10.1109/twc.2010.05.090700

2-s2.0-77952255404

30.

Zhang

Yang

Liu

Feng

Incentive mechanism for multiuser cooperative relaying in wireless Ad hoc networks: a resource-exchange based approach

Wireless Personal Communications 2013 73 3 697 715

10.1007/s11277-013-1211-z

2-s2.0-84890564446

31.

Chakrabarti

Parekh

Ruia

A trust based routing scheme for wireless sensor networks

Advances in Computer Science and Information Technology. Networks and Communications: Second International Conference, CCSIT 2012, Bangalore, India, January 2-4, 2012. Proceedings, Part I 2012 84

Berlin, Germany

Springer

159 169 Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering

10.1007/978-3-642-27299-8_18

32.

McKelvey

R. D.

Palfrey

T. R.

Quantal response equilibria for normal form games

Games and Economic Behavior 1995 10 1 6 38

10.1006/game.1995.1023

Zbl0832.90126

2-s2.0-0348166371

33.

Pirzada

A. A.

McDonald

Circumventing sinkholes and wormholes in wireless sensor networks

Proceedings of the International Conference on Wireless Ad Hoc Networks (IWWAN '05)

June 2005

Columbus, Ohio, USA

34.

Heidemann

Estrin

Geography-informed energy conservation for ad hoc routing

Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MobiCom '01)

July 2001

Rome, Italy

70 84

10.1145/381677.381685

35.

Umuhoza

Omlin

C. W. P.

A metric of trust in mobile Ad hoc networks using direct source routing algorithms

Proceedings of the Southern African Telecommunication Networks and Applications Conference (SATNAC '05)

2005

36.

Sathian

Baskaran

Dhavachelvan

Lifetime enhancement by Cluster Head Cooperative Trustworthy Energy Efficient MIMO routing algorithm based on game theory for WSN

Proceedings of the 3rd International Conference on Computing, Communication and Networking Technologies (ICCCNT '12)

July 2012

Coimbatore, India

10.1109/icccnt.2012.6396079

2-s2.0-84873296860

37.

Shila

D. M.

Cheng

Anjali

Mitigating selective forwarding attacks with a channel-aware approach in WMNS

IEEE Transactions on Wireless Communications 2010 9 5 1661 1675

2-s2.0-77952255404

10.1109/TWC.2010.05.090700