[題名] Location-Aided Routing(LAR) in Mobile Ad Hoc Networks

[著者] Young-Bae Ko Nitin H. Vaidya
[日付] 1998/10/25
[出典] Proc. of MobiCom'98

Abstract

• (GPS の)位置情報を利用して Ad-Hoc Network の経路制御の性能向上を図る。
• 経路探索の範囲を制限する。
• 要求範囲を決める 2 つのアルゴリズムを提案する。

1. Introduction

• MANET ではトポロジの変化が予測できない為、経路探索が難しい。
• 様々な経路探索の為の手法が提案されている。
• どのように位置情報を利用して経路探索の性能向上を図るかについて述べる。

2. Related Work

• トラフィックパターンに対応した経路制御
  • DSR: on-demand route discovery
  • AODV: on-demand route discovery
  • TORA: 局所性に注目したオーバヘッド削減
  • ZRP: 定期的処理による scope の決定によるオーバヘッド削減
• PCS においては地理的位置情報を利用した経路探索を行なっている。
  • selective paging: MH の近くのセルにだけ呼出をかける。
• Metricom の GPS を利用した経路制御
  • 全ての BS の位置が測定してあって、1 hop 近い方に中継する。
• 他にも幾つかある。

3. Location-Aided Routing(LAR) Protocol

3.1. Route Discovery Using Flooding

• フラディングを使った経路探索は以下の通りの手法で行なう。(DSR 似)
  • 送信者が経路要求を隣接ノードへブロードキャストをする
  • 経路要求を受け取ったホストは自分の ID と要求を比較して同じな ら自分に対する経路要求であることを認識し、そうでなければ更に 隣接ホストにブロードキャストする。
  • 同じ要求を過去に受け取ったことがあるかどうかはシーケンス番号 でチェックし、受け取ったことがある場合はブロードキャストしな い。
• 図1 の例: S が D を探す。
  • S が隣接ホストにブロードキャスト
  • B, C は X へ更に隣接ホストに経路要求をブロードキャスト
  • X は B からの要求を受け取った時点で次ホストに中継するが、さ らに C から同じ要求を受け取っても無視する。
• 経路要求には通った経路が記録され、経路応答はこの経路を逆にたどって要 求者に返る。
• 経路要求にはタイムアウト/再探索がある。
• 経路探索が始まるのは送信者が相手までの経路を知らない場合と経路が壊れ たことを検知した場合。
  • 今回の実装では経路が壊れた時には経路誤りメッセージを返す。
• 経路探索の過程で送信者までの経路を途中のホストが知ることができる。
• DSR や AODV は上記のアルゴリズムを基に様々な拡張を行なっている。本論 文の議論は、そのまま、DSR や AODV に適用できるが、話を簡単にする為に、 上記のアルゴリズムで話を進める。

3.2. Preliminaries

Location Information

• LAR で使う位置情報は GPS から得る。
• GPS で得た位置には 50-100m の誤差があるが、誤差がないものとして話を 進める。
• 誤差についてはパフォーマンス評価の部分で触れる。

Expected Zone and Request Zone

• S は D の時刻 t0 における位置(L)を知っていると仮定。
• D の移動速度 v を知っていれば、現在(t1)の移動範囲を予測できる。 v(t1-t0) 図2(a)
• 単なる「予測」である
  • S が D の t0 における位置を知らなければ予測できない。
  • D が北に動いていることを知っていれば予測移動範囲は更にしぼれ る。
• 送信者は要求範囲を設定する。
  • 送信者自身が予測移動範囲外にある場合は要求範囲は予測移動範囲 より広くなる。(図3 a)
  • 図3 b のようなネットワークの場合は相手までの経路が見つからな いのでタイムアウト後に範囲を拡張してもう一度探索を行なう。
  • 検索範囲を広げることはオーバヘッドを大きくすることを意味し、 トレードオフとなる。

3.3. Determining Membership of Request Zones

• - 各ホストが、リクエスト毎に自分が要求範囲に入っているかを判断する。

LAR Scheme 1

• 矩形で要求範囲を指定する。
• 送信者は自分と予測移動範囲が入る最小の矩形を作成。(図4 a, b)
• 図4(a) においては I は要求を中継するが、J は破棄する。
• 応答メッセージには相手の現在地と時間が記録されている。
• 仮定では平均移動速度は既知。
• 矩形の大きさは平均移動速度と時間経過に比例している。
• 移動速度が遅い場合は、時間経過が長くなることが予想される。
  • リンクが切れる可能性は移動距離に関係する。
• 要求範囲が大きすぎることも小さすぎることもない。

LAR Scheme 2

