Ⅰ. 서 론

이동 애드혹 네트워크(Mobile Ad Hoc Network; MANET)는 중앙 관리되는 인프라 없이 이동 무선 노드들만의 집합으로 구성되어 멀티홉 방식으로 서 로 간에 패킷을 교환하는 네트워크로, 네트워크에 자율성과 융통성을 부여한 신개념 네트워크 이다. 이동 애드혹 네트워크의 구성 노드들은 전파 도달 거리가 제한되므로 중계 노드로서 데이터를 전달하 는 역할을 수행하며, 기본적으로 배터리 전력을 사 용하여 에너지의 공급이 일정치 않은 특성을 갖는 다[1].

특히 노드의 배터리 소진은 링크 연결을 깨뜨리 며 네트워크의 생존성(survivability)에 지대한 영향 을 미치게 된다. 따라서 네트워크의 생존시간을 증 대시키고 연결성을 보장하기 위해서는 노드의 에너 지 소비를 고려한 전송경로의 선택이 필수적이다. 지금까지는 일반적으로 가장 짧은 연결 홉 수를 갖 거나 링크의 전송률이 높은 경로를 선택하였으나, 이러한 라우팅 방식은 노드가 송수신에 소비하는 전력량이나 원래 갖고 있던 배터리 잔량을 고려하 지 않아 네트워크의 생존시간 측면에서는 좋은 성 능을 보여주지 못한다[2]. 따라서 노드의 사용 전력 량과 배터리 잔량을 고려한 다양한 에너지 효율적 인 라우팅 방식들이 제안되었다[2-5]. 이 방식들은 네트워크 생존시간의 증대를 위하여 노드의 소모 전력량과 배터리 잔량을 조합하여 라우팅 비용을 설계하고 이를 기반으로 전체 라우팅 비용을 최소 화하는 경로를 최종 선택한다.

멀티홉 연결시 소소 노드와 목적지 노드 사이에 존재하는 중계 노드의 경우 패킷을 수신하여 전달하 는 역할을 수행하므로, 두개의 송수신 링크를 가지며 각각의 링크에서 수신하고 송신하는데 전력 소모가 발생한다. 다시 말해, 전송 경로상의 하나의 노드를 놓고 보았을 때 이 노드에서 소모되는 전력 값은 수 신 링크와 송신 링크 모두와 관련된다. 하지만 기존 의 저전력 라우팅 방식들은 한 노드로부터 연결 가 능한 다른 한 노드까지의 링크에서 소모되는 전력만 을 고려할 뿐, 연결된 노드가 추가적으로 소모해야 하는 다음 송신링크의 전력을 동시에 고려하지 않는 다. 아울러 기존 방식은 자신의 배터리 잔량만을 고 려하여 라우팅 비용을 계산할 뿐, 연결하려는 노드의 배터리 잔량을 같이 고려하지 않는다[4-6]. 이러한 방 식의 중계노드 선택은 한 번에 한쪽 링크에서 발생 하는 비용만을 고려하므로 실제 경로 상에서 멀티홉 송수신에 소모되는 노드의 모든 전력 소비량을 엄밀 히 반영하지 못하여 생존시간을 최대화하는 최적 라 우팅 경로를 찾기 어렵다[7].

제안 라우팅 방식은 네트워크 생존시간을 최대화 하는 라우팅 경로를 찾기 위하여 연결 가능한 경로 의 전체 링크에서 소모되는 송수신 전력량과 연결 된 노드의 모든 배터리 잔량을 고려한다. 이를 위해 제안방안은 각 노드가 라우팅을 위한 제어 패킷을 네트워크상에 플러딩(flooding)하고 필요한 정보를 수집하여 목적지 노드에게 전달하는 소스 라우팅 방식을 채택한다. 또한 소스 라우팅에서 발생하는 정보 전달 오버헤드(overhead)를 최소화하기 위하여 효과적인 라우팅 비용 값을 설계하고, 이를 기반으 로 네트워크 생존시간을 최대화하는 경로를 선택하 는 효율적인 라우팅 프로토콜을 함께 제안한다.

이 논문의 구성은 다음과 같다. 2장에서는 제안 라우팅 프로토콜과 관련 기존 연구들에 대해 서술 하고, 3장에서는 제안하는 라우팅 프로토콜에 대하 여 자세히 설명한다. 4장에서는 시뮬레이션 결과를 바탕으로 제안 라우팅 방식과 기존 라우팅 방식의 성능을 비교 분석한다. 마지막으로 5장에서 본 논 문의 결론을 맺는다.

Ⅱ. 관련 라우팅 프로토콜

1. 애드혹 라우팅 프로토콜

