Skip to main content

Advertisement

SpringerLink
Log in

Neighbor Selection Game in Wireless Ad Hoc Networks

  • Published:
Wireless Personal Communications Aims and scope Submit manuscript

Abstract

In wireless ad hoc networks, there is no infrastructure to enforce cooperation between nodes. As a result, nodes may act selfishly when running network protocols to conserve their energy resources as much as possible. In this paper, we consider the “neighbor selection” game in which each individual node tries to selfishly choose its neighborhood such that its own energy consumption is optimized. We first focus on a simplified version of this game where nodes know their transmission power before participating in the game. After analyzing the problem, we propose a couple of distributed algorithms to find stable topologies using two kinds of global and local connectivity information. We then take into account the general case where the transmission powers are unknown variables and should be determined during the game. Finally, we evaluate the performance of the proposed algorithms through simulations.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ramanathan, R., & Rosales-Hain, R. (2000). Topology control of multihop wireless networks using transmit power adjustment. In Proceeding of IEEE INFOCOM.

  2. Santi, P. (2005). Topology control in wireless ad hoc and sensor networks. ACM Computing Surveys, 37(2).

  3. Lloyd, E. L., Liu, R., Marathe, M. V., Ramanathan, R., & Ravi, S. S. (2002). Algorithmic aspects of topology control problems for ad hoc networks. In Proceeding of ACM MobiHoc.

  4. Eidenbenz S., Kumar V., Zust S. (2006) Equilibria in topology control games for ad hoc networks. ACM/Kluwer Mobile Networks and Applications 11(2): 143–159

    Article  Google Scholar 

  5. Pham, P. P., & Perreau, S. (2003). Performance analysis of reactive shortest path and multi-path routing mechanism with load balance. In Proceeding of IEEE INFOCOM.

  6. Ganjali, Y., & Keshavarzian, A. (2004). Load balancing in ad hoc networks: single-path routing vs. multi-path routing. In Proceeding of IEEE INFOCOM.

  7. Komali, R. S., MacKenzie, A. B., & Gilles, R. P. (2008). Effect of Selfish Node Behavior on Efficient Topology Design. IEEE Trans Mobile Computing, 7(9).

  8. Song W., Li X., Frieder O., Wang W. (2006) Localized topology control for unicast and broadcast in wireless ad hoc networks. IEEE/ACM Trans Parallel and Distributed Systems 17(4): 321–334

    Article  Google Scholar 

  9. Zarifzadeh, S., Nayyeri, A., & Yazdani, N. (2008). Efficient construction of network topology to conserve energy in wireless ad hoc networks. Elsevier Computer Communications, 31(1).

  10. Zarifzadeh, S., Nayyeri, A., Yazdani, N., Khonsari, A., & Hajabdolali, H. (2009). Joint range assignment and routing to conserve energy in wireless ad hoc networks. Elsevier Computer Networks, 53(11).

  11. Al-Karaki J. N., Kamal A. E. (2008) Stimulating node cooperation in mobile ad hoc networks. Wireless Personal Communications 44: 219–239

    Article  Google Scholar 

  12. Srivastava, V., Neel, J., MacKenzie, A., Menon, R., Hicks, J., DaSilva, L., Reed, J., & Gilles, R. (2005). Using Game Theory to Analyze Wireless Ad Hoc Networks. IEEE Comm Surveys and Tutorials, Fourth Quarter.

  13. Komali, R. S., & MacKenzie, A. B. (2006). Distributed topology control in ad hoc networks: A game theoretic perspective. In Proceeding of IEEE CCNC.

  14. Komali R. S., Thomas R. W., DaSilva L. A., MacKenzie A. B. (2010) The price of ignorance: Distributed topology control in cognitive networks. IEEE Trans Wireless Communications 9(4): 1434–1445

    Article  Google Scholar 

  15. Zarifzadeh, S., Nayyeri, A., & Yazdani, N. (2012). Energy-efficient topology control in wireless ad hoc networks with selfish nodes. Elsevier Computer Networks, 56(2).

  16. van den Berg, E., Fecko, M.A., Samtani, S., Lacatus, C., & Patel, M. (2010). Cognitive Topology Control based on Game Theory. In Proceeding of IEEE Milcom.

  17. Ren H., Meng M. Q. H. (2009) Game-theoritic modeling of joint topology control and power scheduling for wireless heterogeneous sensor networks. IEEE Trans Automation Science and Engineering 6(4): 610–625

    Article  Google Scholar 

  18. Hao, X. C., & Zhang, Y. X. (2012). Virtual game-based energy balanced topology control algorithm for wireless sensor networks. Wireless Personal Communications.

  19. Chu, X., & Sethu, H. (2012). Cooperative topology control with vdaptation for improved lifetime in wireless ad hoc networks. In Proceeding of IEEE INFOCOM.

  20. Yuen, S., & Li, B. (2005). Strategyproof mechanisms towards evolutionary topology formation in autonomous networks. ACM/Kluwer Mobile Networks and Applications, special issue on non-cooperative. Wireless Networking and Computing.

  21. Cai, J., Liu, Y., Lian, J., Li, M., Pooch, U. W., & Ni, L. M. (2006). Truthful topology control in wireless ad hoc networks with selfish nodes. In Proceeding of ICPP.

  22. Santi, P., Eidenbenz, S., & Resta, G. (2006). A framework for incentive compatible topology control in non-cooperative wireless multi-hop networks. In Proceeding of DIWANS.

  23. Fudenberg D., Tirole J. (1991) Game theory. MIT Press, Cambridge

    Google Scholar 

  24. Monderer D., Shapley L. (1996) Potential games. Games and Economic Behavior 14: 124–143

    Article  MathSciNet  MATH  Google Scholar 

  25. Jones C. E., Sivalingam K. M., Agrawal P., Chen J. C. (2001) A survey of energy efficient network protocols for wireless networks. Wireless Networks 7(4): 343–358

    Article  MATH  Google Scholar 

  26. Komali, R. S., & MacKenzie, A. B. (2009). Analyzing selfish topology control in multi-radio multi-channel multi-hop wireless networks. In Proceeding of IEEE ICC.

  27. Li, N., Hou, J. C., & Sha, L. (2003). Design and analysis of an MST-Based topology control algorithm. In Proceeding of IEEE INFOCOM.

  28. Muqattash, A., & Krunz, M. (2003). CDMA-based MAC protocol for wireless ad hoc networks. In Proceeding of ACM MobiHoc.

  29. Singh V. P., Kumar K. (2011) Literature survey on power control algorithms for mobile ad-hoc network. Wireless Personal Communications 60: 679–685

    Article  Google Scholar 

  30. Felegyhazi, M., Hubaux, J. P., & Buttyan, L. (2006). Nash equilibria of packet forwarding strategies in wireless ad hoc networks. IEEE Trans Mobile Computing, 5(5).

  31. Johnson D. S., Lenstra J. K., Rinnoy Kan A. H. G. (1978) The complexity of the network design problem. Networks 8: 279–285

    Article  MathSciNet  MATH  Google Scholar 

  32. Wong R.T. (1980) Worst case analysis of network design problem heuristics. SIAM Journal of Algorithms on Discrete Mathematics. 1: 51–63

    Article  MATH  Google Scholar 

  33. Wu B.Y., Chao K.M., Tang C.Y. (2000) Approximation algorithms for the shortest path total path length spanning tree problem. Elsevier Discrete Applied Mathematics 105: 273–289

    Article  MathSciNet  MATH  Google Scholar 

  34. Cormen T. H., Leiserson C. E., Rivest R. L. (1990) Introduction to algorithms. MIT Press, Cambridge

    MATH  Google Scholar 

  35. Mieghem P., Langen S. (2005) Influence of the link weight structure on the shortest path. Physical Review 71(056113): 1–13

    Google Scholar 

  36. Mieghem P., Magdalena S. M. (2005) Phase transition in the link weight structure of networks. Physical Review 72(056138): 2–7

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. ECE Department, University of Tehran, 14395-515, Tehran, Iran

    Sajjad Zarifzadeh

  2. Institute for Research in Fundamental Sciences (IPM), Tehran, Iran

    Nasser Yazdani

Authors
  1. Sajjad Zarifzadeh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nasser Yazdani
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sajjad Zarifzadeh.

Additional information

This research was conducted when S. Zarifzadeh was a visiting researcher in Georgia Tech, USA.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zarifzadeh, S., Yazdani, N. Neighbor Selection Game in Wireless Ad Hoc Networks. Wireless Pers Commun 70, 617–640 (2013). https://doi.org/10.1007/s11277-012-0711-6

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11277-012-0711-6

Keywords

Search

Navigation