2.3.1 거래 개시를 위한 최초 패킷의 발송

최초 패킷 발송은 전력을 공급(판매) 혹은 수신(구매)하려고 하는 전력 라우터로부터 시작된다. 전력을 공급하려는 라우터는 공급 패킷($S$)을 발송하며, 전력을 공급받기를 원하는 라우터는 수요 패킷($D$)을 발송한다. 이 패킷의 값은 공급 비용($P_{G}$) 혹은 구매 가격($P_{D}$)을 포함하며 다음과 같이 표현된다.

위 식에서 $i$는 패킷을 최초 발송한 라우터의 식별 번호를 의미한다. 전력 거래를 원하는 라우터는 이 패킷을 인접한 모든 전력 라우터로 브로드캐스팅한다. 수요 패킷($D$)에 대하여도 동일한 방법이 적용된다.

2.3.2 수신한 패킷의 평가

전력 라우터 $i$가 전력 거래 요청을 개시하여 패킷이 경로상에 있는 전력 라우터 $j$에 의해 중계되어 전력 라우터 $k$가 수신하였다고 하면, 그 패킷은 다음과 같이 표현된다.

이 경우 전력 라우터 $k$는 수신한 패킷 $S[i][j]$의 중계 여부를 결정하기 위하여 동일한 전력라우터 $i$에서 최초 발송되어 다른 경로를 통하여 전달되어 수신된 패킷들과 비교하여 이들 패킷의 비용보다 작을 경우 중계하고, 이보다 클 경우 폐기한다.

즉, 전력 라우터 $k$는 다음 조건을 만족할 경우 중계한다.

식(3)에서 $k_{\min}$은 전력 라우터 $i$에서 최초 발송하여 수신한 패킷 중 최적 비용으로 판별된 중계 전력 라우터의 번호를 의미한다.

2.3.3 수신한 패킷의 갱신 및 중계

전력 라우터 $k$는 전력 라우터 $j$를 거쳐 수신한 패킷 $S[i][j]$을 중계하기로 결정한 경우, 수신한 패킷에 자신의 중계 비용($P_{R}[k]$)을 합하여 새로운 패킷을 작성한다. 이때 작성된 패킷은 수신한 패킷에 자신의 식별 번호를 덧붙여 $S[i][j][k]$로 표시하며, 식(4)와 같이 나타낼 수 있다.

전력 라우터 $k$는 $S[i][j]$를 송신한 전력 라우터 $j$를 제외한 다른 모든 라우터에 식(4)의 패킷을 브로드캐스팅하며, 이를 플러딩(flooding)이라고 한다.

라우팅 패킷을 수신할 때마다 라우터는 패킷의 전달 여부를 판단하여 최적의 값을 가지는 패킷만 중계하므로 네트워크에 패킷이 반복적으로 중계되어 패킷의 홍수를 이루게 되는 플러딩의 단점을 방지할 수 있다.

2.3.4 최적 경로의 식별

전력 라우터 $k$는 동일한 전력 라우터 $i$가 최초 발송한 패킷 중 최소의 값을 가지는 것으로 판단된 패킷을 $S[i][j][k]$라고 하면, 이로부터 식(5)와 같은 최적 경로를 추출할 수 있다. 식(5)는 전력 라우터 $i$로부터 라우터 $j$를 거쳐서 최종적으로 라우터 $k$로 전력을 중계하는 것을 의미한다.

3.1.1 패킷의 중계

제안한 방식을 설명하기 위해 Fig. 5와 같은 라우터 6개로 구성된 네트워크를 가정한다. 각 전력 라우터는 식별 번호로 구분한다. 전력 라우터 1이 전력 공급을 위해 패킷의 전송을 개시한다고 가정한다. 그리고 편의상 모든 라우터의 중계 비용은 동일하다고 가정한다.

전력 라우터 1은 최초 작성된 패킷 $S[1]$을 연결된 모든 인접 라우터에 브로드캐스팅한다. 즉, 전력 라우터 1은 이와 연결된 인접 전력 라우터 2, 3, 4로 패킷 $S[1]$을 전송한다. 식(6)에서 $P_{G}[1]$은 전력 라우터 1의 공급 비용을 의미한다.

각 라우터는 패킷을 수신한 경우 수신한 패킷을 평가하여 중계할 패킷과 폐기할 패킷을 구분하여 중계할 패킷을 인접 라우터로 중계하는 작용을 한다. 다음에 패킷이 중계되는 각 스텝에서의 각 전력 라우터의 동작을 기술한다.

[step 1]

패킷 $S[1]$을 수신한 전력 라우터 2, 3, 4는 기존의 동일한 전력 라우터로부터 수신한 패킷이 없으므로 패킷의 평가 단계에서 패킷 $S[1]$을 중계하는 것으로 결정한다.

이어 전력 라우터 2, 3, 4는 각각 수신한 패킷 $S[1]$으로부터 자신의 중계 비용을 반영한 패킷 $S[1][2]$, $S[1][3]$, $S[1][4]$를 제작한다. 각 패킷은 다음과 같다. 식에서 $P_{R}[k]$은 각 전력 라우터의 중계 비용을 의미한다.

