Defining a problem on Sensor Netowrks.

Recently, small electronic devices were developed with the idea of monitor hostile areas. These devices are provided with several sensors to measure diverse environmental parameters, e.g., temperature, humidity, pressure, soil makeup, noise levels, etc. Due to its nature, these devices are called sensors. And also, the sensors has processing capabilities. Furthermore, they are provided with a radio communication system, using a single shared channel to transmit and receive radio signals. Usually, the capacity of this radio system is small, i.e., the radii of transmission and reception are small with respect to the size of the monitored area. The sensors are designed to be easily and massively deployed in unreachable areas, usually it is assumed that they will be deployed from the air using, for instance, an airplane. Hence, they are tiny enough so that several of them fit in one hand.

The goal is, once the sensors are deployed they start an infitnite communication process among them in order to build a Sensor Network. This communication process is carried out using radio communication, but due to the single shared (transmission or reception) channel, sensors must deal with collisions of transmissions, and when a sensor is transmitting it can not receive any other transmission. Hence, a really special situation is necessary to effectively establish the communication, a node receive a transmission when only one of its possible transmitters (sensors into its reception radius) is transmitting and the rest are in silence. Due to the random nature of the sensors deployment, it is impossible to predetermine anything about the sensors that will be in the transmission (or reception) radius of another sensor. Hence, it is very challenging to determine communication patterns for the sensors, in order to maintain the network, and the communication, during an infinite period of time.

Most of the communication patterns, or protocols, for sensors in sensor networks use randomness to deal with collisions and the lack of information about the network. Randomized protocols are usually fast and resilient to failures, but they frequently rely on redundant transmissions. Given that the most restrictive resource in sensor networks is energy and that the dominating factor in energy consumption is the radio communication, deterministic solutions may yield energy-efficient solutions.

The model.

Sensors are represented by n nodes deployed randomly in R^2, and the Sensor Network by a Geometric Graph using these n nodes, where an undirected edge connect a pair of nodes if and only if they are at an Euclidean distance of at most a parameter r. Given the random deployment of the nodes, we assume that the topology of the network is unknown. Nevertheless, it is assumed that the network is connected and that the maximum degree of any node is bounded by a parameter k < n. Time is assumed to be slotted. In a time slot a node can be transmitting or receiving. The communication among neighboring nodes is through broadcast, i.e., a node transmit to all its neighbors, defined by the graph, at the same time. Finally, nodes are activated adversarially, i.e., nodes are deployed in a sleeping mode, and an adversary decides the activation moment.

Definition 1. If in a given slot exactly one of the adjacent neighbors of a node x transmits, and x it self is not transmitting, we say that there was a clear reception at x in that time slot.

Definition 2. If the node x transmits a message in a given time slot, and no other node within two hops of x transmits in the same time slot, we say that there was a clear transmission for node x.

And now the problem in a Sensor Network.

Problem 1. Given a Sensor Network of n nodes and maximum degree k, where nodes are activated possibly at different times, and upon activation stay active forever, in order to solve the Recurring Reception problem every active node must clearly receive from all of its active neighboring nodes infinitely many times.

Problem 2. Given a Sensor Network of n nodes and maximum degree k, where nodes are activated possibly at different times, and upon activation stay active forever, in order to solve the Recurring Transmission problem every active node must clearly transmit to all of its active neighboring nodes infinitely many times.

Since the post is too long until now, I will let you some weeks to think in possible solutions, or in some equivalent problem previously stated in a different context, maybe combinatorics.

What is a topological invariant?

This note provides a general picture of a classical problem in differential topology and geometry, namely the classification of smooth manifolds. A natural question is: Where do these objects come from? As in many branches of mathematics, physics provides many examples of interesting mathematical objects: the dynamics of mechanical systems involve "spaces" with many degrees of freedom, for example the dynamic of a particle moving under the action of a field of forces. How do we describe this dynamic? The first step is to find a model for all the possible configurations of the particle. This leads to the notion of a manifold. A smooth manifold of dimension d is an abstract topological space which is locally diffeomorphic to R^d . Roughly, a smooth manifold consist of small euclidean pieces glued together by diffeomorphisms. Examples of manifolds are the torus, the sphere and the Klein bottle. This is the image to have, but we should not think of a manifold as always sitting inside a euclidean space, but rather as an abstract object. Indeed, the space of all k-dimensional linear subspaces of a given vector space V has a natural manifold structure, but it is clear that this manifold is not contained in a euclidean space (it is quite a nice exercise to find the local model of this space!). It follows from the definition that two d-dimensional manifolds are locally the same space, but of course they are not necessarily the same global space: the 2-sphere and the 2-torus are not the same global object. How do we know if two manifolds are globally the same space or not? This motivates the problem of finding topological invariants, this means an algebraic data naturally attached to a manifold, where "naturally" means that such a data has to be preserved by homeomorphisms. The first example of a topological invariant is given by the following classification result.

Theorem 1. If M is a compact oriented 2-dimensional manifold then there exists an integer number g such that M is homeomorphic to a 2-sphere with g handles.

We refer to a 2-manifold as a surface. The integer number g is called the genus of a surface. The result above is known as the classification of compact surfaces and it says that every surface is completely determined by its genus. Hence, a 2-sphere is not globally a 2-torus, since the sphere has genus 0 and the torus has genus 1!.

What about higher dimensions?

The philosophy is simple, we need to find invariants. The idea of finding invariants goes back to Poincare and his algebraic study of manifolds. Why algebra? the answer is pretty simple, algebra allows you to make computations, so if we were able to attach an algebraic data to a manifold, then we are in algebra territory, so let us make computations and then translate our computations to a topological language. For example, consider a manifold and let us define its Poincare group: the elements of the group are loops in M identified up to homotopy and the group structure is given by concatenation of loops. This is the fundamental group of a manifold. The fundamental group is an algebraic object with the following property: two manifolds which are globally the same object, then their fundamental groups are necessarily isomorphic. The fundamental group does not classify manifolds since there exist examples of non homeomorphic manifolds with the same fundamental group (the cylinder and the circle). So if our interest in classifying manifolds remains, we need to look for more invariants, more subtle invariants. Classical invariants associated to a manifold are homotopy groups or homology and cohomology groups, but these invariants are not powerful enough to classify smooth manifolds...so...

That's all folks?

Now we bring geometry into the picture! In spite of the fact that we shall reduce even more the type of manifolds to be classified, we consider smooth manifold with extra geometrical structures as: Riemannian manifolds, complex manifolds, algebraic manifolds, symplectic manifolds, or manifolds acted on by a group of symmetries (ie; by a Lie group). The geometrical point of view has shown to be in the right direction.

Theorem 2. (Thurston) There exist just eight different types of 3-dimensional compact smooth manifolds.

The theorem above is known as Thurston geometrization conjecture. It was proved by G. Perelman (Fields medal 2006) using hard geometric-analytical techniques as the theory of geometric flows (Ricci flow and PDEs). In particular the geometrization of 3-manifolds gives a solution to a very famous problem in topology:

Conjecture 1. (Poincare) A compact 3-manifold "without holes" has the topology of the sphere.

In summary, in dimension 2, 3 we have satisfactory answers to the problem of classifying smooth manifolds, but we have not solved our problem at all, for example:

What about dimension 4?

Now we need to improve our techniques and the main idea to solving this question is to bring physics into the picture (notice that 4 is exactly the dimension of the space-time). This leads to the work of S. Donaldson (Fields Medal 1986) and the theory of connections on principal bundles, but we postpone the answer to a future note.