モバイルエージェントネットワークの拡張とシミュレーション

Presentation on theme: "モバイルエージェントネットワークの拡張とシミュレーション"— Presentation transcript:

1 モバイルエージェントネットワークの拡張とシミュレーション
大西　量 北海道工業大学

2 位置透過性を持つメッセージ通信 移動前のホストに移動先を通知 送信元はそのホストにメッセージを送信
ホストがメッセージを受け取って本来の通信相手が存在する移動先ホストに転送 Source Host 1 Host 2 Destination Message

3 問題点 どこか1箇所でも通信不能なホストがあるとメッセージは相手に届かない n次モバイルエージェントネットワーク によって解決 Source
Host 1 Host 2 Destination Message n次モバイルエージェントネットワーク によって解決

4 n次モバイルエージェントネットワーク 有限で単純な無閉路有向グラフG=(V, E) Vに属する頂点: ホスト Eに属する有向辺: リンク
単純グラフ：　平行辺を持たない 無閉路グラフ：　回路を持たない n: 許容できる通信不能なホストの数

5 n次モバイルエージェントネットワーク(2)
ターゲット: 外向きのリンクを持たないただ一つのホスト プロキシ: ターゲット以外のホスト k次プロキシ: 外向きのリンクの数がk個あるプロキシ 特殊プロキシ: k≦n であるk次プロキシ 正規プロキシ: 特殊プロキシでないプロキシ すべての特殊プロキシはターゲットを終点とするリンクを持つ

6 モバイルエージェントネットワークの例 (n=1) p s t 正規プロキシ 特殊プロキシ ターゲット

7 モバイルエージェントネットワークの信頼性
[定理] 互いに異なる任意のプロキシvとn個のプロキシw1・・・wnについて、どのw1・・・wnも通らないvからターゲットまでの経路が存在する t W3 W1 v W2

8 証明 vから以下のように適切な経路を辿る k本＞n 正規プロキシにいる間は終点がw1・・・wnのどれでもないリンクを辿る

9 証明(続き) いつかはターゲットか特殊プロキシにたどり着く 特殊プロキシに居るときはターゲットを終点とするリンクを辿る
ターゲットに居るのならば終了 t s 特殊プロキシ ターゲット

10 モバイルエージェントネットワーク書き換え系
モバイルエージェントネットワーク の動的変化を表現 4つの規則 新しいホストへの移動 特殊プロキシへの移動 正規プロキシへの移動 バイパス 発展 修復

11 規則1. 新しいホストへの移動 (V, E) → (V + {u}, E + {(t, u)}
規則1.　新しいホストへの移動 (V, E) → (V + {u}, E + {(t, u)} + {(s1, u), (s2, u), …, (si, u)}) s2 s1 t u s2 s1 t (n=2)

12 規則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 s1 t s2への移動(n=2)

13 規則3. 正規プロキシへの移動 (V, E) → (V, E ＼ {(u, x1), (u, x2), …, (u, xj)}
+ {(t, u)} + {(s1, u), (s2, u), …, (si, u)}) u s2 s1 t u s2 s1 t uへの移動(n=2)

14 規則4. バイパス v ≠ w のとき (V, E) → (V, E ＼ {(u, v)} + {(u, w)}) u v w u v w

15 モバイルエージェントネットワーク書き換え系 の健全性
[定理2] G0 → *G ならば、G はモバイルエージェントネットワークである。 t s 初期モバイルエージェントネットワークG0

16 証明 G0がモバイルエージェントネットワークであることは明白 Gがモバイルエージェントネットワーク かつ
G→G’ならば G’はモバイルエージェントネットワーク グラフの有限性、単純性、非循環性

17 モバイルエージェントネットワークの シミュレーション
n次モバイルエージェントネットワークを シミュレート 任意ホストに移動させ、メッセージを移動元から転送

18 モバイルエージェント ネットワークシミュレータ(1)

19 モバイルエージェント ネットワークシミュレータ(2)

20 おわりに モバイルエージェントネットワークの拡張 ネットワークの拡張による信頼性向上 ネットワーク書き換え系 書き換え系の健全性
シミュレート モバイルエージェントシステムに実装