(57)【要約】  いくつかのノード装置および基地局を含み、ルーティング計算機を有する無線通信システムであって、第１ルーティングマップで動作し、ルーティング計算機がノード装置間の通信に関するデータを収集し、ルート改善が示されているかどうか判定し、示されている場合は、ルーティング計算機が改善されたルーティングソリューションを生成し、（たとえば、現行のルーティングマップ／ソリューションを新規のもので置き換えることによって）最適化されたルーティングソリューションから生成された新規ルーティングマップを実施するために、命令が第１ルーティングマップを介してノード装置に配送される、無線通信システム。改善されたルーティングソリューションは、通信信頼性および／または効率、たとえば品質に関する、１つまたは複数の要因を考慮して最適化されてもよい。【選択図】図５
2009500962.tif 000002
【特許請求の範囲】
【請求項１】
いくつかのノード装置および少なくとも１つの基地局を含む無線通信システムであって、ルート計算機が前記通信システムに関連付けられ、前記システムが第１ルーティングマップで動作している間に、前記ルート計算機がノード装置間の通信に関するデータを収集し、ルート改善が示されているかどうか判定し、示されている場合は、前記ルート計算機が改善されたルーティングソリューションを生成し、前記改善されたルーティングソリューションから生成された新規ルーティングマップを実施するために、命令が前記第１ルーティングマップを介して前記ノード装置に関係させられる無線通信システム。
【請求項２】
前記基地局が前記ルート計算機を含む、請求項１に記載のシステム。
【請求項３】
新規ノードをさらに含み、前記新規ノードが追加された場合、前記新規ノードと宛先ノードとの間の少なくとも１つの通信ルートを決める分散方法が前記新規ノードを前記新規ルーティングマップに追加するために使用される、請求項１に記載のシステム。
【請求項４】
少なくとも第１および第２非オーバーラッピングルートが前記新規ノードと前記宛先ノードとの間で決められる、請求項２に記載のシステム。
【請求項５】
前記ルーティング計算機が、新規ノードが追加された後を含めて、複数の対のノード装置間の通信に関するデータを収集するステップと、ルート改善が定期的に必要かどうか判定するステップとを実施する、請求項１に記載のシステム。
【請求項６】
フル機能装置であるノードもあれば、機能を限定した装置であるノードもある、請求項１に記載のシステム。
【請求項７】
第１および第２非オーバーラッピングルートが機能を限定した装置と宛先ノードとの間で定義される、請求項６に記載のシステム。
【請求項８】
第１および第２非オーバーラッピングルートがフル機能装置と宛先ノードとの間で定義される、請求項６に記載のシステム。
【請求項９】
前記改善されたルーティングソリューションが、通信効率に関する１つまたは複数の要因を考慮して前記システムを最適化することによって生成された最適化されたソリューションである、請求項１に記載のシステム。
【請求項１０】
前記改善されたルーティングソリューションが通信の信頼性に関する１つまたは複数の要因を考慮して前記システムを最適化することによって生成された最適化されたソリューションである、請求項１に記載のシステム。
【請求項１１】
基地局およびいくつかのノード装置を含み、そのシステム内の装置間の通信リンクを使用する現行の通信構成で動作する無線通信システムを動作させる方法であって、
システム改善が示されているかどうか判定するステップと、
示されている場合は、改善されたシステム構成を生成するステップと、
前記改善されたシステム構成に関するデータを前記ノード装置に配送するステップと、
前記現行の通信構成を前記改善されたシステム構成で置き換えるステップと、
を含む方法。
【請求項１２】
前記現行の通信構成が、ノード装置を前記１つまたは複数の宛先ノードに接続する複数の通信ルートを含み、ノード装置ごとに、前記ノード装置と宛先ノードとの間に定義された少なくとも第１および第２非オーバーラッピング冗長パスがある、請求項１１に記載の方法。
【請求項１３】
システム改善が示されているかどうか判定する前記ステップが、新規デバイスが前記システムに追加されるたびに実施される、請求項１１に記載の方法。
【請求項１４】
システム改善が示されているかどうか判定する前記ステップが定期的に実施される、請求項１１に記載の方法。
【請求項１５】
システム改善が示されているかどうか判定する前記ステップが、前記現行の通信構成の品質を判定するために前記システム内の装置間の通信リンクの特徴を観察するステップと、前記システムのための改善された通信構成の品質を推定するステップと、前記現行の通信構成の前記品質を前記改善された通信構成の前記推定された品質と比較するステップとを含む、請求項１１に記載の方法。
【請求項１６】
前記改善された通信構成が、通信信頼性に関する要因を考慮して最適化される、請求項１５に記載の方法。
【請求項１７】
前記改善された通信構成が通信効率に関する要因を考慮して最適化される、請求項１５に記載の方法。
【請求項１８】
ルート計算機およびいくつかのノード装置を含む無線通信システムでの使用のためのノード装置であって、
前記ノード装置がメッセージを前記システム内の宛先ノードに宛てるためのルートを備えて構成されているかどうか判定し、そのように構成されていない場合は、発見プロトコルシーケンスであって、
ａ）前記宛先ノードへの配送を求める発見ルーティング要求を生成するステップと、
ｂ）メッセージを前記宛先ノードに宛てるための選択された通信ルートを示す前記発見ルーティング要求に関する前記ルート計算機からのルーティングメッセージを受信するステップと、
ｃ）前記発見プロトコルシーケンスを出て、前記選択された通信ルートを使用して将来のメッセージを前記宛先ノードにルーティングするステップと、
を含む発見プロトコルシーケンスに入る動作と、
前記ルート計算機に前記ノード装置によって到達可能なリンクの通信特徴を示す動作と、
前記発見プロトコルシーケンスにない場合は、前記ルート計算機から、計画された通信ルートを前記宛先ノードに示す前記通信特徴を使用して生成されたルーティングメッセージを受信し、前記計画された通信ルートを使用して将来のメッセージを前記宛先ノードにルーティングする動作と
を行うように構成されたノード装置。
【請求項１９】
基地局およびいくつかのノード装置を含む無線通信システムのためのルーティング計算機であって、
前記システム内の現行のルーティング機構を観察する動作と、
前記システム内の前記現行のルーティング機構に関する現行のメトリックを生成する動作と、
可能な改善されたシステム動作の推定に関する改善されたメトリックを生成する動作と、
システム改善が示されているかどうか判定するために前記動作中のメトリックを前記改善されたメトリックと比較する動作と、
示されている場合は、実際のルーティング機構を新規ルーティング機構で置き換えるためにメッセージを前記システム内の少なくとも１つのノード装置に配送する動作と、
を行うように構成されたルーティング計算機。
【請求項２０】
いくつかのノード装置および基地局を含む無線通信システムでの使用のための基地局であって、請求項１９に記載のルーティング計算機を含む基地局。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、参照により本明細書に組み込まれている、ＷＩＲＥＬＥＳＳ  ＲＯＵＴＩＮＧ  ＳＹＳＴＥＭＳ  ＡＮＤ  ＭＥＴＨＯＤＳという名称の米国特許出願第１０／９０５，９７１号の一部継続出願である。
【０００２】
本発明は、無線ネットワーキングの分野に関する。より詳細には、本発明は、無線ネットワーキング通信プロトコルおよびそれらの実施に関する。
【背景技術】
【０００３】
無線通信システムは、情報を第１装置から第２装置に移すためにルーティングプロトコルを利用する。そのようなシステムでは、無線通信システムを第２通信システムに接続する１つまたは複数の基地局（ルートノードまたはゲートウェイを含めて様々な用語が使用される）が存在することが多い。１つの例は、無線システムと有線システムとの間の中間物（中継装置）として働くアクセスポイントである。無線システムにおけるその他の装置は、基地局ノードに到達すべきデータをどのようにルーティングするか決めなければならない。
【０００４】
装置の信頼できる送信範囲は基地局ノードを含まないこともあるので、ルーティング戦略は中間装置を利用することが多い。たとえば、図１に示されているように、装置Ｘは通信範囲ＲＸを有し、装置Ｙは通信範囲ＲＹを有し、基地局装置Ｂは通信範囲ＲＢを有する。無線ネットワークにこれら３つの装置しか含まれていない場合は、ソリューションは簡単である。すなわち、ＸがＢに送信すべきデータを有する場合、ＸはＹにデータを送信し、ＹはＢにデータを送信する。しかし、より多くの装置が追加されるにつれて、ルーティングソリューションはより複雑になる。
【発明の開示】
【課題を解決するための手段】
【０００５】
本発明は、第１の例示的実施形態では、いくつかのノード装置および基地局を含む無線通信システムを含み、該システムは第１ルーティングマップで動作し、ルート計算機が複数の対のノード装置間の通信に関するデータを収集するために使用され、ルーティング改善が示されているかどうか判定し、示されている場合は、ルート計算機が改善されたルーティングソリューションを生成し、改善されたルーティングソリューションから生成された新規ルーティングマップを実施するために、命令が第１ルーティングマップを介してノード装置に中継される。基地局は、ルート計算機でもよく、あるいはソフトウェアまたはハードウェア要素としてルート計算機を含んでもよい。いくつかの実施形態では、１つまたは複数の要因を考慮して最適化されたルーティングソリューションを使用して、改善されたルーティングソリューションが生成されてもよい。
【０００６】
他の例示的実施形態では、本発明は、無線通信システムを動作させる方法で実施され、無線通信システムは基地局およびいくつかのノード装置を含み、そのシステム内の複数の対の装置間の通信リンクを使用する現行の通信構成で動作する。例示的方法は、システムのルーティング改善が示されているかどうか判定するステップと、示されている場合は、改善されたシステム構成を生成するステップと、改善されたシステム構成に関するデータをノード装置に配送するステップと、現行の通信構成を改善されたシステム構成で置き換えるステップとを含む。
【発明を実施するための最良の形態】
【０００７】
以下の詳細な説明は図面を参照しながら読まれるべきである。必ずしも比例しているとは限らない図面は、例示的実施形態を示し、本発明の範囲を限定することを意図するものではない。
【０００８】
ＷＩＲＥＬＥＳＳ  ＲＯＵＴＩＮＧ  ＳＹＳＴＥＭＳ  ＡＮＤ  ＭＥＴＨＯＤＳという名称の米国特許出願第１０／９０５，９７１号が参照により本明細書に組み込まれている。第１０／９０５，９７１号特許出願に記載されている方法のいくつかは、既存の通信システムのベンチマーキングおよび既存のシステムの通信プロトコル／ルートに対応できる。既存のシステム接続および通信ルートに関するデータが収集されてもよく、次いで改善されたネットワークソリューションが既存のシステムとの比較のために生成されてもよい。既存のシステムソリューションおよび改善されたシステムソリューションのためのメトリックが生成され、比較されてもよい。次いで、中心的に生成された通信プロトコルを使用する再構成が適切であるかどうかが判定されてもよい。いくつかの実施形態では、本発明は、新規に生成されたソリューションの実施を含む。いくつかの実施形態では、改善されたソリューションが、通信のセキュリティ、効率および／または信頼性に関する１つまたは複数の要因を考慮して最適化されてもよい。
【０００９】
例示的一実施形態では、いくつかの装置を有する無線ネットワークが提供される。良くないデータルーティングは、そのようなネットワークの応答時間を増大する可能性があり、そのようなネットワークを限られた数の装置への過剰依存に対して脆弱にする。たとえば、データが重点的に１つまたは２つのノードを通してルーティングされた場合、これらのノードは、基地局へのデータ移動に対して隘路を形成し、遅延を引き起こす可能性がある。さらに、重点的に使用されたノードの障害が重大なデータ損失につながる可能性がある。
【００１０】
そのようなネットワークの中のデータルーティングの設計および選択は、データルーティングが静的（非移動）装置を有するネットワークの中で行われる場合でも、それらのネットワークの分散性のために複雑になる。いかなる所与の時間にでも、ネットワークの一部である１つまたは複数の装置が、いかなる理由ででも、ネットワークの残部との接続を失う可能性がある。たとえば、突然生じたローカルノイズが、装置との通信を遮断する可能性があり、装置が定期的に低電力スリープモードに入ることもある。さらに、ネットワークを、初期セットアップ後に装置を追加することができるようにしておくことが望ましいことも多い。
【００１１】
これらの様々な問題の１つの結果は、データルーティングの集中構成が、手間がかかって面倒になることである。たとえば、集中構成は、装置が永続的にまたは一時的に追加または除去されたときに更新を必要とする可能性がある。集中構成を更新することは、ネットワーク内の各装置に個別にコンタクトすることを必要とする可能性がある。これらの問題は、動作進行中は、分散構成を望ましい特徴にする。しかし、分散構成は集中構成ほど効率のよい結果を出すことができないことがシミュレーションで判明している。
【００１２】
本明細書では、目的の規格を使用してシステム通信の効率が前のソリューションより良くなった場合は、ルーティングソリューションが改善されたと述べられてもよい。たとえば、改善されたソリューションが、その全ルーティングマップにおいて別のソリューションより少ないデータホップを有してもよい。選択されてもよいいくつかの要因、たとえば、ホップ数、ノード待ち時間、および受信された信号強度インジケータがある。さらに、これらの要因は、平均または中央値システムレベル、最高レベル、対数加算などを含めて、いくつかの方式で考察される。したがって、特定の要因およびその要因を分析する特定の方式の選択は、様々であり得る。いくつかの改善されたソリューションは、１つまたは複数のそのような要因を利用する最適化されたソリューションでもよい。たとえば、同時係属中の米国特許出願第１０／９０５，９７１号に記載されているように、いくつかの要因が、考察される要因のために最適化されるソリューションを見つけるために線形プログラミング法が使用されることができる加重和とみなされてもよい。そのような最適化は、複数の層、すなわち、考察される要因、各要因が考察されるフォーマット、および様々な要因に与えられる重みを有してもよい。
【００１３】
以下の例示的実施例のいくつかは、ルーティング計算機の包含に関係する。ルーティング計算機は、ソフトウェアまたはその他の命令セットの一部分として、あるいは、所望された場合は、基地局ノードを含めて、通信ネットワークの任意のノード内のハードウェアの中で、実施されてもよいことが理解されるべきである。さらに、ルーティング計算機はまた、普通は通信ネットワークの一部分ではない個別の装置において、たとえば、構成装置、更新装置、または最適化装置の一部分として、実施されてもよい。
【００１４】
図２は、無線ネットワークにおける非オーバーラッピング冗長ルートの図である。このネットワークは、基地局Ｂ、ならびにいくつかのノードＩ１．．．Ｉ６およびＸを含んで示されている。この例示的実施形態では、目的は、各装置と基地局Ｂとの間の強靭な通信を提供することである。非オーバーラッピング冗長ルートを定義することは、そのような目的を達成する１つの方法である。第１ルート１は、ＸとＢとの間で定義され、奇数番号のノードＩ５、Ｉ３、およびＩ１を通る。第２ルート２は、ＸとＢとの間で定義され、偶数番号のノードＩ６、Ｉ４、およびＩ２を通る。２つのルート１、２は、オーバーラップせず、したがって、非オーバーラッピング冗長ルートである。任意のノードから他の任意のノードに行く追加のルートが定義されてもよく、ノードと基地局との間でだけでなくてもよい。ルートは、一般に、宛先ノードに向けられるかまたは宛てられ、基地局は、いくつかのシステムでは、いくつかの可能な宛先ノードのうちの１つだけである。
【００１５】
また、Ｉ５からＢへの冗長を生成するために追加のルートが示されている。第１ルートがルート１を辿り、ルート３として示され、Ｉ５のための別のルートがルート４を辿りＩ４およびＩ２を通る。同様に、ノードＩ６のためにルート５がルート２の一部分を辿り、ルート６がノードＩ３およびＩ１を通る。図から分かるように、比較的少ないノードまたは装置の場合でも、特に非オーバーラッピング冗長パスが所望される場合は、パスの数はすぐに増える。いくつかの実施形態では、装置Ｘは、その他のノード装置Ｉ１．．．Ｉ６と同様の方式で動作する装置である。他の実施形態では、そうではなく、たとえば以下で図６においてさらに示されているように、装置Ｘは、ノード装置とは異なるタイプの装置でもよい。たとえば、いくつかのノード装置はフル機能装置（ＦＦＤ）でもよく、装置Ｘはアプリケーションに応じて、ＦＤＤ、または機能を限定した装置（ＲＦＤ）のいずれでもよい。
【００１６】
図３は、装置Ｋのためのルートの分散構成を示す図である。この例示的実施形態では、Ｋは、他の装置Ｌ、Ｍ、Ｎ、Ｐ、Ｑ、Ｒ、Ｓ、および基地局ＢＳをすでに有するシステムに新規に追加された装置でもよい。装置Ｋはまた、システムの一部分であったが、今は、たとえば、低電力スリープ期間の後で、または接触を妨害する干渉（ノイズ）の期間の後で、システムとの接触を再確立している装置でもよい。装置Ｋはまた、たとえば、他の装置がシステムに追加またはシステムから除去された後で、再構成ルーティングに対するコマンドを考慮してそれ自体を再構成してもよい。
【００１７】
Ｋを追加するための分散構成は、次のとおり行われてもよい。Ｋが、それ自体のアドレスＫを伴うルーティング要求ＲＲＥＱを生成し、メッセージ「ＲＲＥＱＫ」を作成する。隣接する装置Ｌ、ＰがＫからルーティング要求を受信した場合、それぞれがメッセージにそれ自体のアドレスを含めた後で、そのメッセージを再送信する。また、他の情報、たとえば、ＲＳＳＩデータ（受信された信号長インジケータ）、他のリンク品質データ、またはノード待ち時間データ（この例示的実施形態では、ノード待ち時間は、ノードによってサービスされるルートの数に比例する）が追加されてもよい。ノード待ち時間データは任意の適切な形を取ってもよい。他の実施例では、ノード待ち時間データは、いくつかのノードまたは各ノードにそのノードにおけるデータ（またはデータのパケット）の常駐時間に関する統計値を保持させることによって生成されることができる。他の実施例では、ノードごとの待ち時間値は、平均常駐時間、あるいは常駐時間のセットまたは分布に関する別の統計値またはメトリックでもよい。たとえば、装置が常に「ＯＮ」であるとは限らない（たとえば、ときどきスリープモードに入る）、生じる可能性のある断続的通信障害に適応するために、収集されたデータは、通信リンク障害のインジケータおよびそのような障害の頻度を含んでもよい。
【００１８】
次いで、ＲＲＥＱが宛先、この場合は基地局ＢＳ、に到達するまで、メッセージが繰り返される。図示されているように、基地局がＫから複数のＲＲＥＱを受信してもよく、この場合、ＲＲＥＱＮＭＬＫが、Ｋによって生成された後、ノードＬ、Ｍ、およびＮを通過し、その後、ＢＳによって受信される。同様に、ＲＲＥＱＳＲＱＰＫが生成された後、ノードＰ、Ｑ、Ｒ、およびＳを通過し、その後、ＢＳによって受信される。次いで、基地局ＢＳがメッセージをすべてソートし、明らかに最良のルートを選択する。通常、「最良の」ルートは、最良のリンク強度および最少のホップ数を有するルートと判定される。基地局に最良のルートを選択させる際に考慮されてもよい他の要因は、ＫとＢＳとの間の中間ノードのうちのいずれかの「負荷」を含む。たとえば、高負荷中間ノード（多数の他の既存のルートの一部分をすでに形成するノード）を含むルートは、高負荷ノードにおけるデータ衝突を避けるために除外されてもよい。
【００１９】
ＢＳが「最良の」ルート（または、いくつかの実施形態で、２つ以上の最良のルート）を選択した後で、ＢＳによってメッセージが生成され、Ｋにどのルート（１つまたは複数）が使用されるべきかを示すためにＫに宛てられる。いくつかの実施形態では、基地局ＢＳが、メッセージがＢＳによって直接Ｋに送信されることができるように、すべての他のノードにブロードキャストすることができるようにされる。他の実施形態では、ＢＳが中間装置を使用してメッセージをＫにルーティングしてもよい。分散構成は、新規装置が追加された場合、他の既存の通信ルートが同じままであるので、通常、ネットワークの中の通信にあまり干渉せずに実施されることができる。
【００２０】
図３では、２つの非オーバーラッピング冗長パスが、Ｋが基地局ＢＳに到達するように定義されていることが分かる。１つのパスは、シリーズＫ−Ｌ−Ｍ−Ｎ−ＢＳを辿る。もう１つのパスは、シリーズＫ−Ｐ−Ｑ−Ｒ−Ｓ−ＢＳを辿る。これらのパスは、異なる長さを有し、しばしば、異なるホップ数を有するとみなされる。中間局（１つの場合ではＬ、Ｍ、およびＮ、もう１つの場合ではＰ、Ｑ、Ｒ、およびＳ）のいずれか１つによって担持される最大負荷は、ルートが変わるごとに異なる可能性がある。パス内の各リンクは、異なる信号長を有してもよい。パス内の各ノードは、そこを通過するルートの数が関係する限り、異なる負荷を担持してもよい。これらの要因のそれぞれは、たとえば、データがＢＳに到達するのに必要な時間の量を変えることによって、または１つのルートがそのシステムで使用される他のルートにどのような影響を与えるかによって、システム性能に影響を与え得る。
【００２１】
図４は、改善および／または最適化が示されているかどうか判定するためにシステム性能を分析する例示的方法の流れ図である。方法１０は、ステップ２０で示されているように、既存の無線システム内のリンク間のリンク特徴を観察することから始まる。既存のシステムは、たとえば、通信ルートに分散方式で少なくともいくつかのノードが追加され提供されたシステムでもよい。他のステップでは、ステップ２２で示されているように、改善されたソリューションが生成される。
【００２２】
例示的一実施形態では、同時係属中の米国特許出願第１０／９０５，９７１号にさらに記載されているように、改善されたソリューションが混合整数線形プログラムのプロセスによって生成される。この例示的実施形態では、次いで、図４のステップ２４で示されているように、１つまたは複数の要因が、改善されたソリューションから第１品質メトリックを生成するために使用される。このメトリックは、たとえば、数でもよい。次に、ステップ２６で示されているように、システムの実際のルーティング特徴が観察される。ステップ２８で示されているように、第２品質メトリックが実際のルーティング特徴を利用して生成される。最後に、ステップ３０で示されているように、第１品質メトリックと第２品質メトリックが比較される。
【００２３】
例示的システムでは、第１品質メトリックと第２品質メトリックの比較が所望の利得になる再構成を示す場合、再構成が行われてもよい。たとえば、第１品質メトリックが第２品質メトリックの予め選択されたパーセンテージ（たとえば、７５％、またはその他の任意の値）より小さい場合は、再構成を実施するために必要とされる計算および通信費用が正当化されるような対応する改善のレベル（たとえば、２５％）が再構成から予期され得る。
【００２４】
本方法は、ルート計算機の動作によって実施されてもよい。ルート計算機は、基地局、通信システム内のノードのうちの１つ、または完全に別個の装置のソフトウェアまたはハードウェア機能でもよい。
【００２５】
一例示的方法では、インフラストラクチャノードは、ノード間の比較対置およびリンクの強さを含めて、それらの物理的特徴の点で特徴付けられる。グラフが、頂点集合が基地局を含めてすべてのノードの集合であるＧ（Ｖ，Ｅ）と定義されることができる。グラフの辺は、頂点間の通信接続性を示す有向辺である。たとえば、頂点Ａと頂点Ｂとの間に有向辺がある場合、ＡからＢへの可能な通信がある。次いで、基地局への２つ（またはそれ以上）の最良の非オーバーラッピングパスが選択される。上記の要因（および／または、所望に応じて、その他の要因）を考慮したグラフィカルな分析が、（選択された要因および／または重みに関して）最適のソリューションがアプローチされることができるようにする。
【００２６】
図５は、改善されたルーティング構成を実施する例示的方法をブロック形式で示す。図５に示されている方法は、やはり、ルート計算機の動作によって行われる。ルート計算機は、基地局、通信システム内のノードのうちの１つ、または完全に別個の装置のソフトウェアまたはハードウェア機能でもよい。
【００２７】
本方法は、いくつかのノードならびに基地局の間で通常の通信が行われる稼働状態４０のシステムから始まる。ときどき、新規装置のチェック４２が行われる。システム内で新規装置が検出された場合は、本方法は、ステップ４４で示されているように、新規装置を追加するためのルーチンを行うことによって継続する。このルーチンは、たとえば、図３に関して上記で説明された分散ルーチンを含む任意の適切な装置追加ルーチンでもよい。ステップ４４で新規装置が追加された後で、本方法は、ステップ４６で示されているように、システムデータを収集することから始まる改善ルーチンに入る。ステップ４２で示されている新規装置がない場合は、本方法は、ステップ４８で示されているように、システム構成の定期的更新の時であるかどうかチェックするステップを含んでもよい。そうであれば、再度、ステップ４６で示されているように、システムデータを収集することから始まる改善ルーチンに行く。そうでなければ、制御は稼働状態４０に戻る。
【００２８】
本方法は、システムデータを使用して、ステップ５０で示されているように、改善が適切か、または必要か判定してもよい。たとえば、同時係属中の米国特許出願第１０／９０５，９７１号で論じられている方法が、改善が適切かどうか判定するために使用されてもよい。改善が適切でない場合は、本方法は、稼働状態４０に戻る。
【００２９】
改善が適切であった場合は、本方法は、ステップ５２で示されているように、改善されたソリューションを確定することによって継続する。改善されたソリューションを生成するために、いかなる適切な要因が使用されてもよい。たとえば、ノード待ち時間の比例した積および平均信号強度が、改善されたソリューションを見つけるために最適化されたメトリックでもよい。他の実施例では、ノード待ち時間に関する比例したメトリック、パスの長さ、リンク品質、および最大ノード負荷の組合せが考慮され最適化されてもよい。
【００３０】
改善されたソリューションを与えられれば、次のステップは、ステップ５２で示されているように、新規ソリューションを配送することである。新規ソリューションは、既存の通信マッピングまたはパスの定義を使用して配送されてもよい。代替として、そのような性能を与えられたシステムでは、新規ソリューションがブロードキャスト信号によって配送されてもよい。いくつかの実施形態では、既存の、すなわち「古い」ソリューションが、新規ソリューションがネットワークノードに配送されることができるまで、使用される。そのように配送された後は、次のステップは、ステップ５４で示されているように、古いルートに関する古いルーティングマップ、プリファレンス、および／またはアドレッシングプロトコルを新規ソリューションのために構成された要素で置き換えることによって実施することである。
【００３１】
図５の方法に示されているように、例示的方法は、新規装置を追加する第１方式が、新規装置が基地局ノードまでネットワークを横断するメッセージを送信する分散法によってであり、ルーティングテーブルが、発見された最良の利用可能なルート（１つまたは複数）を使用して簡単に更新されるアプローチを採用する。いくつかの実施形態では、「最良の」利用可能なルートが追加の要因を使用して定義される。たとえば、短期間にいくつかの新規装置が追加された場合、既存のルートを再使用するのではなく、基地局ノードへのホップのために新規に追加された装置を使用することにプリファレンスが与えられてもよい。これは、いくつかの実施形態では、可能な限り最大限まで実施されてもよい。他の実施例では、（通信ホップの数、品質、待ち時間などの選択された要因（１つまたは複数）の点から見て）新規装置の間で基地局ノードに「最も近い」装置に到達するためにいくつかのホップが利用できるように新規装置が追加されてもよく、残りすべての新規装置からの通信は、「最も近い」ノード装置にルーティングされ、そこから他の既存のルートを通してルーティングされてもよい。
【００３２】
本発明のコンテキストの中で、ルーティングに対する集中アプローチは、改善されたソリューションのカテゴリとみなされることができる。「最適の」アプローチを生成するにはいくつかの要因が関与するので、実際には、単一の「最適の」ルーティングアプローチはめったにないことが理解されるべきである。そうではなく、通信品質に関する１つまたは複数の要因の点から見て最適化されてもよい改善された通信ソリューションがある。
【００３３】
図６は、例示的無線センサネットワークを示す。このネットワークは、ゲートウェイノードまたは基地局ノード１００、いくつかのインフラストラクチャノード１０２、１０４、１０６、１０８、１１０、１１２、およびセンサＳとして示されているいくつかのリーフノードを含む。例示的実施例では、どの１つのインフラストラクチャノードの障害もセンサをネットワークから完全には切断しないように、各センサはそれ自体２つのインフラストラクチャノードに関連している。いくつかの実施形態では、ネットワークが、その開示が参照により本明細書に組み込まれている、２００４年６月１７日に出願された、ＷＩＲＥＬＥＳＳ  ＣＯＭＭＵＮＩＣＡＴＩＯＮ  ＳＹＳＴＥＭ  ＷＩＴＨ  ＣＨＡＮＮＥＬ  ＨＯＰＰＩＮＧ  ＡＮＤ  ＲＥＤＵＮＤＡＮＴ  ＣＯＮＮＥＣＴＩＶＩＴＹという名称の、同時係属中の米国特許出願第１０／８７０，２９５号に記載されている形を取る。他の実施形態では、センサＳは機能を限定した装置（ＲＦＤ）とみなされてもよく、一方、インフラストラクチャノード１０２、１０４、１０６、１０８、１１０、１１２はフル機能装置（ＦＦＤ）とみなされる。ＲＦＤおよびＦＦＤ装置はまた、他のプロトコル、たとえば、ＩＥＥＥ８０２．１５．４に基づくＺｉｇｂｅｅプロトコルに従って対話してもよい。
【００３４】
一実施形態では、センサのうちの少なくともいくつかが低電力モードで動作する。たとえば、所与のセンサがアクティブモードおよび低電力スリープモードを有してもよく、センサは定期的に低電力スリープから目覚めてアクティブモードを使用してデータを送信する。低電力スリープの間、センサは通信のために利用できない。スケジュールされた時間に、センサは目覚めてもよく、関連するインフラストラクチャノードへの送信のために収集したいかなるデータも送信する。次に、インフラストラクチャノードがそのセンサデータを基地局に送信する。
【００３５】
冗長のために、センサが２つのインフラストラクチャノードに送信してもよい。たとえば、いくつかのセンサ１１４、１１６、１１８がインフラストラクチャノード１０４、１０６のそれぞれに関連して示されている。いくつかの実施形態では、システムが、インフラストラクチャノード１０４、１０６を通過するこれらのセンサ１１４、１１６、１１８からの信号のためのルートが非オーバーラッピングであるように構成される。たとえば、第１センサ１１４からの信号が、インフラストラクチャノード１０４および１１０に、次いで基地局ノード１００に、またインフラストラクチャノード１０６にも、次いで基地局ノード１００にルーティングされてもよい。一方、第２センサ１１６からの信号が同じ対のルートを有してもよい。図示されているシステムから、ノード１０２はいくつかのセンサ送信のために使用される可能性があることが分かる。システムの全体の待ち時間を低減するために、ノード１０２を通ってルーティングされる可能性のあるいくつかのデータがノード１０２のまわりにルーティングされてもよい。したがって、センサ１１８などのデータは、インフラストラクチャノード１０４および１１０にルーティングされてから基地局ノード１００にルーティングされてもよく、また、まずノード１０６、１０８、および１１２に進むことによってノード１０２のまわりにルーティングされてから、基地局ノード１００に行ってもよい。
【００３６】
ルーティングに対する分散アプローチで生じる可能性のある問題の１つをハイライトするために、システムにセンサ１２０が追加されたと仮定する。図から分かるように、センサ１２０は、ノード１０２および１０８との関連が望ましいように配置される。センサ１２０は、ノード１０６との通信のためにも十分近くてもよいが、明らかにノード１０２のほうが近い。しかし、センサ１２０がシステムに追加された最も新しいセンサであれば、ノード１０２はすでにシステムの最も重いルーティング負荷を担持している可能性がある。ノード１０２がすでに負荷をルーティングするための立場にある場合、ノード１０２は、センサ１２０からの信号をルーティングするために利用することはできない。これはセンサ１２０がノード１０６および１０８と関連することを必要とし、センサ１２０からノード１０６に行く信号は、まずノード１０４および１１０に再送信されてから基地局ノード１００に到達する。その結果は効率が悪い。しかし、新規センサが追加されるたびに、センサが除去されるたびに、センサがその関連するインフラストラクチャノードとの通信を失うたびに、そして、通信を失ったセンサが通信を再取得するたびに、また、インフラストラクチャノードが追加され、除去され、または通信を失い、再取得するたびに、全ルーティングテーブルを再構成することは、構成信号をルーティングする雑音を生成する可能性がある。したがって、本発明によって、必要な場合は、図５に示されている方法で例示的に決められたように、改善されたソリューションが実施されることができる。
【００３７】
実際の性能が所望の閾値より低くなったときは、システムは、集中方式または分散方式のいずれかの方式で再構成されることができる。たとえば、上記で図４に関して説明されたようにメトリックが生成された場合、かつ、実際のシステムメトリックが、予め決められた量だけ、改善されたスコアより悪いスコアを示した場合、システムが再構成されてもよい。本明細書で使用されるように、そのような決定は、再構成が通信システムの特徴によって示されるということの発見として特徴付けることができる。
【００３８】
システム内の装置のうちのいずれの装置が本発明に関する分析を行うようにプログラムされてもよい。たとえば、基地局が分析を行ってもよい。代替として、別個の装置がそのような分析を行うためにシステムに通信可能に結合されてもよい。所望された場合は、基地局がシステム性能データを収集し、そのデータを、システムの一部分ではない別の装置（たとえば、基地局によってアクセス可能な有線ネットワークを使用してアクセス可能な装置）に送信してもよい。改善されたソリューションは追加の計算機能を必要とする可能性があるので、性能データをシステムの外の別個の装置に送信する能力が、システムが動作している間でもシステム分析が生じることができるようにするのを助けることができる。
【００３９】
本発明は、本明細書に記載され企図された特定の実施形態以外の様々な形態で明示されてもよいことを当業者は理解するであろう。したがって、添付の特許請求の範囲に記載の本発明の範囲および趣旨から逸脱することなく、形態および詳細における逸脱がなされてもよい。
【図面の簡単な説明】
【００４０】
【図１】通信範囲を示す無線ネットワークの図である。
【図２】無線ネットワークにおける非オーバーラッピング冗長ルートの図である。
【図３】装置Ａのためのルートの分散構成を示す図である。
【図４】例示的ルーティング改善方法の流れ図である。
【図５】例示的一実施形態の流れ図である。
【図６】無線センサネットワークを示す図である。
【図１】
2009500962.tif 000003
【図２】
2009500962.tif 000004
【図３】
2009500962.tif 000005
【図４】
2009500962.tif 000006
【図５】
2009500962.tif 000007
【図６】
2009500962.tif 000008
【手続補正書】
【提出日】平成20年3月11日(2008.3.11)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
１つまたは複数の宛先ノード（１００）およびいくつかのノード装置（１０２、１０４、１０６、１０８、１１０、１１２、１１４、１１６、１１８、１２０）を含み、そのシステム内の装置間の通信リンク（１、２、３、４、５、６）を使用する現行の通信構成で動作する無線通信システムを動作させる方法であって、
システム改善が示されているかどうか判定するステップと、
示されている場合は、改善されたシステム構成を生成するステップと、
前記改善されたシステム構成に関するデータを前記ノード装置（１０２、１０４、１０６、１０８、１１０、１１２、１１４、１１６、１１８、１２０）に配送するステップと、
前記現行の通信構成を前記改善されたシステム構成で置き換えるステップと、
を含む方法。
【請求項２】
無線通信システムであって、
いくつかのノード装置（１０２、１０４、１０６、１０８、１１０、１１２、１１４、１１６、１１８、１２０）および少なくとも１つの基地局（１００）であって、ルート計算機が前記通信システムに関連付けられ、前記システムが第１ルーティングマップで動作している間に、前記ルート計算機が前記ノード装置（１０２、１０４、１０６、１０８、１１０、１１２、１１４、１１６、１１８、１２０）間の通信に関するデータを収集し、ルート改善が示されているかどうか判定し、示されている場合は、前記ルート計算機が改善されたルーティングソリューションを生成し、前記改善されたルーティングソリューションから生成された新規ルーティングマップを実施するために、命令が前記第１ルーティングマップを介して前記ノード装置（１０２、１０４、１０６、１０８、１１０、１１２、１１４、１１６、１１８、１２０）に関係させられる、いくつかのノード装置（１０２、１０４、１０６、１０８、１１０、１１２、１１４、１１６、１１８、１２０）および少なくとも１つの基地局（１００）と、
新規ノードと
を含み、前記新規ノードが追加された場合、前記新規ノードと宛先ノードとの間の少なくとも１つの通信ルートを決める分散方法が前記新規ノードを前記新規ルーティングマップに追加するために使用される無線通信システム。
【請求項３】
ルート計算機およびいくつかのノード装置（１０２、１０４、１０６、１０８、１１０、１１２、１１４、１１６、１１８、１２０）を含む無線通信システムでの使用のためのノード装置（１０２、１０４、１０６、１０８、１１０、１１２、１１４、１１６、１１８、１２０）であって、
前記ノード装置（１０２、１０４、１０６、１０８、１１０、１１２、１１４、１１６、１１８、１２０）がメッセージを前記システム内の宛先ノードに宛てるためのルートを備えて構成されているかどうか判定し、そのように構成されていない場合は、発見プロトコルシーケンスであって、
ａ）前記宛先ノード（１００）への配送を求める発見ルーティング要求を生成するステップと、
ｂ）メッセージを前記宛先ノードに宛てるための選択された通信ルートを示す前記発見ルーティング要求に関する前記ルート計算機からのルーティングメッセージを受信するステップと、
ｃ）前記発見プロトコルシーケンスを出て、前記選択された通信ルートを使用して将来のメッセージを前記宛先ノード（１００）にルーティングするステップと、
を含む発見プロトコルシーケンスに入る動作と、
前記ルート計算機に前記ノード装置（１００）によって到達可能なリンクの通信特徴を示す動作と、
前記発見プロトコルシーケンスにない場合は、前記ルート計算機から、計画された通信ルートを前記宛先ノード（１００）に示す前記通信特徴を使用して生成されたルーティングメッセージを受信し、前記計画された通信ルートを使用して将来のメッセージを前記宛先ノード（１００）にルーティングする動作と
を行うように構成されたノード装置（１０２、１０４、１０６、１０８、１１０、１１２、１１４、１１６、１１８、１２０）。
【請求項４】
いくつかのノード装置（１００）および基地局（１００）を含む無線通信システムでの使用のための基地局（１００）であって、
前記システムの現行のルーティング構成を観察する動作と、
前記システムの前記現行のルーティング構成に関する現行のメトリックを生成する動作と、
可能な改善されたシステム動作の推定に関する改善されたメトリックを生成する動作と、
システム改善が示されているかどうか判定するために前記動作中のメトリックを前記改善されたメトリックと比較する動作と、
示されている場合は、実際のルーティング構成を新規ルーティング構成で置き換えるためにメッセージを前記システム内の少なくとも１つのノード装置に配送する動作と、
を行うように構成されたルーティング計算機を含む基地局（１００）。
【国際調査報告】
2009500962.tif 000009
2009500962.tif 000010
2009500962.tif 000011
2009500962.tif 000012
2009500962.tif 000013