Detecting cuts in sensor networks

doi:10.1145/1340771.1340776

Detecting cuts in sensor networks

2008-04-08

18

OA

AI

N

Nisheeth Shrivastava *

DOI：10.1145/1340771.1340776

原文链接

查看原文

摘要

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.

Keyword:

algorithms

security

theory

distributed algorithms

computational geometry

network failure

Detecting cuts in sensor networks

摘要

AI总结

期刊

机构