Shortcuts
lighten wireless load
By
Kimberly Patch,
Technology Research NewsMost people have a computer frustration story that involves spending an inordinate amount of time finding a file stored on a hard drive.
Connect computers into large networks, and finding a given computer within the network becomes a similar logistical problem. And when those computers are mobile devices like laptops, PDAs and wireless sensors that wander in and out of networks, locating a specific device gets trickier still.
A researcher from the University of Southern California has found that adding a few well-placed links, or connections between devices in an ad hoc mobile network is an efficient way to make it easier to locate a given device. The tricky part, however, is knowing where to add the links. To do this, the researcher turned the mobility liability into an advantage.
In a small network it's easy to find a given computer -- just send a message to every computer and the right one will respond. This is akin to raising your voice in a room of people who you don't know by sight to get the one among them named Karen to respond. This method quickly becomes inefficient, however, as the size of the network or room full of people who want to talk to each other grows.
Current approaches to locating specific computers on wireless networks tend to be hierarchical. Networks are divided into clusters of devices, and each cluster appoints a cluster-head to be responsible for communications between clusters.
In mobile networks, however, if a cluster-head moves out of range, the cluster must reconfigure and appoint another cluster-head. Unfortunately, this scenario tends to happen often, which increases the network's communications and power use, according to Ahmed Helmy, an assistant professor of electrical engineering at the University of Southern California.
To address this problem, Helmy turned to the small-world, or six-degrees-of-separation, concept.
The concept was first uncovered in 1967 when sociologist Stanley Milgram found that it took an average of only six exchanges, or hops, between people and their acquaintances for a letter to find its way from a person in Omaha, Nebraska to a Boston recipient the original sender did not know.
It took more than three decades for researchers to explain Milgram's empirical evidence mathematically. Columbia University researchers showed earlier this year that in terms of communications, network devices -- as well as people in social networks -- tend to aggregate into groups, and any given node or person tends to be a member of several groups that don't necessarily overlap much. Individuals or devices that span different groups -- like a soccer mom who is also a classical musician -- provide shortcuts between those groups.
Helmy's idea was to introduce extra shortcuts into mobile networks to cut down the number of fellow devices a given mobile computer passed messages through in order to find another computer on the network. The idea "was to use the concept of shortcuts in order to discover resources in ad hoc and sensor networks," he said.
Helmy divided up the mobile network into zones where every node is aware of a few other nodes within its general vicinity. Then he introduced shortcuts, or contacts that extended beyond a node's zone.
Through a series of experiments he found that adding a relatively small number of links reduced the average degrees of separation, or path length, significantly. "In a network of 1,000 nodes and around 5,000 links, adding 25 to 150 links achieves 40 to 60 percent reduction in path length," Helmy said.
The degrees of separation equates to the number of search queries that are needed to find a given device on the network. "Reducing... degrees of separation leads to reduction in resource discovery overhead," said Helmy.
One of the challenges to doing this in mobile networks, however, is that it would be "a continuous process to create and maintain shortcuts, because the nodes continuously move," he said.
Helmy found that the most efficient data links were those that connected areas that spanned 25 to 40 percent of the maximum distance of the network. "I was able to show... that shortcuts need not be of maximal distance. They may be a very manageable and predictable distance, and still achieve the maximum reduction in degrees of separation," he said.
For mobile networks, the question is how to choose shortcuts that span this desirable distance range.
The second part of Helmy's idea was to use the nodes' mobility to create shortcuts of the desirable length.
The network nodes choose potential shortcut nodes from those they already keep track of in their own zones, which is the closest 5 to 10 percent of the network. The nodes then keep track of these former neighbors as they move away from the node's zone, and promote them into shortcuts if and when they reach a place that is somewhere between 25 to 40 percent of the total network distance away, said Helmy. This is akin to keeping track of neighbors who move out of town as a way of collecting contacts in far-off places.
Helmy's experiments showed that it is possible to efficiently track zone neighbors that are likely to move -- and remain for some time -- a desirable distance away. "Mobility can and should be utilized to increase the network view" of a given node, said Helmy.
Using mobility properties of neighboring nodes to select them as future out-of-area contacts is "quite clever," said Leonard Miller, an electronics engineer at the National Institute of Standards and Technology (NIST).
The work is "the first practical examination of the small world... phenomenon that I have seen which applies to wireless terminals," said Miller.
The concepts could eventually be applied to self-configuring wireless ad hoc communication and sensor networks useful for "responding to emergencies and arbitrary situations or... mass deployment of low-cost sensors," he said.
The work is applicable to infrastructure-less wireless mobile networks that must be quickly put together, and networks of sensors, said Helmy. "There are various emerging classes of applications especially in the areas of search and rescue, vehicular networks, habitat and environmental monitoring, remote reconnaissance missions [and] rapidly deployable networks [including those in] battlefields," he said.
Helmy is currently examining when and why network mobility can be an advantage, and is working on software that can adapt to a network that is sometimes mobile and sometimes not. The software is "a set of adaptive protocols that are flexible enough to allow mobility utilization when possible, yet still provide efficient operation" when mobility cannot be used, he said.
Helmy's eventual goal is to form practical networks that are made up of tens of thousands or millions of small devices and sensors, he said. These types of networks could be practical in about five years, he said.
The research was funded by the National Science Foundation (NSF).
Timeline: 5 years
Funding: National Science Foundation (NSF)
TRN Categories: Networking; Physics; Wireless Communications
Story Type: News
Related Elements: Technical paper, "Small Large-scale Wireless Networks: Mobility-Assisted Resource Discovery," posted at the Computer Research Repository (CoRR) at xxx.lanl.gov/abs/cs.NI/0207069
Advertisements:
August 21/28, 2002
Page One
Biochips get pumped
Chip design aims for quantum leap
Net traffic mimics earthquakes
Stamps and glue make circuits
Shortcuts lighten wireless load
News:
Research News Roundup
Research Watch blog
Features:
View from the High Ground Q&A
How It Works
RSS Feeds:
News
| Blog
| Books 
Ad links:
Buy an ad link
| Advertisements:
|
 |
Ad links: Clear History
Buy an ad link
|
TRN
Newswire and Headline Feeds for Web sites
|
© Copyright Technology Research News, LLC 2000-2006. All rights reserved.
