[논문]위치 정보를 이용한 개미 집단 시스템 기반의 무선 센서 네트워크 라우팅 알고리즘 구현

전혜경; 한승진; 정경용; 임기욱; 이정현

doi:10.5392/jkca.2011.11.6.051

위치 정보를 이용한 개미 집단 시스템 기반의 무선 센서 네트워크 라우팅 알고리즘 구현
Implementation of ACS-based Wireless Sensor Network Routing Algorithm using Location Information 원문보기

한국콘텐츠학회논문지 = The Journal of the Korea Contents Association, v.11 no.6, 2011년, pp.51 - 58

전혜경 (인하대학교 컴퓨터정보공학과) , 한승진 (경인여자대학교 정보미디어학부) , 정경용 (상지대학교 컴퓨터정보공학부) , 임기욱 (선문대학교 컴퓨터정보공학부) , 이정현 (인하대학교 컴퓨터정보공학과)

초록
AI-Helper

무선 센서 네트워크의 라우팅 기술은 제한된 에너지를 갖고 있는 센서 노드들의 에너지 수명을 최대한으로 연장할 수 있는 방법으로 많이 연구되고 있다. 기본 라우팅 방법 중 위치 정보를 이용한 라우팅 방법은 라우팅 설정을 위한 계산시에 필요한 정보의 양이 평면, 계층적 라우팅 방법보다 적기 때문에 효율적이다. 하지만 주로 거리를 활용하기 때문에 센서 노드의 에너지 활용도가 떨어질 수도 있다. 본 논문에서는 최적의 경로 탐색에 많이 이용되고 있는 개미 집단 시스템(ACS : Ant Colony System)의 전이 확률에 센서의 에너지양과 싱크와의 거리를 이용한 가중치를 부여하여 무선 센서 네트워크의 에너지 사용량을 고르게 사용할 수 있게 하였다. 제안된 방법은 대표적인 GPSR(Greedy Perimeter Stateless Routing)과 비교하여 에너지 사용도에 있어 평균적으로 46.80%의 향상을 보였으며, 기존의 ACS보다 동일한 시간의 수행 종료 후 잔여 에너지가 평균 6.7% 더 남아 있음을 확인하였다.

Abstract ▼ AI-Helper

One of the objectives of research on routing methods in wireless sensor networks is maximizing the energy life of sensor nodes that have limited energy. In this study, we tried to even energy use in a wireless sensor network by giving a weight to the transition probability of ACS(Ant Colony System), which is commonly used to find the optimal path, based on the amount of energy in a sensor and the distance of the sensor from the sink. The proposed method showed improvement by 46.80% on the average in energy utility in comparison with representative routing method GPSR (Greedy Perimeter Stateless Routing), and its residual energy after operation for a specific length of time was 6.7% more on the average than that in ACS.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문에서는 여러 라우팅 방법 중 소스 노드와 이웃하고 있는 이웃 노드와 싱크와의 거리가 가장 가까운 노드를 선택하는 위치 기반 라우팅을 변형하는 방법[5]과 최적의 해를 찾는 휴리스틱 기법 중에 하나인 개미 집단 시스템(Ant Colony System)[15]을 이용한 무선 센서 네트워크 라우팅 알고리즘을 제안한다. 개미 집단 시스템은 선행 개미가 선택한 경로에 페르몬의 양을 증가 시켜 다음 후행 개미가 최적의 경로를 선택하도록 하는 알고리즘이다[15].
본 논문에서는 위치 기반 라우팅에서 필요한 주변노드의 위치 정보와 개미 집단 시스템에서 사용하는 전이 확률을 이용하여 주변노드 중 라우팅에 참여할 다음 노드를 선택하여 최적의 경로를 구하는 라우팅 방법을 제안한다. 제안 방법을 통해 기존의 전이확률에서 사용되던 거리 파라미터를 센서 노드의 에너지양으로 적용하고 싱크와 주변 노드의 거리를 이용해 가중치를 두어 센서 노드의 잔여 에너지양을 효율적으로 관리하여 전체 네트워크 수명의 연장을 보인다.
본 논문에서는 전이확률 계산시 노드 위치에 따른 가중치를 추가한다. 가중치를 추가하는 이유는 현재 노드의 이웃노드들과 싱크와의 거리를 계산하여 거리에 대한 파라미터를 넣어 최적의 해를 찾기 위함이다.
본 논문은 위치 정보와 개미 집단 시스템의 페르몬양, 전이확률 등의 휴리스틱한 정보를 통해 최적의 경로를 찾는 방법을 제안하였다. 제안 방법은 위치인식 기반 라우팅의 빠른 에너지 고갈 문제를 해결하고 싱크를 향한 방향성을 고려하여 최적의 경로를 네트워크 전반에 걸쳐 고르게 검색하였다.

