Transcript SMART A Scan-based Movement-Assisted Sensor Deployment

SMART: A Scan-based MovementAssisted Sensor Deployment Method in
Wireless Sensor Networks
Jie Wu and Shuhui Yang
Department of Computer Science and Engineering
Florida Atlantic University
INFOCOM 2005
Outline






Introduction
Related Works
Scan-based Movement-assisted Sensor
Deployment Method (SMART)
Extended SMART
Simulation
Conclusion
Introduction

The efficiency of a sensor network depends on the
deployment and coverage of the monitoring area.

A good sensor deployment is still necessary to
balance the workload of sensors.

Two methods used to enhance the coverage after
an initial random deployment

Incremental sensor deployment
 Deploys additional sensors

Movement-assisted sensor deployment
 Moves the existing sensors
Introduction

The sensor deployment problem can be
viewed as load balance problem



Partitioned small region  processor
Number of sensors in a region  load
Two differences between deployment and
load balance


Different objectives: number of moves
Different technical issues: communication hole
Introduction – Basic Idea

2D scan-based movement-assisted deployment







The sensor network is partitioned into a n n 2-D mesh of
clusters
Each cluster covers a small square area.
The cluster is controlled by a clusterhead
The clusterhead knows the cluster’s position i and the number of
sensors wi in the cluster
Each clusterhead is in charge communication and bookkeeping
Two scans ,once for rows and once for columns, are used to
calculate the average load and determine the overloaded and
underloaded clusters.
Load is shifted from overloaded clusters to underloaded ones.
Introduction – Ideal Case Example
Unbalanced State
Scan in rows
Balanced State
Scan in columns
Introduction

Communication hole problem: the clusters with empty
size can not communication with other clusters, so the
scan approach can not be used.
Related Works (1)

Load balance in multiprocessor systems [13] [14]

Diffusion: each node exchange load with all neighbors
wi  wi 


wi , w j : load in node i, j

adj (i ) : adjacent node to i

ai , j
a
jadj ( i )
i, j
( w j  wi )
: diffusion parameter  ¼ for fastest convergence [17] in 2-D mesh
Dimension Exchange: group adjacent edges to different four
dimensions, two adjacent node by the edge exchange load.
wi  (1   ) wi  w j


: exchange rate
Related Works (2)

Movement-assisted sensor deployment

Virtual force based mobile sensor deployment algorithm
(VFA) [6]
 Using the potential field to calculate virtual force

Voronoi diagram based sensor deployment algorithm [5]



VEC: sensors calculate the virtual force form its Voronoi
neighbor
VOR: sensors detect the coverage holes and move to its
farthest Voronoi vertex
Minimax: sensors move to target position such that whose
distance to the farthest vertex is minimized
SMART - Clustering

Clustering

n n cluster

Each cluster covers x x square
Sensing range: 2 x
Intra-transmission range: 2 x
Inter-transmission range: 5 x
Each sensor knows its cluster id i
Each clusterhead knows its load





n
x
x
Load (number of sensors) of a cluster
SMART – Scan (1)

Scan for 1-D array of clusters to calculate the load in the
balance state






wi : number of sensors in cluster i
vi : prefix sum of the first i clusters
vn : total sum
w : the average load (number of sensors) in a balanced state
vi : prefix sum of the first i clusters in balanced state
First scan calculates w , second scan sends w back and calculate vi
vn  54
first
Determine state
of each cluster
second
w  54 / 6  9
Send w back
SMART – Scan (2)

Determine the “give/take” state of each cluster
 wi  w  0  neutral state
 wi  w  0  overloaded  give state
 w  w  0  underloaded  take state
i

Determine the shifted number of sensors

Overloaded clusters




Give right: wi  min{ wi  w, max{ vi  vi ,0}}

Give left:  wi  (wi  wi )  wi
Underloaded clusters



wi  min{ w  wi , max{ vi 1  vi 1 ,0}}
Take left:


Take right: wi  (wi  wi ) wi
SMART – Properties (1)

Theorem 1: Any violation of the four conditions on give and
take state of each cluster will increase of overall moving
distance and/or total number of moves to reach a load
balanced state.

Proof:

Condition 1: change a cluster i from take to give, the i gives unit to j, i still
have to get a compensate from k, it will increase the moving distance.
Condition 2: change a cluster i form give to take, same as condition 1.
Condition 3: cluster i mixes take-left with take-right

Condition 4: cluster i mixes give-right with give-left, similar to condition 3.


