KR101068667B1

KR101068667B1 - 히든 노드 및 감지 간섭을 고려한 라우팅 경로 설정 방법, 그 시스템 및 이를 기록한 기록매체

Info

Publication number: KR101068667B1
Application number: KR1020090091469A
Authority: KR
Inventors: 김명철; 강성원; 디마 아매드 모하매드 함마쉬
Original assignee: 한국과학기술원
Priority date: 2009-09-28
Filing date: 2009-09-28
Publication date: 2011-09-28
Also published as: US8300538B2; KR20110034093A; US20110075578A1

Abstract

히든 노드 및 감지 간섭을 고려하여 라우팅 경로를 설정하기 위한 방법 및 시스템이 개시된다. 복수 개의 노드 및 두 개의 노드를 연결하는 복수 개의 링크를 포함하는 무선 멀티 홉 네트워크에서 소스 노드로부터 목적지 노드로 패킷을 전송하기 위한 라우팅 경로를 설정하기 위한 방법은, 링크들 각각의 캐리어 감지 간섭을 나타내는 캐리어 감지 간섭 가중치(carrier sense interference weight)를 연산하고, 소스 노드 및 목적지 노드를 연결하는 적어도 하나의 특정 경로(specific path)에 포함되는 링크들의 캐리어 감지 간섭 가중치를 조합하는 단계, 링크들 각각의 히든 노드 문제(hidden node problem)를 나타내는 히든 노드 가중치를 연산하고, 경로에 포함되는 링크들의 히든 노드 가중치를 합산하는 단계, 및 캐리어 감지 간섭 가중치 및 히든 노드 가중치를 조합하여 특정 경로의 메트릭(metric) 값을 연산하고, 가장 작은 메트릭 값을 가지는 특정 경로를 라우팅 경로로서 결정하는 단계를 포함한다. 본 발명에 의하여 다중 채널 다중 무선 메쉬 네트워크에서 히든 노드 문제와 캐리어 감지 간섭을 최소화하는 경로를 선정하여 네트워크 성능을 향상시킬 수 있다.

Description

히든 노드 및 감지 간섭을 고려한 라우팅 경로 설정 방법, 그 시스템 및 이를 기록한 기록매체{Method and system for setting routing path considering hidden node and carrier sense interference, and recording medium thereof}

본 발명은 컴퓨터 네트워크에서의 라우팅 경로 설정에 관한 것으로, 특히 다중 홉 무선 네트워크에서의 네트워크 성능 향상을 위하여 히든 노드 및 감지 간섭을 고려한 라우팅 경로 설정 방법, 그 시스템 및 이를 기록한 기록매체에 관한 것이다.

일종의 다중 홉 무선 네트워크인 무선 메쉬 네트워크는 네트워크의 크기가 커짐에 따라 캐리어 감지 간섭(carrier sense interference)과 히든 노드 문제(hidden node problem)에로 인해 네트워크 성능이 급격하게 떨어진다.

멀티채널 멀티라디오가 무선 매쉬 네트워크 용량(capacity)을 효과적으로 증가 시킬 수 있지만 멀티채널 네트워크의 최대 이용률을 얻기 위해서는 캐리어 감지 간섭과 히든 노드 문제를 줄일 수 있도록 각 노드의 링크들에 채널을 할당 되야 한다. 그러나 채널 할당문제의 복잡도가 NP hard 문제이기 때문에 채널이 형성된 후 채널 다양성(channel diversity), 경로내 간섭(intra-flow interference), 경로간 간섭(inter-flow interference), 히든 노드 문제와 같은 요소들을 고려한 라우팅 메트릭을 이용하여 라우팅 경로를 설정하여야 한다. 메트릭이란 라우팅 프로토콜이 최적 경로를 선택하기 위해 참고하는 값으로, 라우팅 프로토콜의 종류에 따라 각기 다르다.

초기에는 라우팅 경로 설정에 사용되는 라우팅 메트릭은 단순히 홉수(hop count)에 의존하였다. 하지만 이런 홉수는 단순히 최단 경로만을 선호하기 때문에 효율적인 라우팅 메트릭이 아니다.

이러한 문제점을 해결하기 위해 Expected transmission count metric (ETX)가 D. De Couto, D. Aguayo, J. Bicket, R. Morris의 high-Throughput Path Metric for Multi-Hop Wireless Routing ACM MOBICOM(2003년 9월)에서 제안됐다. ETX는 링크 패킷 손실률을 최적의 링크 품질을 가진 경로를 선택하는 기반으로 이용함으로써 링크의 상태를 평가한다. 그러나, 이 기법이 비록 최단경로에 비해 좋은 성능을 보이지만, 링크들의 대역폭(bandwidth)이 고려되지 않고 오직 링크상의 손실 비율만이 고려된다. 또한 Channel-diversity가 높은 경로를 선택하지도 못하고, 히든 노드 문제를 해결하지도 못한다.

이러한 ETX의 문제점을 해결하고자 R. Draves, J. Padhye, B. Zill 2005년 6월 22일에 출원한 대한민국 공개번호 10-2006-0092811 의해 누적형 예상 전송시간 메트릭을 사용하는 링크품질 라우팅을 위한 시스템 및 방이 제안되었다. 이 방식은 ETX에서의 channel diversity 문제를 해결하였다. 더욱이 이 방식은 링크의 bandwidth 를 포함하여 ETX를 개선하여 Expected Transmission Time (ETT)를 제안 하였다. 각각의 개별 링크들이 ETX 값을 사용하기 때문에 ETT는 링크상에 재 전송을 포함하여 단일 packet을 전송하는데 필요한 시간을 계산한다. 이러한 값을 토대로 한 패킷의 총 지연시간과 채널 다양성(channel diversity)을 계산하여 경로를 선정한다.

비록 WCETT가 ETX의 문제점 중 일부를 해결했지만 아직도 여전히 문제점을 안고 있다.

첫째, WCETT는 ETX가 그러하듯 히든 노드 문제를 고려하지 않기 때문에 이를 구분하거나 피할 수 없다.

둘째, 한 경로상에 같은 채널을 사용하는 링크들은 서로의 캐리어 감지범위 안에 위치 할 경우에만 간섭이 발생하나 WCETT는 같은 채널을 사용하는 링크를 경로상 링크의 위치에 관계없이 병목현상을 일으키는 채널계산에 포함시키기 때문에 정확한 계산을 하지 못한다.

셋째, WCETT는 경로간 간섭 (inter-flow interference)을 고려하지 않고 경로내 (intra-flow interference)만 고려하였다.

이렇듯 WCETT와 ETX가 해결하지 못하는 히든 노드 문제를 다루기 위해 J. Sangiamwong, T. Sugiyama은 hidden node aware routing metric (IEEE PIMRC 2007)을 제안했다. 이 라우팅 메트릭은 IEEE 802.11s의 neighbor discovery 단계에서 브로드 캐스팅되는 Local Link State Announcement 패킷 교환을 통해 히든 노드를 구분하고 MAC layer에서 패킷 전송 시간을 고려하여 히든 노드문제에 의한 패킷 충돌률을 계산하여 경로선정에 사용한다. 그러나, 이 라우팅 메트릭은 히든 노드의 영 향을 적절히 추정하지 못했고 경로내 또는 경로간 (intra-flow와 inter-flow) 간섭을 고려 하지 않는 문제점을 가지고 있다.

따라서, 본 발명이 해결하고자 하는 첫 번째 과제는 히든 노드와 캐리어 감지 간섭을 최소화하여 무선 메쉬 네트워크 환경에서 라우팅 성능 향상을 꾀할 수 있는 히든 노드 및 감지 간섭을 고려한 라우팅 경로 설정 방법을 제공하는 것이다.

그리고 본 발명이 해결하고자 하는 두 번째 과제는 상기 히든 노드 및 감지 간섭을 고려한 라우팅 경로 설정 방법을 적용한 히든 노드 및 감지 간섭을 고려한 라우팅 경로 설정 시스템을 제공하는 것이다.

그리고, 본 발명이 해결하고자 하는 세 번째 과제는 상기 히든 노드 및 감지 간섭을 고려한 라우팅 경로 설정 방법을 컴퓨터에서 실행시킬 수 있는 기록매체를 제공하는 것이다.

