Transcript Section 10 (Ch.13) – Ad Hoc and Sensor

CS 6910 – Pervasive Computing
Spring 2007
Section 10 (Ch.13):
Ad Hoc and Sensor Networks
Prof. Leszek Lilien
Department of Computer Science
Western Michigan University
Slides based on publisher’s slides for 1st and 2nd edition of:
Introduction to Wireless and Mobile Systems by Agrawal & Zeng
© 2003, 2006, Dharma P. Agrawal and Qing-An Zeng. All rights reserved.
Some original slides were modified by L. Lilien, who strived to make such modifications clearly
visible. Some slides were added by L. Lilien, and are © 2006-2007 by Leszek T. Lilien.
Requests to use L. Lilien’s slides for non-profit purposes will be gladly granted upon a written
request.
0
Chapter 13
Ad Hoc and Sensor Networks
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
(Modified by LTL)
1
Outline





Introduction
Characteristics of MANETs
Applications
Routing
 Table-driven Routing Protocols
 Source-initiated On-demand Routing
 Hybrid (Routing) Protocols
Wireless Sensor Networks
 General Wireless Sensor Networks
 Fixed Wireless Sensor Networks
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
2
13.1. Introduction

A Mobile Ad hoc Network (MANET)
 An ad hoc network



Formed as needed
Does not require support from any existing newtork
infrastructure
Formal def. of MANET:
 An autonomous system of mobile nodes or MSs (also
serving as routers) connected by wireless links, the union
of which forms a communications network modeled in
the form of an arbitrary communication graph

Autonomous => does not require support from any existing
network infrastructure
 But might be able to use such support if available



Such support might be available from time to time
Support could be: an Internet gateway or some fixed stations
Notice how different from cellular network

Requires infrastructure (BS, MSC, backbone network, etc.)
=> not ad hoc
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
3
13.1 Introduction – cont. 1

Characteristics of MANETs:
 Dynamically changing topology

Changing in an unpredictable manner



Limited power available to nodes (e.g., a battery)
Usually communicates only with neighboring nodes


Among other reasons, to save power
Peer-to-peer


Since nodes are free to move
No more or less “important” nodes
Information transmission via store-and-forward


Using multi-hop routing
MSs also serve as routers
Moving to a new location
MS2
MS2
(fig)
Asymmetric =
unidirectional - when
xmission power of
nodes on its ends is
different (e.g., MS4
stronger than MS7)
MS4
Asymmetric link
MS3
MS5
MS7
Symmetric link
MS1
MS6
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
4
13.1 Introduction – cont. 2

As nodes move:
 Connectivity changes
 Topology information must be updated


E.g., MS2 changes attachment: from MS3 to MS4
Communication characteristics for MANETs:
 Each node equipped with a wireless transmitter and a
receiver with an appropriate antenna
 Impossible to have all nodes within each other’s radio
range
 When the nodes are close by (within each others radio range),
they can communicate directly


If direct comm. => no routing needed
(one hop)
Wireless connectivity modeled by a random multi-hop
graph exists between the nodes
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
5
13.2 Characteristics of Ad Hoc Networks
(revisited)


Dynamic topologies
 Network topology may change dynamically as the nodes
are free to move
Bandwidth-constrained, variable capacity links
 Wireless links have typically lower capacity than wired
 Realized throughput of wireless communication is lower
than the radio’s maximum transmission rate
 Link capacity is relatively low => congestion is common
(collisions occurs frequently as application demand approaches link capacity)

Energy-constrained operation
 Nodes in ad hoc network may rely on batteries or other
limited energy sources

Energy conservation may be a dominant design factor
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
6
13.2 Characteristics of Ad Hoc Networks – cont.

Limited physical security
 More prone to physical security threats than wired
networks




Incl. stealing mobile ad hoc devices
Many attacks, incl. Eavesdropping, spoofing, and DoS
attacks are easier
Decentralized network control
 Eliminates single points of failure
(=> better reliability)
Scalability problems
 As networks get large
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
7
13.3. Applications (Examples)



“Wearable” computing
Defense applications
Crisis-management applications


Telemedicine


E.g., assistance by a surgeon for an emergency
Tele-geoprocessing applications



Natural disasters, where the entire communication infrastructure is in
disarray
Queries dependent on location of the users
Integrating geographical info systems (GIS) & GPS
Virtual navigation


Data from a remote database transmitted to navigation device in car
or in hand
May contain graphical representation of streets, buildings, and the
latest traffic information


