Sage Journals: Discover world-class research

Abstract

We propose an energy-aware dynamic routing strategy in order to provide balanced energy consumption in wireless sensor networks, hence, prolonging the lifetime of the network. The proposed routing algorithm uses local betweenness centrality to estimate the energy consumption of the neighboring nodes around a given local sensor node, without requiring global information about the network topology or energy consumption, and to divert traffic from nodes that are more heavily used. Because nodes with large local betweenness centrality consume energy more quickly, the network lifetime can be prolonged by redistributing energy consumption to nodes with smaller local betweenness centrality. Simulation results showed that the proposed routing strategy has advantages over shortest path routing with respect to extending network lifetime and balancing energy consumption in wireless sensor networks, yet does not introduce significant additional transmission overhead or a longer average path length.

1. Introduction

Wireless sensor networks (WSNs) have many desirable characteristics, including easy deployment and self-organization, and are becoming increasingly important in modern society. The applications of WSNs range from important societal issues such as environmental surveillance, intelligent transportation, disaster relief, and health care to military issues including battlefield biological and nuclear monitoring as well as target tracking [1]. WSNs generally consist of a large number of small, embedded, low-power sensor nodes with sensing, data processing, and wireless communication capabilities [1]. They are deployed in a wide distribution area and collaborate to form an ad hoc network. The sensor nodes are battery-operated, most of which are not rechargeable, and cease to function once the battery expires. Owing to logistical issues such as remoteness or inaccessibility of distribution areas, it is not straightforward to replace sensor nodes with expired batteries. Therefore, balancing the energy consumption of WSNs to prolong the network lifetime is of considerable importance. In WSNs, the energy is consumed in different ways in different nodes; however, the primary energy cost is in data transmission once the networks have been organized.

Experimental measurements have shown that data transmission is generally very expensive in terms of energy consumption, while data processing consumes significantly less energy [2]. Data transmission depends on the routing strategy; therefore, designing a reasonable routing strategy to balance energy consumption has significant potential to prolong the lifetime of WSNs [3].

Along with the discovery of scale-free [4] properties, complex networks have been applied to a wide range of natural and social systems, such as the Internet, social networks, scientific collaboration networks, metabolic networks, and WSNs [5, 6]. Recently, routing in complex networks has attracted considerable interest across many fields of science. Research on routing strategies has overwhelmingly focused on improving transport capacity and controlling congestion, which are crucial problems on many large-scale networks such as the Internet, phone networks, and airport networks [7–14]. WSNs have a low data rate and low energy consumption [6, 15], and so the critical problem in WSNs is the longevity of the network, and the major constraint is energy consumption rather than congestion control.

Much work has been done developing WSN routing (e.g., see [16–27] for extensive reviews). Most existing energy-aware routing algorithms assume that the communication load is evenly distributed; however, this assumption is not consistent with the data usage requirements of individual nodes within many WSNs. Almost no studies have considered energy-aware routing in WSNs from the point of view of the structure and dynamics of large complex networks.

In this paper, we propose an energy-aware routing in WSNs using local betweenness centrality (EAR-LBC). The proposed routing algorithm has two features that differ from those of most current research (1)

It utilizes the basic principles of complex network theory, in particular the concept of betweenness centrality (BC) to estimate the remaining energy of the sensor nodes. Routing in WSNs takes place according to the criterion of the shortest available path from a given source to its destination. The nodes with the largest BC, which are usually called the central nodes of networks and are located in the shortest path, are susceptible to more frequent data transmission due to heavier traffic load [3]. Energy consumption at these central nodes occurs at a greater rate than that of other sensor nodes, leading to unbalanced energy consumption in the network. Once the central node runs out of energy, the WSN will cease to function. Consequently, we propose the EAR-LBC algorithm, which uses local BC (defined in Section 3) to consider the energy cost of forwarding data, and takes both the shortest path and the remaining energy of the sensor node into account, rather than simply employing traditional metrics such as the shortest path.

(2)

A systematic approach is taken to verify the validity of the EAR-LBC algorithm. Because most network topological structures (including WSN) exhibit scale-free behavior, we designed a simulation model based on Barabasi-Albert (BA) scale-free networks (discussed in Section 4.1). This simulation model is consistent with most WSN topological structures. For definiteness and without loss of generality, we investigated the performance of the EAR-LBC algorithm using three simulation scenarios generated by the model.

