Game Theoretic Approach in Adapting QoS Routing Protocol for Wireless Multimedia Sensor Networks

Abstract

Network routing has a direct impact on the fairness and efficiency of the whole wireless multimedia sensor networks, the cooperation of nodes in term of routing can be considered as a group called routing coalition. In order to improve the fairness of the wireless multimedia sensors networks, each node should take into account the choices of joining a appropriate routing coalition. This paper presents a game theoretic approach, called coalitional routing game (CRG), which is guideline for nodes to choose the best coalition. The objective of the proposed method is to achieve fairness and QoS efficiency for each node in joining the routing coalition. The Shapley value is used as a solution for the CRG. The coalitional routing game is implemented in DSR protocol in network simulator NS-2 to verify its performance with simulations. Numerical analysis and simulations are conducted, and the results demonstrate that the CRG improves performance of the DSR compared to the same network with only DSR protocol.

1. Introduction

Wireless sensor networks (WSN) have been made viable by the convergence of microelectromechanical systems technology, wireless communications, and digital electronics [1]. They have been widely deployed in a vast variety of environments for commercial, civil, and military applications such as surveillance, vehicle tracking, and climate. Many problems associated with these large scale networks are emerging and receiving intensive studies, for example, the problem of decentralized networks and cooperation between the nodes, in [2]; these problems are formulated as a constrained quadratic programming problem and then a recurrent neural network with independent modules is proposed to solve the problem in a distributed manner. To tackle the problem of finding a feasible solution to a class of nonlinear inequalities defined on a graph, a recurrent neural network is proposed in [3], Laplacian Eigenmap as Heuristic Information is proposed in [4]. The problem of multimedia transmission is that video-streaming services are likely to be used. These services require the provision of QoS (quality of service), which still remains an open issue in WSN. The special characteristics of WSN, such as energy constraints, lack of centralized infrastructure, and variable link capacity, make the QoS provision over these networks a challenging objective; to tackle this problem, game theory was used, which was widely used in the distributed network [5, 6].

Multipath routing has become a promising quality of service (QoS) mechanism for multimedia streaming over WSN. It is motivated by two enabling technologies, that is, scalable source coding and service differentiation. Most of the latest image and video coding methods are scalable, including JPEG2000, MPEG-2, MPEG-4, and many wavelet based coders. These coders can produce a code stream in multiple quality layers, typically a base layer and one or more enhancement layers. When the network system allows for multipath routing, the multiple paths discovered by the routing protocol usually have quite different QoS characteristics, which are indicated by their link metrics, and multimedia streaming could be delivered over WSN with a promising QoS.

Multimedia streaming using multipath routing has been extensively studied [7–14]. Most of the multipath routing protocols originate from AODV [15] or DSR [16] protocols. These multipath routing protocols modify the route discovery and route maintenance mechanisms of DSR and AODV protocols to improve the performances of a network in terms of delay, reliability, overhead reduction, energy efficiency, and network throughput. Intuitively, there are multiple nodes in a path which can be considered as a coalition. If one node has many coalitions to choose, then it is natural to assume that every node will compete for the high payoff coalition. Traditionally this situation is managed through pricing and service agreements. However, such solutions often lead to in-effective use of the shared resource.

In this paper, a route between source and destination would be considered as a coalition, so there are many coalitions in WSN, and the same node would be in many deferent coalitions. This may cause WSN inefficiency. Game theoretic framework called coalitional routing game (CRG) will be introduced, which is guideline for nodes to choose the best coalition. The objective of the proposed method is to achieve fairness and QoS efficiency for each node in joining the appropriate coalition. The Shapley value is a solution for every node to choose the best coalition. The CRG is implemented in DSR to find multiple routing coalitions. By simulation, we verified that CRG not only improved performance adaptive to link-state, but also improved energy balance of WSN. All of these would prolong the lifetime and promote efficiency of WSN.

The rest of this paper is organized as follows. Section 2 discusses the proposed coalition routing game. Section 3 presents NS-2 simulation results for the proposed approach and compares the results with those of DSR. Section 4 provides the conclusion and some discussion on future works.

2. Coalitional Routing Game