상기 첫 번째 과제를 해결하기 위하여 본 발명은, 복수 개의 노드 및 두 개의 노드를 연결하는 복수 개의 링크를 포함하는 무선 멀티 홉 네트워크에서 소스 노드로부터 목적지 노드로 패킷을 전송하기 위한 라우팅 경로를 설정하기 위한 방법에 있어서, 상기 링크들 각각의 캐리어 감지 간섭을 나타내는 캐리어 감지 간섭 가중치(carrier sense interference weight)를 연산하고, 상기 소스 노드 및 상기 목적지 노드를 연결하는 적어도 하나의 특정 경로(specific path)에 포함되는 링크들의 캐리어 감지 간섭 가중치를 조합하는 단계; 상기 링크들 각각의 히든 노드 문제(hidden node problem)를 나타내는 히든 노드 가중치를 연산하고, 상기 특정 경 로에 포함되는 링크들의 히든 노드 가중치를 합산하는 단계; 및 상기 캐리어 감지 간섭 가중치 및 상기 히든 노드 가중치를 조합하여 상기 특정 경로의 메트릭(metric)값을 연산하고, 가장 작은 메트릭 값을 가지는 특정 경로를 상기 라우팅 경로로서 결정하는 단계를 포함하는 라우팅 경로 설정 방법을 제공한다.

한편, 상기 캐리어 감지 간섭 가중치는 동일한 공유 채널을 이용하는 경로에 속하는 링크들 또는 인접 경로에 속하는 링크들 간의 캐리어 감지 간섭을 나타내고, 상기 히든 노드 가중치는 동일한 경로 또는 인접 경로 내의 링크에 의하여 야기되는 히든 노드 문제를 나타내는 것을 특징으로 한다.

또한, 상기 무선 멀티 홉 네트워크는 서로 다른 채널을 사용하는 다중 이종 무선 트랜스시버를 가진 노드들을 포함하는 것을 특징으로 한다.

또한, 캐리어 감지 간섭 가중치는, 상기 경로 내의 특정 링크에서의 패킷 전송 시간 및 상기 경로 상의 패킷 재송신 횟수를 이용하여 연산되는 것을 특징으로 한다.

또한, 상기 패킷 전송 시간은, 고정 패킷 사이즈, 미리 할당된 로 링크(raw link) 대역폭 및 MAC 계층 프로토콜 프레임간 간격(inter-frame spacing) 및 제어 패킷을 이용하여 연산되는 것을 특징으로 한다.

또한, 상기 패킷 재송신 횟수는, 상기 특정 링크 상의 시간에 따른 가중치 정방향 및 역방향 전송률(weigthed forward and reverse delivery ratios)을 이용하여 연산되고, 상기 가중치 정방향 및 역방향 전송률은 연속적인 두 개의 전송률들에 지수적 가중치 평균화 기법(exponential weighted averaging technique)을 적 용하여 연산되는 것을 특징으로 한다.

또한, 상기 히든 노드 가중치는, 상기 경로 내의 특정 링크에 영향을 미치는 모든 히든 링크에 기인한 예상 충돌 횟수들 및 상기 특정 링크 상의 패킷 송신 시간을 이용하여 연산되는 것을 특징으로 한다.

또한, 상기 예상 충돌 횟수는, 히든 노드 충돌(Hidden Node Collision, HNCOL) 분석학적 모델에 따라서 히든 노드와의 충돌에 의해 패킷이 전송되는 횟수인 것을 특징으로 한다.

또한, 상기 히든 노드 가중치는 상기 히든 노드와의 충돌 확률을 이용하여 연산되고, 상기 히든 노드와의 충돌 확률은 하기의 식 1에 의해 연산되는 것을 특징으로 한다.

(1)

(상기 식 1에서 A,B는 노드를 의미하며, VP는 링크 A-B에서 히든 노드 충돌이 발생할 수 있는 기간이며, Data_pkt_TT는 데이터 패킷 전송 시간을 의미함.)

또한, 총 데이터 전송 시간은, 경로 p에서 캐리어 감지 간섭 효과에 의한 총 추정 패킷 전송 시간을 WCEPTT_CS라 하고, 히든 노드에 의한 총 추정 패킷 전송 시간을 CEPTT_HN이라고 하며, WCEPTT_CS 및 CEPTT_HN이 평활 인자(smoothing factor)

를 가지고 지수적 가중치 평균화 기법을 이용하여 조합된다고 하면, 하기의 식 2에 의해 결정되는 것을 특징으로 한다.

(2)

상기 두번째 과제를 해결하기 위하여 본 발명은, 복수 개의 노드 및 두 개의 노드를 연결하는 복수 개의 링크를 포함하는 무선 멀티 홉 네트워크에서 소스 노드로부터 목적지 노드로 패킷을 전송하기 위한 라우팅 경로를 설정하기 위한 시스템을 제공하는데, 이 시스템은 상기 링크들 각각의 캐리어 감지 간섭을 나타내는 캐리어 감지 간섭 가중치(carrier sense interference weight)를 연산하고, 상기 소스 노드 및 상기 목적지 노드를 연결하는 적어도 하나의 특정 경로(specific path)에 포함되는 링크들의 캐리어 감지 간섭 가중치를 조합하기 위한 캐리어 감지 간섭 가중치 합산 메커니즘; 상기 링크들 각각의 히든 노드 문제(hidden node problem)를 나타내는 히든 노드 가중치를 연산하고, 상기 경로에 포함되는 링크들의 히든 노드 가중치를 합산하는 히든 노드 가중치 합산 메커니즘; 및 상기 캐리어 감지 간섭 가중치 및 상기 히든 노드 가중치를 조합하여 상기 특정 경로의 메트릭(metric) 값을 연산하고, 가장 작은 메트릭 값을 가지는 특정 경로를 상기 라우팅 경로로서 결정하는 라우팅 경로 결정 메커니즘을 포함하는 것을 특징으로 한다.

특히, 상기 캐리어 감지 간섭 가중치는 동일한 공유 채널을 이용하는 경로에 속하는 링크들 또는 인접 경로에 속하는 링크들 간의 캐리어 감지 간섭을 나타내고, 상기 히든 노드 가중치는 동일한 경로 또는 인접 경로 내의 링크에 의하여 야기되는 히든 노드 문제를 나타낸다.

또한, 상기 무선 멀티 홉 네트워크는 서로 다른 채널을 사용하는 다중 이종 무선 트랜스시버를 가진 노드들을 포함한다.

또한, 상기 캐리어 감지 간섭 가중치는, 상기 경로 내의 특정 링크에서의 패킷 전송 시간 및 상기 경로 상의 패킷 재송신 횟수를 이용하여 연산된다.

또한, 상기 패킷 전송 시간은, 고정 패킷 사이즈, 미리 할당된 로 링크(raw link) 대역폭 및 MAC 계층 프로토콜 프레임간 간격 및 제어 패킷을 이용하여 연산된다.

또한, 상기 패킷 재송신 횟수는, 상기 특정 링크 상의 시간에 따른 가중치 정방향 및 역방향 전송률(weigthed forward and reverse delivery ratios)을 이용하여 연산되고, 상기 가중치 정방향 및 역방향 전송률은 연속적인 두 개의 전송률들에 지수적 가중치 평균화 기법(exponential weighted averaging technique)을 적용하여 연산된다.

또한, 상기 히든 노드 가중치는, 상기 경로 내의 특정 링크에 영향을 미치는 모든 히든 링크에 기인한 예상 충돌 횟수들 및 상기 특정 링크 상의 패킷 송신 시간을 이용하여 연산된다.

또한, 상기 예상 충돌 횟수는, 히든 노드 충돌(Hidden Node Collision, HNCOL) 분석학적 모델에 따라서 히든 노드와의 충돌에 의해 패킷이 전송되는 횟수이다.

또한, 상기 총 데이터 전송 시간은, 경로 p에서 캐리어 감지 간섭 효과에 의한 총 추정 패킷 전송 시간을 WCEPTT_CS라 하고, 히든 노드에 의한 총 추정 패킷 전송 시간을 CEPTT_HN이라고 하며, WCEPTT_CS 및 CEPTT_HN이 평활 인자(smoothing factor)

를 가지고 지수적 가중치 평균화 기법을 이용하여 조합된다고 하면, 하기의 식 3에 의해 결정되는 것을 특징으로 한다.

