This dissertation describes a service discovery system that supports new application scenarios in ubiquitous networks. Traditionally, service discovery systems are used to discover network devices (for example, printers, faxes, projectors, and so on) that are available on the local area network. In contrast, we aim to develop a service discovery system that locates physical objects in the real world including objects that typically are not connected to the network. Our application scenarios include a friend finder, a discount coupon, a bargain, a goods exchange, and an exhibition. Together, these represent the future vision of service discovery in ubiquitous computing environments.

There are a number of technological solutions that can be used to achieve these application scenarios. In general, they can be divided in two categories: 1) systems that are based on infrastructure (infrastructure-based systems) and 2) systems that are not based on infrastructure (infrastructure-less systems). Systems built using cellular networks or Wi-Fi access points represent infrastructure-based solutions. Because of high network installment costs and expensive maintenance, we choose an infrastructure-less approach for our service discovery system implementation. The known wireless technologies that can be used for infrastructure-less service discovery include: Wi-Fi based Mobile Ad hoc Networks (MANET), Personal Area Networks (PAN), such as Bluetooth; and wireless sensor networks (WSN), such as Zigbee. However, these solutions are inappropriate for realizing the described scenarios because of disadvantages including uncertain or long service discovery time and high power consumption. In addition, available discovery systems based on these wireless technologies lack some tools necessary for easy device configuration. They also lack a dedicated personal wireless device for service discovery in ubiquitous computing environments. All this inspired us to develop a complete service discovery system, including software and hardware implementations, to fill the described gaps and make possible the described scenarios.

The service discovery system design depends on the selection of a communication model. Unlike previous reactive systems, in which a discovering device sends a request packet, the proposed discovery system is based on proactive discovery in which advertisers broadcast service data. The proposed model is selected because it represents a basic protocol used in almost all communication systems to obtain information about available wireless communication devices in proximity. To get such information, these devices must send periodic broadcast packets known as "beacons," which include the device ID. In our system, we use beacons along with service data to advertise services in proximity so that other devices can receive these advertisements and filter them to check whether a user needs them or not.

In addition to a proactive discovery model, we consider a single-hop time-bounded discovery. The reason for considering a single-hop discovery is motivated by fact that multi-hop broadcasting in distributed wireless networks postulates a well-known problem called broadcast storm problem; that is, there's a tradeoff between covered area and the number of sent re-broadcasts. In our service discovery, we need to discover-within a few dozen meters-the area that can be covered with a single-hop broadcast without generating extra traffic, which consumes power and affects scalability. Moreover, it's important for a user to discover all services in proximity within a defined time-bound. Time-bounded discovery allows for controlling discovery time and power consumption because a wireless device selects the lowest broadcast rate to achieve necessary discovery time-bound, thus saving more power by broadcasting fewer packets.

In practice, the realization of the pure infrastructure-less discovery system is a difficult task. This is for two reasons. First, it is difficult to achieve some fundamental functionality without using a centralized solution that would require infrastructure. For example, determining a common format data for a service requires that a server stores all data formats). Second, because we perform service discovery using miniaturized wireless devices that provide poor performance characteristics, it is convenient to use infrastructure to configure these devices for optimum performance. Hence, we propose a hybrid service discovery system that combines infrastructure-based and infrastructure-less functionalities. The distinguishing feature of the proposed system is that we require devices to discover services without relying on infrastructure. Connecting to the infrastructure is required only when configuring the device and accessing discovered services. Because these procedures take place infrequently, the proposed system is similar in its design to infrastructure-less discovery systems but provides superior performance characteristics compared to the pure infrastructure-less discovery systems. All this makes the proposed system a potential candidate for all service discovery applications in future ubiquitous networks.

In the design of our system we consider four components including a data management system, the hardware design of a miniaturized wireless discovery device, client software and wireless device firmware, and a time-bounded wireless media access control (MAC) protocol. For the design of each component, we consider conventional methods and propose new ones that best fit system requirements for flexible and efficient service discovery in ubiquitous networks.

