Energy-Aware Hierarchical Topology Control for Wireless Sensor Networks with Energy-Harvesting Nodes

Abstract

The nodes in a wireless sensor network (WSN) are often clustered to improve the efficiency of data transmission, but this can cause an imbalance in the energy available at each node. This impairs the transmission capability of some nodes and hence reduces network connectivity. This imbalance worsens as nodes become defunct. We propose a multilayer topology for long-term hybrid WSNs which contain both battery-powered and energy-harvesting nodes. Each node periodically selects its own layer, depending on the energy it has available, in order to balance energy levels and maintain network connectivity. Simulations show that this scheme improves the delivery of data across a WSN.

1. Introduction

Wireless sensor networks (WSNs) are now widely used to collect environmental data. A WSN consists of many wireless sensor nodes, which communicate the data they acquire to a sink node. Because of wireless range limitations, this usually involves multihop transmission, passing data from one node to the next. Nodes also have a limited lifetime because they run on batteries, and when these are exhausted transmissions cease and other nodes, which used the dead node for relaying data, may no longer be able to communicate with the sink. Therefore, it is important to prolong lifetime of the sensor nodes in a WSN.

Controlling the topology of the wireless connections between nodes can prolong the life of a network, by avoiding undue reliance on bottleneck nodes, which are likely to fail easily due to the volume of traffic that they handle, bringing out large parts of the network. However, networks with no hierarchy have their own problems. Early WSNs had a flat topology and transferred data using a flooding scheme. This can cause a broadcast storm and the redundant transmissions that result quickly exhaust the nodes’ batteries. This problem is exacerbated because the nodes closest to the sink use more energy than the others, and when they fail the rest of the network becomes isolated and thus useless.

A popular way to create a hierarchical topology is clustering. Nodes can organize themselves into clusters, each of which has a head which aggregates data from the nodes in the cluster and forwards it to the sink node. This scheme is better than the flat topology, but the cluster heads are its weak links: these nodes consume more energy than the other nodes, and die early, isolating the cluster from the sink.

This drawback is commonly ameliorated by periodically changing the head node within a cluster. Even so, dead nodes fail early and have to be replaced to achieve a satisfactory network lifetime as a whole. We have proposed a multilayer topology control scheme as an alternative way of addressing the problem. In our scheme [1], nodes are allocated to several layers, depending on the amount of energy they have available, with the aim of balancing usage against remaining energy. Nodes with plenty of energy are placed in an upper layer, and these nodes aggregate data received from lower layers. This has been shown to maintain good connectivity for far longer than other topology control schemes. However, our scheme requires to estimate lifetime of the entire network and the average amount of data relayed by each layer, in order to determine its own layer. Unfortunately, this information is not readily available at every node because the accuracy with which it can be estimated depends on the location of the node. Moreover, since all nodes are periodically able to move to other layers, estimates soon become inaccurate, and thus many nodes fail to locate themselves in the best layer.

The life of a network can also be prolonged if energy is harvested from the environment: an energy-harvesting node can potentially operate forever by recharging its battery with environmental energy. Even so, a node will eventually cease to operate if it consumes more energy than it is able to harvest. Many researchers [2] have designed topology control schemes to maximize the lifetime of a network of energy-harvesting nodes. However, many practical WSNs contain a mixed population of nodes, some of which can and some of which cannot harvest energy, and prolonging the lifetime of this class of WSN has received much less attention.

In this paper, we propose a topology control scheme for preserving connectivity between nodes in long-term WSNs, in which defunct nodes are manually replaced and which contains both energy-harvesting nodes and battery-powered nodes. In such a WSN, the battery-powered nodes can be expected to have diverse amounts of residual energy, which decline with length of deployment. As in our previous scheme, the nodes arrange themselves into layers, and the nodes on the upper layer are given the job of aggregating data received from the nodes on the lower layers and sending it to a sink node. Like previous layering schemes, this arrangement improves energy efficiency and connectivity; but this new scheme increases the lifetime of battery-powered nodes by preferentially locating energy-harvesting nodes on higher layers.

The rest of the paper is organized as follows. In Section 2 we describe the background to this research and review related work. In Section 3 we introduce our scheme for layer-based topology control and describe how nodes choose their layer and establish connectivity with neighboring nodes. In Section 4 we present experimental results and assess the performance of our scheme. In Section 5 we introduce a proposal for further research. Section 6 concludes the paper.

2. Background and Related Work

2.1. Energy-Harvesting Wireless Sensor Networks

WSNs consisting solely of battery-powered nodes naturally have a limited lifetime, and there have been many proposals [2] to use energy-harvesting nodes to extend the lifetime of WSNs [2]. The environmental sources from which it is practical for nodes to harvest energy are the sun [3–8] and the wind [8, 9]. Solar-powered wireless sensor nodes are usually preferred [10] because of the high areal density of solar power (about 15 mW/cm²).

Many schemes have been proposed to maximize the contribution of solar energy to extending the life of a WSN. Kansal et al. [11] proposed an energy model for solar-powered nodes, which estimates the levels of energy consumption and harvesting which will allow a node to survive indefinitely. Noh and Kang [12] designed an energy allocation scheme which estimates the energy that will be harvested by a solar cell every hour and determines future consumption levels which will allow the node to survive; a complementary routing algorithm has also been presented [13].

The efficient use of solar energy requires accurate prediction, which is relatively easy because of its obvious relation to the diurnal cycle. Nevertheless, the availability of sunlight is of course affected by weather. Kansal et al. [3], Piorno et al. [14], Moser et al. [15], and Cammarano et al. [16] have all proposed models for estimating the availability of solar energy, using, respectively, an exponentially weighted moving-average (EWMA), the so-called weather-conditioned moving average (WCMA), a weighted sum of historical data, and the Pro-Energy model.

