(57)【特許請求の範囲】
【請求項１】
位置検出方法であって：
複数のフィールドデバイスと一つのターゲットデバイスとに関連する領域に対応して設けられた格子の中の複数のノードを定義する段階と；
前記複数のノードにおける前記フィールドデバイスからの予測信号強度を、前記フィールドデバイスの位置と対応するノードまでの距離を用いて決定する段階であって、特定のノードにおけるそれぞれの予測信号強度は、前記フィールドデバイスの一つと関連する、段階と；
前記ターゲットデバイスと通信する前記フィールドデバイスのそれぞれのための、前記ターゲットデバイスにおける前記フィールドデバイスからの実信号強度を測定する段階であって、それぞれの実信号強度は前記フィールドデバイスの一つと関連する、段階と；
特定のフィールドデバイスの実信号強度より大きいか又は等しい、特定のフィールドデバイスの予測信号強度を有する前記ノードを有効なノードとして指定する段階と；
前記有効なノードのうち、前記フィールドデバイスの実信号強度が、前記フィールドデバイスの予測信号強度のフィンガープリントと一致する、少なくとも一つのノードを決定する段階と；
を有する、位置検出方法。
【請求項２】
前記予測信号強度を決定する段階は、
信号伝搬、予測される不確実性を含む信号伝搬、既知の障害物、潜在的な障害の確率及び空気湿度からなるグループから選択されるモデル化のファクターを用いて予測信号強度を決定する段階
をさらに有する、請求項１に記載の位置検出方法。
【請求項３】
少なくとも一つのフィールドデバイスがオフラインであるときを検出する段階
をさらに含み、
前記予測信号強度を決定する段階は、
少なくとも一つのオフラインのフィールドデバイスを明らかにする予測信号強度を決定する段階
をさらに有する、請求項１に記載の位置検出方法。
【請求項４】
前記実信号強度は第一の実信号強度であり、
前記ターゲットデバイスと通信する前記フィールドデバイスのそれぞれのための、前記ターゲットデバイスの第二の実信号強度を測定する段階であって、それぞれの実信号強度は前記フィールドデバイスの一つに関連する、段階と；
前記第二の実信号強度を前記第一の実信号強度と比較する段階と；
前記比較に基づいて前記領域内で物体が動いている可能性を決定する段階と；
を有する、請求項１に記載の位置検出方法。
【請求項５】
前記複数のノードにおいて、補助的な予測位置パラメータを決定する段階と；
前記実信号強度が前記予測信号強度と等しい前記有効なノードの少なくとも一つにおける補助的な実位置パラメータを測定する段階と；
前記補助的な予測位置パラメータと前記補助的な実位置パラメータとを比較する段階と；
をさらに有する、請求項１に記載の位置検出方法。
【請求項６】
前記補助的な実位置パラメータは、ＷｉＦｉ信号強度、温度、電気的雑音、光源レベル及び雑音レベルからなるグループから選択される
ことを特徴とする、請求項５に記載の位置検出方法。
【請求項７】
固定されたフィールドデバイスの既知の場所から少なくとも一つのフィールドデバイスの位置を推定する段階
をさらに有する、請求項１に記載の位置検出方法。
【請求項８】
前記有効なノードのうち、前記フィールドデバイスの実信号強度が前記フィールドデバイスの予測信号強度のフィンガープリントと一致する少なくとも一つのノードについて、予測されるノード位置を決定する段階と；
前記有効なノードのうち、前記実信号強度が前記予測信号強度と厳密に一致する少なくとも一つのノードについて、実際のノード位置を測定する段階と；
前記予測されるノード位置と前記実際のノード位置とを比較する段階と；
をさらに有する、請求項１に記載の位置検出方法。
【請求項９】
前記予測信号強度を決定する段階は、
前記予測されるノード位置と前記実際のノード位置とを比較することによる差に対して前記予測信号強度を補正する段階
をさらに有する、請求項８に記載の位置検出方法。
【請求項１０】
前記少なくとも一つのノードを決定する段階は、
信号強度における予測可能な変動のために前記予測信号強度を重み付けする段階
をさらに有する、請求項１に記載の位置検出方法。
【請求項１１】
前記予測信号強度を決定する段階は、ランダムに選択される複数のノードの初期集団のために、複数のノードにおける前記フィールドデバイスからの予測信号強度を決定する段階を有し、
前記少なくとも一つのノードを決定する段階は、
前記初期集団の適合度を試験する段階と；
前記適合度に基づいて前記初期集団から、複数のノードの、少なくとも一つの追加集団へと進化させる段階と；
前記少なくとも一つの追加集団の適合度を試験する段階と；
前記ターゲットデバイスの位置として前記有効なノードの少なくとも一つを、所定の適合度の値と所定の繰り返しの数とからなるグループから選択される基準に基づいて、決定する段階と；
を有する、請求項１に記載の位置検出方法。
【請求項１２】
前記少なくとも一つの追加集団へと進化させる段階は、遺伝的システムと人工免疫システムとからなるグループから選択されるシステムを用いて、少なくとも一つの追加集団へと進化させる段階
を有する、請求項１１に記載の位置検出方法。
【請求項１３】
位置検出システムであって：
一つのターゲットデバイスと；
複数のフィールドデバイスと；
一つのプロセッサと；
を有し、前記プロセッサは：
前記複数のフィールドデバイスと前記一つのターゲットデバイスとに関連する領域に対応して設けられた格子の中の複数のノードにおける前記フィールドデバイスからの予測信号強度を、前記フィールドデバイスの位置と対応するノードまでの距離を用いて決定し、特定のノードにおけるそれぞれの予測信号強度は、前記フィールドデバイスの一つと関連し；
前記ターゲットデバイスと通信する前記フィールドデバイスのそれぞれのための、前記ターゲットデバイスにおける前記フィールドデバイスからの実信号強度を測定し、それぞれの実信号強度は前記フィールドデバイスの一つと関連し；
特定のフィールドデバイスの実信号強度より大きいか又は等しい、特定のフィールドデバイスの予測信号強度を有する前記ノードを有効なノードとして指定し；
前記有効なノードのうち、前記フィールドデバイスの実信号強度が、前記フィールドデバイスの予測信号強度のフィンガープリントと一致する、少なくとも一つのノードを決定する；
よう機能することを特徴とする、位置検出システム。
【請求項１４】
前記プロセッサは、
少なくとも一つのフィールドデバイスがオフラインであるときを検出し、予測信号強度の決定において少なくとも一つのオフラインのフィールドデバイスを明らかにする
ようさらに機能する、請求項１３に記載の位置検出システム。
【請求項１５】
前記実信号強度は第一の実信号強度であり、
前記プロセッサは：
前記ターゲットデバイスと通信する前記フィールドデバイスのそれぞれのための、前記ターゲットデバイスの第二の実信号強度を測定し、それぞれの実信号強度は前記フィールドデバイスの一つに関連し；
前記第二の実信号強度を前記第一の実信号強度と比較し；
前記比較に基づいて前記領域内で物体が動いている可能性を決定する；
ようさらに機能する、請求項１３に記載の位置検出システム。
【請求項１６】
前記実信号強度が前記予測信号強度と等しい前記有効なノードの少なくとも一つにおける補助的な実位置パラメータを測定するよう機能する、補助的な位置パラメータのためのセンサ
をさらに有し、
前記プロセッサは、
前記複数のノードにおける補助的な予測位置パラメータを決定し；
前記補助的な予測位置パラメータと前記補助的な実位置パラメータとを比較する；
ようさらに機能する、請求項１３に記載の位置検出システム。
【請求項１７】
前記プロセッサは、
固定されたフィールドデバイスの既知の場所から少なくとも一つのフィールドデバイスの位置を推定する
ようさらに機能する、請求項１３に記載の位置検出システム。
【請求項１８】
前記有効なノードのうち、前記実信号強度が前記予測信号強度と厳密に一致する少なくとも一つのノードについて、実際のノード位置を測定するよう機能する、位置センサ
をさらに有し、
前記プロセッサは、
前記有効なノードのうち、前記実信号強度が前記予測信号強度のフィンガープリントと一致する少なくとも一つのノードについて、予測されるノード位置を決定し；
前記予測されるノード位置と前記実際のノード位置とを比較する；
ようさらに機能する、請求項１３に記載の位置検出システム。
【請求項１９】
前記プロセッサは、
信号強度における予測可能な変動のために前記予測信号強度を重み付けする
ようさらに機能する、請求項１３に記載の位置検出システム。
【請求項２０】
位置検出方法であって：
一つのターゲットデバイスと複数のフィールドデバイスとに関連する領域に対応して設けられた格子の中の複数のノードを定義する段階と；
前記フィールドデバイスにおける前記ターゲットデバイスの予測信号強度を、前記フィールドデバイスの位置と対応するノードまでの距離を用いて決定する段階であって、特定のフィールドデバイスにおけるそれぞれの予測信号強度は、前記複数のノードの一つと関連する、段階と；
前記ターゲットデバイスと通信する前記フィールドデバイスのそれぞれのための、前記フィールドデバイスにおける前記ターゲットデバイスからの実信号強度を測定する段階であって、それぞれの実信号強度は前記フィールドデバイスの一つと関連する、段階と；
前記特定のフィールドデバイスの実信号強度より大きいか又は等しい、前記特定のフィールドデバイスの予測信号強度を有する前記ノードを有効なノードとして指定する段階と；
前記有効なノードのうち、前記フィールドデバイスの実信号強度が、前記フィールドデバイスの予測信号強度のフィンガープリントと一致する、少なくとも一つのノードを決定する段階と；
を有する、位置検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、位置検出システム及び位置検出方法に関し、特に、フィンガープリント法を用いた位置検出システム及び位置検出方法に関する。
【背景技術】
【０００２】
無線通信ネットワーク及び無線制御ネットワークは、ホーム・オートメーション、ビルディング・オートメーション、医療インフラ、低電力ケーブルレスリンク、資産管理及び他のアプリケーションのため、ますます普及が進んでいる。そのようなネットワークの一つの利益は、ネットワークデバイス又はネットワークタグを設置する能力である。例えば、照明委託職員は、特定の無線デバイスを素早く識別できるため、導入コストが削減される。高価な機材はタグ付けされ、ビルの中及び周辺で追跡されることができる。このことにより、職員は、緊急時における使用又は校正のために必要なとき、タグ付けされた機材を容易に探すことができる。タグ付けされた機材は、特定の境界を越えて移動されたとき、警報を発することもできる。そのような無線通信ネットワーク及び無線制御ネットワークの一例は、低コストで、低電力で、ＩＥＥＥ８０２．１５．４の無線規格の上で動作するＺｉｇＢｅｅプロトコルを使用する無線規格である、ＺｉｇＢｅｅネットワークである。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
無線デバイスは、多数の固定点から距離を推定し、その距離推定から位置を三角測量することにより、探すことができる。しかし、その位置の正確さは、その距離推定の正確さに依存する。距離を推定する二つの方法は、ＴＯＦ（Ｔｉｍｅ  Ｏｆ  Ｆｌｉｇｈｔ）法及び信号強度である。ＴＯＦ法の距離推定による距離は、ある点から別の点を通る信号の時刻と、予期される信号速度とから計算される。信号強度の距離推定による距離は、信号強度の減少と、予期される信号強度の減衰とから計算される。不幸なことに、いくつかの無線通信ネットワーク及び無線制御ネットワークの帯域はとても狭く、ＴＯＦ法の距離推定を行うことができない。さらに、いくつかの無線通信ネットワーク及び無線制御ネットワークの信号強度は、減衰や、壁や人のような物体からの反射により、場所によって広く変化する。このことは、概して、ＴＯＦ法による距離推定又は信号強度による距離推定を阻む。
【０００４】
位置検出の他のアプローチは、フィンガープリント法である。信号強度は、無線通信ネットワークおよび無線制御ネットワークの領域にわたって、その領域のフィンガープリントの組、すなわち、その領域内のあらゆる位置にある近隣のデバイスからの信号強度の地図を決定するために測定される。見つけるべきデバイスは、そのデバイスの周りの、既知の位置のデバイスからの信号強度を測定する。測定された信号強度は、そのデバイスの位置を決定するために、フィンガープリントの組と比較される。不幸なことに、その領域のフィンガープリントの組を決定することは、多くの時間と労働力を要し、作業を費用のかかるものにする。さらに、測定された信号強度と、フィンガープリントの組との比較は、フィンガープリントの組全体にわたる比較を必要とするため、かなりの計算量と時間を必要とする。
【０００５】
上に述べた欠点を克服するフィンガープリント法を用いた位置検出システム及び位置検出方法が望まれる。
【課題を解決するための手段】
【０００６】
本発明の一つの実施形態は、位置検出方法であって：複数のフィールドデバイスと一つのターゲットデバイスとに関連する領域に対応して設けられた格子の中の複数のノードを定義する段階と；前記複数のノードにおける前記フィールドデバイスからの予測信号強度を、前記フィールドデバイスの位置と対応するノードまでの距離を用いて決定する段階であって、特定のノードにおけるそれぞれの予測信号強度は、前記フィールドデバイスの一つと関連する、段階と；前記ターゲットデバイスと通信する前記フィールドデバイスのそれぞれのための、前記ターゲットデバイスにおける前記フィールドデバイスからの実信号強度を測定する段階であって、それぞれの実信号強度は前記フィールドデバイスの一つと関連する、段階と；特定のフィールドデバイスの実信号強度より大きいか又は等しい、特定のフィールドデバイスの予測信号強度を有する前記ノードを有効なノードとして指定する段階と；前記有効なノードのうち、前記フィールドデバイスの実信号強度が、前記フィールドデバイスの予測信号強度と一致する、少なくとも一つの有効なノードを決定する段階と；を有する。
【０００７】
本発明の異なる実施形態は、位置検出システムであって：一つのターゲットデバイスと；複数のフィールドデバイスと；一つのプロセッサと；を有し、前記プロセッサは：前記複数のフィールドデバイスと前記一つのターゲットデバイスとに関連する領域に対応して設けられた格子の中の複数のノードにおける前記フィールドデバイスからの予測信号強度を、前記フィールドデバイスの位置と対応するノードまでの距離を用いて決定し、特定のノードにおけるそれぞれの予測信号強度は、前記フィールドデバイスの一つと関連し；前記ターゲットデバイスと通信する前記フィールドデバイスのそれぞれのための、前記ターゲットデバイスにおける前記フィールドデバイスからの実信号強度を測定し、それぞれの実信号強度は前記フィールドデバイスの一つと関連し；特定のフィールドデバイスの実信号強度より大きいか又は等しい、特定のフィールドデバイスの予測信号強度を有する前記ノードを有効なノードとして指定し；前記有効なノードのうち、前記フィールドデバイスの実信号強度が、前記フィールドデバイスの予測信号強度と一致する、少なくとも一つの有効なノードを決定する；よう機能することを特徴とする。
【０００８】
本発明のさらに異なる実施形態は、位置検出方法であって：一つのターゲットデバイスと複数のフィールドデバイスとに関連する領域に対応して設けられた格子の中の複数のノードを定義する段階と；前記フィールドデバイスにおける前記ターゲットデバイスの予測信号強度を、前記フィールドデバイスの位置と対応するノードまでの距離を用いて決定する段階であって、特定のフィールドデバイスにおけるそれぞれの予測信号強度は、前記複数のノードの一つと関連する、段階と；前記ターゲットデバイスと通信する前記フィールドデバイスのそれぞれのための、前記フィールドデバイスにおける前記ターゲットデバイスからの実信号強度を測定する段階であって、それぞれの実信号強度は前記フィールドデバイスの一つと関連する、段階と；前記特定のフィールドデバイスの実信号強度より大きいか又は等しい、前記特定のフィールドデバイスの予測信号強度を有する前記ノードを有効なノードとして指定する段階と；前記有効なノードのうち、前記フィールドデバイスの実信号強度が、前記フィールドデバイスの予測信号強度と一致する、少なくとも一つの有効なノードを決定する段階と；を有する。
【０００９】
本発明についての先述及び他の特徴及び利点は、添付される図面を読むとともに、現在の望ましい実施形態についての以下の詳細な説明からさらに明らかになる。詳細な説明及び図面は、添付されるクレーム及びその均等物によって定義される本発明の範囲を制限するのではなく、単に本発明の実例であるに過ぎない。
【００１０】
図面において、同様の参照文字は、一般に、異なる図面を通して同一の部分を示している。また、図面は必ずしもスケールが変更されておらず、一般に本発明の原理の説明が重視される。
【図面の簡単な説明】
【００１１】
【図１】本発明に従う位置検出システムの概略図。
【図２】本発明に従う位置検出システム及び位置検出方法での使用のための無線装置のブロック図。
【図３】本発明に従う位置検出方法のフローチャート。
【図４】本発明に従う異なる位置検出方法のフローチャート。
【発明を実施するための形態】
【００１２】
図１は、本発明のいくつかの実施形態に従う位置検出システムの概略図である。ある領域に関連する多数のフィールドデバイスは、その領域内のターゲットデバイスを探すために用いられる。
【００１３】
図１を参照すると、いくつかの実施形態において、位置検出システム２０は、複数のフィールドデバイス３０と少なくとも一つのターゲットデバイス４０を含む。フィールドデバイス３０は、多数のノード５２を含む一つの領域５０と関連する。フィールドデバイス３０は、領域５０に関する既知の場所にある。ターゲットデバイス４０は、領域５０に関する未知の場所にあり、位置が決定されるべき装置である。フィールドデバイス３０は互いに通信でき、及びターゲットデバイス４０と通信することができる。フィールドデバイス３０及び／又はターゲットデバイス４０は、領域５０の中又は外にある、任意の制御ユニット６０とも通信することができる。異なる実施形態において、任意の制御ユニット６０は、フィールドデバイス３０又はターゲットデバイス４０の一つに含まれることができる。領域５０の中又は外の障害物６２は、ターゲットデバイス４０及びフィールドデバイス３０の間の信号を減衰し、かつ／あるいは反射し得る。そうして、仮に障害物６２が存在していなかったとすると発生し得た信号強度から、ノード５２における信号強度を変化させる。例示的な障害物とは、壁、人及び家具等を含む。位置検出システム２０は、実際のノードの位置を測定するためのモバイル位置センサ、あるいは、実際の補助的な位置パラメータを測定するためのデバイスのような、任意の検知装置６４も含むことができる。補助的な位置パラメータとは、ＷｉＦｉ信号強度、気温、電気的雑音、光源レベル及び雑音レベル等である。任意の検知装置６４は、位置検出の正確さに応じてフィードバックを提供するために用いられることができる。あるいは、任意の検知装置６４は、領域内のフィールドデバイス及びそれらの周囲の状況についてのモデル化への追加の入力を提供するために用いられる。
【００１４】
領域５０は、多数のフィールドデバイス３０に関連する、あらゆる領域であり得る。フィールドデバイス３０は、領域５０の中又は外に存在することができ、ノード５２の上又はノード５２から外れて存在することができる。領域５０の中のノード５２は、特定のアプリケーションに要求される、あらゆるパターンにおいて定義されることができる。この例において、ノード５２は、デカルト格子内に配置される。ノード５２は、利用可能な計算資源が許し、さらにターゲットデバイス４０の探索における所望の正確さにより要求されるような間隔を有し、二次元又は三次元において定義されることができる。
【００１５】
フィールドデバイス３０は、ターゲットデバイス４０と無線で通信する。フィールドデバイス３０とターゲットデバイス４０は、ＩＥＥＥ８０２．１５．４の無線規格の上で動作するＺｉｇＢｅｅプロトコル、（８０２．１１ｂ／ｇ／ｎのような）ＩＥＥＥ規格８０２．１１に従うＷｉＦｉプロトコル、Ｂｌｕｅｔｏｏｔｈプロトコル又はＢｌｕｅｔｏｏｔｈ  Ｌｏｗ  Ｅｎｅｒｇｙプロトコル等のような、あらゆる所望のプロトコルを用いて通信することができる。ＺｉｇＢｅｅプロトコルシステムは、特に照明インフラが無線制御のためにＺｉｇＢｅｅプロトコルを用いるとき、固定の基準点における多数の野外デバイスを一般に有する。ターゲットデバイス４０を設置するとき、フィールドデバイス３０の場所が既知である限り、フィールドデバイス３０は固定又は可動であることができる。一つの実施形態において、少なくとも一つの野外デバイスの位置は、固定されたフィールドデバイスの既知の場所から推定されることができる。したがって、位置検出を開始するとき、全てのフィールドデバイスの位置は必要とされない。
【００１６】
図２は、本発明のいくつかの実施形態に従う位置検出システム及び位置検出方法とともに用いる無線装置のブロック図である。無線装置は、フィールドデバイス又はターゲットデバイスであり得る。この例において、無線装置は、送信器、受信器又は送信器と受信器であり、可動又は固定であることができる。
【００１７】
図２を参照すると、いくつかの実施形態において、無線装置７０は、メモリ７２、プロセッサ７４、送信器７６及び受信器７８を含む。メモリ７２は、データ及び／又は命令を保管するために適するあらゆるメモリであり得る。メモリ７２は、プロセッサ７４と情報を交換する。プロセッサ７４は、無線装置７０の演算を制御する。送信器７６及び受信器７８は、他の無線装置及び／又は中央制御センターと無線で通信する。さらに、送信器７６及び受信器７８は、アンテナを含むことができる。送信器７６は、プロセッサ７４からデータ及び命令を受信することができ、無線装置７０から信号を送信することができる。受信器７８は、無線装置７０の外部からの信号を受信することができ、データ及び命令をプロセッサ７４に提供することができる。
【００１８】
無線装置７０は、送信器、受信器又は送信器及び受信器として動作することができる。一つの実施形態において、送信器７６は省略されることができ、無線装置７０は受信器として動作することができる。異なる実施形態において、受信器７８は省略されることができ、無線装置７０は送信器として動作することができる。一つの実施形態において、無線装置７０は、ＩＥＥＥ８０２．１５．４の無線規格の上で動作するＺｉｇＢｅｅ通信プロトコルに従って動作する。他の実施形態において、無線装置７０は、（８０２．１１ｂ／ｇ／ｎのような）ＩＥＥＥ規格８０２．１１に従うＷｉＦｉプロトコル、Ｂｌｕｅｔｏｏｔｈプロトコル又はＢｌｕｅｔｏｏｔｈ  Ｌｏｗ  Ｅｎｅｒｇｙプロトコル等に従って動作する。当業者は、無線装置７０は、特定のアプリケーションに要求されるあらゆる無線プロトコルに従って動作できることを理解する。無線装置は、照明器具、照明制御ユニット、追跡されるべき資産、内科患者、又は他のあらゆる物体のような、別の物体と関連することができる。無線装置は、関連する物体を制御し、かつ／又は監視することもできる。
【００１９】
無線装置７０は、単一のキャリア周波数又は多数のキャリア周波数において信号を送信及び受信することができる。波長はキャリア周波数とともに変化するので、異なるフィールドデバイスからの信号間の障害と相互作用に対する感度は、異なるキャリア周波数とともに変化する。一つの実施形態において、プロセッサ７４は、異なるキャリア周波数間で無線装置７０の動作を切り替えることができる。
【００２０】
当業者は、プロセッサ７４は、計算能力及びデータ通信の容易さのため、必要に応じて、無線装置７０とともに、又は別の場所に設置される多数のプロセッサであることを理解するだろう。一つの実施形態において、プロセッサは、各無線装置におけるプロセッサ及び無線装置と通信する任意の制御ユニットにおける中央プロセッサを含む。
【００２１】
図３は、本発明のいくつかの実施形態に従った位置検出方法のフローチャートである。方法１００は、複数のフィールドデバイスと一つのターゲットデバイスとに関連する領域の中の複数のノードを定義する段階１０２と；前記複数のノードにおける前記フィールドデバイスからの予測信号強度を決定する段階１０４であって、特定のノードにおけるそれぞれの予測信号強度は、前記フィールドデバイスの一つと関連する、段階と；前記ターゲットデバイスと通信する前記フィールドデバイスのそれぞれのために、前記ターゲットデバイスにおける前記フィールドデバイスからの実信号強度を測定する段階１０６であって、それぞれの実信号強度は前記フィールドデバイスの一つと関連する、段階と；特定のフィールドデバイスの実信号強度より大きいか又は等しい、特定のフィールドデバイスの予測信号強度を有する前記ノードを有効なノードとして指定する段階１０８と；前記有効なノードのうち、前記フィールドデバイスの実信号強度が、前記フィールドデバイスの予測信号強度と一致する、少なくとも一つの有効なノードを決定する段階１１０と；を有する。方法１００は、上記の図１及び図２において示される位置検出システムとともに実行されることができる。計算の演算は、無線装置内のプロセッサ、分散プロセッサ、任意の制御ユニット内のプロセッサ及び／又は遠隔プロセッサで実行されることができる。
【００２２】
図３を参照すると、複数のフィールドデバイスと一つのターゲットデバイスとに関連する領域の中の複数のノードを定義する段階１０２は、前記ターゲットデバイスが設置され得る前記領域を設置する。前記フィールドデバイスは、生成する無線周波数信号が前記領域内にある限り、あるいは受信する無線周波数信号が前記領域から生じる限り、前記領域の外側に存在することができる。前記フィールドデバイスは、固定又は可動であることができるが、前記領域に対して既知の場所に存在する。一つの実施形態において、前記フィールドデバイスは、無線周波数信号を生成し、その無線周波数信号のいくつか又は全ては、前記ターゲットデバイスにより受信される。他の実施形態において、前記ターゲットデバイスは、無線周波数信号を生成し、その無線周波数信号のいくつか又は全ては、前記フィールドデバイスにより受信される。
【００２３】
前記ノードにおける前記フィールドデバイスからの予測信号強度（ＳＳＥ）を決定する段階１０４であって、特定のノードにおけるそれぞれの予測信号強度は、前記フィールドデバイスの一つと関連する、段階は、前記領域のためのフィンガープリントの組、すなわち、前記領域内のあらゆる位置の前記フィールドデバイス又はターゲットデバイスからの信号強度の地図を決定する。予測信号強度は、前記領域内の前記フィールドデバイス及びそれらの周囲の状況をモデル化する様々な方法により決定されることができる。
【００２４】
予測信号強度を決定するためのモデル化の一つの例は、例えば、関心領域を表す一様なデカルト格子に関して、それぞれのｘ−ｙノードのレコードを有する二次元の例のような、ノードにおける予測信号強度のレコード行列（又は多次元行列）を作成する。信号をもたらすフィールドデバイスに対応するフィールドデバイスノードのそれぞれのレコードは、前記フィールドデバイスノードの識別子（Node  A;Node  B；…；Node  X）、前記フィールドデバイスノードの座標（Ax,Ay;Bx,By;…;Xx,Xy）、前記フィールドデバイスノードの信号レベル（SignalLevelAtA;SignalLevelAtB;…;SignalLevelAtX）、及び特定のアプリケーションで要求される前記フィールドデバイスノードのあらゆる他のデータのようなデータを含むことができる。前記データは、自動推論によるハードコードされたプログラムを通じて入力されることができ、あるいはいくつかの他のユーザインターフェースを通じて手動で入力されることができる。
【００２５】
それぞれのフィールドデバイスからの、領域内のそれぞれのノードの予測信号強度は、前記フィールドデバイスノードのレコードから計算されることができる。ある予測信号レコードは、レコードであるRecordContents(x,y)とともに、（座標x,yにおける）前記格子の中のそれぞれのノードx,yのために構成されることができる。RecordContents(x,y)は、前記フィールドデバイスノードのそれぞれからの、前記ノードにおける信号レベルを含み、{signalLevelFromNodeA；signalLevelFromNodeB;…;signalLevelFromNodeX}に等しい。信号レベルの値は、前記フィールドデバイスノードから前記ノードへの距離を計算し、さらにその距離における信号強度の減少を推定することにより決定されることができる。例えば、フィールドデバイスノードA(Ax,Ay)からノード(x,y)への距離は、［(Ax-x)^2+(Ay-y)^2］の平方と等しい。ノードx,yにおける信号レベルの値SignalLevelFromNodeAは、SignalLevelAtA*fn（フィールドデバイスノードAからノードx,yの距離）に等しい。ここで、関数fn(x)は、ソースからの距離xにおける残存信号強度の推定値を返す。一般的な２．４ＧＨｚ点送信器の一つの実施形態においては、前記関数fn(x)は(X^-3.5)に等しい。計算は、それぞれのフィールドデバイスノードの前記領域内のそれぞれのノードのために実行され、前記領域内の全てのノードx,yのレコードであるRecordContents(x,y)を追加する。
【００２６】
一つの実施形態において、前記予測信号強度は、テーブル内に保持されることができる。テーブル空間及び計算量を節約する異なる実施形態において、特に計算が多数のノードのために実行されるべきときに、予測信号強度の計算は、あるノードのためのFNerrorの計算と組み合わされることができる。
【００２７】
当業者は、ノードにおける予測信号強度（ＳＳＥ）を決定する段階１０４、すなわち、領域のためのフィンガープリントの組のモデル化は、多くの方法により実行されることができ、特定のアプリケーションに要求されるように適応されることができることを理解するだろう。ノードにおけるフィールドデバイスからの予測信号強度（ＳＳＥ）を決定する段階１０４において、決定は、ノードにおける予測信号強度（ＳＳＥ）のさらなる正確さを提供するためのモデル化のファクターを用いることができる。例示的なモデル化のファクターは、信号伝搬、予測される不確実性を含む信号伝搬、既知の障害物、潜在的な障害の確率及び空気湿度等を含む。一つの実施形態において、信号伝搬、すなわちフィールドデバイスからの放射パターンは、レイトレーシングのような方法を用いてモデル化されることができる。このことは、特定の方向において、より強い信号又はゼロの信号を有する、特定の種類のアンテナのための補正を含むことができる。信号伝搬は、任意で、放射パターンにおける予測される不確実性を明らかにすることができる。異なる実施形態において、fn(x)が(X^-3.5)と等しいということよりも、距離に応じた放射パターンの減衰についてより複雑で正確なモデルを使用することができる。異なる実施形態において、距離に応じた放射パターンの減衰は、特定の屋内環境のために適するように、fn(x)が(X^-2.5)と等しくなるようにモデル化できる。異なる実施形態において、領域内の既知の障害物は、信号の反射及び／又は減衰を明らかにするようモデル化できる。ユーザインターフェースは、既知の障害物の位置及び種類を入力するために用いられることができる。異なる実施形態において、トラフィックのパターンは、人及び／又は物体が領域内に存在し、信号強度を変化させる可能性を明らかにするための、潜在的な障害物の可能性としてモデル化できる。異なる実施形態において、予期された空気湿度は、信号の減衰を明らかにするためにモデル化できる。ユーザインターフェース又は他の自動化されたセンサ入力は、領域全体の湿度及び／又は領域の特定の地域の湿度を入力するために、含まれることができる。
【００２８】
予測信号強度を決定する段階において、方法１００は、少なくとも一つのフィールドデバイスがオフラインであるときを検出し、少なくとも一つのオフラインのフィールドデバイスを明らかにする予測信号強度を決定することにより、オフラインであるフィールドデバイスを明らかにすることができる。オフラインのフィールドデバイスはもはや信号を生成しないため、最初にフィンガープリントの組のために計算された予測信号強度は、もはや領域内の予測信号強度を表していない。ターゲットデバイスは、オフラインのフィールドデバイスからの信号がないとみなし、信号強度が、特定のフィールドデバイスが遠く離れていることを示すものであると解釈する。結果として、ターゲットデバイスの位置検出の質は悪化する。一つの実施形態において、ユーザインターフェースは、オフラインである、あらゆるフィールドデバイスを入力するために、含まれることができる。実信号強度が予測信号強度と厳密に等しい、少なくとも一つの有効なノードを決定する場合において用いられる関数FNerrorは、オフラインのフィールドデバイスの条件を無視することができる。
【００２９】
ターゲットデバイスと通信するフィールドデバイスのそれぞれのために、前記ターゲットデバイスにおける前記フィールドデバイスからの実信号強度（ＳＳＡ）を測定する段階１０６であって、それぞれの実信号強度は前記フィールドデバイスの一つと関連する、段階は、予測信号強度（ＳＳＥ）との比較のために情報を取得する。ターゲットデバイスのレコードは、ターゲットデバイスにおいて受信される、フィールドデバイスノードのそれぞれからの信号レベルを含む、{signalLevelFromNodeA;signalLevelFromNodeB;…;signalLevelFromNodeX}と等しいレコードMeasuredRecordを有する実信号強度から構成されることができる。
【００３０】
特定のフィールドデバイスの実信号強度より大きいか又は等しい、特定のフィールドデバイスの予測信号強度（ＳＳＥ）を有するノードを有効なノードとして指定する段階１０８は、信号の物理的挙動を明らかにする。反射及び異常な状態以外の、特定のノードにおける特定のフィールドデバイスの、実信号強度の有効な測定値は、予測信号強度より小さいか、ほぼ等しい。すなわち、信号は物理的モデルと比べて増大せず、より減衰されあるいは吸収される傾向が強い。実信号強度が、あるターゲットデバイスがある特定のフィールドデバイスから１０メートル離れていることを示唆しているとき、そのターゲットデバイス及び特定のフィールドデバイスは、それらの間の経路が遮られておらず、弱まっていないとき、高い確率で１０メートルである。あるいは、経路が遮られ、弱められているとき、そのターゲットデバイス及び特定のフィールドデバイスは、１０メートルよりやや近くである。すなわち、そのターゲットデバイスと特定のフィールドデバイスは、より離れている可能性は低い。したがって、予測信号強度より大きい特定のフィールドデバイスの実信号強度を有するノードは、有効でないノードとして無視することができ、有効なノードのみがターゲットデバイスの設置において用いられることができる。当業者は、ここで定義される等しいという語は、ほぼ等しいことを含むため、実信号強度より大きい又は等しい予測信号強度を有する有効なノードとは、ある特定のアプリケーションに要求されるように、予測信号強度よりわずかに大きい実信号強度を有するノードを含むことができることを理解する。
【００３１】
有効なノードのうち、フィールドデバイスの実信号強度（ＳＳＡ）が、前記フィールドデバイスの予測信号強度（ＳＳＥ）と一致する、少なくとも一つの有効なノードを決定する段階１１０は、ターゲットデバイスが最も配置される可能性が高い場所、すなわちフィールドデバイスからの予測信号強度のフィンガープリントがターゲットデバイスにおいて検出された実信号強度に一致する場所のノードを選択する。一致とは、実信号強度（ＳＳＡ）と予測信号強度（ＳＳＥ）とが、前記決定の方法に適するやり方かつ前記決定の方法に適する程度に一致するときに起こるものとして、ここでは定義される。一つの実施形態において、実信号強度（ＳＳＡ）は、実信号強度（ＳＳＡ）と予測信号強度（ＳＳＥ）の間の誤差が最小化されるとき、予測信号強度（ＳＳＥ）と一致する。異なる実施形態において、実信号強度（ＳＳＡ）は、実信号強度（ＳＳＡ）と予測信号強度（ＳＳＥ）の間の誤差が所定の誤差値しかないとき、予測信号強度（ＳＳＥ）と一致する。異なる実施形態において、実信号強度（ＳＳＡ）は、全てのノードのための視覚的なディスプレイにおいて、誤差の合計の分布について、観察者によって発見されるパターンが、ターゲットデバイスに最もふさわしいノードであることを示すとき、予測信号強度（ＳＳＥ）と一致する。異なる実施形態において、実信号強度（ＳＳＡ）は、ノードのノード位置の平均が、ターゲットデバイスに最もふさわしいノードであることを示すとき、予測信号強度（ＳＳＥ）と一致する。当業者は、程度及び決定の方法が、ある特定のアプリケーションに要求されるように選択されることができることを理解するだろう。
【００３２】
一つの実施形態において、フィールドデバイスにおける実信号強度を含むレコードであるMeasuredRecordは、最適合致を見つけるために、それぞれのノードにおける予測信号強度を含む、見込まれるRecordContents(x,y)のそれぞれに対して比較されることができる。一つの例において、最小二乗法が用いられ、FNError[record1,record2]は、
[(record1:valueA-record2:valueA)^2+(record1:valueB-record2:valueB)^2+…+(record1:valueX-record2:valueX)^2]
の平方根に等しいような、二つのレコードを比較する最小二乗関数として定義されるFNerrorが用いられる。
【００３３】
ある特定のノードの予測信号強度を有するRecordContents(x,y)と、ターゲットデバイスの実信号強度を有するMeasuredRecordとを比較すると、FNerror[RecordContents(x,y),MeasuredRecord]が
[(RecordContents(x,y):signalLevelFromNodeA-MeasuredRecord:signalLevelFromNodeA)^2+
(RecordContents(x,y):signalLevelFromNodeB-MeasuredRecord:signalLevelFromNodeB)^2+…+
(RecordContents(x,y):signalLevelFromNodeX-MeasuredRecord:signalLevelFromNodeX)^2]
の平方根と等しい。個別に全ての(x,y)のためのFNerrorを計算した後、ターゲットデバイスの位置についての最善の推定値は、FNerror[RecordContents(x,y),MeasuredRecord]が最小となる位置(x,y)である。一つの実施形態において、ターゲットデバイスを見つけることのできる、もっともらしい、あるいは可能性のあるノードは、グラフ及び／又はリストの中に示され得る。ターゲットデバイスが既知のノードにおいて存在する確率は、そのグラフ又はリストに含まれることができる。一つの例において、FNerrorは、x、y軸上のノード位置、及びz軸上の確率の表示としてのFNerrorとともに、三次元グラフ上に示される。
【００３４】
当業者は、多数のバリエーション及び追加が、上で述べた位置検出方法のために可能であることを理解するだろう。
【００３５】
一つの実施形態において、実信号強度の変動は、フィールドデバイスからの信号を妨げる人又は他の物体のような、動く物体がフィールドデバイスの領域内に存在する場合を決定するために用いられることができる。第一の実信号強度は、ターゲットデバイスと通信するフィールドデバイスのそれぞれに対して、前記ターゲットデバイスのために測定されることができる。このとき、それぞれの実信号強度は前記フィールドデバイスの一つと関連する。前記ターゲットデバイスと通信するフィールドデバイスのそれぞれの第二の実信号強度が、次に測定される。第二の実信号強度は、第一の実信号強度と比較され、その比較に基づいて、物体が領域内で移動している可能性を決定することができる。
【００３６】
異なる実施形態において、予測信号強度は、前記有効なノードのうち、前記フィールドデバイスの実信号強度が、前記フィールドデバイスの予測信号強度と一致する、少なくとも一つの有効なノードを決定する１１０とき、信号強度における予測可能な変動のために重み付けされることができる。統計的手法が、変動する信号から、信号強度の変動を明らかにするために用いられることができる。実信号強度(MeasuredRecord)の組は、異なる時間において記録されることができ、信号が一定か変動しているかを評価するために用いられることができる。それぞれの特定のフィールドデバイスの、時間をかけて測定される最大実信号強度は、実信号強度の最良の推定値として扱われ、実信号強度の組から決定されることができる。最大実信号強度は、FNerror関数における単一の実信号強度値の代わりに用いられることができる。信号の障害の可能性は、ある特定のフィールドデバイスの実信号強度の組からの最小実信号強度を、前記特定のフィールドデバイスの最大実信号強度で割ることにより、フィールドデバイスのそれぞれのために計算されることができる。信号の障害の可能性は、フィールドデバイスの一つのFNerror関数を重み付けするタイミングを決定するために用いられる。すなわち、誤差のファクターは、予期しない状態が検出されたとき、高い誤差値を生成するために、FNerror関数へ適用されることができる。予期しない状態の例は、ある特定のフィールドデバイスの実信号強度が、一般に予期される信号強度より大幅に低いとき、つまり通常は妨害されないときに、前記特定のフィールドデバイスは妨害されたとと考えられるとき、あるいは、ある特定のフィールドデバイスの実信号強度が、最大実信号強度より大幅に大きいとき、つまり通常は妨害されるときに、前記特定のフィールドデバイスが妨害されないと考えられるときを含む。したがって、信号の障害の可能性は、フィンガープリント法の評価の一部になる。
【００３７】
異なる実施形態において、FNerror関数は、実信号強度が、あるノードにおける予測信号強度より高いとき、より高い誤差を与えるよう重み付けされることができる。一つの例において、実信号強度が予測信号強度より高いノードのENerror関数の項（ｔｅｒｍ）は、５の係数のような所定のペナルティ係数により乗算されることができる。重み付けは、実信号強度が、二つのノード間の距離の物理特性によって予測される予測信号強度と一般的に同様であるか、又はそれより小さいという観察に基づく。なぜなら、障害物は信号を吸収するためである。一つの例において、ある特定のフィールドデバイスの実信号強度より小さい、ある特定のフィールドデバイスの予測信号強度を有するノードは、誤差の大きな有効なノードとして指定されることができる。そして、誤差の大きな有効なノードを含む、有効なノードの少なくとも一つの決定にとりかかる。有効なノードにおいては、フィールドデバイスの実信号強度が、有効なノードの少なくとも一つにおける、フィールドデバイスの予測信号強度と一致する１１０。有効なノードの少なくとも一つを決定することは、フィールドデバイスの実信号強度と予測信号強度とを比較し、誤差関数FNerrorを最小化する有効なノードの少なくとも一つを決定することを含む。誤差の大きい有効なノードのための誤差項（ｅｒｒｏｒ  ｔｅｒｍｓ）は、他の有効なノードと比べて、誤差の大きい有効なノードにペナルティーを科すための所定のペナルティ係数によって積算される。
【００３８】
異なる実施形態において、位置検出方法は、ターゲットデバイスの位置の決定における、追加の環境パラメータを含むことができる。方法１００は、ノードにおいて補助的な予測位置パラメータを決定する段階と；実信号強度が予測信号強度と等しい有効なノードの少なくとも一つにおける補助的な実位置パラメータを測定する段階と；前記補助的な予測位置パラメータと前記補助的な実位置パラメータとを比較する段階と；を含むことができる。補助的な位置パラメータは、領域において検出され得る、あらゆる環境パラメータとしてここでは定義される。例となる補助的な位置パラメータは、ＷｉＦｉ信号強度、温度、電気的雑音、光源レベル及び雑音レベル等である。
【００３９】
異なる実施形態において、位置検出方法は、決定された位置の正確さに応じてフィードバックを含むことができる。方法１００は、フィールドデバイスの実信号強度が、有効なノードの一つにおけるフィールドデバイスの予測信号強度と一致する、有効なノードの少なくとも一つの、予測されるノード位置を決定する段階と；実信号強度が予測信号強度と厳密に一致する有効なノードの少なくとも一つの実際のノード位置を測定する段階と；前記予測されるノード位置と前記実際のノード位置を比較する段階と；を含むことができる。実際のノード位置は、任意の検知装置のようなモバイル装置を用いて測定されることができる。予測信号強度を決定する段階１０４において、予測信号強度は、予測されるノード位置と実際のノード位置とを比較することにより発見される、あらゆる差異に対して補正されることができる。
【００４０】
異なる実施形態において、位置検出方法は、進化的アルゴリズムのモデル化を用いることができる。計算の負荷は、領域内の全てのノードではなく、限られた数のノードの予測信号強度を計算することにより、進化的アルゴリズムのモデル化において削減される。遺伝的アルゴリズム（ＧＡ）に基づく遺伝システム又は人工免疫システムアルゴリズム（ＡＩＳ）に基づく人工免疫システムのような進化的アルゴリズム（ＥＡ）は、ターゲットデバイスのための最もふさわしい位置を選択し、最もふさわしい位置の周りのノードの予測信号強度を計算する。したがって、推測信号強度は、領域内の全てのノードについて最初に計算される必要はなく、推測信号強度は必要なときに計算されることができる。一つの実施形態において、推測信号強度は、計算されたとき、将来の使用のために保管される。これは、将来の使用のために必要とされるとき、再計算を避けるためである。
【００４１】
進化的アルゴリズムは、個体、すなわち問題に対する個々の可能性のある解が、いかに良くその問題を解くかを決定することに依存する。この性質の評価基準は、個体の適合度と呼ばれる。高い適合度の個体は、問題に対する解として試験される個体の、それに続く集団の発達に、より貢献する可能性が高い。位置検出の問題のために、適合度は、実信号強度と予測信号強度との間の信号強度の差を最小化する高い適合度の個体とともに、FNerror関数により決定されることができる。
【００４２】
進化アルゴリズムは、問題を解くための最適化アルゴリズムであり、一般に以下を含む高いレベルのアルゴリズムに従う。
１）問題に対する可能性のある解である個体の、ランダムな集団を生成する；
２）個々の個体の適合度を評価する、すなわちいかに良く個々の個体が問題を解くかを決定する；
３）評価された適合度を踏まえて、問題に対する潜在的な解である個体の新しい集団へと進化させる；
４）繰り返しの数又は所定の適合度のような、停止基準が満たされて停止するまで、評価と進化が繰り返される
進化的アルゴリズムは、位置検出方法１００に適用できる。予測信号強度の決定１０４において、ノードにおけるフィールドデバイスからの予測信号強度は、ランダムに選択されるノードの初期集団のために決定される。少なくとも一つの有効なノードを決定する段階１１０は、前記初期集団の適合度を試験する段階と；前記適合度に基づいて前記初期集団からノードの少なくとも一つの追加集団へと進化させる段階と；前記少なくとも一つの追加集団の適合度を試験する段階と；ターゲットデバイスの位置として有効なノードの少なくとも一つを、所定の適合度の値と所定の繰り返しの数とからなるグループから選択される基準に基づいて、決定する段階と；を含む。少なくとも一つの追加集団へと進化させる段階は、遺伝システムと人工免疫システムとから選択されるシステムを用いて、すなわち、遺伝的アルゴリズムに基づく遺伝システム又は人工免疫システムアルゴリズムに基づく人工免疫システムを適用して、少なくとも一つの追加集団を進化させる段階を含む。
【００４３】
位置検出の問題のため、所定の数の個体のランダムな集団は、領域内のランダムに選択されたノード(x,y)の組である。ターゲットデバイスは、前記ノードの一つの上、又は近くで見つけられ得るが、ランダムな選択により、その可能性はランダムである。適合度は、それぞれの個体（RecordContents(x,y)）の予測信号強度を計算又は探索し、予測信号強度とターゲットデバイス（MeasuredRecord）において測定される実信号強度とをFNerror関数を用いて比較することにより、評価される。問題の解決とターゲットデバイスの発見に最も近い、高い適合度の個体は、最も低いFNerror値を有する。一つの実施形態において、FNerror値は、０と１との間で正規化されることができる。個体の新たな集団の進化は、遺伝的アルゴリズム又は人工免疫システムアルゴリズムのような、用いられる進化的アルゴリズムの種類に依存する。しかし、新たな集団は、現在の世代（最適なノード）からの高い適合度の個体と、前記高い適合度の個体から進化した新たな個体（新たなノード）とを含む。適合度は新しい集団のために評価され、異なる新たな集団に進化する。そして、前記過程は、最も高い適合度のノードがターゲットデバイスの位置であることを示す、所望の基準を満たす適合度まで繰り返される。あるいは、前記過程は、最も高い適合度のノードがターゲットデバイスの最もふさわしい位置として指定される点で所定の数の繰り返しが完了するまで、繰り返される。
【００４４】
遺伝的アルゴリズムに基づく遺伝システム及び人工免疫システムアルゴリズムに基づく人工免疫システムは、個体の新たな集団を進化させる方法において異なる。
【００４５】
遺伝的アルゴリズムに基づく遺伝システムのために、現在の世代からの二つ以上の高い適合度の個体（最適なノード）が親ノードとして選択され、新たな個体ノード（新たなノード）が親ノードから進化する。典型的に、二つの親がランダムに選択され（一つの例において、高い適合度の個体に向けて偏りを有する方法に基づく）、交叉され、そして突然変異される。これらの二つの＊新たな＊個体は、次に、子の集団へと追加される。この過程は、子の集団がメインの集団と同じサイズになるまで繰り返される。そうすると、子の集団が次の繰り返しのためにメインの集団になる。
【００４６】
一つの例において、新たな個体のノードは、親ノード間の平均の位置にあるノードである。ＧＡにおいて、子孫を生成するために、選択される親に適用される二つの遺伝的圧力が存在する。一つの個体がx,y座標であるとすると、
P1=(x1,y1)
P2=(x2,y2)
である。交叉は、それぞれの親の部分を、二つの子へと組み合わせる。したがって、P1及びP2を前提として、交叉は二つの親の間でｙ成分を交換でき、
C1=(x1,y2)
C2=(x2,y1)
を生成する。突然変異は、次に、それらの子のそれぞれを（場合により）わずかに修正する。例えば、
C1_m=(x1+2,y2)
C2_m=(x2-1,y1+3)
である。当業者は、交叉及び突然変異がどのように生じるかについて、多数のバリエーションが存在することを理解するだろう。両方の操作は、一般的には所定の確率に基づく。例えば、交叉は８０％の確率で発生し、一方突然変異は５％程度の確率で発生する。二つの親の間の平均の位置は、交叉についての、別の可能性のある形態であり得る。これらは、次に、場合によっては突然変異され得る。
【００４７】
一つの実施形態において、新たな個体は、前の世代からの最適ノードの一部と、多数の新たな個体のノードとを含む。異なる実施形態において、新たな集団は、新たな個体のノードのみを含む。アルゴリズムがどのように設計されるかに依存して、ある集団から最も適合しないノードが廃棄されるが、いくつかは、多様性を維持し、不正な集中を避けるために、集団の中に保持され得る。次の（子の）集団は、上述のように、あらゆる適合性の低いノードの削除をすることなく、作成されることができる。集団のサイズは一定である。なぜなら、前の世代は完全に失われているためである。このため、親の集団からの最適ノードの一部は、子の集団において通常は保持される。一つの例において、遺伝的アルゴリズムは以下のように表すことができる。
−集団pop、サイズN
−While  繰り返しi<MAX_it
−  While  next_pop.size<=pop.size
−    popから二つの親をランダムに選択する。それぞれの個体の適合度に一般的には比例する。
−    いくつかの所定の確率に従って交叉を実行する（二つの掛け合わせた子を生成するために、それぞれの親の個体の“遺伝的な”表現の部分を組み合わせる）
−    いくつかの所定の確率に従って突然変異を実行する（情報のランダムな“遺伝的な”ビットを変化させる）
−    二つの子をnext_popに加える
−  next_popが生成されるまで繰り返す
−停止基準まで繰り返す  
人工免疫システムアルゴリズムに基づく人工免疫システムのために、高い適合度の個体は、個体の新たな集団へと進化させるために、クローン化され突然変異される。人工免疫システムアルゴリズムの一つの種類は、クローン選択理論に基づく。クローン選択理論は、ＣＬＯＮＡＬＧクローン選択において実装されるような、適合度に比例するクローン化及び反比例による突然変異を採用する。適合度に比例するクローン化と、適合度に反比例する突然変異との組み合わせにより、人工免疫システムアルゴリズムは、現在の良い解の周辺で局所探索を実行することができる。適合度は、人工免疫システムアルゴリズムに基づく人工免疫システムの親和度としても知られる。
【００４８】
高い適合度の所定の数の個体がクローン化のために選択され、適合度に従ってクローン化される。よりよい個体の適合度は、個体のより多くのクローンを生成する。例えば、最も高い適合度の個体は、５つのクローンへ、次に高いものは３つのクローンへ、さらに次に高いものは１つのクローンへとクローン化されることができる。当業者は、クローンの数を決定するための他のクローン化方法が、特定のアプリケーションに要求されるように用いられることができることを理解するだろう。
【００４９】
前記クローンは、前記クローンの適合度に反比例する突然変異の程度により、突然変異される。クローンの適合度が良いとき、クローンを最適解に向かわせるために必要とされる突然変異は、より少ない。クローンから突然変異されたノードまでの距離は、クローンの適合度に依存する。一つの実施形態において、突然変異されたノードは、クローンの適合度に対して反比例する、前記クローンから離れた距離において選択される。より適合度の高いクローンは、所望の解により近いクローンであり、したがって解に達するために突然変異する必要性が低い。異なる実施形態において、フィールドデバイスのそれぞれからの誤差のような、FNerrorの計算の構成成分が分析され、突然変異されたノードは、FNerror値を減らすための距離及び方向において変化される。
【００５０】
突然変異の方向は、何の情報が計算のための利用できるかに依存する。適合度の値のみが利用可能な一つの実施形態においては、方向はランダムである。さらなる情報が識別され得るとき、例えば、それぞれのフィールドデバイスからの信号強度が個別に考慮されるとき、突然変異の方向は、場合によってさらに影響を受け得る。一つの例において、突然変異は、個々の成分の信号強度の誤差を減らすために実行されることができる。異なる例において、方向は、適合度を改善する可能性のある角度の周りの統計的分布（例えば、正規分布）に基づいて選択されることができる。この角度は、（より適合度を高くするような、）現時点で最も低い信号強度の誤差を有するフィールドデバイスに対する角度、あるいは（より適合度を高くするような、）最大の信号強度誤差を有する角度に基づくことができる。当業者は、多数のバリエーションが可能であることを理解するだろう。
【００５１】
一般に、個体（クローン）の移動の全体的な方向は、適合度の計算、クローンの生成及び突然変異の過程によって影響される。突然変異されたクローンは、ランダムな方向において生成され；親より適合度の高いクローンは、次回の繰り返しにおいて、（親及び兄弟より）より多くのクローンを自分自身で生成し、そして次の一連の探索の中心を形成する。多数の繰り返しにわたって、探索の有効な中心は、子の適合度の改善に基づく一つ以上の方向において移動すると考えられる。
【００５２】
適合度の値は、突然変異されたノードのために計算されることができる。最も高い適合度の値を有する突然変異されたノードは、メモリ、あるいはクローン化に用いられる固体のメインの集団と異なる、個体の解の組の集団の中に保管されることができる。
【００５３】
現時点で最も確からしい位置として保管される個体は、より高い適合度の個体によってのみ、後続の繰り返しにおいて置き換えられることができ、より低い適合度の個体によっては置き換えられない。異なる実施形態において、最も高い適合度の値を有する突然変異された所定の数のノードは、ターゲットデバイスの現在の最も確からしい位置として保管されることができる。例えば、５つの最も確からしい突然変異されたノードが保管されることができる。所定の数の突然変異されたノードの位置におけるクローンのグループ分けの基準は、どの程度ターゲットデバイスが突然変異されたノードのグループの近くにあり得るかを決定するために計算されることができる。２Ｄ空間においてグループがより接近して固まっているとき、ターゲットデバイスはよりグループの近くに存在する。一つの例において、位置におけるグループ分けの近さは、グループのそれぞれのFNerror値の合計から決定されることができる。FNerrorは、それぞれのフィールドデバイスからの距離に基づいて、信号強度の誤差を計算する。それぞれの最も確からしいノードは、信号強度に関して共に近接し得るが、x,y座標に関して共に接近し得ない。異なる例において、ある集団の計測（ｃｌｕｓｔｅｒ  ｍｅａｓｕｒｅｍｅｎｔ）は、最も確からしいノードの間の２Ｄ距離に基づいて実行されることができる。さらに異なる例において、最も確からしいノードの中心（それぞれの座標次元の平均を意味する）が計算されることができ、それぞれのノードとこの中心との間の距離の合計（あるいは、平均距離）である。集団がより小型であると（すなわち、より小さい合計、あるいはより小さい平均距離）、デバイスが発見されるべき可能性のある目標領域は小さくなる。このことは、小さくてより小型な領域は、ターゲットデバイスがその領域内に存在する高い可能性を暗示すると仮定する。逆に、大きな目標領域は、あらゆる特定の点にターゲットデバイスの位置を絞ることができていない。角度もまた考慮されることができる。最も確からしいノードは、一つ以上の集団を形成する。閾値は、最も確からしいノードを適切な集団に割り当てるために用いられることができる。一つ以上の集団は、ターゲットデバイスのための一つ以上のふさわしい位置を示唆するだろう。これらの集団は、その集団におけるノードの数によって何らかのランク付けがなされることができる。ある集団においてより多くのノードがあるとき、そのエリア内にターゲットデバイスがある可能性が高い。当業者は、アプローチがＫ−ｍｅａｎｓ法のクラスタリングと同様であることを理解するだろう。
【００５４】
新たな集団が、次に作成される。突然変異されたノードを含む集団の、所定の数の個体は、ランダムに生成された個体と置き換えられることができる。クローンノード／突然変異されたノードは、メインの集団から分離されることができ、あるいは統合されることができる。集団の部分をランダムに生成された個体で置き換えることは、大域検索を実行することである。そうして、問題に対する潜在的な解空間にわたって新たな良い解を探す。さらに同様に、人工免疫システムアルゴリズムが極小値を免れることを支援する。一つの実施形態において、最も低い適合度の値を有する所定の数のノードは、ランダムに生成された個体で置き換えられる。他の実施形態において、適合度の値は選択メカニズムとして用いられる。このとき、適合度の値は、重み付け係数として用いられ、さらに確率論的手法により決定される、既知の個体の置換がその重み付け係数を含む。例えば、選択は、逆のルーレット選択であり得る。ルーレット選択は、合計を得るために、全ての個体の適合度の値を合計する。それぞれの個体の適合度をこの合計値で除算すると、（正規化され得る）合計についての割合が得られる。それぞれの個体は、次に、この正規化された割合に基づいてランク付けされることができる。ランダムの確率が、生成されることができ、さらにそのランダムな数値が適する割合に基づいて、適切な固体を選択するよう用いられることができる。このアプローチは、高い適合度のノードに偏らせる。低い適合度のノードに偏らせるためには、それぞれの正規化された割合は、１から上で計算された割合を減算する。当業者は、様々な方法が、ある特定のアプリケーションに要求されるように、クローン化されたセルをメインの集団へ導入するために用いられることができることを理解する。
【００５５】
遺伝的アルゴリズム又は人工免疫システムアルゴリズムを用いて進化した新たな集団は、停止基準を満たし、停止するまで繰り返し評価され進化することができる。例示的な停止基準は、所定の繰り返し数、あるいは予測信号強度にほぼ等しい実信号強度を有する位置が見つかっていることを示す所定の適合度の値を含む。
【００５６】
図４は、本発明のいくつかの実施形態に従った異なる位置検出方法のフローチャートである。この実施形態において、目標ノードが信号を送信し、フィールドデバイスが前記信号を検出する。前記フィールドデバイスは、実信号強度を、計算のための、任意の制御ユニットへ報告することができる。
【００５７】
方法２００は、一つのターゲットデバイスと複数のフィールドデバイスとに関連する領域の中の複数のノードを定義する段階２０２と；前記フィールドデバイスにおける前記ターゲットデバイスからの予測信号強度を決定する段階２０４であって、一つの特定のフィールドデバイスにおけるそれぞれの予測信号強度は、前記複数のノードの一つと関連する、段階と；前記ターゲットデバイスと通信する前記フィールドデバイスのそれぞれのために、前記フィールドデバイスにおける前記ターゲットデバイスからの実信号強度を測定する段階２０６であって、それぞれの実信号強度は前記フィールドデバイスの一つと関連する、段階と；前記特定のフィールドデバイスの前記実信号強度より大きいか又は等しい、前記特定のフィールドデバイスの前記予測信号強度を有する前記ノードを有効なノードとして指定する段階２０８と；前記有効なノードのうち、前記フィールドデバイスの実信号強度が、前記フィールドデバイスの予測信号強度と一致する、少なくとも一つの有効なノードを決定する段階２１０とを含む。
【００５８】
ここで複数の発明の実施形態が説明され図示されたが、当業者は容易に多様な他の手段、及び／又は機能を実行するための構造、及び／又は結果の取得、及び／又はここで説明される一つ以上の利点を想定するだろう。そして、そのようなバリエーション及び／又は改良のそれぞれは、ここで説明される発明の実施形態の範囲内であると考えられる。さらに一般的に、当業者は、ここで説明される全てのパラメータ、寸法、材料及び構成は、例示的なものであることを意味し、実際のパラメータ、寸法、材料及び／又は構成は、特定のアプリケーション又は本発明の教示が用いられるアプリケーションに依存することを理解するだろう。当業者は、日常的な実験を用いて、ここで説明される特定の発明の実施形態に対する多数の均等物を、認識あるいは確かめることができるだろう。したがって、先述の実施形態は、添付されるクレーム及びその均等物の範囲内において、例に関する方法によってのみ提供され、発明の実施形態は、特に説明され、クレームされるのとは別の方法で実行されることができる。本開示書の発明の実施形態は、ここで説明される、それぞれの個別の機能、システム、装置、素材、キット及び／又は方法に向けられる。さらに、そのような機能、システム、装置、素材、キット及び／又は方法のような二つ以上のあらゆる組み合わせは、そのような機能、システム、装置、素材、キット及び／又は方法が相互に矛盾しないときには、本開示書の発明の範囲内に含まれる。
【図１】
0005818779.tif 000002
【図２】
0005818779.tif 000003
【図３】
0005818779.tif 000004
【図４】
0005818779.tif 000005