臺灣博碩士論文加值系統

IEEE 802.16標準的技術，也就是WiMAX技術，是一種可以服務於大範圍區域的無線存取技術。它的傳輸速率可以達到每秒100Mbps以上，因此WiMAX可以說是一種高速的無線寬頻網路技術。因為WiMAX技術允許用戶台之間採取多點跳躍(Multi-hop)的形式來處理資料封包，所以WiMAX技術不需要佈建大量的基地台，而只需要少數幾個基地台就能夠覆蓋一整個大都會區域。正因為如此，各個用戶台之間與用戶台和基地台之間需要採用一個有效率的繞送及封包排程(Routing and packet scheduling, 簡稱為RPS)演算法來解決資料的傳遞問題。事實上，近年來排程問題在多點跳躍式的WiMAX網路上已成為一個重要的研究議題。在本論文中，我們將研究IEEE 802.16網路中的RPS問題，並提出一個快速的方法來求解此問題。
多點跳躍式的WiMAX網路大致上可分為兩種類型：WiMAX網狀網路(WiMAX mesh networks)和行動多躍中繼網路(Mobile multihop relay networks)。在本論文中，我們將針對WiMAX網狀網路來提出一個快速集中式排程演算法。一個排程演算法的目標是最大化網路的吞吐量(Throughput)，也就是為用戶台所要求的封包數做有效的排程，使得所有用戶台的封包皆可傳送到基地台，且使用的時槽數為最少，並保證在這個排程中，用戶台之間的封包傳遞不會相互干擾。
在一般的網路拓撲之下，文獻[9]已經證明IEEE 802.16網狀網路上之RPS問題是NP-Complete，也就是說，求解RPS問題必須花費指數時間才能夠找出最小的時槽數。所以當用戶台的數量變多時，一組最佳的封包排程便常常無法在短時間內可以被找到。針對NP-Complete問題，西元1970年左右，數學技術上出現了一個有效率的計算概念，稱為拉格朗日鬆弛法(Lagrange relaxation)。拉格朗日鬆弛法的基本概念是鬆弛一個問題的某些限制條件，以縮小此問題的解集合空間，以使得這個問題的求解時間能夠被縮短。也就是說，此方法乃是試圖將所有可能使得一個組合最佳化問題陷入指數時間的限制式鬆弛並併入此問題的目標函數以成為一個拉格朗日問題。通常此拉格朗日問題能夠在較短的時間內得到一個最佳解。
本論文將利用拉格朗日鬆弛法來縮小RPS問題的解集合空間以便能夠縮短求解RPS問題的時間。在理論方面，本論文將把RPS問題轉換成為一個Lagrangian RPS問題，並且證明這個Lagrangian RPS問題的目標函數是一個凹性函數(Concave function)。此Lagrangian RPS問題簡化原來的 RPS 問題，並且可以在較短的時間內為RPS問題找出一個最佳解。事實上，為了加快RPS問題的求解速度，本論文已技巧性地減少了RPS問題之解集合空間。我們的電腦模擬顯示我們的技巧可以減少37.73%左右的解集合空間。也就是說，假若文獻[9] 之混合整數線性規劃公式的解集合空間為100%，那麼我們的技巧能夠在其62.27%的解集合空間內找出最小時槽數的排程。這在理論上是合理的，因為RPS問題常常存在多個具有最小時槽數的不同排程，所以我們刪除了37.73%的解集合空間，但並不表示我們完全刪除所有最小時槽數的排程。
本論文的電腦模擬顯示，相對於文獻[9]為RPS問題所提出的混合整數線性規劃公式，我們所使用的拉格朗日鬆弛法可以為RPS問題在較短的時間內找出最小的時槽數。以執行時間來看，我們的技巧最多可以降低97.87%的執行時間。因此，我們所提出的拉格朗日鬆弛技巧是有價值的，因為它確實可以縮短求解RPS問題的時間。

