JP3781436B2 - ２進フィードバックを用いたランダムアクセス通信法 - Google Patents

Description

本発明は、２進フィードバックを用いたランダムアクセス通信法に関する。特に、本発明は、複数の端局によりアクセスされる時間スロット伝送チャンネルをもつ通信ネットワークスにおいて、バイナリフィードバックをもつランダムアクセス通信のための方法に関する；ここでランダムアクセスとは、ユーザーが伝送すべき情報を持つときはいつでも通信することをしようとすることを意味している；時間スロット通信チャンネルを持った通信ネットワークとは、規則的な予め規定された時間間隔、いわゆる時間スロットでのみ通信が可能な通信チャンネルのことである；また、２進フィードバック手段とは、通信ネットワークのユーザーが、それ以前の時間スロットが成功裡に送出されたデータパケットを含んでいるかどうかの情報が与えられていることを意味している。
通信、たとえば衛星通信ネットワーク、ＬＡＮ（ランダムアクセスネットワーク）、あるいは移動無線ネットワークなどの単一チャンネルへのランダムアクセス通信においては、衝突形、パケットスイッチ形、時間スロット伝送チャンネルなど、前述の単一チャンネルの資源を効率的に分け合う複数のユーザーの組織化と協調が必要である。
この一般的なモデルに対するアクセスアルゴリズムは、Springer社から１９８１に出版された、CISM Course and Lectures，265号、CISMコースとレクチャー２６５号、論文「Collision Resolution Algorithms and Random-Access Communications、衝突解消アルゴリズムとランダムアクセス通信」（文書D１）中で提案され解析されている。この文書Ｄ１中で、フィードバックを用いて衝突形チャンネルにランダムアクセスするための衝突解消アルゴリズムが、各送信器によるパケットの送出と再送出についてのプロトコールとして定義されている；それは衝突にかかわるすべてのパケットが最終的には再送出に成功し、すべての送信器（衝突パケットを含む送信器だけでなく）が、最終的にしかも同時にこれらのパケットの送出の成功を感知することである。すなわち、すべての送信器が同時に、衝突したパケットの再送出にすべて成功したことを感知するようになる時点で、衝突が完全に解消されたと考えるのである。あるインターバル中で発生したすべてのメッセージの送出に成功したとき、そのインターバルが解消されたと考える。基本のインターバルは、先行インターバルが解消されたとき、はじめて開始される。文書Ｄ１で与えられたこれらの定義が、本文書の残余の部分全体を通して用いられる。
上に述べた一般的なモデルに対するアクセスアルゴリズムは、１９８４年４月に出版された、IEEE Transactions on Communications，COM-32巻、７６９−７８４ページ所載の論文「Random Multiple-Access Communication and Group Testing、ランダム複数アクセスとグループテスティング」（文書Ｄ２）、ならびに、１９９０年５月に出版された、IEEE Transactions on Information Theory，IT-３６巻、６１４−６２２ページ所載の論文「Random-Access Communication with Multiple Reception（多重受信を含むランダムアクセス通信）」（文書Ｄ３）中で提案され解析されている。これらの論文、Ｄ２とＤ３、のいずれにおいても、２進の成功/不成功フィードバックが検討されている。成功/不成功フィードバックは、伝送チャンネルのユーザーに、与えられたスロットが送出に成功したパケットを含んでいたかどうかを表示する情報を提供する。このことは、たとえば、受信器が、チャンネルノイズと衝突ノイズとを、たとえば、循環冗長度チェック（Cyclic Redundancy Check（ＣＲＣ））などでは区別できないような状況において必要となる。文書３で指摘されているように。ユーザーが送信パワースペクトルを低く保てば、拡散スペクトルランダムアクセスシステムは、成功/不成功フィードバックに帰着する。しかしそうすると、２個かそれ以上のパケットの衝突から生ずるノズル様の波形を、ノイズのみの波形と区別することが難しくなる。２進フィードバックのいま１つの例としては、無線のATM（Asynchronous Transfer Mode，非同期転送モード）ネットワークがあり、そこでは移動ユーザーのアクセス地点の低レートでのフィードバックが、ユーザーに送出されたパケット中にエラーが検出されたか（この場合、再送出を強制する）どうかを報せている。成功/不成功フィードバックについては、以前に文書Ｄ３で述べられているように、チャンネルあたりの成功送出率で測った動作状態は、最良でスループット０．３２９（３２．９％）である。
１９９０年に出版された、Problemi Peredachi Informatsii，２６巻、３号、６７−８２ページ所載の論文「Random Multiple Access in a Channel with Binary Success/No-Success（２進成功/不成功フィードバックを含むチャンネル内でのランダム多数アクセス）」（文書Ｄ５）において、成功/不成功フィードバックのスループットが、１９７２年５月に出版され、１９７５年にComputer Communication Review，５巻、２８−４２ページに再版された「ALOHA Packet System With and Without Slot Capture（スロットおよびキャプチャーつき、ならびに、スロットおよびキャプチャーなしのＡＬＯＨＡパケットシステム）」（文書Ｄ４）中に述べられているＡＬＯＨＡによる到達可能最大スループットである、１／ｅ（約０．３６８）、にまで改善され得るだろうということが述べられていた。
ランダムアクセスシステムでの補助ユーザーの概念が文書Ｄ２ではじめて導入され、それはまた、文書Ｄ５および１９８９年に出版された、IEEE Transactions on Communications，COM-３７巻、526−530ページ所載の論文「A Limited Sensing Random-Access Algorithm with Binary Success Failure Feedback（２進成功失敗フィードバックを含む有限センシングランダムアクセスアルゴリズム）」（文書Ｄ６）中で使われた。補助ユーザーとはある特定スロット中にダミーのパケットを送出するダミーのユーザーのことである。補助ユーザーのこの動作の目的は、１つのスロットを犠牲にして成功/不成功形のフィードバックをアイドル/成功/衝突形の３進フィードバックにインプリシットリーに（裏で）変換することである。すでに述べたように、衝突解消アルゴリズムであるべきプロトコールに対して、衝突解消の終結をすべてのユーザーが認識することが必須である。補助ユーザーあるいはテストパケットのような類似のコンセプトを使わなければ、このことは、文書Ｄ５でも述べられているように、複数のユーザーを含む環境にある純粋な成功/不成功フィードバックに対して不可能である。文書Ｄ６中で述べられているアルゴリズムでは、不成功フィードバック、すなわち、負のフィードバックが起こる毎に、その直後、ダミーパケットが１つのスロットを犠牲にして補助ユーザーによって送出される。文書Ｄ５に述べられているアルゴリズムにおいても、衝突の解消中に補助ユーザーによるダミーパケットの送出に対して複数のスロットが犠牲にされている。
本発明は、複数の端末器（ユーザー）によりアクセスされる時間スロットを持つ伝送チャンネルを含む通信ネットワークにおいて２進フィードバックを含むランダムアクセス通信についての新規で改良された方法を提案することが目的である；その方法によって送出不成功となったパケットが再送出され、また補助ユーザーはダミーパケットを送出する。
本発明によれば、これらの目的は、特に、独立請求項の特徴記述部の諸特徴によって達成される。さらに、従属請求項と詳細な説明から優れた実施例が出てくる。
特に、これらの目的は本発明によれば次のようにして達成される；すなわち送出不成功となったパケット、つまり衝突に含まれていたパケットの再送出の順序が、インターバル中でのそれらのパケットのそれぞれの位置に依存する；それにより、その位置は各パケットに割り当てられたパラメーター数値によって決定され、また、それらの数値は、パケットの衝突が解消されている時間中に起こっている負のフィードバック（不成功フィードバック）の終了後変更される。このようにして、その負のフィードバック（不成功フィードバック）が各スロット中の再送出されたパケット間の衝突によるものであったのか、あるいは、そのスロットが空（から）であったことによるものであったのかを判定するために、ダミーパケットを送出することによって時間スロットを犠牲にすることなく、これらのパケットの再送出の順序を決定するパラメーター数値が変更され、衝突の解消が続けられる。このことは、時間スロットをダミーパケットによって犠牲にすることなく、同一の衝突パケットの継続的な再送出によるデッドロック遭遇の危険を冒すことなく、繰り返される衝突を解消することができる、という利点を持っている。
本発明の好適実施例においては、各パケットに割り当てられた上記パラメーター数値が、各パケットの発生時刻にもとづいている。
本発明においては、前記パラメーター数値の変更の上記のステップは、好ましくは、ランダム化によって行われる。
本発明においては、負のフィードバック（不成功フィードバック）が各スロット中の再送出されたパケット間の衝突によるものであったか、あるいは、そのスロットが空（から）であったことによるものであったか、を判定するため、ダミーパケットは好ましくは負のフィードバックのある程度の発生の際にだけ送出される；すなわち先行する衝突が（完全に）解消された後の最初の負のフィードバックの際にだけ、それに続いてダミーパケットが送出される。このことは、ダミースロットによって犠牲にされるスロット数を減らすことができるという利点を持っている。
本発明においては、前記不成功に終わったパケットの再送出を可能にするかどうかは、好ましくは前記インターバルを２つの部分に分割する予め規定されたパラメーターによって決定される。この方法は衝突パケットを含むインターバルをはっきりとサブセットに分割することを可能にする簡便な方法を提供するものである。
本発明の変形においては、前記予め規定されたパラメーターは衝突回数に依存して変更される。このことは、本方法ならびにその効率が伝送チャンネルの現在の状況に対してダイナミックに適応できるという利点を持っている。
本発明においては、衝突は、好ましくは２回の引き続く正のフィードバックのメッセージ（成功フィードバック）によって示される２回の引き続く成功送出があって、はじめて解消される。
本発明においては、衝突に関係しなかった端末装置は、それらの装置が衝突の解消を知って後に初めてパケットの送出が許されることが好ましい。
本発明の好適実施例においては、前記通信ネットワークの少なくともあるものは移動無線ネットワークであり、端末の少なくともあるものは移動電話である。
本発明の好適実施例は、以下に、例を用いて示される。実施例は、以下の付属の図面によって示される。
図１は成功/不成功フィードバックの状態図である。
図２は、インターバル［０，ｘ）における送出のために発生されたパケットの例を示す。
図３は、成功/不成功フィードバックを含むランダムアクセス通信法のフローダイアグラムを示す。
図４は、端末装置（ユーザー）、共通受信者、ならびに補助ユーザーを含む模式的な通信ネットワークのブロック図である。
提案されている方法は、図４に示すように、複数の端末装置２、すなわちネットワーク１のユーザー２、たとえば衛星通信ネットワーク、ローカルエリアネットワーク（ＬＡＮ）、移動無線ネットワークなどからアクセスされる、時間スロット伝送チャンネルを含む通信ネットワーク１におけるランダムアクセス通信用として意図されている。したがって、受信ユーザー２，３に対する伝送チャンネル、すなわち送出チャンネルは、時間スロットで分割された衝突形のチャンネルである。送出チャンネルに対する偶発的ノイズ、あるいはその他の妨害は本方法では考慮されておらず、それらは他の方法、たとえば、ここで提案された方法の主題でない何か付加的な通信プロとコールの段階で処理されるものと想定している。２個あるいはそれ以上のデータパケット間の衝突は、その中に含まれるすべての情報を破壊すること、すなわち、衝突に含まれたパケットは受信ユーザー２あるいは３で再構成することはできない。更に、ユーザー（複数）２は１スロットの継続時間の間にパケット（複数）を送る、すなわちただ１人のユーザー２が１スロットの継続時間の間に１個のパケットを成功裡に送れるのみであると想定されている。
ここに提案されている方法では、通信ネットワーク１に参加しているユーザー２に、各スロットの終わりに、たとえば、共通受信器３から２進の成功/不成功フィードバック

