[논문]곤충 행동 양식 기반의 애드 혹 네트워크를 위한 존 반경 결정 알고리즘

이혜민; 김동성

doi:10.5302/j.icros.2014.14.8015

[국내논문] 곤충 행동 양식 기반의 애드 혹 네트워크를 위한 존 반경 결정 알고리즘
Insect-Inspired Algorithm for Zone Radius Determination of Ad-hoc Networks 원문보기

제어·로봇·시스템학회 논문지 = Journal of institute of control, robotics and systems, v.20 no.10, 2014년, pp.1079 - 1083

이혜민 (금오공과대학교 전자공학부) , 김동성 (금오공과대학교 전자공학부)

Abstract ▼ AI-Helper

In this paper, a new zone radius determination algorithm is proposed for a nature-inspired routing protocol that emulates the foraging behavior of bees based on their ability to find an optimal route from nectar sites. Instead of changing the radius of nodes one-hop by one-hop, the proposed algorithm alters the radius of nodes as gaps of another radius and adapt quickly to network conditions. The simulation results show that the proposed algorithm has higher efficiency compared with existing studies in an aspect of computational complexity and end-to-end delay.

Keyword

AI 본문요약
AI-Helper

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

문제 정의

본 논문에서는 MANET에서 수렴 시간을 단축시켜 네트워크 연결성을 높이고 계산적인 효율을 높이기 위해 꿀을 찾는 벌의 행동방식을 모방하는 존 반경 결정 알고리즘을 제안한다. 기존의 IZRP 알고리즘은 최소 탐색 방법에 따라 한 홉씩 존 반경을 증가시키기 때문에 새로운 최적의 존 반경을 빠르게 결정 할 수 없어 지연이 길다는 문제점이 있다.
무선 센서 네트워크에서 송신지 노드와 수신지 노드 사이에 라우팅의 성능을 높이기 위해 벌들의 꿀을 찾는 방식에서 착안된 ABC (Artificial Bee Colony) 알고리즘이 연구되었다[9]. 본 연구에서는 이를 수정해 기존의 IZRP에 적용하여 종단 지연을 낮춰 네트워크의 연결성을 높이고자한다.
본 절에서는 꿀벌이 먹이를 찾는 행동을 수학적으로 분석하여 모델링한 ABC 알고리즘을 기존의 존 반경 결정 알고리즘에 적용하고자 한다.
본 논문에서는 벌이 꿀을 찾아다니는 행동을 근거하여 MANET에서 노드의 이동성을 고려하여 효율적인 존 라우팅 결정 알고리즘을 제안하였다. 모의실험 결과에서, 제안된 방법이 기존의 것과 비교하여 MANET에서 계산 복잡성 및 종단 지연 시간의 측면에서 보다 개선됨을 보였다.

가설 설정

존 반경 결정 알고리즘은 현재 IZRP의 트래픽인 Z(ρ)의 입력을 2000에서 20000사이에 균일하게 분포된 함수로 가정했다.

제안 방법

기존의 IZRP 알고리즘은 최소 탐색 방법에 따라 한 홉씩 존 반경을 증가시키기 때문에 새로운 최적의 존 반경을 빠르게 결정 할 수 없어 지연이 길다는 문제점이 있다. 이를 수정한 제시한 알고리즘은 꿀을 찾는 벌에 근거하며 대기벌이 이전의 꿀이 있는 지역을 현재의 지역과 비교하여 꿀의 확보율이 높은 장소로 빠르게 이동하는 행동양식을 IZRP에 반영하였다. 본 논문의 구성은 다음과 같다.
본 절에서 IZRP 알고리즘과 제안된 알고리즘의 입력의 수에 따른 계산 복잡성을 모의실험을 통해 비교하고 그 차이를 증명한다. 그 다음 두 알고리즘의 종단 지연을 비교하여 제안된 알고리즘이 기존의 IZRP 알고리즘 보다 지연이 짧아 효율성이 높음을 보였다.
그림 2는 입력의 수(n)에 따른 기존 알고리즘과 제안된 알고리즘의 계산의 복잡성의 차이를 나타낸다. 특정 CPU clock(Intel Core2Due 2.66GHz(CPU), 2GB(RAM), WindowXP)을 사용하여 도출된 실행 시간에 따라 계산 복잡성을 결정하였다. 이 복잡성은 입력의 수 n과 노드의 존 반경 크기에 따른 제어 트래픽에 따라 변경된다.
또한 존 반경은 MANET에서 이기종간의 중요한 역할을 하며 변화하는 네트워크 상태 변화에 빠르게 적응하게 한다. 그러므로 제안된 알고리즘은 존 반결 결정시 지연을 줄여 라우팅 트래픽을 감소시킨다.

