自律分散協調システムとは？

自律分散協調システムとは？
自律分散協調システムとは？
n
n
n
まとめ
今後の展望
システム内にシステム全体を制御／統治するスパー
バイザは存在しない。
各サブシステムは、自律、分散した構成要素からなる。
全体のシステムの機能は、サブシステム間の協調作
業によって遂行される。
生物システム
社会システム
情報システム
© H. Tokuda, Keio University
基本的な概念
n
自律性
n
n
n
n
n
n
n
多数の個
空間的・ネット的に分散
n
協調性
n
n
n
n
n
個の確立
主体的行動
分散性
n
n
自律分散協調システムの目的
n
個と個の協調プロトコル
協調により全体の機能を維持・形成する
構成論的手法 vs. 自己組織論的手法
n
n
システムとしての評価
n
n
n
評価の軸
良いシステム vs. 悪いシステム
n
n
情報システムにおける自律分散協調論
情報システムにおける自律分散協調論
n 自律分散協調コンピューティング
n 工学的なシステムだけでなく
、他の分野の自
律分散協調システムシステムのデザイン、解
析、評価に応用する。
n
機能拡大
コスト性能比の改善
分散処理による効率・サービスの改善
オンラインリアルタイム処理の実現
局所化による通信量の低減
構成要素のｍモジュール化
拡張性の保証
集団組織の効率化
信頼性・耐故障性の改善
状況・環境変化への適応
生存可能性の増大
情報システムにおける自律分散協調論
新しいキーワード
n 自律分散協調システムのねらい
n
自己組織性
n 創発のメカニズム
n
n
自律分散協調コンピューティング
アドホックネットワークプロトコル
n ソフトウェアエージェント
n 自律ロボット
n p2pアプリケーション
n
生物システム
社会システム
情報システム
1
自律性について
n
社会システム
n
ガバナンスモデル
• 電子政府モデル
• 地方自治体モデル
n
教育、交通、安全システム
• スマート
交差点問題
n
自律分散協調モデル
n
創発とは？
n
ロボット自動整列問題
n
掃除ロボット問題
ロボット整列問題
ある部屋内において、与えられた半径ｄの円
周上にほぼ等間隔で整列するプログラムを
作成せよ。
n 仮定
n
ロボットが共有座標系を持つ
n 同期的な動作をする (c.f. life game)
n
• Waveは、どう起るか？
• ロボットよ、コンパスを持って協調せよ！
• どのようなアルゴリズムが良いか？
Robot.java
協調性について
どのように協調するのか？
n 実行例…
n
n
協調メカニズム
n
協調プロトコル
• どのような協調パターンがあるのか？
• どのように記述するのか？
• なぜ協調するのか？
n
自然なプロトコル
n
人工的なプロトコル
• 生物システム
•
•
•
•
•
Client-Server
Ethernet’s MAC Layer
競売プロトコル
回覧板プロトコル
その他多種多様なプロトコル。。。
wave2.c: 課題
自律分散協調コンピューティング
どのように協調するのか？
n 実行例…
n
n
分散アルゴリズム
n
n
相互排除問題、デッドロック問題、etc
複雑な問題に対する新しいアプローチ
エージェントシステム
n 遺伝的アルゴリズム(GA)
n
n
協調作業支援システム
CSCWシステム
n グループウェア
n
2
分散アルゴリズム
Distributed Mutual Exclusion
n Election Algorithm
n Distributed Deadlock
n Clock Synchronization
n Byzantine consensus problem
n
何が良いシステムか？
評価基準は？
© H. Tokuda, Keio University
安全に非難誘導を行うシステム
NTT-Docomo
i-mode Gateway
仮定：
公募をしてシステムの提案書を受け
取った
n 評価基準は、どうあるべきか？
n
∼ 事例２ ∼
基準１∼５ぐらいを明記
n その理由を述べる！
n
© H. Tokuda, Keio University
Centralized i-mode portal
集中型の問題点
n
単一故障
危機管理上の問題
n 顧客からの クレーム増
n
n
スケーラビリティ
n
2,800万以上のclientに対応
応答性の低下
n 負荷分散の欠如
n
3
Distributed i-mode Portal
集中型のメリット
n
ビジネスの独占
ビジネスモデルの創出
n 回線使用料の独占
n
n
セキュリティの向上
n
n
専用回線の利用
アカウンティングの容易性
分散型のメリット
n
新しいビジネスの導入
n
n
ビジネスモデルの創出
回線使用料の徴収モデル
• 個人から法人へ
n
スケーラビリティの向上
n
n
n
i-mode portalの構造
応答性・ユーザビリティの向上
多機能端末
n
Universal controller型が可能
分散型の問題点
n
アカウンティング問題
n
回線使用料の徴収へのオーバヘッド
新しいドコモボックスの開発
n セキュリティ
の確保
n 多機能端末
n
n
端末コストの増大
Docomo i-modeシステム
n
仮定：Centralized/Decentralizedシステ
ムを評価しないといけない
Mobile Ad hoc Networks
∼ 事例３ ∼
n
評価基準は、どうあるべきか？
基準１∼５ぐらいを明記
n その理由を述べる！
n
© H. Tokuda, Keio University
4
無線アドホックネットワーク
n
アドホックネットワーク：応用例
アドホックネットワークとは？
n
n
ネットワーク･インフラが存在しない
n
• peer-to-peerでの通信スタイル
n
トポロジが人や物の動きと共に動的に変化する
n
Weak Connectivity
パーソナルエリアネットワーク
n
• ノードの移動、無線電波品質の変化
軍隊の (Military) 環境
n
n
• 常時接続の保証ではない
n
n
センサーネットワーク
n
n
n
n
対象データ
センサーノード設置点に関するデータ
センサーノード間を移動する物に関するデータ
ノード通信機能
n
Wireless sensor node
n
IrDA
• UC Berkeley MICA
• MIT Pin computing
• Smart Tags
n
タクシーネットワーク、ミーティングルーム、
スポーツスタジアム、ボート
緊急時の操作
n
センサー・デバイスネットワーク
兵士、戦車、戦闘機
一般市民の (Civilian) 環境
n
n
携帯電話、ラップトップ、時計
地震、洪水、竜巻
捜索と救出、警察や消防士
UC Berkeley MICA Motes
MICA Motes & Sensors
n Low power wireless sensor
network
n Smart Sensor
n Wireless Message Hopping
n Tiny OS
n
データ伝播機能
n
Comm. protocols for sensor nodes
Smart-Dust Prototypes
AT&T Cambridge: Piconet
The 5 mm2 of silicon costs approximately $0.30
to manufacture in quantities.
The inductor $.01, crystal $.15, and battery, $.16,
round out rest of the potential future node cost.
5
MIT Pushpin Computing Node
センサー・デバイスネットワークの課題
n
センサーノード配置問題
n
n
n
どのように配置するのか？
コストvs. 効率・精度
計算資源の制約
n
プログラムサイズ
n
実行時間
• コード・
データスペースの制限
• 非力なＣＰＵによる処理能力不足
n
n
n
n
消費電力節減問題
固定ノードvs. 動的ノード
Master Slave vs. P2P
Comm. protocols for sensor nodes
6