KR101616278B1 - 모바일 애드혹 네트워크에서 그리드 기반 혼합형 라우팅 시스템 및 방법 - Google Patents

Abstract

본 발명은 그리드 기반 혼합형 라우팅 시스템 및 방법에 관한 것으로서, 각 노드가 목적지 노드와의 방향성 및 이웃 노드의 정보를 고려하여 라우팅 경로를 탐색하도록 구성되는 경로 탐색부, 소스 노드에서부터 RREQ(Route Request) 메시지를 전송하면서 상기 라우팅 경로 상에 존재하는 노드들 사이의 최소 연결 가능 시간과 상기 소스 노드에서 상기 목적지 노드까지의 홉 수를 계산하게 하고, 상기 목적지 노드가 상기 최소 연결 가능 시간과 상기 홉 수를 고려하여 데이터를 전송할 최적의 라우팅 경로를 선택하도록 구성되는 경로 선택부 및 초기 설정된 라우팅 경로로 데이터를 전송하지 못하고 노드로의 전송이 실패한 경우 문제가 발생한 노드의 바로 이전 노드에서 상기 목적지 노드에 대한 라우팅 경로를 재탐색하도록 구성되는 경로 갱신부를 포함함으로써, 라우팅 경로 생성을 위한 메시지 전송을 감소시키고, 헤더 선택, 이웃 노드 관리, 경로 검색 및 응답 절차 등의 많은 관리 비용을 감소시키며, 대체 경로 생성을 위한 비용을 감소시킬 수 있다.

Description

모바일 애드혹 네트워크에서 그리드 기반 혼합형 라우팅 시스템 및 방법{Grid Based Hybrid Routing System and Method in Mobile Ad-hoc Networks}

본 발명은 혼합형 라우팅 시스템 및 방법에 관한 것으로, 더욱 상세하게는 그리드 기반의 환경에서 연결성을 고려하여 라우팅 경로를 생성하고 유지하는 위치 기반 혼합형 라우팅 시스템 및 방법에 관한 것이다.

무선 통신 및 휴대용 컴퓨팅 장치가 발전하면서 모바일 기기 사용이 급증함에 따라 모바일 애드혹 네트워크(MANET; Mobile Ad-hoc Network)에 많은 관심이 집중되고 있다. MANET은 망 설치와 확장이 용이하고 멀티 홉 통신을 통해 넓은 범위의 통신이 가능하다. 이러한 특징을 갖는 MANET은 재해 지역, 군사 환경 등에서 다양하게 응용되고 있다. 또한, MANET은 네트워크 인프라 없이 무선 링크를 통해 서로 통신하는 자율 이동 노드의 집합으로 구성된다. 즉, 기지국이나 AP(access point)와 같은 중계기 없이 이동 노드들 간에 자체적으로 네트워크를 구성한다. MANET은 예측 불가능한 이동성과 한정적인 전력 및 대역폭으로 인해 네트워크 토폴로지가 역동적으로 변하는 특성이 있다. 이러한 특성으로 노드들은 자유롭고 예측 불가능하게 움직이기 때문에 목적지까지의 메시지 전송 경로는 자주 끊어지게 되며 이는 네트워크의 전체적인 성능을 감소시킨다. 따라서, 이를 위해 MANET에서는 네트워크 변화에 효과적으로 대응할 수 있는 안정성이 우수한 다양한 라우팅 프로토콜이 활발히 연구되고 있다. 또한, 최근 스마트폰, 태블릿 PC 등의 사용증가와 더불어 이 기기들을 더 빠르고 안정적으로 뒷받침해 줄 수 있는 MANET 환경에 대한 연구가 지속적으로 요구되고 있다.

MANET의 라우팅은 노드 간 링크 정보를 이용하여 언제, 어떻게 경로를 발견하는지에 따라 프로액티브(proactive), 리액티브(reactive), 하이브리드(hybrid) 프로토콜로 구분된다. 프로액티브 방식의 라우팅에서는 네트워크를 구성하는 각 노드들이 네트워크 내 모든 목적지에 대한 라우팅 경로 정보를 관리한다. 이러한 프로액티브 방식의 라우팅은 모든 노드가 항상 최신의 라우팅 정보와 결과를 유지하기 때문에 서비스 지연은 발생하지 않으나 최신의 라우팅 테이블 구축 및 관리를 위한 추가 오버헤드 비용이 발생한다. 이러한 오버헤드 문제를 해결하기 위해 온디맨드(on-demand) 방식의 리액티브 라우팅 프로토콜이 소개되었다. 리액티브 방식의 라우팅은 소스 노드가 실제 데이터를 전송하는 과정에서 라우팅 정보가 필요할 때 RREQ(Route Request) 메시지를 브로드캐스팅한다. 이러한 리액티브 방식의 라우팅에서는 모든 노드들이 라우팅 경로를 관리하지 않고, 필요한 경우에만 경로를 탐색하여 데이터를 전송하기 때문에 프로액티브 방식에 비하여 주기적인 트래픽이 감소한다는 장점이 있다. 그러나, 리액티브 라우팅 방식은 MANET에서 자주 발생하는 토폴로지 변경으로 인해 경로 탐색에 많은 제어 패킷을 생성하고 데이터 전송 또는 정보 공유가 필요할 때 제어 메시지를 사용하여 라우팅 경로를 탐색하는 과정을 수행하기 때문에 최신 라우팅 정보를 얻기 위해 높은 지연을 초래하는 단점을 가진다. 하이브리드 방식은 프로액티브 라우팅 방식과 리액티브 라우팅 방식을 혼합한 형태로 각 노드가 사전에 가까운 거리에 있는 이웃 노드의 라우팅 정보를 유지하고, 필요한 경우에만 멀리 있는 노드의 경로 생성을 요구하는 라우팅 방식이다. 하이브리드 방식의 ZRP(Zone Routing Protocol) 알고리즘은 경로의 홉 수를 기준으로 특정 영역을 정의하고 특정 홉 이내에 존재하는 노드들의 라우팅 정보만을 관리한다. 즉, 영역 내의 노드들을 대상으로는 프로액티브 방식을, 영역 외의 노드들을 대상으로는 리액티브 방식을 선택적으로 적용하여 기존의 프로액티브 방식과 리액티브 방식의 문제점을 해결하였다. ZRP는 주기적 정보 교환을 특정 영역 내에 위치한 근거리 목적지 노드들로 한정시킴으로써 경로 탐색을 위한 플러딩(flooding) 메시지 수를 감소시켜 트래픽 오버헤드를 저하시키는 효과를 제공한다. 하지만, ZRP는 정해진 특정 홉 이내의 모든 노드를 대상으로 일괄적인 프로액티브 방식을 적용함으로써, 실제 통신이 거의 일어나지 않는 노드의 정보를 저장하고 통신이 빈번한 노드의 정보가 저장되지 않는 문제가 발생할 수 있다. 따라서, 이러한 Zone 방식의 라우팅에서는 실제로 빈번하게 데이터 전송이 발생되는 통신 경로를 파악하고, 이 경로에 대하여 Proactive 방식을 적용하는 요구가 반드시 필요하다.

