Sensor Network Configuration and the Curse of Dimensionality

Abstract

Sensor network problems in three dimensions have not been adequately addressed- there is a tendency to either ignore the extension of algorithms from two dimensions (2D) to three dimensions (3D) for simplicity or believe that it is straightforward. We draw examples from well known problems in geometry and argue that this step needs special investigation- while some properties of networks in 2D directly generalize to 3D, many require additional computational complexity, and a few do not generalize at all. This paper focuses on the problem of deployment and configuration of sensor networks in 3D, draws attention to the fundamental difficulties involved, and presents a set of local geometric rules that can be used to construct efficient network topologies in 3D. 1.