.

Algorithmic Foundations of Sensor Networks Lecture 3: Data propagation algorithms part III
Sotiris Nikoletseas
Department of Computer Engineering and Informatics University of Patras, Greece

March 8, 2013

1 / 35

A canonical problem: Local Event Detection and . Data Propagation

A single sensor, p, senses a local event E . The general propagation problem is the following: How can sensor p, via cooperation with the rest of the sensors in the network, propagate information about event E to the control center?

2 / 35

. Representative data propagation protocols

Directed Diffusion (DD): a tree-structure protocol (suitable

for low dynamics)

LEACH: clustering (suitable for small area networks) Local Target Protocol (LTP): local optimization (best for

dense networks)
Probabilistic Forwarding Protocol (PFR): redundant

optimized transmissions (good efciency / fault-tolerance trade-offs, best for sparse networks)
Energy Balanced Protocol (EBP): guaranteeing same per

sensor energy (prolong network life-time)

3 / 35

. The Local Target Protocol (LTP) The model (I)

We call network nodes particles. a) Each particle may have two communication modes: a broadcast (radio) beacon mode and a directed to a point transmission mode (laser beam). However, a radio broadcast sufces. b) Each particle may alternate between a sleeping and an awake mode. During sleeping periods particles cease any communication. c) Particles do not move. d) The particles are spread in a two-dimensional area (plane).

4 / 35

. The model (II)

e) A receiving wall W is a line in the plane. The wall represents the control center (multiple/mobile sinks). f) Each particle is aware of the direction toward W . g) No geolocation abilities assumed Denitions: Let d (in numbers of particles /m2 ) be the density of the cloud. Let R be the maximum (beacon/laser) transmission range of each particle.

5 / 35

. The Local Target Protocol (LTP)

Let d (pi , pj ) the (vertical) distance of pi , pj and d (pi , W ) the (vertical) distance of pi from W . Let info(E ) the info to be propagated. Each p receiving info(E ) does the following:
Search Phase: It uses a low energy broadcast of a beacon

(angle above and below the vertical line) to discover a particle closer to W (i.e. a p where d (p , W ) < d (p , W )).
Direct Transmission Phase: If found, p sends info(E ) to p

via a direct line (laser) transmission.

Backtrack Phase: If repetitions of the search phase fail to

discover a particle nearer to W , then p sends info(E ) to the particle it received the information from.

6 / 35

Example of the Search Phase

Example of Data Propagation

p3 p2 p1
a0 a1 a2

p0

p'

beacon circle

7 / 35

. Efciency

Denitions: Let hopt the (optimal) number of hops" (vertical to W transmissions) needed to reach W , if particles always exist in pair-wise distances R towards W . Let h the actual number of hops (transmissions) taken to reach W . The hops efciency of the data propagation protocol is the ratio Ch = where hopt =
d (p, W ) R

h hopt

8 / 35

. Why studying h, Ch ?

When a particle p looks around" for a particle as close to W as possible to pass information, it may not get any particle in the perfect direction (on the line vertical to W passing from p), mainly because: a) There might never have been any particles in that direction. b) Particles of sufcient remaining battery power may not be available anymore. c) Particles available may temporarily sleep" to save energy.

9 / 35

. Simplifying Assumptions for a Rigorous Analysis

The search phase always nds a p in the semicircle of

center p and radius R towards W . This assumption can be relaxed: (a) by repetitions of the search phase (b) we may consider a cyclic sector dened by circles of radii R R, R (c) if a search phase ultimately fails, the protocol backtracks.

The position of p is random uniform in the arc of angle 2a. Each target selection is stochastically independent of the

others.

10 / 35

. Lemma . The expected hops" efciency of LTP in the -uniform case is E . (Ch ) sin , for large hopt . Also, 1 E (Ch ) 2 1.57.
Proof: A sequence of points is generated, p0 = p, p1 , p2 , . . . , ph1 , ph where ph1 is the rst particle found within W s range and ph is beyond W . Let i be the (positive or negative) angle of pi w.r.t. pi 1 s vertical line to W . It is:
h1 i =1 h i =1

d (pi 1 , pi ) d (p, W )

d (pi 1 , pi )

11 / 35

The (vertical) progress toward W is i = d (pi 1 , pi ) = R cos i . We get:

h 1 i =1

cos i hopt

h i =1

cos i

From Walds equation, then E (h 1) E (cos i ) E (hopt ) E (h) E (cos i ) E (h ) 1 = E (Ch ) + sin hopt sin hopt since E (cos i ) =

cos x

1 sin dx = 2
2

Assuming large values for hopt and since for 0 we get the result.

it is 1

sin

12 / 35

. The min-two uniform targets" (M2TP) Protocol

We assume that the search returns two points p , p each uniform in (, ) and that the protocol selects the best. Let i 1 , i 2 {the angles }of the particles found and let i = min |i 1 |, |i 2 | . Then, ( )2 { } I P{i > } = I P |i 1 | > |i 2 | > = Thus, the distribution function of i , is Fi () = I P{i } = and the probability density function is, d 2 fi () = I P{i } = d 2 2 2 ( 1 )