May assist driver in selecting a route
Education and Internet access


K-12, continued education, etc., for people in remote areas
E.g., email-by-bus in remote villages
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
8
13.4. Routing in MANETS

Many factors affecting routing in MANETs:
 Models of topology
 Selection of routers
 Initiation of route requests
 Specific underlying characteristics


E.g. application-based characteristics
Major goals in selecting routing protocols:
 Provide the maximum possible reliability - use alternative
routes if an intermediate node fails
 Choose a route with the least cost



E.g., minimal # of hops from source to destination
Give the nodes the best possible response time and
throughput
Each node in MANETs expected to serve as a router

All execute the same routing protocol

Protocol calculates a route
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
9
13.4.1. Need for Routing in MANETS

Goals for routing in MANETs:
1) Route computation must be distributed

Centralized routing in a dynamic network is usually too expensive
2) Routing computation should not involve the maintenance
of global state

Would require xmitting a lot of information in dynamic topology
3) As few nodes as possible involved in route computation
and state propagation


But every node must have quick access to routes on demand
Ensure infrequent topology updates for MANET portions that
have no traffic
4) Each node must be only concerned about the routes to
its destinations
5) Stale routes must be avoided or detected & eliminated
6) Broadcasts should be avoided

Broadcasts can be highly unreliable in MANETs
7) If topology stabilizes, the routes must converge to the
optimal routes
8) It is desirable to have a backup route

Used when the primary route becomes stale
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
10
13.4.1. Need for Routing in MANETS – cont.
A major challenge in designing routing protocol:
 Must know at least how to route a packet via its
neighbors
 Network topology can change frequently
 Large # of network nodes (MSs)
=> Could have a lot of info to update


Unless a clever protocol design
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
11
13.4.2. Routing Classification

Types of routing protocols:
1) Proactive protocols
 Keep routes ready at all times
When a packet needs to be forwarded, the route is
already known
Example: distance vector routing protocols (more below)


2) Reactive (= on-demand) protocols

Route determination on demand
Determine a route only when there is a packet to send
Examples: flooding routing algorithms, ad hoc on-demand
distance vector (AODV), temporarily ordered routing
algorithm (TORA) (more below)



Proactive vs. reactive
 In proactive:
a route available immediately
 In reactive:
(1) a significant delay
(2) significant traffic of control msgs
(searching for a route)
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
12
13.4.2. Routing Classification – cont.

Is proactive or reactive better for MANETs?
 Pure proactive use too much bandwidth for control updating routing information




Too keep it current all the time
But topology changes are so quick that most routes never used
– a waste!
Pure reactive too slow for real-time applications
(Orthogonal) types of routing protocols:
1) Table-driven protocols
2) Source-initiated on-demand protocols
3) Hybrid protocls
More on all of them in the following subsections
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
13
13.5. Table-driven Routing Protocols


“Table-driven” because:
Each node maintains table(s) with routing information for
every other nodes in the network
Table-driven is proactive


When the topology changes, updates are propagated throughout
the network.
Examples of table-driven routing protocols are:



Destination Sequenced Distance Vector routing (DSDV)
Cluster-head Gateway Switch routing (CGSR)
Wireless Routing Protocol (WRP)
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
14
++SKIP++ 13.5.1. Destination-Sequenced
Distance-Vector Routing (DSDV)


Based on the Bellman-Ford algorithm (skipped – Ch.12)
Each mobile node maintains a routing table



Routing table updates are periodically transmitted
Each entry in the table is marked by a sequence number


In terms of number of hops to each destination
Helps to distinguish stale routes from new ones, and thereby avoiding
loops
To minimize the routing updates, variable sized update
packets are used

Depending on the number of topological changes
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
15
13.5.2. Cluster-head Gateway Switch
Routing (CGSR)


Cluster-head gateway switch routing (CGSR) –
a clustered multi-hop routing, heuristic
MANET divided into clusters
 For each cluster, a cluster-head (CH) elected

By a distributed CH selection algorithm

It modifies DSDV by using a hierarchical CH to route traffic
Gateway nodes are bridges connecting cluster heads
Frequent changes of CHs affect the performance


Gateway Node
Cluster Head
Internal (noncluster) Node
1
0
7
8
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
9
16
13.5.2. Cluster Head Gateway Switch Routing (CGSR)

CGSR scenario - routing from Node 1 to Node 12:






