Blind matchmaking for more efficient wireless networks

A network management scheme developed by KAUST allows users from different network providers to pair up to make better use of the available wireless spectrum although the two users know little about each other¹.

Wireless networks are groaning under the strain of an ever-increasing number of mobile devices and data-hungry applications, such as video streaming. This means network engineers are searching for alternative methods to utilize the available wireless bandwidth. Although wireless technology is improving all the time, a major source of inefficiency persists in the way that telecommunication companies divide up the wireless spectrum—the range of radio frequencies available for wireless communications.

Dr. Doha Hamza and Jeff Shamma, Professor of Electrical Engineering, have developed a way for strangers to pair up to make better use of the available bandwidth.

“Cognitive radio technology, as we call it, is a promising approach to solve the wireless spectrum scarcity problem,” explained Hamza. “This technology allows secondary unlicensed users to access the primary licensed users’ frequency bands. To make this possible, the primary and secondary users need to be robustly paired in a way that ensures mutual benefit while maintaining quality-of-service constraints.”

Hamza and Shamma turned to a sub-field of game theory called matching theory to deal with the cognitive radio-pairing problem. Matching theory is a mathematical framework for forming pairs from two groups that is already used routinely for several applications, such as organ-exchange programs, college admissions and communications networks.

“Primary users and secondary users need to be matched so that the partnership is mutually beneficial and binding,” said Shamma. “Different partnerships can provide different benefits, and primary and secondary users can have preferences over possible partnerships; however, unlike conventional applications for matching theory, there is no central authority to regulate the market, meaning that primary and secondary users have limited information about the preferences of other actors.”

To address the lack of centralization, the researchers developed a “blind” matching algorithm involving a relatively simple learning process. The agents meet one-on-one and make proposals based on their current aspirations. The proposals may be accepted or rejected, resulting in the forming and breaking of partnerships. Likewise, agent aspirations regarding the potential benefit of finding a partner may also rise and fall.

The algorithm is broadly applicable to general-matching settings, but is particularly useful for implementing in cognitive-radio networks. Shamma explained that “despite the blind encounters and limited information, we showed that this simple dynamic converges to a stable-matching state in which no pair of agents has an incentive to break their current matches in favor of others.”