Network Structure-Aware Ant-Based Routing in Large-Scale Wireless Sensor Networks

Abstract

Routing algorithms for large-scale sensor networks should be capable of finding energy efficient paths to prolong the lifetime of the networks in a decentralized manner. With this respect, Ant System has several proper characteristics for routing algorithm in large-scale wireless sensor networks. First, its distributed mechanism enables routing algorithm to find a solution with only local information and be robust for uncertainties in wireless sensor networks. Second, the framework of the Ant System is proper to solve dynamic problems such as routing problem. Transition probability in Ant System can be used to estimate how good a given routing path is. Capturing these features, this work proposes two Ant Systems based routing algorithms, which are AS-RWSNs (Ant System for Routing in Wireless Sensor Networks) and SAAS-RWSN (Structure-Aware AS-RWSN). The AS-RWSN applies the original Ant System to routing algorithm for wireless sensor network and SAAS-RSN upgrades AS-RWSN with considering properties of network structure such as degree of node. In SAAS-RSN, sensors with high node degree have high data traffic since they have more routing paths. Consequently, SAAS-RSN achieves an energy balance over sensor network through this routing scheme. We demonstrate the effectiveness of the proposed algorithms by comparing three existing routing algorithms.

1. Introduction

Large-scale wireless sensor networks consist of a large number of sensors being deployed in a target area to report predetermined events or transmit sensed data to the base station for further analysis [1, 2]. In the large-scale wireless sensor networks (LWSN), routing problem becomes more important and tricky because a number of sensors are involved and the sensors are limited in power and calculation capacity. Therefore, routing algorithm for the large-scale wireless sensor networks should be capable of finding energy efficient paths and, at the same time, achieving an energy balance over the network to prolong the lifetime of sensor networks through a decentralized decision making scheme [1, 2]. Moreover, the following two issues should be considered to design routing algorithm for large-scale wireless sensor networks. First, the routing algorithm should give a good performance regardless of event generation pattern. In fact, events could be generated at the sensor, randomly [3], uniformly [4] over the target area, or repeatedly [5] at a specific part of the target area. Even, event patterns can change from one type to another over time. Therefore, the routing algorithm should be sufficiently robust for diverse event generation functions. Second, a network topology can be changed by energy depletion of sensors, introduction of new sensors, or change position of sensor. Therefore, the routing algorithm should be able to handle these uncertainties caused by diverse event generation functions and change of network topology. To achieve this purpose, this work considers Ant System (AS). The basic idea of the Ant System is a positive feedback mechanism in which following ants find better solutions by considering the results of preceding ants' decisions [6]. The AS is suitable for controlling large-scale dynamic systems like communication networks because of the following desirable features:

• (i)

In AS, ants find paths with only local information, the amount of pheromone on links. Therefore, AS is decentralized and can control large-scale systems having a number of entities without an exponential increase of computational effort due to its decentralized nature.

(ii)

The AS is robust for unexpected changes of environments. In telecommunication networks, AS adapts to traffic conditions with communications among ants and route data to less congested areas of the network. The AS has an adaptive mechanism to the changes of environments.

(iii)

In routing problems, the transition probabilities of the AS can be interpreted as availability of nodes. This availability reveals the probability that the framework of the AS can be used for solving dynamic routing problems. With this feature data traffic in WSNs can be dispersed to maximize the lifetime of networks.

With these characteristics, we utilize the Ant System to tackle the routing problem addressed in [7, 8]. Firstly, this work proposes an ant-based routing algorithm for wireless sensor networks, called AS-RWSNs (Ant System for Routing in Wireless Sensor Networks). The AS-RWSN advances the original AS by using data packets themselves as “ants” and redefining a link cost to consider the residual energy of the corresponding sensor. As the link cost, the energy cost in [8] devised to consider a balance of sensors' remaining energies as well as energy-efficiency can be used. Secondly, the AS-RWSN is upgraded by considering node heterogeneity. Generally, sensors of WSNs are heterogeneous in node degree (the number of neighboring nodes). The heterogeneity of sensors can be utilized to compute the goodness of the sensors and can be incorporated into the proposed routing algorithm, AS-RWSN, and improve the performance of the routing algorithm. Considering the goodness of nodes, a network structure-aware ant routing algorithm, SAAS-RWSNs (Structure-Aware Ant System for Routing in Wireless Sensor Networks), is proposed.

The remainder of this paper is organized as follows. Section 2 summarizes related works on Ant System and routing in wireless sensor networks and Section 3 introduces an ant-based routing algorithm, called AS-RWSN, for large-scale wireless sensor networks. After presenting the Structure-Aware Ant System for Routing in Sections 4 and 5 we provide extensive simulation results. Finally we conclude our work in Section 6.

2. Previous Works

2.1. Ant Systems

In 1992, Dorigo [9] devised the Ant System (AS) as a metaheuristic to solve the traveling salesman problem (TSP). The traveling salesman problem involves finding a closed path connecting n cities by minimal distances. If $d_{ij}$ is the Euclidean distance between cities i and j, then m ants are launched into network with different starting nodes to find solutions. Ants decide the next node based on a transition rule for selecting the next city. Ants' decisions for the next node also depend on the amount of pheromone, ${\tau }_{ij}(t)$ , on links. This pheromone amount for each link changes according to the performance of ants travelling through the link. The shorter the travel time of an ant is, the more the link is reinforced. With these considerations the transition probabilities from city i to city j for kth ant are defined as in

$$\begin{array}{cc}& p_{ij}^k\left(t\right)=\frac{{\left[{\tau }_{ij}\left(t\right)\right]}^{\alpha }·{\left[\mathrm{1}/d_{ij}\right]}^{\beta }}{{\sum }_{l\in J_i^k}{\left[{\tau }_{il}\left(t\right)\right]}^{\alpha }·{\left[\mathrm{1}/d_{ij}\right]}^{\beta }}\hspace{1em}\text{if\hspace{0.17em}\hspace{0.17em}}j\notin \text{tab}{\text{u}}_k,\hspace{0.17em}\hspace{0.17em}\mathrm{0}\text{\hspace{0.17em}\hspace{0.17em}otherwise},\end{array}$$

(1)

where α and β are tuning parameters and $J_i^k$ is the list of cities which ant k at city i can transit. Ant k calculates $J_i^k$ with its tabu list, $\text{tab}{\text{u}}_k$ , which is a list of cities already visited. The tabu list prevents ant k from visiting a city more than once. Notably, the value of the probability $p_{ij}^k(t)$ can be different for two ants on the same node i because these two ants probably have different tabu lists. After completing a tour, each ant reinforces each link $(i,j)$ included in the tour by adding an amount of pheromone $\Delta {\tau }_{ij}^k$ which depends on how well the ant has performed. At time t, ant k deposits ${\tau }_{ij}^k$ on the link $(i,j)$ as in

