In the conclusion of a four part series, the authors of “Ad hoc wireless networks,” look at the remaining challenges in wireless sensor network design relating energy efficient hardware design, synchronization, transport layer protocols and real time communications.
The purpose of a sensor network is to monitor and report events or phenomena taking place in a particular area. Hence, the main parameters which define how well the network observes a given area are “coverage” and “exposure.”
In the conclusion of this series (see Part 1, Part 2 and Part 3,), we shall formally define the coverage and exposure problems, and briefly describe some mathematical techniques to solve them.
Coverage is a measure of how well the network can observe or cover an event. Coverage depends upon the range and sensitivity of the sensing nodes, and the location and density of the sensing nodes in the given region.
The worst-case coverage define s areas of breach, that is, where coverage is the poorest. This can be used to determine if additional sensors need to be deployed to improve the network. The best-case coverage, on the other hand, define s the areas of best coverage. A path along the areas of best coverage is called a maximum support path or maximum exposure path.
A mathematical technique to solve the coverage problem is the Voronoi diagram. It can be proved that the path PB will be composed of line segments that belong to the Voronoi diagram corresponding to the sensor graph.
In two dimensions, the Voronoi diagram of a set of sites is a partitioning of the plane into a set of convex polygons such that all points inside a polygon are closest to the site enclosed by the polygon, and the polygons have edges equidistant from the nearby sites. A Voronoi diagram for a sensor network, and a breach path from I to F,are shown in Figure 12.14 below.
on image to enlarge.
Figure 12.14. Voronoi diagram.
As shown in Figure 12.14 above, the algorithm to find the breach path PB is:
1) Generate the Voronoi diagram, with the set of vertices V and the set of edges E. This is done by drawing the perpendicular bisectors of every line segment joining two sites, and using their points of intersection as the vertices of the convex polygons.
2) Create a weighted graph with vertices from V and edges from E, such that the weight of each edge in the graph is the minimum distance from all sensors in S. The edge weights represent the distance from the nearest sensor. Smaller edge weights imply better coverage along the edge.
3) Determine the maximum cost path from I to F, using breadth-first search.
The maximum cost implies least coverage. Hence, the required breach path is along this maximum-cost path determined from the Voronoi diagram. The breach path shows the region of maximum vulnerability in a sensor network, where the coverage provided by the sensors is the weakest.
A related problem is that of finding the best-case coverage. The problem is formally stated as finding the path which offers the maximum coverage, that is, the maximum support path PS in S,from I to F .The solution is obtained by a mathematical technique called Delaunay triangulation, shown in Figure 12.15. below
on image to enlarge.
Figure 12.15. Delaunay triangulation.
This is obtained from the Voronoi diagram by connecting the sites whose polygons share a common edge. The best path PS will be a set of line segments from the Delaunay triangulation, connecting some of the sensor nodes.
The algorithm is again similar to that used to findthe maximum breach path, replacing the Voronoi diagram by the Delaunay triangulation, and defining the edge costs proportional to the line segment lengths. The maximum support path is hence formed by a set of line segments connecting some of the sensor nodes.
Exposure is defined as the expected ability of observing a target in the sensor field. It is formally define d as the integral of the sensing function on a path from source node Ps to destination node Pd. The sensing power of a node s at point p is usually modeled as
where γ and k are constants, and d(s,p)is the distance of p from s.Consider anetwork with sensors s1,s2,…,sn.The total intensity at point p,called the all-sensor field intensity, is given by
The closest-sensor field intensity at p is
where smin is the closest sensor to p. The exposure during travel of an event along apath p(t)is defined by the exposure function
where xx) is the elemental arc length, and t1,t2 are the time instances between which the path is traversed. For conversion from Cartesian coordinates (x(t),y(t)),
In the simplest case of having one sensor node at (0,0) in a unit field , the breach path or minimum exposure path (MEP) from (-1,-1) to (1,1) is shown in Figure 12.16 below.
Figure 12.16. Unit field minimum exposure path
The MEP consists of the line segment from vi to ui, part of the inscribed circle from ui to uj ,and the line segment from uj to vj . This is shown in Figure 12.17 below.
Figure 12.17. Polygon field minimum exposure path.
The exposure problem is still unsolved for two points in the same corner, or for points within the inscribed circle. For the generic exposure problem of determining the MEP for randomly placed sensor nodes in the network, the network is tessellated with grid points. An example is shown in Figure 12.18 below.
Figure 12.18. Generic minimum exposure path.
Within each square, all vertices are connected to obtain a grid. Higher order grids have greater accuracy. For each edge in the grid network, the exposure function is used to determine the edge weights, and the MEP is define d as the shortest path, determined by Dijkstra’s algorithm.
The mathematical concept of exposure is important for evaluating the target detection capability of a sensor network. Sensors are deployed in a given area to detect events occurring in the field of interest.
The nodes collaborate among themselves (perform data fusion) through the exchange of localized information, and reach a decision about the location and movement of a given event or target. In , Clouqueur et al. discuss a probabilistic protocol for target detection, where the observations made by individual sensors are collaborated, and the presence or movement of a target is probabilistically determined by data fusion, with allowance for noise in data recording. The network topology which gives a maximum exposure is also determined analytically.