Coverage in wireless ad hoc sensor networks

Published on Jun 1, 2003in IEEE Transactions on Computers2.663
路 DOI :10.1109/TC.2003.1204831
Xiang-Yang Li89
Estimated H-index: 89
(IIT: Illinois Institute of Technology),
Peng-Jun Wan57
Estimated H-index: 57
(IIT: Illinois Institute of Technology),
Ophir Frieder53
Estimated H-index: 53
(IIT: Illinois Institute of Technology)
Sources
Abstract
Sensor networks pose a number of challenging conceptual and optimization problems such as location, deployment, and tracking. One of the fundamental problems in sensor networks is the calculation of the coverage. In Meguerdichian et al. (2001), it is assumed that the sensor has uniform sensing ability. We provide efficient distributed algorithms to optimally solve the best-coverage problem raised in the above-mentioned article. In addition, we consider a more general sensing model: the sensing ability diminishes as the distance increases. As energy conservation is a major concern in wireless (or sensor) networks, we also consider how to find an optimum best-coverage-path with the least energy consumption and how to find an optimum best-coverage-path that travels a small distance. In addition, we justify the correctness of the method proposed above that uses the Delaunay triangulation to solve the best coverage problem and show that the search space of the best coverage problem can be confined to the relative neighborhood graph, which can be constructed locally.
Figures & Tables
Download
馃摉 Papers frequently viewed together
2003
2 Authors (Suman Banerjee)
References26
Newest
Nov 7, 2002 in INFOCOM (International Conference on Computer Communications)
#1Xiang-Yang Li (IIT: Illinois Institute of Technology)H-Index: 89
#2Gruia Calinescu (IIT: Illinois Institute of Technology)H-Index: 30
Last. Peng-Jun Wan (IIT: Illinois Institute of Technology)H-Index: 57
view all 3 authors...
Several localized routing protocols (see Bose, P. and Morin, P., Proc. 10th Annual Int. Symp. on Algorithms and Computation ISAAC, 1999) guarantee the delivery of packets when the underlying network topology is the Delaunay triangulation of all wireless nodes. However, it is expensive to construct the Delaunay triangulation in a distributed manner. Given a set of wireless nodes, we more accurately model the network as a unit-disk graph, UDG, in which a link between two nodes exists only if the d...
Source
#1Siu Man Lui (HKUST: Hong Kong University of Science and Technology)H-Index: 10
#2Karl Reiner Lang (HKUST: Hong Kong University of Science and Technology)H-Index: 20
Last. Sai Ho Kwok (HKUST: Hong Kong University of Science and Technology)H-Index: 14
view all 3 authors...
Businesses are trying to explore new business opportunities in the newly emerging P2P technology applications. Motivating peer members through incentive mechanisms to supply contributions to the system and controlling free riding are suggested in this paper as important success factors for developing P2P-based business models. We review the psychology and community behavior literature in order to provide an explanation for the reasons why people get motivated to participate in P2P systems and to...
Source
#1Xiang-Yang Li (IIT: Illinois Institute of Technology)H-Index: 89
#2Peng-Jun Wan (IIT: Illinois Institute of Technology)H-Index: 57
Last. Ophir Frieder (IIT: Illinois Institute of Technology)H-Index: 53
view all 4 authors...
We consider how to construct power efficient wireless ad hoc networks. We propose two different methods combining several well-known proximity graphs including the Gabriel graph and the Yao graph, which can be constructed locally and efficiently. Firstly, we combine the Gabriel structure and the Yao structure. The constructed topology has at most O(n) edges and each node has a bounded out-degree. Secondly, we use the Yao structure and then use the reverse of the Yao structure. The constructed to...
Source
#1Xiang-Yang Li (IIT: Illinois Institute of Technology)H-Index: 89
#2Peng-Jun WanH-Index: 57
Last. Yu WangH-Index: 55
view all 3 authors...
Due to the limited resources available in the wireless ad hoc networking nodes, the scalability is crucial for network operations. One effective approach is to maintain only a sparse spanner of a linear number of links while still preseving the power-efficient route for any pair of nodes. For any spanner G, its power stretch factor is defined as the maximum ratio of the minimum power needed to support any link in this spanner to the least necessary. In this paper, we first consider several well-...
Source
Jul 16, 2001 in MOBICOM (ACM/IEEE International Conference on Mobile Computing and Networking)
#1Seapahn Meguerdichian (UCLA: University of California, Los Angeles)H-Index: 6
#2Farinaz Koushanfar (University of California, Berkeley)H-Index: 63
Last. Miodrag Potkonjak (UCLA: University of California, Los Angeles)H-Index: 77
view all 4 authors...
Wireless ad-hoc sensor networks will provide one of the missing connections between the Internet and the physical world. One of the fundamental problems in sensor networks is the calculation of coverage. Exposure is directly related to coverage in that it is a measure of how well an object, moving on an arbitrary path, can be observed by the sensor network over a period of time. In addition to the informal definition, we formally define exposure and study its properties. We have developed an eff...
Source
Apr 22, 2001 in INFOCOM (International Conference on Computer Communications)
#1Seapahn Meguerdichian (UCLA: University of California, Los Angeles)H-Index: 6
#2Farinaz KoushanfarH-Index: 63
Last. Mani SrivastavaH-Index: 106
view all 4 authors...
Wireless ad-hoc sensor networks have recently emerged as a premier research topic. They have great long-term economic potential, ability to transform our lives, and pose many new system-building challenges. Sensor networks also pose a number of new conceptual and optimization problems. Some, such as location, deployment, and tracking, are fundamental issues, in that many applications rely on them for needed information. We address one of the fundamental problems, namely coverage. Coverage in gen...
Source
#1Srdjan Capkun ('ENS Paris': 脡cole Normale Sup茅rieure)H-Index: 70
#2Maher Hamdi ('ENS Paris': 脡cole Normale Sup茅rieure)H-Index: 3
Last. Jean-Pierre Hubaux ('ENS Paris': 脡cole Normale Sup茅rieure)H-Index: 92
view all 3 authors...
We consider the problem of node positioning in ad-hoc networks. We propose a distributed, infrastructure-free positioning algorithm that does not rely on Global Positioning System (GPS). The algorithm uses the distances between the nodes to build a relative coordinate system in which the node positions are computed in two dimensions. The main contribution of this work is to define and compute relative positions of the nodes in an ad-hoc network without using GPS. We further explain how the propo...
Source
#1Mauricio Marengoni (UMass: University of Massachusetts Amherst)H-Index: 9
#2Bruce A. Draper (CSU: Colorado State University)H-Index: 44
Last. Ramesh K. Sitaraman (UMass: University of Massachusetts Amherst)H-Index: 40
view all 4 authors...
Abstract The Art Gallery Problem deals with determining the number of observers necessary to cover an art gallery room such that every point is seen by at least one observer. This problem is well known and has a linear time solution for the 2D case, but little is known in the 3D case. In this paper we present a polynomial time solution for the 3D version of the Art Gallery Problem. Because the problem is NP-hard, the solution presented is an approximation, and we present the bounds to our soluti...
Source
#1A. Molina (UoB: University of Bristol)H-Index: 7
Last. Andrew R NixH-Index: 47
view all 3 authors...
The cost and complexity of a network is closely related to the number of base-stations (BSs) required to achieve the system operator's service objectives. The location of BSs is not an easy task and there are numerous factors that must be taken into account when deciding the optimum position of BSs. This paper discusses the performance of three different algorithms developed to solve the BS location problem: the greedy algorithm (GR), the genetic algorithm (GA) and the combination algorithm for ...
Source
#1Piyush GuptaH-Index: 74
#2P. KumarH-Index: 10
In wireless data networks each transmitter's power needs to be high enough to reach the intended receivers, while generating minimum interference on other receivers sharing the same channel. In particular, if the nodes in the network are assumed to cooperate in routing each oth颅 ers' packets, as is the case in ad hoc wireless networks, each node should transmit with just enough power to guarantee connectivity in the network. Towards this end, we derive the critical power a node in the network ne...
Source
Cited By469
Newest
#1Pooja Chaturvedi (NU: Nirma University of Science and Technology)
#2A. K. Daniel (Madan Mohan Malaviya University of Technology)H-Index: 7
Wireless sensor network (WSN) is an emerging research field in recent years. The advancement in sensory device and communication technologies has enabled the deployment of diverse sensor networks such as random network consisting of thousand sensors or carefully deployed deterministic network. Despite the plethora of applicability of sensor networks, there are some limitations too such as energy efficiency, lifetime, coverage, localization etc. As the sensor nodes are battery driven so conservat...
Source
#1Hung Le (UMass: University of Massachusetts Amherst)H-Index: 6
#2Cuong Than (UMass: University of Massachusetts Amherst)
The greedy spanner in a low dimensional Euclidean space is a fundamental geometric construction that has been extensively studied over three decades as it possesses the two most basic properties of a good spanner: constant maximum degree and constant lightness. Recently, Eppstein and Khodabandeh showed that the greedy spanner in \mathbb{R}^2admits a sublinear separator in a strong sense: any subgraph of kvertices of the greedy spanner in \mathbb{R}^2has a separator of size O(\sqrt{k})..
Abstract The problem of coverage in two-dimensional (2D) wireless sensor networks is challenging and is still open. Precisely, determining the minimum sensor density (i.e, minimum number of sensors per unit area) that is required to cover a 2D field of interest (FoI), where every point in the field is covered by at least one sensor, is still under investigation. The problem of 2D k-coverage, which requires that every point in a 2D FoI be covered by at least k sensors, where k 鈮 1 , is more chall...
Source
Consider a two-dimensional rectangular region guarded by a set of sensors, which may be smart networked surveillance cameras or simpler sensor devices. In order to evaluate the level of security provided by these sensors, it is useful to find and evaluate the path with the lowest level of exposure to the sensors. Then, if desired, additional sensors can be placed at strategic locations to increase the level of security provided. General forms of these two problems are presented in this paper. Ne...
Source
#3Rakesh Swain (Siksha O Anusandhan University)H-Index: 2
Abstract Vehicular Ad-hoc NETwork (VANET) is a meteoric growing research area due to the technological advancement in sensing, computation, communication, and radio wireless technology. The demand for VANET is increasing day by day due to the numerous diverse applications. Applications of VANET include safety applications like reduction in the road accident by broadcasting messages to the driver, convenience applications like automatic parking service, commercial applications like selling and bu...
Source
Voronoi diagrams are powerful for understanding spatial properties. However, few reports have been made for moving generators despite their important applications. We present a topology-oriented event-increment (TOI-E) algorithm for constructing a Voronoi diagram of moving circular disks in the plane over the time horizon [ 0, t(infinity)). The proposed TOI-E algorithm computes the event history of the Voronoi diagram over the entire time horizon in O(kF logn + kC n logn) time with O(n logn) pre...
Source
May 1, 2021 in ISCAS (International Symposium on Circuits and Systems)
#2Xiang Li (Fudan University)H-Index: 70
Source
#1Lili Zhang (Soochow University (Suzhou))H-Index: 2
#2Cheng-Kuan Lin (FZU: Fuzhou University)H-Index: 10
Last. Yuan-Hsiang Teng (Providence University)H-Index: 8
view all 5 authors...
Target traversing is an important research topic in wireless sensor networks, with most studies examining coverage issues of the target鈥檚 moving paths. The best coverage path is one that minimizes the target support to the sensors. Most existing algorithms either ensure that the target remains as close as possible to the sensors or deploy sensors to enhance coverage. In this paper, we consider a scenario where the target must traverse the sensor network within a certain time constraint. Furtherm...
Source
#1S.S. AravinthH-Index: 1
#2J. Senthilkumar (Sona College of Technology)H-Index: 5
Last. Y. Suresh (Sona College of Technology)H-Index: 6
view all 4 authors...
Source
#1Roland KatonaH-Index: 2
#2Victor CioncaH-Index: 10
Last. Dirk PeschH-Index: 26
view all 4 authors...
A recent trend in wireless sensor networks (WSNs) is network virtualization to support on-demand sharing of sensing functionality. The efficient allocation of WSN resources to sensing requests is obtained using virtual network embedding (VNE). This must take into account Quality of Service (e.g., reliability), Quality of Information (e.g., sensing accuracy), and deal with wireless interference. With increased computational complexity due to the added constraints, finding an optimal solution can ...
Source
This website uses cookies.
We use cookies to improve your online experience. By continuing to use our website we assume you agree to the placement of these cookies.
To learn more, you can find in our Privacy Policy.