Packet sent by Node 1 is first routed to its CH (2)
The packet is routed from CH (2) to gateway (4) connecting to CH of
another cluster (5)
Packet routed from gateway (4) to the next CH (5)
…
Packet routed from gateway (10) to CH of destination cluster (11)
Packet routed to destination node (12)
6
12
5
11
4
10
7
2
1
9
8
3
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
Gateway Node
Cluster Head
Internal (noncluster) Node
17
++SKIP++ 13.5.3. The Wireless Routing
Protocol (WRP)

Each node maintains 4 tables:
 Distance table
 Routing table
 Link cost table
 Message Retransmission List table (MRL)
MRL contains the sequence number of the update
message, a retransmission counter and a list of
updates sent in the update message
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
18
++SKIP++ 13.5.3. The Wireless Routing Protocol (WRP) – cont.





Nodes inform each other of link changes using update
messages
Nodes send update messages after processing updates
from their neighbors or after detecting a change in the
link
If a node is not sending messages, it must send a HELLO
message within a specified time to ensure connectivity
If the node receives a HELLO message from a new node,
that node is added to the table
It avoids the “count to infinity” problem
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
19
13.6. Source-Initiated On-Demand
Routing (the second category of routing protocols)


Source-initiated on-demand routing - the 2nd
category (“family”) of routing protocols
This family of protocols includes:
1) Ad hoc On-Demand Distance Vector (AODV)
2) Dynamic Source Routing (DSR)
3) Temporary Ordered Routing Algorithm (TORA)
4) Associativity Based Routing (ABR)
5) Signal Stability Routing (SSR)
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
20
++SKIP++ 13.6.1. Ad hoc On-Demand
Distance Vector Routing
 AODV is an improvement over DSDV, which
minimizes the number of required broadcasts by
creating routes on demand
 Nodes that are not in a selected path do not
maintain routing information or participate in
routing table exchanges
 A source node initiates a path discovery process to
locate the other intermediate nodes (and the
destination), by broadcasting a Route Request
(RREQ) packet to its neighbors
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
21
++SKIP++ Route Discovery in AODV
Protocol
Hop1
Hop2
Hop3
7
2
5
Source 1
8 Destination
3
6
4
(a) Propagation of Route Request (RREQ) Packet
7
2
5
Source 1
8 Destination
3
4
6
(b) Path Taken by the Route Reply (RREP) Packet
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
22
++SKIP++13.6.2. Dynamic Source
Routing
 The protocol consists of two major phases: Route
Discovery, Route Maintenance
 When a mobile node has a packet to send to some
destination, it first consults its route cache to check whether
it has a route to that destination
 If it is an un-expired route, it will use this route
 If the node does not have a route, it initiates route discovery
by broadcasting a Route Request packet
 This Route Request contains the address of the destination,
along with the source address
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
23
++SKIP++ 13.6.2. Dynamic Source Routing – cont. 1
 Each node receiving the packet checks to see whether it
has a route to the destination. If it does not, it adds its own
address to the route record of the packet and forwards it.
 A route reply is generated when the request reaches either
the destination itself or an intermediate node that contains
in its route cache an un-expired route to that destination.
 If the node generating the route reply is the destination, it
places the the route record contained in the route request
into the route reply.
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
24
++SKIP++ 13.6.2. Dynamic Source Routing – cont. 2
Creation of Route Record in DSR
Hop1
2
<1>
Source 11
Hop2
Hop3
77
<1,2>
5
<1>
33
Hop4
<1,3,5,7>
<1,3,5>
8 Destination
<1,3>
<1>
6
44
<1,4,6>
<1,4>
(a) Building Record Route During Route Discovery
7
2
5
Source 1
8 Destination
3
<1,4,6>
6
4
<1,4,6>
<1,4,6>
(b) Propagation of Route Reply with the Route Record
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
25
++SKIP++ 13.6.3. Temporarily Ordered
Routing Algorithm (TORA)



TORA is a highly adaptive loop-free distributed
routing algorithm based on the concept of link
reversal
TORA decouples the generation of potentially farreaching control messages from the rate of
topological changes
The height metric is used to model the routing state
of the network
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
26
++SKIP++ 13.6.3. TORA – cont. 1
Source
H=3
H=2
H=1
H=0
Destination
Illustration of Tora height metric
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
27
++SKIP++ 13.6.3. TORA – cont. 2



