Wireless network researchers at Virginia Tech are developing a competition in which teams of students match their algorithmic prowess in sending data across uncontrolled, ad hoc networks, where success will depend on cooperating AND competing against each other. The MANIAC Challenge will boost understanding of network behaviors, while motivating students in the field."
Wireless communications research is in crisis, according to Allen MacKenzie. Researchers and engineers tend to focus on point-to-point access and signals, however, the biggest issues are quickly becoming dynamic and complex wireless networks. “We have no unifying theory of how they work, and we need this theory to be engineers,” he said. “We need analytical tools so we can build and operate these complex systems.”
MacKenzie, who joined ECE last year as an assistant professor, recently won a $400,000 National Science Foundation (NSF) CAREER Award to develop analytical tools that can be applied to controlling the power, interconnections, and interference avoidance in wireless networks. The CAREER Awards are NSF’s most prestigious awards for new faculty members.
Much of the work in wireless communications is heavily reliant on simulation and heuristics (rules of thumb), with a growing emphasis on experimentation, he explained. “Unfortunately, unlike many other parts of electrical and computer engineering, we do not have a deep understanding how these networks work. We cannot write formulas and equations to solve networking problems.”
Complex, dynamic systems
Today’s internet is said to have about 317 million hosts. Wireless networks are smaller, but with the proliferation of devices beyond cell phones, PDAs, and laptops, wireless networks are expected to become as ubiquitous as the internet, according to MacKenzie. Further complicating wireless networks is the mobility factor, as shown by a recent New York City proposal to design a wireless safety network that could accommodate tens of thousands of mobile devices moving at speeds up to 70 mph. “Not only do we have size to contend with, but it’s possible they may all be moving around at high speed.”
MacKenzie and other researchers believe that game theory, which has revolutionized economics, may provide greater understanding of wireless systems. “The global economy, with 6.4 billion participants, is the most complex dynamic system developed by people,” he said. “If game theory can help us understand that system, maybe it can help us provide fundamental insights into the growing complexity of wireless systems.”
Applying economic theory to engineering
Game theory focuses on the interactions between players or agents in a changing environment, rather than the actions of a single player in a static environment. There are three elements to a game: players, preferences, and actions, which are the choices of the players.
Allen MacKenzie (left) and graduate student Ramakant Komali review a presentation on game theory for wireless networking.
When applied to wireless engineering, the players can be either human decision-makers or software controlling the devices. The actions can be decisions such as increasing power, or switching channels. Preferences become the player’s objective, or utility. “Potential games are particularly attractive for engineering applications,” MacKenzie said. “A game is a potential game if there is a single function that can express the preferences of any player when the actions of all other players are fixed.”
Although game theory seems to fit the wireless network situation, it is not directly applicable without significant adaptations for engineering, according to MacKenzie. He described two properties of preferences that are important to engineering and sometimes ignored by the economic theorists. “First, as a player, I must be able to measure my utility,” he said. “If I can’t, it’s not my utility. Second, the happiness of the player is different from the happiness of the designer.” A designer might want to maximize average node throughput, for example, whereas a player just wants to maximize her own throughput. The designer’s preferences do not typically play a role in traditional game theory.
Other differences involve cooperation. Most game theory models are based on noncooperating players, where each individual makes decisions for maximum personal benefit. In wireless networks, however, the designer can program the devices to consider the welfare of the whole network. Devices can be programmed to cooperate.
Cooperative games involve the formation of coalitions and the ability of players to negotiate and make binding agreements. “Nobel laureate John Nash suggested that all cooperative games should be studied by reducing them to non-cooperative form,” MacKenzie explained.
“Yet a fundamental question remains unaddressed: How can players with common objectives but differing information and limited means of communication cooperate to achieve a common goal?” This brings up another difference in that the economic models typically assume full knowledge of all the other player’s preferences and actions, whereas in wireless networks, decisions are made with limited knowledge and communications. Gaining more knowledge of each other’s situation requires more control traffic, which reduces network capability.
Working with colleagues in ECE and Economics, MacKenzie is applying game theory to understanding the tradeoffs in power control. In a cell system or wireless LAN where a single base provides access to several connections, any individual device that increases its power will get a higher signal-to-noise ratio, faster throughput, and fewer errors. The downside is that increasing power drains batteries faster and increases interference to other users on the network. “Using game theory, we can identify both problems and potential solutions,” MacKenzie said. “However, using the Nash equilibrium all the players end up increasing their transmit power and draining their batteries. So some researchers have proposed added pricing to the equation: charging individuals for creating interference to others.”
MacKenzie has proposed solving the power control problem by considering it as a repeated game. “Make the players responsible for enforcing the social welfare, or network quality,” he explained. “If you raise your power too much and interfere with all of us, the next time, we’ll punish you. If you know you will be punished, you might not misbehave in the first place.” For the CAREER project, he is applying the repeated-game-group-enforcement scenario to ad hoc networks.
The power control problem is directly related to topology control, or control of the network links in an ad hoc network. “If the user increases power, he can talk farther away, but that affects the topology of the network,” he said. “All these properties cost extra power and are the users willing to trade battery life for that?” He also described an extensive literature in the social sciences regarding network formation, where people are connected to those with whom they do business. “Perhaps it contains elements that can be connected with wireless topology control.”
MacKenzie is also applying game theory to analyzing interference avoidance and control the spreading code. In communications, the goal is for the spreading codes of different nodes to be maximally orthogonal (perpendicular) to each other, which generates the least interference. “Right now, spreading codes are chosen by the base station, but in the future, it would be nice if individuals could do it themselves and control what they see as interference,” he said. “That would also work best for ad hoc networks. What happens when you increase the signal-to-noise ratio, then choose the most orthogonal spread? The individual is better off and so is the entire network, since each individual is doing its best to avoid the others.”
Whether it is in controlling power, topology, or interference, MacKenzie is working to alter or extend game theory so that he can develop analytical tools for wireless communications. “Game theory was developed to understand systems that already exist. We engineers want to design what does not exist,” he said. “We need a deeper understanding of mechanism design: How can you design a game with specific outcomes? We need tools that focus on cooperation, not just conflict…We need to explicitly model information in games and acknowledge that each player has little information…”
He believes these analytical efforts may be applicable beyond wireless networks. “If you are an electrical or computer engineer today, you are going to have a hard time not encountering extremely complex dynamic systems in your work. It will happen in power, wireless, or circuits with multiple decision-making entities. Increasing complexity demands new, more powerful analytical tools.”
Increasing Exposure to EE
Allen MacKenzie has a special interest in boosting the representation of women and minorities in ECE. As part of his NSF CAREER Award, he is working to increase exposure to electrical engineering among middle and high-school girls. His team plans to develop a series of active, hands-on, modular education units to introduce students to communications engineering. Anticipated units include the mathematics of AM Communications, the Science of AM Communications, Simulation of an AM Communication System, Build a Crystal Radio, and Build an AM Transmitter.
The modules will first be introduced at the Virginia Tech College of Engineering summer camps for middle and high school students: C-Tech2 (photo) and Imagination. The modules will also be available on the web and MacKenzie expects to teach modules to groups of interested high school science and mathematics teachers in Southwest Virginia.