This is not the document you are looking for? Use the search form below to find more!

Report home > Technology

Wireless sensor network

0.00 (0 votes)
Document Description
This is about wireless sensor nodes charging
File Details
  • Added: January, 30th 2012
  • Reads: 187
  • Downloads: 0
  • File size: 706.35kb
  • Pages: 11
  • Tags: about charging, node replacement, node reclamation
  • content preview
Submitter
  • Username: rukshana
  • Name: rukshana
  • Documents: 1
Embed Code:
Comment is disabled by submitter.
Related Documents

Energy Management for Wireless Sensor Network Nodes

by: editor_ijaet, 7 pages

Wireless sensor networks consist of small, autonomous devices with wireless networking capabilities. In order to further increase the applicability in real world applications, minimizing energy ...

Building a Rural Wireless Mesh Network: A do-it-yourself guide to planning and building a Freifunk based mesh network

by: manualzon, 44 pages

Network and Network programming building wireless mesh network in rural Africa, without VSAT (satellite based internet network)

Industrial Wireless Sensor Networks Market - Global Forecast & Analysis (2012 – 2017)

by: marketreports, 2 pages

Industrial Wireless Sensor Networks research report classified the global IWSN market on the basis of components, IWSN technologies, industrial applications and geographical market; forecasting ...

Wearable Wireless Sensor Market-Global Industry Size,Trends,Analysis And Forecast 2011-2015: MarketResearchReports.biz

by: mrrbiz, 7 pages

TechNavio's analysts forecast the Global Wearable Wireless Sensor market to grow at a CAGR of 110 percent over the period 2011-2015. One of the key factors contributing to this market growth is the ...

Navigating a successful entry in residential lighting and building automation wireless sensor network markets.

by: donaldhood, 1 pages

(1888PressRelease) West Technology Research Solutions reports define market risk to entrants in residential lighting and energy harvesting building automation applications.

Mining and Supporting Community Structures in Sensor Network Research

by: khulood, 44 pages

Mining and supporting community structures in sensor network research Alberto Pepe (University of California at Los Angeles) Marko A. Rodriguez (Los Alamos National Laboratory) CENS Friday ...

On The Intruder Detection For Sinkhole Attack In Wireless Sensor Networks

by: florus, 23 pages

On the Intruder Detection for Sinkhole Attack in Wireless Sensor Networks Edith C. H. Ngai 1 , Jiangchuan Liu 2 , and Michael R. Lyu 1 1 Department of Computer…

SAIC, HP, GE and Others. Wireless Sensors Network Case.

by: suzuka, 18 pages

SAIC, HP, GE And OTHERS: The Business Case for Wireless Sensors Networks (Case Study) Page 214 Telecommunications And Networks Prepared by : Mohammad Faizan Khalid SAIC SAIC ...

Ieee 2010 - vebek virtual energy-based encryption and keying for wireless sensor networks

by: philippe, 2 pages

NCCT IEEE PROJECTS 2010-11 Promise for the Best Projects JAVA & .NET IEEE TRANSACTIONS ON MOBILE COMPUTING JULY 2010 (VOL. 9 NO. 7) ...

Content Preview
Prolonging Sensor Network Lifetime Through Wireless Charging
Yang Peng, Zi Li, Wensheng Zhang, and Daji Qiao
Iowa State University, Ames, IA, USA
Email: {yangpeng,zili,wzhang,daji}@iastate.edu
Abstract
As the wireless charging technology is being commer-
cialized [12], it has become a promising alternative to ad-
The emerging wireless charging technology is a promis-
dress the energy constraint problem in sensor networks.
ing alternative to address the power constraint problem
Different from energy harvesting technologies, the wire-
in sensor networks.
Comparing to existing approaches,
less charging technology, together with more and more ma-
this technology can replenish energy in a more control-
ture and inexpensive mobile robots, will make controllable
lable manner and does not require accurate location of or
power replenishment possible, with which power can be
physical alignment to sensor nodes. However, little work
replenished proactively to meet application requirements
has been reported on designing and implementing a wire-
rather than passively adapted to the availability of environ-
less charging system for sensor networks. In this paper,
mental resources. Comparing with sensor node or battery
we design such a system, build a proof-of-concept proto-
replacement approaches, the wireless charging technology
type, conduct experiments on the prototype to evaluate its
allows a mobile charger to transfer energy to sensor nodes
feasibility and performance in small-scale networks, and
wirelessly without requiring accurate localization of sensor
conduct extensive simulations to study its performance in
nodes or strict alignment between the charger and nodes.
large-scale networks. Experimental and simulation results
demonstrate that the proposed system can utilize the wire-
less charging technology effectively to prolong the network
In spite of the potential advantages of the wireless charg-
lifetime through delivering energy by a robot to where it is
ing technology, little work has been reported on designing
needed. The effects of various configuration and design pa-
and implementing a wireless charging system for sensor
rameters have also been studied, which may serve as useful
networks. In this work, we design such a system that con-
guidelines in actual deployment of the proposed system in
sists of (1) a mobile wireless power charger; (2) a network
practice.
of sensor nodes equipped with wireless power receivers;
and (3) an energy station that is responsible for monitor-
ing the energy status of sensor nodes, deciding the power
charging sequences to be executed by the mobile charger.
1
Introduction
We have built a proof-of-concept prototype of the system,
and conducted experiments on the prototype to evaluate its
Wireless sensor nodes are powered by small batteries,
feasibility and performance in small-scale networks. In ad-
and the limited energy supply has constrained the lifetime
dition, we have conducted extensive simulations to study
of a sensor network. This has been a long-lasting, fun-
the performance of the proposed system in large-scale net-
damental problem faced by sensor networks that are de-
works. Experimental and simulation results demonstrate
signed for long-term operation. Energy conservation [2, 8],
that the proposed system can utilize the wireless charging
environmental energy harvesting [3, 5, 6, 11], incremental
technology effectively to prolong the network lifetime. The
deployment, and battery replacement [17, 19] approaches
effects of the wireless charging efficiency, the routing algo-
have been proposed to address the problem. However, en-
rithm and various design parameters have also been studied,
ergy conservation schemes can only slow down energy con-
which may serve as useful guidelines in actual deployment
sumption but not compensate energy depletion. Harvest-
of the proposed system in practice.
ing environmental energy, such as solar [3, 6], wind [11],
vibration [5], is subject to their availability which is of-
ten uncontrollable by people. The incremental deployment
The rest of the paper is organized as follows. Section 2
approach may not be environmentally friendly because de-
presents the design and implementation of the proposed
serted nodes can pollute the environment. The battery or
system. Section 3 formulates the charging problem and
node replacement approach is applicable only for scenarios
presents the details of charging algorithms. Sections 4 and 5
that sensor nodes are accessible by people or sophisticated
report the experimental results obtained from the prototype
robots that can locate and physically touch the sensor nodes.
system, and the simulation results on large-scale networks,
respectively. Finally, Section 6 summarizes the related work
This work is supported partly by the NSF under Grant CNS-0831874.
and Section 7 concludes the paper.