데이터처리

그림 2. IZRP과 제안된 알고리즘의 계산 복잡성 비교.
그림3. 기존의 방법에서 존 반경이 1, 2, 3 일 때와 IZR을 사용 할 때의 평균 종단지연 비교.

성능/효과

게다가 T₁(n)과 T₂(n)의 방정식은 입력 n의 상수 값에 비례하여 상승하게 된다. 입력 n의 상수를 보면, 제안한 알고리즘은 노드에서 많은 양의 패킷을 전송할 때 트래픽을 감소시킨다. 즉 제안한 알고리즘이 존 반경 결정시간을 단축해 준다는 것을 식 (5)를 통해 알 수 있다.
본 절에서 IZRP 알고리즘과 제안된 알고리즘의 입력의 수에 따른 계산 복잡성을 모의실험을 통해 비교하고 그 차이를 증명한다. 그 다음 두 알고리즘의 종단 지연을 비교하여 제안된 알고리즘이 기존의 IZRP 알고리즘 보다 지연이 짧아 효율성이 높음을 보였다.
이 복잡성은 입력의 수 n과 노드의 존 반경 크기에 따른 제어 트래픽에 따라 변경된다. 알고리즘 2에서 인접한 노드에서 홉의 수가 URM/DRM을 통하여 직접적으로 변경될 때 최적의 존 반경을 찾기 위한 시간이 현저히 감소된다. 입력의 수 n이 2000일 때 IZRP보다 10%정도 복잡성가 낮고 n=10,000일 때 20%, n=20,000일 때 23%의 개선을 보여 지연을 줄였다.
알고리즘 2에서 인접한 노드에서 홉의 수가 URM/DRM을 통하여 직접적으로 변경될 때 최적의 존 반경을 찾기 위한 시간이 현저히 감소된다. 입력의 수 n이 2000일 때 IZRP보다 10%정도 복잡성가 낮고 n=10,000일 때 20%, n=20,000일 때 23%의 개선을 보여 지연을 줄였다.
존 반경이 1에서부터 3으로 변할 때의 그래프를 보면 노드의 수가 증가함에 따라 존 반경이 큰 경우, 지연 시간이 감소됨을 알 수 있다. 그리하여 IZR을 사용하여 존 반경을 설정한 경우 우수한 성능을 보였다.
본 논문에서는 벌이 꿀을 찾아다니는 행동을 근거하여 MANET에서 노드의 이동성을 고려하여 효율적인 존 라우팅 결정 알고리즘을 제안하였다. 모의실험 결과에서, 제안된 방법이 기존의 것과 비교하여 MANET에서 계산 복잡성 및 종단 지연 시간의 측면에서 보다 개선됨을 보였다.

후속연구

향후 연구 방향은 대규모의 무선 애드 혹 네트워크에서 네트워크 연결성을 더욱 증가시킬 수 있는 방법에 대해 연구할 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	애드 혹 통신의 네트워크 환경의 문제점은 무엇인가?	애드 혹 통신의 네트워크 환경은 존 반경안의 노드들의 수가 빈번하게 바뀜에 따라 불안정성을 보인다. 이러한 문제점들을 고려해 존 라우팅 프로토콜의 효율성을 개선시키기 위한 방안으로 독립적인 존 라우팅 프로토콜 IZRP(Independent Zone Routing Protocol)이 연구되었다[6].
	기존의 IZRP 알고리즘의 문제점은 무엇인가?	본 논문에서는 MANET에서 수렴 시간을 단축시켜 네트워크 연결성을 높이고 계산적인 효율을 높이기 위해 꿀을 찾는 벌의 행동방식을 모방하는 존 반경 결정 알고리즘을 제안한다. 기존의 IZRP 알고리즘은 최소 탐색 방법에 따라한 홉씩 존 반경을 증가시키기 때문에 새로운 최적의 존 반경을 빠르게 결정 할 수 없어 지연이 길다는 문제점이 있다. 이를 수정한 제시한 알고리즘은 꿀을 찾는 벌에 근거하며 대기벌이 이전의 꿀이 있는 지역을 현재의 지역과 비교하여 꿀의 확보율이 높은 장소로 빠르게 이동하는 행동양식을 IZRP에 반영하였다.
	ABC 알고리즘에서 벌은 단계별로 어떤 행동을 하는가?	전형적으로 ABC 알고리즘에서 벌의 행동은 그림 1과 같이 세 단계로 나뉜다. 1단계에서 일벌은 꿀이 있는 지역의 확보율을 계산하기 위해 채집 장소로 이동하여 꿀을 발견하면 8자춤(waggle dance)을 춘다[10]. 이를 발견한 대기벌은 2단계에서 보이는 것과 같이 일벌을 따라 8자춤을 춘다. 이때 8자춤의 진동수가 높으면 높을수록 꿀 확보율이 높은 지역을 뜻한다. 마지막 3단계에서, 대다수의 대기벌이 진동수가 더 높은 춤을 추는 일벌들을 따라 춘다. 이후 일벌은 탐색벌이 되어 더 꿀 확보율이 좋은 장소를 탐색하기 위해 이동한다.

