[논문]센서 네트워크에서 실시간 침입탐지 라우팅을 위한 다목적 개미 군집 최적화 알고리즘

강승호

doi:10.3745/ktccs.2013.2.5.191

센서 네트워크에서 실시간 침입탐지 라우팅을 위한 다목적 개미 군집 최적화 알고리즘
A Multi-objective Ant Colony Optimization Algorithm for Real Time Intrusion Detection Routing in Sensor Network 원문보기

정보처리학회논문지. KIPS transactions on computer and communication systems 컴퓨터 및 통신 시스템, v.2 no.5, 2013년, pp.191 - 198

강승호 (국가수리과학연구소 수리생물학연구팀)

초록
AI-Helper

이동하는 베이스 노드를 가진 무선 센서 네트워크(WSN)에서 실시간 침입탐지를 위해서는 침입을 탐지한 센서로부터 베이스 노드까지의 정보 전달이 짧은 라우팅 경로를 통해 이루어져야 한다. 센서 네트워크에서 최소 Wiener수 신장트리(MWST)기반 라우팅 방법은 최소 신장트리(MST)기반 라우팅 방법에 비해 작은 홉 수를 보장하고 있어서 실시간 침입탐지에 적합함이 알려져 있다. 하지만 주어진 네트워크로부터 최소 Wiener 수 신장트리를 찾는 문제는 NP-hard이고 특정 노드에 대한 의존성이 커서 최소 신장 트리 기반 라우팅 방법에 비해 짧은 네트워크 수명을 갖는 단점이 있다. 본 논문은 실시간 침입탐지를 위해 최소 Wiener수 신장트리를 개선해 작은 홉 수와 긴 네트워크의 수명을 동시에 보장하는 라우팅 트리를 찾는 다목적 개미 군집 최적화 알고리즘을 제안한다. 그리고 제안한 라우팅 트리의 성능을 패킷의 평균 전송 홉 수 및 네트워크 전력 소모, 네트워크의 수명 측면에서 최소 신장트리기반 라우팅 방법 및 최소 Wiener수 신장트리기반 라우팅 방법과 비교한다.

Abstract ▼ AI-Helper

It is required to transmit data through shorter path between sensor and base node for real time intrusion detection in wireless sensor networks (WSN) with a mobile base node. Because minimum Wiener index spanning tree (MWST) based routing approach guarantees lower average hop count than that of minimum spanning tree (MST) based routing method in WSN, it is known that MWST based routing is appropriate for real time intrusion detection. However, the minimum Wiener index spanning tree problem which aims to find a spanning tree which has the minimum Wiener index from a given weighted graph was proved to be a NP-hard. And owing to its high dependency on certain nodes, minimum Wiener index tree based routing method has a shorter network lifetime than that of minimum spanning tree based routing method. In this paper, we propose a multi-objective ant colony optimization algorithm to tackle these problems, so that it can be used to detect intrusion in real time in wireless sensor networks with a mobile base node. And we compare the results of our proposed method with MST based routing and MWST based routing in respect to average hop count, network energy consumption and network lifetime by simulation.

주제어

AI 본문요약
AI-Helper

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

문제 정의

모든 센서간 라운드 패킷 전송은 센서 네트워크 모델에 다수의 베이스 노드나 베이스 노드의 이동성을 포함하기 위한 시나리오이다. 일반적으로 무선 센서 네트워크에서는 베이스 노드와 가장 근접한 센서가 다른 센서로부터 전송된 데이터를 최종적으로 베이스 노드에 전달하게 되므로 모든 센서가 이동하는 베이스 노드의 최근접 센서가 될 수 있기 때문이다.
본 논문은 이동하는 베이스 노드를 가진 센서 네트워크 환경 하에서 실시간 침입탐지를 위해 Wiener 수 신장트리의 장점인 작은 전송 홉 수와 높은 에너지 효율성을 보장하면서 동시에 단점인 짧은 네트워크 수명을 개선하고자 다목적 개미 군집 최적화 알고리즘을 제안한다. 제안하는 개미군집 최적화 알고리즘은 조합 최적화 문제 해결에 사용되는 메타 휴리스틱 알고리즘의 하나로 수백 개의 센서로 구성된 네트워크에도 사용이 가능하다.
하지만 특정 노드들에 대한 전송 의존도가 높아 네트워크 수명이 짧은 단점을 가지고 있다. 본 논문은 이러한 단점들을 보완하고자 지연 시간 최소화와 더불어 네트워크 수명 연장을 목적으로 하는 다목적 개미 군집 최적화 알고리즘을 설계하였다. 많은 수의 센서를 가진 네트워크에도 사용이 가능하며 평균 홉 수나 네트워크 효율성은 MWST기반 라우팅 방법과 비슷한 결과를 보인 반면 네트워크 수명에 있어서는 MST에 기반한 방법과 비슷한 결과를 보였다.
하지만 네트워크의 수명 단축이라는 효과도 동시에 가져온다는 사실을 확인할 수 있다. 본 논문은 패킷 전송에서 지연시간 최소화와 네트워크 수명 최대화라는 상충관계에 있는 두 가지 목적을 모두 만족시키는 라우팅 트리 토폴로지의 생성을 위해 다목적 개미 군집 최적화(Multi-Object Ant Colony Optimization) 알고리즘을 제시한다. 개미 군집 최적화 알고리즘은 조합 최적화 문제를 해결하는데 사용되는 메타 휴리스틱 알고리즘으로 여러 분야에서 다양한 문제에 사용되고 있다[12, 15, 16, 17, 18].

