An Energy-Efficient Clustering Routing Protocol Based on Evolutionary Game Theory in Wireless Sensor Networks

Abstract

The features that sensor nodes are powered by battery and have severe energy constraint make the design of energy-efficient protocol a key task for wireless sensor networks (WSNs). Clustering protocols significantly cut down the energy expenditure of each sensor node. However, hot spots problem occurs in locations close to the sink. Besides, it makes things worse if the nodes with less energy are selected as cluster heads (CHs), because they are often loaded heavier traffic than cluster members (CMs) due to their duty. The issues which exist in WSNs are proposed and the primary reason why cluster head election is hard to control is then presented. A mathematical model aiming to ease the hot spots problem via optimizing the cluster size is proposed and an optimal cluster size (OCS) algorithm is given firstly. Subsequently, an evolutionary game model for the sensor nodes to terminate the anarchism during the process of cluster head selection is presented, and a novel routing protocol named Energy Efficient Routing protocol based on Evolutionary Game (EEREG) theory is proposed. Finally, extensive simulation experiments and performance comparisons with the well-known hierarchical routing protocols are conducted. The experiment results show that a significant improvement in energy efficiency as well as lifetime extension is achieved.

1. Introduction

Due to the rapid development of the technology of microelectric-mechanical system (MEMS) and the great progress in wireless communication, wireless sensor networks (WSNs) have gained worldwide attention and application. At present, wireless sensor networks are found to be applied in a variety of fields, such as environmental monitoring, habitat monitoring, industrial control, battlefield surveillance [1–4], structural health monitoring [5, 6], infrastructure and facility diagnosis, and other commercial applications [2, 7, 8]. One of the basic functions of WSNs is to report the event data sensed by nodes to the sink for further analysis.

WSNs consist of hundreds or even thousands of communication nodes featuring limited sensing, processing, computing capabilities, and especially constraint energy supply. It is expected to be well functional for several months or even longer according to specific applications. However, the nodes are usually deployed in harsh and inaccessible areas, which makes it impossible or impracticable to recharge energy or replace batteries. Consequently, some nodes run out of energy and network partition emerges. To prolong the lifetime of WSNs as long as possible, great attention should be paid to the energy efficiency. Besides, due to the nonuniform generation of the event data in some applications such as habitat monitoring, the unbalance traffic flows in some network areas, the monitoring of the migration of a herb of animals [2], and so on. Some nodes will use up their energy earlier than expected. This is known as hot spots problem and means the end of life of the network. It will definitely affect the performance of the network. For instance, [1] pointed out that there is still up to 93 percent of the initial energy left in the nodes further away from the sink when the nodes one hop away depleted their energy through the results in [9]. The aforementioned circumstance indicates that the energy efficiency and energy balance should all be brought into consideration to ensure that WSNs would live longer.

Energy consumption exists in three major components in each sensor node: sensing, communicating, and processing unit. Research results show that a large proportion of the energy is consumed in the process of communication. For example, it has been proved that the energy depleted by a node to transmit one-bit data over 20 meters is equivalent to that to run 1000 CPU instructions [10].

Recent years have witnessed great efforts being made to prolong the lifetime of WSNs. Most of these efforts concentrate on the energy efficiency and balance. All the existing methods can be divided into the following categories:

• (1)

Topology control and MAC scheduling: as the traffic load usually distributes unevenly, it is advisable to vary the nodes density with different areas [11–13]. In addition, some researches indicate that some collision-free MAC scheduling protocols are devised to avoid energy loss caused by transmitting collision [11].

(2)

Energy-efficiency routing protocols: numerous relevant protocols have emerged recently. Among them the protocols based on clustering are promising methods owing to their support for data fusion and other good properties such as good scalability and arrangement, as shown in [6, 10, 14–17].

(3)

Energy-balanced data propagation: it aims at achieving energy conservation via some energy-balanced data transmission schemes. Since the energy consumed in transmission accounts for a large amount of the total energy, this mechanism is expected to conserve energy effectively as shown in [18].

Wireless sensor networks belong to a kind of distributed system. As Lee proposed, the behavior and subsequently the quality of services (Qos) of these systems can be controlled by the algorithms selected [19]. So the distributed control algorithm is required to be designed. On the other hand, as the cluster head selection is a complicated issue, the centralized control is also required.

The main contributions of this paper are listed as follows:

• (1)

The primary reason why the nodes select the cluster heads (CHs) at random is pointed out firstly. Then the paper suggests that the anarchism can be eliminated by defining some regulations via game theory.

(2)

The paper proposes a mathematical model which can be applied to most of the network model to ease the energy burden of nodes near the sink. Based on this, an algorithm named the Optimal Clustering Size (OCS) algorithm is designed.

(3)

The opinion that the cluster head election can be controlled via some rules is confirmed via Lemma 4. Then a cluster head selection method is proposed based on the evolutionary game theory. Finally the Energy Efficient Routing protocol based on Evolutionary Game (EEREG) theory is put forward. As the EEREG is both centralized and distributed, it functions more flexibly and steadily.

(4)

In addition to the theoretical foundation, lots of experiments and extensive data analysis have been made to verify its validity. It is proved to be superior to several hierarchical routing protocols in the lifespan of network as well as traffic load.

This paper is organized as follows: the next section discusses the related works. Some relative notions and an issue existing in cluster head selection process are proposed in Section 3. Section 4 proposes the network model as well as an algorithm called Optimal Clustering Size (OCS) algorithm. Consequently the defect mentioned in the Section 3 is solved by the evolutionary game theory and the Energy Efficient Routing protocol based on Evolutionary Game (EEREG) theory is introduced, which is followed by Section 5 that evaluates the performance of the EEREG through simulation experiment. Section 6 concludes the paper and the future work is pointed out.

2. Related Works

Recent years have witnessed numerous achievements which aim at extending the lifetime of the network via different techniques. Some of the representative means proposed these days are detailed as follows.

Low-energy adaptive clustering hierarchy (LEACH) [20] is one of the most classical distributed cluster-based routing protocols in WSNs [15]. It adopts an approach to evenly distribute the energy loads by randomly rotating the role of cluster heads (CHs). However, the CHs are not selected in a nondeterministic way, and they may scatter unequally. Furthermore, the CHs transmit data to the sink directly; those far from the sink will exhaust their energy earlier. To address the problem existed in LEACH, a centralized routing protocol LEACH-C is proposed. It uses a central algorithm to produce better clusters. In LEACH-C the cluster was formed by the sink. The simulated annealing algorithm [21] is used to select the CHs.

