(57)【要約】  ３つ以上の競合局の間の共用チャネルのための競合解消プロトコルにおける窓を制御する方法。局は、初期下限値Ｌに初期時に等しい下限値ｌと初期上限値Ｕに初期時に等しい上限値ｈとを有する間隔内で数ｘを発生し、数ｘが下限値ｌと上限窓境界値ｗとを有する窓の中に入る場合にチャネルにアクセスする試行を行うことにより、複数のステップにおいてチャネルについて競合し、窓外の数を発生した局は、チャネルの競合から排除され、窓中の数を発生した局は、チャネルの競合を継続し、当該方法は、競合に勝ち得たと判定される１つの局が選ばれるまで継続し、上限窓境界値ｗを、チャネルへのアクセスの試行をなすことになる局の予想数が１に略等しくなる範囲としての窓に設定するステップを有する。好適実施例では、上限窓境界値ｗは、ｗ＝Ｗ（ｌ，ｈ）≡ｌ＋（ｈ−ｌ）／ｎ（但し、ｈ≡Ｕ）、或いはｗ＝Ｗ（ｌ，ｈ）≡（ｌ＋ｈ）／２なる式により設定される。ｎは、競合する局の数又は推定数を表す。
2007533192.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも３つの競合局の間の共用チャネルのための競合解消プロトコルにおける窓を制御する方法であって、局は、初期下限値Ｌに初期時に等しい下限値ｌと初期上限値Ｕに初期時に等しい上限値ｈとを有する間隔内で数ｘを発生し、前記数ｘが前記下限値と上限窓境界値ｗとを有する窓の中に入る場合に当該チャネルにアクセスする試行を行うことにより、複数のステップにおいてチャネルについて競合し、前記窓の外の数を発生した局は、当該チャネルの競合から排除され、前記窓の中の数を発生した局は、当該チャネルの競合を継続し、当該方法は、当該競合に勝ち得たと判定される１つの局が選ばれるまで継続し、当該方法は、
・前記上限窓境界値ｗを、前記チャネルへのアクセスの試行をなすことになる局の予想される数が１に略等しくなる範囲としての窓に設定するステップを有する、
方法。
【請求項２】
請求項１に記載の方法であって、前記上限窓境界値ｗは、前記発生される数ｘが前記上限窓境界値ｗ以下となる確率Ｐ１から、前記発生される数ｘが前記下限値ｌ以下となる確率Ｐ２を引いたものが競合局の概数で割ったものと略等しくなるように設定される、方法。
【請求項３】
請求項１に記載の方法であって、前記上限窓境界値ｗは、
2007533192.tif 000012
なる式により計算され、当該発生される数ｘは、Ｆ（Ｌ）＝０及びＦ（Ｕ）＝１で［Ｌ，Ｕ］について確率分布Ｆを呈し、ＦはＦ−１（Ｆ（ｘ））＝ｘで関数Ｆ−１が存在するような可逆なものであり、ｎは、競合する局の数又は競合する局の推定数を示す、方法。
【請求項４】
請求項１に記載の方法であって、前記上限窓境界値ｗは、
2007533192.tif 000013
なる式により設定され、ｎは、競合する局の数又は競合する局の推定数を示す、方法。
【請求項５】
請求項１ないし４のうちいずれか１つに記載の方法であって、衝突が生じているかどうか又は前記チャネルがアイドル状態かどうかを検出するステップと、衝突が生じている場合にｌ´＝ｌ，ｈ´＝ｗに設定するステップと、前記チャネルがアイドル状態の場合にｌ´＝ｗ，ｈ´＝ｈに設定するステップと、ｗ´＝Ｗ（ｌ´，ｈ´）を計算するステップと、ｌ＝ｌ´，ｗ＝ｗ´，ｈ＝ｈ´と設定することにより前記間隔及び窓境界値を更新するステップとを有する方法。
【請求項６】
少なくとも３つの競合する局の間で共用されるチャネルのための競合解消プロトコルにおける窓を制御する方法であって、局は、初期下限値Ｌに初期時に等しい下限値ｌと初期上限値Ｕに初期時に等しい上限値ｈとを有する間隔内で数ｘを発生し、前記数ｘが下限窓境界値ｗと前記上限値ｈとを有する窓の中に入る場合に当該チャネルにアクセスする試行を行うことにより、複数のステップにおいてチャネルについて競合し、前記窓の外の数を発生した局は、当該チャネルの競合から排除され、前記窓の中の数を発生した局は、当該チャネルの競合を継続し、当該方法は、当該競合に勝ち得たと判定される１つの局が選ばれるまで継続し、当該方法は、
・前記下限窓境界値ｗを、前記チャネルへのアクセスの試行をなすことになる局の予想される数が１に略等しくなる範囲としての窓に設定するステップを有する、
方法。
【請求項７】
請求項６に記載の方法であって、前記下限窓境界値ｗは、前記発生される数ｘが前記下限窓境界値ｗ以上となる確率Ｐ１から、前記発生される数ｘが前記上限値ｈ以上となる確率Ｐ２を引いたものが競合局の概数で割ったものと略等しくなるように設定される、方法。
【請求項８】
請求項６に記載の方法であって、前記下限窓境界値ｗは、
2007533192.tif 000014
なる式により計算され、当該発生される数ｘは、Ｆ（Ｌ）＝０及びＦ（Ｕ）＝１で［Ｌ，Ｕ］について確率分布Ｆを呈し、ＦはＦ−１（Ｆ（ｘ））＝ｘで関数Ｆ−１が存在するような可逆なものであり、ｎは、競合する局の数又は競合する局の推定数を示す、方法。
【請求項９】
請求項６に記載の方法であって、前記下限窓境界値ｗは、
2007533192.tif 000015
なる式により設定され、ｎは、競合する局の数又は競合する局の推定数を示す、方法。
【請求項１０】
請求項６ないし９のうちいずれか１つに記載の方法であって、衝突が生じているかどうか又は前記チャネルがアイドル状態かどうかを検出するステップと、前記チャネルがアイドル状態の場合にｌ´＝ｌ，ｈ´＝ｗに設定するステップと、衝突が生じている場合にｌ´＝ｗ，ｈ´＝ｈに設定しｗ´＝Ｗ（ｌ´，ｈ´）を計算するステップと、ｌ＝ｌ´，ｗ＝ｗ´，ｈ＝ｈ´と設定することにより前記間隔及び窓境界値を更新するステップと、を有する方法。
【請求項１１】
請求項１ないし１０のうちいずれか１つに記載の方法であって、局は、前記窓の境界を表す値及び発生される数を維持するように構成され、前記局は、前記発生された数が前記窓の中に入るかどうかを評価し、当該チャネル状態についての情報を得るとともに、この情報が前記チャネルがアイドル状態にあること又は衝突が発生していることを示す場合、及び前記発生された数が前記窓の中に入る場合に、前記窓境界値の少なくとも一方が請求項１ないし１０のうちいずれか１つに記載の方法により変更され前記局が当該チャネルにおいて通信を試行する、方法。
【請求項１２】
コンピュータにおいて実行される場合に請求項１ないし１１のうちいずれか１つに記載の方法を行う符号化手段を有するコンピュータプログラム製品。
【請求項１３】
請求項１ないし１１のうちいずれか１つに記載の方法により動作するように構成される競合解消プロセッサを有する装置。
【請求項１４】
請求項１３に記載の装置であって、無線媒体におけるチャネルを介して通信を行うように構成された送信及び受信手段を有する装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、共用される通信チャネルの競合解消を扱うプロトコルに関する。
【背景技術】
【０００２】
かかるプロトコルは、複数局との共用チャネルのための競合解消を扱うものである。このチャネルは、幾つかの局が当該チャネルを介して通信する排他的な権利を獲得する最終目標をもって当該チャネルについて競合することができる程度に共用される。競合に勝てない局は、当該競合において排除されるが、後の競合において再び当該チャネルについて競うことができる。
【０００３】
局は、所定の数量的間隔例えば０から１までの間隔内で乱数又は擬似乱数を発生することにより当該チャネルについて競い、各局の乱数は、当該乱数が当該所定の数量的間隔内に位置づけられる下限及び上限を持つ窓（ウインドウ）の範囲内にあるかどうかにつき評価される。１以上のステップにおいて、この窓の下限及び／又は上限は、当該窓内の数を持つ１つの局が選ばれるまで変えられる。この局は、競合解消、及びこれによる当該チャネルによる通信の排他的権利を獲得する。したがって、当該窓の上限及び下限の中の数を有する局は、その発生された数が当該窓の中にある限り当該チャネルについて競い続けるのに対し、当該窓の中にない数を有する局は、当該競合において排除される。
【０００４】
このようなプロトコルの種々の用途が存在し、競合解消の処理は、上の段落の範囲内で様々な方法により、種々のタイプのイベントに応答した種々の時点で行うことができる。しかしながら、競合解消は、チャネルを用いる権利を複数の局の中の１つの局に与える必要がある度に、一般的なルールとして適用される。チャネルの使用権利は、所定のデータパケット数、所定のバイト数を伝送することに制限することができ、或いは、指定された時間間隔に限定可能であり、或いは、局が所定のモードで動作する場合に限ることができる。
【０００５】
大抵の用途においては、適切であると考えられる比較的低いデータオーバヘッドで局にチャネルアロケーションを付与することがプロトコルの機能である。したがって、プロトコルは、当該プロトコルの競合解消が頻繁に行われているときに特に好都合である。これは、種々のタイプのネットワーク、例えば、ネットワークの動作の間に接続及び接続解除されることの可能なネットワーク化された局の間でチャネルが共用される無線ネットワークにおける場合とすることができ
る。
【０００６】
加えて、当該プロトコルは、時分割多重アクセス（ＴＤＭＡ）及び周波数分割多重アクセス（ＦＤＭＡ）のような固定化されたアロケーション方法よりも柔軟性があり頑強なものである。
【０００７】
しかしながら、競合解消プロトコルの効率は、変えようとしたときに当該窓の新しい下限及び／又は上限を計算するために適用されるアルゴリズムに非常に大きく依拠するものである。このアルゴリズムはまた、窓制御ルールとも言われている。
【０００８】
米国特許第４，６３０，２６４号は、局間の共用チャネルについてのこのような競合解消プロトコルを開示している。ここで、各局は、共通の窓を維持し、チャネルの使用のために競争する局は数を発生する。発生された数が当該窓に入ると、局は、次のタイムスロットにおいて競争し、そうでなければ、現在の競合が解消され、当該競争に勝った局からパケットが送信されるまで待機しなければならない。衝突検出ルールが適用されて、１つ以上の局が競争しているかどうかが検出される。２つ以上の局が競争していると、或いは競争している局がない場合は、当該窓を拡張し、縮小し又は変更するように各局において窓制御ルールが適用される。この処理は、厳密に１つの局が競合するまで繰り返される。データのパケットはその後に送ることができる。
【０００９】
上記開示の中には、窓制御のための２つのコンピュータ的に異なる方策が記述されている。第１の方策は、窓を変更すなわち拡張、縮小又は移動しようとするときの当該窓の新しい限界値の精密な計算に基づいている。この精密な計算は、乱数の確率密度分布に基づくものであり、多大な計算時間量を使うかなり複雑な計算を伴うものである。一方、こうした計算は、プロトコルが競合解消を行っているときで当該窓を変える直前に急いで行うことができる。これにより、精密な計算は、複雑な計算で、すなわち、より強力なプロセッサを使って又は競合解消の持続期間をより長くかけて得られる。かくして、精密な計算は、将来の競合スロットの数を最小化することに関して最適なものであるが、非常に複雑な計算を招くものであり、リアルタイムでの評価が不可能となる。他方、精密な計算の結果は、予め計算し、ルックアップテーブルに記憶することが可能であり、これにより、競合解消中に当該結果を供給する手間を減らすことができる。しかしながら、これは、当該ルックアップテーブルを含むように構成される記憶手段を使って得られるものである。
【００１０】
ルックアップテーブルの方策の研究により、最大３２個の局に対して、各エントリが当該ルックアップテーブルにおいて単一有効桁ですなわちエントリ当たり４バイトで記憶されるときに、約２ＭＢのメモリを使うことになることが明らかとされている。最大６４個の局に対しては、記憶の条件は、１７ＭＢのメモリという量に達することになる。
【００１１】
一方、米国特許第４，６３０，２６４号によれば、期待される将来の競合スロットの数を少し増大させて簡単化されたルールに至る簡単化された窓制御ルールを適用することも提案されている。この簡単されたルールは、ｗ＝（ａ＋ｂ）／２なる式に基づくものである。ここでａは窓の下限であり、ｂは窓の上限、ｗは新しい上限である。この簡単化されたアルゴリズムは、精密な計算とルックアップテーブルの方策との間の妥協である。シミュレーションにより、ほぼ負荷に独立した振る舞いを呈しネットワーク負荷に殆ど無関係に競合を解消するために平均２．４サイクル必要とすることが判明されている。但し、より詳細なシミュレーションにより、競合を解消するための断定された平均サイクルは、チャネルにつき５を上回るほどの数の局が競合しているときに２．４サイクルを遥かに超えることが明らかとなっている。この超過はさらに、局が多く含まれるに伴ってより顕著になる。約１０局については約５０％その平均値が増大し、約１００局については約３００％その平均値が増大する。これは、本質的に競合解消を減速させるものであり、これによりネットワークの性能を大きく低下させることになる。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
上記問題及びその他の問題は、本発明により、以下の段落において要約される方法によって競合解消を行った場合に解決する。
【課題を解決するための手段】
【００１３】
本方法は、少なくとも３つの競合局の間の共用チャネルのための競合解消プロトコルにおける窓を制御することを含む方法であって、局は、初期下限値Ｌに初期時に等しい下限値ｌと初期上限値Ｕに初期時に等しい上限値ｈとを有する間隔内で数ｘを発生し、前記数ｘが前記下限値と上限窓境界値ｗとを有する窓の中に入る場合に当該チャネルにアクセスする試行を行うことにより、複数のステップにおいてチャネルについて競合し、前記窓の外の数を発生した局は、当該チャネルの競合から排除され、前記窓の中の数を発生した局は、当該チャネルの競合を継続し、当該方法は、当該競合に勝ち得たと判定される１つの局が選ばれるまで継続し、当該方法は、・前記上限窓境界値ｗを、前記チャネルへのアクセスの試行をなすことになる局の予想される数が１に略等しくなる範囲としての窓に設定するステップを有する、方法である。
【００１４】
この窓は、可能な限り少ない数の繰り返しで競合を解消することについて良好な性能を呈している。本発明は、良好に行う窓を計算する方法が計算上平易なものでありルックアップテーブルを必要としないものを提案する。チャネルについて競合する局の数が得られない場合、上限窓境界値ｗは、チャネルへのアクセスの試行をなす局の予想数が概して半分となる窓を規定するようにセット可能である。
【００１５】
本発明の実施例において、前記上限窓境界値ｗは、前記発生される数ｘが前記上限窓境界値ｗ以下となる確率Ｐ１から、前記発生される数ｘが前記下限値ｌ以下となる確率Ｐ２を引いたものが競合局の概数で割ったものと略等しくなるように設定される。
【００１６】
本発明による好適実施例において、前記上限窓境界値ｗは、
2007533192.tif 000003
なる式により計算され、当該発生される数ｘは、Ｆ（Ｌ）＝０及びＦ（Ｕ）＝１で［Ｌ，Ｕ］について確率分布Ｆを呈し、ＦはＦ−１（Ｆ（ｘ））＝ｘで関数Ｆ−１が存在するような可逆なものであり、ｎは、競合する局の数又は競合する局の推定数を示す。これにより、発生された数の最低値を持つ局が競合解消を勝ち取ることになる。上記式は、計算上の複雑さと可及的少ないステップによる競合解消をなす点での性能との間の良好なトレードオフを示す。特に、ｈが上限値Ｕに概ね等しく、Ｆ（ｈ）を計算する必要がない場合に良好である。
【００１７】
数ｘが一様又は略一様分布から発生する、できる限り少数の競合解消ステップにより競合を解消するため、上限窓境界値は、次の式によりセットされる。
2007533192.tif 000004
【００１８】
効果的なのは、競合解消方法が、衝突が生じているかどうか又は前記チャネルがアイドル状態かどうかを検出するステップと、衝突が生じている場合にｌ´＝ｌ，ｈ´＝ｗに設定するステップと、或いは前記チャネルがアイドル状態の場合にｌ´＝ｗ，ｈ´＝ｈに設定するステップと、ｗ´＝Ｗ（ｌ´，ｈ´）を計算するステップと、ｌ＝ｌ´，ｗ＝ｗ´，ｈ＝ｈ´と設定することにより前記間隔及び窓境界値を更新するステップとを有するものである。これにより、当該窓は、最低の数ｘを持つ局が選択されるときに効率的に設定される。
【００１９】
本発明によるこの方策は、ＲＲと示され、上記２つの式の最後のものを適用するだけのＷａｈと示される従来技術（米国特許第４，６３０，２６４号）と比較するためにシミュレートされている。下の表１は、ｎ局のうちの１つが選ばれる場合の競合解消に達するのに必要なステップの予想数として当該シミュレーション結果を示している。
【表１】
2007533192.tif 000005
【００２０】
したがって、本発明は、従来技術に対して大きく改善された性能を提供する。
【００２１】
発生された数の最高のものを持つ局を選択することが望まれる場合、窓の下限ｗ及び上限ｈを有する窓が用いられ、前記下限窓境界値ｗは、
2007533192.tif 000006
なる式により計算され、当該発生される数ｘは、Ｆ（Ｌ）＝０及びＦ（Ｕ）＝１で［Ｌ，Ｕ］について確率分布Ｆを呈し、ＦはＦ−１（Ｆ（ｘ））＝ｘで関数Ｆ−１が存在するような可逆なものであり、ｎは、競合する局の数又は競合する局の推定数を示すようにしている。
【００２２】
数ｘが一様分布又は略一様分布から発生される場合の可及的に少ない数の競合解消ステップで当該競合を解消するため、前記下限窓境界値ｗは、
2007533192.tif 000007
なる式により設定される。
【００２３】
効果的なものとして、競合解消方法は、衝突が生じているかどうか又は前記チャネルがアイドル状態かどうかを検出するステップと、前記チャネルがアイドル状態の場合にｌ´＝ｌ，ｈ´＝ｗに設定するステップと、或いは衝突が生じている場合にｌ´＝ｗ，ｈ´＝ｈに設定しｗ´＝Ｗ（ｌ´，ｈ´）を計算するステップと、ｌ＝ｌ´，ｗ＝ｗ´，ｈ＝ｈ´と設定することにより前記間隔及び窓境界値を更新するステップと、を有する。これにより、当該窓は、最高の数ｘを持つ局が選択されるときに効果的にセットされる。
【００２４】
好ましくは、局は、前記窓の境界を表す値及び発生される数を維持するように構成され、前記局は、前記発生された数が前記窓の中に入るかどうかを評価し、当該チャネル状態についての情報（アイドル、成功、衝突）を得るとともに、この情報が前記チャネルがアイドル状態にあること又は衝突が発生していることを示す場合、及び前記発生された数が前記窓の中に入る場合に、前記窓境界値の少なくとも一方が上述したようにして変更され前記局が当該チャネルにおいて通信を試行する。これにより、局は、チャネルについて競合することを継続し、競合の間に当該チャネルの非常に限定された使用をもって当該チャネルについて競合することができ、より高いペイロードのスループットが導かれる。なお、どのようにして次のタイムスロットの窓を設定するかについて決定するために、競合解消の所定のタイムスロットにつき当該チャネルの状態が得られる。また、「成功」は、１つの局が選ばれこれによりその競合に勝ったことを意味する。
【００２５】
さらに、本発明は、上記方法がコンピュータ上で実行されるときに当該方法を行うための符号化手段を有するコンピュータプログラム製品に関する。
【００２６】
本発明はまた、上述した方法により動作するように構成された競合解消プロセッサを有する装置に関する。
【００２７】
好ましくは、当該装置は、無線の媒体におけるチャネルを介して通信するように構成された送信及び受信手段を有するのがよい。
【発明を実施するための最良の形態】
【００２８】
図１は、競合解消を扱うように構成されたプロトコルの原理を示している。この原理は、それぞれ０及び１に選択される下限Ｌから上限Ｕの間隔において値が全般に及んでいる数量的なスケールによって描かれている。この原理は、大文字ＡからＤで示される４つのステップで示されている。最初のステップＡでは、チャネルについて競合する５つの局がｘ１，ｘ２，ｘ３，ｘ４及びｘ５と示されるそれぞれの実数値の番号を発生する。これにより、ｘ１は第１の局を示す第１の数であり、ｘ２は第２の局を示す第２の数、そしてｘ３以降も同様ということになる。かかるアルゴリズムは、最も低い数を持つ局を選択する趣旨により説明されるが、最も大なる数を持つ局を選択するように変更可能である。
【００２９】
第１の境界値ｌ及び第２の境界値ｗにより、窓が規定される。このプロトコルによれば、この窓は、当該チャネルにおいて通信を行うことを試行し当該チャネルについて競合することを継続することが許容される当該チャネルにつき競合する局のうちのいずれかの局を規定する。継続することが許容される局は、窓の境界内における番号ｘ１，ｘ２，…，ｘ５を持つ局だけである。これら局は、チャネルにおける通信の試行が許容される。２つ以上の局がそのチャネル上の通信をしようとすると、非常に高い可能性で衝突が起きることとなる。このような衝突は、検出可能であり、この検出は、２つ以上の局がチャネルにつき競合しているかどうかの指標を供給する。２つ以上の局がチャネルについて競合していると、当該競合は未だ解消されておらず、当該窓は、当該チャネルの衝突又はアイドル状態が検出されずこれにより或る局が競合に勝ちもって当該チャネル上の通信の権利を獲得するまで、繰り返し収縮又は移動させられることにより変更される。衝突解消の間、当該チャネルについて競合しつづけることが許された局だけが当該窓の境界内の数を持つものとなるので、他の局は、予選のように、連続した競合から排除されることになる。これらの局は、後の競合解消において、例えば、勝った局がチャネル上でデータパケットを送信したとき、チャネルについて競合することができる。
【００３０】
この原理の説明を再開するため、ステップＡにおいては５つの番号が発生されている。窓の下限は変数ｌにより決定され、この変数は値０にセットされる。変数ｈは、窓の現時点でとりうる最大の値を示している。この初期ステップでは、ｗ＝ｈにセットされ、衝突が検出可能であるという結果により、５つの全ての局がチャネルにおいて通信をするように試行することになる。この場合、中間の変数ｌ´は、ｌに等しくセットされ、ｈ´は、ｗに等しくセットされ、ｗ´はｗ´＝Ｗ（ｌ´，ｈ´）と計算される。その後、変数ｌ，ｈ及びｗは、中間の変数の値で更新される（ｌ＝ｌ´；ｗ＝ｗ´；ｈ＝ｈ´）。
【００３１】
この段階Ｂでは、窓［ｌ，ｗ］は、値ｘ１及びｘ２を取り込み、これにより、２つの局がチャネルにおける通信の試行が許容される一方、他の３つの局は競合から排除される。したがって、衝突が検出可能なので、当該競合が未だ解消されていないことを結論として導き出すことができる。また、この場合、中間の変数ｌ´は、ｌに等しくセットされ、ｈ´はｗと等しくセットされ、ｗ´はｗ´＝Ｗ（ｌ´，ｈ´）と計算される。その後、変数ｌ，ｈ及びｗは、中間変数の値で更新される（ｌ＝ｌ´；ｗ＝ｗ´；ｈ＝ｈ´）。
【００３２】
この段階Ｃでは、窓［ｌ，ｗ］は何ら番号を取り込まず、チャネルを取り込む試行を許される局はないので、当該チャネルはアイドル状態のままである。
【００３３】
そこで、チャネルがアイドルのままであることが検出可能なので、中間変数ｌ´はｗに等しくセットされ、ｈ´はｈに等しくセットされ、ｗ´はｗ´＝Ｗ（ｌ´，ｈ´）と計算される。そして、変数ｌ，ｈ及びｗは、中間変数の値で更新される（ｌ＝ｌ´；ｗ＝ｗ´；ｈ＝ｈ´）。これは、段階Ｂに存在する衝突が［ｗ；ｈ］に存在するようになることは分かるので、窓を［ｌ；ｗ］から［ｗ；ｈ］へ交換し付加的に当該窓を縮小することに対応する。したがって、結果としての窓は、段階Ｄに示されるものとなる。
【００３４】
後の段階Ｄでは、窓［ｌ，ｗ］は正確に１つの番号を取り込み、これにより唯１つの局がチャネル上での通信をなすことが許容される。この局は、競合解消に勝ったものとして判定される。
【００３５】
したがって換言すれば、このプロトコルは、多数の局を伴う共用チャネルのための競合解消を扱う。例えば０と１とで番号をランダムに選択する各競合局に基づいて、プロトコルは、多数のステップで、各ステップにつき窓を計算して最終的に唯１つの局が当該窓で孤立させるようにしている。この局が競合に勝つのである。
【００３６】
図２は、窓を制御するための方法のフローチャートを示している。第１のステップ２００では、チャネルについて競合する各局がそれぞれの局を表す数ｘを発生する。
【００３７】
簡単に説明するため、番号が発生される範囲としての間隔の上限Ｕ及び下限Ｌは、値０及び１であるとする。
【００３８】
このフローチャートの以下の説明では、最低の数を持つ局を選択することと、数ｘが発生される範囲としての間隔［０；１］における均等な確率分布とに関して最初に説明する。第２には、最大の数を選択する実施例を説明する。さらに、発生した数ｘの不均等な確率分布に基づく実施例を説明する。
【００３９】
ステップ２０１では、窓の第１の境界ｌが０にセットされ、変数ｈ及びｗが１にセットされる。また、中間変数ｌ´及びｈ´は、それぞれｌ及びｗの値にセットされる。
【００４０】
さらにステップ２０２では、ｗ´が
2007533192.tif 000008
として計算される。ここで、ｎは、次のタイムスロットにおけるチャネルについて競合する局の予想の数である。この局の数は、既知の方法により推定可能である。
【００４１】
後続のステップ２０３においては、変数ｌ，ｈ及びｗが更新され、ｌ＝ｌ´；ｗ＝ｗ´及びｈ＝ｈ´となる。結果としての窓［ｌ，ｗ］は、第１及び第２の境界値ｌ，ｗでセットされる。
【００４２】
ステップ２０３の後は、窓［ｌ，ｗ］内の発生の数を持つ各局が、当該チャネルにおける送信の試行が許容される。ステップ２０４では、当該チャネルにおいて送信の試行をなす２つ以上の局の結果として衝突が生じているかどうかが判定される。肯定のイベント（Ｙ）においてこの方法がステップ２０５を介してステップ２０６へ導かれ、ここで、変数ｌ´及びｈ´がｌ及びｗにそれぞれ等しくセットされ、後続のステップ２０７において、ｗ´がｗ´＝Ｗ（ｌ´，ｈ´）として計算される。ここで、ｗ´は、次の式に応じてセットされる。
2007533192.tif 000009
【００４３】
次のステップ２０８において、各変数が更新され、ｌ＝ｌ´；ｈ＝ｈ´；ｗ＝ｗ´となる。結果としての窓［ｌ，ｗ］は、第１及び第２の境界値ｌ，ｗでセットされる。
【００４４】
ステップ２０８の後、本方法は、ステップ２０４を再開し、このステップの間、ステップ２０８においてセットされた窓内の数を持つ局が当該チャネルにおける送信の試行が許容される。また、当該チャネルで衝突が生じたかどうかが判定される。衝突が何ら検出されない場合（Ｎ）、本方法は、ステップ２０５を介してステップ２０９に差し向けられる。ステップ２０９においては、チャネルがアイドル状態か（Ｙ）又はそうでないか（Ｎ）が判定される。
【００４５】
チャネルがアイドル状態である場合、変数ｌ´及びｈ´は、ステップ２１１においてｗ及びｈのそれぞれに等しくセットされる。次のステップ２１２では、ｗ´がｗ´＝Ｗ（ｌ´，ｈ´）として計算される。ここでもｗ´は、次の式によりセットされる。
2007533192.tif 000010
【００４６】
ステップ２１３において、当該変数は、ｌ＝ｌ´；ｈ＝ｈ´；ｗ＝ｗ´として更新される。結果としての窓［ｌ，ｗ］は、第１及び第２の境界値ｌ，ｗでセットされる。これにより、本方法が当該窓がステップ２１３でセットされた後に再開するステップ２０４において送信することについて局を許容する。
【００４７】
チャネルがステップ２０９においてアイドルとなっていないと判断された場合、前のステップ２０４において衝突がなかったので単一の局により使用されていると目される。この単一のチャネルは、チャネルに対する競合に勝った局として選ばれ又は競合解消されたものとして判定される。かくして、この競合解消方法は、勝ち得た局をもってステップ２１４に達することを狙ったものである。
【００４８】
数ｘが一様な確率分布の下で発生されない状況では、窓の第２の境界値ｗ，ｗ´を計算するためのより包括的な方策が、本発明の範囲から逸脱することなく適用可能である。この状況において、次の式が適用される。
2007533192.tif 000011
【００４９】
ここで、発生した数ｘは、間隔［Ｌ，Ｕ］についての関数Ｆにより表される分布を呈するものであり、すなわち、より正式には、Ｆ（Ｌ）＝０及びＦ（Ｕ）＝１でｘ∈［Ｌ，Ｕ］に対してＰ（Ｘ≦ｘ）＝Ｆ（ｘ）である。ここでＦは可逆なもの、すなわちＦ−１＝（Ｆ（ｘ））＝ｘとなる関数Ｆ−１が存在する。
【００５０】
数が一様に分布する場合、関数Ｆは、識別関数である。したがって、上記一般式は、一様分布の式に換算されることが分かる。
【００５１】
最低の数ｘを選択することについて説明したが、本方法は、最大の数を選択するように変更することができる。この変更は、Ｌ＝０の場合に次の式により上述した変数を置換することにより行うことができる。
ｘ：Ｕ−ｘ
ｈ：Ｕ−ｌ
ｌ：Ｕ−ｈ
ｗ：Ｕ−ｗ
或いは、もっと一般的に、
ｘ：Ｌ＋Ｕ−ｘ
ｈ：Ｌ＋Ｕ−ｌ
ｌ：Ｌ＋Ｕ−ｈ
ｗ：Ｌ＋Ｕ−ｗ
【００５２】
また、中間変数にはステップ２０６及び２１１において次のようにして値が割り当てられる。チャネルがアイドルの場合にｌ´＝ｌ，ｈ´＝ｗにセットしｗ´＝Ｗ（ｌ´，ｈ´）を計算する。或いは、衝突が生じている場合、ｌ´＝ｗ，ｈ´＝ｈにセットしｗ´＝Ｗ（ｌ´，ｈ´）を計算する。当該間隔及び窓境界値は、上述と同様に、すなわちｌ＝ｌ´，ｗ＝ｗ´，ｈ＝ｈ´をセットすることにより更新される。
【００５３】
図３は、局を示している。局３０１は、チャネルＣｈ（図示せず）を介して通信するように構成される送信／受信（Ｔｘ／Ｒｘ）機３０５を有し、当該チャネルは、２つ以上の局の間の通信をなす他の局と共用可能である。この実施例では、送信／受信機３０５は、データソース３０６から当該チャネルにおいてペイロードデータを送信し、データソース３０６に当該チャネルにおいてペイロードデータを受信するか、かかる送信及び受信の一方をなすように構成される。
【００５４】
この局は、図２のフローチャートに関してより詳細に説明されるように動作するように構成された競合解消プロセッサ３０２を有する。この局は、窓を表す変数ｌ，ｗ及びｈ及び変数ｘｎに含まれる発生される数を格納するメモリ３０４を有する。チャネルがアイドル状態にあるかどうか及びチャネルに衝突があるかどうかについて判定をなすことを規定するため、局３０１は、その旨を示す信号を供給するユニット３０３を有する。
【００５５】
この局は、クロック信号発生器３０７を付加的に有する。この発生器は、所定の時点において競合解消タイムスロットの実行を規定するようにプロセッサ３０２にタイミング信号を供給するように構成される。クロック発生器３０７は、チャネルを介して他の局と同期化されるようにしてもよい。
【００５６】
上述した発明によれば、第２の窓境界値ｗが、チャネルへのアクセスの試行をなすことになる局の予想数が概して１に等しくなる範囲としての窓にセットされる。この窓は、出来る限り少ない繰り返しで競合を解消することに関して良好な性能を呈している。チャネルにつき競合する局の数が得られない場合は、第２の窓境界値ｗは、チャネルへのアクセスの試行をなすことになる局の予想数が概して半分になる範囲としての窓にセットされることができる。
【００５７】
競合に勝つものとして最低の数を持つ局を選択することを望む場合で、局の数がｎのとき、チャネルについて競合を開始することが分かり、局のいずれもｈ＝Ｕの場合に未だ排除されていないことが分かる。その場合、窓は、チャネルについて競合開始した局のうち１／ｎの（すなわち１つの）局を予想して取り込む形に変換される。その他の場合、幾つかの競合のものが既に排除された形としてもよく、したがって、当該窓は、本方法の前の反復において競合する局のうち１／２の局を予想して取り込む形に変換される。
【図面の簡単な説明】
【００５８】
【図１Ａ】競合解消を扱うように構成されたプロトコルの原理を示す図。
【図１Ｂ】競合解消を扱うように構成されたプロトコルの原理を示す図。
【図１Ｃ】競合解消を扱うように構成されたプロトコルの原理を示す図。
【図１Ｄ】競合解消を扱うように構成されたプロトコルの原理を示す図。
【図２】窓を制御するための方法を示すフローチャート。
【図３】局を示す図。
【図１Ａ】
2007533192.tif 000016
【図１Ｂ】
2007533192.tif 000017
【図１Ｃ】
2007533192.tif 000018
【図１Ｄ】
2007533192.tif 000019
【図２】
2007533192.tif 000020
【図３】
2007533192.tif 000021
【国際調査報告】
2007533192.tif 000022
2007533192.tif 000023