Ant-Based Transmission Range Assignment Scheme for Energy Hole Problem in Wireless Sensor Networks

Abstract

We investigate the problem of uneven energy consumption in large-scale many-to-one sensor networks (modeled as concentric coronas) with constant data reporting, which is known as an energy hole around the sink. We conclude that lifetime maximization and the energy hole problem can be solved by searching optimal transmission range for the sensors in each corona and then prove this is an NP-hard optimization problem. In view of the effectiveness of ant colony algorithms in solving combinatorial optimization problems, we propose an ant-based heuristic algorithm (ASTRL) to address the optimal transmission range assignment for the goal of achieving life maximization of sensor networks. Experimentation shows that the performance of ASTRL is very close to the optimal results obtained from exhaustive search method. Furthermore, extensive simulations have also been performed to evaluate the performance of ASTRL using various simulation parameters. The simulation results reveal that, with low communication cost, ASTRL can significantly mitigate the energy hole problem in wireless sensor networks with either uniform or nonuniform node distribution.

1. Introduction

Rapid technological advances in microelectromechanical systems (MEMS) and low-power wireless communications have enabled the deployment of large scale wireless sensor networks (WSNs). The potential applications of sensor networks are highly varied, such as environmental monitoring, target tracking, and battlefield surveillance [1, 2]. Due to limited and nonrechargeable energy provision, the energy resource of sensor networks should be managed wisely to extend the lifetime of sensors [3–7].

The sink node in a WSN receives the data from the sensor nodes and forwards these data to the applications over the WSN. Usually, the sensor nodes closest to the sink tend to deplete their energy budget more rapidly than others [8–10] because such nodes need to transmit more data than other nodes. This causes the problem of energy hole around the sink. A WSN suffering from the energy hole problem cannot deliver more data, and consequently the network lifetime has been greatly shortened, although most of the sensor nodes can still work properly.

Recently, there have been a number of studies done on the energy hole problem for improving the network lifetime. Generally, these studies aiming to mitigate or solve the energy hole problem can be divided into 3 categories: (i) assistant approaches, such as deployment assistance, traffic compression, and aggregation in [11]; (ii) node distribution strategies. Lian et al. in [9] propose a nonuniform sensor distribution strategy. The density of sensors increases when their distance to the sink decreases; (iii) adjustable transmission range. Jarry et al. [12] propose a mixed routing algorithm which allows each sensor node to send a message either to one of its immediate neighbors or to the base station directly.

Since adjusting transmission range of sensors is a promising way to be used for prolonging lifetime of sensor networks, we solve the energy hole problem by performing optimizing the transmission range assignment based on corona model in [8]. We prove that the problem of optimal transmission range assignment in coronas to achieve minimum energy consumption is an NP-hard problem, and therefore an approximation algorithm with low communication cost should be proposed for network lifetime optimization. However, the existing researches [3, 12, 13] on addressing energy hole problem in category (iii) mainly work in a preplanned manner. The cooperation, communication, and management are deliberately modeled, designed, and tuned before the deployment of sensors. These methods usually ignore the requirements of self-adaptation and self-calibration and always produce complex protocols with higher overhead and just passable performance, which act dully to the change of environment. Fortunately, inspired by the ecosystem, some biologic models are applied in networks [14–16]. These biologic models exhibit swarm intelligence in pursuing a global optimal goal and throw new light on the energy hole problem in WSN.

Recently, the Ant Colony Algorithm (ACO) has been widely used in solving the combinatorial optimization problems. Through the simple cooperation of solo entity and the positive feedback mechanism, ACO outperforms tradition manners in terms of self-adaptation and self-calibration. In this paper, we propose an ant-based algorithm (ASTRL) for mitigating the energy hole problem in order to prolong the lifetime of networks with different node distributions. As far as we know, we are the first to use bioinspired methods to solve the energy hole problem in WSNs.

The remainder of the paper is organized as follows. Section 2 presents our literature review. Section 3 introduces the system assumption used throughout our work and then analyzes the energy hole problem and concludes that the problem of searching optimal transmission range list is a multiobjective problem. Section 4 gives the design details of ANT-based algorithm for mitigating energy hole problem in WSNs. Section 5 shows the effectiveness of the ASTRL via extensive simulations. Section 6 concludes this paper.

2. Related Works

Li and Mohapatra [17] investigate the problem of uneven energy consumption in a large class of many-to-one sensor networks. The authors describe the energy hole in a ring model (like corona model) and present the definitions of the per node traffic load and the per node energy consuming rate (ECR). In a many-to-one sensor network, all sensor nodes generate constant bit rate (CBR) data and send them to a single sink via multihop transmissions. Based on the observation that sensor nodes sitting around the sink need to relay more traffic compared to other nodes in outer subregions, their analysis verifies that nodes in inner rings suffer much faster energy consumption rates and thus have much shorter expected lifetime. The authors term this phenomenon of uneven energy consumption rates as the energy hole problem, which may result in serious consequences, for example, early dysfunction of the entire network. The authors present some approaches to the energy hole problem, including deployment assistance, traffic compression, and aggregation. Jarry et al. [12] propose an algorithm to resolve the energy hole problem, which uses mobile sensors to heal energy holes. The cost of these assistant approaches is a lot.