노드 간 상대적인 위치 정보나 링크 상태를 가지고 라우팅 정보를 획득하는 기존의 방법과 달리 위치 정보를 이용하여 라우팅을 하는 방법에 대해서도 연구가 이루어지고 있다. 위치 서비스는 목적지의 위치를 결정하고 패킷의 목적지 주소를 포함하도록 패킷의 송신자에 의해 사용된다. 위치 기반 라우팅은 경로 설정을 위해 노드의 물리적 위치 정보를 이용한다. 노드는 GPS와 위치 서비스를 통해 자신과 목적지의 지리적 위치를 얻을 수 있다. 위치 정보의 가용성은 응용 프로그램 수준에서뿐만 아니라 네트워크 수준에서 광범위한 영향을 주게 된다. 노드의 물리적 위치의 사용이 모바일 애드혹 네트워크 라우팅 기술의 효율성을 향상시킬 수 있다. 위치 기반 라우팅은 많은 오버헤드를 차지하는 라우팅 경로 설정 및 유지를 필요로 하지 않거나 제한적으로만 필요로 한다는 장점을 가진다. 또한, 위치 기반 라우팅은 확장성이 우수하다는 장점이 존재한다.

이러한 위치 기반의 서비스를 활용한 물리적 영역을 2D 그리드 영역으로 분할하는 그리드 라우팅 방법이 있다. MANET에서 라우팅 알고리즘의 대부분은 중간 노드의 ID로 구성되어 경로를 설정한다. 경로 상의 한 노드에 연결할 수 없게 되면 전체 경로가 파괴되고 경로 재 연결 또는 복구를 함에 있어 통신 과정에서 높은 라우팅 오버헤드와 데이터의 불연속성으로 이어질 수 있다. 그러나 그리드 라우팅은 대상 노드를 연결하는 가상 그리드의 경로를 통해 이루어지고 고정 크기의 그리드 네트워크 영역을 분할함으로써 경로 유지 비용은 감소되고 경로 손상의 확률을 줄여 수명을 연장한다. 각 그리드 영역에는 라우팅을 처리하는 헤드 노드가 존재하며 게이트웨이 노드라고도 한다. 각 그리드의 게이트웨이 노드는 통과하는 모든 패킷을 릴레이 하도록 선택된다. 그러나 네트워크의 처리량이 한정된 게이트웨이 노드가 패킷을 전송할 수 있다는 사실에 제한될 수 있다. 따라서, 게이트웨이 노드는 현재의 그리드 영역을 벗어날 경우 새로운 게이트웨이 노드를 선택하기 위해 많은 오버헤드가 소비된다. 노드 속도의 증가에 따라 오버헤드가 매우 높아진다.

살펴본 바와 같이, 기존 연구들은 라우팅 경로를 생성하고 유지하기 위해 전체 네트워크에 메시지를 전송하기 때문에 많은 통신비용이 요구되며 설정된 라우팅 경로를 통해 데이터 전송이 불가능할 경우 새로운 경로를 생성하기 위한 추가적인 비용이 발생한다. 또한 기존의 그리드 기반 라우팅은 각 영역에 헤더를 두어 여러 정보를 유지하기 때문에 헤더의 관리 비용이 증가한다. 이에, 모바일 Ad-hoc 네트워크 서비스를 제공하기 위해서는 노드 이동성에 따른 네트워크 토폴로지 변화에 적응적이며 소스 노드에서 목적지 노드까지 안정적으로 데이터를 전달할 수 있는 라우팅 기법이 필요한 실정이다.

대한민국 공개특허공보 제10-2012-0046048호(공개일 2012.05.09.) 대한민국 공개특허공보 제10-2010-0073947호(공개일 2010.07.01.)

따라서, 본 발명은 상기한 종래 기술의 문제점을 해결하기 위해 이루어진 것으로서, 본 발명의 목적은 헤더를 두지 않기 때문에 헤더 관리 비용이 감소하며 모든 노드가 메시지를 전송할 수 있고, 중간 노드들이 노드와 그리드간의 위치 관계에 기초하여 메시지를 중계하는 다음 홉을 결정하며, 각 그리드 영역의 좌표와 이웃 노드의 정보를 활용하여 노드의 방향성을 고려한 라우팅 경로를 탐색하고, 노드들 사이의 연결성을 고려하여 라우팅 경로를 유지하는 그리드 기반 혼합형 라우팅 시스템 및 방법을 제공하는데 있다.

상기와 같은 목적을 달성하기 위한 본 발명의 그리드 기반 혼합형 라우팅 시스템은, 각 노드가 목적지 노드와의 방향성 및 이웃 노드의 정보를 고려하여 라우팅 경로를 탐색하도록 구성되는 경로 탐색부, 소스 노드에서부터 RREQ(Route Request) 메시지를 전송하면서 상기 라우팅 경로 상에 존재하는 노드들 사이의 최소 연결 가능 시간과 상기 소스 노드에서 상기 목적지 노드까지의 홉 수를 계산하게 하고, 상기 목적지 노드가 상기 최소 연결 가능 시간과 상기 홉 수를 고려하여 데이터를 전송할 최적의 라우팅 경로를 선택하도록 구성되는 경로 선택부 및 초기 설정된 라우팅 경로로 데이터를 전송하지 못하고 노드로의 전송이 실패한 경우 문제가 발생한 노드의 바로 이전 노드에서 상기 목적지 노드에 대한 라우팅 경로를 재탐색하도록 구성되는 경로 갱신부를 포함한다.