2
System Design and Implementation
2.1
System Overview
As shown in Fig. 1, the proposed system has three main
components: a mobile charger (MC) - a mobile robot car-
rying a wireless power charger, a network of sensor nodes
equipped with wireless power receivers, and an energy sta-
tion that monitors the energy status of the network and di-
Figure 2: (a) the MC - an Acroname Garcia robot with
rects the MC to charge sensor nodes.
a Powercast charger; (b) TelosB motes with Powercast
Energy
receivers.
Station
Sink
Mote
of 5.8 to 9 V. The MC communicates with the energy station
(a PC in our experiments) via an IEEE 802.11b interface.
Mote
Mobile
Energy charging is carried out in the 903-927 MHz band
Charger
Mote
while sensor nodes communicate in the 2.4 GHz band.
When the MC is charging, its power consumption is 3 W.
Mote
The effective amount of power that can be captured by a
Mote
Mote
receiver varies with the distance between the receiver and
Routing Path
the MC. The relation is shown in Fig. 3, which is obtained
Travel path
from our field-test results. The antenna gain is 1.15 for both
Long Range
Radio
Mote
Mote
power charger and receiver. As shown in the figure, the
receiver can receive about 45 mW power when it is 10 cm
Figure 1: System overview.
away from the charger, meaning that the charging efficiency
The system works as follows. Sensor nodes perform ap-
is about 1.5%. As the distance increases, the charging effi-
plication tasks such as environment monitoring, generate
ciency decreases.
sensory data, and periodically report the data to the sink.
200
In addition, they also monitor the voltage readings of their
own batteries, estimate energy consumption rates, based on
which derive their own lifetime, and then report the infor-
150
mation to the sink periodically. When the energy informa-
tion is forwarded to the sink, it is aggregated en-route to
100
save communication overhead. Particularly, only the energy
information of the k shortest-lifetime nodes is forwarded
50
while the information of other nodes is dropped, where k
Power Received (mW)
is a system parameter. Upon receiving the energy informa-
tion, the sink forwards it to the energy station, which runs a
0 0 5 10 15 20
40
60
80
100
charging algorithm to process the information and plan the
Charger-Receiver Distance (cm)
charging activities, and then sends a command message to
Figure 3: Power captured by the receiver vs. charger-
the MC. The command includes the charging plan that the
receiver distance.
MC should execute. Once receiving the command, the MC
starts charging a selected set of sensor nodes sequentially
2.3
Software Components
according to the instruction. When the MC receives a new
command, it adjusts its charging activities accordingly.
The software components are developed based on
We have built a proof-of-concept prototype of the pro-
TinyOS 2.1 [16] and loaded to each sensor node in the net-
posed system. Its hardware and software components are
work. Fig. 4 shows the software architecture. The right side
described in the next two sections.
of the figure is the conventional framework in most sensor
networks, while the left side (shaded part) is our designed
2.2
Hardware Components
Power Management component, which is compatible to and
can be easily integrated with the conventional framework.
The Powercast wireless power charger and receiver [12]
The conventional framework adopts the component-
are used in our prototype system. As shown in Fig. 2,
based MAC layer architecture (MLA) [7].
The energy-
a Powercast charger is installed on an Acroname Garcia
efficient UPMA-XMAC [15] (a variation of X-MAC [1] in
robot [4] to become the MC, and each TelosB sensor is
TinyOS) is used as the MAC protocol.
The routing layer
equipped with a Powercast receiver. When the Garcia robot
uses the GPSR protocol. We implement a new Power Man-
moves at 1 m/s (used in our experiments), its power con-
agement (PM) component to monitor energy levels and con-
sumption is about 8 W and the voltage level is in the range
sumption rates of individual sensor nodes and report such

