6. EVALUATION
The approaches described in this paper are useful if they can
be efficiently implemented and improve the energy-efficiency of
distributed systems such as sensor nets. In Section 5 we described
several applications that employ these techniques. In this section,
we measure the benefits of aggregation and nested queries and
verify raw matching performance.
6.1 Aggregation benefits
In Section 5.1, we argued that it is relatively easy to build sensor
network applications using attribute-based naming, and innetwork
filters. In earlier work, we have observed that in-network
aggregation is important to the performance of data diffusion [23].
In this section, we validate these results with an actual implementation
of a simple surveillance application using attribute-based
names and filters.
We examined in-network aggregation in our testbed of 14 PC/104
sensor nodes distributed on two floors of ISI (Figure 7). These sensors
are connected by Radiometrix RPC modems (off-the-shelf,
418 MHz, packet-based radios that provide about 13kb/s throughput)
with 10dB attenuators on the antennas to allow multi-hop
communications in our relatively confined space. The exact topology
varies depending on the level of RF activity, and the network
is typically 5 hops across.
To evaluate the effect of aggregation we placed a sink on one
side of the topology (“D” at node 28) and then placed data sources
on the other side (“S” at nodes 25, 16, 22, and 13), typically 4 hops
apart. All sources generate events representing the detection of
Figure 7: Node positions in our sensor testbed. Light nodes
(11, 13, 16) are on the 10th floor; the remaining dark nodes
are on the 11th floor. Radio range varies greatly depending on
node position, but the longest stable link was between nodes 20
and 25.
some object at the rate of one event every 6 seconds. For experiment
repeatability events are artificially generated, rather than
taken from a physical sensor and signal processing. Each event
generates a 112 bytes message and is given sequence numbers
that are synchronized at experiment start.2 All nodes were configured
with aggregation filters that pass the first unique event and
suppress subsequent events with identical sequence numbers. Although
this scenario abstracts some details of a complete sensor
network (for example, real signal processing may have different
sensing delays), we believe it captures the essence of the networking
component of multi-sensor aggregation.
We would like to compare the energy expended per received
event. Unfortunately, we cannot measure that directly for two reasons.
First, we do not have hardware to directly measure energy
consumption in a running system. Second, we have previously
observed that choice of MAC protocol can completely dominate
energy measurements. In low power radios, MAC protocols that
do not sleep periodically are dominated by the amount of time
spent listening, regardless of choice of protocol. Thus energyconscious
protocols like PAMAS [32] or TDMA are necessary for
long-lived sensor networks. We are currently experimenting with
power-aware MAC approaches.
Although we currently cannot measure energy consumption on
an appropriate MAC, we can estimate the effectiveness of reducing
traffic for MACs with different duty cycles. A simple model
of energy consumption is:
"!$#%!'&(*)+#$),&(*-.#/-
where and # define the relative power and time spent listening,
receiving, and sending and is defined as the required listen
duty cycle (the fraction of time the radio must be listening to
receive all traffic destined to it). We found our sensor network
contained pockets of severe congestion, but in the aggregate, radios
listen:receive:send times were about 1:3:40. Relative energy
0An operational sensor network would use timestamps instead of
sequence numbers. Both require synchronization, but time can
be synchronized globally with GPS or NTP. We use sequence
numbers because at the time of this experiment we had not synchronized
our clocks. Experimentally, other than synchronization
overhead, sequence numbers and timestamps are equivalent.
0
500
1000
1500
2000
2500
3000
3500
0 1 2 3 4 5
Bytes sent by diffusion
1
(per received distinct event)
2
Number of Sources
With suppression
Without suppression
Figure 8: Bytes sent from all diffusion modules, normalized to
the number of distinct events, for varying numbers of sources.
consumption of listen:receive:send has been measured at ratios
from 1:1.05:1.4 to 1:2:2.5 [37]. For simplicity, assume energy
consumption ratios of 1:2:2. With these parameters, energy usage
for nodes with a duty cycle of 1 are completely dominated by
energy spent listening. At duty cycle of 22% half of the energy is
spent listening. Duty cycles of 10% begin to be dominated by send
cost. Duty cycle for most radios today is 100%, but TDMA radios
such as in WINSng nodes [29] may have duty cycles of 10–15%
for non-base-stations. This analysis illustrates the importance of
energy-conserving MAC protocols.
Since we cannot directly measure energy per event, Figure 8
measures bytes sent from diffusion in all nodes in the system normalized
to the number of distinct events received. Each point in
this graph represents the mean of five 30-minute experiments with
95% confidence intervals. Performance with one source is basically
identical with and without suppression (this form of aggregation).
As expected, suppression requires less data per event with
multiple sources than experiments without suppression. With suppression
the amount of traffic is roughly constant regardless of
the number of sources. This application-specific data aggregation
shows the benefit of in-network processing. It also shows that diffusion
is useful for point-to-multipoint communication, since traffic
represents both data and control traffic. Comparing traffic with
and without suppression shows that suppression is able to reduce
traffic by up to 42% for four sources. The network exhibits very
high loss rates at that level of traffic. Our current MAC is quite unsophisticated,
performing only simple carrier detection and lacking
RTS/CTS or ARQ. Since all messages are broken into several
27-byte fragments, loss of a single fragment results in loss of the
whole message, and hidden terminals are endemic to our multihop
topology, this MAC performs particularly poorly at high load.
We are currently working on a better MAC protocol.
We can confirm these results with a simple traffic model. We
approximate all messages as 127B long and add together interest
messages (sent every 60s and flooded from each node), reinforcement
messages (sent on the reinforced path between the sink and
each source), simple data messages (9 out of every 10 data messages,
sent only on the reinforced path, and either aggregated or
not), and exploratory data messages (1 out of every 10 data messages,
sent from each source and flooded in turn from each node,
again
possibly aggregated). If data messages are not aggregated,
each source incurs the cost of the full path, while if data messages
are aggregated after the first hop each incurs one hop cost to the
aggregation point and then one message will travel on to the sink.
Summing the message cost and normalizing per event we expect
aggregation to provide a flat 990B/event independent of the number
of sources, and we expect bytes sent per event to increase from
990 to 3289B/event without aggregation as the number of sources
rise from 1 to 4.
The shape of this prediction matches our experimental results,
but in absolute terms it underpredicts the B/event of aggregation
and overpredicts the 4-source/no-aggregation case. We believe
these differences are due to MAC-layer collisions in the experiment
that tend to drive bytes-per-event to the middle. Only 55–
80% of events generated in the experiment were delivered to the
sink, so bytes-per-event in less congested portions of the experiment
(with one source or aggregation) is high because traffic is
normalized over fewer events. On the other hand, with four sources
and no aggregation, we believe collisions happen very near the
data sources and so the aggregate amount of data sent is lower
that predicted. In addition, we sometimes observe longer paths in
experiment than we expected.
These experimental measurements of aggregation are also useful
to validate our previous simulation experiments that consider a
wider range of scenarios. Previous simulation studies have shown
that aggregation can reduce energy consumption by a factor of 3–
5
3
in a large network (50–250 nodes) with five active sources and
five sinks (Figure 6b from [23]). Although care must be used in
comparing energy to bytes sent, a 3–5-fold energy savings with
five sources is much greater than the 42% (or 1.7-fold) traffic savings
we observe with four sources. The primary reason for this
difference is differences in ratio of exploratory to data messages
in these systems. Exploratory messages (called low-data rate messages
in [23]) are used to select good gradients and so are flooded
to all nodes. Data messages (called high-rate messages in [23])
are sent only on reinforced gradients forming a path between the
sources and sinks. In simulation the ratio of exploratory to data
messages sent from a source was about 1:100 (exploratory messages
were sent every 50s, data every 0.5s, messages were modeled
as 64B packets). In our testbed this ratio was about 1:10
(exploratory messages every 60s, data every 6s, with messages
of roughly the same size). Increasing this ratio in experiment
was not possible given our small radio bandwidth (13kb/s rather
than 1.6Mb/s in simulation) while keeping reasonable experimental
running times. This large difference in ratios is consistent with
the large difference in energy or traffic savings.
A potential disadvantage of data aggregation is increased latency.
The effect of aggregation on latency is strongly dependent
on the specific, application-determined aggregation algorithm. The
algorithm used in these experiments does not affect latency at all,
since we forward unique events immediately upon reception and
then suppress any additional duplicates (incurring only the additional
negligible cost of searching for duplicates). Other aggregation
algorithms, such as those that delay transmitting a sensor
reading with the hope of aggregating readings from other sensors,
can add some latency. Understanding aggregation and sensor fusion
algorithms is an important area of future work.
Although we have quantified the benefits of in-network aggregation
in a specific application, aggregation is one example of
in-network processing. Other examples range from simple data
0
10
20
30
40
50
60
70
80
90
0 1 2 3 4 5
audio events succesfully delivered (%)
4
number of light sensors
1-level
2-level
Figure 9: Percentage of audio events successfully delivered to
the user.
caching to collaborative signal processing. As our experiments
show, not only do attribute matching and filters make aggregation
and similar services easy to provide, they also enable noticeable
performance improvements.
6.2 Nested query benefits
In Section 5.2 we suggested that nested queries could reduce
network costs and latency, and we argued that nested queries could
be implemented using attributes and filters. To validate our claim
about the potential performance benefits of this implementation
we measure the performance of an application that uses nested
queries against one that does not.
The application is similar to that described in Section 5.2 and
Figure 6: a user requests acoustic data correlated with (triggered
by) light sensors. We reuse our PC/104 testbed shown in Figure
7 placing the user “U” at node 39, the audio sensor “A” at
node 20, and light sensors “L” at nodes 16, 25, 22, and 13. It is
one hop from the light sensors to the audio sensor, and two hops
from there to the user node. To provide a reproducible experiment
we simulate light data to change automatically every minute on
the minute. Light sensors report their state every 2s (no special
attempt is made to synchronize or unsynchronize sensors). Audio
sensors generate simulated audio data each time any light sensor
changes state. Light and audio data messages are about 100 bytes
long.
Figure 9 shows the percentage of light change events that successfully
result in audio data delivered to the user. (Data points
represent the mean of three 20-minute experiments and show 95%
confidence intervals.) The total number of possible events are the
number of times all light sources change state and a successful
event is audio data delivered to the user. These delivery rates
do not reflect per-hop message delivery rates (which are much
higher), but rather the cumulative effect of sending best-effort data
across three or five hops for nested or flat queries, respectively.
This system is very congested, and as described above (Section
6.1), our primitive MAC protocol exaggerates the impact of
congestion. Missing events translate into increased detection latency.
Although a sensor network could afford to miss a few events
(since they would be retransmitted in the next time the sensor is
measured), these loss rates are unacceptably high for an operaSet
A: interest Set B: data
class IS interest class IS data
task EQ “detectAnimal” task IS “detectAnimal”
confidence GT 50 confidence IS 90
latitude GE 10.0 latitude IS 20.0
latitude LE 100.0 longitude IS 80.0
longitude GE 5.0 target IS “4-leg”
longitude LE 95.0
target IS “4-leg”
Figure 10: Attributes used for matching experiments.
tional system.
However, this experiment sharply contrasts the bandwidth requirements
of nested and flat queries. Even with one sensor the
flat query shows significantly greater loss than the nested query
because both light and audio data must travel to the user. Both
flat and nested queries suffer greater loss when more sensors are
present, but the one-level query falls off further. Comparing the
delivery rates of nested queries with one-level queries shows that
localizing the data to the sensors is very important to parsimonious
use of bandwidth. In an uncongested network we expect
that nested queries would allow operation with a lower level of
data traffic than one-level queries and so would allow a lower radio
duty cycle and a longer network lifetime.
6.3 Runtime
costs of matching
Attribute matching is used in all communication between sensors,
filters, and applications in our system. Although technology
trends suggest rapid improvement in processor performance,
price, and size, sensor nodes may chose to hold performance constant
and leverage technology through reduced price and size, so
run-time performance must be considered. A second constraint is
memory storage, particularly in very small implementations.
To evaluate matching performance we examined the cost of
matching data from a sensor. The basic matching in that case compares
an 8-element interest against a 6-element data (attributes are
shown in Figure 10). To evaluate the cost of larger data objects
we increased the number of attributes in the data from 6 to 30 attributes.
This experiment was done on our PC/104 sensor node
with a 66MHz AMD 486-class CPU. To evaluate the cost of a single
match we measured cost of many matches (5000 for matching
or 10,000 for the non-matching case) in a loop and normalized, repeating
this experiment 1000 times to avoid undue system effects
such as interrupts. The order of attributes in each set is randomized
each experiment. We also show 95% confidence intervals, although
they are always less than 5% of the mean. Although memory
caching will cause this approach to underestimate the cost of
a match, the basic trends it identifies should be applicable to operational
systems.
Our expectation is that the cost of matching is linear with the
number of elements. This is confirmed in Figure 11 that shows
the cost of matching as the number of attributes in one attribute
set increases in different ways. The two lowest lines (no-match/IS
and no-match/EQ) show the case where one of the attributes in
set A is not matched by those in set B (specifically, the confidence
value in set B is changed from 90 to 10). Because the two-way
matching algorithm tests the formals in set A first, the incremental
cost of additional attributes in set B is fairly small in this case,
and it is insensitive to the type of attribute added. If the failing
formal was in set B we would expect the cost to be higher (mid-
0
100
200
300
400
500
600
700
800
900
0 5 10 15 20 25 30 35
uSec per match
4
number of attributes in set B
match/IS
match/EQ
no-match/IS
no-match/EQ
Figure 11: Matching performance as the number of attributes
grow.
way between the measured data).
The two higher lines (match/IS and match/EQ) show the cost
of matching when all attributes succeed. The difference in cost
of additional attributes in these lines shows the cost of additional
matching. In the match/EQ line all additional attributes are formals
(additions of the “class EQ interest” attribute), so each new
attribute must be matched against set A. For match/IS, additional
attributes are actuals (repetitions of ‘extra IS “foo” ’) that must be
examined but do not require searching.
Although our current implementation is completely unoptimized,
the absolute performance of these operations is quite reasonable.
At 500
5
s/match for small attribute sets our quite slow PC/104
can match 2000 sets per second. Although quite slow by Internet
router standards, this is reasonable for sensor networks where
we expect high-level events to happen with frequencies of 10Hz
or less.
Finally, these measurements suggest several potential optimizations
to matching performance. Segregating actuals from formals
can reduce search time (since formals cannot match other formals
there is no need to compare them). Attributes could be statically or
dynamically optimized to move the attributes least likely to match
to the front. We plan to explore these kinds of optimizations in the
future.
6.4 Experiment Discussion
These experiments have provided new insight into sensor network
operation, building substantially on our prior simulation studies
[23].
These experiments are first examination of nested queries and
matching performance. They suggest that the CPU overhead of
matching should not be a constraint for reasonably powerful sensor
nodes and that nested queries can greatly reduce contention by
localizing data movement.
These experiments have explored low-bandwidth operation. Previous
simulation studies of sensor networks often have not used
the low-bandwidth radios we see in actual sensor-network hardware.
Protocols and scenarios behave qualitatively different at
10–20kb/s for sensor networks rather than the 3–12Mb/s common
to wireless 802.11 LANs. Even with our early operational experience
in small-scale demonstrations and testing, we did not appreciate
the difficulty of operating a 14-node sensor network at a
relatively high utilization. Our observations suggest two areas of
future work: first, sensor networks must adapt to local node densities
(we are beginning to explore this area [11]). Second, more
work is needed to understand how diffusion’s parameters map to
different needs, particularly the trade-offs between overhead and
reliability present in the frequency of exploratory messages, interests,
and reinforcements. Finally, the diffusion applications we
currently use operate in an open loop; feedback and congestion
control are needed.
Two aspects of radio propagation proved unexpectedly difficult.
First, some experiments seemed to show asymmetric links (communication
was fine in one direction but poor or impossible in
the other). Diffusion does not currently work well with asymmetric
links; we are considering how to best revise it. Second, some
links provided only intermittent connectivity. A future direction
for diffusion might send similar data over multiple paths to gain
robustness when faced with low-quality links. Current simulation
models, even with statistical noise, do not adequately reflect these
observed propagation characteristics.
Finally, we were generally happy with our approach to attribute
naming and filters. It was reasonably easy to build and adapt our
sample applications and debugging software.
0 comments:
Post a Comment