要約

  • directed diffusionは、固定した送信元を指定せず、属性で表したデータ要求を広げ、各ノードに期限付きgradientを作り、探索結果から一部の戻り道をreinforceした。
  • reinforceされた経路が示すのは選択指標の下で観測された転送性能であり、センサーの本人性、現象の真実性、観測の網羅性、加工前データの保存を保証しない。

消える記憶から始める

通常のIP通信では、どのホストへ送るかが先に決まる。1990年代末に想定された多数の小型センサーでは、順序が違った。利用者が知りたいのは特定番号の機械ではなく、ある場所である現象が起きたかどうかである。各ノードは電池と無線容量が限られ、全体を常に把握する中央装置も期待できない。

1999年の論文Next Century Challengesは、Deborah Estrin、Ramesh Govindan、John Heidemann、Satish Kumarの共同研究だった。近隣だけを見た単純な規則から全体として有用な協調を生む「localized algorithms」を論じている。EstrinはSCADDSの主要研究者の一人だが、directed diffusionを単独で発明したわけではない。MobiCom 2000版はChalermek Intanagonwiwat、Govindan、Estrinの共著で、2003年の論文にはHeidemannとFabio Silvaも加わる。同論文は、属性で名付けたデータをdiffuseする発想をVan Jacobsonが示唆したとも記している。

アプリケーションは欲しい情報を属性と値の組で表した。車両追跡の例なら、種類、地理的な矩形、更新間隔、継続時間である。このタスク記述がinterestになる。interestを出すノードはsinkと呼ばれるが、既知のセンサーのアドレスは指定しない。ネットワークに対し、一定の語彙で一致するデータを求める。

ここで証拠の限界が決まる。語彙が曖昧なら、正確な照合でも間違った問いに答え得る。応答がなければ、現象がなかった、対応センサーがなかった、interestが届かなかった、電池が切れた、状態が失効した、という複数の仮説が残る。無応答は「不存在」と同義ではない。

gradientはローカルな需要の向き

interestを受けたノードはそれをcacheし、どの隣接ノードから来たかを記憶する。その隣接方向に作る状態がgradientである。gradientには方向だけでなく、要求されるデータレートや有効期間も含められた。同じinterestが複数の隣接から届けば、複数のgradientが並ぶ。

interestの配送は信頼できるとは仮定されないため、sinkは周期的に更新する。timestampと期限が古い状態を消す。短い更新周期は変化への追随を高めるが、制御通信と電力を使う。長い周期は省電力でも、すでに誤った状態を残す。

gradientが証明するのは、あるノードが現在、ある隣接から届いた互換的な需要を覚えていることまでである。隣接ノードを認証せず、物理センサーを特定せず、end-to-endの連続経路を保証しない。運用証跡にはinterestの版、直近隣接、生成・更新・失効時刻、削除理由が必要になる。

探索と強化は別の局面

interestに一致するセンサーはsourceとなり、同じ属性体系でデータを作る。初期データは探索的に複数gradientを通ることができる。sinkは到着を比較し、好ましい隣接へpositive reinforcementを返す。各ノードが上流側で同じ選択を繰り返し、sourceまで強化された経路ができる。その後のデータは一つまたは少数の経路へ絞られる。

選択には最初に届いたcopyや低いlatencyが使われ得る。negative reinforcementは重複や遅い枝を弱め、定期的な探索は環境変化後の代替経路を見つける。これは全ネットワークを見渡した永久最適化ではなく、観測した挙動への局所的な適応である。

最初の到着は、あるsinkと時間窓における順番しか示さない。低遅延はsourceの真正性でも測定の正確さでもない。他経路のlossによって一つの経路だけが良く見える場合もある。通信を集中させれば、選ばれたrelayの電池を先に消費する可能性もある。

reinforcementは測定であると同時に資源配分である。選択された経路はより多くのtrafficを得て、より多く観測され、次にも選ばれやすい。経路性能と観測への信頼を分けなければ、早期の偶然が評判へ変換される。

集約後の値は履歴ではない

中間ノードはduplicate抑制、cache、変換、aggregationを行えた。無線送信が高価な環境では、近くで処理して送信回数を減らすことが重要だった。cacheはloopや同一messageの反復も抑えられる。

しかし、似た二件の報告が同一事象とは限らない。片方を消せば、重複を除いたことにも、独立した裏付けを失ったことにもなる。平均値は規則どおりでも、センサー間の不一致を隠す。sinkが受け取るのは有用な結果であって、全報告の逐語的な記録ではない。

したがってaggregationには、規則と版、入力・出力件数、時間窓、処理ノード、抑制理由、raw dataの回収可否を添える必要がある。このreceiptがなければ、結果は再利用できても、何を捨てたかは検証できない。

数値を条件から切り離さない

2003年論文は、遠隔監視または車両追跡の設定で分析、packet-level simulation、小規模platformによる評価を行い、対象条件で大きな省エネルギー効果を示した。あらゆるsensor workloadへの保証ではない。

Heidemann、Silva、Estrinによる後続研究は、単一の方式が全applicationに最適ではないと明記した。two-phase pull、one-phase pull、pushは、sourceとsinkの間で探索costを異なる形に配る。source数、sink数、event頻度、配置、地理的範囲、link asymmetryによって適否が変わる。field experimentで報告された40〜60%の差は、その試験条件で選択が重要だった証拠であり、普遍的な利得率ではない。

この歴史が残したものは、addressingの単純な置換ではない。欲しい情報の記述が一時的なnetwork stateを作り、用が終われば消えるという設計順序である。そして、意味の一致、pathの選択、観測を信じる判断を、別々に記録しなければならないという運用原則である。

出典