• t0 での相手までの距離 DISTs と相手ホスト D の位置を要求メッセージに 格納する。
• 要求メッセージを受信したホストは、自分から D までの距離 DISTi を算出。
• DISTs + δ ≧ DISTi なら DISTi を格納して中継する。そうでなければ破 棄する。
• 次にパケットを受信したホスト J は DISTi + δ ≧ DISTj なら DISTj を 格納して中継する。そうでなければ破棄する。
• δを大きくするとパフォーマンスは下がるが、見つかる可能性は大きくなる。
• δは位置計測が誤差を含んでいる場合に 0 ではなくなる。今回のシミュレー ションでは δ=0。
• 図5 は Scheme 1 と 2 の比較である。N に着目。
• 計測に誤差はつきもの。
• Scheme 1 では予測移動範囲を e + v(t1-t0) とするべき。

4. Performance Evaluation

• MaRS(Maryland Routing Simulator)でシミュレーション。
• flooding, LAR Scheme 1, LAR Scheme2 について測定。

4.1. Simulation Model

• ノード数: 15, 30, 50
• 範囲: 1000 unit x 1000 unit
• 移動: 常に動き続ける。平均速度=v、最大速度=v+α、最低速度=v-α
  • v ＜ 10、α = 1.5
  • v ≧ 10、α = 2.5
  • 平均速度は 1.5 〜 32.5 unit/sec
  • 平均 20 unit(/sec?) 移動。指数分布。
  • 方向はランダム
  • 境界では跳ね返る。
• 通信範囲: 全てのノードは同じ通信範囲 200, 300, 400, 500 unit
• 通信容量: 100KByte
• 時間: v = 1.5 の場合 4000 sec, v = 4.5 の場合 1333 sec
• 通信ペア: ランダム
  • 相手に届かなかったパケットは捨てられる。
  • 送信者は 10 packet/sec で送出
• 一回目は LAR Scheme を使用。返答が無ければ flooding。タイムアウトは 2 秒。
• 同時に送信した時の遅延、エラーに関しては考慮しない。

4.2. Simulation Results

• 言葉の定義
  • data packet(DP): 相手によって受信されたパケット
  • routing packet(RP): 様々なホストに受信されたパケット
• 異なる 30 以上の移動パターンによるシミュレーションの平均値で示す。ただし、 パラメータ(平均速度、ノード数、送信範囲等)は同じ
• 図6 RP/DP vs 平均速度
  • 図6(a): RP/DP
  • 図6(b): LAR による性能上昇(in %)。対 flooding 比
  • RP/DP 比は MH の移動速度が上ルにつれて全てのプロトコルで悪くなる。
  • LAR を使うとどちらの Scheme でも性能はあがる
• 図7 RP/DP vs 送信範囲
  • 通信範囲が広くなると RP/DP 比は良くなる。
  • 図7(b) の 200 unit の時は LAR Scheme 1 が flooding より悪い。
    • 数ホップするのでタイムアウトまでに返事が帰って来ない
• 図8 RP/DP vs ノード数
  • 数が少ないと送信範囲が狭いのと同じなので、あまりメリットが無い。
  • ノード数 15 以下では LAR のオーバヘッドが大きかった。
• 図9 RP/経路発見 vs 平均速度
  • LAR Scheme 2、LAR Scheme 1、flooding の順の性能

Impact of Location Error

• 実際の GPS の測量では e unit の誤差があるが、上では 0 とした。
• 図 10: GPS の誤差はほとんど気にならない。
• 図 11: e が大きくなると探索範囲が広がるが、その分見付かる確率も増える。

5. Variations and Optimizations

Alternative Definitions of Request Zone

• 改良1: Scheme 1 の送信者の部分にある境界を、すこし広げる。
• 改良2: 長方形では無く、平行四辺形などを導入する。
• 改良3: タイムアウトした場合、探索範囲を徐々に広げる。
• 改良4: 平均速度以外の情報(例: 方向)等も利用する。

Adaptation of Request Zone

• 中間ノードで予測範囲を再計算することにより、より正確な位置を特定。
  LAR1
  • 送信者: t0 を もとにした t1 時の位置による予測範囲
  • 中継者: t0 を もとにした t2 時の位置による予測範囲
  LAR2
  • 距離をより新しいDの位置に基づいて計算

Propagation of Location and Speed Information

• 始めは他のホストの位置、速度などの情報を持たない。
• 経路要求、経路応答メッセージに位置や平均速度をいれることによって相手 の位置を知ることができる。
• 他のパケットにもピギーバックできる。

Local Search

• 図12 (c) のようにした方が効率が良い。
• このためには 図12 (a) のような経路誤り通知が必要。

6. Conclusion

• 位置情報を使って経路探索のオーバヘッドを削減する方法を検討した。
• 2 つの方法を示した。
• シミュレーションで提案した方法の有効性を示した。
• 更に改良案を幾つか示した。