Application
PMConfig
PMInfo
StdControl
most recent energy information about its own and its
Power Management (PM)
Receive
Send
LPL
descendent nodes on the routing tree, and periodically
Aggregation
Query
(Intercept)
Insert
Core
Management
Receive
generates an aggregated report to send to its parent
(Intercept)
Update
Receive
Send
Send
Routing Receive
node. Particularly, the aggregated report only contains
(Intercept)
(Intercept)
Lifetime
Query
Estimation
Send
the energy information about the k shortest-lifetime
Routing
Forwarding
Monitor Update
nodes known to this module.
Energy
Send
Receive
Monitoring
Send
*
Read
Receive
The core module processes intercepted report mes-
DataReady
Read
MAC
sages, triggers the aggregation management module to
DataReady
Send
Receive
ADC
generate aggregated energy information reports, and
Radio Core
updates the settings of the PM based on user's request.
Figure 4: Software overview where the shaded part is
the new Power Management component implemented in
3
The Charging Problem and Algorithms
our system.
As mentioned in the previous section, based on the col-
information to the energy station. The design goals of the
lected energy information, the energy station runs a charg-
PM component are to achieve (1) low communication and
ing algorithm to plan the charging activities for the MC, i.e.,
memory overheads; (2) easy integration with the conven-
to determine the sequence of nodes to be charged and the
tional framework; and (3) efficient collection of accurate
amount of energy to be charged to each node. In this sec-
network-wide energy information. To integrate with the
tion, we formally state the charging problem that the energy
conventional framework, the PM only requires simple inter-
station tries to solve (which is NP-complete) and present
facing with the application, routing and ADC components:
two heuristic charging algorithms to address the issue.
* After the system is booted up, the application compo-
3.1
Formulation of the Charging Problem
nent needs to enable the functionality of the PM.
* The PM is allocated a collection message ID for rout-
Suppose Graph G = (V, E) represents the topology of a
ing the energy report message to the energy station.
static sensor network, where each vertex stands for a sensor
node and the length of an edge stands for the distance be-
* The PM intercepts forwarded energy report messages
tween the nodes connected by it. Suppose all sensor nodes
through the intercept interface provided by the routing
have the same battery capacity Es. In other words, the total
layer.
amount of energy that can be stored in a sensor node's bat-
*
tery is E
The PM uses a read interface to connect to the ADC
s. For each sensor node i (i V ), let ei and cri
denote its residual energy and energy consumption rate, re-
component to monitor battery voltage level.
spectively. There is a mobile charger (MC) in the network
In order to adaptively tune the functionality of the PM for
and its distance to each sensor node is known. The MC
various application scenarios, two additional interfaces are
carries a battery of capacity Ec. When the MC charges a
provided to the application component: the PMConfig in-
sensor node, it consume c power while the power received
terface provides commands to configure energy information
by the sensor node is c where is called the charging
report interval, energy consumption estimation model, and
efficiency. The MC moves at the speed of v and the power
low energy alarm threshold; the PMInfo interface provides
consumption for its movement is m.
commands to query current energy level, consumption rate
We study a particular charging problem whose goal is
and estimated lifetime.
to find an optimal charging sequence for the MC, denoted
Internally, the PM has the following modules:
as S = (n1, ct1), * * * , (n|S|, ct|S|) , where nj, ctj (j =
1, * * * , |S|) represents that node nj is charged in the jth step
* The energy monitoring module samples the battery
for a period of ctj time, such that the network lifetime is
voltage reading at a user-defined interval.
maximized. Here, the network lifetime refers to the time
*
when the first sensor node in the network uses up its energy.
The lifetime estimation module estimates the energy
Table 1 summarizes the notations used in the formulation of
consumption rate and derives lifetime of a node based
the charging problem.
the energy information obtained from the energy mon-
itoring module. Users are allowed to select the estima-
3.2
NP-Completeness
of
the
Charging
tion model. The simple moving average (SMA) and the
Problem
exponential moving average (EMA) models are imple-
mented, yet new estimation models customized to spe-
cific battery characteristics (e.g., pure ultra capacitor
By reducing the NP-Complete Traveling Salesman Prob-
energy source) can be added.
lem (TSP) to the above charging problem, we can prove that
the charging problem is also NP-Complete. The decision
* The aggregation management module is responsible
versions of the charging problem and the TSP problem are
for aggregating the energy information. It records the
as follows.

Table 1: Notations Used in the Charging Problem For-
reached. With this charging sequence, the lifetime of each
mulation
node is extended by at least c1 = |V |. Since the sum
cri
notation
meaning
of the MC's moving time ( D = D) and the total charging
v
time (1 |V | = |V |) is equal to the initial nodal lifetime
cri
energy consumption rate of sensor node i
( ei = D + |V |), we know that the network can survive for
e
cri
i
residual energy of sensor node i
at least T = D + 2 |V | time with the charging sequence.
Es
battery capacity of a sensor node
Hence, the above instance of the charging problem also has
Ec
battery capacity of the MC
a positive answer.
c
the MC's charging power consumption
Step II: Conversely, if there is a charging sequence that

the MC's charging efficiency
extends the network lifetime to T = D + 2 |V |, each

node must be charged for at least one time unit since the
m
the MC's moving power consumption
v
the MC's moving speed
initial nodal lifetime is only D + |V |. This means that each
node must be visited at least once. Excluding the charging
energy consumption, the MC has at most Ec -c 1|V | =
*

