Transcript sink

Structure-Free Data Aggregation
in Sensor Networks
Outline





Introduction
Background
DAA & RW
Performance Evaluation
Conclusion
Introduction

Because of structured approaches may incur high
maintenance overhead in dynamic scenarios for
event-based application.

The author wish to design techniques and protocols
that lead to efficient data aggregation without
explicit maintenance of a structure.

So the author propose the structure-free data
aggregation for the event-based sensor networks.
Outline





Introduction
Background
DAA & RW
Performance Evaluation
Conclusion
Background
What
is Data Aggregation
Why
Data Aggregation
How
to do Data Aggregation
Structure
data aggregation
What is Data Aggregation

When sensors generate raw data packets, before these
packets transfer to the sink, we can do the process
combining and compressing data coming from different
sensors in order to reduce the packets to be sent over
the network.
Sink
A
aggregator
A
Sink
aggregator
B
B
Why to do Data Aggregation

The main purpose of data aggregation is in order to
conserve energy to extend the lifetime of sensor node.

So we reduce the packet length and the transmission
times to conserve energy by data aggregation.
How to do Data Aggregation

Two approaches:

Aggregation with size reduction (e.g. local temperature)

Aggregation without size reduction (e.g. temperature and
humidity)

Two consideration factor:

Temporal Convergence
- These packets must meet in the same node at the same time

Spatial Convergence
- These packets must meet in the same node at the same time
Spatial Convergence

How to transfer packet to the node with the packet
which can be aggregated.
A
S
B
E
D
A
S
C
B
S
C
E
D
A
B
A
B
E
D
A
S
C
C
B
D
E
A
B
C
C
Fig (a) shows the packet transmissions
using opportunistic aggregation.
Fig(b) shows how information about the
existence of data in neighboring nodes
can be exploited to make dynamic
forwarding decisions to achieve higher
aggregation.
Node have packet to send
Routing path by routing protocol
S
E
D
(a)
S
E
D
(b)
Wireless link
Structure data aggregation

Centralized structured approaches
- These approaches are suited for data gathering application

Distributed structured approaches
- These approaches are proposed for event-based application.

Structured approaches have several limitations for
event-based application.
-For dynamic scenarios, the overhead of construction and
maintenance of the structure may outweigh the benefits of data
aggregation.
Outline





Introduction
Background
DAA & RW
Performance Evaluation
Conclusion
DAA Assumption

Node know the geographic location of their one-hop
neighbors and the sink.

The Interference range is at least twice the transmission
range.
Node a’s Interference range
a
r

b
r
c
We aggregate packets that are generated at the same
time, so nodes must be time-synchronized.
Data-Aware Anycast(DAA)

DAA is based on anycasting at the MAC layer to determine
the next-hop for each transmission.

DAA Base-approach (use RTS/CTS)


We define the Aggregation ID(AID) to associate packets that
can be aggregated.
RTS contains the AID of the transmitting packet and any
neighbor that has a packet with the same AID can respond with
a CTS.
sink
e
f
RTS
CTS
RTS
CTS
d
RTS
RTS
a CTS
RTS
c
b
Enhanced DAA (1/2)

CTS Priority

Class A: The receiver has a packet with the same AID as
specified in RTS and ids closer to the sink than the
sender.

Class B: The receiver has a packet with the same AID as
specified in RTS but is farther away from the sink than
the sender.

Class C: The receiver does not have a packet with the same
AID but is closer to the sink than the sender.
• Class C1: nodes are on the shortest path to the sink.
• Class C2: nodes are at least closer to the sink by half of the
transmission range than the sender.
• Class C3: Remaining nodes in Class C.
Enhanced DAA (2/2)

It shows packets are still aggregated when they have the
chance to meet; otherwise, the packets are forwarded
greedily toward the sink.
CTS
slot
Class A
sende
r
e
Class A
f
d
c
Class C3
Class A receiver
1
Class A
receiver 2
Class C2
Class B
receiver 3
a
b
Shortest path
Class B
Class C
receiver 4
Minislot
Class A
Class B
Class C
RTS
CTS
Canceled
CTS
Canceled
CTS
Canceled
CTS
Goals

Early aggregation
- Packets must get aggregated as early as possible on their journey to
the sink.

Tolerance to event dynamics
- If the event region changes, the overhead must not increase and the
aggregation performance must remain unchanged.

Robust to interference
- Intermittent link failures should not affect the aggregation performance.

Fault tolerance
- The aggregation performance must not be affected by node failures.
Without Temporal Convergence

In DAA, packets may not get aggregated if they are spatially
separated and if they are be forwarded in lock-step by MAC layer.
Sink
A
B
C
D
Interference
range
Sink
A
B
- Hence A must set a delay time.
C
With packet
D
Without packet
How to choose delay time

Concept:

The difference between two delays must larger then the
transmission time between two nodes.
Sink
12ms
9ms
A
B
6ms
3ms
C
D
Delay time
…
2ms
Sink
2ms
2ms
12ms
2ms
A
B
transmission time
1ms
3ms
C
D
…
2ms
2ms
2ms
How to decide A’s delay ?
Event Size
Sink
sensor
Event-detected sensor
Randomized Waiting (RW)

Each source delays its transmission by an interval
chosen from 0 to γ, where γ is the maximum delay.

How to choose γ?

Because the optimum value of γ depends on the size of
the event and the time to transmit a packet.
- if event size increases, the max delay should increase.

Weak point
-Random delay is chosen too close.
Outline





Introduction
Background
DAA & RW
Performance Evaluation
Conclusion
Experiment Simulation

Environment description:

Topology is a 15 x 7 grid network with 105 nodes.

Sink locate at corner of the network and other 104 node
generate packets when they detect an event.

Each node can communicate with their two-hop grid
neighbors directly.

We compare DAA+RW to Aggregation Tree (AT) and
Opportunistic Aggregation (OP).
Result
Conclusion

The proposed approach for data aggregation that do not use any
explicit structures.

For spatial convergence, we proposed Data-Aware Anycast (DAA)
For temporal convergence, we proposed Randomized Waiting (RW)




In simulation, DAA with RW approach can improve the normalized
load by as much as 73 percent compared to opportunistic aggregation.
Based on the experimental study, DAA + RW can significantly reduce
the normalized overhead in terms of number of transmissions.
This shows that structure-free data aggregation techniques have great
potential for event-based applications.