Transcript Topology Management --Power Efficient Spatial Query

Topology Management
--Power Efficient Spatial Query
Presented by
Weihang jiang
Today’s plan


Introduction: 10-15 mins
Details :
• heuristic algorithm 15 mins
• Greedy



Centralized
Decentralized
Questions
10mins
5mins
Problem definition

Select a small number of sensors
that are sufficient to answer the
query accurately. Also these selected
sensors should form a connected
communication path, so that they
form a logical routing topology
Context of research
Sensor Database
[4]
Art Gallery
Problem
[20,10]
Query operation
Optimal placement VS
Optimal selections
Geometric set
cover problems
[16 ,17 ,5]
Broadcast
MDCS [14]
[9,18,26,1,
17]
Power efficient
organization[25]
Decentralized, cost
of communication
Notion of
connectivity
Connected sensor
Cover
Sensor database




P. Bonnet, J. Gehrke, and P. Seshadri. Towards sensor database systems.
In Proc. of Intl. Conf. on Mobile Data Management, 2001.
Example
• Factory Warehouse
Sensor Database
• stored data: the set of sensors and environment
• sensor data: produced by signal processing functions.
Query
• Monitoring queries are long running.
• The desired result of a query is typically a series of notifications of
system activity
• Queries need to correlate data produced simultaneously by different
sensors.
• Queries need to aggregate sensor data over time windows.
• Most queries contain some condition restricting the set of sensors that
are involved (usually geographical conditions).
Back
Art Gallery Problem



DEMO:
http://valis.cs.uiuc.edu/~sariel/resea
rch/CG/applets/art_gallery/artgal.ht
ml
http://www.cs.mcgill.ca/~thierry/50
7applet/triangulize.html
Back
Art Gallery Problem
Broadcast
-- MDCS


The idea is to suppress redundant
broadcast by using only a small
number of nodes to broadcast, but
ensuring that all the nodes in the
network receive the broadcast
message
Coverage: all the area
Back
Back
Power efficient organization
Power Efficient Organization of Wireless Sensor
NetworksSasa Slijepcevic, Miodrag Potkonjak



Choose nodes rather than deploy
nodes
Divide sensors into mutually
exclusive sets, each of those sets
completely covers query area
•Power saving
Divide to as many groups as possible
Algorithm

Definition of field
• A set of points. Two points belong to
the same field iff they are covered by
the same set of sensors

Critical Element
• A field covered by the minimal number of sensors
• 2,3,6,8 are critical elements

Find as many as possible exclusive covering sets
• 1) Start with a critical element
• 2) Then use objective function to choose one sensor which covers
this critical element
• 3) If now all the chosen sensor cover the query area
• we got one exclusive covering set Goto 1)
Else
• Goto 1)
objective function




(1) favor sets that cover a high number of
uncovered elements (less sensors)
(2) favor sets that cover more sparsely
covered elements
(3) favor sets that do not cover the area
redundantly (more exclusive sets)
(4) favor sets that redundantly cover the
elements that do not belong to sparsely
covered areas
The heuristic
Power efficient organization(cont)

Drawbacks
•Centralized
•Communication cost
Back
Connected sensor
Cover
Compared with breath first flooding D+2qm VS 2qn (n>>m)
Back
Important definitions

Subelement; Valid Subelement
• = Field ; a field in query area

Candidate Sensor; Candidate path
• A sensor contains a Subelement which has not
been chosen
• A path connects a candidate sensor with
previously chosen sensors

Uncovered Valid Subelement; Benefit of a
Candidate path
• Benefit = # of uncovered Valid Subelement / #
of sensor on the path but not chosen
Greedy algorithm (centralized)




Start with chosen sensor set M (the
original sensor)
Find out SC (set of candidate
sensors)
Basing on Benefit of a Candidate
path, choose one candidate sensor,
add it and the path into M
Goto beginning
Decentralized


Instead send Candidate Path Search
to the SC (set of candidate sensors,
which is hard to find out locally),
send CPS to the Candidate sensors
around newest added sensor
Seems no much impact on # of
selected sesors
END!!!
Question???
Motivation

Sensor Database

Limited Battery Power
Overview

Motivation