1. NCCU Academic Hub
  2. Publications
  3. College of Informatics
  4. Theses
  5. Item

Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 以代理人基方法之基礎設施互依性模擬
Infrastructure Interdependency Simulation Using Agent-Based Modeling
作者 劉治宏
Liu, Chih Hung
貢獻者 李蔡彥
Li, Tsai Yen
劉治宏
Liu, Chih Hung
關鍵詞 代理人基模擬
電力網路
互依性分析
Agent-Based Modeling
Power grid
Interdependency
日期 2012
上傳時間 1-Apr-2013 14:39:04 (UTC+8)
摘要 基礎設施是民生不可或缺的元素之一。重要基礎設施通常由許多節點構成，也因為彼此之間相依性極高，所以也被視為一種典型的複雜系統。近年來以資訊科技輔助分析這類重點基礎設施的研究也越來越多，從文獻上來看主要可以分為兩大類：(1)互依性分析(2)系統分析。前者著重於使用像拓樸分析這類數值分析的方式，找出弱點基礎設施；而後者則是使用大量模擬的方式來找尋潛在的弱點基礎設施，並模擬不同情境的危機情境。常見的基礎設施分析，多以拓樸分析為基礎找出弱的節點，並套用蒙地卡羅演算法到模型內，做為模擬的依據，但較少見到以基礎設施的各項屬性和規則當作模型的模擬。因此，本篇論文的貢獻是希望以台灣電力公司之電力基礎設施運轉規章、基礎設施的屬性等這些資料為例，當作建立模型的基礎，將Push-Relabel演算法的步驟分散至各代理人上，作為電力調度平衡的計算方式，並採用Repast Simphony作為我們代理人基模擬的工具。藉由操作這些節點的狀態，我們設計了七個不同情境的模擬，並以IEEE指標做為結果的評估方式，藉以說明我們可以透過代理人基模擬找出基礎設施中的弱點，並能夠建立不同的情境模擬各式的危機和災難，進而提供預防的機會。此外，我們的模擬工具亦提供不同的視覺化呈現結果，讓使用者能夠簡單的看出模擬過程的變化，並能夠將結果儲存並重現。
Infrastructure is important to our lives. Most infrastructure facilities consist of nodes and edges of high dependency. These kinds of facilities are considered as traditional complex systems. The research of using computer technologies to analyze such systems has grown recently. We can classify recent research into two categories: 1. Dependency analysis, and 2. System dynamic analysis. The former focuses on computation methods such as topology analysis to find vulnerable nodes while the latter focuses on large-scale simulation to find potential vulnerable infrastructure facilities. Common dependency analysis uses topology analysis to find vulnerable nodes and apply the Monte-Carlo method to their model. However, it merely applies an infrastructure’s parameters and rules to their model. In this thesis, our contributions are on applying such parameters and rules to our model by taking Taiwan Power Company as an example. On this basis, we use agent-based modeling to simulate the context. We used the Push-Relabel algorithm to dispatch the power flow. And we used Repast Simphony as a tool of agent-based modeling. We established different situations to simulate different disasters such as earthquake or tsunami, and to provide a chance estimate and reduce the damages of such a disaster in advance. Besides, we also used indices of an IEEE standard to evaluate our result. In other words, we can find the vulnerable nodes or potential threat in a power grid with agent-based simulation. Besides, we provided various user interfaces for users to observe the information of the power grid more easily and efficiently. Our user interfaces can dynamically present the change of information on the power grid, and the result can be saved and loaded for future uses.
參考文獻 http://www.taipower.com.tw/left_bar/power_life/power_flow.htm.
     [2] S.M. Rinaldi, J.P. Peerenboom, T.K. Kelly, Identifying, Understanding, and Analyzing Critical Infrastructure Interdependencies, IEEE control systems magazine., 21 (2001) 11-25.
     [3] C.M. Macal, M.J. North, Agent-based Modeling and Simulation, Winter Simulation Conference, (2009).
     [4] L. Hagen, A.B. Kahng, New Spectral Methods for Ratio Cut Partitioning and Clustering IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, (1992).
     [5] L. CIUPALA, The Cost Scaling Algorithm for Bipartite Network, Bulletin of the Transilvania University of Brasov, 2 (2009) 8.
     [6] P. Crucitti, V. Latora, M. Marchiori, Model for Cascading Failures in Complex Networks, Physical Review E, 69 (2004).
     [7] P. Crucitti, V. Latora, M. Marchiori, A Topological Analysis of the Italian Electric Power Grid, Physica A, 338 (2004) 92-97.
     [8] P. Crucitti, V. Latora, M. Marchiori, Locating Critical Lines in High-Voltage Electrical Power Grids, Fluctuation and Noise Letters, 5 (2005).
     [9] F. Cadini, E. Zio, C.-A. Petrescu, Using Centrality Measures to Rank the Importance of the Components of a Complex Network Infrastructure, in: R. Setola, S. Geretshuber (Eds.) Critical Information Infrastructure Security, (Springer Berlin / Heidelberg, 2009), 155-167.
     [10] I. Eusgeld, W. Kröger, G. Sansavini, M. Schläpfer, E. Zio, The Role of Network Theory and Object-Oriented Modeling within a Framework for the Vulnerability Analysis of Critical Infrastructures, Reliability Engineering & System Safety, 94 (2009) 954-963.
     [11] E. Zio, C.-A. Petrescu, G. Sansavini, Vulnerability Analysis of a Power Transmission System, (2008).
     [12] E. Zio, R. Piccinelli, Randomized Flow Model and Centrality Measure for Electrical Power Transmission Network Analysis, Reliability Engineering & System Safety, 95 (2010) 379-385.
     [13] C.M.R. Sanseverino, E. Zio, Solving Advanced Network Reliability Problems by Means of Cellular Automata and Monte Carlo Sampling, Reliability Engineering & System Safety, 89 (2005) 219-226.
     [14] E. Zio, L. Podofillini, V. Zille, A Combination of Monte Carlo Simulation and Cellular Automata for Computing the Availability of Complex Network Systems, Reliability Engineering & System Safety, 91 (2006) 181-190.
     [15] M. Marseguerra, E. Zio, Monte Carlo Simulation for Model-Based Fault Diagnosis in Dynamic Systems, Reliability Engineering & System Safety, 94 (2009) 180-186.
     [16] S.A. Harp, S. Brignone, B.F. Wollenberg, T. Samad, SEPIA. A Simulator for Electric Power Industry Agents, Control Systems, IEEE, 20 (2000) 53-69.
     [17] P. Pederson, D. Dudenhoeffer, S. Hartley, M. Permann, Critical Infrastructure Interdependency Modeling A Survey of U.S and international research, (2006).
     [18] L. Tolbert, H. Qi, F. Peng, Scalable Multi-Agent System for RealTime Electric Power Management, in: Proc. Power Engineering Society Summer Meeting, (2001), 1676-1679.
     [19] M. Anim, Toward Self-Healing Energy Infrastructure Systems, Computer Applications in Power, IEEE, 14 (2001) 20-28.
     [20] S. Panzieri, R. Setola, G. Ulivi, An Agent Based Simulator for Critical Interdependent Infrastructures, (2004).
     [21] M. Schüle, R. Herrler, F. Klügl, Coupling GIS and Multi-Agent Simulation – Towards Infrastructure for Realistic Simulation, in: G. Lindemann, J. Denzinger, I. Timm, R. Unland (Eds.) Multiagent System Technologies, (Springer Berlin / Heidelberg, 2004), 228-242.
     [22] E. Casalicchio, E. Galli, S. Tucci, Federated Agent-Based Modeling and Simulation Approach to Study Interdependencies in IT Critical Infrastructures, in: Proceedings of the 11th IEEE International Symposium on Distributed Simulation and Real-Time Applications, (IEEE Computer Society, 2007), 182-189.
     [23] E. Casalicchio, E. Galli, S. Tucci, Modeling and Simulation of Complex Interdependent Systems: A Federated Agent-Based Approach, in: Critical Information Infrastructure Security, (Springer-Verlag, 2009), 72-83.
     [24] R.C. Mihailescu, M. Vasirani, S. Ossowski, Towards Agent-Based Virtual Power Stations via Multi-Level Coalition Formation, in: First International Workshop on Agent Technologies for Energy Systems, (2010).
     [25] A. Saleem, M. Lind, M.M. Veloso, Multiagent-Based Protection and Control in Decentralized Electric Power Systems, in: First International Workshop on Agent Technologies for Energy Systems, (2010).
     [26] W. Lam, A.M. Segre, A Distributed Learning Algorithm for Bayesian Inference Networks IEEE Transactions on Knowledge and Data Engineering, (2002) 13.
     [27] M. Hoefer, Strategic Cooperation in Cost Sharing Games, 6th International Workshop, WINE, (2010) 17.
     [28] SWARM, http://www.swarm.org.
     [29] MASON, http://cs.gmu.edu/~eclab/projects/mason/.
     [30] Repast Simphony, http://repast.sourceforge.net/.
     [31] A.V. Goldberg, R.E. Tarjan, A New Approach to the Maximum Flow Problem, Proceeding STOC `86 Proceedings of the eighteenth annual ACM symposium on Theory of computing (1986) 11.
     [32] J.D. Glover, M.S. Sarma, T.J. Overbye, Power System Analysis and Design, Fifth Edition, (2011).
     [33] I.P.E. Society, IEEE Guide for Electric Power Distribution Reliability Indices, (2012).
     [34] 台灣電力公司, 超高壓系統之來臨－南北第一路～第三路345kV幹線暨超高壓變電所 http://taipower.pcc.gov.tw/files/15-1002-234,c88-1.php.
     [35] Gordoncheng`s Blog,電力系統負載曲線, http://gordoncheng.wordpress.com/2010/09/06/%E9%9B%BB%E5%8A%9B%E7%B3%BB%E7%B5%B1%E8%B2%A0%E8%BC%89%E6%9B%B2%E7%B7%9Aload-curve/
     [36] Y.H. Liu, Computational Large-Scale Complex Networks : Competition Network and Power Grid, in: Graduate Institute of Applied Physics, (National Chengchi University, 2012), 73.
