大下 福仁

本稿では,はじめにエージェントグループの概念を示し,グループゴシップ問題の定義を行う.エージェントグループは,同じ目的を成し遂げようとする複数エージェントの集合である.例えば,あるアプリケーションによって作られた複数のエージェントは同じグループに属す.複数のアプリケーションが実行されているモバイルエージェントシステムでは,複数のグループが存在する.グループゴシップ問題とは,各エージェントが同じグループに属す全てのエージェントから情報を収集することである.次に,異なるグループのエージェントが協調することにより,各グループのグループゴシップを効率よく実現するためのアルゴリズムについて考察する.ただし,収集する情報には,機密情報など他のグループには知られたくない情報が含まれていることがあるため,他のグループのエージェントとは制御情報(例えばカウンタ値やIDなどの情報)のみ交換を許すこととする.本稿では,これらの条件のもと,グループゴシップ問題の解決に必要な総移動数を最小化することを考える.その結果,様々なネットワークトポロジに対して総移動数の上界と下界が一致することを示す.

オーバーレイネットワークとは,物理ネットワーク上に構築される仮想リンクから誘導されるネットワークである.仮想リンクを用いることで,物理ネットワークの制約を受けずに望ましい性質を持つトポロジを構成することができる.弦付リングネットワークは,効率的なルーティングや探索,負荷分散,さらに高度な連結性を実現するネットワークトポロジとしてよく利用される.オーバーレイネットワークには,物理ネットワークの変化によって引き起こされるトポロジの変化に対する適応性(自己安定性)の実現が望まれている.本稿では,オーバーレイネットワークとして弦付リングネットワークを構成する空間計算量に優れた自己安定アルゴリズムを提案する.

本稿では,仮想グリッドネットワークにおける葉が多い幅優先全域木(BFS木)の安全な自己適応型構成法の提案を行う.仮想グリッドネットワークとは,無線通信端末(ノード)が点在する領域を正方領域(グリッドセル)に分割し,各グリッドセルから1つずつ選んだノード(ルータ)で構成されるグリッド状のネットワークである.本稿では,グリッド上に任意の根付き全域木が与えられたとき,局所的更新を繰り返し適用することにより,葉が多いBFS木を再構成する手法を提案する.本手法は,再構成の間も常に全域木を維持するように木を局所的に変更する安全収束という性質を満たす.

本稿では,非同期リングネットワークにおけるモバイルエージェントの部分集合問題について考察する.部分集合問題とは,集合すべきエージェント数gが与えられたとき,すべてのエージェントがサイズ(エージェント数)g以上のグループに分かれて集合する問題である.本稿では,アルゴリズムが決定性で,エージェントにIDがある場合と,アルゴリズムが乱択で,エージェントにIDがない場合に,部分集合問題を解決するアルゴリズムを提案する.そして,決定性アルゴリズムでは,ノード数をnとしたときに,総移動回数の上界がO(gn)であることを示し,総移動回数の点で漸近的に最適であるということを述べる.

本稿では,リングネットワーク上に存在するモバイルエージェントを等間隔に配置するための,均一配置アルゴリズムについて考察する.各ノードに白板が存在する場合,およびノードにトークンを置くことのできる場合について,それぞれ均一配置を行う移動方法を提案し,最悪時のエージェントメモリ量,時間複雑度,エージェントの総移動回数の関係を示す.また,リングネットワークで均一配置を実現するための総移動回数の下界を示し,提案した移動方法が総移動回数の観点で漸近的に最適であることを示す.

一様充填問題を解決するにあたり，自律移動が可能なロボティックセンサエージェント(以下，RSAと呼ぶ)を利用した方法がある．RSAを利用する手法には，対象領域の性質やRSAの性能の違いにより，多数のモデルが存在する．本稿では，格子型にモデル化を行った領域を扱い，議論を進めていく．また，対象領域の格子型へのモデル化の他に，対象領域の形状やアゴリズムの制約により，複数のモデルに分類し，各モデルにおいて求められるRSAの性能比較を行う．更に，分類したモデルの下で，それぞれ適用可能な提案アルゴリズムを紹介する．

本研究ではセンサネットワークを用いたトラッキングを扱う.<br />トラッキングとは移動体の位置情報を監視し,<br />ユーザに与えることである.また,センサネットワークでは<br />エネルギー消費を抑えることが望まれており,<br />送信されるメッセージ数を少なくすることが重要である.<br />多くの既存研究では,センサネットワーク内の1ノードを<br />データ保管用のノードとして設定することで,<br />ユーザが効率的に情報を収集することを提案している.<br />しかし,これらの手法ではユーザが必要としない時にも,<br />データ収集のためのメッセージを必要とする.<br />本研究では,データ保管用のノードを特定しないことにより,<br />ネットワーク全体でのメッセージ数を削減する手法を提案する.

