政策・メディア研究科 間 博人 徳田英幸 haru@ht.sfc.keio.ac.jp 自律分散協調システム論 政策・メディア研究科 間　博人　　徳田英幸 haru@ht.sfc.keio.ac.jp.

Presentation on theme: "政策・メディア研究科 間 博人 徳田英幸 haru@ht.sfc.keio.ac.jp 自律分散協調システム論 政策・メディア研究科 間　博人　　徳田英幸 haru@ht.sfc.keio.ac.jp."— Presentation transcript:

1 政策・メディア研究科 間 博人 徳田英幸 haru@ht.sfc.keio.ac.jp
自律分散協調システム論 政策・メディア研究科 間　博人　　徳田英幸

2 講義内容 分散協調アルゴリズムの応用例としてアドホックネットワークに関するプロトコル事例を紹介する 無線ネットワークの種類
Flooding 経路制御プロトコル センサネットワーク

3 無線ネットワーク(例:無線LAN) 有線ネットワーク 無線ネットワーク アクセスポイント

4 アドホックネットワーク 瞬時にその場で構成するネットワーク node

5 自律分散協調システムとは？ システム内にシステム全体を制御／統治するスパーバイザは存在しない。
各サブシステムは、自律、分散した構成要素からなる。 全体のシステムの機能は、サブシステム間の協調作業によって遂行される。 © H.Tokuda 2008

6 Wireless Networks

7 様々な無線技術 無線LAN 衛星通信 PAN セルラーネットワーク

8 衛星通信 無線LAN 衛星通信 PAN セルラーネットワーク

9 衛星通信 C band(4~8GHz帯） Ku band （12~18GHz帯） Ka band (27~40GHz帯)
降雨減衰がなく、伝搬損失が小さい 設置場所に制約がある Ku band （12~18GHz帯） 降雨減衰や伝搬損失はあるが比較的小さい 設置場所にCバンドほど制約がない Ka band (27~40GHz帯) 広帯域通信が可能。降雨減衰が大きい 設置設備が高い 衛星間通信にも利用される

10 セルラーネットワーク 無線LAN 衛星通信 PAN セルラーネットワーク

11 セルラーネットワーク 他社・他地域の交換機 交換機 B A 基地局 端末 セル

12 セルラーネットワーク セルラーネットワークとは 地域を細胞（セル）状に細かく分割し、それぞれのセル同士をつなげてネットワークを形成する方式
携帯電話（ＰＤＣ、cdmaOne、ＩＭＴ-2000 etc.) 通信端末間の距離が近くても基地局を介さなければならないので、遠回りになる場合がある セル

13 無線LAN 無線LAN 衛星通信 PAN セルラーネットワークr

14 無線LAN 有線ネットワーク アクセスポイント

15 無線LAN IEEE802.11a IEEE802.11b IEEE802.11g 5GHz帯 最大伝送速度･･･54Mbps
802.11･･･CSMA/CS, 2.4GHzISM帯を利用した直接拡散(DSSS Direct Sequence Spread Spectrum )方式と周波数ホッピング(FHSS Frequency Hopping Spread Spectrum)方式と，ベースバンド赤外線の3種類が規定されている．802.11bは直接スペクトラム拡散(DSSS)方式だけとなった。 HIPERLAN(High Performance Radio Local Area Network)･･･欧州のETSI(European Telecommunications Standard Institute)で規格化、HIPERLAN-type1では20Mbps,type2では54Mbps 物理層OFDM: (Orthogonal Frequency-Division Multiplexing)とは、一つの高速データ列を複数の低速の副搬送波で並列に伝達する多元通信の特殊な方法のことである。 The air interface of HIPERLAN/2 is based on TDD and dynamic TDMA.

16 パーソナルエリアネットワーク 無線LAN 衛星通信 PAN セルラーネットワーク

17 パーソナルエリアネットワーク 情報機器端末同士のネットワーク

18 パーソナルエリアネットワーク IrDA Bluetooth HomeRF 赤外線を使用 最大伝送速度･･･16Mbps 2.4GHz帯
IrDA（Infrared Data Association）･･･point to point Bluetooth･･･携帯情報機器向けの短距離無線データ通信技術の規格である．１０ｍ以内1Mbps ，1つのMasterと1つのSlaveの1対1(Point-to-Point)と1つのMasterと複数のSlaveの1対多(Point-to-Multipoint)通信ができるFHSS(周波数ホッピング拡散方式,Frequency Hopping Spread Spectrum)を採用. HomeRF(Home Radio Frequency)･･･HRFWG（HomeRF Working Group)で規格化 Digital frequency hopping spread spectrumを用いる。 TDMAとCSMA/CAを両方ともサポート、real-timeを望むときにはTDMAを、速くデータを送りたい ときにはCSMA/CAを用いる。 機器間の通信にはSWAP（ Shared Wireless Access Protocol） と呼ばれるプロトコルが用いられ、鍵長40ビットの暗号化通信により、安全性を確保することができる。通信可能な距離は50～100m。