The protocol performs three basic functions: route
creation, route maintenance, route erasure
During the route creation and maintenance phases
nodes use a height metric to establish a Directed
Acyclic Graph (DAG) rooted at the destination
Thereafter links are assigned a direction based on the
relative heights
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
28
++SKIP++ 13.6.3 13.6.3. TORA – cont. 3
2
(-,-)
Source
1
5
(-,-)
3
(-,-)
(-,-)
7
(-,-)
Destination
8
(0,0)
6
(-,-)
4
(-,-)
Figure 13.6(a) – Propagation of the query message
2
(0,3)
Source
1
(0,3)
3
(0,3)
5
(0,2)
7
(0,1)
8
Destination
(0,0)
4
(0,2)
6
(0,1)
Node’s height updated as a result of the update message
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
29
++SKIP++ 13.6.3 13.6.4. Associativity
Based Routing (ABR)







The three phases of ABR are: route discovery, route
reconstruction, route deletion
In ABR a route is selected based on the degree of stability
associated with mobile node
Association stability is defined by connection stability of one
node with respect to another node over time and space
Each node generates a beacon to signify its existence
When received by neighboring nodes, the beacon causes
their associativity tables to be updated
The route discovery is accomplished by a Broadcast QueryReply (BQ-REPLY) cycle
When a discovered route is no longer desired, the source
node initiates a Route Delete broadcast so that all the nodes
along the route update their routing tables
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
30
++SKIP++ 13.6.3 13.6.5. SignalStability-Based Routing (SSR)


SSR selects a route based on the signal strength
between nodes and a node’s location stability
This route selection criteria has the effect of choosing
routes that have a better link connectivity
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
31
13.7. Hybrid routing protocols


Many of hybrid routing protocols
7 example protocols follow
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
32
++SKIP++ 13.7. Hybrid routing protocols – cont. 1
1) Zone Routing Protocol (ZRP): A node proactively maintains
routes to destinations within a local neighborhood
 The construction of a routing zone requires a node to
first know who its neighbor, which is implemented
through a MAC layer Neighbor Discovery Protocol
2) Fisheye State Routing (FSR): There are multi-level fisheye
scopes to reduce routing update overhead in large
networks
 It helps to make a routing protocol scalable by
gathering data on the topology, which may be needed
soon
3) Landmark Routing (LANMAR): Uses a landmark to keep
track of a logical subnet
 The LANMAR routing table includes only those nodes
within the scope and the landmark nodes themselves
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
33
++SKIP++ 13.7. Hybrid routing protocols – cont. 2
4) Location-Aided Routing (LAR): Exploits location information
to limit the scope of routing
 LAR limits the search based on the expected location of
the destination node and thereby restricts and controls
the flood of Route Request packets
5) Distance Routing Effect Algorithm for Mobility (DREAM) :
Based on the distance effect and a node’s mobility rate
 Each node can optimize the frequency at which it sends
updates to the networks and correspondingly reduce the
bandwidth and energy used
6) Relative Distance Micro-discovery Ad Hoc Routing
(RDMAR): Based on the calculated relative distance
between two terminals
 The query flood is localized to a limited region centered
at the source node
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
34
++SKIP++ 13.7. Hybrid routing protocols – cont. 3
7) Power Aware Routing: Power-aware metrics are used for
determining routes
 It reduces the cost, ensures that the mean time to node
failure is increased, without any further delay in packet
delivery
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
35
++SKIP++ 13.7.7B. Summary of Some
Characteristics of Selected Protocols
Protocol
Route
Flood for
Acquisi- Route
tion
Discovery
Delay for
Route
Discovery
Multipath
Capability
Effect of Route
Failure
DSDV Compute No
d a priori
No
No
Updates the
routing tables of all
nodes
WRP
Compute No
d a priori
No
No
Ultimately, updates
the routing tables
of all nodes by
exchanging MRL
between neighbors
DSR
Ondemand,
only
when
needed
Yes
Not
explicitly.
The
technique
of salvaging
may quickly
restore a
route
Route error
propagated up to
the source to erase
invalid path
Yes.
Aggressive
use of
caching
may reduce
flood
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
36
Summary of Some Characteristics of Selected Protocols – cont.
Protocol
Route
Acquisition
Ondemand,
only
when
needed
Flood for
Route
Discovery
Yes.
Controlled
use of
cache to
reduce
flood
Delay for
Route
Discovery
Yes
Multipath Effect of Route
Capability Failure
No,
although
recent
research
indicate
viability
Route error
propagated up to
the source to
erase invalid path
TORA
Ondemand,
only
when
needed
Basically
one for
initial route
discovery
Yes. Once the
DAG is
constructed,
multiple paths
are found
Yes
Error is recovered
locally
LAR
Ondemand,
only
when
needed
Reduced
Yes
by using
location
information
No
Route error
propagated up to
the source
ZRP
Hybrid
Only
outside a
source's
zone
No
Hybrid of updating
nodes' tables
within a zone and
propagating route
error to the source
AODV
Only if the
destination is
outside the
source's zone
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
37
++SKIP++ 13.7.8. Multipath Routing
Protocols

