考慮資源運輸路徑之應急蜂巢式行動通訊網路建置排程

高采衣

當發生大規模的地震或強烈的颱風等重大天然災害時，通訊系統常常隨著電力與交通系統的損毀而癱瘓。由歷年大型災變中多數災區內之行動通訊系統全面中斷即可印證行動通訊系統其實是極為脆弱的，然而有效運作的通訊系統卻是災情傳遞、資源調度及救災是否順利的關鍵因素。本文所探討的應急通訊系統利用倖存的連通基地台和斷訊卻沒有損毀的基地台，以無線電連接起來建構一個臨時性的通訊系統，稱為應急蜂巢式行動通訊網路(Contingency Cellular Network，CCN)。

由於各地災情狀況不完全相同，CCN的建構順序必須考慮災區的輕重緩急、時間的急迫等因素依序建構。因此當CCN拓樸規劃完成後，根據CCN拓樸、各地災情嚴重程度以及拓樸中基地台間的相對距離(運輸時間)進行基地台建構排程規劃，以達到最大的總救災效益。

本文考慮各基地台所能發揮的救災效益、所需建構時間、以及運輸工具從任一基地台到另一基地台所需運輸時間，提出兩個適合CCN拓樸樹狀結構的考慮資源運輸路徑之最佳化排程模型CCNDS-AC和CCNDS-UC。CCNDS-AC限制建構順序必須從連網台往下循序建構，但CCN-UC則否。因發生突發性大型天然災害時，可容許的計算時間相當短暫，因此提出了兩個快速的啟發式演算法 DS-ACG與DS-UCB，可在短時間內求出一組相當逼近於最佳解的建構排程順序，與DS-UCB相互比較。

本文以電腦模擬的方式進行小規模實驗與大規模實驗評估，並且用Genetic Algorithm來比較啟發式演算法的效能。結果顯示DS-UCB 明顯優於DS-ACG及Genetic Algorithm。在小規模實驗中DS-UCB可求得與最佳解的總救災效益誤差平均約0.9%的近似最佳解建構順序。而在大規模實驗下， DS-UCB與十萬個解中的最佳解─pseudo optimal solution相較，總救災效益平均高出約16.7%，而總救災時間平均約少了19.4%。

Resource Delivery Path Dependent Deployment Scheduling for Contingency Cellular Network

When stricken by a large-scale disaster, the efficiency of disaster response operation is very critical to life saving. 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. We designed a contingency cellular network (CCN) by connecting physically intact but service-disrupted base stations together with wireless links. Since the transportation capacity may be very limited, scheduling of CCN deployment order according to the demand of disaster operation and traveling time between base stations becomes an important issue.

We propose two optimization models: CCN Deployment Scheduling Antecessor Constrained Problem (CCNDS-AC) and CCN Deployment Scheduling Unconstrained Problem (CCNDS-UC), aiming to maximize the efficiency of disaster response operation. Both problems are proven to be NP Hard. We also designed two rapid heuristic algorithms, DS-ASG and DS-UCB to solve the problems respectively when it is needed in urgent.

Finally, we evaluated the proposed algorithms against optimal solutions (in small cases only) as well as genetic algorithm by simulation. The experimental results show that DS-UCB outperforms all other algorithms. In small scale cases, the profit obtained by DS-UCB is only 0.9% smaller than what the optimum solution can get. In large scale cases, as compared to the pseudo optimum solution, which is the best solution among 100,000 solutions, DS-UCB outperforms pseudo optimum solutions in profit by 16.7%, and in traveling time by 19.4%, both in average.