애드혹 라우팅 프로토콜은 크게 Proactive (Table- Driven) 라우팅과 Reactive (On-Demand) 라우팅 방 식으로 나뉜다. Proactive 라우팅 프로토콜은 유선에 서 사용하는 라우팅 프로토콜을 무선 환경에서 사 용할 때의 자연스러운 확장 버전이라고 볼 수 있다. Proactive 라우팅에서 각 노드는 네트워크상의 다른 노드와의 연결을 위한 최신 정보를 기록하기 위해 하나 이상의 라우팅 테이블을 유지 관리한다. 테이 블의 각 행은 어떤 노드나 서브넷에 도달하기 위해 전달해야 할 다음 홉에 대한 정보와 함께 이 경로 에 대한 비용을 저장한다. 토폴로지 변경에 대한 정 보를 네트워크의 모든 노드에게 어떻게 전달하느냐 에 따라 table-driven 라우팅 프로토콜의 종류가 달 라지는데 현재 다양한 proactive 라우팅 프로토콜이 제안되어 있다[1].

반면 reactive 라우팅 프로토콜은 on-demand 라우 팅 프로토콜이라고도 불리는데, 이는 말 그대로 최 신 토폴로지 정보를 라우팅 테이블을 통해 유지 관 리하지 않고 필요에 따라 그때그때 경로를 찾아서 쓰는 방식을 따른다. 대표적인 reactive 라우팅 프로 토콜로는 Dynamic Source Routing (DSR)[8], ad hoc on-demand distance vector routing (AODV)[9], temporally ordered routing algorithm (TORA)[10] 등이 있다. 본 논문에서 제안하는 에너지 인지 소스 라우팅 프로 토콜은 이러한 reactive 방식의 라우팅 프로토콜에 속하며 DSR 프로토콜을 개선한 것이므로 DSR의 동작 방식에 대해 간략히 소개한다.

DSR은 가장 일반적으로 사용되는 reactive 라우 팅 프로토콜로, DSR에서는 한 노드가 전송 경로를 찾고자 할 때 route request 메시지를 주변 이웃 노 드에게 방송한다. 이를 수신한 이웃 노드는 route request 패킷의 헤더에 자신의 주소 정보를 추가하 여 다시 주변 노드에게 방송을 한다. 이러한 과정을 통해 route request 메시지가 목적지 노드나 목적지 노드로의 경로를 알고 있는 노드에게 전달되면, route request 헤더에 저장되어 있는 경로 정보를 따 라 역으로 소스 노드에게 route reply 메시지를 전송 함으로써 소스 노드에게 목적지 노드까지의 발견된 경로 정보를 알려주게 된다. 이와 같이 라우팅 경로 를 찾기 위한 route request와 같은 제어 패킷에 소 스-목적지 사이의 경로 정보를 모두 저장하는 방식 을 소스(source) 라우팅이라고 부른다. 일반적으로 DSR은 목적지 노드에 가장 먼저 도착한 route request 패킷의 경로를 선택하여 가장 짧은 홉 수를 갖는 라우팅 경로를 사용한다.

2. 저전력 라우팅 프로토콜

제안 라우팅 프로토콜의 목적인 생존시간 최대 화와 관련되어 기존에 제안된 대표적인 저전력 라 우팅 프로토콜에 대해 설명한다.

Minimum Power Routing (MPR)[2]은 소스에서 목 적지로 패킷을 전송하는데 소모되는 총 전력량(비 트당 에너지)을 최소화하는 것을 목적으로 다음과 같은 라우팅 전략을 사용한다.

여기에서 P(i,i+1)은 노드 i가 노드 i+1에게 송신할 때 사용하는 전력 값으로 링크 비용에 해당한다. 링 크별 전력 값 P는 노드가 고정된 송신 파워를 사용 하는 경우에는 패킷을 송신하는데 걸리는 시간에 비례하여 결정되며, 노드가 송신 파워를 동적으로 변경할 수 있는 경우에는 링크의 물리적인 거리에 따른 경로 손실(path loss) 값을 기반으로 결정된다.

Minimum Battery Cost Routing (MBCR)[3]은 노드 의 서로 다른 배터리 잔량을 고려하여 배터리 잔량 의 역수를 라우팅 비용으로 정의하고, 다음과 같이 라우팅 경로상의 모든 노드들의 배터리 비용의 합 을 최소화하는 것을 목적으로 경로를 선택한다.

여기에서 R_i는 노드 i의 배터리 잔량을 나타낸다. 결국 MBCR 방식은 배터리 잔량의 총합이 가장 큰 경로를 선택하게 함으로써 선택된 전송 경로의 생 존시간을 증대시키는 효과가 있다.

