lecture localization-goldenberg-defense.ppt

lecture note

1. Fine-Grained Localization in
Sensor and Ad-Hoc Networks
David Goldenberg
Dissertation Advisor: Y. Richard Yang
Committee Members: Jim Aspnes, A. Stephen Morse,
Avi Silberschatz, Nitin Vaidya (UIUC)
Ph.D. Dissertation Defense

2. 2
Overview
This dissertation provides a theoretical basis for
the localization problem, demonstrating
conditions for its solvabilityand defining its
computational complexity.
We apply our fundamental results on localization
to identify conditions under which the problem is
efficiently solvableand to develop localization
algorithmsfor a broader class of networks than
previous approaches could localize.

3. 3
Collaborators (2003-2006)
Brian D.O. Anderson (Australia National University and NICTA)
James Aspnes
P.N. Belhumeur (Columbia University)
Pascal Bihler
Ming Cao
Tolga Eren
Jia Fang
Arvind Krishnamurthy
Jie (Archer) Lin
Wesley Maness
A. Stephen Morse
Brad Rosen
Andreas Savvides
Walter Whiteley (York University)
Y. Richard Yang
Anthony Young

4. 4
Outline
Introduction to Localization
Conditions for Unique Localization
Computational Complexity of Localization
Localization in Sparse Networks

5. 5
Why are Locations Important?
Wireless ad-hoc networks are an important emerging technology
Small, low-cost, low-power, multi-functional sensors will soon be a reality.
Accurate locations of individual sensors are useful for many applications
“Sensing data without knowing the sensor location is meaningless.”[IEEE
Computer, Vol. 33, 2000]
New applications enabled by availability of sensor locations.
Location-aware computing
Resource selection (server, printer, etc.).
Location aware information services (web-search, advertisement, etc.).
Sensor network applications
Inventory management, intruder detection, traffic monitoring,
emergency crew coordination, air/water quality monitoring,
military/intelligence apps.

6. 6
Example: Great Duck Island Sensor Network
Monitoring breeding of Leach’s
Storm Petrels without human
presence.
15 minute human visit leads to 20%
offspring mortality.
Sensors need to be small to avoid
disrupting bird behavior.

7. 7
Great Duck Island Deployment Goals
Occupancy pattern of nests?
Environmental changes around the
nests over time?
Environmental variation across nests?
Correlation with breeding success?
Light, temperature, infrared, and
humidity sensors installed.
Infrared sensors detect presence of
birds in nests.
10m
Single hop weather
Single hop burrow
Multi hop weather
Multi hop burrow
Sensor locations critical to interpreting data.
Locations determined by manual
configuration, but this will not be possible in
the general case.

8. 8
Example: ZebraNet Sensor Network
Biologists want to track animals to study:
Interactions between individuals.
Interactions between species.
Impact of human development.
Current tracking technology: VHF collar transmitters
Wishlist:
24/7 position, data, and interaction logs.
Wireless connectivity for mobility.
Data storage to tolerate an intermittent base station.
ZebraNet:
Mobile sensor net with intermittent base station.
Records position using GPS every 3 minutes.
Records Sun/shade info.
Detailed movement information (speed, movement signature)
3minutes each hour.
Future: head up/head down, body temperature, heart rate,
camera.
Goal, full ecosystem monitoring (zebras, hyenas, lions…).

9. 9
Military Applications
Intelligence gathering (troop movements, events of interest).
Detection and localization of chemical, biological, radiological,
nuclear, and explosive materials.
Sniper localization.
Signal jamming over a specific area.
Visions for sensor network deployment:
Dropped in large numbers from UAV.
Mortar-Launched.
!

10. 10
Why is Localization a Non-Trivial Problem?
Manual configuration
Unscalable and sometimes impossible.
Why not use GPS to localize?
Hardware requirements vs. small sensors.
Obstructions to GPS satellites common.
GPS satellites not necessarily overhead.
Doesn’t work indoors or underground.
GPS jammed by sophisticated adversaries.
GPS accuracy (10-20 feet) poor for short
range sensors.

