創発システムに向けて 慶應義塾大学環境情報学部 徳田英幸

創発システムについて 複数の要素が有機的に関係し合って、相互作用を通して全体としてまとまった機能を発現している要素の集まり 弱い創発システム 相互作用が変わればシステムの機能も変わる！ 弱い創発システム ミクロな要素の動きが集まって全体にわたるマクロなパターンが創発するシステム 強い創発システム 環境変化に適応できる創発するシステム © H.Tokuda 2010

創発のかたち 上位層でのかたち 水の対流 サッカー場のウェーブ 自律型ロボットの整列問題 グループ、群、コミュニティ © H.Tokuda 2007

共通する性質は？ 自分と同じ能力の要素が沢山存在する 沢山の要素が広い空間に分散している すべての要素が共通の方法で（自分の近くの要素とだけ）情報の交換をする すべての要素が同時並列的にうごく すべての要素が同じ状況になるように動く(同じ評価関数をもっている） © H.Tokuda 2007

創発のギャップ 人間 vs. 自律型ロボット 多様な個 同期性 個の密度 全体の規模 実空間上の行動 vs. ネットワーク上の行動 個の非プログラム性 個の学習・動的適応性 多様な個 多様な価値観 情動的な行動 同期性 個の密度 population density 全体の規模 Scalability 実空間上の行動　vs. ネットワーク上の行動 © H.Tokuda 2007

自律分散協調コンピューティング 慶應義塾大学環境情報学部 徳田英幸 © H.Tokuda 2007

ちょっと復習と。。。 前半部分のまとめ 自律分散協調システム 分散アルゴリズム アドホックネットワーク／センサネットワーク P2P型アプリケーション マルチエージェントシステム 発見的手法

情報システムにおける自律分散協調 自律分散協調システムのねらい 自律分散協調コンピューティング 自己組織性 創発のメカニズム アドホックネットワークプロトコル ソフトウェアエージェント 自律ロボット p2pアプリケーション © H.Tokuda 2007

自律性について 社会システム 自律分散協調モデル ガバナンスモデル 教育、交通、安全システム 創発とは？ ロボット自動整列問題 電子政府モデル 地方自治体モデル 教育、交通、安全システム スマート交差点問題 自律分散協調モデル 創発とは？ Waveは、どう起るか？ ロボット自動整列問題 ロボットよ、コンパスを持って協調せよ！ 掃除ロボット問題 どのようなアルゴリズムが良いか？ © H.Tokuda 2007

協調性について 協調メカニズム 協調プロトコル 自然なプロトコル 人工的なプロトコル どのような協調パターンがあるのか？ どのように記述するのか？ なぜ協調するのか？ 自然なプロトコル 生物システム 人工的なプロトコル Client-Server Ethernet’s MAC Layer 競売プロトコル 回覧板プロトコル その他多種多様なプロトコル。。。 © H.Tokuda 2007

自律分散コンピューティング 分散アルゴリズム 複雑な問題に対する新しいアプローチ 自律性 分散性 協調性 遺伝的アルゴリズム(GA) 分散エージェント、マルチエージェント、自律ロボット 分散性 物理的な分散（コントロール＋データ）, p2pシステム フラットな構造 協調性 協調プロトコル 複雑な問題に対する新しいアプローチ 遺伝的アルゴリズム(GA) ニューラルコンピューティング © H.Tokuda 2007

Mobile Ad hoc Networks 　

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

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

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を受け取ったノードＳはＪ→Ｄの経路情報を消去する。

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

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

Wireless Sensor Networks

センサネットワーク利用分野 （出展： ユビキタスセンサネットワーク技術に関する調査研究会） © H.Tokuda 2007

日米欧におけるセンサネットワーク （出展： 野村総合研究所&ユビキタスセンサネットワーク技術に関する調査研究会） © H.Tokuda 2007

Sensor Network Models Sink-node Model P2P Model Habitat sensing Seismic monitoring Structuring instrumentation Soil conditioning P2P Model Smart Kindergarten Smart Objects, Smart Toys Smart Surroundings Lovegety Navigety Sink Node Smart Nodes © H.Tokuda 2007

Traditional Sensor Networks © H.Tokuda 2007

P2p models: Lovegety & Navigety The Original p2p goods: Lovegety Navigety © H.Tokuda 2007

What is a Smart Sensor? P2P model Smart Sensor = Comp.+Comm.+Sensor+Actuator Why? Extending traditional sensor networks for Ubicomp applications P2P model No base stations Effective use of Context-information Ambient technology Smart Lamp © H.Tokuda 2007

例題： A Group Tour Keeper Smart Sensor with LED lights + button １２ １３ © H.Tokuda 2007

U. of Karlsruhe: Smart-Its Detection, processing and communication of sensor data in sticker-size to be embedded into everyday objects Generic Platform © H.Tokuda 2007

P2P型システムとその応用

P2p型システム peer: 端末ノード peer-to-peer: 1対１の対等な協調作業形態 アプリケーション 分類 ファイル共有、交換、配信: Chord, Napster, Gnutella, Winny グループウェア: Grove 分散コンピューティング: SETI@home 分類 構造的p2pシステム Deterministic algorithms DHT (Distributed Hash Table)-based Systems CAN (Content Addressable Network) 非構造的p2pシステム Randomized algorithms Search by Flooding alg. E.g. MANET’s routing © H.Tokuda 2007

C/S型 vs. P2P型 © H.Tokuda 2007