Transcript Chapter 4 Routing Protocols

Ad hoc and Sensor Networks
Routing protocols
(Part II)
Outline
 4.1
Routing Challenges and Design Issues in WSNs
 4.2 Flat Routing
 4.3 Hierarchical Routing
 4.4 Location Based Routing
 4.5 QoS Based Routing
 4.6 Data Aggregation and Convergecast
 4.7 Data Centric Networking
 4.8 ZigBee
 4.9 Conclusions
2
Chapter 4.6
Data Aggregation and
Convergecast
Aggregation in Sensor Networks

Traditional Address-Centric routing



IP address routing
Not suitable in large scale sensor networks
Data-Centric Routing


Content-based routing
Enhance the data aggregation opportunity
Source 1
Source 2
1
B
1
Source 2
2
2
A
1
a) Address-Centric (AC) Routing
Data
Aggregation
B
A
1+2
2
Sink
4
Source 1
Sink
b) Data-Centric (DC) Routing
Theoretical Results on Aggregation

Let there be k sources located within a diameter X, each a distance di
from the sink. Let NA and ND be the number of transmissions required
with AC and optimal DC protocols, respectively.
1. The following are bounds on ND:
N D  (k  1) X  min(di )
N D  min(di )  (k  1)
2. Asymptotically, for fixed k, X, as d = min(di) is increased,
limd 
ND 1

NA k
3. Although the problem is NP-hard in general, the optimal data
aggregation tree can be formed in polynomial time when the sources
induce a connected sub-graph on the communication graph.
5
Aggregation Techniques

In general the formation of the optimal aggregation tree is NPhard. Some suboptimal DC routing heuristics as follows:
 Center at Nearest Source (CNSDC)


Shortest Path Tree (SPTDC)


Start with path from sink to nearest source. Successively add next
nearest source to the existing tree.
Address Centric (AC)

6
Opportunistically merge the shortest paths from each source wherever
they overlap.
Greedy Incremental Tree (GITDC)


All sources send the information first to the source nearest to the sink,
which acts as the aggregator.
No aggregation, distinct shortest paths from each source to sink.
Performance Study
Event-Radius model
7
Random Sources model
Performance Study (cont.)
Energy Costs
Event-Radius model
8
Performance Study (cont.)
Energy Costs
Random Sources model
9
Conclusions
 Data
aggregation can result in significant energy
savings for a wide range of operational scenarios.
 The gains from aggregation are paid for with
potentially higher delay. It should be possible to
design routing algorithms for sensor networks in
which this tradeoff is made explicitly.
10
Reference

