1. 서 론

최근 센서 네트워크 기술의 발전으로 장비는 갈수록 소형화되고 통신은 증가하여 무선통신기술을 통한 여러 사물 인터넷 기술들이 발전하고 있다. 이는 소형 센서 네트워크를 통해서 여러 가지 사업을 할 수 있다. 일례로, 철새들에게 소형 센서를 장착하여 새들의 움직임을 포착하고 관찰할 수도 있고 센서를 부착한 부표를 바다에 뿌려서 해양에서 벌어지는 일들에 대해서 정보수집을 할 수도 있다. 이처럼 다양한 산업 분야에서 활발하게 이용되고 있다. 그러나 깊은 산속, 정글 밀림, 사람의 손길이 닿지 않은 지역 등 다양한 환경의 특성상 여러 가지 위험요인이 산재해 있어 현재의 기술을 이용한 탐색을 수행하기에는 큰 어려움이 따른다. 이를 해결하기 위한 많은 연구가 수행되고 있고, 최근 센서 네트워크 기술의 발달을 통해 무선 애드혹 센서 네트워크(ASNs)에 대한 연구가 활발하게 진행되고 있다[1].

애드혹 네트워크는 크게 소스 노드, 중계 노드, 싱크 노드로 구성되어있다. 센서 네트워크는 넓은 지역을 탐지해야 하 는데 무선 네트워크 특성상 각각 노드들은 광범위하게 배치되어 멀티 홉 통신을 수행하게 된다. 이는 탐지된 데이터가 싱크노드까지 도달하기 위해 중계되어야 하는 노드들의 양이 증가함을 의미한다. 기본적으로 무선 센서 네트워크 환경에서 네트워크 환경을 이루는 노드들은 배터리를 통해서 전력 을 공급받는 경우가 많다. 현재 배터리 기술로 센서 네트워크의 수명이 1년이라면 그 뒤로는 더는 센서를 활용 할 수가 없게 된다. 하지만 그 이후에도 계속해서 주변 환경에 대해서 지속적인 확인이 되어야 한다. 이처럼 센서 네트워크는 한 번 설치하면 그 다음에 유지보수 하는 것이 사실상 불가능하다. 따라서 배터리를 최소한으로 소모하기 위해서 네트워크 자원 을 효율적으로 이용해야 한다[1,2].

무선 네트워크에서는 제한된 통신 범위, 높은 전송 횟수, 잦은 전송지연으로 인해 데이터 손실이 자주 발생한다. 손실된 데이터를 복구하기 위해 노드들은 재전송을 수행해야 하며 이 과정에서 에너지 소모량이 증가하게 된다. 한정된 자원을 이용하여 네트워크를 구성해야 하고, 노드의 위치 변경이 많이 이루어지는 만큼 노드의 에너지 소모량 증가는 전체 네트워크의 수명감소로 직결되기 때문에 에너지의 중요성이 부각이 된다. 따라서 소스 노드로부터 싱크 노드까지 최적의 중계경로를 탐 색하여 에너지 효율을 높이는 과정이 필요하다[3,4].

본 논문에서는 다양한 환경에서 제약조건이 많고 예측하기 힘든 에너지의 소모가 발생할 수 있는 네트워크 환경에서 에너지 효율을 높이고 전체 네트워크의 수명을 늘리기 위해 Q-러닝을 적용한 라우팅 기법을 제안한다. 네트워크의 구성 노드들은 이웃 노드들의 정보가 담긴 자신의 Q 테이블을 가지 고 어떤 노드로 전송을 할지 선택하게 된다. 각 노드는 자신의 선택에 대해 보상을 받게 되고, 전송을 반복적으로 수행하며 데이터가 축적되면 최적의 전송경로를 찾을 수 있게 된다. 본 논문에서는 이를 통해 데이터의 전송확률을 높이고 전체 네트워크의 에너지 소모율을 균등하게 배분하여 결과적으로 네트워크의 수명을 증가시켰다. 앞서 언급했듯이 환경의 특성상 전송실패가 발생할 가능성이 크기 때문에 전송 실패에 대한 정보를 누적하고 학습시켜서 전송 성공확률을 증가시켰다.

본 논문의 구성은 다음과 같다. 2장에서는 애드혹 센서네트워크와 관련된 기존의 연구들을 소개하고 3장에서는 제안 기법의 기반이 되는 Q-러닝에 관해 설명한 뒤 제안된 알고리즘에 대해 세부적으로 설명한다. 4장에서는 성능평가를 통해 제안된 기법의 우수성을 검증한다. 마지막으로 5장에서 결론에 대해 논의한다.

2. 관련 연구

본 장에서는 ASN 환경에서 진행된 에너지 효율을 향상시키기 위한 라우팅 알고리즘 연구에 대해 살펴본다. 본장의 구성은 다음과 같다. 네트워크 전체의 수명을 증가시키는 방 법을 적용한 기법과 네트워크를 지역적으로 분할하여 라우팅을 수행하는 연구기법을 소개한다.

2.1 ASN의 전체 수명연장을 위해 제안된 라우팅 프로토콜

