Open Access Open Access  Restricted Access Subscription or Fee Access

Performance Comparison of ILP Models for QoS Topology Control to Conserve Energy in WANETs


(*) Corresponding author


Authors' affiliations


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


WANET; Ad hoc; Wireless; Topology Control; Network Topology; QoS; ILP; Complexity Analysis; Performance Evaluation

Full Text:

PDF


References


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