(57)【要約】【課題】本発明の実施例提供一種タイムスロット割り当て方法及び装置提供する。【解決手段】かかる方法は、HELLOパケットを形成し、前記HELLOパケットは、ローカルノードによりリクエストされた複数タイムスロットの関連情報を含み、又は、ローカルノードによりリクエストされた複数タイムスロットの関連情報及びローカルノードの少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報を含み；及び、前記HELLOパケットを送信し、前記HELLOパケットを受信したノードに、前記HELLOパケットに含まれている情報に基づいて、前記ローカルノードによりリクエストされた複数タイムスロットに対して認証を行わせることを含む。【選択図】図６
2015056899.tif 000002
【特許請求の範囲】
【請求項１】
ノードであって、
HELLOパケットを形成する形成ユニットであって、前記HELLOパケットは、前記ノードによりリクエストされた複数タイムスロットの関連情報を含み、又は、前記ノードによりリクエストされた複数タイムスロットの関連情報及び前記ノードの少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報を含む、形成ユニット；及び
前記形成ユニットが形成した前記HELLOパケットを送信し、前記HELLOパケットを受信したノードに、前記HELLOに含まれている情報に基づいて、前記ノードによりリクエストされたタイムスロットに対して認証を行わせる、送信ユニットを含み、
前記ノードによりリクエストされた複数タイムスロットの関連情報は、前記ノードのアドレス、前記ノードが送信しようとするデータパケットの受信ノードのアドレス、前記ノードによりリクエストされた複数タイムスロットの開始タイムスロットインデックス、及びタイムスロット長さを含み、
前記隣接ノードによりリクエストされた複数タイムスロットの関連情報は、隣接ノードのアドレス、隣接ノードが送信しようとするデータパケットの受信ノードのアドレス、隣接ノードによりリクエストされた複数タイムスロットの開始タイムスロットインデックス、タイムスロット長さ、隣接ノードからローカルノードに到着する距離、及び隣接ノードによりリクエストされた複数タイムスロットの確認情報を含む、ノード。
【請求項２】
請求項1に記載のノードであって、
前記形成ユニットは、
ルーティング表からローカルノードが送信しようとするデータパケットの受信ノードを選択し、前記ローカルノードが送信しようとするデータパケットの受信ノードのアドレスを得る第一取得モジュール；
ローカル予約履歴情報及び/又はローカルリクエスト表に基づいて、リクエストされた複数タイムスロットを確定し、リクエストされた複数タイムスロットの開始タイムスロットインデックス及びタイムスロット長さを得る第二取得モジュール；
ローカルノードが送信しようとするデータパケットの受信ノードのアドレス、リクエストされた複数タイムスロットの開始タイムスロットインデックス、タイムスロット長さ、及びローカルノードのアドレスに基づいて、前記ローカルノードによりリクエストされた複数タイムスロットの関連情報を得る形成モジュールを含む、ノード。
【請求項３】
請求項2に記載のノードであって、
前記形成ユニットは、更に、
所定策略に基づいて、ローカルリクエスト表から少なくとも１つの隣接ノードの情報エントリーを、前記少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報として選択する第三取得モジュールを含む、ノード。
【請求項４】
請求項2に記載のノードであって、
第二取得モジュールは、
所要なタイムスロット長さを計算する計算モジュール；
前記予約履歴情報に基づいて、所要なタイムスロット長さが変化しているかどうかを確定する確定モジュール；
所要なタイムスロット長さが変化している時に、計算された所要なタイムスロット長さに基づいてアイドルタイムスロットを選択し、選択されたアイドルタイムスロットに基づいて、リクエストされた複数タイムスロットを確定する第一選択モジュール；
所要なタイムスロット長さが変化しておらず、且つ、前記予約履歴情報に基づいて、前にリクエストされた複数タイムスロットが有効であると確定した時に、前記予約履歴情報に基づいて、リクエストされた複数タイムスロットを確定する第二選択モジュール；及び
所要なタイムスロット長さが変化していないが、前記予約履歴情報に基づいて、前にリクエストされた複数タイムスロットが無効であると確定した時に、計算された所要なタイムスロット長さに基づいてアイドルタイムスロットを選択し、選択されたアイドルタイムスロットに基づいて、リクエストされた複数タイムスロットを確定する第三選択モジュールを含む、ノード。
【請求項５】
請求項4に記載のノードであって、
前記第一選択モジュール又は前記第三選択モジュールは、予め構成されたタイムスロット集合から未使用のタイムスロットを前記開始タイムスロットとしてランダムに選択し；又は、予め構成されたタイムスロット集合から一番目の未使用のタイムスロットを前記開始タイムスロットとして選択し；又は、予め構成されたタイムスロット集合から最大の未使用のタイムスロット間隔内の中間位置のタイムスロットを前記開始タイムスロットとして選択し；又は、予め構成されたタイムスロット集合からタイムスロットインデックスがローカルノードのアドレスの関数であるタイムスロットを前記開始タイムスロットとして選択し；又は、ローカルノードのホップ数に基づいて、前記ホップ数に対応するタイムスロット集合から未使用のタイムスロットを前記開始タイムスロットとして選択し、また、前記開始タイムスロットを開始点として、ローカルリクエスト表の情報に基づいて、連続するM個の未占用のタイムスロットを前記アイドルタイムスロットとして選択し、そのうち、Mは、計算された所要なタイムスロット長さ以下である、ノード。
【請求項６】
請求項3に記載のノードであって、
前記第三取得モジュールは、具体的に、ローカルリクエスト表からローカルノードのnホップ衝突域内の1〜（n-1）ホップ隣接ノードのエントリーを前記少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報として選択し；又は、ローカルリクエスト表からローカルノードのnホップ衝突域内の全ての1ホップ隣接ノードのエントリー及び2〜（n-1）ホップ隣接ノードのエントリー中の確認情報が同意であるエントリーを前記少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報として選択するために用いられる、ノード。
【請求項７】
請求項1に記載のノードであって、更に、
受信したHELLOパケットに基づいて、HELLOパケットの送信ノードによりリクエストされたタイムスロットに対して認証を行い、及び/又は、ローカルノードによりリクエストされたタイムスロットが有効であるかどうかを確定し、及び/又は、ローカルリクエスト表又はローカル予約履歴情報を更新する処理ユニットを含み、
そのうち、受信したHELLOパケットは、前記HELLOの送信ノードによりリクエストされた複数タイムスロットの関連情報のみを含み、又は、受信したHELLOパケットは、前記HELLOの送信ノードによりリクエストされた複数タイムスロットの関連情報、及び、前記HELLOパケットの送信ノードの少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報を含む、ノード。
【請求項８】
請求項7に記載のノードであって、
前記処理ユニットは、
受信したHELLOパケット中の前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットの関連情報を遍歴する第一遍歴モジュール；及び
前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットと、ローカルリクエスト表中確の認情報が同意である1〜（n-1）ホップ隣接ノードによりリクエストされた複数タイムスロットとが衝突する時に、前記HELLOパケットの送信ノードによりリクエストされたタイムスロットに反対を付与し、また、ローカルリクエスト表に前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットの関連情報に対応する情報エントリーを追加し；前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットと、ローカルリクエスト表中の確認情報が同意である1〜（n-1）ホップ隣接ノードによりリクエストされた複数タイムスロットとが衝突しない時に、前記HELLOパケットの送信ノードによりリクエストされたタイムスロットに同意を付与し、また、ローカルリクエスト表に前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットの関連情報に対応する情報エントリーを追加する第一処理モジュールを含み、
前記第一処理モジュールは、前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットと、ローカルリクエスト表中の確認情報が同意である1〜（n-1）ホップ隣接ノードによりリクエストされた複数タイムスロットとが衝突しない時に、前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットと、ローカルノードによりリクエストされた複数タイムスロットとが衝突するかどうかを判断し、衝突する場合、ローカルノードによりリクエストされた複数タイムスロットが無効であると確定し、また、ローカル予約履歴情報を変更し；衝突しない場合、ローカルノードによりリクエストされた複数タイムスロットが有効であると確定し、また、ローカル予約履歴情報を不変にさせる、ノード。
【請求項９】
請求項8に記載のノードであって、
前記処理ユニットは、更に、
受信したHELLOパケット中の前記HELLOパケットの送信ノードの各隣接ノードによりリクエストされた複数タイムスロットの関連情報を遍歴する第二遍歴モジュール；及び
前記隣接ノードによりリクエストされた複数タイムスロットの関連情報が指示しているローカル源IDがローカルノードのIDである時に、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報が指示している確認情報に基づいて、ローカルノードによりリクエストされたタイムスロットが有効であるかどうかを確定し、そして、これに基づいてローカル予約履歴情報を更新し；前記隣接ノードによりリクエストされた複数タイムスロットの関連情報が指示しているローカル源IDがローカルノードのIDでない時に、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報に基づいて、ローカルリクエスト表を更新する第二処理モジュールを含み、
前記第二処理モジュールは、ローカルリクエスト表中の各情報エントリーに基づいて、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報を保存したことがあるかどうかを確定し、保存したことがない場合、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報をローカルリクエスト表に追加し、また、それに対応する距離に1を加算し；保存したことがある場合、前記HELLOパケット中の前記隣接ノードの前記関連情報に対応する距離が、ローカルリクエスト表中の前記隣接ノードの前記関連情報に対応する距離よりも小さい時に、ローカルリクエスト表中の前記隣接ノードの前記関連情報を更新し、また、それに対応する距離に1を加算し；前記HELLOパケット中の前記隣接ノードの前記関連情報に対応する距離が、ローカルリクエスト表中の前記隣接ノードの前記関連情報に対応する距離よりも小さい時に、前記HELLOパケット中の前記隣接ノードによりリクエストされた複数タイムスロットの確認情報が同意であるかどうかを判断し、同意の場合、ローカルリクエスト表中の全ての1ホップ隣接ノードの確認情報を更新する、ノード。
【請求項１０】
タイムスロット割り当て方法であって、
HELLOパケットを形成し、前記HELLOパケットは、ローカルノードによりリクエストされた複数タイムスロットの関連情報を含み、又は、ローカルノードによりリクエストされた複数タイムスロットの関連情報及びローカルノードの少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報を含み；及び
前記HELLOパケットを送信し、前記HELLOパケットを受信したノードに、前記HELLOパケットに含まれている情報に基づいて、前記ローカルノードによりリクエストされた複数タイムスロットに対して認証を行わせることを含む、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線通信、Ad  hocネットワーク、及びスマートグリッドに関し、特に、タイムスロット割り当て方法及び装置に関する。
【背景技術】
【０００２】
MAC（Media  Access  Control）層プロトコルは、ネットワーク中の特殊送信器の無線リソース、例えば、タイムスロット、周波数チャネル、拡散コードなどを確保するように設計されるものである。また、Ad  hocネットワークについて、中央管理がないため、一般のに、ハンドシェイク又はネゴシエーションによりリソース割り当てを保証する。
【０００３】
CSMA（Carrier  sensing  multiple  access)は、MAC層プロトコル中の最も汎用するものである。各潜在的な送信ノードは、ネットワークにパケットを実際に送信する前に、チャネルの状態を検出しなければならない。チャネルの実際の状態を正確に反映していない時には、コリジョン（衝突）が生じる可能性があり、このようなコリジョンは、隠れ端末問題と称される。大量のノードが同じ時間にパケットを送信しようとする大規模ネットワークについて言えば、この問題は非常に酷くなる可能性がある。最終的には、サービス品質（QoS、Quality  of  Service）の低下を招き、応用ニーズを満足することができなくなる。
【０００４】
TDMA（Time  division  multiple  access）は、MAC層プロトコルの代替方案を提供する。唯一のタイムスロットが伝送のためにリザーブ（reserve）され、これにより、高いサービス品質を保証する。IEEE（Institute  of  Electrical  and  Electronics  Engineers）802.15.4規格では、無コリジョン周期（CFP、collision  free  period）と称されるスーパーフレームの一部は、TDMA伝送のために分けられる。前記周期内の最小可用ユニットは、保証付きタイムスロット（GTS、Guaranteed  Time  Slot）と称される。
【０００５】
しかしながら、IEEE  802.15.4規格では、スター型トポロジーネットワークのみに基本的なGTSスケジューリング構成を提供し、他の複雑類型ネットワーク、特に、大規模ネットワーク及びAd  hocモードにおけるタイムスロット割り当てをサポートすることができない。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の主な目的は、背景技術に記載のような問題を解決するためのタイムスロット割り当て方法及び装置を提供することにある。
【課題を解決するための手段】
【０００７】
本発明の実施例の第一側面によれば、ノードが提供され、そのうち、前記ノードは、
前記ノードによりリクエスト（要求・予約）された複数タイムスロットの関連情報を含み、又は、前記ノードによりリクエストされた複数タイムスロットの関連情報、及び、前記ノードの少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報を含むHELLOパケットを形成する形成ユニット；及び
前記形成ユニットが形成した前記HELLOパケットを送信し、前記HELLOパケットを受信したノードに、前記HELLOに含まれている情報に基づいて、前記ノードによりリクエストされた複数タイムスロットに対して認証を行わせる送信ユニット；
を含み、そのうち、
前記ノードによりリクエストされた複数タイムスロットの関連情報は、前記ノードのアドレス、前記ノードが送信しようとするデータパケットの受信ノードのアドレス、前記ノードによりリクエストされた複数タイムスロットの開始タイムスロットのインデックス、及びタイムスロット長さを含み；
前記隣接ノードによりリクエストされた複数タイムスロットの関連情報は、隣接ノードのアドレス、隣接ノードが送信しようとするデータパケットの受信ノードのアドレス、隣接ノードによりリクエストされた複数タイムスロットの開始タイムスロットのインデックス、タイムスロット長さ、隣接ノードからローカルノードに到着する距離、及び隣接ノードによりリクエストされた複数タイムスロットの確認情報を含む。
【０００８】
本発明の実施例の有益な効果は、本発明の実施例の方法及び装置により、トラフィックに基づいてタイムスロット利用率を向上させることができる。
【図面の簡単な説明】
【０００９】
【図１】時間領域上でのHELLOパケット及びデータパケットの分布型伝送を示す図である。
【図２】スーパーフレームのフレーム構造を示す図である。
【図３Ａ】HELLOパケットのフォーマットの一例を示す図である。
【図３Ｂ】HELLOパケットのフォーマットの他の一例を示す図である。
【図４】HELLOパケットを送信及び受信するためのフローチャートである。
【図５】3ホップ衝突域を示す図である。
【図６】本発明の実施例におけるタイムスロット割り当て方法のフローチャートである。
【図７】HELLOパケットを形成する一例のフローチャートである。
【図８】リクエストされた複数タイムスロットを確定するためのフローチャートである。
【図９】アイドルタイムスロットを選択するためのフローチャートである。
【図１０】アイドルタイムスロットを選択する一例を示す図である。
【図１１】HELLOパケットを送信するためのフローチャートである。
【図１２】HELLOパケットを受信するためのフローチャートである。
【図１３】周期が3である時におけるインタリーブ前及びインタリーブ後のタイムスロットを示す図である。
【図１４】拡張された予約タイムスロットを示す図である。
【図１５】本発明の実施例におけるノードの構成を示す図。
【発明を実施するための形態】
【００１０】
以下、図面を参照しながら、発明を実施するための形態を詳しく説明する。
【００１１】
当業者が容易に本発明の原理及び実施形態を理解し得るために、本発明の実施例は、Ad-hocネットワークを例として説明されているが、理解すべきは、本発明の実施例は、Ad-hocネットワークに限定されず、例えば、本発明の実施例が提供する方法及び装置は、無線通信やスマートグリッドなどの他のマルチホップネットワークにも適用され得るとのことである。
【００１２】
本発明の実施例では、タイムスロット割り当てが分布型の方式で実行され、これにより、ad  hocネットワークの実施をより一層助けることができる。タイムスロット割り当てのプロセスに用いる制御パケット、即ち、HELLOパケットは、ブロードキャストによるパケットであり、且つ、通常、ルーティング協議に用いられる。データパケットの伝送のために有効なリソースを予約するためには、前記制御パケットは分かれて伝送される。言い換えると、データパケット及び制御パケットは、異なる周波数又はタイムスロット又は他の類型のチャネル中に伝送される。図1に示すのは、IEEE  802.15.4システムにおいて時間上で分かれて伝送される一例である。
【００１３】
前記タイムスロット割り当てのフローは、制御パケット即ちHELLOパケットの交換により完成され、各ノードは、HELLOパケットを送信及び受信することにより、データ伝送のために有効なタイムスロットを予約し、衝突を避ける。割り当ての柔軟性及び有効性を保証するために、CAP中に伝送されるHELLOパケットは、必ずしも、同じスーパーフレーム中のタイムスロットを予約するために用いられず、これらのHELLOパケットは、前又は後のスーパーフレーム中のタイムスロットを予約するために用いられてもよい。ある場合、一定数のスーパーフレームに対して組分けを行い、ネットワークの規模を拡大することができる。これは、スーパーフレーム中の任意の１つの中（CAP）に送信されるHELLOパケットが、これらのスーパーフレーム中（CFP）の任意のタイムスロットを予約することが許可されていることを意味する。図2は、１つの組中のスーパーフレームの数が5と設定される例を示す。
【００１４】
他のノードが同じタイムスロットを用いてデータ伝送を行うことを避けるために、HELLOパケットが周期的にブロードキャストされ、これにより、占用されている特定タイムスロットを指示する。前記周期は、応用ニーズに一致してもよい。静的ネットワーク、例えば、スマートグリッドについて言えば、ノードの位置があまり変化しないなので、このとき、比較的長い周期を採用してもよい。
【００１５】
本発明の実施例では、HELLOパケットは、２つの部分に分けられてもよく、第一部分は、REQ部分であり、HELLOパケットの送信元によりリクエストされたタイムスロット、即ち、ローカルノードによりリクエストされた複数タイムスロットの関連情報を示し；第二部分は、RES部分であり、隣接ノードのリクエストへのレスポンス、即ち、ローカルノードの少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報を示し、各隣接ノードに対応し、前記隣接ノードのリクエストへのレスポンスを含む。第一部分では、前記送信元によりリクエストされたタイムスロットは、４つのセグメントの情報、即ち、ローカル源ID、ローカル目標ID、開始タイムスロットインデックス、及びタイムスロット長さを含み；第二部分では、各レスポンスは、少なくとも、次の６つのセグメントの情報、即ち、ローカル源ID、ローカル目標ID、開始タイムスロットインデックス、タイムスロット長さ、距離、及び確認情報を含む。
【００１６】
図3Aは、本実施例におけるHELLOパケットのフォーマットの一例を示す図。図3Aに示すように、ローカル源ID（Local  Source  ID）は、データパケットの送信アドレスを表し、HELLOパケットが自分のためのタイムスロット予約のために送信される場合、HELLOパケットの送信元のIDとは同じであり；ローカル目標ID（Destination  ID）は、データパケットの受信先のアドレスを表し、マルチホップad  hocネットワークの場合、ネクストホップのIDを示し、前記ネットワークがツリー型トポロジーである場合、親ノードのIDを示し；開始タイムスロットインデックス（Start  slot  Index）は、ローカル源ノードが一番予約したい開始タイムスロットを表し、前記タイムスロットの選択は、HELLOパケットから抽出した隣接ノードの選択の観察に基づくべきであり；長さ（Length）は、ローカル源ノードが予約したい、開始タイムスロットからの所望のタイムスロット長さを示し；距離（Distance）は、ローカル源ノードと、HELLOパケットの送信ノードとの間のホップ数を表し；確認情報（Confirmation）は、隣接ノードから得たフィードバックであり、ローカル源ノードが前記所望のタイムスロットを予約できるかどうかへの同意又は不同意（即ち、反対）を表し、HELLOパケットを受信した後に、ローカル源ノードのIDと、HELLOパケットの送信元のIDとが同じである場合、各ノードは、前記確認情報を決定すべきである。
【００１７】
図3Bは、本実施例におけるのHELLOパケットのフォーマットの他の一例を示す図である。図3Bに示すように、図3AのHELLOパケットとは同じ情報以外に、前記例では、各情報エントリーは、更に、ローカル源ノードのインタリーブ周期を含み、これにより、各ローカル源ノードは、所定のインタリーブ方法により、リクエストされた複数タイムスロットを物理タイムスロットにマッピングしてデータ伝送を行う。
【００１８】
本発明の実施例では、隣接ノードの予約及び各タイムスロット中の状態更新の追跡を行うために、各ノードは、１つのローカル表を維持する必要があり、前記ローカル表には、複数エントリーを含み、各項目は、少なくとも、受信したHELLOパケット中のRES部分と同様のエントリーを含み、図3Aの例に対応して、ローカルリクエスト表中の各項目は、６つのエントリー、即ち、ローカル源ノードID、ローカル目標ノードID、開始タイムスロットインデックス、長さ、距離、及び確認情報を含み；図3Bの例に対応して、ローカルリクエスト表中の各項目は、７つのエントリーを含み、上述の６つのエントリー以外に、インタリーブ周期を更に含む。
【００１９】
表1は、図3Aの例に対応するローカル表の一例である。また、在本発明の実施例では、前記ローカル表がリクエスト表又はローカルリクエスト表とも称される。
【表１】
2015056899.tif 000003
【００２０】
本発明の実施例では、HELLOパケットの交換プロセスが図4に示されている。HELLOパケットの伝送は、ローカルタイマーによりスケジューリングされる。ローカルタイマー起動時に、HELLOパケットの送信ノードは、先ず、HELLOパケットの上述のような２つの部分の内容を決め、そして、前記HELLOパケットを形成する。前記HELLOパケットを受信した時に、HELLOパケットの受信ノードは、ローカル観察、例えば、ローカルリクエスト表に基づいて、前記HELLOパケット中のREQ部分に関連する確認値、即ち、前記HELLOパケットの送信ノードによりリクエストされた前記複数タイムスロットに同意するかどうかに関連する情報を決定すべきである。また、HELLOパケットから取得された全ての情報は、ローカルリクエスト表の更新に使用すべきである。
【００２１】
本発明の実施例では、nホップ衝突域の概念が定義されている。１つの衝突域内の２つのノードが同時にパケットを送信する場合、衝突が生じる可能性がある。よって、本発明の実施例では、時間領域上でこれらのノードを分離し、これにより、このような場合の発生を避ける。そのうち、各ノードは、nホップ範囲内の隣接ノードの情報をローカルリクエスト表に保存し、且つ、これらの占用されているタイムスロットを、伝送のために選択することができない。また、各ノードは、1、2ないしn-1ホップ隣接ノードを選択し、HELLOパケットのRES部分を形成することができる。且つ、各ノードは、1、2ないしn-1ホップ隣接ノードの情報に基づいて、隣接ノードによりリクエストされた複数タイムスロットに対して確認を行う。
【００２２】
図5は、3ホップ衝突域の一例を示す。図5に示すように、ノードA及びノードDは、同じタイムスロットを予約することができない。ノードDは、ノードB及びノードC（1ホップ及び2ホップ隣接ノード）の情報を、HELLOパケットのブロードキャストフローに入れ、これにより、ノードEは、前記HELLOパケットを受信することができ、且つ、ノードB、ノードC及びノードDとは同じタイムスロットを選択することができない。また、ノードEは、ノードAとは同じタイムスロットを選択することができ、なぜなら、ノードA及びノードEは、１つの衝突域内に位置しないからである。且つ、ノードEがノードAとは同じタイムスロットを予約している場合、ノードDは、このような状況を発現することができるが、ノードEを拒否することができない。その理由は、ノードAがノードDの3ホップ隣接ノードであることにある。
【００２３】
本発明の実施例では、各ノードは更に、前に予約した複数タイムスロット、及び、隣接ノードの、予約した複数タイムスロットの関連情報への確認結果を保存する。これらは、次回HELLOパケットを形成する時に、アイドルタイムスロットを選択するための参考とされ得る。
【００２４】
本発明の実施例では、HELLOパケットの伝送プロセスでは、ノードは、可用アイドルタイムスロットを見つけてHELLOパケットのREQ部分を形成する必要があり、また、リクエスト表から適切な情報を見つけてHELLOパケットのRES部分を形成する必要がある。以下、図面及び具体的な実施例に基に、本発明の実施例におけるタイムスロット割り当て方法及び装置について詳細に説明する。
【実施例１】
【００２５】
本発明の実施例は、タイムスロット割り当て方法を提供し、前記方法は、マルチホップネットワーク中のノードに用いる。図6は、前記方法のフローチャートであり、図6に示すように、前記方法は、次のステップを含む。
【００２６】
ステップ601：HELLOパケットを形成し、前記HELLOパケットは、ローカルノードによりリクエストされた複数タイムスロットの関連情報を含み、又は、ローカルノードによりリクエストされた複数タイムスロットの関連情報、及び、ローカルノードの少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報を含む。
【００２７】
そのうち、ローカルノードによりリクエストされた複数タイムスロットの関連情報は、上述したHELLOパケットのREQ部分であり、ローカルノードの少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報は、上述したHELLOパケットのRES部分である。REQ部分及びRES部分の内容については、上述に説明したため、ここでは詳しい説明を省略する。
【００２８】
本実施例の１つの場面では、ローカルノードが初めてパケットを送信する。この場合、他のノードからのHELLOパケットを受信したことがないため、ローカルリクエスト表を記憶してない。このときに形成したHELLOパケットは、REQ部分のみを含む。
【００２９】
本実施例の他の場面では、ローカルノードが他のノードからのHELLOパケットを受信したことがあり、また、前記HELLOパケット中の情報に基づいてローカルリクエスト表を記憶又は更新したことがある。このときに形成したHELLOパケットは、REQ部分及びRES部分を含む。
【００３０】
ステップ602：前記HELLOパケットを送信し、前記HELLOパケットを受信したノードに、前記HELLOパケットに含まれている情報に基づいて、前記ローカルノードによりリクエストされた複数タイムスロットに対して認証を行わせる。
【００３１】
そのうち、上述のように、本発明の実施例では、上述のHELLOパケットを形成する目的は、タイムスロットを予約してデータ伝送を行うことにあり、このようなHELLOパケットを形成した後に、従来の手段によりブロードキャストし送信することができる。前記HELLOパケットを受信したノードは、前記HELLOパケット中の情報に基づいて、前記ローカルノードによりリクエストされた複数タイムスロットに対して認証を行うことができ、また、これに基づいて、リクエストされた複数タイムスロットが有効であるかどうかを確認することができ、また、そのローカルリクエスト表又は予約履歴情報を更新することができ、また、本実施例の方法によりそのHELLOパケットを形成する。具体的な受信フローは、以下に説明する。
【００３２】
本実施例では、上述のように、ローカルノードによりリクエストされた複数タイムスロットの関連情報は、ローカルノードのアドレス（即ち、ローカルノードが送信しようとするデータパケットの送信ノードのアドレス）、ローカルノードが送信しようとするデータパケットの受信ノードのアドレス、リクエストされた複数タイムスロットの開始タイムスロットインデックス、及びタイムスロット長さを含む。隣接ノードによりリクエストされた複数タイムスロットの関連情報は、隣接ノードのアドレス（即ち、隣接ノードが送信しようとするデータパケットの送信ノードのアドレス）、隣接ノードが送信しようとするデータパケットの受信ノードのアドレス、隣接ノードによりリクエストされた複数タイムスロットの開始タイムスロットインデックス、タイムスロット長さ、隣接ノードからローカルノード（上述のHELLOパケットの送信ノード）に到着する距離、及び隣接ノードによりリクエストされた複数タイムスロットの確認情報を含む。
【００３３】
本実施例では、上述のように、上述の内容以外に、ローカルノードによりリクエストされた複数タイムスロットの関連情報は更に、ローカルノードのインタリーブ周期を含んでもよく；同様に、隣接ノードによりリクエストされた複数タイムスロットの関連情報は更に、隣接ノードのインタリーブ周期を含んでもよい。
【００３４】
本実施例では、ステップ601は、図7に示す方法により実現されてもよく、図7に示すように、前記方法は、次のステップを含む。
【００３５】
ステップ701：ルーティング表から、ローカルノードが送信しようとするデータパケットの受信ノードを選択し、前記ローカルノードが送信しようとするデータパケットの受信ノードのアドレスを得る。
【００３６】
そのうち、各ノードは、ルーティング表を保存維持し、前記ルーティング表は、前記ノードから目標ノードに到着する複数の経路、及び、各経路のルーティングコストを示す。本実施例では、ルーティングコスト最小の経路に対応する受信ノードを、送信しようとするデータパケットの受信ノードとして選択し、前記受信ノードのアドレスを取得してもよい。
【００３７】
ステップ702：ローカル予約履歴情報及び/又はローカルリクエスト表に基づいて、リクエストされた複数タイムスロットを確定し、リクエストされた複数タイムスロットの開始タイムスロットインデックス及びタイムスロット長さを得る。
【００３８】
そのうち、ステップ702は、アイドルタイムスロットを選択するステップであり、前に選択したアイドルタイムスロットが有効であり、且つ、所定時間内に隣接ノードからの反対意見を受けていない場合、前に選択したアイドルタイムスロットを選択してもよく、そうでない場合、アイドルタイムスロットを再選択し、再選択したアイドルタイムスロットの開始タイムスロット及びタイムスロット長さを確定してもよい。具体的には以下に説明する。
【００３９】
ステップ703：ローカルノードが送信しようとするデータパケットの受信ノードのアドレス、リクエストされた複数タイムスロットの開始タイムスロットインデックス、タイムスロット長さ、及びローカルノードのアドレスに基づいて、前記ローカルノードによりリクエストされた複数タイムスロットの関連情報を得る。
【００４０】
そのうち、ステップ701により、データパケットの受信ノードのアドレスを取得し、ステップ702により、リクエストされた複数タイムスロットの開始タイムスロット及びタイムスロット長さを取得していると、ローカルノードによりリクエストされた複数タイムスロットの関連情報、即ち、HELLOパケットのREQ部分を形成することができる。そのうち、前記REQ部分では、前記HELLOパケットが、ローカルノードのためにタイムスロットを予約するためのものであるため、前記HELLOパケットのREQ部分のローカル源IDがローカルノードのIDである。
【００４１】
本実施例では、ローカル表には隣接ノードに対応する情報エントリーが記憶されていれば、図7の方法は更に次のステップをも含む。
【００４２】
ステップ704：所定策略に基づいて、ローカルリクエスト表から、少なくとも１つの隣接ノードの情報エントリーを、前記少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報として選択する。
【００４３】
そのうち、ローカルリクエスト表から、ローカルノードのnホップ衝突域内の1〜（n-1）ホップ隣接ノードのエントリーを、前記少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報として選択してもよく；ローカルリクエスト表から、ローカルノードのnホップ衝突域内の全ての1ホップ隣接ノードのエントリー、及び、2〜（n-1）ホップ隣接ノードのエントリー中の確認情報が同意であるエントリーを、前記少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報として選択してもよい。HELLOパケットに形成されたエントリーが多いほど、到着し得る、HELLOパケットの予約情報に含まれている領域が大きく、衝突の可能性が低いとのことを保証することができる。
【００４４】
ステップ702では、リクエストされた複数タイムスロットを確定するステップは、図8の方法により実現されてもよく、図8に示すように、前記方法は、次のステップを含む。
【００４５】
ステップ801：所要なタイムスロット長さを計算する。
【００４６】
そのうち、所要なタイムスロット長さは、トラフィックの絶対値に基づいて計算されてもよく、nホップ衝突域内のトラフィックストリームの比に基づいて計算されてもよい。なお、本実施例はこれに限定されず、本発明の精神及び範囲内では、当業者が想到した他の所要なタイムスロット長さの計算方法も、本発明の保護範囲内に属する。
【００４７】
そのうち、トラフィックの絶対値に基づいて所要なタイムスロット長さを計算することは、ローカルノードの全てのサブノードが予約したタイムスロットの長さの和に基づいて、所要なタイムスロット長さを計算することである。
【００４８】
各ノードが１つのパケットを生成し、また、それをシンク（sink）ノードに送信したいとする。ローカルノードがK個のサブノードを有し、且つ、サブノードiがlengthi個の伝送用タイムスロットをリクエストしている場合、ローカルノードの所要なタイムスロット長さは、次の公式により計算することができる。
【数１】
2015056899.tif 000004
【００４９】
即ち、サブノードは、ローカル表のエントリー中の目的ノードIDがローカルノードである源ノードIDが示すノードである。
【００５０】
そのうち、nホップ衝突域内のトラフィックストリームの比に基づいて所要なタイムスロット長さを計算することは、ローカルノードの衝突域内の隣接ノードのトラフィックに基づいて所要なタイムスロット長さを計算することである。
【００５１】
隣接ノードjがローカルノードのnホップ衝突域内に位置し、且つ、それがlengthj個の伝送用タイムスロットをリクエストしており、且つ、ローカルノードがnホップ衝突域内にN個の隣接ノードを有するとする場合、ローカルノードの所要なタイムスロット長さは、次の公式により計算することができる。
【数２】
2015056899.tif 000005
【００５２】
そのうち、Stotalは、衝突域内の保証付きタイムスロットの総数、例えば、１つのHELLOパケットの間隔、又は、１つのスーパーフレームなどを表し、即ち、それは、予約可能なタイムスロットの周期を示す。
【００５３】
ステップ802：ローカルに保存された予約履歴情報に基づいて、所要なタイムスロット長さが変化しているかどうかを確定する。
【００５４】
そのうち、上述のように、各ノードは、前に予約した複数タイムスロットの関連情報、例えば、開始タイムスロット、タイムスロット長さ、フラグなどを保存することができ、本実施例では、予約履歴情報と称される。前記予約履歴情報に基づいて、前に予約したタイムスロット長さと、計算された所要なタイムスロット長さとの比較により、計算された所要なタイムスロット長さが変化しているかどうかを確認することができる。
【００５５】
ステップ803：所要なタイムスロット長さが変化している場合、計算された所要なタイムスロット長さに基づいてアイドルタイムスロットを選択し、選択されたアイドルタイムスロットに基づいて、リクエストされた複数タイムスロットの開始タイムスロット及びタイムスロット長さを確定する。
【００５６】
そのうち、ステップ802の判断により、変化が発生していると確定した場合、アイドルタイムスロットを再選択する必要がある。
【００５７】
一例では、アイドルタイムスロットを選択するステップは、図9に示す方法により実現されてもよく、図9に示すように、前記方法は、次のステップを含む。
【００５８】
ステップ901：開始タイムスロットを選択し；
ステップ902：前記開始タイムスロットを開始点とし、ローカルリクエスト表の情報に基づいて、連続するM個の未占用のタイムスロットを前記アイドルタイムスロットとして選択し、そのうち、Mは、計算された所要なタイムスロット長さ以下である。
【００５９】
ステップ901では、リクエスト表に含まれている情報に基づいて、アイドル開始タイムスロットを選択することができる。
【００６０】
一例では、前記開始タイムスロットは、nホップ衝突域内の他のノードにより占用されていないタイムスロットからランダムに選択してもよく、即ち、予め構成されたタイムスロット集合から、未使用のタイムスロットを前記開始タイムスロットとしてランダムに選択してもよい。
【００６１】
一例では、前記開始タイムスロットは、ローカルノードの１つの関数により確定されてもよく、即ち、予め構成されたタイムスロット集合から、タイムスロットインデックスがローカルノードのアドレスの関数であるタイムスロットを、前記開始タイムスロットとして選択してもよく、例えば、次の関数である。
【数３】
2015056899.tif 000006
【００６２】
そのうち、Kは、タイムスロットの総数を示す。
【００６３】
一例では、前記開始タイムスロットは、ホップ数の関数により確定されてもよく、即ち、ローカルノードのホップ数に基づいて、前記ホップ数に対応するタイムスロット集合から、未使用のタイムスロットを前記開始タイムスロットとして選択してもよい。表2に示すように、第iホップのノードは、集合kiのみの中の開始アイドルタイムスロットを選択することができる。
【表２】
2015056899.tif 000007
【００６４】
一例では、前記開始タイムスロットは更に、占用されているタイムスロットへの観察により確定されてもよい。例えば、選択されたタイムスロットは、一番目の、他のノードにより占用されていないアイドルタイムスロットであってもよい。或いは、２つの占用されているタイムスロットの間の最大アイドルタイムスロット間隔を見つけて、その中間の１つを適切なタイムスロットとして選択してもよい。この場合、２つの占用されているタイムスロットの間の最大アイドルタイムスロット間隔を保証することができる。図10は、開始タイムスロットを選択する一例を示す。
【００６５】
なお、上述の開始タイムスロットの選択方法は例示のみであり、本発明の実施例はこれに限定されない。また、そのうち、予め構成されたタイムスロット集合は、予め設定されたHELLOパケット間隔中の指定（所定）フレームのデータ部分であってもよく、予め設定されたHELLOパケット間隔中の全てのフレームのデータ部分であってもよい。
【００６６】
ステップ902では、先ず、ローカルリクエスト表の情報に基づいて、開始タイムスロット開始から前記所要なタイムスロット長さを経って修了タイムスロットまでの範囲内の全てのタイムスロットがアイドルであるかどうかを確定し、前記範囲内の全てのタイムスロットがアイドルである場合、前記開始タイムスロットを含む連続するM個のタイムスロットを前記アイドルタイムスロットとして確定し、この場合、Mは、前記所要なタイムスロット長さである。また、前記範囲内に少なくとも１つのタイムスロットが占用されている場合、言い換えると、ステップ901により選択された開始タイムスロットを開始点とすることにより、所要なタイムスロット長さを満足する複数の連続するアイドルタイムスロットを見つけることができない場合、前記範囲内の最後の１つの占用されているタイムスロットの後の一番目のアイドルタイムスロットを前記開始タイムスロットとし、そして、ステップ902に戻り類似する処理を継続する。
【００６７】
ステップ902では、ローカルリクエスト表の情報によれば、所要なタイムスロット長さの個数の連続する未占用のアイドルタイムスロットがない場合があり、このとき、所要なタイムスロット長さの数を減らし、そして、ステップ901に戻り類似する処理を継続してもよい。
【００６８】
図9の方法によりアイドルタイムスロットを選択することができ、そして、前記アイドルタイムスロットの開始タイムスロット及びタイムスロット長さを確定することができ、これにより、HELLOパケットのREQ部分を形成することができる。
【００６９】
ステップ804：所要なタイムスロット長さが変化しておらず、且つ、前記予約履歴情報に基づいて確定した、前に選択したタイムスロットが有効である場合、前記予約履歴情報に基づいて、リクエストされた複数タイムスロットの開始タイムスロット及びタイムスロット長さを確定する。
【００７０】
そのうち、ステップ802の判断より、タイムスロット長さが変化しておらず、且つ、前に選択したタイムスロットが有効であると確定した場合、直接、前に予約したタイムスロットを、今回リクエストされたアイドルタイムスロットとすることができ、これにより、その開始タイムスロット及其タイムスロット長さを確定することができる。
【００７１】
ステップ805：所要なタイムスロット長さが変化していないが、前記予約履歴情報に基づいて確定した、前に選択したタイムスロットが無効である場合、計算された所要なタイムスロット長さに基づいてアイドルタイムスロットを選択し、そして、選択されたアイドルタイムスロットに基づいて、リクエストされた複数タイムスロットの開始タイムスロット及びタイムスロット長さを確定する。
【００７２】
そのうち、ステップ802の判断により、タイムスロット長さが変化していないが、前に選択したタイムスロットが無効であると確定した場合、アイドルタイムスロットを再び選択する必要があり、選択する方法は、ステップ803中のアイドルタイムスロットを選択する方法とは同じであってもよく、図9の方法により実現されてもよいので、ここでは詳しい説明を省略する。
【００７３】
本実施例の方法をより明確にするために、以下、HELLOパケットの送信フローを基に、本実施例の方法について説明する。
【００７４】
図11は、本発明の実施例による方法のHELLOパケットの送信フローチャートであり、図11に示すように、前記フローは、次のステップを含む。
【００７５】
ステップ1101：HELLOパケットのタイマーが起動し；
ステップ1102：ローカルルーティング表からローカル目標ノードのアドレスを取得し；
上述のように、ルーティングコストが最小である経路の受信ノードをローカル目標ノードとして選択し、ローカル目標アドレスを得てもよい。
【００７６】
ステップ1103：所要な長さを更新し；
上述のように、前述の方法により所要なタイムスロット長さを計算することができる。
【００７７】
ステップ1104：所要な長さが変化しているかどうかを確定し、変化が発生していない場合、ステップ1105を実行し、変化が発生している場合、ステップ1106を実行し；
上述のように、ローカルに保存された予約履歴情報との比較により、所要なタイムスロット長さが変化しているかどうかを判断することができる。
【００７８】
ステップ1105：前に選択したタイムスロットが有効であるかどうかを確定し、無効である場合、ステップ1106を実行し、有効である場合、ステップ1107を実行し：
ステップ1106：新しいアイドルタイムスロットを選択し；
上述のように、図9の方法により新しいアイドルタイムスロットを選択することができる。
【００７９】
ステップ1107：HELLOパケットのREQ部分を形成し；
ステップ1108：ローカルリクエスト表からエントリーを選択し；
上述のように、nホップ衝突域内の1、2、…、（n-1）ホップ隣接ノードのエントリーを選択してもよく、又は、nホップ衝突域内の全ての1ホップ隣接ノードのエントリー及び2〜（n-1）ホップ隣接ノード中の確認情報が同意であるエントリーを選択してもよい。
【００８０】
ステップ1109：HELLOパケットのRES部分を形成し；
ステップ1110：HELLOパケットを送信する。
【００８１】
本実施例の方法によりHELLOパケットを形成し、そして送信することにより、タイムスロットの予約を有効に行うことができ、タイムスロットの利用率を向上させることができる。
【００８２】
本発明の実施例では、HELLOパケットを受信した場合、受信したHELLOパケットに基づいて、HELLOパケットの送信ノードによりリクエストされた複数タイムスロットに対して認証を行うことができ、例えば、前記HELLOパケットの送信元によりリクエストされた複数タイムスロットに同意又は反対することができる。また、受信したHELLOパケットに基づいて、ローカルノードによりリクエストされた複数タイムスロットが有効であるかどうかを確定することができ、また、受信したHELLOパケットに基づいて、ローカルリクエスト表又はローカル予約履歴情報を更新することができる。
【００８３】
そのうち、前記受信したHELLOパケットに含まれている内容は、上述に形成したHELLOパケットとは同じであり、即ち、REQ部分のみを含む可能性があり、即ち、HELLOパケットの送信元によりリクエストされた複数タイムスロットの関連情報のみを含む可能性があり、また、REQ部分及びRES部分の両方を含む可能性があり、即ち、HELLOパケットの送信元によりリクエストされた複数タイムスロットの関連情報だけでなく、前記HELLOパケットの送信ノードの少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報をも含む可能性がある。
【００８４】
本実施例では、受信したHELLOパケットのREQ部分に基づいて、HELLOパケットの送信元によりリクエストされた複数タイムスロットに対して認証を行い（ローカルノードの同意又は反対の意見を与える）、これは、前記REQ部分によりリクエストされた複数タイムスロットと、ローカルリクエスト表中の一部のエントリーとの比較の方式で実現することができる。
【００８５】
一例では、受信したHELLOパケットのREQ部分と、ローカルリクエスト表中の確認情報が同意であるnホップ衝突域内の1、2、…、（n-1）ホップ隣接ノードのエントリーとの比較を行うことにより、前記HELLOパケットの送信元によりリクエストされた複数タイムスロットが占用されているかどうかを確定し、占用されている場合、衝突が存在すると確定し、このとき、ローカルノードが前記HELLOパケットの送信元によりリクエストされた複数タイムスロットに与える意見は、反対であり、逆に、占用されていない場合、衝突が存在しないと確定し、このとき、ローカルノードが前記HELLOパケットの送信元によりリクエストされた複数タイムスロットに与える意見は、同意である。
【００８６】
そのうち、ローカルノードは、前記HELLOパケットの送信元によりリクエストされた複数タイムスロットにローカル意見を付与した後に、これに基づいて、ローカルリクエスト表を更新することができ、例えば、反対の場合、確認情報を反対（confirmation=0）に設定し、そして、前記エントリーをローカルリクエスト表に追加し；同意の場合、確認情報を同意（confirmation=1）に設定し、そして、前記エントリーをローカルリクエスト表に追加する。また、同意の場合、ローカルノードは更に、前記HELLOパケットの送信元によりリクエストされた複数タイムスロットと、ローカルノードによりリクエストされた複数タイムスロットとが衝突するかどうかを確認することもでき、衝突しない場合、ローカルノードによりリクエストされた複数タイムスロットが有効であると確定し、このとき、ローカル予約履歴情報を不変に維持させ、衝突する場合、ローカルノードによりリクエストされた複数タイムスロットが無効であると確定し、このとき、ローカル予約履歴情報を変更する必要があり、例えば、ローカル予約履歴情報が指示している状態を無効に変更し、又は、ローカル予約履歴情報が指示している、ローカルノードによりリクエストされた複数タイムスロットのインデックスを特定値に変更するなどである。
【００８７】
本実施例では、オプションで、前記ローカルノードによりリクエストされた複数タイムスロットに対して認証を行う前に、先に、前記REQ部分を受信したことがあるかどうかを確定してもよく、はいの場合、それを処理したことがあり、前記REQ部分が古いものであるとのことを示し、このとき、直接修了し；いいえの場合、それを処理したことがなく、前記REQ部分が新しいものであるとのことを示し、このとき、前記ローカルノードによりリクエストされた複数タイムスロットに対して認証を行う。そのうち、前記REQ部分を受信したことがあるかどうかは、それをローカルリクエスト表と比較することにより実現することができ、前記REQ部分がローカルリクエスト表中（ローカルリクエスト表には、受信したREQ部分のLocal  Source  ID、Local  Destination  ID、Start  index及びLengthと同じ情報エントリーが含まれている）に存在する場合、前記REQ部分を受信したことがあると確定し、そうでない場合、前記REQ部分を受信したことがないと確定する。
【００８８】
本実施例では、オプションで、前記ローカルノードによりリクエストされた複数タイムスロットに対して認証を行う前に、更に先に、前記REQ部分が有効であるかどうかを確定することができ、例えば、前記REQ部分が指示している、リクエストされたタイムスロットのインデックスが0以上であるかどうかを判断することにより、前記REQ部分が有効であるかどうかを確認してもよく、0以上の場合、前記HELLOパケットの送信元が１つの有効なタイムスロットをリクエストしたとのことを示し、この場合、前記ローカルノードによりリクエストされた複数タイムスロットに対して認証を行い；0より小さい場合、前記HELLOパケットの送信元が１つの無効のタイムスロットをリクエストした、又は、前記HELLOパケットの送信元がタイムスロットを予約する気がなかったとのことを示し、このとき、直接、ローカルリクエスト表に、前記REQ部分に対応する情報エントリーを追加し、そのうち、前記新しく増加されたエントリーに対応する確認情報が特定値であってもよい。
【００８９】
上述の例は、例示だけであり、本実施例の他の例では、nホップ衝突域内の第1、2、…、（n-1）ホップの隣接ノードのエントリーと比較しなくてもよい。即ち、所定策略に基づいて、他の隣接ノードのエントリーと比較し、これにより、占用されているタイムスロットが衝突するかどうかを確定してもよく、また、比較する方法は類似するため、ここでは詳しい説明を省略する。
【００９０】
上述の処理により、受信したHELLOパケットの送信元によりリクエストされた複数タイムスロットに対しての認証を完成させたのみならず、受信したHELLOパケットのREQ部分によるローカルリクエスト表又はローカル予約履歴情報の更新をも完成させた。
【００９１】
本実施例では、前記HELLOパケット中のRES部分の情報に基づいて、ローカルノードによりリクエストされた複数タイムスロットが有効であるかどうかを確認し、そして、これに基づいて、ローカルリクエスト表又はローカル予約履歴情報を更新することは、前記RES部分の各RESエントリーを遍歴する方式で実現することができる。
【００９２】
そのうち、ローカル源ノードのアドレスがローカルノードのアドレスであるRESエントリーは、ローカルノードによりリクエストされた複数タイムスロットの関連情報であり、且つ、前記RESエントリーに対応する確認情報は、他のノードが、ローカルノードによりリクエストされた複数タイムスロットに与えた認証結果である。前記認証結果が同意の場合、ローカルノードによりリクエストされた複数タイムスロットが有効であると確認し、このとき、ローカル予約履歴情報を変更する必要がなく；逆に、前記認証結果が反対の場合、ローカルノードによりリクエストされた複数タイムスロットが無効であると確認し、このとき、ローカルに保存された予約履歴情報を変更する必要があり、例えば、ローカルに保存された予約履歴情報中のリクエストされた複数タイムスロットのフラグ（flag）を無効に変更し、又は、直接、ローカルに保存された予約履歴情報中のリクエストされた複数タイムスロットの開始タイムスロット及びタイムスロット長さを0よりも小さい数に変更するなどである。
【００９３】
そのうち、ローカル源ノードのアドレスがローカルノードのアドレスでないRESエントリーについて、これらのRESエントリーに基づいて、ローカルリクエスト表を更新する必要がある。例えば、某RESエントリーについて、前記RESエントリーと、ローカルリクエスト表中の各項目とを比較し、前記RESエントリーのローカル源ノードアドレスが新しいものであるときに、即ち、ローカルリクエスト表に前記エントリーを記憶したことがないときに、ローカルリクエスト表にこのような１つのエントリーを追加し、また、その距離に1を加算し；前記RESエントリーのローカル源ノードのアドレスが古いものであるときに、即ち、ローカルリクエスト表に前記エントリーを記憶したことがあるときに、前記RESエントリーの距離と、ローカルリクエスト表中の対応するエントリーの距離とを比較し、前記RESエントリーの距離が、ローカルリクエスト表中の対応するエントリーの距離以上であるときに、前記RESエントリーに対しての処理を修了させ、次の１つのRESエントリーを取得してもよく；前記RESエントリーの距離が、ローカルリクエスト表中の対応するエントリーの距離よりも小さいときに、前記RESエントリーに対応する確認情報をチェックし、確認情報が反対（confirmation=0）の場合、前記RESエントリーが、ローカルリクエスト表中の各項目に対応する、リクエストされたタイムスロットに影響しないことを示し、この場合、直接、前記RESエントリーの距離に1を加算してローカルリクエスト表中の対応するエントリーの距離とし；確認情報が同意（confirmation=1）の場合、これに基づいて、ローカルリクエスト表中の全ての1ホップ隣接ノードの確認情報を更新する必要があるとのことを示し、例えば、ローカルリクエスト表中の1ホップ隣接ノードに対応するエントリー中のリクエストされたタイムスロットと、前記RESエントリーに対応するリクエストされた複数タイムスロットとが衝突するとき、前記1ホップ隣接ノードに対応するエントリーの確認情報を反対に変更し、そうでない場合、1ホップ隣接ノードに対応する確認情報を同意に変更し、その後、前記RESエントリーの距離に1を加算してローカルリクエスト表中の対応するエントリーの距離とする。
【００９４】
そのうち、各RESエントリーを処理する時に、先ず、前記RESエントリーが有効であるかどうかを確認する必要があり、同様に、ローカルリクエスト表と比較することにより確定することができ、前にこのようなエントリーを受信したことがない場合、前記RESエントリーが新しいものであると見なし、前記RESエントリーが有効であると確定し、そうでない場合、前記RESエントリーが古いものであると見なし、前記RESエントリーが無効であると確定する。
【００９５】
図12は、本発明の実施例における方法によるHELLOパケットの受信フローチャートである。図12に示すように、前記ローは、次のステップを含む。
【００９６】
ステップ1201：受信が開始し；
ステップ1202：次の１つのRESエントリーを得ているかどうかを確定し、はいの場合、ステップ1203を実行し、そうでない場合、ステップ1214を実行し；
そのうち、次の１つのRESエントリーを得ている場合、次の１つのRESエントリーに対して処理を行い、次の１つのRESエントリーを得ていない場合、全てのRESエントリーに対しての処理が完了したとのことを示し、このとき、ステップ1214に進みREQ部分を処理する。
【００９７】
ステップ1203：前記RESエントリーが新しいものか古いものかをチェックし、新しいものの場合、ステップ1204を実行し、そうでない場合、ステップ1202に戻り、次の１つのRESエントリーを取得し；
そのうち、前記RESエントリーが新しいのもか古いものかを確定することは、ローカルリクエスト表中の各項目と比較することにより行うことができ、前記RESエントリーを記憶したことがあり、且つ、前記RESエントリーが指示している情報が変化していない場合、前記RESエントリーが古いものであるとのことを示し、そうでない場合、前記RESエントリーが新しいものであるとのことを示す。
【００９８】
ステップ1204：前記RESエントリーのローカル源IDがローカルノードのIDであるかどどうかを確定し、はいの場合、ステップ1205を実行し、そうでない場合、ステップ1208を実行し；
そのうち、前記RESエントリーのローカル源IDがローカルノードのIDである場合、前記RESエントリーは、ローカルノードによりリクエストされた複数タイムスロットに対応する関連情報であり、且つ、前記RESエントリーは、ローカルノードによりリクエストされた複数タイムスロットへの確認情報を含む。
【００９９】
ステップ1205：前記RESエントリーの確認情報が同意であるかどうかを判断し、反対の場合、ステップ1206を実行し、同意の場合、ステップ1207を実行し；
ステップ1206：ローカルノードによりリクエストされた複数タイムスロットが無効であると確定し、ステップ1213に戻り；
そのうち、前記RESエントリーは、ローカルノードによりリクエストされた複数タイムスロットに対応する関連情報であり、ローカルノードによりリクエストされた複数タイムスロットの関連情報は、リクエスト表に存在せず、ローカルに保存された予約履歴情報のみに存在する。よって、ステップ1213に戻った後に、ローカルリクエスト表を処理せず、ローカルに保存された予約履歴情報を変更し、例えば、ローカルに保存された予約履歴情報中のフラグ（flag）が有効である場合、それを無効に変更し、その後又は同時に、ステップ1202に戻り、次の１つのRESエントリーを取得する。
【０１００】
ステップ1207：ローカルノードによりリクエストされた複数タイムスロットが有効であると確定し、ステップ1213に戻り；
そのうち、ステップ1206と類似し、ステップ1213に戻った後に、ローカルリクエスト表を処理せず、ローカルに保存された予約履歴情報を更新し、例えば、ローカルに保存された予約履歴情報中のフラグが無効である場合、それを有効に変更し、その後又は同時にステップ1202に戻り、次の１つのRESエントリーを取得する。
【０１０１】
ステップ1208：前記RESエントリーのローカル源IDが新しいものであるかどうかを確定し、はいの場合、ステップ1212を実行し、そうでない場合、ステップ1209を実行し；
ステップ1209：前記RESエントリーの距離が、ローカルリクエスト表中の対応するエントリーの距離より小さいかどうかを判断し、はいの場合、ステップ1210を実行し、そうでない場合、ステップ1202に戻り；
ステップ1210：前記RESエントリーの確認情報が同意であるかどうかを判断し、はいの場合、ステップ1211を実行し、そうでない場合、ステップ1212を実行し；
ステップ1211：ローカルリクエスト表中の全ての1ホップ隣接ノードの確認情報を更新し；
上述のように、前記RESエントリーと、ローカルリクエスト表中の全ての1ホップ隣接ノードに対応するエントリーとを比較し、前記RESエントリーが指示している、リクエストされたタイムスロットと、ローカルリクエスト表の1ホップ隣接ノード中の確認情報が同意である1ホップ隣接ノードに対応するエントリーが指示している、リクエストされたタイムスロットとが衝突する場合、前記1ホップ隣接ノードの確認情報を反対に変更する。
【０１０２】
ステップ1212：前記RESエントリーに対応するローカルリクエスト表中のエントリーの距離を、前記RESエントリーが指示している距離に1を加算した後の値に設定し、ステップ1213に戻り；
ステップ1213：ローカルリクエスト表を更新し、又は、ローカル予約履歴情報を更新し；
上述のように、前記RESエントリーが指示している情報が異なるため、ローカルリクエスト表又はローカル予約履歴情報を更新する方法も異なる。
【０１０３】
ステップ1214：REQ部分を取得し；
ステップ1215：前記REQ部分のエントリーが新しいものか古いものかをチェックし、古いものの場合、処理を終了させ、新しいものの場合、ステップ1216を実行し；
そのうち、ローカルリクエスト表に前記エントリーを記憶したことがあり、且つ、前記エントリーが指示している情報がREQの各情報と同じである場合、前記エントリーが古いものであるとのことを示し、そうでない場合、前記エントリーが新しいものであるとのをことを示す。
【０１０４】
ステップ1216：前記エントリーの開始タイムスロットが0以上であるかどうかを判断し、はいの場合、ステップ1217を実行し、そうでない場合、ステップ1222を実行し；
そのうち、前記エントリーの開始タイムスロットが0より小さい場合、HELLOパケットの送信元が１つの有効なタイムスロットをリクエストしていないとのことを示し、このとき、ローカルリクエスト表を直接更新し、例えば、前記エントリーをローカルリクエスト表に追加してもよい。
【０１０５】
ステップ1217：前記エントリーと、ローカルリクエスト表中の1、2、…、（n-1）ホップの隣接ノードとが衝突するかどうかを判断し、はいの場合、ステップ1218を実行し、そうでない場合、ステップ1219を実行し；
ステップ1218：前記エントリーの確認情報を反対に設定し、その後、ステップ1222を実行してローカルリクエスト表を更新し；
そのうち、衝突が発生しているため、前記HELLOパケットの送信元がそのリクエストしたタイムスロットを使用できず、よって、そのリクエストした複数タイムスロットに反対の意見を与え、そして、それをローカルリクエスト表に追加する。
【０１０６】
ステップ1219：前記エントリーの確認情報を同意と設定し、その後、ステップ1220を実行し；
そのうち、衝突が発生していないため、前記HELLOパケットの送信元がそのリクエストしたタイムスロットを使用でき、よって、そのリクエストした複数タイムスロットに同意の意見を与える。
【０１０７】
ステップ1220：前記エントリーと、ローカルノードのREQ部分とが衝突するかどうかを判断し、はいの場合、ステップ1221を実行し、そうでない場合、ステップ1222を実行し；
ステップ1221：ローカルノードのREQ部分が無効であると確定し、ステップ1222を実行してローカルリクエスト表を更新し；
そのうち、前記エントリーが、ローカルリクエスト表中のエントリーと衝突しないが、ローカルのREQ部分と衝突するため、このとき、ローカルノードがそのリクエストしたタイムスロットを使用できないと確定し、ローカルに保存された予約履歴情報中のリクエストされた複数タイムスロットのフラグを無効に変更する。また、更に、確認情報が有効と設置されている前記エントリーをローカルリクエスト表に追加する必要がある。
【０１０８】
ステップ1222：ローカルリクエスト表又はローカル予約履歴情報を更新する。
【０１０９】
上述のように、異なる処理プロセスに基づいて、ローカルリクエスト表を更新する。
【０１１０】
図12の説明では、受信したHELLOパケットにREQ部分及びRES部分が含まれていることを例としているが、本実施例は、これに限定されない。上述のように、一例では、例えば、初回HELLOパケットを形成するプロセスにおいて、ローカルリクエスト表を記憶していないため、前記形成したHELLOパケットがREQ部分のみを含み、このとき、このようなHELLOパケットを受信したノードは、前記HELLOパケットの送信元によりリクエストされた複数タイムスロットに対して認証を行えば（同意又は反対の意見を付与すれば）よく、また、これに基づいて、ローカルリクエスト表又はローカル予約履歴情報を更新すればよく、即ち、ステップ1214〜1222の処理のみを実行すればよく、ここでは詳しい説明を省略する。
【０１１１】
本実施例における方法により、受信したHELLOに対してそれ相応の処理を行うことにより、より有効にタイムスロットを予約しHELLOパケットを形成することができ、タイムスロット利用率を向上させることができる。
【０１１２】
本発明の実施例では、成功裏に複数タイムスロットを予約し、予約した複数タイムスロットのタイムスロット集合を得た後に、さらに、いくつかのインタリーブ方法を用いて、前記タイムスロット集合中の複数タイムスロットを物理タイムスロット上にマッピングすることができ、これにより、インタリーブ後のタイムスロット上でデータを伝送することができる。このように、より一層、タイムスロットの割り当て効率を向上させることができる。
【０１１３】
そのうち、各ノードのインタリーブ周期を示すために、HELLOパケットに１つのインタリーブ周期のセグメントを図3Bに示すように追加する必要があり、そのうち、前記インタリーブ周期は、タイムスロットのインタリーブを採用するかどうかを示し、例えば、周期が0である場合、タイムスロットのインタリーブを使用しないことを示し、周期が0でない場合、タイムスロットのインタリーブを採用し、且つ、そのうち、前記数がインタリーブの周期に等しいことを示す。
【０１１４】
そのうち、インタリーブ後のタイムスロット及びインタリーブ前のタイムスロットは一対一で対応する。Slotinterleaving[i]により、Slot[i]のインタリーブ後のタイムスロットを示してもよい。
【０１１５】
そのうち、周期は、インタリーブの書き込み周期を表し、Stotalは、１つの割り当て周期内における可用タイムスロットの数を表す。
【０１１６】
図13は、周期が3の時に１つのインタリーブ割り当ての例を示し、図13に示すように、本発明の実施例の方法を用いてタイムスロット割り当てを行うことにより得た結果は、タイムスロット1、2、3であるが、インタリーブ割り当て後に得た結果はさ、タイムスロット1、3、6となる。
【０１１７】
図13のインタリーブ方法は例示のみであり、本発明の実施例は、これに限定されず、従来技術中の他のインタリーブ方法は同様に適用することができる。
【０１１８】
本実施例のタイムスロット割り当て方法により、タイムスロットの利用率を向上させることができる。
【０１１９】
本発明の実施例では、ネットワーク中の全てのノードがタイムスロットを予約した後に、各ノードのローカルリクエスト表がもう変化しない。このとき、各ノードは、同じ規則（ルール）を用いて予約したタイムスロットを拡張することができ、これにより、より一層、データの送信効率を向上させることができる。
【０１２０】
図14は、左へ拡張する一例を示す。図14に示すように、ノードは、ローカル表に基づいて、自分が予約したタイムスロットの左側のアイドルタイムスロットを占用し、そして、HELLOパケットによりブロードキャストする。そのうち、左側にアイドルタイムスロットがなければ、占用を拡張しない。
【０１２１】
そのうち、左への拡張は例示のみであり、本発明の実施例はこれに限定されず、他の規則に基づいて拡張を行ってもよく、例えば、右へ拡張してもよい。
【０１２２】
本発明の実施例は更にノードを次の実施例2に記載のように提供し、前記ノードが問題を解決する原理は、実施例1の方法に類似するため、その具体的な実施は、実施例1の方法の実施を参照することができ、内容が同じ処の記載はここでは省略する。
【実施例２】
【０１２３】
本発明の実施例は、マルチホップネットワーク中のノードを提供する。図15は、前記ノードの構成を示す図であり、図15に示すように、前記ノードは、次のユニットを含む。
【０１２４】
形成ユニット151：HELLOパケットを形成し、前記HELLOパケットは、前記ノードによりリクエストされた複数タイムスロットの関連情報（REQ部分）を含み、又は、前記ノードによりリクエストされた複数タイムスロットの関連情報（REQ部分）、及び、前記ノードの少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報（RES部分）を含む。
【０１２５】
送信ユニット152：形成ユニットが形成した前記HELLOパケットを送信し、前記HELLOパケットを受信したノードに、前記HELLOに含まれている情報に基づいて、前記ノードによりリクエストされた複数タイムスロットに対して認証を行わせる。
【０１２６】
そのうち、前記ノードによりリクエストされた複数タイムスロットの関連情報は、前記ノードのアドレス、前記ノードが送信しようとするデータパケットの受信ノードのアドレス、前記ノードによりリクエストされた複数タイムスロットの開始タイムスロットインデックス、及びタイムスロット長さを含み；前記ノードの少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報は、隣接ノードのアドレス、隣接ノードが送信しようとするデータパケットの受信ノードのアドレス、隣接ノードによりリクエストされた複数タイムスロットの開始タイムスロットインデックス、タイムスロット長さ、隣接ノードからローカルノードに到着する距離、及び、隣接ノードによりリクエストされた複数タイムスロットの確認情報を含む。
【０１２７】
一例では、前記ローカルノードによりリクエストされた複数タイムスロットの関連情報は更に、ローカルノードのインタリーブ周期をも含み、それ相応に、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報は更に、隣接ノードのインタリーブ周期をも含む。
【０１２８】
一例では、前記形成ユニット151は、次のモジュールを含む。
【０１２９】
第一取得モジュール1511：ルーティング表から、ローカルノードが送信しようとするデータパケットの受信ノードを選択し、前記ローカルノードが送信しようとするデータパケットの受信ノードのアドレスを得る。
【０１３０】
第二取得モジュール1512：ローカル予約履歴情報及び/又はローカルに保存されたローカルリクエスト表に基づいて、リクエストされた複数タイムスロットを確定し、これにより、リクエストされた複数タイムスロットの開始タイムスロットインデックス及びタイムスロット長さを得る。
【０１３１】
形成モジュール1513：ローカルノードが送信しようとするデータパケットの受信ノードのアドレス、リクエストされた複数タイムスロットの開始タイムスロットインデックス、タイムスロット長さ、及びローカルノードのアドレスに基づいて、前記ローカルノードによりリクエストされた複数タイムスロットの関連情報（REQ部分）を得る。
【０１３２】
そのうち、前記形成ユニット151は更に、次のモジュールをも含む。
【０１３３】
第三取得モジュール1514：所定策略に基づいて、ローカルリクエスト表から、少なくとも１つの隣接ノードの情報エントリーを、前記ノードの少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報（RES部分）として選択する。
【０１３４】
この例では、第二取得モジュール1512は、計算モジュール15121、確定モジュール15122、第一選択モジュール15123、第二選択モジュール15124、及び第三選択モジュール15125を含む。
【０１３５】
計算モジュール15121は、所要なタイムスロット長さを計算する。前記計算モジュール15121は、ローカルノードの全てのサブノードが予約したタイムスロットの長さの和に基づいて所要なタイムスロット長さを計算してもよく、ローカルノードの衝突域内の隣接ノードのトラフィックに基づいて所要なタイムスロット長さを計算してもよい。上述のようであるため、ここでは詳しい説明を省略する。
【０１３６】
確定モジュール15122は、ローカルに保存された予約履歴情報に基づいて、所要なタイムスロット長さが変化しているかどうかを確定する。
【０１３７】
第一選択モジュール15123は、所要なタイムスロット長さが変化している時に、計算された所要なタイムスロット長さに基づいて、アイドルタイムスロットを選択し、また、選択されたアイドルタイムスロットに基づいて、リクエストされた複数タイムスロットを確定する。
【０１３８】
第二選択モジュール15124は、所要なタイムスロット長さが変化しておらず、且つ、前記予約履歴情報に基づいて、前にリクエストされた複数タイムスロットが有効であると確定した時に、前記予約履歴情報に基づいて、リクエストされた複数タイムスロットを確定する。
【０１３９】
第三選択モジュール15125は、所要なタイムスロット長さが変化していないが、前記予約履歴情報に基づいて、前にリクエストされた複数タイムスロットが無効であると確定した時に、計算された所要なタイムスロット長さに基づいて、アイドルタイムスロットを選択し、そして、選択されたアイドルタイムスロットに基づいて、リクエストされた複数タイムスロットを確定する。
【０１４０】
そのうち、第一選択モジュール15123及び第三選択モジュール15125は、アイドルタイムスロットを選択する時に、先ず、開始タイムスロットを確定し、そして、前記開始タイムスロットを開始点とし、ローカルリクエスト表の情報に基づいて、連続するM個の未占用のタイムスロットを前記アイドルタイムスロットとして選択してもよく、そのうち、Mは、計算された所要なタイムスロット長さ以下である。
【０１４１】
そのうち、開始タイムスロットを確定する時に、予め構成されたタイムスロット集合から、未使用のタイムスロットを前記開始タイムスロットとしてランダムに選択してもよく；又は、予め構成されたタイムスロット集合から、一番目の未使用のタイムスロットを前記開始タイムスロットとして選択してもよく；又は、予め構成されたタイムスロット集合から、最大の未使用のタイムスロット間隔内の中間位置のタイムスロットを前記開始タイムスロットとして選択してもよく；又は、予め構成されたタイムスロット集合から、タイムスロットインデックスがローカルノードのアドレスの関数であるタイムスロットを前記開始タイムスロットとして選択してもよく；又は、ローカルノードのホップ数に基づいて、前記ホップ数に対応するタイムスロット集合から、未使用のタイムスロットを前記開始タイムスロットとして選択してもよい。ここでの予め構成されたタイムスロット集合は、予め設定されたHELLOパケット間隔中の指定フレームのデータ部分であってもよく、予め設定されたHELLOパケット間隔中の全てのフレームのデータ部分であってもよい。
【０１４２】
そのうち、連続するM個の未占用のタイムスロットを選択する時に、ローカルリクエスト表の情報に基づいて、前記開始タイムスロットから前記所要なタイムスロット長さを経って修了タイムスロットまでの範囲内の全てのタイムスロットがアイドルであるかどうかを確定し、前記範囲内の全てのタイムスロットがアイドルである時に、前記開始タイムスロットを含む連続するM個のタイムスロットを前記アイドルタイムスロットとし、そのうち、Mは、前記所要なタイムスロット長さである。そのうち、前記範囲内において少なくとも１つのタイムスロットが占用されている時に、前記範囲内の最後１つの占用されていないのタイムスロットの後の一番目のアイドルタイムスロットを、前記開始タイムスロットとし、そして、アイドルタイムスロットを再選択する。そのうち、ローカルリクエスト表の情報に基づいて、M個の連続する未占用のアイドルタイムスロットがないと確定した時に、Mの数を減らし、減らした後のMの数を所要なタイムスロット長さとし、そして、アイドルタイムスロットを再選択する。
【０１４３】
そのうち、前記第二取得モジュール1512の上述の構成は例示のみであり、ローカルに保存される予約履歴情報がない例では、ローカルリクエスト表のみに基づいて、アイドルタイムスロットを選択してもよく、また、ローカルにローカルリクエスト表（ローカルリクエスト表が空である）が保存されない例では、ランダムに又は所定策略に基づいてアイドルタイムスロットを選択してもよい。
【０１４４】
本実施例では、第三取得モジュール1514は、ローカルリクエスト表から、ローカルノードのnホップ衝突域内の1〜（n-1）ホップ隣接ノードのエントリーを、前記少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報として選択してもよく；又は、ローカルリクエスト表から、ローカルノードのnホップ衝突域内の全ての1ホップ隣接ノードのエントリー及び2〜（n-1）ホップ隣接ノードのエントリー中の確認情報が同意であるエントリーを前記少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報として選択してもよい。
【０１４５】
本実施例では、前記ノードは更に処理ユニット153を含み、それは、受信したHELLOパケットに基づいて、HELLOパケットの送信元によりリクエストされたタイムスロットに対して認証を行い、及び/又は、ローカルノードによりリクエストされた複数タイムスロットが有効であるかどうかを確定し、及び/又は、ローカルリクエスト表又はローカル予約履歴情報を更新する。
【０１４６】
そのうち、受信したHELLOパケットは、前記HELLOの送信ノードによりリクエストされた複数タイムスロットの関連情報のみを含む場合があり、又は、受信したHELLOパケットは、前記HELLOの送信ノードによりリクエストされた複数タイムスロットの関連情報、及び、前記HELLOパケットの送信ノードの少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報を含む場合がある。
【０１４７】
そのうち、前記処理ユニット153は、次のようなモジュールを含んでもよい。
【０１４８】
第一遍歴モジュール1531：前記HELLOパケット中の前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットの関連情報（HELLOパケットのREQ部分）を遍歴する。
【０１４９】
第一処理モジュール1532：前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットと、ローカルリクエスト表中の確認情報が同意である1〜（n-1）ホップ隣接ノードによりリクエストされた複数タイムスロットとが衝突する時に、前記HELLOパケットの送信ノードによりリクエストされたタイムスロットに反対を付与し、また、ローカルリクエスト表に、前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットの関連情報に対応する情報エントリーを追加し；前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットと、ローカルリクエスト表中の確認情報が同意である1〜（n-1）ホップ隣接ノードによりリクエストされた複数タイムスロットとが衝突しない時に、前記HELLOパケットの送信ノードによりリクエストされたタイムスロットに同意を付与し、また、ローカルリクエスト表に、前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットの関連情報に対応する情報エントリーを追加する。
【０１５０】
そのうち、前記第一処理モジュール1532は、前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットと、ローカルリクエスト表中の確認情報が同意である1〜（n-1）ホップ隣接ノードによりリクエストされた複数タイムスロットと衝突しない時に、前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットと、ローカルリクエストの複数タイムスロットとが衝突するかどうかを確定し、衝突する場合、ローカルノードによりリクエストされた複数タイムスロットが無効であると確認し、ローカル予約履歴情報を更新し；衝突しない場合、ローカルノードによりリクエストされた複数タイムスロットが有効であると確認し、そして、ローカル予約履歴情報を不変に維持させる。
【０１５１】
そのうち、前記処理ユニット153は更に次のモジュールを含んでもよい。
【０１５２】
第二遍歴モジュール1533：受信したHELLOパケット中の前記HELLOパケットの送信ノードの各隣接ノードによりリクエストされた複数タイムスロットの関連情報（HELLOパケットのRES部分であり、少なくとも１つのRESエントリーを含む）を遍歴する。
【０１５３】
第二処理モジュール1534：前記隣接ノードによりリクエストされた複数タイムスロットの関連情報が指示しているローカル源IDがローカルノードのIDである時に、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報が指示している確認情報に基づいて、ローカルリクエストのタイムスロットが有効であるかどうかを確定し、また、っこれに基づいて、ローカル予約履歴情報を更新し；前記隣接ノードによりリクエストされた複数タイムスロットの関連情報が指示しているローカル源IDがローカルノードのIDでない時に、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報に基づいて、ローカルリクエスト表を更新する。
【０１５４】
そのうち、前記第二処理モジュール1534は、ローカルリクエスト表中の各情報エントリーに基づいて、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報を記憶したことがあるかどうかを確定し、保存したことがない場合、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報をローカルリクエスト表に追加し、また、その対応する距離に1を加算し；保存したことがある場合、前記HELLOパケット中の前記隣接ノードの前記関連情報に対応する距離がローカルリクエスト表中の前記隣接ノードの前記関連情報に対応する距離よりも小さい時に、ローカルリクエスト表中の前記隣接ノードの前記関連情報を更新し、その対応する距離に1を加算し；前記HELLOパケット中の前記隣接ノードの前記関連情報に対応する距離がローカルリクエスト表中の前記隣接ノードの前記関連情報に対応する距離よりも小さい時に、前記HELLOパケット中の前記隣接ノードによりリクエストされた複数タイムスロットの確認情報が同意であるかどうかを判断し、同意の場合、ローカルリクエスト表中の全ての1ホップ隣接ノードの確認情報を更新する。
【０１５５】
本実施例のノードによりタイムスロット予約を行うことにより、タイムスロット割り当ての利用率を向上させることができる。
【０１５６】
本発明の上述のノード（装置）及び方法は、ハードウェアにより実現されてもよく、ハードウェアとソフトウェアとの組み合わせにより実現されてもよい。また、本発明は、このようなコンピュータ可読なプログラムにも関し、即ち、前記プログラムは、ロジック部により実行されている時に、前記ロジック部に、上述の装置又は構成部品を実現させることができ、又は、前記ロジック部に、上述の各種方法又はステップを実現させることができる。本発明は、さらに、上述のプログラムを記録している記憶媒体、例えば、ハードディスク、磁気ディスク、光ディスク、DVD、flashメモリなどにも関する。
【０１５７】
また、上述の各実施例を含む実施形態に関し、更に以下の付記を開示する。
【０１５８】
（付記1）
タイムスロット割り当て方法であって、
HELLOパケットを形成し、前記HELLOパケットは、ローカルノードによりリクエストされた複数タイムスロットの関連情報を含み、又は、ローカルノードによりリクエストされた複数タイムスロットの関連情報及びローカルノードの少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報を含み；及び
前記HELLOパケットを送信し、前記HELLOパケットを受信したノードに、前記HELLOパケットに含まれている情報に基づいて、前記ローカルノードによりリクエストされた複数タイムスロットに対して認証を行わせることを含む、方法。
【０１５９】
（付記2）
付記1に記載の方法であって、
前記ローカルノードによりリクエストされた複数タイムスロットの関連情報は、ローカルノードのアドレス、ローカルノードが送信しようとするデータパケットの受信ノードのアドレス、ローカルノードによりリクエストされた複数タイムスロットの開始タイムスロットインデックス、及びタイムスロット長さを含み；
前記隣接ノードによりリクエストされた複数タイムスロットの関連情報は、隣接ノードのアドレス、隣接ノードが送信しようとするデータパケットの受信ノードのアドレス、隣接ノードによりリクエストされた複数タイムスロットの開始タイムスロットインデックス、タイムスロット長さ、隣接ノードからローカルノードに到着する距離、及び隣接ノードによりリクエストされた複数タイムスロットの確認情報を含む、方法。
【０１６０】
（付記3）
付記2に記載の方法であって、
前記ローカルノードによりリクエストされた複数タイムスロットの関連情報は、ローカルノードのインタリーブ周期を更に含み；
前記隣接ノードによりリクエストされた複数タイムスロットの関連情報は、隣接ノードのインタリーブ周期を更に含む、方法。
【０１６１】
（付記4）
付記1に記載の方法であって、
HELLOパケットを形成するステップは、
ルーティング表から、ローカルノードが送信しようとするデータパケットの受信ノードを選択し、前記ローカルノードが送信しようとするデータパケットの受信ノードのアドレスを取得し；
ローカル予約履歴情報及び/又はローカルリクエスト表に基づいて、リクエストされた複数タイムスロットを確定し、リクエストされた複数タイムスロットの開始タイムスロットインデックス及びタイムスロット長さを取得し；及び
ローカルノードが送信しようとするデータパケットの受信ノードアドレス、リクエストされた複数タイムスロットの開始タイムスロットインデックス、タイムスロット長さ、及びローカルノードのアドレスに基づいて、前記ローカルノードによりリクエストされた複数タイムスロットの関連情報を取得することを含む、方法。
【０１６２】
（付記5）
付記4に記載の方法であって、
HELLOパケットを形成するステップは、
所定策略に基づいて、ローカルリクエスト表から、少なくとも１つの隣接ノードの情報エントリーを前記少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報として選択することを更に含む、方法。
【０１６３】
（付記6）
付記4に記載の方法であって、
リクエストされた複数タイムスロットを確定するステップは、
所要なタイムスロット長さを計算し；
ローカル予約履歴情報に基づいて、所要なタイムスロット長さが変化しているかどうかを確定し；
所要なタイムスロット長さが変化している場合、計算された所要なタイムスロット長さに基づいてアイドルタイムスロットを選択し、選択されたアイドルタイムスロットに基づいて、リクエストされた複数タイムスロットを確定し；
所要なタイムスロット長さが変化しておらず、且つ、前記予約履歴情報に基づいて、前にリクエストされた複数タイムスロットが有効であると確定した場合、前記予約履歴情報に基づいて、リクエストされた複数タイムスロットを確定し；及び
所要なタイムスロット長さが変化していないが、前記予約履歴情報に基づいて、前にリクエストされた複数タイムスロットが無効であると確定した場合、計算された所要なタイムスロット長さに基づいて、アイドルタイムスロットを選択し、選択されたアイドルタイムスロットに基づいて、リクエストされた複数タイムスロットを確定することを含む、方法。
【０１６４】
（付記7）
付記6に記載の方法であって、
所要なタイムスロット長さを計算するステップは、
ローカルノードの全てのサブノードが予約したタイムスロットの長さの和に基づいて、所要なタイムスロット長さを計算し；又は
ローカルノードの衝突域内の隣接ノードのトラフィックに基づいて、所要なタイムスロット長さを計算することを含む、方法。
【０１６５】
（付記8）
付記6に記載の方法であって、
計算された所要なタイムスロット長さに基づいて、アイドルタイムスロットを選択するステップは、
S1：開始タイムスロットを確定し；
S2：前記開始タイムスロットを開始点とし、ローカルリクエスト表の情報に基づいて、連続するM個の未占用のタイムスロットを前記アイドルタイムスロットとして選択し、そのうち、Mは、計算された所要なタイムスロット長さ以下であることを含む、方法。
【０１６６】
（付記9）
付記8に記載の方法であって、
ステップS1は、
予め構成されたタイムスロット集合から未使用のタイムスロットを前記開始タイムスロットとしてランダムに選択し；又は
予め構成されたタイムスロット集合から一番目の未使用のタイムスロットを前記開始タイムスロットとして選択し；又は
予め構成されたタイムスロット集合から、最大の未使用のタイムスロット間隔内の中間位置のタイムスロットを前記開始タイムスロットとして選択し；又は
予め構成されたタイムスロット集合から、タイムスロットインデックスがローカルノードのアドレスの関数であるタイムスロットを前記開始タイムスロットとして選択し；又は
ローカルノードのホップ数に基づいて、前記ホップ数に対応するタイムスロット集合から、未使用のタイムスロットを前記開始タイムスロットとして選択することを含む、方法。
【０１６７】
（付記10）
付記9に記載の方法であって、
前記予め構成されたタイムスロット集合は、予め設定されたHELLOパケット間隔中の指定フレームのデータ部分であり；又は
前記予め設置のタイムスロット集合は、予め設定されたHELLOパケット間隔中の全てのフレームのデータ部分である、方法。
【０１６８】
（付記11）
付記8に記載の方法であって、
ステップS2は、
ローカルリクエスト表の情報に基づいて、前記開始タイムスロットから前記所要なタイムスロット長さを経って修了タイムスロットまでで範囲内の全てのタイムスロットがアイドルであるかどうかを確定し；及び
前記範囲内の全てのタイムスロットがアイドルである場合、前記開始タイムスロットを含む連続するM個のタイムスロットを前記アイドルタイムスロットとし、そのうち、Mは、前記所要なタイムスロット長さであることを含む、方法。
【０１６９】
（付記12）
付記11に記載の方法であって、
前記範囲内において少なくとも１つのタイムスロットが占用されている場合、前記範囲内の最後の１つの占用されていないタイムスロットの後の一番目のアイドルタイムスロットを前記開始タイムスロットとし、そして、ステップS2に戻る、方法。
【０１７０】
（付記13）
付記12に記載の方法であって、
ローカルリクエスト表の情報に基づいて、M個の連続する未占用のアイドルタイムスロットがないと確定した場合、Mの数を減らし、ステップS1に戻る、方法。
【０１７１】
（付記14）
付記5に記載の方法であって、
ローカルリクエスト表から少なくとも１つの隣接ノードの情報エントリーを選択するステップは、
ローカルリクエスト表から、ローカルノードのnホップ衝突域内の1〜（n-1）ホップ隣接ノードのエントリーを、前記少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報として選択し；又は
ローカルリクエスト表から、ローカルノードのnホップ衝突域内の全ての1ホップ隣接ノードのエントリー及び2〜（n-1）ホップ隣接ノードのエントリー中の確認情報が同意であるエントリーを前記少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報として選択することを含む、方法。
【０１７２】
（付記15）
付記1に記載の方法であって、
受信したHELLOパケットに基づいて、HELLOパケットの送信ノードによりリクエストされた複数タイムスロットに対して認証を行い、及び/又は、ローカルノードによりリクエストされた複数タイムスロットが有効であるかどうかを確定し、及び/又は、ローカルリクエスト表又はローカル予約履歴情報を更新することを更に含み、
そのうち、受信したHELLOパケットは、前記HELLOの送信ノードによりリクエストされた複数タイムスロットの関連情報のみを含み、又は、受信したHELLOパケットは、前記HELLOの送信ノードによりリクエストされた複数タイムスロットの関連情報、及び、前記HELLOパケットの送信ノードの少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報を含む、方法。
【０１７３】
（付記16）
付記15に記載の方法であって、
受信したHELLOパケットは、前記HELLOの送信ノードによりリクエストされた複数タイムスロットの関連情報のみを含む場合、HELLOパケットを受信した後に、前記方法は、更に
受信したHELLOパケット中の前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットの関連情報を遍歴し；
前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットと、ローカルリクエスト表中の確認情報が同意である1〜（n-1）ホップ隣接ノードによりリクエストされた複数タイムスロットとが衝突する時に、前記HELLOパケットの送信ノードによりリクエストされたタイムスロットに反対を付与し、また、ローカルリクエスト表に前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットの関連情報に対応する情報エントリーを追加し；
前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットと、ローカルリクエスト表中の確認情報が同意である1〜（n-1）ホップ隣接ノードによりリクエストされた複数タイムスロットとが衝突しない時に、前記HELLOパケットの送信ノードによりリクエストされたタイムスロットに同意を付与し、また、ローカルリクエスト表に前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットの関連情報に対応する情報エントリーを追加し；
前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットと、ローカルリクエスト表中の確認情報が同意である1〜（n-1）ホップ隣接ノードによりリクエストされた複数タイムスロットとが衝突しない時に、前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットと、ローカルノードによりリクエストされた複数タイムスロットとが衝突するかどうかを判断し、衝突する場合、ローカルノードによりリクエストされた複数タイムスロットが無効であると確認し、また、ローカル予約履歴情報を更新し；衝突しない場合、ローカルリクエストの複数タイムスロットが有効であると確認し、また、ローカル予約履歴情報を不変にさせることを含む、方法。
【０１７４】
（付記17）
付記16に記載の方法であって、
受信したHELLOパケットは更に、HELLOパケットの送信ノードの少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報を含む場合、HELLOパケットの送信ノードによりリクエストされた複数タイムスロットの関連情報を遍歴する前に、前記方法は、更に、
受信したHELLOパケット中の前記HELLOパケットの送信ノードの各隣接ノードによりリクエストされた複数タイムスロットの関連情報を遍歴し；
前記隣接ノードによりリクエストされた複数タイムスロットの関連情報が指示しているローカル源IDがローカルノードのIDである時に、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報が指示している確認情報に基づいて、ローカルリクエストのタイムスロットが有効であるかどうかを確定し、そして、これに基づいて、ローカル予約履歴情報を更新し；及び
前記隣接ノードによりリクエストされた複数タイムスロットの関連情報が指示しているのローカル源IDがローカルノードのIDでない時に、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報に基づいてローカルリクエスト表を更新することを含む、方法。
【０１７５】
（付記18）
付記17に記載の方法であって、
前記隣接ノードによりリクエストされた複数タイムスロットの関連情報が指示している確認情報に基づいて、ローカルリクエストのタイムスロットが有効であるかどうかを確定するステップは、
前記隣接ノードによりリクエストされた複数タイムスロットの関連情報が指示している確認情報が同意である場合、ローカルノードによりリクエストされたタイムスロットが有効であると確認し、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報が指示している確認情報が反対である場合、ローカルノードによりリクエストされたタイムスロットが無効であると確認することを含む、方法。
【０１７６】
（付記19）
付記17に記載の方法であって、
前記隣接ノードによりリクエストされた複数タイムスロットの関連情報に基づいてローカルリクエスト表を更新するステップは、
ローカルリクエスト表中の各情報エントリーに基づいて、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報を保存したことがあるかどうかを確定し、保存したことがないと確認した場合、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報をローカルリクエスト表に追加し、また、それに対応する距離に1を加算し；保存したことがある場合、前記HELLOパケット中の前記隣接ノードの前記関連情報に対応する距離が、ローカルリクエスト表中の前記隣接ノードの前記関連情報に対応する距離よりも小さい時に、ローカルリクエスト表中の前記隣接ノードの前記関連情報を更新し、また、それに対応する距離に1を加算することを含む、方法。
【０１７７】
（付記20）
付記19に記載の方法であって、
前記HELLOパケット中の前記隣接ノードの前記関連情報に対応する距離がローカルリクエスト表中の前記隣接ノードの前記関連情報に対応する距離よりも小さい時に、前記方法は、更に、
前記HELLOパケット中の前記隣接ノードによりリクエストされた複数タイムスロットの確認情報が同意であるかどうかを確認し、同意の場合、ローカルリクエスト表中の全ての1ホップ隣接ノードの確認情報を更新することを含む、方法。
【０１７８】
（付記21）
ノードであって、
HELLOパケットを形成する形成ユニットであって、前記HELLOパケットは、前記ノードによりリクエストされた複数タイムスロットの関連情報を含み、又は、前記ノードによりリクエストされた複数タイムスロットの関連情報及び前記ノードの少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報を含む、形成ユニット；及び
形成ユニットが形成した前記HELLOパケットを送信し、前記HELLOパケットを受信したノードに、前記HELLOに含まれている情報に基づいて、前記ノードによりリクエストされたタイムスロットに対して認証を行わせる、送信ユニットを含む、ノード。
【０１７９】
（付記22）
付記21に記載のノードであって、
前記ノードによりリクエストされた複数タイムスロットの関連情報は、前記ノードのアドレス、前記ノードが送信しようとするデータパケットの受信ノードのアドレス、前記ノードによりリクエストされた複数タイムスロットの開始タイムスロットインデックス、及びタイムスロット長さを含み；
前記隣接ノードによりリクエストされた複数タイムスロットの関連情報は、隣接ノードのアドレス、隣接ノードが送信しようとするデータパケットの受信ノードのアドレス、隣接ノードによりリクエストされた複数タイムスロットの開始タイムスロットインデックス、タイムスロット長さ、隣接ノードからローカルノードに到着する距離、及び隣接ノードによりリクエストされた複数タイムスロットの確認情報を含む、ノード。
【０１８０】
（付記23）
付記22に記載のノードであって、
前記ローカルノードによりリクエストされた複数タイムスロットの関連情報は、ローカルノードのインタリーブ周期を更に含み、
前記隣接ノードによりリクエストされた複数タイムスロットの関連情報は、隣接ノードのインタリーブ周期を更に含む、ノード。
【０１８１】
（付記24）
付記21に記載のノードであって、
前記形成ユニットは、
ルーティング表からローカルノードが送信しようとするデータパケットの受信ノードを選択し、前記ローカルノードが送信しようとするデータパケットの受信ノードのアドレスを得る第一取得モジュール；
ローカル予約履歴情報及び/又はローカルリクエスト表に基づいて、リクエストされた複数タイムスロットを確定し、リクエストされた複数タイムスロットの開始タイムスロットインデックス及びタイムスロット長さを得る第二取得モジュール；
ローカルノードが送信しようとするデータパケットの受信ノードのアドレス、リクエストされた複数タイムスロットの開始タイムスロットインデックス、タイムスロット長さ、及びローカルノードのアドレスに基づいて、前記ローカルノードによりリクエストされた複数タイムスロットの関連情報を得る形成モジュールを含む、ノード。
【０１８２】
（付記25）
付記24に記載のノードであって、
前記形成ユニットは、更に、
所定策略に基づいて、ローカルリクエスト表から少なくとも１つの隣接ノードの情報エントリーを、前記少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報として選択する第三取得モジュールを含む、ノード。
【０１８３】
（付記26）
付記23に記載のノードであって、
第二取得モジュールは、
所要なタイムスロット長さを計算する計算モジュール；
前記予約履歴情報に基づいて、所要なタイムスロット長さが変化しているかどうかを確定する確定モジュール；
所要なタイムスロット長さが変化している時に、計算された所要なタイムスロット長さに基づいてアイドルタイムスロットを選択し、選択されたアイドルタイムスロットに基づいて、リクエストされた複数タイムスロットを確定する第一選択モジュール；
所要なタイムスロット長さが変化しておらず、且つ、前記予約履歴情報に基づいて、前にリクエストされた複数タイムスロットが有効であると確定した時に、前記予約履歴情報に基づいて、リクエストされた複数タイムスロットを確定する第二選択モジュール；及び
所要なタイムスロット長さが変化していないが、前記予約履歴情報に基づいて、前にリクエストされた複数タイムスロットが無効であると確定した時に、計算された所要なタイムスロット長さに基づいてアイドルタイムスロットを選択し、選択されたアイドルタイムスロットに基づいて、リクエストされた複数タイムスロットを確定する第三選択モジュールを含む、ノード。
【０１８４】
（付記27）
付記26に記載のノードであって、
前記計算モジュールは、ローカルノードの全てのサブノードが予約したタイムスロットの長さの和に基づいて所要なタイムスロット長さを計算し；又は、前記計算モジュールは、ローカルノードの衝突域内の隣接ノードのトラフィックに基づいて所要なタイムスロット長さを計算する、ノード。
【０１８５】
（付記28）
付記26に記載のノードであって、
前記第一選択モジュール又は前記第三選択モジュールは、アイドルタイムスロットを選択する時に、先ず、開始タイムスロットを確定し、そして、前記開始タイムスロットを開始点とし、ローカルリクエスト表の情報に基づいて、連続するM個の未占用のタイムスロットを前記アイドルタイムスロットとして選択し、そのうち、Mは、計算された所要なタイムスロット長さ以下である、ノード。
【０１８６】
（付記29）
付記28に記載のノードであって、
前記第一選択モジュール又は前記第三選択モジュールは、予め構成されたタイムスロット集合から未使用のタイムスロットを前記開始タイムスロットとしてランダムに選択し；又は、予め構成されたタイムスロット集合から一番目の未使用のタイムスロットを前記開始タイムスロットとして選択し；又は、予め構成されたタイムスロット集合から最大の未使用のタイムスロット間隔内の中間位置のタイムスロットを前記開始タイムスロットとして選択し；又は、予め構成されたタイムスロット集合からタイムスロットインデックスがローカルノードのアドレスの関数であるタイムスロットを前記開始タイムスロットとして選択し；又は、ローカルノードのホップ数に基づいて、前記ホップ数に対応するタイムスロット集合から未使用のタイムスロットを前記開始タイムスロットとして選択する、ノード。
【０１８７】
（付記30）
付記29に記載のノードであって、
前記予め構成されたタイムスロット集合は、予め設定されたHELLOパケット間隔中の所定フレームのデータ部分であり；又は、前記予め設置のタイムスロット集合は、予め設定されたHELLOパケット間隔中の全てのフレームのデータ部分である、ノード。
【０１８８】
（付記31）
付記28に記載のノードであって、
前記第一選択モジュール又は前記第三選択モジュールは、ローカルリクエスト表の情報に基づいて、前記開始タイムスロットから前記所要なタイムスロット長さを経って修了タイムスロットまでの範囲内の全てのタイムスロットがアイドルであるかどうかを確定し、前記範囲内の全てのタイムスロットがアイドルである時に、前記開始タイムスロットを含む連続するM個のタイムスロットが前記アイドルタイムスロットであると確定し、そのうち、Mは、前記所要なタイムスロット長さである、ノード。
【０１８９】
（付記32）
付記31に記載のノードであって、
前記第一選択モジュール又は前記第三選択モジュールは、前記範囲内において少なくとも１つのタイムスロットが占用されている時に、前記範囲内の最後の１つの占用されているタイムスロットの後の一番目のアイドルタイムスロットを前記開始タイムスロットとし、アイドルタイムスロットを再選択する、ノード。
【０１９０】
（付記33）
付記32に記載のノードであって、
前記第一選択モジュール又は前記第三選択モジュールは、ローカルリクエスト表の情報に基づいて、M個の連続する未占用のアイドルタイムスロットがないと確定した時に、Mの数を減らし、減らした後のMの数を所要なタイムスロット長さとし、アイドルタイムスロットを再選択する、ノード。
【０１９１】
（付記34）
付記25に記載のノードであって、
前記第三取得モジュールは、具体的に、ローカルリクエスト表からローカルノードのnホップ衝突域内の1〜（n-1）ホップ隣接ノードのエントリーを前記少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報として選択し；又は、ローカルリクエスト表からローカルノードのnホップ衝突域内の全ての1ホップ隣接ノードのエントリー及び2〜（n-1）ホップ隣接ノードのエントリー中の確認情報が同意であるエントリーを前記少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報として選択するために用いられる、ノード。
【０１９２】
（付記35）
付記21に記載のノードであって、更に、
受信したHELLOパケットに基づいて、HELLOパケットの送信ノードによりリクエストされたタイムスロットに対して認証を行い、及び/又は、ローカルノードによりリクエストされたタイムスロットが有効であるかどうかを確定し、及び/又は、ローカルリクエスト表又はローカル予約履歴情報を更新する処理ユニットを含み、
そのうち、受信したHELLOパケットは、前記HELLOの送信ノードによりリクエストされた複数タイムスロットの関連情報のみを含み、又は、受信したHELLOパケットは、前記HELLOの送信ノードによりリクエストされた複数タイムスロットの関連情報、及び、前記HELLOパケットの送信ノードの少なくとも１つの隣接ノードによりリクエストされた複数タイムスロットの関連情報を含む、ノード。
【０１９３】
（付記36）
付記35に記載のノードであって、
前記処理ユニットは、
受信したHELLOパケット中の前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットの関連情報を遍歴する第一遍歴モジュール；及び
前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットと、ローカルリクエスト表中確の認情報が同意である1〜（n-1）ホップ隣接ノードによりリクエストされた複数タイムスロットとが衝突する時に、前記HELLOパケットの送信ノードによりリクエストされたタイムスロットに反対を付与し、また、ローカルリクエスト表に前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットの関連情報に対応する情報エントリーを追加し；前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットと、ローカルリクエスト表中の確認情報が同意である1〜（n-1）ホップ隣接ノードによりリクエストされた複数タイムスロットとが衝突しない時に、前記HELLOパケットの送信ノードによりリクエストされたタイムスロットに同意を付与し、また、ローカルリクエスト表に前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットの関連情報に対応する情報エントリーを追加する、第一処理モジュールを含む、ノード。
【０１９４】
（付記37）
付記36に記載のノードであって、
前記第一処理モジュールは、前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットと、ローカルリクエスト表中の確認情報が同意である1〜（n-1）ホップ隣接ノードによりリクエストされた複数タイムスロットとが衝突しない時に、前記HELLOパケットの送信ノードによりリクエストされた複数タイムスロットと、ローカルノードによりリクエストされた複数タイムスロットとが衝突するかどうかを判断し、衝突する場合、ローカルノードによりリクエストされた複数タイムスロットが無効であると確定し、また、ローカル予約履歴情報を変更し；衝突しない場合、ローカルノードによりリクエストされた複数タイムスロットが有効であると確定し、また、ローカル予約履歴情報を不変にさせる、ノード。
【０１９５】
（付記38）
付記36又は37に記載のノードであって、
前記処理ユニットは、更に、
受信したHELLOパケット中の前記HELLOパケットの送信ノードの各隣接ノードによりリクエストされた複数タイムスロットの関連情報を遍歴する第二遍歴モジュール；及び
前記隣接ノードによりリクエストされた複数タイムスロットの関連情報が指示しているローカル源IDがローカルノードのIDである時に、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報が指示している確認情報に基づいて、ローカルノードによりリクエストされたタイムスロットが有効であるかどうかを確定し、そして、これに基づいてローカル予約履歴情報を更新し；前記隣接ノードによりリクエストされた複数タイムスロットの関連情報が指示しているローカル源IDがローカルノードのIDでない時に、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報に基づいて、ローカルリクエスト表を更新する第二処理モジュールを含む、ノード。
【０１９６】
（付記39）
付記38に記載のノードであって、
前記第二処理モジュールは、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報が指示している確認情報に基づいて、ローカルノードによりリクエストされたタイムスロットが有効であるかどうかを確定する時に、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報が指示している確認情報が同意である場合、ローカルノードによりリクエストされたタイムスロットが有効であると確定し、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報が指示している確認情報が反対である場合、ローカルノードによりリクエストされたタイムスロットが無効であると確認する、ノード。
【０１９７】
（付記40）
付記38に記載のノードであって、
前記第二処理モジュールは、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報に基づいてローカルリクエスト表を更新する時に、ローカルリクエスト表中の各情報エントリーに基づいて、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報を保存したことがあるかどうかを確定し、保存したことがない場合、前記隣接ノードによりリクエストされた複数タイムスロットの関連情報をローカルリクエスト表に追加し、また、それに対応する距離に1を加算し；保存したことがある場合、前記HELLOパケット中の前記隣接ノードの前記関連情報に対応する距離が、ローカルリクエスト表中の前記隣接ノードの前記関連情報に対応する距離よりも小さい時に、ローカルリクエスト表中の前記隣接ノードの前記関連情報を更新し、また、それに対応する距離に1を加算し；前記HELLOパケット中の前記隣接ノードの前記関連情報に対応する距離が、ローカルリクエスト表中の前記隣接ノードの前記関連情報に対応する距離よりも小さい時に、前記HELLOパケット中の前記隣接ノードによりリクエストされた複数タイムスロットの確認情報が同意であるかどうかを判断し、同意の場合、ローカルリクエスト表中の全ての1ホップ隣接ノードの確認情報を更新する、ノード。
【０１９８】
以上、本発明の好ましい実施形態を説明したが、本発明はこの実施形態に限定されず、本発明の趣旨を離脱しない限り、本発明に対するあらゆる変更は本発明の技術的範囲に属する。
【図１】
2015056899.tif 000008
【図３Ａ】
2015056899.tif 000009
【図３Ｂ】
2015056899.tif 000010
【図４】
2015056899.tif 000011
【図５】
2015056899.tif 000012
【図６】
2015056899.tif 000013
【図７】
2015056899.tif 000014
【図８】
2015056899.tif 000015
【図９】
2015056899.tif 000016
【図１０】
2015056899.tif 000017
【図１１】
2015056899.tif 000018
【図１２】
2015056899.tif 000019
【図１３】
2015056899.tif 000020
【図１５】
2015056899.tif 000021
【図２】
2015056899.tif 000022
【図１４】
2015056899.tif 000023