The authors in [17] believe that the energy overhead which resulted from the head rotation must be taken into account. Therefore they propose a threshold-based cluster replacement (T-TEACH) in which an energy threshold is preestablished. CHs are replaced only if their current residual energy is smaller than the threshold; thus the whole energy expenditure can be reduced by minimizing the frequency of the CHs substitution.

A protocol called power-efficient gathering in sensor information systems (PEGASIS) is presented in [22]. It forms a chain to facilitate transmission process. It also designates nodes to transmit fused data to the sink. Meanwhile the nodes take turns to transmit data to reduce the average energy consumption and extend the network lifetime.

Reference [10] proposes a routing protocol based on the chessboard clustering (CC) scheme in heterogeneous sensor networks (HSN). The authors adopt a heterogeneous sensor network model in which a few powerful high-end sensors as well as many low-end sensors are deployed. A high-end node has more energy supply, so it acts as cluster head. The CC scheme uses a two-phase method to balance the energy dissipation.

A distributed clustering algorithm energy-efficient clustering (EC) is put forward in [14], in which the cluster size is determined by the hop count to the sink to approximately balance the lifetime of nodes. Additionally, the authors propose an energy-efficient multiple-hops WSN data collection protocol to evaluate EC's performance.

In [23], a routing protocol named EDFCM improved from LEACH [20] is presented. In EDFCM, a very function to calculate the optimum number of clusters is obtained. Although it also takes advantage of the residual energy and energy consumption rate to lengthen the lifetime, the process of cluster head selection is based on a method of one-step energy consumption. However, as trying to balance the energy consumption round by round, it inevitably produces much overhead.

The tradeoff between extending the time when the first node dies and that when the last node dies was taken into account in [5]. An algorithm named evolutionary-based protocol is proposed to obtain a better compromise between the stability time and network lifetime.

In [15], the imbalanced energy consumption between clusters is analyzed, and an energy-balancing cluster approach for gradient-based routing (EBCAG) is proposed to balance the energy depletion. A concept of gradient value and an unequal clustering scheme are adopted to achieve energy balance among all nodes. Additionally, the optimal cluster radius in different gradients is calculated to minimize the total energy consumption.

A localized and load-balanced clustering (LLBC) protocol is proposed in [6], which contains two approaches. One, which is named improved cluster head rotation (ICHR), aims at reducing the cost in head rotation by using localized information. For example, it will necessarily change CH according to the remained energy of the sensor nodes. The other one modified static clustering (MSC) will adjust the cardinality of clusters to equipoise the energy consumption among the clusters. However, it may increase energy burden on some clusters, which will make the energy dissipation faster. Therefore it may not be as useful as it claims.

A density-based dynamic clustering (DDC) algorithm for clustering and cluster head election mechanism is obtained in [16]. It uses a distributed algorithm named distributed independence set discovery (DISD) to select CH in merely O(1) complexity per sensor node. Besides, the authors introduce a concept to measure the age of the cluster head as well as a sleep management scheme including NBSM and ESSM policies to balance energy load and reduce energy consumption.

An energy-balanced routing protocol (EBRP) is designed with the help of the concept of potential in physics in [1]. The authors define the depth potential, energy density potential, and energy potential fields and then compound the three ones into a unified virtual potential field. Via EBRP, the packet can be driven to the sink and energy consumption balance can be achieved at the same time.

Reference [2] introduces a distributed energy balanced routing (DEBR) algorithm which adopts new metrics. The authors take the energy balanced routing problem as an integer programming model. In this model, composite metrics, energy cost (EC), and the total energy cost (TEC) are defined to come up with a good path through which energy sufficiency and energy efficiency can be achieved at the same time. Every node makes a local decision when transmitting data according to the value of TECs.

In [7], the authors firstly survey mechanisms which utilize nodes' mobility to prolong the lifetime of network. They classified the mechanisms into three categories: using mobile sinks; using mobile sensors redeployment; and using mobile relays. Then analysis is made on how these mechanisms extend the lifetime of network. Finally, comparisons are conducted among the three algorithms.

In [8, 24], the concept of energy-welfare is presented and in [8] a routing protocol named maximum energy welfare (MaxEW) routing applying to diverse event generation patterns is designed. It utilizes the social welfare function to achieve energy-efficiency as well as energy-balancing simultaneously. Based on social sciences, the authors define the energy equality (EE) and energy welfare (EW) which has exactly the same form as the so-called Atkinson welfare function does to attain the two objectives mentioned above.

Reference [3] introduces a routing method using a combination of a fuzzy approach and an A-star algorithm. To select a path which features the highest remaining battery power, minimum number of hop counts and minimum traffic load to the sink, an A-star path searching algorithm featuring an evaluation function, and a fuzzy system are proposed. Subsequently, each sensor node can transmit data according to the path previously selected to the sink. Besides, the routing schedule is conducted dynamically in consideration of current level of the nodes' metrics.

The authors in [4] present an adaptive energy-aware multipath routing protocol with load balance (AEMRP-LB). A concept direction-angle to eliminate the energy dissipation during the course of broadcast is proposed. It uses multipath to balance the energy consumption.

The former part of the paper indicates that most of the existing schemes have taken into account the residual energy, the energy expenditure of transmission, and the hop counts to the sink. Although the clustering schemes introduced in [6, 10, 15–17, 20, 22, 23] can extend the lifetime to some extent and the mechanisms in [2, 3, 7–9] can balance the energy consumption in some ways, the uneven event generation rate and the energy consumed in the cluster formation process are not taken into consideration, which consequently lead to energy imbalance and unnecessary energy loss.

3. The Problem and Some Notations

In this section, the energy imbalance issue in addition to the hot spot problem [1, 2, 15, 17] will be presented. During the process of clusters formation, the energy consumption which resulted from anarchic CH selection is presented firstly. Subsequently, the energy consumption model will be introduced. Finally, some definitions, terminologies, and assumptions are presented for better understanding.

3.1. The Problem

3.1.1. Excessive Energy Dissipation during the Cluster Head Selection

In wireless sensor networks, clustering is a critical way to minimize energy exhaust due to the similarity of data collected by adjacent nodes. Generally speaking, clusters are formed round by round. Each round has two phases: cluster head selection and data communication. A lot of methods have been proposed to optimize cluster head rotation [18, 20, 22, 23] in the first phase. However, the cause of excessive energy exhausts is ignored by most of the literature [1–18, 20, 22, 23, 25–27].