ASN 환경에서 네트워크 전체의 수명을 연장하기 위해 많은 연구들이 공통적으로 추구하고 있는 것은 불필요한 데이터의 재전송이나 에너지의 불균형 소비 등을 막는 것이다. 이를 해결하기 위해 네트워크의 전송 경로를 보다 효율적으로 설정, 혹은 재설정 하여 노드의 에너지 소모량을 감소시키거나 데이터의 전송 확률을 높이는 등 네트워크의 수명을 연장 하기 위한 다양한 라우팅 프로토콜이 제안되고 있다.

1) QLEC 기법

QLEC 기법[6]은 노드의 잔여 에너지를 고려해서 분산 네트워크를 형성한 다음 네트워크의 수명을 연장하는 것을 목표로 한다. 일반적인 네트워크의 라우팅 프로토콜은 노드 수, 또는 에너지의 소비량을 기반으로 하여 최단 경로를 찾는 알고리즘을 이용하여 수명연장을 달성한다. 그러나 이러한 방법을 통해 라우팅 프로토콜이 구성되면 일정한 경로를 통해 반복적인 전송이 발생하여 특정 노드들의 사용량이 급격하게 증가하게 되고 이는 해당 노드의 수명 단축을 초래한다. 다른 노드들에 비해 에너지 소모량이 많아진 노드는 빠르게 작동을 멈추게 되고, 라우팅 보이드 (Routing Void)를 생성하게 되어 네트워크 운용에 차질이 생기게 된다.

보다 잔류 에너지를 균등하게 사용하기 위해서 QLEC 기법에서는 강화학습 기법 중 하나인 Q-러닝을 이용하였다. 각 노드는 주변 노드들의 잔류 에너지의 정보를 각자 테이블에 저장한 후 그중에서 가장 잔류 에너지가 많은 노드를 헤드로 선택한다. 이를 기반으로 주변에 노드들을 가지고 클러스터링을 형성한다. 클러스터링에 포함되지 않은 노드들은 가장 가까우면서 에너지가 많은 헤드 노드를 선택하게 된다. 헤드 노드는 경로를 탐색하기 위해서 각 헤드 노드의 정보를 Q 테이블에 저장한다. Q-러닝 기법을 이용한 경로 탐색을 수행한다. 보상함수~(reward function)를 통해 현재 노드의 선택 결과에 대한 보상을 책정하여 Q 테이블에 반영한다. 이를 반복적으로 수행하며 에너지 소 비를 고르게 분배하여 수명을 연장을 달성할 수 있다[6].

2.2 지역화 기반 라우팅 프로토콜

지역화 기반 라우팅 프로토콜은 네트워크를 지역적으로 분할하여 라우팅을 수행하는 방식이다. 기본적으로 최적의 경로만을 탐색하는 방식으로 라우팅을 수행하기 때문에 전송효율이 높다는 장점이 있다. 그러나 경로 탐색에 포함되는 노드의 수가 많아질수록 효율이 떨어진다는 단점이 있다. 이를 해결하기 위해 중계 노드 탐색 범위를 제한하거나, 다음 홉 노드에 패킷이 도달할 수 있도록 전송에너지를 조절하는 등 다양한 기법이 연구되고 있다.

1) GeRaF

Geographic Random Forwarding 기법(GeRaF)[7]은 다음 홉 전달 노드를 선택하기 위해 RTS/CTS 메시지 메커니즘을 사용한다. 최적의 릴레이 노드를 선택하기 위해서 무 작위 선택에 기반한 포워딩 기술을 사용하였다. 먼저, 짧은 거리와 이용 가능한 노드의 평균 수를 함수로 구한 다음 다양한 멀티 홉 통신 솔루션을 구한다. 그리고 성능을 평가해서 최고의 릴레이 노드 하나를 선택하는 방식이다. 패킷이 싱크 노드에 전달되지 않는 한 모든 홉에서 같은 프로세스가 반복된다. 단점으로는 모든 노드가 참여해야 정확한 측정이 되고 과도한 에너지 소비와 RTS/CTS 패킷으로 인한 긴 지연은 GeRaF 프로토콜의 주요 제한 사항이다.

3. 제안된 기법

본 장에서는 ASN 환경에서 데이터를 다음 홉으로 전달하기 위해 이웃 노드들을 선별하는 과정을 소개한다. 이웃 노드의 선발은 강화학습 기법 중 유명한 기법인 Q-러닝을 기반으로 수행하게 된다. 본 장에서는 우선 Q-러닝에 대한 소개를 한 후 제안하는 라우팅 기법을 소개한다.

3.1 강화학습과 Q-러닝 알고리즘

본 절에서는 제안하는 기법의 이론적 기반이 되는 강화학습(Reinforcement Learning)과 Q-러닝을 소개한다. 우선 강화학습의 기본 모델에 관해 설명하고 Q-러닝이 유도되는 과정을 수식을 통해 설명한다.

1) 강화학습(Reinforcement Learning)

강화학습은 경험을 통해 학습하는 인간의 학습방식을 기계에 적용하여 연구한 학습기법이다. 특정 에이전트(agent)가 특정한 환경 탐색할 때 특정 상황(state)에서 특정한 행동(action)을 취하여 얻을 수 있는 보상(reward)에 기반하여 보상을 극대화할 수 있는 행동의 정책(policy)을 정의하는 것이 목적이다. Fig. 1은 에이전트가 강화학습을 통해 정책을 찾아가는 과정에 대한 개념도이다[5]