가설 설정

특정 센서 네트워크 표준 기술의 하위 계층 프로토콜들의 효과를 차단하고 순수한 토폴로지 효과만을 검증하기 위하여 [9]에서 사용한 모의 실험기(simulator)를 수정하여 제작하였다. 모의 실험기는 네트워크 내의 모든 센서는 동일한 종류를 가정하였다. 50m×50m 공간에 50, 60, 70, 80, 90, 100개의 센서가 임의로 배치된 상황에서 모든 실험이 진행 되었다.

제안 방법

50m×50m 공간에 50, 60, 70, 80, 90, 100개의 센서가 임의로 배치된 상황에서 모든 실험이 진행 되었다.
S는 식 (5)를 따르는 확률 변수이다. 만약 q가 q₀보다 크면 현재 선택 가능한 모든 간선을 대상으로 S에 의해 확률을 부여하고 부여 된 확률에 비례해서 특정 간선이 선택되도록 한다. 식 (5)의 위 식 분모는 현재 선택가능한 모든 간선을 대상으로 값들을 합한 것이다.
[9, 10]은 베이스 노드의 이동성이 큰 네트워크 환경에서 사용할 라우팅 방법으로 모든 센서간의 경로 길이가 최소인 최소 Wiener 수 신장트리(MWST) 기반 라우팅 방법을 제시하였다. 모든 센서가 한 번씩 베이스 노드가 되어 다른 센서로부터 동일한 크기의 패킷을 전송 받는 상황인 라운드 패킷 전송 시나리오 등을 사용해 MWST 기반 라우팅 방법과 최소신장트리(MST) 기반의 라우팅 방법을 비교하였다. 이에 따르면 MWST 기반 라우팅 방법은 패킷 전송에 소모되는 에너지의 양이나 패킷의 전송 홉 수면에서 MST 기반라우팅 방법에 비해 좋은 성능을 보였다.
이때 추가하는 노드의 선택은 이미 트리를 형성하고 있는 노드와 그렇지 않은 노드들 사이 중 가장 작은 가중치를 갖는 간선을 끝점으로 하는 정점이 해당된다. 본 논문이 제안하는 방법은 트리 생성을 위한 노드 선택 시 탐욕적인 방법을 사용하는 대신 개미 군집 최적화 알고리즘이 제공하는 확률적인 상태 전이 규칙을 사용한다[16].
50m×50m 공간에 50, 60, 70, 80, 90, 100개의 센서가 임의로 배치된 상황에서 모든 실험이 진행 되었다. 실험의 정확성을 기하기 위하여 10개의 사례를 생성하여 실험한 후 이를 평균하였다.
본 논문은 이동하는 베이스 노드를 가진 센서 네트워크 환경 하에서 실시간 침입탐지를 위해 Wiener 수 신장트리의 장점인 작은 전송 홉 수와 높은 에너지 효율성을 보장하면서 동시에 단점인 짧은 네트워크 수명을 개선하고자 다목적 개미 군집 최적화 알고리즘을 제안한다. 제안하는 개미군집 최적화 알고리즘은 조합 최적화 문제 해결에 사용되는 메타 휴리스틱 알고리즘의 하나로 수백 개의 센서로 구성된 네트워크에도 사용이 가능하다. 제안한 라우팅 방법의 성능을 평가하기 위해 MST 기반 라우팅 방법 및 MWST 기반 라우팅 방법과 라운드 패킷 전송 시나리오를 이용해 평균 홉 수와 에너지 소모량 및 네트워크 수명을 비교한다.
다목적 개미 군집 최적화 알고리즘(MO-ACO)을 사용하려면 문제의 해, 즉 모든 센서를 연결하는 트리를 생성하는 방법이 필요하다. 트리 생성은 최소 신장 트리를 구하는 Prim 알고리즘[19]을 변형한 방법을 사용한다. Prim 알고리즘은 임의 노드를 출발점으로 하여 매번 노드 하나씩을 트리에 추가 시켜 결국 모든 노드를 커버하는 신장트리를 생성해내는 탐욕적(greedy) 알고리즘이다.
특정 센서 네트워크 표준 기술의 하위 계층 프로토콜들의 효과를 차단하고 순수한 토폴로지 효과만을 검증하기 위하여 [9]에서 사용한 모의 실험기(simulator)를 수정하여 제작하였다. 모의 실험기는 네트워크 내의 모든 센서는 동일한 종류를 가정하였다.

