위치기반 이동Ad-hoc네트워크 기술 동향

위치기반 이동Ad-hoc네트워크 기술 동향

권혜연* 이병복* 박애순**

이동 Ad-hoc 네트워크는 고정된 인프라의 도움 없이 이동 노드만으로 구성이 가능하므로 네트워크의 독립성과 융통성을 높일 수 있으나, 노드의 참여와 이탈이 자유로우므로 네트워크를 유지하고 관리하기가 어렵다. 이러한 이동Ad-hoc 네트워크에서 네트워크에 편재되어 있는 노드들의 지리적 또는 논리적인 위치 정보를 이용하면 효율적인 라우팅이 가능하고 네트워크의 확장성을 높일 수 있으며 위치기반 기술에 접목하여 인프라에 의존하기 어려운 다양한 응용 서비스의 효과적인 지원을 기대할 수 있다. 그러나 대부분의 위치기반 기술들은 중앙집중적이고 고정된 특정 노드에 의존하는 형태로서 다양한 이동 노드들의 협조에 의해 동작하는 분산 환경의 이동 Ad-hoc 네트워크에 그대로 적용하기 어려운 문제점이 있다. 본 고에서는 기반망에 독립적인 이동 Ad-hoc 네트워크에서의 위치기반 기술의 특징을 분석하고 현재까지 개발된 주요 기술들을 살펴보며 향후 발전 가능성을 고찰해 보고자 한다. ▧

I. 서 론

이동 Ad-hoc 네트워크는 고정된 인프라의 도움없이 이동 노드만으로 이루어진 네트워크로서, 네트워크의 독립성과 융통성을 높일 수 있다. 하지만 이동 노드의 참여와 이탈이 자유로우므로 네트워크의 유지와 관리에 어려움이 많다. 이러한 이동 Ad-hoc 네트워크에서 네트워크 노드의 지리적 또는 논리적인 위치 정보를 이용하면 라우팅의 효율성과 네트워크의 확장성을 높일 수 있다. 또한, 위치기반 기술에 접목하여 인프라에 의존하기 어려운 다양한 응용 서비스에서 보다 효과적인 지원이 가능하다. 이를 위해서는 이동 노드의 위치를 파악하고 적응하기 위한 고도의 위치인식 기술이 요구된다.

최근에는 LBS(Location Based Service) 기반의 다양한 콘텐츠가 개발되어 본격적인 상업 서비스가 제공되고 유비쿼터스 네트워크에 대한 관심이 고조되면서 위치기반 기술과 그 응용에 대한 관심과 중요성이 높아지고 있다. 그러나 대부분의 위치기반 기술들은 중앙집중적이고 이동성에 많은 제약을 가지므로, 빈번하게 움직이는 이동 노드들의 협조에 의해 동작하는 분산 환경의 이동 Ad-hoc 네트워크에서는 그대로 적용하기 어려운 문제점이 있다. 본 고에서는 기존의 위치기반 기술들의 특징과 비교하여 이동 Ad-hoc 네트워크에서의 위치기반 기술의 특징을 분석하고 현재까지 진행되고 있는 주요 연구 기술을 살펴보며 향후 발전 방향을 모색해보고자 한다.

본 고의 구성은 다음과 같다. I장 서론에 이어 II장에서는 기존의 위치기반 기술의 특징을 간략하게 기술한다. III장에서는 이동 Ad-hoc 네트워크 관점에서 위치기반 기술의 특징을 정의하고 주요 기술에 대해 살펴보며 마지막으로 IV장에서 결론을 맺는다.

II. 위치기반 기술 개요

위치기반 기술은 특정 위치에 놓인 대상체(사람 또는 사물)의 물리적, 지리적 또는 논리적인 위치 정보를 알아내어(위치 측위) 그에 적절히 반응하는 기술(시스템 및 서비스)이다[1]. 가장 일반적인 위치 측위 방법으로는 물체간의 거리차나 각도 또는 방위각을 측정하여 위치를 측정하는 삼각 측량 방법(Triangulation)과 특정 관점(Vantage Point)에서 보이는 풍경을 이용한 장면 분석 방법(Scene Analysis), 그리고 특정 위치에 근접하여 대상체를 알아내는 근접 방법(Proximity)이 있다. 이들 방법들은 대상체의 위치 정보를 제공해 주는 매체와 이 정보를 전달하는 다양한 통신 기술과 밀접하게 연관되어 있다. 본 절에서는 이해를 돕기 위해 기존의 위치기반 기술들을 통신 기술과 영상 기술별로 분류하여 살펴본다.

