Bandwidth Allocation For Contingency Cellular Network 應急蜂巢式行動通訊網路的頻寬分配 Bandwidth Allocation For Contingency Cellular Network 指導教授：連耀南教授 研究生：吳雲鼎

Outline Introduction Related work Contingency Cellular Network (CCN) Communication systems crash by natural disasters Requirements analysis of contingency communication system Related work Common contingency communication systems Contingency Cellular Network (CCN) Bandwidth allocation for CCN Concept Problem definition Model Algorithm design Evaluation Summary & future work Disaster task group & communications category

Outline Introduction Related work Contingency Cellular Network (CCN) Communication systems crash by natural disasters Requirements analysis of contingency communication system Related work Common contingency communication systems Contingency Cellular Network (CCN) Bandwidth allocation for CCN Concept Problem definition Model Algorithm design Evaluation Summary & future work Disaster task group & communications category

Introduction 全球天災頻傳，極端氣候、大型地震…等，造成大範圍災害 無線通訊已完全融入一般大眾的生活之中，當大規模的地震或強烈颱風等重大天然災害發生時，通訊系統卻常常癱瘓 有效運作的通訊系統是災情傳遞及救災調度、協調是否成功的關鍵因素

大型天然災害發生時救災面臨的挑戰 災區交通癱瘓 通訊網路幾乎癱瘓，通訊設備缺乏 外援進入緩慢 專業救災人員及設備嚴重不足 第一線救援仰賴當地人員 通訊網路幾乎癱瘓，通訊設備缺乏 救災人員彼此溝通困難 資訊不完整 救災資源不易協調分配而錯置 誤判情勢 錯失救援機會 5

大型天然災害發生時救災面臨的挑戰 通訊系統在大型天然災害中 需要能快速建置的應急通訊系統 供給受災相關人員使用 十分脆弱 對救難、救濟影響甚鉅 需要能快速建置的應急通訊系統 提高救災效率 供給受災相關人員使用 救難人員 災民 政府救災單位

大型天然災害對通訊的衝擊 橋樑、道路中斷 建物倒塌 加深救災人員通訊難度 通訊系統的實體線路斷裂 主、備援線路可能一倂毀損 通訊設備損毀 八八水災

大型天然災害對通訊系統的影響 固網與行動通訊系統癱瘓 通訊設備修復困難 機房斷電 固定線路毀損 基地台或機房毀損 921地震 88水災 基地台—BSC/RNC—行動交換機(MSC) 基地台或機房毀損 通訊設備修復困難 921地震 中華電信耗費15天，搶通災區電信網路 88水災 斷訊基地台總數達3302座 中華電信斷訊基地台達1800座 550座在兩天之後仍無法恢復運轉 造成通訊系統的損害,原因包括 資料來源: 國家通訊傳播委員會、中華電信 8

Golden 72 Hours 人員受困，黃金72小時亟待救援 The survival rate is 90% within 24 hours; 50% between 24 and 48 hours; 20% between 48 and 72 hours. The chances of survival over 72 hours are quite rare. 通訊設備修復困難, 仍需面對救援黃金72小時的挑戰, 隨時監,存活率快速下降 資料來源: http://baike.baidu.com

應急通訊系統需求 建置需求 運轉需求 網路元件必須取得容易 建置難度低 建置速度快 使用端設備數量多、成本低 易於使用，不需特別訓練 具備允入控制機制，可抵擋瞬增的話務量 具救災緊急通話先行之功能 具行動能力 由於時間與資源的限制, 挑戰與特殊需求

應急通訊系統評估指標 使用成本 建構難易度 進入災區難易度 終端設備普及率 終端設備操作難易度 終端設備可移動性 通訊品質 系統運轉難易度 使用成本：廣泛使用此緊急通訊系統的成本 建構難易度：將此緊急通訊系統建構起來的困難度 進入災區難易度：將緊急通訊系統運送進災區的難易度 終端設備普及率：災區人員具有此緊急通訊系統通訊設備的程度 終端設備操作難易度：災區人員操作此通訊設備的難易度 終端設備可移動性：災區人員攜帶通訊設備移動的能力 通訊品質：利用此緊急通訊系統的通訊品質 系統運轉難易度：緊急通訊系統架構起來後維持運轉的難易度

Outline Introduction Related work Contingency Cellular Network (CCN) Communication systems crash by natural disasters Requirements analysis of contingency communication system Related work Common contingency communication systems Contingency Cellular Network (CCN) Bandwidth allocation for CCN Concept Problem definition Model Algorithm design Evaluation Summary & future work Disaster task group & communications category

常見應急通訊系統—專用高抗災通信平臺 專用高抗災通信平臺 優點 限制 以「消防救災體系與行動通信系統結合」、「整合光纖、微波、衛星鏈路形成多重中繼傳輸備援路由」及「加強電力備援系統」為設計理念 在災前預先佈建強固機房，並於特定基地台佈建衛星、微波等無線通訊設備，以確保政府救災體系緊急通訊順暢 優點 災前即已佈建完成，災難發生時，馬上就可以使用 系統可靠性高 結合行動通信系統與消防救災體系 限制 成本過高，數量遠遠不足，僅侷限於少數固定的特定區域 由於數量稀少，無法供應數量龐大的志願救災人員使用 強固:電力,備用backhual

