(57)【要約】  ワイヤレスネットワーク、特にワイヤレスアドホックまたはメッシュネットワークにおけるノード間通信方法を提供する。相異なる周波数帯の複数のワイヤレスチャネルが設けられ、ノードは上記相異なるチャネル上で動作可能である。本方法は、上記ノードのそれぞれに、該ノードが通常存在するホームチャネルが割り当てられ、自己のホームチャネルを退出して上記複数のチャネルのうちの別のチャネル（一時動作チャネル）に切り替わるノードが、該一時動作チャネルに関する情報を上記ノードのホームチャネル上に提供することを特徴とする。
2011528880.tif 000002
【特許請求の範囲】
【請求項１】
ワイヤレスネットワーク、特にワイヤレスアドホックまたはメッシュネットワークにおけるノード間通信方法において、相異なる周波数帯の複数のワイヤレスチャネルが設けられ、前記ノードは前記相異なるチャネル上で動作可能であり、
前記ノードのそれぞれに、該ノードが通常存在するホームチャネルが割り当てられ、自己のホームチャネルを退出して前記複数のチャネルのうちの別のチャネルすなわち一時動作チャネルに切り替わるノードが、該一時動作チャネルに関する情報を前記ノードのホームチャネル上に提供することを特徴とする、ワイヤレスネットワークにおけるノード間通信方法。
【請求項２】
ノードが「アイドルまたは受信」動作状態および「送信」動作状態を有し、ノードは、「アイドルまたは受信」動作状態にあるとき、自己のホームチャネル上に滞在することを特徴とする請求項１に記載の方法。
【請求項３】
送信ノードと受信ノードとの間の協調が、コネクションの最初に一度行われることを特徴とする請求項１または２に記載の方法。
【請求項４】
送信ノードが、同じホームチャネルを有する受信ノードに対する未処理パケットを有する場合、送信ノードが自己のホームチャネル上に同期要求をブロードキャストすることを特徴とする請求項１ないし３のいずれか１項に記載の方法。
【請求項５】
前記送信ノードと前記受信ノードとの間のデータ交換が、前記受信ノードが同期応答をブロードキャストした後に開始されることを特徴とする請求項４に記載の方法。
【請求項６】
選択されたチャネルが、相異なるチャネル上に存在するノードのための最初の接点となるランデブーチャネルとして設けられることを特徴とする請求項１ないし５のいずれか１項に記載の方法。
【請求項７】
前記ランデブーチャネルが、ネットワーク管理者によって事前に指定されることを特徴とする請求項６に記載の方法。
【請求項８】
送信ノードが、別のホームチャネルを有する受信ノードに対する未処理パケットを有する場合、自己のホームチャネル上にチャネル転送メッセージをブロードキャストすることを特徴とする請求項１ないし７のいずれか１項に記載の方法。
【請求項９】
前記ノードが、前記ランデブーチャネル上に前記チャネル転送メッセージを連続的にブロードキャストすることを特徴とする請求項８に記載の方法。
【請求項１０】
前記送信ノードが前記受信ノードのホームチャネルを知っている場合、前記送信ノードが、該チャネルに切り替え、該チャネル上に同期要求をブロードキャストすることを特徴とする請求項８または９に記載の方法。
【請求項１１】
前記受信ノードが自己のホームチャネル上にある場合、前記受信ノードが前記送信ノードに対して同期応答によって応答することを特徴とする請求項１０に記載の方法。
【請求項１２】
前記受信ノードが自己のホームチャネル上にない場合、前記受信ノードのホームチャネル上の他のノードが前記送信ノードに対してチャネル転送メッセージによって応答することを特徴とする請求項１０に記載の方法。
【請求項１３】
前記送信ノードは、応答を受信しない場合、および／または、前記受信ノードのホームチャネルを知らない場合、一連のランデブーチャネルで連続的に前記受信ノードを探索することを特徴とする請求項８ないし１２のいずれか１項に記載の方法。
【請求項１４】
前記送信ノードは、前記ランデブーチャネルのいずれの上でも前記受信ノードを発見しない場合、残りのデータチャネル上で前記受信者を探索し始めることを特徴とする請求項１３に記載の方法。
【請求項１５】
ノードのホームチャネルが、該ノードの識別子に基づいて指定されることを特徴とする請求項１ないし１４のいずれか１項に記載の方法。
【請求項１６】
ノードは、前記ホームチャネルすなわち現ホームチャネルが輻輳していることを検知した場合、別のホームチャネルすなわち新しいホームチャネルをランダムに選択することを特徴とする請求項１ないし１５のいずれか１項に記載の方法。
【請求項１７】
ノードは、新しいホームチャネルを選択した場合、チャネル転送メッセージをブロードキャストすることにより、自己の新しいホームチャネルをアナウンスすることを特徴とする請求項１ないし１６のいずれか１項に記載の方法。
【請求項１８】
前記マルチチャネル通信の実装が、ＩＥＥＥ８０２．１１標準に準拠したハードウェアに基づくことを特徴とする請求項１ないし１７のいずれか１項に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ワイヤレスネットワーク、特にワイヤレスアドホックまたはメッシュネットワークにおけるノード間通信方法に関する。このネットワークでは、相異なる周波数帯の複数のワイヤレスチャネルが設けられ、前記ノードは前記相異なるチャネル上で動作可能である。
【背景技術】
【０００２】
近年、住宅地、キャンパス、地域コミュニティ、さらには大都市圏においてワイヤレスインフラストラクチャを整備するために使用可能な新技術として、アドホックネットワークおよびワイヤレスメッシュネットワーク（wireless mesh network, ＷＭＮ）が登場している。アドホックネットワークおよびＷＭＮにとって、ＩＥＥＥ８０２．１１は魅力的なワイヤレス技術である。というのは、ＩＥＥＥ８０２．１１は、成熟し、安価で、広く利用可能なためである。ＩＥＥＥ８０２．１１アドホックモードでは多くの新規なアプリケーションが可能である。例えば、メッシュネットワーキング、将来のホームネットワーキング、自動車間、および自動車−インフラストラクチャ間の通信等が挙げられる。ＩＥＥＥ８０２．１１に基づくアドホックネットワークおよびＷＭＮにおける重要な問題として、すべてのノードが単一チャネル上で動作するため、ネットワーク容量がかなり制限されることがある。その結果、アドホックネットワークの容量はチャネル容量に制限される。
【０００３】
一般に、アドホックネットワークおよびＷＭＮにおいて複数の周波数帯を活用することによる容量向上には、ＭＡＣ（メディアアクセス制御）拡張およびルーティング拡張という２つのアプローチがある。ルーティング拡張（例えば非特許文献１および非特許文献２に記載）は通常、ノードが、相異なるチャネルに同調された相異なるＮＩＣ（ネットワークインタフェースカード）を備えた複数のワイヤレスネットワークインタフェースを有することを必要とする。
【０００４】
これに対して、ＭＡＣ拡張は通常、１つのネットワークインタフェースしか必要としないので、より魅力的である。マルチチャネルＭＡＣプロトコルのようなＭＡＣ拡張は、ワイヤレスアドホックネットワークにおけるノードが複数のワイヤレスチャネル上で動作することが可能なので、最近かなり注目されている。マルチチャネルＭＡＣの主要な課題は、起こり得る干渉を避けるために相異なるチャネル上でノードが動作するようにし、相異なるチャネル上で動作する可能性のあるノード間の協調を実現する必要があることである。最近、いくつかのマルチチャネルＭＡＣプロトコルが提案されており、さまざまな方法でノード間協調の課題に対処している。
【０００５】
１．例えば、動的チャネル割当（Dynamic Channel Assignment, ＤＣＡ）プロトコルは、ノードごとに２つの無線インタフェースを使用して、１つの制御チャネルおよび複数のデータチャネル上で動作する（非特許文献３参照）。ＤＣＡでは、一方の無線インタフェースが制御チャネルに同調され、制御インタフェースと呼ばれる。他方の無線インタフェースはデータインタフェースと呼ばれ、データパケットおよび確認応答（acknowledgment）を送信するために、データチャネルのうちの１つに動的に切り替えられる。ＤＣＡにおける各ノードは、全データチャネルに対するチャネル使用リスト（channel usage list）ＣＵＬを維持管理する。ノードは、制御チャネル上で傍受する制御フレームに基づいて自己のＣＵＬを更新する。また、各ノードは、自己のＣＵＬから動的に計算する空きチャネルリスト（free channel list）ＦＣＬも維持管理する。ＤＣＡは、チャネル予約のために、制御チャネル上で、送信要求（request-to-send, ＲＴＳ）、送信可（clear-to-send, ＣＴＳ）、および予約（reservation, ＲＥＳ）という３種の制御フレームを使用する。ホストＡがホストＢへデータを送信したいとき、ホストＡは自己のＦＣＬをＲＴＳフレームに挿入し、そのフレームをホストＢへ送信する。ホストＢは、ホストＡのＦＣＬを自己のＦＣＬと照合し、利用可能なデータチャネル（もしあれば）を選択し、ＣＴＳフレームをホストＡへ返送する。そして、ホストＡは、指定した期間の間に、選択されたデータチャネルを近隣が使用しないように、ＲＥＳフレームを送信する。ホストＡおよびホストＢの近隣は、制御チャネル上で傍受するＣＴＳおよびＲＥＳフレームに基づいて、自己のＣＵＬを更新することができる。
【０００６】
２．マルチチャネルＭＡＣ（ＭＭＡＣ）プロトコルは、ただ１つの無線インタフェースを使用して、複数のデータチャネル上で動作する（非特許文献４に記載）。ＭＭＡＣは、ノード間の時刻同期を必要とし、時間をビーコン間隔に分割する。各ビーコン間隔は、ＡＴＩＭウィンドウと呼ばれる小さいウィンドウで開始される。ＭＭＡＣは、「ＡＴＩＭ」（Ad hoc Traffic Indication Message）という用語をＩＥＥＥ８０２．１１省電力モードから借用しているが、ＡＴＩＭはＭＭＡＣにおいては異なる目的のために使用される。ＭＭＡＣにおける各ノードは、ノード近傍内のチャネル使用を把握する選好チャネルリスト（Preferable Channel List, ＰＣＬ）と呼ばれるデータ構造体を維持管理する。ＭＭＡＣでは、チャネルはノードにおいて高選好、中選好、低選好という３つの状態を取り得る。高選好は、当該ノードが現在のビーコン間隔のためにこのチャネルをすでに選択しており、次のビーコン間隔までこのチャネルを選び続けなければならないことを示す。中選好は、このチャネルが当該ノードの伝送範囲内の近隣によって取られていないことを意味する。低選好は、当該ノードの伝送範囲内の少なくとも１つの近隣によってこのチャネルがすでに取られていることを示す。また、ノードは、ビーコン間隔内の各チャネルの使用を記録するチャネルごとのカウンタも維持管理する。これらのカウンタによって、ノードは、チャネルの負荷分散を行うことができる。
【０００７】
ＡＴＩＭウィンドウの期間中、すべてのノードは、ビーコンおよびＡＴＩＭフレームを交換するためにデフォルトチャネルに切り替わる（デフォルトチャネルは、ＡＴＩＭウィンドウの外部でのデータ交換にも使用可能である）。ホストＡがホストＢへデータを送信したいとき、ホストＡは自己のＰＣＬをＡＴＩＭフレームに挿入し、それをホストＢへ送信する。ホストＢは、ホストＡのＰＣＬを自己のＰＣＬと比較して、１つのチャネルを選択し、ＡＴＩＭ−ＡＣＫフレームをホストＡへ返送する。ホストＡが、別のチャネルをすでに選択しているのでホストＢによって指定されたチャネルを選択できない場合、ホストＡは、次のビーコン間隔まで待機しなければならない。そうでない場合、ホストＡは、選択されたチャネルでＡＴＩＭ−ＲＥＳフレームを送信する。これにより、その伝送範囲内の近隣は自己のＰＣＬを更新することができる。ＡＴＩＭウィンドウの後、ホストＡとホストＢは、選択されたチャネルに切り替えてデータを交換する。
【０００８】
３．ＳＳＣＨ（Slotted Seeded Channel Hopping）は、ただ１つの無線インタフェースを使用して、複数のデータチャネル上で動作する（非特許文献５に記載）。ＳＳＣＨは、ノード間の時刻同期を必要とし、時間をスロットに分割する。ＳＳＣＨにおいて、各ノードは、当該ノードが後続スロットで切り替わることを予定しているチャネルのリストを含む「チャネルスケジュール」を維持管理する。ノードのチャネルスケジュールは、現チャネルと、チャネルを更新するためのルールのセットとしてコンパクトに表現される。ＳＳＣＨは、ルールのセットが、４つの（チャネル，シード）のペアからなるセットとして表現されることを提案している。各ノードは、各スロットにおいて、自己の４つの（チャネル，シード）のペアのセットのそれぞれについて、次のチャネル更新を実行する。
チャネルｉ  ←  （チャネルｉ＋シードｉ）  ｍｏｄ  Ｎ
ただし、ｉは０〜３であり、Ｎは利用可能な直交チャネルの個数である。例えば、Ｎは、ＩＥＥＥ８０２．１１ｂでは３であり、ＩＥＥＥ８０２．１１ａでは１３である。ＳＳＣＨにおいて、各ノードは、自己のチャネルスケジュールを頻繁にブロードキャストし、他のノードのチャネルスケジュールを把握する。ホストＡがホストＢへデータを送信したいとき、ホストＡは、ホストＢのチャネルスケジュールを採用することによって、ホストＢに従うことができる。
【０００９】
４．非同期マルチチャネル協調プロトコル（Asynchronous Multi-channel Coordination Protocol, ＡＭＣＰ）は、ノードごとにただ１つの無線インタフェースしか必要とせず、ノード間の時刻同期を必要とせずに、Ｎ個のデータチャネル上で動作する（非特許文献６参照）。しかし、ＡＭＣＰは、専用の制御チャネルを使用し、その制御チャネル上で、ノードどうしが制御フレームを交換してチャネル予約を交渉する。ＡＭＣＰにおいて、各ノードは、Ｎ個のデータチャネルに対応するＮ個のエントリを有するチャネルテーブルを維持管理する。各エントリは、チャネルが利用可能であるか、あるいは、そのチャネルが伝送範囲内の他のノードによってどのくらい長く使用されているかを示す。また、各ノードは、０からＮまでの値を取り得る変数ｐｒｅｆｅｒを維持管理する。ｐｒｅｆｅｒは、０でない場合、当該ノードが選好するデータチャネルへのインデックスを含む。０の場合、ｐｒｅｆｅｒは、当該ノードが選好を有していないことを示す。
【００１０】
ホストＡがホストＢへデータパケットを送信したいとき、まず、競合するデータチャネルを選択する。ホストＡの変数ｐｒｅｆｅｒが０でなく、このチャネルが利用可能な場合、ホストＡはこのチャネルを選択する。そうでない場合、ホストＡは、自己の利用可能なデータチャネルのうちの１つをランダムに選択する。ホストＡは、選択されたデータチャネルへのインデックスをＲＴＳフレームに挿入し、それをホストＢへ送信する。ホストＢがそのＲＴＳフレームを受信すると、ホストＢは、そのチャネルがホストＢにとって利用可能である場合には、選択されたデータチャネルへのインデックスを有する「確認ＣＴＳ」を送信することができる。そうでない場合、ホストＢは、自己の利用可能なデータチャネルのリストを有する「拒否ＣＴＳ」を送信する。ホストＡは、「確認ＣＴＳ」を受信した場合、選択されたチャネルに切り替え、データパケットをホストＢへ送信する。そうでない場合、ホストＡは、ホストＡおよびホストＢの双方にとって利用可能なチャネルを選択し、新しいＲＴＳフレームをホストＢへ送信する。ホストＡおよびホストＢの伝送範囲内の他のホストは、ＲＴＳおよびＣＴＳフレームを傍受し、それに応じて、チャネル利用可能性に対する自己のチャネルテーブルを更新することができる。
【００１１】
マルチチャネルＭＡＣでもノードは周波数ダイバーシティを活用することができ、ワイヤレスアドホックネットワークの容量は単一チャネルの容量にはもはや制限されないが、上記のプロトコルは、低いチャネル切り替え遅延およびノード間の精密なクロック同期という、２つのかなり非現実的な仮定に依拠していることに注意すべきである。これらの仮定の問題点は次の通りである。第１に、精密なクロック同期を実現することは、可能ではあるがかなり困難であり、相当の実装オーバーヘッドを必要とし、これはアドホックネットワークのスケーラビリティに影響を及ぼす。第２に、ＧＰＳ装置を用いた同期は、製造コストおよび実装の複雑さを増大させ、また、屋内配備には使用できない。第３に、実測研究で指摘されているように、市販のＩＥＥＥ８０２．１１ハードウェアでのチャネル切り替え遅延は、従来のマルチチャネルＭＡＣソリューションで使用されている想定値よりも非常に高い。例えば、想定値は通常、数十ないし数百マイクロ秒の範囲内にあるのに対して、実測値が示したところでは、チャネル切り替え遅延はＬｉｎｕｘおよびＷｉｎｄｏｗｓ(登録商標）において数ミリ秒である（例えば非特許文献２あるいは非特許文献７に記載）。これらの理由により、提案されているマルチチャネルＭＡＣプロトコルは、現在の実用的制限のもとではうまく機能しない。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】R. Draves et al.: Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks（マルチ無線マルチホップワイヤレスメッシュネットワークにおけるルーティング）, ACM MobiCom’04, ２００４年９月
【非特許文献２】A. Raniwala et al.: Architecture and Algorithms for an IEEE 802.11-Based Multi-Channel Wireless Mesh Network（ＩＥＥＥ８０２．１１に基づくマルチチャネルワイヤレスメッシュネットワークのためのアーキテクチャおよびアルゴリズム）, IEEE Infocom 2005, ２００５年３月
【非特許文献３】Wu et al., A new multi-channel MAC protocol with on-demand channel assignment for multi-hop mobile ad hoc networks（マルチホップモバイルアドホックネットワークのためのオンデマンド型チャネル割当を備えた新しいマルチチャネルＭＡＣプロトコル）, ISPAN’00, ２０００年１２月
【非特許文献４】J. So et al.: Multi-Channel MAC for ad hoc networks: Handling multi-channel hidden terminals using a single transceiver（アドホックネットワークのためのマルチチャネルＭＡＣ：単一のトランシーバを用いてマルチチャネル隠れ端末を処理する）, ACM MobiHoc’04, ２００４年５月
【非特許文献５】P. Bahl et al.: SSCH: Slotted seeded channel hopping for capacity improvement in IEEE 802.11 ad-hoc wireless networks（ＳＳＣＨ：ＩＥＥＥ８０２．１１アドホックワイヤレスネットワークにおける容量向上のためのスロット化シード付きチャネルホッピング）, ACM MobiCom’04, ２００４年９月
【非特許文献６】J. Shi et al.: Starvation mitigation through multi-channel coordination in CSMA based wireless networks（ＣＳＭＡに基づくワイヤレスネットワークにおけるマルチチャネル協調による枯渇軽減）, ACM MobiHoc’06, ２００６年５月
【非特許文献７】H. Wu et al., Proactive Scan: Fast Handoff with Smart Triggers for 802.11 Wireless LAN（積極的スキャン：８０２．１１ワイヤレスＬＡＮのためのスマートトリガを備えた高速ハンドオフ）, IEEE Infocom 2007, ２００７年５月
【発明の概要】
【発明が解決しようとする課題】
【００１３】
したがって、本発明の目的は、頭書のようなワイヤレスネットワークにおけるノード間通信方法において、上記の非現実的仮定が不要となるような改良およびさらなる展開を行うことである。また、本方法は、市販のＩＥＥＥ８０２．１１ハードウェアでの実施が可能であるという意味で、実用的となるものである。
【課題を解決するための手段】
【００１４】
本発明によれば、上記の目的は、請求項１の構成を備えた方法によって達成される。この請求項に記載の通り、本方法は、以下のことを特徴とする。すなわち、前記ノードのそれぞれに、該ノードが通常存在するホームチャネルが割り当てられ、自己のホームチャネルを退出して前記複数のチャネルのうちの別のチャネル（一時動作チャネル）に切り替わるノードが、該一時動作チャネルに関する情報を前記ノードのホームチャネル上に提供する。
【００１５】
本発明によって初めて認識されたこととして、ワイヤレスネットワークにおける（例えばモバイル）ノード間の実用的通信方法は、非同期マルチチャネルホッピングによって実現することができる。非同期とは、ノードが非同期的に動作すること、すなわち、時刻同期が不要なことを意味する。本発明は、各ノードにホームチャネルを割り当てることを、ノードが自己のホームチャネルを退出する場合の情報メカニズムとともに提案する。すなわち、自己のホームチャネルを退出して別のチャネル（一時動作チャネルという）に切り替わるノードが、一時動作チャネルに関する情報を自己のホームチャネル上に提供することで、このノードが、他のノードによって容易かつ効率的に発見可能となるようにする。ノードの一時動作チャネルに関する情報の効率的提供の結果として、複数の周波数帯を活用することができ、それにより、ＩＥＥＥ８０２．１１に基づくネットワークの容量が大幅に向上する。また、本発明による方法は、ネットワークノードごとにただ１つのネットワークインタフェースしか必要としない。このため、ネットワークノードは、相異なる動作チャネル間で切り替わることが可能である。
【００１６】
好ましい実施形態によれば、ノードは「アイドルまたは受信」動作状態および「送信」動作状態を有することが可能である。ここでノードは、「アイドルまたは受信」動作状態にあるとき、自己のホームチャネル上に滞在する。「アイドルまたは受信」動作状態とは、ノードが送信すべきパケットを有していないとき、すなわち、ノードがアイドルであるかまたはパケットを受信中であるときに、ノードがこの状態にあることを意味する。これに対して、ノードが別のノードに対する未処理パケットを有するとき、ノードは「送信」状態にある。結果として、ノードは、別のノードに対する未処理パケットを有するとき、「アイドルまたは受信」状態から「送信」状態に遷移する。
【００１７】
有利な態様として、送信ノードと受信ノードとの間の協調が、コネクションの最初に一度行われる。マルチチャネルＭＡＣのこのような実装は、クロック同期に依拠していないことから、実装の複雑さがより低く、より堅牢で費用効果が高いので、魅力的である。
【００１８】
あるノード（送信ノード）が、送信ノードと同じホームチャネルを有する別のノード（受信ノード）に対する未処理パケットを有する場合、送信ノードが自己のホームチャネル上に同期要求をブロードキャストするようにしてもよい。受信ノードは、同期要求を受信すると（受信ノードは同じ（ホーム）チャネル上で動作（すなわち送受信）しているのでこれが可能である）、対応する同期応答によって応答することができる。このハンドシェイクの後、これらの２つのノードはデータ交換を開始することができる。
【００１９】
特に好ましい実施形態によれば、選択されたチャネルが、相異なるチャネル上に存在するノードのための接点となるランデブーチャネルとして設けられる。ランデブーチャネルは、正規のＩＥＥＥ８０２．１１チャネルにほかならないので、データ交換のために従来通り使用可能である。しかし、任意の２つのノードがそれらのホームチャネル上で互いを発見しない場合には、それらのノード間の最初の接点としても作用する。一連のランデブーチャネルは、ネットワーク管理者によって事前に指定されてもよいし、単に、利用可能なチャネルのうちのある特定の順序でのサブセットであってもよい。
【００２０】
あるノード（送信ノード）が、送信ノードとは別のホームチャネルを有する別のノード（受信ノード）に対する未処理パケットを有する場合、送信ノードは、自己のホームチャネルを一時的に退出し、別のチャネル上にある受信ノードを発見し連絡をとろうとしなければならない。このような場合、送信ノードは、自己のホームチャネルを退出する前に、自己のホームチャネル上にチャネル転送メッセージをブロードキャストするようにしてもよい。チャネル転送メッセージは、送信ノードが切り替わる先の新しいチャネルを示すことにより、送信ノードのホームチャネル上に存在する他のノードに、送信ノードをどこで見つければよいかを通知するようにしてもよい。より包括的な情報ポリシーとして、送信ノードは、ランデブーチャネル上にもチャネル転送メッセージを連続的にブロードキャストしてもよい。衝突およびビット誤りを考慮して、送信ノードは、上記のチャネルのそれぞれで、自己のチャネル転送メッセージを数回再送してもよい。
【００２１】
送信ノードとは別のホームチャネルを有する受信ノードの発見プロセスに関して、次の２つの場合を区別することができる。送信ノードが受信ノードのホームチャネルを知っている場合、送信ノードは、単にそのチャネルに切り替え、そのチャネル上に同期要求をブロードキャストすることにより受信ノードと連絡をとろうとすればよい。そして、受信ノードは、自己のホームチャネル上にある場合、この同期要求に対して、同期応答によって応答すればよい。上記ですでに述べたように、このようなハンドシェイクの後、データ交換を開始することができる。他方、受信ノードが自己のホームチャネル上に（一時的に）ない場合、受信ノードのホームチャネル上にあって受信ノードの現チャネルに関する知識を有する他のノードが、送信ノードに対して、「無償の」チャネル転送メッセージによって応答してもよい。上記知識は、受信ノードもまた、自己のホームチャネルを退出する前に、自己のホームチャネル上にチャネル転送メッセージをブロードキャストすることにより、そのチャネル上の他のノードに対して、受信ノードの新しい（一時）動作チャネルを通知した結果であってもよい。
【００２２】
受信ノードのホームチャネル上で応答が（受信ノード自身による応答も、そのチャネル上の他のどのノードによる応答も）得られない場合、および／または、前記受信ノードのホームチャネルを知らない場合、送信ノードは、一連のランデブーチャネルで連続的に受信ノードを探索してもよい。この理由は、受信ノードがそのホームチャネル上にない場合には、受信ノードはその現チャネルに関するヒントを（上記で説明したように）ランデブーチャネル上に提供しているかもしれないからである。すなわち、送信ノードは、所定数の同期要求を送信した後、同期応答またはチャネル転送メッセージを受信しない場合、一連のランデブーチャネルで受信ノードを探索しようとしてもよい。
【００２３】
送信者が、どのランデブーチャネル上でも同期応答またはチャネル転送メッセージを受信しない場合、さらに送信ノードは、残りのデータチャネル上で受信ノードを探索し始めてもよい。しかし、本発明によれば、自己のホームチャネルを退出するノードによって情報が提供されるので、この場合はまれにしか起こらないはずであり、フェイルセーフ解決策を提供するための最後の手段としてのみ意味を有する。
【００２４】
ホームチャネルの決定および割当の信頼性を高めるため、各ノードは最初に自己のノード識別子（例えばＭＡＣアドレス）に基づいて自己のホームチャネルを選択してもよい。しかし、ノードは、自己の現ホームチャネルが輻輳していることを検知したときには、別のホームチャネルをランダムに選択してもよい。
【００２５】
この場合にも、ノードは、自己の旧ホームチャネル上に、そして場合によってはさらにランデブーチャネル上に、対応するチャネル転送メッセージをブロードキャストすることで、自己の新ホームチャネルをアナウンスしてもよい。不安定性を避けるため、ノードは、自己の新ホームチャネルもまた輻輳していることを検知した場合には、別の新ホームチャネルを選択する前に、最小の時間間隔の間、自己の新ホームチャネルを使用するようにしてもよい。
【００２６】
好ましい実施形態によれば、前記マルチチャネル通信の実装は、ＩＥＥＥ８０２．１１標準に準拠したハードウェアに基づく。本発明が提案する非同期マルチチャネルホッピングのためのプロトコルは、ＩＥＥＥ８０２．１１のＭＡＣプロトコルに対する拡張として実装可能である。これに関して注意すべき重要な点であるが、３つの新しい制御フレームが導入されているが（「同期要求」、「同期応答」、および「チャネル転送メッセージ」）、それらは標準のＩＥＥＥ８０２．１１の枠内で実装可能である。例えば、これらのフレームは、ＩＥＥＥ８０２．１１アクションフレームに埋め込まれた情報要素としてエンコード可能である。このアプローチにより、本発明が提案する方法は、旧式のＩＥＥＥ８０２．１１ノードとの互換性がある。というのは、それらのノードは、本発明に関連する制御メッセージをエンコードする情報要素を無視すればよく、それでもなお、ＩＥＥＥ８０２．１１ＭＡＣを使用する本発明を実装したノードとともに動作可能だからである。
【００２７】
本発明を好適な態様で実施するにはいくつもの可能性がある。このためには、一方で請求項１に従属する諸請求項を参照しつつ、他方で図面により例示された本発明の好ましい実施形態についての以下の説明を参照されたい。図面を用いて本発明の好ましい実施形態を説明する際には、本発明の教示による好ましい実施形態一般およびその変形例について説明する。
【図面の簡単な説明】
【００２８】
【図１】基本的な適用シナリオにおける本発明による方法の第１実施形態を模式的に例示する図である。
【図２】ホームチャネル経由でのチャネル転送を備えた、本発明による方法の第２実施形態を模式的に例示する図である。
【図３】ランデブーチャネル経由でのチャネル転送を備えた、本発明による方法の第３実施形態を模式的に例示する図である。
【発明を実施するための形態】
【００２９】
基本的に、本発明による方法は、非同期マルチチャネルホッピングプロトコル（asynchronous multi-channel hopping protocol, 以下ではＡＭＨＰと称する）と呼ぶことができる。本発明の重要な側面として、ＡＭＨＰは、同じワイヤレスネットワークに属するノードが相異なるチャネル上に存在することが可能であり、それらが互いを発見するための分散型メカニズムを備えている。これにより、ワイヤレスネットワークの大幅な容量向上を達成することができる。
【００３０】
以下では、まず、実用的なマルチチャネルＭＡＣの諸要件と、これらの要件の動機を説明する。主要な動機は次の通りである。
【００３１】
１）チャネル間負荷分散：
マルチチャネルＭＡＣの主要な目標は、相異なる直交チャネル上で互いに競合するフローを分散させることによって、アドホックネットワークの容量を向上させることである。そこで、マルチチャネルＭＡＣは、すべての利用可能なチャネルにわたる負荷分散を実現し、単一チャネル上のボトルネックを回避することが重要となる。
【００３２】
２）ノード間協調の促進：
マルチチャネルＭＡＣのもう１つの重要な目標は、相異なるチャネル上で動作する可能性のあるノード間の協調を実現することである。このため、マルチチャネルＭＡＣは、ノードどうしが迅速かつ容易に互いを発見するための効率的なメカニズムを備える必要がある。
【００３３】
３）クロック同期の不使用：
いくつかのマルチチャネルＭＡＣプロトコルでは、相異なるチャネル上で動作する可能性のあるノード間の協調を実現するために、精密なクロック同期を必要とする。クロック同期は実現するのがかなり複雑である。そのため、クロック同期に依拠しないマルチチャネルＭＡＣのほうが、実装の複雑さがより低く、より堅牢で費用効果が高いので、より魅力的である。
【００３４】
４）チャネル切り替えオーバーヘッドの低減：
従来のいくつかのマルチチャネルＭＡＣプロトコルは、チャネル切り替え遅延がかなり小さい（数十ないし数百マイクロ秒）ことを想定している。この想定であれば、頻繁にチャネル切り替えをしても、生じるパフォーマンスオーバーヘッドは少しだけなので、ノード間協調を実現するために使用可能である。しかし、実測値が示したところでは、市販のＩＥＥＥ８０２．１１ハードウェアでのチャネル切り替え遅延はかなり大きい（数ミリ秒）。この実用上の制限のもとでは、頻繁なチャネル切り替えを回避するマルチチャネルＭＡＣプロトコルを設計することが重要である。
【００３５】
ＡＭＨＰは、ノードが相異なるワイヤレスチャネル上で動作することを可能にすることによって、要件１）を満たす。また、ＡＭＨＰは、ノードが自己の現在の動作チャネルが過負荷であることを検知したときに、異なる動作チャネルを選択することを可能にすることによって、負荷分散を実現する。
【００３６】
要件２）を満たすため、ＡＭＨＰは、ノードどうしが互いを発見するための２つの分散型メカニズムを使用することによって、ノード間の効率的協調を容易にする。第１に、各ノードは「ホームチャネル」を有する。ノードは通常、ホームチャネルに存在することにより、他のノードがそのノードを容易に発見することができる。第２に、ノードは、自己の「ホームチャネル」を退出するとき、自己の一時チャネルに関する情報を提供する。
【００３７】
ＡＭＨＰは、ノードどうしが非同期的に動作することを可能にすることによって、要件３）を満たす。
【００３８】
要件４）を満たすため、ＡＭＨＰは、コネクションの最初に一度だけ初期切り替えオーバーヘッドを受ける。この切り替えオーバーヘッドは、その後にさらなる切り替えが不要なので、コネクションの継続時間とともに低減される。「パケット単位」での動作や周期的チャネル切り替えの実行の代わりに、ＡＭＨＰは、「コネクション単位」で、すなわち比較的長い時間スケール（数百ミリ秒）で動作する。この時間スケールで、ＡＭＨＰは、相異なるチャネルにわたってノードを分散させることで負荷分散を実現しようとする。あるチャネルを複数のノードが共有する場合、ＡＭＨＰは、短時間スケール（数十ないし数百マイクロ秒）で、メディアアクセス制御のためのＩＥＥＥ８０２．１１ＭＡＣに依拠する。
【００３９】
ＡＭＨＰにおいて、ノードは、「アイドルまたは受信」および「送信」という２つの動作状態を有する。ノードは、送信すべきパケットを有していないとき、「アイドルまたは受信」状態にある。ノードは、別のノードに対する未処理パケットを有するとき、「送信」状態にある。
【００４０】
１）アイドルまたは受信状態。ＡＭＨＰにおいて、各ノードは「ホームチャネル」を有する。ノードは、「アイドルまたは受信」状態にあるとき、自己のホームチャネル上に滞在する。各ノードは最初に、自己のＭＡＣアドレスに基づいて自己のホームチャネルを選択する。しかし、ノードは、自己の現ホームチャネルが輻輳していることを検知したときには、別のホームチャネルをランダムに選択し、「ランデブーチャネル」上に「ＡＭＨＰチャネル転送」をブロードキャストすることで、自己の新しいホームチャネルをアナウンスすることができる。不安定性を避けるため、ノードは、別の新しい「ホームチャネル」を選択する前に、最小の時間間隔の間、自己の新しい「ホームチャネル」を使用する。
【００４１】
２）送信状態。ノードは、別のノードに対する未処理パケットを有するとき、「アイドルまたは受信」状態から「送信」状態に遷移する。送信者および受信者が同じホームチャネルを有する場合、送信者は、「ＡＭＨＰ  ｓｙｎｃ要求」（同期要求）を送信することができ、受信者は、「ＡＭＨＰ  ｓｙｎｃ応答」（同期応答）で応答することができる。このハンドシェイクの後、これらの２つのノードはデータ交換を開始することができる。送信者が受信者のホームチャネルを知らない場合、あるいは、これら２つのノードが相異なるホームチャネルを有する場合、送信者は、チャネル転送の作成および受信者の発見という２つのステップを実行することになる。
【００４２】
ステップ１：チャネル転送の作成。送信者は、別のチャネル上の受信者と連絡をとるために一時的に自己のホームチャネルを退出しなければならないので、自己の一時チャネルについて他のノードに通知する。この目的のため、送信者は、「ＡＭＨＰチャネル転送」を、まず自己のホームチャネル上に、そして一連の選択されたチャネル（「ランデブーチャネル」）上にブロードキャストする。「ランデブーチャネル」は、データ交換のために使用可能な正規のＩＥＥＥ８０２．１１チャネルにほかならない。しかし、任意の２つのノードがそれらのホームチャネル上で互いを発見しない場合には、それらのノード間の最初の接点としても作用する。これら一連のランデブーチャネルは、ネットワーク管理者によって事前に指定されてもよいし、単に、利用可能なチャネルのうちのある特定の順序でのサブセットであってもよい。
【００４３】
ステップ２：受信ノードの発見。送信者が受信者のホームチャネルを知っている場合、送信者は、そのチャネルに切り替え、「ＡＭＨＰ  ｓｙｎｃ要求」をブロードキャストすることにより受信者と連絡をとろうとする。受信者は、自己のホームチャネル上にある場合、「ＡＭＨＰ  ｓｙｎｃ応答」で応答し、これら２つのノードはデータ交換を開始することができる。受信者が別のチャネル上にある場合、受信者のホームチャネル上にあって受信者の一時チャネルに関する知識を有する他のノードが、送信ノードに対して、無償の「ＡＭＨＰチャネル転送」によって送信者に応答することができる。送信者は、ある個数の「ＡＭＨＰ  ｓｙｎｃ要求」を送信した後、「ＡＭＨＰ  ｓｙｎｃ応答」または「ＡＭＨＰチャネル転送」を受信しない場合、「ランデブーチャネル」で連続的に受信者を探索しようとする。
【００４４】
ステップ１およびステップ２について、わかりやすくするために別々に説明したが、それらを組み合わせることも可能である。この場合、ノードは「ランデブーチャネル」上に「ＡＭＨＰ  ｓｙｎｃ要求」および「ＡＭＨＰチャネル転送」を連続的にブロードキャストすることで、チャネル切り替えオーバーヘッドを低減する。
【００４５】
送信者は、受信者の現チャネルを知らないとき、ランデブーチャネル上で受信者を連続的に探索する。この理由は、受信者がそのホームチャネル上にない場合には、受信者はその現チャネルに関するヒントを（上記で説明したように）「ランデブーチャネル」上にも提供しているからである。送信者は、どの「ランデブーチャネル」上でも「ＡＭＨＰ  ｓｙｎｃ応答」または「ＡＭＨＰチャネル転送」を受信しない場合、残りのデータチャネル上で受信ノードを探索し始める。この場合はまれにしか起こらないはずであり、フェイルセーフ解決策を提供するための最後の手段としてのみ意味を有する。
【００４６】
送信者が受信者を発見すると、送信者は受信者とデータ交換を開始することができる。データ交換後、送信者は「ランデブーチャネル」に連続的に切り替わり、「ＡＭＨＰチャネル転送」をブロードキャストすることにより、これから自己のホームチャネルに戻ることを他のノードに通知する。
【００４７】
ＡＭＨＰは、ＩＥＥＥ８０２．１１ＭＡＣを拡張してパケット単位で動作するのではなく、ＩＥＥＥ８０２．１１ＭＡＣとは異なる時間スケールで動作することができる。このため、ＡＭＨＰおよびＩＥＥＥ８０２．１１ＭＡＣは相互に補完し合うことで、２つの異なる時間スケールで複数のチャネルにわたる負荷分散を実現する。ＡＭＨＰの設計選択により、ノードは、ある時間間隔において複数のノードとデータを交換することができる。他のマルチチャネルＭＡＣプロトコルでは、ノードは、ある時間間隔において他の１つのノードとしかデータを交換することができない。
【００４８】
ＡＭＨＰの動作の概略を、以下の３つのシナリオで例示する。
【００４９】
図１に示す基本的シナリオでは、ノードＡ、Ｂ、およびＣは、「アイドルまたは受信」動作状態にあるとき、すなわち、送信すべきパケットを有していない場合、それぞれのホームチャネル上に滞在する。ノードＡが例えばノードＣとデータを交換したい場合、ノードＡはＣのホームチャネルに切り替わり、Ｃとデータ交換を開始する。しかし、ノードＡがノードＣに切り替わる前に、本発明によれば、ノードＡは、自己のホームチャネル上に、自己の一時動作チャネル、すなわちノードＣのホームチャネルに関する情報を残す。すなわち、ノードＡは、ノードＣのホームチャネルに切り替わる前に、対応するチャネル転送メッセージを自己のホームチャネル上にブロードキャストする。これにより、ノードＡのホームチャネル上に存在する他のノードには、ノードＡがどこで見つかるかが通知される。
【００５０】
「アイドルまたは受信」状態から「送信」状態に遷移し、ノードＣのホームチャネルに切り替わった後、ノードＡは、同期要求である「ＡＭＨＰ  ｓｙｎｃ要求」（図示せず）を送信し、受信ノードＣは、同期応答である「ＡＭＨＰ  ｓｙｎｃ応答」（同じく図示せず）で応答する。このハンドシェイクの後、データ交換を開始することができる。データの交換が終了した後、ノードＡは自己のホームチャネルに切り替わって戻る。
【００５１】
ホームチャネル経由のチャネル転送の一例を図２に例示する。このシナリオでは、最初にノードＡ、Ｂ、Ｃ、およびＤがそれぞれのホームチャネル上に滞在し、ノードＡおよびノードＤが同じホームチャネルを共有する。ノードＡが例えばノードＣとデータを交換したい場合、この場合もまず、ノードＡは、チャネル転送メッセージをブロードキャストしてから、Ｃのホームチャネルに切り替わる。ノードＣのホームチャネル上でノードＡとＣとの間のハンドシェイクを（例えば「ＡＭＨＰ  ｓｙｎｃ要求」および「ＡＭＨＰ  ｓｙｎｃ応答」により）実行した後、これら２つのノードはデータ交換を開始することができる。
【００５２】
また、図２に例示したシナリオでは、ノードＢがノードＡとデータを交換したいので、ノードＡのホームチャネルに切り替わる。しかし、ノードＡは一時的に、自己のホームチャネル上ではなくノードＣのホームチャネル上で動作している。その結果、ノードＢは、ノードＤからチャネル転送を受信する。ノードＤは、その前にノードＡからチャネル転送メッセージを受信しており、ノードＡの一時動作チャネルについて知らされているからである。この通知に基づいて、ノードＢは、ノードＡと通信するために、ノードＣのチャネルに切り替わることができる。ノードＣのホームチャネル上でノードＡとハンドシェイクを実行した後、ノードＢとノードＡはデータ交換を開始することができる。なお、注意すべきであるが、ノードＡ、Ｂ、およびＣは、元のＩＥＥＥ８０２．１１ＭＡＣプロトコルを使用することにより共通のチャネルを共有することができる。
【００５３】
ランデブーチャネル経由のチャネル転送の一例を図３に例示する。わかりやすくするために、ただ１つのランデブーチャネルを図３に示しているが、現実の適用シナリオでは、複数の相異なるランデブーチャネルを実装してよいことはもちろんである。図３のシナリオでは、最初にノードＡ、Ｂ、Ｃ、およびＤがそれぞれのホームチャネル上に滞在している。ノードＡは、ノードＣとデータを交換したいとき、自己のホームチャネル上およびランデブーチャネル上にチャネル転送メッセージをブロードキャストする。（複数のランデブーチャネルがある場合、相異なるランデブーチャネルのそれぞれにチャネル転送メッセージをブロードキャストしてもよい）。その後、ノードＡは、ノードＣのホームチャネルに切り替わり、ノードＣとデータ交換を開始する。
【００５４】
ノードＢがノードＡとのデータ交換を希望し、ノードＡのホームチャネルに切り替わる。ノードＢは、「ＡＭＨＰ  ｓｙｎｃ要求」をブロードキャストするが、応答を受信しない。というのは、ノードＡは一時的にノードＣのホームチャネル上で動作しているので、ノードＢの「ＡＭＨＰ  ｓｙｎｃ要求」を自己のホームチャネル上で受信することができないからである。ノードＢは、「ＡＭＨＰ  ｓｙｎｃ要求」に対する応答を受信しないので、ランデブーチャネルに（複数のランデブーチャネルがある場合には相異なるランデブーチャネルに連続的に）切り替わり、ノードＤからチャネル転送を受信する。ノードＤは、ノードＡによってランデブーチャネル上でブロードキャストされたチャネル転送メッセージにより、ノードＡの現在の動作チャネルについて通知されている。ノードＤからチャネル転送を受信すると、ノードＢは、ノードＣのホームチャネルに切り替わり、ノードＡとデータ交換を開始する。なお、これに関して注意すべきであるが、ノードＡ、Ｂ、Ｃ、およびＤは、元のＩＥＥＥ８０２．１１ＭＡＣプロトコルを使用することにより共通のチャネルを共有することができる。
【００５５】
上記の説明および添付図面の記載に基づいて、当業者は本発明の多くの変形例および他の実施形態に想到し得るであろう。したがって、本発明は、開示した具体的実施形態に限定されるものではなく、変形例および他の実施形態も、添付の特許請求の範囲内に含まれるものと解すべきである。本明細書では特定の用語を用いているが、それらは総称的・説明的意味でのみ用いられており、限定を目的としたものではない。
【図１】
2011528880.tif 000003
【図２】
2011528880.tif 000004
【図３】
2011528880.tif 000005
【国際調査報告】
2011528880.tif 000006
2011528880.tif 000007