Decision version of the charging problem: Given a net-
m D energy for moving, which can be used to traverse
a distance of at most D. Therefore, there exists a tour that
work G = (V, E), the sensor node behavior (charac-
visits every node and the length of the tour is at most D.
terized by Es, ei and cri), and the MC behavior (char-
As the TSP is a well-known NP-complete problem, the
acterized by Ec, c, m, v and ), the question is
charging problem is also NP-complete.
whether there exists a charging sequence S with which
the network lifetime can reach at least T .
3.3
Heuristic Charging Algorithms
* Decision version of the TSP problem: Given a network
G = (V , E ), the question is whether there exists a
In this section, we present two heuristic algorithms to ad-
visiting sequence (i.e., tour) that covers all nodes in V
dress the difficult charging problem. As the lifetime of the
and has a length of at most D.
network is the same as the lifetime of the first sensor node
Theorem 3.1. The decision version of the charging prob-
that uses up its battery energy, a naive algorithm is to always
lem is NP-complete.
charge the node with the shortest lifetime to its battery ca-
pacity. Unfortunately, this may cause the MC to move back
Proof. (sketch) Firstly, given a charging sequence S, we
and forth between nodes, which could incur large move-
can verify whether the network lifetime can reach T with S
ment overhead. The proposed greedy and greedyPlus charg-
by simulating each charging operation. This takes O(|S|)
ing algorithms aim to reduce the movement overhead.
steps. Therefore, the charging problem belongs to NP.
Next, we show that any instance of TSP can be reduced
3.3.1
Greedy Algorithm
to an instance of the charging problem. Letting G =
(V , E ), D be an arbitrary instance of TSP, an instance of
The greedy algorithm is designed to find a charging se-
the charging problem G, Es, ei, cri, Ec, c, m, v, can
quence with which the lifetime of the network can be pro-
be constructed as follows:1
longed as much as possible while incurring less movement
than the naive algorithm. It works as follows. All sensor
* G = G , cri = , ei = (D + |V |) , Es = ei + c;
nodes are sorted according to the lifetime in the ascend-
*
ing order. Let us denote the sorted list that contains the
= 1, m = 1, v = 1, c = |V | , Ec = m D +
k shortest-lifetime nodes as (n

1, l1), * * * , (nk, lk) , where
c |V |;
(ni, li) represents node ni with a lifetime of li if it is not
* T = D + 2 |V |.
being charged, and li li+1 (1 i k - 1). Clearly,
l1 is the network lifetime if there is no charging. Then, as
Here, is a small positive value. The following two steps
shown in Algorithm 1, a charging sequence can be found in
show that these two instances are equivalent.
the following manner:
Step I: Suppose there is a tour n1, n2, * * * , nm (ni
V
*
), which covers all node in V and has a length of at most
Loop 1: The algorithm tries to extend the network life-
D, for the above TSP instance. Then, a charging sequence
time from l1 towards l2. In other words, the target net-
S = (n
work lifetime is set to l2, and if a feasible charging se-
1, 1), * * * , (nm, 1) , where node ni is charged in
quence can be found (i.e., without violating the battery
the ith step for one time unit, can be constructed for the
capacity of a sensor node, or depleting the battery en-
above instance of the charging problem. The charging op-
ergy of the MC in the mid of the sequence) to charge
eration is valid due to the facts that (1) the MC's energy
node n
capacity E
1 so that the network lifetime is extended be-
c is large enough to support the moving and
yond l
charging operations; and (2) each node can be charged for
1, the algorithm continues to Loop 2; otherwise,
it halts. In this algorithm, the charging behavior of
one time unit before the capacity ceiling of its battery is
the MC is greedy in the sense that, once the MC starts
1In both instances, the salesman and the MC start from the same posi-
charging a sensor node, it keeps charging the node for
tion.
as long time as possible.

* Loop j (2 j k): The algorithm tries to extend
At the end of the above procedure, among all the found
the network lifetime from l1 towards lj+1. Similarly,
feasible charging sequences, the one that extends the net-
if a feasible charging sequence can be found to charge
work lifetime the most is selected by the algorithm. The
nodes n1, n2, * * * , nj so that the network lifetime is
complexity of this algorithm is O(k2k!). Simulation results
extended beyond l1, the algorithm continues to the next
show that the algorithm can prolong the network lifetime
loop; otherwise, it halts.
effectively with a relatively small k, e.g., k = 5, while the
performance improvement by increasing k further is not sig-
nificant. Therefore, the greedy algorithm is simple to imple-
Algorithm 1 The Greedy Algorithm
ment and effective in practice. Note that when k = 0, the
Input:
greedy algorithm reduces to the special case when there is
*
no charging in the network, while when k = 1, the greedy
P : position of the MC
algorithm is equivalent to the naive algorithm.
* : remaining energy in the MC's battery
One potential issue with the greedy algorithm is that the
* (n
greedy nature of the algorithm (i.e., the MC keeps charg-
1, l1), * * * , (nk, lk) :
list of k shortest-lifetime nodes
sorted in the ascending order of their lifetime
ing a sensor node for as long time as possible once started)
may degrade the system performance under certain circum-
* G = (V, E), Es, c, m, v, , cri (i = 1, * * * , k): other
stances. Fig. 5 illustrates an example scenario when the
system parameters
greedy algorithm does not perform well. In this example,
Output: a charging sequence
at time 0, sensor nodes n1, n2 and n3 have the residual en-
1: S
/* the best charging sequence found so far */
ergy of 1800 J, 1800 J and 7200 J, respectively, and they
2: L l
have the same energy consumption rate of 0.01 J/s. The
1
/* network lifetime achieved with S */
3: for j = 1 to k do
battery capacity of a sensor node and the MC is 10000 J
and 270000 J, respectively. Suppose k = 3,
4:
if j = k then
c = 3 W,
= 0.02, and the MC movement cost and delay are negli-
5:
T
Es
/* target network lifetime */
max1ij cri
gible (i.e., c = 0 W, v = ).
6:
else if lj = lj+1 then
7:
continue
n1
8:
else
n2
0
0
K
)
0
0
0
n3
9:
T l
2
7
0
0
j+1
/* target network lifetime */
7