The remainder of this paper is organized as follows. Section 2 presents a review of relevant prior work. The proposed routing strategy is described in Section 3. Section 4 discusses the simulation results. Finally, the paper is concluded in Section 5.

2. Related Works

Applying complex network theory to the design of energy-aware routing in WSNs is an interdisciplinary field, which combines WSNs with complex networks. Accordingly, in this sections we describe related research progress in two ways: energy-aware routing in WSNs and routing in scale-free networks.

2.1. Energy-Aware Routing in WSNs

Many energy-aware routing algorithms for WSNs have been presented in recent years. Those routing algorithms can be categorized into two types. One type is the clustering routing algorithms that divide sensor nodes into clusters and balance the energy consumption by cluster head selection to extend network lifetime [19, 23, 24, 26, 27]. Cluster-based routing is an efficient way to reduce energy consumption and extend network lifetime within a cluster. The number of messages transmitted to the base station is reduced by data aggregation and fusion, which reduces the overall energy consumption. Cluster-based routing is mainly implemented as a two-layer strategy: one layer is used to select cluster heads, and the other layer is used for routing. High-energy nodes can be used to process and send information, whereas low-energy nodes can be used to perform sensing in close proximity to the target. The clustering algorithm is based on cluster selecting, which incurs an additional energy cost. The other type is centralized routing, which uses probabilistic forwarding [18] or an optimization strategy, such as ant colony optimization, linear programming, or heuristic approaches, to find an energy-balanced route based on the global information on the network topology and energy consumption [16, 17, 20–22, 25].

However, most existing energy-aware routing algorithms assume that energy consumption in WSNs is evenly distributed or that a WSN is deployed as a specific scenario when analyzing the validity of its routing algorithms, which is not consistent with most WSN topological structures. Almost all studies have failed to consider energy-aware routing from the point of view of the structure and dynamics of large complex networks.

2.2. Routing in Scale-Free Networks

Because of the importance of large complex communication networks in modern society (such as the Internet, which has scale-free properties), the dynamics of the underlying structure (such as traffic congestion) have drawn much attention from both physics and engineering standpoints. Making full use of complex network theory, the routing strategies in scale-free networks overwhelmingly focus on improving transport capacity and congestion control. To avoid congestion and improve the transmission capacity of networks, many routing strategies have been proposed in scale-free networks, including random walk, efficient routing, local routing, optimal routing, and hub avoidance strategies [8–14].

WSNs typically have scale-free properties, and it is necessary to study the routing process according to the particular requirements of these types of networks. Energy awareness is a central design issue for WSNs; to extend network lifetimes, energy-aware routing should be considered in these scale-free networks.

3. Routing Strategy

In this section, we present an overview of the EAR-LBC routing strategy then provide the pseudocode to implement it. Finally, we use a simple routing example to illustrate the proposed algorithm.

3.1. Greedy Forwarding

The proposed routing strategy is a local routing search algorithm based on greedy forwarding. Greedy forwarding aims to bring messages closer to the destination using only local information in each stage of the journey. Thus, each node forwards the message to the neighbor that is most suitable from a local point of view, which can be the one that minimizes the energy cost to the destination in each step.

Because we apply greedy forwarding to find a route from the source to the destination, we must choose a selection function that describes which of the candidates is the most promising. That is, we must identify the optimum next stage of the journey at each sensor node during the process of route finding. Obviously, it is desirable for each sensor node to forward the data packet to a neighboring node that is both close to the destination and has sufficient energy to forward the data packet. This greedy forwarding criterion can be described as a selection function that determines which candidate is nearest to the destination [16]. Suppose that node X has M direct (one-hop) neighbors, $n_{1}, n_{2}, \dots, n_{M}$ , and the destination node is D. The selection function is

\begin{matrix} f = \min ({cost}_{1}, {cost}_{2}, \dots, \cos t_{M}), \end{matrix}

(1)

where ${cost}_{i}$ is the cost between $n_{i}$ , the ith neighbor of X, and the destination D, for $i \in [1, M]$ . We define cost as follows:

\begin{matrix} {cost}_{i} = α d_{i} + (1 - α) e_{i}, \end{matrix}

(2)

where α is an adjustable parameter [9], $d_{i}$ is the distance from the ith neighbor to the destination, and $e_{i}$ is the energy consumed at the ith neighbor. The parameter α determines the weightings of $d_{i}$ and $e_{i}$ in the cost calculation.

3.2. Local Betweenness Centrality

