Project Title: A Microeconomic Approach: Protocol Design for Ubiquitous and Integrated Networks
Sponsor: Oak Ridge Associated Universities & UNC-Charlotte (via the ORAU Ralph E. Powe Junior Faculty Enhancement Awards)
Duration: June 2006 - May 2007
Investigators: Dr. Yu Wang (PI)
A ubiquitous and integrated architecture has been envisioned for future networking. Most of the algorithms and protocols designed in computer network implicitly assume that the participating computers/users will act as instructed. However, end users in a wireless network are interested in the share of the radio spectrum they enjoy, not in the global optimum of the system. If these nodes act selfishly (e.g., refuse to relay the data while the routing protocol assumed that they will), it may hinder the functioning of the network. Therefore, protocols intended for selfish computers/users must be designed in advance to cope with selfishness for future ubiquitous and integrated networks. In this project, we investigate the impact of users' selfish behavior on the performance of several particular network protocols in integrated networks, and aims to design truthful network protocols based on game theory approaches for ubiquitous and integrated networks with various selfish participants.
The long-term goal of this research is to develop, design, and implement network protocols for ubiquitous and integrated networks by taking user behaviors into account. Specifically, in this project, we focused on the design of new routing and multicast protocols for selfish wireless networks.
In this project, we investigated the design and development of truthful network protocols for selfish wireless networks where the network entities try to maximize their own benefits instead of altruistically contribute to the network by following the prescribed protocols. We applied two technologies, game theory and graph theory, which were developed in interdisciplinary areas involving economics, mathematics and computer science, into the design of wireless network protocols. The research activities can be divided into three:
Unicast routing protocol in selfish multihop wireless networks. We proposed novel solutions for unicast routing in wireless networks consisted of selfish terminals to alleviate the inevitable over-payment problem (and thus economic inefficiency) of the VCG (Vickrey-Clark-Groves) mechanism. In addition, we systematically studied the unicast routing system in which both the relay terminals and the service requestor (either the source or the destination nodes or both) could be selfish.
Multicast routing protocol in selfish multihop wireless networks. We studied how to design strategy-proof multicast protocols for non-cooperative wireless networks such that these selfish entities will follow the protocols out of their own interests.
Unicast routing protocol in selfish wireless integrated networks. Wireless hybrid networks combine the characteristics of both cellular/WLAN and mobile ad hoc networks. We studied how to conduct efficient unicast routing in selfish wireless hybrid networks.
Research Findings and Outcomes:
During the above research activities, we made the following research findings:
routing protocol in selfish multihop wireless networks.
a) For the principal model where the service requestor is not selfish, we developed a mechanism that provably creates incentives for intermediate terminals to cooperate in forwarding packets for others. Our mechanism substantially reduces the overpayment by using Nash equilibrium solutions as opposed to strategy-proof VCG solutions.
b) For a more realistic case where the service requestor can act selfishly, we showed that if we insist on the requirement of strategyproofness for the relay terminals, then no system can guarantee that the central authority can retrieve at least 1/n of the total payment.
c) We developed a strategy-proof unicast system that collects 1/2n of the total payment, which is thus asymptotically optimum.
d) By only requiring Nash Equilibrium solutions, we designed a system that creates incentives for the service requestor and intermediate terminals to correctly follow the prescribed protocol. More importantly, the central authority can retrieve at least half the total payment.
e) We verified the economic efficiency of our systems through simulations that are based on very realistic terminal distributions.
Related Publication: "OURS: Optimal Unicast Routing Systems in Non-Cooperative Wireless Networks", W. Wang, S. Eidenbenz, Y. Wang, X.-Y. Li, 12th ACM Annual International Conference on Mobile Computing and Networking (MobiCom 2006), 2006.
routing protocol in selfish multihop wireless networks.
a) For the widely used multicast structures, we showed that the VCG based mechanism does not guarantee that the selfish terminals will follow the protocols.
b) We designed the first multicast protocols without using VCG mechanism such that each agent maximizes its profit when it truthfully reports its cost.
c) We gave a general framework to decide whether it is possible to have a strategyproof multicast protocol, and how if possible to transform an existing multicast protocol to a strategyproof multicast protocol
d) We showed how the payments to those relay entities are shared fairly among all receivers so that it encourages collaboration among receivers.
e) Extensive simulations were conducted to study the practical performances of the proposed protocols regarding the actual network cost and total payment
Related Publication: "Design Multicast Protocols for Non-Cooperative Networks", W. Wang, X.-Y. Li, Y. Wang, Z. Sun, IEEE Journal on Selected Areas in Communications (JSAC), Volume: 26, Number: 7, Pages: 1238-1249, September 2008.
routing protocol in selfish wireless integrated networks.
a) We designed a VCG-based routing protocol for hybrid networks, and showed it is truthful but could lead to large over-payment.
b) We modified the VCG-based routing protocol to make it more efficient for hybrid networks in term of total payment. However, we proved that nodes could lie up their costs in the modified method.
c) We proposed a novel routing protocol based on first-price path auctions, which can achieve a Nash equilibrium with low total payment.
Related Publication: "Routing Game in Hybrid Wireless Mesh Networks with Selfish Mesh Clients", Y. Wang, T.A. Dahlberg, W. Wang, International Journal of Autonomous and Adaptive Communications Systems (IJAACS), Volume: 1, Number: 4, Pages: 425-446, 2008.