$$\begin{array}{cc}& {\Delta \tau }_{ij}^k=\left\{\begin{array}{cc}\frac{Q}{L^k},\hfill & \text{if ant\hspace{0.17em}\hspace{0.17em}}k\text{\hspace{0.17em}\hspace{0.17em}travels}\left(i,j\right)\text{between time\hspace{0.17em}\hspace{0.17em}}t\text{\hspace{0.17em}\hspace{0.17em}and\hspace{0.17em}\hspace{0.17em}}t+n,\hfill \\ \mathrm{0},\hfill & \text{otherwise,}\hfill \end{array}\right.\end{array}$$

(2)

where Q is a constant and $L^k$ is kth ant's tour length. While, since the amount of pheromone deposited depends heavily on the quality of solution, converging to a local optimal by reinforcing the current best solution too much is possible, therefore, incorporating a pheromone update mechanism that prevents the algorithm from converging to a not very good solution is necessary. A coefficient of evaporation, $\rho \mathrm{\hspace{0.17em}\hspace{0.17em}}(0\le \rho \le l)$ , is included in a pheromone update rule to avoid converging to local optimal solutions. Therefore, the pheromone update rule not only reinforces links by ant's performance but also weakens the links by pheromone evaporation. The following equation shows the pheromone update rule:

$$\begin{array}{cc}& {\tau }_{ij}\left(t+n\right)=\left(\mathrm{1}-\rho \right){\tau }_{ij}\left(t\right)+\Delta {\tau }_{ij},\hspace{1em}\text{where\hspace{0.17em}\hspace{0.17em}}\Delta {\tau }_{ij}={\displaystyle \sum }_{k=\mathrm{1}}^m\Delta {\tau }_{ij}^k.\end{array}$$

(3)

The initial amount of pheromone on links is a small positive constant, ${\tau }_0$ . Through this pheromone update rule AS improves solutions. This rule can be also called the global update rule. Besides the TSP, the AS has many applications such as the Quadratic Assignment Problem (QAP) [10], Job-shop Scheduling Problem (JSP) [11], Graphic Coloring Problem (GCP) [12], Vehicle Routing Problem (VRP) [13], and other NP-hard problems [14, 15].

Even though extensive research has considered the static optimization problems, relatively less effort has contributed to solutions of dynamic optimization problems such as the network routing problem. In fact, one favorable characteristic of the ant-based approach is adaptiveness to and robustness for changes of environment over time. Therefore, AS and ACS are suitable for dynamic optimization problems. Schoonderwoerd et al. [16] firstly tackled a dynamic problem, a routing problem in telecommunication networks, with AS. In this work, ants launch periodically from any node in the network at any time. With a given destination the ants travel over the network. Each node updates its routing table with information from the launched ants. Di Caro and Dorigo [17] proposed an ant-based adaptive routing algorithm, AntNet, to traffic conditions. Different from the Schoonderwoerd's work, the AntNet emphasizes the adaptability of routing algorithm for data traffic in its routing mechanism. The experimental results of this work show that AntNet performed better than NSFNET and NTTnet which are well-known, existing, routing algorithms. White et al. [18] proposed an ant-based algorithm for routing in circuit-switched networks. This routing scheme is built by Point-to-Point (PTP) request. For each pair of starting points and destinations, an ant launches at the starting point to look for the best path to the destination, given a cost function.

Zhang et al. [19] proposed an ant-based routing algorithm designated for wireless sensor networks. This work proposed the sensor-driven cost-aware ant routing, based on AntNet. In the routing algorithm, sensors are aware, from their neighbors, of the costs to arrive at the destination. Using this information, the transition probabilities at sensor i to one of neighboring nodes, j, are determined by

$$\begin{array}{cc}& p_{ij}=\frac{C_j}{{\sum }_{k\in N_i}{C}_k},\end{array}$$

(4)

where $p_{ij}$ is the transition probability for node j at node i, $N_i$ is the set of node i's neighboring nodes, and $C_j$ is a function of cost or distance from node j to the destination. Apparently, less cost leads to greater probability. Even though this feature enables finding energy efficient paths, the routing algorithm does not consider energy balance over the network. Some sensors in this algorithm are forced to deplete quickly.

In [20], energy sufficiency is a consideration in the calculation of transition probability, as shown in

$$\begin{array}{cc}& p_{ij}^k=\frac{{\tau }_{ij}^{\alpha }·{\eta }_{ij}^{\beta }}{{\sum }_{l\in N_i,l\notin M^k}{\tau }_{il}^{\alpha }·{\eta }_{il}^{\beta }},\end{array}$$

(5)

where ${\eta }_{ij}=E_j/{\sum }_{l\in N_i}{E}_l$ . ${\eta }_{ij}$ is a heuristic metric to consider energy sufficiency of node j only. $E_j$ and $M_k$ are the current energy of node j and a tabu list of ant k, respectively. Since a node having more energy has a greater probability, an energy balance of network is achieved by this ant routing algorithm. The proposed algorithm also utilizes the pheromone update rule to consider energy-efficiency of a given path. The pheromone update rule is exactly the same to (3) except $\Delta {\tau }_{ij}$ is the total number of visits by an ant. A limitation of this approach is to consider energy-efficiency and balance indirectly.

Lin et al. [21] proposed an ant colony optimization approach to find the maximum number of connected covers which satisfy sensing coverage and network connectivity at the same time with a given sensor network. The uniqueness of this work is that wireless sensor networks considered are heterogeneous. The heterogeneity of sensors can be utilized to upgrade routing algorithm for wireless sensor networks.

2.2. Routing in WSN

Many works have contributed to devise routing algorithms to prolong the lifetime of sensor networks. Hierarchical routing, which includes LEACH, PEGASIS, HEED, TEEN, and QDA (QoS-based data aggregation), forms clusters and elects a cluster-leader for each cluster responsible for sending all the data from its followers to the base station [22–26]. Through clustering and cluster-leader selection rules, these hierarchical approaches distribute energy usages over the network.

In LEACH (Low-Energy Adaptive Clustering Hierarchy) [23], sensors elect themselves to be a cluster-leader with a probability proportional to the amount of energy left. The cluster-leaders broadcast and each sensor determines to which cluster it wants to belong. Once all the nodes are organized into clusters, each cluster-head collects data from its members and sends data to the base station. TEEN (threshold sensitive energy efficient sensor network protocol) [25] is similar to LEACH but it allows the followers to send data only when sensed data indicate some events. In PEGASIS (Power-Efficient Gathering in Sensor Information Systems) [22], all sensors form a chain with minimal energy length and communicate with the base station through one leader sensor which is randomly selected in each round. HEED (Hybrid, Energy Efficient, Distributed clustering approach) [24] is similar to LEACH but it allows multihop routing through cluster-leaders. Different from other hierarchical algorithms, QDA [26] proposed a mathematical model considering two performance factors, which are sensor network lifetime and aggregation precision, at the same time. Since the mathematical model is genetic, it can be customized for any hierarchy routing algorithms. One drawback of the hierarchical routing algorithms is the necessity for high overheads involved in reforming clusters and cluster-leaders, which is essential to distribute the energy usages. Another drawback is that the number of hops to the base station is limited; that is, solution space is narrowed down. The number of hops is limited to two in LEACH, PEGASIS, and HEED and to the number of cluster-leaders in HEED.

Many approaches have been conducted to formulate maximum lifetime routing problems as linear or nonlinear programming (LP or NLP) problems and propose distributed algorithms designed to solve the LP or NLP problems [27–32].

Chang and Tassiulas [27] proposed a LP model to maximize the lifetime of wireless sensor networks and a heuristic algorithm, FA (Flow Augmentation) algorithm, to solve the LP problem in a decentralized manner. In FA, each sensor chooses a path that minimizes energy cost, by defining link cost as a combination of energy consumption of the link and energy residuals at the two end nodes. The main drawback of this algorithm is that every sensor must have detailed information of the entire network in order to solve the shortest path problem. In addition, the shortest path problem becomes more and more complex with the size of the network. Hua and Yum [30] considered a dual optimization routing problem, which optimizes data aggregation and routing simultaneously, to maximize network lifetime. They derived the necessary and sufficient conditions for obtaining the optimality of the optimization problem and designed a distributed gradient algorithm to find solutions which satisfy those conditions. However, this algorithm requires sensors to be aware of positions of their neighboring nodes and themselves. In addition, the routing model considered in this work reduces the solution space by making sensors consider only neighboring sensors close to the sink node. In [28, 29], nonlinear optimization formulations were introduced to maximize lifetimes of sensor networks and distributed routing algorithms were proposed to tackle the nonlinear problems. Even though these algorithms are capable of generating near optimal solutions, they require sensors for relatively high computational power and additional information to guarantee no-loop routing. Many other researches [31, 32] also have tackled maximum lifetime routing problems with mathematical models. Since sensors only consider downstream neighboring sensors (close to the base station) for routing, solution spaces for routing policies could be reduced and the quality of solutions degraded in terms of energy balance.

Rogers et al. [4] proposed a Self-Organized Routing algorithm, in which each sensor tries to maximize its own lifetime by hiring another sensor as a mediator. Since a mediator is allowed to hire its own mediator again, the number of hops is not limited in this algorithm. To make sensors willingly serve as mediators, they introduced a delicate payment scheme. Sensors earn different payments depending on whether they transmit their own data or mediate other sensors' data. If a sensor can get more payment, it is willing to be a mediator for other sensors. This algorithm has several desirable properties. Energy-efficiency and energy-balancing are pursued together through the selfish behaviors, sensors make local decisions based on local information, and there is no limitation to the solution space.

Ok et al. [7, 8] consider an energy balance in sensor networks to extend lifetime of sensor network. They devised a couple of metric, energy cost and energy welfare, to achieve energy balances of sensor networks in a decentralized manner. These approaches bring not only extension of lifetime but also some desirable property which is robustness for uncertainties of network topology and event generation pattern. In consideration of these advantages this work proposes a distributed routing algorithm based Ant System to achieve energy balance.

Some other approaches also have been proposed to extend lifetime of sensor networks. Rassam et al. developed a new adaptive and efficient dimension reduction model (APCADR) for hierarchical sensor networks to minimize the power consumption in radio communication [33]. Amiri et al. proposed a fuzzy ant colony optimization based routing algorithm which is designed to find an optimal path for a given source and destination [34]. They applied a fuzzy logic to ants' decision making scheme in ant colony optimization. Kiani et al. devised a machine learning based routing protocol for wireless sensor networks [35]. The routing protocol engages a reinforce learning technique which is a clustering method to avoid nonfunctioning sensors due to early power depletion.

3. Ant System for Routing in Wireless Sensor Networks (AS-RWSNs)

3.1. Sensor Network Model

To design and evaluate routing algorithm we consider a sensor network shown in [7, 8]. In the sensor network where n homogenous sensors (or nodes) are randomly and uniformly distributed over a target area, a base station receives sensed data from the sensors for further analysis. Each sensor has two wireless communication interfaces for its neighboring sensors and the base station. The one for neighboring nodes adopts a fixed transmission power which determines neighboring distance while the other for the base station can change its transmission power so that sensor can transmit data to the base station with the minimum power. For a given sensor the sensors within its neighboring distance are its neighboring sensors. This scheme enables each sensor to be aware of the current energy level of its neighbors or energy required to transmit from its neighboring sensors to the base station by eavesdropping for data from the neighbors [36]. This updating process guarantees that information of neighboring sensors for the routing decision is available for sensors [7, 36].

The energy consumption of wireless communication sensor occurs in sensing, receiving, and transmitting data. However, the amount of energy consumed for sensing is unaffected by routing algorithm and only a small difference exists between the energy consumptions of idle and receiving modes [4, 22, 27, 37–40]. Therefore, only the energy consumptions for transmission are generally considered in designing a routing algorithm. A sensor is capable of changing its transmission power to control its transmission distance [4, 22, 23, 39, 41–43]. Many previous works [4, 22, 23] used a simple deterministic energy consumption model in which the required energy $(E)$ is proportional to transmission distance $(d)$ and size of data. After normalizing radio characteristic constant and size of data, the energy consumption model is simplified to $E=d^2$ [4].

For evaluation purpose, we define lifetime of sensor network and event generation patterns. First, the definition of sensor network lifetime is the time until the first node or a portion of nodes becomes incapable, due to energy depletion, of sending data to its neighbors. The portion can vary depending on the context of the sensor networks. In this paper, the lifetime of a sensor network is the number of rounds until the first ( $L_1$ ), 10% ( $L_{10}$ ), and 20% ( $L_{20}$ ) node(s) become inactive. In the case of event generation, three patterns are considered as follows:

• (i)

Uniform event generation: every sensor has a data packet to be reported in any round [4, 22, 23, 44].

(ii)

Random event generation with random rate α: every sensor has a data packet to be reported with probability α in any round. The probability α is called random rate [5, 45].

(iii)

Repeated event generation from a local area A: only the sensors in a local area A have data packets to be reported in any round. The shape of the area can be a point, a circle, a square, or any other shape [3].

3.2. Ant System for Routing Problem in LWSN

Different from the AS for combinatorial optimization problems such as TSP, the one for routing problem in communication networks should be able to provide optimal routing policies for each node rather than find an optimal solution. In other words, the routing algorithm for communication networks should find routing policies for all nodes for routing a given data traffic. Ant System for Routing in Wireless Sensor Network (AS-RWSN) is devised to corporate this consideration. The AS-RWSN has several different characteristics from the existing Ant System.

First of all, in wired telecommunication networks, the current traffic of the only link determines the current availability of a link. However, in wireless sensor networks, the capacity of a given link mainly depends on the current energy of the corresponding sensor. Therefore, the proposed algorithm uses a composite measure, energy cost ( ${EC}_{ij}$ ), devised to consider energy sufficiency as well as energy-efficiency [8]. Energy cost from node i to j, ${EC}_{ij}$ , can be defined as in the following equation over time:

$$\begin{array}{cc}& {EC}_{ij}=\frac{e_{ij}}{E_i}+\frac{e_{j,\mathrm{B}\mathrm{S}}}{E_j},\hspace{1em}\text{where\hspace{0.17em}}\hspace{0.17em}{e}_{ii}=\mathrm{0},\hspace{0.17em}\hspace{0.17em}j\in N_i.\end{array}$$

(6)

$E_i$ and $e_{ij}$ represent the currently available energy of node i and the required energy for transmission from node i to j, respectively. Also, $e_{j,\mathrm{B}\mathrm{S}}$ is the required energy for transmission from node j to the base station. The energy cost for the path via node j ( ${EC}_{ij}$ ) is designed to be cheaper when node j has larger energy and the location of node j is closer to the base station. Using the energy cost, transition probability can be calculated by (7). The smaller energy costs lead to the larger transition probability and vice versa:

$$\begin{array}{cc}& p_{ij}^k\left(t\right)=\frac{{\left[{\tau }_{ij}\left(t\right)\right]}^{\alpha }·{\left[\mathrm{1}/{EC}_{ij}\right]}^{\beta }}{{\sum }_{l\in N_i^k}{\left[{\tau }_{il}\left(t\right)\right]}^{\alpha }·{\left[\mathrm{1}/{EC}_{ij}\right]}^{\beta }}\hspace{1em}\text{if\hspace{0.17em}\hspace{0.17em}}j\notin \text{tab}{\text{u}}_k,\mathrm{0}\text{\hspace{0.17em}\hspace{0.17em}otherwise}.\end{array}$$

(7)

According to the transition probability, each sensor routes the data packet to the base station. Once the data packet arrives at the base station, every edge involved in routing the data packet updates its pheromone concentration by

$$\begin{array}{cc}& {\tau }_{ij}\left(t\right)⟵{\left(\mathrm{1}-\rho \right)\tau }_{ij}\left(t\right)+\Delta {\tau }^k,\hspace{1em}\text{where}\left(i,j\right)\in {\text{Tour}}_k,\hspace{0.17em}\hspace{0.17em}\mathrm{0}\le \rho \le \mathrm{1}.\end{array}$$

(8)

ρ is the pheromone evaporation rate and enables the algorithm not to stick to bad solution by preventing unlimited accumulation of the pheromone trails. ${\text{Tour}}_k$ is a path travelled by ant k and $\Delta {\tau }^k$ is the total energy cost for the path passed by data packet k. $\Delta {\tau }^k$ is the amount of pheromone deposited by ant k that can be fixed or is proportional to the total cost of the forward path and, in this work, the total energy cost is set to $l_0/{\sum }_{(i,j)\in {\mathrm{t}\mathrm{o}\mathrm{u}\mathrm{r}}_k}C_{ij}$ . By (8) more pheromone is assigned to more efficient path in terms of energy cost. With this mechanism the precedent ant or data packet leads the following one to energy efficient path.

3.3. Explanatory Examples

Two examples are provided to clarify the mechanism of the AS-RWSN algorithm. In Figure 1, sensor 1 has a data packet k to be sent to the base station. Since it has two neighboring nodes, sensors 2 and 3, three possible paths, one direct path, and two indirect paths via sensors 2 and 3 are available. To route the data packet or choose one of the possible paths, sensor 1 calculates transition probabilities for available paths (Tables 1 and 2). With (6) and (7) ant k computes $E{C}_{1j}(t)$ and $p_{1j}^k$ . Using the transition probabilities in the routing table (the fourth column of Table 1), ant k chooses one of the three paths with probabilities 0.23, 0.31, and 0.46. Assuming that data packet k is sent to the base station through the direct path, after receiving data, the base station broadcasts the traveled path and the cost of tour to all sensors. The sensors related to the traveled path update the concentration of pheromone on the corresponding links by $\Delta \tau =1/{\sum }_{\left(i,j\right)\in {\mathrm{t}\mathrm{o}\mathrm{u}\mathrm{r}}_k}{EC}_{ij}$ (global update). The tour of ant k is $(1,\text{BS})$ , $\Delta \tau =1/20$ , and new ${\tau }_{1,\text{BS}}=1.05$ , while ${\tau }_{12}$ and ${\tau }_{13}$ do not change. Since sensor 1 transmits data packet k to the base station, $E{C}_{1j}(t)$ also changes from 100 to 80 and all $E{C}_{1j}(t)$ change as shown in Table 2. The new ${\tau }_{1i}$ and $E{C}_{1j}(t)$ allow calculation of new transition probabilities for links, as shown in the fourth column of Table 2. After node 1 routes data k to the base station, transition probabilities at node 1 for the base station, node 2, and node 3 become 0.2, 0.32, and 0.47, respectively. While the global update rule reinforces the path that an ant traveled according to the performance of the ant, the local update rule weakens the path by decrease of residual energies of transmitting sensors.

Table 1

Routing table of node 1 before routing the packet data k.

j	$${\tau }_{\mathrm{1}j}$$	$${EC}_{\mathrm{1}j}(t)$$	$$p_{\mathrm{1}j}^k$$
BS	1.0	$$\frac{\mathrm{20}}{\mathrm{100}}=\mathrm{0.2}$$	$\frac{\mathrm{1}/\mathrm{0.2}}{\mathrm{1}/\mathrm{0.2}+\mathrm{1}/\mathrm{0.15}+\mathrm{1}/\mathrm{0.1}}=\mathrm{0.23}$
2	1.0	$$\frac{\mathrm{5}}{\mathrm{100}}+\frac{\mathrm{10}}{\mathrm{100}}=\mathrm{0.15}$$	$\frac{\mathrm{1}/\mathrm{0.15}}{\mathrm{1}/\mathrm{0.2}+\mathrm{1}/\mathrm{0.15}+\mathrm{1}/\mathrm{0.1}}=\mathrm{0.31}$
3	1.0	$$\frac{\mathrm{5}}{\mathrm{100}}+\frac{\mathrm{5}}{\mathrm{100}}=\mathrm{0.1}$$	$\frac{\mathrm{1}/\mathrm{0.2}}{\mathrm{1}/\mathrm{0.2}+\mathrm{1}/\mathrm{0.15}+\mathrm{1}/\mathrm{0.1}}=\mathrm{0.46}$

Table 2

Routing table of node 1 after routing the data packet k.

j	$${\tau }_{\mathrm{1}j}$$	$${EC}_{\mathrm{1}j}(t)$$	$$p_{\mathrm{1}j}^k$$
BS	$$\mathrm{1}+\frac{\mathrm{1}}{\mathrm{20}}=\mathrm{1.05}$$	$$\frac{\mathrm{20}}{\mathrm{80}}=\mathrm{0.25}$$	$$\frac{\left(\mathrm{1.05}\right)\cdot \mathrm{1}/\mathrm{0.25}}{(\mathrm{1.05})\cdot \mathrm{1}/\mathrm{0.25}+\mathrm{1}/\mathrm{0.16}+\mathrm{1}/\mathrm{0.11}}=\mathrm{0.21}$$
2	1.0	$$\frac{\mathrm{5}}{\mathrm{80}}+\frac{\mathrm{10}}{\mathrm{100}}=\mathrm{0.16}$$	$$\frac{\mathrm{1}/\mathrm{0.16}}{(\mathrm{1.05})\cdot \mathrm{1}/\mathrm{0.25}+\mathrm{1}/\mathrm{0.16}+\mathrm{1}/\mathrm{0.11}}=\mathrm{0.32}$$
3	1.0	$$\frac{\mathrm{5}}{\mathrm{80}}+\frac{\mathrm{5}}{\mathrm{100}}=\mathrm{0.11}$$	$$\frac{\mathrm{1}/\mathrm{0.11}}{\left(\mathrm{1.05}\right)\cdot \mathrm{1}/\mathrm{0.25}+\mathrm{1}/\mathrm{0.16}+\mathrm{1}/\mathrm{0.11}}=\mathrm{0.47}$$

Figure 1

Transition probabilities (a) before routing data k and (b) after routing data k to the base station.

The second example concerns the tabu list. In AS, a launched ant keeps and updates its tabu lists for the nodes which it has visited. Using this list the ant can avoid visiting any node more than once. This scheme guarantees that ants can build paths to destinations, or the base station, without any loop. As shown in Figure 2, ant k's tabu list is empty when ant k is launched at node 1. After hopping to node 3, ant k does not consider node 1 as a hop to the next node because node 1 is included in ant k's tabu list. Similarly, as ant k moves from node 3 to node 2, the tabu list becomes $\{\mathrm{1,3}\}$ . Even though nodes 1 and 3 are neighboring nodes of node 2, ant k does not consider these nodes listed in the tabu list as a possible next hop.

Figure 2

An example: tabu list of ant k.

3.4. Algorithm Details

The design of the proposed routing algorithm, AS-RWSN, has the following considerations. First, using a transition rule, sensors can spread data traffic over the whole network to achieve an energy balance and consequently maximize the lifetime of sensor networks. The transition rule advances one of the original AS by redefining link cost. Second, through a pheromone update rule, the transition probability to the nodes, included with good solution paths, will increase as the proposed routing algorithm runs. Lastly, since network parameters continuously change with time, a good path is not always good and it is not necessary to find a good path for each sensor in a setup period by using dummy ants. Therefore, AS-RWSN can skip the initial path finding process by considering each data packet as a data ant. Each data packet changes environment parameters for the next data packet when it is routed as dummy ants in Ant Systems.

Assuming that each data is an ant, every ant should go to the base station, and ants arriving at the base station are terminated. A data ant k hops from one node to another node or the base station until it arrives at the base station; simultaneously it records visited nodes in its tabu list. The data ant k selects the next node to hop to according to the probability $p_{ij}^k$ in (7) and updates the energy costs in the routing table of the current node by (6). If the data ant k selects a node as the next node, the transition probability for the node deceases by this local update rule. Notably, the energy balance for a network can be achieved by this feature of the algorithm. Once data ant k has reached the base station, the base station directs sensors to update the pheromone of every edge $(i,j)$ which the ant traversed with (8). In fact, the more efficient a path is, the more a pheromone is deposited on the path by the global update rule. Therefore, $\Delta {\tau }^k$ in (8) should be proportional to the inverse of the energy cost used for routing data k. For example, $\mathrm{1}/{\sum }_{(i,j)\in \text{PATH}}{EC}_{ij}^k(t)$ can be used as $\Delta {\tau }^k$ .

Each sensor keeps a small routing table. This routing table contains node identification number, energy cost to the base station, the amount of pheromone, and transition probability for each neighboring node or the corresponding link. The steps of the algorithm are the following:

• (1)

Initialization of the routing table: during the initial setup period, each sensor finds its direct distance to the base station and calculates its energy cost ( $EC$ ) defined previously. Then, each sensor broadcasts a setup message to its neighbors with a preset transmission power for the neighboring distance. This setup message includes identification number and EC of the transmitting sensor itself. Every sensor receiving this setup message registers the transmitting sensor as one of its neighbors. The corresponding pheromone is set to 1.0 and transition probability is calculated by (7). Since all sensors have an identical neighbor distance, every sensor will receive the setup messages from all of its neighbors. After the setup period, all sensors initialize their routing tables.

(2)

Local update: the routing table reflects changes of neighbors' energy levels. When a sensor transmits a data packet, all of its neighbors receive the packet and the current energy cost of the transmitting sensor. As a result, whenever a sensor's battery level changes, all routing tables of its neighboring nodes are updated. The fields of EC and transition probability for the corresponding sensor are updated by (6) and (7).

(3)

Global update: once the base station receives an ant or a data packet, the base station broadcasts the information gathered by the ant to the visited nodes to update the pheromone concentration. Based on (8), the visited node updates the pheromone deposit of the corresponding link.

As explained earlier, AS-RWSN guarantees elimination of loops in any routing path. Since each data ant has a tabu list of visited nodes, the ant never visits any node more than once. Therefore, AS-RWSN always assures finding a routing path to the base station without loops. Algorithm 1 provides a high-level description of the routing decisions of AS-RWSN.

Algorithm 1: High-level description of AS-RWSN.

Let   $N(t)$ be the set of nodes having data at time t

Let LT be the lifetime of network and   $L_i$ corresponding threshold

For   $t=1$ to $t_{\max }$   do

  For   $k=1$ to n  do

    If   $k\in N(t)$   then

    Launch ${\text{ant}}^k(t)$ at node k

    Repeat

    Let  i be the current node

    IF   $E_i\le {TEB}_i$   then

      $nDead\leftarrow nDead+1$

     If   $nDead\ge L_i$   then

       $\text{LT}=t$

     End If

    Else

     Choose the next node j, $j\in N_i+\left\{\right.\text{BS}\left.\right\}$ with probability: Equation (7)

    End If

    After each transition ${\text{ant}}^k(t)$ applies the local update rule: Equation (6)

    Until   ${\text{ant}}^k(t)$ arrives at the BS

    Compute the length $L^k(t)$ of the tour $T^k(t)$ produced by ${\text{ant}}^k(t)$

    For every edge $(i;j)\in T^k(t)$   do

      Update pheromone trails by applying the rule: Equation (8)

    End For

    End If

  End For

End For

Print lifetime of network (LT)

Stop

4. Structure-Aware Ant Colony System for Routing in Sensor Networks (SAAS-RWSNs)

The AS-RWSN proposed in the earlier section can be improved by considering node heterogeneity. The AS-RWSN assumes that all nodes in networks are homogenous. However, many large-scale networks found in communications, biology, or sociology have heterogeneity among various properties. For example, complex networks were found to exhibit a scale-free degree distribution. Complex network theory provides various methods for characterizing the heterogeneity. When the goodness of nodes is identified by such methods, the routing algorithms can be designed more effectively based on the utilization of a network's structural properties. Proposing a structure-aware ant colony routing, called Structure-Aware Ant System for Routing in Wireless Sensor Networks (SAAS-RWSNs), this algorithm captures the advantage. In fact, the SAAS-RWSN advances AS-RWSN by considering a property of network structure such as degree of node. The basic idea of SAAS-RWSN is that routing data traffic to node having more links leads to energy balance. If a node has many neighboring nodes, then it has many alternative paths and a high chance to disperse data traffic. In the SAAS-RWSN algorithm, a greater number of links induce greater transition probability. In Figure 3, sensor i has three neighboring nodes, A, B, and C. The number of links of nodes A, B, and C is 5, 3, and 2, respectively. When sensor i routes a data packet, it assigns higher probability to the higher link degree node, for instance, node A. Assigning a higher transition probability to node A than node C leads to a distribution of data traffic over the whole network.

Figure 3

An example: the basic idea of SAAS-RWSN.

4.1. Node Goodness

Incorporating a property of network structure into AS-RWSN requires a metric to evaluate node goodness. In many applications, nodes are highly heterogeneous in their degree (i.e., the number of edges per node) [46, 47]. Clustering coefficients, quantifying local transitivity, are also heterogeneous [48, 49]. However, recently, many studies have attempted to analyze and characterize the heterogeneity of weighted complex networks. As a result, node degree, the number of neighboring nodes or links, can adequately capture the heterogeneity of nodes with relatively less computational effort. If the goodness of node i at time t is ${\gamma }_i(t)$ , then the scale of node goodness is ${\gamma }_{\min }\le {\gamma }_i\le {\gamma }_{\max }$ based on $\alpha /\beta$ used in diverse algorithms. The bounds can be a function of network structure such as numbers of nodes and/or links. The following equation can be a possible function to measure node goodness:

$$\begin{array}{cc}& {\gamma }_i\left(t\right)⟵{\gamma }_i+\left({\gamma }_{\max }-{\gamma }_{\min }\right)\frac{d_i\left(t\right)}{{\max }_i\hspace{0.17em}{d}_i\left(t\right)},\end{array}$$

(9)

where $d_i$ denotes the degree of node i. In wireless sensor networks, the number of neighboring nodes can vary due to energy depletion or change of position. Therefore, $d_i\left(t\right)$ and ${\gamma }_i(t)$ can also vary with time, while, in the case of static networks, $d_i\left(t\right)$ and ${\gamma }_i(t)$ are replaced by $d_i$ and ${\gamma }_i$ .

Powering the link goodness, $C_{ij}(t)$ by the node goodness ${\gamma }_i(t)$ allows applying node goodness, ${\gamma }_i(t)$ , to the calculation of transition probability. Note that α and β can be reduced to one parameter, ${\gamma }_i$ , representing the relative influence, and the node goodness can be static or dynamic depending on its nature. This definition of probability function directly incorporates the heterogeneity of the network and eliminates the tuning process. The following equation determines transition probability in SAAS-RWSN:

$$\begin{array}{cc}& p_{ij}^k\left(t\right)=\frac{\left[{\tau }_{ij}\left(t\right)\right]·{\left[\mathrm{1}/{EC}_{ij}\right]}^{{\gamma }_j\left(t\right)}}{{\sum }_{l{\in N}_i^k}\left[{\tau }_{il}\left(t\right)\right]·{\left[\mathrm{1}/{EC}_{il}\right]}^{{\gamma }_j\left(t\right)}},\hspace{1em}\text{if\hspace{0.17em}\hspace{0.17em}}j\notin \text{tab}{\text{u}}_k,\mathrm{0}\text{\hspace{0.17em}\hspace{0.17em}otherwise}.\end{array}$$

(10)

4.2. An Example

This section provides an example to clarify the mechanism of the SAAS-RWSN algorithm. In Figure 4, sensor 1 has a data packet to be sent to the base station. It has two neighboring nodes, sensors 2 and 3, which have 4 and 2 node degrees, respectively. If $E_i$ and ${\tau }_i\forall i$ are 100 and 1.0, then, as shown in the second and third columns of Table 3, $E{C}_{ij}$ and ${\gamma }_i(t)$ are determined by (6) and (9) where ${\gamma }_{\mathrm{m}\mathrm{a}\mathrm{x}}$ and ${\gamma }_{\mathrm{m}\mathrm{i}\mathrm{n}}$ are 2.0 and 1.5, respectively. With (10) the transition probabilities in the routing table (Table 3) can be calculated and ant k chooses one of the three paths with probabilities 0.19, 0.5, and 0.31. Even though nodes 2 and 3 have the same energy cost, sensor 2 has a higher probability since it has a higher node degree. After routing ant k, sensor i conducts the global and local updating processes. The global and local updating rules are the same as the ones in AS-RWSN. In addition, if node degree of any neighboring node changes, sensor i updates the node degree of the corresponding node in its routing table. Sensors under the SAAS-RWSN follow this procedure to route their data.

Table 3

Routing table of node 1 for data packet k.

j	$${EC}_{\mathrm{1}j}(t)$$	$${\tau }_{\mathrm{1}j}$$	$$p_{\mathrm{1}j}^k$$
BS	$$\frac{\mathrm{20}}{\mathrm{100}}=\mathrm{0.2}$$	$$\mathrm{1.5}+\mathrm{0.5}\times \frac{\mathrm{2}}{\mathrm{4}}=\mathrm{1.75}$$	$$\frac{{\mathrm{5}}^{\mathrm{1.75}}}{{\mathrm{5}}^{\mathrm{1.75}}+{\mathrm{6.7}}^{\mathrm{2}}+{\mathrm{6.7}}^{\mathrm{1.75}}}=\mathrm{0.19}$$
2	$$\frac{\mathrm{5}}{\mathrm{100}}+\frac{\mathrm{10}}{\mathrm{100}}=\mathrm{0.15}$$	$$\mathrm{1.5}+\mathrm{0.5}\times \frac{\mathrm{4}}{\mathrm{4}}=\mathrm{2.0}$$	$$\frac{{\mathrm{6.7}}^{\mathrm{2}}}{{\mathrm{5}}^{\mathrm{1.75}}+{\mathrm{6.7}}^{\mathrm{2}}+{\mathrm{6.7}}^{\mathrm{1.75}}}=\mathrm{0.5}$$
3	$$\frac{\mathrm{5}}{\mathrm{100}}+\frac{\mathrm{10}}{\mathrm{100}}=\mathrm{0.15}$$	$$\mathrm{1.5}+\mathrm{0.5}\times \frac{\mathrm{2}}{\mathrm{4}}=\mathrm{1.75}$$	$$\frac{{\mathrm{6.7}}^{\mathrm{1.75}}}{{\mathrm{5}}^{\mathrm{1.75}}+{\mathrm{6.7}}^{\mathrm{2}}+{\mathrm{6.7}}^{\mathrm{1.75}}}=\mathrm{0.31}$$

Figure 4

An example: SAAS-RWSN.

4.3. Algorithm Details

SAAS-RWSN has the same routing framework as AS-RWSN, except for considering the degree of nodes when a node calculates the transition probability for neighboring nodes. Similar to AS-RWSN, sensors in SAAS-RWSN keep a routing table. This table contains node degree as well as all information which routing table in AS-RWSN has (node identification number, energy cost to the base station, the amount of pheromone, transition probability, and node degree for each neighboring node). Similar to AS-RWSN, SAAS-RWSN also guarantees elimination of loops in any routing path with a tabu list. Algorithm 2 provides a high-level description of the routing decisions of SAAS-RWSN.

Algorithm 2: High-level description of SAAS-RWSN.

Let   $N(t)$ be the set of nodes having data at time t

Let LT be the lifetime of network and and ${nDead}_0$ corresponding threshold

For   $k=1$ to n  do

  Calculate ${\gamma }_k(t)$ by (8)

End For

For   $t=1$ to $t_{\max }$   do

  For   $k=1$ to n  do

    If   $k\in N(t)$   then

    Launch ${\text{ant}}^k(t)$ at node k

    Repeat

    Let  i be the current node

    IF   $E_i\le {TEB}_i$   then

      $nDead\leftarrow nDead+1$

     If   $nDead\ge L_0$   then

       $\text{LT}=t$

     End If

    Else

     Choose the next node j, $j\in N_i+\left\{\right.\text{BS}\left.\right\}$ with probability: Equation (10)

    End If

    After each transition ${\text{ant}}^k(t)$ applies the local update rule: Equations (6) and (7)

    Until   ${\text{ant}}^k(t)$ arrives at BS

    Compute the length $L^k(t)$ of the tour $T^k(t)$ produced by ${\text{ant}}^k(t)$

    For every edge $\left(i;j\right)\in T^k(t)$   do

      Update pheromone trails by applying the rule: Equation (8)

    End For

    End If

  End For

End For

Print Lifetime of network (LT)

Stop

5. Experimental Results

This section presents several experimental results to validate the effectiveness of AS-RWSN, SAAS-RWSN, and distributed AS-RWSN, which has exactly the same frame as AS-RWSN except for the global updating rule. In the distributed AS-RWSN, nodes calculate transition probability only based on local information obtained from neighboring nodes. Distributed AS-RWSN has no pheromone update after completing tours of data ants. This section also compares the distributed AS-RWSN with AS-RWSN and SAAS-RWSN to show the effect of the global update.

The comparison of the proposed algorithms is with three other algorithms: Direct Communication (Direct), Minimum Transmission Energy (MTE), and Self-Organized Routing (SOR). In Direct, every sensor simply transmits data directly to the base station without any consideration of energy-efficiency. In contrast, MTE considers energy-efficiency by choosing a path with minimum total energy consumption but it does not take into account energy-balancing. SOR pursues energy-efficiency as well as energy-balancing together and has several desirable properties as discussed earlier.

The experiments use a sensor network in which 100 nodes have random and uniform deployment in $100\hspace{0.17em}\mathrm{m}\times 100\hspace{0.17em}\mathrm{m}$ square area with the base station located at (50, 150) as shown in Figure 5. Sensors are initially endowed 250,000 energy units. The initial energy endowments are established such that the farthest node from the base station is capable of transmitting data 100 times under Direct. To demonstrate the effects of different event generation patterns, performed simulations use uniform, random, and repeated event generation patterns we have defined. In case of random generation, the random rate α is set to 0.25, which means that the probability that each sensor has an event in a round is 0.25, while, for the repeated event generation, sensors located in a square area from (0, 0) to (50, 50) incur repeated events.

Figure 5

The configuration of experimental sensor network: 100 nodes randomly and uniformly deployed in $100\hspace{0.17em}\mathrm{m}\times 100\hspace{0.17em}\mathrm{m}$ square area with the base station located at (50, 150).

The empirical analysis consists of three parts; Section 5.1 evaluates the lifetime driven by Direct, MTE, SOR, and three AS-RWSNs discussed in this section. Section 5.2 discusses in routing algorithms how well AS-RWSN achieves an energy well-balanced network with comparison to three existing routing algorithms. Section 5.3 discusses the performances of three ant-based routing algorithms. Because a sensor network is generated randomly, 100 experiments are repeated for each condition and an average of the results is taken.

5.1. Lifetime

This experimentation evaluates the performance of the AS-RWSN and SAAS-RWSN algorithms with 20 m neighboring distance of the square sensor network. Figure 6(a) plots the number of active sensors against time (i.e., number of rounds) for a uniform event generation pattern with routing algorithms mentioned. This graph indicates that AS-RWSN and SAAS-RWSN outperform Direct, MTE, and SOR until approximately 65% of sensors become inactive. Sensors in Direct, MTE, and SOR algorithms depleted their energies gradually over time. However, in the proposed algorithms, the majority of sensors are alive up to approximately time 200 and deplete simultaneously right after, thus indicating good energy-balancing throughout the network. Similar observations appear even for random and repeated event generation patterns, as shown in Figures 6(b) and 6(c), respectively. Particularly, the performances of AS-RWSN and SAAS-RWSN in the repeated event function are dominantly better than others in all different definitions of lifetime. With these findings, the conclusion is that the new algorithm is superior to other routing algorithms regardless of event generation patterns and therefore robust. Also noticeable is the fact that the result from SAAS-RWSN is better than one from AS-RWSN. Considering network structure routing algorithms can prolong the lifetime of sensor networks. Table 4 summarizes $L_1$ , $L_{10}$ , and $L_{20}$ of Direct, MTE, SOR, AS-RWSN, and SAAS-RWSN with uniform, random, and repeated event generation functions. For the SAAS-RWSN algorithm ${\gamma }_{\mathrm{m}\mathrm{i}\mathrm{n}}$ and ${\gamma }_{\mathrm{m}\mathrm{a}\mathrm{x}}$ are set to 1.5 and 2.0.

Table 4

Lifetime ( $L_1$ , $L_{\mathrm{10}}$ , and $L_{\mathrm{20}}$ ) with Direct, MTE, SOR, AS-RWSN, and SAAS-RWSN.

	Uniform			Random			Repeated
	$$L_1$$	$$L_{\mathrm{10}}$$	$$L_{\mathrm{20}}$$	$$L_1$$	$$L_{\mathrm{10}}$$	$$L_{\mathrm{20}}$$	$$L_1$$	$$L_{\mathrm{10}}$$	$$L_{\mathrm{20}}$$
Direct	105.24	122.72	141.75	394.81	492.63	567.95	107.67	143.51	190.14
MTE	12.13	77.58	125.91	50.09	311.17	504.75	37.43	269.35	416.05
SOR	29.81	110.24	151.42	121.2	442.57	607.28	110.91	305.99	405.91
AS-RWSN	182.97	209.48	216.98	733.41	839.29	868.86	281.86	436.94	650.89
SAAS-RWSN	212.02	225.31	228.68	847.07	903.05	917.08	443.72	689.91	885.81
Optimal	282.2	282.2	282.2	1128.81	1128.81	1128.81	1115.43	1115.43	1115.43

Figure 6

The number of active sensors over time under (a) uniform, (b) random, and (c) repeated event generation patterns.

5.2. Energy-Balancing

Figure 7 shows how well SAAS-RWSN achieves energy-balancing over the network. As shown in Figure 7(a) for Direct, Figure 7(b) for MTE, and Figure 7(c) for SOR, sensors far away or close to the base station become inactive at around 150th round. However, as shown in Figure 7(d), all the sensors under SAAS-RWSN remain alive. This desirable behavior results from the fact that SAAS-RWSN is efficiently utilizing the distributed energy resources in a balanced way.

Figure 7

The energy population at 150th round under uniform event generation pattern: (a) Direct, (b) MTE, (c) SOR, and (d) SAAS-RWSN.

Figure 8 shows the routing paths for the four algorithms under repeated event generation pattern in the square region from (0, 0) to (50, 50). While using Direct, MTE, and SOR, data traffic concentrates on the left half of the target area. On the other hand, since SAAS-RWSN tries to maximize equality, the traffic is dispersed over the whole network leading to superior energy-balancing. As a result, SAAS-RWSN keeps more sensors operating over time as shown in Figure 6(c).

Figure 8

Routing paths by (a) Direct, (b) MTE, (c) SOR, and (d) SAAS-RWSN, under repeated event generation pattern in the square region from (0, 0) to (50, 50).

5.3. Comparisons of Lifetime of AS-RWSNs

This section evaluates the effect of global update by comparing AS-RWSN and SAAS-RWSN with a distributed AS-RWSN. Figure 9 shows the network lifetimes of AS-RWSN, SAAS-RWSN, and distributed AS-RWSN. As shown in Figure 9(a), the result from distributed AS-RWSN is similar to those of AS-RWSN and SAAS-RWSN. Even though some performance deterioration exists (Figure 9(b)), distributed AS-RWSN also pursues energy balance and extends the lifetime of sensor networks. In fact, the difference between AS-RWSN and distributed AS-RWSN indicates the effect of global update. Inevitably, no global update leads to a sacrifice of solution quality. However, distributed AS-RWSN is more suitable for wireless sensor networks which are large-scale and highly dynamic systems.

Figure 9

Lifetime of AS-RWSN, SAAS-RWSN, and Distributed AS-RWSN.

6. Conclusions and Future Work

Sensor networks are dynamic and large-scale systems. A distributed control mechanism is necessary for managing such systems. An Ant System algorithm provides such a distributed and robust control framework. This paper, based on ant colony system, proposes two ant-based routing algorithms: AS-RWSNs (Ant System for Routing in Sensor Networks) and SAAS-RWSNs (Structure-Aware Ant System for Routing in Sensor Networks). AS-RWSN modified the original Ant System to be applied to sensor network applications by introducing a new link cost, energy cost. SAAS-RWSN advanced AS-RWSN by considering heterogeneity of networks in routing. These two proposed routing algorithms outperform existing routing algorithms in wireless sensor networks. The convergence trait of Ant System improves the system performance and, at the same time, its randomness features lead to a balance of the whole network in terms of traffic and energy. Numerical experiments show that ant-based routing algorithms perform well in wireless sensor networks.

This work only proposed node degree as a metric to identify heterogeneity of networks. However, many other metrics such as the clustering coefficient and local betweenness centrality [50] are available in complex network theory. Future work will integrate this study's ant-based routing algorithm with these other metrics for characterizing the heterogeneity of sensor networks.