臺灣博碩士論文加值系統

Proportional fair scheduling has been extensively studied. Early works considered single-carrier situations. As OFDMA being adopted in many modern broadband wireless systems, multi-carrier scheduling becomes a hot topic. Rather than directly applying a single-carrier algorithm to each carrier in turn independently, by jointly considering and scheduling the all channel resources, better system utilization may be achieved. In this work, we take IEEE 802.16j OFDMA multihop relay network under transparent relaying mode as our reference system model. We consider a high-level multi-carrier proportional fair scheduling problem under infinitely backlogged assumption. To better utilize the system resources, three data transmission schemes are considered: direct transmission, relay transmission, and cooperative transmission. The BS gathers SINRs of each link and is responsible for assigning time, frequency, and transmission scheme for each user in every frame. The basic goal is to reach proportional fairness and we want to further maximize system throughput, which involves very high complexity. An time-efficient scheduling algorithm is therefore desired at run-time. We proposed four algorithms and compare their performance through extensive simulations. Analysis of the behaviors of our proposed algorithms is also presented.

比例式公平排程(Proportional fair scheduling)已經受到廣泛的研究。早期研究的是單載子(single-carrier)系統，而在正交分頻多工存取(OFDMA)在許多近代的無線寬頻系統上被採用時，多載子(multi-carrier)的排程成為了研究的焦點。不同於直接將適用於單載子系統的演算法一一套用在每個載子上，當能同時考慮對所有的頻道排程時，能更充份有效地使用系統資源。在本次研究，我們的參考環境是IEEE所提出的802.16j正交分頻多工存取多躍中繼網路(multihop relay network)，並且假定其運做在透空中繼模式(transparent relaying mode)底下。我們考慮一個高階的多載子比例式公平排程的問題，假定所有的用戶永遠待排程的資料。為了更善用系統資源，考慮三種資料傳輸機制，分別是直接傳輸(direct transmission)、中繼傳輸(relay transmission)，以及協同式傳輸(cooperative transmission)。基地台獲取各連線的SINR值，並且負責在每一個傳訊框(frame)中，為使用者指定資料收送的時間、所使用的頻道，以及所採用的傳輸機制。基本目標是想達成比例式公平排程的要求，並且進一步想將系統傳輸量最大化。要解決這樣的問題，複雜度相當高，因此為了要能在系統運做時使用，勢必需要有執行時間上很有效率的排程演算法。我們提出了四種演算法，並且透過模擬實驗來比較了他們的結果，也同時對每種演算法的行為模式做了一些分析。

Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2. Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1. IEEE 802.16j Multihop Relay Networks . . . . . . . . . . . . . . . . . . . 4
2.1.1. Sub-carrier permutation and sub-channels . . . . . . . . . . . . . . 4
2.1.2. Adaptive modulation and coding (AMC) . . . . . . . . . . . . . . 5
2.1.3. Multihop relay (MR) . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.4. Transparent and non-transparent relaying mode . . . . . . . . . . . 6
2.2. Cooperative communications . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.1. Cooperative relaying . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.2. Cooperative diversity schemes . . . . . . . . . . . . . . . . . . . . 8
2.3. Proportional fair scheduling . . . . . . . . . . . . . . . . . . . . . . . . . 8
3. System Model and Problem Statement . . . . . . . . . . . . . . . . . . . . . 11
3.1. Considered transmission schemes . . . . . . . . . . . . . . . . . . . . . . 11
3.2. System model and notations . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3. Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4. Proposed Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.1. Algorithm 1: Inner-frame Update . . . . . . . . . . . . . . . . . . . . . . . 18
4.2. Algorithm 2: Base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.3. Algorithm 3: k-channel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.4. Algorithm 4: Time Division . . . . . . . . . . . . . . . . . . . . . . . . . 24
5. Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.1. Simulation Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.2. Performance Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5.3. Upper bound for proportional fair metric . . . . . . . . . . . . . . . . . . . 28
5.4. Algorithm running time . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.5. Experiment 1: Scheduling under Various Channel Conditions . . . . . . . . 29
5.5.1. Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.6. Experiment 2: Scheduling non-fixed Number of MSs . . . . . . . . . . . . 40
5.6.1. A New Algorithm: Dynamic . . . . . . . . . . . . . . . . . . . . . 40
5.6.2. Scenario 2-1: Increase MS count . . . . . . . . . . . . . . . . . . . 40
5.6.3. Scenario 2-2: Decrease MS count . . . . . . . . . . . . . . . . . . 43
6. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

