실내 빌딩 환경에서 부하 균등을 고려한 대피경로 산출
Planning Evacuation Routes with Load Balancing in Indoor Building Environments
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
본 연구는 복층 건물에서 실내 재난상황이 발생했을 때 적절한 대피경로들을 산출하기 위한 새로운 알고리즘을 제안한다. 제안된 방안은 Disaster Evacuation Graph(DEG)를 도입하여, 탐색시간을 크게 단축시킨다. 또한, 대피 경로 상의 인원수용능력과 그에 따른 인원 분산을 동시에 고려한다. 경로를 탐색하는 과정은 크게 두 단계로 구성된다. 이 때 각 단계는 Horitzontal Tiering(HT)과 Vertical Tiering(VT) 단계라 한다. HT 단계에서는 특정 층 임의의 공간으로부터 계단으로 향하는 가능한 최적의 경로를 산출한다. 그리고 모든 층에 대해 HT 단계를 수행한 이후, 각 층의 모든 공간으로부터 건물 입구나 옥상과 같은 안전지대로 향하는 경로를 결정하기 위해, VT 단계에서 HT 단계의 결과들을 통합한다. 이러한 단계별 과정에서 각각, 층 내 모든 공간으로부터 계단으로 향하는 경로와 각 계단으로부터 안전지대로 향하는 경로가 산출된다. 그리고 이러한 과정에서 경로를 탐색하기 위한 그래프의 범위를 결정하기 위해 티어링(tiering) 기법이 이용된다. 제안된 알고리즘의 성능을 평가하기 위하여, 빠른 탐색과 인원 분산을 위해 기존에 연구되었던 경로탐색 알고리즘들과, 경로탐색에 소요된 시간 및 사용자 대피시간을 비교한다. 제안된 알고리즘은 기존에 비해 더 짧은 시간 내에 빠르게 대피할 수 있는 경로를 산출한다. 특히 경로탐색을 위한 시간복잡도 성능이 뛰어나기 때문에, 높은 층으로 구성된 큰 규모의 건물에서 유용하게 활용할 수 있다.
Abstract
This paper presents a novel algorithm for searching evacuation paths in indoor disaster environments. The proposed method significantly improves the time complexity to find the paths to the evacuation exit by introducing a light-weight Disaster Evacuation Graph (DEG) for a building in terms of the size of the graph. With the DEG, the method also considers load balancing and bottleneck capacity of the paths to the evacuation exit simultaneously. The behavior of the algorithm consists of two phases: horizontal tiering (HT) and vertical tiering (VT). The HT phase finds a possible optimal path from anywhere of a specific floor to the evacuation stairs of the floor. Thus, after finishing the HT phases of all floors in parallel the VT phase begins to integrate all results from the previous HT phases to determine a evacuation path from anywhere of a floor to the safety zone of the building that could be the entrance or the roof of the building. It should be noted that the path produced by the algorithm. And, in order to define the range of graph to process, tiering scheme is used. In order to test the performance of the method, computing times and evacuation times are compared to the existing path searching algorithms. The result shows the proposed method is better than the existing algorithms in terms of the computing time and evacuation time. It is useful in a large-scale building to find the evacuation routes for evacuees quickly.
참고문헌 (22)
- G. Ni., "Incremental Updates Based on Graph Theory for Consumer Electronic Devices", IEEE Transactions on Consumer Electronics, 61(1), pp.128~136 (2015)
- C. Hernández., "Reusing Cost-Minimal Paths for Goal-Directed Navigation in Partially Known Terrains", Autonomous Agents and Multi-Agent Systems (2014)
- J. Ahn., "RescueMe : An Indoor Mobile Augmented-Reality Evacuation System by Personalized Pedometry", 2011 IEEE Asia-Pacific Services Computing Conference, pp.70~77 (2011)
- W. Bian., "Research on Personalized Indoor Routing Algorithm", 2014 13th International Symposium on DCABES, pp.275~277 (2014)
- L. S. C. Pun-Cheng, "An Interactive Web-Based Public Transport Enquiry System With Real-Time Optimal Route Computation", IEEE Transactions on Intelligent Transportation Systems, 13(2), pp.983~988 (2012)
- H. Yu., "Use Critical Sub-graph to Optimize the In-building Shortest Path Algorithm", 20123rd International Conference on Innovations in Bio-Inspired Computing and Applications, pp.323~328 (2012)
- S. Chen., "Search for All Minimal Paths in a General Large Flow Network", IEEE Transactions on Reliability, 61(4), pp.949~956 (2012)
- 라동준, "Wi-Fi 신호를 사용하지 않고 보행자 궤적과 건물내 지도 특성만을 이용한 스마트폰 실내 위치 측정 시스템", 대한임베디드공학회논문지, 9(6), pp.323~334 (2014), 대한임베디드공학회[DOI]
- T. S. Perry, "Navigating the Great Indoors", IEEE Spectrum, 49(11), pp.15~ (2012)
- B. Xiao, "An Efficient Algorithm for Dynamic Shortest Path Tree Update in Network Routing", Journal of Communications and Networks, 9(4), pp.473~481 (2007), 한국통신학회
- B. Pizzileo., "A New Algorithm for Controlling Building Evacuation by Feedback on Hazard Level and Crowd Distribution", Proc. of IEEE Industrial Electronics Society Annual International Conference (IECON), pp.434~439 (2011)
- 김은성, "인간이동 감지기술을 활용한 다중이용건축물에서의 최적피난경로 알고리즘의 연구", 한국디지털건축인테리어학회 논문집, 8(2), pp.13~20 (2008), 한국디지털건축·인테리어학회
- 곽수영, "건물내 전체 인원분포를 고려한 실내 보행자 최적 대피모형", 한국지형공간정보학회지, 20(2), pp.23~29 (2012), 한국지형공간정보학회[DOI]
- 강창모, "재난지역에서의 대피·대응 동시수행을 위한 다중목적 긴급대피경로 최적화", 대한토목학회논문집(국문), 34(2), pp.617~626 (2014), 대한토목학회[DOI]
- 장민수, "BLE 환경에서 실내 위기관리를 위한 스마트 장치 기반의 재난대피 시스템", 대한임베디드공학회논문지, 10(5), pp.281~296 (2015), 대한임베디드공학회[DOI]
- J. Sun., "Indoor Evacuation Routes Planning with a Grid Graph-based Model", 2011 19th International Conference on Geoinformatics, pp.1~4 (2011)
- T. Y. Wang., "The Application of the Shortest Path Algorithm in the Evacuation System", 2011 International Conference on ICM, 2, pp.250~253 (2011)
- C. Hernández., "Reusing Cost-Minimal Paths for Goal-Directed Navigation in Partially Known Terrains", Autonomous Agents and Multi-Agent Systems (2014)
- R. Prim, "Shortest Connection Networks and Some Generalizations", Bell System Technical Journal, 36, pp.1389~1401 (1957)
- 이상운, "최소신장트리를 이용한 무방향 그래프의 점대점 최단경로 탐색알고리즘", 한국컴퓨터정보학회논문지, 19(7), pp.103~111 (2014), 한국컴퓨터정보학회
- "Ability Systems"[URL]
- "Korea Information Engineering Services"[URL]