We noticed you're browsing in private or incognito mode.

To continue reading this article, please exit incognito mode or log in.

Not a subscriber? Subscribe now for unlimited access to online articles.

Emerging Technology from the arXiv

A View from Emerging Technology from the arXiv

A Step Toward Solving The Mobile Router Conundrum

A new mathematical model shows how the changing web of links between mobile phones could one day form an autonomous network.

  • February 23, 2010

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

Become an MIT Technology Review Insider for in-depth analysis and unparalleled perspective.

Subscribe today
Want more award-winning journalism? Subscribe to All Access Digital.
  • All Access Digital {! insider.prices.digital !}*

    {! insider.display.menuOptionsLabel !}

    The digital magazine, plus unlimited site access, our online archive, and The Download delivered to your email in-box each weekday.

    See details+

    12-month subscription

    Unlimited access to all our daily online news and feature stories

    Digital magazine (6 bi-monthly issues)

    Access to entire PDF magazine archive dating back to 1899

    The Download: newsletter delivery each weekday to your inbox

You've read of three free articles this month. for unlimited online access. You've read of three free articles this month. for unlimited online access. This is your last free article this month. for unlimited online access. You've read all your free articles this month. for unlimited online access. You've read of three free articles this month. for more, or for unlimited online access. for two more free articles, or for unlimited online access.