Reliable and Energy-Efficient Data
Delivery in Sparse WSNs withMultiple Mobile Sinks
Giuseppe Anastasi
Pervasive Computing & Networking Lab (PerLab)
Dept. of Information Engineering, University of Pisa
E-mail: giuseppe.anastasi@iet.unipi.it
Website: www.iet.unipi.it/~anastasi/
PerLabSun Yat-Sen University
Guangzhou, China, April 6, 20111

Reliable and Energy-Efficient
Data Delivery in Sparse WSNswith Multiple Mobile Sinks

Based on joint work with

Eleonora Borgia, Marco Conti and Enrico Gregori
IIT-CNR, Italy

BioNets
Bio-inspired Service Evolution
for the Pervasive Age8OverviewPerLab WSNs with Mobile Sinks
 Advantages and Challenges

 Reliable & Energy Efficient Data Delivery to MSs
 Adaptive Hybrid Protocol

 Simulation Results
 Experimental Measurements
 Conclusions

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

99

WSNs with Mobile Sinks
PerLab

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

1010

WSNs with Mobile Sinks
PerLabAdvantages
 Connectivity
 A sparse sensor network may be a feasible solution for a large
number of applications.

 Cost Reduced number of sensor nodes  reduced costs

 Reliability
 Single-hop communication instead of multi-hop communication
 Reduced contentions/collisions and message losses Energy Efficiency
 Mobile Sinks can help reducing the funneling effect
Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

1111

WSNs with Mobile Sinks
PerLabChallenges
 Contact Detection
 Reliable Data Transfer

 Data Forwarding Mobility Control

MobileSink

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

1212

Approaches to Data Collection
PerLabM. Di Francesco, S. Das, G. Anastasi, Data Collection in Wireless Sensor Networks withMobile Elements: A Survey, ACM Transactions on Sensor Networks, to appear (2012),
Available at http://info.iet.unipi.it/~anastasi/pubblications.html
Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

1313

Reliable and Energy-efficient
Data Delivery to Mobile Sinks

Which is the best way to transfer all the data
available at the sensor node to the Mobile Sink(s)with the minimum energy expenditure?

14

Reference Scenario
PerLab Urban Sensing Scenario
 Sparse WSN with multiple mobile users
 Each user consumes data for its own purposes (MS) Bundle-oriented communication

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

1515

Data Transfer
PerLab Challenges
 Contacts are sporadic and short Contact duration depends on MS path, speed, …

 Some contacts may be missed due to duty cycle

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

1616

Data Transfer
PerLab

 Challenges
 The discovery phase further reduces the residual
contact time

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

1717

Data Transfer
PerLab Challenges
 Communication is impaired by message losses This reduces the available bandwidthMobileSink

G. Anastasi, M. Conti, E. Gregori, C. Spagoni, G. Valente, Motes
Sensor Networks in Dynamic Scenarios: a Performance Study for
Pervasive Applications in Urban Environments, International Journalof Ubiquitous Computing and Intelligence, Vol. 1, N.1, April 2007.

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

1818

Data TransferPerLab Challenges
 Multiple MSs simultaneously in contact
 They typically enter the contact area at different times
 They have different contact durations
 They experience different conditions (e.g., message loss)

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

1919

Data Transfer ProtocolPerLab Design Principles
 Reliable communication despite of message losses Efficient exploitation of limited resources
 Verbose protocols should be avoided

 Adaptation to channel conditions
 Non accurate information
 Time-varying channel conditions
 Multiple MSs

 Beaconing is required also during communication
 This can be achieved through ACKs

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs2020

Common ApproachPerLab ARQ Scheme