The availability of small, low-power global positioning system (GPS) receivers for calculating relative coordinates makes it possible to obtain the distance from the ith neighbor to the destination. Therefore, in (2), we can readily obtain the value of $d_{i}$ . However, for large WSN applications, it can be very difficult for a given sensor node to determine the energy $e_{i}$ consumed at a neighboring node because of the additional overhead. In this section, we introduce the definition of local BC to estimate $e_{i}$ .

Recent studies [7, 10] have reported that BC plays an important role in the traffic on networks. For a given network, the BC of a node is defined as

\begin{matrix} B_{i} = \sum_{s \neq d} ‍ \frac{σ_{s d} (i)}{σ_{s d}}, \end{matrix}

(3)

where $σ_{s d}$ is the number of shortest paths going from s to d, and $σ_{s d} (i)$ is the number of shortest paths going from s to d and passing through i. BC quantifies the number of times a node appears in the shortest paths between two other nodes. The BC is a useful measure of the load placed on a given node in a network, as well as the importance of the node in the network. It has become a popular measurement to characterize complex networks. Based on complex network theory, if the number of nodes on the networks is denoted by N, and there are R data packets that need to be transmitted at every time step, then the average number of packets passing through a given node in t time steps can be obtained as follows [10]:

\begin{matrix} \frac{R t B_{i}}{N (N - 1)} . \end{matrix}

(4)

Assuming that the sensor node forwarding a data packet consumes energy $E_{f}$ , combining (4) and (2) we obtain

\begin{matrix} {cost}_{i} = α d_{i} + (1 - α) \frac{R t B_{i}}{N (N - 1)} E_{f}, \end{matrix}

(5)

where $B_{i}$ is BC of the ith neighbor.

However, there remains a problem that must be solved. The BC is calculated based on global topology information, which is generally not available in large-scale wireless ad hoc sensor networks. To deal with this problem, we propose an energy-aware routing system based on local BC. We extend the concept of BC from the global topology to a local routing table, which consists of the destination and the next hop information only. Similarly, the local BC of a node for a local routing table is defined as

\begin{matrix} b_{i} = \sum_{s, d, i \in Local, s \neq d} ‍ \frac{σ_{s d} (i)}{σ_{s d}}, \end{matrix}

(6)

where $σ_{s d}$ is the number of paths going from s to d in the local routing table of the local sensor node, X, and $σ_{s d} (i)$ is the number of paths going from s to d and passing through the ith neighbor in the local routing table of X. The local BC gives an estimate of the traffic handled by the neighbors around X. Therefore, the neighbor with the greatest local BC delivers more data packets, thus; consumes more energy. If we combine (5) and (6), we arrive at

\begin{matrix} {cost}_{i} = α d_{i} + (1 - α) \frac{R t b_{i}}{N (N - 1)} E_{f} . \end{matrix}

(7)

3.3. Routing Algorithm

The proposed routing algorithm is a distributed routing algorithm based on local BC. For each sensor node X, which receives a data packet P, the next hop is determined as follows. (1)

For each neighbor $n_{i}$ , the cost, ${cost}_{i}$ , is calculated using (7) with the current routing table.

(2)

Among the neighbors of X, we choose the $n_{i}$ with the minimum ${cost}_{i}$ as the next hop and forward the data packet P.

(3)

If there is no routing information about the current data packet P in the routing table, routing paths for P are added. If routing information already exists, we update the next hop information to that determined in step (2).

The pseudocode to implement the algorithm is shown in Algorithm 1.

Algorithm 1: Greedy route finding.

Input: the received packet (P)

Output: the next hop ( $n e x t h o p$ )

/⋆for each neighbor of X, calculate its

cost⋆/

foreach neighbor $n_{i}$ of X do

if routing table is empty then

$b_{i} = 0$

else

according to (6), computes $b_{i}$ based on routing

table of X;

end

computes $d_{i}$ ;

$c o s t_{i} = α d_{i} + (1 - α) \frac{R t b_{i}}{N (N - 1)} E_{f}$ ;

end

/⋆among the neighbors of X, chose the

minimum cost as the next hop⋆/

${c o s t}_{m i n} = {c o s t}_{1}$

foreach neighbor's ${c o s t}_{i}$ of X do

if ${c o s t}_{m i n} > c o s t_{i}$ then

${c o s t}_{m i n} = c o s t_{i}$ ;

$n e x t h o p = n_{i}$ ;

end

/⋆update the routing table ofX ⋆/

flagexist= 0;

