Transcript Solving Generic Role Assignment Exactly

Solving Generic Role Assignment Exactly
Christian Frank and Kay Römer
ETH Zurich, Switzerland
Apr 26th, 2006
Programming Abstractions for WSN
 Task at hand on a higher level:


Retrieve data from network
(TinyDB)
Assign different functions to
network nodes (Role Assignment)
 Wireless Sensor Networks



Apr 26th, 2006
Small sensing devices,
communicating wirelessly
Allow unobtrusive monitoring of
physical processes
Programmed as a distributed
system
Christian Frank <[email protected]>
read_sensor()
send_msg()
get_pos()
2
Role Assignment Problems
 Coverage


Roles ON, OFF
ON nodes cover every geographic spot
 Clustering

Roles: Clusterhead, Gateway, Slave
 Connected Subgraph
 Data Aggregation

Roles: Data Source, Aggregator, Forwarder
 Many variations and combinations of the above
Apr 26th, 2006
Christian Frank <[email protected]>
3
Role Assignment Abstraction
 Programmer defines a list of roles

Functions that a node may perform in the network
 Annotated with conditions for assigning each role,
based on:


Apr 26th, 2006
Local node properties (available sensors, processing
power, battery, position…)
Properties of nodes in network neighborhood
Christian Frank <[email protected]>
4
Example Specification: Coverage
 Network consists of more nodes
on
off
than needed
 Only some nodes need to have
sensors ON
 Others may save power and
sleep with sensors OFF
 Conditions of ON role:

Temperature sensor
 Battery above threshold
 No other ON node in sensing
range
ON :: {
temp-sensor == true &&
battery >= threshold &&
count(2 meters) {
role == ON
} == 0
}
OFF :: else
{ pred }:{ pred } :
 xcount(scope)
== retrieve(scope)
 store
Countsnodes
nodesmatching
matching pred
scope
predwithin
in property
Apr 26th, 2006
Christian Frank <[email protected]>
x
5
Elements of a Role-Assignment System
Role
Assignment
Problem
RA
Algorithm
Role
Specifications
Distributed
Algorithm
Node
Properties
Network
RA Algorithm
Property
Directory
App.
battery = 80%
pos = (12, 3)
role = ON …
Role
Assignment
Apr 26th, 2006
Christian Frank <[email protected]>
6
Distributed Algorithm
on
off
 Distributed algorithm repeats three
basic steps:



Send properties to neighbors
Wait random interval, receive properties
Decide role
 Does solution exist?
 How good is the solution?
 Distributed fixpoint iteration
 Notifies applications on stable role
 Details in “Algorithms for Generic Role
Assignment…” In Proc. of Sensys 2005
Apr 26th, 2006
Christian Frank <[email protected]>
7
Verification through Integer Program
Role
Assignment
Problem
RA
Algorithm
Role
Specifications
Centralized
Algorithm
Network
Node
Properties
IP Converter
Integer
Program
CPLEX Solver
 Detect infeasible
specifications
 Optimize number
of nodes with a
certain role(s)
Role
Assignment
Apr 26th, 2006
Christian Frank <[email protected]>
8
ON :: {
count(scope) {
role == ON
} <= 0 }
OFF :: else
Example Integer Program
 Binary result variables
 For
each node i and role r
x(i, r ) 
 Constraints (for each
1
0
if node i is assigned role r
otherwise
node i ):
 Only
one role should be
assigned to a node i
 Role ON is assigned iff
count operator is true
 “: If role ON, count
 “ 
must be true
 “ similar
 “ 
x(i,ON)  x(i,OFF)  1
x(i,ON)  1





x( j, ON )  0
jscope

x( j, ON )  0  M  (1  x(i, ON ))
jscope
M high number,
annuls constraint
Apr 26th, 2006
Christian Frank <[email protected]>
9
Additional Variables and Constraints
 Variables
 Output
variables indicating
computed role
 Auxiliary variables at each node
- For each atomic predicate
- For each and / or
- For each role condition (opposed
to assignment)
 Constraints formulating
 And
/ or
 Assign first matching role, if
more than one condition
matches
y1
cON
y2
y3
cOFF
ON :: {
temp-sensor == true &&
battery >= threshold &&
count(2 meters) {
role == ON
} == 0
}
OFF :: else
cON 
 y1 y 2  y 3
 3cON  y 1  y 2  y 3
xOFF  cOFF  cON
 Retrieve operators (paper)
Apr 26th, 2006
Christian Frank <[email protected]>
10
Results: Feasibility
 Some specifications are infeasible, toy
example:



Condition for Red: At least 1 Green neighbor
Condition for Green: No Red neighbor
Grey: Else
 Infeasibility is not always apparent in the
specification

Distributed algorithm does not find solution
 IP can be used to detect infeasibility

Apr 26th, 2006
Compute feasible topology
Christian Frank <[email protected]>
11
Results: Optimality
 IP can be used to
compute gap between
“distributed” and
“optimal” configuration
 Generated IPs
computable in
reasonable time for
many nodes
Apr 26th, 2006
Christian Frank <[email protected]>
ON nodes with Coverage Example
Distributed
IP
12
Summary
 IP-based role assignment algorithm


Compute feasibility (or feasible topology)
Optimize number of nodes with a certain role(s)
 Integrated development tool



Apr 26th, 2006
Simulator of distributed algorithms
Integer-program based verifier
Visualization
Christian Frank <[email protected]>
13
Solving Generic Role Assignment Exactly
Christian Frank and Kay Römer
ETH Zurich, Switzerland
Apr 26th, 2006