The mathematics of joining dots is helping create more robust communication networks, says S.Ananthanarayanan.

Having many paths of connections between points in a network makes both for faster communication as well as stability when some of the paths get blocked or crowded. Networks that arise and grow with high interconnectedness, like the biological networks or social networks are found to provide for ample alternate paths of communication, which minimize the chances of the network coming down, even when natural conditions change or people move, and so on. The Internet is one such well connected and stable network that has come to stay.

But there is now a new entity, the wireless networks, where devices set up and dismantle ‘ad hoc’ networks ‘on the fly’. Instances are of emergency responders fanning through a burning building or devices placed on the slopes of a volcano to monitor activity or robots sent out to look for leaks in an oil rig, or for explosives in a minefield. In the case of the Internet, there are fixed routers that channel traffic, and the routers are monitored by service providers, to respond to congestion. Similarly, mobile phone users speak not to each other but to cell towers and base stations, which are fixed. But in an ad hoc network, all devices are participants in the working of the network and each one needs to sense the others and collectively ensure that vital information passes intact and in time. Researchers at MIT’s Computer Science and Artificial Intelligence Lab, the Israel Institute of Technology at Haifa and the University of Freiburg, Germany, are to present a new approach to the special problems that arise in ad hoc networks at a forthcoming symposium of the industry.

Special problemsA feature of ad hoc networks is that that the quality of links within the network fluctuates rapidly. Routing strategies, of sending more or less information through alternate paths of communication, need to be changed often to keep the network going. As responders in the network change position, they could pull further apart, with drop in the bandwidth of communication channels, or links could be broken or new ones formed. In the adverse conditions where these networks are deployed, some sensors could be destroyed altogether.

The bandwidth and power that the sensors have at their disposal is a relevant factor. If sensors could send data to each other without limit, for instance, the distance between them may not matter. The time for which the sensors can work without a battery recharge is another factor. This may be in hours for robots at oil rigs or in months in the case of sensors placed in a volcano. These are the factors that set apart the problems and solutions in ad hoc networks, as opposed to the Internet or a cell phone network.

GraphsThe way the question of connections between places in a network has been abstracted is with a field of mathematics known as graph theory. The word, graph, in this context is just a collection of points, which represent objects, connected by links, which represent the relationship between the objects. Each point may be connected to one or more than one other point. The points are called nodes and the connections are called edges.

Graph theory looks at the connectivity, or the number of links in a network, so that there are alternative paths, shorter and longer paths, the speed or efficiency of a path which affect the throughput. Throughput may be measured in quantity of information, in a communication network, or of the number of trains, in a railway network, or of microbes in a network that spreads an infectious disease, by the number of citations of research papers, and so on. Specification of the network hence consists of identifying the nodes, and describing the links between adjacent or connected nodes in terms of the time the links take, the quantity they can carry, or the cost or other factors. For instance, in a transport network, there could be a cheaper, but slower route and also a faster, but expensive route, via an expressway that charges a toll, but where heavy loads are not allowed. Real life networks can have thousands of nodes and proportionate numbers of edges and optimization becomes a fertile ground for computers.

Computer algorithms, that is to say, methods of manipulating data, have been devised to start from the basic node and edge description and to arrive at a strategy to transfer either from and to any node, or one or more specified nodes, information, people, cargo, etc, in the fastest or cheapest or safest, means possible, with alternatives when a particular node or edge gets congested or defective, etc. One idea that is used is of the spanning tree, or a path through the network which touches all the nodes. It is easy to see that there may be many spanning trees in a given network. The next concept is of the minimum spanning tree, or the tree that has the least length, or cost, etc. For a cable company laying the cable to cover all houses in an area, for instance, the interest could be to use the least length of cable, but this may not be the cheapest solution if the shortest path involved a portion where the cable had to be buried deeper or specially shielded, etc. The ideal layout may even depend on the bandwidth required at different nodes.

Another concept is of the edge-disjoint spanning trees, or alternate trees that do not share any edges. Such trees are true alternate paths and can become simultaneous or parallel channels, so that the total throughput is multiplied and the network is safe even if there are failures of links.

Ad hoc networksThe networks of interest so far have been of the kind that have a good number of nodes which are very rich in connection to other nodes. These nodes are called hubs and this structure makes for lesser numbers of nodes which have more connections. The result is a network with more nodes with less connections, and hence the greater chance that a failure will occur at such nodes. The stability of the graph in any case depends on both the number of nodes, or vertices, and the number of edges, or links, which need to be removed before stability is affected. And there has been much work on the subject, with the emphasis on the egde connectivity, rather than the vertex connectivity.

Later this month, MIT graduate student Moshen Ghaffari is to present the work of his team, which includes Keren Censor-Hillel, Israel and Fabian Kuhn, Germany. The new work addresses the properties of vertex connectivity in a manner similar to the work on edge connectivity. The team broke up the network into groups of vertices which have the property that each vertex is connected to all the others in the group and at least one of them is adjacent to a node outside the group. This property allows information to flow within the group and also connection outside the group, which is called a connected dominating set. Just like a graph is known to contain almost as many edge-disjoint spanning trees as edge connectivity, “each graph contains almost as many vertex-disjoint connected dominating sets as its vertex connectivity,” Ghaffari says. “So if you think of an application like broadcasting information through a network, we can now decompose the network into many groups, each being one connected dominating set," he says. "Each of these groups is then going to be responsible for broadcasting some set of the messages, and all groups work in parallel to broadcast all the messages fast — almost as fast as possible.”

As connections and spanning trees are variable in ad hoc networks, breaking the network into groups of nodes is the way to optimize performance in these applications. It would also help analyse the effects of node failures, as against edge failures.