(57)【要約】      （修正有）【課題】メッシュの区切り方を階層化し、順次計算を行い、最終的な精度で最大尤度に対応する位置を求める方法を提供する。【解決手段】対象エリアにおいて、尤度の最大値の位置を求め場合に、メッシュの区切り方を階層化し、順次計算を行い、最終的に指定のメッシュ間隔で最大尤度に対応する位置を求める方法を提案するものである。まず、粗いメッシュに対して、各メッシュの尤度を計算し、最大の尤度を探索する。次の最大の尤度の周辺の大きさを指定し、その指定領域において、メッシュの間隔を小さく区切る。指定領域において、微細なメッシュについて尤度を求め、順次同様にして尤度が最大となる位置を求め、最終指定のメッシュサイズとなるまで繰り返して、最大尤度に対応する位置を決定する。【選択図】図４
2005341516.tif 000002
【特許請求の範囲】
【請求項１】
指定された領域において、尤度が位置の関数となり、尤度が最大となる位置を求める問題に対して、前記指定領域を、予め計算した第一のメッシュで分割し、メッシュの交点に対して尤度を計算し、前記尤度が最大となる位置を求め、前記求めた位置を中心として新たなエリアを指定し、前記エリアを第二のメッシュ間隔で分割して、各メッシュ交点について尤度を計算し、順次最終の精度のメッシュ間隔となるまで尤度を計算する階層化計算方法に関し、最終メッシュサイズの計算までの計算回数が最小となるように最適な階層化数を求め、前記最適階層化数に対応する各階層におけるメッシュサイズを求め、前記の階層化計算に従って尤度を順次計算し、最終メッシュ間隔まで計算し、最大尤度と位置を求めることを特徴とする階層化最尤推定計算方式。
【請求項２】
請求項１において、領域を矩形領域とした階層化最尤推定計算方式。
【請求項３】
請求項１において、任意形状の領域を、前記領域を含む最小の矩形領域で覆い、前記矩形領域に対して最大の尤度と位置を階層化により計算する階層化最尤推定計算方式
【請求項４】
請求項１−３に対して、階層化段数を予め指定し、前記指定段数における各階層の最適なメッシュサイズを事前に計算し、前記メッシュサイズに従って、最大尤度と位置を階層的に求める階層化最尤推定計算方式。
【発明の詳細な説明】
【発明の詳細な説明】
【技術分野】
【０００１】    本発明は、指定された領域において、尤度が位置の関数となり、尤度が最大となる位置を求める計算アルゴリズムに関するものである。
【背景技術】
【０００２】    微細なメッシュに区切った位置の最適値を求める方法として、従来の手法を応用するばあい、次の２通りが知られている。第１の方法は、微細なメッシュの全体について、尤度を求め、最大値を探索し、最大値に相当する位置が最適値とする方法である。【０００３】    第２の方法は、初期メッシュの位置を指定し、そこを起点として山登り法を適用する方式である。
【発明が解決しようとする課題】
【０００４】    第１の方法は、メッシュ間隔を小さくすると、計算時間が、平面の場合で自乗オーダで増加することとなる。例えば、２００ｍ四方のエリアにおいて、４ｍ間隔のメッシュでは、２５００回の計算が必要となり、２ｍ間隔のメッシュでは、１００００回となる。このように精度を上げると計算回数は大幅に増加する。
【０００５】    第２の方法では、初期の位置に計算時間が依存することとなる。また、周辺を探索する時間がかかることとなる。更に、ローカルにミニマムが生じる場合は、最終的な解を得られないことも問題である。
【問題を解決するための手段】
【０００６】  本発明は、従来の問題を解決するため、メッシュの区切り方を階層化し、順次計算を行い、最終的な精度で最大尤度に対応する位置を求める方法を提案するものである。まず、粗いメッシュに対して、各メッシュの尤度を計算し、最大の尤度を探索する。次の最大の尤度の周辺の大きさを指定し、その指定領域において、メッシュの間隔を小さく区切る。指定領域において、微細なメッシュについて尤度を求め、最大値の位置を最適位置とする。この場合、メッシュの区切り方法を階層化し、、順次最適位置を追い込む方法である。この場合、各階層において、計算回数を最小にするメッシュサイズがあり、そのサイズに従って順次計算を行うことにより、最も計算回数が少なくなる。
【０００７】  以下、図面と式を用いて説明する。図１は、正方のエリアの場合である。正方でなくても同様に求めることができる。縦と横の長さをＬとする。最初のメッシュ間隔をｌ１とする。このサイズで、エリアを当分し、全メッシュ交点の尤度を求める。その最大値を中心として、２ｌ１で囲むエリアを指定する。次にそのエリアをｌ２のサイズで区切ることとする。２ｌ２で囲むエリアについて、尤度を求め、最大値の位置を求め、以下同様に繰り返す。
【０００８】尤度計算時間は、
Ｔ＝ｃ・Ｍ    ｃ：１つの要素計算時間（定数），Ｍ：計算回数  で表される。
ｎ階層における総合の計算回数をＭｎとし、計算回数の一般式を求める。
対象のエリアをＬ１×Ｌ２とする。
まず、一階層で行った場合の計算回数をＭ１とする。一階層とは、階層化を行わないことに対応する。最小メッシュ間隔をΔｌ１×Δｌ２とすると、
2005341516.tif 000003
となる。
【０００９】次に、２階層とした場合、最初のメッシュサイズをｌ１とすると、第一階層の計算数と第二階層の計算回数の和となる。
2005341516.tif 000004
である。計算最小回数の条件を求める。
【００１０】
2005341516.tif 000005
最小となる条件は、
2005341516.tif 000006
これより、
2005341516.tif 000007
であり、
2005341516.tif 000008
以下同様に、ｎ階層まで計算すると、計算の最小数は、
2005341516.tif 000009
で与えられる。
【００１１】    初期の分割線分は、以下で与えられる。
2005341516.tif 000010
以降の階層化段数ｉにおいては、以下の漸化式で求められる。
2005341516.tif 000011
ここで、分割数が整数倍となるための条件を求めると、Ｌ１に対する最初の分割数をｋ、Ｌ２に対する最初の分割数をｍとすると、
2005341516.tif 000012
を満たすことが必要となる。その場合の最終段階の分割メッシュサイズは
2005341516.tif 000013
最終分割メッシュサイズを指定した場合は、最初の分割数は必ずも整数とならないが、端の処理を適宜行うことにより実際は問題とならない。
【００１５】  以下、具体的な例をもって示す。対象領域をＬ＝２００［ｍ］の正方形とする。ここでは、最終段階メッシュサイズを指定し、Δｌ＝３，２．５，２，１．５，１，０．５ｍとする。式（８）にＬ，Δｌを代入してＭｎが最小値をもつｎ（階層数）をそれぞれ求め表１に示した。表１より、Δｌの値によって計算回数Ｔが最小となる最適な階層数が存在することを示している。最適な階層数が最小分割サイズによって異なるのは、メッシュ数が離散数となるためである。
2005341516.tif 000014
【発明を実施するための最良の形態】
【実施例】
【００１６】  ２００ｍ四方の領域をＲとし、Ｒ内で移動する端末の位置を推定する問題で発明の実施例を説明する。図１に実施例の対象エリアを示す。図１に示すよう、Ｒ内に予め複数のアクセスポイントＡＰが配置されているとする。また、領域内を移動機ＭＳが移動するとする。移動機ＭＳから電波が送信され、Ｒに配置された複数のアクセスポイントＡＰで端末からの電波を受信する。各アクセスポイントＡＰの座標は予め既知である。アクセスポイントＡＰにおける移動機からの電波の受信レベル情報から移動端末の位置を計算するものとする。【００１６】受信レベルは、距離と共に減衰するため受信レベルの大きさにより移動端末の位置の推定は可能である。もし、移動機ＭＳとアクセスポイントＡＰ間の伝搬に障害物がなく、直接伝搬の場合は、３つのアクセスポイントＡＰの受信レベルにより移動機の位置は一意に決定される。この場合は、探索の必要はない。しかし、一般に伝搬路には障害物が存在する場合がある。障害物が存在して電波が到着するのは、周囲の反射あるいは回折などのためである。これを一般にマルチパスと称する。マルチパス伝搬路の場合は、受信レベルは距離減衰以外に、マルチパスに起因する変動を伴うこととなる。この変動は、場所により異なり、従って、移動機ＭＳの位置によって異なることとなる。【００１７】移動機ＭＳの位置が事前に分からない場合は、確率的に扱うことが必要となる。移動端末とアクセスポイントの距離をｒとすると受信レベルは、以下の様に表せる。
2005341516.tif 000015
ここで、Ａは定数、αは距離減衰係数、Δは確率変数である。Δの確率分布が次式のようにデシベル正規分布に従うとする。
2005341516.tif 000016
但し、σは標準偏差である。今、３つのアクセスポイントＡｐｉが受信する受信レベルをΓｉとする。受信するアクセスポイントは、４以上とすれば精度は向上する。逆に２以下の場合は、推定位置は点と成らず面となる。【００１８】Δが確率変数のため、Γも確率変数となる。アクセスポイントＡｐｉにおける受信レベルをΓｉとし、移動機の位置をｘｓとすると、受信レベルΓｉを受信する確率は、ｐ（Γｉ｜ｘｓ）となる。受信レベルが与えられ、位置の確率は
2005341516.tif 000017
となる。但し、位置および、受信レベルの確率は一様とすると、Ｃは常数となる。すなわち、位置を推定することは、位置を変えて確率の変化を求めることに対応する。【００１９】確率が最も大きい場合を推定位置とすることにより位置の推定が可能となる。複数のアクセスポイントうぃ用いた時との推定位置の確率は、それらの積となり、それを尤度という。ｎ個のアクセスポイントで受信したとすると、
2005341516.tif 000018
となる。λに対して対数をとったものを対数尤度という。これをΛと表すと
2005341516.tif 000019
従って、式（５）により、位置の推定が可能となる。移動機ＭＳの位置の最尤推定は確率Λが最大となる位置である。  尤度を計算した例を図２に示す。縦軸が尤度の値で、尤も高い値が移動機の推定位置である。【００２０】  次に階層化手法によって計算する方法について説明する。移動機の位置を変化させて推定するため、領域Ｒをメッシュに分割する。  Ｌ＝２００ｍの正方形として、最終のメッシュ間隔をΔｌ１１＝Δｌ１２＝Δｌ＝０．５ｍとする。階層数は最適値の８とする。第一階層でのメッシュ間隔は、
2005341516.tif 000020
となる。このメッシュ間隔で区切る。端は、エリア外となるので、１６のメッシュの交点について尤度を計算する。尤度の最大のポイントをＰ１とする。Ｐ１を中心として２ｌ１の区域を設定する。その区域を長さｌ２でメッシュ分割を行う。ｌ２は、次式で与えられる。
2005341516.tif 000021
【００２１】同様に、尤度を計算し、最大の位置をＰ２とする。Ｐ２を中心として区域を設定し、ｌ３で分割する。ｌ３は
2005341516.tif 000022
である。以下同様に計算を行う。尤度の計算は、メッシュ分割された交点に対して、式（１６）より順次求めることが可能である。【００２２】第二の実施例として、対象エリアが矩形でない場合の処理方法を説明する。図９に例を示す。対象エリアを覆う最小の矩形領域を設定する。その矩形領域に対して、メッシュ分割を行い、同様に階層化手法を適用すればよい。この時、対象エリアから外れたメッシュの交点については、尤度はゼロとすればよい。対数尤度の場合は、負の十分大きい値を設定するばよい。【００２３】階層化におけるエリアの設定について、上記の説明では、最大の尤度を中心として、新たなメッシュサイズの２倍四方を設定する方法について説明したが、このエリアの設定は、２倍以上または、２倍以内でも可能である。大きくすると最終誤差は小さくなるが、時間がかかり、小さくすると時間は短縮されるが、誤差が大きくなり、両者のトレードオフとなる。
【発明の効果】
【００２４】  シミュレーションは５回行い、階層を行わなかった場合と、８階層の場合のコンピュータの計算時間を表２に示す。但し、パラメータはＡ＝１３０，α＝３．４σ＝２とした。
2005341516.tif 000023
表より、１階層に比較し、最適な８階層で行うと１４３倍計算時間が短縮される。更に、移動機の台数を１０台として同様なシミュレーションを行った結果を表３に示す。
2005341516.tif 000024
表３からわかるように、階層化を行なった場合移動機数を１０台に増やしてもシミュレーション時間が０．１２４［秒］に抑えられることが可能である。
【００２５】  計算回数に対して、最終メッシュ間隔をパラメータとし、非階層化の場合と最適階層化の比較を表４に示す。
2005341516.tif 000025
【００２６】表より、メッシュ間隔が３ｍの場合で、３６倍、０．５ｍの場合は、８４６倍計算回数が削減される。更に、階層化の場合は、メッシュ間隔を１／２とした場合、非階層化では、約４倍の計算数となるが、最適階層化の場合は、約１．２倍の増加にすぎない。最終メッシュ間隔を小さくするほど、その効果が大きい。
【００２７】  図７に、８段の階層化を行った場合と、階層化を行わない場合の位置の推定精度の比較をします。階層化を行わないことは、最小のメッシュサイズの全てについて計算した場合に相当する。図より、精度の差はなく、階層化により得られた推定が正しいことを示している。
【図面の簡単な説明】
【００２８】
【図１】対象とするエリアＲとアクセスポイントＡＰの配置
【図２】尤度の計算例、ｘ軸、ｙ軸はエリアを表し、縦軸は尤度の値を表す。
【図３】階層化アルゴリムにおけるメッシュの区切り方
【図４】階層化手法の計算のフローチャート
【図５】階層化の領域の変化の様子  第一階層において、ｌ１１，ｌ１２は、第一階層におけるメッシュの間隔を示す。Ｐ１は、第一階層の計算において求めた最大尤度の位置を示す。第二階層において、ｌ２１，ｌ２２は、第二階層におけるメッシュの間隔を示す。Ｐ２は、第二階層の計算において求めた最大尤度の位置を示す。
【図６】メッシュサイズをパラメータとした時の階層数と計算回数  Δｌは最終段階のメッシュサイズを示す。
【図７】メッシュサイズをパラメータとした時の階層数と計算回数。計算回数を線形で拡大して表示。
【図８】階層化手法を適用した場合と適用せず最小メッシュで最大尤度の位置を推定した場合の精度の比較。推定精度は、真の位置と推定位置の距離をｍで表示。
【図９】対象領域が非矩形領域の場合の領域の設定とメッシュ分割の例。
【図１】
2005341516.tif 000026
【図２】
2005341516.tif 000027
【図３】
2005341516.tif 000028
【図４】
2005341516.tif 000029
【図５】
2005341516.tif 000030
【図６】
2005341516.tif 000031
【図７】
2005341516.tif 000032
【図８】
2005341516.tif 000033
【図９】
2005341516.tif 000034