19 Network Bandwidth Latency Range mobility Room/Building Campus-area Metro-area Satellite networks >1Mbps <100kbps <2Mbps 10-100Mbps <10ms ms >100ms >>100ms <300 m <1.5km 数km 数百km 人が歩く速さ 自転車の速さ 車の速さ 固定

20 無線ネットワークの分類 衛星通信 携帯電話 無線ＬＡＮ モバイルアドホックネットワーク センサネットワーク 必要ない
既存のネットワーク・インフラが 必要である モバイルアドホックネットワーク センサネットワーク 既存のネットワーク・インフラが 必要ない

21 Mobile Ad Hoc Networks

22 アドホックネットワークとは（1/2） ネットワーク・インフラを必要としない 端末の移動に対応

23 アドホックネットワークとは（2/2） マルチホップを利用したルーティング C B A

24 従来のネットワークとの違い（1/3） Internet ネットワーク･インフラは固定 ネットワーク･トポロジはほとんど変化しない

25 従来のネットワークとの違い（2/3） Cellular Networks 終端ホップは無線だが、ネットワーク･インフラは固定 交換機 交換機
基地局 基地局 交換機 交換機 基地局 基地局

26 従来のネットワークとの違い（3/3） Single-hop Wireless Networks 電波の届く距離にアクセスポイントが必要
有線ネットワーク 無線ネットワーク アクセスポイント

27 Multi-hop Wireless Ad Hoc Networks
ネットワーク･インフラが存在しない トポロジの変化が発生する ノードの移動、無線電波品質の変化

28 アドホックネットワークの可能性（1/2） 交通ネットワーク 緊急時における利用 情報共有→屋外でも可

29 アドホックネットワークの可能性（2/2） マルチホップを利用した通信モデル 日常生活での情報共有 BS 情報共有→屋外でも可 B A

30 アドホックネットワーク（応用例） パーソナルエリアネットワーク 軍隊の (Military) 環境 一般市民の (Civilian) 環境
携帯電話、ラップトップ、時計 軍隊の (Military) 環境 兵士、戦車、戦闘機 一般市民の (Civilian) 環境 タクシーネットワーク、ミーティングルーム、スポーツスタジアム、ボート 緊急時の操作 地震、洪水、竜巻 捜索と救出、警察や消防士

31 アドホックネットワークにおける経路制御 通信相手までの経路発見 経路確立後の経路維持 Y Z S E F B C M L J A G H D
K I N 通信元端末は通信先端末のアドレスだけを知っている

32 Key Technology: Flooding
Internet ノードが持つIPアドレスがネットワーク上の位置を示している ルータは宛先アドレスを基にデータを次のルータ/ノードに中継する Ad Hoc Networks すべてのノードがルータの役割をする ノードは移動するため、宛先までの経路は頻繁に変化する 経路の分からない宛先までデータを届けるメカニズムが必要 Flooding

33 Flooding for Data Delivery
送信者Ｓは宛先Ｄのデータ（パケット）Ｐをすべての近隣ノードにブロードキャストで転送する Ｐを受け取った各ノードはさらに近隣のノードにＰをブロードキャストで転送する。 同じパケットを何度も転送することを避ける為にＰにはシケーンス番号を付けておく Ｐが宛先Ｄまで到達するとＤは自分宛てのパケットなので中継しない。

34 Flooding for Data Delivery
Z S E F B C M L J A G H D K I N パケットＰをすでに受信したノード お互いにデータが送受信可能なノード

35 Flooding for Data Delivery
ブロードキャストによる転送 Z S E F B C M L J A G H D K I N パケットＰを最初に受信したノード パケットＰの転送

36 Flooding for Data Delivery
Z S E F B C M L J A G H D K I N

37 Flooding for Data Delivery
Z S E F B C M L J A G H D K I N ノードＣはパケットＰをＧとＨから受け取るが、すでに転送したパケットであるため、もう一度転送はしない。

38 Flooding for Data Delivery
Z S E F B C M L J A G H D K I N

39 Flooding for Data Delivery
Z S E F B C M L J A G H D K I N ノードＤは最終宛先である為パケットＰをノードＮに転送しない

40 Flooding for Data Delivery
Z S E F B C M L J A G H D K I N Flooding 終了

41 Flooding for Data Delivery: Advantages
簡単なメカニズム　（実装が容易） データパケット以外の情報を送信する必要がない トポロジの変更が頻繁に起こるような環境では経路の管理 (Discovery/Maintenance) をする必要がないため効率的 データ配信の信頼性が高い パケットが複数の経路を通って宛先に届くので信頼性がある