11. 11
Fine-Grained Localization (Savvides, 2001)
Physically:
Network of nnodes, mof which have known location, existing in space at
locations: {x
1…x
m,x
m+1,…,x
n}.
Set of somepair-wise inter-node distance measurements.
Usually between proximal nodes (iff d < r in unit disk networks).
Abstraction
Given: Graph G
N, {x
1,...,x
m}, and δ, the edge weight function.
Find: Realizationof the graph.
5
4
1
2
3 1
2
3
4
5
{x
1,x
2,x
3}
{x
4, x
5}
Beacons: nodes with known position
Regular nodes: nodes with unknown position
{d
14, d
24, d
25, d
35, d
45}

12. 12
Ranging Systems
TDoA –Time Difference of Arrival
Uses ultrasound and radio signals
to determine distance.
Range of meters, cmaccuracy.
Possible to increase sensing range
by increasing transmission power.
MIT cricket mote
UCLA medusa mote (2001)
UCLA medusa mote 2 (2002)
Yale ENALAB XYZ Motes

13. 13
Our Contributions
Graph-theoretic conditions for the unique solvability of the localization
problem in the plane.
Proof that the problem is NP-complete even for the idealized case of
unit-disk networks.
Constructive characterizationof classes of uniquely localizable and
easily localizable networks for the plane and 3D.
A localization algorithm that localizes a wider class of networks than
was possible with existing approaches.
In-depth study of the localizability properties of random networks:
New adaptive localizability-optimizing deployment strategies.
Impact of non-uniquely localizable nodes on network performance.

14. 14
Outline
Introduction to Localization
Conditions for Unique Localization
Computational Complexity of Localization
Localization in Sparse Networks

15. 15
Unique Localizability
Network is uniquely localizableif there is exactly one set
of points {x
m+1,…,x
n} consistent with G
N, {x
1,…,x
m} and
δ:E to R.
Can we determine localizability by graph properties alone?
(as opposed to the properties of δ).
In the plane, yes (more or less). Properties of the graph
determine solvability in the generic case.
Probability 1 for randomly generated node locations.

16. 16
Degenerate Cases Fool Abstraction
2
1
3
4
2
1
3
4
{x
1, x
2, x
3}
{d
14, d
24, d
34}
probability 1 case:
probability 0 case:
first case: {x
4}
second case: ???
2
1
3
?
?
In general, this network is
uniquely localizable.
In degenerate case, it is not:
The constraints are redundant.
4
2
1
3

17. 17
Continuous Non-Uniqueness
Continuous non-uniqueness:
Can move points from one configuration to another while
respecting constraints.
Excess degrees of freedom present in configuration.
A formation is RIGIDif it cannot be continuously deformed.

18. 18
Condition for Rigidity
Purely combinatorial characterization of
generic rigidity in the plane.
2n-3 edges necessary for rigidity, and:
Laman’s condition:
A graph G with 2n-3 edges is rigid in two dimensions
if and only if no subgraph G’ has more than 2n’-3 edges*.
* where n’ is the number of vertices in G’
Laman’s condition is a statement that any rigid graph with n vertices must have a set
of 2n-3 well-distributededges.
Not enough edges Enough edges but not well distributed Just right

19. 19
1 config2
4
configs
1
4
2
3
5
1
4
2
3
5
1
4
2
3
5
1
4
2
3
5
Discontinuous Non-Uniqueness in Rigid Graphs
2
3
0 4
1
56
2
3
0 4
1
56
2
3
0 4
1
56
1
4
…
2
3
5
1
4
2
3
5
1
4
2
3
5
Flip Ambiguities:
Discontinuous Flex
Ambiguities:

20. 20
Unique Graph Realization
a
e
b
f
c
d
a
c
b
e
d
f
Solution:
G must be 3-connected.
G must be redundantly rigid:
It must remain rigid upon
removal of any single edge.
G must be rigid.
A graph has a unique realization in the plane iff it is redundantly
rigid and 3-connected (globally rigid). Hendrickson, ‘94