11
B. Krishnamachari, D. Estrin, and S. B. Wicker, "The
impact of data aggregation in wireless sensor networks," In
Proceedings of the 22nd International Conference on
Distributed Computing Systems Workshops (ICDCSW'02), pp.
575-578, Vienna, Austria, July 02-05 2002.
Chapter 4.7
Data centric networking
4.7.2 Data-centric Storage
 Data


Data is stored inside the network.
All data with the same name (or data range) will be
stored at the same sensor network location
 Why



13
centric storage
data centric storage?
Energy efficiency
Robustness against mobility and node failures
Scalability
One-dimensional Data Storage
 Data-Centric
Storage in Sensornets with GHT, a
Geographic Hash Table (GHT [Ratnasamy et al.
2003])



14
Data Storage and Retrieval
Perimeter Refresh Protocol
Structured Replication
One-dimensional Data Storage


15
GHT
Elephant
 Put(k, v)- stores v
Data
(observed data)
(12,24)
according to the key k
data
 Get(k)- retrieve
response
whatever value is
query
associated with key k
user
Hash function
Get (“elephant”)
Put (“elephant”, data)
 Hash the key into the
Hash (‘elephant’)=(12,24)
Hash (‘elephant’)=(12,24)
geographic coordinates
 Put() and Get()
operations on the same
An example for GHT
key “k” hash k to the
same location
Perimeter Refresh Protocol
 Assume
key k hashes
at location L
A
is closest to L so it
becomes the home
node
E
Replica
Replica
D
L
F
A
home
C
16
B
Structured Replication
 Augment
event name
with hierarchy depth
 Given root r and given
hierarchy depth d

(0, 100)
(100, 100)
Compute 4d – 1 mirror
images of r
(0, 0)
(100, 0)
root point
level 1 mirror points
level 2 mirror points
Example of structured replication
with a 2-level decomposition
17
Conclusions
 Data
centric storage entails naming of data and
storing data at nodes within the sensor network
 GHT uses Perimeter Refresh Protocol and
structured replication to enhance robustness and
scalability
 DCS is useful in large sensor networks and there
are many detected events but not all event types
are Queried
18
Multi-dimensional Data Storage
 Multi-Dimensional
Range Queries in Sensor
Networks (DIM [Li et al. 2003])



19
Building Zones
Data Insertion
Query Propagation
Building Zones
L[0, 1/2)
Divide network into
zones.
 Each node mapped
to one zone.
 Encode zones based
on division.
 Each zone has a
unique code.
 Map m-d space to
zones.
 Zones organized
into a virtual binary
tree.
L[1/2, 1)

T[1/2, 1)
0111
110
3
4
1111
5
1110
2
1
6
0110
T[0, 1/2)
7
9
8
0001
10
0000
001
L[0, 1/4)
L[1/4, 1/2)
10
L[1/2, 3/4)
L: Light, T: Temperature
L[3/4, 1)
T[3/4, 1) T[1/2, 3/4) T[1/4, 1/2) T[0, 1/4)
20
010
Data Insertion

L[1/2, 1)
T[1/2, 1)
010
0111
3
E1= <0.8, 0.7>
5
4
1110
2
1
6
0110
Store E1
T[0, 1/2)
7
9
8
0001
10
0000
L[0, 1/4)
001
L[1/4, 1/2)
10
L[1/2, 3/4)
L: Light, T: Temperature
21
1111
110
L[3/4, 1)
T[3/4, 1) T[1/2, 3/4) T[1/4, 1/2) T[0, 1/4)
Encode events
 Compute
geographic
destination
 Hand to
GPSR
 Intermediate
nodes can
refine the
destination
estimation
L[0, 1/2)
Query Propagation

22
L[1/2, 1)
010
0111
Q11= <.5-.75, . 5-1>
T[1/2, 1)
1111
110
3
4
Q12= <.75-1, .75-1>
5
1110
2
1
6
0110
T[3/4, 1) T[1/2, 3/4) T[1/4, 1/2) T[0, 1/4)
Split a large
query into
smaller subqueries.
 Encode each subquery.
 Process subqueries
separately,
resolving locally
or forwarding to
other nodes
based on their
codes.
L[0, 1/2)
Q10= <.75-1, .5-.75>
T[0, 1/2)
7
9
8
0001
10
Q1= <0.5-1, 0.5-1>
0000
L[0, 1/4)
001
L[1/4, 1/2)
10
L[1/2, 3/4)
L: Light, T: Temperature
L[3/4, 1)
Conclusions
 DIM
resolves multi-dimensional range queries
efficiently.
 Work that still needs to be done



23
Skewed data distribution
 These can cause storage and transmission hotspots.
Existential queries
 Whether there exists an event matching a multidimensional range.
Node heterogeneity
 Nodes with larger storage space assert larger-sized
zones for themselves.
Chapter 4.8
ZigBee
24
The ZigBee Standard

ZigBee is a low cost, low power, low complexity, and low
data rate wireless communication technology at short range.
Based on IEEE 802.15.4, it is mainly used as a low data rate
monitoring and controlling sensor network
Applications
Application Framework
Zigbee
Specification
Network & Security
Application
Medium Access Control (MAC) Layer
802.15.4
Zigbee stack
Physical (PHY) Layer
Hardware
25
The Network Layer
26

ZigBee identifies three device types
 The ZigBee coordinator (one in the network) is an FFD
managing the whole network
 A ZigBee router is an FFD with routing capabilities
 A ZigBee end-device corresponds to a RFD or FFD acting
as a simple device

The ZigBee network layer supports three types of network
configurations:
 Star topology
 Tree topology
 Mesh topology
The Network Layer (cont.)
(a) Star network
ZigBee coordinator
27
(b) Tree network
ZigBee router
(c) Mesh network
ZigBee end device
Network Formation and Address
Assignment (Tree Network)
 Before
forming a network, the coordinator
determines
28

Maximum number of children of a router (Cm)

Maximum number of child routers of a router (Rm)

Depth of the network (Lm)

Note that a child of a router can be a router or an end
device, so Cm ≥ Rm

The coordinator and routers can each have at most Rm
child routers and at most Cm − Rm child end devices
Network Formation and Address
Assignment (cont.)



For the coordinator, the whole address space is logically
partitioned into Rm + 1 blocks
The first Rm blocks are to be assigned to the coordinator’s
child routers and the last block is reserved for the
coordinator’s own child end devices
From Cm, Rm, and Lm, each router computes a parameter
called Cskip to derive the starting addresses of its children’s
address pools
1  Cm   Lm  d  1 ,


Cskip  d   1  Cm  Rm  Cm  RmLmd 1
,

1  Rm

29
if Rm  1
Otherwise
Network Formation and Address
Assignment (cont.)
 The
coordinator is said to be at depth d = 0, and d is
increased by one after each level
 Address
assignment begins from the ZigBee
coordinator by assigning address 0 to itself
 If

a parent node at depth d has an address Aparent :
the n-th child router is assigned to address:
Aparent + (n − 1) × Cskip(d) + 1

the n-th child end device is assigned to address:
Aparent + Rm × Cskip(d) + n
30
Network Formation and Address
Assignment (cont.)
Cm = 5: Maximum number of children
of a router
Rm = 4: Maximum number of child
routers of a router
Lm = 2: Depth of the network
Addr = 9
Addr = 8
Addr = 10
A2
Addr = 7
Cskip = 1
Addr = 24
Addr = 12
A4
Addr = 6
Addr = 19
Cskip = 1
A3
Addr = 13
Cskip = 1
Addr = 0
Cskip = 6
A1
Addr = 1
Addr = 25 Cskip = 1
Addr = 3
the n-th child router:
Aparent + (n − 1) × Cskip(d) + 1
the n-th child end device:
Aparent + Rm × Cskip(d) + n
Addr = 2
ZigBee coordinator
31
ZigBee router
ZigBee end device
ZigBee Routing Protocol
 In
a ZigBee network, the coordinator and routers
can directly transmit packets along the tree
 When a device receives a packet, it first checks if it
is the destination or one of its child end devices is
the destination
 If so, this device will accept the packet or forward
this packet to the designated child. Otherwise, it
forwards the packet to its parent
32
ZigBee Routing Protocol (cont.)

If a device n receives a packet with destination Adest .
Assume that the depth of the device n is d and its address is
A. This packet is for one of its descendants if the destination
address Adest satisfies A < Adest < A+ Cskip(d − 1), and this
packet will be relayed to the child router with address
 Adest   A  1 
Ar  A  1  
  Cskip  d 
 Cskip  d  

33
If the destination is not a descendant of this device, this
packet will be forwarded to its parent
ZigBee Routing Protocol (cont.)
Addr = 64
Cskip = 1
Addr = 125
Cm = 6
Rm = 4
Lm = 3
Addr = 92
Addr = 30
Addr = 63
Cskip = 7
Addr = 1
Cskip = 7
Addr = 31
Addr = 33
Cskip = 1
B
Addr = 0
Cskip = 31
? A
?
Addr = 32
Cskip = 7
Addr = 126
 Adest   A  1 
Ar  A  1  
  Cskip  d 
 Cskip  d  
Addr = 40
C Cskip = 1
A < Adest < A + Cskip(d − 1)
Z
Addr = 38
ZigBee coordinator
34
ZigBee router
ZigBee end device
Route Discovery (Mesh Network)
Routing Table in ZigBee
Field Name
35
Description
Destination
Address
Next-hop
Address
16-bit network address of the destination
Entry Status
One of Active, Discovery or Inactive
16-bit network address of next hop towards
destination
Route Discovery (cont.)
Route Discovery Table
Field Name
Description
RREQ ID
(route request)
Unique ID (sequence number) given to every
RREQ message being broadcasted
Source
Address
Sender
Address
Forward Cost
Network address of the initiator of the route
request
Network address of the device that sent the
most recent lowest cost RREQ
The accumulated path cost from the RREQ
originator to the current device
The accumulated path cost from the current
device to the RREQ destination
Residual Cost
36
Route Discovery (cont.)
RREQ
message
Yes
Does
RREQ
report
A better
fwd path
cost ?
No
Drop RREQ
RDT entry
exists for this
RREQ ?
Yes
Update RDT entry
with better fwd path
cost
Yes
Send RREP
Create RDT entry
and record fwd path
cost
Is
RREQ for local
node or one of
end-device
children ?
No
The RREQ processing
37
No
Create RT entry
(Discovery under way)
And rebroadcast RREQ
Route Discovery (cont.)
Discard route
request
B
C
A
route reply
S
T
D
Unicast
Broadcast
Without routing
capacity
38
References
39

P. Baronti, P. Pillai, V. Chook, S. Chessa, and F. Gotta, A. andFun Hu. Wireless
sensor networks: a survey on the state of the art and the 802.15.4 and zigbee
standards. Communication Research Centre, UK, May 2006.

J. Bruck, J. Gao and A. A. Jiang, “MAP: Medial Axis Based Geometric Routing
in Sensor Network,” in Proceedings of ACM MobiCom, 2005.

Q. Fang, J. Gao, L. Guibas, V. de Silva, and L. Zhang. GLIDER: Gradient
landmark-based distributed routing for sensor networks. In Proc. of the 24th
Conference of the IEEE Communication Society (INFOCOM’05), March 2005.

B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris. Span: An energyefficient coordination algorithm for topology maintenance in ad hoc wireless
networks. In International Conference on Mobile Computing and Networking
(MobiCom 2001), pages 85–96, Rome, Italy, July 2001.

Y. Xu, J. Heidemann, and D. Estrin. Geography-informed energy conservation
for ad hoc routing. In Proceedings of the ACM/IEEE International Conference
on Mobile Computing and Networking, pages 70–84, Rome, Italy, July 2001.
Conclusions




40
Routing in sensor networks is a new area of research, with
a limited but rapidly growing set of research results
We highlight the design trade-offs between energy and
communication overhead savings in some of the routing
paradigm, as well as the advantages and disadvantages of
each routing technique
Overall, the routing techniques are classified based on the
network structure into four categories: flat, hierarchical,
and location-based routing, and QoS based routing
protocols.
Although many of these routing techniques look promising,
there are still many challenges that need to be solved in
sensor networks