描述 碩士
國立政治大學
資訊科學學系
98753003
101
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0098753003
資料類型 thesis
dc.contributor.advisor 李蔡彥zh_TW
dc.contributor.advisor Li, Tsai Yenen_US
dc.contributor.author (Authors) 劉治宏zh_TW
dc.contributor.author (Authors) Liu, Chih Hungen_US
dc.creator (作者) 劉治宏zh_TW
dc.creator (作者) Liu, Chih Hungen_US
dc.date (日期) 2012en_US
dc.date.accessioned 1-Apr-2013 14:39:04 (UTC+8)-
dc.date.available 1-Apr-2013 14:39:04 (UTC+8)-
dc.date.issued (上傳時間) 1-Apr-2013 14:39:04 (UTC+8)-
dc.identifier (Other Identifiers) G0098753003en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/57579-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學學系zh_TW
dc.description (描述) 98753003zh_TW
dc.description (描述) 101zh_TW
dc.description.abstract (摘要) 基礎設施是民生不可或缺的元素之一。重要基礎設施通常由許多節點構成，也因為彼此之間相依性極高，所以也被視為一種典型的複雜系統。近年來以資訊科技輔助分析這類重點基礎設施的研究也越來越多，從文獻上來看主要可以分為兩大類：(1)互依性分析(2)系統分析。前者著重於使用像拓樸分析這類數值分析的方式，找出弱點基礎設施；而後者則是使用大量模擬的方式來找尋潛在的弱點基礎設施，並模擬不同情境的危機情境。常見的基礎設施分析，多以拓樸分析為基礎找出弱的節點，並套用蒙地卡羅演算法到模型內，做為模擬的依據，但較少見到以基礎設施的各項屬性和規則當作模型的模擬。因此，本篇論文的貢獻是希望以台灣電力公司之電力基礎設施運轉規章、基礎設施的屬性等這些資料為例，當作建立模型的基礎，將Push-Relabel演算法的步驟分散至各代理人上，作為電力調度平衡的計算方式，並採用Repast Simphony作為我們代理人基模擬的工具。藉由操作這些節點的狀態，我們設計了七個不同情境的模擬，並以IEEE指標做為結果的評估方式，藉以說明我們可以透過代理人基模擬找出基礎設施中的弱點，並能夠建立不同的情境模擬各式的危機和災難，進而提供預防的機會。此外，我們的模擬工具亦提供不同的視覺化呈現結果，讓使用者能夠簡單的看出模擬過程的變化，並能夠將結果儲存並重現。zh_TW
dc.description.abstract (摘要) Infrastructure is important to our lives. Most infrastructure facilities consist of nodes and edges of high dependency. These kinds of facilities are considered as traditional complex systems. The research of using computer technologies to analyze such systems has grown recently. We can classify recent research into two categories: 1. Dependency analysis, and 2. System dynamic analysis. The former focuses on computation methods such as topology analysis to find vulnerable nodes while the latter focuses on large-scale simulation to find potential vulnerable infrastructure facilities. Common dependency analysis uses topology analysis to find vulnerable nodes and apply the Monte-Carlo method to their model. However, it merely applies an infrastructure’s parameters and rules to their model. In this thesis, our contributions are on applying such parameters and rules to our model by taking Taiwan Power Company as an example. On this basis, we use agent-based modeling to simulate the context. We used the Push-Relabel algorithm to dispatch the power flow. And we used Repast Simphony as a tool of agent-based modeling. We established different situations to simulate different disasters such as earthquake or tsunami, and to provide a chance estimate and reduce the damages of such a disaster in advance. Besides, we also used indices of an IEEE standard to evaluate our result. In other words, we can find the vulnerable nodes or potential threat in a power grid with agent-based simulation. Besides, we provided various user interfaces for users to observe the information of the power grid more easily and efficiently. Our user interfaces can dynamically present the change of information on the power grid, and the result can be saved and loaded for future uses.en_US
dc.description.tableofcontents 摘要 viii
     Abstract ix
     第一章 導論 1
     1.1研究動機與目的 1
     1.2問題描述 5
     1.3代理人概述 6
     1.4論文貢獻 7
     1.5論文架構 8
     第二章 相關研究 9
     2.1分析類模型 9
     2.2模擬類模型 10
     第三章 階層式代理人 13
     3.1電力系統特性 14
     3.2代理人基模擬 16
     3.3設計構想 17
     第四章 代理人系統設計 22
     4.1Push-Relabel演算法 23
     4.2資料前處理與電力網路圖建置 30
     4.3代理人實作 31
     4.3.1發電機代理人 31
     4.3.2電廠代理人 32
     4.3.3調度代理人 34
     4.3.4消費者代理人 34
     4.3.5變電站代理人 35
     4.3.6災難代理人 36
     第五章 模擬介面設計 38
     5.1地理座標圖形視圖 39
     5.2變電站階層架構圖形視圖(Substation Schematic View) 40
     5.3電廠階層架構圖形視圖(Powerplant Schematic View) 41
     5.4操作介面設計 42
     第六章 實驗分析 44
     6.1台灣電力網路資訊 44
     6.2模型基本驗證 47
     6.3實驗分析 55
     6.3.1大台北地區電廠損害分析 57
     6.3.2電網分割對大台北地區電廠損害分析 58
     6.3.3中部電廠損壞對大台北地區電廠損害分析 59
     6.3.4電網分割與中部電廠損壞對大台北地區電廠損害分析 60
     6.3.5南電北送樞紐損壞對大台北地區電廠損害分析 62
     6.3.6南電北送樞紐與中部電廠損壞對大台北地區電廠損害分析 63
     6.3.7桃園大台北地區超高壓變電戰損壞數目比較 65
     第七章 結論與未來展望 69
     參考文獻 71
     
      		zh_TW
