Low Duty Cycle Wireless Sensor Networks Research

L2: Lazy Forwarding in Low Duty Cycle Wireless Sensor Networks 1Zhichao Cao, 1,2Yuan He, 1,2Yunhao Liu 1Hong Kong University of Science and Technology 2Tsinghua University

Outline Introduction & Motivation Design Implementation Evaluation Conclusion 2

Low Duty Cycle WSNs X-MAC Periodical wake-up Sender initiated transmission t I wake up periodically. If I hear nothing, I will go back to sleep! I prepare send a packet. I will not stop sending until the ACK comes! 3

Drawbacks Unsynchronized wake-up schedule Long preamble The waste of energy How to shorten it? Realize the receiver s wake-up schedule by synchronization Avoid much extra energy cost Keep the synchronization accuracy 4

Forwarding in WSNs 4-bit link estimation Independent probabilistic link model Collection Tree Protocol (CTP) ETX based shortest path routing 5

Drawbacks These protocols neglect the difference between preamble based X-MAC and always-on CSMA MAC! Persistent transmission of X-MAC preamble 4-bit might overestimate the link quality CTP might take more energy and longer delay to retransmit. How to forward efficiently? Accurate probabilistic model for preamble packets. Adaptive forwarding scheme to mitigate the unexpected influence of packet loss. 6

Opportunities Link burstiness Short-term link behavior Dynamic forwarding Take the earlier chance. Robust to short-term failure. 50 40 Node 35 Node 31 30 Node ID 20 Node 19 Node 10 Node 15 10 0 100 200 300 400 500 Temporal Sequence (ms) Timing Sequence (ms) 7

Design Overview Piggybacked on routing beacon to save energy Local synchronization with error control Sync X-MAC Multivariate Bernoulli link model Dependent probabilistic model for preamble packets Avoid the bursty loss by controlling the length of the preamble. Dynamic forwarding scheme Involve multiple forwarders to maximize the packet delivery yield with limited energy budget 8

Sync X-MAC Local Synchronization the latest wake-up The interval is constant, if the period of all nodes is the same. 9

Sync X-MAC (cont.) Sync X-MAC Sender t ACK loss Sync X-MAC Receiver t To avoid further energy waste, the maximum preamble length should be constrained! 10

MB Link Model t How about this time? 11

MB Link Model (cont.) The probability is updated by unicast data! t Receiver j ACK 1 2 4 Sender i 3 Snd1 += 1 ACK1 += 0 For any preamble packet k, ?? Update by Exponentially Weighted Moving Average (EWMA) method. Snd2 += 1 ACK2 += 0 Snd3 += 1 ACK3 += 0 Snd4 += 1 ACK4 += 1 ?? =???? ????. 12

MB Link Model (cont.) The probability is initiated and refreshed by broadcast beacon! t Rec = 0 Rec = 1 Rec = 1 Rec = 2 Receiver i n n+1 n+3 Sender j n+2 1 ??? ?????= 0.67 Treat each preamble packet transmission as independent, ?? ?? = 13

MB Link Model (cont.) Delivery probability of a preamble of length k ?1= ?1 ??= ?? 1+ (1 ?? 1) ?? Marginal benefit of the tail ????_??????= ???_?????? ???= ??+ (1 ??) ???+1 14

Dynamic Forwarding Expected Delivery Quality (EDQ) ??? =???? ???; Expected Packet Delivery Ratio (EPDR) Hop count (HOP) Compute recursively! Assume the length of transmission window is k from node i to j. ?(?) ????? =????? ?? ????+ 1 EDQA(sink) =1 EDQC(A) =0.5 C EDQE(C) =0.33 E EDQG(E) =0.25 G EDQG(D) =0.2 1 1 1 1 A Sink EPDR = 1 HOP = 0 0.9 0.8 F D B 1 1 EDQF(E) =0.225 EDQB(sink) =1 0.75 EDQF(D) =0.25 EDQD(B) =0.375 15

Dynamic Forwarding (cont.) Sink Forwarder 2 I have data to send now! Node i Forwarder 1 How to distribute the limited energy budget for each forwarder to achieve the maximum delivery probability? Forwarder 3 Forwarder 2 Preamble Length 0.9 0.7 0.5 0.5 Forwarder 1 Forwarder 3 Forwarder 1 0.7 0.2 0.1 0.1 Forwarder 2 Node i 0.8 0.7 0.6 0.4 Forwarder 3 16