42 Flooding for Data Delivery: Disadvantages
オーバーヘッドが大きい パケットが無駄に多くのノードに配信される。 TTL データ配信の信頼性を100%にすることが難しい Flooding はブロードキャストを使っている。 信頼性のあるブロードキャストを実装することはオーバーヘッドをさらに増加させる。 同時に2つのノードがパケットを送信するとパケットの衝突が起こる可能性がある→パケット喪失 無線の帯域は狭い為、データをFloodingさせるメカニズムはスケーラビリティの点で難点がある

43 Flooding of Control Packets
コントロールパケットは経路を発見するために利用する 発見した経路はデータパケットを送るのに利用する 経路を管理するためにコントロールパケットを定期的に送る必要がある ノードの移動に伴い経路が変化する可能性がある

44 アドホックネットワークを実現するためのプロトコルの研究
DARPA（米国国防総省） 研究プログラム Packet Radio Network (PRNET) Survivable Adaptive Networks (SURAN) Global Mobile Information Systems (GLOMO) IETF Mobile Ad Hoc Networks (MANET) Working Group 1997- Dynamic Source Routing (DSR) Ad-hoc On-demand Distance Vector Routing (AODV)

45 アドホックネットワークの ルーティングプロトコルの分類
Reactive 型 （On-Demand型）プロトコル 経路が必要な時に宛先までの経路を作成 Proactive 型 （Table-Driven型）プロトコル あらかじめ各宛先への経路を構築しておく Hybrid型プロトコル

46 DSR: Dynamic Source Routing
ノードＳがパケットをＤに送りたいが経路を知らない場合 Route Discovery を行う ノードＳはRoute Request (RREQ)を Flooding する それぞれのノードはRREQを中継する際に　　自分のアドレスをRREQに付加する David B. Johnson (CMU → Rice Univ.)

47 Route Discovery in DSR SからDに対する RREQ を既に受け取ったノード Y Z S E F B C M L J A
G H D K I N SからDに対する RREQ を既に受け取ったノード

48 Route Discovery in DSR Y Z [S] S E F B C M L J A G H D K I N
[X,Y] RREQ に付加しているアドレスのリスト

49 Route Discovery in DSR Y Z S [S,E] E F B C M L J A G [S,C] H D K I N

50 Route Discovery in DSR Y Z S E F B [S,E,F] C M L J A G H D K [S,C,G] I N ノードＣは RREQ をＧとＨから受け取るが、すでに転送したRREQであるため、もう一度転送はしない。

51 Route Discovery in DSR Y Z S E F [S,E,F,J] B C M L J A G H D K I N
[S,C,G,K]

52 Route Discovery in DSR ノードＤは最終宛先である為RREQをノードＮに転送しない Y Z S E
[S,E,F,J,M] F B C M L J A G H D K I N ノードＤは最終宛先である為RREQをノードＮに転送しない

53 Route Discovery in DSR ノードDは Router Reply (RREP) を返答する。
RREPはRREQに付加しているアドレスを逆にたどって送られる。 RREPにはＳからＤへの経路の情報が含まれている。 ノードSは最初に受け取った RREP に含まれている経路をノードDまでの経路として記憶(キャッシュ)する。

54 Route Reply in DSR RREP の転送 ＳはＤへの経路は Ｓ→Ｅ→Ｆ→Ｊ→Ｄ であると記憶する。 Y Z S
RREP [S,E,F,J,D] E F B C M L J A G H D K I N RREP の転送 ＳはＤへの経路は Ｓ→Ｅ→Ｆ→Ｊ→Ｄ であると記憶する。

55 Data Delivery in DSR 経由するノードが多くなる程、パケットヘッダが大きくなる Y Z DATA [S,E,F,J,D]
B C M L J A G H D K I N 経由するノードが多くなる程、パケットヘッダが大きくなる

56 Route Error (RERR) Y Z RERR [J-D] S E F B C M L J A G H D K I N ＪはＤへの経路が壊れたというメッセージを含んだReply Error (RERR) をＪ→Ｆ→Ｅ→Ｓという経路で送信ノードＳに送る。 RERRを受け取ったノードＳはＪ→Ｄの経路情報を消去する。

57 AODV: Ad-hoc On-Demand Distance Vector Routing
DSRは宛先のルートをすべてパケットのヘッダに含んでいる。 大きなヘッダは転送効率を悪くする。 AODVはデータパケットに経路を含ませないようにする為に、各ノードで経路情報を保持する。 Charles E. Perkins (IBM→Sun→Nokia)

