Easm : Energy-efficient Data Dissemination for Arbitrary Sink Mobility in Wireless Sensor Networks

EASM : Energy-efficient Data Dissemination for Arbitrary Sink Mobility in Wireless Sensor Networks

• Aniruddha S. Gokhale ([e-mail])

• (work done with Amogh Kavimandan)

• Institute for Software Integrated Systems

• Dept. of Electrical Eng & Computer Sc

• Vanderbilt University

• Nashville, TN, USA

Focus: Wireless Sensor Networks (WSNs)

• Salient features of WSNs

• Collection of wireless sensor nodes
• Signal processing, radio and sensing in one IC
• Nodes are constrained in radio, battery & computational power, and storage capacity
• Most nodes are stationary, sinks may be mobile
• Potentially very large scale & geographically dispersed deployment
• Designed for unattended operation => need for autonomous behavior
• Communication costs outweigh computation costs
• Nodes configured usually once – due to high cost in reconfiguration
• Frequent topological changes owing to node failures, battery depletion, etc
• Non trivial challenges in data dissemination
• Used in habitat monitoring, target tracking & localization, etc.

WSN Node Architecture

• Physical Layer

• sensor hardware e.g., radio

• MAC Layer

• channel access e.g., TDMA, adaptive duty cycling

• Routing Layer

• packet routing e.g., flooding, GPSR

• Data Management Layer

• data aggregation and data dissemination

• Application/Services Layer

• target tracking, habitat monitoring

Talk Outline

• Data Dissemination Challenges in WSNs

• Existing Work & Shortcomings

• Our research - EASM

• Protocol Design
• Protocol Evaluation

• Application Support

• Model-driven Development & Middleware for WSNs

• Concluding Remarks

Data Dissemination Challenges

• Energy efficiency

• support multihop paths

• Scalability

• support increased sink-source pairs

• Tolerance to topology changes

• successful packet delivery in the face of node mobility and failure

• Timely availability of data

• timeliness of data is important

• Data-centric routing

• attribute-based naming

Existing Work in Data Dissemination for WSNs

• Directed Diffusion (Intanagonwiwat 2000)

• Sinks periodically propagate (broadcast) interests
• One path is reinforced to be used for communication

Shortcomings of Current Approaches

• Increased Routing load

• broadcast of interests increases routing load

• Restricted sink mobility

• only localized movements supported

• Scalability issues

• e.g., in TTDD - as many grids as sources!

• Undesired energy consumption

• increases for higher sink speeds

EASM: A Novel Energy Efficient Data Dissemination Scheme for supporting Arbitrary Sink Mobility

• Basic Idea

• Sink initiated

• Rendezvous-based scheme

• Uses GPSR as underlying routing protocol

• Data request and response know their destination => no broadcast

• Directed-response used to ensure data delivery for fast moving sinks

• Replication used to reduce hot-spot complexity

EASM: Rendezvous Nodes

• An event type maps to a location within sensing space, called the rendezvous point
• A rendezvous point is aware of the instantaneous source node location at any point
• Sink interested in an event uses hash function to find the location of rendezvous point for the event type and sends query using GPSR

EASM: Response Propagation

• Directed response strategy

• Sensing space is considered as a virtual grid

• Sink sends grid center location with every request, which is the center of its home cell

• Source uses grid center as a hint to direct response to sink

• Handles localized sink movement patterns

• Sink polls grid center after a predetermined interval of time

• Grid center forwards response if sink moved out of its home cell

EASM: Response Propagation

EASM: Hot-spot Complexity Management

• Replication to relieve rendezvous point or grid center hot-spot complexity

• A node replicates if it cannot perform forwarding functions
• Node initiates n depth election to determine nodes, which can be used for replication
• Nodes with high residual energies are chosen as forwarders (have source forwarding information)
• all other nodes in election are interceptors (have forwarder information)
• A packet is read by an interceptor/forwarder at depth n, & forwarded to destination

EASM: Hot-spot Complexity Management

• Replication (contd.)

• - Lease based, renewed every k seconds with the initial node

• - Fault tolerance by maintaining multiple forwarders with each interceptor

• - State required is small (source location at each forwarder, forwarder location(s) at each interceptor)

• - Employed at rendezvous points, grid centers

EASM: Routing Protocol

• Leverage the Greedy Perimeter Stateless Routing (GPSR) [Karp 2000] for routing

• Two methods for forwarding packets

• Greedy Geographic forwarding: Each forwarding node sends packet to a one-hop neighbor geographically closest to destination
• Perimeter Forwarding: Packet is forwarded along the perimeter when geographical routing fails

Results and Comparison

Results and Comparison

• Routing load significantly reduced

• Further reduction at high speeds

Additional Research Challenges

• Hash function properties

• Overload on rendezvous node due to collisions on data type
• Can hash function affect routing costs (proximity of rendezvous node to sink)
• Can hash function provide capability of load balancing

• Aggregation of requests

• Can rendezvous nodes aggregate requests from different sinks for the same data type that arrive close to each other
• Can source aggregate data to multiple sinks with same interest and which lie in the same cell

• Priority handling

• Is there a priority scheme that ranks sinks

• Effects of passage of time

• What if a source dies?
• What if a sink is no longer interested in a data type?
• How are internal data structures refreshed?

• What are additional energy costs to perform these optimizations?

