Coverage and Connectivity

Abstract

A major advantage of wireless sensor networks (WSNs) over wired networks is the potential for ad hoc deployment of the network. If the monitoring of a dangerous environment is required, then one may not be able to deploy a wired network.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

A major advantage of wireless sensor networks (WSNs) over wired networks is the potential for ad hoc deployment of the network. If the monitoring of a dangerous environment is required, then one may not be able to deploy a wired network. However, a WSN may be deployed in even the most inhospitable of domains, and the sensor data can then be gathered and monitored from a remote location. A likely ad hoc deployment method for distributing the sensor nodes in such a hazardous terrain is to airdrop them over the region of interest. In a chemical monitoring application, for instance, wireless sensor nodes may be airdropped over an area which could be unsafe to manually deploy the nodes and then self-organize them into a network for this monitoring task.

The problem with this deployment method, as well as other random deployment methods often used with WSNs, is that one has no full control over where the nodes will be located. Consider, as an example, the application of battlefield surveillance in which a large number of sensor nodes, designed to detect and locate the presence of enemy snipers [30], are airdropped over the battlefield. Nodes may use acoustic sensing to detect gunshots fired by snipers and approximate the location of a shooter by aggregating the time of arrival (ToA) data from several sensors. Crucial to this application, as well as many others, is the often implicit assumption that the deployment of sensor nodes is complete such that any event occurring within the sensor field will be detected. However, due to the randomness of a deployment there is no guarantee of complete coverage, raising questions on how to verify the absence of holes in the sensor coverage within the region of interest, and how to locate such holes in coverage if they do exist.

The coverage of the area of interest is one of the Qualify of Service (QoS) metrics in WSNs [18] as it describes how well the sensing field is sensed or covered by the sensor nodes. A point in the region of interest is considered to be covered  if one or more sensors can measure the phenomena of interest at that point. If every point in the sensing field is covered by at least one sensor node, we say that the coverage is complete, and such coverage has degree of one. Sometimes specific applications require higher fault redundancy or sensor network measurement accuracy, resulting in higher degree of coverage where multiple sensor nodes cover point(s) in the sensing field.

Related to coverage is connectivity—another important characteristic of WSNs. As described later in the chapter, sensor networks can be modeled using graphs where nodes are equivalent to vertices and communication links are represented by corresponding edges. If the equivalent graph is connected then we consider the sensor network to be connected. The graph (or sensor network) is connected if there is an edge path (communication path) between any two vertices (nodes) in the graph (network). Otherwise, the graph (network) is disconnected and some nodes are not able to communicate with the rest of the network. Disconnected network nodes are basically useless for the network since the information on those nodes is not accessible by the network anymore. Similarly, as with the coverage in the sensor network, connectivity can have higher degrees that allows for more robust networks where removal or failure of some nodes does not cause the network to become disconnected.

Notions of coverage and connectivity are, in most practical applications, not independent of each other. Most applications have strict requirements for both of these network characteristics. It is often required to provide a certain level (quality) of coverage, while maintaining the network connectivity. This translates into constrained optimization problems, discussed later in the chapter, where type of coverage determines optimization cost function and connectivity relates to constraints. Similarly, it might be required to deploy a robust network that is fault-tolerant with a higher degree of connectivity, while the sensing area is still fully covered.

In this chapter, we review important notation and results related to sensor network coverage and connectivity and tools that are commonly used in modeling of sensor networks coverage and connectivity. We present basic graph notations that are used in WSN modeling including tools used in coverage modeling and provide few examples of optimal coverage under sensor network connectivity constraints.

5.1 Modeling Sensor Networks Using Graphs

In this section, we cover modeling of wireless sensor network using certain mathematical constructs known as graphs and simplicial complexes. This mapping of the sensor network allows users to perform mathematical and computational analysis of the network’s topology, to analyze network coverage and connectivity, and develop algorithms that deal with those issues. Such modeling is, in general, applicable to both networks with known coordinates and coordinate-free networks.

5.1.1 Communication Graphs

A graph, defined as $G = \left( {V,E} \right)$ describes a set V of vertices and a set E of edges that connect the vertices. In most cases in WSN applications, it is presumed that all communication links between sensor nodes are bidirectional. This means that if node A is within the communication range of node B, then the reverse is also true. For this reason, this discussion of graphs may be restricted to deal only with undirected simple graphs. A graph is called a simple graph if it does not contain multiple edges between pairs of vertices or self-loops, which connect a vertex to itself, and it is called undirected if all edges are bidirectional. For simplicity, the term graph is often used to refer to such graphs. Figure 5.1 illustrates the graph $G = \left( {V,E} \right)$ with vertex set $V = \left\{ {1,2,3,4} \right\}$, and edge set $E = \left\{ {12,13,14,24,34} \right\}$. Note also that the edge set for an undirected graph may consist of unordered pairs of vertices such that the edge 12 is equivalent to the edge 21.

Fig. 5.1

Example of a simple graph with four vertices and five edges

Here, we define terms such as vertex degrees and order of a graph [54] that are used in WSNs modeling.

Definition 5.1

The degree of vertex v in a graph G, d(v) is the number of edges incident to v. If the maximum degree in a graph is equal to the minimum degree in the graph, then the graph is called regular graph. The graph is called k-regular if the common degree is k.

For example, the degree of vertex 1 in the graph in Fig. 5.1 is 3, while the degree of vertex 3 is 2.

Definition 5.2

The order of a graph G, n(G), is the number of vertices in graph G. The size of a graph G, e(G), is the number of edges in graph G.

Definition 5.3

[54] A graph G is connected if it has a u, v-path whenever $u,v \in V(G)$; otherwise, G is disconnected. If graph G has a u, v-path, then vertex u is connected to vertex v in G.

Directed Graphs

Communication links in sensor networks does not need to be symmetric. If the node A can hear the node B, it does not necessary mean that the node A can hear the node B. This can happen due to several reasons including node failure, different energy levels at the node that force radio to operate at different power levels, etc. A model that represents such a network is called directed graph.

Definition 5.4

[54] A directed graph G is a triple consisting of a vertex set V(G), an edge set E(G), and a function that assigns to each edge an ordered pair of vertices. The first vertex of the ordered pair is the tail of the edge, and the second is the head.

An example of a directed graph is given in Fig. 5.2, where there is an edge from 3 to 1, from 3 to 2, and from 3 to 4. There is also an edge from 1 to 2, and from 4 to 2.

Fig. 5.2

Example of a directed graph

Definition 5.5

An adjacency matrix A(G) of a directed graph G is a matrix that at the position i, j has the number of edges from v _i to v _j .

For example, an adjacency matrix for the graph in Fig. 5.2 is given by

$$A(G) = \begin{array}{*{20}c} {} & {1\quad 2\quad 3\quad 4} \\ \begin{aligned} 1 \hfill \\ 2 \hfill \\ 3 \hfill \\ 4 \hfill \\ \end{aligned} & {\left( {\begin{array}{*{20}c} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ \end{array} } \right)} \\ \end{array} .$$

(5.1)

If the graph is weighted, then for each pair of vertices u, v, there is a assigned weight $a_{uv}$, [34]. We consider a graph with weights that are real, satisfying $a_{uv} = a_{vu}$, $a_{uv} \ne 0$ if and only if u and v are adjacent vertices, and $a_{uv} \ge 0$. In case of weighted graphs, the adjacency matrix is $A(G) = \left[ {a_{uv} } \right]_{u,v \in V(G)}$ and the degree of a vertex v is equal to a sum of all weights that are adjoining to the vertex v, i.e., $d(v) = \sum_{u} {a_{uv} }$.

Definition 5.6

A complement of a graph G is a graph $\bar{G}$ that has the same set of vertices and a complement set of edges, i.e., there is an edge between any two vertices in $\bar{G}$ if there is no edge between the same vertices in G.

Note that together, a graph G and its complement $\bar{G}$ form a complete graph with all possible edges, see Fig. 5.3.

Fig. 5.3

A graph G, its compliment $\bar{G}$ and a complete graph $G + \bar{G} = K_{n}$