Lian et al. [9] argue that, in static situations, for large-scale networks, after the lifetime of the sensor network is over, there is still a great amount of energy left unused, which can be up to 90% of total initial energy. Thus, the static models with uniformly distributed homogenous sensors cannot efficiently utilize their energy. The authors propose a nonuniform sensor distribution strategy. The density of sensors increases when their distance to the sink decreases. Their simulation results show that, for networks with high density, the nonuniform sensor distribution strategy can increase the total data capacity by an order of magnitude. Wu et al. [18] propose a nonuniform node distribution strategy to achieve the subbalanced energy depletion. The authors state that, if the number of nodes in coronas increases from corona $C_{R-\mathrm{1}}$ to corona $C_{\mathrm{1}}$ in a geometric progression with common ratio $q>\mathrm{1}$ and there are $N_{R-\mathrm{1}}/(q-\mathrm{1})$ nodes in corona $C_R$ , then the network can achieve subbalanced energy depletion. Here, Ni denotes the number of nodes in corona $C_i$ . But the node distribution strategy can hardly work in the real world, because in most cases the node distribution is random and hence an uncontrollable node density in local area.

Olariu and Stojmenovic [8] discuss the relationship between the network lifetime and the width of each corona in concentric corona model. The authors prove that, in order to minimize the total amount of energy spent on routing along a path originating from a sensor in a corona and ending at the sink, all the coronas must have the same width. However, the authors assume that all nodes in corona $C_i$ should forward data in corona $C_{i-\mathrm{1}}$ , and the transmission range in corona $C_i$ is $r_i-r_{i-\mathrm{1}}$ (here $C_i$ is the subarea delimited by the circles of radii $r_{i-\mathrm{1}}$ and $r_i$ ). If each corona has different width and different transmission range, we think this assumption may lead to the waste of energy for transmission. For example, as shown in Figure 1, the width of corona $C_i$ is larger than that of corona $C_{i-\mathrm{1}}$ and all nodes in $C_i$ have the same transmission range of $r_i-r_{i-\mathrm{1}}$ that is larger than the width of corona $C_{i-\mathrm{1}}$ . Divide the corona $C_i$ into two subcoronas, namely, $s_{\mathrm{1}}$ and $s_{\mathrm{2}}$ (see in Figure 1). The width of subcorona $s_{\mathrm{1}}$ is equal to that of corona $C_{i-\mathrm{1}}$ , so nodes in $s_{\mathrm{1}}$ will transmit data to $C_{i-\mathrm{1}}$ . The nodes in subcorona $s_{\mathrm{2}}$ which are close to corona $C_{i-\mathrm{1}}$ with transmission range larger than the width of corona $C_{i-\mathrm{1}}$ may transmit data across corona $C_{i-\mathrm{1}}$ to corona $C_{i-\mathrm{2}}$ that is closer to the sink node. Because of the authors assumption that the data transmitted from all nodes in corona $C_i$ should be forwarded for the next hop in corona $C_{i-\mathrm{1}}$ rather than corona $C_{i-\mathrm{2}}$ , these nodes in $s_{\mathrm{2}}$ with transmission range $r_i-r_{i-\mathrm{1}}$ which can transmit data to $C_{i-\mathrm{2}}$ but should transmit to $C_{i-\mathrm{1}}$ will waste energy for transmission.

Figure 1

The energy problem caused by corona model with different width.

For balancing the energy load among sensors in the network, Jarry et al. [12] propose a mixed routing algorithm which allows each sensor node to send a message either to one of its immediate neighbors or to the base station directly. The decision about the next receiver is determined by a potential function depending on its remaining energy. However, when the network area radius is bigger than the sensors maximal transmission range, the proposed algorithm cannot be applicable.

Some biologically intelligent algorithms have been used to solve routing problems in networks. Di Caro and Dorigo [19] propose AntNet, an approach to the adaptive learning of routing tables in communications networks. AntNet, the routing algorithm they proposed, is a mobile agents system showing some essential features of parallel replicated Monte Carlo systems. The algorithm takes inspiration from previous work on artificial ant colonies techniques to solve combinatorial optimization problems and telephone network routing. The core ideas of these techniques are (i) the use of repeated and concurrent simulations carried out by a population of artificial agents called ants to generate new solutions to the problem, (ii) the use by the agents of stochastic local search to build the solutions in an incremental way, and (iii) the use of information collected during past simulations to direct future search for better solutions.

Ant routing has shown excellent performance for sensor networks. Aghaei et al. [20] present an AntNet-based routing network, which meets the enhanced sensor network requirements, including energy consumption, success rate, and time delay. Okdem and Karaboga [21] have developed a routing scheme and adapted ACO algorithm to this scheme to get a dynamic and reliable routing protocol. Their algorithm has also been implemented in router chip, which provides an easy handling of WSN routing operations for sensor node designers.