한편, 본 발명의 그리드 기반 혼합형 라우팅 방법은, 경로 탐색부가 각 노드의 목적지 노드와의 방향성 및 이웃 노드의 정보를 고려하여 라우팅 경로를 탐색하도록 구성되는 경로 탐색 단계, 경로 선택부가 소스 노드에서부터 RREQ 메시지를 전송하면서 상기 라우팅 경로 상에 존재하는 노드들 사이의 최소 연결 가능 시간과 상기 소스 노드에서 상기 목적지 노드까지의 홉 수를 계산하게 하고, 상기 목적지 노드가 상기 최소 연결 가능 시간과 상기 홉 수를 고려하여 데이터를 전송할 최적의 라우팅 경로를 선택하는 경로 선택 단계 및 초기 설정된 라우팅 경로로 데이터를 전송하지 못하고 노드로의 전송이 실패한 경우, 경로 갱신부가 문제가 발생한 노드의 바로 이전 노드에서 상기 목적지 노드에 대한 라우팅 경로를 재탐색하는 단계를 포함한다.

상술한 바와 같이, 본 발명에 의한 그리드 기반 혼합형 라우팅 시스템 및 방법에 따르면, 목적지 노드의 위치 정보를 활용하여 목적지 노드 방향에 있는 일부 영역에만 메시지를 전송함으로써 라우팅 경로 생성을 위한 메시지 전송을 감소시키고, 소스 노드와 목적지 노드 사이에 연결성을 고려하여 안정된 라우팅 경로를 생성하며, 각 그리드 영역에 헤더를 두지 않음으로써 모든 노드가 메시지를 전달하는 후보가 될 수 있고 헤더 선택, 이웃 노드 관리, 경로 검색 및 응답 절차 등의 많은 관리 비용을 감소시키고, 모바일 노드의 이동으로 메시지 전송이 불가능할 경우 문제가 발생한 노드의 바로 이전 노드에서 새로 목적지 노드에 대한 대체 경로를 생성함으로써 대체 경로 생성을 위한 비용을 감소시킬 수 있다.

도 1은 본 발명의 바람직한 실시예에 따른 라우팅 시스템의 전체적인 구성을 개략적으로 나타낸 블록도이다.
도 2는 본 발명의 바람직한 실시예에 따른 라우팅 방법의 전체적인 처리 과정을 개략적으로 나타낸 그림이다.
도 3은 본 발명의 바람직한 실시예에 따른 라우팅 방법의 전체적인 처리 동작을 나타내는 흐름도이다.
도 4는 본 발명과 같은 그리드 라우팅 방법에서 일반적으로 사용되는 그리드 크기를 나타낸 그림이다.
도 5는 그리드의 측면 길이와 통신 범위 사이의 관계를 나타낸 그림이다.
도 6은 노드 4의 이웃 노드를 나타낸 것이다.
도 7은 노드 4에 대한 INNT(Intra Neighbor Node Table)를 나타낸 것이다.
도 8은 노드 4에 대한 NZNT(Neighbor Zone Node Table)를 나타낸 것이다.
도 9는 본 발명의 바람직한 실시예에 따라 좌표를 통해 방향성을 고려한 경로 탐색 과정을 나타내는 그림이다.
도 10은 도 9b의 경우를 예로 들어 소스 노드 12로부터 RREQ 메시지가 전송되는 경로 탐색 과정을 나타낸 그림이다.
도 11은 노드 12에 대한 INNT(Intra Neighbor Node Table)를 나타낸 것이다.
도 12는 노드 12에 대한 NZNT(Neighbor Zone Node Table)를 나타낸 것이다.
도 13은 본 발명의 바람직한 실시예를 따른 경로 선택 과정을 나타낸 그림이다.
도 14는 RREQ 메시지에 저장된 경로 정보를 나타낸 것이다.
도 15는 본 발명의 바람직한 실시예에 따라 부분 경로 갱신에 의하여 라우팅 경로가 새로 설정되는 과정 즉, 경로 복구 과정을 나타낸 그림이다.

이하, 본 발명의 그리드 기반 혼합형 라우팅 시스템 및 방법에 대하여 첨부된 도면을 참조하여 상세히 설명하기로 한다.

도 1은 본 발명의 바람직한 실시예에 따른 라우팅 시스템의 전체적인 구성을 개략적으로 나타낸 블록도이다.

도 1은 본 발명의 바람직한 실시예에 따른 라우팅 시스템의 전체적인 구성을 개략적으로 나타낸 블록도이다.

도 1을 참조하면, 본 발명의 그리드 기반 혼합 라우팅 시스템은 경로 탐색부(100), 경로 선택부(200) 및 경로 갱신부(300)를 포함하여 이루어진다.

먼저, 경로 탐색부(100)는 그리드 영역 하나의 크기를 노드의 통신 범위보다 크게 설정하고, 각 노드가 자신의 통신 범위 내에 존재하는 이웃 노드들에 대한 정보를 유지하고 이를 현재 노드가 존재하는 그리드 영역 내에 존재하는 노드들을 관리하는 INNT(Intra Neighbor Node Table)와 동일 좌표 영역 외에 존재하는 1홉 노드들을 관리하는 NZNT(Neighbor Zone Node Table)로 관리하며, 각 노드가 목적지 노드와의 방향성 및 이웃 노드의 정보를 고려하여 라우팅 경로를 탐색하도록 구성된다. 구체적으로, 경로 탐색부(100)는 현재 위치의 노드가 현재 노드가 위치하고 있는 그리드 영역(C_zone)의 좌표와 목적지 노드가 위치하고 있는 그리드 영역(DN_zone)의 좌표를 비교하여 목적지 노드 방향에 인접한 RREQ 메시지를 전송할 전달 영역(DV_zone)을 선택하고, 프록시 노드(proxy node)가 상기 NZNT를 검색하여 통신 가능한 이웃 영역(neighbor zone)의 좌표가 존재하는지 확인하고 좌표가 존재한다면 상기 INNT를 검색하여 이웃 영역으로 전송 가능한 노드를 찾아 메시지를 전송하도록 구성된다.

다음으로, 경로 선택부(200)는 소스 노드에서부터 RREQ(Route Request) 메시지를 전송하면서 연결 가능 시간과 홉 수를 계산하게 하고, 목적지 노드가 라우팅 경로 상에 존재하는 노드들 사이의 최소 연결 가능 시간과 소스 노드에서 목적지 노드까지의 홉 수를 고려하여 데이터를 전송할 최적의 라우팅 경로를 선택하도록 구성된다. 이때, 목적지 노드는 최소 연결 가능 시간이 길고 홉 수가 작은 경로를 최적의 라우팅 경로로 선택하게 된다.