WSNs are commonly mapped to corresponding graphs that represent connectivity of the nodes and can be used to solve certain problems. The set of sensor nodes N in the network becomes the set of vertices in the graph. Two nodes are then connected with a graph edge if there is a direct communication link between them. By direct communication link, we mean only those nodes that can communicate directly without multi-hopping. This is illustrated in Fig. 5.4 below where a sensor network is represented as a graph.

Fig. 5.4

Mapping a sensor network to a graph

Assuming that communication range between sensor nodes is r _c and that the communication model is binary (when inside the communication range nodes can communicate, outside the range they cannot), then any two nodes whose Euclidean distance is less than r _c have a corresponding graph edge in the equivalent communication graph. Equivalently, if two nodes lie in each other’s communication disk, then there is an edge between them. Therefore, the sensor network is modeled using a specific type of graph known as a unit disk graph, which admits a graph edge between two vertices if their Euclidean distance is less than a fixed threshold. For communication networks, this graph is commonly referred to as the communication graph of the network. An example of a communication graph for a simple network is given in Fig. 5.5. The disks around each node represent the communication range r _c of the nodes.

Fig. 5.5

A sensor network and its communication graph—a unit disk graph

5.2 Coverage

One of the fundamental problems in the field of WSNs is the coverage. Coverage is an important indicator of the Quality of Service (QoS) in a sensor network [33]. The coverage problem can be approached in a number of ways due to the broad range of possible sensor network applications, but the central goal is to determine how well a set of sensor nodes monitors a given area.

The sensor coverage problem is closely related to the art gallery problem [37], a well-known visibility problem from computational geometry. The objective of this problem, which was originally proposed in August 1973 by mathematician Victor Klee, is to determine a minimum number of observers needed for surveillance of an art gallery such that every point can be seen by at least one observer.

This problem is illustrated in Fig. 5.6. Note that for any convex region, such as that to the left, only one observer is required. For the region to the right, two observers are needed to monitor the entire area since one observer to the lower left corner cannot see the portion at the top right.

Fig. 5.6

The art gallery problem example

This problem is shown to be NP-hard in [31]. Reference [7] proves that $\left\lfloor {n/3} \right\rfloor$ observers are always sufficient and the solution is sometimes optimal in 2D space, where n is the number of sides in the polygonal region being monitored, and the floor function $\left\lfloor x \right\rfloor$ is defined as the largest integer not greater than x (for example, $\left\lfloor {3.2} \right\rfloor = 3$, $\left\lfloor { - 3.2} \right\rfloor = - 4$). This result is commonly referred to as Chvatal’s art gallery theorem. A linear-time algorithm for locating these $\left\lfloor {n/3} \right\rfloor$ observers is given in [27]. An approximation algorithm for the 3D case is proposed in [32] which is within $O({ \log }\,n)$ of the optimal solution.

In [16], coverage is classified into three main categories: blanket coverage, barrier coverage, and sweep coverage. The goal of blanket coverage, as name suggests, is to maximize the coverage of area of interest. This is the common objective for a majority of WSN monitoring applications. Barrier coverage attempts to minimize the probability of an intruder penetrating the barrier and is important security feature in WSN applications. An example of barrier coverage is border patrol, where a nation attempts to keep people from crossing its borders illegally [3, 29]. Finally, sweep coverage is the equivalent of a barrier moving across the area of interest where a set of sensors sweeps specific area. This incorporates aspects of both blanket coverage and barrier coverage. These three types of coverage are shown below in Figs. 5.7, 5.8, and 5.9, respectively.

Fig. 5.7

Blanket coverage

Fig. 5.8

Barrier coverage

Fig. 5.9

Sweep coverage

A further issue to consider with coverage problems is point coverage versus area coverage. Either the sensor nodes can focus coverage on certain areas or targets, referred to as point coverage, or they can be spread out in an attempt to cover an entire area, referred to as area coverage. Typically, in most common WSN applications, area coverage is used. However, there are some situations, such as in tracking applications, where point coverage may be more appropriate.

The topic of sensing coverage is often approached by studying how to position the sensors such that the area of interest is sufficiently monitored. A non-complete coverage in WSNs (coverage with holes) allows for intrusion into the system and presents a security issue where a WSN needs to deal with intrusion detection in some other way [2, 42]. Several authors have considered the problem of optimally positioning sensor such that a region is maximally covered [6, 23, 26, 58]. The central idea is to spread out the nodes as much as possible to improve sensing coverage over a region of interest. Other results have focused on finding a minimal number of sensors needed to monitor an area [1, 38]. This approach is especially useful in an over-deployed network where one can find a minimal subset of the sensors that will maintain the desired level of coverage and power off all other nodes to reduce power consumption [47, 48, 52, 57].

5.2.1 Coverage Holes

The problem of locating coverage holes in a coordinate-free network has been studied in [13–15]. A strictly graph theoretic approach is used to locate nodes on the boundary of holes; however, no clear definition is given of what constitutes a hole for the proposed method. Additionally, [14] provides a graph theoretic method for using only local connectivity information (i.e., no coordinates) to develop a rough sketch of the layout of the network. The relationship between sensing coverage and node connectivity in sensor networks is given in [57]. This fundamental result states that if the communication range of the sensor nodes is at least twice the sensing range then complete sensing coverage of a convex region implies connectivity of the network. A generalization of this result to higher degrees of coverage, often referred to as k-coverage, is presented in [52]. A sensor field is called k-covered if every point is covered by at least k sensors. Under the same assumption, that the communication range be at least twice the sensing range, k-coverage implies k-connectivity.

Local connectivity information, without any positioning information, was used in [19, 40, 45] to determine if a region is covered or not [23]. Mathematical models of homology [45] were used to determine the coverage. A further extension of this work [19] shows how to detect the boundary of a hole in the network. This method only works for sensor networks that have a single hole and for networks having multiple holes it likely will not identify all holes. Furthermore, there is no guarantee that the algorithm will exactly locate even single holes. These references present a method of determining coverage without knowing the positions of the sensors. The major limitation is that there must be a certain ratio between the sensing range and the communication range of the sensor nodes or connectivity information alone is not enough to imply sensing coverage.

Whereas much study has been focused on how to improve coverage in sensor networks, research in [25] seeks to identify any holes in coverage that may be present in the existing sensor network deployment. Only after verifying that coverage is not sufficient would attempts be made to improve coverage or patch holes.

If the area of interest is not completely covered, it is called coverage holes, or simply holes. It is in these holes that an event may go undetected. Figure 5.10 gives an example of a sensor network with fully 1-covered sensor field and a sensor network with a coverage hole.

Fig. 5.10

Fully covered (1-covered) sensor field (left) and deployment with a coverage hole (right)

After determining the existence of holes it is also desirable to locate the holes so that, if necessary, they can be patched. Detecting the location of holes may be useful for other reasons as well. The presence of a hole may indicate a feature of the terrain, such as a lake, or some other phenomenon, such as a fire, which cannot be patched by the simple deployment of additional sensors. Also, messages are more likely to be routed through nodes on hole boundaries, depleting their available battery power more quickly, which could finally enlarge the hole [56] and degrade the network performance.

Assuming a simple, omnidirectional sensing model, each sensor node has a certain sensing range r _s and a transmission, or communication, range r _c.

In real-life applications, sensing and communication models are not always omnidirectional. Such models also heavily depend on environmental conditions.

Example 5.1

The IRIS sensor nodes are equipped with omnidirectional antennas capable of transmitting signal up to 500 m. That capability is produced in environments where there are no obstructions and the EM signal is allowed to propagate without interference. In the case of an urban environment, the sensing range would be considerably less; moreover, other factors such as multipath signal reflections, shadowing, and path loss due to non-free space propagation also affect the accuracy of the model. The received signal strength gradually decreases with the distance from the transmitter. The received signal strength is inversely proportional to the square of the distance between the transmitting and receiving antennas. Mathematically, it can be written as

$$\frac{{P_{r} }}{{P_{t} }} = \left[ {\frac{{\sqrt {G_{l} \lambda } }}{4\pi d}} \right]^{2} ,$$

(5.2)

