1. 서 론

웹서비스(Web service)⁽¹⁾는 웹 기술을 기반으로 하여 machine들 간의 inter-operation을 제공하기 위한 소프트웨어 시스템이다. 특히, 최근 소프트웨어 분야에서 주목 받고 있는 서비스 지향 아키텍쳐(Service-Oriented Architecture)의 서비스는 독립적 기능을 가질 수 있는 비즈니스 논리의 기본 단위이다⁽²⁾. 이러한 서비스 지향 아키텍쳐의 가장 보편적인 형태인 웹서비스는 반복활용이 가능하고, 자체 독립적이며, 다른 서비스의 일부로 구성될 수 있다. 서비스의 내부 개발은 서비스의 client에게는 블랙박스처럼 보일 수 있도록, 서비스 공급자는 해당 서비스를 이용할 수 있는 인터페이스(API)를 통해 서비스의 기능을 노출한다. 서비스 지향 아키텍처는 이러한 기능과 인터페이스를 조합하여 하나의 프로세스로 조율할 수 있고, 이렇게 형성된 프로세스는 새로운 기능을 제공하는 서비스가 된다.

웹서비스는 분산 시스템 환경, 웹 환경에서 서버시스템이 다수의 사람/기기 등의 client에게 자신의 기능을 사용할 수 있도록 지원하는 서비스의 형태로 많이 사용되어 왔다. 이 뿐만 아니라, 최근 빠르게 발전하고 있는 사물인터넷(Internet-of-Things, IoT) 관련한 다수의 연구에서도 각각의 사물의 기능을 하나의 웹서비스로서 구현하고 상위 구조에서 이러한 서비스 집합을 관리하는 서비스 지향 아키텍쳐 기반 방식을 사용하고 있다^(3,4).

사용자가 원하는 요구사항을 특정 웹서비스 하나로 완전히 충족시키지 못하는 경우에는, 여러 개의 웹서비스들을 이용하여하여 해당 요구사항을 만족시킬 수 있도록 합성하는 웹서비스 컴포지션(Web Service Composition) 기법⁽¹¹⁾이 매우 유용하게 사용될 수 있다. 특히, 웹서비스를 이용하는 client마다 원하는 요구사항이 무한히 다양할 수 있기 때문에, 그에 맞춰 모든 서비스를 처음부터 끝까지 다 개발한다는 것은 개발의 비용과 효율성 측면에서 매우 어려울 수 있다. 특히 웹 기반의 대규모 서비스나, 컴퓨팅 리소스가 한정적인 다양한 IoT기기들을 많이 사용됨에 따라, 서비스 지향 아키텍쳐 기반의 웹서비스 컴포지션 문제는 그 활용성을 인정받고 있고, 많은 다양한 연구가 진행되고 있다^(5,6).

하지만, 최근 IoT를 포함한 다양한 환경에서는 일시적인 서버 다운, 시스템 과부하, 네트워크 불량 등의 다양한 환경적 변화가 발생한다. 이러한 변화가 발행하면, 웹서비스 컴포지션 문제의 셋팅이 변하게 됨으로, 이미 구해놓은 최적의 솔루션 합성 웹서비스는 더 이상 유효하지 않게 된다. 그렇다고, 일부의 환경 변화 때문에 전체 컴포지션 문제를 처음부터 푼다는 것은 상당한 컴퓨팅 시간의 낭비를 초래할 수 있다. 이런 이유로 본 논문에서는 웹서비스 문제의 변화에 따라, QoS기반 웹서비스 컴포지션 문제를 처음부터 다시 풀지 않고, 이전 풀이에서의 중간 과정을 최대한 활용하여 최적의 솔루션을 효율적으로 찾아낼 수 있는 replanning 알고리즘을 제안한다.

본 논문의 구성은 다음가 같다. 2장에서는 본 논문에서 해결하고자 하는 QoS 기반 웹서비스 컴포지션 문제를 정의하고, 3장에서는 본 논문에서 제안하는 replanning 알고리즘을 설명하며, 4장에서는 본 논문에서 제안하는 replanning 알고리즘의 효율성의 입증하는 실험결과를 보인다. 마지막으로 5장에서는 본 논문의 결론을 제시한다.