本研究では，UNIXコマンドを実際に使用しながら効率的に学習することが可能なシステムを提案する．提案システムでは，学習者の入力したコマンド列に対して，同数かより少ないコマンドで置換可能な効率的なコマンド列を提案する．学習者が次にどのコマンドを入力すべきか分からない時には，次に入力すべきコマンドの候補を提示する．これにより学習者はシステムが提示したコマンドに関する知識の習得することが可能となる．次に，提案システムを利用して2人の学習者の入力履歴を比較し相互学習を行うこれによりシステムが適切に助言出来なかった場合にも，他の学習者の入力履歴から，学習者が新たな知識を習得することを期待できる．本発表では，提案システムの紹介・評価結果について説明する．

動的な分散システムにおける重要な問題の一つに，トポロジ変化に対して全域木を再構成する問題 (全域木更新問題) がある．全域木は，分散システム内の各ノードが，木上の隣接ノード集合や木上の親ノードを出力として管理することによって表される．頻繁な出力の変更はシステムの可用性を低下させるため，出力の変化数を最小化して全域木更新問題を解くことが望ましい．これまでに，全域木更新問題を解く分散アルゴリズムは提案されているが，出力の変化数の最小化を目標としているものはない．本稿では，出力の変化数の最小化を目標とする 3 つの全域木更新問題を定式化し，これらの問題を解く分散アルゴリズムを提案する．One of the most important properties of distributed algorithms for dynamic distributed systems is to update a spanning tree (SPT) in response to topology changes. An SPT is represented by outputs of each node: tree neighbors and the parent on the tree. Some distributed algorithms to update an SPT have been presented but no algorithms aim to minimize the number of output changes. Frequent output changes reduce the availability of the system. Hence, it is desirable to update the SPT with minimizing the number of output changes. This report formalizes three SPT update problems with the aim of minimizing the number of output changes and presents distributed algorithms for the problems.

著者らは，オンラインでの協調学習における議論を支援するために，HAKASE システムを提案する．HAKASEは以下の流れに沿った議論型の協調学習を支援する．まず学習者は事前にWWW上の資料を収集する．そして学習者たちはオンラインチャットに似た形式でHAKASE を用いた議論を行なう．このとき，各参加者の発言を促す資料を，議論進行に応じてHAKASE は随時自動提示する．これにより，資料活用が容易な議論環境の実現と同時に，資料を根拠とした発言を参加者に意識させる効果を狙う．著者らはHAKASE の試作システムを実装し、評価実験を行なった．本稿では実装の概要と運用結果について報告する．In this paper, we propose HAKASE system which supports online discussion in collaborative learning. Specifically, HAKASE supports collaborative learning of the following style: Learners search useful online documents on the Web in advance. Then, they discuss online with HAKASE, like online chat. During a discussion, HAKASE presents appropriate online documents that learners found in advance. HAKASE system gives online discussion space in which learners easily make use of online documents, and at the same time, it makes learners be aware that opinion must be stated based on reasons, specifically, online documents that support their opinion. We implemented a prototype system of HAKASE, and evaluated it. This paper reports outline of mplementation of HAKASE and evaluation of test operation.

fー耐故障分散アルゴリズムとは，高々ノ個の計算機が故障しても正しく問題を解くアルゴリズムである．本研究では，ノー耐故障分散アルゴリズムの理解を支援するために，f＋１個の故障のもとで正しい解を出力しない実行と，その実行に類似したノ個またはf＋１個の故障のもとで正しい解を出力する実行を生成するシステムを提案する．これらの実行を比較することで，故障が問題を解けなくした原因を利用者は考察でき，fー耐故障分散アルゴリズムの理解に繋がる．さらに，本研究では，２つの実行の生成に必要な計算時間を削減する仕組みについて考察と実験を行なう．その結果，類似度の高い２つの実行を実用的な時間で生成できることを示す．An ｆ-resilient distributed algorithm solves a problem correctly if there are at most ｆ faulty processes in a system. In this paper, we propose a tool to support understanding of ｆ-resilient distributed algorithms. Our tool presents two similar executions of an algorithm: the one is an execution with ｆ +1 faults in which the algorithm cannot solve the problem, and the other is an execution with ｆ or ｆ + 1 faults in which the algorithm solves the problem. Users can easily understand the strategy for tolerating faults by comparing the executions. In addition, we present a method to reduce constructing time for the executions, and show by experiments that they are constructed in practical time.