Due to the lack of enough reason, the nodes tend to be anarchic when selecting CHs. Each node has the same possibility to become CH and that leads to much unnecessary energy consumption. Besides, in extreme cases the node which has the least energy and locates the furthest away from the sink will become CH, which will make things worse. Figure 1 helps to explain the above situation. Nodes a, b, c, and d whose energy is marked by integers are deployed within the transmission range of each node as shown in Figure 1(a). As (b) indicates, node c decides to be CH based on the irrational analysis. Then it broadcasts an advertisement message (ADV) [20] to other nodes. The other nodes agree to node c and then the data collected by them are transmitted to node c as (c) shows. With the heavier energy burden less initial energy, node c would exhaust the energy earlier than expected.

Figure 1

The cluster head election when nodes are anarchic.

Although most of [1–18, 20, 22, 23, 25–27] have discussed the energy imbalance issue in detail, few of them have found out the primary cause. In fact, it is mainly caused by the nodes' lack of intelligence. Consequently, the nodes act randomly when deciding which one to be CH. Then the case shown in Figure 1 may emerge. Fortunately, the game theory [28] gives a solution to this problem. As long as some policies, which will lead to reach a Nash Equilibrium [28], are made for the nodes, the nodes will act as expected. Figure 2 shows a situation where the nodes are regulated by some rules concerning energy balance and energy efficiency. Finally, the node with most energy, namely, a, is selected as CH. This will contribute to achieving higher energy-efficiency and longer lifespan.

Figure 2

The cluster head selection when nodes are regulated by some rules.

3.1.2. Energy Imbalance among Different Regions

This problem can also be described as “hot spot” problem [1, 2, 15, 17]. As Figure 3 indicates, the nodes near the sink, namely, d and e, have to bear a heavier traffic load due to their special position. They do not only need to relay the packets of their own but also propagate the data from further regions. As a result, they tend to use up the energy earlier than other compeers do. When this happens, the network would be partitioned and its lifespan would be terminal.

Figure 3

The “hot spot” problem in wireless sensor networks.

3.2. Energy Consumption Model

Sensor nodes deplete their energy when sensing, receiving, and transmitting data. Because most of the energy is used to transmit data, this section is only concerned with energy for transmission. As the discussions in [6, 8, 15, 20, 23, 25] show, the energy model adopted in this paper for a node to transmit one bit of data to another over distance d equals

$$\begin{array}{cc}& e_{\mathrm{t}\mathrm{x}}=E_{\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}}+{\epsilon }_{\mathrm{a}\mathrm{m}\mathrm{p}}·d^{\alpha },\end{array}$$

(1)

where $E_{\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}}$ and ${\epsilon }_{\mathrm{a}\mathrm{m}\mathrm{p}}$ represent the energy consumption of transmitter circuit and transmitter amplifier, respectively, and $\alpha \hspace{0.17em}\hspace{0.17em}(2\le \alpha \le 4)$ is the propagation loss exponent. In detail, α is 2 for free space and increases to be 4 when obstacles exist. To receive a one-bit packet, the corresponding energy dissipation is shown as

$$\begin{array}{cc}& e_{\mathrm{r}\mathrm{x}}=E_{\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}}.\end{array}$$

(2)

Note that the energy exhausted in the receiver circuit is assumed to equal that of the transmitter circuit for the sake of simplicity.

3.3. Some Assumptions and Notations

To facilitate our further exposition, some assumptions and notations are put forward as follows:

• (a)

Every node can change its transmission power to vary its transmission; hence energy dissipation can be reduced via multihop transmission.

(b)

All the nodes are stationary once having been deployed and there is no need to allocate uniform energy for them. Besides, they have to be location-aware.

(c)

The sink has no limit in processing capacity and energy supply.

(d)

Every node has a uniform data traffic to be transmitted in a fixed time slot or round, which means that the event generation rate is even in the assigned area. In this paper, it is assumed to be μ.

(e)

All sensor nodes are grouped into clusters according to the geographical position. It will be presented subsequently and the number of nodes in distinct clusters differs. It is denoted as $N_{\mathrm{C}\mathrm{M}}$ .

(f)

The sensors distribution is the same as that in [18], which means that every node is deployed randomly in the networks area so that the quantity of sensor nodes in a certain area is proportional to the size of the networks. In this scenario the node density can be represented as ρ.

(g)

The lifetime of the wireless sensor network is defined as the number of rounds or time when the first node or a portion of nodes become incapable as [8]. Concerning this, related definitions will be given in Section 5.1.

4. Energy Efficient Clustering Routing Protocol Based on Evolutionary Game Theory (EEREG)

4.1. Network Model and an Optimal Cluster Size (OCS) Algorithm

In this section, the network model is presented and the optimal number of nodes in one cluster is analyzed in detail through mathematical model. Finally, an optimal cluster size (OCS) algorithm to solve the problem mentioned in Section 3.1.2 is introduced thoroughly.

4.1.1. Network Model

In this paper, a sector network is assumed to be divided into k annular sections. The sector has a central angle θ. This model is similar to that mentioned in [15, 18]. The sink is deployed at the center of the sector and each ring is d in width, just as shown in Figure 4. The area of the sector is denoted as A and that of the ith ring is denoted as $A_i$ . Without loss of generality, the sector can be an absolute monitor area or just a part of a larger general region. Therefore, the optimal cluster size (OCS) algorithm succeeding can be applied to the regions in any shapes including rectangle, square, and triangle.

Figure 4

The network model.

4.1.2. The Optimal Size of Clusters and Relative Theory Foundation

Given the above-mentioned discussion, it is clear that the nearer the regions are to the sink, the smaller size the clusters should be. So it is vital to determine the cluster size according to its distance. In this subsection, a mathematical model is presented.

According to the assumptions the data generated is related to the size of cluster. The size of cluster is the number of nodes in the cluster. For the sake of simplicity, the authors denote the cluster size in the ith sectors as $N_{\mathrm{C}\mathrm{M}i}$ . Based on the energy model aforementioned, the energy CHs consume contains receiving and transmission parts. The former is used to receive packets from CMs as well as the outer rings and the latter is used to transmit the data to CHs in inner sectors and the sink. Given the same width of rings and the transmission power of CHs, the values $e_{\mathrm{t}\mathrm{x}}$ and $e_{\mathrm{r}\mathrm{x}}$ are identical. This means the energy depletion can be simplified as the data traffic a CH bears. For convenience, the data generated in the first ring is denoted as Data.

Lemma 1.

The data generated in ith ring are $\left(2i-1\right)$ Data.

Proof.

Obviously the area of the first ring $A_{\mathrm{1}}$ is

$$\begin{array}{cc}& A_{\mathrm{1}}=\frac{\mathrm{1}}{\mathrm{2}}\theta ·d^{\mathrm{2}}.\end{array}$$

(3)

So the area of the ith $A_i$ is