が供給される。それによって、ユーザー２は、そのスロットが成功裡に送出された１個のパケットを確かに含んでいたかどうか、あるいはそのスロットが正確に１個のパケットを含んでいなかったかどうか、すなわちそのスロットが空（から）であったかどうか、あるいは、そのスロットが２個あるいはそれ以上の衝突パケットを含んでいたかどうか、を知らされ、衝突解消プロセスがはじめられる。送出チャンネルについて述べたように、フィードバックチャンネル、すなわち、ユーザー２に対するフィードバックを供給するための伝送チャンネルに対する偶発的ノイズ、あるいは、その他の妨害についても、本方法では考慮しておらず、それらは、他の方法、たとえばここで提案されている方法の主題ではない何か付加的な通信プロトコールの段階、により処理されるものと想定している。２進フィードバックの供給についての伝搬遅延はスロットの継続時間に対して無視できる程度に小さいと想定でき、したがって、与えられたスロットに対するフィードバック情報は、引き続くスロットに誰が送信できるかを決定するのに有効に使うことができる、ということにも注目しなければならない。共通受信器３による受信は、使われている通信ネットワーク１のタイプに応じて、当該分野に精通する何人（なんびと）によっても知られている種々の方法で実行することができる。たとえば移動無線ネットワークでは、共通受信器３の受信を、ネットワークのベースステーションの各ソフトウエアプログラムで実行することも可能である；その場合には、ベースステーションで、それらがメモリーとかデーターキャリアーにしまわれていて、プロセッサーによって処理されてもよい。
さらに説明を加えれば、送出チャンネルとフィードバックチャンネルとは、たとえば、もしフィードバックがネットワーク１に接続されている当該装置で実行されている共通受信器３で行われているならば、同じ通信手段で実現してもよいし；またもし、フィードバックチャンネルが少なくともネットワーク１に接続されている端末２にある何等かの手段で行われているなら、異なる通信手段で実現してもよい；ということを挙げておかなければならない。
以上に示したように、提案されている方法に用いられている２進フィードバック

