近年，通信理論の分野でgossipプロトコルという通信手法が注目されている．これは情報伝達を確率的に行う手法のひとつであり，例えばアドホックネットワーク上でルーティングを行う際などに多く用いられる[1-4]．しかし，gossipプロトコルの性能評価に関する理論的な結果はあまり多くない．また，gossipプロトコルは単一のパケットを拡散する場合のみが陽に考慮されており，複数のパケットを同時に拡散させた場合に関する研究はなされていないなどの問題もある．

　そこで本研究では，複数の情報が拡散するという現象を調べるために，既存のgossipプロトコルを拡張し，同時に複数の情報を扱えるようにする．そしてその拡張されたgossipプロトコルにおける情報浸透確率などを解析し，その性質を調べていく．

Gossipプロトコル

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

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

　Floodingの欠点を改善しようという試みはすでにいくつかなされており[8,9]，その1つとしてgossipプロトコルが挙げられる．Gossipプロトコルとは，メッセージを受け取ったセンサは，通信可能な範囲にいるすべてのセンサに対して，一定の確率でメッセージを送信する手法である．Haas et al.[2]によれば，情報伝達率（メッセージを受け取ったノードの割合）は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]によってはじめて提唱された理論である．当初は多孔子の物質内を浸透していく流体のモデルとして研究されていたが，このモデルが強磁性体の相転移現象や電気伝導度を表現できることが判明するにつれ，次第に注目を浴びるようになった．近年では，森林火災の広がり方や病気の蔓延の様子，人やコンピュータの「つながり」を表現するモデルとしてしばしば用いられている[18,19]．

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

ボンド・サイトパーコレーション

　上で説明したサイトパーコレーションはグラフの頂点だけが確率的に変化したが，グラフの頂点だけでなく，枝もまた開もしくは閉という2つの状態をとり，開の状態では浸透するが，閉の状態では浸透しないというモデルを考えることもできる．このようなモデルはボンド・サイトパーコレーションと呼ばれる．このボンド・サイトパーコレーションは単純なパーコレーションの拡張にあたるモデルであり，主に2次元のグラフに対して研究が行われている．例えばHammersley[21]はボンド・サイトパーコレーションの浸透確率に関する不等式を導出している．ボンド・サイトパーコレーションの臨界曲線に関しては，その解析解は求まっていないものの，Yanuka et al.[22]により，実験値とよく一致する曲線が発見されており，その曲線はYanuka-Englman曲線と呼ばれている．また，Tarasevich et al.[23]では様々なグラフに対する臨界曲線の数値的な計算が行われている．ボンド・サイトパーコレーションの応用に関する研究もいくつか行われている[24-30]．

感染症の数理的モデル

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

　本研究の目的は，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... であることが数値的に知られているので[38,39]，この近似値は 0.02 ほどの誤差を持っていることがわかる．

　これまでのgossipプロトコルは，すべて単一のパケットを送信する場合しか陽に考慮されておらず，パケットが複数にわたる場合は考えられてこなかった．そこで，さらに複数のパケットを扱うことのできるgossipプロトコルについて考察する．これは例えば，ワイヤレスセンサネットワーク上においてセンサ同士が比較的短い時間間隔でビーコンをやりとりする場合や，大きな情報を複数の小さなパケットに分割する場合に相当する．

　複数のパケットを扱う場合，各時刻において，各センサの近傍から複数種のパケットが同時に送信されているケースが考えられるので，その場合のセンサの振る舞いを規定しなければならない．ここでは，センサの近傍から複数種のパケットが送信されている場合は，送信されているパケットのうちの1つを受信するものとし，受信するパケットは一様な確率で選択されるものとモデル化する．すなわち，各時刻において，センサが複数のパケットを同時に受信することはないものとする．また，パケットの発信源は原点のみとする．上で紹介したgossipプロトコルにこの規定を付加したものを，本研究では拡張gossipプロトコルと呼ぶことにする．また，以下では特にパケットが2種類の場合について考察する．

　次に，拡張gossipプロトコルの指標として，情報伝達率と臨界確率を導入する．情報伝達率は，パケットを受信することのできたノードの割合として定義し，臨界確率を，情報伝達率が正の値をとるしきい値として定義する．

