近年，人やコンピュータのつながり方を表す手段としてパーコレーション理論が注目を浴びている．パーコレーション理論とは，多孔子の物体を浸透(percolate)していく流体の挙動を確率的現象としてモデル化し，その解析を行うことから始まった理論である．現在，パーコレーション理論は確率論的に定式化され，様々な数学的結果が得られている[1,2]ものの，未だに解決されていない問題も少なくない．一方，通信理論の分野にgossipプロトコルというものがある．これは情報伝達を確率的に行う手法のひとつであり，例えばアドホックネットワーク上でルーティングを行う際などに多く用いられる[3,4]．

　本研究の目的は，gossipプロトコルとサイトパーコレーションの関係を明かにし，サイトパーコレーションの問題をgossipプロトコルの観点から検討することである．

Gossipプロトコル

　近年，身の回りのあらゆる物を有線あるいは無線のネットワークでつなぐことで様々なサービスや利便性を提供し，人々の生活を豊かにしようという試みが多くある．日本ではu-Japan政策[5]などが有名である．それらの試みの中でも特に，近年におけるコンピュータやセンサの小型化，それらに搭載する電源の性能の向上などとも相まって，アクセスポイントなどを介さず直接通信するネットワーク，すなわちアドホックネットワークが注目を集めている．アドホックネットワーク上での情報伝達をいかに効率化するかが実用上重要な課題となっており，様々な研究がなされている[6,7]．

　アドホックなネットワーク上でメッセージをやりとりする方法はいくつか提案されているが，その代表的な手法のひとつにFloodingがある[3]．Floodingとは，メッセージを受け取ったセンサは，送信可能な範囲にあるすべてのセンサに対してメッセージを送る手法である．この手法は，グラフ構造が動的に変化するネットワークに対しても確実に目的のセンサにデータを送ることができるといったロバスト性をもつ．その一方で，Floodingを用いた場合，ネットワークの構造によっては不要なメッセージのやりとりが大量に発生し，通信帯域幅を圧迫してしまうという欠点も持っている．この現象はブロードキャストストームと呼ばれ，特にセンサが密に存在するネットワーク上では深刻な問題となっている．

　Floodingの欠点を改善しようという試みはすでにいくつかなされており[8,9]，その1つとしてgossipプロトコルが挙げられる．gossipプロトコルとは，メッセージを受け取ったセンサは，通信可能な範囲にいるすべてのセンサに対して，一定の確率でメッセージを送信する手法である．Haas et al.[4]によれば，情報伝達率（メッセージを受け取ったノードの割合）は2峰的な性質を持つことが実験的に示されている．すなわち，ほとんどすべてのセンサがメッセージを受けとるか，あるいはほとんどすべてのセンサがメッセージを受け取れないかのいずれかになるという性質である．これは対象とするネットワークが大きい場合に特に顕著である．

　このgossipプロトコルを応用したものもいくつか提案されている．例えばBeraldi[10]やSasson et al.[11]，Huang et al.[12]などの研究がそれであり，情報伝達の更なる効率化を図っている．また，ビザンチン攻撃などに代表されるアドホックネットワーク特有の脆弱性に対する研究もBurmester et al.[13]によって行われている．また，コンセンサス問題，すなわち個々のノードの持つ量を自律分散的なアルゴリズムによって一定の値に収束させる問題を，gossipプロトコルを用いて解決しようという試みもある[14,15]．文献[16]は，[14]の状況設定のもとで，通信による情報の量子化が起こりうる場合も想定し，解析を行っている．

パーコレーション理論

　パーコレーション理論はBroadbent et al.[17]によってはじめて提唱された理論である．当初は多孔子の物質内を浸透していく流体のモデルとして研究されていたが，このモデルが強磁性体の相転移現象や電気伝導度を表現できることが判明するにつれ，次第に注目を浴びるようになった．近年では，森林火災の広がり方や病気の蔓延の様子，人やコンピュータの「つながり」を表現するモデルとしてしばしば用いられている．

　用語の準備のために，パーコレーションの数学モデルについて簡単に紹介したい．ここでは特にサイトパーコレーションについて説明する．まずはグラフ G を考える．グラフ G 上の頂点を各々独立に一定の確率 p で選択する操作を行う．選択された頂点を開いた頂点といい，開いた頂点のみで構成される連結成分を開クラスターと呼ぶ．原点を含むクラスターのサイズが無限大になる確率は，ある値をしきいとして正の値をとることが知られており，このしきい値を臨界確率と呼ぶ．一般に臨界確率はグラフ G によって異なる値をとることが知られており，臨界確率を求めることに多くの努力が費やされている．現在では臨界確率は数値的に精度よく計算されているものの，多くのグラフに対して，その厳密な値は知られていない．

感染症の数理的モデル

　gossipプロトコルのような情報拡散は感染症の蔓延と多くの類似点を持っていると考えられるため，感染症に関する先行研究もいくつか挙げておきたい．感染症の数理的解析は1930年頃から行われており，現在でも盛んに研究が行われている．近年では，より実社会に近いといわれている複雑ネットワーク上での解析が注目を浴びており，文献[18,19]では感染症蔓延予防策の効果を複雑ネットワーク上において数値的に評価している．また，Durrett et al.[20]は空間的な感染症のモデルに平均場近時を施すことにより，Chaos現象が発生することを示している．

　本研究の目的は，gossipプロトコルとサイトパーコレーションの関係を明かにし，サイトパーコレーションの問題をgossipプロトコルの観点から検討することである．そこでまず，各ノードに状態を割り当てることでgossipプロトコルを確率過程として記述する．そして，gossipプロトコルの情報伝達率を，パケットを受信できたノードの割合として定義し，さらにgossipプロトコルの臨界確率を，gossipプロトコルの情報伝達率が正の値をとるしきい値として定義する．情報伝達率や臨界確率はgossipプロトコルの性能を図る指標と見なすこともできる．

　そして，正方格子上のサイトパーコレーションの臨界確率と正方格子上のgossipプロトコルの臨界確率が等しいことを解析的に証明する．この証明は，正方格子に限らず，ほとんどの格子（厳密には，無限開クラスターの唯一性が保証されるグラフ）に対して同様に成立する．

　次に，ノードの割合に関するダイナミクスを近似的に導き，gossipプロトコルの情報伝達率を近似的に解析することで，臨界確率の近似値を導出する．図1の青線が近似された情報伝達率の値であり，赤線は十分大きな正方格子上でのシミュレーション値である．

図1 : Approximation value of saturation

　この近似によれば，gossipプロトコルの臨界確率は ( sqrt(2) - 1 ) / 2 = 0.618... となる．さきに，正方格子状のサイトパーコレーションの臨界確率と正方格子状のgossipプロトコルの臨界確率が等しいことを証明したので， ( sqrt(2) - 1 ) / 2 = 0.618... はサイトパーコレーションの臨界確率の近似値でもあると言える．しかし，正方格子上のサイトパーコレーションの臨界確率はおよそ 0.592... であることが数値的に知られているので[1,2]，この近似値は 0.02 ほどの誤差を持っていることがわかる．

　今後の目標は，情報伝達率の近似を改善することである．また，本研究の手法にField TheoryやMarkov Random Fieldの考え方を適用することによって，正方格子上のサイトパーコレーションの臨界確率の導出も試みたい．