常見應急通訊系統—無線對講機 無線對講機(Walkie-Talkie) 優點 限制 手持的雙向無線電收發器，特徵為半雙工 輸出功率越強，發射信號的覆蓋範圍越大 環境的電磁干擾、建築物、天氣情況和地形差別會直接影響信號的覆蓋範圍 優點 體積小重量輕，可隨身攜帶 電池充電後可長時間使用 不需佈建通訊網路即可使用 限制 全世界很多地方普及率低 (e.g. 台灣) 需要簡單學習才能使用 沒有優先分級能力

常見應急通訊系統—業餘無線電 業餘無線電(Amateur radio) 優點 限制 俗稱火腿(Ham radio)，與無線對講機相似，但通訊的距離較遠 優點 電波所及範圍內即使不知道對方身份地點亦可大範圍廣播通訊，適合做訊息發佈功能 不需佈建通訊網路即可使用 限制 普及率低 使用上困難，需要執照方能操作，沒受過訓練很難直接使用 行動力低

常見應急通訊系統 —行動衛星通訊 行動衛星通訊 優點 限制 通訊衛星為一個掛在空中的通訊中繼站 目前常用於行動衛星通訊的為中低軌道衛星，中地球軌道(MEO: Medium-Earth Orbit)距地5000~15000km，如美國的奧德塞計劃(Odyssey)；低地球軌道(LEO: Low-Earth Orbit)距地500~1500km的高度，如Motorola銥計劃(Iridium) 優點 覆蓋面廣，通訊距離遠 不受地震等天災、地理條件影響限制 可隨身攜帶 限制 普及率非常低 易受天候影響 手持終端可隨身攜帶

常見應急通訊系統 —集群通訊系統 集群通訊系統(Trunking radio) 優點 限制 專業用應急通訊系統，如Project 25、TETRA 由早期的專用無線電調度系統逐漸發展形成的 具備群組呼叫、優先分級等能力 由中央控制器集中控制和管理系統中的每一個頻段，以動態方式迅速的把空閒頻段分配出去，用戶群會呈現樹狀結構 優點 通訊網路架設快 涵蓋範圍廣 可靠性高 限制 話機數量有限 需經專業訓練，主要使用者為軍方或專業救難隊 如果交通系統癱瘓，不易運送至災區，因體積、重量過大無法空投 A hand-held Project 25 radio used in US systems

常見應急通訊系統—移動基地台 移動基地台 優點 限制 一個可移動的通訊系統 實際處理現場傳輸來的語音、影像、圖片等數據，實現現場各種不同規格、不同頻段的通訊網路的交換，構成統一的應急指揮平台 目前中華電信北部有18台、中部有11台、南部有8台移動基地台 優點 架設速度快 運用靈活，調度方便 限制 造價昂貴，數量稀少 交通可能斷絕，難以移動到災區 設備龐大無法空運

研究中的應急通訊系統—MANET MANET(Mobile Adhoc Network ) P2Pnet 優點 限制 利用志願救災人員帶有無線區域網路的筆記型電腦或智慧型手機以Multi-hop Ad-Hoc Network方式連接成一個 MANET，在沒有連接Internet、沒有伺服器的情況下利用VoIP支援緊急的通訊與資訊運用 優點 可使用災區內志願救災人員的筆電等設備就地取材來建構，節省大量經費 不受交通系統癱瘓之影響，就地取材，立即建構，在第一時間投入救災 限制 使用者必須具備建置系統的技術知識，並非一般使用者可以使用 具通話品質的VoIP之有效距離極短，有待克服 尚在實驗階段，並無成熟產品，尚須繁複的設定方能使用

應急通訊系統比較 使用成本 建構難 易度 進入災區難易度 終端設備普及率 終端設備操作難易度 終端設備移動性 通訊品質 運轉難易度 Walkie- Talkie 低 不需建構 易 視地區而定 需簡單學習 高 中 無 Amateur Radio 需專業人士架構 需專業執照 行動衛星通訊 極高 既存 集群通訊系統 (量少) 簡單 難(需道路運送) 移動式基地台 MANET 需專業安裝設定 就地取材 在8個評估指標各有優劣

Outline Introduction Related work Contingency Cellular Network (CCN) Communication systems crash by natural disasters Requirements analysis of contingency communication system Related work Common contingency communication systems Contingency Cellular Network (CCN) Bandwidth allocation for CCN Concept Problem definition Model Algorithm design Evaluation Summary & future work Disaster task group & communications category

CCN Introduction 應急蜂巢式行動通訊網路, CCN 無線通訊連接斷訊基地台群 建立臨時應急行動通訊網路 使用時機 CCN 使災區人員能利用手機通訊 使用時機 在黃金救援時期內提供通訊 CCN Regular cell phone system time usability 先講what’s CCN, 無線電串聯斷訊但完好的基地台 先講是啥, 再說好處 在黃金救援時期內提供通訊, 隨業者修復, 使用時機逐漸減少 22

