(57)【特許請求の範囲】
【請求項１】
マルチチャネル通信ネットワークのノードの制御の下、
宛先に送信されることになる情報を受信するステップと、
前記ノードのメモリにおいて維持されたビジーデバイスリストをクエリするステップであって、前記ビジーデバイスリストは、１つまたは複数の隣接ノードの可用性に関する情報を含んでいる、ステップと、
前記１つまたは複数の隣接ノードと一連の通信を交換することによって前記１つまたは複数の隣接ノードとのリンクの品質を判定するステップと、
前記ビジーデバイスリストおよび前記判定されたリンクの品質にしたがって、送信を受信するのに利用可能であり、および、前記情報を前記宛先に伝搬することが可能な隣接ノードを識別するステップと、
現在利用可能なデバイスよりも高い判定されたリンク品質を有する前記ビジーデバイスリスト上のデバイスが利用可能になるまで、送信を遅延させるステップと、
前記情報を前記識別された隣接ノードに、前記デバイスを介して送信するステップと
を備えたことを特徴とする方法。
【請求項２】
前記情報を受信するステップは、前記情報が前記宛先に送信されることになることのインジケーションとともに、前記情報を隣接ノードから受信するステップを備えていることを特徴とする請求項１に記載の方法。
【請求項３】
前記情報を受信するステップは、前記ノードのローカル計測モジュールから前記情報を受信するステップを備えており、前記情報は、前記宛先に送信されることになるリソース消費データを含んでいることを特徴とする請求項１に記載の方法。
【請求項４】
前記ビジーデバイスリストは、前記ノードの媒体アクセス制御（ＭＡＣ）サブレイヤにおいて維持されることを特徴とする請求項１に記載の方法。
【請求項５】
前記マルチチャネル通信ネットワークの制御チャネル上で前記ノードによってオーバーヒアされたメッセージに含まれるリザベーション情報に基づいて、前記ビジーデバイスリストを更新するステップをさらに備えたことを特徴とする請求項１に記載の方法。
【請求項６】
前記ノードによってオーバーヒアされた前記メッセージは、前記マルチチャネル通信ネットワークの他のノードにアドレス指定された送信要求（ＲＴＳ）メッセージ、および／または、前記マルチチャネル通信ネットワークの他のノードにアドレス指定された送信可（ＣＴＳ）メッセージを含んでいることを特徴とする請求項５に記載の方法。
【請求項７】
前記マルチチャネル通信ネットワークの制御チャネル上でリスンするステップと、
前記制御チャネル上で他のノードによって送信され、および／または、他のノードに向けられたメッセージをオーバーヒアするステップであって、前記オーバーヒアされたメッセージは、前記他のノードの非可用性および非可用性の期間を示している、ステップと、  前記オーバーヒアされたメッセージに基づいて、前記他のノードの非可用性および非可用性の期間を含むように、前記ビジーデバイスリストを更新するステップと
をさらに備えたことを特徴とする請求項１に記載の方法。
【請求項８】
前記情報を前記識別された隣接ノードに送信するステップは、
制御チャネル上で送信要求（ＲＴＳ）メッセージを前記識別された隣接ノードに送信するステップであって、前記ＲＴＳメッセージは、送信されることになる情報のサイズ、および、前記情報が送信されることになるデータチャネルを示している、ステップと、
送信可（ＣＴＳ）メッセージを前記識別された隣接ノードから受信するステップであって、前記ＣＴＳメッセージは、
前記識別された隣接ノードが前記情報を受信することに利用可能であることと、
前記情報が送信されることになる前記データチャネルが受理可能であることの確認、または、前記情報を送信する代替データチャネルの指定と、
前記情報の前記サイズおよび前記ノードと前記識別された隣接ノードとの間の送信の最大データレートに基づいている、前記情報の送信の予想される時間と、
を示している、ステップと、
前記ＣＴＳメッセージにおいて確認された前記データチャネル、または、前記ＣＴＳメッセージにおいて指定された前記代替データチャネル上で、前記情報を前記識別された隣接ノードに送信するステップと
を備えていることを特徴とする請求項１に記載の方法。
【請求項９】
マルチチャネル通信ネットワークのノードの１つまたは複数のコンピュータ可読記憶媒体であって、前記コンピュータ可読記憶媒体は、前記ノードの１つまたは複数のプロセッサによって実行されると、前記ノードが請求項１乃至８のいずれか一項に記載の方法を実行するように構成する命令を格納していることを特徴とするコンピュータ可読記憶媒体。
【請求項１０】
ネットワークコンピューティングデバイスであって、
１つまたは複数のプロセッサと、
前記１つまたは複数のプロセッサに通信可能に結合されたメモリと、
前記ネットワークコンピューティングデバイスの前記メモリにおいて維持されたビジーデバイスリストであって、前記ビジーデバイスリストは、マルチチャネル通信ネットワークの他のネットワークコンピューティングデバイスの非可用性および非可用性の期間を示している、ビジーデバイスリストと、
前記メモリに格納され、および、前記他のネットワークコンピューティングデバイスと一連の通信を交換することによって、前記他のネットワークコンピューティングデバイスとのリンクの品質を判定するように前記１つまたは複数のプロセッサによって実行可能な適格化モジュールと、
前記メモリに格納され、ならびに、前記ビジーデバイスリストおよび前記判定されたリンクの品質に基づいて前記ネットワークコンピューティングデバイスからの通信をルーティングするように前記１つまたは複数のプロセッサによって実行可能なルーティングモジュールであって、現在利用可能なデバイスよりも高い判定されたリンク品質を有する前記ビジーデバイスリスト上のデバイスが利用可能になるまで、前記通信のルーティングが遅延される、ルーティングモジュールと
を備えたことを特徴とするネットワークコンピューティングデバイス。
【請求項１１】
複数の異なるチャネル上で通信を送信および受信することが可能なマルチチャネル無線と、
前記マルチチャネル通信ネットワークの所定の周波数ホッピングパターンにしたがって、前記複数の異なるチャネル間で切替わるように構成された周波数ホッピングモジュールと
をさらに備えたことを特徴とする請求項１０に記載のネットワークコンピューティングデバイス。
【請求項１２】
前記ルーティングモジュールは、前記マルチチャネル通信ネットワークの制御チャネル上で、前記ネットワークコンピューティングデバイスによってオーバーヒアされたメッセージに含まれるリザベーション情報に基づいて、前記ビジーデバイスリストを更新するようにさらに構成されており、前記リザベーション情報は、ビジーであるネットワークコンピューティングデバイスのインジケーション、および、ネットワークコンピューティングデバイスがビジーとなる期間を含んでいることを特徴とする請求項１０に記載のネットワークコンピューティングデバイス。
【請求項１３】
前記適格化モジュールは、
１つまたは複数のリンクのリンク品質が所定の閾値品質を満たすと判定したことに応答して、前記ネットワークコンピューティングデバイスとそれぞれの他のネットワークコンピューティングデバイスとの間の前記１つまたは複数のリンクを適格とし、および、
適格とされたリンクのリストを前記ネットワークコンピューティングデバイスの前記メモリに格納する
ことを特徴とする請求項１０に記載のネットワークコンピューティングデバイス。
【請求項１４】
前記メモリに格納され、および、前記ネットワークコンピューティングデバイスの物理ロケーションからリソース消費データを収集するように前記１つまたは複数のプロセッサによって実行可能である計測モジュールをさらに備えており、前記リソース消費データは、電気消費データ、水道消費データ、および／または、天然ガス消費データを備えていることを特徴とする請求項１０に記載のネットワークコンピューティングデバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、通信のルーティング技術に関する。
【背景技術】
【０００２】
本願は、２０１１年１１月１１日に出願され、および、「ノード可用性に基づく通信のルーティング」と題する欧州特許出願第１１１８８９０．４号の優先権を主張するものであり、上記出願は参照により本明細書に組み込まれる。
【０００３】
メッシュネットワークなどの通信ネットワークは、種々の異なるデバイスを接続するために使用されている。例えば、メッシュネットワークは、ユーティリティメータ、セルラリレー、変圧器、および／またはノードを接続するために、ユーティリティ産業で採用されてきた。メッシュネットワークにおけるノードは、主として、隣接ノードからデータを受信し、および、他の、隣接ノードに中継もしくは伝搬することが可能である。
【０００４】
従来の有線ネットワークでは、ソースと宛先との間の最も少ないホップ数に基づいてメッセージをルーティングするルーティングメトリック（routing metric）が使用されることがある。しかしながら、無線メッシュネットワークでは、ノード間のデータレートは、１つのリンクから別のリンクへと大きく変化することがある。このデータレートの変動は、メッシュネットワークが、異なる特徴および能力（capability）を有する複数の異なる世代のノードを含むことが多いという事実に少なくとも部分的に起因することがある。例えば、異なる世代のノードは、異なる変調技術および／またはデータレートを採用することがあり、または、採用することが可能である。このことは、とりわけ、ノードが時間とともに次第にサービスに置かれ、および、比較的長いライフサイクル（例えば、２０年以上）、当該分野に存続することが予想されるユーティリティメッシュネットワークに当てはまる。一般に、より新たな世代のノードは、旧世代のノードよりも追加的な変調およびより高いデータレートの能力がある。
【０００５】
加えて、複数の異なるノードが同時に異なるチャネル上で送信しているマルチチャネルネットワークのケースでは、一部の宛先ノードは、異なるチャネル上で送信または受信することにビジー（busy）であることを理由に、それらに対して意図された送信をミス（miss）してしまうことがある。従来では、別のデバイスを通信しているビジーな宛先デバイスにメッセージを送信するノードは、宛先デバイスから応答を受信しないであろう。そのケースでは、メッセージを送信しているノードは、粗悪なリンク品質（poor link quality）を理由に、衝突を理由に（すなわち、同時に同一のチャネル上の複数の送信）、または、宛先デバイスが単に、別のチャネル上で別のデバイスと通信するのにビジーであったことを理由に、送信が失敗したかを知る方法を有さない。
【０００６】
したがって、既存のルーティングメトリックは、複数の異なる世代のノードまたは異なる能力を有するノードを含む異種（heterogeneous）マルチチャネル無線メッシュネットワーク内で送信をルーティングする効果的な方法を提供しない。
【発明の概要】
【０００７】
添付図面を参照して、発明の詳細な説明が示される。図面では、参照番号の最も左の桁が、参照番号が最初に現れる図を識別する。異なる図面における同一の参照番号の使用は、類似のもしくは同一の項目を示す。
【図面の簡単な説明】
【０００８】
【図１】複数の異なる能力を有するノード間で送信を効果的にルーティングすることができる、マルチチャネル無線メッシュネットワークの例示的なアーキテクチャの図である。
【図２】図１のアーキテクチャの例示的なノードの追加的な詳細を示す図である。
【図３】ネットワークのノード間のリンクの品質にしたがって、マルチチャネル無線メッシュネットワークにおいて送信をルーティングする例示的な方法を示すフローチャートである。
【図４】マルチチャネル無線メッシュネットワークのリンクの品質を判定する例示的な方法の信号フローチャートである。
【図５】マルチチャネル無線メッシュネットワークにおいて送信をルーティングするためのビジーなデバイスリストを採用する例示的な方法を示すフローチャートである。
【図６】ノードがデータを別のノードに送信することを望んでいることを示すのに使用することができる送信要求メッセージ（request-to-send message）の例示的なフレーム構造の図である。
【図７】ノードがデータを受信するのに利用可能であることを示すのに使用することができる送信可メッセージ（clear-to-send message）の例示的なフレーム構造の図である。
【発明を実施するための形態】
【０００９】
＜概要＞
上述したように、既存のルーティングメトリックは、マルチチャネル無線メッシュネットワーク内で送信をルーティングする効果的な方法を提供しない。例えば、既存のルーティングメトリックは、送信データレートがリンクからリンクへと変化することがあるように、ノードが異なる能力を有する異種無線メッシュネットワークにおいて通信をルーティングするのに適していない。本明細書で使用されるように、「リンク」は無線周波数（ＲＦ）によってなど、ネットワークの２つのノード間での直接送信パス（別のノードを通じて渡すことなく）を指す。２つのノード間のリンクに渡ってのデータレートは、少なくとも部分的には、２つのノードの送信能力（例えば、互換性のある変調技術およびデータレート）に依存する。このように、リンクを渡っての最大データレートは、リンクの最も遅いノードの能力によって制限される。
【００１０】
本願は、異種無線メッシュネットワークのノード間で高度に（intelligently）通信をルーティングするための技術を説明する。例えば、本願は、ネットワークのノード間でリンクの品質を判定し、および、当該判定されたリンクの品質に少なくとも部分的に基づいて通信をルーティングすることを説明する。
【００１１】
従来のルーティングメトリックはまた、主として、宛先ノードが、異なるチャネル上で送信または受信することにビジーであることを理由に、宛先ノードに対して意図された送信をミスしてしまうことがある、いわゆる「ミシングデスティネーション問題（missing destination problem」を考慮しない。従来のルーティングメトリックを採用するときに、意図された宛先ノードから応答を受信しないノードは、衝突が発生し、および、コンテンションウィンドウのサイズ（すなわち、ノードがメッセージを再送信する前に待機する平均時間量）が増大したと考えることがある。この増大した待機時間は、不必要な遅延およびその意図された宛先への送信を伝搬する非効率性をもたらすことがある。
【００１２】
本願はまた、１つまたは複数の隣接ノードに対する可用性情報（availability information）を含む、各ノードに対するビジーデバイスリストを維持することを説明する。通信は、ビジーデバイスリストにおいて維持された隣接ノードの可用性情報に少なくとも部分的に基づいて、ルーティングされてもよい。
【００１３】
したがって、本願において示される種々の実施形態では、送信は、リンク品質（例えば、適格とされた（qualified）リンクのリストに基づいて）、隣接ノードの可用性（例えば、ビジーデバイスリストに基づいて）、またはその両方に基づいて、マルチチャネルメッシュネットワークなどの通信ネットワークにおいてルーティングされてもよい。
【００１４】
ルーティング技術は、複数のノードを含むユーティリティメッシュネットワークのコンテキストで示される。ユーティリティメッシュネットワークのノードは、例えば、スマートユーティリティメータ（例えば、電気、ガスおよび／または水道メータ）、センサ（例えば、温度センサ、ウェザーステーション（weather stations）、周波数センサなど）、制御デバイス、変圧器、ルータ、サーバ、リレー（例えば、セルラリレー）、スイッチ、バルブ、および、他のネットワークデバイスを含んでもよい。ルーティング技術がユーティリティメッシュネットワークのコンテキストで示されるが、ルーティング技術は追加的に、または、代替的に、他のネットワークおよび／もしくは他の応用例に適用可能であってもよい。このように、他の実装において、ノードは、通信ネットワークに結合され、ならびに、データを送信および／または受信することが可能な任意のデバイスを含んでもよい。
【００１５】
複数のおよび多様な実装および実施形態が、以下、「リンク品質に基づくルーティング」および「ノード可用性に基づくルーティング」の概要から始まって示される。これらの概要は、本明細書で示されるルーティング技術を実装するのに使用可能な「例示的なアーキテクチャ」および「例示的なノード」の詳細に従う。次に、本願は、リンク品質に基づくルーティングの例示的なプロセス」および「ノード可用性に基づくルーティングの例示的なプロセス」の追加的な詳細を示す。例示的なルーティングプロセスの詳細な議論に従って、本願は、本明細書で説明されるようなルーティング方法を実装するのに使用することができるいくつかの「例示的なプロトコルデータユニット（ＰＤＵ）」の詳細を含む。最後に、本願は、簡潔な「結論」で結論づける、この概要およびセクションの冒頭を含む以下のセクションは、単に実装および実施形態を例示するものであり、特許請求する範囲を制限するものと解釈すべきではない。
【００１６】
＜リンク品質に基づくルーティングの概要＞
１つの例示的な実施形態では、本願は、マルチチャネルユーティリティネットワークなどの通信ネットワークのノード間のリンクの品質を判定し、および、判定されたリンクの品質に少なくとも部分的に基づいて通信をルーティングすることを示す。この例では、ノードは、ノードと複数の隣接ノードとの間のリンク品質を判定する。複数の隣接ノードの各々に対し、ノードは、ノードとそれぞれの隣接ノードとの間の判定されたリンク品質を、所定の閾値品質と比較する。リンク品質が所定の閾値品質を満たす場合は、ノードはリンクを適格とし（qualify）、および、当該リンクを、閾値リンク品質を満たす適格とされたリンクのリストに追加してもよい。そして、ノードは、適格とされたリンクを有するノードとの隣接ノードに通信をルーティングしてもよい。
【００１７】
ノードは、ノードと１つまたは複数のその隣接ノードとの間のリンクの品質を判定してもよい。一例では、ノードが比較的少数の隣接ノード（例えば、１０より少ない）を有している場合、ノードは、当該ノードとその隣接ノードのすべてとの間のリンクの品質を判定してもよい。代わりに、ノードが多数の隣接ノードを有している場合、ノードは自身とその隣接ノードのサブセットとの間のリンク品質を判定してもよい。一例では、ノードは、当該ノードが閾値リンク品質を満たす所定の数のリンク（例えば、５、１０、２０など）を判定するまで、その隣接ノードとのリンクの品質を判定することを継続してもよく、その結果、ノードに対する十分な数の良好な通信パスを保証する。
【００１８】
ノードは、リンク上の隣接ノードとの一連の（series）通信を交換することによって、隣接ノードとのリンクの品質を判定してもよい。例えば、一実施形態では、ノードは、送信要求（ＲＴＳ：request-to-send）メッセージを隣接ノードに送信してもよい。送信要求メッセージは、テストする通信チャネルのシーケンスを指定してもよい。例えば、テストされることになる通信チャネルのシーケンスは、テストするチャネル番号、テストするチャネル間のステップ間隔、および、テストするチャネルの数を始める（begin）ことによって、指定されてもよい。それに応じて、ノードは隣接ノードから、当該隣接ノードが送信を受信するのに利用可能であることを示す送信可（ＣＴＳ：clear-to-send）メッセージを受信してもよい。そして、ノードは、テストする通信チャネルのシーケンスにしたがって、隣接ノードにテストデータパケットを送信することによって、ノードとそれぞれの隣接ノードとの間の通信チャネルのシーケンスをテストすることを進めてもよい。テストデータパケットを受信すると、隣接ノードは、通信チャネルの同一のシーケンスにしたがって、テストデータパケットを送信し返してもよい。テストデータパケットの各々は、リンクを通じた送信の時間におけるコストのインジケーションを含んでもよい。
【００１９】
隣接ノードからテストデータパケットを受信すると、ノードは、通信チャネルのシーケンスのテストに基づいて、ノードと隣接ノードとの間のリンク品質を算出してもよい。ノードはまた、ノードが隣接ノードから受信した多数のテストデータパケットを含む確認パケットを送信してもよい。隣接ノードは、確認パケットを使用して、ノードとそれぞれの隣接ノードとの間のリンク品質を評価してもよい。リンク品質が所定の閾値品質を満たす場合は、ノードはリンクを適格とし、および、閾値リンク品質を満たす適格とされたリンクのリストに当該リンクを追加してもよい。リンクは、通信チャネルのすべてのまたはその一部に対して適格とされてもよい。例えば、チャネルダイバシティを促進して他の隣接ノードからの干渉および衝突の可能性を減少させるために、リンクはチャネルの一部に対して適格とされてもよい。また、例えば、１つまたは複数のチャネルがテストデータの交換の間に発見されて、干渉を経験し、または、粗悪な品質の送信を有していた場合は、ノードはチャネルの一部に対して適格とされてもよい。一部の例では、適格とされたリンクのリストは、ノードとそれぞれの隣接ノードとの間のリンクの相対品質にしたがって、隣接ノードを順位付けることを含んでもよい。このケースでは、ノードは、リンクの相対品質に少なくとも部分的に基づいて、その隣接ノードに通信をルーティングしてもよい（例えば、最も高い品質を有するリンクによってノードに接続された利用可能な隣接ノードに通信をルーティングする）。
【００２０】
種々の異なるメトリックが使用されて、ノード間のリンク品質を算出してもよい。１つの特定の例では、リンク品質は、リンクにわたる（across）通信の予想される送信時間（ＥＴＴ：expected transmission time）に基づいて算出されてもよい。ＥＴＴは、式１に基づいて算出されてもよい。
【００２１】
【数１】
0005938480.tif 000002
【００２２】
Ｐは、リンク上のロスレート（loss rate）であり、Ｐｆは、データパケットが隣接ノードに到達することに成功する確立（probability）であり、Ｐｒは、隣接ノードからの確認が受信されるのに成功する確立であり、Ｓは、データパケットのパケットサイズ（例えば、ビットまたは他の単位）であり、および、Ｂは、２つのノード間のリンクの帯域幅（例えば、ビット／秒または他の単位）である。
【００２３】
例えば、２つのノードｘおよびｙを考えると、ノードｘに対するＰｆは、ノードｘからノードｙによって受信されたテストデータパケットの数を、ノードｘによって送信されたテストデータパケットで割ったものとなる。ノードｘに対するＰｒは、ノードｙからノードｘによって受信されたテストデータパケット数を、ノードｙによって送信されたテストデータパケットで割ったものとなる。ノードｙに対するＰｆおよびＰｒは、同様の方法で計算される。式１は、リンク品質を測定するのに使用されてもよいルーティングメトリックの１つの例にすぎず、他の例では、種々の他のメトリックがリンク品質を測定するのに使用されてもよい。
【００２４】
ＲＴＳを受信した後に、隣接ノードが通信を受信するのに利用可能でない場合は（例えば、隣接ノードが既に前もってスケジューリングされた通信を有している場合）、隣接ノードは、送信不可（ＮＣＴＳ：not-clear-to-send）メッセージを送信し返してもよい。隣接ノードが別のチャネル上で通信するのにビジーである場合は、隣接ノードはＲＴＳを受信しなくてもよく、したがって、応答しない。ノードがＮＣＴＳを受信し、または、応答を受信しない場合は、当該ノードは一定時間待機し、ならびに、異なる隣接ノードを再び試み、および／または、試みてもよい。
【００２５】
＜ノード可用性に基づくルーティングの概要＞
別の例示的な実施形態では、本願は、１つまたは複数の隣接ノードに対する可用性情報を含む、各ノードに対するビジーデバイスリストを維持し、ならびに、隣接ノードの可用性に基づいて送信をルーティングすることを示す。この例では、ノードは宛先に送信されることになるいくつかの情報（例えば、リソース消費情報、レポート、アラート、ステータスメッセージ、ソフトウェア／ファームウェアアップデートなど）を受信する。情報は、隣接ノードからまたはシステムもしくはノード自体のコンポーネント（例えば、ローカルセンサまたは計測モジュール）から受信されてもよい。情報を受信すると、ノードは、ビジーデバイスリストをクエリして、１つまたは複数の隣接ノードの可用性を判定してもよい。そして、ノードは、ビジーデバイスリストにしたがって、送信を受信することに利用可能であり、および、情報を宛先に伝搬することが可能な隣接ノードを識別してもよい。そして、ノードは、情報を識別された隣接ノードに送信してもよい。
【００２６】
ビジーデバイスリストは一般に、ノード自体のローカルメモリにおいて維持される（例えば、ノードの媒体アクセス制御（ＭＡＣ）サブレイヤにおいて）。しかしながら、一部の実施形態では、ビジーデバイスリストは、追加的にもしくは代替的に、ネットワーク上の別のロケーションにおいて維持されてもよい（例えば、親ノード、セルラルータ、リレー、またはネットワークストレージデバイスなど）。
【００２７】
ビジーデバイスリストは、マルチチャネル通信ネットワークの制御チャネル上のノードによってオーバーヒアされた（overheard）メッセージに含まれるリザベーション情報（reservation information）に基づいて、生成され、維持され、および、更新されてもよい。リザベーション情報は、ビジーであるノード、および、それらがビジーである時間を識別してもよい。このリザベーション情報は、例えば、マルチチャネル通信ネットワークの他のノードにアドレス指定された送信要求（ＲＴＳ）メッセージ、および／またはマルチチャネル通信ネットワークの他のノードにアドレス指定され送信可（ＣＴＳ）メッセージを含む、種々のメッセージに含まれてもよい。
【００２８】
＜例示的なアーキテクチャ＞
図１は、リンク品質および／またはノードの可用性にしたがって、送信をルーティングすることができる、マルチチャネル無線メッシュネットワークの例示的なアーキテクチャ１００の図である。アーキテクチャ１００は、直接通信パスすなわち「リンク」を介して互いに通信可能に結合された複数のノード１０２Ａ、１０２Ｂ、１０２Ｃ．．．１０２Ｎ（総称してノード１０２と称される）を含む。この例では、Ｎは、ワイドエリアネットワーク（ＷＡＮ）、メトロポリタンネットワーク（ＭＡＮ）、ローカルエリアネットワーク（ＬＡＮ）、ネイバーフッドエリアネットワーク（ＮＡＮ）またはパーソナルエリアネットワーク（ＰＡＮ）などの自立的ルーティングエリア（ＡＲＡ）におけるノードの数を表す。
【００２９】
上述したように、用語「リンク」は、２つのノード間の直接通信パス（別のノードを通らずまたは別のノードによって伝搬されない）を指す。各リンクは、ノードがデータを送信または受信することが可能な複数のチャネルを表してもよい。複数のチャネルの各々は、当該複数のチャネルの各々に対して同一または異なる周波数範囲によって定義されてもよい。一部のインスタンスでは、複数のチャネルは、ＲＦチャネルを備える。複数のチャネルは、制御チャネルおよび複数のデータチャネルを備えてもよい。一部のインスタンスでは、制御チャネルは、ノード間において１つまたは複数のメッセージを通信して、データを転送するのに利用されることになるデータチャネルの１つを特定するのに利用される。一般に、制御チャネル上の送信は、データチャネル上の送信と比較して短い。
【００３０】
ノード１０２の各々は、例えば、スマートユーティリティメータ（例えば、電気、ガス、および／または水道メータ）、センサ（例えば、温度センサ、ウェザーステーション、周波数センサなど）、制御デバイス、変圧器、ルータ、サーバ、リレー（例えば、セルラリレー）、スイッチ、バルブ、それらの組合せ、または、通信ネットワークに結合可能であり、ならびに、データを送信および／もしくは受信することが可能な任意のデバイス、などの種々の従来のコンピューティングデバイスのいずれかとして実装されてもよい。
【００３１】
この例では、ノード１０２はまた、インターネットなどのバックホールネットワーク１０６へのＡＲＡの接続ポイントとしてサービスするエッジデバイス（edge device)（例えば、セルラリレー、セルラルータ、エッジルータ、ＤＯＤＡＧルートなど）を介して中央オフィス１０４と通信するように構成される。例示された例では、ノード１０２Ａは、ＡＲＡの他のノード１０２Ｂ乃至１０２Ｎから中央オフィス１０４へ、および中央オフィス１０４から、ネットワーク１０を介して通信を中継するセルラリレーとしてサービスする。
【００３２】
ノード１０２Ｃは、ノード１０２の各々の代表であり、ならびに、無線１０８およびプロセシングユニット１１０を含む。無線１０８は、複数のチャネル／周波数のうちの１つまたは複数を介して無線周波数（ＲＦ）信号を送信および／または受信するように構成されたＲＦ送受信機を備える。一部の実施形態では、ノード１０２の各々は、各通信リンクの制御チャネルおよび複数のデータチャネルなどの、複数の異なるチャネル上でデータを送信および受信するように構成された単一無線１０８を含む。無線１０８はまた、複数の異なる変調技術、データレート、プロトコル、信号強度、および／または電力レベルを実装するように構成されてもよい。アーキテクチャ１００は、ノード１０２が、異なるタイプのノード（例えば、スマートメータ、セルラリレー、センサなど）、異なる世代もしくはモデルのノード、ならびに／あるいは、異なるチャネル上で、または、異なる変調技術、データレート、プロトコル、信号強度および／もしくは電力レベルを使用して送信することが可能なノードを含んでもよいという点で、ノードの異種ネットワークを表してもよい。
【００３３】
プロセシングユニット１１０は、メモリ１１４と通信可能に結合された１つまたは複数のプロセッサ１１２を含んでもよい。メモリ１１４は、プロセッサ１１２上で実行可能であり、種々の機能を実装する１つまたは複数のソフトウェアおよび／またはファームウェアモジュールを格納するように構成されてもよい。モジュールは、本明細書においてプロセッサ上で実行可能なソフトウェアおよび／またはファームウェアとして示されているが、他の実施形態では、モジュールの一部もしくはすべては、示された機能を実行するハードウェア（例えば、ＡＳＩＣ、特殊プロセシングユニットとして）全体として、または、その一部として実装されてもよい。
【００３４】
図１の実施形態では、メモリ１１４は、ルーティングモジュール１１６、適格化モジュール（qualification module）１１８およびビジーデバイスリストモジュール１２０を含む。ルーティングモジュール１１６は、適格化モジュール１１８によって判定されたノード１０２間のリンクの品質、ビジーデバイスリストモジュール１２０によって判定されたノード１０２の可用性、および／または、１つまたは複数の他のファクタに基づいて、ＡＲＡのノード１０２間で送信をルーティングするように構成される。これらおよび他のファクタに基づいて、ルーティングモジュール１１６がどのように通信をルーティングするかの追加の詳細は、図２乃至５の議論において以下に提供される。
【００３５】
適格化モジュール１１８は、ノード１０２間のリンクの品質を判定するように構成される。例示された例では、ノード１０２Ｃの適格化モジュール１１８は、ノード１０２Ｃとその隣接ノード１０２Ａおよび１０２Ｃとの間のリンクが、品質の閾値レベルを満たし、したがって、「適格とされたリンク」（qualified links）として指定されると判定している。一方で、適格化モジュール１１８は、ノード１０２Ｃとその隣接ノード１０２Ｂとの間のリンクの品質を判定しておらず、または、適格化モジュール１１８は、ノード１０２Ｃとその隣接ノード１０２Ｂとの間のリンクが品質の閾値レベルを満たしていないと判定している（例えば、リンクは干渉を経験し、弱くもしくは減退した信号を有しており、または、送信に対して適切でない）。したがって、ノード１０２Ｃとその隣接ノード１０２Ｂとの間のリンクは、図１において、適格とされていないリンク（unqualified link）として指定される。
【００３６】
ビジーデバイスリストモジュール１２０は、ノード１０２の可用性を判定し、ならびに、ビジーであるノードおよびそれらがビジーである期間（duration）をリスト化することを維持するように構成される。例示された例では、ビジーデバイスリストモジュール１２０は、ノード１０２Ｂがノード１０２Ａにデータを送信するのにビジーであり、したがって、ノード１０２Ｃからの送信を受信することが利用可能でないことを示している。
【００３７】
メモリ１１４は、コンピュータ可読媒体を備えてもよく、ならびに、ランダムアクセスメモリ（ＲＡＭ）などの揮発性メモリ、および／またはリードオンリメモリ（ＲＯＭ）もしくはフラッシュＲＡＭなどの不揮発性メモリの形式をとってもよい。コンピュータ可読媒体は、コンピューティングデバイスの１つもしくは複数のプロセッサによる実行のためのコンピュータ可読命令、データ構造、プログラムモジュールもしくは他のデータなどの、情報の格納のための任意の方法もしくは技術において実装される、揮発性および不揮発性、着脱可能および着脱不能媒体を含む。コンピュータ可読媒体の例は、相変化メモリ（ＰＲＡＭ：phase change memory）、静的ランダムアクセスメモリ（ＳＲＡＭ）、動的ランダムアクセスメモリ（ＤＲＡＭ）、もしくは他のタイプのランダムアクセスメモリ、リードオンリメモリ（ＲＯＭ）、電気的消去可能リードオンリメモリ（ＥＥＰＲＯＭ）、フラッシュメモリもしくは他のメモリ技術、コンパクトディスクリードオンリメモリ（ＣＤ−ＲＯＭ）、デジタル多用途ディスク（ＤＶＤ）、もしくは他の光学記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置もしくは他の磁気記憶デバイス、または、コンピューティングデバイスによるアクセスのための情報を格納するのに使用することができる任意の他の非送信媒体を含むが、それらに限定されない。本明細書で定義されるように、コンピュータ可読媒体は、変調データ信号および搬送波などの通信媒体を含まない。
【００３８】
ネットワーク１０６は、それ自体が無線もしくは有線ネットワークまたはそれらの組合せを備えることができるバックホールネットワークを表している。ネットワーク１０６は、互いに相互接続された個々のネットワークの集合であってもよく、ならびに、単一の大規模ネットワーク（例えば、インターネットまたはイントラネット）として機能していてもよい。さらに、個々のネットワークは、無線もしくは有線ネットワークまたはそれらの組合せであってもよい。
【００３９】
中央オフィス１０４は、サーバ、パーソナルコンピュータ、ラップトップコンピュータなどの１つまたは複数のコンピューティングデバイスによって実装されてもよい。１つまたは複数のコンピューティングデバイスは、メモリに通信可能に結合された１つまたは複数のプロセッサを備えてもよい。一部の例では、中央オフィス１０４は、１つまたは複数のノード１０２から受信されたデータの処理、分析、格納および／または管理を実行する、集中型メータデータ管理システム（centralized meter data management system）を含む。例えば、中央オフィス１０４は、スマートユーティリティメータ、センサ、制御デバイス、ルータ、レギュレータ、サーバ、リレー、スイッチ、バルブおよび／または他のノードから取得されたデータを処理、分析、格納、および／または管理してもよい。 図１の例は、単一のロケーションにおける中央オフィス１０４を示しているが、一部の例では、中央オフィスは、複数のロケーション間で分散されてもよく、および／または、完全に除外されてもよい（例えば、高度非集中型分散コンピューティングプラットフォーム）。
【００４０】
＜例示的なノード＞
図２は、図１のノード１０２Ｃの例の追加の詳細を示す図である。この例では、無線１０８は、ＲＦフロントエンド２０２およびベースバンドプロセッサ２０４に結合されたアンテナ２００を含む。ＲＦフロントエンド２０２は、送信および／または受信機能を提供してもよい。ＲＦフロントエンド２０２は、アンテナによって提供され、および、ノード１０２の１つもしくは複数から取得される信号を同調し、ならびに／または、減衰するなどの機能を提供する、高周波数アナログ、および／もしくは、ハードウェアコンポーネントを含んでもよい。ＲＦフロントエンド２０２は、信号をベースバンドプロセッサ２０４に提供してもよい。
【００４１】
１つの例では、ベースバンドプロセッサ２０４のすべてもしくは一部は、ソフトウェア（ＳＷ）定義無線（software defined radio）として構成されてもよい。１つの例では、ベースバンドプロセッサ２０４は、周波数および／またはチャネル選択機能を無線１０８に提供する。例えば、ＳＷ定義無線は、プロセッサもしくは特定用途向け集積回路（ＡＳＩＣ）または他の組み込みコンピューティングデバイスによって実行されるソフトウェアで実装される、ミキサ、フィルタ、増幅器、変調器、復調器、ディテクタなどを含んでもよい。ＳＷ定義無線は、プロセッサ１１２、ならびに、メモリ１１４において定義されおよび格納されたソフトウェアを利用してもよい。代わりに、無線１０８は、アナログコンポーネントを少なくとも部分的に使用して実装されてもよい。
【００４２】
プロセシングユニット１１０はまた、時間を維持するように構成されたクロック２０６を含んでもよい。クロック２０６はまた、１つまたは複数のカウントアップまたはカウントダウンタイマを提供するように構成されてもよい。このようなタイマは、複数の通信チャネル間での周波数ホッピングに使用されてもよい。
【００４３】
周波数ホッピングモジュール２０８は、ベースバンドプロセッサ２０４およびクロック２０６と通信するように構成されてもよい。１つの例では、周波数ホッピングモジュール２０８は、時間情報を取得し、および／または、クロック２０６に周波数ホッピングタイマを設定するように構成される。このような時間情報および／またはタイマは、異なるチャネルもしくは周波数を「ホッピング」または同調するときを周波数ホッピングモジュール２０８に示す。加えて、周波数ホッピングモジュール２０８は、ＳＷ定義無線または無線１０８の他のコンポーネントを命令して、実際の周波数変更（frequency changes）を実行するように構成されてもよい。したがって、周波数ホッピングモジュール２０８は、合意した（agreed upon）周波数間で、合意した時間で、繰り返しシフトし、ならびに、合意した期間、および合意したプロトコルで別のノードと通信することが可能である。
【００４４】
一部の実装では（例えば、ノードがユーティリティメータのときに）、メモリ１１４はまた、１つまたは複数のリソース（例えば、電気、水、天然ガスなど）の消費データを収集するように構成された計測モジュール２１０を含んでもよく、消費データは、最終的に中央オフィス１０４または他の宛先への伝搬のために、１つまたは複数の他のノード１０２に送信されてもよい。
【００４５】
上述したように、メモリ１１４はまた、適格化モジュール１１８およびビジーデバイスリストモジュール１２０を含んでもよい。適格化モジュール１１８は、ノード間のリンクの品質を判定し、ならびに、適格とされたリンクリスト（qualified links list）２１２もしくは他のリンク品質情報のレポジトリに、リンクの品質に関する情報を格納する。同様に、ビジーデバイスリストモジュール１２０は、ノード１０２の可用性を判定し、ならびに、ビジーであるノードおよびビジーとなる期間（duration）をビジーデバイスリスト２１４もしくは他のノード可用性データのレポジトリにリスト化することを維持する。適格とされたリンクリスト２１２およびビジーデバイスリスト２１４が、ノード１０２Ｃのローカルメモリに格納されたデータのリストであるとして示されているが、他の実施形態では、リンク品質およびノード可用性情報は、単一リストもしくはリストでない形式で格納されてもよい。さらに、一部の実施形態では、リンク品質およびノード可用性情報は、追加的にもしくは代替的に、ネットワーク上の１つまたは複数の他のロケーションにおいて（例えば、親ノード、セルラルータ、リレー、またはネットワーク記憶デバイスなど）維持されてもよい。
【００４６】
上述したように、適格とされたリンクリスト２１２およびビジーデバイスリスト２１４は、別個のリストとして、または、１つの複合リストとして維持されてもよい。例示された例では、適格とされたリンクリスト２１２およびビジーデバイスリスト２１４は、メモリ１１４において複合リスト２１６として格納される。この図で例示されるように、この例における適格とされたリンクリスト２１２およびビジーデバイスリスト２１４は、一部の重複する情報を含む。
【００４７】
一般に適格とされたリンクリスト２１２に対応する複合リスト２１６の一部は、鎖線領域によって区切られ、ならびに、この例では、ノードがそれとの通信リンクを有する隣接ノード（ヘッダ「Neighbors」の下（under the heading "Neighbors"））のリスト、各隣接ノードとのリンクが適格とされるかのインジケーション（ヘッダ「Qualified」の下）、各リンクに対して適格とされたチャネルのリスト（ヘッダ「Channels」の下）、ならびに、リンクの相対品質によるリンクの順位付け（ヘッダ「Rank」の下）を含む。しかしながら、他の実施形態では、適格とされたリンクリスト２１２は、追加のもしくは代替的な情報（例えば、リンクの相対品質スコア、各リンクの個々のチャネルの相対品質、各リンクもしくは各リンクの各チャネルに対する最大データレートなど）を含んでもよい。
【００４８】
一般にビジーデバイスリスト２１４に対応する複合リスト２１６の一部は、鎖線領域によって区切られ、ならびに、この例では、ノードがそれとの通信リンクを有する隣接ノードのリスト（ヘッダ「Neighbors」の下）、各リンクに対して適格とされたチャネルのリスト（ヘッダ「Channels」の下）、各ノードの可用性状態（ヘッダ「Availability」の下）、ならびに、可用性状態に対応する期間（ヘッダ「Duration」の下）を含む。本明細書で使用されるように、ノードがビジーデバイスリストにおいて利用可能であるとして肯定的に示される場合（例えば、通信を受信するのにスケジューリングされ／予約された時間を有する）、または、暗に利用可能である場合（例えば、利用可能でないとして示されず、従って、利用可能であると想定されるノード）、当該ノードは送信を受信するのに「利用可能であり」もしくは「可用性を有する」。他の実施形態では、ビジーデバイスリスト２１４は、追加的なもしくは代替的な情報を有してもよい（例えば、ビジーノードによって実行されているオペレーションのタイプ、ビジーノードによって送信／受信されているデータのサイズなど）。
【００４９】
ルーティングモジュール１１６は、適格とされたリンクリスト２１２において示されるようなリンク品質、ビジーデバイスリスト２１４において示されるような隣接ノードの可用性、または、複合リスト２１６を使用することの両方に基づいて、送信をルーティングしてもよい。例えば、１つの例示的なルーティングメトリックにしたがって、ノードは、最良のリンク品質ランクを有する利用可能なノードに送信をルーティングすることを試みてもよい。したがって、例示された例では、ノードＮは、無期限に利用可能であり（available for an indefinite duration）、および、利用可能な最良の品質の適格とされたリンク（すなわち、最も低いランク）の両方であるので（ノードＮはその最終的な宛先へ送信を伝搬することが可能であることを想定する）、ノード１０２Ｃは、チャネル５を除く（以下に述べるように、チャネル５は現在、ノードＡおよびＢによって使用されている）チャネル１乃至７のうちの１つの上でノードＮに送信をルーティングしてもよい。この例では、ノードＡは、チャネル５上でのノードＢにデータを送信するのにビジーであるので、送信を受信するのにすぐには利用可能とはならず、それゆえに、ノードＣは、ノードＡがより高い品質のリンク（すなわちより低いランク）を有しているという事実にも関わらず、ノードＡに送信をルーティングしない。また、ノードＣは、チャネル５上でノードＡとＢとの間の送信を阻害することを回避するために、チャネル５上でノードＮにルーティングしない。
【００５０】
代替的なルーティングメトリックにしたがって、ルーティングモジュール１１６は、リンク品質を可用性よりも高く重み付けしてもよい。このケースでは、再び例示された実施形態を参照して、利用可能であるノードにデータを即時に送信するのではなく、ノードＣは、ノードＡがより高い品質（すなわち、より低いランク）のリンク品質を有していることを理由に、ノードＡが利用可能になるときに、ノードＡにデータを送信することを待機することを選択してもよい。さらなる別の代替では、ノードＣは、ノードＡが比較的短い期間に利用可能なる場合のみに、通信をノードＡにルーティングすることを待機することを選択してもよい。言い換えると、通信をどこにルーティングするかの決定は、リンク品質と利用可能になるまでの期間との間のバランスをとってもよい。
【００５１】
＜リンク品質に基づくルーティングの例示的な方法＞
図３は、メッシュネットワークのノード間のリンクの品質を判定し、および、リンク品質に少なくとも部分的に基づいて通信をルーティングする例示的な方法３００を示している。方法３００は、便宜上、図１の例示的なアーキテクチャ１００を参照して示される。しかしながら、方法３００は、図１の例示的なアーキテクチャ１００での使用に限定されず、他のアーキテクチャおよびデバイスを使用して実装されてもよい。
【００５２】
方法３００は、ブロック３０２において、ノード１０２などのノードがノード１０２Ｎなどの隣接ノードとのリンクの品質を判定することで開始する。リンク品質の判定は、ノード１０２Ｃの適格化モジュール１１８などの適格化モジュールによって実行されてもよい。リンク適格化プロセス（link qualification process）の追加の詳細は、図４を参照して以下に示される。
【００５３】
ブロック３０４において、ノード１０２Ｃが隣接ノード１０２Ｎとのリンクの品質を判定すると、ノード１０２Ｃの適格化モジュール１１８は、判定されたリンク品質を閾値リンク品質と比較する。判定されたリンク品質が閾値リンク品質を満たす場合（すなわち、閾値以上である）、ブロック３０６において、ノード１０２Ｃはノード１０２Ｃと隣接ノード１０２Ｎとの間のリンクを適格とし、および、当該リンクを適格とされたリンクリスト２１２に追加する。
【００５４】
ブロック３０８において、ノード１０２Ｃは、所定の数の適格とされたリンクが存在するかを判定する。所定の数の適格とされたリンクは、ノードが有するその周辺の（immediate）隣接ノードとのリンクの数に等しくてもよく、または、所定の数の適格とされたリンクは、ノードが有するその周辺の隣接ノードとのリンクの数のすべてよりも少なくてもよい。例えば、所定の数の適格とされたリンクは、高いネットワークのトラフィックの時間の間でさえ、ノードに対する良好な通信パスを保証するのに十分な数（例えば、３、５、１０など）を備えてもよい。ブロック３０８において、ノード１０２Ｃが所定の数の適格とされたリンクが存在しないと判定した場合、ノード１０２Ｃは、所定の数の適格とされたリンクが達成されるまで、ブロック３０２乃至３０６のオペレーションを繰り返してもよい。一方、ブロック３０８において、ノード１０２Ｃが所定の数の適格とされたリンクが存在すると判定した場合、ノード１０２Ｃは、ブロック３１０において、一部の実施形態に進み、ノード１０２Ｃと隣接ノード１０２Ａ、１０２Ｂおよび１０２Ｎとの間のリンクの相対品質にしたがって、隣接ノードを順位付けしてもよい。しかしながら、他の実施形態では、順位付けオペレーション３１０は、省略されてもよい。
【００５５】
ブロック３１２において、ノード１０２Ｃのルーティングモジュール１１６は、それとの適格とされたリンクを有する隣接ノードに通信をルーティングすることを開始してもよい。したがって、例示された例では、ノード１０２Ｃは、ノード１０２Ｃがノード１０２Ａおよび１０２Ｎとの適格とされたリンクを有しているが、ノード１０２Ｂとは適格とされたリンクを有しないので、ノード１０２Ｂではなく、ノード１０２Ａおよび１０２Ｎに通信をルーティングすることを開始してもよい。適格とされたリンクの存在に単に基づいて通信をルーティングすることに加えて、またはそれに代えて、ブロック３１０において、ノード１０２Ｃがリンク品質に基づいて隣接ノードを順位付けした場合、ノード１０２Ｃは、リンク品質の順位付けに基づいて、通信をルーティングしてもよい（例えば、優先度を与えて、より高い品質のリンクを介して通信を送信する）。
【００５６】
図４は、リンクの品質に基づいてリンクを適格化する例示的な方法４００の追加の詳細を示す信号フローチャートである。便宜上、方法４００は、図１の例示的なアーキテクチャ１００のノード１０２Ｃおよび１０２Ｎを参照して示される。しかしながら、方法４００は、図１の例示的なアーキテクチャ１００での使用に限定されず、他のアーキテクチャおよびデバイスを使用して実装されてもよい。
【００５７】
図４では、ノード１０２Ｃなどのノードは、リンク上でノード１０２Ｎなどの隣接ノードと一連の通信を交換することによって、隣接ノードとのリンクの品質を判定してもよい。例えば、オペレーション４０２において、ノード１０２Ｃは、隣接ノード１０２Ｎに送信要求（ＲＴＳ）メッセージを送信してもよい。送信要求メッセージは、テストする通信チャネルのシーケンスを指定してもよい。例えば、テストされることになる通信チャネルのシーケンスは、テストするチャネル番号Ｘ、テストするチャネル間のステップのインターバルＹ、およびテストするチャネルの数Ｍを始める（begin）ことによって、指定されてもよい。チャネルのシーケンスは、以下の式２にしたがって、数学的に表現されてもよい。
【００５８】
【数２】
0005938480.tif 000003
【００５９】
式２において、ｋは、シーケンスにおけるチャネルの番号である（例えば、テストされる第１のチャネル）。
【００６０】
その後、オペレーション４０４において、ノード１０２Ｃは、隣接ノード１０２Ｎから、隣接ノードが送信を受信するのに利用可能であることを示す送信可（ＣＴＳ）メッセージを受信してもよい。オペレーション４０６において、ノード１０２Ｃは、テストする通信チャネルのシーケンスにしたがって、隣接ノードにテストデータパケットを送信することによって、ノード１０２Ｃとそれぞれの隣接ノード１０２Ｎとの間の通信チャネルのシーケンスをテストすることに進んでもよい。テストデータパケットを受信すると、オペレーション４０８において、隣接ノード１０２Ｎは、通信チャネルの同一のシーケンスにしたがって、テストデータパケットを送信し返してもよい。オペレーション４０８において返されたテストデータパケットの各々は、リンクを通じた送信の時間のコストと、ノード１０２Ｎがノード１０２Ｃから受信したテストデータパケットの数のインジケーションを含んでもよい。
【００６１】
隣接ノードからテストデータパケットを受信し返すと、オペレーション４１０において、ノード１０２Ｃは、通信チャネルのシーケンスのテストに基づいて、ノード１０２Ｃと隣接ノード１０２Ｎとの間のリンク品質を算出してもよい。例えば、ノード１０２Ｃは、上記式１にしたがって、リンク品質を算出してもよい。代わりに、種々の他のメトリックが使用されて、リンク品質を算出してもよい。リンク品質が所定の閾値品質を満たす場合は、ノード１０２Ｃは、当該リンクを適格としてもよく、および、当該リンクを、図３を参照して上述した閾値リンク品質を満たす適格とされたリンクのリストに追加してもよい。
【００６２】
オペレーション４１２において、ノード１０２Ｃはまた、ノード１０２Ｃが隣接ノード１０２Ｎから受信したテストデータパケットの番号を含む確認パケットを送信してもよい。オペレーション４１４において、隣接ノード１０２Ｎは、１０２Ｃによって送信された確認パケットの受信に成功したことを示す確認応答パケットをノード１０２Ｃに送信してもよい。オペレーション４１６において、隣接ノード１０２Ｎは、確認パケットを使用して、ノード１０２Ｃと隣接ノード１０２Ｎとの間のリンクの品質を評価してもよい（例えば、上記式１のリンク品質メトリックを使用して）。リンク品質が所定の閾値品質を満たす場合は、隣接ノード１０２Ｎは、当該リンクを適格とし、および、当該リンクを、図３を参照して上述した閾値リンク品質を満たす適格とされたリンクのリストに追加してもよい。方法４００は、各ノードに対する所定の数のリンクを適格とするのに必要とされるように、何度も実行されてもよい。
【００６３】
＜ノード可用性に基づくルーティングの例示的な方法＞
図５は、メッシュネットワークのノード間のリンクを適格とする例示的な方法５００を示している。方法５００は、便宜上、図１の例示的なアーキテクチャ１００を参照して示される。しかしながら、方法５００は、図１の例示的なアーキテクチャ１００での使用に限定されず、他のアーキテクチャおよびデバイスを使用して実装されてもよい。
【００６４】
方法５００にしたがって、ブロック５０２において、ノード１０２Ｃなどのノードは、ノード１０２Ａ、１０２Ｂおよび１０２Ｎなどの隣接ノードの可用性情報（すなわち、ビジー、利用可能、非利用可能など）を含むビジーデバイスリストを維持し、および、更新する。ビジーデバイスリストは、例えば、ＭＡＣサブレイヤにおいて実装されてもよく、および、ノード１０２Ｃのメモリに格納されてもよい。
【００６５】
特に、ブロック５０４において、ノード１０２Ｃは、制御チャネルをリスンすることによって（すなわち、無線１０８を制御チャネルに同調させて、制御チャネル上で送信された任意の通信を受信する）、ビジーデバイスリストを維持／更新してもよい。ブロック５０６において、ノード１０２Ｃは、ネットワーク上で他のノードによって送信されたＲＴＳメッセージまたはＣＴＳメッセージなどの１つまたは複数のメッセージをオーバーヒア（overhear）してもよい。オーバーヒアされたメッセージは、可用性情報（例えば、特定のノードが１つまたは複数の特定されたデータチャネル上でデータを送信または受信することを意図すること）を含むリザベーション情報、ならびに、期間情報（duration information）（例えば、送信されることになるデータのサイズ、送信の時間、および／または送信に対する開始時間）を含んでもよい。ブロック５０８において、ノード１０２Ｃは、オーバーヒアされたメッセージに関連付けられた他のノードの可用性および可用性の期間を含むように、そのビジーデバイスリストを更新してもよい。
【００６６】
ブロック５１０において、ノード１０２Ｃは、宛先に送信されることになる情報（例えば、隣接ノードから伝搬される情報、ノードの自身の計測モジュールからの消費情報（consumption information））を受信してもよい。ブロック５１２において、ノード１０２Ｃは、ビジーデバイスリストをクエリし、ブロック５１４において、ビジーデバイスリストにしたがって、宛先へ情報を伝搬することに利用可能であり、および、伝搬することが可能な１つまたは複数の隣接ノードを識別する。１以上の隣接ノードがこの基準を満たす場合、ノード１０２Ｃは、１つまたは複数の他の基準（例えば、リンク品質、ネットワークトラフィック、ランダム選択など）に基づいて、どの隣接ノードに情報を送信するかを選択してもよい。
【００６７】
どの隣接ノードに情報を送信するかを識別した後に、ブロック５１６において、ノード１０２Ｃは、識別された隣接ノードに情報を送信する。特に、ブロック５１８における送信プロセスの１つの例では、ノード１０２Ｃは、制御チャネル上で識別された隣接ノードにＲＴＳメッセージを送信してもよい。ＲＴＳメッセージは、例えば、送信されることになる情報のサイズ、ノード１０２Ｃが情報を送信するのを選ぶ（prefer to）データチャネル、送信が開始される時間、および／または、送信をネゴシエートするのに有用な任意の他の情報を含んでもよい。ＲＴＳを受信した隣接ノードが利用可能である場合、ブロック５２０において、ノード１０２Ｃは、隣接ノードからＣＴＳメッセージを受信する。ＣＴＳメッセージは、識別された隣接ノードが利用可能であることのインジケーション、ＲＴＳで特定されたデータチャネルの確認もしくは送信に対する代替データチャネルの指定、送信の予想される時間（データのサイズおよびリンクに渡っての最大データレートに基づいて）、および／または、送信をネゴシエートするのに有用な任意の他の情報を含んでもよい。最後に、ブロック５２２において、ノード１０２Ｃは、確認されたデータチャネルまたは代替データチャネル上で、識別された隣接ノードに情報を送信する。
【００６８】
方法３００、４００および５００は、ブロック、ならびに、ハードウェア, ソフトウェア、ファームウェアもしくはそれらの組合せで実装することができるオペレーションのシーケンスを表す論理フローチャートにおける矢印の集合として示される。ブロックが示される順序は、限定として解釈されることを意図せず、示された任意の数のオペレーションを任意の順序で組み合わせて、方法または代替の方法を実装することができる。加えて、個々のオペレーションは、本明細書で示される本発明の精神および範囲から逸脱することなく、当該方法から省略されてもよい。ソフトウェアのコンテキストにおいて、コンピュータ命令を表すブロックは、１つまたは複数のプロセッサによって実行されると、定義されたオペレーションを実行する。ハードウェアのコンテキストにおいて、ブロックは、定義されたオペレーションを実行するように構成された１つまたは複数の回路を表してもよい（例えば、特定用途向け集積回路（ＡＳＩＣ））。
【００６９】
＜例示的なプロトコルデータユニット（ＰＤＵ）＞
図６および７は、制御チャネルおよび／またはデータチャネルを介して転送することができるいくつかの例示的なプロトコルデータユニット（ＰＤＵ）を示す。用語ＰＤＵは、本明細書においては、一般に任意の通信、 メッセージ、または図１に示すような通信ネットワーク内の送信を参照する（refer to）のに使用される。用語ＰＤＵは、少なくとも概念的には、オープンシステムインターコネクション（ＯＳＩ）モデルに基づいてもよく、および、例えば、ビット、フレーム、パケット、セグメントなどを備えてもよい。一部のインスタンスでは、ＯＳＩモデルの１つまたは複数のレイヤは、ノード間で１つまたは複数のＰＤＵを転送するために利用されてもよい。例えば、ＯＳＩモデルのデータリンクレイヤは、アーキテクチャ１００における２つ以上のノード１０２間でＰＤＵを転送するのに利用されてもよい。特定の実装では、データリンクレイヤの媒体アクセス制御（ＭＡＣ）サブレイヤは、２つ以上のノード１０２間でＰＤＵを転送するのに利用されてもよい。さらに、一部の実装では、ＰＤＵを転送するのに、キャリアセンス多重アクセス／衝突回避（ＣＳＭＡ／ＣＡ）などのアクセス方法が利用されてもよい。
【００７０】
図６は、ノードがデータを別のノードに送信することを望んでいることを示すのに使用することができる例示的な送信要求（ＲＴＳ）フレーム６００を示しており、図７は、ノードがデータを受信するのに利用可能であることを示すのに使用することができる例示的な送信可（ＣＴＳ）フレーム７００を示している。一部の例では、ＲＴＳメッセージを受信すると、ノードは（利用可能である場合は）、ＣＴＳメッセージを送信することによって応答してもよい。この例では、ＲＴＳおよびＣＴＳフレーム構造は、ＩＥＥＥ８０２．１５．４（ｅ）スタンダードによって部分的に定義される。しかしながら、他の例では、他のＰＤＵ構造が、ＲＴＳメッセージ、ＣＴＳメッセージ、または、マルチチャネル通信ネットワークに関連付けられたリザベーション情報を搬送する他の通信に使用されてもよい。
【００７１】
上述したように、ＲＴＳフレーム６００およびＣＴＳフレーム７００（総称して、データフレーム６００および７００）は、マルチチャネル通信ネットワークのノード間のリンクを適格とし、および、マルチチャネル通信ネットワークのノード間で通信をルーティングするのに使用可能な情報を含む。フレーム６００および７００は、便宜上、図１のアーキテクチャ１００の例示的なネットワーク、ならびに、例示的な方法３００、４００および５００を参照して示される。しかしながら、例示的なフレーム６００および７００は、例示的なアーキテクチャ１００もしくは方法３００、４００および５００での使用に限定されず、他のアーキテクチャおよびデバイスを使用して実装されてもよく、ならびに／または、他の方法を実行してもよい。
【００７２】
図６を参照すると、例示的なＲＴＳフレームが使用されて、隣接ノードに、ノードがデータを送信することを望んでおり、および、別の送信に対して利用可能でないことを通知し、ならびに、特定のデータチャネル、および、１つまたは複数の物理（ＰＨＹ）パラメータ（例えば、データレートおよび／または変調技術）を意図された受信ノードとネゴシエートしてもよい。図６に示すように、ＲＴＳフレームは、以下のフィールド、フレーム制御（ＦＣ）、シーケンス番号、宛先パーソナルエリアネットワーク（ＰＡＮ）識別子、宛先アドレス、ソースＰＡＮ識別子、ソースアドレス、補助セキュリティヘッダ（auxiliary security header）、ペイロード、および、フレームチェックシーケンス（ＦＣＳ）、を含む。ペイロード以外のＲＴＳフレームの上記フィールドの詳細は、当業者にとって周知であり、本明細書においては詳細な説明は行わない。しかしながら、ＲＴＳフレームのペイロードは、上述したルーティング技術、および、他の機能を実装するためにカスタマイズされる。ペイロードは、サイズが可変であってもよく、および、例えば、１つまたは複数の以下のフィールドを含んでもよい。
Ｔｙｐｅ：このフィールドは、フレームのタイプ、例えば、ＲＴＳ、ＣＴＳ、送信不可（ＮＣＴＳ：not-clear-to-send）などを示す。図６の例では、このフィールドは、フレームがＲＴＳフレームであることを示す。
ＨＷ：このフィールドは、ＲＴＳフレームを送信するノードのハードウェアのタイプを示す。タイプは、例えば、デバイスのバージョンもしくは世代、および／または、ノードの能力を判定するのに使用可能な任意の他の情報（例えば、電池式（battery powered）、変調技術、および／またはノードによってサポートされるデータレート）を含んでもよい。
Ｒａｎｋ：このフィールドは、ＲＴＳフレームを送信しているノードの低電力・高損失ネットワーク（ＲＲＬ：Low power and Lossy networks）のランク（知っている場合）に対するルーティングプロトコルを示す。ランクは、隣接ノードからセルルータへのパスのコストを表しており、ならびに、例えば、ＥＴＴを算出する式１のメトリック（metric）を使用して算出されてもよい。より高位のランクは、セルルータからより遠いノードである。このフィールドは、ＭＡＣサブレイヤにおいてルーティングの一貫した検知のためにノードを受信することによって利用されてもよい。
ＤＯＤＡＧ  ＩＤ：このフィールドは、Ｄｅｓｔｉｎａｔｉｏｎ  Ｏｒｉｅｎｔｅｄ  Ｄｉｒｅｃｔｅｄ  Ａｃｙｃｌｉｃ  Ｇｒａｐｈ（ＤＯＤＡＧ）ルート（例えば、ネットワーク境界ルータ（network border router）、セルラルータ、リレーなど）を識別する、ＤＯＤＡＧ識別子（ＩＤ）であり、ＤＯＤＡＧルートを通じて、ＲＴＳを送信しているノードは、中央オフィスまたは他のネットワークコンピューティングデバイスとの通信のために、インターネットなどのバックホールネットワークに接続される。図１のアーキテクチャ１００のコンテキストにおいて、ノードＡは、バックホールネットワークの例であるネットワーク１０６と通信しているアーキテクチャ１００のＤＯＤＡＧルートの例である。ＤＯＤＡＧ＿ＩＤは、ＲＴＳフレームを受信するノードが、ＭＡＣサブレイヤにおいてルーティングの一貫した状態（routing consistency conditions）を検証することによって、ＲＴＳフレームを受理または拒絶することを可能にする。
Ｄｕｒａｔｉｏｎ：このフィールドは、ＲＴＳにおいて特定されるデータフレームを交換することに対するトータルの予想される時間を示す。Ｄｕｒａｔｉｏｎは、特定されたデータフレームを送信するための時間、フレーム間のフレーム間隔時間（ＩＦＳ：inter-frame spacing）（例えば、ＳＩＦＳ、ＧＩＦＳなど）などの待機時間、および、肯定応答（ＡＣＫ）もしくは否定応答（ＮＡＣＫ）の応答を含んでもよい。Ｄｕｒａｔｉｏｎフィールドは、ノードが別のノードと通信するのにビジーであり、したがって、受信するのに利用可能でない期間を判定するのに使用されてもよい。Ｄｕｒａｔｉｏｎフィールドは、図２に示されるビジーデバイスリスト２１４などの、ビジーデバイスリストの「Ｄｕｒａｔｉｏｎ」列に追加する（populate）ために使用されてもよい。
Ｃｈ：このフィールドは、ＲＴＳがチャネルリストを含むかを示すフラグを含む。
Ｃｈａｎｎｅｌｓ  Ｌｉｓｔ：このフィールドは、ＲＴＳフレームを送信するノードに対して利用可能であるチャネルのリストを含む、チャネルリストを含む。ＲＴＳフレームを受信するノードは、利用可能なチャネルからチャネルを選択してもよく、および、ＣＴＳフレーム内部のこの選択されたチャネルを特定してもよい。一部の例では、チャネルリストは、ノードに対して利用可能なすべてのチャネルよりも少ないチャネルを含んでもよい。例えば、直接シーケンススペクトル拡散（ＤＳＳＳ：Direct-sequence Spread Spectrum）変調が採用される場合、チャネルリストは、９１５ＭＨｚ  ＩＳＭ帯域における１３チャネルに限定されてもよい。チャネルリストは、例えば、ＲＴＳを送信したノードとＲＴＳを受信したノードとの間の適格とされたチャネルのリストを備えてもよい。適格とされたチャネルのリストは、図２を参照して示されたノード１０２Ｃのメモリ１１４において維持される適格とされたリンク２１２のリストなどの、ＲＴＳを送信したノード、および／またはＲＴＳを受信したノードのメモリにおいて維持されてもよい。
Ｄａｔｅ  Ｒａｔｅ（ＤＲ）ｐａｒａｍｅｔｅｒ：このフィールドは、ＲＴＳフレームを送信するノードによってサポートされ、および／または、提案される最大データレートを示す。ＲＴＳフレームを受信するノードは、このフィールドを利用して、ノードを送信および受信することの両方が可能なデータレートを判定してもよい。判定されたデータレートは、ＣＴＳフレームを使用して、当該送信しているノードに送信されてもよい。判定されたデータレートは、最大でも、２つのノードのより遅い方の最大データレートに設定される。したがって、ＲＴＳが、受信ノードよりも高いデータレートを提案することが可能な場合、受信ノードは、ＣＴＳフレームを送信するときに、より低いデータレート（最大でも、受信ノードの最大データレート）を設定する。
Ｄａｔａ＿ＩＤ：このフィールドは、データパケットのＩＤを含む。このＩＤは、ＲＴＳフレームの内部で提示されてもよい。このフィールドは、例えば、データパケットが特定のノードによって送信されているが、肯定応答が、データパケットを送信したノードにおいて受信されなかった場合に、利用されてもよい。このケースでは、Ｄａｔａ＿ＩＤとともにデータパケットを送信したノードは、データパケットが受信されなかったと想定してもよく、および、同一のＤａｔａ＿ＩＤに対するＲＴＳフレームを再送信してもよい。一部のケースでは、特定のノードが、受信された最後のＤａｔａ＿ＩＤの番号を記録するときに、特定のノードは、ＣＴＳフレームの代わりに、ＡＣＫフレームで応答してもよく、したがって、データフレームの再送信を回避する。
Ｆ＿ＩＤ：このフィールドは、ＲＴＳフレームのＭＡＣフレームＩＤを含む。ＲＴＳフレームの意図された宛先は、このＲＴＳフレームに応答するＣＴＳフレームにおいて、このＦ＿ＩＤを複製する。ＲＴＳフレームを送信するノードがＣＴＳフレームを受信するときに、当該ノードは、ＣＴＳフレームにおけるＦ＿ＩＤを使用して、ＣＴＳフレームが予想された１つであるかを判定してもよい（すなわち、それは、ノードが以前に送信したＲＴＳフレームへの応答において送信されている）。
ＮＰ：このフィールドは、ＲＴＳフレームを受信するノードと交換されることになるパケットの数を示す。このフィールドは、制御チャネルをリスンすることに切り替わる前に、受信ノードがいくつのパケットを特定されたデータチャネル上でリスンするかを示す。このフィールドはまた、特定のチャネルの可用性を判定する際に有用であってもよい。
Ｐｒｅ＿Ｃｈ：このフィールドは、ノードが図４に示すテストデータフレームなどのデータフレームを交換するのに利用することを選ぶチャネルを示す。この交換に関与されないが、ＲＴＳをオーバーヒアするノードは、このフィールドに基づいてビジーデバイスリスト（例えば、図３を参照して示される）を更新してもよい。デフォルトにより、ＲＴＳフレームの受信側は、可能である場合は、データ交換に対してこのチャネルを選択してもよい。しかしながら、このチャネルがビジーであり、または、リンクの適格とされたチャネルでない場合、受信側ノードはＣＴＳにおいて異なるチャネルを指定してもよい。
ＤＩＲ：このフィールドは、トラフィックがルートからであるか、または、トラフィックがルートに送信されることになるかを示す。ルートからリーフへ送信されるトラフィックは、「ダウンストリーム」と称され、ルートへ送信されるすべての通信は「アップストリーム」と称される。このフィールドは、例えば、アップストリームトラフィックに対しては１に、ダウンストリームトラフィックに対しては０に設定されてもよい。
【００７３】
図７は、ノードがデータを受信するのに利用可能であることを示すのに通信されるフレームの形式での例示的なＣＴＳメッセージ７００を示している。ＣＴＳフレーム７００は、例えば、物理パラメータおよび第１のノードによって選択されたデータチャネルを含んでもよい。一部のインスタンスでは、ＣＴＳフレームは、隣接ノードにＲＴＳを送信しているノードおよびＣＴＳを送信しているノードが利用可能であり、ならびに、選択されたデータチャネルが、特定の時間の間、ビジーであることを通知するのに利用される。図７の例では、ＣＴＳフレームは、以下のフィールド、ＦＣ、シーケンス番号、宛先ＰＡＮ識別子、宛先アドレス、ソースＰＡＮ識別子, ソースアドレス、補助セキュリティヘッダ、ペイロード、および、ＦＣＳを含む。ペイロード以外のＣＴＳフレームの上記フィールドの詳細は、当業者にとって周知であり、本明細書においては詳細な説明は行わない。しかしながら、ＣＴＳフレームのペイロードは、上述したルーティング技術、および、他の機能を実装するためにカスタマイズされる。ＣＴＳフレームのペイロードは、サイズが可変であってもよく、および、例えば、１つまたは複数の以下のフィールドを含んでもよい。
Ｔｙｐｅ：このフィールドは、図６を参照して示されたのと同様の情報を示してもよい。図７の例では、このフィールドは、フレームがＣＴＳフレームであることを示す。
ＨＷ：このフィールドは、ＲＴＳフレームを受信したノード（すなわち、当該ノードはＣＴＳフレームを送信する）のハードウェアパラメータ（例えば、デバイスのタイプ、デバイスのバージョンまたは世代）を含む。
Ｒａｎｋ：このフィールドは、ＲＴＳフレームの対応するフィールドに類似しているが、ＣＴＳフレームに適用されるものに類似してもよい。このフィールドは、例えば、図２で示す適格化リンクリスト２１２における相対品質にしたがって、リンクを順位付けする際に使用されてもよい。
ＤＯＤＡＧ＿ＩＤ：このフィールドは、ＲＴＳフレームの対応するフィールドに類似しているが、ＣＴＳフレームに適用されるものに類似してもよい。特に、このフィールドは、ＭＡＣサブレイヤにおいてルーティングの一貫した状態を検証することによって、ＣＴＳフレームを受信して、受理または拒絶するノードに対して選択を提供するＤＯＤＡＧ識別子である。
Ｄｕｒａｔｉｏｎ：このフィールドは、ＲＴＳフレームの対応するフィールドに類似しているが、ＣＴＳフレームに適用されるものに類似してもよく、図２のビジーデバイスリスト２１４を維持するためなど、可用性および可用性の期間を判定するのに使用されてもよい。
Ｃｈａｎｎｅｌ：このフィールドは、ＲＴＳフレームを受信したノードによって選択されるデータチャネルを示している。
ＤＲ：このフィールドは、ＲＴＳフレームを受信したノードによって選択されるデータレートを示している。データレートは、ＲＴＳにおいて特定されたデータレートと同一であってもよく（受信ノードがデータレートに順応できる（capable of the data rate）場合）、または、異なってもよい（受信ノードがデータレートに順応できない場合）。このデータレートは、データチャネル上で図４を参照して示されたテストデータパケットなどのデータを転送するために実装されてもよい。
Ｆ＿ＩＤ：このフィールドは、ＲＴＳフレームのＦ＿ＩＤ値と同一であってもよいＣＴＳフレームのＭＡＣフレームＩＤを含む。
【００７４】
上述したように、ＲＴＳおよびＣＴＳフレーム６００および７００は、単に、本明細書で示されたルーティング技術を実装するために使用することができる一部のＰＤＵの例である。他の実施形態では、種々の他のＰＤＵが上述したルーティング技術を実装するのに採用されてもよい。
【００７５】
＜結論＞
本願は、実施形態が特定の構造的な特徴および／または方法的な動作を有することを説明したが、特許請求の範囲は、必ずしも説明した特定の特徴または動作に限定されないことが理解される。むしろ、当該特定の特徴および動作は、単に、本願の特許請求の範囲に含まれる一部の実施形態を例示するものである。
【図１】
0005938480.tif 000004
【図２】
0005938480.tif 000005
【図３】
0005938480.tif 000006
【図４】
0005938480.tif 000007
【図５】
0005938480.tif 000008
【図６】
0005938480.tif 000009
【図７】
0005938480.tif 000010