Advertisement

Equilibria for Broadcast Range Assignment Games in Ad-Hoc Networks

  • Pilu Crescenzi
  • Miriam Di Ianni
  • Alessandro Lazzoni
  • Paolo Penna
  • Gianluca Rossi
  • Paola Vocca
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3738)

Abstract

Ad-hoc networks are an emerging networking technology, in which the nodes form a network with no fixed infrastructure: each node forwards messages to the others by using the wireless links induced by their power levels. Generally, energy-efficient protocols heavily rely on cooperation. In this paper, we analyze from a game-theoretic point of view the problem of performing a broadcast operation from a given station s. We show both theoretical and experimental results on how the existence of (good) Nash equilibria is determined by factors such as the transmission power of the stations or the payment policy that stations can use to enforce their reciprocal cooperation.

Keywords

Nash Equilibrium Transmission Range Minimum Span Tree Random Instance Payment Policy 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Ambühl, C.: An optimal bound for the mst algorithm to compute energy efficient broadcast trees in wireless networks. In: Proc. of the 33rd International Colloquium on Automata, Languages and Programming, ICALP (2005) (to appear)Google Scholar
  2. 2.
    Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, É., Wexler, T.: Near-optimal Network Design with Selfish Agents. In: STOC 2003: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pp. 511–520. ACM Press, New York (2003)CrossRefGoogle Scholar
  3. 3.
    Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, É., Wexler, T., Roughgarden, T.: The Price of Stability for Network Design with Fair Cost Allocation. In: FOCS, pp. 295–304 (2004)Google Scholar
  4. 4.
    Bilò, V., Flammini, M., Melideo, G., Moscardelli, L.: On Nash Equilibria for Multicast Transmissions in Ad-Hoc Wireless Networks. In: Proc. of the 15th International Symposium on Algorithms and Computation (ISAAC), pp. 172–183 (2004)Google Scholar
  5. 5.
    Cǎlinescu, G., Li, X.Y., Frieder, O., Wan, P.J.: Minimum-Energy Broadcast Routing in Static Ad Hoc Wireless Networks. In: Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pp. 1162–1171 (2001)Google Scholar
  6. 6.
    Clementi, A.E.F., Crescenzi, P., Penna, P., Rossi, G., Vocca, P.: A Worst-case Analysis of an MST-based Heuristic to Construct Energy-Efficient Broadcast Trees in Wireless Networks. Technical Report 010, University of Rome “Tor Vergata”, Math Department (2001), Available at http://www.mat.uniroma2.it/~penna/papers/stacs01-TR.ps.gz (Extended version of [7])
  7. 7.
    Clementi, A.E.F., Crescenzi, P., Penna, P., Rossi, G., Vocca, P.: On the complexity of computing minimum energy consumption broadcast subgraphs. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol. 2010, pp. 121–131. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  8. 8.
    Crescenzi, P., Di Ianni, M., Lazzoni, A., Penna, P., Rossi, G., Vocca, P.: Equilibria for Broadcast Range Assignment Games in Ad-Hoc Networks. Technical Report, University of Rome “Tor Vergata”, Math Department (2005), Available at http://www.mat.uniroma2.it/~rossig/adhocnow2005extended.pdf
  9. 9.
    Eidenbenz, S., Kumar, V.S.A., Zust, S.: Equilibria in Topology Control Games for Ad-Hoc Networks. In: Proceedings of the DIALM (2003)Google Scholar
  10. 10.
    Ephremides, A., Nguyen, G.D., Wieselthier, J.E.: On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks. In: Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pp. 585–594 (2000)Google Scholar
  11. 11.
    Jardosh, A., Belding-Royer, E.M., Almeroth, K.C., Suri, S.: Real world Environment Models for Mobile Ad hoc Networks. IEEE Journal on Special Areas in Communications (to appear)Google Scholar
  12. 12.
    Klasing, R., Navarra, A., Papadopoulos, A., Pérénnes, S.: Adaptive broadcast consumption (ABC), a new heuristic and new bounds for the minimum energy broadcast routing problem. In: Mitrou, N.M., Kontovasilis, K., Rouskas, G.N., Iliadis, I., Merakos, L. (eds.) NETWORKING 2004. LNCS, vol. 3042, pp. 866–877. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  13. 13.
    Monderer, D., Shapley, L.S.: Potential Game. Games and Economic Behaviour 14, 124–143 (1996)zbMATHCrossRefMathSciNetGoogle Scholar
  14. 14.
    Monma, C.L., Suri, S.: Transitions in Geometric Minimum Spanning Trees. Discrete & Computational Geometry 8, 265–293 (1992)zbMATHCrossRefMathSciNetGoogle Scholar
  15. 15.
    Osborne, M.J., Rubinstein, A.: A Course in Game Theory. MIT Press, Cambridge (1994)zbMATHGoogle Scholar
  16. 16.
    Pahlavan, K., Levesque, A.: Wireless Information Networks. Wiley-Interscience, Hoboken (1995)Google Scholar
  17. 17.
    Penna, P., Ventre, C.: Energy-Efficient Broadcasting in Ad-Hoc Networks: Combining MSTs with Shortest-Path Trees. In: Proc. of the 1st ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks (PE-WASUN), pp. 61–68. ACM Press, New York (2004)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Pilu Crescenzi
    • 1
  • Miriam Di Ianni
    • 2
  • Alessandro Lazzoni
    • 1
  • Paolo Penna
    • 3
  • Gianluca Rossi
    • 2
  • Paola Vocca
    • 4
  1. 1.Dipartimento di Sistemi e InformaticaUniversità di FirenzeFlorenceItaly
  2. 2.Dipartimento di MatematicaUniversità degli Studi di Roma “Tor Vergata”RomeItaly
  3. 3.Dipartimento di Informatica ed Applicazioni “R.M. Capocelli”Università di SalernoSalernoItaly
  4. 4.Dipartimento di MatematicaUniversità di LecceLecceItaly

Personalised recommendations