In many surveillance scenarios, there are some known critical locations where the events of concern are expected to occur. A common goal in such applications is to use sensors to monitor these critical locations with sufficient quality of surveillance within a designated period. However, with limited sensing resources, the coverage and lifetime requirement may not be satisfied at the same time. Thus, sometimes the sensor needs to reduce its duty cycle in order to satisfy the stringent lifetime constraint. In this paper, we model the critical location coverage problem using a point coverage model with the objective of scheduling sensors to maximize the event detection probability while meeting the network lifetime requirement. We show that this problem is NP-hard and propose a distributed algorithm with a provable approximation ratio of 0.5. Extensive simulations show that the proposed distributed algorithm outperforms the extensions of several state-of-the-art schemes with a significant margin while preserving the network lifetime requirement.

Mission-driven sensor networks usually have special lifetime requirements. However, the density of the sensors may not be large enough to satisfy the coverage requirement while meeting the lifetime constraint at the same time. Sometimes, coverage has to be traded for network lifetime. In this paper, we study how to schedule sensors to maximize their coverage during a specified network lifetime. Unlike sensor deployment, where the goal is to maximize the spatial coverage, our objective is to maximize the spatial-temporal coverage by scheduling sensors' activity after they have been deployed. Since the optimization problem is NP-hard, we first present a centralized heuristic whose approximation factor is proved to be 1/2, and then, propose a distributed parallel optimization protocol (POP). In POP, nodes optimize their schedules on their own but converge to local optimality without conflict with one another. Theoretical and simulation results show that POP substantially outperforms other schemes in terms of network lifetime, coverage redundancy, convergence time, and event detection probability.

Self-monitoring the sensor statuses such as liveness, node density and residue energy is critical for maintaining the normal operation of the sensor network. When building the monitoring architecture, most existing work focuses on minimizing the number of monitoring nodes. However, with less monitoring points, the false alarm rate may increase as a consequence. In this paper, we study the fundamental tradeoff between the number of monitoring nodes and the false alarm rate in the wireless sensor networks. Specifically, we propose fully distributed monitoring algorithms, to build up a poller-pollee based architecture with the objective to minimize the number of overall pollers while bounding the false alarm rate. Based on the established monitoring architecture, we further explore the hop-by-hop aggregation opportunity along the multihop path from the polee to the poller, with the objective to minimize the monitoring overhead. We show that the optimal aggregation path problem is NP-hard and propose an opportunistic greedy algorithm, which achieves an approximation ratio of 5/4. As far as we know, this is the first proved constant approximation ratio applied to the aggregation path selection schemes over the wireless sensor networks.

In this paper, we study sensor enabled landmine networks by formulating a minimum-cost mine selection problem. The problem arises in a target defence scenario, where the objective is to destroy the intruding targets using the minimum-cost pre-deployed mines. Due to the problem complexity, we first transform it using a novel bucket-tub model, and then propose several approximation algorithms. Among them, it is shown that the layering algorithm can achieve an approximation ratio of alpha ldr f, where alpha ges 1 is the tunable relaxation factor and f is the maximum number of mines that a target is associated with, and that the greedy algorithm has an approximation ratio of SigmajRj, where Rjis the coefficient in the related integer program. We also present a localized greedy algorithm which is shown to produce the same solution set as the global greedy algorithm. Theoretical analysis and extensive simulations demonstrate the effectiveness of the proposed algorithms.

For sensor networks deployed in unattended, harsh environments, the knowledge of sensor statuses such as liveness, node density and residue energy, is critical for maintaining the normal operation of the network. In this paper, we propose a poller-pollee based architecture to monitor the sensor status, focusing on two important issues: false alarm and energy efficiency. To reduce the false alarm rate, each pollee is monitored by multiple pollers. However, this approach will increase the power and bandwidth consumption. To address this issue, we propose a novel solution where the monitored sensor sends the status reports to different pollers in a round robin manner. In this way, bandwidth and power can be saved, and the false alarm rate can be reduced. We further propose a simple randomized algorithm to select the optimal number of pollers to stochastically minimize the expected total energy consumption due to monitoring. Theoretical analyses and simulations are used to demonstrate the effectiveness of the proposed techniques.

To prolong the lifetime of sensor networks, various scheduling schemes have been designed to reduce the number of active sensors. However, some scheduling strategies, such as partial coverage scheduling and target coverage scheduling, may result in disconnected network topologies, due to the low density of the active nodes. In such cases, traditional routing algorithms cannot be applied, and the shortest path discovered by these algorithms may not have the minimum packet delivery latency. In this paper, we address the problem of finding minimum latency routes in intermittently connected sensor networks by proposing an on-demand minimum latency (ODML) routing algorithm. Since on-demand routing algorithm does not work well when the source and destination frequently communicate with each other, we propose two proactive minimum latency routing algorithms: optimal-PML and quick-PML. Theoretical analysis and simulation results show that (1) ODML can effectively identify minimum latency routes which have much smaller latency than the shortest path, and (2) optimal-PML can minimize the routing message overhead and quick-PML can significantly reduce the route acquisition delay.

This paper focuses on designing autonomous device discovery algorithms for Bluetooth networks. We first extend the conventional asymmetric Bluetooth link model to three point-to-point symmetric link models. Their performances are compared analytically. To achieve proximity awareness among a group of Bluetooth devices, three control information exchanging methods are also proposed. Combining with the three link models, this gives 9 possible variants of autonomous device discovery algorithm. A comprehensive comparative study based on these 9 variants is then carried out using Bluehoc simulator.

Data exchange within a Bluetooth piconet is master-driven. The channel/slot utilization thus depends on the efficiency of the scheduling algorithm adopted by the master. In this paper, a novel MAC layer scheduling algorithm, called floating threshold (FT), is proposed. Unlike existing approaches, FT allows the master to estimate the backlog queue status at each slave accurately based only on a single feedback bit and a floating threshold. The master can then derive an optimized packet transmission schedule. Using simulations, we show that FT outperforms existing algorithms in terms of channel utilization, packet delay and packet dropping probability.