무언가를 학습하기 위해서는 문제에 대한 정의가 필요하다. 강화학습에서는 이러한 문제를 에이전트의 환경으로 정의하며 이는 마르코프의 의사결정 프로세스(MDP)로 표현한다[5]. 일반적인 MDP는 [TeX:] $$[S, A, P, R]$$ 총 4개의 인자로 구성되어있고, S는 상태(state), A는 행동(action), P는 상태 전이확률(state transition probabilities), R은 보상(reward)의 집합을 의미한다. 상태 전이 확률 P는 [TeX:] $$P_{s \rightarrow s^{\prime}}^{a}$$로 구성되며 이는 현재 상태 S서 특정 행동A를 통해 다음 상태 [TeX:] $$S^{\prime}$$으로 이동할 확률을 의미한다. [TeX:] $$R(s, a)$$는 상태s에서 행동a 취했을 때 받을 수 있는 보상을 의미하고 [TeX:] $$R_{s \rightarrow s^{\prime}}^{a}$$는 현재 상태s서 특정 행동 a를 통해 다음 상태[TeX:] $$s^{\prime}$$으로 이동했을 때 받을 수 있는 보상을 의미한다. 시간t에서 [TeX:] $$P_{s \rightarrow s^{\prime}}^{a}$$와 [TeX:] $$R(s, a)$$를 수학적으로 표현하면 Equation (1)과 같다.

강화학습에서 정책(policy)[TeX:] $$\pi$$는 상태[TeX:] $$s \in S$$에서 행동[TeX:] $$a \in A(s)$$를 취할 확률[TeX:] $$\pi(s, a)$$를 의미한다. 정책[TeX:] $$\pi$$에서 상태S의 값은

[TeX:] $$V^{\pi}(S)$$로 정의되며 이는 정책[TeX:] $$\pi$$에 속한 행동을 취했을 때의 기대 보상을 의미한다. 이를 수식으로 표현하면 Equation (2) 와 같다.

여기서 [TeX:] $$E_{\pi}\{\}$$는 시간t에서 정책[TeX:] $$\pi$$에 속한 행동의 결과로 얻게 되는 보상의 총합을 의미하고, [TeX:] $$\gamma$$는 미래의 보상에 대한 dis-count factor이다. Bellman's optimality를 통해 Equation(2)를 Equation (3)과 같이 재귀방정식으로 재정의할 수 있다.

3.2 Q-러닝 알고리즘

강화학습의 기법 중 가장 유명한 Q-러닝 기법은 특정한 모델이 없이 다양한 상황에 적용하여 사용할 수 있는 특징(Model-free)이 있다. 기본 모델 없이 최적의 정책을 산출할 수 있어 다양한 상황에서 유동적으로 사용 가능하다는 장점이 있다. Q-러닝은 Q값이라 불리는 상태-행동의 쌍[TeX:] $$Q(s, a)$$,을 기반으로 학습 한다. 상태s 정책[TeX:] $$\pi$$에 속한 행동a를 통해 얻을 수 있는 값은 [TeX:] $$Q^{\pi}(s, a)$$로 정의되며 이를 수식으로 표현하면 Equation (4)와 같다[1].

Equation (3)과 (4)의 식을 통해 Equation (5)의 값을 구할 수 있다.

[TeX:] $$Q^{*}\left(s_{t}, a_{t}\right)$$는 상태[TeX:] $$s_{t}$$에서 행동[TeX:] $$a_{t}$$를 수행한 후 최적의 정책을 따랐을 때의 기대 보상을 의미한다. 이는 반복 수행을 통해 근사화될 수 있다.

여기서 [TeX:] $$\alpha$$ learning rate로 Q값을 업데이트할 때 현재의 Q값과 미래의Q값 사이의 가중치로서 학습 속도를 조정하는 데 사용된다.

3.3 애드혹 센서 네트워크 라우팅 프로토콜

애드혹 센서 네트워크 라우팅 프로토콜이 어떻게 작동하는지 자세하게 살펴본다. 제안된 프로토콜은 환경설정, 라우팅 알고리즘으로 구성되어 있다.

1) 애드혹 센서 네트워크 환경 알고리즘

환경설정 알고리즘의 핵심은 센서네트워크의 환경을 설정하 는 것이다. 독립적인 제어를 위해서 각 센서노드들은 Control_Record에 라우팅 정보를 개별적으로 관리한다. Control_Record는 Path_Cost(PC)와 보상 기록 행렬[TeX:] $$(\mathbb{U}[\cdot])$$두 개의 파라미터로 구성되어있다. PC는 가까운 싱크노드까지의 통신 수행 능력 의 정도를 나타내고, [TeX:] $$\mathbb{U}[\cdot]$$는 노드가 취한 행동의 보수가 기록 된 행렬이다. Control_Record의 정보는 노드들이 라우팅 경로를 결정하는데 이용된다.

PC는 가까운 싱크노드까지 라우팅을 수행할 때 발생하는 [TeX:] $$\operatorname{Lin} k \operatorname{cost}\left(L_{c}\right)$$를 통해 구한다. 두 센서 노드 사이의 링크 비용 을 추정하기 위해 [TeX:] $$L_{c}$$를 정의한다. 각 센서노드에서 PC값은 현재 노드에서 싱크노드까지의 [TeX:] $$L_{c}$$의 총합으로 계산된다. 노드의 에너지 잔량과 에너지 소비율을 기반으로 [TeX:] $$\delta_{i}$$에서 [TeX:] $$\delta_{j}$$까지의 [TeX:] $$L_{c}(i, j)$$는 Equation (7)과 같이 구해진다.