[1] H. Yin and S. Alamouti, “Ofdma: A broadband wireless access technology,” pp. 1–4,
March 2006.
[2] L. Tassiulas, R. Tassiulas, and A. Ephremides, “Dynamic server allocation to parallel queues with randomly varying connectivity,” IEEE Transactions on Information Theory, vol. 39, pp. 466–478, 1993.
[3] L. Tassiulas and A. Ephremides, “Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks,” IEEE Trans. Automat. Contr., vol. 37, pp. 1936–1948, Dec. 1992.
[4] M. Andrews and L. Zhang, “Scheduling algorithms for multi-carrier wireless data systems,” in MobiCom ’07: Proceedings of the 13th annual ACM international conference on Mobile computing and networking, (New York, NY, USA), pp. 3–14, ACM, 2007.
[5] “Multiuser diversity in wireless networks.” http://www.eecs.berkely.edu/ dtse/stanford416.ps, 2002.
[6] A. L. Stolyar, “On the asymptotic optimality of the gradient scheduling algorithm for multiuser throughput allocation,” Oper. Res., vol. 53, no. 1, pp. 12–25, 2005.
[7] F. Kelly, A. Maulloo, and D. Tan, “Rate control in communication networks: shadow prices, proportional fairness and stability,” in Journal of the Operational Research Society, vol. 49, 1998.
[8] J. G. Andrews, A. Ghosh, and R. Muhamed, Fundamentals of WiMAX: Understanding Broadband Wireless Networking (Prentice Hall Communications Engineering and Emerging Technologies Series). Prentice Hall PTR, March 2007.
[9] “IEEE standard for local and metropolitan area networks; part 16: air interface for fixed and mobile broadband wireless access systems multihop relay specification.” IEEE P802.16j/D6, July 2008.
[10] H. J. Kushner and P. A. Whiting, “Convergence of proportional-fair sharing algorithms under general conditions,” IEEE Trans.Wireless Commun, vol. 3, pp. 1250–1259, 2003.
[11] “IEEE standard for local and metropolitan area networks; part 16: air interface for fixed broadband wireless access systems.” IEEE 802.16Rev2/D0, Mar. 2007.
[12] V. Tarokh, N. Seshadri, and A. Calderbank, “Space-time codes for high data rate wireless communication: performance criterion and code construction,” Information Theory, IEEE Transactions on, vol. 44, pp. 744–765, Mar 1998.
[13] B. Can, H. Yanikomeroglu, F. A. Onat, E. de Carvalho, and H. Yomo, “Efficient cooperative diversity schemes and radio resource allocation for ieee 802.16j,” in WCNC,
pp. 36–41, 2008.
[14] C. Wengerter, J. Ohlhorst, and A. von Elbwart, “Fairness and throughput analysis for generalized proportional fair frequency scheduling in ofdma,” vol. 3, pp. 1903–1907 Vol. 3, May-1 June 2005.
[15] H. Kim and Y. Han, “A proportional fair scheduling for multicarrier transmission systems,” Communications Letters, IEEE, vol. 9, pp. 210–212, March 2005.
[16] V. Erceg, L. J. Greenstein, S. Y. Tjandra, S. R. Parkoff, A. Gupta, B. Kulic, A. A. Julius, and R. Bianchi, “An empirically based path loss model for wireless channels in suburban environments,” Selected Areas in Communications, IEEE Journal on, vol. 17, no. 7, pp. 1205–1211, 1999.
[17] J. Proakis, Digital Communications. McGraw-Hill Science/Engineering/Math, August 2000.
[18] B. Sklar, “Rayleigh fading channels in mobile digital communication systems .i. characterization,” Communications Magazine, IEEE, vol. 35, no. 7, pp. 90–100, 1997.
[19] W. C. Jakes and D. C. Cox, Microwave Mobile Communications. Wiley-IEEE Press, 1994.
[20] “Ns-miracle.” http://www.dei.unipd.it/wdyn/?IDsezione=3966.