Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/54333
|
| Title: | 應急蜂巢式行動網路的拓撲設計
Topology design for contingency cellular network |
| Authors: | 黃玉潔
Huang, Yu Chieh |
| Contributors: | 連耀南
Lien, Yao Nan
黃玉潔
Huang, Yu Chieh |
| Keywords: | 應急蜂巢式行動網路
大型自然災害
Contingency Cellular Network
large-scale disaster
K-Minimum Cost Spanning Tree |
| Date: | 2010 |
| Issue Date: | 2012-10-30 10:44:41 (UTC+8) |
| Abstract: | 大型災害頻傳傷亡慘重，若能把握於救災黃金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 Spanning
iii
Tree 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. |
| 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. |
| Description: | 碩士
國立政治大學
資訊科學學系
97753005
99 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0097753005 |
| Data Type: | thesis |
| Appears in Collections: | [資訊科學系] 學位論文
|
Files in This Item:
| File |
Size | Format | |
|---|
| 300501.pdf | 2962Kb | Adobe PDF2 | 678 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
