Transcript Chapter 4 Routing Protocols

Chapter 4
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
2016/3/31
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
2016/3/31
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,
lim d 
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
2016/3/31
Aggregation Techniques

In general the formation of the optimal aggregation tree is NP-hard.
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.
2016/3/31
Performance Study
Event-Radius model
7
Random Sources model
2016/3/31
Performance Study (cont.)
Energy Costs
8
Event-Radius model
2016/3/31
Performance Study (cont.)
Energy Costs
9
Random Sources model
2016/3/31
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
2016/3/31
Reference

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.
11
2016/3/31
Chapter 4.7
Data centric networking
4.7.2 Data-centric Storage

Data centric storage



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 data centric storage?



13
Energy efficiency
Robustness against mobility and node failures
Scalability
2016/3/31
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
2016/3/31
One-dimensional Data Storage


GHT
 Put(k, v)- stores v
(observed data) according
to the key k
 Get(k)- retrieve whatever
value is associated with
key k
Hash function
 Hash the key into the
geographic coordinates
 Put() and Get() operations
on the same key “k” hash
k to the same location
15
Elephant
Data
(12,24)
data
response
query
user
Get (“elephant”)
Put (“elephant”, data)
Hash (‘elephant’)=(12,24)
Hash (‘elephant’)=(12,24)
An example for GHT
2016/3/31
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
2016/3/31
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
2016/3/31
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
2016/3/31
Multi-dimensional Data Storage

Multi-Dimensional Range Queries in Sensor
Networks (DIM [Li et al. 2003])



19
Building Zones
Data Insertion
Query Propagation
2016/3/31
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)
T[3/4, 1) T[1/2, 3/4) T[1/4, 1/2) T[0, 1/4)
20
010
L[3/4, 1)
L: Light, T: Temperature
2016/3/31
Data Insertion

L[1/2, 1)
T[1/2, 1)
010
0111
3
E1= <0.8, 0.7>
1111
110
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)
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)
L[3/4, 1)
L: Light, T: Temperature
21
2016/3/31
Query Propagation

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[3/4, 1)
L: Light, T: Temperature
22
2016/3/31
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.
2016/3/31
Chapter 4.8
ZigBee
24
2016/3/31
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
2016/3/31
The Network Layer

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
26
2016/3/31
The Network Layer (cont.)
(a) Star network
ZigBee coordinator
27
(b) Tree network
ZigBee router
(c) Mesh network
ZigBee end device
2016/3/31
Network Formation and Address Assignment

Before forming a network, the coordinator determines





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 least Cm − Rm child end devices
28
2016/3/31
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  Rm Lm d 1
,

1  Rm

29
if Rm  1
Otherwise
2016/3/31
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 nth child router is assigned to address
 Aparent + (n − 1) × Cskip(d) + 1
n-th child end device is assigned to address
 Aparent + Rm × Cskip(d) + n
30
2016/3/31
Network Formation and Address
Assignment (cont.)
Cm = 5
Rm = 4
Lm = 2
Addr = 9
Addr = 10
Addr = 8
A2
Addr = 7
Cskip = 1
Addr = 24
Addr = 12
A4
Addr = 6
Addr = 19
Cskip = 1
Addr = 0
Cskip = 6
A1
A3
Addr = 13
Cskip = 1
Addr = 25
Addr = 3
Aparent + (n − 1) × Cskip(d) + 1
Aparent + Rm × Cskip(d) + n
Addr = 1
Cskip = 1
Addr = 2
ZigBee coordinator
31
ZigBee router
ZigBee end device
2016/3/31
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
2016/3/31
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  

If the destination is not a descendant of this device, this packet
will be forwarded to its parent
33
2016/3/31
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 B
Cskip = 1
Addr = 38
? A
?
Addr = 32
Cskip = 7
 Adest   A  1 
  Cskip  d 
Cskip
d
  

Addr = 126 Ar  A  1  
Addr = 40
C Cskip = 1
A < Adest < A+ Cskip(d − 1)
Z
ZigBee coordinator
34
Addr = 0
Cskip = 31
ZigBee router
ZigBee end device
2016/3/31
Route Discovery
Field Name
Description
Destination
16-bit network address of the destination
Address
Next-hop Address 16-bit network address of next hop towards
destination
Entry Status
One of Active, Discovery or Inactive
Routing Table in ZigBee
35
2016/3/31
Route Discovery (cont.)
Field Name
Description
RREQ ID
(route request)
Unique ID (sequence number) given to every
RREQ message being broadcasted
Source Address
Network address of the initiator of the route
request
Sender Address Network address of the device that sent the most
recent lowest cost RREQ
Forward Cost
The accumulated path cost from the RREQ
originator to the current device
Residual Cost
The accumulated path cost from the current
device to the RREQ destination
36
Route Discovery Table
2016/3/31
Route Discovery (cont.)
RREQ message
Yes
Does
RREQ report
A better fwd
path cost ?
Yes
RDT entry
exists for this
RREQ ?
Update RDT entry with
better fwd path cost
Yes
No
Drop RREQ
Create RDT entry and
record fwd path cost
No
Send RREP
Is
RREQ for local
node or one of
end-device
children ?
No
Create RT entry
(Discovery_Underway)
And rebroadcast RREQ
The RREQ processing
37
2016/3/31
Route Discovery (cont.)
Discard route
request
B
C
A
route reply
S
T
D
Unicast
Broadcast
Without routing capacity
38
2016/3/31
References

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 landmarkbased 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 energy-efficient
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.
39
2016/3/31
Conclusions




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
40
2016/3/31