(3)

본 발명에 의하면, 멀티채널 멀티라디오 무선 메쉬 네트워크에서 히든 노드 문제와 캐리어 감지 간섭을 최소화하는 경로를 선정하여 네트워크 성능을 향상시키고, 라우팅 메트릭을 라우팅 프로토콜의 관계없이 다양한 라우팅 프로토콜에 적용가능하기 때문에 다양한 다중 홉 멀티채널 멀티라디오 무선 매쉬 네트워크 환경에서 라우팅 성능 향상 효과를 기대할 수 있으며, 멀티라디오 무선 메쉬 네트워크에 Hello 패킷 브로드캐스팅시 발생하는 각 채널에 중복된 패킷 전송을 목적 노드와 체널별로 패킷 분류화를 통해 줄여 전체적인 네트워크 오버헤드를 줄일 수 있고, 히든 노드 문제와 캐리어 감지 간섭을 피하는 경로를 통해 라우팅을 안정적으로 유지할 수 있도록 한다.

이하, 첨부한 도면을 참조하여 본 발명의 바람직한 실시예를 설명함으로서, 본 발명을 상세히 설명한다. 그러나, 본 발명은 여러 가지 상이한 형태로 구현될 수 있으며, 설명하는 실시예에 한정되는 것이 아니다. 오히려, 이러한 실시예들은 본 명세서가 더 완전하게 이해될 수 있도록 하기 위하여 제공되며, 당업자에게 본 발명의 기술적 사상을 완전하게 전달할 것이다. 상세한 설명에서, 본 발명을 명확 하게 설명하기 위하여 설명과 관계없는 부분은 생략된다.

본 명세서에서 이용되는 용어는 특정 실시예만 설명하기 위한 목적으로 이용되는 것이 아니며, 본 발명을 한정하는 것으로 이해되어서는 안된다. 본 명세서에서 이용되는 단수의 “한”, “하나의”, “그” 라는 표현은 명백히 그렇지 않다고 기술되지 않는한 복수 표현 역시 포함하는 것으로 의도된다. 더 나아가, 한, 하나의 등과 같은 표현은 반드시 양을 제한하는 것이 아니고, 오히려 참조되는 아이템이 적어도 하나 존재할 수 있다는 것을 나타낸다. 더 나아가, “포함” 및/또는 “포함하는” 또는 “구비” 및/또는 “구비하는”이라는 표현이 본 명세서에서 이용되면, 이것들은 언급된 특징, 영역, 정수, 단계, 동작, 요소, 및/또는 성분들이 존재한다는 것을 나타내는 것이라는 것이 이해되어야 하며, 반면에 이들 이외의 하나 또는 그 이상의 특징, 영역, 정수, 단계, 동작, 요소, 및/또는 그룹이 존재하거나 이들이 추가적으로 존재한다는 것을 배제하는 것이 아니라는 점도 이해되어야 한다.

다른 방식으로 정의되지 않는 한, 본 명세서에서 이용되는 모든 용어(기술적 및 과학적 용어를 포함)들은 당업자에게 널리 이해되는 것과 동일한 의미를 가진다. 더 나아가, 널리 이용되는 사전에 정의되는 것과 같은 용어들은 관련 기술 및 본 발명과의 관련을 통하여 그들의 의미와 일치하는 의미를 가지는 것으로 해석되어야 하며, 본 명세서에서 명백하게 달리 정의되지 않는한 이상적이거나 또는 너무 형식적인 의미로 해석되어서는 안된다는 점도 이해되어야 한다.

도면에서, 도면 내의 유사한 부재 번호는 유사한 요소를 가리킨다. 도면의 모양, 크기, 및 영역 등은 간략화를 위하여 과장될 수 있다.

본 발명은 히든 노드와 감지 간섭을 고려한 라우팅 메트릭을 이용하여 네트워크의 성능 향상을 이루도록 한 것이다.

즉, 멀티 홉 멀티 라디오 멀티 채널 네트워크에서 발신 노드와 수신 노드간의 데이터 전송에서 네트워크의 성능이 줄어드는 것을 방지하기 위하여 각 링크에 대하여 히든 노드 문제와 캐리어 감지 간섭에 의한 데이터 전송 시간을 측정한다.

이를 위하여, 첫 번째로 캐리어 감지 간섭에 의하여 데이터 패킷의 전송 시간을 측정하고, 두 번째로 히든 노드가 존재하는 환경에서의 데이터 패킷의 전송 시간을 측정한다.

그러면, 이를 조합하여 각 링크의 데이터 전송 시간을 계산하여 경로상 링크의 조합에 의한 총 데이터 전송 시간을 추정함으로써 최상의 경로를 선택하기 위한 본 발명에 따른 라우팅 경로 설정을 수행할 수 있게 된다.

본 발명은 경로내 간섭(intra-flow interference)과 경로간 간섭(inter-flow interference)을 최소화하여 라우팅 경로를 설정할 수 있으며, 각각의 경로에 있어서 히든 노드에 의한 충돌 현상을 최소화할 수 있다.

본 발명에서는 두 개의 가중치(weights)가 연산된다. 하나는 캐리어 감지 간섭 효과에 의한 추정 패킷 전송 시간(Expected Packet Transmission Time with Carrier Sence interference effect:EPTT_CS)이고, 다른 하나는 히든 노드 효과에 의한 추정 패킷 전송 시간(Expected Packet Transmission Time with Hidden Node effect:EPTT_HN)이다.

여기서, EPTT_CS와 EPTT_HN의 값이 각 링크에서의 두가지 중요한 가중치가 되고, 경로상 링크의 조합들에 의한 총 데이터 전송 시간을 추청하여, 최상의 경로를 선택할 수 있으며, 이것이 본 발명이 제안하는 새로운 라우팅 메트릭인 HIAM(Hidden node and Interference Aware routing Metric)인 것이다.

도 1은 본 발명에 따른 히든 노드 및 감지 간섭을 고려한 라우팅 경로 설정 방법의 흐름도를 도시한 것이다.

도 1을 참조하면 우선, 무선 멀티 홉 네트워크에 있어서 소스 노드와 목적지 노드를 연결하는 경로의 특정 링크에 대하여 캐리어 감지 간섭에 대한 감지 간섭 가중치를 연산한다.(S110)

그 다음, 상기 특정 링크에 대하여 히든 노드 문제에 대한 히든 노드 가중치를 연산한다.(S120)

상기 감지 간섭 가중치 및 상기 히든 노드 가중치를 조합하여 링크의 라우팅 메트릭 값을 연산하고(S130), 경로상 링크의 조합에 의한 총 데이터 전송 시간을 추정함으로써 데이터 전송 시간이 가장 짧은 라우팅 경로를 설정한다(S140).

상기의 각 단계에 대한 자세한 상세한 설명은 하기에 기술하기로 한다.

본 발명의 소정 실시예들은, 노드들이 IEEE 802.11 사양의 라디오를 가진, 무선 네트워크에서의 사용을 위해 설계된다. 그러나, 다른 실시예들은 다른 무선 기술들에 기초한 네트워크들에 적용될 수 있다. 본 발명은 스트리핑 기술들 또는 지향성 안테나들의 사용과 같은, 다중-홉 무선 네트워크들에서 네트워크 용량을 향상시키기 위한 하나이상의 다른 기술들 또는 메커니즘들과 함께 사용될 수 있다.

본 발명에 의한 HIAM 라우팅 메트릭은 전술한 바와 같이, 각 링크에서의 EPTT_CS와 EPTT_HN을 연산하여야 한다. 그리고 이를 위하여 우선 고정 크기의 패킷 전송 시간(Packet Transmission Time:PTT)을 우선 연산하여야 한다.

PTT 연산은 하기의 수학식 1과 같다,

상기 수학식 1에서 PTT_ij는 노드 i와 노드 j를 연결하는 링크를 통하여 패킷이 전송되는 시간을 의미한다. 그리고, DIFS와 DATA는 MAC 계층에서 사용되는 인터 프레임 인터벌을 의미하며, DATA_pkt_TT(Data packet transmission time)는 데이터 패킷 전송 시간을, ACK_TT(acknowledgment packet transmission time)는 ACK 패킷 전송 시간을 나타낸다. MAC 계층에서 ACK 패킷은 기본 데이터 전송 속도인 1Mbps로 전송 된다.

