Overview

Sensor network problems in three dimensions have not been adequately analyzed - there is a tendency to either ignore the extension of algorithms from two dimensions (2D) to three dimensions (3D) or believe that it is straightforward. We have studied some 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. In particular, we have focused on the problem of deployment and configuration of sensor networks in 3D. We have also launched a preliminary study of network localization using distributed optimization particularly tailored to the needs of future tiered architectures (e.g. Tenet). Specifically, we propose a mathematical optimization-based framework for localization based on proximity constraints. Most variants of localization can be cast into this framework depending on the kinds of input available (e.g. ranging). We show accurate results, and exploit a technique from distributed optimization to divide the problem into pieces suitable for computation at the master-level nodes. We believe this is likely to be applicable to other problems such as power-aware routing.

Approach

We reviewed a number of deployment and configuration techniques in 2D and in a recent paper have highlighted the nature of the difficulty involved in extending them to 3D. These insights will be of value to stimulate research into new and appropriate techniques. We have shown that controlled deployment is one particularly attractive technique to construct efficient networks in 3D. In order to achieve this in a distributed manner, we investigated local geometric rules that can guarantee global coverage and connectivity properties. We have demonstrated an algorithm that finds the largest empty solid angle subtended by a node’s neighbors. This can be used as a primitive for extending several topology control algorithms that use directional information. Finally, we have tested our proximity-based tiered localization algorithm in simulated networks and verified its functionality. We wanted to demonstrate that intensive computation at the master nodes, coupled with extremely simple data collection at sensor nodes, produces data fusion performance comparable to systems where the sensor nodes have been outfitted with specialized sensing hardware, or carefully configured, yet have access to relatively poor computational resources. Also we asked if there are convenient and efficient ways to distribute and manage computation across the master nodes in a tiered network.

Systems/Experiments

Controlled deployments are feasible when positions of individual nodes can be altered - either by the nodes themselves or by an external agent. The control on position can be exploited to construct efficient network topologies. Local geometric conditions that can influence global coverage and connectivity properties are key to achieving this. To this end, we explored two families of topologies, proximity graphs (such as RNG, GG) and tiling structures that possess desirable global properties. For the purpose of analysis we assume a binary disc communication model and sensing model for the nodes. It must be emphasized here that such analysis only provides broad guidelines. Any algorithm design must account for irregular communication range, etc. Proximity graphs such as the Relative Neighborhood Graph (RNG), Gabriel Graph (GG) and Delaunay Graph (DelG) are guaranteed to be connected and have other useful properties. They have been extensively used for topology control, routing, etc. We have established sufficient conditions for the communication graph to contain each of RNG, GG, and DelG. The analysis is non-trivial because the edge-lengths in communication graphs are restricted by the communication range of nodes, while in proximity graphs they depend only on the relative positions of nodes and very long edges are possible. Without giving the mathematical details we summarize the key findings which are that it is possible to give bound on the size of the largest cone around a node which much contain at least one network neighbor in order for the network graph to be a supergraph of a GG or an RNG. These local conditions can be integrated with node placement to construct efficient topologies. A key requirement is an algorithm to check for empty cones larger than a given angle. This is non-trivial in 3D because there does not exist a natural “order” of neighbors. We have proposed an algorithm for finding the largest empty cone around a given node.

For proximity-based localization we model each connectivity constraint as an inequality. We formulate the optimization problem as an unconstrained minimization. In such a formulation, each neighbor constraint contributes a cost and each non-neighbor constraint contributes a cost term. We minimize the total cost. An intelligent choice of a subset of these constraints could reduce the computational load significantly while preserving accuracy. We exploit this in the distributed version of the optimization. In the formulation, each new node added to the network adds N constraints. Hence, the number of constraints scales as N 2. Assume now, that there are k master-class nodes in the network. The network is divided into k partitions, each roughly containing N/k 2 nodes. Now, each such node has (N/k) 2 constraints. This is a significant reduction in workload and also forms a tradeoff between the number of master-class nodes deployed and the computational load on each of them. Using distributed optimization we solved the resulting systems. The figure shows localization error as the system converges.

Figure 1: Localization error vs. Iteration: Localization error in distance vs. the number of iterations for which the optimization ran.

Accomplishments

By generalizing the value of theta, a family of graphs can be defined. We call these Neighbor-Every-Theta (NET) graphs that have the property that each node in the network has at least one neighbor in every specified angle cone of its communication range. We believe that NET graphs can provide a range of coverage and connectivity tradeoffs for varying values of angle. We have presented a framework for low-level services in sensor networks based on the idea that one can tradeoff computation to achieve accuracy in tiered networks. We showed a simple proof-of-concept proximity-based localization study, and argued how we can extend it readily to other kinds of localization, as well as other services such as power-aware routing.

Future Directions

In the first problem – that of using local geometry to make control decisions for connectivity and coverage – we plan to investigate cases more closely aligned with real network behavior ie. less idealized. In the second problem, we plan to implement and study a functional version of our algorithm (in general, the distributed optimization setup) in Tenet.

People

Students: Sameera Poduri and Karthik Dantu

Faculty: Gaurav S. Sukhatme

Non-CENS collaborators: Sundeep Pattem and Bhaskar Krishnamachari