그림. 1. 응급 환자 대응 시스템 문제

Fig. 1. Emergency response system

2. QoS 기반 웹서비스 컴포지션

2.2 QoS 기반 웹서비스 컴포지션 문제

본 논문에서 다루고자 하는 QoS 기반 웹서비스 컴포지션 문제는 다음과 같다.

Definition 1. (QoS를 고려한 웹서비스) 각각의 w는 (I, O, Q)로 정의된다. I는 input parameter들의 집합이며, O는 output parameter들의 집합, Q는 quality 기준과 그 값의 pair들로 이루어진 associate 배열이다.

Example 1. 우편번호 검색 웹서비스 w는 ({PostalAddress}, {ZipCode}, {(RespTime: 503msec), (Thrp: 150)}으로 정의될 수 있다. 이 웹서비스는 주소를 입력받아서, 그에 해당하는 우편번호를 생성하며, response time은 503msec, throughput은 150이다.

Definition 2. (웹서비스의 QoS 값) 웹서비스 w = (I, O, Q)가 주어졌을 때, w의 QoS값 QoS(w)는 아래와 값이 weighted sum으로 구할 수 있다. 웹서비스 w는 Definition 1에서 정의한대로 input, output parameter들의 집합 I, O를 가지고 있으며, QoS의 값을 나타내는 집합 Q를 가지고 있다. 또한, Q는 n개의 키(quality 기준) k, k, ..., k를 가지고 있다.

(1)

$Qo S(w)=f_{1}(Q[k_{1}])+ ... +f_{n}(Q[k_{n}])=\sum_{i=1}^{n}f_{i}(Q[k_{i}])$

위의 식 (1)에서 f는 주어진 weight 정책에 따라 결정되는 weight 함수이다.

Definition 3. (합성 웹서비스) 웹서비스 w = (I, O, Q), w= (I, O, Q), ..., w = (I, O, Q)이 주어졌을 때, 이들의 serial composition을 나타내는 합성 웹서비스 w･w･ … ･w는 아래와 같이 (I, O, Q)로 정의된다.

- $I =\bigcup_{i=1}^{n}(I_{i}-(\bigcup_{j=1}^{n-1}O_{j}))$

- $O =\bigcup_{i=1}^{n}O_{i}$

- $ \begin{aligned} Q=&\left(k_{1}: c_{k_{1}}\left(Q_{1}\left[k_{1}\right], Q_{2}\left[k_{1}\right], \ldots, Q_{n}\left[k_{1}\right]\right)\right) \\ &\left(k_{2}: c_{k_{2}}\left(Q_{1}\left[k_{2}\right], Q_{2}\left[k_{2}\right], \ldots, Q_{n}\left[k_{2}\right]\right)\right) \\ & \cdots \\ &\left(k_{\mid K\mid}: c_{k_{\mid K\mid}}\left(Q_{1}\left[k_{\mid K\mid}\right], Q_{2}\left[k_{\mid K\mid}\right], \ldots, Q_{n}\left[k_{\mid K\mid}\right]\right)\right) \end{aligned} $

위의 식에서, K는 $\bigcap_{i=1}^{n}key(Q_{i})$로 가정하며, 각각의 k는 K의 원소이고, $c_{k_{i}}$는 i번째 QoS 기준에 대한 n-ary 합성함수이다. 예를 들어 QoS 기준이 response time이라면, 이에 대한 합성함수 c(t, t, ..., t)은 $\sum_{i=1}^{n}t_{i}$이다.

Definition 4. (QoS 기반 웹서비스 합성 문제) QoS를 고려한 웹서비스 집합 W와 사용자가 원하는 웹서비스 w = (I, O, Q)가 주어졌을 때, W의 원소 웹서비스들을 이용하여 만들 수 있는 합성 웹서비스들 중에서 I에 포함된 정보로서, O에 존재하는 모든 정보들을 만들어 낼 수 있는 합성 웹서비스 중에서 QoS 값이 가장 최적인 합성 웹서비스 w를 합성하는 문제이다.

그림. 2. 변경된 응급 환자 대응 시스템 문제

Fig. 2. Emergency response system changed

3. QoS 기반 웹서비스 컴포지션을 위한 Replanning 알고리즘

이번 장에서는 QoS 기반 웹서비스 컴포지션 문제의 연속적인 변화에 대처하여 최적의 합성 웹서비스를 효율적으로 만들어내는 replanning 알고리즘을 제안한다. 일반적으로는 컴포지션 문제가 변화하여도, 보통의 QoS 기반 웹서비스 컴포지션 알고리즘^(5,7)들 역시 변화된 문제에 대해서 처음부터 문제를 푸는 방식으로 최적의 합성 웹서비스를 찾아낼 수 있다. 하지만, 이러한 방식은 기존의 search에서 찾아낸 유용한 정보들을 사용하지 않고, 처음부터 다시 문제를 풀기 때문에 시간적 낭비를 초래한다. 본 논문에서 제안하는 replanning 알고리즘은 문제를 처음 풀 때는 최적의 알고리즘이라고 알려진 uniform cost search 알고리즘⁽⁸⁾을 기반으로 문제를 풀게 되지만, 변화된 문제에 대해서 최적의 합성 웹서비스를 구할 때는 지난 단계에서 구축한 정보 중 변화되지 않은 부분들을 재사용함으로써, 일반적인 알고리즘보다 훨씬 더 빠른 시간에 최적의 합성 웹서비스를 찾을 수 있다. 본 논문에서 제안하는 replanning 알고리즘은 AI 분야와 알고리즘 분야에서 연구된 incremental algorithm^(9,10)을 기반으로 하고 있다.

본 논문에서 제안하는 replaning 알고리즘은 각 state들의 QoS 값을 구하기 위해서, initial state에서부터 goal state까지를 탐색한다. 이러한 탐색을 위해서, 제안하는 알고리즘은 현재 고려중인 state들을 priority queue를 이용하여 관리하며, 이 priority queue의 key 값은 각 state s에 대해 key(s) = min (s.cqos, s.rhs)로 나타낼 수 있다. 여기서, s.cqos는 현재까지 계산된 initial state에서부터 해당 state s까지의 예상 QoS 값이며, s.rhs는 해당 state s의 cqos 값의 one-step lookahead 값이다. 본 논문의 replanning 알고리즘은 A 알고리즘⁽¹²⁾과 비슷한 방식으로 state들을 확장 방문하게 되며, 이러한 과정을 goal state에 도착할 때까지 반복한다. 이 경우, replanning 알고리즘이 priority queue를 사용했기 때문에, initial state에서부터 goal state까지 최적의 path 상에 있는 edge들의 시퀀스가 최적의 합성 웹서비스에 해당되게 된다. 일반적인 컴포지션 알고리즘들은 여기에서 알고리즘을 종료하게 되지만, 본 논문의 replanning 알고리즘은 문제의 변화를 다시 입력으로 받아서, 변화된 state들의 rhs 값을 수정하고 priority queue에 다시 삽입하게 된다. 그 후에, 새로운 최적의 합성 웹서비스를 구하기 위해 앞선 방식을 반복하게 되면, 변화된 부분만을 다시 계산함으로써, 일반적인 컴포지션 알고리즘들이 변화된 문제를 처음부터 다시 푸는 것에 비해 실행시간을 상당히 줄일 수 있다.

그림. 3. 알고리즘의 순서도

Fig. 3. Flowchart for the algorithm

그림 3은 본 논문에서 제안하는 QoS 기반 웹서비스 컴포지션 문제에 대한 replanning 알고리즘의 순서도이며, 그림 4는 자세한 알고리즘을 나타낸다. 본 알고리즘은 주어진 웹서비스들의 집합 W과 요구사항에 대한 정보를 포함하는 w을 입력으로 받아서, 그 요구사항을 만족시키고 최적의 QoS 값을 갖는 합성 웹서비스를 만들어 낸다. 또한, 계속되는 문제 변경에 대해서 최적인 합성 웹서비스를 구성하게 된다. 본 알고리즘은 main 프로시져를 포함하여 3개의 프로시져로 구성되어 있다. main 프로시져는 1차로 주어진 문제의 입력 값에 따라 문제를 초기화하고, 그에 따라서 FindOptimalComposition 프로시져를 호출하여, initial state인 s에서부터 goal state인 s까지의 최적의 합성 웹서비스를 구하게 된다. 그 후에 외부로부터 문제의 변경을 입력받고 그 입력에 따라 문제를 변경 후, 또다시 FindOptimalComposition 프로시져를 이용하여 변경된 문제에 대한 최적의 합성 웹서비스를 구하게 되며, 이러한 반복을 사용자가 원하는 만큼 되풀이 할 수 있다. 또한, main 프로시져와 FindOptimalComposition 프로시져가 호출하는 UpdateState 프로시져는 입력 값으로 전달받은 state s를 상황에 맞게 priority queue U에 삽입 또는 삭제하게 된다.

제안하는 replanning 알고리즘을 main 프로시져부터 자세히 설명하면, 일단 주어진 w로부터 initial state s와 goal state s을 만들어낸다 (line 32~33). 34번째 줄의 U는 현재 고려중인 state들을 관리하는 priority queue를 나타낸다. 그 후에, 각 state들에 대해서 cqos와 rhs를 ∞로 초기화 한다(line 36~37). 또한, 각 state s에 대해 최적의 경로를 추적하기 위해서 최적의 경로 상의 parent state를 s.parent에 기록한다(초기 값은 NULL).

초기 값 설정 이후에는 FindOptimalComposition 프로시져를 호출하게 되고(line 43), 다음과 같이 priority queue U를 이용하여 initial state에서 goal state까지 탐색하면서 최적의 합성 웹서비스를 만들어 간다(line 6 ~ 30). 먼저, priority queue U로부터 최적의 key 값을 갖는 state s를 반환 받아서 (line 8), 이 state가 overconsistent(즉, s.cqos > s.rhs인 경우)한지 under- consistent(즉, s.cqos < s.rhs인 경우)한지를 검사 한다 (line 9). 만약 해당 state s가 overconsistent하다면, s까지의 경로를 고려했을 때 현재보다 좋은 경로를 찾은 것을 의미함으로, 알고리즘은 state s의 cqos 값에 rhs 값을 대입해준다(line 10). 또한, 이러한 수정을 s의 successor state들에게도 반영해주며, Update- State 프로시져를 호출하여 priority queue도 업데이트해준다(line 12 ~ 18). 만약 8번째 줄에서 반환 받은 state s가 overconsistent하지 않고 underconsistent하다면, 아래의 단계를 거친다(line 19 ~ 28). 즉, 이러한 경우는 일반적으로 현재까지 구해 놓은 최적의 path가 문제의 변경으로 인해 더 이상 유효하지 않을 때 생기는 것이므로, 일단 state s의 cqos 값을 무한대로 재설정한다(line 20). 그 후에, s와 s의 successor state들에 대해서, 그들의 rhs 값들을 업데이트해주고, UpdateState 프로시져를 호출하여 priority queue도 업데이트해 준다(line 21 ~ 27). Find- OptimalComposition 프로시져는 priority queue의 top의 key 값이 goal state의 key 값보다 작거나 goal state의 cqos 값이 rhs 값보다 작을 동안 state들을 확장하며(line 7 ~ 29), FindOptimal- Composition 프로시져가 끝났을 때, initial state에서 goal state까지의 최적의 합성 웹서비스를 찾게 된다. 이 최적의 합성 웹서비스는 ConstructSolution() 프로시져를 호출하여 goal state부터 initial state까지의 최적의 parent 정보를 이용해서 backward로 구성해 낼 수 있다(line 44).

1단계의 최적의 솔루션을 구한 후에는 문제의 변화를 기다린다(line 45). 문제 변화가 입력이 되면, 그 변화에 해당하는 웹서비스들의 QoS 값이 기존의 값보다 개선되었는지, 나빠졌는지에 따라서 나누어 처리된다(line 49 ~ 61). 즉, 만약 개선이 되었다면, 그 후속 state s’에 대해서, 최적의 경로를 변경해 주어야 하는지 판단 후 변경하고, UpdateState 프로시져를 통해서 priority queue도 그에 맞게 변경해 준다(line 50 ~ 54). 그렇지 않고 해당 웹서비스의 QoS 값이 나빠진 경우도, 그 후속 state s’에 대해서, 최적의 경로를 변경해주어야 하는지 판단 후 변경하고, UpdateState 프로시져를 통해서 priority queue도 그에 맞게 변경해 준다(line 56 ~ 60). 이렇게 변화된 문제에 대해, FindOptimalComposition 프로시져를 다시 호출하여 실행하게 되고(line 43), 이 프로시져가 종료하게 되면, 변화된 문제에 대한 최적의 합성 웹서비스를 다시 구할 수 있게 된다. 본 알고리즘은 변화된 문제의 정보를 받고, QoS가 변경된 웹서비스에 영향을 받는 state들만을 다시 priority queue에 삽입하여 계산함으로써 일반적인 알고리즘이 처음부터 다시 계산하는 것에 비해 search space를 상당히 줄일 수 있다.

4. 실험 결과

본 연구에서는 QoS 기반 웹서비스 합성 문제에 대해서 3장에서 설명한 replanning 알고리즘을 구현하였고, 이번 장에서는 그 효율성에 대해서 실험을 통해 입증한다. 본 연구에서 구현한 툴은 4개의 파일(웹서비스들의 집합을 나타내는 WSDL 파일, 웹서비스 파라메터들의 타입 정보를 나타내는 OWL 파일, 웹서비스들의 QoS 정보를 나타내는 WSLA 파일, 요구사항을 나타내는 WSDL 파일)을 입력 파일로 받아서, 최적의 합성 웹서비스를 나타내는 BPEL 파일을 생성한다.

본 실험에서는 웹서비스 챌린지 2009⁽¹³⁾에서 제공된 TestSet- Generator를 통해서 4개의 문제를 임의로 생성하였다. 표 1은 4개의 실험 문제에 대한 특성을 설명하고 있다. 그리고, 본 논문의 실험은 2.30GHz 프로세서, 8G 메모리, Linux 운영체제를 사용하는 PC에서 진행되었다.

본 논문에서 제안하는 replanning 알고리즘의 효율성을 입증하기 위해서, 이번 실험에서는 본 연구에서 구현한 replanning 기반 알고리즘 툴과 uniform cost search 알고리즘⁽⁸⁾에 기반한 툴을 구현하여 비교를 진행하였다. 표 2는 두 개의 툴이 표 1에서 설명한 4개의 문제에 대해서 얼마나 빨리 최적의 합성 웹서비스를 찾아내었는지를 나타낸다. 즉, 표 2는 각 문제에 대하여, 문제 변화율, 두 가지 툴의 실행시간(단위: msec), 성능비율(uniform cost 알고리즘 실행시간 ÷ replanning 알고리즘 실행시간)을 보여 주고 있다. 본 연구에서 제안한 replanning 알고리즘은 문제의 변화된 부분만을 재탐색하기 때문에, 변화율이 적을수록 uniform cost search 알고리즘에 비해 높은 성능을 보일 것으로 예상했다. 이러한 예상을 입증하기 위해서, 본 실험에서는 문제의 변화율을 2%에서 10%까지 증가시키면서 무작위로 문제를 변경하여 두 가지 툴의 실행시간을 비교하였다. 해당 변화율만큼 문제에 변화를 주기 위해서, TestSetGenerator를 통해 생성된 문제에서 해당 변화율만큼의 웹서비스를 램덤하게 선정하여, 그 웹서비스의 QoS 값을 랜덤하게 변화시켰다. 일반적으로 incremental search 분야에서는 문제의 변화가 아주 심하다고는 가정하지 않기 때문에, 본 실험에서도 다른 연구^(14,15)와 비슷하게 10%까지로 변화율을 제한하였다.

표 2는 본 논문에서 제안하는 replanning 알고리즘이 일반적으로 최적의 알고리즘이라고 인정되는 uniform cost search 알고리즘에 비해, 문제에 따라 11.4배에서 1.3배 빠르다는 것을 확인하고 있다. 문제 p에서 웹서비스 변화율이 2%일 때, replanning 알고리즘은 평균 286.4 msec이 걸린데 비해 uniform cost 알고리즘은 3259.8 msec 걸림으로써, replanning 알고리즘이 11.4배 빨랐다. 반면, 변화율이 커지는 경우 (p의 10% 변화율)는 변화된 웹서비스들이 영향을 미치는 부분이 상대적으로 커짐에 따라 성능비율이 다소 낮아지기는 하지만, 그래도 replanning 알고리즘이 1.5배 빠른 것으로 나타났다. 다른 문제(p, p, p)의 경우에도 p과 비슷하게, 문제 변화율이 낮을 때는 replanning 알고리즘이 uniform cost 알고리즘보다 5배에서 10배 정도 빨랐으며, 문제 변화율이 10%가 되어도 1.3배에서 1.5배정도 좋은 실행시간을 보였다.

그림 5는 지금까지 설명한 p, p, p, p에 대한 실험에서 나타난 실행시간을 그래프로 표현한 것이다. 각각의 그래프에서 x축은 문제 변화율, y축은 실행시간(단위: msec)을 나타내고 있다. 각각의 그래프 역시 전체적으로 replanning 알고리즘의 실행시간이 uniform cost search 알고리즘의 실행시간보다 우수한 것으로 나타나고 있으며, 특히 문제 변화율이 적을 때에 훨씬 더 좋은 성능을 나타내고 있음을 입증하고 있다. 그러한 이유는 본 연구에서 제안하는 replanning 알고리즘의 경우, 변화된 문제를 풀 때 문제를 처음부터 다시 풀지 않고, 기존의 답을 바탕으로 변화된 부분만을 재검색하는 방법으로 문제를 해결하기 때문에, 문제 변화율이 적을수록 replanning 알고리즘이 재검색해야 하는 부분이 줄어들기 때문이다. 반면에 일반적인 알고리즘은 처음부터 문제를 새로 풀기 때문에 변화된 문제에 대한 답을 찾을 때도 일정한 정도의 노력이 필요하다.

5. 결 론

본 논문에서는 변화되는 QoS 기반 웹서비스 컴포지션 문제를 효율적으로 해결하기 위한 replanning 알고리즘을 제안하였다. 일반적인 QoS 기반 웹서비스 컴포지션 알고리즘들은, 문제가 변경된 경우에 이 문제를 새로운 문제로 인식하여 처음부터 다시 최적의 솔루션을 구하게 된다. 반면에 본 논문에서 제안하는 replanning 알고리즘은 이전 단계에서 구해 놓은 정보들을 최대한 재활용하여, 변화된 웹서비스들이 영향을 미치는 부분만을 재계산함으로써, 일반적으로 최적의 알고리즘이라고 알려진 uniform cost search 알고리즘에 비해 실행시간 측면에서 우수한 성능을 보였다. 본 논문에서 제안하는 replanning 기반 알고리즘은 IoT 기기들을 포함한 환경(일시적인 서버 다운, 시스템 과부하, 네트워크 불량 등의 환경적 변화가 빈번한 환경)에서의 웹서비스 합성 문제를 해결할 때 기존의 알고리즘보다 실행 시간 측면에서 큰 도움을 줄 수 있을 것으로 예상한다.

향후 연구과제로서 replanning 알고리즘을 다양한 분야에 적용하는 것이 의미 있다고 할 수 있다. 특히, vehicular network⁽¹⁶⁾과 UAV(Unmanned aerial vehicles)⁽¹⁷⁾와 같은 QoS 기반 IoT 서비스 분야에 적용이 흥미롭다 할 수 있다. 또한, 다양한 실험을 통해 replanning 알고리즘이 일반 알고리즘보다 우수한 부분을 더 정확히 알아내는 연구도 중요할 것이라 생각된다.