KR100636805B1

KR100636805B1 - 이동성을 고려하여 라우팅 경로 설정이 가능한 애드 혹네트워크 및 그 라우팅 경로 설정방법

Info

Publication number: KR100636805B1
Application number: KR1020050004124A
Authority: KR
Inventors: 최영곤; 김정호; 김재훈; 노용성; 마크브라이언; 슈브란슈씽
Original assignee: 조지 매이슨 인털렉춸 프로퍼티즈, 인코퍼레이티드; 삼성전자주식회사
Priority date: 2005-01-17
Filing date: 2005-01-17
Publication date: 2006-10-23
Also published as: KR20060084109A; US20060165025A1; US8335511B2

Abstract

이동성을 고려하여 라우팅 경로 설정이 가능한 애드 혹 네트워크 및 그 라우팅 경로 설정방법이 개시된다. 본 애드 혹 네트워크는, 인접 노드가 자신의 전송 영역안에 존재할 확률을 산출하고, 산출한 확률을 포함하는 라우팅 요청 메세지를 생성하여 인접 노드로 전달하거나, 산출한 확률과 전달받은 라우팅 요청 메세지에 포함되어 있는 확률 중 낮은 확률로 라우팅 경로 요청 메세지를 갱신하여 인접 노드로 전달하거나, 전달받은 적어도 하나의 라우팅 요청 메세지에 포함되어 있는 확률 중 가장 높은 확률을 포함하고 있는 라우팅 요청 메세지를 전송한 경로를 라우팅 경로로 설정하는 적어도 하나의 노드를 포함한다. 이에 의해, 링크 안정 메트릭을 이용하여 안정한 라우팅 경로의 설정이 가능하며, 노드들의 이동성을 고려하여 다음 상태를 미리 예측함으로써 라우팅 경로를 유지, 보수, 및 재 설정하는 것이 가능하다.

애드 혹 네트워크, 이동성, 링크안정메트릭, 라우트안정메트릭

Description

