政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/57582

政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/57582

English | 正體中文 | 简体中文 | Post-Print筆數 : 27 | Items with full text/Total items : 113648/144635 (79%)
Visitors : 51599802 Online Users : 952

RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.

Scope

please add "double quotation mark" for query phrases to get precise results

please goto advance search for comprehansive author search

Adv. Search

Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer

Goto mobile version

政大典藏 > College of Informatics > Department of Computer Science > Theses > Item 140.119/57582

Please use this identifier to cite or link to this item: https://nccur.lib.nccu.edu.tw/handle/140.119/57582

Title:	應急蜂巢式行動通訊網路的跨網路拓樸設計 Cross Network Topology Design for Contingency Cellular Network
Authors:	黃冠傑 Huang, Kuan Chieh
Contributors:	連耀南 Lien, Yao Nan 黃冠傑 Huang, Kuan Chieh
Keywords:	大型自然災害應急通訊應急蜂巢式行動通訊網路網路拓樸最小生成樹問題 Large-scale disaster Emergency communication Contingency cellular network Network topology K-Minimum Spanning Tree problem
Date:	2012
Issue Date:	2013-04-01 14:39:08 (UTC+8)
Abstract:	當大型災害發生時，往往造成傷亡慘重，若能把握於救災黃金72小時內救出受困民眾，則可望挽回更多寶貴的生命，但災區的通訊網路基礎設施時常因災害而遭受嚴重的損毀，無法正常運作。救災工作在缺乏通訊系統的支援下，因溝通協調的困難，大大提高救援的困難度。我們分析歸納應急通訊系統的七大技術需求，提出一個可快速恢復特定區域通訊服務的網路，並為其設計通訊的拓樸結構。我們稱該網路為應急蜂巢式行動通訊網路(Contingency Cellular Network)，簡稱CCN網路。CCN網路利用倖存的連通基地台和斷訊卻沒有損毀的基地台，以無線電連接起來建構一個臨時性的通訊系統，具有建置速度快、使用門檻低等多項特點，災區內擁有行動電話的使用者，可利用本網路作為救災通訊之用。本研究中，我們以各基地台通訊範圍內的通訊需求人數與災區毀損程度，作為效益參數，在數量有限的應急通訊設備下，連接不同電信業者倖存的基地台，建立應急蜂巢式行動網路的跨網路拓樸，此拓樸除追求最大救災效益外，並顧及通訊品質，避免建立負載失衡的連線。我們將問題塑模為一類似圖論中的K-Maximum Spanning Tree問題，稱為Depth Bounded Mutually Exclusive K-Maximum Profit Spanning Tree問題，並且提供數個快速的啟發式演算法，可在緊急時快速地建立應急蜂巢式行動網路的跨網路拓樸。 When stricken by a large-scale disaster, the efficiency of disaster response operation is very critical to life saving. However, communication systems, such as cellular networks, usually crashed due to various causes that make coordination extremely difficult for many disorganized disaster response workers. 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 analyze 7-ability for emergency communication systems and propose a Contingency Cellular Network (CCN) by connecting disconnected base stations together with wireless links and contingency recovery packages. 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 save many lives. This thesis addresses the design of forwarding topology using multiple operator’s base stations aiming to maximize the efficiency of disaster response. 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 Cross Network Topology Design problem into a K-Maximum Spanning Tree Problem aiming to maximize disaster operation efficiency. The problem is proven to be NP Hard. We also design some efficient heuristic algorithms to solve the problem when it is needed in urgent. 第一章、簡介 1 1.1、災區應急通訊系統需求分析 3 1.1.1、大型天然災害發生時救災行動面臨的挑戰 3 1.1.2、固網與行動通訊系統癱瘓原因 5 1.1.3、通訊設備修復困難 7 1.1.4、大型災害的救災時效 7 1.1.5、應急通訊網建置之挑戰與需求 8 1.1.6、應急通訊網效能指標 12 1.2、應急通訊網路簡介 13 1.3、論文架構 14 第二章、相關研究 15 2.1、第三代行動通訊架構 15 2.1.1、通用行動通訊系統陸地無線接入網 (UTRAN) 16 2.1.2、核心網路 (Core Network) 16 2.1.3、 3G 網路通訊協定 17 2.2、應急通訊系統種類 18 2.2.1、專用高抗災通信平臺 19 2.2.2、無線對講機 (Walkie-Talkie) 19 2.2.3、業餘無線電 (Amateur radio) 20 2.2.4、行動衛星通訊 (Satellite mobile phone) 21 2.2.5、專業用集群通訊系統 (Trunking radio) 22 2.2.6、移動基地台 (Cell on wheels) 23 2.2.7、行動隨意式網路 (MANET) 24 2.2.8、過去應急通訊系統相關研究 25 2.2.9、應急通訊系統綜合比較 28 2.3、相關演算法 30 2.3.1、精確解法 (Exact Algorithm) 30 2.3.2、後啟發式演算法 (Meta-heuristics) 32 2.3.3、評論 35 2.4、生成樹演算法 36 2.4.1、最小生成樹Minimum Spanning Tree (MST) 36 2.4.2、最大生成樹Maximum Spanning Tree (MaxST) 36 2.4.3、 K-Minimum Spanning Tree (K-MST) 36 2.4.4、 K-Maximum Spanning Tree (K-MaxST) 37 第三章、應急蜂巢式行動通訊網路 (CCN) 38 3.1、系統架構 40 3.1.1、 CCN連網方式 41 3.1.2、系統元件 42 3.2、通訊模式 45 3.2.1、災區通訊型態分類 45 3.2.2、 CCN通訊模式 46 3.3、 CCN功能架構(Functional Architecture) 49 3.4、 CCN服務流程 52 3.5、建置與運轉流程 55 3.6、重要研究議題與未來研究方向 56 第四章、應急蜂巢式行動通訊網路的跨網路拓樸設計 60 4.1、設計理念與目標 60 4.2、 CCN網路拓樸的建構 61 4.3、多連網台網路拓樸規劃 63 4.4、問題定義 63 4.4.1、救災效益定義 64 4.4.2、問題描述 64 4.5、最佳化問題模型 65 4.5.1、限制深度互斥模型(DBME K-MaxST) 65 4.5.2、自律深度互斥模型(DCME K-MaxST) 66 4.5.3、自律深度模型(DC K-MaxST) 67 4.6、演算法設計 69 4.6.1、 CCN Topology Design – Depth Bounded Mutually Exclusive 69 4.6.2、 CCN Topology Design – Depth Controlled Mutually Exclusive 74 4.6.3、 CCN Topology Design – Depth Controlled 78 第五章、效能評估 80 5.1、實驗目的 80 5.2、實驗環境 80 5.3、實驗說明 81 5.4、實驗ㄧ：小規模實驗 81 5.4.1、評估指標 81 5.4.2、實驗參數設定 81 5.4.3、實驗結果 82 5.5、實驗二：大規模實驗 91 5.5.1、評估指標 91 5.5.2、實驗參數設定 92 5.5.3、實驗結果 92 5.6、實驗總結 100 第六章、結論與未來展望方向 101 參考文獻 103 附錄 108
Reference:	[1] 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. [2] Association of Public-Safety Communications Officials International, Project 25, http://www.apcointl.org/frequency/project25.php, retrieved May. 2010. [3] Yong Bai, Wencai Du, Zhengxin Ma, Chong Shen, Youling Zhou and Baodan Chen, "Emergency communication system by heterogeneous wireless networking," 2011 International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM) , June. 2010. [4] Melanie Basich, "Wireless When You Need It," http://www.policemag.com/ Channel/Technology/Articles/Print/Story/2009/01/Wireless-When-You-Need-It.aspx, retrieved Jan. 2009. [5] Jean-Charles Bazin, and Hongdong Li, and In So Kweon, and C´edric Demonceaux, and Pascal Vasseur, and Katsushi Ikeuchi, "A Branch and Bound Approach to Correspondence and Grouping Problems," IEEE Transactions on Pattern Analysis and Machine Intelligence, Tokyo, Dec. 2012. [6] Carlo Bertolli, Daniele Tarchi, Romano Fantacci, Marco Vanneschi, and Andrea Tassi, "An Integrated Communication-Computing Solution in Emergency Management," ACM International Wireless Communications and Mobile Computing Conference 6th, Caen, France, June. 2010. [7] 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. [8] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms, Third Edition. Cambridge, Mass.: The MIT Press, 2009. [9] 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. [10] Weimin Dong, et al., Chi-Chi, "Taiwan Earthquake Event Report, Risk Management Solutions," Inc., https://www.rms.com/Publications/Taiwan_Event.pdf, retrieved Mar. 2010. [11] Jinling Du, and Dalian Liu, "Hybrid Genetic Algorithm for the Multi-objective Flexible Schedu ling Problem," IEEE International Conference on Computational Intelligence and Security, Nanning, China, Dec. 2010. [12] Arjan Durresi, Mimoza Durresi, Vamsi Paruchuri, and Leonard Barolli, "Ad Hoc Communications for Emergency Conditions," IEEE International Conference on Advanced Information Networking and Applications, Biopolis, Singapore, Mar. 2011. [13] R. C. Eberhart, and J. Kennedy, "New Optimizer Using Particle Swarm Theory," Proc. Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan, Oct. 1995. [14] 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. [15] 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. [16] M.R. Garey, and M.D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. 1979. ISBN 0-7167-1045-5. [17] Harri Holma and Antti Toskala, WCDMA for UMTS : radio access for third generation mobile communications, Third Edition. Chichester, England: Wiley, 2004. [18] Hong Kong Amateur Radio Transmitting Society, Proposal on Amateur Radio Emergency Service in Hong Kong-Mobilezing Radio Amateur’s community Resources for Disaster and Emergency Communications, Document No. 06/XIII/018, Aug. 2005. [19] Jyh-Shyan Huang, Yao-Nan Lien and Yu-Chieh Huang, "Network Topology Planning for Contingency Cellular Network," Proceedings of 17th Mobile Computong Workshop, Aug. 2012, Taoyuan, Taiwan, NSC 100-2221-E-008. [20] ITR-RESCUE, Robust Networking and Information Collection Project, http://www.itr-rescue.org/research/networking.php, retrieved Feb. 2010. [21] Bahareh Jalili, and Mehrdad Dianati, "Application of Taboo Search and Genetic Algorithm in planning and optimization of UMTS radio networks," ACM International Wireless Communications and Mobile Computing Conference 6th, New York, USA, June 2010. [22] Hung-Chin Jang, Yao-Nan Lien and Tzu-Chieh Tsai, "Rescue Information System for Earthquake Disasters Based on MANET Emergency Communication Platform," Proc. of the ACM International Workshop on Advanced Topics in Mobile Computing for Emergency Management: Communication and Computing Platforms (MCEM 2009), June, 2009, Leipzig, Germany, pp. 623-627. [23] K. Habibul Kabir, and Masahiro Sasabe, and Tetsuya Takine, "Integer programming formulation for grouping clusters in ferry-assisted DTNs," IEEE 26th International Conference on Advanced Information Networking and Applications Workshops, Fukuoka-shi, Japan, March. 2012. [24] J. Kennedy, and R. C. Eberhart, "Particle Swarm Optimization," IEEE International Confernece on Neural network, vol. 4, Perth, Australia, Nov. 1995, pp. 1942-1948. [25] Richard E. Krock, "Lack of Emergency Recovery Palnning Is a Disaster Waiting to Happen," IEEE Communications Magazine, Jan. 2011. [26] Tae-Ho Lee and Taesang Choi, "Self powered wireless communication platform for disaster relief," 2011 Asia-Pacific Network Operations and Management Symposium (APNOMS), Sep. 2011. [27] Yao-Nan Lien, Li-Cheng Chi and Yuh-Sheng Shaw, "A Walkie-Talkie-Like Emergency Communication System for Catastrophic Natural Disasters," Proc. of ISPAN09, Kaohsiung, Taiwan, Dec. 2009. [28] Yao-Nan Lien, Hung-Chin Jang, and Tzu-Chieh Tsai, "A MANET Based Emergency Communication and Information System for Catastrophic Natural Disasters," IEEE Workshop on Specialized Ad Hoc Networks and Systems, Montreal, Canada, June. 2009. [29] Yao-Nan Lien, Li-Cheng Chi and Chih-Chieh Huang, "A Multi-hop Walkie-Talkie-Like Emergency Communication System for Catastrophic Natural Disasters," Proceedings of International Conference on Parallel Processing Workshop (on Applications of Wireless Ad Hoc and Sensor Networks), San Diego, CA. [30] Yao-Nan Lien, Hung-Chin Jang and Tzu-Chieh Tsai, "Design of P2Pnet: An Autonomous P2P Ad-Hoc Group Communication System," Proceedings of The First International Workshop on Mobile Peer-to-Peer Information Services (MP2PIS), May 18-21, 2009, Taipei, Taiwan, [31] Jaeaoo Lim, Rchard Klein, and Jason Thatcher, "Good Technology, Bad Management: A Case Study of the Satellite Phone Industry," Journal of Information Technology Management, vol. XVI, no.2, 2005, pp. 48-55. [32] Kelly T. Morrison, AT&T, "Rapidly Recovering from the Catastrophic Loss of a Major Telecommunications Office," IEEE Communications Magazine, vol.19, no.1, Jan. 2011. pp. 28-35. [33] E. Natalizio, "The practical experience of implementing a GSM BTS through open software hardware," 2010 International Symposium on Applied Sciences in Biomedical and Communication Technologies (ISABEL), Nov. 2010. [34] J. Chris Oberg, Andrew G. Whitt, Robert M. Mills, "Disasters Will Happen - Are You Ready?," IEEE Communications Magazine, vol.49, no.1, Jan. 2011. pp. 36-45. [35] Ren Qing-dao-er-ji, and Yuping Wang, Xiaojing Si, "An Improved Genetic Algorithm For Job Shop Scheduling Problem," IEEE International Conference on Computational Intelligence and Security, Nanning, China, Dec. 2010. [36] Yang Ran, "Considerations and Suggestions on Improvement of Communication Network Disaster Countermeasures after the Wenchuan Earthquake," IEEE Communications Magazine, vol.49, no.1, Jan. 2011. pp. 44-47. [37] 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. [38] María Luisa Santamaría, and Sebastià Galmé, "Multi-objective Simulated Annealing Approach for Optimal Routing in Time-Driven Sensor Networks," IEEE 19th Annual International Symposium on Modelling, Analysis, and Simulation of Computer and Telecommunication Systems, Singapore, July. 2011. [39] Zhenhong Shao, Yongxiang Liu, Yi Wu and Lianfeng Shen, "A Rapid and Reliable Disaster Emergency Mobile Communication System via Aerial Ad Hoc BS networks," 2011 International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM) , Sep. 2011 . [40] Yoshitaka Shibata, Yosuke Sato, Naoki Ogasawara, Go Chiba, "A Disaster Information System by Ballooned Wireless Adhoc Network," IEEE International Conference on Complex, Intelligent and Software Intensive Systems, Fukuoka, Japan Mar. 2009. [41] Steven S. Skiena. The algorithm design manual. London: Springer-Verlag London, 2008. [42] The Weather Channel, "Earthquake Deaths to Reach 3.5 Million by 2100," http://www.weather.com/news/science/earthquake-deaths-dramatic-rise-20130221, retrieved Feb. 2013. [43] Stelios Timotheou and Georgios Loukas, "Autonomous Networked Robots for the Establishment of Wireless Communication in Uncertain Emergency Response Scenarios," ACM symposium on Applied Computing, New York, USA, Mar. 2009. [44] Sarah Underwood, "Improving Disaster Management," Comm. of ACM, vol. 53, no. 2, Feb. 2010, pp. 18-20. [45] Misako Urakami, Yuya Okada, Yasuyuki Niwa, Hisaya Motogi, Hiroshi Matsuno, "Construction of Wireless Network for Information Communication for a Disaster-affected Island," IEEE International Conference on Advanced Information Networking and Applications Workshops, Perth, Australia Apr. 2010 [46] Fan Wei, Md.Emadadul Haque, Yukihiro Fukunaga, Takehiro Gouda, Xiaodong Lu and Kinji Mori "Autonomous Community Construction Technology for Timely Transmitting Emergency Information," IEEE Symposia and Workshops on Ubiquitous, Autonomic and Trusted Computing, Shaanxi, China, Oct. 2010. [47] Jiayang Yu, and Ruonan Rao, "A Method for Solving the Performance Isolation Problem in PaaS Based on Forecast and Dynamic Programming," IEEE Fourth International Conference on Computational and Information Sciences (ICCIS), China, August. 2012. [48] 3GPP, Specifications, http://www.3gpp.org/Specifications, retrieved Nov. 2011. [49] 3GPP, TS 23.401, “General Packet Radio Service (GPRS) enhancements for Evolved Universal Terrestrial Radio Access Network (E-UTRAN) access” version 11.0.0 [50] 林進豐, 行動衛星通訊, 五南出版社, ISBN：9789571150062, Dec. 2007 [51] 孫玉, 應急通信技術總體框架討論, 人民郵電出版社, ISBN：7115208328, 2009 [52] 張雪麗等, 應急通信新技術與系統應用, 機械工業出版社, ISBN：9787111292982, Jan. 2010 [53] 姚國章, 應急管理信息化建設, 北京大學出版社, ISBN：9787301155806, Sep. 2009 [54] 連耀南, 黃智賢, 大型自然災害下大規模救災緊急通訊系統方案, Proc. of 2010 National Symposium On Telecommunications, TaoYuan, Taiwan, Dec.2010. [55] 楊永年, “八八水災救災體系之研究,” 公共行政學報, vol. 32, pp.143-169. [56] 交通部電信總局, 九二一震災災後重建電信問答手冊, http://kbteq.ascc.net/archive/dgt/dgt01.html, retrieved Dec. 2011. [57] 國家通訊傳播委員會, 高雄縣莫拉克颱風災後通訊傳播設施改善實施計畫, Jun. 2010 [58] 高抗災通信平臺, http://88flood.www.gov.tw/committee_news_detail.php?cn_id=506, retrieved Dec. 2011.
Description:	碩士國立政治大學資訊科學學系 99753030 101
Source URI:	http://thesis.lib.nccu.edu.tw/record/#G0099753030
Data Type:	thesis
Appears in Collections:	[Department of Computer Science ] Theses

Files in This Item:

File	Size	Format
index.html	0Kb	HTML2	308	View/Open

All items in 政大典藏 are protected by copyright, with all rights reserved.

社群 sharing

著作權政策宣告 Copyright Announcement

1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.

DSpace Software Copyright © 2002-2004 MIT & Hewlett-Packard / Enhanced by NTU Library IR team Copyright © - Feedback