2.2. Hierarchical Topology Control for WSNs with Energy-Harvesting Nodes

Topology control, which determines how nodes connect to each other, is an important issue which affects WSN performance. Only relatively recently has it been applied to WSNs which use energy-harvesting nodes.

Voigt et al. [17] introduced the solar-aware LEACH algorithm (sLEACH) which applies LEACH [18] to WSNs consisting of both solar-powered and battery-powered nodes. The sLEACH algorithm strongly favors the use of solar-powered nodes as cluster heads, which have to do more work than other nodes. LEACH is effective in equalizing energy usage across (battery-powered) nodes, but sLEACH cannot be applied to large WSNs because all the cluster heads must connect directly to the sink. In addition, sLEACH tends to allow the harvested energy to be under-utilized, or to run out, because sLEACH does not consider energy stored at each node and the rate at which each node acquires energy.

Zhang et al. [19, 20] proposed a scheme which overcomes the need for each cluster head to connect directly to the sink, by using further energy-harvesting nodes to relay transmissions from the cluster head to the sink. This can also save energy by reducing the range over which cluster heads are required to transmit. Gou et al. [21] also addressed the drawbacks of sLEACH by partitioning a WSN and taking the energy remaining in each node into account.

Jakobsen et al. [22] and Meng et al. [23] also have proposed hierarchical topology control schemes for energy-harvesting nodes.

3. Layer-Based Topology Control with Energy-Harvesting Sensor Nodes

We will now introduce a new layer-based topology control scheme and explain how to allocate nodes to layers, how nodes operate within the layers, and how the scheme applies to energy-harvesting nodes. We will assume that a WSN contains both battery-powered and energy-harvesting nodes, which periodically forward the data that they have gathered to the sink node. We are also assuming that defunct nodes will be replaced, because this is a long-term WSN.

3.1. Review of Layer-Based Topology Control for Long-Term WSNs with Battery-Powered Nodes

In our previous layer-based topology control scheme [1], all the nodes gather data and periodically forward it to a sink node. Nodes are arranged in layers, and data travels hierarchically. This scheme has been shown to reduce the imbalance in available energy across the nodes.

Each node is periodically allocated to a layer on the basis of its estimated lifetime. The nodes in each layer affectively consider all higher-layer nodes as local sink nodes, relative to their own layer, and data is routed by the multi-sink-aware minimum-depth tree (m-MDT) algorithm [24]. Nodes in the upper layers forward the data received from lower-layer nodes, as well as the data they themselves have acquired, to nodes in yet higher layers. By repetition of these processes all the data arrives at the actual sink node. In order to prevent data being sent on void [25] or cyclic routes, nodes are not permitted to send data to nodes in lower layers. Figure 1 shows a topology with three layers.

Figure 1

Overview of layer-based topology control.

Naturally, nodes in higher layers will have to transit more data, requiring more energy. This is why energy-rich nodes are placed in higher layers. Each node determines its own layer, on the basis of the amount of energy that it has remaining, the amount of data which it is likely to have to transmit, and its estimated lifetime.

As we already mentioned, a drawback with this scheme is that the nodes’ estimation of the amount of data which they will have to transmit during a subsequent data transmission phase is not accurate, because it is an average of the amount of data transmitted by all the nodes, whereas the actual amount depends on the location of a particular node. In addition, this scheme potentially allows all nodes to change their layers very frequently, making it difficult to determine which layer is actually the best, because the amount of energy that a node forecasts it will consume in a layer is likely to be very different from its actual consumption when it moves itself to that layer. Furthermore, our scheme does not consider energy-harvesting nodes, which is the rationale of this present paper. We address all these deficiencies in the new scheme which we will now describe.

3.2. The Layer Determination Algorithm

We will now introduce our improved layer-based topology control scheme and explain how each node determines its layer. Unfortunately, this requires a lot of notation, and so we summarize frequently used notation in Notation Summary.

3.2.1. Operation of a Node

When a node $n_{i}$ is deployed in a network for the first time, it joins the lowest layer and selects a target node among neighboring nodes in response to Local topology control information (TCI) messages from neighboring nodes. Node $n_{i}$ then begins to gather information from the environment and sends it to the sink node via its target node, during every gathering period $p_{gather}$ . At the beginning of each round the sink node sends a Global topology control information (TCI) message to the entire network, using a flooding process. This occupies a setup period $p_{setup}$ . Each node then begins its Layer determination process at the beginning of the subsequent layer determination period $p_{{layer}_{i}}$ , or earlier, if it has received the Global TCI message from the sink node. This process determines a nodes’ new layer. If a node $n_{i}$ is moving to another layer, then it sends a Layer notification message to its neighbors, and they may have to select new target nodes as a result. The logic of node operation is shown in Figure 2, and Figure 3 shows an example timeline.

Figure 2

Node operation.

Figure 3

Example of node operation. The shaded box indicates a single round.

3.2.2. Topology Control Information for Layer and Target Determination

To determine the layer in which it should reside, a node needs information about its 1- and 2-hop neighbor nodes in the network. This information is delivered to nodes by topology control information (TCI) messages, which can be local or global, depending on their content and the range over which they are delivered.

Global TCI. At the beginning of each setup period $p_{setup}$ a Global TCI message, containing information relating to topology control and routing, is transmitted by the sink node to the entire network, using a flooding process. When a node which receives a Global TCI message, it executes the Synchronous layer determination process, presented as Algorithm 2 and may then change its layer. The sink node selects setup period $p_{setup}$ . A longer setup period makes topology control more accurate, but the allowable topology control overhead is limited. Table 1 shows the contents of a Global TCI message.

Table 1

Global TCI message.

Notation	Description
a	Index of this TCI message
i	Index of the sender node
j	The layer to which the sender belongs (for routing)

