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

Uh oh–you've read all five of your free articles for this month.

Insider Premium

$179.95/yr US PRICE

Want more award-winning journalism? Subscribe to Insider Plus.

  • Insider Plus {! insider.prices.plus !}*

    {! insider.display.menuOptionsLabel !}

    Everything included in Insider Basic, plus ad-free web experience, select discounts to partner offerings and MIT Technology Review events

    See details+

    What's Included

    Bimonthly home delivery and unlimited 24/7 access to MIT Technology Review’s website.

    The Download. Our daily newsletter of what's important in technology and innovation.

    Access to the Magazine archive. Over 24,000 articles going back to 1899 at your fingertips.

    Special Discounts to select partner offerings

    Discount to MIT Technology Review events

    Ad-free web experience

You've read of free articles this month.