Transcript COT 6930 Ad Hoc Networks (Part III)

COT 6930 Ad Hoc Networks
(Part III)
Jie Wu
Department of Computer
Science and Engineering
Florida Atlantic University
Boca Raton, FL 33431
Table of Contents
Introduction
 Infrastructured networks

Handoff
 location management (mobile IP)
 channel assignment

Table of Contents (cont’d.)

Infrastructureless networks
Wireless MAC (IEEE 802.11 and Bluetooth)
Security
Ad Hoc Routing Protocols
Multicasting and Broadcasting
Table of Contents (cont’d.)

Infrastructureless networks (cont’d.)
Power Optimization

Applications
Sensor networks and indoor wireless
environments
Pervasive computing

Sample on-going projects
Security
Security goals (Zhou and Hass, IEEE Network,
1999):

Availability


Confidentiality


Survivability of network services despite
denial of service attacks
Certain information is never disclosed to
unauthorized entities
Integrity

Message being transferred is never corrupted
Security

Authentication
• Enables a node to ensure that the identity
of the peer node it is communicating with.

Non-repudiation
• The origin of a message cannot deny
having sent the message
Security

Challenges in ad hoc network
security
The nodes are constantly mobile
 The protocols implemented are cooperative in nature
 There is a lack of a fixed infrastructure
to collect audit data
 No clear distinction between normalcy
and anomaly in ad hoc networks

Security

Type of attack

External attack: An attack caused by nodes
that do not belong to the network.

Internal attack: An attack from nodes that
belong to the network due to them getting
compromised or captured.
Security

Some objectives:
Ad hoc networks should have a
distributed architecture with no central
entities to achieve high survivability
 Because of frequent changes in
topology, trust relationship among
nodes in ad hoc networks also changes.
 Security mechanisms should be
scalable to handle a large network.

Security
Sample security attacks:




Passive eavesdropping
Active impersonation
Message reply
Message distortion
Security

Traditional approaches
Authentication protocols
 Digital signature
 Encryption

Security

Secure key management

Threshold cryptography
• The public key is known to all whereas the
private key is divided into n shares.
• Decentralized Certification Authority to
distribute key pairs.
• The private key can be constructed with
any subset of shares of certain sizes.
Security

Proactive security
• Share refreshing: servers compute new shares from
old ones in collaboration without disclosing the
service private key to any server

Asynchrony
• Cannot distinguish a compromised server from a
correct but slow one
• Weak consistency: do not require that the correct
servers to be consistent after each operation;
instead, only enough correct servers need to be upto-date.
Security

Secure routing

External attack: injecting erroneous routing
information or distorting routing information

Internal attack: compromised node
advertise incorrect routing information
(similar to the Byzantine general problem)
Security
Security problems in AODV and DSR

(Dahill, UM-CS-2001-037)
Remote redirection
• Sequence number (AODV)
• Hop count (AODV)
• Source route (DSR)


Spoofing (impersonation) (AODV and DSR)
Fabrication
• Error message (AODV and DSR)
• Source route (DSR)
Power Optimization

Network Longevity (Wieselthier, Infocom
2002)
 Time at which first node runs out of energy
 Time at which first node degrades below an
acceptable level
 Time until the network becomes disconnected

High throughput volume

High total number of bits delivered
Power Optimization
Two related goals
(Toh, IEEE Comm. Mag.
2001)
Saving overall energy consumptions
in the networks
 Prolong life span of each individual
node

Power Optimization
Source of Power Consumption
al, MobiCom 1998)

Communication cost
• Transmit
• Receive
• Standby