여기서 [TeX:] $$d_{(i, j)}$$는 [TeX:] $$\delta_{j}$$와[TeX:] $$\delta_{j}$$사이의 거리이고, [TeX:] $$v_{(i, j)}$$는 [TeX:] $$\delta_{j}$$와[TeX:] $$\delta_{j}$$ 사이의 상대속도, [TeX:] $$n_{j}$$는 [TeX:] $$\delta_{j}$$의 이웃 노드의 수, [TeX:] $$\mathcal{E}_{i}$$는 [TeX:] $$\delta_{i}$$의 에너지 잔량을 의미한다. [TeX:] $$D_{M}$$과 [TeX:] $$V_{M}, E_{M}, N_{j}$$는 각각 센서 노드의 최대통신반경, 최대속도, 초기 에너지의 양, 의 이웃 노드의 최대 수를 의미한다.

본 논문에서는 실시간으로 변동하는 [TeX:] $$L_{c}$$를 추정하기 위해 각 파라미터들 사이에 [TeX:] $$\alpha_{i}, \beta_{i}, \gamma_{i}$$를 가중치로 부여한다. 현재 노드 [TeX:] $$\delta_{i}$$와 다음 노드[TeX:] $$\delta_{j}$$사이의 거리가 가까울 경우, 노드 사이의 상대속도가 데이터 전송에 미치는 영향이 커지게 된다. 이러 한 경우에는 노드 사이의 상대속도에 더 높은 가중치를 부여하기 위해 [TeX:] $$\beta_{i}$$에 높은 값을 부여하는 것이 적합하다. 반대로 노드 사이의 거리가 멀어질수록 상대속도가 미치는 영향이 줄어들기 때문에 [TeX:] $$\beta_{i}$$의 밀도 [TeX:] $$\left(\frac{n_{j}}{N_{j}}\right)$$의 영향을 크게 받지 않으며 전송이 가능하다. 이러한 경우 [TeX:] $$\gamma_{i}$$에 높은 값을 부여하여 에너 지의 잔량에 더 높은 가중치를 두는 것이 적합하다. 반대로 [TeX:] $$\delta_{j}$$의 밀도에 높은 가중치를 부여하는 것이 적합하다. [TeX:] $$\beta_{i}$$와[TeX:] $$\gamma_{i}$$의 조화 평균인 [TeX:] $$\alpha_{i}$$를 거리와 속도, 에너지 잔량과 밀도 사이의 가중치로 부여하여 실시간으로 변화하는 환경을 반영한다.

네트워크 토폴로지를 구성하기 위해, 초기에는 각각의 개 별노드에서 이웃노드들의 [TeX:] $$L_{c}$$값을 추정한다. 싱크 노드가 1홉 거리의 이웃 노드로 위치하고 있는 노드들은 해당 노드에서 싱크노드까지의 [TeX:] $$L_{c}$$값을 PC값으로 하고 [TeX:] $$P C_{i}$$을 Equation (8)과 같이 설정한다.

여기서 [TeX:] $$N_{i}$$는 [TeX:] $$\delta_{i}$$의 이웃노드들의 집합이다. Equation (8)에서 계산된 이웃노드들의 PC값을 토대로 [TeX:] $$\mathbb{U}[\cdot]$$값이 Equation (9)와 같이 초기화된다.

[Algorithm 1]은 환경설정 알고리즘을 pseudo code 로 나타낸 것이다. 1~2단계에서는 노드 [TeX:] $$\delta_{i}$$와 [TeX:] $$\delta_{j}$$사이의 거리를 통해 가중치 [TeX:] $$\beta_{i}$$를 구하고, 노드 [TeX:] $$\delta_{i}$$의 에너지 잔량을 통해 가중치 [TeX:] $$\gamma_{i}$$를 구한다. 가중치 [TeX:] $$\beta_{i}$$와 [TeX:] $$\gamma_{i}$$의 조화평균으로 가중치 [TeX:] $$\alpha_{i}$$를 구한 후, 3단계에서 Equation (7)의 식을 통해 노드 [TeX:] $$\delta_{i}$$에서 [TeX:] $$\delta_{j}$$까지의 [TeX:] $$\operatorname{Lin} k \cos t\left(L_{c}\right)$$를 구한다. 4단계에서는 현재 노드가 싱크 노드와 1홉거리 이웃인지를 판별한다. 1홉 거리 이웃이라 면 현재 노드에서 싱크노드까지의 [TeX:] $$L_{c}$$값을 PC값으로 설정한 후 그 값을 이웃 노드들에 전달한다. 5단계에서는 이웃 노드 들에 PC값을 전달받을 경우, 현재노드로부터 해당 이웃노드 까지의 [TeX:] $$L_{c}$$값과 전달받은 PC값을 더하여 현재 노드의 PC값을 설정한다. 6단계에서는 Equation (8)의 식을 통하여 노드 [TeX:] $$\delta_{i}$$의 PC값을 결정한다. 7단계에서는 Equation (9)의 식을 통 해 이웃 노드들의 PC값을 토대로 [TeX:] $$\mathbb{U}[\cdot]$$값을 초기화 한다.

