Bio-Inspired Self Organizing Networks (BISON) Algorithm for Blanket Coverage in Unknown Indoor Environments

Student thesis: Master's Thesis

Abstract

Wireless sensor networks (WSN) emerge at the center of the fast expanding Internet of Things (IoT) revolution. Hence, increased research efforts are being directed toward its efficient deployment, optimization and adaptive operation. Rapid deployment of WSN in an unknown, obstacle-rich and noisy environment is a critical challenge that involves finding optimal locations for the network nodes. This in turn helps in delivering optimally balanced sensing and communication services at the maximum possible coverage, subject to complex mutual constraints. The three stages of WSN implementation (deployment, optimization and adaptive operation) represent complex multi-parametric problems that are naturally suited for bio-inspired optimization techniques, known for delivering complex emergent self-organization behaviour based on very simple autonomous local interactions. Inspired by the behaviour of a group of animals roaming through the environment, we explored the possibility of harnessing the formalized mechanics of this emergent behaviour based on Voronoi centroid tessellation for rapid deployment of WSN in any unknown environment. Specifically, this dissertation addresses the challenge of autonomous self-deployment of WSN in any two-dimensional bounded target space of unknown geometry and topology. To achieve this goal, we have developed a working simulation prototype of such auto-deployment based on the adapted variant of Voronoi-based algorithm, termed Bio-Inspired Self-Organizing Network (BISON). The proposed method assumes entering the target space from the selected inlet (ex: doors), and triggering the sequential controlled and optimized release of vehicle or drone carried WSN nodes, which autonomously spread and connect throughout the space to rapidly form a blanket coverage network ready for delivering variety of sensing, monitoring or communication services. The sensor nodes autonomously move toward their range-dependent, partially observable Voronoi cells' centers, maintaining a stable collision-free flow designed to rapidly explore and cover the whole target space at the minimum possible time, using as few nodes as possible and draining as little energy as possible, all that without any prior knowledge about the geometry of the space and the obstacles. BISON is designed to automatically expand and rapidly converge towards uniformly distributed maximum coverage stabled locations that can be used as a blueprint of the optimized fixed solution, temporarily utilized and automatically decommissioned or adaptively evolved along the dynamically changing environment with the self-healing functions implementing the basic Artificial Intelligence (AI) characteristics. BISON performance and various functionalities are thoroughly evaluated in terms of the target space coverage, number of nodes utilized for deployment, deployment energy expenditure proxy-measured by the total distance travelled, and the uniformity and stability attained in a converged network. The model was also exposed to simulated sensing uncertainty and evaluated within a variety of simulated environments that contain various internal structures, different obstacle shapes and scattered objects' distributions, yielding vital conclusions related to the dynamics of automated decentralized space exploration while ensuring BISON's broad applicability and noise resilience necessary in the absence of any prior knowledge about the target space it is tasked to explore, cover and build network in. Extensive set of simulated deployment experiments demonstrate convergence to the stable near-full coverage network, achieved at a fraction of a deployment cost and time, compared to competitive models reported in the literature, which allow to consider BISON as a strong new approach to AI-flavoured blanket-coverage WSN deployment achieved virtually without any human intervention. In an attempt to further improve, simplify and generalize BISON deployment, various model changes and algorithmic simplifications have been explored. The core BISON algorithm has been merged with the localized Genetic Algorithm (GA) applied to push the trade-off between the pace of space exploration and the energy expense further towards faster deployments, especially when faced with complex obstruction structures. Finally, we further contributed to the effect of noise on the variations of the performance among BISON approaches through analysing the noise coherence on the collective motion of the nodes, and performing temporal network analysis to discuss the variations in the connections at different environments.
Date of AwardSep 2019
Original languageAmerican English

Keywords

  • Self-deployment Network
  • Voronoi-based Algorithm
  • WSN Coverage Optimization
  • Energy Consumption
  • Obstacles Avoidance
  • Noise Coherence
  • Temporal Network Graphs.

Cite this

'