마지막으로, 경로 갱신부(300)는 초기 설정된 라우팅 경로로 데이터를 전송하지 못하고 노드로의 전송이 실패한 경우 문제가 발생한 노드의 바로 이전 노드에서 목적지 노드에 대한 라우팅 경로를 재탐색하도록 구성된다. 특히, 본 발명의 경로 갱신부(300)는 메시지를 재전송받은 이전 홉 노드가 초기 설정된 라우팅 경로에 의한 다음 홉 노드가 그 메시지 전송에 필요 없음을 표시해두고 다른 이웃 노드를 그 메시지에 대한 다음 홉으로 검색하게 함으로써, 메시지가 특정 노드 사이에서 왔다갔다를 반복하는 이른바, 핑퐁 효과 발생을 방지할 수 있다.

그러면, 여기서 상기와 같이 구성된 시스템을 이용한 본 발명의 그리드 기반 혼합형 라우팅 방법에 대해 설명하기로 한다.

도 2는 본 발명의 바람직한 실시예에 따른 라우팅 방법의 전체적인 처리 과정을 개략적으로 나타낸 그림이다. 본 발명의 바람직한 실시예에 따르면, 라우팅 경로를 생성을 위해 소스 노드(3)는 목적지 노드(10)까지 RREQ(Route Request) 메시지를 전송하고 목적지 노드는 이에 대한 응답으로 RREP(Route Response) 메시지를 소스 노드(3)로 전송한다. 구체적으로, 본 발명의 바람직한 실시예에서 각 노드는 현재 자신의 위치 좌표와 목적지 노드의 좌표를 비교하여 목적지 방향에 있는 인접한 3개의 존(zone)에 RREQ 메시지를 전송한다. 즉, 소스 노드(3)는 목적지 방향으로 인전합 3개의 노드(12, 4, 37)로 RREQ 메시지를 전송하며, 메시지를 받은 노드들는 위와 같은 방법으로 목적지 노드(10)에 도달할 때까지 RREQ 메시지를 전송한다. RREQ 메시지를 받은 목적지 노드(10)는 RREQ 메시지에 포함된 경로들 중에서 연결성과 홉 수를 고려하여 최적의 라우팅 경로를 선택하고, 생성된 경로를 통해 RREP 메시지를 소스 노드(3)로 전송한다. RREP 메시지를 받은 소스 노드(3)은 RREP 메시지에 포함된 최적 경로를 통하여 목적지 노드로 실제 데이터를 전송한다. 실제 데이터는 소스 노드(3)에서부터 노드(4, 13, 28, 14, 21, 22, 1, 40, 25, 24, 49, 48)를 거쳐 목적지 노드(10)로 전송된다.

본 발명의 바람직한 실시예에 따른 라우팅 방법은 크게 라우팅 경로 탐색 단계, 경로 선택 단계 및 경로 복구 단계를 포함하여 이루어진다. 본 발명의 바람직한 실시예에 따른 라우팅 방법의 전체적인 처리 동작을 나타내는 흐름도는 도 3과 같다. 이때, 소스 노드는 GPS와 같은 위치 인식 장치를 통해 자신의 위치 정보와 목적지의 위치 정보를 미리 알고 있다고 가정한다.

도 3을 참조하면, 본 발명의 모든 노드는 동일 좌표 내에 존재하는 노드들과 주기적인 메시지를 통하여 이웃 노드들에 대한 정보를 유지하고 이를 테이블로 관리하며, 메시지를 전송할 때 현재 노드는 목적지 노드와 좌표를 비교하여(S110) 메시지를 전달할 영역을 선택한다(S120). 그리고, 이웃 노드에 대한 정보가 담긴 테이블을 검색하여(S130) 테이블에 전송가능한 노드가 존재하는지 판단한다(S140). 단계 S140 판단 결과, 테이블에 전송가능한 노드가 존재하면, 각 노드는 이러한 자신의 이웃 노드들과 목적지 노드의 위치 정보 및 이웃 노드의 정보를 기반으로 라우팅 경로를 생성하기 위한 RREQ 메시지를 전송한다(S150). 이때, 각 노드는 최적의 이웃 노드를 다음 중간 노드로 선택하고 이 노드로 데이터를 전달하여 점차적으로 목적지 노드로 데이터를 전송한다. 특히, 본 발명의 바람직한 실시예에 따르면, RREQ 메시지를 전달하면서 경로 연결성과 홉 수를 계산하여 더 빠르고 안정적인 전송을 할 수 있게 한다. 이와 같은 본 발명의 경로 탐색의 보다 구체적인 과정은 도 4 내지 도 8을 전제로 도 9 내지 도 12에서 상세하세 설명된다.

다음으로, RREQ 메시지를 전송받은 목적지 노드는 위치적으로 최적의 경로를 선택하여 소스 노드로 RREP 메시지를 전송함으로써(S210) 선택된 경로들이 모여 전체 네트워크에서 효과적인 라우팅을 형성하게 한다. 이와 같은 본 발명의 경로 선택의 자세한 과정은 도 13 및 도 14에서 보다 구체적으로 설명된다.

초기 설정된 라우팅 경로에 의해 메시지 전송 중 노드로의 전송이 실패할 경우에는(S310) 경로 복구 알고리즘에 따라 재 경로 탐색을 한다(S320). 이와 같은 본 발명의 경로 복구의 자세한 과정은 도 15에서 보다 구체적으로 설명된다.

도 4는 본 발명과 같은 그리드 라우팅 방법에서 일반적으로 사용되는 그리드 크기를 나타낸 그림으로서, 도 4a는 그리드 셀의 헤드 노드가 대각선으로 인접한 셀 이외의 주변에 있는 4개의 셀에 있는 노드와 통신하고, 도 4b는 셀 헤드 노드를 중심으로 이웃하는 8개 셀의 노드와 통신하며, 도 4c는 이웃하는 임의의 8개 셀의 노드와 통신한다. 도 5는 그리드의 측면 길이와 통신 범위 사이의 관계를 나타낸 그림이다. 여기서, d는 그리드의 길이, r은 통신 범위를 의미한다.

본 발명과 같은 그리드 기반 라우팅 프로토콜의 성능에 영향을 미치는 변수 중 하나는 그리드 크기이다. 메시지는 현재 영역에서 다른 영역으로 이동해야 한다. 다른 그리드 크기는 성능 파라미터(메시지 수, 전달률, 지연 시간 등)에 큰 차이의 결과를 가져올 수 있다. 본 발명의 바람직한 실시예에서는 그리드 영역 하나의 크기를 노드의 통신 범위보다 크게 설정함으로써 라우팅 비용을 감소시킬 수 있다. 1-홉 정보는 모두 알고 있으므로 통신 범위가 그리드 크기보다 커야 할 필요가 없고, 그리드 크기가 커서 관리해야 하는 zone의 수가 적다. 그리고 계층 구조인 헤더를 사용하지 않기 때문에 모든 노드가 메시지를 전송하는 후보가 될 수 있고 헤더 관리 비용이 발생하지 않는다. 따라서, 노드 관리 비용을 감소할 수 있다. 또한 경로 탐색 시 통신 가능한 모든 노드에게 RREQ 메시지를 보내지 않기 때문에 메시지 오버헤드가 감소한다.