は、ユーザー２が空（から）のスロットと衝突パケットを含むスロットとの間の判別を、そのまま可能とするものではない。与えられたスロットにパケットを送って、不成功のフィードバック

を受け取ったユーザー２は、そこに衝突があったことを知ることになるが、「サイレントな」ユーザー２は空（から）のスロットと衝突スロットとを区別することができない。空（から）のスロットと衝突スロットとの区別がすべてのユーザー２に対して可能となるために、本方法は、本発明の衝突解消方法によって指定された特定のスロットの期間にダミーパケットを送出するダミーユーザーである補助ユーザー４を少なくとも１つ使うことになる。補助ユーザー４の動作の目的は、１つのスロットを犠牲にして成功/不成功形フィードバック

をアイドル/成功/衝突形の３進フィードバックに裏で（インプリシットリに）変換することである。すでに述べたように、衝突解消アルゴリズムであるべきプロトコールに対して、衝突解消の終結をすべてのユーザー２が認識することが必須である。補助ユーザーつまりダミーユーザー４の動作は、使われている通信ネットワーク１のタイプに応じて、当該分野に精通する何人によっても知られている種々の方法で実行することができる。たとえば、移動無線ネットワークでは、補助ユーザー４の動作を、ネットワークのベースステーションの各ソフトウエアプログラムによって実行することも可能であり；またローカルエリアネットワークの場合には、ネットワークの特別の目的を持つノードで実行することもできる。ベースステーションあるいは特別の目的を持つノードにおいては、それぞれ、ソフトウエアプログラムはメモリーとかデーターキャリアーにしまわれてもよいし、プロセッサーによって処理してもよい。本発明の変形においては、共通受信器３と補助ユーザー４は同一の物理装置で実行することも可能である。
ここに提案した方法は衝突解消の期間のブロック化されたアクセスにもとづいていること、すなわち衝突解消に関与しなかったユーザー（複数）２は、それぞれの衝突が解消されたという情報を受け取ってからでなければパケットの送出を許されない、ということも指摘しておくべきである。何のデーターも送出しなかったユーザー（複数）２は、空（から）のスロットと衝突パケットを含むスロットとの判別ができないのであるが、このことは、それらが、負のフィードバック