한편, DATA_pkt_TT는 하기의 수학식 2와 같이 계산되고, ACK_TT는 하기의 수학식 3과 같이 계산된다.

PTT은 한 패킷이 하나의 링크상에 전송되는데 필요한 총 시간이다. 발신 노 드의 MAC 계층에서는 ACK 패킷 수신 없이는 이 패킷이 성공적으로 전송 되었다고 간주 하지 않기 때문에 packet이 손실 되더라도 발신 노드는 packet 재전송을 위해 ACK timeout 시간 동안 기다려야 한다. 그러므로 한 링크상의 패킷 전송 시간을 정확하게 계산하기 위해서는 ACK 전송시간과 SIFS 그리고 DIFS를 계산에 포함하여야 한다.

한편, 전송 범위과 케리어 감지 범위가 같은 경우를 가정하였기 때문에 캐리어 감지 노드들에 의한 충돌은 CSMA가 방지하기 때문에 무시하고 RTS/CTS 기능은 사용하지 않는다.

이러한 가정들을 토대로 HNCOL_num는 분석적인 모델을 통해 계산된다. 이 분석학적 모델을 설명하기 위해 4 개의 노드들이 일렬로 구성된 (A, B, C, D 순으로 구성) 간단한 토폴로지에서 모든 노드들에 동일한 채널을 사용하여 바로 옆에 위치한 노드와 연결된 예를 사용한다. 이 토폴로지상 링크 C-D는 링크 A-B의 히든 링크가 된다.

히든 링크에 의한 한 패킷의 재전송 회수를 계산하기 위해 한 패킷을 전송하기 위한 시간뿐만 아니라 히든 노드 문제에 의해 패킷충돌이 발생한 경우의 재전송시간을 고려하기 위해 충분한 기간을 설정해야 한다.

MAC 계층에서 최대 재전송 횟수를 4회 까지만 허용하기 때문에 총 전송시간, TIME을 5*PTT로 정의하였다. 이는 히든 노드 문제에 의한 충돌이 발생한 경우 허용되는 4회의 재전송 횟수와 최초 패킷 전송에 필요한 총 전송 시간을 나타낸다. 재 전송 간의 백오프 기간(최대 512㎲)은 무시할 만큼 짧기 때문에 우리가 정의한 TIME 기간에 포함하지 않는다.

이 TIME 기간 동안 위 예에서의 링크 A-B가 전송을 하는 중에 링크 C-D가 전송을 시작하지만 않으면 링크 A-B와 링크 C-D에서의 전송에 충돌을 일어나지 않는다.

링크 B-C상 노드 B의 캐리어 감지 범위안에 노드 C와 A가 위치하기 때문에 링크 B-C는 링크 A-B와 C-D의 캐리어 감지 링크가 되기 때문에 노드 B가 링크 B-C에 패킷을 전송하는 동안 노드 A와 노드 C가 데이터를 전송하는 경우는 발생하지 않는다. 더욱이 노드 A의 캐리어 감지 범위안에 활동중인 다른 링크가 존재할 경우 이런 캐리어 감지 노드들이 전송을 하는 동안 노드 A는 전송을 하지 못하게 되고 노드 C와 충돌도 발생하지 않는다. 노드 C 역시 노드 A와 같은 상황을 겪게 된다.

이 기간 TIME 동안 링크 A-B와 링크 C-D 사이에 충돌이 일어나기 쉬운 기간(vulnerable period)을 얻기 위해 링크 A-B와 C-B의 캐리어 감지 범위 안의 링크들에 의해 채널이 점유되는 기간들을 구하여 이를 전체시간 TIME에서 빼야 한다. 캐리어 감지 노드들이 캐리어 감지영역에 있는 링크들에게 패킷을 전송하는 기간을 측정하기 위해서 먼저 이 노드들이 패킷을 전송할 확률을 계산하여야 한다. 모든 노드들은 같은 데이터율(data rate)를 가진다는 가정하에 이 확률은 하기의 수학식 4와 같이 계산된다.

상기 수학식 4에서

는 링크 A-B의 모든 캐리어 감지 링크들이 데이터 전송을 위해 채널을 점유할 확률을 의미한다. 그리고,

는 링크 A-B의 캐리어 감지 범위 안의 링크 A-B와 같은 채널 Ch_n을 사용하는 링크들의 수를 의미한다. 상기 수학식 4에서 분모는 링크 A-B를 포함하여 이 링크와 같은 캐리어 감지 범위안에 있는 링크들의 총 개수를 의미한다. 이 확률은 히든 링크인 C-D와 이에 영향을 받는 링크 A-B 양쪽 모두를 위하여 연산된다.

이러한 확률들을 사용하여

(Carrier Sense links Transmission Time)를 구할 수 있다.

또 이 시간 동안 링크 A-B와 C-D는 idle한 상태로 유지되고 히든 노드 문제에 의한 충돌이 일어나지 않기 때문에

는 다음과 같이 수학식 5에 의해 계산된다.

여기에서 모든 링크들이 동일한 대역폭을 가지고 패킷의 크기가 고정되어 있는 가정 하에 첫 번째 부분인

은 링크 A-B의 캐리어 감지 범위 안에 있는 링크들이 전송에 사용하는 시간을 나타낸다. 다시 말해 이 시간 동안 링크 A-B가 idle하다는 것을 의미한다.

는 링크 AB의 캐리어 감지 범위 안에 있는 링크들이 전송할 확률을

는 링크 AB로 하나의 패킷이 전송될 때 필요한 시간을 나타낸다. 두 번째 부분 역시 같은 방식으로 적용 된다.

결국, TIME 기간에서

를 차감하면 충돌이 일어나기 쉬운 기간(VP : Vulnerable period )을 구할 수 있다.

이 VP기간은 링크 A-B와 C-D가 전송할 기회를 가지는 기간으로서 히든 링크인 C-D 때문에 링크 A-B에서 충돌이 발생할 수 있는 기간이다.

VP는 하기의 수학식 6과 같이 계산된다.

이렇듯 링크 A-B에서 충돌이 얼마나 많이 발생하는지를 계산하기 위해 하나의 패킷 전송을 VP안에 완료할 확률을 계산한다.

링크 A-B에서의 히든 노드 문제에 의한 충돌이 일어날 확률

은 하기의 수학식 7과 같이 계산된다.

상기 수학식 7에서, PTT는 VP동안 충돌이 발생하는 시간을 의미하며, 전술하였듯이 PTT는 데이터 패킷 전송 시간과 ACK 패킷 전송 시간을 모두 포함한다. 가정된 시나리오를 고려하면, 노드 B가 노드 A로부터 데이터 패킷을 성공적으로 수신 했고 노드 B가 노드 A로 ACK 패킷 전송을 시작했다면 노드 C는 전송을 할 수 없다. 따라서 ACK 패킷 전송 시간 동안에는 충돌이 발생하지 않기 때문에 PTT 동안 충돌이 유효한 시간을 얻기 위해 데이터 패킷 전송 시간만을 고려하여야 한다. 이것은, 노드 B가 노드 C의 캐리어 감지 범위 안에 있기 때문이며, 따라서 ACK 패킷 전송 시간 동안에는 충돌이 발생하지 않는다. PTT 동안의 충돌 유효 시간은

을 이용하여 하기의 수학식 8과 같이 계산된다.

결론적으로 히든 노드에 의한 충돌 횟수를 예측하기 위해 수학식 9와 같이

의 역수를 취하여 얻는다.

한편, 이 링크에 영향을 미치는 모든 히든 노드에 의한 충돌을 고려한

을 연산하고, 이는 하기의 수학식 10과 같다.

상기 수학식 10에서 PTT_ij는 노드 i와 노드 j를 연결하는 링크의 패킷 전송 시간이며, H는 링크 ij의 히든 링크의 집합을 의미하고,

은 히든 링크 fg에 의해 링크 ij 상에 발생할 패킷 충돌 횟수를 의미한다. 또한,

는 링크 ij에 영향을 미치는 모든 히든 링크 H 집합에 의해 야기되는 총 패킷 충돌 횟수를 의미한다.

는 HNCOL 분석 모델에 의해 추정된다.

패스 메트릭 연산은 경로 상의 모든 링크의