CCN可行性分析 利用2G、3G行動通訊網路 Reuse原有基地台 基地台的分佈topology，經完善規劃 建置成本低 可快速佈建 手機普及率非常高 不需改裝即可投入使用 使用者不需訓練 Reuse原有基地台 停斷電、後端線路毀損 大部分斷訊基地台，本身無毀損 基地台的分佈topology，經完善規劃 不需費時選擇應急通訊系統的基站地點 置於高處 訊號良好、較少line-of-sight問題 建置成本低 利用既有的基地台設備及手機 可快速佈建 基地台都已在災區內 額外設備(緊急修復包)重量極輕，可空運或空投

CCN系統元件 Connected station(連網台) Isolated station(孤立台) Contingency Recover Package(應急修復包) Power module Inter-Cell Communications Module (ICC Module) Emulated Controller Module (EC Module) Satellite Communications Module (optional) 孤立台 連網台 衛星通訊設備 由原有的行動電話基地台改裝而成 孤立台 (ICC Module) 發電機

CCN網路架構 ICC Module ICC Module 不斷串聯,多重跳接to連網台,再到核心網路

CCN建置與運轉流程 第一階段：災情評估 (Damage Assessment Phase) 第二階段：緊急維修規劃期 (CCN Planning Phase) 例如：網路拓樸規劃、建構排程、頻寬分配 第三階段：緊急維修建置期 (CCN Deployment Phase) 第四階段：緊急服務運轉期 (CCN Operation Phase) 例如：允入控制 Core Network EC Module 發電機 連網台 孤立台 衛星通訊設備 Phase1評估災情是否需CCN 26

CCN通話分類 通話分類 功能 發/受話端 說明 S Signaling Traffic Base Station ↔ Radio Core Network 用以傳送control message以及call setup 1 急難救助 受困人員 → 災區(外)民眾 緊急救難人員 緊急救難中心 受困民眾對外求援之用 2 災情回報 災區居民 各地災情狀況之回報、傳達 3 救災相關 受困民眾/災區居民 救災資源分配、指揮調度、救災人員追蹤以及二次災害之預警等 A 緊急醫療救護及協助 B 醫療設備、器材、人員之調度 C 緊急救難機具及設備調度 D 二次災難預警廣播 E 受災民眾協尋作業 F 救援物資之協調、調度、補給、發放 G 緊急救難人員調度、狀況回報 H 後續就醫治療及照護 4 互道平安 災區外民眾 緊急救難人員親屬 脫困人員報平安、災區外人員詢問災區內民眾狀況 優先權不同, 雖然分priority,但無法知道通話人是誰,優先權為何

通訊品質需求(Bandwidth/channel) CCN差異化通訊品質 CCN channel分級 使用者 話務功能性需求 救難人員 災情通報 災民 慰問關懷 差異化災區通訊服務品質 依話務功能性區分通訊品質 差異化有助提升頻寬使用效益 不同使用者話務重要性不同 頻寬資源有限，須妥善運用 重要服務給予較高QoS CCN 不同品質channel設計 話務功能性需求 通訊品質需求(Bandwidth/channel) 災情通報 e.g.64K 慰問關懷 e.g.16K 64K channel 16K channel 差異化QOS是對內,對外無QOS,因CCN無法控制外部,只有總頻寬 差異化有助提升頻寬使用效益(提高服務量):基於3項原因 血型:communication清晰的重要 連外3G已是all IP network, 可以切頻寬 彈性調配 重要服務給予較高QoS 如 HIV … communication出問題後果嚴重,應給予高頻寬減考溝通錯誤,較無critical,如調一部怪手來,救給較低qos,這樣可擠出更多頻寬服務更多user 差異化可提升頻寬使用效益 不同使用者話務重要性不同，適度滿足通訊需求 頻寬資源有限，須妥善運用，提供更大的服務量 優先集群模式,有優先權的人都註冊了,其他default priority, 受困民眾則用119 血型： AB 血型： A

CCN通訊模式 一般模式(Ordinary Mode) 無線對講機模式(Walkie-Talkie Mode) CCN範圍內的手機可與CCN內、外任何電話通訊 佔用連外資源 差異化優先等級允入控制 無線對講機模式(Walkie-Talkie Mode) CCN網路內部同一個基地台信號範圍內的通訊 CCN基地台無線電頻道閒置 志願救災人員無由得知欲通話對象之電話號碼 沒有限定接收者的廣播模式非常適合災區使用 使用者告知 由119轉告 (CCN-119) 國家指定特殊緊急號碼，如118 簡訊傳送服務範圍內所有手機通知撥號方式 根據災區使用者需求的分析,設計三種mode 因基地台分配到的頻寬資源很少,使得CCN基地台無線電頻道閒置 國家指定特殊緊急號碼, 如118, 推動難度較高

CCN通訊模式 優先群集模式(Priority Group Mode) 災區的救災通訊共同特色 規劃原則 允入控制 CCN內部用臨時碼指派 彼此不知電話號碼，也沒有時間記憶或記錄對方號碼 大部分的通訊是對特定角色，而非特定個人 緊急程度較高，且各有不同 規劃原則 每一個群體，指定一個代表號，有優先順序 群體的成員註冊其電話號碼及所屬群體 被叫時，該群體所有成員都會接到來電訊號 群體中的任一個成員可以承接呼叫 允入控制 CCN內部用臨時碼指派 參考國家編碼計畫，採用12或其他1字頭的三位或四位號碼 簡化撥號 允入控制 依CCN DB群體優先權 臨時碼指派給user 當HLR連不上時