where, P _r is the received power, P _t is the transmitted power, λ is the wavelength of the signal, d is the distance between receiver and transmitter, and G _l is the product of the transmit and receive antenna field radiation pattern. Because the antennas on the nodes are omnidirectional, the factor G _l is equal to 1.

Consider a set $S \subset \Re^{2}$ that represents a sensing area of interest. A network of N equal sensor nodes is deployed over S with sensor locations at $\left( {x_{i} ,y_{i} ,z_{i} } \right)$. A sensing function is given by $p_{i} (q)$ where p _i is the probability that the event $q \in S$ will be detected. Such probability represents the sensing model and in its simplest form the probability can take the form of a uniform probability density function [20]

$$p_{i} (q) = \left\{ {\begin{array}{*{20}l} {1,} \hfill & {d_{i} \le r_{s} } \hfill \\ {0,} \hfill & {d_{i} > r_{s} } \hfill \\ \end{array} } \right.$$

(5.3)

or

$$p_{i} (q) = \left\{ {\begin{array}{*{20}l} {P_{t} \left[ {\frac{{\sqrt {G_{l} \lambda } }}{{4\pi d_{i} }}} \right]^{2} ,} \hfill & {d_{i} \le r_{s} } \hfill \\ {0,} \hfill & {d_{i} > r_{s} } \hfill \\ \end{array} } \right.$$

(5.4)

where r _s is the sensing radius of the omnidirectional antenna and $d_{i}$ is a distance between the location of a sensor node i and specific sensing point in the field q, i.e.,

$$d_{i} = \left\| {\left( {x_{i} ,y_{i} ,z_{i} } \right) - q} \right\|.$$

(5.5)

In case of a uniform sensing probability function, the radius r _s around each node is referred to as its sensing disk, see Fig. 5.11. It is within this disk that the sensor will detect the desired phenomenon with probability of one. This is sometimes referred to as a binary sensing model since an event is either detected or it is not detected. Probabilistic models are also discussed in the literature [21, 58] and may be more realistic than binary sensing model. The same is true for communication models that affect connectivity of WSNs. However, when coverage and connectivity are discussed, usually the simplest binary models are considered (sensors can either sense or not, nodes can either communicate with other nodes or not).

Fig. 5.11

Sensing and communication range of a sensor node

5.3 Connectivity

Deployment of wireless sensor networks requires minimization of cost, reduction in computation and communication, high-degree of sensing area coverage, while maintaining a connected network. If the network is not connected, information cannot flow from deployed sensors towards the network gateway or a base station. If a network is modeled as a graph, then network connectivity is equivalent to graph connectivity, i.e., there exists a path between any two vertices (nodes) in the graph. Equivalently to the degree of coverage, there is a degree of network connectivity where k-connectivity means that removing any k − 1 nodes still leaves the graph connected. Several deployment algorithms that optimize some aspect of coverage, while maintaining network connectivity, are given in [18]. Potential field algorithm provides sensor nodes mobility where coverage can be maximized, while the network is still connected [39]. Decentralized estimation and control of graph connectivity for WSNs with mobile nodes is given in [55].

The concept of potential field is an artificially created field where static and mobile nodes are subject to specifically designed forces. Since the goal is to maximize the coverage while maintain the connectivity, two forces were suggested in [39]: F ^R—a repulsive force that move mobile sensor nodes away from each other to maximize the coverage; and F ^A—an attractive force that pulls nodes towards each other to stay connected. Both forces are inversely proportional to the square of the distance between node pairs and are given by

$$\begin{aligned} F^{R} (i,j) & = \frac{{ - K_{r} }}{{\left( {{\text{dist}}\left[ {(x_{i} ,y_{i} ),(x_{j} ,y_{j} )} \right]} \right)^{2} }}\frac{{(x_{i} ,y_{i} ) - (x_{j} ,y_{j} )}}{{{\text{dist}}\left[ {(x_{i} ,y_{i} ),(x_{j} ,y_{j} )} \right]}} \\ F^{A} (i,j) & = \left\{ {\begin{array}{*{20}l} {\frac{{ - K_{a} }}{{\left( {{\text{dist}}\left[ {(x_{i} ,y_{i} ),(x_{j} ,y_{j} )} \right] - R_{c} } \right)^{2} }}\frac{{(x_{i} ,y_{i} ) - (x_{j} ,y_{j} )}}{{{\text{dist}}\left[ {(x_{i} ,y_{i} ),(x_{j} ,y_{j} )} \right]}},{\text{for}}\;{\text{critical}}\;{\text{connect}}.} \hfill \\ {0,\quad {\text{otherwise}}} \hfill \\ \end{array} } \right. \\ \end{aligned}$$

(5.6)

where $(x_{i} ,y_{i} )$ is an x,y location of a sensor node i, and $K_{r}$ and $K_{a}$ are design constants. Nodes are initially positioned at one place, and then start repelling from each other. When they are only k-connected neighbors left for a single node (critical connection), the attractive force starts pulling sensor nodes, thus preventing further reduction in sensor nodes connectivity. The nodes reach equilibrium state when sum of all forces acting on a node is equal to zero. The method provides an elegant, distributed solution for deployment of mobile sensor nodes under k-connectivity constraints.

Distributed algorithm that applies virtual forces is presented in [22]. Such algorithm maximizes the coverage and maintains uniform distribution of sensor nodes. The method assumes that nodes have information about their coordinates. The virtual force is proportional to the distance between sensor nodes and expected density of sensor nodes in the sensing field. The force is given by

$$F(i,j) = \frac{\mu (i)}{{\mu^{2} (R_{c} )}}\left( {R_{c} - {\text{dist}}\left[ {(x_{i} ,y_{i} ),(x_{j} ,y_{j} )} \right]} \right)\frac{{(x_{i} ,y_{i} ) - (x_{j} ,y_{j} )}}{{{\text{dist}}\left[ {(x_{i} ,y_{i} ),(x_{j} ,y_{j} )} \right]}},$$

(5.7)

where $\mu (i)$ is the local node density the at sensor node i, and the expected density $\mu (R_{c} )$. The expected density  depends on communication radius and is given by

$$\mu (R_{c} ) = \frac{{N\pi R_{c}^{2} }}{A},$$

(5.8)

with N being the number of sensor nodes, R _c communication radius, and A the sensing area. The algorithm provides movement of the nodes based on virtual forces and finishes when there are no new movements of nodes.

A centralized approach using virtual forces is given in [58, 60]. Each sensor has three virtual forces that act upon the node: repulsive force from the obstacles, attractive force from the sensing areas of high interest, and forces from other nodes. The specific forces from other nodes can either be repulsive or attractive, depending on their mutual distance and design parameters. The force applied to each sensor node is given by

$$F_{i} = \sum\limits_{{j \in N_{i} }} {F_{ij} + F_{i}^{R} + F_{i}^{A} } ,$$

(5.9)

where $F_{ij}$ is the force (repulsive or attractive) from node j to node i, $F_{i}^{R}$ is the repulsive force applied to the node, and $F_{i}^{A}$ is the attractive force applied to the node. The force $F_{ij}$ is given by

$$F_{ij} = \left\{ {\begin{array}{*{20}l} {w_{A} \left( {{\text{dist}}\left[ {(x_{i} ,y_{i} ),(x_{j} ,y_{j} )} \right] - d_{th} } \right)\angle i\vec{j},\quad {\text{if}}\,{\text{dist}}\left[ {(x_{i} ,y_{i} ),(x_{j} ,y_{j} )} \right] > d_{th} } \hfill \\ {0,\quad {\text{if}}\,{\text{dist}}\left[ {(x_{i} ,y_{i} ),(x_{j} ,y_{j} )} \right] = d_{th} } \hfill \\ {\frac{{w_{B} }}{{{\text{dist}}\left[ {(x_{i} ,y_{i} ),(x_{j} ,y_{j} )} \right]}}\angle i\vec{j} + \pi ,\quad {\text{if}}\,{\text{dist}}\left[ {(x_{i} ,y_{i} ),(x_{j} ,y_{j} )} \right] < d_{th} } \hfill \\ \end{array} } \right.,$$

(5.10)

where $i\vec{j}$ is the vector from node i to node j, $d_{th}$ is the threshold value for the mutual distance between nodes, and $w_{A}$ and $w_{B}$ are the constants determining amplitude of the forces. The method provides centralized deployment algorithm with controlled connectivity of the network. The sign of the force changes when distance between nodes crosses $d_{th}$ threshold, allowing for controlled connectivity of the network. The computational complexity of the virtual force algorithm is $O(nmk)$ for a network of n nodes deployed on the $m \times k$ grid.

5.3.1 Graph Laplacian

The Laplacian matrix of a network communication graph is of fundamental importance in network connectivity, network diameter, mean distance, number of connected components of a graph and numerous other applications, [34]. We review a standard graph theory terminology that includes adjacency matrix and the Laplacian matrix of graphs. In Sect. 5.1.1 we defined an adjacency matrix A(G) of a directional graph G as a matrix that at the position i, j has the number of edges from v _i to v _j . We also introduced a degree of a vertex v _i .

Let D(G) be a diagonal matrix indexed by a vertex set V(G), $D(G) = {\text{diag}}\left\{ {d(v_{1} ),d(v_{2} ), \ldots ,d(v_{n} )} \right\}$. The Laplacian matrix of a graph G is defined as

$$Q(G) = D(G) - A(G).$$

(5.11)

The Laplacian matrix is also called Kirchhoff matrix or admittance matrix and it finds its application in electrical networks. The Laplacian matrix is positive semi-definite and symmetric matrix with the additional property that all rows sum to zero (show this property as an exercise). The characteristic polynomial of Q(G) is given by

$$\mu (G,\lambda ) = { \det }\left( {\lambda I - Q} \right),$$

(5.12)

where I is the identity matrix of same dimensions at Q. The characteristic polynomial roots are the Laplacian eigenvalues $\lambda_{1} \le \lambda_{2} \le \cdots \le \lambda_{n}$ where n is the order of G.

Example 5.2

Consider two graphs shown in Fig. 5.12.

Fig. 5.12

Connected (left) and disconnected (right) graph

The adjacency matrix A ₁ (for the graph on the left) and matrix A ₂ (for the graph on the right) are given by

$$A_{1} = \left[ {\begin{array}{*{20}c} 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \\ \end{array} } \right] ,A_{2} = \left[ {\begin{array}{*{20}c} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ \end{array} } \right].$$

(5.13)

Corresponding Laplacian matrices are:

$$\begin{aligned} Q_{1} & = \left[ {\begin{array}{*{20}c} 3 & 0 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 4 & 0 \\ 0 & 0 & 0 & 0 & 2 \\ \end{array} } \right] - \left[ {\begin{array}{*{20}c} 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \\ \end{array} } \right] \\ & = \left[ {\begin{array}{*{20}c} 3 & { - 1} & { - 1} & { - 1} & 0 \\ { - 1} & 2 & 0 & { - 1} & 0 \\ { - 1} & 0 & 3 & { - 1} & { - 1} \\ { - 1} & { - 1} & { - 1} & 4 & { - 1} \\ 0 & 0 & { - 1} & { - 1} & 2 \\ \end{array} } \right] \\ \end{aligned}$$

(5.14)

$$\begin{aligned} Q_{2} & = \left[ {\begin{array}{*{20}c} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} } \right] - \left[ {\begin{array}{*{20}c} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ \end{array} } \right] \\ & = \left[ {\begin{array}{*{20}c} 1 & 0 & { - 1} & 0 & 0 \\ 0 & 1 & 0 & { - 1} & 0 \\ { - 1} & 0 & 2 & 0 & { - 1} \\ 0 & { - 1} & 0 & 1 & 0 \\ 0 & 0 & { - 1} & 0 & 1 \\ \end{array} } \right] \\ \end{aligned}$$

(5.15)

and corresponding Laplacian eigenvalues are:

$$\mu (G_{1} ):0,1.58,3,4.41,5$$

(5.16)

$$\mu (G_{2} ):0,0,1,2,3.$$

(5.17)

Note that the graph G ₂ is disconnected and has two components, and its first two eigenvalues are equal to zero. The following theorem [34] relates spectrum of the Laplacian graph matrix and graph connectivity.

Theorem 5.1

Let G be a weighted graph with all weights nonnegative. Then:

• (a) Q(G) has only real eigenvalues,

• (b) Q(G) is positive semi-definite,

• (c) Its smallest eigenvalue is $\lambda_{1} = 0$ and a corresponding eigenvector is $\left[ {1,1, \ldots ,1} \right]^{T}$. The multiplicity of 0 as an eigenvalue of Q(G) is equal to the number of components of graph G.

From Theorem 5.1, it follows that $\lambda_{1} = 0$, $\lambda_{2} > 0$ if and only if the graph G is connected. Therefore, the eigenvalues of the graph Laplacian serves as a measure of graph connectivity. The number $\lambda_{2} (G)$ is also called algebraic connectivity of the graph G as it directly relates to its connectivity [12]. If $\lambda_{2} = 0$ then the graph (network) is disconnected. If $\lambda_{2} > 0$, the graph (network) is connected, with the second eigenvalue $\lambda_{2}$ being a measure of the graph (network) connectivity. The following Theorem [34] lists few useful bounds on Laplacian eigenvalues.

Theorem 5.2

Let G(V, E) be a graph of order n. The following bounds are valid:

• (a) $\lambda_{2} \le \frac{n}{n - 1}{ \hbox{min} }\left\{ {d(v)} \right\}$

• (b) $\lambda_{n} \le { \hbox{max} }\left\{ {d(u) + d(v)} \right\}$ where $uv \in E(G)$

• (c) $\sum_{i = 1}^{n} {\lambda_{i} = 2\left| {E(G)} \right| = \sum\limits_{v} {d(v)} }$

• (d) $\lambda_{n} \ge \frac{n}{n - 1}{ \hbox{max} }\left\{ {d(v)} \right\}$.

The following result describes behavior of eigenvalues when additional edges are inserted in the communication graph [34]. This corresponds to a scenario when nodes move closer to each other, thus increasing their connectivity.

Theorem 5.3

The eigenvalues of graph G and $G^{{\prime }} = G + e$ satisfy

$$0 = \lambda_{1} (G) = \lambda_{1} (G^{{\prime }} ) \le \lambda_{2} (G) \le \lambda_{2} (G^{{\prime }} ) \le \cdots \le \lambda_{n} (G) \le \lambda_{n} (G^{{\prime }} ).$$

(5.18)

The number of spanning trees is also related to the spectrum of Laplacian. Let $\kappa (G)$ be the number of spanning trees of the graph G of order n. The number of spanning trees is related to eigenvalues by

$$\kappa (G) = \frac{1}{n}\lambda_{2} (G)\lambda_{3} (G) \ldots \lambda_{n} (G).$$

(5.19)

The second eigenvalue of a graph Laplacian is closely related to the graph diameter (the longest shortest path between any two graph vertices, i.e., the largest number of vertices that must be traversed to travel from one vertex to another), which relates to the sensor network coverage area. The upper and lower bounds on graph diameter are given by [34]

$$\frac{4}{{n\lambda_{2} (G)}} \le {\text{diam}}(G) \le 2\left\lceil {\frac{{\Delta + \lambda_{2} (G)}}{{4\lambda_{2} (G)}}ln(n - 1)} \right\rceil ,$$

(5.20)

where $\Delta$ is the maximum degree in graph G, $\Delta = { \hbox{max} }\left\{ {d(v)} \right\}$.

Applications of Laplacian eigenvalue-based analysis include mobile sensor networks, robotics swarms, cooperative control, consensus networks, and others. Most applications utilize the fact that the measure of network connectivity is the second smallest eigenvalue of the Laplacian matrix of the graph. For instance, in [43], a decentralized connectivity maintenance control strategy for mobile robotic systems/networks is considered, i.e., a group of N agents with single-integrator dynamics

$$\dot{p}_{i} = u_{i} ,$$

(5.21)

where $p_{i}$ and $u_{i}$ are position and control input, respectively, for the i-th agent. In [53], the connectivity maintenance control algorithm is given by

$$u_{i} = \frac{{\partial \lambda_{2} }}{{\partial p_{i} }}.$$

(5.22)

To improve the system stability from the connectivity point of view, it is proposed in [43] a modified control algorithm where control signal increases as the algebraic connectivity of the graph decreases (graph becomes “less connected”). The modified controls algorithms is given by

$$u_{i} = {\text{csch}}^{2} (\lambda_{2} - \varepsilon )\frac{{\partial \lambda_{2} }}{{\partial p_{i} }},$$

(5.23)

where ${\text{csch}}$ is the standard hyperbolic cosecant function and $\varepsilon$ is the desired lower-bound for the value of $\lambda_{2}$. This approach allows the control signal to increases when connectivity in the network is reduced.

5.4 Coverage Models Using Voronoi Diagrams

In Chap. 2 we provided an overview of Voronoi diagrams. Voronoi diagrams can be used for studying WSN deployment, coverage control, and hole patching. A vector-based algorithm was proposed in [51] where sensors move from densely covered areas to sparsely covered areas. Sensors act on each other with repulsive force. The virtual force from neighboring sensors will move the sensor such that the mutual distance is close to average distance between nodes. During each movement, each sensor calculates future coverage within its Voronoi cell. If the future movement will not improve the coverage, the sensor will not move to the target location and will instead move to the midpoint position between its target location and new location. Voronoi cell also has repulsive forces from the cell boundary, thus pushing the sensor node toward the inside of the region.

Voronoi-based algorithm moves sensor nodes towards the maximum coverage. It is a greedy algorithm where each sensor checks for holes within its Voronoi cell. If the hole is detected, the node moves towards its farthest vertex in the Voronoi cell. The distance between the farthest Voronoi vertex and its new location is equal to the sensing range with a maximum moving distance of the node being equal to the half of the communication range.

A combination of mobile and static nodes offers reduced cost while networks still has flexibility of mobile networks. Voronoi diagrams can be used for a hole detection in such networks [50]. Static nodes map their Voronoi diagrams and calculate coverage holes within their Voronoi cells. Static nodes then start the bidding process in which a mobile node will move to patch the hole. If there is a hole, a static sensor chooses the Voronoi vertex that is the farthest from the sensor and calculates related bid. The bid is given by

$$B_{i} = \pi (d - r_{s} )^{2} ,$$

(5.24)

where d is the distance between the sensor node and the Voronoi vertex, and r _s is the sensing range. Mobile nodes also have their own base price. The static node finds the mobile node whose base price is lower than its bid. The mobile node receives all bids from its neighbors, and based on the highest bid moves to heal the coverage hole. Once the mobile node accepts the bid, it updates its base price with that specific bid. This bidding-price model guarantees that the total size of holes will decrease over time, meaning no mobile node will patch the one hole, and create larger one at the same time.

5.5 Simplicial Complexes

A k-simplex is defined as the convex hull of a set of k + 1 points in $\Re^{n}$. More intuitively, a k-simplex is simply an unordered (k + 1)-tuple of points. For example, a 0-simplex ($\sigma_{0}$) is defined as a single point and a 1-simplex ($\sigma_{1}$) is defined as an unordered pair of points. These are identical to vertices and edges in graph theoretic terminology. A 2-simplex ($\sigma_{2}$), comprised a triple of points is informally a triangle that is “filled in” so that it is not hollow inside. A 3-simplex ($\sigma_{3}$), also called a tetrahedron, is defined by a set of four points, and is again, solid inside. In general, any k-simplex has a solid interior, though it is difficult to visualize this in higher dimensions. Examples of the first several k-simplices are illustrated in Fig. 5.13 [40].

Fig. 5.13

Examples of a 0-simplex, a 1-simplex, a 2-simplex, and a 3-simplex

This concept of k-simplices may also be extended to include collections of attached simplices, which are known as simplicial complexes. A simplicial complex K is a finite collection of simplices that satisfies the following two conditions:

• 1. For any simplex $\sigma_{i} \in K$, each face of $\sigma_{i}$ is also in K;

• 2. Two k-simplices $\sigma_{1} ,\sigma_{2} \in K$ must intersect at a common face.

While (a)–(c) in Fig. 5.14 are collections of k-simplices; it is clear from the definition that (c) is not a simplicial complex because it violates condition 2.

Fig. 5.14

Examples of simplicial complexes (a, b) and a non-simplicial complex (c)

It is evident from the above discussion that there is a strong similarity between graphs and simplicial complexes. In fact, a simplicial complex is in a sense just the generalization of a graph to higher dimensions. If we define the r-skeleton of the simplicial complex K as the collection of all k-simplices of K for which k ≤ r, then it is clear that the 1-skeleton of K is a graph, also called the underlying graph of K, since it is simply a set of vertices and edges.

5.5.1 From WSNs to Simplicial Complexes

We introduce here two important simplicial complexes and their respective planar counterparts and show how each may be used to model a WSN [40]. The sensor network is mapped to one of these simplicial complexes which correspond to sensing coverage. Then, the simplicial complex can be analyzed to find the number and location of holes, which relate to holes in the actual sensor network. Such simplicial complexes can model the coverage of the sensor networks and related quality of service in terms of coverage completeness.

Čech Complex

The Čech complex, also known as the nerve complex [4], can be defined for a set of points X with a parameter $r > 0$. The points x ₀, x ₁, …, x _n are defined as 0-simplices. The 1-simplex $\left[ {x_{0} x_{1} } \right]$ is defined if the r-balls centered at x ₀ and x ₁ intersect. If the r-balls centered at x ₀, x ₁, and x ₂ have a common intersection, then the 2-simplex $\left[ {x_{0} x_{1} x_{2} } \right]$ exists in the Čech complex. In general, the k-simplex $\left[ {x_{0} x_{1} x_{2} \ldots x_{k} } \right]$ exists if and only if the r-balls centered at x ₀, x ₁, …, x _k have a nonempty common intersection.

It is obvious that this construction fits well for modeling coverage in a WSN. To observe this, one only needs to consider that r from the above construction equals the sensing radius r _s . For example, when three sensing disks have a common intersection we add a 2-simplex to the Čech complex which signifies that the entire area inside the polygon (i.e., triangle) formed by these three sensor nodes is covered. The inclusion of higher dimensional simplices indicates higher degrees of coverage. Figure 5.15 illustrates the construction of simplices from the union of coverage disks. In (a), a 1-simplex is constructed since the disks have a common intersection. The disks in (b) do not have a common intersection and the corresponding triangle is not filled, while the disks in (c) do have a common intersection and the corresponding filled triangle is constructed (2-simplex) [40].

Fig. 5.15

Constructing the Čech complex from the union of sensing disks

An important benefit of this simplicial complex is that it can be computed even if the nodes have different sensing ranges, as long as the sensing model is a circle around the node. For theoretical analysis purposes it is usually assumed that all nodes have identical sensing ranges, but do note that this assumption is, in general, not required. However, a potential disadvantage of this simplicial complex construction is that precise distances between nodes must be known. If these distances are not precisely known this could lead to errors in the constructed Čech complex.

Rips Complex [40]

The Rips complex, sometimes also called the Vietoris complex, was originally introduced by Vietoris in 1927 [49]. Given the point set X with a diameter r, the Rips complex is defined as follows. The k-simplex $\left[ {x_{0} x_{1} x_{2} \ldots x_{k} } \right]$ is defined in the Rips complex if the pairwise distance between each of x ₀, x ₁, x ₂, …, x _k is less than r. For example, when the distance between two points x ₀ and x ₁ is less than r, then we define the 1-simplex $\left[ {x_{0} x_{1} } \right]$. Likewise, if the pairwise distance between the three points at x ₀, x ₁, and x ₂ are all less than r, then we define the 2-simplex $\left[ {x_{0} x_{1} x_{2} } \right]$.

Note that the definition of the Rips complex is very similar to that of the unit disk graph from Sect. 5.1.1. It is apparent from the two definitions that using parameter r for each, the 1-skeleton of the Rips complex is equivalent to the unit disk graph. The Rips complex can be considered as a sort of “higher dimensional” version of the unit disk graph.

This similarity in the Rips complex and the unit disk graph leads to an alternate approach to constructing the Rips complex which is extremely useful for sensor networks and was exploited in [45] to construct the Rips complex in a coordinate-free network. Given the communication graph of the network, which by definition is a unit disk graph, the graph can be expanded to include higher dimensional simplices as follows. Any complete graph on k vertices, that is, the graph in which all k vertices are pairwise adjacent, corresponds to a (k − 1)-simplex in the Rips complex. Thus, any triangles (K ₃) in the communication graph are “filled in” to become 2-simplices, any tetrahedrons (K ₄) are “filled in” to become 3-simplices, and so on. Since no locations are needed to create the communication graph the Rips complex for a sensor network can be constructed entirely from local connectivity data. Figure 5.16 shows an example communication graph and its induced Rips complex.

Fig. 5.16

Communication graph (a) and its induced Rips complex (b)

5.5.2 Comparison of Čech Complex and Rips Complex

While the Čech complex maps the coverage provided by the union of sensing coverage disks into a corresponding simplicial complex, this relationship is not as well defined for the Rips complex whose construction is based solely on the communication range of the nodes and does not take into account their sensing range at all. In [45], the ratio $r_{c} \le \sqrt 3 \cdot r_{s}$ is used since for a set of three nodes with maximum pairwise distance for communication range of $r_{c}$, the sensing radius must be at least $r_{c} /\sqrt 3$ for the sensing disks to have common intersection as shown in Fig. 5.17 [40].

Fig. 5.17

Relationship between r _c and r _s for the Rips complex

It can also be shown that the radius-r Rips complex has the same 1-skeleton as the radius-r/2 Čech complex. Thus, assuming $r_{s} = r_{c} /2$, then the Rips complex and the Čech complex are equivalent with the possible exception with three communicating nodes without a common intersection of their sensing disks. In other words, triangle-shaped holes, such as that in Fig. 5.15b, are not possible in the Rips complex since based on the above assumption the nodes are all within communication range, and they would immediately be “filled in” as 2-simplices.

Figure 5.18 shows examples of Rips and Čech complexes created using the above assumption. Notice that the only difference is that the triangle-shaped holes in the Čech complex do not exist in the Rips complex as mentioned above. This could be acceptable in some applications since the triangular holes represent areas with very small coverage holes, and larger holes will exist in both complexes. The drawback to using this assumption, however, is that if this ratio is not exact, then this equivalence between two simplicial complexes will not hold.

Fig. 5.18

Rips complex (left) and Čech complex (right) for $r_{s} = r_{c} /2$

Even with the help of either of the above assumptions, the Čech complex and Rips complex are still not equivalent. For this reason, results in [45] instead show how to infer Čech data by “squeezing” it between two Rips complexes constructed at different radii. This idea may be useful for verifying coverage, but it is not as helpful in localization of the holes. If the sensor nodes’ coordinates are known, then the Čech complex may be used to capture the exact coverage of the sensing disks. Otherwise, if sensor nodes’ coordinates are not known, then for any ratio between sensing and communication radii the Rips complex will only approximate the Čech complex.

5.5.3 Subcomplexes with Planar Topology

We introduce subcomplexes of both the Čech complex and the Rips complex [40]. The significance of these subcomplexes is that their underlying graphs are planar, meaning that they have no crossing edges. As a result, both simplicial complexes are 2-complexes, which mean that the largest k-simplex in the complex is a 2-simplex and k-simplices of higher dimensions cannot exist in the complex. These subcomplexes can be considered as the maximal subcomplexes that retain the number and shape of the holes in the original complex.

Alpha-Shape Complex [40]

Closely related to the Čech complex is the Alpha-shape complex, which is originally due to Herbert Edelsbrunner [11]. To construct this complex, one must first compute the Voronoi diagraph Vor _X for the point set X. Next, for each point $x \in X$ its Alpha-cell A(x, r) can be defined as the intersection ${\text{Vor}}_{X} (x) \cap B(x,r)$, where Vor _X (x) is the Voronoi cell of x and B(x, r) is an open ball of radius r centered at x. The Alpha-shape complex $C_{\alpha } \left( {X,r} \right)$ is defined by the nerve, or Čech complex of the set of Alpha-cells A(x, r). That is, a k-simplex in the Alpha-shape complex corresponds to the non-empty intersection of k + 1 alpha-cells.

Figure 5.19 shows the Voronoi diagram and sensing disks for a set of points. The collection of Alpha-cells, which is the intersection of each sensing disk and its Voronoi cell, is shown in Fig. 5.20. Finally, the nerve of these alpha-cells is taken to create the alpha-shape complex shown in Fig. 5.20. Notice that the two holes in the alpha-shape complex clearly correspond to the holes in the union of sensing disks from Fig. 5.19.

Fig. 5.19

Voronoi diagram (left) and union of sensing disks (right) for a set of points

Fig. 5.20

Alpha cells (left) and alpha shape complex (right) for point set from Fig. 5.19

It can be shown that for a given parameter r and a set of points X there is a homotopy equivalence between the two complexes, i.e., the thickness can be ignored (i.e., higher dimensional k-simplices), and the holes stayed preserved in the complex as shown in Fig. 5.21. Also, as may be expected with the use of the Voronoi diagram, the Alpha-shape complex is a subcomplex of the Delaunay complex and so its underlying graph must be planar.

Fig. 5.21

Union of sensing disks (a), Čech complex (b), and alpha shape complex (c) for a set of sensor nodes

Maximal Simplicial Complex [40]

Note that it is also highly desirable to have a planar subcomplex of the Rips complex, analogous to the relationship between the Čech and Alpha-shape complexes. The basic goal is to remove a subset of the edges in the communication graph such that the new graph is planar and the number and shape of holes is maintained in the induced Rips complex. In general, this is a difficult problem since the embedding is not known and removal of the wrong edges will have an effect on the holes in the induced Rips complex.

Researchers in [35] have proposed a solution to this problem by examining all crossing edges in the communication graph and carefully eliminating one edge in the crossing pair while still maintaining the structure of the topological holes. Authors refer to the planar subgraph as a maximal simplicial subgraph. After obtaining this subgraph, all that is left is to “fill in” all the triangles to obtain the induced Rips complex, which they call the maximal simplicial complex.

Figure 5.22 shows an example communication graph and its maximal simplicial complex obtained from the communication graph. The relative position of holes is maintained in the maximal simplicial complex.

Fig. 5.22

Communication graph (left) and its maximal simplicial complex (right)

5.6 Simplicial Homology and Coverage Holes

Homology is a mathematical method for detecting and counting holes in a topological space using algebra. A basic background on homology theory that is relevant to the sensor networks coverage is presented here, while a more complete development of homology theory can be found in [24, 36].

One way to define homology is as a vector space. For a simplicial complex K, the 1-dimensional homology H ₁(K) can be used to determine its holes. This can be represented as a vector space whose basis represents cycles in K surrounding its holes. Thus, the dimension of this vector space |H ₁(K)|, often called the first Betti number of K, gives the number of cycles that corresponds to the number of holes. Holes of higher dimension may also be found using homology. For example, the second Betti number for a sphere S, which is the dimension of H ₂(S), is 1 because the sphere is empty inside. For the sensor network coverage problems, one-dimensional holes correspond to holes in sensing coverage.

Computing the first Betti number of a simplicial complex is important in the analysis of coverage completeness since it provides information about a number of holes that exist in the network. Two software packages for computional homology are PLEX [46] and CHomP [8]. The typical Betti number implementations involve computing the rank of matrices, which for very large networks, can be prohibitively slow. However, this method does not take into account that the simplicial complexes are not arbitrary but are constrained by the physical nature of the sensor network. A simple arithmetic formula for computing the first Betti number of a simplicial complex K is given by:

$$b_{1} = b_{0} - \sum\limits_{k = 0}^{n} {( - 1)^{k} \left| {(k{\text{-simplices}}\,{\text{in}}\,K)} \right|} ,$$

(5.25)

where n corresponds to the largest k-simplex in K, and b ₀ is the zeroth Betti number, which is equivalent to the number of connected components in the underlying graph, or 1-skeleton, of K. This follows from the Euler characteristic χ for a simplicial complex which can be defined as the alternating sum of Betti numbers

$$\chi = \sum\limits_{k = 0}^{\infty } {( - 1)^{k} b_{k} } .$$

(5.26)

For an arbitrary simplicial complex, Betti numbers of any dimension may be nonzero. However, all the simplicial complexes that relate to sensor networks have constraints due to the disk-shaped sensing and communication ranges which have been assumed. Therefore, all Betti numbers of dimension larger than one will be zero if the nodes lie in the plane. This leads to the simplified formula

$$\chi = b_{0} - b_{1} ,$$

(5.27)

where b ₀ is equivalent to the number of connected components in the underlying graph. A second definition of the Euler characteristic for a simplicial complex K using the alternating sum of the number of k-simplices is given by

$$\chi = \sum\limits_{k = 0}^{n} {( - 1)^{k} \left| {(k{\text{-simplices}}\,{\text{in}}\,K)} \right|} ,$$

(5.28)

where n corresponds to the largest k-simplex in K. From here follows the Eq. (5.25).

The drawback of (5.25) in computing coverage holes is that one must know all higher dimensional simplices, whereas with the matrix intensive computations, only the (k + 1)-simplices and lower dimensions are needed to find the k-th Betti number. Thus, only the sets of 0-, 1-, and 2-simplices would be needed to compute b ₁. However, for the planar subcomplexes described above, the following simplified result can be used:

$$b_{1} = b_{0} - \left| {V(G)} \right| + \left| {E(G)} \right| - \left| {(2{\text{-simplices}}\,{\text{in}}\,K)} \right|,$$

(5.29)

where G is the underlying graph of the simplicial complex K. Under assumption that the 1-skeleton of K is a connected graph, which is typically the case, then b ₀ = 1 and so the computation can be simplified even further to

$$b_{1} = 1 - \left| {V(G)} \right| + \left| {E(G)} \right| - \left| {(2{\text{-simplices}}\,{\text{in}}\,K)} \right|.$$

(5.30)

Note that this formula can also be derived from Euler’s formula for connected planar graphs. Euler’s formula for a connected planar graph can be written as $V - E + F = 2$, where V is the number of vertices, E is the number of edges, and F is the number of faces. This formula, however, accounts for an additional face known as the infinite, or exterior face, which is not needed for sensor networks applications and can be discarded. Also, it is clear that the number of faces F in the planar underlying graph of one of the planar subcomplexes is the sum of the number of 2-simplices in the complex and the number of holes. This is due to the obvious fact that every face in the underlying graph is either a 2-simplex or a hole.

Example 5.3

Consider the simple complex illustrated in Fig. 5.23. The simplicial complex has seven 0-simplices (or vertices), nine 1-simplices (or edges), and two 2-simplices. Inserting these values into Eq. (5.30), we see that $b_{1} = 1 - 7 + 9 - 2 = 1$, as expected by observation of the simplicial complex (Fig. 5.23).

Fig. 5.23

Example simplicial complex with b ₁ = 1

In applications related to sensor networks hole coverage, the alpha-shape complex and the maximal simplicial complex have advantage over other complexes for multiple reasons. First, algorithms for computing the number of holes in the complex are computationally efficient by utilizing simple arithmetic calculations. Second, divide-and-conquer algorithms are often suitable for planar graphs. Furthermore, it allows for coverage holes to be defined as faces in the underlying planar graph. If the underlying graph is not planar, holes may not be uniquely identifiable as is shown in Fig. 5.24. Notice that the hole is not uniquely defined since one could argue that cycle A, B, D, cycle A, B, C, or cycle A, B, C, D are all the correct way to identify the hole.

Fig. 5.24

Sensing disks (left) and corresponding simplicial complex (right) which contains a hole that is not uniquely identifiable

5.7 K-Coverage

Coverage in WSNs applications is usually associated with 1-coverage where it is desired to have at least one sensor node covering every point of interest. If 1-coverage is not satisfied, then there is a hole in the sensor network coverage. The term hole here also refers to a 1-hole, meaning there is not at least one sensor node covering a certain area in the set of interest. A more robust network to node failures and other node related errors might have k-coverage requirements, i.e., that every point in the area of interest should be covered by at least k sensor nodes.

Definition 5.7

Consider a sensor network consisting of a set Z sensor nodes and a region on interest S. A subset $P \subset S$ is said to be k-covered if and only if for every point $p \in P$, there are at least k sensor nodes from Z that cover the point p.

Looking at the construction of the Čech complex it is evident that only a single point must be covered by k + 1 disks to create a k-simplex (e.g., see Fig. 5.15c). It is required to show that the entire area inside a polygon formed by k vertices is k-covered. This implies that for any single polygon vertex the other k − 1 vertices must all lie within its sensing disk and leads us back to the Rips complex, which admits a k-simplex if the pairwise distance between any set of k vertices is less than parameter r. Thus, a construction of the Rips complex using the parameter r _s allows one to determine k-coverage. For example, any 3-simplex in this simplicial complex comprised four vertices and, of course, the area inside the polygon formed by these vertices is 4-covered. Note that this method gives a sufficient (but not necessary) condition for k-coverage since there may still be other k-covered portions of the network which do not entirely fill the area inside a polygon formed by a subset of nodes. However, this is much like the case for 1-coverage where a hole in the simplicial complex looks large, but in reality, is much smaller when considering the actual union of sensing disks (e.g., see Fig. 5.15b).

5.8 Coverage Control

The problem of deploying sensors to satisfy application requirements is called coverage control problem [5]. The coverage control can be static, or offline, and dynamic, or online. In the static coverage, the sensor node locations are pre-calculated before the deployment, such that once deployed, the sensor network satisfies pre-assigned coverage mission requirements. This is equivalent to the facility location optimization problem in operations research. The dynamic coverage control includes mobile sensor networks, Fig. 5.25, where the coverage control is calculated online and the position of sensor nodes is adjusted according to specified criteria. Furthermore, the dynamic coverage control can be centralized with a central controller (or a base station) providing control inputs to the whole network, or distributed where each sensor node adjusts its position according to the locally executed algorithm.

Fig. 5.25

Micro-aerial vehicle based sensor network—a mobile sensor networks with dynamic coverage control

Another example of dynamic coverage control is a future WSN usage in weather monitoring and hurricane tracking. Even though hurricanes can be tracked by satellites, precise wind speed, precipitation, and pressure of the storm-affected area can be monitored and detected only using close-range sensing devices. Presently such monitoring and data gathering is done using NOAA reconnaissance airplane with probes that record air pressure, humidity, temperature, and wind speed that weather scientists use to predict storm surge, place and time when the storm hits the land.

Future hurricane monitoring systems will consist of a network of ground sensors and mobile sensors with coverage that can dynamically adapt to changes in the hurricane path and strength; see Fig. 5.26.

Fig. 5.26

Static and mobile sensor nodes track a hurricane

Several optimal control problems related to sensor networks were formulated in [5]. An optimal coverage under constraints of imprecise detection and terrain properties where the number of sensor nodes is minimized was presented in [9]. In [17] problems arising in maintaining coordination and communication between the group of robots and solutions to these problems were discussed. Three models of deployment are introduced to maximize the coverage area within the close range of the mobile nodes, deployment to maximize the probability of detecting a source, and deployment to maximize the visibility of the network. A variety of control methods in multi-vehicle cooperative control using graph theory have been presented in [41]. Optimal coverage control for mobile sensor networks was presented in [10]. The paper uses a Voronoi partitioning and Lloyd descent algorithm but does not consider network connectivity constraints. Two location functions that characterize coverage performance were provided in [9] including a study of their gradient properties via nonsmooth analysis. In most cases, the feasibility sets are assumed to be convex and related optimization problems are convex optimization problems. If network connectivity is considered as well, then underlying optimization problems become, in most cases, non-convex optimization problems.

Example 5.4

Consider a coverage control problem in chemical plants where it is required to provide an optimal coverage of large chemical plants or areas of interest with a large number of static sensor nodes that monitor for a wide spectrum of chemical agents; have several mobile nodes moving over rough plant terrain and track a possible contamination cloud; and allow technicians to adjust the controller of all mobile sensor nodes. This is an optimal coverage control problem with a trade-off between uniform coverage of the whole plant and focused coverage of the contamination cloud; see Fig. 5.27.

Fig. 5.27

Focused coverage (left) versus uniform coverage (right)

Let r be the sensors radio transmission range. Assume that there is a focus point $\left( {X_{F} (t),Y_{F} (t)} \right)$ where several mobile sensor nodes should converge. In the case of a chemical contamination example, the focus point can be a contamination cloud (center of mass of the cloud). Consider a region of interest S that is a compact set, and a set Z of sensor nodes. A subset $M \subset Z$ is a set of all mobile sensor nodes. An optimal coverage control problem can be formulated by specifying a cost function of interest and constraints that limit the network in terms of geometry, flow, energy, or any other network parameter.

The coverage control problem can be formulated as an optimal control problem, or more precisely, as a linear-quadratic regulator (LQR) problem. The problem is to find an optimal location of mobile nodes M, such that the following cost function is minimized:

$$\hbox{min} J_{1} = R\sum\limits_{i \in M} {{\text{dist}}^{2} \left[ {(x_{i} ,y_{i} ),(X_{F} (t),Y_{F} (t))} \right]} + Q\sum\limits_{i \in M,j \in Z} {{\text{dist}}^{ - 2} \left[ {(x_{i} ,y_{i} ),(x_{j} ,y_{j} )} \right]} ,$$

(5.31)

where R and Q are the control design parameters or weighting factors, and ${\text{dist}}\left[ {(x_{i} ,y_{i} ),(x_{j} ,y_{j} )} \right]$ is an Euclidean distance between nodes i and j and is given by

$${\text{dist}}\left[ {(x_{i} ,y_{i} ),(x_{j} ,y_{j} )} \right] = \sqrt {(x_{i} - x_{j} )^{2} + (y_{i} - y_{j} )^{2} } .$$

(5.32)

Note that this is a convex optimization problem since the optimization cost function is convex and there are no constraints. Convex optimization refers to cost function being a convex function and constraint set being a convex set; otherwise, optimization is a non-convex and common operation research methods do not apply. For extra reading on non-convex optimization, we refer to [27]. The parameter R penalizes closeness to the focus point, or tracking of the target. The parameter Q penalizes uniform distribution of nodes across the set S. For example, R = 10, Q = 10,000 means that the user is much more concerned with the uniform node distribution than to cover the specific area of interest, Fig. 5.27 (right). On the other hand, R = 10,000, Q = 10 indicates that the user wants extensive coverage of the focus point (tracking) rather than uniform node distribution, Fig. 5.27 (left).

The cost function in (5.31) has such specific form because the original problem is a multi-objective optimization problem. One common way to solve this type of problem is to combine the weighted sums of each individual objective function into an aggregate objective function (AOF). Specifically, the two objectives are to minimize the distance between the mobile nodes and the focus point and to maximize the distance between the mobile nodes and the other static and mobile nodes (minimize the inverse of this distance).

The problem formulation, including the cost function that is given in (5.31) has more of a theoretical significance, since it does not consider the network connectivity. Namely, such a solution will optimize the cost function and distribute the nodes accordingly without consideration of the network connectivity. Some sensor nodes can go out of communication range and become useless from the network standpoint. More realistic problem formulation that includes network connectivity can be given as follows.

Given the compact coverage area of interest S, a focus point $\left( {X_{F} (t),Y_{F} (t)} \right)$, sensor network graph $G(t) = \left( {N(t),E(t)} \right)$ and mobile subgraph $G_{m} (t) = \left( {M(t),E_{m} (t)} \right)$, find an optimal vertex location of the mobile subgraph $G_{m} (t)$ such that the following cost function is minimized

$$\hbox{min} J_{2} = R\sum\limits_{i \in M} {{\text{dist}}^{2} \left[ {(x_{i} ,y_{i} ),(X_{F} (t),Y_{F} (t))} \right]} + Q\sum\limits_{i \in M,j \in N} {{\text{dist}}^{ - 2} \left[ {(x_{i} ,y_{i} ),(x_{j} ,y_{j} )} \right]} ,$$

(5.33)

such that the graph $G(t)$ stays vertex k-connected and satisfies the mobile node localization condition. Constants R and Q are control design parameters.

Note that this is a non-convex optimization problem where a feasibility set is, in general, a non-convex set. Similarly, one can formulate suboptimal sensor network coverage control problem with focus/target areas possibly represented by several disjoint sets. Such constraint set is, in general, non-convex.

An optimal deployment that is based on probabilistic models is given in [59]. The sensor locations (x,y) have Gaussian distribution given by its mean and standard deviation, as well as its join distribution $p_{xy} (x,y)$. The probability for a gridpoint $(i,j)$ to be detected by a sensor at $(x,y)$ is given by $c_{ij} (x,y)$ and the miss probability of the gridpoint is $m_{ij} (x,y) = 1 - c_{ij} (x,y)$. For a set N of deployed static sensors, the total miss probability of the gridpoint $(i,j)$ is given by

$$m_{ij} = \prod\limits_{(x,y) \in N} {(1 - c_{ij} (x,y)} ).$$

(5.34)

Assuming that the newly deployed sensor will be placed at $(x,y)$, the total miss probability is given by

$$m(x,y) = \sum\limits_{{(i,j) \in {\text{Grid}}}} {m_{ij} (x,y)m_{ij} } .$$

(5.35)

Based on the calculated total miss probability, one can place the sensor to minimize the miss probability, providing the best possible sensor network coverage from the probability of detection point of view under given assumptions of grid deployment. After every node deployment, above probabilities are updated and recalculated based on new topology. The computational complexity of miss probability algorithm is $O(n^{2} m^{2} )$ for a grid size of $n \times m$.

Questions and Exercises

• 1. What is the degree of a vertex in a graph G? Provide an example.

• 2. Explain when is a graph connected? Draw examples of connected and disconnected graphs.

• 3. Demonstrate by example that if a graph G is disconnected, then its complement $\bar{G}$ is connected. Show another example that the opposite is not true—if the graph G is connected, then its complement $\bar{G}$ is not necessary disconnected. Finally, prove this statement rigorously.

• 4. Study the Chvátal’s art gallery theorem and find out what is an upper bound on the minimal number of guards that are required to cover the gallery? Please describe “upper bound on the minimal number” in case of this problem.

• 5. If the gallery floor plan can be divided into square rooms, what would be the upper bound on the minimal number of guards required to cover the gallery in this case?

• 6. When one can say that complete sensing coverage of a convex region implies connectivity of the network?

• 7. Given a graph $V = \{ 1,2,3,4,5,6,7\}$, $E = \{ (1,2),(1,3),(1,5),(2,3),(3,5),(4,7),(6,7)\}$, using a graph Laplacian check if the graph is connected. Find the number of spanning trees using Laplacian eigenvalues.

• 8. Given a graph $V = \{ 1,2,3,4,5,6,7,8,9\}$, $E = \{ (1,2),(1,3),(1,5),(2,3),(3,5),(3,6),(4,5),(5,8),(5,9),(6,7),(6,8)\}$, estimate the lower and upper bounds on the graph diameter.

• 9. For a graph with vertices $V = \{ 1,2,3,4,5\}$, draw a complex and a simplicial complex.

• 10. For a set of points in two-dimensional space with the following coordinates $X = \{ ( - 1, - 2),(1,0),(2,3),(3, - 4),( - 3, - 5)\}$, draw a Voronoi diagram and derive alpha shape complex.

• 11. Describe a k-coverage in sensor networks and its relationship with the Rips complex. What does it mean by 2-coverage specifically and in terms of the Rips complex?

• 12. Use linear quadratic control problem setup similar to the one given in Eq. (5.31) and formulate a sensor network coverage control problem where it is required for mobile nodes to be attracted to the target node, to be repelled from the static sensor nodes, and to be repelled from each other (mobile nodes).

• 13. How can you extend the previous problem formulation and include constraints that would ensure collision avoidance between mobile sensor nodes?