Transcript Node Localization in Sensor Networks

Routing Considerations for Sensor
Networks
Lecture 12
October 12, 2004
EENG 460a / CPSC 436 / ENAS 960
Networked Embedded Systems &
Sensor Networks
Andreas Savvides
[email protected]
Office: AKW 212
Tel 432-1275
Course Website
http://www.eng.yale.edu/enalab/courses/eeng460a
Announcements
 Feng Zhao’s talk tomorrow 4:00pm @ AKW 500
 Student session 3:20 – 4:00pm AKW 500
 Reading for this lecture
• Zhao & Guibas Section 3.3 through 3.6
 Reading for next lecture
• Directed Diffusion – paper posted on the class website
 Today’s presentation IDSQ
Routing Considerations in Sensor Networks
 Traditional TCP/IP routing not attractive for
sensor networks
• Too much overhead and large routing tables
 Sensor networks are more ad-hoc
• Each node acts as a router
• Still different than ad-hoc networks
o Proactive routing is too expensive
o Some possibility for reactive routing such as
– Fish-eye routing, AODV, DSR
Routing Goal
 Focus on localized state-less routing
• Consider only local neighborhood
 Classical separation of address and content does not hold
• Care about reaching the nodes rather than a particular address – what can
be sensed by a node can most probably be sensed by neighboring nodes
• Interested in routing by attributes – data centric
o Node’s location
o Node’s type of sensors
o Range of values in the sensed data
 Notion of optimality can vary
• QoS routing – latency is important => shortest path
• Energy aware routing – longer paths are ok => avoid nodes with less
energy
Geographic Routing
 Aims to route based on very limited state
information
 Geographic routing protocols assume
•
•
•
•
All nodes know their geographic location
Each node knows its 1-hop neighbors
Destination is a node with a given location
Each packet can hold a limited amount of information
as to where it has been in the network
 Any issues with this?
• Needs to maintain information between node IDs and
node location (referred to as location service)
Geographic Forwarding Approaches
 Greedy distance routing: select the neighbor
geographically closest to the destination and
forward the data to that neighbor
 Compass routing: pick the next node as the one
that minimizes the angle to destination
 What are the problems with the basic approaches
• Greedy distance routing – may get stuck in local
minima
• Compass routing – may go in loops
Planarization of Routing Graph
 To get protocols that guarantee data delivery,
make graph planar
 Remove some edges from your network graph G
• Aim: Keep the same connectivity but make the graph
planar
o no two edges in G should intersect each other
• In the planar subdivision of G each node is assumed to
know the circular order of its neighbors
• Convex perimeter routing and other face routing
protocols use this property
Common Planarization Methods

Relative Neighborhood Graph (RNG)
•
The edge xy is introduced if the intersection of circles centered at x and y with radius the
distance d(x,y) is free of other nodes
x

Grabriel Graph
•
The edge xy is introduced if the diameter xy is free of other nodes
x

y
y
Both graphs RNG and Gabriel graphs can be found with distributed construction
Greedy Perimeter Stateless Routing(GPSR)
 Geographic protocol based on the offline
construction of planar graphs
• RDG, Gabriel, later on RDG suggested
 Has 2 main phases forwarding and recovery
 Forwarding is greedy
 Recovery – uses a right-hand rule to recover
from holes. It stops as soon as a node closer
to the destination is found
Routing on a Curve
 Specify a curve a packet should follow
 Analytical description of a curve carried by the packet
 Curves may correspond to natural features of the
environment where the network is deployed
 Can be implemented in a local greedy fashion that requires
no global knowledge
 Curve specified in parametric form C(t)=(x(t),y(t))
• t – time parameter – could be just relative time
 Each node makes use of nodes trajectory information and
neighbor positions to decide the next hop for the packet.
Attribute Based Routing & Directed Diffusion
 Nodes desire certain information and other
nodes have some information. How do they
find each other?
 Use attribute value pairs to describe the data
Attribute value record
type = animal
instance = horse
location = [89, 154]
time = 2:45:23
Information request record
type = animal
instance = horse
rect = [0,200,0,200]
Directed Diffusion
 Each node names data with one or more attributes
 Other nodes express interests based on these attributes
 Network nodes propagate the interests and results back to
the sink
 Negative gradients inhibit the propagation of information
& positive gradients encourage information propagation
 Assumption: the sink will be interested in repeated
measurements from a source for a period of time
 Paa-Kwesi will give a detailed presentation of directed
diffusion next time
Next Lecture
 Geographic Hash Tables – Andreas
 Directed Diffusion – Paa Kwesi