Local TCI. A Local TCI message contains information about a node's 2-hop neighbors, the shortest hop-count from the sending node to a higher-layer node, and the nodes’ expected lifetime, together with general neighborhood information commonly exchanged by nodes within WSNs. A node $n_{i}^{j}$ periodically broadcasts to its 1-hop neighbors, following a generic WSN protocol at the beginning of its layer determination period ${p_{layer}}_{i}$ . Tables 2 and 3 show the contents of a Local TCI message.

Table 2

Local TCI message.

Notation	Description
i	Node index
j	The sender's layer
N	Set of neighbor nodes $n_{k}^{l} \in N$
$h_{i}$	Hop-count to the closest known node on a higher layer
$L_{i}$	Expected lifetime of the sender (in rounds)

Table 3

Information about each neighbor node in N.

Notation	Description
$s_{k}$	Amount of data which this neighbor node transmitted during the previous gathering period $p_{gather}$
$t_{k}$	Neighbor's target node
l	Neighbor's layer
$h_{k}$	Shortest hop-count from this neighbor to a node on a higher layer
$L_{k}$	Expected lifetime of this neighbor (in rounds)

In our previous system [1], the average expected lifetime of all nodes was delivered to all the nodes in the WSN by means of a Global TCI message, and this information was used in determining each node's layer; but this procedure is not appropriate for WSNs in which nodes closer to a sink use more energy. In our new scheme, therefore, each node calculates a local average expected lifetime from information supplied by its 1- and 2-hop neighbors. This average is derived from the expected lifetime $L_{i}$ of a node i, which is determined as follows:

\begin{matrix} L_{i} = \frac{{E_{remain}}_{i}}{{E_{round}}_{i}}, \end{matrix}

(1)

where

{E_{remain}}_{i}

is the remaining energy in node i's battery and

{E_{round}}_{i}

is the energy that node i consumed during the previous round.

3.2.3. Layer Determination

Each node $n_{i}$ determines its layer by executing a Layer determination process at the beginning of its layer determination period ${p_{layer}}_{i}$ , or when it receives a Global TCI message or a Layer notification message. There are two kinds of Layer determination process, as follows.

Asynchronous Layer Determination. Node $n_{i}^{j}$ performs this process at the start of every layer determination period ${p_{layer}}_{i}$ .

It determines whether to move up one layer by computing $L_{i}^{j + 1}$ , which is the estimated lifetime of node i, if it moves up to layer $j + 1$ . The expression for $L_{i}^{j + 1}$ follows later, as (9). Node $n_{i}^{j}$ compares $L_{i}^{j + 1}$ with ${\bar{L}}_{i}$ , the average local expected lifetime of its 1- and 2-hop neighbors. If $L_{i}^{j + 1}$ is greater than ${\bar{L}}_{i}$ , then $n_{i}^{j}$ ascends to the next higher layer, provided that it will have at least one node in its set of neighbor nodes $N_{i}$ at the new level. Otherwise, $n_{i}^{j}$ does not change layers, to avoid becoming a void node.

If node $n_{i}^{j}$ moves from layer j to layer $j + 1$ as a result of running the Asynchronous layer determination process, it broadcasts a Layer notification message to inform its neighbors of the change. A node which receives such a message redetermines its target node by running the Target determination process. This selects the node's neighbor $n_{k}^{l} (l > j)$ which has the minimum hop-count to an upper-layer node to be its new target node. The Asynchronous layer determination and Target determination processes are presented as Algorithm 1.

Algorithm 1: Asynchronous layer determination.

Reuire: ${p_{layer}}_{i}$ of node $n_{i}^{j}$ expires

Ensure: Determine whether node $n_{i}^{j}$ moves to layer $j + 1$

(1) procedure Layer Determination

(2) Calculate $L_{i}^{j + 1}$ using (9)

(3) if $L_{i}^{j + 1} > \bar{L} \land {\exists n}_{k}^{l} (l > j) \in N_{i}$ then

(4) $j \leftarrow j + 1$

(5) Target Determination( $j, N_{i}$ )

(6) Broadcast Layer notification message

(7) end if

(8) end procedure

(9) procedure Target Determination( $j, N_{i}$ )

(10) if $S = \{n_{k}^{l} | l > j \land n_{k}^{l} \in N_{i}\} \neq \emptyset$ then

(11) $t_{i} \leftarrow n_{k}^{l} (has minimum h_{k}) \in S$

(12) else

(13) $t_{i} \leftarrow n_{k}^{l} (has minimum h_{k}) \in \{n_{k}^{l} | l = j, n_{k}^{l} \in N\}$

(14) end if

(15) end procedure

Algorithm 2: Synchronous layer determination.

Require: Node $n_{i}^{j}$ receives Global TCI message from $n_{k}^{l}$

Ensure: Determine whether node $n_{i}^{j}$ moves to layer $j - 1$

(1) Calculate $L_{i}$ using (1)

(2) if $n_{i}^{j}$ has already received a TCI from another node then

(3) if $j_{next} > j \land l > j$ then

(4) $j \leftarrow MIN (j_{next}, l)$

(5) $t_{i} \leftarrow n_{k}^{l}$

(6) Broadcast Global TCI message

(7) end if

(8) else

(9) if $L_{i} < \bar{L}$ then

(10) $j_{next} \leftarrow j - 1$

(11) else

(12) $j_{next} \leftarrow j$

(13) end if

(14) $j \leftarrow MIN(j_{next}, l)$

(15) $t_{i} \leftarrow n_{k}^{l}$

(16) Broadcast Global TCI message

(17) end if

Synchronous Layer Determination. This process determines whether a node will descend to the layer below its current layer. The sink node broadcasts a Global TCI message of the form described in Table 1, and every node which receives it runs the Synchronous layer determination process.