が発生した時から、負のフィードバック

が空（から）のスロットによるものなのか、それぞれの衝突が解消されたためなのか、が通知されるまで、それらがパケットを送出することを許されない、ということを意味している。その目的を達成するために、通信ネットワーク１に接続されている端末装置２、すなわち、参加しているユーザー２は、以下により詳しく述べるように、提案されている方法を実行する。
２進フィードバック

を含むランダムアクセス通信に対する提案の方法では、下限ａ_tを含み、上限ｂ_tを含まないインターバル［ａ_t，ｂ_t）において、ユーザー２によって発生されたデーターパケットは、スロットｔ＋１の期間の送出可能インターバルＥ_t+1＝［ａ_t，ｂ_t）中に送出することができる。たとえば、図２は、パケットＰ１およびＰ２が発生した、下限ａ₀＝０、上限ｂ₀＝ａ₀＋ｘ＝ｘ，を持つインターバル［０，ｘ）を示している。インターバルＥ＝［０，ｘ）が送出可能になると、これら継続時間ｘの２個のパケットの両方がスロット１の期間に送出されるが、前にも述べたように１つのスロット中には１個のパケットの送出のみが可能なので、それら２個のパケットは衝突してしまう。この衝突の解消と引き続くスロットへのこれら２個のパケットＰ１、Ｐ２の再送出は、後に、もっと詳しく説明される。
送出可能インターバルＥ₁＝［０，ｘ）の期間のいかなる（無し、を含んでの）通信アクティビティーに対する結果、すなわち、対応するスロットが送出成功パケットを含んでいたか、あるいは、その特定のスロットが送出成功パケットを含んでいなかったか、を示す２進フィードバック

が、上に説明したように、たとえば、共通受信器３で処理可能な関数θ（Ｅ_t）によって表示され、それによって、θ（Ｅ_t）＝Ｓが成功結果、すなわち各スロットが送出成功パケットを含んでいたこと、また、

が成功結果がなかったこと、すなわち各スロットが送出成功パケットを含んでいなかったこと、を示している。
図１の状態図は、状態Ｓ₀，Ｓ₁，Ｓ₂，ならびにＳ₃間の状態遷移を示しており、そこで、状態遷移は、イネーブルとされたインターバルＥ_tの結果、すなわち関数θ（Ｅ_t）の値を示している。状態遷移は引き続くインターバルＥ_t+1がいかに、それに先行するイネーブルとされたインターバルＥｔとそのインターバルに対する結果に依存しているかを判定する。本方法は状態Ｓ₀からはじまり、そうして、本方法はイネーブルとされたインターバルE_tの結果のθ（E_t）が成功、すなわち、θ（Ｅ_t）＝Ｓであるかぎり、状態Ｓ₀にとどまる。通信ネットワーク１に接続されていて、かつ、本方法を実行する特定の端末機器２であるユーザー２に対して、このことは、状態Ｓ₀にある間、それが正のフィードバックＳを受け取っているかぎり、状態Ｓ₀にとどまることを意味している。
図３に示されたフローチャートの最初のステップ１００において、本方法は、ｔ＝０で初期値ａ₀＝０ではじまり、初期状態Ｓ₀でインターバルＥ₁＝［０，ｘ）にあるステップ１１０へ続く。このようにして、送出可能インターバルＥ₁＝［０，ｘ）にあって、ユーザー２によって発生されたいかなるデーターパケットも、この初期インターバルに対応するスロットｔ＝１中に送出することができる。ｘの値（ｘ＞０）は後で決定される。
ステップ１２０では、共通受信器３は、それが送出成功データーパケットを受け取ったかどうかをステップ１２１でチェックすることによって、それに先行して送出可能となったインターバルにフィードバックして、ユーザー２に供給する。もし、そこに送出成功データーパケットがあったならば、共通受信器３は、ステップ１２３において、すべてのユーザー２に正のフィードバックＳを送る。まだ状態Ｓ₀にあり、正のフィードバックθ（Ｅ₁）＝Ｓを受け取っているユーザー２は、ステップ２００のインターバルをａ_t+1＝ａ_t＋ｘと増加し、次のインターバルＥ_t+1＝［ａ_t，ａ_t＋ｘ）を送出可能とする。しかし、もし共通受信器３がステップ１２１で、それが、成功裡に送出されたデーターパケットを受け取って居なかったことを判定するとすれば、それが多くのデーターパケット間の衝突によるものであったのか、または、それがそのスロットが単に空（から）であったことによるものであったのか、にかかわらず、共通受信器３はステップ１２２ですべてのユーザー２に負のフィードバック