Min-Max Battery Cost Routing (MMBCR)[2, 3]은 MBCR의 라우팅 비용을 그대로 사용하면서 최종 경로 선택 전략만을 변경하여 경로 상에서 가장 작 은 배터리 잔량을 가진 노드를 피하도록 다음과 같 이 전송경로를 결정한다.

MBCR은 각 노드의 배터리 잔량을 공평하게 해주 는 효과를 가져다줌으로써 전체 네트워크 생존시간 을 증대시킨다.

Conditional Max-Min Battery Capacity Routing (CMMBCR)[3]은 MBCR과 MMBCR을 결합하여 사용 하는 방식으로 경로상의 모든 노드의 에너지 잔량이 정해진 임계값보다 큰 경우에는 MBCR을 적용하여 전송에 소비되는 전체 전력량을 감소시키는 전략을 취하고, 경로상의 하나의 노드라도 에너지 잔량이 임 계치보다 떨어지는 경우에는 MMBCR을 사용하여 경로 생존시간을 최대화하는 전략을 취한다.

이러한 CMMBCR은 기존 두 전략의 장점을 결합한 것으로 적절한 임계값(threshold)을 선택함으로써 네 트워크 에너지 소비 효율과 생존시간을 동시에 증 대시킬 수 있다.

Power-Aware Source Routing (PASR)[4]과 Energy Aware Routing (EAR)[5]은 전송 링크에서 소비되는 전력과 노드의 배터리 잔량을 동시에 고려하여 다 음과 같은 전략으로 라우팅 경로를 결정한다.

여기에서 α와 β는 양수를 갖는 가중치이다. 따라서 사용하는 라우팅 비용은 링크 ij의 생존시간의 역수 에 해당되며, 전송 경로 상의 모든 링크의 생존시간 의 합을 최대화 하는 경로를 최종 선택하게 된다. 두 라우팅 방식은 각 링크의 생존시간을 라우팅 비 용으로 고려하므로 기존에 소비 전력량이나 배터리 잔량만을 고려한 라우팅 방식 대비 보다 생존시간 측면에서 보다 나은 성능을 제공한다.

III. 제안 라우팅 프로토콜

제안 라우팅 방식은 기본적으로 기존 DSR 프로 토콜의 동작을 기반으로 하며 PASR이나 ESR과 같 이 전송 경로를 구성하는 각 링크에서 소모되는 송 수신 전력 값과 각 노드의 배터리 잔량 값을 동시 에 고려한다. 하지만 제안 방안의 경우 각 노드에서 소모되는 송수신 전력 값이 연결된 두 링크의 전송 률을 기반으로 계산되어 멀티홉 패킷 전송시 발생 하는 실제 전력소모가 전송 경로 결정에 반영된다. 이를 기반으로 최소 생존시간을 갖는 노드를 경로 상에 최대한 포함시키지 않도록 하는 min-max 라우 팅 전략을 채택하여 네트워크 생존시간을 최대화한 다. 여기에서는 고려하는 네트워크 생존시간과 환 경을 정의하고 제안하는 라우팅 비용과 프로토콜 동작절차에 대해서 자세히 설명한다.

1. 목적 함수 및 환경 변수

제안 라우팅 방식은 전송경로의 생존시간을 최 대화하는 것을 목적으로 한다. 본 논문에서 전송경 로의 생존시간은 경로를 구성하는 노드 중 배터리 가 소진되는 첫 번째 노드가 발생할 때까지의 시간 으로 정의된다. 따라서 <그림 1>과 같이 소스 노드 (S)와 목적지 노드(D)를 연결하는 하나의 경로에 대 하여 생존시간(L_e2e)은 다음과 같이 정의된다.

여기에서 L_j는 전송경로 상의 노드 j의 생존시간을 의미한다. 따라서 제안 라우팅 방식의 목적함수는 다음과 같이 L_path를 최대화 하는 S-D간 경로 (벡터 P)를 찾는 것이 된다.

애드혹 네트워크 환경에서 라우팅 설계를 위한 환경 변수를 다음과 같이 정의한다.

2. 라우팅 비용 설계

제안 라우팅에서 사용하는 라우팅 비용(C_j)을 도 출한다. 먼저 전송경로를 통해 D_req 크기의 패킷을 전송한다고 할 때 경로상의 노드 j에서 필요로 하는 패킷 수신시간(T j r x)과 송신시간(T j t x)은 각각 다음과 같이 계산된다.

또한 노드 j에서 D_req 크기의 패킷을 전송할 때 소모 되는 수신에너지(E j r x)와 송신에너지(E j t x)는 각각 다 음과 같이 계산된다.

