| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Nash Equilibria of Packet Forwarding Strategies in Wireless Ad Hoc Networks
May 2006 (vol. 5 no. 5)
pp. 463-476
In self-organizing ad hoc networks, all the networking functions rely on the contribution of the participants. As a basic example, nodes have to forward packets for each other in order to enable multihop communication. In recent years, incentive mechanisms have been proposed to give nodes incentive to cooperate, especially in packet forwarding. However, the need for these mechanisms was not formally justified. In this paper, we address the problem of whether cooperation can exist without incentive mechanisms. We propose a model based on game theory and graph theory to investigate equilibrium conditions of packet forwarding strategies. We prove theorems about the equilibrium conditions for both cooperative and noncooperative strategies. We perform simulations to estimate the probability that the conditions for a cooperative equilibrium hold in randomly generated network scenarios. As the problem is involved, we deliberately restrict ourselves to a static configuration. We conclude that in static ad hoc networks— where the relationships between the nodes are likely to be stable—cooperation needs to be encouraged.
[1] T. Alpcan, T. Basar, R. Srikant, and E. Altman, “CDMA Uplink Power Control as a Noncooperative Game,” Wireless Networks, The J. Mobile Comm., Computation and Information, Nov. 2002.
[2] R. Axelrod, The Evolution of Cooperation. New York: Basic Books, 1984.
[3] S. Buchegger and J-Y. Le Boudec, “Performance Analysis of the CONFIDANT Protocol (Cooperation of Nodes— Fairness in Dynamic Ad-Hoc NeTworks),” Proc. Third ACM Int'l Symp. Mobile Ad Hoc Networking and Computing (MobiHoc '02), pp. 80-91, June 2002.
[4] L. Buttyán and J.-P. Hubaux, “Enforcing Service Availability in Mobile Ad Hoc WANs,” Proc. First ACM/IEEE Int'l Workshop Mobile Ad Hoc Networking and Computing (MobiHoc '00), Aug. 2000.
[5] L. Buttyán and J.-P. Hubaux, “Stimulating Cooperation in Self-Organizing Mobile Ad Hoc Networks,” ACM/Kluwer Mobile Networks and Applications (MONET) Special Issue on Mobile Ad Hoc Networks, vol. 8, no. 5, Oct. 2003.
[6] J.R. Douceur, “The Sybil Attack,” Proc. Int'l Workshop Peer-to-Peer Systems, Mar. 2002.
[7] M. Félegyházi, L. Buttyán, and J.-P. Hubaux, “Equilibrium Analysis of Packet Forwarding Strategies in Wireless Ad Hoc Networks— the Static Case,” Proc. Conf. Personal Wireless Comm. (PWC '03), Sept. 2003.
[8] D. Fudenberg and J. Tirole, Game Theory. MIT Press, 1991.
[9] D. Goodman and N. Mandayam, “Network Assisted Power Control for Wireless Data,” Mobile Networks and Applications (MONET), vol. 6, pp. 409-415, 2001.
[10] J.P. Hubaux, T. Gross, J.Y. Le Boudec, and M. Vetterli, “Towards Self-Organized Mobile Ad Hoc Networks: The Terminodes Project,” IEEE Comm. Magazine, Jan. 2001.
[11] Y. Jin and G. Kesidis, “Nash Equilibria of a Generic Networking Game with Applications to Circuit-Switched Networks,” Proc. IEEE INFOCOM '03 Conf., Mar.-Apr. 2003.
[12] Y. Korilis, A. Lazar, and A. Orda, “Architecting Noncooperative Networks,” IEEE J. Selected Areas in Comm., vol. 13, no. 8, 1995.
[13] Y. Korilis and A. Orda, “Incentive Compatible Pricing Strategies for QoS Routing,” Proc. IEEE INFOCOM'99 Conf., Mar. 1999.
[14] S. Marti, T.J. Giuli, K. Lai, and M. Baker, “Mitigating Routing Misbehavior in Movile Ad Hoc Networks,” Proc. ACM/IEEE Int'l Conf. Mobile Computing and Networking (Mobicom '00), pp. 255-265, 2000.
[15] P. Michiardi and R. Molva, “Core: A COllaborative Reputation Mechanism to Enforce Node Cooperation in Mobile Ad Hoc Networks,” Proc. Conf. Comm. and Multimedia Security 2002, Sept. 2002.
[16] J. Nash, “Equilibrium Points in $N{\hbox{-}}{\rm Person}$ Games,” Proc. Nat'l Academy of Sciences, vol. 36, pp. 48-49, 1950.
[17] M.J. Osborne and A. Rubinstein, A Course in Game Theory. MIT Press, 1994.
[18] Y. Qiu and P. Marbach, “Bandwidth Allocation in Wireless Ad Hoc Networks: A Price-Based Approach,” Proc. IEEE INFOCOM '03 Conf., Mar.-Apr. 2003.
[19] A. Rapaport and A.M. Chammah, The Prisoner's Dilemma. Ann Arbor, Mich.: Univ. of Michigan Press, 1965.
[20] T. Roughgarden, “Selfish Routing,” PhD thesis, Cornell Univ., May 2002.
[21] V. Srinivasan, P. Nuggehalli, C.F. Chiasserini, and R.R. Rao, “Cooperation in Wireless Ad Hoc Networks,” Proc. IEEE INFOCOM '03 Conf., Mar.-Apr. 2003.
[22] R. Trivers, “The Evolution of Reciprocal Alturism,” Quarterly Rev. of Biology, vol. 46, pp. 35-57, 1971.
[23] A. Urpi, M. Bonuccelli, and S. Giordano, “Modeling Cooperation in Mobile Ad Hoc Networks: A Formal Description of Selfishness,” Proc. WiOpt '03 Conf.: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, Mar. 2003.
[24] L.M. Wahl and M.A. Nowak, “The Continuous Prisoner's Dilemma: I. Linear Reactive Strategies,” J. Theoretical Biology, vol. 200, pp. 307-321, 1999.
[25] H. Yaïche, R.R. Mazumdar, and C. Rosenberg, “A Game Theoretical Framework for Bandwidth Allocation and Pricing in Broadband Networks,” IEEE/ACM Trans. Networking, vol. 8, no. 5, Oct. 2000.
[26] M. Xiao, N.B. Schroff, and E.K.P. Chong, “Utility-Based Power Control in Cellular Systems,” Proc. IEEE INFOCOM '01 Conf., Apr. 2001.
[27] S. Zhong, Y.R. Yang, and J. Chen, “Sprite: A Simple, Cheat-Proof, Credit-Based System for Mobile Ad Hoc Networks,” Proc. IEEE INFOCOM '03 Conf., Mar.-Apr. 2003.
Index Terms:
Ad hoc networks, cooperation, graph theory, game theory, Nash equilibrium.
Citation:
M?rk F?legyh?zi, Jean-Pierre Hubaux, Levente Butty?, "Nash Equilibria of Packet Forwarding Strategies in Wireless Ad Hoc Networks," IEEE Transactions on Mobile Computing, vol. 5, no. 5, pp. 463-476, May 2006, doi:10.1109/TMC.2006.68
