A multi carrier selectable routing scheme by normalized transmission characteristics (MCS-NTC) at marine multi-carrier MANETs

2.1 기존 연구

MANET(Mobile Ad hoc Network)은 이동체간의 자율망 모델로서 해상의 선박들도 유사한 환경에 있어 해상통신망의 모델로 삼을 수 있다. 선박이 일반적으로 항로를 따라 이동하는 특성을 반영한 해상통신망 모델과 경로배정 프로토콜이 제안되었다[2][5]. 이들은 단일 캐리어인 경우를 가정하므로 다중 캐리어가 혼재하는 현재의 해상통신환경 현실을 반영하지 못한다.

캐리어선호도와 응용의 전송요구특성을 이용하는 CPR[3]과 NTCR[4]는 선박이 쓸 수 있는 모든 캐리어를 고려하나 배정된 다중 홉 경로상의 모든 링크가 동일한 캐리어로 된 최적경로만을 탐색한다.

이 논문에서 제안하는 경로배정방식(MCS-NTC)은 NTCR의 정규화된 전송요구특성을 이용하지만, 탐색되는 배정된 경로 상에 각 링크(홉)들이 가용 캐리어들 가운데 최적 캐리어로 채택할 수 있도록 하여 결과적으로 경로 상의 각 링크가 서로 다른 캐리어로 형성될 수 있는 점이 다른 점이다.

2.2 캐리어와 응용의 전송특성

선박은 GPS를 통해 자신의 위치와 AIS, LRIT를 통해 다른 선박의 위치를 파악한다. wLAN, HSDPA, LTE, WiMAX, WiBro, VHF, Inmarsat의 캐리어를 선택적으로 활용할 수 있으며, 캐리어간 핸드오버가 지연시간 없이 이루어지는 다중매체 통신환경[6]에 있다고 가정한다. 해상에서 캐리어가 제공하는 전송특성과 응용이 요구하는 전송특성이 Table 1 (a)와 (b)에 각각 정리되어 있다

이 논문의 MCS-NTC방식에서는 전송특성(성능지표인 전송률, 비용, 지연시간)을 정규화(normalization)시켜 그 값에 따라 각 홉에 가장 적합한 노드와 캐리어를 선택한다. 전송특성을 정규화하는 이유는 각 전송특성의 값의 범위가 서로 크게 달라 여러 특성들에 대한 단순 연산 결과치로 특정 매체에 대한 통합적인 전송특성의 적합도를 판단하는 것이 불가능하기 때문이다. 이 이유로 실제값들을 그대로 이용하는 방식에서는 최다승(Max-Win)과 같은 매체비교방식(MWR, OMH-MW)이 고안되었으나 계산이 복잡하여 경로를 탐색하는 시간이 많이 걸린다.

Table 1

Marine Communication Characteristics[1]

캐리어와 응용의 전송특성 실제값(절댓값)들을 상대적인 값(0~100: 통상적인 백분율의 최소, 최대치를 적용)으로 변환한 후 이 상대값에 대해 산술합을 해서 최적 노드와 캐리어를 선택한다. 절댓값을 상대값으로 변환하는 것을 정규화라 일컫는다. 정규화된 값(정규값)은 식 (1)에 의해 구해진다.

(max - min) : 100 = ( x - min ) : n  (1)

식 (1)에서 max와 min은 캐리어와 응용의 각 전송특성의 최대와 최솟값이다. 예를 들어, 전송률에서 max는 WiMAX의 70Mbps이고 min은 안전응용의 1Kbps이다. 이 두 값의 정규값은 각각 100과 0이 된다.

x는 정규값(n)을 구하고자하는 특정 전송특성값이다. 예를 들어, wLAN의 전송률 (x=)54Mbps의 정규값은 (n=)77.14이다.

Table 2 (a)와 (b)에 정규화된 전송특성을 각각 정리하였다. 거의 모든 해상에서 위성통신이 가능하므로 위성은 다른 캐리어에 대한 경로탐색이 모두 실패한 경우 적용되는 캐리어로서 경로배정 과정에서는 고려되지 않는다.

Table 2

Normalized Transmission Characteristics

3.1 자율적 해상통신망 모델

[1]의 다중 캐리어로 중첩된 자율적 해상통신망 모델을 따른다. 해상데이터통신망 N=(V,E)은 노드(V)로 항구와 선박, 그리고 에지(E)로 노드간 캐리어로 이어지는 무선링크로 구성된다. 해상에는 7종의 캐리어로 구성된 개별적인 데이터통신망이 존재하므로 N은