If node $n_{i}^{j}$ receives a Global TCI message from node $n_{k}^{l}$ , it calculates its expected lifetime $L_{i}$ using (1). If $L_{i}$ is less than the local expected lifetime ${\bar{L}}_{i}$ , it moves to the next lower layer $j - 1$ . Then it selects $n_{k}^{l}$ as its target node and sends a Global TCI message to its neighbors. However, if node $n_{i}^{j}$ subsequently receives a duplicate Global TCI message from another node $n_{o}^{p}$ , it runs the Layer determination process again. If this changes its choice of layer, it selects $n_{o}^{p}$ as its target node $t_{i}$ and broadcasts its Global TCI message again. Each node repeats this process until all the nodes have determined their layers and target nodes. This process is presented as Algorithm 2.

We will now explain why there are two Layer determination processes. If all the nodes were to change their layers at the same time, their estimates of their own lifetimes $\bar{L}$ would be less accurate, because the method of determining ${\bar{L}}_{i}$ assumes that neighbor nodes will not change their layers until ${\bar{L}}_{i}$ is calculated again. Therefore the Asynchronous layer determination process is used to determine whether a node should move up to the next layer. However, when a node $n_{i}^{j}$ moves down a layer, it is not certain that the nodes which have $n_{i}^{j}$ as their target node will be able to find a new route to a higher-layer node. This is why the process which determines whether a node moves up a layer is executed by asynchronously at the beginning of each layer determination period ${p_{layer}}_{i}$ , whereas all the nodes run the process which determines whether they will move down at the same time.

3.2.4. Estimated Lifetime of a Battery-Powered Node

Our scheme requires each node to calculate its expected lifetime and then to determine its layer by comparing its own expectation with the local expected lifetime ${\bar{L}}_{i}$ . The expected lifetime of a node can be obtained by applying (1) to the amount of energy which that node consumed during the previous round. However, the Synchronous layer determination process, presented as Algorithm 1, requires a node to estimate its lifetime on the assumption that it is elevated to layer $j + 1$ . We will explain this move complicated process in due course.

Estimation of Energy Consumption. An estimate of the energy consumed by a node can be made as follows [26]:

\begin{matrix} E_{consume} = E_{trans} + E_{receive} + E_{elec}, \end{matrix}

(2)

where

E_{trans}

and

E_{receive}

are, respectively, the amount of energy consumed by the node's radio transceiver during the transmission and receipt of data and

E_{elec}

is the energy consumed by the node's electric circuits. The energy which a node

n_{i}^{j}

consumes during the setup period

p_{setup}

, starting at time t, is

\begin{array}{l} {E_{round}}_{i}^{j} (t) = \int_{t}^{t + p_{setup}} {E_{consume}}_{i}^{j} (τ) d τ, \end{array}

(3)

\begin{array}{l} {E_{round}}_{i}^{j} (t) \\ = \int_{t}^{t + p_{setup}} ({E_{trans}}_{i}^{j} (τ) + {E_{receive}}_{i}^{j} (τ) + {E_{elec}}_{i} (τ)) d τ, \end{array}

(4)

where

{E_{trans}}_{i}^{j}

is the energy required by node

n_{i}^{j}

during period

p_{setup}

, which can be determined as follows:

\begin{matrix} \int_{t}^{t + p_{setup}} {E_{trans}}_{i}^{j} (τ) d τ = s {β d}^{α}, \end{matrix}

(5)

\begin{matrix} \int_{t}^{t + p_{setup}} {E_{trans}}_{i}^{j} (τ) d τ = ⌊\frac{p_{setup}}{p_{gather}}⌋ {s_{trans}}_{i}^{j} {β d}_{i}^{α} . \end{matrix}

(6)

In this expression s is the amount of data to be transmitted;

{s_{trans}}_{i}^{j}

is the amount of data which

n_{i}^{j}

transmits during gathering period

p_{gather}

; α is the path loss (

2 \geq α \geq 5

); β is the energy used by the power amplifier in transmitting 1 bit over a distance of 1 meter; d is the distance between the nodes [m]. By substituting (6) into (4),

{E_{round}}_{i}^{j} (t)

can be expressed as follows:

\begin{array}{l} {E_{round}}_{i}^{j} (t) = ⌊\frac{p_{s}}{p_{g}}⌋ {s_{trans}}_{i}^{j} {β d}_{i}^{α} \\ + \int_{t}^{t + p_{setup}} ({E_{receive}}_{i}^{j} (τ) + {E_{elec}}_{i}^{j} (τ)) d τ . \end{array}

(7)

Let us assume that the data from lower-layer nodes is aggregated into a single packet, which is sent immediately. The amount of data to be transmitted

{s_{trans}}_{i}^{j}

, which varies from layer to layer, can be expressed as follows:

\begin{matrix} {s_{trans}}_{i}^{j} = s_{head} + s_{sensor} + {s_{lower}}_{i}^{j} + {s_{relay}}_{i}^{j}, \end{matrix}

(8)

where

s_{head}

is the amount of data in a packet header;

s_{sensor}

is the amount of data gathered by the sensor in node

n_{i}^{j}

;

{s_{lower}}_{i}^{j}

is the amount of data received by node

n_{i}^{j}

from nodes on lower layers, excluding packet headers; and

{s_{relay}}_{i}^{j}

is the amount of data received from nodes on the same layer.

Estimating the Amount of Data That a Node Must Transmit If It Moves to a Higher Layer. The amount of data which node $n_{i}^{j}$ will have to transmit if it is elevated to layer $j + 1$ can be determined by considering three cases, shown in Figure 4. In describing these cases, we will write the set of neighbor nodes of $n_{i}^{j}$ , $N_{i}$ , and the target node of $n_{k}$ as $\forall n_{k}^{l} \in N_{i}$ , as $t_{k}$ .

Figure 4

Estimating the amount of data to be transmitted, as part of Asynchronous layer determination.

