トポロジ制御は、分散コンピューティングにおいて用いられる手法であり、基盤となるネットワーク（グラフとしてモデル化）を変更することで、生成されたグラフ上で分散アルゴリズムを実行する際のコストを削減します。これは分散アルゴリズムにおける基本的な手法です。例えば、（最小）全域木をバックボーンとして用いることで、ブロードキャストのコストをO(m)からO(n)に削減できます。ここで、mとnはそれぞれグラフ内の辺の数と頂点の数です。
「トポロジー制御」という用語は、主に無線アドホックネットワークやセンサーネットワークの研究コミュニティで使用されています。この分野におけるトポロジー制御の主な目的は、エネルギーの節約、ノード間の干渉の低減、そしてネットワークの寿命の延長です。しかし、最近では電力システムのネットワーク構造の制御に関しても、この用語が注目を集めています。
トポロジの構築と保守
最近、トポロジ制御アルゴリズムは、初期の削減を担当するトポロジ構築と、接続性やカバレッジなどの特性が保持されるように削減されたトポロジの維持を担当するトポロジ維持という 2 つのサブ問題に分割されています。
これはトポロジ制御プロトコルの第一段階です。初期トポロジが展開されると、特にノードの配置がランダムな場合、管理者はネットワークの設計を制御できなくなります。例えば、一部のエリアは非常に高密度で、冗長ノードが多数存在する場合、メッセージの衝突回数が増加し、同様の位置にあるノードから同じ情報が複数コピーされる可能性があります。ただし、管理者はネットワークのいくつかのパラメータ、例えばノードの送信電力、ノードの状態（アクティブまたはスリープ）、ノードの役割（クラスタヘッド、ゲートウェイ、通常）などを制御できます。これらのパラメータを変更することで、ネットワークのトポロジを変更できます。
トポロジが縮小され、ネットワークが本来の目的を果たし始めると同時に、選択されたノードはエネルギーを消費し始めます。縮小されたトポロジは、ネットワークアクティビティがフル稼働するとすぐに「最適性」を失い始めます。アクティブになってからしばらく経つと、一部のノードはエネルギー不足に陥り始めます。特に、マルチホップの無線センサーネットワークでは、集中的なパケット転送により、シンクに近いノードは遠いノードよりも多くのエネルギーを消費します。接続性、カバレッジ、密度などの望ましい特性を維持するために、トポロジ制御を定期的に実行する必要があります。
トポロジ構築アルゴリズム
トポロジ構築を実行する方法は多数あります。
- 展開フェーズにおけるノードの位置の最適化
- ノードの送信範囲を変更する
- ネットワークからノードをオフにする
- コミュニケーションのバックボーンを構築する
- クラスタリング
- 接続性を維持するためにネットワークに新しいノードを追加する（フェデレーテッドワイヤレスセンサーネットワーク）
トポロジ構築アルゴリズムの例をいくつか示します。
送信範囲ベース
- 幾何学ベース:ガブリエルグラフ(GG)、相対近傍グラフ(RNG)、ボロノイ図
- スパニングツリーベース: LMST、[1] iMST [2]
- 方向ベース: ヤオグラフと最近傍グラフ、円錐ベーストポロジー制御 (CBTC)、分散RNG
- 近隣ベース：KNeigh、[3] XTC [4]
- ルーティングベース：COMPOW [5]
階層的
- CDSベース：A3、[6] EECDS、[7] CDSルールK [8]
- クラスターベース：低エネルギー適応型クラスタリング階層（LEACH）、HEED [9]
グラフィック例
-
フルパワーネットワークトポロジ -
最小スパニングツリーによるネットワークトポロジの縮小（送信範囲の変更）
-
接続された支配セットによるネットワークトポロジの縮小（ネットワーク全体をカバーするノードのサブセットを選択し、選択されていないノードをオフにする）
トポロジ維持アルゴリズム
トポロジ構築と同じように、トポロジメンテナンスを実行する方法は多数あります。
- グローバル vs. ローカル
- ダイナミック vs. スタティック vs. ハイブリッド
- 時間、エネルギー、密度、ランダムなどによってトリガーされます。
トポロジ維持アルゴリズムの例は次のとおりです。
グローバル
- DGTRec (動的グローバルトポロジー再作成) :
定期的に、すべての非アクティブなノードを起動し、ネットワーク内の既存の縮小されたトポロジをリセットし、トポロジ構築プロトコルを適用します。
- SGTRot (静的グローバルトポロジー回転) :
トポロジ構築プロトコルは、まず複数の縮約トポロジ（できれば可能な限り互いに独立なもの）を作成する必要があります。その後、定期的にすべての非アクティブなノードを起動し、クリスマスツリーのように、現在アクティブな縮約トポロジを次のトポロジに変更します。
- HGTRotRec (ハイブリッドグローバルトポロジーの回転と再現)
SGTRot として機能しますが、現在アクティブな縮小トポロジが特定のレベルの切断を検出すると、縮小トポロジをリセットし、トポロジ構築プロトコルを呼び出して、その特定の縮小トポロジを再作成します。
地元
- DL-DSR（ダイナミックローカルDSRベースTM）
このプロトコルは、動的ソース ルーティング(DSR) ルーティング アルゴリズムに基づいており、ノードに障害が発生した場合に切断されたノードのパスを再作成します。
上記のプロトコルはすべて[10]で見つけることができます。Atarraya [11]では、これらのプロトコルそれぞれに異なるトリガーを持つ2つのバージョンが実装されています。1つは時間、もう1つはエネルギーです。さらに、Atarrayaでは、すべてのトポロジ構築プロトコルとトポロジ維持プロトコルを組み合わせて、特定の構築プロトコルに最適な維持ポリシーをテストすることができます。ただし、トポロジ構築に関する多くの論文では、この点について全く研究が行われていないことに注意が必要です。
さらに読む
このテーマについては多くの書籍や論文が書かれています。
- 無線センサーネットワークのトポロジー制御。ACM MobiCom 2003。[12]
- 無線センサーネットワークにおけるトポロジー制御：教育・研究のためのコンパニオンシミュレーションツール付き。ミゲル・ラブラドール、ペドロ・ワイトマン著。シュプリンガー、2009年。[10]
- 無線アドホックネットワークとセンサーネットワークにおけるトポロジー制御. パオロ・サンティ. Wiley. 2005. [13]
- 無線センサーネットワークのためのプロトコルとアーキテクチャ. ホルガー・カールとアンドレアス・ウィリグ. ワイリー・インターサイエンス. 2007. [14]
- 協力通信を用いたMANETの容量最適化トポロジー制御。2011年。[15]
- 屋内ワイヤレスセンサーネットワークの堅牢なトポロジ制御。2008 年。
トポロジー制御のシミュレーション
ネットワークシミュレーションツールは数多く存在しますが、トポロジ制御アルゴリズムのテスト、設計、教育に特化して設計されたツールがAtarrayaです。[11]
Atarrayaは、Javaで開発されたイベント駆動型シミュレータであり、トポロジ制御アルゴリズムの設計とテストのための新しいフレームワークを提供します。オープンソースアプリケーションであり、GNU V.3ライセンスの下で配布されています。開発は、サウスフロリダ大学の博士課程学生であるPedro Wightman氏とMiguel Labrador博士の共同研究によるものです。このシミュレータの詳細な説明を含む論文がSIMUTools 2009で発表されました。論文はこちらのリンクからご覧いただけます。
参考文献
- ^ [1]、局所最小全域木
- ^ [2]、反復最小全域木
- ^ [3] [永久リンク切れ]、KNEIGH
- ^ 「アーカイブコピー」（PDF） 。 2007年7月5日時点のオリジナル（PDF）からアーカイブ。2009年4月30日閲覧。
{{cite web}}: CS1 maint: アーカイブされたコピーをタイトルとして (リンク)、XTC - ^ [4], COMPOW, Hi
- ^ [5]、A3: WSNのためのトポロジ構築プロトコル
- ^ [6]、EECD
- ^ [7]、CDSルールK
- ^ [8]、注意
- ^ ab トポロジー制御、ラブラドールおよびワイトマン著、「無線センサーネットワークにおけるトポロジー制御」
- ^ ab [9]、Atarraya、無線センサーネットワークのトポロジー制御シミュレータ
- ^ J. Pan、Y. Hou、L. Cai、Y. Shi、および X. Shen、「ワイヤレス センサー ネットワークのトポロジ制御」、Proc. ACM Int'l Conf. on Mobile Comp. and Netw. (MobiCom'03)、pp. 286--299、サンディエゴ、カリフォルニア州、米国、2003 年 9 月 14 ～ 19 日。
- ^ トポロジー制御、Santi著、無線アドホックおよびセンサーネットワークにおけるトポロジー制御
- ^ ホルガー・カールとアンドレアス・ウィリグ著『無線センサーネットワークのプロトコルとアーキテクチャ』
- ^ Q. Guan、FR Yu、S. Jiang、VCM Leung、「協調通信を備えたMANETの容量最適化トポロジー制御」、IEEE Trans. Wireless Comm.、vol. 10、no. 7、pp. 2162-2170、2011年7月。