Pp. 324 - 333
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
38
13.8. Wireless Sensor Networks

Wireless sensor networks (WSNs)
 A class of ad hoc networks
 A collection of hundreds or thousands of tiny,
disposable (bec. low-cost) & low-power (bec. battery-operated)
sensor nodes


Communicating together to achieve an assigned task:
monitoring & analysis of an area
Sensor node in WSN
 Converts a sensed physical attribute (e.g., temperature)
into data
 Includes :
 Sensing module
 Communications module
 Computing module
 Memory module
 Power source (usually a battery)
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
39
13.8. Wireless Sensor Networks – cont. 1

Wired sensor networks
 Example: wired sensornet within a plane
 Known for years in many applications
 Monitor critical physical parameters
 Alert when anomalies perceived
 Sensor locations carefully predesigned
 Sensors distributed in strategic locations
 # of sensor nodes can be huge



As many as needed to cover the monitored area
Connected via wires
Fault tolerance requirements
 Avoid single points of failure
 If work unattended => can not repair if failed

E.g., in inhospitable or inaccessible milieus
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
40
13.8. Wireless Sensor Networks – cont. 2


Advances in technology enabled wireless sensornets
(WSNs)
 Esp. advances in miniaturization, low-cost sensors (&
multisensors), wireless communications, batteries
Low costs (due to advances in technology) enabled massive
deployment of WSN nodes
 No need for predesigned locations

Can drop them from a plane, a speeding car, etc.
=> no installation costs
(saves more)
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
41
13.8. Wireless Sensor Networks – cont. 3

Advantages of WSNs over wired sensornets
1) Ease of deployment

Deployed without careful design

E.g., dropped from a plane
2) Extended range

At the same cost can cover a larger area



No need for infrastructure
One large wired sensornet replaced by many smaller wireless
sensornets at the same cost
Can easily move from area to area
3) Fault tolerance



A design requirement!
Must tolerate node failures (maybe reduces monitoring accuracy)
Some fault tolerance is “natural”
 Bec. failure of a sensor node is “masked” by other nodes
collecting similar data in the same area
4) Mobility

No wires inhibiting mobility – not even for power

(batteries)
Still WSNs less mobile than ad hoc networks
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
42
13.8. Wireless Sensor Networks – cont. 4

Inherent limitations of WSNs
1) Limited energy (batteries, etc.)
2) Low-bandwidth transmission
3) Error-prone transmission
 Bec. xmitted at low power (Item 1 above) & over limited
badwidth (Item 2 above)
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
43
13.8. Wireless Sensor Networks – cont. 5

Design requirements for WSNs & their protocols
1) Maximize WSN lifetime
 Discussed below
2) Accommodate dynamic, fast-changing physical parameters affecting WSNs, such as:
(1) Power availability for nodes
(2) Positions of nodes
(3) Reachability

For a given node, which other nodes can it reach
(4) Types of tasks executed by nodes

I.e. what attributes
reports
(such as temperature)
the node monitors &
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
44
13.8. Wireless Sensor Networks – cont. 6

Dealing with limited energy:
 Design WSN & its protocols carefully to maximize WSN’s
lifetime
 One approach: balance energy use in such a way that
all nodes die at approximately the same time

Once this happens, can replace the whole sensornet

Better than replacing individual nodes
(impossible or
inconvenient)
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
45
13.8. Wireless Sensor Networks – cont. 7

Data exchange in WSN is fundamentally different than in
other wireless networks
 WSNs are data-centric networks
 The interest is in “what is the data?” rather than
“where is the data?”



E.g., WSNs focus on attributes
(e.g., temperature, velocity)
WSNs must efficiently respond to application/user
queries asking for data
=> WSNs require different routing protocols then MANETs
 Routing protocols for WSNs must be application-dataspecific
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
46
13.8. Wireless Sensor Networks – cont. 8

