With the combination of emerging paradigms, such as service-oriented computing and ubiquitous computing, end-users are now provided with a myriad of services to utilize smart objects to achieve their goals. The most promising standard to utilize these services is WS-BPEL, which employs centralized coordination for simpler management of interaction and synchronization. However, centralized approaches suffer from scalability, heterogeneity, and inefficiency, especially when the system is managed across different entities. Moreover, it is quite unrealistic to assume that one client device has permissions to access all available operations of smart objects as well as support different types of required communication interfaces. Hence, in this paper, I propose a novel distributed coordination scheme that helps end-users collaborate more efficiently to achieve their common goals. Unlike traditional distributed coordination methods, that are limited to static environments, the proposed scheme incorporates dynamic ubiquitous computing environments where requirements of tasks and available resources can be altered throughout task execution. Under the proposed scheme, mobile client devices are able to self-collaborate without a dedicated central server by spontaneously electing a task coordinator among them. Moreover, the proposed scheme also deals with dynamic events such as the joining and leaving of users, clients and tasks, supporting dynamic reallocation while keeping them transparent for end-users. Finally, the proposed scheme is evaluated through simulations at different numbers of services and client devices, showing improved results in performance optimality, assignment efficiency, and dependency coverage of composition.
어반 컴퓨팅 환경은 기존 유비쿼터스 환경의 확장된 형태로써 보다 고밀도의 최종 사용자와 더 많은 물리적 환경 그리고 다양한 사용자의 유형과 사회적 관계를 지원한다. 어반 컴퓨팅 환경의 최종적 목표는 최종 사용자가 보다 쉽게 로컬 환경 또는 웹에 존재하는 서비스들을 발견하고 상황에 맞게 조합하여 언제 어디서든 사용할 수 있도록 지원하는 것이다. 최근에 스마트폰, 스마트 TV, 지능 전자 기기 같은 스마트 오브젝트들이 급격히 증가함에 따라 기존의 웹 서비스 조합 기술 역시 물리적 환경으로 확장되고 있다. 기존 웹 서비스 조합 기술은 서비스 간의 느슨한 결합(Loosely coupled), 상호 운용성(Interoperability), 플랫폼 독립성(platform-independent) 등의 장점을 통해 최종 사용자의 상황에 맞춰 유연성 있는 서비스 조합 및 제공이 가능하고 이 서비스들은 웹 서비스 수행 언어 표준인 WS-BPEL (Web Service-Business Process Execution Language)을 통해 실제 환경의 스마트 오브젝트들과 연동되어 사용자의 태스크를 지원한다.
WS-BPEL은 하나의 ‘작곡자’(Orchestrator)를 통한 중앙 처리 방법을 사용함으로써 서비스 간의 상호작용과 동기화를 보다 간단하게 관리할 수 있다는 장점이 있다. 하지만 중앙 처리 방법은 크로스-엔터프라이즈 같은 분산 형태를 가진 시스템에서는 매우 비효율적일 뿐만 아니라 수행해야할 태스크와 처리해야할 계산(Computation)이 많아질수록 성능이 급격히 저하된다. 뿐만 아니라, 수많은 스마트 오브젝트가 존재하는 실제 상황에서는 하나의 클라이언트 기기에게 모든 스마트 오브젝트에 대해 접근할 수 있는 권한과 상호 운용성을 기대하기는 어렵다. 따라서 주어진 태스크를 보다 효율적으로 수행하고 수행 불가능한 태스크를 가능하게 하기 위해서는 클라이언트 기기가 서로 협력할 수 있는 분산 코디네이션 방법이 필요하다.
태스크의 분산 처리 방법은 이미 기존의 컴퓨팅 환경에서 연구가 진행되어 왔고 이의 효율성 역시 입증되었다. 하지만 어반 컴퓨팅 환경에서의 서비스 조합 및 수행에서는 다음과 같은 이유로 기존의 분산 처리 방법은 적용할 수 없다. 첫째, 기존의 컴퓨팅 환경과 반해 어반 컴퓨팅 환경에서의 클라이언트 기기는 CPU, RAM과 같은 단순 처리 능력 뿐만 아니라 센서, 통신 방법, 액세스 권한 등 클라이언트 기기간의 역량 차이를 보인다. 즉, 각각의 클라이언트 기기는 접근 할 수 있는 센서, 스마트 오브젝트의 기능들이 다르기 때문에 수행 가능한 서비스들 역시 나뉘게 된다. 둘째, 어반 컴퓨팅 환경에서의 클라이언트 기기는 대체로 모바일 기기이기 때문에 이들은 태스크 수행 중 언제나 떠날 수 있고 또한 새로운 기기 역시 언제나 협력에 합류 할 수 있어야 한다. 더불어, 사용자들의 합류, 떠남에 따라 역동적으로 변하는 요구사항에 맞춰 태스크의 삽입/삭제/확장을 통한 태스크의 재구성이 가능해야 한다. 이들은 수행되고 있는 태스크에 방해 없이 이루어져야 하며 최종 사용자의 개입 역시 최소화 되어야한다.
본 논문에서는 위의 요구사항을 준수하는 태스크의 분산 코디네이션 방법을 제시한다. 가장 최적으로 태스크를 분배하는 문제는 각 서비스의 품질 뿐만 아니라 서비스 간의 의존 관계, 클라이언트 기기의 능력 및 수용력 등 다층, 다지수를 고려해야하는 문제로, 이는 다항식 시간 내에 풀 수 없는 NP-hard 문제이다. 따라서 태스크를 즉시적으로 분배하기 위해 본 논문에서는 그래프 채색 알고리즘을 이용한 분산 코디네이션 기법을 제시하고 반복적으로 그리디 알고리즘(Greedy Algorithm)을 수행하여 분배 결과의 최적성을 향상시키는 알고리즘을 제안하였다. 이어서 제안된 알고리즘의 성능 평가를 위해 다수의 클라이언트 기기가 협력하여 태스크를 수행하는 시뮬레이션을 구현하고 다양한 시뮬레이션 환경에서의 반복적 실험을 통해 제안된 알고리즘의 효율성을 증명하였다.
