Designing localized algorithms for large‐scale wireless sensor networks : a geometric perspective

Abstract

Wireless Sensor Networks (WSNs) provide the service of monitoring and sensing physical environment. With the pervasive applications of WSNs in various fields, the increasing network scale brings considerable challenges in many aspects, from high-level applications to low-level networking and communication. In this thesis, we try to understand large-scale WSNs from geometric perspective. In particular, by exploiting the multi-fold geometric properties of WSNs (e.g., sensor nodes' locations and connectivity as well as their unique sensing/communicating models), we can build geometric models and apply geometric algorithms to address perplexing problems of large-scale WSNs. In contrast to typical geometric techniques which require global information as input, we design localized algorithms which can be performed by individual sensor nodes in a distributed manner using only locally available information, to benefit large-scale WSNs in terms of time cost, system adaptivity and robustness, energy efficiency, as well as network performance.

In many applications, a large-scale WSN is deployed to monitor and survey time-variant events, which demands a fast boundary detection technique. Considering sensor nodes may be deployed in a 3D volume, the first focus of this thesis is boundary detection for large-scale 3D WSNs. We model a 3D WSN as point cloud sampled from a hypothetic 3D volume. Borrowing the idea of direct visibility, we present an on-line boundary detection algorithm to identify the sensor nodes on the boundary surfaces of the 3D volume using only local position information. Additionally, we propose a localized parametrization algorithm to regulate the detected arbitrarily shaped network boundaries into spheres, thereby supporting other network functionalities, e.g., distinguishing internal boundaries from the external one, and geographic routing. We evaluate our strategies of boundary detection and regulation with extensive implementations and simulations.