モバイルエージェントネットワークの拡張とシミュレーション大西量北海道工業大学位置透過性を持つメッセージ通信    移動前のホストに移動先を通知送信元はそのホストにメッセージを送信ホストがメッセージを受け取って本来の通信相手が存在する移動先ホストに転送 Message Source Message Host 1 Message Host 2 Destination 問題点  どこか1箇所でも通信不能なホストがあるとメッセージは相手に届かない Message Source Message Host 1 Host 2 Destination n次モバイルエージェントネットワークによって解決 n次モバイルエージェントネットワーク   有限で単純な無閉路有向グラフG=(V, E)  Vに属する頂点: ホスト  Eに属する有向辺: リンク  単純グラフ：平行辺を持たない  無閉路グラフ：回路を持たない n: 許容できる通信不能なホストの数 n次モバイルエージェントネットワーク(2)       ターゲット: 外向きのリンクを持たないただ一つのホストプロキシ: ターゲット以外のホスト k次プロキシ: 外向きのリンクの数がk個あるプロキシ特殊プロキシ: k≦n であるk次プロキシ正規プロキシ: 特殊プロキシでないプロキシすべての特殊プロキシはターゲットを終点とするリンクを持つモバイルエージェントネットワークの例 (n=1) p p 正規プロキシ s t 特殊プロキシターゲットモバイルエージェントネットワークの信頼性 [定理] 互いに異なる任意のプロキシvとn個のプロキシw1・・・wnについて、どのw1・・・ wnも通らないvからターゲットまでの経路が存在する W1 t W2 v W3 証明  vから以下のように適切な経路を辿る   正規プロキシにいる間は終点がw1・・・wnのどれでもないリンクを辿るこの方法ではw1・・・wnにたどり着くことは絶対にあり得ない k本＞n 正規プロキシ証明(続き)    いつかはターゲットか特殊プロキシにたどり着く特殊プロキシに居るときはターゲットを終点とするリンクを辿るターゲットに居るのならば終了 s 特殊プロキシ t ターゲットモバイルエージェントネットワーク書き換え系   モバイルエージェントネットワークの動的変化を表現 4つの規則  新しいホストへの移動発展  特殊プロキシへの移動  正規プロキシへの移動修復  バイパス規則1. 新しいホストへの移動 (V, E) → (V + {u}, E + {(t, u)} + {(s1, u), (s2, u), …, (si, u)}) s2 s1 t u (n=2) 規則2. 特殊プロキシへの移動 (V, E) → (V, E ＼ {{(sk, s1), (sk, s2), …, (sk, sk-1)} + {(sk, t)}} + {(s1, sk), (s2, sk), …, (sk-1, sk)} + {(t, sk)}) s2 s1 t s2への移動(n=2) 規則3. 正規プロキシへの移動 (V, E) → (V, E ＼ {(u, x1), (u, x2), …, (u, xj)} + {(t, u)} + {(s1, u), (s2, u), …, (si, u)}) uu s2 s1 t uへの移動(n=2) 規則4. バイパス v ≠ w のとき (V, E) → (V, E ＼ {(u, v)} + {(u, w)}) u v w モバイルエージェントネットワーク書き換え系の健全性 [定理2] G0 → *G ならば、G はモバイルエージェントネットワークである。 s t 初期モバイルエージェントネットワークG0 証明    G0がモバイルエージェントネットワークであることは明白 Gがモバイルエージェントネットワークかつ G→G’ならば G’はモバイルエージェントネットワークグラフの有限性、単純性、非循環性モバイルエージェントネットワークのシミュレーション   n次モバイルエージェントネットワークをシミュレート任意ホストに移動させ、メッセージを移動元から転送モバイルエージェントネットワークシミュレータ(1) モバイルエージェントネットワークシミュレータ(2) おわりに       モバイルエージェントネットワークの拡張ネットワークの拡張による信頼性向上ネットワーク書き換え系書き換え系の健全性シミュレートモバイルエージェントシステムに実装