LOCATION-AWARE ROUTING AND GEOCASTING IN WIRELESS AD HOC NETWORKS

Abstract

본 논문은 무선 Ad hoc 네트워크에 관련된 두 가지 주된 라우팅 알고리즘 중 위치 인지 라우팅과 geocasting에 관해 연구하였다. 첫째로, 무선 Ad hoc 네트워크를 위해 LGHR (Location-aware Grid-based Hierarchical Routing)이라고 불리는 새로운 위치 인지 라우팅 프로토콜을 제안하여 같은 범주 내의 다른 알고리즘들 에서 발생되는 오버헤드를 감소시키고자 하였다. LGHR에서 네트워크 영역은 겹치지 않는 존 들로 분리되어져 있다. 하나의 그룹은 전체 네트워크에서 존 들로 분할되어지고, 각각의 존 들은 그리드 라고 불리는 더 좁은 영역들로 나누어지는 방식으로 이루어져 있다. 각각의 존과 그리드 내에서는 중앙집중형 접근방식이 사용되어지고 있다. 각각의 존으로부터 하나의 리더가 선택되며 각각의 그리드로부터는 게이트웨이라 불리는 중심 노드들이 선택된다. 각 리더는 라우팅 테이블을 구성할 책임이 있으며 이는 이후 게이트웨이들에게 보내져 존 내 혹은 존 간 라우팅 기법을 위하여 사용된다. 제시된 LGHR 프로토콜은 ZHLS와 GRID로 알려진 다른 위치 인지 라우팅 프로토콜들과 비교하였다. ZHLS 역시 각각의 존 에서 링크 상태 라우팅을 사용하는 계층형 프로토콜이다. 존 안에 있는 각각의 노드들은 그 존 내의 모든 다른 노드들에게 LSP (Link State Packet) 들을 보내며 각각의 노드들은 존 내 또는 존 간의 경로배정표를 저장하여 라우팅 동작을 수행하게된다. 따라서 존 내에 많은 노드들이 있을 경우 매우 많은 통신 오버헤드가 발생하게 된다. 본 논문에서 제시된 프로토콜인 LGHR은 더 작은 그리드들로 각각의 존을 분할 함으로써 통신 오버헤드와 저장 오버헤드를 감소시키고자 하였다. ZHLS와는 달리, 게이트웨이 노드들만이 라우팅 테이블들을 유지하게 되고 실제적인 전송은 gateway-by-gateway 방식으로 수행된다. 각 프로토콜들의 비교를 위해 ZHLS와 LGHR에 대한 수학적 분석을 수행한 후 성능 분석을 하였다. 제안된 프로토콜은 모든 노드들에 의해 발생하는 통신 오버헤드 뿐만 아니라 저장 오버헤드 관점에서도 ZHLS 보다 더 우수한 특성을 보이고 있다. 또한 제안한 프로토콜은 GRID로 불리는 위치 인지 프로토콜과도 비교되어졌으며 게이트웨이 선출 기법들을 기반으로 안정성 요소들에 대하여도 분석이 이루어졌다. GRID는 하나의 게이트웨이 선정을 위해 단지 그리드의 중심으로부터의 거리만을 사용하는 반면 LGHR은 그리드의 중심으로부터의 거리는 물론 노드에 따른 이동속도를 이용하고 있다. 시뮬레이션 결과 무선 노드들이 매우 빠른 속도로 움직이는 경우 LGHR이 GRID 기법보다 더 안정적으로 동작함을 명확하게 보여주고있다. 본문에서 다루어진 두 번째 주제는 무선 Ad hoc 네트워크에서 모든 노드들이 하나의 geocast 영역 안으로 geocast 패킷 전달을 보장하는 문제에 대한 것이다. Geocast 영역 안에 있는 일부 노드들은 같은 영역 내의 다른 노드들에 직접적으로 접근하지 못하는 경우가 발생하는데 이들 노드들의 분리된 그룹을 Islands 이라 한다. Geocast 영역 내의 모든 노드들에게 패킷들의 전달을 보장하기 위하여 G3 (Grid-based Guaranteed Geocast) 라고 불리는 geocasting 프로토콜이 제시 하였으며, 여기에서는 Island들에게 패킷들을 전달하기 위해 geocast 영역 바깥 쪽 노드들을 사용하였다. Geocast 영역 밖의 몇몇 노드들은 Island들에게 직접적으로 연결될 수 있지만 이들 중 Main Entry Point (MEP) 라고 불리는 하나의 노드만이 선택 되어 패킷전달역할을 수행하게된다. 이와같은 MEP들은 geocast 영역 안쪽 노드들에게 패킷들을 전달할 책임을 가지고 있으며 geocast 영역 안으로 중복적인 패킷 전송을 피할 수 있도록 하고있다. LS(위치기반 서버) 의 개념 또한 새롭게 정의 되어졌으며 경로배정의 역할을 수행하여야 할 책임이 있다. 제안된 기법의 성능 평가를 위하여 두 가지 다른 LBM과 GAMER를 가지고 시뮬레이션을 수행하여 비교하였다. 제안된 기법이 geocast 패킷들의 전달을 보장함은 물론 처리율, 종단간의 지연, 패킷 전달율과 데이터 패킷 오버헤드에 대해서도 다른 두 프로토콜 (LBM, GAMER)들 보다는 더 나은 성능을 지니고 있음을 시뮬레이션을 통해 검증하였다.

