Optimal and Heuristic Algorithms for the Power-Based QoS Multiple Routing Problem for Mobile Ad Hoc Networks

Abstract

在本篇論文中，我們將要探討如何為隨意網路之多個來源節點找尋多條路徑來將它們的資料封包繞送到它們各自的目的節點並且保證在整個資料封包的繞送過程中都不會發生電力不足的情況。這個問題已經被証明是一個NP-complete問題。在本篇論文中，根據網路流量的原理和線性規劃的技巧，我們將提出一個整數線性規劃公式來求解這個問題的最佳解。此外，基於Dijkstra’s演算法的技巧，我們也將提出擁有較低時間複雜度的啟發式演算法來求解這個問題的次佳解。電腦模擬結果顯示我們的啟發式演算法所求得的次佳解是相當接近最佳解的。

In this paper, we will consider the problem of searching for multiple paths between multiple pairs of sources and destinations satisfying the power requirement in a mobile ad hoc network. The problem has been proved to be an NP-complete problem. In this paper, according to the principle of network flow and linear programming techniques, we will propose an integer linear programming formula to generate the optimal solution for this problem. Furthermore, based on the Dijkstra’s algorithm, efficient heuristic algorithms with low time complexities are developed. Computer simulations verify that the suboptimal solutions generated by our heuristic algorithms are very close to the optimal ones.