Geometric Chemotaxis: A Biologically-Inspired Framework for a Class of Wireless Coverage Problems
H.Ozgur Sanli, Rahul Simha, Bhagi Narahari
We present a new, biologically-inspired algorithm for the problem of covering a given region with wireless “units ”(sensors or base-stations). The general problem, framed mathematically as the problem of covering a polygon with a minimum number of circles, is applicable both to sensor networks in which the units are sensors with known sensing range and to wireless networks in which the units are base stations that have a known transmission range. While past work has considered the problem of locating a given number of units, we consider the joint problem of both determining the optimal number as well as locating them. Our approach to solving the problem invokes a new biological metaphor in algorithm design, chemotaxis, that is different from other biology-inspired algorithms such as neural networks or genetic algorithms. In this metaphor, the wireless units are treated as food-seeking organisms that coalesce around nutrient sources and thereby cover a region; by carefully selecting the geometry of these nutrient sources and their distribution, we show that it is possible to control the chemotactic process to efficiently provide overall coverage. We also consider the additional problem of coverage in the presence of obstacles such as indoor walls that attenuate transmission.