(
J
2
3
3
MC
y
6
6
10:
for each permutation of n1, * * * , nj : n1, * * * , nj do
r
g
e
n
0
0
11:
(P , , en , * * * , en ) (P, , en , * * * , en )
l

E
0
0
0
0
1
j
1
j
a
4
4
u
0 0
5
8
5
8
12:
S , L 0
i
d
s
1 1
0
e
0
9
13:
for w = 1 to j do
R
0
0
0
0
25
50
Time (h)
14:
ChargeTime (T - lw) x crn
[ x c]
Charge n1
w
/* time needed to charge nw to extend lifetime to T */
(a)
n1
15:
NodeCapTime E
0
K
K
s - en
[ x c]
0
0
0
5
n2
w
)
2
7
5
0
3
7
0
n
/* time needed to charge n
2
7
1
3
3
w to full battery capacity

(
J
6
y
6
MC
*/
r
g
0
e
5
0
0
n
0
0
0
0
4
6
6
5
16:
MCCapTime

l

E
3
3
1
0 0
a
3
0 0
u
0
8 8
5
- distance(P , n
i
d
1 1
3
1
w ) x m/v
c
s
e
R
0
0 0
0
/* maximum time that can be spent to move to and
0
12.5
25
125
Charge n
Time (h)
1
Charge n2
charge nw with the remaining energy at the MC */
(b)
en
,n )
17:
DeadTime
min
x
- distance(nw x
cr
v
Figure 5: An example to illustrate that the greedy algo-
w+1xj
nx
/* maximum time that can be spent to charge n
rithm could be improved further: (a) network lifetime is
w s.t.
no other node dies before the MC can charge it */
50 hours with the greedy algorithm; (b) network lifetime
18:
tw min(ChargeTime, NodeCapTime, MCCapTime, DeadTime)
is 125 hours with more balanced charging.
/* tw is the actual time that the MC will charge nw */
19:
if t
As shown in Fig. 5(a), with the greedy algorithm, the
w < 0 then
20:
break
MC starts charging n1 at time 0 and continues to time 25
21:
Update P , , e
hours when the residual energy of n1 becomes the same as
n , * * * , en
1
j
that of n3 (hence they have the same lifetime as they have
22:
(nw, tw) is appended to S
the same energy consumption rate). This action causes the
23:
L is computed for the charging sequence S
MC to use up all of its battery energy. As a result, the net-
24:
if L > L then
work lifetime is 50 hours when the residual energy of n2
25:
S S, L L
becomes zero. In comparison, if the MC takes a less greedy
26:
if (no better charging sequence found in this iteration) then
approach that charges n1 for 12.5 hours and then charges n2
27:
return S
for 12.5 hours, as shown in Fig. 5(b), the network can sur-
28: return S
vive much longer for 125 hours in total, resulting in a 250%

performance improvement. Motivated by this observation,
1
2
3
4
5
6
7
8
9
we revise the greedy algorithm to allow the MC to charge
sensor nodes in a more balanced manner. The revised algo-
1
2
3
rithm is named the greedyPlus algorithm.
4
5
6
3.3.2
GreedyPlus Algorithm
7
8
9
In the greedy algorithm, the MC tends to charge a node in
a greedy manner towards the target lifetime T without con-
Figure 7: Experimental topologies.
sidering whether the lifetime of other nodes can also be ex-
tended to T . In fact, as long as one node cannot have its
lifetime extended to T , the network lifetime cannot reach
Before each experiment, the batteries on each node are
T , meaning that some of the energy being charged to the
pre-charged to a certain voltage level up to 2.9 V (normal-
current node may be wasted. The greedyPlus algorithm im-
ized to energy level 100% in the following figures), and the
proves upon the greedy algorithm by applying binary search
energy of a mote is assumed to be depleted when the voltage
to find a more suitable target network lifetime at each loop,
level of its batteries drops to 2.7 V (normalized to energy
which is a target achievable by all sensor nodes in the net-
level 0% in the following figures).
work. Fig. 6 shows the flowchart of the greedyPlus algo-
During the experiments, each sensor node sends out a
rithm, which is based on the pseudo-code of the greedy al-
data packet every 16 20 seconds and an energy report ev-
gorithm in Algorithm 1. In the flowchart,
is a small quan-
ery 10 minutes. The UPMA-XMAC protocol running on
tity to help define exit conditions for the greedyPlus algo-
each sensor node sets its low power listening interval to
rithm.
2 seconds. Every 10 minutes, the energy station runs the
charging algorithm to adjust the charging plan.
Line 9 in Algorithm 1
lmax = T
4.2
Evaluation Results
lmin = lj
lmin = T
lmax = T
T = (lmin + lmax) / 2
T = (lmin + lmax) / 2
Fig. 8 and Fig. 9 show the evaluation results for the line
and grid topologies, respectively. We measure (1) the initial
Is there a charging sequence S to
extend network lifetime to T ?
energy level of individual nodes; (2) the lifetime of the net-
(Lines 10-22 in Algorithm 1)
No
Yes
No
No
work and individual nodes when there is no energy charging
(tagged as no charge in the figures) and when the greedy-
Plus algorithm is used; and (3) the distribution of charging
T lmax - ?
T lmin + ?
time among individual nodes.
Yes
Record S, T
Yes
4.2.1
Evaluation Results for Line Topology
Line 23 in Algorithm 1
As shown in Fig. 8(b), the greedyPlus algorithm signifi-
Figure 6: GreedyPlus algorithm Flowchart.
cantly improves the network lifetime from 8.3 hours to 15.3
hours, an increase of 84%. This is accomplished by charg-
ing more energy to nodes that have shorter lifetime if there
4
Experiments
were no charging. Particularly, nodes 2, 3 and 4 have higher
energy consumption rates than other nodes because they
Experiments have been performed on the prototype sys-
forward more data packets; node 6 has low energy level at
tem to evaluate its feasibility and performance.
the beginning of the experiment. Hence, these nodes have
shorter lifetime than others when there is no charging. Their
4.1
Experimental Setup
lifetime (especially the lifetime of node 2) becomes the bot-
tleneck of the network lifetime. As shown in Fig. 8(c), the
Nine Telosb sensor nodes are used in the experiments.
greedyPlus algorithm charges more energy to these nodes to
Each node is powered by two 1.5V 2000mAh Alkaline
extend their lifetime and consequently improve the network
rechargeable batteries. The power receiver in the node can
lifetime.
charge the batteries when it receives energy from the MC,
and the charger-receiver distance varies from 5cm to 20cm.
4.2.2
Evaluation Results for Grid Topology
The sensor nodes are deployed in the line or grid topol-
ogy as shown in Fig. 7, where neighboring nodes are two
For the grid topology, as shown in Fig. 9(b), the greedyPlus
meters apart and the CC2420 radio transmission power is
algorithm improves the network lifetime from 7.2 hours to
set to level 3 which results in a communication range of
15.92 hours, an increase of 120%. Nodes 2, 4 and 6 are
about 3.5 meters. In both topologies, node 1 works as the
charged the most as they have a higher energy consump-
sink connected to a PC with stable power supply and there-
tion rate or a lower initial energy level. Node 5 is seldom
fore it does not need to be charged.
charged due to its high initial energy level and node 7 is

100
no charge
100
no charge
greedyPlus
greedyPlus
75
75
50
50
25
25
Energy Level (%)
Energy Level (%)
0
0
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
Node ID
Node ID
(a) Initial energy of individual nodes.
(a) Initial energy of individual nodes.
Node Lifetime (no charge)
Node Lifetime (no charge)
Node Lifetime (greedyPlus)
Node Lifetime (greedyPlus)
Network Lifetime (no charge)
Network Lifetime (no charge)
Network Lifetime (greedyPlus)
20
20
Network Lifetime (greedyPlus)
15
(h)
15
(h)
10
10
5
5
0
0
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
Node ID
Node ID
(b) Lifetime of the network and individual nodes.
(b) Lifetime of the network and individual nodes.
3.5
6
3
5
2.5
4
2
(h)
3
(h)
1.5
2
1
0.5
1
0
0
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
Node ID
Node ID
(c) Distribution of charging time among sensor nodes.
(c) Distribution of charging time among sensor nodes.
Figure 8: Evaluation results for line topology.
Figure 9: Evaluation results for grid topology.
seldom charged for its being a leaf node with low energy
Fig. 10(a) displays a charging trace in one experiment.
consumption rate. Also being leaf nodes, nodes 8 and 9
Corresponding to this charging trace, Fig. 10(b) demon-
however receive more charging than node 7 because they
strates the changes of node 2's voltage readings. Fig. 10(c)
have less initial energy than node 7.
shows the changes of node 2's voltage readings when there
is no charging. It can be observed in Fig. 10(b) that, when
node 2 is being charged (e.g., during time 25289 26516
4.2.3
Summary
seconds), its voltage reading increases very fast. However,
The evaluation results have demonstrated that, in a sensor
the fast increase is "false" and not stable because, as also
network where motes run on different initial energy sup-
shown in Fig. 10(b), immediately after the charging phase
plies and heterogeneous consumption rates, the proposed
ends (e.g., during time 26516 30491 seconds), the volt-
wireless charging system can improve the network life-
age reading drops much more rapidly than the normal case
time through accurately identifying the bottleneck nodes
shown in Fig. 10(c).
and charging them to extend their lifetime.
If such instant measurements of energy levels are used
directly as the input to the charging algorithm, the algorithm
may output less efficient charging decisions. Specifically, a
4.3
Discussion
measured fast but false increase of energy level may mis-
lead the algorithm to believe that the currently charged node
The experiments not only verify the feasibility and ef-
has been charged with sufficient amount of energy and de-
fectiveness of our proposed design, but also demonstrate
cide to charge another node; but immediately after the MC
some phenomena that are hard to discover through theoret-
leaves, the fast drop of energy level will be measured, which
ical derivations or simulations. Such discovery is helpful in
may force the charging algorithm to schedule the MC back
enhancing our design and making it more effective in prac-
to charge the node again. The back-and-forth scheduling
tice. As an example, we present in the following the phe-
of the MC can waste energy and hence degrade the perfor-
nomenon of abnormal voltage level reading which happens
mance of the charging system.
during and immediately after a node being charged. We
To address this issue, in our design and implementation,
also analyze its effects on the charging performance, and
when a node is being charged, its energy level that is just
describe our solution to address the issue.
measured is not used directly as the input to the charging

which reports data packets to the sink at the rate of . It
9
8
also sends one energy report every hour; hence, the energy
7
station runs the charging algorithm once every hour.
6
5
The routing algorithm adopted in the simulations uses
4
Node ID
3
metric Ci = T ri u1- ei
Es [9] to select routes. In the metric,
2
u is a system parameter, ei is node i's residual energy and
0
10000
20000
30000
40000
50000
60000
T ri is the sum of energy consumption for packet transmis-
Time (seconds)
sion and reception at node i. This metric is a combination
(a) Charging trace.
of the minimum energy (T rij) and max-min residual energy
(u1- ei
Es ) metrics. When u = 1, the metric is reduced to the
100
greedyPlus
minimum energy (ME) metric which is used to find the path
80
that can minimize the network-wide energy consumption;
26516
60
when u > 1, it is reduced to an energy-aware (EA) metric
that aims to balance energy consumption among all nodes
40
in the network. We let u = 1 or u = 100 in the simulations.
20
Energy Level (%)
Table 2 lists other default simulation parameters.
25289
30491
0 0
10000
20000
30000
40000
50000
60000
Table 2: Default Simulation Parameters
Time (seconds)
(b) Node 2's energy variation with charging trace in Fig. 10(a): its
parameter
value
voltage reading increases fast when being charged and drops fast
communication range of a sensor node(m)
70
immediately after charging completes.
battery capacity of a sensor node: Es (KJ)
10
battery capacity of MC: Ec (KJ)
2000
100
no charge
data packet generation rate: (packets/hour)
12
80
the MC's charging power consumption: c (W)
3
60
the MC's moving power consumption: m (W)
50
40
the MC's moving speed (m/s)
1
20
Energy Level (%)
the sensor's tx power consumption (J/packet)
0.05
0
the sensor's rx power consumption (J/packet)
0.06
0
10000
20000
30000
40000
50000
60000
Time (seconds)
system parameter k
5
(c) Node 2's energy variation without Charging.
the MC's charging efficiency: (%)
1.5
the number of sinks
4
Figure 10: Abnormal voltage reading during and imme-
the routing metric
ME
diately after a node being charged.
algorithm. Instead, its energy levels measured during a cer-
5.2
Simulation Results
tain recent time frame (e.g., the past 10 minutes) are aver-
aged and then scaled down by another certain constant (e.g.,
We measure the network lifetime of the naive, greedy
100) to remove the abnormally sharp increase of its voltage
and greedyPlus algorithms under different situations by
reading during the charging time. According to the exper-
varying the number of sinks, the system parameter k and
iments, the benefit brought by this averaging and scaling
the charging efficiency .
technique is significant. Particularly, the average improve-
ment of network lifetime is about 84% and 120% for the
5.2.1
Network lifetime with varying number of sinks
line and grid topologies respectively when the technique is
adopted, while the improvement is only about 40% if the
We first measure the lifetime when the number of sinks
technique is not used.
changes. If there are n sinks, the whole network field is di-
vided evenly into n areas and one sink is placed at the center
5
Simulations
of each area. Fig. 11(a) shows that all three algorithms can
significantly improve the network lifetime (by at least 80%)
regardless of the number of sinks. Among these algorithms,
Extensive simulations have been conducted to evaluate
the greedy and greedyPlus algorithms outperform the naive
the proposed system in large-scale networks.
one as they can significantly reduce energy consumption on
MC's movement, which is demonstrated in Fig. 11(b), and
5.1
Simulation Setup
therefore can use more energy to charge sensor nodes.
It is also found that, as the number of sinks increases, less
The proposed system is simulated in a custom simulator.
improvement of network lifetime is achieved by the charg-
In the simulations, 100 nodes are randomly deployed in a
ing algorithms. Particularly, the greedyPlus algorithm ex-
500 m x 500 m field. Every sensor node is a data source
tends the network lifetime by 117% when there is one sink,

3000
no charge
no charge
naive
naive
2500
greedy
greedy
greedyPlus
greedyPlus
2000
1200
(h) 1500
(h) 800
1000
500
400
0
1
4
9
Number of Sinks
k=3
k=5
k=7
k=10
(a) Network lifetime.
(a) Network lifetime.
1000
naive
naive
greedy
greedy
greedyPlus
greedyPlus
800
1000
600
800
400
(KJoule)
600
(KJoule)
400
200
200
0
1
4
9
Number of Sinks
k=3
k=5
k=7
k=10
(b) Energy consumed by MC movement.
(b) Energy consumed by MC movement.
Figure 11: Effects of the number of sinks.
Figure 12: Effects of system parameter k.
but the ratio drops to 88% when there are 9 sinks. This
the benefit brought by increasing k is not significant and the
is due to the following reasons. The energy consumption
benefit decreases as k gets large. In the simulations, we let
rates of different sensor nodes become more even as the
k = 5 by default.
number of sinks increases. With the increase, more sen-
sor nodes need to be charged to extend the network life-
time. As the MC's charging capacity and efficiency are
bounded, increasing the number of charged sensor nodes
5.2.3
Network lifetime with varying
decreases the amount of energy charged to each of these
nodes. Consequently, the overall improvement in network
Due to the relatively low value of (i.e., 1.5%) in previous
lifetime decreases. The improvement of network lifetime is
simulations, even when all of E
further reduced because the MC has to consume more en-
c = 2000 KJ energy is used
by the MC for charging, only 30 KJ can be received by sen-
ergy in movement as it needs to charge more nodes, which
sor nodes. Hence, the charging efficiency has been a major
decreases the amount of energy that can be used for charg-
constraint on improving the network lifetime. Fig. 13 shows
ing sensor nodes. The phenomenon indicates that, the less
that the network lifetime can be significantly increased as
even are the energy consumption rates among sensor nodes,
increases. Particularly, the greedyPlus algorithm can extend
the fewer sensor nodes need to be charged and the better
the network lifetime by about 100% with = 1.5% and the
performance can be achieved by the charging algorithms.
extension ratio rises to 200% when = 6%.
5.2.2
Network lifetime with varying k
2000
no charge
naive
greedy
1500
greedyPlus
The network lifetime extended by the greedy and greedy-
Plus algorithms does not increase linearly or significantly as
1000
(h)
k increases. This phenomenon is attributed to the following
500
reasons. If the number of bottleneck nodes that constrain
the network lifetime is less than k, increasing k does not
0
0.75
1.5
3
6
improve the network lifetime as only the energy informa-
Efficiency (%)
tion about bottleneck nodes is useful for charging planning.
If the number of bottleneck nodes is larger than k, the in-
Figure 13: Effects of charging efficiency .
formation of all the bottleneck nodes can still be gradually
obtained and considered by the charging algorithms as the
The charging efficiency can be increased through ad-
algorithms are run once every certain time interval and each
vance in charging technology. In fact, it can be increased
running of the algorithm is based on the energy informa-
through delicate sensor node deployment such as the aggre-
tion of the k shortest-lifetime sensor nodes at the moment.
gated sensor node deployment strategy proposed by Tong et
As shown in Fig. 12(b), a larger k does help in reducing
al. [18]. Thus, when combined with the aggregated node
the movement energy consumption as the information of
deployment strategy, the performance of the proposed wire-
more nodes is considered in charging planning. However,
less charging system may be improved further.

5.2.4
Energy-efficient Routing vs.
Energy-balanced
5.2.5
Network lifetime with varying
Routing
Fig. 15 demonstrates how much the network lifetime can
be improved by the greedyPlus algorithm, as the date rate
When using the ME metric, the routing algorithm adopted
() varies. When is small (e.g., < 48 packets per
in the simulations becomes an energy-efficient algorithm as
hour), the lifetime improvement is over 100% for both
it tends to find routes that consume the least total energy.
E
When using the EA metric, the routing algorithm becomes
c = 20000K J and Ec = 2000K J .
However, the im-
provement ratio decreases as increases. This is due to the
an energy-balanced algorithm as it tends to find routes that
fact that the charging capability of the MC is determined by
distribute communication workload among all sensor nodes

as evenly as possible. In a non-rechargeable network, the
c (the maximal amount of energy that can be actually
charged to the network per unit of time) and E
energy-balanced routing algorithm outperforms the energy-
c (the to-
tal amount of energy carried by the MC). When is small,
efficient algorithm in terms of network lifetime, but this

may not be always true when sensor nodes can be charged.
c is large enough to keep the network alive before the
Extensive simulations have been conducted to study which
MC runs out of its energy at time Ec . Hence, E

c becomes
c
of these two types of algorithms is more beneficial to our
the major factor that determines the improvement of net-
proposed system.
work lifetime, and a larger Ec brings more improvement
in network lifetime. On the other hand, when is large,
c becomes the major factor that determines the im-
6000
2000
provement of network lifetime, as some bottleneck nodes
1800
5000
may die much earlier before the MC runs out of its energy.
1600
4000
In this case, increasing Ec does not help in prolonging the
(h)
1400
(h)
3000
network lifetime.
1200
2000
1000
energy aware routing
energy aware routing
minimum energy routing
minimum energy routing
800
1000
0.75 1.5 2.25 3 3.75 4.5 5.25 6
0.75 1.5 2.25 3 3.75 4.5 5.25 6
350
E =2000KJ
c
Efficiency (%)
Efficiency (%)
300
E =20000KJ
c
(a) Ec = 2000 KJ.
(b) Ec = 20000 KJ.
250
Figure 14: Effects of the routing algorithm.
200
150
In our simulations, Ec (the total amount of energy car-
100
ried by the MC) and vary, the greedyPlus algorithm is run,
50
and the achieved network lifetime is measured. The results
Lifetime Improvement (%)
are shown in Fig. 14. As shown in the figure, the energy-
0
6
12 24
48
96
192
balanced algorithm (EA) outperforms the energy-efficient
Data Rate (packets/hour)
algorithm (ME) when Ec or is small; however, ME out-
performs EA when both E
Figure 15:
Effects of on the performance of the
c and are large. The reasons
behind the phenomena are as follows.
greedyPlus algorithm.
When the ME routing algorithm is used, nodes that are
on multiple routing paths have higher communication over-
head and thus become bottleneck nodes. When or Ec is
5.2.6
Summary
small, some of these bottleneck nodes cannot be recharged
in a timely manner before their energy is used up though
To summarize, we have the following observations from
some other nodes may still have lots of energy left, which
simulation results:
results in a short network lifetime. On the other hand, the
* Wireless charging is effective in prolonging the net-
EA routing algorithm tends to balance the energy consump-
work lifetime.
tion among nodes. With EA, the energy consumption rates
of bottleneck nodes typically are lower than the bottleneck
* Through careful movement planning, the proposed
nodes in the network running ME, and hence their life-
greedy and greedyPlus algorithms consume less en-
time is also longer. Therefore, the network running EA can
ergy for movement and thus have more energy for
achieve a longer lifetime.
charging to extend the network lifetime. Though these
When Ec and are large, bottleneck nodes in the net-
algorithms have a complexity exponential with system
work running ME are likely to be charged promptly. Hence,
parameter k, a small k can generate decent results.
the charging algorithm can effectively balance the lifetime
Hence, these algorithms are practically efficient.
between bottleneck and non-bottleneck nodes as the EA
routing algorithm does. Moreover, the ME algorithm con-
* The improvement of the network lifetime becomes
sumes less network-wide energy than the EA algorithm.
more significant as the charging efficiency increases.
Resulted from these two effects, the network running ME
This observation is encouraging as the charging ef-
can achieve longer lifetime than the one running EA.
ficiency can be improved through not only advance

Download
Wireless sensor network

 

 

Your download will begin in a moment.
If it doesn't, click here to try again.

Share Wireless sensor network to:

Insert your wordpress URL:

example:

http://myblog.wordpress.com/
or
http://myblog.com/

Share Wireless sensor network as:

From:

To:

Share Wireless sensor network.

Enter two words as shown below. If you cannot read the words, click the refresh icon.

loading

Share Wireless sensor network as:

Copy html code above and paste to your web page.

loading