The continuous advance of digital mobile communication technology coupled with the recent proliferation of portable computers has led development efforts for future mobile systems toward mobile computing - a new paradigm of future communication and computing networks. This thesis addresses two major issues, indexing and clustering, of wireless data broadcasting that has many application areas for its bandwidth and energy efficiency.
First, we address the indexing issues for wireless broadcast data. The index information on the wireless channel enables the clients to move to the data of their interest without energy comsumption, so improves the energy efficiency. In the thesis we propose a set of index replication methods. Forward-Link (FL) approach, Nephew-Link (NL) approach, and Sibling-Link (SL) approach. These index replication methods are based on our three criteria: accessibility, energy-efficiency and adjacency. These criteria mean an index information should provide addresses such that: the addresses should be accessible from the time when the index is delivered, mobile clients should get energy-efficiency through the addresses, and the replicated addresses should be adjacent to the address of replicating index. With experiment and analysis, we show the performance of these index replication methods. We also propose another index replication method that does not satisfy the adjacency criteria, but has the best performance for point queries among the proposed methods.
Second, we address the clustering issues of wireless broadcast data for multi-point queries. By effective clustering of the broadcast data, the mobile client can access the data on the air in short latency, that is, it improves access time efficiency. We assume that every data object is not replicated in a single broadcast stream and a mobile query accesses one or more data objects. The inherent measure of wireless data clustering is the access time of queries, but it is difficult to use in clustering methods. Thus, we propose a new measure, called Query Distance (QD), that represents the coherence degree of data objects a mobile query accesses. We show the Query Distance measure effectively represents the query's access time. Using the Query Distance measure, we propose two clustering methods for wireless broadcast data, 1) Schedule Expansion Method and 2) Gray Coding Method. The Schedule Expansion Method (SEM) consrtucts the broadcast schedule by appending each data set of the queries with possible data movements. In this method we propose a set of operators and rules of schedule expansion. The Gray Coding Method(GCM) uses the clustering properties of the Gray codes. We explain the wireless data clustering properties of the Gray codes with the Code Distance measure. By experiments we show the performance advantage of the proposed methods.
The proposed indexing and clustering methods can be effectively combined and used for wireless data broadcasting, that is, we can generate a sequence of wireless data broadcasting with our clustering methods and construct the index structure for the data with our indexing methods. Through the experiments and analysis we show they can improve the performance (i.e., bandwidth and energy efficiency) of wireless data broadcasting systems.
무선 통신 기술의 발전에 따라 최근 다양한 형태의 이동 컴퓨팅 환경들이 나타나고 있다. 우리가 흔히 사용하고 있는 Cellular Phone이나 PCS를 비롯하여 이들과 연동하여 사용되는 각종 PDA 단말기들을 이용한 무선 정보 시스템의 출현이나, 라디오 주파수대를 사용하는 전문화된 무선 분산 시스템들에 이르기까지 이동 컴퓨팅 패러다임은 다가오는 미래를 대표하는 컴퓨팅 구조가 될 것이 명확하다.
무선 통신을 이용하는 이동 컴퓨팅 시스템에서 가지고 있는 특징들 중에서 기존 유산 기반 시스템들에서는 발견할 수 없는 것들로 무선 통신 대역 폭(bandwidth)의 제약과 무선 단말기의 전원(energy)제약이 있다. 유선 환경과 달리 인간이 통신을 위해 사용할 수 있는 주파수 대역이 물리적으로 한정되어 있으며, 이동 사용자가 휴대하는 단말기는 전지를 에너지원으로 사용하기에 에너지 사용이 제한적일 수 밖에 없다. 이러한 두 가지 문제를 효과적으로 해결할 수 있는 방법이ㅡ 하나로 데이타 방송 (broadcasting) 기법이 제안되어 사용되고 있다.
데이타 방송이란 서버로 부터 불특정 다수의 사용자들에서 정해진 채널을 통해 데이타를 전송하는 방법으로 사용자들은 서버에 요구(request)를 하지 않고 단순히 방송 되는 데이타를 수신하기만 하는 방법이다. 사용자가 서버에게 요구를 하지 않음으로서 사용자의 에너지 사용을 최소화 할 수 있으며 - 무선 데이타의 송신은 수신에 필요한 에너지의 1000배 이상을 필요로 한다 - 공동의 채널을 많은 사용자가 공유할 수 있기 때문에 주파수 대역의 효과적인 사용이 가능하다.
방송 기법을 통한 데이타 전송시 고려하여야 하는 패러미터에는 데이타의 접근 시간(access time)과 튜닝 시간(tuning time)이 있다. 데이타 접근 시간은 사용자가 방송 채널을 통해 특정 데이타를 수신하기를 희망하는 시점에서 원하는 데이타들 완전히 전달 받을 때 까지의 대기 시간을 나타내며, 튜닝 시간은 접근 시간 동안 방송 데이타를 듣기 위해 에너지 사용을 하여야 하는 시간을 나타낸다. 경우에 따라 자신이 원하지 않는 데이타는 듣지 않고 지나칠 수 있기 때문이다.
본 논문에서는 무선 방송 데이타의 효과적인 관리를 위하여 사용자가 효과적으로 원하는 데이타를 찾을 수 있도록 하는 방송 데이타의 i) 색인 기법과, ii) 클러스터링 기법에 대하여 다루고 있다. 색인 기법은 데이타의 튜닝 시간을 단축시키는 방법이며, 클러스터링 기법은 데이타의 접근 시간을 단축시키는 방법이다.
기존 색인 기법으로 Distributed Indexing 이라는 색인 방법이 있다. 트리 구조 형태의 색인으로 계층 구조의 일부를 반복하는 방법을 사용하며, 최적의 반복 수준에 대하여 연구가 되었다. 본 논문에서는 이 방법을 사용하는데 있어 주파수 대역의 낭비가 발생하는 문제점을 지적하고 이를 해결하는 방법을 제안한다. 기존 방법이 색인을 반복함에 있어 시간적으로 과거의 주소를 색인 정보로 제공하는 문제점을 해결하기 위하여, 색인 반복시 반복 색인이 지녀야 하는 3가지의 기존으로 접근 가능성 (accessibility), 에너지 효율성 (energy-efficiency), 그리고 근접성(adjacency)를 제안하였다. 그리고 이들 기준에 부합하는 3가지 색인 반복 기법 - FL, NL, SL을 제안하였다.
기존 방법과 비교하여 제안하는 방법들이 제공하는 성능 향상 정도를 분석을 통해 '식'형태로 나타냈으며, 실험으로 이들 분석의 정확성을 입증하였다. 3가지 기준들 중에서 영역 질의(range query)를 위한 근접성 기준을 완화시켜 점 질의(point query)에 대하여 최고의 성능을 제공하는 새로운 방법도 제시하였다. 제안한 방법들은 추가의 오버헤드 및 단점들을 지니지 않으며, 기존 색인 방법들의 문제점을 효과적으로 해결할 수 있는 방법들로, 무선 방송 데이타의 색인으로서 효과적임을 알 수 있었다.
지금까지 연구되어 온 무선 방송 데이타의 클러스터링 방법은 점 질의들을 효과적으로 처리하기 위하여, 데이타의 방송 횟수를 조절하는 방법들이었다. 하지만, 본 논문에서는 기존에 고려하지 않았던 다중 점 질의(multi-point query)를 가정하고 있다. 하나의 질의가 여러 데이타들을 접근하는 환경에서는 데이타의 클러스터링이 매우 중요한 처리 대상이 된다.
무선 데이타의 클러스터링은 기존이 디스크 환경에서의 데이타 클러스터링과 전혀 다른 특성을 지니고 있다. 디스크를 사용하는 경우에는 디스크의 탐색 시간(seek time)이 중요한 성능 요소로서 작용하지만, 무선 환경에서는 그러한 요인이 존재하지 않는다. 본 논문에서는 무선 방송 데이타의 클러스터링을 위하여 질의 거리(Query Distance)라는 클러스터링 기준을 제시한다. 이는 한 질의가 접근하는 다수의 데이타들 사이에 나타나는 응집 정도를 나타내는 기준으로 무선 데이타의 접근 시간을 효과적으로 나타내는 수단이 된다.
본 논문에서 제안한 클러스터링 기준을 사용하여 2가지 클러스터링 방법을 제안한다. 첫 번째 방법인 Schedule Expansion Method(SEM)은 질의가 갖는 참조 빈도(reference frequency)에 따라 상위 질의부터 하위 질의의 순서로 방송 스케줄에 추가하여 스케줄을 구성하는 방법이다. 이 방법에서 상위 질의의 질의 거리를 최소화 하면서 하위 질의의 질의 거리를 줄이는 질의 확장 규칙들(schedule expansion rules)과 연산자들을 사용한다. 두 번째 방법인 Gray Coding Method(GCM)은 그레이 코드(Gray codes)의 클러스터링 특성을 이용하는 방법으로 각 데이타들을 질의 참조에 따라 비트 벡터 형태로 나타낸 후, 그레이 코드의 배열 순서에 따라 정렬하는 방법을 사용한다. 그레이 코드가 갖는 무선 데이타 클러스터링 특성을 분석하여 제안하는 방법이 갖는 의미를 보였다.
제안하는 두가지 무선 데이타 클러스터링 방법을 실험하였고, 그 결과로 다중점 질의들에 대한 클러스터링의 중요성을 확인할 수 있었다. 두 방법 중 SEM이 GCM에 비해 다소 우수한 성능을 나타냈으며, GCM은 SEM에 비해 구현이 쉬운 특징을 갖는다.
본 논문에서 제안하는 색인 및 클러스터링 기법들은 다양한 무선 컴퓨팅 시스템에서 활용될 수 있다. 데이타 클러스터링을 통해 방송 데이타의 순서를 결정한 후 색인 기법을 통해 색인과 데이타를 결합하여 데이타를 사용자들에서 방송하게 된다. 따라서, 무선 데이타의 방송에 있어 데이타의 클러스터링과 색인은 시스템의 성능 결정에 매우 중요한 역할을 담당하게 된다.