가설 설정

반경은 20m 로 설정한다. 각 노드는 싱크의 값을 알고 있고, 노드의 위치는 GPS로 알 수 있다고 가정한다. 또한 싱크 노드의 에너지양은 무한대로 설정한다.

제안 방법

우선 위치기반 프로토콜중 대표적인 GPSR과 제안방법을 비교하고, 개미 집단 알고리즘과 제안 방법을 비교한다. GPSR과 제안 방법은 네트워크를 구성하는 센서 중 잔여 에너지의 양이 0 이하가 되면 네트워크의 수명이 종료되는 것으로 실험한다. 개미집단시스템과 제안 방법은 동일한 시간동안 패킷 전송을 수행한 후 남아 있는 잔여 에너지의 양을 측정 비교한다.
GPSR과 제안 방법은 네트워크를 구성하는 센서 중 잔여 에너지의 양이 0 이하가 되면 네트워크의 수명이 종료되는 것으로 실험한다. 개미집단시스템과 제안 방법은 동일한 시간동안 패킷 전송을 수행한 후 남아 있는 잔여 에너지의 양을 측정 비교한다. 실험을 위한 하드웨어 사양은 CPU는 Intel Core2 Duo 1.
개미 집단 시스템에서는 지역 갱신과 전역 갱신을 모두 수행한다. 본 논문에서도 지역갱신과 전역갱신을 수행하여 에너지 홀에 빠지지 않도록 한다. 지역 갱신의경우 아래와 같이 값을 변경시킨다.
또한 싱크 노드의 에너지양은 무한대로 설정한다. 실험은 제안방법과 ACS의 경우 일정한 시간 동안 수행후의 잔여 에너지양을 비교하였고, GPSR의 경우 잔여 에너지의 양이 0 보다 작은 경우가 발생하면 수행 후 멈춘후 잔여 에너지 양을 비교해 보았다.
본 논문에서는 제안된 알고리즘의 성능을 비교하기 위해서 다음과 같이 실험한다. 우선 위치기반 프로토콜중 대표적인 GPSR과 제안방법을 비교하고, 개미 집단 알고리즘과 제안 방법을 비교한다. GPSR과 제안 방법은 네트워크를 구성하는 센서 중 잔여 에너지의 양이 0 이하가 되면 네트워크의 수명이 종료되는 것으로 실험한다.
임계치는 경로상에 있는 노드들의 평균 페르몬 양을 구한 후 초기값 1을 뺀다. 이 값을 데이터 전송에 소비되는 에너지 양에 라우팅 경로 길이를 곱한 값과 비교한 후 더 크면 전역 갱신을 수행한다. 전역 갱신을 위한 페르몬 갱신식은 아래와 같다.
이 장에서는 개미 알고리즘을 기본으로 한 센서 네트워크에서의 에너지 효율적인 라우팅 경로 설정에 대한 방법을 제안한다. 제안하는 알고리즘은 다음 노드를 선택할 때 이웃 노드에 패킷을 전송할 때의 에너지 비용 (Energy Cost)을 구하고, 이 에너지 비용을 개미 집단 최적화 알고리즘의 전이확률에 이용한다[13].
본 논문은 위치 정보와 개미 집단 시스템의 페르몬양, 전이확률 등의 휴리스틱한 정보를 통해 최적의 경로를 찾는 방법을 제안하였다. 제안 방법은 위치인식 기반 라우팅의 빠른 에너지 고갈 문제를 해결하고 싱크를 향한 방향성을 고려하여 최적의 경로를 네트워크 전반에 걸쳐 고르게 검색하였다. 실험 결과 제안 방법은 기존의 방법에 비해 에너지 사용도에 있어서 46.
하지만 싱크를 향해서 라우팅하는 것이 아니기 때문에 라우팅이 싱크 방향과 상관없이 라우팅되는 모습을 볼 수 있다. 제안된 방법은 전체적으로 라우팅을 고르게 하고 있고 싱크를 향해서 라우팅하는 모습을 살펴 볼 수 있다. GPSR의 경우는 라우팅 방향이 무조건 싱크를 향하고 있지만 거리만을 가지고 최적의 경로를 찾기 때문에 해당 경로만으로 패킷을 전송할 경우 에너지 소비가 빨리 일어나므로 고른 라우팅을 하지 못하는 모습을 볼 수 있다.
제안방법에서는 기존의 1/dij는 에너지 비용인 ECostij로 가중치 ωi를 추가하여 전이 확률을 변경하여 향상된 알고리즘을 제공한다.
이 장에서는 개미 알고리즘을 기본으로 한 센서 네트워크에서의 에너지 효율적인 라우팅 경로 설정에 대한 방법을 제안한다. 제안하는 알고리즘은 다음 노드를 선택할 때 이웃 노드에 패킷을 전송할 때의 에너지 비용 (Energy Cost)을 구하고, 이 에너지 비용을 개미 집단 최적화 알고리즘의 전이확률에 이용한다[13]. 아래 식 (1)은 에너지 비용을 계산하기 위한 수식이다.

