UC Santa Cruz

Outdoor IoT networks are used for a range of applications including surveillance and environmental monitoring. The nodes of such networks sense environmental data and, through wireless networks that interconnect them, transmit these measurements to data collection sites known as sinks. Much research in this area focuses on 2D deployments where nodes must remain coplanar and 3D deployments where nodes can move freely through the air or underwater. However outdoor deployments where nodes remain on the surface of terrain cannot be modeled as either 2D or 3D because the models fail to account for obstructions to communication and coverage that are caused by the terrain itself. Such “2.5D deployments” require terrain-aware deployment tools and algorithms that are not yet well developed. In this dissertation I present my work on such tools and algorithms.

First, I developed two novel terrain-aware network deployment algorithms. Grid Partition accounts for visibility over 2.5D terrain, but it also improves performance by using elevation as a visibility proxy that vastly reduces the number of more costly visibility computations. The other algorithm, EMNAglobal,steps, improves on EMNAglobal, an estimation-of-distribution algorithm, by computing the covariance matrix of the solution population’s distribution by referencing the mean of the previous generation instead of the mean of the current generation’s mean. Comprehensive experiments show that the proposed algorithms perform as well as or better than traditional optimization meta-heuristics, measured as network sensor coverage. In addition, the core idea behind one of the algorithms, Grid Partition, can serve as a meta-heuristic itself and is used in one of my recoveryalgorithms.

Next, I developed and evaluated a class of terrain-aware network recovery algorithms which guide networks in self-repair following a node failure. Terrain-Aware Recovery with Commshed Intersections (TARCI) consists of four algorithm variants. Experiments show that the variant that incorporates Grid Partition as a meta-heuristic (TARCI-GP) achieves nearly the same quality of results as a variant that includes an exhaustive step while requiring two orders of magnitude less CPU time. In addition, I show that my terrain-aware recovery algorithms perform better than recovery algorithms that are intended for 2Ddeployments.

Finally, to help with the development of my terrain-aware algorithms, I created a terrain-aware experimental framework. The Terrain-Aware Framework For IoT (TAFFI) simulates Java- and C++-based algorithms, both distributed and centralized. The framework provides a library of line-of-sight algorithms and a suite of benchmark terrains. To ensure that the benchmarks include a wide range of landform variation, another contribution of this dissertation is the design of two terrain classifiers that ensure that the benchmark terrains used in the experiments represent a wide variety of terrain landforms.