Case 1 (target node $t_{k} = n_{m}^{j}$ ).

The highest layer of any of the neighbor nodes $n_{k}^{l}$ is j, because a node sends data to its highest-layer neighbors. However, if $n_{i}^{j}$ is elevated to become $n_{i}^{j + 1}$ , it will be the highest-layer node among neighbors of $n_{k}^{l}$ . Therefore, $n_{i}^{j + 1}$ becomes the new target node $n_{k}$ , and the ${s_{data}}_{k}$ bits which node $n_{k}$ transferred during the previous round must be added to ${s_{lower}}_{i}^{j + 1}$ .

Case 2 ( $t_{k} = n_{m}^{j + 1}$ and the hop-count of $n_{m}^{j + 1}, h_{m} > h_{i}$ ).

The target node $t_{k}$ will become $n_{i}^{j + 1}$ . However, if $l = j + 1$ , then ${s_{data}}_{k} + s_{head}$ should be added to ${s_{relay}}_{i}^{j + 1}$ , because $n_{k}^{l}$ will use $n_{i}^{j + 1}$ as a relay node; but if $l < j + 1$ , then ${s_{data}}_{k}$ should be added to ${s_{lower}}_{i}^{j + 1}$ , because $n_{i}^{j + 1}$ will be used as an aggregation node.

Case 3 (otherwise).

Other nodes already have better target nodes than $n_{i}^{j + 1}$ , and so they do not send it any data.

All the information which a node requires in order to estimate the amount of data that it will have to relay can be obtained by exchanging Local TCI messages with its neighbors.

The estimated lifetime $L_{i}^{j + 1}$ , which is the number of rounds that node $n_{i}^{j + 1}$ can be expected to survive, can now be calculated from ${E_{round}}_{i}^{j + 1} (t)$ , as follows:

\begin{matrix} L_{i}^{j + 1} = ⌊\frac{{E_{remain}}_{i}}{{E_{round}}_{i}^{j + 1} (t)}⌋ . \end{matrix}

(9)

L_{i}^{j + 1}

is used in Algorithm 1 to determine whether

n_{i}^{j}

moves up a layer.

3.3. Introducing Energy-Harvesting Nodes to a Layered Topology

In a WSN that has both energy-harvesting and battery-powered nodes, the network lifetime can be extended by preferential deployment of energy-harvesting nodes on upper layers as aggregation nodes. However, a node will eventually die if it uses more energy than it harvests and this is a greater threat to upper-layer nodes, because they have to transmit a lot of data. It is better to deploy energy-harvesting nodes on layers with workloads that allow them to them to survive indefinitely.

In the previous section, we showed how to determine the layer of a battery-powered node on the basis of a comparison between its estimated lifetime and the average expected lifetime of neighboring nodes. However, energy-harvesting nodes do not have well-defined lifetimes, and so they must be allocated to layers in a different way.

3.3.1. Energy Model for Energy-Harvesting Nodes

Although its long-term survival cannot be predicted, an energy-harvesting node $n_{i}^{j}$ , for the case that it can determine its layer, needs to know whether its lifetime extends beyond the current round. Kansal et al. [11] introduced a model of energy harvesting and consumption and proposed a bound on the residual energy which should allow a node to survive indefinitely. Based on this model, the residual energy available to node $n_{i}^{j}$ , after a setup period $p_{setup}$ beginning at time t, can be expressed as follows:

\begin{array}{l} {E_{remain}}_{i}^{j} (t + p_{setup}) = {E_{remain}}_{i} (t) - {E_{round}}_{i}^{j} (t) \\ + {E_{charge}}_{i} (t, p_{setup}), \\ 0 < {E_{remain}}_{i} (x) < {E_{\max}}_{i}, \end{array}

(10)

where

{E_{remain}}_{i}^{j} (t)

is the residual energy available to node

n_{i}^{j}

at time t;

{E_{round}}_{i}^{j} (t)

is the energy consumed during

p_{setup}

;

{E_{charge}}_{i} (t, p_{setup})

is the energy harvested during

p_{setup}

; and

E_{\max}

is the capacity of the node's battery.

The expected energy harvest, ${E_{charge}}_{i} (t, p_{setup})$ , can be determined as follows:

\begin{matrix} {E_{charge}}_{i} (t, p_{setup}) = \int_{t}^{t + p_{setup}} λ_{i} (τ) d τ, \end{matrix}

(11)

where

λ_{i} (τ)

is the charging rate of

n_{i}

at time τ. Some researchers have suggested ways of estimating λ. For instance, Kansal et al. [3] use an exponentially weighted moving-average (EWMA) algorithm to estimate the charging rate of a solar cell.

The expected energy consumption ${E_{round}}_{i}^{j} (t)$ can be calculated using (1) or (7).

3.3.2. Determining the Layer of an Energy-Harvesting Node

Because of the impracticality of estimating the lifetime of an energy-harvesting node, we settle for estimating whether an energy-harvesting node $n_{i}^{j}$ is likely to be alive after $p_{setup}$ if it is allocated to a certain layer. If it is expected to survive on a higher layer, then it moves up to that layer; conversely, if it is not expected to survive on its current layer, it moves to a lower layer.

Determining Whether a Node Should Move to a Higher Layer. If the estimated energy conserved stored in the battery of an energy-harvesting node $n_{i}^{j}$ , which is ${E_{remain}}_{i}^{j + 1} (t + p_{setup})$ and can be found using (10), satisfies the following condition, then the node can move to the next higher layer $j + 1$ :

\begin{matrix} {E_{remain}}_{i}^{j + 1} (t + p_{setup}) > {E_{\min}}_{i} + ϵ_{i}, \end{matrix}

(12)

where

{E_{\min}}_{i}

is the minimum energy required to operate node

n_{i}

properly, which depends on the specification of each sensor node, and