應急通訊系統比較 使用成本 建構難 易度 進入災區難易度 終端設備普及率 終端設備操作難易度 終端設備移動性 通訊品質 運轉難易度 Walkie- Talkie 低 不需建構 易 視地區而定 需簡單學習 高 中 無 Amateur Radio 需專業人士架構 需專業執照 行動衛星通訊 極高 既存 集群通訊系統 (量少) 簡單 難(需道路運送) 移動式基地台 MANET 需專業安裝設定 就地取材 CCN 應急通訊系統 重量輕 可空運 CCN相當具有可行性

建構 CCN 需克服的相關議題 整體網路拓樸規劃 建構排程 頻寬分配 Intranet建構 基地台介面整合 多數的基地台無法直接連上後端網路，需透過多重跳接的方式連上。網路拓樸的規劃將決定整個網路的效能、救災效益和穩定度 建構排程 在資源有限情況下，找出最佳建構順序，達到最大救災效益 頻寬分配 CCN頻寬有限且各基地台除本地流量外，需轉送鄰台流量，因此每個基地台可接受的使用者數量需作合理分配，避免分配失衡，同時找出最佳頻寬分配，達到最大救災效益 Intranet建構 封包傳送路徑均需繞送至後端核心網路的交換機進行連接，Intranet的建構讓同屬同一基地台的手機之間可以利用閒置頻道彼此互通，而不需佔用基地台連外頻寬 基地台介面整合 外來設備必須無縫的與基地台介接，包括各種通訊協定，確保基地台可恢復運作 建構排程: 修復包, 載具, 工作組

建構 CCN 需克服的相關議題 允入政策制定 自動化建構 跨網路CCN 設計出一套priority based admission control policy 自動化建構 以事先架設EC module為前提，設計一套分散式演算法，產生forwarding tree，自動建構CCN網路，提供通訊服務，直到電源中斷服務停止 跨網路CCN 聯合各家公司的基地台，使建成CCN的機會大幅增加

CCN頻寬適當配置的效益 依據災區人口與受災程度適當分配頻寬，反映災區需求 頻寬充分使用，提升救災效益 保留少部分高品質通訊資源，供緊急、重要話務使用 我們只針對允入的,作頻寬分配, 考慮到需求(如 人口, 緊急程度等救災效益), 並沒有探討放多少traffic進來 頻寬充分使用:降QOS供更多人用 高品質通道for必須講清楚, 否則影響生命 如 HIV, 提供高品質通訊資源供緊急、重要話務清晰傳遞: 不用競爭資源

Outline Introduction Related work Contingency Cellular Network (CCN) Communication systems crash by natural disasters Requirements analysis of contingency communication system Related work Common contingency communication systems Contingency Cellular Network (CCN) Bandwidth allocation for CCN Concept Problem definition Model Algorithm design Evaluation Summary & future work Disaster task group & communications category

Bandwidth Allocation for CCN 最大化救災效益 Bandwidth allocation的考慮因素 反映災區環境 差異化QoS滿足不同等級使用者需求 網路拓樸的限制 例如連網時間,災情,人口數… Root可直達RNC，表示當地電信纜線並未中斷，通常市話亦可運作(因為是同一綑)，資源可多配給sub tree，對root而言,profit可能低(user自訂) 配合admission control 善用BW:如何善用BW: 與緊急程度有關, 智慧配BW 提升救災效益

Bandwidth Allocation for CCN–假設條件 所有鏈結頻寬 發自本地基地台的容許流量 Circuit Switching 較容易快速建置 較容易維持QoS 維運較容易 簡化Bandwidth Allocation為Channel Allocation問題 Topology與連外總頻寬固定，若變動，Reallocate 用右圖解說 分配結果是發自本地基地台的流量 BWA簡化成channel allocation問題 CCN Available Bandwidth固定 CCN Forwarding Tree的root連外 EC Module所建構的connectivity in CCN Forwarding Tree

Bandwidth Allocation for CCN– Problem Definition 救災效益 參考環境因素訂定，例如 涵蓋受災人口數 涵蓋註冊手機數 災害種類(如地震, 核災, 水災…) 災情程度(如降雨量、土石監測預警…) 緊急程度 生還率 效益遞減 由模型使用者定義 國家救災單位 涵蓋註冊手機數(無法確知受災人口時用以推算人口數)

Bandwidth Allocation for CCN– Problem Definition 限制條件 可用頻寬資源 連網台連外頻寬 鄰台間互連頻寬 Aggregate traffic不能超過upstream link capacity Local traffic Forwarding traffic 各基地台基本頻寬需求 各節點因應救災需要，必須保留供local traffic使用之最小channel數 避免channel配置過度集中 由模型使用者定義 v1 BSC/RNC v2 v3 v4 CCN forwarding tree v5 Basic needs:確保所有災區CCN基地台分配到最基本之頻寬資源

