Friday, March 21, 2003

Capacity of Ad Hoc Wireless Networks 8:37:48 PM • • comment [] • Google It! Ad-hoc wireless networks (AHWN) are digital communication networks built from a set of small, independent, wireless devices. Unlike more "traditional" wireless networks, in which end devices communicate with some type of a fixed server, in AHWNs end devices talk to each other directly. As devices move from one place to another, or communication patterns change, connections between devices are changed accordingly, thus the "ad-hoc" aspect. By their nature, AHWNs do not require a centralized architecture, and all devices on the network can be regarded on equal footing. In principle, this means that the entire population of a large geographical region can be equipped with such devices, and never pay their local service provider to communicate. If device A wants to talk with device B, it can do so directly provided they are close enough. What if the two devices are two far apart? Here comes the "neat" part: The devices talk to other device which are close enough, thus establishing a multi-hop route between them. In terms of routability, it's just like how the Internet works (a message starting from end device A travels through multiple routers until it reaches end device B), except that each end device can also act as a router, the routes are ad-hoc, and no-one needs to pay any bills. If it's so good, why don't we all dump our Internet providers tomorrow? Well, some people think this is exactly how the future looks like. They lobby quite regularly for their position these days. Personally, I have quite a few reservations about this sort of "free-lunch" architecture. An interesting paper I read today provides some practical evidence (as opposed to theoretical arguments) that such networks -- while they might work perfectly for local regions -- do not scale to Internet sizes. In their paper Capacity of Ad Hoc Wireless Networks (which is recommended reading to anyone interested in the subject), the authors conclude: [...] We find that, in general, 802.11 does a reasonable job of scheduling packet transmissions in ad hoc networks. 802.11 is more efficient for orderly local traffic patterns, such as a lattice network with only horizontal flows. 802.11 is also able to approach the theoretical maximum capacity of O(1/sqrt(n)) per node in a large random network of n nodes with random traffic. We argue that the key factor deciding whether large ad hoc networks are feasible is the locality of traffic. We present specific criteria to distinguish traffic patterns that allow scalable capacity from those that do not. [Li, Blake, De Couto, Lee, and Morris; Capacity of Ad Hoc Wireless Networks]

© Copyright 2003 Ziv Caspi.