を送ることになる。
状態Ｓ₀にある間に、負のフィードバック

が送られると、本方法は、図１に示すように、状態Ｓ₁に移る。図３に示されているフローチャートでは、このことは、ユーザー２が状態をＳ₁にセットし、それ以前にイネーブルとしたインターバルＥ_t+1＝Ｅ_tを、再び、イネーブルとするステップ１３０中に反映されている。同時に、補助またはダミーのユーザー４は状態をＳ₁にセットし、ダミーパケットをスロット１４０中に送り出す。このようにして、もしステップ１２２で出された負のフィードバック

が衝突データーパケットによるものであったならば、これらのデーターパケットは、イネーブルとしたインターバルＥ_t+1＝Ｅ_t中で再び衝突を起こすであろうし、一方、もしステップ１２２で出された負のフィードバック

が空（から）のスロットによるものであったならば、ダミーパケットがステップ１４０で補助ユーザーによって衝突することなく送出されることになる。
共通受信器３は、ステップ１５０で、それが送出成功データーパケットを受信したかどうかをステップ１５１でチェックすることによって、それ以前にイネーブルとされたインターバルへのフィードバックをユーザー２に送る。もし送出成功データーパケットがあったならば、すなわち、もしダミーパケットが衝突することなく配送されたならば、共通受信器３はステップ１５３ですべてのユーザー２に正のフィードバックＳを送る。図１の状態図で示されているように、状態Ｓ₁で正のフィードバックが供給された場合には、本方法は状態Ｓ₀に戻る。図３に見られるように、状態Ｓ₁にあり正のフィードバックＳを受け取っているユーザー２は、ステップ２００においてインターバルをａ_t+1＝ａ_t＋ｘと増加してステップ１１０に進み、状態Ｓ₀にある次のインターバルＥ_t+1＝［ａ_t，ａ_t＋ｘ）を送出可能とする。しかし、もし共通受信器３が、ステップ１５１において、それが順次送られてくるデーターパケットを受信しなかったならば、それは、ステップ１５２で、すべてのユーザー2に負のフィードバック

を送る。このように、ステップ１５２で、共通受信器３によって負のフィードバック

が供給されると、すべてのユーザー２は、ステップ１２２で共通受信器３によって供給された最初の負のフィードバック

が空（から）のスロットにるものではなく、データーパケットの衝突によるものであったことに気付く。
図１の状態図で示したように、状態Ｓ₁で負のフィードバック

が供給されると、本方法は状態Ｓ₂に移る。これに対応して、図３に示されたフローチャートのステップ１６０において、状態Ｓ₂で、ユーザー２は、それ以前に再びイネーブルとされたインターバルの下位部分Ｅ_t+1＝［ａ_t，ａ_t＋αｘ）を送出可能とすることにより、検出された衝突の解消を開始する。このようにして、インターバルのこの下位部分の中で発生されたデーターパケットだけが、ユーザー（単数、ならびに複数）２に送出される。インターバルを２つの部分に分割するパラメーターであるα（１≧α≧０）の最適値は後に決定される。
ステップ１７０では、共通受信器３が、ユーザー２にそれが送出成功データーパケットを受け取ったかどうかを、ステップ１７１でチェックすることによって、インターバルの再びイネーブルとされた下位部分へのフィードバックを供給する。もし共通受信器３が、ステップ１７１で、それが送出成功データーパケットを受信しなかったと判定するならば、ステップ１７２で、すべてのユーザーに負のフィードバック

を供給する。しかし、この段階では、負のフィードバック

がインターバルの下位部分での多くのパケットの衝突によるものなのか、空（から）のスロットによるものかは、明らかでない。もう１つのダミーパケットを送ることによって、もう１つのスロットを犠牲にするよりも、また同じ空（から）のスロットを再びイネーブルとすることを避けるため、本方法はそのインターバル中の（少なくとも２個の残っている）パケットの位置を変えることによりステップを進める。このようにしてステップ２１０において衝突解消に関与したユーザー２が、そのインターバル中のそれらのパケットの位置をランダム化する。このことは、分散システムに適する技術分野に精通した何人（なんびと）によっても知られているランダム化のアルゴリズム、すなわち、ネットワーク１に接続されている種々の端末装置２に同じランダム数値を同時に発生することのないようなアルゴリズムによって達成できる。図１の状態図に示されているように、状態２において負のフィードバック

