大型天然災害會癱瘓通訊系統，嚴重影響到救災效率，本論文旨在快速進行可用的鄰台間無線電鏈結頻寬分配，供應急通訊系統使用。無線通訊技術的成熟，為使用者帶來極大的便利性，但當發生大規模的地震或強烈颱風等重大天然災害時，通訊系統卻常常因架構等因素，隨著電力與交通系統的損毀而癱瘓。由歷年大型災變中多數災區內之行動通訊系統全面中斷即可印證行動通訊系統其實是極為脆弱，而有效運作的通訊系統卻是災情傳遞、資源調度以及互助協調是否順利的關鍵因素。 本文所探討的應急通訊系統是利用倖存的連通基地台和斷訊卻沒有損毀的基地台，以無線電連接起來建構一個臨時性的通訊系統，稱為應急蜂巢式行動通訊網路(Contingency Cellular Network，CCN)。由於CCN鄰台間無線電鏈結的頻寬有限，大量話務將造成通訊系統壅塞，影響重要訊息傳遞，且災區各個地方需求與受災情況不盡相同，使得CCN頻寬資源需視各地需求與需求緊急程度進行規劃配置，以充分發揮頻寬效益傳遞重要資訊。本論文主要在探討如何在CCN網路拓樸、連外頻寬分配已決定的情況下，進行CCN跨基地台頻寬分配，以達到最大的救災效益。我們提出一適合CCN樹狀結構的頻寬分配優化模型，在兼顧涵蓋率的情況下追求救災效益的最大化，此模型可供使用者(救災指揮單位)系統化的解決CCN跨基地台頻寬分配問題。 本文所提出的頻寬分配模型包含CCN樹狀拓樸、鄰台間之無線電鏈結頻 寬資源限制、需求對(存在通訊需求之兩基地台)、差異化之通訊品質通道和頻寬效益遞減函數。我們證明此模型是NP-Hard問題，並提出一個考慮各需求對緊急程度以及通訊品質需求差異而進行快速頻寬分配的演算法，此演算法以貪婪法在各中間步驟挑選當下效益密度最高的選擇賦予頻寬，如此逐步計算得到最終解。 我們以電腦模擬的方式，評估CBBAG演算法搭配不同頻寬救災效益密度計算之效能。在我們的實驗中，CBBAG演算法搭配additive的頻寬救災效益密度計算方式所的效能最佳，在小規模模擬環境下，在所模擬的30個亂數產生的案例中，CBBAG演算法與最佳解相較，效能差距不超過9.4%。而在大規模環境下，在所模擬的10個亂數產生的案例中，CBBAG演算法與準最佳解相較，效能至少超過最少21.8%，最多43.26%。 最後我們以unit cost of coverage improvement比較兩種效益遞減函數在增加涵蓋率時所承擔的效益成本。由實驗結果可以發現，CBBAG演算法搭配1/sqrt(分配至某需求對的頻道數)效益遞減函數所付出的效益成本較小。

