Zheng, Rong2014-03-132014-03-13December 22012-12http://hdl.handle.net/10657/565Sensor networks have risen in importance in last several years. They have been deployed for several tasks, such as monitoring volcanoes, monitoring buildings and infrastructures, detecting enemy instrution in military, etc... Sensor location plays an important role in network quality. It has impact on different aspects, i.e., network connectivity, network coverage to name a few. However, exact sensor locations are rarely achieved. In the one hand, sensors may be misplaced during operations. On the other hand, sensor locations are kept uncertain due to privacy concerns. This raises the need for investigating sensor networks with the presence of sensor location uncertainty. This dissertation provides an analysis on sensor networks with the presence of uncertainty. First, we investigate network coverage and target localization and tracking using binary proximity sensors under sensor location uncertainty. A deterministic, polynomial-time algorithm is devised to compute the minimum sensing range for guaranteed coverage. Furthermore, algorithms are proposed for target localization and measurement model for target tracking in sensor networks. The approaches are based on the high order maximum Voronoi diagram of disks in the plane. Next, we study privacy in spatial queries. In contrast to sensor location uncertainty, uncertainty is introduced to spatial queries to protect user information. Essentially, the querying user is grouped with other users to form a cloak for which spatial queries are made, instead of a single query location. In this disseration, a framework for user identity privacy in $k$-nearest queries is proposed, in which we devise a $k$-anonymous, locality-preserving cloaking algorithm. Cloaks are also used in spatial skyline queries, which leads to different domination relationships. The disseration proposes geometric algorithms for spatial skyline queries with user location uncertainty. In addition, the fuzzy domination relationship in spatial skyline queries is investigated. Our work opens up new directions in spatial skyline queries with uncertainty.application/pdfengThe author of this work is the copyright owner. UH Libraries and the Texas Digital Library have their permission to store and provide access to this work. Further transmission, reproduction, or presentation of this work is prohibited except with permission of the author(s).Sensor networkMobile networkUncertaintySkyline querySpatial skyline queryComputational geometryPrivacyLocation-based serviceComputer science2014-03-13Thesisborn digital