が与えられた途端、その方法は状態２に留まる。図３のフローチャートから分かることができるように、ユーザー２はステップ１６０で状態Ｓ₂にあることを続け、そのインターバルの同じ下位部分Ｅ_t+1＝［ａ_t，ａ_t＋αｘ）を再びイネーブルとする；しかし今度は、関与するユーザー２のデーターパケットがその同じインターバル内で新しい位置を占めている。
一方、もし共通受信器３がステップ１７１で送出成功データーパケットがあったと判定したならば、共通受信器３は、ステップ１７３ですべてのユーザー２に、衝突パケットの少なくとも１個が、ここで成功裡に再送出されたということを表す正のフィードバックＳを送る。図１の状態図で説明したように、状態Ｓ₂で正のフィードバックがあると、本方法は状態Ｓ₃に遷移する。図３に見られるように、衝突解消に関与し、なおも再送出すべきデーターパケットを保持しているユーザー２は、ステップ１８０で、そのインターバルの残りの上位部Ｅ_t+1＝［ａ_t＋αｘ，ａ_t＋ｘ）をイネーブルにすることと等価な動作として、全インターバルＥ_t+1＝［ａ_t，ａ_t＋ｘ）をイネーブルにし、この上位部分にある位置でデーターパケットを再送出することにより状態Ｓ₃にあることを持続する。
ステップ１９０では、共通受信器３がステップ１９１で、それが送出成功データーパケットを受け取ったかどうかをチェックすることにより、そのインターバルの再びイネーブルとなった上位部分へのフィードバックをユーザー２に送る。ステップ１３１において、もし共通受器３が、それが送出成功データーパケットを受け取らなかったと判定すれば、共通受器３は、ステップ１９２ですべてのユーザー２に負のフィードバック

を送る。図１の状態図に示したように、状態Ｓ₃に負のフィードバック

が送られると、この方法は状態Ｓ₂を持続する。図３のフローチャートに見られるように、衝突に関与したユーザー２はステップ２１０で残りのパケットの位置を再びランダム化することによって、またそのインターバルＥ_t+1＝［ａ_t，ａ_t＋αx）の下位部分を再びイネーブルとすることによって、その状態を維持する。しかしもし共通受信器がステップ１９１において送出成功パケットがあったと判定するならば、共通受信器３はステップ１９３において、すべてのユーザー２に１個の残りのデーターパケットの再送出にいま成功したということを示す正のフィードバックを送る。図１の状態図に示したように、状態Ｓ₃において正のフィードバックＳが送られると、この方法は状態Ｓ₀に遷移し、衝突が解消される。図１の状態図に見られるように、衝突の解消は引き続く２回の送出成功があって初めて終了するので、すべての関与した衝突解消の終了を検出することができる。
図３のフローチャートに示したように、衝突解消の後、ユーザー２は、ステップ２００でインターバルをａ_t+1＝ａ_t＋ｘと１つ増やしてステップ１１０に進み、状態Ｓ₀にある次のインターバルＥ_t+1＝［ａ_t，ａ_t＋ｘ）をイネーブルにする。
当該技術分野に精通する人であれば誰でも、本提案の方法が端末装置２で実行可能となる種々の方法をよく知っている。たとえば本方法の各ステップは、図３のフローチャートに示したように端末装置２で実行されているが、それはたとえば、プログラム可能なメモリーとかチップカードのメモリーといったように、端末装置２の格納装置２１によって格納可能なソフトウエアープログラムとしても実行することができる；たとえばマイクロプロセッサーとかチップカードなどの端末装置の処理手段２２によって処理することもできる。本発明による方法を実行するための処理方法とか格納手段とは別に、本方法に関与するすべての装置は、状態遷移のトラッキングを維持するために、状態情報を格納するための手段、たとえば装置のリード・ライトメモリーとか装置に挿入するチップカードなどをも持っていなければならない。

より明瞭に説明するために、図２は、インターバル［０，ｘ）における送出するために発生されたパケットの１例を示している。時間軸ｔに沿ってならぶ垂直の矢印は、何時（いつ）発信者が、すなわち関与しているユーザー２が、送出すべきパケットＰ１、Ｐ２を発生したかを示している。表１に見られるように、本方法は、インターバルＥ₁＝［０，ｘ）をイネーブルにすることによって、すなわちスロットｔ＝１の間にパケットＰ１とＰ２の送出をイネーブルとすることによって、状態Ｓ₀からはじまる。イネーブルとなったインターバルＥ₁＝［０，ｘ）に対応する１つのスロットに送出される２個のデーターパケットＰ１、Ｐ２があるので、各フィードバックθ（Ｅ₁）は負

である。次のスロットｔ＝２の間では、本方法は状態Ｓ₁にあり、ユーザー２は前のインターバルＳ₂＝［０，ｘ）を再びイネーブルとし、したがって、同じデータパケットＰ１、Ｐ２が再送出され、補助ユーザー４がダミーパケットを送出する。その結果得られるフィードバックθ（Ｅ₂）は再び負の