隨著智慧家庭概念與技術的興盛與成熟，未來ISP(Internet Service Provider)業者勢必面臨管理大量智慧家庭中各種不同應用競爭頻寬資源的情況。為因應大量且繁雜類型的應用服務彼此競爭智慧家庭端及ISP端的頻寬資源，考量並應用適當的頻寬分配法則以盡可能優化使用者體驗(QoE)是本研究的研究動機。相關文獻的排程演算法如TDPSS (Time Domain Priority Set Scheduler)、MSCDL (Mac Scheduler)、Proportional Fair (PF)及Adaptive Modified Largest Weighted Delay First (AMLWDF)等。若要用以管理大量智慧家庭的頻寬資源時，ISP業者須將家庭申辦頻寬方案以及ISP端的系統頻寬分開考量。ISP在整合(aggregate)多個家庭的頻寬資源請求時，會依服務類別分配頻寬，最後依據不同類別採取適當處理，進而提升不同應用的QoS品質。 本篇論文著重於延遲時間的考量，提出能分類來自各個智慧家庭中，屬於不同 QCI (QoS Class Identifier)級別的頻寬請求並以不同佇列存放，依DADS (Delay Aware Dynamical Scheduling)演算法計算優先權值。我們利用保障頻寬與動態配置頻寬給不同用戶服務佇列，並優先分配頻寬給較高優先權的用戶服務，以期在維持一定公平性的前提下，盡可能地降低延遲來提升QoS品質。 在我們的實驗數據分析中，我們將DADS和其他方法如MSCDL、PF、TDPSS以及AMLWDF進行公平性、產能、延遲以及抖動率等效能優劣的比較與分析。最後在總結與未來研究方向，我們歸納與整理了DADS與PF、MSCDL、TDPSS以及AMLWDF等演算法的效能優劣。實驗結果顯示，在延遲上，DADS勝過PF和TDPSS，但略輸MSCDL及AMLWDF；在抖動率及產能上，DADS均較其它四者為差；公平性上則是劣於TDPSS、PF及MSCDL但優於AMLWDF。雖然DADS在整體的表現並非最好，但在特別重視延遲時間的Category1類別(包含QCI級別為1、2及5的應用服務)的延遲效能僅輸AMLWDF些許，而產能卻明顯勝過AMLWDF，由此可見DADS在Category1的表現最佳。 / With the concept and technology of smart homes becoming more and more mature and popular, Internet service provider (ISP) must face managing large set of various applications from smart homes which competing for bandwidth resources. In order to enhance Quality of Services (QoS) of a lot of various applications while they are competing bandwidth resources of both smart homes (home internal) and Internet service provider (home external), we propose a QoS aware bandwidth allocation criterion to optimize Quality of user Experience (QoE). Since ISP has to manage bandwidth resources of large set of smart homes, in the proposed criterion each ISP separates the bandwidth resources for home external bandwidth and system bandwidth of ISP, respectively. Then, aggregates bandwidth requests of large number of smart homes according to distinct service classes. This thesis focuses on the performance index of delay. We proposed to classify bandwidth requests from smart homes and put them into different queues, finally, calculate priority values by DADS (Delay Aware Dynamical Scheduling) algorithm. The proposed method is able to effectively reduce delay time with certain degree of fairness guarantee by dynamically allocate bandwidth resources for services with distinct service priorities. In the experiments, we compared DADS with other algorithms such as MSCDL (Mac Scheduler), PF (Proportional Fair), TDPSS (Time Domain Priority Set Scheduler) and AMLWDF (Adaptive Modified Largest Weighted Delay First), etc. in terms of fairness, throughput, delay and jitter. The experiments results show that DADS performs much better than PF and TDPSS but a bit worse than MSCDL and AMLWDF in terms of delay. However, DADS shows no better performance than all other algorithms in terms of jitter and throughput. In fairness comparison, DADS is worse than PF, TDPSS and MSCDL but is better than AMLWDF. Though DADS has no superior performance on overall indices, it is a bit worse than AMLWDF in delay of Category1 (including QCI 1, 2 and 5), its throughput is better than AMLWDF. Therefore, DADS’s performance is the best on Category1 considering overall indices.