도 6은 노드 4의 이웃 노드를 나타내며, 도 7 및 도 8은 각각 노드 4의 INNT(Intra Neighbor Node Table)와 NZNT(Neighbor Zone Node Table)를 나타낸다.

도 7 및 도 8에 도시된 바와 같이, 본 발명의 바람직한 실시예에 따른 각 노드는 주기적인 갱신 메시지를 통하여 자신의 통신 범위 내에 존재하는 이웃 노드들에 대한 정보를 INNT(Intra Neighbor Node Table)와 NZNT(Neighbor Zone Node Table) 2개의 테이블로 유지한다. INNT는 현재 노드가 존재하는 그리드 영역 내에 존재하는 노드들을 관리하고, NZNT는 동일 좌표 영역 외에 존재하는 1홉 노드들을 관리한다. 각 테이블은 <Node_ID, X_Coordinate, Y_Coordinate, Node_Velocity> 구조로 저장된다. 이때, Node_ID는 노드 식별자이고, X_Coordinate와 Y_Coordinate는 그리드 영역의 x축 y축 좌표이며, Node_Velocity는 노드가 이동하는 속도로서 x축과 y축으로 이동하는 속도 (Vx, Vy)로 나타낸다. 이러한 메시지를 통하여 각 노드는 자신이 속해 있는 그리드 영역 내의 정보를 관리하는 INNT와 영역 외의 정보를 관리하는 NZNT를 유지한다.

도 9는 본 발명의 바람직한 실시예에 따라 좌표를 통해 방향성을 고려한 경로 탐색 과정을 나타내는 그림이다.

본 발명의 바람직한 실시예에 따르면, 소스 노드로부터 목적지 노드까지 실제 데이터를 빠르고 안정적으로 전송하기 위한 최적의 경로를 확립하고 선택하기 위해 먼저 경로 탐색 과정을 수행한다. 기존 모바일 애드혹 네트워크 환경에서의 라우팅 기법은 브로드캐스트 방식을 사용하여 RREQ 메시지를 목적지 노드까지 전송하고, RREQ 메시지를 수신한 목적지 노드는 소스 노드에게 응답으로 RREP 메시지를 전송한다. 그러나 이러한 방법은 전송해야 할 메시지 수가 기하급수적으로 증가할 수 있고, 라우팅 비용이 증가한다. 또한, RREQ 메시지를 전송하는 과정에서 더 이상 메시지를 전송할 수 있는 노드가 존재하지 않을 경우에는 메시지를 우회하거나 중복 경로에 메시지를 전송하게 된다. 이러한 문제점을 해결하기 위해 본 발명의 바람직한 실시예에서는 경로를 탐색할 때 목적지 노드와의 방향성과 이웃 노드의 정보를 고려한다.

본 발명의 바람직한 실시예에 따른 경로 탐색 방법에서는 C_zone(Current zone)의 좌표와 DN_zone(destination zone)의 좌표를 비교하여 메시지를 전달할 DV_zone(delivery zone)을 선택한다. C_zone은 현재 노드가 위치하고 있는 그리드 영역, DN_zone은 목적지 노드가 위치하고 있는 그리드 영역, 그리고 DV_zone은 현재 위치하고 있는 C_zone의 노드가 메시지를 전달해야 하는 그리드 영역을 의미한다. 현재 위치의 노드는 C_zone의 좌표와 DN_zone의 좌표를 비교하여 목적지 노드 방향에 있는 인접한 DV_zone을 선택하여 RREQ 메시지를 전송한다. 도 9는 C_zone을 중심으로 이웃한 3개의 DV_zone을 나타낸다. 이때, x_c는 C_zone의 x좌표, x_d는 DN_zone의 x좌표, y_c는 C_zone의 y좌표, y_d는 DN_zone의 y좌표를 의미한다. C_zone에 있는 current node는 이웃한 3개의 DV_zone에 모두 메시지를 전송한다. 즉, 도 9a와 같이 C_zone의 x축 값이 DN_zone의 x축 값보다 크고 C_zone의 y축 값이 DN_zone의 y축 값보다 작거나 같으면, 좌측 상단에 있는 3개의 영역이 DV_zone으로 선택된다. 그리고, 도 9b와 같이 C_zone의 x축 값이 DN_zone의 x축 값보다 작거나 같고 C_zone의 y축 값이 DN_zone의 y축 값보다 작거나 같으면, 우측 상단에 있는 3개의 영역이 DV_zone으로 선택된다. 이와 마찬가지로, 도 9c에서 C_zone의 x축 값이 DN_zone의 x축 값보다 크고 C_zone의 y축 값이 DN_zone의 y축 값보다 작으면, 좌측 하단에 있는 3개의 영역이 DV_zone으로 선택된다. 그리고, 도 9d에서 C_zone의 x축 값이 DN_zone의 x축 값보다 작거나 같고 C_zone의 y축 값이 DN_zone의 y축 값보다 크면, 우측 하단에 있는 3개의 영역이 DV_zone으로 선택된다.

그 후, DV_zone으로 선택된 3개의 A-zone, B-zone, C-zone에서 가장 먼저 메시지를 수신한 노드 즉, 다른 C_zone으로부터 직접 메시지를 수신한 노드를 프록시 노드(proxy node)라 할 때, 프록시 노드는 자신이 관리하고 있는 2개의 테이블을 검색한다. 먼저 NZNT를 검색하여 통신 가능한 이웃 영역(neighbor zone)의 좌표가 존재하는지 확인한다. 좌표가 존재한다면 다음으로 INNT를 검색하여 이웃 영역(neighbor zone)으로 전송 가능한 노드를 찾아 메시지를 전송한다. NZNT에 노드에 대한 정보가 없어서 이웃 영역(neighbor zone)으로 전송이 불가능한 경우에는 더 이상 메시지를 전송하지 않는다.

도 10은 도 9b의 경우를 예로 들어 소스 노드 12로부터 RREQ 메시지가 전송되는 경로 탐색 과정을 나타낸 그림이다. 도 11 및 도 12는 노드 12의 INNT와 NZNT 테이블을 나타낸 것이다.

