(57)【要約】【課題】  複数の無線端末が自己組織化されて互いに通信を行うネットワークにおけるエンド・エンド間のデータ転送の遅延を保障する。【解決手段】送信すべきデータに対して送信元端末と宛先端末との間で複数のルートを検索し、検索された複数のルートのひとつを選択して送信し、転送遅延が要求を満足できなかったときにはそのデータに対する送信優先度を上げ、それでも要求が満足されないときには転送ルートを切り替え、それでも要求が満足されないときにはルート検索からやり直す。【選択図】  図３
2007221568.tif 000002
【特許請求の範囲】
【請求項１】
複数の無線端末が自己組織化されて互いに通信を行うネットワーク上でエンド・エンド間の転送遅延を保障する転送遅延制御方法において、
送信すべきデータに対して送信元端末と宛先端末との間で複数のルートを検索する第一のステップと、
検索された複数のルートのひとつを選択して前記送信すべきデータを前記送信元端末から前記宛先端末へ送信する第二のステップと、
前記送信すべきデータに対して前記送信元端末から前記宛先端末への転送遅延が要求を満足できなかったときにはそのデータに対する送信優先度を上げる第三のステップと、
送信優先度を上げても前記要求が満足されないときには前記送信元端末から前記宛先端末への転送ルートを前記第一のステップで検索された複数のルートのうちの別のルートに切り替える第四のステップと
を含み、
前記第四のステップにより転送ルートを切り替えても前記要求が満足されないときには前記第一のステップからやり直す
ことを特徴とする転送遅延制御方法。
【請求項２】
前記第三のステップにおいて、前記送信すべきデータに対して転送遅延が必要以上に小さいときには、そのデータに対する送信優先度を下げる請求項１記載の転送遅延制御方法。
【請求項３】
前記ネットワーク上で転送されるデータにそれぞれそのデータに要求される実時間性に応じてトラヒック・レベルが設定され、
前記第三のステップでは、前記送信すべきデータのトラヒック・レベルに対して転送遅延が満足されているか否かを判断する
請求項１または２記載の転送遅延制御方法。
【請求項４】
それぞれのトラヒック・レベルには、そのレベルのデータが許容できる最大の遅延量と、それより小さい遅延までは必要としない最小の遅延量とが割り当てられる請求項３記載の転送遅延制御方法。
【請求項５】
それぞれのトラヒック・レベルに対して個々に１または複数の送信優先度が割り当てられる請求項３記載の転送遅延制御方法。
【請求項６】
前記第二のステップで前記送信すべきデータを送信する前に、選択したルートが実際に転送遅延要求を満足できるかどうか確認するための擬似データを送信する請求項１記載の転送遅延制御方法。
【請求項７】
ネットワーク上の宛先端末との間でルートを検索する手段と、
検索されたルートにデータを送信する手段と
を備えた無線端末において、
前記検索する手段は複数のルートを検索してルート・テーブルに蓄える手段を含み、
前記送信する手段は、送信したデータに対する転送遅延要求が満足されなかったことを宛先端末から通知されたときには、そのデータに対する送信優先度を上げるか、あるいは、それ以上上げることができない場合には前記ルート・テーブルに蓄えれられた別のルートに転送ルートを切り替える手段を含む
ことを特徴とする無線端末。
【請求項８】
前記送信する手段は、送信したデータの転送遅延が必要以上に小さいことを宛先端末から通知されたときには、そのデータに対する送信優先度を下げる手段を含む請求項７記載の無線端末。
【請求項９】
送信元端末からのデータを受信してその転送遅延を測定する手段と、
測定された転送遅延がそのデータに要求される範囲を満たしていない場合にはそれを前記送信元端末に通知する手段と
をさらに備えた請求項７または８記載の無線端末。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は無線ネットワーク内でのエンド・エンド間のデータ転送に関する。特に、実時間トラヒックのデータ伝送における遅延を保障する技術に関する。
【０００２】
本発明は特に、アドホック・ネットワークでの利用に適する。「アドホック・ネットワーク」とは、パーソナル・コンピュータ、携帯電話機、携帯情報端末（ＰＤＡ）などの無線端末が自己組織化された自立分散型の無線ネットワークという。類似する用語として「マルチホップ無線ネットワーク」もあるが、こちらは基地局などの固定施設が介在する場合を含む。本発明において「アドホック・ネットワーク」とは、いかなる固定施設も介在せずに端末同士が通信を行う純粋な分散ネットワークに限定される。
【背景技術】
【０００３】
アドホック・ネットワークを構築するための技術として、多重アクセスを可能にするためのＣＳＭＡ／ＣＡ（Carrier Sense Multiple Access with Collision Avoidance）プロトコル、マルチホップ通信のためのＤＳＲ（Dynamic Source Routing）アルゴリズム（非特許文献１参照）やＡＯＤＶ（Adhoc On-Demand Distance Vector）ルーティング・アルゴリズム（非特許文献２参照）など、多数の無線技術、プロトコルおよびアルゴリズムが研究されてきた。
【０００４】
しかし、アドホック・ネットワーク内でのエンド・エンド間のサービスの質（ＱｏＳ：Quality of Service）を確保するための技術については、これまで、ほとんど研究されていない。実際、エンド・エンド間ＱｏＳを確保することは、アドホック・ネットワーク本来の動的トポロジおよび機動性と相容れない部分があり、有線ネットワークやセルラネットワークで用いられている従来の方法、例えばネットワーク上で送信先までの帯域を予約して通信品質を確保するリソースリザベーションは、そのままアドホック・ネットワークで採用することはできない。
【非特許文献１】Internet Draft, “The dynamic source routing protocol for mobile ad hoc networks (DSR).”, http://www.ietf.org/internet-drafts/draft-ietf-manet-dsr-10.txt
【非特許文献２】RFC3561, “Ad hoc on demand distance vector (AODV) routing.”, http://www.ietf.org/rfc/rfc3561.txt
【非特許文献３】IEEE802.11e “Part 11: Wireless Medium Access Control (MAC) 6 and Physical Layer (PHY) specifications: Medium Access Control (MAC) Enhancements for Quality of Service (QoS)”
【発明の開示】
【発明が解決しようとする課題】
【０００５】
アドホック・ネットワークでエンド・エンド間ＱｏＳを確保するためには、ある特定の性能メトリックがあらかじめ決められたしきい値以下または以上に維持されるように、資源を動的に修正することが基本となる。
【０００６】
資源を動的に修正する方法として、伝送速度、伝送範囲、伝送確率などの種々の無線資源のマッピングを無線環境に適合するように修正することが考えられる。しかし、それらのパラメータはそれぞれが特定のアクセス技術や物理的技術に関連しており、それを修正できるのは特定の利用形態に限られる。例えば伝送範囲の修正は、端末がその送信パワーを種々の送信範囲で変更することができるネットワークには適するが、ＩＥＥＥ  ８０２．１１シリーズで標準化されているアドホック・ネットワークのような固定送信パワーのネットワーク、すなわち送信範囲および送信パワーがすべての端末および送信で固定されている固定送信パワーのネットワークでは、採用することができない。強固なプロトコルを設計するためには、無線環境を適応的に修正するための共通のパラメータを開発する必要がある。
【０００７】
また、アドホック・ネットワークにおいては、リンクあるいはポイント・ポイント間でＱｏＳを確保しても、エンド・エンド間でのＱｏＳを確保できるとは限らない。例えば、ＩＥＥＥ８０２．１１ｅ（非特許文献３参照）で規定されたＥＤＣＦのようなＱｏＳ  ＭＡＣ（Media Access Control）プロトコルは、リンクの質を保障することができる。しかし、リンクを組み合わせて構成されるエンド・エンド間のパスの質については、個々の端末のＱｏＳ  ＭＡＣプロトコルによって保障されるものではない。ＱｏＳ  ＭＡＣプロトコルでエンド・エンドＱｏＳを確保するには、パス内のすべての端末が互いに協力する必要がある。しかも、動的ネットワーク内ですべてのエンド・エンド間ＱｏＳの要求を満たすために、リンクの個々のＱｏＳパラメータをどのように割り当てるかが非常に重要である。ＱｏＳ  ＭＡＣプロトコルは、アプリオリに定義された遅延または速度などのＱｏＳパラメータを必要とする。例えば、エンド・エンド遅延をどのようにリンクの遅延要求に分割するかである。一方、遅延の最適分割は無線環境により種々に変化するため、分割を動的に修正する必要があり、非常に困難である。
【０００８】
エンド・エンド間のＱｏＳの要求を満足するルートまたはパスを見つけるためのルーティング・アルゴリズムも開発されているが、これらのアルゴリズムは一般に、複雑なルート維持アルゴリズムおよびネットワーク資源管理プロトコルに依存している。このため、適応修正がどれだけ可能かは、これらのアルゴリズムに制限される。
【０００９】
本発明は、このような課題を解決し、各種アルゴリズムあるいはプロトコルに依存せずにエンド・エンド間のデータ転送の遅延を保障することのできる転送遅延制御方法およびそのための無線端末を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の転送遅延制御方法は、複数の無線端末が自己組織化されて互いに通信を行うネットワーク上でエンド・エンド間の転送遅延を保障する方法において、送信すべきデータに対して送信元端末と宛先端末との間で複数のルートを検索する第一のステップと、検索された複数のルートのひとつを選択して前記送信すべきデータを前記送信元端末から前記宛先端末へ送信する第二のステップと、前記送信すべきデータに対して前記送信元端末から前記宛先端末への転送遅延が要求を満足できなかったときにはそのデータに対する送信優先度を上げる第三のステップと、送信優先度を上げても前記要求が満足されないときには前記送信元端末から前記宛先端末への転送ルートを前記第一のステップで検索された複数のルートのうちの別のルートに切り替える第四のステップとを含み、前記第四のステップにより転送ルートを切り替えても前記要求が満足されないときには前記第一のステップからやり直すことを特徴とする。
【００１１】
前記第三のステップにおいて、前記送信すべきデータに対して転送遅延が必要以上に小さいときには、そのデータに対する送信優先度を下げることが望ましい。
【００１２】
具体的には、前記ネットワーク上で転送されるデータにそれぞれそのデータに要求される実時間性に応じてトラヒック・レベルを設定し、前記第三のステップでは、前記送信すべきデータのトラヒック・レベルに対して転送遅延が満足されているか否かを判断する。それぞれのトラヒック・レベルには、そのレベルのデータが許容できる最大の遅延量と、それより小さい遅延までは必要としない最小の遅延量とを割り当てる。それぞれのトラヒック・レベルに対して、個々に１または複数の送信優先度を割り当てる。
【００１３】
前記第二のステップで前記送信すべきデータを送信する前に、選択したルートが実際に転送遅延要求を満足できるかどうか確認するための擬似データを送信することが望ましい。
【００１４】
本発明によるとさらに、上記のネットワークで用いられる無線端末が提供される。すなわち、この無線端末は、ネットワーク上の宛先端末との間でルートを検索する手段と、検索されたルートにデータを送信する手段とを備えた無線端末において、前記検索する手段は複数のルートを検索してルート・テーブルに蓄える手段を含み、前記送信する手段は、送信したデータに対する転送遅延要求が満足されなかったことを宛先端末から通知されたときには、そのデータに対する送信優先度を上げるか、あるいは、それ以上に上げることができない場合には前記ルート・テーブルに蓄えられた別のルートに転送ルートを切り替える手段を含むことを特徴とする。
【００１５】
前記送信する手段は、送信したデータの転送遅延が必要以上に小さいことを宛先端末から通知されたときには、そのデータに対する送信優先度を下げる手段を含むことが望ましい。
【００１６】
送信元端末からのデータを受信してその転送遅延を測定する手段と、測定された転送遅延がそのデータに要求される範囲を満たしていない場合にはそれを前記送信元端末に通知する手段とをさらに備えることが望ましい。
【発明の効果】
【００１７】
本発明では、送信すべきデータに送信優先度を与え、要求される転送遅延を満足できなくなったときにはその送信優先度を上げる。それでも満足できない場合には、ルートを切り替える。送信優先度は特別のＱｏＳスキームではなく、種々のプロトコルやアルゴリズムに適合させて、ＭＡＣまたは物理層内のトラヒックの優先度を設定することができる。これにより、不必要なルート検索を行う必要なく、システム容量の範囲内でエンド・エンド間の所要転送遅延を満足することが可能となる。
【００１８】
ここで注意すべきことは、本発明における「送信優先度」は、送信すべきデータに要求される転送遅延と直接関係するパラメータではなく、転送遅延が満たされないときに修正すべきパラメータであることである。したがって、転送遅延が満たされる限りデータを低優先度で転送し、その分だけ資源を他のデータ転送に利用して、ユーザ間で資源を効率的に共有することができる。
【００１９】
一方、送信すべきデータに要求される転送遅延と直接関係するパラメータとして、各データにトラヒック・レベルが設定される。各トラヒック・レベルには、１または複数の送信優先度が割り当てられる。このとき、各トラヒック・レベルには、そのトラヒック・レベルに要求される転送遅延にしたがって、他のトラヒック・レベルとは異なる最大送信優先度が割り当てられる。実時間性が要求される音声や映像などのデータには高いトラヒック・レベルを割り当てておくことで、輻輳時にも他のデータより高い送信優先度を得ることができ、転送遅延をできるだけ保障することができる。
【００２０】
また、転送遅延が必要以上に小さいときにそのデータに対する送信優先度を下げることで、ユーザ間で資源を効率的に共有することができ、ネットワーク全体のパフォーマンスを向上させることができる。
【発明を実施するための最良の形態】
【００２１】
図１は本発明を実施する無線ネットワークの構成例を示す図であり、図２は本発明による転送遅延制御方法の手順を簡単に示す図である。
【００２２】
この無線ネットワークはアドホック・ネットワークを形成し、パーソナル・コンピュータ、携帯電話機、携帯情報端末などの無線端末１１〜１６が、自己組織化されて互いに通信を行う。図１では、無線端末１１から無線端末１５へのデータが無線端末１３を経由して転送される例を示す。
【００２３】
ここで、エンド・エンド間の転送遅延を保障する方法について、図２を参照し、無線端末２１から無線端末２６にデータを転送する場合を例に説明する。送信すべきデータに対して送信元の無線端末２１と宛先の無線端末２６との間で複数のルートを検索する。ここでは、無線端末２３、２４を経由するルートと、無線端末２５を経由するルートとが見つかったものとする。送信元の無線端末２１は、検索されたルートのひとつ、この場合は無線端末２３、２４を経由するルートを選択して、データを無線端末２６に向けてパケットにより送信する。無線端末２６は受信データの平均遅延を求め、その値が要求を満足していない場合には、それを無線端末２１に通知する。無線端末２１は、無線端末２６からの通知を受取ると、そのデータに対する送信優先度を上げる。送信優先度を上げても要求が満足されないときには、無線端末２１から無線端末２６への転送ルートを別のルート、この例では無線端末２５を経由するルートに切り替える。それでも遅延要求が満足されないときには、ルートを再探索する。
【００２４】
詳しい実施例について以下に説明する。
【実施例１】
【００２５】
図３は本発明による優先度モデルを用いてエンド・エンド遅延を保障する方法のフローチャートである。ここではルーティング・アルゴリズムとして単純なものを例示するが、本発明はルーティング・アルゴリズムに限定されるものではなく、他の複雑な、または効率のよいルーティング・アルゴリズムを利用してもよい。
【００２６】
送信元端末がデータを送信したい時には、最初に、ルートを問い合わせるための要求メッセージＰＲＥＱを送信する（Ｓ１１）。このＰＲＥＱには宛先アドレスおよび送信時刻が付されており、可能なあらゆるルートで転送される。宛先端末がＰＲＥＱを受信すると直ちに、確認メッセージＲＲＥＰを返信し（Ｓ２１）、ＰＲＥＱと逆ルートで転送される。その一方で、ＲＲＥＰは、ルート遅延を推定するため、受信ＰＲＥＱに付された時間情報を使用する。送信元がＲＲＥＰを受信すると、ＲＲＥＰに付されたルート情報を得、そのルートを送信元のルート・テーブルに保存する（Ｓ１２）。ただし、送信元がこのルートを直ぐに使用してデータを送信するのではなく、予備ルートのための別のルート情報が付されたＲＲＥＱを受信するまで、ある時間待機する。同時に、送信元はＲＲＥＰに付された時刻情報をＲＲＥＰの受信時刻と比較して、ルートの遅延を計算する。待機時間が過ぎ、ルート・テーブルが少なくともひとつのルートを含むとき、送信元は、遅延の制約を考慮して、適切なルートを用いてデータを送信する。
【００２７】
本発明者らの解析およびシミュレーションによると、ＲＲＥＱ／ＲＲＥＰパケットは、種々のネットワークやアクセス・プロトコル内で、データ・パケットとは異なる遅延を受けることが観測された。詳細な差異については、現在のところわかっていない。そこで送信元端末は、データ・パケットの遅延を調べるため、そのデータに許容される最大の優先度で擬似データを送信する（Ｓ１３）。最大の優先度を用いる理由は、そのルートで遅延要求を満足できるかどうかを確認することが目的だからである。擬似データを受信した宛先端末は、確認メッーセージＡＣＫを返送する（Ｓ２２）。返送されたＡＣＫにより擬似データの受信を確認すると、送信元端末は、ルートの遅延がそのデータにとって満足できるものであるかどうかを計算する（Ｓ１４）。そして、データの遅延要求を満足するルートのうち最も適切なルートを選択し（Ｓ１５）、最も低い優先度でデータを送信する（Ｓ１６）。要求を満たすルートが存在しない場合には、新たなルートを見つける処理から繰り返す。
【００２８】
ネットワーク状態は動的に変化し、トラヒックはそれ自身をネットワーク環境に適合させる必要がある。このため、宛先端末においてトラヒックの遅延を記録し続け、トラヒックの平均遅延を計算する（Ｓ２３）。平均遅延が遅延要求より大きいか、あるいは最小しきい値より小さい場合（Ｓ２４）、宛先端末は送信元端末にＭａｒｋ  ＡＣＫを送信する（Ｓ２５）。Ｍａｒｋ  ＡＣＫを受信した後、送信元端末はデータの送信優先度を修正する（Ｓ１７）。優先度の修正がＱｏＳ要求を満足できない場合には、送信元端末はルート・テーブルから他のルートを選択し（Ｓ１９、Ｓ１１０）、データを送信する（Ｓ１６）。優先度の修正の詳細については後述する。
【００２９】
図４はトラヒック・レベルと送信優先度との関係を示す。本発明では、ネットワーク上で転送されるデータにそれぞれ、そのデータに要求される実時間性に応じてトラヒック・レベルが設定される。それぞれのトラヒック・レベルには、個々に、１または複数の送信優先度が割り当てられる。トラヒック・レベルがＭ段階、優先度のレベルがＮ段階あるとすると、従来技術ではひとつの優先度がひとつのトラヒック・レベルに対応してＮ＝Ｍであるのに対し、本発明では、Ｎ＞Ｍである。
【００３０】
それぞれのトラヒック・レベルには、そのレベルのデータが許容できる最大の遅延量（これを「最大遅延制約」という）と、それより小さい遅延までは必要としない最小しきい値の遅延量（これを「最小遅延制約」という）とが割り当てられる。図５に、トラヒック・レベルと遅延制約との関係を示す。これについては後で詳しく説明する。
【００３１】
図４では、各トラヒック・レベルの最小の送信優先度を同じ値「１」としている。これは、各トラヒック・レベルに対して同一の最小送信優先度「１」でデータを送信することを意味する。ただし、本発明は各トラヒック・レベルの最小送信優先度が同一であることに限定されるものではなく、トラヒック・レベル毎に異なる最小送信優先度を割り当てることもできる。
【００３２】
各データの送信優先度は、遅延制約を満足するかぎり、最小送信優先度と最大送信優先度との間のどの値をとることもできる。本願発明者らの解析によれば、トラヒック負荷が軽いときには送信優先度は低く維持され、トラヒック負荷が高いときには送信優先度が最大送信優先度に近くなる。したがって、すべてのトラヒック・レベルに対して最小送信優先度を同一の「１」にしておくことにより、トラヒックが軽く資源が十分なときには、低優先度のトラヒックで資源を占有することができる。
【００３３】
図５に示すように、各トラヒック・レベルには、ひとつの最大遅延制約とひとつの最小遅延制約とが設定される。最大遅延制約は、トラヒックの違いに対して従来から用いられるパラメータである。例えば音声または映像トラヒックの最大遅延制約は、それ以外のデータのトラヒックによりはるかに小さい。これに対して最小遅延制約は、トラヒックの違いに対するものではなく、資源の最適割り当てのためのものである。トラヒックの平均遅延が最小遅延制約より小さいときには、トラヒックがその要求より多くの資源を消費し、その優先度が少し高いか、または高過ぎることを意味する。そこで、そのトラヒックに対するデータの送信優先度を減少させ、同時に、許容できる遅延に維持する。間接的に解放された資源は他のトラヒックで利用でき、最適な資源の割り当てが達成される。図５では、最小遅延制約が最大遅延制約より各トラヒック・レベルで同じ値だけ小さく、しかもその差が小さいものとしている。本発明はこのような場合に限定されるものではなく、最大遅延制約と最小遅延制約との最適割り当ては適宜設定すべきである。
【００３４】
図６は送信優先度の修正の詳細を示すフローチャートである。送信元は、Ｍａｒｋ  ＡＣＫを受信すると、そのＭａｒｋ  ＡＣＫにより伝えられた情報にしたがって、データの送信優先度を修正する。まず、宛先端末により計算されＭａｒｋ  ＡＣＫパケットで伝達された平均遅延が最大遅延制約より大きい場合（Ｓ３１）、送信優先度がそのデータのトラヒック・レベルにおける最大優先度より小さければ（Ｓ３２）、送信元端末はそのデータに対する送信優先度を高める（Ｓ３３）。さもなければ、ルート・テーブルから他のルートを検索し（Ｓ３７）、予備ルートが存在すればそれを選択する（Ｓ３８）。平均遅延が最小遅延制約より小さい場合（Ｓ３４）、そのデータの送信優先度が最小優先度より大きければ（Ｓ３５）、送信元端末はそのデータの送信優先度を下げる（Ｓ３６）。送信優先度を下げることで、高優先度のトラヒックによる過剰な資源の占有を解放し、トラヒック負荷を平衡させることができる。
【００３５】
各無線端末においてデータをその送信優先度に従って送信するには、優先度毎にバッファを設けて優先度の高いバッファに蓄積されているデータから順に送信するなど、従来の技術を利用することができる。ただし、従来は各データの最大遅延制約に対応して異なる優先度のバッファを設け、データの種類とバッファとの対応を固定していたのに対し、本発明でこのような技術を利用する場合には、データの種類（トラヒック・レベル）とバッファとには直接の対応関係をもたせず、各データに対して適応的に設定される送信優先度に従って、そのデータを対応する優先度のバッファに振り分けるようにする。
【図面の簡単な説明】
【００３６】
【図１】本発明を実施する無線ネットワークの構成例を示す図。
【図２】本発明による転送遅延制御方法の手順を簡単に示す図。
【図３】エンド・エンド遅延を保障する方法のフローチャート。
【図４】トラヒック・レベルと送信優先度との関係を示す図。
【図５】トラヒック・レベルと遅延制約との関係を示す図。
【図６】送信優先度の修正の詳細を示すフローチャート。
【符号の説明】
【００３７】
１１〜１６、２１〜２６  無線端末
【図１】
2007221568.tif 000003
【図２】
2007221568.tif 000004
【図３】
2007221568.tif 000005
【図４】
2007221568.tif 000006
【図５】
2007221568.tif 000007
【図６】
2007221568.tif 000008