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

Slides:



Advertisements
Similar presentations
UDL( 片方向通信路 ) 衛星リンクには Feeder,Receiver が存在 双方向通信には2つのチャンネル データの流れは一方通行 N 局による通信には n(n-1) のチャンネルが必要 送信局が入れ替わることにより、 擬似的に多対多型通信を行う研究もされている.
Advertisements

IP over DVB-RCS の設計と実装 研究背景 DVB-RCS 衛星回線を用いて受信局から送信局への狭帯域な戻り回線を提供 Forward Link Return Link HUB Terminal.
MANETを用いた車車間マルチホップ通信環境の構築
無線干渉実験 慶應義塾大学大学院 政策・メディア研究科 金田 裕剛.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
アドホックネットワークの概要と技術動向 2005年2月26日 千葉大学大学院 阪田 史郎
第1回.
コンピュータ基礎(10) 11章 通信ネットワーク.
ネットワーク技術II 第8.2課 イーサネット・スイッチング
前回の課題 IPv6アドレス IP ARP ICMP NAT インターネット層 2003年12月4日 情報ネットワーク論 新村太郎.
仮想ブロードキャストリンクを利用した 片方向通信路の透過的経路制御 藤枝 俊輔(慶應義塾大学)
IPv6 エニーキャスト ルーティングプロトコル PIA-SM の設計および実装
インターネット構成法 最終発表 政策メディア科  2年  臼井 健 環境情報学部  3年  伊藤 雄太.
神奈川大学大学院工学研究科 電気電子情報工学専攻
TCP (Transmission Control Protocol)
創発システムに向けて 慶應義塾大学環境情報学部 徳田英幸.
Keio University Takefuji Lab. SecurityTeam INAS Kensuke Naoe
発表の流れ 研究背景 マルチテナント型データセンタ 関連研究 IPマルチキャスト ユニキャスト変換手法 提案手法 性能評価.
WindowsNTによるLAN構築 ポリテクセンター秋田 情報・通信系.
センサノード 時刻同期と位置測定 浅川 和久 2008/11/16 センサノード 時刻同期と位置測定.
輪講: 詳解TCP/IP ACE B3 suzuk.
自律分散協調システム.
無線センサネットワークにおける 実測に基づいた電力消費モデルの確立
Towards Commercial Mobile Ad Hoc Network Applications: A Radio Dispatch System ECN M1 sada.
トランスポート層.
コンテンツ配信 エンコード (符号化) CBR (Constant Bit Rate) VBR (Variable Bit Rate)
ネットワーク機器接続 2SK 情報機器工学.
アドホックネットワークの ルーティングプロトコル
コンピュータ基礎(10) 11章 通信ネットワーク.
ノードの情報を動的に反映したオーバレイネットワークの構築
ノードの情報を動的に反映したオーバレイネットワークの構築
ま と め と 補 足 ネットワークシステムⅠ 第15回.
MANETを用いた車車間マルチホップ通信環境の構築
移動型ネットワーク基盤システム furu (M2)
「コンピュータと情報システム」 06章 通信ネットワーク
慶應義塾大学 武藤研究室 セキュリティグループINAS 直江健介
大規模アドホックネットワークにおける 階層的な名前解決法
山本 貴之 大阪大学 大学院基礎工学研究科 情報数理系専攻 村田研究室 博士前期課程
6月19日 RoutingとRouting Protocol 大竹 由美子
イーサネット.
Copyright Yumiko OHTAKE
総合講義B:インターネット社会の安全性 第6回 ネットワークの基盤技術
Ibaraki Univ. Dept of Electrical & Electronic Eng.
IPv6 ネットワークにおける エニーキャスト通信実現のための プロトコル設計と実装
大阪大学 大学院情報科学研究科 博士前期課程2年 宮原研究室 土居 聡
TCP/UDP プロセス間の通信のためのプロトコル TCP:信頼性高、処理時間大 UDP:信頼性低、処理時間小 ftp SMTP HTTP
Progress Report Kenji Kaneda.
インターネットの基礎知識 その3 ~TCP・UDP層編~
第9章 Error and Control Messages (ICMP)
マルチホーミングを利用した Proxy Mobile IPv6の ハンドオーバー
情報通信ネットワークの 仕組み.
IP over DVB-RCSの設計と実装
Hawkeye: 街中ネットワークでのContext-aware Service提供を目指して
進捗報告 金田憲二.
片方向通信路を含む ネットワークアーキテクチャに於ける 動的な仮想リンク制御機構の設計と実装
最低限インターネット ネットワークにつなぎましょ!
P2P ネットワーク上で 実時間ストリーミングを実現するための 分散制御プロトコルの提案
勝手にインフラ隊 (の中の人といっしょ) に学ぶネットワーク講座 Part2
Prof. Noriyoshi Yamauchi
勝手にインフラ隊 (の中の人といっしょ) に学ぶネットワーク講座 Part2
アドホックルーティングにおける 省電力フラッディング手法の提案
衛星回線を含むネットワークにおける 動的経路制御に関する研究
計算機群における 「動的なインターネット接続性」の共有に関する研究
Amicus: A Group Abstraction for Mobile Group Communications
低軌道周回衛星における インターネット構築に関する研究
異種セグメント端末による 分散型仮想LAN構築機構の設計と実装
慶應義塾大学 政策・メディア研究科 修士課程 2年 間 博人
情報ネットワーク 岡村耕二.
ネットワークシステム ネットワークシステム概要.
Presentation transcript:

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

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

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

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

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

Wireless Networks

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

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

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

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

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

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

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

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

無線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.

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

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

パーソナルエリアネットワーク IrDA Bluetooth HomeRF 赤外線を使用 最大伝送速度・・・16Mbps 2.4GHz帯 IrDA(Infrared Data Association)・・・point to point Bluetooth・・・携帯情報機器向けの短距離無線データ通信技術の規格である.10m以内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。

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

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

Mobile Ad Hoc Networks

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 を既に受け取ったノード

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 に付加しているアドレスのリスト

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

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 ノードCは RREQ をGとHから受け取るが、すでに転送したRREQであるため、もう一度転送はしない。

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]

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

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

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

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

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

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

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 を既に受け取ったノード

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

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

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

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

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

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

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

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

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

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

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

Challenges セキュリティ アドレスを割り当て問題 Quality of Service (サービス品質)保証 キラーアプリケーション IETF manet: http://www.ietf.org/html.charters/manet-charter.html CMU Monarch Project (DSR): http://www.monarch.cs.cmu.edu/ Charles E. Perkins (AODV) :http://www.srvloc.org/charliep/charliep.html

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

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

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

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

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

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

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

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

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

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