Keywords

1 Introduction

Wireless Sensor Networks (WSNs) incorporate a large number of communication nodes with restricted sensing, processing, and computational capabilities [1]. WSNs are being used in various applications in real life. WSNs have uses ranging from essential social matters such as monitoring of environment and habitat, traffic global position system (GPS), medical emergency, and health services to economic matters like production control and structure monitoring [2]. But there is always a resource constraint due to the nature and property of WSNs. There is always unreliability due to its wireless nature, and there are many energy-related deficiencies due to its power limitation. There are many challenges to make the network efficient to prolong network lifetime along with its own applications due to its constraints.

Routing involves finding the optimum way to transmit data from source to destination nodes in the network. Due to its small nodes, network lifetime is one of its most important factors. Therefore, routing always involves power management in its forefront while designing protocols. Many routing protocols use clustering or hierarchical approach to minimize the consumption of energy during data transmission. Clustering involves creating a cluster or group of clusters to transmit data from source to destination nodes in the network.

Game Theory is used in various walks of life in different applications in different sciences. It has also been used in WSNs. It is used for different aspects in WSNs like mitigating selfish nodes, providing games to increase efficiency, designing routing protocols, security protocols. We can find many works have been carried out using Game Theory to improve different aspects in WSNs. Game Theory came into existence as a branch of economics. It is a mathematical model used to examine as well as predict the actions of rational and selfish individuals.

This paper studies existing proposed game models used for designing clustering algorithm with energy efficiency as the main concern which further leads to energy-efficient routing in WSN.

2 Game Theory

Game Theory was firstly used in economics to make decisions in uncertain conditions. It provides mathematical techniques for analyzing the situations and predicting the future based on the decision taken by individual player. A game is a tuple <N, S, U>, where

  • N: set of players,

  • S: a set of actions/strategies for each player and

  • U: utility or payoff function.

Each player has certain strategy with which he plays the game, and it is defined in set S. Each strategy will consist of some action plan which covers possible situations that can come up in a game. A utility in a game is the players’ incentive for playing that strategy. It describes the players’ preference and assigns some payoff for each strategy, and the payoff with a larger value is the one that is favored. A Nash Equilibrium is a solution in a game such that the actions of the players do not change even if it knows the strategy of the other players as it does not improve its utility.

2.1 Types of Games

There are different forms of games, and its classification is shown in Fig. 1. A brief description of each of the types is given below:

Fig. 1
figure 1

Types of games

Full size image

  • Cooperative and Non-cooperative Games: The game in which each player knows the strategies of other players and selects the strategy that favors all the players is known as cooperative games, whereas non-cooperative games are games in which no one cooperates with each other and every player is trying to maximize their own profit.

  • Normal Form and Extensive Form Game: Normal form games are games in which the payoffs as well as strategies used in a game are shown in a tabular format. It can be used to find strategies that are dominated as well as in Nash Equilibrium. The extensive form game is a game where the description of game is done in a decision tree form. It helps in events decided by chance.

  • Simultaneous-Move and Sequential-Move Games: Simultaneous-move games are games in which the players adopt the strategy simultaneously. Each player is unaware about the strategy of another player, whereas in sequential-move games consist of games where players come to know strategy of earlier players.

  • Zero-Sum and Nonzero-Sum Games: Zero-sum games are games in which one player’s gain amounts to another player’s loss, and hence, the sum of outcomes is always zero, whereas in nonzero-sum games, the sum of outcomes is not zero.

  • Symmetric and Asymmetric Games: Symmetric games are games in which the strategy adopted by all players is same. Here, the payoffs depend on the strategy of the game. Asymmetric games are games where players adopt different strategies. Here, the payoffs depend on the player.

Most games in real life are non-cooperative ones where each node only thinks about itself and its network lifetime. There are also cooperative ones where nodes agree with each other to increase payoffs. Many literature have shown the use of non-cooperative games in WSNs where energy efficiency becomes utmost importance. Thus in such situation, nodes refuse to waste extra energy and conserve its energy by not participating in the process. So the selfish nodes are incentivized by offering bigger payoffs. Also in some cases, selfish nodes are also punished as defected nodes are doubly punished so as to discourage selfish nodes from defecting.

2.2 Games Used for Energy Efficiency in WSN

