In recent years, many network scientists have turned their attention away from centralized networks — such as the Internet and the cell-phone network — and toward ad hoc networks, wireless networks formed on the fly by, say, emergency responders fanning through a burning building, tiny sensors scattered on the slopes of a volcano to monitor its activity, or autonomous robots exploring a forbidding environment. “The problems are very tantalizing, they’re exciting to work on and they have an interesting mathematical structure,” says Nancy Lynch, NEC Professor of Software Science and Engineering. “All of traditional distributed-computing theory deals with wired-network algorithms, so those communication protocols have been studied for many years.”
In the Internet, the responsibility for directing data traffic lies with special-purpose devices called routers. Internet service providers monitor the flow of traffic across their networks and, if they spot congestion, revise the routers’ instructions accordingly. With the cell network, two people a block apart could be having a phone conversation, but they aren’t directly exchanging data. Rather, they’re sending data to a cell tower that determines what to do with it — as it does for thousands of other cell-phone users in the vicinity. “If everything could be run by some node that’s on the Internet, that’s maybe a solved problem, kind of boring,” Lynch says. “The base station just computes everything and tells everybody what to do.”
In an ad hoc network, there are no base stations, and there are no supervisors monitoring network performance as a whole. A sensor dropped on the side of a volcano powers on and tries to determine how many other active sensors are within communication range. Together, the sensors then piece together whatever information they need to perform their collective task.
Another common feature of ad hoc networks is that they’re constantly changing. The wind blows — or the lava flows — and suddenly some of the volcano sensors are farther away from their neighbors, with lower-bandwidth data connections than they had before; or perhaps some of the connections have been broken entirely, while new ones have been formed; or perhaps some of the sensors have been destroyed outright. The problem of changing network topology is even more acute for, say, robots crawling all over an underwater oil rig looking for leaks, or sensor-laden cars exchanging data about traffic conditions as they weave among each other on a busy state highway.
If the devices in an ad hoc network had unlimited power, it would be relatively easy for them to accommodate changing topologies: any one device could send as much data as it needed to any other, regardless of the distance separating them. But for many of the envisioned applications of ad hoc networking, power is at a premium. The oil-rig robots might need to operate for hours between battery charges, the volcano sensors for years. The need to maximize the efficiency of data exchange — in order to minimize energy consumption — makes designing communications protocols for ad hoc networks even more challenging.
As handheld devices become more and more powerful, the prospect that they could arrange themselves into ad hoc networks also becomes more intriguing. MIT professor of electrical engineering Muriel Médard has investigated whether ad hoc networking could abet the dissemination of information among large localized groups. Médard imagines, for instance, that the cell phones of fans at a sporting event could organize into ad hoc networks to enable very efficient distribution of video data, so that thousands of people could simultaneously watch high-quality replays of entirely different plays without overburdening the local data networks. Lynch says that her group had toyed with the idea of a “HikerNet,” which would allow hikers without cell service to exchange information about trail conditions, and that other researchers have investigated multiplayer games that would use direct connections between cell phones. She also points to the failure of the cellular network in New Orleans after Hurricane Katrina as an instance in which ad hoc networking could have been useful.
“Everything was knocked out,” she says. “You had everybody with their devices, but they couldn’t use them. These devices are capable of communicating with other nearby devices, so they’re capable of conveying information across an entire ad hoc network. But there was no ad hoc network set up. There was no software to do that.” The “killer app” that would persuade people to open up their phones to direct transmissions from their neighbors may not have emerged yet. But the enthusiasm greeting Apple’s announcement that future versions of the iPhone might be able to serve as wireless base stations suggests that the idea could have market potential.
In the Internet, the responsibility for directing data traffic lies with special-purpose devices called routers. Internet service providers monitor the flow of traffic across their networks and, if they spot congestion, revise the routers’ instructions accordingly. With the cell network, two people a block apart could be having a phone conversation, but they aren’t directly exchanging data. Rather, they’re sending data to a cell tower that determines what to do with it — as it does for thousands of other cell-phone users in the vicinity. “If everything could be run by some node that’s on the Internet, that’s maybe a solved problem, kind of boring,” Lynch says. “The base station just computes everything and tells everybody what to do.”
In an ad hoc network, there are no base stations, and there are no supervisors monitoring network performance as a whole. A sensor dropped on the side of a volcano powers on and tries to determine how many other active sensors are within communication range. Together, the sensors then piece together whatever information they need to perform their collective task.
Another common feature of ad hoc networks is that they’re constantly changing. The wind blows — or the lava flows — and suddenly some of the volcano sensors are farther away from their neighbors, with lower-bandwidth data connections than they had before; or perhaps some of the connections have been broken entirely, while new ones have been formed; or perhaps some of the sensors have been destroyed outright. The problem of changing network topology is even more acute for, say, robots crawling all over an underwater oil rig looking for leaks, or sensor-laden cars exchanging data about traffic conditions as they weave among each other on a busy state highway.
If the devices in an ad hoc network had unlimited power, it would be relatively easy for them to accommodate changing topologies: any one device could send as much data as it needed to any other, regardless of the distance separating them. But for many of the envisioned applications of ad hoc networking, power is at a premium. The oil-rig robots might need to operate for hours between battery charges, the volcano sensors for years. The need to maximize the efficiency of data exchange — in order to minimize energy consumption — makes designing communications protocols for ad hoc networks even more challenging.
As handheld devices become more and more powerful, the prospect that they could arrange themselves into ad hoc networks also becomes more intriguing. MIT professor of electrical engineering Muriel Médard has investigated whether ad hoc networking could abet the dissemination of information among large localized groups. Médard imagines, for instance, that the cell phones of fans at a sporting event could organize into ad hoc networks to enable very efficient distribution of video data, so that thousands of people could simultaneously watch high-quality replays of entirely different plays without overburdening the local data networks. Lynch says that her group had toyed with the idea of a “HikerNet,” which would allow hikers without cell service to exchange information about trail conditions, and that other researchers have investigated multiplayer games that would use direct connections between cell phones. She also points to the failure of the cellular network in New Orleans after Hurricane Katrina as an instance in which ad hoc networking could have been useful.
“Everything was knocked out,” she says. “You had everybody with their devices, but they couldn’t use them. These devices are capable of communicating with other nearby devices, so they’re capable of conveying information across an entire ad hoc network. But there was no ad hoc network set up. There was no software to do that.” The “killer app” that would persuade people to open up their phones to direct transmissions from their neighbors may not have emerged yet. But the enthusiasm greeting Apple’s announcement that future versions of the iPhone might be able to serve as wireless base stations suggests that the idea could have market potential.