where

V_i = {선박, 항구},

E_i = {(v_i, w_i)|거리(v_i,w_i)≤전송범위(C_i)}

이다. 식 (2)에서 C={wLAN, HSDPA, LTE, WiMAX, WiBro, VHF, Inmarsat}, V=∪_i=1,2,...,7V_i, E=∪_i=1,2,...,7E_i이다. 에지는 지리적인 노드간 거리가 특정 캐리어의 전송범위 이내이면 해당 캐리어를 활용하는 링크로 해당 노드 간에 형성된다.

3.2 MCS-NTC 경로배정방식

MCS-NTC에서는 응용이 요구하는 전송특성을 가장 적합하게 만족하는 노드와 캐리어를 경로상의 링크별로 선정하기 때문에 홉별로 캐리어가 서로 다를 수 있다. 최종결과물인 출발지와 목적지 사이의 최적 멀티 홉 경로는 하나 이상의 캐리어 망을 넘나들면서 활용하는 형태가 될 수 있다.

경로를 탐색할 때 다음 홉을 위한 최적노드와 캐리어를 선택하기 위한 기준으로 적합도(Goodness(G))개념을 세워 적용한다. G의 산출을 위해 우선 응용과 각 캐리어 i의 전송특성 정규값의 차 (B_i, C_i, D_i)를 식 (3), (4), 그리고 (5)와 같이 구한다.

식 (3)에서 B_i은 응용 A가 요구하는 대역폭 정규값 NB_A과 캐리어 i가 제공하는 대역폭 정규값 NB_i의 차에 대한 절대치이다. 식 (4)와 식 (5)는 각각 요금과 지연시간의 차에 대한 절대치를 구하는 식이다. 여기서 구한 B_i, C_i, D_i들은 작으면 작을수록 응용이 요구하는 값에 근사한 값을 캐리어에서 제공하는 것이다. 그럴수록 캐리어의 응용에 대한 적합도가 좋다는 뜻이 된다.

위에서 가중치 k (1 또는 w(>1))가 적용된다. 캐리어가 응용이 요구하는 전송특성을 만족하는 경우에는 k=1이 되고, 그렇지 않으면 수용불가능한 의미로 k=w(>1)를 가중치로 곱한다. 이것으로 수용불가능한 캐리어를 완전히 배제하지 않고 수용 가능성의 정도를 조절할 수 있다.

G_iM = B_i + C_i + D_i    (6)

식 (6)이 최종적으로 각 캐리어 i의 적합도(G)이다. 이 값도 작을수록 캐리어의 응용에 대한 적합도가 좋음을 의미한다. 따라서 알고리즘에서 다음 홉을 선택할 때 G_i가 최소인 노드와 캐리어를 선택하면 된다.

G_i를 이용하여 s(출발지)에서 d(목적지)사이의 최적경로를 찾는 MCS-NTC 경로배정방식은 다음과 같다.

① s로부터 경로는 있으나 방문하지 않은 노드들 가운데 s에서 노드까지 링크들의 적합도(G)의 합이 최소(식 (7))인 노드 u를 찾음. u=d이면 성공적으로 종료.

② 노드 u의 모든 이웃노드 v 가운데

이면 s에서 v로 가는 경로를 s-...-u-v 로 갱신함. 또는

이면서 s-...-u-v경로의 홉수가 기존 s-...-v경로의 홉수보다 적으면 s에서 v로 가는 경로를 s-...-u-v로 갱신함. G_uv는 노드 u와 v를 잇는 링크의 적합도임.

③ Step ①로 돌아감.

4.1 평가환경

MCS-NTC의 성능을 OMH-MW과 비교하기 위해 두 방식 모두 동일하게 Table 3의 환경에서 시뮬레이션되었다.

시뮬레이터는 MS VS2005에서 C++로 구현하였다. 노드는 200Km X 200Km 정방형 바다에서 임의의 위치에 배치하였고 노드의 총수는 102개에서 실험하였다. 두 방식의 초기 실험조건을 동일하게 설정하는 데 가장 중요한 요소인 노드들의 위치를 동일하게 적용하였다. 최종적으로 성능분석에 이용된 실험결과는 10,000개의 서로 다른 망을 생성하여 두 방식에 적용 실험한 결과들의 평균치이다.

Table 3

Experimental Environment for Simulation [1]