1. 위성통신을 이용한 위치기반 기술

지구 궤도에 떠 있는 GPS(Global Positioning System) 위성에서 보내 오는 반송파 신호의 위상을 측정(절대 측위)하거나 반송파 신호의 코드를 추적(상대 측위)하여 위성까지의 거리를 측정함으로써 삼각 측량 방법에 의한 위치 정보의 획득이 용이하다[2]. 일반적으로 3개의 위성을 통하여 2차원적인 위치를 계산할 수 있으며, 3차원적인 위치를 결정하기 위해서는 적어도 4개의 위성에서 전파를 수신할 수 있어야 한다. GPS와의 위성 통신을 이용한 위치기반 기술은 신호 반경이 넓고 고정된 위성을 통해 안정적인 서비스의 제공이 가능하여 현재 가장 많이 사용되고 있지만, 정밀도가 낮고 GPS 위성 신호의 수신이 어려운 실내나 음영지역에서는 서비스가 불가능한 단점이 있다.

2. 이동통신을 이용한 위치기반 기술

현재 구축되어 있는 셀룰러 이동통신 네트워크를 이용하여 삼각 측량 방법에 의해 이동 단말의 지리적인 위치 정보를 구할 수 있다. 이는 단말의 서비스 셀 영역의 기지국과 주변 기지국간의 협조에 의해 단말의 위치를 알아내는 네트워크 기반 방식과 기지국과는 별개로 GPS 수신기를 가진 단말이 위치 정보를 네트워크로 전달하는 단말 기반 방식, 그리고 이 둘을 혼합한 하이브리드 방식이 있다[3]. 이동통신을 이용한 기술들은 별도의 인프라 구축이 필요 없고 GPS와 같이 서비스 영역이 넓어 매크로 위치 측위 기술로 많이 활용되고 있다. 그러나 기지국이 위치하는 셀 반경 내나 전파의 수신이 가능한 도심에서만 사용이 가능하고 전파 특성에 의한 회절 및 다중 경로, 신호 감쇠에 의해 실내에서의 정확성이 떨어지는 문제점이 있다.

3. 무선통신을 이용한 위치기반 기술

상기 위성통신이나 이동통신을 이용한 위치인식 기술들은 서비스 제공 영역이 넓어 실외에 적합한 반면에 실내나 음영지역에서의 사용에 제약이 따른다. 따라서 최근에는 적외선(Diffuse-Infrared)이나 초음파(Ultrasonic Wave), RF(Radio Frequency), UWB(Ultra Wideband), RFID 등의 다양한 무선통신 기술을 이용한 위치 측위 기술이 활발히 연구되고 있다.

적외선 신호를 이용한 방식은 실내 곳곳에 부착된 적외선 센서가 고유 ID 코드를 가진 적외선 장치를 인식하여 위치를 찾아내는 방식이다. 비교적 시스템의 구성이 간단하고 저렴하나 적외선 신호의 특성상 가시 거리 내에서만 사용이 가능하고 형광 또는 직접적인 태양광이 비치는 장소에서는 사용하기 어려운 단점이 있다. 이를 이용한 대표적인 시스템으로는 AT&T Lab. 에서 개발한 Active Badge System[4,5]이 있다.

초음파를 이용한 방식으로는 빠른 RF 신호와 상대적으로 느린 초음파의 전송 속도차를 이용하여 대상체의 위치를 찾아내는 방법이다. 이는 3차원의 위치인식이 가능하고 저전력, 저비용의 시스템을 구성할 수 있는 장점을 가진다. 이를 이용한 시스템으로는 MIT의 Cricket System[6]과 AT&T Lab 에서 개발한 Active Bat System[7]이 대표적이다.

한편, 대상체가 수신하는 RF 신호의 강도(Signal Strength)를 측정하여 신호 감쇠로 인한 신호 전달 거리를 측정하여 위치를 계산할 수 있다. 일반적으로 IEEE 802.11 무선랜 또는 ISM (Industrial, Scientific and Medical) 대역의 무선 RF가 많이 이용되는데 이는 전파 영역이 넓어 몇 층 이상의 건물 내에서도 사용이 가능한 반면에 잡음 및 반사, 굴절 등에 의해 정확도가 떨어지는 문제점이 있다. 대표적인 시스템으로는 마이크로소프트사에서 개발한 RADAR 시스템[10]과 Pinpoint 3D-iD 시스템[11,12,13]이 있다.

