Johns Hopkins EN 600 647 - Truthful Multicast Routing in Selfish Wireless Networks

Unformatted text preview:

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

Johns Hopkins EN 600 647 - Truthful Multicast Routing in Selfish Wireless Networks

Documents in this Course
Mobile IP

Mobile IP

33 pages

WiMAX

WiMAX

31 pages

Load more
Download Truthful Multicast Routing in Selfish Wireless Networks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Truthful Multicast Routing in Selfish Wireless Networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Truthful Multicast Routing in Selfish Wireless Networks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?