[논문]최대 커버리지 센서 배치를 위한 유전 알고리즘

윤유림; 김용혁

doi:10.5391/jkiis.2010.20.3.406

최대 커버리지 센서 배치를 위한 유전 알고리즘
Genetic Algorithms for Maximizing the Coverage of Sensor Deployment 원문보기

한국지능시스템학회 논문지 = Journal of Korean institute of intelligent systems, v.20 no.3, 2010년, pp.406 - 412

윤유림 (서울대학교 컴퓨터공학부) , 김용혁 (광운대학교 컴퓨터소프트웨어학과)

초록
AI-Helper

본 논문에서는 실세계에서 센서를 배치할 때 발생하는 최적화 문제인 최대 커버리지 센서 배치 문제를 정의하고 문제의 해 공간의 특성을 분석하였다. 또한 최대 커버리지 센서 배치 문제의 좋은 해를 얻기 위해 유전 알고리즘을 설계하고 그 우수성을 비교 실험을 통해 보였다. 이 문제에 유전 알고리즘을 적용할 때 중요하게 고려되어야 할 부분은 평가 함수를 어떻게 구현하느냐 인데 몬테카를로법을 통해 해결할 수 있었다. 유전 알고리즘의 몬테카를로법을 이용한 평가 부분에서 샘플 생성 횟수를 조절함으로써 동일한 성능을 내면서 계산 시간을 크게 줄일 수 있었다.

Abstract ▼ AI-Helper

In this paper, we formally define the problem of maximizing the coverage of sensor deployment, which is the optimization problem appeared in real-world sensor deployment, and analyze the properties of its solution space. To solve the problem, we proposed novel genetic algorithms, and we could show their superiority through experiments. When applying genetic algorithms to maximum coverage sensor deployment, the most important issue is how we evaluate the given sensor deployment efficiently. We could resolve the difficulty by using Monte Carlo method. By regulating the number of generated samples in the Monte Carlo evaluation of genetic algorithms, we could also reduce the computing time significantly without loss of solution quality.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 실제 센서 배치를 할 때 많이 발생하는 문제인 최대 커버리지 센서 배치 문제를 정의하고 그 문제 공간의 성질을 분석했다. 또한 유전 알고리즘을 통해 좋은 해를 구하는 방법을 모색해 보았다.
본 논문에서는 일정한 넓이의 지역을 주어진 종류와 개수의 센서들로 최대한 많이 커버하는 것을 목적으로 하는 문제를 고려해 본다. 보통 센서 배치에 관한 연구들에서 비용 문제로 인해 센서들을 무한히 많이 생산할 수는 없으며 센서의 탐지 범위를 넓히기 위해 최대한 넓은 범위를 커버 하는 것이 효율적이라는 면에서 위 문제는 실제 세계에 적용 분야가 무척 많은 문제라 할 수 있다.
보통 센서 배치에 관한 연구들에서 비용 문제로 인해 센서들을 무한히 많이 생산할 수는 없으며 센서의 탐지 범위를 넓히기 위해 최대한 넓은 범위를 커버 하는 것이 효율적이라는 면에서 위 문제는 실제 세계에 적용 분야가 무척 많은 문제라 할 수 있다. 이 논문에서는 위 문제를 명확하게 정의하고 좋은 해를 찾기 위해 유전 알고리즘을 이용한 효율적인 알고리즘을 모색해 본다.

가설 설정

이것을 알아보기 위해 본 논문에서는 전체 영역 A를[0,100]× [0,100]의 정사각형으로 가정하고 그 안에 중심이 (50,50), 탐지거리가 40인 센서 한 개를 배치한 가장 간단한 경우에 대해 몬테카를로법을 수행해 보았다.
일단 센서는 세 종류가 있는 경우를 다루었고 커버해야 하는 전체 영역을 [0,100]× [0,100]의 정사각형으로 가정하였다.
최대 커버리지 센서 배치 문제에서 커버해야 하는 전체 영역은 다양한 모양으로 나타날 수 있지만 본 연구에서는 기본적인 2차원 정사각형 모양인 [0,100]× [0,100]을 가정하기로 한다.

제안 방법

