무선 센서 네트워크에서 데이터의 종류에 따른 QoS를 보장하기 위한 Node-disjoint 멀티 패스 라우팅 알고리즘
An Optimized QoS Node-disjoint Multipath Routing Algorithm Suitable for Data Type over Wireless Sensor Network
초록/요약
최근 들어 무선 센서 네트워크에 대한 관심이 높아지면서 수 많은 곳에서 연구가 이루어지고 있다. 무선 센서 네트워크는 적은 비용, 낮은 처리 성능, 낮은 전송 속도의 특징을 가지며 수 많은 센서 노드들로 이루어진 네트워크이다. 무선 센서 네트워크는 무선 애드혹 네트워크를 기반으로 발전된 네트워크로서 Point-to-Point 연결 기반의 무선 애드혹 네트워크와 달리 브로드 캐스트 기반의 통신 방법을 사용한다. 무선 센서 네트워크 분야에서 다양한 연구가 진행되어 왔지만 그 중에서 라우팅 알고리즘과 관련한 연구가 가장 활발히 이루어지고 있으며 기존의 라우팅 알고리즘 연구는 주로 싱글 패스 기반의 라우팅 프로토콜 위주로 연구가 진행되어왔다. 그러나 최근 들어 무선 센서 네트워크를 통해 비교적 큰 용량의 데이터를 전송하려는 시도가 실시되면서 멀티 패스 기반의 라우팅 알고리즘에 대한 연구가 새롭게 떠오르고 있다. 더불어 기존의 무선 네트워크에서 데이터 전송 시 QoS를 보장하기 위한 라우팅 알고리즘이 연구되어 오던 것이 발전되어 무선 센서 네트워크에서 데이터 전송 시 QoS를 보장하기 위한 라우팅 알고리즘이 새롭게 시도되고 있다. 따라서 본 논문에서는 무선 센서 네트워크에서 멀티 패스 기반의 라우팅 알고리즘을 제안한다. 멀티 패스 라우팅 알고리즘은 크게 Link-disjoint 멀티 패스 라우팅 알고리즘과 Node-disjoint 멀티 패스 라우팅 알고리즘이 있는데, 그 중에서 Node-disjoint 멀티 패스 라우팅 알고리즘을 본 논문에서는 제안한다. 더불어 Node-disjoint 멀티 패스 라우팅 알고리즘에 데이터 전송 시 QoS를 보장하기 위한 방법을 적용한 새로운 Node-disjoint QoS 멀티 패스 라우팅 알고리즘을 제안한다. 이어서 본 논문에서 제안하는 Node-disjoint QoS 멀티 패스 라우팅 알고리즘을 이용하였을 때 어떤 성능을 보이는지, 기존의 Node-disjoint 멀티 패스 라우팅 알고리즘과 비교하여 어느 정도의 성능 향상을 보이는지 알아본다.
more목차
감사의 글 .................................................................................................................. i
논문 요약 ................................................................................................................ iii
본문 차례 ................................................................................................................ iv
그림 차례 ................................................................................................................. v
서론 ........................................................................................................................... 1
본론 ........................................................................................................................... 6
I. 배경 연구 ............................................................................................................. 6
1. 라우팅 프로토콜의 종류 ........................................................................... 6
II. 기존 연구의 문제점 .......................................................................................... 7
1. 싱글 패스 라우팅 프로토콜의 문제점 ................................................... 8
2. 멀티 패스 라우팅 프로토콜의 필요성 ................................................. 13
3. 멀티 패스 라우팅 프로토콜의 종류 및 특징 ..................................... 15
III. 제안 알고리즘 ................................................................................................. 21
1. 개선된 Node-disjoint 멀티 패스 라우팅 알고리즘 ............................. 21
A. 노드 ID 리스트를 이용한 경로 탐색 방법 ................................ 22
B. 라우팅 오버헤드 감소 방법 .......................................................... 23
C. Node-disjoint 경로 선택 방법 ......................................................... 25
D. 목적지 노드의 Node-disjoint 경로 선택 방법 ............................ 26
E. RREP 메시지의 전송 및 경로 설정 방법 ................................... 27
2. QoS 라우팅을 적용한 Node-disjoint 멀티 패스 라우팅 알고리즘 ... 29
A. QoS 정보 수집을 통한 경로 탐색 알고리즘 .............................. 32
B. 목적지 노드에서 최종 경로를 선택하는 알고리즘 .................. 37
IV. 실험 및 분석 ................................................................................................... 44
결론 ......................................................................................................................... 48
참고문헌 ................................................................................................................. 49
목차
그림 1. 무선 센서 네트워크의 적용 예 - Great Duck Island ........................... 1
그림 2. 무선 센서 네트워크의 적용 예 - Great Duck Island ........................... 2
그림 3. 무선 센서 네트워크의 적용 예 - Health Care ..................................... 3
그림 4. 무선 센서 네트워크의 적용 예 - Tactical Sensor Network ................. 4
그림 5. Ad hoc 네트워크의 종류 .......................................................................... 6
그림 6. 싱글 패스 라우팅의 예 ........................................................................... 8
그림 7. 멀티 패스 라우팅의 예 ......................................................................... 14
그림 8. 멀티 패스 라우팅 프로토콜의 종류 ................................................... 15
그림 9. Link-disjoint 멀티 패스 ........................................................................... 16
그림 10. Node-disjoint 멀티 패스 ........................................................................ 17
그림 11. 멀티 패스 라우팅을 이용한 데이터 전송의 예 - 중복 전송 ...... 18
그림 12. 멀티 패스 라우팅을 이용한 데이터 전송의 예 - 분할 전송...... 18
그림 13. 대체 경로 설정 과정 - 초기 상태 ................................................... 20
그림 14. 대체 경로 설정 과정 - 경로 단절 ................................................... 20
그림 15. 대체 경로 설정 과정 - 경로 재 설정 ............................................. 21
그림 16. RREQ 메시지 전송 과정 ..................................................................... 23
그림 17. RREQ 메시지 전송 중 Node-disjoint 여부 확인 ............................. 25
그림 18. 목적지 노드에서의 Node-disjoint 경로 선택 과정 ......................... 26
그림 19. RREP 메시지 전송 과정 ...................................................................... 28
그림 20. Node-disjoint 멀태 패스 라우팅 테이블 ............................................ 28
그림 21. RREQ 메시지 헤더 ............................................................................... 33
그림 22. 중간 노드들의 라우팅 테이블 ........................................................... 33
그림 23. 소스 노드의 동작 알고리즘 ............................................................... 34
그림 24. RREQ 메시지 추가 정보 ..................................................................... 35
그림 25. 중간 노드의 동작 알고리즘 ............................................................... 37
그림 26. 멀티 패스를 통한 멀티미디어 데이터 전송 방법 ......................... 39
그림 27. 멀티 패스를 통한 멀티미디어 데이터 전송 방법 ......................... 39
그림 28. 목적지 노드의 동작 알고리즘 – 전체 ............................................. 40
그림 29. 목적지 노드의 동작 알고리즘 – 멀티미디어 데이터 ................... 41
그림 30. 목적지 노드의 동작 알고리즘 – 바이너리 데이터 ....................... 42
그림 31. 목적지 노드의 동작 알고리즘 – 스칼라 데이터 ........................... 43
그림 32. 실험 토폴로지 ....................................................................................... 44
그림 33. 결과 1 – 데이터 전송 지연 ................................................................ 45
그림 34. 결과 2 – 데이터 전송에 걸린 시간 .................................................. 46
그림 35. 결과 3 – 데이터 전송률 ...................................................................... 47
