A wireless ad hoc network is composed of several tiny and inexpensive device such as wireless sensor networks (WSNs) which have limited energy. In this network energy, efficiency is one of the most crucial requirements. Data transmitting in minimum power level is one way of maximizing energy efficiency. Thus, transmission power level of nodes should be managed in a smart way to improve energy efficiency. Topology control is one of the main algorithms used in a wireless network to decrease transmission power level while preserving network connectivity. Topology control could improve energy efficiency by reasonably tuning the transmission power level while preserving network connectivity in order to increase network capacity and lifetime. In pursuit of energy efficiency and connectivity, nodes can be selfish and are conflicting with each other. Therefore to overcome the conflict, game theory is used to construct energy efficient topology, as well as minimizing energy consumption. In this paper, the main goal and most recent energy efficient topology control algorithms in WSNs and ad hoc network are classified and studied according to their specific goals. 1. Introduction Wireless sensor networks (WSNs) are a particular type of ad hoc network, in which the nodes are autonomous. These nodes are tiny devices equipped with communication component, data computation, and sensing capability [1–3]. In this type of network, each node collects information from the target area and sends this information to a sink, through a multihop communication network. A wireless network consists of hundreds to thousands nodes, which are deployed either inside the target area or very close to the target area. Upon an event happening or during monitoring sessions, the wireless nodes will collect and report this information to the sink node for further analysis. These wireless networks can be used for many important applications such as health care, intrusion detection and plants control, weather monitoring, security and tactical surveillance, disaster monitoring, and ambient conditions detection [1, 4]. As an example, in forest fire early detection system [5], wireless temperature and smoke wireless nodes are installed in the forest to detect fire or smoke in its early stage, without deploying complicated wired structures. Another application is in a battlefield, a soldier can be aware of the status of friendly troops or the availability of equipment by their information collected from wireless networks [6]. Energy efficiency is one of the main requirements in sensor networks [7].
References
[1]
I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Communications Magazine, vol. 40, no. 8, pp. 102–105, 2002.
[2]
P. Santi and J. Simon, “Silence is golden with high probability: maintaining a connected backbone in wireless sensor networks,” in Wireless Sensor Networks, pp. 106–121, 2004.
[3]
P. Santi, “Topology control in wireless ad hoc and sensor networks,” ACM Computing Surveys, vol. 37, no. 2, pp. 164–194, 2005.
[4]
S. E. Calvano, W. Xiao, D. R. Richards et al., “A network-based analysis of systemic inflammation in humans,” Nature, vol. 437, no. 7061, pp. 1032–1037, 2005.
[5]
N. Mladineo and S. Knezic, “Optimisation of forest fire sensor network using gis technology,” in Proceedings of the 22nd International Conference on Information Technology Interfaces (ITI '02), pp. 391–396, 2000.
[6]
L. Ritchie, S. Deval, M. Reisslein, and A. W. Richa, “Evaluation of physical carrier sense based spanner construction and maintenance as well as broadcast and convergecast in ad hoc networks,” Ad Hoc Networks, vol. 7, no. 7, pp. 1347–1369, 2009.
[7]
R. S. Komali, A. B. MacKenzie, and R. P. Gilles, “Effect of selfish node behavior on efficient topology design,” IEEE Transactions on Mobile Computing, vol. 7, no. 9, pp. 1057–1070, 2008.
[8]
T. M. Chiwewe and G. P. Hancke, “A distributed topology control technique for low interference and energy efficiency in wireless sensor networks,” IEEE Transactions on Industrial Informatics, vol. 8, no. 1, pp. 11–19, 2012.
[9]
R. S. Komali and A. B. MacKenzie, “Distributed topology control in ad-hoc networks: a game theoretic perspective,” in Proceedings of the 3rd IEEE Consumer Communications and Networking Conference (CCNC '06), pp. 563–568, January 2006.
[10]
Z. Mi and Y. Yang, “Topology control and coverage enhancement of dynamic networks based on the controllable movement of mobile agents,” in Proceedings of the IEEE International Conference on Communications (ICC '11), pp. 1–5, June 2011.
[11]
S.-C. Wang, D. S. L. Wei, and S.-Y. Kuo, “An SPT-based topology control algorithm for wireless ad hoc networks,” Computer Communications, vol. 29, no. 16, pp. 3092–3103, 2006.
[12]
Y. Wang, “Topology control for wireless sensor networks,” in Wireless Sensor Networks and Applications, pp. 113–147, 2008.
[13]
C. Song, M. Liu, J. Cao, Y. Zheng, H. Gong, and G. Chen, “Maximizing network lifetime based on transmission range adjustment in wireless sensor networks,” Computer Communications, vol. 32, no. 11, pp. 1316–1325, 2009.
[14]
X. Wu, G. Chen, and S. K. Das, “Avoiding energy holes in wireless sensor networks with nonuniform node distribution,” IEEE Transactions on Parallel and Distributed Systems, vol. 19, no. 5, pp. 710–720, 2008.
[15]
X.-C. Hao, Y.-X. Zhang, N. Jia, and B. Liu, “Virtual game-based energy balanced topology control algorithm for wireless sensor networks,” Wireless Personal Communications, pp. 1–20, 2012.
[16]
C. Schurgers, V. Tsiatsis, and M. B. Srivastava, “Stem: topology management for energy efficient sensor networks,” in IEEE Aerospace Conference Proceedings, vol. 3, pp. 1099–1108, 2002.
[17]
S. Zarifzadeh, A. Nayyeri, and N. Yazdani, “Efficient construction of network topology to conserve energy in wireless ad hoc networks,” Computer Communications, vol. 31, no. 1, pp. 160–173, 2008.
[18]
S. Rizvi, H. K. Qureshi, S. Ali Khayam, V. Rakocevic, and M. Rajarajan, “A1: an energy efficient topology control algorithm for connected area coverage in wireless sensor networks,” Journal of Network and Computer Applications, vol. 35, no. 2, pp. 597–605, 2012.
[19]
S. Eidenbenz, V. S. A. Kumar, and S. Zust, “Equilibria in topology control games for ad hoc networks,” Mobile Networks and Applications, vol. 11, no. 2, pp. 143–159, 2006.
[20]
R. S. Komali, R. W. Thomas, L. A. Dasilva, and A. B. MacKenzie, “The price of ignorance: distributed topology control in cognitive networks,” IEEE Transactions on Wireless Communications, vol. 9, no. 4, pp. 1434–1445, 2010.
[21]
S. Zarifzadeh and N. Yazdani, “Neighbor selection game in wireless ad hoc networks,” Wireless Personal Communications-, vol. 70, no. 2, pp. 617–640, 2013.
[22]
M. J. Osborne, An Introduction to Game Theory, vol. 3, Oxford University Press, New York, NY, USA, 2004.
[23]
J. Ratliff, “A folk theorem sampler. Lecture notes,” 2010, http://www.virtualperfection.com/gametheory/5.3.FolkTheoremSampler.1.0.pdf.
[24]
G. Arslan and J. S. Shamma, “Distributed convergence to nash equilibria with local utility measurements,” in Proceedings of the 43rd IEEE Conference on Decision and Control (CDC '04), pp. 1538–1543, December 2004.
[25]
J. R. Marden, G. Arslan, and J. S. Shamma, “Joint strategy fictitious play with inertia for potential games,” IEEE Transactions on Automatic Control, vol. 54, no. 2, pp. 208–220, 2009.
[26]
D. Monderer and L. S. Shapley, “Potential games,” Games and Economic Behavior, vol. 14, no. 1, pp. 124–143, 1996.
[27]
W. Poundstone and N. Metropolis, “Prisoner’s dilemma: John von neumann, game theory, and the puzzle of the bomb,” Physics Today, vol. 45, article 73, 1992.
[28]
J. Liu and B. Li, “Distributed topology control in wireless sensor networks with asymmetric links,” in IEEE Global Telecommunications Conference (GLOBECOM '03), pp. 1257–1262, December 2003.
[29]
H. Zhang and J. C. Hou, “Maintaining sensing coverage and connectivity in large sensor networks,” Ad Hoc & Sensor Wireless Networks, vol. 1, no. 1-2, pp. 89–124, 2005.
[30]
X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless, and C. Gill, “Integrated coverage and connectivity configuration in wireless sensor networks,” in Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys '03), pp. 28–39, November 2003.
[31]
P. Gupta and P. R. Kumar, “The capacity of wireless networks,” IEEE Transactions on Information Theory, vol. 46, no. 2, pp. 388–404, 2000.
[32]
R. Ramanathan and R. Rosales-Hain, “Topology control of multihop wireless networks using transmit power adjustment,” in Proceedings of a IEEE 19th Annual Joint Conference of the Computer and Communications Societies (INFOCOM '00), vol. 2, pp. 404–413, March 2000.
[33]
M. Kadivar, M. E. Shiri, and M. Dehghan, “Distributed topology control algorithm based on one- and two-hop neighbors' information for ad hoc networks,” Computer Communications, vol. 32, no. 2, pp. 368–375, 2009.
[34]
H. Sethu and T. Gerety, “A new distributed topology control algorithm for wireless environments with non-uniform path loss and multipath propagation,” Ad Hoc Networks, vol. 8, no. 3, pp. 280–294, 2010.
[35]
S. Zarifzadeh, N. Yazdani, and A. Nayyeri, “Energy-efficient topology control in wireless ad hoc networks with selfish nodes,” Computer Networks, vol. 56, no. 2, pp. 902–914, 2012.
[36]
N. Li, J. C. Hou, and L. Sha, “Design and analysis of an MST-based topology control algorithm,” IEEE Transactions on Wireless Communications, vol. 4, no. 3, pp. 1195–1206, 2005.
[37]
R. Wattenhofer and A. Zollinger, “XTC: a practical topology control algorithm for ad-hoc networks,” in Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS '04), pp. 2969–2976, April 2004.
[38]
P. Santi and D. M. Blough, “The critical transmitting range for connectivity in sparse wireless ad hoc networks,” IEEE Transactions on Mobile Computing, vol. 2, no. 1, pp. 25–39, 2003.
[39]
J. Yu, H. Roh, W. Lee, S. Pack, and D. -Z. Du, “Topology control in cooperative wireless ad-hoc networks,” IEEE Journal on Selected Areas in Communications, vol. 30, no. 9, pp. 1771–1779, 2012.
[40]
J. Li and P. Mohapatra, “Analytical modeling and mitigation techniques for the energy hole problem in sensor networks,” Pervasive and Mobile Computing, vol. 3, no. 3, pp. 233–254, 2007.
[41]
M. Cardei, J. Wu, and S. Yang, “Topology control in ad hoc wireless networks using cooperative communication,” IEEE Transactions on Mobile Computing, vol. 5, no. 6, pp. 711–724, 2006.
[42]
X. Chu and H. Sethu, “Cooperative topology control with adaptation for improved lifetime in wireless ad hoc networks,” in Proceedings of the 28th IEEE International Conference on Computer Communications (INFOCOM '12), pp. 262–270, 2012.
[43]
S. Olariu and I. Stojmenovi？, “Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting,” in Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM '06), vol. 6, pp. 1–12, April 2006.
[44]
R. Sun, J. Yuan, I. You, X. Shan, and Y. Ren, “Energy-aware weighted graph based dynamic topology control algorithm,” Simulation Modelling Practice and Theory, vol. 19, no. 8, pp. 1773–1781, 2011.
[45]
C.-Y. Lee, L.-C. Shiu, F.-T. Lin, and C.-S. Yang, “Distributed topology control algorithm on broadcasting in wireless sensor network,” Journal of Network and Computer Applications, vol. 36, pp. 1186–1195, 2013.
[46]
V. Srivastava, J. Neel, A. B. MacKenzie, et al., “Using game theory to analyze wireless ad hoc networks,” IEEE Communications Surveys and Tutorials, vol. 7, no. 4, pp. 46–56, 2005.
[47]
M. D. Penrose, “The longest edge of the random minimal spanning tree,” The Annals of Applied Probability, vol. 7, no. 2, pp. 340–361, 1997.
[48]
L. M. Kirousis, E. Kranakis, D. Krizanc, and A. Pelc, “Power consumption in packet radio networks,” Theoretical Computer Science, vol. 243, no. 1-2, pp. 289–305, 2000.
[49]
A. E. F. Clementi, P. Penna, and R. Silvestri, “Hardness results for the power range assignment problem in packet radio networks,” in Algorithms and Techniques of Randomization, Approximation, and Combinatorial Optimization, pp. 197–208, 1999.
[50]
J. Lian, K. Naik, and G. B. Agnew, “Data capacity improvement of wireless sensor networks using non-uniform sensor distribution,” International Journal of Distributed Sensor Networks, vol. 2, no. 2, pp. 121–145, 2006.
[51]
A. Jarry, P. Leone, O. Powell, and J. Rolim, “An optimal data propagation algorithm for maximizing the lifespan of sensor networks,” in Distributed Computing in Sensor Systems, pp. 405–421, 2006.
[52]
S. Yuen and B. Li, “Strategyproof mechanisms towards dynamic topology formation in autonomous networks,” Mobile Networks and Applications, vol. 10, no. 6, pp. 961–970, 2005.
[53]
P. Santi, S. Eidenbenz, and G. Resta, “A framework for incentive compatible topology control in non-cooperative wireless multi-hop networks,” in Proceedings of the Workshop on Dependability Issues in Wireless Ad Hoc Networks and Sensor Networks (DIWANS '06), pp. 9–18, September 2006.
[54]
K. Miyao, H. Nakayama, N. Ansari, and N. Kato, “LTRT: an efficient and reliable topology control algorithm for ad-hoc networks,” IEEE Transactions on Wireless Communications, vol. 8, no. 12, pp. 6050–6058, 2009.
[55]
N. Li and J. C. Hou, “Localized topology control algorithms for heterogeneous wireless networks,” IEEE/ACM Transactions on Networking, vol. 13, no. 6, pp. 1313–1324, 2005.