while $f l a g e x i s t$ ==0 and not end of routing table of X do

/⋆ $r_{i}$ is theith routing entry in the

routing table ofX⋆/

if $r_{i} . d e s t i n a t i o n = = P . d e s t i n a t i o n$ then

flagexist $= =$ 1;

$r_{i} . n e x t h o p = n e x t h o p$

end

if $f l a g e x i s t$ ==0 then

/⋆there is no routing entry for this

packet P,need to append new rout

information⋆/

Add a new routing entry $r_{n e w}$ ;

$r_{n e w} . d e s t i n a t i o n = P . d e s t i n a t i o n$ ;

$r_{n e w} . n e x t h o p = n e x t h o p$ ;

end

if $P . d e s t i n a t i o n$ == $n e x t h o p$ then

directly send to the destinaiton

end

Initially, the routing table of X will be empty. From (6), the value of $b_{i}$ is 0, and so the cost at a neighboring node is determined from $d_{i}$ in (7). That is, the cost is determined by the distance from the ith neighbor to the destination. The packet is forwarded to the neighbor that is closest to the destination. The next hop information of the sensor node X is recorded in the routing table. As the amount of information in the routing table increases, the value of $b_{i}$ plays a larger role in the cost calculation. A neighbor with greater $b_{i}$ will have already consumed more energy due to local packet forwarding. If there are several neighbors with the same distance to the destination, the data packet should be forwarded to the neighbor with the lowest $b_{i}$ , as this will have more energy remaining than the other neighbors.

The key to the algorithm is dynamic calculation of cost informed by updating the local routing table. By choosing the optimal next hop by minimizing cost, the data packet can be routed by sensor nodes with more energy. Energy consumption becomes more uniform, and the network lifetime can be prolonged. Obviously, the proposed algorithm is equal to the traditional shortest path routing when $α = 1$ .

3.4. A Routing Example

Here, we illustrate the algorithm using a simple routing example. Consider a wireless network topology shown in Figure 1. To demonstrate the function of local BC, we consider the distance from one node to another to be the number of hops between them and focus on the change in the local BC. In Figure 1, suppose that the source node S sends several data packets, denoted by $P 1$ , $P 2$ ,…, to the destination node D and that $α = 0.125$ .

Figure 1

An example of WSN topology.

When S sends $P 1$ to D, the routing table of S is empty at the beginning. S has two one-hop neighbors, $X 1$ and $X 3$ . According to (6), the values of the local BC for these two nodes are 0. So the cost of neighbors around node S is only determined by the distance between them, and the cost of node $X 1$ , ${cost}_{X 1}$ , is calculated as follows:

\begin{array}{l} \begin{array}{l} {cost}_{X 1} = α d_{X 1 \to D} + (1 - α) b_{X 1} = \frac{1}{8} \times 2 + (1 - \frac{1}{8}) \times 0 \\ = \frac{2}{8} . \end{array} \end{array}

(8)

The term $d_{X 1 \to D}$ is the distance between node $X 1$ and the destination node D, and $b_{X 1}$ is the local BC of node $X 1$ . In a similar manner, we can obtain the cost of node $X 3$ as follows:

\begin{array}{l} \begin{array}{l} {cost}_{X 3} = α d_{X 3 \to D} + (1 - α) b_{X 3} = \frac{1}{8} \times 1 + (1 - \frac{1}{8}) \times 0 \\ = \frac{1}{8}, \end{array} \end{array}

(9)

where ${cost}_{X 3}$ is less than ${cost}_{X 1}$ , so $X 3$ is chosen as the next hop, and node S updates its routing table as shown in Table 1.

Table 1

Routing table of node S when sending data packet $P 1$ .

Destination	Next hop
D	$X 3$

Node $X 3$ receives data packet $P 1$ and finds the destination node D is in its neighbor set, then forwards the data packet to the destination node D. Node S sends $P 1$ to D using the route $S \to X 3 \to D$ .

When S sends $P 2$ to D, according to (6), the local BC of $X 1$ , denoted by $b_{X 1}$ , is 0 because there is no route passing through $X 1$ in the routing table of S. The local BC of $X 3$ , denoted by $b_{X 3}$ , is 1 because the number of paths going from S to D in the local routing table of S is 1, and the number of paths going from S to D and passing through $X 3$ in the local routing table of S is 1. S calculates the cost of its neighbors, $X 1$ and $X 2$ , again using (7); thus, we obtain