따라서 식 (8)과 (9)로 부터 노드 j에서 소모되는 전 체 송·수신 에너지의 크기는 다음과 같이 계산된다.

노드 j가 갖고 있는 배터리 잔량 E_j과 식 (10)을 고 려하여 노드 j가 멀티홉 전송에 참여할 때 노드 j의 생존시간은 다음과 같이 결정된다.

따라서 노드 j의 선택에 따른 라우팅 비용은 노드 j 의 생존시간의 역수로 결정가능하며 이때 D_req 값은 모든 경로에서 동일하므로 생략 가능하므로, 제안 하는 라우팅 비용은 다음과 같이 표현된다.

즉, 제안 라우팅 비용은 각 노드의 배터리 잔량과 각 노드에 연결되는 수신링크와 송신링크의 전송률 에 의존한다. 기존 라우팅 비용의 경우 노드 간 하 나의 링크 상황에 따라 결정되는 에너지 소모량을 고려한 각 링크의 생존시간을 사용한 반면, 제안 라 우팅 비용의 경우 각 노드에 연결된 두 송수신 링 크의 전송률에 따라 소모되는 노드의 모든 에너지 소모량을 고려한 각 노드의 생존시간을 사용한다.

아울러, 라우팅 비용 계산식에 다음과 같은 제약 사항을 포함할 수 있다.

즉, 노드의 에너지 잔량이 사전에 정해진 임계치보 다 작거나 두 노드 사이의 링크 전송률이 정해진 임계치보다 작은 경우에는 라우팅 비용 값을 무한 대로 설정하여 해당 노드를 경로 상에 포함되지 않 도록 할 수 있다.

3. 라우팅 프로토콜 동작

제안 라우팅 프로토콜은 on-demand 라우팅 방식 을 기반으로 하여 기존의 DSR과 같은 소스 라우팅 프로토콜에 쉽게 접목이 가능하다. 단지, 제안 방안 의 경우 라우팅 비용 계산에 필요한 노드의 에너지 잔량(E_j) 정보와 링크 전송률(R_ij) 정보가 필요하므로 라우팅 시에 이들 정보가 새롭게 추가된다. 이외에 라우팅에 사용되는 제어 패킷의 종류 및 기능, 경로 탐색 및 유지를 위한 시그널링 절차 등은 앞 장에 서 설명한 DSR 프로토콜의 것을 그대로 사용가능 하다. 따라서 제안 라우팅 프로토콜은 기존 DSR 프 로토콜과 호환성을 가지며 약간의 변경을 통해서 쉽게 구현 가능하다는 장점을 갖는다.

<그림 2>는 제안하는 라우팅 프로토콜의 동작 절 차를 보여주며, 다음과 같은 절차에 따라 동작한다.

IV. 성능 평가

제안 방안과 성능 비교를 위하여 앞에서 설명한 MPR, MBCR, MMBCR, PASR 외에 가장 짧은 홉 수를 갖는 경로를 선택하는 Shortest Hop Routing (SHR)과 경로 상의 각 링크 전송률의 총 합이 가장 큰 경로를 선택하는 Max Sum Rate (MSR) 라우팅 방식을 추가적으로 고려하였다[1]. MATLAB을 사 용하여 Monte Carlo 시뮬레이션을 수행하였고, 각 결과는 1000번의 수행에 대해 평균을 취한 값이다.

<표 1>은 사용한 시뮬레이션 파라미터를 보여준 다. 20개의 노드가 1000×1000 m의 정사각형 영역에 서 랜덤하게 설치되며 이들 중 소스 노드와 목적지 노드도 랜덤하게 선택된다[4]. 각 노드가 갖고 있는 배터리 잔량 값은 실제 다수 노드의 배터리 상태를 고려할 때 일반적으로 normal 분포를 따른다고 볼 수 있으므로 평균 500 Joul과 표준편차 100 Joul을 갖는 normal 분포를 따르도록 설정하였다. 1024×10 바이트의 패킷을 23 dBm의 고정 송신 파워를 사용 하여 전송한다고 할 때 각 링크 상태에 따라 해당 노드가 송수신해야 하는 시간이 결정되도록 하였 다. 이때 모든 노드가 송수신하는데 드는 초당 전력 소비량은 각각 1.65와 1.4 watt로 설정된다[11]. 제안 방안의 경우 최종 경로 선택을 위하여 목적지 노드 에서 정해진 시간만큼 route request 메시지를 기다 리는데, 여기에서는 shortest hop을 통해 가장 먼저 도착한 메시지 이후에 이 shortest hop 보다 5홉이 더 큰 경로까지만 수신한다고 가정하여, 각 라우팅 수행 마다 [shortest hop, shortest hop+5] 사이의 전송 홉 수를 갖는 route request 패킷의 정보만을 이용하 여 최종 경로를 결정한다.

