Mobile Ad hoc Network(MANET) consists of a node that has mobility. In MANET, the node has routing , the node builds a network of their own, no dependent infrastructure. Topology are exchanged due to node mobility in MANET. For reducing the change of topology, hierarchical network algorithm has been investigated. In hierarchical network, cluster member node communicates through cluster head node. When the load-balancing of cluster head node is exceed, assigned cluster member node can’t communicate with base station. To solve this problem, we proposed Load Tolerance algorithm. The proposed algorithm, when cluster member node can’t send a message by cluster head node that exceed load-balancing, then the cluster member node sends a message by selected load tolerance node. Through a simulation, the proposed algorithm improves packet delivery ratio in cluster routing.
모바일 애드 혹 네트워크(Mobile Ad hoc Network)는 유동성을 가진 노드들로 구성된 네트워크로써, 각 노드간 패킷의 송수신이 가능하다. 패킷의 송수신이 가능한 노드는 모바일 애드 혹 네트워크에서 라우팅 역할을 수행하여, 통신기반 시설의 지원 없이도 네트워크를 구축할 수 있어, 재해 재난지역, 전쟁지역과 같은 환경에서도 네트워크를 구축한다. 하지만 모바일 애드 혹 네트워크는 노드의 유동성에 의해 토폴로지의 변화가 빈번하여, 라우팅 경로를 복구하기 위해 네트워크의 오버헤드가 증가하며, 에너지를 비효율적으로 사용한다[1,2]. 이러한 오버헤드의 감소 및 효율적인 에너지 사용에 따른 라우팅 경로를 유지하기 위해 계층적 네트워크 구조에 대한 연구가 진행되었다. 계층적 네트워크에서 하위계층 노드인 클러스터 멤버노드는 상위계층인 클러스터 헤드노드를 통해 타 클러스터 헤드노드 및 베이스스테이션에게 패킷을 전송한다[3,4]. 하지만 특정 클러스터 헤드노드가 패킷을 저장할 수 있는 공간에 비해 수신 받은 패킷의 양이 많을 경우, 특정 클러스터 헤드노드에게 소속된 클러스터 멤버노드는 패킷의 수신이 지연되거나, 연결이 단절되어 패킷을 송신할 수 없는 상황이 발생한다[5-7].
이를 해결하기 위해 본 논문에서는 LT알고리즘을 제안한다. LT알고리즘은 계층적 네트워크가 형성된 모바일 애드 혹 네트워크에서 상위계층 노드인 클러스터 헤드노드에게 패킷의 전송이 집중되어 패킷의 전송량이 패킷저장량을 초과하였을 경우, 하위노드인 클러스터 멤버노드는 로드밸런싱을 이용하여, 유효한 통신범위 이내에 존재하는 타 클러스터 헤드노드의 라우팅 경로를 이용하여 지속적인 통신을 지원하는 알고리즘이다.
기존에 제안된 계층적 라우팅 알고리즘은 특정 노드에 대해 패킷의 전송이 집중되는 경우, 소속된 클러스터 멤버노드는 패킷의 전송이 지연되거나, 연결이 단절되어 통신을 패킷을 송신할 수 없게 된다.
맥스-민(Max-min) 알고리즘은 일정한 전송 홉 이내에 존재하는 이웃노드로부터 전송 홉에 따른 네트워크의 밀도를 계산한다. 계산된 밀도를 이용하여 계층적 네트워크 구조 형성 및 전송경로를 설정한다[8].
RODMRP(Resilient Ontology-based Dynamic Multicast Routing Protocol) 알고리즘은 노드의 이동에 의해 노드간 링크가 실패하여 통신을 할 수 없을 경우, 노드간의 상관관계를 이용하여 선정한 양부 노드를 통해 전송경로를 회복하고 통신한다[9]. 본 논문에서 제안하는 알고리즘은 노드의 수용량과 흐름량을 고려하여 계층적 구조가 형성된 네트워크에서 클러스터 헤드노드가 통신을 할 수 없을 경우, 네트워크의 지속적인 통신을 지원하는 Load Tolerance(LT)노드를 선택한다. 관련 논문에서 제안한 이동노드의 클러스터링 알고리즘인 DDV(Dynamic Direction Vector) 알고리즘은 노드의 유동성에 따른 빈번한 토폴로지의 변화를 노드의 속성정보 중이동 방향과 이동 속도 속성 정보를 이용하여, 클러스터를 형성 및 유지하는 알고리즘으로 토폴로지의 변화에 따른 라우팅 경로 변화를 줄이며, 노드의 통신을 유지하는 알고리즘이다[10]. 본 논문에서는 LT노드를 선정하기 위해 DDV에서 노드간의 이동 방향의 차이를 이용하여 확률을 계산하며, 이동 방향 속성 이외에도 노드의 다른 여러 속성을 이용한 확률을 계산하여 LT노드를 선정한다.
본 논문에서 제안하는 LT알고리즘은 클러스터 헤드노드의 로드밸런싱이 초과하여 소속된 클러스터 멤버노드가 목적노드에게 패킷을 전달할 수 없을 경우, 선정된 LT노드를 통해 지속적인 통신을 지원하는 알고리즘이다. LT노드를 선정하기 위해 네트워크의 각 노드는 유효한 통신범위를 가져야 하며, 통신 반경은 노드의 홉 수와 전송범위에 의해 설정되며, 다음 수식 1과 같이 표현할 수 있다.
여기서,
그림 1에서 수식 1에 의해 노드의 통신 범위(Rc)가 설정됨에 따라 클러스터 멤버노드1은 자신이 소속된 클러스터의 클러스터 헤드노드1과 클러스터 멤버노드2정보 이외에도 소속된 클러스터 헤드노드와 연결되어 있는 타 클러스터 헤드노드2, 3의 정보를 알 수 있다. 제안된 알고리즘에서는 유효한 통신의 범위를 설정하기 위해 홉 수를 2홉으로 설정하였다.
노드의 통신범위가 설정된 이후, 클러스터 멤버노드는 지속적인 통신을 위해 노드의 이동 거리, 방향, 에너지, 로드밸런싱과 같은 노드의 속성을 이용한 확률계산에 의해 LT노드를 선정한다. 노드의 거리 속성을 이용한 확률은 노드의 정보를 확인 할 수 있는 통신범위를 기준으로 노드간 거리를 비교하며, 다음 수식 2와 같이 나타낸다.
여기서,
여기서,
노드의 에너지속성 확률은 초기 노드에게 설정된 에너지와 시간에 따른 잔여 에너지를 비교하여, 잔여에너지가 높은 노드를 LT노드로 선정하며, 수식 4와 같다.
여기서,
노드가 같은 크기의 데이터를 받을 경우, 노드의 로드밸런싱은 네트워크가 구축된 지역의 환경과 노드의 수용량에 따라 달라질 수 있다[11]. 노드의 로드밸런싱의 확률을 계산하기 위해 로드밸런싱을 네트워크의 환경에 따른 노드의 용량과 흐름양을 이용하여 다음 수식 5와 같이 나타낸다.
여기서,
여기서, 여기서,
여기서,
LT노드 선정과정 의사코드
표 1에서 N은 네트워크에 존재하는 노드의 개수를 의미하며, G는 네트워크에 존재하는 클러스터 헤드노드의 수를 의미한다. CH는 네트워크에서 선정된 클러스터 헤드노드 그룹, CM은 클러스터 멤버노드의 그룹을 의미한다.
LT알고리즘은 클러스터 헤드노드의 로드밸런싱을 통해 로드밸런싱이 높을 경우, 노드의 속성비교를 통해 선정된 LT노드를 통해 패킷을 전송함으로써 지속적인 통신을 지원하는 알고리즘이다. 클러스터 멤버노드는 지속적인 통신을 위해 클러스터 헤드노드의 로드밸런싱을 주기적으로 상황테이블에 저장하게 되며, 다음 표 2와 같이 나타낸다.
클러스터 멤버노드의 상황테이블
표 2에서 CHID는 통신범위 내에 존재하는 클러스터 헤드노드의 아이디를 의미하며, 클러스터 헤드노드의 로드밸런싱과 LT노드 선정확률을 저장한다. 클러스터 멤버노드는 상황테이블에서 자신이 속한 클러스터 헤드노드의 로드밸런싱이 높을 경우, 노드의 속성에 의해 선정된 LT노드에게 패킷을 전송하며, 그 과정은 다음 그림 2와 같다.
그림 2에서 S는 패킷을 보내는 소스노드를 의미하며, D는 패킷을 수신받는 목적노드를 의미한다. 번호가 기재된 사각형은 클러스터 헤드노드, 번호가 기재된 원은 클러스터 멤버노드를 의미한다. 그림 2 (a)는 LT노드가 선정되기 전의 라우팅경로로 클러스터 멤버노드인 소스노드는 클러스터 헤드노드2를 통해 목적노드에게 통신하고 있다. 그림 2 (b)에서 소스노드가 소속된 클러스터 헤드노드의 로드밸런싱이 높은 것을 확인하면, 통신 범위내에 있는 클러스터 헤드노드 중 LT노드 선정확률이 높은 노드를 LT노드로 선정하여, 패킷을 전송한다. 그림2 (c)는 패킷을 수신한 LT노드는 목적노드와 통신하는 경로를 통해 통신한다.
본 논문에서 제안하는 알고리즘은 클러스터 헤드노드의 로드밸런싱이 집중되었을 경우, 설정된 통신범위에 존재하며, 클러스터 멤버노드의 속성과 유사한 클러스터 헤드노드를 LT노드로 선정하여 통신하는 알고리즘이다. LT알고리즘의 통신이 향상됨을 확인하기 위해 패킷 전송률을 모의실험하였다. 패킷 전송률을 분석하기 위한 수식은 다음 수식 9와 수식 10으로 나타낸다.
여기서,
본 논문에서 주어진 모의실험 환경은 실험 동작 시간은 300초로 설정하였으며, 패킷의 전송주기는 1초마다 패킷을 송신하였다. 패킷 전송률은 30간격으로 패킷 전송률을 계산하였으며, 네트워크 영역은 1000x1000(
모의실험환경
다음 그림 3은 네트워크의 영역이 1000x1000(
다음 그림 4는 네트워크의 영역이 1500x1500(
다음 그림 5는 네트워크의 영역이 2000x2000(
LT알고리즘은 노드의 전송범위가 늘어남에 따라 55%에서 87%의 패킷 전송률을 보여주고 있으며, 맥스-민 알고리즘은 0.009%에서 21%의 패킷 전송률을 나타내고 있다. 이전 모의실험에 비해 LT알고리즘의 패킷 전송률은 낮아 졌으나, 맥스-민 알고리즘에 비해 높은 패킷 전송률을 보여주고 있다.
본 논문에서는 LT알고리즘을 소개하였다. LT알고리즘은 클러스터가 형성된 네트워크에서 클러스터 헤드노드에게 패킷이 집중되어 통신을 할 수 없는 경우, 클러스터 멤버노드는 통신범위 내에 있는 클러스터 헤드노드의 거리, 방향, 에너지, 로드밸런싱의 속성을 비교하여 LT노드를 선정하며, 클러스터 헤드노드의 로드밸런싱이 집중된 상황을 확인하였을 경우, 지속적인 통신을 위해 LT노드를 통해 통신한다. 모의실험 결과, 네트워크의 영역이 증가함에 따라 LT알고리즘의 패킷전송률은 하향되었으나, 노드의 전송범위에 상관없이 맥스-민 알고리즘에 비해 향상된 패킷 전송률을 보여주었다. 하지만 네트워크 밀도, 에너지와 같은 다른 특정 요인에 의해 통신이 제한될 경우, 다른 결과가 나타날 수 있어, 이에 대한 연구가 필요하다.