WSNs are made up of sensors with limited energy supply so the sensors ought to be able to manage energy efficiently while also minimizing its utility and completing its assigned work by communicating in the network. There are different games and approaches taken by the papers in this survey to improve its energy efficiency compared to previous protocols. There are different games also used in these papers to achieve required results.

From [3], it is seen that the following Game Theory methods have been used to formulate games in WSN:

  1. (i)

    Cooperative and non-cooperative game

  2. (ii)

    Repeated game

  3. (iii)

    Coalitional game

  4. (iv)

    Evolutionary game

  5. (v)

    Gur game

  6. (vi)

    Bargaining game

  7. (vii)

    Bayesian game

  8. (viii)

    Transferable and non-transferable utility game

  9. (ix)

    Zero and nonzero games

  10. (x)

    Ping-Pong game

  11. (xi)

    Jamming game

There have been many research papers in WSN related to Game Theory. Figure 2 shows the distribution of the publications year-wise.

Fig. 2
figure 2

No. of publications based on Game Theory for WSN [3]

Full size image

Non-cooperative game is the game which closely resembles the real-life situation as each node is selfish. Non-cooperative Game Theory inspects the relation among competing players, where each player individually selects its strategy and each player’s goal is to increase its utility or reduction of its cost. In the survey, Non-cooperative games have been used to find Nash Equilibrium under incomplete information and in one where every node communicates with each other. In another non-cooperative game, a Subgame Perfect Nash Equilibrium is used to select Cluster-Heads. Cooperative game is one in which coalitions are formed by grouping of players, and these players try to strengthen their game position by finding a coalition and act as a single entity by virtue of an agreement. In one, cooperative game is used to find Nash Equilibrium. Coalitional Game Theory is used in another to form coalitions to transmit data. Evolutionary Game Theory (EGT) is another approach. Here, some strategies in the game program the players. From large population, random players are drawn repeatedly and made to play the same pure or mixed strategies. The payoff includes the individual fitness or expected number of surviving offspring. Bayesian game is also used in another approach. In it, we choose the Cluster-Head among rich nodes and poor nodes through a Bayesian game. In it, Bayesian Nash Equilibrium is reached through Bayesian games.

3 Related Works

In this section, we present approaches and protocols used by researchers to improve the energy efficiency in WSNs using Game Theory.

Koltsidas and Pavlidou [4] formulated a clustering mechanism called Clustered Routing for Selfish Sensors (CROSSs) which has the critical aspect as the random rotation of Cluster-Head’s role for the goals of energy balancing, based on the rationality and selfishness of the sensor nodes in the network. In this paper, clustering game (CG) is used with a utility function that involves a payoff of 0 to a node if all nodes do not participate and a utility of v-c if it becomes a Cluster-Head and v for a node if it does not become a Cluster-Head but some other node is one (where c is the expense of becoming a CH and v is the gain amount for successful data transmission to Base Station). It is a case of mixed strategies Nash Equilibrium. In this, the players select their strategy randomly succeeding a probability distribution. Thus, the nodes compute the probability of becoming a CH. And randomly some nodes declare themselves as CHs and alert others so that other nodes can send data to the nearest CH. CHs thus aggregate and send the data to the sink. It is then repeated. Zero Probability Rule (ZPR) is also used to set the probability of nodes that have been CHs to zero until every neighbor has been a CH, and then, it switches back it to normal. However, the paper assumes that every sensor communicates with each and every other sensor.

Xie et al. [5] formulated a new algorithm and named it as Localized Game Theoretical Clustering Algorithm (LGCA). In this approach, energy efficiency is improved by using Game Theory (mixed strategy Nash Equilibrium) and a repeated clustering game. The game and utility function is similar to the [4], i.e., Clustering game. It differs though due to the fact that in it, every node plays a clustering game on its own and also joins the games of their neighbors’ to get its equilibrium probability. This helps nodes declare themselves as CHs. It also uses Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) mechanism as avoidance of closeness between two CHs. Its drawback is that it assumed that every node’s parameter is the same. Also, various important parameters like node degree, residual energy, and distance to Base Station (BS) are not of concern in this paper. Also, final CHs should have more preference toward powerful nodes instead of any nodes.