2) 애드혹 센서 네트워크 라우팅 알고리즘

제안된 환경설정 알고리즘이 완료되면 애드혹 센서 네트워크의 가상 토폴로지는 싱크노드를 뿌리로 하는 스패닝트리로 형성된다. 그러나 라우팅 작업 중 실시간으로 변화하는 환경에 의해 PC값과 [TeX:] $$\mathbb{U}[\cdot]$$값은 동적으로 변화하게 되며 이를 제어할 추가적인 라우팅 알고리즘이 필요하다.

애드혹 센서 네트워크의 라우팅 알고리즘을 설계하기 위해 Multi-player Markov Decision Process(MMDP)를 고려한다. 각각의 센서노드들은 플레이어의 역할을 수행하고, 플레이어 [TeX:] $$i\left(\delta_{i}\right)$$는 최적의 라우팅 [TeX:] $$\psi_{i}^{*} \in \mathbb{A}_{i}$$를 찾는다. 여기서 [TeX:] $$\mathbb{A}_{i}$$는 노드[TeX:] $$\delta_{i}$$의 행동(action)들의 집합으로 [TeX:] $$\left|\mathbb{A}_{i}\right|=\left|N_{i}\right|$$의 관계가 형성되고, [TeX:] $$\psi_{i}^{*}$$는 1홉 거리에서 이웃노드들 중 하나의 노드를 선택하는 라우팅 정책을 의미한다. 시간 t에서 노드 [TeX:] $$\delta_{i}$$의 상태와 행동은 [TeX:] $$s_{i}(t)$$와 [TeX:] $$a_{i}(t)$$로 정의할 수 있으며 각각 [TeX:] $$s_{i}(t) \in \mathbb{S}_{i}, a_{i}(t) \in \mathbb{A}_{i}$$관계를 갖게 된다. [TeX:] $$U_{i}\left(s_{i}(t), a_{i}(t)\right)$$는 시간 t에서 노드 [TeX:] $$\delta_{i}$$의 상태가 [TeX:] $$s_{i}(t)$$일 때 행동 [TeX:] $$a_{i}(t)$$를 취했을 때 발생하는 [TeX:] $$\delta_{i}$$의 보상을 의미한다. [TeX:] $$U_{i}(s, a)$$ 함수는 노드 [TeX:] $$\delta_{i}$$의 동작 및 성능을 결정하기 때문에 Q-러닝의 학습에 중요한 역할을 수행한다.

Q-러닝을 적용한 ASN 라우팅 알고리즘의 최종 목표는 패킷을 최대 보상으로 싱크 노드에 전달하는 것이다. [TeX:] $$a_{i}(t)=a_{i}^{m}$$는 시간 t에서 m번째 이웃 노드를 선택하는 행동을 의미하고, 이때의 [TeX:] $$\mathbb{U}_{i}[\cdot]$$는 Equation (10)과 같다.

여기서 [TeX:] $$P C_{m}^{t}$$는 시간 t에서 m번째 이웃 노드의 PC값을 의미하고, [TeX:] $$S_{i}^{m}(t)$$는 [TeX:] $$a_{i}^{m}$$의 결과(전송이 성공했는지, 실패 했는지)를 의미한다. m번째 이웃 노드의 PC값에 [TeX:] $$\delta_{i}$$와 [TeX:] $$\delta_{m}$$의 [TeX:] $$L_{c}$$값을 더하면 [TeX:] $$\delta_{i}$$부터 싱크노드까지의 총 전송 비용을 구할 수 있게 된다. 따라서 [TeX:] $$P C_{m}^{t}+L_{c(i, m)}$$의 값은 낮을수록 높은 전송효율을 갖게 된다. [TeX:] $$a_{i}^{m}$$의 전송 성공여부를 누적으로 학습하기 위해 [TeX:] $$t-\Delta t$$ 시간부터 t시간까지의 이웃노드들의 전송 성공여부를 [TeX:] $$S_{i}^{m}(t)$$에 저장한다. 이때 [TeX:] $$a_{i}^{m}$$로 선택되어 전송이 성공하였을 경우엔 1, [TeX:] $$a_{i}^{m}$$로 선택되지 않았을 경우엔 1의 보상을 부여하고 전송이 실패하였을 경우엔 0.9의 페널티를 부여한다. 누적된 성공확률을 보상에 반영하여 노드들을 정확하게 학습시킬 수 있다.

Q-러닝 알고리즘은 기본적으로 greedy알고리즘을 기반으로 동작한다. 가장 높은 Q값을 갖는 노드를 선택하는 행동을 취해 가장 높은 보상을 받는 것을 목표로 한다. 이는 싱크노드까지 패킷을 전달할 때 최적의 경로를 선택하는데 도움이 된다[8].

효과적으로 Q-러닝 알고리즘을 발전시키기 위해서는 [TeX:] $$\varepsilon-\text { greedy }$$ 정책을 적용해야 한다. [TeX:] $$\varepsilon-\text { greedy }$$정책이란 답을 얻기 위해서는 충분하게 경험해보는 것이 필요한데 단순히 greedy알고리즘을 통해 선택할 경우에는 얻은 답이 최적의 해답이라고 장담할 수 없기 때문에 [TeX:] $$\mathcal{E}$$값이라는 일정한 모험의 요소를 추가한 것이다. [TeX:] $$\mathcal{E}$$값 을 정의하는 것은 확률 결정 문제이다. 상태 s에서 [TeX:] $$\varepsilon-\text { greedy }$$정책 [TeX:] $$\pi$$를 통해 행동 a를 선택할 확률은 [TeX:] $$\pi(a \mid s)$$로 정의된다.