3. System Model

In this section, the network model, energy model and corona model will be presented, respectively.

3.1. Network Model

We assume our sensor network model as follows: (1) once deployed, the sensors must work unattended, and all sensor nodes are static. Each sensor has a nonrenewable energy budget, and the initial energy of each sensor is $ϵ>\mathrm{0}$ ; (2) each sensor has a maximum transmission range, denoted as $t_x$ , and assumed to be much smaller than R (the furthest possible distance from a sensor to the sink node); (3) sensors are required to send their sensed data constantly at a certain rate. For sake of simplicity, we assume that each sensor node generates and sends L bits of data per unit time; (4) we assume there is a perfect MAC layer in the network, that is, transmission scheduling is so perfect that there is no collision and retransmission. Initially the network is well connected. The issue that what node density can ensure network connectivity is investigated in [13]; (5) based on greedy forwarding approach, sensor nodes transmit data packets to the sink. In such greedy forwarding scheme, data packets are transmitted to the next-hop node which is closer to the destination.

Definition 1 (network lifetime).

Li and Mohapatra in [17] present the definition of system lifetime, which is the time till a proportion of nodes die. A corona of sensor nodes in the network is said to be dead when it is unable to forward any data or send its own data. So the network lifetime in this paper is defined as the duration from the very beginning of the network until the first corona of sensor nodes dies.

3.2. Energy Model

A typical sensor node comprises three basic units: sensing unit, processing unit, and transceivers. Our energy model only involves the power for receiving and transmitting data without considering the energy consumed for sensing and processing data, which depends on the computation hardware architecture and the computation complexity. According to [17], the energy consumption formulas that we use in the analysis and simulations throughout the rest of this paper are as follows:

$$\begin{array}{cc}& E_{\mathrm{trans}}=\left({\beta }_{\mathrm{1}}+{\beta }_{\mathrm{2}}{d}^{\alpha }\right)l,\end{array}$$

(1)

$$\begin{array}{cc}& E_{\text{rec}}={\beta }_{\mathrm{3}}l.\end{array}$$

(2)

Here $E_{\mathrm{trans}}$ denotes the energy consumption for transmitting and $E_{\text{rec}}$ denotes the energy consumption for receiving. l (in bits/sec) is the data rate of each sensor node, and α is $\mathrm{2}$ or $\mathrm{4}$ . The term $d_{\alpha }$ accounts for the path loss. According to [17], some typical values of the above parameters in current sensor technologies are as follows:

$$\begin{array}{cc}& {\beta }_{\mathrm{1}}=\mathrm{45}\times \frac{\mathrm{1}{\mathrm{0}}^{-\mathrm{9}}\hspace{0.17em}\text{J}}{\text{bit}},\\ {\beta }_{\mathrm{2}}=\mathrm{10}\times \frac{\mathrm{1}{\mathrm{0}}^{-\mathrm{12}}\hspace{0.17em}\text{J}/\text{bit}}{{\text{m}}^{\mathrm{2}}}\hspace{1em}\left(\text{when}\mathrm{\hspace{0.17em}\hspace{0.17em}}\alpha =\mathrm{2}\right),\end{array}$$

(3) or

$$\begin{array}{cc}& {\beta }_{\mathrm{2}}=\mathrm{0}.\mathrm{001}\times \frac{{\mathrm{10}}^{-\mathrm{12}}\hspace{0.17em}\text{J}/\text{bit}}{{\text{m}}^{\mathrm{4}}}\hspace{1em}(\text{when}\mathrm{\hspace{0.17em}\hspace{0.17em}}\alpha =\mathrm{4}),\\ {\beta }_{\mathrm{3}}=\mathrm{139}\times \frac{\mathrm{1}{\mathrm{0}}^{-\mathrm{9}}\hspace{0.17em}\text{J}}{\text{bit}}.\end{array}$$

(4)

3.3. Corona Model with Adjustable Transmission Range

In order to save energy, sensors can adjust their transmission ranges. For simplicity, we divide the maximum transmission range into k levels, that is, $\{(\mathrm{1}/k)t_x,(\mathrm{2}/k)t_x,(\mathrm{3}/k)t_x,\dots ,t_x\}$ . As shown in Figure 2, each sensor has k levels of transmission range to choose. The Unit Length of Transmission Range (ULTR) is denoted by d:

$$\begin{array}{cc}& d=\frac{t_x}{k}.\end{array}$$

(5)

Figure 2

Illustration of adjustable transmission ranges.

We partition the whole area with radius R into m adjacent concentric parts termed coronas. They are presented as follows (see Figure 3), which has been discussed in [22, 23]. The width of each corona is 1ULTR therefore,

$$\begin{array}{cc}& m=\frac{R}{d}.\end{array}$$

