淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2407200800561400
中文論文名稱 基植於IEEE 802.16 無線網狀網路上設計一同時考量上傳及下載資料流之分散式時槽選擇機制
英文論文名稱 A Decentralized Minislot Selection (DMS) Scheme for Uplink and Downlink Traffic in IEEE 802.16 Wireless Mesh Networks
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 96
學期 2
出版年 97
研究生中文姓名 蔣季陶
研究生英文姓名 Chi-Tao Chiang
學號 695410075
學位類別 碩士
語文別 英文
口試日期 2008-06-27
論文頁數 43頁
口試委員 指導教授-石貴平
委員-廖文華
委員-王三元
委員-王勝石
中文關鍵字 無線網狀網路  IEEE 802.16  WiMAX  集中式排程  分時多重存取 
英文關鍵字 Wireless Mesh Network  IEEE 802.16  WiMAX  Centralized Scheduling  Time Division Multiple Access (TDMA) 
學科別分類 學科別應用科學資訊工程
中文摘要 本論文考量在IEEE 802.16 無線網狀網路傳輸環境中,針對規格書所定義的集中式排程(Centralized Scheduling) 機制下提出一個分散式時槽選擇機制。此機制的目的在於有效地分配Minislots 資源使其能充分的利用,期望能夠使用最少的Minislots 來滿足網路中節點的需求。基於此目的,本論文先使用整數線性規劃 (Integer Linear Programming, ILP) 的方式來建構此排程問題的模型。此數學模型考慮傳輸對在不會互相影響的前提下,Minislot 的最佳使用數量及排程方式。然而ILP 求解屬於NP-complete 之問題,因此本論文進一步探討分散式時槽選擇機制以符合IEEE 802.16 無線網狀網路之真實情況。本論文首先探討不當的選擇Minislot 將會衍生出的三大造成整體網路執行效能下降問題:隱藏節點問題 (Hidden Terminal Problem) 、本身繞徑Minislot 不足問題 (Minislot Shortage Problem for Self-Route, MSP-SR) 及相鄰繞徑Minislot 不足問題 (Minislot Shortage Problem for Neighboring-Route, MSP-NP)。有鑑於此,本論文對於網路中節點使用Minislots 傳輸方式提出Minislots 使用限制政策(Minislots Inhibited Policies, MIPs)與Minislots 決定政策(Minislots Decision Policies, MDPs),並且同時考慮資料傳輸路徑上Minslots 的衝突問題及Minislots 的重覆使用,提出一分散式Minislot時槽選擇之機制。本論文透過此分散式Minislot 選擇機制,致使多對傳輸對可在同時間內進行傳輸,並能夠避免碰撞的發生,藉以提高網路的整體效能。由模擬實驗結果的數據得知,此分散式Minislot 選擇機制相較於IEEE 802.16 通訊協定能有較高網路整體效能與較低的傳輸延遲時間。
英文摘要 This thesis proposes a Decentralized Minislot Selection (DMS) scheme with bandwidth guarantee based on centralized scheduling in IEEE 802.16 mesh networks. The goals of this scheme are to increase spatial reuse and achieve high system throughput. Based on the above goals, this thesis first develops an Integer Linear Programming (ILP) model for determining optimum minislot scheduling to minimize the used minislots accounting for the effect of interference and variable-rate transmission. However, solving the ILP problem is an NP-complete problem. Therefore, a Decentralized Minislot Selection (DMS) scheme is proposed in the thesis. This scheme contains two main policies: Minislot Inhibited Policies (MIPs) and Minislot Decision Policies (MDPs), for determining which minislots are valid to use and which minslots in the valid minislots can be used
actually, respectively. In MDPs, three heuristic policies, 3BDP, LCFP and MRFP, are proposed to increase the successful rate of transmission and alleviate the minislot shortage problems. By the simulation result, the proposed scheme not only increases network throughput but also avoids the occurrences of collision and minislot shortage problems.
論文目次 Contents
Contents...................................................I
List of Figures..........................................III
1 Introduction............................................ 1
2 Preliminaries........................................... 5
2.1 IEEE 802.16 Frame Structure..........................5
2.2 IEEE 802.16 Centralized Scheduling Mechanism........ 6
2.3 Related Work.........................................8
3 Problem Statements and ILP Constraints................. 11
3.1 Problem Statements..................................11
3.2 ILP Constraints for CFTS Scheduling Problem........ 12
4 Challenges of Design Minislot Selection Scheme......... 15
4.1 Hidden Terminal Problem.............................15
4.2 Minislot Shortage Problems . . . 16
4.2.1 Minislot Shortage Problems for Self-Route(MSP-SR).16
4.2.2 Minislot Shortage Problems for Neighboring-Route
(MSP-NR)..........................................17
5 DMS:Decentralized Minislot Selection Scheme............ 19
5.1 Minislot Inhibited Policies (MIPs)..................19
5.2 Minislot Decision Policies (MDPs)...................21
5.2.1 Three-Hop Backward Decision Policy (3BDP).........21
5.2.2 Least Con°ict First Policy (LCFP).................22
5.2.3 Most Reuse First Policy (MRFP)....................23
5.3 DMS:Decentralized Minislot Selection Scheme.........24
6 Performance Evaluation..................................27
6.1 Simulation Setup....................................27
6.2 Simulation Results..................................27
7 Conclusion..............................................31
Bibliography..............................................33
International Conference Versions.........................35

