UWB 애드 혹 네트워크에서의 TCP 성능 향상을 위한위치 기반 라우팅 방법(Method for Location-Aided Routing with High TCPThroughput in Ultra Wideband Ad-Hoc Network)

(19)대한민국특허청(KR)
(12) 등록특허공보(B1)

(51) 。Int. Cl.
H04L 12/28 (2006.01)
H04L 29/06 (2006.01)
(45) 공고일자
(11) 등록번호
(24) 등록일자
2007년03월14일
10-0695104
2007년03월08일
(21) 출원번호 10-2006-0010902 (65) 공개번호
(22) 출원일자 2006년02월04일 (43) 공개일자
심사청구일자 2006년02월04일
(73) 특허권자 에스케이 텔레콤주식회사
서울 중구 을지로2가 11번지
(72) 발명자 신용식
서울 강서구 등촌3동 등촌 주공아파트 505-508
박용길
경기도 성남시 분당구 서현동 효자촌동아아파트 203-1503호
김성근
서울 양천구 목6동 목동6단지아파트 601-201
오세현
서울 강남구 대치동 503 개포1차아파트 9-1202
이명성
서울 강남구 도곡동 964번지 현대그린아파트 1605호
(74) 대리인 김성남
(56) 선행기술조사문헌
WO 2005/062553 등록특허공보 10-6644535
* 심사관에 의하여 인용된 문헌
심사관 : 정해양
전체 청구항 수 : 총 8 항
(54) ＵＷＢ 애드 혹 네트워크에서의 ＴＣＰ 성능 향상을 위한위치 기반 라우팅 방법
(57) 요약
본 발명은 UWB 애드 혹 네트워크에서의 TCP 성능 향상을 위한 위치 기반 라우팅 방법에 관한 것이다.
본 발명의 UWB 애드 혹 네트워크에서의 TCP 성능 향상을 위한 위치 기반 라우팅 방법은, (A) 상기 UWB 애드 혹 네트워
크 상의 각 노드가 주기적으로 네트워크 상의 모든 노드에 대하여 TCP 효율이 최대가 되는 최소 손실 라우팅 경로를 탐색
하고, 탐색된 라우팅 경로를 이용하여 라우팅 테이블을 생성하여 유지하는 단계와; (B) 패킷 전송 이벤트가 발생된 노드가,
등록특허 10-0695104
- 1 -
자신 노드로부터 목적지 노드까지의 거리(D)가 자신의 최적 전송 거리인 임계치 거리(F) 이하인지를 판단하는 단계와; (C)
상기 판단 결과, 자신 노드로부터 목적지 노드까지의 거리(D)가 자신의 임계치 거리(F)를 초과하는 경우, 상기 자신 노드가
자신이 유지하고 있는 상기 라우팅 테이블에서 상기 목적지 노드로의 최소 손실 경로를 찾고, 자신 노드로부터 목적지 노
드까지의 거리(D)가 자신의 임계치 거리(F) 이하인 경우, 상기 자신 노드는 상기 목적지 노드로 직접 패킷을 전송하는 단
계; 를 포함함에 기술적 특징이 있다.
대표도
도 6
특허청구의 범위
청구항 1.
UWB 애드 혹 네트워크에서의 TCP 성능 향상을 위한 위치 기반 라우팅 방법으로서,
(A) 상기 UWB 애드 혹 네트워크 상의 각 노드가 주기적으로 네트워크 상의 모든 노드에 대하여 TCP 효율이 최대가 되는
최소 손실 라우팅 경로를 탐색하고, 탐색된 라우팅 경로를 이용하여 라우팅 테이블을 생성하여 유지하는 단계와;
(B) 패킷 전송 이벤트가 발생된 노드가, 자신 노드로부터 목적지 노드까지의 거리(D)가 자신의 최적 전송 거리인 임계치
거리(F) 이하인지를 판단하는 단계와;
(C) 상기 판단 결과, 자신 노드로부터 목적지 노드까지의 거리(D)가 자신의 임계치 거리(F)를 초과하는 경우, 상기 자신 노
드가 자신이 유지하고 있는 상기 라우팅 테이블에서 상기 목적지 노드로의 최소 손실 경로를 찾고, 자신 노드로부터 목적
지 노드까지의 거리(D)가 자신의 임계치 거리(F) 이하인 경우, 상기 자신 노드는 상기 목적지 노드로 직접 패킷을 전송하는
단계;
를 포함하는 것을 특징으로 하는 UWB 애드 혹 네트워크에서의 TCP 성능 향상을 위한 위치 기반 라우팅 방법.
청구항 2.
제1항에 있어서,
상기 제(A)단계는,
(a) 각 노드가 주기적으로 UWB 애드 혹 네트워크 상의 모든 노드들의 위치를 측정하는 단계와;
(b) 각 노드가 상기 측정된 위치를 이용하여 최소 손실 라우팅 경로를 탐색하여 라우팅 테이블을 생성하는 단계;
로 이루어짐을 특징으로 하는 UWB 애드 혹 네트워크에서의 TCP 성능 향상을 위한 위치 기반 라우팅 방법.
청구항 3.
제2항에 있어서,
상기 네트워크 상의 모든 노드를 원소로 하는 집합을 V, 최소 손실 경로가 탐색된 목적지 노드의 집합을 Y, 라우팅 테이블
의 생성을 위해 최소 손실 트리를 갖는 집합을 F라 할 때,
상기 제(b)단계는,
등록특허 10-0695104
- 2 -
b-1) 각 노드가 상기 집합 Y가 자신 노드만을 원소로 하도록 초기화하고, 상기 집합 F를 공집합으로 초기화하는 단계와;
b-2) 상기 집합 V-Y 에서 자신 노드로부터 TCP 효율 손실이 최소인 노드를 선택하는 단계와;
b-3) 상기 선택된 노드를 상기 집합 Y 에 추가하는 단계와;
b-4) 자신 노드로부터 상기 선택한 최소 손실 노드까지의 최소 손실 경로 상에 홉이 있는 경우, 해당 경로 상의 홉을 상기
집합 F 에 추가하는 단계; 및
b-5) 집합 V 와 Y 를 비교하고, 두 집합이 일치하지 않는 경우 상기 b-2) 단계로 궤환하고, 두 집합이 일치하는 경우 상기
집합 F 를 이용하여 라우팅 테이블을 생성하는 단계;
를 포함하는 것을 특징으로 하는 UWB 애드 혹 네트워크에서의 TCP 성능 향상을 위한 위치 기반 라우팅 방법.
청구항 4.
제3항에 있어서,
상기 b-2)단계에서,
상기 자신 노드는 상기 집합 Y 에 있는 노드들을 중계 노드로 사용하여 TCP 효율 손실이 최소인 노드를 선택하는 것을 특
징으로 하는 UWB 애드 혹 네트워크에서의 TCP 성능 향상을 위한 위치 기반 라우팅 방법.
청구항 5.
제3항 또는 제4항에 있어서,
상기 b-2) 단계에서,
상기 자신 노드는,
미리 정의된 최대 홉 수를 가진 라우트에 의해 지원되는 최소 전송률(r0), TCP 처리량의 감쇄 인자(λ), 자신 노드로부터 목
적지 노드까지의 라우트 길이(LR)를 이용하여 효율의 최대값(Rmax)을 계산하고, 계산된 효율 최대값에 각 홉에서 발생하
는 부가적인 전송률의 감쇄(α) 및 중계 노드의 처리 손실(β)을 적용하여 최종 효율 계산값(Re)을 산출하고, 산출된 최종 효
율 계산값이 최대가 되는 최소 손실 노드를 선택하는 것을 특징으로 하는 UWB 애드 혹 네트워크에서의 TCP 성능 향상을
위한 위치 기반 라우팅 방법.
청구항 6.
제5항에 있어서,
상기 자신 노드는,
수학식 를 통해 상기 효율의 최대값(Rmax)을 산출하는 것을 특징으로 하는 UWB
애드 혹 네트워크에서의 TCP 성능 향상을 위한 위치 기반 라우팅 방법.
등록특허 10-0695104
- 3 -
청구항 7.
제5항에 있어서,
상기 자신 노드는,
수학식 (H: 홉 수, i: 홉 인덱스)를 통해 상기 최종 효율 계산값(Re)을 산출하
는 것을 특징으로 하는 UWB 애드 혹 네트워크에서의 TCP 성능 향상을 위한 위치 기반 라우팅 방법.
청구항 8.
제5항에 있어서,
상기 자신 노드는,
수학식 (H: 홉 수, i: 홉 인덱스)를 통해 상기 최종 효율 계산값(Re)을 산
출하는 것이고,
상기 최종 효율 계산값(Re)을 산출하는 수학식에서,
상기 자신 노드는, 자신이 패킷 전송 가능한 최대 반경 거리인 C(>F)를 가지며, 각 홉의 길이를 Li라 할 때, 다음 수학식에
의해 상기 αi를 결정하는 것을 특징으로 하는 UWB 애드 혹 네트워크에서의 TCP 성능 향상을 위한 위치 기반 라우팅 방
법.
명세서
발명의 상세한 설명
발명의 목적
발명이 속하는 기술 및 그 분야의 종래기술
본 발명은 UWB 애드 혹 네트워크에서의 TCP 성능 향상을 위한 위치 기반 라우팅 방법에 관한 것으로, 보다 자세하게는
UWB 시스템의 위치 측정 특성을 이용하여 UWB 애드 혹 네트워크에서 최소 홉, 최소 라우트 길이를 기준으로 라우팅하
는 방식에 비하여 TCP 효율을 극대화시킬 수 있도록 하는 UWB 애드 혹 네트워크에서의 TCP 성능 향상을 위한 위치 기
반 라우팅 방법에 관한 것이다.
등록특허 10-0695104
- 4 -
UWB(Ultra Wide-Band)는 확산 스펙트럼 통신 기술의 한 종류로서 넓은 대역을 점유하고 있고, 고속의 데이터 전송을 지
원하는 통신 시스템으로서, 단거리 무선 통신과 고정 기반망 없이 노드들끼리 통신을 할 수 있는 애드-혹(Ad-Hoc) 네트워
크에 적용할 수 있는 유망한 기술 분야 중 하나로 여겨지고 있다.
기존의 무선 통신 시스템과 달리, 애드-혹 방식의 통신 시스템은 기반 시설이나 기지국을 필요로 하지 않으며, 일반적으로
애드-혹 네트워크의 이동 노드들은 라우터의 기능과 종단 시스템의 기능을 함께 가지고 있다. 그러므로, 이러한 네트워크
환경에서는 이동 노드들이 멀티 홉 전송 방식을 이용할 필요가 있으며, 이러한 애드-혹 방식은 유비쿼터스 컴퓨팅과 무선
센서 네트워크에 활용될 수 있다.
한편, 상기 애드-혹 방식의 통신 시스템에서는 신뢰성 있는 데이터 전송을 위해 TCP 프로토콜을 사용하며, TCP 프로토콜
은 유선 네트워크를 위해 설계된 것이므로 이동 환경에서는 몇 가지 문제점이 있다. 즉, 무선 채널 자체는 쉽게 에러가 발
생하고 노드의 이동성 및 채널 상태가 변화함에 따라 링크 안정성과 오류 문제가 발생하며, 노드들의 충돌은 인접 노드들
로부터 전송된 패킷의 충돌을 야기시키고 멀티 홉 라우팅에 대한 TCP 처리량을 떨어뜨린다.
이에 따라, 애드-혹 네트워크에서 TCP 성능 향상을 위해 다양한 방법들이 연구되어 왔으며, 연구된 방법으로는 최대 윈도
우에 따라 지연 애크(Ack)를 사용하는 방법, TCP 혼잡 윈도우의 크기 증가를 억제하는 방법, 충돌을 감소시키기 위한 링
크층의 랜덤 초기 감지 방식 구현, TCP 패킷의 동적 페이싱(Facing)을 사용하는 방법 등이 있으나, 이러한 방법들에서는
라우팅 방식이 고려되지 않았다.
한편, 애드-혹 네트워크를 위해 제안된 기존의 라우팅 프로토콜로는 DSDV(Destination-Sequence Distance-Vector
Routing), DSR(Dynamic Source Routing), AODV(Ad-Hoc On-Demand Distance Vector Routing) 등이 있다.
DSDV는 프로-액티브 라우팅 프로토콜로서, 노드간에 주기적인 업데이트 패킷을 주고 받음으로써 네트워크 상의 모든 노
드에 대한 경로 정보를 라우팅 테이블에 유지한다.
DSR, AODV와 같은 온-디맨드(On-Demand) 라우팅 프로토콜은 필요에 따라 라우팅 리퀘스트(RREQ) 패킷을 네트워크
전체에 전송하여 목적지까지의 경로를 찾는 방식으로서, ADOV에서는 라우팅 리퀘스트 패킷이 지나온 노드마다 역방향
경로에 대한 정보를 라우팅 테이블에 추가하고, 라우팅 리퀘스트 패킷이 역방향 경로를 통해 송신자에게 전달될 때, 송신
자에서 목적지 사이의 경로가 중간 노드들의 라우팅 테이블에 추가되는 방식으로 최신의 라우팅 테이블을 유지하고 최소
의 홉을 거치도록 라우트 경로를 설정하는 방식이다.
그런데, 상기 AODV 프로토콜은 최초의 검색 지연 문제점을 가지고 있으며, 선택된 경로가 TCP 성능에 어떠한 영향을 미
칠지 고려되지 않았으므로, TCP 성능 측면에서 예상치 못한 손실이 일어날 수 있으며, 선택 경로의 품질을 사전에 알 수
없고, 특히 모든 경로에서 경로의 길이가 길어지면 상대적으로 TCP 효율은 감소하게 되나, 상기 AODV 프로토콜은 이를
고려하지 않았으므로 너무 긴 다중 홉으로 인한 TCP 성능의 저하를 야기할 수 있다는 단점이 있다.
발명이 이루고자 하는 기술적 과제
따라서, 본 발명은 상기와 같은 종래 기술의 제반 단점과 문제점을 해결하기 위한 것으로, UWB 애드 혹 네트워크에서
UWB 시스템의 위치 측정 특성을 이용하여 최소 홉, 최소 라우트 길이를 라우팅 기준으로 하는 기존의 라우팅 방식에 비하
여 TCP 효율을 극대화할 수 있는 경로를 선택하도록 하는 UWB 애드 혹 네트워크에서의 TCP 성능 향상을 위한 위치 기
반 라우팅 방법을 제공함에 본 발명의 목적이 있다.
발명의 구성
본 발명의 상기 목적은 UWB 애드 혹 네트워크에서의 TCP 성능 향상을 위한 위치 기반 라우팅 방법으로서, (A) 상기
UWB 애드 혹 네트워크 상의 각 노드가 주기적으로 네트워크 상의 모든 노드에 대하여 TCP 효율이 최대가 되는 최소 손실
라우팅 경로를 탐색하고, 탐색된 라우팅 경로를 이용하여 라우팅 테이블을 생성하여 유지하는 단계와; (B) 패킷 전송 이벤
트가 발생된 노드가, 자신 노드로부터 목적지 노드까지의 거리(D)가 자신의 최적 전송 거리인 임계치 거리(F) 이하인지를
판단하는 단계와; (C) 상기 판단 결과, 자신 노드로부터 목적지 노드까지의 거리(D)가 자신의 임계치 거리(F)를 초과하는
경우, 상기 자신 노드가 자신이 유지하고 있는 상기 라우팅 테이블에서 상기 목적지 노드로의 최소 손실 경로를 찾고, 자신
등록특허 10-0695104
- 5 -
노드로부터 목적지 노드까지의 거리(D)가 자신의 임계치 거리(F) 이하인 경우, 상기 자신 노드는 상기 목적지 노드로 직접
패킷을 전송하는 단계; 를 포함하는 UWB 애드 혹 네트워크에서의 TCP 성능 향상을 위한 위치 기반 라우팅 방법에 의해
달성된다.
본 발명의 상기 목적과 기술적 구성 및 그에 따른 작용 효과에 관한 자세한 사항은 본 발명의 명세서에 첨부된 도면에 의거
한 이하 상세한 설명에 의해 보다 명확하게 이해될 것이다.
먼저, 도 1은 체인 네트워크 토폴로지이고, 도 2는 도 1의 토폴로지에서 정규화된 TCP 효율을 나타낸 그래프로서, 다중 홉
이 TCP 처리량에 미치는 영향을 설명하기 위한 것이다.
도 1의 단순 체인형 네트워크 토폴로지에서, 소스 노드(Sender)는 TCP 프로토콜을 사용하여 데이터를 전송한다. 여기서,
소스 노드로부터 목적지 노드(Receiver)까지는 단일 홉이나 다중 홉으로 연결되며, 이 때 모든 홉의 길이(홉 간 거리)는 같
다고 가정한다.
도 2는 도 1에서의 체인 네트워크 토폴러지의 모의실험 결과를 나타낸 것으로, 정규화된 TCP 처리량은 실제 얻을 수 있는
효율의 최대치로 나눈 비율이다. 그리고, 정규화된 거리는 노드의 최대 반경 거리(C)로 실제 거리를 나눈 비율로, 경로의
유효성을 도 2를 참조하여 보면 다음과 같은 특성을 갖게 된다.
우선, 전송 출력의 한계로 인해 소스 노드와 목적지 노드 사이의 거리(D)가 최대 반경 거리(C)보다 크게되면, 소스 노드와
목적지 노드는 직접적으로 통신할 수 없다. 이 경우, 다중 홉 경로를 사용해 먼 거리까지 그 연결성을 확장시킬 수 있지만
만약 D가 H(홉 수)×C 보다 크다면 효율은 0이 된다.
또한, 경로의 길이가 길어지면 상대적으로 TCP 효율은 감소하며, 만약 한 경로의 특정 홉 길이가 송신 노드가 패킷을 전송
할 수 있는 한계 거리인 최대 반경 거리(C)에 비해 아주 길어질 경우, 그 라우트에는 병목 현상이 일어날 것이며, 이러한 상
황은 하나의 다중 홉 경로가 하나 이상의 길이가 긴 홉을 가진 경우에 더 나빠진다.
만약, 소스 노드와 목적지 노드 사이의 거리(D)가 특정 짧은 송신 거리보다도 적을 경우에는, 단일 홉의 성능이 다른 모든
다중 홉 라우트의 성능을 능가한다. 왜냐하면, 좁은 범위 내에서는 순방향 패킷의 충돌 가능성이 H(홉 수)와 함께 상승하기
때문이며, 게다가 중간(릴레이) 노드가 많다는 것은 결국 더 많은 처리 지연과 전파 지연을 의미하기 때문이다. 결과적으로
TCP 연결의 왕복 시간이 누적되고 TCP 성능은 다중 홉 경로에 거쳐서 떨어진다.
그리고, D가 커지면 충돌이 작아지며 상대적으로 짧은 홉을 가진 다중 홉 경로는 더 많은 효율을 보장할 수 있다. 긴 홉을
통한 경우의 대량 감쇄는 이것을 두 개 또는 세 개의 짧은 홉으로 대체할 경우 완화될 수 있다.
흔히, 근거리 홉 라우터는 홉의 길이가 최적의 한계 거리인 임계치 거리(F, 예: F=0.5C)보다 훨씬 짧은 홉들로 구성되어 있
다. 소스 노드와 목적지 노드 사이의 거리(D)가 임계치 거리(F) 보다 길면, 단거리 홉 라우트는 H×F > D라는 조건을 만족
해야 하고 서로 다른 단거리 홉 라우트들은 매우 비슷한 성능을 보여준다.
모든 단거리 홉 라우트 성능 곡선의 상층부는 하나의 지수 감쇄 곡선으로 근접하게 되며, 전체 전력 소모와 간섭을 감소시
키기 위하여 홉의 수가 적은 단거리 홉 라우트가 선택되도록 우선순위를 부여하도록 한다. 예를 들어, F < D < 2F 에서 두
개의 홉을 가진 라우트가 우세할 것이며, 2F < D < 3F이라면 세 개의 홉을 가진 라우트가 상대적으로 성능이 좋을 것이다.
따라서, 본 발명에서는 이러한 조건을 고려하여 라우팅 경로를 결정한다.
앞서 언급한 것처럼 이동 노드는 전력 제약에 따른 한정적인 무선 영역을 갖게 되며, 좁은 통신 영역에서 단일 홉 라우트가
우세한 것은 다중 홉 라우트에서 과도한 지연과 경합 문제가 발생하기 때문이나, 만약 소스 노드가 목적지 노드로부터 멀
리 떨어진 경우, 단일 홉이나 적은 수의 홉 라우트로는 신호 수신을 제대로 할 수 없으므로 다중 홉 라우트가 우세하게 된
다.
다음, 도 3은 본 발명에 따른 UWB 애드 혹 네트워크에서의 라우팅 방법을 설명하기 위한 개념도이고, 도 4는 체인 네트워
크에서 특정 파라미터 값을 적용한 경우의 TCP 효율을 나타낸 그래프이다.
도 3에 도시된 바와 같이, 네트워크 상의 모든 노드들은 최대 반경 거리(C)와 임계치 거리(F)를 갖게 되며, 소스 노드와 목
적지 노드가 임계치 거리보다 멀리 떨어진 경우에는 소스 노드로부터 목적지 노드로 직접 패킷을 전송하는 것보다, 임계치
거리 미만의 릴레이 노드를 경유하여 패킷을 전송하는 것이 TCP 성능 측면에서 유리하다.
등록특허 10-0695104
- 6 -
UWB 시스템에서 각 노드들은 다른 노드들과의 거리 즉, 다른 노드들의 위치를 알 수 있으며, 이를 이용하여 본 발명에서
는 네트워크 상의 모든 노드들이 주기적으로 상대 노드들의 위치를 측정하고, 이를 기반으로 TCP 성능을 최대화한 최소
손실 경로를 결정하고, 이에 따른 라우팅 테이블을 유지한다.
D는 소스 노드와 목적지 노드 사이의 거리이고, LR은 이 둘 사이의 라우트 길이라고 할 때, LR은 다음과 같다.
수학식 1
여기에서, {Li}는 경로에 종속된 홉들의 길이이고 i는 홉 인덱스이다. 모든 i 에 대해 Li ≤ F, D > F인 짧은 홉 경로를 고려
시, 효율의 최대값은 다음 식과 같다.
수학식 2
여기에서 ro는 미리 정의된 최대 홉 수를 가진 라우트에 의해 지원될 수 있는 전송율의 최소범위를 가리키며, λ는 처리량-
감쇄 인자로, 만약 경로 상에 F 보다 긴 홉이 있다면 처리량에 추가적인 감소를 고려해야 한다. 즉, 각 홉 i에서 발생하는 부
가적인 전송률의 감쇄(αi)는 다음 식과 같이 구할 수 있다.
수학식 3
즉, 홉 길이가 임계치 거리 F 이하이면 부가적 전송률 감쇄는 없으며, 홉 길이가 임계치 거리와 최대 반경 거리 사이이면 부
가적 전송률의 감쇄는 최대 반경 거리와 홉 길이의 차를, 최대 반경 거리와 임계치 거리의 차로 나눈 값으로 감쇄되며, 홉
길이가 최대 반경 거리 이상이 되면 패킷은 전송될 수 없게 된다.
본 발명에서 모든 노드들은 다음 수학식 4를 이용하여 효율 계산값을 구할 수 있다.
수학식 4
여기에서 β는 중계(릴레이) 노드의 자체적 처리 손실이며, 이 손실로 인해 다중 홉 경로에 있는 노드들에 의해 발생하는 과
도 지연과 성능 저하가 생긴다. 이에 따라, 본 발명에서는 β를 사용하여 다중 홉 라우트의 성능을 좀더 적은 수의 홉을 가진
라우트에 우선권을 부여하도록 측정한다. 한편, 상기 수학식 4에서는 D ≤ F일 경우의 다중 홉 경로 충돌 문제는 고려하지
않았지만, 이 경우에는 직접 연결 방식을 채용하여 이 문제를 해결할 수 있다.
도 4는 체인형 네트워크에서 F = 0.52C, r0 = 0.25, λ= 0.125, β= 0.04 일 경우의 TCP 성능 측정 결과를 보여준다. 이러
한 변수들은 곡선 근사법을 사용 추정치가 정확하다고 판단될 때까지 조정될 수 있다. 도면에서 알 수 있듯이, TCP 성능은
소스 노드와 목적지 노드 간 거리가 멀어질수록 멀티 홉 경로가 우세함을 알 수 있다.
이러한 점에 기인하여, 본 발명에서는 상기 수학식 4를 통한 효율 계산치를 기반으로 경로상에 TCP 효율을 최대화시킬 수
있는 라우팅 알고리즘을 제시하며, 이동 네트워크 토폴로지는 무방향 그래프(undirected graph)로 가정한다. 각 노드는
등록특허 10-0695104
- 7 -
그래프 상에서 vertex이다. 네트워크 상의 모든 노드는 자체적으로 다른 모든 노드에 대해 최소 경로를 찾는다. 여기서 최
소 경로란 효율 손실이 최소가 되는 경로를 의미한다. 수학식 4의 Re의 역수는 라우트를 통한 전송률 손실을 측정하는데
사용할 수 있다. 다음은 이러한 접근법의 알고리즘을 도 5 및 도 6을 통해 순차적으로 설명하면 다음과 같다.
도 5는 본 발명의 일 실시예에 따른 라우팅 방법의 각 노드에서의 라우팅 테이블 생성 과정을 나타낸 흐름도, 도 6은 본 발
명의 일 실시예에 따른 라우팅 방법의 패킷 전송 과정을 나타낸 흐름도이다.
도 5에 도시된 바와 같이, 본 발명에서 각 노드는 노드의 이동성을 고려하여 라우팅 테이블을 갱신하기 위하여, 주기적으
로 UWB 애드 혹 네트워크 상의 모든 노드들의 위치를 측정한다(S101).
UWB 시스템은 1ns 또는 그 미만의 아주 짧은 펄스를 사용하여 수신 펄스의 도착 시간을 측정하는데 있어 우수한 시간 분
해능(time resolution)를 제공할 뿐만 아니라, 노드 사이의 거리를 정확하게 탐지할 수 있다. 위치 측정 알고리즘은 다양한
방식이 연구되어 왔으며, 일 예로서 자신의 위치를 알고 있는 한 노드에서 다른 노드로 펄스를 전달하면 그 다른 노드에 펄
스가 도달한 도착 시간의 차로 그 위치를 알 수 있다. 본 발명에서 이러한 노드 간 위치 측정 방법은 제한되지 않는다.
이 후, 각 노드는 상기 측정된 위치 즉, 노드 간 거리를 이용하여 이하의 라우팅 테이블 생성 과정(S102~S107)을 수행한
다.
먼저, 모든 노드로의 최적 경로를 탐색하기 위해 각 노드는 집합 V, Y, F를 초기화한다. 여기서 집합 V는 네트워크 상의 모
든 노드 집합으로서, 노드의 수가 N개인 경우를 나타내며, 집합 Y는 소스 노드 즉, 자신의 노드를 나타내며, 집합 F는 최소
손실 트리를 갖는 집합으로서 초기에는 공집합으로 세팅된다(S102).
다음, 상기 자신 노드(소스 노드)는 집합 V-Y 에서 소스 노드(v1)로부터 최소 손실을 갖는 즉, 효율 손실이 최소인 노드 v
를 선택한다(S103). 이때, 상기 노드 v 의 선택시, 상기 소스 노드는 중계 노드로서 집합 Y 에 있는 노드들을 사용할 수 있
다.
상기 단계 S103에서, 상기 소스 노드는 앞서 언급한 수학식 4를 이용하여 다른 노드들의 효율 계산값을 산출하고, 효율 계
산값이 최대이거나, 효율 계산값의 역수가 최소인 노드를 선택하는 것이다.
다음, 상기 소스 노드는 상기와 같이 선택된 노드 v 를 집합 Y 에 추가한다(S104). 이때, 집합 Y 에 상기 최소 손실 노드를
추가하는 것은 이후에 상기 선택된 노드를 제외한 다른 노드들만을 가지고 계속하여 최소 손실 노드를 선택하기 위함이며,
또한 다른 노드들에 대한 최소 손실 경로의 선택 시 상기 선택된 노드를 중계 노드로서 사용할 수 있음을 의미한다.
그리고, 상기 소스 노드는 소스 노드로부터 상기 선택한 최소 손실 노드까지의 최소 손실 경로 상의 홉(최소 손실 노드를
목적지 노드로 할 때 자신 노드의 다음 노드)을 집합 F 에 추가한다(S105). 상기 집합 F 는 모든 노드에 대한 최소 손실 경
로의 탐색 과정이 끝난 후 최종적으로 라우팅 테이블을 생성하는 데 이용된다.
한편, 최초의 최소 손실 노드 선택시에는 집합 Y 에 자기 자신 노드만이 있으므로, 릴레이 노드의 선택은 불가능하게 되며,
이 경우 상기 선택된 최소 손실 노드 v 까지는 단일 홉 경로가 될 것이고, 이에 따라 첫번째 단계에서 집합 F 에는 어떠한
노드도 추가되지 않게 된다. 즉, 상기 소스 노드 v1으로부터 상기 노드 v 까지의 최소 손실 경로는 단일 홉 경로이다.
다음, 상기 소스 노드는 모든 노드에 대하여 최소 손실 경로를 찾아야 하므로, 집합 V 와 Y 가 동일한 집합이 될 때까지 상
기 S103 단계 내지 S105 단계를 계속하여 수행한다. 즉, 상기 S105 단계 수행 이후, 상기 소스 노드는 상기 집합 V 와 Y를
비교하고(S106), 두 집합이 일치하지 않는 경우 상기 S103 단계로 궤환한다.
한편, 상기와 같은 과정을 거쳐 집합 V 와 Y 가 동일한 집합이 되면, 모든 노드들로의 최소 손실 경로가 탐색된 것이므로,
상기 소스 노드는 집합 F 의 정보를 이용하여 라우팅 테이블을 생성하거나, 이전 라우팅 테이블이 있는 경우 이를 갱신한
다(S107).
여기서, 라우팅 테이블은 상기 소스 노드를 제외한 다른 모든 노드들이 목적지 노드인 각각의 경우, 자신이 패킷을 전송해
야 하는 다음 홉의 노드 정보를 갖는다. 예를 들어, 자신 노드가 1번이고, 1번으로부터 5번까지의 최소 손실 경로 상에 릴
레이 노드로서 8번, 10번, 9번 노드가 순차적으로 존재하는 경우, 상기 라우팅 테이블에는 5번 노드가 목적지인 경우의 다
음 홉으로서 8번 노드가 기록될 것이다.
등록특허 10-0695104
- 8 -
상기와 같이, 본 발명에서 각 노드들은 주기적인 라우팅 테이블 갱신 과정을 수행하며, 경로의 탐색은 효율 손실이 최소가
되도록 하기 위하여 TCP 효율 계산값을 산출하고 이를 기반으로 최소 손실 경로를 결정함에 의해 이루어진다.
이후, 도 6에서와 같이 상기와 같은 라우팅 테이블을 유지하는 각 노드는 자신이 소스 노드가 되어 특정 목적지 노드로 패
킷을 전송하여야 하거나, 다른 노드로부터 패킷이 포워딩됨에 따라 패킷 전송 이벤트가 발생하면(S201), 자신 노드로부터
목적지 노드까지의 거리(D)가 자신의 임계치 거리(F) 이하인지를 판단한다(S202).
상기 판단 결과, 자신 노드로부터 목적지 노드까지의 거리(D)가 자신의 임계치 거리(F)를 초과하는 경우, 상기 자신 노드
(또는 소스 노드)는 자신이 유지하고 있는 라우팅 테이블에서 상기 목적지 노드로의 최소 손실 경로를 찾고, 자신의 다음
홉을 검색한 후(S203), 해당 홉으로 패킷을 포워딩한다(S204).
상기 임계치 거리(F)는 자신이 직접 전송할 수 있는 최적 임계치 거리를 의미하므로, 만약, 자신 노드로부터 목적지 노드까
지의 거리(D)가 자신의 임계치 거리(F) 이하인 경우, 상기 자신 노드는 상기 목적지 노드로 직접 패킷을 전송한다(S202-
1).
상기 설명한 본 발명의 라우팅 방법의 TCP 성능을 모의 실험을 통해 분석한 결과를 도 7 내지 도 11을 통해 도시하였으며,
도 7 내지 도 9는 정적 네트워크 토폴로지의 실험 결과를, 도 10 및 도 11은 동적 네트워크 토폴로지의 실험 결과를 보여준
다. 도면에서, LAR(Location Aided Routing)은 본 발명의 라우팅 방법을 의미한다.
먼저, 도 7은 임의의 정적 네트워크 토폴로지, 도 8은 도 7에서 본 발명의 라우팅 방법을 적용한 경우와 기존의 AODV 프
로토콜에 의한 라우팅 방법을 적용한 경우의 경로 비교표, 도 9는 도 7에서 본 발명의 라우팅 방법을 적용한 경우와 기존의
AODV 프로토콜에 의한 라우팅 방법을 적용한 경우의 TCP 성능 비교 그래프이다.
도 7의 정적 네트워크 토폴로지에서 32개의 노드는 30[m] × 30[m] 크기의 정사각형에 랜덤하게 놓여지며 이동하지는
않는다. 이 토폴로지에서 각 노드들에는 0번에서 31번까지 번호가 부여되어 있으며, 점선으로 표시된 9개의 쌍은 무작위
로 추출된 것이다.
도 7을 적용한 모의 실험 결과를 도 8 및 도 9를 통해 살펴보면, 소스 노드와 목적지 노드 간 직접 연결을 제외하고 본 발명
의 라우팅 방법에 의해 선택된 라우트들은 기존의 AODV 프로토콜에 비해 더 많은 홉 수를 거치며, 효율 측면에서 성능이
우수함을 알 수 있다.
직접 연결인 #2과 #9 조차도, 본 발명의 라우팅 방법에서는 초기 검색 대기 지연이 필요한 AODV와 비교하여 더 높은 효
율을 제공한다.
도 8의 표에 나타낸 바와 같이, 본 발명의 라우팅 방법의 효율의 이론값은 각 연결의 모의 실험 결과와 거의 비슷함을 알 수
있으며, 이와 같은 결과를 통해 본 발명의 라우팅 구조가 잘 동작함을 알 수 있다.
다음, 도 10은 랜덤하게 이동하는 노드의 예를 나타낸 동적 네트워크 토폴로지, 도 11은 도 10에서 본 발명의 라우팅 방법
을 적용한 경우와 기존의 AODV 프로토콜에 의한 라우팅 방법을 적용한 경우의 이동 속도에 따른 TCP 성능 비교 그래프
이다.
이 동적 시나리오에서는, 16개의 노드가 앞서 설명한 정적 토폴로지에서와 같은 크기의 정사각형 영역에 놓여있고, 랜덤한
방향으로 그 영역 안에서 이동한다고 가정한다. 도 10은 랜덤하게 이동하는 노드의 예를 보여주고 있다.
각 노드는 0에서 15까지 번호가 부여되어 있고, 4쌍으로 임의로 나뉜다. 이 실험에서는 3가지의 다양한 이동 속도를 고려
하였으며, 느린 속도는 약 0.5 m/s (1.8 km/h), 빠른 속도는 1.5 m/s (5.4 km/h) 이며 중간속도는 1.0 m/s (3.6 km/h) 이
다.
도 11에는 각 TCP 연결들의 전체 효율을 나타내었다. 본 발명의 라우팅 방법에서는 최대의 TCP 효율을 가진 경로를 탐색
하므로, 각 이동 속도에서 본 발명에 의한 총 효율은 AODV의 효율보다 값이 큰 것을 볼 수 있다.
등록특허 10-0695104
- 9 -
또한, 도 11에 의하면 이동 속도가 효율에 미치는 영향을 알 수 있다. 즉, 속도가 빠를수록 연결 상태의 안정성이 나빠지므
로 효율이 떨어진다. AODV 프로토콜을 사용한 경우는 경로를 설정하는데 훨씬 많은 시간이 걸리지만 그 라우팅 테이블은
노드의 이동 속도가 빨라지면 거의 쓸모 없게 되며, TCP 효율의 손실이 있는 경우 경로 찾기로 인해 지연시간이 초래된다.
반면, 본 발명의 라우팅 방법에 의하면, 위치 정보를 이용하여 라우팅 경로 결정시 시간 소모를 피하고 높은 효율을 갖는
경로를 선택하기 쉽다. 따라서 선택된 경로는 더 긴 수명을 가지며 만약 위치 정보가 지정 시간 내에 갱신될 수 있다면 본
발명은 경로 선택 에러나 해제 없이 연속적인 TCP 연결을 제공할 수 있을 것이다.
본 발명이 속하는 기술분야의 당업자는 본 발명이 그 기술적 사상이나 필수적 특징을 변경하지 않고서 다른 구체적인 형태
로 실시될 수 있으므로, 이상에서 기술한 실시예들은 모든 면에서 예시적인 것이며 한정적인 것이 아닌 것으로서 이해해야
만 한다. 본 발명의 범위는 상기 상세한 설명보다는 후술하는 특허청구범위에 의하여 나타내어지며, 특허청구범위의 의미
및 범위 그리고 그 등가개념으로부터 도출되는 모든 변경 또는 변형된 형태가 본 발명의 범위에 포함되는 것으로 해석되어
야 한다.
발명의 효과
따라서, 본 발명의 UWB 애드 혹 네트워크에서의 TCP 성능 향상을 위한 위치 기반 라우팅 방법에 의하면, 최대의 TCP 효
율을 갖는 경로를 탐색함으로써, 초기 검색 대기 지연이 필요한 AODV와 비교하여 정적인 UWB 애드 혹 네트워크 및 동적
인 UWB 애드 혹 네트워크에서 더 높은 효율을 제공하며, 라우팅 경로 결정시 시간 소모를 피할 수 있고 높은 효율을 갖는
경로를 선택하기 쉬우며, 이에 따라 선택된 경로는 더 긴 수명을 가지며 경로 선택 에러나 해제 없이 연속적인 TCP 연결을
제공할 수 있을 것으로 기대된다.
도면의 간단한 설명
도 1은 체인 네트워크 토폴로지,
도 2는 도 1의 토폴로지에서 정규화된 TCP 효율을 나타낸 그래프,
도 3은 본 발명에 따른 UWB 애드 혹 네트워크에서의 라우팅 방법을 설명하기 위한 개념도,
도 4는 체인 네트워크에서 특정 파라미터 값을 적용한 경우의 TCP 효율을 나타낸 그래프,
도 5는 본 발명의 일 실시예에 따른 라우팅 방법의 각 노드에서의 라우팅 테이블 생성 과정을 나타낸 흐름도,
도 6은 본 발명의 일 실시예에 따른 라우팅 방법의 패킷 전송 과정을 나타낸 흐름도,
도 7은 임의의 정적 네트워크 토폴로지,
도 8은 도 7에서 본 발명의 라우팅 방법을 적용한 경우와 기존의 AODV 프로토콜에 의한 라우팅 방법을 적용한 경우의 경
로 비교표,
도 9은 도 7에서 본 발명의 라우팅 방법을 적용한 경우와 기존의 AODV 프로토콜에 의한 라우팅 방법을 적용한 경우의
TCP 성능 비교 그래프,
도 10은 랜덤하게 이동하는 노드의 예를 나타낸 동적 네트워크 토폴로지,
도 11은 도 10에서 본 발명의 라우팅 방법을 적용한 경우와 기존의 AODV 프로토콜에 의한 라우팅 방법을 적용한 경우의
이동 속도에 따른 TCP 성능 비교 그래프이다.
도면
등록특허 10-0695104
- 10 -
도면1
도면2
도면3
등록특허 10-0695104
- 11 -
도면4
도면5
등록특허 10-0695104
- 12 -
도면6
도면7
등록특허 10-0695104
- 13 -
도면8
도면9
도면10
등록특허 10-0695104
- 14 -
도면11
등록특허 10-0695104
- 15 -