성능비교치는 각 응용에 대해 최적경로 R이 가지는 평균 B_R, C_R, D_R, H_R과 평균 실행시간(T_R)(단위 ms)이다. 여기서 B_R, C_R, D_R는 식 (3), (4), (5)로 각각 구한 차들의 평균값이다. 전송률, 비용, 지연시간, 홉수 측면에서 응용 요구값에 얼마나 최적경로가 적합한지를 표현한 것으로 작을수록 더욱 적합함을 나타낸다. HR는 최적경로 R의 홉수이다. 여기에 최적경로에 이용된 캐리어의 수와 실행시간도 비교한다.

식 (3), (4), (5)를 계산할 때 적용되는, 캐리어가 응용의 요구 전송특성을 만족시키지 못함을 표현하는 가중치 w를 1.3, 1.5, 2.0, 1000.0으로 각각 달리한 결과를 비교하였다. 앞의 세 값은 수용불가능 캐리어에 대해 가해지는 불이익을 점차 키워 수용불가능 캐리어가 최적 캐리어로 선택되는 것을 점차 어렵게 하는 상황을, 마지막 값은 수용불가능 캐리어가 거의 채택되지 않도록 하여 응용의 요구를 만족시키는 캐리어만을 채택되는 상황을 표현한 것이다.

4.2 성능분석

Table 4의 가중치 w가 1.3일 때 비용은 VoIP를 제외한 다른 응용에서 OMH-MW보다 10~90%까지 더 많이 들고, 지연시간 측면에서 IPTV 응용에서 31%, 안전응용에서 23%정도 적합도가 낮아짐을 보였다. 이는 응용의 최대허용 지연시간을 넘어서는 캐리어가 가중치 1.3으로 채택이 될 수 있기 때문이다.

그 외 전송특성에서는 OMH-MW보다 크게 개선되었다. 특히 주목할 사항은 대역폭 측면에서 크게는 메일응용에서 무려 97%, 작게는 VoIP응용에서 47%까지 적합도를 높여 대역폭의 활용에서 극적인 개선이 이루어진 점이다. 더욱이 최적경로에서 사용된 캐리어의 수도 절반 정도 줄인 점도 중요하다.

경로탐색시간도 전반적으로 92% 정도를 단축시켜 거의 10분의 1시간으로 최적경로를 찾았다. 이는 MCS-NTC방식의 전송특성의 정규값에 의한 단순 산술합으로 최적노드와 캐리어를 선택하는 것이 실행시간 단축에 매우 효과적임을 보인 것이다.

w가 1.5와 2.0 경우에도 여전히 대역폭과 실행시간 측면에서는 w가 1.3일 때와 유사하게 많은 개선이 이루어졌다. 캐리어가 응용의 요구특성을 만족하지 못하면 그 캐리어를 전혀 채택하지 못하게 하는 의미를 가지는 가중치 w가 1000.0일 때(Table 7) 앞서 세 경우들과는 다른 결과가 눈에 띤다. 비용과 지연시간 측면의 성능이 OMH-MW와 비슷해지거나 오히려 웹과 VoIP 응용에서는 크게 개선되는 결과를 보인 것이다. 특히 비용 측면에서는 웹과 VoIP 응용에서 각각 98%와 93%정도 더 좋은 결과를 얻었다.

반면에 대역폭을 보면 앞서 세 가지 가중치 경우에서는 획기적인 개선이 있었으나 위의 웹과 VoIP 응용에서 각각 147%와 17%정도 적합도가 오히려 떨어졌다. 이것은 응용이 요구하는 대역폭보다 제공하는 대역폭이 큰 캐리어를 선택하는 경우이고 대역폭 활용 측면에서 최적화 정도가 떨어진 것에 요인이 있다. 그러나 MCS-NTC에서 근본적으로 추구한 성능요소인 경로탐색시간이 이 경우에도 여전히 획기적으로 줄어들었다.

전반적으로 MCS-NTC 방식은 기존의 OMH-MW 방식에 비해 비용과 지연시간에서 다소의 희생을 제외하면 거의 모든 전송특성 측면에서 크게 성능이 개선되었다. 특히 단순 연산으로 최적노드와 캐리어를 선택하여 실행시간이 기존의 약 10%로 크게 단축된 점이다.

Table 4

Performance Comparison (w = 1.3)

Table 5

Performance Comparison (w = 1.5)

Table 6

Performance Comparison (w = 2.0)

Table 7

Performance Comparison (w = 1000)