List of Figures
Figure 1.1 IEEE 802.16 Mesh Networks.......................2
Figure 2.1 IEEE 802.16 Mesh Frame Structure................6
Figure 2.2 IEEE 802.16 Routing Tree........................7
Figure 3.1 Examples of Two Transmission Sets..............12
Figure 4.1 An Example of Hidden Terminal Problem..........16
Figure 4.2 An illustrative example for MSP-SR and MSP-NR..17
Figure 5.1 Demonstration of MIPs..........................20
Figure 5.2 Demonstration of 3BDP..........................22
Figure 5.3 Demonstration of MRFP..........................24
Figure 5.4 Demonstration of DMS...........................26
Figure 6.1 Impact of network density on the network throughput................................................28
Figure 6.2 Impact of network density on the data delay....29
Figure 6.3 Impact of network density on the channel utilization...............................................29
參考文獻 [1] I. F. Akyildiz, X.Wang, and W.Wang, "Wireless Mesh
Networks: a Survey," Computer Networks and ISDN
Systems, vol. 47, no. 4, pp. 445-487, March, 2005.
[2] H. Bolcskel, A. Paulraj, K. Hari, R. Nabar, and W. Lu,
"Fixed Broadband Wireless Access: State of The Art,
Challenges, and Future Directions," IEEE Communications
Magazine, vol. 39, no. 1, pp. 100-108, January, 2001.
[3] J. Chen, C. Chi, and Q. Guo, "An Odd-even Alternation
Mechanism for Centralized Scheduling in WiMAX Mesh
Networks," in Proceeding of the IEEE Global Telecommu-
nications Conference (GLOBECOM), November, 2006, pp.1-6.
[4] L. Fu, Z. Cao, and P. Fan, "Spatial Reuse in IEEE
802.16 Based Wireless Mesh Networks," in Proceedings of
the IEEE International Symposium on Communications and
Information Technology (ISCIT), vol. 2, October, 2005,
pp. 1358-1361.
[5] B. Han, W. Jia, and L. Lin, "Performance Evaluation of
Scheduling in IEEE 802.16 Based Wireless Mesh
Networks," Computer Communications, vol. 30, no. 4, pp.
782-792, February, 2007.
[6] IEEE Draft Standard for Local and Metropolitan Area
Networks -Part 16: Air Interface for Broadband Wireless
Access Systems, IEEE Draft Std. P802.16 Rev2/D2, 2007.
[7] IEEE Standard for Local and Metropolitan Area Networks -
Part 16: Air Interface for Fixed Broadband Wireless
Access Systems, IEEE Std. 802.16-2004, 2004.
[8] H. Shetiya and V. Sharma, "Algorithms for Routing and
Centralized Scheduling to Provide QoS in IEEE 802.16
Mesh Networks," in Proceeding of the ACM workshop
on Wireless multimedia networking and performance
modeling (WMuNeP), October,2005, pp. 140-149.
[9] J. Tao, F. Liu, Z. Zeng, and Z. Lin, "Throughput
Enhancement in WiMAX Mesh Networks Using Concurrent
Transmission," in Proceedings of International
Conference on Wireless Communications, Networking and
Mobile Computing (WCNM), vol. 2,September, 2005, pp.
871-874.
[10] W. Webb, "Broadband Fixed Wireless Access as a Key
Component of The Future Integrated Communications
Environment," IEEE Communications Magazine, vol. 39,
no. 9, pp. 115{121, September, 2001.
[11] H.-Y. Wei, S. Ganguly, R. Izmailov, and Z.
Haas, "Interference-aware IEEE 802.16 WiMAX Mesh
Networks," in Proceedings of the IEEE Vehicular
Technology Conference (VTC), vol. 5, May, 2005, pp.
3102-3106.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2013-07-29公開。
  • 同意授權瀏覽/列印電子全文服務,於2013-07-29起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信