(57)【要約】メディア・アクセス制御（ＭＡＣ）スケジューリング・アルゴリズムに対するシステムおよび方法であって、ノード・ステータス情報を伝える制御ＲＴＳ／ＣＴＳメッセージを用いることによって、アドホック・ネットワークにおける使用のフェアネスおよびサービスの差別化を実現するための、分布型自己調整アプローチを有するシステムおよび方法。ローカル・スケジューリング・アルゴリズムは、ノードのステータスを特定する属性を含む漏れ聞こえるＲＴＳ／ＣＴＳ情報を用いて、データ・メッセージおよびＡＣＫメッセージが異なるデータ・チャンネルを通して送信されるような多チャンネル・システムに対する近辺ステータスの認識を最大にする。システムが単一チャンネルを使用する場合には、対応する情報を、ＤＡＴＡメッセージまたはＡＣＫメッセージを用いることによって伝えても良い。アルゴリズムは、近辺における与えられた負荷、伝えられた負荷、およびバックログの負荷を測定して、種々のノード、種々のリンク、および種々のストリーム間の使用のフェアネスが実現されるように、チャンネル・アクセス・タイマを調整する。アルゴリズムは、さらに、ノード・キュー・ステータスに基づいて優先度レベルを計算すること、近隣ステータスに基づいて優先度レベルを計算することの両方を行なって、コンテンション層を壊してサービスの差別化を可能にすることができる。
2006527523.tif 000002
【特許請求の範囲】
【請求項１】
アドホック・マルチホッピング・ピア・トゥ・ピア無線通信ネットワークにおけるノードに対してメディア・アクセス制御（ＭＡＣ）スケジューリングを実行するための方法であって、
送信を試行するノードを制御して、受信された送信要求（ＲＴＳ）メッセージおよび受信準備完了（ＣＴＳ）メッセージに含まれる情報に基づいて、該ノードの優先度レベル重みを評価すること、
前記評価された優先度レベル重みに基づいて、前記ノードの送信をスケジューリングすること、
を備える方法。
【請求項２】
請求項１に記載の方法において、前記制御するステップは、さらに、受信されたＲＴＳメッセージおよびＣＴＳメッセージに基づいて、近隣ノードの優先度レベル重みを評価することを含み、前記スケジューリングするステップは、前記ノードの評価された優先度レベル重みと、前記近隣ノードの評価された優先度レベル重みとに基づいて、送信をスケジュールすることを含む、方法。
【請求項３】
請求項１に記載の方法において、前記ＲＴＳメッセージおよびＣＴＳメッセージに含まれる情報は、送信元および宛先ＭＡＣアドレス、現在のパケット長、データ・チャンネル・レート、選択されたデータ・チャンネル、およびパケット優先度レベルから計算される重み付きキュー長のうちの少なくとも１つを含む、方法。
【請求項４】
請求項１に記載の方法において、システムが単一チャンネルを使用し、かつＲＴＳ／ＣＴＳが送信に対して有効になっていない場合には、前記ＲＴＳメッセージおよびＣＴＳメッセージに含まれる情報を、ＤＡＴＡメッセージおよびＡＣＫメッセージにおいてそれぞれ伝えることができる、方法。
【請求項５】
請求項２に記載の方法において、システムが単一チャンネルを使用し、かつＲＴＳ／ＣＴＳが送信に対して有効になっていない場合には、前記ＲＴＳメッセージおよびＣＴＳメッセージに含まれる情報を、ＤＡＴＡメッセージおよびＡＣＫメッセージにおいてそれぞれ伝えることができる、方法。
【請求項６】
請求項３に記載の方法において、システムが単一チャンネルを使用し、かつＲＴＳ／ＣＴＳが送信に対して有効になっていない場合には、前記ＲＴＳメッセージおよびＣＴＳメッセージに含まれる情報を、ＤＡＴＡメッセージおよびＡＣＫメッセージにおいてそれぞれ伝えることができる、方法。
【請求項７】
請求項１に記載の方法において、前記ノードが移動ノードである、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線アドホック・ネットワーク・システムにおけるメディア・アクセス制御（ＭＡＣ：Media Access Control）プロトコルに関する。具体的には、完全分布型システムにおけるフェアネスおよびサービスの差別化の問題を解決するためのローカル・スケジューリング・アルゴリズムを含むハンドシェーキング・プロトコルを有する通信システムおよび方法を、単一または多チャンネル、マルチホップ無線ネットワークにおけるデータ交換に対して用いる。
【背景技術】
【０００２】
この１０年間で、移動無線電話機ネットワークなどの無線通信ネットワークは、ますます普及している。このような無線通信ネットワークは、一般に、「セルラ・ネットワーク」と呼ばれている。何故なら、サービス・エリアを「セル」と呼ばれる複数の領域に分割するように、ネットワーク・インフラストラクチャの配置が行なわれるからである。地上のセルラ・ネットワークには、サービス・エリアの全体を通して指定箇所に地理的に分布された複数の相互接続された基地局、またはベース・ノードが含まれている。各ベース・ノードには、カバー・エリア内に位置する移動ユーザ・ノードたとえば無線電話機と、電磁信号たとえば無線周波数（ＲＦ：Radio Frequency ）通信信号を送受信することができる１つまたは複数の送受信装置が含まれる。通信信号には、たとえば、所望の変調技術により変調されてデータ・パケットとして送信される音声データが含まれる。当業者ならば理解できるように、ネットワーク・ノードは、データ・パケット通信を多重化フォーマットで、たとえば、時分割多元接続（ＴＤＭＡ：Time Division Multiple Access ）フォーマット、符号分割多元接続（ＣＤＭＡ：Code Division Multiple Access ）フォーマット、または周波数分割多元接続（ＦＤＭＡ：Frequency Division Multiple Access）フォーマットで送受信する。多重化フォーマットは、ベース・ノードにおける単一の送受信装置が、そのカバー・エリア内の複数の移動ノードと同時に通信することを可能にするものである。
【０００３】
近年、「アドホック」ネットワークとして知られる移動通信ネットワークの形式が、軍事使用を目的として開発されている。この形式のネットワークでは、各移動ノードが、他の移動ノードに対する基地局またはルータとして動作できるため、基地局の固定されたインフラストラクチャを設ける必要がなくなる。アドホック・ネットワークの詳細については、メイヤ（Mayor ）に付与された米国特許第５，９４３，３２２号の明細書で述べられている。なお、この文献の全体の内容は、本明細書において参照により取り入れられている。
【０００４】
より高性能なアドホック・ネットワークも開発中である。すなわち、従来のアドホック・ネットワークと同様に移動ノードが互いと通信できるだけでなく、さらに、移動ノードが、固定ネットワークにアクセスして、他の移動ノード（たとえば公衆交換電話網（ＰＳＴＮ：Public Switched Telephone Network ）上の移動ノード、および他のネットワークたとえばインターネット上の移動ノード）と通信できるようなアドホック・ネットワークである。これらの高性能な形式のアドホック・ネットワークの詳細は、以下の文献に記載されている。「ＰＳＴＮおよびセルラ・ネットワークに接続されたアドホック・ピア・トゥ・ピア移動無線アクセス・システム（Ad hoc Peer-to-Peer Mobile Radio Access System Interfaced to the PSTN and Cellular Networks ）」（米国特許出願第０９／８９７，７９０号明細書、２００１年６月２９日出願）、「別個の予約チャンネルを有する共有パラレル・データ・チャンネルに対する調整チャンネル・アクセスを有するアドホック、ピア・トゥ・ピア無線ネットワークに対する時分割プロトコル（Time Division Protocol for an Ad-Hoc, Peer-to-Peer Network Having Coordinating Channel Access to Shared Parallel Data Channel with Separate Reservation Channel ）」（米国特許出願第０９／８１５，１５７号明細書、２００１年３月２２日出願）、および「アドホック、ピア・トゥ・ピア、移動無線アクセス・システムに対する優先順位決めされたルーティング（Prioritized-Routing for an Ad-Hoc, Peer-to-Peer, Mobile Radio Access System ）」（米国特許出願第０９／８１５，１６４号明細書、２００１年３月２２日出願）。なお、これらの文献の全体の内容は本明細書において参照により取り入れられている。
【０００５】
しかしながら、ノード間の通信は、干渉、マルチパスおよびフェーディング効果、ならびに衝突に起因するエラーを受けることが多い。多くのこのようなエラーは、送信ノードと受信ノードとの間の制御信号ハンドシェークを用いて回避することができる。衝突回避型多重アクセス（ＭＡＣＡ：Multiple Access with Collision Avoidance）などの通信プロトコルでは、送信要求（ＲＴＳ：Request-To-Send ）制御パケットからなるハンドシェーク技術をノード間で用いている。送信要求制御パケットは、送信元ノードから宛先ノードへ送られ、宛先ノードは、それに応答して、受信準備完了（ＣＴＳ：Clear-To-Send ）制御パケットを用いて返答する。しかしながら、ＭＡＣＡＷアルゴリズムが通常取り扱うのは、このようなエラーを補正するためのＡＲＱ再送信であり、補正は、送信要求／受信準備完了（ＲＴＳ／ＣＴＳ）チャンネル・アクセス・シーケンス全体を繰り返すことによって行なわれる。加えて、ＭＡＣＡＷでは、データ送信（ＤＳ：Data-Sending）メッセージを導入して、ＲＴＳ−ＣＴＳ−ＤＳ−ＤＡＴＡ−ＡＣＫメッセージ交換および新たなバック・オフ・アルゴリズムを形成していた。ＩＥＥＥ８０２．１１ＭＡＣは、ＣＳＭＡ／ＣＡプロトコルの変形である。ＣＳＭＡ／ＣＡプロトコルでは、キャリア・センシングおよび仮想（ＲＴＳ−ＣＴＳ交換）キャリア・センシングの両方を、信頼性を改善するための確認応答メッセージを用いて実施する。
【０００６】
したがって、無線アドホック・ネットワーク・システムにおける通信を検出およびスケジュールして、前述したようなエラーを回避することができ、かつ補正に関連する複雑さを排除することができるメディア・アクセス制御プロトコルが必要である。
【０００７】
レディ（Redi）に付与された米国特許第６，５５６，５８２号の明細書（この文献の全体の内容は本明細書において参照により取り入れられている）に記載されているように、ＭＡＣＡベースの無線ネットワークにおいて多重アクセス衝突を回避するための方法について説明する。この衝突回避方式は、複数の送受信装置、すなわちデータ・チャンネルおよび予約チャンネル送受信装置を有するシステムに対して提案されている。送受信装置は同時に働くため、見逃される予約チャンネルはない。ＮＣＴＳメッセージを用いて、他のノードに、意図した宛先ノードがビジーであることを通知する。したがって、１つの送受信装置および１つまたは複数のデータ・チャンネルを有することに関する問題（たとえば予約データを見失うこと）を解決する必要がある。レディ特許に記載されている方法には、ＲＴＳメッセージにおける優先度フィールドを用いることも含まれている。しかしながら、この情報の処理は、絶対的な比較に基づいている。すなわち、近辺における送信の相対的なステータスは用いられず、フェアネスも考慮されない。
【０００８】
ケルマーニ（Kermani ）らに付与された米国特許第６，１１８，７８８号の明細書（この文献の全体の内容は本明細書において参照により取り入れられている）に記載されているように、ＭＡＣＡベースの無線ネットワークにおいてフェアネスを実現するための方法について説明する。ケルマーニ特許で考慮されるシステムには、チャンネルが１つしかなく、このチャンネルでは、送信継続時間が、ＲＴＳ−ＣＴＳメッセージに分布しておらず、送信後のバースト制御フレームの終わりを介して分布している。したがって、送信継続時間がＲＴＳ−ＣＴＳメッセージを介して通知される複数のデータ・チャンネル・システムを含むアドレスおよびチャンネル・モニタリングが必要である。ケルマーニ特許の主な目的は、隠れ端末問題を解決することであるが、１つの送受信装置および複数のデータ・チャンネルを有することに関する問題（たとえば予約データを見失うこと）もまた解決する訳ではない。ケルマーニ特許で提案されているシステムは、以下の事実に基づいている。すなわち、近隣は、近辺における可能な論理的接続の数または何らかの他の情報を、この情報を分配することで完全に知っているということである。たとえば、通知されたウィンドウ・サイズを聞いた近隣は、自身のウィンドウ・サイズを相応に調整することが推奨される。しかしながら、このようにすることは、この情報が正確でないときには、すべてのノードがそれらのバックオフ時間を短くして、衝突を増やす場合がある。したがって、送信および受信者アシスタント情報補正からのフィードバックを用いて、近辺およびリンクについての情報を完全にする方法およびシステムが必要である。ケルマーニ特許では、サービスの差別化は考慮されていない。
【０００９】
ベンベニステ（Benveniste）の米国特許出願公開第２００２０１５４６５３号明細書（この文献の全体の内容は本明細書において参照により取り入れられている）に記載されているように、ＣＳＭＡネットワークに対するトラフィックへのバックオフ適合を用いる方法について説明する。考慮されているシステムは、１つのチャンネルを有するワン・ホップ・システムである。この方法の目的は、ＩＥＥＥ８０２．１１形式のネットワークを、コンテンション遅延およびサービスの差別化に関して改善することである。この方法は主に、失敗した送信試行の数からトラフィック強度を推定することに基づいている。しかしながら、マルチホッピング・システムでは、チャンネル・アクセス遅延の重要な原因の１つは、多くのストリームが１つの中継ノード（たとえばワン・ホップ・システムにおけるアクセス・ポイントとしての中央制御能力がない無線ルータ）において集中すること、および中継ノードがビジーであることである。したがって、チャンネルおよびアドレス・モニタリングによって、衝突確率は減少する（したがって、失敗する送信試行の数は減少する）が、与えられたトラフィック強度は高い場合がある。この遅延によって、短期のアンフェアネスが生じ、ＴＣＰ形式のトラフィックが遅くなり、したがって、実際のトラフィック強度が変化する場合がある。したがって、この問題を軽減するためにノード重みが必要である。
【００１０】
さらに、多チャンネルを有するシステムに対して、予約チャンネルおよびデータ・チャンネル衝突を差別化する必要がある。他の点は、ベンベニステ公開で説明されている方法とは異なり、種々の次ホップまでのストリームが中継ノードに存在する場合があるために、次ホップのビジー・ステータスまたはリンク障害に起因したバックログのパケットが生じて、別の次ホップ用のより新しいパケットよりも後でスケジュールされる場合がある、ということである。不完全な近辺情報が生じることが、マルチホップの１つまたは多チャンネル・ネットワークにおける重要な問題である。したがって、これらの問題を軽減するために、局所的な測定値を（ユニキャスト・メッセージングを介して）比較するシステムおよび方法が必要である。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明の目的は、メディア・アクセス制御（ＭＡＣ）のシステムおよび方法であって、ローカル・スケジューリング・アルゴリズム、具体的には双方向のスケジューリング技術を含むことで、ノード・ステータス情報を伝えるＲＴＳ／ＣＴＳ制御メッセージを用いることによってアドホック・ネットワークにおけるフェアネスおよびサービスの差別化を実現するシステムおよび方法を提供することにある。
【００１２】
本発明の他の目的は、ＲＴＳ／ＣＴＳメッセージ情報を用いて単一ノードの情報を測定し、測定された情報に基づいて単一ノードに重み因子を割り当てることができるローカル・スケジューリング・アルゴリズムを提供することにある。
【００１３】
本発明の他の目的は、ＲＴＳ／ＣＴＳメッセージ情報を用いて単一ノードの近隣ノード情報を測定し、測定された情報に基づいて単一ノードの各近隣ノードに重み因子を割り当てることができるローカル・スケジューリング・アルゴリズムを提供することにある。
【００１４】
本発明の他の目的は、単一ノードの重み因子のみを用いる第１のステートレス方式、ならびに単一ノードの重み因子および近隣ノードの重み因子を用いる第２のステートフル方式を含む少なくとも２つのスケジューリング方式を実行することができるローカル・スケジューリング・アルゴリズムを提供することにある。
【００１５】
本発明の他の目的は、少なくとも２つのスケジューリング方式を実行して、ノード、種々のリンク、および種々のストリーム間でのフェアな使用が実現されるようにチャンネル・アクセスを調整することができるローカル・スケジューリング・アルゴリズムを提供することである。
【課題を解決するための手段】
【００１６】
これらの目的および他の目的は、ノード・ステータス情報を伝える制御ＲＴＳ／ＣＴＳメッセージを用いることによってアドホック・ネットワークにおける使用のフェアネスおよびサービスの差別化を実現するための、分布型自己調整アプローチを有するＭＡＣアルゴリズムのためのシステムおよび方法を提供することによって、実質的に実現される。ローカル・スケジューリング・アルゴリズムとして、ノードのステータスを特定する属性を含む漏れ聞こえるＲＴＳ／ＣＴＳ情報を用いて近辺認識を最大にするアルゴリズムが提供される。システムは、単一チャンネルまたは多チャンネル（この場合、データ・メッセージおよびＡＣＫメッセージは、異なるチャンネルを通して送信される）からなっていても良い。アルゴリズムは、近辺における与えられた負荷、伝えられた負荷、およびバックログの負荷を測定して、種々のノード、種々のリンク、および種々のストリーム間での使用のフェアネスが実現されるように、チャンネル・アクセス・タイマを調整する。アルゴリズムは、さらに、ノード・キュー・ステータスに基づいて優先度レベルを計算すること、近隣ステータスに基づいて優先度レベルを計算することの両方を行なって、コンテンション層を壊してサービスの差別化を可能にすることができる。
【発明を実施するための最良の形態】
【００１７】
本発明のこれらの目的および他の目的、優位性および新たな特徴は、以下の詳細な説明を添付図面とともに読むことにより、容易に理解されよう。
後述する本発明の実施形態においては、単一／多チャンネル、マルチホップ無線ネットワークにおけるデータ交換に対するハンドシェーキング・プロトコルを含む通信システムおよび方法が開示される。完全分布型システムたとえば図１のネットワーク１００におけるチャンネル使用のフェアネスおよびサービスの差別化の問題を解決するために、ローカル・スケジューリング・アルゴリズムが１つまたは複数のノードにおいて与えられる。
【００１８】
図１は、本発明の実施形態を用いるアドホック・パケット交換型無線通信ネットワーク１００の例を示すブロック図である。具体的には、ネットワーク１００は、複数の移動無線ユーザ端末１０２−１〜１０２−ｎ（ノード１０２または移動ノード１０２と呼ぶ）を含んでいる。ネットワーク１００は、複数のアクセス・ポイント１０６−１，１０６−２，…１０６−ｎ（ノード１０６またはアクセス・ポイント１０６と呼ぶ）を有する固定ネットワーク１０４を含むことができる（しかしながら、必ずしも必要とする訳ではない）。これらのノード１０６は、ノード１０２に、固定ネットワーク１０４へのアクセスを与えるためのものである。固定ネットワーク１０４は、たとえば、核となるローカル・アクセス・ネットワーク（ＬＡＮ：Local Area Network）、および複数のサーバおよびゲートウェイ・ルータを含むことができる。サーバおよびゲートウェイ・ルータは、ネットワーク・ノードに、他のネットワークたとえば他のアドホック・ネットワーク、公衆交換電話網（ＰＳＴＮ：Public Switched Telephone Network ）およびインターネットへのアクセスを与えるためのものである。またネットワーク１００は、複数の固定ルータ１０７−１〜１０７−ｎ（ノード１０７またはルータ１０７と呼ぶ）を含んでいても良い。これらのルータ１０７は、データ・パケットを他のノード１０２，１０６，または１０７の間でルーティングするためのものである。ここでの説明上、前述したノードを一括して、「ノード１０２，１０６，および１０７」、または単純に「ノード」もしくは「端末」と呼ぶこともあることに注意されたい。当業者ならば理解できるように、ノード１０２，１０６，および１０７は、互いに直接通信することもできるし、あるいはノード間で送信中のパケットに対するルータとして動作する１つまたは複数の他のノードを介して通信することもできる。このことは以下の文献に記載されている。米国特許第５，９４３，３２２号明細書（メイヤ）、および米国特許出願第０９／８９７，７９０号明細書、米国特許出願第０９／８１５，１５７号明細書、および米国特許出願第０９／８１５，１６４号明細書（これらはすでに参照されている）。
【００１９】
図２に示したように、各ノード１０２，１０６，および１０７には、送受信装置１０８が含まれている。送受信装置１０８はアンテナ１１０に結合され、コントローラ１１２の制御の下で、ノード１０２，１０６，または１０７との間で、パケット化された信号などの信号を送受信することができる。パケット化されたデータ信号は、たとえば、音声、データ、またはマルチメディア情報、およびパケット化された制御信号（ノード・ルーティングおよび更新情報など）を含むことができる。
【００２０】
各ノード１０２，１０６，および１０７には、さらに、メモリ１１４、たとえばランダム・アクセス・メモリ（ＲＡＭ：Random Access Memory）が含まれている。メモリ１１４は、とりわけ、ネットワークにおける自分自身および他のノードに関するルーティング情報を記憶することができる。ノード１０２，１０６，および１０７は、それぞれのルーティング情報（ルーティング通知と呼ぶ）を、互いに、放送機構を介して周期的に交換する。この交換は、種々の間隔で、たとえば新たなノードがネットワークに移入するとき、あるいはネットワーク内の既存のノードが移動するときに行なわれる。
【００２１】
図２にさらに示すように、ある特定のノード、特に移動ノード１０２は、ホスト１１６を含むことができる。ホスト１１６は、任意の数の装置、たとえばノートブック・コンピュータ端末、移動電話機ユニット、移動データ・ユニット、または任意の他の好適な装置により構成されていても良い。また各ノード１０２，１０６，および１０７には、インターネット・プロトコル（ＩＰ：Internet Protocol ）およびアドレス解決プロトコル（ＡＲＰ：Address Resolution Protocol ）を実行するための適切なハードウェアおよびソフトウェアも含まれている。当業者ならば、これらのプロトコルの目的を容易に理解することができよう。また伝送制御プロトコル（ＴＣＰ：Transmission Control Protocol ）およびユーザ・データグラム・プロトコル（ＵＤＰ：User Datagram Protocol）を実行するための適切なハードウェアおよびソフトウェアが含まれていても良い。さらに、各ノードには、自動再送要求（ＡＲＱ：Automatic Repeat Request）機能およびメディア・アクセス制御（ＭＡＣ：Media Access Control）を実行するための適切なハードウェアおよびソフトウェア・プロトコルが含まれている。このプロトコルには、フェアネスおよびサービスの差別化の問題を解決するために与えられるローカル・スケジューリング・アルゴリズムが含まれている。これについては、以下で詳細に述べる。
【００２２】
図１のネットワーク１００では、各ノード１０２，１０６，および１０７は、時間の測定量に基づく自己調整による局所的なスケジューラとしての機能を果たす。この機能は、「スケジューリング・アルゴリズム」を用いることによって実現可能である。「スケジューリング・アルゴリズム」は、与えられた負荷および伝えられた負荷の測定量に依存して種々の方法で、性能と複雑さとの間のトレードオフのバランスを取ることによって実施可能である。すべてのノードにおいて、ローカル・スケジューリング・テーブルが保持される。このテーブルは、アドレスおよびチャンネル・モニタリングの結果を用いることによって更新される。さらに、各受信ノードは、それ自身のテーブルを用いること、かつチューニング因子を用いて返答することによって、スケジューリングを制御することができる。アルゴリズム例において、チューニング因子に対する例を与える。したがって、後述する実施形態では、隠れノードおよび露出するノードに関する多数の問題、およびモビリティに関する問題が、発信者によって開始されおよび受信者によって調整される双方向のスケジューリング技術を用いることによって解決される。
【００２３】
後述する本発明の実施形態においては、多チャンネルだけでなく単一チャンネルを用いても良い。多チャンネル・システムが例として与えられる。多チャンネル・マルチホップ・ネットワーク、たとえば図１のネットワーク１００では、「送信要求」（ＲＴＳ：Request-To-Send ）メッセージおよび「受信準備完了」（ＣＴＳ：Clear-To-Send ）メッセージが、予約チャンネルを通して送信される一方で、データおよび「確認応答」（ＡＣＫ：Acknowledgement ）メッセージが、選択されたデータ・チャンネルを介して送信される。しかしながら、単一チャンネル・システムでは、これらのメッセージは、同一のチャンネル上で送信される。またＲＴＳ／ＣＴＳメッセージは、近隣ステータス情報を含むこともできる。近隣ステータス情報は、送信元および宛先ＭＡＣアドレス、現在のパケット長、データ・チャンネル・レート、選択されたデータ・チャンネル、パケット優先度レベル（すなわち、優先順位、再送信試行、パケット寿命などの組み合わせ）から計算される重み付きキュー長を含むことができる。
【００２４】
本実施形態においては、前述したＲＴＳ／ＣＴＳメッセージから導き出される情報に基づいて、少なくとも２つのスケジューリング方式を採用することができる。ノード自身の自己優先度レベル（ノードの「重み」としても知られている）のみを用いることによって、「ステートレス」スケジューリングを実施することができる。さらに、近隣ノードの重み値にも基づいて調整することによって、「ステートフル」スケジューリングを実施することができる。ステートフル・スケジューリングを行なう際、各ノードは、送信されたＲＴＳ／ＣＴＳ制御メッセージからの近辺（すなわち近隣ノード）情報を保持することができる。
【００２５】
後述する本発明の実施形態においては、ノード自身の現在のステータスと、ノードの近隣ノードの現在のステータス情報との少なくとも一方を用いることによって、チャンネル・アクセス時間およびバックオフ遅延を制御するために、ローカル・スケジューリング・アルゴリズムが与えられる。さらに、そのスケジューリング・アルゴリズムでは、優先度インデックスに基づいてこれらのタイマに適応することによって、サービスの差別化が実現される。
【００２６】
ローカル・スケジューリング・アルゴリズムは、双方向に分布された自己調整アプローチに基づいて、予約データ情報を用いることによりアドホック・ネットワークにおけるフェアネスおよびサービスの差別化を実現する。任意の数の移動ノードを含む無線アドホック・ネットワークにおいて結果として生じる分布されたスケジューリングは、第１および第２の本発明の実施形態による以下のステップを通して実現することができる。
【００２７】
第１のステップでは、各ノードにおいて、トラフィック負荷および優先度の重み付き因子を測定する。第２の同様のステップでは、各ノードにおいて、トラフィック負荷および優先度の重み付き因子を、各近隣ノードに対して測定する。これらの値を、第３のステップにおいて単独であるいは組み合わせて用いて、送信ノードにおいて、送信ノードにおけるトラフィックに基づいてアクセス時間間隔を計算し、送信ノードの近隣ノードのトラフィック状態を計算する。これには、発信者によって開始され、受信者によって調整される双方向のスケジューリングの第１の部分が含まれる。これについては、ステップ４および５において後述する。
【００２８】
受信ノードにおける第４のステップでは、各遠隔ノードに対する同等なバンド幅およびアクセス時間間隔が、意図しないＲＴＳおよびＣＴＳから得られる測定されたトラフィックに基づいて計算される。これについては、例で説明する。続いて第５のステップでは、受信ノードにおいて、計算値によるノード・アクセスに基づいて調整されたチャンネル・アクセス時間（すなわち、チャンネル・アクセス試行減少または増加させるチューニング因子）を用いて、ＣＴＳを送信するのかあるいはＮＣＴＳを送信するのかを決定する。これには、発信者によって開始され、受信ノードによって調整される双方向のスケジューリングの第２の部分が含まれる。
【００２９】
前述した双方向のスケジューリング・アルゴリズムの５つのステップは、所望するスケジューリング方式に依存して、ステートレス・スケジューリング・アルゴリズムまたはステートフル・スケジューリング・アルゴリズムのいずれかにおいて、第１の実施形態または第２の実施形態のいずれかとして適用可能である。前述したように、２つのスケジューリング方式を採用することができる。ステートレス・スケジューリングは、ノード自身の重みを用いることによって実施可能である。ステートフル・スケジューリングは、近隣ノードの重み値にも基づいてさらに調整することによって実施可能である。
【００３０】
スケジューリング・アルゴリズムの第１の実施形態においては、収集情報のためにアドレスおよびチャンネル・モニタリングのみを使用し、アドレスおよび／またはチャンネルがフリーになってから送信継続時間をスケジューリングする。スケジューリング・アルゴリズムの第２の実施形態においては、各ノードは、ある特定の時間の間に各接続を通って送信されてくるトラフィックについての情報を収集し、その局所的なテーブルにおける重み値を、将来のスケジューリングのために更新する。予約が予約チャンネルを通して制御メッセージを送信することによって行なわれるため、予約チャンネルに対して調整されている近隣ノードはすべて、その局所的なテーブルを更新することができる。
【００３１】
第１および第２の実施形態における収集情報の測定量は、ノードまたは近隣ノードの与えられた負荷および伝えられた負荷に関する種々の測定基準を含むことができる。これについては、以下で詳細に述べる。仮定として、本発明の実施形態の少なくとも１つにおいては、種々の優先度が、種々のバンド幅要求、遅延要求、およびパケット損失レートに対応することができ、かつ種々の優先度を、各トラフィック・クラスまたはフローに対して規定しても良いものと、することができる。両方の実施形態において、種々の優先度に基づいて差別化することができる。主な違いは、第２の実施形態においては、制御フレームを介して分布されたさらなる近辺情報を用いて、チャンネル・アクセス時間を計算することである。
【００３２】
測定量は、ＲＴＳメッセージおよびＣＴＳメッセージから導き出すことができ、以下のものについての情報（しかしながら、これらに限定される訳ではない）を含むことができる。パケット長、データ・チャンネル・レート、送信元ＭＡＣアドレス、宛先ＭＡＣアドレス、使用チャンネル（すなわち、ＣＴＳ、ＲＴＳ、放送）、パケット優先度レベル、および重み付きキュー長。宛先ＭＡＣアドレスは、次ホップ・ノード・アドレスを示すことができる。パケット優先度レベルは、優先順位、バックオフ・カウンタ、寿命などから計算される組み合わせ値とすることができる。またパケット優先度レベルはオプションであるとしても良い。また受信ノードがパケット優先度レベルを用いて、現在の要求を横取りすることができる。重み付きキュー長は、後の時間に送信されるべきキューイングされた負荷を通知するために、優先度レベルおよびトラフィック／ストリーム・インデックスによって重み付けされた値とすることができる。分類は、トラフィック・クラスまたはフローの観点から行われても良い。
【００３３】
スケジューリング・アルゴリズムの第１の実施形態においては、ＲＴＳメッセージおよびＣＴＳメッセージ交換を漏れ聞いた各ノードは、その局所的なトラフィック・テーブルの更新を、パケット長およびデータ・チャンネル・レートに基づいてチャンネル・ホールド・オフ時間を計算し、送信元および宛先アドレス・ビジー時間に基づいてアドレス・ホールド・オフ時間を計算することによって行なう。
【００３４】
スケジューリング・アルゴリズムの第２の実施形態においては、ＲＴＳメッセージおよびＣＴＳメッセージ交換を漏れ聞いた各ノードは、その局所的なトラフィック・テーブルの更新を、パケット長およびデータ・チャンネル・レートに基づいてチャンネル・ホールド・オフ時間を計算し、送信元および宛先アドレス・ビジー時間に基づいてアドレス・ホールド・オフ時間を計算し、かつ重み値を計算することによって行なう。
【００３５】
この情報に基づいて、第１および第２の両方の実施形態において、各ノードは、使用する次のチャンネル・アクセス時間をスケジュールする。意図しないＲＴＳメッセージまたはＣＴＳメッセージが聞こえる場合には、ノードは、対応するアドレスおよびチャンネルに対するリリース・タイムを計算する。このリリース・タイムは、パケット継続時間およびランダムな時間間隔に依存する。これら自身はノード重みに依存する。ランダムな間隔は、たとえば、一様に分布した時間間隔から、規格化されたノード重みを引いたものとすることができる。規格化されたノード重みは、正比例の時間間隔を有するように規格化可能である。パケット重みは、優先順位、送信数、寿命などに依存しても良い。ノード重みの最大値は、各クラスまたはフローに対して用いられる個々のパケット重み値、バッファ・サイズ、およびレート抑制アルゴリズムに依存する。
【００３６】
送信試行を終了中の各ノードは、これらのチャンネルおよび宛先リリース・タイムを前述の計算値に設定することによって、次の試行のスケジューリングを行なうことができる。宛先および少なくとも１つのチャンネルが利用可能であるならば、パケットは送信される。タイマは、一様に分布され、そのレンジは、ノード重み、重み付きの以前のパケット送信継続時間、および以前の送信ステータス（失敗または成功）に依存して、異なる。
【００３７】
第１のスケジューリング方式であるステートレス・スケジューリングでは、ノード重みは、スケジューリング・アルゴリズムの第１および第２の両実施形態に対するモニタリング・ケースに対して説明したように計算される。第２のスケジューリング方式であるステートフル・スケジューリングでは、ノードが、スケジューリング・アルゴリズムの第１および第２の両実施形態に対して、それ自身のチャンネル・アクセス・ケースのスケジューリングを試行するときに、ノードは、局所的なテーブルにおけるそれ自身のランクをチェックして、チャンネル・アクセス・タイマを計算する。そのチャンネル・アクセス時間が終了し、かつチャンネルを捕らえるノードが他にないときにのみ、ノードはＲＴＳメッセージを送信してチャンネルを主張することができる。このチャンネル・アクセス時間の間に他の送信試行が存在する場合には、ノードは、チャンネル・アクセス・タイマをリセットして、新たな情報に基づいて新たなチャンネル・アクセスをスケジュールする。
【００３８】
スケジューリング・アルゴリズムの第１および第２の両実施形態において、ＲＴＳ−ＣＴＳハンドシェークが不完全なために以前の送信試行が失敗している場合には、チャンネル・アクセス時間を増加させて衝突の可能性を減少させる。増分は、指数関数的であっても良い。否定応答（negative ACK）またはＡＣＫタイムアウトにより以前の送信試行が失敗している場合には、ノード重みを増加させてチャンネル障害を補償することができる。
【００３９】
前述した両方のスケジューリング・アルゴリズムの１つの機能は、ノードの重みが大きいときにはチャンネル・アクセス・タイマを減少させ、残りの状況ではチャンネル・アクセス・タイマを増加させることである。理想的には、システムは、同一の優先度のトラフィックを有するノードに対しては、異なる負荷が与えられていても、フェアでなければならない。これは、最大および最小のタイマ値の計算、近隣ノードの総計されたトラフィック・ステータス、およびレート抑制アルゴリズムにより実現可能である。
【００４０】
スケジューリング・アルゴリズムの第１および第２の両実施形態において、第２のスケジューリング方式であるステートフル・スケジューリングを実行するときには、アルゴリズムは、種々のノードの伝えられた負荷をトラッキングするための機能を含むこともできる。
【００４１】
具体的には、第１の状況として、ノードがＲＴＳメッセージを受信するときには、ＲＴＳメッセージがそのノードに対して意図されたものか否かに拘わらず、アルゴリズムは、特定された優先度レベルにおいて、アドレス・ビジー時間を計算し、与えられた負荷をパケット長に基づいて計算し、かつデータ・レートを計算する。宛先が近隣ノードでない場合には、これは、送信元（宛先ではなく）がノードの通信範囲内であることを示す。両方の場合において、ＲＴＳメッセージにおける情報たとえばパケット長、送信元、宛先、および優先度は、与えられたトラフィック負荷を測定するのに有用である。
【００４２】
第２の状況として、ノードが、そのノードに対するものではないＣＴＳメッセージを受信するときには、アルゴリズムは、特定された優先度レベルにおいて、アドレスおよびチャンネル・ビジー時間を計算し、伝えられた負荷をパケット長に基づいて計算し、かつデータ・レートを計算する。
【００４３】
第３の状況として、ノードがＲＴＳメッセージを送信するときには、アルゴリズムは、そのノードの与えられた負荷を、特定された優先度レベルにおいて計算する。
最後に、第４の状況として、ノードがＣＴＳメッセージを受信するときには、アルゴリズムは、そのノードの伝えられた負荷を、特定された優先度レベルにおいて計算する。
【００４４】
受信ノードが、受信ノードの伝えられた負荷が許容値を超えることを検出した場合には、受信ノードは、送信を要求するＲＴＳを受信すると直ちに、ＣＴＳメッセージまたはＮＣＴＳメッセージを送信することを決定して、チューニング因子を伝えることによって送信ノードを遅くすることができる。この結果、隠れ端末に関する問題の多く、たとえば送信元に関連したアンフェアネスなチャンネルおよび宛先アクセス、ならびにモビリティに関係した問題の多く、たとえば送信元が新たな近辺に移動したときに近辺についての知識がないことに起因する送信元に関連したアンフェアなアクセスが排除される。発信者は、受信ノード調整を用いることで、その新たなチャンネル・アクセス時間を調整することができる。
【００４５】
さらに、スケジューリング・アルゴリズムの第１および第２の両実施形態においては、同一の近辺におけるノードは、優先度レベルおよび重み付きキュー長をチェックすることによって、サービスの差別化およびフェアネスを考慮するように、チャンネル・アクセスをスケジュールすることができる。優先順位および重み付きキュー長を用いて、チャンネル・アクセス遅延を調整することができる。これは、優先順位が高くかつキュー長の重み付けが大きいノードに、より高い優先度を与えることによってなされる。一方で、優先度レベルにおけるパケット寿命因子を用いて、優先順位トラフィックが低くかつトラフィック負荷が軽いノードが窮乏することを回避するように、チャンネル・アクセス遅延を調整することができる。
【００４６】
前述した本発明の実施形態では、ノード・ステータス情報を伝える制御ＲＴＳ／ＣＴＳメッセージを用いることによって、アドホック・ネットワークにおけるフェアネスおよびサービスの差別化を実現する分布型自己調整アプローチを開示している。前述したローカル・スケジューリング・アルゴリズムでは、ノード・ステータスを特定する属性を含む漏れ聞こえるＲＴＳ／ＣＴＳ情報を用いて、種々のデータ・チャンネルを通してデータおよびＡＣＫメッセージが送信されている多チャンネル・システムに対する近辺ステータスの認識を最大にする。スケジューリング・アルゴリズムの第１および第２の両実施形態においては、与えられた負荷、伝えられた負荷、およびバックログの負荷近辺を測定して、種々のノード、種々のリンク、および種々のストリーム間でのフェアネスが実現されるように、チャンネル・アクセス・タイマを調整する。また各アルゴリズムは、ノード・キュー・ステータスに基づいて優先度レベルを計算すること、かつ近隣ステータスに基づいて優先度レベルを計算することの両方を行なって、コンテンション層を壊してサービスの差別化を可能にし、受信ノードを用いて、近辺についての受信ノードのより良好な視野に基づいて、分布されたスケジューリング決定を調整することで、トラフィック負荷が低いノードが窮乏することを回避することができる。
【００４７】
以下は、例を伴う本発明の実施形態の説明である。以下の例では、ノード（送信元または中継ノード）がトラフィック・クラス（ｃ）の組を有する第１および第２のアルゴリズムを例示する。これらの例では、フェアネス・インターバルの計算は各送信試行の後に行なわれ、一方で、チャンネルおよびアドレス・モニタリングは、意図しないＲＴＳまたはＣＴＳ（すなわち、このノードに対して意図されていないＲＴＳまたはＣＴＳ）を受信したときに行なわれる。例は、ユニキャスト・メッセージの送信にも及ぶ。なお、バックオフ値、優先度レベル、および測定値の計算は変更し得るものであり、この例は説明のために与えられたに過ぎないことに注意されたい。
【００４８】
第１のアルゴリズム
パケット送信
１）パケット記憶装置におけるパケットの優先度値の合計として、総計された「重み」を計算する。パケットの優先度は、優先順位、試行回数、およびパケットの寿命の、重み付き合計として計算され得る。
【００４９】
【数１】
2006527523.tif 000003
【００５０】
【数２】
2006527523.tif 000004
ここで、Ｗｊは、ノードｊに対する総計された重みであり、ｐｉは、ｉ番目のパケットの優先度レベルであり、ｗｐｃ，ｗｎｃ，およびｗａｃはそれぞれ、優先順位（ｐｒｉ）、試行回数（ｎａｉ）、およびクラスｃに対して割り当てられたキューにおけるパケットの寿命（ａｉ）に対する重み因子である。なお、重みは、与えられた負荷に対応することに注意されたい。ノードの重みと優先度情報との間の関係は、与えられた例では線形であるが、他の形式の関係を用いても良い。たとえば指数関数的または対数関数的な関係である。同様に、これらの例を考慮して、本発明たとえばフェアネス・インターバル計算の種々の変更および変形を行なっても良い。
【００５１】
２）ノードが、宛先までの新たな経路を用いてパケットを送信する準備ができている場合には、次ホップをアイドルした後に、利用可能なデータ・チャンネルの組、送信継続時間、送信元および次ホップ・アドレスを含むＲＴＳを送信する。なお、これはマルチホップ・システムであるため、新たな経路が、送信前に利用可能でなければならないことに注意されたい。経路においてわずかでも変化が起こると、送信されるべきパケットが変化する場合がある。
【００５２】
３）ＣＴＳがタイムアウトであるか、あるいはＮＣＴＳを受信した場合、フェアネス・インターバルＴｆを更新する。
【００５３】
【数３】
2006527523.tif 000005
ここで、ｗｆは、正数であり（指数関数的なバックオフを用いる場合には、ｗｆは、ＣＴＳ受信障害が起きる度に２つ増える）、ＲｆおよびＭｆは、正数であり、Ｕ［  ］は一様な分布を示す。Ｗｎｊは、規格化された重みであるので、Ｍｆ−Ｗｎｊ≧ｎである。ここで、ｎは正数である。たとえばｎ＝０の場合、Ｗｎｊ＝（ＷｊＭｆ）／Ｗｍａｘである。ここで、Ｗｍａｘは最大の重み値である。
【００５４】
４）ＣＴＳを受信した場合、ｗｆを減少させるか、あるいはｗｆ＝１を設定する。ＣＴＳには、選択されたデータ・チャンネル、送信継続時間、送信元および次ホップ・アドレスが含まれる。受信者がこのノードに対する新たなｗｆ値を送信したか否かをチェックする。なお、チューニング因子には、バックオフの式で用いられる他のパラメータが含まれていても良いことに注意されたい。
【００５５】
５）ＡＣＫを受信した場合、フェアネス・インターバルを更新する。
【００５６】
【数４】
2006527523.tif 000006
ここで、ｗｔは、パケット送信継続時間ｐｋ＿ｔｉｍｅに対する重み因子である。なお、中継ノードをシェアリングする際にフェアネスを得ようと望む場合には、次ホップを用いるためのフェアネス・インターバルを、チャンネル・フェアネス・インターバルと同様に計算しても良いことに注意されたい。
【００５７】
アドレスおよびチャンネル・モニタリング
１）意図しないＲＴＳを受信した場合は直ちに、ＣＴＳを待って、時間間隔Ｔａの間ビジーである送信元および次ホップ・アドレスの両方をマークする。
【００５８】
【数５】
2006527523.tif 000007
ここで、ｐｋ＿ｔｉｍｅは、ハンドシェーク技術による対応するオーバー・ヘッドを含む送信の継続時間である。ＲｆおよびＭｆは、フェアネス計算およびモニタリングに対して異なっていても良い。
【００５９】
２）意図しないＣＴＳを受信した場合は直ちに、送信元および次ホップ・アドレスの両方ならびに時間間隔Ｔａの間ビジーであるチャンネルをマークする。
【００６０】
【数６】
2006527523.tif 000008
ここで、ＲｆおよびＭｆは、アドレスおよびチャンネル・モニタリングに対して異なっていても良い。
【００６１】
第２のアルゴリズム
パケット送信
１）パケット記憶装置におけるパケットの優先度値の合計として、総計された「重み」を計算する。パケットの優先度は、優先順位、試行回数、およびパケットの寿命の重み付き合計として計算しても良い。なお、すべてのノードはその重み値を、ＲＴＳメッセージおよびＣＴＳメッセージを介して分布させることに注意されたい。
【００６２】
【数７】
2006527523.tif 000009
【００６３】
【数８】
2006527523.tif 000010
【００６４】
【数９】
2006527523.tif 000011
ここで、Ｗｊは、ノードｊに対する総計された重みであり、ｐｉは、ｉ番目のパケットの優先度レベルであり、ｗｐｃ，ｗｎｃ，およびｗａｃはそれぞれ、優先順位（ｐｒｉ）、試行回数（ｎａｉ）、およびキューｃにおけるパケットの寿命（ａｉ）、に対する重み因子であり、Ｗｔｊは、近隣ノードの重みに基づいて規格化されたノード重みである。
【００６５】
２）ノードが、新たな経路を用いてパケットを送信する準備ができている場合には、次ホップをアイドルした後に、利用可能なデータ・チャンネルの組、送信継続時間、送信元および次ホップ・アドレス、ノード重み、およびチャンネル・アクセス／スループット情報を含むＲＴＳを送信する。
【００６６】
３）ＣＴＳがタイムアウトであるか、あるいはＮＣＴＳを受信した場合、フェアネス・インターバルＴｆを更新する。
【００６７】
【数１０】
2006527523.tif 000012
ここで、ｗｆは、正数であり（指数関数的なバックオフを用いる場合には、ｗｆは、ＣＴＳ受信障害が起きる度に２つ増える）、ＲｆおよびＭｆは正数であり、Ｕ［  ］は一様な分布を示す。Ｗｔｎｊは規格化された重みであるので、Ｍｆ−Ｗｔｎｊ≧ｎである。ここでｎは、正数である。なお、パラメータに対する範囲は、第１のアルゴリズムのものとは異なるべきであることに注意されたい。説明を簡単にするために、同一の符号を用いている。
【００６８】
４）ＣＴＳを受信した場合、ｗｆを減少させるか、あるいはｗｆ＝１を設定する。受信者がこのノードに対する新たなｗｆ値を送信したか否かをチェックする。なお、チューニング因子には、バックオフの式で用いられる他のパラメータが含まれていても良いことに注意されたい。
【００６９】
５）ＡＣＫを受信した場合、フェアネス・インターバルを更新する。
【００７０】
【数１１】
2006527523.tif 000013
ここでｗｔは、パケット送信継続時間ｐｋ＿ｔｉｍｅに対する重み因子である。
【００７１】
６）ＡＣＫを受信した後、ノード・チャンネル占有時間を更新する。他のパラメータたとえばスループットを用いることもできる。
【００７２】
【数１２】
2006527523.tif 000014
ここでαは忘却因子であり、ｌは、ＣＴｊが更新された最後の時間である。なお、αは、モビリティに依存しても良く、たとえば、近隣テーブルの変化レートに基づいて選択しても良いことに注意されたい。なお、中継ノードをシェアリングする際にフェアネスを得ようと望む場合には、次ホップを用いるためのフェアネス・インターバルを、チャンネル・フェアネス・インターバルと同様に計算しても良いことに注意されたい。
【００７３】
アドレスおよびチャンネル・モニタリング
１）意図しないＲＴＳを受信した場合は直ちに、ＣＴＳを待って、時間間隔Ｔａの間ビジーである送信元および次ホップ・アドレスの両方をマークする。
【００７４】
【数１３】
2006527523.tif 000015
ここで、ｐｋ＿ｔｉｍｅは、ハンドシェーク技術による対応するオーバー・ヘッドを含む送信の継続時間である。ＲｆおよびＭｆは、フェアネス計算およびモニタリングに対して、異なっていても良い。このノードに対するＷｋおよびＣＴｋ値を更新する。ＣＴｋおよびＷｋ値を、ＣＴｊおよびＷｊ値と比較して、ｗｆ値を更新する。なお、重みは与えられる負荷に対応するが、チャンネル占有情報は伝えられた負荷に対応することに注意されたい。
【００７５】
２）意図しないＣＴＳを受信した場合は直ちに、送信元および次ホップ・アドレスの両方ならびに時間間隔Ｔａの間ビジーであるチャンネルをマークする。このノードに対するＷｋおよびＣＴｋ値を、ＲＴＳに対して更新されていなかった場合、更新する。
【００７６】
【数１４】
2006527523.tif 000016
ここで、ＲｆおよびＭｆは、アドレスおよびチャンネル・モニタリングに対して異なっていても良い。ＣＴｋおよびＷｋ値を、ＣＴｊおよびＷｊ値と比較して、ｗｆ値を更新する。
【００７７】
本発明のいくつかの典型的な実施形態のみについて詳細に説明してきたが、当業者であれば容易に分かるように、本発明の新たな示唆および優位性から実質的に逸脱することなく、典型的な実施形態において多くの変更が可能である。したがって、このような変更はすべて、本発明の範囲に含まれることが意図される。
【図面の簡単な説明】
【００７８】
【図１】本発明の実施形態による複数のノードを含むアドホック・パケット交換型無線通信ネットワーク例を示すブロック図。
【図２】図１に示すネットワークにおいて用いられる移動ノードの例を示すブロック図。
【図１】
2006527523.tif 000017
【図２】
2006527523.tif 000018
【国際調査報告】
2006527523.tif 000019
2006527523.tif 000020