28-09-2013, 03:18 PM
PERFORMANCE OF ADDRESS CODING WHEN APPLIED TO DATA STORAGE AND RETRIEVAL
PERFORMANCE OF ADDRESS.pptx (Size: 299.14 KB / Downloads: 13)
Background
Sensor networks have constraints that conflict in many existing protocols
Common constraints include
Robustness
Life Expectancy
Response Time
Scalability
Protocols such as Optimized Link State Routing (OLSR) may exhibit life expectancy issues (Chen,Shen,IEEE, 2004)
Protocols such as Ad Hoc Distance Vector Routing (AODV) may exhibit response time issues. (Woonkang, Minseok, IEEE, 2008)
Address coding was initially conceived as a backup strategy
Distribution of data yields some interesting possibilities
Previous papers discussed
Reliability gains from Address coding (Gaynor, Coore, IEEE WHNC, 2008)
Implementation over local addressing strategies (Gaynor, Coore, CCITT, 09)
Promise of possibiilities shown in previous work such as
HaloClip (increase throughput by storing data on neighbouring nodes) (Ghandeharizadeh et al. , IEEE, 2008)
Network coding (increase information flow through incremental coding on intermediary nodes) (Alswede et al., IEEE, 2000)
Operation of OLSR
Creates a communication backbone by establishing multipoint relays (MPRs)
Modification of the connected dominating set strategy
every node in the network not in the dominating set is only one hop away from a node in the set.
Network flooded to establish topology
with cost O(NlgN)
N is number of nodes in network
Link state information then stored
Even if never used
Lifetime issues show up eventually,
nodes on the communication backbone that are used more frequently have more power depletion
Any protocol that applies MPR strategy will be susceptible to this issue.
Operation of AODV
AODV uses different route establishment process
Does not flood or store unused route information
Destinations discovered “just-in-time”
When source wants to send packet to unknown destination
Route Request (RREQ) transmitted
If a node receiving RREQ is the required node, or knows where the required node is
Route Response (RREP) generated , which follows the route of the request back the source.
If receiving node has no information on intended destination, RREQ forwarded to neighbours, as long as TTL of searching packet does not expire
Default TTL is 3 secs
If no response to RREQ within TTL, another RREQ sent with larger TTL.
Expanding ring search results,which can have high latency.
How Address Coding can help
Number of hops from source to sink affect throughput and energy usage
If copies of data are distributed throughout network, randomly located sinks will have easier access.
Consider an application that involves the monitoring of a region of interest , denoted by R on the figure 1, within a network area, denoted by the entire map.
Application uses a continuous monitoring strategy
information is recorded, and periodically batched updates distributed
In application, numerous requests for data are performed from random points in network
One question is
How efficient is the data retrieval process?
The Simulation:Setup
Developed with Tossim
Running on tinyos-2.1.0
Used python to manage interactions with event queue
Java used to help with analysis
100 motes distributed randomly over area 2000x2000 square units
Network area further subdivided into 25 sectors, each assigned address depending on location
When each mote turns on, it acquires a random address in the network area, and is assigned to a sector.
Summary
The Address coding strategy
allows data to be stored closer to sinks
can be used to increase throughput and energy efficiency, while maintaining scalability
For certain implementation models, can be extremely efficient