(57)【要約】変化するトラフィック負荷に適応するため、無線ネットワークの単一ネットワーク装置によるスロット化リンクの使用量に優先順位を付ける方法であって、リンクを使用する優先順位の配分を所定の値に事前設定するステップと、現在のリンク使用量を監視するステップと、監視された使用量に応じて優先順位を適応させるステップと、を含む。
2004532555.tif 000002
【特許請求の範囲】
【請求項１】
変化するトラフィック負荷に適応するため、無線ネットワークの単一ネットワーク装置によりスロット化リンクの使用量に優先順位を付ける方法であって、
リンクを使用する優先順位の配分を所定の値に事前設定するステップと、
現在のリンク使用量を監視するステップと、
前記の監視された使用量に応じて前記優先順位を適応させるステップと、を含む方法。
【請求項２】
前記優先順位が異なるレベルの優先順位に分割される、請求項１に記載の方法。
【請求項３】
第１のレベルの優先順位がマスタとスレーブとを区別する、請求項２に記載の方法。
【請求項４】
第２のレベルの優先順位がリンクを使用する権限に関連する、請求項２に記載の方法。
【請求項５】
第３のレベルの優先順位が前記装置間の通信時間の配分に関連する、請求項２に記載の方法。
【請求項６】
前記ネットワークの２つの装置間の通信が交信スロットでのみ開始できる、請求項１に記載の方法。
【請求項７】
交信スロットの繰返し速度が調整可能であり、該交信スロットの繰返し速度が前記の監視されるリンク使用量に関連するよう調整される、請求項６に記載の方法。
【請求項８】
前記交信スロットの繰返し速度が２の乗算または除算によって変えられる、請求項７に記載の方法。
【請求項９】
優先順位の１つのレベルが最後に成功した交信以降の経過時間に関連する、請求項８に記載の方法。
【請求項１０】
通信関連データを１つの装置から別の装置に転送するステップをさらに含む、請求項１に記載の方法。
【請求項１１】
伝送に割り込む任意選択のステップを含む、請求項１に記載の方法。
【請求項１２】
各リンク使用量を監視する前記のステップが、
現在のスロット番号（Ｎslot）と、
交信イベントが完了したとみなされるそれ以降のスロットの量（Ｎcontact_timeout）と、
次の可能な交信のタイムスタンプ（Ｎnext_contact）と、の値を監視するステップを含む、請求項１に記載の方法。
【請求項１３】
各リンク使用量を監視する前記ステップが、
ピア装置と交信する優先順位が増大するそれ以降のスロットの量（Ｎmax_poll）と、
最終交信タイムスタンプ（Ｎlast_contact）と、の値を監視するステップをさらに含む、請求項１に記載の方法。
【請求項１４】
前記優先順位の適応が、スロット・アカウント（ｓ）とスロット・アカウントしきい値（ｍｉｎ＿ｓｅｒｖｅ）の適応を含む、請求項１に記載の方法。
【請求項１５】
前記スロット・アカウント（ｓ）が未使用スロット・アカウント（ｕｓ）によって拡張される、請求項１４に記載の方法。
【請求項１６】
２つの交信スロット（Ｎcontact）間の距離に関連するバックオフ・カウンタ（ｂ）の値を格納し適応するステップを含む、請求項１に記載の方法。
【請求項１７】
ネットワークのスロット化リンクの使用量に優先順位を付けるソフトウェア・ツールであって、該ソフトウェア・ツールがコンピュータまたはネットワーク装置上で実行される場合請求項１〜１６の何れか一項に記載の全てのステップを実行するソフトウェア・ツール。
【請求項１８】
ネットワークのスロット化リンクの使用量に優先順位を付けるコンピュータ・プログラムであって、該プログラムがコンピュータまたはネットワーク装置上で実行される場合請求項１〜１６の何れか一項に記載の全てのステップを実行するプログラム・コード手段を備える、コンピュータ・プログラム。
【請求項１９】
コンピュータ・プログラム製品であって、該プログラム製品がコンピュータまたはネットワーク装置上で実行される場合請求項１〜１６の何れか一項に記載の方法を実行する、コンピュータ可読媒体上に格納されるプログラム・コード手段を備えるコンピュータ・プログラム製品。
【請求項２０】
ネットワークのスロット化リンクの使用量に優先順位を付けることのできるネットワーク装置であって、
リンクを使用する優先順位の配分を所定の値に事前設定する手段と、
現在のリンク使用量を監視する手段と、
前記の監視された使用量に応じて現在のリンク使用量を適応させる手段と、を備えるネットワーク装置。
【請求項２１】
伝送関連データを格納する手段をさらに備える、請求項２０に記載のネットワーク装置。
【請求項２２】
入力データを格納する格納手段をさらに備える、請求項２０に記載のネットワーク装置。
【請求項２３】
請求項２０〜２２に記載のネットワーク装置を備えるネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はネットワークに関し、特に単一装置間の通信を行う無線ネットワークに関する。具体的には、本発明は、装置がスロット化ポイント・ツー・ポイントリンク上で通信するネットワーク・トポロジに関する。さらに具体的には、本発明は、１つの装置が多数の他の装置に接続でき、その際その１つの装置は一度に他の１つの装置としか通信できないネットワークに関する。
【背景技術】
【０００２】
従来のネットワーク、例えば、コンピュータ、プリンタ、モデム等といったマイクロプロセッサ制御式装置のネットワークは、ネットワーク内の装置間の物理的有線接続に依存していた。必要な接続の物理的性質のため、従来のネットワークは一般に、その性質上あまり柔軟性がないものと認識されている。例えば、さらなる装置をネットワークに追加するには、追加装置をネットワークに物理的に接続しなければならず、かつ追加装置が接続されたことをネットワーク・サーバに通知しなければならないこともある。
【０００３】
しかし、最近、無線ネットワークの出現が注目されており、そこではネットワーク接続は典型的には無線電波リンクによって提供される。こうしたネットワークの１つは様々なブルートゥース（Ｂｌｕｅｔｏｏｔｈ）標準に記載されている（例えば、ｈｔｔｐ：／／ｗｗｗ．ｂｌｕｅｔｏｏｔｈ．ｃｏｍ参照）。当業者が認識するように、他の無線ネットワークも存在しており、本出願でブルートゥースを参照しているのは本出願をそれに制限することを企図するものではない。
【０００４】
ブルートゥース無線技術によって、ユーザは、移動式電話、コンピュータ、プリンタ等といった様々な通信機器間の容易な、無線による即時接続を行えるようになる。ブルートゥース技術は短距離無線接続性を提供し、ポイント・ツー・ポイント及びポイント・ツー・マルチポイント両方の接続をサポートする。現在では、７つまでの動作状態の「スレーブ」装置が「マスタ」装置と通信でき、「ピコネット」を形成する。こうしたいくつかの「ピコネット」を設けて臨時の「スキャターネット」として互いにリンクすることができ、常に柔軟な構成の中での通信が可能になる。
【０００５】
ピコネット及びスキャターネットの無線という性質のためと、出費を最小化するため、無線ネットワーク装置の大部分はデータ送受信機を１つだけ含む。従って、ネットワーク装置は一度に１つの他ネットワーク装置としか通信できない。１つのマスタと７つまでの動作状態スレーブを有するピコネット内では、ほぼ最適なデータ転送を実行するため特別なスケジューリング処理を使用する必要はない。これは、マスタは普通最大の計算機能力を有する装置であり、スレーブは普通マスタ装置の周辺装置アプリケーションであるという事実による。このトポロジでは、マスタの通信が最適化されると、総合通信性能が最適化される。スキャターネットのレベルでは、総合通信性能は他のパラメータに依存する。スキャターネットでは、１つのネットワーク装置はマスタまたはスレーブという役割に固定されるのではなく、リンクの中のあるものに対してはマスタとなり、同時にリンクの中の他のものに対してはスレーブとなることができる。従って、優先順位または伝送時間の任意または均一な配分は常に部分最適であると予想できる。
【０００６】
「複数ピコネットへの同時接続性」に関するＷＯ  ９９／１４８９８のような、ピコネット間の接続に関する従来の解決策は、特定のブルートゥース低電力モードとネゴシエーション期間の利用に基づくものであるため、例えば、パラメータ・ネゴシエーションに起因する通信オーバヘッドといった、ある対応する制限内で機能するよう制約されていた。さらに、周期的な挙動を想定したため、変化するトラフィック負荷とトポロジに対する適応性は最小に制限されていた。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
スロット化ネットワークの構築に伴う問題の１つは、総合通信性能を最適化することである。
【０００８】
スロット化ネットワークの構築に伴う別の問題は、ネットワーク装置は移動可能であるので、リンクにかかるトラフィック負荷は各ネットワーク装置の位置によって変化するという事実である。
【０００９】
スロット化ネットワークに関する別の問題は、利用可能な通信時間を公平な形で共有することである。
【課題を解決するための手段】
【００１０】
本発明の第１の態様によれば、変化するトラフィック負荷に適応するため、無線ネットワーク中の単一ネットワーク装置によりスロット化リンクの使用量に優先順位を付ける方法であって、リンクを使用する優先順位の配分を所定の値に事前設定するステップと、現在のリンク使用量を監視するステップと、監視された使用量に応じて優先順位を適応させるステップとを含む方法が提供される。優先順位の配分を事前設定することによって、リンクを使用するリンク間の優先順位の均一な配分を選択できる。さらに発達したネットワークでは、装置は、事前に最適化された優先順位配分によって開始される、前の期間中に得られた前の平均値の平均優先順位配分を格納してもよい。現在のリンク使用量を監視することによって、ネットワーク装置は現在の優先順位配分が最適か否かを自ら検出することができる。監視された使用量に応じて優先順位を適応させることによって、ネットワーク装置は自らローカル通信性能を適応させ最適化することができる。
【００１１】
本発明の基本的な概念は、各ネットワーク装置のローカル通信性能を最適化することによって、総合通信性能を増大することである。スロット化リンクは普通、パケットでデータを伝送し、それぞれ１つのスロットまたはいくつかのスロットに収まる。少なくとも３つの異なる種類のパケットを区別しなければならない。第１に、通常のデータ・パケットが存在するが、これは付加制御情報を伝送することもある。第２に、送信すべきデータを持たない装置によって送信される、データのないいわゆるＮＵＬＬパケットが存在する。第３に、データを伝送しないが論理（Ｂｏｏｌｅａｎ）フラグ（再配分フラグ）を提供するいわゆるＡＢＯＲＴパケットが存在する。ＡＢＯＲＴパケットは交信（ｃｏｎｔａｃｔ）の最後に使用してもよい。ＡＢＯＲＴパケットを使用して単一リンクまたはネットワーク装置の優先順位を適応させることができる。
【００１２】
優先順位は異なるレベルの優先順位に分割されることが好ましい。異なるレベルの優先順位によって、異なる態様の通信を考慮し、異なる最適化戦略を使用して異なるネットワーク状況に適応することができる。
【００１３】
第１のレベルの優先順位はマスタとスレーブとを区別することが有益である。例えば、主要な伝送方向が全体的に反転するようなほぼ線形のネットワーク構造の場合、バイナリー・バージョンのマスタ／スレーブ概念で十分なことがある。単一ネットワーク装置が１つより多いマスタに接続できる相互接続を伴う柔軟なネットワーク・トポロジでは、バイナリーのマスタ／スレーブ概念は不十分である。相互接続ネットワーク構造では、段階的マスタ／スレーブ概念が適用できるが、そこではスレーブがより高い順位のマスタからの命令によって占有されている場合、スレーブは別のマスタからの命令を拒否できる。ポイント・ツー・ポイントリンクのネットワークでは、単一のネットワーク装置はリンクの各末端でマスタ／スレーブの値について合意しなければならない。この概念はローカルなマスタ／スレーブ規定または広域のマスタ／スレーブ規定と関連していてもよい。広域のマスタ／スレーブ規定は、スレーブ装置がどの命令を遵守すべきか決定できないという状況を防止できる。ローカルなマスタ／スレーブ規定によって、ネットワークは、トポロジの変化といった異なるネットワーク条件に柔軟に応じることができるようになる。スキャターネットは、現在のブルートゥースの単一ピコネット・トポロジの拡張である。それは、時分割多重方式によって複数のピコネットに参加するブルートゥース装置によって可能になっており、スキャターネット・サポートをブルートゥース技術に追加している。これはスニフモードと非常によく似ているが、スキャターネット・モードは電力節約を第１の目的とするものではない。しかし、それは、ピコネット間多重化によって発生する空き期間がある場合、複数ピコネット参加（ＰＭＰ）装置が電池電力を節約できるように設計されている。スキャター・モードのブルートゥース装置は異なるピコネットで異なる役割を有することができる。スキャター・モードは、ピコネット間の切換が時分割多重方式で容易にできるよう設計されている。この方法はマスタ／スレーブの役割割り当てとは無関係に適用される。
【００１４】
優先順位のレベルはリンクを使用する優先順位に関連することが好都合である。リンクを使用する段階的優先順位によって、バイナリーのマスタ／スレーブ概念を段階的マスタ／スレーブ概念に拡張できる。ポイント・ツー・ポイントリンクの場合、リンクを使用する権限は、リンクのもう一端のネットワーク装置より高い優先順位と同等である。
【００１５】
第３のレベルの優先順位は前記装置間の通信時間の配分に関連することが好ましい。装置間の通信時間に関連する優先順位によって、単一ネットワーク装置間の通信の最適化を向上する追加パラメータを導入できる。時分割二重（ＴＤＤ）転送モードでは、帯域幅または転送速度といった他の転送パラメータは普通変化しない。他の転送モードでは、帯域幅、変調等といった他の転送パラメータも変化しうる。スロット化通信方式を使用する通信リンクでは、スロット長が変化しうる。
【００１６】
通信時間は、連続して使用されるスロットの数として規定できる。固定長スロットによるスロット化通信方式を使用するネットワークでは、可変通信時間は、１スロット長の倍数の不連続なステップにおいてのみ変更できる。通信時間は、端末装置が連続して使用できるスロットの数を規定するスロット・アカウントｓの値でスケジューリングできる。
【００１７】
ネットワークの２つの装置間の通信は交信スロット（ｃｏｎｔａｃｔ  ｓｌｏｔ）でのみ開始できることが好都合である。交信スロットを使用することによって、単一のマスタ／スレーブ装置の対は、交信が開始できる時間を規定する。通信リンクのマスタは、データまたはパケットを送信することによって、交信スロットの中でスレーブ装置を自由にアドレス指定することができる。スレーブはこのスロットで開始されるパケットをリスニングし、パケットを送信することによって応答すればよい。そのようにすれば、交信イベントが開始される。装置のうち１つだけが特定の交信スロットを使用しようとするならば、装置は不首尾な交信試行を行うことになるだろう。交信イベントを確立するため交信スロットを使用しない装置は、例えば、別の交信イベントまたは他の通信リンクの交信スロットといった、何らかの他の目的のために、このスロットを自由に使用できる。基本的に、どの交信スロットも交信イベントを開始するために使用できる。しかし、現在の交信イベントを続行するために、いくつかの交信スロットをスキップすることが必要かつ妥当なことがある。従って、交信スロットは、スロット・アカウントと呼ばれる、次に来る交信スロットの優先順位を決定する１つのパラメータを備える。交信スロットの使用を考慮する場合、区別しなければならない２つの場合が存在する。本方法におけるスケジューリングは、通信の不確実性に対処するよう特に設計されており、これは、成功した通信の量を監視し、それに応じて使用する交信スロットと交信イベント長を適応させる優先順位概念の提案に帰結している。
【００１８】
装置が参加している、現在動作状態にある交信イベントが存在しなければ、次に来る交信スロットが使用可能である。現在交信イベントが存在する場合、現在使用されている通信リンク以外の通信リンクの次に来る交信スロットが現在の交信イベントの割り込みをトリガしてもよい。そのようにするには、新しい通信リンクのスロット・アカウントｓnewが、現在の通信リンクのスロット・アカウントｓcurrentをあるしきい値だけ超えなければならない。このしきい値は、前の及び現在の通信リンクのｍｉｎ＿ｓｅｒｖｅ値の最大値として規定してもよい。すなわち、ｓnew−ｓcurrent  ｍａｘ（ｍｉｎ＿ｓｅｒｖｅcurrent、ｍｉｎ＿ｓｅｒｖｅnew）という数式が成り立たなければならない。異なる通信リンクのいくつかの交信スロットが同時に出現することが起こりうる。この場合、どの通信リンクの交信スロットを使用するよう選択するかを決定する優先順位方式を考案しなければならない。
【００１９】
交信スロットの繰返し速度は可変であり、繰返し速度は監視されるリンク使用量に関連するよう調整されることが好ましい。双方の装置が送信すべきデータを持たないため、交信試行が成功した直後に交信イベントが終了するということが起こりうる。その交信試行のために使用された２つのスロットは事実上失われるので、この種のイベントの発生を最小化することが望ましい。さらに、不成功な交信試行の数を少なく保つことはきわめて重要であり、これはそうしなければ交信イベントが不必要に打ち切られてしまうことになるからである。
【００２０】
すなわち、このような通信リンクでの交信試行の数を減らすことが好適なことがある。そのため、通信リンク毎にバックオフ・カウンタが用意される。このカウンタはあるイベントの際に増減する。バックオフ・カウンタの値が高いのは、交信スロットが発生する頻度が低いことを意味する。バックオフ・カウンタは、スロット番号の値が、最終交信についての所定の値を最大ポーリングの値だけ超えていない通信リンクについてのみ有効であることに注意のこと。装置がある通信リンクについて行った交信イベントが不成功だった場合、この通信リンクのバックオフ・カウンタは増やされる。
【００２１】
交信スロットの前記繰返し速度は２の乗算または除算によって変化することが好都合である。このアプローチは特に、あるピアが別のピアとは別のバックオフ・レベルを選択する場合に対応している。これは、その後の交信スロット間の距離を２だけで乗算または除算することによって得られる。従って、高い方のバックオフ・レベルの交信スロットは常に、低い方のレベルの交信スロットの部分集合である。他の乗数も可能であるが、さらに大きな乗数を使用するのは、最高及び最低パラメータ間の段階が大まかになりすぎるという欠点を有する。１〜５１２通信スロットの範囲の場合、乗数２は１０の異なる段階を提供するが、乗数３は６段階しか提供しない。乗算は両端で制限されるべきであることに注意のこと。下限は、最小通信が１つのスロットを含むことから例えば１＝２0でよく、上限は「ワインドアップ（ｗｉｎｄ  ｕｐ）効果」を防止するため例えば５１２＝２9でよい。例えばバックアップ・カウンタが６４に設定されている場合、「ワインドアップ効果」は例えば乗数２について発生し、アサートされたスロット・アカウントを実行するには数百年を要するだろう。
【００２２】
優先順位の１つのレベルは最後に成功した交信以降の経過時間に関連することが有益である。２つの装置間のリンクの優先順位は最終交信以降の経過時間と共に増大すればよい。これは、最終交信以降の経過時間を優先順位に適応させ、低い交信頻度が高い優先順位を有することの欠点を考慮に入れる。単一の装置がネットワークに通知しない状態に置かれることを防止するため、または単一ネットワーク装置が蓄積するデータが多くなりすぎるのを防止するため、所定の時間間隔が合意され、それ以降は交信スロットの優先順位を最大値に設定または少なくとも増大するようにする。これはバックオフ・カウンタの「ワインドアップ」を防止するが、それが意味するのは、２つの交信スロット間の距離がネットワーク・ユーザに注目されるということである。従って、現在の交信イベントは、スロット番号の値が最終交信について所定の値を最大ポーリングの値だけ超えている通信リンクの交信スロットの使用によって打ち切ってもよい。最終ステップでは、現在の交信イベントを打ち切って次に来る交信スロットを使用する装置は、適当な値の再配分フラグ（新しい通信リンクのスロット番号が最大ポーリング値を超えていればＦＡＬＳＥ、さもなければＴＲＵＥ）を有するＡＢＯＲＴパケットを送信することで現在のピア装置に通知してもよい。
【００２３】
通信関連データは１つの装置から別の装置に転送されることが好都合である。周波数ホッピング伝送アルゴリズムを使用する場合、これはホップ・シーケンスまたはその計算のために使用されるデータでよい。通信関連データは必要な送信電力、例えば電波接続で使用される伝送装置の場合電力節約モードに関連付けできる。通信関連データは転送速度に関するデータを備えてもよい。さらには、移動式コンピュータ等のような完全移動式端末装置の場合、予想残り動作時間に関する情報を含んでもよい。情報は、次の伝送の予想長さ、次の伝送の予想優先順位、またさらには高い優先順位を有する次の伝送の予想時間を備えてもよい。
【００２４】
優先順位を付ける本方法はさらに、特に低い優先順位の伝送に割り込む任意選択のステップを含むことが好ましい。特にデータ伝送ネットワークでは、優先順位は、第１のレベルでは、現在の伝送の終了後データ伝送リンクにアクセスする優先順位を含む。第２のレベルの優先順位は装置が低い優先順位の現在の伝送に割り込みできるようにする。例えば、スレーブがポーリングに応答しない状況にマスタが対処する場合が考えられるが、これは、無線ネットワークでは、例えばスレーブ装置の位置変化によって容易に発生しうる。従って、マスタ装置は、他のスレーブまたはマスタ装置を現在のリンクに追加またはそこから削除するアルゴリズムを必要とする。単一の装置が現在のリンクから削除され、ある期間の後再び追加しなければならなくなるのを防止するためには、優先順位を最終交信以降の経過時間に関連付ければよい。従って、単一のスレーブ装置を現在の伝送期間中に削除する場合、時間のかかる再追加手順を避けるためには、前記装置の優先順位を最大値に設定して現在の伝送に割り込み、マスタ装置と交信してリンクからの削除を防止すればよい。
【００２５】
伝送の打ち切りは、例えば、第１の装置が第２の装置のスレーブであり、第２の装置が同時に第３の装置のスレーブであるような線形ツリー装置サブネットワークの場合有用である。このサブネット構造では、第３の装置は、第１の装置への長いデータ通信によって占有されている場合、第２の装置にアクセスしなくてもよい。第３の装置による第２の装置への通信が阻止されるのを防止するため、第２の装置は第１と第２との装置の間のデータ伝送を打ち切ることができる。現在の伝送の割込みはＡＢＯＲＴパケットによって実行すればよい。ＡＢＯＲＴパケットは、出所の不明なＡＢＯＲＴパケットが現在の伝送に割り込みするのを防止するため、ある装置の特定のアドレスと発信者を含んでもよい。
【００２６】
各リンクに優先順位を付けるステップは、現在のスロット番号（Ｎslot）と、それ以降交信イベントが完了したとみなされるスロットの量（Ｎcontact_timeout）と、次の可能な交信のタイムスタンプ（Ｎnext_contact）との値を監視し適応させるステップを含む。
ロール（ｒｏｌｅ）の値は、マスタＭとスレーブＳとを最も簡単な方法で区別する。ロールは主に、命令が転送される通信リンクの方向を規定する。これは２つのネットワーク装置間の第１のレベルの優先順位付けである。ネットワークはスロット化ネットワークであるが、このことは伝送が時間離散的であることを意味する。スロットは時分割二重（ＴＤＤ）転送モードの転送単位と同じ長さでよい。特に周波数ホッピング・アルゴリズムを使用する他の転送モードと組み合わせて、スロットは、そのアルゴリズムが単一の周波数を使用する時間と同じ長さでよい。データ伝送が実行可能なあるスロットを規定するため、スロットに番号を付ける。この番号がスロット番号Ｎslotである。マスタとスレーブとはＮslotの実際の値について合意し、双方のシステムが互いに通信できるようにしなければならない。一部のスロットは通信を開始するために使用でき、そうしたスロットは交信スロットＮcontactと呼ばれる。交信スロットを使用することで、単一のマスタ及びスレーブ装置の対は、交信が開始できる個々の時間を規定できる。双方の装置は同じアルゴリズムを使用して次のＮcontactを計算する必要がある。１つのＮcontactで次のＮcontactの位置の伝送に失敗すると、システムは回復する機会を持たないため、各ＮcontactでＮnext_contactを転送するだけでは不十分である。そこで、システムは、Ｎnext_contactを計算できるアルゴリズムを必要とする。各通信リンクは自己の交信スロットと、交信スロットを計算する方法とを有してもよい。さらには、異なる通信リンクの交信スロットは完全に無関係であってもよい。すなわち、異なる通信リンクの交信スロットが互いに重なることも起こりうる。
【００２７】
ある特定の通信リンクのマスタとスレーブが、その通信リンクについて次の交信スロットとして同じものを決定する確率は高い。そのため、双方の装置が互いに通信したい場合、マスタとスレーブとが交信イベントを開始することが保証される。提案されたバックオフ機構を使用する場合、特に注意を払わなければならない。この機構は、２つの装置がある制限された時間の後で接触できるよう適切に選択されなければならない。交信スロットを決定する簡単な方法は、それらの所定のスロット設定において等距離に配置することである。この場合、２つのパラメータＮinter_contact及び０  Ｎcontact_offset＜Ｎinter_contactが規定される。第１のパラメータは２つの交信スロット間の距離を規定し、第２のパラメータはスロット設定における相対的配置を規定する。Ｎslotｍｏｄ  Ｎinter_contact  ＝  Ｎcontact_offsetの場合、スロット番号Ｎslotを有するスロットが交信スロットである。Ｎnext_contactを見出さなければならない場合、この数式を満たす現在のスロット番号以後の最小スロット番号を選択する。通常の配置での最も簡単な事例はＮinter_contactを１に設定し、Ｎcontact_offsetを０に設定することによって得られる。
【００２８】
さらに、双方の装置は伝送の推定長さに関するデータを格納できる。従って、双方のネットワーク装置には実際の伝送がどのくらい続くかが分かっている。
各スロットでは、データまたは他の情報を含むパケットが転送できる。１つより多いスロットを使用する長いパケットも可能である。３つの異なる種類のパケットを区別しなければならない。第１に、普通のデータ・パケットが存在するが、これは付加制御情報を伝送することもある。第２に、送信すべきデータを持たない装置によって送信される、データのないいわゆるＮＵＬＬパケットが存在する。第３に、データを伝送しないが論理フラグ（再配分フラグ）を提供するいわゆるＡＢＯＲＴパケットが存在する。ＡＢＯＲＴパケットは交信イベントの最後に使用してもよい。
通信リンクの両側で同じ交信スロットを使用することによって、２つの装置間の交信イベントが確立された後、２つの装置は交信イベントが終了するまでデータを交換し続ける。双方の装置はいつでも現在の交信イベントの終了を決定してもよい。
ピア装置Ａ及びＢが通信リンク上で交信イベントを行っている時、装置Ａは装置Ｂに通知せずに現在の交信イベントの終了を決定し、別の装置との交信イベントを開始してもよい。装置Ｂは相手装置が去ったことに気付かないので、タイムアウトの後、すなわち現在のスロット番号ＮslotがＮlast_contactをしきい値Ｎcontact_timeoutだけ超えた時この交信イベントを終了する。交信イベントの暗黙的な終了がスロットの再配分をトリガすることもある。
【００２９】
交信イベントの明示的な終了には３つの可能性が存在する。第１には、ＡＢＯＲＴ制御パケットの受信である。交信イベントを終了する装置はＡＢＯＲＴ制御パケットを送信してそのピアに通知してもよい。すなわち、ＡＢＯＲＴパケットを受信した装置は即座に現在の交信イベントが終了したものとみなす。ＡＢＯＲＴパケットの再配分制御フラグの状態に応じて、受信装置側でスロットの再配分を開始してもよい。第２には、２つのＮＵＬＬの連続である。通信リンクの双方の装置の待ち行列が空になると、装置はＮＵＬＬパケットを送信する。次に、スレーブがマスタのＮＵＬＬパケットにＮＵＬＬパケットで答えた後、双方の装置は即座に現在の交信イベントが終了したものとみなす。２つのＮＵＬＬの連続の場合、スロットの再配分は双方の装置側でトリガされてもよい。第３には、より高い優先順位を有する別の交信イベントの開始である。また、次のスロットで別の通信リンクの交信スロットを使用するので、装置は現在の交信イベントを終了してもよい。通信リンクのピア装置は、交信イベントの終了に明示的（ＡＢＯＲＴパケットがピア装置に送信される場合）または暗示的（その種のパケットが送信されない場合）の何れかの形で気付くことになる。
【００３０】
ネットワークのスロット化リンクに優先順位を付ける方法はさらに、それ以降ピア装置と交信する優先順位が増大するスロットの量（Ｎmax_poll）と最終交信タイムスタンプ（Ｎlast_contact）とを格納するステップを含むことが好都合である。ＮslotとＮlast_contactの値によって、装置は最後に成功した交信以降の時間を計数または計算することができる。優先順位が低くデータ転送速度も低い装置は常に、ネットワークとの接触を失う、すなわちネットワークがリンクまたは装置を「忘れてしまう」ことの危険にさらされている。これを防止するため、最後に成功した交信以降あまりに多くの時間が経過した場合、ネットワーク装置の優先順位を増大する。伝送がなかったので、マスタ及びスレーブの双方は同じアルゴリズムを使用してリンクの優先順位を増大しなければならない。Ｎmax_pollに達した場合は、優先順位を段階的に増大するか、または最大に設定してもよい。
【００３１】
優先順位の適応には、スロット・アカウント（ｓ）とスロット・アカウントしきい値（ｍｉｎ  ｓｅｒｖｅ）の適応が含まれることが好ましい。スロット・アカウント設定（ｓｌｏｔ  ａｃｃｏｕｎｔｉｎｇ）は普通、各スロットの冒頭で行われる。１つの装置上でいくつかの異なる規定のスロット・タイミングが存在する場合、１つを基準タイミングとして選択する。スロット・アカウント設定は、基準タイミングで各スロットの冒頭でなされる。ただし、必ずしもこのタイミングを使用して最終パケットを送信または受信するわけではない。従って、パケットが現在送信または受信されている通信リンクのスロットの各冒頭で、通信リンクにタグが付けられる。各基準スロットの冒頭で、タグ付き通信リンクは最終送信／受信スロットについてアカウント設定される、すなわち、そのスロット・アカウントは１だけ減らされる。タグはアカウント設定の後除去される。
【００３２】
スロット・アカウントを使用して交信イベントをスケジューリングしスロットを再配分することによって通信時間の公平な配分を達成する方法が最も好ましい。これによってスロット・アカウント値の再配分は容易に得られる。
【００３３】
ネットワークのスロット化リンクの使用量に優先順位を付ける方法は、スロット・アカウント（ｓ）を未使用のスロット・アカウント（ｕｓ）によって拡張するステップを含むことが好ましい。アカウント設定時に、どの装置にもタグが付けられないということが起こりうる。この場合、未使用のスロット・アカウント（ｕｓ）をアカウント設定する。各スロットの冒頭で、各装置での１つの通信リンクのスロット・アカウントは１だけ増大される。しかし、未使用スロットのアカウントｕｓが０以下の場合、このアカウントを１だけ増大しなければならず、他のアカウントは増大しない。
【００３４】
アカウントは、通信リンクがスロットの全体量から得るべき望ましい割り当てに比例して増大すべきである。全ての通信リンクが平等に扱われる最も単純な場合では、全てのアカウントは（長期的には）スロットの等しい割り当てを得る。これを達成するアプローチでは、アカウントはラウンドロビン方式で増大される。
最終スロットの期間に何かが送信または受信された場合、転送に使用された通信リンクのスロット・アカウントが減らされる。最終スロットの期間に何も送信または受信されなかった場合、未使用スロット・アカウントｕｓは１だけ減らされる。その結果、各装置において、スロットの冒頭で増大及び減少操作が行われた後、通信リンクについての未使用スロット・アカウントと全てのスロット・アカウントとの合計は常に０である。過去において割り当てられた取り分より多いスロットを使用したピア装置は負のスロット・アカウントを有し、過去において割り当てられたスロットを使い切らなかったピア装置は正のスロット・アカウントを有することになる。アルゴリズムによって補償される不公正の量を制限するため、スロット・アカウントの最大及び最小値を制限することが望ましい。スロット・アカウントは、最大値に達すると、スロットの冒頭で増やす対象になることはできない。最小値に達したスロット・アカウントを減らす代わりに、未使用スロット・アカウントｕｓを減らせばよい。スロットを通信リンクに公平に割り当てるため、提案されたスケジューリング機構は、交信イベントを適切にスケジューリングしかつスロットを再配分することによって、スロット・アカウントのバランスを取ろうとする。
【００３５】
一般に、スロットの再配分は、現在の通信リンクのスロット・アカウントからある量のスロットを取り、それを他の通信リンク間で配分する。全ての通信リンクが平等に扱われる最も単純な場合では、スロットは他の通信リンク間で均等に配分される。もちろん、全てのスロット・アカウントとｕｓの合計は０である。
配分すべきスロットの量は様々な方法で計算できる。１つの選択肢は全ての正スロット・アカウント値を配分することである（すなわち、再配分の後スロット・アカウントは０になる）。もう１つの方法は、残りの通信リンク間でスロットを均等に配分した後現在の通信リンクのアカウントの値が最も低いスロット・アカウントに等しくなるようにスロットを配分することであろう。この場合、配分すべきスロットの量は、
（ｓcurrent−ｓmin）＊（ｎ−１）／ｎ
によって与えられるが、ここでｓcurrentは現在の通信リンクのアカウントの値であり、ｓminは最低アカウントの値であり、ｎは装置の通信リンクの数である。ｓcurrent＞ｓminの場合、クレジット（ｃｒｅｄｉｔ）だけが配分されることに注意されたい。
【００３６】
ネットワークのスロット化リンクの使用量に優先順位を付ける方法はさらに、２つの交信スロットＮcontactの間の距離に関連するバックオフ・カウンタ（ｂ）の値を格納し適応させるステップを含むことが有益である。双方の装置が送信すべきデータを持たないため、交信試行が成功した直後に交信イベントが終了するということが起こりうる。その交信試行のために使用された２つのスロットは事実上失われるので、この種のイベントの発生を最小化することが望ましい。さらに、不成功な交信試行の数を少なく保つことはきわめて重要であり、これはそうでなければ交信イベントが不必要に打ち切られるからである。
従って、このような通信リンクでの交信試行の数を減らすことが好ましいことがある。そのため、通信リンク毎にバックオフ・カウンタが用意される。このカウンタはあるイベントの際に増減する。バックオフ・カウンタの値が高いのは、交信スロットが発生する頻度が低いことを意味する。バックオフ・カウンタは、Ｎslotの値がＮlast_contactをＮmax_pollの値だけ超えていない通信リンクについてのみ有効である。
【００３７】
バックオフ・カウンタｂと交信スロットの等距離配置とが実現されている場合、
Ｎslotｍｏｄ２bＮinter_contact＝Ｎcontact_offset
であればＮslotは交信スロットである。
【００３８】
装置がある通信リンクについて行った交信イベントが不成功だった場合、この通信リンクのバックオフ・カウンタは１つ増やされる。バックオフ・カウンタの他の規定も可能である。
【００３９】
本発明の別の態様によれば、ネットワークのスロット化リンクの使用量に優先順位を付けるソフトウェア・ツールであって、前記ソフトウェア・ツールがコンピュータまたはネットワーク装置上で実行される場合先行する方法請求項の何れか一項に記載の全てのステップを実行するプログラム・コード手段を備えるソフトウェア・ツールが提供される。
【００４０】
本発明の別の態様によれば、ネットワークのスロット化リンクの使用量に優先順位を付けるコンピュータ・プログラムであって、前記プログラムがコンピュータまたはネットワーク装置上で実行される場合先行する方法請求項の何れか一項に記載の全てのステップを実行するプログラム・コード手段を備えるコンピュータ・プログラムが提供される。
【００４１】
本発明のまた別の態様によれば、コンピュータ・プログラム製品であって、前記プログラム製品がコンピュータまたはネットワーク装置上で実行される場合先行する方法請求項の何れか一項に記載の方法を実行する、コンピュータ可読媒体上に格納されるプログラム・コード手段を備えるコンピュータ・プログラム製品が提供される。
【００４２】
本発明のまた別の態様によれば、ネットワーク装置であって、ネットワークのスロット化リンクの使用量に優先順位を付けることができ、リンクを使用する優先順位の配分を所定の値に事前設定する手段と、現在のリンク使用量を監視する手段と、監視された使用量に応じて優先順位を適応する手段とを備えるネットワーク装置が提供される。この装置によって、所定の優先順位配分で最適化を開始することができる。開始の配分は、常に、例えば最後に使用された配分によってＲＯＭ（読み出し専用メモリ）に格納された同じものであってもよく、あるいは最適化処理のため最適な開始の配分を見出すため最適化処理の点で異なってもよい。
【００４３】
ネットワーク装置は伝送関連データを格納する手段を備えることが好都合である。そのデータは、装置がそれぞれのリンクに対するスレーブまたはマスタであるかを決定するロールの値と、スロット番号Ｎslotの値と、Ｎmax_pollの値と、Ｎinter_contactの値と、Ｎnext_contactの値の計算する基礎を形成するＮcontact_timeout及びＮcontact_offsetと、Ｎlast_contactと、スロット・アカウントｓと、未使用スロット・アカウントｕｓと、バックオフ・カウンタｂとを備えてもよい。計算値の中には格納しなければならないものもある。
【００４４】
ネットワーク装置はさらに、入力及び出力データの格納手段を備えることが好ましい。格納手段はデータ待ち行列またはコンピュータで使用される他の格納装置でよい。ネットワーク装置はデータを同時に受信し送信することができないため、メモリはネットワーク装置の重要な部分である。簡単で瞬時に実行可能な命令を処理する場合格納装置は必要ない。データ伝送は長くかかることがあり、割り込み不能なこともある。伝送は複数のスロットを占有することもあるので、ある交信スロットに入るため進行中の伝送の割り込みが必要なことがある。これは送信側と同様受信側でも起こりうる。伝送の割り込みができない状況もありうる。この制約に対処するため、交信スロットの使用は事前に計画しなければならない。もちろん、将来見込まれるスロットの数は伝送の最大長（スロットを単位として計数された）に依存する。さらに、ピア装置の伝送の長さを制限する必要があることもある（例えば、それぞれの制御データを普通のデータ・パケットに添付することによって）。データ受信速度が印刷速度よりはるかに大きいプリンタの場合のように、非スロット同期方式で動作する装置の場合格納手段を提供しなければならない。例えば、外部ランダムアクセス・メモリ装置では、データ・アクセスとデータ伝送との間の時間遅延なしに、装置がスロット同期方式で動作するように、別個のデータ待ち行列を設置しなければならない。
【００４５】
本発明のさらなる態様によれば、先行するネットワーク請求項に記載のネットワーク装置を備えるネットワークが提供される。こうした「全無線」ネットワークはその構造上非常に柔軟で自己編成的である。建築物内約１０ｍを範囲とし事務室の推定容積を約４０ｍ3とすると、３０までの他の事務室が１つのネットワーク装置の範囲内となりうる。７つまでのネットワーク装置を想定すると、２００までの装置が１つの単一無線ネットワーク装置のアクセス可能範囲内となりうる。従って、こうしたネットワーク装置間の転送が最適化される。
【００４６】
スキャターネットでは、産業スパイ行為を防止するため、スキャターネットの特別な対策及び監視を行わなければならない。従って、各スキャターネット装置は、スキャターネットに参加する全ての装置にそれが行えるようにする認証及び暗号化を備えてもよい。しかしこれは、スキャターネットへの直接アクセスを複雑にすることがある。１０〜１００ｍの範囲を有するスキャターネットでさえ、指向性アンテナを使用することによって、さらに長い距離から傍受されることもある。認証を生成する１つの選択肢として、ＳＩＭ（加入者識別モジュール）を使用してシステム・アクセスを保証してもよく、その場合ユーザは、電子キーとして着脱式のＳＩＭを自分の個人用装置に挿入した場合だけネットワークへのアクセスが得られる。ＳＩＭ概念を使用して広域の段階的マスタ／スレーブ概念を規定してもよい。
以下、本発明は添付の図面を参照して詳細に説明される。
【発明を実施するための最良の形態】
【００４７】
図１は、装置１〜６と、装置１〜６間の通信リンクとからなるトポロジを示す。通信リンクはポイント・ツー・ポイントであり、関係している２つの装置間でデータまたは制御パケットを交換するために使用される。通信リンクに参加する２つの装置の一方はリンクのマスタＭであり、もう一方はスレーブＳである。ある装置１〜６が特定の通信リンクに適応させるマスタＭまたはスレーブＳの役割は、装置１〜６の他の通信リンクとは無関係である。トポロジの接続に対するマスタ／スレーブの役割の割り当ては事前に行われる。図１はこのようなトポロジの一例を示す。
【００４８】
図２は、本発明によるネットワークのノードを示す。装置４はその時点で通信リンク上の他の１つの装置とだけ通信できる（装置５だけを図示する）。いくつかのリンク４３、４５、４６上で通信するため、装置は、時分割多重方式を使用して通信リンク４３、４５、４６の間で切換を行わなければならない。通信リンク４５上の２つの装置４、５の間の通信は、双方の装置が同時に同じ通信リンク４５を使用している場合のみ可能である。
【００４９】
２つの装置４、５が通信リンク４５上で互いに通信する場合、通信リンク４５のマスタ装置４は通信パラメータ（例えば、タイミング、スロット番号、周波数等、一部を枠内で図示する）を決定し、スレーブ装置５はそのパラメータに適応する。装置はスロット化通信方式を使用する。マスタ装置４は通信リンク４５上のスロット設定を決定する。提案された優先順位付け方法の説明を簡単にするため、スロットはネットワーク全体を通じて整合されていると想定する。スロットを識別するため、マスタ装置４はスロット番号Ｎslotを各スロットに割り当てる。スレーブ装置５には、スロット番号Ｎslotを含むマスタ装置４の通信パラメータが分かっていると想定する。スレーブ装置５は、マスタ装置４がそれをポーリングする場合のみパケットの送信を許可される。これは通常のデータ・パケット、またはデータを含まない制御パケット（いわゆるＮＵＬＬパケット）を使用して起こりうる。スレーブ装置５は、何らかのパケット（データを含むかまたは含まない）を送信することによってマスタ装置４の全てのパケットに応答する必要がある。１つより多いスロットを使用するパケットも可能である。各リンクのマスタは、リンクの通信パラメータと優先順位パラメータ（Ｍ／Ｓ、Ｎinter_contact等の値）とを規定する。
【００５０】
図３は、異なるスロット・タイミングによるスロット・アカウント設定のタイミング図を示す。現在まで、ネットワークの全ての装置は同じスロットの規定を使用していると想定していた。以下では、マスタ毎に異なるスロットの規定をサポートするために、提案された機構に対して行わなければならない適応を紹介する。ただし、スレーブがマスタと通信する場合はマスタのタイミングに従わなければならないので、通信リンクのスレーブは引き続きマスタのスロットの規定を知ろうとする。一般に、２つの問題を解決しなければならない。第１に、異なるスロット・タイミングについてスロット・アカウントの管理を行わなければならない。第２に、交信スロットが使用される場合、異なる通信リンク間の時間ずれを考慮しなければならない。ネットワーク全体を通じて全てのスロットが同期していると想定されたので、各スロットの冒頭でスロット・アカウント設定を行えばよい。１つの装置上でスロット・タイミングのいくつかの異なる規定が存在する場合、１つを基準タイミングとして選択する。スロット・アカウント設定は、基準タイミングにおける各スロットの冒頭でなされる。しかし、必ずしもこのタイミングを使用して最終パケットを送信または受信したわけではない。従って、パケットが現在送信または受信されている通信リンクのスロットの各冒頭で、通信リンクにタグが付けられる。各基準スロットの冒頭で、タグ付き通信リンクは最終送信／受信スロットについてアカウント設定される、すなわち、そのスロット・アカウントは１つだけ減らされる。タグはアカウント設定の後除去される。アカウント設定時に、どの装置にもタグが付けられないということが起こりうる。この場合、未使用のスロット・アカウントｕｓをアカウント設定する。
【００５１】
図４は、不均一なデータ・トラフィック配分を伴う図１のネットワーク・トポロジを示す。図１と同様、ネットワーク装置４はネットワーク装置３、５及び６に対するマスタである。ネットワーク装置３は装置４に対するスレーブであり、装置１及び２に対するマスタである。リンクは、接続する装置を列挙することにより番号が付けられる。リンクの矢印はリンクのマスタ／スレーブ関係、従って第１のレベルの優先順位を示す。この例では、２つの大きなデータ転送が行われている。第１のものは、装置１から装置２へ、装置３とリンク３１及び３２とを介して行われ、これは短縮リンク１３２である。同様に短縮されて、リンク５４６で第２のデータ転送が行われる。それと同時に、リンク４３では伝送がない。従って、２つの交信スロット間の距離はバックオフ・カウンタによって増大され、同時に、連続して使用可能なスロットの数はスロット再配分によって減らすことができる。従って、装置３は主として装置１から装置２にデータを転送し、一時的にリンク４３を監視して、未使用リンクであまり多くの時間を浪費するのを防止する。装置４は主として装置５から装置６にデータを転送し、一時的にリンク４３を監視して、未使用リンクであまり多くの時間を浪費するのを防止する。従って、リンク１３２及び５４６上の２つの交信スロット間のＮic＝２bＮinter_contactの値は最小に設定されるので、双方のリンクは装置３及び４の全伝送時間をほぼ占有する。リンク４３では、Ｎicは、ＮicがＮmax_pollを超えるまで増大し、その際Ｎmax_pollはもっぱら「ワインドアップ」効果を防止することに関係する。
【００５２】
本出願は例示の助けによる本発明の実現及び実施例の説明を含む。当業者が認識するように、本発明は上記で提示された実施例の細部に制限されるものではなく、本発明は、添付の請求項の範囲から逸脱することなく別の形態で実現してもよい。上記で提示された実施例は例示的であって制限的でないとすべきである。すなわち、本発明を実現し使用する可能性は添付の請求項によってのみ制限される。その結果同等の実現を含む、請求項によって決定されるように本発明を実現する様々な選択肢も、本発明の範囲に属する。
【図面の簡単な説明】
【００５３】
【図１】図１は装置と通信リンクとからなるネットワーク・トポロジを示す図である。
【図２】図２は本発明によるネットワークのノードを示す図である。
【図３】図３は異なるスロット・タイミングによるスロット・アカウント設定のタイミング図を示す図である。
【図４】図４は不均一なデータ・トラフィック配分を伴う図１のネットワーク・トポロジを示す図である。
【図１】
2004532555.tif 000003
【図２】
2004532555.tif 000004
【図３】
2004532555.tif 000005
【図４】
2004532555.tif 000006
【国際公開パンフレット】
2004532555.tif 000007
2004532555.tif 000008
2004532555.tif 000009
2004532555.tif 000010
2004532555.tif 000011
2004532555.tif 000012
2004532555.tif 000013
2004532555.tif 000014
2004532555.tif 000015
2004532555.tif 000016
2004532555.tif 000017
2004532555.tif 000018
2004532555.tif 000019
2004532555.tif 000020
2004532555.tif 000021
2004532555.tif 000022
2004532555.tif 000023
2004532555.tif 000024
2004532555.tif 000025
2004532555.tif 000026
2004532555.tif 000027
【国際調査報告】
2004532555.tif 000028
2004532555.tif 000029
2004532555.tif 000030