$$\begin{array}{cc}& A_i=\frac{\left\{\pi {\left(id\right)}^{\mathrm{2}}-\pi {\left[\left(i-\mathrm{1}\right)d\right]}^{\mathrm{2}}\right\}·\theta }{\mathrm{2}\pi }=\left(\mathrm{2}i-\mathrm{1}\right)·\frac{\theta d^{\mathrm{2}}}{\mathrm{2}},\\ A_i=\left(\mathrm{2}i-\mathrm{1}\right)·A_{\mathrm{1}}.\end{array}$$

(4)

The node density is ρ, so the number of nodes in the ith ring $N_{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}i}$ is

$$\begin{array}{cc}& N_{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}i}=\rho ·A_i=\rho ·\left(\mathrm{2}i-\mathrm{1}\right)A_{\mathrm{1}}.\end{array}$$

(5)

According to the assumption, the data generated in ${\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}}_i$ is

$$\begin{array}{cc}& {\mathrm{D}\mathrm{a}\mathrm{t}\mathrm{a}}_i=\mu ·N_{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}i}=\mu ·\rho \left(\mathrm{2}i-\mathrm{1}\right)·A_{\mathrm{1}}.\end{array}$$

(6)

Let

$$\begin{array}{cc}& \beta =\mathrm{D}\mathrm{a}\mathrm{t}\mathrm{a}=\mu ·\rho ·A_{\mathrm{1}}=\mu ·\rho ·\frac{\theta d^{\mathrm{2}}}{\mathrm{2}}\end{array}$$

(7)

and then

$$\begin{array}{cc}& {\mathrm{D}\mathrm{a}\mathrm{t}\mathrm{a}}_i=\left(\mathrm{2}i-\mathrm{1}\right)\mathrm{D}\mathrm{a}\mathrm{t}\mathrm{a}.\end{array}$$

(8)

For simplicity, the following designations are adopted:

$$\begin{array}{cc}& e_{\mathrm{1}}=e_{\mathrm{t}\mathrm{x}},\\ e_{\mathrm{2}}=e_{\mathrm{r}\mathrm{x}}=E_{\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}}.\end{array}$$

(9)

Lemma 2.

To prolong the lifespan, the following relationship between $N_{CMi}$ and $N_{CMi+\mathrm{1}}$ has to be guaranteed:

$$\begin{array}{cc}& N_{CMi}=\frac{\left(\mathrm{2}i-\mathrm{1}\right)N_{CMi+\mathrm{1}}·e_{\mathrm{1}}}{\left(\mathrm{2}{N}_{CMi+\mathrm{1}}+\mathrm{1}-\mathrm{2}i\right)·e_{\mathrm{2}}}.\end{array}$$

(10)

Proof.

In order to balance the energy consumption, the energy dissipation rate of the ith ring should be equal to that of the $i+\mathrm{1}$ th ring. Consequently the following equation can be attained:

$$\begin{array}{cc}& \left(\mathrm{2}i-\mathrm{1}\right)·\beta ·e_{\mathrm{2}}+\left[\frac{\left(\mathrm{2}k-\mathrm{1}\right)·\beta }{N_{\mathrm{C}\mathrm{M}k}}+\frac{\left(\mathrm{2}k-\mathrm{3}\right)·\beta }{N_{\mathrm{C}\mathrm{M}k-\mathrm{1}}}+\cdots +\frac{\left(\mathrm{2}i+\mathrm{1}\right)·\beta }{N_{\mathrm{C}\mathrm{M}i+\mathrm{1}}}\right]·e_{\mathrm{1}}=\left(\mathrm{2}i-\mathrm{3}\right)·\beta ·e_{\mathrm{2}}+\left[\frac{\left(\mathrm{2}k-\mathrm{1}\right)·\beta }{N_{\mathrm{C}\mathrm{M}k}}+\cdots +\frac{\left(\mathrm{2}i-\mathrm{1}\right)·\beta }{N_{\mathrm{C}\mathrm{M}i}}\right]·e_{\mathrm{2}}+\left[\frac{\left(\mathrm{2}k-\mathrm{1}\right)·\beta }{N_{\mathrm{C}\mathrm{M}k}}+\frac{\left(\mathrm{2}k-\mathrm{3}\right)·\beta }{N_{\mathrm{C}\mathrm{M}k-\mathrm{1}}}+\cdots +\frac{\left(\mathrm{2}i-\mathrm{1}\right)·\beta }{N_{\mathrm{C}\mathrm{M}i}}+\frac{\left(\mathrm{2}i-\mathrm{3}\right)·\beta }{N_{\mathrm{C}\mathrm{M}i-\mathrm{1}}}\right]·e_{\mathrm{1}}.\end{array}$$

(11)

Then

$$\begin{array}{cc}& N_{\mathrm{C}\mathrm{M}i-\mathrm{1}}=\frac{\left(\mathrm{2}i-\mathrm{3}\right)N_{\mathrm{C}\mathrm{M}i}·e_{\mathrm{1}}}{\left(\mathrm{2}{N}_{\mathrm{C}\mathrm{M}i}+\mathrm{1}-\mathrm{2}i\right)·e_{\mathrm{2}}}.\end{array}$$

(12)

So

$$\begin{array}{cc}& N_{\mathrm{C}\mathrm{M}i}=\frac{\left(\mathrm{2}i-\mathrm{1}\right)N_{\mathrm{C}\mathrm{M}i+\mathrm{1}}·e_{\mathrm{1}}}{\left(\mathrm{2}{N}_{\mathrm{C}\mathrm{M}i+\mathrm{1}}+\mathrm{1}-\mathrm{2}i\right)·e_{\mathrm{2}}}\end{array}$$

(13)

is attained.

Lemma 3.

The size of cluster $N_{CMi}$ in $A_i$ can be determined through the value of $N_{CMk}$ , and the relationship between them can be described as

$$\begin{array}{cc}& N_{CMi}=\left[{{\displaystyle \prod }}_{j=i}^{k-\mathrm{1}}\frac{\left(\mathrm{2}j-\mathrm{1}\right)·N_{CMj+1}·e_{\mathrm{1}}}{\left(\mathrm{2}{N}_{CMj+\mathrm{1}}+\mathrm{1}-\mathrm{2}j\right)·e_{\mathrm{2}}}\right]·N_{CMk},\hspace{1em}i=\mathrm{1,2},\dots ,k-\mathrm{1}.\end{array}$$

(14)

Proof.

CHs in the outermost layer only need to transmit their own data, so the value of $N_{\mathrm{C}\mathrm{M}k}$ is relatively easy to determine. Then $N_{\mathrm{C}\mathrm{M}k-\mathrm{1}}$ can be attained via expression (15) as follows:

