28-09-2016, 11:34 AM
1456551779-SensingCoverageandConnectivityinLargeSensorNetwork.rtf (Size: 1.77 MB / Downloads: 6)
In this paper, we address the issues of maintaining sensing coverage and connectivity by keeping a minimum number of sensor nodes in the active mode in wireless sensor networks. We investigate the relationship between coverage and connectivity by solving the following two sub-problems. First, we prove that if the radio range is at least twice the sensing range, complete coverage of a convex area implies connectivity among the working set of nodes. Second, we derive, under the ideal case in which node density is sufficiently high, a set of optimality conditions under which a subset of working sensor nodes can be chosen for complete coverage.
Based on the optimality conditions, we then devise a decentralized density control algorithm, Optimal Geographical Density Control
(OGDC), for density control in large scale sensor networks. The OGDC algorithm is fully localized and can maintain coverage as well as connectivity, regardless of the relationship between the radio range and the sensing range. Ns-2 simulations show that OGDC outperforms existing density control algorithms [25, 26, 29] with respect to the number of working nodes needed and network lifetime (with up to 50% improvement), and achieves almost the same coverage as the algorithm with the best result.
INTRODUCTION
Recent technological advances have led to the emergence of pervasive networks of small, low-power devices that integrate sensors and actuators with limited on-board processing and wireless communication capabilities. These sensor networks open new vistas for many potential applications,
such as battlefield surveillance, environment monitoring and biological detection [2, 10, 13, 17].
Since most of the low-power devices have limited battery life and replacing batteries on tens of thousands of these devices is infeasible, it is well accepted that a sensor network should be deployed with high density (up to 20 nodes/m3 [23]) in order to prolong the network lifetime. In such a high-density network with energy-constrained sensors, if all the sensor nodes operate in the active mode, an excessive amount of energy will be wasted, sensor data collected is likely to be highly correlated and redundant, and moreover, excessive packet collision may occur as a result of sensors intending to send packets simultaneously in the presence of certain triggering events. Hence it is neither necessary nor desirable to have all nodes simultaneously operate in the active mode.
One important issue that arises in such high-density sensor networks is density control — the function that controls the density of the working sensors to certain level [29]. Specifically, density control ensures only a subset of sensor nodes operates in the active mode, while fulfilling the following two requirements: (i) coverage: the area that can be monitored is not smaller than that which can be monitored by a full set of sensors; and (ii) connectivity: the sensor network remains connected so that the information collected by sensor nodes can be relayed back to data sinks or controllers. Under the assumption that an (acoustic or light) signal can be detected with certain minimum signal to noise ratio by a sensor node if the sensor is within a certain range of the signal source, the first issue essentially boils down to a coverage problem: assuming that each node can monitor a disk (the radius of which is called the sensing range of the sensor node) centered at the node on a two dimensional surface, what is the minimum set of nodes that can cover the entire area? Moreover, if the relationship between coverage and connectivity can be well characterized (e.g., under what condition coverage may imply connectivity and vice versa), the connectivity issue can be studied, in conjunction with the first. In addition to the above two requirements, it is desirable to choose a minimum set of working sensors in order to reduce power consumption and prolong network lifetime. Finally, due to the distributed nature of sensor networks, a practical density control algorithm should be not only distributed but also completely localized (i.e., relies on and makes use of local information only) [10].
In this paper, we address the issue of density control in an analytic framework, and based on the findings, propose a fully decentralized and localized algorithm, called Optimal Geographical Density Control (OGDC), in large scale sensor networks. Our goal is to maintain coverage as well as connectivity using a minimum number of sensor nodes. We investigate the relationship between coverage and connectivity by solving the following
Sensor Area Coverage 91
two sub-problems. First, we prove that under the assumption (A1) the radio range is at least twice the sensing range, a complete coverage of a convex area implies connectivity among the set of working nodes. Note that as indicated in Tables 2 and 3, (A1) holds for a wide spectrum of sensor devices that recently emerge. As a result, the proof allows us to focus only on the coverage problem, as complete coverage implies connectivity. Second, we explore, under the ideal case that the node density is sufficiently high, a set of optimality conditions under which a subset of working nodes can be chosen for complete coverage. Based on the optimality conditions, we then devise a decentralized and localized density control algorithm, OGDC. We also discuss the procedures taken by OGDC in the (infrequent) case that the radio range is smaller than twice the sensing range, thus allowing OGDC to be uniformly applied to all cases. We also perform ns-2 simulations to validate OGDC and compare it against a hexagon-based GAF-like algorithm, the PEAS algorithm presented in [29] and the CCP protocol in [26].
Several researchers have addressed the same or similar issues, with the work reported in [11,25,26,28,29] coming closest to ours. (We will provide a detailed summary of existing work in Section 5.) However, the work reported in [28,29] does not ensure complete coverage. Although the work reported in [25] does attempt to solve the complete coverage problem, it requires a large number of nodes to operate in the active mode (even more than a simple algorithm based on the idea of GAF does [27]). On the other hand, the work in [11] assumes error-free channels and requires reliable broadcasting in a certain range, which is hard to implement in wireless environments. The very recent work by Wang et al. [26] contains a similar analysis on the relationship between coverage and connectivity, but does not derive optimal conditions for minimizing the number of working nodes as we do in this paper.
The rest of the paper is organized as follows. In Section 2 we investigate the relationship between coverage and connectivity. In Section 3 we derive the optimality conditions for complete coverage under the ideal case. Following that, we present in Section 4 the proposed density control algorithm, and give in Section 5 a detailed summary of existing works. Finally, we present our simulation study in Section 6 and conclude the paper in Section 7.