7/1/2018

Reference papers
Routing Protocols  J. Al-Karaki, A. E. Kamal, “Routing Techniques in
Wireless Sensor Networks: A Survey”

 K. Akkaya, M. Younis, “A Survey on Routing Protocols

for Wireless Sensor Networks”

Kuliah Jaringan Sensor

Dosen: Ali Husein A. ST. MEng

Routing challenges and design Routing challenges and design

issues issues
 Node deployment  Data routing methods
 Manual deployment  Application-specific
 Sensors are manually deployed  Time-driven: Periodic monitoring
 Data is routed through predetermined path
 Event-driven: Respond to sudden changes
 Random deployment  Query-driven: Respond to queries
 Optimal clustering is necessary to allow connectivity &
energy-efficiency  Hybrid

 Multi-hop routing

Routing challenges and design Routing challenges and design

issues issues
 Node/link heterogeneity  Fault tolerance
 Homogeneous sensors  Some sensors may fail due to lack of power, physical

 Heterogeneous nodes with different roles & damage, or environmental interference

capabilities  Adjust transmission power, change sensing rate,
 Diverse modalities reroute packets through regions with more power
 If cluster heads may have more energy & computational
capability, they take care of transmissions to the base station
(BS)

1
 7/1/2018

Routing challenges and design Routing challenges and design

issues issues
 Network dynamics  Transmission media
 Mobile nodes  Wireless channel

 Mobile events, e.g., target tracking  Limited bandwidth: 1 – 100Kbps

 If WSN is to sense a fixed event, networks can work  MAC

in a reactive manner  Contention-free, e.g., TDMA or CDMA
 A lot of applications require periodic reporting  Contention-based, e.g., CSMA, MACA, or 802.11

Routing challenges and design Routing challenges and design

issues issues
 Connectivity  Coverage
 High density  high connectivity  An individual sensor’s view is limited
 Area coverage is an important design factor
 Some sensors may die after consuming their battery
power  Data aggregation
 Connectivity depends on possibly random
 Quality of Service
deployment  Bounded delay
 Energy efficiency for longer network lifetime

Routing Protocols in WSNs

I. Flat routing
 I. Flat
 II. Hierarchical
 III. Location-based
 IV. QoS-based

2
 7/1/2018

SPIN (Sensor Protocols for

Information via Negotiation)
 Flooding
 Too much waste
 Implosion & Overlap
 Use in a limited scope,
if necessary
 Data-centric routing
 No globally unique ID
 Naming based on data
attributes
 SPIN, Directed
diffusion, ...

SPIN Direct Diffusion: Motivation

 Pros  Properties of Sensor Networks
 Each node only needs to know its one-hop  Data centric
neighbors  No central authority
 Significantly reduce energy consumption compared  Resource constrained
to flooding  Nodes are tied to physical locations
 Cons  Nodes may not know the topology
 Data advertisement cannot guarantee the delivery of  Nodes are generally stationary
data
 If the node interested in the data are far from the source,
 How can we get data from the sensors?
data will not be delivered
 Not good for applications requiring reliable data delivery,
e.g., intrusion detection

Directed Diffusion: Main Directed Diffusion: Motivating

Features Example
 Data centric  Sensor nodes are monitoring animals
 Individual nodes are unimportant  Users are interested in receiving data for all 4-legged
 Request driven creatures seen in a rectangle
 Sinks place requests as interests  Users specify the data rate
 Sources satisfying the interest can be found
 Intermediate nodes route data toward sinks
 Localized repair and reinforcement
 Multi-path delivery for multiple sources, sinks,
and queries

3
 7/1/2018

Directed Diffusion: Interest and Directed Diffusion: Interest

Event Naming Propagation
 Query/interest:  Flood interest
1. Type=four-legged animal  Constrained or Directional flooding based on location is
2. Interval=20ms (event data rate)
3. Duration=10 seconds (time to cache) possible
4. Rect=[-100, 100, 200, 400]  Directional propagation based on previously cached data
 Reply:
1. Type=four-legged animal Gradient
2. Instance = elephant Source Interest
3. Location = [125, 220]
4. Intensity = 0.6
5. Confidence = 0.85
6. Timestamp = 01:20:40
 Attribute-Value pairs, no advanced
naming scheme Sink

Directed Diffusion: Data

Propagation Directed Diffusion: Reinforcement
 Multipath routing  Reinforce one of the neighbor after receiving initial data.
 Consider each gradient’s link quality  Neighbor who consistently performs better than others
 Neighbor from whom most events received