$$\begin{array}{cc}& N_{\mathrm{C}\mathrm{M}k-\mathrm{1}}=\frac{\left(\mathrm{2}k-\mathrm{3}\right)N_{\mathrm{C}\mathrm{M}k}·e_{\mathrm{1}}}{\left(\mathrm{2}{N}_{\mathrm{C}\mathrm{M}k}+\mathrm{1}-\mathrm{2}k\right)·e_{\mathrm{2}}}.\end{array}$$

(15)

Iterating the aforementioned process until the value of $N_{\mathrm{C}\mathrm{M}\mathrm{1}}$ is determined. Eventually, the value of $N_{\mathrm{C}\mathrm{M}i}$ can be obtained through the following expression:

$$\begin{array}{cc}& N_{\mathrm{C}\mathrm{M}i}=\left[{{\displaystyle \prod }}_{j=i}^{k-\mathrm{1}}\frac{\left(\mathrm{2}j-\mathrm{1}\right)·N_{\mathrm{C}\mathrm{M}j+\mathrm{1}}·e_{\mathrm{1}}}{\left(\mathrm{2}{N}_{\mathrm{C}\mathrm{M}j+\mathrm{1}}+\mathrm{1}-\mathrm{2}j\right)·e_{\mathrm{2}}}\right]·N_{\mathrm{C}\mathrm{M}k},\hspace{1em}i=\mathrm{1,2},\dots ,k-\mathrm{1}.\end{array}$$

(16)

The above expression suggests that $N_{\mathrm{C}\mathrm{M}i}\hspace{0.17em}\hspace{0.17em}\left(i=\mathrm{1,2},\dots ,k-\mathrm{1}\right)$ can be determined through the value of $N_{\mathrm{C}\mathrm{M}k}$ . Apparently, the CHs in sector k should deplete as little energy as possible; meanwhile the energy differentials between CH and CMs should be controlled within a certain range. Therefore a threshold is adopted according to the specific applications. It is represented by $T_{\mathrm{T}\mathrm{h}\mathrm{r}\mathrm{e}\mathrm{s}}$ in the coming analysis of this paper.

The determination of variable of $N_{\mathrm{C}\mathrm{M}k}$ can be transformed into an optimization problem:

$$\begin{array}{cc}& \mathrm{M}\mathrm{i}\mathrm{n}\hspace{1em}{E}_{\mathrm{C}\mathrm{M}k}=\mathrm{M}\mathrm{i}\mathrm{n}·\left[\left(\mathrm{2}k-\mathrm{1}\right)\beta -\mu N_{\mathrm{C}\mathrm{M}k}\right]e_{\mathrm{2}}+\frac{\left(\mathrm{2}k-\mathrm{1}\right)\beta }{N_{\mathrm{C}\mathrm{M}k}}·\left(E_{\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}}+{\epsilon }_{\mathrm{a}\mathrm{m}\mathrm{p}}{d}^{\alpha }\right)\\ \text{Subject to}\hspace{1em}\mu \left(N_{\mathrm{C}\mathrm{M}k}-\mathrm{1}\right)e_{\mathrm{2}}+\left(E_{\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}}+{\epsilon }_{\mathrm{a}\mathrm{m}\mathrm{p}}{d}^{\alpha }\right)-e_{\mathrm{2}}\le T_{\mathrm{T}\mathrm{h}\mathrm{r}\mathrm{e}\mathrm{s}}.\end{array}$$

(17)

4.1.3. The Optimal Cluster Size (OCS) Algorithm

According to Section 4.1.2, the optimal cluster size (OCS) algorithm can be described as follows: the sensor nodes send HELLO passage to the sink to indicate their location and energy information. Once receiving the HELLO message, the sink divides the area into k parts. Then it calculates $N_{\mathrm{C}\mathrm{M}i}$ based on expressions (17) and Lemma 3 according the specific parameters d and $T_{\mathrm{t}\mathrm{h}\mathrm{r}\mathrm{e}\mathrm{s}}$ . Finally, it sends broadcast message to all sensors to inform the optimal cluster size in different sectors. Besides, the number of clusters and the percentage of the CHs can be received. It is denoted as P and will be used in Section 4.3.

4.2. Cluster Head Selection Based on Game Theory

In this section, the game theory [28] is introduced briefly as the foundation to promote our research further. The superiority of the game theory in solving the conflict between individual and the collective is presented firstly. Subsequently, the evolutionary game theory model in the cluster head election is studied. The cluster head election algorithm based on the evolutionary game theory is given finally.

4.2.1. Evolutionary Game Theory

Game theory, which was proposed in 1944 [26], is a theory concerning decision-making. It provides guides to the participants who face a dilemma. In game theory, an important concept Nash Equilibrium was proposed in 1950 which has promoted the research of noncooperative game. When a game model reaches Nash Equilibrium, it means that players can hardly obtain more favorable utility via other actions.

The classical game theory is based on the assumption that all the players are perfectly rational. Then the prediction about the game is consistent with the actual results [26]. To be perfectly rational, it is necessary that in this paper every node should be aware of other nodes' action as well as their characteristics. Nevertheless, this demand cannot always be met owing to some practical reasons, such as energy constraint. So it is impossible for each player to be acquainted with the information of others. Besides, individual differences in intelligence and learning capacity will lead to the differences in the rational level.

Evolutionary game theory can be applied to the above situation. It was firstly introduced by Maynard Smith in 1974 [27]. In the real network environment, the assumption that players should be rational enough to determine their decisions is obviously not always satisfied. Given such context, evolutionary game theory can be utilized to solve some issues in the wireless sensor networks.

4.2.2. An Evolutionary Game Theory Model

In this part, a game model is presented firstly. Then a lemma is proposed which meets the evolution stable strategy. After the lemma proof, a novel cluster head selection algorithm and a routing protocol named Energy Efficient Routing protocol based on Evolutionary Game (EEREG) theory are given.

In an area with N nodes, the cluster head selection game can be represented by a three-tuple

$$\begin{array}{cc}& G\left(P,S,U\right),\end{array}$$

(18)

where P, S, and U represent the node set, the strategy set, and the utilities, respectively. P has two subsets H and L, which denote the node sets possess more energy and those with less energy relatively. Thereby

$$\begin{array}{cc}& P=H\cup L\\ H\cap L=\varphi \end{array}$$

(19)

should be founded. It means that every node in P belongs to either H or L. Each individual in P has two strategies to choose from to be cluster head or not to be cluster head (NCH). The utilities are given in the following section.