Dynamic Forwarding (cont.) Find the energy sequence {l1 lm} to maximize the delivery quality! =?? 1 + 1/????1 ?1(?1) ????1 ?1(?1)) ????({?2, ,??}) ???? ?1, ,?? + (1 ?? NP Hard Problem! 17

Dynamic Forwarding (cont.) Greedy Algorithm Energy budget is 6 packets! Initiate the heap with = ), i k p f k Initialize {l1, l2, , lm} as {0, 0, , 0} Pick up , , f it 1( t t t 1,2,..., m { f , f } i i i 1 2 m Maximum Heap Pick up the maximum Marginal benefit link j Preamble Length 0.9 0.7 0.5 0.5 F1 The heap is not empty and 1 Update the heap by +1( i p lj += 1 Yes m 0.7 0.2 0.1 0.1 No kl F2 l t f ) j i j 0.8 0.7 0.6 0.4 F3 No TW_LENGTH and BURSTY_LOSS l j l t Exit Yes RP ( f ) k i i j 18

Implementation 25 Telosb nodes indoor testbed Each node generates a packet per [2-4]s. Radio power is 1. Run for 30 minutes each time. 40 Telosb nodes outdoor testbed 5 8 grids. Each node generates a packet per [30-60]s. Radio power is 1. Run for 1 hour each time. 19

Implementation (cont.) Memory Utilization Version RAM(bytes) ROM(bytes) CTP + 4-bit + X-MAC (X-MAC) 5490 27666 CTP + 4-bit + Sync X-MAC (Sync X-MAC) 6427 36958 CTP + 4-bit + A-MAC (A-MAC) 5410 29794 DSF + 4-bit + Sync X-MAC (DSF) 6507 38070 Deterministic L2 6933 39386 Dynamic L2 6933 39572 20

Evaluation Average Performance Version Preamble Length PDR Duty Cycle CPP ROR X-MAC 97.1 13.4 263.5 14.5 9.5 Sync X-MAC 97.7 10.7 59.6 3.4 5.59 DSF 99.1 9.4 53.3 3.22 4.2 Deterministic L2 97.1 8.5 44.3 2.4 3.1 Dynamic L2 99.5 7.2 38.6 2.0 3.6 21

Evaluation (cont.) Average Performance Version Preamble Length PDR Duty Cycle CPP ROR X-MAC 97.1 13.4 263.5 14.5 9.5 Sync X-MAC 97.7 10.7 59.6 3.4 5.59 DSF 99.1 9.4 53.3 3.22 4.2 Deterministic L2 97.1 8.5 44.3 2.4 3.1 Dynamic L2 99.5 7.2 38.6 2.0 3.6 22

Evaluation (cont.) Average Performance Version Preamble Length PDR Duty Cycle CPP ROR X-MAC 97.1 13.4 263.5 14.5 9.5 Sync X-MAC 97.7 10.7 59.6 3.4 5.59 DSF 99.1 9.4 53.3 3.22 4.2 Deterministic L2 97.1 8.5 44.3 2.4 3.1 Dynamic L2 99.5 7.2 38.6 2.0 3.6 23

Evaluation (cont.) Average Performance Duty- Cycle 6.2% 3.3% Max- Hop 9 9 Version PDR 94.7% 98.0% Ave-Hop 4.0 4.2 A-MAC Dynamic L2 Outdoor testbed The best wake-up interval (128 ms) of A-MAC is smaller than L2 (512 ms) so that the energy baseline of A-MAC is higher. 24

Conclusion L2 is a practical data forwarding technique tailored to low duty cycle WSNs. Key design MB link model for short-term link burstiness Greedy energy distribution with dynamic forwarding Evaluation Indoor and outdoor testbeds Both high packet delivery ratio and low energy consumption Future works Large-scale test Different hardware 25

Thank you! Question? 26

Back-up Slides 27

Synchronization Global synchronization Global time All nodes align their clocks to a standard clock. 28

Synchronization (cont.) + ( ) ( ) jt jt Routing Beacon SendOff Node j as Sender PreaOff t SFD Interrupt loss offset j ( ) i Node i as Receiver t HearOff ti(SFD) ( ) it offseti(j) = (SendOff + PreaOff - HearOff) mod ( ) 29

Evaluation (cont.) Average Performance Version Preamble Length PDR Duty Cycle CPP ROR X-MAC 97.1 13.4 263.5 14.5 9.5 Sync X-MAC 97.7 10.7 59.6 3.4 5.59 DSF 99.1 9.4 53.3 3.22 4.2 Deterministic L2 97.1 8.5 44.3 2.4 3.1 Dynamic L2 99.5 7.2 38.6 2.0 3.6 30

Evaluation (cont.) 1.0 1.0 0.8 0.8 0.6 0.6 CDF CDF 0.4 0.4 2 Dynamic L DSF 2 Dynamic L DSF 2 Deterministic L Sync X-MAC X-MAC 0.2 0.2 2 Deterministic L Syn-X-MAC 0.0 0.0 0.00 0.05 0.10 0.15 0.20 0.25 0.30 0.35 20 30 40 50 60 70 80 90 100 Radio-on Duty Cycle Preamble Length (ms) 1.0 1.0 0.8 0.8 0.6 0.6 CDF CDF 0.4 0.4 2 2 Dynamic L DSF Dynamic L DSF 0.2 0.2 2 2 Deterministic L Sync-X-MAC Deterministic L Sync-X-MAC 0.0 0.0 0 1 2 3 4 5 6 0 5 10 15 20 Contention per Packet Overheard Pkts / Received Pkts 31

Evaluation (cont.) # of Forwarder Candidates Average 1.61 2.38 Standard Deviation 0.55 1.29 Version DSF Dynamic L2 L2 Dependents on the node density Degrade to deterministic way under the sparse deployment DSF Involve all neighbors as the candidates Convergence problem Depend on the time of the best forward wake-up 32