Kansal, A. and Somasundara, A. and Jea, D. and Srivastava, M. B. , Intelligent Fluid Infrastructure for Embedded
Networks. Proc ACM International Conference on Mobile Systems, Applications and Services (MobiSys 2004), Boston,MA, 6-9 June, pp. 99-110.
Somasundara, A. and Kansal, A. and Jea, D. and Estrin, D. and Srivastava, M., Controllably Mobile Infrastructure forLow Energy Embedded Networks. IEEE Transactions on Mobile Computing, Vol. 5 (8), 2006, 958-973.
Basagni, S. and Carosi, A. and Melachrinoudis, E. and Petrioli, C. and Wang, M. Controlled Sink Mobility for Prolonging
Wireless Sensor Networks Lifetime. ACM Wireless Networks (WINET), Vol. 14(6), 2008, pp. 831-858.
Shi, G. and Liao, M. and Ma, M. and Shu, Y. Exploiting Sink Movement for Energy-efficient Load-Balancing in WirelessSensor Networks. Proc. ACM International Workshop on Foundations of Wireless Ad hoc and Sensor Networking andComputing (FOWANC 2008), Hong Kong, Hong Kong , China, 28 May, pp. 39-44.
Song, L. and Hatzinakos, D., Dense Wireless Sensor Networks with Mobile Sinks. Proc. IEEE Conference on Acoustic,Speech, and Signal Processing (ICASSP 2005), Philadelphia, PA, 18-23 March 2005, pp. 677-680.
Song, L. and Hatzinakos, D., Architecture of Wireless Sensor Networks with Mobile Sinks: Sparsely Deployed Sensors.
IEEE Transaction on Vehicular Technology, Vol. 56(4), 2007, pp. 1826–1836.
Anastasi, G., Conti, M., Monaldi, E., Passarella, A., An Adaptive Data-transfer Protocol for Sensor Networks with Data
Mules. Proc. IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM
2007), Helsinki, Finland, 18-21 June 2007.

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

2121

Selective RepeatPerLab Simple ARQ Scheme The sender transmits data messages
 The receiver replies with ACKs including an indication of data
messages correctly received
 Selective retransmission of missed/corrupted messages

 Robust against message losses Corrupted or missed messages are retransmitted
 No assumption about the MS’s location

 Suitable for unicast communication
 Data are to be transferred to a single MS at a time

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

2222Erasure coding
PerLabkkk+Rk’>k

Any subset of k encoded blocks allows the receiver toreconstruct the source data
Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

2323