이동성을 고려하여 라우팅 경로 설정이 가능한 애드 혹 네트워크 및 그 라우팅 경로 설정방법{Ad hoc network for setting up routing path under mobility's consideration and routing path setting up method thereof}

도 1은 일반적인 애드 혹 네트워크의 구성도,

도 2는 애드 혹 네트워크에서 라우팅 경로 설정 방법의 설명에 제공되는 도면,

도 3은 본 발명의 일 실시예에 따른 이동성을 고려하여 라우팅 경로를 설정하는 방법의 설명에 제공되는 도면, 그리고

도 4는 본 발명의 일 실시예에 따른 이동성을 고려하는 노드의 블럭도이다.

* 도면의 주요 부분에 대한 부호의 설명 *

A : 소스 노드 B,C,E,F,G : 노드

D : 목적지 노드 400,402,404,406 : 전송영역

본 발명은 애드 혹 네트워크 및 그 라우팅 경로 설정방법에 관한 것으로, 더욱 상세하게는, 애드 혹 네트워크를 구성하는 노드들의 이동성을 고려하여 소스 노 드가 목적지 노드로, 목적지 노드가 소스 노드로 데이터를 전송하기 위한 가장 안정적인 라우팅 경로를 설정하는 것이 가능한 애드 혹 네트워크 및 그 라우팅 경로 설정방법에 관한 것이다.

일반적인 이동통신 시스템은 이동단말(mobile element)과 기지국(base station)간에 데이터를 송수신한다. 이동단말과 기지국은 다른 이동단말 또는 노드(node)들을 경유하지 않고 직접 데이터를 송수신한다. 하지만, 애드 혹(Ad hoc) 네트워크에서는 소스 노드(Source node)의 데이터를 목적지 노드(Destination node)로 전달하고자 할 경우, 소스 노드와 목적지 노드 사이에 존재하는 다른 노드들을 이용하는 것이 가능하다.

이하 도 1을 이용하여 일반적인 애드 혹 네트워크의 구조에 대해 알아본다. 도 1에 도시되어 있는 바와 같이, 애드 혹 네트워크는 소스 노드와 복수 개의 노드들로 구성된다. 도 1은 하나의 소스 노드만을 도시하고 있으나, 사용자의 설정에 따라 애드 혹 네트워크는 적어도 2개의 소스 노드들로 구성될 수 있다.

소스 노드는 데이터를 목적지 노드로 전송한다. 목적지 노드는 소스 노드가 전송한 데이터를 전달 받는다. 목적지 노드로부터 일정 거리 이내에 위치하고 있는 소스 노드는 전송할 데이터를 직접 목적지 노드로 전달한다. 하지만, 일정 거리 이내에 위치하고 있지 않은 소스 노드는 데이터를 목적지 노드로 직접 전달할 수가 없다. 그러므로, 소스 노드는 목적지 노드로 직접 데이터를 전달하는 대신 목적지 노드에 인접한 노드들로 데이터를 전송한다. 상술한 바와 같이 일정 거리 이내에 위치하고 있지 않는 노드가 인접 노드들을 이용하여 데이터를 전송하는 이유는 데 이터 전송에 따른 전력 소모를 최소화하기 위해서이다. 즉, 소스 노드와 목적지 노드간의 거리와 소스 노드가 목적지 노드로 데이터를 전송하는데 소모되는 전력은 일반적으로 상호 비례한다. 따라서, 목적지 노드로부터 일정 거리 이내에 위치하고 있지 않은 소스 노드는 복수 개의 노드들을 이용하여 데이터를 전송함으로서 데이터 전송에 따른 전력소모를 최소화할 수 있게 된다.

도 2는 애드 혹 네트워크에서 라우팅 경로 설정 방법의 설명에 제공되는 도면이다. 이하 도 2를 참조하여, 소스 노드가 목적지 노드로 데이터를 전송하기 위한 라우팅 경로를 설정하는 방법에 대해 구체적으로 설명하기로 한다.

소스 노드인 노드 A는 자신의 위치 정보와 목적지 노드인 노드 D의 위치 정보를 포함한 라우팅 요청(routing request: RREQ) 메세지를 생성한다. 소스 노드는 생성한 RREQ메세지를 인접 노드들로 브로드캐스팅한다. 도 2에 의하여, 노드 B, 노드 C가 RREQ 메세지를 수신한다. RREQ 메세지를 수신한 노드 B, 노드 C는 RREQ메세지에 포함된 목적지 노드의 주소와 자신의 주소를 비교한다. 목적지 노드의 주소와 자신의 주소가 동일하지 않을 경우, 노드 B, 노드 C는 수신한 RREQ 메세지를 갱신한 후 인접 노드들로 브로드캐스팅한다. 갱신되는 정보에는 홉카운트가 포함된다.

소스 노드가 브로드캐스팅한 RREQ 메세지가 여러 경로를 거쳐 목적지 노드로 전달된다. 전달받은 RREQ 메세지에 포함된 목적지 노드의 주소와 자신의 주소가 동일한 경우 자신을 목적지 노드로 판단하며, 해당 목적지 노드는 전달된 RREQ 메세지에 포함되어 있는 홉카운트 중에서 홉카운트가 가장 작은 경로를 선택한다. 즉, 목적지 노드는 홉카운트가 2인 노드 B를 경유하는 경로를 선택한다. 그리고, 목적 지 노드는 소스 노드로 선택된 홉카운트가 가장 작은 경로의 정보를 포함한 라우팅 응답(routing reply: RREP) 메세지를 전송한다. 소스 노드는 전달받은 RREP메세지에 포함된 홉카운트가 가장 작은 경로를 라우팅 경로로 설정한다. 소스 노드는 설정된 라우팅 경로를 이용하여 노드 B를 경유하여 목적지 노드로 데이터를 전달한다.

상술한 과정과 같이, 소스 노드는 라우팅 경로를 설정하여 목적지 노드로 데이터를 전달한다. 그러나, 일반적으로 애드 혹 네트워크를 구성하고 있는 복수 개의 노드들은 고정되어 있는 것이 아니라 어느 정도 이동성이 보장된다. 그러므로, 노드들의 이동성으로 인해 설정된 라우팅 경로를 반복적으로 사용할 수 없는 문제가 발생할 수 있기 때문에, 노드들의 이동성이 고려된 라우팅 경로의 설정이 요구된다.

그런데, 노드들의 이동성을 고려하는 종래의 기술의 경우, 간단한 웨이 포인트 모델링(Random Waypoint Modeling)을 사용함으로써 실제 네트워크 환경의 실시간 라우팅 프로토콜에는 적용이 불가능하다. 노드들의 이동성을 고려하는 다른 기술의 경우에도, 이동성 모델링의 단순화를 위해 모든 노드들이 직선으로 등속 운동함을 가정하고 있어야만 한다.

그러나, 애드 혹 네트워크를 구성하는 노드들은 자유자제로 불규칙한 이동을 할 뿐만 아니라 이동 속도 또한 불규칙하다. 따라서, 종래의 이동성을 고려한 라우팅 경로 설정방법은 노드들의 이동성을 예측하는 것이 불가능하며, 실제 애드 혹 네트워크에 적용하여 불규칙한 노드들의 이동성을 고려한 안정한 라우팅 경로를 설 정하는 것이 불가능하다. 그러므로, 설정된 라우팅 경로에 위치하고 있는 노드가 이동하여 경로를 벗어날 경우에는 라우팅 경로를 재 설정하기 위해 오랜 시간이 소요되며, 라우팅 경로를 재 설정하는 동안에는 실시간 데이터를 전송하지 못하는 문제가 발생할 수 있다.

따라서, 본 발명의 목적은, 애드 혹 네트워크를 구성하는 노드들의 이동성을 고려하여 안정한 라우팅 경로 설정이 가능한 애드 혹 네트워크 및 그 라우팅 경로 설정방법을 제공함에 있다.

본 발명의 다른 목적은, 노드들이 이동성을 미리 예측하여 기설정된 라우팅 경로의 사용이 불가능해지기 전에 미리 안정한 라우팅 경로의 설정이 가능한 애드 혹 네트워크 및 그 라우팅 경로 설정방법을 제공함에 있다.

상기 목적을 달성하기 위한 본 발명에 따른 애드 혹 네트워크는, 인접 노드가 자신의 전송 영역안에 존재할 확률을 산출하고, 산출한 상기 확률을 포함하는 라우팅 요청 메세지를 생성하여 상기 인접 노드로 전달하거나, 산출한 상기 확률과 전달받은 상기 라우팅 요청 메세지에 포함되어 있는 확률 중 낮은 확률로 상기 라우팅 경로 요청 메세지를 갱신하여 상기 인접 노드로 전달하거나, 전달받은 적어도 하나의 라우팅 요청 메세지에 포함되어 있는 확률 중 가장 높은 확률을 포함하고 있는 라우팅 요청 메세지를 전송한 경로를 라우팅 경로로 설정하는 적어도 하나의 노드를 포함한다.

그리고, 상기 인접 노드가 전송 영역에 존재할 확률은, 링크 유지 여부를 판단하기 위한 링크 안정 메트릭인 것이 바람직하다.

그리고, 바람직하게는, 상기 링크 안정 메트릭은, GPS로부터 수신한 상태 정보를 이용해 산출한다.

그리고, 상기 상태 정보는, X축 위치, X축 속도, X축 가속도, Y축 위치, Y축 속도, Y축 가속도를 포함한다.

그리고, 바람직하게는, 상기 적어도 하나의 노드는, 자신의 상태 정보를 소정 주기로 상기 인접 노드로 전달하고, 상기 인접 노드로부터 전달된 상태 정보를 상기 소정 주기로 업데이트한다.

그리고, 바람직하게는, 상기 패킷에 포함된 확률 중 상기 가장 높은 확률은,상기 라우팅 경로의 설정을 위한 라우트 안정 메트릭이다.

상기 적어도 하나의 노드는, 동일한 라우트 안정 메트릭이 적어도 하나 이상이면 홉카운트가 가장 작은 경로를 상기 라우팅 경로로 설정하는 것이 바람직하다.

한편, 본 발명의 애드 혹 네트워크의 라우팅 경로 설정방법은, 인접 노드가 자신의 전송 영역안에 존재할 확률을 산출하고, 산출한 상기 확률을 포함하는 상기 라우팅 요청 메세지를 생성하여 상기 인접 노드로 전달하는 단계, 인접 노드가 자신의 전송 영역안에 존재할 확률을 산출하고, 산출한 상기 확률과 전달받은 라우팅 요청 메세지에 포함되어 있는 확률 중 낮은 확률로 상기 라우팅 경로 요청 메세지를 갱신하는 단계, 및 전달받은 적어도 하나의 라우팅 요청 메세지에 포함되어 있는 확률 중 가장 높은 확률을 포함하고 있는 라우팅 요청 메세지를 전송한 경로를 라우팅 경로로 설정하는 단계를 포함한다.

또한, 바람직하게는, 상기 링크 안정 메트릭은, GPS로부터 수신한 상태 정보를 이용해 산출한다.

바람직하게는, 상기 상태 정보는, X축 위치, X축 속도, X축 가속도, Y축 위치, Y축 속도, Y축 가속도를 포함한다.

그리고, 자신의 상태 정보를 소정 주기로 상기 인접 노드로 전달하고, 상기 인접 노드로부터 전달된 상태 정보를 상기 소정 주기로 업데이트하는 것이 바람직하다.

또한, 동일한 라우트 안정 메트릭이 적어도 하나 이상이면 홉카운트가 가장 작은 경로를 상기 라우팅 경로로 설정하는 것이 바람직하다.

또한, 본 발명에 따른 애드 혹 네트워크는, 기설정된 라우팅 경로 상에 위치하고 있는 인접 노드에 대해 산출한 자신의 전송 영역안에 존재할 확률이 소정 유효값보다 작으면 메세지를 전달하거나, 메세지를 전달받으면, 상기 기설정된 라우팅 경로를 보수 또는 재 설정하는 적어도 하나의 노드를 포함한다.

그리고, 상기 소정 유효값은, 상기 인접 노드가 자신의 전송 영역을 벗어나기 전의 임계치인 것이 바람직하다.

바람직하게는, 상기 메세지는, 링크 파손 메세지로, 기설정된 라우팅 경로의 파손을 나타낸다.

또한, 상기 적어도 하나의 노드는, 산출된 상기 확률이 상기 소정 유효값보다 크면 링크를 유지하는 것이 바람직하다.

그리고, 바람직하게는, 상기 적어도 하나의 노드는, 링크 안정 메트릭이 높은 노드를 이용하여 기설정된 상기 라우팅 경로를 보수 또는 저장된 라우트 안정 메트릭 중 높은 라우트 안정 메트릭을 전달한 경로를 라우팅 경로로 재 설정한다.

또한, 상기 적어도 하나의 노드는, 인접 노드의 다음 상태 정보를 산출하기 위한 파라미터를 산출하는 파라미터 산출부, 및 산출된 상기 파라미터를 이용해 상기 인접 노드의 다음 상태 정보를 산출하는 칼만 필터부를 포함하며, 산출된 상기 다음 상태 정보를 이용하여 상기 인접 노드가 다음 상태에 자신의 전송 영역에 존재할 확률을 산출하는 것이 바람직하다.

그리고, 바람직하게는, 상기 파라미터 산출부는, 율 워커 방정식을 이용하여 상기 파라미터를 산출한다.

한편, 본 발명에 따른 애드 혹 네트워크의 라우팅 경로 설정방법은, 기설정된 라우팅 경로 상에 위치하고 있는 인접 노드에 대해 산출한 자신의 전송 영역안에 존재할 확률이 소정 유효값보다 작으면 메세지를 상기 소스 노드로 전달하는 단계, 및 상기 메세지를 전달받으면, 상기 기설정된 라우팅 경로를 보수 또는 재 설정하는 단계를 포함한다.

바람직하게는, 상기 소정 유효값은, 상기 인접 노드가 자신의 전송 영역을 벗어나기 전의 임계치이다.

그리고, 상기 메세지는, 링크 파손 메세지로, 기설정된 라우팅 경로의 파손을 나타내는 것이 바람직하다.

또한, 바람직하게는, 산출된 상기 확률이 상기 소정 유효값보다 크면 링크를 유지한다.

그리고, 링크 안정 메트릭이 높은 노드를 이용하여 기설정된 상기 라우팅 경로를 보수 또는 저장된 라우트 안정 메트릭 중 높은 라우트 안정 메트릭을 전달한 경로를 라우팅 경로로 재 설정 중 어느 하나를 수행하는 것이 바람직하다.

또한, 바람직하게는, 인접 노드의 다음 상태 정보를 산출하기 위한 파라미터를 산출하는 단계, 및 산출된 상기 파라미터를 이용해 상기 인접 노드의 다음 상태 정보를 산출하는 단계를 더 포함하며, 산출된 상기 다음 상태 정보를 이용하여 상기 인접 노드가 다음 상태에 자신의 전송 영역에 존재할 확률을 산출한다.

그리고, 상기 파라미터를 산출하는 단계는, 율 워커 방정식을 이용하여 상기 파라미터를 산출하는 것이 바람직하다.

이하에서는 도면을 참조하여 본 발명을 상세하게 설명한다.

도 3은 본 발명의 일 실시예에 따른 이동성을 고려하여 라우팅 경로를 설정하는 방법의 설명에 제공되는 도면이다.

도 3을 참조하면, 애드 혹 네트워크는 소스 노드인 노드 A, 목적지 노드 D와 노드 B, 노드 C, 노드 E, 노드 F, 및 노드 G로 구성된다. 소스 노드와 목적지 노드 간에 데이터를 중계하는 노드 B, 노드 C, 노드 E, 노드 F, 및 노드 G를 중계 노드 라 한다. 소스 노드는 400의 전송 영역을 가지며, 노드 B는 402의 전송 영역, 노드 C는 404의 전송 영역, 노드 E는 406의 전송 영역을 가진다. 소스 노드는 노드들의 이동성을 고려하여 목적지 노드까지의 라우팅 경로를 설정한다.

구체적으로, 노드들은 GPS(Global Position System)로부터 자신의 이동 상태에 대한 정보를 수신한다. 상태 정보에는 자신의 X축 위치, X축 속도, X축 가속도 Y축 위치, Y축 속도, Y축 가속도에 대한 정보등이 포함되어 있다. 노드들은 수신한 상태 정보에 의해 자신의 현재 위치를 알 수 있다. 노드들은 수신한 상태 정보를 주기적으로 인접 이웃 노드들로 브로드캐스팅한다. 수신한 상태 정보를 브로드캐스팅하는 중간에 화이트 노이즈(white noise)에 의하여 상태 정보가 왜곡되어 부정확한 정보가 전달될 수 있으므로, 노드들은 상태 정보의 코베리언스(covariance) 값을 취한다. 그리고, 노드들은 상태 정보와 상태 정보의 코베리언스 값에 행렬 H를 붙여 (Hs, HMH')를 인접 이웃 노드들로 브로드캐스팅한다. s는 상태 정보이고, M = Cov(s)로 상태 정보의 코베리언스이며, H =

이다. 이에 의해, 노드들은 이웃 노드들의 위치를 알 수 있으며, 상태 정보에 포함된 자신의 위치와 이웃 노드의 위치에 의해 자신과 이웃 노드 사이의 거리를 알 수 있다.

소스 노드는 인접 이웃 노드인 노드 B, 노드 C로 상술한 방법에 의한 자신의 상태 정보를 주기적으로 브로드캐스팅한다. 그리고, 노드 B는 소스 노드, 목적지 노드, 노드 E로, 노드 C는 노드 A, 노드 E, 노드 F로, 노드 E는 노드 B, 노드 C, 목적지 노드로 상술한 방법에 의한 자신의 상태 정보를 주기적으로 브로드캐스팅한 다. 이에 의해, 소스 노드는 노드 B, 노드 C의 위치를 알며, 노드 B와의 거리, 및 노드 C와의 거리를 안다. 마찬가지로, 다른 노드들도 이웃 노드들의 위치, 및 이웃 노드들과의 거리를 안다.

소스 노드는 전송 영역 400 안에 존재하는 노드 B와의 링크 안정 메트릭(Link Stability Metric)을 산출한다.

수학식 1은 링크 안정 메트릭을 나타내는 것으로, 일정 시간 동안 자신의 전송 영역안에 다른 노드가 위치할 확률 즉, 자신과 다른 노드 사이의 링크가 유지될 확률을 나타낸다. 구체적으로, 링크 안정 메트릭은 어느 시간 n에서 k까지의 일정 시간 동안 전송 영역의 거리

안에 노드 p에서 노드 q까지의 링크

가 존재할 확률이다. 전송 영역의 거리

는 전송 인터페이스에 따라 다르며, 고정된 값으로 전송 영역 400, 402, 204, 406 모두 동일하다.

소스 노드는 노드 B가 전송 영역 400안에 존재하여, 노드 B와의 링크가 유지될 확률을 산출한다.

수학식 2는 노드 B가 소스 노드의 전송 영역 400안에 존재할 확률을 계산하는 식이다. 이 때, X, K,

값은 아래 수학식 3과 같다.

,

노드 B가 브로드캐스팅한 (Hs, HMH')을 이용하여 수학식 3을 계산할 수 있다. 이상에서의 수학식 2, 3을 이용하여, 소스 노드는 노드 C가 전송 영역 400안에 존재하여, 노드 C와의 링크가 유지될 확률을 산출한다.

링크 안정 메트릭이 산출되면, 소스 노드는 라우팅 경로 설정을 위한 RREQ메세지를 생성한다. 생성된 RREQ메세지에는 자신의 위치, 목적지 노드의 위치, 및 링크 안정 메트릭이 포함되어 있다. 초기 생성된 RREQ메세지에는 링크 안정 메트릭 값이 최대 값으로 설정된다. 소스 노드는 생성된 RREQ메세지를 전송 영역 400안에 존재하는 노드 B, 노드 C로 브로드캐스팅한다.

노드 B, 노드 C는 먼저 RREQ 메세지의 목적지 주소가 자신의 주소와 일치하는지를 확인한다. 일치하지 않는 경우, 수신한 RREQ 메세지에 포함되어 있는 전 링크의 링크 안정 메트릭과 산출된 링크 안정 메트릭을 비교한다. 노드 B, 노드 C는 수신한 RREQ 메세지에 포함된 링크 안정 메트릭을 비교 결과에 따라 더 작은 링크 안정 메트릭으로 갱신한 후 인접 노드들로 새로 생성된 RREQ 메세지를 브로드캐스팅한다. 노드 B, 노드 C의 경우 링크 안정 메트릭이 최대 값인 초기 RREQ 메세지지를 수신하였기 때문에 항상 소스 노드와 해당 노드와의 링크 안정 메트릭을 갱신하게 된다. 갱신되는 정보에는 홉카운트도 포함된다. 노드 B, 노드 C로부터 해당 RREQ 메세지를 수신한 다른 중계 노드들은 먼저 RREQ 메세지에 포함된 목적지 주소가 자신의 주소와 일치하는지를 확인한다. 일치하지 않는 경우, 수신한 RREQ 메세지에 포함된 링크 안정 메트릭과 해당 RREQ 메세지를 수신할 이웃 노드와의 링크 안정 메트릭을 비교하여 더 낮은 값을 새로 재 전송할 RREQ메세지에 갱신한 후, 이웃 노드로 재 전송한다. 상기 과정을 반복하면서 해당 경로의 안정성을 계산할 수 있으며, 가장 불안정한 링크의 링크 안정 메트릭이 전체 경로의 링크 안정 메트릭이 된다.

소스 노드가 브로드캐스팅한 RREQ 메시지가 상술한 과정을 반복하여 여러 경로를 거쳐 목적지 노드로 전달된다. 목적지 노드는 전달된 RREQ 메세지에 포함되어 있는 링크 안정 메트릭을 비교하여, 링크 안정 메트릭이 가장 높은 경로를 선택한다. 링크 안정 메트릭이 가장 높은 경로를 선택함으로써, 가장 안정한 경로가 라우 팅 경로가 된다. 일 예로, 소스 노드 - 노드 B - 목적지 노드의 경로로 전달된 RREQ 메세지에 포함되어 있는 링크 안정 메트릭이 2이고, 소스 노드 - 노드 B - 노드 E - 목적지 노드의 경로로 전달된 RREQ 메세지에 포함되어 있는 링크 안정 메트릭이 1, 소스 노드 - 노드 C - 노드 E - 목적지 노드의 경로로 전달된 RREQ 메세지에 포함되어 있는 링크 안정 메트릭이 3이라고 가정한다. 그러면, 목적지 노드는 전달된 RREQ 메세지에 포함되어 있는 링크 안정 메트릭이 3으로 가장 높은 소스 노드 - 노드 C - 노드 E - 목적지 노드의 경로를 선택한다. 이로써, 가장 안정한 링크 안정 메트릭을 가지는 경로가 소스 노드와 목적지 노드의 라우팅 경로가 된다.

이 때, 링크 안정 메트릭이 우선 메트릭이고, 홉카운트는 차선 메트릭으로써, 목적지 노드는 소스 노드 - 노드 B - 목적지 노드의 경로가 홉카운트 2로 가장 작지만 링크 안정 메트릭이 3으로 가장 높은 소스 노드 - 노드 C - 노드 E - 목적지 노드의 경로를 선택하는 것이 자명하다. 그러나, 링크 안정 메트릭이 동일한 경우가 발생하면, 차선 메트릭인 홉카운트를 비교하여, 홉카운트가 가장 작은 경로를 선택한다.

선택된 링크 안정 메트릭이 라우트 안정 메트릭(Route Stability Metric)이 된다. 라우트 안정 메트릭은 소스 노드와 목적지 노드 사이에 위치하는 노드들의 이동성을 고려하여 안정한 라우팅 경로를 설정하게 한다. 따라서, 링크 안정 메트릭 3이 라우팅 안정 메트릭이 된다. 목적지 노드는 라우터 안정 메트릭을 포함한 RREP메세지를 생성한다. 그리고, 목적지 노드는 생성된 RREP메세지를 소스 노드로 전송한다. 소스 노드는 전달받은 RREP메세지에 포함된 라우터 안정 메트릭 즉, 링 크 안정 메트릭이 가장 높은 경로를 라우팅 경로로 설정한다. 소스 노드는 설정된 라우팅 경로를 이용하여 목적지 노드로 데이터를 전달한다. 상기의 일 예에 따라, 소스 노드는 소스 노드 - 노드 C - 노드 E - 목적지 노드의 경로를 라우팅 경로로 설정하고, 설정된 라우팅 경로를 통해 목적지 노드로 데이터를 전달한다.

도 4를 참조하면, 애드 혹 네트워크를 구성하는 노드들은 이동성에 따른 다음 상태를 미리 예측하여 설정된 라우팅 경로를 유지하거나, 보수, 또는 재 설정하기 위해 칼만 필터(Kalman filter)부(510)와 파라미터 산출부(paramiter estimator)(520)를 구비한다.

노드들은 GPS로부터 자신의 이동 상태에 대한 상태 정보를 수신한다. 상태 정보가 GPS로부터 노드들로 수신되는 중간에, 또는 이웃 노드들로 브로드캐스팅되는 도중에 화이트 노이즈 등에 의하여 왜곡되어 부정확한 정보가 전달될 수 있다. 이 때, 칼만 필터부(510)는 노드들의 시간에 따른 이동 변화를 적절하게 예측할 수 있도록 노이즈로부터 정확한 노드들의 이동 변화를 찾아낸다. 파라미터 산출부(520)는 노드들의 이동 변화에 따른 다음 상태를 예측하기 위해 필요한 파라미터를 산출한다.

이하에서는 도 3를 참조하여 설정된 라우팅 경로인 소스 노드 - 노드 C - 노드 E - 목적지 노드의 경로를 일 예로 들어 노드들의 이동성 고려에 대해 구체적으로 설명하기로 한다. 노드들은 GPS로부터 자신의 X축 위치, X축 속도, X축 가속도 Y축 위치, Y축 속도, Y축 가속도에 대한 상태 정보

를 수신한다. 노드들은 수신된 자신의 상태 정보를 주기적으로 인접 이웃 노드들로 브로드캐스팅한다. 소스 노드는 설정된 라우팅 경로 상에 위치한 노드 C의 상태 정보를 전달받는다. 전달받은 노드 C의 상태 정보 은 소스 노드에 구비된 칼만 필터부(510)로 입력된다. 칼만 필터부(510)는 입력된 상태 정보

에서 노이즈를 제거한다.

수학식 4는 전달된 어느 시간 n에 노드의 상태 정보

를 이용해 노드의 이동성을 고려하여 다음 상태

를 예측하는 것을 나타낸다. 소스 노드는 수학식 4를 이용하여, 노드 C의 다음 상태를 예측하는 것이 가능하다.

는 6*6 변환 행렬이다.

은 6*1 플랜트(plant) 노이즈로 전달시 왜곡된 상태 정보를 보상해주고,

로 나타내며,

일때

이고,

일때

이다. 이 때,

는

의 코베리언스 행렬이다. 행렬

와

는 노드들의 이동 변화에 따른 다음 상태를 예측하기 위해 필요한 파라 미터로, 파라미터 산출부(520)에 의해 산출된다. 파라미터 산출부(520)는 율 워커(Yule Walker) 방정식를 이용해 행렬

와

를 산출한다.

(1)

(2)

(3)

(4)

(5)

수학식 5는 노드 C의 이동 변화에 따른 다음 상태를 예측하기 위한 파라미터

와

를 산출하기 위한 율 워커 방정식이다. 소스 노드에 구비된 파라미터 산출부(520)는 칼만 필터부(510)에 의해 노이즈가 제거된 노드 C의 상태 정보

와 수학식 5를 이용하여

와

를 산출한다. 구체적으로, 파라미터 산출부(520)는 식 (2),(3)를 이용하여 식 (1)를 통해 행렬

를 산출하고, 식 (2), (3), (5)를 이용하여 식 (4)를 통해 행렬

를 산출한다. 산출된

와

는 다시 칼만 필터부(510)로 입력된다. 칼만 필터부(510)는 입력된

와

를 이용하여, 노드 C의 이동 변화에 따른 다음 상태 정보

를 산출하여, 노드 C의 다음 상태를 예측한다.

(1)

(2)

(3)

(4)

(5)

(6)

수학식 6은

와

를 이용하여 노드 C의 이동 변화에 따른 다음 상태 를 예측하기 위한 식이다. 구체적으로, 식 (1)은 노드 C의 다음 상태의 예측값인

를 산출하는 식으로, 식 (2), (3), (4)를 이용한다. 칼만 필터부(510)는 파라미터 산출부(520)에 의해 산출되어 입력된

와

, 식 (2), (3), (4)를 이용한 식 (1)를 통해

를 산출한다. 이 때, 식 (2)의

은 현재 상태의 예측값이고,

은 이전 상태의 예측값이며,

은 측정값으로 노드 C로부터 전달받은 노드 C의 상태 정보

이다. 식 (3)의 H =

이다. 식 (5)는 노드 C의 다음 상태의 코베리언스 예측값인

을 산출하는 식으로, 식 (3), (4), (6)를 이용한다. 칼만 필터부(510)은 파라미터 산출부(520)에 의해 산출되어 입력된

와

, 식 (3), (4), (6)를 이용한 식 (5)를 통해

을 산출한다. 이 때, 식 (5), (6)의

은 현재 상태의 코베리언스 예측값이고,

은 이전 상태의 코베리언스 예측값이다. 그리고, 식 (5)의

는 항등원(identity) 행렬이다.

소스 노드는 수학식 5, 6를 이용하여 노드 C의 이동 변화에 따른 다음 상태 예측값과 다음 상태의 코베리언스 예측값을 산출한다. 그리고, 소스 노드는 산출된 예측값을 이용해 링크 안정 메트릭을 산출한다. 링크 안정 메트릭을 산출하는 과정은 도 3에서 수학식 2, 3으로 설명하였으므로 생략하기로 한다. 소스 노드는 산출 된 링크 안정 메트릭을 기설정된 소정 유효값과 비교한다. 소정 유효값은 인접 노드가 자신의 전송영역을 벗어나기 전의 임계치이다.

비교결과, 소스 노드는 링크 안정 메트릭이 기설정된 소정 유효값보다 작으면, 노드 C가 이동성에 의해 다음 상태에 전송 영역 400를 벗어나 노드 C와의 링크가 파손될 것이라고 예측한다. 소스 노드는 노드 C와의 링크가 파손될 것이라고 예측되면, 인접한 이웃 노드들과의 링크 안정 메트릭 중에서 안정한 링크 안정 메트릭을 가진 노드를 경유하는 것으로 기설정된 라우팅 경로를 보수한다. 또는, 소스 노드는 저장되어 있는 목적지 노드까지의 경로 중에서 기설정된 라우팅 경로 다음으로 안정한 라우트 안정 메트릭을 가진 경로를 라우팅 경로로 재 설정하는 것이 가능하다. 또한, 소스 노드는 RREQ메세지를 생성하여 다른 라우팅 경로를 재 설정하는 것이 가능하다. 라우팅 경로를 설정하는 방법은 도 3에서 설명하였으므로 생략한다.

반면, 소스 노드는 링크 안정 메트릭이 기설정된 소정 유효값보다 크면, 노드 C가 다음 상태에도 전송 영역 400를 벗어나지 않아 노드 C와의 링크가 안정할 것이라고 예측하고 기설정된 라우팅 경로를 유지한다.

노드 C는 이상에서 설명한 방법을 이용하여 노드 E의 다음 상태 예측값과 다음 상태의 코베리언스 예측값을 산출하여, 산출된 예측값에 의한 링크 안정 메트릭을 산출한다. 노드 C는 산출된 링크 안정 메트릭이 기설정된 소정 유효값보다 작으면, 노드 E가 다음 상태에 이동성에 의해 전송 영역 404를 벗어나 노드 E와의 링크가 파손될 것이라고 예측한다. 노드 C는 노드 E와의 링크가 파손될 것이라고 예측 되면, 링크 파손(Link Breakage)메세지를 생성하여 소스 노드로 전달한다. 링크 파손메세지는 기설정된 라우팅 경로가 가까운 미래에 파손될 것이라는 것을 나타낸다. 노드 C로부터 링크 파손메세지를 전달받은 소스 노드는 기설정된 라우팅 경로를 보수, 또는 재 설정한다. 마찬가지로, 노드 E는 이상에서 설명한 방법을 이용하여 목적지 노드의 다음 상태를 예측한다.

기설정된 라우팅 경로에 포함되어 있는 노드들의 이동성에 의해 링크가 파손될 것이라고 예측되어도, 소스 노드는 라우팅 경로를 보수, 또는 재 설정하는 동안에 기설정된 라우팅 경로를 통해 계속 목적지 노드로 데이터를 전송할 수 있다. 그리고, 링크가 파손되면 소스 노드는 보수된 라우팅 경로, 또는 재 설정된 라우팅 경로를 통해 목적지 노드로 데이터를 전송할 수 있다. 이로써, 링크 파손을 미리 예측하여 링크 파손 전까지만 설정된 라우팅 경로로 데이터를 전송하므로써, 링크 파손을 모르고 계속 데이터를 전송하여 데이터를 재 전송해야함에 의한 데이터 패킷의 손실을 줄이고 링크 파손의 인지부터 라우팅 경로의 재 설정까지 걸리는 시간을 줄여 데이터 통신이 끊기는 시간을 최소화하는 것이 가능하다.

이상에서는, 기설정된 라우팅 경로 상에 위치하는 노드들의 이동성에 따른 다음 상태를 미리 예측하여 라우팅 경로를 유지, 보수, 및 재 설정하는 것으로 설명하였으나, 현재 상태에서도 노드들의 이동성을 고려하여 라우팅 경로를 설정하고, 유지, 보수, 및 재 설정하는 것이 가능하다.

이상 설명한 바와 같이, 본 발명에 따르면, 링크 안정 메트릭을 이용하여 안 정한 라우팅 경로의 설정이 가능하며, 노드들의 이동성을 고려하여 다음 상태를 미리 예측함으로써 라우팅 경로를 효율적으로 유지, 보수, 및 재 설정하는 것이 가능하다.

또한, 이상에서는 본 발명의 바람직한 실시예에 대하여 도시하고 설명하였지만, 본 발명은 상술한 특정의 실시예에 한정되지 아니하며, 청구범위에서 청구하는 본 발명의 요지를 벗어남이 없이 당해 발명이 속하는 기술분야에서 통상의 지식을 가진자에 의해 다양한 변형실시가 가능한 것은 물론이고, 이러한 변형실시들은 본 발명의 기술적 사상이나 전망으로부터 이해되어져서는 안 될 것이다.

Claims

인접 노드가 자신의 전송 영역안에 존재할 확률을 산출하고, 산출한 상기 확률을 포함하는 라우팅 요청 메세지를 생성하여 상기 인접 노드로 전달하거나,

산출한 상기 확률과 전달받은 상기 라우팅 요청 메세지에 포함되어 있는 확률 중 낮은 확률로 상기 라우팅 경로 요청 메세지를 갱신하여 상기 인접 노드로 전달하거나,

전달받은 적어도 하나의 라우팅 요청 메세지에 포함되어 있는 확률 중 가장 높은 확률을 포함하고 있는 라우팅 요청 메세지를 전송한 경로를 라우팅 경로로 설정하는 적어도 하나의 노드를 포함하는 것을 특징으로 하는 애드 혹 네트워크.
제 1항에 있어서,

상기 인접 노드가 전송 영역에 존재할 확률은,

링크 유지 여부를 판단하기 위한 링크 안정 메트릭인 것을 특징으로 하는 애드 혹 네트워크.
제 2항에 있어서,

상기 링크 안정 메트릭은,

GPS로부터 수신한 상태 정보를 이용해 산출하는 것을 특징으로 하는 애드 혹 네트워크.
제 3항에 있어서,

상기 상태 정보는,

X축 위치, X축 속도, X축 가속도, Y축 위치, Y축 속도, Y축 가속도를 포함하는 것을 특징으로 하는 애드 혹 네트워크.
제 1항에 있어서,

상기 적어도 하나의 노드는,

자신의 상태 정보를 소정 주기로 인접 노드로 전달하고, 상기 인접 노드로부터 전달된 상태 정보를 상기 소정 주기로 업데이트하는 것을 특징으로 하는 애드 혹 네크워크.
제 1항에 있어서,

상기 패킷에 포함된 확률 중 상기 가장 높은 확률은,

상기 라우팅 경로의 설정을 위한 라우트 안정 메트릭인 것을 특징으로 하는 애드 혹 네트워크.
제 6항에 있어서,

상기 적어도 하나의 노드는,

동일한 라우트 안정 메트릭이 적어도 하나 이상이면 홉카운트가 가장 작은 경로를 상기 라우팅 경로로 설정하는 것을 특징으로 하는 애드 혹 네트워크.
인접 노드가 자신의 전송 영역안에 존재할 확률을 산출하고, 산출한 상기 확률을 포함하는 상기 라우팅 요청 메세지를 생성하여 상기 인접 노드로 전달하는 단계;

인접 노드가 자신의 전송 영역안에 존재할 확률을 산출하고, 산출한 상기 확률과 전달받은 라우팅 요청 메세지에 포함되어 있는 확률 중 낮은 확률로 상기 라우팅 경로 요청 메세지를 갱신하는 단계;및

전달받은 적어도 하나의 라우팅 요청 메세지에 포함되어 있는 확률 중 가장 높은 확률을 포함하고 있는 라우팅 요청 메세지를 전송한 경로를 라우팅 경로로 설정하는 단계;를 포함하는 것을 특징으로 하는 애드 혹 네트워크의 라우팅 경로 설정방법.
제 8항에 있어서,

상기 인접 노드가 전송 영역에 존재할 확률은,

링크 유지 여부를 판단하기 위한 링크 안정 메트릭인 것을 특징으로 하는 애드 혹 네트워크의 라우팅 경로 설정방법.
제 9항에 있어서,

상기 링크 안정 메트릭은,

GPS로부터 수신한 상태 정보를 이용해 산출하는 것을 특징으로 하는 애드 혹 네트워크의 라우팅 경로 설정방법.
제 10항에 있어서,

상기 상태 정보는,

X축 위치, X축 속도, X축 가속도, Y축 위치, Y축 속도, Y축 가속도를 포함하는 것을 특징으로 하는 애드 혹 네트워크의 라우팅 경로 설정방법.
제 8항에 있어서,

자신의 상태 정보를 소정 주기로 상기 인접 노드로 전달하고, 상기 인접 노드로부터 전달된 상태 정보를 상기 소정 주기로 업데이트하는 것을 특징으로 하는 애드 혹 네트워크의 라우팅 경로 설정방법.
제 8항에 있어서,

상기 패킷에 포함된 확률 중 상기 가장 높은 확률은,

상기 라우팅 경로의 설정을 위한 라우트 안정 메트릭인 것을 특징으로 하는 애드 혹 네트워크의 라우팅 경로 설정방법.
제 13항에 있어서,

동일한 라우트 안정 메트릭이 적어도 하나 이상이면 홉카운트가 가장 작은 경로를 상기 라우팅 경로로 설정하는 것을 특징으로 하는 애드 혹 네트워크의 라우팅 경로 설정방법.
기설정된 라우팅 경로 상에 위치하고 있는 인접 노드에 대해 산출한 자신의 전송 영역안에 존재할 확률이 소정 유효값보다 작으면 메세지를 전달하거나,

메세지를 전달받으면, 상기 기설정된 라우팅 경로를 보수 또는 재 설정하는 적어도 하나의 노드를 포함하는 것을 특징으로 하는 애드 혹 네트워크.
제 15항에 있어서,

상기 소정 유효값은,

상기 인접 노드가 자신의 전송 영역을 벗어나기 전의 임계치인 것을 특징으로 하는 애드 혹 네트워크.
제 15항에 있어서,

상기 메세지는,

링크 파손 메세지로, 기설정된 라우팅 경로의 파손을 나타내는 것을 특징으로 하는 애드 혹 네트워크.
제 15항에 있어서,

상기 적어도 하나의 노드는,

산출된 상기 확률이 상기 소정 유효값보다 크면 링크를 유지하는 것을 특징으로 하는 애드 혹 네트워크.
제 15항에 있어서,

상기 적어도 하나의 노드는,

링크 안정 메트릭이 높은 노드를 이용하여 기설정된 상기 라우팅 경로를 보수 또는 저장된 라우트 안정 메트릭 중 높은 라우트 안정 메트릭을 전달한 경로를 라우팅 경로로 재 설정하는 것을 특징으로 하는 애드 혹 네트워크.
제 15항에 있어서,

상기 적어도 하나의 노드는,

인접 노드의 다음 상태 정보를 산출하기 위한 파라미터를 산출하는 파라미터 산출부;및

산출된 상기 파라미터를 이용해 상기 인접 노드의 다음 상태 정보를 산출하는 칼만 필터부;를 포함하며,

산출된 상기 다음 상태 정보를 이용하여 상기 인접 노드가 다음 상태에 자신의 전송 영역에 존재할 확률을 산출하는 것을 특징으로 하는 애드 혹 네트워크.
제 20항에 있어서,

상기 파라미터 산출부는,

율 워커 방정식을 이용하여 상기 파라미터를 산출하는 것을 특징으로 하는 애드 혹 네트워크.
기설정된 라우팅 경로 상에 위치하고 있는 인접 노드에 대해 산출한 자신의 전송 영역안에 존재할 확률이 소정 유효값보다 작으면 메세지를 상기 소스 노드로 전달하는 단계;및

상기 메세지를 전달받으면, 상기 기설정된 라우팅 경로를 보수 또는 재 설정하는 단계;를 포함하는 것을 특징으로 하는 애드 혹 네트워크의 라우팅 경로 설정방법.
제 22항에 있어서,

상기 소정 유효값은,

상기 인접 노드가 자신의 전송 영역을 벗어나기 전의 임계치인 것을 특징으로 하는 애드 혹 네트워크의 라우팅 경로 설정 방법.
제 22항에 있어서,

상기 메세지는,

링크 파손 메세지로, 기설정된 라우팅 경로의 파손을 나타내는 것을 특징으로 하는 애드 혹 네트워크의 라우팅 경로 설정방법.
제 22항에 있어서,

산출된 상기 확률이 상기 소정 유효값보다 크면 링크를 유지하는 것을 특징으로 하는 애드 혹 네트워크의 라우팅 경로 설정방법.
제 22항에 있어서,

링크 안정 메트릭이 높은 노드를 이용하여 기설정된 상기 라우팅 경로를 보수 또는 저장된 라우트 안정 메트릭 중 높은 라우트 안정 메트릭을 전달한 경로를 라우팅 경로로 재 설정 중 어느 하나를 수행하는 것을 특징으로 하는 애드 혹 네트워크의 노드의 라우팅 경로 설정방법.
제 22항에 있어서,

인접 노드의 다음 상태 정보를 산출하기 위한 파라미터를 산출하는 단계;및

산출된 상기 파라미터를 이용해 상기 인접 노드의 다음 상태 정보를 산출하는 단계;를 더 포함하며,

산출된 상기 다음 상태 정보를 이용하여 상기 인접 노드가 다음 상태에 자신의 전송 영역에 존재할 확률을 산출하는 것을 특징으로 하는 애드 혹 네트워크의 라우팅 경로 설정방법.
제 27항에 있어서,

상기 파라미터를 산출하는 단계는,

율 워커 방정식을 이용하여 상기 파라미터를 산출하는 것을 특징으로 하는 애드 혹 네트워크의 라우팅 경로 설정방법.