(57)【特許請求の範囲】
【請求項１】
身体領域ネットワーク（BAN）においてグローバル・ビーコンの送信をスケジューリングする方法であって、前記BANはマスター・ノードおよびスレーブ・ノードを含み、前記マスター・ノードは木トポロジーに構成されており、当該方法は：
上り期間の間に木の葉ノードからルート・ノードへと上りグローバル・ビーコン（AGB）を伝搬させる段階であって、AGBは少なくとも時間ラウンドの期間中の時間スロットの予約を含む、段階と；
ルート・ノードによってAGBを処理して時間スロット占有情報を判別する段階と；
下り期間の間にルート・ノードから葉ノードへと下りグローバル・ビーコン（DGB）を伝搬させる段階であって、DGBは少なくとも時間ラウンドの期間中の時間スロットの予約を含む、段階と；
ルート・ノード以外のマスター・ノードによってDGBを処理してDGBに含まれている少なくともスロット占有情報を更新する段階とを含む、
方法。
【請求項２】
各マスター・ノードを、該マスター・ノードがブートするときに初期化する段階をさらに含む、請求項１記載の方法。
【請求項３】
各マスター・ノードを初期化する段階がさらに：
単一の時間ラウンドの期間中、ビーコンを求めてスキャンする段階と；
前記時間ラウンドの期間中にグローバル・ビーコンが受信されなかった場合に前記マスター・ノードをルート・ノードとして宣言する段階とを含む、
請求項２記載の方法。
【請求項４】
前記ラウンド時間の期間中にグローバル・ビーコンが受信された場合、前記マスター・ノードをビーコン・グループに加える段階と；
前記マスター・ノードのRSTを前記ビーコン・グループのRSTに同期させる段階と；
加入スロットの一つにおいて、前記マスター・ノードについてのAGBの送信をスケジュールする段階とをさらに含む、
請求項３記載の方法。
【請求項５】
前記マスター・ノードがルート・ノードであると宣言される場合、前記下り期間のタスクを実行するよう前記マスター・ノードを設定する段階と；
前記マスター・ノードがルート・ノードであると宣言されない場合、前記上り期間のタスクを実行するよう前記マスター・ノードを設定する段階とをさらに含む、
請求項４記載の方法。
【請求項６】
前記上り期間の間に、ルート・ノードでない各マスター・ノードが：
子ノードおよびオーファン・ノードからの情報を含むAGBを、そのマスター・ノードのために予約されている時間スロットにおいて送る段階と；
そのマスター・ノードの子ノードの時間スロット、加入スロットまたはそのマスター・ノードのために予約されている時間スロットより前でかつ前記加入時間スロットより後の時間スロットを傾聴する段階とを実行する、
請求項１記載の方法。
【請求項７】
受信されたAGBに含まれる情報を記憶する段階をさらに含む、請求項６記載の方法。
【請求項８】
請求項１記載の方法であって、ルート・ノードによってAGBを処理する段階がさらに：
時間スロット占有情報に基づいて未占有時間スロットを占有させる段階であって、
未占有スロットにタグ付けし、
占有スロットの所有者に、そのスロットを動かして空スロットを埋めるよう指示し、
迫っている動きについて親および子に通知することを含む、段階と；
木メンテナンス動作を実行して更新された木情報を生成する段階と；
前記木情報および前記スロット占有情報を含むようDGBを構築する段階とを含む、
方法。
【請求項９】
請求項８記載の方法であって、木メンテナンス動作を実行する段階がさらに：
ビーコン・グループが少なくとも一つのオーファン・ノードを含む場合、該ビーコン・グループ内の各オーファン・ノードに親ノードを割り当てる段階と；
前記ビーコン・グループに加わった新しいノードに親ノードを割り当てる段階と；
マスター・ノードが前記BANを礼儀正しく抜けたときに：
前記マスター・ノードを前記木から除去し、
前記ビーコン・グループを更新し、
抜けたマスター・ノードに接続された親ノードおよび子ノードの状態を更新することを実行する段階と；
マスター・ノードが前記BANを無断で抜けたときに：
前記マスター・ノードを前記木から除去し、
前記ビーコン・グループを更新し、
抜けたノードに接続された親ノードおよび子ノードの状態を更新することを実行する段階とを含む、
方法。
【請求項１０】
請求項１記載の方法であって、DGBを伝搬させる段階がさらに：
ルート・ノードによって、DGBを、ルート・ノードのために予約された時間スロットにおいて送信する段階と；
前記DGBを受信する各親ノードによってその子ノードに、前記DGBのそのままのコピーを送信する段階と；
受信されたDGBまたは該DGBのそのままのコピーに含まれている情報を保存する段階とを含む、
方法。
【請求項１１】
前記DGBのそのままのコピーが、親マスター・ノードとその子ノードとの間でクロックを同期させるために利用される、請求項１０記載の方法。
【請求項１２】
ルート以外のノードによってDGBを処理する段階がさらに：
前記DGBのそのままのコピーを受信する段階と；
前記DGBに含まれている情報に基づいて木情報を更新する段階とを含む、
請求項１０記載の方法。
【請求項１３】
請求項１２記載の方法であって、さらに：
ルートによって送られたDGBがルート・ノード以外のノードにおいて受信されないとき、現在のルート・ノードの時間スロットの隣の時間スロットを占有するノードを新しいルート・ノードであると宣言する段階と；
ルート・ノードによって送られたDGBがルート・ノード以外のノードにおいて受信されないとき、スロット再順序付けをトリガーする段階とを含み、該スロット再順序付けは：
加入時間スロットの一つをランダムに選択し、
上り期間の間に、選択されたスロットにおいてAGB送信をスケジュールすることを含む、
方法。
【請求項１４】
コンピュータ実行可能コードが記憶されたコンピュータ可読媒体であって、前記コンピュータ実行可能コードは、実行されたときに、プロセッサに、身体領域ネットワーク（BAN）においてグローバル・ビーコンの送信をスケジューリングするプロセスであって、前記BANはマスター・ノードおよびスレーブ・ノードを含み、前記マスター・ノードは木トポロジーに構成されており、前記プロセスは：
上り期間の間に木の葉ノードからルート・ノードへと上りグローバル・ビーコン（AGB）を伝搬させる段階であって、AGBは少なくとも時間ラウンドの期間中の時間スロットの予約を含む、段階と；
ルート・ノードによってAGBを処理して時間スロット占有情報を判別する段階と；
下り期間の間にルート・ノードから葉ノードへと下りグローバル・ビーコン（DGB）を伝搬させる段階であって、DGBは少なくとも時間ラウンドの期間中の時間スロットの予約を含む、段階と；
ルート・ノード以外のマスター・ノードによってDGBを処理してDGBに含まれている少なくともスロット占有情報を更新する段階とを含む、
プロセスを実行させる、コンピュータ可読媒体。
【請求項１５】
各マスター・ノードを、該マスター・ノードがブートするときに初期化することをさらに含む、請求項１４記載のコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、2008年8月11日に出願された米国仮出願第61/087,746号の利益を主張する。
【０００２】
本発明は概括的には、身体領域ネットワーク（BAN:  body  area  network）において使用される媒体アクセス制御（MAC:  medium  access  control）プロトコルに関する。
【背景技術】
【０００３】
身体領域ネットワーク（BAN）は、主として、生命徴候〔バイタルサイン〕（vital  signs）の恒久的な監視およびログ記録のために設計されている。図１に示される例示的なBANは、典型的には身につけることができるまたは人体中に埋め込まれることのできるセンサーである複数のノード１２０を含む。ノード１２０は、生命に関する身体パラメータおよび動きをモニタリングし、無線媒体を通じて互いに通信する。ノード１２０は、身体からのデータを一つまたは複数のノード１３０に送信できる。ノード１３０から、そのデータはリアルタイムで病院、診療所または他所に、ローカル・エリア・ネットワーク（LAN）、広域ネットワーク（WAN）、セルラー・ネットワークなどを通じて転送されることができる。
【０００４】
BANの設計のための要求は、ノード１２０および１３０のエネルギー効率、スケーラビリティ、統合（integration）、干渉緩和、共存（coexistence）、高いサービス品質（QoS:  quality  of  service）およびセキュリティを含む。効率的なエネルギー消費は、受信者ノード（すなわちデータを受信するノード）を傾聴状態とスリープ状態との間で最適にデューティー・サイクリング〔稼働切り換え〕することによって達成できる。スリープ状態では、ノードのトランシーバはオフにされ、それによりエネルギーが節約される。デューティー・サイクリング（duty  cycling）は、アイドルな傾聴（listening）、傍受（overhearing）、衝突および制御オーバーヘッドを最小限にするねらいで、MACプロトコルによって実行される。
【０００５】
関連技術では、短距離無線ネットワークのためのいくつかのMACプロトコルが開示されている。たとえば、IEEE802規格委員会は、無線式のローカル・エリア・ネットワークおよびパーソナル・エリア・ネットワークのための一連の規格を開発した。無線ローカル・エリア・ネットワーク（WLAN:  wireless  local  area  network）用に設計されたIEEE802.11規格および無線パーソナル・エリア・ネットワーク（WPAN:  wireless  personal  area  network）用に設計されたIEEE802.15.4規格などである。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
BANは、生命に重要な医療アプリケーションのために使われることが意図される。したがって、信頼性、故障耐性〔フォールト・トレランス〕およびQoSが、エネルギー効率のほかに、根本的な要件となる。同じBANまたは複数のBAN内のノードは、体をひねったり、向きを変えたり、歩いたり、走ったりするためにレンジ内にはいったり出たりして動くことがありうる。よって、根本的な要件を達成するために、BANは頻繁なトポロジーおよび密度変化について敏捷であるべきである。WLANおよびWPANについて提案されたMACプロトコルはこれらの問題に効果的に対処するものではなく、BANのためには不適となっている。
【０００７】
具体的には、上述した無線ネットワークとは対照的に、BANはきわめて局在化されたネットワークである。典型的にはBANノードの送信レンジは3メートルである。身体上の任意の二つのノードの間の距離は3メートルに満たないという事実を考えれば、身体上の大半のノードは、互いの直接の通信レンジ内にある。しかしながら、場合によっては、ノードは、身体の陰のため、互いから隠されることがある。たとえば、身体の正面にあるノードは、身体の背面にある別のノードからは、重度の経路損失のため、到達可能でないことがある。よって、身体上の任意の二つのノードの間の接続性を提供するためには、マルチホップ通信が必要とされる。
【０００８】
身体上のノードの近接性のため、時分割多重アクセス方式が、メッセージ衝突を回避し、信頼性を改善するための好ましい方法である。この方式では、チャネル・アクセス時間は、固定された反復される継続時間の時間ラウンドに分割される。よって、時間ラウンドは、反復される固定された継続時間であり、該時間ラウンドの間にノードは媒体にアクセスできる。ネットワーク中のすべてのノードは、グローバル・ビーコン・メッセージを援用して、ラウンド当たり一回、自分のクロックを同期させる。定期的なクロック同期は、クロック・ドリフトを克服するために必要である。ラウンド時間はさらに、固定された継続時間の時間スロットに分割される。時間スロットは、媒体リザーブ〔予約〕の基本単位としてはたらく。ノードは時間スロットをリザーブし、その時間スロットの間は媒体にアクセスする排他的な権利をもつ。競合のない時間スロット・リザーブを可能にするために、時間スロット要求および割り当ては、ネットワーク中のすべてのノードに知られている必要がある。
【課題を解決するための手段】
【０００９】
本発明のある好ましい実施形態では、グローバル・ビーコンが、リザーブ要求を交換するため、すなわちノードが媒体にアクセスできる時間スロットを予約するためにも利用される。現在のラウンドのグローバル・ビーコン期間の間に、すべてのノードが次のラウンドのためのリザーブ要求を交換する。現在のラウンドの間に受信される要求に基づいて、次のラウンドについての競合のない時間スロット割り当てが導出される。グローバル・ビーコンの送信の適正なシーケンスが、リザーブ要求がグローバルに伝搬されることを保証するために決定的に重要である。たとえば、図２に示されるように、三つのノード２００−Ｘ、２００−Ｙおよび２００−Ｚが線形トポロジーで配列される。ノード２００−Ｘおよび２００−Ｚは互いからは隠されているが、２００−Ｙからの送信レンジ内にある。
【００１０】
このトポロジーにおいて、ノード２００−Ｘが第一のグローバル・ビーコンを送信し、続いてノード２００−Ｙがグローバル・ビーコンを送信し、それにノード２００−Ｚのグローバル・ビーコンが続く。各グローバル・ビーコンは、当該ノードが現在のラウンドの間に直接的または間接的に受信したリザーブ要求を担持する。ノードは、近隣ノードのグローバル・ビーコンを、そのリザーブ要求を知るために傾聴する。この場合、ノード２００−Ｘによって送られるグローバル・ビーコンはノード２００−Ｙビーコンに先行するので、ノード２００−Ｙは次のラウンドについてのノード２００−Ｘのリザーブ要求について知ることができる。したがって、ノード２００−Ｙのグローバル・ビーコンは、ノード２００−Ｘのリザーブ要求をも担持する。同様に、ノード２００−Ｚによって送られるグローバル・ビーコンはノード２００−Ｘおよびノード２００−Ｙのリザーブ要求を担持する。このグローバル・ビーコン・シーケンスの終わりには、ノード２００−Ｙおよび２００−Ｚは3個すべてのノードのリザーブ要求を知ることになる。しかしながら、ノード２００−Ｘはノード２００−Ｚからのリザーブ要求は受信しない。もう一つの例として、ノード２００−Ｙが第一のグローバル・ビーコンを送信し、それにノード２００−Ｚが続き、それにノード２００−Ｘが続くとする。この場合は、ノード２００−Ｘおよび２００−Ｚは互いのリザーブ要求を受信しない。
【００１１】
図２に示されるトポロジーについて、グローバル・ビーコンの適正なシーケンシング〔序列化〕が必要となろう。たとえば、ノード２００−Ｘが第一のグローバル・ビーコンを送信し、ノード２００−Ｚのグローバル・ビーコンがそれに続く。すると、ノード２００−Ｙは次のラウンドについてのノード２００−Ｘおよび２００−Ｚのリザーブ要求について、それらのグローバル・ビーコンを傾聴することによって、知る。この場合、ノード２００−Ｙは、ノード２００−Ｘおよびノード２００−Ｚのリザーブ要求に加えて、自分のリザーブ要求をそのグローバル・ビーコン中に埋め込み、最後のグローバル・ビーコンを送信する。この最後のグローバル・ビーコンにより、各ノードは、すべてのノードからのリザーブ要求を知ることができる。
【００１２】
上記の例は、リザーブ要求をグローバルに伝搬させるためには、グローバル・ビーコンのシーケンシングが任意に実行されることはできないことを明確に実証している。したがって、リザーブ要求を効率的に伝搬させるために、グローバル・ビーコンの送信をスケジューリングする方法を提供することが望ましい。
【００１３】
本発明のある種の実施形態は、身体領域ネットワーク（BAN）においてグローバル・ビーコンの送信をスケジューリングする方法を含む。BANはマスター・ノードおよびスレーブ・ノードを含む。ここで、マスター・ノードは木〔ツリー〕トポロジーに構成されている。本方法は、上り期間（ascending  period）の間に木の葉〔リーフ〕ノードからルート・ノードへと上りグローバル・ビーコン（AGB:  ascending  global  beacon）を伝搬させる段階であって、AGBは少なくとも時間ラウンドの期間中の時間スロットの予約を含む、段階と；ルート・ノードによってAGBを処理して時間スロット占有情報を判別する段階と；下り期間（descending  period）の間にルート・ノードから葉ノードへと下りグローバル・ビーコン（DGB:  descending  global  beacon）を伝搬させる段階であって、DGBは少なくとも時間ラウンドの期間中の時間スロットの予約を含む、段階と；ルート・ノード以外のマスター・ノードによってDGBを処理してDGBに含まれている少なくともスロット占有情報を更新する段階とを含む。
【００１４】
発明と見なされる主題は、付属の請求項において具体的に特定され、明確に記載される。本発明の以上のおよびその他の特徴および利点は、付属の図面とともに参照される以下の詳細な記述から明白となるであろう。
【図面の簡単な説明】
【００１５】
【図１】身体領域無線ネットワークの概略図である。
【図２】グローバル・ビーコンをスケジューリングするための任意技法を記述する身体領域ネットワークの線形トポロジーを示す図である。
【図３】Ａは上り期間中の木トポロジーにおける情報伝搬の方向を示す図であり、Ｂは下り期間中の木トポロジーにおける情報伝搬の方向を示す図である。
【図３−２】Ｃ、Ｄ、Ｅは、時間ラウンド、ビーコン・グループ、加入窓ならびに上り期間および下り期間の間の時間スロット占有を示す図であり、Ｆはノードが木を離れる際の更新された木トポロジーを示す図である。
【図４】グローバル・ビーコンの送信をスケジューリングする方法を記述する、限定しない例示的な図である。
【図５】本発明のある実施形態に基づいて実行される、初期化段階の実行を記述するフローチャートである。
【図６】本発明のある実施形態に基づいて実装される、上り期間の間のマスター・ノードの動作を記述するフローチャートである。
【図７】本発明のある実施形態に基づいて実装される、上りグローバル・ビーコンの処理を記述する例示的なフローチャートである。
【図８】本発明のある実施形態に基づいて実装される、下り期間の間の下りグローバル・ビーコンの伝搬を記述するフローチャートである。
【図９】本発明のある実施形態に基づいて実装される、下りグローバル・ビーコンの処理を記述する例示的なフローチャートである。
【図１０】ルート・ノードが死ぬときに実行されるプロセスの例を示す図である。
【発明を実施するための形態】
【００１６】
本発明によって開示される実施形態が、本稿の革新的な教示の数多くの有利な使用の例でしかないことを注意しておくことは重要である。一般に、本願の明細書においてなされる陳述は、必ずしもさまざまな特許請求される発明のいずれかを限定するものではない。さらに、いくつかの陳述は、いくつかの発明的な特徴に当てはまるが他の発明的な特徴には当てはまらないこともある。一般に、特に示されるのでない限り、一般性を失うことなく、単数形の要素は複数であってもよく、複数形の要素は単数であってもよい。図面において、いくつかの図面を通じて、同様の参照符号は同様の部分を指す。
【００１７】
本発明のある実施形態は、少なくとも身体領域ネットワーク（BAN）において同期、媒体予約、QoSおよび故障耐性〔フォールト・トレランス〕を可能にするために本質的である、グローバル・ビーコン・スケジューリングのための方法を提供する。本方法は、BANのレイテンシ要求およびトラフィック条件を達成するために適応されることができ、それによりQoSを損なうことなく電力を節約する、動的かつスケーラブルなデューティー・サイクリングを可能にする。本発明の原理によれば、グローバル・ビーコン・スケジューリング方法は、身体領域ネットワーク（BAN）においてマスター・ノードの（論理的な）木トポロジーを構築および維持する。木トポロジーにおいて、ノードは親‐子関係をもつ。ここで、ルート・ノードは親をもたず、他のすべてのノードはちょうど一つの親をもつ。ノードは複数の子をもっていてもよい。子を一つも持たないノードは葉ノードである。
【００１８】
本発明のある実施形態によれば、時間ラウンド３１０（図３Ｃに示される）内のあらかじめ定義された時間スロットがグローバル・ビーコン期間（GBP:  global  beacon  period）３２０のために予約される。マスター・ノードはグローバル・ビーコン期間を傾聴し、自分に割り当てられた時間スロットにおいてグローバル・ビーコンを送る。自分のクロックを同期させ、予約要求を交換するためである。グローバル・ビーコン期間はさらに二つの時間期間に分割される：上り期間（AP）３２２と下り期間（DP）３２４である。本発明のある好ましい実施形態では、時間ラウンドの継続時間は、グローバル・ビーコン期間の継続時間よりも著しく大きい。それにより制御オーバーヘッドを最小限にする。
【００１９】
上り期間の間に、情報は父祖（親）に渡され、下り期間の間は情報は子孫（子）に渡される。これは図３のＡおよびＢにおいてさらに示される。図３のＡおよびＢはそれぞれ、上り期間および下り期間の間の木トポロジーにおける情報伝搬の方向を示している。ノード「Ａ」はルートであり、ノード「Ｂ」「Ｅ」「Ｆ」は葉ノードである。グローバル・ビーコン期間中にグローバル・ビーコンを送るすべてのデバイスは、まとめて、ビーコン・グループと称される。この例では、ビーコン・グループはデバイスＡ、Ｂ、Ｃ、Ｄ、ＥおよびＦからなる。
【００２０】
具体的には、上り期間の間に、ルート以外のすべてのノードは自分のグローバル・ビーコンを、それぞれのスロットにおいて、上っていく順に送信する、すなわち子が親より前にグローバル・ビーコンを送る。オーファン〔孤児〕ノードとは、その親を発見しないノードである。この期間の間、親は子のグローバル・ビーコンおよびオーファン・ノードのグローバル・ビーコンを傾聴する。（図３のＡに示される）木トポロジーに基づくグローバル・ビーコン送信の上りシーケンスの例は、Ｆ→Ｅ→Ｄ→Ｃ→Ｂ→ＡおよびＢ→Ｅ→Ｄ→Ｆ→Ｃ→Ａである。
【００２１】
下り期間の間は、グローバル・ビーコン送信のシーケンスは逆になる。すなわち、親が子より先にグローバル・ビーコンを送信する。この期間中、子は親のグローバル・ビーコンを傾聴する。下り期間の間は、葉ノードおよびオーファンはグローバル・ビーコンを送信する必要はない。（図３のＢに示される）木トポロジーに基づくグローバル・ビーコン送信の下りシーケンスの例は、Ａ→Ｂ→Ｃ→Ｄ→Ｅ→ＦおよびＡ→Ｃ→Ｆ→Ｄ→Ｅ→Ｂである。
【００２２】
下りシーケンスが上りシーケンスの逆であることを注意しておくべきである。すなわち、上りシーケンスがＢ→Ｅ→Ｄ→Ｆ→Ｃ→Ａであるとすると、下りシーケンスはＡ→Ｃ→Ｆ→Ｄ→Ｅ→Ｂとなる。ルートは上り期間の間、そのグローバル・ビーコンを送信する必要がなく、葉ノードは下り期間の間そのグローバル・ビーコンを送信する必要がないので、グローバル・ビーコン送信の上りおよび下りのシーケンスは、空き時間スロットを含んでいてもよい。たとえば、図３−２のＤにおいて、上りシーケンスはＦ→Ｅ→Ｄ→Ｃ→Ｂ→＿であり、対応する下りシーケンスはＡ→＿→Ｃ→Ｄ→＿→＿である。ここで、「＿」は空きスロットを示す。グローバル・ビーコン送信を省くことにより、ノードは電力を節約する。
【００２３】
予約要求および他の関連する情報は、上り期間の間に、上りグローバル・ビーコン（AGB）を使ってルートに向かって伝搬させられる。上り期間の終わりには、ルートは完全なグローバル・トポロジーおよびすべてのマスター・ノードの予約要求を知っている。下り期間の間は、ルートはその情報をすべてのノードに、下りグローバル・ビーコン（DGB）を使って配送する。下り期間の終わりには、すべてのマスター・ノードはルートから必要とされる情報を受信する。
【００２４】
すべてのノードがルートの直接的な通信レンジ内にある必要はないことを注意しておくべきである。情報は、上り期間の間に子から親へと伝搬し、下り期間の間に親から子へと伝搬する。上記の例では、上り期間の間、ノード「Ｄ」はノード「Ｅ」から上りグローバル・ビーコンを受信し、その情報を、ルート「Ａ」によって受信されるべき自分の上りビーコンに埋め込む。同様に、下り期間の間、ノード「Ｄ」はルート「Ａ」から下りグローバル・ビーコンを受信し、その情報を、ノード「Ｅ」によって受信されるべき自分の下りビーコンに埋め込む。ルート「Ａ」とノード「Ｅ」は互いの直接的な通信レンジ外にあることを注意しておくべきである。しかしながら、ルート「Ａ」はノード「Ｅ」からの予約要求をノード「Ｄ」を通じて受信し、ノード「Ｅ」はルート応答をノード「Ｄ」を通じて受信する。このプロトコルは、ビーコン・グループ内のすべてのノードが情報を受信することを保証する。
【００２５】
電源投入される最初のノードがルートになり、ラウンド毎に、ルート・スロットにおいて、下りグローバル・ビーコンを送る。その後ブートするノードは、図３−２のＤに描かれている加入窓３３０内の「加入スロット」において自分のAGBを送ることによって、既存のビーコン・グループに加わる。新たに加わる各ノードは、ある親に割り当てられ、こうして木が構築される。加入窓は、新しいノードが既存のビーコン・グループに加わることを容易にするために割り当てられる所定数の時間スロット（加入スロット）である。ビーコン・グループ内のすべてのノードが加入窓内の加入スロットを傾聴する。加入窓は、新しいデバイスがビーコン・グループに加わって時間スロットを占有すると左に動き、デバイスがビーコン・グループを離脱するときには右に動く。新しいデバイスがビーコン・グループに加わるにつれ、上り期間におけるスロット占有は後方に成長し、下り期間におけるスロット占有は前方に成長していく。ルートが故障するまたはビーコン・グループを離脱すると、ルート・スロットの次のスロットを占有しているノードがルートになる。図３−２のＦに示されるように、ノードＢはノードＡがビーコン・グループを抜けた後にルートになる。デバイスが当該ビーコン・グループを離脱するために上り期間にできる非占有スロットは、それより前のスロットを占有していたデバイスによって満たされる。こうして、安定状態では、上り期間における加入スロットとルート・スロットとの間のすべてのグローバル・ビーコン・スロットは、図３−２のＥに示されるように、占有される。ノードがビーコン・グループを離脱するとき、木は図３−２のＦに示されるように枝刈りされる。こうして、木は分散式に動的に構築される。
【００２６】
図４は、本発明のある実施形態に基づいて開示されるグローバル・ビーコン・スケジューリング・プロトコル（GBSP:  global  beacon  scheduling  protocol）を動作させる方法を記述する、限定しない、例示的な図４００を示している。S410において、各マスター・ノードは、該ノードがブートされるときに初期化される。その後、種々の時間期間の間に繰り返されるプロセスが実行される。具体的には、S420において、上りグローバル・ビーコン（AGB）が葉ノードからルートに伝搬させられ、次いでS430において、上りグローバル・ビーコンはルートによって処理される。S440において、下りグローバル・ビーコン（DGB）はルートから他のすべてのノードに伝搬させられる。S450において、下りグローバル・ビーコンは、ルートでない各ノードによって処理される。上記の各方法ステップは、以下に詳しく述べる。
【００２７】
図５は、初期化ステップS410の実行をより詳細に記述する例示的な、限定しないフローチャートを示している。初期化ステップS410は、ノードが電源投入されたときに実行される。S511では、マスター・ノードが単一時間ラウンドの間、ビーコンを求めてスキャンする。時間ラウンドは、反復される固定された時間期間であり、その間にノードが媒体にアクセスできる。ステップS513およびS510では、マスター・ノードが、動作のための好適なチャネルを見出すまで、複数のチャネルを逐次的にスキャンしてもよい。S512では、その時間ラウンドの間にグローバル・ビーコンが受信されたかどうかが検査される。ビーコンが受信されておらず、チャネルが良好であると判定される場合には、S514において、マスター・ノードは自らがルートであると宣言し、自らのラウンド開始時間（RST:  round  start  time）を設定し、状態変数をあらかじめ定義された値に初期化する。その後、そのマスター・ノードはルートとして機能することを開始し、S515において実行はS440に進む。
【００２８】
マスター・ノードがグローバル・ビーコンを受信する場合には、ステップS516およびS517において、ノードはそのRSTを同期させ、ビーコン・グループのメンバーおよび現在のルートを決定する。S518では、ノードは状態変数をしかるべく初期化し、加入時間スロットになるまで傾聴する。S519では、ラウンド当たりあらかじめ定義された数までのノードが加わることを許容するよう、加入時間スロットはグローバル・ビーコン期間の先頭に位置特定される（located）。既存のビーコン・グループに加わろうとするノードは、S520において加入スロットの一つをランダムに選び、そのスロットにおいて上りグローバル・ビーコン送信をスケジューリングする。その後、S521において、実行はS420に続く。
【００２９】
既存のビーコン・グループのすべてのマスター・ノードは、加入してくるノードを発見するために加入時間スロットを傾聴する。ビーコン・グループに加わろうとするノードは、加入時間スロットにアクセスするために競争しなければならない。加わろうとしているノードがあるランダムな時間にわたって媒体がアイドルであることを感知すると、そのノードは上り期間の間にランダムに選ばれた加入スロットにおいて上りグローバル・ビーコンを送信する。加入するノードは、加入に成功するまではオーファンであると見なされ、加入に成功すると、そのノードはルートによって親を割り当てられる。ノードが競争に負けた場合は、そのノードは別の加入スロットを求めて競争する。ひとたびノードが加入スロットにおいてその上りグローバル・ビーコンを送ると、そのノードは下り期間になるまでスリープし、下り期間の間、そのノードは下りグローバル・ビーコンを傾聴する。ノードが下り期間の間に自らがルート下りグローバル・ビーコンにおいてリストされていることを見出す場合、既存のビーコン・グループに加わろうとするそのノードの試行は成功したことになる。そうでない場合には、ステップS520の実行を通じて、そのノードは、相続く諸ラウンドにおける加入窓の間に、ビーコン・グループに加わろうとする試行を繰り返す。そのような試行は、そのノードが加入に成功するまで、または許容される不成功の加入試行の最大数を超えるまで、繰り返される。
【００３０】
図６は、本発明のある実施形態に基づいて実装される、上り期間（ascending  period）の間のマスター・ノードの動作を記述する例示的なフローチャートS420を示している。上り期間の間、S618において、すべてのノードは加入時間スロットおよび子のスロットを傾聴する。具体的には、マスター・ノードは、ステップS618の実行を、ステップS613、S614およびS615において現在スロットがそのマスター・ノードの子によって所有されている、現在のスロットが加入スロットである、あるいはtopologyDiscovery〔トポロジー発見〕変数が真であると設定されていると判定される場合にのみ実行する。安定状態では、topologyDiscovery変数は偽に設定されており、トポロジーの何らかの変化が発見されたときは常に真に設定される。S619において、そのスロットが、そのノード自身のスロットより前かつ加入スロットより後に生起するかどうかが検査される。ノードは、上り期間中は、加入スロットより前および自分自身のスロットより後のスロットは傾聴する必要がない。S620において、現在スロットの間に、少なくとも一つの上りグローバル・ビーコンが受信されたことが判定される場合、S621において、受信された上りグローバル・ビーコンが記憶される。上りグローバル・ビーコンの送信ノードはその親ノードのIDを埋め込んでいるか、あるいは自らをオーファンであると同定する。これは、上りグローバル・ビーコンの受信者が、自分の子でもオーファンでもないノードから受信される上りグローバル・ビーコンを破棄するのを助ける。
【００３１】
現在スロットが当該ノードの時間スロットであり、そのノードがルートでない場合（S612およびS617）、そのノードは、その子およびオーファン・ノードすべてから受信された情報を含む上りグローバル・ビーコンを送る。そのノードがルートである場合には、実行は終了する。ステップS622およびS625を実行することによって、マスター・ノードは上り期間の間にすべての時間スロットを訪れる。
【００３２】
図７は、本発明のある実施形態に基づいて実装される、上りグローバル・ビーコンの処理を記述する例示的なフローチャートS430を示している。このプロセスは、上り期間の間に受信される上りグローバル・ビーコンを解析するルート・ノードによって実行される。S710では、何らかの上りグローバル・ビーコンが受信されたかどうかが検査され、もしそうであれば、実行はS711に続く。もしそうでなければ、実行はS722に進む。S711では、ルート・ノードは受信されたAGB（単数または複数）を解析し、時間スロット占有情報を判別し、現在の親‐子関係を評価する。具体的には、ルートは、あるビーコン・グループに属するノードからのAGBが見られなかった連続するラウンド数を数える。S712では、受信された各AGBについて、カウントダウン変数が所定値、例えば3にリセットされる。同様に、占有されている各スロットについて、スロットが未占有のままであった連続するラウンド数を数えるカウントダウン変数も所定値にリセットされる。
【００３３】
ルート下りグローバル・ビーコンが連続する所定数のラウンドにわたってなかった場合、ルート・スロットの次のスロットを占有するノードが自らを新しいルートであると宣言する。しかしながら、もとのルートがいまだ生きていてそのビーコンが一時的な干渉のためにみつからなかった可能性もある。これは、複数のノードが自らをルートであると広告する状況につながりうる。このような場合がS713において検査され、実際に複数のノードがルートであると広告されている場合、S705において、それらのルートのどれが最も高いランクを有するかが判定される。最高のランクをもつルートがそのルートの地位を保持し、他のルートはルートとしては認識されない。ノードのランクは、一意的であり曖昧さがなく各ビーコンと一緒に広告される、ノードのMAC  IDに基づくこともできる。あるいはまた、ノードのランクは残留エネルギー（residual  energy）または占有されているグローバル・ビーコン・スロットまたは多くのパラメータの組み合わせの関数であることもできる。
【００３４】
その後、S714において、そのビーコン・グループ内にオーファン・ノードがあるかどうかが判定され、もしあればS715においてルートは各オーファン・ノードに対して一つの親を割り当てる。S716において、新しいノードが既存のビーコン・グループに加わったかどうかが判定され、もしそうであれば、S717において、加入窓が更新される。S718では、上りグローバル・ビーコン中の新たに加わったノードの上りグローバル・ビーコンを聞いた既存のノードの一つが、新たに加わったノードの親にされ、木トポロジーはしかるべく更新される。
【００３５】
S719では、次のラウンドにおいていずれかのノードがビーコン・グループを礼儀正しく（gracefully）離脱するかどうかが検査される。マスター・ノードはビーコン・グループを礼儀正しく離脱するまたは無断で（silently）離脱することがありうる。礼儀正しく抜ける場合、ノードは、ビーコン・グループを離脱する意向を、その情報を上りグローバル・ビーコンに埋め込むことによって宣言し、それによりルートは、離脱するというノードの希望について知る。ノードが礼儀正しく抜けるとき、S720で、ルートはそのノードを木から取り除き、木を更新し、抜けるノードはその親の子リストからパージされる。S720においてさらに、離脱するノードの子はオーファンとしてマークされ、そのスロットは空きとタグ付けされる。そのノードが葉ノードでなければ、S721において、topologyDiscovery変数が真の値に設定される。
【００３６】
ノードは、親が抜けたらオーファンになる。オーファン・ノードのための新しい親をみつけることができるためには、残りのノードがオーファン・ノード・スロットを傾聴する必要がある。topologyDiscovery変数を真の値に設定することは、ノードが、自分のスロットより前でかつ加入スロットより後のすべてのスロットを傾聴することを可能にする。ルートがビーコン・グループを離脱する場合には、次のスロットを占有しているノードがルートになることを注意しておく。新しいルートがその責務を帯びるのは、次のラウンドからである。
【００３７】
ノードは、突然グローバル・ビーコンの送信を止めることによって、無断でビーコン・グループを抜けることがありうる。よって、現在ラウンドのビーコン・スロット占有情報をビーコン・グループのメンバーシップと比較することによって、ルートはどのノードが上りグローバル・ビーコンを送信しなかったかを発見できる。グローバル・ビーコンは、干渉または衝突またはそのノードが（たとえばバッテリー切れのため）無断で抜けたことのために見逃されたことがありうる。したがって、S722において、そのビーコン・グループ中の何らかの既存のノードの上りグローバル・ビーコンがみつからなかったどうかが判定され、もしそうであれば、S723においてtopologyDiscovery変数が真の値に設定され、みつからないノードおよびその子はオーファンとしてマークされる。さらに、S724において、みつからないノードがビーコン・グループからパージされ、木が枝刈りされ、そのノードの親がみつからないノードを子のリストから除去するよう通知される。ある好ましい実施形態では、ステップS724は、ノードの上りグローバル・ビーコンが所定数の連続するラウンドにわたってみつからなかった場合にのみ実行される。ビーコン・グループ全体からの上りグローバル・ビーコンが受信される場合、そのことは、安定なトポロジーを示し、したがって、S725において、topologyDiscovery変数は偽に設定される。無断で抜けたノードのビーコン・スロットは、ルートによってビーコン・グループから除去されるまで、所定数のラウンドにわたって保存されてもよい。これは、マスター・ノードが、たとえそのグローバル・ビーコン期間の間に衝突または干渉を経験したとしても、正常に機能することを許容する。
【００３８】
S726およびS727において、上り期間における最初の占有されたスロットおよび最後の占有されたスロットの間の何らかのスロットが所定数の連続するラウンドにわたって非占有のままであるかどうかが検査され、もしそうであれば、S728において、ノードは、空きスロットを埋めるために、自分のスロットをルートに向かって動かすようスケジュールされる。ノードがそのスロットをルートに向かって動かすようスケジュールされる場合、その親および子は下りグローバル・ビーコンを介して、迫っている動きについて通知される。上り期間における最初の占有されたスロットが空きになる場合、加入窓はこの変化を反映するよう更新される。こうして、安定状態においては、加入スロットとルートのスロットとの間に空きスロットはない。S729では、ルートは、更新された木情報、スロット占有情報、加入スロット位置、topologyDiscovery変数および動くスロット情報を含む出ていく下りグローバル・ビーコンを構築する。
【００３９】
ルート以外のノードがルートの下りグローバル・ビーコンを見逃す場合、そのノードはsearchingForRoot〔ルート検索中〕およびtopologyDiscoveryの変数を真に設定する。このことが起こりうるのは、たとえば、ルート下りグローバル・ビーコンのノードへの伝搬を防止するためのトポロジー変化のためである。これは、ノードがS702においてAGBを解析し、S703において現在のルートを知っている他のノードがあるかどうかを判定することを可能にする。もしそうであれば、S704において、そのノードはslotReordering〔スロット再順序付け〕変数を真の値に設定する。あるノードがルート下りグローバル・ビーコンを受信しないがビーコン・グループ内にルート下りビーコンを受信する他のノードがあるという事実は、当該ノードがもはやそのルートの子孫のうちにはいっていないことを示す。この状況を是正するためには、ルート・ビーコンを見逃したノードがそのスロットを動かしてルートの子孫になることが必要である。slotReordering変数の設定が、そのノードに、そのAGBをランダムに選ばれた加入スロットにおいて送信し、それによりルートの子孫になることを強制する。
【００４０】
図８は、本発明のある実施形態に基づいて実装される、下り期間の間の下りグローバル・ビーコンの伝搬を詳細に記述する例示的なフローチャートS440を示している。下り期間は、S812においてルートがその下りグローバル・ビーコンを送ることをもって始まる。さらに、S814において、親ノードが、その子によって受信されるよう、ルート下りグローバル・ビーコンの逐語的な（verbatim）コピーを送信する。その後、S815において、ルートおよび他の親は、下り期間の終わりになるまでスリープする。ノード（ルート以外の）は、S816において、現在のスロットが自分の親によって所有されているかどうかを判定する検査を実行し、もしそうであれば、S818で、自分の親のスロットに傾聴する。ノードはまた、S817においてtopologyDiscovery変数が真である場合、S818において、自分のスロットよりも前に生起するスロットをも傾聴する。S820では、下りグローバル・ビーコンを受信する（ルート以外の）ノードは、そのクロックを親と同期させ、その情報を記憶する。ステップS821およびS819は、ノードが、下り期間の間にすべての時間スロットを訪れることを保証する。
【００４１】
図９は、本発明のある実施形態に基づいて実装される、下りグローバル・ビーコンの処理のステップを記述する例示的なフローチャートS450を示している。（ルートでない）各ノードは、ルートによって送られた下りグローバル・ビーコンにおいてカプセル化されている情報を処理する。S911において、ルート下りグローバル・ビーコンが前記ルートによってその親から受信されたかどうかが検査される。複数の下りグローバル・ビーコンが二つ以上のルートから受信された場合、S916において、ランクが最高のルートが、有効なルートとして選択される。その後、S917において、前記ルートがこのノードについての情報を含めたか否かを判定する検査が実行される。S918において、下りグローバル・ビーコンに含められた情報、たとえばトポロジー、スロット占有、親‐子関係、オーファン・ノードなどが、当該ノードによって処理される。具体的には、当該ノードは、その親ノードIDおよびその時間スロット、その子のノードIDおよびそれらの時間スロット、オーファン・ノードのステータス、topologyDiscovery変数、ノード時間スロットおよび木トポロジーを維持するために利用される他の変数を更新する。当該ノードは現在ラウンドにおいてルートから下りグローバル・ビーコンを受信したので、当該ノードは変数searchingForRootおよびslotReorderingを偽に設定する。さらに、countdownToBecomeRoot〔ルートになるまでのカウントダウン〕変数がslotDist〔スロット距離〕の値にリセットされる。これについてはのちに詳述する。
【００４２】
S911では、ノードがルートから下りグローバル・ビーコンを受信しなかったかどうかが検査される。もしそのとおりであれば、S912において、slotReordering変数値が真か偽かを判定する別の検査が実行される。slotReordering変数の真の値は、そのノードは下りグローバル・ビーコンをルートから受信しなかったものの、ルートの下りグローバル・ビーコンを受信した他のノードがあることを示す。この状況を是正するため、S919において、ノードは加入スロットの一つをランダムに選択し、上り期間の間の選択されたスロットにおいて、上りグローバル・ビーコン送信をスケジュールする。他方、slotReordering変数値が偽である場合、S913において、ノードは自らをオーファンとマークし、countdownToBecomeRoot変数が1だけデクリメントされ、searchingForRootおよびtopologyDiscovery変数が真に設定される。countdownToBecomeRootはグローバル変数であり、
slotDist＝｜ルートのスロットid−自分のスロットid｜＋1
のように計算されるslotDistの値に初期化される。
【００４３】
S914において実行される検査に基づいて、countdownToBecomeRoot値が0と異なっている限り、searchingForRootおよびtopologyDiscovery変数の値は真のままである。countdownToBecomeRoot変数が0に達するとき、S920においてそのノードはルートになり、searchingForRootは偽に設定される。ルートが無断で消える場合を扱う例を以下に述べる。
【００４４】
図１０は、ルートが死ぬときに木を更新するプロセスの例を与えている。この例は、図３のＡおよびＢに示される木トポロジーを参照する。ビーコン・グループ、加入窓ならびに上り期間および下り期間の間の時間スロット占有は図３−２のＤおよびＥに示されている。
【００４５】
図１０に与える表の第２列は、図３−２のＣに示されるスロット占有に基づいて、各ノードにおけるcountDownToBecomeRoot変数の値を示している。安定状態（すなわちラウンドn）では、countDownToBecomeRoot変数はslotDistに設定されている。これはノードＢについては2、ノードＣについては3などである。ルートＡはラウンドnにおいて死ぬ。ラウンドn＋2の終わりに、ノードＢにおけるcountDownToBecomeRoot変数の値は0に達し、ノードＢはルートになる。ラウンドn＋3の間に、ノードＢは、その下りグローバル・ビーコンにおいて、自らをルートとして広告する。ノードＢの下りグローバル・ビーコンは、ノードＣおよびＤによって受信され、ノードＣおよびＤは第５列に示されるように、そのcountDownToBecomeRoot変数をslotDistにリセットする。ラウンドn＋4の終わりには、ノードＥおよびＦも新しいルートＢの存在を、それぞれノードＤおよびＣの下りグローバル・ビーコンから知る。ここで、ラウンドn＋4の終わりには、ノードＥおよびＦも、最後の列に示されるように、そのcountDownToBecomeRootをslotDistにリセットする。徐々にノードＢがノードＡのスロットを受け継ぎ、次いでノードＣがノードＢのスロットを受け継ぎ、などとなる。こうして、すべての空きスロットが一つずつ埋められていき、その結果、図３−２のＣに示される更新されたグローバル・ビーコン・スロット占有および図３−２のＤに示される更新されたトポロジーとなる。
【００４６】
他方、ノードＣが3連続ラウンドにわたってルート・ビーコンを聞かない（すなわちノードＡおよびＢが両方とも死んでいる）場合、ノードＣはラウンドn＋3の終わりにルートの役割を帯びる。同様に、ノードＤは、4連続ラウンドにわたってルートから何も聞かない場合、ラウンドn＋4の終わりに自らをルートであると宣言する。
【００４７】
個々のノードが自律的に自らをルートであると宣言するので、複数のルートが同時に動作している状況が起こることがありうる。この種の状況は、ランクが最高のルートだけにルートとして機能し続けることを許容することによって解決され、他のルートは通常ノードになる。これはステップS908、S909およびS910によって例証されている。このことは、提案されるプロトコルが、ルート障害を含むノード障害から効率的に回復できることを示す。
【００４８】
本稿に記載される教示が、身体領域ネットワーク（BAN）にとって、該ネットワークの特性のため、非常に魅力的であることが理解されるであろう。具体的には、身体領域ネットワーク（BAN）は、伝送レンジは3メートルである非常に局在化したネットワークである。よって、たいていのノードは互いと直接的な通信レンジ内にある。いかなる無線ネットワークにおいても、予約を実施し（enforce）、隠れたノード衝突を回避するためには２ホップ近傍の知識は不可欠である。身体領域ネットワーク（BAN）の場合、２ホップ近傍の知識を取得することは、グローバルな知識を得ることと等価である。よって、グローバル情報を集めることは、追加的なオーバーヘッドを生じない。さらに、グローバルな知識は、スケジューリング・アルゴリズムを最適化するために賢明に活用できる。チャネル利用度（utilization）およびスループットは、グローバルな知識を用いて改善できる。さらに、グローバルなトポロジーの知識により、別個のルーティング層の必要がなくなる。これは、プロトコル・オーバーヘッドおよびメモリ・フットプリントのかなりの節約につながり、これは最終的にはエネルギー節約につながる。
【００４９】
木トポロジーに基づくグローバル・ビーコン送信のシーケンス化は、ネットワーク全体を同期させるためにも好適である。下り期間の間に、ルートは深さ１における諸ノードを同期させ、それらは今度は深さ２における諸ノードを同期させる、などとなる。
【００５０】
上記の方法が、これに限られないが、トラフィック指示マップ（traffic  indication  map）、リンク状態、受信信号強度インジケータ、ハイバーネーション〔冬眠〕・モード・インジケータ、チャネル・スイッチ記述子、ラウンド開始時間オフセット、マルチキャスト・バインディング、セキュリティ情報などを含む他の型の情報を交換するためにも使用できることも理解されるであろう。
【００５１】
以上の詳細な記述は、本発明が取ることのできる数多くの形のうちの若干を述べている。以上の詳細な記述が、本発明の定義に対する限定としてではなく、本発明が取ることのできる選ばれた形の例解として理解されることが意図されている。本発明の範囲を定義することが意図されているのは、あらゆる等価物を含む請求項のみである。
【００５２】
最も好ましくは、本発明の原理はハードウェア、ファームウェアおよびソフトウェアの任意の組み合わせとして実装される。さらに、ソフトウェアは好ましくはプログラム記憶ユニットまたはコンピュータ可読媒体上に有形的に具現されたアプリケーション・プログラムとして実装される。アプリケーション・プログラムは、任意の好適なアーキテクチャをもつ機械にアップロードされ、これによって実行されてもよい。好ましくは、該機械は、一つまたは複数の中央処理ユニット（「CPU」）、メモリおよび入出力インターフェースのようなハードウェアを有するコンピュータ・プラットフォーム上で実装される。コンピュータ・プラットフォームはオペレーティング・システムおよびマイクロ命令コードを含んでいてもよい。本稿で記載されているさまざまなプロセスおよび機能は、マイクロ命令コードの一部であっても、アプリケーション・プログラムの一部であっても、それらの任意の組み合わせであってもよく、CPUによって実行されてもよい。これは、そのようなコンピュータまたはプロセッサが明示的に示されているか否かにはよらない。さらに、追加的なデータ記憶ユニットおよび印刷ユニットといったさまざまな他の周辺ユニットがコンピュータ・プラットフォームに接続されてもよい。
【図１】
0005406298.tif 000002
【図２】
0005406298.tif 000003
【図３−１】
0005406298.tif 000004
【図３−２】
0005406298.tif 000005
【図４】
0005406298.tif 000006
【図５】
0005406298.tif 000007
【図６】
0005406298.tif 000008
【図７】
0005406298.tif 000009
【図８】
0005406298.tif 000010
【図９】
0005406298.tif 000011
【図１０】
0005406298.tif 000012