導入
自己安定化、または自己安定化は、相互に通信できる複数のマシンで構成される分散システムの特性であり、システムが誤って初期化されたり障害が発生したりした場合に、終了した数の正しい動作に自動的に戻ります。計算手順。自己安定化は、1974 年にEdsger Dijkstraによって定義されました。基本的に理論コンピューター科学で分析された自己安定化は、障害後にシステムを復元するための人間の介入が不可能な領域、または「パスすることが望ましい領域」での応用を目的としています。センサー ネットワークや衛星などの重要なシステム。
考えられる応用例: センサーネットワーク
ワイヤレス センサー ネットワークは、小型の自律マシン、センサーのセットです。各センサーには、マイクロプロセッサー、少量のRAM 、バッテリー、無線トランシーバー、および 1 つ以上の測定器(温度計、湿度計など) が含まれています。このようなネットワークの目標は、個々のセンサーによって行われた測定値を自動的にまとめて、全体的な結果を導き出すことです。アプリケーションの中には、森林にセンサー ネットワークを導入して火災が発生した場合に警告したり、紛争地域に導入して敵の存在を検出したり、ビオトープに導入して動物に迷惑をかけずに観察したりすることができます。センサーは初歩的なプロセッサーに限定されているため、その計算能力には限界があります。さらに、無線通信の範囲が広がるにつれてバッテリーが減り、エネルギー消費が増加するため、通信距離が制限されます。実際、センサーは主にアクセスが難しい場所で使用されるため、バッテリーを交換するためにセンサーを作業することは通常は計画されていません。一般に、センサーからの情報は、より優れた計算能力と送信能力を持つ基地局 (反対の図) によって復元されます。一般に、センサーは固定されています。センサーは特定の場所に設置され、移動することはできません。
センサーのネットワークが有用であるためには、自律的である必要があります。センサーは、介入を必要とせずに情報を交換し、処理を実行する必要があります。ただし、多数のシステム障害が発生する可能性があります。たとえば、センサーが故障したり、新しいセンサーがそのエリアに配備されたりする可能性があります。自己安定化は、センサー ネットワークがこれらの外乱から自動的に回復することを保証するソリューションの 1 つです。
自己安定化アルゴリズムは、センサー ネットワークに特有の基本的な問題、特に時間多重化(センサーはそのうちの 1 つだけが送信するスロットについて合意する)、指向性ブロードキャスト通信(センサー ネットワークに適したルーティング方法)、および次の事実にもかかわらず動作を解決できます。一部のセンサーはネットワークの残りの部分から定期的に切断される場合があります。同様に、センサー ネットワークに適応した自己安定化ソリューションは、グラフの色付け、最大安定値またはスパニングツリーの計算、さらにはクロック同期などの古典的な問題に対しても存在します。
移動可能なエージェントにセンサーを配置するモバイルセンサー ネットワークもあります。これは、ビオトープではなく動物自体にセンサーを設置することで、野生動物の行動を妨げることなく観察する新しい方法を提供します。システム内に存在するセンサーの数を決定することからなる自己安定計数問題を解決するための必要十分条件が、このフレームワークで確立されました。この問題は、別々に定式化されたポピュレーション プロトコルの問題に加わります。この問題は、システムを、ランダムに移動し、出会ったときに情報を交換できる、メモリが非常に限られたエージェントのセットとして考えることから構成されます。