Yang et al. [6] proposed a hybrid distributed clustering protocol based on Game Theory called HGTD (Hybrid, Game Theory based and Distributed clustering). This proposed algorithm contains two phases: (i) initialization and (ii) setup phase. Initialization phase lets nodes calculate the distance from the node to the Base Station and also its neighbors. The setup phase consists of tentative CHs selection, final CHs election, and clusters formation. Tentative CHs selection lets each node play various clustering games with itself and its neighbors. It then plays a clustering game on its own and calculates the equilibrium probability to decide by itself whether to be a CH. It then broadcasts and receives messages to know its neighbor tentative CHs. The final CHs are elected to ensure an even distribution of CHs. Any tentative CHs with no neighbor tentative CHs automatically becomes a final CH. For others, it starts an iterative process in which tentative nodes are selected when each node select a CH based on the lowest cost. The nodes become the tentative nodes for next round. Then if the node is in nmax (i) iteration and also is the tentative CH plus has the lowest cost within a radius R or it does not have any neighboring CHs, it becomes a final CH and it then broadcasts the message within radius R. In cluster formation, the normal node with neighboring final CHs selects the node with the smallest node degree to join the cluster. It also improves on LGCA by assigning more weight toward potential CHs with fewer neighbor CHs and more residual energy to improve it.

Kazemeyni et al. [7] proposed an enhanced group membership protocol for WSNs which selects the best available group the node can have. It uses coalition Game Theory in cooperative games. It uses a proposed power-sensitive AODV routing protocol that detects the cheapest route from node to the leader. In this paper, a coalitional game (N, v) is proposed consisting of N players and utility function or coalition value defined by a characteristic function v: 2N → R for each players in coalition. In coalition game, a player does not earn any incentives in joining or forming a new coalition. It uses the utility function \( \omega \left( {P_{j} ,\delta_{j} } \right) = \left( {\frac{R}{{P_{j} }}} \right)\left( {1 - {\text{e}}^{ - 0.5\delta j} } \right)^{L} \)[7]. When applying \( \omega \) to a node j, \( P_{j} \) is the power used by j to transfer message and \( \delta_{j} \) is the signal-to-interference-and-noise ratio (SINR) for j. Furthermore, R specifies the rate of information transmission in L bit packets in the WSN. The protocol modifies the AODV protocol by having every group leader use the power-sensitive AODV protocol and in turn find the cheapest path for a node j as a possible group member and assess the gain of group membership for j: \( g_{i} \)(M ∪ {j}, N) < \( g_{i} \)(M, N ∪ {j}). If utility is improved, then the leader sends an Invite message along with utility values both old and new to j. The node j computes the benefit and accepts the Invite message. The Leader accepts and updates its utility.

Zheng et al. [8] used the Game Theory’s theorem to analyze routing in WSNs. It also proposes a clustering routing algorithm based on the Bayesian game called Bayesian Game Clustering Routing Algorithm (BGCRA). BGCRA uses separation of nodes into poor and rich nodes. It is different from others as it uses Bayesian game but also it assumes that the network consists of practical heterogeneous WSNs, whereas most protocols assume the homogeneous network which is not true in a real-life situation. In a practical heterogeneous WSN, there may be different types of sensor with different preferences and characteristics and different power levels. In this algorithm, the nodes are divided into rich and poor nodes in regard to remained energy class, and the preferences for both nodes are different for both. But it also needs to be more inclusive in division of nodes other than only rich and poor.

Mishra et al. [9] proposed a Cluster-Heads (CH) selection algorithm named as Game Theory-Based Energy-Efficient Cluster-Head Selection Approach (GECSA) using Subgame Perfect Nash Equilibrium (SPNE) decision of Game Theory. In this paper, a Game G that is non-cooperative is considered. It is assumed that the number of players is n and every cluster is seen as a player in the game, and there are k nodes in each cluster. Every player has q number of strategies denoted as S. The residual energy \( E_{\text{residual}} \) is fixed as a strategy for each player \( p_{i} \). Then the action of one player is checked with another player to see the greater one. After getting SPNE, the one is selected as a CH. There are different numbers of strategies for each player in the game, and each player according to his payoffs chooses his best strategy. Every player selects its best strategy amidst all SPNEs denoted as \( s_{ \hbox{max} } \) and chooses it as a CH in the event of multiple SPNEs.

For CH distribution in every region, there is a statistical allocation of sensor nodes in a finite space. After selecting the CHs, each CH broadcasts announcement packets within a radius suppose β\( r_{i} \), where β is the system parameter. Every non-CH should receive the packet. From these packets, the non-CH chooses a CH as their own and sends the information. The CH first aggregates the data before forwarding it to the sink node via another CH.