A data management system targets three important discovery system methods: 1) a method to decide the common data format for advertisement and filter of the same service, 2) a method to achieve scalable compact data format, and 3) a procedure for handling discovered services. To achieve efficient matchmaking, we introduce a new method for data format sharing and creation that requires users to re-use available data formats or create new ones that can be shared with other users. In this case, users are guaranteed that their service data has a high chance of being discovered. In addition, we proposed a method for service data packet minimization that allows resource-constrained wireless devices to broadcast tiny service data packets that contain sufficient service information for users to locate necessary services. Having smaller data packet sizes result in shorter transfer time. This, in turn, allows for achieving superior discovery performance because the wireless channel is less busy with data traffic. Finally, we propose a data management method for handling service discoveries. In particular, we designed a method, currently not implemented in other service discovery systems, that blocks service discoveries of already discovered services.

We also implemented a hardware device prototype for proactive wireless discovery. The design requirement was to build a compact wireless device with the minimum number of low power hardware components sufficient for service discovery. In addition, it was important to make a general device that could be used in diverse discovery application scenarios without the need to develop a new device to meet application requirements. Moreover, we developed a device that allows for the replacement or extension of some hardware components should some additional hardware be needed. Finally, we include additional hardware for the device that provides a method for seamless and automatic firmware updates.

In the dissertation work, we describe the design of client software and firmware. The designed client software allows an average user to easily configure and control a wireless discovery device. The designed firmware allows a user to optimize the program size of the firmware depending on application needs. The client software includes a middleware plus generic applications developed on top of the middleware. The middleware allows a developer to access a full range of system functions to create customized applications for service discovery in ubiquitous computing environments. The generic applications allow users and developers to quickly introduce service discovery application scenarios without any need to use programming languages (unless there is a need of custom user interface). Hence, we describe our developed general web-enabled interface that lets a user configure a device for wireless discovery or advertisement, define new services, and access detailed information about discovered services. Also, we developed a unique application that lets a developer control a wireless device with minimal development time. Finally, the dissertation describes modular firmware design that allows for minimizing the size of the firmware to make it possible to use microcontrollers with smaller available memory. Because microcontrollers with smaller program memory are cheaper, the result is a cost-effective solution. The minimization becomes possible because some application scenarios do not require the full range of available functionalities.