<그림 3>은 각 라우팅 방법의 평균 전송 홉 수 를 나타낸다. 항상 가장 짧은 경로를 선택하는 SHR 이 당연히 가장 작은 전송 홉 수를 보여주며, MSR 과 MPR은 SHR과 비슷한 성능을 갖는다. 이들 MSR과 MPR은 링크 상태에 기반하여 결정되는 전 송률과 전송 전력량을 각각 라우팅 비용으로 사용 하므로 서로 동일한 성능을 갖는다. 반면, 배터리 잔량을 라우팅 비용으로 사용하는 MBCR과 생존시 간을 라우팅 비용으로 고려하는 PASR의 경우 라우 팅 비용의 전체 합을 최소화하는 방식(min-sum)으 로 동작하므로 전송 홉 수가 증가하게 된다. 제안방 식의 경우 SHR 대비 전송 홉 수가 약간 증가됨을 볼 수 있다.

<그림 4>는 라우팅 방법에 따라 결정된 전송 경 로의 종단간 평균 전송률을 나타낸다. 전송률의 경 우 전송률을 최대화하는 방식으로 동작하는 MSR이 가장 좋은 성능을 보이며, MPR도 같은 링크 상태에 따라 전송 파워를 결정하므로 같은 성능 값을 갖는 다. SHR도 비슷한 성능을 가지며, 노드의 배터리 잔 량을 라우팅 비용으로 고려하는 MBCR, MMBCR, PASR 그리고 제안 방식은 높은 전송률을 갖는 경로 대신 배터리 잔량이 많은 노드를 선택하게 되므로 전송률은 다소 떨어지게 된다. 특히 MBCR과 PASR 은 MMBCR과 제안 방식과 같이 min-max 전략을 취 하지 않고 min-sum 전략을 취하므로 전송 홉 수와 마찬가지로 전송률도 낮게 나오게 된다.

<그림 5>은 라우팅 경로 상의 모든 노드가 패킷 을 송수신하는데 필요한 에너지의 총 합을 보여준 다. MPR의 경우에 각 노드의 전력의 총 합을 최소 화하는 방식으로 경로를 선택하기 때문에 가장 좋 은 성능을 보여주며, SHR과 MSR의 경우에 앞서와 같이 비슷한 성능을 갖는다. 하지만 배터리 잔량과 생존시간을 각각 고려한 MBCR과 PASR은 전송경 로의 홉 수가 증가하므로 전체 소비되는 에너지양 이 증가하게 된다. 반면 제안 방식은 MPR 보다는 약간 증가된 성능을 보여준다.

<그림 6>은 각 라우팅 방식별 설정된 경로의 생 존시간을 보여준다. 생존 시간 측면에서는 기존 라 우팅 방식들은 서로 비슷한 성능을 갖지만, 제안 방 식의 경우 가장 긴 생존시간을 보여준다. 이는 제안 방식이 경로상의 모든 노드의 배터리 잔량과 송수 신에 필요한 전력량을 실제 각 노드의 생존시간에 맞게 고려하였기 때문이다. 기존의 생존시간을 고 려한 PASR 방식은 경로의 종단간 모든 노드의 생 존시간을 정확히 고려하지 않기 때문에 제안 방식 보다 성능이 떨어진다.

Ⅴ. 결 론

제안 라우팅 프로토콜은 DSR 프로토콜을 기반으 로 노드의 송수신 전력 소모량과 배터리 잔량을 고 려하여 실제 패킷을 전송할 때 결정되는 경로의 생 존시간을 최대화하는 경로를 선택한다. 본 논문에 서는 이를 위한 새로운 라우팅 비용을 제안하였으 며, 경로 탐색시 발생하는 제어 패킷 오버헤드를 최 소화하는 라우팅 프로토콜을 설계하였다. 시뮬레이 션 결과 제안방식은 전송 홉 수, 전송률, 에너지 소 비량 측면에서 기존 방식과 비슷한 성능을 보이면 서, 생존 시간 측면에서는 기존 방식 대비 약 20% 의 이득을 보여준다. 제안 라우팅 프로토콜은 기존 DSR 프로토콜의 동작 방식과 호환성이 유지되며 제어 패킷 필드의 간단한 변경으로 구현 가능하므 로, 향후 에너지 절감이 요구되는 애드혹 네트워크 에 효과적으로 적용 가능하리라 기대된다.