RFID 기술은 RFID 태그 또는 스마트 태그라고 불리는 고유 식별 ID를 가진 초소형 IC 칩을 부착한 대상체가 접근하면 판독기가 칩을 읽어내어 대상체의 정보를 알아내는 기술로서 대상체의 위치정보를 찾아내기가 용이하다. RFID는 비가시성(Non-line-of-Sight)이고 비접촉식(No-contact)이며 동시에 여러 태그를 고속으로 인식할 수 있는 등의 여러 장점을 가지고 있어 요즘 많이 활용되고 있다. 이를 이용한 대표적인 시스템으로는 LANDMARC[14]가 있다.

UWB는 단거리 구간에서 저전력으로 넓은 스펙트럼 주파수를 통해 많은 양의 디지털 데이터를 전송하기 위한 무선 기술로서, 변복조 기능이 필요 없고 낮은 전력 밀도를 가지며 전력 소모가 작고 저가의 통신 장비의 구현이 가능하다. 이는 투과성이 좋아서 건물내의 벽이나 비금속 칸막이 등을 통과할 수 있고 음영지역에서도 사람이나 사물의 위치를 파악할 수 있고 정확도가 높아서 실내 위치인식에 많이 사용될 것으로 기대되고 있다.

4. 영상 인식을 이용한 위치기반 기술

지금까지 언급한 기술들이 대부분 삼각 측량 또는 근접에 의한 위치 측위 기술을 활용한다면 영상 인식을 이용한 기술은 장면 분석 방법을 활용한다. 이는 일반적으로 특정 공간에 놓여진 비디오 카메라를 통해 잡힌 영상의 시간적 또는 공간적인 차이점을 찾아내어 위치를 찾아내는데, 마이크로소프트 연구소에서 유비쿼터스 컴퓨팅의 일환으로 수행 중인 EasyLiving 프로젝트[15]에서 개발한 개인 위치 추적기(Person Tracker)[16,17]가 대표적인 시스템이다.

III. 위치기반 이동 Ad-hoc 네트워크 기술 동향

II절에서 살펴본 위치기반 기술들은 위치에 대한 상대적 또는 절대적인 정보를 제공하는 고정된 레퍼런스 노드들이 반드시 존재한다. 특히, GPS[2]나 기지국[3], 또는 실내의 고정된 위치에 놓여진 네트워크 센서[4], 초음파 수신기[6], 또는 리스너[7]들이 레퍼런스 노드로서 상대적 또는 절대적인 위치에 대한 안정된 정보를 제공하고 있다.

반면, 이동 Ad-hoc 네트워크는 고정된 특정 인프라 및 특정 레퍼런스 노드에 의존하지 않고 네트워크 토폴로지가 유동적이며 이동 노드가 라우팅 기능을 포함한 많은 기능들을 자체 해결하거나 분산 수행하도록 설계됨으로써 이를 그대로 적용하기가 어렵다. 물론, 이동 Ad-hoc 네트워크에서도 응용에 따라 GPS 또는 특정 인프라에 의존하여 위치 정보를 파악하는 다양한 시스템들이 개발되고 있다. 그러나, 군사용이나 재난 통신, 센서 네트워크와 같이 즉흥적이고 독립적인 네트워크에서는 GPS 위성 신호나 특정 인프라 또는 마스터에 의존한 서비스를 지속적으로 기대하기가 어렵다. 또한, 이동 Ad-hoc 네트워크를 구성하는 단말은 대부분 배터리에 의존하므로 GPS 수신기나 초음파 발생기와 같은 별도의 하드웨어를 장착하기가 용이치 않다. 게다가, 고정밀의 위치 계산을 위해 적절한 단말의 분산 처리 기능이 요구되므로 단말의 구성에 많은 제약이 따르며, 고정되지 않은 노드들간의 협력에 의해 위치가 계산되므로 대부분 상대적이고 논리적인 위치만이 판별되므로 지리적으로 절대적인 위치 정보를 얻어내기가 어렵다.