21. 21
Is The Network Uniquely Localizable?
Problem: By looking only at the physical connectivitystructure, we would neglect
our a prioriknowledge of beacon positions.
Solution: The distances between beacons are implicitly known!
By adding all edges between beacons to G
N, we get the Grounded
Graphof the network, whose properties determine network
localizability.
Theorem: A network is generically uniquely localizableiff its grounded
graph is globally rigid and it contains at least three beacons.
By augmenting graph structure in this way, we fully express all available
constraint information in a graph.
5
4
1
2
3
Is this localizable?
1
2
3
4
5

22. 22
Examples of GR graphs -Constructions
Every globally rigid graph has a spanning subgraph that is minimally globally rigid.
Every minimally globally rigid graph can be constructed inductively starting from K
4by a
series of extensions(Berg-Jordan ‘01):
New node wand edges uwand vwreplace edgeuv.
Edge wxadded for some node xdistinct from u, v.
Minimal globally rigid graphs have 2n-2edges.
1
3 4
2
1
3 4
2
5
1
3 4
2
5
6
1
3 4
2
5
6
7
1
3 4
2
5
6
7
8
…
Light edges are those subdivided by the extension operation.

23. 23
Examples of Global Rigidity
Random network –avg node degree 6. Regularized random network –avg node degree 4.5.
Globally rigid components in green.

24. 24
Construction Using Trilateration
A position is uniquely determined by three distances to three non-collinear references.
Minimal trilateration graphs formed by trilateration extension:
New node wand edges uw, vw, xwadded, for u, v, x distinct.
Minimal trilateration graphs are globally rigid.
Minimal trilateration graphs have 3n-6edges.
1
3 4
2
1
3 4
2
5
1
3 4
2
5
6
1
3 4
2
5
6
7
1
3 4
2
5
6
7
8 …
Light edges are those removed in extension for minimally GR graph but not in trilateration.

25. 25
Trilateration Graphs
A trilateration graph G is one with an trilaterative ordering: an ordering
of the vertices 1,...,n such that the complete graph on the initial 3 vertices
is inGand from every vertex j > 3, there are at least 3edges to vertices
earlier in the sequence.
Trilateration graphs are globally rigid.
Hand-made trilateration –avg degree 6. Trilateration graph from mobile network –avg degree 9.

26. 26
“Tripled” Connected Graphs are
Trilateration Graphs
Theorem:
Let G = (V,E) be a connected graph.
Let G
3
= (V,EE
2
E
3
) be the graph formed from G by
adding an edge between any two vertices connected by
paths of 2 or 3 edges in E.
Then G
3
is a trilateration graph.
Example where
G is a path.

27. 27
“Doubled” 2-connected Graphs are
Globally Rigid in 2D
Theorem:
Let G be a 2-connected graph.
Then G
2
is globally rigid.
Example where
G is a cycle.
Minimally GR graph
by extension:
Doubled cycle:
Doubled cycles always
have two edges more than
a minimally GR graph, so
they are globally rigid.
One gets G
2
by doubling sensing radius or
measuring angles between adjacent edges.

28. 28
“Tripled” Biconnected Graphs are
Globally Rigid in 3D
There is no known generic characterization
of global rigidity in 3D, but our result on
doubled graphs extends to 3D.
Theorem:
Let G be a 2-connected graph.
Then G
3
is globally rigid in 3D.

29. 29
Summary of Constructive Characterization
of Globally Rigid Graphs
2D
3-connectivity necessary for GR.
G
2
GR if G 2-connected.
G
3
GR if G connected.
3D
G
3
GR in 3D if G 2-connected.
G
4
GR in 3D if G connected.
Unique localizability by increasing sensing range, given
initial connectivity.
Conditions under which additional information can help.

30. 30
Outline
Introduction to Localization
Conditions for Unique Localization
Computational Complexity of Localization
Localization in Sparse Networks

31. 31
Localization
5
4
1
2
3
1
2
3
4
5
Decision problem
Search problem
Rigidity
theory
Does this have a
unique realization?
Yes/No
1
2
3
4
5
{x
1,x
2,x
3}
{d
14, d
24, d
25, d
35, d
45}
This graph has a
unique realization.
What is it?
???
{x
4,x
5}
This problem is in
general NP-hard.

