Truthful Multicast Routing in Selfish Wireless NetworksWeizhao WangDept. of Computer ScienceIllinois Institute of Technology,[email protected] Li∗Dept. of Computer ScienceIllinois Institute of Technology,[email protected] WangDept. of Computer ScienceUniversity of North Carolina [email protected] wireless networks, it is often assumed that each individual wire-less terminal will faithfully follow the prescribed protocols withoutany deviation– except, perhaps, for a few faulty or malicious ones.Wireless terminals, when owned by individual users, will likelydo what is the most beneficial to their owners, i.e., act “selfishly”.Therefore, an algorithm or protocol intended for selfish wirelessnetworks must be designed.In this paper, we specifically study how to conduct efficient mul-ticast routing in selfish wireless networks. We assume that eachwireless terminal or communication link will incur a cost when ittransits some data. Traditionally, the VCG mechanism has been theonly method to design protocols so that each selfish agent will fol-low the protocols for its own interest to maximize its benefit. Themain contributions of this paper are two-folds. First, for each ofthe widely used multicast structures, we show that the VCG basedmechanism does not guarantee that the selfish terminals will fol-low the protocol. Second, we design the first multicast protocolswithout using VCG mechanism such that each agent maximizes itsprofit when it truthfully reports its cost.Extensive simulations are conducted to study the practical per-formances of the proposed protocols regarding the actual networkcost and total payment.Categories and Subject DescriptorsC.2.2 [NetworkProtocols]: Routing Protocols; G.2.2 [Graph The-ory]: Network problems, Graph algorithms.General TermsAlgorithms, Design, Economics, Theory.KeywordsWireless ad hoc networks, selfish, mechanism design, pricing.∗The work of the author is partially supported by NSF CCR-0311174.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.MobiCom’04, Sept. 26-Oct. 1, 2004, Philadelphia, Pennsylvania, USA.Copyright 2004 ACM 1-58113-868-7/04/0009 ...$5.00.1. INTRODUCTIONIn wireless ad hoc networks, it is commonly assumed that, eachterminal contributes its local resources to forward the data for otherterminals to serve the common good, and benefits from resourcescontributed by other terminals to route its packets in return. How-ever, the limitation of energy supply, memory and computing re-sources of these wireless devices raise concerns about this tradi-tional assumption. A wireless device owned by an individual usermay prefer not participating in the routing to save its energy and re-sources. Therefore, if we assume that all users are selfish, providingincentives to wireless terminals is a must to encourage contributionand thus maintains the robustness and availability of wireless net-working systems. The question turns to how the incentives are de-signed. Consider a unicast routing and forwarding protocol basedon the least cost path (LCP): each terminal is asked to declare itscost of forwarding a unit data for other terminals, and the least costpath connecting the source and the target terminal is then selected.A very naive incentive is to pay each wireless terminal its declaredcost. However, the individual wireless terminal may declare an ar-bitrarily high cost for forwarding a data packet to other terminalshoping to increase its payment. Here, we would like to design apayment scheme such that every wireless terminal will report itscost truthfully and always forward others’ traffic out of its own in-terest to maximize its profit. This payment scheme is called strate-gyproof in the literature since it removes speculation and counter-speculation among wireless terminals. Always forwarding others’traffic is a dominant strategy of each terminal as it maximizes auser’s profit no matter what other users do. Unfortunately, it hasbeen shown in [24] that there does not exist a dominant strategysolution in which every node always forwards others’ packets inan ad hoc routing and forward game. However, there does exist astrategyproof payment scheme for the routing subgame.The most well-known and widely used strategyproof paymentmethod is so called VCG mechanism family by Vickrey [21], Clarke[6], and Groves [10]. A VCG mechanism uses an output that maxi-mizes the social efficiency, i.e., the total valuations of participatingagents. Several mechanisms [15, 7, 1, 24], which essentially allbelong to the VCG mechanism family, have been proposed in theliterature to ensure that each network agent will report its cost truth-fully for unicast. In these mechanisms, the least cost path, whichmaximizes the social efficiency, is used for routing. To support acommunication among a group of users, multicast is more efficientthan unicast or broadcast, as it can transmit packets to destinationsusing fewer network resource, thus increasing the social efficiency.A truthful multicast routing protocol, which selfish wireless ter-minals will follow, is composed of two components: (1) the treestructure that connects the sources and receivers, and (2) the pay-ment to the relay nodes in this tree. Multicast poses a unique chal-245lenge in designing strategyproof mechanisms: it is NP-hard to findthe tree structure with the minimum cost, which in turn maximizesthe social efficiency. A range of multicast structures, such as theleast cost path tree (LCPT), the pruning minimum spanning tree(PMST), virtual minimum spanning tree (VMST) and Steiner tree,were proposed to replace the optimal multicast tree. In this paper,we will not redesign the wheel; instead, we show how paymentschemes can be designed for existing multicast tree structures sothat rational selfish wireless terminals will follow the protocols fortheir own interests.This paper focuses on the design of truthful payment schemesfor the multicast routing subgame. The main contribution is as fol-lows. Firstly, for each of these widely used multicast structures, weshow that a simple application of VCG payment method is not
View Full Document