The IEEE 802.16 standard, also known as the WiMAX technology, is a technology of wireless network access which can service a large area. Its transmission rate exceeds 100 Mbps, which qualifies itself to fit the category of high-speed wireless broadband network technology. Since the WiMAX technology adopts the multi-hop technique to deal with data packets among subscriber stations (SSs), only a few base stations (BSs) are required to cover a large metropolitan area. For this reason, an efficient routing and packet scheduling (RPS) algorithm is necessary to deal with SS-to-SS and SS-to-BS data transmissions. In fact, the RPS problem has recently become an important research topic in the multi-hop WiMAX. In this thesis, we study the RPS problem in the IEEE 802.16 network and propose a fast method to solve it.
The multi-hop WiMAX can be subdivided into two types: WiMAX mesh networks and mobile multi-hop relay networks. Focusing on the first type, we want to design a fast centralized scheduling scheme. The objective of a scheduling scheme is to maximize the throughput of the network. In other words, we will design a fast scheduling scheme to meet the requirement of all the SSs so that all of the packets can be delivered to the BS while minimizing the number of time slots and prohibiting the interference between any two packets.
The authors of literature [9] have proven that the RPS problem is NP-complete for a general network topology. It means that it must take exponential time to find the optimal solution of the RPS problem. Thus, when the number of SSs is large, it is usually impossible to find an optimum schedule within a short time. As an approach to NP-complete problems, an efficient computational methodology was proposed around 1970, namely, the Lagrange relaxation based method. The basic idea is that some constraints of a given problem can be relaxed so as to reduce the solution space, which in turn shortens the solution-searching time. In other words, this method relaxes the constraints which may otherwise make the running time of a combinatorial optimization problem become exponential. These relaxed constraints are merged into the objective function such that the original problem becomes a Lagrangian problem. In general, an optimal solution to the resultant Lagrangian problem can be obtained within a shorter period of time.
In this thesis, the Lagrange relaxation based method is applied to shrink the solution space of the RPS problem for the purpose of shortening the solution-searching time. First, we theoretically transform the RPS problem into a Lagrangian RPS problem, which is then proved to be a concave function. This Lagrangian RPS problem simplifies the original RPS problem and can be used to find an optimal solution for the original RPS problem within a shorter time. In fact, to speed up the search of an optimal solution, we have cut down the solution space of the RPS problem. Our computer simulations show a decrease of the solution space by 37.73%. In other words, if the solution space must be searched by the mixed integer linear programming formulation in [9] is 100%, our method can find an optimal time slot schedule with 62.27% of its solution space. Our method is feasible. This is because different schedules of minimum time slots usually exist in the RPS problem. We eliminate 37.73% of the solution space without completely eliminating all the minimum time slot schedules.
According to the computer simulations, in contrast to the mixed integer linear programming formulation in [9], our Lagrange relaxation based method can attain a minimum time slot schedule within a shorter time for the RPS problem. In terms of running time, our method can decrease its running time by 97.87%. In conclusion, our Lagrange relaxation based method is demonstrated to be valuable for its contribution of a shorter solution time.

目錄 頁次
中文摘要 i
英文摘要 iii
誌謝 v
目錄 vi
表目錄 viii
圖目錄 ix
第一章 導論 1
1.1 WiMAX簡介 1
1.2 IEEE 802.16通訊標準的發展 3
1.3 WiMAX技術與LTE技術的比較 6
1.4 本論文組織與架構 9
第二章 相關研究工作及文獻回顧 11
2.1 WiMAX網路模式 11
2.2 IEEE 802.16 網狀網路之訊框架構 13
2.3 集中式排程的相關技術及文獻探討 14
第三章 繞送及封包排程問題 19
3.1 問題定義與描述 19
3.2 RPS問題的一個簡單範例 20
3.3 RPS問題之複雜度分析 24
第四章 線性規劃與RPS問題 26
4.1 線性規劃簡介 26
4.2 利用混合整數規劃解決RPS問題 32
第五章 Lagrange鬆弛法 34
5.1 Lagrange鬆弛法的基本概念 34
5.2 Lagrange鬆弛法的基本公式 35
5.2.1 當限制式為等式時 35
5.2.2 當限制式為不等式時 37
5.3 Lagrange鬆弛法的一個範例說明 41
5.4 拉格朗日係數λ的選擇 50
5.5 選擇拉格朗日係數λ的一個例子 53
5.6 調整拉格朗日係數λ以決定RPS問題的解集合空間大小 58
第六章 以拉格朗日鬆弛法分析RPS問題 60
6.1 使用拉格朗日鬆弛法求解RPS問題 60
6.2 使用次梯度演算法計算拉格朗日係數λ2 71
6.3 使用拉格朗日鬆弛法求解RPS問題在理論上的應用價值 76
第七章 模擬環境與結果 77
7.1 RPS問題模擬環境與模擬參數的設定 77
7.2 RPS問題的電腦模擬結果與數據分析 79
第八章 結論 82
參考文獻 83

