(57)【特許請求の範囲】
【請求項１】
ポインタ情報をリンクすることで順番を決め、ある一定期間内に記憶部に登録された情報を優先順位に従った順序で並べ替えを行う方法であって、
優先順位の付与された所定個数の情報要素を検索対象として、ＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）を用いた部分一致検索を行って既登録であるか否か判定し、一致が認められた場合には、一致した位置に、検索対象となった検索パタンを追加する処理を行うステップと、
不一致の場合、検索対象の情報要素を所定個数に減少させ再度部分一致検索を行い、一致する場合、一致位置に対して、ポインタ挿入の位置を決定するステップと、
前記所定個数に減少しても再度不一致の場合、検索対象の情報要素の個数をさらに減少させて検索パタン情報との部分一致検索を逐次行っていくステップと、
決定されたポインタ挿入位置から順序情報を生成するステップと、
を含む、ことを特徴とする、部分一致検索を導入した並べ替え方法。
【請求項２】
請求項１記載の部分一致検索を導入した並べ替え方法を、ダイナミックＴＤＭＡ通信システムのフレーミング情報の生成、ローカルエリアネットワークのスイッチング集線装置、回線交換機のチャネル割り当ての、いずれかにおける、スケジューリングに用いたことを特徴とする、部分一致検索を導入した並べ替え方法。
【請求項３】
請求項１記載の部分一致検索を導入した並べ替え方法を、ダイナミックＴＤＭＡ通信システムの無線基地局における送受信順番管理に用い、一定期間内に登録された情報に付与される優先順位には、基地局送信クラスタ内セル番号、端末番号又は端末登録順位番号、送信信号種別（チャネル種別）、バーストの構成要素順のうちの少なくともいずれか一を用いる、ことを特徴とする、部分一致検索を導入した並べ替え方法。
【請求項４】
請求項１記載の部分一致検索を導入した並べ替え方法を、集配処理を所定時間で区切りながら到着コード番号順の処理を行う処理装置を含む、並び替え処理を行う装置における、並び替え処理に用いる、ことを特徴とする、部分一致検索を導入した並べ替え方法。
【請求項５】
請求項１記載の部分一致検索を導入した並べ替え方法を用いて、記憶部に登録されている情報と検索照合を行いながら、類似条件の処理要求が発生すると、前記条件ごとに、処理を分岐させる並行処理を行う、ことを特徴とする、部分一致検索を導入した並べ替え方法。
【請求項６】
（ａ）所定桁数（ｎ桁）の２進数値で優先順位を表現する場合、所定桁数の優先順位を検索対象として、検索パタン格納部から検索パタン情報を取り出し、ＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）を用いて部分一致検索を行った結果により、既登録であるか否か判定し、一致が認められた場合は、一致した位置に、検索対象となった検索パタンを追加する処理を行うステップと、
（ｂ）不一致の場合、検索対象を優先順位の上位所定桁を１桁減らして上位ｎ−１桁とし、前記上位ｎ−１桁に対して再度部分一致検索を行い、一致した場合、上位からｎ桁目の値が０の場合、一致位置の先頭に決定し、前記ｎ桁目の値が１の場合、検索対象として、１ずつ２進加算していった値で再検索を行い、一致すれば、ポインタ挿入位置を、一致位置の先頭に決定し、桁あふれまで加算しても一致しなければポインタ挿入位置を末尾に決定するステップと、
（ｃ）前記上位ｎ−１桁でも不一致の場合には、桁をさらに減少させ、検索対象として、前記ステップ（ｂ）と同様の操作を行うステップと、
（ｄ）最上位桁のみの検索で一致した場合、前記最上位桁の下位のビットが０ならばポインタ挿入位置を一致位置の先頭に決定し、１ならばポインタ挿入位置を末尾に決定し、最上位桁のみの検索で不一致の場合、最上位桁が０ならばポインタ挿入位置を先頭に、１ならばポインタ挿入位置を末尾に決定するステップと、
（ｅ）前記決定されたポインタ挿入位置に対して、ポインタをリンクで接続することで順序情報を生成するステップと、
を含む、ことを特徴とする部分一致検索を導入した並べ替え方法。
【請求項７】
ＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）を用いて部分一致検索を行う順序整理部を備え、
前記順序整理部が、所定期間内に記憶部に登録された情報に対して、優先順位が付与された所定個数の情報要素を検索対象として、検索パタン格納部に格納された検索パタン情報と、前記ＣＡＭを用いた部分一致検索を行った結果により、既登録であるか否か判定し、一致が認められた場合は、一致した位置に、検索対象となった検索パタンを追加する処理を行う手段と、
不一致の場合、検索対象の情報要素を所定個数に減少させて再度部分一致検索を行い、一致する場合、一致箇所に対してポインタ挿入位置を決定する手段と、
前記所定個数に減少しても再度不一致の場合、検索対象の情報要素の個数をさらに減少させて検索パタン情報との部分一致検索を逐次行っていく手段と、
決定されたポインタ挿入位置から順序情報を生成する手段と、
を含む、ことを特徴とする、部分一致検索を導入した並べ替え装置。
【請求項８】
通信チャネルごとの通信帯域要求に基づいて、動的にフレーム内の通信開始時刻や通信時間長を割り当てるダイナミックＴＤＭＡ（時分割多元アクセス）方式の無線通信システムにおいて、
無線端末局と無線通信する無線基地局のスケジューリング部が、フレーム内の時系列上への配置を受け持つフレーミング情報生成部と、処理要求部とを備え、
前記フレーミング情報生成部は、有線インタフェース部や無線インタフェース部からの通信帯域要求をまとめた前記処理要求部からの情報を基に、時系列上に配置した結果をフレーミング情報として、フレーミング部に受け渡し、
前記無線基地局の前記フレーミング情報生成部が、フレームごとに、優先順位にしたがって並べ替えを行い、時系列上の配置を行う順序整理部として、請求項７記載の部分一致検索を導入した並べ替え装置を備えた、ことを特徴とする、無線通信システム。
【請求項９】
請求項８記載の無線通信システムにおいて、前記順序整理部が、前記優先順位として、基地局送信クラスタ内セル番号、端末番号又は端末登録順位番号、送信信号種別（チャネル種別）、バーストの構成要素順のうちの少なくともいずれか一を用いる、ことを特徴とする無線通信システム。
【請求項１０】
ＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）を用いた部分一致検索を行い、情報を優先順位に従って並べ替える処理として、
（ａ）ある一定期間内に記憶部に登録された情報に対して、優先順位が付与された所定個数の情報要素を検索対象として、検索パタン格納部に格納された検索パタン情報と、前記ＣＡＭを用いた部分一致検索を行った結果により、既登録であるか否か判定し、一致が認められた場合は、一致した位置に、検索対象となった検索パタンを追加する処理を行う処理と、
（ｂ）不一致の場合、検索対象の情報要素を所定個数に減少させて再度部分一致検索を行い、一致する場合、該当する所定個数の情報要素の先頭に決定する処理と、
（ｃ）前記所定個数に減少しても再度不一致の場合、検索対象の情報要素の個数をさらに減少させて検索パタン情報との部分一致検索を逐次行っていく処理と、
（ｄ）決定された位置の順序情報を生成する手段と、
の前記（ａ）乃至（ｄ）の各処理をコンピュータに実行させるためのプログラムを記録した記録媒体。
【請求項１１】
ＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）を用いた部分一致検索を行い、情報を優先順位に従って並べ替える処理として、
（ａ）所定桁数（ｎ桁）の２進数値で優先順位を表現する場合、所定桁数の優先順位を検索対象として、検索パタン格納部から検索パタン情報を取り出し、前記ＣＡＭを用いて部分一致検索を行った結果により、既登録であるか否か判定し、一致が認められた場合は、該当する位置に追加を行う処理と、
（ｂ）不一致の場合、検索対象を優先順位の上位所定桁を１桁減らして上位ｎ−１桁とし、前記上位ｎ−１桁に対して再度部分一致検索を行い、一致した場合、上位からｎ桁目の値が０の場合、一致位置の先頭に決定し、前記ｎ桁目の値が１の場合、検索対象として、１ずつ２進加算していった値で再検索を行い、一致すれば、ポインタ挿入位置を、一致位置の先頭に決定し、桁あふれまで加算しても一致しなければポインタ挿入位置を末尾に決定する処理と、
（ｃ）前記上位ｎ−１桁でも不一致の場合には、桁をさらに減少させ、検索対象として、前記（ｂ）と同様の操作を行う処理と、
（ｄ）最上位桁のみの検索で一致した場合、前記最上位桁の下位のビットが０ならばポインタ挿入位置を一致位置の先頭に決定し、１ならばポインタ挿入位置を末尾に決定し、最上位桁のみの検索で不一致の場合、最上位桁が０ならばポインタ挿入位置を先頭に、１ならばポインタ挿入位置を末尾に決定する処理と、
（ｅ）前記決定されたポインタ挿入位置に対して、ポインタをリンクで接続することで順序情報を生成する処理と、
を含み、前記（ａ）乃至（ｅ）の各処理をコンピュータに実行させるためのプログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データの並び替え技術に関し、特に、部分一致検索を用いた並び替え方法及び装置並びに記録媒体に関する。
【０００２】
【従来の技術】
従来のデータ並べ替え（ソート）手法として、すべてのデータを準備した上で、公知のクイックソート法などを用いて一括並べ替えを行う方法が用いられる。
【０００３】
無線通信システムの分野において、ダイナミック時分割多重アクセス（ＴＤＭＡ）方式でのスケジューリングは、フレーム毎に、通信チャネルの配置が異なり、通信チャネル毎に要求される通信帯域も異なる。
【０００４】
そのため、特定の用途で固定的に割り当てられる通信チャネルや、固定的に通信帯域が割り当てられる通信チャネルを除いて、同じ通信チャネルにおいても、毎フレームごとに、時系列上の時間位置や時間長が異なる。
【０００５】
【発明が解決しようとする課題】
ところで、無線通信システムにおいて、数ミリ秒などの短期間のフレームの間に、フレーム内の送受信順等の並べ替えや時系列上への配置を完了するには、処理時間の短縮などを図るための技術の開発が、重要な課題となっている。
【０００６】
したがって、本発明は上記課題を認識した本願発明者が鋭意研究した結果創案されたものであって、その主たる目的は、処理を分散して並べ替えを行うとともに、高速化を図る、並べ替え方法及び装置並びに記録媒体を提供することにある。
【０００７】
【課題を解決するための手段】
前記目的を達成する本発明は、ある一定期間内に登録された情報に対して、順序に関する優先順位を付与し、部分一致検索に基づき、前記優先順位に従った順序で並べ替えを行い、一定期間の終了時に、その順序情報を出力する、ことを特徴とする。
【０００８】
本発明は、所定期間内に登録された情報に順序に関する優先順位を付与する手段と、前記情報に対して、部分一致検索により、前記優先順位に従った順序で並べ替えを行う部分一致検索手段と、並べ替えられた順序情報を出力する手段と、を備える。
【０００９】
【発明の実施の形態】
本発明の実施の形態について説明する。本発明は、部分一致検索を採用して、ある一定期間内の処理要求を、順次受け付け、優先順位（順序情報）に従って並べ替えを行うものである。従来より用いられている並べ替え方法と比較した場合、
・部分一致検索を採り入れることにより、順次検索よりも、最大検索処理時間の短縮を図ることができる、
・並べ替えを、一括処理せずに、処理を分散させることができる、
等の利点を有している。
【００１０】
本発明においては、最大検索処理時間の短縮は、ポインタを用いた順序情報管理を想定し、このポインタの順次検索を使用した並べ替え手法と比較して、部分一致検索を導入した並べ替えでの検索回数は、より少ない回数で完了できる。
【００１１】
また、本発明においては、処理の分散化は、ある一定期間内において、発生した処理要求に応じた個別処理が並行して求められ、同時に並べ替え処理を必要とするような形態を、適用対象としている。
【００１２】
この場合、処理要求ごとに、既登録の処理要求との照合が必要な場合に、並べ替えの一括処理の適用が難しく、要求を順次受け付けることにより、処理を、分散させるものである。
【００１３】
本発明は、ある一定期間内に登録された情報に対して、優先順位（順序情報）を付与し、部分一致検索手法を導入して、その優先順位に従った順序で並べ替え（ソーティング）を行い、一定期間の終了時に、その順序情報を出力させる手段を提供するものである。
【００１４】
本発明の適用対象の一例をあげれば、無線ＬＡＮ基地局における送受信順番管理などに用いることができる。すなわち、通信チャネルごとの通信帯域要求に基づいて、動的にフレーム内の通信開始時刻や通信時間長を割り当てるダイナミックＴＤＭＡ（時分割多元アクセス）方式の無線通信システムにおいて、無線端末局と無線通信する無線基地局のスケジューリング部が、フレーム内の時系列上への配置を受け持つフレーミング情報生成部と、処理要求部とを備え、前記フレーミング情報生成部は、有線インタフェース部や無線インタフェース部からの通信帯域要求をまとめた前記処理要求部からの情報を基に、時系列上に配置した結果をフレーミング情報として、フレーミング部に受け渡し、前記無線基地局の前記フレーミング情報生成部が、部分一致検索を導入した並べ替え方法を用いて、フレームごとに、優先順位にしたがって並べ替えを行う順序整理部を備えている。
【００１５】
この場合、一定期間内に登録された情報に付与される優先順位には、基地局送信クラスタ内セル番号、端末番号あるいは端末登録順位番号、送信信号種別（チャネル種別）、バーストの構成要素順等を用いることができる。
【００１６】
しかしながら、本発明は、上記用途に限定されるものではなく、順位情報に従って並べ替えを行う場合の一般的な用途に適用が可能である。
【００１７】
本発明は、部分一致検索を導入することにより、過去に登録されている情報と照合を行いながら、類似条件の処理要求が発生すると、その条件ごとに、処理を分岐させるような並行処理を行う場合に、特に有効とされる。
【００１８】
本発明の方法は、その一実施の形態として、ＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）を用いた部分一致検索を行い、情報を優先順位に従って並べ替える処理（順序整理処理）として、
（ａ）所定桁数（ｎ桁）の２進数値で優先順位を表現する場合、所定桁数の優先順位を検索対象として、検索パタン格納部から検索パタン情報から取り出し、前記ＣＡＭを用いて部分一致検索を行った結果により、既登録であるか否か判定し、一致が認められた場合は、該当する位置に追加を行うステップと、
（ｂ）不一致の場合、検索対象を優先順位の上位所定桁を１桁減らして上位ｎ−１桁とし、前記上位ｎ−１桁に対して再度部分一致検索を行い、一致した場合、上位からｎ桁目の値が０の場合、一致位置の先頭に決定し、前記ｎ桁目の値が１の場合、検索対象として、１ずつ２進加算していった値で再検索を行い、一致すれば、ポインタ挿入位置を、一致位置の先頭に決定し、桁あふれまで加算しても一致しなければポインタ挿入位置を末尾に決定するステップと、
（ｃ）前記上位ｎ−１桁でも不一致の場合には、桁をさらに減少させ、検索対象として、前記ステップ（ｂ）と同様の操作を行うステップと、
（ｄ）最上位桁のみの検索で一致した場合、前記最上位桁の下位のビットが０ならばポインタ挿入位置を一致位置の先頭に決定し、１ならばポインタ挿入位置を末尾に決定し、最上位桁のみの検索で不一致の場合、最上位桁が０ならばポインタ挿入位置を先頭に、１ならばポインタ挿入位置を末尾に決定するステップと、
（ｅ）前記決定されたポインタ挿入位置に対して、ポインタをリンクで接続することで順序情報を生成するステップと、
を含む。上記（ａ）乃至（ｅ）の各ステップの処理は、コンピュータ上でプログラムを実行することで実現するようにしてもよい。
【００１９】
【実施例】
本発明の実施例について図面を参照して以下に説明する。以下では、図１に示すような無線通信システムに本発明を適用した実施例を説明する。この実施例は、無線通信システムの無線基地局１の送受信時分割スケジューリング機能を実現するスケジューリング部１２に、本発明を適用したものである。
【００２０】
この実施例における無線通信システムは、ネットワーク側と無線側との仲介を行う無線基地局１と、無線側と携帯端末（ノート型ＰＣ、専用端末等）の仲介を行う無線端末局２と、を備えて構成される。
【００２１】
無線基地局１は、主な構成要素として、有線側、無線側からの通信帯域要求を把握し、通信内容に応じた優先順位に基づき時系列上に送受信順を並べ込んでいくスケジューリング部１２と、スケジューリング部１２でのスケジューリング結果を実時間に配置するフレーミング部１４と、モデムや高周波部等を含む無線インタフェース部１５と、ネットワークとの接続を可能にするための有線インタフェース部１３と、を備えている。
【００２２】
無線端末局２は、主な構成要素として、無線を通じて行われる基地局からの指示でフレーミング情報を再生するスケジューリング部２２と、携帯端末とのインタフェースとなるアプリケーションインタフェース部２５と、フレーミング部２４と、無線インタフェース部２３と、を備えている。
【００２３】
この実施例において、無線通信は、時分割多重アクセス（ＴＤＭＡ）方式による通信であり、「フレーム」と呼ぶ、ある一定期間の繰り返し周期の中で送受信の時刻を通信チャネル毎に指定して実施するものであり、ここでは、特に、その通信チャネルごとの通信帯域要求に基づいて、動的にフレーム内の通信開始時刻や通信時間長を割り当てるダイナミックＴＤＭＡ通信方式への適用を想定している。
【００２４】
無線基地局１のスケジューリング部１２は、フレーム内の時系列上への配置を受け持つフレーミング情報生成部１０と、処理要求部１１とを備えている。すなわち、無線基地局１のスケジューリング部１２は、有線インタフェース部１３や無線インタフェース部１５からの通信帯域要求などをまとめた処理要求部１１からの情報を基に、後述する順序整理部１００（図２参照）で、時系列上に配置した結果をフレーミング情報として、フレーミング部１４に受け渡す役割を受け持つ。
【００２５】
また、無線端末局２のスケジューリング部２２は、無線基地局１から無線インタフェース部２３を通して得られた配置情報と、アプリケーションインタフェース部２５からの通信帯域要求をまとめた処理要求部２１からの情報を基に、フレーミング情報を再生・加工し、フレーミング部２４に受け渡す役割を受け持つ。
【００２６】
図２は、本発明の一実施例におけるフレーミング情報生成部１０の構成の一例を示す図である。処理要求部１１からの処理要求を受け付ける処理要求受付部１０１と、処理要求部１１からの時刻情報設定を受け付ける処理時刻管理部１０２と、処理要求受付部１０１からの検索・順序整理指示を受け、検索パタン格納部１０４の検索パタン情報を参照して順序整理を行う順序整理部１００と、順序整理部１００からのポインタ追加を入力し、ポインタ情報を、順序整理部１００に返却する順序情報記憶部１０５と、統計情報管理部１０６と、順序情報記憶部１０５からの順序情報をうけとりフレーミング部１４に出力する順序情報出力部１０３と、を備え、必要に応じて、処理要求部１１との間で詳細情報を受け渡す詳細情報記憶部１０７を備えて構成される。
【００２７】
処理要求部１１からの処理要求を処理要求受付部１０１で受け付けてバッファリングする。処理要求受付部１０１は、受け付けた情報に基づいて、順序整理部１００に対して、検索指示、順序整理指示を行う。
【００２８】
順序整理部１００は、検索パタン格納部１０４の検索パタン情報や処理時刻管理部１０２からの情報を基に、情報の並べ替え処理を行い、その結果を、順序情報記憶部１０５に記憶させ、統計情報管理部１０６に統計情報を出力する。
【００２９】
そして、順序情報記憶部１０５に記憶された順序情報は、順序情報出力部１０３に受け渡され、フレーム毎など出力指示が発生した時点で、フレーミング部１４に出力する。
【００３０】
図３は、本発明の一実施例における順序整理部１００の構成を示す図である。なお、図４には、比較例として、従来の方式よる順序整理部２００の構成の一例を示す。
【００３１】
図３を参照すると、順序整理部１００は、部分一致検索部１１０と、ポインタ生成部１１２と、ＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ：コンデンツ・アドレッサブル・メモリ）１１１を備えている。
【００３２】
一方、図４を参照すると、従来の順序整理部２００は、順次検索部２０１と、ポインタ生成部２０２とを備えている。
【００３３】
図３と図４の構成を比較した場合、従来方式の順序整理部２００では、順序検索を行う順次検索部２０１を備えているのに対し、本発明の一実施例においては、順序整理部１００が、部分一致検索に適したＣＡＭ１１１などで構成する部分一致検索部１１０を備えている。
【００３４】
本発明の一実施例についてさらに詳細に説明する。ダイナミックＴＤＭＡを採用した通信システムでは、無線基地局がチャネル毎に時々刻々と変化する通信帯域を有線側、無線側から要求として受け付け、その要求に応じたチャネルの配置を行う。
【００３５】
その際、送受信データは時分割されたバーストに載せられるため、各チャネルの中でもバーストの構成要素が時系列上に配置される必要がある。
【００３６】
また、無線基地局からの通信を、アンテナの構成法により、複数のサービスエリアに分割するためのセクタアンテナから、時分割で別々に送受信させるためにも、時系列上に、配置される必要がある。
【００３７】
そこで、これらの時系列上への配置順を、優先順位情報として、２進数コード化し、フレーム毎に、そのコード順に従って並べ替えて、時系列上への配置を行うために、スケジューリング部内に順序整理部１００を配置する。
【００３８】
この順序整理部１００に部分一致検索部１１０を配置する。
【００３９】
部分一致検索部１１０は、あるパタン列を格納されているメモリアドレスを逆引きできる機能を持つＣＡＭ１１１を使用すると比較的容易に機能を実現することが可能である。ＣＡＭ１１１の使用により、登録数が増大した場合についても比較的少ないアクセス回数で、フレーム内のチャネル配置状況が検索できる。
【００４０】
また、その検索結果に基づいて、すでに配置済みのチャネルであるため、データチャネルだけを追加配置したり、未配置のチャネルであるため、制御用チャネルやバースト識別用領域を追加配置したりするなどの処理を選択することが可能である。この追加配置処理が、実際の並べ替え処理と並行される処理の例である。
【００４１】
また、無線基地局において、時系列上への配置結果を、順序情報として、フレーミング部１４などへ渡すため、この順序情報を構築するためにポインタの概念を導入し、配置構成要素を、ポインタで照合可能とした状態で記憶する順序情報記憶部１０５と、その順序情報をフレーム毎に出力される順序情報出力部１０３により、並べ替えた結果である順序情報が、フレーミング部１４などへ出力される。
【００４２】
本発明の一実施例における部分一致検索の動作の一例を、図５を参照して説明する。
【００４３】
図５（ａ）は、４桁の２進数値で優先順位を表現する場合の例である。
【００４４】
まず、順序整理部１００では、処理要求された優先順位４桁（２進値「ＡＢＣＤ」）を検索対象として、検索パタン格納部１０４から取り出し、ＣＡＭ（図３の１１１）等を用いて部分一致検索を行った結果により、既登録であるか否か判定し、一致が認められた場合は、「ＡＢＣＤ」の位置に追加の処理を行う。
【００４５】
ここで、不一致だった場合、検索対象を、優先順位の上位３桁（ＡＢＣ）にして再度部分一致検索を行い、「Ｄ＝０」の場合は、「ＡＢＣ＊」（ただし、「＊」は、ワイルドカード）の先頭位置に決定する。
【００４６】
「Ｄ＝１」の場合は、検索対象として、「ａｂｃ」（「ＡＢＣ」に１ずつ加算していったもの）での再検索を行い、一致すれば、その先頭位置に決定し、桁あふれまで加算しても一致しなければ末尾に決定する。
【００４７】
「ＡＢＣ」でも不一致の場合は、桁をさらに減少させ、「ＡＢ」を検索対象として同様の操作を行う。
【００４８】
「Ｃ＝０」の場合は、「ＡＢ＊＊」の先頭位置に決定する。
【００４９】
「Ｃ＝１」の場合は、検索対象として、「ａｂ」（「ＡＢ」に１ずつ加算していったもの）での再検索を行い、一致すれば、「ａｂ００」の先頭位置に決定し、桁あふれまで加算しても一致しなければ、末尾に決定する。
【００５０】
このようにして、最上位桁「Ａ」のみの検索で一致した場合、「Ｂ＝０」ならば一致位置の先頭に決定し、「Ｂ＝１」ならば末尾位置に決定する。不一致であった場合、「Ａ＝０」ならば先頭位置、「Ａ＝１」ならば、末尾位置に決定する。
【００５１】
このように決定された位置に対して、リンクチェーン型のポインタ構造を構築することにより、順序情報を生成する。
【００５２】
図５（ｂ）は、図５（ａ）と基本的には類似した処理であるが、部分一致検索で末尾位置も検出可能な場合に用いる例を示したものである。
【００５３】
例えば上位３桁（「ＡＢＣ」）、上位２桁（「ＡＢ」）が検索対象である場合、４桁目（「Ｄ」）、３桁目（「Ｃ」）が「０」であれば一致位置の先頭、「１」であれば、一致位置の末尾に配置することで、ポインタ位置の決定が可能である。
【００５４】
図６、図７は、本発明における部分一致検索のフローチャートを示し、図５に示した例を、優先順位ｎ桁（２進数）で一般化したものである。基本的な動作は上述と同様である。
【００５５】
全ｎ桁分の比較で一致するか判定し（ステップＳ１）、一致した場合（ステップＳ１のＹＥＳ）、Ｌに一致位置、Ｐに要求処理を追加とし、挿入位置Ｌに対して処理Ｐを実行する（ステップＳ２）。
【００５６】
全ｎ桁分の比較で一致しない場合（ステップＳ１のＮＯ）、上位ｎ−１桁分の比較で一致した場合（ステップＳ４のＹＥＳ）、上位からｎ桁目が「０」の場合（ステップＳ８のＹＥＳ）、Ｌに上位ｎ−１桁分の一致位置の先頭、Ｐにポインタ挿入とし（ステップＳ９）、ターミナル１に移行する。上位からｎ桁目が「０」でない場合（ステップＳ８のＮＯ）、ステップＳ１１からＳ１３の処理を、ｍ＝１〜２(m-1)−１を行う。
【００５７】
比較元の上位ｎ−１桁に対してｍを加算し（ステップＳ１１）、加算値が桁あふれをしている場合（ステップＳ１１ＡのＹＥＳ）、Ｌを末尾に、Ｐをポインタ挿入とし（ステップＳ１２）、ターミナル１に移行する。
【００５８】
上位ｎ−１桁分の比較で一致した場合（ステップＳ１３のＹＥＳ）、Ｌに一致位置、Ｐをポインタ挿入とし（ステップＳ１４）、ターミナル１に移行する。
【００５９】
ループを抜け出した場合、Ｌを末尾に、Ｐをポインタ挿入とし（ステップＳ１５）、ターミナル１に移行する。
【００６０】
上位ｎ−２桁分の比較で一致した場合（ステップＳ５のＹＥＳ）、ターミナル３へ、上位２桁分の比較で一致した場合（ステップＳ６のＹＥＳ）、ターミナル４へ、上位１桁分の比較で一致した場合（ステップＳ７のＹＥＳ）、ターミナル５へ、それ以外はターミナル６へ移行する。
【００６１】
ターミナル３においては、上位からｎ−１桁目が０の場合（ステップＳ１７のＹＥＳ）、Ｌに上位ｎ−２桁分の一致位置の先頭、Ｐにポインタ挿入とし（ステップＳ１８）、ターミナル１に移行する。上位からｎ−１桁目が０でない場合（ステップＳ１７のＮＯ）、ステップＳ２０からステップＳ２３の処理を、ｍ＝１〜２(m-2)−１繰り返す、比較元の上位ｎ−２桁に対してｍを加算し（ステップＳ２０）、加算値が桁あふれをしている場合（ステップＳ２１のＹＥＳ）、Ｌを末尾に、Ｐをポインタ挿入とし（ステップＳ２２）、ターミナル１に移行する。上位ｎ−２桁分の比較で一致した場合（ステップＳ２３のＹＥＳ）、Ｌに一致位置、Ｐをポインタ挿入とし（ステップＳ２４）、ターミナル１に移行する。ループを抜け出したあと、Ｌを末尾に、Ｐをポインタ挿入とし（ステップＳ２６）、ターミナル１に移行する。
【００６２】
ターミナル４においては、上位３桁分の比較で一致した場合、上位から３桁目が０の場合（ステップＳ２７のＹＥＳ）、Ｌに上位２桁分の一致位置の先頭、Ｐにポインタ挿入とし（ステップＳ２８）、ターミナル１に移行する。上位から３桁目が０でない場合、ステップＳ３０〜Ｓ３３の処理をｍ＝１〜２2−１繰り返す、比較元の上位ｎ−２桁に対してｍを加算し（ステップＳ３０）、加算値が桁あふれをしている場合（ステップＳ３２のＹＥＳ）、Ｌを末尾に、Ｐをポインタ挿入とし（ステップＳ３２）、ターミナル１に移行する。上位２桁分の比較で一致した場合（ステップＳ３３のＹＥＳ）、Ｌに一致位置、Ｐをポインタ挿入とし（ステップＳ３４）、ターミナル１に移行する。ループを抜け出したあと、Ｌを末尾に、Ｐをポインタ挿入とし（ステップＳ３７）、ターミナル１に移行する。
【００６３】
ターミナル５においては、上位から２桁目が０の場合（ステップＳ３８のＹＥＳ）、Ｌに上位１桁分の一致位置の先頭、Ｐにポインタ挿入とし（ステップＳ３９）、ターミナル１に移行し、上位から２桁目が０でない場合（ステップＳ３８のＮＯ）、Ｌを末尾に、Ｐをポインタ挿入とし（ステップＳ４０）、ターミナル１に移行する。
【００６４】
ターミナル６においては、上位から１桁目が０の場合（ステップＳ４１のＹＥＳ）、Ｌに先頭、Ｐにポインタ挿入とし（ステップＳ４２）、ターミナル１に移行し、上位から１桁目が０でない場合（ステップＳ４１のＮＯ）、Ｌを末尾に、Ｐをポインタ挿入とし（ステップＳ４３）、ターミナル１に移行する。
【００６５】
そして上記各ステップで挿入位置が決定されてポインタをリンクすることで順序情報が構成される。
【００６６】
図５、図６及び図７に処理を例示した順序整理部１００の部分一致検索処理は、コンピュータ上で実行されるプログラムにより実現される。この場合、該プログラムを記録した記録媒体（フロッピーディスク、ハードディスク、磁気テープ、ＣＤ−ＲＯＭ、ＤＶＤ、あるいは半導体メモリ等）から、該プログラムを、読み出し装置から、コンピュータに読み出して実行することで、本発明を実施することができる。
【００６７】
本発明の実施例の作用効果について説明する。まず、処理時間の分散について、例えば、検索をかけながら、実時間上での集計を行うなど、処理の途中の状況が必要となるような場合で、他の処理を同時進行させる場合に、本発明が有効となる。とくに、前記した実施例においては、各端末毎、各通信チャネル毎に変調速度等のパラメータが異なる例を取り扱うため、これらや、さらに他の単位で時系列上の配置に必要な実時間の集計が必須となる。
【００６８】
すなわち、この集計値が、通信チャネルの配置を許可するかどうかの判定材料となるという点が重要である。
【００６９】
また、
・すでに配置された通信チャネルへの追加かどうか、
・始めて配置される端末向けの通信チャネルかどうか、
・配置済みのクラスタ内セル向けあるいはセクタ向けに配置される通信チャネルかどうか、
などの把握は、検索しながら得ていく情報で行う必要があるため、一括並べ替えでは実現が難しい場合がある。
【００７０】
なお、上記したクラスタとは、ある１つのアンテナによるサービスエリアであるセルを複数集合したものを指し、同一のフレームをクラスタ内の各セルで共有し合う特徴を持つものである。
【００７１】
次に、検索処理時間の短縮について、順番を、ポインタ情報で接続し合うようなデータで表現しながら、先に述べた実施例の並べ替えを実現する際に、従来の手法では、順序情報をコード化した優先順位に基づく順次検索を行って並べ替えを行っている。この場合、最大の処理時間は、登録数に対して、級数的に増加する。
【００７２】
これに対して、前記実施例では、部分一致検索に適する電子デバイスであるＣＡＭなどを導入することにより、既登録かどうかの判定材料とすることができる。この場合の最大の処理時間は、登録数に対して比例に近い処理時間となり、順次検索を用いる場合と比較すると処理時間の短縮効果が現れてくる。
【００７３】
検索処理時間の短縮効果の一例を掲げるために、順次検索を用いる場合と、本発明を用いる場合とで、２進数で優先順位８桁（登録件数は１２８件とする）、１０桁（登録件数は１０２４件とする）の例を検討した。
【００７４】
このとき、各優先順位に対して１件ずつを登録していき、１回の検索判定を１アクセスと数え、最大処理アクセス数を比較すると、
従来の順次検索の場合は、
・優先順位８桁、１２８件で８２５６アクセス、
・優先順位１０２４件で５２４８００アクセス
であるのに対し、本発明を適用した場合、
・優先順位１２８件で２２０８アクセス（約７３．３％減）、
・優先順位１０２４件で１３２３５２アクセス（約７４．８％減）
となる。
【００７５】
このように、処理時間の大部分を占めるアクセス回数で比較すると大幅な短縮効果が生じる。分岐処理、及びＣＡＭ等へのアクセス増など、従来の順次検索と、本発明の検索とでは、処理内容自体が変更されるため、単純な比較はできないものの、アクセス回数を特段に低減していることはたしかである。
【００７６】
本発明によれば、検索処理短縮効果が期待でき、並べ替え時に他の処理と組み合わせる必要があるシステムなどにとくに有効となる。
【００７７】
本発明は、並べ替え処理を行う過程の情報も使用しながら順次並べ替えを行うものであり、無線に限らずに、他のダイナミックＴＤＭＡ通信システムのスケジューリング部にも、適用が可能である。イーサネット等のＬＡＮ（ローカルエリアネットワーク）のスイッチングＨＵＢや、動的なチャネル割り当てを回線交換機により実現するような場合にも、本発明を適用することができる。
【００７８】
本発明は、通信分野に限らず、並べ替え処理を必要とする装置一般に適用が可能である。例えば、ある時間で区切りながら集荷分配の管理などで到着コード番号順の処理を行うような処理装置への応用も可能である。この中で、集荷場の到着先別の仕分け機に本発明を適用することで、到着コードの区切りを動的に扱うことなどが可能となり、仕分け機の構成の仕方によっては、集荷場内空間の有効利用を図ることが可能となる。
【００７９】
【発明の効果】
以上説明したように、本発明によれば、一定期間内に登録された情報に対して、順序に関する優先順位を付与し、部分一致検索に基づき、前記優先順位に従った順序で並べ替えを行い、一定期間の終了時に、その順序情報を出力する構成としたことにより、処理時間の分散、及び、検索処理時間の短縮を達成することができ、並べ替え時に、他の処理と組み合わせる必要があるシステムに適用した場合に特に有効である。
【図面の簡単な説明】
【図１】本発明の一実施例の通信システムを示す図である。
【図２】本発明の一実施例のシステム構成を示す図である。
【図３】本発明の一実施例の順序整理部の構成を示す図である。
【図４】従来の順序整理部の構成を示す図である。
【図５】本発明の一実施例の部分一致検索の例を示す説明図である。
【図６】本発明の一実施例の部分一致検索の例を示す説明図である。
【図７】本発明の一実施例の並べ替えによるポインタ挿入位置の決定方法の例を示す流れ図である。
【符号の説明】
１  無線基地局
２  無線端末局
１０  フレーミング情報生成部
１１  処理要求部
１２  スケジューリング部
１３  有線インタフェース部
１４  フレーミング部
１５  無線インタフェース部
２０  フレーミング情報生成部
２１  処理要求部
２２  スケジューリング部
２３  無線インタフェース部
２４  フレーミング部
２５  アプリケーションインタフェース部
１００、２００  順序整理部
１０１  処理要求受付部
１０２  処理時刻管理部
１０３  順序情報出力部
１０４  検索パタン格納部
１０５  順序情報記憶部
１０６  統計情報管理部
１１０  部分一致検索部
１１１  ＣＡＭ
１１２  ポインタ生成部
２０１  順次検索部
２０２  ポインタ生成部
【図１】
0003641998.tif 000002
【図２】
0003641998.tif 000003
【図３】
0003641998.tif 000004
【図４】
0003641998.tif 000005
【図５】
0003641998.tif 000006
【図６】
0003641998.tif 000007
【図７】
0003641998.tif 000008