A WSN can be presented as a connected, undirected, and weighted graph $G=(V,E)$ where $V=\{v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_n\}$ denotes the set of nodes in the network and $E=\{e_{\mathrm{12}},e_{\mathrm{13}},\dots ,e_{xy}\}$ depicts the set of bidirectional links between nodes. $s\in V$ is the source node, and $d\in (V-s)$ is the destination node. For a pair of nodes $v_i,v_j\in V\hspace{0.17em}\hspace{0.17em}(i\ne j)$ , if the link $e_{ij}=(v_i,v_j)\in E$ , then $(v_i,v_j)$ consists of a pair of adjacent nodes. Each node $n\in V$ in the graph includes a set of five QoS metrics elements: $\{\text{bw}(n),\text{pl}(n),\text{ma}(n),\text{dl}(n),\text{re}(n)\}$ , where $\text{bw}(n)$ expresses the minimum expected bandwidth of node n, $\text{pl}(n)$ expresses the maximum packet loss rate of node n, $\text{ma}(n)$ denotes the available memory in node n, $\text{dl}(n)$ shows the queuing delay in node n, and $\text{re}(n)$ reveals the normalized remaining energy in the node n with respect to the initial energy, defined as $\text{re}(n)=E_{\text{residual}}(n)/E_{\text{initial}}(n)$ , where $E_{\text{residual}}(n)$ unveils the remaining energy in the battery of node n and $E_{\text{initial}}(n)$ indicates the initial energy in the battery of node n. These parameters were important elements to find routes in a WSN.

For a unicast path $P=(s,v_a,v_b,\dots ,d)$ from the source node to the destination node, its QoS parameters are computed as follows:

$$\begin{array}{cc}& \text{bandwidth}\left(P\right)=\underset{n\in P}{\min }\left\{\text{bw}\left(n\right)\right\},\\ \text{delay}\left(P\right)=\sum _{n\in P}\text{dl}\left(n\right),\\ \text{packetloss}\left(P\right)=\mathrm{1}-\prod _{n\in P}\text{pl}\left(n\right),\\ \text{energy}\left(P\right)=\underset{n\in P}{\min }\left\{\text{re}\left(n\right)\right\},\\ \text{memory}\left(P\right)=\underset{n\in P}{\min }\left\{\text{ma}\left(n\right)\right\}.\end{array}$$

(1)

Consider the grouping problem for wireless sensor networks as a coalitional game. Every route from the source to the destination was treated as a coalition. The sensor nodes are the players and the game is concerned with whether a node should join a group or not. How the node may select the best group to join, we need a utility function which reflects the benefit for the node's joining a coalition. Here we use the quality of routing to measure the payoff for a participation node, because quality of routing is shared among every participation node. The payoff function of a path PC can be expressed as follows:

$$\begin{array}{l}f\left(P\right)={\gamma }_P^b\left(\text{bandwidth}\left(P\right)-B_{\min }\right)+{\gamma }_P^d\left(D_{\max }-\text{delay}\left(P\right)\right)\\ +{\gamma }_P^l\left(\mathrm{1}-\text{packetloss}\left(P\right)\right)+{\gamma }_P^e\left(\text{energy}\left(P\right)-E_{\min }\right)\\ +{\gamma }_P^m\left(\text{memory}\left(P\right)-M_{\min }\right),\end{array}$$

(2)

where $\text{bandwidth}(P)$ , $\text{delay}(P)$ , $\text{packetloss}(P)$ , $\text{energy}(P)$ , and i, respectively, denote bandwidth, delay, packet loss rate, residual energy ratio, and available memory for the path as defined in (1). $B_{\min }$ , $D_{\max }$ , $E_{\min }$ , and $M_{\min }$ indicate the path's minimal tolerable bandwidth, maximal tolerable delays, minimal residual energy ratio, and normalized memory available, respectively. Variables ${\gamma }_P^b$ , ${\gamma }_P^d$ , ${\gamma }_P^l$ , ${\gamma }_P^e$ , and ${\gamma }_P^m$ translate the bandwidth weight factor, delay, packet loss rate, residual energy ratio, and available memory for global quality of routing, respectively.

Cooperative games focus on how to assign the total benefits among coalitions, taking into account individual and group incentives, as well as various fairness properties. We define the notion of a benefit sharing game as follows: a benefit sharing game consists of a finite set A of n nodes and a benefit function $f:{\mathrm{2}}^A\to R^{+}$ to denote the nonnegative benefit from the set of coalition.

As a widely applicable concept, the Shapley value is a solution that assigns a single benefit allocation to benefit sharing games. We choose this solution to a cooperative game since the computational complexity is small and the Shapley value provides relatively anonymous solution by a random ordering of the nodes. It had been proved that the Shapley value is the unique value on the set of games satisfying anonymity, dummy, and additivity. Let $S\subseteq A\setminus \{i\}$ denote all coalitions S of A not containing node i. For any node $i\in A$ and any set $S\subseteq A\setminus \{i\}$ , the probability that the set of nodes that comes before i in a random ordering is precisely S is $\left|S\right|!(n-\mathrm{1}-|S|)!/n!$ , where $\left|S\right|$ is cardinality of S. Then the Shapley value

$$\begin{array}{cc}& {\phi }_i\left(f\right)=\sum _{S\subseteq A\setminus \left\{i\right\}}\frac{\left|S\right|!\left(n-\mathrm{1}-\left|S\right|\right)!}{n!}\left(f\left(S\cup \left\{i\right\}\right)-f\left(S\right)\right),\end{array}$$