참고문헌 (11)

T.-L. Pham and D.-S. Kim, "Routing protocol over lossy links for ISA100.11a industrial wireless sensor networks," Wireless Networks, pp. 1-12, 2014.
T. T. Le and D.-S. Kim, "An efficient throughput improvement through bandwidth awareness in cognitive radio networks," Journal of Communications and Networks (JCN), vol. 16, no. 2, pp. 146-154, 2014.

원문보기 상세보기
T. T. Le, P. T. A. Quang, S. Y. Shin, and D.-S. Kim, "BAR: Bandwidth-Aware opportunistic localized-routing for cognitive radio networks," GC12 WS MIMOCR, pp. 937-942, Dec. 2012.
T. M. Phuong and D.-S. Kim, "Efficient power control scheme for cognitive industrial sensor networks," International Journal of Control and Automation (IJCA), vol. 7, no. 3, pp. 177-188, 2014.
D. D. Tan and D.-S. Kim, "Dynamic traffic-aware routing algorithm for multi-sink wireless sensor networks," Wireless Networks, vol. 19, no. 8, 2013.
P. Samar, M. Pearlman, and Z. Haas, "Independent zone routing: an adaptive hybrid routing framework for ad hoc wireless networks," IEEE/ACM Transactions on Networking, vol. 12, no. 4, pp. 595-608, Aug. 2004.

상세보기
M. Pearlman and Z. Haas, "Determining the optimal configuration for the zone routing protocol," IEEE Journal on Selected Areas in Communications, vol. 17, no. 8, pp. 1395-1414, Aug. 1999.

상세보기
D. Ravilla, V. Sumalatha, and P. C. S. Reddy, "Performance comparisons of ZRP and IZRP routing protocols for Ad hoc Wireless Networks," International Conference on Energy, Automation and Signal, pp. 1-8, Dec. 2011.
D. Karaboga, "An idea based on honey bee swarm for numerical optimization," Technical Report, Oct. 2005.
T. D. Seeley, "Honeybee Democracy," Princeton University Press, pp. 280-288, 2010.
H. M. Lee, D.-S. Kim, "nsect-Inspired Algorithm for Zone Radius Determination in Independent Zone Routing Protocol," Proc. of 2014 29th ICROS Annual Conference (ICROS 2014) (in Korean), Daegu, Korea, pp. 25-26 Jun. 2014.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

[국내논문] 곤충 행동 양식 기반의 애드 혹 네트워크를 위한 존 반경 결정 알고리즘
Insect-Inspired Algorithm for Zone Radius Determination of Ad-hoc Networks 원문보기

Abstract ▼ AI-Helper

Keyword

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

데이터처리

성능/효과

후속연구

질의응답

참고문헌 (11)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

[국내논문] 곤충 행동 양식 기반의 애드 혹 네트워크를 위한 존 반경 결정 알고리즘 Insect-Inspired Algorithm for Zone Radius Determination of Ad-hoc Networks 원문보기

Abstract ▼ AI-Helper

Keyword

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

데이터처리

성능/효과

후속연구

질의응답

참고문헌 (11)

이 논문을 인용한 문헌

저자의 다른 논문 :

김동성 (35)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

[국내논문] 곤충 행동 양식 기반의 애드 혹 네트워크를 위한 존 반경 결정 알고리즘
Insect-Inspired Algorithm for Zone Radius Determination of Ad-hoc Networks 원문보기

AI 본문요약
AI-Helper