T a G-tiny-aggregation-service_usenix-2002

USNIX OSDI 2002

TAG: a Tiny AGgregation Service for Ad-Hoc Sensor Networks http://www.cs.berkeley.edu/~madden/madden_tag.pdf

Samuel madden, Michael J. Franklin UC Berkeley

0. 概要

低消費電力、分散、無線なセンサネットワーク上でセンサの属性とかを集約する ための手法であるTAGを提案した。

TAGは下記のような感じ

• SQL-likeな言語で表された集約queryをSensor Network上に流す
• 個々のセンサがもつデータがqueryに当てはまるかどうかを、それぞ れのSensorで調べる。
• 当てはまったデータを持つSensorだけ結果を返す
• 返る途中でどんどんデータが集まってくる(個々のSensorで集約する) Figure 2を見るとよくわかる。
• Centralized Approachに比べてトラフィックは軽減されたよ。

1. Introduction

小さいSensorとネットワークが最近はやってる。たとえば mote(http://www.spp.co.jp/sssj/motemica.html)がある。

moteの概要

• 2cm x 4cm x 1cm
• 無線、小さな電池、センサ
• TinyOS

TinyOSは、UC Berkleyが開発してるAd-Hoc Sensor Network用の少メモリOS。

世の中にはMoteを利用した研究がいくつか存在している。

• 地震の時のビルの挙動を見る研究("Smart buildings admit their faults", UC Berkeley LabNotes, 2001)
• 群集モニタリング("Wireless Sensor networks for habitat monitoring, ACM,2002")
• 大量のコンピュータの温度を見張る管理者

センサアプリケーションが使用するデータは生データではなく要約(集約)したデー タを用いる。いくつかの研究はセンサネットワークにおけるデータ集約の重要性 を示している。("Building ejjicient wireless sensor networks with low-level nameing", SOSP, 2001)

この先行研究は集約化をアプリケーション独自の機構(Cに似た低レベル言語とか で扱う)にしている。それに対して我々は集約化はシステムの"Core Service"と するべきだとしている。

C言語の拡張とかではなく、このサービスはもっと高度な抽象化をして扱うべき である。これによって、コンピュータの専門家以外の人も簡単に扱えるし、組み 込みOSとかハードウェアとかに依存することはなくなる。

1.1 The TAG Approach

TAG(Tiny AGgregation)を

このサービス(集約化サービス)には二つの欠けてはいけない属性がある。

• データセットおよび集約化に対するsimpleなインタフェース データベース言語とかの使い易いインタフェースとかね。
• 時間、消費電力を考慮した、Sensor Network上への集約化queryの配布 このとき、いらないデータは個々のSensorの時点で捨てて、本当に必要なデー タだけ集約するといいよね

1.2 Overview of the Paper

• SQL-likeな言語を使って集約queryを表現する。
• 集約queryをNetwork上に流して結果を得る。
• Centralized Approacheに対してどれぐらい軽減されたかの評価
• 高レベル言語が役に立つこと示す

2. motes and Ad-Hoc Networks

2.1 motes

AODVっぽいアルゴリズム

2.2 Ad-Hoc Routing Algorithm

Tree-based Routing Schemeらしい。

3. Query Model and Environment

SQL-styleなqueryを使用(joinは除く)

例:
	SELECT AVG(volume), room FROM sensors
	  WHERE floor = 6
	  GROUP BY room
	  HAVING AVG(volume) > threashold
	  EPOCH DURATION 30s

普通のSQLとTAGが違うところは、TAGの結果はStream valueとして出てくること。 こういう継続的なデータの方が便利。

3.1 Structure of Aggregates

たくさんノードがあるネットワークでは、構造化というのが必要("Adaptive parallel aggregatin algorithms", ACM SIGMOD,1995)。TAGでは三つの手法を使っ て実現。

3.2 Taxonomy(分類法) of Aggregates

• Distributive aggregates
• Algebraic aggregates
• Holisti aggregates
• Unique aggregates
• Content-Sensitive aggregates

4 In Network Aggregates

4.1 Tiny Aggregation

TAGは二つのphaseから成る

• distribution phase
• collection phase

Distribution Phaseの前にあらかじめTreeを形成しておく。

Collection phaseの時、Aggregation Queryを受け取ったsensor Node(Node Aと する) はデータをTreeの親に返す。

このとき、データが返っていく途中のSensor Node(Node Bとする)でも、Queryに 当てはまるデータがある(こともある)。その場合、そのNode Bの次にデータが返 るSensor Node(Node Cとする)には、Node AのデータとNode Bのデータの両方が 返ってくる。

もしもNode CのデータもQueryに当てはまったら、Node Cのデータも付け加えて 返す。この繰り返す。

4.2 Grouping

Figure 2を見ればよくわかる。

でも、Groupingには問題もある。Groupingしすぎると、途中のノード(枝ではな いノード)のstrageがパンクする可能性がある。これを避けるための我々のアプ ローチは、一つ以上のグループを選んで、local Strageから親に向けて追い出す こと。

4.3 Additional Advantages of TAG

TAGの一番の利点は、トラフィックを軽減すること。でも、そのほかにもいくつ か利点がある。

1つ目の利点は切断とlossに耐性があること。

2つ目の利点は通常は、一番上のノードはたくさんデータを処理(Query発信元に 送信)しなければならないから電力消費が激しいけど、TAGなら少なくてすむ。

最後の利点として、TAGは時間軸でスロット(epoch)を分割するので、processer のidlingと相性がいい。

5. Simulation-Based Evaluation

javaで実装(Simulation)した。

2500のdevice、50のネットワークで、3つのシナリオを試した。

5.1 performance of TAG

5.2 Grouping Expreriments

6. Optimizations

6.1 Taking Advantage of A Shared Channel

6.2 Hypothesis(仮説) Testing

7. Improving Tolerance to Loss

7.1 Topology maintenance and Recovery

もしも、親から見放されたら子は新しい親を選ぶ。

7.2 Effects of A Single Loss

7.3 Effect of Realistic Communication

7.4 Child Cache

Aggregationの効果を向上させるために、simple caching schemeも提案する。

親は、ある一定期間における子の(不完全な)データを記憶しておく。くるはずの 子のデータがこなかったらそのデータを使う。

子が新しい親を選ぶまでの時間より、親がデータを記憶しておく時間のほうが短 ければ、この手法は重複することなく使用可能なデータを増やすことができる。

その実験も行ったよ。

7.5 Using Available Redundancy

8. Prototype Implementation

以上のimprove techniqueを使用したプロトタイプ実装をTiny OS Mica上で行っ た。

9. Related Work

10. Conclusions