無線中繼網路具服務品質保證之鏈路排程演算法

Link Scheduling with Hard QoS Guarantees for Wireless Relay Networks

洪啟堯(Chi-Yao Hong)

指導教授 ： 逄愛君

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.00201

摘要

近年來，由於中繼台在無線寬頻網路所帶來之龐大優勢，無線中繼網路的相關研究正逐漸受到重視；在這之中，設計一套有效的資源分配方法則為目前之首要課題。基於WiMAX系統之中繼模式，本論文證明，具頻寬及延遲保證的鏈路排程問題，難以在多項式時間內獲得理想的近似解。為最佳化系統效能，本論文更進一步提出一套有效率的排程機制，根據理論分析，該機制之效能可在多數實際環境下有效逼近於最佳解。我們也發展出一個模擬模型，以對本系統進行更精確的效能評估。實驗結果證實，本論文所提出之機制的平均效能相當理想。

關鍵字

無線中繼網路 ； 鏈路排程 ； 服務品質 ； 近似演算法 ； 最佳化

並列摘要

The emerging wireless relay networks (WRNs) are expected to provide the improvement on throughput and the extension of coverage area for next-generation wireless systems. We study an optimization problem for multi-hop link scheduling with bandwidth and delay guarantees over WRNs. Our optimization problem is investigated under a general interference model with a generic objective. The objective can be based on various kinds of performance indexes (e.g., throughput, fairness and capacity) determined by service providers. Through the theoretical analysis, the intractability and in-approximability of the optimization problem are shown. Due to the intractable computational complexity, we present efficient algorithms to practically provide a small approximation factor against any optimal solution even for a worst-case input. Furthermore, the experimental results indicate that our presented algorithms yield near-optimal performance in the average case.

並列關鍵字

Wireless Relay Networks ； Link Scheduling ； Quality of Service ； Approximation Algorithm ； Optimization

參考文獻

[1] “IEEE 802.16-2004, Air interface for fixed broadband wireless access systems,” Piscataway, NJ, 2004.

[2] E. Arikan, “Some complexity results about packet radio networks,” IEEE Trans. Intell. Transp. Syst., vol. iT-30, pp. 910–918, Jul. 1984.

[3] H. Viswanathan and S. Mukherjee, “Throughput-range tradeoff of wireless mesh backhaul networks,” IEEE J. Sel. Areas Commun., vol. 24, pp. 593–602, Mar. 2006.

[4] T. Jian, X. Guoliang, C. Chandler, and Z.Weiyi, “Link scheduling with power control for throughput enhancement in multihop wireless networks,” IEEE Trans. Veh. Technol., vol. 55, pp. 733–742, May 2006.

[5] A. Behzad and I. Rubin, “Optimum integrated link scheduling and power control for multihop wireless networks,” IEEE Trans. Veh. Technol., vol. 56, pp. 194–205, Jan. 2007.