모바일 애드 혹 네트워크(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과 같이 표현할 수 있다.

여기서, R_C는 노드의 통신범위를 의미하며, k는 전송 홉 수, R_T는 노드의 전송범위를 의미하며, 다음 그림 1로 표현한다.

그림 1에서 수식 1에 의해 노드의 통신 범위(Rc)가 설정됨에 따라 클러스터 멤버노드1은 자신이 소속된 클러스터의 클러스터 헤드노드1과 클러스터 멤버노드2정보 이외에도 소속된 클러스터 헤드노드와 연결되어 있는 타 클러스터 헤드노드2, 3의 정보를 알 수 있다. 제안된 알고리즘에서는 유효한 통신의 범위를 설정하기 위해 홉 수를 2홉으로 설정하였다.

노드의 통신범위가 설정된 이후, 클러스터 멤버노드는 지속적인 통신을 위해 노드의 이동 거리, 방향, 에너지, 로드밸런싱과 같은 노드의 속성을 이용한 확률계산에 의해 LT노드를 선정한다. 노드의 거리 속성을 이용한 확률은 노드의 정보를 확인 할 수 있는 통신범위를 기준으로 노드간 거리를 비교하며, 다음 수식 2와 같이 나타낸다.

여기서, P_i'(t)|_dist는 노드간 거리 속성에 의한 확률을 의미하며, dist_i'j(t)는 시간이 t일 경우, 클러스터 헤드노드 i′과 클러스터 멤버노드 j간의 거리를 의미한다. LT노드는 클러스터 멤버노드와 이동하는 방향이 비슷해야 하며, 노드의 방향속성에 대한 확률은 관련 논문에서 제안한 DDV 알고리즘 중 방향에 대한 속성정보를 사용하여 노드간 방향의 차이와 설정된 방향의 차이 임계값을 이용하며, 다음 수식 3과 같다.

여기서, Dir_i'j는 클러스터 헤드노드 i′과 클러스터 멤버노드 j간 방향의 차이를 의미하며, 는 방향차이의 임계값을 의미한다.

노드의 에너지속성 확률은 초기 노드에게 설정된 에너지와 시간에 따른 잔여 에너지를 비교하여, 잔여에너지가 높은 노드를 LT노드로 선정하며, 수식 4와 같다.

여기서, P_i'(t)|_E는 에너지 속성에 의한 확률을 의미하며, E_init는 초기 설정된 노드의 에너지를 의미하며, E_i'(t)는 시간에 따른 클러스터 헤드노드 i′의 잔여 에너지를 의미한다.

노드가 같은 크기의 데이터를 받을 경우, 노드의 로드밸런싱은 네트워크가 구축된 지역의 환경과 노드의 수용량에 따라 달라질 수 있다[11]. 노드의 로드밸런싱의 확률을 계산하기 위해 로드밸런싱을 네트워크의 환경에 따른 노드의 용량과 흐름양을 이용하여 다음 수식 5와 같이 나타낸다.

여기서, lb_i(t)는 시간에 따른 노드의 로드밸런싱을 의미하며, flow_i(t)는 클러스터 헤드노드 i 흐르는 흐름량을 의미한다. C_i는 패킷을 저장하기 위한 클러스터 헤드노드 i의 수용량을 의미하며, 노드의 흐름량 flow_i(t)은 노드의 수용량 C_i을 초과하여 통신을 할 수 없다. 는 네트워크가 구축된 환경에 따른 노드의 흐름환경을 의미하며, 상수 α에 의해 나타낸다. lb_i(t)은 0~1사이의 값을 가지며 큰 값을 가질수록, 노드 i의 저장할 수 있는 수용량은 작다는 것을 의미한다. lb_i(t)에 의해 노드의 로드 밸런싱의 확률은 다음 수식 6에 의해 계산된다.

여기서, 여기서, P_i'(t)|_lb는 LT노드를 선정하기 위한 노드의 로드밸런싱의 확률을 의미하며, 확률이 높을 수록 클러스터 헤드노드 i′가 저장할 수 있는 수용량은 크다는 것을 의미한다. 노드의 각 속성 확률에 가중치를 곱하여, 노드 i′의 LT노드 선정확률을 계산하며, 다음 수식 7과 같다.

여기서, i는 클러스터 헤드노드를 의미하며, j는 클러스터 멤버노드를 의미한다. i′은 클러스터 멤버노드 통신 범위 내에 존재하는 클러스터 헤드노드, w_i′(dist), w_i′(Dir), w_i′(E), w_i′(lb)은 거리와 방향, 에너지, 로드밸런싱에 대한 가중치를 의미한다. w_i′(attr)은 노드의 속성 집합을 의미한다. 노드는 LT노드를 선정하기 위해 노드의 여러 속성을 선택할 수 있으며, 선택된 속성의 가중치의 합은 1이다. 선택된 노드의 속성 중 유의적 관계를 가지는 노드의 속성들은 노드의 속성간 가중치의 영향을 받으며, 가중치의 합은 유의적 관계를 가지고 있지 않는 노드 속성의 가중치 값을 제한 값이다. 노드의 거리, 방향, 에너지, 로드밸런싱 속성을 이용하여 각 속성의 기대 값에 따른 확률을 계산하여, 높은 선정 확률을 가진 클러스터 헤드노드를 LT노드로 선정한다. 다음 표 1은 LT노드를 선정하는 과정을 나타낸 의사코드이다.

표 1에서 N은 네트워크에 존재하는 노드의 개수를 의미하며, G는 네트워크에 존재하는 클러스터 헤드노드의 수를 의미한다. CH는 네트워크에서 선정된 클러스터 헤드노드 그룹, CM은 클러스터 멤버노드의 그룹을 의미한다. LT_i(t)는 클러스터 멤버노드가 선정한 LT 노드를 의미한다. LT노드를 선정하기 위해 통신 범위에 존재하는 클러스터 헤드노드를 검색하며, 통신 범위내에 있는 클러스터 헤드노드의 LT노드 선정확률을 계산하여, 가장 높은 확률을 가진 클러스터 헤드노드를 LT노드로 선정하여 출력한다.

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으로 나타낸다.

여기서, f(flow_j(t))는 네트워크에 존재하는 클러스터 멤버노드들이 베이스스테이션으로 패킷을 보냈을 경우, 베이스스테이션에서 받는 패킷의 양을 의미한다. 여기서 flow_j(t)는 클러스터 멤버노드 j에서 베이스 스테이션으로 보내는 패킷을 의미하며, Avg_Path(j,BS)(P_i(t)|_lb)는 클러스터 멤버노드 j에서 베이스 스테이션으로 패킷을 송신할 경우, 라우팅 경로에 존재하는 클러스터 헤드노드들의 평균 로드밸런싱을 의미한다. 클러스터 멤버노드들이 베이스 스테이션에게 송신한 패킷의 총량과 로드밸런싱에 의해 베이스 스테이션에서 수신 받은 패킷 량을 수식 10에 의해 비교하여, 패킷 전송률을 분석하였다.

본 논문에서 주어진 모의실험 환경은 실험 동작 시간은 300초로 설정하였으며, 패킷의 전송주기는 1초마다 패킷을 송신하였다. 패킷 전송률은 30간격으로 패킷 전송률을 계산하였으며, 네트워크 영역은 1000x1000(m²)에서 2000x2000(m²)의 네트워크 영역의 크기를 증가하였다. 노드의 개수는 2000개로 네트워크 영역에 임의적으로 배치하였다. 노드의 전송영역은 400m에서 600m까지 설정하였으며, 노드의 속도는 최소 1(m/s)에서 최대 16(m/s)로 설정하였다. 비교 알고리즘은 일정한 홉 이내에 존재하는 이웃노드의 수에 의해 전송경로를 설정하는 맥스-민 알고리즘(Max-min Algorithm)과 비교 하였다.

다음 그림 3은 네트워크의 영역이 1000x1000(m²)인 경우, 노드의 전송영역의 크기에 따른 패킷전송률을 나타내고 있다. 본 논문에서 제안한 알고리즘은 노드의 전송영역에 상관없이 98~99%의 패킷 전송률을 나타내었으며, 맥스-민 알고리즘은 노드의 전송범위에 따라 19~52%의 패킷 전송률을 나타내고 있다. 제안한 알고리즘이 맥스-민 알고리즘보다 높은 패킷전송률을 보여주고 있다.

다음 그림 4는 네트워크의 영역이 1500x1500(m²)인 경우, 노드의 전송영역의 크기에 따른 패킷전송률을 나타내고 있다. LT알고리즘은 노드의 전송범위가 늘어남에 따라 74%에서 98%의 패킷 전송률을 보여주고 있으며, 맥스-민 알고리즘은 25%에서 41%의 패킷 전송률을 나타내고 있다. 네트워크의 영역이 1000x1000(m²)일 경우보다 낮은 패킷 전송률을 보여주나, 맥스-민 알고리즘에 비해 높은 패킷 전송률을 나타내고 있다.

다음 그림 5는 네트워크의 영역이 2000x2000(m²)인 경우, 노드의 전송영역의 크기에 따른 패킷전송률을 나타내고 있다.

LT알고리즘은 노드의 전송범위가 늘어남에 따라 55%에서 87%의 패킷 전송률을 보여주고 있으며, 맥스-민 알고리즘은 0.009%에서 21%의 패킷 전송률을 나타내고 있다. 이전 모의실험에 비해 LT알고리즘의 패킷 전송률은 낮아 졌으나, 맥스-민 알고리즘에 비해 높은 패킷 전송률을 보여주고 있다.

본 논문에서는 LT알고리즘을 소개하였다. LT알고리즘은 클러스터가 형성된 네트워크에서 클러스터 헤드노드에게 패킷이 집중되어 통신을 할 수 없는 경우, 클러스터 멤버노드는 통신범위 내에 있는 클러스터 헤드노드의 거리, 방향, 에너지, 로드밸런싱의 속성을 비교하여 LT노드를 선정하며, 클러스터 헤드노드의 로드밸런싱이 집중된 상황을 확인하였을 경우, 지속적인 통신을 위해 LT노드를 통해 통신한다. 모의실험 결과, 네트워크의 영역이 증가함에 따라 LT알고리즘의 패킷전송률은 하향되었으나, 노드의 전송범위에 상관없이 맥스-민 알고리즘에 비해 향상된 패킷 전송률을 보여주었다. 하지만 네트워크 밀도, 에너지와 같은 다른 특정 요인에 의해 통신이 제한될 경우, 다른 결과가 나타날 수 있어, 이에 대한 연구가 필요하다.