20130911
Expected sum and maximum of displacement of random sensors for coverage of a domain
Publication
Publication
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(n1/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).
Additional Metadata  

Keywords  Barrier, Coverage, Displacement, Mobile, Random, Sensors 
Conference  25th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2013 
Citation 
Kranakis, E, Krizanc, D. (Danny), MoralesPonce, O. (Oscar), Narayanan, L. (Lata), Opatrny, J. (Jaroslav), & Shende, S. (Sunil). (2013). Expected sum and maximum of displacement of random sensors for coverage of a domain. Presented at the 25th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2013.