Model of Bandwidth Allocation for CCN– CCN forwarding tree Given CCN forwarding tree T(V,E), where , v1 is the root of T C={ci | i=1,2,3,…,n } is the set of uplink capacity of vi ci : the uplink capacity of vi ci ≤ cj , if vj is the parent node of vi c2 c4 c3 c5 c6 v1 BSC/RNC c7 v2 v3 v4 v5 v6 v7 c1 Local traffic:在該BS信號範圍,且被ME選擇為BS 子node的link capacity不大於父節點link capacity If tree只1層就是標準背包問題,背包裡有小背包, sort , top-down or button-up 有定義過的參數才能出現,定義的東西在冒號左邊,右邊放說明,所以沒出現過的符號一定要先在左邊出現過 圖論定義subtree cx(vi): channel class x assigned to Vi數量 40

Model of Bandwidth Allocation for CCN– CCN channel class B={bj | j=1,2,3,…,m } is the set of bandwidth required per channel class bj : the bandwidth required of channel class j Channel class Bandwidth/Channel (bj) 1 e.g.64K 2 e.g.32K 3 e.g.16K m e.g. ?K

Model of Bandwidth Allocation for CCN– CCN profit function for bandwidth allocation is the set of the profit of channel assigned fij : the profit of the first channel of class j assigned to vi g(k) : the profit attenuation function of the k-th same channel class assigned to the same node, for example, g(k)= , fij & g(k) are user designed

Model of Bandwidth Allocation for CCN– CCN channel assigned for basic needs is the set of the amount of basic channel needs dij : the basic needs of channel class j assigned to vi

Model of Bandwidth Allocation for CCN– CCN channel assigned is the set of the amount of channel assigned aij : the amount of channel class j assigned to vi 找到A使得max objective function

Model of Bandwidth Allocation for CCN– Objective function Our problem is to find aij A, such that is maximized subject to and is local bandwidth required of vi 各node受到 本地量+子tree forwaring不超過upstream capacity 限制, 頻寬分配結果aij幣旭大於基本頻寬需求dij

Problem Complexity—Knapsack Problem 0-1 Knapsack Problem：有N個物品和一個背包，其中: 物品具有重量W (w1, w2, …, wn) 和利潤P (p1, p2, …, pn) 背包的最大重量承受限制為C 如何取物可得最高價值? 0-1 Knapsack Problem is NP-Hard Richard M. Karp (1972). "Reducibility Among Combinatorial Problems“. In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103. Garey, M.; D. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. 1979. ISBN 0-7167-1045-5. A similar dynamic programming solution for the 0-1 knapsack problem also runs in pseudo-polynomial time.(碰到極大數字輸入時會沒效率) BWA的物品是n乘m, tree depth 3的full tree有15 node, 若有3種channel class, 就是有45種物品可選???  以整個tree看,物品選擇會很多種(n乘m) 未來頻寬夠大,可應用類型就會多,所以model已考量未來前瞻性需求,很可能KP的物品選擇會很多種, (會有極大數字輸入, 所以符合NPC)

Problem Complexity— Bandwidth Allocation for CCN Bandwidth Allocation for CCN (CCN-BA) 針對每個連網台(vi)，有m個channel class可選擇配置，和一個uplink頻寬限制，其中: 各種Channel class具有不同頻寬要求 (b1, b2, …, bm)和效益 (fi1, fi2, …, fim) 存在uplink頻寬最大承受限制 (ci) 如何配置channel可得最大效益? Nested 0-1 Knapsack Problem CCN forwarding tree c2 c4 c3 c5 c6 v1 BSC/RNC c7 v2 v3 v4 v5 v6 v7 c1 有限頻寬下,要放入哪些channel可獲得最大效益 BW of Channel class (b1, b2, …, bm) 連網台(vi) 效益 (fi1, fi2, …, fim)

Problem Complexity— Reduce CCN-BA to Knapsack Problem 可在多項式時間裡對應 0-1 Knapsack Problem CCN-BA C W P T(V,E) V = {v1}, E = Ø C’ = {C} B = W F = P D = {0} G = {1} c2 c4 c3 c5 c6 v1 v2 v3 v4 v5 v6 c1 要證明CCNBA是NP 加上限制條件作reduce Listen 1:04 record

Problem Complexity—NP-Hard Given an instance X:[C,W,P] in 0-1 knapsack problem, we can find an instance Y:[V,T,C’,B,F,D,G] in CCN-BA such that an optimal solution ay for Y is also an optimal solution for X. Let instance Y be a one level tree, where V=T={v1}, C’={C}, B=W, F=P, D={0}, and G={1}. Denote the total profit of a solution a for X and Y to be px(a) and py(a), respectively. Because F=P, we can easily prove px(a) and py(a) are equal. For simplicity, both px(a) and py(a) are denoted as p (a). First, we prove ay is a valid allocation for X. Since B=W, F=P, and C’={C}, any solution of Y whose total bandwidth must less than or equal to the given limit C so that ay must be a valid allocation for X. Since instance Y is a one level tree, for a similar argument, we can prove that any valid allocation ax for X is also a valid allocation for Y. Ref. scheduling v1.2 p.36 T=T’(vroot ,Ø), C’=C, B=W, F’=P, D’=0.就是我找到的instance 1. [ay] 最大值會出現在所有BW給root用時的配置組合,所以root可用BW配置組合只會比[ay]小,不會大(因為subtree會分掉一些), 所以[ay] is a valid allocation for X (valid 是指不會超出X的配置規則,即less than or equal to a given limit C) 2. CCN只有root可以完整對應KP 以上不大對!! Listen 10/31 record

