學術產出-Theses
Article View/Open
Publication Export
-
題名 應急蜂巢式行動網路的拓撲設計
Topology design for contingency cellular network作者 黃玉潔
Huang, Yu Chieh貢獻者 連耀南
Lien, Yao Nan
黃玉潔
Huang, Yu Chieh關鍵詞 應急蜂巢式行動網路
大型自然災害
Contingency Cellular Network
large-scale disaster
K-Minimum Cost Spanning Tree日期 2010 上傳時間 30-Oct-2012 10:44:41 (UTC+8) 摘要 大型災害頻傳傷亡慘重，若能把握於救災黃金72小時內救出受困民眾，則可望挽回更多寶貴的生命，但災區通訊網路基礎設施常因災害而遭受嚴重損毀，無法正常運作。救災工作在缺乏通訊系統的支援下，因溝通協調的困難而紊亂無章、效率低落。本研究提出一個可快速恢復特定區域通訊服務的網路，並為其設計通訊的拓撲結構。我們稱該網路為應急蜂巢式行動通訊網路(Contingency Cellular Network)，簡稱CCN網路。CCN網路利用無線電連接災區行動電話網路中斷訊但結構未損的基地台建構而成，具有建置速度快、使用門檻低等多項特點，可支援災區救援的緊急通訊。本研究中，我們以各毀損基地台通訊範圍內的通訊需求人數與災區毀損程度，作為效益參數，嘗詴在蜂巢式網路的格網架構以及數量有限的緊急通訊設備下，選擇效益較高的位置點配置緊急通訊設備，建立應急蜂巢式行動網路的網路拓撲，此拓撲除追求最大救災效益外，並顧及通訊品質，避免建立負載失衡的連線。我們將問題塑模為一類似圖論中的K-Minimum Cost Spanning Tree (K-Cardinality Tree or KCT)問題，稱為Depth Bounded K-Maximum Profit Spanning Tree問題，並提供數個快速的啟發式演算法，可在緊急時快速地建立應急蜂巢式行動網路拓撲。
When a catastrophic natural disaster occurs, the efficiency of disaster response operation is critical to life saving. However, communication systems, such as cellular networks, usually crashed due to various causes that make coordination difficult for many disorganized disaster response workers extremely. 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 propose a Contingency Cellular Network (CCN) by connecting disconnected base stations together with wireless links and portable power generators. CCN can support existing mobile phone users with limited capability. Such a system can support a large number of voluntary workers in the early hours of a catastrophic natural disaster, thus saving many lives.Communication traffics, either voice or data, are forwarded hop-by-hop to the external network that remains operational. The efficiency and effeteness of CCN is obviously depends on the topology of such a forwarding network. This thesis addresses the design of forwarding topology aiming to maximize its efficiency. We take the degree of emergency degree of the damage, population of each stricken as the priority measure as well as the amount of emergency recovery resources as the constraint to determine the topology. We model the CCN topology design problem into a Depth Bounded K-Maximum Spanning Tree Problem. The problem is proven NP-hard and we designed an efficient heuristic algorithm (DBTB) to solve it. We also model CCN topology design problem into a Hop Concerned K-Maximum SpanningiiiTree Program and designed a HCTB algorithm to solve it. The simulation results show that DBTB algorithm can control tree depth effectively but HCTB can gain more profit.參考文獻 [1] Association of Public-Safety Communications Officials International, Project 25, http://www.apcointl.org/frequency/project25.php, retrieved May 2010.[2] Alfayez Adel, Assiri Majid, Clerk Rutvij, and Alsaadan Usamah, “Evaluating the Viability of TETRA for US Public Safety Communication,” University of Colorado at Boulder Interdisciplinary Telecommunications Program Capstone Project, Boulder, USA, Nov. 2009.[3] Christian Blum, Maria J. Blesa, “New metaheuristic approaches for the edge-weighted k-cardinality tree problem,” Computers and Operations Research, vol. 32, no. 6, June 2005, pp. 1355-1377.[4] Chandra Chekuri, Sudipto Guha, “The Steiner k-Cut Problem,” SIAM Journal on Discrete Mathematics, vol. 20, issue 1, 2006.[5] Chandra Chekuri, Sudipto Guha and Joseph Seffi Naor, “Approximating Steiner k-Cuts,” Lecture Notes in Computer Science, vol. 2719, 2003.[6] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms, Third Edition. Cambridge, Mass.: The MIT Press, 2009.[7] Raheleh Dilmaghani, and Ramesh Rao, “A Systematic Approach to Improve Communication for Emergency Response,” Proc. of 42nd Hawaii Int`l Conference on System Sciences, Waikoloa, Big Island, Hawaii, Jan. 2009.[8] Ulrich Faigle and Walter Kern, “Computational Complexity of Some Maximum Average Weight Problems with Precedence Constraints,” Operations Research, vol. 42, no. 4, Jul. - Aug., 1994, pp. 688-693.[9] Matteo Fischetti, Horst W. Hamacher, Kurt Jørnsten, Francesco Maffioli, “Weighted k-cardinality trees: complexity and polyhedral structure,” Networks, vol. 24, issue 1, 1994, pp. 11–21.[10] Anupam Guptaa, Viswanath Nagarajanb, R. Ravi, “An improved approximation algorithm for requirement cut,” Operations Research Letters, vol. 38, issue 4, July 2010, pp. 322–325.[11] Harri Holma and Antti Toskala, WCDMA for UMTS : radio access for third generation mobile communications, Third Edition. Chichester, England: Wiley, 2004.[12] ITR-RESCUE, “Robust Networking and In-formation Collection Project,” http://www.itr-rescue.org/research/networking.php, retrieved Feb. 2010.[13] Richard E. Krock, “Lack of Emergency Recovery Palnning Is a Disaster Waiting to Happen,” IEEE Communications Magazine, Jan. 2011.[14] Yao-Nan Lien, Li-Cheng Chi and Yuh-Sheng Shaw, “A Walkie-Talkie-Like Emergency Communication System for Catastrophic Natural Disasters”, Proc. of ISPAN09, Dec., 2009.[15] Yao-Nan Lien, Hung-Chin Jang, and Tzu-Chieh Tsai, “A MANET Based Emergency Communication and Information System for Catastrophic Natural Disasters,” Proc. of IEEE Workshop on Specialized Ad Hoc Networks and Systems, Montreal, Canada, June 26, 2009.[16] Overview of The Universal Mobile Telecommunication System, http://www.umtsworld.com/technology/overview.htm, retrieved Aug. 2011.[17] Cristina Ribeiro, and Alexander Ferworn, “Computational Public Safety in Emergency Management Communications,” ACM International Wireless Communications and Mobile Computing Conference 6th, New York, USA, Oct. 2010.[18] Huzur Saran and Vijay V. Vazirani, “Finding k Cuts within Twice the Optimal,” SIAM Journal on Computing, vol. 24, issue 1, 1995, pp. 101-108.[19] Stephan Seufert, Srikanta Bedathur, Julian Mestre, Gerhard Weikum, “Bonsai: Growing Interesting Small Trees,” 2010 IEEE International Conference on Data Mining, 2010, pp.1013-1018.[20] Steven S. Skiena. The algorithm design manual. London: Springer-Verlag London, 2008.[21] 日本地震氣象廳, http://www.jma.go.jp/jma/press/1103/11c/201103111620.html, retrieved Aug. 2011.[22] 日本警察廳, http://www.npa.go.jp/archive/keibi/biki/higaijokyo.pdf, retrieved Aug. 2011.[23] 孫玉, “應急通信技術總體框架討論,” 人民郵電出版社, ISBN：7115208328, 2009.[24] 連耀南, 黃智賢, “大型自然災害下規模救災緊急通訊系統方案,” National Symposium on Telecommunications(NST) 2010, Dec. 3-4, 2010.[25] 楊永年, “八八水災救災體系之研究,” 公共行政學報, vol. 32, pp.143-169. 描述 碩士
國立政治大學
資訊科學學系
97753005
99資料來源 http://thesis.lib.nccu.edu.tw/record/#G0097753005 資料類型 thesis dc.contributor.advisor 連耀南 zh_TW dc.contributor.advisor Lien, Yao Nan en_US dc.contributor.author (Authors) 黃玉潔 zh_TW dc.contributor.author (Authors) Huang, Yu Chieh en_US dc.creator (作者) 黃玉潔 zh_TW dc.creator (作者) Huang, Yu Chieh en_US dc.date (日期) 2010 en_US dc.date.accessioned 30-Oct-2012 10:44:41 (UTC+8) - dc.date.available 30-Oct-2012 10:44:41 (UTC+8) - dc.date.issued (上傳時間) 30-Oct-2012 10:44:41 (UTC+8) - dc.identifier (Other Identifiers) G0097753005 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/54333 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學學系 zh_TW dc.description (描述) 97753005 zh_TW dc.description (描述) 99 zh_TW dc.description.abstract (摘要) 大型災害頻傳傷亡慘重，若能把握於救災黃金72小時內救出受困民眾，則可望挽回更多寶貴的生命，但災區通訊網路基礎設施常因災害而遭受嚴重損毀，無法正常運作。救災工作在缺乏通訊系統的支援下，因溝通協調的困難而紊亂無章、效率低落。本研究提出一個可快速恢復特定區域通訊服務的網路，並為其設計通訊的拓撲結構。我們稱該網路為應急蜂巢式行動通訊網路(Contingency Cellular Network)，簡稱CCN網路。CCN網路利用無線電連接災區行動電話網路中斷訊但結構未損的基地台建構而成，具有建置速度快、使用門檻低等多項特點，可支援災區救援的緊急通訊。本研究中，我們以各毀損基地台通訊範圍內的通訊需求人數與災區毀損程度，作為效益參數，嘗詴在蜂巢式網路的格網架構以及數量有限的緊急通訊設備下，選擇效益較高的位置點配置緊急通訊設備，建立應急蜂巢式行動網路的網路拓撲，此拓撲除追求最大救災效益外，並顧及通訊品質，避免建立負載失衡的連線。我們將問題塑模為一類似圖論中的K-Minimum Cost Spanning Tree (K-Cardinality Tree or KCT)問題，稱為Depth Bounded K-Maximum Profit Spanning Tree問題，並提供數個快速的啟發式演算法，可在緊急時快速地建立應急蜂巢式行動網路拓撲。 zh_TW dc.description.abstract (摘要) When a catastrophic natural disaster occurs, the efficiency of disaster response operation is critical to life saving. However, communication systems, such as cellular networks, usually crashed due to various causes that make coordination difficult for many disorganized disaster response workers extremely. 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 propose a Contingency Cellular Network (CCN) by connecting disconnected base stations together with wireless links and portable power generators. CCN can support existing mobile phone users with limited capability. Such a system can support a large number of voluntary workers in the early hours of a catastrophic natural disaster, thus saving many lives.Communication traffics, either voice or data, are forwarded hop-by-hop to the external network that remains operational. The efficiency and effeteness of CCN is obviously depends on the topology of such a forwarding network. This thesis addresses the design of forwarding topology aiming to maximize its efficiency. We take the degree of emergency degree of the damage, population of each stricken as the priority measure as well as the amount of emergency recovery resources as the constraint to determine the topology. We model the CCN topology design problem into a Depth Bounded K-Maximum Spanning Tree Problem. The problem is proven NP-hard and we designed an efficient heuristic algorithm (DBTB) to solve it. We also model CCN topology design problem into a Hop Concerned K-Maximum SpanningiiiTree Program and designed a HCTB algorithm to solve it. The simulation results show that DBTB algorithm can control tree depth effectively but HCTB can gain more profit. en_US dc.description.tableofcontents 第一章 緒論 11.1 簡介 11.2 大型天然災害的影響 21.3 大型天然災害對通訊的衝擊 31.4 大型災害的救災時效 61.5 通訊設備修復困難 7第二章 相關研究 82.1 第三代行動通訊系統架構 82.1.1 UTRAN 82.1.2 CN 92.2 應急通訊的設計需求 102.3 常見應急通訊介紹與比較 112.3.1 無線對講機 122.3.2 業餘無線電 122.3.3 移動基地台 (Cell on Wheels) 132.3.4 中繼式無線電系統 142.3.5 MANET 152.3.6 應急通訊系統比較 162.4 展開樹演算法 172.4.1 最小成本展開樹 172.4.2 最大成本展開樹 172.4.3 K-Minimum Cost Spanning Tree 182.4.4 K-Maximum Cost Spanning Tree 182.4.5 Steiner K-Cut Problem 18第三章 應急蜂巢式行動網路(CCN) 193.1 系統簡介 193.2 系統架構 203.3 系統使用時機 243.4 系統元件 243.5 研究議題 273.5.1 網路拓撲規劃 273.5.2 建構排程設計 283.5.3 網路頻寬分配 293.5.4 Priority-based允入控制 293.5.5 Intranet建構 293.5.6 自動化建構 303.5.7 基地台介面整合 303.6 重要實作議題探討 31第四章 應急蜂巢式行動網路的拓撲規劃 334.1 CCN網路拓撲規劃的重要性 334.2 無線通訊模組鏈結數對拓撲規劃的影響 334.2.1 2-link無線模組 334.2.2 3-link無線模組 344.3 CCN網路拓撲的建構 354.4 效益參數 374.5 多連網台的網路拓撲規劃 374.6 CCN Forwarding Tree 374.6.1 ERP數量之限制 414.6.2 Relay-hop數量對拓撲的影響 414.7 最佳化問題模型 434.7.1 限深模型(DB K-MaxST) 434.7.1.1 NP-Completeness 444.7.2 折減模型(HC K-MaxST) 464.8 演算法設計 464.8.1 Depth Bounded Tree Building (DBTB) Algorithm 474.8.2 Hop Concern Tree Building (HCTB) Algorithm 49第五章 效能評估 525.1 實驗目的 525.2 實驗環境 525.3 實驗ㄧ: 小規模實驗 525.4 實驗二: 大規模實驗 575.5 實驗結論 63第六章 結論與未來工作 64參考文獻 65 zh_TW dc.language.iso en_US - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0097753005 en_US dc.subject (關鍵詞) 應急蜂巢式行動網路 zh_TW dc.subject (關鍵詞) 大型自然災害 zh_TW dc.subject (關鍵詞) Contingency Cellular Network en_US dc.subject (關鍵詞) large-scale disaster en_US dc.subject (關鍵詞) K-Minimum Cost Spanning Tree en_US dc.title (題名) 應急蜂巢式行動網路的拓撲設計 zh_TW dc.title (題名) Topology design for contingency cellular network en_US dc.type (資料類型) thesis en dc.relation.reference (參考文獻) [1] Association of Public-Safety Communications Officials International, Project 25, http://www.apcointl.org/frequency/project25.php, retrieved May 2010.[2] Alfayez Adel, Assiri Majid, Clerk Rutvij, and Alsaadan Usamah, “Evaluating the Viability of TETRA for US Public Safety Communication,” University of Colorado at Boulder Interdisciplinary Telecommunications Program Capstone Project, Boulder, USA, Nov. 2009.[3] Christian Blum, Maria J. Blesa, “New metaheuristic approaches for the edge-weighted k-cardinality tree problem,” Computers and Operations Research, vol. 32, no. 6, June 2005, pp. 1355-1377.[4] Chandra Chekuri, Sudipto Guha, “The Steiner k-Cut Problem,” SIAM Journal on Discrete Mathematics, vol. 20, issue 1, 2006.[5] Chandra Chekuri, Sudipto Guha and Joseph Seffi Naor, “Approximating Steiner k-Cuts,” Lecture Notes in Computer Science, vol. 2719, 2003.[6] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms, Third Edition. Cambridge, Mass.: The MIT Press, 2009.[7] Raheleh Dilmaghani, and Ramesh Rao, “A Systematic Approach to Improve Communication for Emergency Response,” Proc. of 42nd Hawaii Int`l Conference on System Sciences, Waikoloa, Big Island, Hawaii, Jan. 2009.[8] Ulrich Faigle and Walter Kern, “Computational Complexity of Some Maximum Average Weight Problems with Precedence Constraints,” Operations Research, vol. 42, no. 4, Jul. - Aug., 1994, pp. 688-693.[9] Matteo Fischetti, Horst W. Hamacher, Kurt Jørnsten, Francesco Maffioli, “Weighted k-cardinality trees: complexity and polyhedral structure,” Networks, vol. 24, issue 1, 1994, pp. 11–21.[10] Anupam Guptaa, Viswanath Nagarajanb, R. Ravi, “An improved approximation algorithm for requirement cut,” Operations Research Letters, vol. 38, issue 4, July 2010, pp. 322–325.[11] Harri Holma and Antti Toskala, WCDMA for UMTS : radio access for third generation mobile communications, Third Edition. Chichester, England: Wiley, 2004.[12] ITR-RESCUE, “Robust Networking and In-formation Collection Project,” http://www.itr-rescue.org/research/networking.php, retrieved Feb. 2010.[13] Richard E. Krock, “Lack of Emergency Recovery Palnning Is a Disaster Waiting to Happen,” IEEE Communications Magazine, Jan. 2011.[14] Yao-Nan Lien, Li-Cheng Chi and Yuh-Sheng Shaw, “A Walkie-Talkie-Like Emergency Communication System for Catastrophic Natural Disasters”, Proc. of ISPAN09, Dec., 2009.[15] Yao-Nan Lien, Hung-Chin Jang, and Tzu-Chieh Tsai, “A MANET Based Emergency Communication and Information System for Catastrophic Natural Disasters,” Proc. of IEEE Workshop on Specialized Ad Hoc Networks and Systems, Montreal, Canada, June 26, 2009.[16] Overview of The Universal Mobile Telecommunication System, http://www.umtsworld.com/technology/overview.htm, retrieved Aug. 2011.[17] Cristina Ribeiro, and Alexander Ferworn, “Computational Public Safety in Emergency Management Communications,” ACM International Wireless Communications and Mobile Computing Conference 6th, New York, USA, Oct. 2010.[18] Huzur Saran and Vijay V. Vazirani, “Finding k Cuts within Twice the Optimal,” SIAM Journal on Computing, vol. 24, issue 1, 1995, pp. 101-108.[19] Stephan Seufert, Srikanta Bedathur, Julian Mestre, Gerhard Weikum, “Bonsai: Growing Interesting Small Trees,” 2010 IEEE International Conference on Data Mining, 2010, pp.1013-1018.[20] Steven S. Skiena. The algorithm design manual. London: Springer-Verlag London, 2008.[21] 日本地震氣象廳, http://www.jma.go.jp/jma/press/1103/11c/201103111620.html, retrieved Aug. 2011.[22] 日本警察廳, http://www.npa.go.jp/archive/keibi/biki/higaijokyo.pdf, retrieved Aug. 2011.[23] 孫玉, “應急通信技術總體框架討論,” 人民郵電出版社, ISBN：7115208328, 2009.[24] 連耀南, 黃智賢, “大型自然災害下規模救災緊急通訊系統方案,” National Symposium on Telecommunications(NST) 2010, Dec. 3-4, 2010.[25] 楊永年, “八八水災救災體系之研究,” 公共行政學報, vol. 32, pp.143-169. zh_TW
