Sage Journals: Discover world-class research

Abstract

Clustering is a popular method to achieve energy efficiency and scalable performance in large-scale sensor networks. Many clustering algorithms were proposed to use energy efficiently, extend network life span, and improve data transfer. Clustered routing for selfish sensors is a recently proposed algorithm based on game theory. In clustered routing for selfish sensors, the sensor nodes campaign to be cluster heads in order to achieve equilibrium probability. However, this algorithm needs global information for the computation of probability and disregard the uneven energy dissipation from different nodes that serve as cluster heads, thereby causing some nodes to die quickly. Therefore, an energy-efficient clustering algorithm based on game theory is proposed in this study. In the cluster head selection phase, each node competes as potential cluster head by joining a localized clustering game, and a potential cluster head is selected to be a real cluster head through a properly designed probability method. Simulation results show that the life span of wireless sensor networks extended by our algorithm becomes longer than those extended by low-energy adaptive clustering hierarchy and clustered routing for selfish sensors when proper parameters are used.

Keywords

Wireless sensor networks clustering energy efficiency game theory residual energy

Introduction

Wireless sensor networks (WSNs) are currently widely used in fields, such as traffic control, industrial and manufacturing automation, e-health, and animal monitoring. They are among the most important technologies of the 21st century and considered as the next step in information revolution.¹ WSNs are wireless networks that comprise a large number of low-cost and low-power sensor nodes deployed either inside or extremely close to the event and contain sensor nodes that can sense the physical environment for data acquisition, data computation, and communication.² A sensor node typically contains signal-processing circuits, microcontrollers, and wireless transmitters or receiver antennas and has limited processing capabilities. After collecting information, sensor nodes send the data to the base station (BS) if the latter is within communication range; otherwise, data are sent to other sensor nodes through routing techniques. A BS is a device that manages WSNs and collects data to be analyzed for further use. This device commonly has more energy capacity, processing power, and memory than typical sensor nodes. Sensor nodes are usually randomly deployed in the sensing fields. Once deployed, their batteries do not require recharging. Therefore, prolonging the life span of networks with limited energy is an important research topic concerning WSNs. The life span of a sensor network can be measured based on generic parameters, such as the time that the first sensor node loses its transmitting capability (first dead), the time that half of the sensor nodes lose their transmitting capabilities (half dead), and the time that all of the sensor nodes lose their transmitting capabilities (all dead). Recent years have witnessed great efforts concerning the energy efficiency made to prolong the life span of networks, such as energy-efficient routing protocols,^3–8 Duty-cycling and medium access control (MAC) protocols,^9–11 topology control,^12–15 energy-efficient data aggregation schemes,^16–19 and cross-layer optimization techniques.^20–23 According to the energy model of sensor nodes,²⁴ the communicating part of a sensor node consumes considerably more energy than the computing part, thereby causing routing techniques to affect the energy conservation of sensor nodes. Clustering algorithms are widely used in WSNs. In cluster-based WSNs, several nodes form a cluster, and one of them is elected as cluster head (CH). The CH collects information from normal nodes and sends aggregated data to the BS or to other CHs. Thus, CHs consume considerably more energy than normal nodes and die faster. Most clustering algorithms randomly select several sensor nodes as CHs. This random selection of CHs cause uneven energy consumption, thereby reducing network life span. Hence, the energy load on every sensor node should be balanced. From the local point, the energy consumption of CHs is influenced by many factors, such as their distance to the BS and the number of cluster members. From the global point, the distribution of the CHs also affects the energy dissipation of the networks. If CHs are close to one another, energy dissipation will be unevenly distributed.

Game theory, which is developed for and extensively used in economics and biology, is a powerful mathematical tool for analyzing and predicting the behavior of rational and selfish entities. Game theory has recently been widely applied in WSNs.²⁵ In Koltsidas and Pavlidou,²⁶ game theory is used to analyze the abovementioned clustering problem and form a clustering mechanism called clustered routing for selfish sensors (CROSS). In CROSS, each sensor node is modeled as a player that can hear the messages of all the other players and know the number of players present. Based on the number of players, each node calculates an equilibrium probability, which decides if a player becomes a CH. However, the sensing field can be large in real WSNs; therefore, a sensor node cannot realistically and effectively communicate with all the sensors. Meanwhile, different CHs with different positions and cluster members do not have the same energy dissipation as normal nodes. CROSS assumes the ideal scenario that all CHs have the same energy dissipation.

In this article, we propose a new clustering algorithm based on localized game theory. For CH selection, each sensor node communicates only with neighbors within its communication radius. We also consider the residual energy of each node. Our proposed algorithm computes a probability on the basis of the number of players in a neighborhood of a node and its residual energy and determines whether to compete for CH.

