Nav: Home

New algorithm keeps data fresh in wireless networks

June 05, 2018

For wireless networks that share time-sensitive information on the fly, it's not enough to transmit data quickly. That data also need to be fresh. Consider the many sensors in your car. While it may take less than a second for most sensors to transmit a data packet to a central processor, the age of that data may vary, depending on how frequently a sensor is relaying readings.

In an ideal network, these sensors should be able to transmit updates constantly, providing the freshest, most current status for every measurable feature, from tire pressure to the proximity of obstacles. But there's only so much data that a wireless channel can transmit without completely overwhelming the network.

How, then, can a constantly updating network -- of sensors, drones, or data-sharing vehicles -- minimize the age of the information that it receives at any moment, while at the same time avoiding data congestion?

Engineers in MIT's Laboratory for Information and Decision Systems are tackling this question and have come up with a way to provide the freshest possible data for a simple wireless network.

The researchers say their method may be applied to simple networks, such as multiple drones that transmit position coordinates to a single control station, or sensors in an industrial plant that relay status updates to a central monitor. Eventually, the team hopes to tackle even more complex systems, such as networks of vehicles that wirelessly share traffic data.

"If you are exchanging congestion information, you would want that information to be as fresh as possible," says Eytan Modiano, professor of aeronautics and astronautics and a member of MIT's Laboratory for Information and Decision Systems. "If it's dated, you might make the wrong decision. That's why the age of information is important."

Modiano and his colleagues presented their method in a paper at IEEE's International Conference on Computation Communications (Infocom), where it won a Best Paper Award. The paper will appear online in the future. The paper's lead author is graduate student Igor Kadota; former graduate student Abhishek Sinha is also a co-author.

Keeping it fresh

Traditional networks are designed to maximize the amount of data that they can transmit across channels, and minimize the time it takes for that data to reach its destination. Only recently have researchers considered the age of the information -- how fresh or stale information is from the perspective of its recipient.

"I first got excited about this problem, thinking in the context of UAVs -- unmanned aerial vehicles that are moving around in an environment, and they need to exchange position information to avoid collisions with one another," Modiano says. "If they don't exchange this information often enough, they might collide. So we stepped back and started looking at the fundamental problem of how to minimize age of information in wireless networks."

In this new paper, Modiano's team looked for ways to provide the freshest possible data to a simple wireless network. They modeled a basic network, consisting of a single data receiver, such as a central control station, and multiple nodes, such as several data-transmitting drones.

The researchers assumed that only one node can transmit data over a wireless channel at any given time. The question they set out to answer: Which node should transmit data at which time, to ensure that the network receives the freshest possible data, on average, from all nodes?

"We are limited in bandwidth, so we need to be selective about what and when nodes are transmitting," Modiano says. "We say, how do we minimize age in this simplest of settings? Can we solve this? And we did."

An optimal age

The team's solution lies in a simple algorithm that essentially calculates an "index" for each node at any given moment. A node's index is based on several factors: the age, or freshness of the data that it's transmitting; the reliability of the channel over which it is communicating; and the overall priority of that node.

"For example, you may have a more expensive drone, or faster drone, and you'd like to have better or more accurate information about that drone. So, you can set that one with a high priority," Kadota explains.

Nodes with a higher priority, a more reliable channel, and older data, are assigned a higher index, versus nodes that are relatively low in priority, communicating over spottier channels, with fresher data, which are labeled with a lower index.

A node's index can change from moment to moment. At any given moment, the algorithm directs the node with the highest index to transmit its data to the receiver. In this prioritizing way, the team found that the network is guaranteed to receive the freshest possible data on average, from all nodes, without overloading its wireless channels.

The team calculated a lower bound, meaning an average age of information for the network that is fresher than any algorithm could ever achieve. They found that the team's algorithm performs very close to this bound, and that it is close to the best that any algorithm could do in terms of providing the freshest possible data for a simple wireless network.

"We came up with a fundamental bound that says, you cannot possibly have a lower age of information than this value ¬-- no algorithm could be better than this bound -- and then we showed that our algorithm came close to that bound," Modiano says. "So it's close to optimal."