32. 32
Computational Complexity
Suppose all edge
distances known
for small triangles.
Localization goes
working out from
any beacon.
Triangle reflection
possibilities grow
exponentially….
…and reflection
possibilities are only
sorted out when one
gets to another beacon.
Intuitively, reflection possibilities are linked with
computational complexity

33. 33
Complexity of GR Graph Realization
If a network is localizable, how does one go about localizing it?
It is NP-hard to localize a network in R
2
even when it is known to
be uniquely localizable.
We will use two tools in our argument:
The NP-hard set-partition problem.
The globally rigid wheel graph W
n.
W
6
The set partition problem:
Input: A set of numbers S.
Output: Can Sbe partitioned into two subsets A
and S-Asuch that the sum of numbers
in each subset is equal?

34. 34
NP-hardness of Realization
Theorem:
Realization of globally rigid weighted graphs that are realizable is NP-hard
Proof sketch:
Assume we have algorithm Xthat takes as input a realizable globally rigid
weighted graph and outputs its unique realization.
We will find the set-partition of the partitionable set Sscaled w.l.o.g so that the
sum of elements in Sis less than π/2 by using calls to X.
Suppose we have S={s
1,s
2,s
3,s
4} with a set-partition. Construct a graph G along
with its edge weights for X:
0
1
23
4 s
1
s
3
s
4
s
2
s
1+s
4=s
2+s
3
rights= lefts
This is a realization of W
5!
Even without Set Partition,
we have the edge weights of G:
d
i,i+1=2sin(s
i/2)
that uniquely determine the
realization .
When G is realized, we obtain
the picture on the left, from
which we obtain set partition!

35. 35
Localization Complexity for Sparse Networks
Problem with previous result is that edges exist arbitrarily.
Graphs used in previous proof unlikely to arise in practice.
In realistic networks, edges are more likely to exist between close
nodes, and do not exist between distant nodes.
Unit Disk Graphs: edge present if distance between nodes less than
parameter r.
Therefore: if edge absent, distance between nodes is greater than r.
Does this information help us solve the localization problem?
0
1
23
4
Rededge would exist in unit disk graph, so unit disk
graph localization would not solve Set Partition.

36. 36
Complexity of Localizing Unit Disk Graphs
Theorem: Localization for sparse sensor networks is NP-hard.
Method:
Reduction from Circuit Satisfiabilityto Unit Disk Graph Reconstruction.
Reduction is by construction of a family of graphs that represent Boolean circuits.
Rigid bodies in the graph represent wires.
Relative position of rigid bodies in the graph represent signals on wires.
NOT and AND gates built out of constraints between these bodies expressed in the
graph structure.
There is a polynomial-time reduction from Circuit Satisfiabilityto Unit Disk Graph
Reconstruction, in which there is a one-to-one correspondence between satisfying
assignments to the circuit and solutions to the resulting localization problem.
Unit Disk Graph Reconstruction (decision problem)
Input: Graph G along with a parameter r, and the square of
each edge length (l
uv)
2
(to avoid irrational edge lengths).
Output: YES iff there exists a set of points in R
2
such that
distance from uto vis l
uvif uvis an edge in Gand greater
than rotherwise.
Circuit Satisfiability (NP-hard):
Input: A boolean combinatorial circuit.
Composed of AND, OR, and NOT gates
Output: YES iff the circuit is satisfiable.

37. 37
Localization in Trilateration Graphs
As one adds more edges, localization becomes easier: There are classes of
globally rigid graph which are easy to localize.
Trilateration graphs are localizable in polynomial time.
Remember: One gets a trilateration graph from a connected network by tripling
the sensing radius.
Algorithm:
If initial 3 vertices known, localize
vertices one at a time until all vertices
localized.
Else starting with each triangle in the
graph, proceed as above until all
localized.
O(|V|
2
) or O(|V|
5
).

38. 38
The following guarantees G
n(r) is k-
connected with high probability for
some constant clarge enough and
constant k:
Penrose, ‘99
r
Connectivity in Random Networks
The random geometric graph G
n(r) is the random
graph associated with formations withn vertices
with all links of length less thanr, where the
vertices are points in [0,1]
2
generated by a two
dimensional Poisson point process of intensity n.c
n
nr
n