데이터처리

제안하는 개미군집 최적화 알고리즘은 조합 최적화 문제 해결에 사용되는 메타 휴리스틱 알고리즘의 하나로 수백 개의 센서로 구성된 네트워크에도 사용이 가능하다. 제안한 라우팅 방법의 성능을 평가하기 위해 MST 기반 라우팅 방법 및 MWST 기반 라우팅 방법과 라운드 패킷 전송 시나리오를 이용해 평균 홉 수와 에너지 소모량 및 네트워크 수명을 비교한다.

이론/모형

본 논문에서 사용하는 패킷 전송 시의 에너지 소비에 대한 모델은 [11]이 제안한 일차 라디오 모델을 사용하였다. 다른 논문[9, 10, 12, 13]들에서도 이 모델을 사용하였으며 통신 모델의 일반적인 가정들을 크게 벗어나지 않기 때문이다.

성능/효과

3은 MST를 이용한 경우와 MSWT를 이용한 경우 및 본 논문이 제안하는 방법(MO-ACO)에 대해서 각각 한 번의 모든 센서간 라운드 패킷 전송 시 패킷의 평균 홉 수를 나타낸 것이다. MST의 경우는 센서 수에 비례하여 평균 홉 수가 증가하는 경향을 보였으며 다른 두 가지 경우보다 훨씬 컸다. 이러한 사실은 MST에 기반한 라우팅 방법들이 패킷 전송에 많은 지연 시간을 요구할 것이라는 사실을 보여준다.
결과적으로 주목해야할 점은 본 논문이 제안하는 트리기반 라우팅 방법이 홉 수나 에너지 효율성에서는 MWST 기반 라우팅 방법과 비슷한 수준을 유지하면서도 단점인 네트워크 수명은 MST 기반 라우팅 방법의 수명 정도를 보장해준다는 사실이다.
본 논문이 제안한 트리에 기반한 라우팅 방법의 경우엔 MST에 기반한 방법과의 차이가 거의 없음을 알 수 있다. 한 가지 유의할 점은 센서수가 많은 경우 세 가지 모두 네트워크의 수명이 수렴하는 경향을 보이고 있으므로 특별히 긴급한 전송 시간을 고려해야하는 응용 서비스의 경우엔 최소 Wiener 수 신장트리 기반 라우팅 방법을 사용할 수 도 있을 것이다.
세 가지 방법 모두 센서 수에 비례해 에너지 소모량이 증가했다. 이 중 MST에 기반한 라우팅 방법의 전력 소비가 가장 컸고 MWST에 기반한 라우팅 방법의 전력 소비가 가장 작았다. MO-ACO에 의한 방법은 MWST에 기반한 방법과 전력 소비 면에서 큰 차이를 보이지 않았다.
모든 센서가 한 번씩 베이스 노드가 되어 다른 센서로부터 동일한 크기의 패킷을 전송 받는 상황인 라운드 패킷 전송 시나리오 등을 사용해 MWST 기반 라우팅 방법과 최소신장트리(MST) 기반의 라우팅 방법을 비교하였다. 이에 따르면 MWST 기반 라우팅 방법은 패킷 전송에 소모되는 에너지의 양이나 패킷의 전송 홉 수면에서 MST 기반라우팅 방법에 비해 좋은 성능을 보였다. 하지만 패킷 전송 시 특정 센서에 대한 의존이 커서 MST에 비해 네트워크 전체의 총 에너지 사용량은 작았음에도 불구하고 특정 센서의 에너지 고갈로 인해 네트워크의 연결이 빨리 끊어진다는 단점을 보여주었다.
많은 수의 센서를 가진 네트워크에도 사용이 가능하며 평균 홉 수나 네트워크 효율성은 MWST기반 라우팅 방법과 비슷한 결과를 보인 반면 네트워크 수명에 있어서는 MST에 기반한 방법과 비슷한 결과를 보였다. 이와 같은 결과는 본 논문이 제시한 라우팅 방법이 이동하는 베이스 노드를 가진 센서 네트워크 환경에서 장시간에 걸쳐 실시간 침입탐지를 보장하는 라우팅 방법으로 적합한 방법임을 보여준 것이다.
이는 동일한 데이터량을 전송하는데 MSWT에 기반한 방법이나 MO-ACO에 의한 방법이 네트워크의 전체 에너지를 적게 소모한다는 사실을 의미한다. 즉 에너지 효율성이 MST 기반 라우팅 방법보다 크다는 사실을 확인할 수 있다. 또한 센서 수가 많아질 수 록 효율성의 차이가 커짐을 확인할 수 있다.
이러한 사실은 MST에 기반한 라우팅 방법들이 패킷 전송에 많은 지연 시간을 요구할 것이라는 사실을 보여준다. 한편 MWST의 경우에 평균 홉 수가 가장 작았지만 MO-ACO의 경우와 큰 차이를 보이지는 않았고 두 경우 모두 센서 수의 증가에 민감하게 반응하지 않음을 확인 할 수 있다. 이러한 실험 결과는 본 논문이 제시하는 MO-ACO에 의한 라우팅 방법이 실시간 침입탐지와 같은 급박한 서비스 제공에 유용하게 사용될 수 있음을 시사한다.

