Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
On the Displacement for Covering a Square with Randomly Placed Sensors
verfasst von : Rafał Kapelko, Evangelos Kranakis
Erschienen in: Ad-hoc, Mobile, and Wireless Networks
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Consider \(n\) sensors placed randomly and independently with the uniform distribution in a unit square. The sensors have identical sensing range equal to \(r\), for some \(r >0\). We are interested in moving the sensors from their initial positions to new positions so as to ensure that the unit square is completely covered, i.e., every point in the square is within the range of a sensor. If the \(i\)-th sensor is displaced a distance \(d_i\), what is a displacement of minimum cost? As cost measure for the displacement of the team of sensors we consider the \(a\)-total movement defined as the sum \(M_a:= \sum _{i=1}^n d_i^a\), for some constant \(a>0\). We assume that \(r\) and \(n\) are chosen so as to allow full coverage of the square and \(0 < a \le 4\). The main contribution of the paper is to show the existence of a tradeoff between the square sensing radius and \(a\)-total movement and can be summarized as follows:
1.
If the square sensing radius is equal to \(\frac{1}{2\sqrt{n}}\) and \(n\) is the square of a natural number we present an algorithm and show that in expectation the \(a\)-total movement is in \(O(n^{1- a/4})\).
2.
If the square sensing radius is greater than \( \frac{2\sqrt{3}}{\sqrt{n}}\) and \(n\) is natural number then we present an algorithm and show that in expectation the \(a\)-total movement is in \(O(n^{1-a/2} (\ln n)^{a/4} )\).
Therefore this sharp decrease from \(O(n^{1- a/4})\) to \(O(n^{1-a/2} (\ln n)^{a/4} )\) in the \(a\)-total movement of the sensors to attain complete coverage of the square indicates the presence of an interesting threshold on the square sensing radius when it increases from \(\frac{1}{2\sqrt{n}}\) to \( \frac{2\sqrt{3}}{\sqrt{n}}\). In addition, we simulate our algorithms above and discuss the results of our simulations.