도 10 내지 도 12를 참조하면, 검은색으로 나타낸 노드는 소스 노드이며 회색으로 표시된 노드가 프록시 노드이다. 각 노드들은 주기적인 업데이트 메시지를 통하여 현재 자신이 속한 그리드 영역 내의 이웃 노드 정보를 공유한다. 따라서, 소스 노드가 속한 그리드 영역 (1, 1)의 모든 노드는 같은 영역 내의 이웃 노드 정보를 알고 있고, 어떤 노드가 다른 그리드 영역의 노드와 연결 가능한지 파악할 수 있다.

도 13은 본 발명의 바람직한 실시예를 따른 경로 선택 과정을 나타낸 그림이다.

라우팅 기법에서는 소스 노드에서 목적지 노드로 RREQ 메시지를 전송하고, RREQ 메시지를 받은 목적지 노드는 이에 대한 응답으로 RREP 메시지를 수신한다. 이 과정에서 데이터 전송이 가능한 다수의 경로가 존재할 경우 실제 데이터를 전송할 최적의 라우팅 경로를 결정하는 것에 따른 비용이 증가한다. 따라서, 본 발명의 바람직한 실시예에 따른 라우팅 방법에서는 연결 가능 시간과 홉 수를 고려하여 데이터를 전송할 최적의 라우팅 경로를 선택한다. 소스 노드에서 목적지 노드로 RREQ 메시지를 전송하고, RREQ 메시지를 받은 목적지 노드가 데이터를 전송할 최적의 라우팅 경로를 결정하고 이 정보를 RREP 메시지에 포함하여 선택한 경로를 따라 소스 노드로 전송한다. 연결 가능 시간을 고려함으로써 더 긴 시간 동안 연결이 가능한 노드와 통신하여 더 안정적인 라우팅을 할 수 있고, 홉 수가 작은 경로를 통한 전송으로 통신비용을 줄이고 데이터를 더 빠르게 전달할 수 있다. 소스 노드에서부터 RREQ 메시지를 전송하면서 연결 가능 시간과 홉 수를 계산한다. RREQ 메시지를 받은 목적지 노드는 메시지에 포함된 정보를 이용하여 데이터를 전송할 최적의 라우팅 경로를 결정하고, 그 정보를 RREP 메시지에 포함하여 소스 노드로 전송한다. 그리고, RREP 메시지를 받은 소스 노드는 수신한 메시지에 포함된 정보를 이용하여 목적지 노드로 데이터를 전송할 최적의 라우팅 경로를 생성한다.

데이터 전송 비용은 소스 노드에서 목적지 노드까지의 홉 수에 의해 결정된다. 각 노드들 사이에 통신 가능한 시간이 짧을 경우 데이터를 전송하는 과정에서 대체 경로를 생성해야 하는 추가 비용이 발생한다. 이에, 본 발명의 바람직한 실시예에 따른 라우팅 방법에서는 경로 연결성과 홉 수를 모두 고려하여 실제 데이터를 전송할 라우팅 경로를 결정한다. 라우팅 경로는 수학식 1에 의해 결정되며 RSV(Route Selection Value)가 가장 큰 경로를 선택한다. RSV는 경로를 선택하는데 사용되는 값으로서 연결 가능 시간이 길고 홉 수가 작을수록 높은 값을 가진다.

경로 연결성은 라우팅 경로 상에 존재하는 노드들 사이의 최소 연결 가능 시간으로 정의한다. 소스 노드에서 목적지 노드로 데이터를 전송하기 위한 라우팅 경로 Ri가 {Ni₁,Ni₂,Ni₃, ..., Ni_k}라고 할 때, 경로의 연결 가능 시간 RCT(R_i)는 수학식 2와 같다. 수학식 2는 라우팅 경로 상에 존재하는 노드들 사이에 안정적으로 통신 가능한 시간을 계산한 것으로 이웃 노드들 사이에 통신 가능한 시간 CTI_i 의 최소값으로 계산한다. 수학식 2에서 CTI_i 는 라우팅 경로 상에 이웃한 두 노드들 사이의 최대 연결 가능 시간으로 수학식 3과 같이 계산한다. MAX(t)는 두 노드 사이의 최대 연결 가능 시간을 의미한다. 본 발명의 바람직한 실시예에서는 RREQ 메시지를 전송하면서 RREQ 메시지를 전송하는 노드의 현재 위치와 속도(Velocity)를 RREQ 메시지에 포함하여 전송한다. 이를 통해 각 노드에 대한 t 시점의 위치를 계산한다. t 시점에서 노드 Nij의 위치를 Pt(Ni_ij)라고 할 때 MAX(t)는｜Pt(N_ij) - Pt(N_ij+1)｜≤ R을 만족하는 최대 시각으로 이웃한 두 노드 N_ij와 N_ij+1의 최대 통신 가능 시각을 나타낸다. 또한, Tout은 현재 시각을 나타내며 ｜Pt(N0_ij) - Pt(N_ij+1)｜는 t 시점에서 노드 N_ij와 N_ij+1 의 거리를 의미한다.

도 13은 본 발명의 바람직한 실시예를 따른 경로 선택 과정을 나타낸 그림으로서, RREQ 메시지에 포함된 경로 정보는 도 14와 같다.

도 14를 참조하면, 소스 노드로부터 목적지 노드까지 총 4개의 경로가 있으며 각 경로는 경로명, 노드 ID, 홉 수, 연결성으로 나타낸다. 이때, 목적지 노드는 수학식 1의 RSV를 계산하여 4개의 경로 중에서 데이터를 전송할 하나의 최적의 경로를 선택한다. 도 14의 각 경로에 대해 RSV를 계산하면 R₁은 2.2, R₂는 1.8, R₃는 1.7, R₄는 1.6이 나오므로 값이 가장 큰 R₁이 최적의 경로로 선택된다. 그 다음, 목적지 노드는 선택된 경로 R₁의 경로를 따라 R₁의 경로 정보를 RREP 메시지에 포함하여 소스 노드로 전송한다. RREP 메시지를 받은 소스 노드는 이 경로를 따라 실제 데이터를 목적지 노드까지 전달한다.

도 15는 본 발명의 바람직한 실시예에 따라 부분 경로 갱신에 의하여 라우팅 경로가 새로 설정되는 과정 즉, 경로 복구 과정을 나타낸 그림이다.

