(57)【要約】【課題】タイムスロット割り当て方法及び装置を提供する。【解決手段】かかる方法は、ローカルノードのタイムスロットリクエスト情報を含み、又は、ローカルノードのタイムスロットリクエスト情報及び少なくとも一つの隣接ノードのタイムスロットリクエスト情報を含むHELLOパケットを形成し；及び、前記HELLOパケットを送信し、前記HELLOパケットを受信したノードに、前記タイムスロットリクエスト情報に基づいて、HELLOパケットの送信元によりリクエストされた予約タイムスロットに対して認証を行わせることを含む。【選択図】図５
2015056895.tif 000002
【特許請求の範囲】
【請求項１】
マルチホップネットワーク中のノードであって、
ローカルノードのタイムスロットリクエスト情報を含み、又は、ローカルノードのタイムスロットリクエスト情報及びローカルノードの少なくとも一つの隣接ノードのタイムスロットリクエスト情報を含むHELLOパケットを形成する形成ユニット；及び
前記HELLOパケットを送信し、前記HELLOパケットを受信したノードに、前記タイムスロットリクエスト情報に基づいて、前記ノードによりリクエストされた予約タイムスロットに対して認証を行わせる送信ユニットを含み、
前記ローカルノードのタイムスロットリクエスト情報は、ローカルノードのアドレス、ローカルノードが送信しようとするデータパケットの受信ノードのアドレス、及びローカルノードによりリクエストされた予約タイムスロットのインデックスを含み；前記隣接ノードのタイムスロットリクエスト情報は、隣接ノードのアドレス、前記隣接ノードが送信しようとするデータパケットの受信ノードのアドレス、前記隣接ノードによりリクエストされた予約タイムスロットのインデックス、及び前記隣接ノードによりリクエストされた予約タイムスロットの確認情報を含む、ノード。
【請求項２】
請求項1に記載のノードであって、
前記形成ユニットは、
ルーティング表から、前記ローカルノードが送信しようとするデータパケットの受信ノードを選択し、前記ローカルノードが送信しようとするデータパケットの受信ノードのアドレスを得る第一取得モジュール；
前記ローカルノードが送信しようとするデータパケットのために予約タイムスロットを選択し、前記ローカルノードによりリクエストされた予約タイムスロットのインデックスを得る第二取得モジュール；及び
前記ローカルノードが送信しようとするデータパケットの受信ノードのアドレス、前記ローカルノードによりリクエストされた予約タイムスロットのインデックス、及びローカルノードのアドレスに基づいて、前記HELLOパケット中のローカルノードのタイムスロットリクエスト情報を形成する形成モジュールを含む、ノード。
【請求項３】
請求項2に記載のノードであって、
前記形成ユニットは、更に、
所定策略に基づいて、ローカルリクエスト表が非空である時に、ローカルリクエスト表から、少なくとも一つの隣接ノードの情報エントリーを前記ローカルノードの少なくとも一つの隣接ノードのタイムスロットリクエスト情報として選択する第三取得モジュールを含み、
前記形成モジュールは、前記ローカルノードの少なくとも一つの隣接ノードのタイムスロットリクエスト情報に基づいて、前記HELLOパケット中のローカルノードの少なくとも一つの隣接ノードのタイムスロットリクエスト情報を形成する、ノード。
【請求項４】
請求項2に記載のノードであって、
前記第二取得モジュールは、
予約履歴情報に基づいて、ローカルノードが前にリクエストした予約タイムスロットが有効であるかどうかを確認し；
ローカルノードが前にリクエストした予約タイムスロットが有効である時に、ローカルノードが前にリクエストした予約タイムスロットを前記予約タイムスロットとし；
ローカルノードが前にリクエストした予約タイムスロットが無効である時に、予め構成されたタイムスロット集合から、未使用のタイムスロットを前記予約タイムスロットとしてランダムに選択し、又は、予め構成されたタイムスロット集合から、一つ目の未使用のタイムスロットを前記予約タイムスロットとして選択し、又は、予め構成されたタイムスロット集合から、最大の未使用のタイムスロットの間隔内の中間位置のタイムスロットを前記予約タイムスロットとして選択し、又は、予め構成されたタイムスロット集合から、タイムスロットインデックスが前記ローカルノードのアドレスの関数であるタイムスロットを前記予約タイムスロットとして選択し、又は、ローカルノードのホップ数に基づいて、該ホップ数に対応するタイムスロット集合から、未使用のタイムスロットを前記予約タイムスロットとして選択するために用いられる、ノード。
【請求項５】
請求項1に記載のノードであって、更に、
受信したHELLOパケットに基づいて、HELLOパケットの送信元によりリクエストされた予約タイムスロットに対して認証を行い、及び/又は、ローカルノードによりリクエストされた予約タイムスロットが有効であるかどうかを確認し、及び/又は、ローカルリクエスト表を更新し、及び/又は、ローカル予約履歴情報を更新する処理ユニットを含み、
受信したHELLOパケットは、HELLOパケットの送信元のタイムスロットリクエスト情報を含み、又は、HELLOパケットの送信元のタイムスロットリクエスト情報及び前記HELLOパケットの送信元の少なくとも一つの隣接ノードのタイムスロットリクエスト情報を含む、ノード。
【請求項６】
請求項5に記載のノードであって、
前記処理ユニットは、
受信したHELLOパケット中の、HELLOパケットの送信元のタイムスロットリクエスト情報を遍歴する第一遍歴モジュール；及び
受信したHELLOパケットの送信元のタイムスロットリクエスト情報と、ローカルリクエスト表中の確認情報が同意である情報エントリーとを比較し；受信したHELLOパケットの送信元のタイムスロットリクエスト情報が指示している、リクエストされた予約タイムスロットと、ローカルリクエスト表中の確認情報が同意である情報エントリーが指示している、リクエストされた予約タイムスロットとが衝突する場合、受信したHELLOパケットの送信元によりリクエストされた予約タイムスロットに「反対」を付与し、ローカルリクエスト表に、該受信したHELLOパケットの送信元のタイムスロットリクエスト情報に対応する情報エントリーを新しく追加し；受信したHELLOパケットの送信元のタイムスロットリクエスト情報が指示している、リクエストされた予約タイムスロットと、ローカルリクエスト表中の確認情報が同意である情報エントリーが指示している、リクエストされた予約タイムスロットとが衝突しない場合、受信したHELLOパケットの送信元によりリクエストされた予約タイムスロットに「同意」を付与し、ローカルリクエスト表に、該受信したHELLOパケットの送信元のタイムスロットリクエスト情報に対応する情報エントリーを新しく追加する第一処理モジュールを含む、ノード。
【請求項７】
請求項6に記載のノードであって、
前記第一処理モジュールは、更に、
受信したHELLOパケットの送信元のタイムスロットリクエスト情報が指示している、リクエストされた予約タイムスロットと、ローカルリクエスト表中の確認情報が同意である情報エントリーが指示している、リクエストされた予約タイムスロットとが衝突しない時に、受信したHELLOパケットの送信元のタイムスロットリクエスト情報が指示している、リクエストされた予約タイムスロットと、ローカルノードにリクエストされた予約タイムスロットとが衝突するかどうかを判断し；衝突する場合、ローカルノードによりリクエストされた予約タイムスロットが無効であると確認し、ローカル予約履歴情報を更新し；衝突しない場合、ローカルノードによりリクエストされた予約タイムスロットが有効であると確認し、ローカル予約履歴情報を不変に維持させるために用いられる、ノード。
【請求項８】
請求項6に記載のノードであって、
前記処理ユニットは、更に、
受信したHELLOパケット中の、HELLOパケットの送信元の少なくとも一つの隣接ノードのタイムスロットリクエスト情報中の、各タイムスロットリクエスト情報を遍歴する第二遍歴モジュール；及び
該タイムスロットリクエスト情報が指示しているローカルソースIDがローカルノードのIDである時に、該タイムスロットリクエスト情報が指示している確認情報に基づいて、ローカルノードによりリクエストされた予約タイムスロットが有効であるかどうかを確認し；該タイムスロットリクエスト情報が指示しているローカルソースIDがローカルノードのIDでない時に、該タイムスロットリクエスト情報が指示している確認情報に基づいてローカルリクエスト表を更新する第二処理モジュールを含む、ノード。
【請求項９】
請求項8に記載のノードであって、
前記第二処理モジュールが、該タイムスロットリクエスト情報が指示している確認情報に基づいて、ローカルノードによりリクエストされた予約タイムスロットが有効であるかどうかを確認する時に、該タイムスロットリクエスト情報が指示している確認情報が同意である場合、前記第二処理モジュールは、ローカルノードによりリクエストされた予約タイムスロットが有効であると確認し；該タイムスロットリクエスト情報が指示している確認情報が反対である場合、前記第二処理モジュールは、ローカルノードによりリクエストされた予約タイムスロットが無効であると確認し、ローカル予約履歴情報を更新し；
前記第二処理モジュールが、該タイムスロットリクエスト情報が指示している確認情報に基づいて、ローカルリクエスト表を更新する時に、該タイムスロットリクエスト情報が指示している確認情報が反対である場合、前記第二処理モジュールは、これに基づいてローカルリクエスト表を直接更新し；該タイムスロットリクエスト情報が指示している確認情報が同意である場合、前記第二処理モジュールは、該タイムスロットリクエスト情報が指示しているローカルソースIDがローカルノードの１ホップ隣接ノードのIDであるかどうかを確認し、はいの場合、これに基づいてローカルリクエスト表を直接更新し、いいえの場合、これに基づいてローカルリクエスト表中の１ホップ隣接ノードの情報エントリーを更新する、ノード。
【請求項１０】
タイムスロット割り当て方法であって、
ローカルノードのタイムスロットリクエスト情報を含み、又は、ローカルノードのタイムスロットリクエスト情報及び少なくとも一つの隣接ノードのタイムスロットリクエスト情報を含む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パケットの送信元によりリクエストされた予約タイムスロットに対して認証を行わせることを含み、
そのうち、前記ローカルノードのタイムスロットリクエスト情報は、ローカルノードのアドレス、ローカルノードが送信しようとするデータパケットの受信ノードのアドレス、及び、ローカルノードにリクエストされた予約タイムスロットのインデックスを含み；前記隣接ノードのタイムスロットリクエスト情報は、隣接ノードのアドレス、前記隣接ノードが送信しようとするデータパケットの受信ノードのアドレス、前記隣接ノードによりリクエストされた予約タイムスロットのインデックス、及び、前記隣接ノードによりリクエストされた予約タイムスロットの確認情報を含む。
【０００９】
本発明の実施例の有益な効果は、本発明の実施例における方法及び装置により、マルチブランチのAd  hocネットワークに用いる、現在のルーティングプロトコル及び802.15.4規格に完全に符合する、HELLOパケットに基づくタイムスロット割り当て方案を提供し、これにより、背景技術に記載のようなデータ衝突の問題を解決し、且つ高いサービス品質のAd  hoc応用をサポートすることができる。
【図面の簡単な説明】
【００１０】
【図１】時間領域でのHELLOパケット及びデータパケットの分布型伝送を示す図である。
【図２】スーパーフレームを示す図である。
【図３】HELLOパケットのフォーマットの一例を示す図である。
【図４】HELLOパケットの送信及び受信のフローチャートである。
【図５】本発明の実施例におけるタイムスロット割り当て方法のフローチャートである。
【図６】本発明の実施例におけるHELLOパケットのREQ部分を形成するフローチャートである。
【図７】本発明の実施例における方法による予約タイムスロットの選択を示す図である。
【図８】本発明の実施例における方法によるHELLOパケットの形成及び送信のフローチャートである。
【図９】受信したHELLOパケットを処理する一例のフローチャートである。
【図１０】受信したHELLOパケットを処理する他の例のフローチャートである。
【図１１】本発明の実施例における方法によるHELLOパケットの受信のフローチャートである。
【図１２】本発明の実施例におけるノードの構成図である。
【発明を実施するための形態】
【００１１】
以下、添付した図面を参照しながら、本発明を実施するための形態を詳細に説明する。
【００１２】
なお、当業者が容易に本発明の原理及び実施形態を理解し得るために、本発明の実施例では、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部分と称され、隣接ノードのリクエストへのレスポンス、即ち、ローカルノードの少なくとも一つの隣接ノードのタイムスロットリクエスト情報を示し、各隣接ノードに対応し、該隣接ノードのリクエストへのレスポンスを含む。
【００１７】
HELLOパケットの第二部分では、各レスポンスは、少なくとも４つのセグメント、即ち、ローカルソースID、ローカル目標ID、タイムスロットインデックス、及び確認情報を含む。ローカルソースIDは、データパケットの送信元のアドレスを表し、HELLOパケットが自分のためにタイムスロットを予約するために用いられる場合、HELLOパケットの送信元のIDに等しい。ローカル目標IDは、データパケットの受信アドレスを表し、マルチホップAd  hocネットワーク中で、ネクストホップのアドレスを指し、ネットワークがツリー型トポロジーである場合、親ノードのIDをも指す。タイムスロットインデックスは、ローカルソースが予約したい最適なタイムスロットを表し、該タイムスロットは、隣接ノードが送信したHELLOパケット中から抽出した該隣接ノードの選択への観察に基づいて選択される。確認情報は、隣接ノードからのフィードバックであり、該確認情報は、「同意」又は「反対」により、ローカルソースがその最適なタイムスロットを予約することができるかどうかを指示する。一つのHELLOパケットを受信すると、ローカルソースIDがHELLOパケットの送信元のIDに等しい場合、各ノードは、該確認情報の値を確定することができる。HELLOパケットの第一部分は、前の３つのセグメントのみ、即ち、ローカルソースID、ローカル目標ID、及びタイムスロットインデックスのみを含む。HELLOパケットのフォーマットは、図3に示される。
【００１８】
本発明の実施例では、隣接ノードの予約を記録し、また、各タイムスロット中の状態更新を追跡するために、各ノードは、一つのローカル表を維持する必要があり、該ローカル表には、複数のエントリーを含み、各エントリーは、少なくとも、受信したHELLOパケット中のRES部分と同様の４つのセグメント、即ち、ローカルソースID、ローカル目標ID、タイムスロットインデックス、及び確認情報を含む。表1は、ローカル表の一例であり、本実施例では、ローカルリクエスト表又はリクエスト表とも称される。
【表１】
2015056895.tif 000003
【００１９】
本発明の実施例では、HELLOパケットの交換プロセスは図4に示される。HELLOパケットの伝送は、ローカルタイマーによりスケジューリングされる。ローカルタイマーが起動する時に、HELLOパケットの送信ノードは、先ず、HELLOパケットの上述の２つの部分の内容を決定し、そして、該HELLOパケットを形成する。該HELLOパケットを受信すると、HELLOパケットの受信ノードは、ローカル観察、例えば、ローカルリクエスト表に基づいて、該HELLOパケット中のREQ部分に関連する確認値、即ち、該HELLOパケットの送信ノードによりリクエストされた予約タイムスロットに同意するかどうかを決定する。また、HELLOパケットから取得した全ての情報は、ローカルリクエスト表を更新するために用いるべきである。
【００２０】
本発明の実施例では、各ノードは更に、その前に予約したタイムスロットをも含み、それは、予約履歴情報と称され、タイムスロットのインデックス及び状態を含み、次回HELLOパケットを形成する時にアイドル（idle）タイムスロットを選択するための参考とされる。
【００２１】
本発明の実施例では、HELLOパケットの伝送プロセスにおいて、ノードは、使用可能なアイドルタイムスロットを見つけてHELLOパケットのREQ部分を形成し、また、リクエスト表から適切な情報を見つけてHELLOパケットのRES部分を形成する必要がある。以下、図面及び具体的な実施例に基づいて、本発明の実施例におけるタイムスロット割り当て方法及び装置について詳細に説明する。
【実施例１】
【００２２】
本発明の実施例は、タイムスロット割り当て方法を提供し、該方法は、マルチホップネットワーク中のノードに用いる。図5は、該方法のフローチャートであり、図5に示すように、該方法は、次のステップを含む。
【００２３】
ステップ501：HELLOパケットを形成し、前記HELLOパケットは、ローカルノードのタイムスロットリクエスト情報を含み、又は、ローカルノードのタイムスロットリクエスト情報及びローカルノードの少なくとも一つの隣接ノードのタイムスロットリクエスト情報を含む。
【００２４】
ステップ502：前記HELLOパケットを送信し、該HELLOパケットを受信したノードに、前記タイムスロットリクエスト情報に基づいて、前記ローカルノードによりリクエストされた予約タイムスロットに対して認証を行わせる。
【００２５】
そのうち、前記ローカルノードのタイムスロットリクエスト情報は、ローカルノードのアドレス、ローカルノードが送信しようとするデータパケットの受信ノードのアドレス、及びローカルノードによりリクエストされた予約タイムスロットのインデックスを含み；前記隣接ノードのタイムスロットリクエスト情報は、隣接ノードのアドレス、前記隣接ノードが送信しようとするデータパケットの受信ノードのアドレス、前記隣接ノードによりリクエストされた予約タイムスロットのインデックス、及び前記隣接ノードによりリクエストされた予約タイムスロットの確認情報を含む。
【００２６】
本実施例では、上述のように、ローカルノード（本発明ではローカルとも称される）のタイムスロットリクエスト情報をHELLOパケットのREQ部分と言い、隣接ノードのタイムスロットリクエスト情報をRES部分と言う。そのうち、REQ部分は、HELLO  sender（HELLOパケットの送信ノードであり、送信ノード又はHELLOパケットの送信元とも称される）が、送信しようとするデータパケットのためにリクエストした予約タイムスロットを示し、RES部分は、HELLO  senderの各隣接ノードが、各自のデータパケットのためにリクエストした予約タイムスロット、及び、リクエストした予約タイムスロットの確認情報を示す。
【００２７】
図3は、本発明の実施例におけるHELLOパケットのフォーマットの一例を示す図である。図3に示すように、該HELLOパケットのREQ部分について言えば、Local  Source  ID（ローカルソースID）は、送信ノードのアドレス、即ち、HELLO  senderのアドレスであり；Local  Destination  ID（ローカル目標ID）は、受信ノードのアドレス、即ち、HELLO  senderが送信しようとするデータパケットの受信ノードのアドレスであり；Slot  index（タイムスロットインデックス）は、HELLO  senderが、送信しようとするデータパケットのためにリクエストした予約タイムスロット（予約タイムスロットとも称される）のインデックスである。該HELLOパケットのRES部分について言えば、複数の情報エントリーを含み、各情報エントリーは、該HELLO  senderの一つの隣接ノードに対応し、該隣接ノードのアドレス（Local  Source  ID  1〜n）、該隣接ノードが送信しようとするデータパケットの受信ノードのアドレス（Local  Destination  ID1〜n）、該隣接ノードが、送信しようとするデータパケットのためにリクエストした予約タイムスロットのインデックス（Slot  index1〜n）、及び該リクエストされた予約タイムスロットの確認情報（Confirmation1〜n）を含む。
【００２８】
本実施例では、HELLOパケットにより、送信しようとするデータのためにタイムスロットを予約するためには、先ず、HELLOパケットを形成する必要があり、このHELLOパケットは、図3に示すように、REQ部分及びRES部分を含んでもよく、REQ部分のみを含んでRES部分を含まなくてもよく、例えば、一回目HELLOパケットによりタイムスロットを予約するノードについては、他の隣接ノードのタイムスロットリクエスト情報をまだ取得していないため、RES部分が空である。
【００２９】
本実施例では、該HELLOパケットのREQ部分の３つのセグメントについては、図6に示す方法により取得してもよく、図6に示すように、該方法は、次のステップを含む。
【００３０】
ステップ601：ルーティング表から、前記ローカルノードが送信しようとするデータパケットの受信ノードを選択し、前記ローカルノードが送信しようとするデータパケットの受信ノードアドレスを取得する。
【００３１】
本実施例では、各ノードは、１つのルーティング表を維持（保存）し、該ルーティング表は、該ノードが目標ノード（例えば、ゲートウェイ）に到達するネクストホップノード及びルーティングコストを表2に示すように記憶する。表2は、ルーティング表の構成を示す。
【表２】
2015056895.tif 000004
【００３２】
ステップ601では、ノードは、ルーティングコスト最小のルーティング経路（即ち、ネクストホップノード）を選択してデータ転送を行ってもよく、この場合、該ルーティングコスト最小のルーティング経路のノードのアドレスは、前記受信ノードのアドレスになる。
【００３３】
ステップ602：前記ローカルノードが送信しようとするデータパケットのために予約タイムスロットを選択し、前記ローカルノードがリクエストした予約タイムスロットのインデックスを取得する。
【００３４】
本実施例では、各ノードは、毎回タイムスロットを予約した後に、その予約したタイムスロットの情報を予約履歴情報として一時的に保存してもよく、ここでの予約タイムスロットの情報は、リクエストした予約タイムスロットのインデックスだけでなく、リクエストした該予約タイムスロットの状態をも含み、後者は、フラグ（flag）により表され、該フラグは、該予約タイムスロットが有効であるかどうかを示し、例えば、valid及びinvalidにより有効及び無効をそれぞれ示してもよい。
【００３５】
ステップ602では、先ず、ローカル予約履歴情報に基づいて、前にリクエストした予約タイムスロットが有効であるかどうかを確定してもよく、有効の場合、前にリクエストした予約タイムスロットを今回のリクエストする予約タイムスロットとし；無効、又は、前にリクエストした予約タイムスロット無しの場合、予約タイムスロットを再選択してもよい。
【００３６】
本実施例では、図7に示すように、予め構成されたタイムスロット集合（セット）から、未使用のタイムスロットを前記予約タイムスロットとしてランダムに選択してもよく；予め構成されたタイムスロット集合から、１つ目の未使用のタイムスロットを前記予約タイムスロットとして選択してもよく；予め構成されたタイムスロット集合から、最大の未使用のタイムスロットの間隔内の中間位置のタイムスロットを前記予約タイムスロットとして選択してもよく；予め構成されたタイムスロット集合から、タイムスロットインデックスが前記ローカルノードのアドレスの関数であるタイムスロットを前記予約タイムスロットとして選択してもよく、例えば、関数si=f(IDi)=IDimodKであり、そのうち、siは、ノードiのために割り当てられたタイムスロットインデックスを示し、IDiは、ノードiのIDを示し、Kは、トータルな可用タイムスロットの個数を示し；又は、ローカルノードのホップ数に基づいて、該ホップ数が対応するタイムスロット集合から、未使用のタイムスロットを前記予約タイムスロットとして選択してもよい。
【００３７】
そのうち、予め構成されたタイムスロット集合は、予め設定されたHELLOパケットの間隔のうち指定（所定）フレームのデータ部分であってもよく、予め設定されたHELLOパケットの間隔のうち全てのフレームのデータ部分であってもよい。本実施例は、これに限定されない。そのうち、好ましくは、指定フレームと、HELLOパケットが所在するフレームとの間隔は、HELLOパケットの間隔の2/5又は4/5である。
【００３８】
そのうち、表3は、本実施例の一例におけるローカルノードのホップ数と、タイムスロット集合との対応関係の記憶表であり、しかし、本実施例は、これに限定されない。
【表３】
2015056895.tif 000005
【００３９】
ステップ603：前記ローカルノードが送信しようとするデータパケットの受信ノードのアドレス、前記予約タイムスロットのタイムスロットインデックス、及びローカルノードのアドレスに基づいて、前記ローカルノードのタイムスロットリクエスト情報を取得する。
【００４０】
そのうち、ステップ601及びステップ602により、データパケットの受信ノードのアドレス及びリクエストされた予約タイムスロットのインデックスをそれぞれ取得した後に、更にローカルアドレスに基づければ、HELLOパケットのREQ部分を構成する内容、即ち、ローカルのタイムスロットリクエスト情報を取得することができる。
【００４１】
本実施例では、該HELLOパケットのRES部分の情報エントリーについては、所定策略に基づいて、ローカルリクエスト表から選択することができる。
【００４２】
本実施例では、各ノードはさらに１つのローカルリクエスト表（リクエスト表とも称される）を保存し、この表は、表1に示すようなものであるため、ここでは詳しい説明を省略する。
【００４３】
本実施例の一例では、表1に示すように、確認情報が“1”のときは、“同意”を表し、即ち、予約タイムスロットを使用できることを表し、例えば、ノードAは、タイムスロットインデックスが“1”のタイムスロットを用いてデータパケットをノードBに送信することができ、また、例えば、ノードEは、タイムスロットインデックスが“4”のタイムスロットを用いてデータパケットをノードFに送信することができ；確認情報が“0”のときは、“反対”を表し、即ち、該タイムスロットを予約しても、それを使用できないことを表し、例えば、ノードCは、タイムスロットインデックスが“1”のタイムスロットを用いてデータパケットをノードDに送信することができない。
【００４４】
本実施例では、該リクエスト表中の情報エントリーは、受信したHELLOパケット基づいて形成する及び更新することができ、具体的には、後述する。
【００４５】
一例では、該ノードがHELLOパケットを受信していない時に、例えば、初期プロセスの時に、リクエスト表に情報エントリーが存在しないため、該ノードが形成したHELLOパケットにはREQ部分のみが存在し、RES部分が存在しない。
【００４６】
他の例では、リクエスト表が非空であり、この場合、該ノードは、所定策略に基づて、リクエスト表から、一部の情報エントリーをHELLOパケットのRES部分の情報エントリーとして選択することができる。
【００４７】
そのうち、該所定策略は、ローカルリクエスト表から、送信ノードがローカルノードの１ホップ隣接ノードであるエントリーを、前記HELLOパケットのRES部分として選択するとのことであってもよく；ローカルリクエスト表から、受信ノードがローカルノードの１ホップ隣接ノードであるエントリーを、前記HELLOパケットのRES部分として選択するとのことであってもよく；ローカルリクエスト表から、送信ノード及び受信ノードがともにローカルノードの１ホップ隣接ノードであるエントリーを、前記HELLOパケットのRES部分として選択するとのことであってもよい。なお、以上は、例示のみであり、本実施例は、これに限定されない。
【００４８】
図8は、本実施例の方法により、HELLOパケットを形成及び送信するフローチャートであり、図8に示すように、該プロセスは、次のステップを含む。
【００４９】
ステップ801：HELLOパケットタイマーが起動し；
ステップ802：ルーティング表に基づいて、データパケットの受信ノードのアドレスを確定し；
ステップ803：前に選択したタイムスロットが有効であるかどうかを判断し、有効の場合、ステップ805を実行し、無効の場合、ステップ804を実行し；
ステップ804：新しいアイドルタイムスロットを選択し；
そのうち、選択する方法は、上述のように複数があり、ここでは、詳しい説明を省略する。
【００５０】
ステップ805：HELLOパケットのREQ部分を形成し；
ステップ806：ローカルリクエスト表から情報エントリーを選択し；
そのうち、選択する方法は、上述のように複数があり、ここでは、詳しい説明を省略する。
【００５１】
ステップ807：HELLOパケットのRES部分を形成し；
ステップ808：HELLOパケットを送信する。
【００５２】
本実施例では、各ノードは、本実施例の方法によってHELLOパケットを送信した後に、該HELLOパケットは、ブロードキャストで送信したので、隣接ノードは、該HELLOパケットを受信することができる。該HELLOパケットには、HELLOパケットの送信ノードのタイムスロットリクエスト情報、及び、該HELLOパケットの送信ノードの隣接ノードのタイムスロットリクエスト情報を含んでいるので、該HELLOパケットを受信したノードは、これに基づいて、HELLOパケットの送信ノードによりリクエストされたタイムスロットに対して認証を行うことができ、又は、これに基づいて、ローカルリクエスト表を更新してもよく、又は、これに基づいて、ローカルリクエスト表を更新し、また、自分が前にリクエストした予約タイムスロットが有効であるかどうかを確定し（何故なら、自分のタイムスロットリクエスト情報は該HELLOパケットのRES部分に存在する可能性がある）、そして、これを踏まえて、さらに、本実施例の方法によってタイムスロット予約（上述のように、本実施例の方法により、HELLOパケットを形成及び送信する）を行う。
【００５３】
よって、本実施例では、図5に示すように、該方法は、更に次のステップを含んでもよい。
【００５４】
ステップ503：受信したHELLOパケットに基づいて、HELLOパケットの送信元によりリクエストされた予約タイムスロットに対して認証を行い、及び/又は、ローカルノードによりリクエストされた予約タイムスロットが有効であるかどうかを確定し、及び/又は、ローカルリクエスト表を更新し、及び/又は、ローカル予約履歴情報を更新する。
【００５５】
本実施例の一例では、受信したHELLOパケットがHELLOパケットの送信元のタイムスロットリクエスト情報のみ、即ち、REQ部分のみを含んでいる場合、ステップ503は、図9に示す方法により実現されてもよく、図9に示すように、該方法は、次のステップを含む。
【００５６】
ステップ901：受信したHELLOパケットのREQ部分を遍歴し；
ステップ902：該REQ部分と、ローカルリクエスト表中の確認情報が同意である各情報エントリーとを比較することにより、該HELLOパケットの送信元によりリクエストされた予約タイムスロットに対して認証（即ち、同意又は反対を付与する）を行い、また、これに基づいて、ローカルリクエスト表及びローカル予約履歴情報を更新する。
【００５７】
具体的には、ステップ902では、該REQ部分が指示している、リクエストされた予約タイムスロットと、ローカルリクエスト表中の確認情報が同意である各エントリーが指示している、リクエストされた予約タイムスロットとが衝突しない場合、該HELLOパケットの送信元によりリクエストされた予約タイムスロットに同意を付与し、そうでない場合、該HELLOパケットの送信元によりリクエストされた予約タイムスロットに反対を付与する。そのうち、該HELLOパケットの送信元によりリクエストされた予約タイムスロットに対して認証を行った後に、更に、これに基づいて、ローカルリクエスト表及びローカル予約履歴情報を更新する必要があり、これにより、次回のHELLOパケットの送信又は受信がスムーズになる。
【００５８】
そのうち、上述のように、該REQ部分が指示している、リクエストされた予約タイムスロットと、ローカルリクエスト表中の確認情報が同意である各エントリーが指示している、リクエストされた予約タイムスロットとが衝突しない場合、ローカルリクエスト表に、該REQ部分に対応する一つのエントリーを新しく追加し、そのうち、該新しく追加されたエントリーに対応する確認情報が同意である。また、さらに、該REQ部分が指示している、リクエストされた予約タイムスロットと、ローカル予約履歴情報が指示している、ローカルノードによりリクエストされた予約タイムスロットとが衝突するかどうかを判断してもよく、衝突する場合、ローカルノードによりリクエストされた予約タイムスロットが無効であると確認し、そして、これに基づいて、ローカル予約履歴情報を修正し、例えば、状態を指示するためのフラグを無効に変え、又は、タイムスロットインデックスを特定値に変え；衝突しない場合、ローカル予約履歴情報を不変に維持させる。
【００５９】
そのうち、上述にように、該REQ部分が指示している、リクエストされた予約タイムスロットと、ローカルリクエスト表中の確認情報が同意である各エントリーが指示している、リクエストされた予約タイムスロットとが衝突する場合、ローカルリクエスト表に、該REQ部分に対応する一つのエントリーを新しく追加し、そのうち、該新しく追加されたエントリーに対応する確認情報が反対である。
【００６０】
本実施例では、オプションで、ステップ902の前に、先に、該REQ部分を受信しているかどうかを確認してもよく、はいの場合、それを処理したことがあり、該REQ部分が古いものであることを示し、この時に、直ちに終了し；いいえの場合、それを処理したことがなく、該REQ部分が新しいものであることを示し、この時に、ステップ902を実行する。
【００６１】
本実施例でが、オプションで、ステップ902の前に、更に、先に、該REQ部分が有効であるかどうかを確認してもよく、例えば、該REQ部分が指示している、リクエストされた予約タイムスロットのインデックスが0より大きいかどうかを判断することにより、該REQ部分が有効であるかどうかを確認してもよく、0より大きい場合、該HELLOパケットの送信元によりリクエストされた予約タイムスロットが一つの有効なものであることを示し、ステップ902を実行し；0以下の場合、該HELLOパケットの送信元が一つの無効なタイムスロットをリクエストして予約したことを示し、又は、該HELLOパケットの送信元がタイムスロットを予約する気がなかったことを示し、この時に、ローカルリクエスト表に、該REQ部分に対応する情報エントリーを直接追加すればよく、そのうち、該新しく追加されたエントリーに対応する確認情報が特定値であってもよい。
【００６２】
図9に示す方法により、HELLOパケットの送信元によりリクエストされた予約タイムスロットに対して認証を行うことができ、そして、これに基づいて、ローカルリクエスト表及びローカル予約履歴情報を更新することができる。
【００６３】
本実施例の他の例では、受信したHELLOパケットが、HELLOパケットの送信元のタイムスロットリクエスト情報、即ち、REQ部分だけでなく、HELLOパケットの送信元の少なくとも一つの隣接ノードのタイムスロットリクエスト情報、即ち、RES部分をも含む場合、ステップ503は、図10に示す方法により実現されてもよく、図10に示すように、該方法は、次のステップを含む。
【００６４】
ステップ1001：受信したHELLOパケット中の、HELLOパケットの送信元の少なくとも一つの隣接ノードのタイムスロットリクエスト情報中の、各隣接ノードのタイムスロットリクエスト情報を遍歴し、即ち、HELLOパケット中のRES部分の各情報エントリーを遍歴（スキャン）する。
【００６５】
ステップ1002：前記情報エントリーのローカルソースIDがローカルノードIDである場合、前記情報エントリーの確認情報に基づいて、ローカルノードによりリクエストされた予約タイムスロットが有効であるかどうかを確定し、そして、これに基づいて、ローカルの予約履歴情報を更新する。
【００６６】
そのうち、該情報エントリーの確認情報が同意である場合、ローカルノードによりリクエストされた予約タイムスロットが有効であると確認し、この時に、ローカルの予約履歴情報を不変にさせてもよく；該情報エントリーの確認情報が反対である場合、ローカルノードによりリクエストされた予約タイムスロットが無効であると確認し、この時に、ローカルの予約履歴情報を更新してもよく、例えば、ローカルの予約履歴情報中の、リクエストされた予約タイムスロットの状態を無効に変更し、又は、ローカルの予約履歴情報中の、リクエストされた予約タイムスロットのインデックスを特定値に修正してもよい。
【００６７】
ステップ1003：前記情報エントリーのローカルソースIDがローカルノードIDでない場合、前記情報エントリーの確認情報に基づいて、ローカルリクエスト表を更新する。
【００６８】
そのうち、該情報エントリーの確認情報が反対である場合、これに基づいて、ローカルリクエスト表を直接更新し、例えば、ローカルリクエスト表に、該情報エントリーに対応する記録を新しく追加し、又は、ローカルリクエスト表中の、該情報エントリーに対応する記録を修正してもよい。該情報エントリーの確認情報が同意である場合、該情報エントリーのローカルソースIDがローカルノードの１hop隣接のIDであるかどうかを判断し、はいの場合、これに基づいて、ローカルリクエスト表を直接更新し、例えば、ローカルリクエスト表に、該情報エントリーに対応する記録を新しく追加し、又は、ローカルリクエスト表中の、該情報エントリーに対応する記録を修正し；いいえの場合、これに基づいて、ローカルリクエスト表中の、ローカルノードの1hop隣接の情報エントリーに対応する確認情報を更新し、例えば、両者が占用するタイムスロットが同じであり且つローカルリクエスト表中の対応する確認情報が同意である場合、ローカルリクエスト表中のそれ相応の記録を反対に変え、両者が占用するタイムスロットが同じであり且つローカルリクエスト表中の対応する確認情報が反対であり又は占用するタイムスロットが異なる場合、ローカルリクエスト表中のそれ相応の記録を不変にさせる。
【００６９】
ステップ1004：該HELLOパケットのREQ部分を遍歴し、該HELLOパケットの送信元によりリクエストされた予約タイムスロットに対して認証を行い、そして、これに基づいて、ローカルリクエスト表及びローカル予約履歴情報を更新する。
【００７０】
そのうち、該ステップは、図9に示す方法により実現されてもよいため、ここでは、詳しい説明を省略する。
【００７１】
この例では、図9に示す方法に類似し、オプションで、ステップ1002の前に、先に、該情報エントリーを受信したことがあるかどうかを確認してもよく、はいの場合、それを処理したことがあり、該情報エントリーが古いものであることを示し、この時に、RES部分の次の一つの情報エントリーを取得し；いいえの場合、それを処理したことがなく、該情報エントリーが新しいものであることを示し、この時に、ステップ1002を実行する。
【００７２】
図10に示す方法により、RES部分中の、ローカルソースIDがローカルノードのIDである情報エントリーに基づいて、ローカルノードによりリクエストされた予約タイムスロットが有効であるかどうかを確認し、そして、RES部分中の他の情報エントリーに基づいて、ローカルリクエスト表を更新してもよく、また、更に、REQ部分に基づいて、HELLOパケットの送信元によりリクエストされた予約タイムスロットに対して認証を行い、そして、これに基づいて、ローカルリクエスト表及びローカル予約履歴情報を更新してもよい。
【００７３】
図11は、本実施例における方法により、受信したHELLOパケットに対して処理を行うフローチャートであり、図11に示すように、該プロセスは、次のステップを含む。
【００７４】
ステップ1101：受信が開始し；
ステップ1102：RESの次の一つのエントリーを取得しているかどうかを判断し、はいの場合、ステップ1103を実行し、いいえの場合、ステップ1112を実行し；
そのうち、RESの各エントリーをスキャンした後にステップ1112を実行してHELLOパケットのREQ部分の処理を行う。
【００７５】
ステップ1103：該エントリーが新しいものか古いものであるかをチェックし、新しいものである場合、ステップ1104を実行し、古いものである場合、ステップ1102に戻り；
ステップ1104：該エントリーの送信ノードのアドレスがローカルアドレスであるかどうかを判断し、はいの場合、ステップ1105を実行し、いいえの場合、ステップ1108を実行し；
ステップ1105：該エントリーの確認情報が0であるかどうかを判断し、はいの場合、ステップ1106を実行し、いいえの場合、ステップ1107を実行し；
ステップ1106：ローカルノードによりリクエストされたタイムスロットが有効であると確認し、ステップ1111を実行し、ローカル予約履歴情報を不変にさせ；
ステップ1107：ローカルノードによりリクエストされたタイムスロットが無効であると確認し、ステップ1111を実行し、ローカル予約履歴情報を更新し；
ステップ1108：該エントリーの確認情報が0であるかどうかを判断し、はいの場合、ステップ1111を実行し、ローカルリクエスト表を更新し、いいえの場合、ステップ1109を実行し；
そのうち、上述のように、該エントリーをローカルリクエスト表に追加してもよい。
【００７６】
ステップ1109：該エントリーの送信ノードのアドレスがローカルの１hop隣接ノードのアドレスであるかどうかを判断し、はいの場合、ステップ1111を実行し、ローカルリクエスト表を更新し、いいえの場合、ステップ1110を実行し；
そのうち、上述のように、該エントリーをローカルリクエスト表に追加してもよい。
【００７７】
ステップ1110：ローカルの１hop隣接ノードの確認情報を更新し、そのうち、タイムスロットの比較により、ローカルの１hop隣接ノードの確認情報を更新するかどうかを確定してもよく；
ステップ1111：ローカルリクエスト表又はローカル予約履歴情報を更新し；
そのうち、判断結果が異なると、ローカルリクエスト表又はローカル予約履歴情報の更新内容も異なり、具体的には、上述のようであるため、ここでは詳しい説明を省略する。
【００７８】
ステップ1112：HELLOパケットのREQ部分を取得し；
ステップ1113：該エントリーが新しいものか古いものであるかをチェックし、新しいものであれば、ステップ1114を実行し、古いものであれば、終了し；
ステップ1114：該エントリーに対応するタイムスロットが0より大きいかどうかをチェックし、はいの場合、ステップ1115を実行し；いいえの場合、ステップ1119を実行し、ローカルリクエスト表を更新し；
そのうち、タイムスロットが0より大きい場合、該HELLOパケットの送信ノードにより一つの有効なタイムスロットがリクエストされたことを示し、この時に、継続してそれによりリクエストされたタイムスロットに対して後続の処理を行ってもよく；そうでない場合、該HELLOパケットの送信ノードが有効なタイムスロットをリクエストしていないことを示し、このような場合、ローカルリクエスト表を直接更新してもよく、例えば、該エントリー（即ち、該HELLOパケットのREQ部分）をローカルリクエスト表に添加してもよい。
【００７９】
ステップ1115：該エントリーがローカルリクエスト表と衝突するかどうかを判断し、はいの場合、ステップ1119を実行し、ローカルリクエスト表を更新し、いいえの場合、ステップ1116を実行する。
【００８０】
そのうち、ローカルリクエスト表と衝突する場合、該HELLOパケットのREQ部分がリクエストしたタイムスロットが該HELLOパケットの送信ノードに占用/予約されているので、該HELLOパケットのREQ部分がリクエストした予約タイムスロットに反対を付与し、そして、これに基づいて、ローカルリクエスト表を更新する。
【００８１】
そのうち、ローカルリクエスト表と衝突しない場合、該HELLOパケットの送信元が、そのリクエストした予約タイムスロットを使用できることを示し、この場合、該HELLOパケットのREQ部分がリクエストした予約タイムスロットに同意を付与し、そして、これに基づいて、ローカルリクエスト表を更新する。
【００８２】
ステップ1116：該エントリーが、ローカルノードによりリクエストされたタイムスロットと衝突するかどうかを判断し、はいの場合、ステップ1117を実行し、いいえの場合、ステップ1118を実行する。
【００８３】
そのうち、HELLOパケットの送信元によりリクエストされた予約タイムスロットが、ローカルノードによりリクエストされたタイムスロットと衝突する場合、ローカルがそのリクエストしたタイムスロットを使用できないことを示し、この場合、これに基づいて、ローカルの予約履歴情報を更新してもよく、これは、上述と同様であるため、ここでは詳しい説明を省略し；そうでない場合、ローカルがそのリクエストしたタイムスロットを使用することができる。
【００８４】
ステップ1117：ローカルノードによりリクエストされたタイムスロットが無効であると確定し、ステップ1119を実行し、ローカル予約履歴情報を更新し；
ステップ1118：ローカルノードによりリクエストされたタイムスロットが有効であると確定し、ステップ1119を実行し、ローカル予約履歴情報を不変にさせ；
ステップ1119：ローカルリクエスト表又はローカル予約履歴情報を更新する。
【００８５】
そのうち、判断結果が異なると、ローカルリクエスト表又はローカル予約履歴情報の更新内容も異なり、具体的には、上述と同様であるので、ここでは、詳しい説明を省略する。
【００８６】
ステップ1120：終了する。
【００８７】
本発明の実施例における方法により、ノードは、HELLOパケットタイマーが起動する時に、REQ部分（自分がリクエストしたタイムスロット情報）を含み、又は、REQ部分（自分がリクエストしたタイムスロット情報）及びRES部分（自分の隣接ノードがリクエストしたタイムスロット情報）を含むHELLOパケットを形成し、そして、該HELLOパケットをブロードキャストして送信し、該HELLOパケットを受信したノードに、これに基づいて、リクエストされた予約タイムスロットが有効かどうかを確認させ、及び/又は、ローカルリクエスト表を更新させ、及び/又は、HELLOパケットの送信元によりリクエストされた予約タイムスロットに対して認証を行わせ、これにより、タイムスロットの有効割り当てを有効に実現し、データ衝突を避けことができ、また、各種マルチホップネットワークにより良く適用し得る。
【００８８】
本発明の実施例は更に、マルチホップネットワーク中のノードを次の実施例2に記載のように提供する。該ノードが問題を解決する原理は、実施例1の方法に類似するため、その具体的な実施は、実施例1における方法の実施を参照することができるため、ここでは、同じ内容の記載を省略する。
【実施例２】
【００８９】
本発明の実施例は、マルチホップネットワーク中のノードを提供する。図12は、該ノードの構成図であり、図12に示すように、該ノードは、次のユニットを含む。
【００９０】
形成ユニット121：HELLOパケットを形成し、前記HELLOパケットは、ローカルノードのタイムスロットリクエスト情報を含み、又は、ローカルノードのタイムスロットリクエスト情報、及び、ローカルノードの少なくとも一つの隣接ノードのタイムスロットリクエスト情報を含む。
【００９１】
送信ユニット122：前記HELLOパケットを送信し、該HELLOパケットを受信したノードに、前記タイムスロットリクエスト情報に基づいて、前記ローカルノードに、リクエストした予約タイムスロットに対して認証を行わせる。
【００９２】
そのうち、前記ローカルのタイムスロットリクエスト情報は、ローカルノードのアドレス、ローカルノードが送信しようとするデータパケットの受信ノードのアドレス、及びローカルノードによりリクエストされた予約タイムスロットのインデックスを含み；前記隣接ノードのタイムスロットリクエスト情報は、隣接ノードのアドレス、前記隣接ノードが送信しようとするデータパケットの受信ノードのアドレス、前記隣接ノードによりリクエストされた予約タイムスロットのインデックス、及び前記隣接ノードによりリクエストされた予約タイムスロットの確認情報を含む。
【００９３】
一例では、前記形成ユニット121は、次のモジュールを含む。
【００９４】
第一取得モジュール1211：ルーティング表から、前記ローカルノードが送信しようとするデータパケットの受信ノードを選択し、前記ローカルノードが送信しようとするデータパケットの受信ノードのアドレスを取得する。
【００９５】
第二取得モジュール1212：前記ローカルノードが送信しようとするデータパケットのために予約タイムスロットを選択し、前記リクエストされた予約タイムスロットのインデックスを取得する。
【００９６】
形成モジュール1213：前記ローカルノードが送信しようとするデータパケットの受信ノードのアドレス、前記リクエストされた予約タイムスロットのインデックス、及びローカルノードのアドレスに基いいて、前記HELLOパケット中のローカルのタイムスロットリクエスト情報を形成する。
【００９７】
一例では、前記形成ユニット121はさらに次のモジュールを含む。
【００９８】
第三取得モジュール1214：所定策略に基づいて、ローカルリクエスト表から、少なくとも一つの隣接ノードの情報エントリーを前記少なくとも一つの隣接ノードのタイムスロットリクエスト情報として選択する。
【００９９】
前記形成モジュール1213は、前記少なくとも一つの隣接ノードのタイムスロットリクエスト情報に基づいて、前記HELLOパケット中の少なくとも一つの隣接ノードのタイムスロットリクエスト情報を形成する。
【０１００】
一例では、前記第二取得モジュール1212は具体的に、前記ローカルノードの前にリクエストした予約タイムスロットが有効である時に、ローカルノードの前にリクエストした予約タイムスロットを前記予約タイムスロットとし；又は、前記ローカルノードの前にリクエストした予約タイムスロットが無効である時に、予め構成されたタイムスロット集合から、未使用のタイムスロットを前記予約タイムスロットとしてランダムに選択し、又は、予め構成されたタイムスロット集合から、一つ目の未使用のタイムスロットを前記予約タイムスロットとして選択し、又は、予め構成されたタイムスロット集合から、最大の未使用のタイムスロットの間隔内の中間位置のタイムスロットを前記予約タイムスロットとして選択し、又は、予め構成されたタイムスロット集合から、タイムスロットインデックスが前記ローカルノードのアドレスの関数であるタイムスロットを前記予約タイムスロットとして選択し、又は、ローカルノードのホップ数に基づいて、該ホップ数に対応するタイムスロット集合から、未使用のタイムスロットを前記予約タイムスロットとして選択するために用いられる。
【０１０１】
一例では、前記ノードはさらに処理ユニット123を含み、それは、受信したHELLOパケットに基づいて、HELLOパケットの送信元によりリクエストされた予約タイムスロットに対して認証を行い、及び/又は、ローカルノードの予約タイムスロットが有効であるかどうかを確定し、及び/又は、ローカルリクエスト表を更新し、及び/又は、ローカル予約履歴情報を更新するために用いられる。
【０１０２】
一例では、前記処理ユニット123は、次のモジュールを含む。
【０１０３】
第一遍歴モジュール1231：前記HELLOパケットのREQ部分、即ち、前記HELLOパケットの送信元のタイムスロットリクエスト情報を遍歴する。
【０１０４】
第一確定モジュール1232：前記HELLOパケットの送信元のタイムスロットリクエスト情報と、ローカルリクエスト表中の確認情報が同意である情報エントリーとを比較することにより、前記HELLOパケットの送信元によりリクエストされた予約タイムスロットに対して認証を行い、そして、これに基づいて、ローカルリクエスト表又はローカル予約履歴情報を更新する。
【０１０５】
そのうち、前記HELLOパケットの送信元のタイムスロットリクエスト情報が指示している、リクエストされた予約タイムスロットと、ローカルリクエスト表中の確認情報が同意である情報エントリーが指示している、リクエストされた予約タイムスロットとが衝突する場合、前記HELLOパケットの送信元によりリクエストされた予約タイムスロットに反対を与え、そして、これに基づいて、ローカルリクエスト表を更新する。
【０１０６】
そのうち、前記HELLOパケットの送信元のタイムスロットリクエスト情報が指示している、リクエストされた予約タイムスロットと、ローカルリクエスト表中の確認情報が同意である情報エントリーが指示している、リクエストされた予約タイムスロットとが衝突ししない場合、前記HELLOパケットの送信元によりリクエストされた予約タイムスロットに同意を与え、そして、これに基づいて、ローカルリクエスト表を更新する。そのうち、さらに、前記HELLOパケットの送信元のタイムスロットリクエスト情報が指示している、リクエストされた予約タイムスロットと、ローカルノードによりリクエストされた予約タイムスロットとが衝突するかどうかを判断してもよく、衝突する場合、ローカルにリクエストされた予約タイムスロットが無効であると確認し、そして、これに基づいて、ローカル予約履歴情報を更新し；衝突しない場合、ローカルにリクエストされた予約タイムスロットが有効であると確認し、そして、これに基づいて、ローカル予約履歴情報を不変にさせる。
【０１０７】
一例では、前記確定ユニット123はさらに次のモジュールを含む。
【０１０８】
第二遍歴モジュール1233：前記HELLOパケットのRES部分の各情報エントリー、即ち、HELLOパケットの送信元の各隣接ノードのタイムスロットリクエスト情報を遍歴する。
【０１０９】
第二確定モジュール1234：前記情報エントリー中のローカルソースIDがローカルノードIDである情報エントリーに基づいて、ローカルノードによりリクエストされた予約タイムスロットが有効であるかどうかを確定し；そして、前記情報エントリー中のローカルソースIDがローカルノードIDでない情報エントリーに基づいて、ローカルリクエスト表を更新する。
【０１１０】
そのうち、ローカルソースIDがローカルノードIDである情報エントリーの確認情報が同意である場合、ローカルノードによりリクエストされた予約タイムスロットが有効であると確定し、そうでない場合、ローカルノードによりリクエストされた予約タイムスロットが無効であると確定し、そして、これに基づいて、ローカルの予約履歴情報を更新する。
【０１１１】
そのうち、ローカルソースIDがローカルノードIDでない情報エントリーの確認情報が同意である場合、該情報エントリーのローカルソースIDがローカルノードの１hop隣接ノードのIDである時に、これに基づいて、ローカルリクエスト表を更新し、該情報エントリーのローカルソースIDがローカルノードの１hop隣接ノードでないIDである時に、ローカルリクエスト表中の１hop隣接ノードの情報エントリーを更新し；ローカルソースIDがローカルノードIDでない情報エントリーの確認情報が反対である場合、これに基づいて、ローカルリクエスト表を更新する。
【０１１２】
本発明の実施例におけるノードにより、HELLOパケットタイマーが起動する時にREQ部分（自分がリクエストしたタイムスロット情報）を含み、又は、REQ部分（自分がリクエストしたタイムスロット情報）及びRES部分（自分の隣接ノードがリクエストしたタイムスロット情報）を含むHELLOパケットを形成し、そして、ブロードキャストして送信し、これにより、該HELLOパケットを受信したノードは、これに基づいて、リクエストされた予約タイムスロットが有効であるかどうかを確定し、及び/又は、ローカルリクエスト表を更新し、及び/又は、HELLOパケットのタイマーが起動する時にHELLOパケットを形成し、これにより、タイムスロットの割り当てを有効に実現し、データ衝突を避けることができ、各種マルチホップネットワークにより良く適用し得る。
【０１１３】
本発明の上述のノード（装置）及び方法は、ハードウェアにより実現されてもよく、ハードウェアとソフトウェアとの組み合わせにより実現されてもよい。また、本発明は、このようなコンピュータ可読なプログラムにも関し、即ち、該プログラムは、ロジック部により実行されている時に、該ロジック部に、上述の装置又は構成部品を実現させることができ、又は、該ロジック部に、上述の各種方法又はステップを実現させることができる。本発明は、さらに、上述のプログラムを記録している記憶媒体、例えば、ハードディスク、磁気ディスク、光ディスク、DVD、flashメモリなどにも関する。
【０１１４】
また、上述の各実施例を含む実施形態に関し、更に以下の付記を開示する。
【０１１５】
（付記1）
タイムスロット割り当て方法であって、
ローカルノードのタイムスロットリクエスト情報を含み、又は、ローカルノードのタイムスロットリクエスト情報及びローカルノードの少なくとも一つの隣接ノードのタイムスロットリクエスト情報を含むHELLOパケットを形成し；及び
前記HELLOパケットを送信し、前記HELLOパケットを受信したノードに、前記タイムスロットリクエスト情報に基づいて、前記ローカルノードによりリクエストされた予約タイムスロットに対して認証を行わせることを含み、
そのうち、前記ローカルノードのタイムスロットリクエスト情報は、ローカルノードのアドレス、ローカルノードが送信しようとするデータパケットの受信ノードのアドレス、及びローカルノードによりリクエストされた予約タイムスロットのインデックスを含み；前記隣接ノードのタイムスロットリクエスト情報は、隣接ノードのアドレス、前記隣接ノードが送信しようとするデータパケットの受信ノードのアドレス、前記隣接ノードによりリクエストされた予約タイムスロットのインデックス、及び前記隣接ノードによりリクエストされた予約タイムスロットの確認情報を含む、方法。
【０１１６】
（付記2）
付記1に記載の方法であって、
HELLOパケットを形成するステップは、
ルーティング表から、前記ローカルノードが送信しようとするデータパケットの受信ノードを選択し、前記ローカルノードが送信しようとするデータパケットの受信ノードのアドレスを取得し；
前記ローカルノードが送信しようとするデータパケットのために予約タイムスロットを選択し、前記ローカルノードによりリクエストされた予約タイムスロットのインデックスを取得し；及び
前記ローカルノードが送信しようとするデータパケットの受信ノードのアドレス、前記ローカルノードによりリクエストされた予約タイムスロットのインデックス、及びローカルノードのアドレスに基づいて、前記ローカルノードのタイムスロットリクエスト情報を取得することを含む、方法。
【０１１７】
（付記3）
付記2に記載の方法であって、
HELLOパケットを形成するステップは、更に、
所定策略に基づいて、ローカルリクエスト表から、少なくとも一つの隣接ノードの情報エントリーを前記少なくとも一つの隣接ノードのタイムスロットリクエスト情報として選択することを含む、方法。
【０１１８】
（付記4）
付記2に記載の方法であって、
前記ローカルノードが送信しようとするデータパケットのために予約タイムスロットを選択するステップは、
ローカル予約履歴情報に基づいて、ローカルノードの前にリクエストした予約タイムスロットが有効であるかどうかを確定し；及び
前記ローカルノードの前にリクエストした予約タイムスロットが有効である時に、ローカルノードの前にリクエストした予約タイムスロットを前記予約タイムスロットとし；
前記ローカルノードの前にリクエストした予約タイムスロットが無効である時に、予め構成されたタイムスロット集合から、未使用のタイムスロットを前記予約タイムスロットとしてランダムに選択し、又は、予め構成されたタイムスロット集合から、一つ目の未使用のタイムスロットを前記予約タイムスロットとして選択し、又は、予め構成されたタイムスロット集合から、最大の未使用のタイムスロットの間隔内の中間位置のタイムスロットを前記予約タイムスロットとして選択し、又は、予め構成されたタイムスロット集合から、タイムスロットインデックスが前記ローカルノードのアドレスの関数であるタイムスロットを前記予約タイムスロットとして選択し、又は、ローカルノードのホップ数に基づいて、該ホップ数に対応するタイムスロット集合から、未使用のタイムスロットを前記予約タイムスロットとして選択することを含む、方法。
【０１１９】
（付記5）
付記4に記載の方法であって、
前記予め構成されたタイムスロット集合は、予め設定されたHELLOパケットの間隔のうち所定フレームのデータ部分であり、又は、予め設定されたHELLOパケットの間隔のうち全てのフレームのデータ部分である、方法。
【０１２０】
（付記6）
付記1に記載の方法であって、更に、
受信したHELLOパケットに基づいて、HELLOパケットの送信元にリクエストされた予約タイムスロットに対して認証を行い、及び/又は、ローカルノードによりリクエストされた予約タイムスロットが有効であるかどうかを確定し、及び/又は、ローカルリクエスト表を更新し、及び/又は、ローカル予約履歴情報を更新することを含み、
そのうち、受信したHELLOパケットは、HELLOパケットの送信元のタイムスロットリクエスト情報を含み、又は、受信したHELLOパケットは、HELLOパケットの送信元のタイムスロットリクエスト情報及びHELLOパケットの送信元の少なくとも一つの隣接ノードのタイムスロットリクエスト情報を含む、方法。
【０１２１】
（付記7）
付記6に記載の方法であって、
受信したHELLOパケットがHELLOパケットの送信元のタイムスロットリクエスト情報のみを含む場合、該HELLOパケットを受信した後に、前記方法は、
受信したHELLOパケット中のHELLOパケットの送信元のタイムスロットリクエスト情報を遍歴し；
受信したHELLOパケットの送信元のタイムスロットリクエスト情報と、ローカルリクエスト表中の確認情報が同意である情報エントリーとを比較し；
受信したHELLOパケットの送信元のタイムスロットリクエスト情報が指示している、リクエストされた予約タイムスロットと、ローカルリクエスト表中の確認情報が同意である情報エントリーが指示している、リクエストされた予約タイムスロットとが衝突する場合、受信したHELLOパケットの送信元によりリクエストされた予約タイムスロットに反対を付与し、そして、ローカルリクエスト表に、該受信したHELLOパケットの送信元のタイムスロットリクエスト情報に対応する情報エントリーを追加し；及び
受信したHELLOパケットの送信元のタイムスロットリクエスト情報が指示している、リクエストされた予約タイムスロットと、ローカルリクエスト表中の確認情報が同意である情報エントリーが指示している、リクエストされた予約タイムスロットとが衝突しない場合、受信したHELLOパケットの送信元によりリクエストされた予約タイムスロットに同意を付与し、そして、ローカルリクエスト表に、該受信したHELLOパケットの送信元のタイムスロットリクエスト情報に対応する情報エントリーを追加することを含む、方法。
【０１２２】
（付記8）
付記7に記載の方法であって、
受信したHELLOパケットの送信元のタイムスロットリクエスト情報が指示している、リクエストされた予約タイムスロットと、ローカルリクエスト表中の確認情報が同意である情報エントリーが指示している、リクエストされた予約タイムスロットとが衝突しない場合、前記方法は、更に、
受信したHELLOパケットの送信元のタイムスロットリクエスト情報が指示している、リクエストされた予約タイムスロットと、ローカルノードによりリクエストされた予約タイムスロット是とが衝突するかどうかを判断し；
衝突する場合、ローカルノードによりリクエストされた予約タイムスロットが無効であると確定し、そして、ローカル予約履歴情報を更新し；及び
衝突しない場合、ローカルノードによりリクエストされた予約タイムスロットが有効であると確定し、ローカル予約履歴情報を不変に維持させることを含む、方法。
【０１２３】
（付記9）
付記7に記載の方法であって、
受信したHELLOパケットが更に、HELLOパケットの送信元の少なくとも一つの隣接ノードのタイムスロットリクエスト情報を含む場合、受信したHELLOパケットの送信元のタイムスロットリクエスト情報を遍歴する前に、前記方法は、更に、
受信したHELLOパケット中の送信元の少なくとも一つの隣接ノードのタイムスロットリクエスト情報中の各タイムスロットリクエスト情報を遍歴し；
該タイムスロットリクエスト情報が指示しているローカルソースIDがローカルノードのIDである場合、該タイムスロットリクエスト情報が指示している確認情報に基づいて、ローカルノードによりリクエストされた予約タイムスロットが有効であるかどうかを確認し；及び
該タイムスロットリクエスト情報が指示しているローカルソースIDがローカルノードのIDでない場合、該タイムスロットリクエスト情報が指示している確認情報に基づいてローカルリクエスト表を更新することを含む、方法。
【０１２４】
（付記10）
付記9に記載の方法であって、
該タイムスロットリクエスト情報が指示している確認情報に基づいて、ローカルノードによりリクエストされた予約タイムスロットが有効であるかどうかを確認するステップは、
該タイムスロットリクエスト情報が指示している確認情報が同意である場合、ローカルノードによりリクエストされた予約タイムスロットが有効であると確認し、そして、これに基づいてローカル予約履歴情報を更新し；及び
該タイムスロットリクエスト情報が指示している確認情報が反対である場合、ローカルノードによりリクエストされた予約タイムスロットが無効であると確認することを含む、方法。
【０１２５】
（付記11）
付記9に記載の方法であって、
該タイムスロットリクエスト情報が指示している確認情報に基づいてローカルリクエスト表を更新するステップは、
該タイムスロットリクエスト情報が指示している確認情報が反対である場合、これに基づいて、ローカルリクエスト表を直接更新し；
該タイムスロットリクエスト情報が指示している確認情報が同意である場合、該タイムスロットリクエスト情報が指示しているローカルソースIDがローカルノードの１hop隣接ノードのIDであるかどうかを判断し、はいの場合、これに基づいて、ローカルリクエスト表を直接更新し、いいえの場合、これに基づいて、ローカルリクエスト表中の１hop隣接ノードの情報エントリーを更新することを含む、方法。
【０１２６】
（付記12）
付記11に記載の方法であって、
ローカルリクエスト表中の１hop隣接ノードの情報エントリーを更新するステップは、
ローカルリクエスト表中の１hop隣接ノードの情報エントリーが指示しているタイムスロットインデックスと、該タイムスロットリクエスト情報が指示しているタイムスロットインデックスとが同じである場合、ローカルリクエスト表中の１hop隣接ノードの情報エントリーが指示している確認情報を無効に修正し；及び
ローカルリクエスト表中の１hop隣接ノードの情報エントリーが指示しているタイムスロットインデックスと、該タイムスロットリクエスト情報が指示しているタイムスロットインデックスとが異なる場合、ローカルリクエスト表中の１hop隣接ノードの情報エントリーを不変に維持させることを含む、方法。
【０１２７】
以上、本発明の好ましい実施形態を説明したが、本発明はこの実施形態に限定されず、本発明の趣旨を離脱しない限り、本発明に対するあらゆる変更は本発明の技術的範囲に属する。
【図１】
2015056895.tif 000006
【図２】
2015056895.tif 000007
【図３】
2015056895.tif 000008
【図４】
2015056895.tif 000009
【図５】
2015056895.tif 000010
【図６】
2015056895.tif 000011
【図７】
2015056895.tif 000012
【図８】
2015056895.tif 000013
【図９】
2015056895.tif 000014
【図１０】
2015056895.tif 000015
【図１１】
2015056895.tif 000016
【図１２】
2015056895.tif 000017