であり、したがって衝突のあったことが明らかになる。スロットｔ＝３の間では、本方法は状態Ｓ₂にあり、ユーザー２は前のインターバルＥ₃＝［０，αｘ）の下位部分をイネーブルとし、そのインターバルの下位部分にあるデーターパケットＰ１を再送出することによって、衝突解消をはじめる。これに対応するフィードバックθ（Ｅ₃）は正のＳであり、本方法は状態Ｓ₃に遷移する。
スロットｔ＝４の間では、各ユーザー２はインターバルＥ₄＝［αｘ，ｘ）の上位部分をイネーブルとし、このようにして、そのインターバルの上位部分にある残りのデーターパケットＰ２を再送出する。これに対応するフィードバックθ（Ｅ₃）は正のＳであるので、衝突解消は終了し、スロットｔ＝５のはじめでは、本方法は状態Ｓ₀を維持し、インターバルＥ₅＝［ｘ，２ｘ）をイネーブルとする。
パケットの位置のランダム化のために、パケットは、それらの発生時点での順序と同じ順序で送出されるとはかぎらない。したがって、本方法は「到着順」形ではない。
以下では、本方法の性能すなわちスループット、および、パラメーターｘとαの値が決められる。２進フィードバックをおこなうための伝搬遅延はスロットの継続時間に比べて無視できるほど小さく、したがって、ある与えられたスロットについてのフィードバック情報は、それに引き続くスロットに誰が送出できるかを決めるのに有効に使うことができる、という点に再度注意されるべきである。以前にも述べたように、あるインターバル中で発生したすべてのパケットが成功裡に送出されたとき、そのインターバルは解消されたと考える。基本のインターバルは、それに先立つインターバルが解消されたときはじめて始まる。処理の基本のインターバルへの引き続いている復帰の間のそれぞれの時間間隔は、衝突解消インターバル（collision resolution interval，ＣＲＩ）といわれる。本方法の性能、すなわち、スループットは、用いられたチャンネルあたりの成功送出の項で測定され、以下の更新理論にもとづく議論を用いて知ることができる。時間軸は、本方法で用いられる一連の衝突解消インターバルに区切られ、この衝突解消インターバルは、最初にそれらが含んでいるメッセージの数によって区別される。到来過程はポアッソンであるので、現実の時間軸上のいかなるインターバルを持つメッセージの最初の分布も一様であると想定され、したがって、ｉ個のメッセージを含む長さαの最初のサブインターバルにｋ個のメッセージが見いだされる確率は

で与えられる。
主要な関心量は、ω_k＝Ｅ［Ｗ_k］、すなわち、ｋ人の送信者の衝突を解消するのに必要なスロットの平均数である。最初に衝突はない（図１）ので、ω₀＝２で、ω₁＝１である。さらに次のこともわかる；

その理由は、最初の不成功のフィードバック（衝突）の後と、補助ユーザーのパケットの送出の後、１−ｐ_2,1の確率を持つ２人の送出ユーザー２は、両者が送出の権利（イネーブル）を与えられているか、いずれもが送出の権利を与えられていないか、であるからである。この場合、衝突を解消するのにもう一方のω₂−１個のスロットが必要である。一方、１人のユーザー２のみがイネーブルのセットにあるときには、本方法は確率ｐ_2,1で状態Ｓ₂から状態Ｓ₃へと遷移し、最初のパケットは成功裡に送出される。Ｓ₃ではすべてのインターバルがイネーブルとなるので、残りのパケットは成功裡に送出され、衝突は解消される。２個のパケットの衝突を解消するのに必要なスロットの平均数は、（１）式を解いた結果として

で表される。
ω_kについての一般的な循環式は、

となる。ただし、境界条件をω₂＝３＋１／p_2,1とする。
これは等価的に、次のように表される。

最初にｋ個のメッセージを含む基本的なインターバルに実際送出されると期待されるメッセージの数n_kは、上のアルゴリズムが、状態Ｓ₀に引き続いて戻る間の長さｘの基本的なインターバル中にすべての到着パケットを成功裡に送出するので、ｋに等しい。すなわち、

状態Ｓ₀のマルコフ過程としての性質が、大数の法則（あるいは、等価的には、更新過程に対する極限定理から）を通して、「ロングラン」のスループットηを次の（４）式で与えられる比で表すことを可能にしている。このようにして、スループットは、時間軸上のランダムな観測が成功に遭遇する確率に等しい。

ここにｑ_kは基本のインターバルが最初にｋ個のメッセージを含んでいる確率である。システムがそれ自体空（から）でないかぎり（システムは、ヘビーな負荷状態にあるとして）、初期の時間ウィンドウ中のメッセージ数は次のポアッソン分布を持っている。ただし、パラメーターλxはチャンネルの活動率の過去の履歴に依存している。この場合には、

