無線ネットワークモデル上の省電力アルゴリズムの研究

無線ネットワーク上で、さまざまな省電力を目指した基本通信アルゴリズムの開発を行った。また、計算機シミュレーションにより、厳密な性能の解析を行った。例えば、次のような成果を得た。1.複数のIDを持たないステーションがn台ネットワーク上に存在する状況を考える。ステーションはIDだけでなく、台数nも知らない。この場合、各ステーションが勝手に送信すると、電波の混信のため、正しい通信が行えない。そこで、通信を行いたいステーションの中から、1台を選ぶ必要がある。これはリーダ選択と呼ばれる。本研究では、n台のステーションからリーダを確率1-1/fで選ぶO(loglog n+log f)時間のアルゴリズムを示した。これは、従来のO(loglog n+√f)時間のアルゴリズムに比べて大幅な改善である。また、シミュレーションでは、従来のアルゴリズムは、最悪1600ステップ動作する場合があったが、本研究のアルゴリズムは、高々60ステップであった。2.同様の状況において、全ステーションに1からnの通し番号を与えるアルゴリズムを開発した。このアルゴリズムは、高い確率で、O(n)時間で終了する。また、各ステーションは、高々O(loglog n)回しか送受信を行わない。送受信が最も電力を消費するので、それを最小化した本アルゴリズムは、省電力であるといえる。これら以外にも、無線ネットワーク上のさまざまなアルゴリズムを提案し、シミュレーションによる性能評価を行った。

無線ネットワーク上で、さまざまな省電力を目指した基本通信アルゴリズムの開発を行った。また、計算機シミュレーションにより、厳密な性能の解析を行った。例えば、次のような成果を得た。1.複数のIDを持たないステーションがn台ネットワーク上に存在する状況を考える。ステーションはIDだけでなく、台数nも知らない。この場合、各ステーションが勝手に送信すると、電波の混信のため、正しい通信が行えない。そこで、通信を行いたいステーションの中から、1台を選ぶ必要がある。これはリーダ選択と呼ばれる。本研究では、n台のステーションからリーダを確率1-1/fで選ぶO(loglog n+log f)時間のアルゴリズムを示した。これは、従来のO(loglog n+√f)時間のアルゴリズムに比べて大幅な改善である。また、シミュレーションでは、従来のアルゴリズムは、最悪1600ステップ動作する場合があったが、本研究のアルゴリズムは、高々60ステップであった。2.同様の状況において、全ステーションに1からnの通し番号を与えるアルゴリズムを開発した。このアルゴリズムは、高い確率で、O(n)時間で終了する。また、各ステーションは、高々O(loglog n)回しか送受信を行わない。送受信が最も電力を消費するので、それを最小化した本アルゴリズムは、省電力であるといえる。これら以外にも、無線ネットワーク上のさまざまなアルゴリズムを提案し、シミュレーションによる性能評価を行った。