Challenges in design of (application-data-specific) routing protocols
for WSNs
1) No unique node ID to be used for routing


Which is typical in traditional wired/wireless networks
Bec. (#1) routing to/from a specific node is not required in datacentric WSNs


Recall: It does not matter “where is the data?”
Bec. (#2) with the large # of nodes in WSNs, ID would be large

ID might be larger than amount of actual data being xmitted
2) Nodes often send aggregated data, not raw data

Adjacent nodes may have similar data, so aggregation cuts traffic
3) Routing protocols must be application-specific and datacentric

Bec. WSNs are application-specific and data-centric

E.g., WSN may require protocol customized to very efficient delivery
of data on a single attribute (e.g., temperature)
 Could be very inefficient for delivery of data on other single
attribute, or delivery of multi-attribute data
4) Minimizing energy consumption
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
47
13.8. Wireless Sensor Networks – cont. 9

Features of an ideal WSN
1) Attribute-based addresses

Composed of a series of attribute-value pairs


Specify physical parameters to be sensed
Example attribute address: “temperature>100C, location=?”

All nodes that sense temperature>100C must report their locations
2) Location-awareness of nodes

A node often

(as in example in (1) above)
needs to know its location
Otherwise cannot provide sensed data (cf. example above)
3) Must react immediately to drastic environment changes


Necessary for time-critical monitoring applications
Can react slowly to non-critical changes/events

Saving bandwidth & energy at the cost of increased latency
4) Efficient handling of queries



Efficient xmission of queries from usesr/applications to appropriate
nodes
(=> need efficient routing!)
Efficient xmission of answers to queries from nodes to
users/applications (=> need efficient routing again!)
Can reply with larger latency for noncritical changes/events

E.g., can increase interval for reporting periodic data
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
48
13.8.1. Case Study of a WSN

A sample WSN use scenario

WSN with temperature sensors around a factory


Example queries:
1)
2)
3)
4)

To protect the factory & to protect population nearby
Report immediately if water temp. in the NE quadrant < 5C
Retrieve today’s avg. water temp. in the SW quadrant
For the next 2 hours, report if water temp. > 100C
Report in which areas water temp. was between 5C & 100C in
the past 2 hours
Conclusions for the scenario

Time-critical queries (as Query 1 above) must be answered
immediately

Data from various nodes should be aggregated to
reduce data traffic


Aggregation usually involves adjacent nodes
Queries are often “persistent” (or “duration-based”)
(as
Queries 2-4 above)

Some “instantaneous” queries

Involve a snapshot of a single network state
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
49
13.8.1. Case Study of a WSN – cont. 1

Types of user queries
1) Historical query
 Mainly for analysis of historical data stored at a BS
 E.g., “What was temp. 2 hours ago in the NW
quadrant?”
2) Instantaneous query (“one-time query“ in the textbook)
 As Query 1 above
 Gives a snapshot of a state of the network
 E.g., “What is the current temp. in the NW quadrant?”
3) Persistent query
 As Queries 2-4 above
 Mainly to monitor network over a time interval with
respect to some parameters
 E.g., “Report temp. in the NW quadrant for the next 2
hours.”
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
50
13.8.1. Case Study of a WSN – cont. 2

Important objectives for adapting to the inherently dynamic
nature of WSNs
1) Exploit spatial diversity & density of sensors/actuators
 Incl. building an adaptive node sleep schedule
2) Optimize the relationship between node density &
network size
3) Keep optimizing the tradeoffs between data redundancy &
bandwidth consumption
…Details below…
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
51
13.8.1. Case Study of a WSN – cont. 3
 Optimizing the tradeoffs between data redundancy &
bandwidth consumption involves:
a) Assuring that on deployment nodes are able to optimize
these tradeoffs while:
 Creating & assembling a network
 Adapting to device failures & degradation
 Managing mobility of sensor/actuator nodes
 Reacting to changes in tasks & sensing requirements
b) Adapting to traffic level
 Certain nodes may detect an event that triggers heavy
traffic
 At other times traffic may be light
c) Allowing fine control over WSN algorithms
 More than just turning it on/off

E.g., allow algorithms to optimize precision vs. energy
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
52
13.9. Fixed Wireless Sensor Networks

Fixed WSNs have pre-designed node locations
 Application specific
 Communicating via LOS infrared beam or conventional
wireless communications
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
53
13.10. Other Issues in Wireless Sensor
Networks

