Intermediate node selection algorithm in vehicular ad hoc network

국문 초록 (Abstract)

바넷 (차량 애드혹 네트워크)는 노드 (차량)들의 예측하기 어려운 이동성으로 인해 주기적으로 네트워크 토폴로지가 변하는 무선 통신 네트워크이다. 네트워크 토폴로지의 주기적인 변화는 데이터 패킷 전송과 라우팅 절차를 어렵게 한다. 따라서, 이와 같은 문제를 개선하기 위해 헬로 메시지 또는 비콘과 같은 연결 제어 메시지를 주기적으로 교환함으로써, 노드들 간의 통신 연결을 감시하는 것과 데이터 라우팅을 위한 다음 홉 노드를 선택하는 과정은 반드시 필요하다.
이와 관련하여 다양한 바넷 라우팅 알고리즘이 존재한다. 바넷에 사용할 수 있는 다양한 라우팅 알고리즘 중에서, 이웃 노드들의 이동성 정보를 이용하는 위치 기반 라우팅 방식이 제안되어왔다. 그러나 노드들의 동적인 움직임 방향과 속력은 쉽게 노드들 사이의 연결을 쉽게 단절시킬 수 있다. 그럼에도 불구하고 기존 알고리즘들은 다양한 측면 (예를 들어, 이웃 노드들이 전송 노드의 전송 범위 가장자리에 위치하거나 비콘 전송 주기 사이에 이웃 노드들의 이동성 변화)을 고려하지 않기 때문에 여전히 노드 간의 통신이 단절되는 가능성이 존재한다.
본 학위 논문에서는 이러한 노드 간의 통신 단절과 라우팅 문제를 개선하기 위해 신뢰적이고 효율적인 중간 노드 선택 알고리즘 두 가지를 제안한다. 첫 번째는 이동성 예측과 이동성 상태에 기반한 중간 노드 선택 알고리즘이다. 본 알고리즘의 핵심은 비콘에 포함된 이동성 정보로부터 이웃 노드의 위치를 예측하고 전송 노드의 전송 범위를 벗어날 확률과 위치에 따른 페널티 같은 이동성 상태 값을 계산하여 이를 활용하는 것이다. 두 번째 알고리즘은 비콘에 포함된 이동성 정보로부터 연결 만료 시간, 전송 노드의 전송 범위를 벗어날 확률, 패킷 전달 확률을 계산하고 각 이웃 노드의 잔여 에너지를 활용하여 다음 홉을 위한 중간 노드를 선택한다.
두 알고리즘의 성능을 평가하기 위해 같은 시뮬레이션 환경에서 기존 알고리즘과 제안된 두 알고리즘의 성능을 비교한다. 시뮬레이션 결과는 제안된 두 알고리즘이 몇 가지 측면 (종단 간 지연, 패킷 전달률, 에너지 소모)에서 기존의 알고리즘에 비해 성능적으로 향상된 것을 보여준다.

다국어 초록 (Multilingual Abstract)

Vehicular Ad Hoc Network (VANET) is a wireless communication network with frequent changes in its topology due to unpredictable movements of nodes (vehicles). The frequent changes of network topology make the data packet transmission and routing process very difficult. Therefore, in order to solve these problems, examination of the communication link between the nodes by periodically exchanging the connection control message such as HELLO messages or beacons and the process of selecting a next hop node for data routing are needed.
In this regard, there are variety of VANET routing algorithms. Among various routing algorithms available for VANET, different position based routing algorithms which use the position information of neighbor nodes have been proposed. However, dynamic movement direction and speed of nodes can easily break the communication between nodes. Nonetheless, due to various aspects (i.e. neighbor nodes locate at the edge of sender's transmission range or change in their mobility between beacon transmission intervals, etc.) that have not been considered in the existing methods, there still exists a possibility of communication disconnection.
In this thesis, we propose two reliable and effective intermediate node selection algorithm to improve the routing problem. The first is an intermediate node selection algorithm based on mobility prediction and mobility state. The key component of this algorithm is selecting the intermediate node by predicting the position of nodes and obtaining the mobility state value (such as the probability of leaving a transmission range and penalty according to area) from the mobility information included in beacons. The second algorithm decides the intermediate node by calculating link expiration time, probability of leaving a transmission range, and probability of packet forwarding by considering information on nodes mobility and each node’s residual energy included in beacons.
In order to evaluate the performance for the two algorithms, we have compared the performance of existing routing algorithms and proposed two algorithm in the same simulation environment. Extensive number of simulation results show that the two proposed algorithms outperform the existing algorithms in some aspect (end-to-end delay, packet delivery ratio, energy consumption).