SMART – Properties (2)

Theorem 2: When take-right (take-left) states get load from
give-left (give-right) states, the overall moving distance is
independent of the actual schedule.

Proof: consider from give-left states. Cluster i is in take-right
state and the closest give-left cluster is i’. But now the unit to i
comes from not-closest cluster j’, and unit from i’ goes to j.
The following figure shows the moving distance is the same.
Di ' i  Dj ' j  Dj ' i  Di ' j
SMART – 1D Load Balance algorithm

Sender-Initiated Optimal Load Balance in 1-D Arrays


For each cluster i in give state, the clusterhead sends wi

units to its right neighbor , and sends wi units to its left
neightbor.

For each cluster j in take state, when the cluster head
senses several bypassing units, it intersects as many units
as possible to fill in its “holes”, Unintersected units move
along the same direction.
SMART – Properties(3)

Theorem 3: The proposed greedy schedule ensures an
optimal schedule in 1-D Arrays

Proof: when a unit is passed to i from right to left, it implies
that subarray [i…n] is in overloaded state; similarly, when a
unit is passed to j’ from left to right, the subarray [1…j’] is
overloaded. Since i < j’, the array [1…n] as a whole is
overloaded, which corresponds to a contradiction.
SMART – Extend 1D to 2D

Extend 1-D scan to 2-D

Scan procedure is applied twice: rows and column

No longer optimal

3
1
3
5
Scan in Rows
Moves +2
2
2
4
4
Scan in Columns
Moves +2
3
3
3
3
Total Moves: 4
Optimal Moves: 2
Solution: the actual movement of sensors occurs after
the columns scan. Only clusters in the overloaded
state with respect to the global average send load.
Extended SMART – Filling Holes

Expansion for filling holes in 1-D arrays

Notations






Segment Si : sequence of non-empty clusters
Wi : summation load of Si
Ci : length of Si
Li : expansion level of Si, 2Li < Ci < 2Li+1
Ei : energy level of Si, Ei = Wi - Ci
Doubling expansion for S



Expansion sequence: 2Li, 2Li+1, 2Li+2,…..
Expansion condition: Ei > 2Li+k
Example: Ci of Si is 13 , 23(8) < 13(Ci) < 23+1(16), Li = 3,
expansion of the segment will be 8, 16, 32,…..
Extended SMART – Holes Solution

Steps of communication holes solution
1. Following the positive direction, each segment
performs expansion through recursive doubling
until it either reaches (covers) the last cluster of
the 1-D array or fails the expansion.
2. Repeat step 1. for the negative direction.
Extended SMART – Properties

Theorem 4: in each segment S in a pre-processing scan,
the total moving distance in constructing S is bounded
by C2 and the communication latency is bounded by 5C.

Theorem 5: assume the average load is at least 2 for
each cluster. After the first pre-processing scan, at least
one postfix of the 1-D array is a segment an all holes will
be filled.

Theorem 6: suppose the average number of sensors in a
cluster is at least 4. after column-wise smoothing, each
row will have at least 2n sensors.
Extended SMART – Overall SMART

Revised SMART

Step 1 (column-wise smoothing): Pre-processing (fill the
communication holes) on column (positive direction). Then
simultaneous pre-processing and scan (load balance) on
column (negative direction). Then scan on column
(positive).

Step 2 (row-wise pre-processing and scan): Pre-processing
on row (positive). Then simultaneous pre-processing and
scan on row (negative), finally scan on row (positive).

Step 3 (column-wise scan): Scan on column (negative
followed by positive).
Simulation(1)

Environment





Simulation area: 500 x 500
Cluster numbers: n x n, n = 4, 10
Sensor numbers: N = 400 ~ 1000
Initial deployment: random and normal distribution
Normal distribution parameter o: o = 1 ~ 5
Simulation(2)

Rounds comparison of DIFF, EXCH, and SMART
Simulation(3)

Distance comparison of DIFF, EXCH, and SMART
Simulation(4)

Balance degree comparison of DIFF, EXCH, and SMART
Simulation(5)

Balance degree comparison of DIFF, EXCH, and SMART by
Grads
Simulation(6)

Comparison of VOR and SMART using different o
Conclusion

The paper have proposed a scan-based movementassisted sensor deployment algorithm.

The algorithm also considered the communication
hole problem.

The algorithm achieve even deployment with
modest costs.

Future work contains intra-cluster balancing and
depth simulation on energy consumption.