Coverage Problems in Wireless Ad-hoc Sensor Networks Seapahn Meguerdichian1, Farinaz Koushanfar2, Miodrag Potkonjak1, Mani B. Srivastava2
1 Computer Science Department, University of California, Los Angeles
2 Electrical Engineering Department, University of California, Los Angeles
{apahn, miodrag}@cs.ucla.edu
{farinaz, mbs}@ee.ucla.edu
Abstract - Wireless ad-hoc nsor networks have recently emerged as a premier rearch topic. They have great long-term economic potential, ability to transform our lives, and po many new system-building challenges. Sensor networks also po a number of new conceptual and optimization prob-lems. Some, such as location, deployment, and tracking, are fundamental issues, in that many applications rely on them for needed information.
In this paper, we address one of the fundamental problems, namely coverage. Coverage in general, answers the questions about quality of rvice (surveillance) that can be provided by a particular nsor network. We first define the coverage problem from veral points of view including deterministi
c, statistical, worst and best ca, and prent examples in each domain. By combining computational geometry and graph theoretic techniques, specifically the Voronoi diagram and graph arch algorithms, we establish the main highlight of the paper - optimal polynomial time worst and average ca algorithm for coverage calculation. We also prent compre-hensive experimental results and discuss future rearch di-rections related to coverage in nsor networks.
I. I NTRODUCTION
As our personal computing era evolves into a ubiquitous computing one, there is a need for a world of fully con-nected devices with inexpensive wireless networks. Im-provements in wireless network technology interfacing with emerging micro-nsor bad on MEMs technology [2], is allowing sophisticated inexpensive nsing, storage, processing, and communication capabilities to be unobtru-sively embedded into our everyday physical world. More-over, embedded web rvers [1, 3] can be ud to connect the physical world of nsors and actuators to the virtual world of information utilities and rvices. Conquently, a flurry of rearch activity has recently commenced in the nsor network domain, especially in wireless ad-hoc nsor networks. Although many of the nsor technologies are not new, there are certain physical laws governing the energy requirements of performing wireless communications that have limited the feasibility of such devices in the past. Som
e of the benefits of the newer, more capable nsor nodes are the ability to:
•Build large-scale networks;
坐地
•Implement sophisticated protocols;
•Reduce the amount of communication (wireless) re-quired to perform tasks by distributed and/or local pre-computations;
•Implement complex power saving modes of operation depending on the environment and the state of the network.
Due to the above-mentioned advances in nsor network technology, more and more practical applications of wire-less nsor networks continue to emerge. As an example, consider the millions of acres that are lost around the world, due to forest fires every year. In all fires, early warnings are critical in preventing small harmless brush fires from becoming monstrous infernos. By deploying specialized wireless nsor nodes in strategically lected high-risk areas, the detection time for such disasters can be drastically reduced, increasing the likelihood of success in early extinguishing efforts. Also, since the nodes are lf-configuring and do not need constant monitoring, the cost of such a deployment is minimal compared to the huge loss incurred in a large blaze.
In addition to the new applications, wireless nsor net-works provide a viable alternative to veral existing tech-nologies. For example, large buildings contain hundreds of environmental nsors that are wired to a central air condi-tioning and ventilation system. The significant wiring costs limit the complexity of current environmental controls and the reconfigurability of the systems. However, replacing the hard-wired monitoring units with ad-hoc wireless n-sor nodes can improve the quality and energy efficiency of the environmental system while allowing almost unlimited reconfiguration and customization in the future. In many instances, the savings in the wiring costs alone justify the u of the wireless nsor nodes.
B. Rearch Goal: Sensor Network Coverage
One of the fundamental issues that aris in nsor net-works, in addition to location calculation, tracking, and deployment, is coverage. Due to the large variety of n-sors and applications, coverage is subject to a wide range of interpretations. In general, coverage can be considered as the measure of quality of rvice of a nsor network. For example, in the previous fire detection nsor networks example, one may ask how well the network can obrve a given area and what the chances are that a fire starting in a specific location will be detected in a given time frame.
Furthermore, coverage formulations can try to find weak points in a nsor field and suggest future deployment or reconfiguration schemes for improving the overall quality of rvice.
In most nsor networks, two emingly contradictory, yet related viewpoints of coverage exist: worst and best ca coverage. In worst-ca coverage, attempts are made to quantify the quality of rvice by finding areas of lower obrvability from nsor nodes and detecting breach re-gions. In best-ca coverage, finding areas of high ob-rvability from nsors and identifying the best support and guidance regions are of primary concern. Our main objective is the design of robust, efficient and scalable al-gorithms to be ud in wireless multi-nsor integration. From the conceptual and algorithmic point of view, the main contribution is provably optimal polynomial time algorithm for coverage in nsor networks. We combine existing computational geometry techniques and constructs such as the Voronoi diagram, with graph theoretical algo-rithmic techniques. The u of Voronoi diagram, efficiently and without loss of optimality, transforms the continuous geometric problem into a discrete graph problem. Further-more, it enables direct application of arch techniques in the resulting graph reprentation. We also study asymp-totic coverage behavior of random wireless ad-hoc net-works.
C. Paper Organization
The reminder of the paper is organized as follows: In the next ction we summarize the related work. In ction III, we survey veral key technologies that are fundamental to our study of coverage. Section IV contains a brief overview of deterministic nsor deployment and coverage. In c-tion V, we prent a formal definition of the worst (breach) and best (support) coverage and propo optimal polyno-mial-time algorithms for solving each ca. Section VI con-tains a wide array of experimental results followed by a brief discussion of our future rearch directions and the conclusion.
II. R ELATED W ORK
The increasing trend in rearch efforts in the areas referred to as Smart Spaces or Pervasive Computing are directly related to many problems in nsor networks. Although many rearchers in the nsor network area have men-tioned the critical notion of coverage in the network, to our knowledge this is the first time that an algorithmic ap-proach combined with computational geometry constructs was adopted in ad-hoc nsor networks. Also, to our knowledge, [18] was the first to identify the importance of computational geometry and Voronoi Diagrams in nsor network coverage. Reference [11] describes a general sys-tematic method for developing an advanced nsor network for monitoring complex systems such as tho found in nuclear power plants but doe
s not prent any general cov-erage algorithms. The Art Gallery Problem [12] deals with determining the number of obrvers necessary to cover an art gallery room such that every point is en by at least one obrver. It has found veral applications in many domains such as the optimal antenna placement problems for wireless communication. The Art Gallery problem was solved optimally in 2D and was shown to be NP-hard in the 3D ca. Reference [12] propos heuristics for solving the 3D ca using Delaunay triangulation. Sensor coverage for detecting global ocean color where nsors obrve the distribution and abundance of oceanic phytoplankton [7] is approached by asmbling and merging data from satellites at different orbits.
消防作文300字Perhaps the most related works are the attempts on cover-age of an initially unknown environment for mobile robots [4, 6]. However, when the geometry of the environment is known in advance, coverage becomes a special ca of path planning [10]. Both of the problems are solved using generalized Voronoi diagrams.
Radar and sonar coverage also prent veral related chal-lenges. The radar and sonar netting optimization is of great importance in the networking technologies and the optimal distribution of detection and tracking in a surveillance area [15]. Bad on the measured radar cross ctions and the coverage diagrams for different radars, [16] propos a method for optimally locating the radars t
o achieve a satis-factory surveillance area with limited radar resources. Coverage studies to maintain connectivity have also been the focus of study. For example, [13] and [14] calculate the optimum number of ba stations required to achieve the system operator's rvice objectives. Previously, connec-tivity was achieved through mobile host attachments to a ba station. However, the connectivity coverage is more important in the ca of ad-hoc wireless networks since the connections are peer-to-peer. Reference [9] shows the im-provement in the network coverage due to the multi-hop routing features and optimizes the coverage constraint to the limited path length. Although our coverage study is aimed at ad-hoc wireless nsor networks, it is different from the above-mentioned class of problems due to our geometrical algorithmic approach.
III. P RELIMINARIES
A. Topology of the network and Sensor Model Generally, wireless nsor networks are targeted to the ex-tremes of miniaturization, availability, accuracy, reliability, and power savings. This requires a networked infrastruc-ture with small physical nodes, low power consumption, and low cost, that in turn limit communications to the im-mediate proximity of each node. There are veral existing models of nsor behavior each with varying degrees of complexity. However, most models share one thing in
common in that generally, nsing ability is directly de-pendant on distance. Conquently, in all our subquent discussions, we assume that nsor coverage decreas as distance from nsors increas.
B. Enabling Technologies: Sensor Location Tech-
nology and Algorithms
The idea of having a smarter environment has fostered a growing interest in location aware systems and rvices. Obtaining reliable location information is an enabling component to many other location-aware basic tasks in nsor networks such as coverage, tracking and mobility management. Here, geolocation with GPS (Global Posi-tioning System) is an unattractive solution due to cost, power, and accuracy constraints. Since our coverage algo-rithms rely on geolocation information, we have imple-mented the location procedure as the initial step before the coverage algorithm. In this geolocation approach [17], a few of the nsor nodes called beacons know their coordi-nates in advance, either from satellite information (GPS) or pre-deployment. The geolocation scheme then relies on signal strength information embedded in the inherent radio frequency communication capabilities of the nodes in ap-proximating neighbor distances. Each node that can hear from a mini
mum of three beacon neighbors can determine its own location by trilateration and become a beacon. It-erative trilaterations are then ud to locate as many nodes as possible.
wifi网络拒绝接入怎么解决We have also developed heuristics to compensate for the errors in the initial beacon locations and distance informa-tion. Initial analysis and percolation simulations show that in a reasonably den network, by having 1% or less of the nodes as initial beacons, almost all other nodes can locate themlves at the end of the location process. In our discus-sions of coverage algorithms, we only consider nodes that have valid location information.
动静之间>春成语C. Enabling Technology: Computational Geometry
Voronoi Diagram and Delaunay Triangulation The Voronoi diagram has been re-invented, ud, and stud-ied in many domains. According to [5] it is believed that the Voronoi diagram is a fundamental construct defined by a discrete t of points. In 2D, the Voronoi diagram of a t of discrete sites (points) partitions the plane into a t of convex polygons such that all points inside a polygon are clost to only one site. This construction effectively pro-duces polygons with edges that are equidistant from neighboring sites. Figure 1 shows an example of a Voronoi diagram for a t of randomly placed sites. Reference [5] prents a detailed survey of Voronoi diagrams and their applications.
Another structure that is directly related to Voronoi dia-grams is the Delaunay triangulation [8]. The Delaunay tri-angulation can be obtained by connecting the sites in the Voronoi diagram who polygons share a common edge. It has been shown that among all possible triangulations, the Delaunay triangulation maximizes the smallest angle in each triangle. Also, neighborhood information can be ex-tracted from the Delaunay triangulation since sites that are clo together are connected. In fact the Delaunay triangu-lation can be ud to find the two clost sites by consider-ing the shortest edge in the triangulation. We u the prop-erties of the Voronoi diagram and Delaunay triangulation to solve for best and worst ca coverages.
Figure 1 - Voronoi Diagram Of A Set Of Randomly
Placed Points In A Plane.
短发控D. Implementation: Centralized vs. Distributed
Multi-hop communication is one of the main enablers in reducing power consumption in ad-hoc nsor networks. The energy required for communication between two arbi-trary nodes A and B is strongly dependent on the distance d between the two nodes. More precily, y
d
B
E⋅
= where y>1 is the path loss exponent depending on the RF envi-ronment and B is a proportionality constant describing the overhead per bit. Given this super linear relationship be-tween energy and distance, generally using veral short intermediate hops to nd a bit is more energy efficient than using one longer hop.
However, an incorrect conclusion would be to u an infi-nite number of hops over the smallest possible distances. In reality, this is impractical for two reasons:
(i) The number of intermediate hops is limited
by the number of nodes between A and B;
(ii) The energy is not limited to the energy radi-ated through the antenna. There is also the
energy dissipated in the radio for receiving a
bit and readying a bit for retransmission.
For applications such as coverage calculations, the energy of computations per node is also a component of the energy metric. It is important to note that technology scaling will gradually reduce the processing costs, with the transmis-sion cost remaining constant. Using compression tech-niques, one can reduce the number of transmitted bits, thus reducing the cost of transmission at the expen of more computation. This communication-computation trade-off is the core idea behind low energy nsor networks. From this discussion it is apparent that a good algorithm designed for wireless nsor networks will require minimal amount of communication. This is in sharp contrast wi
th classical distributed systems [19] where the goal generally is maxi-mizing the speed of execution. This renders the classical distributed algorithm irrelevant for developing wireless nsor networks algorithms.
The most relevant metrics in wireless networks is power. Experimental measurements indicate that communication cost in wireless ad-hoc networks is at least two orders of magnitude higher than computation costs in terms of con-sumed power. Note that the coverage problem is intrinsi-cally global in the n that, lack of knowledge of location of any single node implies that the problem may not be solved correctly. Therefore, any algorithm which aims to provide correct solution must inherently u all location data.
IV. D ETERMINISTIC C OVERAGE
In order to achieve deterministic coverage, a static network must be deployed according to a predefined shape. The predefined locations of the nsors can be uniform in dif-ferent areas of the nsor field or can be weighted to com-pensate for the more critically monitored areas. An exam-ple of a uniform deterministic coverage is the grid-bad nsor deployment where nodes are located on the interc-tion points of a grid. In this ca, the problem of coverage of the nsor field reduces
to the problem of coverage of one cell and its neighborhood due to the symmetric and periodic deployment scheme.
An example of weighted predefined deployment is the -curity nsor systems ud in muums. The more valuable exhibit items are equipped with more nsors to maximize the coverage of the monitoring scheme. Another determi-nistic deployment scheme can be found in the 3D Art Gal-lery Problem heuristics solutions discusd in [12]. Our propod coverage algorithm can be ud in all predefined (deterministic) deployment schemes to determine the cov-erage in the nsor field.
V. S TOCHASTIC C OVERAGE
In many situations, deterministic deployment is neither feasible nor practical. Another deployment option is to cover the nsor field with nsors randomly distributed in the environment. The stochastic random distribution scheme can be uniform, Gaussian, Poisson or any other distribution bad on the application at hand. In the simula-tion studies for this paper, we have generally assumed uni-form nsor distribution, although our algorithm is applica-ble to any other deployment scheme of the nsor nodes.
A. Worst Ca Coverage- Maximal Breach Path
The breach-bad coverage discusd earlier can formally be stated as:
Given: A field A instrumented with nsors S where for each nsor s i∈S, the location (x i,y i) is known; areas I and F corresponding to initial (I) and final (F) locations of an agent.
Problem: Identify P B, the Maximal Breach Path in S, start-ing in I and ending in F.
P B in this ca is defined as a path through the field A, with end-points I and F and with the property that for any point p on the path P B, the distance from p to the clost nsor is maximized. The regions I and F are arbitrary regions de-termined by the task at hand and may be located anywhere inside or outside the nsor field.
Since by construction, the line gments of the Voronoi diagram maximize distance from the clost sites, the Maximal Breach Path P B, must lie on the line gments of the Voronoi diagram corresponding to the nsors in S. If any point p on the path P B deviates from Voronoi line g-ments, by definition, it must be clor to at least one nsor in S. Thus, the following three steps obtain the solution to this problem:
1) Generate Voronoi diagram for S;
2) Apply graph theory abstraction;
3) Find P B using Binary-Search and Breadth-First-
Search.
The lines at the boundaries of the Voronoi diagram extend to infinity. However, since here we are dealing with a finite area A, we must clip the Voronoi diagram to the boundaries of A. Since traveling along the bounds of the nsor field also constitutes a valid path, we introduce extra edges in the Voronoi diagram corresponding to the bounds of A. In subquent discussions, when we refer to the Voronoi dia-gram, we are actually referring to the bounded Voronoi diagram.
The first part of the algorithm detailed in Figure 2 gener-ates the Voronoi diagram corresponding to the nsors in S. The weighted, undirected graph G is constructed by creat-ing a node for each vertex and an edge corresponding to each line gment in the Voronoi diagram. Each edge in graph G is given a weight equal to its minimum distance from the clost nsor in S. The algorithm then performs a binary arch between the smallest and largest edge weights in G. In each step, breadth-first-arch is ud to check the existence of a path from I to F using only edges
with weights that are larger than the arch criteria called breach_weight. If a path exists, breach_weight is incread to further restrict the edges considered in the next arch iteration. If a path is not found, breach_weight is lowered to relax the constraint on the arch. Upon completion, the algorithm has found the Maximal Breach Path, which is the path from I to F with the highest possible weighted edges. Generate Bounded Voronoi diagram for S with vertex t U and line gment t L.
Initialize weighted undirected graph G(V,E)
FOR each vertex u i∈U
Create duplicate vertex v i in V
FOR each l i(u j,u k)∈L
Create edge e i(v j,v k) in E
Weight(e i)=min distance from nsor s i∈S for 1≤i≤|S|
min_weight = min edge weight in G
max_weight = max edge weight in G
range = (max_weight – min_weight) / 2
breach_weight = min_weight + range
WHILE (range > binary_arch_tolerance)
Initialize graph G’(V’,E’)
FOR each v i∈V
Create vertex v i’ in G’
FOR each e i∈E
IF Weight(e i)≥breach_weight
Inrt edge e i’ in G’
range = range / 2
IF BFS(G’,I,F) is Successful
breach_weight = breach_weight + range
ELSE
breach_weight = breach_weight – range家庭的英语单词
END IF
Figure 2 - Maximal Breach Path Algorithm
a股It must be noted that the Maximal Breach Path is not unique. In fact, in general, there are many paths that can qualify as the Maximal Breach Path. However, they all u edges with weights that are larger or equal to the breach_weight determined in the binary arch pha of the algorithm, with at least one edge that has a weight equal to breach_weight. The breach_weight found by the algorithm is the minimum distance from nsors that an agent travel-ing on any path through the field A (from I to F) must en-counter at least once. If new nsors can be deployed or existing nsors moved such that this breach_weight is decread, then the worst-ca coverage is improved.
B. Best Ca Coverage- Maximal Support Path Similar to the worst-ca (breach) coverage formulation, the best-ca (support) coverage can be stated as:
Given: A field A instrumented with nsors S where for each nsor s i∈S, the location (x i,y i) is known; areas I and F corresponding to initial (I) and final (F) locations of the agent. Problem: Identify P S, the path of maximal support in S, starting in I and ending in F.
P S in this ca is defined as a path through the field A, with end-points I and F, and with the property that for any point p on the path P S, the distance from p to the clost nsor is minimized.
Since the Delaunay triangulation produces triangles that have minimal edge lengths among all possible triangula-tions, P S must lie on the lines of the Delaunay triangulation of the nsors in S. Intuitively, if one tries to move in S while minimizing distance from nsors, one must attempt to travel along straight lines connecting nsor nodes. The algorithm for solving for P S is very similar to the breach algorithm in Figure 2 with the following exceptions:
(i) The Voronoi diagram is replaced by the De-
launay triangulation as the underlying geo-
metric structure;
(ii) The edges in graph G are assigned weights equal to the length of the corresponding line
gments in the Delaunay triangulation;
(iii) The arch parameter breach_weight is re-placed by the new parameter support_weight. In this ca, the maximal support path may also not be unique. However, the support_weight found in the binary arch pha of the algorithm is indicative of the best-ca coverage of the network. Here, support_weight is the maximum distance from the clost nsors that an agent traveling on any path through the field A (from I to F) must encounter at least once. If additional nsors can be de-ployed or existing nsors moved such that support_weight is decread, then the best-ca coverage is improved.
C. Complexity
The best known algorithms for the generation of the Vo-ronoi diagram have O(n log n) complexities. The conver-sion to graphs and weight assignments can be accom-plished in linear time and therefore do not add any signifi-cant overhead to the computation. In most cas, BFS (and DFS) ha
ve O(m) complexity where m is the number of edges in the graph. Since in realistic cas we deal with spar networks the actual complexity is O(n) while it could be as high as O(n2). Binary arch is accomplished in O(log range) where range is usually limited. So, while the worst ca complexity of the algorithm is O(n2 log n), in practice the networks are spar and the overall complexity is O(n log n), dominated by the Voronoi procedure which has large constant factor in its complexity.