\begin{matrix} {cost}_{X 1} = α d_{X 1} + (1 - α) b_{X 1} = \frac{1}{8} \times 2 + (1 - \frac{1}{8}) \times 0 = \frac{2}{8}, \\ {cost}_{X 3} = α d_{X 3} + (1 - α) b_{X 3} = \frac{1}{8} \times 1 + (1 - \frac{1}{8}) \times 1 = 1, \end{matrix}

(10)

where ${cost}_{X 1}$ is less than ${cost}_{X 3}$ , $X 1$ is chosen as the next hop, and node S updates its routing table as shown in Table 2. Node $X 1$ receives data packet $P 2$ and determines that the next hop is $X 2$ using EAR-LBC. Finally, S sends $P 2$ to D using route $S \to X 1 \to X 2 \to D$ .

Table 2

Routing table of node S when sending data packet $P 2$ .

Destination	Next hop
D	$X 1$

In this example, data packets are routed from S to D via $S \to X 3 \to D$ and route $S \to X 1 \to X 2 \to D$ . If the shortest path algorithm was to be used, all network traffic from S to D would be routed via $S \to X 3 \to D$ , and energy would be consumed at a greater rate at $X 3$ than at nodes $X 1$ and $X 2$ because of the unbalanced network traffic. Using the proposed routing strategy, network traffic from S to D is shared by nodes $X 1$ , $X 2$ , and $X 3$ , and the the energy consumption is more balanced. The local BC is calculated based on the routing information recorded in the routing table. If the routing table is changed, the local BC is also changed, which in turn feeds back to change the routing table. From the interaction between the routing table and the calculation of the local BC, network traffic can be allocate in a manner that provides more balanced energy consumption in the network.

4. Simulation

In this section, we describe simulations that were performed to evaluate the performance of the proposed routing strategy, developed using MATLAB. Our goal was to determine the advantages of the routing strategy in terms of network lifetime, average path length, and residual energy by comparing the performance to that of other routing algorithms. Most routing processes in WSNs take place according to the criterion of the fewest hops from a given source to the destination. This is equivalent to the shortest path routing from a given source to its destination in a graph with the same edge weight on all available wireless links. We compared the performance of the EAR-LBC to that of the shortest path routing (SP).

4.1. Simulation Model

The BA model is one of several proposed models that generates scale-free networks, and the networks studied in our simulation were generated using this model. BA scale-free network incorporates two important general concepts: growth and preferential attachment. Both growth and preferential attachment exist widely in real networks. Growth means that the number of nodes in the network increases over time. Preferential attachment means that the more connected a node is, the more likely it will be to receive new links. Nodes with a higher degree have a greater ability to grab links added to the network.

The generation of networks begins with an initial network of $m_{0}$ nodes, where $m_{0} \geq 2$ and the degree of each node in the initial network should be at least 1; otherwise the node will always remain disconnected from the rest of the network. New nodes are added to the network one at a time. Each new node is connected to m existing nodes with a probability that is proportional to the number of links that the existing nodes already have. Formally, the probability $p_{i}$ that the new node is connected to node i is [1]

\begin{matrix} p_{i} = \frac{k_{i}}{\sum_{j} ‍ k_{j}}, \end{matrix}

(11)

where $k_{i}$ is the degree of node i and the summation is over all preexisting nodes j. Heavily linked nodes tend to quickly accumulate even more links, while nodes with only a few links are unlikely to be chosen as the destination for a new link. The new nodes have a “preference” to attach themselves to nodes that are already heavily linked. The average degree of a scale-free network using BA model, denoted by $〈 k 〉$ , is approximately equal to $2 m$ [4].

In our model, the number of sensor nodes in the networks is denoted by N. All nodes are treated as both sensors and routers for generating and transporting data packets, and each link has the same packet-delivery capacity. Consistent with the low data rate in WSNs, we assume that each node has sufficient processing and buffering capacity to deliver and handle all of the data packets it receives in each time step. Transport on the network proceeds in discrete time steps and is driven by inserting R new data packets, with randomly chosen sources and destinations. At each time step, every node delivers the packets toward the neighboring node with the optimum next hop as determined by the routing strategy. For the sake of comparison, the number of new data packets generated by the nodes per time step was fixed at 1 (i.e., $R = 1$ ); however, it is trivial to change this so as to meet the demands of various example networks. The initial energy of the every node was 5 joules, and $E_{f}$ is $0.02$ joules. The adjustable parameter α was 0.75.

