![]() |
The Coverage Problem in a Wireless Sensor Network - Printable Version +- Free Academic Seminars And Projects Reports (https://easyreport.in) +-- Forum: Seminars Topics And Discussions (https://easyreport.in/forumdisplay.php?fid=30) +--- Forum: Miscellaneous Seminars Topics (https://easyreport.in/forumdisplay.php?fid=21) +---- Forum: General Seminar Topics (https://easyreport.in/forumdisplay.php?fid=58) +---- Thread: The Coverage Problem in a Wireless Sensor Network (/showthread.php?tid=59080) |
The Coverage Problem in a Wireless Sensor Network - siddhartha - 10-04-2017 The Coverage Problem in a Wireless Sensor Network [attachment=17748] ABSTRACT One fundamental issue in sensor networks is the coverage problem, which reflects how well a sensor network is monitored or tracked by sensors. In this paper, we formulate this problem as a decision problem, whose goal is to determine whether every point in the service area of the sensor network is covered by at least k sensors, where k is a predefined value. The sensing ranges of sensors can be unit disks or non-unit disks. We present polynomial-time algorithms, in terms of the number of sensors, that can be easily translated to distributed protocols. The result is a generalization of some earlier results where only k = 1 is assumed. Applications of the result include: (i) positioning applications, (ii) situations which require stronger environmental monitoring capability, and (ii) scenarios which impose more stringent fault-tolerant capability. Categories and Subject Descriptors F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems Geometrical problems and computations, Routing and layout General Terms Algorithms, Measurement, Reliability, Performance, Theory Keywords ad hoc network, computer geometry, coverage problem, ubiquitous computing, wireless network, sensor network 1. INTRODUCTION The rapid progress of wireless communication and embedded micro-sensing MEMS technologies has made wireless sensor networks possible. Such environments may have many inexpensive wireless nodes, each capable of collecting, storing, and processing environmental information, and communicating with neighboring nodes. In the past, sensors are connected by wire lines. Today, this environment is combined with the novel ad hoc networking technology to facilitate inter-sensor communication [4, 15]. THE PROPOSED SOLUTIONS At the first glance, the coverage problem seems to be very difficult. A naive solution is to find out all sub-regions divided by the sensing regions of all n sensors (i.e., n circles), and then check if each sub-region is k-covered or not, as shown in Fig. 1. Managing all sub-regions is a difficult and computationally expensive job in geometry because there could exist as many as O(n2) sub-regions divided by the circles. Also, it may be difficult to calculate these sub-regions. 3.1 The k-UC Problem In the section, we propose a solution to the k-UC problem, which has a cost of O(nd log d), where d is the maximum number of sensors that may intersect a sensor. Instead of determining the coverage of each sub-region, our approach tries to look at how the perimeter of each sensor s sensing range is covered. Specifically, our algorithm tries to determine whether the perimeter of a sensor under consideration is sufficiently covered. By collecting this information from all sensors, a correct decision can be made. |