Sage Journals: Discover world-class research

Abstract

Clustering techniques in wireless sensor networks have been widely utilized for their good performance in reducing energy dissipation and prolonging network lifetime. Once the cluster heads have been decided, the allocation of member nodes in the cross coverages formed by two or more clusters is critical to keep an energy balance on the cluster heads. In earlier studies, however, the allocation of member nodes simply depends on the distance or degree (the node number within the cluster heads’ communication radius) and, therefore, could cause imbalance to the cluster heads’ load and further degrade the whole wireless sensor network. To maintain the load balance of the cluster heads, in this article, game theory is introduced into the allocation problem of the member nodes. Before using the game theory approach, the number and distribution of cluster heads are first checked. If the cover rate of the cluster heads is low, then the node(s) uncovered by any cluster are randomly selected as new cluster head(s) to attain the cover rate required in the article. Furthermore, the number of cluster heads in a monitoring region is restricted. Finally, a game-based, energy-balance method is proposed and applied in the cluster-based routing protocols to improve their performance. For verification, the proposed method is embedded into the localized game theoretical clustering algorithm and hybrid, game theory–based and distributed clustering algorithm, which are two game theory and typical cluster-based routing protocols. The experimental results show that both of the improved protocols do balance the loads of the cluster heads and achieve better performance than their original versions in spanning the lifetime and balancing the energy in wireless sensor networks.

Keywords

Wireless sensor networks clustering network lifetime game theory cross coverage

Introduction

Wireless sensor networks (WSNs) have attracted broad attention from many research communities in recent years for their good performance. Their rapid development has mainly benefited from the vast advancements in hardware and wireless communication technology. The sensor nodes are basic elements of WSNs, which are characterized by their small volume, cheapness and availability. A large number of sensors can wirelessly communicate with one another. Each node senses local physical data and then forwards it to a remote base station (BS) called a sink.¹ WSNs have already been broadly applied in various fields, such as environmental monitoring,² agriculture, health care,³ disaster management,⁴ domestic systems and surveillance systems.⁵ However, the networks face a common problem in that a sensor node equipped with battery is difficult to recharge or replace since it could be deployed in untouchable environments.⁶ Thus, efficient energy management that prolongs the network lifetime becomes a hot spot.

Usually, the deployment of sensors is random or regular in a monitoring region. For energy saving, they must be efficiently organized. Clustering, an effective organization technique, is used to group the sensor nodes into independent clusters. In clustering, the role of each sensor node is the same as each of the others but can take on different responsibilities. The sensor node that serves as a cluster head (CH) is responsible for collecting data from its member nodes (MNs), aggregating the data and forwarding the aggregated data to the BS. The sensor node that serves as an MN is for sensing data and sending the data to a CH in a direct or indirect way. Cluster-based routing is known as hierarchical routing. The hierarchical routing schemes include the following protocols, such as low-energy adaptive clustering hierarchy (LEACH),⁷ hybrid energy-efficient distributed (HEED) clustering,⁸ distributed weight-based energy-efficient hierarchical clustering (DWEHC) protocol, two-level hierarchy LEACH (TL-LEACH),⁹ base station–controlled dynamic clustering protocol (BCDCP),¹⁰ threshold sensitive sensors energy or efficient sensor network protocol (TEEN).¹¹ In these protocols, the CHs suffer from the extra workload. As a result, once a normal node with less energy is chosen to be a CH, it will prematurely run out of power. Thus, how to select an appropriate CH is important to balancing the energy consumption in WSNs. In addition to hierarchical routing methods, there is flat routing. The typical flat routing protocols include flooding and gossiping, sensor protocols for information via negotiation (SPIN),¹² directed diffusion (DD)¹³ and greedy perimeter stateless routing (GPSR).¹⁴ In flat routing protocols, all of the nodes take on same tasks and functions over the whole network, and the data that the sensors obtain are sent hop-by-hop by flooding. However, in comparison with hierarchical routing, the protocols based on flat routing have difficulty in being competent for large-scale networks. Thus, the clustering routing becomes a hot research branch of routing technology in WSNs because of its various advantages, for example, more scalability, data aggregation/fusion, less load, less energy consumption and more robustness.

Game theory (GT) is usually used to study rational individual activities in interest conflicts.¹⁵ In recent years, it is introduced for the optimal selection of CHs in WSNs. It first models all of the sensor nodes; in the game, players are given different interests according to various strategies. After a competition of their interests against one another, a better balance in the energy load will be achieved.¹⁶ In the CHs’ selection game, the CH consumes more energy than the MNs. Thus, each player does not want to become a CH for its own interest. However, each node must provide services for the global interest. In this situation, it is important to devise a GT-based and energy-balance protocol between the minimization of the energy expenditure and the effective provision of necessary services.⁶ clustered routing for selfish sensors (CROSS)¹⁷ is the first protocol to use the GT to find the optimal CHs in the clustering routing. In CROSS, each sensor node is a player in the game. The strategies are devised under different payoffs that motivate players to compete for their own interests. Finally, the decision of a player (node) to be a CH or not relies on the equilibrium probability derived from the GT-based method. However, since the nodes’ transmission capability is not restricted, CROSS is not suitable for practical applications. To meet the requirements in real networks, a localized game theoretical clustering algorithm (LGCA)¹⁸ is presented. Each player communicates only with its neighbours within a fixed communication radius. Thus, LGCA is more suitable for real scenarios than CROSS. To further improve the performance of LGCA, a hybrid, game theory–based and distributed clustering algorithm (HGTD)¹⁹ is proposed, and it offers some fined-grained payoff definitions for each node under different strategies in local games and achieves higher performance over the lifetime of networks. LGCA and HGTD use the same GT strategies as CROSS. The main difference between LGCA and CROSS is in the communication ability: LGCA is restricted, while CROSS is not. In addition to the fact that the communication ability of each node is restricted, HGTD gives concrete definitions of the payoffs under different strategies and uses an iteration procedure to remove the neighbouring CHs within their proximity. In this article, we mainly use GT to analyse the optimal allocation of MNs in cross coverages by two or more clusters after the election of the CHs. In addition, in the CH-selection phase, the number and the distribution of the CHs are also considered to be important factors that affect the network performance. The main contributions of this article are listed as follows:

We first deduce an optimal number of CHs. If the distribution of CHs is uneven and their number is less than the optimal number, then new CH(s) will be automatically selected on the basis of a preset threshold.

We apply GT to determine the allocation of the sensor nodes in the cross coverage by two or more clusters. Their appropriate allocation makes the CHs and the whole network have better energy balance.

We give payoff definitions that are related to the energy consumption for the CHs in cross coverages. In the game, we also consider two distances: one distance is the distance between the CHs and normal nodes and the other is the distance between the CHs and the BS. All of the considerations are devoted to constructing an energy-efficient network.

