Performance Comparison of ILP Models for QoS Topology Control to Conserve Energy in WANETs
(*) Corresponding author
DOI: https://doi.org/10.15866/irecap.v5i6.7653
Abstract
Within the objective of conserving energy, in our previous paper we treated the Topology Control as an optimization problem, where the objective function was to reduce the overall energy consumed by all nodes in the network and the constraints were the traffic bandwidth and the maximum hop-count. To capitalize and refine the results of our first work, this paper discusses the computational complexity and the performance evaluation of two QoS ILP-based models: The Routing-IP model that we proposed and another QoS model extracted from the literature. Having implemented those models, we then conducted an extensive experimental comparison of the performance of both models in dense networks up to 700 nodes. To properly measure the effectiveness of those models, we used performance metrics namely: Execution time, Number of solved nodes/Number of simplex iterations and Statistics model. Simulation results demonstrate that our proposed model Routing-IP outperforms the other model. Indeed, it converges faster while needing less processing and memory resources.
Copyright © 2015 Praise Worthy Prize - All rights reserved.
Keywords
Full Text:
PDFReferences
Hanzo, Lajos and Tafazolli, Rahim. A survey of QoS routing solutions for mobile ad hoc networks. Communications Surveys & Tutorials, IEEE, 2007, vol. 9, no 2, p. 50-70.
http://dx.doi.org/10.1109/comst.2007.382407
Santhi, G. and Nachiappan, Alamelu. A survey of QoS routing protocols for mobile ad hoc networks. International journal of computer science & information Technology (IJCSIT) Vol, 2010, vol. 2.
http://dx.doi.org/10.5121/ijcsit.2010.2411
Paolo Santi, Topology Control in Wireless Ad Hoc and Sensor Networks. John Wiley & Sons, 2005, pp. 16.
https://dx.doi.org/ 10.1002/0470094559
Fadoua, Yakine and Abdellah Idrissi, Energy-Aware Topology Control And Qos Routing In Ad-Hoc Networks, Procedia Computer Science, 2015, vol. 56, p. 309-316.
http://dx.doi.org/10.1016/j.procs.2015.07.213
Jia, Xiaohua, Li, Deying, and Du, Dingzhu. QoS topology control in ad hoc wireless networks. In: INFOCOM 2004. Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE, 2004. p. 1264-1272.
http://dx.doi.org/10.1109/infcom.2004.1357012
Chen, Wen-Tsuen and Huang, Nen-Fu. The strongly connecting problem on multihop packet radio networks. Communications, IEEE Transactions on, 1989, vol. 37, no 3, p. 293-295.
http://dx.doi.org/10.1109/26.20105
Cheng, Xiaochun, Cardei, Mihaela, Sun, Jianhua, et al. Topology control of ad hoc wireless networks for energy efficiency. Computers, IEEE Transactions on, 2004, vol. 53, no 12, p. 1629-1635.
http://dx.doi.org/10.1109/tc.2004.121
Lloyd, Errol L., Liu, Rui, Marathe, Madhav V., et al. Algorithmic aspects of topology control problems for ad hoc networks. Mobile Networks and applications, 2005, vol. 10, no 1-2, p. 19-34.
http://dx.doi.org/10.1023/b:mone.0000048543.95178.f5
Ramanathan, Ram Et Rosales-Hain, Regina. Topology control of multihop wireless networks using transmit power adjustment. In: INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE. IEEE, 2000. p. 404-413.
http://dx.doi.org/10.1109/infcom.2000.832213
Li, Ning, Hou, Jennifer C., and Sha, Lui. Design and analysis of an MST-based topology control algorithm. Wireless Communications, IEEE Transactions on, 2005, vol. 4, no 3, p. 1195-1206.
http://dx.doi.org/10.1109/twc.2005.846971
Li, Li, Halpern, Joseph Y., Bahl, Paramvir, et al. Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks. In: Proceedings of the twentieth annual ACM symposium on Principles of distributed computing. ACM, 2001. p. 264-273.
http://dx.doi.org/10.1145/383962.384043
Huang, Zhuochuan, Shen, Chien-Chung, Srisathapornphat, Chavalit, et al. Topology control for ad hoc networks with directional antennas. In: Computer Communications and Networks, 2002. Proceedings. Eleventh International Conference on. IEEE, 2002. p. 16-21.
http://dx.doi.org/10.1109/icccn.2002.1043039
Marsan, Marco Ajmone, Chiasserini, Carla F., Nucci, Antonio, et al. Optimizing the topology of Bluetooth wireless personal area networks. In: INFOCOM 2002. Twenty-first annual joint conference of the IEEE computer and communications societies. Proceedings. IEEE. IEEE, 2002. p. 572-579.
http://dx.doi.org/10.1109/INFCOM.2002.1019302
Liu, Hai, Li, Deying, and Jia, Xiaohua. QoS topology control with minimal total energy cost in Ad hoc wireless networks. In: Mobile Ad-hoc and Sensor Networks. Springer Berlin Heidelberg, 2006. p. 622-637.
http://dx.doi.org/10.1007/11943952_53
Li, Deying, Jia, Xiaohua, and Du, Hongwei. QoS topology control for nonhomogenous ad hoc wireless networks. EURASIP Journal on Wireless Communications and Networking, 2006, vol. 2006, no 2, p. 43-43.
http://dx.doi.org/10.1155/wcn/2006/82417
Cheng, Xiaochun, Cardei, Mihaela, Sun, Jianhua, et al. Topology control of ad hoc wireless networks for energy efficiency. Computers, IEEE Transactions on, 2004, vol. 53, no 12, p. 1629-1635.
http://dx.doi.org/10.1109/tc.2004.121
A. Idrissi, 2012. How to minimize the energy consumption in mobile ad-hoc networks. International Journal of Artificial Intelligence & Applications, 3: 1-10.
http://dx.doi.org/10.5121/ijaia.2012.3201
A. Idrissi, C.M. Li, J.F. Myoupo, 2006. An algorithm for a constraint optimization problem in mobile adhoc networks. Proceeding of the 18th IEEE International Conference on Tools with Artificial Intelligence, Nov. 13-15, IEEE Xplore Press, Arlington, VA., pp: 55-562.
http://dx.doi.org/10.1109/ICTAI.2006.29
A. Idrissi and F. Yakine, “ Multicast routing with quality of service constraints in the Ad Hoc wireless networks”. J. Comput. Sci.,10,(2014):1839-1849.
http://dx.doi.org/10.3844/jcssp.2014.1839.1849
F. Yakine and A. Idrissi, “Delay-constrained efficient multicast routing in wireless Ad Hoc networks.” In : Next Generation Networks and Services (NGNS), 2014 Fifth International Conference on. IEEE, (2014): 289-294.
http://dx.doi.org/10.1109/ngns.2014.6990266
Deo Narsingh. Graph theory with applications to engineering and computer science. PHI Learning Pvt. Ltd., 2004 pp: 32.
Wieselthier, Jeffrey E., Nguyen, Gam D., and Ephremides, Anthony. On the construction of energy-efficient broadcast and multicast trees in wireless networks. In: INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE. IEEE, 2000. p. 585-594.
http://dx.doi.org/10.1109/infcom.2000.832232
Das, Amal K., Marks, Robert J., El-Sharkawi, Mohamed, and al. Minimum power broadcast trees for wireless networks: integer programming formulations. In : INFOCOM 2003. TwentySecond Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies. IEEE, 2003. p. 1001-1010.
http://dx.doi.org/10.1109/infcom.2003.1208937
AMPL Optimization LLC http://www.ampl.com
IBM ILOG CPLEX Optimizer , http://www-01.ibm.com/software/integration/optimization/cplex-optimizer
Ausiello, Giorgio, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, and Marco Protasi. Complexity and approximation: Combinatorial optimization problems and their approximability properties. Springer Science & Business Media, 2012.
http://dx.doi.org/10.1007/978-3-642-58412-1_1
Patel, Jagat, and John W. Chinneck. "Active-constraint variable ordering for faster feasibility of mixed integer linear programs." Mathematical Programming 110.3 (2007): 445-474.
http://dx.doi.org/10.1007/s10107-006-0009-0
IBM ILOG CPLEX V12.1, 2009. User’s Manual. IBM ILOG CPLEX V12.1.
http://dx.doi.org/10.2478/v10177-012-0052-0
Brearley, A. L., Gautam Mitra, and H. Paul Williams. "Analysis of mathematical programming problems prior to applying the simplex algorithm." Mathematical programming 8, no. 1 (1975): 54-83.
http://dx.doi.org/10.1007/bf01580428
CPLEX, ILOG AMPL. "System Version 10.0 User’s Guide." (2006):p.70.
“Guidelines for estimating CPLEX memory requirements based on problem size”, Retrieved March 11, 2015, from http://www-01.ibm.com/support/docview.wss?uid=swg2139993
Z.Sheng and C. H. Liu. Energy Efficient Cooperative Wireless Communication and Networks. CRC Press (2014): p.142.
http://dx.doi.org/10.1201/b17657
Saeed, S., Ismail, M., Hassan, R., Al-Hemyari, A., Flow-based admission control and QoS maintenance for real time traffic over MANETs, (2014) International Review on Computers and Software (IRECOS), 9 (10), pp. 1712-1720.
http://dx.doi.org/10.15866/irecos.v9i10.3929
Manohari, D., Anandha Mala, G.S., Swarm Based Topology Control for Fault Tolerance in MANET, (2013) International Review on Computers and Software (IRECOS), 8 (4), pp. 1037-1044.
Yan, G., Peng, Y., Huang, B., A hierarchical QoS routing algorithm based on VMN for MANET, (2013) International Review on Computers and Software (IRECOS), 8 (2), pp. 627-631.
Rathan, K., Bandwidth allocation in wireless mesh network using efficient path selection scheme, (2015) International Review on Computers and Software (IRECOS), 10 (6), pp. 545-551.
http://dx.doi.org/10.15866/irecos.v10i6.5714
Thangadurai, N., Dhanasekaran, R., Karthika, R.D., Dynamic traffic energy efficient topology based routing protocol for wireless Ad hoc sensor networks, (2013) International Review on Computers and Software (IRECOS), 8 (5), pp. 1141-1148.
Shankar, T., Shanmugavel, S., Karthikeyan, A., Nadeem, A., Multivariate Gaussian mean distributed network topology for energy efficient communication in wireless sensor networks, (2013) International Review on Computers and Software (IRECOS), 8 (5), pp. 1203-1208.
Refbacks
- There are currently no refbacks.
Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2024 Praise Worthy Prize