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

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

English | 正體中文 | 简体中文 | Post-Print筆數 : 27 | 全文笔数/总笔数 : 113392/144379 (79%)
造访人次 : 51228393 在线人数 : 905

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

搜寻范围

查询小技巧：

您可在西文检索词汇前后加上"双引号"，以获取较精准的检索结果

若欲以作者姓名搜寻，建议至进阶搜寻限定作者字段，可获得较完整数据

进阶搜寻

主页 ‧ 登入 ‧ 上传 ‧ 说明 ‧ 关于政大典藏 ‧ 管理

到手机版

政大機構典藏 > 資訊學院 > 資訊科學系 > 學位論文 > Item 140.119/61491

请使用永久网址来引用或连结此文件: https://nccur.lib.nccu.edu.tw/handle/140.119/61491

题名:	考慮資源運輸路徑之應急蜂巢式行動通訊網路建置排程 Resource Delivery Path Dependent Deployment Scheduling for Contingency Cellular Network
作者:	高采衣 Kao, Tsai I
贡献者:	連耀南 Lien, Yao Nan 高采衣 Kao, Tsai I
关键词:	大型自然災害應急通訊應急蜂巢式行動通訊網路排程 Large-scale disaster Emergency communication Contingency cellular network Scheduling
日期:	2012
上传时间:	2013-11-01 11:44:04 (UTC+8)
摘要:	當發生大規模的地震或強烈的颱風等重大天然災害時，通訊系統常常隨著電力與交通系統的損毀而癱瘓。由歷年大型災變中多數災區內之行動通訊系統全面中斷即可印證行動通訊系統其實是極為脆弱的，然而有效運作的通訊系統卻是災情傳遞、資源調度及救災是否順利的關鍵因素。本文所探討的應急通訊系統利用倖存的連通基地台和斷訊卻沒有損毀的基地台，以無線電連接起來建構一個臨時性的通訊系統，稱為應急蜂巢式行動通訊網路(Contingency Cellular Network，CCN)。由於各地災情狀況不完全相同，CCN的建構順序必須考慮災區的輕重緩急、時間的急迫等因素依序建構。因此當CCN拓樸規劃完成後，根據CCN拓樸、各地災情嚴重程度以及拓樸中基地台間的相對距離(運輸時間)進行基地台建構排程規劃，以達到最大的總救災效益。本文考慮各基地台所能發揮的救災效益、所需建構時間、以及運輸工具從任一基地台到另一基地台所需運輸時間，提出兩個適合CCN拓樸樹狀結構的考慮資源運輸路徑之最佳化排程模型CCNDS-AC和CCNDS-UC。CCNDS-AC限制建構順序必須從連網台往下循序建構，但CCN-UC則否。因發生突發性大型天然災害時，可容許的計算時間相當短暫，因此提出了兩個快速的啟發式演算法DS-ACG與DS-UCB，可在短時間內求出一組相當逼近於最佳解的建構排程順序，與DS-UCB相互比較。本文以電腦模擬的方式進行小規模實驗與大規模實驗評估，並且用Genetic Algorithm來比較啟發式演算法的效能。結果顯示DS-UCB明顯優於DS-ACG及Genetic Algorithm。在小規模實驗中DS-UCB可求得與最佳解的總救災效益誤差平均約0.9%的近似最佳解建構順序。而在大規模實驗下， DS-UCB與十萬個解中的最佳解─pseudo optimal solution相較，總救災效益平均高出約16.7%，而總救災時間平均約少了19.4%。 When stricken by a large-scale disaster, the efficiency of disaster response operation is very critical to life saving. 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. We designed a contingency cellular network (CCN) by connecting physically intact but service-disrupted base stations together with wireless links. Since the transportation capacity may be very limited, scheduling of CCN deployment order according to the demand of disaster operation and traveling time between base stations becomes an important issue. We propose two optimization models: CCN Deployment Scheduling Antecessor Constrained Problem (CCNDS-AC) and CCN Deployment Scheduling Unconstrained Problem (CCNDS-UC), aiming to maximize the efficiency of disaster response operation. Both problems are proven to be NP Hard. We also designed two rapid heuristic algorithms, DS-ASG and DS-UCB to solve the problems respectively when it is needed in urgent. Finally, we evaluated the proposed algorithms against optimal solutions (in small cases only) as well as genetic algorithm by simulation. The experimental results show that DS-UCB outperforms all other algorithms. In small scale cases, the profit obtained by DS-UCB is only 0.9% smaller than what the optimum solution can get. In large scale cases, as compared to the pseudo optimum solution, which is the best solution among 100,000 solutions, DS-UCB outperforms pseudo optimum solutions in profit by 16.7%, and in traveling time by 19.4%, both in average.
參考文獻:	[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] 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, Hongdong Li, In So Kweon, Cédric Demonceaux, Pascal Vasseur and Katsushi Ikeuchi, "A Branch and Bound Approach to Correspondence and Grouping Problems," IEEE Transactions on Pattern Analysis and Machine Intelligence, Tokoyo, Japan, 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] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, "Introduction to Algorithms," Third Edition, Cambridge, Mass.: The MIT Press, 2009. [8] 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. [9] 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. [10] Jinling Du, and Dalian Liu, "Hybrid Genetic Algorithm for the Multi-objective Flexible Scheduling Problem," IEEE International Conference on Computational Intelligence and Security, Nanning, China, Dec. 2010. [11] 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. [12] 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. [13] M.R. Garey, and M.D. Johnson. "Computers and Intractability: A Guide to the Theory of NP-Completeness," 1979. ISBN 0-7167-1045-5. [14] Jyh-Shyan Huang, Yao-Nan Lien and Yu-Chieh Huang, " Network Topology Planning for Contingency Cellular Network," Proceedings of 17th Mobile Computing Workshop, Aug. 2012, Taoyuan, Taiwan, NSC 100-2221-E-008. [15] Jyh-Shyan Huang, Yan-Song Wang and Yao-Nan Lien, "Deployment Scheduling for Contingency Cellular Network for Disaster Operations," Proceedings of the 15th Asis-Pacific Network Operations and Management Symposium, Sep. 2013, Hiroshima, Japan, NSC 101-2420-H-004-006-MY3. [16] ITR-RESCUE, Robust Networking and Information Collection Project, http://www.itr-rescue.org/research/networking.php, retrieved Feb. 2010. [17] 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. [18] 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. [19] 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. [20] J. Kennedy, and R. C. Eberhart, "Particle Swarm Optimization," IEEE International Confernece on Neural network, vol. 4, Perth, Australia, Nov. 1995, pp. 1942-1948. [21] 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. [22] Yao-Nan Lien and Yung-Chuan Wun, "QoS-Aware Packet Scheduling by Looking Ahead Approach", Proc. of The 19th Workshop on Object-Oriented Technology and Applications, HuWei, Taiwan, Sep. 2008. [23] 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. [24] 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. [25] 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. [26] 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. [27] 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. [28] 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. [29] 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. [30] 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. [31] 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. [32] 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. [33] 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. [34] 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. [35] 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. [36] 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. [37] 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. [38] 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. [39] Search Underwood, "Improving Disaster Management," Comm. of ACM, vol. 53, no. 2, Feb. 2010, pp. 18-20. [40] Misako Urakami, Yuya Okada, Yasuyuki Niwa, Hisaya Motogi and 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. [41] 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. [42] 3GPP, Specifications, http://www.3gpp.org/Specifications, retrieved Nov. 2011. [43] 3GPP, TS 23.401, "General Packet Radio Service (GPRS) enhancements for Evolved Universal Terrestrial Radio Access Network (E-UTRAN) access" version 11.0.0. [44] 林進豐, "行動衛星通訊," 五南出版社, ISBN：9789571150062, Dec. 2007. [45] 姚國章, "應急管理信息化建設," 北京大學出版社, ISBN：9787301155806, Sep. 2009. [46] 孫玉, "應急通信技術總體框架討論," 人民郵電出版社, ISBN：7115208328, 2009. [47] 連耀南, 黃智賢, "大型自然災害下大規模救災緊急通訊系統方案," Proc. of 2010 National Symposium On Telecommunications, Tao-Yuan, Taiwan, Dec.2010. [48] 張雪麗等, "應急通信新技術與系統應用," 機械工業出版社, ISBN：9787111292982, Jan. 2010. [49] 楊永年, "八八水災救災體系之研究," 公共行政學報, vol. 32, pp.143-169, Sep. 2009. [50] 交通部電信總局, "九二一震災災後重建電信問答手冊," http://kbteq.ascc.net/archive/dgt/dgt01.html, retrieved Dec. 2011. [51] 高抗災通信平臺, http://88flood.www.gov.tw/committee_news_detail.php?cn_id=506, retrieved Dec. 2011. [52] 國家通訊傳播委員會, "高雄縣莫拉克颱風災後通訊傳播設施改善實施計畫," Jun. 2010.
描述:	碩士國立政治大學資訊科學學系 100753031 101
資料來源:	http://thesis.lib.nccu.edu.tw/record/#G0100753031
数据类型:	thesis
显示于类别:	[Department of Computer Science ] Theses

文件中的档案:

档案	大小	格式	浏览次数
303101.pdf	4495Kb	Adobe PDF2	211	检视/开启

在政大典藏中所有的数据项都受到原著作权保护.

社群 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 © - 回馈