(57)【要約】【課題】無線ネットワークにおけるある無線機器の自己位置を特定する、協調位置特定技術を用いたシステムを提供する。【解決手段】無線ネットワークにおける少なくとも１つの他の無線機器からある無線機器が受信する信号の関数として任意の信号メトリックを推定する。このシステムではまた、少なくとも１つの他の無線機器の少なくとも１つの可能性のある位置の分布を表す、少なくとも１つの信念を変換して、少なくとも１つの変換後信念を生成する。このシステムではさらに、少なくとも１つの変換後信念の関数として自己信念を決定し、無線ネットワークにおける自己信念の関数として自己位置を特定する。【選択図】図６
2010507985.tif 000002
【特許請求の範囲】
【請求項１】
ある無線機器が無線ネットワークにおいて自己位置を特定する方法であって、
前記無線ネットワークにおける前記ある無線機器の少なくとも１つの可能性のある位置の分布を表す少なくとも１つの変換後信念を計算する工程であって、前記少なくとも１つの変換後信念は、少なくとも１つの他の無線機器から前記ある無線機器により受信される無線信号に関連する任意の信号メトリックの関数である、変換後信念計算工程と、
前記少なくとも１つの変換後信念の関数として自己信念を決定する、自己信念決定工程と、
前記無線ネットワークにおいて、前記自己信念の関数として自己位置を特定する、自己位置特定工程とを備えた、無線機器の位置特定方法。
【請求項２】
請求項１において、前記無線ネットワークの物理的構成が時間的に変化する、無線機器の位置特定方法。
【請求項３】
請求項１において、複数の他の無線機器から構成される少なくとも１つのあるサブセットが、複数の他の無線機器から構成される少なくとも１つの他のサブセット対して移動するものである、無線機器の位置特定方法。
【請求項４】
請求項１において、複数の他の無線機器から構成される少なくとも１つのあるサブセットは、第１タイプの前記任意の信号メトリックを推定し、複数の他の無線機器から構成される少なくとも１つの他のサブセットは、第２タイプの前記任意の信号メトリックを推定する、無線機器の位置特定方法。
【請求項５】
請求項４において、前記任意の信号メトリックが、前記少なくとも１つの他の無線機器に対する前記ある無線機器の特性を計算するのに用いられ、前記特性は、角度、距離、接続性、位置、姿勢、速度および角速度の情報からなるグループから選択される、無線機器の位置特定方法。
【請求項６】
請求項４において、前記第１タイプの前記任意の信号が、前記第２タイプの前記任意の信号と比較して非対称である、無線機器の位置特定方法。
【請求項７】
請求項１において、前記少なくとも１つの信念を変換する工程と、前記自己信念決定工程とは、因子グラフ定理に基づいている、無線機器の位置特定方法。
【請求項８】
請求項１において、前記少なくとも１つの信念を変換する工程は、前記任意の信号メトリックを推定することに関する機能を自己評価する工程を有する、無線機器の位置特定方法。
【請求項９】
請求項１において、前記自己信念を変換する工程は、さらに、先に決定された自己信念を更新する工程、または、新たな自己信念を決定する工程を有する、無線機器の位置特定方法。
【請求項１０】
請求項１において、さらに、前記無線ネットワークにおいて、前記少なくとも１つの他の無線機器の位置を特定する工程を有する、無線機器の位置特定方法。
【請求項１１】
請求項１において、前記分布は、確率密度関数または確率質量関数である、無線機器の位置特定方法。
【請求項１２】
無線ネットワークにおいてある無線機器の自己位置を特定する位置表示装置であって、
前記無線ネットワークにおける前記ある無線機器の少なくとも１つの可能性のある位置の分布を表す少なくとも１つの変換後信念を計算する計算部であって、前記少なくとも１つの変換後信念は、少なくとも１つの他の無線機器から前記ある無線機器により受信される無線信号に関連する任意の信号メトリックの関数である、計算部と、
前記少なくとも１つの変換後信念の関数として自己信念を決定する自己信念決定部と、
前記無線ネットワークにおいて、前記自己信念の関数として自己位置を特定する自己位置特定部とを備えた、位置表示装置。
【請求項１３】
請求項１２において、前記無線ネットワークの物理的構成が時間的に変化する、位置表示装置。
【請求項１４】
請求項１２において、複数の他の無線機器から構成される少なくとも１つのあるサブセットが、複数の他の無線機器から構成される少なくとも１つの他のサブセットに対して移動し、
前記計算部、前記自己信念決定部および前記自己位置特定部が、さらに移動性を考慮に入れる、位置表示装置。
【請求項１５】
請求項１２において、複数の他の無線機器から構成される少なくとも１つのあるサブセットの各計算部は、第１タイプの前記任意の信号メトリックを推定し、前記少なくとも１つの他の無線機器から構成される少なくとも１つの他のサブセットの各計算部は、第２タイプの前記任意の信号メトリックを推定する、位置表示装置。
【請求項１６】
請求項１５において、前記任意の信号メトリックが、前記少なくとも１つの他の無線機器に対して前記ある無線機器の特性を測定し、前記特性は、角度、距離、接続性、位置、姿勢、速度および角速度の情報からなるグループから選択される、位置表示装置。
【請求項１７】
請求項１５において、前記第１タイプの前記任意の信号が、前記第２タイプの前記任意の信号と比較して非対称である、位置表示装置。
【請求項１８】
請求項１２において、前記変換部は、因子グラフ原理に基づいて、前記少なくとも１つの信念を変換し、前記自己信念決定部は、因子グラフ原理に基づいて、前記自己信念を決定する、位置表示装置。
【請求項１９】
請求項１２において、前記計算部はさらに、前記任意の信号メトリックを推定することに関する機能を自己評価する、位置表示装置。
【請求項２０】
請求項１２において、前記自己信念決定部はさらに、先に決定された自己信念を更新するか、または新たな自己信念を決定する、位置表示装置。
【請求項２１】
請求項１２において、前記自己位置特定部はさらに、前記無線ネットワークにおいて、少なくとも１つの他の無線機器の位置を特定する、位置表示装置。
【請求項２２】
請求項１２において、前記分布は、確率密度関数または確率質量関数である、位置表示装置。
【請求項２３】
内部に記憶されたコンピュータプログラムを有するコンピュータプログラム製品であって、無線ネットワークにおけるある無線機器のプロセッサによって実行されると、
前記無線ネットワークにおける前記ある無線機器の少なくとも１つの可能性のある位置の分布を表す少なくとも１つの変換後信念を計算する手順であって、前記少なくとも１つの変換後信念は、少なくとも１つの他の無線機器から前記ある無線機器により受信される無線信号に関連する任意の信号メトリックの関数である、計算手順と、
前記少なくとも１つの変換後信念の関数として自己信念を決定する、自己信念決定手順と、
前記無線ネットワークにおいて、前記自己信念の関数として自己位置を特定する、自己位置特定手順とを、前記プロセッサに実行させる命令によって前記コンピュータプログラムが定義されているコンピュータプログラム製品。
【発明の詳細な説明】
【関連出願】
【０００１】
本願は、発明の名称「ＵＷＢネットワークにおける協調位置特定」の、2006年10月25日付で出願された、米国特許仮出願番号第60/854,393号の利益を主張する。上記出願の全教示は参照により本明細書に引用したものとする。
＜連邦政府による資金提供を受けた研究開発の記載＞
【０００２】
本発明は、認可番号第ECCS-0636519およびANI−0336518に従って米国科学財団によって、ならびに認可番号第N00014-03-1-0489に従って米国海事研究局よって、全体または部分的に支援された。米国政府は、本発明に一定の権利を有する。
【技術分野】
【０００３】
本発明は、無線ネットワークにおける協調位置特定（cooperative localization）に関する。
【背景技術】
【０００４】
位置認識技術は、コンピュータ、携帯電話サービス、センサネットワーク、および他の多くの商業・軍事・社会的用途に大変革をもたらす可能性がある。位置特定を利用して、ネットワーク内の無線機器の位置を見つけることができる。ネットワークは、エージェントとして知られるかなりの数の無線機器、および多数のアンカを有する場合がある。アンカ（例えば、セルラ基地局）は、一般には、ネットワーク内における自己位置について何らかの情報を有するが、これに対して、エージェントは、一般には、ネットワーク内における自己位置についてほとんどまたは全く情報を有しないことが多い。
【０００５】
ネットワーク内のエージェントの位置を判定する既知の技術として、集中型位置特定がある。この集中型位置特定では、ネットワーク内の各ノード（例えばアンカおよびエージェント）は、各ノードの相対的な位置特定測定の集合を中央処理装置にルーティングする。中央処理装置は、例えば測定値セットの最適化関数を採用することによって、各ノードから得られた測定値セットを用いてネットワーク内の全ノードの位置を判定する。
【０００６】
現在の位置特定方法のほとんどは、非協調位置特定と称される別の既知の位置特定技術を利用する。非協調位置特定方法では、エージェント間に何ら通信がなく、エージェントとアンカの間にのみ通信が存在する。位置特定処理の間、エージェントは、自己の位置を判定するために３つのアンカとの通信範囲内に位置する必要がある。したがって、エージェントがその位置を見つけるためには、各エージェントがその位置を判定するのに十分なデータにアクセスすることを保証するように、多数のアンカを用いる必要がある。これより、全てのエージェントの位置を見つけるために、非協調位置特定は、アンカを高密度にするか、または長距離高出力の伝送が可能なアンカが要求される。
【０００７】
位置特定の第３の既知の技術は、協調位置特定である。協調位置特定では、エージェント間の通信が可能になり、全てのエージェントが複数アンカの通信範囲内に位置する必要がなくなる。したがって、エージェントは、他のエージェントに対して仮想アンカとして作用できる。いずれのエージェントも利用可能な多くの情報を有するため、協調位置特定は、優れた精度および広い適用範囲を提供できる。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
協調位置特定の従来技術による方法は、集中型位置特定方法および非協調位置特定方法に改善をもたらしているが、従来技術による協調位置特定方法は、依然として多数の欠点を含む。典型的には、従来技術による協調位置特定方法は、ノードからノードへの単一の位置推定の交換のみが可能である。単一推定を用いることは、位置特定の計算において不正確さを生じさせる可能性がある。さらに、協調位置特定の従来技術による方法は、ノード間距離の推定値のような対称データセットを利用するのみである。協調位置特定の従来技術による方法は、また、ネットワーク内の全ノードが同種であることを要件とする。この場合、受信信号強度のような処理信号メトリック（信号の特性測定値）が、相互に通信する同一タイプのノードによって取得される。また、協調位置特定の従来技術による方法では、一般に、信号メトリックの推定に同一の処理つまりアルゴリズムを各ノードが用いる必要がある。このため、各ノードは同一のハードウェア能力およびソフトウェア能力を備えている必要がある。
【課題を解決するための手段】
【０００９】
本発明の例示的な一実施形態においては、協調位置特定技術を利用して、エージェントとアンカの両方が可能性のある位置（位置する可能性のある場所）の確率を送信することによって、ネットワークシステム内のエージェントについての可能性のある位置の分布を取得する。本発明の一実施形態においては、異種ノードおよび異種処理方法を採用して、対称および非対称のデータセットを処理する。これにより、位置特定能力が大幅に改善される。本発明の別の実施形態においては、因子グラフ定理を用いて、完全な協調位置特定方法を開発することにより、ネットワーク内の全ノードの推定位置を算出する。
【００１０】
本発明の一実施形態においては、無線ネットワーク内の無線機器の位置を自己識別するシステムおよびその方法が開示される。このシステムは、無線ネットワーク内の無線機器の少なくとも１つの可能性のある位置の分布を表す、少なくとも１つの変換後信念（変換された信念）を計算するように構成された計算ユニットを備える。この少なくとも１つの変換後信念は、少なくとも１つの他の無線機器から無線機器が受信する無線信号に関連する任意の信号メトリックの関数である。分布は、確率密度関数または確率質量関数である。システムはさらに、少なくとも１つの変換後信念の関数として自己信念を決定するように構成された信念決定ユニットと、自己信念の関数として無線ネットワークにおける自己位置を識別する（特定する）ように構成された識別ユニット（特定ユニット）とを有する。
【００１１】
無線ネットワークは経時変化してもよい。具体的には、複数の他の無線機器のうちの少なくとも１つのサブセットが、複数の他の無線機器のうちの少なくとも１つの他のサブセットに対して移動してもよく、これらサブセットのそれぞれの推定ユニット、変換ユニット、信念決定ユニットおよび識別ユニットはさらに、移動性を考慮に入れるように構成される。
【００１２】
複数の他の無線機器のうちの少なくとも１つのサブセットの推定ユニットは、第１タイプの任意の信号メトリックを推定するように構成されてもよく、複数の他の無線機器のうちの少なくとも１つの他のサブセットの推定ユニットは、第２タイプの任意の信号メトリックを推定するように構成されてもよい。任意の信号メトリックは、少なくとも１つの他の無線機器を基準としたその無線機器の特性である。この特性は、角度、距離、接続性、位置、姿勢、速度および角速度情報からなるグループから選択されてもよい。第１タイプの任意の信号メトリックに対応する特性は、第２タイプの任意の信号メトリックに対応する特性と比較して非対称であってもよい。
【００１３】
変換ユニットは、少なくとも１つの信念を変換するようにさらに構成されてもよく、決定ユニットは、因子グラフ定理に基づいて、自己信念を決定するように構成されてもよい。また、変換ユニットは、任意の信号メトリックを推定することに関する機能を自動的に評価するようにさらに構成されてもよい。
【００１４】
決定ユニットはさらに、先に決定された自己信念を更新するか、または新たな自己信念を決定するように構成されてもよい。識別ユニットはさらに、無線ネットワーク内の少なくとも１つの他の無線機器の位置を識別するように構成されてもよい。
【００１５】
上記内容は、添付図面に示されている、以下の本発明の例示的な実施形態に関するより詳細な説明から明らかとなるであろう。図面では、異なる図であっても、同一の参照符号は同一部分を指す。図面は必ずしも縮尺通りではなく、代わりに、本発明の実施形態を説明することに重点を置いている。
【図面の簡単な説明】
【００１６】
【図１】本発明による例示的な位置特定方法およびその装置を利用できる環境を上から見た図である。
【図２】本発明による例示的な位置特定方法およびそれに対応する装置を利用できる環境の概略図である。
【図３Ａ】無線機器と少なくとも１つの他の無線機器との間の相対位置の属性（ＡＲＰ）の例を示す図である。
【図３Ｂ】無線機器と少なくとも１つの他の無線機器との間の相対位置の属性（ＡＲＰ）の例を示す図である。
【図３Ｃ】無線機器と少なくとも１つの他の無線機器との間の相対位置の属性（ＡＲＰ）の例を示す図である。
【図４】図２のネットワークを表す因子グラフの例の図である。
【図５】図２のノードにおいて使用される例示的な位置特定プロセッサの概略図である。
【図６】本発明の例示的な一実施形態による、協調位置特定方法の例示的な動作を示す流れ図である。
【発明を実施するための形態】
【００１７】
本発明の例示的な実施形態の説明は以下の通りである。
【００１８】
図１は、集中型位置特定方法を採用した、種々のモバイル機器、すなわちエージェント１０３ａ〜１０３ｈを特徴とする屋内環境１００の平面図の一例を示す。エージェントは、例えば、消防士が捜索救助任務の間にそれぞれ携帯する無線機器である。無線機器は移動型であるため、その位置が不明になることがある。これら無線機器の位置を判定するのに、無線機器は、「アンカ」（例えば、無線アクセスポイント）１０５ａ〜１０５ｃおよび中央位置特定計算ユニット１０９のみに依存する。アンカは、固定で既知の場所に配置されている。アンカは近接エージェントとの間で信号を送受信して、距離（例えば、アンカからエージェントへの距離）の推定値に基づいて種々のエージェントに位置を提供することを試みる。アンカはまた、無線のコネクション１０７を介して、中央位置特定計算ユニット１０９と通信するように構成されている。集中型位置特定方法を用いてエージェントが自己の位置を判定するために、種々のアンカはエージェントから受信した情報を中央位置特定計算ユニット１０９に送信する。中央ユニット１０９は、無線ネットワーク内の各エージェントの推定位置を計算する。信頼性の高い位置推定値を生成するために集中型位置特定方法を用いてもよいが、この方法は、単一の位置において全ての計算を実行しなければならないという欠点がある。
【００１９】
図２は、非協調位置特定方法を利用するネットワークの一例を示す。ネットワーク２００は、３つのセルラ基地送受信局（「基地局」）（ＢＴＳ３、ＢＴＳ４およびＢＴＳ５）を有し、これらセルラ基地送受信局はアンカとして機能する。セルラ基地局すなわちアンカは、自己の位置を認識している。ネットワークはまた、携帯電話（例えば、ＭＳ１およびＭＳ２）のような多数の移動局（ＭＳ）を有する。移動局はエージェントとして機能する。携帯電話すなわちエージェントは、自己の位置をほとんどまたは全く認識していない。エージェントはまた、ネットワーク全体にわたって移動することができる。したがって、エージェントの位置は変化する。アンカとエージェントは、それぞれ基地局と携帯電話に限定されるものではなく、任意の形態の無線機器であってもよいことは理解されるべきである。ここで、基地局は典型的にはネットワークに配線接続されているが、それでも基地局は「無線機器」の定義に含まれている。また、アンカおよびエージェントの両方が移動できるものであってもよいことも理解されるべきである。
【００２０】
非協調位置特定の方法においては、エージェントは、ネットワーク内での自己の位置を判定する際に、アンカと通信するのみである。例えば、エージェントＭＳ１が、アンカＢＳ３およびＢＳ５と通信することのみが可能な、ネットワーク内の場所に位置する場合（すなわち、エージェントＭＳ１がアンカＢＳ４との通信範囲内には存在しない）を想定する。エージェントＭＳ１は、アンカＢＳ３と通信すると、アンカＢ３から情報パケット（図示せず）を取得する。図２に示す実施例においては、情報パケットに相当する無線信号が、エージェントＭＳ１の相対位置の属性（ＡＲＰ）の推定である信号メトリックをアンカＢＳ３に提供する。
【００２１】
信号メトリックは、１つまたは数個の因子（例えば、到着時間、到着時間差、受信信号強度、到着角度、ドップラー偏移、および接続性）に基づく。これら信号メトリックは、送信機と受信機との間の相対位置（ＡＲＰ）に関する情報を提供する。例えば、距離のＡＲＰを推定するために、信号メトリックとして、到着時間、到着時間差、往復飛行時間、受信信号強度、およびホップ数が用いられる。角度のＡＲＰを推定するために、信号メトリックとして、到着角度が用いられ、または、アンテナステアリングを表す情報が用いられる。接続性のＡＲＰを推定するために、信号メトリックとして受信信号強度（ＲＳＳ）が用いられる。
【００２２】
図３Ａ〜図３ＣはＡＲＰ情報の例示的な形態を示す。これらの図は、任意の信号メトリックの例であり、接続性（図３Ａ；エージェントＭＳ１の位置している可能性がある場所を円が重なっている領域内に制約する。ここで、２つの円はそれぞれアンカＢＳ３とＢＳ５の回りで既知の半径を有する）、距離（図３Ｂ；エージェントＭＳ１の位置している可能性がある場所を、円周が重なる部分上に制約する。各円は、それぞれ、アンカＢＳ３およびＢＳ５の回りで既知の半径を有する）、または角度（図３Ｃ；エージェントＭＳ１の位置している可能性がある場所を、アンカＢＳ３およびＢＳ５をそれぞれ通る線の１組に制約する）を示す。種々の他のＡＲＰが、例えば、位置、姿勢、速度およびノードに対する角速度情報などの信号メトリックデータに基づいて取得される。
【００２３】
距離のＡＲＰは対称である。例えば、ノードＡからノードＢまでの距離は、ノードＢからノードＡまでの距離に等しい。角度と接続性のＡＲＰは非対称であるかもしれない。この理由は、ノードＡからノードＢへの角度または接続性が、ノードＢからノードＡへの角度または接続性に等しくない可能性があるからである。
【００２４】
図２の実施例においては、対象である距離のＡＲＰを推定するのに受信信号強度の信号メトリックを用いる。ＡＲＰ推定値が与えられると、エージェントＭＳ１は、エージェント自体がアンカＢＳ３から特定の距離または半径に位置していることを判定する。アンカＢＳ３が提供する情報を所与として、エージェントＭＳ１が位置している可能性のある場所は、点線の円２０１によって表わされる。
【００２５】
エージェントＭＳ１はアンカＢＳ５から距離情報を取得する。そして、アンカＢＳ５の回りの点線円２０２が、アンカＢＳ５に対してＭＳ１が位置している可能性のある場所を表す。これより、エージェントＭＳ１の実際の位置は、２つの点線円２０１、２０２の交差部分に限定される。したがって、エージェントＭＳ１が位置している可能性がある場所として２つの位置２０３、２０５がもたらされる。エージェントＭＳ１が３つのアンカの通信範囲内にはないため、ＭＳ１は自己の位置を一意的に決定することができない。
【００２６】
エージェントＭＳ２もアンカＢＳ４とＢＳ５の通信範囲内のみに位置することから、同様に、ＭＳ２も自己の位置を一意的に判定することができない。エージェントＭＳ２が位置している可能性のある場所２０７、２０９は、点線円２０６、２０８の交差点に相当する。
【００２７】
無線機器の位置を判定する別の方法は、協調位置特定を用いる方法である。協調位置特定では、エージェントは、その位置推定値を交換することによって、アンカおよび他のエージェントの両方と通信する。したがって、エージェントは仮想アンカとして機能する。エージェントおよびアンカはノードと見なされる。この場合、各ノードは、ノードのタイプに関係なく、他のノードと通信する能力を有する。エージェント間の通信によって、全エージェントは１つ以上のアンカの範囲内に位置する必要がなくなる。
【００２８】
しかし、協調位置特定の従来技術による方法は、多くの欠点を含んでいる。協調位置特定の従来技術による方法では、一度に、単一の位置推定値のみが送信される。協調位置特定の従来技術による方法はまた、従来技術による方法が対称ＡＲＰ（例えば、距離の測定）を用いることを可能にするのみであるという点で制限されている。さらに、協調位置特定の従来技術による方法は、典型的には、ネットワークの全ノードが同種であることを要件とする。同種の各ノードは、同一タイプのＡＲＰとなる信号を送受信する。同種ノードにはまた、位置推定値を同様の方式で処理できる、同様のハードウェアおよびソフトウェア能力が必要とされる。
【００２９】
本発明の例示的な一実施形態においては、協調位置特定技術を利用して、可能性がある複数の位置の確率の特徴を表す分布をエージェントおよびアンカが送信することによって、ネットワークシステム内のエージェントが位置している可能性がある場所を取得する。本発明の一実施形態においては、信号メトリックを用いて対称および非対称のＡＲＰを取得する。このように、本発明の実施形態による協調位置特定方法は、距離のＡＲＰのみに限定されず、当技術分野で既知の任意のＡＲＰを用いる。任意の信号メトリックおよび当技術分野で既知のＡＲＰが、本発明のいずれの例示的な実施形態において採用されてもよいこともまた理解されるべきである。
【００３０】
本発明の別の実施形態においては、システムのノードは異種であり、このため、非対称で、同一でない値を有し、異なるタイプであるＡＲＰを用いることによって、各ノードは位置を推定することができる。本発明の例示的な一実施形態によれば、ネットワークの異種ノードはまた、ノードからノードに至るまで異なるハードウェアおよびソフトウェアシステムを有する。本発明の別の実施形態においては、ネットワーク内の全ノードの推定位置を判定するために、完全な協調位置特定方法を開発するのに因子グラフ理論を用いる。
【００３１】
図４は、図２に示されるネットワークの因子グラフ表示を示す上面図である。図５は、図２の各エージェントに設けられた位置特定プロセッサの概略を表す。図６は、例示的な協調位置特定方法のとり得る動作を表す流れ図である。図４〜図６は、本発明の例示的な実施形態による協調位置特定に対する数学、ハードウェアおよびソフトウェアのアプローチをそれぞれ示す。
【００３２】
因子グラフは、多変数関数を表して理解するために直感的な方法を提供する。因子グラフは、グローバル関数を、因子の積、またはローカル関数として表す。いずれの因子がいずれの変数に依存しているかを示すことによって、因子グラフは、グローバル関数の変数が共有のローカル関数を通していかに相互依存しているかを示す。
【００３３】
本発明の例示的な一実施形態において、因子グラフは、信号メトリックの集合Ｚを所与として、ネットワーク内の全ノードの可能性のある位置を表す、結合（joint）事後確率分布ｐ（ｘ１，…，ｘＮ｜Ｚ）から得られる。ただし、Ｎは、ネットワーク内のノードの総数に等しい。結合事後確率分布は、以下のように表すことができる。
【００３４】
【数１】
2010507985.tif 000003
【００３５】
ここで、ｚｊ→iは、ノードｊによって送信された信号から、ノードiによって得られる信号メトリックである。関数ｐ（ｚｊ→i｜ｘｉ，ｘｊ）は、ノードiおよびｊの位置を条件とした信号メトリックの分布である。
【００３６】
結合事後確率分布ｐ（ｘ１，…，ｘＮ｜Ｚ）についての式を得ると、和積アルゴリズム（ＳＰＡ）（信念伝搬（belief propagation）としても知られている）を、作成された因子グラフに用いて、全ノードiについての周辺（marginal）事後分布ｐ（ｘｉ｜Ｚ）の近似を決定する。各ノードの自己位置ｘｉを推定するのに、ネットワーク内の各ノードは周辺事後分布の近似を用いる。周辺事後分布ｐ（ｘｉ｜Ｚ）の近似はまた、因子グラフ理論を用いて物理的ネットワークにマッピングされてもよい。これについて詳細に後述する。
【００３７】
図４の実施例において、図２のネットワークの５つのノードＢＳ３、ＢＳ５、ＢＳ４、ＭＳ１およびＭＳ２は、それぞれ、ボックス４０３、４１５、４１１、４０７および４１９で強調表示されたサブグラフに関連付けられている。ノードＭＳ１、ＭＳ２、ＢＳ３、ＢＳ４およびＢＳ５の可能性のある位置（位置している可能性のある場所）は、それぞれ、ｘ１〜ｘ５と表記された、因子グラフにおける境界線として表されている。エージェントノードＭＳ１およびＭＳ２の可能性のある位置（それぞれｘ１およびｘ２）は、近接ノードにより送信される情報によって提供される。可能性のある位置を取得する操作は、因子グラフ４００におけるバーテックス（vertex）によって表される。これについて、詳細に後述する。
【００３８】
本発明の例示的な一実施形態において、協調位置特定方法の第１の操作は、ネットワーク内の全ノードの信念を初期化することである（ステップ６０１）。初期化では、アンカおよびエージェントの信念が、これらの周辺事前分布ｐ（ｘｉ）と等しく設定される。周辺事前分布ｐ（ｘｉ）は、ノードiの可能性のある位置について、変数ｘｉの関数である。周辺事前分布ｐ（ｘｉ）は、位置特定処理の開始前に認識しているノードiを反映する。ネットワーク内の各ノードＢＳ３、ＢＳ５、ＢＳ４、ＭＳ１およびＭＳ２についての周辺事前分布は、それぞれ、バーテックス４０１、４１３、４０９、４０５および４１７と表記されている。
【００３９】
アンカＢＳ３、ＢＳ５およびＢＳ４は自己の位置を認識しているため、これらアンカは、信念をディラックのデルタ分布の形式の事前分布に初期化する。ディラックのデルタ分布は、ゼロ位置のみに非ゼロ確率を定義する関数であり、このゼロ位置は各アンカが認識している位置である。ネットワーク内のアンカには、自己位置を常に完全に認識しているわけではないアンカも存在する。したがって、自己の位置を部分的に認識しているアンカの事前分布は、任意の形状を有する分布である可能性があることは理解されるべきである。
【００４０】
エージェントＭＳ１およびＭＳ２は、信念を均一な分布形状の事前分布に初期化する。エージェントは、最初は、自己位置を認識していないため、均一分布は、各エージェントの全ての可能性のある位置に対して等しい確率値を有する。エージェントは、自己の位置を部分的に認識していることがある。この場合、事前分布は任意の形状を有する。エージェントは、自己の位置を十分に認識していることがある。この場合、事前分布はディラックのデルタ分布により定義される形状になる。
【００４１】
エージェントとアンカは上述の分布のいずれか、および当技術分野で既知の任意の他の分布を有してもよいことは理解されるべきである。エージェントおよびアンカは、他のエージェントおよびアンカと比較して自己の位置をより認識している、いくつかのエージェントおよびアンカと同一の分布を有する必要がないことも理解されるべきである。
【００４２】
一実施形態においては、ネットワーク内の全ノードの信念を初期化すると、反復値が設定または確定される（ステップ６０３）。反復値は、ネットワーク内の各ノードによって協調位置特定方法が実行される回数を定義する。最大反復値「ｍａｘ」は、ネットワークの実行時間に対して動的に設定される。したがって、ネットワークは、そのネットワークに関係する種々の機器を常時追跡して位置を突き止める。必ずしも全てのノードが全ての反復に関与しているわけではないことは理解されるべきである。
【００４３】
反復値が定義されると、システムは反復の現在値「Ｌ」を継続的すなわち持続的に監視して、最大反復値「ｍａｘ」に到達しているか否かを判定する（ステップ６０５）。最大反復値「ｍａｘ」に到達していると判定されると、位置特定システムは、終了に誘導される（ステップ６０７）。そうでない場合、ネットワーク内のノードすなわちノードシステムは、協調位置特定の反復処理に進む（ステップ６０９）。最初に、システムは、ネットワーク内の全ノードの自己信念を更新する（ステップ６１１）。自己信念の更新は、ノードの移動性に基づき、慣性計測装置またはジャイロスコープなどの当技術分野で既知の任意の技術を利用する。エージェントとアンカの両方とが移動する能力を有する場合もある。少なくとも１つの実施形態においては、ネットワーク内の全てのノードが更新されなくてもよいため、このような実施形態では、ノードのサブセットのみが一度に更新されることは理解されるべきである。したがって、バーテックス４０１、４１３、４０９、４０５および４１７とそれぞれ表記された各ノードＢＳ３、ＢＳ５、ＢＳ４、ＭＳ１およびＭＳ２の周辺事前分布ｐ（ｘｉ）が、そのノード分のみ更新される。
【００４４】
さらに、この反復処理の間に、新しいノードがネットワークに入るのが検出されることがあり、または現在のノードがネットワークを出るのが検出されることもある。そのため、因子グラフの構成が変化する（例えば、ネットワークに入るノードに対応する新しいサブグラフが因子グラフに追加されたり、またはネットワークを出るノードのサブグラフが削除されたりする）。このようにして、協調位置特定処理の継続期間の間に、ネットワークトポロジが変化すると因子グラフのトポロジも変化する。
【００４５】
次に、ネットワーク内の全ノードが、現在の自己信念をブロードキャストする（ステップ６１３）。このブロードキャストは、ＳＰＡを用いて達成される。ＳＰＡを、因子グラフ上を通過するメッセージとして適用して、ネットワーク内の各ノードに対する周辺事後分布ｐ（ｘｉ｜Ｚ）の近似を得る。周辺事後分布ｐ（ｘｉ｜Ｚ）は、自己信念ｂ（ｘｉ）によって近似される。
【００４６】
例えば、図４に示した因子グラフでは、エージェントＭＳ１がアンカＢＳ３の通信範囲内にあるため、アンカＢＳ３はその自己信念ｂ（ｘ３）４２１をエージェントＭＳ１に送信する。同様に、エージェントＭＳ１はエージェントＭＳ２の通信範囲内にあるため、エージェントＭＳ１は仮想アンカとして機能し、その自己信念ｂ（ｘ１）４２３をエージェントＭＳ２に送信する。同様に、エージェントＭＳ２は仮想アンカとして機能し、その自己信念ｂ（ｘ２）４２５をエージェントＭＳ１に送信する。アンカＢＳ４はエージェントＭＳ２の通信範囲内にあるため、その自己信念ｂ（ｘ４）４２７をエージェントＭＳ２に送信する。アンカＢＳ５は、エージェントＭＳ１およびエージェントＭＳ２の両方の通信範囲内にあるため、その自己信念ｂ（ｘ５）４２８、ｂ（ｘ５）４２９をそれぞれエージェントＭＳ１およびエージェントＭＳ２に送信する。
【００４７】
アンカＢＳ５のサブグラフ４１５では、複数のノードに自己信念を送信するときに、等値バーテックス（equality vertex）４３１が用いられる。同様に、エージェントＭＳ１およびＭＳ２のそれぞれのサブグラフ４０７、４１９もまた、これらエージェントが複数のノードと通信していることから、等値バーテックス４３１を有する。
【００４８】
ノードは、ブロードキャストの期間中、複数のメッセージパケットを送受信してもよいことは理解されるべきである。例えば、ノードＡが往復時間の信号メトリックを推定する場合、ノードＡはノードＢにパケットを送信し、ノードＢはノードＡにパケットを返信する。
【００４９】
ネットワーク内の各ノードが自己信念をブロードキャストする際、各ノードは位置特定プロセッサ５００を個々に利用して、ブロードキャストされた信念に基づいて新たな自己信念を算出する。最初に、ノードが、ネットワーク内の他のノードからアンテナ５０３を介してブロードキャストされた信念５０１を受信する（ステップ６１７）。各ノードは、信念を受信するノードの通信範囲内の任意の数のノードから任意の数のブロードキャストされた信念５０１を受信する。
【００５０】
近接ノードから信念を受信した後、ノードは、変換後信念を生成する処理を開始する（ステップ６１９）。変換後信念を生成する処理においては、ネットワーク内の少なくとも１つの他のノードに関するノードの任意の信号メトリックを推定するために、ノードの位置特定プロセッサは、送信された信念５０１を受信するように構成された推定ユニット５０７を設ける。任意の信号メトリックは、任意のタイプまたは値の信号メトリックである（例えば、使用されてもよい信号メトリックのタイプは、対称または同種の信号メトリックに限定されない）。推定された任意の信号メトリック５０９は、少なくとも１つのノードからの受信した信念信号の関数である。
【００５１】
任意の信号メトリックが、事前反復からの同一送信ノードから推定されている場合、または、位置特定処理の開始前である場合、新しい任意信号が推定されてもされなくてもよいことは理解されるべきである。推定信号メトリックから得られたＡＲＰ推定値が、ノードごとに異なるタイプおよび／または値を使用できるように、ネットワーク内のノードが異種であってもよいこともまた理解されるべきである。
【００５２】
また、信号メトリックを推定するのに異なる技術または処理を各ノードが用いるように、ネットワーク内のノードは異種であってもよい。信号メトリックおよびＡＲＰは、解析的、数値的または統計的方法の任意の組み合わせを用いて推定されてもよいことも理解されるべきである。また、各ノードが、ネットワーク内の他のノードとは独立して信号メトリックを推定してもよいことも理解されるべきである。例えば、ノードＡは、ネットワーク内の他のノードの推定信号メトリックを認識することなく、受信したメッセージから信号メトリックを推定してもよい。
【００５３】
任意の信号メトリック５０９が提供されると、推定された任意の信号メトリック５０９に基づいて変換後信念５１３を提供するために、この信号メトリックが変換ユニット５１１に送信される。ネットワーク内の各ノードは、複数の推定ユニットおよび変換ユニット、すなわち計算ユニット５１５を有してもよい。この計算ユニット５１５は、受信された入力してくる信念５０１それぞれに対する変換後信念５１３を同時に決定するように構成されている。代わりに、推定ユニットおよび変換ユニット、すなわち計算ユニット５１５は、受信された入力してくる信念５０１それぞれに対する変換後信念５１３を順次決定するように構成されてもよい。任意の数の信号メトリックを推定するために、別のノードから送信された信念が、現在のノードによって使用されてもよいことは理解されるべきである。さらに、信号メトリックは任意の数のＡＰＲを説明するのに用いられてもよい。
【００５４】
変換後信念の生成を、図４を用いて数学的に説明する。例えば、エージェントＭＳ１では、エージェントＭＳ１に送信されるアンカＢＳ３からの自己信念４２１から得られる変換後信念の生成は、バーテックス４３０によって表される。ＳＰＡは、生成された変換後信念ｃ３→１（ｘ１）４３２を等値バーテックス４３１に送信する。同様に、アンカＢＳ５からの送信された自己信念４２８を用いて、推定された任意の信号メトリックを取得することによって、バーテックス４３３で表されている変換後信念を生成する。次に、変換後信念ｃ５→１（ｘ１）４３４も等値バーテックス４３１に送信される。最後に、送信された自己信念４２５に基づき、第３の変換後信念の生成が、バーテックス４３５で示される。生成された変換後信念ｃ２→１（ｘ１）４３６はまた、ＳＰＡを介して等値バーテックス４３１に送信される。
【００５５】
エージェントＭＳ２についても同様に、変換後信念の生成は、バーテックス４４１、４３７、４３９によって表され、それぞれ、変換後信念ｃ１→２（ｘ２）４４２、ｃ４→２（ｘ２）４３８、ｃ５→２（ｘ２）４４８が得られる。変換後信念ｃ１→２（ｘ２）４４２、ｃ４→２（ｘ２）４３８、ｃ５→２（ｘ２）４４８は、ＳＰＡを介してサブグラフＭＳ２の等値バーテックス４３１に送信される。
【００５６】
変換後信念の生成は、以下の式によって表すことができる。
【００５７】
【数２】
2010507985.tif 000004
【００５８】
ここで、ｃｊ→ｉ（ｘｉ）は、現在のノードｉで生成された変換後信念であり、ｐ（ｚｊ→ｉ｜ｘｉ，ｘｊ）は、ノードｊから現在のノードｉに送信された信号から抽出された信号メトリックｚｊ→ｉの分布であり、ｂ（Ｌ−１）（ｘｊ）はノードｊによって現在のノードｉにブロードキャストされた自己信念である。上式の積分は、全ての可能性のあるｘｊに対して実行される多次元積分である。変換後信念の生成は、解析、数値または統計積分法の任意の組み合わせを用いて実行されてもよいことは理解されるべきである。変換後信念が、位置ｘｉ、ｘｊの関数として推定された信号メトリックｚｊ→ｉに関連する何らかの不確実性、および環境に関する何らかの認識（例えば、障害物の存在、低い信号対雑音比、弱い信号強度、推定処理における固有の不確定性など）を考慮に入れてもよいことは理解されるべきである。変換後信念の生成は、解析的、数値的または統計的方法の任意の組み合わせを用いて実行されてもよいことは理解されるべきである。
【００５９】
変換後信念の全てが各ノードのサブグラフの等値バーテックス４３１に送信されると、等値バーテックス４３１は各変換後信念を評価する。等値バーテックス４３１は、例えば、ある生成された変換後信念の値が、他の生成された変換後信念と大きく異なる場合、不一致と自己評価する（ステップ６２１）。例えば、変換後信念が、故障しているノードから送信されたものである場合、この自己信念は、続く位置特定の計算とずれている可能性がある。故障しているノードは、低い信号対雑音比で信号を送信するノード、虚偽の情報を送信するノード、または他のノードから送信された情報から取得された位置推定値から大きく異なる位置推定値を導く情報を送信するノードである。
【００６０】
変換後信念が不一致に関して評価されると、各ノードの新たな自己信念が決定される（ステップ６２３）。各ノードの位置特定プロセッサ５００は、生成された変換後信念５１３を全て信念決定ユニット５１７に転送する。信念決定ユニット５１７は、現在のノードの周辺事前分布ｐ（ｘｉ）、および生成された変換後信念を考慮して、新たに決定された自己信念５１９を生成する。生成された変換後信念は、通信範囲内のネットワークにおいてノードからの送信された自己信念の関数である。
【００６１】
新たに決定された自己信念５１９は、先に決定された自己信念を考慮して実行される。すなわち、信念決定ユニット５１７は、先の反復から決定された自己信念に関する記憶、すなわち認識を用いて、新たな自己信念５１９を決定する。記憶を用いた新たな自己信念５１９の決定は、以下のように表すことができる。
【００６２】
【数３】
2010507985.tif 000005
【００６３】
ここで、ｂ（Ｌ）（ｘｉ）は、現在の反復Ｌ中に決定されたノードｊの自己信念であり、ｂ（Ｌ−１）（ｘｉ）は、先の反復Ｌ−１において決定されたノードｊの自己信念であり、Γｉは、ノードｉの近接ノードのセットであり、このノードセットからノードｉは一致した変換後信念を選択し、ｃｊ→ｉ（ｘｉ）は、ノードｊからノードｉに送信された信号メトリックによって生成された変換後信念である。新たに決定される自己信念５１９の生成も、先の反復から決定された自己信念の記憶（認識）がなくとも実行できることは理解されるべきである。記憶なしに生成された新たな自己信念５１９は、以下のように表される。
【００６４】
【数４】
2010507985.tif 000006
【００６５】
ここで、ｐ（ｘｉ）は、現在のノードｉの周辺事前分布である。したがって、周辺事前分布は、先に生成された自己信念を考慮しないシステムで利用される。信念決定ユニット５１７は、周辺事前分布と現在のノードｉの先に生成された自己信念の両方を利用してもよいことは理解されるべきである。また、いくつかのノードは記憶を用いて新たな自己信念を生成するが、一方で、ネットワーク内の他のノードは、新たな自己信念を生成するのに記憶を用いないという点で、ネットワーク内のノードは異種であってもよいことは理解されるべきである。また、記憶を使用しても使用しなくても、新たに決定された自己信念５１９の生成は、解析的、数値的または統計的方法の任意の組み合わせを用いて実行されてもよいことは理解されるべきである。ネットワーク内の全てのノードが自己信念を生成する必要があるとは限らないことは理解されるべきである。例えば、ノードが定義された位置を有し、先の反復から移動していないことが判定される場合、そのノードはその自己信念を更新する必要がない。
【００６６】
新たな自己信念を決定すると、識別ユニット５２１を用いて自己位置５２３を推定する（ステップ６２５）。推定された自己位置５２３は、決定後自己信念の平均値、中央値または最頻値を取ることによって判定される。自己信念は確率分布の形である。ネットワーク内のノードは、自己位置５２３を推定するのに様々な方法を利用する。
【００６７】
ネットワーク内のノードの位置特定プロセッサ５００はまた、近接識別ユニット５２７を有する。近接の識別ユニット５２７を用いて、近接ノードによって送信された信念の平均値、中央値または最頻値を取ることによって、通信範囲内のノードの位置を推定する。このようにして、ネットワーク内のノードのトポロジマップ５２９を作成して、各ノードにこのトポロジを提供する。これによって、ネットワーク内の全てのノードが、完全なネットワークトポロジにアクセスすることができる。このトポロジマップは、別のデータパケット内で全てのノードによってブロードキャストされてもよい（５３１）。送信されたトポロジ５３１は、送信された決定後自己信念５２５を含むデータパケットの一部として含まれてもよいことは理解されるべきである。ネットワーク内のノードは、様々な方法を使用してトポロジマップ５２９を作成してもよいことも理解されるべきである。
【００６８】
各ノードによって生成される推定信号メトリックは、障害物に関する情報を含む可能性のあるＡＲＰを提供する場合もあることも理解されるべきである。障害物は、ネットワーク内のノード間またはノード周辺に存在し得る。障害物の例として、これらに限定されるわけではないが、壁または建物が挙げられる。この情報はまた、ネットワークのトポロジを作成する際、および自己信念を生成する際に用いられる。
【００６９】
上述の操作６１９〜６２５は、現在の反復中にネットワーク内の全ノードに対して実行される（ステップ６２７）。操作６１９〜６２５がネットワーク内の全ノードについて実行されると、新たな反復が実行される（ステップ６２９）。新たな反復中、先に説明したように移動性を考慮に入れるために、決定後自己信念５１７を更新する（ステップ６１１）。更新されると、更新された決定後自己信念がブロードキャストされ（５２５）、上述の操作６１９〜６２５が、更新された決定後自己信念を用いて実行される。ネットワーク内の全てのノードが全ての反復に関与する必要がないことは理解されるべきである。さらに、ノードは、その反復に関与する全ての計算操作に関与しなくてもよい。
【００７０】
協調位置特定処理のような本明細書で開示した特定の処理は、ハードウェア、ファームウェアまたはソフトウェアで実現されてもよいことは理解されるべきである。ソフトウェアで実現された場合、このソフトウェアは、ランダムアクセスメモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、コンパクトディスク読み出し専用メモリ（ＣＤ−ＲＯＭ）など任意の形態のコンピュータ読み取り可能な媒体に記憶されてもよい。操作中、汎用プロセッサまたは特定用途プロセッサが、当技術分野で既知の方式で、ソフトウェアをロードして実行する。
【００７１】
本発明を発明の例示的な実施形態を参照して具体的に示し、説明してきたが、当業者には、添付の特許請求の範囲に包含される本発明の範囲から逸脱することなく、形態および細部に様々な変更がなされてもよいことは理解されるであろう。
【符号の説明】
【００７２】
１０３  無線機器
１０５  無線機器
２００  無線ネットワーク
【図１】
2010507985.tif 000007
【図２】
2010507985.tif 000008
【図３Ａ】
2010507985.tif 000009
【図３Ｂ】
2010507985.tif 000010
【図３Ｃ】
2010507985.tif 000011
【図４】
2010507985.tif 000012
【図５】
2010507985.tif 000013
【図６】
2010507985.tif 000014
【国際調査報告】
2010507985.tif 000015
2010507985.tif 000016