후속연구

앞으로 물리 계층과 MAC 계층을 포함한 보다 현실적인 상황에서의 지연시간 등을 알아보는 실험으로 확대할 계획이다.
한편 MWST의 경우에 평균 홉 수가 가장 작았지만 MO-ACO의 경우와 큰 차이를 보이지는 않았고 두 경우 모두 센서 수의 증가에 민감하게 반응하지 않음을 확인 할 수 있다. 이러한 실험 결과는 본 논문이 제시하는 MO-ACO에 의한 라우팅 방법이 실시간 침입탐지와 같은 급박한 서비스 제공에 유용하게 사용될 수 있음을 시사한다.

질의응답

핵심어	질문	논문에서 추출한 답변
	센서 네트워크를 구성하는 작은 센서들은 어떤 기능을 가지고 있는가?	센서 네트워크를 구성하는 작은 센서들은 빛, 소리, 온도, 이미지, 압력, 진동 등의 다양한 형태의 정보들을 감지하고 감지된 정보들을 특정 목적에 맞게 처리하여 처리된 정보를 베이스 노드까지 전송하는 기능을 가지고 있다. 이러한 센서들 덕분에 센서 네트워크는 국방 영역을 비롯해 환경 감시, 재해 예방, 의료 보건 분야 및 조선, 해양 영역 등 다양한 곳에서 여러 가지 목적으로 사용되고 있다[1-4].
	MWST 기반 라우팅 방법은 어떠한 측면에서 MST 기반 라우팅 방법에 비해 좋은 성능을 보였는가?	모든 센서가 한 번씩 베이스 노드가 되어 다른 센서로부터 동일한 크기의 패킷을 전송 받는 상황인 라운드 패킷 전송 시나리오 등을 사용해 MWST 기반 라우팅 방법과 최소신장트리(MST) 기반의 라우팅 방법을 비교하였다. 이에 따르면 MWST 기반 라우팅 방법은 패킷 전송에 소모되는 에너지의 양이나 패킷의 전송 홉 수면에서 MST 기반라우팅 방법에 비해 좋은 성능을 보였다. 하지만 패킷 전송 시 특정 센서에 대한 의존이 커서 MST에 비해 네트워크 전체의 총 에너지 사용량은 작았음에도 불구하고 특정 센서의 에너지 고갈로 인해 네트워크의 연결이 빨리 끊어진다는 단점을 보여주었다.
	MWST 기반 라우팅 방법은 어떠한 단점이 있는가?	이에 따르면 MWST 기반 라우팅 방법은 패킷 전송에 소모되는 에너지의 양이나 패킷의 전송 홉 수면에서 MST 기반라우팅 방법에 비해 좋은 성능을 보였다. 하지만 패킷 전송 시 특정 센서에 대한 의존이 커서 MST에 비해 네트워크 전체의 총 에너지 사용량은 작았음에도 불구하고 특정 센서의 에너지 고갈로 인해 네트워크의 연결이 빨리 끊어진다는 단점을 보여주었다.

참고문헌 (20)

I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "Wireless sensor networks: a survey," Computer Networks, Vol.38, pp.393-422, 2002.