The clustering algorithm is regarded as a kind of promising energy-efficient protocols in WSNs [2, 10, 17, 23]. Ideally, the nodes in set H are expected to be CHs. They usually broadcast the ADV [20] packets to others within their transmission range and wait them to join in. However, just as being mentioned in the former section, the ADV messages are also sent by the class L nodes due to the limited rationality. If these nodes become CHs, their energy will be drained quickly. Then the dying process of WSNs will accelerate as the energy imbalance problem is exacerbated.

Evolutionary game theory provides a perfect solution because of its applications in the situation where players without perfect rationality need to cooperate with each other to achieve the Pareto Nash Equilibrium [28]. In order to maximize the collective interest, some rules are required to be instituted to restrict players' behavior. In this paper, the nodes must be regulated in selecting the heads. In this section the theoretical principle to regulate the nodes' behavior is given.

To encourage the nodes in subset H to be CHs and meanwhile prevent class L nodes from being selected, the utility function should be carefully devised. The utility function $u_i$ of each player in our model can be defined as follows:

$$\begin{array}{cc}& u_i=r_i-p_i,\hspace{1em}\left(i=\mathrm{1,2}\right),\end{array}$$

(20)

where $r_i$ and $p_i$ denote the profit and the penalty of node i, respectively. In this paper the values of them are related to the parameters $P_H$ , $P_L$ , e, Δ, and ${\bar{E}}_{\mathrm{r}\mathrm{e}}$ whose meanings are listed in Table 1. Our evolutionary game theory model involves two players: class H and class L nodes. According to the basic principle of game theory, the payoff matrix is put forward in Table 2.

Table 1

Some parameters used in the game model.

$$P_H$$	The proportion of the class H nodes
$$P_L$$	The proportion of the class L nodes
e	The energy consumed when acting as CH
Δ	The energy difference between class H and class L nodes
$${\stackrel{-}{E}}_{\text{re}}$$	The average residual energy of nodes

Table 2

The payoff matrix.

		The nodes with low energy
		To be cluster head	Not to be cluster head
The nodes with high energy	To be cluster head	$P_H\left(-\mathrm{\Delta }-e\right)$ , $P_L(-\mathrm{\Delta }-e)$	$-P_{H}e$ , $-P_{L}e$
	Not to be cluster head	$-2P_H\mathrm{\Delta }$ , $P_L(-2\mathrm{\Delta }-e)$	$-{\stackrel{-}{E}}_{\text{re}}$ , $-{\stackrel{-}{E}}_{\text{re}}$

Although the behavior of players is not so motivated due to the lack of full intelligence, the rate of a certain behavior tends to be stable when the evolutionary game theory is adopted. The change of rate is named replicator dynamics (RD) and the state is known to be the evolutionary stable strategies (ESS). When some conditions met, the game will enter into such a state quickly and remain steady. The following passage gives the proof about the existence of ESS via dynamics analysis. This lays the theoretical foundation for this paper and is also the innovation of EEREG.

Lemma 4.

The ESS of the evolutionary game is CH for H and NCH for L under given condition.

Proof.

The payoff matrix is shown in Table 2. For the sake of simplicity, the players are denoted as H and L. Assuming the rate of selecting CH strategy for H is x, hence that of choosing NCH is $(\mathrm{1}-x)$ . Similarly, those for L are y and $\mathrm{1}-y$ , respectively. In such way, H's expected utilities of CH strategy $U_{H-CH}$ and that of $U_{H-NCH}$ are, respectively, expressed as

$$\begin{array}{cc}& U_{H-CH}=y{P}_H\left(-\Delta -e\right)+\left(\mathrm{1}-y\right)\left(-P_{H}e\right)=-y{P}_{H}e,\end{array}$$

(21)

$$\begin{array}{cc}& U_{H-NCH}=y\left(-\mathrm{2}{P}_H\Delta \right)+\left(\mathrm{1}-y\right)\left(-{\bar{E}}_{\mathrm{r}\mathrm{e}}\right)=-\mathrm{2}y{P}_H\Delta -{\bar{E}}_{\mathrm{r}\mathrm{e}}+y{\bar{E}}_{\mathrm{r}\mathrm{e}}.\end{array}$$

(22)

The average revenue of H can be denoted as follows:

$$\begin{array}{cc}& {\bar{U}}_H=x\left(-y{P}_H\Delta -P_{H}e\right)+\left(\mathrm{1}-x\right)\left(-\mathrm{2}y{P}_H\Delta -{\bar{E}}_{\mathrm{r}\mathrm{e}}+y{\bar{E}}_{\mathrm{r}\mathrm{e}}\right)=xy{P}_H\Delta -x{P}_{H}e-\mathrm{2}y{P}_H-{\bar{E}}_{\mathrm{r}\mathrm{e}}+y{\bar{E}}_{\mathrm{r}\mathrm{e}}+x{\bar{E}}_{\mathrm{r}\mathrm{e}}-xy{\bar{E}}_{\mathrm{r}\mathrm{e}}.\end{array}$$

(23)

Now the replication dynamic analysis is done, and the replicator dynamics equation is

$$\begin{array}{cc}& \frac{dx}{dt}=x\left(U_{H-CH}-{\bar{U}}_H\right)=x\left(-y{P}_H\Delta -P_{H}e-xy{P}_H\Delta +x{P}_{H}e+\mathrm{2}y{P}_H\Delta +{\bar{E}}_{\mathrm{r}\mathrm{e}}-y{\bar{E}}_{\mathrm{r}\mathrm{e}}-x{\bar{E}}_{\mathrm{r}\mathrm{e}}+xy{\bar{E}}_{\mathrm{r}\mathrm{e}}\right)=x\left(\mathrm{1}-x\right)\left[{\bar{E}}_{\mathrm{r}\mathrm{e}}-P_{H}e-y\left({\bar{E}}_{\mathrm{r}\mathrm{e}}-P_H\Delta \right)\right].\end{array}$$

(24)

Likewise, the following expressions can be obtained:

