Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/6511
DC FieldValueLanguage
dc.contributor.advisor廖俊睿zh_TW
dc.contributor.advisorJan-Ray Liaoen_US
dc.contributor.author彭立勳zh_TW
dc.contributor.authorPeng, Li-Xunen_US
dc.date2005zh_TW
dc.date.accessioned2014-06-06T06:38:23Z-
dc.date.available2014-06-06T06:38:23Z-
dc.identifier.urihttp://hdl.handle.net/11455/6511-
dc.description.abstract在無線網路中,因為通道可能會發生連續性的錯誤,且隨著使用者所在位置的不同,通道發生錯誤的機率也會不同,所以要設計一個優良的無線公平排隊演算法(Wireless Fair Queueing Algorithm)很不容易 。因此,我們首先在論文中闡述一個理想的無線公平排隊演算法應該要具備哪些特性。然後我們介紹學者所提出的無線公平排隊演算法之統一架構(Unified Architecture of Wireless Fair Queueing Algorithms)。藉由統一架構的幫助,我們可以較輕易地來實現或改善原有的無線公平排隊演算法,使它們的表現能夠更好。 這篇論文中,我們利用統一架構實現出五種由學者所提出的無線公平排隊演算法,分別為CSDPS [4]、IWFQ [5]、SBFA [6]、CIF-Q [7]與WFS [8]並對他們做綜合分析。另外,我們亦透過模擬來比較這些演算法的服務降低(Service Degradation)特性。經由分析與模擬的結果,我們發現CIF-Q與WFS這兩個演算法的表現最好。另外,我們也在統一架構下,改善WPS與SBFA這兩個表現不是特別好的無線公平排隊演算法,使它們的表現能夠趨近CIF-Q與WFS。 我們在論文的最後,提出了一個可以讓資料流的領先值與落後值衰減的機制,稱為老化作用(Aging Effect)。經由我們模擬的結果發現,當老化作用運用於無線公平排隊演算法時,會使得使用者的領先值或落後值,隨著時間的增加而成指數性的衰減。zh_TW
dc.description.abstractFair queueing in the wireless networks poses significant challenges because channel errors are bursty and location-dependent. In this thesis, we first introduce the requirements of an ideal wireless fair queueing algorithm. Then, we introduce a unified wireless fair queueing architecture in which we can design an ideal wireless fair queueing algorithm. We map five wireless fair queueing algorithms onto the unified architecture. These algorithms are: CSDPS [4], IWFQ [5], SBFA [6], CIF-Q [7], and WFS [8]. Through simulation, we compare the service degradation property of these algorithms. We conclude that two of these algorithms, CIF-Q and WFS are better in terms of short-term and long-term fairness, short-term and long-term throughput bounds. With these results, we improve WPS algorithm. We find that the modified WPS algorithm performs well as compared to CIF-Q and WFS. In addition, we improve SBFA algorithm and find that the performance of SBFA has also been improved. Finally, we present Aging Effect which decay lead and lag of flow. Through simulation, we find that Aging Effect could decay lead and lag of flow exponentially.en_US
dc.description.tableofcontents致謝……...……………...…………...……………...……………......…...i 摘要……….……………………...…………………………...………. ...ii ABSTRACT…….…...……………...……………...…...………………..iv 目錄……...……………...……………...……………...……………….....v 圖目錄……...……………...……………………………………..……….ix 表目錄……...……………...……………………………………..………xii 第一章 緒論………………………………….………………...……...…1 1.1 動機與目的………………………………………………………. 1 1.2 論文架構………………………………………………..…..……..3 第二章 有線與無線公平排隊演算法的差異……………………..…….4 2.1 有線公平排隊演算法.……………………….……………………4 2.1.1 Weighted Fair Queueing (WFQ)…………………………………4 2.1.2 Start-Time Fair Queueing (SFQ)…………………………………6 2.1.3 Weighted Round Robin (WRR)……………………………...……7 2.2 有線與無線網路環境的差異…………………………………..…8 2.3 理想的無線公平排隊演算法之特性…………………………..…8 第三章 無線公平排隊演算法之統一架構...…………...……………….10 3.1 無線公平排隊演算法之統一架構介紹…………………………..11 3.2 無錯誤服務模型(Error-free Service Model)……………………...13 3.3 領先與落後模型(Lead and Lag Model)…………………..……...13 3.4 補償模型(Compensation Model)…………………………………15 3.5 時槽佇列與封包佇列(Slot Queues and Packet Queues)…………16 3.6 通道監測與預測(Channel Monitor and Prediction)……….……..18 3.7 總結…………………………………………….………………….18 第四章 五種無線公平排隊演算法的介紹..…………………………….19 4.1 Channel State Dependent Packet Scheduling Algorithm (CSDPS)..20 4.1.1 無錯誤服務模型…………………………….……… ……………20 4.1.2 補償模型……………………………………………………………20 4.1.3 領先與落後模型……………………………………………..……21 4.1.4 討論………………………………………………………….………21 4.2 Wireless Packet Scheduling Algorithm (WPS)……………….……21 4.2.1 無錯誤服務模型……………………………………………...…...21 4.2.2 補償模型……………………………………………………………23 4.2.3 領先與落後模型…………………………………………..………26 4.2.4 討論………………………………………………………………….27 4.3 Server Based Fairness Approach Algorithm (SBFA)….……...……27 4.3.1 無錯誤服務模型……………………………………………...……27 4.3.2 補償模型…………………………………………………………....28 4.3.3 領先與落後模型…………………………………………….……29 4.3.4 討論…………………………………………………………………30 4.4 Channel-Condition Independent Fair Queueing Algorithm(CIF-Q)..30 4.4.1 無錯誤服務模型……………………………………………..……30 4.4.2 補償模型……………………………………………………………30 4.4.3 領先與落後模型……………………………………………..……32 4.4.4 討論………………………………………………….………………34 4.5 Wireless Fair Service Algorithm (WFS)………………..…….……35 4.5.1 無錯誤服務模型………………………………………..…………35 4.5.2 補償模型……………………………………………………………36 4.5.3 領先與落後模型…………………………………………..………38 4.5.4 討論……………………………………………….…………………39 4.6 總結……………………………………………………..................39 第五章 無線公平排隊演算法的改善.……………………..…...……….40 5.1 WPS 的改善..……………………………………….......................41 5.1.1 CIF-Q演算法的領先補償機制應用於WPS演算法上……41 5.1.1.1 無錯誤服務模型……………………………………..………41 5.1.1.2 補償模型………………………………………………………41 5.1.1.3 領先與落後模型…………………………………..…………43 5.1.1.4 討論…………………………………………………….………43 5.1.2 WFS演算法的領先補償機制應用於WPS演算法上……..44 5.1.2.1 無錯誤服務模型……………………………………….……44 5.1.2.2 補償模型………………………………………………………44 5.1.2.3 領先與落後模型………………………………..……………46 5.1.2.4 討論……………………………….……………………………46 5.2 SBFA的改善..………………………………………......................47 5.3 老化作用的介紹………………………………..............................48 5.4 總結……………………………………………………………..…50 第六章 模擬結果與分析………………………………………………...51 6.1 模擬環境及參數介紹……………………………………………..51 6.2 五種無線公平排隊演算法的模擬………………………..………52 6.3改善過的無線公平排隊演算法的模擬……………………...……66 6.4老化作用應用於無線公平排隊演算法的模擬………………..….73 第七章 結論與未來工作…………………………………………….......80 7.1 結論…………………………………………..................................80 7.2 未來工作……………………………………………………..……81 參考文獻………………………………………………………………….82 圖目錄 圖2-1 Weighted Round-Robin (WRR)……………………………………7 圖3-1 無線公平排隊演算法之統一架構...............................................11 圖3-2 時槽佇列與封包佇列…………………………………………...17 圖4-1 WPS的例子…..…………………………………………………23 圖4-2 SBFA的例子………………………………………………...…..29 圖5-1 老化作用(Aging Effect)的介紹…………………………………49 圖6-1 資料流在CSDPS中的傳輸率比較………………………….….53 圖6-2 Flow B與Flow C在CSDPS中的延遲情況…………………..54 圖6-3 Flow A在CSDPS中的延遲情況……………………………….54 圖6-4 資料流在WPS中的傳輸率比較……………………….………55 圖6-5 Flow B與Flow C在WPS中的延遲情況……………………..56 圖6-6 Flow A在WPS中的延遲情況…………………………………56 圖6-7 資料流在SBFA中的傳輸率比較………………………………57 圖6-8 Flow B與Flow C在SBFA中的延遲情況…………………….58 圖6-9 Flow A在SBFA中的延遲情況………………………………...58 圖6-10 資料流在CIF-Q中的傳輸率比較………………………………59 圖6-11 Flow B與Flow C在CIF-Q中的延遲情況…………………..60 圖6-12 Flow A在CIF-Q中的延遲情況………………………………60 圖6-13 資料流在WFS中的傳輸率比較………………………………61 圖6-14 Flow B與Flow C在WFS中的延遲情況……………………62 圖6-15 Flow A在WFS中的延遲情況………………………………..62 圖6-16 Flow A的傳輸率綜合比較(針對第四章所提及的演算法)…..65 圖6-17 Flow B的傳輸率綜合比較(針對第四章所提及的演算法)…..65 圖6-18 Flow C的傳輸率綜合比較(針對第四章所提及的演算法)…..66 圖6-19 資料流在CIF-Q與WPS with Lead Compensation of CIF-Q中的傳輸率比較……………………………………………………………….67 圖6-20 Flow B & C在WPS with Lead Compensation of CIF-Q中的延遲情況……………………………………………………………………….68 圖6-21 Flow A在WPS with Lead Compensation of CIF-Q中的延遲情況.................................................................................................................68 圖6-22 資料流在WFS與WPS with Lead Compensation of WFS中的傳輸率比較………………………………………………………………….69 圖6-23 Flow B & C在WPS with Lead Compensation of WFS中的延遲情況…………………………………………………………………………70 圖6-24 Flow A在WPS with Lead Compensation of WFS中的延遲情況…………………………………………………………………………70 圖6-25 資料流在SBFA與改善過後的SBFA中的傳輸率比較……71 圖6-26 Flow B & C在改善過後的SBFA中的延遲情況…………...72 圖6-27 Flow A在改善過後的SBFA中的延遲情況………………...72 圖6-28 資料流在WPS中之傳輸率比較(有老化作用時)…………….75 圖6-29 資料流在WPS中之領先值比較(有老化作用時)…………….75 圖6-30 資料流在CIF-Q中之傳輸率比較(有老化作用時)…………...76 圖6-31 資料流在CIF-Q中之領先值比較(有老化作用時)…………...76 圖6-32 資料流在WFS中之傳輸率比較(有老化作用時)…………….77 圖6-33 資料流在WFS中之領先值比較(有老化作用時)…………….77 圖6-34 資料流在WPS with Lead Compensation of CIF-Q中之傳輸率比較(有老化作用時)………………………………………………………..78 圖6-35 資料流在WPS with Lead Compensation of CIF-Q中之領先值比較(有老化作用時)………………………………………………………..78 圖6-36 資料流在WPS with Lead Compensation of WFS中之傳輸率比較(有老化作用時)………………………………………………………..79 圖6-37 資料流在WPS with Lead Compensation of WFS中之領先值比較(有老化作用時)………………………………………………………..79 表目錄 表4-1 WRR與WRR-Spreading之比較……………………………......22 表6-1 資料流的延遲情況綜合比較(針對第四章所提及的演算法)…..64 表6-2 資料流的延遲情況綜合比較(針對第五章所提及的演算法)…..73zh_TW
dc.language.isoen_USzh_TW
dc.publisher電機工程學系zh_TW
dc.title無線公平排隊演算法之統一架構zh_TW
dc.titleA Unified Architecture of Wireless Fair Queueing Algorithmsen_US
dc.typeThesis and Dissertationzh_TW
item.fulltextno fulltext-
item.languageiso639-1en_US-
item.openairetypeThesis and Dissertation-
item.cerifentitytypePublications-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.grantfulltextnone-
Appears in Collections:電機工程學系所
Show simple item record
 
TAIR Related Article

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.