(6) Assume that all the sensor nodes located in the same corona have the same transmission range, and the transmission ranges of the sensor nodes located in different coronas can be different. Therefore, if the transmission range of one node is i ULTR; its real transmission range can be calculated by the following equation:

$$\begin{array}{cc}& i\times d=i\times \left(\frac{t_x}{k}\right).\end{array}$$

(7)

Figure 3

Concentric coronas.

Generally, there are the following two data forwarding patterns in corona model.

• (1)

$k=\mathrm{1}$ . As shown in Figure 4(a), corona $C_i$ relays all the data generated or forwarded by corona $C_{i+\mathrm{1}}$ to the sink node.

(2)

$k>\mathrm{1}$ . The next-hop corona of corona $C_{i+\mathrm{1}}$ is determined by its assigned transmission range, which has been illustrated in Figure 4(b). Here, we use TRL to indicate the transmission range list of all coronas. Intuitively, the second data forwarding pattern can do better in solving energy hole problem, and therefore it has been adopted in this paper.

Figure 4

Two data forwarding patterns in corona model.

4. Ant-Based Algorithm for Searching Transmission Range List (ASTRL)

Consider an arbitrary wedge W subtended by an angle of θ, and refer to Figure 5. W is partitioned into msectors $C_{\mathrm{1}},C_{\mathrm{2}},\dots ,C_m$ by its intersection with m concentric circles, centered at the sink, and of monotonically increasing radii $r_{\mathrm{1}}<r_{\mathrm{2}}<\cdots <r_k=R$ . For convenience of notation we write $r_{\mathrm{0}}=\mathrm{0}$ and interpret $C_{\mathrm{0}}$ as the sink itself. Each sector $C_i$ selects a node as a corona head denoted as $H_i$ to determine the transmission range of all nodes in this sector.

Figure 5

A sector W and the associated subcoronas.

4.1. Construction Graph

Each node has k transmission range levels to choose, so nodes in each corona have k coronas to be the possible next hop. Figure 6(a) shows all available routes with $k=\mathrm{2}$ , termed as construction graph in ACO. In the construction graph, vertex denotes each subcorona. And if sector $C_i$ has a transmission range which can transmit data to sector $C_j$ , there is a directed edge $(C_i,C_j)$ from $C_i$ to $C_j$ . The artificial ants can construct solutions in the construction graph by randomized walks.

Figure 6

Construction graph and spanning tree.

The characters of the construction graph are as follows.

• (1)

Out-degree: vertexes with ID bigger than k have k out-degrees, and the out degree of each vertex whose ID is not-bigger than k is equal to its sector ID.

(2)

In-degree: the vertexes of outmost k sectors have $(m-i)$ in-degrees (where m is the number of sectors and i is the sector ID), and each of other vertexes has k in-degrees, including the sink node.

(3)

The edge $(A_i,A_j)\hspace{0.17em}\hspace{0.17em}(\mathrm{1}\le i,\hspace{0.17em}\hspace{0.17em}j\le m)$ should satisfy the condition $i>j$ .

In Section 3, we have discussed that, in order to mitigate energy hole problem and maximize network lifetime, we need to search an optimal transmission range list. According to the list we can obtain a spanning tree from the construction graph (see Figure 6(b)). The root of the obtained spanning tree is sink node. The following are the characters of the spanning tree.

• (1)

Out-degree: each vertex has only one out-degree.

(2)

In-degree: each vertex has not more than k in-degrees.

(3)

The edge $(A_i,A_j)\hspace{0.17em}\hspace{0.17em}(\mathrm{1}\le i,\hspace{0.17em}\hspace{0.17em}j\le m)$ should satisfy the condition $i>j$ .

Because searching optimal transmission range lists is NP hard, we propose an ant-based algorithm to achieve optimizing using energy for transmission. In the construction graph, artificial ants generated from each vertexes travel toward the sink node to discover feasible paths with low energy consumption.

4.2. ASTRL Design

In ASTRL, we employ two types of ants: (i) forward ant ( $Fant$ ), which travels from the source nodes to the sink node, and (ii) backward ant ( $Bant$ ), which is generated by $Fant$ when $Fant$ reaches the sink node.

The artificial ants read and write in the following three data structures stored in each corona head (see in Figure 7).

• (1)

A pheromone table $R_i$ , which records the pheromone of each edge started from the vertex of this corona in construction graph. Let ${\tau }_{i,j}$ denote the edge $(i,r)$ with transmission range j, so $r=i-j$ . The initial pheromone of edge $(i,r)$ is obtained as follows:

$$\begin{array}{cc}& {\tau }_{i,j}=\frac{\mathrm{1}}{W_{i,j}\left(\mathrm{0}\right)}=\frac{\mathrm{1}}{L\left[{\beta }_{\mathrm{1}}+{\beta }_{\mathrm{2}}{\left(x_{i}d\right)}^{\alpha }\right]\mathrm{\hspace{0.17em}\hspace{0.17em}}}.\end{array}$$