58 Route Requests in AODV SからDに対する RREQ を既に受け取ったノード Y Z S E F B C M L J A
G H D K I N SからDに対する RREQ を既に受け取ったノード

59 Route Requests in AODV RREQの転送 Y ブロードキャストによる転送 Z S E F B C M L J A G H
K I N RREQの転送

60 Route Requests in AODV Y EはRREQをSから受け取ったことを記憶しておく。 Z S E F B C M L J A
G H D K I N 逆方向の経路のリンク

61 Reverse Path Setup in AODV
Y Z S E F B C M L J A G H D K I N

62 Reverse Path Setup in AODV
Y Z S E F B C M L J A G H D K I N

63 Reverse Path Setup in AODV
Y Z S E F B C M L J A G H D K I N

64 Route Reply in AODV Y Z S E F B C M L J A G H D K I N RREPによって通知される経路

65 Forward Path Setup in AODV
Y Z S E F B C M L J A G H D K I N RREPが逆の経路を通ってSに戻ってきた時各ノードの経路情報は設定される 送信経路

66 Data Delivery in AODV Y DATA Z S E F B C M L J A G H D K I N

67 Route Error in AODV ノードの移動により経路が壊れた場合、すべてのノードにRoute Error を伝えなくてはならない。（各ノードが持つ古い経路情報を消去するため） Route Error Packet の　Flooding が起こる 一定時間使われなかった経路情報は消去する。

68 Summary: DSR vs. AODV DSR AODV 送信ノードは宛先までの完全な経路を知っている。
ネットワークトポロジの変化が少ない時に高い性能 パケットにルーティング情報が入るため転送効率が悪い AODV 各ノードは宛先に届けるために次にどのノードに投げれば良いかだけを知っている。 ネットワークトポロジが頻繁に変更する時に高い性能 まだ有効な経路情報を消去してしまう危険性がある。

69 Ad Hoc Networking Protocol How to design ?
どのようなノードの移動パターンを想定するべきか？ どのような通信トラフィックを想定するべきか？

70 Challenges セキュリティ アドレスを割り当て問題 Quality of Service （サービス品質）保証
キラーアプリケーション IETF manet: CMU Monarch Project (DSR): Charles E. Perkins (AODV) :

71

72 無線ネットワークの分類 衛星通信 携帯電話 無線ＬＡＮ モバイルアドホックネットワーク センサネットワーク 必要ない
既存のネットワーク・インフラが 必要である モバイルアドホックネットワーク センサネットワーク 既存のネットワーク・インフラが 必要ない

73 センサネットワーク 多数の相互無線通信可能な小型ノード利用 各ノードにセンシング機能 センサ ノード センサ ノード センサ ノード センサ

74 プロトタイプ Motes Pushpin uCube Smart-Its Dot 01 Mica 02
Bluetooth 10 meters range IrDA 3 meters range

75 UC Berkeley: Smart Dust
Modern Sensor Nodes UC Berkeley: COTS Dust UC Berkeley: Smart Dust UC Berkeley: COTS Dust Rockwell: WINS UCLA: WINS JPL: Sensor Webs

76 応用 モノ 人 部屋 境域環境 (屋外)広域環境 対象領域 個人 企業・組織 社会・自治体 利用主体 看護・医療・教育 物流・
マーケティング ホームセキュリティ 犯罪防止 ビル管理 プラントモニタリング 農場モニタリング 福祉サービス 防犯・防災 サベイランス 交通モニタリング 環境モニタリング

77 MANETとセンサネットの共通点 マルチホップ転送 識別子割当て問題 省電力 Bluetooth 10 meters range
IrDA 3 meters range

78 MANETとセンサネットの差異 センサネットのノードは必ずしも移動を仮定する必要はない。
センサネットでは、配送されるデータが「センサデータ」という特殊データであることを考慮してネットワークを設計する必要がある。 Bluetooth 10 meters range IrDA 3 meters range

79 技術的な分解 応用システム セキュリティ トランスポート システム設計 最適配置 キャリブレーション ルーティング
位置特定(localization) Exposure Bluetooth 10 meters range IrDA 3 meters range 電源管理 センシング/無線デバイス ハードウェア

80 研究テーマ ルーティング（データ配送） Localization (位置特定) 省電力 同期 キャリブレーション 配置の最適化 データ量圧縮
Bluetooth 10 meters range IrDA 3 meters range

81 まとめ ・ センサネットワークは、センシングと無線デバイスを組み合わせたノードで構成されるネットワークである
・　センサネットワークは、センシングと無線デバイスを組み合わせたノードで構成されるネットワークである ・　無線アドホックネットワークと共通の課題も多い ・　しかし、センシングに関わる特有の問題も多い ・　ユビキタスコンピューティングを支える技術として発展が見込まれる