考慮服務品質限制之具最大比率合成能力中繼站無線網路成本最小化建置與路由策略

Abstract

近來，寬頻無線網路蓬勃發展，802.16j作為其中一項正在制定並且受到高度關注的新興標準，引入了中繼站 (relays) 的概念並且擁有以下兩點最重要的優勢：1. 中繼站作為基地台 (base station) 和用戶 (mobile station) 的中介點，可以接收基地台的信號，加強並傳送到用戶端，反之亦然，並藉此達到延伸基地台服務覆蓋率的目的。 2. 在802.16j的標準中，相容多樣中繼 (diversity relaying) 的技術，利用一些增益合成 (gain combining) 的原理，如最大比率合成(maximal ration combining)，可以在用戶端收到加總的訊噪比 (signal-to-noise)，而達到降低位元錯誤率 (bit error rate)、提高信賴度 (reliability) 的效果。 本篇論文中，在中繼站無線網路架設的問題下，關於中繼站要建置在何處以及多少數量的中繼站必須被建置的問題，我們提出了確實的解決方案以達到整體建置成本最小的目的。並且在過程中，我們發展出一套群播樹 (multicast tree)路由的演算法，來確保用戶需要的頻寬以及滿足服務品質 (QoS) 的要求。 我們將整個問題數學模式化為一個嚴謹的混合式整數線性最佳化模型，目標函式為最小化中繼站建置成本，此數學問題在本質上具有高度的複雜性和困難度。本論文採用拉格蘭日鬆弛法為基礎來處理此一複雜的問題，並根據所得到的結果改良演算法並求的最後的結果。根據實驗結果顯示，本篇論文不僅能有效率的求得此問題解，且在問題解的效能上更比其他既有的演算法更為優越。

Recently, broadband wireless networks have become greatly popular and among these, IEEE 802.16j, which is a developing standard, is attracting considerable interests. The concept of adopting relays, which is the main focus of 802.16j, has two major advantages. Firstly, relays can serve as inter-mediums between base stations (BSs) and mobile stations (MSs) to repeat signals on both directions for the purpose of coverage extensions. Secondly, cooperatively relaying techniques are exploited in 802.16j to achieve superior reliabilities of communications using gain combining approaches like maximal ratio combining (MRC). In this thesis, we propose a solution for decisions on where and how many relays should be deployed in a design of 802.16j wireless network to minimize the total development cost. During the procedure, we derive a multicast tree routing algorithm to fulfill the QoS and throughput requirements on both down-link (DL) and up-link (UL) communications. The solution approach is based on Lagrangean relaxation in conjunction with novel optimization-based heuristics. With the exceptional properties of Lagrangean relaxation we expect to efficiently and effectively solve this complicated optimization problem. Computational experiments will be conducted to evaluate the performance of the proposed algorithm.