이에 본 절에서는 이동 Ad-hoc 네트워크에서의 주요 위치기반 기술에 대해 살펴보고자 한다.

1. 위치기반 라우팅

이동 Ad-hoc 네트워크에서 위치기반 기술이 가장 구체적으로 적용되는 분야가 라우팅 프로토콜로서 이를 Geographic Routing이라고 한다.

일반적으로 토폴로지 기반의 라우팅 프로토콜은 최단 경로 알고리즘에 기반하여 노드들의 이동성이 높으면 경로 탐색에 대한 오버헤드가 증가하고 네트워크가 확장되면 이를 유지하고 관리하기가 어려워진다. 반면에, 위치기반 라우팅 기술은 라우팅 설정 및 패킷 전송이 노드의 지리적인 위치 정보에 기반하므로 라우팅이 용이하고 빈번한 네트워크 토폴로지의 변화에도 쉽게 적응하며 네트워크 확장성을 높일 수 있다. 또한 각각의 노드는 자신의 이웃 노드의 정보만 유지하면 되므로 라우팅 테이블 유지가 필요하지 않다. 이를 대표하는 프로토콜들로 다음과 같은 기술들이 있다.

가. LAR

LAR(Location-aware Routing)[18]은 GPS를 통해 얻은 위치 정보를 이용하여 중간에서 경로 요청 메시지를 전달하는 이웃 노드의 수를 제한함으로써 불필요한 브로드캐스팅 메시지의 전파를 줄이고자 하는 알고리즘이다. 경로를 찾는 노드의 입장에서 목적지 노드가 위치할 것으로 예상되는 예상영역(Expected Zone)을 찾아내어 이를 근거로 경로 요청 메시지의 전파 범위인 요구영역(Request Zone)을 결정한다. 예상영역에 대한 예로써, 노드 S의 입장에서 목적지 노드 D가 시간 t₀에는 위치 L에 있었고 평균 속도 v로 이동하여 현재 t₁에 있다고 가정하면, 위치 L을 중심으로 하는 반경 v(t₁-t₀)의 원을 그릴 수 있는데 이것이 노드 D가 있을 거라고 예상되는 예상영역이다. 여기서 원의 중심은 t₀에 노드 D가 있었던 위치 L을 나타낸다. 이때 노드 D의 실제 속도가 평균보다 빠르다면 노드 D는 시간 t₁에서 예상영역 외부에 있을 것이다. 일반적으로 목적지 노드의 이동성에 대한 많은 정보를 가질수록 예상영역은 작아진다. 이러한 예상영역을 근거로 요구영역을 정의하는데 요구영역의 멤버쉽 결정 알고리즘에 따라 LARS (LAR scheme) 1과 2로 나누어진다.

LARS 1은 (그림 1 a)와 같이 요구영역을 4개의 모서리를 가진 사각형으로 정의한다. 노드 S의 노드 D에 대한 예상영역의 중심은 노드 D의 좌표인 (X_d, Y_d)가 된다. 이때의 요구영역은 노드 S와 노드 D에 대한 예상영역을 모두 포함한 X와 Y축으로 표현되는 사각형이다. 노드 S가 노드 D의 경로를 알고자 할 때, 노드 S는 경로 요청 메시지에 요구영역에 대한 좌표를 포함한다. 경로 요청 메시지를 수신한 중간 노드는 자신이 경로 요청 메시지 내에 포함된 좌표의 4개 모서리 안에 들어 있을 때만 메시지를 포워딩한다.

반면, LARS 2는 (그림 1 b)와 같이 노드 S가 자신의 위치와 시간 t₀에서의 노드 D의 좌표 (X_d, Y_d)에 대한 거리차 (DIST_s)를 계산하여 이를 경로 요청 메시지에 포함한다. 이 경로 요청 메시지를 받은 노드 i는 좌표 (X_d, Y_d)와 자신의 좌표와의 거리차 DIST_i를 계산하여 임의의 δ에 대해 DIST_s+δ>= DIST_i를 만족하는 경우에만 경로 요청 메시지 내에 있는 DIST_s 를 DIST_i로 바꾸어 포워딩하고 그렇지 않으면 이를 무시한다.

이와 같이 LARS는 위치정보를 이용하여 목적지 노드의 경로 탐색을 위한 경로 요청 메시지의 전파 범위를 한정(Limited flooding)함으로서 라우팅 오버헤드 및 경로 탐색 지연을 줄이는데 목적이 있다.