의 총합으로 연산된다.

은 하기의 수학식 11에 의해 연산될 수 있다.

본 발명에 따르는 HIAM 라우팅 메트릭의 WCEPTT_CS은 수정된 ETX(Modified ETX, METX) 메커니즘을 이용하여 캐리어 감지 간섭에 의해 야기되는 재전송 횟수를 측정함으로써 연산된다.

ETX를 HIAM 라우팅 메트릭에 적용하는데 2가지 문제점이 있다. 첫번째 문제점은 ETX에서 손실률를 구할 때 사용되는 인터벌(interval)이 본 발명에서 제안한 HNCOL 분석학적 모델보다 많이 길다는 것이다. 두 번째 문제점은 ETX에서 예측된 한 패킷의 최대 재전송 횟수가 HNCOL 분석학적 모델에서 예측한 재전송 회수보다 많이 크다는 것이다. 본 발명이 포함하는 분석학적 모델에서 예측되는 재전송 회수는 5회를 넘지 않는다. 이 횟수는 MAC 계층에서 패킷 전송을 포함한 최대 패킷 재전송 횟수이다. 그러므로 ETX와 HNCOL 간에는 균형이 필요하다. ETX에서 윈도우(window)는 어떠한 인터벌 시간으로도 변경할 수 있지만 일반적으로 10초인 윈도우 시간(window time)을 동일하게 사용하여 계산한다. 만약 이 윈도우를 1초로 변경하면, 단 한번의 재전송도 일어나지 않는 부정확하고 일반적이지 않은 결과를 얻을 것이다. 그러므로 우리는 전송률을 연산하는 새로운 방법을 제안하는데, 여기서 모든 링크가 이미 모든 패킷을 성공적으로 수신하였다는 가정 하에 모든 링크는 1과 같은 높은 전송률로부터 시작하게 된다. 매초, ETX 프로브 패킷(probe packet) 은 브로트캐스팅 된다. 만약 링크의 수신 측이 패킷을 수신하지 못했다면 이 링크의 전송률은 감소한다. 매 1초 후 1초에서 다음 초까지 손실된 packet의 수가 누적된다. 전송률(DR:Delivery ratio)은 수학식 12와 같이 계산된다.

여기에서, DRf,r은 한쪽 방향(전방향 또는 역방향)의 전송률을 뜻한다. accum_pkt는 누적된 손실 패킷들의 갯수이고, max_retrans 는 MAC 계층의 최대 재전송 횟수이다. 이러한 프로세스는 원본 패킷 송신에 추가하여 MAC 계층에서의 최대 재전송 한계치와 동일한 시간 윈도우에 대해서 반복될 것이다. 이후의 5초 동안에, 전송률은 1로 재시작될 것이다. 모든 단계는 5초 안에 수행이 완료 되며 delivery ratio를 구하기 위해 반복 된다. 그러나 이러한 방식은 링크 상태를 갑작스럽게 변하게 할 수 있고, ETX 값을 부정확하게 할 수 있다. 이처럼 변동이 심한 ETX 값을 안정시키기 위해서는 수학식 13과 같이 지수적 가중치 평균화 기법(exponential weighted averaging technique 또는 exponential moving average technique)을 이용하여 계산한다.

여기에서, WDR은 가중치 전송률(Weighted Delivery Ratio, WDR)이고, α는 변경 가능한 변수로서 0<α<1 이다. HIAM라우팅 메트릭에서, α는 0.8로 설정하여 새로운 ETX에 기존 ETX 보다 높은 가중치를 부여했다. 이러한 설정으로 안정적으로 매 초마다 비교적 정확한 ETX값을 얻을 수 있다.

마지막으로 METX(modified ETX)는 아래의 수학식 14와 같이 오리지널 ETX와 같은 방법으로 계산된다.

여기에서, WDR_f와 WDR_r은 각각 한 링크 상의 가중치 정방향 및 역방향 전송률을 뜻한다.

채널 n을 사용하는 링크 ij의 EPTT_CS는 수학식 15와 같이 계산된다.

WCETT를 확장하여 intra-flow 와 inter-flow interference를 고려하기 위해 경로 p 상에 있는 링크 또는 이 경로 근처에 있는 링크이던지 상관없이 경로 p상의 링크 ij와 간섭이 일어나는 모든 링크들을 고려하여 하기의 수학식 16과 같이 계산 된다.

여기에서, CSp는 경로 p상에 존재하는 링크 ij의 캐리어 감지 범위안에 위치하고 경로 p에 포함되거나 근접한 모든 링크들의 집합을 뜻한다.

는 링크 ij의 캐리어 감지 범위 안에 위치하는 링크들 중 링크 ij를 포함하여 채널 n (CH_n)을 사용하는 모든 링크들의 집합이다. CSp 집합 내의 간섭을 일으키는 링크들의 EPTT_CS은 경로 p 상에 하나의 패킷을 전송할 때 재 전송과 매체(medium)를 점유하기 위해 대기한 시간을 포함하여 전송에 필요한 시간의 총 합을 뜻한다. 이렇게 계산된 값을

이라고 명하고 수학식 17과 같이 계산된다.

여기에서,

는 CSP 집합 안에 포함된 링크 uv에 의한 경로 p의 총 전송시간을 의미한다.

경로 상 링크들의 캐리어 감지 범위 안에서 간섭을 일으키는 링크들의 EPTT 값들을 모두 합하여 통해 inter-flow와 intra-flow 간섭을 계산한다.

이를 계산할 때 본 발명은 액티브(active) 링크들 만을 고려하고, 아이들(idle) 링크들은 고려하지 않는다.

액티브 링크는 링크 상에 데이터 플로우를 전송하는 비지(busy) 링크를 의미하며, 아이들(idle) 링크는 패킷 전송을 하지 않거나 제어 패킷(RREQ이나 Hello 패킷)만을 전송하는 링크를 뜻한다.

이와 같이 분류하는 이유는 히든 링크와 간섭을 일으키는 링크가 데이터 플로우 전송을 하는 비지 상태가 아니면 다른 링크들에게 영향을 주지 않기 때문이다.

또한 본 발명은, 오리지널 WCETT의 두 번째 계산 부분을 변경한

(BCL: Bottleneck Link Channel) 계산을 이용하여 채널 배치 문제를 해결했다.

즉 같은 채널을 사용하고 서로가 캐리어 감지 범위 안에 위치한 링크들만을 합하도록 변경했다. 이러한 변경을 통해 더 좋은 다양한 채널(channel diversity)을 사용한 경로들을 구별할 수 있다. 새로운 BLC는 하기의 수학식 18에 의해 계산된다.

여기에서,

는 링크 ij의 캐리어 감지 범위 안에서 링크 ij와 같은 채널을 사용하는 링크 uv의 캐리어 감지 간섭에 의한 전송 시간을 뜻한다. 또한 두 링크들은 경로 p상에 위치 하고 있다. 결국 BLC는 같은 채널을 사용하고 각 각의 간섭 범위 안에 위치한 링크들의 최대 합을 의미한다. 최종 WCEPTT_CS 은 다음과 같이 수학식 19에 의해 계산된다.

본 발명의 실시예에는 최대 홉 카운트 메트릭을 사용하는 AODV라우팅 프로토콜을 HIAM 라우팅 메트릭으로 대체하는 라우팅 프로토콜, 및 제어 패킷들 중 일부를 확장하는 방법 및 Hello 패킷을 브로드캐스팅하는 방법이 포함되며, 더 나아가 우리는 다중-채넛 다중-무선 환경에 적합하도록 이 방법을 수정하였다. 수정된 라우팅 프로토콜은 세 가지 주된 단계로 구성된다. 첫번째 단계는 각 링크에 대해 연산된 HIAM 메트릭의 환경 초기화를 위한 Hello 패킷을 교환하는 것이다. 두 번째 단계는 HIAM값을 포함하는 RREQ 패킷을 경로 상에 브로트캐스팅하는 단계이다. 마지막 단계는 목적지 노드에서 전송 받은 3개의 RREQ 패킷에 대한 HIAM 라우팅 메트릭을 계산하고 이 중 가장 작은 값을 가지는 경로를 선택하는 단계이다.

