* 본 글은 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)
3.2 Route discovery based on RL and SL
3.1. 에서는 SL을 활용하여 PBP와 EED를 예측해내는 Regression model을 만들었다.
이번 섹션에서는 source node에서 destination node까지의 각 route에서 PBP를 최소화시키기 위해 RL 방법을 적용하는 것에 대해 알아볼 것이다. 이와 동시에, QoT와 EED는 항상 보장되어야 한다.
routing algorithm에 사용되는 state의 정보는 Rsd 상의 BPB,EED 및 SNR을 포함한다.
BPB는 routing algorithm의 objective function에 사용되며, EED와 SNR은 routing constraint를 정의하는데 사용된다.
3.2.1 Construct routing objective function using Q-learning
IRSML의 route selection의 목표는 Rsd의 PBP를 최소화하는 것이다.
이전에 정의한 route 상의 PBP에 기반하여, 업데이트 된 route 상의 PBP인 Q-value를 얻기 위하여 RL method의 basic equation을 수정한다.
Q(s,a,d)는 Rsd 상의 PBP이며 source to node a to destination 을 의미한다.
R(s,a)는 source에서 node a로 이동할 때 받는 reward로써, s to a hop 상의 PBP이다.
즉, R(s,a)는 앞서 서술한 Regression model로 예측된 Bh(s,a)와 같다.
α 와 γ는 각각 learning rate, discount factor 이다.
3.2.2 Determine routing constraints using Q-learning
QoS를 보장하기 위해, 찾아낸 route는 항상 EED와 QoT constraints를 만족해야만 한다.
IRSML 알고리즘 상에서, 이러한 constraint들은 정의된 objective function의 learning rate α를 바꾸어줌으로써 정의된다.
Update EED:
매 Q-value가 업데이트 될 때마다, EED 역시 다음을 따라 업데이트 된다.
Tr(s,a,d)는 s->a->d 의 EED, Th(s,a)는 s->a 의 EED, Tr(a,b',d)는 a->b'->d 의 EED 이다.
각각은 이전에 정의해둔 EED 정의를 따른다. (3.1.2 EED 참조)
b'는 다음의 조건을 만족하는 node a의 이웃 노드이다.
Update QoT:
QoT는 각 route의 destination node에서 SNR로 정의된다. 그런데 SDWN은 multihop wireless network이다.
따라서 각 route의 destination node에서 SNR은 중간 노드들의 relay type에 의존하게 된다.
즉, amplify and forward(AF) 또는 decode and forward(DF)에 의해 정의된다.
(data relay method)
βr(s,d)과 βh(i,j)들은 route Rsd, hop hij의 SNR이다. 학습을 하는 동안, SNR은 Q-value 업데이트 시마다 지속적으로 업데이트 된다. 이를 통해 우리는 SNR 업데이트 방정식을 다음과 같이 정의 가능하다.
알고리즘을 보면 각 node i,j에 대해 Q-value(i,j,d)는 max로 초기화하고, SNR, EED는 0으로 초기화한다.
이때 만약 j가 i의 이웃이었다면 Bh(i,j)를 다음과 같은 regression model로 예측한다. 그 후 예측한 PBP를 Reward(i,j)에도 저장해준다. 해당 작업은 network 내에 있는 모든 node들에 대해 실행된다.
그 후 각각 d의 이웃 node k에 대해 Q-value, SNR, EED를 해당 노드 간의 PBP, SNR, EED로 초기화 해준다.
다음에는 learning이 시작되는데, 파라미터로 주어진 learning의 횟수만큼 source, node a를 network에 node 중에서 랜덤하게 뽑는다.
이 후 minQ를 max로 선언하고 set of nodes in network 중 선정된 a가 아닌 다른 노드들 각각에 대해 minQ 값을 검색한다.
( if minQ > Q(a,b,d), then update. )
그 후에 min node들을 저장할 공간 Nmin을 만들고 Q(a,b,d)가 minQ였던 node들을 Nmin에 저장한다.
이를 통해
이 조건을 만족하는 b'는 Nmin 중 랜덤하게 선정되고, SNR, EED를 각각 update rule로 update 한다.
그 후에 SNR(s,a,d)가 요구된 QoT 만큼을 충족하고 EED가 limit보다 빠를 때, learning rate를 1로 적용하여 update한다.
최종적으로 Q(s,a,d)를 Q-value equation으로 update하며 학습 싸이클을 마치게 된다.
IRSML 알고리즘에서 Q-value matrix는 각 node에서 destination까지 route의 PBP를 저장하며 learning rate를 통해 QoT, EED 제약조건에 충족할 경우에만 학습을 한다. ALGORITHM 1에 따라 Q-value matrix를 update한 후, 최소 PBP를 가지는 Rsd는 ALGORITHM 2에 따라 flow switch table을 update하기 위해 결정된다.
해당 Algorithm들은 전부 SDN Controller 위에서 돌아간다.
next를 source. 즉, 출발지로 정의하고 알고리즘을 시작한다. 그 후 destination에 도착할 때까지 현재 노드에서 minQ를 가지는 b를 Q-value matrix를 통해 찾아내고, 해당 b를 chosenNext로 정한다. 그렇게 찾아낸 chosnNext로 flowSwitchTable을 수행한 이후, next를 chosenNext로 바꾸어줌으로써 다음 node로 이동한다.
'논문' 카테고리의 다른 글
| SL, RL을 기반으로 한 라우팅 알고리즘 - 5(Conclusions) (0) | 2024.01.02 |
|---|---|
| SL, RL을 기반으로 한 라우팅 알고리즘 - 4 (0) | 2024.01.02 |
| SL, RL을 기반으로 한 라우팅 알고리즘 - 3.1 (0) | 2023.12.29 |
| SL, RL을 기반으로 한 라우팅 알고리즘 - 2 (0) | 2023.12.28 |
| SL, RL을 기반으로 한 라우팅 알고리즘 - 1 (0) | 2023.12.27 |