In this paper, we propose a context-awareness routing algorithm DDV (Dynamic Direction Vector)-hop algorithm in Mobile Ad Hoc Networks. The existing algorithm in MANET, it has a vulnerability that the dynamic network topology and the absence of network expandability of mobility of nodes. The proposed algorithm performs cluster formation using a range of direction and threshold of velocity for the base-station, we calculate the exchange of the cluster head node probability using the direction and velocity for maintaining cluster formation. The DDV algorithm forms a cluster based on the cluster head node. As a result of simulation, our scheme could maintain the proper number of cluster and cluster members regardless of topology changes.
최근 무선 통신 기술의 발전과 다양한 센서노드의 개발로 인해 무선 센서 네트워크는 저전력, 저 비용 통신 기술과 더불어 MEMS(Micro Electro Mechanical System)기술, RF 기술의 발전으로 인하여 더욱 많은 연구가 이루어지고 있다. 무선 센서 네트워크란 정보를 수집하기 위해 센서, 무선 전송을 위한 다양한 프로토콜 기반의 무선송.수신장치, 데이터 처리를 위한 프로세싱 유닛으로 이루어진 것으로 네트워크 확장성, 자가 설정, 자가 복구, 멀티 캐스트 라우팅의 특징을 지니고 있다. 또한 재해, 재난상황 감시 및 군사적 용도로서 임시적 망을 형성하는 목적을 바탕으로 고안 되었으나, 언제 어디서나 자율적으로망을 형성하는 특성으로 인하여 유비쿼터스 네트워크 실현을 위한 기반으로 연구가 확대 되고 있다[1-3].
MANET(Mobile Ad hoc Network)은 기간망에 의존하지 않는 이동 노드들로 구성된 자율망 또는 추론망에 의한 멀티홉 무선 통신 네트워크로 구성되는 특성으로 인하여 다양한 활용 분야가 제시되고 있다. 특히 노드의 속성 정보를 고려한 라우팅에 대한 연구가 활발히 전개 되고 있다. MANET의 라우팅 방식은 모든 센서 노드가 센싱한 데이터를 기지국으로 보내는 평면적 라우팅 방식과 센서 노드들의 클러스터를 형성하여 클러스터 내의 센서 노드가 센싱한 데이터를 클러스터 헤드노드가 취합 후 기지국으로 전달하는 계층적 클러스터링 방식으로 구분할 수 있다[4-5]. 이 경우 만일 헤드 노드가 방전 되거나 환경이 열악한 지형에서 노드 동작이 불능 상태가 되었을 경우 헤드로부터 보존된 경로가 단절 되어 원활한 통신을 할 수 없게 된다. 그러므로 위와 같은 상황이 발생할 경우 최대한 빨리 라우팅 경로를 복구 시켜주어 정상적인 라우팅이 될 수 있도록 새로운 헤드 노드를 선출하여 전체 네트워크의 수명을 연장 시켜주는 방안이 필수적이다. 또한 MANET의 특성상 각 노드들은 이동성, 속도 그리고 에너지와 같은 다양한 속성 정보를 가진다. 하지만 전송대역폭과 에너지 사용에 제약을 가지며 이러한 특징이 노드간의 잦은 회선 단절과 경로 재설정 문제를 야기한다. 또한 제한적 자원을 활용해야 하며 노드의 이동성에 따른 잦은 토폴로지 변화로 인하여 기존 네트워크의 라우팅 방식을 적용하기 어렵기 때문에 네트워크 내에 제어 메시지 및 데이터 패킷이 과도하게 생성되어 네트워크 트래픽 증가도 발생하기도 한다. 이러한 불필요한 에너지소모로 인하여 망에서 노드의 수명을 단축시켜 전체 네트워크의 수명이 단축 되는 문제점이 발생하게 된다[6-8].
본 논문에서는 상황인식 기반의 스케쥴링 기법인 DDV(Dynamic Direction Vector)-hop 알고리즘을 제안한다. 본 알고리즘은 계층적 클러스터 구조의 MANET환경에서 노드의 이동하는 방향성 및 속도에 따른 노드의 이동 속성 정보를 고려하여 클러스터를 생성 및 유지하는 기법으로 네트워크의 부하를 감소시키고 네트워크 토폴로지를 안정적으로 유지할 수 있다.
MANET환경과 유사한 VANET(Vehicular Ad hoc Network)에서는 이동성을 가진 노드에 의한 잦은 토폴로지의 변화에 대해 라우팅을 유지하기 위한 연구가 진행되어 왔다. 노드의 여러 속성 중 방향 속성을 이용하여 라우팅 하는 알고리즘인 MDBC(Moving Direction Based Greedy Routing Algorithm)는 노드의 움직이는 방향을 설정하기 위하여 현재 노드의 위치의 x좌표가 이전 위치의 x좌표가 클 경우에는 동쪽, 작을 경우에는 서쪽, y좌표가 이전 노드의 y좌표보다 클 경우 북쪽, 작을 경우 남쪽으로 움직이는 방향을 설정하게 된다. 노드의 움직이는 방향이 설정 되면, hello message를 브로드 캐스팅하여 이웃노드의 위치와 움직이는 방향을 이웃노드 테이블로 저장하며, 노드는 목적노드까지 패킷을 전달하기 위하여 DREQ(Destination REQuest)와 DREP(Destination REPly)를 이용하여 목적지 노드까지의 안정적인 라우팅 경로를 찾게 된다[9].
Lili Hu는 동적인 VANET환경에서 노드의 방향과 속도를 고려한 GPSR(Greedy Perimeter Stateless Routing)알고리즘을 제시하였다. 노드의 방향과 속도를 고려한 GPSR 알고리즘에서 노드는 노드의 속도와 방향정보가 담긴 hello 패킷을 주기적으로 보내어 이웃노드의 현재 위치를 파악 하며 노드의 속도와 방향 정보를 이용하여 현재 위치를 계산하는 식은 다음 수식 (1)과 같이 표현할 수 있다.
여기서
Lowest ID cluster(LIC) 알고리즘은 모바일 애드 혹 네트워크에서 제안된 알고리즘으로 아이디가 낮은 노드를 클러스터 헤드노드로 선정하여 클러스터를 형성하는 알고리즘이다. 선정된 클러스터 헤드노드는 자신의 아이디보다 높은 아이디를 가진 노드를 클러스터 멤버노드로 선정하며, 노드의 전송 범위 안에 두개 이상의 클러스터 헤드노드가 있을 경우, 게이트웨이 노드로 선정하여 클러스터 헤드노드간 통신에 이용한다. 하지만 LIC 알고리즘에서 클러스터 헤드노드는 자신의 아이디보다 높은 아이디를 가진 노드의 데이터 패킷을 수신하기 때문에, 에너지를 효율적으로 사용하지 못하며, 빈번하게 연결이 단절된다[11].
Mobility Based Metric for Clustering algorithm(MOBIC) 알고리즘은 모바일 애드 혹 네트워크에서 노드의 위치에 따른 속도 속성을 이용하여, 클러스터를 형성하는 알고리즘으로, 일정시간 노드의 위치의 변화를 이용하여 속도를 측정한다. MOBIC 알고리즘에서 속도의 변화가 적은 노드를 클러스터 헤드노드로 선정하며, 클러스터 헤드노드는 2홉 이내에 존재하는 노드를 클러스터 멤버노드로 선정하여 클러스터를 형성한다[12].
본 논문에서는 노드의 이동하는 방향성 및 속도에 따른 노드의 이동 속성 정보를 고려하여 클러스터를 생성 및 유지하는 기법인 DDV 알고리즘을 제안하였다. 기존 클러스터링 기법은 노드의 이동으로 인하여 네트워크 토폴로지가 지속적으로 변하여 토폴로지 변경 정보를 네트워크 전체로 브로드 캐스팅하여 네트워크 부하를 가중 시키는 문제점이 발생시켜 네트워크의 확장성결여에 대한 취약성을 지니고 있다. 따라서 본 논문에서는 노드의 이동성에 따른 방향성 및 이동 속도가 같은 노드들끼리 클러스터를 구성하여 네트워크 토폴로지의 변화를 줄일 수 있고 네트워크의 패킷 전송률을 증가시켜 네트워크의 부하를 감소시킬 수 있다.
본 논문은 클러스터링 형성 시 다음과 같은 가정을 갖는다. 첫 번째로 전체 네트워크 영역의 중심에 베이스 스테이션이 위치한다. 두 번째로 베이스스테이션을 기준으로 4개의 영역으로 분리한다. 그림 1에서 보는바와 같이 위 가정에 따라 초기 노드의 배치 및 방향성 및 속도의 속성정보를 보여준다.
초기 클러스터 헤드를 선출하는 과정은 다음 그림 2와 같이 각 영역의 중심에 있는 노드들이 클러스터 헤드로 선출이 되고 같은 속성 정보를 갖고 있는 노드들을 찾게 된다. 또한 각 영역의 경계에 있는 노드들은 자신의 이동하는 방향성 및 속도 정보에 따라 가장 유사한 영역으로 편입이 되며, 편입된 영역에서 클러스터링을 형성한다.
각 영역에 있는 노드들은 이동성을 가지고 있기 때문에 현제 소속되어 있는 영역을 이탈하는 상황이 발생한다. 이 경우 다른 영역으로 이동을 하게 되면 최종 자신이 속한 영역에서 클러스터링을 형성하게 된다. 예를 들어 현재 자신이 A라는 영역에 속해 있다가 B라는 영역으로 이동을 하게 된다면, 자신이 갖고 있는 이동성 및 속도의 속성 정보에 따라 B영역에서 다시 클러스터링을 형성하여 라우팅 경로를 유지한다.
위 그림 2와 같이 초기 클러스터 헤드 노드가 선출이 되면 주변의 노드들에게 헤드 노드로 선정 되었음을 알리게 되고 알림을 받은 일반 노드들은 자신과 가까우며, 이동 방향 및 속도를 고려하여 헤드 노드를 선택하여 조인 메시지를 보낸다. 조인 메시지를 받은 헤드 노드는 자신의 멤버 노드로 등록하여 다음 그림 3와 같이 클러스터 형성이 완료 된다. 클러스터링이 설정이 되면, 멤버 노드들은 메시지를 헤드 노드들에게 전송하고, 헤드노드는 베이스스테이션으로 메시지를 전송하는 라우팅 구조를 갖게 된다.
본 논문에서는 노드의 방향성 및 속도 등 이동 노드의 속성 정보를 고려하여 클러스터를 생성 및 유지하는 기법인 DDV 알고리즘을 제안하였다. 제안하는 알고리즘은 다음과 같은 속성정보를 갖는다. 네트워크 내에 있는 노드의 집합을
여기서,
DDV 알고리즘은 노드의 방향성과 속도에 의해 클러스터를 형성 및 유지하여 네트워크의 지속 적인 통신을 지원하는 알고리즘으로써, 크게 초기 클러스터를 형성하는 과정과 클러스터를 유지하기 위한 클러스터 헤드노드 교체 과정으로 표현된다.
3.2.1. 클러스터 형성 방법
DDV 알고리즘에서 초기 클러스터를 형성하기 위해 베이스 스테이션이 네트워크 중앙에 위치한다고 가정하고, 베이스스테이션을 기준으로 네트워크 영역을 나누는 방법은 다음 수식 (5)와 같다.
여기서,
다음 수식 (6)과 (7)과 같이 베이스스테이션을 기준으로 초기 클러스터 헤드노드를 선정하기 위한 방향의 범위는 rs로 표현하며, rs의 값이 커질수록 설정되는 방향의 범위는 넓어진다.
여기서,
위 수식 (7)과 같이 클러스터 헤드노드를 선정후 노드간 방향의 유사성을 측정하는 방법은 다음 수식 (9)와 (10)과 같다.
여기서,
여기서,
여기서,
클러스터 형성 과정 의사코드
3.2.2. 클러스터 유지 방법
클러스터 헤드 노드의 에너지 부하를 줄이기 위하여 헤드 노드교체는 필수 요소이다. 따라서 클러스터링 형성 후 클러스터를 유지하는 단계는 다음과 같다. 클러스터헤드 노드가 되기 위한 확률적 성공률을 노드의 속성정보인 방향과 속도, 그리고 노드의 잔여 에너지에 의한 선택 확률을 계산하게 된다. 클러스터 멤버 노드의 잔여 에너지에 의한 확률을 계산하는 방법은 다음 수식 (14)와 같다[13-15].
여기서,
계산된 교체 확률을 이용하여 클러스터 헤드노드의 교체확률을 최종적으로 계산하는 방법은 다음 수식 (16)과 같다.
여기서,
클러스터 헤드노드 교체과정 의사코드
그림 4에서 보는바와 같이, 노드 X와 노드 Y는 클러스터 헤드노드A와 클러스터 헤드노드 B의 전송반경 내에 모두 포함 된다. 이런 경우, 어떤 클러스터 헤드노드를 선택하는 것이 효율적인 클러스터링 방법인지 보여주는 예시이다. 기존 알고리즘 같은 경우, 방향과 속도에 상관 없이 위치가 가까운 클러스터 헤드노드를 선택하게 된다. 하지만 본 논문에서 제안한 DDV 알고리즘에 따르면, 위치가 가까운 클러스터 헤드노드를 선택하는 것이 아닌, 클러스터 헤드노드의 이동하는 방향성 및 속도를 비교하여 속성 정보가 유사한 헤드노드를 선택하게 된다. 예를 들어, 노드 X는 클러스터 헤드노드 A와 클러스터 헤드노드 B 모두 클러스터를 구성할 수 있지만, 자신이 가지고 있는 방향성 및 속도 정보를 클러스터 헤드노드들과 비교하여 가장 유사한 클러스터 헤드노드 B를 선택하여 네트워크의 부하를 감소시키고 네트워크 토폴로지를 안정적으로 유지할 수 있다[18].
제안한 DDV 알고리즘의 효율성에 대한 증명을 하기 위해 이동 노드의 방향성과 속도 정보에 따른 패킷 전송률을 모의 실험하였다. 본 논문에서의 효율성에 대한 증명을 하기 위한 패킷 전송률 측정 방법은 다음 수식 (17)과 같다.
여기서
제안한 DDV 알고리즘의 효율성을 비교하기 위하여 Random 네트워크를 사용하였으며, Random 네트워크는 특정 제약을 받지 않고 자율적으로 클러스터링 및 헤드 노드 교체를 하고 라우팅 경로를 설정한다.
본 논문에서 주어진 모의 실험 환경은 노드의 분포영역이 100x100(m)에서 노드를 무작위로 배치 후 노드의 방향성 과 속도에 따른 클러스터를 구성한다. 각 이동 노드의 방향성은 4개의 영역으로 나누어지며 각 노드의 속도는 1 ~ 16m/s 사이에서 무작위로 값이 배정된다. 전체 네트워크 영역의 중심에 베이스스테이션이 위치하는 것으로 가정하고, 베이스스테이션을 기준으로 4개의 영역으로 분리하여 모의 실험 하였다. 본 논문에서 주어진 모의 실험 환경은 다음 표 3과 같다.
모의실험 환경
그림 5은 DDV 알고리즘과 Random 네트워크의 패킷 전송률을 비교 실험한 결과이다. 그림 5에서 (a)는 100x100 네트워크 지역에서 100개의 노드로 시간에 따른 패킷 전송률을 관찰한 결과이고, (b)는 200개 노드로 시간에 따른 패킷 전송률을 관찰한 결과이다. 또한 그림 5의 (c)는 300개 노드로 시간에 따른 패킷 전송률을 관찰한 결과이고, (d)는 400개의 노드로 시간에 따른 패킷 전송률을 관찰한 결과이다.
그림 5에서 보는 보는바와 같이 노드의 방향성 및 속도에 따른 이동성을 반영함으로써 측정 시간에 따라 노드의 패킷 전송률은 DDV 알고리즘이 최소 30%에서 50% 까지 효율적인 패킷 전송률을 보여주고 있다. 또한 네트워크내 노드의 수가 증가할수록 패킷 전송률은 좋은 결과를 보여주고 있음을 확인하였다. 이는 노드의 밀도에 따라 패킷 전송률에 영향을 주는 결과를 보여주고 있다. 따라서 계층적 프로토콜인 모바일 에드 혹 네트워크에서 각 노드간 방향성 및 속도 정보가 큰 영향을 미치고 있음을 확인할 수 있었다.
본 논문에서는 모바일 에드 혹 네트워크에서의 노드의 이동성에 따른 네트워크 토폴로지가 지속적으로 변하는 문제점을 분석하고, 이를 보완하기 위한 새로운 알고리즘을 제안하였다. 본 논문에서 제안한 DDV 알고리즘은 MANET의 계층적 클러스터 구조에서 노드의 이동하는 방향성 및 속도에 따른 속성정보를 고려하여 클러스터를 생성 및 유지하는 기법이다. 노드의 이동하는 방향 및 이동 속도가 유사한 노드들끼리 클러스터를 구성하고 유지함에 있어 네트워크 토폴로지 변화를 줄일 수 있다. 또한 각 노드에 대한 네트워크의 부하를 감소 시켜 네트워크 토폴로지를 안정적으로 유지할 수 있음을 확인하였다. 노드의 속성 정보에 따른 클러스터링후 패킷 전송률을 측정하여 비교 분석한 결과 본 논문에서 제안하는 DDV 알고리즘이 효율적인 결과를 보여 주었다. 따라서 에드 혹 네트워크에서 중요한 이슈인 토폴로지 변화 및 네트워크 부하 측면에서 높은 결과를 보여 줄 수 있을 것으로 기대한다. 하지만 네트워크 특성상 상황에 따라 다른 결과를 보여줄 수 있을 것이고 향후 다른 속성 정보를 추가하여 함께 비교 분석하는 연구가 필요 하겠다.