This article is organized as follows. In section “Related works,” we discuss the related works on WSNs routing and clustering problems. In section “System model,” we described the system model in our proposed algorithm. We present our proposed algorithm in section “ECAGT algorithm.” In section “Simulation results and discussions,” we give the algorithm analysis and simulation results. Conclusions are presented in the last section. Finally, section “Conclusions” concludes this article.

Related works

Routing in WSNs means that the data from the sensor is forwarded to the BS. Routing algorithm is an important research topic in WSNs, and a number of routing and clustering algorithms have been developed so far.

Low-energy adaptive clustering hierarchy (LEACH)²⁴ is a well-known single-hop self-organizing clustering algorithm proposed by Heinzelman et al. and widely referenced routing protocol for WSNs. In this algorithm, the nodes in the networks form clusters by self-organization, and one of the nodes in each cluster is selected as CH. All non-CH nodes transmit data to the CHs, which receive and aggregate data before transmitting them to the BS. This two-layered algorithm minimizes energy consumption in WSNs through cluster formation and data aggregation. In LEACH, each node independently decides whether to become a CH. A sensor node selects a random number between 0 and 1. If this number is less than the threshold $T (n)$ , the node becomes a CH. $T (n)$ is a well-designed threshold assigned to sensor nodes n and is calculated as follows