Note:
 I believe that such section is missing in the textboook
 The following issues are not just for Fixed WSNs, as
organization of the Chapter 13 suggests
… continued…
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
54
13.10.1. Classification of Sensor
Networks

Classification of sensor networks
 Proactive networks
 Nodes periodically switch on their sensors &
transmitters, sense the environment & transmit the
data of interest


Reactive networks
 Nodes react immediately to sudden or drastic changes
in the value of the sensed attribute
Once proactive/reactive network type is chosen, efficient
routing protocols must be designed
 Preferably using a suitable MAC sublayer protocol to avoid
collisions
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
55
13.10.2. Fundamentals of MAC Protocols
for Wireless Sensor Networks



We said: “Efficient routing protocols must be designed,
preferably using a suitable MAC sublayer protocol to avoid
collisions”
Radio xmission is broadcast in nature
Can “simulate” unicast by all but one node (addressee)
ignoring what they hear
 This “simulation” is done by the MAC sublayer
 Additionally, MAC coordinates accesses to the medium to
avoid collisions
 Coordinates by using appropriate channel allocation
schemes for WSNs (next)
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
56
13.10.2. Fundamentals of MAC Protocols for WSNs – cont. 1

Categories of channel allocation schemes for WSNs
1) Static channel allocation
 If there are N nodes, the bandwidth is divided into N
equal portions (divided => no interference)
 Can be divided in many ways:




In frequency (FDMA) / In time (TDMA) / In code (CDMA)
In space (SDMA: Space Division Multiple Access)
In OFDM (Orthogonal Frequency Division Multiplexing)
Works very well for small & fixed # of users
2) Dynamic channel allocation
 No fixed assignment of bandwidth
 Contention-based (collisions occur, resolved by retransmission)
 Works very well for dynamic # of users
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
57
13.10.2. Fundamentals of MAC Protocols for WSNs – cont. 2

Data transmission in WSNs can use either flat or hierarchical
topology

Hierarchical: forms clusters, uses them
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
58
Material required for the final exam
ENDS HERE
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
59
13.10.3. Flat Routing in Sensor Networks

Routing issues in WSNs
 In traditional wired networks each node is identified
by a unique address, which is used for routing
 Sensor networks, being data-centric do not, in
general, require routing to specific nodes
 Adjacent nodes may have similar data
 So it is desirable to aggregate these data & only
then send it
 The requirements for the sensor network change with
application, hence it is application-specific
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
60
13.10.3. Flat Routing in Sensor Networks – cont.

Protocols for collecting data to answer queries
1) Directed diffusion
 Query flooded throughout the network
 Events start from some specific points & move
outwards to reach the requesting node
 This type of data collection does not fully exploit the
feature of WSNs that adjacent nodes have similar data
2) Sensor Protocols for Information via Negotiation (SPIN)
 Disseminates the information at each node to every
node in the network
3) COUGAR
 This is a warehousing approach
 The data is extracted in a pre-defined manner and
stored in a central database (BS)


Query processing takes place on the BS
COUGAR is a unique model for query representation in
sensor networks
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
61
13.10.4. Hierarchical Routing
in Sensor Networks

Hierarchical Routing in Sensor Networks




Most suitable for WSNs
WSN consists of a Base Station (BS), away from the
nodes, through which the end user can access data from
the sensor network
BS can transmit with high power
Nodes cannot reply directly to the BS due to their low
power constraints, resulting in asymmetric communication
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
62
13.10.4. Hierarchical Routing – cont. 1
3.1
3.2
Base Station
3
3.3
2
2.3
1.0.1
1.0.2
1
2.1
2.2
1.2.5
1.2.4
1.0.3
1.2
1.1.2
1.1
1.1.3
1.1.4
1.1.1
1.2.3
1.2.1
1.2.2
1.1.5
Simple sensor node
First Level Cluster Head
Second Level Cluster Head
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
63
13.10.4. Hierarchical Routing – cont. 2

Hierarchical routing protocols
1) Cluster-Based Routing Protocol (CBRP)
 Here the cluster members just send the data to the
cluster head (CH)
 The CH routes the data to the destination
 Not suitable for a highly mobile environment, as a
lot of HELLO messages are sent to maintain the
cluster
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
64
13.10.4. Hierarchical Routing – cont. 3
2) Low-Energy Adaptive Clustering Hierarchy (LEACH)
 LEACH is a family of protocols
 It contains both distributed and centralized schemes
 Use proactive updates
 It utilizes randomized rotation of local cluster heads