Problem Complexity—NP-Hard Next, we prove that an optimal solution ay for Y is also an optimal solution for X by contradiction. As we have proved, ay is also a valid allocation for X, whose total profit is p(ay). Assume ay is not an optimal allocation for X, there must be another allocation ax, whose total profit p(ax) is greater than p(ay). And any valid ax is also a valid allocation for Y, whose total profit is p(ax), which is greater than p(ay). This contradicts to the assumption that ay is an optimal solution for Y. As a result, ay must be an optimal solution for X. The reduction of CCN-BA to 0-1 Knapsack Problem is done. The proof of NP-hardness of CCN-BA is straightforward. Q.E.D. Bandwidth Allocation for CCN is a nested 0-1 knapsack problem and NP-Hard 說明 Px, Py 是一樣function 加起來的, 即Px([a]) = Py([a]) Because C’=C, B=W, F’=P, total profit of X for [ax], which is px([ax]), is equal to total profit of Y for [ax], which is py([ax]).

Outline v1 v2 v3 v4 v5 v6 v7 Introduction Related work Communication systems crash by natural disasters Requirements analysis of contingency communication system Related work Common contingency communication systems Contingency Cellular Network (CCN) Bandwidth allocation for CCN Concept Problem definition Model Algorithm design Evaluation Summary & future work c2 c4 c3 c5 c6 v1 BSC/RNC c7 v2 v3 v4 v5 v6 v7 c1 Disaster task group & communications category

Heuristic Algorithm Design Bandwidth Allocation Greedy approach (BAG) Flow Diagram 更新profit及剩餘頻寬 給定CCN頻寬分配資訊 是否存在可分配頻寬之候選節點?5 計算各候選節點頻寬分配profit density 排序各候選節點頻寬分配profit density 選擇最佳profit density 是否合法分配? 頻寬分配 選擇次佳profit density 開始 結束 Y N profit density：F/bj

Heuristic Algorithm Design BAG algorithm pseudo code Greedy approach CCN-BA(T,C,B,F,D) Set A={} /* the amount of channel class j assigned to vi*/ Set V={} /*仍可配channel的candidate node*/ initial A = D initial V = VT initial C = C-(A · B) if any ci < minimum bj delete vi & descent(vi) from V end if K影響BW及profit值但不影響分配進行,把K視為profit獨立事件,比較簡單 Set p=0 /*total profit*/

Heuristic Algorithm Design BAG algorithm pseudo code Greedy approach (cont.) while V is not empty do sort F of V by profit density let fij ·g(k) be a highest profit density assign of F subject to min_ci(from vi to v1) ≥ bj plus 1 to aij minus bj from each ci(from vi to v1) update fij ·g(k+1) to F if any ci < minimum bj delete vi & descent(vi) from V end if end while Coding時應該要存C與F的各state, 容易debug let fij(x) be a highest profit density assign of F : def: profit density最大BW需求最小level上層優先i小的先 plus fij(x) to p

Bandwidth/channel (bj) CCN-BA BAG example Given CCN forwarding tree v1 BSC/RNC v2 v3 v4 v5 c1=58 c3=20 c2=30 c4=20 c5=20 Bandwidth requirement of channel class Channel class Bandwidth/channel (bj) 1 12K 2 7K 3 5K Attenuation Function g(k)= Initial profit (fij) Basic needs (dij) channel class vi 12k 7k 5k v1 16 13 5 v2 15 10 7 v3 25 20 v4 18 12 8 v5 29 23 channel class vi 12k 7k 5k v1 1 v2 v3 v4 v5 /*highest profit: max f(x) min BW req. upper level prefer smaller i prefer*/ The profit of HIGH quality channel is higher than the lower quality channel. Profit不應比較低品質的差,至少一樣

CCN-BA BAG example Initial v1 v2 v3 v4 v5 BSC/RNC c1=23 c3=23 c2=9 Allocation (aij) channel class vi 12k 7k 5k v1 1 v2 v3 v4 v5 Profit of channel assigned Channel Class Node 12k 7k 5k profit Profit density v1 16 1.33 9.19 1.31 5 1.00 v2 15 1.25 7.07 1.01 7 1.40 v3 25 2.08 14.14 2.02 10 2.00 v4 18 1.50 8.49 1.21 8 1.60 v5 29 2.42 16.26 2.32 3.00 /*highest profit: max f(x) min BW req. upper level prefer smaller i prefer*/ The profit of HIGH quality channel is higher than the lower quality channel. Profit不應比較低品質的差,至少一樣