Raja and Dananjayan [10] have proposed a Game Theory based routing protocol which enhances the lifetime of WSN. It uses Cooperative Multiple Input Multiple Output (CMIMO) scheme along with Efficient Energy Consumption Protocol (EECP) proposed by them. In this paper, EECP is used at the beginning to select CHs. It contains (1) CH election stage (2) intracommunication stage, and (3) intercommunication stage. In every round, the above stages are repeated. The first stage consists of election of CH, and the method used is randomized maximum weight selection method. The second stage (intracommunication stage) consists of data collection and aggregation by CH from its cluster members. The third stage (intercommunication stage) consists of forwarding the aggregated data to the sink node through CHs and CNs. Then, CMIMO is used as a routing scheme. It consists of three phases: cluster formation, intra- and intercluster communication. In CMIMO using maximum weight selection method, the CHs are selected. Then, the selected CH nodes choose cooperative sending nodes and cooperative receiving nodes for CMIMO communication based on the weights in accordance to each nodes energy availability. Nodes with higher weights nearer to the elected CH will be the sending and receiving cooperative group nodes for the cluster. Here, coalitional Game Theory is used for the selection of CNs and selection is done using the basis as the distance and residual energy of the nodes. The coalitional game is modeled as (N, ν, V) where N is the set of players (nodes), {1, 2…, n}, ν is the characteristic function based on the network lifetime, V is the partition of N, V \( \subseteq \) N. It is, however, not suitable for short distances but effective in longer distances. There is also a delay problem.

Tyagi et al. [11] proposed a Bayesian Coalition Game-based optimized clustering in WSNs using the concepts of Learning Automata (LA) and Bayesian Coalition Game (BCG) where Sensor Nodes (SNs) are considered as the players in the game with dynamic threshold-based coalition formation among themselves, i.e., the nodes form coalition based on distance-based thresholds making a partition of the network field. In the process, a reward or penalty is assigned to every player in accordance to the finite number of actions performed. One of the SNs is elected as CH based on the subfield. So in this approach, data can be sent to BS directly or through CHs. An LA-assisted coalition game-based clustering scheme is being used. Node densities are calculated as \( G_{1} ,G_{2} \) of the calculated subregions.

If G1 = G2, LA’s action is rewarded with updates to action probability vector. Penalty is also performed according to the above. The computation of ratio of rewards and a penalty is done, and a new coalition is joined if and only if the value is lower than predefined threshold else it continues on in the current coalition. CH is chosen as the node having maximum value of PF. It broadcasts the message to CMs using TDMA schedule.

Tan et al. [12] proposed an algorithm for Cluster-Head selection based on cost sharing game known as Cost Sharing Game-based Clustering (CSGC). It is used to select CHs and fair allocation of cost. It uses a cost sharing game made up of a set N with m agents and a cost function C. It also uses Shapley value and cost shares (ξ) to distribute the total cost equitably.

In this paper in a cluster, a cost sharing game is used with three agents as \( {\text{PCH}}_{0} ,{\text{PCH}}_{1} ,{\text{PCH}}_{2} \) where one is in center, other has additional energy, and the other is in the boundary of a cluster. So a potential CHs is elected (\( {\text{PCH}}_{0} \)) and other potential CHs are recruited according to above conditions. Now, CMS are recruited. It is done by same conditions as CHs. Only non-CHs are allowed. It is used to relay data in their time slots and sleeps in other time. CHs coalition is used to share cost.

4 Conclusion

This report starts by a brief introduction of WSN, its application, and different aspects of WSN. The limitations of sensor nodes in WSNs are also briefly discussed. Game Theory and its components are introduced, and Nash Equilibrium is also noted. Game Theory is discussed as an approach to combat energy efficiency issues faced by WSNs. The different games used by paper surveyed are discussed in brief. We have discussed the cooperation or non-cooperation of nodes in a network. We have discussed the various ways the papers tried to improve energy efficiency, be it by using clusters and Cluster-Head or mitigating selfish nodes by punishing nodes or rewarding others handsomely for participating. Most papers assume the homogeneity of networks and also that communication between nodes are always there. It also shows the improvement of different protocols used for energy efficiency in subsequent papers.