Computation cost
(Singh et
Power-Aware Routing

Wu et al’s Power-aware marking
process (Wu et al, ICPP 2001)
Use energy level as priority in Rule 1
and Rule 2 of marking process
 Balance the overall energy consumption
and the lifespan of each node

Location-Based Routing


Let P(dis) represent the power
consumption of transmitting with distance
dis
Stojmenovic et al’s greedy method
(Stojmenovic et al, IPDPS 2001)


Each node knows the location of destination
and all its neighbors
Source s selects a neighbor n to reach
destination d with minimum
P(dis(s,n))+P(dis(n,d))
Adjustable Transmission
Ranges
Power level of a transmission can be
chosen within a given range of
values

 Transmission cost: P( dis )  d
where a=2 or 4.

Uniform Transmission
Range
Problem: Use a minimum uniform
transmission range to connect a given set
of points
Greedy algorithms
Binary search
 Kruskal’s MST (Ramanathan & Rosales
Hain, ICC 2000)

Prim’s MST (Dai & Wu, FAU 2002)
Power Optimization
Kruskal’s MST:
Each node is initialized as a separate
connected component
 Edges are sorted and traversed in nondecreasing order
 An edge is added to the MST whenever
it connects any two connected
components.

Power Optimization
Prim’s algorithm
The approach starts from an arbitrary
root and grow a single tree until it
spans all the vertices.
 At each step, an edge of lightest
possible weight is added.

Non-uniform transmission
range
Wireless multicast advantage
(Wieselthier, Infocom 2000):
Pi ,( j ,k )  max{ Pik , Pij }
where Pij is power needed between
node i and node j
Non-uniform transmission
range

S broadcasts to two destinations: D1
and D1 (r1=dis(s, D1), and r2=dis(s, D2)).
Direct: S broadcasts to both at the
same time
 Indirect: S sends the packet to D1
which then relays the packet to D2

Non-uniform transmission
range

Use “direct” if r1  r2 cos , where


angle between r and r
1
2
Non-uniform transmission
range

Broadcast incremental power
algorithm (Wieselthier Infocom 2000)
Standard Prim’s algorithm
 Pair {i, j} that results in the minimum
incremental power for i to reach j is
selected, where i is in the tree and j is
outside the tree.

Non-uniform transmission
range

Other algorithms
Broadcast least-unicast-cost algorithm
 Broadcast link-based MST algorithm


The sweep: removing unnecessary
transmissions
Non-uniform transmission
range

Extensions to directional antennas
(Wieselthier, Infocom 2002)

Energy consumption:
r



300
Extended power incremental algorithm
Non-uniform transmission
range

Possible extensions
Fixed beamwidth
 Single beam per node
 Multiple beams per node
 Limited multiple beams per node
 Directional receiving antennas

Non-uniform transmission
range

Incorporation of resource limitation

Bandwidth limitation
• Greedy frequency assignment, but cannot
ensure coverage (when running out of
frequencies)

Energy limitation
Ei (0) 
Pij  Pij (
)
Ei (t )
'
Sensor Networks

Sensor networks (Estrin, Mobicom
1999)





Information gathering and processing
Data centric: data is requested based on
certain attributes
Application specific
Energy constraint
Data aggregation (also data fusion)
Sensor Networks

Military applications:
(4C’s) Command, control,
communications, computing
 Intelligence, surveillance,
reconnaissance
 Targeting systems

Sensor Networks

Health care
• Monitor patients
• Assist disabled patients

Commercial applications
• Managing inventory
• Monitoring product quality
• Monitoring disaster areas
Sensor Networks
Design factors
(Akyildiz et al, IEEE Comm.
Mag. Aug. 2002)
 Fault Tolerance (sustain functionalities)
 Scalability (hundreds or thousands)
 Production Cost (now $10, near future $1)
 Hardware Constraints
 Network Topology (pre-, post-, and redeployment)
 Transmission Media (RF (WINS), Infrared
(Bluetooth), and Optical (Smart Dust))
 Power Consumption (with < 0.5 Ah, 1.2 V)
Sensor Networks

Sample problems
Coverage and exposure problems
 Data dissemination and gathering

Coverage and Exposure
Problems

Coverage problem



Quality of service (surveillance) that can be
provided by a particular sensor network
Related to to Art Gallery Problem (solved
optimally in 2D, but NP-hard in 3D)
Exposure problem

(Meguerdichian, Infocom 2001)
(Meguerdichian, Mobicom 2001)
A measure of how well an object, moving on
an arbitrary path, can be observed by the
sensor network over a period of time
Coverage and Exposure
Problems

Voronoi diagram of a set of points

Partitions the plane into a set of convex
polygons with such that all points inside
a polygon are closest to only one point.
Coverage and Exposure
Problems

A sample Voronoi diagram
Coverage and Exposure
Problems

Delaunay triangulation


Obtained by connecting the sites in the
Voronoi diagram whose polygons share a
common edge.
It can be used to find the two closest points
by considering the shortest edge in the
triangulation.
Coverage and Exposure
Problems

Maximal breach path
(worst case
coverage)
 A path p connecting two end points such that
the distance from p to the closest sensor is
maximized
 Fact: The maximal breach path must lie on
the line segments of the Voronoi diagram.
 Solution: binary search + breadth-first search
Coverage and Exposure
Problems

Maximal Support Path
(Best Case
Coverage)
 A path p with the distance from p to the
closest sensor is minimized
 The maximal support path must lie on the
lines of the Delaunay triangulation
Coverage and Exposure
Problems

Exposure problem
Expected average ability of serving a
target in the sensor field
 General sensing model:

S ( s, p ) 
dis ( s, p )

where s is the sensor and p the point.
Coverage and Exposure
Problems

Exposure problem:
function
integral of the sensing
Coverage and Exposure
Problems

Minimal Exposure Path



Transform the continuous problem domain to
a discrete one.
Apply graph-theoretic abstraction.
Compute the minimal exposure path using
Dijkstra’s algorithm.
Coverage and Exposure
Problems
First, second, and third-order generalized 2*2 grid
Data Dissemination and Gathering

Two different approaches


Traditional reverse multicast/broadcast tree
with BS as the sink (root).
Three-phase protocol: sinks broadcast the
interest, and sensor nodes broadcast an
advertisement for the available data and wait
for a request from the interested nodes.
Data Dissemination and Gathering

Energy-efficient route (Akyildiz, 2002)




Maximum total available energy route
Minimum energy consumption route
Minimum hop route
Maximum minimum available energy node
route
Data Dissemination and Gathering

Sample data aggregation protocols






SMECN (Li and Halpern, ICC’01)
SPIN (Heinzelman et al, MobiCom’99)
SAR (Sohrabi, IEEE Pers. Comm., Oct. 2000)
Directed Diffusion (Intanagonwiwat et al,
MobiCom’00)
Linear Chain* (Lidsey and Raghavendra, IEEE
TPDS, Sept. 2002)
LEACH * (Heinzelman et al, Hawaii Conf.
2000)
Data Dissemination and Gathering

SMECN


SPIN


Create a subgraph of the sensor network that
contains the minimum energy path
Sends data to sensor nodes only if they are
interested; has three types of messages (ADV,
REQ, and DATA)
SAR

Creates multiple trees where the root of each
tree is one hop neighbor from the sink; select
a tree for data to be routed back to the sink
according to the energy resources and
additive QoS metric
Data Dissemination and Gathering

Directed diffusion


Linear Chain


Sets up gradients for data to flow from source
to sink during interest dissemination (initiated
from the sink)
A linear chain with a rotating gathering point.
LEACH

Clusters with clusterheads as gathering
points; again clusterheads are rotated to
balance energy consumption
Data Dissemination and Gathering

Sequential gathering in a linear chain
Data Dissemination and Gathering

Parallel gathering (recursive double)
Data Dissemination and Gathering

Enhancement


Multiple chain
Better linear chain formation
• New node always the new head of the linear chain
• New node can be inserted into the existing chain
Data Dissemination and Gathering

Multiple Chains
Data Dissemination and
Gathering

Simple chain (new node as head of chain)
Data Dissemination and Gathering

Simple chain (new node inserted in the
chain)
Data Dissemination and Gathering

LEACH
Data Dissemination and Gathering

Extended LEACH (energy-based)
Indoor Environments

Three popular technologies
Wireless LANs (IEEE 802.11 standard)
 HomeRF (http://www.homerf.org/tech/,

Negus et al, IEEE Personal Comm. Feb. 2000)

Bluetooth (http://www.bluetooth.com/)
Indoor Environments

Network topology


Straightforward for 802.11WLAN and
HomeRF (e.g., In TDMA-based MAC protocol,
a central entity is used to assign slots to the
stations).
The Bluetooth topology poses interesting
challenges.
Bluetooth

Bluetooth Special Interest Group (formed
in July 1997 with now 1200 companies).



Major technology for short-range wireless
networks and wireless personal area
network.
An enabling technology for multi-hop ad
hoc networks.
Low cost of Bluetooth chips (about $5 per
chip).
Bluetooth

Basic facts




Operates in the unlicensed Industrial-ScienceMedical (ISM) band at 2.45 GHz.
Adopts frequency-hop transceivers to combat
interference and fading.
The nominal radio range: 10 meters with a
transmit power of 0 dBm.
The extended radio range: 100 meters with
amplified transmit power of 20 dBm.
Bluetooth: Basic Structure

Piconet





A simple on-hop star-like network
A master unit
Up to 7 active slave units
Unlimited number of passive slave units.
Scatternet


A group of connected piconets
A unit serves as a bridge between the
overlapping piconets in proximity.
Bluetooth: Basic Structure

Open problem: a method for forming an
efficient scatternet under a practical networking
scenario.

Two methods: Bluetree and Bluenet
Bluetree (Zaruba, ICC 2001)

Blueroot Grown Bluetrees



The blueroot starts paging its neighbors one
by one.
If a paged node is not part of any piconet, it
accepts the page (thus becoming the slave of
the paging node).
Once a node has been assigned the role of
slave in a piconet, it initiates paging all its
neighbors one by one, and so on.
Bluetree (Zaruba, ICC 2001)

Blueroot Grown Bluetrees (sample)
Bluetree (Zaruba, ICC 2001)

Limiting the number of slaves



Observations: if a node has more than five
neighbors, then there are at least two nodes
that are neighbors themselves.
The paging number obtains the neighbor set
of each neighbor.
Balanced Bluetree (Wu and ?, 2003)


Using neighbors’ neighbor sets.
Using neighbor locations.
Bluetree (Zaruba, ICC 2001)

Distributed Bluetrees


Speed up the scatternet formation process by
selecting more than one root (phase 1).
Then by merging the trees generated by each
root (phase 2).
Bluetree (Zaruba, ICC 2001)

Phase 1



Each slave will be informed about the root of
the tree.
When paging nodes are in the tree,
information of respective roots are
exchanged.
Each node having roles from the set {M, S,
(MS)}, where M for master and S for slave.
Bluetree (Zaruba, ICC 2001)

Phase 2
Merge bluetrees (pairwise)
 Each node can only receive at most one
additional M, S, or MS.
 Each node having roles from the set:
{M, S, (MS), (SS), (MSS)} (note that
(MM)=M).

Bluetree (Zaruba, ICC 2001)

Distributed bluetree (sample)
Bluetree (Zaruba, ICC 2001)

Overflow problem (Wu)
u

Solution:
v
slot reservation (up to 6 slaves)
Bluenet (Wang et al, Hawaii
Conf. 2002)

Drawbacks of bluetrees
Lacks of reliability
 Lacks of efficient routing
 Parents nodes are likely to become
communication “bottleneck”.


Three types of nods in Bluenet

Master (M), Slave (S), Bridge (M/S or
S/S)
Bluenet (Wang et al, Hawaii
Conf. 2002)
Rule 1: Avoid forming further
piconets inside a piconet.
 Rule 2: For a bridge node, avoid
setting up more than one
connections to the same piconet.
 Rule 3: Inside a piconet, the master
tries to aquire some number of
slaves (not too many or too few).

Bluenet (Wang et al, Hawaii
Conf. 2002)
Phase 1: Initial piconets formed with
some separate Bluetooth nodes left.
 Phase 2: Separate Bluetooth nodes
get connected to initial piconets.
 Phase 3: Piconets get connected to
form a scatternet (slaves set up
outgoing links).
 Dominating-set-based bluenet?

NeuRFon (Motorola Research
Lab., ICCCN 2002)
Build a reverse shortest path tree
(w.r.t. a given root) through paging.
 Self-healing: find a new parent with
a lowest-level number (cloested to
the root).

On-going projects

Internet P2P applications
(http://www.p2pwg.org)




Distributed systems in which nodes of equal
roles and capabilities exchanges information
and services directly with each other.
Servant for both server/client.
Major issue: efficient techniques for search
and retrieval of data.
Sample systems: Gnutella, Napster, and
Morpheus.
On-going projects

Basics of P2P protocols



Searching: query-source sends “query-send”
with file id through controlled flooding
Network dynamic: A peer joins the network
through “broadcast-send” to select “logical
neighbors” (neighborhood with short session
duration, 2 hours per day on average).
Transferring files: The query-source servant
establishes the end-to-end communication
with the file-source (datagram transmission
after the file is fragmented in small pieces).
On-going projects

Basics of P2P protocols (cont’d)


Controlled flooding: caches (query-id,
query-source) to avoid duplicate query
processing and uses TTL to prevents a
message being forwarded infinitely.
Neighborhood control: uses the “pingpong” protocol for maintaining up-to-date
neighbors and issues “broadcast-send” to find
another neighbor when the current one is lost.
On-going projects

Sample P2P search protocols (ICDCS
2002)




Iterative deepening: multiple breadth-first
searches with successively large depth limits.
Directed BFS: sending query messages to
just a subset of its neighbors.
Local indices: each node maintaining an
index over the data of all nodes.
Mobile agents: swarm intelligence – the
collection of simple ants achieve “intelligent”
collective behavior.
On-going projects

Sensor nodes

Smart dust
(http://robotics.eecs.berkeley.edu/~pis
ter/SmartDust)
• Autonomous sensing and communication in
a cubic millimeter
• Macro motes: 20 meter comm. range, one
week lifetime in continuous op. and 2 years
with 1% duty cycling.
On-going projects

Sensor nodes

Smart dust
(http://robotics.eecs.berkeley.edu/~pister/Sm
artDust)
• Autonomous sensing and communication in a cubic
millimeter
• Macro motes: 20 meter comm. range, one week
lifetime in continuous op. and 2 years with 1% duty
cycling.

PicoRadio
(http://bwrc.eecs.berkeley.edu/Research/Pico
_Radio/PN3/)
On-going projects

Power-Aware Ad Hoc and Sensor
Networks

μAMPS (μ-Adaptive Multi-domain Power
aware Sensors) (http://wwwmtl.mitedu/research/icsystems/uamps)
• Innovative energy-optimized solution at all
levels of the system hiearchy

PACMAN (http://pacman.usc.edu)
On-going projects

Sensor Networks

WINS (Wireless Integrated Network
Sensors) (http://www.janet.ucla/WINS)
• Distributed network and internet access to
sensors, controls, and processors that are
deeply embedded in equipment.

SensoNet
(http://www.ece.gatech.edu/research/l
abs/bwn)
On-going projects

Distributed Algorithms

SCADDS (Scalable Coordination
Architectures for Deeply Distributed
Systems) (http://www.isi.edu/scadds)
• Directed diffusion, adaptive fidelity,
localization, time synchronization, selfconfiguration, and sensor-MAC
On-going projects

Power conservation algorithms
Span (Chen et al, MIT).
 PAMAS (Power Aware Multi Access
protocol with Signaling for Ad Hoc Net
works) (Singh, SIGCOMM, 1999).

On-going projects

Distributed query processing
COUGAR device database project
(http://www.cs.cornell.edu/database/c
ougar/index.htm)
 Database
(http://cs.rutgers.edu/dataman/)

On-going projects

Security for Sensor Networks

SPINS (Security Protocols for Sensor
Networks)
(http://www.ece.cmu.edu/~adrian/proj
ect.html)