The expected local progress is: 2(1 cos ) E (cos i ) = cos fi () d = 2 0

. . . . . .

13 / 35

. Lemma . The expected hops efciency of the min-two uniform targets protocol in 2 the -uniform case is E (Ch ) 2(1 cos ) , for 0 and for large h . 2 . We remark that
0

lim E (Ch ) = lim

2 =1 2 sin a

and
2

lim E (Ch ) =

(/2)2 2 = 1.24 2(1 0) 8

. Lemma . The expected hops" efciency of the min two uniform targets protocol is 2 1 E (Ch ) 8 1.24 for . large h and for 0 2 .
. . . . . .

14 / 35

. Tight upper bounds to the hops distribution

Consider p at distance x from W . We assume that when p searches in the sector S dened by (, ) and R, a particle p is returned in )d A. the sector with some probability density f (p Denition: (Horizontal progress) Let x be the projection of the line segment (p, p ) on the line from p vertical to W . Assume each search returns such a p , with independent and identical distribution f (). Denition: (Signicant progress) Let m > 0 be the least integer such that I P{x > 0 < p < 1 is a given constant.
R m}

p, where

15 / 35

Denition: Let the stochastic process P where with probability p the horizontal progress is R/m and with probability q = 1 p it is 0. . Lemma: . Let Q the actual process. Then I PP {h h0 } I PQ {h h0 } (stochastic dominance). . Now let t =
x R/m

mx
R

. Consider the integer r.v. H such

that I P{H = i } = q ) for any i 0. Then H is geometrically distributed. Let H1 , . . . , Ht be t random variables, i.i.d. according to H . Clearly then: q i (1 . Lemma . I P{H1 + + Ht = h} .PP {# of hops is h} = I
. . . . . .

16 / 35

. Theorem . ( t ) t (t +h1) t h h I pq h .PP {the number of hops is h} = h p (q ) =

(since h is negative binomial because it is the number of failures until the tth success)

Corollary: For the process P , the mean and variance of the number of hops are: tq tq E (h) = Var (h) = 2 p p The method above nds a distribution that upper bounds the x number of hops. Since for all f () it is h R = hopt we get . Theorem . The process P estimates the expected number of hops with a )(1p) guaranteed ratio (m+1p at most. . Example: When for p = 0.5 we have m = 2 and the efciency ratio is 3, i.e. the overestimate is 3 times the optimal number of hops.
. . . . .

17 / 35

. Summary evaluation of LTP

local, simple, greedy protocol no global structure (set of paths) maintained good for dense networks performance drops in sparse / faulty networks

18 / 35

The Probabilistic Forwarding Protocol (PFR) The . Model

We assume that each particle has the following abilities: i) It can estimate the direction of a received transmission (e.g. via the technology of direction-sensing antennae). ii) It can estimate the distance from a nearby particle that did the transmission (e.g. via estimation of the attenuation of the received signal). iii) It knows the direction towards the sink S. This can be implemented during a set-up phase, where the sink broadcasts information about itself to all particles. iv) All particles have a common co-ordinates system. Note that GPS information is not needed for this protocol. Also, there is no need to know the global structure of the network.
. . . . . .

19 / 35

. Propagation Protocol Properties

Correctness. Protocol must guarantee that data arrives

to the sink S , given that the network is operational.

Robustness. must guarantee that data arrives at

enough points in a small interval around S , in cases when part of the network has become inoperative.
Efciency. should have a small ratio of the number k of

activated particles over the total number N of particles k r=N . Thus r is an energy efciency measure of .

20 / 35

. The basic idea of PFR

PFR probabilistically favors redundant transmissions toward the sink within a thin zone of particles around the line connecting the particle sensing the event E and the sink.

Thin Zone of particles

. . . . . .

21 / 35

. The Forwarding Probability

Data is propagated with a suitably chosen probability p, while it is not propagated with probability 1 p. To favor near-optimal transmissions the following probability is used: Pfwd =
E
p2 p1
1 2

22 / 35

. The two phases of PFR