(8) Here, $W_{i,j}(\mathrm{0})$ denotes the $ECR$ value of sending data generated by itself with transmission range level j during unit time in $C_i$ . After each interval $\delta t$ , the pheromone of each edge in construction graph will be reduced, termed as evaporation. Let γ denote the evaporation coefficient, which can balance the ability of exploring new routes and that of storing energy-efficient routes:

$$\begin{array}{cc}& {\tau }_{i,j}⟵{\tau }_{i,j}-\mathrm{\hspace{0.17em}\hspace{0.17em}}\gamma {\tau }_{i,j}.\end{array}$$

(9)

(2)

A routing table $T_i$ , with probabilistic entries. $T_i$ defines the probabilistic routing policy currently adopted at corona head $H_i$ for each transmission range j: for the destination $C_{\mathrm{0}}$ (sink node) and for each neighbor vertex $(i-j)$ , $T_i$ stores a probability value $P_{i,j}$ expressing the goodness (desirability), under the current network routing policy, of choosing j as the next transmission range. Based on this, ants can explore better routing path. For each corona $C_i$ , the probabilities stored should be satisfied as follows:

$$\begin{array}{cc}& \sum _{j=\mathrm{1}}^k‍P_{i,j}=\mathrm{1},\hspace{1em}i\in \left[\mathrm{1},m\right].\end{array}$$

(10)

(3)

The per node traffic load of corona $C_i$ generated from each outer corona, denoted as $L_{i,j}$ , where i is the ID of corona $C_i$ and j is the ID of outer corona. The values are obtained through an initializing process: during the initial unit time, each corona generates data at the rate of l, then sends them, and forward the data generated by outer coronas to the sink with transmission range d, and each data packet records the ID of corona which generates it. Therefore, the nodes of corona $C_i$ can receive data generated from $C_{i+\mathrm{1}},C_{i+\mathrm{2}},\dots ,C_m$ and store the per node traffic load generated from these coronas, denoted as $L_{i,i+\mathrm{1}},L_{i,i+\mathrm{2}},\dots ,L_{i,m}$ . In ATSRL, if an ant $g_j$ arrives in corona head $H_i$ , and the coronas which $g_j$ has passed through can be a set $\text{pat}{\text{h}}_j=j_{\mathrm{1}},j_{\mathrm{2}},\dots ,j_n$ , obviously $j_n\le m-i$ . Therefore, the $ECR$ value of forwarding $g_j$ by the corona head $H_i$ with transmission range level u is

$$\begin{array}{lll}{W}_j\hfill & =\hfill & L[{\beta }_1+{\beta }_2{(x_{i}d)}^{\alpha }]\hfill \\ \hfill & \hfill & +\left(\sum _{j=1}^v\sum _{jy\in pat{h}_j}{L}_{i,jy}\right)\times [{\beta }_1+{\beta }_2{(ud)}^{\alpha }+{\beta }_3].\hfill \end{array}$$

(11)

Figure 7

The energy problem caused by corona model with a different width.

The ant-based algorithm is described as follows.

• (1)

At regular intervals of $\delta t$ from every corona head $H_i$ , a forward ant Fant is launched toward sink node. Forward ants carry the same data packets, so that they experience the same traffic loads.

(2)

While traveling toward their destination nodes, the ants keep memory of their paths and of the energy consumption found. The identifier of every visited node r and the energy consumption are pushed onto a memory stack $S_i(g)$ in each ant g.

(3)

At each node r, each traveling ant heading towards sink node selects from the neighbors it has not visited yet the node t to move to; otherwise, the node t will be selected from all the neighbors in case all of them had been previously visited. The neighbor t is selected with a probability (goodness) $P_{i,j}$ that is computed with pheromone ${\tau }_{i,j}$ of each transmission range. Here, a and b are the coefficients for determining the influence of τ and η. Because all ants travel from one sector with bigger ID to another with smaller ID, there will be no cycle in each path:

$$\begin{array}{cc}& P_{i,j}=\frac{{\tau }_{i,j}^a{\eta }_{i,j}^b}{{\sum }_{l=\mathrm{1}}^k\left({\tau }_{i,l}^a{\eta }_{i,j}^b\right)}.\end{array}$$

(12)

(4)

When sink node is reached, the ant $Fant$ generates a backward ant $Bant$ and transfers to it all of its memory and then dies.

(5)

The backward ant $Bant$ takes the same path as that of its corresponding forward ant, but in the opposite direction. When the backward ant arrived at node r along the path mentioned before, it will update its own pheromone. Backward ants do not carry any data packet; they use higher priority queues because their task is to quickly propagate to the routing tables the information accumulated by the forward ants computed in

$$\begin{array}{cc}& \delta \tau =\frac{\mathrm{1}}{{\sum }_{\left(i,\left(i-j\right)\right)\in \text{pat}{\text{h}}_g}{W}_{i,j}}.\end{array}$$

(13)

(6)

