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.
Similar content being viewed by others
References
Ramanathan, R., & Rosales-Hain, R. (2000). Topology control of multihop wireless networks using transmit power adjustment. In Proceeding of IEEE INFOCOM.
Santi, P. (2005). Topology control in wireless ad hoc and sensor networks. ACM Computing Surveys, 37(2).
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.
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
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.
Ganjali, Y., & Keshavarzian, A. (2004). Load balancing in ad hoc networks: single-path routing vs. multi-path routing. In Proceeding of IEEE INFOCOM.
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).
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
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).
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).
Al-Karaki J. N., Kamal A. E. (2008) Stimulating node cooperation in mobile ad hoc networks. Wireless Personal Communications 44: 219–239
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.
Komali, R. S., & MacKenzie, A. B. (2006). Distributed topology control in ad hoc networks: A game theoretic perspective. In Proceeding of IEEE CCNC.
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
Zarifzadeh, S., Nayyeri, A., & Yazdani, N. (2012). Energy-efficient topology control in wireless ad hoc networks with selfish nodes. Elsevier Computer Networks, 56(2).
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.
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
Hao, X. C., & Zhang, Y. X. (2012). Virtual game-based energy balanced topology control algorithm for wireless sensor networks. Wireless Personal Communications.
Chu, X., & Sethu, H. (2012). Cooperative topology control with vdaptation for improved lifetime in wireless ad hoc networks. In Proceeding of IEEE INFOCOM.
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.
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.
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.
Fudenberg D., Tirole J. (1991) Game theory. MIT Press, Cambridge
Monderer D., Shapley L. (1996) Potential games. Games and Economic Behavior 14: 124–143
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
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.
Li, N., Hou, J. C., & Sha, L. (2003). Design and analysis of an MST-Based topology control algorithm. In Proceeding of IEEE INFOCOM.
Muqattash, A., & Krunz, M. (2003). CDMA-based MAC protocol for wireless ad hoc networks. In Proceeding of ACM MobiHoc.
Singh V. P., Kumar K. (2011) Literature survey on power control algorithms for mobile ad-hoc network. Wireless Personal Communications 60: 679–685
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).
Johnson D. S., Lenstra J. K., Rinnoy Kan A. H. G. (1978) The complexity of the network design problem. Networks 8: 279–285
Wong R.T. (1980) Worst case analysis of network design problem heuristics. SIAM Journal of Algorithms on Discrete Mathematics. 1: 51–63
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
Cormen T. H., Leiserson C. E., Rivest R. L. (1990) Introduction to algorithms. MIT Press, Cambridge
Mieghem P., Langen S. (2005) Influence of the link weight structure on the shortest path. Physical Review 71(056113): 1–13
Mieghem P., Magdalena S. M. (2005) Phase transition in the link weight structure of networks. Physical Review 72(056138): 2–7
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was conducted when S. Zarifzadeh was a visiting researcher in Georgia Tech, USA.
Rights 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
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11277-012-0711-6