Hello 패킷 교환과 환경 설정 단계에서, 각 노드들은 캐리어 감지 간섭 링크들과 히든 링크들을 구분하기 위해 direct_neighbors_table과 indirect_neighbors_table을 생성한다. Direct_neighbors_table은 노드의 전송 범위 안에 위치한 직접 연결된 이웃 노드들의 정보를 포함하고, indirect_neighbors_table은 노드에 직접 연결된 이웃 노드들의 이웃 노드들의 정보를 포함하고 있다.

direct_neighbors_table는 각 노드에서 직접 연결된 이웃 노드들로부터 받은 ETX 프로브(probe) 패킷을 기본으로 생성되며 노드는 자신의 ETX 프로브 패킷에 이 테이블의 복사본을 첨부하고 정기적으로 브로드캐스팅한다. 본래 ETX 프로브 패킷은 직접연결된 이웃들로부터 받은 프로브 패킷을 기초로 하여 만들어진 테이블을 포함하기 때문에 이 테이블은 Direct Neighbor address(DN_addr)와 Forward Delivery Ratio(DRf)를 포함한다. 이 테이블에 해당하는 레코드(record)들을 토대로 다음과 같은 4개의 필드들이 추가되어 확장된다. Channel (ChnID) 필드는 direct neighbor과 사용하는 채널을 의미하고, EPTT_CS 필드는 direct link의 서로 다른 캐리어 감지 간섭에 의한 패킷 전송 시간를 고려하기 위해 필요한 필드이다. 그리고 CS_num은 노드의 캐리어 감지 범위 안에 같은 채널을 사용하는 엑티브 링크들의 개수를 의미한다. 마지막으로 STATUS 필드는 데이터 패킷들의 전송 중에 링크가 idle인지 엑티브인지 링크의 상태를 불리안(Boolean) 변수로 나타내는 필드이다. 언제나 패킷이 direct neighbor로부터 전달되면 패킷이 전송된 라디오는 엑티브 상태가 되고 이에 대응되는 링크 역시 엑티브 상태가 된다.

특히 채널과 이웃들의 수가 늘어나면 Hello 패킷의 크기는 새로 추가된 필드들에 의해 급격하게 증가 될 것이다. 게다가 멀티채널 멀티라디오 무선 매쉬 네트워크에서 패킷 브로드케스팅은 각 채널마다에 원본 패킷의 사본이 브로드캐스팅되기 때문에 더 증가하게된다. 이러한 네트워크 오버해드의 증가는 네트워크 대역폭를 낭비시킨다. 이러한 낭비를 줄이기 위해 본 발명은 Hello 패킷의 브로드캐스팅 과정을 변경하였다. Hello 패킷은 direct_neighbors_table을 포함하기 때문에 이 테이블을 Channel ID(Chn ID)를 기준하여 record 그룹들로 분류하고 각 record 그룹들을 서로 다른 Hello 패킷에 넣는다. 그리고 이 Hello 패킷을 record와 관련한 채널에만 브로드케스팅 하게한다. 이러한 방식으로 Hello 패킷이 노드가 사용하는 채널들의 수만큼 작은 패킷들로 나누어진다. 예를 들어 3개의 채널을 사용하고 있으면 Hello 패킷을 채널별로 3개의 인터페이스에 각각 할당한다. 그러므로 패킷을 분류할 때 3개의 패킷으로 분리되고 각 패킷은 대략적으로 원본 패킷의 1/3크기 만 하게 된다. 이러한 방법을 통해 채널 증가에 따른 브로드캐스팅 오버해드 증가를 줄일 수 있다.

indirect_neighbors_table은 direct neighbor들로부터 정기적으로 수신되는 Hello 패킷들에 포함된 direct_neighbors_table을 통해 구성된다. indirect_neighbors_table은 한 노드의 캐리어 감지 범위 밖에 있는 노드들과 direct neighbor들의 캐리어 감지 범위 안에 있는 노드들에 대한 정보를 제공할 수 있다.

이 테이블은 각 노드가 히든 링크들을 구별하고 이 링크들과 충돌할 확률을 구하는데 사용된다. Indirect neighbors table은 6개의 필드들(Direct neighbor address, Indirect neighbor address, Chn ID, Indirect CS_num, STATUS, EPTT_HN) 로 구성되어 있다. Direct neighbor address는 송신 노드의 direct_neighbors_table을 가지고 있는 수신된 Hello 패킷의 source address를 검색하기 위한 필드이다.

Indirect neighbor address와 뒤에 따라오는 필드들은 수신된 direct_neighbors_table 정보로 채워진다. 마지막 필드인 EPTT_HN은 히든 노드 문제에 의한 재전송을 포함한 총 패킷의 전송 시간을 의미한다. 이 값은 direct_neighbors_table과 indirect_neighbors_table의 정보를 사용하여 주기적으로 계산된다. STATUS 필드는 엑티브 히든 링크들을 고려하여 링크의 상태가 엑티브인지 idle인지를 나타낸다. Indirect neighbor CS_num은 히든 링크의 캐리어 감지 노드들이 전송할 기회를 갖게 되는 확률을 구하는데 사용된다. 이 확률을 사용하여 HNCOL_num 값을 구하고 결론적으로 EPTT_HN 값을 구한다.

Hello packet 교환과 HIAM의 환경 설정과정은 도 2와 같이 이루어진다.

도 2는 본 발명에 따른 AODV의 Hello 패킷 교환과 HIAM의 환경 설정과정을 도시한 것이다.

도 2를 참조하면, 노드는 Hello 패킷 인터벌의 시간이 경과하도록 대기한다(S210).

그런 다음, 자신의 direct_neighbors_table을 살펴본 후(S220), 자신의 direct_neighbors_table을 헬로우 패킷에 포함시킨다(S230). 그런 다음, 그 노드는 헬로우 패킷을 브로드캐스팅하게 된다(S240).

indirect_neighbors_table은 자신의 노드와 직접적으로 연결된 노드에 의해 전송된 헬로우 패킷에 포함된 direct_neighbors_table을 이용하여 정기적으로 생성된다.

indirect_neighbors_table은 실제로 한 노드와 직접적으로 연결된 노드에 대한 정보를 주게 되는 것이다.

따라서, 이 테이블은 각각의 노드가 히든 링크를 찾아내고, 히든 링크와의 충돌 확률을 연산하는데 사용될 수 있다.

indirect_neighbors_table은 총 6개의 필드로 구성될 수 있다.

첫 번째 필드는 헬로우 패킷에 포함되며, 소스 어드레스로부터 취할 수 있는 직접 연결된 이웃 노드의 주소이다.

두 번째 필드는 수신된 헬로우 패킷에 포함된 로컬 테이블에서의 노드 주소에 상응하는 직접 연결되지 않은 노드의 주소이다/

세 번째 내지 다섯 번째 필드는 direct_neighbors_tabledp 포함된 정보인 CS-num, 채널 ID, 그리고 STATUS이다.

여섯 번째 필드는

으로, 히든 노드 문제에 의해 발생되는 추정 패킷 전송 시간이다.

이와 같은 여섯 개의 필드는 direct_neighbors_table과 indirect_neighbors_table의 정보에 의해 주기적으로 연산된다. 그리고, 오직 액티브 히든 링크만이 본 발명의 프로토콜의 대상이 된다.

그러면, indirect_neighbor CS-num은 히든 링크의 캐리서 감지 노드가 전송할 기회를 가질 확률을 연산하는데 사용될 수 있다.

이 확률은

값과

값을 연산하는데 사용될 수 있다.

도 3은 수신측에서의 헬로우 패킷을 수신하는 과정을 도시한 것이다.

도 3을 참조하면, 우선 헬로우 패킷을 수신한 후에(301), 수신 노드는 헬로우 패킷으로부터 송신자의 주소를 파악하고(302), 헬로우 패킷으로부터 수신 링크의 정보를 탐색한다.(303)

그런 다음 송신자의 주소에 기초하여 리시빙 링크 기록은 direct_neighbors_table에 위치하고, 관련 링크 정보를 업데이트한다(304).

그런 다음, 노드는 송신자와 직접적으로 연결된 이웃 노드에 대한 헬로우 패킷에 저장된 indirect_neighbors_table의 정보를 업데이트하고(305), 노드는 리시빙 링크를 통하여 헬로우 패킷의 수를 업데이트 한다(306). 한편, 노드는 헬로우 패킷에 수신된 forward delivery ratio와 reverse delivery ratio를 이용하여 METX 값을 연산한다.(307)

