外乱に対して安定な分散アルゴリズムの相互作用パターン

点击翻译按钮获取中文摘要

本研究は，自己安定の概念を基礎におき大規模な分散システムを対象として，ネットワーク変動に対する高度な自律性と適応性を実現する分散アルゴリズムの基礎理論に関するものである．特に分散システム内のノードは対等で，集中制御を行う特別なノードが無く，ノード総数が極めて膨大である分散システムを主な研究の対象とする．現在，無線ワイヤレスセンサネットワークではひとつのシステムにおいては数十程度の規模であるが，本研究の目的は，このような限定的なノード数を大きく越えて，大規模数のノードが対等に相互作用する自律的な分散システムの設計技法の確立を目指して研究を進めている．2022年度は主に，(1) マイナス支配集合問題の一般化，および，(2) 2-極小支配集合問題について，これらの問題に対する自己安定分散アルゴリズムの開発に取り組んで幾つかの成果を上げ，国際会議で発表を行った.マイナス支配集合問題の一般化に関する研究では，すでに知られているマイナス支配集合問題に対してマイナス(L,K,Z)支配集合問題という一般化の提案を行った．2-極小支配集合問題に関する研究では，準最適解である極小支配集合に対して準最適性を改善した2-極小支配集合を提案した．具体的には，支配集合に含まれる2つの頂点を除外し，新たに1つの頂点を追加する操作により，支配集合のサイズが減少できない場合を2-極小性と定めた．この2-極小性は準最適解ではあるものの，分散システムにおける局所的な情報交換で実現できることから，通信コストを抑えつつ解の改善を行うという点で応用上の観点から興味深い問題設定である．