데이터처리

위치 기반 라우팅 중 제안된 여러 가지 방법 중 논문에서는 GPSR(Greedy Perimeter Stateless Routing)[5]와 제안된 방법을 비교 분석한다. GPSR은 목적지 노드의 라우팅을 위하여 패킷을 수신한 이웃 노드의 위치와 패킷의 목적지 정보를 사용하여 점진적으로 패킷의 포워딩을 결정하는 Greedy 포워딩 방법을 사용하는 알고리즘이다[5].

성능/효과

제안 방법은 위치인식 기반 라우팅의 빠른 에너지 고갈 문제를 해결하고 싱크를 향한 방향성을 고려하여 최적의 경로를 네트워크 전반에 걸쳐 고르게 검색하였다. 실험 결과 제안 방법은 기존의 방법에 비해 에너지 사용도에 있어서 46.80%, 동일 시간 경로 탐색 및 데이터 전송 후 잔여 에너지의 양이 기존의 방법에 비해 6.7% 향상됨을 보였다.
본 논문에서는 위치 기반 라우팅에서 필요한 주변노드의 위치 정보와 개미 집단 시스템에서 사용하는 전이 확률을 이용하여 주변노드 중 라우팅에 참여할 다음 노드를 선택하여 최적의 경로를 구하는 라우팅 방법을 제안한다. 제안 방법을 통해 기존의 전이확률에서 사용되던 거리 파라미터를 센서 노드의 에너지양으로 적용하고 싱크와 주변 노드의 거리를 이용해 가중치를 두어 센서 노드의 잔여 에너지양을 효율적으로 관리하여 전체 네트워크 수명의 연장을 보인다.

후속연구

향후 연구 과제로는 고정된 싱크 노드를 이동 싱크 노드로 바꾼 상태에서 에너지 효율성에 대해 알아 보도록 하고, 제안된 방법에 암호화 기법을 적용하여 외부 공격에 좀더 강건한 네트워크 구축하는 연구를 할 예정이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	무선 센서 네트워크를 많이 사용하게된 배경은 무엇인가?	최근 반도체, 나노 기술, 미세 센서 장치, 무선 기술의 발달로 주변 환경을 감시하고, 데이터를 수집하는 용도로 무선 센서 네트워크가 많이 이용되고 있다. 무선 센서 네트워크의 응용은 주로 인간이 직접적으로 장기간 관찰이 어려운 지역에 대한 감시, 예를 들면 전쟁지역이나 야생 동물들의 서식 지역, 자연 재해 감시등이 주된 응용 환경이 된다[1-3].
	무선 센서 네트워크롤 응용되는 것은 무엇인가?	최근 반도체, 나노 기술, 미세 센서 장치, 무선 기술의 발달로 주변 환경을 감시하고, 데이터를 수집하는 용도로 무선 센서 네트워크가 많이 이용되고 있다. 무선 센서 네트워크의 응용은 주로 인간이 직접적으로 장기간 관찰이 어려운 지역에 대한 감시, 예를 들면 전쟁지역이나 야생 동물들의 서식 지역, 자연 재해 감시등이 주된 응용 환경이 된다[1-3]. 이러한 환경에 센서 노드들은 적게는 수십개에서 많게는 수만개가 분포된다.
	위치 정보와 개미 집단 시스템의 페르몬양, 전이확률 등의 휴리스틱한 정보를 통해 최적의 경로를 찾는 방법을 제안한 결과는 무엇인가?	제안 방법은 위치인식 기반 라우팅의 빠른 에너지 고갈 문제를 해결하고 싱크를 향한 방향성을 고려하여 최적의 경로를 네트워크 전반에 걸쳐 고르게 검색하였다. 실험 결과 제안 방법은 기존의 방법에 비해 에너지 사용도에 있어서 46.80%, 동일 시간 경로 탐색 및 데이터 전송 후 잔여 에너지의 양이 기존의 방법에 비해 6.7% 향상됨을 보였다.