log
lim
2
Note: Need nr
2
/(log n) > c, for some c, to
guarantee even connectivity.
Theorem: If nr
2
/(log n) > 8, with high
probability, G
n(r) is a trilateration graph.
This identifies conditions under which a
simple iterated trilateration algorithm will
succeed in localization.

39. 39
Trilateration in Random Networks
Localized mode:
Broadcast position.
Unlocalized mode:
Listen for broadcast.
ifbroadcast from (x,y) heard,
Determine distance to (x,y).
ifthree broadcasts heard
Determine position
Switch to localized mode
Iterative Trilateration
But how
fast?
Sensors have 2 modes.
Sensors determine distance from heard transmitter.
All sensors are pre-placed and plugged in

40. 40
Asymptotics of Trilateration in Random Networks
Beacons Sensing radius E[t
loc])
log
(
n
n
O )log(nO )
log
(
n
n
O )
log
(
n
n
O )
log
(
n
n
O )
log
(
n
n
O )(nO )1(O )1(O
Running times to complete localization using trilateration for different beacon densities.

41. 41
NP-hardness of Localization
Fine-grained localization is NP-harddue to NP-hardness
of realizing globally rigid graphs.
This means that localization of networks in complete
generality is unlikely to be efficiently solvable.
Motivates search for reasonable special cases and
heuristics. Explains hit-or-miss character of previous
approaches.
Changing sensing radius can predictably convert connectedness
to global rigidity and trilateration.

42. 42
Outline
Introduction to Localization
Conditions for Unique Localization
Computational Complexity of Localization
Localization in Sparse Networks

43. 43
Motivation
Being able to precisely localize only trilateration
networks is unsatisfying.
Trilateration networks contain significantly more
constraints than necessary for unique localizability.
Can we localize networks with closer to the minimal
number of constraints?
1
3 4
2
5
6
7
8
1
3 4
2
5
6
7
8
Trilateration graphGlobally rigid subgraph
Rededges unnecessary
for unique localizability.

44. 44
Bilateration Graphs
A bilateration graph G is one with a bilateration ordering:
an ordering of the vertices 1,...,n such that the complete
graph on the initial 3 vertices is inGand from every vertex j
> 3, there are at least 2edges to vertices earlier in the
sequence.
Theorem: Bilateration graphs are rigid (but not globally rigid).
Theorem: Let G = (V,E) be a connected graph.
Then G
2
is a bilateration graph.
Bilateration graphs are finitely localizablein O(2
|V|
) time.
Algorithm:
If initial 3 vertices known, finitely localize
vertices one at a time by computing all
possible positions consistent with neighbor
positions until all vertices finitely localized.
Else starting with each triangle in the graph,
proceed as above until all finitely localized.
0
1
2
3
3’
4
4’4’’
4’’’
55’
6
6’
6’
6’

45. 45
Localization in Doubled Cycles
Based on finite localization of bilateration graphs,
localization is uniquely computable for globally
rigid doubled cycles.
Completes in O(2
|V|
) time.
Assumes nodes in general position.
0
1
2
3
3’
4
4’4’’
4’’’
55’
6
6’
6’
6’
“Sweep”Algorithm:
Fix the position of three vertices.
Until no progress made:
Finitely localize each vertex connected
to two finitely localized vertices.
Remove possibilities with no consistent
descendants.

46. 46
Localization in Doubled 2-connected Graphs
2-connected graphs are a union of cycles (they have an Ear Decomposition).
The ear decomposition gives a ordering in which cycles may be localized
using previous algorithm.
Note: This means if we have angles, we can localize 2-connected networks.
Biconnected network with its ear decomposition. Doubled biconnected network.

47. 47
Localization on General Sparse Networks
Worst-case exponential time algorithm for localization
in sparse networks:
For which types of network does sweep localization work?
Theorem: Shell sweep finitely localizes bilateration networks.
Theorem: Shell sweep uniquely localizes globally rigid bilateration
networks.
If G is connected, when run on G
2
, shell sweep produces all possible
positions for each node. If G
2
globally rigid, gives the unique positions.
Question: How many globally rigid networks are also bilaterations?
3
1
2
7
4
6
5
0
4’
5’
3
1
2
7
4
6
5
0
3’
6’

48. 48
Typical random graph.
Starting nodes randomly
chosen.
Shell sweep uniquely
localizes localizable
portion.
Also non-uniquely
localizes nodes rigidly
connected to localized
region.
Shell Sweep on
Random Network

49. 49
500 node graph with
considerable anisotropy
and 4.5 average degree.
Shell sweep computes
in <5 seconds* with no
intermediate position set
exceeding 128.
Performance
on Large
Network
* As a JAVA applet on a zoo
node with a dual 2.8GHz CPU
and 2GB RAM

50. 50
Failing Case
Globally rigid network.
Connection between
clusters unbridgeable
by bilateration.

51. 51
Extent of Sweep Localization
Sweeps localizes more nodes than
trilateration, and almost all localizable nodes!
In regular networks, sweeps localizes
significantly more nodes than trilateration.
Most incremental localization algorithms are
trilateration based.
Key point:Many globally rigid random
geometric graphs are bilateration graphs.
Sweeps in Random Network Sweeps in Regular Network

52. 52
Summary of Localization Density
Spectrum
Localization is NP-hard in general, but there are classes of graphs that
are easy to localize.
Complete graphs.
Trilateration graphs.
Graphs that we know how to localize in worst-case exponential time:
Doubled biconnected graphs.
Basic idea: more edges make localization easier.
Goal: to understand which networks can be localized and which are
problematic.
Consider all possible networks on nsensors
Some networks can be
localized in O(|V|
5
):
Trilateration graphs with unknown
ordering
UnlocalizableSome networks can be
localized in exponential
time:
Doubled biconnected graphs
Globally rigid bilateration graphs
Some networks can be
localized in O(|V|
2
) time:
Trilateration graphs with known
ordering

53. 53
When Does Localization Become Easy?
Sparse
Dense
Unsolvable
Easy
Globally Rigid NP-hard
Trilateration Graph Polynomial time
Number of edges
Complexity of
realization
Complete Graph
3-connected r
3
3r
1
2r
2
Sensing radius in G
n(r)
0
1
ExponentialBilateration Graph

54. 54
Conclusion and Future Work
Formalized the localization problem and its solvability.
Showed that the problem is fundamentally
computationally hard.
Constructively characterized easily localizable
networks.
Provided algorithm that localizes more nodes than
previous incremental algorithms.
Next:
Localization using maps.
Localization using angular order information.
Localization in networks of mobile nodes.
Localization in 3D or on 3D surfaces.
Full system from deployment to localization.

55. 55
Our Work in the Field
“Rigidity, Computation, and Randomization in Network Localization”-[Infocom 2004]
Conditions for unique fine-grained localization.
Initial computational complexity results.
“On the Computational Complexity of Sensor Network Localization”-[Algosensors 2004]
Computational complexity results.
“A Theory of Network Localization”-[Transactions on Mobile Computing 2006]
“Graphical Properties of Easily Localizable Sensor Networks”-[under review]
Characterizing easily localizable ad-hoc networks.
“Precise Localization in Sparse Sensor Networks”-[Accepted to Mobicom 2006]
Algorithm for localization in sparse ad-hoc networks.
“Localization in Partially Localizable Networks”-[Infocom 2005]
Investigation of partially localizable networks.
Localizability-aware network deployment.
“Towards Mobility as a Network Control Primitive” -[Mobihoc 2004]
Location-aware controlled node-mobility algorithm for sensor network optimization.

56. 56
Acknowledgements
I would like to thank all my collaborators, without whom this work would not have
been possible.
Brian D.O. Anderson (Australia National University and NICTA)
James Aspnes
P.N. Belhumeur (Columbia University)
Pascal Bihler
Ming Cao
Tolga Eren
Jia Fang
Arvind Krishnamurthy
Jie (Archer) Lin
Wesley Maness
A. Stephen Morse
Brad Rosen
Andreas Savvides
Walter Whiteley (York University)
Y. Richard Yang
Anthony Young
THANK YOU FOR LISTENING
ANY QUESTIONS?