4.2. Simulation Scenarios

Three simulation scenarios were designed as follows. (1)

The number of nodes was fixed at $N = 600$ , and the network lifetime and the average path length were investigated as a function of the average degree. In other words, we analyzed the performance of both EAR-LBC and SP routing when the average degree of the scale-free network increases, which corresponds to an increasing number of links between nodes.

(2)

We fixed the average degree so that $m_{0} = m = 5$ and $〈 k 〉 \approx 10$ and investigated the network lifetime and the average path length as a function of the number of nodes. In other words, we analyzed the performance of both EAR-LBC and SP routing when the number of nodes increases, but the average number of links between nodes does not change.

(3)

We analyzed the distribution of the residual energy in a network using both EAR-LBC and SP routing. The average degree of this network was 12 ( $m_{0} = m = 6$ , $〈 k 〉 \approx 12$ ), and the number of nodes was $N = 600$ .

4.3. Simulation Results

Figure 2 shows the simulated network lifetime, and Figure 3 shows the simulated average path length with $N = 600$ as a function of the average degree of the network for the two routing strategies. The network lifetime is considerably longer for the EAR-LBC scheme. Furthermore, the larger the average degree of the network, the longer the network lifetime can be. This can be explained by considering that there are more paths among central nodes; in EAR-LBC, the network traffic can be distributed among a larger number of different paths, and, hence, nodes with excessive energy consumption can be avoided.

Figure 2

The network lifetime, t, as a function of parameter m with $N = 600$ for both EAR-LBC and SP routing.

Figure 3

The average path length, $〈 L 〉$ , as a function of the parameter m with $N = 600$ for both EAR-LBC and SP routing.

As shown in Figure 3, the average path length of two routing strategies decreased as the average degree increased, which can be explained by considering that there are more links between the sensor nodes, and so more direct routes are likely to be available. It can be seen that, although EAR-LBC enhances the network lifetime, it does not lead to a significant increase in the average path length. Both methods resulted in almost the same average path length. This is a particular useful result because an increase in the number of hops would result in an increased energy consumption for the network as a whole. In fact, EAR-LBC only incurs an additional computational cost in processing the expression in (7) in exchange for an increase in the network lifetime. This additional computational cost is slight because data processing consumes significantly less energy than data transmission in WSNs.

The average degree was fixed at $m = 5$ ( $〈 k 〉 \approx 10$ ), and we investigated the network lifetime and the average path length as a function of the number of nodes. As shown in Figure 4, network lifetime was greatly enhanced using EAR-LBC; in both methods, the lifetime changes little a as the number of nodes is varied because if the average degree is invariant, the number of links among the sensor nodes does not increase. The network lifetime is primarily related to the traffic density rather than the number of nodes. Figure 5 shows the average path length as a function of the number of nodes; the results are similar to those shown in Figure 3. EAR-LBC enhanced network lifetime, but did not increase the average path length. EAR-LBC had almost the same average path length as SP routing.

Figure 4

The network lifetime, t, as a function of the network scale, N, with $m = 5$ , for both EAR-LBC and SP routing.

Figure 5

The average path length, $〈 L 〉$ , as a function of the network scale, N, with $m = 5$ , for both EAR-LBC and SP routing.

Figure 6 shows the distribution of residual energy plotted against the node index for a network with $N = 600$ and $m_{0} = m = 6$ when the first failure node appears (because of energy depletion) in EAR-LBC and SP routing. The network was generated using the BA model with $m_{0} = m = 6$ , which means that of the network initially had 6 nodes, and each new node was connected to 6 existing nodes. We view the order in which the nodes join the network as the index of the nodes, so that a smaller index corresponds to higher-degree nodes. Such nodes carry more networks traffic, so the energy consumption will be greater and faster at these nodes. This is why the residual energy of low-index nodes is less than that of high-index nodes. EAR-LBC resulted in a more uniform residual energy distribution than SP routing, even when the EAR-LBC network had a lifetime that was twice as long as that the SP routing. This is because EAR-LBC distributes the network traffic over several routes, decreasing the energy consumption of high-degree nodes.

Figure 6

The distribution of residual energy plotted as a function of the node index, for a network where $N = 600$ and $m_{0} = m = 6$ , when the first failure node appears, for both EAR-LBC and SP routing.

