A Step Toward Solving The Mobile Router Conundrum

One of the features of cellphone networks is that the nodes that distribute information are stationary, even though the phones themselves are not. These kinds of networks have been widely studied and do a good job of distributing voice and data in areas where the infrastructure is well structured and tightly controlled, such as in cities in the developed world. But they require two very different types of component: powerful stationary base stations and small mobile phones.

However, another option is to make all the mobile nodes equally responsible for distributing data. So your mobile phone (or laptop or car) would not only send and receive the data your request but route other people’s too. In this case, the network is constantly reforming as the nodes move in and out of contact with each other. The benefit is that the network essentially creates and runs itself. But the challenge is to ensure that each node has the information it needs to efficiently route data.

It’s easy to imagine that mobile ad hoc networks should work well in areas where the density of nodes is high, such as city centres. But what happens in the suburbs, when the density of nodes is much lower? Today, Andrea Clementi and pals at the University of Rome in Italy study just such a type of mobile ad hoc network and prove a surprising result.

The network they study is a “city” filled with nodes that chose a destination at random and then travel to it along simple L-shaped paths. To get to where they want to go, they move along the x-axis and then the y-axis or vice versa, then they chose another destination and so on. This is known as a Manhattan Random Way Point Model because of its similarity to navigating techniques in the Big Apple.

This model naturally leads to a high density of nodes in the city centre but a much lower density in the suburbs. The question that Clementi and co study is how quickly a given piece of information can reach every node in each area, a quantity they call the flooding time.

The flooding time is important because it represents an important limit of the network’s capability. In particular, network engineers need to know if there is an upper bound on the flooding time. If there is no bound, so the flooding time is infinite, it would take forever for the data to flood the network, which is of little practical value.

However, Clementi and co prove that there is an upper bound to the flooding time in the city centre which depends on factors such as the distance each node can transmit. That gives this network a real practical value.

However, the surprise is the flooding time in the suburbs. “A consequence of our result is that flooding over the sparse and highly-disconnected suburb can be as fast as flooding over the dense and connected central zone,” say Clementi and co.

That’s potentially good news for the designers of future generations of mobile networks, particularly those for in-car communications which are likely to require these kinds of networks. However, while the result may hold if you live in Manhattan or somewhere similar, it is by no means general. For the non-city dwellers, more network theory will be needed.

Ref: arxiv.org/abs/1002.3757: Fast Flooding over Manhattan