グラフ理論を用いたマルチホップ無線ネットワークの最適化法

摘要

複数の無線局を中継するマルチホップ無線ネットワークにおいて，経路構築·周波数割当·クラスタリングは重要な課題である．従来さまざまなアルゴリズムが提案されているが，計算機シミュレーションによる検討によるものが大部分を占めており，理論的な検討はほとんどされていないのが現状である．そこで本稿では，グラフ理論を用いて最適化の検討を行う．行列の縮退，チャネル割り当てリストの縮退，無線リンク間の特定の干渉パターンの除外により演算量を削減し，評価関数として各無線局が同時に受信できる最大スループットを用いることで，容易に最適解を導出できることを示す．