臺灣博碩士論文加值系統

在本文目的在解決多重轉送電力線通訊接取網路(multi-hop Power Line Communication access network)的路由和時槽分配問題。在本系統中，時間被分割成數個固定大小的分時多工(time-division multiplexing, TDM)週期，各週期又被分割成半動態頻寬分配區段(SBAP)與動態頻寬分配區段(DBAP)。半動態頻寬分配區段用來提供電力線通訊網路中各個客戶端設備(Customer Premises Equipment, CPE)在週期中的固定頻寬，以配合頻寬保證服務，本區段的頻寬分配結果會維持較多週期。在動態頻寬分配區段，所有的節點共享剩餘頻寬，頻寬以週期為基礎動態的分配給各節點。本文中我們將空間重用(spatial reuse)與速率適配(rate adaptation)納入考量，並考慮線路狀況(channel quality)以決定最佳的多重轉送路由。在路由與時槽分配問題中，我們將半動態頻寬分配區段設計成整數線性規劃問題(ILP)，其目標函式為最小化時槽使用量以滿足所有頻寬需求敏感的服務。這是一個非確定性多項式時間複雜性類(NP-hard)的問題，為減少計算時間，我們提出一種以Lagrangean relaxation(LR)為基礎的演算法來解此問題。對於動態頻寬分配區段，我們提出一種token-based排程演算法來分配剩餘頻寬。在數值分析中可以看出我們提出的LR-based演算法可以在很短的運算時間內得到近似最佳解，且動態頻寬分配區段所使用的token-based排程演算法，可以提供較高的頻寬吞吐量(throughput)並達成各節點間出色的頻寬分享公平性。

Abstract—in this work, we address the Routing and Time slot Assignment (R&TA) problem in multi-hop power line communication (PLC) access networks. In our system, time is divided into fixed sized TDM cycles. Each cycle comprises a semi-dynamic bandwidth allocation period (SBAP) and a dynamic bandwidth allocation period (DBAP). The SBAP is used to provide each PLC Customer Premises Equipment (CPE) fixed bandwidth for providing bandwidth guaranteed services. It's a persistent bandwidth provisioning. The bandwidth of DBAP is shared by all of the nodes. This bandwidth is dynamically allocated to each node by a per cycle basis. We take spatial reuse and rate adaption into account. Our design also takes channel quality into consideration in determining the optimal multi-hop routing. We formulate the R&TA problem for the SBAP as an integer linear programming (ILP) model in which the objective function is to minimize the total bandwidth usage for supporting all bandwidth sensitive services in the network. Since this problem is an NP-hard problem, in order to reduce the computation time, we have developed a Lagrangean relaxation (LR) based algorithm to resolve the problem. For the DBAP part, we propose a token-based scheduling algorithm. Numerical results reveal that the proposed LR algorithm can obtain a near optimal solution in short computation time. For the DBAP part, the proposed token-based scheduling algorithm can provide high throughput especially it can provide excellent fairness for bandwidth sharing among all nodes.

誌謝辭 i
中文摘要 ii
英文摘要 iii
目錄 iv
圖目錄 vi
表目錄 viii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 論文架構 3
第二章 文獻探討 4
2.1 電力線接取網路標準 4
2.2 電力線通訊接取網路單元架構 5
2.3 媒介存取控制 8
2.4 時槽重用 9
2.5 速率配適 10
2.6 路由選擇 10
2.7 其他公平性分配排程 11
2.8 核心設計概要 11
第三章 路由與時槽分配問題之最佳化模型 13
3.1 設計重點 13
3.2 數學模型 13
3.2.1 變數及模型介紹 13
3.2.2 目標函數與限制式 15
3.3 Lagrangean relaxation based演算法 15
第四章 動態頻寬分配區段排程演算法 20
4.1 設計考量 20
4.2 排程演算法 21
4.3 TokenDBA演算法 22
第五章 數據結果 25
5.1 環境設定 25
5.2 半動態頻寬分配區段之路由與時槽分配 27
5.3 動態頻寬分配區段之排程與時槽分配 33
第六章 結論 40
參考文獻 41

[1]Andrea M. Tonello et al., "Optimal Time Slot Design in an OFDM-TDMA System over Power-Line Time-Variant Channels," in Proc. IEEE ISPLC, 2009.
[2]Hao Zou et al., "Multiuser OFDMA Resource Allocation Algorithms for In-Home Power-Line Communications," in Proc. IEEE GLOBECOM, 2008.
[3]IEEE Communications Society, "IEEE Standard for Broadband over Power Line Networks: Medium Access Control and Physical Layer Specifications," IEEE Std 1901, 2010.
[4]Le Phu Do et al., "Scheduling Strategies for Service Admission in Powerline Communication Access Networks with QoS Support," in Proc. IEEE ISPLC, 2008.
[5]Le Phu Do et al., "Channel Reuse Improvement for Coexistence between Access and In-Home PLC Systems with Dynamic Resource Allocation," in Proc. WSPLC, 2009.
[6]Le Phu Do et al.,"Distributed Dynamic Resource Allocation for Multi-Cell PLC Networks," in Proc. IEEE ISPLC, 2009.
[7]Le Phu Do et al., "Dynamic Resource Allocation Protocol for Large PLC Networks," in Proc IEEE ISPLC, 2012.
[8]M. Shreedhar et al., "Efficient Fair Queuing Using Deficit Round-Robin," in Proc. IEEE/ACM TRANSACTIONS OF NETWORKING, 1996.
[9]Nikolaos Papandreou et al., "Fair Resource Allocation in Multiuser Indoor Power Line Communications," in Proc. IEEE ISPLC, 2006.
[10]Peng An et al., "Analysis on Application of Repeater Technology in Powerline Communications Networks," in Proc. IEEE ISPLC, 2007.
[11]Rongping Dong et al., "Utility-based Joint Resource Allocation and Scheduling for Indoor Power Line Communications," in Proc. IEEE/ACM TRANSACTIONS ON NETWORKING, 1996.
[12]Stefano Galli et al., "Time Reuse Algorithms: A Novel Approach to Solving the Issue of Scalability in Dense Power Line Networks," in Proc. IEEE ISPLC, 2009.
[13]Steven S. W. Lee et al., "Optimal Bandwidth Guaranteed Routing and Time Slot Assignment for Broadband PLC Access Networks," in Proc. IEEE ISPLC, 2012.