이보다 더 많은 횟수의 난수를 발생하게 되면 해를 평가하는데 너무 오랜 시간이 소모되어 좋은 해를 찾는다 해도 비용이 너무 많이 들게 된다. 그러나 최종적으로는 유전 알고리즘의 최종 해를 1,000,000 회의 난수 점을 발생해서 재평가하여 실제에 아주 근접한 값을 구하도록 하였다.
이제 컴퓨터로 난수를 발생하여 무작위로 정사각형 내부에 점을 찍는다. 그리고 정사각형의 꼭지점과의 거리를 계산하여 점이 사분원의 내부에 있는지 외부에 있는지를 판단한다. 예를 들어 전체 m 개의 점을 찍었다고 할 때 이중 n 개가 사분원의 내부에 있었다면 두 숫자의 비율, 즉, n/m의 값은 넓이의 비인 π/4에 근접하리라고 예측할 수 있다.
이 점에 착안하여 난수 발생 횟수를 일정하게 고정하지 않고 처음에는 적은 수의 난수만 발생하다가 세대가 지남에 따라 점점 더 많은 수의 난수를 발생해서 평가 함수에 적용하여 후반으로 갈수록 정확도를 높이도록 하는 방법도 함께 구현했다. 다음 절의 실험 결과에 난수 발생 횟수를 일정하게 고정한 방식과 세대가 지남에 따라 점점 횟수를 늘리는 방식의 성능을 비교했다.
RANDOM은 GA와 수행 시간이 비슷하게 걸리도록 하기 위해 25,000 개(GA를 한번 수행할 때 생성하는 자식 해의 총 개수)의 랜덤 배치들 중 가장 좋은 품질의 배치를 선택하는 것을 한 번 수행하는것으로 정했다. 또, 몬테카를로법을 통한 해의 평가에서 발생한 난수 점의 개수를 일정하게 고정하지 않고 세대수가 증가할수록 개수를 점점 늘려나가는 방식(MGA)의 성능도 같이 비교했다. 이 경우 초기 난수 발생 횟수를 10,000으로하고 100 세대가 지날 때마다 10,000 회씩 늘려 나갔다.
본 논문에서는 실제 센서 배치를 할 때 많이 발생하는 문제인 최대 커버리지 센서 배치 문제를 정의하고 그 문제 공간의 성질을 분석했다. 또한 유전 알고리즘을 통해 좋은 해를 구하는 방법을 모색해 보았다.
본 논문의 모든 실험에서 확장 상자 연산자의 확장비율 α를 0.5, 가우시안 변이 연산자의 표준 편차 σ를 전체 구간 길이의 반인 50, 변이 확률 pm을 0.1로 정했다.
유전 알고리즘의 성능을 비교해보기 위해 임의로 생성한 해들 중 가장 좋은 품질(RANDOM)과 유전 알고리즘으로 구한 해의 품질(GA)을 비교했다. RANDOM은 GA와 수행 시간이 비슷하게 걸리도록 하기 위해 25,000 개(GA를 한번 수행할 때 생성하는 자식 해의 총 개수)의 랜덤 배치들 중 가장 좋은 품질의 배치를 선택하는 것을 한 번 수행하는것으로 정했다.
문제에서 마지막에는 실제와 유사한 정확한 평가 값이 필요하지만 사실 유전 알고리즘이 수행되는 중간에는 각 해들의 값이 정확한 것보다는 평가에 들어가는 비용을 줄이는것이 더 효율적일 수 있다. 이 점에 착안하여 난수 발생 횟수를 일정하게 고정하지 않고 처음에는 적은 수의 난수만 발생하다가 세대가 지남에 따라 점점 더 많은 수의 난수를 발생해서 평가 함수에 적용하여 후반으로 갈수록 정확도를 높이도록 하는 방법도 함께 구현했다. 다음 절의 실험 결과에 난수 발생 횟수를 일정하게 고정한 방식과 세대가 지남에 따라 점점 횟수를 늘리는 방식의 성능을 비교했다.

대상 데이터

교차 연산자로는 실수 문제에 대해 좋은 성능을 보이는것으로 알려진 확장 상자 교차 연산자를 채택했고 변이 연산자로는 가우시안 변이 연산자를 사용했다. 확장 상자 연산자는 두 부모해의 각각의 좌표마다 두 값 사이의 상자를 일정 비율 늘려서 그 안에서 고른 확률로 자식 해를 선택하는 방법이고, 가우시안 변이 연산자는 변이량이 일정 표준편차를 가진 정규 분포를 따르도록 하는 방법이다.