멀티 센서 라우팅 모델을 통해 각 센서 노드는 현재 ASN의 시스템 상황을 학습하여 [TeX:] $$\pi(a \mid s)$$를 통해 릴레이노드가 선택될 확률을 결정한다. [TeX:] $$\pi(a \mid s)$$는 Equation (11)과 같이 정의된다.

여기서 m은 액션으로 선택하는 노드를 방문한 횟수를 의미하고 [TeX:] $$\mathcal{E}$$값은 최적의 노드를 제외한 나머지 노드를 랜덤 하게 선택할 수 있도록 주어진 상수 값이다.

[알고리즘 2]는 라우팅 알고리즘을 pseudo code로 나타낸 것이다. 1단계에서는 Equation (1)의 식을 이용하여 노드[TeX:] $$\delta_{i}$$의 m번째 이웃노드가 시간 t에서 릴레이노드로 선택되었을때의 [TeX:] $$\delta_{i}$$의 보상[TeX:] $$\mathbb{U}[\cdot]$$을 계산한다. 2단계에서는 시간 t에서 노드 [TeX:] $$\delta_{i}$$의 행동 [TeX:] $$a_{i}^{m}$$의 결과가 성공했는지 실패했는지를 기록한 [TeX:] $$S_{i}^{m}(t)$$를 통해 실패한 전송에 대한 페널티를 부여한다. 3단계 에서는 Equation (10)을 통해 획득한 유틸리티 [TeX:] $$\mathbb{U}[\cdot]$$를 Equation (6)에 대입하여 이웃노드들의 Q 값을 계산한다. 4단계에서는 Q-러닝 알고리즘을 효과적으로 발전시키기 위해 Equation (11)을 이용하여 [TeX:] $$\varepsilon-\text { greedy }$$정책을 설정한다. 5단계에서는 계산된 유틸리티 [TeX:] $$\mathbb{U}_{i}[\cdot]$$와 [TeX:] $$\varepsilon-\text { greedy }$$정책을 기반으로 다음 중계노드를 선택하여 데이터를 전송한다.

3.4 Q-러닝 알고리즘

본 논문에서는 Q-러닝 알고리즘을 적용한 새로운 라우팅 알고리즘을 제안한다. Q-러닝 기반의 라우팅 모델을 사용하여 시 시각각으로 변화하는 상황을 기록, 수집한다. 따라서 센서 노드는 현재 상황을 개별적으로 학습하고 최상의 라우팅 경로를 찾아낸다. 현재의 환경 조건은 동적으로 변화하므로 라우팅 작업중에 각 노드는 주기적으로 라우팅 정보를 업데이트하고 현재 전략을 재평가한 후 그에 따라 패킷 전달을 위해 인접 노드 중 하나를 선택한다. 이러한 절차를 통해 네트워크 전체의 전송 효율을 높일 수 있고 결과적으로 네트워크의 수명을 연장할 수 있다. 제안된 라우팅 알고리즘의 주요한 단계는 다음과 같다.

Step1: 싱크 노드가 setup메시지를 브로드캐스팅 한다. 메시 지를 수신한 센서 노드는 Equation (7)의 식에 따라 [TeX:] $$L_{c}$$를 개별 적으로 추정한 후 setup메시지를 이웃 노드들에 전파한다.

Step2: 노드가 다수의 setup메시지를 수신하면, 이 노드는 싱크 노드에 도달하기 위해 이들 중 하나를 선택하고 Equation (8)과 (9)의 식에 따라 PC값과 [TeX:] $$\mathbb{U}[\cdot]$$를 초기화한다.

Step3: 라우팅 결정 순간 마다, 각각의 센서노드들은 계산 된 유틸리티[TeX:] $$\mathbb{U}_{i}[\cdot]$$와 [TeX:] $$\varepsilon-\text { greedy }$$정책에 따라 통계적으로 다음 노드를 선택한다.

Step4: 선택된 라우팅 전략을 기반으로 각 센서 노드들의 [TeX:] $$\mathbb{U}[\cdot]$$ 벡터값이 실시간으로 수정된다.

Step5: 일정한 시간마다, 각각의 센서노드들의 PC,[TeX:] $$\mathbb{U}[\cdot]$$및 [TeX:] $$P(\cdot)$$값은 Equation (8), (9) 및 (11)의 식에 의해 주기적으로 재추정된다.

Step6: 시간 에서 각 노드들의 라우팅 전략은 -learning mechanism을 사용하여 Equation (6)의 식에 따라 선택된다.

Step7: 자신의 데이터를 싱크 노드로 전달하기 위해 각 노드들은 Step1~6을 반복적으로 수행한다.

Step8: 반복적인 라우팅 절차를 통해 노드들은 개별적으로 학습하고 이를 통해 최적의 라우팅 경로를 선택하여 네트워크 전체적으로 균형 잡힌 시스템 성능을 달성한다.

4. 성능 평가