그런 다음, METX 값을 사용하여 EPTT_CS 값을 연산하고(308), 그런 다음, direct_neighbors_table에 리시빙 링크 기록에 의하여 EPTT_CS값을 업데이트 한다.(309)

그리고, 노드는 히든 링크를 식별하는데, 이는 송신측에서 수신측 방향으로 링크된 수신 링크를 통하여 히든 링크를 식별한다.(310)

그리고, 노드는 indirect_neighbors_table을 통하여 히든 링크의 CS_num을 연산한다.(311) 그런 다음, 각 노드는 히든 링크에 의해 야기되는 HNCOL_num을 연산한다.(312)

그리고, 노드는 HNCOL_num의 총 합을 연산하고(313), 영향을 미치는 링크의 EPTT_HN을 연산한다.(314)

최종적으로, 각 노드는 EPTT_HN 값을 이용하여 indirect_neighbors_table을 갱신한다.(315)

본 발명은 AODV과 같은 라우팅 프로토콜에서 제 2 단계인 RREQ 패킷 브로드캐스팅 단계를 포함한다. 한 노드가 다른 한 노드로 data 패킷 전송을 원하면 노드는 먼저 라우트 요청(RREQ : Route Request)패킷를 전송하여 경로를 설정 해야 한다. AODV 라우팅 프로토콜에서 RREQ 패킷은 오리지널 필드들(첫 번째와 두 번째 필드 Source address and Sequence Number, Destination address and Sequence Number)에 5개의 필드들(forwarding node address, ChID, EPTT_CS, CS_EPTT_SUM, EPTT_HN)을 추가하였다. 이 5개의 필드는 목적지 노드 에서 HIAM을 계산하기 위해 필요하다.

한 노드가 RREQ 패킷을 받으면 이 RREQ를 전달하려는 노드의 address와 라디오에 서 사용할 채널로 업데이트한다. 그런 다음 그 노드는 두 값들을 사용하여 direct_neighbors_table에서 이 링크의 레코드를 검색하고 이 링크에 대응하는 EPTT_CS값을 얻는다. 이 EPTT_CS값은 이전 홉들에 의해 RREQ 패킷에 이미 저장된 값을 이용하여 RREQ 패킷이 지나온 경로의 CS_EPTT_SUM을 구할 때 사용하고 이 결과값을 RREQ 패킷에 포함한다. 또한 이 노드는 이전 홉들에서 RREQ 패킷에 기록된 EPTT_CS 값들을 이 경로의 BLC 계산에 사용 한다. 마지막으로 RREQ 패킷은 indirect_neighbors_table에서 얻은 링크의 EPTT_HN 값을 업데이트한다.

수신한 RREQ 패킷으로 계산된 HIAM값을 기본으로 노드는 이 RREQ 패킷의 경로가 소스 노드와 목적지 노드의 조합이 같은 이전에 수신한 RREQ 패킷에 의해 라 우팅 테이블에 저장된 경로보다 좋은 지를 비교한다. 만약 RREQ 패킷에 의해 계산된 HIAM값이 라우팅 테이블에 저장된 값 보다 좋으면 라우팅 테이블을 업데이트하고 이 RREQ를 브로드케스팅한다. 만약 그렇지 않으면 이 RREQ를 드롭한다.

본 발명은 라우팅 프로토콜에서 제 3 단계인 RREP 초기화 단계를 포함한다. 중간 노드들에 의한 라우트 응답(RREP : Route Reply) 패킷 초기화는 불가능 하게 하고 목적지 노드에서만 RREP 초기화가 가능하게 했다. 목적지 노드는 정해진 interval time안에 최대 3개의 RREQ 패킷들을 기다린다. 이 interval 동안 모두 받으면 3개의 RREQ 각각에 대한 HIAM 라우팅 메트릭이 계산되고 이 3개의 값은 서로 비교된다. 결론적으로 가장 작은 값을 가지는 경로가 선정된다. 만약 이 interval 동안 전송된 RREQ 패킷이 3개 보다 적으면 이 라우팅 메트릭은 이 interval 동안에 받은 RREQ 패킷들 만을 계산하고 이들만을 비교한다.

도 4는 RREQ 패킷의 수신 노드에서의 진행 과정을 도시한 것이다.

도 4를 참조하면, 노드는 RREQ 패킷을 수신하고(401), 송신 인터페이스의 어드레스, EPTT_CS, 및 CHnID를 direct_neighbors_table로부터 탐색한다(402).

그리고, 노드는 direct_neighbors_table를 이용하여 리시빙 링크를 통하여 CS_EPTT_sum를 연산한다(403).

그런 다음, EPTT_HN을 indirect_neighbors_table로부터 리시빙 링크를 통하여 연산하고(404), 상기 정보들을 RREQ 패킷에 저장한다(405).

그런 다음, RREQ 패킷에 저장된 현재 경로에 모든 링크에 대한 EPTT_HN의 총 합을 연산하고(406), BLC 값을 구하게 된다(407).

그런 다음, 노드는 CS_EPTT_sum과 BLC를 이용하여 WCEPTT_CS값을 구하고(408), EPTT_HN을 이용하여 CEPTT_HN을 구하며(409), 노드는 HIAM을 연산하고(410), 라우팅 테이블을 갱신(411)한 다음 RREQ 패킷을 브로드캐스팅한다(412).

본 발명은 소프트웨어를 통해 실행될 수 있다. 소프트웨어로 실행될 때, 본 발명의 구성 수단들은 필요한 작업을 실행하는 코드 세그먼트들이다.

프로그램 또는 코드 세그먼트들은 프로세서 판독 가능 매체에 저장되거나 전송 매체 또는 통신망에서 반송파와 결합된 컴퓨터 데이터 신호에 의하여 전송될 수 있다.

컴퓨터가 읽을 수 있는 기록매체는 컴퓨터 시스템에 의하여 읽혀질 수 있는 테이터가 저장되는 모든 종류의 기록 장치를 포함한다. 컴퓨터가 읽을 수 있는 기록 장치의 예로는 ROM, RAM, CD-ROM, DVD±ROM, DVD-RAM, 자기 테이프, 플로피 디스크, 하드 디스크(hard disk), 광데이터 저장장치 등이 있다.

또한, 컴퓨터가 읽을 수 있는 기록매체는 네트워크로 연결된 컴퓨터 장치에 분산되어 분산방식으로 컴퓨터가 읽을 수 있는 코드가 저장되고 실행될 수 있다.

본 발명은 도면에 도시된 일 실시예를 참고로 하여 설명하였으나 이는 예시적인 것에 불과하며 당해 분야에서 통상의 지식을 가진 자라면 이로부터 다양한 변형 및 실시예의 변형이 가능하다는 점을 이해할 것이다.

그러나, 이와 같은 변형은 본 발명의 기술적 보호범위내에 있다고 보아야 한다. 따라서, 본 발명의 진정한 기술적 보호범위는 첨부된 특허청구범위의 기술적 사상에 의해서 정해져야 할 것이다.

Claims

복수 개의 노드 및 두 개의 노드를 연결하는 복수 개의 링크를 포함하는 무선 멀티 홉 네트워크에서 소스 노드로부터 목적지 노드로 패킷을 전송하기 위한 라우팅 경로를 설정하기 위한 방법에 있어서,

상기 링크들 각각의 캐리어 감지 간섭을 나타내는 캐리어 감지 간섭 가중치(carrier sense interference weight)를 연산하고, 상기 소스 노드 및 상기 목적지 노드를 연결하는 적어도 하나의 특정 경로(specific path)에 포함되는 링크들의 캐리어 감지 간섭 가중치를 조합하는 단계;

상기 링크들 각각의 히든 노드 문제(hidden node problem)를 나타내는 히든 노드 가중치를 연산하고, 상기 경로에 포함되는 링크들의 히든 노드 가중치를 합산하는 단계; 및

상기 캐리어 감지 간섭 가중치 및 상기 히든 노드 가중치를 조합하여 링크의 라우팅 메트릭 값을 연산하고, 경로상 링크의 조합에 의한 총 데이터 전송 시간을 추정함으로써 데이터 전송 시간이 가장 짧은 경로를 상기 라우팅 경로로서 결정하는 단계를 포함하며,

