Coverage Problem in Wireless Sensor Networks

Monitoring and surveillance are two of the main applications of wireless sensor networks. Network coverage measures how well an area is monitored by a sensor network. As an important research issue in wireless sensor networks today, the coverage problem has been studied extensively, and many solutions have been proposed. Some solutions focus on pure coverage problems to characterize the coverage of wireless ad hoc sensor networks, i.e., the $k$ -coverage problem [55] bnd the arrier coverage problem [38]. Other solutions integrate network connectivity into coverage problems, since network connectivity, which indicates whether any two nodes in a sensor network can communicate with each other, is necessary for successful data transmission.

We have investigated variations of coverage models in wireless sensor networks and some results are briefly described as follows.

Given a barrier (i.e., a path, a cycle, a simple polygon) and mobile sensors (or robots) that are lying in the interior of this barrieri, where the sensors can move autonomously in the plane, we investigate how to move the sensors within this region so as to optimize either the minimum sum or the minimum of the maximum of the distances covered by the respective sensors. In [10], we introduced the above problem and showed that,

• the min-max problem on the unit-disk-barrier can be solved in $O(n^{3.5}\log{n})$ time where $n$ is the number of mobile sensors,
• the min-max problem on a simple polygon can be solved in $O(mn^{3.5}\log{n})$ time where $m$ is the size of the simple polygon,
• for a given constant $\epsilon$ , there is an $O(\frac{1}{\epsilon}n^{4})$ -time algorithm for the min-sum problem on the unit-disk-barrier with an approximation ratio of no more than $1+\epsilon$ , and
• for a given constant $\epsilon$ , there is an $O(\frac{1}{\epsilon}mn^{5})$ -time algorithm for the min-sum problem on a simple polygon with an approximation ratio of no more than $1+\epsilon$ .

Most recently, we studied the $k$ -barrier coverage problem on a belt region [38] and proposed an efficient algorithm for it with an approximation ratio of no more than $2$ . A belt region with a sensor network deployed over it is said to be $k$ -barrier covered if and only if all paths crossing through the belt are $k$ -covered by the sensor network.

In [11], we investigate the problem of converting (connected) networks of omnidirectional sensors to strongly connected networks of sensors with multiple directional antennae. Consider a set $S$ of $n$ points in the plane modeling sensors of an ad hoc network. Each sensor uses a fixed number, say $1 \leq k \leq 5$ , of directional antennae modeled as a circular sector with a given spread (or angle) and range (or radius). In the paper, we give algorithms for orienting the antennae at each sensor so that the resulting directed graph induced by the directed antennae on the nodes is strongly connected, and also study tradeoffs between angle spread and range for maintaining connectivity.

Table 4 summarizes the results obtained and also mentions previous results from the literature. We assume that the maximum length of edges in a Minimum Spanning Tree of $S$ is 1. (Notation: Let $\varphi_k$ be a given non-negative value in $[0,2\pi)$ such that the sum of angles of $k$ antennae at each sensor location is bounded by $\varphi_k, k=1,\ldots,4$ .)

Table 4: Upper bounds on antenna range for various specified sums of antennae.

Antennae #	Antennae Spreads	Antennae Range	Reference
$1$	$\varphi_1 \geq 0$	$2$	[46]
	$\pi\leq \varphi_1< 8\pi/5$	$2\sin{\left(\pi- \varphi_1 /2 \right) }$	[16]
	$\varphi_1\geq 8\pi/5$	$1$	[16]
$2$	$\varphi_2 \geq \pi$	$2 \sin (2 \pi /9)$	[11]
	$\frac{2\pi}{3} \leq \varphi_2 < \pi$	$2 \sin (\frac{\pi}{2} -\frac{\varphi_2}{4} )$	[11]
	$\varphi_2 \geq 6\pi/5$	$1$	[11]
$3$	$\varphi_3 \geq 2\pi/3$	$\sqrt{2}$	[11]
	$\varphi_3 \geq 4\pi/5$	$1$	[11]
$4$	$\varphi_4 \geq 2\pi/5$	$1$	[11]

In [11], we gave several tradeoffs between antenna spread and range when each sensor has $k$ directional antennae, $k = 2, 3, 4$ , so as to guarantee the resulting network is strongly connected. Several problems remain open. Lower bounds are lacking from our study and it remains open to prove NP completeness results for the case of multiple antennae per sensor. Another interesting question concerns ensuring that for a given integer $c$ the resulting network is strongly $c$ -connected, i.e., it remains strongly connected after the deletion of any $c-1$ nodes.