　以上の問題設定のもとで，正方格子上における拡張されたgossipプロトコルの臨界確率がパケットを送信する時間間隔に対して単調増加であることを解析的に証明する．また，送信されるパケットの送信時間間隔が無限に離れているという特殊な場合における，情報伝達率の上界と下界を導出する．この上界と下界から，送信されるパケットの送信時間間隔が無限に離れているという場合においては，拡張gossipプロトコルの臨界確率は拡張される前の臨界確率と等しいということが直ちに導かれる．

　数学的証明では，臨界確率と送信時間間隔の間の単調性しか示せていないが，図 2に示す数値実験においては，臨界確率はほぼ等しい値をとっていることがわかる．

図 2: Numerical value of saturation with extended gossip protocol

　ここでは再び単一のパケットを送信する場合について考える．これまでは通信障害などによってパケットが失なわれることは考慮せず，通信は常に成功することを仮定してきた．そこで，ここでは通信障害を考慮した場合におけるgossipプロトコルについて考察する．今回は特に正方格子状に配置されたノード同士の通信が一定の確率 q で出来なくなるという状況下で，送信確率 q のgossipプロトコルを行った場合について取り扱う．

　以上の問題設定のもとで，通信障害を考慮したgossipプロトコルの情報伝達率の臨界曲線はボンド・サイトパーコレーションの浸透確率の臨界曲線と一致することを証明する．図 3は通信障害を考慮したgossipプロトコルの臨界曲線とYanuka-Englman曲線[22]をプロットしたものである．

図 3: Critical curve of gossip protocol

　今後は，送信時間と臨界確率の関係についてより詳細な条件が導出できるかどうかを検討する．また本研究では臨界現象を明確に表すためにパーコレーション理論を用いたが，それ以外の枠組みで臨界的な現象が再現でるかという点についても興味がある．また，情報浸透確率が0-1の性質を持つことから自己組織化との関連もあるのではないかと考えられるので，その方向性も検討してみたい．

[1] J. Yick, B. Mukherjee, and D. Ghosal, "Wireless sensor network survey," Comp. Networks, vol. 52, pp. 2292–2300, 2008.

[2] Z. Haas, J. Halpern, and L. Li, "Gossip-based ad hoc routing," IEEE/ACM Trans. Netw., vol. 14, pp. 479-491, 2006.

[3] D. Shah, "Network gossip algorithm," IEEE ICASSP, pp. 3673-3676, 2009.

[4] R. Korsnes, "Rapid self organised initiation of ad hoc sensor networks close above the percolation threshold," Physical Review A, pp. 2841-2848, 2010.

