考量訊號延遲以及傳輸量下無線通訊網路針對多種流量類型之近似最佳化時槽分配演算法

Abstract

無線網路能夠帶給使用者更多的方便性，但由於傳輸特性的限制，每位使用者所能分配到的頻寬也有限；在多媒體傳輸的服務需求增加之下，對於資料傳輸的服務品質(Quality of Service)的要求也更為嚴格。對於網際網路提供業者而言，如何在無線網路有限的頻寬資源之下，滿足各種等級的服務品質要求，並且使得網際網路提供業者的收益能夠達到最大化，這是一個相當值得研究的議題。 我們將上述的問題透過馬可夫決策過程並結合拉格蘭日鬆弛法來解決馬可夫決策過程加上額外的服務品質的要求問題。藉由以上所提出的方法，我們預期可以得到一個針對不同系統狀態下的最佳時槽分配策略，能夠在滿足系統服務品質要求之下，達到系統收益最大化的目的。

Wireless communication networks provide convenience, however, also challenges to multimedia services due to typically limited bandwidth and various QoS (Quality-of-Service) requirements. For a wireless communication network service provider/administrator, it is then essential to develop an effective resource allocation policy so as to fully satisfy possibly different QoS requirements by different classes of traffic, while in the meantime, for example, the overall long-term system revenue rate can be maximized. In this thesis, the problem of time slot allocation in wireless communication networks under throughput and delay constraints for multiple classes of traffic is considered. The basic approach to the algorithm development is a novel combination of MDP (Markovian Decision Process) and Lagrangean relaxation. The problem is first formulated as a standard linear-programming form of an MDP problem, however, with additional QoS constraints. Lagrangean relaxation is then applied to relax such QoS constraints. This Lagrangean relaxation problem, after proper regrouping of the terms involved in the objective function, becomes a standard MDP problem (with a new revenue matrix compared with the original problem) and can be solved by standard liner programming techniques or the policy enhancement algorithm. Another primal heuristic based upon the policy enhancement algorithm is also developed for comparison purposed. It is expected that efficient and effective algorithms be developed by the proposed approach.