Given a set of points of interest (POIs), the spatial skyline query for a set of locations returns the POIs that are close to all locations. Answering spatial skyline query can find many applications in Geographical Information Systems. In this paper, we consider the problem of spatial skyline query with uncertainty. Two types of uncertainty are investigated. First, location uncertainty arises when query point (user) locations are not known exactly either due to privacy concerns or measurement limitations. Second, error margins can be used to model tolerance to distance measurement errors between POIs and query points. We devise efficient polynomial-time algorithms to address both types of uncertainty, and rigorously prove their correctness.

Since the onset of wireless sensor networks, target localization and tracking have received much attention in a wide range of applications including battle field surveillance, wildlife monitoring and border security. However, little work has been done that addresses the realistic considerations of uncertainties in sensor locations and evaluates their impacts on the accuracy of target localization and tracking. In this paper, we carry out a rigorous study of these problems using a computational geometry approach. We introduce the geometric structures of order-k max and min Voronoi Diagrams (VDs) and propose an algorithm to construct these diagrams. Based on order-k max and min VDs, efficient algorithms are developed to evaluate the likelihood of noisy sensor readings and kNN queries, which serve as building blocks in target localization and tracking under sensor location uncertainties.

Location privacy is an important concern in participatory sensing applications, where users can both contribute valuable information (data reporting) as well as retrieve (location-dependent) information (query) regarding their surroundings. K-anonymity is an important measure for privacy to prevent the disclosure of personal data. In this paper, we propose a mechanism based on locality-sensitive hashing (LSH) to partition user locations into groups each containing at least K users (called spatial cloaks). The mechanism is shown to preserve both locality and K-anonymity. We then devise an efficient algorithm to answer kNN queries for any point in the spatial cloaks of arbitrary polygonal shape. Extensive simulation study shows that both algorithms have superior performance with moderate computation complexity.

Uncertainty in sensor locations is a norm in both planned and unplanned deployments. Even carefully positioned in the deployment phase, sensors may be displaced due to environmental or human factors during the course of operation. In this paper, we present a systematic study of the impact of location uncertainty on the coverage properties of wireless sensor networks. The uncertainty is modeled as disks of possibly different radius around the nominal positions. We introduce the concept of order-k (k ≥ 1) max Voronoi Diagram (VD) and devise an efficient polynomial algorithm to construct order-k VDs. Order-k max VD is critical in determining the minimum sensing radius needed to ensure worst-case k-coverage, call k-exposure. Simulation studies validate the correctness of the proposed algorithms and demonstrate their superiority over a naive approach.

Distributed active sensing is a new sensing paradigm, where active sensors and passive sensors are distributed in a field, and collaboratively detect and track the objects. "Exposure" of distributed active sensing networks (DASNs) quantifies the dimension limitations in detectability. It is important to deploy the sensors such that the exposure is minimized. Exposure minimization is shown to be NP-hard, and thus efficient heuristic algorithms are needed. In this paper, we propose a Genetic Algorithm (GA)-based solution that aims at achieving low exposure, scalability, and fast convergence. A novel flat binary chromosome encoding scheme and corresponding crossover and mutation operators are devised. Geometric knowledge is incorporated to significantly improve the convergence rate. Through extensive simulations, we demonstrate that the proposed algorithm outperforms a simple heuristic algorithm by up to 75%. The simulation results show that this algorithm is robust, self-adaptive and efficient under irregular boundary conditions.

Distributed active sensing is a new sensing paradigm, where active sensors (aka actuators) as illuminating sources and passive sensors as receivers are distributed in a field, and collaboratively detect events of interest. In this paper, we study the fundamental properties of distributed actuator and sensor networks (DASNs) in detecting and localizing obstacles. A novel notion of “exposure” is defined, which quantifies the dimension limitations in detectability. Using simple geometric constructs, we propose polynomial-time algorithms to compute the exposure and bounding regions where the center of the obstacles may lie.