ϵ_{i}

is the estimation error of

{E_{charge}}_{i} (t, p_{setup})

, which can be estimated using a charging energy estimation algorithm [3]. If (12) is satisfied, node

n_{i}

will not become defunct until next round at the earliest. We can now modify the Asynchronous layer determination process to apply to energy-harvesting nodes by modifying line 3 of Algorithm 1 to reflect (12).

Determining Whether a Node Should Move to a Lower Layer. If the expected energy remaining in energy-harvesting node $n_{i}^{j}$ , which is ${E_{remain}}_{i}^{j} (t + p_{setup})$ and can be found using (10), satisfies the following condition, then that node should move to a lower layer, because it will die in its current layer:

\begin{matrix} {E_{remain}}_{i}^{j} (t + p_{setup}) < {E_{\min}}_{i} + ϵ_{i} . \end{matrix}

(13)

However,

{E_{remain}}_{i}^{j} (t + p_{setup})

must be computed using

{E_{consume}}_{i}^{j} (t - p_{setup}, t)

, which is the energy consumed during the previous round, in (7) instead of

{E_{round}}_{i}^{j} (t)

. We can modify the Synchronous layer determination process to apply to energy-harvesting nodes by modifying Algorithm 2 to reflect (13).

4. Experimental Results

4.1. Simulation Environment

We wrote a simulation in C++ to evaluate the performance of the proposed scheme. In this simulation, we measured the average amount of dead nodes, and the average number of data arriving at the sink node, with a network topology consisting of up to four layers, respectively: a single layer is a flat topology. We deployed 500 nodes and each test set was run 20 times for 5000 rounds to obtain the average values. For topologies with more than one layer, all nodes were assigned to layers at the beginning of each round, using the proposed scheme. Each node transfers the data that it obtains from its sensor to one of the nodes in the layer above by running the minimum-depth tree algorithm at intervals of $p_{gather}$ . The nodes in the upper layers aggregate their own data with that received from the nodes below and forward it all to their target node. Table 4 summarizes the important parameters used in this simulation.

Table 4

Important parameters used in our simulation.

Parameter	Value
Number of nodes	500
Node density	0.03~0.07 nodes/m²
Node placement	Random
Amount of data in a packet	60 bytes
Amount of a packet header	40 bytes
Transmission range	10~20 m
Maximum number of layers	1~4
α and β in (6)	4 and 100 pJ/bit/m²
$E_{elec}$ and $E_{receive}$ in (4)	0.000048 J and 0.048 J
${p_{layer}}_{i}$ and $p_{setup}$	6 hours
$p_{gather}$	60 s

4.2. Simulation Results

Figures 5 and 6 show the cumulative number of defunct nodes and the amount of data which the sink node received successfully. In this experiment, all nodes are battery-powered, and dead nodes are not replaced. We did not use any data aggregation scheme, to exclude its influence on the results. Figure 5 shows that the layered topology reduces the number of defunct nodes, especially at the beginning of the simulation, compared to the flat topology. This demonstrates how the nodes in a layered topology prolong their lifetimes by changing layer to manage their energy usage. By round 800, the number of dead nodes in a 4-layer network is reduced by 15%, compared to a flat network, and the difference increases in subsequent rounds. Figure 6 shows that this reduction in the number of dead nodes increases the amount of data reaching the sink.

Figure 5

Change in the number of dead nodes without replacement.

Figure 6

Change in the amount of data gathered at the sink node without replacement.

Figure 7 traces the number of defunct nodes over time in the network, in a scenario in which dead nodes are replaced with new nodes at every 200 rounds. This resulting sawtooth curve results in the pattern of Figure 5 as the network is refreshed by new nodes with fully changed batteries. Figures 8 and 9, respectively, show the number of dead nodes and the amount of data that arrived at the sink node, as the replacement period was varied from 100 to 300. The flat topology causes more nodes to die and data transmission is less effective than it is with the layered topology. The effectiveness of transmission declines as the redeployment period increases, as we would expect, because dead nodes are waiting longer for replacement.

Figure 7

Variation in the number of dead nodes with periodic replacement.

Figure 8

Variation in the number of dead nodes with the replacement period.

Figure 9

Variation in the amount of data arriving at the sink node with the replacement period.

Figures 10 and 11, respectively, show the number of dead nodes and the amount of data delivered to the sink. In this simulation, we assume that the network consists of only battery-powered nodes, and each node was a naive data aggregation scheme. Nodes aggregate the data received from the nodes in lower layers with their own data before sending it to their target node. The size of the resulting packet can be reduced omitting the headers of the packets received from lower-layer nodes; and the effectiveness of data aggregation is proportional to the size of a packet header. As shown in Figures 10 and 11, our scheme shown reduces the number of dead nodes by about 10% and delivers slightly more data than the flat topology.

Figure 10

Number of dead nodes with data aggregation.

Figure 11

Amount of data arriving at the sink node with the data aggregation.

In order to analyze the effectiveness of our scheme in networks with energy-harvesting nodes, we measured the number of dead nodes and the amount of transmitted data in a network consisting of 90% battery-powered nodes and 10% of energy-harvesting nodes. As shown in Figure 12, the number of dead nodes is reduced by about 10% by our scheme, which is very similar to the result for the network with only battery-powered nodes. Figure 13 shows that our scheme also delivers more data. However, it also shows that the effectiveness of transmission is sometimes reduced by the presence of energy-harvesting nodes. We suggest that this is because the energy-harvesting nodes are not replaced, even when they have little energy; instead, they wait for energy to arrive and charge their batteries. Meanwhile transmissions are failing. We also found that using energy-harvesting nodes as cluster nodes produces the least effective transmission of data. Again, we attribute this to the amount of energy acquired by these nodes, which is inadequate to transmit lots of data. This problem may be addressed by increasing the size of solar panels fitted to energy-harvesting nodes, or reducing the proportion of these nodes that are deployed.