이번 장에서는 본 논문에서 제안하는 Q-러닝 기반의 애드 혹 센서 네트워크 라우팅 프로토콜의 성능을 시뮬레이션을 통해 기존에 존재하는 타 기법들과의 차이를 비교한다. 이를 통해 본 논문에서 제안하는 기법의 성능을 평가한다. 시뮬레이션은 C++ 을 이용하여 개발한 시뮬레이터를 이용하였다. 성능평가를 위한 네트워크 환경은 다음과 같다.

Table 1. System Parameters는 성능 평가를 위해 가정한 네트워크 환경 및 매개변수이다. 각 실험의 성능 평가 기준은 한 번 전송에 참여하는 평균 노드의 수, 라우팅 성공률(Routing Success Rate: RSR), 전체 네트워크의 평균 수명(Average Lifetime of entire Network: ALN) 등에 대해 비교하였다.

QASN(Q-LearningAd-hocSensorNetwork)의 성능 분 석을 위해 기존의 지리적 라우팅의 기법인 GeRaF[7]기법과

Q-러닝 기반의 기법인 QLEC[6]기법을 통해 라우팅 성공률과 평균 수명에 대해 비교하였다. 각 실험은 100회 반복 시뮬레이션을 수행한 후 그 평균값을 사용하였다.

Fig. 2는 소스 노드부터 싱크 노드까지 데이터를 전송할 때 한 라운드 전송에 참여하는 노드의 수이다. 위의 그래프는 제안된 기법과 GeRaF기법과 QLEC기법의 평균 노드의 수를 보여준다. QLEC과 GeRaF기법은 평균 35개와 30개 정도로 비슷한 결과를 보였다. 그 이유는 QLEC 기법은 클러스터링 알고리즘을 이용하기 때문에 하나의 헤드 노드가 포함하고 있는 노드의 수가 많으므로 전송에 참여하는 노드의 수가 다른 기법에 비해 많아서 라우팅에 GeRaF 기법은 브로드 캐스트 기반으로 데이터를 전송을 수행하기 때문에 평균 노드의 수가 많다. 반면 제안된 기법은 에너지의 잔량과 밀도 등 복합적인 요소를 고려하여 최대 30개의 노드만을 참여노드로 구성하였다.

Fig. 3은 제안된 기법과 GeRaF 기법과 QLEC기법의 전체 전송 횟수 중 소스 노드부터 싱크 노드까지 라우팅을 성공한 전송의 비율을 나타낸다. 실험 결과 제안된 기법은 GeRaF 기법과 비교하면 약 8.89%가량, QLEC기법에 비해서는 약 1.75% 더 높은 성공률을 보였다. 전송실패에 대한 별다른 대처가 없는 GeRaF 기법은 잦은 전송지연과 데이터 유실이 발생하는 넓은 환경의 특성상 라우팅 성공률이 상대적으로 떨어진다. 또한 라우팅 내에 중계 노드의 수가 적어질수록 라우팅 성공률이 낮아지게 된다. QLEC 기법의 경우 클러스터링을 형성하는 특성상 라우팅 성공확률이 상대적으로 높다. 하지만 클러스터링에서 헤드 노드의 전송량이 많으므로 에너지

소비가 편중된다. 데이터 전송이 실패하였을 경우 해당 노드의 Q 값을 낮추는 페널티를 부여한 후 재전송을 수행한다. 중계 실패 노드의 Q 값이 다른 노드의 Q 값보다 낮아질 때까 지 반복적으로 수행하기 때문에 에너지의 낭비가 발생한다는 단점 또한 있다. 제안된 기법은 전송실패가 발생한 노드에 대해 Equation (10) 을 이용하여 페널티를 부여한다. 현재 시점에서부터 다섯 번의 전송에 대한 실패를 누적하여 적용하므로 전송실패노드를 중계 노드로 선택할 확률이 기하급수적으로 낮아진다. 위 실험을 통해 제안된 기법은 GeRaF 기법에 비해 높은 라우팅 성공률을 갖는 것을 확인할 수 있다.

Fig. 4는 데이터 전송 시작부터 네트워크 종료할 때까지 제안된 기법과 GeRaF 기법과 QLEC기법의 평균 전송 횟수를 나타낸다. 실험 결과 제안된 기법은 GeRaF 기법과 비교하면 26.35%,QLEC기법에 비해 10.93%만큼 증가한 횟수로 전송을 수행하였다. GeRaF 기법의 경우에는 에너지 효율을 중시하는 라우팅을 하므로 정해진 중계 노드만을 전송에 참여하므로 라우팅 내의 중계 노드들의 수명이 다하면 다른 노드의 수명과 상관없이 네트워크가 종료된다. 네트워크의 밀도에 따라 변하는 특성을 보여주고 있다. 밀도가 높으면 라우팅 노드의 수가 증가하여 단거리 통신의 효율적 통신이 가능 하지만 밀도가 낮으면 노드 간의 수가 적어지기 때문에 통신에 들어가는 에너지량이 높아진다. 따라서 다른 기법들에 비해 전송 횟수가 현저하게 낮게 나타난다. QLEC 기법은 클러스터링 형성을 통해서 헤드 노드 간의 통신을 한다. 이렇게 되면 헤드 노드의 자원이 참여하는 자원보다 낮아지게 되면 헤드 노드를 교체하게 되고 헤드 노드는 다시 그룹에 속한 노드가 된다. QLEC기법은 GeRaF의 기법보다 높은 전송 횟수를 보여준다. 하지만 헤드 노드의 변경과 클러스터링을 형성해야 하는 과정에서 소모되는 에너지의 양이 많다. 형성된 클러스터 헤더 간의 네트워크 간에 재전송으로 인한 에너지 소모량이 많아 특정 노드의 수명이 빠르게 줄어든다는 단점이 있다.

