효율적인 드론봇 네트워크 구성을 위한 Multiplexer 할당모형에 관한 연구

<인덱스>

k : 고리(ring)의 인덱스,

e ∈ E: 호(edge)의 집합,

i, j ∈ V: 마디(node)의 집합.

<파라미터>

C (> 0) : 고리의 용량,

d_e (> 0) : 호 e(∈E)의 수요

(communication demand).

<결정변수>

$x_i^k=\left\{\begin{array}{c}1,\text{ 고리 }k\text{의 multiplexer가 마디 }i\text{ 에 설치,}\\ 0,\text{ 고리 }k\text{의 multiplexer가 마디 }i\text{ 에 미설치}.\end{array}\right.$

$y_e^k=\left\{\begin{array}{c}1,\text{ 호 }e\text{의 수요 }{d}_e\text{ 가 고리 }k\text{ 에 할당,}\\ 0,\text{ 호 }e\text{의 수요 }{d}_e\text{ 가 고리 }k\text{ 에 미할당}.\end{array}\right.$

<모형화>

고리(ring)의 인덱스는 k로 표기하되 총 n 개의 고리가 존재할 수 있음을 가정한다. 집합 E 와 V 는 주어진 네트워크  G= (V, E)의 무향호와 마디의 집합을 각각 의미하며, e 는 호의 집합 E 에 속하는 호, i, j 는 마디의 집합 V 에 속하는 마디를의 인덱스를 표현한다. 각 고리의 용량은 균일한(identical) 값인 C, 각 호의 수요를 d_e 로 표기한다. 이 네트워크 최적화 문제의 결정변수는 마디 i 위치에 고리 k에 대한 multiplexer 설치여부를 표현하는 $x_i^k$ 이며, 마디 i, j 에 고리 k에 대한 multiplexer가 설치되었을 때 (즉, $x_i^k=x_j^k=1$), 마디 i, j 를 잇는 호 e = (i, j)의 수요  d_e의 충족여부 표현하는 $y_e^k$ 가 이진결정변수(binary decision variable)로 설정된다.

수학적 모형의 제약식 (2)는 모든 호 e(∈E) 가 반드시 하나의 고리(ring)에 할당되어야 함을 나타내며, 제약식 (3)에 각 고리에 할당된 호의 수요 ${\displaystyle \sum _{e\in E}{d}_e{y}_e^k}$ 는 고리의 용량(C)를 초과하지 않아야 한다. 또한, 제약식 (4)-(5)는 호 e = (i,j)의 수요 d_e 가 고리 k에 할당$\left(y_e^k=1\right)$되기 위해서는 해당 multiplexer가 마디 i, j 에 설치되어야 함$\left(x_i^k=x_j^k=1\right)$을 표현한다. 마지막으로 제약식 (6)-(7)은 결정변수$x_i^k,y_e^k$는 0 혹은 1의 값을 갖는 이진변수로 제약된다. 이 모든 제약조건 (2)-(7)을 만족하는 가운데, 목적함수 (1)에 의해 설치된 multiplexer의 수의 합이 최소화되는 할당안을 도출한다.

이외에도, 문제 상황에 따라 목적함수와 제약조건을 일부 수정하여 복잡한 형태의 MAP를 정의할 수도 있다. 예를 들어, 두 종류의 multiplexer가 활용될 수 있는 상황이라면, 몇몇 제약식을 기본모형에 추가해야 한다. 예를 들어, multiplexer Type 1은 용량이 C₁이며 각 multiplexer의 비용은 α, multiplexer Type 2는 용량이 C₂(>C₁)이며 multiplexer의 비용은 β일 때의 상황을 고려해보자. 그렇다면, 기본모형에 다음의 결정변수 $Z_i^k$와 $w_i^k$를 추가하고, 목적함수는 (1)′로 수정하고, 제약식 (8)-(10)을 추가한 응용모형을 활용할 수 있다.

<결정변수(추가)>

$\begin{array}{c}{z}_i^k\text{: 고리 }k\text{의 마디 }i\text{ 에 설치되는 용량 }{C}_1\text{의 슬롯 수},\\ w_i^k:\text{고리 }k\text{의 마디 }i\text{ 에 설치되는 용량 }{C}_2\text{의 슬롯 수}.\end{array}$

<모형화(수정)>

본 논문에서 제안하는 Greedy 휴리스틱 방법은 최적해는 아닐지라도 기존 해에서 순간 가장 효과적인 방향으로 해를 개선해나가는 휴리스틱 방법론 중 하나이다. 본 절에서 제시하는 greedy 휴리스틱은 임의로 선택된 초기해에서 추가 가능한 가장 큰 수요를 가진 인접한 호를 추가해나가는 방식이다. 본 논문의 greedy 휴리스틱 해법(Greedy Heuristic Algorithm, GHA)의 세부적인 절차는 다음과 같다.

Step 0. k = 1.

Step 1. (Choosing initial edge) Start with edge e which has positive demand. If there exist multiple positive edges, choose the smallest index among them.

Step 2. Add e to the ring k.

Step 3. (Finding and adding an adjacent edge) Find an addible edge e with the largest demand among edges which are adjacent edges in ring k. Add edge e in the ring k and set d_e = 0. Repeat step 3 until there is no edge that can be added to ring k.

Step 4. k = k + 1 and go to step 1 if there exists an edge of positive demand. Otherwise, stop.

위 Greedy 휴리스틱 알고리즘은 각 반복단계(iterations)별로 하나의 고리(ring)에 초기 할당한 호를 기준으로 인접한 호들을 잔여용량 범위 내에서 새로운 호를 추가하는 방식으로 설계되었다. Step 1은 최초 임의의 호를 하나 선택하는 것으로 시작한다. Step 2에서는 최초 선택한 호를 고리 k에 할당하고, Step 3에서는 최초 할당한 호의 인접 호들 중에서 d_e 의 값이 가장 큰 호부터 순차적으로 고리 k에 추가한다. 더 이상 k = 1 인 고리에 호를 추가할 수 없게 되면(즉, 고리의 잔여용량이 부족하면), 현재까지 할당한 호들의 수요 d_e를 0의 값으로 설정하고, 다음 고리 k = 2 로 넘어간다. 이때, k = 1 일 때와 동일하게 Steps 1-3을 반복 적용하며, 이 반복단계(k = 2)에서 다시 고리의 용량 범위에서 호들이 할당될 때까지 반복한다. 해당 알고리즘의 절차를 상세히 보이기 위해, 그림 6의 네트워크 예제에 GHA를 적용한 결과를 표 1에 각 반복단계별로 순차적으로 제시하였다.

표 1에서 첫 번째 반복단계 (k = 1)에서 초기 선택된 호는 임의의 선택한 호 (1,2)이며, 이 호와 인접한(adjacent) 호 중에서 고리의 잔여용량(C = 256)을 만족하는 가장 큰 용량을 가진 호들인 (1,5)-(1,3)-(2,3)를 순차적으로 첫 번째 고리(Ring 1)에 할당한다. 이때, 마디 1, 2, 3, 4에 각 1개씩 총 4개의 multiplexer가 필요하다. 이후 두 번째 반복단계(k = 2)에서 할당되지 않은 호들 중에서 호(1,4)를 임의로 선택하고, 이어서 다시 순차적으로 호(3,4)-(4,5)-(2,5)를 두 번째 고리(Ring 2)에 추가한다. 마지막 반복단계(k = 3)에서는 잔존하는 유일한 호 (3,5)를 세 번째 고리에 할당하고, 더 이상 남아있는 호가 없으므로 알고리즘을 종료한다. 최종, 그림 6의 네트워크 예제는 모든 호들의 수요를 충족하기 위해서는 고리가 총 3개 요구되며, 각 고리에 호들을 모두 할당하기 위해서는 총 11개(=4+5+2)의 multiplexer가 요구된다는 것을 최종 결과로 얻을 수 있다.

표 1의 결과를 바탕으로, 최적해를 도출해내는 Branch and Cut 알고리즘과 본 논문에서 제시하는 휴리스틱 알고리즘을 각각 적용하여 목적함수 값과 계산시간을 비교하였다. (본 3절에서 제시하는 모든 실험은 Intel Core™ i5-7200U CPU @ 2.50GHz, RAM 8.00GB PC 환경에서 산출된 결과이다.)

본 논문에서 제안하는 휴리스틱 방법의 계산효율성과 정확도를 분석하기 위해, 정확한 최적해를 도출할 수 있는 Branch & Cut(B&C) 기법을 비교군으로 활용하였다. 표 2는 그림 1의 네트워크 예제를 B&C 기법과 본 논문에서 제안한 GHA를 적용하여 비교한 결과이다. B&C 기법은 MATLAB을 활용하여 스크립트를 작성하였으며, 최적해를 도출하기 위해 GROBI 8.01을 활용하였다. 동일한 예제에 대한 목적함수 값은 각각 10과 11이 도출되였고, GHA를 통해 정확한 최적해를 도출하지는 못하였으나 비교적 근사한 값을 얻었다. 계산시간 면에서는 B&C 기법을 통해 0.7309초, GHA는 0.0341초 만에 결과를 얻음으로써 약 20배 가량 빠른 속도로 보였다.

본 논문에서 제안하는 GHA의 효용성을 확인하기 위해 추가적인 실험을 진행하였으며, 이때 활용한 파라미터의 값은 표 3과 같다. 고리의 용량(C)은 256이며, 각 호의 수요 d_e 는 0과 150의 사이 임의의 정수로 선택하였다. 각 문제 예제 별 마디의 수는 4, 5, 6으로 하되, 복잡한 문제 유형 생성을 위해 모든 마디 쌍을 연결하는 호가 존재하는 네트워크(complete network)를 고려하였다.

표 4에서 보듯이, 각 마디의 수(4, 5, 6)에 대한 문제 예제는 각 10개씩 생성하였으며, 마디의 개수가 4개인 문제 예에서는 최적 목적함수 값의 차이는 +6.85 %로서, GHA가 B&C 기법에 비해 약 6 % 높은 수준의 목적함수 값을 도출하였다. 반면, 계산속도는 B&C 기법에 비해 약 12 배 가량 빨랐다. 마디의 수가 5, 6 개인 문제 예제의 결과를 통해 마디의 수가 많아질수록, 최적 목적함수 값의 개선 정도가 나빠지긴 하지만 그 차이는 점점 감소함을 확인할 수 있었으며, 6 개 마디 문제예제의 경우, B&C 기법에 비해 5,000 배 이상의 빠른 계산속도를 보여주었다. 기존 연구에서 제안되었던 휴리스틱 알고리즘과의 직접적 성능 비교는 제한되나, Sutter et al.(1998)의 연구에서 7개 노드로 구성된 네트워크에 대한 휴리스틱 알고리즘 적용 결과가 계산 시간은 평균 약 4초 정도가 소요되었다.

보다 면밀한 분석을 위해, 마디의 개수가 6개인 10개 문제예제의 결과를 그림 7과 그림 8을 통해 살펴보자.

그림 7은 10개 문제 예제에 대한 B&C 기법과 GHA의 계산시간(초)의 결과를 보여준다. GHA의 경우, 모든 문제 예제 대해 계산시간 면에서 큰 차이를 보이지 않는다.(GHA의 계산시간을 표현하는 주황색 선은 상당히 평편한 형상을 보인다.) 하지만, B&C 기법의 경우 문제 예제에 따라 계산시간 면에서 상당히 큰 차이를 보임을 알 수 있다. (문제 예제 #1: 약 861초, 문제 예제 #5: 약 2초)

그림 8은 10개 문제 예제에 대한 B&C 기법과 GHA의 목적함수값 결과를 비교한 것이다. GHA의 경우 모든 문제 예제에 대해 B&C 기법 대비 [2,4] 가량 높은 목적함수 값을 도출해주는 것으로 확인하였다.