Which is the optimal redundancy?
PerLabThe source node sends (k + R) codes.
Which is the probability to receive correctly at least k codesat the destination?
k + R i ⋅ p ⋅ (1 − p )k + r −i
Psucc = Pr ob k ≥ k = ∑ i i =k {'}k +R

where:
 k’: number of codes correctly received by the destination
 p: packet loss (constant)Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

2424

Energy Efficiency
PerLabk ⋅ S MSG
η=⋅ Psucc(k + R ) ⋅ δ MSG ⋅ Ptx
where:
 Psucck
 SMSG
 k+R
 δMSG Ptx

probability to receive at least k codes
original number of messages
message size (in bytes)
total number of coded messages sent
time taken to send a single coded message
transmit power

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

2525

Optimal Redundancy (k=4)
PerLab12x100Optimal Redundancy (hundreds) %1086420020406080

Packet Loss (%)
Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

26

26

Optimal Redundancy
PerLab12x100Optimal Redundancy (hundreds) %

10

 k=4
 k= 8 k= 16 k= 32 k= 64 k= 128864

20020406080

Packet Loss (%)

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

27

27

Erasure coding in our scenario
PerLab Multiple MS scenario
 The required redundancy is different for different MSs
 For a given MS, the required redundancy varies overtime Redundancy should beadaptive

 ACKs are required for implicit beaconing

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

2828Hybrid Approach
PerLab HI: Hybrid Interleaved Data Delivery
 Adaptive Erasure Coding + ACKs
 Reed-Solomon codes are considered

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

29

29

Basic idea
PerLab The bundle is divided in B blocks
 Each block is then encoded separately
 Codes are generated in advance…
 … and sent out on demand The number of transmitted codes depends onfeedbacks received from MSs (through ACKs)

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple Mobile Sinks

3030

Interleaved Transmission
PerLab HI: Hybrid Interleaved Data Delivery
 Messages to transmit are picked from consecutive blocks
 Uniform distribution of message losses among blocks

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

3131

Adaptive Redundancy
PerLab Each encoded message includes
 Block identifier (0, 1, …, B-1)
 Sequence number within the block (1, 2, …)
 Encoded data unit

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

3232

Simulation SetupPerLab Ad Hoc Simulator
 HI Protocol and SR Protocol
 Discovery based on periodic Beacon emission by MSs

 Scenario Single Sensor, Multiple MSs
 MSs move along linear paths, at a fixed distance from the sensor

 Message Losses

2

 c 
 c p (t ) = a2  t − max  + a1  t − max  + a02 2 
Parameter

v=3.6 km/h

v=20 km/hv=40 km/h

cmax

158s

30s

17s

a0

0.133

0.38280.4492

a10 s-1

0 s-1

0 s-1

a2

0.000138 s-2

0.0028 s-2

0.0077 s-2

G. Anastasi, M. Conti, E. Monaldi, A. Passarella, An Adaptive Data-transfer
Protocol for Sensor Networks with Data Mules, Proc. IEEE WoWMoM
2007, Helsinki, Finland, June 18-21, 2007.

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple Mobile Sinks

3333

Performance Metrics
PerLab Decoding Probability probability of receiving the minimum amount of codes for a MS being
able to decode the original data bundle
 in the SR protocol, probability of receiving the complete bundle

 Energy Consumption
 average total energy consumed by the sensor node per each bytecorrectly transferred to MS(s)Total Number of ACKs
generated by all MSs(m ⋅ δ MSG ⋅ Ptx ) + m ⋅ δ MSG ⋅ N MS (δ ACK ⋅ Prx )Energy =Energy spent for sending
m data messages

TACK
Btot

Total # of bytes
decoded by all MSs

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple Mobile Sinks

Energy spent for receiving
ACKs from all MSs3434Simulation Parameters
PerLabParameter

Valuek, n (HI protocol)

8, 256

Message/ACK Size

110 bytes

Message Transmission Time δ MSG

17 ms

ACK Transmission Timeδ ACK

17 ms

ACK Period

TACK

16* δ ACK

Beacon Period

TB

100 ms

NACK (40Km/h, 3.6Km/h)8, 24

Duty Cycle (D)5%Transmission PowerPtx

52.2 mW

Reception PowerPrx

56.4 mW

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple Mobile Sinks

3535

Impact of Redundancy
PerLabRedundancy

kRk+R

Level 0808

Level 18816

Level 282432

Level 38248256

Level

0.3

100

HI: Level 0
HI: Level 1
HI: Level 2
HI: Level 30.25

80

Energy (mJ/Byte)

Decoding Probability (%)

907060504030

HI: Level 0
HI: Level 1
HI: Level 2
HI: Level 3

20
1000

1234567

8

90.2

0.15

0.1

0.05

1000

Number of MSs

12345678910

Number of MSs

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple Mobile Sinks

3636

Simulation Results
PerLab Increasing number of MSs
 All MSs move at the same speed (40 Km/h)

SR: 1 MSHI: 1 MS
SR: 3 MSs
HI: 3 MSs
SR: 5 MSs
HI: 5 MSs
SR: 10 MSs
HI: 10 MSs

Decoding Probability (%)

908070605040300.20.18
0.16

Energy (mJ / Byte)

100

0.14
0.12
0.1
0.08
0.06

200.04100.0200510152025303540

Bundle Size (KBytes)

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

SR: 1 MS
HI: 1 MS
SR: 3 MSs
HI: 3 MSs
SR: 5 MSs
HI: 5 MSs
SR: 10 MSs
HI: 10 MSs

00510152025303540

Bundle Size (KBytes)

3737Simulation Results
PerLab 3 Mobile Sinks
 with different paths and speeds

1000.1900.0980

0.08

Energy (mJ / Byte)

Decoding Probability (%)

 3.6 Km/h, 20 Km/h, 40 Km/h

7060
50
40
30
201000

SR: 3 MSs
HI: 3 MSs

0.07
0.06
0.05
0.04
0.03
0.02
0.01

SR: 3 MSs
HI: 3 MSs
51015202530

3540

Bundle Size (KBytes)

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

00510152025303540

Bundle Size (KBytes)

3838

Simulation Results
PerLab Single MS Moving at 40 Km/h

SR: 1 MS
HI: 1 MS
SR: 3 MSs
HI: 3 MSs
SR: 5 MSs
HI: 5 MSs
SR: 10 MSs
HI: 10 MSs

Decoding Probability (%)

908070605040300.20.18
0.16

Energy (mJ / Byte)

100

0.14
0.12
0.1
0.08
0.06

200.04100.0200510152025303540

Bundle Size (KBytes)

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

SR: 1 MS
HI: 1 MS
SR: 3 MSs
HI: 3 MSs
SR: 5 MSs
HI: 5 MSs
SR: 10 MSs
HI: 10 MSs

00510152025303540Bundle Size (KBytes)

3939

Short Bundles
PerLab

SR protocol
ACKMS

1SN132344ACK75671812233446568785588HI protocol
ACKMSSN

1132

344ACK

7567899101112

10111213131415141640

Validation with real sensor nodes
PerLab

 T-mote Sky TinyOS Operating System
 IEEE 802.15.4 PHY
 Mobility and message loss2 c  c p (t ) = a2  t − max  + a1  t − max  + a02 2 p(t)Sensor nodep(t)MS3p(t)MS2
MS141

Experimental vs. Simulation Results
PerLabHISR40 Kmh, DC 5%, SR protocol

40 Kmh, DC 5%, HI protocol
90

Decoding Probability (%)

100

Simulation: 1 MS
Testbed: 1 MS
Simulation: 5 MSs
Testbed: 5 MSs

80
70
60
50403020

Simulation: 1 MS
Testbed: 1 MS
Simulation: 5 MSs
Testbed: 5 MSs

90

Decoding Probability (%)

10080
7060
504030201010051015202530350540101540 Kmh, DC 5%, HI protocol

0.25

Energy (mJ/Byte)

Energy (mJ/Byte)

3035403540

0.3

Simulation: 1 MS
Testbed: 1 MS
Simulation: 5 MSs
Testbed: 5 MSs

0.2

0.15

0.10.05052540 Kmh, DC 5%, SR protocol

0.3

0.25

20

Bundle Size (KBytes)

Bundle Size (KBytes)

Simulation: 1 MS
Testbed: 1 MS
Simulation: 5 MSs
Testbed: 5 MSs

0.2

0.15

0.1

0.05

1015202530

3540

Bundle Size (KBytes)

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

051015202530

Bundle Size (KBytes)

4242Energy Cost of CodingPerLab Coding/decoding consumes energy Decoding is not an issue as MSs are resource rich
 Coding may be an issue Energy Consumption for coding CPU Power consumption: 3 mW
 256-code blocks  40.5 µJ/byte Larger than the energy consumed for transmission~30 µJ/byte (with 1 MS)

 32 code blocks

 3.9 µJ/byte

 Negligible wrt energy spent for transmission

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

4343

Memory requirementsPerLab Memory Availability
 Tmote Sky: 32 KB
 Jennic: 96 KB SunSpot: 512 KB

 Memory Requirements
 256-code block (8+248) = 256*110 bytes = 28 KB
 32-code block (8+24) = 32*110 bytes = 3.5 KB

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

4444

Conclusions
PerLab

 Reliable & Energy Efficient Data Transfer in Sparse
WSNs with Multiple MSs
 Sporadic and short contact times
 Communication affected by message losses HI protocol
 Erasure Coding + ACKs Coding is performed in advance Number of transmitted codes depends on loss conditions

 Simulation + Experimental Evaluation
 HI outperforms SR even when there is a single MS Energy for coding is negligible wrt energy for transmission

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple Mobile Sinks

4545

ReferencesPerLab

G. Anastasi, E. Borgia, M. Conti, E. Gregori, A Hybrid Adaptive Protocol for
Reliable Data Delivery in WSNs with Multiple Mobile Sinks, The Computer
Journal, to appear.
currently available at
http://comjnl.oxfordjournals.org/cgi/reprint/bxq038?ijkey=9XSrcSgVlpbbN1R&keytype=ref
http://info.iet.unipi.it/~anastasi/papers/tcj10.pdf

G. Anastasi, E. Borgia, M. Conti, M. Di Francesco, Reliable Data Delivery insparse WSNs with Multiple Mobile Sinks: an Experimental Analysis,
Proceedings of the IEEE International Symposium on Computers andCommunications (ISCC 2011), Corfu, Greece, June 28 – July 1, 2011.



G. Anastasi, E. Borgia, M. Conti, E. Gregori, HI: A Hybrid Adaptive Interleaved
Communication Protocol for Reliable Data Transfer in WSNs with Mobile Sinks,
Proceedings of IEEE Percom 2009 Workshops, International Workshop onSensor Networks and Systems for Pervasive Computing (PerSeNS 2009),
Galveston, USA, March 9, 2009.

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

46

46

PerLabThank you!

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple MSs

47

47