Fig. 5는 시뮬레이션을 반복 수행할 때 전송에 참여하는 노드의 수의 평균의 변화량을 나타낸다. 시간의 흐름은 데이터의 전송 횟수로 대체하여 실험을 진행하였다. GeRaF 기법은 지리적 라우팅과 EPA라는 패킷의 이득, 신뢰성 및 에너지 소비의 균형을 맞추는 단위 에너지 소비당 예상되는 패킷 향상 값을 통해 효율적인 경로를 탐색하는 라우팅 프로토콜이

다. 전송 초기 단계부터 최적의 경로를 찾아가기 때문에 제안된 기법과 QLEC기법보다 적은 중계 노드를 갖게 된다. 시간의 흐름에 따라 제안된 기법과 QLEC기법은 학습을 통해 최적의 경로를 찾아가게 되어 포함하는 중계 노드의 수가 줄어들게 되고 GeRaF 기법의 경우 EPA의 상한선 내에 효율적인 노드의 수가 거리에 따라서 적어지게 된다. 노드들의 에너지가 적어지게 되면 통신에 들어가는 에너지가 많아지게 되고 효율이 낮아진 노드들은 통신에 참여할 수 없게 된다. GeRaF의 경우에는 밀도가 높은 경우의 통신에 적합하기에 평균 수명이 짧은 단점이 있다. QLEC기법은 노드 간의 클러스터링을 형성하고 클러스터링에서 가장 에너지가 높은 노드 를 헤드 노드로 선정하게 된다. 그리고 클러스터링에서는 에너지의 잔량을 가지고 통신을 하게 된다. 헤드 노드들은 중계 노드로써 헤드 노드 간의 통신을 통해서 싱크노드까지 통신을 하게 된다. 에너지 잔량을 기반으로 헤드 노드를 선택할 경우 한 홉 간 전송의 에너지 효율은 높아질 수 있지만 싱크 노드까지 완성된 최적의 라우팅 경로에 포함된 헤드 노드의 수가 많아질 수 있다는 문제점이 발생한다. 제안된 기법은 다음 중계 노드를 선택할 때 에너지의 잔량 뿐만 아니라 노드 간 거리, 중계 노드의 밀도 등 다양한 환경변수를 고려하여 더욱 효 과적인 학습 체계를 구축하였다. 이를 통해 제안된 기법은 데이터를 1회 전송할 때 최소한의 노드를 이용하여 높은 에너지 효율을 달성하였다. 시뮬레이션의 결과 제안된 기법은 QLEC 기법보다 약 10.9% 높은 전송 횟수를 달성하여 네트워크의 수명 연장을 효과적으로 달성하였음을 확인할 수 있었다.

5. 결 론

ASN 라우팅 체계는 특정 제어 문제에 집중되어 있다. 그러나 이러한 점 때문에 균형 잡힌 시스템 성능을 얻는 것이 매우 어렵고 부적합하다. 환경적인 제약요소가 많고 자연적인 장애물로 인해 다양한 위치에 센서 노드들이 배치되지 못하여 불필요한 에너지 소비와 전송 지연 등이 발생하게 된다. 물리적인 관여가 어려운 환경의 특성상 균형 잡힌 시스템 성능은 시스템 전체의 수명에 관여하여 매우 중요하게 작용한다. 따라서 전체 네트워크의 수명을 증가시키기 위해서는 각 노드에서 소모되는 에너지의 양을 균등하게 배분하는 방법이 필요하다.

본 논문에서는 효율적인 에너지 소비를 통해 애드혹 센서 네트워크의 수명을 연장하기 위한 Q-러닝을 이용한 라우팅 프로토콜을 제안하였다. 또한 전송 실패 노드에 대한 페널티를 누적으로 부과하여 실패 노드를 회피할 확률을 높였고 에너지, 거리 등 다양한 환경요소를 고려하여 학습 효과를 높이는 기법을 제안하였다. 시뮬레이션을 통해 제안된 기법은 GeRaF 기법과 비교하면 약 8.89%가량, QLEC기법에 비해서는 약 1.75% 더 높은 성공률을 보였다. 전송 횟수에 대해서 비교하면 제안된 기법은 GeRaF 기법과 비교하면 26.35%, QLEC 기법에 비해 10.93%만큼 증가한 횟수로 전송을 수행하여 네트워크 수명 증가를 달성하였음을 확인할 수 있었다. 제안된 기법은 네트워크 내의 생존 노드의 수가 감소하여도 노드들의 잔여 에너지량을 검토하여 최적의 경로를 탐색함으로써 높은 라우팅 효율을 달성했음을 알 수 있었다. 또한 정책을 통해 시간이 지남에 따라 높은 학습효율을 달성하여 노드들의 에너지 소비율을 균등하게 배분해 전체 네트워크의 수명연장을 달성한 것을 확인하고 기존의 기법에 비해 더욱 효율적인 라우팅 기법임을 증명하였다.