(57)【要約】デバイス割り当てのための、大規模で存在しているトポロジカル・グラフの低い精度、高い計算量および低い割り当て成功率という問題を解決するため、本発明はデバイス自動割り当てのための方法および装置を提案する。本発明のある側面によれば、各目標デバイスと諸基準デバイスとの間の測定された距離関係情報と、割り当てノードに対応する、諸基準デバイスと諸目標デバイスとの間の想定された距離関係情報とを比較し、次いで、差が最小の目標デバイスを割り当てノードに対応するものとして選択することによって、デバイスの割り当て精度が大幅に改善される。本発明のもう一つの側面によれば、複数の基準デバイスに基づいて、複数の割り当てノードにおける複数の目標デバイスを同時に、大きな安全マージンをもって決定することによって、割り当ての計算量が低下する。本発明のさらなる側面によれば、大きなトポロジカル・グラフをブロックに分割し、部分トポロジー・ブロックを割り当ておよび検証することによって、部分トポロジー・ブロックの割り当て精度が改善され、誤り分散が回避され、トポロジカル・グラフの全体的な割り当て成功率が向上する。
2012506192.tif 000002
【特許請求の範囲】
【請求項１】
トポロジカル・グラフ中での各目標デバイスの位置を決定する方法であって：
ａ．少なくとも二つの基準デバイスと各目標デバイスとの間の無線接続を確立する段階であって、前記基準デバイスのそれぞれの前記トポロジカル・グラフにおける位置は既知であり、前記トポロジカル・グラフは複数のノードの位置情報を含む、段階と；
ｂ．前記無線接続に基づいて、各目標デバイスの、前記少なくとも二つの基準デバイスに対する、測定距離関係情報を測定し、距離基準情報を得る段階と；
ｃ．前記距離基準情報に基づいて、各目標デバイスが前記ノードのどの位置に対応するかを決定する段階とを含む、
方法。
【請求項２】
請求項１記載の方法であって、前記段階ｂがさらに：
・各目標デバイスが前記トポロジカル・グラフ中のある割り当てノードの位置に位置されていると想定し、該想定のもとで、各目標デバイスの、前記少なくとも二つの基準デバイスに対する、想定距離関係情報を得る段階を含み；
各目標デバイスについて、前記距離基準情報は、その測定距離関係情報と前記割り当てノードについての想定距離関係情報との間の差を含み；
前記段階ｃがさらに：
・前記割り当てノードについて、前記目標デバイスの一つまたは複数から、その想定距離関係情報と測定距離関係情報との間の差が相対的に小さい一つの目標デバイスを、前記割り当てノードに対応する目標デバイスとして選択する段階を含む、
方法。
【請求項３】
請求項２記載の方法であって、前記段階ｃがさらに：
・前記割り当てノードについて、対応する想定距離関係情報と測定距離関係情報との間の差が最も小さい目標デバイスを、前記割り当てノードに対応する目標デバイスとして選択することを含む、
方法。
【請求項４】
請求項２記載の方法であって、前記段階ｃがさらに：
ｃ１．前記割り当てノードについて、想定距離関係情報と測定距離関係情報との間の差が相対的に小さい所定数の複数の候補目標デバイスを決定する段階と；
ｃ２．各候補目標デバイスを第一の補助基準デバイスとして取り、前記少なくとも二つの基準デバイスおよび前記第一の補助基準デバイスに従って、一つまたは複数の補助基準ノードに対応する一つまたは複数の補助目標デバイスがあると仮定する段階と；
ｃ３．前記一つまたは複数の補助基準ノードに対応する、候補目標デバイスと前記一つまたは複数の補助目標デバイスとの各組み合わせについて、前記候補目標デバイスおよび前記少なくとも二つの基準デバイスおよび前記対応する一つまたは複数の補助目標デバイスの間の無線接続に基づいて、前記候補目標デバイスの、前記少なくとも二つの基準デバイスおよび前記対応する一つまたは複数の補助目標デバイスに対する測定距離関係情報を測定し、前記一つまたは複数の補助目標デバイスが前記一つまたは複数の補助基準ノードに対応すると想定して、該想定のもとに、前記候補目標デバイスの、前記少なくとも二つの基準デバイスおよび前記対応する一つまたは複数の補助目標デバイスに対する、想定距離関係情報を得る段階と；
ｃ４．各組み合わせから、前記候補目標デバイスの、前記少なくとも二つの基準デバイスおよび前記対応する一つまたは複数の補助目標デバイスに対する測定距離関係情報と、その想定距離関係情報との間の差が最も小さい組み合わせを判別し、その組み合わせにおける候補目標デバイスが前記割り当てノードにおける目標デバイスに対応すると判定する段階とを含む、
方法。
【請求項５】
請求項４記載の方法であって、前記段階ｃ２がさらに：
ｃ２−１：前記候補目標デバイスの一つを第一の補助基準デバイスとして取り、近くの一つまたは複数の目標デバイスと少なくとも二つの基準デバイスおよび前記第一の補助デバイスとの間の無線接続に基づいて、前記一つまたは複数の目標デバイスの、前記少なくとも二つの基準デバイスおよび前記第一の補助基準デバイスに対する、測定距離関係情報を測定する段階と；
ｃ２−２：前記目標デバイスのそれぞれが前記補助基準ノードの一つに対応すると想定し、該想定のもとで、各目標デバイスの、前記少なくとも二つの基準デバイスおよび前記第一の補助基準デバイスに対する、想定距離関係情報を得る段階と；
ｃ２−３：前記補助基準ノードについて、すべての目標デバイスのうちから、前記目標デバイスの、前記少なくとも二つの基準デバイスおよび前記第一の補助基準デバイスに対する、想定距離関係情報と測定距離関係情報との間の差が相対的に小さい一つまたは複数の目標デバイスを、前記補助ノードに対応する補助目標デバイスとして決定する段階とを含み、
前記候補目標デバイスのそれぞれおよび前記補助基準ノードのそれぞれについて、上記の諸段階を繰り返すことを含む、
方法。
【請求項６】
請求項２ないし５のうちいずれか一項記載の方法であって、前記測定距離関係情報および想定距離関係情報が、対応するデバイス間での電波信号の受信信号強度指標RSSIおよび／または飛行時間を含み、想定距離関係情報と測定距離関係情報との間の前記差が、対応する目標デバイスが対応する位置にあるという想定のもとでの対応する目標デバイスと対応する基準デバイスとの間の相対的な想定されるRSSIベクトルと、それらの間の相対的な測定されるRSSIベクトルとの間のベクトル差、および／または、対応する目標デバイスが対応する位置にあるという想定のもとでの対応する目標デバイスと対応する基準デバイスとの間の想定される飛行時間と、それらの間の測定される飛行時間との間の差、を含む、
方法。
【請求項７】
請求項１記載の方法であって、前記トポロジカル・グラフ中でのノードの位置がグリッド形であり、前記段階ｂが：
・前記目標デバイスすべてのうちの所定数の複数の目標デバイスによって構成されるすべての候補グループを列挙し、前記各候補グループについて、所定の組み合わせ規則に従って、前記少なくとも二つの基準デバイスに対する、前記所定数の複数の目標デバイスの測定距離関係情報の数学的な組み合わせを決定する段階を含み、前記距離基準情報はすべての候補グループの対応する数学的組み合わせを含み；
前記段階ｃが：
ｃ１．すべての候補グループの対応する数学的組み合わせに基づいて、所定の規則に従って一つの目標候補グループを選択し、前記目標候補グループの所定数の複数の目標デバイスを、前記少なくとも二つの基準デバイスに近隣の所定数の複数の割り当てノードに対応する選択されたデバイスとして選択する段階と；
ｃ２．前記少なくとも二つの基準デバイスの少なくとも一つに対する、前記所定数の複数の選択されたデバイスの測定距離関係情報に基づいて、前記所定数の複数の選択されたデバイスのそれぞれがどの割り当てノードに対応するかを決定する段階とを含む、
方法。
【請求項８】
請求項７記載の方法であって、前記少なくとも二つの基準ノードは同じグリッド線上にあり、互いに隣接しており、前記目標デバイスのそれぞれは前記少なくとも二つの基準デバイスの同じ側にあるおよび／または前記少なくとも二つの基準デバイスと同じグリッド線上にあり、前記所定数の複数の割り当てノードは前記基準デバイスのそれぞれに同じ側で隣接しており、前記距離関係情報は対応するデバイス間での電波信号の受信信号強度指標RSSIおよび／または飛行時間を含み、前記数学的組み合わせは電波信号のRSSIおよび／または飛行時間の線形結合である、方法。
【請求項９】
請求項１ないし８のうちいずれか一項記載の方法であって、さらに：
ｄ．前記割り当てノードに対応すると決定された前記目標デバイスを新しい基準デバイスとして取り、段階ａないしｃを繰り返すことを、前記トポロジカル・グラフ中のすべてのノードに対応する目標デバイスが決定されるまで行う、
方法。
【請求項１０】
トポロジカル・グラフ中の各目標デバイスの位置を決定する方法であって、前記トポロジカル・グラフは複数のノードの位置情報を含み、当該方法は：
Ａ．前記トポロジカル・グラフを、所定の規則に従って、割り当てられるべきある数の部分トポロジー・ブロックに分割し、割り当てられるべき前記部分トポロジー・ブロックの一つまたは複数に隣接する基準ブロックを決定する段階と；
Ｂ．割り当てられるべき前記目標部分トポロジー・ブロックに隣接する前記基準ブロックの基準デバイスを、初期基準デバイスとして取り、初期割り当て方法を使って初期割り当てを実行し、前記目標部分トポロジー・ブロックの各ノードがそれぞれ対応する前記目標デバイスの存在を仮定する段階と；
Ｃ．前記初期基準デバイスとは異なる検証基準デバイスおよび／または前記初期割り当て方法とは異なる検証割り当て方法を使って検証割り当てを実行し、前記目標部分トポロジー・ブロックの各ノードがそれぞれ対応する前記目標デバイスの存在を仮定する段階と；
Ｄ．前記初期割り当ての仮定結果が前記検証割り当ての仮定結果と同一であれば、前記目標部分トポロジー・ブロックが割り当てられたと判断し、前記仮定結果が異なっていれば、前記目標部分トポロジー・ブロックが相変わらず割り当てられるべきであると判断する段階と；
Ｅ．割り当てられるべき前記部分トポロジー・ブロックすべてを割り当てるために、基準ブロックとして委託された前記部分トポロジー・ブロックすべてを取り、前記段階ＢないしＤを繰り返す段階とを含む、
方法。
【請求項１１】
請求項１０記載の方法であって、前記段階Ａにおいて基準ブロックを決定する段階が：
・第一の基準デバイスに基づいて、第一の割り当て方法を使って、前記基準ブロック中の各ノードにそれぞれ基準デバイスが対応すると仮定する段階と；
・前記第一の基準デバイスとは異なる第二の基準デバイスおよび／または前記第一の割り当て方法とは異なる第二の割り当て方法を使って、前記基準ブロック中の各ノードにそれぞれ対応する基準デバイスの存在を仮定する段階と；
・前記第二の基準デバイスおよび／または前記第二の割り当て方法に対応する仮定結果が前記第一の基準デバイスおよび前記第一の割り当て方法に対応する仮定結果と同一であれば、前記仮定結果に従って、前記基準ブロック中の各ノードに対応する基準デバイスをそれぞれ決定する段階とを含む、
方法。
【請求項１２】
請求項１０または１１記載の方法であって、前記検証基準デバイスは、前記段階Ｂにおいて仮定される前記目標部分トポロジー・ブロック中の目標デバイスを含む、方法。
【請求項１３】
トポロジカル・グラフ中での各目標デバイスの位置を決定する割り当て装置であって、前記トポロジカル・グラフは複数のノードの位置情報を含み、前記トポロジカル・グラフにおける少なくとも二つの基準デバイスの位置は既知であり、各基準デバイスと前記目標デバイスのそれぞれとの間に無線接続があり、当該割り当て装置は：
・前記少なくとも二つの基準デバイスに対する、前記各目標デバイスの測定距離関係情報を受け取るよう構成された受信機と；
・距離基準情報を得るよう構成された第一の取得手段と；
・前記距離基準情報に基づいて、各目標デバイスがそれぞれ前記ノードのどの位置に対応するかを決定するよう構成された第一の決定手段とを有する、
装置。
【請求項１４】
請求項１３記載の装置であって、前記第一の取得手段がさらに：
各目標デバイスが前記トポロジカル・グラフ中のある割り当てノードの位置に位置されていると想定し、該想定のもとで、各目標デバイスの、前記少なくとも二つの基準デバイスに対する、想定距離関係情報を得るよう構成されており；
各目標デバイスについて、前記距離基準情報は、その測定距離関係情報と前記割り当てノードについての想定距離関係情報との間の差を含み；
前記第一の決定手段がさらに、前記割り当てノードについて、前記目標デバイスの一つまたは複数から、その想定距離関係情報と測定距離関係情報との間の差が相対的に小さい一つの目標デバイスを、前記割り当てノードに対応する目標デバイスとして選択するよう構成されている、
装置。
【請求項１５】
請求項１４記載の装置であって、前記第一の決定手段が：
・前記割り当てノードについて、想定距離関係情報と測定距離関係情報との間の差が相対的に小さい所定数の複数の候補目標デバイスを決定するよう構成された候補デバイス決定手段と；
・各候補目標デバイスを第一の補助基準デバイスとして取り、前記少なくとも二つの基準デバイスおよび前記第一の補助基準デバイスに従って、一つまたは複数の補助基準ノードに対応する一つまたは複数の補助目標デバイスがあると仮定するよう構成された補助目標デバイス仮定手段と；
・前記一つまたは複数の補助基準ノードに対応する、候補目標デバイスと前記一つまたは複数の補助目標デバイスとの各組み合わせについて、各候補目標デバイスおよび前記少なくとも二つの基準デバイスおよび前記対応する一つまたは複数の補助目標デバイスの間の無線接続に基づいて、各候補目標デバイスの、前記少なくとも二つの基準デバイスおよび前記対応する一つまたは複数の補助目標デバイスに対する測定距離関係情報の測定を実行し、前記一つまたは複数の補助目標デバイスが前記一つまたは複数の補助基準ノードに対応すると想定して、該想定のもとに、各候補目標デバイスの、前記少なくとも二つの基準デバイスおよび対応する一つまたは複数の補助目標デバイスに対する、想定距離関係情報を得るよう構成された第二の取得手段とを有しており；
前記第一の決定手段がさらに：
すべての組み合わせから、前記候補目標デバイスの、前記少なくとも二つの基準デバイスおよび対応する一つまたは複数の補助目標デバイスに対する測定距離関係情報と想定距離関係情報との間の差が最も小さい組み合わせを判別し、その組み合わせにおける候補目標デバイスが前記割り当てノードにおける目標デバイスに対応すると判定するよう構成されている、
装置。
【請求項１６】
請求項１５記載の装置であって、前記補助割り当てデバイス仮定手段がさらに：
・前記候補目標デバイスの一つを第一の補助基準デバイスとして取り、近くの一つまたは複数の目標デバイスと少なくとも二つの基準デバイスおよび第一の補助基準デバイスとの間の無線接続に基づいて、前記一つまたは複数の目標デバイスの、前記少なくとも二つの基準デバイスおよび前記第一の補助基準デバイスに対する、測定距離関係情報を測定するよう構成された第三の取得手段と；
・各目標デバイスがそれぞれ前記補助基準ノードの一つに対応すると想定し、該想定のもとで、各目標デバイスの、前記少なくとも二つの基準デバイスおよび前記第一の補助基準デバイスに対する、想定距離関係情報を得るよう構成された第四の取得手段と；
・前記補助基準ノードについて、すべての目標デバイスのうちから、前記目標デバイスの、前記少なくとも二つの基準デバイスおよび前記第一の補助基準デバイスに対する、想定距離関係情報と測定距離関係情報との間の差が相対的に小さい一つまたは複数の目標デバイスを、前記補助ノードに対応する補助目標デバイスとして決定するよう構成されている第二の決定手段とを有する、
装置。
【請求項１７】
請求項１３記載の装置であって、前記トポロジカル・グラフがグリッド形であり、前記第一の取得手段が：
・前記目標デバイスすべてのうちの所定数の複数の目標デバイスによって構成されるすべての候補グループを列挙し、各候補グループについて、前記少なくとも二つの基準デバイスに対する、前記核候補グループの前記所定数の複数の目標デバイスの測定距離関係情報の数学的な組み合わせを決定するよう構成されており、前記距離基準情報はすべての候補グループの対応する数学的組み合わせを含み；
前記第一の決定手段が：
・すべての候補グループの対応する数学的組み合わせに基づいて、所定の規則に従って一つの目標候補グループを選択し、前記目標候補グループの所定数の複数の目標デバイスを、前記少なくとも二つの基準デバイスに隣接する所定数の複数の割り当てデバイスに対応する選択されたデバイスとして選択するよう構成された候補グループ決定手段と；
・前記少なくとも二つの基準デバイスの少なくとも一つに対する、前記所定数の複数の選択されたデバイスの測定距離関係情報に基づいて、前記所定数の複数の選択されたデバイスのそれぞれがどの割り当てノードに対応するかを決定するよう構成された第三の決定手段とを有する、
装置。
【請求項１８】
請求項１７記載の装置であって、前記少なくとも二つの基準デバイスは同じグリッド線上にあり、互いに隣接しており、各目標デバイスは前記少なくとも二つの基準デバイスの同じ側にあるおよび／または前記少なくとも二つの基準デバイスと同じグリッド線上にあり、前記所定数の複数の割り当てノードは各基準デバイスに同じ側で隣接しており、前記距離関係情報は対応するデバイス間での電波信号の受信信号強度指標RSSIおよび／または飛行時間を含み、前記数学的組み合わせは電波信号のRSSIおよび／または飛行時間の線形結合である、装置。
【請求項１９】
トポロジカル・グラフ中の各目標デバイスの位置を決定する装置であって、前記トポロジカル・グラフは複数のノードの位置情報を含み、当該装置は：
・前記トポロジカル・グラフを、所定の規則に従って、割り当てられるべきある数の部分トポロジー・ブロックに分割するよう構成されたブロック分割手段と；
・割り当てられるべき一つまたは複数の部分トポロジー・ブロックに隣接する基準ブロックを決定するよう構成された基準ブロック決定手段と；
・割り当てられるべき前記目標部分トポロジー・ブロックに隣接する前記基準ブロックの基準デバイスを、初期基準デバイスとして取り、初期割り当て方法を使って初期割り当てを実行し、前記目標部分トポロジー・ブロックの各ノードがそれぞれ対応する前記目標デバイスの存在を仮定するよう構成された初期割り当て手段と；
・前記初期基準デバイスとは異なる検証基準デバイスおよび／または前記初期割り当て方法とは異なる検証割り当て方法を使って検証割り当てを実行し、前記目標部分トポロジー・ブロックの各ノードがそれぞれ対応する前記目標デバイスの存在を仮定するよう構成された検証割り当て手段と；
・前記検証割り当ての仮定結果が前記初期割り当ての仮定結果と同一であれば、前記目標部分トポロジー・ブロックが割り当てられたと判断し、前記仮定結果が異なっていれば、前記目標部分トポロジー・ブロックが相変わらず割り当てられるべきであると判断するよう構成された判断手段とを有し、
前記基準ブロック決定手段はさらに、割り当てられるべき他の関連する部分トポロジー・ブロックすべてを割り当てるために、基準ブロックとして割り当てられた前記部分トポロジー・ブロックすべてを取るようさらに構成されている、
装置。
【請求項２０】
請求項１９記載の装置であって、
前記基準ブロック決定手段はさらに：
・第一の基準デバイスに基づいて、第一の割り当て方法を使って、前記基準ブロックの各ノードにそれぞれ基準デバイスの存在を仮定するよう構成された第三の割り当て手段と；
・前記第一の基準デバイスとは異なる第二の基準デバイスおよび／または前記第一の割り当て方法とは異なる第二の割り当て方法を使って、前記基準ブロック中の各ノードにそれぞれ対応する基準デバイスの存在を仮定するよう構成された第四の割り当て手段とを有しており；
前記基準ブロック決定手段はさらに、前記第二の基準デバイスおよび／または前記第二の割り当て方法に対応する仮定結果が前記第一の基準デバイスおよび前記第一の割り当て方法に対応する仮定結果と同一であれば、前記仮定結果に従って、前記基準ブロックの各ノードに対応する基準デバイスをそれぞれ決定するよう構成されている、
装置。
【請求項２１】
請求項１９または２０記載の装置であって、前記検証基準デバイスは、前記処理割り当て手段によって仮定される前記目標部分トポロジー・ブロック中の目標デバイスを含む、装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デバイスの自動割り当てに関し、特に無線技術に基づくデバイスの自動割り当てのための方法および装置に関する。
【背景技術】
【０００２】
今日、さまざまな建物や領域において、照明、デコレーションまたは表示機能といった複数の機能を提供するよう、非常に多数の照明デバイスによって構成されるアレイのようなデバイス・アレイが大規模に展開されている。建物管理システムのようなシステムは該照明デバイス・アレイを遠隔モニタリングおよび管理し、各照明デバイスのオン、オフを制御し、その照明モードを切り換えるなどする。照明、デコレーションまたは表示のような複数の機能に対して改善するために、異なるノード位置にあるすべての照明位置に異なる命令を送り、所望の照明、デコレーションおよび表示機能を実現するよう、前記システムは各照明デバイスの位置、たとえば各デバイスの一意的識別情報（Unique  Identification；略UID）とデザイン・トポロジカル・グラフ上でのその設置ノード位置との間の対応関係、を正確に取得することができる必要がある。システムによって取得される各デバイスの位置がその実際の物理的位置でない場合、これは照明アレイが適正に機能しないことを引き起こす。デバイス・アレイの通常動作の前に実行されるデバイス・アレイの割り当て（assigning）は、この問題を解決して、各デバイスがトポロジカル・グラフにおける一つの既知のノードに対応するようにする目的のためである。
【０００３】
デバイス・アレイ中のデバイスの数の多さのため、手動の割り当てを実行することはきわめて難しく、そうする場合、誤りが生じやすいことがある。したがって、上述の割り当て作業は空中の電波信号の伝搬特性を利用することによって実行できる；たとえば、自動割り当てはデバイス間の距離に関する取得された情報に基づいて三角測量技術によって実行できる。距離に関する情報は、電波信号の受信信号強度指標（Received  Signal  Strength  Indication；略RSSI）または飛行時間（time  of  flight）を通じて取得できる。RSSIまたは飛行時間を測定することによって、割り当てを実行するための二つのデバイス間の距離が間接的に取得できる。しかしながら、従来技術ではいくつかの問題に遭遇する。第一の問題は、デバイスの割り当て精度である。電波信号の伝送は多くの因子によって影響されるので、同じ距離にある二つのデバイスの間の伝送パラメータは、異なるアンテナ利得または異なる干渉の場合、異なるマルチパス環境において大きな逸脱を引き起こしうる。そのためその伝送パラメータによって決定される距離が大きな誤差を含むことになり、割り当て精度が影響を受ける。第二の問題は、二次元以上の空間については、あらゆる二デバイス間の距離についての情報に基づいてトポロジカル・グラフ全体における全デバイスの位置を決定することは、困難な、非決定的多項式（nondeterministic  polynomial；略NP）問題であることがわかっている。計算量は領域内のデバイスの数とともに指数関数的に増大する。第三の問題は、デバイス・アレイのデバイス数が非常に多いとき、トポロジカル・グラフ全体における割り当ての誤り確率が増大し、誤った割り当てがさらなる割り当て誤りにつながる誤り分散（error  dispersion）を引き起こす。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上述した従来技術の欠点を解消するために、デバイス割り当てプロセスの精度を高めること、割り当ての計算量を減らすこと、およびトポロジカル・グラフ全体の割り当て成功率を改善することが解決する必要のある当技術分野におけるいくつかの技術的課題である。いうところのデバイスは上述の照明デバイス（illumination  device）を含み、また調整デバイス（adjusting  device）、オーディオ再生デバイス（audio  regeneration  device）などをも含む。
【課題を解決するための手段】
【０００５】
上述した一つまたは複数の懸案によりよく対処するため、本発明のある側面のある実施形態によれば、トポロジカル・グラフ中で各目標デバイスの位置を決定する方法であって：ａ．少なくとも二つの基準デバイスと各目標デバイスとの間の無線接続を確立する段階であって、前記基準デバイスのそれぞれのトポロジカル・グラフにおける位置は既知であり、前記トポロジカル・グラフは複数のノードの位置情報を含む、段階と；ｂ．前記無線接続に基づいて、各目標デバイスの、前記少なくとも二つの基準デバイスに対する、測定された距離に関する情報を測定し、距離基準情報を取得する段階と；ｃ．前記距離基準情報に基づいて、各目標デバイスが前記諸ノードのうちのどの位置に対応するかを決定する段階とを含む、方法が提供される。
【０００６】
ある側面のある好ましい実施形態によれば、前記段階ｂがさらに：各目標デバイスが前記トポロジカル・グラフ中のある割り当てノードの位置にあるとの想定で、各目標デバイスの、前記少なくとも二つの基準デバイスに対する、想定距離関係情報を得る段階を含み；各目標デバイスに対応して、前記距離基準情報は、測定距離関係情報と前記割り当てノードについての想定距離関係情報との間の差を含み；前記段階ｃがさらに：前記割り当てノードについて、一つまたは複数の目標デバイスから、想定距離関係情報と測定距離関係情報との間の差が相対的により小さい一つの目標デバイスを、前記割り当てノードに対応する目標デバイスとして選択する段階を含む。
【０００７】
別の側面のある好ましい実施形態によれば、前記トポロジカル・グラフ中での各ノードの位置がグリッド形であり、前記段階ｂが：前記目標デバイスのうちの所定数の複数の目標デバイスによって構成されるすべての候補グループを列挙し、所定の組み合わせ規則に従って、前記少なくとも二つの基準デバイスに対する、各候補グループの前記所定数の複数の目標デバイスの測定距離関係情報の数学的な組み合わせを決定する段階を含み、前記距離基準情報はすべての候補グループの対応する数学的組み合わせを含み；前記段階ｃが：ｃ１．すべての候補グループの対応する数学的組み合わせに基づいて、所定の規則に従って一つの目標候補グループを選択し、前記目標候補グループの所定数の複数の目標デバイスを、前記少なくとも二つの基準デバイスに近隣の所定数の複数の割り当てノードに対応する選択されたデバイスとして選択する段階と；ｃ２．前記少なくとも二つの基準デバイスの少なくとも一つに対する、前記所定数の複数の選択されたデバイスの測定距離関係情報に基づいて、前記所定数の複数の選択されたデバイスのそれぞれがどの割り当てノードに対応するかを決定する段階とを含む。
【０００８】
本発明の別の側面のある実施形態によれば、トポロジカル・グラフ中の各目標デバイスの位置を決定する方法であって、前記トポロジカル・グラフは複数のノードの位置情報を含み、当該方法は：Ａ．前記トポロジカル・グラフを、割り当てられるべきある数の部分トポロジー・ブロックに分割し、割り当てられるべき前記部分トポロジー・ブロックの一つまたは複数に隣接する基準ブロックを決定する段階と；Ｂ．割り当てられるべき前記目標部分トポロジー・ブロックに隣接する前記基準ブロックの基準デバイスを、初期基準デバイスとして取り、初期割り当て方法を使って初期割り当てを実行し、前記目標部分トポロジー・ブロックの各ノードが対応する前記目標デバイスの存在を仮定する段階と；Ｃ．前記初期基準デバイスとは異なる検証基準デバイスおよび／または前記初期割り当て方法とは異なる検証割り当て方法を使って検証割り当てを実行し、前記目標部分トポロジー・ブロックの各ノードがそれぞれ対応する前記目標デバイスの存在を仮定する段階と；Ｄ．前記検証割り当ての仮定結果が前記初期割り当ての仮定結果と同一であれば、前記目標部分トポロジー・ブロックが割り当てられたと判断し、そうでなければ前記目標部分トポロジー・ブロックが相変わらず割り当てられるべきであると判断する段階と；Ｅ．割り当てられるべき他のすべての部分トポロジー・ブロックすべてを割り当てるよう、基準ブロックとして割り当てられた前記部分トポロジー・ブロックすべてを取り、前記段階ＢないしＤを繰り返す段階とを含む、方法が提供される。
【０００９】
本発明のある側面に関連する方法または装置によれば、実際の測定を通じて得られた測定距離関係情報を、デバイスが割り当てノードに対応するという想定のもとでの想定距離関係情報と比較することにより、想定された情報と測定された情報との間の最小の差をもつ目標デバイスが割り当てノードに対応するものとして選択され、割り当ては、強い故障耐性能力をもち、デバイスの割り当て精度が実質的に改善される。本発明のもう一つの側面に関係する方法または装置によれば、複数の基準デバイスに基づいて、複数の割り当てノードに対応する複数の目標デバイスを、大きな安全マージンをもって決定することによって、割り当ての計算量が削減され、デバイスの割り当て精度が改善される。もう一つの側面に関係する方法または装置によれば、トポロジカル・グラフを部分トポロジー・ブロックに分割し、各部分トポロジー・ブロックをそれぞれ割り当ておよび検証することによって、部分トポロジー・ブロックの割り当て精度が向上し、部分トポロジー・ブロックにおけるデバイス割り当て誤りによって引き起こされる誤り分散が回避され、それによりトポロジカル・グラフの割り当て成功率が向上する。
【００１０】
本発明のこれらおよびその他の特徴は以下の実施形態の部分において詳細に例解される。
【図面の簡単な説明】
【００１１】
本発明の特長、目的および利点は、付属の図面を参照しての限定しない例示的な実施形態の以下の詳細な記述によってより容易に理解されるであろう。図面において、同じまたは同様の参照符号は同じまたは同様の手段を表す。
【図１】本発明のある実施形態に基づく照明領域のトポロジカル・グラフを概略的に示す図である。
【図２】照明領域中の、各ノードおよび設置されている照明デバイスにおける主要な構成要素のブロック図である。
【図３】インターフェースを介した、自動割り当てシステムと無線ネットワークとの間の接続を概略的に示す図である。
【図４】本発明のある実施形態に基づく、自動割り当てシステムを通じて、トポロジカル・グラフ中のノードが対応する目標デバイスを決定する方法のフローチャートである。
【図５】本発明に基づく、コンピュータの形の装置の実現を概略的に示す図である。
【図６】本発明のもう一つの実施形態に基づく、グリッド形のトポロジカル・グラフを概略的に示す図である。
【図７】本発明のもう一つの実施形態に基づく、もう一つのグリッド形のトポロジカル・グラフを概略的に示す図である。
【図８】本発明のもう一つの実施形態に基づく、自動割り当てシステムを通じて、グリッド形のトポロジカル・グラフ中のノードが対応する目標デバイスを決定する方法のフローチャートである。
【図９】本発明のもう一つの実施形態に基づく、自動割り当てシステムを通じて、グリッド形のトポロジカル・グラフ中のすべてのノードが対応する目標デバイスを決定するプロセスを示す図である。
【図１０】トポロジカル・グラフの割り当て成功率とトポロジカル・グラフのノード数との間の関係のシミュレーションを概略的に示す図である。
【図１１】本発明のもう一つの実施形態に基づき、自動割り当てシステムがトポロジカル・グラフをいくつかの部分トポロジー・ブロックに分割することを概略的に示す図である。
【図１２】本発明のもう一つの実施形態に基づき、部分トポロジー・ブロックに基づいて自動割り当てシステムを通じて、トポロジカル・グラフ中のノードが対応する目標デバイスを決定する方法のフローチャートである。
【発明を実施するための形態】
【００１２】
以下では、本発明の実施形態が、図１ないし図１２を参照して、システム方法に関して明快にされる。本発明に基づく装置およびその動作モードも以下の実施形態において記述される。
【実施例１】
【００１３】
図１は、無線ネットワークに基づく照明領域を概略的に示している。ここで、この照明領域のトポロジカル・グラフが示されている。すなわち、領域中の各照明ノードの位置(1,1)、(1,2)、……、(4,4)はみな既知である。照明領域のノードに設置された照明デバイス１、２、……、１６があるが、どの照明デバイスがどのノードに対応するかは未知である。図２に示されるように、各ノードは照明要素２１０、ZigBee  RFモジュールのような無線通信モジュール２２０および電源２３０を有する。無線通信モジュール２２０は、ZigBee  RFプロトコルまたは他のプロトコルに基づいて、他のノードの無線通信モジュールと無線通信を実行し、無線ネットワーク１００を確立することができる。前記デバイスの任意のものによって送られる信号は送信元デバイスの一意的な識別情報を担持し；受信デバイスは、その識別情報に基づいて、電波信号の送信元デバイスを決定し、当該デバイスと送信元デバイスとの間の、電波信号のRSSIまたは飛行時間などのような測定される距離に関係した情報を測定し、測定された距離に関係する情報を他のノードまたは無線ネットワーク１００外の自動割り当てシステム３００に提供することができる。電源２３０はトランスのような要素を有することができ、120V  60Hzまたは230V  50Hzコンセント電源のような幹線電源に接続されることができ、それによりノードに設置された照明要素および無線通信モジュールの動作のために必要とされる電力を提供できる。照明領域は建物または戸外環境にあることができる。照明領域における自動割り当て（automatic  assigning）の目的は、照明デバイス１、２、……１６のうちのどれにノード(1,1)、(1,2)、……、(4,4)がそれぞれ対応するかを決定することである。この実施形態は、本発明を例解するための例として照明デバイスを使うが、本発明が他の形のトポロジーにおける温度調整デバイス、オーディオ再生デバイスなどといった他のデバイスにも適用可能であることは理解されるであろう。
【００１４】
図３に示されるように、自動割り当てシステム３００は無線ネットワーク１００と、無線またはケーブル・インターフェース３１０を介して接続されることができる；たとえば、自動割り当てシステム３００は一つまたは複数の照明デバイスと接続される。これらの照明デバイスどうしの間のRSSIまたは飛行時間のような距離に関係する情報を無線ネットワーク１００において得るためである。
【００１５】
この実施形態では、すべての目標照明デバイスがそれぞれ位置しているノードを決定するために、まず、少なくとも二つの照明デバイスが位置しているノードが決定されるべきであり、次いで、それら二つの照明デバイスを基準デバイスとして取ることによって、他のデバイスが位置しているノードが決定される。図１に示される正方形のように、この実施形態は、本発明を例解するために三つの基準デバイス１、２および５を例として取り、それらはそれぞれノード(1,1)、(1,2)および(2,1)にある。本発明は二つの基準デバイスまたは三より多くの基準デバイスの場合にも適用可能であることは理解されるであろう。基準デバイスの位置決定は、それらのデバイスが設置されるときに既存の手動入力を使うことによって、あるいは他の方法によって実行されることができる。基準デバイスが決定されたのち、この実施形態はまず、暗い色で表されているノード(2,2)にどの照明デバイスが設置されているかを決定する。この実施形態では、基準デバイスは照明デバイスとして再利用される；基準デバイスは割り当てのために特化して使用されるデバイスであることもできることは理解されるであろう。
【００１６】
図４に示されるように、ステップS10において、トポロジカル・グラフ内の照明デバイス（基準デバイスを含む）が、それらどうしの間で無線ネットワーク１００を確立し、三つの基準デバイスのそれぞれと各照明デバイスとの間の無線接続を確立すべきである。本発明において言及される「無線接続（wireless  connection）」は接続指向の（connection-oriented）または無接続の（connectionless）ポイントツーポイント通信リンクがあらゆる二デバイスの間に確立されることを要求するのではなく、デバイスが、受信信号に基づいてRSSIおよび／または飛行時間のような必要な情報を得るよう他のデバイスによって送られた電波信号を検出できることを言っていることを注意しておくべきである。たとえば、これはネットワーク探索プロセスを通じて無線接続を確立することによってなされることができる。これは、照明デバイスおよびその無線通信デバイスのいずれかが立ち上がるときになされる。たとえば、各照明デバイスの無線通信モジュールがあるブロードキャスト・チャネルに調整され、当該デバイスの型を含む告示メッセージをブロードキャストし、他のすべてのデバイスに返信し、ソースを同定することを要求する。各照明デバイスが告示メッセージを他の諸デバイスから受信したのち、当該デバイスと送信元デバイスとの間の、電波信号のRSSIまたは飛行時間のような距離に関係した情報が決定されることができる。さらに、デバイスは他のデバイスからの告示メッセージがあるかどうかを、能動的に告示メッセージを送ることなく、モニタリングし、受信された告示メッセージから必要な情報を取得することができる。すなわち、「無線接続」は一方向的であることもできるのである。この実施形態では、三つの基準デバイス１、２および５のそれぞれは、自分と近隣の目標照明デバイスそれぞれとの間の実際の
【００１７】
【数１】
2012506192.tif 000003
を取得し、該実際のRSSIrefi,devicejを自動割り当てシステム３００に提供する。ここで、refi、i∈{1,2,5}は各基準デバイス（reference  device）を表し、devicej、j∈{3,4,6,…,16}は各目標照明デバイスを表す。目標照明デバイスがそれらの基準デバイスから遠い場合、該目標照明デバイスが送る信号は基準デバイスによって検出されないことがありうる。よって、該目標照明デバイスと基準デバイスとの間のRSSIは無視されるまたは無限小と考えられることができる。商業的なRFチップおよびモジュールの大半は基準デバイスのためにRSSIを取得する機能をサポートでき、その具体的な使用は本発明の焦点ではなく、よってこれ以上説明はしない。
【００１８】
電波信号の伝搬減衰は一般に次の公式を満たすことが理解されるであろう：
RSSI(dB)＝10lgC−λ10lgd        (1)
ここで、Cはアンテナ利得および周波数などに関係する係数、λは経路損失因子、dは送信デバイスと受信デバイスとの間の距離である。見て取れるように、RSSIの変化傾向は距離の変化傾向とは反対である。実際的な環境では、RSSIは他の因子によって影響されうる。したがって、若干数のノードにおける若干数の照明デバイスを決定するために、RSSI測定エラーによって引き起こされる目標デバイスの抜けを避けるために、さらなる目標照明デバイスの測定結果を考慮に入れることができる。この実施形態では、割り当てノード(2,2)に設置された照明デバイスを決定するために、無線ネットワーク１００は、三つの基準デバイス１、２および５に対して相対的に大きなRSSIをもつ６個の照明デバイスの測定されたRSSI（これは目標デバイスから基準デバイスへの上りRSSIまたは基準デバイスから目標デバイスへの下りRSSIまたは上りおよび下りRSSIの平均であることができる）を測定し、取得し、測定されたRSSIを自動割り当てシステム３００に提供することができ、それにより計算を著しく軽減することができる。無線ネットワーク１００はまた、１３個の目標デバイスすべてから基準デバイスへの測定されたRSSIを自動割り当てシステムに提供することもできる。
【００１９】
次いで、ステップS11において、自動割り当てシステム３００は、無線ネットワーク１００の各目標デバイスと三つの基準デバイス１、２および５のそれぞれとの間の測定されたRSSIを受信する。システム３００はまた、各目標照明デバイスが割り当てノード(2,2)に位置されていたことを想定した。各目標照明デバイスの、基準位置にある三つの基準デバイス１、２および５に対する、相対的な想定されたRSSIは、それぞれ、上記の想定された条件の下で計算される。ここで、相対想定RSSIは
【００２０】
【数２】
2012506192.tif 000004
によって表される。refi、i∈{1,2,5}は各基準デバイスを表し、posは割り当てノード(2,2)を表す。
【００２１】
自動割り当てシステム３００は、目標デバイスと基準デバイス１、２および５との間のRSSIを記述するためのノルム（norm）として相対RSSIベクトルを用いる。割り当てノード(2,2)について、想定RSSIベクトルは次の公式に対応するものとして定義される：
【００２２】
【数３】
2012506192.tif 000005
公式(1)から知ることができるように、ベクトル要素RSSIref2,pos−RSSIref1,posは割り当てノードと基準デバイス２の間の距離と割り当てノードと基準デバイス１の間の距離との間の比および経路損失因子λだけに依存し、アンテナ利得などを含むパラメータCは打ち消されることができる。割り当てノードおよび各基準デバイスのノード位置はトポロジカル・グラフにおいて既知であるので、上記距離の比は容易に得ることができ、経路損失因子λも実際的な環境における簡単な測定によって得ることができる。よって、相対想定RSSIは計算を通じて得ることができる。
【００２３】
相対測定RSSIは次の公式に対応するものとして定義される：
【００２４】
【数４】
2012506192.tif 000006
RSSIref1,devicej、RSSIref2,devicejおよびRSSIref5,devicejは、それぞれ基準デバイス１、２および５のそれぞれに対する各目標デバイスの測定されたRSSIであり、自動割り当てシステム３００はこれらのデータを取得済みであり、よって相対想定RSSIも計算を通じて得ることができることは理解されるであろう。
【００２５】
次いで、自動割り当てシステム３００は、各目標デバイスの相対測定RSSIベクトルと割り当てノード(2,2)に関するその相対想定RSSIベクトルとの間の差を計算する。ここで、この差が各目標デバイスの距離基準情報として使用される。具体的には、ベクトルの差はベクトル差のモードであることができ、次の公式によっても計算されることもできる：
【００２６】
【数５】
2012506192.tif 000007
ここで、V_measured(devicej)nおよびV_assumednはそれぞれ、相対測定RSSIベクトルのn番目の要素と相対想定RSSIベクトルのn番目の要素を表す。
【００２７】
その後、ステップS12において、割り当てノード(2,2)について、自動割り当てシステム３００は、各目標デバイスの相対測定RSSIベクトルと割り当てノード(2,2)に関するその相対想定RSSIの間の計算された差を比較して、割り当てノード(2,2)に対応する目標照明デバイスを決定する。これは、ビタビ復号アルゴリズムのような最尤シーケンス検出と似ている。上述した公式(4)は例として使われているだけであることは理解されるであろう。すなわち、当業者はこの公式を重みをかけられた係数を設定することなどによって修正して実際のネットワーク環境に適応させることができる。
【００２８】
一つの場合では、計算を軽減するため、自動割り当てシステム３００は想定された値と測定された値との間の最小の差をもつ目標照明デバイスを、割り当てノード(2,2)における照明デバイスとして選択する。
【００２９】
上記において、本発明は、相対RSSIを例として取ることによって例解されている。この場合、相対想定RSSIベクトルは割り当てノードと各基準位置との間の距離の比によって決定できる。相対RSSIを使っているのは、トポロジカル・グラフにおける無線通信環境の測定を簡単化し、同時に照明デバイスの無線通信モジュールのアンテナ利得差をなくす目的のためであることは理解されるであろう。本実施形態の教示に基づき、当業者は、本発明が割り当てノードと各基準位置との間の距離の絶対想定RSSIとその絶対測定RSSIとの間の比較に基づくことができることがわかるであろう。公式(1)によれば、システム３００はアンテナ利得を含む各照明デバイスのパラメータCを取得し、それにより、照明デバイスが割り当てノードにあるという想定のもとに、照明デバイスと各基準デバイスとの間の絶対想定RSSIを決定し、絶対想定RSSIを絶対測定RSSIと比較し、伝搬特性の変化によって引き起こされる測定歪みが最大限軽減されることができるよう、想定された値と測定された値との間の最小の差をもつ目標デバイスをその割り当てノード(2,2)にある照明デバイスとして選択する。
【００３０】
もう一つの場合では、選択の正しさを保証するため、ステップS120において、自動割り当てシステム３００は、想定された値と測定された値との間の相対的に小さな差をもつ複数の目標デバイスを割り当てノード(2,2)に対応する候補照明デバイスとして取り、どの照明デバイスが割り当てノード(2,2)に位置されている可能性が最も高いかを判別すべく、各候補照明デバイスを検証する。
【００３１】
具体的には、ステップS121において、自動割り当てシステム３００は前記複数の候補照明デバイスを、基準デバイス１、２および５と一緒に使われる第一の補助基準デバイスとして取り、補助目標デバイスが近くの複数の補助基準ノードに対応すると仮定する。記述を容易にするため、本発明において、kcanは複数の候補照明デバイスの数を表し、krefは補助基準ノードの数を表す。自動割り当てシステム３００は候補照明デバイスの好適な数kcanおよび好適な補助基準ノードおよびその数krefを、トポロジーのスケールおよびシステムの計算能力に応じて選択できる。図１に示されるように、この実施形態では、自動割り当てシステム３００は基準デバイス１、２、５および割り当てノード(2,2)に最も近い５つのノード、つまり(1,3)、(2,3)、(3,1)、(3,2)および(3,3)を、図１で左下がりの斜線で示される補助基準ノードとして選択する。次いで、kcan個の第一の補助基準デバイスおよび基準デバイス１、２および５のそれぞれに基づいて、自動割り当てシステム３００は所定の割り当て方法用いて、５つの補助基準ノード(1,3)、(2,3)、(3,1)、(3,2)および(3,3)における（？）補助目標デバイスの存在を想定する。システム３００は、基準デバイスに基づく既存の割り当て方法を用いることができ、割り当てノード(2,2)における設置されている照明目標デバイスを決定するために使用される、先のステップS10ないしS12と同様の最尤法を使うこともできる。具体的には、ステップS1210において、システム３００は各目標照明デバイスから各基準デバイスおよび各第一の補助基準デバイスへの測定されたRSSIを取得する。ステップS1211では、各目標デバイスが各目標基準ノードに位置されていると想定され、この想定のもとで、各目標デバイスと各基準デバイスおよび各第一の補助基準デバイスとの間の想定RSSIが計算される。最後に、ステップS1212において、測定されたRSSIと想定されたRSSIとの比較に基づいて、目標デバイスは補助基準ノードにおいてより小さな差をもつと仮定される。先のステップS1210およびステップS1211の順序は決まっていないことは理解されるであろう。同様に、各補助基準ノードについて一つまたは複数の補助目標デバイスがあると仮定することもできる。たとえば、各補助基準ノードについてkcan個の補助目標デバイスがあると仮定される場合、kcan個の候補照明デバイスについて、合計kcan6通りの候補照明デバイスおよび補助目標デバイスの組み合わせがある。これは、これらの組み合わせが１個の割り当てノードおよび５個の補助基準位置に対応し、各位置についてkcanの可能なデバイスがあることを意味する。
【００３２】
次いで、割り当てノード(2,2)を決定するための上述したステップS10ないしS12と同様の方法を使うことによって、ステップS122では、自動割り当てシステム３００は基準デバイス１、２および５ならびに５個の補助基準ノード(1,3)、(2,3)、(3,1)、(3,2)、(3,3)の位置を基準位置として取る。候補照明デバイスおよび補助目標デバイスのkcan6通りの組み合わせについて、自動割り当てシステム３００は、各組み合わせについて、基準デバイス１、２、５に対する対応する候補照明デバイスおよび対応する補助目標デバイスの測定されたRSSIを取得し、kcan6通りの組み合わせに対応する合計kcan6個の測定されたRSSIが得られるはずである。kcan6通りの候補照明デバイスおよび補助目標デバイスの組み合わせについて、自動割り当てシステム３００はまた、基準デバイス１、２、５に対する各候補照明デバイスおよび対応する補助目標デバイスの想定されたRSSIを、各候補照明デバイスが割り当てノード(2,2)のところに位置しているという想定のもとに、取得し、kcan6通りの組み合わせに対応する合計kcan6個の想定されたRSSIが得られるはずである。想定されるRSSIは相対RSSIまたは絶対RSSIであることができる。
【００３３】
最後に、ステップS123において、自動割り当てシステム３００は、kcan6通りの組み合わせのうちで、候補目標デバイスの測定されたRSSIと対応する想定されたRSSIとの間の最小の差をもつ組み合わせを決定し、割り当てノード(2,2)にあるこの組み合わせの候補目標デバイスをこのノードにある目標デバイスとして選択する。具体的な比較方法は、相対RSSIまたは絶対RSSIに基づくことができ、これ以上説明はしない。検証が実行されない上述した方法と比べ、本方法は（？）複数の候補目標デバイスの存在を仮定し、最尤法のような方法に基づいてその確からしさの比較による検証を実行し、割り当てノード(2,2)のところに位置している可能性が最も高い照明デバイスを決定する。これにより割り当ての成功率が高められる。
【００３４】
好ましくは、割り当てノードに対応する照明デバイスが決定されたのち、その照明デバイスを、基準デバイス１、２および５と一緒に基準デバイスとして取ることができる。システム３００は上記のステップS10ないしS12を繰り返し、他の割り当てノードに照明デバイスが設置されているかどうかを判別し、トポロジカル・グラフにおけるすべての割り当てノードに対応するすべての目標デバイスが決定されるまで続け、次いで、トポロジカル・グラフの割り当てプロセスが完了する。割り当てノードの割り当てプロセスにおいて、割り当てがより多くの基準デバイスに基づくほど、割り当ての精度は高いはずである。自動割り当てシステムは、トポロジカル・グラフの実際的なスケールおよびシステムの計算能力に従って好適な位置にある基準ノードを選択すべきである。これは、割り当ての精度を保証するばかりでなく、割り当てに関わる計算負荷を実質的に軽減しもする。
【００３５】
上記では、本発明はRSSIを例にとって記述されているが、本発明が他の距離関係情報、たとえば照明デバイスが割り当てノードのところに位置しているという想定のもとでの実際に測定された飛行時間と想定される飛行時間の間の差の比較のために使われることもできることは理解しておくべきである。その際、システムはその差に基づいて、各割り当てノードに設置された照明デバイスを判別する。さらに、RSSIを飛行時間と一緒に用いることもできる。本発明の教示に基づいて、当業者は、他の距離関係情報の想定された値と測定された値の差の比較に基づく、本発明に基づく他の方法を考案できることは明らかである。そうした方法も本発明の付属の請求項の範囲内であり、よって明細書ではこれ以上の詳細を与えることはしない。
【００３６】
上述した方法と同様に、本発明のある側面では、自動割り当てシステム３００は各ステップの機能を充足するための対応する手段を有することができる。具体的には、自動割り当てシステム３００は無線ネットワーク１００と通信するよう構成された受信機を有する。すなわち、該受信機は無線またはケーブル・インターフェースを介して無線ネットワーク１００中の一つまたは複数のデバイスと通信し、諸デバイスのうちからRSSIのような測定された距離に関係する情報を得ることができる。本システムは、ステップS11を充足するよう構成された受信機および第一の取得手段と、ステップS120を充足するよう構成された候補照明決定手段と、ステップS121を充足するよう構成された（？）手段の存在を想定する補助目標デバイスと、ステップS122を充足するよう構成された第二の取得デバイスと、ステップS123を充足するよう構成された第一の決定手段とを有することができる。好ましくは、（？）手段の存在を想定する補助目標デバイスはまた、ステップS1210を充足するよう構成された第三の取得手段と、ステップS1211を充足するよう構成された第四の取得手段と、ステップS1212を充足するよう構成された第二の決定手段とを有することができる。図５に示されるように、第一の取得手段および第一の決定手段ならびにそのサブ手段は、コンピュータ内に統合され、対応する機能を充足するようプログラムされるCPUの形で実現されることができる。機能プログラムはROMまたはRAMのようなメモリからCPUによって読まれることができ、割り当て結果は、割り当てオペレーターによる閲覧のために、モニタ上に表示されることができる。受信機は第一の取得手段および第一の決定手段とシリアル・インターフェースまたはイーサネット（登録商標）・インターフェースを介して通信できる。自動割り当てシステム３００の構成は本実施形態に限定されるものではなく、上記の詳細な説明に基づいて、当業者は対応する手段および関連する動作プロセスを設計でき、それらも本発明の付属の請求項の範囲内であることは理解されるであろう。したがって、明細書ではさらなる詳細を与えることはしない。
【００３７】
上記の実施形態に基づく本発明の側面が、図１に示される二次元のグリッド形のトポロジカル・グラフに制限されるものではなく、三次元トポロジカル・グラフのような任意の形および任意の次元について適用可能であることは理解できる。これらも本発明の付属の請求項の範囲内であり、明細書ではこれ以上の詳細を与えることはしない。
【００３８】
上記では、本発明のある側面に基づき、方法および装置が詳細に例解されてきた。すなわち、自動割り当てシステムが、ある割り当てノードに関して、各目標デバイスと諸基準デバイスとの間の測定された距離に関係する情報を、各目標デバイスと諸基準デバイスとの間の想定される距離に関係する情報と比較し、最初の差をもつ目標デバイスを目標デバイスとして選択する。下記では、本発明のもう一つの側面に基づく割り当て方法を例解する。
【実施例２】
【００３９】
本発明のもう一つの側面に基づく実施形態について記述する前に、割り当ての安全マージンについての関連知識をまず導入しておく。図６に示されるように、ノードが正方形のグリッド形に分散されているトポロジカル・グラフにおいて、基準デバイス１および２はそれぞれ基準ノード(1,1)および(1,2)に置かれ；他の未知の目標照明デバイスは他のノードに置かれ、各照明デバイスの無線通信モジュールの構成は同一である（たとえば、アンテナ利得および送信電力が同一）。ノード(1,1)に最も近い割り当てノード(2,1)が割り当てられるとき、ノード(2,1)とノード(1,1)との間の距離が、ノード(1,1)と全ノードのそれぞれ（基準ノード(1,2)を除く）との間の距離のうち最小の距離なので、割り当ては次の原理に基づくことができる：全目標デバイスのうちで、自分と基準デバイス１との間の最大のRSSIをもつ照明デバイスが割り当てノード(2,1)における照明デバイスである。一方、ノード(2,2)における目標照明デバイスは位置(1,1)に二番目に近いので、この目標照明デバイスは、割り当てノードのところにある照明デバイスであると間違われる可能性が最も高い。理論的には、ノード(2,2)にある目標照明デバイスと基準デバイス１との間のRSSIは10lgC−10λlg(√2)dである。ここで、Cはアンテナ利得、周波数などに関係する定数、λは経路損失因子、dは正方形グリッドの辺の長さであり、一方、割り当てノード(2,1)における目標照明デバイスと基準デバイス１の間のRSSIは10lgC−10λlgdである。前者は後者よりもm＝10λlg(√2)dBだけ小さく、mの値はこの割り当て方法の安全マージンである。  (2,2)にある目標照明デバイスと基準デバイス１との間の実際に測定されるRSSIが、実際的な環境の影響のために、割り当て装置(2,1)にある目標照明デバイスと基準デバイス１との間のRSSI以上である場合、割り当てシステムが割り当てノード(2,1)に対応する目標デバイスを判断するのに困難が生じ、ノード(2,2)にある照明デバイスをノード(2,1)にあるデバイスとして誤って決定することさえありうる。したがって、誤った割り当てを避けるために、安全マージンは一般にできるだけ大きいべきである。
【００４０】
二つの基準デバイス１および２に基づいて最も近い二つの割り当てノード(2,1)および(2,2)にある二つの目標デバイスを同時に割り当てるとき、割り当ては、たとえば、次の原理に基づく：５つのRSSIの和、すなわち前記二つの割り当てノードにおける二つの目標デバイスの間のRSSIで一つ、前記二つの目標デバイスのそれぞれと前記二つの基準デバイスのそれぞれとの間のRSSIで他の４個、の和が最大。すべての目標照明デバイスのうちの二つの目標照明デバイスのあらゆる組み合わせを列挙して計算することにより、システムは、最も大きな組み合わせをもつ二つの目標デバイスを、割り当てノード(2,1)および(2,2)にあるものとして選択する。一方、照明位置(2,2)および(1,3)にある二つの照明デバイスは、基準デバイスに二番目に近い。同様に、計算により、５つのRSSIの和、すなわち前記二つの照明位置(2,2)および(1,3)における二つの照明デバイスの間のRSSIで一つ、前記二つの照明デバイスのそれぞれと前記二つの基準デバイスのそれぞれとの間のRSSIで他の４個、の和が、割り当てノード(2,1)および(2,2)における二つの照明デバイスに対応する５つのRSSIの和よりもm′＝10λlg2  dBだけ小さいことを得ることができる。見て取れるように、本割り当て方法の安全マージンは、一つの基準デバイスが一つの目標照明デバイスを割り当てるために使われていた上述の方法の割り当てマージンm＝10λlg√2  dBに比べて改善されている。
【００４１】
本発明のもう一つの側面によれば、この安全マージンが改善される。それは、各目標デバイスと諸基準デバイスとの間の測定された距離に関係する情報をそれぞれ測定したのち、すべての目標デバイスのうち所定数の複数の目標デバイスによって構成されるすべての候補グループを列挙し、すべての前記候補グループについて、所定の組み合わせ規則に従って、前記少なくとも二つの基準デバイスに対して、前記所定数の複数の目標デバイスの測定された距離に関係する情報の数学的組み合わせを決定し、所定の規則に従って、一つの目標候補グループを選択し、前記目標候補グループの複数の目標デバイスのうちある所定数を、基準デバイスに隣接する所定数の複数の割り当てノードに対応する選択されたデバイスとして選択し、次いで、各選択されたデバイスと各基準デイバスとの間の測定された距離に関係する情報に基づいて、各選択されたデバイスに対応する割り当てノードを決定することによる。
【００４２】
以下では、本発明のこの側面について実施形態を通じて例解する。図７に示されるように、トポロジカル・グラフにおいて、ノード位置(1,1)、(1,2)および(1,3)は基準位置である。基準デバイス１、２および３はこれらの位置にあることがわかっている；他のノードに設定されている照明デバイスは、割り当てられるべき未知の目標照明デバイスである。三つの基準デバイスは互いに同じグリッド上にあり、互いに隣接している。各目標デバイスは三つの基準デバイスの同じ側に、あるいは三つの基準デバイスと同じグリッド線上に位置されている。たとえば、図における基準デバイスは、トポロジカル・グラフ全体の左上隅に位置されており、目標照明デバイスは基準デバイスの右側および下側に位置されている。割り当ての順序も上記の条件、すなわち上から下へ、左から右へを満たす。それにより、目標照明デバイスが割り当てられたデバイスの右側または下側に位置されていることが保証される。本実施形態はまず、それぞれ同じ側で三つの基準位置に隣接する三つの割り当てノード(2,1)、(2,2)および(2,3)を割り当てる。
【００４３】
図８に示されるように、まず、ステップS10'において、トポロジカル・グラフにおける各照明デバイスおよび諸基準デバイスが無線ネットワーク１００を確立すべきである。基準デバイスの決定方法および無線ネットワーク１００の確立方法は、上述した実施例１と同様であり、これ以上の説明はしない。
【００４４】
次いで、ステップS11'において、自動割り当てシステム３００は、無線ネットワーク１００に基づいて、目標照明デバイスのそれぞれから、三つの基準デバイス１、２および３のそれぞれまでの実際のRSSIを得ることができる。RSSIijが基準位置jと割り当てノードiの間の測定されたRSSIを表すとする。次いで、各割り当てノードについて、パラメータDi＝RSSIi1−RSSIi3を定義する。このパラメータは、割り当てノードiと基準デバイス１との間の距離と、割り当てノードiと基準デバイス３との間の距離の比に関係する。
【００４５】
図７に示したグリッド構造によれば、各割り当てノードiについて、パラメータDiは
D(1,1)＞D(3,1)＞D(3,2)＝D(2,2)＞…        (5)
を満たすべきである。
【００４６】
そして、図７に示したグリッド形のトポロジカル・グラフから明らかなように、割り当てノード(2,1)および(2,2)と基準位置(1,1)および(1,2)との間の距離の和が最小になり；それらの距離の和は、目標照明位置と基準デバイス１および２との間のRSSIの和の形で表されることができる。
【００４７】
上記二つの原理に従って、各目標照明デバイスと基準デバイス１、２および３との間のRSSIに基づいて、自動割り当てシステム３００は、各目標照明デバイスと基準デバイス１、２および３のそれぞれとの間のRSSIを、次の公式によって記述される線形結合規則に従って組み合わせる：
Adevice＝RSSI1device＋RSSI2device−0.5×RSSI3device        (6)
ここで、変数deviceは各目標照明デバイスを表し、RSSIrdevice、r＝1,2,3は目標照明デバイスと基準デバイスrとの間のRSSIを表す。
【００４８】
次いで、ステップS120'において、自動割り当てシステム３００は、すべての目標照明デバイスの値Aを比較して、それぞれ最も大きな値Aと二番目に大きな値Aをもつ二つの目標照明デバイスを、割り当てノード(2,1)および(2,2)に対応する選択されたデバイスとして、選択する。順序の正しさを保証するために、二つの選択されたデバイスがそれぞれ位置されるノードは未知のままであり（？）、続くステップにおいて決定されることになる。
【００４９】
次いで、二つの選択されたデバイスに基づいて、割り当てノード(2,3)における第三の選択されたデバイスが、残っている目標照明デバイスから仮定される。図７に示したグリッド形のトポロジカル・グラフによれば、第三の選択されたデバイスと基準デバイス２および３およびノード(2,2)におけるデバイスのそれぞれとの間の距離の和が最小になるはずであり、同様に、それらの距離の和はRSSIによって表されることもできる。最初の二つの選択されたデバイスのどちらが位置(2,2)に設置されているかは現在未知なので、本実施形態は、最初の二つの選択されたデバイスにより近い目標照明デバイスを考える。次いで、各目標照明デバイスと基準デバイス２および３のそれぞれとの間のRSSIならびに各目標照明デバイスと最初の二つの選択されたデバイスのそれぞれとの間の相対的に大きなRSSIに基づいて、自動割り当てシステム３００は、次の公式によって記述される線形結合規則に従って組み合わせを実行する：
Bdevice＝RSSI2device＋RSSI3device＋RSSILdevice        (7)
ここで、変数deviceは残っている各目標照明デバイスを表し、RSSILdeviceは目標照明デバイスと最初の二つの選択されたデバイスのそれぞれとの間の二つのRSSIのうち相対的に大きなほうを表す。
【００５０】
次いで、自動割り当てシステム３００は、残っている目標照明デバイスすべての値Bを比較し、最大の値Bをもつ目標照明デバイスを第三の選択されたデバイスとして選択する。
【００５１】
三つの選択されたデバイスを決定するための上述した線形結合公式(6)および(7)は、グリッド形のトポロジカル・グラフに基づくヒューリスティックなアルゴリズム公式である。当業者は、本発明は上記の公式に限定されないことを理解するであろう。アルゴリズム設計を通じて、三つの割り当てノードに対応する三つの選択されたデバイスを決定するために使われる、後述するもう一つの例のような他の方法および公式が設計できる。
【００５２】
図７に示されるように、二つの基準位置(1,1)および(1,2)に基づいて、目標照明デバイスのうちの二つによって構成されるあらゆる組み合わせが列挙され、５つのRSSIの和、すなわち前記二つの照明デバイスの間のRSSIで一つ、前記二つの照明デバイスと前記二つの基準デバイス１および２のそれぞれとの間のRSSIで他の４個、の和が最大になる組み合わせにおける二つの照明デバイスが、二つの基準位置(1,1)および(1,2)に隣接する割り当てノード(2,1)および(2,2)にある。次いで、二つの基準位置(1,2)および(1,3)に基づいて、割り当てノード(2,2)および(2,3)における選択されたデバイスが同じようにして決定される。二つの割り当てノード（？）は三つの異なる選択されたデバイスを得るべきであり、該三つの選択されたデバイスはこれら三つの（？）割り当てノードにあるべきである。
【００５３】
三つの割り当てノードにある三つの選択されたデバイスを決定したのち、ステップS122'において、自動割り当てシステム３００は、三つの選択されたデバイスと三つの基準デバイスとの間の距離に関係する情報に基づいて、三つの選択されたデバイスがそれぞれ位置されている割り当てノードを決定する。
【００５４】
具体的には、図７に示したグリッド・トポロジカル・グラフによれば、(2,1)、(2,2)および(2,3)にある三つの選択されたデバイスについて、次の条件を満たすべきである。
【００５５】
１．変数Ci＝RSSI1i−RSSI3iを、三つの割り当てノードについての、割り当て点iにあるべきである選択されたデバイスから基準デバイス１へのRSSIと、前記選択されたデバイスから基準デバイス３へのRSSIとの間の差であるとする。変数Ciは次の関係を満たすべきである：
C(2,1)＞C(2,2)＞C(2,3)        (8)
|C(2,2)|＜|C(2,1)|＝|C(2,3)|        (9)。
【００５６】
中央の位置(2,2)にある選択されたデバイスから二つの他の選択されたデバイスへのRSSIの和が最大であるべきである；RSSIi,jが割り当てノードiにある選択されたデバイスから割り当てノードjにある選択されたデバイスへのRSSIであるとし、変数Eiは
【００５７】
【数６】
2012506192.tif 000008
であるとし、次の関係がある：
E(2,2)＞E(2,1)＝E(2,3)        (10)。
【００５８】
上記の二つの条件に基づいて、選択されたデバイスから基準デバイス１までのRSSIと選択されたデバイスから基準デバイス３までのRSSIとの間の差（値Ciに対応する）をまず比較することにより、差の大きい順に従って割り当てノード(2,1)、(2,2)および(2,3)において三つの選択されたデバイスが決定される。割り当ての精度をさらに改善するために、中央の位置(2,2)にある選択された装置が再び検証される。中央の位置にある選択されたデバイスから他の二つの選択されたデバイスへのRSSIの和（値Eiに対応する）と、中央の位置にある選択されたデバイスから基準デバイス１および基準デバイス３へのRSSIの間の差（値Ciに対応する）の絶対値との間の差（Ei−|Ci|に対応する）が最大となるべきである。最大の差をもつ選択されたデバイスが検証後、中央の位置に位置されていない場合、それは現在中央の位置にある選択されたデバイスと交換されるべきである。
【００５９】
三つの選択されたデバイスがそれぞれ位置される割り当てノードを決定するための上記の方法および公式(8)、(9)および(10)は唯一というものではなく、グリッド形のトポロジカル・グラフに基づくヒューリスティックなアルゴリズム公式である。当業者は、アルゴリズム設計を通じて、選択されたデバイスがそれぞれ位置される割り当てノードを決定するために、たとえばRSSIに重みをかけるまたは非線形結合を実行するなどどといった、他の方法および公式を設計できる。それらも本発明の保護範囲内である。
【００６０】
それぞれ割り当てノード(2,1)、(2,2)および(2,3)における三つの選択されたデバイスを決定したのち、自動割り当てシステム３００はノード(2,1)、(2,2)および(2,3)にあるそれら三つの選択されたデバイスを新しい基準デバイスとして採用し、ノード(2,1)、(2,2)および(2,3)にに隣接する他の目標照明デバイスを割り当てる。図９に示すところでは、正方形のブロックが割り当て済みのノードおよびデバイスを表し、白丸ブロックが割り当てられるべきノードを表し、暗い色の丸ブロックが委託中の（being  commissioned）ノードを表す。図９の（３）に示されるように、自動割り当てシステムは、トポロジカル・グラフの左部分におけるすべてのノードに設置されている照明デバイスを決定する。次いで、図９の（４）に示されるように、自動割り当てシステムは、垂直線内の三つの隣り合う割り当てられた照明デバイスを基準デバイスに取り、基準デバイスの右側の垂直線内の三つの隣り合う割り当てノードに設置されている目標照明デバイスを決定する。そして、図９の（５）に示されるように、割り当てられた選択されたデバイスは、割り当ての精度を改善するために検証されることができる。最後に、トポロジカル・グラフ全体におけるすべてのノードに設置された照明デバイスが決定され、割り当てプロセスは終了する。
【００６１】
上記では、本発明を例解するためにRSSIを例にとっているが、本発明が他の距離関係情報、たとえば飛行時間または飛行時間とRSSIの組み合わせを使うこともできることは理解されるであろう。RSSIについての本発明の教示に基づいて、当業者は、複数の基準デバイスに基づいて複数のデバイスを決定する方法を見出すことができることは明らかである。そうした方法も本発明の付属の請求項の範囲内であり、よって明細書ではこれ以上の詳細を与えることはしない。
【００６２】
自動割り当てシステム３００は各ステップの機能をそれぞれ充足するよう構成された対応する手段を有することができる。たとえば、ステップS11'を充足するよう構成された受信機および第一の取得手段と、ステップS120'を充足するよう構成された候補グループ決定手段と、ステップS121'を充足するよう構成された第三の決定手段である。これらの手段は、図５に示されるのと同様の、プログラムされたCPUを通じて実現されることができる。上述の記述に基づき、当業者は、対応する手段およびその動作モードを設計し、実現することができる。それらも本発明の付属の請求項の範囲内であり、よって明細書ではさらなる詳細を与えることはしない。
【００６３】
上記の実施形態に基づく本発明の側面が、図６、図７および図９に示される二次元のグリッド形のトポロジカル・グラフに制限されるものではなく、他のグリッド形のトポロジカル・グラフおよび三次元環境にも適用可能であることは理解されるであろう。これらも本発明の付属の請求項の範囲内であり、明細書ではこれ以上の詳細を与えることはしない。
【００６４】
上記では、本発明のある側面に基づき、方法および装置が例解されてきた。すなわち、複数の目標ノードにおける複数の照明デバイスを、複数の基準デバイスに基づいて、大きな安全マージンをもって、同時に決定し、次いで、それら複数の照明デバイスがそれぞれ位置されている目標ノードを決定する自動割り当てシステムである。以下では、本発明のもう一つの側面に基づく割り当て方法について詳細に述べる。
【実施例３】
【００６５】
トポロジカル・グラフ全体の割り当て成功率はトポロジカル・グラフのノード数に関係している。図１０に示されるように、シミュレーション結果は、成功する割り当て処理の数とトポロジカル・グラフのノード数との間の関係を示している。縦座標は、５０の割り当て処理のうちいくつ成功したかを表し、横座標はRSSIの測定誤差の標準偏差を表す（RSSIの測定誤差は平均が０のガウス分布であると想定している）。このシミュレーションによって用いられた割り当て方法は、上述の実施例１において使用された方法である。見て取れるように、ノードが１６個から２５個に増加するとともに（それぞれ三つの基準ノードを含む）、成功した割り当て処理の数は減少している。理由は、より多くのノードがあるほど、複数のノード全体について、誤った割り当てが生じる可能性が高くなるということである。一方、誤って割り当てられたノードが他のノードを割り当てるための基準ノードとして採用され、誤りを分散させることがありうる。したがって、大きなトポロジカル・グラフを正しく割り当てるためには、技術スタッフは割り当て処理を何回か実行する必要があることがある。
【００６６】
この問題を解決するために、本発明のもう一つの側面によれば、図１１に示されるように、自動割り当てシステム３００は大きなトポロジカル・グラフを複数の部分トポロジー・ブロックに分割する。システム３００は基準デバイスに基づいて部分トポロジー・ブロックを割り当て、各部分トポロジー・ブロックを検証する。検証後、正しく割り当てられていると判明した部分トポロジー・ブロック内のデバイスだけが、他の部分トポロジー・ブロックを割り当てるための基準デバイスとして採用されることができる。それにより、誤り伝搬が回避される。また、誤って割り当てられた部分トポロジー・ブロックが、正しい割り当てを達成するために何回か割り当てられることができることも許容される。それによりトポロジカル・グラフ全体の割り当て成功率が改善される。
【００６７】
具体的には、図１２に示されるように、ステップS20において、自動割り当てシステム３００はトポロジカル・グラフを、所定の規則に従って、ある数の割り当てられるべき部分トポロジー・ブロックに分割する。好ましくは、前記ある数の割り当てられるべき部分トポロジー・ブロックは、トポロジカル・グラフのノードおよび目標デバイスを省略せず、これらの部分トポロジー・ブロックは重なり合ってもいない。たとえば、図１１に示されるように、トポロジカル・グラフはグリッドの形の互いに隣接する１６個の部分トポロジー・ブロックに均等に分割される。部分トポロジー・ブロック分割の具体的な方法は、本発明の焦点ではなく、当業者は実際的な要件に従って、満足のいく分割方法を決定できる。
【００６８】
ステップS20では、自動割り当てシステム３００はさらに、基準ブロックBrを決定する。基準ブロックは、図１１の左上隅に示されるように、割り当てられるべき部分トポロジー・ブロックB1およびB2に隣接する。自動割り当てシステム３００は、隣接する部分トポロジー・ブロックB1およびB2を割り当てるために、割り当てられるべき部分トポロジー・ブロックB1およびB2に隣接する基準ブロック内のデバイスを、基準デバイスとして用いる。基準ブロックおよび基準ブロックのノードに設置されている基準デバイスを決定する具体的な方法は、基準ブロック内の既知の位置をもつデバイスを、上述した実施例１および実施例２または他の任意の既存の割り当て方法に基づいて割り当てを実行するための基準デバイスとして使うことができる。好ましくは、自動割り当てシステム３００は基準ブロックを検証する。具体的には、ステップS200において、自動割り当てシステム３００は、基準ブロック内の第一の諸基準デバイスに基づいて、第一の割り当て方法を採用して、（？）基準デバイスが基準ブロックの各ノードにそれぞれ設置されていると仮定する。次いで、ステップS201において、自動割り当てシステム３００は、第一の諸基準デバイスとは異なる諸基準デバイスを使って、第二の割り当て方法を採用し、（？）再び基準デバイスが基準ブロックの各基準位置に（？）設置されていると仮定する。最後に、ステップS202において、第二の基準デバイスに対応する仮定結果が第一の基準デバイスに対応する結果と同一であれば、自動割り当てシステム３００は、仮定結果に従って、基準ブロックの各ノードに設置されている基準デバイスを決定する。第一の基準デバイスが第二の基準デバイスとは異なるという状況の下では、第一の割り当て方法は上述した第二の割り当て方法と同じであることも異なることもできること、それらの方法による両割り当て結果が検証の機能を果たすことができることは理解されるであろう。同様に、第一の基準デバイスがそのまま使用されることもでき、第一の割り当て方法と異なる第二の割り当て方法が用いられれば、割り当て結果が検証の機能を果たすことができる。本発明は基準ブロックもトポロジー・ブロックであると想定することによって例解されているが、他の実施形態では、基準ブロック自身も複数の基準デバイスを含むことができることは理解されるであろう。
【００６９】
基準ブロックBrを決定したのち、図１１に示されるように、ステップS21において、自動割り当てシステム３００は、基準ブロックBrの、割り当てられるべき目標部分トポロジー・ブロックB1に隣接する諸基準デバイスR1を、初期基準デバイスとして取り、初期割り当てを実行するために初期割り当て方法を使い、各目標デバイスがそれぞれ目標部分トポロジー・ブロックB1の各ノードに設置されている（？）と仮定する（？）。前記初期割り当て方法は、トポロジカル・グラフにおけるノードに対応する目標デバイスを決定するいかなる割り当て方法を使うこともできる。たとえば、実施例１および実施例２において上述した方法である。
【００７０】
次いで、ステップS22において、自動割り当てシステム３００は、初期基準デバイスR1とは異なり、かつ目標部分トポロジー・ブロックB1に関係した諸デバイスR3を検証基準デバイスとして使い、該検証基準デバイスに基づいて検証割り当て方法を用いて検証割り当てを実行し、各目標デバイスが目標部分トポロジー・ブロックB1の各ノードに設置されていると仮定する（？）。前記検証基準デバイスは、目標部分トポロジー・ブロックB1の他のデバイスであってステップS21における初期基準デバイスR1に基づいて仮定される（？）もの、あるいは目標部分トポロジー・ブロックB1に隣接するまたは目標部分トポロジー・ブロックB1内にあるあらかじめ知られているさらに他の基準デバイスであることができる。検証基準デバイスが上述した初期基準デバイスとは異なるという状況の下では、検証割り当て方法は上述した初期割り当て方法と同じであることも異なることもできること、それらの方法による両割り当て結果が検証の機能を果たすことができることは理解されるであろう。同様に、初期基準デバイスがそのまま使用されることもでき、初期割り当て方法とは異なる検証割り当て方法が用いられ、この場合、割り当て結果が検証の機能を果たすことができる。
【００７１】
次いで、ステップS23において、自動割り当てシステム３００は、基準デバイスR3および／または検証割り当て方法に対応する仮定結果が、基準デバイスR1および初期割り当て方法に対応する仮定結果と同一であるかどうかを判断し、検証する。それらが同一であれば、自動割り当てシステム３００は目標部分トポロジー・ブロックB1の割り当てが成功し、再び検証される必要はないと判断する；部分トポロジー・ブロックB1は次いで割り当てられるべき他の隣接する部分トポロジー・ブロックを割り当てるための基準ブロックとして取ることができる。それらの仮定結果が異なる場合には、目標部分トポロジー・ブロックB1は相変わらず割り当てられるべきである；このトポロジー・ブロックはいまだ割り当てが成功する可能性がある；詳細は本記述の以下の部分において例解される。
【００７２】
上記のステップS21ないしS23とは関係なく、部分トポロジー・ブロックB2に隣接する基準デバイスR2に基づいて、システム３００は、各目標デバイスが目標部分トポロジー・ブロックB2内の各ノードに設置されていると仮定し（？）、割り当てが成功かどうかを検証する。B2が成功裏に割り当てられている場合、B2は、B3のような他の隣接する部分トポロジー・ブロックを割り当てるための基準ブロックとして取ることができる。同様に、B3が成功裏に割り当てられている場合、B3は上述した状況の下では成功裏に割り当てられていない部分トポロジー・ブロックB1に隣接しているので、B1に隣接するB3の諸デバイスを基準デバイスとして取ることができ、B1の割り当てが再び実行される。このようにして、B1の割り当て時が増え、割り当て成功率が改善される。
【００７３】
トポロジカル・グラフ全体について、上記のステップが繰り返され、すべての割り当てられた部分トポロジー・ブロックが割り当てられるべき他の部分トポロジー・ブロックを割り当てるための基準ブロックとして取られる。次の表のシミュレーション結果は、本実施形態に基づく割り当て方法の割り当て成功率を示している。
【００７４】
【表１】
2012506192.tif 000009
表から見て取れるように、複数の部分トポロジー・ブロックをもつトポロジカル・グラフの割り当て成功率は単一の部分トポロジー・ブロックの割り当て成功率より高い。これは、割り当てエラーのある部分トポロジー・ブロックがその後も何回か割り当てられることがありえ、そのためトポロジカル・グラフ全体の割り当て成功率が実質的に高められるためである。
【００７５】
反復の過程において次のような状況が存在しうることは注目に値する：割り当てが成功したすべての部分トポロジー・ブロックが割り当てられるべき隣接する部分トポロジー・ブロックを割り当てるための基準ブロックとして取られるが、すべての隣接する基準ブロックに基づいて割り当てが行われた後でも正しい割り当て結果を得ることのできない割り当てられるべき部分トポロジー・ブロックがまだある。この場合、本発明の処理方法全体が繰り返されることができ、トポロジカル・グラフが再びブロックに分割され、測定され、割り当てられる。トポロジカル・グラフの割り当て成功が保証できない理由が、割り当てアルゴリズムが実際的な通信環境の逸脱によって全く影響されることができないことが保証できないということ、および各部分トポロジー・ブロックが正しく割り当てられることができないということであることは理解されるであろう。本実施形態において開示されている内容に基づいて、当業者は、本発明の処理方法全体が再現可能であり、繰り返し実現されることができること、およびその繰り返される実現は部分トポロジー・ブロックの割り当てのランダムさには依存しないことを理解するであろう。
【００７６】
自動割り当てシステム３００は、各ステップの機能をそれぞれ充足するよう構成された対応する手段を有することができる。たとえば、ステップS20を充足するよう構成されたブロック分割手段および基準ブロック決定手段、ステップS21を充足するよう構成された初期割り当て手段、ステップS22を充足するよう構成された検証割り当て手段およびステップS23を充足するよう構成された判断手段である。好ましくは、基準ブロック決定手段はさらに、ステップS200を充足するよう構成された第三の割り当て手段と、ステップS201を充足するよう構成された第四の割り当て手段を有する。これらの手段は、プログラムされたCPUを通じて実現されることができる。上述の詳細な記述に基づき、当業者は、対応する手段およびその作用プロセスを設計できる。それらも本発明の付属の請求項の範囲内であり、よって明細書ではさらなる詳細を与えることはしない。
【００７７】
上記の実施形態に基づく本発明の側面が、図１１に示されるトポロジカル・グラフに制限されるものではなく、他のトポロジカル・グラフについて適用可能であり、三次元環境においても使用できることは理解できる。これらはみな本発明の付属の請求項の範囲内であり、明細書ではこれ以上の詳細を与えることはしない。
【図１】
2012506192.tif 000010
【図２】
2012506192.tif 000011
【図３】
2012506192.tif 000012
【図４】
2012506192.tif 000013
【図５】
2012506192.tif 000014
【図６】
2012506192.tif 000015
【図７】
2012506192.tif 000016
【図８】
2012506192.tif 000017
【図９】
2012506192.tif 000018
【図１０】
2012506192.tif 000019
【図１１】
2012506192.tif 000020
【図１２】
2012506192.tif 000021
【手続補正書】
【提出日】平成23年4月19日(2011.4.19)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
トポロジカル・グラフ中での各目標デバイスの位置を決定する方法であって：
ａ．少なくとも二つの基準デバイスと各目標デバイスとの間の無線接続を確立する段階であって、前記基準デバイスのそれぞれの前記トポロジカル・グラフにおける位置は既知であり、前記トポロジカル・グラフは複数のノードの位置情報を含む、段階と；
ｂ．前記無線接続に基づいて、各目標デバイスの、前記少なくとも二つの基準デバイスに対する、測定距離関係情報を測定し、距離基準情報を得る段階とを含み；
当該方法がさらに、
ｃ．前記距離基準情報に基づいて、各目標デバイスを前記トポロジカル・グラフの対応するノードにマッピングする段階を含むことを特徴とする、
方法。
【請求項２】
請求項１記載の方法であって、前記段階ｂがさらに：
・各目標デバイスが前記トポロジカル・グラフ中のある割り当てノードの位置に位置されていると想定し、該想定のもとで、各目標デバイスの、前記少なくとも二つの基準デバイスに対する、想定距離関係情報を得る段階を含み；
各目標デバイスについて、前記距離基準情報は、その測定距離関係情報と前記割り当てノードについての想定距離関係情報との間の差を含み；
前記段階ｃがさらに：
・前記割り当てノードについて、前記目標デバイスの一つまたは複数から、その想定距離関係情報と測定距離関係情報との間の差が相対的に小さい一つの目標デバイスを、前記割り当てノードに対応する目標デバイスとして選択する段階を含む、
方法。
【請求項３】
請求項２記載の方法であって、前記段階ｃがさらに：
・前記割り当てノードについて、対応する想定距離関係情報と測定距離関係情報との間の差が最も小さい目標デバイスを、前記割り当てノードに対応する目標デバイスとして選択することを含む、
方法。
【請求項４】
請求項２記載の方法であって、前記段階ｃがさらに：
ｃ１．前記割り当てノードについて、想定距離関係情報と測定距離関係情報との間の差が相対的に小さい所定数の複数の候補目標デバイスを決定する段階と；
ｃ２．各候補目標デバイスを第一の補助基準デバイスとして取り、前記少なくとも二つの基準デバイスおよび前記第一の補助基準デバイスに従って、一つまたは複数の補助基準ノードに対応する一つまたは複数の補助目標デバイスがあると仮定する段階と；
ｃ３．前記一つまたは複数の補助基準ノードに対応する、候補目標デバイスと前記一つまたは複数の補助目標デバイスとの各組み合わせについて、前記候補目標デバイスおよび前記少なくとも二つの基準デバイスおよび前記対応する一つまたは複数の補助目標デバイスの間の無線接続に基づいて、前記候補目標デバイスの、前記少なくとも二つの基準デバイスおよび前記対応する一つまたは複数の補助目標デバイスに対する測定距離関係情報を測定し、前記一つまたは複数の補助目標デバイスが前記一つまたは複数の補助基準ノードに対応すると想定して、該想定のもとに、前記候補目標デバイスの、前記少なくとも二つの基準デバイスおよび前記対応する一つまたは複数の補助目標デバイスに対する、想定距離関係情報を得る段階と；
ｃ４．各組み合わせから、前記候補目標デバイスの、前記少なくとも二つの基準デバイスおよび前記対応する一つまたは複数の補助目標デバイスに対する測定距離関係情報と、その想定距離関係情報との間の差が最も小さい組み合わせを判別し、その組み合わせにおける候補目標デバイスが前記割り当てノードにおける目標デバイスに対応すると判定する段階とを含む、
方法。
【請求項５】
請求項４記載の方法であって、前記段階ｃ２がさらに：
ｃ２−１：前記候補目標デバイスの一つを第一の補助基準デバイスとして取り、近くの一つまたは複数の目標デバイスと少なくとも二つの基準デバイスおよび前記第一の補助デバイスとの間の無線接続に基づいて、前記一つまたは複数の目標デバイスの、前記少なくとも二つの基準デバイスおよび前記第一の補助基準デバイスに対する、測定距離関係情報を測定する段階と；
ｃ２−２：前記目標デバイスのそれぞれが前記補助基準ノードの一つに対応すると想定し、該想定のもとで、各目標デバイスの、前記少なくとも二つの基準デバイスおよび前記第一の補助基準デバイスに対する、想定距離関係情報を得る段階と；
ｃ２−３：前記補助基準ノードについて、すべての目標デバイスのうちから、前記目標デバイスの、前記少なくとも二つの基準デバイスおよび前記第一の補助基準デバイスに対する、想定距離関係情報と測定距離関係情報との間の差が相対的に小さい一つまたは複数の目標デバイスを、前記補助ノードに対応する補助目標デバイスとして決定する段階とを含み、
前記候補目標デバイスのそれぞれおよび前記補助基準ノードのそれぞれについて、上記の諸段階を繰り返すことを含む、
方法。
【請求項６】
請求項２ないし５のうちいずれか一項記載の方法であって、前記測定距離関係情報および想定距離関係情報が、対応するデバイス間での電波信号の受信信号強度指標RSSIおよび／または飛行時間を含み、想定距離関係情報と測定距離関係情報との間の前記差が、対応する目標デバイスが対応する位置にあるという想定のもとでの対応する目標デバイスと対応する基準デバイスとの間の相対的な想定されるRSSIベクトルと、それらの間の相対的な測定されるRSSIベクトルとの間のベクトル差、および／または、対応する目標デバイスが対応する位置にあるという想定のもとでの対応する目標デバイスと対応する基準デバイスとの間の想定される飛行時間と、それらの間の測定される飛行時間との間の差、を含む、
方法。
【請求項７】
請求項１記載の方法であって、前記トポロジカル・グラフ中でのノードの位置がグリッド形であり、前記段階ｂが：
・前記目標デバイスすべてのうちの所定数の複数の目標デバイスによって構成されるすべての候補グループを列挙し、前記各候補グループについて、所定の組み合わせ規則に従って、前記少なくとも二つの基準デバイスに対する、前記所定数の複数の目標デバイスの測定距離関係情報の数学的な組み合わせを決定する段階を含み、前記距離基準情報はすべての候補グループの対応する数学的組み合わせを含み；
前記段階ｃが：
ｃ１．すべての候補グループの対応する数学的組み合わせに基づいて、所定の規則に従って一つの目標候補グループを選択し、前記目標候補グループの所定数の複数の目標デバイスを、前記少なくとも二つの基準デバイスに近隣の所定数の複数の割り当てノードに対応する選択されたデバイスとして選択する段階と；
ｃ２．前記少なくとも二つの基準デバイスの少なくとも一つに対する、前記所定数の複数の選択されたデバイスの測定距離関係情報に基づいて、前記所定数の複数の選択されたデバイスのそれぞれがどの割り当てノードに対応するかを決定する段階とを含む、
方法。
【請求項８】
請求項７記載の方法であって、前記少なくとも二つの基準ノードは同じグリッド線上にあり、互いに隣接しており、前記目標デバイスのそれぞれは前記少なくとも二つの基準デバイスの同じ側にあるおよび／または前記少なくとも二つの基準デバイスと同じグリッド線上にあり、前記所定数の複数の割り当てノードは前記基準デバイスのそれぞれに同じ側で隣接しており、前記距離関係情報は対応するデバイス間での電波信号の受信信号強度指標RSSIおよび／または飛行時間を含み、前記数学的組み合わせは電波信号のRSSIおよび／または飛行時間の線形結合である、方法。
【請求項９】
請求項１ないし８のうちいずれか一項記載の方法であって、さらに：
ｄ．前記割り当てノードに対応すると決定された前記目標デバイスを新しい基準デバイスとして取り、段階ａないしｃを繰り返すことを、前記トポロジカル・グラフ中のすべてのノードに対応する目標デバイスが決定されるまで行う、
方法。
【請求項１０】
トポロジカル・グラフ中での各目標デバイスの位置を決定する割り当て装置であって、前記トポロジカル・グラフは複数のノードの位置情報を含み、前記トポロジカル・グラフにおける少なくとも二つの基準デバイスの位置は既知であり、各基準デバイスと前記目標デバイスのそれぞれとの間に無線接続があり、当該割り当て装置は：
・前記少なくとも二つの基準デバイスに対する、前記各目標デバイスの測定距離関係情報を受け取るよう構成された受信機と；
・距離基準情報を得るよう構成された第一の取得手段とを有し；
当該割り当て装置はさらに：
・前記距離基準情報に基づいて、各目標デバイスを前記トポロジカル・グラフの対応するノードにマッピングするよう構成された第一の決定手段を有することを特徴とする、
装置。
【請求項１１】
請求項１０記載の装置であって、前記第一の取得手段がさらに：
各目標デバイスが前記トポロジカル・グラフ中のある割り当てノードの位置に位置されていると想定し、該想定のもとで、各目標デバイスの、前記少なくとも二つの基準デバイスに対する、想定距離関係情報を得るよう構成されており；
各目標デバイスについて、前記距離基準情報は、その測定距離関係情報と前記割り当てノードについての想定距離関係情報との間の差を含み；
前記第一の決定手段がさらに、前記割り当てノードについて、前記目標デバイスの一つまたは複数から、その想定距離関係情報と測定距離関係情報との間の差が相対的に小さい一つの目標デバイスを、前記割り当てノードに対応する目標デバイスとして選択するよう構成されている、
装置。
【請求項１２】
請求項１１記載の装置であって、前記第一の決定手段が：
・前記割り当てノードについて、想定距離関係情報と測定距離関係情報との間の差が相対的に小さい所定数の複数の候補目標デバイスを決定するよう構成された候補デバイス決定手段と；
・各候補目標デバイスを第一の補助基準デバイスとして取り、前記少なくとも二つの基準デバイスおよび前記第一の補助基準デバイスに従って、一つまたは複数の補助基準ノードに対応する一つまたは複数の補助目標デバイスがあると仮定するよう構成された補助目標デバイス仮定手段と；
・前記一つまたは複数の補助基準ノードに対応する、候補目標デバイスと前記一つまたは複数の補助目標デバイスとの各組み合わせについて、各候補目標デバイスおよび前記少なくとも二つの基準デバイスおよび前記対応する一つまたは複数の補助目標デバイスの間の無線接続に基づいて、各候補目標デバイスの、前記少なくとも二つの基準デバイスおよび前記対応する一つまたは複数の補助目標デバイスに対する測定距離関係情報の測定を実行し、前記一つまたは複数の補助目標デバイスが前記一つまたは複数の補助基準ノードに対応すると想定して、該想定のもとに、各候補目標デバイスの、前記少なくとも二つの基準デバイスおよび対応する一つまたは複数の補助目標デバイスに対する、想定距離関係情報を得るよう構成された第二の取得手段とを有しており；
前記第一の決定手段がさらに：
すべての組み合わせから、前記候補目標デバイスの、前記少なくとも二つの基準デバイスおよび対応する一つまたは複数の補助目標デバイスに対する測定距離関係情報と想定距離関係情報との間の差が最も小さい組み合わせを判別し、その組み合わせにおける候補目標デバイスが前記割り当てノードにおける目標デバイスに対応すると判定するよう構成されている、
装置。
【請求項１３】
請求項１２記載の装置であって、前記補助割り当てデバイス仮定手段がさらに：
・前記候補目標デバイスの一つを第一の補助基準デバイスとして取り、近くの一つまたは複数の目標デバイスと少なくとも二つの基準デバイスおよび第一の補助基準デバイスとの間の無線接続に基づいて、前記一つまたは複数の目標デバイスの、前記少なくとも二つの基準デバイスおよび前記第一の補助基準デバイスに対する、測定距離関係情報を測定するよう構成された第三の取得手段と；
・各目標デバイスがそれぞれ前記補助基準ノードの一つに対応すると想定し、該想定のもとで、各目標デバイスの、前記少なくとも二つの基準デバイスおよび前記第一の補助基準デバイスに対する、想定距離関係情報を得るよう構成された第四の取得手段と；
・前記補助基準ノードについて、すべての目標デバイスのうちから、前記目標デバイスの、前記少なくとも二つの基準デバイスおよび前記第一の補助基準デバイスに対する、想定距離関係情報と測定距離関係情報との間の差が相対的に小さい一つまたは複数の目標デバイスを、前記補助ノードに対応する補助目標デバイスとして決定するよう構成されている第二の決定手段とを有する、
装置。
【請求項１４】
請求項１０記載の装置であって、前記トポロジカル・グラフがグリッド形であり、前記第一の取得手段が：
・前記目標デバイスすべてのうちの所定数の複数の目標デバイスによって構成されるすべての候補グループを列挙し、各候補グループについて、前記少なくとも二つの基準デバイスに対する、前記核候補グループの前記所定数の複数の目標デバイスの測定距離関係情報の数学的な組み合わせを決定するよう構成されており、前記距離基準情報はすべての候補グループの対応する数学的組み合わせを含み；
前記第一の決定手段が：
・すべての候補グループの対応する数学的組み合わせに基づいて、所定の規則に従って一つの目標候補グループを選択し、前記目標候補グループの所定数の複数の目標デバイスを、前記少なくとも二つの基準デバイスに隣接する所定数の複数の割り当てデバイスに対応する選択されたデバイスとして選択するよう構成された候補グループ決定手段と；
・前記少なくとも二つの基準デバイスの少なくとも一つに対する、前記所定数の複数の選択されたデバイスの測定距離関係情報に基づいて、前記所定数の複数の選択されたデバイスのそれぞれがどの割り当てノードに対応するかを決定するよう構成された第三の決定手段とを有する、
装置。
【請求項１５】
請求項１４記載の装置であって、前記少なくとも二つの基準デバイスは同じグリッド線上にあり、互いに隣接しており、各目標デバイスは前記少なくとも二つの基準デバイスの同じ側にあるおよび／または前記少なくとも二つの基準デバイスと同じグリッド線上にあり、前記所定数の複数の割り当てノードは各基準デバイスに同じ側で隣接しており、前記距離関係情報は対応するデバイス間での電波信号の受信信号強度指標RSSIおよび／または飛行時間を含み、前記数学的組み合わせは電波信号のRSSIおよび／または飛行時間の線形結合である、装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００２
【補正方法】変更
【補正の内容】
【０００２】
今日、さまざまな建物や領域において、照明、デコレーションまたは表示機能といった複数の機能を提供するよう、非常に多数の照明デバイスによって構成されるアレイのようなデバイス・アレイが大規模に展開されている。建物管理システムのようなシステムは該照明デバイス・アレイを遠隔モニタリングおよび管理し、各照明デバイスのオン、オフを制御し、その照明モードを切り換えるなどする。照明、デコレーションまたは表示のような複数の機能に対して改善するために、異なるノード位置にあるすべての照明位置に異なる命令を送り、所望の照明、デコレーションおよび表示機能を実現するよう、前記システムは各照明デバイスの位置、たとえば各デバイスの一意的識別情報（Unique  Identification；略UID）とデザイン・トポロジカル・グラフ上でのその設置ノード位置との間の対応関係、を正確に取得することができる必要がある。システムによって取得される各デバイスの位置がその実際の物理的位置でない場合、これは照明アレイが適正に機能しないことを引き起こす。デバイス・アレイの通常動作の前に実行されるデバイス・アレイの割り当て（assigning）は、この問題を解決して、各デバイスがトポロジカル・グラフにおける一つの既知のノードに対応するようにする目的のためである。
WO2006/095316は、複数のノードの測定された相対的な空間位置を利用することによって無線照明ノードをグループ化する方法を開示している。WO2006/095316においては、相対空間位置を測るためにRSSIが使われる。二つのノードが壁によって隔てられているとき、両者の測定されたRSSI値は大きく異なることがあり、その結果、これら二つのノードは二つの異なるグループにグループ化される。
US2006/0274676A1は、複数の経路損失値を測定し、経路損失モデルを利用することによって距離を決定するノードを位置特定する方法を開示している。決定された距離に基づいてノードの位置が位置特定される。
【国際調査報告】
2012506192.tif 000022
2012506192.tif 000023