This thesis is primarily concerned with two main topics in wireless ad hoc networks: location-aware routing and geocasting. First, a new location-aware routing protocol called Location-aware Grid-based Hierarchical Routing (LGHR) protocol is proposed for mobile ad hoc networks that attempts to reduce the overhead generated by other protocols falling in the same category. In LGHR, the network area is divided into non-overlapping zones. A hierarchy is established in such a manner that the whole network is partitioned into zones and each zone is then further divided into smaller regions called grids. A centralized approach is used within each zone and grid. A leader is elected from each zone whereas a central node called gateway is elected from each smaller grid. The leader is responsible for making routing tables which then sends these tables to the respective gateways. Both intra-zone and inter-zone routing mechanisms are explained. The proposed protocol is compared with other location-aware routing protocols known as Zone-based Hierarchical Link State (ZHLS) and GRID. ZHLS which is also a hierarchical protocol uses link state routing in each zone. Each node in a zone sends its link state packets to all other nodes in its zone. Hence, each node stores and makes its intra-zone and inter-zone routing tables causing huge communication overhead in case there are large numbers of nodes in a zone. The proposed protocol LGHR reduces the communication and storage overhead by further partitioning each zone into smaller grids. Unlike ZHLS, only gateway nodes keep the routing tables and routing is performed in a gateway-by-gateway manner. In order to compare both protocols, the mathematical analysis is done for both ZHLS and LGHR and then evaluation is performed. The analysis clearly indicates that the proposed protocol performs better than ZHLS in terms of the storage overhead as well as communication overhead generated by all nodes. The protocol is also compared with another location-aware protocol called GRID. The stability factor is analyzed by doing simulations for both protocols. The stability factor is chosen on the basis of gateway election mechanisms. GRID uses only the distance from the center of the grid for electing a gateway whereas LGHR takes into account the velocity of a node along with the distance form the center of the grid. The simulation results clearly show that the proposed protocol LGHR is more stable than GRID especially in scenarios where the wireless nodes are moving with very high velocity. The second topic discussed in the dissertation is the problem of guaranteeing the delivery of geocast packets to all nodes inside a geocast region for wireless ad hoc networks. The nodes in the geocast region may not be directly connected to one another, causing isolated groups of nodes that do not have direct access to some other nodes within a geocast region. These isolated groups of nodes are named as islands. In order to ensure the delivery of packets to all nodes, a geocasting protocol called Grid-based Guaranteed Geocast (GGG or G3) is proposed that uses the nodes outside the geocast region to deliver packets to these islands. Several nodes outside the geocast region can have direct connections with islands, but only one node is elected called Main Entry Point (MEP) which is responsible for delivering the packets to the nodes inside the geocast region. This helps in avoiding duplicate packets entering the geocast region. Also, the concept of location server is redefined and is given the routing responsibilities as well. Simulations are performed to compare the proposed mechanism with two other geocasting protocols, LBM and GAMER. The simulations prove that the proposed mechanism not only guarantees the delivery of geocast packets but also performs better than the other two protocols, LBM and GAMER in terms of throughput, end-to-end delay, packet delivery ratio and data packet overhead.