Consider the task of monitoring changes in the structure of dynamic spatial phenomena such as algal blooms or oil spills. Such phenomena consist of multiple disconnected region components, which can reconfigure over time. This work uses qualitative spatial reasoning to record only salient changes to the internal structure of these regions.
To detect and store such qualitative spatial information, this research proposes a collection of five in-network, decentralized algorithms. Unlike previous work, these algorithms are able to operate in networks of mobile geosensor nodes with no access to coordinate information. A decentralized approach to algorithm design allows for information processing to take place within the network, with the defining feature being that no single node has access to the entirety of data in the network.
A fundamental aspect of decentralized algorithms is wireless communication between nodes. As such communication has high power requirements, the algorithms presented in this work are designed to minimize the amount of communication taking place, while still maintaining accuracy. Experimental evaluation of these algorithms found that meeting the criteria of sufficient node density, broadcast interval, and communication distance produced accurate results. These three factors were found to be dependent upon the characteristics of the phenomena being monitored.
It was also found that the modules comprising each of the decentralized algorithms exhibited either sub-polynomial, linear, or weakly polynomial scalability (with the worst case being O(n1.1)). The order of scalability produced by a module was found to be due to the type of decentralized algorithm that module was based on, with leader election based algorithms producing weakly polynomial scalability, and surprise flooding based algorithms producing linear or sub-polynomial scalability.
This work aims to provide long-term environmental monitoring to areas that have previously been unable to be monitored due to their location, the cost of deploying a suitable geosensor network, or the time-span required.