상기 총 데이터 전송 시간은, 경로 p에서 캐리어 감지 간섭 효과에 의한 총 추정 패킷 전송 시간을 WCEPTT_CS라 하고, 히든 노드에 의한 총 추정 패킷 전송 시간을 CEPTT_HN이라고 하며, WCEPTT_CS 및 CEPTT_HN이 평활 인자(smoothing factor)
를 가지고 지수적 가중치 평균화 기법을 이용하여 조합된다는 조건하에, 하기의 식 1에 의해 결정되는 것을 특징으로 하는 라우팅 경로 설정 방법.

(1).
제1항에 있어서,

상기 캐리어 감지 간섭 가중치는 동일한 공유 채널을 이용하는 경로에 속하는 링크들 또는 인접 경로에 속하는 링크들 간의 캐리어 감지 간섭을 나타내고,

상기 히든 노드 가중치는 동일한 경로 또는 인접 경로 내의 링크에 의하여 야기되는 히든 노드 문제를 나타내는 것을 특징으로 하는 라우팅 경로 설정 방법.
제1항에 있어서, 상기 무선 멀티 홉 네트워크는,

서로 다른 채널을 사용하는 다중 이종 무선 트랜스시버를 가진 노드들을 포함하는 것을 특징으로 하는 라우팅 경로 설정 방법.
제1항에 있어서,

상기 캐리어 감지 간섭 가중치는, 상기 경로 내의 특정 링크에서의 패킷 전송 시간 및 상기 경로 상의 패킷 재송신 횟수를 이용하여 연산되는 것을 특징으로 하는 라우팅 경로 설정 방법.
제4항에 있어서,

상기 패킷 전송 시간은, 고정 패킷 사이즈, 미리 할당된 로 링크(raw link) 대역폭 및 MAC 계층 프로토콜 프레임간 간격(inter-frame spacing) 및 제어 패킷을 이용하여 연산되는 것을 특징으로 하는 라우팅 경로 설정 방법.
제4항에 있어서,

상기 패킷 재송신 횟수는, 상기 특정 링크 상의 시간에 따른 가중치 정방향 및 역방향 전송률(weigthed forward and reverse delivery ratios)을 이용하여 연산되고, 상기 가중치 정방향 및 역방향 전송률은 연속적인 두 개의 전송률들에 지 수적 가중치 평균화 기법(exponential weighted averaging technique)을 적용하여 연산되는 것을 특징으로 하는 라우팅 경로 설정 방법.
제1항에 있어서,

상기 히든 노드 가중치는, 상기 경로 내의 특정 링크에 영향을 미치는 모든 히든 링크에 기인한 예상 충돌 횟수들 및 상기 특정 링크 상의 패킷 송신 시간을 이용하여 연산되는 것을 특징으로 하는 라우팅 경로 설정 방법.
제7항에 있어서,

상기 예상 충돌 횟수는, 히든 노드 충돌(Hidden Node Collision, HNCOL) 분석학적 모델에 따라서 히든 노드와의 충돌에 의해 패킷이 전송되는 횟수인 것을 특징으로 하는 라우팅 경로 설정 방법.
제7항에 있어서,

상기 히든 노드 가중치는 상기 히든 노드와의 충돌 확률을 이용하여 연산되고,

상기 히든 노드와의 충돌 확률은 하기의 식 2에 의해 연산되는 것을 특징으로 하는 라우팅 경로 설정 방법.

(2)

(상기 식 2에서 A,B는 노드를 의미하며, VP는 링크 A-B에서 히든 노드 충돌이 발생할 수 있는 기간이며, Data_pkt_TT는 데이터 패킷 전송 시간을 의미함.)
삭제
제1항 내지 제9항 중 어느 한 항의 방법을 컴퓨터에서 실행시키도록 하는 프로그램이 기록된 기록매체.
복수 개의 노드 및 두 개의 노드를 연결하는 복수 개의 링크를 포함하는 무선 멀티 홉 네트워크에서 소스 노드로부터 목적지 노드로 패킷을 전송하기 위한 라우팅 경로를 설정하기 위한 시스템에 있어서,

상기 링크들 각각의 캐리어 감지 간섭을 나타내는 캐리어 감지 간섭 가중치(carrier sense interference weight)를 연산하고, 상기 소스 노드 및 상기 목적지 노드를 연결하는 적어도 하나의 특정 경로(specific path)에 포함되는 링크들의 캐리어 감지 간섭 가중치를 조합하기 위한 캐리어 감지 간섭 가중치 합산 메커니즘;

상기 링크들 각각의 히든 노드 문제(hidden node problem)를 나타내는 히든 노드 가중치를 연산하고, 상기 경로에 포함되는 링크들의 히든 노드 가중치를 합산하는 히든 노드 가중치 합산 메커니즘; 및

상기 캐리어 감지 간섭 가중치 및 상기 히든 노드 가중치를 조합하여 링크의 라우팅 메트릭 값을 연산하고, 경로상 링크의 조합에 의한 총 데이터 전송 시간을 추정함으로써 데이터 전송 시간이 가장 짧은 경로를 상기 라우팅 경로로서 결정하는 라우팅 경로 결정 메커니즘을 포함하며,

상기 총 데이터 전송 시간은, 경로 p에서 캐리어 감지 간섭 효과에 의한 총 추정 패킷 전송 시간을 WCEPTT_CS라 하고, 히든 노드에 의한 총 추정 패킷 전송 시간을 CEPTT_HN이라고 하며, WCEPTT_CS 및 CEPTT_HN이 평활 인자(smoothing factor)
를 가지고 지수적 가중치 평균화 기법을 이용하여 조합된다는 조건하에, 하기의 식 3에 의해 결정되는 것을 특징으로 하는 것을 특징으로 하는 라우팅 경로 설정 시스템.

(3).
제12항에 있어서,

상기 캐리어 감지 간섭 가중치는 동일한 공유 채널을 이용하는 경로에 속하는 링크들 또는 인접 경로에 속하는 링크들 간의 캐리어 감지 간섭을 나타내고,

상기 히든 노드 가중치는 동일한 경로 또는 인접 경로 내의 링크에 의하여 야기되는 히든 노드 문제를 나타내는 것을 특징으로 하는 라우팅 경로 설정 시스템.
제12항에 있어서, 상기 무선 멀티 홉 네트워크는,

서로 다른 채널을 사용하는 다중 이종 무선 트랜스시버를 가진 노드들을 포함하는 것을 특징으로 하는 라우팅 경로 설정 시스템.
제12항에 있어서,

상기 캐리어 감지 간섭 가중치는, 상기 경로 내의 특정 링크에서의 패킷 전송 시간 및 상기 경로 상의 패킷 재송신 횟수를 이용하여 연산되는 것을 특징으로 하는 라우팅 경로 설정 시스템.
제15항에 있어서,

상기 패킷 전송 시간은, 고정 패킷 사이즈, 미리 할당된 로 링크(raw link) 대역폭 및 MAC 계층 프로토콜 프레임간 간격 및 제어 패킷을 이용하여 연산되는 것을 특징으로 하는 라우팅 경로 설정 시스템.
제15항에 있어서,

상기 패킷 재송신 횟수는, 상기 특정 링크 상의 시간에 따른 가중치 정방향 및 역방향 전송률(weigthed forward and reverse delivery ratios)을 이용하여 연산되고, 상기 가중치 정방향 및 역방향 전송률은 연속적인 두 개의 전송률들에 지수적 가중치 평균화 기법(exponential weighted averaging technique)을 적용하여 연산되는 것을 특징으로 하는 라우팅 경로 설정 시스템.
제12항에 있어서,

상기 히든 노드 가중치는, 상기 경로 내의 특정 링크에 영향을 미치는 모든 히든 링크에 기인한 예상 충돌 횟수들 및 상기 특정 링크 상의 패킷 송신 시간을 이용하여 연산되는 것을 특징으로 하는 라우팅 경로 설정 시스템.
제18항에 있어서,

상기 예상 충돌 횟수는, 히든 노드 충돌(Hidden Node Collision, HNCOL) 분석학적 모델에 따라서 히든 노드와의 충돌에 의해 패킷이 전송되는 횟수인 것을 특징으로 하는 라우팅 경로 설정 시스템.
삭제