.png){kind=icon}
.png){kind=icon}
Return
Detecting cuts in sensor networks
.png){kind=icon}
OA
AI
DOI：10.1145/1340771.1340776.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We propose a low-overhead scheme for detecting a network partition or cut in a sensor network. Consider a network S of n sensors, modeled as points in a two-dimensional plane. An epsilon-cut, for any 0 < epsilon <, is a linear separation of epsilon n nodes in S from a distinguished node, the base station. Our main result is that, by monitoring the status of just O(1/epsilon) nodes in the network, the base station can detect whenever an epsilon-cut occurs. Furthermore, this detection comes with a deterministic guarantee that every reported cut has size at least epsilon n/2. Besides this combinatorial result, we also propose efficient algorithms for finding the O(1/epsilon) nodes that should act as sentinels, and report on our simulation results, comparing the sentinel algorithm with two natural schemes based on random sampling.
Keywords:
algorithms
security
theory
distributed algorithms
computational geometry
network failure
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4.7
Papers:
995
Citations:
2.0K
View more organizations