나. DREAM

DREAM(Distance Routing Effect Algorithm for Mobility)[19]은 라우팅 테이블에 각 노드의 위치 정보를 저장하고 이 정보를 이용하여 계산된 위치로 데이터를 전송하는 알고리즘이다. 라우팅 테이블 내의 각 노드의 정확한 위치 계산을 위하여 각 노드는 주기적으로 자신의 좌표를 포함한 제어 메시지를 브로드캐스팅한다. 각 노드의 좌표는 두 노드간의 거리차와 노드의 이동 속도를 이용하여 계산된다. 이때, 두 노드간의 거리가 크면 클수록 서로에 대해 느리게 이동하는 것과 같은 거리 효과를 이용하여 노드간의 거리차에 대한 함수로 위치 정보를 갱신한다. 또한, 노드의 이동 속도에만 근거하여 이동하는 노드에 의해 자체적으로 위치 갱신의 전송이 개시된다. 이는 고속 이동 노드보다는 저속 이동 노드에 대한 라우팅 정보의 갱신 빈도가 낮으므로 네트워크에 라우팅 정보의 갱신을 요구하는 빈도를 최소화할 수 있으므로 대역폭과 에너지의 사용을 줄일 수 있다. 이와 같이 위치 정보를 가진 라우팅 테이블에 근거하여 주어진 확률로 목적지 노드가 기록된 방향으로 메시지를 전송하므로 안정된 전송을 보장한다.

다. GPSR

GPSR(Greedy Perimeter Stateless Routing)[20]은 목적지 노드로의 라우팅을 위하여 패킷을 수신한 이웃 노드의 위치와 패킷의 목적지 정보를 사용하여 점진적으로 패킷의 포워딩을 결정하는 Greedy 포워딩 방법을 사용한 알고리즘이다. 즉, 패킷을 수신한 노드는 자신과 인접한 이웃 노드 중에 목적지 노드에 가장 가까이 위치한 노드로 패킷을 전송한다. (그림 2)는 Greedy 포워딩 방법을 보여주는 예를 나타내는데, 노드 y는 노드 x가 보낸 패킷의 목적지 노드인 D로 가는 가장 근접한 노드이다.

한편, 패킷이 Greedy 포워딩이 불가능한 영역에 도착하면 그 영역 주변에서 다시 새로운 경로를 찾아낸다. 노드의 위치 정보는 GPS를 통해 얻어지며 각각의 노드는 주기적인 Hello 메시지를 주고 받음으로써 이웃 노드에 대한 최신의 위치 정보를 유지한다.

GPSR은 국부적인 네트워크 토폴로지 정보만을 유지하므로 Distance Vector와 같은 최단 경로 라우팅이나 기타 다른 라우팅 프로토콜에 비해 빈번한 네트워크 토폴로지의 변화에도 빠르게 적응할 수 있으며 네트워크의 확장성이 좋아 밀집된 네트워크 환경에 적합하다.

라. GRID

GRID[21]는 노드들의 지리적 위치인 GR(Geographic Area)을 다수의 논리적 grid로 나누고, 하나 이상의 호스트들이 GL(Grid Leader)로 선택되어 라우팅을 책임지도록 하는 프로토콜이다. grid는 (d×d) 크기의 사각형으로 좌표 (x, y)로 표시된다. GPS 수신기와 같은 위치 측위 장치를 가진 각각의 호스트들은 주어진 임의의 물리적 위치에서 grid 좌표에 미리 매핑된다. 경로 탐색은 grid-by-grid로 수행되고 각 grid에서 하나의 호스트가 그 grid의 게이트웨이로 선출되는데, 그 게이트웨이 호스트는 경로 발견 및 패킷 릴레이, 그리고 경로 유지에 대한 책임을 진다. 경로 발견은 (그림 3)과 같이 각각의 grid에서 선택된 검은 점의 게이트웨이 호스트를 통해 경로 요청 메시지들이 전달된다. 게이트웨이 호스트는 중복된 경로 요청 패킷을 제거하고 밀집된 환경에 적절한 필터링을 제공한다.

마. GLS