MANET 환경에서는 노드의 이동성으로 인하여 Hello 메시지를 일정 시간 이상 보지 못하거나 이웃 노드가 다른 위치로 이동 등으로 인하여 초기 설정된 라우팅 경로로 데이터를 전송하지 못하는 경우가 빈번히 발생한다. 따라서, 데이터 전송을 수행할 대체 경로를 생성해야 한다. 만약 데이터를 전송하는 과정에서 초기 라우팅 경로를 생성하는 것과 동일한 절차를 통해 대체 경로를 생성할 경우, 전송 지연은 물론 경로 요청 및 응답 메시지를 추가적으로 전송해야 한다. 이러한 문제점을 해결하기 위해 본 발명의 바람직한 실시예에 따른 라우팅 방법에서는 부분 경로 갱신을 사용한다. 기존 방법에서는 전송에 실패할 경우 에러 메시지를 소스 노드까지 보내고 메시지를 받은 소스 노드는 전송 가능한 경로를 다시 찾기 위해 경로 재 탐색을 시작하기 때문에 많은 시간과 추가적인 비용이 발생한다. 하지만, 본 발명의 바람직한 실시예에 따른 라우팅 방법에서는 문제가 발생한 노드의 바로 이전 노드에서 새로 목적지 노드에 대한 라우팅 경로를 찾기 때문에 기존 방법에 비해 빠르게 이루어진다. 이전 노드로 메시지를 다시 전달하여 라우팅을 다시 할 수 있도록 해주면 메시지 폐기가 감소될 수 있다. 이와 같은 재경로 탐색에 적용되는 기법을 백오프(back off) 방법이라 한다. 그러나 이와 같은 백오프 방법을 라우팅 방법에 단순하게 적용하면 메시지가 특정 노드 사이에서 왔다갔다 반복하는 핑퐁 효과가 발생할 수 있다. 이로 인하여 메시지가 계속 전송되고 있음에도 불구하고 최종 목적지 노드까지 전송될 수 없게 된다. 이러한 문제점을 벗어나기 위해 본 발명의 바람직한 실시예에 따른 라우팅 방법의 경로 갱신 과정에서는 백오프 방법에 의해 재전송되는 메시지를 다시 받은 이전 홉 노드는 기본 라우팅 방법에 의한 다음 홉 노드가 그 메시지 전송에 필요 없음을 표시해두고 다른 이웃 노드를 그 메시지에 대한 다음 홉으로 검색해야 한다.

도 15를 참조하면, 노드 1에 문제가 생겨 더 이상 그 라우팅 경로를 사용할 수 없게 되었다고 가정할 때, 노드 22에서 노드 1의 메시지를 더 이상 수신할 수 없게 되어 노드 1을 사용할 수 없다. 따라서, 노드 1 의 바로 이전 노드인 노드 22의 테이블에서 이웃 노드 1을 삭제하고 새로 라우팅 경로를 찾게 된다. 이러한 경우 노드 22에서 새로 갱신된 이웃 테이블을 사용하여 목적지 노드에 대한 홉 노드 2를 찾아서 메시지를 전달하게 된다. 그러면 노드 2에서 노드 53을 거쳐 목적지 노드로 메시지 전송이 이루어지게 된다. 따라서, 본 발명에서 제안하는 경로 복구 방법을 사용하면 자신의 주변 노드 정보만을 이용하여 자율적으로 메시지를 전송할 수 있는 경로를 찾을 수 있다.

살펴본 바와 같이, 본 발명의 그리드 기반 라우팅 시스템 및 방법은 하이브리드 라우팅을 사용하여 동일한 그리드 영역 내의 노드에 대한 라우팅 정보를 프로액티브(proactive) 방식으로 관리하여 경로 탐색 메시지를 최소화한다. 그리고 필요한 경우에만 리액티브(reactive) 방식으로 인접한 그리드 영역의 노드와 연결된 통신 가능한 노드를 통해 최적 경로를 제공함으로써 기존 방식에 비해 주기적 업데이트 메시지를 감소시킨다. 또한, 그리드를 통신 반경보다 더 크게 설정하고 헤더를 두지 않음으로써 계층 구조를 이용하지 않는다. 헤더는 그리드 영역 내의 모든 정보를 관리하며 메시지 전송을 담당한다. 그러나 헤더가 현재 그리드 영역에서 벗어나 다른 영역으로 이동하는 경우에는 새로운 헤더를 선출한다. 그러므로 헤더 관리 및 새로운 헤더 선출 등의 추가적인 비용이 증가하게 된다. 따라서 본 발명의 그리드 기반 라우팅 시스템 및 방법은 헤드 노드가 존재하지 않기 때문에 경로 상의 각 그리드의 모든 노드가 메시지를 전달하기 위한 후보가 될 수 있다. 각 중간 노드는 위치 관계와 그리드 구성을 기반으로 다음 홉을 결정한다. 메시지는 각 노드가 가지고 있는 라우팅 테이블을 통하여 지리적으로 원하는 그리드 영역에 가장 가까운 이웃 노드로 전달 될 수 있다. 이와 같이, 본 발명의 그리드 기반 라우팅 시스템 및 방법에서는 그리드 기반의 구조 안에 노드 정보를 유지한다는 측면에서 토폴로지를 구성하는 특정 노드의 변화에 큰 영향을 받지 않는 장점을 가진다.

이상에서 몇 가지 실시예를 들어 본 발명을 더욱 상세하게 설명하였으나, 본 발명은 반드시 이러한 실시예로 국한되는 것이 아니고 본 발명의 기술사상을 벗어나지 않는 범위 내에서 다양하게 변형실시될 수 있다.

100 : 경로 탐색부
200 : 경로 선택부
300 : 경로 갱신부

Claims (13)

