Beacon node placement, node-to-node measurement, and target node positioning are the three key steps for a localization process. However, compared with the other two steps, beacon node placement still lacks a comprehensive, systematic study in research literatures. To fill this gap, we address the Beacon Node Placment (BNP) problem that deploys beacon nodes for minimal localization error in this paper. BNP is difficult in that the localization error is determined by a complicated combination of factors, i.e., the localization error differing greatly under a different environment, with a different algorithm applied, or with a different type of beacon node used. In view of the hardness of BNP, we propose an approximate function to reduce time cost in localization error calculation, and also prove its time complexity and error bound. By approximation, a sub-optimal distribution of beacon nodes could be found within acceptable time cost for placement. In the experiment, we test our method and compare it with other node placement methods under various settings and environments. The experimental results show feasibility and effectiveness of our method in practice.
Beacon node placement has been previously studied for coverage and distribution in research literature. In the coverage problem, it is required to use the minimal number of beacon nodes to achieving k-coverage in a given area. As it is proved to be NP-hard @cite_3 , some approximate @cite_8 and random @cite_4 placement methods are proposed to k-cover bounded or unbounded area. As for distribution, a typical work is to locate a target node by Trilateration or Multilateration when beacon nodes are in GDoP optimal distribution @cite_17 . And also, beacon nodes are deployed by random, max and grid placement @cite_21 for localization.
@cite_4 @cite_8 @cite_21 @cite_3 @cite_17
2157165312 1989231680 2100465929 2141685007 1974025511
We propose new algorithms to achieve k-coverage in dense sensor networks. In such networks, covering sensor locations approximates covering the whole area. However, it has been shown before that selecting the minimum set of sensors to activate from an already deployed set of sensors is NP-hard. We propose an efficient approximation algorithm which achieves a solution of size within a logarithmic factor of the optimal. We prove that our algorithm is correct and analyze its complexity. We implement our algorithm and compare it against two others in the literature. Our results show that the logarithmic factor is only a worst-case upper bound and the solution size is close to the optimal in most cases. A key feature of our algorithm is that it can be implemented in a distributed manner with local information and low message complexity. We design and implement a fully distributed version of our algorithm. Our distributed algorithm does not require that sensors know their locations. Comparison with two other distributed algorithms in the literature indicates that our algorithm: (i) converges much faster than the others, (ii) activates near-optimal number of sensors, and (iii) significantly prolongs (almost doubles) the network lifetime because it consumes much less energy than the other algorithms. Sensing coverage is an essential functionality of wireless sensor networks (WSNs). However, it is also well known that coverage alone in WSNs is not sufficient, and hence network connectivity should also be considered for the correct operation of WSNs. In this paper, we address the problem of k-coverage in WSNs such that in each scheduling round, every location in a monitored field (or simply field) is covered by at least k active sensors while all active sensors are being connected. Precisely, we study sensors duty-cycling strategies for generating k-coverage configurations in WSNs. First, we model the k-coverage problem in WSNs. Second, we derive a sufficient condition of the sensor spatial density for complete k-coverage of a field. We also provide a relationship between the communication and sensing ranges of sensors to maintain both k-coverage of a field and connectivity among all active sensors. Third, we propose four configuration protocols to solve the problem of k-coverage in WSNs. We prove that our protocols select a minimum number of sensors to achieve full k-coverage of a field while guaranteeing connectivity between them. Then, we relax some widely used assumptions for coverage configuration in WSNs, to promote the use of our proposed protocols in real-world sensing applications. Our simulation results show that our protocols outperform an existing distributed k-coverage configuration protocol. Beacon placement strongly affects the quality of spatial localization, a critical service for context-aware applications in wireless sensor networks; yet this aspect of localization has received little attention. Fixed beacon placement approaches such as uniform and very dense placement are not always viable and will be inadequate in very noisy environments in which sensor networks may be expected to operate (with high terrain and propagation uncertainties). We motivate the need for empirically adaptive beacon placement and outline a general approach based on exploration and instrumentation of the terrain conditions by a mobile human or robot agent. We design, evaluate and analyze three novel adaptive beacon placement algorithms using this approach for localization based on RF-proximity. In our evaluation, we find that beacon density rather than noise level has a more significant impact on beacon placement algorithms. Our beacon placement algorithms are applicable to a low (beacon) density regime of operation. Noise makes moderate density regimes more improvable. Spatial query execution is an essential functionality of a sensor network, where a query gathers sensor data within a specific geographic region. Redundancy within a sensor network can be exploited to reduce the communication cost incurred in execution of such queries. Any reduction in communication cost would result in an efficient use of the battery energy, which is very limited in sensors. One approach to reduce the communication cost of a query is to self-organize the network, in response to a query, into a topology that involves only a small subset of the sensors sufficient to process the query. The query is then executed using only the sensors in the constructed topology. The self-organization technique is beneficial for queries that run sufficiently long to amortize the communication cost incurred in self-organization. In this paper, we design and analyze algorithms for suchself-organization of a sensor network to reduce energy consumption. In particular, we develop the notion of a connected sensor cover and design a centralized approximation algorithm that constructs a topology involving a near-optimal connected sensor cover. We prove that the size of the constructed topology is within an O(logn) factor of the optimal size, where n is the network size. We develop a distributed self-organization version of the approximation algorithm, and propose several optimizations to reduce the communication overhead of the algorithm. We also design another distributed algorithm based on node priorities that has a further lower communication overhead, but does not provide any guarantee on the size of the connected sensor cover constructed. Finally, we evaluate the distributed algorithms using simulations and show that our approaches results in significant communication cost reductions. The authors present a review of the GDOP metric as used in GPS. Their goal is to review this metric and many of its known bounds as well as to report some new results. They use a formal linear algebraic framework to aid further study and insight.