이론/모형

결국 각 센서의 위치를 중심으로 하고 반지름이 센서의 탐지 거리인 원들의 면적 합이 되는데 각 원들이 서로 겹치기도 하므로 원의 면적 공식 같은 수식으로는 구하기가 쉽지 않다. 따라서 본 논문에서는 몬테카를로법으로 주어진 해를 평가한다.

성능/효과

MGA의 결과를 보면 GA에 비해 시간이 거의 반으로 줄어들었지만 해의 품질은 크게 차이가 나지 않았다는 것을 확인할 수 있다. 따라서 처음에는 약간 부정확하게 해를 평가하다가 세대가 지남에 따라 점점 정확도를 높여가는 방법이 더 효율적이라고 할 수 있다.
이렇게 생성된 N/2 개의 자식 해와 N 개의 기존 부모 해 중 품질이 가장 좋은 N 개가 다음 세대를 구성한다. 본 논문에서는 50의 인구수를 사용했고 1,000 세대를 수행한 후 이제까지 찾은 해 중 가장 좋은 해를 출력한다.
최대 커버리지 센서 배치 문제의 표현 공간과 해 공간의 관계는 몫(quotient) 공간의 개념으로 이해할 수 있으며 이러한 문제의 성질을 응용하면 좀 더 좋은 해를 구할 수 있을 것이다. 본 연구에서 고안한 유전 알고리즘의 성능이 임의로 발생한 해들보다 품질이 좋다는 것을 실험을 통해 확인함으로써 최대 커버리지 센서 배치 문제에 유전 알고리즘이 문제의 해 공간을 조금 더 효율적으로 탐색할 수 있음을 보였다. 유전 알고리즘에서 해의 평가를 몬테카를로법을 통해 구현하였고 몬테카를로법에서 사용되는 난수 점의 발생 횟수를 고정하지 않고 처음에는 적은 수로 시작해서 유전 알고리즘의 세대가 증가함에 따라 점점 늘려나가는 방식을 통해 수행 시간을 단축하는 효과를 얻을 수 있었다.
본 연구에서 고안한 유전 알고리즘의 성능이 임의로 발생한 해들보다 품질이 좋다는 것을 실험을 통해 확인함으로써 최대 커버리지 센서 배치 문제에 유전 알고리즘이 문제의 해 공간을 조금 더 효율적으로 탐색할 수 있음을 보였다. 유전 알고리즘에서 해의 평가를 몬테카를로법을 통해 구현하였고 몬테카를로법에서 사용되는 난수 점의 발생 횟수를 고정하지 않고 처음에는 적은 수로 시작해서 유전 알고리즘의 세대가 증가함에 따라 점점 늘려나가는 방식을 통해 수행 시간을 단축하는 효과를 얻을 수 있었다.

후속연구

최대 커버리지 센서 배치 문제의 표현 공간과 해 공간의 관계는 몫(quotient) 공간의 개념으로 이해할 수 있으며 이러한 문제의 성질을 응용하면 좀 더 좋은 해를 구할 수 있을 것이다. 본 연구에서 고안한 유전 알고리즘의 성능이 임의로 발생한 해들보다 품질이 좋다는 것을 실험을 통해 확인함으로써 최대 커버리지 센서 배치 문제에 유전 알고리즘이 문제의 해 공간을 조금 더 효율적으로 탐색할 수 있음을 보였다.

질의응답

