lighten wireless load
Technology Research News
Most 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
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,
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
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
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
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
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
Biochips get pumped
Chip design aims
for quantum leap
Net traffic mimics
Stamps and glue make
Research News Roundup
Research Watch blog
View from the High Ground Q&A
How It Works
News | Blog
Buy an ad link