Phase 1: The Front" Creation Phase. Initially (by using a limited, in terms of rounds, ooding) a sufciently large front" of particles is built, to guarantee the survivability of the data propagation process. Each particle having received the data, deterministically broadcasts it toward the sink. Phase 2: The Probabilistic Forwarding Phase. Each particle p receiving info(), broadcasts it to all its neighbors with probability I Pfwd (or it does not propagate any data with probability 1 I Pfwd ) dened as follows: { 1 if threshold = 134o I Pfwd = otherwise

23 / 35

. The Correctness of PFR

. Lemma . PFR always succeeds in sending the information from E to S when the whole network is operational. .

In the proof, geometry is used (i.e. we cover the network area by unit squares and show that there are always particles close enough to the optimal line, i.e. with > 134o , that deterministically broadcast).

24 / 35

. The Energy Efciency of PFR

We consider particles that are active but as far as possible from ES
n0 E S

The particles inside the LQ Area

We approximate w by the following random walk

y x xo E xo x y
. . . . . .

25 / 35

By using stochastic dominance by a continuous time discouraged arrivals birth-death process, we prove: . Theorem . The energy efciency of the PFR protocol is

(( ) ) 2
n0 n

where

n0 = |ES | and the total number of particles in the network is N = n2 . For n0 = o(n), this is o(1). .

26 / 35

. The Robustness of PFR

Particles very near the ES line are considered. We study the case when some of these particles (at angles > 134o ) are not operating. The probability that none of them transmits is very small. It is shown: . Lemma . PFR manages to propagate the crucial data across lines parallel to ES , and of constant distance, with xed nonzero probability. .

27 / 35

. Experimental Comparison of LTP and PFR

The simulation environment:
C++ 2D geometry data types of LEDA a variety of sensor elds in a 100m100m square area: we drop randomly n [100, 3000] particles (i.e. 0.01 d 0.3) xed radio range R = 5m search angle = 90 we repeated each experiment more than 5000 times to get

good average results

28 / 35

. LTP The impact of angle

Ideal Hops Efciency for angles [5, 90]

0 Ch 1

1.8

1.4

Ch initially decreases

1.2

very fast, while having a limiting behavior for 40

0.8

0.6 100 90 80 70 60 50 40 30 20 10 0

Maximum Angle Local Target Min-Two Targets

29 / 35

Hops Efficiency

(assuming particles always exist)

1.6

. LTP The impact of sampling several targets

Ideal Hops Efciency for different number of targets

1.8

1.6

Hops Efficiency

# targets Ch 1 4 targets already very

1.4

1.2

close to optimal

0.8

0.6 0 1 2 3 4 5 6 7 8 9 10 11

Min-# Targets

30 / 35

. LTP Failure rate

Failure rate for density d [0.01, 0.5] and = 90

100%

for d 0.1 both

Failure Rate

90% 80% 70% 60% 50% 40% 30% 20% 10% 0% 0 0.1 0.2 0.3 0.4 0.5 0.6

protocols almost always backtrack

for d 0.2 the failure

rate drops very fast to 0.

Particle Density
Local Target Min-Two Target

31 / 35

. Ratio of activated particles over density

1 0.9

Ratio of Active Particles over Total Particles (r)

0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0.01

0.03

0.05

0.07

0.09

0.11

0.13

0.15

0.17

0.19

0.21

0.23

0.25

0.27

0.29

Particle Density (d)

PFR LTPe LTPa LTPr

PFR behaves very well (r 0.3) for low densities

(d 0.07)

PFRs energy dissipation increases with density LTP performs best in dense networks
. . . . . .

32 / 35

. Number of Backtracks
60

50

Number of Backtracks

40

30

20

10

0 0.01

0.03

0.05

0.07

0.09

0.11

0.13

0.15

0.17

0.19

0.21

0.23

0.25

0.27

0.29

Particle Density (d)

LTPe LTPa LTPr

For very low densities (i.e. d 0.12), LTP backtracks a lot. As density increases, the number of backtracks of LTP

reduces fast and almost reaches zero.

33 / 35

. Average number of hops to the sink

160 140

Number of Hops to reach Sink

120

100

80

60

40

20

0 0.01

0.03

0.05

0.07

0.09

0.11

0.13

0.15

0.17

0.19

0.21

0.23

0.25

0.27

0.29

Particle Density (d)

PFR

LTPe

LTPa

LTPr

all protocols are near optimal (40 hops) even for low

densities ( 0.17). PFR achieves this even for very low densities ( 0.07). LTP shows a pathological behavior for low densities ( 0.12) due to many backtracks.
. . . .

34 / 35

. Relevant References
- I. Chatzigiannakis, P. Spirakis and S. Nikoletseas, Efcient and Robust Protocols for Local Detection and Propagation in Smart Dust Networks, in the Journal of Mobile Networks (MONET), 2005. Also, in the ACM Principles of Mobile Computing (POMC) 2002. - I. Chatzigiannakis, T. Dimitriou, S. Nikoletseas, and P. Spirakis, A Probabilistic Algorithm for Efcient and Robust Data Propagation in Smart Dust Networks, in the Proceedings of the 5th European Wireless Conference on Mobile and Wireless Systems beyond 3G (EW 2004), pp. 344-350, 2004. Also, in the Ad-Hoc Networks Journal, Elsevier, 4 (5): 621-635 (2006). - I. Chatzigiannakis, T. Dimitriou, M. Mavronicolas, S. Nikoletseas and P. Spirakis, A Comparative Study of Protocols for Efcient Data Propagation in Smart Dust Networks, in the Parallel Processing Letters (PPL) Journal, Volume 13, Number 4, pp. 615-627, 2003. Also, Distinguished Paper (4th out of 338 papers) in the European Symposium on Parallel Processing (EuroPar), 2003.

35 / 35