### Skapa referens, olika format (klipp och klistra)

**Harvard**

Kranakis, E., Kriz̧anc, D., Morales-Ponce, O., Narayanan, L., Opatrný, J. och Shende, S. (2013) *Expected sum and maximum of displacement of random sensors for coverage of a domain*.

** BibTeX **

@conference{

Kranakis2013,

author={Kranakis, Evangelos and Kriz̧anc, Danny and Morales-Ponce, Oscar and Narayanan, Lata and Opatrný, Jaroslav and Shende, Sunil M.},

title={Expected sum and maximum of displacement of random sensors for coverage of a domain},

booktitle={Annual ACM Symposium on Parallelism in Algorithms and Architectures},

isbn={9781450315722},

pages={73-82},

abstract={Assume that n sensors with identical range r = f(n)/2n, for some f(n) > 1 for all n, are thrown randomly and independently with the uniform distribution in the unit interval [0,1]. They are required to move to new positions so as to cover the entire unit interval in the sense that every point in the interval is within the range of a sensor. We obtain tradeoffs between the expected sum and maximum of displacements of the sensors and their range required to accomplish this task. In particular, when f(n) = 1 the expected total displacement is shown to be Θ(√n). For sensors with larger ranges we present two algorithms that prove the upper bound for the sum drops sharply as f(n) increases. The first of these holds for f(n) ≥ 6 and shows the total movement of the sensors is O ( √In n/(n)) while the second holds for 12 ≤ f(n) ≤ In n - 2 In In n and gives an upper bound of O(ln n/f(n)ef(n)/2 ). Note that the second algorithm improves upon the first for f(n) δ In In n - In In Inn. Further we show a lower bound, for any 1 ω f(n) < √n of (εf/(n)e-(1+ε)/(n)),ε> 0. For the case of the expected maximum displacement of a sensor when f(n) = 1 our bounds are (n -1/2) and for any ε > 0, O(n-1/2+ε). For larger sensor ranges (up to (1 - ε)ln n/n ε > O) the expected maximum displacement is shown to be Θ(ln n/n). We also obtain similar sum and maximum displacement and range tradeoffs for area coverage for sensors thrown at random in a unit square. In this case, for the expected maximum displacement our bounds are tight and for the expected sum they are within a factor of √ln n. Finally, we investigate the related problem of the expected total and maximum displacement for perimeter coverage (whereby only the perimeter of the region need be covered) of a unit square. For example, when n sensors of radius > 2/n are thrown randomly and independently with the uniform distribution in the interior of a unit square, we can show the total expected displacement required to cover the perimeter is n/12 + o(n). © 2013 ACM.},

year={2013},

keywords={Barrier, Coverage, Displacement, Mobile, Random, Sensors},

}

** RefWorks **

RT Conference Proceedings

SR Print

ID 190064

A1 Kranakis, Evangelos

A1 Kriz̧anc, Danny

A1 Morales-Ponce, Oscar

A1 Narayanan, Lata

A1 Opatrný, Jaroslav

A1 Shende, Sunil M.

T1 Expected sum and maximum of displacement of random sensors for coverage of a domain

YR 2013

T2 Annual ACM Symposium on Parallelism in Algorithms and Architectures

SN 9781450315722

SP 73

OP 82

AB Assume that n sensors with identical range r = f(n)/2n, for some f(n) > 1 for all n, are thrown randomly and independently with the uniform distribution in the unit interval [0,1]. They are required to move to new positions so as to cover the entire unit interval in the sense that every point in the interval is within the range of a sensor. We obtain tradeoffs between the expected sum and maximum of displacements of the sensors and their range required to accomplish this task. In particular, when f(n) = 1 the expected total displacement is shown to be Θ(√n). For sensors with larger ranges we present two algorithms that prove the upper bound for the sum drops sharply as f(n) increases. The first of these holds for f(n) ≥ 6 and shows the total movement of the sensors is O ( √In n/(n)) while the second holds for 12 ≤ f(n) ≤ In n - 2 In In n and gives an upper bound of O(ln n/f(n)ef(n)/2 ). Note that the second algorithm improves upon the first for f(n) δ In In n - In In Inn. Further we show a lower bound, for any 1 ω f(n) < √n of (εf/(n)e-(1+ε)/(n)),ε> 0. For the case of the expected maximum displacement of a sensor when f(n) = 1 our bounds are (n -1/2) and for any ε > 0, O(n-1/2+ε). For larger sensor ranges (up to (1 - ε)ln n/n ε > O) the expected maximum displacement is shown to be Θ(ln n/n). We also obtain similar sum and maximum displacement and range tradeoffs for area coverage for sensors thrown at random in a unit square. In this case, for the expected maximum displacement our bounds are tight and for the expected sum they are within a factor of √ln n. Finally, we investigate the related problem of the expected total and maximum displacement for perimeter coverage (whereby only the perimeter of the region need be covered) of a unit square. For example, when n sensors of radius > 2/n are thrown randomly and independently with the uniform distribution in the interior of a unit square, we can show the total expected displacement required to cover the perimeter is n/12 + o(n). © 2013 ACM.

LA eng

OL 30