IRSML 논문 구현 아이디어(알고리즘)

* 본 블로그에 작성한 논문 IRSML을 읽고 어떻게 직접 시뮬레이션을 구현해볼지 아이디어들을 작성해놓은 글입니다.

 

---

! 중요한 개념

SDWN 구조

 

PBP function

 

Regression method : C4.5 Decision Tree

 

 

Simulation Parameters

 

 

EED

 

* erlang 등 다양한 정보통신학 용어(http://www.ktword.co.kr/test/view/view.php?m_temp1=519)

ㅇ 트래픽 밀도의 단위 및 차원
     - 차원 : 무차원
     - 단위 
        . [Erlang] : 1회선을 1시간 동안 점유한 트래픽량

 

 

RL function with Q-value

 

EED Update Rule

b' constraint

 

SNR(QoT) Update Rule

---

 

구현 아이디어

1. Supervised learning Phase

SL

본 논문에서는 Offline Training, 즉 배치 기법을 활용하였다.

해당 방법에서는 사전에 준비된 Data set을 Training, test, validation(optional) 으로 나누어 Training data set으로 훈련을 시키고, test data set으로 검증을 하는 것이 요구된다.

결국 Data set을 어디서 구하냐가 문제인데, 해당 논문에서는 OMNeT++과 INET framework 2.0을 이용해 TABLE 1의 상황을 가정하고 시뮬레이션 하고, 그 데이터를 Training data set으로 사용한 것 같다.

(여기서 Simulation parameter들을 수정하는 것으로 Training data set을 다양하게 만들어볼 수 있을 것 같은데, 주어진 조건 중 Speed of MH가 0~20 m/s인게 조금 아쉽다. 차량을 주행한다면 20 m/s 이상으로 올라가는 경우가 많이 생기는데 그 이상의 속도에서는 부정적인 결과가 나와서 제외한 것일까?)

 

하여 나도 우선 Data들은 시뮬레이터들을 통해 생성되었다고 여기고 구현을 이어나가겠다.

우선 떠오르는 대로 임시 pseudo code를 작성했다.

 

Z
//Simulation Network

F(ρ,L)
/*After Simulation, determin regression function of PBP(i,j) with variables of the trafficload, 
QueueLength*/

Q, βr, Tr = n*n*n size tensor
// (source) * (inter) * (destination)

Bh, R = n*n matrix
// (source)*(destination)

model 
//non-linear Regression model for predict PBP (Use F(ρ,L))

for(i= 1~N, i++) do
   for(j=1~N, j++) do
   //N은 network 상의 node의 갯수
	if(j == i) then continue
        Q(i,j,d) = inf.
        βr(i,j,d) = 0
        Tr(i,j,d) = 0
        if(Z.getNode(j).isNeighbor(i)) then
          Bh(i,j) = model.(Z.getρ(i,j), Z.getL(i,j)) //Predict PBP(i,j)
          R(i,j) = Bh(i,j)
        else
          R(i,j) = inf.
        end if
    end for
end for
// Q-val tensor는 max 값으로 초기화
// SNR, EED tensor는 0으로 전부 초기화.
// PBP matrix는 i와 j가 이웃 노드일 때 predicted PBP로 init.
// Reward matrix는 i,j가 이웃 노드일 때 PBP 값. else inf.

for(d=1~N, d++) do
	for(k=1~N, k++) do
		if(Z.getNode(k).isNeghbor(d)) then
			Q(k,d,d) = Z.getPBP(k,d)
			βr(k,d,d) = Z.getSNR(k,d)
			Tr(k,d,d) = Z.getEED(k,d)
		end if
         //k,d는 이웃노드이기 때문에 구하기 가능.
    end for
end for
// 이웃노드 간의 값을 실제로 측정된 초기 값으로 설정(이 후 RL을 통한 예측 시작)

 

해당 Supervise Phase가 끝나게 되면, Q-val. tensor는 이웃한 k,d에 대해 Q(k,d,d)의 값들만 실제 측정된 route PBP 값으로 초기화되고, 나머지는 전부 max 값으로 초기화 되며, SNR, EED 역시 이웃한 k,d 외 값들은 0으로 초기화된다.

 

i to j predicted PBP를 저장하고 있는 Br matrix는 이웃한 i,j에 대해서만 값을 지니며 나머지는 Max 값으로 초기화 되어있다.( Reward matrix R 역시 마찬가지다. )

 

이렇게 SL을 통해 초기 값들과 초기 예측 값들을 이웃한 노드들에 대해 기록한 후, 학습을 시작한다.

이 때, 각 regression model은 MATLAB Fitting tool을 활용하였다고 가정하였다.

또한 Regression model의 constant * Trafficload(Queue Length)는 정규화되었다고 가정했다.

 

2. Reinforcement Learning Phase

RL

 

! RL의 목표

만약 모든 Q(a,b,c) tensor의 값을 학습하여 구성해둔다면, Q(s,a,d) route의 Optimal Route를 찾기 위해서는

단순히 node d에 도착할 때까지 Q(s,a,b) 값이 가장 작은 b를 선정해서 이동 -> Q(a,b,c) 값이 가장 작은 c를 선정해서 이동... 을 반복하면 될 것이다.

for( n = 1~Δ, n++ ) do
	s = random(1,N);
    a = random(1,N);
    while(true) do 
    	if(s==a) then 
        	a = random(1,N);
            continue;
        end if
    	break;
    end while
    minQ = inf.;
    for( i = 1~N, i++ ) do
    //N은 network 상의 node 갯수
        if((i == s) || (i == a)) then
        	continue;
        end if
        if(minQ > Q(a,b,d)) then
        	minQ = Q(a,b,d)
        end if
    end for
    
    Nmin = new Set();
    for( i = 1~N; i++ ) do
    	if((i == s) || (i == a)) then
        	continue;
        end if
        if(Q(a,i,d) == minQ) then
        	Nmin.add(i);
        end if
    end for
    
    b = Nmin.get(random(1,L)); 
    //L = Queue Length
    βr(s,a,d) = SNRupdateFunction(s,d);
    Tr(s,a,d) = EEDupdateFunction(s,a,b,d);
    if((βr(s,a,d) < reqSNR) || (Tr(s,a,d) > limEED)) then
   		α = 0;
    else
    	α = 1;
    end if
    Q(s,a,d) = QvalupdateFunction(s,a,d);
end for

(자세한 구현 과정은 모각코 첫 번째 모임 개인 계획, 활동과정 및 결과 (tistory.com) )

 

이 RL phase까지 전부 완료되게 되면 Optimal Route를 찾기 위한 Q-val tensor init이 끝나게 되며, 이 tensor에 해당하는 값을 greedy approach로 destination에 도착할 때까지 고르면 Minimized PBP(Q-val) Route의 선정이 가능하게 된다.

따라서 다음은 CDN Controller의 Flow swtich table update Algorithm을 구현해야한다.

 

3. Flow switch Table update Algorithm

 

route R(s,d)를 찾아야한다고 가정하자.

알고리즘을 간단히 요약하면 s부터 시작해서 SL&RL 알고리즘의 결과물로 도출된 optimal Q-value tensor에서 greedy approach로 최소 Q-value를 가지는 다음 노드를 선정, flowSwitchTable에 업데이트를 반복해 d에 도달하는 알고리즘이다.

// Routing을 위한 source 's'와 destination 'd' 주어졌다고 가정.
// N은 network 내부의 node 갯수

next = s;
while(next != d) do
    chosenNext = null;
    minQ = inf.
    for(b=0~N; b++) do
    	 if(minQ > Q(next,b,d)) then
         	minQ = Q(next,b,d);
            chosenNext = b;
         end if
    end for
    //이 지점에서 best node b Q-val map에서 검색 완료
    flowSwitchTable(next,d) = chosenNext;
    //next에서 d로 가기위한 best approach는 'b'이다.
    next = chosenNext;
end while