當發生大規模地震或強烈颱風等大型天然災害，其災後72小時為人命搜救之黃金期。由歷來的大型災變中，可知行動通訊系統其實極為脆弱且不可靠，而通訊系統癱瘓將影響救災工作之成效。本論文中探討的應急通訊系統利用倖存之連通基地台和斷訊卻沒有損毀的基地台，以無線電互相連接成一個轉送拓樸以建構臨時性通訊系統，稱為應急蜂巢式行動通訊網路(Contingency Cellular Network，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 degradation. Our research results provide users a fundamental base to determine their availability requirement at a countable performance degradation.

Indiana University-Purdue University Indianapolis (IUPUI) / Collaborative helping via social networking conversation threads can pose serious challenges in emergency situations. Interfaces that support complex group interaction and sense-making can help. This research applies human-computer interaction (HCI), computer-supported cooperative work (CSCW), and collaboration engineering in developing an interactive design, the Mega-Collaboration Tool (MCT). The goal is to reduce the cognitive load of a group’s growing mental model, thus increasing the general public’s ability to organize spontaneous collaborative helping. The specific aims of this research include understanding the dynamics of mental model negotiation and determining whether MCT can assist the group’s sense-making ability without increasing net cognitive load. The proposed HCI theory is that interfaces supporting collaborative cognition motivate contribution and reduce information bias, thus increasing the information shared. These research questions are addressed: 1. Does MCT support better collaborative cognition? 2. Does increasing the size of the shared data repository increase the amount of information shared? 3. Does this happen because group members experience 1) a greater sense of strategic commitment to the knowledge structure, 2) increased intrinsic motivation to contribute, and 3) reduced resistance to sharing information? These questions were affirmed to varying degrees, giving insight into the collaborative process. Greater content did not motive group members directly; instead, half of their motivation came from awareness of their contribution’s relevance. Greater content and organization improved this awareness, and also encouraged sharing through increased enthusiasm and reduced bias. Increased commitment was a result of this process, rather than a cause. Also, MCT increased collaborative cognition but was significantly hampered by Internet performance. This challenge indicates MCT’s system components should be redesigned to allow asynchronous interaction. These results should contribute to the development of MCT, other collaboration engineering applications, and HCI and information science theory.

In recent years, social media platforms such as Twitter and Facebook have emerged as effective tools for broadcasting messages worldwide during disaster events. With millions of messages posted through these services during such events, it has become imperative to identify valuable information that can help the emergency responders to develop effective relief efforts and aid victims. Many studies implied that the role of social media during disasters is invaluable and can be incorporated into emergency decision-making process. However, due to the "big data" nature of social media, it is very labor-intensive to employ human resources to sift through social media posts and categorize/classify them as useful information. Hence, there is a growing need for machine intelligence to automate the process of extracting useful information from the social media data during disaster events. This dissertation addresses the following questions: In a social media stream of messages, what is the useful information to be extracted that can help emergency response organizations to become more situationally aware during and following a disaster? What are the features (or patterns) that can contribute to automatically identifying messages that are useful during disasters? We explored a wide variety of features in conjunction with supervised learning algorithms to automatically identify messages that are useful during disaster events. The feature design includes sentiment features to extract the geo-mapped sentiment expressed in tweets, as well as tweet-content and user detail features to predict the likelihood of the information contained in a tweet to be quickly spread in the network. Further experimentation is carried out to see how these features help in identifying the informative tweets and filter out those tweets that are conversational in nature.

當大型災害來臨，通訊系統對救災效益具有不可或缺的重要性。然而，一般公眾通訊系統，如行動通訊網路等，常因各種不同因素導致系統攤瘓，使得協調大批非組織的救災志工，顯得異常困難。現存多個緊急通訊系統的佈建，需仰頼良好的交通運輸。不幸的是，部分道路和橋樑常因大型災害而斷裂或變型，導致災區對外交通運輸中斷，無法快速的將緊急通訊系統的網路元件，運送至災區佈建。我們提出應急行動通訊系統(Contingency Cellular Network, CCN) 以提供災區救災工作的緊急通訊。部分行動基地台雖然結構完整，但因失去與核心網路連線能力或電力供應，而無法提供服務，成為孤立基地台。應急行動通訊網路(CCN) 搭配無線通訊與衛星通訊技術建置一多重跳接無線網路，以恢復孤立基地台與核心網路連線能力；並配備發電機，提供電力，使孤立基地台可提供有限的服務。救災志工和災民無需使用特殊手持設備或額外的訓練，只需使用原有的手機，即可使用CCN的應急通訊服務。CCN可於第一時間，提供大批救災志工和災民通訊服務，以提高救災效益，因而拯救更多寶貴的生命。 本論文主要聚焦在應急行動通訊系統設計所衍生出的相關議題，如 應急網路需求分析、系統架構設計、網路拓樸規劃、網路頻寬規劃、佈署行程規劃等議題。本論文針對網路拓樸規劃、網路頻寬規劃、佈署行程規劃問題以數學模式進行塑模並證明這些問題為NP-Hard問題。因網路拓樸規劃、網路頻寬規劃、佈署行程規劃需緊急完成，我們也提出啟發式算法快速解決這些規劃問題。實驗結果顯示，這些啟發式算法均具良好的效能。 / Communication system is crucial to the efficiency of disaster response operation in the large-scale disaster. However, communication systems, such as cellular networks, usually crashed due to various causes making coordination among disorganized disaster responders extremely difficult. Unfortunately, rapid deployment of many existing emergency communication systems relies on a good transportation system, which is usually not available in a catastrophic natural disaster. We proposed a Contingency Cellular Network (CCN) for emergency communication by connecting disconnected base stations together with wireless links to construct a wireless multi-hop cellular network. CCN can support existing mobile phone users with reduced capability. Such a system can support a large number of disaster responders in the early hours of a catastrophic natural disaster, thus save many lives. Our research addresses the design issues of the network topology of CCN, such as network topology planning, bandwidth management, deployment scheduling and etc., and we take the degree of emergency and population of each stricken area as the priority measure as well as the available resources as the constraint to determine the network topology. Mathematical models of these design issues are proposed and proved as NP-Hard problems. Since the network topology, bandwidth management, deployment scheduling are needed in urgent, we propose heuristic algorithms to solve these problems quickly. Finally, we evaluated the proposed algorithms by simulation. A significant improvement in resiliency is reached.

大型天然災害會癱瘓通訊系統，嚴重影響到救災效率，本論文旨在快速進行可用連外頻寬分配，供應急通訊系統使用。無線通訊技術的成熟，為使用者帶來極大的便利性，但當發生大規模的地震或強烈颱風等重大天然災害時，通訊系統卻常常因架構等因素，隨著電力與交通系統的損毀而癱瘓。由歷年大型災變中多數災區內之行動通訊系統全面中斷即可印證行動通訊系統其實是極為脆弱，而有效運作的通訊系統卻是災情傳遞、資源調度以及互助協調是否順利的關鍵因素。 本篇論文所探討的應急通訊系統是利用倖存的連通基地台和斷訊卻沒有損毀的基地台，以無線電連接起來建構一個臨時性的通訊系統，稱為應急蜂巢式行動通訊網路(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.