應急蜂巢式行動通訊網路的多路徑拓撲設計 當發生大規模地震或強烈颱風等大型天然災害,其災後72小時為人命搜救 之黃金期。由歷來的大型災變中,可知行動通訊系統其實極為脆弱且不可靠,而 通訊系統癱瘓將影響救災工作之成效。本論文中探討的應急通訊系統利用倖存之 連通基地台和斷訊卻沒有損毀的基地台,以無線電建構臨時性通訊系統,稱為應 急蜂巢式行動通訊網路(Contingency Cellular Network,CCN)。
在災難發生後,災區通常有許多須要較高通話需求的關鍵區域,其通話需求 遠高於輕度災區,建置CCN時必須優先保障其通訊需求,我們先前研究所提出 初步的CCN樹狀拓撲其結構較脆弱,若任何一個link斷訊,則其結構以下的使 用者通訊將受到影響,導致任何一個節點對外通訊能力非常脆弱,影響CCN之 可用度。為了提升CCN之可用度,我們提出了多路徑的CCN網路拓撲解決方 案,在本方案中,每個關鍵區域都有數條對外通訊的連線。 本論文以各基地台通訊範圍內的通訊需求人數與災區毀損程度,作為效益參數, 在有限緊急修復資源下,將問題塑模為一個類似K-Maximum Spanning Tree問題 的Length Bounded Disjoint K-Path Max-Profit Mesh問題,我們證明它屬於 NP-Hard問題,並且提出快速且效能不差之啟發式演算法,可在緊急時建立應急 蜂巢式行動網路的多路徑網路拓樸。本文以電腦模擬方式,進行實驗以驗證我們 的模型正確可行,並評估多路徑拓撲可提升之CCN可靠度,實驗結果提供使用 者依不同的CCN可靠度及總救災效益需求,選擇所需之多路徑數量。
When stricken by a catastrophic natural disaster, the golden 72 hours is very critical to life saving. However, communication systems including cellular networks often crashed due to various causes making big impact to the efficiency of disaster response. Our research proposes the Contingency Cellular Network (CCN) by connecting disconnected base stations together using wireless links to form an overlay Ad Hoc network over a disconnected cellular network.
In our previous study, we proposed a tree topology to construct CCN, which is vulnerable since a single link failure may have a big impact to the availability of CCN. This thesis proposes a multi-path topology to enhance the availability of CCN such that the selected critical areas will have redundant communication paths connecting to the core network and thus, have higher resiliency against link failure. We model the CCN Multi-path Network Topology Design problem into a combinatorial problem, called Length Bounded Disjoint K-Path Max-Profit Mesh Problem. We take the degree of emergency and the population of each stricken area as the priority measure as well as the amount of emergency recovery resources as the capacity constraint in the topology computation model. The problem is proven to be NP Hard. Therefore, we designed an efficient heuristic algorithm (HLBDK) to solve the problem when it is needed in urgent. Finally, we evaluated the proposed algorithm by simulation. The simulation results show that the average performance deviation of the proposed heuristic algorithm away from the optimal solutions is smaller than 7% in all cases. A significant improvement in the availability can be obtained by using multi-path topology at a reasonable performance loss. Our research results provide users a fundamental base to determine their availability requirement at a countable performance loss.