Arriving at a node r from a neighbor node f, the backward ant updates the pheromone of edge $(r,f)$ and the routing table $T_r$ :

$$\begin{array}{cc}& {\tau }_{r,\left(r-f\right)}⟵{\tau }_{r,\left(r-f\right)}+\delta \tau ,\hspace{1em}\left(r,f\right)\in \text{pat}{\text{h}}_g.\end{array}$$

(14) The routing table $T_r$ is changed by incrementing the probability ${\tau }_{i,j}$ (i.e., the pheromone of choosing neighbor f) and decrementing the other probabilities. The amount of the variation in the probabilities depends on a measure of goodness we associate with the energy consumption experienced by the forward ant and is given above.

(7)

After the optimizing time $t_{\mathrm{0}}$ , each corona head chooses the transmission range with the maximal probability in $T_i$ as the transmission range of the corona and then broadcasts it to all nodes in this corona.

5. Simulation Results

Based on the energy model described in Section 3, we simulate the ASTRL proposed in this paper with consideration of the two strategies of deploying nodes, namely, uniform and nonuniform node distributions. Here, we have to mention that it is the greed forwarding strategy that is adopted in simulations for data forwarding, which has been presented in Section 3.

5.1. Simulation Parameters

The initial energy of each node (denoted as ε) is $\mathrm{50}\hspace{0.17em}\text{J}$ . The sensor nodes maximum transmission distance (denoted as $t_x$ ) is $\mathrm{20}\hspace{0.17em}\text{m}$ ; $t_x$ is divided into k levels, and k is 4. Each sensor node generates and sends L bits of data per second, and L is set to be 4102 bits. The node density is $\mathrm{5}/{\text{m}}^{\mathrm{2}}$ . The parameter in the energy consumption formula (1) is set to be 4, and the setting of other parameters has been introduced in Section 3.2. In ASTRL, the optimizing time (denoted as $t_{\mathrm{0}}$ ) is 1000 s, and the time interval $\delta t$ is 0.1 s; the evaporation coefficient γ is $\mathrm{0.05}$ , and the parameters a and b are set to be $\mathrm{1}$ and $\mathrm{0.3}$ , respectively. For ease of reading, we have listed all parameters in Table 1.

Table 1

Simulation parameters.

Parameter	Value
Initial energy of each node $(\epsilon )$	50 J
Maximum transmission range $(t_x)$	20 m
Number of transmission range levels $(k)$	$\mathrm{4}$
Length of unit data (L/sec)	$\mathrm{4}\times \mathrm{1}{\mathrm{0}}^{-\mathrm{2}}$
Density $(\rho )$	$\mathrm{5}/{\text{m}}^{\mathrm{2}}$
α	$\mathrm{4}$
${\beta }_{\mathrm{1}}$	$45\times {10}^{-9}$  J/bit
${\beta }_{\mathrm{2}}$	${\mathrm{10}}^{\mathrm{15}}$  J/bit/m4
${\beta }_{\mathrm{3}}$	$\mathrm{135}\times {\mathrm{10}}^{\mathrm{9}}$  J/bit
$t_{\mathrm{0}}$	1000 sec
$\delta t$	0.1 sec
γ	$\mathrm{0.05}$
a	$\mathrm{1}$
b	$\mathrm{3}$

Our simulation includes three parts: (1) using an ant colony optimizing process as an example to show the variation in probabilities of using different transmission ranges during the whole process; (2) compare ASTRL with other algorithms under different situations, which include optimal algorithm and the algorithms proposed in other papers. Under any of the situations the results are an average over $\mathrm{100}$ independent runs or more; (3) discuss the influence of the parameter settings in ASTRL on its performance.

5.2. Variation in the Probabilities of Using Certain Transmission Range

With the parameters listed in Table 1, the simulations examine the variation in the probabilities of using certain transmission range of the specific coronas selected from all coronas ( $\mathrm{12}$ coronas) under circumstance of uniform node distribution. Figure 8 shows how the variation in the probabilities that each of the $\mathrm{4}$ coronas (i.e., $C_{\mathrm{4}},C_{\mathrm{7}},C_{\mathrm{10}},\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{and}\mathrm{\hspace{0.17em}\hspace{0.17em}}{C}_{\mathrm{12}}$ ) uses certain transmission ranges within 1000 s. As it shows, during the ant colony optimizing process, the farther the corona is from the sink, the more slowly its probabilities of transmission range converge; particularly, for the corona $C_{\mathrm{12}}$ , the variation amplitude of the probabilities is the greatest. This is because inner coronas (like $C_{\mathrm{4}}$ ), which are close to the sink, have fewer route options, and thus being able to determine their transmission range earlier than outer coronas via the study of network traffic. For outer coronas, since they have to adapt to the routing status of inner coronas, they are unable to determine their transmission ranges until inner coronas have finished the determination of their own transmission ranges.

Figure 8

Variation in the probabilities of using certain transmission range of specific coronas.

