The Multi-Constrained Dynamic Programming Problem in View of Routing Strategies in Wireless Mesh Networks
Sabreen Mahmood Shukr, Nuha A. S. Alwan, Ibraheem Kassim Ibraheem · 2012
We address the problem of satisfying multiple constraints in a shortest-path Dijkstra-based dynamic programming (DP) framework. We solve this problem considering its applicability to routing in wireless mesh networks. Our work, therefore, relates to quality-ofservice (QoS) metrics such as bandwidth, delay and the number of hops between network nodes. The present work is based on the optimization of one or more metrics while bounding the other. Specifically, we compute high-capacity paths while simultaneously bounding the end-to-end delay and the number of hops to an upper limit. We prospectively call the resulting algorithm the comprehensive mesh routing algorithm (CMRA). We show by computer simulations that the proposed algorithm features wide versatility when dealing with multiple constraints as compared to other approaches involving the optimization of a weighting function. This latter technique is not easily applicable to wireless networks due to different networking metrics having values with widely different orders of magnitude.