$T (n) = {\begin{matrix} \frac{p_{e}}{1 - p_{e} \times (r m o d \frac{1}{p_{e}})} & if n \in G \\ 0 & otherwise \end{matrix}$ (1)

where n is the node ID, r is the current round, p_e is the expected percentage of CH, and G is the collection of nodes that are not elected as CHs in the last 1/p_e rounds. Once CHs have been elected, the other nodes select the nearest CH. Each node is elected as a CH once every 1/p_e rounds. This procedure makes the nodes to die randomly at the same rate. From our perspective, some nodes do not consume the same energy while serving as CH. It does not consider the remaining energy of the nodes when selecting CHs. Many routing algorithms are proposed based on LEACH, such as LEACH-C,²⁷ which is a centralized version of LEACH. In these algorithms, CHs are not declared by the nodes themselves but by the BS. Each node sends its local information to the BS, which then decides the CHs by its global knowledge of the network. This centralized algorithm is beneficial because the BS has advanced computation capabilities and practically unlimited power. The results showed that LEACH-C increases network life span. However, the transmission of local information from the nodes to the BS is energy consuming. Meanwhile, power-efficient gathering in sensor information systems is similar to that in LEACH but requires less energy per round.²⁸ A chain is created such that each node receives aggregated information, which is then forwarded to a nearby node. This algorithm allows for a variation in communication energy parameters. In terms of node number and dynamic density and topology change in WSNs, Feng et al.²⁹ proposed a load-balanced hierarchical topology control algorithm based on LEACH. Shin et al.³⁰ presented a novel energy-efficient clustering scheme called clustering with one-time setup, which removed the cluster-reforming process required at every round after the first round.

CROSS²⁶ is proposed by Gerorgios Koltsidas and Fotini-Niovi Pavlidou from Aristotle University in Greece. This algorithm combines game theory and clustering to solve the routing problem of WSNs. In the said paper, sensor nodes are modeled as players, and CH selection is modeled as a clustering game. Whether a sensor node decides to declare itself a CH is the strategy space. The payoffs depend on whether the node declares itself a CH and whether data are sent to the BS. The author proved the existence of a Nash equilibrium, where no node will have the incentive to change the balance if every node declares itself a CH with probability p. p is computed as

$p = 1 - (ω)^{\frac{1}{N - 1}}$ (2)

where N is the number of nodes joining the game and $ω$ is a predefined parameter. In CROSS, each node competes to become a CH with a probability p. Some of the nodes successfully declare themselves as CHs and form their corresponding clusters. To evenly distribute energy consumption, the author also proposed a zero probability rule (ZPR), which states that each node elected as CH sets p to zero until all its neighbors have also served as CHs before p is computed normally again.²⁶ The result showed that the network life span values under CROSS are similar to those under LEACH. In Xie et al.,³¹ the authors proposed a localized game theoretical clustering algorithm (LGCA) based on CROSS. In LGCA, each node selfishly plays a localized clustering game only with neighbors within a certain communication radius. Hybrid, game theory–based and distributed clustering (HGTD)³² is a clustering protocol proposed on the basis of LGCA. It defines the payoff for each node when choosing different strategies, where both node degree and distance to BS are considered in the process of playing localized clustering game.

Routing algorithms come in different types as well. Clustering algorithms, such as weighted clustering,³³ hierarchal clustering,^34–36 and dynamic clustering,³⁷ were proposed to organize nodes as clusters. The cluster-based approach for energy-efficiency (CLENER) algorithm, which was proposed in Silva et al.,³⁸ uses fuzzy logic to form clusters. The non-CHs select CHs according to a cost function computed through the Takagi Sugeno fuzzy system.³⁹ An efficient data routing scheme is proposed in Anisi et al.⁴⁰ for controlling data delivery from the nodes to the BS. This scheme defines the link cost function of the next nodes and selects the next node by comparing their costs. Finally, a novel energy-efficient clustering mechanism based on the artificial bee colony algorithm was proposed by Karaboga et al.⁴¹ In the next sections, we will propose a new clustering algorithm.

System model

Network model

WSN routing protocols are application specific. The assumptions regarding WSNs in this article are as follows:

The sensor nodes are fixed, energy-constrained, and have the same capabilities;

The BS is not subject to energy restrictions and has strong communication and computation capabilities;

Batteries do not recharge after node deployment;

The sensor nodes have enough power to reach the BS;

Each sensor node can change its transmission power level dynamically to adapt to a certain communication distance;

A sensor node can switch between run and sleep states under the command of a TDMA order.

We use the similar concept of round for LEACH. However, our proposed algorithm has no epoch. Each round has two states, namely, setup and steady states. In our algorithm, each node collects local information in the setup phase. Figure 1 shows a time line of our proposed algorithm.

Figure 1.

Time line showing the procedures of our proposed algorithm.

Energy model

The evaluation of wireless communication algorithms and dissipation of energy when transmitting and receiving signals mostly depend on the energy model of communication. We assume an ideal model based on the energy model of LEACH. Figure 2 shows the radio energy dissipation model.

Figure 2.

Radio energy dissipation model.

In Figure 2, l is the bytes of transmitting data. d is the distance between the transmitting node and the receiving node. $E_{elec}$ is the dissipated energy of transmitting electric circle and receiving electric circle, which equal each other in this energy model. $ε_{amp}$ is the amplifying power, which has two values $ε_{fs}$ and $ε_{fs}$ . $ε_{fs}$ is the free-space energy-amplifying power. $ε_{mp}$ is the multi-path energy-amplifying power. m is an amplifying factor, which also has two values corresponding to different channels.

In the simulation, we use the same channel model used in Heinzelman et al.²⁴ This channel model includes free-space transmitting model ( $d^{2}$ power loss) and multi-path transmitting model ( $d^{4}$ power loss). The determining factor in this model is the distance d between the sending and receiving nodes and $d_{0}$ is the threshold. If $d < d_{0}$ , we use the free-space model. Otherwise, we use the multi-path model.⁴² Therefore, if we transmit l-bit data over a distance d, the energy dissipation in the transmitting parts is

$E_{tx} (l, d) = {\begin{matrix} l E_{elec} + l ε_{fs} d^{2} & d < d_{0} \\ l E_{elec} + l ε_{mp} d^{4} & d \geq d_{0} \end{matrix}$ (3)

With $l E_{elec} + l ε_{fs} d^{2} = l E_{elec} + l ε_{mp} d^{4}$ , we obtained the threshold

$d_{0} = \sqrt{\frac{ε_{fs}}{ε_{mp}}}$ (4)

The energy dissipated by the receiving part is

$E_{rx} (l) = l E_{elec}$ (5)

The values of $E_{elec}$ are determined by factors like digital encoding, digital modulation, and filtering. The energy dissipated by amplifying signals $ε_{fs} d^{2}$ and $ε_{mp} d^{4}$ are determined by the distance between the sending and the receiving nodes.

CHs aggregate the data they receive before transmitting them to the sink. The energy spent by a CH in aggregating $N_{u}$ packets of the same length l is computed as follows

$E_{aggr} = N_{u} \cdot l \cdot ε_{da}$ (6)

where $ε_{da}$ is the data aggregating rate, which is the energy consumed by the CH for aggregating a one-bit packet.

Therefore, when sensor i is selected as a CH, the energy consumption is

$c = N_{u} \cdot E_{rx} + E_{aggr} + E_{ch, bs}$ (7)

where $E_{ch, bs}$ is the energy consumed by data transmission from a CH to a BS. When sensor i is selected as a normal node, the energy consumption is

$δ = E_{tx} + E_{i, ch}$ (8)

where $E_{i, ch}$ is the energy consumption of data transmission from node i to its CH.

ECAGT algorithm

In this article, we propose an energy-efficient clustering algorithm based on game theory (ECAGT). This algorithm uses the same concept of round as that used by LEACH and CROSS. Each round consists of two states: setup state and steady state. In the setup state, we propose a new function for CH selection. CHs are elected and clusters are formed in this stage. In the steady state, the WSN sends data to the BS. In this article, our work focuses on CH selection and cluster formation.

Setup phase

Collecting local information

In this phase, each node collects the local information of its neighbor. As previously assumed, each sensor node can adjust its power level to adapt to a certain communication distance, and each node at their highest power level can communicate with another node. However, the energy dissipation of message sending increases as the communication distance increases. In this article, we set a communication radius $R_{c}$ for every sensor node in the setup phase. Each node communicates only with its neighbors within radius $R_{c}$ in the setup phase. First, every node broadcasts a HELLO message to its neighbors. When a sensor node receives a HELLO message, it sends an ACKNOWLEDGE message to the original node. A HELLO message includes the ID of the node. An ACKNOWLEDGE message includes the ID and residual energy of the node. Each node then determines the number of sensor nodes within its $R_{c}$ and the residual energies of the sensor nodes. We use $N_{i}$ as the number of sensor nodes within node i‘s communication range. For example, in Figure 3, $N_{i} = 2$ , $N_{j} = 3$ , and $N_{k} = 4$ .

Figure 3.

Nodes communicate only with neighbors within radius $R_{c}$ in the setup phase.

Selecting CHs

From our perspective, LEACH and CROSS both select CHs randomly in each round. Thus, the position of the CHs cannot be evenly distributed. The CHs can be near or far from one another. Figure 4(a) shows a possible CH distribution layout in LEACH and CROSS. Despite the Zero Probability Zule, the energy consumption of the different CHs in equation (7) cannot be the same.

Figure 4.

Comparison of CHs distribution. (a) Possible CH distribution layout in LEACH and CROSS and (b) typical CH distribution layout in our proposed algorithm.

In this article, we use a localized method to make sure that the CHs are properly distributed. Before a node chooses whether to become a CH, it first decides whether to be a candidate CH. Candidate CHs compete to be final CHs. After a node decides to be a candidate CH, it will announce itself as the final CH if it does not receive an announcement message from its neighbor sensor nodes. When a candidate CH hears an announcement, it will declare itself a normal node and leave the competition. This response eliminates the neighbors of CHs within a certain radius. Figure 4(b) shows a typical CH distribution layout in our proposed algorithm.

In CH candidate selection, we consider energy dissipation and propose a function based on equation (2) to select candidate CHs. This function is described as follows

$P_{i} = (1 - {(ω)}^{\frac{1}{N_{i} - 1}}) \times {(\frac{E_{i}}{E_{ave}})}^{α}$ (9)

where $N_{i}$ is the number of node i‘s neighbor nodes; $E_{i}$ is the residual energy of the node i; $E_{ave}$ is the average energy of all the nodes within sensor node i‘s communication radius (including itself); and $ω$ and $α$ are two parameters that are discussed later.

The first part of the equation comes from the equilibrium of game theory, which is used in equation (2). The second part of the equation is the energy dissipation factor. By adding this factor to the equilibrium, the energy dissipation factor will have an effect on CH selection. We will discuss this equation and how it can affect the selection of CHs in detail in the next section.

After collecting local information, node i computes $P_{i}$ and generates a random number $ran d_{i}$ between 0 and 1. If $P_{i}$ is bigger than this random number, it will declare itself as candidate CH. We noticed that there is a possibility that $P_{i}$ is bigger than one. On that condition, we think that the note is highly suitable to be the candidate CH. Since it is bigger than one, it will definitely declare itself as candidate CH.

Cluster formation

After all the final CHs are elected, the final CHs change their communication power to transmit data to the BS and broadcast a message to announce their election. When normal nodes receive the message, they select the CH nearest to them. Some normal nodes may not be selected because they cannot reach any CH within their communication radii. Our solution to this problem is the changing of the power levels of all the unselected nodes to enable their communication with the nearest CH, so they can join the cluster. Figure 5 is the setup state flowchart of our proposed solution.

Figure 5.

Flowchart of the setup state in the proposed algorithm.

Steady state

After all the clusters are formed, sensor nodes start to transmit data to the BS. In this state, CHs allocate time slots to the normal nodes. Each normal node collects sensing data and transmits them to its CH using its designated time slot. After a CH receives all the data packets from its cluster members, it aggregates the data and sends a compressed packet to the BS. After all the data are sent to the BS once in this state, the networks revert to the setup state and restart the cluster formation until the wireless network exhausts all the energy.

Simulation results and discussions

Simulation model

To evaluate our proposed algorithm, we run several simulations that compare LEACH, CROSS, and ECAGT with one another. We use MATLAB (R2014a) as the simulation tool. Table 1 shows the simulation parameters.

Table 1.

Simulation parameters.

Parameter	Value
$Number of nodes$	100
$Sensing field$	100 m × 100 m
$BS position$	(50, 175)
$Data packet$	4000 bytes
$Signal packet$	100 bytes
$E_{elec}$	50 nJ/bit
$ε_{fs}$	10 pJ/bit/signal
$ε_{mp}$	0.0013 pJ/bit/m4
$ε_{da}$	5 nJ/bit/signal
$E_{o}$	0.5 J

We randomly place 100 nodes in a 100 m × 100 m area. The BS is at (50, 175), which is at least 75 m from the closest node of the network. The data packet size is 4000 bytes and the control signal packet size is 100 bytes. We use the energy model as we described in the “System model” section. In this energy model, $E_{elec}$ is the energy dissipation of the transmitting and receiving electric circles, which equals each other. $ε_{fs}$ is the free-space energy-amplifying dissipation, $ε_{mp}$ is the multi-path energy loss dissipation, and $ε_{da}$ is the data aggregation rate. Each node has an initial energy of $0.5 J$ . We consider the life span of the networks as an important metric that reflects the performance of the algorithms. When a node has insufficient energy for data transmission, it is called a dead node. First dead is when the first sensor node loses its transmitting capability, half dead is when half of the sensor nodes lose their transmitting capabilities, and all dead is when 95% of the sensor nodes lose their transmitting capabilities. $R_{c}$ , $α$ , and $ω$ are the main parameters.

Parameter analysis

This section discusses how parameters $R_{c}$ , $α$ , and $ω$ are selected. Radius $R_{c}$ is one of the most important parameters in our algorithm. In the discussion on $R_{c}$ , we first set $α = 8$ (to be discussed it later). Then, we run the simulations with different $R_{c}$ and $ω$ . Figures 6 and 7 show life span of the networks (first dead and all dead) with the different $R_{c}$ and $ω$ values in our proposed algorithm. Figure 6 shows that when $R_{c}$ is higher than 30 m, the first dead of networks behaves better than when $R_{c}$ is smaller than 30 m in most of $ω$ . When $ω$ is extremely large, the first dead has a small value regardless $R_{c}$ . Figure 8 shows that as $ω$ increases, the average number of CHs per round decreases. When $ω$ is 0.9, the network has no CH, and all nodes send the data directly to the BS, thereby consuming energy that is larger than that consumed when data are sent to other nodes. Therefore, the first dead of the network in Figure 6 shows a small value. This result corresponds to equation (9). With other parameters constant, the probability of nodes deciding to be CHs decreases as $ω$ increases. At a proper $ω$ and an $R_{c}$ larger than 30 m, the first dead has a value near its original value. Figure 8 shows that as $R_{c}$ increases, the average number of CHs per round decreases. When it is 30 m, the number of CHs is approximately 5, which is similar to the result obtained by LEACH (5%). Therefore, we set $R_{c}$ as 30 m in this study.

Figure 6.

Life span of networks with different $R_{c}$ and $ω$ (first dead).

Figure 7.

Life span of networks with different $R_{c}$ and $ω$ (all dead).

Figure 8.

Average number of cluster heads with different $R_{c}$ and $ω$ .

$ω$ is another important parameter in our algorithm. This variable shows the importance of the number of neighbor nodes and decides the balance point of the games. Figure 9 shows the number of living nodes in each round under different $ω$ values. The higher the $ω$ , the earlier the first dead emerges. This pattern is in accordance with equation (9), which states that the bigger the $ω$ , the smaller the probability of nodes deciding to be CHs, thereby increasing energy consumption and resulting in the early death of nodes. When $ω$ is 00.1–0.1, the life span of the network retains a high value, and the average number of CHs is similar to that of LEACH ( $5 %$ ), which is shown in Figure 10. Therefore, our algorithm performs well when $ω$ is 0.01–0.1.

Figure 9.

Life span of the networks under different $ω$ .

Figure 10.

Average number of cluster heads under different $ω$ .

$α$ shows the importance of residual energy in CH selection. Figure 11 shows the life span of networks with different $α$ . When $α$ is bigger than 8, the networks achieve a good performance; therefore, we set $α = 8$ .

Figure 11.

Life span of the networks with different $α$ .

Algorithm discussions

In this section, we analyze the characters of our proposed algorithm.

Deviation of CHs position

To evaluate the distribution of CHs, we define a new performance parameter: $Mean_dist$ which is the mean distance between CHs

$Mean_dist = \frac{1}{C_{c}^{2}} \cdot \sum_{i = 1}^{c} \sum_{j = 1}^{c} d_{ij}$ (10)

where $d_{ij}$ is the distance between CHs i and j and c is the number of cluster heads per round. $C_{c}^{2}$ is the combination of choosing two different CHs from c CHs. $Mean_dist$ is the average distance between CHs. When $Mean_dist$ is large, the CHs may be evenly distributed, as shown in Figure 4(b). Otherwise, the CHs are unevenly distributed, thereby energy consumption is larger than that in a large $Mean_dist$ . Figure 12 shows that the $Mean_dist$ of LEACH and ECAGT are approximately 50 and 60, respectively. Therefore, the CHs of our proposed algorithm ECAGT are more evenly distributed than those of LEACH.

Figure 12.

Comparison of $Mean_dist$ : (a) $Mean_dist$ of LEACH and (b) $Mean_dist$ of ECAGT.

Probability discussion

Equation (9) is detailed in this section. First, we set P, $P 1$ , and $P 2$ as follows. $P 1$ is the first part of P and the equation used for CROSS in Koltsidas et al.²⁶ $P 2$ is the second part of P and is originally proposed in this article

$P 1 = 1 - ω^{1 / N_{i} - 1}$ (11)

$P 2 = {(\frac{E_{i}}{E_{ave}})}^{α}$ (12)

$P = (1 - ω^{\frac{1}{N_{i} - 1}}) \times {(\frac{E_{i}}{E_{ave}})}^{α}$ (13)

We add equation (12) to introduce the energy dissipation factor in CH selection. $P 2$ represents the degree of importance of energy dissipation in CH selection. Figure 13 shows the values of P, $P 1$ , and $P 2$ in different rounds of node 11 (for example). Figures 14 and 15 are two more specific parts of Figure 13.

Figure 13.

Values of P, $P 1$ , and $P 2$ in different rounds.

Figure 14.

Values of P, $P 1$ , and $P 2$ in rounds 1–10 (Node ID = 11).

Figure 15.

Values of P, $P 1$ , and $P 2$ in rounds 700–710 (Node ID = 11).

Based on Figures 13 –15, P is mainly decided by $P 1$ initially. Over time, $P 2$ becomes more important. P is finally decided by $P 2$ . This result is consistent with our expectations. In the early rounds, all the nodes have the same residual energy. Therefore, the game theory part ( $P 1$ ) is in best position to decide the CHs. The energy differences among the nodes increase over time. When the CHs remains decided by $P 1$ in this scenario, many CHs have low-energy levels, and thus, the nodes die quickly. Therefore, as the energy differences among the nodes increase, the nodes with high-energy levels should be allowed to become CHs. This reasoning is the basis of equation P. This conclusion can be obtained from another perspective using Figures 16 and 17.

Figure 16.

Values of P, $P 1$ , and $P 2$ in round 100th.

Figure 17.

Values of P, $P 1$ , and $P 2$ in round 900th.

Simulation results

In this section, we compare our proposed algorithm ECAGT with three other algorithms LEACH, CROSS, and LGCA. Figure 18 shows the life span of the networks under LEACH ( $p = 0.05$ ), CROSS ( $ω = 0.05$ ), LGCA ( $ω = 0.05$ ), and ECAGT ( $R_{c} = 30$ , $ω = 0.05$ , and $α = 8$ ). Based on Figures 16 and 17, the first dead of ECAGT appeared 200 to 300 rounds later than those of LEACH and LGCA and 100 more rounds later than CROSS, which shows that our algorithm extended the life span of the networks and conserved energy. Although game approach computation and information exchanged in our algorithm will consume more energy than LEACH and CROSS, our algorithm still can extend life span of the networks because the energy consumed in computation is far more less than in communication. Information exchanged in the process of playing localized game in our algorithm is also localized and the packets are small. The advantage of ECAGT can cover this shortage.

Figure 18.

Comparison of network life spans of LEACH, CROSS, LGCA, and ECAGT.

Figure 19 compares the number of CHs per round in LEACH, CROSS, LGCA, and ECAGT. Based on Figure 19, LEACH and CROSS both have rounds with no CHs, that is, the nodes send data directly to the BS in these rounds. The figure also indicates that the deviation in the number of CHs in ECAGT is smaller than those in LEACH and CROSS.

Figure 19.

Comparison of CHs number per round of LEACH, CROSS, LGCA, and ECAGT.

To eliminate the random factors, we run the simulation 1000 times and obtain the average life span of the networks. Figure 20 compares the network life spans across the three algorithms. In contrast to LEACH, CROSS, and LGCA, our algorithm ECAGT can prolong the life span of the first dead and half dead nodes. However, when the nodes start to die, the networks under ECAGT die faster than those under LEACH and CROSS. This effect resulting in all dead time under ECAGT is smaller than that under LEACH, CROSS, and LGCA.

Figure 20.

A comparison of network life span of LEACH, CROSS, LGCA, and ECAGT.

Conclusion

In this article, we propose a new clustering algorithm based on LEACH and CROSS. In our proposed algorithm, each node and its neighbors form a clustering game for the selection of CHs, which in turn contend to be final CHs. One CH at most is within the computing radius of each sensor node. This mechanism ensures that the CHs are evenly distributed and the energy in the networks are evenly consumed. We also propose a new clustering probability equation, which makes the sensor node with high residual energy and increases the probability of a node with few neighbor nodes of becoming a CH. Simulation results show that when proper parameters are used, our algorithm is superior to LEACH and CROSS with regard to extension of WSN life span.

Footnotes

Handling Editor: Amiya Nayak

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 the Fundamental Research Funds for the Central Universities (WH1213010).

References

Estrin

Borriello

Colwell

et al . Embedded, everywhere: a research agenda for networked systems of embedded computers. Washington, DC: National Academies Press, 2001.

Akyildiz

Sankarasubramaniam

et al . A survey on sensor networks. IEEE Commun Mag 2002; 40(8): 102–114.

Pantazis

Nikolidakis

Vergados

DD.

Energy efficient routing protocols in wireless sensor networks: a survey. IEEE Commun Surv Tut 2013; 15(2): 551–591.

Zhang

Zheng

et al . An energy-balanced routing method based on forward-aware factor for wireless sensor networks. IEEE T Ind Inform 2014; 10(1): 766–773.

Kuila

Jana

PK.

Energy efficient clustering and routing algorithms for wireless sensor networks: particle swarm optimization approach. Eng Appl Artif Intel 2014; 33: 127–140.

Vijayan

Raaza

A novel cluster arrangement energy efficient routing protocol for wireless sensor networks. Indian J Sci Technol 2016; 9(2): 1–9.

Anisi

Abdul-Salaam

Idris

MYI

et al . Energy harvesting and battery power based routing in wireless sensor networks. Wirel Netw 2017; 23(1): 249–266.

Ren

Zhang

et al . Lifetime and energy hole evolution analysis in data-gathering wireless sensor networks. IEEE T Ind Inform 2016; 12(2): 788–800.

Doudou

Djenouri

Badache

et al . Synchronous contention-based MAC protocols for delay-sensitive wireless sensor networks: a review and taxonomy. J Netw Comput Appl 2014; 38: 172–184.

10.

Huang

Xiao

Soltani

et al . The evolution of MAC protocols in wireless sensor networks: a survey. IEEE Commun Surv Tut 2013; 15(1): 101–120.

11.

Carrano

Passos

Magalhaes

et al . Survey and taxonomy of duty cycling mechanisms in wireless sensor networks. IEEE Commun Surv Tut 2014; 16(1): 181–194.

12.

Vasilakos

AV.

A survey on topology control in wireless sensor networks: taxonomy, comparative study, and open issues. P IEEE 2013; 101(12): 2538–2557.

13.

Bagci

Korpeoglu

Yazici

A distributed fault-tolerant topology control algorithm for heterogeneous wireless sensor networks. IEEE T Parall Distr 2015; 26(4): 914–923.

14.

Deniz

Bagci

Korpeoglu

et al . An adaptive, energy-aware and distributed fault-tolerant topology-control algorithm for heterogeneous wireless sensor networks. Ad Hoc Netw 2016; 44: 104–117.

15.

Deshpande

Montiel

McLauchlan

. Wireless sensor networks: a comparative study for energy minimization using topology control. In: 2014 sixth annual IEEE green technologies conference (GreenTech), Corpus Christi, TX, 3–4 April 2014, pp.44–48. New York: IEEE.

16.

Dong

Ota

Liu

RMER: reliable and energy-efficient data collection for large-scale wireless sensor networks. IEEE Internet Things 2016; 3(4): 511–519.

17.

Liu

Zhang

et al . High energy-efficient and privacy-preserving secure data aggregation for wireless sensor networks. Int J Commun Syst 2013; 26(3): 380–394.

18.

Yao

Cao

Vasilakos

. EDAL: an energy-efficient, delay-aware, and lifetime-balancing data collection protocol for wireless sensor networks. In: 2013 IEEE 10th international conference on mobile ad-hoc and sensor systems (MASS), Hangzhou, China, 14–16 October 2013, pp.182–190. New York: IEEE.

19.

Sran

Kaur

et al . Energy aware chain based data aggregation scheme for wireless sensor network. In: 2015 international conference on energy systems and applications, Pune, India, 30 October–1 November 2015, pp.113–117. New York: IEEE.

20.

Xiao

Deng

et al . A survey of cross-layer designs in wireless networks. IEEE Commun Surv Tut 2014; 16(1): 110–126.

21.

Liu

Xia

Shroff

et al . Distributed cross-layer optimization in wireless networks: a second-order approach. In: 2013 Proceedings IEEE INFOCOM, Turin, 14–19 April 2013, pp.2103–2111. New York: IEEE.

22.

Han

Jornet

Fadel

et al . A cross-layer communication module for the Internet of Things. Comput Netw 2013; 57(3): 622–633.

23.

Marques

Dall’Anese

Giannakis

GB.

Cross-layer optimization and receiver localization for cognitive networks using interference tweets. IEEE J Sel Area Comm 2014; 32(3): 641–653.

24.

Heinzelman

Chandrakasan

Balakrishnan

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

25.

Shi

Wang

Kwok

et al . Game theory for wireless sensor networks: a survey. Sensors 2012; 12(7): 9055–9097.

26.

Koltsidas

Pavlidou

FN.

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

27.

Heinzelman

WB.

Application-specific protocol architectures for wireless networks. PhD Thesis, Massachusetts Institute of Technology, Cambridge, MA, 2000.

28.

Lindsey

Raghavendra

CS.

PEGASIS: Power-Efficient GAthering in Sensor Information Systems. In: Aerospace conference proceedings, 2002, Big Sky, MT, 9–16 March 2002, vol. 3, pp.1125–1130. New York: IEEE.

29.

Feng

Zhang

Tan

et al . Research on the algorithm of load-balanced hierarchical topology control for WSN. Appl Math 2013; 7(1L): 347–352.

30.

Shin

Moh

Chung

Clustering with one-time setup for reduced energy consumption and prolonged lifetime in wireless sensor networks. Int J Distrib Sens N 2013; 3: 264–273.

31.

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: 188–192.

32.

Yang

Zhong

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

33.

Chatterjee

Das

Turgut

WCA: a weighted clustering algorithm for mobile ad hoc networks. Cluster Comput 2002; 5(2): 193–204.

34.

Banerjee

Khuller

. A clustering scheme for hierarchical control in multi-hop wireless networks. In: Twentieth annual joint conference of the IEEE computer and communications societies (INFOCOM 2001), Anchorage, AK, 22–26 April 2001, vol. 2. pp.1028–1037. New York: IEEE.

35.

Gao

Yang

et al . An improved auction scheme for task allocation in wireless sensor network. In: 2010 6th international conference on wireless communications networking and mobile computing (WiCOM), Chengdu, China, 23–25 September 2010, pp.1–4. New York: IEEE.

36.

Zheng

Lin

. Clustering routing algorithm using game-theoretic techniques for WSNs. In: Proceedings of the 2004 international symposium on circuits and systems (ISCAS ’04), Vancouver, BC, Canada, 23–26 May 2004, vol. 4. New York: IEEE.

37.

Chen

Hou

Sha

Dynamic clustering for acoustic target tracking in wireless sensor networks. IEEE T Mobile Comput 2004; 3(3): 258–271.

38.

Silva

Costa

Pires

et al . A cluster-based approach to provide energy-efficient in WSN. IJCSNS 2013; 13(1): 55.

39.

Negnevitsky

Artificial intelligence: a guide to intelligent systems. Harlow: Pearson Education, 2005.

40.

Anisi

Abdullah

Razak

SA.

Energy-efficient and reliable data delivery in wireless sensor networks. Wirel Netw 2013; 19(4): 495–505.

41.

Karaboga

Okdem

Ozturk

Cluster based wireless sensor network routing using artificial bee colony algorithm. Wirel Netw 2012; 18(7): 847–860.

42.

Rappaport

TS.

Wireless communications: principles and practice. Piscataway, NJ: Prentice Hall, 1996.

Energy-efficient clustering algorithm based on game theory for wireless sensor networks

Abstract

Keywords

Introduction

Related works

System model

Network model

Energy model

ECAGT algorithm

Setup phase

Collecting local information

Selecting CHs

Cluster formation

Steady state

Simulation results and discussions

Simulation model

Parameter analysis

Algorithm discussions

Deviation of CHs position

Probability discussion

Simulation results

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References