(57)【特許請求の範囲】
【請求項１】
ネットワークに接続されたセンサを含む環境内のユーザの移動をモデル化する方法であって、前記方法はプロセッサによって実行され、前記センサの検知様式は、赤外線、熱、超音波、光、レーダ、ソナー、マイクロ波、圧力、オン−オフスイッチ、およびこれらの組み合わせからなる群から選択され、
前記センサにおいて、ユーザの移動に伴って生じる前記検知様式に対応する物理量の変化である事象を検出すること、
各事象を、特定のセンサおよび該事象の時刻に応じてラベル付けすること、
各センサの事象を合計して、ヒストグラムにおける対応する時間間隔のビンに関連付けること、
前記ヒストグラムから次式に従って複数の同時生起行列を生成すること
【数１】
0004754800.tif 000006
ここで、ｉおよびｊは考えられる各センサ対を表し、δは時間のずれを表し、Ｔは検
出の合計時間であり、ｔは特定の時刻を表し、Ｈは前記ビンに関連付けられた事象の 総数を表す
を備え、
特定のセンサが未来の活動に関する事象を検出し、
前記同時生起行列から、終了事象が生じる確率分布を、前記特定のセンサ以外の全ての他のセンサによって検出された事象に基づいて求めること、
前記確率分布の和をとることによって、前記事象の検出中に、前記終了事象を検出する前に前記未来の活動が生じる確率を予測すること
をさらに備える
環境内のユーザの移動をモデル化する方法。
【請求項２】
前記環境は、建物の内部である
請求項１に記載の方法。
【請求項３】
前記環境は、オープンスペースである
請求項１に記載の方法。
【請求項４】
前記ネットワークは、有線である
請求項１に記載の方法。
【請求項５】
前記ネットワークは、無線である
請求項１に記載の方法。
【請求項６】
前記ネットワークは、有線および無線のセンサを含む
請求項１に記載の方法。
【請求項７】
前記センサは、前記事象の検出に１ビットの分解能を有する
請求項１に記載の方法。
【請求項８】
前記センサは、前記環境においてアドホックな任意のパターンでグローバルに分散される
請求項１に記載の方法。
【請求項９】
いくつかのセンサの範囲は、重複しない
請求項１に記載の方法。
【請求項１０】
他のセンサ毎に１つの分布がある
請求項１に記載の方法。
【請求項１１】
ネットワークに接続されたセンサを含む環境内のセンサネットワークのジオメトリをモデル化する方法であって、前記方法はプロセッサによって実行され、前記センサの検知様式は、赤外線、熱、超音波、光、レーダ、ソナー、マイクロ波、圧力、オン−オフスイッチ、およびこれらの組み合わせからなる群から選択され、
前記センサにおいて、ユーザの移動に伴って生じる前記検知様式に対応する物理量の変化である事象を検出すること、
各事象を、特定のセンサおよび該事象の時刻に応じてラベル付けすること、
各センサの事象を合計して、ヒストグラムにおける対応する時間間隔のビンに関連付けること、
前記ヒストグラムから次式に従って複数の同時生起行列を生成すること
【数２】
0004754800.tif 000007
ここで、ｉおよびｊは考えられる各センサ対を表し、δは時間のずれを表し、Ｔは検
出の合計時間であり、ｔは特定の時刻を表し、Ｈは前記ビンに関連付けられた事象の 総数を表す
を備え、
考えられる各センサ対について、該センサ対間の距離を求めること、
前記距離を前記センサのジオメトリにマッピングすること
をさらに備える
環境内のセンサネットワークのジオメトリをモデル化する方法。
【請求項１２】
前記合計した事象はピークを含み、各ピークは特定のセンサ対間の相対的な時間のずれを反映する
請求項１１に記載の方法。
【請求項１３】
前記求めることは、
所定時間にわたる前記ユーザの移動の一定の平均速度を前記センサ対間の前記相対的な時間のずれに適用すること
をさらに含む
請求項１２に記載の方法。
【請求項１４】
前記マッピングすることは、多次元尺度構成法を用いる
請求項１１に記載の方法。
【請求項１５】
応力測度
【数３】
0004754800.tif 000008
ここで、ｆ（ｉｊ）は非計量的な単調変換である
を用いて特定のジオメトリが推定距離と一致する可能性を評価すること
をさらに含む
請求項１４に記載の方法。
【請求項１６】
前記応力測度は、前記センサ対間の距離を順位付けする
請求項１５に記載の方法。
【請求項１７】
環境内のユーザの移動をモデル化するシステムであって、
前記環境全体に分散され、検知様式が、赤外線、熱、超音波、光、レーダ、ソナー、マイクロ波、圧力、オン−オフスイッチ、およびこれらの組み合わせからなる群から選択され、ユーザの移動に伴って生じる物理量の変化である事象を検出し、特定のセンサが未来の活動に関する事象を検出する複数のセンサと、
前記センサによって検出された事象を、特定のセンサおよび該事象の時刻に応じてラベル付けする手段と、
各センサの事象を合計して、ヒストグラムにおける対応する時間間隔のビンに関連付ける手段と、
前記ヒストグラムから次式
【数４】
0004754800.tif 000009
ここで、ｉおよびｊは考えられる各センサ対を表し、δは時間のずれを表し、Ｔは検
出の合計時間であり、ｔは特定の時刻を表し、Ｈは前記ビンに関連付けられた事象の 総数を表す
に従って複数の同時生起行列を生成する手段と
を備え、
特定のセンサが未来の活動に関する事象を検出し、
前記同時生起行列から、終了事象が生じる確率分布を、前記特定のセンサ以外の全ての他のセンサによって検出された事象に基づいて求める手段と、
前記確率分布の和をとって、前記事象の検出中に、前記終了事象を検出する前に前記未来の活動が生じる確率を予測する手段と
をさらに備える
環境内のユーザの移動をモデル化するシステム。
【請求項１８】
環境内のセンサネットワークのジオメトリをモデル化するシステムであって、
前記環境全体に分散され、検知様式が、赤外線、熱、超音波、光、レーダ、ソナー、マイクロ波、圧力、オン−オフスイッチ、およびこれらの組み合わせからなる群から選択され、ユーザの移動に伴って生じる物理量の変化である事象を検出し、特定のセンサが未来の活動に関する事象を検出する複数のセンサと、
前記センサによって検出された事象を、特定のセンサおよび該事象の時刻に応じてラベル付けする手段と、
各センサの事象を合計して、ヒストグラムにおける対応する時間間隔のビンに関連付けること、
前記ヒストグラムから次式
【数５】
0004754800.tif 000010
ここで、ｉおよびｊは考えられる各センサ対を表し、δは時間のずれを表し、Ｔは検
出の合計時間であり、ｔは特定の時刻を表し、Ｈは前記ビンに関連付けられた事象の 総数を表す
に従って複数の同時生起行列を生成する手段と
を備え、
考えられる各センサ対について、該センサ対間の距離を求める手段と、
前記距離を前記センサのジオメトリにマッピングする手段と
をさらに備える
環境内のセンサネットワークのジオメトリをモデル化するシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはセンサネットワークに関し、特にセンサネットワークを用いて物体のトラフィックをモデル化するとともに、センサネットワークのジオメトリをモデル化することに関する。
【背景技術】
【０００２】
環境のユーザは、その環境が包囲された建物であれ、オープンスペースであれ、都市および地方の道路であれ、ユーザが環境内を動き回るのに伴って、移動パターンを動的に生成する。ユーザは、人、車両、または他の移動物体である可能性がある。
【０００３】
しかし、そのような環境用の自動化システム（例えば暖房、冷房、照明、エレベータ、安全、トラフィック制御のシステム）はほとんど、ユーザ（例えば建物の居住者、車両、または他の移動物体）に対する動作を動的に調整するために移動パターンを考慮しない。
【０００４】
せいぜい、エレベータシステムが、朝は上昇トラフィック、夕方は下降トラフィックを優先させる事前にプログラムされたスケジュールを有する場合がある。同様に、ＨＶＡＣシステムは、様々な事前にプログラムされた日中および夜間の動作設定を有する場合がある。信号機も事前にプログラムされることができる。局所的な移動に応答するセンサを含む自動化器具等のデバイスもいくつかある。しかし、ほとんどのシステムは通常、環境内の大規模な移動パターンに敏感でない。
【０００５】
環境内にセンサネットワークを設けて、環境内のユーザの移動パターンすなわちトラフィックの流れを求めることができることが望ましい。さらに、既知のユーザパターンに基づいてユーザの未来の活動を予測することが望ましい。
【０００６】
静的なおよびアドホックなセンサネットワークが既知である。アドホックなセンサネットワークを用いることが好ましい。これにより、環境の構成および使用パターンが時間を経て変化するのに伴ってセンサを再配置することが容易になる。したがって、センサは、現在または未来の使用パターンに適応させることができる。
【０００７】
しかし、いずれの場合にも、センサによって取得したデータを場所特有の解析に有用なものとするには、環境に関するセンサのジオメトリを求めることが必要である。ジオメトリはセンサ間の空間関係を定める。これは、センサ自体のみを用いて自動的かつ受動的に行うことが望ましい。
【０００８】
Nissanka等著「The cricket location-support system」（Proc. of the Sixth Annual ACM International Conference on Mobile Computing and Networking, August 2000）は、超音波信号を計時してセンサの場所を求めるセンサネットワークを記載する。これは、特別なコンポーネントおよび処理を用いる能動的なシステムである。ＲＦ信号に基づく他の同様の技法が、LaMarcal等著「Plantcare: An investigation in practical ubiquitous systems」（Fourth International Conference on Ubiquitous Computing, 2002）、および２００３年８月２６日付で出願されたSahinogluの米国特許出願第０９／６４９，７５９号「Location Estimation in Partially Synchronized Networks」に記載される。これらのシステムは比較的複雑である。多くの応用について、ネットワーク内のセンサジオメトリの分解能は本来、従来技術の解決策に伴うコストと複雑性に値しない。
【０００９】
従来技術では、移動パターンを求めるために追跡データが用いられてきた。W.E.L. Grimson等著「Using adaptive tracking to classify and monitor activities in a site」（IEEE CVPR, June 1998）、およびJohnson等著「Learning the distribution of object trajectories for event recognition」（Image and Vision Computing, 14(8), 1996）を参照。これらの方法は、所定時間にわたる環境内の特定の物体の追跡および識別を必要とする。
【００１０】
ジョージア工科大学のＡｗａｒｅ Ｈｏｍｅプロジェクトは、比較的忠実度の低いモデルから挙動を理解しようとする同様のイディオムに従う。Kidd等著「The aware home: A living laboratory for ubiquitous computing research」（Proceedings of Second International Workshop on Cooperative Buildings, October 1999）を参照。この研究もまた、環境内のパターン情報を求めるために特定の個々の物体またはユーザの追跡データを必要とする。
【００１１】
従来技術では、環境における事象予測もまた、特定の物体の追跡データを必要とした。Feldman他に対して２００３年７月１日付で発行された米国特許第６，５８７，７８１号を参照。この方法は、様々な情報源から取得した膨大なトラフィックデータに処理ステップを適用する前に、そのデータに対して優先順位付け、フィルタリング、および制御を行うことを必要とし、環境のジオメトリが既知でなくてはならない。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
センサネットワークを用いてトラフィックの流れをモデル化することが望ましい。これは受動的に、かつ特定の物体に関する事象を識別せずに行われることが望ましい。また、トラフィックの流れに基づいて未来の活動を予測することが望ましい。さらに、同様の方法でセンサネットワークのジオメトリを求めることが望ましい。
【課題を解決するための手段】
【００１３】
本発明による方法は、ネットワークに接続されたセンサを含む環境内のユーザの移動をモデル化する。ユーザの移動による事象はセンサにおいて検出され、各事象は、特定のセンサおよび事象の時刻に応じてラベル付けされる。各センサの事象は合計され、対応するヒストグラムの時間間隔ビンに入れられる。ヒストグラムから
【００１４】
【数１】
0004754800.tif 000002
【００１５】
ここで、ｉおよびｊは考えられる各センサ対を表し、δは時間のずれを表し、Ｔは検
出の合計時間であり、ｔは特定の時刻を表し、Ｈはヒストグラムの時間間隔ビンを表
す。
【００１６】
に従って複数の同時生起行列が生成される。
【００１７】
考えられる各センサ対について、センサ対間の距離を求め、この距離をセンサのジオメトリにマッピングする。
【００１８】
同時生起行列は、ネットワークのジオメトリを求めるため、および終了事象によって信号で知らされる未来の活動を予測するために用いることができる。
【発明を実施するための最良の形態】
【００１９】
トラフィックのモデル化
システム構造
図１Ａは、本発明による、センサネットワーク内のトラフィックパターンをモデル化するとともに、センサネットワークのジオメトリをモデル化するシステム１００を示す。システム１００は、環境１０５内に複数のセンサ１１０〜１１６を含む。応用例において、環境１０５はオフィスビルであり、センサは廊下、ロビー、エレベータの待合エリア、休憩室、出入口等といったトラフィックエリアに配置される。
【００２０】
図１Ｂは、建物の間取り図を示す。番号を付けた円は出入口１５１を示し、黒丸はセンサ１５２を示す。３とラベル付けされた出入口１５３はエレベータのドアである。センサ１５４はエレベータホールの呼びボタンである。
【００２１】
センサ１１０〜１１６はコントローラ１２０に接続される。接続は有線または無線、例えばＩＥＥＥ−１３９４ネットワークとすることができる。
【００２２】
好ましい実施の形態において、センサは極めて低い分解能を有する。例えばセンサは、１ビットを用いてしか事象を検出し報告することができない。
【００２３】
したがって、事象は単なるブール事象である。検出されたユーザの動きの方向、速度およびアイデンティティに関する補助情報は必要ない。また、あるセンサから別のセンサまでユーザを追跡する必要はない。
【００２４】
検知様式の例としては、赤外線、熱、超音波、光、レーダ、ソナー、マイクロ波、および圧力がある。あるいは、センサは単純な電気的オン−オフスイッチとすることもできる。例えば、光スイッチがオンになること、エレベータボタンを押すこと、器具をオンにすることが検知事象となり、環境内のセンサに近いユーザを示すことができる。
【００２５】
センサは、センサの範囲内で生じる「事象」を検出することを可能にするような方向に向けられている。例えば、センサは天井に取り付けられて、廊下の縦軸と整列している。
【００２６】
特徴として、センサは低分解能であり、例えば論理０は事象がないことを示し、論理１は事象が検出されたことを示す。センサは、環境においてアドホックな任意のパターンでグローバルに分散される。センサの範囲は重複する必要はない。センサの範囲は様々であってよい。環境における事象の検出に使用される方法も様々であってよい。
【００２７】
コントローラ１２０は、互いに結合されたプロセッサ、メモリ、Ｉ／Ｏインタフェースおよび周辺デバイスを含む。プロセッサは、以下で図２を参照してさらに詳細に説明するような、本発明によるジオメトリを定める方法を実施するオペレーティングシステムおよびアプリケーションプログラムを実行する。
【００２８】
システム動作
システム１００の動作には、ユーザ１０１が環境１０５内で移動する１０２ことが必要である。ユーザは、人、車両、または他の移動物体である可能性がある。ユーザが移動するに伴い、様々なセンサが作動され、ユーザがセンサに近づく様々な時刻で「事象」が検出される。
【００２９】
事象間の時間のずれを用いて、特定の環境ではユーザは略一定の速度で移動すると仮定して距離を推定する。したがって、推定距離から計算されたジオメトリは縮尺まで比較的正確である。しかし、システムは個々のユーザの認識と追跡を必要とせず、システムが検出した事象は任意の特定のユーザと関連付けられないことを理解すべきである。
【００３０】
図２は、センサネットワーク１００によって検出された事象に基づいて自動的にモデル化を行う方法２００を示す。センサが、事象２０１を環境１０５内で検出する２１０。各事象を、検出センサｉおよび事象の時刻ｔに応じてラベル付けする２２０。ラベル付けした事象２２１を、検出した事象のリスト２３１に追加する２３０。事象リストはＥ（ｉ，ｔ）＝｛０，１｝の形態である。
Ｅｉ，ｔ＝｛０，１｝                                                （１）
【００３１】
事象リスト２３１中の特定のエントリは、動き事象がｉ番目のセンサによって時刻ｔに検出された場合にのみ真（１）である。事象はブール事象であり、センサの範囲内のどこかにおける何らかの動きの存在を示すに過ぎず、ユーザの数、ユーザのアイデンティティ、ならびに動きの方向および速度、または任意の他の二次情報は示さないことに留意すべきである。
【００３２】
センサが、リスト中のラベル付けした事象を所定の時間間隔「ビン」について合計して２４０、ヒストグラム３００に入れる。このヒストグラム３００は、後述のような同時生起行列Ｃｉ，ｊ，δ２５１を作成する２５０ために用いる。ここで、ｉおよびｊは２つのセンサであり、δはセンサｉおよびセンサｊにおける２つの事象間の時間のずれである。同時生起行列は、本発明による検出事象の基本モデルである。この基本モデルは、いくつかの異なる応用に用いることができる。
【００３３】
ネットワークジオメトリのモデル化
１つの応用において、モデルは、ネットワークのジオメトリを求めるために用いる。ジオメトリはセンサ間の空間関係を定める。
【００３４】
センサ間距離ｄｉ，ｊ２６１を同時生起行列２５１から推定する２６０。距離は時間のずれから、環境内の大きな時間間隔にわたる移動は略一定であると仮定して推定する。次に距離２６１を、センサのネットワークのジオメトリ２７１にマッピングする２７０。
【００３５】
図３は、例示的なヒストグラム３００を示す。各ビン３０１〜３０９は、特定のセンサｉが０．５秒の時間間隔中に検出した全ての事象の合計を表す。事象ヒストグラムのエントリＨｉ，ｔは、センサｉからの時間間隔ビンｔ中の検出事象の総数である。
【００３６】
次式に従って、ある範囲の時間のずれδにわたりセンサｉおよびｊの対で比較を行うことによって、個々のヒストグラムのエントリを用いて同時生起行列２５１を作成する。
【００３７】
【数２】
0004754800.tif 000003
【００３８】
ここで、ｉおよびｊは比較するセンサであり、δはずれであり、図４では１．５秒のずれの場合を示す。
【００３９】
図５は、センサｉの同時生起行列の事象の和を、センサｊ〜ｐの同時生起行列の事象の和と、３０秒のずれの範囲にわたって比較する。図５において、時間は左から右へ進む。同時生起行列のピーク５０１〜５０６は、センサｉとそれぞれのセンサｊ〜ｐにおける検出事象間の相対的な時間のずれを反映する。長い時間間隔にわたって、ピークは、大多数のユーザがセンサｉから次のセンサｊ〜ｐまで移動するのにかかる平均「通過」時間５１１〜５１６で生じる。
【００４０】
通過時間５１１〜５１６を用いて、対応するセンサ間の距離ｄ２６１を求める。次にこの距離を、スケーリングされたセンサのジオメトリ２７１にマッピングする２７０。
【００４１】
好ましい実施の形態では、多次元尺度構成法（ＭＤＳ）を用いて距離をジオメトリにマッピングする。例えば、Steyvers著「Multidimensional Scaling」（Encyclopedia of Cognitive Science, Macmillan Reference Ltd. 2002）を参照。ＭＤＳは概して、物体（例えばセンサ）を、距離の制約下で所定の次元数（例えば２）を有する空間に配置する。
【００４２】
「応力」の測度Φを用いて、特定のジオメトリが推定した距離と一致する可能性を、次式に従って評価することができる。
【００４３】
【数３】
0004754800.tif 000004
【００４４】
ここで、ｆ（ｉｊ）は非計量的な単調変換である。応力の測度を用いて、センサ間の距離を順位付けする。
【００４５】
距離の偏差の二乗和、またはそれらの距離の何らかの単調変換を用いた測度等の他の同様の測度も用いることができる。概して、応力の測度が小さいほど、推定されるジオメトリが、センサによって観察される実際の物理的なジオメトリを正確に反映する可能性は高くなる。ユーザの推定速度を適用することによって、ジオメトリを実世界の寸法にスケーリングすることができる。
【００４６】
本明細書中に記載する本発明による同時生起行列は、主に、センサネットワークのジオメトリを求めるために用いられる。しかし、同時生起行列は、環境内のユーザの移動のいくつかの一般的なグローバルならびにローカルな特徴を取り込むことに留意すべきである。したがって、同時生起行列は、他の有用な応用にも用いることができる。
【００４７】
活動の予測
図６に示すように、同時生起行列は、また、未来の活動６２０を予測するために用いることができる。本発明によれば、活動の開始は終了事象によって信号で知らされる。例えば、検出される事象は、図１Ｂのホールおよびホワイエエリアで移動するユーザである。終了事象は、ユーザがエレベータボタン１５４を押すことによって信号で知らされるホール呼びである。活動は、エレベータかごがユーザを運搬するようにスケジュールすることである。
【００４８】
解決すべき課題は、ユーザがホール呼びボタン１５４を押す前にエレベータかごのスケジュール活動を予測することである。この活動を高い信頼レベルで予測できれば、ユーザが呼びボタンを押す前にエレベータを送ることができる。これにより時間が節約される。
【００４９】
過去のいくらかの時間間隔ｔ＜Ｔ０について同時生起行列２５１が与えられた場合、課題は、特定の活動に関連する終了事象が検出される前にその活動を予測することである。この課題は、同時生起行列２５１が与えられた場合に活動Ａに関連する特定の終了事象Ｅｔｅｒｍが特定の時刻に生じる確率として言い換えることができる。
【００５０】
この確率を求める一方法は、全ての他の検出事象に対するそれぞれの終了事象の確率分布の和をとることである６１０。同時生起行列はこれを、事象と終了事象の間の時間のずれをパラメータ化することによって可能にする。
【００５１】
図７に示すように、活動予測の目的で、同時生起行列の時間のずれは確率分布として解釈される。確率分布は、予測すべき活動に関連する終了事象から時間を遡ることによって解析される。
【００５２】
図７において、終了事象を、センサｉが時刻ｔｅ７００において検出する。確率分布７１０は、時刻７０２をピークとするいくらかの時間のずれ７０１の場合に、センサｊが検出する事象の後に終了事象が続く可能性を示す。同様に、時刻７０４をピークとする分布７１１によって示される時間のずれ７０３の場合に、センサｌが検出する事象の後に終了事象が続く。
【００５３】
図８は、時間を整列させた後の分布７１０〜７１１の正規化した和８００を示す。実質上、和８００は、センサｊにおいて時間のずれ７０２で事象が検出され、かつセンサｌにおいて時間のずれ７０４で別の事象が検出された場合に終了事象が生じる可能性をモデル化する。これは数学的には次のように表すことができる。
【００５４】
【数４】
0004754800.tif 000005
【００５５】
ｔ０＞ｔｅと設定し、確率をしきい値と比較することによって、未来の所定の時間について活動の可能性を予測する。
【００５６】
図９は、１〜１６秒のタイムラグの場合の、本発明に従って活動を予測する方法の受信機の動作特性（ＲＯＣ）曲線を示す。
【００５７】
本発明を好ましい実施の形態の例として記載してきたが、本発明の精神および範囲内で様々な他の適応および修正を行うことができることが理解されるべきである。したがって、併記の特許請求の範囲の目的は、本発明の真の精神および範囲に入る変形および修正をすべて網羅することである。
【図面の簡単な説明】
【００５８】
【図１Ａ】本発明を用いることができるセンサネットワークのブロック図である。
【図１Ｂ】本発明を用いることができるセンサネットワークを有する建物の間取り図である。
【図２】本発明による、センサネットワークのジオメトリをモデル化する方法のフロー図である。
【図３】所定時間にわたって検出された事象のヒストグラムである。
【図４】ある時間のずれにおけるセンサヒストグラムの比較を示す図である。
【図５】同時生起行列からセンサ間距離を求めることを示す図である。
【図６】本発明による、未来の活動を予測する方法のフロー図である。
【図７】検出事象と終了事象の間の時間のずれを比較する図である。
【図８】予測事象の確率分布の和を示す図である。
【図９】本発明の結果のＲＯＣ曲線である。
【図１Ａ】
0004754800.tif 000011
【図１Ｂ】
0004754800.tif 000012
【図２】
0004754800.tif 000013
【図３】
0004754800.tif 000014
【図４】
0004754800.tif 000015
【図５】
0004754800.tif 000016
【図６】
0004754800.tif 000017
【図７】
0004754800.tif 000018
【図８】
0004754800.tif 000019
【図９】
0004754800.tif 000020