Game Theory for Wireless Sensor Networks: A Survey <s> Basics of Game Theory <s> Standard wireless sensor network models emphasize energy efficiency and distributed decision-making by considering untethered and unattended sensors. To this we add two constraints--the possibility of sensor failure and the fact that each sensor must tradeoff its own resource consumption with overall network objectives. In this paper, we develop an analytical model of energy-constrained, reliable, data-centric information routing in sensor networks under all the above constraints. Unlike existing techniques, we use game theory to model intelligent sensors thereby making our approach sensor-centric. Sensors behave as rational players in an N-player routing game, where they tradeoff individual communication and other costs with network wide benefits. The outcome of the sensor behavior is a sequence of communication link establishments, resulting in routing paths from reporting to querying sensors. We show that the optimal routing architecture is the Nash equilibrium of the N-player routing game and that computing the optimal paths (which maximizes payoffs of the individual sensors) is NP-Hard with and without data-aggregation. We develop a game-theoretic metric called path weakness to measure the qualitative performance of different routing mechanisms. This sensor-centric concept which is based on the contribution of individual sensors to the overall routing objective is used to define the quality of routing (QoR) paths. Analytical results on computing paths of bounded weakness are derived and game-theoretic heuristics for finding approximately optimal paths are presented. Simulation results are used to compare the QoR of different routing paths derived using various energy-constrained routing algorithms. <s> BIB001 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Basics of Game Theory <s> The advance in wireless technologies makes now viable to start to develop ad hoc networks. However, without a mechanism that prevents misbehaviors, these networks could result easily unreliable. We develop a model, based on game theory, capable of formally explaining characteristics of ad hoc networks (as the nodes' selfishness or the network mobility). It also allows to formally study and analyze strategies for cooperation. As example, we describe a simple strategy that enforces packet forwarding among nodes. <s> BIB002 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Basics of Game Theory <s> Path length, path reliability, and sensor energy-consumption are three major constraints affecting routing in resource constrained, unreliable wireless sensor networks. By considering the implicit collaborative imperative for sensors to achieve overall network objectives subject to individual resource consumption, we develop a game-theoretic model of reliable, length and energy-constrained, sensor-centric information routing in sensor networks. We define two distinct payoff (benefit) functions and show that computing optimally reliable energy-constrained paths is NP-Hard under both models for arbitrary sensor networks. We then show that optimal length-constrained paths can be computed in polynomial time in a distributed manner (using O(E) messages) for popular sensor network implementations using geographic routing. We also develop sensor-centric metrics called path weakness to measure the qualitative performance of different routing schemes and provide theoretical limits on the inapproximability of computing paths with bounded weakness. Heuristics for computing optimal paths in arbitrary sensor networks are described along with simulation results comparing performance with other routing algorithms. <s> BIB003 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Basics of Game Theory <s> Sensor networks are large scale networks consisting of several nodes and some base stations. The nodes are monitoring the environment and send their measurement data towards the base stations possibly via multiple hops. Since the nodes are often battery powered, an important design criterion for sensor networks is the maximization of their lifetime. In this paper, we consider multi-domain sensor networks, by which we mean a set of sensor networks that co-exist at the same physical location but run by different authorities. In this setting, the lifetime of all networks can be increased if the nodes cooperate and also forward packets originating from foreign domains. There is a risk, however, that a selfish network takes advantage of the cooperativeness of the other networks and exploits them. We study this problem in a game theoretic setting, and show that, in most cases, there is a Nash equilibrium in the system, in which at least one of the strategies is cooperative, even without introducing any external incentives (e.g., payments). <s> BIB004 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Basics of Game Theory <s> In self-organizing ad hoc networks, all the networking functions rely on the contribution of the participants. As a basic example, nodes have to forward packets for each other in order to enable multihop communication. In recent years, incentive mechanisms have been proposed to give nodes incentive to cooperate, especially in packet forwarding. However, the need for these mechanisms was not formally justified. In this paper, we address the problem of whether cooperation can exist without incentive mechanisms. We propose a model,based on game theory and graph theory to investigate equilibrium conditions of packet forwarding strategies. We prove theorems about the equilibrium conditions for both cooperative and noncooperative strategies. We perform simulations to estimate the probability that the conditions for a cooperative equilibrium hold in randomly generated network scenarios.. As the problem is involved, we deliberately restrict ourselves to a static configuration. We conclude that in static ad hoc networks where the relationships between the nodes are likely to be stab le-cooperation needs to be encouraged. <s> BIB005 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Basics of Game Theory <s> Numerous routing protocols have been proposed for wireless networks. A common assumption made by the majority of these protocols is that each wireless node will follow the prescribed protocol without any deviation. This may not be true in practice since wireless nodes could be owned by users who perform in their own interests. We then have to design routing protocols that still work properly even for networks composed of selfish nodes. In this paper, we propose a unicast routing protocol to address this issue under the assumption that all networking nodes are rational. Here, a node is rational if it always chooses a strategy that maximizes its benefit. We assume that each node has a privately known cost of relaying a unit of data for other nodes. In our protocol, each wireless node has to declare a cost for forwarding a unit of data. When a node wants to send data to the access point, it first computes the least cost path to the access point and then computes a payment to each node on this path. We present a pricing mechanism such that the profit of each relay node is maximized when it declares its true cost. We also give a time optimal method to compute the payment in a centralized manner. We then discuss in detail how to implement the routing protocol in the distributed manner. We conduct extensive simulations to study the ratio of the total payment over the total cost incurred by all relay nodes. We find that this ratio is small in practice. Our protocol works when the wireless nodes will not collude and we show that no truthful mechanism can avoid the collusion of any pair of two nodes. We also give a truthful mechanism when a node only colludes with its neighbors. <s> BIB006 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Basics of Game Theory <s> Wireless sensor networks (WSN) are planted for sensing the area which people mostly concern and to send data of light, pressure, sound, and so on, back to people to make further analyses. Differ from normal lineal networks, WSN are usually restricted by energy store, plethoric information flow, and short communication distance. So, there are many research hotpots in WSN such as routing, economization of energy, adaptive self-configuration, etc. Among these aspects, the area of quality of service (QoS) remains largely open. This is due to that the optimal alive sensor node number is difficult to determine in a certain focused area which satisfies the requirement of QoS. In the paper, under a circumstance of ITS (Intelligent Transportation Systems) application, a modified Gur Game strategy based on localized information is given to determine the optimal alive node number in a focused area. In the strategy, all nodes use local information to modify their finite state automaton, and the base station receives the QoS feedback and gives the dynamic density domination information. The simulation results about the band shape density domination are given. The results show that the strategy can effectively control the density of nodes and meet the requirement of QoS even with impediment added. <s> BIB007 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Basics of Game Theory <s> We describe a decentralized learning-based activation algorithm for a ZigBee-enabled unattended ground sensor network. Sensor nodes learn to monitor their environment in a low-power "sleep" mode, until an intruder is detected, then enter a full-power mode only if the benefit for doing so outweighs an energy cost. Our formulation accounts for the energy required to transmit and the probability of successful transmission in a crowded ZigBee network. Since these depend on the activity of other nodes, we propose a decentralized adaptive algorithm for sensor activation based on game theoretic principles. We show that the algorithm tracks the time-varying set of correlated equilibria of the problem, and illustrate performance through simulation. The algorithm is described as a stochastic approximation, with attendant differential inclusion analysis. <s> BIB008 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Basics of Game Theory <s> Game Theory (GT) is a branch of applied mathematics that models situations where players (participants in a game) participate in a strategic situation (the game) in which they perform different actions attempting to maximise their profits, while at the same time minimise losses. As nodes in Wireless Sensor Networks (WSN) can be abstracted as the players in such games where energy and information are valuable resources it is obvious that Game Theory provides a solid framework for both the modelling and the induction of node behaviour in such networks. The proposed algorithm induces an energy-aware and efficient collaborative behaviour to the nodes using sensor centric information, by making them aware of their interdependency, without compromising the main purpose of the network - the collection of information. <s> BIB009 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Basics of Game Theory <s> In infrastructure-less sensor networks, efficient usage of energy is very critical because of the limited energy available to the sensor nodes. Among various phenomena that consume energy, radio communication is by far the most demanding one. One of the effective ways to limit unnecessary energy loss is to control the power at which the nodes transmit signals. In this paper, we apply game theory to solve the power control problem in a CDMA-based distributed sensor network. We formulate a noncooperative game under incomplete information and study the existence of Nash equilibrium. With the help of this equilibrium, we devise a distributed algorithm for optimal power control and prove that the system is power stable only if the nodes comply with certain transmit power thresholds. We show that even in a noncooperative scenario, it is in the best interest of the nodes to comply with these thresholds. The power level at which a node should transmit, to maximize its utility, is evaluated. Moreover, we compare the utilities when the nodes are allowed to transmit with discrete and continuous power levels; the performance with discrete levels is upper bounded by the continuous case. We define a distortion metric that gives a quantitative measure of the goodness of having finite power levels and also find those levels that minimize the distortion. Numerical results demonstrate that the proposed algorithm achieves the best possible payoff/utility for the sensor nodes even by consuming less power. <s> BIB010
Game theory is increasingly attracting more attention as a mechanism to solve various problems in WSNs BIB001 BIB003 BIB002 BIB005 BIB004 BIB006 . Generally, a game consists of a set of players, a set of strategies for each player and a set of corresponding utility functions. A norm form game of a WSN of n sensor nodes is given by a 3-tuple G = <N, S, U>. Here, G is a particular game, where N = {n BIB007 , n 2 , ..., n n } is a finite set of the sensor nodes. S = {S 1 , S 2 , ..., S n }, is the strategy space of the sensor node i can select from is represented by S i (i = 1, 2, ..., n). U = {u 1 , u 2 , ..., u n } is the corresponding payoff function of node i represented by u i (i = 1, 2, ..., n), u i is a utility value of each node receives at the end of an action. A strategy for a player is a complete plan of actions in all possible situations in the game. The players try to act selfishly to maximize their consequences according to their preferences. We have to formulate the payoff functions in a way that will help node i to select a strategy S i that represents the best response to the strategies selected by the other n-1 nodes. Here, s i is the particular strategy chosen by node i and s -i is the particular strategies chosen by all of the other nodes in the game. For strategies s = {s i , s −i }, it is called a strategy profile or sometimes a strategy combination. Every different combination of individual choices of strategies can produce a different strategy profile. The strategy profile s = {s BIB007 , s 2 , ..., s n -s i ∈ S i , i = 1, 2, ..., n} needs to place the nodes responding to a Nash Equilibrium (NE). It is a solution concept that describes a steady state condition of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only its own strategy unilaterally. NE is identified wherein no nodes will rationally choose to deviate from his chosen strategy otherwise it will diminish its utility, i.e., u i (s i , A utility function describing player preferences for a given player assigns a number for every possible outcome of the game with the property that a higher number implies that the outcome is more preferred. In literature BIB010 , the utility is defined as: where u i (s i , s −i ) can be considered as the utility of node i transmitting information to a node j, b is the number of information bits in a packet of size F bits, r is the transmission rate in bits/sec using strategy s i , and f (γ j ) is efficiency function which increase with expected SINR of the receiving node. The efficiency function is defined as: (2) where P e is the bit error rate which depends on the channel state and interference from other nodes. Schillings and Yang BIB009 used the GT framework to construct a query-based Versatile Game Theoretic Routing Protocol (VGTR) to accomplish the extraction of data from WSN. Three payoff functions are used. The first two represent node survivability and the third one represents the importance of the information collected. Node survivability represents the capability of a node to remain in contact with the Sink for as long as possible. To explain these three payoff functions clearly, several definitions were used, such as Upstream Potential Path Nodes (UPPN) Robustness, and Neighbor Robustness. After several years of development, there are several variations of game theory applicable in wireless sensor networks. The developments include cooperative game theory [8] , non-cooperative game theory  BIB008 , and repeated game theory  .