dc.language.iso en_US-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0098753003en_US
dc.subject (關鍵詞) 代理人基模擬zh_TW
dc.subject (關鍵詞) 電力網路zh_TW
dc.subject (關鍵詞) 互依性分析zh_TW
dc.subject (關鍵詞) Agent-Based Modelingen_US
dc.subject (關鍵詞) Power griden_US
dc.subject (關鍵詞) Interdependencyen_US
dc.title (題名) 以代理人基方法之基礎設施互依性模擬zh_TW
dc.title (題名) Infrastructure Interdependency Simulation Using Agent-Based Modelingen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) http://www.taipower.com.tw/left_bar/power_life/power_flow.htm.
     [2] S.M. Rinaldi, J.P. Peerenboom, T.K. Kelly, Identifying, Understanding, and Analyzing Critical Infrastructure Interdependencies, IEEE control systems magazine., 21 (2001) 11-25.
     [3] C.M. Macal, M.J. North, Agent-based Modeling and Simulation, Winter Simulation Conference, (2009).
     [4] L. Hagen, A.B. Kahng, New Spectral Methods for Ratio Cut Partitioning and Clustering IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, (1992).
     [5] L. CIUPALA, The Cost Scaling Algorithm for Bipartite Network, Bulletin of the Transilvania University of Brasov, 2 (2009) 8.
     [6] P. Crucitti, V. Latora, M. Marchiori, Model for Cascading Failures in Complex Networks, Physical Review E, 69 (2004).
     [7] P. Crucitti, V. Latora, M. Marchiori, A Topological Analysis of the Italian Electric Power Grid, Physica A, 338 (2004) 92-97.
     [8] P. Crucitti, V. Latora, M. Marchiori, Locating Critical Lines in High-Voltage Electrical Power Grids, Fluctuation and Noise Letters, 5 (2005).
     [9] F. Cadini, E. Zio, C.-A. Petrescu, Using Centrality Measures to Rank the Importance of the Components of a Complex Network Infrastructure, in: R. Setola, S. Geretshuber (Eds.) Critical Information Infrastructure Security, (Springer Berlin / Heidelberg, 2009), 155-167.
     [10] I. Eusgeld, W. Kröger, G. Sansavini, M. Schläpfer, E. Zio, The Role of Network Theory and Object-Oriented Modeling within a Framework for the Vulnerability Analysis of Critical Infrastructures, Reliability Engineering & System Safety, 94 (2009) 954-963.
     [11] E. Zio, C.-A. Petrescu, G. Sansavini, Vulnerability Analysis of a Power Transmission System, (2008).
     [12] E. Zio, R. Piccinelli, Randomized Flow Model and Centrality Measure for Electrical Power Transmission Network Analysis, Reliability Engineering & System Safety, 95 (2010) 379-385.
     [13] C.M.R. Sanseverino, E. Zio, Solving Advanced Network Reliability Problems by Means of Cellular Automata and Monte Carlo Sampling, Reliability Engineering & System Safety, 89 (2005) 219-226.
     [14] E. Zio, L. Podofillini, V. Zille, A Combination of Monte Carlo Simulation and Cellular Automata for Computing the Availability of Complex Network Systems, Reliability Engineering & System Safety, 91 (2006) 181-190.
     [15] M. Marseguerra, E. Zio, Monte Carlo Simulation for Model-Based Fault Diagnosis in Dynamic Systems, Reliability Engineering & System Safety, 94 (2009) 180-186.
     [16] S.A. Harp, S. Brignone, B.F. Wollenberg, T. Samad, SEPIA. A Simulator for Electric Power Industry Agents, Control Systems, IEEE, 20 (2000) 53-69.
     [17] P. Pederson, D. Dudenhoeffer, S. Hartley, M. Permann, Critical Infrastructure Interdependency Modeling A Survey of U.S and international research, (2006).
     [18] L. Tolbert, H. Qi, F. Peng, Scalable Multi-Agent System for RealTime Electric Power Management, in: Proc. Power Engineering Society Summer Meeting, (2001), 1676-1679.
     [19] M. Anim, Toward Self-Healing Energy Infrastructure Systems, Computer Applications in Power, IEEE, 14 (2001) 20-28.
     [20] S. Panzieri, R. Setola, G. Ulivi, An Agent Based Simulator for Critical Interdependent Infrastructures, (2004).
     [21] M. Schüle, R. Herrler, F. Klügl, Coupling GIS and Multi-Agent Simulation – Towards Infrastructure for Realistic Simulation, in: G. Lindemann, J. Denzinger, I. Timm, R. Unland (Eds.) Multiagent System Technologies, (Springer Berlin / Heidelberg, 2004), 228-242.
     [22] E. Casalicchio, E. Galli, S. Tucci, Federated Agent-Based Modeling and Simulation Approach to Study Interdependencies in IT Critical Infrastructures, in: Proceedings of the 11th IEEE International Symposium on Distributed Simulation and Real-Time Applications, (IEEE Computer Society, 2007), 182-189.
     [23] E. Casalicchio, E. Galli, S. Tucci, Modeling and Simulation of Complex Interdependent Systems: A Federated Agent-Based Approach, in: Critical Information Infrastructure Security, (Springer-Verlag, 2009), 72-83.
     [24] R.C. Mihailescu, M. Vasirani, S. Ossowski, Towards Agent-Based Virtual Power Stations via Multi-Level Coalition Formation, in: First International Workshop on Agent Technologies for Energy Systems, (2010).
     [25] A. Saleem, M. Lind, M.M. Veloso, Multiagent-Based Protection and Control in Decentralized Electric Power Systems, in: First International Workshop on Agent Technologies for Energy Systems, (2010).
     [26] W. Lam, A.M. Segre, A Distributed Learning Algorithm for Bayesian Inference Networks IEEE Transactions on Knowledge and Data Engineering, (2002) 13.
     [27] M. Hoefer, Strategic Cooperation in Cost Sharing Games, 6th International Workshop, WINE, (2010) 17.
     [28] SWARM, http://www.swarm.org.
     [29] MASON, http://cs.gmu.edu/~eclab/projects/mason/.
     [30] Repast Simphony, http://repast.sourceforge.net/.
     [31] A.V. Goldberg, R.E. Tarjan, A New Approach to the Maximum Flow Problem, Proceeding STOC `86 Proceedings of the eighteenth annual ACM symposium on Theory of computing (1986) 11.
     [32] J.D. Glover, M.S. Sarma, T.J. Overbye, Power System Analysis and Design, Fifth Edition, (2011).
     [33] I.P.E. Society, IEEE Guide for Electric Power Distribution Reliability Indices, (2012).
     [34] 台灣電力公司, 超高壓系統之來臨－南北第一路～第三路345kV幹線暨超高壓變電所 http://taipower.pcc.gov.tw/files/15-1002-234,c88-1.php.
     [35] Gordoncheng`s Blog,電力系統負載曲線, http://gordoncheng.wordpress.com/2010/09/06/%E9%9B%BB%E5%8A%9B%E7%B3%BB%E7%B5%B1%E8%B2%A0%E8%BC%89%E6%9B%B2%E7%B7%9Aload-curve/
     [36] Y.H. Liu, Computational Large-Scale Complex Networks : Competition Network and Power Grid, in: Graduate Institute of Applied Physics, (National Chengchi University, 2012), 73.		zh_TW