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

作者：Jeong Myeong Hun^*; Duckham Matt; Kealy Allison; Miller Harvey J; Peisker Andrej

来源：International Journal of Geographical Information Science, 2014, 28(1): 1-21.

DOI：10.1080/13658816.2013.801578

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

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.

• 出版日期2014-1-2