Figure 7 shows a columnar comparison chart for EAR-LBC and SP routing, illustrating the distribution of nodes as a function of the residual energy. We rate the residual energy of each node on a scale of 1 to 4. A residual energy in range of 0 to 200 is level 1. A residual energy in range of 200 to 440 is levels 2. A residual energy in range of 440 to 480 is level 3. A residual energy in range of 480 to 500 is level 4. As shown in the left column, when EAR-LBC and SP routing had the same network data traffic with $R = 1527$ , the first failure node appeared under SP, while the EAR-LBC network continued to function. In this case, the number of nodes in the EAR-LBC network with a residual energy in level 2 and 3 was larger than the number of nodes in that energy range for the network with SP routing. As shown in the right column of the figure, at failure, the residual energy of most nodes was in level 4 when using SP routing, but was evenly distributed in levels 3 and 4 when using EAR-LBC. That is, the residual energy distribution was more uniform in EAR-LBC compared to SP routing.

Figure 7

Columnar comparison chart for EAR-LBC and SP routing showing the number of nodes in different residual energy levels, for a network with $N = 600$ and $m_{0} = m = 6$ .

5. Conclusions and Future Works

We proposed an EAR-LBC for WSNs based on local BC and investigated the network lifetime and the average path length assuming that all nodes had the same initial energy. The proposed routing strategy considers realistic network structures and the dynamic energy consumption of large WSNs.

Our proposed algorithm improves upon the existing methods in two ways regarding the extension of network lifetime. First, our strategy uses greedy forwarding, which takes both the shortest path and the remaining energy at each node into account, rather than simply using traditional metrics such as the shortest path. A tunable weight, α, is used as a parameter to determine the share of path length and remaining energy in route finding. This can be easily adjusted to optimize the routing strategy in line with the particular demands of a given network. Second, the routing strategy introduces the local BC to dynamically estimate the energy consumption of the neighboring nodes. Because of these features, even in the absence of global information on network topology and energy consumption, data packets can be routed to the sensor nodes with more residual energy, which provides a more balanced energy consumption in the network.

Because of these two improvements, EAR-LBC extends network lifetime without introducing additional transmission overhead or a longer average path length. Our results have applications to the design and optimization of routing for WSNs, including environmental monitoring systems, health care systems, and target-tracking systems.

Our future work will aim to improve and extend EAR-LBC algorithms, taking into account many additional characteristics of WSNs. There are a number of directions for future research. First, we will analyze and compare the performance of the EAR-LBC strategy described here and other energy-aware routing algorithms. Based on this comparative research, we will gain insight into which applications are best suited to EAR-LBC algorithms. Second, we will create a physical implementation to evaluate the performance of the EAR-LBC algorithms experimentally and study how to select design parameters according to the WSN application.

Footnotes

Acknowledgment

This work was supported in part by the National Natural Science and Foundation of China under Grants 61105070, 61073025, 61170031, and 61272069.

References

Larios

D. F.

Barbancho

Rodriguez

Sevillano

J. L.

Molina

F. J.

Leon

Energy efficient wireless sensor network communications based on computational intelligent data fusion for environmental monitoring

IET Communications 2012 6 14 2189 2197

Anastasi

Conti

Di Francesco

Passarella

Energy conservation in wireless sensor networks: a survey

Ad Hoc Networks 2009 7 3 537 568

2-s2.0-56449087483

10.1016/j.adhoc.2008.06.003

Ishmanov

Malik

A. S.

Kim

S. W.

Energy consumption balancing (ECB) issues and mechanisms in wireless sensor networks (WSNs): a comprehensive overview

European Transactions on Telecommunications 2011 22 4 151 167

2-s2.0-79959538975

10.1002/ett.1466

Barabasi

A. L.

Albert

Emergence of scaling in randomnetworks

Science 1999 286 509

Hawick

K. A.

James

H. A.

Small-world effects in wireless agent sensor networks

International Journal of Wireless and Mobile Computing 2010 4 3 155 164

2-s2.0-77955105936

10.1504/IJWMC.2010.034213

Zhu

Luo

Peng

Luo

Complex networks-based energy-efficient evolution model for wireless sensor networks

Chaos, Solitons and Fractals 2009 41 4 1828 1835

2-s2.0-67349223908

10.1016/j.chaos.2008.07.032

Yan

Zhou

Z.-Q.

Wang

B.-H.

Efficient routing on complex networks

Physical Review E 2006 73 4 6108 6111

Danila

Sun

Bassler

K. E.

Collectively optimal routing for congested traffic limited by link capacity

Physical Review E 2009 80 6 6116 6122