GLS(Grid Location Service)[22,23]는 상기 GRID 프로토콜과 마찬가지로 grid 방법을 사용하여 경로를 발견하고 유지하며 패킷을 포워딩하는 라우팅 프로토콜이다. 그러나 GRID 프로토콜이 grid를 동일한 크기로 나누었다면, GLS에서는 모든 노드가 동일한 grid 단위로 구성되는데 grid는 크기의 증가에 따라 여러 order를 가지는 계층적 구조를 갖는다. 즉, order i의 사각형이 4개가 모여 order i +1의 사각형을 구성한다. 각각의 노드는 자신과 인접한 order 1의 사각형에서 자신의 ID와 가장 근접한 ID를 갖는 노드를 위치 서버(Location Server)로 지정한다. 그리고 반복적으로 order의 크기를 늘려 가며 위치 서버를 지정하는데, 가장 근접한 ID란 자신의 ID보다 큰 ID 중에서 가장 작은 ID를 가진 노드를 나타낸다. 자신의 ID 보다 큰 ID가 해당 order내에 없으면 가장 작은 ID를 선택한다.

GLS는 각각의 노드가 네트워크에 있는 다른 노드의 위치 서버로 동작하여 위치 서버를 분산시킴으로써 네트워크 확장이 용이하다. 반면에 네트워크상의 모든 노드에 대한 위치 정보가 중복 저장되고 위치 서버의 사용 여부에 상관없이 자신의 위치가 변할 때마다 위치 정보를 갱신해야 하는 불필요한 오버헤드를 발생시킬 수 있다.

2. 지오캐스팅 기술

지오캐스팅(Geocasting)[24,25]은 위치 정보를 이용하여 GA(Geographical Area)에 있는 하나 이상의 노드에게 패킷을 전송하는 멀티캐스팅의 변형으로, 멀티캐스팅에서 그룹의 관리와 가입과 탈퇴에 대한 오버헤드를 위치 정보를 이용하여 해결한다. GA내에 있는 어떠한 노드라도 외부로부터 데이터를 수신하면 주변의 다른 노드에게 플러딩하도록 되어 있다.

가. LBM

LBM(Location-Based Multicast)[26]은 앞에서 언급한 LAR을 멀티캐스팅 개념으로 접근한 프로토콜이다. 여기서 GA는 MR(Multicast Region)로 정의되며, 하나 이상의 노드의 집합은 위치기반 멀티캐스트 그룹(Location Based Multicast Group)이 된다. 임의의 노드가 MR에 들어가게 되면 그 노드는 자동으로 멀티캐스트 그룹에 추가된다. LBMS(LBM Scheme)는 패킷 포워딩 영역 결정 방법에 따라 두 개의 알고리즘으로 나누어 진다.

LBMS 1은 두개의 GZ(Geographic Zone)을 가지는데 하나는 MR(Multicast Region)이고 다른 하나는 FZ(Forwarding Zone)이다. FZ는 (그림 4 a)와 같이 송신 노드 S와 MR을 모두 포함하는 가장 작은 영역이다. 노드 S는 멀티캐스트 패킷에 FZ의 4개 모서리의 좌표를 포함한다. 이 좌표를 기준으로 FZ안에 있는 노드가 이 패킷을 수신하면 그 노드는 그의 이웃들에게 이 패킷을 포워딩한다. 만약 FZ 바깥에 있는 노드가 패킷을 수신하면 이 패킷을 버린다.

LBMS 2는 명시적인 FZ가 존재하지 않고 패킷을 포워딩할 것인가는 노드들의 상대적 거리로 결정한다. (그림 4 b)와 같이 MR의 중심 좌표 (X_c, Y_c)와 송신자의 좌표 (X_s, Y_s)가 전송 패킷에 포함된다. 지리적으로 중앙인 MR의 중심 좌표 (X_c, Y_c)로부터 임의의 노드 Z에 대한 거리는 DIST_z가 된다. 패킷을 수신한 중간 노드 i는 거리 DIST_i를 계산하여, 임의의 파라메타 δ에 대해 DIST_i+δ>=DISTi이면 이웃 노드들에게 패킷을 포워딩하고 그렇지 않으면 패킷을 버린다. 패킷을 포워딩할 때 송신자의 좌표 (X_s, Y_s)는 포워딩 노드의 좌표 (X_i, Y_i)로 바꾸어 전송한다.

나. GeoGRID