隨著智慧家庭技術及物聯網的裝置大幅度地成長，智慧家庭的網路流量亦隨之升高。當大量成長的智慧家庭流量造成網路壅塞時，可能使緊急服務的警告機制失效，或是造成某些應用服務品質低劣而不堪使用。這些問題恐阻礙智慧家庭未來的發展性。 為改善上述問題，本文提出創新的物聯網智慧家庭頻寬配置管理架構。以ISP業者管理數以千計的物聯網智慧家庭為情境，針對智慧家庭多樣化的應用服務，利用具前瞻性的軟體定義網路，提供ISP業者對智慧家庭外部網路頻寬做最佳化的配置。 本研究依改良後的3GPP LTE QoS Class Identifier (QCI)，分類智慧家庭的服務，並考量服務的優先權及延遲程度，提出BASH演算法。透過本研究，ISP業者能依定義好的服務類別，將匯集後的智慧家庭服務流量藉由配置訊務流(traffic flow)的權重，計算出不同服務的最佳頻寬分配量，達到提升QoS及使用者QoE的目的。 為確認本論文所提出之方法的有效性，實驗設計是利用Linux伺服器架設OpenvSwitch、Ryu控制器及Mininet模擬器，建構SDN網路環境。實驗結果顯示，本研究所提出的BASH與ISP所用的傳統頻寬分配方法相比，能有效提高30%的throughput，降低159%的delay time及967%的 jitter time。 / With the increasing number of IoT (Internet of Things) devices and advance of smart home technology, the network traffic of smart home is also raising rapidly. When network congestion occurs due to massive traffic, some emergent alert mechanisms might become invalid or cause some application services performance degraded. All kinds of these will dramatically hamper the future development of smart homes. In order to resolve these problems, we propose an innovative bandwidth allocation smart home management framework for IoT enabled smart homes. The application scope of this research assumes a scenario that an ISP (Internet Service Provider) should support thousands of IoT enabled smart homes for a variety of services. The proposed bandwidth allocation framework is based on the promising software defined networking (SDN) architecture and is responsible for optimizing bandwidth allocation on external Internet traffic. We modify the 3GPP LTE QoS Class Identifier (QCI) to adaptive to the services suitable for smart homes. The proposed bandwidth allocation smart home (BASH) algorithm considers service priority and delay at the same time. With this framework, ISP is able to optimize bandwidth allocation by aggregating thousands of classified services of smart homes and thus effectively enhance Quality of Service (QoS) and user experience (QoE). In order to verify the proposed methods, we implement a SDN environment by using Linux Ubuntu servers with Mininet, Open vSwitch and Ryu controller. The experiment results show that BASH outperforms ISP traditional method in increasing the throughput by 30%, reducing delay and jitter by 159% and 967%, respectively.

隨著物聯網這個萬物連網的概念順勢推動智慧家庭在市場裡蓬勃發展，可預期未來ISP(Internet Service Provider)業者勢必面臨大量智慧家庭中各種不同應用服務互相競爭頻寬資源的情況，甚至遇到網路滿載壅塞時造成應用服務不堪使用的情形。 為改善上述問題，本文以ISP業者管理智慧家庭中眾多的物聯網設備為情境，透過軟體定義網路 (Software Defined Network，SDN)進行頻寬排程配置，排程演算法以可兼顧公平性(fairness)、時間延遲(delay)及應用服務優先權(service priority)的A-MLWDF (Adaptive Modified Largest Weighted Delay First) [7]演算法，確保優先配置頻寬給智慧家庭中優先權較高、時效較為急迫的流量，以降低應用服務的延遲來提升智慧家庭網路之服務品質(Quality of Service，QoS)。 本研究透過OMNet++模擬器建構SDN環境與傳統環境中有眾多物聯網設備之智慧家庭。家中物聯網設備包含M2M (Machine to Machine)和非M2M(non Machine to Machine)裝置，以提供各種智慧家庭應用服務。我們透過SDN架構進行頻寬配置，達到集中式管控家中的頻寬資源，其中排程演算法包括PF、MLWDF、A-MLWDF。實驗結果顯示，以上排程演算法雖然於SDN環境下在公平性與抖動率表現並不顯著，公平性約改善1.6%及抖動率約降低1%左右，但在產能與延遲方面表現較為顯著，能有效提高產能約52%，及降低延遲約 52%。 / With the concept of IoT (Internet of Things) spread rapidly, it is the opportunity to promote smart homes in the expanding market. We can see that the future ISP (Internet Service Provider) has to face a large number of smart homes having bandwidth competition in a variety of different applications and causing application services unavailable due to network congestion.     In order to resolve the above problems, we propose that each ISP (Internet Service Provider) has to manage a large number of IoT devices in a smart home to performs bandwidth scheduling through Software Defined Network (SDN). We choose to use A-MLWDF scheduling algorithm (Adaptive Modified Largest Weighted Delay First) [7] which considers fairness, delay and service priority. A-MLWDF is able to ensure services of higher priority and emergent traffic be allocated bandwidth earlier and greatly reduce delay and thus effectively enhance Quality of Service (QoS) of smart homes.     In this research, we implement a SDN environment by using OMNet++ to simulate the bandwidth competition among smart homes with IoT devices. The IoT devices consists of M2M (Machine to Machine) and non-M2M (non Machine to Machine) devices which offer a variety of intelligent home application services. We configure the bandwidth allocation under SDN control. The scheduling algorithms include PF, MLWDF and A-MLWDF. When the network traffic is congested, SDN can significantly increase throughput and reduce latency compared to traditional network management. The experimental results show that above scheduling algorithms using SDN environment having no significant performance improvements in fairness and jitter. The fairness increases around 1.6% and the jitter reduces around 1%. However, it shows significant improvement on throughout and delay. The throughput increases around 52% and the delay reduces around 52%.