CCN-BA BAG example Allocate [v5, 5k] v1 v2 v3 v4 v5 c2=4 c4=13 c3=23 BSC/RNC v2 v3 v4 v5 c1=18 Allocation (aij) channel class vi 12k 7k 5k v1 1 v2 v3 v4 v5 12k 7k 5k v5 1 Profit of channel assigned Channel Class Node 12k 7k 5k profit Profit density v1 16 1.33 9.19 1.31 5 1.00 v2 15 1.25 7.07 1.01 7 1.40 v3 25 2.08 14.14 2.02 10 2.00 v4 18 1.50 8.49 1.21 8 1.60 v5 29 2.42 16.26 2.32 3.00 /*highest profit: max f(x) min BW req. upper level prefer smaller i prefer*/ The profit of HIGH quality channel is higher than the lower quality channel. Profit不應比較低品質的差,至少一樣

CCN-BA BAG example Remove v2,v4,v5 from candidate node v1 v2 v3 v4 v5 BSC/RNC Allocation (aij) channel class vi 12k 7k 5k v1 1 v2 v3 v4 v5 c1=18 v1 c2=4 c3=23 v2 v3 c4=13 c5=8 v4 v5 Profit of channel assigned Channel Class Node 12k 7k 5k profit Profit density v1 16 1.33 9.19 1.31 5 1.00 v2 15 1.25 7.07 1.01 7 1.40 v3 25 2.08 14.14 2.02 10 2.00 v4 18 1.50 8.49 1.21 8 1.60 v5 29 2.42 16.26 2.32 10.61 2.12 /*highest profit: max f(x) min BW req. upper level prefer smaller i prefer*/ The profit of HIGH quality channel is higher than the lower quality channel. Profit不應比較低品質的差,至少一樣

CCN-BA BAG example Allocate [v3, 12k] v1 v2 v3 v4 v5 BSC/RNC v2 v3 v4 v5 c1=6 Allocation (aij) channel class vi 12k 7k 5k v1 1 v2 v3 v4 v5 12k 7k 5k v3 1 Profit of channel assigned Channel Class Node 12k 7k 5k profit Profit density v1 16 1.33 9.19 1.31 5 1.00 v2 15 1.25 7.07 1.01 7 1.40 v3 25 2.08 14.14 2.02 10 2.00 v4 18 1.50 8.49 1.21 8 1.60 v5 29 2.42 16.26 2.32 10.61 2.12 /*highest profit: max f(x) min BW req. upper level prefer smaller i prefer*/ The profit of HIGH quality channel is higher than the lower quality channel. Profit不應比較低品質的差,至少一樣

CCN-BA BAG example Allocate [v3, 5k] v1 v2 v3 v4 v5 BSC/RNC v2 v3 v4 v5 c1=1 Allocation (aij) channel class vi 12k 7k 5k v1 1 v2 v3 v4 v5 12k 7k 5k v3 1 Profit of channel assigned Channel Class Node 12k 7k 5k profit Profit density v1 16 1.33 9.19 1.31 5 1.00 v2 15 1.25 7.07 1.01 7 1.40 v3 17.68 1.47 14.14 2.02 10 2.00 v4 18 1.50 8.49 1.21 8 1.60 v5 29 2.42 16.26 2.32 10.61 2.12 /*highest profit: max f(x) min BW req. upper level prefer smaller i prefer*/ The profit of HIGH quality channel is higher than the lower quality channel. Profit不應比較低品質的差,至少一樣

CCN-BA BAG example Remove v1,v3 from candidate node v1 v2 v4 v5 v3 BSC/RNC v2 v4 v5 c1=1 v3 Remove v1,v3 from candidate node Allocation (aij) channel class vi 12k 7k 5k v1 1 v2 v3 v4 v5 Profit of channel assigned Channel Class Node 12k 7k 5k profit Profit density v1 16 1.33 9.19 1.31 5 1.00 v2 15 1.25 7.07 1.01 7 1.40 v3 17.68 1.47 14.14 2.02 1.41 v4 18 1.50 8.49 1.21 8 1.60 v5 29 2.42 16.26 2.32 10.61 2.12 /*highest profit: max f(x) min BW req. upper level prefer smaller i prefer*/ The profit of HIGH quality channel is higher than the lower quality channel. Profit不應比較低品質的差,至少一樣

CCN-BA BAG example No more candidate node  Finished v1 v2 v4 v5 v3 BSC/RNC v2 v4 v5 c1=1 v3 Allocation (aij) channel class vi 12k 7k 5k v1 1 v2 v3 v4 v5 Total profit = basic needs profit + channel assigned by profit density =(13+10+20+12+23 )+15+25+10 =128

Outline Introduction Related work Contingency Cellular Network (CCN) Communication systems crash by natural disasters Requirements analysis of contingency communication system Related work Common contingency communication systems Contingency Cellular Network (CCN) Bandwidth allocation for CCN Concept Problem definition Model Algorithm design Evaluation Summary & future work Disaster task group & communications category

實驗設計 實驗目的：評估BAG演算法的效能 使用電腦隨機產生大量模擬案例，憑以計算BAG演算法在不同環境條件下之效能 實驗一 實驗二 實驗三 效益遞減函數 實驗二 實驗三 大 規模實驗 實驗基地台個數：6、7、8、9、10、100 各進行10個獨立測試