$$\begin{array}{cc}& U_{L-CH}=x{P}_L\left(-\Delta -e\right)+\left(\mathrm{1}-x\right)\left(-\mathrm{2}\Delta -e\right)=x{P}_L\Delta -\mathrm{2}{P}_L\Delta -P_{L}e,\\ U_{L-NCH}=x\left(-P_{L}e\right)+\left(\mathrm{1}-x\right)\left(-{\bar{E}}_{\mathrm{r}\mathrm{e}}\right)=-x{P}_{L}e-{\bar{E}}_{\mathrm{r}\mathrm{e}}+x{\bar{E}}_{\mathrm{r}\mathrm{e}},\\ {\bar{U}}_L=y\left(x{P}_L\Delta -\mathrm{2}{P}_L\Delta -P_{L}e\right)+\left(\mathrm{1}-y\right)\left(-x{P}_{L}e-{\bar{E}}_{\mathrm{r}\mathrm{e}}+x{\bar{E}}_{\mathrm{r}\mathrm{e}}\right)=xy{P}_L\Delta -\mathrm{2}y{P}_L\Delta -y{P}_{L}e-x{P}_{L}e-{\bar{E}}_{\mathrm{r}\mathrm{e}}+x{\bar{E}}_{\mathrm{r}\mathrm{e}}+xy{P}_{L}e+y{\bar{E}}_{\mathrm{r}\mathrm{e}}-xy{\bar{E}}_{\mathrm{r}\mathrm{e}},\\ \frac{dy}{dt}=y\left(U_{L-CH}-{\bar{U}}_L\right)=y\left(\mathrm{1}-y\right)\left[{\bar{E}}_{\mathrm{r}\mathrm{e}}-\mathrm{2}{P}_L\Delta -P_{L}e-x\left({\bar{E}}_{\mathrm{r}\mathrm{e}}-P_L\Delta -P_{L}e\right)\right].\end{array}$$

(25)

Subsequently, the dynamic replication phase diagrams are shown as Figures 5 and 6. Figure 5 shows that $x^{\ast }=\mathrm{1}$ is ESS of player H when condition

$$\begin{array}{cc}& y<\frac{{\bar{E}}_{\mathrm{r}\mathrm{e}}-P_{H}e}{{\bar{E}}_{\mathrm{r}\mathrm{e}}-P_H\Delta }\end{array}$$

(26)

is met. Likewise, $y^{\ast }=\mathrm{0}$ is ESS of L when

$$\begin{array}{cc}& x>\frac{{\bar{E}}_{\mathrm{r}\mathrm{e}}-\mathrm{2}{P}_L\Delta -P_{L}e}{{\bar{E}}_{\mathrm{r}\mathrm{e}}-P_L\Delta -P_{L}e}.\end{array}$$

(27)

Figure 7 shows that the strategy combination is as follows: class H nodes decide to be CHs and class L nodes act as CMs. This strategy combination is ESS if x and y satisfy the above conditions at the same time. Thus the ESS can be reached if the sink regulates the initial values of x and y. For the sake of convenience, inequalities (26) and (27) are called critical conditions.

Figure 5

Dynamic replication phase diagram of H when $y<\left({\bar{E}}_{\mathrm{r}\mathrm{e}}-P_{H}e\right)/\left({\bar{E}}_{\mathrm{r}\mathrm{e}}-P_H\Delta \right)$ .

Figure 6

Dynamic replication phase diagram of L when $x>\left({\bar{E}}_{\mathrm{r}\mathrm{e}}-\mathrm{2}{P}_L\Delta -P_{L}e\right)/\left({\bar{E}}_{\mathrm{r}\mathrm{e}}-P_L\Delta -P_{L}e\right)$ .

Figure 7

The relationship between the two players' dynamic replication.

Because the size of cluster is determined by OCS algorithm, the percent of CHs P is used in the cluster formation phase. Thus two critical values $x_{\mathrm{c}\mathrm{r}}$ and $y_{\mathrm{c}\mathrm{r}}$ are given as follows:

$$\begin{array}{cc}& x_{\mathrm{c}\mathrm{r}}=P·\frac{{\bar{E}}_{\mathrm{r}\mathrm{e}}-\mathrm{2}{P}_L\Delta -P_{L}e}{{\bar{E}}_{\mathrm{r}\mathrm{e}}-P_L\Delta -P_{L}e},\\ y_{\mathrm{c}\mathrm{r}}=P·\frac{{\bar{E}}_{\mathrm{r}\mathrm{e}}-P_{H}e}{{\bar{E}}_{\mathrm{r}\mathrm{e}}-P_H\Delta }.\end{array}$$

(28)

The nodes' behavior is directly influenced by x and y. Lemma 4 shows that nodes will select CHs in an ideal way if critical conditions are both met. From inequalities (26) and (27) it can be obtained that x and y are determined by average residual energy of network and energy range. They are key indexes for the lifespan of WSNs. It means the nodes' behavior is in accordance with the energy efficiency. Therefore, this clustering formation algorithm can increase energy utilization.

4.3. Energy-Efficient Clustering Routing Protocol

Based on the evolutionary game theory, the Energy Efficient Routing protocol based on Evolutionary Game (EEREG) theory is presented. It comprises three components: optimal cluster size determination, cluster formation, and data transmission phase. The first one is processed according to OCS algorithm and the last one is the same as most clustering routing protocols, so this part mainly introduces the cluster formation algorithm. Its novelty lies in the fact that the cluster selection is controlled by energy efficiency via game theory. When the energy is distributed equally, each node has the same possibility of selecting itself as CH. Only class H nodes tend to be CH when energy is imbalanced. Furthermore, the bigger the energy range is, the higher the probability they have. The algorithm is explained as follows.

Firstly, each sensor node sends hello message which contains its position, energy information to the sink, and then the latter generates the following parameters: $P_H$ , $P_L$ , e, ${\bar{E}}_{\mathrm{r}\mathrm{e}}$ , and Δ. As the environment of the sensor nodes is changing from time to time, these parameters have to be adjusted in a certain cycle T. Note that e equals the product of $e_{\mathrm{1}}$ and the average number of CMs. Then it determines the initial critical conditions via inequalities (26) and (27) and sends them to sensor nodes. The final critical values sent to sensor nodes should be adjusted according to parameter P which is obtained in Section 4.1.3. Finally, the sink broadcasts message to the sensor nodes to announce the critical values and ${\bar{E}}_{\mathrm{r}\mathrm{e}}$ .

On receiving the broadcast message, the sensor node generates a random number ranging from 0 to 1 firstly. Its residual energy is compared with ${\bar{E}}_{\mathrm{r}\mathrm{e}}$ to decide which classes it belongs to. It belongs to class H when its residual energy is larger; otherwise it belongs to class L. The class H node compares the random number with $x_{\mathrm{c}\mathrm{r}}$ . It acts as CH when the former is smaller. Similarly, class L node decides to be NCH if its random number is smaller than $y_{\mathrm{c}\mathrm{r}}$ . Then it waits for the ADV [20] from CHs. The initial value of x and y conforms to the critical condition, so class H nodes tend to be CHs and class L nodes tend to be CMs. Moreover, the critical values change dynamically along with the energy status of WSNs. So it is obvious that the cluster head distribution can adapt to that of energy.

