Topology in Sensor Networks

This thesis discuss the application of techniques from computational topology to wireless sensor networks. Wireless sensor networks are systems which consist of small, resource constrained "motes" embedded in the physical world. The motes can then collect data about the environment such as light, humidity, temperature, etc. There are many different types of sensor networks, depending on the type of sensor used. We mainly consider static sensors measuring scalar values with motes primarily constrained by energy consumption. Topology is a branch of mathematics which studies how spaces are connected and attempts to classify their global structure based on this. In large, particularly ad-hoc deployments, motes do not know their own locations. However, they do have proximity information in the form of wireless links. Topology needs only proximity information, making it well suited for sensor networks. The first part of this thesis will discuss a topological sweep where coarse global knowledge is used to impose a topological structure on the network. This structure is called a potential field and is built by solving Laplace's equation with Dirichlet boundary conditions. The choice of boundary conditions is done by choosing a small subset of the network which are called boundary nodes, as they are usually chosen to be on the physical boundary of the network. Once the boundary nodes have been chosen, the potential field can be built using only local information. The potential field can be used to perform network-wide operations such as data-aggregation and dissemination efficiently using a sweep on the potential field. The potential field acts as a guide for the sweep and because of its properties as a harmonic function, correctness of the sweep can be shown. The second part discusses how a qualitative description of data in a sensor network can be computed. In particular, we use compute a homological description of the sub-level sets. This gives an indication as to how many siginficant peaks there exist in a sensor field. This problem has been well studied when location information is available such as in GIS systems. As sensor networks do not usually have this information, this work shows that it is possible to get a provable approximation of the persistence of the peaks using only proximity information by computing the image persistence of two nested Vietoris-Rips complexes. Finally, we discuss how the toplogical invariant of homology can be computed distributedly in a sensor network. We first give an algorithm for general complexes, which mimics reduction via Gaussian Elimination of the boundary matrix in the network. We compare this to another method based on Hodge theory and show that in practice our algorithm requires less communication. Then we give an algorithm which is restricted to important special case of the plane, but is much more efficient than the general algorithms and performs within a log-factor of the optimal centralized algorithm. It works by computing a hierechical decomposition of the sensor network. Homology is then computed in a top-down manner along the decomposition through refinement. The most important aspect of this algorithm is that after a coarse global computation, all further homology computations are localized, leading to an algorithm well suited to sensor networks.