5.3. Comparison with Other Algorithms

In this section, we evaluate the performance of the algorithm we proposed in this paper through comparing it with other existing algorithms. In the simulation, we compare ASTRL with two other algorithms.

• (1)

Optimal list (OL), namely, the optimal transmission range list. Since it is obtained by enumerating all available transmission range lists and selecting from them the list with maximal lifetime, it must be the optimal transmission range list compared to other transmission range lists of the network.

(2)

$t_x$ , the algorithm proposed in [8]. According to this algorithm, which is only capable of dealing with uniform node distribution, all the nodes in coronas adopt the maximal transmission range. We simulate the three algorithms with uniform node distribution and get their respective average network lifetime. In this simulation, in consideration of the requirements of $t_x$ , the maximal transmission range of sensor nodes is set to be $\mathrm{5}\hspace{0.17em}\text{m}$ .

We experimentally compare the network lifetime with different network sizes (different coronas). As the results in Figure 9(a) show, in terms of the network lifetime, ASTRL is close to OL obtained by exhaustive search but significantly outperforms $t_x$ . Figure 9(b) shows the average residual energy ratios of different algorithms, and the average residual energy ratio refers to the ratio of the remaining energy available when the network lifetime ends to the total initial energy of the network. As Figure 9(b) indicates, the performance of ASTRL is close to OL in terms of the average residual energy ratio. Compared with $t_x$ , ASTRL has comparatively increased the energy efficiency so as to prolong the network lifetime.

Figure 9

Network lifetime and average residual energy ratios of different algorithms.

The simulation is performed with $\mathrm{100}$ different uniform node distributions, and for each of them we run ASTRL $\mathrm{100}$ times. Figure 10 shows the ratios of the average network lifetime of ASTRL to that of OL in the networks with different uniform node distributions. As Figure 10 indicates the experimental results of ASTRL are close to the optimal network lifetime in the networks with whether $\mathrm{8}$ or $\mathrm{10}$ coronas. In addition, since there is only a minor fluctuation in the experimental results of ASTRL, $\mathrm{85}\%$ of which are larger than $\mathrm{0.8}$ , we conclude that ASTRL can perform well in the networks with uniform random node distribution.

Figure 10

Network lifetime ratio with optimal solution in uniform random node distribution.

The simulations mentioned above are designed just for small-scale networks. This is because it is almost impossible to enumerate all potential transmission range lists in large-scale networks. For this reason, we have to compare ASTRL with $t_x$ in a large-scale network (more than $\mathrm{20}$ coronas). Figure 11 shows how the network lifetime and the average residual energy ratios of the two algorithms vary with the increase of the number of the coronas in the network. Similar to Figures 9 and 11 indicates that even in large-scale networks ASTRL drastically outperforms $t_x$ in terms of both network lifetime and average residual energy ratio.

Figure 11

Network lifetime and average residual energy ratios of different algorithms.

ASTRL will take some optimizing time to determine the transmission range of each corona, and therefore we have to analyze the influence of the optimizing time of ASTRL on the lifetime of the whole network, and that will be done from the following four aspects. (1) After the optimizing time, the transmission range of the sensor nodes in each corona will be fixed without any change henceforth. (However, if the sensor network suffers from high node fault ratio, ASTRL can run again for adapting to the topology changes of the network. In this case, sink node can play the role of a decision-maker to decide whether to perform the optimizing process again or not.) (2) As shown in Figures 9(a) and 11(a), the ratio of the optimizing time to the lifetime of the whole network is very low. (3) Since the energy consumption for transmitting the ants can be ignored (see Section 3.2), the energy consumed by ASTRL itself is insignificant, which has little influence on the network lifetime accordingly. (4) As Figures 9(a) and 11(a) show, compared with $t_x$ , ASTRL improves the network lifetime significantly at the cost of the energy consumption for the optimizing process. For this reason, we conclude that ASTRL outperforms $t_x$ .

The authors in [18] propose to use a strategy of nonuniform node distribution to achieve maximum energy efficiency. According to the strategy, from the corona $C_{R-\mathrm{1}}$ to the innermost corona $C_{\mathrm{1}}$ , the number of the sensor nodes increases in a geometric ratio of $q>\mathrm{1}$ , and in the corona $C_R$ there are $N_{R-\mathrm{1}}/(q-\mathrm{1})$ nodes. Besides the distribution strategy, they also propose a routing protocol called $q\text{-}Switch$ , in which all the sensor nodes use the maximum transmission range. It is proved in [18] that the nonuniform node distribution strategy used in co-ordination with the routing protocol $q\text{-}Switch$ will achieve the subbalanced energy depletion in the network and thus achieving the optimal network lifetime. Considering the decisive importance of the distribution strategy, we decide to evaluate the performance of ASTRL in large-scale networks with nonuniform node distribution by comparing it with $q\text{-}Switch$ .

