Growth Codes: Maximizing Sensor Network Data Persistence Abhinav Kamra, Vishal Misra, Dan Rubenstein

Growth Codes: Maximizing Sensor Network Data Persistence

• Abhinav Kamra, Vishal Misra, Dan Rubenstein

• Department of Computer Science, Columbia University

Outline

• Problem Description

• Solution Approach: Growth Codes

• Experiments and Simulations

• Conclusions and Ongoing work

Background: A generic sensor network

Specific Context: Disaster Scenarios

• e.g., Monitoring earthquakes, fires, floods, war zones

• Problems in this setting

• Congestion near sink(s)
• All nodes simultaneously forward data
• Overwhelm sink(s) capacity

Specific Context: Disaster Scenarios - 2

• Problems in this setting

• Network Collapsing: nodes failing rapidly
• Pre-computed routes may fail
• Data from failed nodes can be lost
• Data Recovery from subset of nodes acceptable

Challenges

• Networking Challenges:

• Disaster scenarios: feedback often infeasible
• Frequent disruptions to routing tree if setup
• Difficult to predict node failures: sink locations unknown, surviving routes unknown
• Difficult to synchronize nodes’ clocks

• Coding Challenges:

• Data source distributed (among all sensor nodes)
• Prior approaches (Turbo codes, LDPC codes) aim at fast complete recovery

• Sensor nodes have very limited memory, CPU, bandwidth

Objectives

• Fraction of data that eventually reaches the sink(s)

Limitations of Previous Work

• Channel Coding based

• (e.g. Turbo Codes [Anderson-ISIT94], LT Codes [Luby02])
• Aim for complete recovery in minimum time
• Difficult to implement with distributed sources

• Routing-based

• (e.g. Directed Diffusion [Govindan00], Cougar [Yao-SIGMOD02])
• Conjecture: Too fragile (disrupted easily) for disaster scenarios

Our Approach

• Two main ideas

• Randomized routing and replication
• Avoid actively maintaining routes
• Replicate data to increase data survival
• Distributed channel codes (Growth Codes)
• Expedite data delivery & survivability

Outline

• Problem Description

• Our Solution: Growth Codes

• Experiments and Simulations

• Conclusions and Ongoing work

Network Assumptions

• N node sensor network

• Limited storage: each node stores small # of data units

• Large storage at sink(s): sink receives codewords from random node(s)

• All sensed data assumed independent (no source coding)

High Level View of the Protocol

High Level View of the Protocol (2)

High Level View of the Protocol (3)

• After time K1, nodes start sending degree 2 codewords

• After time K2, nodes start sending degree 3 codewords

• .

• .

• After time Ki, nodes start sending degree i+1 codewords

The Intuition behind Growth Codes

The Intuition behind Growth Codes(2)

Outline

• Problem Description

• Growth Codes

• Simulations and Experiments

• Conclusions and Ongoing work

Simulations/Experiments: Compare data persistence of various approaches

• Simulations:

• Centralized Setting: compare GC with other channel coding schemes
• Distributed Simulation: assess large-scale performance of coding vs no coding

• Experiments on motes:

• Compare time of complete recovery for GC vs routing
• Measure resilience to node failures

Comparison with various coding schemes (N = 1500)

• Centralized Simulation

• (to compare with other channel coding schemes for which only centralized versions exist)

• Single source, single sink
• Source generates random codewords according to coding scheme (GC, Soliton)
• Zero failure rate

Growth Codes vs No Coding (Varying N)

• Distributed Simulation

• (to assess the performance gain of coding)

• N sources, single sink
• Random graph topology (avg degree 10)
• Sink receives 1 codeword per time unit

Experiments with (micaz) motes

• (to measure data persistence with time)

• GC vs TinyOS’s “MultiHop” routing protocol

• No routing state at time 0 (scenario where sensor nodes are deployed rapidly)

Motes experiments: Resilience to node failures

• Nodes generate data every 300 seconds

• 3 nodes fail just after 3rd data generation

Motes experiments: Resilience to node failures

Other Results: Please refer to our paper

• Good values for K1, K2, …

• More simulations/experiments

• Various topologies
• Other failure scenarios

• Implementation details:

• Memory usage at sensor nodes: how it affects performance
• How to handle periodic data generation
• How to reduce overhead of coefficients

Conclusions

• Data persistence in sensor networks:

• First distributed channel codes (GC)
• Protocol requires minimal configuration
• Is robust to node failures

• Simulations and experiments on micaz motes show, (compared to prior coding and routing methods)

• GC achieves complete recovery faster
• GC recovers more partial data at any time

Ongoing Work

• Adapt Growth Codes to scenarios where sensor data is correlated

• Take advantage of any available routing information (e.g. before a disaster)

• Estimate network size on the fly to use in Growth Codes

Thanks for your patience !

• For more information

• DNA Research Lab, Columbia University

• http://dna-wsl.cs.columbia.edu/