Figure 12

Variation in the number of dead nodes as the proportion of energy-harvesting nodes is increased.

Figure 13

Variation in the amount of data arriving at the sink node as the proportion of energy-harvesting nodes is increased.

5. Future Work

The routing algorithm adopted in this paper causes a node to choose the route that reaches a higher-layer node with the minimum hop-count: only the length of routes is considered, not the residual energy in the nodes on those routes or their contribution to overall network connectivity. Therefore it does not explicitly contribute to the lifetime or connectivity of a network. We believe that it should be possible to design a routing scheme for layer-based topology control which makes a greater contribution to overall network efficiency.

The aggregation scheme reported in this paper is naive, in that it only aggregates data delivered from lower layers. More efficient data aggregation or fusion schemes have been described [27–30], and we intend to adopt one of them to reduce the volume of data to be transmitted and hence increase the lifetime of a WSN.

6. Conclusions

Since the nodes in a WSN are connected to the sink node by multihop routes, the demise of intermediate nodes reduces the amount of data that reaches the sink. A lot of work by many researches has been put into topology control techniques to address this problem.

In this paper we have proposed a layer-based topology control scheme for WSNs consisting of many nodes, some of which are battery-powered and some energy harvesting. These nodes are arranged in layers on the basis of their residual energy. The nodes in the higher layers aggregate data received from lower-layer nodes and send it to the sink node, together with data obtained from their own sensor. This preserves the connectivity of the WSN, because the expected lifetimes of nodes are balanced by moving them between layers.

Footnotes

Notation Summary

Conflict of Interests

The authors declare no conflict of interests.

Acknowledgments

This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korean government (MEST) (NRF-2012R1A1A2044653, no. 2011-0000228) and by Next-Generation Information Computing Development Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (no. 2012M3C4A7032182).

References

Yoon

Noh

D. K.

Shin

Multi-layer topology control for long-term wireless sensor networks

EURASIP Journal on Wireless Communications and Networking 2012 2012 1, article 164 9

10.1186/1687-1499-2012-164

2-s2.0-84872875189

Sudevalayam

Kulkarni

Energy harvesting sensor nodes: survey and implications

IEEE Communications Surveys & Tutorials 2011 13 3 443 461

10.1109/surv.2011.060710.00094

2-s2.0-79959289243

Kansal

Hsu

Zahedi

Srivastava

M. B.

Power management in energy harvesting sensor networks

ACM Transactions on Embedded Computing Systems 2007 6 4, article 32

10.1145/1274858.1274870

Jiang

Polastre

Culler

Perpetual environmentally powered sensor networks

Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN '05)

April 2005

IEEE

463 468

10.1109/ipsn.2005.1440974

2-s2.0-33646950065

Raghunathan

Kansal

Hsu

Friedman

Srivastava

Design considerations for solar energy harvesting wireless embedded systems

Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN '05)

April 2005

IEEE Press

457 462

10.1109/ipsn.2005.1440973

2-s2.0-33646926519

Hsu

Zahedi

Kansal

Srivastava

Raghunathan

Adaptive duty cycling for energy harvesting systems

Proceedings of the 2006 International Symposium on Low Power Electronics and Design

October 2006

ACM

180 185

Simjee

Chou

P. H.

Everlast: long-life, supercapacitor-operated wireless sensor node