Related work and motivation

In the cluster formation phase, it is important to appropriately allocate nodes in cross coverages to different CHs to balance the energy consumption. In earlier papers, there are two simple but typical allocation schemes^7,18,19 that are used to address the issue. One is the distance scheme in which MNs join the nearest CH to form clusters; the other is the degree scheme in which MNs join the CHs with the smallest degree. LEACH⁷ does use the distance criterion. For each non–cluster head node, joining a cluster or not depends on its received signal strength of CHs’ advertisement. When a sensor node receives signals from ambient CHs, it selects and joins the cluster for which the signal received from the CH is stronger than that from the other CHs. In general, the nearer the distance between two sensor nodes, the stronger the received signal. An LGCA has a similar allocation scheme as LEACH. It is unlikely that a HGTD uses the degree criterion in the clustering formation phase. The non-CH nodes will join the CH that has the smallest node degree. To demonstrate the difference between the two schemes, simulations are given here using the parameters shown in Table 1, and the simulation results are given in Figures 1 –8, in which six final CHs are considered to reach a good demonstration.

Table 1.

Simulation parameters.

Parameters	Values
Initial energy (J)	0.5
Packet size, L (bits)	3000
Control packet size (bits)	300
$E_{elec} (nJ / bits)$	50
$E_{Tx} (nJ / bits)$	50
$E_{Rx} (nJ / bits)$	50
$ε_{amp} (pJ / bit / m^{4})$	0.0013
$ε_{fs} (pJ / bit / m^{2})$	10
$E_{DA} (nJ / bit / message)$	5
$Area (m^{2})$	100 × 100

Figure 1.

Distance criterion allocating the nodes in the cross coverage.

Figure 2.

Six random CHs in LEACH when the monitored area is 1 × 10⁴ m².

Figure 3.

Number of member nodes of each cluster in LEACH.

Figure 4.

Energy expenditure of each CH in LEACH.

Figure 5.

Degree criterion allocated the nodes in the cross coverage.

Figure 6.

Six selected final CHs in HGTD when the monitored area is 1 × 10⁴ m².

Figure 7.

Number of member nodes in each cluster in HGTD.

Figure 8.

Energy expenditure of each node in HGTD.

In Figure 1, the two large red and green dots denote the CH in the left region and that in the right, respectively. Normal nodes are represented by small red or green dots in the cross coverage formed by two clusters and will join the cluster according to the distance criterion. Although the left cluster has more normal sensor nodes than the right cluster, the nodes in the cross coverage select the closer CH to join. Thus, it must cause the CH in the left cluster to expend more energy than that in the right cluster.

LEACH is used to show the results based on the distance criterion. In Figure 2, the CHs are randomly selected and their distribution is uneven in the monitored region. Figure 3 clearly shows that the distance criterion causes Clusters #1 and #5 to have more MNs than the other clusters. Correspondingly, CHs 1 and 5 consume more energy than the others in Figure 4.

In Figure 5, the large red and green dots also denote the left and right CHs, respectively. Normal nodes in the cross coverage formed by the two clusters will choose to join a cluster according to the degree criterion. Although the cluster in the left has more normal sensor nodes than that in the right, the nodes in the jointly managed zone will choose to join the CH that has fewer nodes. Since the green CH will serve the far nodes to raise its degree, the result is that the green CH will expend more energy than the left CH.

In Figure 6, the HGTD protocol is used to show the results for the degree criterion. It is clear that the distribution of the CHs is relatively even. However, the degree criterion in HGTD causes Clusters #1, #2 and #6 to manage more MNs than the other clusters, which is shown in Figure 7. It can also be seen that CHs 1, 2 and 5 spend more energy than the other CHs in Figure 8.

From Figures 4 and 8, it is obvious that the nodes’ allocation in the cross coverages will seriously influence the CHs’ energy balance.

From the above simulation, we found that both of the allocation criteria have their own weaknesses. Motivated by GT, in this article, it is used to allocate the MNs in the cross coverages to different CHs. Next, we plan to use GT^6,20 to model and address the situation. Additionally, before the nodes’ allocation in the cross coverages, the number and the distribution of the CHs are first considered for the purpose of achieving higher performance of the WSNs.

Overview of the system model

Network model

The proposed method is mainly applied in the two-layer network model–based protocols, which are based on the two-layer network model.²¹ In the model, the sensors in the bottom layer are responsible for collecting the data and then forwarding the data to the corresponding CH in the top layer. Finally, the CHs aggregate the data and send the data to a BS. In these protocols, the following assumptions are required:

Each node is equipped with a unique ID, which is used to label the data source;

Once the sensor nodes are placed in the monitoring region, their positions never change;

The battery energy of all of the nodes is the same and cannot be recharged, while the energy of the BS is not limited;

The distance can be measured according to the wireless radio signal power;

Each node can adapt to its transmission power according to its distance to the destination.

The radio model

A two-layer radio model⁶ is shown in Figure 9.

Figure 9.

Two-layer radio model.

To compute the nodes’ energy consumption in the model, the cost of a k-bit packet transmitted to the destination is calculated by equation (1) in Jin et al.,²² Heinzelma et al.,²³ Shokouhifar and Jalali²⁴ and Sabet and Naji²⁵

