Please use this identifier to cite or link to this item:

Title: Optimal and Heuristic Algorithms for the Power-Based QoS Multiple Routing Problem for Mobile Ad Hoc Networks
Authors: Sheu, Pi-Rong
Chien, Chia-Hung
Liao, Wei-Sheng
Li, Yu-Ting
Chen, Zhi-Cheng
Keywords: 隨意網路;多重路徑繞送;電力考量;路徑繞送;服務品質
Ad Hoc Network;Multiple Routing;Power-Aware;Routing;Quality of Service
Date: 2005
Issue Date: 2017-10-23 14:22:06 (UTC+8)
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.
Relation: TANET 2005 台灣網際網路研討會論文集
Data Type: conference
Appears in Collections:[TANET 台灣網際網路研討會] 會議論文

Files in This Item:

File Description SizeFormat
450.pdf245KbAdobe PDF131View/Open

All items in 學術集成 are protected by copyright, with all rights reserved.

社群 sharing