(57)【要約】【課題】複数個のサブチャネルを含むチャネルを使用して装置間でフレームをやりとりする通信システムにて、チャネルアクセス遅延、チャネル利用率、各通信装置によるサブチャネル獲得確率等の問題を解決乃至緩和する。【解決手段】システムに参加する個々の装置にて、複数個のサブチャネルを含むフレームを使用して随時フレームをやりとりする（９１０）。その際、各装置は、自装置へのデータ流入から自装置によるデータ送出までの待ち時間指標たるスイッチングラテンシ、予約可能サブチャネル群における隣接サブチャネル間短手距離、又はその双方に基づき、予約候補サブチャネルを選択し（９１２）、選択済サブチャネルの中から選択済サブチャネル数を限度にフレーム毎に且つ動的にサブチャネルを予約する（９１４）。【選択図】図９
2008160846.tif 000002
【特許請求の範囲】
【請求項１】
複数個のサブチャネルを含むチャネルを使用し複数の装置間で随時フレームをやりとりする通信システムであって、
各装置が、
予約可能サブチャネル群の中からその隣接サブチャネル間短手距離に基づき予約候補サブチャネルを選択し、
選択済サブチャネルの中から選択済サブチャネル数を限度にフレーム毎に且つ動的にサブチャネルを予約する通信システム。
【請求項２】
請求項１記載の通信システムであって、予約候補サブチャネルとして、予約可能サブチャネル群の中で隣接サブチャネル間短手距離の分散がより小さくなる複数個を選択する通信システム。
【請求項３】
請求項１記載の通信システムであって、サブチャネルの選択に際して、従前の帯域幅条件に基づき各チャネルにおける予約可能サブチャネル数を制限するグリーディ法を併用する通信システム。
【請求項４】
請求項１記載の通信システムであって、サブチャネルを予約するとき予約済サブチャネルのうち何れか又は全てを解放する通信システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はネットワークにおけるチャネルアクセス技術に関し、より詳細には動的チャネルアクセスプロトコルと併用しうるスケジューリング法に関する。
【背景技術】
【０００２】
ネットワーク技術の進歩により、昨今では、例えばモバイルスマートホン（個人情報端末化された携帯電話）向けアプリケーションやＶｏＷＩＰ(Voice over Wireless Internet Protocol)準拠のアプリケーション等、複数種類の音声関連アプリケーションを個々のネットワークでサポートできるようになっている。近い将来、これらのアプリケーションは、レガシーなＤＣＡ(Data Centric Application)が搭載された移動端末上で同時実行されることとなろう。その結果生じる音声／データ混在トラフィックを個々のネットワークでサポートするには、それらのアプリケーションにて使用するチャネルアクセスプロトコル例えばＭＡＣ(Media Access Control)プロトコルによって、高水準のチャネル利用率を実現しつつチャネルアクセス遅延を抑えねばならない。チャネル利用率を高めることはＤＣＡを実行する上で重要なことであり、チャネルアクセス遅延を抑えることは、音声関連その他のリアルタイムアプリケーションを実行して通信を行う際にデータが円滑に授受されるようにする上で必須のことである。
【０００３】
マルチホップアドホックネットワーク用やワイヤレスＬＡＮ(Local Area Network)用のチャネルアクセス方式としては既にコンテンションベース（競合主義）のチャネルアクセス方式が開発されているが、それらの方式では、ネットワーク負荷が高まっているときにチャネル利用率を高水準に保つことができない。更に、既存のコンテンションベースチャネルアクセス方式をアドホックネットワークで使用すると衝突が起きやすく、衝突が起きると一部の端末がチャネルを取得できなくなって飢餓状態になる可能性がある。従って、既存のコンテンションベースチャネルアクセス方式では、チャネルアクセス遅延を確実に上限値以下に抑えることができない。そのため、ネットワークが高負荷になっているときには、ソフトリアルタイムアプリケーションのみならずバルク転送アプリケーションすら、そのネットワーク上では実行できなくなる。
【０００４】
コンテンションフリーチャネルアクセス方式はこうした問題点を解決するために提案されたものであり、これを用いることによってコンフリクトフリー（競合排除的）なチャネルアクセスを実現することができる。しかも、その通信システムのノードに当たる個々の通信装置の周辺で無線状態がどのような状態かに左右されない。コンテンションフリーチャネルアクセス方式には、大別してトポロジインディペンデントな方式とトポロジディペンデントな方式がある。そのうちトポロジインディペンデント（ネットワークトポロジ非依存型）コンテンションフリーチャネルアクセス方式においては、固定的な送信スケジュールに従い、そのアドホックネットワーク内の各ノードに位置する個々の通信装置を通信チャネルに周期的にアクセスさせる。例えば、グローバルスケジュールを構成する１個又は複数個のユニークなサブチャネル例えばタイムスロットを、各通信装置に事前に割り当てるようにする。従って、こうした方式では衝突は発生し得ず、またチャネルアクセス遅延も確実に抑えることができる。反面、各通信装置での制御信号オーバヘッドがかなり嵩む、各通信装置がネットワーク全体についての知識を持っていなければならない、チャネル利用率が低くなりやすい等といった問題が生じるのが普通である。
【０００５】
これに対して、トポロジディペンデント（ネットワークトポロジ利用型）コンテンションフリーチャネルアクセス方式においては、小規模な通信装置群毎に個別に送信スケジュールを決定するので、高負荷時の利用率低下といった問題が生じない。しかも、そのために新たに必要になる情報は、ローカルトポロジ情報即ちそのネットワーク上の小範囲についてのトポロジ情報だけである。この方式の一例たる動的（ランダム）チャネルアクセス方式では、各通信装置が自装置に対応するサブチャネルを使用してチャネルにアクセスできる確率が常にある程度は生じるよう、送信スケジュールを確率的に決定する。
【０００６】
【非特許文献１】A.Aggarwal, L.J.Guibas, J.Saxe and P.W.Shor, "A Linear-Time Algorithm for Computing the Voronoi Diagram of a Convex Polygon", Discret and Computational Geometry 4, pp.591-604, 1989
【非特許文献２】L.Bao and J.J.Garcia-Luna-Aceves, "A New Approach to Channel Access Scheduling for AdHoc Networks", Proc.ACM Mobicom 2001, 2001
【非特許文献３】J.Chuzhoy and Y.Rabani, "Approximating K-Median with Non-Uniform Capacities", in 'SODA '05:Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms', Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, pp.952-958, 2005
【非特許文献４】R.Levi, D.B.Shmoys and C.Swamy, "LP-Based Approximation Algorithms for Capacitated Facility Location", in G.N.Daniel Bienstock ed., 'Integer Programming and Combinatorial Optimization: 10th International IPCO Conference', Vol.3064 of Lecture Notes in Computer Science, Springer, Berlin, pp.206-218, 2004
【非特許文献５】V.Radhakrishnan, S.O.Krumke, M.V.Marathe and D.J.Rosenkrantz, "Compact Location Problems", in 'Lecture Notes in Computer Science', Vol.761, Springer Verlag, 1993
【非特許文献６】Z.Tang and J.J.Garcia-Luna-Acevas, "A Protocol for Topology Dependent Transmission Scheduling", in Proc.IEEE Wireless Communications and Networking Conference 1999(WCNC99), September 1999
【発明の開示】
【発明が解決しようとする課題】
【０００７】
こうしたトポロジディペンデントなコンテンションフリーチャネルアクセス方式によれば、トポロジインディペンデントなコンテンションフリーチャネルアクセス方式に比べ制御信号オーバヘッドを抑えることができるが、残念なことにチャネルアクセス遅延を確実に抑えることができない。とりわけ、その通信システム内で同じサブチャネルを取り合う関係にある他の通信装置の台数が増えると、各通信装置が自装置用にサブチャネルを獲得できる確率が下がってしまう。
【０００８】
従って、上掲の問題点が解消乃至緩和されたチャネルアクセス方法及び装置が、求められているといえよう。
【課題を解決するための手段】
【０００９】
ここに、本発明は、複数個のサブチャネルを含むチャネルを使用し複数の装置間で随時フレームをやりとりする通信システム等にて実施することができる。その場合、各装置に、予約可能サブチャネル群の中から予約候補サブチャネルを選択する機能と、選択済サブチャネルの中から選択済サブチャネル数を限度にフレーム毎に且つ動的にサブチャネルを予約する機能とを、持たせるようにする。また、予約候補サブチャネルの選択は、予約可能サブチャネル群における隣接サブチャネル間短手距離、その装置に対するデータ流入からその装置によるデータ送出までの待ち時間、又はその双方に基づき行うようにする。
【００１０】
予約候補サブチャネルとしては、例えば、予約可能サブチャネルのうち隣接サブチャネル間短手距離の分散がより小さくなる複数個を選択する。
【００１１】
サブチャネルの選択に際しては、例えば、従前の帯域幅条件に基づき各チャネルにおける予約可能サブチャネル数を制限するグリーディ法を併用する。
【００１２】
サブチャネルの選択は、例えば、流入データ量と送出待ち時間の積の加重総和乃至平均、隣接サブチャネル間短手距離と送出待ち時間乃至スイッチングラテンシの加重平均、又はその双方が小さくなるように行う。更に、クラス乃至種類が異なる複数通りのデータについてそれぞれ短手距離を求め、それらに基づきサブチャネルを選択するようにしてもよい。
【００１３】
サブチャネルを予約するときには、例えば、予約済サブチャネルのうち何れか又は全てを解放する処理、新たに選択したサブチャネルを予約する処理、又はその双方を実行する。
【００１４】
サブチャネルは、例えば、タイムスロット、周波数帯域、スペクトラム拡散コード、指向性アンテナ等のフレーム送受信手段に対応付ける。
【００１５】
また、本発明は、こうした通信システム用の通信装置としても表現することができる。
【００１６】
そして、本発明は、当該通信システム向けの通信手順であって上掲の各機能に対応するステップを含む手順としても、表現することができる。
【発明を実施するための最良の形態】
【００１７】
以下、本発明の実施形態に係る通信システム、そのシステムで実行される通信手順及びそのシステムを構成する通信装置について説明する。本発明に係る通信システムにおいては本発明に係る通信手順を実行することによって装置間通信を行う。具体的には、その通信システムのノードたる個々の通信装置間で、複数個のサブチャネルを含むチャネルを介してフレームを送信即ち交換する際に、本発明に特徴的な予約法を通信装置毎に実行して、ネットワーク内共用通信チャネルに対するアクセスをスケジューリングする。
【００１８】
また、本発明には様々な実施形態がある。そのうちある種の実施形態では、各通信装置がどのサブチャネルを予約するのかを、隣接サブチャネル間短手距離の分散（ジッタ）、データトラフィック乃至データフローの特性、或いはその双方に基づきフレーム毎に決定する。例えば、その通信装置へのデータ流入からその通信装置によるデータ送出にスイッチングするまでの待ちに係るラテンシが短くなるように、選択済サブチャネルの中からサブチャネルを予約する。こうして予約、決定したスケジュールによれば、本通信システムにおけるチャネル利用率を高めチャネルアクセス遅延を短くすることができる。
【００１９】
この予約処理はフレーム単位で実行されるので、各サブチャネル毎にフレーム個数分繰り返されることとなる。従って、各フレーム用にどのサブチャネルを予約するかという予約問題は、リング沿い割当問題として図式表現することができる。そのため、以下の説明では、本発明の実施形態に係る予約法のことをＲＯＡＲ(Ring Optimal Assignment Reservation：リング沿い割当最適化型予約法)と称している。このＲＯＡＲは、コンテンションベース及びコンテンションフリーの何れであるか、またトポロジーディペンデント及びトポロジーインディペンデントの何れであるかを問わず様々なチャネルアクセスプロトコルと組み合わせることができるが、動的チャネルアクセスプロトコル、即ちダイナミックエレクションとも称されるプロトコルと組み合わせるのが望ましい。この種のプロトコルであれば、その通信装置によるサブチャネル予約と他の通信装置によるサブチャネル予約とがコンフリクトした場合に、それを解決、解消することができる。また、予約スケジュールに変更があった場合に、それに関する情報を通信装置間でやりとりする形態で、本発明を実施することもできる。
【００２０】
更に、本発明に係る通信システム、通信手順乃至通信装置の用途は多岐に亘っている。即ち、ＷｉＦｉ(登録商標)、ＷｉＭａｘ(商標)又はＩＥＥＥ(登録商標)８０２規格に準拠したＬＡＮや、ＷＡＮ(Wide Area Network)、ＭＡＮ(Metropolitan Area Network)等といったネットワークや、ＧＳＭ(登録商標)等の携帯電話網等、様々なネットワークで本発明を利用することができる。また、本発明に係る通信手順は、本発明に係る通信システムに参加する様々な通信装置にて実行することができる。即ち、固定局か移動局かの別を問わず、また局、装置、ノード等どのような名称のものでもよい。更に、固定セル型のネットワークでもまたランダム乃至アドホック型のネットワークでも本発明を実施することができる。そして、本発明に係る通信システム、通信手順乃至通信装置は、ＴＤＭＡ(Time-Division Multiple Access)、ＦＤＭＡ(Frequency-Division Multiple Access)、ＣＤＭＡ(Code-Division Multiple Access)等の通信プロトコルや、空間ダイバーシティ法等の通信技術に適合するように、実施することができる。
【００２１】
なお、以下の説明中、選択（エレクション）とは、１個、２個又はそれ以上の個数のフレームの送出に使用したいサブチャネルをその通信システム内の個々の通信装置即ち互いに競合関係にある複数の通信装置それぞれで決めること又はその手法を指している。また、予約（リザベーション）とは、選択済サブチャネルの中からその通信装置でフレーム送出に使用するサブチャネルを決めること（及びその結果を同通信システム内の他の通信装置に知らせること）又はその手法を指している。そして、スケジューリングとは、サブチャネル選択、サブチャネル予約又はその双方を実行するための一群の手順又はその実行を指している。
【００２２】
ここで、ＲＯＡＲについて例示説明するため、図１に、本発明に係る通信システムにて使用するフレーム構成の一例１００を示す。このシステムは、個々のチャネルを複数個のサブチャネル即ちタイムスロット１１０に時分割して使用する構成である（以下同様にタイムスロットをサブチャネルとする例で説明するがサブチャネルには他の形態もある）。各スロット１１０にて送信される個々のフレーム１００は、送信機識別情報やデータ総量等の情報がセットされたスロットヘッダ１１２、データフローに関する情報がセットされたコンテキストパケット１１４、更には他の１個又は複数個の通信装置に伝えたい情報がセットされた１個又は複数個のデータパケット１１６等を含んでいる。
【００２３】
各通信装置は、同じ通信システムに参加している他の通信装置との間で、図示した構成又はそれに類する構成を採るフレーム１００をやりとりする。この通信に際し、各通信装置は、ＭＡＣプロトコル等を含むチャネルアクセスプロトコルに従いタイムスロット１１０を予約する。即ち、選択済スロット１１０のうち何個かを予約しまた予約済スロット１１０のうち不要になったものを解放する。本発明の好適な実施形態ではこれを後述のＲＯＡＲ法に則り行う。なお、図示したフレーム構成は例であり、図示要素中の何個かを削除したもの、逆に何個か新たな要素を追加したもの、何種類かの要素を統合して要素数を減らしたもの、その要素順を入れ替えたもの等、様々な構成のフレームで本発明を実施できる。
【００２４】
以下の説明で使用する記号のうち、Ｓは各チャネルに含まれるタイムスロットの個数を表している。更に、単位時間中に設定できるチャネルの個数はタイミング及びハードウェアによって左右されるものであり、個々の通信装置をシステム側とどの程度正確にクロック同期させうるかにもよるが、チャネル長は例えば１００〜５００ｍｓｅｃ程度になる。チャネルは周期的に繰り返し到来するので、スロット生起タイミングはチャネル長を円周とする円上の位置として表すことができる。
【００２５】
従って、その円即ちスケジュールリングの円周は整数値Ｓで表すことができ、スロット生起タイミングの位置即ちスロット位置はこのリングに沿って時計回り方向に振った１からＳまでの番号により表すことができ、スロット位置の間隔は方向付の円弧で表すことができる。この円弧の長さ即ちスロット間距離は、例えば次のような指標で表す。即ち、リング上のあるスロット位置ｕと別のスロット位置ｖとの間の距離は、次の式の時計回り弧長
【数１】
2008160846.tif 000003
や、次の式の短手弧長（絶対弧長）
【数２】
2008160846.tif 000004
を指標として表現できる。これらの指標のうち、時計回り距離δCLKについてはともかく短手距離δABSについては三角不等式が成り立つので、その関係をうまく利用することで、本発明実施時における予約計算の量をかなり抑えることができよう。なお、三角不等式とは、任意の三点を結んだ三角形の二辺の長さの和が残りの一辺の長さよりも必ず大きくなる、という公式のことである。
【００２６】
図２に、本発明と併用しうるある種のチャネルアクセスプロトコルについて、その問題点を示す。この図は予約してあるタイムスロット即ち予約済スロット２１２，２４２同士の関係を時刻２１０に沿って表したものである。いわゆるグリーディ法に基づくチャネルアクセスプロトコル、即ち従前の帯域幅条件に基づき各チャネルにおける予約可能サブチャネル数を制限するプロトコルを使用した場合、データレートがほぼ一定で且つネットワークに過負荷乃至輻輳が生じていない状態では、図中上側に示すように、予約済スロット２１２とその次の予約済スロット２１２の間の時間間隔２１４がほぼ一定長になる。
【００２７】
しかし、データフローがバースト的で時間変動が大きいときや、ネットワークに過負荷が生じているときには、グリーディ法に則りスロット予約を行うと、図中下側に示すようなチャネルアクセス状態２３０が発生することがある。この状態２３０では、予約済スロット２４２とその次の予約済スロット２４２との間の時間間隔２４４が不定長になるので、その通信システムにおける待ち時間が長くなることがある。以下例示説明するＲＯＡＲによれば、この問題を解消乃至緩和することができる。
【００２８】
ＲＯＡＲの特徴の一つはスロット選択予約問題をある目的関数に対する最適化問題として扱うことにある。例えば、ある通信装置にて使用するフレーム１００の構成が図１に示した構成であるとする。また、第ｉタイムスロットにてその通信装置に流入する負荷データ量をＬiユニット、その通信装置における予約済スロットの集合をＲ、その通信装置にて予約可能スロットの中から新規に選択したタイムスロット即ち予約候補スロットの集合をＷ、それらの和集合Ｒ∪Ｗ即ち選択済スロット集合をＶで、それぞれ表すこととする。ＲＯＡＲで解決する最適化問題とは、選択済スロット集合Ｖの部分集合のうち目的関数を最適化する部分集合Ｖ’を導出する問題のことである。なお、集合Ｖの要素Ｖiたる個々のスロットには、そのスロット１個で送出できる負荷データ量に限界がある。以下の説明ではその限界即ちスロット別送出容量をＣと表記する。最適スロット集合Ｖ’の要素数Ｋはその通信装置における予約可能スロット数以下であるので、その通信装置が１チャネルで送出できる上限の負荷データ量即ち使用可能送出容量はＫ・Ｃユニットとなる。
【００２９】
この最適化問題の解法には大別して次の二種類がある。第１の解法は、Ｋ個のタイムスロットＶiからなる部分集合のうち予約済スロット間距離分散が最小になるもの、即ちその集合に属するスロットを使用するとチャネル内フレーム送出タイミングばらつきが最小になるものを以て、最適スロット集合Ｖ’とする、という解法である。ここでは送信スケジュールをサイクリックなスケジュールとし、毎チャネル同じスロットを送出用に予約するものとしている。この原理による予約法のことを本願ではＲＯＡＲ−Ｖ(ROAR by Variance)法と称する。
【００３０】
第２の解法は、スイッチングラテンシが最短になる部分集合を以て最適スロット集合Ｖ’とし、流入した負荷データをユニット毎にその集合Ｖ’中の何れかのタイムスロットに割り当てる、という解法である。スイッチングラテンシとは、データ流入（インバウンド）に使用されたタイムスロットとデータ送出（アウトバウンド）に使用されるタイムスロットとの間の距離δCLK又はそれに基づく待ち時間指標のことである。この原理による予約法のことを本願ではＲＯＡＲ−Ｌ(ROAR by Latency)法と称する。
【００３１】
また、サブチャネル予約最適化問題にはこれ以外にも幾つか解法がある。そのなかでもＲＯＡＲ−Ｖ法とＲＯＡＲ−Ｌ法を“いいとこ取り”で併用する複合的予約法には、更に幾つかのバリエーションがある。例えば、リアルタイムデータフローに対してはＲＯＡＲ−Ｌ法を適用してスイッチングラテンシを抑え、残った予約可能タイムスロットはＲＯＡＲ−Ｖ法に則りバルクデータフローや新規データフローに割り当てる、という形態である。また、予約可能スロットが十分な個数ある場合に、既知のバルクデータトラフィックに対してはＲＯＡＲ−Ｌ法によりスロットを割り当てる一方、新規若しくは不測のデータフローに対してはＲＯＡＲ−Ｖ法によりスロットを割り当てる、という形態もあり得る。
【００３２】
更には、別々のクラスのリアルタイムデータトラフィックに対し別々にＲＯＡＲ−Ｌ法を適用してタイムスロットを割り当てる形態も採りうる。例えば、まず厳しい期限が付いたデータトラフィックに対しＲＯＡＲ−Ｌ法でスロットを割り当て、その後により緩い期限が付いたデータトラフィックに対し同じくＲＯＡＲ−Ｌ法でスロットを割り当て、最後にバルクデータトラフィックに対しＲＯＡＲ−Ｖ法でスロットを割り当てる、という形態である。また、まず厳しい期限が付いたデータトラフィックに対しグリーディ法（図２参照）でスロットを割り当て、次により緩い期限が付いたデータトラフィックに対しＲＯＡＲ−Ｌ法でスロットを割り当て、最後にバルクデータトラフィックに対しＲＯＡＲ−Ｖ法でスロットを割り当てる、という形態もあり得る。後者で厳守期限付きデータトラフィック向けスロット予約をグリーディ法で行うのは、その種のトラフィックについては大抵の場合スイッチングラテンシ短縮より期限厳守の方が重要視されるので、より期限を守りやすい図２の状態２００にしたいからである。
【００３３】
図３及び図４に、本発明の一実施形態に係るＲＯＡＲ−Ｖ法を示す。図３に示したのはタイムスロット割当が非最適な状態におけるスケジュールリング３００であり、図４に示したのは最適な状態におけるスケジュールリング４００である。これらのリング３００，４００上には、先にも説明した通り、時計盤上での時刻取りと同様の形態でＳ通りのスロット位置が示されている。時刻３１０は図中時計回りに流れる。また、リング３００，４００はそれぞれ内側のリングと外側のリングから構成されており、内側のリング上にはアウトバウンドスロットの理想位置が方形のマーカで、外側のリング上には実際にアウトバウンドに使用できるタイムスロットの位置が円形のマーカで、それぞれ記されている。円形マーカで表された選択済スロットには予約済スロット（既に予約してあるスロット）と予約候補スロット（選択はしたが予約はしていないスロット）とがあり、選択済スロット集合Ｖはそれらが混在した集合になっている。
【００３４】
いま、あるスロット集合に属するタイムスロットのうちスケジュールリング上で互いに隣接しているもの（隣接スロット（より一般には隣接サブチャネル））の間の短手距離δABSの集合をＤと表すこととする。ＲＯＡＲ−Ｖ法でめざしているのは、選択済スロット集合Ｖの部分集合の中からその要素数がＫ個以下でその隣接スロット間短手距離集合ＤV'における分散ｖａｒ（ＤV'）が最小のものを、最適スロット集合Ｖ’として導出することである。なお、リング上のスロット数がＳ、最適スロット集合Ｖ’の要素数がＫであるので、解に期待される隣接スロット間短手距離理想値μはＳ／Ｋになる。
【００３５】
また、スケジュールリング上の三点間でそれぞれ時計回り距離δCLKを求めた場合、得られる三通りの時計回り距離δCLKのうち二通りを加算しても残りの一通りの時計回り距離δCLKより大きくなるとは限らない（即ち時計回り距離δCLKについては三角不等式が成り立たない）ので、ＲＯＡＲ−Ｖ法を時計回り距離δCLKに基づき実行することは困難である。これに対して、短手距離δABSについては三角不等式が成り立つので、リング上における短手距離δABSがほぼ最小になる解であれば求めることができ、またそれはまさにダイナミックプログラミングによって実現することができる。
【００３６】
表１は、ＲＯＡＲ−Ｖ法の一例たるＰｉｃｋＢｅｓｔ手順を実際のプログラムコードを模した形態で表したものである。この手順においては、まず、集合Ｖに属するｎ個のタイムスロットＶi（表中ではＶ［ｉ］；以下他の集合でも同様）のうち位置０のものが最適解に含まれるものと仮定し、そのスロットＶ0を始点兼終点として、表２に示すＦｉｌｌＴａｂｌｅ手順（これも実際のプログラムコードを模した形態で示す）を実行する。ＦｉｌｌＴａｂｌｅ手順は、指定された始点位置ｉからＫ個のスロットを巡って始点と同じ終点位置ｉに至る種々の経路のうち、その経路沿いで求めた隣接スロット間距離ＩＶiの自乗和が最小になる暫定解を、特定、判別する手順である。ＰｉｃｋＢｅｓｔ手順では、次いで、次のスロットＶ1を新たな始点兼終点に指定して、同様のＦｉｌｌＴａｂｌｅ手順を繰り返す。これを繰り返してｉ＝０〜ｎ−１の範囲全体を調べること、即ちスケジュールリング上にＳ個あるスロットのうち集合Ｖに属するものを始点兼終点とする暫定解を求めそれらを逐次比較することで、隣接スロット間距離自乗和が最小になる経路ｐ即ち最適解と、その経路ｐにおける隣接スロット間距離自乗和ｓｓとがわかる。なお、ＦｉｌｌＴａｂｌｅ手順にて求める距離ＩＶiは短手距離δABSである。
【００３７】
【表１】
2008160846.tif 000005
【００３８】
【表２】
2008160846.tif 000006
【００３９】
ＦｉｌｌＴａｂｌｅ手順では、まず、そのサイズがＫ×ｎの二次元配列ｍ［ｒｏｗ，ｃｏｌ］を準備する。配列ｍは経路ｐ及びその経路ｐにおける隣接スロット間距離自乗和ｓｓからなる順序対（ｓｓ，ｐ）を格納するための配列である。経路ｐは、始点より後にその経路ｐで辿るタイムスロットの位置ｃｉの順序集合（ｃ１，ｃ２，…，ｃＫ）で表す。ＦｉｌｌＴａｂｌｅ手順では、ＰｉｃｋＢｅｓｔ手順にて巡回指定される始点兼終点についての暫定解を、それぞれ自乗和ｓｓ及び経路ｐの順序対（ｓｓ，ｐ）として表された配列要素から選び出す。但し、スケジュールリングは閉じていなければならないので（経路の終点が始点に重ならねばならないので）、ＦｉｌｌＴａｂｌｅ手順による計算は第Ｋ行まで行う。従って、実際に得られる暫定解はＫ＋１個のスロットを含んでいる。
【００４０】
ＦｉｌｌＴａｂｌｅ手順では、始点兼終点位置ｉが指定されると、まずその位置のタイムスロットＶiからの距離ＩＶiの自乗δＩＶi2をタイムスロットｊ毎に求め、それを含む順序対（δＩＶi2，（φ））によって配列要素ｍ［１，ｊ］を初期設定する（φ：空）。始点兼終点からその隣接スロットまでの距離であるので、単なる自乗を以て自乗和の初期値にすることができる。次いで、ｒｏｗ＝２〜Ｋの範囲については、第ｒｏｗ−１スロットまでの隣接スロット間距離自乗和ｍ［ｒｏｗ−１，ｋ］．ｓｓに当該第ｒｏｗ−１スロットからの距離の自乗δＩＶi2を加算した値ｘが最小になるものを、ｋを変化させて選んで、その値ｘと、それに対応するスロット位置順序集合ｍ［ｒｏｗ−１，ｋ］．ｌａｓｔ∪ｋとからなる順序列ｅにより、配列要素ｍ［ｒｏｗ，ｃｏｌ］を埋める。
【００４１】
こうして配列要素がｍ［Ｋ，ｎ］まで埋まったら、配列要素ｍ［Ｋ，ｎ］から解を逆読みしていく。上掲の通り、配列ｍの各要素は、列番号ｃｉの順序集合（ｃ１，ｃ２，…，ｃＫ）で表した経路ｐと、その経路に沿った自乗和ｓｓからなる順序対（ｓｓ，ｐ）であるので、経路ｐに沿って逆読みしていくことで、そのときの始点兼終点位置ｉについての暫定解を読み取ることができる。従って、ＰｉｃｋＢｅｓｔ手順で最適解を求めるには、逆読みで暫定解を求める処理を隣接スロット間距離の集合ＩＶを回転させながら繰り返す必要がある。
【００４２】
但し、ＰｉｃｋＢｅｓｔ手順の実行所要時間は時刻を変数とする多項式によって与えられる。その実行には概ねＯ（ｎ3・Ｋ）オーダの回数の演算を行う必要があるので、この手順によりスケジューリングを行うにはかなり高い処理能力が必要になる。例えば、５００ｍｓｅｃ長のチャネルを複数個のタイムスロットに時分割する通信方式で、各チャネルのうち３００ｍｓｅｃを動的スロット選択とチャネルアクセスプロトコル更新に使用する場合、残りの２００ｍｓｅｃの間にＰｉｃｋＢｅｓｔ手順を終えねばならない。予約済スロットと予約候補スロットの合計で選択済スロットが１チャネル当たりｎ＝約１００個あるとすると、ＰｉｃｋＢｅｓｔ手順によって例えばＫ＝約１０個のスロットを予約するには、その２００ｍｓｅｃの間にｎ3・Ｋ≒１０００万回以上の演算を行える装置が必要になり、それには数ＧＨｚ以上の処理速度を有するプロセッサが必要になる。そのため、ＰｉｃｋＢｅｓｔ手順で得られる最適解を近似する解しか得られないがよりヒューリスティックな近似的解法で、ＲＯＡＲ−Ｖ法を実施するのも理に適っている。ヒューリスティックな近似的解法であれば演算回数をO（K・ｎ・ｌｏｇ（ｎ））オーダに抑えることができるので、上に示した例と同じ前提なら２００ｍｓｅｃの間に１万回オーダの演算を行えればよく、プロセッサの速度はＭＨｚオーダで足りる。
【００４３】
ＲＯＡＲ−Ｖ法のヒューリスティックな実施形態でも、スケジュールリング上で所要個数のタイムスロットを通る経路の中から隣接スロット間短手距離分散σ2が最小になるものを探してスロットを予約する。例えば、各チャネルを１６スロットに時分割して使用する通信システムがあるとする（Ｓ＝１６）。また、図３及び図４に示すように、それら１６個のスロットのうち予約済のもの及び新規選択したものからなる選択済スロット集合Ｖの要素数が６であるとする（ｎ＝６）。そのなかから３個のスロットを予約する（Ｋ＝３）処理をＲＯＡＲ−Ｖ法によって行う場合、まず、集合Ｖに属するスロットのうち何れか１個が始点兼終点として指定される。Ｓ＝１６、Ｋ＝３であるから隣接スロット間短手距離期待値μは１６／３であるので、第１スロットを始点兼終点として指定した場合の理想スロット位置ｕi（ｉ＝１，…，Ｋ）は、スケジュールリング３００の内側リング上に示した通り位置１からμおきで並ぶｕ1＝１、ｕ2＝１９／３、ｕ3＝３５／３の３個になる。ＲＯＡＲ−Ｖ法のヒューリスティックな実施形態では、リング３００の外側リング上にマーカで示したスロットの集合Ｖから、各理想位置ｕiにそれに最も近いスロットを暫定解要素として採用する。図３の例で採用される位置ｖi（ｉ＝１，…，Ｋ）はｖ1＝１、ｖ2＝８、ｖ3＝１１、それらについての分散σ2は約３．２になる。この次に始点兼終点として指定されるのは図４に示すように第３スロットであり、その場合における理想位置ｕiはリング４００の内側リングに示す通り位置３からμおきでｕ1＝３、ｕ2＝２５／３、ｕ3＝４１／３の３通り、集合Ｖに属するスロットのうち各理想位置ｕiに最も近いものの位置ｖiは外側リング上から読み取れるようにｖ1＝３、ｖ2＝８、ｖ3＝１４の３個、そしてそれらについての分散σ2は約０．２になる。以後集合Ｖに属する各スロットを始点兼終点として同様の処理を繰り返すと、図示例の場合第３スロットを始点兼終点とした場合の暫定解ｖ1＝３、ｖ2＝８、ｖ3＝１４で分散σ2が最小になるのでその解が最適解として扱われる。
【００４４】
また、上の例では各理想スロット位置に最も近いタイムスロットの個数が１個であったが、スケジュールリング上でその理想位置の前後にある合計２個のスロットがその理想位置に対して互いに（ほぼ）等距離になる場合もある。このように理想位置に対して複数のスロットが距離的に拮抗した場合には、どちらのスロットを以て暫定解要素とするかを効率的に決める論理を使用するとよい。例えば図５に示すリング５００においては、外側リング上にマーカで示されているスロットの集合Ｖのうち位置４及び６にある２個のスロットが、内側リング上の理想位置５に対して互いに等距離になっている。こうした場合には例えばルックアヘッド処理を実行するとよい。即ち、まず、集合Ｖの中で拮抗先理想位置５から１個後の理想位置９に最も近いスロットがどれかを先取りで調べる（ルックアヘッド５１０）。該当するのは位置８のスロットであるので、その結果を理想位置５についての暫定解要素採否判断にフィードフォワードする。即ち、相拮抗している位置４及び６のスロットそれぞれについてスロット８に至る経路（部分）の距離自乗和を計算し、計算結果が小さい方を判別、採用する。図示例の場合、位置４直前直後部分の距離自乗和は３2＋４2＝２５、位置６直前直後部分の距離自乗和は５2＋２2＝２９であるので、距離自乗和が小さくなる位置４のスロットを以て理想位置５に対応する暫定解要素とする。
【００４５】
但し、このように１個後の理想位置に最も近いタイムスロットをルックアヘッドする処理だけでは、更にそのルックアヘッド先にも距離的な拮抗関係がある場合等に、長い時間のかかる組合せ計算が必要になることがある。例えば、図６に示すスケジュールリング６００では、ルックアヘッド先理想位置９について位置８及び位置１０のスロットが距離的な拮抗関係にある。こうした場合、面倒な組合せ計算を避けるために、位置８及び位置１０のスロットのうち一方をランダムにピックアップし理想位置９に対応する暫定解要素と仮定する（ランダムピック６１０）。位置８のスロットが仮定された場合は、図５に示した例と同様、理想位置５について相拮抗する２個のスロットのうち位置４のスロットがその理想位置５に対応する暫定解要素として採用される。これに対し、位置１０のスロットが仮定された場合、理想位置５に対応する暫定解要素として位置６のスロットを採用した方が距離自乗和が小さくなるので、理想位置５に対応する暫定解要素としては位置６のスロット即ち長期的に見て次善な方が採用される。なお、ある処理サイクルでルックアヘッド処理が実行された場合でも、その後の処理サイクル即ち先取りされた理想位置に係る暫定解要素を決めるサイクルで、前の処理サイクルで暫定解要素と仮定されたスロットが暫定解要素として必ず採用されるわけではない。また、以上説明したのは１個先取り版のルックアヘッド処理であったが、これは無論、複数個先取り版に拡張することもできる。複数個先取りするとより長い処理時間が必要になる反面よりよい解が見つかりやすくなる。
【００４６】
ＲＯＡＲ−Ｖ法のヒューリスティックな実施形態の一例としては、表３に示すＲｏｔａｔｅＲｉｎｇ手順がある。この表は、実際のプログラムコードを模した形態でＲｏｔａｔｅＲｉｎｇ手順を表したものである。ここに例示したＲｏｔａｔｅＲｉｎｇ手順においては、ＦｉｎｄＮｅｘｔ手順を実行することにより、始点として指定されたタイムスロットからｋ＝１，…，Ｋ−１個後まで、合計Ｋ個のスロットＶiの中から理想スロット位置ｔａｒｇｅｔとの距離が最も小さくなる頂点要素即ち暫定解要素を見つけていく。ＲｏｔａｔｅＲｉｎｇ手順においては、この処理をその始点となるスロットを変更しつつ、また理想スロット位置ｔａｒｇｅｔを隣接スロット間短手距離期待値μ（表３ではｕと表記）ずつ更新して繰り返し実行することにより、近似解を見つける。
【００４７】
【表３】
2008160846.tif 000007
【００４８】
表４は、ＦｉｎｄＮｅｘｔ手順を実際のプログラムコードを模した形態で表したものである。この手順を実行すると、返り値として空集合｛φ｝、集合｛ｉ1｝又は集合｛ｉ1，ｉ2｝が得られる。返り値が空集合であるなら調べた構成が無効であるということである。そうしたケースは、通常、まだ調べていないタイムスロットの個数が予約したいタイムスロットの残り個数（最大Ｋ）より少ないときに生じる。
【００４９】
【表４】
2008160846.tif 000008
【００５０】
また、返り値が単一要素集合｛ｉ1｝ならその要素ｉ1たるタイムスロットが単一且つ最適な頂点即ち暫定解要素であり、二要素集合｛ｉ1，ｉ2｝ならその要素ｉ1，ｉ2たる２個のスロットはその理想位置に対して等距離である（距離的に拮抗している）。後者の場合は、要素ｉ1前後の経路部分における距離自乗和と要素ｉ2前後の経路部分における距離自乗和とを比較し小さな距離自乗和を呈する方の要素を以て暫定解要素として採用する（ルックアヘッド処理）。但し、そのとき調べていたのが解の半ばに位置する理想位置ではなくＫ番目に位置する理想位置に最も近いスロットの位置であるなら、始点から終点に至る全経路での隣接スロット間短手距離分散が最小になる方の要素を暫定解要素として採用する。また、ルックアヘッド先理想位置に対して２個のスロットが互いに等距離であるときはそれらのうち一方をランダムにピックアップして暫定解要素と仮定しフィードフォワードする（ランダムピック処理）。
【００５１】
次に、タイムスロット予約問題を待ち時間に着目してＲＯＡＲ−Ｌ法で解く場合には、集合Ｖの部分集合のうちその要素数｜Ｖ’｜が予約可能スロット数最大値Ｋ以下の部分集合であってデータ流入からデータ送出へのスイッチングに係る待ち時間即ちスイッチングラテンシが最短になる集合Ｖ’を、解として求める。更に、その解は、スロット１個で送出する負荷データユニット数がスロット別送出容量Ｃ以下に収まる、という条件と、そのチャネル全体での流入負荷データのうち使用可能送出容量Ｋ・Ｃ以下の個数のユニットを送出する、という条件とを、満たしていなければならない。なお、スイッチングラテンシは、時計回り距離δCLKとスイッチング対象負荷データユニット数とを乗じて求める。
【００５２】
以下、ＲＯＡＲ−Ｌ法の実施形態として、まずグリーディ法を利用して初期解を決め、その初期解を可制御なブランチアンドバウンド法で改質する、という実施形態を説明する。この実施形態は短時間で実行することができ、また初期解改質に費やす時間を上限制御することができるため、通信システムにおけるリアルタイム処理上のデッドラインを遵守することができる。解の導出には、スケジュールリング上の各部各部のトポロジを利用する。
【００５３】
図７及び図８に、本発明の一実施形態に係るＲＯＡＲ−Ｌ法を説明するためスケジュールリング７００，８００を示す。リング７００，８００はそれぞれ内側のリングと外側のリングから構成されており、内側のリング上にはこの通信装置への負荷データ流入タイミングが方形のマーカで、外側のリング上にはこの通信装置からの負荷データ送出用に予約できるタイムスロットの位置が円形のマーカで、それぞれ記されている。選択済スロットを示す円形マーカにはスミヌリのマーカと白抜きのマーカがあり、スミヌリのマーカは予約済スロットを、白抜きのマーカは新規予約即ち予約候補スロットを、それぞれ表している。更に、図中のスポーク状の線には対応するスロットの位置を表す番号１，…，Ｓが付されている。
【００５４】
スケジュールリング８００上に示されている割当例は、その送信容量Ｃが５のアウトバウンドスロットに対しその容量制限を満たすようにインバウンドデータを割り当てた例である。本実施形態に係るグリーディ法ブランチアンドバウンド法併用手順では、グリーディ法でこうした初期解を得た上で、その初期解に応じた初期条件に則りブランチアンドバウンド法で状態空間に対するバイナリサーチを行う。また、先に説明した例と同じく、位置ｉにあるインバウンドスロットにて流入する負荷データの量を流入負荷データユニット数Ｌiで表すこととする。各インバウンドスロットにおける流入負荷データは、アウトバウンドスロットを介しこの通信装置から送出することができるよう０〜Ｃ個のユニットに整数分割しなければならない。
【００５５】
更に、本手順では、現チャネル中でこの通信装置が送出に使用可能なタイムスロットを網羅する集合Ｖの部分集合Ｖ’のうち、その要素数｜Ｖ’｜がＫ個以下でスイッチングラテンシが最短になるものを選り出し、送信用に割り当てることを目的とする。その際、流入負荷データユニット数δLが使用可能送出容量Ｋ・Ｃを上回っていると、送出容量不足で流入負荷データ全てを送出に回す（スイッチングする）ことができないので、確保できる送出容量Ｋ・Ｃの範囲内でスイッチングラテンシが最短になるよう部分集合Ｖ’を導出する。
【００５６】
本手順では、まずグリーディ法に基づく初期解導出を実行する。図７に示すように、集合Ｖに属するタイムスロット群における隣接スロット間期間はその集合Ｖの要素数｜Ｖ｜と同じ個数あり、それぞれ、その期間の始点を第ｊスロット、終点をスロットＶjとする期間Ｉjとして表すことができる。ここに、例えば第４スロットとスロットＶ4で挟まれた期間Ｉ4＝［５，８］においては、位置６及び位置７の合計で６ユニットの負荷データ（方形マーカに付された数字の合計）が流入していることがわかる。スロット別送出容量Ｃが５であるので、少なくともそれらのうち１ユニット（例えば位置７で流入したもの）は位置８より後のスロットで送出せざるを得ない。そのため、位置８までの遅延時間と遅延ユニット数の積の総和、即ち遅延スロット数ユニット数積和は、最小で、位置６についての遅延スロット数２×流入データユニット数３＝６と位置７についての遅延スロット数１×（流入データユニット数３−先送りの１ユニット）＝２との和８になる。初期解導出には、従前の帯域幅条件に基づき（例えば予約済スロット集合Ｒに属するスロットを対象として）個々の隣接スロット間期間に対し同様の処理を実行すればよい。
【００５７】
即ち、与えられた隣接スロット間期間における流入負荷データユニットの中から、とりあえず、その期間の終点から最も遠い位置即ち最も早い時点のタイムスロットで流入したユニット（群）を選び、その期間の終点に位置するタイムスロットをそのユニット（群）の送出用に仮予約する。次いで、仮予約したスロット及びそのスロットで送出する負荷データユニットについてはとりあえず問題が解決したと見なし、まだ空きのあるスロット及びまだ仮予約が済んでいない流入負荷データユニットを対象に、同様の選択及び仮予約処理を繰り返せばよい。繰り返し回数は最多でスロット数のＫとなる。
【００５８】
このように、グリーディ法では隣接スロット間期間に着目して大まかに仮予約を行うのである程度のスケジュール遅延が発生する。その量は前述の通り遅延スロット数ユニット数積和で表される。例えばスケジュールリング８００上にスミヌリ円形マーカで表したスロットを仮予約すると、遅延スロット数ユニット数積和で表したスケジュール遅延は５７になる。次に実行するブランチアンドバウンド法では、このスケジュール遅延例えば遅延スロット数ユニット数積和を初期条件Δとして用いる。
【００５９】
ブランチアンドバウンド法においては、各分岐点（後述）におけるコスト指標として遅延時間指標を計算し、その結果をこの初期条件Δに照らして予約を行う。即ち、初期条件Δに照らしそのスロットを送信用に予約するかそれとも無視する（予約しない）かを決める処理を、集合Ｖに属する各タイムスロットについて行う。初期条件Δに照らすコスト指標としては、その分岐点までのスケジュール遅延合計値σにその分岐点で計算した先送り性遅延δを加算した値σ＋δを用いる。そのうちスケジュール遅延合計値σの方は前掲の遅延スロット数ユニット数積和の累計で計算し、先送り性遅延δはまた別の手法で計算する。即ち、先送り性遅延δとは、今調べているスロットにてその負荷データを送出したときに生じるであろう遅延に比べて、そのスロットを無視しその次のスロットにて負荷データを送出したときにどの程度遅延が増すか、即ち今調べているスロットを無視したことで付加的に発生してしまう遅延の量を、示す指標である。各分岐点では、その分岐点で調べるスロットを無視した場合に生じる先送り性遅延δを計算しコスト指標σ＋δを求めて初期条件Δと比較する。σ＋δ＞Δであれば条件超過であるので、そのスロット及びその子スロット（二値判別ツリーでその先にある分岐点）全てを無視することに決める。逆に、予約できるのであればその分岐点でのスケジュール遅延を計算してそれまでのスケジュール遅延合計値σを加算更新する。
【００６０】
ここで、未実現遅延合計値ではなく先送り性遅延δを使用するのは、ブランチアンドバウンド法ではその方がより多くの選択肢を発見できるからである。特に、無視するタイムスロットの次のスロットに対するスロット数ユニット数積総和を未実現遅延合計値として扱いコスト指標に組み込むとしたら、その値は早々と初期条件Δを超過してしまう。そのため、仮にそれに基づき送出用スロットを探索したとしても、上限値以下の未実現遅延合計値を呈するような選択肢は見つけられないことが多くなろう。それよりは、今調べているスロットに近い数個について、送出容量Ｋ・Ｃの制限内で些少な遅延で実際にフレーム送出を行えるか否かを調べていった方がよい。
【００６１】
ブランチアンドバウンド法においては、状態空間にて定義された二値判別ツリー（バイナリツリー）として問題を表現し、このツリー上の各分岐点にてスロット採否検討即ちバイナリサーチを行う。また、各分岐点にはラベルを付す。このラベルは残り予約可能スロット数余裕ｒ及び残り未予約スロット数ｑによる順序対（ｒ，ｑ）である。残り予約可能スロット数余裕ｒとは、選択済スロット集合Ｖに属するスロットのうちこれまでのところ無視されていないスロットの個数から、残り未予約スロット数ｑを減じた値である。また、二値判別ツリーのルートに位置する分岐点、即ち集合Ｖに属するどのスロットも調べられておらずラベル（｜Ｖ｜−Ｋ，Ｋ）が付されている分岐点では、スケジュール遅延合計値σ及び先送り性遅延δが共に０、従ってその加算値も０である。
【００６２】
二値判別ツリーの各分岐点では、その分岐点に係るタイムスロットＶiを送信用に予約するのかそれとも無視するのかを決定する。予約する場合は、その分岐点（ｒ，ｑ）にて算出したスケジュール遅延でスケジュール遅延合計値σが更新され、次の分岐点（ｒ−１，ｑ−１）に移る。先送り性遅延δは増えない。逆に、その分岐点（ｒ，ｑ）に係るタイムスロットＶiを無視する場合は、先送り性遅延δが増え、別の分岐点（ｒ−１，ｑ）に移る。スケジュール遅延合計値σは増加させない。
【００６３】
また、二値判別ツリーには、そこで判別処理が終わりになる終端分岐点として、分岐点（ｒ，０）、分岐点（０，ｑ）及びそれらの中間に位置する種々の分岐点がある。そのラベルから読み取れるように、分岐点（０，ｑ）では最早タイムスロットを選り好みする余地がなく、残りｑ個のスロットについては判別処理を断念せざるを得ない。そのため、この分岐点（０，ｑ）に達したら例えば残りｑ個のスロットを全て予約するように前もって決めておく。同じく分岐点（ｒ，０）ではまだ予約可能なスロットがｒ個残っているが当初設定したｑ＝Ｋ個のスロットは予約を終えている。即ち、グリーディ法により初期導出された分岐条件Δを満たす経路に沿ってスロットの予約がなされている。そして、分岐点（ｒ，０）と分岐点（０，ｑ）の間に位置する分岐点、例えば（｜Ｖ｜−Ｋ−１，０）では、検討によりスロットが１個無視されたが当初設定したｑ＝Ｋ個のスロットは予約を終えている。総じて、終端分岐点は何れも（ｘ，０）、（０，ｘ）又は（０，０）の形式で表現できるが、これらのラベルはユニークではなく二値判別ツリー上に何回でも現れうる。
【００６４】
こうしたブランチアンドバウンド法で予約を行うと、最悪の場合、Ｖ個のタイムスロットからＱ個を取り出すときの組合せ｜Ｖ｜／Ｑ通りを全て調べることを余儀なくされ、処理所要時間が極めて長くなる可能性がある。しかしながらそれは最悪の場合である。平均的には、グリーディ法で定めた初期条件Δを上回る経路を調べることがないようコスト指標σ＋δによる制限を課してあるため、処理所要時間はＯ（Ｑ）オーダより若干長めの時間でほぼ安定する。更に、ブランチアンドバウンド法では各分岐点で尤もらしい（実現性のある）方を選択して処理を進めるので、二値判別ツリーに沿った処理に要する時間をほどほどに抑えつつ、そこそこ好適な解を発見することができる。勿論、ブランチアンドバウンド法の代わりに、例えばシミュレーティッドアニーリング法その他、本件技術分野で知られている様々な最適化法を使用することができる。
【００６５】
更に、フレーム送出の度にタイムスロット予約を行う装置では、ある種の複合的な方式を採用するとよい。即ち、新たなデータフローが到来したとき、予約可能スロットのうち最多でＫ個をスイッチング用にリアルタイム予約できるような方式を採用するとよい。また、例えばチャネル乃至フレームの始期終期等を捉えて周期的にＫ個の最適なスロットを選択、予約する大域的にヒューリスティックな予約法を使用するようにすれば、全データフローに亘るスイッチングラテンシを抑えることができる。
【００６６】
例えば、予約可能タイムスロットがありそのスロットを予約しても予約済スロット数がその装置における上限個数Ｋを超過しない場合には、新たなデータフローが到来したらそのデータフローのスイッチング用に新たなスロットを予約することができる。そうでない場合は、例えば予約済スロット等使用可能なその他のスロット中の未使用帯域を使用して、そのデータフローをスイッチングするようにすればよい。更に、周期的に到来する最適化時期には、全てのデータフローを検討して新規にスロットを選択し、当該新規選択スロットと予約済スロットを対象にスロット予約処理を実行するとよい。また、あるデータフローが高優先度のデータ、例えばリアルタイムデータ、ロージッタデータ、バルクデータ等である場合は、最高優先度のトラフィックを最優先で最適化するという方針で、そのトラフィック用のスロットを直ちに予約するとよい。
【００６７】
また、流入データ量にそれに対応する送信待ち時間を乗じた量の加重平均、隣接サブチャネル間短手距離とスイッチングラテンシの加重平均、又はその双方が小さくなるようサブチャネルを選択する形態で、本発明を実施することもできる。更に、データに複数のクラス乃至種類がある場合に、各クラス乃至種類毎に隣接サブチャネル間短手距離やスイッチングラテンシを求め、例えば第１クラスの短手距離と第２クラスのスイッチングラテンシに基づきサブチャネルを選択する形態でも、本発明を実施することができる。
【００６８】
なお、それぞれ図３〜図８に示したスケジュールリング３００、４００、５００、６００、７００及び８００を参照して本発明に係る予約法の実施形態について説明したが、本発明は、説明した手順のうち一部を削除したもの、別の手順を付加したもの、説明したステップ同士を統合したもの、ステップ乃至手順の実行順序を入れ替えたもの等、様々な形態で実施できる。
【００６９】
次に、本発明に係る装置間通信手順の具体例について説明する。図９は、本発明の一実施形態における装置間通信手順９００を示すフローチャートである。本手順９００においては、通信システム内の個々の装置が複数個のサブチャネルを含むチャネルを使用して随時フレームをやりとりする（９１０）。各装置は、特に、予約可能サブチャネルの中から予約候補サブチャネルを判別・選択し（９１２）選択済サブチャネルの中からフレーム送出用のサブチャネルを予約する（９１４）。サブチャネルの選択は、自装置へのデータ流入と自装置からのデータ送出の間のスイッチングラテンシ、予約可能サブチャネル群における隣接サブチャネル間短手距離、又はその双方に基づき行い、サブチャネルの予約は、選択済サブチャネル数を限度としてフレーム毎に且つ動的に行う。なお、この手順は一例であって、図示した手順の一部を省略することや、図示した手順に別のステップを追加することや、各ステップの実行順序を入れ替えることや、複数個のステップを結合させて単一のステップにすること等、様々な変形を施すことができる。
【００７０】
更に、本発明に係る通信装置の具体例について説明する。図１０は、本発明の一実施形態に係る通信装置１０００の構成を示すブロック図である。本装置１０００は、１個又は複数個のプロセッサ１０１０、通信インタフェース１０１２並びにユーザインタフェース１０１４を、１本又は複数本の信号線１０２２によって相互接続した構成を有している。プロセッサ１０１０は例えば並列処理やマルチスレッド演算を実行し、通信インタフェース１０１２は例えば常時接続用のインタフェースであり、信号線１０２２は例えば通信バスを構成している。更に、ユーザインタフェース１０１４としてはディスプレイ１０１６、キーボード１０１８、ポインタ（例えばマウス）１０２０等の装置が用いられている。
【００７１】
本装置１０００のメモリ１０２４は、揮発性メモリ、不揮発性メモリ又はそれらの組合せによって実現されている。具体的には、ＲＯＭ(Read Only Memory)、ＲＡＭ(Random Access Memory)、ＥＰＲＯＭ(Erasable and Programable ROM)、ＥＥＰＲＯＭ(Electrically Erasable and Programmable ROM)、フラッシュメモリ、何枚かのスマートカード（商標）、何個かの磁気ディスク／ドライブ、何個かの光ディスク／ドライブ等から構成されている。メモリ１０２４に書き込まれている情報のうちオペレーティングシステム１０２６は、種々のハードウェアディペンデントタスクを実行すべく各種基本システムサービスの実行手順を定義する命令群によって構成されている。オペレーティングシステム１０２６としては例えばリアルタイムオペレーティングシステムを使用するとよい。メモリ１０２４には、更に、通信手順を定義する命令群が通信モジュール１０２８として格納されている。この通信手順を利用することによって、例えば本装置１０００に対して遠隔配置されているものも含め、何台かのコンピュータ、通信装置乃至サーバと通信することができる。
【００７２】
メモリ１０２４にはこれら以外にも様々なプログラムモジュール乃至命令群が格納されている。例えば予約モジュール１０３０やコンフリクト解消モジュール１０３２といったモジュール乃至命令群である。メモリ１０２４には、更に、本装置１０００と通信している通信装置のリスト１０３４、サブチャネル１０３８毎の予約状況１０３６等も格納されている。そして、メモリ１０２４に、リスト１０３４にある何台かの通信装置からの情報受信時刻をリストにした通信履歴１０４０を格納するようにしてもよいし、サブチャネルを利用したコンテンションフリー送信をスケジューリングする必要上時間同期が必要なコンテンションフリーチャネルアクセスプロトコルの場合は、同期情報１０４２等も格納しておくとよい（但しこれらはオプションである）。
【００７３】
メモリ１０２４に格納されているプログラムモジュール乃至命令群は、例えば手続指向プログラミング言語、オブジェクト指向プログラミング言語等の高級言語や、アセンブラ、マシン語等の言語によって記述されており、プロセッサ１０１０にて実行する際には適宜コンパイラ乃至インタプリタによってコンフィギュレーションされる。
【００７４】
なお、この図では、多数の機能要素が単一装置１０００に搭載されているかのように表記しているが、これは本装置１０００に搭載しうる機能要素の類例を表すためであり、本発明の実施形態を構造的に限定することを目的としたものではない。実際には、本件技術分野において相当程度の熟練を積まれた方々（いわゆる当業者）であれば理解できるように、装置１０００の構成要素として描かれている種々の機能要素は、多数のコンピュータ乃至サーバによって分担実行されるよう、それらのコンピュータ乃至サーバに分散搭載することもできる。また、本装置１０００の全機能又はその一部を何個かのＡＳＩＣ(Application Specific Integrated Circuit)、何個かのＤＳＰ(Digital Signal Processor)又はその組合せによって実現することもできる。
【００７５】
そして、本装置１０００の構成要素のうち一部を省略することや、図示されていない構成要素を本装置１０００に追加することや、何個かの構成要素を統合して１個にすることや、構成要素の配置を変更すること等も可能である。また、本装置１０００の機能のうちどれだけをハードウェア的に実現しどれだけをソフトウェア的に実現するかについても、本件技術分野に既存の知識を利用し適宜定めることができる。
【００７６】
次に、装置１０００にて使用しうるデータ構造について具体的に説明する。図１１は、本発明の一実施形態にて使用するデータ構造１１００の例を示すブロック図である。本データ構造１１００はサブチャネル毎の通信履歴１１００から構成されており、各通信履歴例えば第１サブチャネルについての通信履歴１１１０−１は、そのサブチャネルを現在予約している装置を特定する情報１１１２−１、データ量１１１４−１、荷重１１１６−１（加重平均を計算する場合）、データのスイッチングラテンシ１１１８−１等の情報から構成されている。但し、このデータ構造１１００は一例であり、図示した構成要素の一部を省略することや、別の構成要素を追加することや、複数種類の構成要素を統合して１個にすることや、各構成要素の順序を変えること等が可能である。
【図面の簡単な説明】
【００７７】
【図１】本発明に係る通信システムにて交換されるフレームの一例構成を示す模式図である。
【図２】本発明にて対策するチャネルアクセスプロトコル上の問題点を示すタイミングチャートである。
【図３】本発明の実施形態に係る予約法を説明するためのスケジュールリング図である。
【図４】本発明の実施形態に係る予約法を説明するためのスケジュールリング図である。
【図５】本発明の実施形態に係る予約法を説明するためのスケジュールリング図である。
【図６】本発明の実施形態に係る予約法を説明するためのスケジュールリング図である。
【図７】本発明の実施形態に係る予約法を説明するためのスケジュールリング図である。
【図８】本発明の実施形態に係る予約法を説明するためのスケジュールリング図である。
【図９】本発明の一実施形態に係る装置間通信手順を示すフローチャートである。
【図１０】本発明の一実施形態に係る通信装置の構成を示すブロック図である。
【図１１】本発明の一実施形態におけるデータ構造の例を示す模式図である。
【符号の説明】
【００７８】
１００  フレーム、１１０，１０３８  タイムスロット／サブチャネル、３００，４００，５００，６００，７００，８００  スケジュールリング、９００  装置間通信手順、９１０  フレーム送信ステップ、９１２  サブチャネル選択ステップ、９１４  サブチャネル予約ステップ、１０００  通信装置、１０３０  予約モジュール、１０３６  予約リスト、１１１４−１  データ量、１１１６−１  荷重、１１１８−１  スイッチングラテンシ。
【図１】
2008160846.tif 000009
【図２】
2008160846.tif 000010
【図３】
2008160846.tif 000011
【図４】
2008160846.tif 000012
【図５】
2008160846.tif 000013
【図６】
2008160846.tif 000014
【図７】
2008160846.tif 000015
【図８】
2008160846.tif 000016
【図９】
2008160846.tif 000017
【図１０】
2008160846.tif 000018
【図１１】
2008160846.tif 000019