EGOSST를 이용한 이동 경로의 가중치를 반영한 효과적 연결
Efficient Connection of Migration Routes with Their Weights Using EGOSST
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문에서는 EGOSST를 이용하여 가중치를 갖는 이동 경로들을 최소 비용으로 모두 연결하는 방법을 제안한다. 이동 경로는 가중치 선분으로 변환될 수 있는데, 이것은 통신선, 도로 및 철도망에서의 동적 궤적뿐 만 아니라, 가중치인 이동 량이나 통행 빈도를 포함한다. 제안되는방법은 단순한 위치 정보만을 고려하여 처리하는 방법에 비해 더 광범위하고 유용한 분야에 응용이 가능할 것이다. 입력 선분의 수, 각 선분가중치의 최대 크기, 그리고 그리드 정밀도를 입력 인자로 설정한 실험에서, 본 논문에서 제안된 방법은 가중치 최소 신장 트리를 이용한 방법과 비교할 때, 연결 비용은 평균 1.07%, 가중치 스타이너 최소 트리 방법에 비해서는 평균 0.43% 감소하였다. 또한 그리드 정밀도를 0.1과0.001로 했을 경우, 가중치 최소 신장 트리 방법에 비해 실행 시간이 각각 평균 97.02%, 2843.87% 증가했으나, 연결 비용은 각각 평균 0.86%, 1.13% 감소되었다. 이는 제안된 방법이 가중치를 반영한 이동 경로의 효과적 연결 뿐 아니라, 그리드 정밀도를 조절하여 생성 시간과 비용 절감 율을 응용 분야에 맞추어 사용될 수 있음을 보인다.
Abstract
In this paper, a mechanism connecting all weighted migration routes with minimum cost with EGOSST is proposed. Weighted migration routes may be converted to weighted input edges considered as not only traces but also traffics or trip frequencies of moving object on communication lines, roads or railroads. Proposed mechanism can be used in more wide and practical area than mechanisms considering only moving object traces. In our experiments, edge number, maximum weight for input edges, and detail level for grid are used as input parameters. The mechanism made connection cost decrease average 1.07% and 0.43% comparing with the method using weight minimum spanning tree and weight steiner minimum tree respectively. When grid detail level is 0.1 and 0.001, while each execution time for a connecting solution increases average 97.02% and 2843.87% comparing with the method using weight minimum spanning tree,connecting cost decreases 0.86% and 1.13% respectively. This shows that by adjusting grid detail level, proposed mechanism might be well applied to the applications where designer must grant priority to reducing connecting cost or shortening execution time as well as that it can provide good solutions of connecting migration routes with weights.
참고문헌 (13)
- G.L. Xue, "Grade of Service Steiner Minimum Trees in Euclidean Plane", Algorithmica, 31, pp.479~500 (2001)
- 박수창, "무선 센서 네트워크에서 예측 가능한 싱크 이동성을 기반으로 한 데이타 전달 프로토콜", 정보과학회논문지 : 컴퓨팅의 실제 및 레터, 14(3), pp.276~280 (2008), 한국정보과학회
- Wing Ho Yuen, "Effect of Node Mobility on Highway Mobile Infostation networks", MSWIM '03 Proceedings of the 6th ACM international workshop on Modeling analysis and simulation of wireless and mobile systems, pp.82~91 (2003)
- D. Bunnjaweht, "Capacity enhancement of a multi-beam technique in a WCDMA network using multiple path connections", Mobility '06 Proceedings of the 3rd international conference on Mobile technology, applications & systems (2006)
- Dongfang Zheng, "Virtual Traffic Path Optimization in Connection-Oriented Networks with Stochastic Traffic", Journal of Network and Systems Management, 12(2), pp.231~249 (2004)
- A. Arvidsson, "The Design and Management of ATM Virtual Path Connection Networks", MASCOTS '99 Proceedings of the 7th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, pp.2~9 (1999)
- Yi-Ting Chien, "An Alternative-Path Approach to Improve Robustness of TCP Connections in Wireless Mesh Networks", 2010 Sixth International Conference on Intelligent Information Hiding and Multimedia Signal, pp.248~251 (2010)
- T.H. Cormen, "Introduction to Algorithm, 2ndEd", pp.561~579 (2001), MIT Press
- "Steiner Minimal Tree Problem"[URL]
- 김인범, "선분상의 포탈을 이용한 근사 선분 최소 신장 트리의 생성", 정보처리학회논문지. 컴퓨터 및 통신시스템, 16(6), pp.509~518 (2009), 한국정보처리학회
- J. Kim, "A Polynomial Time Approximation Scheme for the Grade of Services Steiner Minimum Tree Problem", Journal of Global Optimization, 24, pp.437~448 (2002)
- 김준모, "센서 네트워크 구축에서의 Combinatorial 기법 적용", 전자공학회논문지 - TC, 45(7), pp.9~16 (2008), 대한전자공학회