Gradient Gradient
Source Data
Source Data
Reinforcement

Sink Sink

Directed Diffusion: Negative Directed Diffusion: Summary of the

Reinforcement protocol
 Explicitly degrade the path by re-sending interest with lower data
rate.
 Time out: Without periodic reinforcement, a gradient will be torn
down

Gradient
Source Data
Reinforcement

Sink

4
 7/1/2018

Directed Diffusion: Pros & Cons Extension of Directed Diffusion

 Different from SPIN in terms of on-demand data querying  One-phase pull
mechanism
 Sink floods interests only if necessary  Propagate interest
 A lot of energy savings
 In SPIN, sensors advertise the availability of data  A receiving node pick the link that delivered the
 Pros interest first
 Data centric: All communications are neighbor to neighbor with no  Assumes the link bidirectionality
need for a node addressing mechanism
 Each node can do aggregation & caching  Push diffusion
 Cons  Sink does not flood interest
 On-demand, query-driven: Inappropriate for applications requiring
continuous data delivery, e.g., environmental monitoring  Source detecting events disseminate exploratory
 Attribute-based naming scheme is application dependent data across the network
 For each application it should be defined a priori
 Extra processing overhead at sensor nodes  Sink having corresponding interest reinforces one of
the paths

Rumor Routing Rumor Routing

 Variation of directed diffusion  When a node generates a query, a node
 Don’t flood interests (or queries) knowing the route to a corresponding event can
 Flood events when the number of events is small but respond by looking up its events table
the number of queries large
 Route the query to the nodes that have observed a  No need for query flooding 
particular event  Only one path between the source and sink  
 Long-lived packets, called agents, flood events  Rumor routing works well only when the number of
through the network
events is small 
 When a node detects an event, it adds the event to
its events table, and generates an agent  Cost of maintaining a large number of agents and large
 Agents travel the network to propagate info about event tables will be prohibitive 
local events  Heuristic for defining the route of an event agent highly
 An agent is associated with TTL (Time-To-Live)
affects the performance of next-hop selection 

MCFA (Minimum Cost Forwarding

Algorithm) MCFA
 Assume the direction of routing is always known, i.e.,  Each node has to know the least cost path estimate to
toward the fixed base station (BS) BS
 BS broadcasts a message with cost set to 0
 No need for a node to have a unique ID or routing table  Every node initially sets its cost to BS to ∞
 Each node maintains the least cost estimate from itself  When a node receives the msg from BS, it checks if the
to BS estimate in the packet + 1 < the node’s current estimate to BS
 If yes, the current estimate & estimate in the msg are updated and
 Broadcast a message to neighbors resent
 A neighbor checks if it’s on the least cost path btwn the  Else, delete the msg; Do nothing
source and BS  A node far from BS may receive several msg’s  A node will
not send the updated msg until a * lc where a is a constant & lc
 If so, it re-broadcasts the message to its neighbors is the link cost
 Repeat until BS is reached  Works well for fixed topologies  
 Sensors are assumed to know what they have to look
for
  or ?

5
 7/1/2018

Gradient-Based Routing (GBR) COUGAR & TinyDB

 Variation of directed diffusion
 Each node memorizes the number of hops when the interest is  View a WSN as a distributed database
diffused
 Each node computes its height, i.e., the minimum number of hops  Use declarative queries to abstract query
to BS processing from the network layer—network
 Difference btwn a node’s height & its neighbor’s is the gradient on layer independent
the link
 Forward a packet on a link with the largest gradient  Perform in-network data aggregation
 Data aggregation
 When multiple paths pass through a node, the node can combine data  Drawbacks
 Traffic spreading  Extra overhead & energy consumption due to the
 Uniformly divide traffic over the network to increase network lifetime extra query layer
 Stochastic scheme: Randomly pick a gradient when two or more next hops
have the same gradient  Synchronization is required for data aggregations
 Energy-based scheme: A node increases its height when its energy drops
below a certain threshold  Leader nodes should be dynamically maintained to
 Stream-based scheme: New streams are not routed through nodes that are prevent them from being hotspots
part of the path for other streams
 Outperforms directed diffusion in terms of total energy

ACQUIRE
 View a WSN as a distributed DB II. Hierarchical Routing
 Complex queries can be divided into subqueries
 BS sends a query
 Each node tries to answer the query by using precached info and