2-s2.0-73649086922

10.1103/PhysRevE.80.066116

066116

Tang

Liu

Liang

Hui

P. M.

Self-adjusting routing schemes for time-varying traffic in scale-free networks

Physical Review E 2009 80 2 6114 6121

10.

Guan

Z. H.

Chen

Qian

T. H.

Routing in scale-free networks based on expanding betweenness centrality

Physica A 2011 390 6 1131 1138

11.

Tang

X. G.

Wong

E. W.

Z. X.

Integrating networks structure and dynamic information for better routing strategy on scale-free networks

Physica A 2009 388 12 2547 2554

12.

Ling

M. B.

Jiang

Wang

Cao

X. B.

Q. S.

Pheromone routing protocol on a scale-free network

Physical Review E 2009 80 6 6110 6115

13.

Meloni

Gomez-Gardenes

Local empathy provides global minimization of congestion in communication networks

Physical Review E 2009 82 5 6105 6112

14.

Tang

Zhou

Efficient routing strategies in scale-free networks with limited bandwidth

Physical Review E 2011 84 2 6116 6120

15.

Biagioni

Topics in ad hoc and sensor networks

IEEE Communications Magazine 2012 50 7 120

16.

X. H.

Hong

S. H.

Fang

A greedy and heuristic routing algorithm for wireless sensor networks in home automation

IET Communications 2011 5 13 1797 1805

17.

Cheng

Xun

Zhou

An energy aware ant colony algorithm for the routing of wireless sensor networks

Intelligent Computing and Information Science 2011 134 395 401

18.

Shah

Rabaey

Energy aware routing for low energy adhoc sensor networks

Proceedings of the IEEE Wireless Communications andNetworking Conference (IEEE WCNC ′02)

March 2002

Orlando, Fla, USA

350 355

19.

Abbasi

A. A.

Younis

A survey on clustering algorithms for wireless sensor networks

Computer Communications 2007 30 14-15 2826 2841

2-s2.0-34548850872

10.1016/j.comcom.2007.05.024

20.

Ren

Zhang

Lin

Ren

S. K. D.

EBRP: energybalanced routing protocol for data gathering in wireless sensor networks

IEEE Transactions on Parallel and Distributed Systems 2011 22 12 2108 2125

21.

Saleem

Di Caro

G. A.

Farooq

Swarm intelligence based routing protocol for wireless sensor networks: survey and future directions

Information Sciences 2011 181 20 4597 4624

2-s2.0-79960558299

10.1016/j.ins.2010.07.005

22.

Zhu

Y. H.

W. D.

Leung

V. C. M.

Energy-efficient tree-based message ferrying routing schemes for wireless sensor networks

Mobile Networks and Applications 2011 16 1 58 70

2-s2.0-79751535932

10.1007/s11036-009-0211-4

23.

Liu

Zhang

Fan

A diagnosis-based clustering and multipath routing protocol for wireless sensor networks

International Journal of Distributed Sensor Networks 2012 2012 11

504205

10.1155/2012/504205

24.

Wang

Yang

Sun

A clustering algorithm based on energy information and cluster heads expectation for wireless sensor networks

Computer and Electrical Engineering 2012 38 3 662 671

25.

Tang

Wang

Xiong

A multicast routing protocol with pruning and energy balancing for wireless sensor networks

International Journal of Distributed Sensor Networks 2012 2012 11

632836

10.1155/2012/632836

26.

Aslam

Phillips

Robertson

Sivakumar

A multi-criterion optimization technique for energy efficient cluster formation in wireless sensor networks

Information Fusion 2011 12 3 202 212

2-s2.0-79954632322

10.1016/j.inffus.2009.12.005

27.

Karim

Nasser

Reliable location-aware routing protocol for mobile wireless sensor network

IET Communications 2012 6 14 2149 2158

Energy-Aware Routing in Wireless Sensor Networks Using Local Betweenness Centrality

Abstract

1. Introduction

2. Related Works

2.1. Energy-Aware Routing in WSNs

2.2. Routing in Scale-Free Networks

3. Routing Strategy

3.1. Greedy Forwarding

3.2. Local Betweenness Centrality

3.3. Routing Algorithm

Algorithm 1: Greedy route finding.

3.4. A Routing Example

4. Simulation

4.1. Simulation Model

4.2. Simulation Scenarios

4.3. Simulation Results

5. Conclusions and Future Works

Footnotes

Acknowledgment

References