(CHs) to evenly distribute the energy load among
sensors
 It makes use of a TDMA/CDMA MAC scheme to reduce
inter and intra-cluster collisions
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
65
13.10.4. Hierarchical Routing – cont. 4
3) Threshold-sensitive Energy Efficient Network protocol
(TEEN)
(a reactive network routing protocol)
 Targeted at reactive networks


The first protocol developed for such networks
At every cluster change time, the CH broadcasts the
following to its members:
 Hard threshold (HT): a threshold value for the sensed
attribute

Soft threshold (ST): a small change in the value of the
sensed attribute which triggers the node to switch on its
transmitter and transmit
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
66
13.10.4. Hierarchical Routing – cont. 5
Parameters
Attribute > Threshold
Cluster Formation
Cluster Change Time
Cluster Head Receives Message
Time Line for TEEN
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
67
13.10.4. Hierarchical Routing – cont. 6




The nodes sense their environment continuously
The first time a parameter from the attribute set
reaches its hard threshold value, the node
switches on its transmitter and sends the sensed
data
The sensed value is stored in an internal variable,
called Sensed Value (SV)
The nodes will transmit data in the current
cluster period only when the following conditions
are true:
 The current value of the sensed attribute is
greater than the hard threshold
 The current value of the sensed attribute
differs from SV by an amount equal to or
greater than the soft threshold
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
68
13.10.4. Hierarchical Routing – cont. 7

Important features of TEEN
 Suitable for time-critical sensing applications
 Message transmission consumes more energy than data
sensing




So the energy consumption in this scheme is less than the
proactive networks
The soft threshold can be varied
At every cluster change time, the parameters are
broadcast afresh, so the user can change them as
required
The main drawback: If the thresholds are not reached,
then the nodes will never communicate
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
69
13.10.4. Hierarchical Routing – cont. 8
4) Adaptive Periodic Threshold-sensitive Energy Efficient
Network protocol (APTEEN)
Functioning:
 The cluster heads broadcasts the following
parameters:
 Attributes (A): This is a set of physical parameters
which the user is interested in obtaining data
about
 Thresholds: This parameter consists of a hard
threshold (HT) and a soft threshold (ST)
 Schedule: This is a TDMA schedule, assigning a
slot to each node
 Count Time (CT): It is the maximum time period
between two successive reports sent by a node
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
70
13.10.4. Hierarchical Routing – cont. 9
TDMA Schedule and
Parameters
Slot for Node i
Cluster Formation
Frame Time
Cluster Change Time
Time line for APTEEN
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
71
13.10.4. Hierarchical Routing – cont. 10





The node senses the environment continuously
Only those nodes which sense a data value at or beyond
the hard threshold transmit
Once a node senses a value beyond HT, it next transmits
data only when the value of that attribute changes by an
amount equal to or greater than the ST
If a node does not send data for a time period equal to the
count time, it is forced to sense and retransmit the data
A TDMA schedule is used and each node in the cluster is
assigned a transmission slot
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
72
13.10.4. Hierarchical Routing – cont. 11

Main features of the APTEEN scheme:
 It combines both proactive & reactive policies
 It offers a lot of flexibility by allowing the user to
set the count-time interval (CT) & the threshold
values for the attributes
 Energy consumption can be controlled by changing
count time & threshold values
 Main drawback: additional complexity required to
implement threshold functions & count time
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
73
13.10.5. Hierarchical Versus Flat Topologies
for Sensor Networks
Hierarchical
Flat
Reservation-based scheduling
Contention-based scheduling
Collisions avoided
Collisions present
Reduced duty cycle due to periodic
sleeping
Variable duty cycle by controlling sleep
time of nodes
Data aggregation by cluster head
Node on multi-hop path aggregates
incoming data from neighbors
Simple but non-optimal routing
Routing is complex but optimal
Requires global and local synchronization
Links formed on the fly, without
synchronization
Overhead of cluster formation throughout
the network
Routes formed only in regions that
have data for transmission
Lower latency as multi-hop network
Latency in waking up intermediate
formed by cluster-heads is always available nodes & setting up the multi-hop path
Energy dissipation is uniform
Energy dissipation depends on traffic
patterns
Energy dissipation can not be controlled
Energy dissipation adapts to traffic
pattern
Fair channel allocation
Fairness not guaranteed
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved
74
The End of Section 10 (Ch. 13)
75