無線通信ネットワークのノード群によって転送される信号からデバイスが位置する領域を特定するための方法及び装置
【課題】無線通信ネットワークのノード群によって転送される信号からデバイスが位置する領域を特定するための方法を提供する。
【解決手段】方法は、デバイスのために繰返し実行される以下のステップ、ノード群の各ノードから、当該ノードが位置する領域を表す情報を受信するステップと、デバイスとノード群の各ノードとを隔てる距離を表す情報を取得するステップと、受信された情報及び取得された情報から、デバイスが位置する領域を計算するステップと、デバイスが位置する上記計算された領域を、ノード群の各ノードに転送するステップとを含む。
【解決手段】方法は、デバイスのために繰返し実行される以下のステップ、ノード群の各ノードから、当該ノードが位置する領域を表す情報を受信するステップと、デバイスとノード群の各ノードとを隔てる距離を表す情報を取得するステップと、受信された情報及び取得された情報から、デバイスが位置する領域を計算するステップと、デバイスが位置する上記計算された領域を、ノード群の各ノードに転送するステップとを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、無線通信ネットワーク内のデバイスのロケーションを特定するための方法及び装置に関する。
【背景技術】
【０００２】
今日、新たに設置される無線セルラー通信デバイスの基地局のように、グローバルポジショニングシステム（ＧＰＳ：Global Position System）の機能又はデバイスを提供する専用デバイス又は移動電話のようなデバイスが益々多くなっている。
【０００３】
そのような端末は、衛星からブロードキャストされる信号を受信することができない建物のようなエリア内に位置する場合がある。
【０００４】
衛星によってブロードキャストされる信号を受信できる場合であっても、デバイスのロケーション、たとえば、デバイスが位置している建物の階を正確に特定することはできない。
【０００５】
陸上通信装置のような複数の発信源によって送信されてデバイスによって取得可能である信号の到着時刻の観測結果に基づいて、デバイスとそれらの発信源とを隔てる距離を推定することは、デバイスの位置を特定できるようにする既知の技法の一例である。
【０００６】
無線通信ネットワーク、たとえば、無線セルラー通信ネットワーク、又はアドホックネットワーク、又はセンサーをリンクするネットワークにおける、送信又は受信能力を有するノードの相対的又は絶対的なロケーションを、それらのノードを隔てる距離から特定することは多くの場合に正確ではない。Ｘmをｄ次元内のノードｍの位置ベクトルとし、ｄm,nをノードｍとｎとの間の観測される距離とすると、十分な数の完全な観測結果がある場合には、各ノードの位置を厳密に計算することができる。これは、全ての観測値ｄm,nに対する連立非線形方程式ｄm,n＝｜Ｘm−Ｘn｜を解くことによって行うことができる。グラフ剛性（graph rigidity）の原則を考慮に入れることによって、一意の解を得るための条件を取り扱うことができる。既知の絶対的なロケーションを有する幾つかのノードが存在する場合には、計算される位置は絶対的な位置であるが、そうでない場合には、幾つかのノードを基準として選択し、それらの基準に対して残りのノードのロケーションが相対的に特定される。
【０００７】
実際には、それらの測定値は誤差ｅm,nによって劣化しており、ｄm,n＝｜Ｘm−Ｘn｜＋ｅm,nである。誤差は、たとえば、受信機における同期誤差、信号を転送する複数のノードの非同期性、及び信号サンプリングに起因する時間測定値の精度の欠損を含む場合がある。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明は、簡単な方法で、かつノードの場所がアプリオリ（a priori）に正確にわかっていない場合であっても、ノードが位置する領域を特定できるようにするための方法及びデバイスを提供することを目的とする。
【課題を解決するための手段】
【０００９】
この目的のために、本発明は、無線通信ネットワークのノード群によって転送される信号からデバイスが位置する領域を特定するための方法に関する。
この方法は、デバイスのために繰返し実行される以下のステップ：
− ノード群の各ノードから、当該ノードが位置する領域を表す情報を受信するステップと、
− デバイスとノード群の各ノードとを隔てる距離を表す情報を取得するステップと、
− 受信された情報及び取得された情報から、デバイスが位置する領域を計算するステップと、
− デバイスが位置する上記計算された領域を、ノード群の各ノードに転送するステップと
を含むことを特徴とする。
【００１０】
また、本発明は、無線通信ネットワークのノード群によって転送される信号からデバイスが位置する領域を特定するための装置にも関する。
この装置は、
− ノード群の各ノードから、当該ノードが位置する領域を表す情報を受信する手段と、
− デバイスとノード群の各ノードとを隔てる距離を表す情報を取得する手段と、
− 受信された情報及び取得された情報から、デバイスが位置する領域を計算する手段と、
− デバイスが位置する上記計算された領域を、ノード群の各ノードに転送する手段と、
− 上記受信する手段、上記入手する手段、上記計算する手段、及び上記転送する手段を繰返し制御する手段と
を備えることを特徴とする。
【００１１】
それゆえ、何回かの繰り返しの後には、デバイスは自身が存在する領域のさらに良好な推定値を有するようになる。当該特定された領域をデバイスが転送するので、各ノードは自身が位置する領域を、デバイスが位置する領域を用いて精緻化することができる。
【００１２】
特定の特徴によれば、ノード群の各ノードから受信される各領域は、少なくとも１つの多面体によって近似される。
【００１３】
それゆえ、多面体は簡単な幾何学図形であるため、それらの多面体は容易に処理することができ、出力精度に大きな影響を及ぼすことなく、アルゴリズムの複雑度が低減される。
【００１４】
特定の特徴によれば、少なくとも１つの多面体は、四面体に分解される。
【００１５】
それゆえ、領域の計算の複雑度は非常に低い。
【００１６】
特定の特徴によれば、１つの多面体を分解した後に得られる各四面体について、当該四面体の少なくとも１つの点から少なくとも第１の距離だけ離れている、空間内の点を含む第１の中間領域が求められる。
【００１７】
それゆえ、領域の計算の複雑度は非常に低い。
【００１８】
特定の特徴によれば、１つの多面体を分解した後に得られる各四面体について、当該四面体の少なくとも１つの点から多くとも第２の距離だけ離れている、空間内の点を含む第２の中間領域が求められる。
【００１９】
それゆえ、領域の計算の複雑度は非常に低い。
【００２０】
さらに、デバイスが存在する領域を画定するために、ノードのロケーションの不確定性を考慮に入れることができる。
【００２１】
特定の特徴によれば、１つの多面体を分解した後に得られる各四面体について、当該四面体に対して求められた第１の中間領域及び第２の中間領域の交わりである第３の中間領域が求められる。
【００２２】
それゆえ、領域の計算の複雑度は非常に低い。
【００２３】
さらに、デバイスが存在する領域を画定するために、ノードのロケーションの不確定性を考慮に入れることができる。
【００２４】
特定の特徴によれば、各第３の中間領域は、少なくとも１つの多面体によって近似される。
【００２５】
それゆえ、多面体は簡単な幾何学図形であるため、それらの多面体は容易に処理することができ、出力精度に大きな影響を及ぼすことなく、アルゴリズムの複雑度が低減される。
【００２６】
特定の特徴によれば、ノード群のうちの１つのノードから受信された領域を近似する各多面体について、第４の中間領域が求められ、第４の中間領域は、ノード群のうちの１つのノードから受信された領域を近似する多面体を構成する四面体に対して求められた第３の中間領域の和集合である。
【００２７】
それゆえ、領域の計算の複雑度は非常に低い。
【００２８】
特定の特徴によれば、デバイスが位置する計算された領域は、第４の中間領域の交わりである。
【００２９】
それゆえ、領域の計算の複雑度は非常に低い。
【００３０】
さらに、デバイスは幾つかのノードの領域を考慮に入れることができ、それによって、デバイス自体の領域のサイズが小さくなる。
【００３１】
特定の特徴によれば、デバイスが位置する上記計算された領域は、少なくとも１つの多面体によって近似される。
【００３２】
それゆえ、領域の計算の複雑度は非常に低い。
【００３３】
特定の特徴によれば、この方法は、上記計算された領域が以前に計算された少なくとも１つの領域と異なる限り実行される。
【００３４】
そのため、各ノードの領域は繰返しを通じて狭められる。
【００３５】
特定の特徴によれば、本発明は、領域が特定されるデバイスによって実行される。
【００３６】
特定の特徴によれば、デバイスは無線通信ネットワークのノードであり、この方法は各ノードによって実行される。
【００３７】
そのため、ノード領域は相互に計算され、繰返しを通じて狭められる。
【００３８】
さらに別の態様によれば、本発明は、プログラム可能デバイス内に直接ロード可能であるコンピュータープログラムに関する。このコンピュータープログラムは、プログラム可能デバイス上で実行される際に本発明による方法のステップを実施するための命令又はコードの一部を含む。
【００３９】
コンピュータープログラムに関連する特徴及び利点は、本発明による方法及びデバイスに関連して先に記述されたのと同じであるので、ここでは繰り返さない。
【００４０】
本発明の特徴は、一例の実施形態に関する以下の説明を読むことからさらに明らかになり、当該説明は添付の図面を参照しながら提示される。
【図面の簡単な説明】
【００４１】
【図１】本発明が実施される無線セルラー通信ネットワークを表す図である。
【図２】本発明が実施される基地局のようなデバイスのアーキテクチャを表す図である。
【図３】本発明による、デバイスのロケーションを特定するためのアルゴリズムの一例を開示する図である。
【図４】本発明による、領域を特定するためのアルゴリズムの一例を開示する図である。
【図５】デバイスが位置する領域を特定するために用いられる第１の中間領域の一例の図である。
【図６】デバイスが位置する領域を特定するために用いられる第２の中間領域の一例の図である。
【図７】デバイスが位置する領域を特定するために用いられる第１の中間領域及び第２の中間領域を合成することによって求められる第３の中間領域の一例の図である。
【図８】第３の中間領域の多面体への分解の一例の図である。
【図９】本発明に従って特定される、デバイスが位置する領域の一例の図である。
【発明を実施するための形態】
【００４２】
図１は、本発明が実施される無線セルラー通信ネットワークを表す。
【００４３】
本発明は、本発明を実行するノードが基地局ＢＳである一例において開示されることになる。
【００４４】
本発明は、アドホックネットワーク又はセンサーネットワークにおいて実施することもできる。
【００４５】
基地局ＢＳは、ピコ基地局又はフェムト基地局及び／又はホーム基地局とすることもできる。
【００４６】
ピコ基地局又はフェムト基地局は、数百又は数十平方メートルをカバーするセルを管理する。
【００４７】
ホーム基地局は、ユーザーの自宅に位置する。
【００４８】
図１においては、４つの基地局ＢＳ１、ＢＳ２、ＢＳ３、及びＢＳ４からなる基地局群が示されている。基地局ＢＳ１、ＢＳ２、ＢＳ３、及びＢＳ４からなる群の各基地局ＢＳは信号を送信することができ、その信号は基地局群内の他の基地局ＢＳによって受信され、基地局群内の基地局間を隔てる距離を求めるために用いられる。信号は、その信号を転送する基地局ＢＳの地理的な位置に関する情報を含むことができる信号であってもよいし、または、基地局ＢＳの位置をアプリオリに知っている移動端末ＭＴによって受信される複数の信号の中から基地局ＢＳｉを一意に認識できるようにする信号である。
【００４９】
図１の例においては、デバイスがノードである。ここで、デバイスは移動端末であってもよいことに留意されたい。
【００５０】
簡単にするために、図１には４つの基地局ＢＳしか示されていないが、基地局群は、さらに多くの数の基地局ＢＳを含んでもよいし、さらに少ない数の基地局ＢＳを含んでもよい。
【００５１】
基地局ＢＳ群は、基地局ＢＳｉとそれに隣接する基地局を含む。
【００５２】
図１において、基地局ＢＳ群は、基地局ＢＳ１とそれに隣接する基地局ＢＳ２〜ＢＳ４を含む。
【００５３】
基地局ＢＳ１と基地局ＢＳ２との間の距離はｄ1,2で表される。基地局ＢＳ１と基地局ＢＳ３との間の距離はｄ1,3で表される。基地局ＢＳ１と基地局ＢＳ４との間の距離はｄ1,4で表される。基地局ＢＳ２と基地局ＢＳ３との間の距離はｄ2,3で表される。基地局ＢＳ３と基地局ＢＳ４との間の距離はｄ4,3で表される。基地局ＢＳ２と基地局ＢＳ４との間の距離はｄ4,2で表される。
【００５４】
本発明によれば、各基地局ＢＳｉ（ｉ＝１〜４）は、既知の距離又は区間に測定誤差があるものと仮定して、基地局ＢＳｉが位置する空間の領域を計算する。基地局ＢＳｉが位置する領域は、基地局ＢＳ群内の他の基地局ＢＳから受信される信号と、基地局ＢＳ群内の互いの基地局ＢＳによって計算されて転送される領域とから計算される。
【００５５】
本発明によれば、基地局ＢＳ群内の各基地局ＢＳｉは、基地局群内の他の基地局から受信される領域に従って基地局ＢＳｉが位置する領域を精緻化し、当該基地局ＢＳｉが位置する精緻化された領域を、基地局群内の他の基地局に再び転送する。
【００５６】
このプロセスは、領域精緻化の改善が見られなくなるまで繰り返し実行されるか、若しくは所定の繰返し回数だけ繰返し実行されるか、または、この繰返しプロセスは長期に渡って周期的に実行される。
【００５７】
領域精緻化の各ステップにおいて、ｄ次元における基地局ＢＳｉの領域Ｒiは、基地局群内の他の基地局ＢＳｋによって与えられる領域Ｒkの推定値から、以下のように計算される。
【００５８】
【数１】
【００５９】
ただし、Ｉi,kは誤差ｅi,kの区間であり、Ω（ｉ）は基地局ＢＳｉが属する基地局ＢＳ群内の他の基地局の集合であり、
【００６０】
【数２】
【００６１】
は次元ｄの数の集合であり、ｄは当該領域が特定される空間の次元である。
【００６２】
そして、これらの領域は繰返し計算される。開始時においては、大きな領域が特定される基地局もあれば、その位置が分かっている場合には完全にロケーションを特定することができる基地局もある。収束するまでの間、繰り返しの度に領域は収縮し、収束するとそれ以上の改善がもたらされなくなって領域の収縮が止まる。
【００６３】
本発明の特定の実現形態によれば、各領域は１つ又は複数の多面体によって近似することができる。その場合、１つ又は複数の多面体の角のみを基地局間で交換することができる。多面体の１つの特性は四面体に分解されることである。四面体は３次元における三角形である。
【００６４】
１つの変形では、領域輪郭の定義を円弧、線に分割することができ、領域輪郭のみが交換される。
【００６５】
基地局ＢＳｉの領域Ｒiは、以下のように表すことができる。
【００６６】
【数３】
【００６７】
ただし、Ａi,kは基地局ＢＳｋの領域Ｒkのみによって特定される領域であり、∩は交わりを表す。
【００６８】
各領域Ｒkを四面体Ｔk,jの和集合に分解することによって、Ａj,kは以下のように書き換えることができる。
【００６９】
【数４】
【００７０】
ただし、Ｂi,k,jは基地局ＢＳｋのみの四面体Ｔk,jのうちの１つから特定される領域であり、∪は和集合を表す。
【００７１】
基地局ＢＳｉとＢＳｋとの間で観測される距離はｄi,kであり、距離ｄi,kに関する誤差区間は［ａ，ｂ］である。エリアＢi,k,jは以下のように定義することができる。
【００７２】
【数５】
【００７３】
ｄmin（ｘ，Ｔk,j）及びｄmax（ｘ，Ｔk,j）を、点ｘとＴk,jの点との間の最小距離及び最大距離とする。
【００７４】
このとき、Ｂi,k,jを以下のように定義することができる。
【００７５】
【数６】
【００７６】
本発明の特定の実現形態によれば、Ｂi,k,jは多面体Ｔk,jの境界要素から計算される。
【００７７】
Ｂi,k,jは、以下の２つの集合の交わりによって求めることができる。
【００７８】
【数７】
【００７９】
第１の中間領域Ｃi,k,jの計算は、Ｔk,j内の少なくとも１つの点から少なくともｄi,k−ｂだけ離れている、空間内の全ての点を見つけることによって行なわれる。
【００８０】
第２の中間領域Ｄi,k,jの計算は、Ｔk,j内の少なくとも１つの点から多くともｄi,k−ａだけ離れている、空間内の全ての点を見つけることによって行なわれる。
【００８１】
第１の中間領域Ｃi,k,jと第２の中間領域Ｄi,k,jとの交わりが、第３の中間領域Ｂi,k,jを与える。
【００８２】
次のステップは、領域Ｒiを少なくとも１つの四面体によって近似することである。
【００８３】
図２は、本発明が実施される基地局のようなデバイスのアーキテクチャを表す図である。
【００８４】
基地局ＢＳは、たとえば、バス２０１によって互いに接続される構成要素と、図３及び図４において開示されるようなプログラムによって制御されるプロセッサ２００とに基づくアーキテクチャを有する。
【００８５】
基地局ＢＳは、専用の集積回路に基づくアーキテクチャを有することもできることに留意されたい。
【００８６】
バス２０１は、プロセッサ２００を、リードオンリーメモリＲＯＭ２０２、ランダムアクセスメモリＲＡＭ２０３、無線インターフェース２０５、及びネットワークインターフェース２０６に接続する。
【００８７】
メモリ２０３は、図３及び図４において開示されるようなアルゴリズムに関連するプログラムの変数及び命令を受信するように意図されるレジスタを含む。
【００８８】
プロセッサ２００は、ネットワークインターフェース２０６の動作及び無線インターフェース２０５の動作を制御する。
【００８９】
リードオンリーメモリ２０２は、図３及び図４において開示されるようなアルゴリズムに関連するプログラムの命令を含み、それらの命令は、基地局ＢＳが起動される際にランダムアクセスメモリ２０３に転送される。
【００９０】
基地局ＢＳは、ネットワークインターフェース２０６を通して通信ネットワークに接続することができる。たとえば、ネットワークインターフェース２０６は、ＤＳＬ（デジタル加入者線）モデム、或いはＩＳＤＮ（統合サービスデジタル網）インターフェース等である。
【００９１】
図３は、本発明によるデバイスのロケーションを特定するためのアルゴリズムの一例を開示する。
【００９２】
本アルゴリズムは、基地局ＢＳ群の各基地局によって実行される。
【００９３】
より厳密には、本アルゴリズムは、基地局ＢＳ群の各基地局ＢＳのプロセッサ２００によって実行される。
【００９４】
本アルゴリズムは、基地局ＢＳ１のプロセッサ２００によって実行される場合として開示されることになる。
【００９５】
ステップＳ３００は初期化段階であり、プロセッサ２００は、基地局ＢＳ１が位置する領域を初期化する。たとえば、領域は、グローバルポジショニングシステム又はエリアコードから特定される。
【００９６】
次のステップＳ３０１において、プロセッサ２００は、無線インターフェース２０５において幾つかの測定値を取得できるか否か、及び、ネットワークインターフェース２０６を通して基地局群内の他の基地局ＢＳ２〜ＢＳ４から領域が受信されるか否かを調べる。
【００９７】
測定値は、距離ｄ1,2、ｄ1,3、及びｄ1,4を表す。測定値は、たとえば、基地局間で転送される信号の信号減衰或いは到着時間から求められる。
【００９８】
無線インターフェース２０５において測定値が取得でき、かつ、領域が受信されない限り、プロセッサ２００はステップＳ３０１を実行する。
【００９９】
無線インターフェース２０５において幾つかの測定値が取得でき、また基地局群内の他の基地局ＢＳ２〜ＢＳ４から領域が受信される場合には、プロセッサ２００はステップＳ３０２に進む。
【０１００】
受信される領域は、たとえば、多面体の角という形式で受信される。
【０１０１】
ステップＳ３０２において、プロセッサ２００は、受信された領域、及び以前に特定された基地局ＢＳ１の領域を用いて、基地局ＢＳ１が位置する領域を計算する。
【０１０２】
領域計算は、図４を参照しながら詳細に開示される。
【０１０３】
次のステップＳ３０３において、プロセッサ２００は、計算された領域を、ネットワークインターフェース２０６を通して基地局群内の他の基地局ＢＳ２〜ＢＳ４に向けて転送する。
【０１０４】
次のステップＳ３０４において、プロセッサ２００は、基地局ＢＳ１の領域が精緻化される必要があるか否かを調べる。
【０１０５】
計算された領域が以前に特定された１つ又は複数の領域と概ね同一である場合には、領域は再び精緻化される必要はない。または、ステップＳ３０１〜Ｓ３０４が所定の回数だけ実行されると、基地局ＢＳ１の領域は精緻化される必要がなくなる。
【０１０６】
基地局ＢＳ１の領域が精緻化される必要があるとき、プロセッサ２００はステップＳ３０１に戻る。
【０１０７】
そうでない場合には、プロセッサ２００はステップＳ３０５に進む。
【０１０８】
ステップＳ３０５において、プロセッサ２００は、最後に特定された領域において基地局ＢＳ１の位置を特定するために、位置決めアルゴリズムを実行する。
【０１０９】
たとえば、位置決めアルゴリズムが測定誤差の確率モデルに基づき、かつ基地局ＢＳ１の潜在的な位置ｘiについての事前確率密度関数ｐi（ｘi）が既知である場合には、結合確率密度を以下のように表すことができる。
【０１１０】
【数８】
【０１１１】
基地局ＢＳ１の位置が完全にわかっているか、或いは基地局ＢＳ１の位置が基準として選択される場合には、「事前（a priori）」はディラック関数であると見なされる。基地局ＢＳ１の位置が完全にわかっていない場合には、「事前（a priori）」は単に省かれる。
【０１１２】
たとえば、位置決めアルゴリズムは、最大事後（ＭＡＰ）アルゴリズムを用いる。その場合、
【０１１３】
【数９】
【０１１４】
である。
【０１１５】
たとえば、位置決めアルゴリズムは、確率モデルが仮定されない場合には、観測値と推定値との間の距離を最小にする非線形最小二乗（ＮＬＬＳ）推定器を用いる。
【０１１６】
【数１０】
【０１１７】
ＭＡＰ及びＮＬＬＳは非凸最適化問題であり、回避されるべき極小値（local minima）が存在する。領域を計算すると、最適化問題は制約条件付き最適化問題になり、各領域は１つの基地局の位置に関する１組の制約と見なすことができる。
【０１１８】
領域が多面体によって近似される場合には、制約は一次不等式になる。また、ニュートン法、最急降下法、擬似焼きなまし法、拡張カルマンフィルタ（ＥＫＦ）のような制約条件付き最適化アルゴリズムのための良好な出発点を選択するために、それらの領域を用いることもできる。
【０１１９】
たとえば、位置決めアルゴリズムは、ノンパラメトリック信念伝搬（ＮＢＰ）のような確率的手法を使用し、この手法では、各基地局における周辺確率密度を求めるために、粒子によって表されるメッセージが異なる基地局間で交換される。粒子はモンテカルロ技法を適用することによって選択される。領域が構成されるとき、粒子はこれらの領域内で選択されることになる。
【０１２０】
次のステップＳ３０６において、プロセッサ２００は、自身の位置を、他の基地局ＢＳに向けて、かつ／又は移動端末に向けて、かつ／又は無線セルラー通信ネットワークのコアネットワークデバイスに向けて転送する。
【０１２１】
次のステップＳ３０７において、プロセッサ２００は、基地局ＢＳ１の位置が精緻化される必要があるか否かを調べる。
【０１２２】
特定された位置が以前に特定された１つ又は複数の位置と概ね同一である場合、その位置は再び精緻化される必要はない。
【０１２３】
基地局ＢＳ１の位置が精緻化される必要がある場合には、プロセッサ２００はステップＳ３０５に戻る。
【０１２４】
そうでない場合には、プロセッサ２００は本アルゴリズムを中断する。
【０１２５】
図４は、本発明による、領域を特定するためのアルゴリズムの一例を開示する。
【０１２６】
本アルゴリズムは、基地局ＢＳ群の各基地局によって実行される。
【０１２７】
より厳密には、本アルゴリズムは各基地局ＢＳのプロセッサ２００によって実行される。
【０１２８】
本アルゴリズムは、基地局ＢＳ１のプロセッサ２００によって実行される場合として開示される。
【０１２９】
ステップＳ４００において、プロセッサ２００は、基地局ＢＳ群内の他の各基地局ＢＳ２〜ＢＳ４によって転送された領域を入手する。領域は多面体形状を有する。
【０１３０】
次のステップＳ４０１において、プロセッサ２００は、必要であれば、各領域を四面体に分解する。
【０１３１】
次のステップＳ４０２において、プロセッサ２００は、以下の公式を用いて各第１の中間領域Ｃi,k,jを計算する。
【０１３２】
【数１１】
【０１３３】
ただし、ｉは基地局ＢＳ１のインデックスであり、ｋは他の基地局ＢＳｋによって転送された領域のインデックスであり、ｊは領域Ｒｋを形成する四面体のインデックスである。
【０１３４】
Ｃi,k,j領域の一例が図５に与えられる。
【０１３５】
図５は、デバイスが位置する領域を特定するために用いられる第１の中間領域の一例を示している。
【０１３６】
第１の中間領域Ｃi,k,jの計算は、Ｔk,j内の少なくとも１つの点から少なくともｄi,k−ｂだけ離れている、空間内の全ての点を見つけることによって行なわれる。
【０１３７】
結果として、第１の中間領域Ｃi,k,jは、Ｔk,jの角を中心にして半径がｄi,k−ｂに等しい球の外側領域の和集合をとることによって得られる。これは、図５によって示されており、図５は２次元の例であるので、Ｔk,jは三角形である。
【０１３８】
半径Ｒａｄbがｄi,k−ｂに等しい円Ｃｉｒｃ１は、その中心が角Ｃｏｒ１である円である。
【０１３９】
半径Ｒａｄbがｄi,k−ｂに等しい円Ｃｉｒｃ２は、その中心が角Ｃｏｒ２である円である。
【０１４０】
半径Ｒａｄbがｄi,k−ｂに等しい円Ｃｉｒｃ３は、その中心が角Ｃｏｒ３である円である。
【０１４１】
この場合、第１の中間領域Ｃi,k,jは、３つの円板Ｃｉｒｃ１〜Ｃｉｒｃ３の交わりを除く、全てのハッチングされた空間である。
【０１４２】
次のステップＳ４０３において、プロセッサ２００は、以下の公式を用いて各第２の中間領域Ｄi,k,jを計算する。
【０１４３】
【数１２】
【０１４４】
第２の中間領域Ｄi,k,jの一例が図６に与えられる。
【０１４５】
図６は、デバイスが位置する領域を特定するために用いられる第２の中間領域の一例を示している。
【０１４６】
第２の中間領域Ｄi,k,jの計算は、Ｔk,j内の少なくとも１つの点から多くともｄi,k−ａだけ離れている、空間内の全ての点を見つけることによって行なわれる。
【０１４７】
四面体を考えるとき、第２の中間領域Ｄi,k,jは、Ｔk,jと、半径ｄi,k−ａの球である構造要素との膨張演算（又は畳み込み）によって生成される。
【０１４８】
それは、各面をそれに直交する方向においてｄi,k−ａだけ外側に平行移動し、結果として生じた面を円柱及び球の一部と繋げることによって求めることができる。図６は、Ｔk,jが三角形であるときの２次元における第２の中間領域Ｄi,k,jの一例を示している。
【０１４９】
半径Ｒａｄbがｄi,k−ａに等しい円Ｃｉｒｃ１’は、その中心が角Ｃｏｒ１である円である。
【０１５０】
半径Ｒａｄbがｄi,k−ａに等しい円Ｃｉｒｃ２’は、その中心が角Ｃｏｒ２である円である。
【０１５１】
半径Ｒａｄbがｄi,k−ａに等しい円Ｃｉｒｃ３’は、その中心が角Ｃｏｒ３である円である。
【０１５２】
次のステップＳ４０４において、プロセッサ２００は、第１の中間領域Ｃi,k,jと第２の中間領域Ｄi,k,jとの交わりを求めることによって、各第３の中間領域Ｂi,k,jを計算する。
【０１５３】
第３の中間領域Ｂi,k,jの一例が図７において与えられる。
【０１５４】
図７は、デバイスが位置する領域を特定するために用いられる、第１の領域と第２の領域とを合成することによって求められる第３の領域の一例を示している。
【０１５５】
図７は２次元の例である。
【０１５６】
第３の中間領域Ｂi,k,jは、図７においてハッチングされている。
【０１５７】
ひとたび、図７のような各第３の中間領域Ｂi,k,jが求められると、各第３の中間領域Ｂi,k,jは多面体によって近似され、２次元の場合には図８に示されるような三角形によって近似される。
【０１５８】
図８は、第３の中間領域の多面体への分解の一例である。
【０１５９】
第３の中間領域Ｂi,k,jの輪郭の近似は、平面から構成される、より小さな領域輪郭ｄを考えることによって実行することができる。輪郭は円弧から構成されるので、幾つかの接平面を形成することができる。
【０１６０】
第３の中間領域Ｂi,k,jの２つの近似が図８に示されている。
【０１６１】
図８は２次元の例である。
【０１６２】
図８に示されるように、第１の近似は多面体Ａｐｐｒ１及びＡｐｐｒ３から構成され、近似Ａｐｐｒ１は単一の三角形から構成され、近似Ａｐｐｒ３は複数の三角形から構成される多面体から構成される。
【０１６３】
第２の近似は多面体Ａｐｐｒ２及びＡｐｐｒ３から構成され、近似Ａｐｐｒ２は１つの多面体から構成され、近似Ａｐｐｒ３は複数の三角形から構成される多面体から構成される。
【０１６４】
次のステップＳ４０５において、プロセッサ２００は、第３の中間領域Ｂi,k,jから各第４の中間領域Ａi,kを計算する。
【０１６５】
第３の中間領域Ｂi,k,jの和集合が、第４の中間領域Ａi,kを形成する。
【０１６６】
次のステップＳ４０６において、プロセッサ２００は、基地局ＢＳ１の領域Ｒ1を計算する。第４の中間領域Ａi,kの交わりが、基地局が位置する領域Ｒ1の近似となる。
【０１６７】
基地局が位置する領域Ｒ1の一例が図９において与えられる。
【０１６８】
図９は、本発明に従って特定される、基地局が位置する領域の一例である。
【０１６９】
図９は２次元の例である。
【０１７０】
図９において、第４の中間領域Ａ1,2は、基地局ＢＳ２が位置する領域Ｒ2から計算された第４の中間領域である。図９において、基地局ＢＳ２が位置する領域Ｒ2は、三角形Ｔ2,1である。第４の中間領域Ａ1,2は、垂直線によってハッチングされているエリアである。
【０１７１】
図９において、第４の中間領域Ａ1,3は、基地局ＢＳ３が位置する領域Ｒ3から計算された領域である。図９において、第４の中間領域Ａ1,3は、第３の中間領域Ｂ1,3,1及びＢ1,3,2から構成されている。領域Ｒ3は、三角形Ｔ3,1及びＴ3,2から構成されている。第４の中間領域Ａ1,3は、斜線によってハッチングされているエリアである。
【０１７２】
第４の中間領域Ａ1,4は、基地局ＢＳ４が位置する領域Ｒ4から計算された領域である。図９において、領域Ｒ4は三角形Ｔ4,1である。第４の中間領域Ａ1,4は、水平線によってハッチングされているエリアである。
【０１７３】
領域Ｒ1は、第４の中間領域Ａ1,2とＡ1,3とＡ1,4との交わりである。
【０１７４】
当然、本発明の範囲から逸脱することなく、上記の本発明の実施形態に対して数多くの変更を行なうことができる。
【技術分野】
【０００１】
本発明は、包括的には、無線通信ネットワーク内のデバイスのロケーションを特定するための方法及び装置に関する。
【背景技術】
【０００２】
今日、新たに設置される無線セルラー通信デバイスの基地局のように、グローバルポジショニングシステム（ＧＰＳ：Global Position System）の機能又はデバイスを提供する専用デバイス又は移動電話のようなデバイスが益々多くなっている。
【０００３】
そのような端末は、衛星からブロードキャストされる信号を受信することができない建物のようなエリア内に位置する場合がある。
【０００４】
衛星によってブロードキャストされる信号を受信できる場合であっても、デバイスのロケーション、たとえば、デバイスが位置している建物の階を正確に特定することはできない。
【０００５】
陸上通信装置のような複数の発信源によって送信されてデバイスによって取得可能である信号の到着時刻の観測結果に基づいて、デバイスとそれらの発信源とを隔てる距離を推定することは、デバイスの位置を特定できるようにする既知の技法の一例である。
【０００６】
無線通信ネットワーク、たとえば、無線セルラー通信ネットワーク、又はアドホックネットワーク、又はセンサーをリンクするネットワークにおける、送信又は受信能力を有するノードの相対的又は絶対的なロケーションを、それらのノードを隔てる距離から特定することは多くの場合に正確ではない。Ｘmをｄ次元内のノードｍの位置ベクトルとし、ｄm,nをノードｍとｎとの間の観測される距離とすると、十分な数の完全な観測結果がある場合には、各ノードの位置を厳密に計算することができる。これは、全ての観測値ｄm,nに対する連立非線形方程式ｄm,n＝｜Ｘm−Ｘn｜を解くことによって行うことができる。グラフ剛性（graph rigidity）の原則を考慮に入れることによって、一意の解を得るための条件を取り扱うことができる。既知の絶対的なロケーションを有する幾つかのノードが存在する場合には、計算される位置は絶対的な位置であるが、そうでない場合には、幾つかのノードを基準として選択し、それらの基準に対して残りのノードのロケーションが相対的に特定される。
【０００７】
実際には、それらの測定値は誤差ｅm,nによって劣化しており、ｄm,n＝｜Ｘm−Ｘn｜＋ｅm,nである。誤差は、たとえば、受信機における同期誤差、信号を転送する複数のノードの非同期性、及び信号サンプリングに起因する時間測定値の精度の欠損を含む場合がある。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明は、簡単な方法で、かつノードの場所がアプリオリ（a priori）に正確にわかっていない場合であっても、ノードが位置する領域を特定できるようにするための方法及びデバイスを提供することを目的とする。
【課題を解決するための手段】
【０００９】
この目的のために、本発明は、無線通信ネットワークのノード群によって転送される信号からデバイスが位置する領域を特定するための方法に関する。
この方法は、デバイスのために繰返し実行される以下のステップ：
− ノード群の各ノードから、当該ノードが位置する領域を表す情報を受信するステップと、
− デバイスとノード群の各ノードとを隔てる距離を表す情報を取得するステップと、
− 受信された情報及び取得された情報から、デバイスが位置する領域を計算するステップと、
− デバイスが位置する上記計算された領域を、ノード群の各ノードに転送するステップと
を含むことを特徴とする。
【００１０】
また、本発明は、無線通信ネットワークのノード群によって転送される信号からデバイスが位置する領域を特定するための装置にも関する。
この装置は、
− ノード群の各ノードから、当該ノードが位置する領域を表す情報を受信する手段と、
− デバイスとノード群の各ノードとを隔てる距離を表す情報を取得する手段と、
− 受信された情報及び取得された情報から、デバイスが位置する領域を計算する手段と、
− デバイスが位置する上記計算された領域を、ノード群の各ノードに転送する手段と、
− 上記受信する手段、上記入手する手段、上記計算する手段、及び上記転送する手段を繰返し制御する手段と
を備えることを特徴とする。
【００１１】
それゆえ、何回かの繰り返しの後には、デバイスは自身が存在する領域のさらに良好な推定値を有するようになる。当該特定された領域をデバイスが転送するので、各ノードは自身が位置する領域を、デバイスが位置する領域を用いて精緻化することができる。
【００１２】
特定の特徴によれば、ノード群の各ノードから受信される各領域は、少なくとも１つの多面体によって近似される。
【００１３】
それゆえ、多面体は簡単な幾何学図形であるため、それらの多面体は容易に処理することができ、出力精度に大きな影響を及ぼすことなく、アルゴリズムの複雑度が低減される。
【００１４】
特定の特徴によれば、少なくとも１つの多面体は、四面体に分解される。
【００１５】
それゆえ、領域の計算の複雑度は非常に低い。
【００１６】
特定の特徴によれば、１つの多面体を分解した後に得られる各四面体について、当該四面体の少なくとも１つの点から少なくとも第１の距離だけ離れている、空間内の点を含む第１の中間領域が求められる。
【００１７】
それゆえ、領域の計算の複雑度は非常に低い。
【００１８】
特定の特徴によれば、１つの多面体を分解した後に得られる各四面体について、当該四面体の少なくとも１つの点から多くとも第２の距離だけ離れている、空間内の点を含む第２の中間領域が求められる。
【００１９】
それゆえ、領域の計算の複雑度は非常に低い。
【００２０】
さらに、デバイスが存在する領域を画定するために、ノードのロケーションの不確定性を考慮に入れることができる。
【００２１】
特定の特徴によれば、１つの多面体を分解した後に得られる各四面体について、当該四面体に対して求められた第１の中間領域及び第２の中間領域の交わりである第３の中間領域が求められる。
【００２２】
それゆえ、領域の計算の複雑度は非常に低い。
【００２３】
さらに、デバイスが存在する領域を画定するために、ノードのロケーションの不確定性を考慮に入れることができる。
【００２４】
特定の特徴によれば、各第３の中間領域は、少なくとも１つの多面体によって近似される。
【００２５】
それゆえ、多面体は簡単な幾何学図形であるため、それらの多面体は容易に処理することができ、出力精度に大きな影響を及ぼすことなく、アルゴリズムの複雑度が低減される。
【００２６】
特定の特徴によれば、ノード群のうちの１つのノードから受信された領域を近似する各多面体について、第４の中間領域が求められ、第４の中間領域は、ノード群のうちの１つのノードから受信された領域を近似する多面体を構成する四面体に対して求められた第３の中間領域の和集合である。
【００２７】
それゆえ、領域の計算の複雑度は非常に低い。
【００２８】
特定の特徴によれば、デバイスが位置する計算された領域は、第４の中間領域の交わりである。
【００２９】
それゆえ、領域の計算の複雑度は非常に低い。
【００３０】
さらに、デバイスは幾つかのノードの領域を考慮に入れることができ、それによって、デバイス自体の領域のサイズが小さくなる。
【００３１】
特定の特徴によれば、デバイスが位置する上記計算された領域は、少なくとも１つの多面体によって近似される。
【００３２】
それゆえ、領域の計算の複雑度は非常に低い。
【００３３】
特定の特徴によれば、この方法は、上記計算された領域が以前に計算された少なくとも１つの領域と異なる限り実行される。
【００３４】
そのため、各ノードの領域は繰返しを通じて狭められる。
【００３５】
特定の特徴によれば、本発明は、領域が特定されるデバイスによって実行される。
【００３６】
特定の特徴によれば、デバイスは無線通信ネットワークのノードであり、この方法は各ノードによって実行される。
【００３７】
そのため、ノード領域は相互に計算され、繰返しを通じて狭められる。
【００３８】
さらに別の態様によれば、本発明は、プログラム可能デバイス内に直接ロード可能であるコンピュータープログラムに関する。このコンピュータープログラムは、プログラム可能デバイス上で実行される際に本発明による方法のステップを実施するための命令又はコードの一部を含む。
【００３９】
コンピュータープログラムに関連する特徴及び利点は、本発明による方法及びデバイスに関連して先に記述されたのと同じであるので、ここでは繰り返さない。
【００４０】
本発明の特徴は、一例の実施形態に関する以下の説明を読むことからさらに明らかになり、当該説明は添付の図面を参照しながら提示される。
【図面の簡単な説明】
【００４１】
【図１】本発明が実施される無線セルラー通信ネットワークを表す図である。
【図２】本発明が実施される基地局のようなデバイスのアーキテクチャを表す図である。
【図３】本発明による、デバイスのロケーションを特定するためのアルゴリズムの一例を開示する図である。
【図４】本発明による、領域を特定するためのアルゴリズムの一例を開示する図である。
【図５】デバイスが位置する領域を特定するために用いられる第１の中間領域の一例の図である。
【図６】デバイスが位置する領域を特定するために用いられる第２の中間領域の一例の図である。
【図７】デバイスが位置する領域を特定するために用いられる第１の中間領域及び第２の中間領域を合成することによって求められる第３の中間領域の一例の図である。
【図８】第３の中間領域の多面体への分解の一例の図である。
【図９】本発明に従って特定される、デバイスが位置する領域の一例の図である。
【発明を実施するための形態】
【００４２】
図１は、本発明が実施される無線セルラー通信ネットワークを表す。
【００４３】
本発明は、本発明を実行するノードが基地局ＢＳである一例において開示されることになる。
【００４４】
本発明は、アドホックネットワーク又はセンサーネットワークにおいて実施することもできる。
【００４５】
基地局ＢＳは、ピコ基地局又はフェムト基地局及び／又はホーム基地局とすることもできる。
【００４６】
ピコ基地局又はフェムト基地局は、数百又は数十平方メートルをカバーするセルを管理する。
【００４７】
ホーム基地局は、ユーザーの自宅に位置する。
【００４８】
図１においては、４つの基地局ＢＳ１、ＢＳ２、ＢＳ３、及びＢＳ４からなる基地局群が示されている。基地局ＢＳ１、ＢＳ２、ＢＳ３、及びＢＳ４からなる群の各基地局ＢＳは信号を送信することができ、その信号は基地局群内の他の基地局ＢＳによって受信され、基地局群内の基地局間を隔てる距離を求めるために用いられる。信号は、その信号を転送する基地局ＢＳの地理的な位置に関する情報を含むことができる信号であってもよいし、または、基地局ＢＳの位置をアプリオリに知っている移動端末ＭＴによって受信される複数の信号の中から基地局ＢＳｉを一意に認識できるようにする信号である。
【００４９】
図１の例においては、デバイスがノードである。ここで、デバイスは移動端末であってもよいことに留意されたい。
【００５０】
簡単にするために、図１には４つの基地局ＢＳしか示されていないが、基地局群は、さらに多くの数の基地局ＢＳを含んでもよいし、さらに少ない数の基地局ＢＳを含んでもよい。
【００５１】
基地局ＢＳ群は、基地局ＢＳｉとそれに隣接する基地局を含む。
【００５２】
図１において、基地局ＢＳ群は、基地局ＢＳ１とそれに隣接する基地局ＢＳ２〜ＢＳ４を含む。
【００５３】
基地局ＢＳ１と基地局ＢＳ２との間の距離はｄ1,2で表される。基地局ＢＳ１と基地局ＢＳ３との間の距離はｄ1,3で表される。基地局ＢＳ１と基地局ＢＳ４との間の距離はｄ1,4で表される。基地局ＢＳ２と基地局ＢＳ３との間の距離はｄ2,3で表される。基地局ＢＳ３と基地局ＢＳ４との間の距離はｄ4,3で表される。基地局ＢＳ２と基地局ＢＳ４との間の距離はｄ4,2で表される。
【００５４】
本発明によれば、各基地局ＢＳｉ（ｉ＝１〜４）は、既知の距離又は区間に測定誤差があるものと仮定して、基地局ＢＳｉが位置する空間の領域を計算する。基地局ＢＳｉが位置する領域は、基地局ＢＳ群内の他の基地局ＢＳから受信される信号と、基地局ＢＳ群内の互いの基地局ＢＳによって計算されて転送される領域とから計算される。
【００５５】
本発明によれば、基地局ＢＳ群内の各基地局ＢＳｉは、基地局群内の他の基地局から受信される領域に従って基地局ＢＳｉが位置する領域を精緻化し、当該基地局ＢＳｉが位置する精緻化された領域を、基地局群内の他の基地局に再び転送する。
【００５６】
このプロセスは、領域精緻化の改善が見られなくなるまで繰り返し実行されるか、若しくは所定の繰返し回数だけ繰返し実行されるか、または、この繰返しプロセスは長期に渡って周期的に実行される。
【００５７】
領域精緻化の各ステップにおいて、ｄ次元における基地局ＢＳｉの領域Ｒiは、基地局群内の他の基地局ＢＳｋによって与えられる領域Ｒkの推定値から、以下のように計算される。
【００５８】
【数１】
【００５９】
ただし、Ｉi,kは誤差ｅi,kの区間であり、Ω（ｉ）は基地局ＢＳｉが属する基地局ＢＳ群内の他の基地局の集合であり、
【００６０】
【数２】
【００６１】
は次元ｄの数の集合であり、ｄは当該領域が特定される空間の次元である。
【００６２】
そして、これらの領域は繰返し計算される。開始時においては、大きな領域が特定される基地局もあれば、その位置が分かっている場合には完全にロケーションを特定することができる基地局もある。収束するまでの間、繰り返しの度に領域は収縮し、収束するとそれ以上の改善がもたらされなくなって領域の収縮が止まる。
【００６３】
本発明の特定の実現形態によれば、各領域は１つ又は複数の多面体によって近似することができる。その場合、１つ又は複数の多面体の角のみを基地局間で交換することができる。多面体の１つの特性は四面体に分解されることである。四面体は３次元における三角形である。
【００６４】
１つの変形では、領域輪郭の定義を円弧、線に分割することができ、領域輪郭のみが交換される。
【００６５】
基地局ＢＳｉの領域Ｒiは、以下のように表すことができる。
【００６６】
【数３】
【００６７】
ただし、Ａi,kは基地局ＢＳｋの領域Ｒkのみによって特定される領域であり、∩は交わりを表す。
【００６８】
各領域Ｒkを四面体Ｔk,jの和集合に分解することによって、Ａj,kは以下のように書き換えることができる。
【００６９】
【数４】
【００７０】
ただし、Ｂi,k,jは基地局ＢＳｋのみの四面体Ｔk,jのうちの１つから特定される領域であり、∪は和集合を表す。
【００７１】
基地局ＢＳｉとＢＳｋとの間で観測される距離はｄi,kであり、距離ｄi,kに関する誤差区間は［ａ，ｂ］である。エリアＢi,k,jは以下のように定義することができる。
【００７２】
【数５】
【００７３】
ｄmin（ｘ，Ｔk,j）及びｄmax（ｘ，Ｔk,j）を、点ｘとＴk,jの点との間の最小距離及び最大距離とする。
【００７４】
このとき、Ｂi,k,jを以下のように定義することができる。
【００７５】
【数６】
【００７６】
本発明の特定の実現形態によれば、Ｂi,k,jは多面体Ｔk,jの境界要素から計算される。
【００７７】
Ｂi,k,jは、以下の２つの集合の交わりによって求めることができる。
【００７８】
【数７】
【００７９】
第１の中間領域Ｃi,k,jの計算は、Ｔk,j内の少なくとも１つの点から少なくともｄi,k−ｂだけ離れている、空間内の全ての点を見つけることによって行なわれる。
【００８０】
第２の中間領域Ｄi,k,jの計算は、Ｔk,j内の少なくとも１つの点から多くともｄi,k−ａだけ離れている、空間内の全ての点を見つけることによって行なわれる。
【００８１】
第１の中間領域Ｃi,k,jと第２の中間領域Ｄi,k,jとの交わりが、第３の中間領域Ｂi,k,jを与える。
【００８２】
次のステップは、領域Ｒiを少なくとも１つの四面体によって近似することである。
【００８３】
図２は、本発明が実施される基地局のようなデバイスのアーキテクチャを表す図である。
【００８４】
基地局ＢＳは、たとえば、バス２０１によって互いに接続される構成要素と、図３及び図４において開示されるようなプログラムによって制御されるプロセッサ２００とに基づくアーキテクチャを有する。
【００８５】
基地局ＢＳは、専用の集積回路に基づくアーキテクチャを有することもできることに留意されたい。
【００８６】
バス２０１は、プロセッサ２００を、リードオンリーメモリＲＯＭ２０２、ランダムアクセスメモリＲＡＭ２０３、無線インターフェース２０５、及びネットワークインターフェース２０６に接続する。
【００８７】
メモリ２０３は、図３及び図４において開示されるようなアルゴリズムに関連するプログラムの変数及び命令を受信するように意図されるレジスタを含む。
【００８８】
プロセッサ２００は、ネットワークインターフェース２０６の動作及び無線インターフェース２０５の動作を制御する。
【００８９】
リードオンリーメモリ２０２は、図３及び図４において開示されるようなアルゴリズムに関連するプログラムの命令を含み、それらの命令は、基地局ＢＳが起動される際にランダムアクセスメモリ２０３に転送される。
【００９０】
基地局ＢＳは、ネットワークインターフェース２０６を通して通信ネットワークに接続することができる。たとえば、ネットワークインターフェース２０６は、ＤＳＬ（デジタル加入者線）モデム、或いはＩＳＤＮ（統合サービスデジタル網）インターフェース等である。
【００９１】
図３は、本発明によるデバイスのロケーションを特定するためのアルゴリズムの一例を開示する。
【００９２】
本アルゴリズムは、基地局ＢＳ群の各基地局によって実行される。
【００９３】
より厳密には、本アルゴリズムは、基地局ＢＳ群の各基地局ＢＳのプロセッサ２００によって実行される。
【００９４】
本アルゴリズムは、基地局ＢＳ１のプロセッサ２００によって実行される場合として開示されることになる。
【００９５】
ステップＳ３００は初期化段階であり、プロセッサ２００は、基地局ＢＳ１が位置する領域を初期化する。たとえば、領域は、グローバルポジショニングシステム又はエリアコードから特定される。
【００９６】
次のステップＳ３０１において、プロセッサ２００は、無線インターフェース２０５において幾つかの測定値を取得できるか否か、及び、ネットワークインターフェース２０６を通して基地局群内の他の基地局ＢＳ２〜ＢＳ４から領域が受信されるか否かを調べる。
【００９７】
測定値は、距離ｄ1,2、ｄ1,3、及びｄ1,4を表す。測定値は、たとえば、基地局間で転送される信号の信号減衰或いは到着時間から求められる。
【００９８】
無線インターフェース２０５において測定値が取得でき、かつ、領域が受信されない限り、プロセッサ２００はステップＳ３０１を実行する。
【００９９】
無線インターフェース２０５において幾つかの測定値が取得でき、また基地局群内の他の基地局ＢＳ２〜ＢＳ４から領域が受信される場合には、プロセッサ２００はステップＳ３０２に進む。
【０１００】
受信される領域は、たとえば、多面体の角という形式で受信される。
【０１０１】
ステップＳ３０２において、プロセッサ２００は、受信された領域、及び以前に特定された基地局ＢＳ１の領域を用いて、基地局ＢＳ１が位置する領域を計算する。
【０１０２】
領域計算は、図４を参照しながら詳細に開示される。
【０１０３】
次のステップＳ３０３において、プロセッサ２００は、計算された領域を、ネットワークインターフェース２０６を通して基地局群内の他の基地局ＢＳ２〜ＢＳ４に向けて転送する。
【０１０４】
次のステップＳ３０４において、プロセッサ２００は、基地局ＢＳ１の領域が精緻化される必要があるか否かを調べる。
【０１０５】
計算された領域が以前に特定された１つ又は複数の領域と概ね同一である場合には、領域は再び精緻化される必要はない。または、ステップＳ３０１〜Ｓ３０４が所定の回数だけ実行されると、基地局ＢＳ１の領域は精緻化される必要がなくなる。
【０１０６】
基地局ＢＳ１の領域が精緻化される必要があるとき、プロセッサ２００はステップＳ３０１に戻る。
【０１０７】
そうでない場合には、プロセッサ２００はステップＳ３０５に進む。
【０１０８】
ステップＳ３０５において、プロセッサ２００は、最後に特定された領域において基地局ＢＳ１の位置を特定するために、位置決めアルゴリズムを実行する。
【０１０９】
たとえば、位置決めアルゴリズムが測定誤差の確率モデルに基づき、かつ基地局ＢＳ１の潜在的な位置ｘiについての事前確率密度関数ｐi（ｘi）が既知である場合には、結合確率密度を以下のように表すことができる。
【０１１０】
【数８】
【０１１１】
基地局ＢＳ１の位置が完全にわかっているか、或いは基地局ＢＳ１の位置が基準として選択される場合には、「事前（a priori）」はディラック関数であると見なされる。基地局ＢＳ１の位置が完全にわかっていない場合には、「事前（a priori）」は単に省かれる。
【０１１２】
たとえば、位置決めアルゴリズムは、最大事後（ＭＡＰ）アルゴリズムを用いる。その場合、
【０１１３】
【数９】
【０１１４】
である。
【０１１５】
たとえば、位置決めアルゴリズムは、確率モデルが仮定されない場合には、観測値と推定値との間の距離を最小にする非線形最小二乗（ＮＬＬＳ）推定器を用いる。
【０１１６】
【数１０】
【０１１７】
ＭＡＰ及びＮＬＬＳは非凸最適化問題であり、回避されるべき極小値（local minima）が存在する。領域を計算すると、最適化問題は制約条件付き最適化問題になり、各領域は１つの基地局の位置に関する１組の制約と見なすことができる。
【０１１８】
領域が多面体によって近似される場合には、制約は一次不等式になる。また、ニュートン法、最急降下法、擬似焼きなまし法、拡張カルマンフィルタ（ＥＫＦ）のような制約条件付き最適化アルゴリズムのための良好な出発点を選択するために、それらの領域を用いることもできる。
【０１１９】
たとえば、位置決めアルゴリズムは、ノンパラメトリック信念伝搬（ＮＢＰ）のような確率的手法を使用し、この手法では、各基地局における周辺確率密度を求めるために、粒子によって表されるメッセージが異なる基地局間で交換される。粒子はモンテカルロ技法を適用することによって選択される。領域が構成されるとき、粒子はこれらの領域内で選択されることになる。
【０１２０】
次のステップＳ３０６において、プロセッサ２００は、自身の位置を、他の基地局ＢＳに向けて、かつ／又は移動端末に向けて、かつ／又は無線セルラー通信ネットワークのコアネットワークデバイスに向けて転送する。
【０１２１】
次のステップＳ３０７において、プロセッサ２００は、基地局ＢＳ１の位置が精緻化される必要があるか否かを調べる。
【０１２２】
特定された位置が以前に特定された１つ又は複数の位置と概ね同一である場合、その位置は再び精緻化される必要はない。
【０１２３】
基地局ＢＳ１の位置が精緻化される必要がある場合には、プロセッサ２００はステップＳ３０５に戻る。
【０１２４】
そうでない場合には、プロセッサ２００は本アルゴリズムを中断する。
【０１２５】
図４は、本発明による、領域を特定するためのアルゴリズムの一例を開示する。
【０１２６】
本アルゴリズムは、基地局ＢＳ群の各基地局によって実行される。
【０１２７】
より厳密には、本アルゴリズムは各基地局ＢＳのプロセッサ２００によって実行される。
【０１２８】
本アルゴリズムは、基地局ＢＳ１のプロセッサ２００によって実行される場合として開示される。
【０１２９】
ステップＳ４００において、プロセッサ２００は、基地局ＢＳ群内の他の各基地局ＢＳ２〜ＢＳ４によって転送された領域を入手する。領域は多面体形状を有する。
【０１３０】
次のステップＳ４０１において、プロセッサ２００は、必要であれば、各領域を四面体に分解する。
【０１３１】
次のステップＳ４０２において、プロセッサ２００は、以下の公式を用いて各第１の中間領域Ｃi,k,jを計算する。
【０１３２】
【数１１】
【０１３３】
ただし、ｉは基地局ＢＳ１のインデックスであり、ｋは他の基地局ＢＳｋによって転送された領域のインデックスであり、ｊは領域Ｒｋを形成する四面体のインデックスである。
【０１３４】
Ｃi,k,j領域の一例が図５に与えられる。
【０１３５】
図５は、デバイスが位置する領域を特定するために用いられる第１の中間領域の一例を示している。
【０１３６】
第１の中間領域Ｃi,k,jの計算は、Ｔk,j内の少なくとも１つの点から少なくともｄi,k−ｂだけ離れている、空間内の全ての点を見つけることによって行なわれる。
【０１３７】
結果として、第１の中間領域Ｃi,k,jは、Ｔk,jの角を中心にして半径がｄi,k−ｂに等しい球の外側領域の和集合をとることによって得られる。これは、図５によって示されており、図５は２次元の例であるので、Ｔk,jは三角形である。
【０１３８】
半径Ｒａｄbがｄi,k−ｂに等しい円Ｃｉｒｃ１は、その中心が角Ｃｏｒ１である円である。
【０１３９】
半径Ｒａｄbがｄi,k−ｂに等しい円Ｃｉｒｃ２は、その中心が角Ｃｏｒ２である円である。
【０１４０】
半径Ｒａｄbがｄi,k−ｂに等しい円Ｃｉｒｃ３は、その中心が角Ｃｏｒ３である円である。
【０１４１】
この場合、第１の中間領域Ｃi,k,jは、３つの円板Ｃｉｒｃ１〜Ｃｉｒｃ３の交わりを除く、全てのハッチングされた空間である。
【０１４２】
次のステップＳ４０３において、プロセッサ２００は、以下の公式を用いて各第２の中間領域Ｄi,k,jを計算する。
【０１４３】
【数１２】
【０１４４】
第２の中間領域Ｄi,k,jの一例が図６に与えられる。
【０１４５】
図６は、デバイスが位置する領域を特定するために用いられる第２の中間領域の一例を示している。
【０１４６】
第２の中間領域Ｄi,k,jの計算は、Ｔk,j内の少なくとも１つの点から多くともｄi,k−ａだけ離れている、空間内の全ての点を見つけることによって行なわれる。
【０１４７】
四面体を考えるとき、第２の中間領域Ｄi,k,jは、Ｔk,jと、半径ｄi,k−ａの球である構造要素との膨張演算（又は畳み込み）によって生成される。
【０１４８】
それは、各面をそれに直交する方向においてｄi,k−ａだけ外側に平行移動し、結果として生じた面を円柱及び球の一部と繋げることによって求めることができる。図６は、Ｔk,jが三角形であるときの２次元における第２の中間領域Ｄi,k,jの一例を示している。
【０１４９】
半径Ｒａｄbがｄi,k−ａに等しい円Ｃｉｒｃ１’は、その中心が角Ｃｏｒ１である円である。
【０１５０】
半径Ｒａｄbがｄi,k−ａに等しい円Ｃｉｒｃ２’は、その中心が角Ｃｏｒ２である円である。
【０１５１】
半径Ｒａｄbがｄi,k−ａに等しい円Ｃｉｒｃ３’は、その中心が角Ｃｏｒ３である円である。
【０１５２】
次のステップＳ４０４において、プロセッサ２００は、第１の中間領域Ｃi,k,jと第２の中間領域Ｄi,k,jとの交わりを求めることによって、各第３の中間領域Ｂi,k,jを計算する。
【０１５３】
第３の中間領域Ｂi,k,jの一例が図７において与えられる。
【０１５４】
図７は、デバイスが位置する領域を特定するために用いられる、第１の領域と第２の領域とを合成することによって求められる第３の領域の一例を示している。
【０１５５】
図７は２次元の例である。
【０１５６】
第３の中間領域Ｂi,k,jは、図７においてハッチングされている。
【０１５７】
ひとたび、図７のような各第３の中間領域Ｂi,k,jが求められると、各第３の中間領域Ｂi,k,jは多面体によって近似され、２次元の場合には図８に示されるような三角形によって近似される。
【０１５８】
図８は、第３の中間領域の多面体への分解の一例である。
【０１５９】
第３の中間領域Ｂi,k,jの輪郭の近似は、平面から構成される、より小さな領域輪郭ｄを考えることによって実行することができる。輪郭は円弧から構成されるので、幾つかの接平面を形成することができる。
【０１６０】
第３の中間領域Ｂi,k,jの２つの近似が図８に示されている。
【０１６１】
図８は２次元の例である。
【０１６２】
図８に示されるように、第１の近似は多面体Ａｐｐｒ１及びＡｐｐｒ３から構成され、近似Ａｐｐｒ１は単一の三角形から構成され、近似Ａｐｐｒ３は複数の三角形から構成される多面体から構成される。
【０１６３】
第２の近似は多面体Ａｐｐｒ２及びＡｐｐｒ３から構成され、近似Ａｐｐｒ２は１つの多面体から構成され、近似Ａｐｐｒ３は複数の三角形から構成される多面体から構成される。
【０１６４】
次のステップＳ４０５において、プロセッサ２００は、第３の中間領域Ｂi,k,jから各第４の中間領域Ａi,kを計算する。
【０１６５】
第３の中間領域Ｂi,k,jの和集合が、第４の中間領域Ａi,kを形成する。
【０１６６】
次のステップＳ４０６において、プロセッサ２００は、基地局ＢＳ１の領域Ｒ1を計算する。第４の中間領域Ａi,kの交わりが、基地局が位置する領域Ｒ1の近似となる。
【０１６７】
基地局が位置する領域Ｒ1の一例が図９において与えられる。
【０１６８】
図９は、本発明に従って特定される、基地局が位置する領域の一例である。
【０１６９】
図９は２次元の例である。
【０１７０】
図９において、第４の中間領域Ａ1,2は、基地局ＢＳ２が位置する領域Ｒ2から計算された第４の中間領域である。図９において、基地局ＢＳ２が位置する領域Ｒ2は、三角形Ｔ2,1である。第４の中間領域Ａ1,2は、垂直線によってハッチングされているエリアである。
【０１７１】
図９において、第４の中間領域Ａ1,3は、基地局ＢＳ３が位置する領域Ｒ3から計算された領域である。図９において、第４の中間領域Ａ1,3は、第３の中間領域Ｂ1,3,1及びＢ1,3,2から構成されている。領域Ｒ3は、三角形Ｔ3,1及びＴ3,2から構成されている。第４の中間領域Ａ1,3は、斜線によってハッチングされているエリアである。
【０１７２】
第４の中間領域Ａ1,4は、基地局ＢＳ４が位置する領域Ｒ4から計算された領域である。図９において、領域Ｒ4は三角形Ｔ4,1である。第４の中間領域Ａ1,4は、水平線によってハッチングされているエリアである。
【０１７３】
領域Ｒ1は、第４の中間領域Ａ1,2とＡ1,3とＡ1,4との交わりである。
【０１７４】
当然、本発明の範囲から逸脱することなく、上記の本発明の実施形態に対して数多くの変更を行なうことができる。
【特許請求の範囲】
【請求項１】
無線通信ネットワークのノード群（ＢＳ２、ＢＳ３、ＢＳ４）によって転送される信号からデバイス（ＢＳ１）が位置する領域を特定するための方法であって、
該方法は、前記デバイスのために繰返し実行される以下のステップ：
− 前記ノード群の各ノードから、該ノードが位置する領域であって少なくとも１つの多面体によって近似される領域を表す情報を受信するステップと、
− 前記デバイスと前記ノード群の各ノードとを隔てる距離を表す情報を取得するステップと、
− 前記受信された情報及び前記取得された情報から、前記デバイスが位置する領域を計算するステップ（Ｓ３０３）と、
− 前記デバイスが位置する前記計算された領域を、前記ノード群の各ノードに転送するステップ（Ｓ３０４）と
を含むことを特徴とする、無線通信ネットワークのノード群によって転送される信号からデバイスが位置する領域を特定するための方法。
【請求項２】
前記少なくとも１つの多面体は、四面体に分解されることを特徴とする、請求項１に記載の方法。
【請求項３】
１つの多面体を分解した後に得られる各四面体について、該四面体の少なくとも１つの点から少なくとも第１の距離だけ離れている、空間内の点を含む第１の中間領域を求めるさらなるステップを含むことを特徴とする、請求項２に記載の方法。
【請求項４】
１つの多面体を分解した後に得られる各四面体について、該四面体の少なくとも１つの点から多くとも第２の距離だけ離れている、空間内の点を含む第２の中間領域を求めるさらなるステップを含むことを特徴とする、請求項２に記載の方法。
【請求項５】
１つの多面体を分解した後に得られる各四面体について、該四面体に対して求められた前記第１の中間領域及び前記第２の中間領域の交わりである第３の中間領域を求めるさらなるステップを含むことを特徴とする、請求項３及び４に記載の方法。
【請求項６】
前記第３の中間領域は、少なくとも１つの多面体によって近似されることを特徴とする、請求項５に記載の方法。
【請求項７】
前記ノード群のうちの１つのノードから受信された領域を近似する各多面体について、第４の中間領域が求められ、該第４の中間領域は、前記ノード群のうちの１つのノードから受信された領域を近似する多面体を構成する四面体に対して求められた前記第３の中間領域の和集合であること特徴とする、請求項６に記載の方法。
【請求項８】
前記デバイスが位置する前記計算された領域は、前記第４の中間領域の交わりであることを特徴とする、請求項７に記載の方法。
【請求項９】
前記デバイスが位置する前記計算された領域は、少なくとも１つの多面体によって近似されることを特徴とする、請求項８に記載の方法。
【請求項１０】
前記方法は、前記計算された領域が以前に計算された少なくとも１つの領域と異なる限り実行されることを特徴とする、請求項１〜９のいずれか一項に記載の方法。
【請求項１１】
前記方法は、前記領域が特定されるデバイスによって実行されることを特徴とする、請求項１〜１０のいずれか一項に記載の方法。
【請求項１２】
前記デバイスは無線通信ネットワークのノードであり、前記方法は各ノードによって実行されることを特徴とする、請求項１〜１１のいずれか一項に記載の方法。
【請求項１３】
無線通信ネットワークのノード群（ＢＳ２、ＢＳ３、ＢＳ４）によって転送される信号からデバイス（ＢＳ１）が位置する領域を特定するための装置であって、
− 前記ノード群の各ノードから、該ノードが位置する領域であって少なくとも１つの多面体によって近似される領域を表す情報を受信する手段（２００）と、
− 前記デバイスと前記ノード群の各ノードとを隔てる距離を表す情報を取得する手段（２００）と、
− 前記受信された情報及び前記取得された情報から、前記デバイスが位置する領域を計算する手段（２００）と、
− 前記デバイスが位置する前記計算された領域を、前記ノード群の各ノードに転送する手段（２００）と、
− 前記受信する手段、前記取得する手段、前記計算する手段、及び前記転送する手段を繰返し制御する手段（２００）と
を備えることを特徴とする、無線通信ネットワークのノード群によって転送される信号からデバイスが位置する領域を特定するための装置。
【請求項１４】
プログラム可能デバイス内に直接ロード可能であるコンピュータープログラムであって、該コンピュータープログラムは、プログラム可能デバイス上で実行される際に請求項１〜１２に記載の方法のステップを実施するための命令又はコードの一部を含む、コンピュータープログラム。
【請求項１】
無線通信ネットワークのノード群（ＢＳ２、ＢＳ３、ＢＳ４）によって転送される信号からデバイス（ＢＳ１）が位置する領域を特定するための方法であって、
該方法は、前記デバイスのために繰返し実行される以下のステップ：
− 前記ノード群の各ノードから、該ノードが位置する領域であって少なくとも１つの多面体によって近似される領域を表す情報を受信するステップと、
− 前記デバイスと前記ノード群の各ノードとを隔てる距離を表す情報を取得するステップと、
− 前記受信された情報及び前記取得された情報から、前記デバイスが位置する領域を計算するステップ（Ｓ３０３）と、
− 前記デバイスが位置する前記計算された領域を、前記ノード群の各ノードに転送するステップ（Ｓ３０４）と
を含むことを特徴とする、無線通信ネットワークのノード群によって転送される信号からデバイスが位置する領域を特定するための方法。
【請求項２】
前記少なくとも１つの多面体は、四面体に分解されることを特徴とする、請求項１に記載の方法。
【請求項３】
１つの多面体を分解した後に得られる各四面体について、該四面体の少なくとも１つの点から少なくとも第１の距離だけ離れている、空間内の点を含む第１の中間領域を求めるさらなるステップを含むことを特徴とする、請求項２に記載の方法。
【請求項４】
１つの多面体を分解した後に得られる各四面体について、該四面体の少なくとも１つの点から多くとも第２の距離だけ離れている、空間内の点を含む第２の中間領域を求めるさらなるステップを含むことを特徴とする、請求項２に記載の方法。
【請求項５】
１つの多面体を分解した後に得られる各四面体について、該四面体に対して求められた前記第１の中間領域及び前記第２の中間領域の交わりである第３の中間領域を求めるさらなるステップを含むことを特徴とする、請求項３及び４に記載の方法。
【請求項６】
前記第３の中間領域は、少なくとも１つの多面体によって近似されることを特徴とする、請求項５に記載の方法。
【請求項７】
前記ノード群のうちの１つのノードから受信された領域を近似する各多面体について、第４の中間領域が求められ、該第４の中間領域は、前記ノード群のうちの１つのノードから受信された領域を近似する多面体を構成する四面体に対して求められた前記第３の中間領域の和集合であること特徴とする、請求項６に記載の方法。
【請求項８】
前記デバイスが位置する前記計算された領域は、前記第４の中間領域の交わりであることを特徴とする、請求項７に記載の方法。
【請求項９】
前記デバイスが位置する前記計算された領域は、少なくとも１つの多面体によって近似されることを特徴とする、請求項８に記載の方法。
【請求項１０】
前記方法は、前記計算された領域が以前に計算された少なくとも１つの領域と異なる限り実行されることを特徴とする、請求項１〜９のいずれか一項に記載の方法。
【請求項１１】
前記方法は、前記領域が特定されるデバイスによって実行されることを特徴とする、請求項１〜１０のいずれか一項に記載の方法。
【請求項１２】
前記デバイスは無線通信ネットワークのノードであり、前記方法は各ノードによって実行されることを特徴とする、請求項１〜１１のいずれか一項に記載の方法。
【請求項１３】
無線通信ネットワークのノード群（ＢＳ２、ＢＳ３、ＢＳ４）によって転送される信号からデバイス（ＢＳ１）が位置する領域を特定するための装置であって、
− 前記ノード群の各ノードから、該ノードが位置する領域であって少なくとも１つの多面体によって近似される領域を表す情報を受信する手段（２００）と、
− 前記デバイスと前記ノード群の各ノードとを隔てる距離を表す情報を取得する手段（２００）と、
− 前記受信された情報及び前記取得された情報から、前記デバイスが位置する領域を計算する手段（２００）と、
− 前記デバイスが位置する前記計算された領域を、前記ノード群の各ノードに転送する手段（２００）と、
− 前記受信する手段、前記取得する手段、前記計算する手段、及び前記転送する手段を繰返し制御する手段（２００）と
を備えることを特徴とする、無線通信ネットワークのノード群によって転送される信号からデバイスが位置する領域を特定するための装置。
【請求項１４】
プログラム可能デバイス内に直接ロード可能であるコンピュータープログラムであって、該コンピュータープログラムは、プログラム可能デバイス上で実行される際に請求項１〜１２に記載の方法のステップを実施するための命令又はコードの一部を含む、コンピュータープログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１１−２５９４３４（Ｐ２０１１−２５９４３４Ａ）
【公開日】平成２３年１２月２２日（２０１１．１２．２２）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１１−１２６６１５（Ｐ２０１１−１２６６１５）
【出願日】平成２３年６月６日（２０１１．６．６）
【出願人】（５０３１６３５２７）ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (175)
【氏名又は名称原語表記】ＭＩＴＳＵＢＩＳＨＩ ＥＬＥＣＴＲＩＣ Ｒ＆Ｄ ＣＥＮＴＲＥ ＥＵＲＯＰＥ Ｂ．Ｖ．
【住所又は居所原語表記】Ｃａｐｒｏｎｉｌａａｎ ４６， １１１９ ＮＳ Ｓｃｈｉｐｈｏｌ Ｒｉｊｋ， Ｔｈｅ Ｎｅｔｈｅｒｌａｎｄｓ
【Ｆターム（参考）】
【公開日】平成２３年１２月２２日（２０１１．１２．２２）
【国際特許分類】
【出願番号】特願２０１１−１２６６１５（Ｐ２０１１−１２６６１５）
【出願日】平成２３年６月６日（２０１１．６．６）
【出願人】（５０３１６３５２７）ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (175)
【氏名又は名称原語表記】ＭＩＴＳＵＢＩＳＨＩ ＥＬＥＣＴＲＩＣ Ｒ＆Ｄ ＣＥＮＴＲＥ ＥＵＲＯＰＥ Ｂ．Ｖ．
【住所又は居所原語表記】Ｃａｐｒｏｎｉｌａａｎ ４６， １１１９ ＮＳ Ｓｃｈｉｐｈｏｌ Ｒｉｊｋ， Ｔｈｅ Ｎｅｔｈｅｒｌａｎｄｓ
【Ｆターム（参考）】
[ Back to top ]