Once a node is determined to be CH, it broadcasts ADV messages. The CMs which receive ADV will decide which CHs to join in. Subsequently, they send join REQ [20] message to the CH. At last, the process of cluster formation terminates. Then CHs act as local control centers to coordinate the data transmission [20]. The cluster formation takes place round by round in every period T.

5. Experimental Validation

In this section, a comparison between the experiment results in EEREG, LEACH, and LEACH-C protocols is made via a network simulator NS2 [4, 16], which is widely used in the network simulation. To evaluate the performance of EEREG, the lifetime of network, energy efficiency, and some other parameters should be compared. For convenience, the following passage gives some definitions.

5.1. Some Definitions

In order to measure the lifetime of network, the following metrics are introduced firstly:

Time until the First Node Dies (TFND): it indicates the duration for witch all the nodes on the network are alive. Similarly, the Time until Half of the Node Dies (THND) and the Time until the Last Node Dies (TLND) are also defined. The three metrics reflect the lifespan of WSNs.

Total Number of Nodes Alive (TNNA): it is also related to the network $\text{lifetime}[]$ . It gives an idea of the area coverage of the network over time.

Average Residual Energy (ARE) of the sensor nodes: it reflects the energy efficiency on average. In general, the bigger it is, the longer life the network would have.

Total Number of Data Signal (TNDS) received by the sink: it is adopted in this paper to evaluate the performance of the routing protocol EEREG.

Throughput against Energy (TE) consumed: It reflects the energy efficiency more intuitively. If a network can process more data with the given energy, more energy-efficient is obvious.

5.2. Simulation Setting and Results Analysis

The network is deployed in a plane domain with the size of 100 × 100. The sensor nodes are randomly distributed. The parameters used in this simulation are listed in Table 3. The parameters are similar to most of the references adopted. It will simplify the simulation but will not reduce the reliability of the comparison. To evaluate the performance of EEREG, LEACH, DHAC [29, 30], TEEN [31], and PEGASIS [32] are used to compare with EEREG. The meanings of d and $T_{\mathrm{T}\mathrm{h}\mathrm{r}\mathrm{e}\mathrm{s}}$ are the same as those in Section 4.1.2.

Table 3

The parameters used in the simulation.

Network space	100 × 100
The position of the sink	( $\mathit{0,0}$ )
The number of the sensor nodes	100
The initial energy of each node	2 J
$$E_{\text{elec}}$$	50 nJ/bit
$${\epsilon }_{\text{amp}}$$	13 pJ/bit/m2
Packet length	500 bits
Simulation time	3600 seconds
d	68
$$T_{\text{Thres}}$$	0.002 J
T	30 seconds

To make sure that the CHs transmit data to each other through free space, the value of d should be lower than 87 m [14, 15]. From the parameters listed in Table 3, the number of sectors is easily obtained to be 3. Besides, the cycle T is set to be 30 s which is larger than that of LEACH because of the energy efficiency of EEREG.

Figure 8 shows the variance of TNNA of the five protocols. It is clear that EEREG balances the energy consumption among the clusters in the best way, and LEACH performs worse because of its randomly rotating its CHs. EEREG decides the size of clusters by OCS algorithm; besides, it selects the CHs based on evolutionary game algorithm. Thus, its energy efficiency is higher. PEGASIS also has a very large TLND but its TFND is too small.

Figure 8

The change of TNNA during the simulation.

Table 4 shows comparison of the network lifetime among the five routing protocols. According to Section 5.1, the lifespan can be measured by TFND, THND, and TLND. So Table 4 lists comparison results. All the three protocols DHAC, TEEN, and PEGASIS beat LEACH in terms of extending the network lifespan. It is clear that TFND of TEEN is large but its TLND is small, while PEGASIS is completely on the contrary. However, EEREG extends TFND over TEEN by 30.7% and extends TLND over PEGASIS by 11.2%. Therefore, EEREG can prolong the network lifetime to some extent. Figure 9 shows the results of Table 4 in picture clearly.

Table 4

The metrics of lifespan.

	TFND	THND	TLND
LEACH	390	520	600
DHAC	1120	1310	1540
TEEN	1010	1260	1430
PEGASIS	810	1370	1780
EEREG	1320	1560	1980

Figure 9

Comparison between FND, HND, and LND.

Figure 10 depicts the variance of Average of Residual Energy (ARE) of different protocols. Although ARE of EEREG is lower than others occasionally, on the whole it is higher than others. Besides, its curve lasts longer time than others. It means EEREG can effectively extend the network lifetime and features higher energy efficiency.

Figure 10

The comparison of ARE.

Figure 11 gives the variance the amount of data received by the sink during the simulation. The curve of EEREG is above other four overly. Due to its longer lifetime, it is apparent that the amount of data transmitted is larger. Besides, it adopts less cycle time to rotate the CHs, so the data received by the sink is larger. It reflects the energy efficiency to some extent.

Figure 11

The sum of data received by the sink.

Figure 12 shows the curve of Throughput against Energy (TE) consumed. As described in Section 5.1, it reflects the energy efficiency directly. The bigger it is, the higher the energy efficiency would be. Although in first half period the value of TE is almost the same between the four protocols, EEREG stands out since sixty percent of energy is used up. It is proved to have better performance.

Figure 12

Throughput against Energy (TE) consumed.

6. Conclusions and Future Work

In this paper, the problem existing in the clustering protocol is analyzed firstly. Then the mathematical model is presented to achieve traffic load equilibrium. Subsequently, the relationship between the cluster size and the distance to the sink is proposed. Furthermore, the algorithm named the optimal cluster size (OCS) algorithm has been proposed to calculate the optimal cluster size. Secondly, the defect existing in the cluster formation phase is pointed out via a simple example. Then, the evolutionary game model is introduced to restrain the nodes' behaviors when CH is selected. It has been proved that that ESS can be obtained under given critical conditions. Thus the state of anarchy could be avoided to lessen the energy consumption when clusters forms.

Finally, the Energy Efficient Routing protocol based on Evolutionary Game (EEREG) theory is presented. Afterwards the network simulation experiment has been made to corroborate our previous analysis and evaluate the performance of the novel routing protocol. The results show that the proposed EEREG protocol can achieve our goal very well. It can extend the lifespan and balance the energy consumption at the same time.

As the sensor devices have limited supply of energy, energy efficiency is believed to be the most important for any protocols designed for WSNs [33]. However, for a long time, security aspects in routing protocols have not been given enough attentions. Most of them have not been designed with security requirements [34]. However, as the applications in critical infrastructures grow wider and wider, security should be taken into consideration. Thus the routing protocol which takes both energy-efficient and security into account is the author's further research direction.