應急蜂巢式行動通訊網路的跨基地台頻寬分配

Cross Base Station Bandwidth Allocation for Contingency Cellular Network

黃郁翔

大型天然災害會癱瘓通訊系統，嚴重影響到救災效率，本論文旨在快速進行可用的鄰台間無線電鏈結頻寬分配，供應急通訊系統使用。無線通訊技術的成熟，為使用者帶來極大的便利性，但當發生大規模的地震或強烈颱風等重大天然災害時，通訊系統卻常常因架構等因素，隨著電力與交通系統的損毀而癱瘓。由歷年大型災變中多數災區內之行動通訊系統全面中斷即可印證行動通訊系統其實是極為脆弱，而有效運作的通訊系統卻是災情傳遞、資源調度以及互助協調是否順利的關鍵因素。

本文所探討的應急通訊系統是利用倖存的連通基地台和斷訊卻沒有損毀的基地台，以無線電連接起來建構一個臨時性的通訊系統，稱為應急蜂巢式行動通訊網路(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(分配至某需求隊的頻道數)效益遞減函數所付出的效益成本較小。

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 inter-BS wireless bandwidth in CCN is limited, a smart bandwidth allocation to facilitate prioritized bandwidth sharing will greatly improve the efficiency of the disaster response operation. We model the CCN Cross Base Station Bandwidth Allocation Problem into a Cross Base Station Bandwidth Allocation Problem (CBBA), which can be treated as a special version of 0-1 Knapsack Problem, aiming to maximize the efficiency of disaster response operation. The problem is proven to be NP Hard. We also design a rapid greedy based heuristic algorithm to solve the problem when it is needed in urgent.

Finally, we evaluated different versions of the proposed algorithm by simulation. The experiments show that the algorithm that uses additive profit desity as the greedy selection critiria performs the best among all three versions. In 10 small random cases, the performance degradation as compared to the optimum solution is no more than 9.4%. In 10 large randam cases, the performance improvement as compared to the psuedo optimum solution is over at least 21.8% and at most 43.26%. We also evaluated attenuation function by uint cost of coverage improvement. The experiments show that the attenuation function of 1/sqrt (number of channels assign to a path) has lower cost.