1. 각 노드가 목적지 노드와의 방향성 및 이웃 노드의 정보를 고려하여 라우팅 경로를 탐색하도록 구성되는 경로 탐색부,
   소스 노드에서부터 RREQ(Route Request) 메시지를 전송하면서 상기 라우팅 경로 상에 존재하는 노드들 사이의 최소 연결 가능 시간과 상기 소스 노드에서 상기 목적지 노드까지의 홉 수를 계산하게 하고, 상기 목적지 노드가 상기 최소 연결 가능 시간과 상기 홉 수를 고려하여 데이터를 전송할 최적의 라우팅 경로를 선택하도록 구성되는 경로 선택부, 및
   초기 설정된 라우팅 경로로 데이터를 전송하지 못하고 노드로의 전송이 실패한 경우 문제가 발생한 노드의 바로 이전 노드에서 상기 목적지 노드에 대한 라우팅 경로를 재탐색하도록 구성되는 경로 갱신부를 포함하며,
   상기 경로 탐색부는,
   각 노드가 자신의 통신 범위 내에 존재하는 이웃 노드들에 대한 정보를 유지하고 이를 현재 노드가 존재하는 그리드 영역 내에 존재하는 노드들을 관리하는 INNT(Intra Neighbor Node Table)와 동일 좌표 영역 외에 존재하는 1홉 노드들을 관리하는 NZNT(Neighbor Zone Node Table)로 관리하게 하며,
   상기 경로 탐색부는,
   상기 각 노드가 현재 노드가 위치하고 있는 그리드 영역(C_zone)의 좌표와 상기 목적지 노드가 위치하고 있는 그리드 영역(DN_zone)의 좌표를 비교하여 상기 목적지 노드 방향에 인접한 상기 RREQ 메시지를 전송할 전달 영역(DV_zone)을 선택하며, 프록시 노드(proxy node)가 상기 NZNT를 검색하여 통신 가능한 이웃 영역(neighbor zone)의 좌표가 존재하는지 확인하고 그러한 좌표가 존재한다면 상기 INNT를 검색하여 상기 이웃 영역으로 전송 가능한 노드를 찾아 상기 RREQ 메시지를 전송하도록 구성되는, 그리드 기반 혼합형 라우팅 시스템.
   
2. 청구항 제1항에서,
   상기 경로 탐색부는,
   그리드 영역 하나의 크기를 노드의 통신 범위보다 크게 설정하는, 그리드 기반 혼합형 라우팅 시스템.
   
3. 삭제
4. 삭제
5. 삭제
6. 청구항 제1항에서,
   상기 경로 선택부는,
   수학식 1 내지 수학식 3에 의해 RSV(Route Selection Value)가 가장 큰 경로를 최적의 라우팅 경로를 선택하는, 그리드 기반 혼합형 라우팅 시스템.
   (수학식 1)
   

   

   
   단,

   

   는 연결 가능 시간으로서 하기 수학식 2와 같고,

   

   는 상기 홉 수이다.
   (수학식 2)
   

   

   
   단,

   

   는 라우팅 경로 상에 이웃한 두 노드들 사이의 최대 연결 가능 시간으로서 하기 수학식 3과 같다. 여기서, k는 자연수이다.
   (수학식 3)
   

   

   
   단,

   

   는 두 노드 사이의 최대 연결 가능 시간,

   

   은 현재 시각이다.
   
7. 청구항 제1항에서,
   상기 경로 갱신부는,
   메시지를 재전송받은 상기 이전 노드가 초기 설정된 라우팅 경로에 의한 다음 노드가 상기 메시지 전송에 필요 없음을 표시해두고 다른 이웃 노드를 상기 메시지에 대한 다음 노드로 검색하게 하는, 그리드 기반 혼합형 라우팅 시스템.
   
8. 경로 탐색부가 각 노드의 목적지 노드와의 방향성 및 이웃 노드의 정보를 고려하여 라우팅 경로를 탐색하도록 구성되는 경로 탐색 단계,
   경로 선택부가 소스 노드에서부터 RREQ 메시지를 전송하면서 상기 라우팅 경로 상에 존재하는 노드들 사이의 최소 연결 가능 시간과 상기 소스 노드에서 상기 목적지 노드까지의 홉 수를 계산하게 하고, 상기 목적지 노드가 상기 최소 연결 가능 시간과 상기 홉 수를 고려하여 데이터를 전송할 최적의 라우팅 경로를 선택하는 경로 선택 단계, 및
   초기 설정된 라우팅 경로로 데이터를 전송하지 못하고 노드로의 전송이 실패한 경우, 경로 갱신부가 문제가 발생한 노드의 바로 이전 노드에서 상기 목적지 노드에 대한 라우팅 경로를 재탐색하는 단계를 포함하며,
   상기 경로 탐색 단계는,
   상기 경로 탐색부가 그리드 영역 하나의 크기를 노드의 통신 범위보다 크게 설정하는 단계, 및
   각 노드가 자신의 통신 범위 내에 존재하는 이웃 노드들에 대한 정보를 유지하고 이를 현재 노드가 존재하는 그리드 영역 내에 존재하는 노드들을 관리하는 INNT(Intra Neighbor Node Table)와 동일 좌표 영역 외에 존재하는 1홉 노드들을 관리하는 NZNT(Neighbor Zone Node Table)을 구성하는 단계를 포함하며,
   상기 경로 탐색 단계는,
   상기 각 노드가 현재 노드가 위치하고 있는 그리드 영역(C_zone)의 좌표와 상기 목적지 노드가 위치하고 있는 그리드 영역(DN_zone)의 좌표를 비교하여 상기 목적지 노드 방향에 인접한 상기 RREQ 메시지를 전송할 전달 영역(DV_zone)을 선택하는 단계,
   프록시 노드(proxy node)가 상기 NZNT를 검색하여 통신 가능한 이웃 영역(neighbor zone)의 좌표가 존재하는지 확인하는 단계, 및
   상기 이웃 영역의 좌표가 존재한다면 상기 INNT를 검색하여 상기 이웃 영역으로 전송 가능한 노드를 찾아 상기 RREQ 메시지를 전송하는 단계를 포함하는, 그리드 기반 혼합형 라우팅 방법.
   
9. 삭제
10. 삭제
11. 삭제
12. 청구항 제8항에서,
    상기 경로 선택 단계는,
    상기 경로 선택부가 하기 수학식 1 내지 수학식 3에 의해 RSV(Route Selection Value)가 가장 큰 경로를 최적의 라우팅 경로를 선택하는, 그리드 기반 혼합형 라우팅 방법.
    (수학식 1)
    

    

    
    단,

    

    는 연결 가능 시간으로서 하기 수학식 2와 같고,

    

    는 상기 홉 수이다.
    (수학식 2)
    

    

    
    단,

    

    는 라우팅 경로 상에 이웃한 두 노드들 사이의 최대 연결 가능 시간으로서 하기 수학식 3과 같다. 여기서, k는 자연수이다.
    (수학식 3)
    

    

    
    단,

    

    는 두 노드 사이의 최대 연결 가능 시간,

    

    은 현재 시각이다.
    
13. 청구항 제8항에서,
    상기 라우팅 경로를 재탐색하는 단계는,
    상기 경로 갱신부가 메시지를 재전송받은 상기 이전 노드가 초기 설정된 라우팅 경로에 의한 다음 노드가 상기 메시지 전송에 필요 없음을 표시해두고 다른 이웃 노드를 상기 메시지에 대한 다음 노드로 검색하게 하는, 그리드 기반 혼합형 라우팅 방법.

Images