SL, RL을 기반으로 한 라우팅 알고리즘 - 2

* 본 글은 IRSML: An intelligent routing algorithm based on machine learning in software defined wireless networking 을 읽으며 공부한 내용을 바탕으로 작성함. (출처: https://onlinelibrary.wiley.com/doi/full/10.4218/etrij.2021-0212)

 

2. Related Works

2.1 Supervised learning(SL)-based routing for wireless networks

 

SL은 input과 output이 동시에 주어지는 학습 방법이다.

무선 네트워킹 분야에서 SL은 주로 optimal routing 알고리즘에서 link quality를 예측하는데 사용된다.

Wang이 작성한 Predicting link quality using supervised learning in wireless sensor networks에 따르면, Link quality를 예측하는 라우팅을 위해서는 메트릭맵을 사용할 수가 있다. 해당 논문의 저자는 이 메트릭 맵의 성능 평가를 위해서 30-node sensor network testbed를 사용했다. 그 결과로 high data rate에서 MetricMap이 MintRoute를 능가한다는 사실을 알 수 있었다. 게다가 MetricMap은 다른 metric들의 성능에 부정적인 영향을 미치지 않는다.

(mint route란 무선 센서 네트워크에서 사용하는 네트워크 계층 프로토콜로써, route selection을 위해 link quality에 기반한 새로운 metric을 개발하는 네트워크 계층 접근 방식이다.)

또한 Singh와 Kaur가 작성한 Machine learning based link cost estimation for routing optimization in wireless sensor networks에 따르면 C4.5 Decision Tree가 wireless sensor network에서 routing 최적화를 위한 link cost 측정에 가장 적합한 알고리즘이라고 한다.

따라서, 우리는 regression을 이용할 것이며, link의 performance metric을 SL을 통해 예측할 것이다. 이 때, 이 metric은 PBP, EED를 포함하고 있다.

 

2.2 Reinforcement learning(RL)-based routing for wireless networks

RL은 주어진 state에 대해 선택한 action에 따라 environment에서 reward를 받고, 그 reward에 따라 action을 수정하는 방식의 학습법이다.

(강화 학습에 대한 자세한 설명 : https://ko.wikipedia.org/wiki/%EA%B0%95%ED%99%94_%ED%95%99%EC%8A%B5)

강화 학습 - 위키백과, 우리 모두의 백과사전

Wireless Mash Network(WMN)에서, WR은 routing table의 update를 위해 이웃 WR들과 Hello packet을 주고받으며 상호작용한다. 매 WR 상호작용시마다, WR은 목적지까지의 path cost의 reward를 얻는다.

이러한 학습 과정에서, WR은 best reward를 제공한 neighbor를 선택하여 routing table을 업데이트 한다.

총 reward 구조는 state(st)에서 action(at)를 하고 난 후라고 가정 시 Q(st,at)로 나타낼 수 있으며, Q-Learning algorithm에 의해 정의된다.

(Q-Learning algorithm : RL 기법 알고리즘 중 하나이다. 각 state와 action에 대한 Q-value는 해당 state에서 해당 action을 선택시 얻을 수 있는 예상 보상이다. agent가 action을 선택하면 environment로부터 reward를 받고, Q-value를 업데이트하게 된다. 이 업데이트는 현재의 Q-value에 새로운 경험에 기반하여 이루어진다.)

업데이트

여기서 α와 γ는 각각 Learning rate와 discount factor이다.(α,γ ∈ [0,1]).

RL-based routing에서 Q-value(1)는 routing algorithm의 목표로 주로 활용된다.

WMN에서는 PBP가 목적 node로 가기 위한 다음 홉을 결정하는데 사용되는 reward로써 고려된다.Syed가 작성한 논문 Route selection for multi hop cognitive radio networks using reinforcement learning: An experimental study, IEEE Access에 따르면 multihop radio network에서 성능을 향상시키기 위해 RL에 기반한 두 가지 경로 선택 방안이 있다.(traditional RL, RL-based with average Q-value)두 가지 방법 모두 bottleneck link에서 사용 가능한 channel time을 Q-learning의 reward로 사용한다. 이 metric은 한 쌍의 source-destination node 사이의 경로를 선택하는데 사용된다. 이러한 학습 방식의 성능을 평가하기 위한 방법은, Reinforcement Learning을 사용하여 경로 선택을 모델링한 testbed를 기존의 경로 선택 방법인 "Highest channel(HC)"와 비교하여 평가하는 것이다.해당 논문의 결과로써 이 2가지 RL 기반 경로 선택 방법은  packet delivery ratio(PDR), throughput, number of route breakages에서 HC approach를 능가하는 것을 알 수 있다.

 

이것 외에도 해당 논문에는 다양한 RL 적용 사례에 대해 다루며 결론적으로 WMN에서 routing protocol에 RL이 효과적으로 사용될 수 있다는 것을 설명한다. RL based routing algorithm들은 높은 효율성을 보이므로, SDWN에서 intelligent routing algorithm을 위해 RL을 사용한다.(Intelligent Routing based on Software-defined network and Machine Learning)이 방법에는 기존 방법들과 3가지의 차이점이 존재한다.

 

1. route to destination을 찾기 위해 SL과 RL을 결합하였다. SL은 각 hop의 PBP와 EED를 예측하기 위해 사용된다. RL은 objective와 routing constraints를 정의하기 위해 사용된다.

 

2. Q-learning algorithm의 learning rate 계수를 지속적으로 변경하여 SDWN에서 EED와 signal-to-noise ratio(SNR)의 constraint를 정의한다.

 

3. source에서 destination으로 이동하는 route의 PBP로 reward function을 구성하였다. 이를 통해 네트워크에서 BPB를 줄일 수 있다.

 

여기까지 본 논문과 관련된 내용들의 설명이었다.다음 글부터는 IRSML 알고리즘에 대해 다룬다.

 

3줄 요약1. SL은 optimal routing 알고리즘에서 link quality를 예측하는데 사용한다. 이는 Mintroute 프로토콜보다 high data rate에서 효과적인 방법이다.2. RL은 WMN에서 routing protocol에 효과적으로 사용될 수 있다. 기존의 경로 선택 방법인 HC와 비교했을 때 PDR, throughput, number of route breakages에서 장점을 보인다.3. 해당 논문에서는 SL과 RL을 결합하여 route to destination을 찾기 위해 알고리즘을 제안했다. SL은 각 hop의 PBP와 EED를 예측하기 위해, RL은 objective와 routing constraints를 정의하기 위해 사용한다.