참고문헌 (18)

I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "A survey on sensor networks," IEEE Communications Magazine, Vol.40, pp.102-114, 2002.

상세보기
G. Anastasi, M. Conti, M. Francesco, and A. Passarella, "Energy conservation in wireless sensor networks: A survey," Ad Hoc Networks, Vol.7, No.3, pp.537-568, 2009.

상세보기
R. Szewczyk, E. Osterwil, J. Polastre, and M. Hamilton, "A Mainwaring Habitat Monitoring With Sensor Networks," Communications of the ACM Vol.47, No.6, pp.34-40, 2004.
B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris, "Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks," Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking, 2001(7).
B. Karp and H. T. Kung, "Greedy perimeter stateless forwarding for wireless networks," Proceedings of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking(MobiCom '00), pp.243-254, Boston, MA., 2000(8).
http://www.inf.ethz.ch/-kasten/research/bathtub/energy_consumption.html, 2001.
M. Stemm and R. H. Katz, "Measuring and reducing energy consumption of network interfaces in hand-held devices," IEICE Transactions on Communications, E80-B, No.8, pp.1125-1131, 1997(8).
K. Sohrabi, Protocols for self-organization of a wireless sensor network, IEEE Personal Communications Vol.7, No.5, pp.16-27, 2000.

상세보기
M. Younis, M. Youssef, and K. Arisha, Energy-aware routing in cluster-based sensor networks, in: Proceedings of the 10th IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS2002), Fort Worth, TX, 2002(10).
C. Schurgers and M. B. Srivastava, Energy efficient routing in wireless sensor networks, in: The MILCOM Proceedings on Communications for Network-Centric Operations:Creating the Information Force, McLean, VA, 2001.
Y. Xu, J. Heidemann and D. Estrin, "Geography-informed energy conservation for ad-hoc routing," Proceedings of 7th Annual ACM/IEEE International Conference on Mobile Computing and Networking(MobiCom '01), pp.70-84, Rome, Italy, 2001(7).
Xin Liu, Q. Huang, and Ying Zhang, "Comb, needles, haystacks:balancing push and pull for discovery in large-scale sensor network," Sensys '04, 2004.
L. M. Gambardella and M. Dorigo, "Ant Colony System: A Cooperative Learning approach to the Traveling Salesman Problem," IEEE Transactions on Evoutionery Computation, Vol.1, No.1, 1997.
T. Rappaort, Wireless Communications: Principle & Practice, Englewood Cliffs, NJ: Prentice-Hall, 1996.
S. Funke, "Topological Hole Detection in Wireless Sensor Networks and its Applications," Workshop on Discrete Algorithms and Methods for MOBILE Computing and Communications, pp.44-53, 2005.
M. Dorigo and C. Blum, "Ant colony optimization theory:A survey"
M. Dorigo, V. Maniezzo, and A. Colorni, "Positive FeedBack as a search strategy," Report No. 91-106, Laboratorio di Calcolatori, Dipartimento di Elettronica, Milano, Italy, 1991.
B. Bullnheimer, R. F. Hartel, and C. Straub, "A New Rank Based Version of the Ant System - A Computational Study," Working Paper No.1, Department of Management of Science, University of Vienna, 1997(4).

저자의 다른 논문 :

LOADING...

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

연합인증