핵심어	질문	논문에서 추출한 답변
	최적화된 센서 배치의 장점은?	특히 표적의 움직임을 감시하는 지상 작전에서는 자동으로 센서를 배치하고 관리하는 시스템이 필수적이다. 최적화된 센서 배치는 사람의 노동력과 시간을 절약해주고 표적의 움직임에 대한 정확한 정보를 제공해주며 동적인 전장(dynamic field)에서 빠르게 전략을 수정할 수 있도록 해 준다. 따라서 센서들을 최적으로 잘 배치하면 표적에 대해 더 명확히 파악할 수 있게 된다.
	센서의 성능 발전에 따라 무선 센서 네트워크는 어떤 분야에 응용되어 왔는가?	센서의 성능이 점점 발전함에 따라 무선 센서 네트워크는 자연 재해 대처, 서식지 감시, 특정 지역의 기후에 대한 연구, 표적에 대한 감시, 응급 구조, 의료 등 여러 분야에 응용되어 왔다. 요즘은 감시 시스템을 구축하는 데 자동화된 센서 배치가 필요한 경우가 많아졌다.
	최대 커버리지 센서 배치 문제의 해가 실수 좌표로 표현되는 특징으로 인한 어려움은?	최대 커버리지 센서 배치 문제의 특징은 해가 실수 좌표로 표현된다는 것이다. 실수 최적화 문제 중 하나로 생각할 수 있으며 이산 공간과 다른 실수 공간의 특성상, 해의 개수가 무한하다는 점에서 좋은 해를 찾기가 그만큼 더 어렵다고 볼 수 있다.

참고문헌 (15)

Y. Zou and K. Chakrabarty, "Sensor deployment and target localization based on virtual forces," Proc. IEEE INFOCOM, pp. 1293-1303, 2003.
A. Howard, M. J. Mataric and G. S. Sukhatme, “Mobile sensor network deployment using potential field: a distributed scalable solution to the area coverage problem”, Proc. International Conference on Distributed Autonomous Robotic Systems, pp. 299-308, 2002.
S. S. Dhillon, K. Chakrabarty and S. S. Iyengar, “Sensor placement algorithms for grid coverage”, Proc. International Conference on Information Fusion, pp. 1581-1587, 2002.
X. Xu and S. Sahni, "Approximation algorithms for wireless sensor deployment," IEEE Transactions on Computers, Vol. 56, No. 12, pp.1681-1695, 2007.

상세보기
Y. Xu and X. Yao, "A GA approach to the optimal placement of sensors in wireless sensor networks with obstacles and preferences," Proc. 3rd IEEE Consumer Communications and Networking Conference, pp. 127-131, 2006.
H. Zhang and J. C. Hou, "Maintaining sensing coverage and connectivity in large sensor networks," Ad Hoc and Sensor Wireless Networks. Vol. 1, No. 1, pp. 89-124, 2005.
K. Chakrabarty, S. S. Iyengar, H. Qi and E. Cho, “Grid coverage for surveillance and target location in distributed sensor networks”, IEEE Transactions on Computers, Vol. 51, pp. 1448-1453, 2002.

상세보기
C. Sharp, S. Schaffert, A. Woo, N. Sastry, C. Karlof, S. Sastry, and D. Culler, "Design and implementation of a sensor network system for vehicle tracking and autonomous interception," European Workshop on Sensor Networks, pp. 93-107, 2005.
C. Zhao, Z. Yu, and P. Chen, "Optimal deployment of nodes based on genetic algorithm in heterogeneous sensor networks," Proc. International Conference on Wireless Communications, Networking and Mobile Computing, pp. 2743-2746, 2007.
J.-H. Seo, Y.-H. Kim, H.-B. Ryou, S.-H. Cha and M. Jo, "Optimal Sensor Deployment for Wireless Surveillance Sensor Networks by a Hybrid Steady-State Genetic Algorithm," IEICE Transactions on Communications, Vol. E91-B, No. 11, pp. 3534-3543, 2008.

상세보기
M. Cardei, M. Thai, Y. Li, and W. Wu, "Energy efficient target coverage in wireless sensor networks," Proc. IEEE INFOCOM, pp. 1976-1984,
G. Wang, G. Cao, T. L. Porta, and W. Zhang, "Sensor relocation in mobile sensor networks," Proc. IEEE INFOCOM, pp. 2302-2312, 2005.
X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless, and C. Gill, "Integrated coverage and connectivity configuration in wireless sensor networks," Proc. First International Conference on Embedded Networked Sensor Systems, pp. 28-39,
M. Locateli and U. Raber, “Packing equal circles in a square: a deterministic global optimization approach”, Discrete Applied Mathematics, Vol. 122, pp. 139-166, 2002.

상세보기
S. Meguerdichian, S. Slijepcevic, V. Karayan and M. Potkonjak, “Coverage problems in wireless ad-hoc sensor networks”, Proc. IEEE INFOCOM, Vol. 3, pp. 1380-1387, 2001.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증