E_{Tx} (k, d) = {\begin{matrix} k E_{elec} + k ε_{fs} d^{2} & d \leq d_{0} \\ k E_{elec} + k ε_{amp} d^{4} & d > d_{0} \end{matrix}, d_{0} = \sqrt{\frac{ε_{fs}}{ε_{amp}}}

(1)

where $E_{elec}$ is the consumption on the transmitter or receiver circuitry, $ε_{fs}$ and $ε_{amp}$ are the respective amplifier characteristic constants of the free-space propagation model and the two-ray ground reflection model, d is the distance from a transmitter to a receiver and $d_{0}$ is the distance in Shokouhifar and Jalali²⁴ used to differentiate the two path loss models. The consumption on the receiver for the k-bit data packet is shown in equation (2)²⁵

E_{Rx} (k) = k E_{elec} + k E_{DA}

(2)

where $E_{DA}$ is the consumption for aggregating a one-bit packet by a CH. In this article, the above assumptions and model are usually used in the preparation phase of our method.

Proposed method

In this article, first, the optimal number of CHs is deduced for the monitoring region. Then, the distribution of CHs is checked, and if the number of the nodes that are uncovered by all clusters exceeds a given threshold, then we will randomly select new CH(s) among the uncovered nodes to meet the node coverage rate in a finite number of iteration steps. Next, the GT is introduced to model the allocation of the nodes that exist in the cross coverages.

Restriction on the number of CHs

Through a number of observations, we found that the number of CHs in a certain region is vital to the proposed method. If the CHs are beyond a certain number, then they will consume more energy for their remote communication with the BS in the WSNs. Additionally, we first give the following formula^19,21 to compute the former optimal number

C H_{opt} = \frac{S}{d_{toBS}^{2}} \sqrt{\frac{ρ ε_{fs}}{2 π ε_{amp}}}

(3)

where $d_{toBS}$ denotes the average distance from all of the CHs to the BS; $C H_{opt}$ is the optimal number in a region; $S$ is the area where the sensor nodes are deployed; and $ρ$ is the nodes’ density. In this article, we reset the CHs’ optimal value to be $σ$ , which is positive and no more than $C H_{opt}$

0 < σ \leq C H_{opt}

Many protocols are devoted to selecting CHs to balance the energy and span the lifetime in a WSN. In the CH-selection phase, to avoid having other tentative CH(s) in the communication radius of a tentative CH, in this article, we select only the attained tentative CHs that have no neighbouring tentative CH(s) as the real CHs. We assume that $σ$ is attained by subtracting the number of the most neighbouring tentative CHs among all of the tentative CHs from the total number of tentative CHs

σ = nu m_{TentativeCHs} - max (degre e^{T} (X))

where $σ$ is the optimal number of CHs in this article, $nu m_{TentativeCHs}$ is the total number of tentative CHs attained by the comparison protocols, $X$ is the set of n tentative CHs $X = {x_{1}, \dots, x_{n}}$ ; and $max (degre e^{T} (\cdot))$ denotes the number of the most neighbouring tentative CHs in the set ‘’. If the current number of CHs is less than $σ$ , then the remaining CHs are selected as real CHs based on their left energy and their current energy consumption. If the value of $σ$ is more than that of the $C H_{opt}$ , then it is set to be that of the $C H_{opt}$ .

Detecting the tentative CHs’ distribution and finding the same point sets in the cross coverages

In the initialization phase, the ‘Start’ message is broadcasted by the BS, and all of the MNs are assumed to be able to receive the message. According to the received signal strength, each node can calculate its distance to the BS. Then, each node broadcasts a ‘Hello’ message to the nodes within a radius of R. Finally, everyone knows all of their neighbours by receiving the ‘Hello’ messages. Additionally, in this article, our approach starts after the tentative CHs’ selection. We first check the distribution of the tentative CHs and then find the sets of the nodes in the different cross coverages; next, the GT method is used to allocate the sensor nodes to appreciate the clusters.

Algorithm 1 is proposed to check the distribution of the current CHs and to reselect new CH(s) among the uncovered nodes. In this algorithm, $threshol d_{set}$ works as the cover rate by the CHs, and it is set at 0.8. When the cover rate reaches this value, the iteration procedure will stop. First, the number of sensor nodes covered by the tentative CHs (including CHs) is known by the BS in the initial phase. The tentative CHs will send their IDs to the BS and then the new optimal number in this article must be calculated by the BS. The BS also calculates the total number $Su m_{allMNs}$ covered by the CHs. If the number is less than the value $θ$ , which is a third of the total number of all nodes in the article, the BS sends the message (which includes the IDs of the uncovered nodes, the current number of covered nodes and the command ‘start generator’) to the uncovered nodes. The message ‘start generator’ asks these nodes to randomly produce a random number. If the random number of the node(s) is more than the threshold $threshol d_{num}$ set inside all of the uncovered sensors, the node(s) calculates the sum of the number of their MNs and the original number of members in its own storage. Then, the covered nodes $Su m_{allMNs}$ are recalculated by the uncovered sensors. Once the ratio $curren t_{ratio}$ of the covered nodes $Su m_{allMNs}$ to the total number is more than $threshol d_{set}$ or the total number of CHs is more than $σ$ , the iterations will stop. Finally, if several CHs exist in their communication radius, then only one CH with the most energy is selected as the final CH.

Algorithm 1. Checking the distribution of the tentative CHs.
1. $Su m_{allMNs} = 0$ ; 2. $newCHs = 0$ ; 3. $\begin{matrix} Su m_{allCHs} is attained by LGCA or HGTD in which no tentative CHs are in their proximity \end{matrix}$ ; 4. $curren t_{ratio} = \frac{Su m_{allMNs}}{nu m_{allnodes}}$ ; 5. $BS_CHmsg (CHI D_{i}, C H^{i} nodeIDs, σ)$ ; 6. $while Msg = = ture (BS : monitoring)$ ; 7. $if Su m_{allCHs} + Nu m_{newCHs} \geq σ$ 8. $sor t_{residualEnergy} (tentativeCHs) in descending order$ ; 9. $first σ tentativeCHs are selected as realCHs$ ; 10. $break$ ; 11. $endif$ 12. $while curren t_{ratio} < threshol d_{set}$ 13. $BS_msg (NodeID s_{uncovered}, ″ startgenerator ″, Su m_{allMNs})$ ; 14. $if Ran d_{num} > threshol d_{num}$ 15. $Nu m_{newCHs}$ = $produce (new tentativeCHs)$ ; 16. $Su m_{allMNs} = Su m_{allMNs} + Nu m_{newMembers}$ ; 17. $curren t_{ratio} = \frac{Su m_{allMNs}}{nu m_{allnodes}}$ ; 18. $if Su m_{allMNs} > θ$ 19. ${Num}_{originalCHs} = {Num}_{originalCHs} + Nu m_{newtentativeCHs}$ ; 20. $CH_BSmsg (CHI D_{i}, I D_{newCHs})$ ; 21. $endif$ 22. $endif$ 23. $endwhile$ 24. $endwhile$ 25. $BS_msg (Allnodes, ″ Begin ″)$ .

Algorithm 1. Checking the distribution of the tentative CHs.

Su m_{allMNs} = 0

;
2.

newCHs = 0

;
3.

\begin{matrix} Su m_{allCHs} is attained by LGCA or HGTD in which no tentative CHs are in their proximity \end{matrix}

;
4.

curren t_{ratio} = \frac{Su m_{allMNs}}{nu m_{allnodes}}

;
5.

BS_CHmsg (CHI D_{i}, C H^{i} nodeIDs, σ)

;
6.

while Msg = = ture (BS : monitoring)

;
7.

if Su m_{allCHs} + Nu m_{newCHs} \geq σ

sor t_{residualEnergy} (tentativeCHs) in descending order

;
9.

first σ tentativeCHs are selected as realCHs

;
10.

break

;
11.

endif

12.

while curren t_{ratio} < threshol d_{set}

13.

BS_msg (NodeID s_{uncovered}, ″ startgenerator ″, Su m_{allMNs})

;
14.

if Ran d_{num} > threshol d_{num}

15.

Nu m_{newCHs}

produce (new tentativeCHs)

;
16.

Su m_{allMNs} = Su m_{allMNs} + Nu m_{newMembers}

;
17.

curren t_{ratio} = \frac{Su m_{allMNs}}{nu m_{allnodes}}

;
18.

if Su m_{allMNs} > θ

19.

{Num}_{originalCHs} = {Num}_{originalCHs} + Nu m_{newtentativeCHs}

;
20.

CH_BSmsg (CHI D_{i}, I D_{newCHs})

;
21.

endif

22.

endif

23.

endwhile

24.

endwhile

25.

BS_msg (Allnodes, ″ Begin ″)

Algorithm 2. Finding the sets of the same cross coverage.
1. $CHs_msg (CHID)$ ; 2. $RecMSG (allofCHs, NormalNod e_{i})$ ; 3. $ComputeNum (C H_{num}) for each node$ ; 4. $C H_{initalNum} = 2$ ; 5. $while (C H_{num} < = Nu m_{CHs})$ 6. $NormalNod e_{i}_msg (NodeID, NumofCH, CHIDs)$ ; 7. $if (NumofC H_{i} = = NumofC H_{j} and CHID s_{i} = = CHID s_{j})$ 8. $isameCoverageID = NewID (NormalNod e_{i}, NormalNod e_{j})$ ; 9. $endif$ 10. $C H_{initalNum} = C H_{initalNum} + 1$ ; 11. $endwhile$

Algorithm 2. Finding the sets of the same cross coverage.

CHs_msg (CHID)

;
2.

RecMSG (allofCHs, NormalNod e_{i})

;
3.

ComputeNum (C H_{num}) for each node

;
4.

C H_{initalNum} = 2

;
5.

while (C H_{num} < = Nu m_{CHs})

NormalNod e_{i}_msg (NodeID, NumofCH, CHIDs)

;
7.

if (NumofC H_{i} = = NumofC H_{j} and CHID s_{i} = = CHID s_{j})

isameCoverageID = NewID (NormalNod e_{i}, NormalNod e_{j})

;
9.

endif

10.

C H_{initalNum} = C H_{initalNum} + 1

;
11.

endwhile

The algorithm below is used to determine the point sets in the cross coverages (Table 2). This procedure consists of four steps. First, the CHs send the message CHID within their specific communication radius; second, normal nodes in the cross coverages receive the message and record it; third, normal nodes send messages that concerned with its node ID NodeID, the number of CHs NumofCH and the CHs’ ID CHIDs in their specific radius; and finally, the normal nodes in the cross coverage exchange messages with one another. Next, each normal node begins to compare the number of CHs, NumofCH, of the node ID NodeID within its radius. If the number for the two nodes is not equal, then it is clear that they are not in the same cross coverage. If the number is equal, then the normal nodes continue to compare their CHIDs. If their CHIDs are the same, then they belong to the same cross coverage. The process is not finished until all of the point sets in the cross coverages are formed.

Table 2.

The payoffs for the simple two-player clustering formation game.

	$CH selecting$	$CH non - selecting$
$CH selecting$	$(m - e, m - e)$	$(m - e, m)$
$CH non - selecting$	$(m, m - e)$	$(0, 0)$

CH: cluster head.

Game application and equilibria analysis

The GT algorithm in this article works in the phase of the clustering formation, which lies in the red region in Figure 10. In Figure 10, first, the data stream is divided into frames, and each frame is also divided into time slots. Each cluster member is allocated one slot. When all of the clusters have been constructed, the first cluster member will be awaked. In the time slot of the MN, its data will be forwarded to its corresponding CH and then the next node repeats the actions similar to the previous node in rapid succession. Additionally, the time slots also contain the data with a guard period if needed for synchronization. Finally, the CHs will aggregate all of the collected data and send it to the BS.

Figure 10.

Work flow with new method (red regions).

Next, we model the game. In Figure 11, the big white circles denote the game players (CHs) and the small white circles (MNs) represent the selected objects in the cross coverage simultaneously covered by clusters A, B and C; the players A, B and C compete for each selected node (MN; $n_{i}$ in Figure 11 is the ith node in the cross coverage).

Figure 11.

Game with three players (CHs) competing for each normal node in the cross coverage.

To allocate the normal nodes in the cross coverage into an appreciated cluster, the clustering competition node game (CCNG) is proposed. The responsibility of a CH in the game is to collect data from the MNs that lie within its radius and to send the aggregated data to a BS, which is usually placed far from all of the sensors. We model the game as $CCNG = 〈 H, T, Π 〉$ , where H is the set of all players, $T = {t_{1}, \dots, t_{i}, \dots, t_{N}}$ is the set of the used strategies and $Π = {Π_{1}, \dots, Π_{i}, \dots, Π_{N}}$ is the set of cost functions of the players. The players are the CHs which participate in each round of the network activity. If pure strategies are used, then the strategy space corresponds to two choices: a player (CH) selects the current node in the cross coverage or not. Letting S be the strategy ‘selecting the node as its own member’ and NS the strategy ‘do not select it’, the strategy space is $S = {Select, NotSelect} = {S, NS}$ . With regard to payoffs, if a CH (player) does not choose a normal node in the cross coverage and if no other CHs choose the node, its payoff will be zero because the data of this node will never be collected and sent to the BS. If at least one other CH declares that this node is its own member, then its payoff will be $m$ , that is, the gain from successfully collecting the data of this node. Finally, if the player declares this node to be its member, then its payoff for successfully collecting the data m will be reduced by an amount that is equal to the cost e of serving for the node. Thus, in this case, the final payoff will be $m - e$ .

Let us now discuss the possible equilibria in the case of two players. Their payoffs are summarized in Table 2. It is obvious that the game strategies are symmetrical because the payoff is only related to the strategies and has nothing to do with who they are.

Both the strategy $(S, S)$ and $(NS, NS)$ are not Nash equilibrium. If two players select the strategy S, then their payoff will be $m - e < m$ . To obtain more payoff, they are better off changing their strategy to $NS$ . In contrast, if they select NS, then any player would prefer to deviate and select an MN as its member because this approach will lead to a positive payoff. In GT, the Nash equilibrium is a solution concept for a non-cooperative game that involves 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 his or her own strategy.²⁶ If each player has chosen a strategy and no player can benefit by changing strategies while the other players keep theirs unchanged, then the current set of strategy choices and the corresponding payoffs constitute a Nash equilibrium. According to the definition, in our case, one player selects $S$ and the other selects $NS$ and then both players have no incentive to change their choice. Therefore, the strategy combination $(S, NS)$ is a Nash equilibrium. Additionally, $(NS, S)$ is a Nash equilibrium for the same reason. Although these two strategies, $(S, NS)$ and $(NS, S)$ , are Nash equilibria, there is no symmetrical Nash equilibrium in the nodes’ selection game because no common strategy for all players exists that results in an equilibrium.

Furthermore, we assume that N players play the game, and we let $T = {t_{1}, \dots, t_{i}, \dots, t_{N}}$ be the vector representation of the strategies played by the players. If no player selects a node in the cross coverage, then all players have no payoffs (the total payoff is zero). If at least one player selects the node as its member, then its payoff will be $m$ after reducing it by the cost of serving the node, and the other players’ payoffs will be $m$ . Therefore, the utility function $Π_{i} (T)$ of an arbitrary player $i$ has the following form

Π_{i} (T) = {\begin{matrix} 0, & i f \forall i \in {1, 2, \dots, N}, & t_{i} = N S \\ m_{i}, & i f t_{i} = N S a n d o n l y o n e & t_{j} (\neq t_{i}) = S \\ m_{i} - e_{i}, & i f t_{i} = S \end{matrix}

(4)

in which the payoff is $m_{i}$ if only one CH selects the ith node as its member but the others not, and the payoff is $m_{i} - e_{i}$ if a CH receives the ith node as its member. It is obvious that $m_{i} - e_{i} < m_{i}$ . Next, some helpful propositions are listed, and we do not prove them because they are straightforward:

Proposition 1. For the symmetrical clustering game, the strategy $T_{allS} = {S, \dots, S, \dots, S}$ is not a Nash equilibrium.

Proposition 2. For the symmetrical clustering game, the strategy $T_{allNS} = {NS, \dots, NS, \dots, NS}$ is not a Nash equilibrium.

Proposition 3. For the symmetrical clustering game, the strategy where a single player plays $S$ and all other players play $NS$ is a Nash equilibrium, and there are N Nash equilibria in the game.

Proposition 4. For the symmetrical clustering game, no symmetric pure strategies with Nash equilibria exist.

To permit the game in the article to have symmetrical Nash equilibria, we must allow the players to play mixed strategies, which means that the players choose their strategies randomly following a probability distribution. In other words, every player now has a probability of selecting a node in its cross coverage as its member and a probability of not doing so. Let us denote the probability of playing $S$ as p and the probability of playing $NS$ as q = 1 − p.

After the above analysis, we will compute the equilibrium probability $p_{i}$ , which is the probability that player $i$ chooses the strategy S. It is based on the Theorem 1,¹⁷ as follows.

Theorem 1

For the symmetrical clustering game, a symmetric mixed strategies Nash equilibrium exists, and the equilibrium probability p that a player declares itself as a cluster head is

p (i) = 1 - w_{i}^{1 / | Nn (i) + 1 |}

(5)

where $w_{i} = e_{i} / m_{i} < 1$ ; e_i is the overhead of selecting the ith member; $m_{i}$ is the payoff of the ith member; and $| Nn (i) |$ denotes the element number of set $Nn (i)$ , which is composed of the ith player’s neighbours.

Calculating equilibrium probabilities

For CH $i$ , if the strategy $NS$ is selected in the local CCNG and if at least one other node in the cross coverage selects the strategy $S$ , then its payoff $m_{i}$ can be calculated by

m_{i} = \frac{d_{j}^{i}}{r} E_{c m_{i}}^{j} + \frac{D_{i}}{Max (D_{1}, D_{2}, \dots, D_{num})} E_{c h_{i}}

(6)

where $d_{j}^{i}$ denotes the distance between the jth node in the cross coverage and the jth CH, D_i denotes the distance between the jth CH and the BS, r is $d_{0}$ in equation (1), $Max (D_{1}, D_{2}, \dots, D_{num})$ is the largest distance among all of the players (CHs) that formed the cross coverage, $E_{c m_{i}}^{j}$ is the energy consumption that is expended by transmitting the data of the jth normal node to the ith CH and $E_{c h_{i}}$ is the average energy expenditure when the ith CH sends the fusion data to the BS. If a CH chooses strategy S, then its payoff $m_{i} - e_{i}$ can be written as follows

m_{i} - e_{i} = \frac{D_{i}}{Max (D_{1}, D_{2}, \dots, D_{num})} E_{c h_{i}}

(7)

where $e_{i}$ is the overhead of selecting the ith member. According to equations (6) and (7), $e_{i}$ can be attained as follows

e_{i} = \frac{d_{j}^{i}}{r} E_{c m_{i}}^{j}

(8)

Let $w_{i} = e_{i} / m_{i}$ ; then, we obtain the following equation

w_{i} = \frac{\frac{d_{j}^{i}}{r} E_{c m_{i}}^{j}}{\frac{d_{j}^{i}}{r} E_{c m_{i}}^{j} + \frac{D_{j}}{Max (D_{1}, D_{2}, \dots, D_{num})} E_{c h_{i}}}

(9)

In equation (9), it is clear that $w_{i}$ must be positive. Then, based on equation (5), the ith player’s equilibrium probability is described as follows

p (i) = 1 - w_{i}^{1 / | Nn (i) + 1 |}

(10)

in which $| Nn (i) |$ is the number of nodes that are only in the ith cluster; if the CH gets a new node in the cross coverage, then $| Nn (i) | = | Nn (i) | + 1$ . Furthermore, we must obtain the equilibrium probability under the influence of the accumulated cost of a player

p (i) = (1 - w_{i}^{1 / | Nn (i) + 1 |}) \cdot e^{- M_{i}}

(11)

where $e^{| * |}$ is the e exponential function, and $M_{i}$ denotes the accumulated cost of CH i, and $M_{i}$ is calculated as follows

M_{i} = \sum_{k = 1}^{N - 1} (α \cdot {num}_{i}^{k} E_{c m_{i}}^{j} + (1 - α) \cdot E_{c h_{i}}), α = {\begin{matrix} 1, is a MN \\ 0, is a CH \end{matrix}

(12)

in which N denotes the current round number, and ${num}_{i}^{k}$ is the number of MNs managed by the ith CH in the kth round.

When the ith CH plays the game, its payoff m_i is calculated by equation (6). Next, the values $E_{c m_{i}}$ and $E_{c h_{i}}$ can be attained before playing the CCNG. If the free-space propagation model is adopted for the intra-cluster communication, then $E_{c m_{i}}$ can be calculated as follows

E_{c m_{i}}^{j} = dat a_{L} \cdot E_{elec} + dat a_{L} \cdot ε_{fs} d_{itoCH}^{2}

(13)

where $dat a_{L}$ is the size of the data packet that is collected by each sensor node in the cross coverage per round, and $d_{itoCH}$ is the practical distance to the competing CH of node i. Additionally, if we adopt the two-ray ground reflection model for the data transmission from a CH to a BS, we have the following equation

E_{c h_{i}} = Ndnu m_{i} \cdot dat a_{L} \cdot E_{elec} + (Ndnu m_{i} + 1) \cdot dat a_{L} \cdot E_{DA} + dat a_{L} \cdot ε_{amp} \cdot d_{itoBS}^{4}

(14)

where $Ndnu m_{i}$ is the ith player’s node degree; $E_{DA}$ is the consumption upon aggregating a one-bit data packet; and $d_{itoBS}$ is the distance from player $i$ to BS, which can be attained by measuring the signal strength received when the BS begins to broadcast the ‘Start’ message. Finally, the specific value of the equilibrium probability for a player (CH) can be calculated according to equations (11), (13) and (14).

Decision of the normal nodes

When $n$ players (CHs) compete for a node in the cross coverage, according to equation (11), we attain their equilibrium probabilities and assign such probabilities to $w_{1}, w_{2}, \dots, w_{n}$

\begin{matrix} w_{1} = p_{1} \\ w_{2} = p_{2} \\ ⋮ \\ w_{n} = p_{n} \end{matrix}

Then, we obtain in Figure 12,

E p_{i} = \frac{w_{i}}{w_{1} + w_{2} + \dots + w_{n}} .

(15)

In equation (15), $E p_{i}$ is the ith regular equilibrium probability. Next, a random number $rod$ is generated between 0 and 1, that is

E p_{i} \geq rod \geq E p_{j}

(16)

Figure 12.

Regular equilibrium probability.

If the value of $rod$ is more than $E p_{i}$ and less than $E p_{j}$ , then the MN selects the $C H_{j}$ with the larger value to join. Then, another node participates in the next game, and it joins the appropriate CH. The process continues up to the completion of the allocation of the normal nodes in all cross coverages.

The main goal of the proposed algorithm is to balance the energy consumption for all CHs by the allocations of the nodes in the cross coverages at the clustering formation phase. Our approach is not completely independent from the CH election protocols, and any other cluster-based routing protocols can use it to obviously improve their performance.

Performance evaluation

Our method is mainly applied in the setup phase, as given in Figure 10. Additionally, allocating the nodes in the cross coverages and reselecting better CHs are our concrete work. In this section, we attempt to further analyse the time consumption of our method.

In detail, on the basis of the CH-selection methods, we first restrict the optimal number of CHs; under the restriction of the optimal number of CHs, we randomly select the uncovered nodes with the larger coverage ratio and the more residual energy to be the CHs. Once the optimal number of CHs is more than or equal to the optimal number set by us, the iteration process will terminate and be clear in Algorithm 1. In this process, the $BS$ has already recorded the position of each node, the distances between one another and the neighbours’ number of each node in its communication radius at the initial phase. In the allocation game, the IDs and the residual energy of the competitive nodes and the corresponding CHs must be sent to the $BS$ . In addition, the $BS$ calculates the equilibrium probabilities based on the their positions and residual energy, which were saved in the $BS$ and finally sends the participative label to the competitive node.

On the basis of the above analysis, it can be seen that the energy consumption is only cost in the information exchange between $MNs$ and the $BS$ and $CHs$ and $BS$ . The $BS$ makes the final decisions: selecting the remaining CHs and allocating the nodes in the cross coverages. Additionally, we assume that the power of the $BS$ is not limited. Thus, we compute only the energy and time consumption by one-way transmission from the $MNs$ and $CHs$ to the $BS$ . In our method, the time and energy consumption $Cos t^{t, e}$ of all of the nodes in each round can be modelled, which is clearly shown in Figure 13

Cos t^{t, e} = \sum_{\forall i \in N} M^{t, e} (M N_{i}, BS) + \sum_{\forall j \in C} M^{t, e} (C H_{j}, BS)

in which $M^{t, e} (P, Q)$ is the time and energy consumption when $P$ and $Q$ communicate with each other, $N$ is the set of all non-CH nodes, $C$ is the set of all CHs, $i$ is the index set of all non-CH nodes and $j$ is the index set of all CHs.

Figure 13.

Communication among MN, CH and BS.

The above formula can be further divided into two parts: one part is

Cos {t^{t, e}}_{Phase 1} = \sum_{\forall i \in N} M^{t, e} (M N_{i}, BS)

and the other part is

Cos {t^{t, e}}_{Phase 2} = \sum_{\forall i \in N} M^{t, e} (M N_{i}, BS) + \sum_{\forall j \in C} M^{t, e} (C H_{j}, BS)

The first of the above two formulas is the phase in which the distribution of CHs will be checked and new CH(s) will be generated if CHs do not attain the cover ratio set by us. It assumes that $Sum (N)$ is the total number of non-CH nodes, and $Sum (C)$ is the total number of tentative CHs attained by other CH-selection methods. The best case of selecting new CH(s) from the $Sum (N)$ nodes is that the number $σ - Su m_{allCHs}$ is precisely the $σ - Su m_{allCHs}$ non-CH nodes that first send their information to the BS. This approach assumes that a node will send k-bit data to the BS. According to the two-layer radio model equation (1), the energy consumption is as follows

E_{beCHs}^{Tx} = (σ - Su m_{allCHs}) \cdot k \cdot (E_{elec} + ε_{amp} d^{4})

in which $E_{beCHs}^{Tx}$ is the energy consumption for generating new CHs when sending the information to the BS, $d$ is the distance between the normal node and the BS and $E_{elec}$ and $ε_{amp}$ are introduced in Table 1.

However, the worst case of selecting new CH(s) from $Sum (N)$ nodes is that each of the $Sum (N)$ nodes will send their information to the BS. Then, the energy consumption is

E_{beCHs}^{Tx} = Sum (N) \cdot k \cdot (E_{elec} + ε_{amp} d^{4})

The second formula is the phase in which the BS decides which CHs will manage the nodes in the cross coverages. This approach assumes that the total number of MNs in the cross coverages is ${Num}_{CC}^{MNs}$ , and the number of participating CHs is ${Num}_{CC}^{CHs}$ . It assumes that a node will send k-bit data to the BS, and then

E_{CC}^{Tx} = ({Num}_{CC}^{MNs} + {Num}_{CC}^{CHs}) \cdot k \cdot (E_{elec} + ε_{amp} d^{4})

in which $E_{CC}^{Tx}$ is the energy consumption in the games when the game members send information to the BS.

The cover ratio in this article can maintain a higher value than that in earlier papers. Thus, there will be fewer isolated nodes, which can save more time than the other approaches. It is worthwhile to mention that the $BS$ takes the main tasks in our method. Thus, the main consumption in time and energy is on the $BS$ . Additionally, the $CHs$ and $MNs$ mainly send and receive the information and then the whole WSN is organized and runs.

Simulation results

In this section, we describe the simulations. The parameters used in the experiments are given in Table 1. Additionally, the simulation results are given in this section. Then, we evaluate the performance of the proposed method by analysing the results.

Simulation environment

A rectangular area with the size $S$ is simulated as the sensor field. We assume that all of the nodes are randomly placed and their distribution density in the area is $ρ$ . The BS is outside of the monitoring region. Each sensor node broadcasts its message within the radius $R$ . Let $C H_{opt}$ denote the optimal number of CHs in this network. Therefore, the average area of a cluster can be described as $S / C H_{opt}$ , and the communication radius $R$ can be set by Yang et al.¹⁹ as follows

R = \sqrt{\frac{S}{π C H_{opt}}}

(17)

In addition, the predefined parameter $w$ in LGCA is calculated as follows

w = \frac{1}{n} \sum_{i = 1}^{n} w_{i}

(18)

Now, we can evaluate the performance of our approach under the following situations.

For various values of the network size S (L×W m²) of the network, the protocols LGCA and HGTD combined with our approach, which are, respectively, called the improved LGCA and HGTD, are compared with LGCA and HGTD themselves. The communication radius R has already been calculated by equation (17). The values of S are chosen as 50×100, 100×100, 100×150, 150×150, 150×200 and 200×200 m². The BS is located on position (L/2, W + 50), and the node density $ρ$ is set to one node per 50 m².

Analysis of results

First, we show the performance in terms of the energy consumption. Figure 14(a) and (b) is the results of LGCA and the improved LGCA, separately, at the 200th round. It is clear that the energy allocation of B is more even than that of A. C and D are the results of HGTD and the improved HGTD. We can see that the CHs in the improved HGTD use their energy evenly but the original HGTD does not. This finding indicates that the GT plays an important role in balancing the energy consumption.

Figure 14.

Comparison of the improved protocols with their original versions in terms of the energy consumption at the 200th round when S = 1 × 10⁴ m²: (a) LGCA, (b) improved LGCA, (c) HGTD and (d) improved HGTD.

Figure 15 compares the number of CHs in LGCA, HGTD and their improved versions for S = 1×10⁴ m². The original optimal number of CHs is derived from equation (3). The number of CHs in the improved protocols is lower than the original optimal number and has a small variance, while LGCA and HGTD show the opposite. It is clear that the variance of the number of CHs is too large to maintain their energy balance.

Figure 15.

Original optimal number of CHs in equation (3), and comparison of the optical numbers of the CHs among LGCA, HGTD and their improved versions when S = 1 × 10⁴ m².

In WSNs, the network lifetime is a very important evaluation criterion for clustering protocols, and it is defined by the lifespan of the first node, which depletes its energy in the network. Figure 16 shows a comparison of the network lifetime among LGCA, HGTD and their improved versions with different network sizes S. In terms of the network lifetime, this figure shows that the improved protocols outperform their original version in all cases of S. With the increase in S, all protocols have a downward trend in S, which means that the CHs cost more energy to send their information to the BS. Additionally, it shows that HGTD is much better than LGCA, which indicates that the CH-selection mechanism is important to the energy balance. The improved protocols have longer lifetimes than their originals. The reason is that our method in the clustering formation phase has good performance. Especially when the monitoring region S is chosen to be 200×200 m², the improved LGCA outperforms HGTD. The figure also indicates that our method can significantly improve the performance of the original protocols. When the monitoring region S is 100×150 m², although the improved LGCA is better than the original LGCA, the efficiency is not obvious. The reason is that the selection of CHs in the original LGCA is not good in the area. Additionally, the improved LGCA inherited some of the CHs from the original LGCA. If the selection of CHs in the original LGCA is not good, then the improved LGCA is also not good. Thus, in Figure 16, this relationship leads the improved LGCA to not obtain a longer lifetime in this S. From the experimental comparison in Figure 16, we also found the fact that the better the CHs that are selected, the larger the number of MNs in cross coverages is. Therefore, the GT plays an important role in allocating the MNs well.

Figure 16.

Comparison of the network lifetimes among LGCA, HGTD and their improved versions for several sizes of the network.

Figure 17 shows the comparison of the rounds until 10% of the nodes die among LGCA, HGTD and their improved versions for different sizes of the network. When S is more than or equal to 150×200 m², the improved HGTD is quicker to have 10% of the nodes die than the original HGTD, while the improved LGCA starts from 100×150 m². This finding indicates that once the first node begins to die, many nodes will quickly die. However, when S is less than 150×150 m², HGTD with our method has more rounds than the original HGTD in attaining the results; whereas, when S is less than 100×150 m², the improved LGCA has more rounds in attaining the above result than the original version.

Figure 17.

Comparison of rounds until 10% of the nodes die among LGCA, HGTD and their improved versions for several sizes of the network.

The network lifetime is a very important metric for the performance evaluation of the clustering protocols since it gives the moment when the network nodes begin to die. In addition, the lifespan of the last dead node is also important. Figure 18 shows a comparison of rounds until the last node dies among the four protocols for different sizes of the network. The improved LGCA has fewer rounds than the original LGCA in finishing its work (until the last node dies). In addition, the energy is used evenly in the improved version. The improved HGTD is almost the same as its original version in terms of the death of the last node, which indicates that all of the nodes in the improved HGTD can evenly use their energy and can effectively work in the network.

Figure 18.

Comparison of rounds until the last node dies among LGCA, HGTD and their improved versions for several sizes of the network.

To show the performances of the improved protocols in detail, Figure 19 gives the number of alive nodes in each round for each of the four protocols when S = 1×10⁴ m². It is clear that the improved LGCA has a shorter interval than its original version from the death of the first node to the last node, which indicates that the energy consumption among the nodes is well allocated in the improved LGCA but not in the original. At the same time, both HGTD and its improved version have shorter intervals. It is clear that both improved versions significantly outperform their original in terms of the first node dead and the last node dead.

Figure 19.

Number of nodes alive versus rounds for LGCA, HGTD and their improved versions when S = 1 × 10⁴ m².

Conclusion

In the cluster formation phase, the normal nodes’ allocation becomes important to the energy balance of the CHs. However, in earlier work, it depends only on some simple methods, which seriously affect the energy balance of the CHs and further degrade the performance of the whole WSN. Additionally, the number and distribution of the CHs are also important in our approach. If the distribution of the CHs is uneven, then the uncovered node(s) by any cluster will be selected as new CH(s) to attain a high coverage rate. Moreover, the number of CHs in a monitoring region is also restricted. Finally, a game-based, energy-balance method is proposed to apply in the cluster-based routing protocols for improving the WSNs’ performance. We select two clustering protocols, LGCA and HGTD, to compare with their improved versions combined with our method. The simulation shows that the improved protocols achieve better performance. In the future, we will apply the GT to analyse the multi-hop interest situation.

Footnotes

Appendix

Algorithm 2.

Notations used in Algorithm 2.

Notation	Description
$CHID$	ID of each CH
$allofCHs$	All of the CHs
$NormalNod e_{i}$	Each non-CH node
$C H_{num}$	The number of CHs
$C H_{initalNum}$	An initial variable for the number of CHs
$Nu m_{CHs}$	The total number of CHs
$NodeID$	ID of a node
$CHIDs$	IDs of CHs
$NumofC H_{i}$	The number of CHs that communicate with the ith node
$CHID s_{i}$	IDs of CHs that communicate with the ith node
$CHID s_{j}$	IDs of CHs that communicate with the jth node
$NewID$	Produce a new ID
$isameCoverageID$	ID belongs to the same cross coverage
$NormalNod e_{i}$	The ith normal node
$NormalNod e_{j}$	The jth normal node

CH: cluster head.

Academic Editor: Thomas Wettergren

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by Project Supported by Scientific and Technological Research Program of Chongqing Municipal Education Commission (Grant No. KJ15012001), Fundamental Research Funds for the Central Universities in China (Grant No. 106112015CDJRC161203), Chongqing Postdoctoral Special Funding Project (Grant No. Xm2015063) and Major Program of National Natural Science Foundation of China (Grant Nos 61472053, 91438104 and 91420102).

References

Kong

Zhan

et al . A novel image mosaicking algorithm for wireless multimedia sensor networks. Int J Distrib Sens N 2013; 9(10): 719640.

Yang

Zhang

et al . Integration of wireless sensor networks in environmental monitoring cyber infrastructure. Wirel Netw 2010; 16(4): 1091–1108.

Pandian

Mohanavelu

Safeer

et al . Vest: wearable multi-parameter remote physiological monitoring system. Med Eng Phys 2008; 30(4): 466–477.

Pogkas

Karastergios

Antonopoulos

et al . Architecture design and implementation of an ad-hoc network for disaster relief operations. IEEE T Ind Inform 2007; 3(1): 63–72.

Byun

Jeon

Noh

et al . An intelligent self-adjusting sensor for smart home services based on zigbee communications. IEEE T Consum Electr 2012; 58(3): 794–802.

AlSkaif

Zapata

Bellalta

Game theory for energy efficiency in wireless sensor networks: latest trends. J Netw Comput Appl 2015; 54: 33–61.

Heinzelman

Chandrakasan

Balakrishnan

. Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd annual Hawaii international conference on system sciences, Maui, HI, 7 January 2000, vol. 2, pp.1–10. New York: IEEE.

Younis

Fahmy

HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks. IEEE T Mobile Comput 2004; 3(4): 366–379.

Loscri

Morabito

Marano

. A two-levels hierarchy for low-energy adaptive clustering hierarchy (TL-LEACH). In: Proceedings of the IEEE 62nd vehicular technology conference (VTC-2005-Fall), Dallas, TX, 28 September 2005, pp.1809–1813. New York: IEEE.

10.

Bajaber

Awan

. Base-station controlled dynamic clustering protocol. In: Proceedings of the international conference on advanced information networking and applications, Bradford, 26–29 May 2009.

11.

Haas

Halpern

Gossip-based ad hoc routing. IEEE ACM T Network 2006; 14(3): 479–491.

12.

Kulik

Heinzelman

Balakrishnan

Negotiation-based protocols for disseminating information in wireless sensor networks. Wirel Netw 2002; 8(2–3): 169–185.

13.

Intanagonwiwat

Govindan

Estrin

et al . Directed diffusion for wireless sensor networking. IEEE ACM T Network 2003; 11(1): 2–16.

14.

Karp

Kung

. GPSR: greedy perimeter stateless routing for wireless networks. In: Proceedings of the 6th annual international conference on mobile computing and networking, Boston, MA, 6–11 August 2000, pp.243–254. New York: ACM.

15.

Akkarajitsakul

Hossain

Niyato

et al . Game theoretic approaches for multiple access in wireless networks: a survey. IEEE Commun Surv Tut 2011; 13(3): 372–395.

16.

Liu

A survey on clustering routing protocols in wireless sensor networks. Sensors 2012; 12(8): 11113–11153.

17.

Koltsidas

Pavlidou

. A game theoretical approach to clustering of ad-hoc and sensor networks. Telecommun Syst 2011; 47(1–2): 81–93.

18.

Xie

Sun

Zhou

et al . An efficient clustering protocol for wireless sensor networks based on localized game theoretical approach. Int J Distrib Sens N 2013; 9(8): 476313.

19.

Yang

Y-Z

Zhong

Y-C

et al . A hybrid, game theory based, and distributed clustering protocol for wireless sensor networks. Wirel Netw 2016; 22(3): 1007–1021.

20.

Khanmirza

Yazdani

Game of energy consumption balancing in heterogeneous sensor networks. Wirel Commun Mob Com 2016; 16(12): 1457–1477.

21.

Bajaber

Awan

An efficient cluster-based communication protocol for wireless sensor networks. Telecommun Syst 2014; 55(3): 387–401.

22.

Jin

Gao

Song

J-Y

et al . Passive cluster-based multipath routing protocol for wireless sensor networks. Wirel Netw 2013; 19(8): 1851–1866.

23.

Heinzelman

Chandrakasan

Balakrishnan

An application-specific protocol architecture for wireless microsensor networks. IEEE T Wirel Commun 2002; 1(4): 660–670.

24.

Shokouhifar

Jalali

A new evolutionary based application specific routing protocol for clustered wireless sensor networks. AEU Int J Electron Commun 2015; 69(1): 432–441.

25.

Sabet

Naji

HR.

A decentralized energy efficient hierarchical cluster-based routing algorithm for wireless sensor networks. AEU Int J Electron Commun 2015; 69(5): 790–799.

26.

Osborne

Rubinstein

A course in game theory. Cambridge, MA: MIT Press, 1994.

An energy-balance and game-theory-based cluster formation method for wireless sensor networks

Abstract

Keywords

Introduction

Related work and motivation

Overview of the system model

Network model

The radio model

Proposed method

Restriction on the number of CHs

Detecting the tentative CHs’ distribution and finding the same point sets in the cross coverages

Game application and equilibria analysis

Theorem 1

Calculating equilibrium probabilities

Decision of the normal nodes

Performance evaluation

Simulation results

Simulation environment

Analysis of results

Conclusion

Footnotes

Appendix

Declaration of conflicting interests

Funding

References