Name
Abstract | ||
|---|---|---|
The capability to query the topology of spatial regions is fundamental to today's centralized spatial computing systems, like spatial databases and GIS. By contrast, this paper explores decentralized algorithms for computing the topology of spatial regions in wireless sensor networks. The approach generates global topological information about regions, using only the local knowledge of nodes and their immediate network neighbors aggregated up through spatial boundary structures. Using three basic boundary structures (boundary nodes, boundary cycles, and boundary orientation), a family of decentralized algorithms is defined that can respond efficiently to snapshot queries about the topology of spatial regions, including containment and adjacency queries. The communication complexity of the algorithm is O(n) for realistic inputs. Empirical investigation of the performance of the approach, using simulation, also confirms the efficiency, scalability, and robustness of this approach. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/TC.2010.177 | IEEE Trans. Computers |
Keywords | Field | DocType |
decentralized computation,spatial region,spatial boundary structure,boundary cycle,basic boundary structure,spatial databases,spatial regions,centralized spatial computing system,decentralized algorithm,boundary node,adjacency query,boundary orientation,face,spatial database,adjacency,local knowledge,communication complexity,geographic information systems,topology,construction industry,wireless sensor networks,algorithm design and analysis,algorithm design,wireless sensor network,containment,computational complexity,lead | Adjacency list,Geographic information system,Topology,Algorithm design,Computer science,Theoretical computer science,Communication complexity,Robustness (computer science),Wireless sensor network,Computational complexity theory,Scalability,Distributed computing | Journal |
Volume | Issue | ISSN |
60 | 8 | 0018-9340 |
Citations | PageRank | References |
4 | 0.42 | 34 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Matt Duckham | 1 | 962 | 62.78 |
| Doron Nussbaum | 2 | 89 | 13.49 |
| Jorg-Rudiger Sack | 3 | 126 | 8.44 |
| Nicola Santoro | 4 | 16 | 4.89 |