無線分散計算機ネットワーク上の高速通信アルゴリズムに関する研究

研究実績の概要は以下の通りである。1.無線ネットワーク上の周波数割当問題をネットワーク上の資源割当問題として定式化し、その計算複雑さについてあきらかにした。特に、与えられたネットワークの各ノードの次数が3に制限されたようなネットワーク(cubic graph)上での割当問題について深く考察し、各ノードに割り当てることのできる周波数を1からmに増加させることにより、各周波数がすべてのノードをカバーするという制約のもとで使用可能な周波数の種類が、mに関して超線形に増加することをあきらかにした(この結果については学術論文誌に投稿中)。2.無線ネットワークは、各送信ノードが複数の受信ノードに単位時間で情報を散布できるという観点から、一種のバスネットワークであるとみなすことができる。我々は各バスに接続されているノード数(無線ネットワークにおける各ノードの次数)が高々l(≧1)であるような(完全結合された)バスネットワークに着目し、そのようなネットワーク上での効率的な全対全通信(gossip)アルゴリズムを開発した(研究発表論文1)。3.無線ネットワークにける情報共有方式を提案した(研究発表論文2)。提案方式では、構成要素(ネットワークのノード)が動的に変化するような集合の共有を無線ネットワーク上でより少ないメッセージのやりとりで実現することができる。提案方式の基本的なアイデアは、共有される情報を連結リスト構造を用いて分散的に保持し、共有情報への各アクセスごとに連結リストの圧縮(path compression)をおこなうことである。提案方式のメッセージ複雑さは、ならし計算量によって評価されている。

研究実績の概要は以下の通りである。1.無線ネットワーク上の周波数割当問題をネットワーク上の資源割当問題として定式化し、その計算複雑さについてあきらかにした。特に、与えられたネットワークの各ノードの次数が3に制限されたようなネットワーク(cubic graph)上での割当問題について深く考察し、各ノードに割り当てることのできる周波数を1からmに増加させることにより、各周波数がすべてのノードをカバーするという制約のもとで使用可能な周波数の種類が、mに関して超線形に増加することをあきらかにした(この結果については学術論文誌に投稿中)。2.無線ネットワークは、各送信ノードが複数の受信ノードに単位時間で情報を散布できるという観点から、一種のバスネットワークであるとみなすことができる。我々は各バスに接続されているノード数(無線ネットワークにおける各ノードの次数)が高々l(≧1)であるような(完全結合された)バスネットワークに着目し、そのようなネットワーク上での効率的な全対全通信(gossip)アルゴリズムを開発した(研究発表論文1)。3.無線ネットワークにける情報共有方式を提案した(研究発表論文2)。提案方式では、構成要素(ネットワークのノード)が動的に変化するような集合の共有を無線ネットワーク上でより少ないメッセージのやりとりで実現することができる。提案方式の基本的なアイデアは、共有される情報を連結リスト構造を用いて分散的に保持し、共有情報への各アクセスごとに連結リストの圧縮(path compression)をおこなうことである。提案方式のメッセージ複雑さは、ならし計算量によって評価されている。