(57)【要約】      （修正有）【課題】無線セルラ通信網のエリアをカバーするノード集合の中で、エネルギー節減モードではないノードの部分集合を決定する方法を提供する。【解決手段】ノードの部分集合のノードは、幾つかのノードがエネルギー節減モードであるとき、ノード集合のエリアをカバーする。ノード集合のうちのノードの近傍ノード間のリンクを決定し、各ノードについて、メトリック値を特定し、メトリックは、ノードがリンクされる未処理ノードの数であり、最も高いメトリック値を有するノードをノードの部分集合に追加し、追加されたノードの近傍にあるノードを処理済みとマークし及び−ノードが全て処理されるまで、メトリックを特定するステップ、ノードをノードの部分集合に追加するステップ及びノードをマークするステップを繰り返す。【選択図】図５
2015177543.tif 000002
【特許請求の範囲】
【請求項１】
エリアをカバーする無線セルラ通信網のノード集合の中で、エネルギー節減モードではないノードの部分集合と、ノードの部分集合に属せずエネルギー節減モードに設定されるノードとを決定する方法であって、前記ノードの部分集合に属さない前記ノードがエネルギー節減モードであるとき、前記ノードの前記部分集合の前記ノードが、前記ノード集合の前記エリアをカバーし、
前記方法が、
前記ノード集合の前記ノードの近傍ノード間のリンクを決定するステップと、
各ノードについて、前記ノードがリンクされる未処理ノードの数であるメトリック値を特定するステップと、
最も高い前記メトリック値を有する前記ノードを前記ノードの部分集合に追加するステップと、
前記追加されたノードの近傍にある前記ノードを処理済みとマークするステップと、
前記ノードが全て処理されるまで、前記メトリックを特定するステップ、前記ノードの部分集合に前記ノードを追加するステップ、および前記ノードをマークするステップを繰り返すステップと、
を含むことを特徴とする、方法。
【請求項２】
前記ノードの部分集合の各ノードが前記ノードの部分集合の少なくとも１つのノードの近傍にあるか、または前記ノードの部分集合の各ノードが前記ノードの部分集合の他のノードの近傍にないことを特徴とする、請求項１に記載の方法。
【請求項３】
前記方法が中央装置によって実行され、近傍ノード間の前記リンクがグラフのリンクであることを特徴とする、請求項１または２に記載の方法。
【請求項４】
前記ノードの部分集合の各ノードが処理済みとマークされることを特徴とする、請求項２に記載の方法。
【請求項５】
前記方法がノード装置の前記集合の各ノードによって実行され、近傍ノード間の前記リンクが、近傍ノードリストおよび近傍ノードの近傍ノードリストに従って決定されることを特徴とする、請求項１に記載の方法。
【請求項６】
前記ノードの部分集合の各ノードが処理済みとマークされることを特徴とする、請求項５に記載の方法。
【請求項７】
前記リンクが、前記ノード集合によってカバーされる前記エリアに現在配置されているモバイル端末および／または前記ノード集合によってカバーされる前記エリアに配置されていたモバイル端末によって報告される測定値に従って、ならびに／あるいは前記ノード集合の前記ノードの近傍関係表に従って決定されることを特徴とする、請求項１〜６の何れか一項に記載の方法。
【請求項８】
前記測定値が、基準信号受信電力および／または基準信号受信品質であることを特徴とする、請求項７に記載の方法。
【請求項９】
前記リンクが、各モバイル端末の推定ＳＩＮＲ値に従って決定され、前記推定ＳＩＮＲ値が、基準信号受信電力および／または基準信号受信品質と、近傍ノードであり得る前記ノードがエネルギー節減モードであるとの仮定とに基づいて特定されることを特徴とする、請求項１〜８の何れか一項に記載の方法。
【請求項１０】
エリアをカバーする無線セルラ通信網のノード集合の中で、エネルギー節減モードではないノードの部分集合と、ノードの部分集合に属せずエネルギー節減モードに設定されるノードとを決定する装置であって、前記ノードの部分集合に属さない前記ノードがエネルギー節減モードであるとき、前記ノードの前記部分集合の前記ノードが、前記ノード集合の前記エリアをカバーし、
前記装置が、
前記ノード集合の前記ノードの近傍ノード間のリンクを特定する手段と、
各ノードについて、前記ノードがリンクされる未処理ノードの数であるメトリック値を特定する手段と、
最も高い前記メトリック値を有する前記ノードを前記ノードの部分集合に追加する手段と、
前記追加されたノードの近傍にある前記ノードを処理済みとマークする手段と、
前記ノードが全て処理されるまで、前記メトリックを特定すること、前記ノードの部分集合に前記ノードを追加すること、および前記ノードをマークすることを繰り返す手段と、
を備えることを特徴とする、装置。
【請求項１１】
プログラマブル装置に直接ロード可能であることができるコンピュータプログラムであって、前記プログラマブル装置で実行されると、請求項１〜９の何れか一項に記載の方法のステップを実施する命令または符号の部分を含む、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的には、エリアをカバーする無線セルラ通信網のノード集合の中で、エネルギー節減モードではないノードの部分集合を決定する方法および装置に関する。
【背景技術】
【０００２】
無線セルラ通信網は今日、広く使用されている。いくつかの基地局は、そのようなネットワークへのアクセスを小さなカバレッジエリア内で提供する。これらの基地局は、ホーム基地局、ピコ基地局、またはフェムト基地局と呼ばれ、電力を消費し、エネルギー節減が重要な話題になっている。
【０００３】
例えば、ホーム基地局の部分集合(subset)をアクティブ状態に保つことができ、無線セルラ通信網によって提供されるカバレッジエリアを維持しながら、他のホーム基地局を電源オフ状態のようなエネルギー節減モードに設定することができる。
【０００４】
システムの全体放射電力を低減しつつ、無線セルラ通信網によってサービングされるモバイル端末へのサービス品質を維持するように、送信電力の最適化を実行することもできる。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明は、エネルギー節減モードに設定される他のホーム基地局のカバレッジを補償する最小濃度のホーム基地局集合を効率的に計算することを目的とする。
【０００６】
この補償集合は、カバレッジエリア内のアクティブ状態のモバイル端末およびアイドル状態のモバイル端末の性能が最適化されるように構築される。
【課題を解決するための手段】
【０００７】
このために、本発明は、エリアをカバーする無線セルラ通信網のノード集合の中で、エネルギー節減モードではないノードの部分集合と、ノードの部分集合に属せずエネルギー節減モードに設定されるノードとを決定する方法であって、ノードの部分集合に属さないノードがエネルギー節減モードであるとき、ノードの部分集合のノードは、ノード集合のエリアをカバーし、
本方法は、
−ノード集合のノードの近傍ノード間のリンクを決定するステップと、
−各ノードについて、ノードがリンクされる未処理ノードの数であるメトリック値を特定するステップと、
−最も高いメトリック値を有するノードをノードの部分集合に追加するステップと、
−追加されたノードの近傍にあるノードを処理済みとマークするステップと、
−ノードが全て処理されるまで、メトリックを特定するステップ、ノードの部分集合にノードを追加するステップ、およびノードをマークするステップを繰り返すステップと、
を含むことを特徴とする、方法に関する。
【０００８】
本発明は、エリアをカバーする無線セルラ通信網のノード集合の中で、エネルギー節減モードではないノードの部分集合と、ノードの部分集合に属せずエネルギー節減モードに設定されるノードとを決定する装置であって、ノードの部分集合に属さないノードがエネルギー節減モードであるとき、ノードの部分集合のノードが、ノード集合のエリアをカバーし、
本装置は、
−ノード集合のノードの近傍ノード間のリンクを特定する手段と、
−各ノードについて、ノードがリンクされる未処理ノードの数であるメトリック値を特定する手段と、
−最も高いメトリック値を有するノードをノードの部分集合に追加する手段と、
−追加されたノードの近傍にあるノードを処理済みとマークする手段と、
−ノードが全て処理されるまで、メトリックを特定すること、ノードの部分集合にノードを追加すること、およびノードをマークすることを繰り返す手段と、
を備えることを特徴とする、装置にも関する。
【０００９】
したがって、決定されるノードの部分集合は、ノードの部分集合内にないノードがエネルギー節減モードに設定されるとき、ノード集合のカバレッジエリア内のモバイル端末についてカバレッジを保証する。
【００１０】
特定の特徴によれば、ノードの部分集合の各ノードがノードの部分集合の少なくとも１つのノードの近傍にあるか、またはノードの部分集合の各ノードがノードの部分集合の他のノードの近傍にない。
【００１１】
したがって、決定されるノードの部分集合は接続され、調整マルチポイント送信技法またはノードの部分集合のノード間のセル間干渉調整を使用することにより、アクティブ状態のモバイル端末および／またはアイドル状態のモバイル端末が受けるサービスの品質を更に改善し得る。
【００１２】
特定の特徴によれば、本方法は、中央装置によって実行され、近傍ノード間のリンクはグラフのリンクである。
【００１３】
したがって、ノード集合のカバレッジエリアのグローバルカバレッジ情報を使用してノードの部分集合が見つけられるため、エネルギー節減能力が改善し、カバレッジエリア内のモバイル端末のサービス品質が維持される。
【００１４】
特定の特徴によれば、本方法は、ノード装置の集合の各ノードによって実行され、近傍ノード間のリンクは、近傍ノードリストおよび近傍ノードの近傍ノードリストに従って決定される。
【００１５】
したがって、ノードの部分集合の決定は、ノード集合のノード間の追加のシグナリングにより、より柔軟且つ効率的に行われる。
【００１６】
特定の特徴によれば、ノードの部分集合は、処理されていないノード数を表すメトリック値に従って決定され、処理されたノードは、ノードの部分集合のノードの近傍にあるノードである。
【００１７】
したがって、決定される部分集合内にないノードがエネルギー節減に設定されるとき、決定されるノードの部分集合は、エネルギー節減モードに設定し得る最大数の近傍ノードのカバレッジを補償し、ノード集合の全体カバレッジは維持される。
【００１８】
特定の特徴によれば、ノードの部分集合の各ノードは処理済みとマークされる。
【００１９】
したがって、決定されるノードの部分集合は接続されず、そのためシグナリングを低減した状態で、ノード集合によってカバーされるエリア内に現在配置されているモバイル端末のカバレッジが補償され、ノードの部分集合の決定の複雑性が低減する。
【００２０】
特定の特徴によれば、リンクは、ノード集合によってカバーされるエリアに現在配置されているモバイル端末および／またはノード集合によってカバーされるエリアに配置されていたモバイル端末によって報告される測定値に従って、ならびに／あるいはノード集合のノードの近傍関係表に従って決定される。
【００２１】
したがって、ノードの部分集合を計算するとき、ノード集合によってカバーされるエリアに現在配置されているモバイル端末のカバレッジは最適化される。
【００２２】
特定の特徴によれば、測定値は、基準信号受信電力および／または基準信号受信品質である。
【００２３】
したがって、ノードの部分集合を計算する場合、ノード集合によってカバーされるエリアに現在配置されているアクティブ状態のモバイル端末が受けるサービスの品質は最適化される。
【００２４】
特定の特徴によれば、リンクは、各モバイル端末の推定ＳＩＮＲ値に従って決定され、推定ＳＩＮＲ値は、基準信号受信電力および／または基準信号受信品質と、近傍ノードであり得るノードがエネルギー節減モードであるとの仮定とに基づいて特定される。
【００２５】
したがって、ノードの部分集合内にないノードをエネルギー節減モードに設定することから得られるエネルギー節減利得と同様に、ノード集合のカバレッジエリア内のモバイル端末のサービス品質が改善する。
【００２６】
更に別の態様によれば、本発明は、プログラマブル装置に直接ロード可能であることができるコンピュータプログラムであって、上記コンピュータプログラムがプログラマブル装置で実行されると、本発明による方法のステップを実施する命令または符号の部分を含む、コンピュータプログラムに関する。
【００２７】
コンピュータプログラムに関連する特徴および利点は、本発明による方法および装置に関連して上述したものと同じであるため、ここで繰り返さない。
【００２８】
本発明の特徴は、実施形態例の以下の説明を読むことからより明確になり、上記説明は添付図面を参照して行われる。
【図面の簡単な説明】
【００２９】
【図１】本発明が実施される無線セルラ通信網のノードのカバレッジエリアを表す。
【図２】本発明が実施されるノードの構造を表す図である。
【図３】本発明の第１の実現形態による、ノードによって実行されるアルゴリズムの一例を開示する。
【図４】本発明により構築されるグラフの一例を表す。
【図５】本発明の第１の実現形態による、支配部分集合を決定するためにノードによって実行されるアルゴリズムの第１の例を開示する。
【図６】本発明の第１の実現形態による、支配部分集合を決定するためにノードによって実行されるアルゴリズムの第２の例を開示する。
【図７】本発明の第２の実現形態による、支配部分集合を決定するために各ノードによって実行されるアルゴリズムの第１の例を開示する。
【図８】本発明の第２の実現形態による、支配部分集合を決定するために各ノードによって実行されるアルゴリズムの第２の例を開示する。
【発明を実施するための形態】
【００３０】
図１は、本発明が実施される無線セルラ通信網のカバレッジエリアノードを表す。
【００３１】
図１の例では、ＮＤ１〜ＮＤ１６と記された１６個のノードの集合がエリアをカバーする。
【００３２】
ノードＮＤ１〜ＮＤ１６は、ホーム基地局、ピコ基地局、またはフェムト基地局である。
【００３３】
ノードＮＤ１〜ＮＤ１６は、ノードＮＤ１〜ＮＤ１６のセルのエリア内に位置されるモバイル端末によって受信され処理され得る信号をセル内で放射する。ノードＮＤ１〜ＮＤ１６は、それぞれのセル内に位置されるモバイル端末によって転送される信号を受信して処理することが可能である。
【００３４】
第１の実現形態により、無線セルラ通信網は、ノードＮＤ１〜ＮＤ１６に論理的に接続される中央装置を備え得る。中央装置は、明確にするために図１に示されていない。
【００３５】
中央装置は、専用装置であってもよく、または無線セルラ通信網から選ばれたホーム基地局に含まれてもよい。
【００３６】
本発明の第１の実現形態によれば中央装置は、
または本発明の第２の実現形態によれば各ノードは、
−ノード集合のノードの近傍ノード間のリンクを決定し、
−各ノードについて、ノードがリンクされる未処理ノードの数であるメトリック値を特定し、
−最も高いメトリック値を有するノードをノードの部分集合に追加し、
−追加されたノードの近傍にあるノードを処理済みとマークし、および
−ノードが全て処理されるまで、メトリックを特定すること、ノードの部分集合にノードを追加すること、およびノードをマークすることを繰り返す。
【００３７】
図２は、本発明が実施されるノードの構造を表す図である。
【００３８】
ノードＮＤは、例えば、バス２０１によって互いに接続される構成要素と、図３、図５、および図６または図７および図８に開示されるようなプログラムによって制御されるプロセッサ２００とに基づく構造を有する。
【００３９】
ここで、ノードＮＤが専用集積回路に基づく構造を有してもよいことに留意する必要がある。
【００４０】
バス２０１は、プロセッサ２００を読み取り専用メモリＲＯＭ２０２、ランダムアクセスメモリＲＡＭ２０３、ネットワークインタフェース２０４、および無線インタフェース２０５にリンクする。
【００４１】
メモリ２０３は、図３、図５、および図６または図７および図８に開示されるようなアルゴリズムに関連するプログラムの変数および命令を受信することが意図されるレジスタを含む。
【００４２】
プロセッサ２００は、無線インタフェース２０５の動作を制御する。
【００４３】
読み取り専用メモリ２０２は、図３、図５、および図６または図７および図８に開示されるようなアルゴリズムに関連するプログラムの命令を含む。命令は、ノードＮＤの電源投入時にランダムアクセスメモリ２０３に転送される。
【００４４】
以下、図３、図５、および図６または図７および図８に関して説明されるアルゴリズムのありとあらゆるステップは、ＰＣ（パーソナルコンピュータ）、ＤＳＰ（デジタル信号プロセッサ）、若しくはマイクロコントローラ等のプログラマブル計算機による命令セットまたはプログラムの実行により、ソフトウェアにおいて実施してもよく、またはＦＰＧＡ（フィールドプログラマブルゲートアレイ）若しくはＡＳＩＣ（特定用途向け集積回路）等の機械若しくは専用構成要素によりハードウェアにおいて実施し得る。
【００４５】
換言すれば、ノードＮＤは、図３、図５、および図６または図７および図８に関して以下に説明されるアルゴリズムのステップをノードＮＤに実行させる回路または回路を含む装置を含む。
【００４６】
図３、図５、および図６または図７および図８に関して以下に説明されるアルゴリズムのステップをノードＮＤに実行させる回路を含むそのような装置は、ノードＮＤに接続可能な外部装置であり得る。
【００４７】
図３は、本発明の第１の実現形態による、ノードによって実行されるアルゴリズムの一例を開示する。
【００４８】
本アルゴリズムは、中央装置として機能するノードＮＤ１のプロセッサ２００によって実行される一例において開示される。
【００４９】
ステップＳ３００において、プロセッサ２００は、ノードＮＤ１〜ＮＤ１６の集合内のモバイル端末の従属近傍関係を表すグラフを構築する。このグラフでは、あらゆるノードが頂点で表される。
２つのノードが近傍である場合、すなわち、１つのノードのＮＤのカバレッジ下の１つのモバイル端末が、他のノードＮＤからの強い干渉も受けている場合、２つの頂点は結ばれる。
ノード集合のグラフの構築は、ノード集合によってカバーされるエリアに現在位置されているモバイル端末および／またはノード集合によってカバーされるエリアに位置されていたモバイル端末によって報告される測定値に基づき得る。
例えば、測定値は、基準信号受信電力(Reference Signal Received Power)（ＲＳＲＰ）および／または基準信号受信品質(Reference Signal Received Quality)（ＲＳＲＱ）である。
【００５０】
ノード集合のグラフの構築は、各ノードＮＤ１〜ＮＤ１６のＲＡＭメモリ２０３に記憶される近傍関係表(neighbour relation tables)（ＮＲＴ）に基づき、本アルゴリズムを実行するノードＮＤ１に転送し得る。
【００５１】
ノード集合のグラフの構築は、モバイル端末によって報告される測定値と、近傍関係表とに基づき得る。
【００５２】
プロセッサ２００は、
１つのノードが他のノードの近傍関係表に属する場合、または
１つのノードによってサービングされる少なくとも１つのモバイル端末が、所定値、例えば−６ｄＢに等しい所定値よりも高い値で、他のノードの基準信号受信電力および／または基準信号受信品質を測定する場合、
２つのノード間にグラフのエッジを生成する。
少なくとも１つのモバイル端末は、
最大の基準信号受信電力および／または基準信号受信品質を有する１つまたは複数のモバイル端末であるか、
最小の基準信号受信電力および／または基準信号受信品質を有する１つまたは複数のモバイル端末であるか、または
ノード集合によってカバーされるエリア内の全てのモバイル端末であり得る。
【００５３】
プロセッサ２００は、各モバイル端末の信号対干渉雑音比（ＳＩＮＲ）値を推定し(extrapolating)、それを所定値と比較することにより、２つのノード間にグラフのエッジを生成する。
推定ＳＩＮＲ値は、ＲＳＲＰおよびＲＳＲＱ測定値に基づくことができ、２つのノードのうちの一方がエネルギー節減モードである場合に他方のノードで得られるＳＩＮＲを表現する。
ＳＩＮＲが所定値よりも高い場合、プロセッサ２００は２つのノード間にエッジを生成する。推定ＳＩＮＲ値は、ＲＳＲＰおよびＲＳＲＱ測定値と、２つのノードのうちの一方が電源投入されているとの仮定とに基づき得る。
ＳＩＮＲ損失が所定値よりも低い場合、プロセッサ２００は２つのノード間にエッジを生成する。
【００５４】
次のステップＳ３０１において、プロセッサ２００はノードの支配部分集合(dominating subset)を決定する。ノードの支配部分集合は、エネルギー節減モードに設定されないノードの集合である。ノードの部分集合に属さないノードは、エネルギー節減モードに設定されることが許可される。支配部分集合は、ステップＳ３００において生成されるグラフに基づいて、最小支配集合として計算し得る。
【００５５】
例えば、頂点ＶのグラフＧの支配部分集合Ｄは、Ｖ内のあらゆる頂点がＤに属するか、またはＤ内の頂点の近傍であるようなものである。換言すれば、支配部分集合Ｄ内のノードは、グラフＧの全ての頂点の近傍にある。
【００５６】
例えば、支配部分集合Ｄは、ステップＳ３００において生成されるグラフに基づいて、接続された最小の支配部分集合として計算し得る。接続された最小の支配集合は、最小サイズの支配部分集合である。接続された最小の支配部分集合の決定について、図５を参照してより詳細に開示する。
【００５７】
ノードの支配部分集合は、ステップＳ３００において生成されるグラフに基づいて、最大の独立集合として計算し得る。最大の独立集合は、任意の２つの頂点が隣接しない、すなわち、接続されない支配部分集合である。最大の独立部分集合の決定について、図５を参照してより詳細に開示する。
【００５８】
次のステップＳ３０２において、プロセッサ２００は、頂点が支配部分集合内にある全てのノードをアクティブモードに設定し、その他をエネルギー節減モードに設定する。
【００５９】
次のステップＳ３０３において、プロセッサ２００は、状態変更が必要であるか否かをチェックする。例えば、中央装置ノードは、ノードＮＤ１〜ＮＤ１６の集合のカバレッジエリア内のモバイル端末の進行中の通信に関連するトラフィックを監視している。平均トラフィックが所与の閾値を超える場合、中央装置は状態変更をトリガーする。
【００６０】
状態変更が検出される場合、プロセッサ２００はステップＳ３０４に移る。
【００６１】
ステップＳ３０４において、プロセッサ２００は、以前はエネルギー節減モードであったノードの部分集合をオンに設定する。すなわち、プロセッサ２００は、以前はエネルギー節減モードであったノードの部分集合、または以前はエネルギー節減モードであった全てのノードを非エネルギー節減モードに設定する。
【００６２】
その後、プロセッサ２００はステップＳ３０１に戻る。
【００６３】
図４は、本発明により構築されたグラフの一例を表す。
【００６４】
図４では、ノードＮＤ１〜ＮＤ１６の頂点およびステップＳ３００において決定される近傍ノードをリンクするエッジが示される。
【００６５】
ノードＮＤ１はノードＮＤ２、ＮＤ７、およびＮＤ６にリンクされる。
ノードＮＤ２は、ノードＮＤ１、ＮＤ４、ＮＤ５、ＮＤ６、およびＮＤ７にリンクされる。
ノードＮＤ３は、ノードＮＤ４、ＮＤ５、およびＮＤ８にリンクされる。
ノードＮＤ４は、ノードＮＤ２、ＮＤ３、およびＮＤ８にリンクされる。
ノードＮＤ５は、ノードＮＤ２、ＮＤ３、ＮＤ７、ＮＤ８、ＮＤ１０、およびＮＤ１１にリンクされる。
ノードＮＤ６は、ノードＮＤ１、ＮＤ２、ＮＤ７、ＮＤ９、およびＮＤ１０にリンクされる。
ノードＮＤ７は、ノードＮＤ１、ＮＤ２、ＮＤ４、ＮＤ６、ＮＤ９、ＮＤ１０、およびＮＤ１１にリンクされる。
ノードＮＤ８は、ノードＮＤ３、ＮＤ４、ＮＤ５、ＮＤ１１、およびＮＤ１２にリンクされる。
ノードＮＤ９は、ノードＮＤ６、ＮＤ７、ＮＤ１０、ＮＤ１３、およびＮＤ１６にリンクされる。
ノードＮＤ１０は、ノードＮＤ５、ＮＤ６、ＮＤ７、ＮＤ１１、ＮＤ１３、ＮＤ１５、およびＮＤ１６にリンクされる。
ノードＮＤ１１は、ノードＮＤ４、ＮＤ７、ＮＤ８、ＮＤ１０、ＮＤ１２、ＮＤ１３、ＮＤ１４、およびＮＤ１５にリンクされる。
ノードＮＤ１２は、ノードＮＤ８、ＮＤ１１、ＮＤ１４、およびＮＤ１５にリンクされる。
ノードＮＤ１３は、ノードＮＤ９、ＮＤ１０、ＮＤ１１、ＮＤ１５、およびＮＤ１６にリンクされる。
ノードＮＤ１４は、ノードＮＤ１１、ＮＤ１２、およびＮＤ１５にリンクされる。
ノードＮＤ１５は、ノードＮＤ１０、ＮＤ１１、ＮＤ１２、ＮＤ１３、およびＮＤ１４にリンクされる。
ノードＮＤ１６は、ノードＮＤ９、ＮＤ１０、およびＮＤ１３にリンクされる。
【００６６】
図５は、本発明の第１の実現形態による、支配部分集合を決定するためにノードによって実行されるアルゴリズムの第１の例を開示する。
【００６７】
本アルゴリアズムは、中央装置として機能するノードＮＤ１のプロセッサ２００によって実行される一例において開示される。
【００６８】
ステップＳ５００において、プロセッサ２００は、支配部分集合を空リストに初期化する。
【００６９】
次のステップＳ５０１において、プロセッサ２００は、最高メトリック値から最低メトリック値まで、メトリック値に従って頂点またはノードのリストをソートする。
【００７０】
メトリックは、初期メトリック値に設定され、例えば、ノードがリンクされる未処理ノードの数である。
【００７１】
図４の例によれば、ノードＮＤ１１は８つの未処理ノードにリンクされる。
ノードＮＤ７およびＮＤ１０は７つの未処理ノードにリンクされる。
ノードＮＤ５は、６つの未処理ノードにリンクされる。
ノードＮＤ２、ＮＤ６、ＮＤ８、ＮＤ９、ＮＤ１３およびＮＤ１５は、５つの未処理ノードにリンクされる。
ノードＮＤ１２は、４つの未処理ノードにリンクされる。
ノードＮＤ１、ＮＤ３、ＮＤ４、ＮＤ１４およびＮＤ１６は、３つの未処理ノードにリンクされる。
【００７２】
次のステップＳ５０２において、プロセッサ２００は、ステップＳ５０１において構築されたリストの最初のノードまたは頂点を支配部分集合に追加する。図４の例によれば、頂点またはノードＮＤ１１が支配部分集合に追加される。
【００７３】
次のステップＳ５０３において、プロセッサ２００は、支配部分集合に追加されたノードまたは頂点にリンクされている頂点またはノードを処理済みとしてマークする。ノードＮＤ４、ＮＤ７、ＮＤ８、ＮＤ１０、ＮＤ１２、ＮＤ１３、ＮＤ１４およびＮＤ１５は処理済みとマークされる。
【００７４】
次のステップＳ５０４において、プロセッサ２００は、全てのノードまたは頂点が処理されたか否かをチェックする。
【００７５】
全てのノードまたは頂点が処理された場合、プロセッサ２００は本アルゴリズムを中断する。その他の場合、プロセッサ２００はステップＳ５０５に移り、メトリックを再計算する。
【００７６】
図４の例によれば、ノードＮＤ７は５つの未処理ノードにリンクされる。
ノードＮＤ１０は４つの未処理ノードにリンクされる。
ノードＮＤ２、ＮＤ５、ＮＤ６、ＮＤ８およびＮＤ１３は、３つの未処理ノードにリンクされる。
ノードＮＤ１、ＮＤ４およびＮＤ９は２つの未処理ノードにリンクされる。
ノードＮＤ３、ＮＤ１２、ＮＤ１４、ＮＤ１５およびＮＤ１６は、１つの未処理ノードにリンクされる。
ノードＮＤ１１は、もはや未処理ノードにリンクされない。
【００７７】
プロセッサ２００は、ステップＳ５０５において構築されるリストの最初のノードまたは頂点を支配部分集合に追加する。図４の例によれば、頂点またはノードＮＤ７が支配部分集合に追加される。
【００７８】
次のステップＳ５０３において、プロセッサ２００は、支配部分集合に追加されたノードまたは頂点にリンクされている頂点またはノードを処理済みとしてマークする。
【００７９】
ノードＮＤ１、ＮＤ２、ＮＤ６、ＮＤ９およびＮＤ１１は処理済みとマークされる。
【００８０】
次のステップＳ５０４において、プロセッサ２００は、全てのノードまたは頂点が処理されたか否かをチェックし、ステップＳ５０５に移り、メトリックを再計算する。
【００８１】
ノードＮＤ８およびＮＤ１０は２つの未処理ノードにリンクされる。
ノードＮＤ２、ＮＤ３、ＮＤ４、ＮＤ５、ＮＤ９およびＮＤ１３は１つの未処理ノードにリンクされる。
ノードＮＤ１、ＮＤ６、ＮＤ７、ＮＤ１１、ＮＤ１２、ＮＤ１４、ＮＤ１５およびＮＤ１６は、もはや未処理ノードにリンクされない。
【００８２】
プロセッサ２００は、ステップＳ５０５において構築されたリストの最初のノードまたは頂点を支配部分集合に追加する。図４の例によれば、頂点またはノードＮＤ８が支配部分集合に追加される。
【００８３】
次のステップＳ５０３において、プロセッサ２００は、支配部分集合に追加されたノードまたは頂点にリンクされている頂点またはノードを処理済みとしてマークする。
【００８４】
ノードＮＤ３およびＮＤ５は、処理済みとマークされる。
【００８５】
次のステップＳ５０４において、プロセッサ２００は、全てのノードまたは頂点が処理されたか否かをチェックし、ステップＳ５０５に移り、メトリックを再計算する。
【００８６】
ノードＮＤ９、ＮＤ１０およびＮＤ１３は１つのみ処理ノードにリンクされる。他のノードはもはや未処理ノードにリンクされない。
【００８７】
プロセッサ２００は、ステップＳ５０５において構築されたリストの最初のノードまたは頂点を支配部分集合に追加する。図４の例によれば、頂点またはノードＮＤ９が支配部分集合に追加される。
【００８８】
次のステップＳ５０３において、プロセッサ２００は、支配部分集合に追加されたノードまたは頂点にリンクされている頂点またはノードを処理済みとしてマークする。
【００８９】
ノードＮＤ１６は処理済みとマークされる。
【００９０】
全ての頂点またはノードが処理されたため、プロセッサ２００は本アルゴリズムを中断する。
【００９１】
支配部分集合は、ノードＮＤ１１、ＮＤ７、ＮＤ８およびＮＤ９を含む。
【００９２】
図６は、本発明の第１の実現形態による、支配部分集合を決定するためにノードによって実行されるアルゴリズムの第２の例を開示する。
【００９３】
本アルゴリアズムは、中央装置として機能するノードＮＤ１のプロセッサ２００によって実行される一例において開示される。
【００９４】
ステップＳ６００において、プロセッサ２００は、支配部分集合を空リストに初期化する。
【００９５】
次のステップＳ６０１において、プロセッサ２００は、最高メトリック値から最低メトリック値まで、メトリック値に従って頂点またはノードのリストをソートする。
【００９６】
メトリックは、初期メトリック値に設定され、例えば、ノードがリンクされる未処理ノードの数である。
【００９７】
図４の例によれば、ノードＮＤ１１は８つの未処理ノードにリンクされる。
ノードＮＤ７およびＮＤ１０は７つの未処理ノードにリンクされる。
ノードＮＤ５は、６つの未処理ノードにリンクされる。
ノードＮＤ２、ＮＤ６、ＮＤ８、ＮＤ９、ＮＤ１３およびＮＤ１５は、５つの未処理ノードにリンクされる。
ノードＮＤ１２は、４つの未処理ノードにリンクされる。
ノードＮＤ１、ＮＤ３、ＮＤ４、ＮＤ１４およびＮＤ１６は、３つの未処理ノードにリンクされる。
【００９８】
次のステップＳ６０２において、プロセッサ２００は、ステップＳ６０１において構築されたリストの最初のノードまたは頂点を支配部分集合に追加する。図４の例によれば、頂点またはノードＮＤ１１が支配部分集合に追加される。
【００９９】
次のステップＳ６０３において、プロセッサ２００は、支配部分集合に追加されたノードまたは頂点にリンクされている頂点またはノードを処理済みとしてマークするとともに、支配部分集合に追加されたノードまたは頂点を処理済みとしてマークする。ノードＮＤ４、ＮＤ７、ＮＤ８、ＮＤ１０、ＮＤ１１、ＮＤ１２、ＮＤ１３、ＮＤ１４およびＮＤ１５は処理済みとマークされる。
【０１００】
次のステップＳ６０４において、プロセッサ２００は、全てのノードまたは頂点が処理されたか否かをチェックする。
【０１０１】
全てのノードまたは頂点が処理された場合、プロセッサ２００は本アルゴリズムを中断する。その他の場合、プロセッサ２００はステップＳ６０５に移り、未処理ノードにわたりメトリックを再計算する。
【０１０２】
図４の例によれば、ノードＮＤ２およびＮＤ６は３つの未処理ノードにリンクされる。
ノードＮＤ１、ＮＤ５およびＮＤ９は２つの未処理ノードにリンクされる。
ノードＮＤ３およびＮＤ１６は１つの未処理ノードにリンクされる。
【０１０３】
次のステップＳ６０２において、プロセッサ２００は、ステップＳ６０１において構築されたリストの最初のノードまたは頂点を支配部分集合に追加する。図４の例によれば、頂点またはノードＮＤ６が支配部分集合に追加される。
【０１０４】
次のステップＳ６０３において、プロセッサ２００は、支配部分集合に追加されたノードまたは頂点にリンクされている頂点またはノードを処理済みとしてマークするとともに、支配部分集合に追加されたノードまたは頂点を処理済みとしてマークする。ノードＮＤ１、ＮＤ２、ＮＤ６、およびＮＤ９は処理済みとマークされる。
【０１０５】
次のステップＳ６０４において、プロセッサ２００は、全てのノードまたは頂点が処理されたか否かをチェックする。
【０１０６】
全てのノードまたは頂点が処理された場合、プロセッサ２００は本アルゴリズムを中断する。その他の場合、プロセッサ２００はステップＳ６０５に移り、未処理ノードにわたりメトリックを再計算する。
【０１０７】
ノードＮＤ３およびＮＤ５は１つの未処理ノードにリンクされる。他のノードはもはや未処理ノードにリンクされない。
【０１０８】
次のステップＳ６０２において、プロセッサ２００は、ステップＳ６０１において構築されたリストの最初のノードまたは頂点を支配部分集合に追加する。頂点またはノードＮＤ３が支配部分集合に追加される。
【０１０９】
次のステップＳ６０３において、プロセッサ２００は、支配部分集合に追加されたノードまたは頂点にリンクされている頂点またはノードを処理済みとしてマークするとともに、支配部分集合に追加されたノードまたは頂点を処理済みとマークする。ノードＮＤ３およびＮＤ５は処理済みとマークされる。
【０１１０】
次のステップＳ６０４において、プロセッサ２００は、全てのノードまたは頂点が処理されたか否かをチェックする。
【０１１１】
全てのノードまたは頂点が処理された場合、プロセッサ２００は本アルゴリズムを中断する。その他の場合、プロセッサ２００はステップＳ６０５に移り、メトリックを再計算する。
【０１１２】
ノードＮＤ１３およびＮＤ９は１つの未処理ノードＮＤ１６にリンクされる。他のノードはもはや未処理ノードにリンクされない。
【０１１３】
次のステップＳ６０２において、プロセッサ２００は、ステップＳ６０１において構築されたリストの最初のノードまたは頂点を支配部分集合に追加する。頂点またはノードＮＤ１６が支配部分集合に追加される。
【０１１４】
次のステップＳ６０３において、プロセッサ２００は、支配部分集合に追加されたノードまたは頂点にリンクされている頂点またはノードを処理済みとしてマークするとともに、支配部分集合に追加されたノードまたは頂点を処理済みとマークする。ノードＮＤ１６は処理済みとマークされる。
【０１１５】
全ての頂点またはノードが処理されたため、プロセッサ２００は本アルゴリズムを中断する。
【０１１６】
支配部分集合は、ノードＮＤ１１、ＮＤ６、ＮＤ３、およびＮＤ１６を含む。
【０１１７】
図７は、本発明の第２の実現形態による、支配部分集合を決定するために各ノードによって実行されるアルゴリズムの第１の例を開示する。
【０１１８】
本アルゴリズムは、より精密には、各ノードのプロセッサ２００によって実行される。
【０１１９】
ステップＳ７００において、プロセッサ２００は、ランク１近傍リストと、ランク２近傍リストとを決定する。
ランク１近傍リストは、ノードによってカバーされるエリア内に現在位置されているモバイル端末および／またはノードによってカバーされるエリアに位置されていたモバイル端末によって報告される測定値で識別されるノードを含む。
例えば、測定値は基準信号受信電力(Reference Signal Received Power)（ＲＳＲＰ）および／または基準信号受信品質(Reference Signal Received Quality)（ＲＳＲＱ）である。
【０１２０】
例えば、ノードは、そのノードによってサービングされる少なくとも１つのモバイル端末が、例えば、−６ｄＢ等に等しい所定値よりも高い値で、他のノードの基準信号受信電力および／または基準信号受信品質を測定する場合に、ランク１近傍リスト内に入る。
少なくとも１つのモバイル端末は、最高の基準信号受信電力および／または基準信号受信品質を有する１つまたは複数のモバイル端末であるか、最小の基準信号受信電力および／または基準信号受信品質を有する１つまたは複数のモバイル端末であるか、またはノード集合によってカバーされるエリア内の全てのモバイル端末であり得る。
【０１２１】
例えば、プロセッサ２００は、ノードによってサービングされる各モバイル端末のＳＩＮＲ値を推定し、それを所定値と比較する。
推定ＳＩＮＲ値は、ＲＳＲＰおよびＲＳＲＱ測定値と、ランク１近傍リストに含まれ得るノードがエネルギー節減モードであるとの仮定とに基づき得る。
ＳＩＮＲが所定値よりも高い場合、プロセッサ２００はノードをランク１近傍リストに含める。
推定ＳＩＮＲ値は、ＲＳＲＰおよびＲＳＲＱ測定値と、ランク１近傍リストに含まれ得るノードが電源投入されているとの仮定とに基づき得る。
ＳＩＮＲ損失が所定値よりも低い場合、プロセッサ２００はノードをランク１近傍リストに含める。
【０１２２】
ランク２近傍リストは、ノードのランク１近傍リストに含まれる各ノードについて、ランク１の各近傍リストに含まれるノードを含む。
【０１２３】
次のステップＳ７０１において、プロセッサ２００は、支配ノードの部分集合を空に設定する。
【０１２４】
次のステップＳ７０２において、プロセッサは、ノードのランク１近傍リスト内で識別される各ノードへの、ノードのカラーを示すメッセージの転送を命令する。
ブラックノードは、ノードの支配部分集合に含まれるノードである。
グレーノードは、ノードの支配部分集合のうちのノードのランク１近傍リスト内にあるノード、すなわち、処理済みノードとマークされるノードである。
ホワイトノードは、本アルゴリズムによって処理されていないノードである。
【０１２５】
次のステップＳ７０３において、プロセッサ２００は、ノードのランク１近傍リストまたはランク２近傍リスト内で識別される各ノードへの、そのノードのランク１近傍リスト内で識別されるホワイトノードの数Ｗ（ｉ）を示すメッセージの転送を命令する。
【０１２６】
次のステップＳ７０４において、プロセッサ２００は、ノードのランク１近傍リストまたはランク２近傍リスト内で識別される各ノードからの、受信メッセージを送信したノードのランク１近傍リスト内で識別されるホワイトノードの数Ｗ（ｊ）を示すメッセージの受信を検出する。換言すれば、Ｗ（ｊ）は未処理近傍ノードの数である。
【０１２７】
次のステップＳ７０５において、プロセッサ２００は、ランク１近傍リスト内のホワイトノードの数Ｗ（ｉ）が、ステップＳ７０４において受信される数Ｗ（ｊ）の中で最大であるか否かをチェックする。
【０１２８】
ホワイトノードの数Ｗ（ｉ）が、ステップＳ７０４において受信される数Ｗ（ｊ）の中で最大である場合、プロセッサ２００はステップＳ７０６に移る。その他の場合、プロセッサ２００はステップＳ７０２に戻る。
【０１２９】
ステップＳ７０６において、プロセッサ２００は、ノードの支配部分集合に属するノードとしてノードを識別する。次に、そのノードはブラックノードになる。
【０１３０】
次のステップＳ７０７において、プロセッサ２００は、ランク１近傍リスト内で識別される各ノードをグレーノードとして、すなわち、処理済みノードとして設定する。
【０１３１】
次のステップＳ７０８において、プロセッサ２００は、ステップＳ７０４において受信されるメッセージを送信したノードのランク１近傍リスト内で識別されるホワイトノードの各数Ｗ（ｊ）がヌル値に等しいか否かをチェックする。
【０１３２】
各数Ｗ（ｊ）がヌル値に等しい場合、プロセッサ２００は本アルゴリズムを中断する。その他の場合、プロセッサ２００はステップＳ７０２に戻る。
【０１３３】
図８は、本発明の第２の実現形態による、支配部分集合を決定するために各ノードによって実行されるアルゴリズムの第２の例を開示する。
【０１３４】
本アルゴリズムは、より精密には、各ノードのプロセッサ２００によって実行される。
【０１３５】
ステップＳ８００において、プロセッサ２００は、ランク１近傍リストと、ランク２近傍リストとを決定する。
ランク１近傍リストは、ノードによってカバーされるエリア内に現在配置されているモバイル端末および／またはノードによってカバーされるエリアに配置されていたモバイル端末によって報告される測定値で識別されるノードを含む。
例えば、測定値は基準信号受信電力（ＲＳＲＰ）および／または基準信号受信品質（ＲＳＲＱ）である。
【０１３６】
例えば、ノードは、そのノードによってサービングされる少なくとも１つのモバイル端末が、例えば、−６ｄＢ等に等しい所定値よりも高い値で、他のノードの基準信号受信電力および／または基準信号受信品質を測定する場合に、ランク１近傍リスト内に入る。
少なくとも１つのモバイル端末は、最高の基準信号受信電力および／または基準信号受信品質を有する１つまたは複数のモバイル端末であるか、最小の基準信号受信電力および／または基準信号受信品質を有する１つまたは複数のモバイル端末であるか、またはノード集合によってカバーされるエリア内の全てのモバイル端末であり得る。
【０１３７】
例えば、プロセッサ２００は、ノードによってサービングされる各モバイル端末のＳＩＮＲ値を推定し、それを所定値と比較する。
推定ＳＩＮＲ値は、ＲＳＲＰおよびＲＳＲＱ測定値と、ランク１近傍リストに含まれ得るノードがエネルギー節減モードであるとの仮定とに基づき得る。
ＳＩＮＲが所定値よりも高い場合、プロセッサ２００はノードをランク１近傍リストに含める。
推定ＳＩＮＲ値は、ＲＳＲＰおよびＲＳＲＱ測定値と、ランク１近傍リストに含まれ得るノードが電源投入されているとの仮定とに基づき得る。
ＳＩＮＲ損失が所定値よりも低い場合、プロセッサ２００はノードをランク１近傍リストに含める。
【０１３８】
ランク２近傍リストは、ノードのランク１近傍リストに含まれる各ノードについて、ランク１の各近傍リストに含まれるノードを含む。
【０１３９】
次のステップＳ８０１において、プロセッサ２００は、支配ノードの部分集合を空に設定する。
【０１４０】
次のステップＳ８０２において、プロセッサは、ノードのランク１近傍リスト内で識別される各ノードへの、ノードのカラーを示すメッセージの転送を命令する。
ブラックノードは、ノードの支配部分集合に含まれるノードである。
グレーノードは、ノードの支配部分集合のうちのノードのランク１近傍リスト内にあるノード、すなわち、処理済みノードとマークされるノードである。
ホワイトノードは、本アルゴリズムによって処理されていないノードである。
【０１４１】
次のステップＳ８０３において、プロセッサ２００は、ノードのランク１近傍リストまたはランク２近傍リスト内で識別される各ノードへの、そのノードのランク１近傍リスト内で識別されるホワイトノードの数Ｗ（ｉ）を示すメッセージの転送を命令する。換言すれば、Ｗ（ｊ）は未処理近傍ノードの数である。
【０１４２】
次のステップＳ８０４において、プロセッサ２００は、ノードのランク１近傍リストまたはランク２近傍リスト内で識別される各ノードからの、受信メッセージを送信したノードのランク１近傍リスト内で識別されるホワイトノードの数Ｗ（ｊ）を示すメッセージの受信を検出する。
【０１４３】
次のステップＳ８０５において、プロセッサ２００は、ランク１近傍リスト内のホワイトノードの数Ｗ（ｉ）が、ステップＳ８０４において受信される数Ｗ（ｊ）の中で最大であるか否かをチェックする。
【０１４４】
ホワイトノードの数Ｗ（ｉ）が、ステップＳ８０４において受信される数Ｗ（ｊ）の中で最大である場合、プロセッサ２００はステップＳ８０６に移る。その他の場合、プロセッサ２００はステップＳ８０２に戻る。
【０１４５】
ステップＳ８０６において、プロセッサ２００は、ノードのランク１近傍リスト内で識別される少なくとも１つのノードがブラックノードであるか否かをチェックする。
【０１４６】
ノードのランク１近傍リスト内で識別される少なくとも１つのノードがブラックノードである場合、プロセッサ２００はステップＳ８０２に戻る。その他の場合、プロセッサ２００はステップＳ８０７に戻る。
【０１４７】
ステップＳ８０７において、プロセッサ２００は、そのノードを、ノードの支配部分集合に属するノードとして識別する。次に、そのノードはブラックノードになる。
【０１４８】
次のステップＳ８０８において、プロセッサ２００は、ランク１近傍リスト内で識別される各ノードをグレーノードとして、すなわち、処理済みノードとして設定する。
【０１４９】
次のステップＳ８０８において、プロセッサ２００は、ステップＳ８０４において受信されるメッセージを送信したノードのランク１近傍リスト内で識別されるホワイトノードの各数Ｗ（ｊ）が、ヌル値に等しいか否かをチェックする。
【０１５０】
各数Ｗ（ｊ）がヌル値に等しい場合、プロセッサ２００は本アルゴリズムを中断する。その他の場合、プロセッサ２００はステップＳ８０２に戻る。
【０１５１】
当然ながら、本発明の範囲から逸脱せずに、上述した本発明の実施形態に多くの変更を行うことができる。
【図１】
2015177543.tif 000003
【図２】
2015177543.tif 000004
【図３】
2015177543.tif 000005
【図４】
2015177543.tif 000006
【図５】
2015177543.tif 000007
【図６】
2015177543.tif 000008
【図７】
2015177543.tif 000009
【図８】
2015177543.tif 000010
【外国語明細書】
2015177543.tif 000011
2015177543.tif 000012
2015177543.tif 000013
2015177543.tif 000014
2015177543.tif 000015
2015177543.tif 000016
2015177543.tif 000017
2015177543.tif 000018
2015177543.tif 000019
2015177543.tif 000020
2015177543.tif 000021
2015177543.tif 000022
2015177543.tif 000023
2015177543.tif 000024
2015177543.tif 000025
2015177543.tif 000026
2015177543.tif 000027
2015177543.tif 000028
2015177543.tif 000029
2015177543.tif 000030
2015177543.tif 000031
2015177543.tif 000032
2015177543.tif 000033
2015177543.tif 000034
2015177543.tif 000035
2015177543.tif 000036
2015177543.tif 000037
2015177543.tif 000038
2015177543.tif 000039