Since the width of each corona in the corona model proposed in [18] is the maximum transmission range $t_x$ while ASTRL is run on a kind of corona model with transmission range levels, to ensure a fair comparison, we have to covert the nonuniform node distribution strategy [18] into a corona model with transmission range levels. The corona with the width of $t_x$ is divided into k subcoronas. From the outmost to the innermost every k subcoronas compose a group, in which each subcorona has the same number of nodes. The simulation parameters are as follows: $q=\mathrm{2}$ , and there are $\mathrm{20}$ nodes in each of the four outmost coronas. Take a network with $\mathrm{12}$ coronas as an example. In the network, there are $\mathrm{20}$ nodes in each of the four coronas (from $C_{\mathrm{8}}$ to $C_{\mathrm{5}}$ ) and $\mathrm{40}$ in each of the other four coronas (from $C_{\mathrm{4}}$ to $C_{\mathrm{1}}$ ). The simulation results are shown in Figure 12. From Figure 12, it can be seen that the performance of ASTRL approaches the optimal values of $q\text{-}Switch$ in terms of both network lifetime and average residual energy ratios. This indicates that ASTRL can adapt well to large-scale networks with nonuniform node distribution. Although $q\text{-}Switch$ performs better, it will be determined by the nonuniform node distribution strategy, which, however, pays too much for node deployment. In contrast, ASTRL, as shown in Figures 11 and 12, is independent of the node distribution strategy and performs equally well in large-scale networks.

Figure 12

Network lifetime and average residual energy ratios with nonuniform deterministic node distribution.

5.4. Effect of the Algorithm Parameters on the Performance

The simulation results in Figure 13 show the variation in the ratios of the average network lifetime of the ant colony algorithm with different evaporation coefficients to that of OL in the uniform node distribution. As Figure 13 shows, when the value of evaporation coefficient (denoted as γ) is $\mathrm{0.05}$ , the algorithm has the best performance; when $\gamma \mathrm{0.01}$ , the evaporation coefficient of the pheromone is so low and the ants find it hard to search for other different routes during the search process and hence the poor search performance; when $\gamma \mathrm{0.01}$ , the evaporation coefficient is so high that the pheromone is unable to be accumulated quickly and hence affecting this positive feedback mechanism.

Figure 13

Average network lifetime ratio with optimal list in uniform node distribution.

We conduct simulations to evaluate the performance of a network with $\mathrm{30}$ coronas in uniform node distribution in terms of the network lifetime. In the simulation the parameter of optimizing time $t_{\mathrm{0}}$ is set to be $\mathrm{102}\hspace{0.17em}\text{s}$ and $\mathrm{103}\hspace{0.17em}\text{s}$ , respectively, and for each of the parameter value we run the algorithm $\mathrm{100}$ times and use the average value of the results to evaluate the performance. As Figure 14 shows, the network lifetime is extended to some extent when $t_{\mathrm{0}}$ increases, but there is not a major fluctuation in the simulation results when $t_{\mathrm{0}}$ varies.

Figure 14

Network lifetime with different optimizing time.

The ant generation rate refers to the number of the ants generated by each node during every time interval $\delta t$ . Next we will discuss the relation between the ant generation rate and the convergence of ASTRL. We conduct simulations to examine how the minimum probability values in construction graph with different ant generation rates vary with the variation in the optimizing time in a network with $\mathrm{10}$ coronas. In the simulation, the ant generation rates are set to be $\mathrm{1},\hspace{0.17em}\hspace{0.17em}\mathrm{2},\hspace{0.17em}\hspace{0.17em}\mathrm{5},\hspace{0.17em}\hspace{0.17em}\text{and}\hspace{0.17em}\hspace{0.17em}\mathrm{10}$ ants, respectively, and each corona selects the maximum value of the probabilities of using different transmission ranges as its own maximum probability value; the smallest value of the maximum probability values of all the coronas is considered as the minimum probability value in construction graph. According to the simulation results in Figure 15, when the ant generation rate is $\mathrm{1}$ , the algorithm achieves the best convergence, that is, the minimum probability value can converge approximately at $\mathrm{1}$ within the shortest time. In addition, we have noticed that the higher the ant generation rate is, the more feedback there is from the ants within the same time period. This kind of reciprocal impact makes the convergence of the algorithm decreased.

Figure 15

The changes of minimal probability with different ants generating rates.

6. Conclusion

The energy hole problem is caused by uneven energy consumption. Because data transmission is achieved by forwarding scheme among coronas, the sensor nodes closest to the sink need to relay more traffic so as to deplete their energy budget faster than other sensors. Based on our analysis, the key factor of improving the network lifetime is that different transmission ranges should be adopted in different regions of the network. Therefore, in this paper, we start with finding the optimal transmission range list based on corona model and propose the ant-based distributed algorithm (ASTRL) which tends to prolong the network lifetime by assigning appropriate transmission range for each corona. The simulation results show our algorithm can significantly improve the network lifetime; actually, it is close to optimal list (OL) in terms of the network lifetime and can perform equally well in the nonuniform node distribution.