One component that significantly affects discovery time performance and power consumption is a wireless media access control (MAC) protocol. The dissertation describes the design and evaluation of a new wireless MAC protocol that achieves reliable and economical service advertisement given the required discovery time in a distributed wireless network. The proposed protocol achieves a given discovery time using the lowest possible transmission rates. (Low transmission rates result in lower power consumption because nodes transmit fewer packets. The protocol represents a decentralized autonomous protocol in which a node makes an autonomous decision about broadcast strategy by collecting information about network conditions. Finally, the protocol operates in a wireless distributed network that has a random topology with sparse and dense node areas.

In summary, the dissertation describes a complete solution for a service discovery in ubiquitous networks to support new application scenarios. The proposed service discovery system represents a hybrid architecture in which infrastructure-based functionalities are used only during when configuring a device or accessing discovered services. The single-hop time-bounded proactive discovery model follows the basic pattern available in most communication networks. Additionally, the proposed model can be extended to other models including reactive and/or multi-hop discovery. We review four components of the service discovery system and their specific functionality including a data management system, wireless device hardware, client software, and a wireless MAC protocol. These components include new methods, algorithms, and protocols that allow for new types of service discovery scenarios in ubiquitous computing environments.

本論文は「ユビキタスネットワーク環境における時間制約型プロアクティブサービス発見機構に関する研究」(Time-bounded Proactive Service Discovery in Ubiquitous Networks)と題し,ユビキタスネットワークにおけるサービス発見のシステムの在り方と,サービス発見に特化したプロアクティブ型の無線通信プロトコルの2つについて論じている.

第1章は,ユビキタスコンピューティングに関するこれまでの研究,ユビキタスネットワークにおいて求められるサービス発見技術やサービス発見が抱える本質的な問題に関して触れ,本論文の背景と各章の目的について述べている.

第2章では,ユビキタスネットワーク環境において実現される新しいサービス発見の形を提案している.具体的には,近くを通る友人,近くの商店からの広告,物々交換を希望する他人の発見といったアプリケーションシナリオを挙げている.このようなアプリケーションシナリオの実現に向けては,近距離の検出,プロアクティブ型,時間制約を設定可能という3つの特徴を持つサービス発見が望ましいことを示したうえで,そのようなサービス発見を近接型サービス発見として定義している.続けて,ユビキタスネットワーク環境での新しいサービスと従来のサービスとを比較し,検出可能な距離の粒度や発見時間といった点から携帯電話やBluetoothといった既存の手法によっては現実的ではないことを示している.

第3章では,近接型サービス発見の要件を明らかにしている.具体的には,サービス発見を利用する全てのアプリケーションにとっての共通の要件として,サービス記述を明示的に行うこと,ユーザがサービス広告およびサービス発見を簡単に設定できることといった要件を示している.また,実際のサービス発見を行うために,プロアクティブ型の発見,近接検知,モビリティといった性質が必要となることを示している.さらに,それぞれのアプリケーションシナリオごとの要件をも明らかにしている.

第4章では,第3章で示した要件を満たすことが可能な,ユビキタスネットワークにおけるサービス発見の設計について述べている.具体的には,まず,システムの全体像,構成要素とその機能について示している.本システムはサーバ,クライアント,サービス発見/広告デバイスから成る.サーバは任意のユーザが必要なサービスのフォーマットを選択できるデータベースを保持している.クライアントはユーザにサービス発見/広告デバイスを簡単に設定可能とするソフトウェアを提供する.サービス発見/広告デバイスは短距離無線を具備しており,実際にサービス発見を行う.続けて,プロアクティブ型の発見を行うためのサービス発見/広告の手続き,高速なサービス発見を実現するためのデータリンク層,発見可能距離の調整機能,モビリティを実現するためのサービス発見/広告デバイスの設計などについて詳細に示している.

第5章では,サービス発見に利用するパケットサイズの小型化手法を示している.パケットサイズはサービス発見の高速化および低消費電力化に向けて重要な要素である.まず,パケットサイズの小型化に向けて,ローカルIDレプリケーション,データ分離,データインデキシングという3つの方法について検討評価している.ネットワークインフラへの依存性の観点から,データ分離とデータインデキシングの2つの方法が提案したサービス発見に適したパケットサイズ小型化手法であることを示している.さらに,データ分離とデータインデキシングの2つの手法に対して,包括的にデータサイズを検討している.

第6章では,ユビキタスネットワークにおいてサービス発見を行う無線MACプロトコルに関して述べている.本無線MACプロトコルは,プロアクティブ型の情報発見を実現するためにFramed Alohaのプロトコルを用いることで,決められた時間内に1ホップで到達するノードを発見することを可能にする.また,本無線MACプロトコルを理想的なネットワークトポロジとランダムなネットワークトポロジの2種類で評価を行い,想定環境において有効であることを示している.さらに,本手法をマルチホップ通信に拡張してサービスを特定時間内に発見を行う方法や,簡易な消費電力低減手法についての解析も行っている.

第7章では,各構成要素の実装について詳細に述べている.まず,サーバとクライアントとサービス発見/広告デバイスのためのソフトウェアコンポーネントの全体像を示している.続けて,サービス発見/広告デバイスのハードウェアデザインと,ユーザが簡単に設定できるように設計された汎用的でグラフィカルなユーザインタフェースの2つのコンポーネントを詳細に示している.

第8章は論文全体を総括しており,本論文の成果をまとめるとともに,ユビキタスコンピューティングの実現へ向けて残された課題,および今後の研究の方向性について述べている.

以上,これを要するに,本論文は,計算資源や通信資源が制約されたユビキタスネットワーク環境に適したサービス発見システムを提案し,個々の機構の有効性を実証したものであり,情報学の基盤に貢献するところが少なくない.したがって,博士(科学)の学位を授与できると認める.