GeoGRID[27]는 상기 기술한 GRID 알고리즘에 기반한다. (그림 5 b)와 같이 GA를 (d×d) 크기의 사각형의 2차원적인 grid 단위로 나누고, 각 grid의 영역에서의 지오캐스트 패킷의 포워딩을 담당할 게이트웨이 노드를 선출한다. FZ는 (그림 5 a)와 같이 소스 노드의 위치와 MR에 의해 결정된다.

GeoGRID는 지오캐스트 패킷을 보내는 방법에 따라 플러딩(Flooding) 기반 알고리즘과 티켓(Ticket) 기반 알고리즘으로 나뉜다.

플러딩 기반 알고리즘은 FZ내의 모든 grid안에 있는 게이트웨이 노드만이 수신된 지오캐스트 패킷을 포워딩한다. 티켓 기반 알고리즘은 송신 노드가 (m×n)인 MR에 대해 (m+n)개의 티켓을 만든 다음, 티켓을 FZ에 있는 이웃 게이트웨이 노드에게 나누어 줌으로써 패킷을 포워딩하는 권한을 준다. 그 이웃 게이트웨이 노드는 송신 노드보다는 MR에 더 가깝게 놓여진 노드를 의미한다.

다. GeoTORA

이전의 LBM 이나 GeoGRID가 데이터 전송을 위한 프로토콜이라면 GeoTORA[28]는 경로 생성을 위한 프로토콜이다. 유니캐스팅 라우팅 프로토콜인 TORA(Temporally Ordered Routing Algorithm)를 이용하여 플러딩에 의한 지오캐스트 패킷 전송의 오버헤드를 줄이고자 하는데 목적이 있다. TORA는 역링크(Link Reversal)에 근거한 분산 라우팅 프로토콜로서 임의의 목적지 노드에게 다중 경로를 제공하고 빠르게 경로를 설정하며 통신 오버헤드를 줄인다. GeoTORA는 TORA를 이용하여 소스 노드는 GR 내에 있는 어떠한 노드에게도 애니캐스트(Anycast)를 수행한다. 한편, 애니캐스트를 위하여 TORA 프로토콜은 각각의 그룹을 위한 DAG(Destination-oriented Acyclic Graphs)를 만들도록 수정된다.

3. Ad-hoc 위치측위 기술

앞에 기술한 위치기반 라우팅이나 지오캐스팅은 GPS나 다른 위치측위 장치에 의해 이미 주어진 위치 정보를 이용하였다. 반면에, 이동 Ad-hoc 네트워크의 고유 기능을 살려 고정되지 않은 노드들이 스스로 자신의 위치를 찾아내는 Ad-hoc 위치측위(Ad-hoc Location-Sensing) 기술도 많이 연구되고 있다. 이 기술은 주로 다수의 센서로 구성된 비교적 규모가 큰 센서 네트워크를 목적으로 연구되는 경향이 있다.

가. APS

APS(Ad-hoc Positioning System)[29]는 GPS에서의 삼각 측량 원리와 Distance Vector 라우팅의 hop-by-hop 정보 전송 방법을 혼합한 위치 측위 시스템이다. 즉, GPS에서와 같이 위치를 측정하기 위한 3개 이상의 Landmark를 hop-by-hop으로 이웃 노드를 통해 찾아간다. 여기서 Landmark는 일종의 자신의 위치를 알고 있는 레퍼런스 노드로서 주기적으로 자신의 위치 정보를 방송한다. Landmark의 hop-by-hop 탐색 기준에 따라 DVH(DV-hop) 알고리즘, DVD(DV-distance) 알고리즘, 그리고 ED(Euclidean Distance) 알고리즘으로 분류된다.

DVH 알고리즘은 노드간의 홉 수(Hop-count)와 홉간 평균 거리를 이용하여 위치를 알아내는 방식이다. Landmark가 방송하는 위치 정보를 수신한 노드는 홉 수를 하나 증가시켜 인접한 이웃 노드에게 전달한다. 이러한 과정을 거쳐 네트워크에 있는 모든 노드들은 Landmark로의 홉 수를 알 수 있고 교정(Correction) 과정을 거쳐 홉간 평균 거리를 알 수 있다. DVD 알고리즘은 홉간 거리(Hop-distance)를 기준으로 이웃 노드들간의 무선 신호 강도를 측정하여 홉 수 대신 이를 전파한다. ED 알고리즘은 GPS 원리와 비슷하며 유클리드 거리(Euclidean Distance)를 기준으로 노드와 Landmark간의 거리를 찾아낸다.

