We consider an interval coverage problem. Given @math intervals of the same length on a line @math and a line segment @math on @math , we want to move the intervals along @math such that every point of @math is covered by at least one interval and the sum of the moving distances of all intervals is minimized. As a basic geometry problem, it has applications in mobile sensor barrier coverage in wireless sensor networks. The previous work solved the problem in @math time. In this paper, by discovering many interesting observations and developing new algorithmic techniques, we present an @math time algorithm. We also show an @math time lower bound for this problem, which implies the optimality of our algorithm.
A Wireless Sensor Network (WSN) uses a large number of sensors to monitor some surrounding environmental phenomena @cite_0 . Each sensor is equipped with a sensing device with limited battery-supplied energy. The sensors process data obtained and forward the data to a base station. Intrusion detection and border surveillance constitute a major application category for WSNs. A main goal of these applications is to detect intruders as they cross the boundary of a region or domain. For example, research efforts were made to extend the scalability of WSNs to the monitoring of international borders @cite_16 @cite_1 . Unlike the traditional full coverage @cite_15 @cite_7 @cite_3 which requires an entire target region to be covered by the sensors, the barrier coverage @cite_8 @cite_9 @cite_10 @cite_14 @cite_1 only seeks to cover the perimeter of the region to ensure that any intruders are detected as they cross the region border. Since barrier coverage requires fewer sensors, it is often preferable to full coverage. Because sensors have limited battery-supplied energy, it is desired to minimize their movements.
@cite_14 @cite_7 @cite_8 @cite_9 @cite_1 @cite_3 @cite_0 @cite_15 @cite_16 @cite_10
2301250350 2219395474 1989231680 2111815723
Barrier coverage in Wireless Sensor Networks (WSNs) is an important research issue as intruder detection is the main purpose of deploying wireless sensors over a specified monitoring region. In WSNs, excessive volume and variety of sensor data are generated, which need to be analyzed for accurate measurement of the image in terms of width and resolution. In this paper, a three layered big data analytic architecture is designed to analyze the data generated during the construction of the barrier and detection of the intruder using camera sensors. Besides, a cloud layer is designed for storing the analyzed data to study the behavior of the intruder. In order to minimize the number of camera sensors for constructing the barrier, algorithms are designed to construct the single barrier with limited node mobility and the barrier path Quality of Sensing (QoS) is maintained with a minimum number of camera sensors. Simulation results show that our algorithms can construct 100 of the barrier with fewer number of camera sensors and average data processing time can be reduced by using parallel servers even if for larger size of data. Wireless sensor network (WSN) brings a new paradigm of real-time embedded systems with limited computation, communication, memory, and energy resources that are being used for huge range of applications where the traditional infrastructure-based network is mostly infeasible. The sensor nodes are densely deployed in a hostile environment to monitor, detect, and analyze the physical phenomenon and consume considerable amount of energy while transmitting the information. It is impractical and sometimes impossible to replace the battery and to maintain longer network life time. So, there is a limitation on the lifetime of the battery power and energy conservation is a challenging issue. Appropriate cluster head (CH) election is one such issue, which can reduce the energy consumption dramatically. Low energy adaptive clustering hierarchy (LEACH) is the most famous hierarchical routing protocol, where the CH is elected in rotation basis based on a probabilistic threshold value and only CHs are allowed to send the information to the base station (BS). But in this approach, a super-CH (SCH) is elected among the CHs who can only send the information to the mobile BS by choosing suitable fuzzy descriptors, such as remaining battery power, mobility of BS, and centrality of the clusters. Fuzzy inference engine (Mamdani’s rule) is used to elect the chance to be the SCH. The results have been derived from NS-2 simulator and show that the proposed protocol performs better than the LEACH protocol in terms of the first node dies, half node alive, better stability, and better lifetime. Sensing coverage is an essential functionality of wireless sensor networks (WSNs). However, it is also well known that coverage alone in WSNs is not sufficient, and hence network connectivity should also be considered for the correct operation of WSNs. In this paper, we address the problem of k-coverage in WSNs such that in each scheduling round, every location in a monitored field (or simply field) is covered by at least k active sensors while all active sensors are being connected. Precisely, we study sensors duty-cycling strategies for generating k-coverage configurations in WSNs. First, we model the k-coverage problem in WSNs. Second, we derive a sufficient condition of the sensor spatial density for complete k-coverage of a field. We also provide a relationship between the communication and sensing ranges of sensors to maintain both k-coverage of a field and connectivity among all active sensors. Third, we propose four configuration protocols to solve the problem of k-coverage in WSNs. We prove that our protocols select a minimum number of sensors to achieve full k-coverage of a field while guaranteeing connectivity between them. Then, we relax some widely used assumptions for coverage configuration in WSNs, to promote the use of our proposed protocols in real-world sensing applications. Our simulation results show that our protocols outperform an existing distributed k-coverage configuration protocol. Wireless Sensor Networks (WSN) are often densely deployed in the region of interest in order to continuously monitor physical phenomenon. Due to highly deployment density and the nature of the physical phenomenon, nearby sensor readings are often highly correlated in both space domain and time domain. These spatial and temporal correlations bring significant potential advantages as well as challenges for developing efficient sensing scheduling protocols for WSN. In this paper, a theoretical framework is developed to model the Quality of Monitoring (QoM) by exploiting both spatial and temporal correlations. The objective of this work is to enable the development of efficient sensing scheduling protocols which exploit these advantageous intrinsic features of the WSN paradigm. Specially, we propose two sensing scheduling schemes in order to maximize the overall QoM subject to resource constraints (e.g., under fixed duty cycle). Extensive experiments validate our theoretical results.