（３）式と（４）式は、任意のλxとαに対して、提案されたアルゴリズムの効率を見いだすための数値的な手続きを与える。コンピューターによる結果は、λxがほぼλx≒１．４０（有意な１０進桁数に丸めて）で、αがα≒０．３８であるときに、約０．３７２のアルゴリズムの最大安定なスループットを示している。もし平均の到着レートがスロットあたり０．３７２よりも少なければ、システムは最後にはそれ自身空（から）になり、したがって安定になる。
提案された方法の計算された０．３７２のスループットは、先行技術で知られた他の２進成功/不成功フィードバックを含むランダムアクセス通信法のどのスループットとよりも高い値である。
提案された方法が、イネーブルとされたインターバルＥ_tのパケットの存在についてどのような仮定をもしていないということを指摘しておかなければならない。したがって、提案された方法はまた、新規の送り手が通信システムに入って来るような環境においても、適正に動作する。
提案された方法の変形において、パラメーターαの値は、本方法が状態Ｓ₂を通過する回数、すなわち衝突の回数によって変わる。したがって、提案された方法の効率は、さらに改善可能である。
送出不成功のパケットが、イネーブルとなったインターバル中でそれらの位置によって再送出されるとき、各パケットの位置は、そのパケットの発生時間にもとづいて決められるということを先に述べた。しかし、ランダム化が起こる前でも、発生時間以外の数値的な値をイネーブルとなったインターバル中のデーターパケットの位置について識別するのに使うことは、当該分野に精通した何人（なんびと）にとっても容易なことである、ということを注意しておくべきであろう。

Claims (12)

1. 複数の端末装置（２）によってアクセスされる時間スロット伝送チャンネルを持つ通信ネットワーク（１）におけるランダムアクセス通信方法であって、
   前記複数の端末装置（２）は、ある１つのスロットが成功裡に送出されたパケットを含んでいたことを示す正のフィードバック（Ｓ）と、前記スロットが成功裡に送出されたパケットを含んでいなかったことを示す負のフィードバック（Ｓ）とを表す２進フィードバック（Ｓ／Ｓ）を供給され、
   負のフィードバック（Ｓ）が発生すると、その負のフィードバック（Ｓ）が前記スロット中での複数のパケットの衝突によるものであったのか、前記スロットが空（から）であったことによるものであったのかを判定するため、補助ユーザー（４）はダミーパケットを送出し、
   前記負のフィードバックが複数のパケットの衝突によるものであったと判定されるとき、その衝突を解消するため、送出が不成功に終わった前記複数のパケットが再送出され、
   前記再送出における当該複数のパケットの順序は、１つのスロットの中の１つのインターバルの中での前記複数のパケットの位置に依存しており、前記位置は前記複数のパケットの各々に割り当てられた第１パラメーターの数値によって決定され、前記数値は、前記衝突の解消の間に（Ｓ ₂ −Ｓ ₃ ）負のフィードバック（Ｓ）が起こると変更される（２１０）、ランダムアクセス通信方法。
2. 前記負のフィードバック
   

   

   が、前記衝突が生じる前に起きた衝突が解消された後の最初の負のフィードバック
   

   

   であることを特徴とする、請求項１によるランダムアクセス通信方法。
3. 前記数値の少なくとも一部がパケットの発生時間にもとづいて決められることを特徴とする、請求項１または２によるランダムアクセス通信方法。
4. 前記数値の変更が、乱数発生処理に基づく変更であることを特徴とする、請求項１〜３のいずれか１つによるランダムアクセス通信方法。
5. 前記送出が不成功に終わったパケットの前記再送出のイネーブルが、前記インターバルを２つの部分へ分割する予め規定された第２のパラメーター（α）によって決められることを特徴とする、請求項１〜４のいずれか１つによるランダムアクセス通信方法。
6. 前記第２のパラメーター（α）が前記衝突の数によって変えられることを特徴とする、請求項５によるランダムアクセス通信方法。
7. ２個の引き続く正のフィードバック（Ｓ）によって示される２個の引き続く成功送出の後に、前記衝突が解消されることを特徴とする、請求項１〜６のいずれか１つによるランダムアクセス通信方法。
8. 衝突解消に関与しなかった端末装置（２）は、その衝突の解消を知った後にのみ、パケットの送出が許されることを特徴とする、請求項１〜７のいずれか１つによるランダムアクセス通信方法。
9. 前記複数の通信ネットワーク（１）の少なくとも一部が移動無線ネットワークであり、前記複数の端末装置（２）の少なくとも一部が移動無線電話であることを特徴とする、請求項１〜８のいずれか１つによるランダムアクセス通信方法。
10. 前記２進フィードバック
    

    

    が端末装置（２）に対して少なくとも１つの共通受信器（３）により提供されることを特徴とする、請求項１〜９のいずれかによるランダムアクセス通信方法。
11. 請求項１〜１０のいずれか１つによる方法を実行するための処理手段（２２）ならびに記憶手段（２１）を備えることを特徴とする、時間スロット伝送チャンネルを持つ通信ネットワーク（１）中のランダムアクセス通信用端末装置（２）。
12. 前記端末装置（２）が移動無線ネットワーク（１）中で通信する移動電話器（２）であることを特徴とする、請求項１１によるランダムアクセス通信用端末装置（２）。

Images