本論文針對隨機數位網路提出一套可行的計算機制，以提供網路管理者進行資源分配與壅塞管理的分析工具。我們研究兩種利潤最佳化模型，探討在預算控制下的頻寬分配方式。因為資源有限，網路管理者無法隨時提供足夠頻寬以滿足隨機的網路需求，而量測網路連結成功與否的阻塞機率(Blocking Probability)為評估此風險之一種指標。我們利用頻寬分配、網路需求量和虛擬端對端路徑的數量等變數，推導阻塞機率函數，並證明阻塞機率的單調性(Monotonicity)和凸性(Convexity)等數學性質。在不失一般性之假設下，我們驗證阻塞機率是(1)隨頻寬增加而變小；(2)在特定的頻寬分配區間內呈凸性；(3)隨網路需求量增加而變大；(4)隨虛擬路徑的數量增加而變小。 本研究探討頻寬分配與阻塞機率之關係，藉由推導單調性和凸性等性質，提供此兩種利潤模型解的最適條件與求解演算法。同時，我們引用經濟學的彈性概念，提出三種模型參數對阻塞機率變化量的彈性定義，並分別進行頻寬分配、網路需求量和虛擬路徑數量對邊際利潤函數的敏感度分析。當網路上的虛擬路徑數量非常大時，阻塞機率的計算將變得複雜難解，因此我們利用高負荷極限理論(Heavy-Traffic Limit Theorem)提供阻塞機率的估計式，並分析其漸近行為(Asymptotic Behavior)。本論文的主要貢獻是分析頻寬分配與阻塞機率之間的關係及其數學性質。網路管理者可應用本研究提出的分析工具，在總預算限制下規劃寬頻網路的資源分配，並根據阻塞機率進行網路參數的調控。 / This thesis considers the problem of bandwidth allocation on communication networks with multiple traffic classes, where bandwidth is determined under the budget constraint. Due to the limited budget, there exists a risk that the network service providers can not assert a 100% guaranteed availability for the stochastic traffic demand at all times. We derive the blocking probabilities of connections as a function of bandwidth, traffic demand and the available number of virtual end-to-end paths for all service classes. Under general assumptions, we prove that the blocking probability is directionally (i) decreasing in bandwidth, (ii) convex in bandwidth for specific regions, (iii) increasing in traffic demand, and (iv) decreasing in the number of virtual paths. We also demonstrate the monotone and convex relations among those model parameters and the expected path occupancy. As the number of virtual paths is huge, we derive a heavy-traffic queueing model, and provide a diffusion approximation and its asymptotic analysis for the blocking probability, where the traffic intensity increases to one from below. Taking the blocking probability into account, two revenue management schemes are introduced to allocate bandwidth under budget control. The revenue/profit functions are studied in this thesis through the monotonicity and convexity of the blocking probability and expected path occupancy. Optimality conditions are derived to obtain an optimal bandwidth allocation for two revenue management schemes, and a solution algorithm is developed to allocate limited budget among competing traffic classes. In addition, we present three elasticities of the blocking probability to study the effect of changing model parameters on the average revenue in analysis of economic models. The sensitivity analysis and economic elasticity notions are proposed to investigate the marginal revenue for a given traffic class by changing bandwidth, traffic demand and the number of virtual paths, respectively. The main contribution of the present work is to prove the relationship between the blocking probability and allocated bandwidth under the budget constraint. Those results are also verified with numerical examples interpreting the blocking probability, utilization level, average revenue, etc. The relationship between blocking probability and bandwidth allocation can be applied in the design and provision of broadband communication networks by optimally choosing model parameters under budget control for sharing bandwidth in terms of blocking/congestion costs.

