Basic Search / Detailed Display

Author: 楊博丞
Bo-Cheng Yang
Thesis Title: 於IEEE 802.16 OFDMA分散式排程網狀網路之雜湊配置演算法
A Novel Hashing Allocation Algorithm in IEEE 802.16 Distributed Scheduling Mesh OFDMA Network
Advisor: 黎碧煌
Bih-Hwang Lee
Committee: 鍾添曜
Tein-Yaw Chung
吳傳嘉
Chwan-Chia Wu
陳添智
Tien-Chi Chen
賴源正
Yuan-Cheng Lai
Degree: 碩士
Master
Department: 電資學院 - 電機工程系
Department of Electrical Engineering
Thesis Publication Year: 2008
Graduation Academic Year: 96
Language: 中文
Pages: 67
Keywords (in Chinese): IEEE 802.16正交分頻多工存取網狀網路分散式排程
Keywords (in other languages): IEEE 802.16, OFDMA, Mesh Network, Distributed Scheduling
Reference times: Clicks: 590Downloads: 2
Share:
School Collection Retrieve National Library Collection Retrieve Error Report
  • 在IEEE 802.16的網狀網路模式中,節點間的訊號處理以及資料的排程方式對系統的效能與容量有著極大的影響。本論文以OFDMA-TDMA做為實體層的資料子訊框,來增加節點在時槽配置上的彈性以期增加頻譜利用率。由於節點無法得知距離為二跳躍的節點之排程資訊,使得要求資料傳送的節點發生要求失效的問題,此問題將會導致傳輸效能降低以及存取時間的延遲。因此本論文針對該問題提出一獨特的時槽選擇機制,讓網路中的節點以不同的依據來做資料的排程,以降低要求失效的問題。在時槽選擇機制中,將本論文提出的”雜湊選擇機制(hash selection scheme;HSS)”來和一般選擇機制以及隨機選擇機制做比較,透過不同的拓樸分析在網狀網路中隱含的主要干擾狀況(primary interference scenario;PIS)和次要干擾狀況(secondary interference scenario;SIS)的問題,並對三種不同機制來比較其問題的改善。經過模擬程式的結果,本論文之方法在不同的拓樸中都有顯著的改善,且在輕載時最多能提高35%的產能,並且可使失效問題降低至0.05%。在重載時,HSS僅能提高約10%的效能,且失效問題也提高到27%,甚至到滿載時,HSS再也無法提升效能,失效問題也和另外兩種機制差不多。


    In IEEE 802.16 mesh network, the transmission signaling and data scheduling method significantly affect the performance and capacity of the system. This paper propose a physical layer uses OFDMA-TDMA in the data subframe to improve data scheduling flexibility and spectrum efficiency. Because local nodes don’t know the exact scheduling information of 2-hop neighbors, the grant messages sent back by the receiver have the chance to collide with other’s decision, known as request invalid, and thus decreases throughput and increase access delay. Therefore, this paper provide an unique slot selection mechanism, known as hash selection scheme (HSS), to against the issue by allowing the node in the network to schedule data with a shifting basis. We compare three different slot selection mechanism, which include normal, random and HSS, on both primary interference scenario (PIS) and secondary interference scenario (SIS) with different topologies. Simulation results show that HSS is 35% better in throughput than others and reduces the request invalid ratio to 0.05% in the relative low loading system. In the relative heavy loading system, HSS is only 10% better in throughput than others and the request invalid ratio reach to 27%. In the full loading system, HSS improve the throughput anymore, and request invalid ratio is the same as others.

    目次 中文摘要 i 英文摘要 ii 圖目次 vi 表目次 ix 第一章 緒論 1 1.1 無線都會網路概述 1 1.2 研究動機 2 1.3 各章節內容摘要 3 第二章 IEEE802.16網路及分散式排程機制 4 2.1 IEEE 802.16網路 4 2.1.1 IEEE 802.16網路架構及特性簡介 4 2.1.2 IEEE 802.16網路硬體架構 6 2.2 分散式排程機制 10 2.2.1 分散式排程機制介紹 10 2.2.2 節點間的關係 10 2.2.3 分散式排程訊息 11 2.2.4 分散式排程運作原理 14 第三章 系統模型 21 3.1系統訊框架構 21 3.1.1 IEEE 802.16標準訊框架構 21 3.1.2 OFDMA-TDMA訊框架構 21 3.2系統運作流程 22 3.2.1 系統運作流程前言 22 3.2.2 二維時槽映射 23 3.2.3 確認排程時槽 30 3.2.4 頻寬要求及排程 31 3.3時槽選擇機制 36 3.3.1一般選擇 36 3.3.2隨機選擇機制 38 3.3.3雜湊選擇機制(hashing selection scheme;HSS) 40 第四章 系統模擬與結果 47 4.1拓樸 47 4.1.1星狀拓樸 47 4.1.2鏈狀拓樸 48 4.1.3隨機拓樸 48 4.2效能量測 49 4.2.1節點傳輸產能 (node throughput) 49 4.2.2節點延遲時間 (delay) 49 4.2.3失效率 (invalidation ratio) 50 4.3系統參數 50 4.3.1流量模型 50 4.3.2系統參數 51 4.4系統模擬結果 51 4.4.1星狀拓樸 51 4.4.2鏈狀拓樸 54 4.4.3隨機拓樸 56 4.4.4參數變化 59 第五章 結論 64 參考文獻 65 圖目次 圖2-1 點對多點網路模式 6 圖2-2 網狀網路模式 6 圖2-3 點對多點網路以TDD方式提供雙向服務的訊框架構 7 圖2-4 點對多點網路以FDD方式提供雙向服務的訊框架構 8 圖2-5 IEEE 802.16標準的網狀網路訊框架構 9 圖2-6 一跳躍躍與二跳躍躍(延伸)節點示意圖 11 圖2-7 排程訊息傳播示意圖 13 圖2-8 分散式排程運作流程 14 圖2-9 節點延遲時間示意圖 16 圖2-10 透過鄰近節點資訊判斷是否需競爭示意圖 17 圖2-11 Election function方塊圖 18 圖2-12 三向交握示意圖 19 圖2-13 使用AvailabilityIE示意圖 20 圖3-1 OFDMA-TDMA架構 22 圖3-2 OFDMA-TDMA資料子訊框 23 圖3-3 二維資料子訊框映射 25 圖3-4 鄰近節點關係圖 25 圖3-5 節點間的鏈結影響關係 26 圖3-6 二維資料子訊框映射演算法 27 圖3-7 二維時槽映射演算法之範例 29 圖3-8 時槽確認範例 30 圖3-9 排程配置方塊圖 33 圖3-10 第一種要求失效示意圖 34 圖3-11 第二種要求失效示意圖 35 圖3-12 一般選擇在PIS情況其輕載與重載配置 37 圖3-13 將OFDMA/TDMA時槽再切割示意圖 38 圖3-14 隨機選擇在PIS情況其輕載與重載配置 39 圖3-15 隨機選擇機制及HSS概念比較 41 圖3-16 HSS演算法和資料區塊對應圖 43 圖3-17 雜湊選擇排程流程 44 圖3-18 雜湊演算法範例拓樸 45 圖3-19 雜湊選擇範例 45 圖4-1 星狀拓樸 47 圖4-2 鏈狀拓樸 48 圖4-3 隨機拓樸 48 圖4-4 星狀拓樸中連接節點數與節點產能的關係 52 圖4-5 星狀拓樸中連接節點數與失效的關係 52 圖4-6 星狀拓樸中流量與節點產能的關係 53 圖4-7 星狀拓樸中流量和失效率的關係 53 圖4-8 鏈狀拓樸中流量與節點產能的關係 55 圖4-9 鏈狀拓樸流量與失效率的關係 55 圖4-10 隨機拓樸中流量與節點產能的關係及改善效益 57 圖4-11 隨機拓樸中流量與延遲時間的關係 57 圖4-12 隨機拓樸中流量與失效率的關係 58 圖4-13 不同的 參數與節點產能的關係 59 圖4-14 不同 參數與延遲時間的關係 60 圖4-15 不同 參數與失效率的關係 60 圖4-16 不同 參數與節點產能的關係 61 圖4-17 不同 參數與延遲時間的關係 62 圖4-18 不同 參數與失效率的關係 62 表目次 表2-1 MSH-DSCH訊息格式 12 表2-2 MSH-DSCH訊息中的SchedulingIE 15 表3-1 MSH-DSCH訊息中的GrantIE 24 表3-2 MSH-DSCH訊息中的RequestIE 32 表4-1系統參數 51

    [1] “IEEE Standard for Local and Metropolitan area networks Part 16: Air Interface for Fixed Broadband Wireless Access Systems,” IEEE Std 802.16-2001.
    [2] “IEEE Standard for Local and metropolitan area networks --- Part 16: Air Interface for Fixed Broadband Wireless Access Systems--- Amendment 2: Medium Access Control Modifications and Additional Physical Layer Specifications for 2-11 GHz,” IEEE Std 802.16a-2003.
    [3] “802.16d IEEE Standard for Local and metropolitan area networks,” IEEE Std 802.16-2004.
    [4] “IEEE Standard for Local and metropolitan area networks Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems Amendment 2: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands and Corrigendum 1,” IEEE Std 802.16e-2005.
    [5] Paramvir Bahl, Atul Adya, Jitendra Padhye, Alec Walman, “Reconsidering wireless systems with multiple radios,” in Proc. of ACM SIGCOMM Computer Communications Review, vol. 34, pp. 39-46, Oct. 2004.
    [6] Ashish Raniwala and Tzi-cker Chiueh, “Architecture and algorithms for and IEEE 802.11-based multi-channel wireless mesh network,” in Proc. of IEEE International Conference on Computer and Communications, (INFOCOM 2005), vol. 3, pp. 2223-2234, Mar. 2005.
    [7] Giuseppe Anastasi, Eleonora Borgia, Marco Conti, and Enrico Gregori, “IEEE 802.11b ad hoc networks: Performance measurements,” Cluster Computing (Springer), vol. 8, pp. 135-145, July 2005.
    [8] Nico Bayer, Dmitry Sivchenko, Bangnan Xu, Veselin Rakocevic, and Joachim Habermann, “Transmission timing of signalling messages in IEEE 802.16 based Mesh Networks,” in Proc. of International Conference on European Wireless 2006, April 2006.
    [9] Min Cao, Wenchao Ma, Qian Zhang, Xiaodong Wang, and Wenwu Zhu, “Modeling and performance analysis of the distributed scheduler in IEEE 802.16 mesh mode,” in Proc. of 6th ACM international symposium on Mobile ad hoc networking and computing, (MobiHoc 2005), pp. 78-89, May. 2005.
    [10] Najah A, Abu Ali, Abd-Elhamid M, Taha, Hassam S, and Hussein T. Mouftah, “IEEE 802.16 Mesh Schedulers Issues and Design Challenges,” IEEE Transaction on Network, vol. 22, no. 1, pp. 58-65, Jan.-Feb. 2008.
    [11] Dave Beyer, Nico van Waes, and Carl Eklund, “Tutorial 802. 16 MAC Layer Mesh Extensions Overview.”
    [12] Nico Bayer, Bangnan Xu, Veselin Rackcevic, and Joachim Habermann, “Improving the Performance of the Distributed Scheduler in IEEE 802.16 Mesh Networks,” in Proc. of Vehicular Technology Conference 2007, (VTC 2007), pp. 1193-1197, April, 2007.
    [13] Yehuda Ben-Shimol, Itzik Kitroser, and Yefim Dinitz, “Two-Dimensional Mapping for Wireless OFDMA Systems,” IEEE Transactions on Broadcasting, vol. 52, no. 3, pp. 388-396, Sep. 2006.
    [14] Petar Djukic and Shahrokh Valaee, “Quality-of-Service Provisioning for Multi-Service TDMA Mesh Networks,” in Proc. of International Teletraffic Congress, pp. 841-852 Aug. 2006.
    [15] Petar Djukic and Shahrokh Valaee, “Distributed Link Scheduler for TDMA Mesh Networks,” in Proc. of IEEE International Conference on Communications 2007, (ICC 07), pp. 3823-3828, June 2007.
    [16] B. Makarevitch, “Jamming Resistant Architecture for WiMAX Mesh Networks,” in Proc. of IEEE Military Communication Conference 2006, (MILCOM 2006), pp. 1-6, Oct. 2006.
    [17] Claudio Cicconetti, Ian F. Akyildiz, and Luciano Lenzini, “Bandwidth Balancing in Multi-Channel IEEE 802.16 Wireless Mesh networks,” in Proc. of 26th IEEE International Conference on Computer Communications 2007, (INFOCOM 2007), pp. 2108-2116, May. 2007.
    [18] R. Jayaparvathy and G. Sureshkumar, “Performance Evaluation of Scheduling Schemes for Fixed Broadband Wireless Access Systems,” in Proc. of 13th IEEE International Conference on Communication, vol. 2, pp. 6, Nov. 2005.

    無法下載圖示 Full text public date 2013/07/29 (Intranet public)
    Full text public date This full text is not authorized to be published. (Internet public)
    Full text public date This full text is not authorized to be published. (National library)
    QR CODE