나. APIT

APIT(Approximation Point In Triangulation Test)[30]는 무선 센서 네트워크에서의 지역 기반 위치 측위 알고리즘이다. APIT는 다수의 센서 노드 중에 극히 일부라도 고출력 송신기를 가지고 GPS 또는 임의의 다른 메커니즘에 의해 위치 정보를 알고 있는 고정 레퍼런스 노드인 앵커(Anchor)를 요구한다. 이러한 앵커들이 송신하는 비콘 신호를 기준으로, 한 개의 노드는 자신이 인식하는 여러 앵커들 중에 세 개의 앵커를 선택하고 자신이 이들 세 개의 앵커가 연결하여 형성되는 삼각형 영역(Triangular Region)의 내부에 있는지를 검사한다. 이렇게 해당 노드가 위치할 것으로 예상되는 지역을 점점 좁혀나가며 테스트하는 방법을 PIT(Point-In Triangulation) 테스트라고 부른다. 임의의 노드 M이 이동하여 세 개의 앵커 A, B, C 중 어느 하나에 가까워진다면 노드 M은 세 개의 앵커를 연결한 삼각형 △ABC 내부에 있다고 가정할 수 있다. 반면에 노드 M이 이동하여 앵커 A, B, C 모두에게서 동시에 가까워지거나 동시에 멀어진다면 노드 M이 삼각형 △ABC 외부에 있다는 것을 가정할 수 있다. 이와 같은 테스트를 PPIT(Perfect PIT) 테스트라고 부른다. 그러나 이러한 PPIT 테스트는 실제 노드가 움직이는 방향을 알기 어렵고, 모든 방향을 테스트 한다는 것이 현실적으로 불가능하다. 따라서 노드 M이 이웃 노드들이 앵커로부터 수신한 비콘 신호의 강도와 자신이 수신한 비콘 신호의 강도를 비교하여 점차적으로 예상지역을 좁혀나가는 APIT(Approximate PIT) 테스트가 현실적이다. APIT 테스트를 완료하면 grid 단위로 매핑된 물리적 공간에서의 노드의 위치를 계산한다.

다. GPS-less Outdoor Localization

GPS-less Outdoor Localization[31]은 실내보다는 실외 환경에서 RF 신호의 수신 강도와 연결성(Connectivity)에 기반 하여 위치를 측정한다. 이 알고리즘은 아주 소형의 가벼운 센서 노드들이 수없이 분포된 환경을 가정한다. 자신의 위치를 알고 있는 고정된 다수의 레퍼런스 포인트(Reference Point)들을 네트워크에 중첩 배치하여 주기적으로 자신의 위치 정보를 담은 비콘 신호를 발생하도록 한다. 센서 등의 작은 장치인 노드들은 특정 시간 동안 주변의 레퍼런스 포인트들로부터 수신된 모든 비콘 신호를 이용하여 주변의 레퍼런스 포인트들의 위치 정보를 알 수 있다. 이때 노드들은 레퍼런스 포인트들의 부분 집합들이 커버하는 중첩영역의 중심을 자신의 위치로 인식한다. 위치 측정 오차는 레퍼런스 포인트의 전송 범위가 짧을수록 그리고 배치 밀도가 높을수록 작아진다. 이 알고리즘은 단순하고 위치 측정을 위한 별도의 하드웨어가 필요 없으나, 미리 다수의 레퍼런스 포인트들을 고정 배치해야 하며 전파가 미치는 영역을 완벽한 원형으로 가정하고 있어 실제 환경에서는 거의 사용이 불가능한 어려움이 있다.

라. SpotON

SpotON[32,33]은 미국 DARPA(Defense Advanced Research Projects Agency)의 지원 하에 연구되어 현재 완료된 프로젝트로서, 다수의 센서로 구성된 Ad-hoc 네트워크에서 무선 신호의 RSSI(Radio Signal Strength Information) 값을 측정하여 나타나는 신호 감쇠로 센서간의 거리를 예측하는 Ad-hoc 위치 측위 시스템이다. 시스템은 다수의 SpotON 태그로 구성되는데, 벽이나 사람 또는 사물 등 어디에든 원하는 위치에 부착되며 저전력, 저비용으로