大型天然災害會癱瘓通訊系統，嚴重影響到救災效率，本論文旨在快速進行可用連外頻寬分配，供應急通訊系統使用。無線通訊技術的成熟，為使用者帶來極大的便利性，但當發生大規模的地震或強烈颱風等重大天然災害時，通訊系統卻常常因架構等因素，隨著電力與交通系統的損毀而癱瘓。由歷年大型災變中多數災區內之行動通訊系統全面中斷即可印證行動通訊系統其實是極為脆弱，而有效運作的通訊系統卻是災情傳遞、資源調度以及互助協調是否順利的關鍵因素。 本篇論文所探討的應急通訊系統是利用倖存的連通基地台和斷訊卻沒有損毀的基地台，以無線電連接起來建構一個臨時性的通訊系統，稱為應急蜂巢式行動通訊網路(Contingency Cellular Network，CCN)。由於CCN的連外頻寬有限，大量話務將造成通訊系統壅塞，影響重要訊息傳遞，且災區各個地方受災情況不盡相同，使得 CCN 的頻寬資源需視各地災情緊急程度與需求進行規劃配置，以充分發揮頻寬效益傳遞重要資訊。本論文主要在探討如何在CCN網路拓樸已決定的情況下進行頻寬分配，以達到最大的救災效益。因此我們提出一適合 CCN 樹狀結構的頻寬分配優化模型，以追求救災效益的最大化，這個模型可供使用者(救災指揮單位)系統化的解決 CCN 頻寬分配問題。 本論文所提出的頻寬分配模型包含 CCN 樹狀拓樸、基地台數目、可用之連外頻寬資源限制、各基地台Backhaul頻寬限制、基本頻寬需求限制、差異化之通訊品質通道和效益遞減函數。我們證明此模型是NP-Hard問題，並提出一個考慮各基地台的災情緊急程度以及通訊品質需求差異而進行快速頻寬分配的演算法，此演算法透過計算頻寬分配總救災效益決定優劣。經實驗，可快速得出接近最佳解的頻寬分配結果。 / When stricken by a large-scale disaster, the efficiency of disaster response operation is very critical to life saving. We propose to build a contingency cellular network to support emergency communication in large scale natural disasters by connecting disconnected base stations. This thesis addresses the bandwidth allocation problem. The advance of mobile communication technologies has brought great convenience to users. Cellular phone becomes the first communication tool most people would use in emergency. However, cellular networks were usually crashed in earthquake, typhoons or other natural disasters due to power outage or backhaul breakage. Unfortunately, the efficiency of communication system is a critical factor to the success of disaster response operation such as resource allocation as well as coordination of rescue and relief operations. We designed a contingency cellular network (CCN) by connecting physically intact but service-disrupted base stations together with wireless links. As the bandwidth resource in CCN is limited, a smart bandwidth allocation to facilitate prioritized bandwidth sharing will maximize the contribution of CCN to the disaster response operation. We model the CCN Bandwidth Allocation Problem into a Nested 0-1 Knapsack Problem aiming to maximize disaster operation efficiency. The problem is proven to be NP Hard. We also design an efficient heuristic algorithm to solve the problem when it is needed in urgent.