[1]Z. Abichar, Y. Peng and J. M. Chang, "WiMAX: The Emergence of Wireless Broadbnad," IT Professional, Vol. 8, Issue 4, pp. 44-48, July-August 2006.
[2] J. G. Andrews, A. Ghosh, and R. Muhamed, Fundamentals of WiMAX: Understanding Broadband Wireless Networking, Pearson Education Inc, 2007.
[3] S. C. Fang and S. Puthenpura, Linear Optimization and Extensions: Theory and Algorithms, Prentice-Hall International, 1993.
[4] M. L. Fisher, "The Lagrangian Relaxation Method for Solving Integer Programming Problems," Management Science, Vol. 27, No. 1, January 1981.
[5]D. Ghosh, A. Gupta, and P. Mohapatra, "Scheduling in Multihop WiMAX Networks," ACM SIGMOBILE Mobile Computing and Communications Review, Vol. 12, Issue 2, pp. 1-11, April 2008.
[6]M. Held and R. M. Karp, "The Traveling Salesman Problem and Minimum Spanning Trees," Institute of Operations Research (INFORMS 1970), Vol. 18, pp. 1138-1162, 1970.
[7]M. Held and R. M. Karp, "The Traveling Salesman Problem and Minimum Spanning Trees: Part II," Proceedings of the 7th Mathematical Programming Symposium, Vol. 1, No. 1, pp. 6-25, December 1971.
[8]R. Irmer, and S. Chia, "Signal Processing Challenges for Future Wireless Communications," Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP 2009), pp. 3625-3628, April 2009.
[9]F. Jin, A. Arora, J. Hwang, and H.-A. Choi, "Routing and Packet Scheduling in WiMAX Mesh Networks," Proceedings of the 4th International Conference on Broadband Communications, Networks and Systems (BROADNETS 2007), pp. 574-582, September 2007.
[10]H. Shetiya and V. Sharma, "Algorithms for Routing and Centralized Scheduling to Provide QoS in IEEE 802.16 Mesh Networks," Proceedings of the 1th ACM Workshop on Wireless Multimedia Networking and Performance Modeling (WMuNeP’05), New York, NY, USA, pp. 140-149, October 2005.
[11]H. Shetiya and V. Sharma, "Algorithms for Routing and Centralized Scheduling to Provide QoS in IEEE 802.16 Mesh Networks," Proceedings of Wireless Communications and Networking Conference (WCNC 2006), pp. 147-152, April 2006.
[12] J. K. Strayer, Linear Programming and Its Applications, Springer-Verlag New Yourk Inc, 1989.
[13]J. Tao, F. Liu, Z. Zeng, and Z. Lin, "Throughput Enhancement WiMax Mesh Networks Using Concurrent Transmission," Proceedings of 2005 International Conference on Wireless Communications, Networking and Mobile Computing, Vol. 2, pp. 871-874, September 2005.
[14] K. Thornburg and A. Hummel, "LINGO 8.0 Tutorial: Introduction to LINGO 8.0," http://www.icaen.uiowa.edu/~ie166/Private/Lingo.pdf
[15]H.-Y Wei, S. Ganguly, R. Izmailov, and Z. J. Haas, "Interference-aware IEEE 802.16 WiMax Mesh Networks," Proceedings of 61st IEEE Vehicular Technology Conference (VTC 2005 Spring), Vol. 5, pp. 3102-3106, 29 May-1 June 2005.