• What are the effects on routing layer and MAC layer or vice versa?

Talk Outline

• Data Dissemination Challenges in WSNs

• Existing Work & Shortcomings

• Our research - EASM

• Protocol Design
• Protocol Evaluation

• Application Support

• Model-driven Development & Middleware for WSNs

• Concluding Remarks

WSN Infrastructure Challenges

• Must address constraints on energy, battery & computational power

• Must have small footprint & be optimized for the product-line

• Provide interoperability & portability

• Must maintain interlayer semantic compatibility

WSN Middleware Configuration Challenges

• Need to satisfy semantic compatibility across layers while satisfying constraints

Opportunities for Tool-based Automation [1/2]

• (1) Per Building Block Scope
• Incurred due to variations in implementations & configurations for a specific patterns-based building block
• e.g., single threaded versus thread-pool based reactor implementation dimension that crosscuts the event demultiplexing strategy (e.g., select, poll, WaitForMultipleObjects)
• Product-line commonalities help reduce the configuration choices
• e.g., single threaded reactor configuration for iterative servers
• Product-specific variabilities identify other optimization opportunities
• e.g., Reactor specialization by removing indirection, i.e., remove all virtual methods from Reactor_Impl base class completely

Opportunities for Tool-based Automation [2/2]

Applying Performance Analytical Models for Design Validation

• Build and validate performance models for invariant parts of middleware building blocks

• Weaving of variability concerns manifested in a building block into the performance models

• Compose and validate performance models of building blocks mirroring the anticipated software design of complete systems

• Estimate end-to-end performance of composed system

• Iterate until design meets performance requirements

Case Study: The Reactor Pattern

Reactor Dynamics

• Registration Phase

• Event handlers register themselves with the Reactor for an event type (e.g., input, output, timeout, exception event types)
• Reactor returns a handle it maintains, which it uses to associate an event type with the registered handler

• Snapshot Phase

• Main program delegates thread of control to Reactor, which in turn takes a snapshot of the system to determine which events are enabled in that snapshot
• For each enabled event, the corresponding event handler is invoked, which services the event
• When all events in a snapshot are handled, the Reactor proceeds to the next snapshot

Characteristics of the Reactor Performance Model

Performance Metrics for the Reactor

Using Stochastic Reward Nets (SRNs) for Performance Analysis

Modeling the Reactor using SRN

Reactor SRN: Taking a Snapshot

Reactor SRN: Initial Marking

Reactor SRN: Firing a Transition (1/6)

Reactor SRN: Firing a Transition (2/6)

Reactor SRN: Firing a Transition (3/6)

Reactor SRN: Firing a Transition (4/6)

Reactor SRN: Firing a Transition (5/6)

Reactor SRN: Firing a Transition (6/6)

Optimizations: Capturing System Invariants (1/2)

• Example System

• Basic Simple (BasicSP) four component Real-time Embedded (DRE) application Distributed scenario

• Timer Component – triggers periodic refresh rates

• GPS Component – generates periodic position updates

• Airframe Component – processes input from the GPS component and feeds to Navigation display

• Navigation Display – displays GPS position updates

Optimizations: Capturing System Invariants (2/2)

Preliminary Results: Handcrafted Middleware Optimizations in TAO ORB

Concluding Remarks

• Proposed a new data dissemination approach

• Results indicate good scalability for higher sink speeds (energy, routing load)

• High redundancy & increased fault tolerance with node replication

• High success rate in packet delivery even when sinks move out of their home cell

• Future work to focus on

• Middleware for sensor networks to support WSN-based product lines
• Model-driven generative programming to synthesize optimized middleware stacks for WSNs

Questions?

EXTRA

Directed Diffusion (1/2)

Directed Diffusion (2/2)

• Mobile sinks – frequent broadcasts of exploratory and diffusion messages

• Multiple reinforced paths – high routing overload

• Flooding – increased energy consumption

TTDD (1/2)

• Aimed at addressing sink mobility, while reducing energy consumption

• A source creates a virtual grid with itself as one of the crossing-points of grid

• A node on the crossing point is dissemination node, knows next hop node (req/resp)

• Sink broadcasts a data request to find the closest dissemination node

• DN forwards the request as shown until it reaches source, response follows same path

TTDD (2/2)

• Cell size parameter is static, can not be changed after initiation – higher cell size means higher interest broadcast for every sink

• Suitable for localized sink mobility, in-progress requests can not be serviced if sink leaves its home cell

• One grid per source, grid maintenance are very costly and not scalable

EASM Operation

• Sink sends request to rendezvous point

• Interceptors intercept request and relay to forwarders

• Forwarder redirects request to source

• Directed response from source to grid center

• Grid center relays response to sink

EASM: A Novel Energy Efficient Data Dissemination Scheme for supporting Arbitrary Sink Mobility

• Salient Features

• Sink initiated

• Rendezvous-based scheme

• Uses GPSR as underlying routing protocol

• Data request and response know their destination => no broadcast

• Directed-response used to ensure data delivery for fast moving sinks

• Replication used to reduce hot-spot complexity

EASM Architecture

• Sensing space – divided into a virtual grid

• Sink – mobile node interested in data

• Source – stationary node sensing a phenomenon

• Rendezvous point – relay requests from sink to source

• Grid center – center of a cell

• Interceptors & forwarders – used in managing hot-spot complexities