自律分散協調システム

自律分散協調コンピューティング 分散コンピューティング 分散アルゴリズム いくつかの事例 マルチエージェント CSCWシステム Mobile Ad hoc Networks Wireless Sensor Networks マルチエージェント Software Agent Mobile Agent CSCWシステム 遺伝的アルゴリズム ニューラルコンピューティング

Mobile Ad hoc Networks

無線アドホックネットワーク アドホックネットワークとは？ ネットワーク･インフラが存在しない トポロジが人や物の動きと共に動的に変化する peer-to-peerでの通信スタイル トポロジが人や物の動きと共に動的に変化する ノードの移動、無線電波品質の変化 Weak Connectivity 常時接続の保証ではない

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

Introduction

Traditional Networks Internet は Ad Hoc Network ではない ネットワーク･インフラは固定 ネットワーク･トポロジはほとんど変化しない

Cellular Networks Cellular Networks は Ad Hoc Network ではない 終端ホップは無線だが、ネットワーク･インフラは固定 基地局 基地局 交換機 交換機 基地局 基地局

Single-hop Wireless Networks Cellular networks と基本的には同じ 電波の届く距離にアクセスポイントが必要 有線ネットワーク 無線ネットワーク アクセスポイント

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

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

Flooding

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

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

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 パケットＰを最初に受信したノード パケットＰの転送

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 ノードＣはパケットＰをＧとＨから受け取るが、すでに転送したパケットであるため、もう一度転送はしない。

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 ノードＤは最終宛先である為パケットＰをノードＮに転送しない

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

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

Ad Hoc Networking Protocols

アドホックネットワークを実現するためのプロトコルの研究 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 ノードＳがパケットをＤに送りたいが経路を知らない場合 Route Discovery を行う ノードＳは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 ノードＣは RREQ をＧとＨから受け取るが、すでに転送した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 ノードＤは最終宛先である為RREQをノードＮに転送しない Y Z S E [S,E,F,J,M] F B C M L J A G H D K I N ノードＤは最終宛先である為RREQをノードＮに転送しない

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

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 の転送 ＳはＤへの経路は Ｓ→Ｅ→Ｆ→Ｊ→Ｄ であると記憶する。

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 ＪはＤへの経路が壊れたというメッセージを含んだReply Error (RERR) をＪ→Ｆ→Ｅ→Ｓという経路で送信ノードＳに送る。 RERRを受け取ったノードＳはＪ→Ｄの経路情報を消去する。

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 各ノードは宛先に届けるために次にどのノードに投げれば良いかだけを知っている。 ネットワークトポロジが頻繁に変更する時に高い性能 まだ有効な経路情報を消去してしまう危険性がある。

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

センサネットワーク

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

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

アプリケーション 生態系観測 海洋観測 土壌観測 破壊診断 Smart Kindergarten Bluetooth 10 meters range IrDA 3 meters range

Smart Kindergarten センサーネットワークのアプリケーションとして幼稚園を対象としたプロジェクト 子供やおもちゃにセンサを取り付け，　 先端的な幼児教育環境の提供を目指す UCLA がやってる http://nesl.ee.ucla.edu/projects/smartkg/

Smart Kindergarten アーキテクチャ Sensing Infrastructure 様々な情報の取得 Network Infrastructure センシングデータの収集 Middleware センシングデータの管理 各種サービスの提供　　　（位置情報など） ３層構造になってます 具体的なセンシングデータ 識別子，絶対/相対位置，音/話，　画像/動画，方位，動き，加速度，さわる/押す

Smart Kindergarten シナリオ：Smart Toy 埋め込まれたセンサから情報の取得　　（触られた / 触ってる子供は誰？　など） 取得したセンシング情報をサーバに送信 サーバ側でコンテキストの抽出 聴覚，視覚，動き，触覚に訴える反応を返す たとえば、触ったら目が光るとか。 触ってる子供を識別して、子供の名前を話すとか action 子供 Smart Toy reaction

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

Source: Jouni Welander (Siemens)