Decentralized and coordinate-free computation of critical points and surface networks in a discretized scalar field

Abstract

This article provides a decentralized and coordinate-free algorithm, called decentralized gradient field (DGraF), to identify critical points (peaks, pits, and passes) and the topological structure of the surface network connecting those critical points. Algorithms that can operate in the network without centralized control and without coordinates are important in emerging resource-constrained spatial computing environments, in particular geosensor networks. Our approach accounts for the discrepancies between finite granularity sensor data and the underlying continuous field, ignored by previous work. Empirical evaluation shows that our DGraF algorithm can improve the accuracy of critical points identification when compared with the current state-of-the-art decentralized algorithm and matches the accuracy of a centralized algorithm for peaks and pits. The DGraF algorithm is efficient, requiring O(n) overall communication complexity, where n is the number of nodes in the geosensor network. Further, empirical investigations of our algorithm across a range of simulations demonstrate improved load balance of DGraF when compared with an existing decentralized algorithm. Our investigation highlights a number of important issues for future research on the detection of holes and the monitoring of dynamic events in a field.

Keywords:

• geosensor network
• decentralized spatial computing
• surface networks
• critical points
• discrete Morse theory

Acknowledgments

The authors would like to thank the three anonymous reviewers for their insightful and thorough comments, leading to a range of improvements to this article. Matt Duckham’s work is supported by funding from the Australian Research Council (ARC) under the Discovery Projects Scheme, grant numbers DP120103758 and DP120100072. Allison Kealy’s work is supported by funding from the ARC, project DP120100072.