センサネットワークの利用例の多くに、ある特定の領域の監視を行い、得られた情報を収集したいという要求がある。各センサの検知領域で監視を行いたい領域（要求領域）を被覆する連結なセンサの集合を連結センサカバーとよび、センサ数が最小の連結センサカバーを求めることは NP 困難であると知られている。分散環境において、少数のセンサで構成される連結センサカバーを求める手法が既に提案されているが、既存手法ではアルゴリズムを開始するのはただ１つのセンサであり、広大な要求領域に対し連結センサカバーを求めるには非常に長い時間を要する。そこで本研究では、分散環境において要求領域の被覆を複数センサで平行に行う手法を提案する。また実験により、提案手法を用いて短時間で十分に少ないセンサ数の連結センサカバーが得られることを示す。A connected sensor cover is extremely useful to monitor an area in sensor networks: a connected sensor cover is a sub set of connected sensors, which covers the area to be monitored with the sensors' sensing regions. It is known that the connected sensor cover problem, which requires to find a connected sensor cover with the smallest number of sensors, is NP-hard. A connected sensor cover algorithm was proposed. However, the larger the area to be monitored is, the more it takes to find a connected sensor cover since only one sensor starts the algorithm. Therefore, in this paper, we proposed an algorithm, in which multiple sensors concurrently elect sensors to be included in a connected sensor cover. We show by simulation that the proposed algorithm finds a connected sensor cover with small number of sensors within a sufficiently short time.

自己安定プロトコルは、任意の初期状況から実行を開始しても、いずれ正しい状況に収束するという性質を持ち、一時故障に対する耐性とネットワークトポロジ変化に対する適応性に優れている。しかし、自己安定プロトコルをモバイルアドホックネットワークのような環境に適用すると、正しい状況に収束する前にトポロジ変化が発生し、正しい状況に収束できない可能性がある。そのため、トポロジ変化へのより高度な対応が必要となっている。Chen ら [1] はモバイルアドホックネットワーク上での自己安定相互排除プロトコルを提案している。Chen らの手法はノードの移動によるトポロジ変化に対して優れた適応性を持つが、ノードの離脱によるトポロジ変化に対する適応性は十分ではない。本稿では Chen らの手法を改善し、ノードの移動、離脱の両方に対して優れた適応性を持つ自己安定相互排除プロトコルを提案する。A Self-stabilizing protocol converges to the desired behavior regardless of an arbitary initial configuration. Thus, a self-stabilizing protocol has strong fault tolerance. However, to apply self-stabilizing protocols in dynamic networks such as mobile ad hoc networks, it is necessary to highly adapt topology changes. Chen et. al. introduced a self-stabilizing mutual exclusion protocol for mobile ad hoc networks that is adaptive for node mobility. However, it has less adaptability for node departure [1]. In this paper we propose a self-stabilizing mutual exclusion protocol that improves adaptability for node departure of [1], and adaptability for node mobility and departure is evaluated by simulation.

本研究では,「誤りからの学習」に基づくアルゴリズム学習のための演習問題の自動生成手法を提案する.ここでの演習問題とは,あるアルゴリズムを実装したソースコードに誤りを含ませたものであり,誤りの修正及び考察を通じてアルゴリズムの理解を深める形式を想定している.演習問題の自動生成においては,演習を通じてアルゴリズムの理解を深められるような誤りの自動挿入を実現することを目標とし,これを実現するシステムを試作した.また,提案手法の評価として,教員等が学習効果を考えて挿入した誤りと提案手法で自動的に挿入される誤りを比較した結果,高い割合で学習効果のある誤りを自動挿入できていることがわかった.加えて,実際の講義において演習を実施した結果も報告する.

P2Pシステムにおいて資源の効率的な配置と検索を実現する手法として,分散ハッシュテーブル(DHT)がよく用いられている.DHTの故障耐性を高める方法としてマルチパスおよびワイドパスと呼ばれる経路の多重化がある.マルチパスは低コストで実現できるが故障耐性が十分でなく,ワイドパスは高い故障耐性を有する反面,高コストである.そこで本研究では,これらの手法を組み合わせた手法を提案し,DHTの一種であるChordに対して適用する.また,解析とシミュレーションによる性能評価を行い,提案手法では既存手法に比べて低コストで故障耐性が向上することを示す.