| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Low-Cost Routing in Selfish and Rational Wireless Ad Hoc Networks
May 2006 (vol. 5 no. 5)
pp. 596-607
Numerous routing protocols have been proposed for wireless networks. A common assumption made by the majority of these protocols is that each wireless node will follow the prescribed protocol without any deviation. This may not be true in practice since wireless nodes could be owned by users who perform in their own interests. We then have to design routing protocols that still work properly even for networks composed of selfish nodes. In this paper, we propose a unicast routing protocol to address this issue under the assumption that all networking nodes are rational. Here, a node is rational if it always chooses a strategy that maximizes its benefit. We assume that each node has a privately known cost of relaying a unit of data for other nodes. In our protocol, each wireless node has to declare a cost for forwarding a unit of data. When a node wants to send data to the access point, it first computes the least cost path to the access point and then computes a payment to each node on this path. We present a pricing mechanism such that the profit of each relay node is maximized when it declares its true cost. We also give a time optimal method to compute the payment in a centralized manner. We then discuss in detail how to implement the routing protocol in the distributed manner. We conduct extensive simulations to study the ratio of the total payment over the total cost incurred by all relay nodes. We find that this ratio is small in practice. Our protocol works when the wireless nodes will not collude and we show that no truthful mechanism can avoid the collusion of any pair of two nodes. We also give a truthful mechanism when a node only colludes with its neighbors.
[1] T. Roughgarden, “Stackelberg Scheduling Strategies,” Proc. ACM Symp. Theory of Computing, pp. 104-113, 2001.
[2] T. Roughgarden, “Designing Networks for Selfish Users is Hard,” Proc. IEEE Symp. Foundations of Computer Science, pp. 472-481, 2001.
[3] T. Roughgarden and E. Tardos, “How Bad is Selfish Routing?,” Proc. IEEE Symp. Foundations of Computer Science, pp. 93-102, 2000.
[4] N. Nisan, “Algorithms for Selfish Agents,” Lecture Notes in Computer Science, vol. 1563, pp. 1-15, 1999.
[5] J. Feigenbaum and S. Shenker, “Distributed Algorithmic Mechanism Design: Recent Results and Future Directions,” Proc. Sixth Int'l Workshop Discrete Algorithms and Methods for Mobile Computing and Comm., pp. 1-13, 2002.
[6] D.J. Lehmann, L.I. O'Callaghan, and Y. Shoham, “Truth Revelation in Approximately Efficient Combinatorial Auctions,” Proc. ACM Conf. Electronic Commerce, pp. 96-102, 1999.
[7] L. Buttyan and J.P. Hubaux, “Stimulating Cooperation in Self-Organizing Mobile Ad Hoc Networks,” ACM/Kluwer Mobile Networks and Applications, vol. 5, no. 8, Oct. 2003.
[8] M. Jakobsson, J.P. Hubaux, and L. Buttyan, “A Micro-Payment Scheme Encouraging Collaboration in Multihop Cellular Networks,” Proc. Conf. Financial Cryptography, 2003.
[9] S. Marti, T.J. Giuli, K. Lai, and M. Baker, “Mitigating Routing Misbehavior in Mobile Ad Hoc Networks,” Proc. MobiCom Conf., 2000.
[10] L. Blazevic, L. Buttyan, S. Capkun, S. Giordano, J.P. Hubaux, and J.Y. LeBoudec, “Self-Organization in Mobile Ad-Hoc Networks: the Approach of Terminodes,” IEEE Comm. Magazine, vol. 39, no. 6, June 2001.
[11] L. Buttyan and J.P. Hubaux, “Enforcing Service Availability in Mobile Ad-Hoc Wans,” Proc. First ACM Int'l Symp. Mobile Ad Hoc Networking and Computing, pp. 87-96, 2000.
[12] V. Srinivasan, P. Nuggehalli, C.F. Chiasserini, and R.R. Rao, “Energy Efficiency of Ad Hoc Wireless Networks with Selfish Users,” Proc. European Wireless Conf., 2002.
[13] V. Srinivasan, P. Nuggehalli, C.F. Chiasserini, and R.R. Rao, “Cooperation in Wireless Ad Hoc Wireless Networks,” Proc. IEEE Infocom Conf., 2003.
[14] K. Jain and V.V. Vazirani, “Applications of Approximation Algorithms to Cooperative Games,” Proc. ACM Symp. Theory of Computing, pp. 364-372, 2001.
[15] J. Feigenbaum, C.H. Papadimitriou, and S. Shenker, “Sharing the Cost of Multicast Transmissions,” J. Computer and System Sciences, vol. 63, no. 1, pp. 21-41, 2001.
[16] W. Vickrey, “Counterspeculation, Auctions and Competitive Sealed Tenders,” J. Finance, pp. 8-37, 1961.
[17] E.H. Clarke, “Multipart Pricing of Public Goods,” Public Choice, pp. 17-33, 1971.
[18] T. Groves, “Incentives in Teams,” Econometrica, pp. 617-631, 1973.
[19] J. Green and J.J. Laffont, “Characterization of Satisfactory Mechanisms for the Revelation of Preferences for Public Goods,” Econometrica, pp. 427-438, 1977.
[20] J. Hershberger and S. Suri, “Vickrey Pricing in Network Routing: Fast Payment Computation,” Proc. IEEE Symp. Foundations of Computer Science, pp. 252-259, 2001.
[21] E. Nardelli, G. Proietti, and P. Widmayer, “Finding the Most Vital Node of a Shortest Path,” Theoretical Computer Science, vol. 296, no. 1, pp. 167-177, 2003.
[22] J. Feigenbaum, C. Papadimitriou, R. Sami, and S. Shenker, “A BGP-Based Mechanism for Lowest-Cost Routing,” Proc. ACM Symp. Principles of Distributed Computing, pp. 173-182, 2002.
[23] K. Jain and V.V. Vazirani, “Group Strategyproofness and No Subsidy via lp-Duality,” 2002.
[24] H. Moulin and S. Shenker, “Strategyproof Sharing of Submodular Costs: Budget Balance versus Efficiency,” Economic Theory, 2002.
[25] L. Anderegg and S. Eidenbenz, “Ad Hoc-VCG: A Truthful and Cost-Efficient Routing Protocol for Mobile Ad Hoc Networks with Selfish Agents,” Proc. ACM MobiCom Conf., pp. 245-259, 2003.
[26] N.B. Salem, L. Buttyan, J.P. Hubaux, and M. Kakobsson, “A Charging and Rewarding Scheme for Packet Forwarding in Multihop Cellular Networks,” Proc. ACM MobiHoc Conf., 2003.
Index Terms:
Noncooperative computing, unicast, game theory, wireless ad hoc networks.
Citation:
Weizhao Wang, Xiang-Yang Li, "Low-Cost Routing in Selfish and Rational Wireless Ad Hoc Networks," IEEE Transactions on Mobile Computing, vol. 5, no. 5, pp. 596-607, May 2006, doi:10.1109/TMC.2006.66