(3)

where ${\phi }_i(f)$ indicates the benefit allocation in the benefit sharing for node i in the coalition $S\cup \{i\}$ . There are two coalitions in (3): the one is S and the other is $S\cup \{i\}$ , and they are all routing coalition. In coalition S, the routing probe cannot arrive at destination node, so the payoff of S is 0. Then

$$\begin{array}{cc}& f\left(S\right)=\mathrm{0}.\end{array}$$

(4)

The benefit allocation in the benefit sharing for node i in the coalition $S\cup \{i\}$ can be written by substituting (4) into (3):

$$\begin{array}{cc}& {\phi }_i\left(f\right)=\sum _{S\subseteq A\setminus \left\{i\right\}}\frac{\left|S\right|!\left(n-\mathrm{1}-\left|S\right|\right)!}{n!}\left(f\left(S\cup \left\{i\right\}\right)\right).\end{array}$$

(5)

In (5), the benefit allocation in the benefit sharing for node i decreases with the number of participation n being increased and with coalition benefits being decreased. So as a rational node, in order to maximize the benefits, the node tends to join the coalition which has less participation number and more benefits.

3. Simulation Model and Results

In the previous section, the coalitional routing game (CRG) and the Shapley value in routing coalition as the solution of this game were explained. The Shapley value for every node, derived in (5), depends strictly on the routing coalition's payoff function $f(S)$ and the number of participation n. In order to evaluate performance of the CRG with DSR protocol, NS-2 simulations were performed. In the simulations, one source node and one sink node were placed, and some nodes with different metric were placed between the source and the sink node. In order to show if CRG enhances the performance of the network compared to DSR alone, the number of nodes between the source and the sink was varied.

To compare the performance of the proposed algorithms, the CRG with DSR, the following metrics were considered: average end-to-end delay per packet is the end-to-end delay (in seconds) for successfully received packets. Packet delivery ratio is the ratio between the number of successfully received packets by the sink and the number of generated packets by the source node. Balance of the energy consumption for nodes can be denoted by standard deviation of all nodes residual energy $E_{\text{nodes}}=(\mathrm{1}/N){\sum }_{i\in N}{(E(i)-\overline{E})}^2$ .

The number of nodes between source node and sink node varied between 30 and 200. Figures 1–3 show average end-to-end delay per packet, packet delivery ratio, and standard deviation of all paths residual energy versus the number of nodes in the network.

Figure 1

Average end-to-end delay versus number of nodes.

Figure 2

Packet delivery ratio versus number of nodes.

Figure 3

Standard deviation of all paths residual energy versus number of nodes.

Figure 1 compares the average end-to-end delay in using DSR with CRG versus using DSR alone with which all other network parameters held the same. The network with the CRG showed a slow increase in packet delay with increasing nodes number, whereas the network with DSR showed a quickly increase in packet delay with increasing nodes number.

In order to perform the convergence time analysis for the proposed CRG algorithm, we construct a mathematical model based on the well-known coupon collector problem [17] to derive the upper bound of the expected number needed in order to collect n distinct stamps, each from the individual router along the attacking path of length n. Following the same methodology as the coupon collector problem, we then want to derive the upper bound of the expected convergence time, so convergence time for every router path can be defined as follow: $\text{convergence}(P)={\sum }_{n\in P}\text{dl}(n)$ , so Figure 1 also shows the convergence time for the CRG and the DSR.

Figure 2 shows that the packet delivery ratios of modified routing protocol outperform the DSR protocol alone.

Figure 3 confirms the fact that CRG which can balance the energy consumption of each node outperforms the DSR protocol alone. All these were due to CRG providing an effective guideline for each node's joining best payoff coalition. So that the network resource can be shared fairly and efficiently.

4. Conclusions

This paper introduced a game theoretic approach to coordinate QoS routing, called coalitional routing game (CRG), for optimizing multipath with different quality metrics in wireless sensor networks. The CRG provides a Shapley value for every node in each routing coalition from the source node to destination node. This makes each node only join one routing coalition one time, which can maximize its utility, and nodes employ CRG to calculate the Shapley value of routing coalition adaptively. Simulation results show that DSR with CRG outperforms the DSR routing protocol, especially in more nodes where much more interactive coalitions are a dominant factor degrading the network performance.

We should point out that this study only demonstrates the viability of the proposed method, and many technical challenges still need to be addressed. A protocol will be developed to implement this QoS game and to use the Shapley value as guideline in the QoS coalition routing for optimizing multipath. For example, the solution Shapley value can be used for the node to decide joining the appropriate routing coalition. A major difficulty in this approach is to accurately estimate all parameters needed in the Shapley value calculation, such as available bandwidth, the delay, the percentage of losses, and the available energy.