(57)【要約】【課題】タイムスロット割り当て方法及び装置を提供する。【解決手段】かかる方法は、HELLOパケットを形成し、前記HELLOパケットは、ローカルノードのGTSリクエスト情報を含み、又は、ローカルノードのGTSリクエスト情報及びローカルノードの衝突域内の少なくとも一つの隣接ノードのGTSリクエスト情報を含み；及び、前記HELLOパケットをブロードキャストし、前記HELLOパケットを受信したノードに、前記HELLOパケットに含まれている情報に基づいて、タイムスロット予約を行わせることを含む、方法。【選択図】図３
2015056893.tif 000002
【特許請求の範囲】
【請求項１】
ノードであって、
GTS二分木を形成する第一形成ユニット；
前記第一形成ユニットが形成したGTS二分木を記憶し、また、予め、ローカル衝突域内の全ての隣接ノードのGTSリクエスト情報及びローカルノードの予約履歴情報を記憶する記憶ユニット；
ローカルノードのGTSリクエスト情報を含み、又は、ローカルノードのGTSリクエスト情報及びローカルノードの衝突域内の少なくとも一つの隣接ノードのGTSリクエスト情報を含むHELLOパケットを形成する第二形成ユニット；及び
前記第二形成ユニットが形成したHELLOパケットをブロードキャストし、前記HELLOパケットを受信したノードに、前記HELLOパケットに含まれている情報に基づいて、タイムスロット予約を行わせるブロードキャストユニットを含む、ノード。
【請求項２】
請求項1に記載のノードであって、
前記第二形成ユニットは、
所定策略に基づいてローカルGTS表から一部の記録を前記隣接ノードのGTSリクエスト情報として選択する第一選択モジュール；及び
リクエストされたGTSを確定し、リクエストされたGTSに対応する情報を前記GTSリクエスト情報とする第一確定モジュールを含む、ノード。
【請求項３】
請求項2に記載のノードであって、
前記第一選択モジュールは、ローカルノードの衝突域内の隣接ノードの最大ホップ数がnである時に、前記ローカルGTS表中のローカルノードの衝突域内の全ての1-hop隣接ノードの記録、及び、2-hop隣接ノード乃至“n-1”-hop隣接ノードの記録のうち、確認情報が同意である記録を前記隣接ノードのGTSリクエスト情報とし；又は、前記ローカルGTS表中の全ての1-hop隣接ノード乃至“n-1”-hop隣接ノードの記録を前記隣接ノードのGTSリクエスト情報とする、ノード。
【請求項４】
請求項2に記載のノードであって、
前記第一確定モジュールは、
リクエストされたGTSの周期を計算する第一計算モジュール；
ローカルに保存されている予約履歴情報に基づいて、リクエストされたGTSの周期が変化しているかどうか、及び/又は、GTSの状態が無効であるかどうかを判断する第一判断モジュール；及び
リクエストされたGTSの周期が変化しており、又は、リクエストされたGTSの状態が無効であるときに、もう一つのGTSを選択し、選択したGTSの関連情報を前記リクエストされたGTSとし；リクエストされたGTSの周期が変化しておらず、且つ、リクエストされたGTSの状態が有効であるときに、予約履歴情報中のローカルノードのGTSリクエスト情報を前記リクエストされたGTSとする、第一処理モジュールを含む、ノード。
【請求項５】
請求項4に記載のノードであって、
前記記憶ユニットは更に、シンクノードの衝突域内の総トラフィックを保存し、前記第一計算モジュールは、ローカルGTS表の各記録を遍歴し、また、前記記録のうち、受信ノードがローカルノードである記録に対応するトラフィックをローカルノードのトラフィックに加入することにより、ローカルノードのトラフィックを取得し、また、前記記憶ユニットに保存されているシンクノードの衝突域内の総トラフィック及び計算されたローカルノードのトラフィックに基づいて、以下の公式により、リクエストされたGTSの周期を計算し、
【数１】
2015056893.tif 000025
そのうち、
（外１）
2015056893.tif 000026
であり、xは、整数であり、TCD-sinkは、シンクノードの衝突域内のトラフィックであり；Tiは、ローカルノードのトラフィックであり、2expは、リクエストされたGTSの周期である、ノード。
【請求項６】
請求項4に記載のノードであって、
前記第一処理モジュールは、もう一つのGTSを選択する時に、計算された、リクエストされたGTSの周期に応じて、所定策略に基づいて、前記形成ユニットが形成したGTS二分木をサーチし、前記リクエストされたGTSの周期が所在する行の上での一つ目の空きGTSを選択し、又は、GTSのオフセットがその受信ノードのGTSのオフセットよりも小さいGTSを選択する、ノード。
【請求項７】
請求項1に記載のノードであって、
前記記憶ユニットは更に、シンクノードの衝突域内の総トラフィックを記憶し、前記HELLOパケットは、更に、シンクノードの衝突域内の総トラフィックを含み、前記第二形成ユニットは、
ローカルノードがシンクノードであるかどうかを判断する第二判断モジュール；
ローカルノードがシンクノードであるときに、ローカルGTS表の各記録を遍歴し、また、各記録に対応するトラフィックをシンクノードの衝突域内の総トラフィックに加入することにより、シンクノードの衝突域内の総トラフィックを取得し、取得したシンクノードの衝突域内の総トラフィックを前記HELLOパケットに加入する第二計算モジュール；及び
ローカルノードがシンクノードであない時に、前記記憶ユニットに保存されているシンクノードの衝突域内の総トラフィックを前記HELLOパケットに加入する第二処理モジュールを含む、ノード。
【請求項８】
請求項1に記載のノードであって、
前記第一形成ユニットは、公式GTS=(2exp,offset)に基づいてGTS二分木の根Root=(20,0)を生成し、そのうち、exp=0、offset=0であり；公式GTSleft-child=(2exp+1,offset)に基づいて、各GTSの一つの左の子GTSを生成し；公式GTSright-child=(2exp+1,offset+2exp)に基づいて、各GTSの一つの右の子GTSを生成し；前記GTS二分木の根、前記各GTSの左の子GTS、及び前記各GTSの右の子GTSから、前記GTS二分木を形成する、ノード。
【請求項９】
請求項1に記載のノードであって、
処理ユニットを含み、前記処理ユニットは、更新モジュール、及び/又は、判定モジュール、及び/又は、合併モジュール、及び/又は、認証モジュールを含み、
前記更新モジュールは、受信したHELLOパケットに基づいて、シンクノードの衝突域内の総トラフィックを更新し；
前記判定モジュールは、HELLOパケットの送信元の、ローカルリクエストされたGTSへの認証結果を確定し；
前記合併モジュールは、HELLOパケット中のGTS表と、ローカルGTS表とを合併し；
前記認証モジュールは、HELLOパケットの送信元にリクエストされたGTSに対して認証を行い
前記更新モジュールは、前記HELLOパケット中のシンクノードの衝突域内の総トラフィックが、ローカルに保存されているシンクノードの衝突域内の総トラフィックよりも大きいときに、ローカルに保存されているシンクノードの衝突域内の総トラフィックを更新し、そうでないときに、ローカルに保存されているシンクノードの衝突域内の総トラフィックを不変にさせ；及び／又は
前記判定モジュールは、HELLOパケットのGTS表の各記録をスキャンし、送信ノードのアドレスがローカルノードアドレスである記録を見つけ；該記録の確認情報が拒否であるときに、ローカルにリクエストされたGTSが無効であると確定し；該記録の確認情報が同意であるときに、ローカルにリクエストされたGTSが有効であると確定し；及び／又は
前記合併モジュールは、HELLOパケット中のGTS表のうち、確認情報が同意である記録をローカルGTS表に合併し；ローカルGTS表には、前記確認情報が同意である記録を記憶していれば、前記処理ユニットは、該記録の距離がローカルGTS表中の対応する記録の距離よりも小さい時に、HELLOパケット中の該記録を以てローカルGTS表中の対応する記録を置換し、且つ該記録の距離に1を加算し；ローカルGTS表には前記確認情報が同意である記録を記憶していなければ、前記処理ユニットは、該記録をローカルGTS表に添加し、また、該記録の距離に1を加算し；及び／又は
前記認証モジュールは、ローカル受信干渉検出を行い、前記HELLOパケットの送信元にリクエストされたGTSが、ローカルノードを受信ノードとするの隣接ノードにリクエストされたGTSと衝突するかどうかを確定し；また、ローカル送信干渉検出を行い、前記HELLOパケットの送信元にリクエストされたGTSが、ローカルにリクエストされたGTSと衝突するかどうかを確定し；両者には衝突がない場合、HELLOパケットの送信元にリクエストされたGTSについて同意を付与し；衝突がある場合、HELLOパケットの送信元のアドレスが前記隣接ノードのアドレスよりも大きいときに、又は、HELLOパケットの送信元のアドレスがローカルアドレスよりも大きいときに、HELLOパケットの送信元にリクエストされたGTSについて同意を付与し、そうでないときに、HELLOパケットの送信元にリクエストされたGTSについて拒否を付与する、ノード。
【請求項１０】
タイムスロット割り当て方法であって、
HELLOパケットを形成し、前記HELLOパケットは、ローカルノードのGTSリクエスト情報を含み、又は、ローカルノードのGTSリクエスト情報及びローカルノードの衝突域内の少なくとも一つの隣接ノードのGTSリクエスト情報を含み；及び
前記HELLOパケットをブロードキャストし、前記HELLOパケットを受信したノードに、前記HELLOパケットに含まれている情報に基づいて、タイムスロット予約を行わせることを含む、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線通信分野に関し、特に、タイムスロット割り当て方法及び装置に関する。
【背景技術】
【０００２】
センサネットワークにおける多くのアプリケーションは、シンクノード（sink  node）で周期的に、センサノード（sensor  node）が生成したデータを取集することを含む。ツリートポロジーでは、周期的にデータを取集することが、無線センサネットワークの基本操作である。このような「多対一」の通信モードは、コンバージキャスト（convergecast）とも定義されている。幾つかのアプリケーションでは、コンバージキャストについて、１００％のパケット到着率を要する。IEEE  802.15.4に指定されているシングルチャネル周波数、スーパーフレームは、無衝突伝送用のGTS（Guaranteed  Time  Slot、保証付きタイムスロット）を提供しているが、IEEE  802.15.4は、タイムスロット割り当て方法を提供していない。特に、ツリートポロジーでは、タイムスロット割り当ては一つの挑戦である。
【０００３】
今のところ、多くの従来のコンバージキャストのタイムスロット割り当て方法は、集中型である。このような集中型方法では、中央制御ユニットを要し、且つ、全ての他のノードの位置をも要する。ノードの数が大きい場合、このような集中型方法は失効になる恐れがある。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の目的は、集中型タイムスロット割り当て方法に存在する問題を解決するためのタイムスロット割り当て方法及び装置を提供することにある。
【課題を解決するための手段】
【０００５】
本発明の実施例の一側面によれば、ノードが提供され、このノードは、
GTS二分木を形成する第一形成ユニット；
前記第一形成ユニットが形成したGTS二分木を記憶し、また、ローカル衝突域内の全ての隣接ノードのGTSリクエスト情報及びローカルノードの予約履歴情報を予め記憶する記憶ユニット；
ローカルノードのGTSリクエスト情報を含む、又は、ローカルノードのGTSリクエスト情報及びローカルノードの衝突域内の少なくとも一つの隣接ノードのGTSリクエスト情報を含むHELLOパケットを形成する第二形成ユニット；及び
前記第二形成ユニットが形成したHELLOパケットをブロードキャストし、前記HELLOパケットを受信したノードに、前記HELLOパケットに含まれている情報に基づいて、タイムスロット予約を行わせるブロードキャストユニットを含む。
【０００６】
本発明の実施例の有益な効果は、本発明の実施例が提供する分散型タイムスロット割り当て方法は、集中型タイムスロット割り当て方法に比べ、中央制御ユニットを要せず、且つ、計算複雑度を低減し、タイムスロットの利用率を向上させることができるとのことにある。
【図面の簡単な説明】
【０００７】
【図１】シンクノードを囲む衝突域を示す図である。
【図２】IEEE  802.15.4規格に指定されているスーパーフレームの構成図である。
【図３】本発明の実施例におけるタイムスロット割り当て方法のフローチャートである。
【図４】GTS表の一例のフォーマットを示す図である。
【図５】リクエストされたGTS周期を確定する一例のフローチャートである。
【図６】ローカルに保存されている予約履歴情報の一例のフォーマットを示す図である。
【図７】リクエストされたGTS周期を計算する一例のフローチャートである。
【図８】HELLOパケットの一例のフォーマットを示す図である。
【図９】GTS二分木を形成するフローチャートである。
【図１０】周期が16である視点のGTS二分木を示す図である。
【図１１】周期が8である視点のGTS二分木を示す図である。
【図１２】1-hop隣接ノード、2-hop隣接ノード及び3-hop隣接ノードを示す図である。
【図１３】衝突域を示す図である。
【図１４】センサノードにおいてトラフィックを計算するフローチャートである。
【図１５】シンクノードにおいて衝突域のトラフィックを計算するフローチャートである。
【図１６】HELLOパケットをブロードキャストするフローチャートである。
【図１７】HELLOパケットを受信するフローチャートである。
【図１８ａ】本発明の実施例の方法と、従来のタイムスロット割り当て方法との平均エンドツーエンド時間遅延の比較図である。
【図１８ｂ】本発明の実施例の方法と、従来のタイムスロット割り当て方法とのパケット到着率の比較図である。
【図１９】本発明の実施例のノードの構成図である。
【発明を実施するための形態】
【０００８】
以下、添付した図面を参照しながら、本発明を実施するための形態を詳しく説明する。
【０００９】
当業者が容易に本発明の原理及び実施形態を理解し得るために、本発明の実施例では、Ad-hocネットワークを例として説明を行うが、理解すべきは、本発明の実施例はAd-hocネットワークに限定されず、例えば、本発明の実施例が提供する方法及び装置は無線通信、スマートグリッドなどの他のマルチホップネットワークにも適用し得るとのことである。
【００１０】
本発明の実施例は、ツリートポロジーにおいてコンバージキャストへのタイムスロット割り当て方法を提供する。該ツリートポロジーは、一つのシンクノード及び大量のセンサノードからなる。図１に示すように、各センサノードは周期的にデータを生成し、且つ該シンクノードはツリーの唯一ルートである。該ツリーポロジーでは、各ノードは一つのみの親ノードを有し、該親ノードは、シンクノードを目的とするのルーティングのネクストホップ（next  hop）である。本発明の実施例では、該タイムスロットは、分散方式で割り当てられ、各ノードは、その親ノードに到着するリンクのために適切なタイムスロットを選択するだけでよい。
【００１１】
本発明の実施例は、IEEE  802.15.4規格に指定されているスーパーフレームに基づくものである。該スーパーフレームは、三つの部分、即ち、ビーコンタイムスロット（Beacon  slot）、CAP（Contention  Access  Period）及びCFP（Contention  Free  Period）を図2に示すように含む。CAPでは、送信器（intending  transmitters）が、CSMA（Carrier  Sense  Multiple  Access）メカニズムを用いて、チャネルに競争的にアクセスする。CFPでは、該送信器が、TDMA（Time  Division  Multiple  Access）方式でチャネルにアクセスする。また、各送信器は、一つ以上のタイムスロットにおいてデータを送信することができる。一つのタイムスロットの長さは、一つのみのデータパケットを送信することができる。一つのノードが指定している全てのタイムスロットは、GTSと称されている。しかしながら、如何にCFP中のこれらのタイムスロットを割り当てるかについては、IEEE  802.15.4に言及されていない。
【００１２】
本発明の実施例は、図2に示すようなスーパーフレームの構成に基づく分散型タイムスロット割り当て方法を提供する。該方法を用いることにより、ツリートポロジーにおけるコンバージキャストをサポートするよう、CFP中のタイムスロットを適切に割り当てることができる。以下、添付した図面及び具体的な実施例に基づいて本発明の実施例におけるタイムスロット割り当て方法及び装置について詳細に説明する。
【実施例１】
【００１３】
本発明の実施例は、タイムスロット割り当て方法を提供する。図3は、該方法のフローチャートである。図3に示すように、該方法は、次のステップを含む。
【００１４】
ステップ301：HELLOパケットを形成し、前記HELLOパケットは、ローカルノードのGTSリクエスト情報を含み、又は、ローカルノードのGTSリクエスト情報及びローカルノードの衝突域内の少なくとも一つの隣接ノードのGTSリクエスト情報を含み；
ステップ302：前記HELLOパケットをブロードキャストし、前記HELLOパケットを受信したノードに、前記HELLOパケットに含まれている情報に基づいて、タイムスロット予約を行わせる。
【００１５】
本発明の実施例では、各ノードは、ローカルに保存されているGTS表に基づいて、HELLOパケットの前記隣接ノードのGTSリクエスト情報を生成することができ、また、ローカルノードのGTSへの選択に基づいて、HELLOパケットのローカルノードのGTSリクエスト情報を生成することができる。
【００１６】
本実施例では、HELLOパケットの前記隣接ノードのGTSリクエスト情報を形成するために、各ノードは一つのGTS表を保存する必要があり、該GTS表は、該ノードの衝突域内の全ての隣接ノードのGTSリクエスト情報を含み、これらの情報は、HELLOパケットを受信し、そして、その中から、その衝突域内の隣接ノードからのGTSリクエスト情報を取集することにより得たれたものである。HELLOパケットを一回目受信する前にローカルGTS表が空であるので、HELLOパケットを一回目受信する前にHELLOパケットを送信すれば、該HELLOパケット中の隣接ノードのGTSリクエスト情報も空である。一例では、ローカルノードは、所定策略に基づいて、ローカルGTS表から一部の記録を前記隣接ノードのGTSリクエスト情報として選択してもよい。例えば、ローカルノードの衝突域内の隣接ノードの最大ホップ数がnであれば、ローカルノードは、ローカルGTS表中のローカルノードの衝突域内の全ての1-hop隣接ノードの記録、及び、2-hop隣接ノードから“n-1”-hop隣接ノードまでの記録のうち、確認情報が同意である記録を前記隣接ノードのGTSリクエスト情報としてもよく；前記ローカルGTS表中の全ての1-hop隣接ノードからn-1-hop隣接ノードまでの記録を前記隣接ノードのGTSリクエスト情報としてもよい。なお、本発明は、これに限定されず、ローカルノードは、他の策略に基づいてローカルGTS表から記録を選択してもよく、例えば、ローカルGTS表中の記録数が所定数よりも小さければ、ローカルノードは、ローカルGTS表中の全ての記録を選択してもよい。
【００１７】
図4は、該GTS表の一例のフォーマットを示す図である。図4に示すように、各ノードは、このような一つのGTS表を維持し、該GTS表は、その衝突域内の他のノードのルーティング及びGTS情報を記録している。各記録は、七つの要素を有し、記録iを例とすれば、“Txi”は、ノードiのIDであり；“Rxi”は、ノードiの親ノード（それは、シンクノードを目標とするルーティングのネクストホップでもある）であり；“expi”及び“offseti”は、ノードiが要するGTSを構成し；“Ti”は、ノードiのトラフィック（式（8）参照）であり；“distancei”は、ノードiから現在のノードまでのホップ数であり、例えば、2-hop隣接ノードの距離は、2であり、また例えば、3-hop衝突域を例とすれば、該“distancei”は、1又は2又は3であり；“commenti”は、現在のノードが行ったGTSiへの確認であり、それは、拒否（denial）又は同意（agree）である。
【００１８】
本実施例では、HELLOパケットのローカルノードのGTSリクエスト情報を形成するために、リクエストされた（requested）GTSを選択する必要がある。
【００１９】
一例では、ローカルノードがローカルノードの予約履歴情報を保存しており、該予約履歴情報は、ローカル（ノード）にリクエストされたGTSを示しており、オプションで、該予約履歴情報は、更に、ローカルにリクエストされたGTSの状態をも示している。この時、該予約履歴情報に基づいて、ローカルにリクエストされたGTSが変化しておらず、且つ、ローカルにリクエストされたGTSの状態が有効である場合、依然として、予約履歴情報中のローカルにリクエストされたGTSの関連情報をローカルノードのGTSリクエスト情報とし；一方、ローカルにリクエストされたGTSが変化しており、又は、ローカルにリクエストされたGTSの状態が無効である場合、GTSを再び選択し、そてし、再び選択したGTSの関連情報をローカルノードのGTSリクエスト情報とする必要がある。
【００２０】
他の例では、ローカルノードがローカルノードの予約履歴情報を保存しない。この時、GTSを直接選択し、そして、選択したGTSの関連情報をローカルノードのGTSリクエスト情報をとしてもよい。
【００２１】
以下、添付した図面に基づいて上述の二つの例について詳細に説明する。なお、前の一例におけるGTSの再選択方法は、後の一例におけるGTSの選択方法とは同じであるので、具体的な実現プロセスについては、重複説明を省略する。
【００２２】
図5は、ローカルに保存されている予約履歴情報に基づいて、リクエストされたGTSを確定する方法のフローチャートである。図5に示すように、該方法は、次のステップを含む。
【００２３】
ステップ501：リクエストされたGTSの周期を計算する。
【００２４】
そのうち、各GTSは、二つの要素を含み、一つは周期であり、もう一つはオフセットである。本実施例では、リクエストされたGTSの周期が変化していれば、リクエストされたGTSもそれに伴って変化するので、新しいGTSを再選択する必要がある。よって、本実施例では、先ず、リクエストされたGTSの周期を計算し、次に、それを、ローカルに保存されているローカルノードの予約履歴情報と比較し、リクエストされたGTSの周期が変化しているかどうかを確認する。
【００２５】
そのうち、ローカルトラフィック、及び、シンクノードの衝突域内のトラフィックに基づいて、リクエストされたGTSの周期を計算してもよく、また、他の策略に基づて、リクエストされたGTSの周期を計算してもよい。具体的には後述する。
【００２６】
ステップ502：ローカルに保存されているローカルノードの予約履歴情報に基づいて、リクエストされたGTSの周期が変化しているかどうか、及び/又は、リクエストされたGTSの状態が無効であるかどうかを判断する。
【００２７】
そのうち、ローカルノードは、更に、ローカルノードにリクエストされたGTSの履歴情報を保存してもよく、本実施例では、ローカルノードのGTSリクエスト情報又は予約履歴情報と称される。上述のように、該予約履歴情報は、ローカルノードにリクエストされたGTSのみを含んでもよく、ローカルノードにリクエストされたGTSと、該ローカルノードにリクエストされたGTSの状態との両方を含んでもよい。
【００２８】
図6は、該リクエストされたGTSの関連情報の一例のフォーマットを示す図である。図6に示すように、それは、六つの要素を含む。そのうち、“state”は、有効（valid）又は無効（invalid）であってよく、それは、隣接ノードから取集されたコメント（意見）による（依存する）。他の要素の意味は、GTS表中の対応する各要素の意味とは同じであるので、ここでは詳しい説明を省略する。そのうち、要素“state”は、オプションであり、即ち、本発明の実施例の他の例では、“state”という要素がなくてもよく、他の方式で、リクエストされたGTSが有効であるかどうかを示してもよい。例えば、ローカルにリクエストされたGTSが無効である時に、該予約履歴情報中の某要素を第一所定値（例えば、某要素を負値）に設定し、ローカルにリクエストされたGTSが有効である時に、該予約履歴情報の各要素を第二所定値（例えば、各要素を正常値）に設定し、このようにすれば、リクエストされたGTSが有効であるかどうかを示すこともでき、即ち、“state”という要素を要しなくてもよい。
【００２９】
ステップ503：リクエストされたGTSの周期が変化しており、又は、リクエストされたGTSの状態が無効であれば、もう一つのGTSを選択し、そして、選択したGTSの関連情報を前記リクエストされたGTSとする。
【００３０】
そのうち、前に選択されたGTSがもう使えないので、一つの新しいGTSを選択する必要がある。一例では、算出された、リクエストされたGTSの周期に応じて、所定策略に基づいて、ローカルに形成されたGTS二分木をサーチし、前記リクエストされたGTSの周期が所在する行の上の一つ目の空きGTSを選択してもよく、又は、GTSのオフセットが、その受信ノードのGTSのオフセットよりも小さいGTSを選択してもよい。そのうち、所定策略は、例えば、前記リクエストされたGTSの周期が所在する行の上で、左から右へローカルに形成されたGTS二分木をサーチし、又は、右から左へローカルに形成されたGTS二分木をサーチするというものである。なお、本発明の実施例は、これに限定されない。
【００３１】
そのうち、該もう一つのGTSを選択する方法は、予約履歴情報を記憶せずにGTSを直接選択する場合にも同様に適用し得るので、ここでは詳しい説明を省略する。
【００３２】
ステップ504：リクエストされたGTSの周期が変化しておらず、且つ、リクエストされたGTSの状態が有効であれば、予約履歴情報中のリクエストされたGTSの関連情報を前記リクエストされたGTSとする。
【００３３】
図5に示す方法により、ローカルノードのGTSリクエスト情報（新しく選択された又は保存されたもの）を確認することができる。
【００３４】
ステップ501の一例では、ローカルノードのトラフィック及びシンクノードの衝突域内のトラフィックに基づいて、リクエストされたGTSの周期を計算することができる。図7は、該例のフローチャートであり、図7に示すように、該方法は、次のステップを含む。
【００３５】
ステップ701：ローカルノードのトラフィックを計算する。
【００３６】
そのうち、ローカルGTS表の各記録を遍歴し、該記録のうちの、受信ノードがローカルノードである記録に対応するトラフィックを、ローカルノードのトラフィックに追加することにより、ローカルノードのトラフィックを得ることができる。
【００３７】
ステップ702：シンクノードの衝突域内のトラフィック及び算出されたローカルノードのトラフィックに基づいて、以下の公式により、リクエストされたGTSの周期を計算する。
【数１】
2015056893.tif 000003
【００３８】
そのうち、
（外１）
2015056893.tif 000004
であり、xは整数であり、TCD-sinkは、シンクノードの衝突域内のトラフィックであり、Tiは、ローカルノードのトラフィックであり、2expは、リクエストされたGTSの周期である。
【００３９】
該例では、ローカルノードがシンクノードであれば、該シンクノードの衝突域内のトラフィックは、計算により得ることができ、ローカルノードがシンクノードでなければ、該シンクノードの衝突域内のトラフィックは、HELLOパケットの交換により得ることがであき、即ち、該HELLOパケットは更に、シンクノードの衝突域内のトラフィックをも含む。
【００４０】
そのうち、ローカルGTS表の各記録を遍歴し、そして、各記録に対応するトラフィックをシンクノードの衝突域内の総トラフィックに追加することで、シンクノードの衝突域内の総トラフィックを得ることができる。
【００４１】
そのうち、各ノードは、シンクノードを囲む衝突域内のトラフィック（TCD-sinkと記す）を保存し、そして、HELLOパケットを形成する時に、シンクノードの衝突域内のトラフィックをHELLOパケットに追加してもよい。
【００４２】
図7に示すような、ローカルトラフィック及びシンクノードの衝突域内のトラフィックに基づいて、リクエストされたGTSの周期を計算する方法は、例示だけであり、本発明の実施例は、これに限定されない。他の例では、他の策略に基づいて、リクエストされたGTSの周期を計算してもよく、例えば、ローカルノードからシンクノードまでのホップ数に基づいて、リクエストされたGTSの周期を計算してもよく、例えば、ホップ数が大きいほど（即ち、シンクノードからの距離が遠いほど）、周期が大きい（所要なタイムスロットが少ない）という原則で、リクエストされたGTSの周期を確定してもよい。
【００４３】
図8は、本発明の実施例における方法により形成されたHELLOパケットの一例のフォーマットを示す図である。図8に示すように、該HELLOパケットには、元の源アドレス（Source  addr）及び目標アドレス（Destination  addr）の他に、ローカルノードのGTSリクエスト情報及びローカルノードの衝突域内の少なくとも一つの隣接ノードのGTSリクエスト情報をも含み、オプションで、更に、シンクノードの衝突域内のトラフィックTCD-sinkをも含む。そのうち、ローカルノードのGTSリクエスト情報は、五つのエレメントから構成され、それぞれは、HELLOパケットの送信ノードのアドレス（Tx）、HELLOパケットの送信ノードが送信しようとするデータパケットの受信ノードのアドレス（Rx）、HELLOパケットの送信ノードにリクエストされたGTSのexp及びオフセット、及び、HELLOパケットの送信ノードのトラフィックである。そのうち、ローカルノードの衝突域内の少なくとも一つの隣接ノードのGTSリクエスト情報は、七つのエレメントから構成され、各エレメントの意味は、GTS表中の各エレメントの意味とは同じであるため、ここでは詳しい説明を省略する。オプションで、該HELLOパケットには、更に、シンクノードの衝突域内のトラフィックTCD-sinkを含んでもよく、該ノードがシンクノードであれば、該TCD-sinkは、計算により得ることができ、該ノードがシンクノードでなければ、該TCD-sinkは、受信したHELLOパケットにより得ることができる。
【００４４】
本発明の実施例では、各ノードが、形成されたGTS二分木に基づいて、必要なGTSを選択し、そして、GTSのネゴーシエイション（negotiation）を行うので、本実施例では、予め一つのGTS二分木を形成してもよい。具体的には、該GTS二分木の形成方法は、図9に示す方法により実現することができる。図9に示すように、該方法は、次のステップを含む。
【００４５】
ステップ901：公式GTS=(2exp,offset)に基づいて、GTS二分木の根Root=(20,0)を生成し、そのうち、exp=0、offset=0であり；
ステップ902：公式GTSleft-child=(2exp+1,offset)に基づいて、各GTSの一つの左の子GTSを生成し；
ステップ903：公式GTSright-child=(2exp+1,offset+2exp)に基づいて、各GTSの一つの右の子GTSを生成し；
ステップ904：前記GTS二分木の根、前記各GTSの左の子GTS、及び前記各GTSの右の子GTSに基づいて、上述のGTS二分木を生成する。
【００４６】
本実施例では、HELLOパケットを受信していれば、受信しているHELLOパケットに基づいて、シンクノードの衝突域内の総トラフィックを更新してもよく、及び/又は、HELLOパケットの送信元の、ローカルにリクエストされたGTSへの認証結果を確定してもよく、及び/又は、HELLOパケット中のGTS表と、ローカルGTS表とを合併してもよく、及び/又は、HELLOパケットの送信元にリクエストされたGTSに対して認証を行ってもよい。これにより、GTSのネゴーシエイションを完成させることができる。
【００４７】
そのうち、シンクノードの衝突域内の総トラフィックの更新については、HELLOパケット中のシンクノードの衝突域内の総トラフィックと、ローカルに保存されているシンクノードの衝突域内の総トラフィックとを比較することにより実現することができる。HELLOパケット中のシンクノードの衝突域内の総のトラフィックが、ローカルに保存されているシンクノードの衝突域内の総のトラフィックよりも大きい場合、ローカルに保存されているシンクノードの衝突域内のトラフィックを更新し、そうでない場合、ローカルに保存されているシンクノードの衝突域内のトラフィックを不変にさせる。
【００４８】
そのうち、HELLOパケットの送信元の、ローカルにリクエストされたGTSへの認証結果の確定については、HELLOパケットのGTS表の各記録をスキャンすることにより実現することができる。HELLOパケットのGTS表の各記録をスキャンすることにより、送信ノードのアドレスがローカルノードアドレスである記録を見つけることができ、該記録は、ローカルにリクエストされたGTSの関連情報である。該記録の確認情報が拒否であれば、ローカルにリクエストされたGTSが無効であると確定し、この時に、ローカル予約履歴情報を変更してもよく、例えば、ローカルにリクエストされたGTSの状態を無効に変更し、又は、ローカルにリクエストされたGTSを空にセットしてもよい。該記録の確認情報が同意であれば、ローカルにリクエストされたGTSが有効であると確定し、この時に、ローカルにリクエストされたGTSの状態を不変にさせる。
【００４９】
そのうち、HELLOパケット中のGTS表と、ローカルGTS表との合併については、HELLOパケット中のGTS表中の各記録と、ローカルGTS表中の各記録とを比較することにより実現することができる。HELLOパケット中のGTS列表のうちの、確認情報が同意である記録を、ローカルGTS表に合併し、そのうち、ローカルGTS表には前記確認情報が同意である記録を記憶したことがある場合、該記録の距離がローカルGTS表中の対応する記録の距離よりも小さい時に、HELLOパケット中の該記録を以てローカルGTS表中の対応する記録を置換し、且つ、将該記録の距離に1をプラス（加算）し、そのうち、ローカルGTS表には前記確認情報が同意である記録を記憶したことがない場合、該記録をローカルGTS表に添加し、且つ、該記録の距離に1をプラスする。
【００５０】
そのうち、HELLOパケットの送信元にリクエストされたGTSへの認証については、HELLOパケットの送信元にリクエストされたGTSと、ローカルGTS表中の各記録及びローカルにリクエストされたGTSとを比較することにより実現することができる。先ず、ローカル受信干渉検出を行い、前記HELLOパケットの送信元にリクエストされたGTSが、ローカルノードを受信ノードとする隣接ノードにリクエストされたGTSと衝突しているかどうかを確定し；その後、ローカル送信干渉検出を行い、前記HELLOパケットの送信元にリクエストされたGTSが、ローカルにリクエストされたGTSと衝突しているかどうかを確定し；衝突がなければ、HELLOパケットの送信元にリクエストされたGTSに「同意」を付与し；衝突があれば、HELLOパケットの送信元のアドレスが前記隣接ノードのアドレスよりも大きい時（前者衝突）に、又は、HELLOパケットの送信元のアドレスがローカルアドレスよりも大きい（後者衝突）時に、HELLOパケットの送信元にリクエストされたGTSに同意を付与し、そうでない時に、HELLOパケットの送信元にリクエストされたGTSに拒否を付与する。
【００５１】
本発明の実施例における方法によれば、計算複雑度を低減し、タイムスロットの利用率を向上させることができる。
【００５２】
本発明の実施例における方法をより明確にするために、以下、GTS二分木の形成、GTSの選択、GTSのネゴーシエイションなどのプロセスを基づいて、本発明の実施例における方法について詳細に説明する。
【００５３】
マルチホップツリートポロジーでは、ブランチの中間部分にあるノードは、子ノードのためにデータパケットを転送する必要がある。よって、データパケットの到着時間を予測することは難しい。GTSが複数の連続タイムスロットを含んでいる場合、データパケットがこれらのタイムスロットよりも遅く到着したら、効率の低下を招くことがある。本発明の実施例におけるGTSは、周期性モードと定義される。公式（1）に示すように、該GTSは、二つの要素を含み、一つのGTSについて、一つ目の指定タイムスロットが“offset”とインデックス付けられ、その後の指定タイムスロットは、各々の周期タイムスロットを重複する。
【数２】
2015056893.tif 000005
【００５４】
ツリートポロジー中のコンバージキャストについては、ツリーの頂部と隣接するノードは、ツリーの底部と隣接するノードに比べ、より多くのデータパケットを転送する必要がある。よって、異なるノードについては、周期が異なるはずである。大きいトラフィックロードを有するノードは、小さい周期を有し、且つ、小さいトラフィックロードを有するノードは、大きい周期を有する。しかしながら、異なる周期は、衝突を引き起こすことがあり、例えば、公式（2）の場合である。
【数３】
2015056893.tif 000006
【００５５】
本発明の実施例では、特殊なGTS選択方法を提案してこのような衝突を避ける。周期は、2のべき乗に基づいて計算するので、GTSは、次のように表すことができる。
【数４】
2015056893.tif 000007
【００５６】
本発明の実施例では、全てのGTSは、GTS二分木により組織される。図10及び図11に示すように、ツリー上の各ノードは一つのGTSを表す。各ノードは二つの項、即ち、(2exp,offset)を含み、これは、該GTSが第offset個のタイムスロットで始まり、2exp個のタイムスロット毎に重複するとのことを意味する。該二分木の根は、(20,0)であり、
【数５】
2015056893.tif 000008
と表される。
【００５７】
GTS二分木では、各GTSは二つの子GTSを有する。二つの子GTSのタイムスロットの総和は、所属する親GTSが含むタイムスロットとは等しい。この二つの子GTSは、公式（5）の計算により得ることができる。
【数６】
2015056893.tif 000009
【００５８】
本発明の実施例では、上述のように、GTS二分木の形成方法は、次のステップを含む。
【００５９】
ステップ1：公式（4）に基づいて根ノードを生成し；
ステップ2：各ノードが、公式（5）に基づいて、一つの左の子及び一つの右の子を生成する。
【００６０】
該GTS二分木は、二つの重要な特徴を有する。第一、全てのタイムスロットは、該GTS二分木に含まれる。図10に示すように、タイムスロットが、時間軸に沿って0からインデックスされ、第4行上のタイムスロットの重複周期が16である。第4行上の各GTSが、一つの周期内の一つのタイムスロットにマッピングされ、且つ、一つの周期内の各タイムスロットが、第4行の一つのGTSにマッピングされる。第二、二つのGTSの間の衝突は、該GTS二分木から検出することができる。このツリーの中では、子GTSは、その親GTSのサブセットである。よって、任意の二つの異なる周期を持つGTSについては、一つのGTSがもう一つのGTSの祖先（親又は親の親又は親の親の親…）であれば、両者が互いに衝突する。簡単に言えば、二つのGTSが同一のブランチにあれば、衝突がある。
【００６１】
以上の二つの特徴に基づいて、本発明の実施例では、時間軸上でなく、GTS二分木中からGTSを選択する。続いて、該ツリートポロジーネットワークでは、各ノードについて、どの周期が適切であるかを決めることになる。上述のように、大きいトラフィックロードを有するノードが小さい周期を有し、小さいトラフィックロードを有するノードが大きい周期を有することは望ましい。よって、本発明の実施例における一例では、トラフィックに基づいて各ノードの所望する周期を計算する。
【００６２】
本発明の実施例では、一つの衝突域内のトラフィックの総数（総量）が衝突域内のトラフィックと定義される。各ノードの周期は、該ノードのトラフィックと、衝突域内のトラフィックとの比であり、公式（6）に示す通りである。
【数７】
2015056893.tif 000010
【００６３】
TCDiは、ノードiを囲む衝突域内のトラフィックであり、Tiは、ノードiのトラフィックである。
【００６４】
公式（3）を再び参照するに、公式（7）に基づいて、ノードiのexpを得ることができ、そして、ノードiの周期2expを得ることができる。
【数８】
2015056893.tif 000011
【００６５】
そのうち、
（外２）
2015056893.tif 000012
であり、xは、整数である。
【００６６】
本実施例の一例では、上述のように、次の方法を用いてexpを計算することができる。
【００６７】
センサネットワークでは、典型的に、全てのセンサノードは、周期的に同じ周波数でデータを生成し、これにより、シンクノードは、これらのデータを収集する。本発明の実施例では、タイムスロット割り当ては、周期的方式であるので、該割り当て方法は、一つのデータ周期のみに注目する。割り当てられたタイムスロットは、時間に伴って重複するので、後続のデータ周期に用いることができる。
【００６８】
一つのノードのトラフィックは、該ノードが一つのデータ周期内に伝送しなければならないデータパケットの数と定義される。該ノードiのトラフィックは、Tiと表され、その生成するデータ及びその子ノードのために転送するデータを含む。Tiは、公式（8）で計算することができる。
【数９】
2015056893.tif 000013
【００６９】
Childiは、ノードiの子ノードセットであり。公式（8）によれば、Tiを重複計算する必要がある。該方法では、各ノードは、周期的にHELLOパケットをブロードキャストし、これにより、最新情報は、隣接ノードの間に交換することができ、例えば、Tiである。Tiの計算プロセスについては、次の部分に詳しく紹介する。
【００７０】
一つの仮定としては、伝送モデルが単位円であり、伝送半径がRでることがある。図12に示すように、一つのノードiについては、その1-hop隣接ノードは、HELLOパケットのブロードキャストが直接到着し得る隣接ノードであり、その2-hop隣接ノードは、少なくとも1回のHELLOパケット転送を経由して到着し得る隣接ノードであり、その3-hop隣接ノードは、少なくとも2回のHELLOパケット転送を経由して到着し得る隣接ノードであり、4-hop乃至n-hop隣接ノードの定義は、これに基づい類推することができる。
【００７１】
一つの実現方法は、干渉半径が伝送半径の２倍である。ノードiについては、その伝送は、1-hop及び2-hop隣接ノードの受信に干渉を与え、且つ、その受信は、1-hop及び2-hop隣接ノードの伝送による干渉を受ける。図13を例とし、ノードi及びその3-hop隣接ノードが同じ時間にデータを送信すれば、ノードiの伝送は、2-hop隣接ノードの受信に影響を与えることがある。十分な抗干渉の保護を提供するために、任意の3ホップ以内の伝送を同じタイムスロット内に行ってはいけない。某ノードを中心とする3ホップ領域は、衝突域（CD、collision  domain）と定義される。図1には、シンクノードを囲む衝突域を示している。
【００７２】
全ての一つの衝突域内のデータ伝送は、異なるタイムスロットにおいて行う必要がある。よって、衝突域に含まれているトラフィックが大きいほど、より多くのタイムスロットを要する。一つの衝突域内のトラフィックは、該衝突域内に位置する全てのノードの総トラフィックに等しく、TCDと表される。ノードiを中心とする衝突域（CDi）のトラフィックは、公式（9）による計算することができる。
【数１０】
2015056893.tif 000014
【００７３】
最大TCDを含む衝突域は、ネットワークのボトルネックである。それは、コンバージキャストのスループットを制限する。よって、ノードiの適切なGTS周期は、
【数１１】
2015056893.tif 000015
である。コンバージキャストでは、シンクノードを中心とする衝突域は最大TCDを含み、且つ、Tsinkは0であり、公式（9）及び（10）を合併し、適切なGTS周期は、公式（11）により計算することができる。
【数１２】
2015056893.tif 000016
【００７４】
公式（7）を再び参照するに、GTSの周期は、2のべき乗であり、且つ、expは、整数であってよく、よって、GTS周期の指数expの計算方法は、
【数１３】
2015056893.tif 000017
である。そのうち、
（外３）
2015056893.tif 000018
であり、xは、整数である。
【００７５】
本発明の実施例では、シングルノードのたけに適切なGTS周期を計算するには、TCD-sink及びTiが必要なものであり、この二つのパラメタは、HELLOパケットの交換プロセスにおいて計算することができる。
【００７６】
本発明の実施例では、GTSの割り当てが分散型であり、各ノードは、その親ノードへのリンクのみにGTSを予約してもよい。各ノードは、その衝突域内の全ての他のノードの情報を取集し、そして、該情報に基づいてGTSを選択する。その後、その1-hopノードに、その選択したGTSをブロードキャストし、そして、隣接ノードからのコメント（意見）を待つ。隣接ノードから拒否のコメントがあれば、それは、他のGTSを再び選択する必要がある。各ノードは、全てのノードがGTSの割り当てについて一致したコメント（意見）を達成するまでに、該分散型プロセスを繰り返す。そのうち、情報収集及びGTSネゴーシエイションは、すべて、HELLOパケットのブロードキャストにより実現される。図2を再び参照するに、CAP周期は、CSMAによりアクセスされ、CFP周期は、TDMAによりアクセスされる。本発明の実施例では、HELLOパケットがCAP周期内にブロードキャストされ、これによって、CFP内のタイムスロットは、ツリートポロジーの各ノードの間に適切に割り当てることができる。
【００７７】
このプロセスをサポートするために、各ノードは、一つのGTS表を上述のように維持する必要があり、図4に示す一例のようであるので、ここでは詳しい説明を省略する。
【００７８】
また、各ノードは更に、所要（必要）なGTSを記録してもよく、一例では、6つの要素を上述のように含み、図6に示す一例のようであるので、ここでは詳しい説明を省略する。
【００７９】
本実施例では、公式（8）に基づいてトラフィックを計算する一例は、図14に示すようであり、各センサノードについて、トラフィックの計算プロセスは、次のステップを含む。
【００８０】
ステップ1401：一つ目の記録からGTS表をスキャンし；
ステップ1402：“Rxi”がローカルノードであれば、ローカルノードのトラフィックに“Ti”を加算し；
ステップ1403：該記録が最後の一つである場合、ステップ1404に進み、そうでない場合、次の記録に進み、ステップ1402に戻り；
ステップ1404：Tiに1を加算し、トラフィックの計算が完成する。
【００８１】
本実施例では、公式（9）に基づいて、シンクノードを囲む衝突域内のトラフィックを計算する一例は、図15に示されるようである。該シンクノードについて、そのトラフィックは0であり、衝突域内のトラフィックの計算プロセスは、次のステップを含む。
【００８２】
ステップ1501：TCD-sinkを0に設定し、一つ目の記録からGTS表をスキャンし；
ステップ1502：TCD-sinkに“Ti”を加算し；
ステップ1503：該記録が最後の一つであれば、計算が修了し、そうでなければ、次の記録に進み、ステップ1502に戻る。
【００８３】
本発明の実施例では、シンクノードを囲むの衝突域内のトラフィック、必要なGTS、及び衝突域内の隣接ノードの情報は、すべて、HELLOパケット中に携帯され、全ての1-hop隣接ノードにブロードキャストされる。HELLOパケットのフォーマットは、図8に示すようである。
【００８４】
ノードiについては、HELLOパケットのブロードキャストのプロセスは、図16に示すようである。
【００８５】
ステップ1601：GTS表をスキャンしてそのトラフィックを計算し、そして、それを、リクエストされたGTSの記録に添加し；
ステップ1602：公式（7）により、“exp”を計算し；
ステップ1603：“exp”の増量が1よりも大きい場合、又は、その所要なGTSの状態が無効（“invalid”）である場合、GTSを選択し、その後、ステップ1607を実行し、そうでない場合、直接ステップ1607を実行し、そのうち、GTSの選択方式は、上述のようであるため、ここでは詳しい説明を省略し；
ステップ1604：HELLOパケットを形成し、“Source  addr”をそのアドレスに設定し、“Destination  addr”をブロードキャストアドレスに設定し、全ての1-hop隣接ノードのGTSの記録をHELLOパケットにコピーし、各2、…、（n-1）ホップ隣接ノードのGTSの記録について、確認情報が同意であれば、それをHELLOパケットにコピーし；
ステップ1605：それがシンクノードであれば、TCD-sinkを計算し、そして、それをHELLOパケットにコピーし、シンクノードでなければ、ローカルに記録されたTCD-sinkをHELLOパケットにコピーし、また、所要なGTSをHELLOパケットにコピーし；
ステップ1606：HELLOパケットを送信する。
【００８６】
本発明の実施例では、１ホップノードからHELLOパケットを受信すると、該ノードは、TCD-sinkを更新し、ローカルGTS表を更新し、そして、HELLOパケットの送信元にリクエストされたGTSについて意見（コメント）を与える。各ノードについて、HELLOパケットの受信プロセスは、図17に示すようである。
【００８７】
ステップ1701：HELLOパケット内のTCD-sinkがローカルTCD-sinkよりも大きい場合、ローカルTCD-sinkを更新し；
ステップ1702：HELLOパケットの送信元の、ローカルにリクエストされたGTSへの確認意見をチェックし；
ステップ1703：HELLOパケット中のGTS表を、ローカルGTS表に合併し；
ステップ1704：HELLOパケットの送信元にリクエストされたGTSについて意見を与える。
【００８８】
ステップ1704では、HELLOパケットの送信元にリクエストされたGTSが、ローカルノードの受信に影響を与えるかどうかをチェックし、及び、ローカルノードの伝送が、HELLOパケットの送信元にリクエストされたGTSに影響を与えるかどうかをチェックすることにより、HELLOパケットの送信元にリクエストされたGTSに意見を与える。
【００８９】
本発明の実施例では、任意の二つのGTS（GTS1及びGTS2を例とする）の衝突条件を与える。
【００９０】
（1）Rx1が、Tx2の1、2、…、（n-1）ホップ隣接ノードに属し、又は、Rx2は、Tx1の1、2、…、（n-1）ホップ隣接ノードに属し；
（2）|offset1-offset2|mod2exp1が0であり、又は、|offset1-offset2|mod2exp2が0である。
【００９１】
以上の二つの条件を満足する時に、衝突が存在すると見なす。
【００９２】
以下、“ローカルにリクエストされたGTSへの意見のチェック”の一例を挙げる。HELLOパケット中のGTS表中の記録をスキャンし、任意のGTSiについて、
“Txi”がローカルノードIDに等しい場合、
Commentiが拒否であれば、
ローカルにリクエストされたGTSが無効であり；
Commentiが同意であれば、
何もしない。
【００９３】
“Txi”がローカルノードIDに等しいときに、該記録が、ローカルにリクエストされたGTSに対応すると見なし、該記録のCommentiが拒否であれば、該HELLOパケットの送信元の、ローカルにリクエストされたGTSへの意見が拒否であると見なし、この場合、ローカルにリクエストされたGTSを無効に変更し、該記録のCommentiが同意であれば、この時に、何もしない。
【００９４】
以下、“GTS表の合併”の一例を挙げる。1-hop隣接ノードとして、HELLOパケットの送信元は、そのリクエストされたGTSを直接報告することができ、しかし、2ホップ及び3-hop隣接ノードのGTS情報は、中間ノードにより転送される必要がある。GTS表の合併の目的は、１ホップ範囲以外の隣接ノードの最新のGTS情報を更新し、そして、それによる衝突を識別することにある。
【００９５】
GTS表合併の一つの実現方法は次に示すようである。HELLOパケット中のGTS表の各記録をスキャンし、該表中の任意の一つのGTSiについて、
GTSiの意見commentiが同意である場合、
GTSiが既にローカルGTS表内にあれば、
HELLOパケット中のGTSiの距離distanceiがローカルGTS表中のGTSiの距離distanceiよりも小さいとき、
ローカル表中のGTSiをHELLOパケット中のGTSiに変え、そのうち、距離distanceiが、HELLOパケット中のGTSiの距離distanceiプラス1に等しく、GTSiについて意見を与え、
HELLOパケット中のGTSiの距離がローカルGTS表中のGTSiの距離以上であるとき、
GTSiについて何もせず、
GTSiがローカルGTS表中になければ、
GTSiをローカルGTS表に添加し、ローカルGTSiの距離が、HELLOパケット中のGTSiの距離プラス1に等しく、GTSiについて意見を与える。
【００９６】
以下、“意見付与（与える）”の一例を挙げる。本発明の実施例は、分散型方式で行われるので、一つのノードは、その衝突域内の任意の他のノードのGTSについて意見を与えることができる。しかし、各ノードは、自分の送信及び受信が影響を受けるかどうかのみに関心を持つ。衝突を検出すると、小さいTx  IDを有するGTSが拒否され、一つのノードは、それにリクエストされたGTSが拒絶されたことを発見すれば、該ノードは、一つの新しいGTSを選択することができる。該方法は、衝突域内の無衝突の受信/伝送を保証することができる。GTSiについて意見を与えるプロセスは、次のステップを含む。
【００９７】
ステップ1：ローカルGTS表をスキャンし、各GTSjについて、
意見commentjが同意であり、且つ、RxjがローカルノードIDに等しい場合、ローカルノードの受信がGTSiの影響を受けるかどうかを決定し、衝突条件に基づいてGTSi及びGTSjをチェックし、
衝突が存在する場合、
Txi>Txjのとき、GTSiについて同意の意見を与え、GTSjについて拒否の意見を与え、
Txi<Txjのとき、GTSiについて拒否の意見を与え、GTSjについて同意の意見を与える。
【００９８】
ステップ2：ローカルにリクエストされたGTSが有効の場合、ローカルノードの伝送がGTSiに影響を与えるかどうかを決定し、衝突条件に基づいてローカルにリクエストされたGTS及びGTSiをチェックし、
衝突が存在する場合、
ローカルノードID>Txiのとき、GTSiについて拒否の意見を与え、
ローカルノードID<Txiのとき、GTSiについて同意の意見を与え、且つ、ローカルにリクエストされたGTSの状態を無効（invalid）に設定する。
【００９９】
ステップ3：ステップ1及びステップ2では衝突が存在しない場合、GTSiについて同意の意見を与える。
【０１００】
該例では、衝突が発生した場合、小さいTx  IDを有するGTSが拒絶される。なお、他の認証方法により実現することもでき、例えば、受信した一つ目のGTSについて同意の意見を与えるなどであり、本実施例は、これに限定されない。
【０１０１】
本実施例では、各ノードについて、次の二つの条件に基づいて一つの新しいGTSを選択してもよい。
【０１０２】
1）TCD-sinkの増加又はローカルトラフィックの増加が所定閾値よりも大きく（リクエストされたGTSの周期が変化している）；
2）現在のGTSが無効である。
【０１０３】
一つのノードは、自分のトラフィックに適切なGTSを選択することにより、その衝突域内の他のノードからの衝突を避けることができる。上述のように、各ノードがGTS二分木を構成し、各ノードは、該ツリーから、その衝突域内の他のノードのGTSと衝突することがない空きGTSを選択する。
【０１０４】
そのうち、GTSの選択を実現する一例は、次のようである。
【０１０５】
ステップ1：公式（7）に基づいて、expを計算し；
ステップ2：周期が2expに等しい行の上で、左から右へGTS二分木をサーチし、最も左側の無衝突GTSを見つける。
【０１０６】
無衝突GTSとは、1）該GTSは、衝突域内の他のノードにより占用されず；2）該GTSは、該GTS二分木において衝突域内の他のノードにより占用されるGTSの祖先又は子孫でない。
【０１０７】
ステップ2では、他のGTS選択方法を同様に適用し得る。例えば、1）右から左へGTSを選択し；2）その親ノードに比べ、小さいオフセットを有するGTSを選択してもよい。
【０１０８】
図18a及び図18bは、本発明の実施例における方法と、従来の連続タイムスロット割り当て方法とのパフォーマンズ比較図である。図18a及び図18bに示すように、最も左側の適切なGTSが選択され、これにより、GTSは、できるだけ、異なる域においてノードにより共用される。該方法は、タイムスロットの異なる空間の重複利用率を大幅に向上させることができる。各ノードは、そのトラフィック及びネットワーク中のトラフィックロード条件に基づいて、適切な数のタイムスロットを選択し、これにより、タイムスロット利用率をも向上させることができる。該方法のパフォーマンスは、従来の連続タイムスロット割り当て方法に比べ、両方法が１００％のパケット到着率を実現する時に、本発明の実施例における方法は、連続タイムスロット割り当て方法に比べ、より小さい平均時間遅延を有する。
【０１０９】
本発明の実施例が提供するタイムスロット割り当て方法は、分散型である。集中型タイムスロット割り当て方法に比べ、中央制御ユニットを要しない。また、本発明の実施例が提供するタイムスロット割り当て方法は、周期的なタイムスロット割り当て方法であり、異なるノードについて周期が異なる。従来のタイムスロット割り当て方法に比べ、該方法では、該周期が各ノードのトラフィックに比例し、一つの利点としては、幾つかのノードが占用しているタイムスロットが多過ぎて且つその一部が必要とされず、又は、幾つかのノードが占用しているタイムスロットが足りていないとのような状況が発生しないことがあり、一つの結果としては、本発明の実施例が提供するタイムスロット割り当て方法において、タイムスロット利用率が非常に高いことがある。また、全ての周期的なGTSはツリー型に従って組織される。GTSの選択及びGTSの衝突の検出がGTS二分木に基づくので、計算複雑度が低い。また、各ノードが最も左側の空きGTSを選択し、これにより、一つのGTSは、最大限で、異なる衝突域において重複使用され得る。このような高タイムスロット重複使用率は、タイムスロットの使用率をも向上させることができる。
【０１１０】
本発明の実施例は更に、マルチホップネットワーク中のノードを次の実施例2に記載のように提供し、該ノードが問題を解決する原理は、実施例1に記載の方法に類似するので、その具体的な実施は、実施例1の方法の実施を参照することができるため、内容が同じ処の記載を省略する。
【実施例２】
【０１１１】
本発明の実施例は、ノード（装置）を提供する。図19は、該ノードの構成図であり、図19に示すように、該ノードは、第一形成ユニット191、記憶ユニット192、第二形成ユニット193及びブロードキャストユニット194を含む。
【０１１２】
第一形成ユニット191は、GTS二分木を形成する。
【０１１３】
記憶ユニット192は、前記第一形成ユニットが形成したGTS二分木を記憶し、また、予めローカルノードの衝突域内の全ての隣接ノードのGTSリクエスト情報、及び、ローカルノードの予約履歴情報を記憶する。オプションで、該記憶ユニット192は更に、シンクノードの衝突域内のトラフィックを記憶してもよい。
【０１１４】
第二形成ユニット193は、HELLOパケットを形成し、前記HELLOパケットは、ローカルノードのGTSリクエスト情報を含み、又は、ローカルノードのGTSリクエスト情報及びローカルノードの衝突域内の少なくとも一つの隣接ノードのGTSリクエスト情報を含む。
【０１１５】
ブロードキャストユニット194は、前記第二形成ユニットが形成したHELLOパケットをブロードキャストし、該HELLOパケットを受信したノードに、前記HELLOパケットに含まれている情報に基づいて、タイムスロット予約を行わせる。
【０１１６】
本実施例では、第一形成ユニット191がGTS二分木を形成する時に、公式GTS=(2exp,offset)に基づいてGTS二分木の根Root=(20,0)を生成し、そのうち、exp=0、offset=0であり；公式GTSleft-child=(2exp+1,offset)に基づいて各GTSの一つの左の子GTSを生成し；公式GTSright-child=(2exp+1,offset+2exp)に基づいて各GTSの一つの右の子GTSを生成し；前記GTS二分木の根、前記各GTSの左の子GTS、及び前記各GTSの右の子GTSから、上述のGTS二分木を形成する。
【０１１７】
本実施例では、記憶ユニット192が記憶する隣接ノードのGTSリクエスト情報は、記録の方式で記憶され、各記録は、一つの隣接ノードに対応し、該隣接ノードのアドレス、該隣接ノードのシンクノードに到着するネクストホップノードのアドレス、該隣接ノードにリクエストされたGTSの周期のべき乗、該隣接ノードにリクエストされたGTSのオフセット、該隣接ノードのトラフィック、該隣接ノードのローカルノードに到着する距離/ホップ数、及び、該隣接ノードにリクエストされたGTSの確認情報を含む。
【０１１８】
本実施例では、記憶ユニット192が記憶するローカル予約履歴情報は、ローカルノードのアドレス、ローカルノードのシンクノードに到着するネクストホップノードのアドレス、ローカルにリクエストされたGTSの周期のべき乗、ローカルにリクエストされたGTSのオフセット、及び、ローカルトラフィックを含む。オプションで、更に、ローカルにリクエストされたGTSの状態を含む。
【０１１９】
本実施例では、第二形成ユニット193は、第一選択モジュール1931及び第一確定モジュール1932を含む。
【０１２０】
第一選択モジュール1931は、所定策略に基づいて、ローカルGTS表から一部の記録を前記隣接ノードのGTSリクエスト情報として選択する。
【０１２１】
第一確定モジュール1932は、リクエストされたGTSを確定し、リクエストされたGTSに対応する情報を前記GTSリクエスト情報とする。
【０１２２】
そのうち、第一選択モジュール1931は、ローカルノードの衝突域内の隣接ノードの最大ホップ数がnである時に、前記ローカルGTS表中のローカルノードの衝突域内の全ての1-hop隣接ノードの記録、及び、2-hop隣接ノード乃至“n-1”-hop隣接ノードの記録のうち確認情報が同意である記録を前記隣接ノードのGTSリクエスト情報として選択し；又は、前記ローカルGTS表中の全ての1-hop隣接ノード乃至“n-1”-hop隣接ノードの記録を前記隣接ノードのGTSリクエスト情報とする。
【０１２３】
そのうち、第一確定モジュール1932は、第一計算モジュール19321、第一判断モジュール19322、第一処理モジュール19323を含む。
【０１２４】
第一計算モジュール19321は、リクエストされたGTSの周期を計算する。
【０１２５】
第一判断モジュール19322は、ローカルに保存されている予約履歴情報に基づいて、リクエストされたGTSの周期が変化しているかどうか、及び/又は、GTSの状態が無効であるかどうかを判断する。
【０１２６】
第一処理モジュール19323は、リクエストされたGTSの周期が変化しており、又は、GTSの状態が無効である時に、GTSを選択し、選択したGTSの関連情報を前記リクエストされたGTSとし；リクエストされたGTSの周期が変化しておらず、且つGTSの状態が有効である時に、予約履歴情報中のリクエストされたGTSの関連情報を前記リクエストされたGTSとする。
【０１２７】
そのうち、第一計算モジュール19321は先ず、ローカルノードのトラフィックを計算し、その後、ローカルに保存されているシンクノードの衝突域内の総トラフィック及び算出されたローカルノードのトラフィックに基づて、次の公式により、リクエストされたGTSの周期を計算する。
【数１４】
2015056893.tif 000019
【０１２８】
そのうち、
（外４）
2015056893.tif 000020
であり、xは、整数であり、TCD-sinkは、シンクノードの衝突域内の総トラフィックであり、Tiは、ローカルノードのトラフィックであり、2expは、リクエストされたGTSの周期である。
【０１２９】
そのうち、第一計算モジュール19321は、ローカルGTS表の各記録をスキャンし、前記記録のうち、受信ノードがローカルノードである記録に対応するトラフィックをローカルノードのトラフィックに加入し、ローカルノードのトラフィックを取得する。
【０１３０】
そのうち、第一処理モジュール19323は、GTSを選択する時に、算出された、リクエストされたGTSの周期に応じて、所定策略に基づいて、ローカルに形成されたGTS二分木をサーチし、前記リクエストされたGTSの周期が所在する行の上での一つ目の空きGTSを選択し、又は、GTSのオフセットがその受信ノードのGTSのオフセットよりも小さいGTSを選択する。
【０１３１】
そのうち、前記所定策略は、左から右へローカルに形成されたGTS二分木をサーチし、又は、右から左へローカルに形成されたGTS二分木をサーチするというものである。
【０１３２】
そのうち、記憶ユニット192は更に、シンクノードの衝突域内の総トラフィックを記憶し、前記HELLOパケットは更に、シンクノードの衝突域内の総トラフィックを含み、第二形成ユニット193は、第二判断モジュール1933、第二計算モジュール1934、及び第二処理モジュール1935を含む。
【０１３３】
第二判断モジュール1933は、ローカルノードがシンクノードであるかどうかを判断する。
【０１３４】
第二計算モジュール1934は、ローカルノードがシンクノードである時に、シンクノードの衝突域内の総トラフィックを計算し、計算により得たシンクノードの衝突域内の総トラフィックを前記HELLOパケットに加入する。
【０１３５】
第二処理モジュール1935は、ローカルノードがシンクノードでない時に、ローカルに保存されたシンクノードの衝突域内の総トラフィックを前記HELLOパケットに加入する。
【０１３６】
そのうち、第二計算モジュール1934は、ローカルGTS表の各記録を遍歴（スキャン）し、各記録に対応するトラフィックをシンクノードの衝突域内の総トラフィックに加入することにより、シンクノードの衝突域内の総トラフィックを得る。
【０１３７】
本実施例では、前記ノードは更に次のものを含む。
【０１３８】
処理ユニット195：更新モジュール1951、及び/又は、判定モジュール1952、及び/又は、合併モジュール1953、及び/又は、認証モジュール1954を含んでもよい。そのうち、更新モジュール1951は、受信したHELLOパケットに基づいて、シンクノードの衝突域内の総トラフィックを更新する。判定モジュール1952は、HELLOパケットの送信元の、ローカルにリクエストされたGTSへの認証結果を確定する。合併モジュール1953は、HELLOパケット中のGTS表と、ローカルGTS表とを合併する。認証モジュール1954は、HELLOパケットの送信元にリクエストされたGTSに対して認証を行う。
【０１３９】
そのうち、前記更新モジュール1951は、前記HELLOパケット中のシンクノードの衝突域内の総トラフィックが、ローカルに保存されているシンクノードの衝突域内の総トラフィックよりも大きい時に、ローカルに保存されているシンクノードの衝突域内のトラフィックを更新し、そうでない場合、ローカルに保存されているシンクノードの衝突域内のトラフィックを不変にさせる。
【０１４０】
そのうち、前記判定モジュール1952は、HELLOパケットのGTS表の各記録をスキャンし、送信ノードのアドレスがローカルノードのアドレスである記録を見つけ；該記録の確認情報が拒否である時に、ローカルにリクエストされたGTSが無効であると確定し、この時に、ローカル予約履歴情報を変更してもよく；該記録の確認情報が同意である時に、ローカルにリクエストされたGTSが有効であると確定し、この時に、ローカルにリクエストされたGTSの状態を不変にさせる。
【０１４１】
そのうち、前記合併モジュール1953は、HELLOパケット中のGTS表のうち、確認情報が同意である記録を、ローカルGTS表に合併し；そのうち、ローカルGTS表には前記確認情報が同意である記録を記憶したことがあれば、前記処理ユニットは、該記録の距離がローカルGTS表中の対応する記録の距離よりも小さい時に、HELLOパケット中の該記録を以てローカルGTS表中の対応する記録を置換し、且つ、該記録の距離に1を加算し；そのうち、ローカルGTS表には前記確認情報が同意である記録を記憶したことがなければ、前記処理ユニットは、該記録をローカルGTS表に添加し、該記録の距離に1を加算する。
【０１４２】
そのうち、前記認証モジュール1954は、ローカル受信干渉検出を行い、前記HELLOパケットの送信元にリクエストされたGTSが、ローカルノードを受信ノードとする隣接ノードにリクエストされたGTSと衝突するかどうかを確定し；また、ローカル送信干渉検出を行い、前記HELLOパケットの送信元にリクエストされたGTSが、ローカルにリクエストされたGTSと衝突するかどうかを確定し；両者には衝突がない場合、HELLOパケットの送信元にリクエストされたGTSについて同意を付与し；衝突が存在する場合、HELLOパケットの送信元のアドレスが前記隣接ノードのアドレスよりも大きいとき、又は、HELLOパケットの送信元のアドレスがローカルノードのアドレスよりも大きいとき、HELLOパケットの送信元にリクエストされたGTSについて同意を付与し、そうでない場合、HELLOパケットの送信元にリクエストされたGTSについて拒否を付与する。
【０１４３】
本発明の実施例が提供するノードにより、タイムスロット割り当ての計算複雑度を低減し、タイムスロットの利用率を向上させることができる。
【０１４４】
本発明の上述の装置及び方法は、ハードウェアにより実現されてもよく、ハードウェアとソフトウェアとの組み合わせにより実現されてもよい。また、本発明は、このようなコンピュータ可読なプログラムにも関し、即ち、該プログラムは、ロジック部により実行されている時に、該ロジック部に、上述の装置又は構成部品を実現させることができ、又は、該ロジック部に、上述の各種方法又はステップを実現させることができる。本発明は、さらに、上述のプログラムを記録している記憶媒体、例えば、ハードディスク、磁気ディスク、光ディスク、DVD、flashメモリなどにも関する。
【０１４５】
また、上述の各実施例を含む実施形態に関し、更に以下の付記を開示する。
【０１４６】
（付記1）
タイムスロット割り当て方法であって、
HELLOパケットを形成し、前記HELLOパケットは、ローカルノードのGTSリクエスト情報を含み、又は、ローカルノードのGTSリクエスト情報及びローカルノードの衝突域内の少なくとも一つの隣接ノードのGTSリクエスト情報を含み；及び
前記HELLOパケットをブロードキャストし、前記HELLOパケットを受信したノードに、前記HELLOパケットに含まれている情報に基づいて、タイムスロット予約を行わせることを含む、方法。
【０１４７】
（付記2）
付記1に記載の方法であって、
HELLOパケットを形成するステップは、
所定策略に基づいて、ローカルGTS表から、一部の記録を前記隣接ノードのGTSリクエスト情報として選択し；及び
リクエストされたGTSを確定し、リクエストされたGTSに対応する情報を前記GTSリクエスト情報をすることを含む、方法。
【０１４８】
（付記3）
付記2に記載の方法であって、
ローカルノードの衝突域内の隣接ノードの最大ホップ数がnであるときに、所定策略に基づいてローカルGTS表から一部の記録を前記隣接ノードのGTSリクエスト情報として選択するステップは、
前記ローカルGTS表中のローカルノードの衝突域内の全ての1-hop隣接ノードの記録、及び、2-hop隣接ノード乃至“n-1”-hop隣接ノードの記録のうち確認情報が同意である記録を前記隣接ノードのGTSリクエスト情報とし；又は
前記ローカルGTS表中の全ての1-hop隣接ノード乃至“n-1”-hop隣接ノードの記録を前記隣接ノードのGTSリクエスト情報とすることを含む、方法。
【０１４９】
（付記4）
付記2に記載の方法であって、
リクエストされたGTSを確定するステップは、
リクエストされたGTSの周期を計算し；
ローカルに保存されている予約履歴情報に基づいて、リクエストされたGTSの周期が変化しているかどうか、及び/又は、GTSの状態が無効であるかどうかを判断し；
リクエストされたGTSの周期が変化しており、又は、GTSの状態が無効であれば、GTSを選択し、選択したGTSの関連情報を前記リクエストされたGTSとし；及び
リクエストされたGTSの周期が変化しておらず、且つ、GTSの状態が有効であれば、予約履歴情報中のリクエストされたGTSの関連情報を前記リクエストされたGTSとすることを含む、方法。
【０１５０】
（付記5）
付記4に記載の方法であって、
リクエストされたGTSの周期を計算するステップは、
ローカルノードのトラフィックを計算し；
ローカルに保存されているシンクノードの衝突域内の総トラフィック、及び、算出されたローカルノードのトラフィックに基づいて、以下の公式で、リクエストされたGTSの周期を計算し：
【数１５】
2015056893.tif 000021
そのうち、
（外５）
2015056893.tif 000022
であり、xは、整数であり、TCD-sinkは、シンクノードの衝突域内の総トラフィックであり、Tiは、ローカルノードのトラフィックであり、2expは、リクエストされたGTSの周期である、方法。
【０１５１】
（付記6）
付記5に記載の方法であって、
ローカルノードのトラフィックを計算するステップは、
ローカルGTS表の各記録を遍歴し；及び
前記記録のうちの、受信ノードがローカルノードである記録に対応するトラフィックをローカルノードのトラフィックに加入し、ローカルノードのトラフィックを得ることを含む、方法。
【０１５２】
（付記7）
付記4に記載の方法であって、
GTSを選択するステップは、
算出された、リクエストされたGTSの周期に応じて、所定策略に基づいてローカルに形成されたGTS二分木をサーチし、前記リクエストされたGTSの周期が所在する行の上での一つ目の空きGTSを選択し、又は、GTSのオフセットがその受信ノードのGTSのオフセットよりも小さいGTSを選択することを含む、方法。
【０１５３】
（付記8）
付記7に記載の方法であって、
前記所定策略は、左から右へローカルに形成されたGTS二分木をサーチし、又は、右から左へローカルに形成されたGTS二分木をサーチするというものである、方法。
【０１５４】
（付記9）
付記1に記載の方法であって、
前記HELLOパケットは更に、シンクノードの衝突域内の総トラフィックを含み、前記HELLOパケットを形成するステップは更に、
ローカルノードがシンクノードであるかどうかを判断し；
ローカルノードがシンクノードであれば、シンクノードの衝突域内の総トラフィックを計算し、計算により得たシンクノードの衝突域内の総トラフィックを前記HELLOパケットに加入し；及び
ローカルノードがシンクノードでなければ、ローカルに保存されているシンクノードの衝突域内の総トラフィックを前記HELLOパケットに加入することを含む、方法。
【０１５５】
（付記10）
付記9に記載の方法であって、
シンクノードの衝突域内の総トラフィックを計算するステップは、
ローカルGTS表の各記録を遍歴し；及び
各記録に対応するトラフィックをシンクノードの衝突域内の総トラフィックに加入し、シンクノードの衝突域内の総トラフィックを得ることを含む、方法。
【０１５６】
（付記11）
付記1に記載の方法であって、更に
GTS二分木を生成することを含み、具体的に、
公式GTS=(2exp,offset)に基づいてGTS二分木の根Root=(20,0)を生成し、そのうち、exp=0、offset=0であり；
公式GTSleft-child=(2exp+1,offset)に基づいて、各GTSの一つの左の子GTSを生成し；
公式GTSright-child=(2exp+1,offset+2exp)に基づいて、各GTSの一つの右の子GTSを生成し；及び
前記GTS二分木の根、前記各GTSの左の子GTS及び前記各GTSの右の子GTSから、前記GTS二分木を形成することを含む、方法。
【０１５７】
（付記12）
付記1に記載の方法であって、
受信したHELLOパケットに基づいて、シンクノードの衝突域内の総トラフィックを更新し；及び/又は、HELLOパケットの送信元の、ローカルにリクエストされたGTSへの認証結果を確定し；及び/又は、HELLOパケット中のGTS表と、ローカルGTS表とを合併し；及び/又は、HELLOパケットの送信元にリクエストされたGTSに対して認証を行うことを含む、方法。
【０１５８】
（付記13）
付記12に記載の方法であって、
シンクノードの衝突域内の総トラフィックを更新するステップは、
HELLOパケット中のシンクノードの衝突域内の総トラフィックが、ローカルに保存されているシンクノードの衝突域内の総トラフィックよりも大きい場合、ローカルに保存されているシンクノードの衝突域内のトラフィックを更新し、そうでない場合、ローカルに保存されれているシンクノードの衝突域内のトラフィックを不変にさせることを含む、方法。
【０１５９】
（付記14）
付記12に記載の方法であって、
HELLOパケットの送信元の、ローカルにリクエストされたGTSへの認証結果を確定するステップは、
HELLOパケットのGTS表の各記録をスキャンし、送信ノードのアドレスがローカルノードのアドレスである記録を見つけ；
該記録の確認情報が拒否であれば、ローカルにリクエストされたGTSが無効であると確定し；及び
該記録の確認情報が同意であれば、ローカルにリクエストされたGTSが有効であると確定することを含む、方法。
【０１６０】
（付記15）
付記12に記載の方法であって、
HELLOパケット中のGTS表と、ローカルGTS表とを合併するステップは、
HELLOパケット中のGTS表のうち確認情報が同意である記録を、ローカルGTS表に合併することを含み、
ローカルGTS表には、前記確認情報が同意である記録を記憶している場合、該記録の距離が、ローカルGTS表中の対応する記録の距離よりも小さい時に、HELLOパケット中の該記録を以て、ローカルGTS表中の対応する記録を置換し、該記録の距離に1を加算し；
ローカルGTS表には、前記確認情報が同意である記録を記憶していない場合、該記録をローカルGTS表に追加し、該記録の距離に1を加算する、方法。
【０１６１】
（付記16）
付記12に記載の方法であって、
HELLOパケットの送信元にリクエストされたGTSに対して認証を行うステップは、
ローカル受信干渉検出を行い、前記HELLOパケットの送信元にリクエストされたGTSが、ローカルノードを受信ノードとする隣接ノードにリクエストされたGTSと衝突するかどうかかを確定し；
ローカル送信干渉検出を行い、前記HELLOパケットの送信元にリクエストされたGTSが、ローカルにリクエストされたGTSと衝突するかどうかを確定し；
衝突が存在しなければ、HELLOパケットの送信元にリクエストされたGTSについて同意を付与し；及び
衝突が存在すれば、HELLOパケットの送信元のアドレスが前記隣接ノードのアドレスよりも大きい場合、又は、HELLOパケットの送信元のアドレスがローカルアドレスよりも大きい場合、HELLOパケットの送信元にリクエストされたGTSについて同意を付与し、そうでない場合、HELLOパケットの送信元にリクエストされたGTSについて拒否を付与することを含む、方法。
【０１６２】
（付記17）
ノードであって、
GTS二分木を形成する第一形成ユニット；
前記第一形成ユニットが形成したGTS二分木を記憶し、また、予めローカル衝突域内の全ての隣接ノードのGTSリクエスト情報、及び、ローカルノードの予約履歴情報を記憶する記憶ユニット；
ローカルノードのGTSリクエスト情報を含み、又は、ローカルノードのGTSリクエスト情報及びローカルノードの衝突域内の少なくとも一つの隣接ノードのGTSリクエスト情報を含むHELLOパケットを形成する第二形成ユニット；及び
前記第二形成ユニットが形成したHELLOパケットをブロードキャストし、該HELLOパケットを受信したノードに、前記HELLOパケットに含まれている情報に基づいて、タイムスロット予約を行わせるブロードキャストユニットを含む、ノード。
【０１６３】
（付記18）
付記17に記載のノードであって、
前記隣接ノードのGTSリクエスト情報は、記録の方式で記憶され、各記録は、一つの隣接ノードに対応し、該隣接ノードのアドレス、該隣接ノードのシンクノードに到着するネクストホップノードのアドレス、該隣接ノードにリクエストされたGTSの周期のべき乗、該隣接ノードにリクエストされたGTSのオフセット、該隣接ノードのトラフィック、該隣接ノードのローカルノードに到着する距離/ホップ数、及び、該隣接ノードにリクエストされたGTSの確認情報を含む、ノード。
【０１６４】
（付記19）
付記17に記載のノードであって、
前記ローカル予約履歴情報は、ローカルアドレス、ローカルノードのシンクノードに到着するネクストホップノードのアドレス、ローカルにリクエストされたGTSの周期のべき乗、ローカルにリクエストされたGTSのオフセット、及び、ローカルトラフィックを含む、ノード。
【０１６５】
（付記20）
付記19に記載のノードであって、
前記ローカル予約履歴情報は更に、ローカルにリクエストされたGTSの状態を含む、ノード。
【０１６６】
（付記21）
付記17に記載のノードであって、
前記第二形成ユニットは、
所定策略に基づいてローカルGTS表から一部の記録を前記隣接ノードのGTSリクエスト情報として選択する第一選択モジュール；及び
リクエストされたGTSを確定し、リクエストされたGTSに対応する情報を前記GTSリクエスト情報とする第一確定モジュールを含む、ノード。
【０１６７】
（付記22）
付記21に記載のノードであって、
前記第一選択モジュールは、ローカルノードの衝突域内の隣接ノードの最大ホップ数がnである時に、前記ローカルGTS表中のローカルノードの衝突域内の全ての1-hop隣接ノードの記録、及び、2-hop隣接ノード乃至“n-1”-hop隣接ノードの記録のうち、確認情報が同意である記録を前記隣接ノードのGTSリクエスト情報とし；又は、前記ローカルGTS表中の全ての1-hop隣接ノード乃至“n-1”-hop隣接ノードの記録を前記隣接ノードのGTSリクエスト情報とする、ノード。
【０１６８】
（付記23）
付記21に記載のノードであって、
前記第一確定モジュールは、
リクエストされたGTSの周期を計算する第一計算モジュール；
ローカルに保存されている予約履歴情報に基づいて、リクエストされたGTSの周期が変化しているかどうか、及び/又は、GTSの状態が無効であるかどうかを判断する第一判断モジュール；及び
リクエストされたGTSの周期が変化しており、又は、GTSの状態が無効であるときに、GTSを選択し、選択したGTSの関連情報を前記リクエストされたGTSとし；リクエストされたGTSの周期が変化しておらず、且つ、GTSの状態が有効であるときに、予約履歴情報中のリクエストされたGTSの関連情報を前記リクエストされたGTSとする、第一処理モジュールを含む、ノード。
【０１６９】
（付記24）
付記23に記載のノードであって、
前記第一計算モジュールは、ローカルノードのトラフィックを計算し、ローカルに保存されているシンクノードの衝突域内の総トラフィック、及び、計算されたローカルノードのトラフィックを用いて、以下の公式で、リクエストされたGTSの周期を計算し、
【数１６】
2015056893.tif 000023
そのうち、
（外６）
2015056893.tif 000024
であり、xは、整数であり、TCD-sinkは、シンクノードの衝突域内の総トラフィックであり；Tiは、ローカルノードのトラフィックであり、2expは、リクエストされたGTSの周期である、ノード。
【０１７０】
（付記25）
付記24に記載のノードであって、
前記第一計算モジュールは、ローカルGTS表の各記録を遍歴し、前記記録のうち、受信ノードがローカルノードである記録に対応するトラフィックをローカルノードのトラフィックに加入し、ローカルノードのトラフィックを得る、ノード。
【０１７１】
（付記26）
付記23に記載のノードであって、
前記第一処理モジュールは、GTSを選択する時に、対応するように、リクエストされたGTSの周期を計算し、所定策略に基づいてローカルに形成されたGTS二分木をサーチし、前記リクエストされたGTSの周期が所在する行の上での一つ目の空きGTSを選択し、又は、GTSのオフセットがその受信ノードのGTSのオフセットよりも小さいGTSを選択する、ノード。
【０１７２】
（付記27）
付記26に記載のノードであって、
前記所定策略は、左から右へローカルに形成されたGTS二分木をサーチし、又は、右から左へローカルに形成されたGTS二分木をサーチするというものである、ノード。
【０１７３】
（付記28）
付記17に記載のノードであって、
前記記憶ユニットは更に、シンクノードの衝突域内の総トラフィックを記憶し、前記HELLOパケットは更に、シンクノードの衝突域内の総トラフィックを含み、前記第二形成ユニットは、
ローカルノードがシンクノードであるかどうかを判断する第二判断モジュール；
ローカルノードがシンクノードである時に、シンクノードの衝突域内の総トラフィックを計算し、計算により得たシンクノードの衝突域内の総トラフィックを前記HELLOパケットに加入する第二計算モジュール；及び
ローカルノードがシンクノードでない時に、ローカルに保存されているシンクノードの衝突域内の総トラフィックを前記HELLOパケットに加入する第二処理モジュールを含む、ノード。
【０１７４】
（付記29）
付記28に記載のノードであって、
前記第二計算モジュールは、ローカルGTS表の各記録を遍歴し、各記録に対応するトラフィックをシンクノードの衝突域内のトラフィックに加入することにより、シンクノードの衝突域内のトラフィックを得る、ノード。
【０１７５】
（付記30）
付記17に記載のノードであって、
前記第一形成ユニットは、GTS二分木を形成する時に、公式GTS=(2exp,offset)に基づいてGTS二分木の根Root=(20,0)を生成し、そのうち、exp=0、offset=0であり；公式GTSleft-child=(2exp+1,offset)に基づいて、各GTSの一つの左の子GTSを生成し；公式GTSright-child=(2exp+1,offset+2exp)に基づいて、各GTSの一つの右の子GTSを生成し；前記GTS二分木の根、前記各GTSの左の子GTS、及び前記各GTSの右の子GTSから、前記GTS二分木を形成する、ノード。
【０１７６】
（付記31）
付記17に記載のノードであって、
処理ユニットを含み、前記処理ユニットは、更新モジュール、及び/又は、判定モジュール、及び/又は、合併モジュール、及び/又は、認証モジュールを含み、
更新モジュールは、受信したHELLOパケットに基づいて、シンクノードの衝突域内のトラフィックを更新し；
判定モジュールは、HELLOパケットの送信元の、ローカルリクエストされたGTSへの認証結果を確定し；
合併モジュールは、HELLOパケット中のGTS表と、ローカルGTS表とを合併し；
認証モジュールは、HELLOパケットの送信元にリクエストされたGTSに対して認証を行う、ノード。
【０１７７】
（付記32）
付記31に記載のノードであって、
前記更新モジュールは、前記HELLOパケット中のシンクノードの衝突域内の総トラフィックが、ローカルに保存されているシンクノードの衝突域内の総トラフィックよりも大きいときに、ローカルに保存されているシンクノードの衝突域内のトラフィックを更新し、そうでないときに、ローカルに保存されているシンクノードの衝突域内のトラフィックを不変にさせる、ノード。
【０１７８】
（付記33）
付記31に記載のノードであって、
前記判定モジュールは、HELLOパケットのGTS表の各記録をスキャンし、送信ノードのアドレスがローカルノードアドレスである記録を見つけ；該記録の確認情報が拒否であるときに、ローカルにリクエストされたGTSが無効であると確定し；該記録の確認情報が同意であるときに、ローカルにリクエストされたGTSが有効であると確定する、ノード。
【０１７９】
（付記34）
付記31に記載のノードであって、
前記合併モジュールは、HELLOパケット中のGTS表のうち、確認情報が同意である記録をローカルGTS表に合併し；ローカルGTS表には、前記確認情報が同意である記録を記憶していれば、前記処理ユニットは、該記録の距離がローカルGTS表中の対応する記録の距離よりも小さい時に、HELLOパケット中の該記録を以てローカルGTS表中の対応する記録を置換し、且つ該記録の距離に1を加算し；ローカルGTS表には前記確認情報が同意である記録を記憶していなければ、前記処理ユニットは、該記録をローカルGTS表に添加し、また、該記録の距離に1を加算する、ノード。
【０１８０】
（付記35）
付記31に記載のノードであって、
前記認証モジュールは、ローカル受信干渉検出を行い、前記HELLOパケットの送信元にリクエストされたGTSが、ローカルノードを受信ノードとするの隣接ノードにリクエストされたGTSと衝突するかどうかを確定し；また、ローカル送信干渉検出を行い、前記HELLOパケットの送信元にリクエストされたGTSが、ローカルにリクエストされたGTSと衝突するかどうかを確定し；両者には衝突がない場合、HELLOパケットの送信元にリクエストされたGTSについて同意を付与し；衝突がある場合、HELLOパケットの送信元のアドレスが前記隣接ノードのアドレスよりも大きいときに、又は、HELLOパケットの送信元のアドレスがローカルアドレスよりも大きいときに、HELLOパケットの送信元にリクエストされたGTSについて同意を付与し、そうでないときに、HELLOパケットの送信元にリクエストされたGTSについて拒否を付与する、ノード。
【０１８１】
以上、本発明の好ましい実施形態を説明したが、本発明はこの実施形態に限定されず、本発明の趣旨を離脱しない限り、本発明に対するあらゆる変更は本発明の技術的範囲に属する。
【図１】
2015056893.tif 000027
【図２】
2015056893.tif 000028
【図３】
2015056893.tif 000029
【図４】
2015056893.tif 000030
【図５】
2015056893.tif 000031
【図６】
2015056893.tif 000032
【図７】
2015056893.tif 000033
【図８】
2015056893.tif 000034
【図９】
2015056893.tif 000035
【図１０】
2015056893.tif 000036
【図１１】
2015056893.tif 000037
【図１２】
2015056893.tif 000038
【図１３】
2015056893.tif 000039
【図１４】
2015056893.tif 000040
【図１５】
2015056893.tif 000041
【図１６】
2015056893.tif 000042
【図１７】
2015056893.tif 000043
【図１８ａ】
2015056893.tif 000044
【図１８ｂ】
2015056893.tif 000045
【図１９】
2015056893.tif 000046