BAG演算法程式模組控制 channel allocation matrix [dij] for basic needs PathMinimumCapacityFind( ) CandidateAllocationCheck( ) any more candidate allocation? BubbleSort( ) ChannelAllocation( ) Y N Read Files LinkCapacityUpdate( ) channel allocation matrix [dij] for basic needs the remaining uplink capacity (ci) per node (vi) minimum capacity from per node to root (minimum ci from vi to v1) candidate channel class can be allocated per node candidate allocation sorted by profit density ProfitAttenuationUpdate( ) channel allocation (aij) profit matrix [fij ]．g(k) profit density matrix [fij ]．g(k) / bj BAG Solution

評估指標 實驗案例是由亂數隨機產生，每次實驗皆獨立不相關，計算效能必須經過正規化(Normalization) 稱為誤差(Deviations from optimum solution，簡稱Deviation) 6~10個基地台 誤差 = (最佳解-演算法解) / (最佳解-最差解) 最佳解：所有合法解計算出來之最大Total Profit 最差解：所有合法解計算出來之最小Total Profit 演算法解：BAG演算法解之Total Profit 100個基地台 準誤差 = (演算法解-準最佳解) / ( max(準最佳解,演算法解) -準最差解) 準最佳解：10萬個解計算出來之最大Total Profit 準最差解：10萬個解計算出來之最小Total Profit

實驗參數與環境 Link Capacity(ci)：32~100 Initial Profit(fij)：30~100 Attenuation Function(g(k))： 、 Channel Class(bj)：16~32 Forwarding Tree Size：6、7、8、9、10、100 實驗電腦規格： 處理器：Intel(R) Core(TM)2 Duo CPU E7400 @ 2.80GHz 雙核 記憶體：2.00 GB 系統類型：32位元Microsoft Windows XP SP3 、

實驗結果 實驗一 50個測試案例 隨著基地台數量增加 整體誤差(Deviation)範圍：0~10.68% 最佳解28個 平均誤差由2.50%緩增至4.46% 平均效能由98.21%略降至96.71%

實驗結果 6 nodes 7 nodes 8 nodes 9 nodes 10 nodes

實驗結果 實驗二 50個測試案例 隨著基地台數量增加 整體誤差(Deviation)範圍：0~14.03% 最佳解19個 平均誤差2.16%~4.76% 平均效能由97.58%略降至96.32%

實驗結果 6 nodes 7 nodes 8 nodes 9 nodes 10 nodes

實驗結果 實驗三 10個測試案例 BAG演算法解均超過準最佳解 整體準誤差範圍在21.12% ~41.30%，平均準誤差32.71%

Total Number of Optimum Solution 實驗總結 Amount of base station Experiment 1 Experiment 2 Average Deviation 6 2.50% 3.14% 2.82% 7 2.58% 3.87% 3.22% 8 2.95% 2.16% 2.55% 9 3.55% 4.18% 10 4.46% 4.76% 4.61% 3.21% 3.62% 3.41% BAG演算法平均誤差 實驗一，演算法平均誤差為3.21% 實驗二，演算法平均誤差為3.62% 基地台數量增加的影響 BAG演算法與最佳解誤差會逐步上升，平均誤差由6個基地台的2.82%提升至10個基地台的4.61% 獲得最佳解(零誤差)之機會下降，當8個基地台時，實驗一、二合計獲12個得最佳解，當10個基地台時，合計獲得7個最佳解 BAG採取貪婪策略，隨基地台數量的增加，可行解之數量亦將隨之增加，因此誤差相對提升 Amount of base station Experiment 1 Experiment 2 Total Number of Optimum Solution 6 3 9 7 4 11 8 12 5 10 28 19 47

Outline Introduction Related work Contingency Cellular Network (CCN) Communication systems crash by natural disasters Requirements analysis of contingency communication system Related work Common contingency communication systems Contingency Cellular Network (CCN) Bandwidth allocation for CCN Concept Problem definition Model Algorithm design Evaluation Summary & future work Disaster task group & communications category

Summary 大型天然災害發生時通訊系統常會癱瘓，利用無線電將功能完整但無法對外進行正常連線的基地台連接起來，建構一個臨時性的行動通訊網路，稱為應急蜂巢式行動通訊網路(Contingency Cellular Network，CCN) 災區通訊存在重要性的差異，將CCN話務分級、通訊品質分級，可在確保重要話務高品質通訊之餘，創造更大服務量，提升救災效益 災區各地之受災情況不同，CCN頻寬使用的救災效益，將隨環境因素及分配頻寬數量而變化 我們提出一個反映各基地台災情緊急程度以及通訊需求差異，且適合於CCN樹狀結構的最佳化頻寬分配模型，以追求救災效益的最大化，供使用者(救災指揮單位)系統化的解決CCN頻寬分配問題 最後提出啟發式演算法，以快速得到一個相近於最佳救災效益的頻寬分配組合

Future Work CCN各鄰台間剩餘的頻寬運用 以節點為單位，作為頻寬分配效益遞減範圍 網路拓樸變化對演算法效能及誤差之影響與改良 非單一路由選擇之頻寬分配 Priority-based允入控制 配合允入控制的調適

Q & A 77