Transcript Localized Clustering algorithm

Next Century Challenges:
Scalable Coordination in
sensor Networks
MOBICOMM (1999)
Deborah Estrin, Ramesh Govindan, John
Heidemann, Satish Kumar
Presented by
Mohammed Alam (shahed)
1
OUTLINE







Introduction
Challenges to Sensor Networks
Localized Algorithms for Coordination
Directed Diffusion
Related Work
Summary
Discussion
2
NETWORKED SENSORS

Sensor devices coordinating to achieve larger
sensing task.

EXAMPLE:




Tracking inventory
Tracking motion of vehicles
Temperature
Noise level
3
EXAMPLES of Sensors
TINY OS
29 Palms Fixed/Mobile Experiment
Tracking vehicles with a UAV-delivered
sensor network
4
Design Challenges

Sheer number of devices




Rule out traditional network device management
Ratio of communicating nodes to users much
larger (1000 :1).
Impossible to concentrate on specific sensors.
Power constraint

Device failure common

Battery supply limited
5
Design Challenges

Frequent change in position



Sensors added
Sensors moved
Sensors removed
 Out of power
 Damaged
 Unreachable
6
Proposed Design Features

Data Centric




Sensors do not need identity (no IP address)
Application focus on data having attributes
Communication primitive : “request” for data
Application Specific


Intermediate nodes cache and aggregate
application specific data
Forwarding requests (like routers)
7
Proposed Solution

Localized Algorithm

Distributed algorithm

Sensors interact in restricted area

Collectively achieve global objective
8
Localized algorithm

Achieved using clustering of sensors
(Localized Clustering algorithm).

Advantages:



Scalability
Improved robustness
Efficient resource utilization (battery power)
9
Clustering in Sensor Networks
Child Sensor
Parent Sensor
10
Goal of
Localized Clustering algorithm

Elect cluster-head sensor such that each
sensor has a cluster-head as parent.

no asymmetric connections

Cluster adapts to network dynamics and
changing energy level of nodes
11
Localized Clustering algorithm

Assume link level procedure on sensor

Adjusts Communication range by tweaking
transmission power to minimum value for full
network connectivity.
12
Localized Clustering algorithm

Assume a multi-level cluster formation

Associate sensors at a level with radius

Radius: Number of physical hops sensor
advertisement will travel

Sensors at higher level = larger radii.
13
Localized Clustering algorithm
Level1
1
2
3
4
Level 0
14
Localized Clustering algorithm
Level1
Send advertisements
1
2
3
4
Level 0
15
Localized Clustering algorithm
Level1
Start promotion timers
Send advertisements
1
2
3
4
Level 0
16
Localized Clustering algorithm
1
Level1
3
promote
2
4
Level 0
17
Localized Clustering algorithm
1
Level1
3
Notify potential children
2
4
Level 0
18
Localized Clustering algorithm
1
Level1
3
Select parent
2
4
Level 0
19
Localized Clustering algorithm
Level1
3
Demote (no child)
1
2
4
Level 0
20
Localized Clustering algorithm
Level1
3
Select parent
1
2
4
Level 0
21
Localized Clustering algorithm



All sensors start at level 0.
Sensors send periodic advertisement to
sensors within radius hops.
Advertisements carry:



Hierarchy level
Parent ID (if any)
Remaining energy in sensor
22
Localized Clustering algorithm

After sending advertisements:


Sensors wait for wait time (proportional to radius).
At end of wait time, if sensor does not have
parent



Level 0 sensor starts promotion timer.
Promotion timer inversely proportional to remaining
energy and number of level 0 advertisements
received.
Smaller time out value for sensors in dense regions
with more power.
23
Localized Clustering algorithm

After promotion timer expires:



Sensor promotes itself to level 1.
Sends periodic advertisements at level 1 radius.
Advertisement lists potential child sensors:



Sensors whose advertisement received in level 0.
The child sensors in lower level chooses the
closest parent.
All sensors keep checking (parent, child) after
wait time period.
24
Localized Clustering algorithm

If battery power of parent sensor less than
certain threshold compared to children


Parent sensor drops a level down.
Election takes place so that a new parent
selected with more power.
25
Difficulty of
Localized Algorithms

Should provide desired global behavior with
indirect global knowledge


Converting centralized algorithm to distributed.
Difficulty in designing adaptability to different
environments and converge to global behavior
over range
26
Solutions to overcome
disadvantage

Adaptive Fidelity Algorithm


Quality of answer traded against battery life,
network bandwidth or number of active sensors
Develop Techniques for characterizing
performance of Localized Algorithms

sacrifice resource utilization, responsiveness
27
Directed Diffusion


Set of abstractions that describe
communication pattern in localized
algorithms.
Sensors name data that it generates.



Data contains attributes.
Other nodes express interests based on
attributes.
Network nodes propagate interests.
28
Directed Diffusion


Interest on data creates gradients that direct
diffusion of data.
Gradients are data dissemination path from
source to sink (requesting information)
nodes.
29
Example of Directed Diffusion
SOURCE
Gradient
SINK
30
Related Work

Ad-hoc Networks

Proactive vs. reactive routing protocols


Distributed Robotics


Energy-efficiency issues
Robots cooperate to discover entire map
Internet Multicast and web caching

Lightweight session
31
Current Developments

Smartdust project:






cubic millimeter sensors
Sensors float in air like dust
WINS (wireless integrated wireless Sensors)
WSN (Wireless Sensing Network)
Odyssey
Habitat monitoring

Great Duck Island
32
Summary


Manage sensor networks using localized
algorithm
Advantages of localized algorithm



Robustness, Energy efficient, manage sheer
numbers
Cluster approach for localization
Directed Diffusion for communication among
sensors
33
QUESTIONS
34
DISCUSSION
35
References







http://robotics.eecs.berkeley.edu/~pister/29Palms0103/
http://www.eecs.berkeley.edu/IPRO/Summary/01abstract
s/szewczyk.1.html
http://nms.lcs.mit.edu/projects/leach/
http://citeseer.nj.nec.com/context/1822734/0
http://www.cens.ucla.edu/Estrin/index.shtml
http://www.greatduckisland.net/images.php
www.mdpi.net/sensors/papers/s20700286.pdf
36