A Comparative Study of Single-Constraint Routing in Wireless Mesh Networks Using Different Dynamic Programming Algorithms
Main Article Content
Abstract
Finding the shortest route in wireless mesh networks is an important aspect. Many techniques are used to solve this problem like dynamic programming, evolutionary algorithms, weighted-sum techniques, and others. In this paper, we use dynamic programming techniques to find the shortest path in wireless mesh networks due to their generality, reduction of complexity and facilitation of numerical computation, simplicity in incorporating constraints, and their onformity to the stochastic nature of some problems. The routing problem is a multi-objective optimization problem with some constraints such as path capacity and end-to-end delay. Single-constraint routing problems and solutions using Dijkstra, Bellman-Ford, and Floyd-Warshall algorithms are proposed in this work with a discussion on the difference between them. These algorithms find the shortest route through finding the optimal rate between two nodes in the wireless networks but with bounded end-to-end delay. The Dijkstra-based algorithm is especially favorable in terms of processing time. We also present a comparison between our proposed single-constraint Dijkstra-based routing algorithm and the mesh routing algorithm (MRA) existing in the literature to clarify the merits of the former.
Article Details
How to Cite
Publication Dates
References
Allard G. and Jacquent, P.H.,2004,”Heuristic for Bandwidth Reservation in Multihop Wireless Networks,” INRIA Rocquencourt, No. 5075, January.
Camen T. H., Leiserson C. E., Rivest R. L. and Stein C., 2001, “Introduction to Algorithms”, 2nd Edition.
Capone A., Carello G., Filippini I., Gualandi S. and Malucelli F., 2010, “Routing, Scheduling and Channel Assignment in Wireless Mesh Networks: Optimization Models and Algorithms”, Ad Hoc Networks, vol. 8, no. 6, August, pp. 545-563.
Cheng H., Xiong N., Vasilakos, A. V., Yang L. T., Chen G. and Zhuang, X., 2012, “Nodes Organization for Channel Assignment with Topology Preservation in Multi-Radio Wireless Mesh Networks”, Ad Hoc Networks, vol. 10, no. 5, pp. 760-773.
Crichigno J., Khoury J., Wu M. Y. and Shu W., 2008, “A Dynamic Programming Approach for Routing in Wireless Mesh Networks,” IEEE Global Telecommunications Conference, pp. 1-5.
Dasgupta, S., Papadimitriou, C. and Vazirani, U., 2007 “Algorithms”, McGraw-Hill.
Doerr B., Eremeev A., Horoba C., Neumann F. and Theili M., 2009, “Evolutionary Algorithms and Dynamic Programming”, GECCO’09: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, ACM, New York, NY, USA, 8-12 July, pp. 771-778.
Glisic, S. and Lorenzo, B., 2009,"Advanced Wireless Networks", 2nd edition, Wiley, July.
Helonde, J. B., Wavhai, V., Deshpande, V. S. and Bhagwat, L. B.,2011,"Performance Analysis of Mesh Routing Algorithm for Routing Metrics Link Capacity and Delay Against Inter-Arrival Time Dependencies”, WOCN: Proceedings in 8th International Conference on Wireless and Optical Communications Networks.
Ilaboya, R., Atikpo, E., Ekoh, G. O., Ezugwu, M. O. and Umokoro, L., 2011, “Application of Dynamic Programming to Solving Reservoir Operational Problems”, Journal of Applied Technology in Environmental Sanitation, vol. 1, no. 3, October, pp. 251-262.
Kowalik K. and Davis M., 2006, “Why Are There So Many Routing Rrotocols for Wireless Mesh Networks”, Irish Signal and Systems Conference, Dublin, 28-30 June.
Lew A. and Mauch H.,2007, “Dynamic Programming: A Computational Tool”, New York: Springer-Verlag, Berlin Heidelberg,.
Marina, M. K., Das, S. R. and Subramanian, A. P., 2010, “A Topology Control Approach for Utilizing Multiple Channels in Multi-Radio Wireless Mesh Networks”, International Journal of Computer and Telecommunications Networking, vol. 54, no. 2, February, pp. 241-256.
Moon, T. K. and Stirling, W. C.,2000 ,“Mathematical Methods and Algorithms for Signal Processing”, Upper Saddle River, New Jersey: Prentice-Hall,.
Mountassir, T., Nassereddine, B., Haqiq, A. and Bennani, S., 2012, “Wireless Mesh Networks Topology Auto Planning”, International Journal of Computer Applications (0975 – 8887), vol. 52, no. 2, August, pp. 27-33.
Raja N. K., Saritha, R., Senthamaraiselvan, A. and Arulanandam, K.,2012,“QSWMCA -Quality of Service in Wireless Mesh Networks by Configuration Arguments”, International Journal of Computer Network and Information Security, vol. 4, no. 6, June, pp. 1-9.
Shukr, S. M., Alwan, N. A. S. and Ibraheem, I. K.,2012, "The Multi-Constrained Dynamic Programming Problem in View of Routing Strategies in Wireless Mesh Networks”, International Journal of Information and Communication Technology Research, vol. 2, no. 6, June, pp. 471-476.
Stallings, W., 2011, “Data and Computer Communications”, Ninth Edition, Prentice Hall,.