forwards the query to another node
 If the cached info is not fresh, the nodes gather info from their
neighbors within a lookahead of d hops
 Once the query is resolved completely, it is sent back to BS via the
reverse path or shortest path
 ACQUIRE can deal with complex queries by allowing many nodes
send to send responses
 Directed diffusion cannot handle complex queries due to too much
flooding
 ACQUIRE can adjust d for efficient query processing
 If d = network diameter, ACQUIRE becomes similar to flooding
 In contrast, a query has to travel more if d is too small
 Provides mathematical modeling to find an optimal value of d for a grid
of sensors, but no experiments performed

LEACH (Low Energy Clustering

Hierarchy) LEACH
 Cluster-based protocol  Pros
 Each node randomly decides to become a cluster heads (CH)
 CH chooses the code to be used in its cluster  Distributed, no global knowledge required
 CDMA between clusters  Energy saving due to aggregation by CHs
 CH broadcasts Adv; Each node decides to which cluster it belongs  Shortcomings
based on the received signal strength of Adv
 CH creates a xmission schedule for TDMA in the cluster  LEACH assumes all nodes can transmit with enough power
 Nodes can sleep when its not their turn to xmit to reach BS if necessary (e.g., elected as CHs)
 CH compresses data received from the nodes in the cluster and  Each node should support both TDMA & CDMA
sends the aggregated data to BS
 CH is rotated randomly
 Extension of LEACH [5]
 High level negotiation, similar to SPIN
 Only data providing new info is transmitted to BS

6
 7/1/2018

Comparison between SPIN, LEACH & TEEN (Threshold sensitive Energy

Directed Diffusion Efficient Network protocol)
SPIN LEACH Directed  Reactive, event-driven protocol for time-critical
applications
Diffusion  A node senses the environment continuously, but turns radio on
and xmit only if the sensor value changes drastically
Optimal No No Yes  No periodic xmission
Route 

Don’t wait until the next period to xmit critical data
Save energy if data is not critical
Network Good Very good Good  CH sends its members a hard & a soft threshold
 Hard threshold: A member only sends data to CH only if data
Lifetime values are in the range of interest

Resource Yes Yes Yes

 Soft threshold: A member only sends data if its value changes
by at least the soft threshold
Awareness  Every node in a cluster takes turns to become the CH for a time
interval called cluster period
Use of Yes No Yes  Hierarchical clustering
meta-data

Multi-level hierarchical clustering in

TEEN & APTEEN TEEN
 Good for time-critical applications 
 Energy saving 
 Less energy than proactive approaches
 Soft threshold can be adapted
 Hard threshold could also be adapted depending on
applications
 Inappropriate for periodic monitoring, e.g.,
habitat monitoring 
 Ambiguity between packet loss and
unimportant data (indicating no drastic change)


APTEEN (Adaptive Threshold sensitive

Energy Efficient Network protocol) Sensor aggregate routing
 Extends TEEN to support both periodic sensing &  Sensor aggregate: a set of nodes satisfying a
reacting to time critical events grouping predicate
 Unlike TEEN, a node must sample & transmit a data if  Mainly designed for target tracking
it has not sent data for a time period equal to CT (count
time) specified by CH
 Compared to LEACH, TEEN & APTEEN consumes
less energy (TEEN consumes the least)
 Network lifetime: TEEN ≥ APTEEN ≥ LEACH
 Drawbacks of TEEN & APTEEN
 Overhead & complexity of forming clusters in multiple levels
and implementing threshold-based functions

Source: M. Handy at University of Rostock

7
 7/1/2018

TTDD (Two Tier Data

Dissemination) TTDD: Sensor Network Model
 Data dissemination to mobile sinks
 Two-tier query & data forwarding
Sink
 Objectives
 Source proactively builds a grid structure to support
data availability for mobile sinks
 Mobility pattern is unknown a priori
 Localize impacts of sink mobility on data forwarding Stimulus Source Sink
 Only a small set of sensor nodes maintain forwarding
state

Source: TTDD at Mobicom ‘02

TTDD Basics TTDD Mobile Sinks

Dissemination Node Dissemination Node

Data Announcement Data Announcement Trajectory

Forwarding
Source Source
Immediate
Dissemination
Data Data Node

Sink Sink

Immediate Query Immediate

Dissemination Dissemination Trajectory
Node Node Forwarding

Source: TTDD at Mobicom ‘02 Source: TTDD at Mobicom ‘02

