RaWMS - Random Walk based Lightweight Membership Service for Wireless Ad Hoc Networks Ziv Bar-Yossef (Department of Electrical Engineering Technion - Israel Institute of Technology) Roy Friedman, Gabriel Kliot (Computer Science Department Technion - Israel Institute of Technology) ABSTRACT RaWMSはMANET向け、軽量なメンバー管理機構 RaWMSは Reverse Random Walk モデルに基づく評価として、従来のフラッディングモデルやゴシップモデルと比較 1. INTRODUCTION Membership service は重要アドホックネットワークでも利用したい   だが、通常のLANと同様にはいかない完全な情報は要らないこの研究による貢献  RaWMS      ビュー（取得するリストの一部）の均一のランダムさ負荷が低い各ノードは任意のサイズのビューを取得可能分割される可能性が低い分割されても自己再生 2. SYSTEM MODEL グラフ理論に基づくこれ以降で用いる定義    v: 各ノード rv: 各ノードの無線送信可能範囲 G = (V, E)  G: グラフ全体  V: ノード全体  E: 各ノード同士の接続  Gd (n, r)  d: 次元 3. RANDOM WALK TECHNIQUES Simple random walks     G = (V, E) :無向グラフ dv: 頂点次数 n = |V| P: 確率的遷移行列 n×n  Pv, u = 1/dv  π:Pにおける静止分散 πP= π RW-based sampling たとえば sample(p, T) の場合    RWをpから開始 Tステップ分RWをする終了したノードが結果を返す定義   t秒後の分散 Tmix：完了時間 The Maximum Degree RW 非正規グラフGを正規グラフG’に変換     最大次数Dを探し、各頂点にD-dvのループをつけて、グラフを正規化する Tactual_mix: ステップ数（ループを除く） Dを大きく見積もると多少の時間ロスに P：マトリクス Random walks on ad hoc network   MANET はRGG (Random Geometric Graphs)にモデル化できる G2(n, r)  無向  接続性   Cは定数 r <= 1/2  大きすぎるとダメ 0<αd<1とすると   n, αのみで dadv, dmax, dmin を算出できる例えばC=1, αd=0.1とすると、dadv=0.9 Mixing Time  Suppose r >= 1/2, n>=10 3.1 Reverse RW-based uniform sampling in ad hoc networks Random Walk 結果をdst u がsrc vに返すと、結果を返すのがオーバヘッドそこで、 Reverse Sampleing Technique dst u のRandom Walk の結果を、src v の結果とする 4. RANDOM WALK BASED MEMBERSHIP SERVICE <NodeIdentifier, LastTime>   NodeIdentifier: 各vの識別子 LastTime: uから最後に“聞いた”時刻プロトコルは2スレッドで成り立つ   ΔごとにRWするスレッド Incoming messageを処理するスレッド discardExpriredFrom View(View, Timeout) discardOldestFromVi ew(View) refreshInView(View, addr) storeInView(View, addr) pickNextNode() 実装イメージ 4.1 Formal Performance analysis Convergence Time  ビュー取得までのプロトコルステップ数 Convergence Period  終了時刻 The average value of r(n)  ボールを投げるとランダムにどれかのビンに入る。N本のビンに少なくとも一つはボールが入るようにするには、いくつボールを投げればよいか？ 4.2 Service properties ビューの均一性  均一にランダムなビューを取得できる Knowledge graph の接続   分割の機会が非常に少ない万が一分割されても、自己再生機能を持つビューサイズの負荷分散 4.3 Reactive extension of the view ネットワークの詳細を知らなくても、ノードの要望に応じて取得可能なビューのサイズを正確に拡張できる 4.4 Network size estimation Birthday paradox を用いる  わずか23人いれば同じ誕生日の人がいる確率が1/2になる現象 5. GOSSIP-BASED MEMBERSHIP Lbpcast  AODVを用いている Shuffling   もともとセンサネットワークで提案されたデータのロスを最低限に Flooding  効率が良くない 5.1 Probabilistic starvation 確率的マルチキャストアルゴリズムノードの大半はメッセージを受け取れるしかし、少数のノードは全くorほとんど受け取れない →要するに、ばらつきがある 5.2 Comparison 比較  Lbpcast はmobilityに弱い 6. SIMULATIONS 8. DISCUSSION RaWMSの提案  MANET向けメンバーリスト管理機構