|
Growth Codes: Maximizing Sensor Network Data Persistence Abhinav Kamra, Vishal Misra, Dan Rubenstein
|
tarix | 05.03.2018 | ölçüsü | 494 b. | | #30130 |
|
Abhinav Kamra, Vishal Misra, Dan Rubenstein Department of Computer Science, Columbia University
Outline Problem Description Solution Approach: Growth Codes Experiments and Simulations
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 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
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)
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/
Dostları ilə paylaş: |
|
|