TTDD Multiple Mobile Sinks Grid Maintenance

Dissemination Node Dissemination Node

Data Announcement Trajectory

Forwarding
Source Source
Immediate X Immediate
Dissemination Dissemination
Data Node Data Node

Source

Source: TTDD at Mobicom ‘02 Source: TTDD at Mobicom ‘02

8
 7/1/2018

GAF (Geographic Adaptive

Fidelity)
III. Location-based routing  Energy-aware location-based protocol mainly designed
protocols for MANET
 Each node knows its location via GPS
 Associate itself with a point in the virtual grid
 Nodes associated with the same point on the grid are considered
equivalent in terms of the cost of packet routing
 Node 1 can reach any of nodes 2, 3 & 4  2,3, 4 are equivalent;
Any of the two can sleep without affecting routing fidelity

GEAR (Geographic and Energy

GAF Aware Routing)
 Three states  Restrict the number of interest floods in
 Discovery: Determine neighbors in a grid directed diffusion
 Active  Consider only a certain region of the network rather
than flooding the entire network
 Sleep
 Each node keeps an estimated cost & a
 Each node in the grid estimates its time of leaving the
grid and sends it to its neighbors
learning cost of reaching the sink through its
neighbors
 The sleeping neighbors adjust their sleeping time to
keep the routing fidelity  Estimated cost = f(residual energy, distance to
the destination)
 Learned cost is propagated one hop back
every time a packet reaches the sink
 Route setup for the next packet can be adjusted

GEAR GEAR
 Phase 1: Forwarding packets towards the region  Phase 2: Forwarding the packet within the
 Forward a packet to the neighbor minimizing the cost target region
function f  Apply either recursive forwarding
 Forward data to the neighbor which is closest to the sink and  Divide the region into four subareas and send four copies of
has the highest level of remaining energy the packet
 Repeat this until regions with only one node are left
 If all neighbors are further than itself, there is a hole
 Pick one of the neighbors based on the learned  Alternatively apply restricted flooding
 Apply when the node density is low
cost
 GEAR successfully delivers significantly more
packets than GPSR (Greedy Perimeter
Stateless Routing)
 GPSR will be covered in detail in another class

9
 7/1/2018

SAR (Sequential Assignment

Routing)
IV. QoS-aware routing  Table-driven multi-path approach to achieve
energy efficiency & fault tolerance
 Creates trees rooted at one hop neighbors of
the sink -> Form multiple paths from sink to
sensors
 QoS metrics, energy resource, priority level of each
packet
 Local Failure Recovery
 Select one of the paths according to the energy
resources and QoS on the path
 High overhead to maintain tables and states at
each sensor

Energy Aware QoS Routing Energy Aware QoS Routing

Protocol Protocol
 Basic settings  Finds least cost and
 Base station
energy efficient paths that
 Gateways can
communicate with each meet the end-to-end delay
other during connection
 Sensor nodes in a cluster
can only be accessed by  Link cost = f(energy reserve,
the gateway managing the transmission energy, error
cluster rate) of nodes
 Focus on QoS routing in
one cluster  Class-based queuing
 Real-time & non-real-time model used to support
traffic exist best-effort and real-time
 Support timing constraints
for RT traffic generated by
 Improve throughput of non-
RT traffic
imaging sensors

Energy Aware QoS Routing Energy Aware QoS Routing

Protocol Protocol
 Support bandwidth ratio r between real-time and best-  Drawbacks
effort traffics  Transmission time is not considered to estimate E2E
 Properly adjust r to support end-to-end delay without severely
starving best-effort traffic delay
 Use extended Dijkstra’s algorithm to list an ascending  Usually, transmission delay >> propagation delay
set of least cost paths  Assumes more powerful gateways
 A gateway checks if E2E QoS can be met  All communications are through gateways
 Estimates E2E delay = E2E queuing delay + E2E propagation  Gateways have to find paths and r to support QoS
delay requirements
 Only allows to establish a real-time connection if E2E delay ≤
E2E Deadline
 Also, tries to find which r value maximizes the throughput of
non-RT traffic

10
 7/1/2018

SPEED Summary
 Each node maintains info about its neighbors and uses
greedy geographic forwarding to find the paths
 Tries to ensure a certain speed for each packet in the
network
 Congestion avoidance
 Flat routing – Does not assume more powerful gateways
or cluster heads
 To be discussed in detail in another class

Questions?

11