On Designing Incentive-Compatible Routing andForwarding Protocols in Wireless Ad-Hoc Networks∗— An Integrated Approach Using Game Theoretical andCryptographic TechniquesSheng ZhongLi (Erran) Li†Yanbin Grace Liu‡Yang Richard Yang§Department of Computer Science and Engineering, SUNY at Buffalo, Buffalo, NY 14260†Networking Research Lab, Bell Laboratories, Lucent Technologies, Murray Hill, NJ 07974‡Department of Computer Sciences, The University of Texas, Austin, TX 78712§Department of Computer Science, Yale University, New Haven, CT 06520ABSTRACTIn many applications, wireless ad-hoc networks are formed by de-vices belonging to independent users. Therefore, a challengingproblem is how to provide incentives to stimulate cooperation. Inthis paper, we study ad-hoc games—the routing and packet for-warding games in wireless ad-hoc networks. Unlike previous workwhich focuses either on routing or on forwarding, this paper in-vestigates both routing and forwarding. We first uncover an im-possibility result—there does not exist a protocol such that follow-ing the protocol to always forward others’ trafficisadominant ac-tion. Then we define a novel solution concept called cooperation-optimal protocols. We present Corsac, a cooperation-optimal pro-tocol consisting of a routing protocol and a forwarding protocol.The routing protocol of Corsac integrates VCG with a novel cryp-tographic technique to address the challenge in wireless ad-hoc net-works that a link’s cost (i.e., its type) is determined by two nodestogether. Corsac also applies efficient cryptographic techniques todesign a forwarding protocol to enforce the routing decision, suchthat fulfilling the routing decision is the optimal action of each nodein the sense that it brings the maximum utility to the node. Addi-tionally, we extend our framework to a practical radio propagationmodel where a transmission is successful with a probability. Weevaluate our protocols using simulations. Our evaluations demon-strate that our protocols provide incentives for nodes to forwardpackets.∗Sheng Zhong was supported in part by NSF grants ANI-0207399and ANI-0238038. This work was done while Sheng Zhong was atYale University. Yang Richard Yang was supported in part by NSFgrants ANI-0207399 and ANI-0238038. Li (Erran) Li was partiallysupported by NSF NRT grant# ANI-0335244.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’05, August 28–September 2, 2005, Cologne, Germany.Copyright 2005 ACM 1-59593-020-5/05/0008 ...$5.00.Categories and Subject DescriptorsC.2.1. [Computer-Communication Networks]: Network Archi-tecture and Design – Wireless communicationGeneral TermsAlgorithms, Economics, Security, DesignKeywordsMechanism design, game theory, security, incentives, wireless ad-hoc network1. INTRODUCTIONMany wireless ad-hoc networks are currently being designed ordeployed, driven by the vision of any-time, any-where connectiv-ity [27, 36, 42] and the wide availability of wireless communicationdevices such as PDAs, cell-phones, and 802.11 access points. Thefunctioning of such ad-hoc networks depends on the assumptionthat nodes in the network forward each other’s traffic. However,because forwarding packets consumes scarce resources such as bat-tery power, when the nodes in the network belong to different users,they may not have incentives to forward each other’s traffic.To stimulate nodes to forward each other’s traffic, many meth-ods have recently been proposed and evaluated (e.g., [3, 4, 5, 6,22, 24, 30, 31, 39, 40, 47]). Given the complexity and the subtletyof the incentive issues, researchers start to formally apply game-theoretic techniques to analyze and design protocols in wirelessad-hoc networks, by modeling the nodes in the networks as self-ish users whose goals are to maximize their own utilities (e.g., [1,3, 4, 5, 6, 39, 24, 29, 40, 44, 47]). Although much progress hasbeen made in the last few years, several fundamental issues remainunaddressed.A major lacking of previous studies is that each study focuseson a single component. Specifically, all previous studies focus ei-ther on the routing component (e.g., [1, 44]) or the packet forward-ing component (e.g., [15, 24, 29, 47]). However, it is clear thatboth routing and packet forwarding are needed to build a completesystem. The routing component determines a packet forwardingpath from a source to a destination; it may also determine howmany credits a node on the path will receive after forwarding eachpacket. However, because the nodes on the path should receivecredits if and only if they actually forward packets, we also needthe packet-forwarding component to verify that forwarding doeshappen. The designs of both the routing component and the for-warding component are challenging: the routing component shoulddiscover efficient packet forwarding paths (such as power-optimalpaths) even when the nodes are selfish and thus may try to cheatto improve their utilities; the packet-forwarding component shouldaddress the fair exchange problem where no node wants to makea commitment before the others do [38]. Although both individ-ual components are challenging, it is more challenging to designand analyze a complete system that integrates both routing and for-warding, given the interdependency of the two components. In themore general networking context, for scalable designs, many net-work systems are designed using a layered architecture; that is, anupper layer component relies on a lower layer component. Also,many network functions are implemented in multiple stages. How-ever, there was no previous methodology in investigating the jointincentive properties of a system involving multiple components orstages where each component or stage needs to deal with incentiveissues.The integration of multiple components is particularly challeng-ing in wireless ad-hoc networks because the wireless and ad-hocnature may make it impossible to design protocols with strong in-centive properties. Consider the forwarding protocol. An ideal for-warding protocol is one in which power-efficient paths are discov-ered; network nodes