상세보기
I. F. Akyildiz and I. H. Kasimoglu, "Wireless sensor and actor networks: research challenges," AdHoc Networks, Vol.2, pp.351-367, 2004.

상세보기
I. F. Akyildiz, T. Melodia, and K. R. Chowdhury, "A survey on wireless multimedia sensor networks," Computer Networks, Vol.51, pp.921-960, 2007.

상세보기
D. Ganesan, A. Cerpa, W. Ye, Y. Yu, J. Zhao, and D. Estrin, "Networking Issues in Wireless Sensor Networks," Journal of Parallel and Distributed Computing, Vol.64, pp.799-814, July, 2004.

상세보기
B. Bhuyan, H. K. D. Sarma, N. Sarma, A. Kar, and R. Mall, "Quality of Serivce (QoS) Provisions in Wireless Sensor Networks and Related Challenges," Wireless Sensor Networks, Vol.2, No.11, pp.861-868, 2010.

상세보기
R. S. Dubey, R. Choubey, and A. Dubey, "Challenges for Quality of Service (QoS) in Wireless Sensor Networks," International Journal of Engineering Science and Technology, Vol.2, No.12, pp.7395-7400, 2010.
L. Zhang, J. Yu, and Xiaoheng Deng, "Modelling the guaranteed QoS for wireless sensor networks: a network calculus approach," EURASIP Journal on Wireless Communication and Networking, Vol.82, pp.1-14, 2011.
S. Upadhyayula, S. K. S. Gupta, "Spanning tree based algorithms for low latency and energy efficient data aggregation enhanced convergecast(DAC) in wireless sensor networks," Ad Hoc Networks, Vol.5, pp.626-648, 2007.

상세보기
S. W. Han, I. S. Jeong, and S. H. Kang, "Low latency and energy efficient routing tree for wireless sensor networks with multiple mobile sinks," Journal of Network and Computer Applications, Vol.36, pp.156-166, 2013.

상세보기
S. H. Kang, K. Y. Kim, W. Y. Lee, M. A Jung, and S. R. Lee, "A Branch and Bound Algorithm to Find a Routing Tree Having Minimum Wiener Index in Sensor Networks with High Mobile Base Node," KICS Journal, Vol.35, No.5, pp.466-463, 2010.
W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, "Energy-Efficient Communication Protocol for Wireless Microsensor Networks," in Proceedings of the 33rd Hawaii International Conference on System Sciences, pp.1-10, 2000.
S. H. Kang, M. S. Choi, M. A Jung, and S. R. Lee, "A Pareto Ant Colony Optimization Algorithm for Application-Specific Routing in Wirelss Sensor & Actor Networks," KICS Journal, Vol.36, No.4, pp.346-353, 2011.

원문보기 상세보기
S. Hussain and O. Islam, "An Energy Efficient Spanning Tree Based Multi-hop Routing in Wireless Sensor Networks," in Proceedings of Wireless Communications and Networking Conference, pp.4383-4388, 2007.
M. Tchuente, P. M. Yonta, J. M. Nlong II, and Y. Denneulin, "On the Minimum Average Distance Spanning Tree of the Hypercube," Acta Applicandae Mathematicae, Vol.102, pp.219-236, 2008.

상세보기
S. K. Chaharsooghi, A. H. M. Kermani, "An effective ant colony optimization algorithm (ACO) for multi-objective resource allocation problem (MORAP)," Applied Mathematics and Computation, Vol.200, No.1, pp.167-177, 2008.

상세보기
M. Dorigo and L. M. Gambardella, "Ant colony system: a cooperative learning approach to the traveling salesman problem," IEEE Transactions on Evolutionary Computation, Vol.1, pp.53-66, 1997.

상세보기
M. Dorigo, V. Maniezzo, and A. Colorni, "The ant system: optimization by a colony of cooperating agents," IEEE Transactions on Systems, Man, and Cybernetics - Part B, Vol.26, pp.29-41, 1996.

상세보기
S. Okdem and D. Karaboga, "Routing in Wireless Sensor Networks Using an Ant Colony Optimization Router Chip," Sensors, Vol.9, pp.909-921, Feb., 2009.

상세보기
R. C. Prim, "Shortest connection networks and some generalization," Bell System Technical Journal, Vol.36, pp.1389-1401, 1957.

상세보기
J. C. Kuo and W. Liao, "Hop Count Distribution of Multihop Paths in Wireless Networks With Arbitrary Node Density: Modeling and Its Applications," IEEE Transactions on Vehicular Technology, Vol.56, pp.2321-2331, 2007.

상세보기

표제어: 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

연합인증