[5] 総務省 u-Japan政策 ホームページ (http://www.soumu.go.jp/menu_seisaku/ict/u-japan/).

[6] S. Verma, "Controlling gossip protocol infection pattern using adaptive fanout," Proc. IEEE International Conf. on Distributed Computing Systems, 2005.

[7] A. Kermarrec, L. Massoulie, and A. Ganesh, "Probabilistic reliable dissemination in large-scale systems," IEEE Trans. on Parallel and Distributed Systems, vol. 14, no. 3, pp. 248-258, 2003.

[8] Y. Tseng, S. Ni, Y. Chen, J. Sheu, "The broadcast storm problem in a mobile ad hoc network," Wireless Networks, vol. 8, pp. 153-167, 2002.

[9] B. Williams and T. Camp, "Comparision of broadcasting techniques for mobile ad hoc networks," MOBIHOC, pp. 194-205, 2002.

[10] R. Beraldi, "The polarized gossip protocol for path discoverly in MANETs," Ad Hoc Networks, vol. 6, pp. 79-91, 2008.

[11] Y. Sasson, D. Cavin, and A. Schiper, "Probabilistic broadcast for flooding in wireless mobile ad hoc networks," in Proc. IEEE WCNC, 2003.

[12] T. Huang, Y. Lin and L. Tang, "Neighbor-aware gossip-based broadcasting scheme for wireless sensor networks," IEEE Conf. Communications and Mobile Computing, pp. 293-297, 2010.

[13] M. Burmester, T. Le, and A. Yasinsac, "Adaptive gossip protocols: Managing security and redundancy in dense ad hoc networks," Ad Hoc Networks, vol. 5, pp. 313-323, 2007.

[14] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, "Randomized gossip algorithms," IEEE Tran. Information Theory, vol. 52, no. 6, pp. 2508-2530, 2006.

[15] G. Picci and T. Taylor, "Almost sure convergence of random gossip algorithms," IEEE Conf. Decision and Control, pp. 12-14, 2007.

[16] R. Galri, F. Fagnani and S. Zampieri, "Gossip consensus algorithms via quantized communication," Automatica, vol. 46, pp. 70-80, 2010.

[17] S. R. Broadbent and J. M. Hammersley, "Percolation process. I. Crystals and Mazes," in Proc. Cambridge Philos. Soc., vol. 53, pp. 629-641, 1957.

[18] D. Callaway, M. Newman, S, Strogatz and D. Watts, "Network robustness and fragility: percolation on random graph," Physical Review Letters, vol. 85, no. 25, pp. 5468-5471, 2000.

[19] Y. Moren, M. Nekovee and A. Pacheco, "Dynamics of rumor spreading in complex network," Physical Review E, vol. 69, 2004.

[20] H. Kesten, "The critical probability of bond percolation on the square lattice equals 1/2," Communications in Mathematical Physics, vol. 74, pp. 41-59, 1980.

[21] J. Hammersley, "A generalization of McDiarmid's theorem for mixed Bernoulli percolation," Mathematical Proceedings of the Cambridge Philosophical Society, vol. 88, pp. 167-170, 1980.

[22] M. Yanuka and R. Englman, "Bond-site percolation: empirical representation of critical probabilities," J. Phys. A: Math. Gen., vol. 23, pp. 399-345, 1990.

[23] Y. Tarasevich and S. Marck, "An investigation of site-bond percolation on many lattices," International Journal of Modern Phys. C, vol. 10, no. 71999, pp. 1193-1204, 1999.

[24] M. Yanuka, "The mixed bond-site percolation problem and its approximation to capillary phenomena in porous media," Journal of Colloid and Interface Science, vol. 134, no. 1, pp. 198-205, 1988.

[25] M. Ioannidis and I. Chatzis, "A mixed-percolation nodel of capillary hysteresis and entrapment in mercury prosimetry," Journal of Colloid and Interface Science, vol. 161, pp. 278-291, 1993.

[26] P. Agrawal, S. Redner, P. Reynolds and H. Stanley, "Site-bond percolation: a low-density series study of the uncorrelated limit," Journal of Phys. A: Math. and Gen., vol. 12, no. 11, pp. 2073-2085, 1979.

[27] M. Yanuka, "The mixed bond-site percolation problem and its application to capillary phenomena in prous media," Journal of Colloid and Interface Science, vol. 134, no. 1, 1990.

[28] H. Nakashini and P. Reynolds, "Site-bond percolation by position-space renormalization group," Physics Letters, vol. 71A, pp. 252-254, 1979.

[29] L. Chayes and R. Schonmann, "Mixed percolation as a bridge between site and bond percolation," The Ann. Appl. Prob., vol. 10, no. 4, pp. 1182-1196, 2000.

[30] B. Watson and P. Leath, "Conductivity in the two-dimensional-site percolation problem," Phys. Rev. B, vol. 9, no. 11, pp. 4893-4897, 1974.

[31] N. Ferguson, D. Cummings, C. Fraser, J. Cajka and P. Cooley, "Strategies for mitigating an infuluenza pandemic," Nature, vol. 442, pp. 448-452, 2006.

[32] S. Cauchemez, A.J. Valleron, P.Y. Boelle, A. Flahault and N.M. Ferguson, "Estimating the impact of school closure on influenza transmission from sentinel data," Nature, vol. 452, pp. 750-754, 2008.

[33] G. Pang and L. Chen, "A delayed SIRS epidemic model with pulse vaccination," Chaos, Solutions and Fractals, vol. 34, pp. 1629-1635, 2007.

[34] R. Durrett and D. Remenik, "Chaos in a spatial epidemic model," The Annals of Appliied Probability, vol. 19, no. 4, pp. 1656-1685, 2009.

[35] M. Nekovee, Y. Moreno, G. Bianconi and M. Marsili, "Theory of rumour spreading in complex social networks," Physica A, vol. 374, pp. 457-470, 2007.

[36] V. Isham, S. Harden and M. Nekovee, "Stochastic epidemic and rumours on finite random networks," Physica A, vol. 389, pp. 561-576, 2010.

[37] E. Lebensztayn, F. Machado and M. Rodriguez, "Limit theorems for a general stochastic rumour model," SIAM Journal on Applied Mathematics, 2011.

[38] B. Bollobas and O. Riordan, Percolation, Cambridge University Press, 2006.

[39] G. Grimmett, Percolation, Springer-Verlag, 1989.