The team is planning to test its index scheme on a simple network of radios, in which one radio may serve as a base station, receiving time-sensitive data from several other radios. Modiano's group is also developing algorithms to optimize the age of information in more complex networks.

"Our future papers will look beyond just one base station, to a network with multiple base stations, and how that interacts," Modiano says. "And that will hopefully solve a much bigger problem."
-end-
This research was funded, in part, by the National Science Foundation (NSF) and the Army Research Office (ARO).

Additional background

ARCHIVE: Solving network congestion http://news.mit.edu/2016/solving-network-congestion-megamimo-0823

ARCHIVE: Designing vehicle-sharing networks http://news.mit.edu/2018/designing-efficient-vehicle-sharing-networks-0123

ARCHIVE: A simple solution for terrible traffic http://news.mit.edu/2017/simple-solution-terrible-traffic-0706

Massachusetts Institute of Technology

Related Algorithm Articles:

New algorithm to help process biological images
Skoltech researchers have presented a new biological image processing method that accurately picks out specific biological objects in complex images.
Skoltech scientists break Google's quantum algorithm
In the near term, Google has devised new quantum enhanced algorithms that operate in the presence of realistic noise.
The most human algorithm
A team from the research group SEES:lab of the Department of Chemical Engineering of the Universitat Rovira I Virgili and ICREA has made a breakthrough with the development of a new algorithm that makes more accurate predictions and generates mathematical models that also make it possible to understand these predictions.
Algorithm turns cancer gene discovery on its head
Prediction method could help personalize cancer treatments and reveal new drug targets.
New algorithm predicts gestational diabetes
Timely prediction may help prevent the condition using nutritional and lifestyle changes.
New algorithm could mean more efficient, accurate equipment for Army
Researchers working on an Army-funded project have developed an algorithm to simulate how electromagnetic waves interact with materials in devices to create equipment more efficiently and accurately.
Universal algorithm set to boost microscopes
EPFL scientists have developed an algorithm that can determine whether a super-resolution microscope is operating at maximum resolution based on a single image.
Algorithm designed to map universe, solve mysteries
Cornell University researchers have developed an algorithm designed to visualize models of the universe in order to solve some of physics' greatest mysteries.
Algorithm tells robots where nearby humans are headed
A new tool for predicting a person's movement trajectory may help humans and robots work together in close proximity.
Algorithm to transform investment banking with higher returns
A University of Bath researcher has created an algorithm which aims to remove the elements of chance, bias or emotion from investment banking decisions, a development which has the potential to reduce errors in financial decision making and improve financial returns in global markets.
More Algorithm News and Algorithm Current Events

Trending Science News

Current Coronavirus (COVID-19) News

Top Science Podcasts

We have hand picked the top science podcasts of 2020.
Now Playing: TED Radio Hour

Listen Again: Reinvention
Change is hard, but it's also an opportunity to discover and reimagine what you thought you knew. From our economy, to music, to even ourselves–this hour TED speakers explore the power of reinvention. Guests include OK Go lead singer Damian Kulash Jr., former college gymnastics coach Valorie Kondos Field, Stockton Mayor Michael Tubbs, and entrepreneur Nick Hanauer.
Now Playing: Science for the People

#562 Superbug to Bedside
By now we're all good and scared about antibiotic resistance, one of the many things coming to get us all. But there's good news, sort of. News antibiotics are coming out! How do they get tested? What does that kind of a trial look like and how does it happen? Host Bethany Brookeshire talks with Matt McCarthy, author of "Superbugs: The Race to Stop an Epidemic", about the ins and outs of testing a new antibiotic in the hospital.
Now Playing: Radiolab

Dispatch 6: Strange Times
Covid has disrupted the most basic routines of our days and nights. But in the middle of a conversation about how to fight the virus, we find a place impervious to the stalled plans and frenetic demands of the outside world. It's a very different kind of front line, where urgent work means moving slow, and time is marked out in tiny pre-planned steps. Then, on a walk through the woods, we consider how the tempo of our lives affects our minds and discover how the beats of biology shape our bodies. This episode was produced with help from Molly Webster and Tracie Hunte. Support Radiolab today at Radiolab.org/donate.