(57)【特許請求の範囲】
【請求項１】
端末局装置が基地局装置に対してアクセスするアクセス方式において、
前記端末局装置から前記基地局装置へのパケットの衝突を解決するために、前記基地局装置は、ツリーアルゴリズムの２分岐において、一方の分岐に属する前記端末局装置から送信がなかった場合、もう一方の分岐の１階層深い２分岐の一方の分岐に属する前記端末局装置の再送を容認することで、パケットの衝突を解決する
ことを特徴とするツリーアルゴリズムを用いたアクセス方式。
【請求項２】
請求項１に記載のアクセス方式において、
前記基地局装置は、前記１階層深い２分岐の一方の分岐に属する前記端末局装置の再送を容認した際に、
前記端末局装置から送信がなかった場合に、前記１階層深い２分岐のもう一方の分岐に属する前記端末局装置の再送を容認する
ことを特徴とするツリーアルゴリズムを用いたアクセス方式。
【請求項３】
端末局装置がアクセスする基地局装置において、
前記端末局装置から送信されるパケットの衝突を解決するために、
ツリーアルゴリズムの２分岐において、一方の分岐に属する前記端末局装置から送信がなかった場合、もう一方の分岐の１階層深い２分岐の一方の分岐に属する前記端末局装置の再送を容認することで、パケットの衝突を解決する
ことを特徴とするツリーアルゴリズムを用いた基地局装置。
【請求項４】
請求項３に記載の基地局装置において、
前記１階層深い２分岐の一方の分岐に属する前記端末局装置の再送を容認した際に、前記端末局装置から送信がなかった場合に、前記１階層深い２分岐のもう一方に属する前記端末局装置の再送を容認する
ことを特徴とするツリーアルゴリズムを用いた基地局装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の端末局装置が基地局装置に接続されており、端末局装置及び基地局装置間における双方向の通信が確保されている通信路において、端末局装置から基地局装置に対してパケットを送信するアクセス方式、及び基地局装置に関する。
【背景技術】
【０００２】
送信制御にバックオフ・プロトコルを用いるランダムアクセス方式に関して、再送トラヒックに対するポリシーの違いによって様々な方法がある。
例えば、再送パケットも新規のパケットと同一の衝突回避制御期間を用いるユニフオーム・ポリシーや、再送回数に応じて衝突回避制御期間を指数的に増加させるエクスポネンシヤル・ポリシーなどがある。
用いるポリシーによってパケットの遅延特性には違いが生じるが、最大スループットが１／ｅ（＝０．３６８）を上回ることはない。
【０００３】
こうしたスロッテド・アロハ方式に対して、スループットを改善させることを目的にいくつかの方式が考案されている。
ＣＳＭＡ（Carrier Sense Multiple Access）方式においては、端末局装置は送信前に送信するチヤネルをキヤリアセンスして他の端末局装置が送信していないか判断し、他の端末局装置が送信中の場合はその送信を待って送信することで衝突を回避してスループットを改善している。
このＣＳＭＡ方式は、ＩＥＥＥ８０２．１１（無線ＬＡＮ）で用いられている（非特許文献１参照）。
【０００４】
しかし、端末局装置間の距離が長すぎたり、壁などの電波を通さない障害物があったりして、電波が到達しないことがある。このように互いの送信信号が到達しない端末局装置を隠れ端末と呼ぶ。
上記隠れ端末が存在すると、隠れ端末に対してキャリアセンスが有効に機能しないため、ＣＳＭＡ方式では衝突の頻度が増し、特性を悪化させる。
【０００５】
隠れ端末の存在によるＣＳＭＡ方式の性能劣化を解決するために、基地局装置が集中して共用回線の管理と端末局装置の制御を行なう方式がある。
ＢＴＭＡ（Busy Tone Multiple Access）方式においては、基地局装置がチャネルの使用状況を監視し、フレーム伝送がある場合はビジートーンを報知する。各端末局装置は、基地局装置からの報知信号に基づきアイドル回線にアクセスすることができる。しかし、メッセージ用チャネルのほかにビジートーン用チャネルを利用可能な周波数帯域に用意する必要があるため、周波数の利用効率が悪くなる（例えば、非特許文献２参照）。
【０００６】
一方、ＩＣＭＡ（Idle-signal Casting Multiple Access）方式では、基地局装置がチャネルの使用状況を監視し、チャネルがアイドルである場合にアイドル信号を周期的に送出する。各端末局装置は、アイドル信号に同期して送出することで、フレームの衝突を避けることができる。単一チャネルでメッセージ信号とアイドル信号の両方を伝送できるため、ＢＴＭＡ方式より効率が良い。しかし、アイドル信号の送出周期に比べてデータフレームの伝送時間が短くなるにつれて最大スループットは低下する（例えば、非特許文献３参照）。
【０００７】
基地局装置が集中して共用回線の管理と端末局装置の制御とを行なう方式として、他に予約方式がある。
reservation−ＡＬＯＨＡにおいては、まずランダムアクセスによってリクエストフレームを送出し、その予約が成功してからデータフレームを伝送する。予約方式はリクエストフレーム長とデータフレーム長の関係に大きく依存する。リクエストフレームがデータフレームに対して十分に短いとき、最大スループットは１に近づくが、これが長くなるにつれてその最大スループットは低下する（例えば、非特許文献４参照）。
【０００８】
一方で、チャネルのアクセス情報などを端末局にフィードバックして、衝突した場合でも衝突を解決するスタック・アルゴジズムが存在する。
衝突を解決する手法としては、各端末局が保持しているユニークな番号（例えばＩＤ）を基にツリー状に絞り込むツリーアルゴリズム（例えば、非特許文献５参照）やトラヒックの発生時刻に基づいて絞り込むＦＣＦＳ（First come first served）アルゴリズム（例えば、非特許文献６参照）などがあるが、どのアルゴリズムも大きなトラヒックがアクセスすると衝突解決の効率が下がるため、高いスループットを得ることが出来ない。
【非特許文献１】IEEE Std. 802.11-1999, Part11: Wirless LAN Medium Access Control (MAC) and Physical Layer(PHY) spesifications. IEEE Std. 802.11, 1999 edition.
【非特許文献２】F. Tobagi and L. Kleinrock: "Packet switching in radio channels: Part II- the hidden terminal problem in CSMA and busy-tone solution", IEEE Trans. Commun., COM-23, pp. 1417-1433 (1975).
【非特許文献３】A. Murase and K. Imamura: "Idle-signal casting multiple access with collision detection (ICMA-CD) for land mobile radio" , IEEE Trans. Vehic. Technol., VT-36, 2, pp. 45-50 (1987).
【非特許文献４】S. S. Lam: "Packet broadcast networks - a performance analysis of the R-ALOHA protocol" , IEEE Trans. Computers, 29, 7, pp. 596-603 (1980).
【非特許文献５】J. I. Capetanakis: "Tree algorithms for packet broadcast channels" , IEEE Trans. Inform. Theory, IT-25, 5, pp. 505-515 (1979).
【非特許文献６】R. G. Gallager: "A perspective on multiaccess channels" , IEEE Trans. Inform. Theory, IT-31, 25, pp. 124-142 (1985).
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、スロッテド・アロハ方式の最大スループットは理論上１／ｅ（＝０．３６８）であり、その場合１００スロットあたり約３７スロットしか有効に使われていない。入力トラヒックがそれ以上ある場合でも残りは有効に使えないため、最大スループットの向上が重要な要素となる。スロッテド・アロハ方式の最大スループットを向上させるため、数多くのアクセス方式が提案されているが、いずれの方式においても効果を得るためにいくつかの前提が存在する。
【００１０】
すなわち、この前提として、ＣＳＭＡ方式においては、システム内における隠れ端末の割合が比較的少ないことであり、ＢＴＭＡ方式においては基地局の基地局装置／端末局の端末局装置が共に複数チャネルを同時に利用できることであり、ＩＣＭＡ方式やｒｅｓｅｒｖａｔｉｏｎ−ＡＬＯＨＡ方式においては、データフレームがアイドル信号送出間隔やリクエストフレームと比べて長いことであり、スタック・アルゴリズムにおいては、入力トラヒックの上限が規定されていることである。
【００１１】
しかし、上述した前提がいずれも満たせないシステムが存在する。すなわち、ユビキタス社会では、非常に多くの低能力端末が広域にわたり、非常に多数分布していると想定されている。
このような端末に対して経済的に対応するため、大きなカバーエリアを有する、基地局の基地局装置によって収容することが考えられる。
この場合、端末局装置と基地局装置との間においては、送信電力やアンテナ特性が、大きく異なる。このため、端末局装置間においては、互いの送信信号の到達しない隠れ端末が多数存在すると考えられる。
【００１２】
一方で、総端末コストを低く抑えるため、端末局の端末局装置が複数チャネルを同時に利用することや、非常に多くの端末局が存在するため、端末局装置が比較 的長いパケットを送信し、チャネルを長時間占有することは考え難い。また、システムとして、入力トラヒックの上限が規定されることも考え難い。
本発明は、このような事情に鑑みてなされたもので、既存の方式が前提としている条件を満たさないシステムにおいて、スロッテッド・アロハ方式以上の最大スループットが得られるアクセス方式及び基地局装置を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明のアクセス方式は、端末局装置が基地局装置に対してアクセスするアクセス方式であり、前記端末局装置から前記基地局装置へのパケットの衝突を解決するために、前記基地局装置は、ツリーアルゴリズムの２分岐において、一方の分岐に属する前記端末局装置から送信がなかった場合、もう一方の分岐の１階層深い２分岐の一方の分岐に属する前記端末局装置の再送を容認することで、パケットの衝突を解決することを特徴とするツリーアルゴリズムを用いたアクセス方式である。
【００１４】
本発明のアクセス方式は、上記発明に記載のアクセス方式において、前記基地局装置は、前記１階層深い２分岐の一方の分岐に属する前記端末局装置の再送を容認した際に、前記端末局装置から送信がなかった場合に、前記１階層深い２分岐のもう一方の分岐に属する前記端末局装置の再送を容認することを特徴とする。
【００１５】
また、本発明は、端末局装置がアクセスする基地局装置において、前記端末局装置から送信されるパケットの衝突を解決するために、ツリーアルゴリズムの２分岐において、一方の分岐に属する前記端末局装置から送信がなかった場合、もう一方の分岐の１階層深い２分岐の一方の分岐に属する前記端末局装置の再送を容認することで、パケットの衝突を解決することを特徴とするツリーアルゴリズムを用いた基地局装置である。
【００１６】
また、本発明は、上記発明に記載の基地局装置において、前記１階層深い２分岐の一方の分岐に属する前記端末局装置の再送を容認した際に、前記端末局装置から送信がなかった場合に、前記１階層深い２分岐のもう一方に属する前記端末局装置の再送を容認することを特徴とする。
【発明の効果】
【００２２】
以上説明したように、本発明によれば、隠れ端末が多数存在する状況において、端末局が比較的短いパケットを基地局に送信するシステムにおいて、各端末局から基地局へのアクセスのスループットが純ＡＬＯＨＡ方式やスロッテド・アロハ（Ｓｌｏｔｔｅｄ  ＡＬＯＨＡ）方式に比べて改善できると共に、高トラヒック負荷時のスループット特性及び遅延特性の劣化を抑えることができる。
【００２３】
また、本発明によれば、隠れ端末装置が多数存在する状況においても、各端末局装置から基地局装置へのアクセスのスループットを従来方式に比較して高くすることができるとともに、高トラフィック負荷時のスループット及び遅延特性の劣化を抑えることができる。
また、本発明によれば、端末局装置の数、アクセスの統計情報、直前の衝突回避制御期間に基づき、算出した最適な衝突回避制御期間を用いてアクセスすることができ、さらに高いスループットを得ることができる。
【発明を実施するための最良の形態】
【００２４】
以下の実施形態の特徴としては、複数の端末局装置から基地局装置にアクセスを行う方法において、端末局装置が公知のバックオフ・プロトコルを用いて送信制御を行う ランダムアクセスフェーズと、端末局装置が送信したパケットが衝突した場合に、例えば、端末局装置がツリーアルゴリズムを用いて、衝突を解決する衝突解決 フェーズとを設ける。
また、ランダムアクセスフェーズと衝突解決フェーズとの切替は、基地局装置がパケット衝突の有無に基づいて判定し、各端末局装置に対して報知する。
さらに、基地局装置は、端末局装置の数、アクセスの統計情報、直前の衝突回避制御期間に応じて、衝突回避制御期間を更新し、各端末局装置に報知する。
【００２５】
上述した構成により、本実施形態の方式においては、初めのランダムアクセス時のみバックオフを行い、再送時にバックオフを行なわないため、バックオフに用いる衝突回避制御期間によって大きく特性が異なってくる。例えば、図１は、端末局装置を１００台、入力トラヒックを１．０にして、衝突回避制御期間の違いによるスループットの変動を示してある。
また、ランダムアクセス送信によって送信パケットが衝突した端末局の送信を基地局装置からのフィードバックによって調整する場合、そのフィードバック・データの伝送中の損失を考慮しないといけない。
さらに、その衝突を解決するまでに必要なスロット数を低く抑えることが出来れば更に最大スループットを改善できる。
以下、上述した特徴の構成及び動作について説明する。
【００２６】
本実施形態の実施形態におけるランダムアクセス方式においては、バックオフ・プロトコルを用いて送信制御を行うランダムアクセス方式において、基地局の基地局 装置からの信号に基づき、端末局の端末局装置はバックオフフェーズと衝突解決フェーズとの２つのフェーズを切り替える。
このバックオフフェーズにおいては、送信待機時間が「０」になった端末局の端末局装置が送信し、衝突が発生すると衝突解決フェーズに移行する。この衝突解 決フェーズに移行すると、基地局の基地局装置は衝突を解決するためアクセス情報をフィードバックし、送信待ちの端末局の端末局装置は送信待機時間の減算を 停止する。基地局が衝突は解決したと判断した場合は、バックオフフェーズに移行する。
【００２７】
衝突解決にバイナリーツリー・アルゴリズムを適用した場合、スループットＳは以下の（１）〜（４）式のように表せる。
但し、ｎは端末局数、Ｗは衝突回避制御期間、λは各端末局で同一のパケット生起確率を表している。
【００２８】
【数１】
0004549987.tif 000002
【００２９】
本実施形態では、上記（１）〜（４）式における関係式より、端末局数や受信状況、直前の衝突回避制御期間に基づき最適な衝突回避制御期間を基地局の基地局装置が算出し、端末局に報知して、各端末局のバックオフ・プロトコルはその値の範囲内でランダムに送信待機時間を選択することで常に最大スループット を追求する方法を示す。
もちろん、上記（１）〜（４）式における関係式以外にも、各端末局の端末局装置におけるパケットの生起確率の違いから端末局間で重み付けを行なったり、上記関係式から導かれる別の指標を用いたりして最適な衝突回避制御期間を算出する手法も含む。
【００３０】
以下の実施形態では、衝突解決にあたり、一方の分岐でパケットの送信があるとみなせなかった場合、もう一方の分岐では複数の端末局が送信を控えていること は明らかであるため、更に階層を深くして条件を絞り込むことで、衝突を解決する方法を示す。この方法を適用した場合、先に示したｑｔは以下の（５）式のように表せるため、スループットも改善される。
【００３１】
【数２】
0004549987.tif 000003
【００３２】
また、衝突パケットの再送信タイミングを図っている端末局が、基地局からのアクセス情報を受信できなかった場合に、送信待機時間を再設定してランダムアクセスを再挑戦する。
さらに、上記のような再送信ができなかった端末局の存在により、再送信タイミングを決定するアルゴリズムが暴走するのを防ぐため、請求項１で示した絞込み手法を連続して行なわない（請求項２）。
以下の実施形態の説明において、簡略化のために、基地局の基地局装置を単に基地局と示し、端末局の端末局装置を単に端末局として説明を行う。
【００３３】
＜第１の実施形態＞
以下、第１の実施形態によるランダムアクセス方式を図面（図２〜図７）を参照して説明する。図２は同実施形態のネットワークの構成例を示すブロック図である。また、図３はフレーム構成を示すブロック図であり、図４は本実施形態の基地局の基地局装置におけるランダムアクセススロットの受信結果判定ロジック図である。図５は、本実施形態の基地局の基地局装置における動作フロ−を示すブロック図である。図６は、衝突解決のためのアルゴリズムとして本実施形態ではツリーアルゴジズムを用い、ツリーアルゴリズムの動作フローを示すブロック図である。図７は端末数に伴うスル−プットが最大となる最適な衝突回避制御期間の変化を表したグラフである。
【００３４】
図２に示すように、ネットワークの構成として、１つの基地局に複数の端末局が接続している。各円は端末局からの送信パケットに対する基地局及び端末局の受信エリアを示している。端末局Ｎ1は隣接する端末局Ｎ2の送信パケットは受信できるが、ＡＰ（基地局）の受信エリア内に存在する他の多く、例えば端末局Ｎ2〜Ｎ5の送信パケットは受信できない。
この場合、例え端末局Ｎ2〜Ｎ5がＡＰに対してランダムアクセスしていたとしても端末局Ｎ1では受信できないため、端末局Ｎ1からの送信を回避することはできない。このように互いの送信信号が受信できない隠れ端末（端末局）が多く存在するネットワークでは、キャリアセンスが有効に機能しないため、ＣＳＭＡ方式では特性を悪化させる。
【００３５】
図３に示すように、１チャネルを上り及び下りトラヒックで時分割しているＴＤＤ回線であり、端末局から基地局へのＲＡスロットと基地局から端末局へのフイードバックスロット（ＦＢスロット）が交互に繰り返されている。ＦＢスロットには直前のＲＡスロットのアクセス結果（衝突、成功、空き）、次のＲＡスロットのアクセスフェーズ情報（ランダムアクセスフェーズまたは衝突解決フェーズ）、必要に応じて受信応答（ＡＣＫ）やパーシャルエコー（ＰＥ）などが含まれる。
【００３６】
図４に示すように、基地局においては、以下のようなロジックを組み込むことにより、各ＲＡスロットにおける受信結果を“衝突”、“成功”、“空き”の３種類で判断できる。
まず、スロットタイミング毎に（Ｓ１）、ＣＲＣなどの誤り検出符号によって（Ｓ２のエラー検出）誤りが検出されない場合は“成功”とみなす。一方、誤りが検出された場合は、受信電力の平均値などをＲＳＳＩ測定器で測定し、受信電力（受信強度）が一定閾値より大きいか否かの判定を行い（Ｓ３）、閾値以上の場合は“衝突”と判断する。また、受信電力が閾値未満の場合は“空き”と判断する。
【００３７】
もしくは、同期（フレーム同期、周波数同期、クロック同期）をとるために既知パターンがランダムアクセスのパケットに付与されている場合、その既知パターンは共通であるため、例え複数の端末局が同時にランダムアクセスして衝突したとしても正常に検出される可能性が高い。そこで、受信電力以外にもこの既知パターンによる同期確立の有無によって“衝突”と“空き”を判断することも可能である。ここで、同期確率が“有”ならば“衝突”と判断し、“無”ならば“空き”と判断する。
【００３８】
また、基地局においては、上述したように判断したＲＡスロットのアクセス状況に基づき、図５に示すように、次のＲＡスロットのアクセスフェーズを決定する。
ランダムアクセスフェーズにおいて、パケットの衝突が発生しないか否かの判定を行っており（Ｓ１１）、衝突が発生しない限りはランダムアクセスフェーズを続け（Ｓ１０）、衝突が発生したならば、次のＲＡスロットで衝突解決フェーズに切り替わる（Ｓ１２，Ｓ１３）。
衝突解決フェーズにおいては、衝突解決のためＲＡスロットのアクセス結果が基地局から端末局にフィードバックされる。
【００３９】
そして、衝突解決フェーズの間、新規にパケットが生起した端末局は衝突回避制御期間に基づき、送信待機時間を選択して送信待ち状態に遷移する。しかしながら、パケットの送信待ち状態の端末局は一時バックオフ・プロトコルを停止して、送信待機時間の減算やパケットの送信を行なわない。
そして、基地局で各端末局間のパケットの衝突がすべて解決したと判断したならば、ランダムアクセスフェーズに切り替え、その情報を端末局にフィードバックする。
【００４０】
図６に示すように、端末局Ｎ0、Ｎ2、Ｎ6、Ｎ7の送信するパケットが衝突したケースを考える。図６（ａ），６（ｂ）に示すツリーアルゴリズムにおいては衝突を解決するため、枝Ｔｍ，ｎ（但し、ｍは階層数を、ｎは各階層における枝の通し番号を表す。）を２分割していく。
まず、枝Ｔ１，０に属する端末局がパケットの再送を試み、端末局Ｎ0とＮ2が再送したパケットが衝突する。再度、パケットが衝突したため更に階層を深くして、枝Ｔ２，０に属する端末局がパケットの再送を試み、端末局Ｎ0が成功する。
そして、枝Ｔ２，１に属する端末局がパケットの再送を試み、端末局Ｎ2が成功する。
【００４１】
次に、枝Ｔ１，１に属する端末局がパケットの再送を試み、端末局Ｎ6と端末局Ｎ7との送信するパケットが衝突する。そこで、階層を深くするが、枝Ｔ２，２に属する端末局が存在しないため空きスロットとなる。
次に、枝Ｔ２，１に属する各端末局がパケットの再送を試み、端末局Ｎ6と端末局Ｎ7の送信するパケットが衝突する。衝突したため更に階層を深くしてＴ３，０に属する端末局がパケットの再送を試み、端末局Ｎ6が成功する。最後に、枝Ｔ３，１に属する端末局Ｎ7が再送を試み、成功する。
次に、端末局数に基づき衝突回避制御期間を制御するアルゴリズムの一例を示す。基地局は、下記（６）式及び（７）式に示すアクセスの統計情報（空きスロットの割合Ｅ、成功スロットの割合Ｔなど）または端末局の認証サーバなどとの通信を介して、当該基地局に属する端末局数ｎを把握することは可能である。ここで、τは各端末局の送信確率を表す。
Ｅ＝（１−τ）ｎ                 …（６）
Ｔ＝ｎτ（１−τ）ｎ−１           …（７）
【００４２】
次に、図７に示すとおり、全端末局のバケット生起確率が同一であると仮定すると、全入力トラヒックが０．１から２．０の範囲内において最大のスループットが得られる最適な衝突回避制御期間は、端末局数にほぼ比例している。このグラフの傾きβは再送パケットのポリシー（最大再送回数や再送回数に応じた衝突回避制御期間の制御など）によって変わってくるが、予めシステムに応じた傾きβを算出し、当該基地局に属する端末局数ｎに基づき、以下の（８）式より衝突回避制御期間を求めることは可能である。
衝突ウィンドウ＝β×ｎ          …（８）
【００４３】
ここで、図７のグラフは、端末局装置の数ｎを横軸とし、全入力トラフィックが０．１から２．０までの平均スループットが最大となる衝突回避時間を縦軸にとっている。ここで、全入力トラフィックは、全端末基地局装置において、単位時間当たりにパケットが生成される情報量としている。すなわち、全入力トラフィック＝ｎ×λである。λは各端末局装置での同一のパケット生起確率を示す。ただし、伝送速度にて規格化している。
スループットは、単位時間当たりの実質的な情報伝送量とし、伝送速度にて規格化している。
【００４４】
また、図７のグラフを求めた条件は以下に示す通りである。
・伝搬：伝送エラーフリー、伝送遅延なし、基地局装置における端末局装置送信パケットの受信電力は同一。
・トラフィック：パケット生起確率及び生起トラフィック量は前端末局装置で同一。
・その他：基地局装置において、端末局装置からのアクセス状況（“成功”“衝突”、“空き”）を的確に把握できる。
【００４５】
次に、上述した衝突解決フェーズにおける一連の処理と、衝突回避制御期間を制御する処理との具体的な説明を、図８，図９，図１０を用いて以下に行う。図８及び図９は、各処理を時系列に示したシーケンス図であり、図１０は図８及び図９にて用いられている符号の説明である。
・はじめ、端末局装置Ｎ0，Ｎ2，Ｎ3，Ｎ5，Ｎ6，Ｎ7がパケットの送信待ち状態にあるとする。
・端末局装置Ｎ3の送信待機時間が「０」となったため、ランダムアクセス送信によるパケット送信を行い、送信が成功。
・次に、端末局装置Ｎ0，Ｎ2，Ｎ6，Ｎ7の送信待機時間がともに「０」となったため、それぞれがランダムアクセス通信を行い、パケットが衝突。
【００４６】
・基地局の基地局装置は、処理を衝突解決フェーズに切り替え、その情報を各端末局の端末局装置に報知。
・該当する端末局装置は衝突アルゴリズムに従い、衝突パケットを再送信する（上述した衝突解決フェーズの処理に記載）。
・上記衝突解決フェーズ中に、端末局装置Ｎ4が送信パケットを生成し、直近の衝突回避制御期間Ｗ3に基づき、送信待機時間を選択。
・衝突解決フェーズのため、端末局装置Ｎ4，Ｎ5はバックオフ・プロトコルを停止し、送信待機時間の減算やパケットの送信を行わない。
・その後、基地局装置は衝突が全て解決したと判断し、ランダムアクセスフェーズに処理を切り替え、その情報を各端末局装置に対して報知する。
・端末局装置Ｎ5は、送信待機時間が「０」となったため、パケットをランダムアクセス送信し、成功。
【００４７】
＜第２の実施形態＞
次に、図１１を参照して、第２の実施形態の説明を行う。図１１は、衝突解決のためのアルゴリズムとして、本実施形態ではツリーアルゴリズムを用い、ツリーアルゴリズムの動作フローを示す概念図である。
すでに説明した第１の実施形態における図６で示したツリーアルゴリズムでは、４個の端末局の衝突を解決するため、衝突解決フェーズが８スロット続いている。そのため、本衝突解決フェーズでのスループットは（４／８）＊１００＝５０％となる。
【００４８】
しかしながら、図６（ａ）及び図１１に示すように、枝Ｔ２，２には、衝突したパケットを送信した端末局が存在しない。このため、空きスロットを観測した場合、この枝Ｔ２，２に対して、枝Ｔ１，１における２分岐のもう一方である枝Ｔ２，３に属する端末局Ｎ6及び端末局Ｎ7に対して、パケットの再送を容認するのではなく、更に条件を絞り込んだ枝Ｔ３，６に属する端末局Ｎ6に対して再送を容認する。
こうすることにより、端末局Ｎ6と端末局Ｎ7との送信するパケットの二度目の衝突を回避し、衝突フェーズに要するスロット数を１スロット少なくすることができる。
そのため、本衝突解決フェーズでのスループットは（４／７）＊１００＝５７％と向上することとなる。
【００４９】
第３の実施形態を図１２，図１３及び図１４を参照して説明する。図１２，図１３及び図１４は、本実施形態の基地局と端末局との間のシーケンスチャートである。
第１の実施形態においては、端末局と基地局との間の伝送路が有線路などのように伝送路上の障害物や距離などによる減衰がほとんどない場合を想定して説明した。
しかしながら、基地局と端末局との間の伝送路が比較的長く、見通しが得られない無線路の場合、伝送路上の障害物や距離などによる減衰（フェージング）が著しい伝送路を想定する必要がある。
【００５０】
このため、送信パケットの受信結果を待っている端末局装置や衝突パケットの再送信タイミングを図っている端末局装置が、基地局装置から報知されるアクセス情報を受信できなかった場合、もしくは送信パケットの受信結果を待っている端末局装置が、基地局装置においてその送信の存在が検出されなかったと判断した場合に、送信待機時間を再設定してバックオフ・プロトコルで再度ランダムアクセスする方式が考えられる。
【００５１】
例えば、端末局からランダムアクセスの受信結果が含まれている基地局から端末局へのフィードバック信号が欠損した場合がある。
この場合、端末局においてランダムアクセスの成功または失敗の判断ができない。この場合には、衝突回避制御時間に基づき再度送信待機時間を設定して、ランダムアクセスする。
図１２には、端末局Ｎ1から送信された信号が基地局で正常に受信されたにも関わらず、基地局からのフィードバック信号が端末局Ｎ1において正常に受信されず、再度送信待機時間を設定して、送信待ち状態に遷移した状態を示している。
【００５２】
一方、端末局から基地局に対するランダムアクセス信号に関しても、例えその信号が衝突しなかった場合においても、同様にフェージングなどの影響で基地局における電界強度が低くなり、正常に受信できず、またその送信の存在さえも検出できない場合がある。
図１３には、端末局Ｎ3のみが基地局に対してランダムアクセスしたにも関わらず、基地局で正常に受信されず、また、その送信の存在さえ検出されず、端末局Ｎ3は再度送信待機時間を設定して、送信待ち状態に遷移した状態を示している。
または、基地局における各端末局が送信した信号が失われるということはなく、電界強度の強い信号が破壊されずに受信されることがある。
この場合、基地局においては電界強度の弱い信号は雑音として捉えるため、衝突の有無を検出することは難しい。そのため、送信の存在を基地局で検出されなかった場合、基地局は、衝突回避制御時間に基づき再度送信待機時間を設定して、ランダムアクセスする。
【００５３】
一方、図１４は、端末局Ｎ3と端末局Ｎ5とが基地局に対して同時にランダムアクセスし、端末局Ｎ5が送信した信号が基地局で正常に受信され、端末局Ｎ3の送信の存在が検出されていない状態を示す。
この場合、端末局Ｎ3は再度送信待機時間を設定して、送信待ち状態に遷移した状態を示している。
いずれの場合も、送信待機時間を設定せずにランダムアクセスすると、フィードバック信号の欠損による再ランダムアクセスの呼量が増してシステムの特性（スループット）が低下してしまう。
【００５４】
＜第４の実施形態＞
第４の実施形態を、図１５及び図１６を参照して説明する。図１５は、本実施形態の基地局と端末局との間の送信のシーケンスチャートである。図１６はツリーアルゴリズムの動作フローを示す概念図である。
第３の実施形態において示した通り、無線伝送路では、例え衝突がなかったとしてもフェージングなどによって信号の欠損が発生する。端末局からランダムアク セスの受信結果が含まれている基地局から端末局へのフィードバック信号が欠損した場合、端末局でランダムアクセスの成功または失敗が判断できない。このた め、端末局は衝突回遊制御時間に基づき再度送信待機時間を設定して、ランダムアクセスする必要がある。
そのため、基地局において正しくパケットの衝突を検出したとしても、その衝突パケットを送信した端末局が基地局からのアクセス状況の情報に基づいて衝突パケットの再送信タイミングを計っているとは限らない。
【００５５】
この図１５のシーケンスは、衝突に関わった複数の端末局がフィードバック信号の欠損のために、再度送信待機時間を設定している場合を示す。
枝Ｔ１，１に属する端末局（Ｎ4とＮ6）がパケットの再送を試み、端末局Ｎ4と端末局Ｎ6との送信したパケットが衝突する。
このランダムアクセスのフィードバック信号を、端末局Ｎ4が欠損したため、次の再送タイミング（枝Ｔ２，２に属する端末局に送信許可）にて送信を行なわない。
基地局は“空き”と判断して、第２の実施形態の方式に基づいて、２分岐のもう一方で更に階層が深い枝Ｔ３，６に属する端末局に再送を容認する。
【００５６】
このフィードバック信号を端末局Ｎ6が欠損したため、パケットの次の再送タイミングでも送信端末局が存在せず、基地局は“空き”と判断する。
そこで、基地局は第２の実施形態に基づき、図１６に示す２分岐のもう一方で更に階層が深い枝Ｔ４，１４に属する端末局にパケットの再送を容認すると、枝Ｔ３，７にはパケットの再送を控えている端末局が存在しないため、永久に第２の実施形態の方式に基づくツリー検索が行なわれてしまう。
このように、衝突に関与した複数の端末局が再度送信待機時間を設定した場合（基地局主導による再送から離脱した場合）、第３の実施形態だけでは、ツリーアルゴリズムから抜け出せなくなってしまう。
【００５７】
そこで、本実施形態においては、枝Ｔ３，６において“空き”を検出した場合、第２の実施形態の方式に示すもう一方の分岐において、更に条件を絞り込むことはせずに、枝Ｔ３，７に属する端末局に再送を容認する。
枝Ｔ３，７には再送する端末局が存在しないため、基地局は“空き”と判断して、ツリーアルゴリズムを終了することができる。
すわわち、第４の実施形態は、第３の実施形態において、基地局装置が、条件を絞り込んだもう一方の分岐において、再度端末局装置からパケットの送信がなされなかった（パケットの再送を行う端末局がない）場合に、もう一方の分岐に対して更に条件を絞り込むことは行なわない。
【００５８】
なお、図２のネットワークにおける端末局装置及び基地局装置の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによりパケットの送信処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境（あるいは表示環境）を備えたＷＷＷシステムも含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００５９】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【図面の簡単な説明】
【００６０】
【図１】本発明における衝突回避抑制期間とスループットとの関係を示すグラフである。
【図２】本発明における実施形態のネットワーク構成を説明する概念図である。
【図３】本発明の第１の実施形態における通信のフレーム構成を示す概念図である。
【図４】本発明の第１の実施形態における基地局のランダムアクセスロットの受信結果判定判定ロジックである。
【図５】本発明の基地局における動作フローを示すフローチャートである。
【図６】第１の実施形態における衝突解決のためのアルゴリズムで用いるツリーアルゴリズムを説明する概念図である。
【図７】端末数に伴うスループットが最大となる最適な衝突回避制御期間の変化を示すグラフである。
【図８】第１の実施形態の具体例を説明するためのシーケンス図である。
【図９】第１の実施形態の具体例を説明するためのシーケンス図である。
【図１０】本発明のシーケンス図で用いる符号を説明する図である。
【図１１】第２の実施形態における衝突解決のためのアルゴリズムとして用いるツリーアルゴリズムの動作フローを示す概念図である。
【図１２】第３の実施形態における衝突解決のためのアルゴリズムを説明するシーメンス図である。
【図１３】第３の実施形態における衝突解決のためのアルゴリズムを説明するシーメンス図である。
【図１４】第３の実施形態における衝突解決のためのアルゴリズムを説明するシーメンス図である。
【図１５】第４の実施形態における衝突解決のためのアルゴリズムを説明するシーメンス図である。
【図１６】第４の実施形態における衝突解決のためのアルゴリズムとして用いるツリーアルゴリズムの説明のための概念図である。
【符号の説明】
【００６１】
ＡＰ…基地局（基地局の基地局装置）
Ｎ0，Ｎ2，Ｎ3，Ｎ4，Ｎ5，Ｎ6，Ｎ7…端末局（端末局の端末局装置）
【図１】
0004549987.tif 000004
【図２】
0004549987.tif 000005
【図３】
0004549987.tif 000006
【図４】
0004549987.tif 000007
【図５】
0004549987.tif 000008
【図６】
0004549987.tif 000009
【図７】
0004549987.tif 000010
【図８】
0004549987.tif 000011
【図９】
0004549987.tif 000012
【図１０】
0004549987.tif 000013
【図１１】
0004549987.tif 000014
【図１２】
0004549987.tif 000015
【図１３】
0004549987.tif 000016
【図１４】
0004549987.tif 000017
【図１５】
0004549987.tif 000018
【図１６】
0004549987.tif 000019