In-network area estimation and localization in Wireless Sensor Networks

Published on Dec 1, 2012 in GLOBECOM (Global Communications Conference)
· DOI :10.1109/GLOCOMW.2012.6477611
Srabani Kundu2
Estimated H-index: 2
(Guru Nanak Institute of Technology),
Nabanita Das12
Estimated H-index: 12
(ISI: Indian Statistical Institute)
In many applications of Wireless Sensor Networks (WSN), a large number of sensor nodes are distributed over an area under investigation. The sensors collect ground data at definite time interval and forward it to the sink. In case of an event, it is often required to estimate the affected area and to identify the location of the event. Since, in WSN, communication is costlier than in-network computation in terms of energy, it is better if the area can be estimated in a distributed fashion on the way when sensed data are forwarded to the sink via multi hop paths. In this paper, a light-weight distributed algorithm is proposed to estimate the area as well as to locate its center. Each node requires only the knowledge of its own location and transmits a single packet per round. Simulation studies have been done to evaluate the performance. Comparison with two other algorithms proposed earlier for area computation without localization shows that our algorithm performs better in terms of accuracy of area estimation improving the error percentage from 15% to 2%. Besides area estimation, the proposed procedure also can locate the center of the affected area with less than 1% error.
📖 Papers frequently viewed together
5 Authors (Xiaoyang Liu, ..., Xiaoping Zeng)
1 Citations
6 Citations
1 Author (Chen Li-qiang)
Mar 14, 2010 in INFOCOM (International Conference on Computer Communications)
#1Chengzhi Li (NCSU: North Carolina State University)H-Index: 8
#2Huaiyu Dai (NCSU: North Carolina State University)H-Index: 35
In this paper we study distributed function computation in a noisy multi-hop wireless network, in which nnodes are uniformly and independently distributed in a unit square. We adopt the adversarial noise model, for which independent binary symmetric channels are assumed for any point-to-point transmissions, with (not necessarily identical) crossover probabilities bounded above by some constant ε. Each node holds an m-bit integer per instance and the computation is started after each node...
7 CitationsSource
#1Navin GoyalH-Index: 20
#2Guy KindlerH-Index: 25
Last. Michael SaksH-Index: 57
view all 3 authors...
We prove the first nontrivial (superlinear) lower bound in the noisy broadcast model, defined by El Gamal in [Open problems presented at the 1984workshop on Specific Problems in Communication and Computation sponsored by Bell Communication Research, in Open Problems in Communication and Computation, T. M. Cover and B. Gopinath, eds., Springer-Verlag, New York, 1987, pp. 60-62]. In this model there are n+1processors P_0,P_1,\ldots,P_n each of which is initially given a private input bit ...
36 CitationsSource
#1Lei Ying (UIUC: University of Illinois at Urbana–Champaign)H-Index: 40
#2R. Srikant (UIUC: University of Illinois at Urbana–Champaign)H-Index: 85
Last. Geir E. Dullerud (UIUC: University of Illinois at Urbana–Champaign)H-Index: 34
view all 3 authors...
In this correspondence, we consider a wireless sensor network consisting of n sensors, and each sensor has a measurement, which is an integer value belonging to the set {().....m-1}, so that it can be represented by [log2 m] bits. The network has a special node called the fusion center whose goal is to compute a symmetric function of these measurements. The problem studied is to minimize the total transmission energy used by the network when computing this function, subject to the constraint tha...
62 CitationsSource
#1Jie Lian (UW: University of Waterloo)H-Index: 7
#2Lei ChenH-Index: 75
Last. Gordon B. AgnewH-Index: 7
view all 5 authors...
In many applications of sensor networks, the sink needs to keep track of the history of sensed data of a monitored region for scientific analysis or supporting historical queries. We call these historical data a time series of value distributions or snapshots. Obviously, to build the time series snapshots by requiring all of the sensors to transmit their data to the sink periodically is not energy efficient. In this paper, we introduce the idea of gradient boundary and propose the gradient bound...
36 CitationsSource
#1A. Giridhar (UIUC: University of Illinois at Urbana–Champaign)H-Index: 1
#2P. R. Kumar (UIUC: University of Illinois at Urbana–Champaign)H-Index: 70
In wireless sensor networks, one is not interested in downloading all the data from all the sensors. Rather, one is only interested in collecting from a sink node a relevant function of the sensor measurements. This paper studies the maximum rate at which functions of sensor measurements can be computed and communicated to the sink node. It focuses on symmetric functions, where only the data from a sensor is important, not its identity. The results include the following. The maximum rate of down...
366 CitationsSource
#1Robert Nowak (UW: University of Wisconsin-Madison)H-Index: 85
#2Urbashi MitraH-Index: 47
Last. Rebecca WillettH-Index: 36
view all 3 authors...
Sensor networks have emerged as a fundamentally new tool for monitoring spatial phenomena. This paper describes a theory and methodology for estimating inhomogeneous, two-dimensional fields using wireless sensor networks. Inhomogeneous fields are composed of two or more homogeneous (smoothly varying) regions separated by boundaries. The boundaries, which correspond to abrupt spatial changes in the field, are nonparametric one-dimensional curves. The sensors make noisy measurements of the field, ...
124 CitationsSource
#1Ben GreensteinH-Index: 15
#2Eddie KohlerH-Index: 51
Last. Deborah EstrinH-Index: 133
view all 4 authors...
We study four distributed techniques for computing the area of a region in a sensor network. Area calculation is a fundamental sensor network primitive, and distributed, in-network approaches prove more scalable than centralized collection in terms of energy consumption. The four techniques—Delaunay triangulations, Voronoi diagrams, and two new, simpler algorithms, inverse neighborhood and inverse neighborhood with location—vary in computational complexity, communication cost, and information re...
15 Citations
#1Bhaskar Krishnamachari (SC: University of Southern California)H-Index: 82
#2S. Sitharama Iyengar (LSU: Louisiana State University)H-Index: 62
We propose a distributed solution for a canonical task in wireless sensor networks - the binary detection of interesting environmental events. We explicitly take into account the possibility of sensor measurement faults and develop a distributed Bayesian algorithm for detecting and correcting such faults. Theoretical analysis and simulation results show that 85-95 percent of faults can be corrected using this algorithm, even when as many as 10 percent of the nodes are faulty.
577 CitationsSource
#1Piyush Gupta (UIUC: University of Illinois at Urbana–Champaign)H-Index: 24
#2P. R. KumarH-Index: 70
When n identical randomly located nodes, each capable of transmitting at W bits per second and using a fixed range, form a wireless network, the throughput /spl lambda/(n) obtainable by each node for a randomly chosen destination is /spl Theta/(W//spl radic/(nlogn)) bits per second under a noninterference protocol. If the nodes are optimally placed in a disk of unit area, traffic patterns are optimally assigned, and each transmission's range is optimally chosen, the bit-distance product that can...
8,088 CitationsSource
We introduce a geometric transformation that allows Voronoi diagrams to be computed using a sweepline technique. The transformation is used to obtain simple algorithms for computing the Voronoi diagram of point sites, of line segment sites, and of weighted point sites. All algorithms haveO(n logn) worst-case running time and useO(n) space.
972 CitationsSource
Cited By6
#1Sai Zhang (Qualcomm)H-Index: 7
#2Cihan Tepedelenlioglu (ASU: Arizona State University)H-Index: 28
Last. Andreas Spanias (ASU: Arizona State University)H-Index: 32
view all 3 authors...
A fully distributed algorithm for estimating the center and the radius of the smallest sphere that contains a wireless sensor network is proposed. The center finding problem is formulated as a convex optimization problem in summation form by using a soft-max approximation to the maximum function. Diffusion adaptation method is used where states of nodes converge to the estimated center distributively. Then, distributed max consensus is used to compute the radius. The proposed algorithm is fully ...
8 CitationsSource
#1Sai Zhang (ASU: Arizona State University)H-Index: 7
Last. Mahesh K. Banavar (Clarkson University)H-Index: 17
view all 4 authors...
Abstract The area of detection and estimation in a distributed wireless sensor network (WSN) has several applications, including military surveillance, sustainability, health monitoring, and Internet of Things (IoT). Compared with a wired centralized sensor network, a distributed WSN has many advantages including scalability and robustness to sensor node failures. In this book, we address the problem of estimating the structure of distributed WSNs. First, we provide a literature review in: (a) g...
6 Citations
#1Srabani Kundu (ISI: Indian Statistical Institute)H-Index: 2
#2Nabanita Das (ISI: Indian Statistical Institute)H-Index: 12
Last. Dibakar Saha (ISI: Indian Statistical Institute)H-Index: 4
view all 4 authors...
In a wireless sensor network (WSN), sensor nodes are deployed to monitor a region. When an event occurs, it is important to detect and estimate the boundary of the affected area and to gather the information to the sink node in real time. In case, all the affected nodes are allowed to send data, congestion may occur, increasing path delay, and also exhausting the energy of the nodes in forwarding a large number of packets. Hence, it is a challenging problem to select a subset of affected nodes, ...
2 CitationsSource
Oct 1, 2017 in ASILOMAR (Asilomar Conference on Signals, Systems and Computers)
#1Sai Zhang (ASU: Arizona State University)H-Index: 7
#2Cihan Tepedelenlioglu (ASU: Arizona State University)H-Index: 28
Last. Andreas Spanias (ASU: Arizona State University)H-Index: 32
view all 3 authors...
A fully distributed algorithm for estimating the center and coverage region of a wireless sensor network (WSN) is proposed. The proposed algorithm is useful in many applications, such as finding the required power for a certain level of connectivity in WSNs and localizing a service center in a network. The network coverage region is defined to be the smallest sphere that covers all the sensor nodes. The center and radius of the smallest covering sphere are estimated. The center estimation is for...
#1Srabani Kundu (Guru Nanak Institute of Technology)H-Index: 2
In many real life applications of WSN, to monitor a wide inaccessible area, a large number of sensor nodes are deployed randomly over the region. When an event occurs, to identify the affected area immediately, it is necessary that the data and the locations of the affected nodes are reported to the sink node with minimum latency. In this paper, for 2D region, using some light-weight distributed in-node processing, a reduced set of boundary nodes are identified, which report to the sink node fol...
1 CitationsSource
#1Srabani Kundu (Guru Nanak Institute of Technology)H-Index: 2
#2Nabanita Das (ISI: Indian Statistical Institute)H-Index: 12
Given a large number of sensor nodes distributed randomly over a 2D region, we address the problem of estimating the boundary of an area affected by an event. The boundaries are often irregular shaped and accurate estimation of such boundaries requires complex computation and data structures which the tiny inexpensive sensor nodes, in general, can not support. In this paper, given a random distribution of homogeneous sensor nodes, in case of an event, the affected nodes execute a simple O(d) dis...
6 CitationsSource