Proceedings of the International Symposium on Low Power Electronics and Design (ISLPED '06)

October 2006

IEEE

197 202

10.1109/LPE.2006.4271835

Park

Chou

P. H.

AmbiMax: autonomous energy harvesting platform for multi-supply wireless sensor nodes

Proceedings of the 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks (SECON '06)

September 2006

Reston, Va, USA

IEEE

168 177

10.1109/sahcn.2006.288421

2-s2.0-43849087328

Weimer

M. A.

Paing

T. S.

Zane

R. A.

Remote area wind energy harvesting for low-power autonomous sensors

Proceedings of the 37th IEEE Power Electronics Specialists Conference (PESC '06)

June 2006

IEEE

1 5

10.1109/pesc.2006.1712213

2-s2.0-42449146549

10.

Roundy

Steingart

Frechette

Wright

Rabaey

Power sources for wireless sensor networks

Wireless Sensor Networks 2004 2920

Berlin, Germany

Springer

1 17 Lecture Notes in Computer Science

10.1007/978-3-540-24606-0_1

11.

Kansal

Potter

Srivastava

M. B.

Performance aware tasking for environmentally powered sensor networks

ACM SIGMETRICS Performance Evaluation Review 2004 32 1 223 234

10.1145/1012888.1005714

12.

Noh

D. K.

Kang

Balanced energy allocation scheme for a solar-powered sensor system and its effects on network-wide performance

Journal of Computer and System Sciences 2011 77 5 917 932

10.1016/j.jcss.2010.08.008

MR2829521

ZBL1253.93139

2-s2.0-79957975770

13.

Noh

Kim

Lee

Kwon

Shin

Priority-based routing for solar-powered wireless sensor networks

Proceedings of the 2nd International Symposium on Wireless Pervasive Computing (ISWPC '07)

February 2007

IEEE

53 58

10.1109/iswpc.2007.342573

2-s2.0-34548133253

14.

Piorno

J. R.

Bergonzini

Atienza

Rosing

T. S.

Prediction and management in energy harvested wireless sensor nodes

Proceedings of the 1st International Conference on Wireless Communication, Vehicular Technology, Information Theory and Aerospace & Electronic Systems Technology (Wireless VITAE '09)

May 2009

IEEE

6 10

10.1109/wirelessvitae.2009.5172412

2-s2.0-70350749765

15.

Moser

Thiele

Brunelli

Benini

Adaptive power management in energy harvesting systems

Proceedings of the Conference on Design, Automation and Test in Europe

April 2007

EDA Consortium

773 778

10.1109/date.2007.364689

2-s2.0-34548358779

16.

Cammarano

Petrioli

Spenza

Pro-energy: a novel energy prediction model for solar and wind energy-harvesting wireless sensor networks

Proceedings of the 9th IEEE International Conference on Mobile Ad-Hoc and Sensor Systems (MASS '12)

October 2012

IEEE

75 83

10.1109/mass.2012.6502504

2-s2.0-84877659567

17.

Voigt

Dunkels

Alonso

Ritter

Schiller

Solar-aware clustering in wireless sensor networks

Proceedings of the 9th International Symposium on Computers and Communications (ISCC '04)

July 2004

IEEE

238 243

2-s2.0-10844251086

18.

Heinzelman

W. R.

Chandrakasan

Balakrishnan

Energy-efficient communication protocol for wireless microsensor networks

Proceedings of the 33rd Annual Hawaii International Conference on System Sciences (HICSS '33)

January 2000

IEEE

2-s2.0-0033877788

10.1109/HICSS.2000.926982

19.

Zhang

Xiao

Tan

H.-P.

A preliminary study on lifetime maximization in clustered wireless sensor networks with energy harvesting nodes

Proceedings of the 8th International Conference on Information, Communications and Signal Processing (ICICS '11)

December 2011

IEEE

1 5

10.1109/icics.2011.6174242

2-s2.0-84860607644

20.

Zhang

Xiao

Tan

H.-P.

Clustering algorithms for maximizing the lifetime of wireless sensor networks with energy-harvesting sensors

Computer Networks 2013 57 14 2689 2704

10.1016/j.comnet.2013.06.003

2-s2.0-84883207594

21.

Gou

Yoo

A partition-based centralized LEACH algorithm for wireless sensor networks using solar energy

Proceedings of the International Conference on Convergence and Hybrid Information Technology (ICHIT '09)

August 2009

ACM

60 66

10.1145/1644993.1645004

2-s2.0-77954740186

22.

Jakobsen

M. K.

Madsen

Hansen

M. R.

Dehar: a distributed energy harvesting aware routing algorithm for ad-hoc multi-hop wireless sensor networks

Proceedings of the IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM '10)

June 2010

IEEE

1 9

10.1109/wowmom.2010.5534899

2-s2.0-77955898239

23.

Meng

Zhang

Dong

Lin

Adaptive energy-harvesting aware clustering routing protocol for wireless sensor networks

Proceedings of the 7th International ICST Conference on Communications and Networking in China (CHINACOM '12)

August 2012

742 747

10.1109/chinacom.2012.6417582

2-s2.0-84874282176

24.

Kim

Seok

Choi

Kwon

Optimal multi-sink positioning and energy-efficient routing in wireless sensor networks

Information Networking. Convergence in Broadband and Mobile Networking 2005 3391

Berlin, Germany

Springer

264 274 Lecture Notes in Computer Science

10.1007/978-3-540-30582-8_28

25.

Karp

Challenges in geographic routing: sparse networks, obstacles, and traffic provisioning

Proceedings of the DIMACS Workshop on Pervasive Networking

2001

26.

Melodia

Pompili

Akyildiz

I. F.

Optimal local topology knowledge for energy efficient geographical routing in sensor networks

Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '04)

March 2004

IEEE

1705 1716

2-s2.0-8344243738

27.

Krishnamachari

Estrin

Wicker

Modelling data-centric routing in wireless sensor networks

Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '02)

2002

39 44

28.

Yao

Gehrke

The cougar approach to in-network query processing in sensor networks

ACM SIGMOD Record 2002 31 3 9 18

10.1145/601858.601861

2-s2.0-1442296009

29.

Lindsey

Raghavendra

C. S.

PEGASIS: power-efficient gathering in sensor information systems

Proceedings of the IEEE Aerospace Conference

March 2002

IEEE

3-1125 3-1130

10.1109/aero.2002.1035242

2-s2.0-51949089156

30.

Braginsky

Estrin

Rumor routing algorithm for sensor networks

Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications

September 2002

ACM

22 31

2-s2.0-0036986248

Energy-Aware Hierarchical Topology Control for Wireless Sensor Networks with Energy-Harvesting Nodes

Abstract

1. Introduction

2. Background and Related Work

2.1. Energy-Harvesting Wireless Sensor Networks

2.2. Hierarchical Topology Control for WSNs with Energy-Harvesting Nodes

3. Layer-Based Topology Control with Energy-Harvesting Sensor Nodes

3.1. Review of Layer-Based Topology Control for Long-Term WSNs with Battery-Powered Nodes

3.2. The Layer Determination Algorithm

3.2.1. Operation of a Node

3.2.2. Topology Control Information for Layer and Target Determination

3.2.3. Layer Determination

Algorithm 1: Asynchronous layer determination.

Algorithm 2: Synchronous layer determination.

3.2.4. Estimated Lifetime of a Battery-Powered Node

Case 1 (target node t k = n m j ).

Case 2 ( t k = n m j + 1 and the hop-count of n m j + 1 , h m > h i ).

Case 3 (otherwise).

3.3. Introducing Energy-Harvesting Nodes to a Layered Topology

3.3.1. Energy Model for Energy-Harvesting Nodes

3.3.2. Determining the Layer of an Energy-Harvesting Node

4. Experimental Results

4.1. Simulation Environment

4.2. Simulation Results

5. Future Work

6. Conclusions

Footnotes

Notation Summary

Conflict of Interests

Acknowledgments

References

Case 1 (target node $t_{k} = n_{m}^{j}$ ).

Case 2 ( $t_{k} = n_{m}^{j + 1}$ and the hop-count of $n_{m}^{j + 1}, h_{m} > h_{i}$ ).