각 전력 라우터는 작성한 패킷을 인접 라우터에 플러딩한다.

[step 2]

이 스텝에서는 전력 라우터 2, 3, 4가 발송한 패킷 $S[1][2]$, $S[1][3]$, $S[1][4]$가 각각 전력 라우터 2, 3, 4, 5, 6으로 중계되어 수신된 상태이다. 각 전력 라우터에 수신된 패킷을 이전 스텝에서 수신한 패킷과 함께 표시하면 다음과 같이 된다.

라우터 2: $S[1]$, $S[1][4]$

라우터 3: $S[1]$, $S[1][4]$

라우터 4: $S[1]$, $S[1][2]$, $S[1][3]$

라우터 5: $S[1][3]$

라우터 6: $S[1][4]$

(1) 라우터 2와 3에서의 패킷 평가 및 중계

Fig. 5에서 보듯이 라우터 2와 3은 동일한 패킷 $S[1][4]$를 라우터 4로부터 수신한다. 라우터 2와 3은 기존에 저장되어 있는 기존 패킷 $S[1]$과 비교하여 식(10)을 얻고, 패킷 $S[1][4]$는 더 이상 전달하지 않고 폐기한다.

(2) 라우터 4에서의 패킷 평가 및 중계

라우터 4는 저장되어 있는 패킷 $S[1]$과 새로 수신한 패킷 $S[1][2]$, $S[1][3]$을 비교하여 다음 결과를 얻는다.

식(11)의 평가 결과로부터 라우터 4는 후 새로 수신한 패킷들을 전달하지 않고 폐기한다.

(3) 라우터 5, 6에서의 패킷 평가 및 중계

라우터 5, 6은 전력 라우터 1로부터 수신한 패킷이 아직 없으므로 각각 $S[1][3]$과 $S[1][4]$을 중계하기로 결정한다. 동일한 방법으로 다음 패킷을 작성한 후 인접 라우터로 플러딩한다. 식(12)와 (13)은 각각 라우터 5와 6에서 작성된 패킷을 나타낸다.

[step 3]

이 단계에서 전력 라우터 2, 3, 4는 추가로 패킷을 수신한 것이 없으며, 전력 라우터 5와 6만 수신한 패킷을 평가한다. 이 단계에서의 전력 라우터 5와 6에 저장된 패킷은 다음과 같다.

라우터 5: $S[1][3],\: S[1][4][6]$

라우터 6: $S[1][4],\: S[1][3][5]$

(1) 라우터 5에서의 패킷 평가 및 중계

라우터 5에서는 모든 라우터의 중계 비용이 동일하다고 가정하였으므로 식(8)과 식(13)으로부터 다음 관계를 알 수 있다. 따라서 수신한 패킷 $S[1][4][6]$은 중계하기 않고 폐기한다.

(2) 라우터 6에서의 패킷 평가 및 중계

라우터 6에서는 식(9)와 식(12)로부터 다음 관계를 알 수 있다. 따라서 패킷 $S[1][3][5]$는 중계하지 않고 패기한다.

이로서 모든 전력 라우터는 추가로 수신한 패킷이 없으며, 전력 라우터 1이 발송한 패킷은 모든 전력 라우터로 중계되었다. 즉, 샘플 네트워크에서 3번의 패킷 중계로 모든 라우터에 패킷 전달이 완료된 것을 알 수 있다.

3.1.2 거래 정보 및 최적 경로 확립

Fig. 6은 패킷 전달이 완료된 후의 각 라우터의 패킷의 저장 상태를 보여준다.

Fig. 6에서 각 라우터가 수신한 모든 패킷을 나타내었다. Fig. 6에서 ○로 표시된 패킷은 중계된 패킷이고 ×로 표시된 패킷은 중계되지 않고 폐기된 패킷을 나타낸다.

라우팅 패킷을 전달받은 각 라우터는 전력을 공급하려고 하는 라우터 1과 자신 사이의 최적 경로와 비용을 알게 된다.

Table 1에 전력 라우터 1이 공급 패킷을 발송하였을 때 네트워크에 연결된 모든 라우터로의 최저 비용 중계 경로와 중계 비용에 관한 관련 정보를 나타내었다.

Table 1에서 라우터 2, 3, 4는 중간에 전력 중계에 참여하는 전력 라우터가 없으므로 중계 비용이 발생하지 않는다. 전력 라우터 5와 6은 중간에 하나의 전력 라우터가 중계에 참여하며, 이들의 중계 비용은 Table 1에 나타낸 것과 같다.

3.1.3 거래의 개시

전력 거래를 원하는 전력 라우터는 반응 패킷을 발송하여 전력 거래 요청을 하게 되며, 반응 패킷을 수신한 공급 라우터는 반응 패킷 중 하나를 선택하여 확인 패킷을 보냄으로써 거래가 시작될 수 있는 요건이 만족된다.