(57)【要約】      （修正有）【課題】アドホックネットワークにおいて、分散型の強固なクラスタヘッドノード選出手法を提供する。【解決手段】アドホックネットワークは複数の移動ノードを含み、それら複数の移動ノードは、現在選出されているクラスタヘッドノードとともにクラスタとして動作する少なくとも１つの移動ノード群を含む。移動ノードは、制御部および無線通信装置を含み、制御部および無線通信装置は、共に協働して、現在選出されているクラスタヘッドノードが動作不能に見えるかどうかを決定し、決定に基づいてトークンによるクラスタヘッドノード選出を開始する。トークンによるクラスタヘッドノード選出の際、クラスタの移動ノードは、それぞれのトークン重みを有するトークンを生成して送信し、近隣ノードからトークンを受信し、トークン重みに基づいてトークンを選択的に再送信し、トークン重みに基づいて新しいクラスタヘッドノードを選出する。【選択図】図１
2008283674.tif 000002
【特許請求の範囲】
【請求項１】
アドホックネットワーク内で複数の移動ノードのクラスタにおいて動作する移動ノードであって、前記クラスタは、現在選出されているクラスタヘッドノードを含み、
前記移動ノードは制御部および無線通信装置を含み、該制御部および該無線通信装置は共に協働して、前記現在選出されているクラスタヘッドノードが動作不能に見えるかどうかを決定し、前記決定に基づいてトークンによるクラスタヘッドノードの選出処理を開始し、該選出処理は、
トークン重みを有するトークンを生成して送信することと、
近隣ノードからトークンを受信することと、
前記トークン重みに基づいて前記トークンを選択的に再送信することと、
前記トークン重みに基づいて新しいクラスタヘッドノードを選出することと
を含むことを特徴とする移動ノード。
【請求項２】
前記制御部および前記無線通信装置は協働して、前記現在選出されているクラスタヘッドノードから状態メッセージを所定の期間、受信できないことに基づいて、前記現在選出されているクラスタヘッドノードが動作不能に見えるかどうかを決定することを特徴とする請求項１に記載の移動ノード。
【請求項３】
前記制御部および前記無線通信装置は協働して、前記現在選出されているクラスタヘッドノードから応答メッセージを傍受できないことと、前記現在選出されているクラスタヘッドノードへ確認要求メッセージを送ることと、前記現在選出されているクラスタヘッドノードから確認メッセージを受信できないこととに基づいて、前記現在選出されているクラスタヘッドノードが動作不能に見えるかどうかを決定することを特徴とする請求項１に記載の移動ノード。
【請求項４】
前記トークンは選出メッセージを有し、各選出メッセージがノードＩＤとパラメータ値とを含むことを特徴とする請求項３に記載の移動ノード。
【請求項５】
前記トークン重みは、前記ノードＩＤと前記パラメータ値とに基づく重み値で規定され、前記制御部および前記無線通信装置は協働して、受信された前記トークンのうちで最高の重み値をもつものと定義される最良トークンを再送信し、前記制御部は、前記最良トークンの前記ノードＩＤをクラスタヘッドノードＩＤとして格納することを特徴とする請求項４に記載の移動ノード。
【請求項６】
移動アドホックネットワーク内でクラスタとして動作する一群の移動ノードのためのクラスタヘッドノードを選出する方法であって、
現在選出されているクラスタヘッドノードが動作不能に見えるかどうかを決定することと、
前記決定に基づいてトークンによるクラスタヘッドノードの選出処理を開始することと
を含み、該選出処理の際に前記クラスタの移動ノードは、
それぞれの移動ノードのトークン重みを有するトークンを生成して送信し、
近隣ノードからトークンを受信し、
前記トークン重みに基づいて前記トークンを選択的に再送信し、
前記トークン重みに基づいて新しいクラスタヘッドノードを選出する
ことを特徴とする方法。
【請求項７】
前記現在選出されているクラスタヘッドノードが動作不能に見えるかどうかを決定することは、前記現在選出されているクラスタヘッドノードから状態メッセージを所定の期間、受信できないことに基づいて行われることを特徴とする請求項６に記載の方法。
【請求項８】
前記現在選出されているクラスタヘッドノードが動作不能に見えるかどうかを決定することは、前記現在選出されているクラスタヘッドノードから応答メッセージを傍受できないことと、前記現在選出されているクラスタヘッドノードへ確認要求メッセージを送ることと、前記現在選出されているクラスタヘッドノードから確認メッセージを受信できないこととに基づいて行われることを特徴とする請求項６に記載の方法。
【請求項９】
前記トークンは選出メッセージを備え、各選出メッセージはノードＩＤとパラメータ値とを含むことを特徴とする請求項６に記載の方法。
【請求項１０】
前記トークン重みは、前記ノードＩＤと前記パラメータ値とに基づく重み値で規定されることを特徴とする請求項９に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信の分野に関し、特に、アドホックネットワークにおける無線通信と、関連する方法とに関する。
【背景技術】
【０００２】
ここ１０年の間、無線ネットワークはますます発展を遂げてきた。最も急速に発展している領域の１つが、移動アドホックネットワークである。物理的にいうと、移動アドホックネットワークは、共通の無線チャネルを共有する、地理的に分散した移動可能な複数のノードを含む。セルラーネットワークまたは衛星ネットワークといった他の種類のネットワークと比較すると、移動アドホックネットワークの最も顕著な特徴は、固定インフラをもたないということである。このネットワークは移動ノードのみで形成されてよく、ノードどうしが互いに伝送し合うと「その場で」ネットワークが作られる。このネットワークは、特定のノードに依存せず、あるノードがネットワークに参加したり他のノードがネットワークから離れたりするのに対して動的に適応する。
【０００３】
こうした固有の特徴があるので、アドホックネットワーク内でデータフローを管理する経路制御プロトコルとしては、頻繁なトポロジ変化に適応できるものが必要である。近年、アドホック経路制御プロトコルの２つの基本カテゴリーが登場した。すなわち、リアクティブ型つまり「オンデマンド型」のプロトコルと、プロアクティブ型つまりテーブル駆動型のプロトコルである。リアクティブ型プロトコルは、経路要求に応じて宛先への特定の経路が必要になった時に、経路制御情報を収集する。リアクティブ型プロトコルの例としては、アドホックオンデマンド距離ベクトル（ad-hoc on demand distance vector、ＡＯＤＶ）経路制御、動的ソース経路制御（dynamic source routing、ＤＳＲ）、時間的に順序付けられた経路制御アルゴリズム（temporally ordered routing algorithm、ＴＯＲＡ）などがある。
【０００４】
一方、プロアクティブ型経路制御プロトコルは、ネットワークにおける各ノードから他のあらゆるノードまでの、整合性のある最新の経路制御情報の維持を試みるものである。このようなプロトコルでは、典型的には、経路制御情報を格納する１以上のテーブルを各ノードが維持する必要があり、また、ネットワーク全体に最新情報を伝達してネットワークの整合性あるビューを維持することによって、ネットワークトポロジの変化に応じる。このようなプロアクティブ型経路制御プロトコルの例としては、パーキンズ（Perkins）に対する米国特許第５，４１２，６５４号に開示された宛先が順序付けられた距離ベクトル（destination-sequenced distance-vector、ＤＳＤＶ）経路制御、無線経路制御プロトコル（wireless routing protocol、ＷＲＰ）、クラスタヘッドゲートウェイスイッチ経路制御（clusterheadgateway switch routing、ＣＧＳＲ）などがある。プロアクティブ型およびリアクティブ型の両手法を用いる混成型プロトコルはゾーン経路制御プロトコル（zone routing protocol、ＺＲＰ）であり、このプロトコルは、ハース（Haas）に対する米国特許第６，３０４，５５６号に開示されている。
【０００５】
アドホックネットワーク開発の進歩にとっての課題の１つは、多数のノードを含むためにこのようなネットワークを拡張するということである。それを狙ったある先行技術の試みでは「脊椎型」（spine）の経路制御を利用しているが、これは例えば、１９９７年の通信に関するＩＥＥＥ国際会議（IEEE International Conference on Communications、ICC '97）における「最小連結支配集合を用いた、アドホックネットワークにおける経路制御」（Routing in Ad-Hoc Networks using Minimum Connected Dominating Sets）にてダス（Das）らによって開示された、最適スパイン経路制御（optimal spine routing、ＯＳＲ）手法などにおいて見られる。この手法では、スパインつまり「仮想の背骨」が、各ネットワークノードがスパインノードから１ホップだけしかないように定義される。全体のトポロジ（リンク状態）が各スパインノードで維持され、また、あらゆる宛先への現在の経路を生成するためにリンク状態型経路制御アルゴリズムが各スパインノードで実行される。
【０００６】
もう１つの関連手法は、クラスタ型スパイン経路制御（clustered spine routing、ＣＳＲ）であり、この手法は、１９９７年のコンピュータの通信とネットワークに関するＩＥＥＥ国際会議（IEEE International Conference on Computer Communications and Networks、ICCCN '97）における「スパインを用いた、アドホックネットワークにおける経路制御」（Routing in Ad Hoc Networks using a Spine）にてダス（Das）らによって開示されている。この手法の目的は、ノードをクラスタにグループ分けするとともにＯＳＲ手法に第２階層水準を加えることによって、スパイン経路制御の適用可能性をより大きなネットワーク規模へと拡張することである。さらに別の手法は、部分知識型スパイン経路制御（partial knowledge spine routing、ＰＳＲ）として知られており、この手法は、１９９８年のコンピュータと通信に関するＩＥＥＥシンポジウム（IEEE symposium on Computers and Communications）における「分岐群脊椎動物門：アドホックネットワークにおけるスパインと経路制御」（The Clade Vertebrata: Spines and Routing in Ad Hoc Networks）にてシバクマール（Sivakumar）らによって開示されている。
【０００７】
アドホックネットワークにおいて、クラスタは、トポロジ的に接続されたノードの群であり、これらのノードは、群において構成員としての地位を共有する。クラスタは、１ホップまたは多数のホップに及ぶことができる。クラスタのヘッダノードは、クラスタの役に立つ特定の機能を有し、また、クラスタヘッドまたは群サーバノード（Group Server Node、ＧＳＮ）と呼ばれてよい。どのノードがＧＳＮになってもよく、ＧＳＮのノードＩＤは、群ＩＤに用いられてよい。群内にはＧＳＮが１つだけ存在するものとされ、また、現在のＧＳＮの電源が落とされた時、または現在のＧＳＮがネットワークもしくは群を離れた時は、新しいＧＳＮが選ばれるものとされる。
【０００８】
ネットワーク内のノードは局所的な知識しか有さないため、ＧＳＮを選出するのに用いられる手法は分散型の方法でなければならない。どのノードが次のＧＳＮになるべきかを裁定するために前もってノードが手動で選ばれるべきではない。ノードが入ったり離れたり、ノードの電源が落ちたり、ノードが姿を消したりするアドホックネットワークにおいては、トポロジが変化しているので、ＧＳＮの選出手法は強固である必要もある。また、ＧＳＮは再選出される場合がある。問題点としては、選出方法によって、複数のＧＳＮを選出したりＧＳＮを１つも選出しなかったりするという結果を招く可能性がある、ということなどがある。非対称リンクや、不安定なリンク、通信接続手順の中断のために、選出されたＧＳＮがアクセス不能になることもある。複数のＧＳＮが選出された場合、それらのうちいくつかは、その状態を放棄せざるを得ない。また、選出処理によってノードが多くの帯域幅を消費することになる可能性があり、システムのオーバーヘッドになってしまう。
【０００９】
またＧＳＮ選出、群の結合、およびタイミング調整がサポートされない場合がある。ＧＳＮは、タイミング基準ノードである。群が結合する間に、１つの群の一部のノードが新たな群へ移ろうとして、それと同時にネットワークタイミングに変化が生じる可能性もある。もしＧＳＮ選出も進行中であれば、どのノードが正しいタイミングを保持し、いくつのＧＳＮがこの混合状態において併存している可能性があるのかについて、ノードが混乱することになる。
【００１０】
また、ＧＳＮ選出の間に、ネットワークの一部が複数の下位群に分かれる場合があり、選出されたＧＳＮが、分かれた下位群のいくつかに到達できなくなっていることがある。さらに、ＧＳＮが、非対称リンクをクラスタに接続した状態のまま、ネットワークから部分的に離れる場合がある。すべてのクラスタノードは、ＧＳＮからの受信はできるが、ＧＳＮへの送信ができない。新しいＧＳＮの選出は、前のＧＳＮの非対称リンクの影響下で進行できなければならない。また、構成ノードは、前のＧＳＮを群から永遠には除外しないようにする。これは、前のＧＳＮが普通の構成ノードとして戻ることを許可されるべきだからである。
【００１１】
これらの問題のいくつかに対処する手法の１つが、低エネルギー局所型クラスタ化（Low-energy localized clustering、ＬＬＣ）アルゴリズムである。任意のあるノードが、ある時間、局所的近隣において他のノードがクラスタヘッドとして宣言されるのを認識しない場合、その任意のノードが自身をクラスタヘッドであると単に宣言する。マルチホップネットワークであれば、多数のクラスタヘッドが選出され得る。選出処理において各ノードが広告メッセージを送って自身の構成員としての地位を宣言するため、この手法は帯域幅効率がよくない。この手法に確認応答が含まれる場合は、さらなる帯域幅が消費される。不安定なリンクのためにいくつかのメッセージが落とされる恐れがあり、また非対称リンクによって、到達不能なクラスタヘッドが生じる可能性がある。さらに、このＬＬＣ手法ではクラスタが２ホップ近隣型のみに限定されるが、多くのクラスタ化手法は２ホップを超える範囲に及ぶ場合がある。
【００１２】
もう１つの手法は、より帯域幅効率に優れた方法である低エネルギー適応型クラスタ化階層（Low Energy Adaptive Clustering Hierarchy、ＬＥＡＣＨ）アルゴリズムである。定期的に、ある確率で、ノードが現在のクラスタヘッドを放棄して自身がクラスタヘッドであると宣言する。この方法では、多数のメッセージ交換は不要であるが、クラスタヘッドが多数になったり、クラスタヘッドが全くなくなったりする可能性がある。従って、この手法は、多くの応用例にとって好適ではないかもしれない。
【特許文献１】米国特許第５，４１２，６５４号明細書
【特許文献２】米国特許第６，３０４，５５６号明細書
【非特許文献１】ダス（Das）ら「最小連結支配集合を用いた、アドホックネットワークにおける経路制御」（Routing in Ad-Hoc Networks using Minimum Connected Dominating Sets）、通信に関するＩＥＥＥ国際会議（IEEE International Conference on Communications、ICC '97）、１９９７年
【非特許文献２】ダス（Das）ら「スパインを用いた、アドホックネットワークにおける経路制御」（Routing in Ad Hoc Networks using a Spine）、コンピュータの通信とネットワークに関するＩＥＥＥ国際会議（IEEE International Conference on Computer Communications and Networks、ICCCN'97）、１９９７年
【非特許文献３】シバクマール（Sivakumar）ら「分岐群脊椎動物門：アドホックネットワークにおけるスパインと経路制御」（The CladeVertebrata: Spines and Routing in Ad Hoc Networks）、コンピュータと通信に関するＩＥＥＥシンポジウム（IEEE symposium on Computers and Communications）、１９９８年
【発明の開示】
【発明が解決しようとする課題】
【００１３】
本発明の目的は、上記背景に鑑みて、アドホックネットワークにおいて、帯域幅効率に優れた、分散型の強固なクラスタヘッドノード選出手法を提供することである。
【課題を解決するための手段】
【００１４】
本発明によるこの、または他の目的、特徴、および効果は、複数の移動ノードを含むアドホックネットワークによって提供され、それら複数の移動ノードは、現在選出されているクラスタヘッドノードとともにクラスタとして動作する少なくとも１つの移動ノード群を含む。各移動ノードは、制御部および無線通信装置を含み、制御部および無線通信装置は共に協働して、現在選出されているクラスタヘッドノードが動作不能（非アクティブ、非動作状態、inactive）に見える（判断される）かどうかを決定し、決定に基づいてトークンによるクラスタヘッドノード選出を開始する。トークンによるクラスタヘッドノード選出の際、クラスタの複数の移動ノードは、それぞれのトークン重みを有するトークンを生成して送信し、近隣ノードからトークンを受信し、トークン重みに基づいてトークンを選択的に再送信し、トークン重みに基づいて新しいクラスタヘッドノードを選出する。
【００１５】
制御部および無線通信装置は協働して、現在選出されているクラスタヘッドノードから状態メッセージを所定の期間、受信できないことに基づいて、現在選出されているクラスタヘッドノードが動作不能であると決定してよい。また、制御部および無線通信装置は協働して、現在選出されているクラスタヘッドノードから応答メッセージを傍受できないことと、現在選出されているクラスタヘッドノードへ確認要求メッセージを送ることと、現在選出されているクラスタヘッドノードから確認メッセージを受信できないこととに基づいて、現在選出されているクラスタヘッドノードが動作不能であると決定してよい。
【００１６】
現在選出されているクラスタヘッドノードが動作不能であるかどうかの決定には、制御部および無線通信装置が共に協働して少なくとも１つの近隣ノードの存在を決定することをさらに含んでよい。トークンはそれぞれの移動ノードの選出メッセージを有してよく、各選出メッセージはノードＩＤとパラメータ値とを含み、パラメータ値は、例えば、該当クラスタノードの近隣ノードの数を示すものである。関連付けられているトークン重みは、ノードＩＤとパラメータ値とに基づく重み値で規定されてよい。制御部および無線通信装置は、協働して、最高重み値をもつ受信トークンというように定義される最良トークンを再送信してよい。制御部は、最良トークンのノードＩＤをクラスタヘッドノードＩＤとして格納してもよい。選出メッセージは、トークンの伝送の境界を規定する群ＩＤ、および／または、トークンが伝送され得る回数を規定する生存回数フィールドをさらに含んでよい。
【００１７】
本発明の別の態様は、アドホックネットワーク内で複数の移動ノードのクラスタにおいて動作する移動ノードを指向したものであり、クラスタは、現在選出されているクラスタヘッドノードを含み、移動ノードは、制御部および無線通信装置を含み、制御部および無線通信装置は共に協働して、現在選出されているクラスタヘッドノードが動作不能に見えるかどうかを決定し、決定に基づいてトークンによるクラスタヘッドノード選出を開始する。この選出処理は、好ましくは、それぞれの移動ノードのトークン重みを有するトークンを生成して送信することと、近隣ノードからトークンを受信することと、トークン重みに基づいてトークンを選択的に再送信することと、トークン重みに基づいて新しいクラスタヘッドノードを選出することとを含む。
【００１８】
本発明の方法の態様は、移動アドホックネットワーク内でクラスタとして動作する一群の移動ノードのためのクラスタヘッドノードを選出することを指向したものであり、現在選出されているクラスタヘッドノードが動作不能に見えるかどうかを決定することと、決定に基づいてトークンによるクラスタヘッドノード選出を開始することとを含む。クラスタの移動ノードは、選出の際に、それぞれのトークン重みを有するトークンを生成して送信し、近隣ノードからトークンを受信し、トークン重みに基づいてトークンを選択的に再送信し、トークン重みに基づいて新しいクラスタヘッドノードを選出する。
【発明を実施するための最良の形態】
【００１９】
以下、添付の図面を参照して、本発明をさらに十分に説明する。添付の図面には、本発明の好ましい実施の形態が示されている。しかしながら、本発明は、多くの異なる形態で実施されてよく、ここに示された実施の形態に限定されると解釈されるべきではない。むしろ、これらの実施の形態は、この開示が徹底的かつ完全となるように、そして、この開示によって本発明の範囲が当業者に十分に伝わるように、提供されている。なお、全体を通して、同一の番号は、同一の要素を指すものとする。
【００２０】
本発明の手法が、特定の通信規格（無線または他のもの）での利用に限定されないこと、そして、多くの無線（または有線）通信規格での利用に適合させられ得ることは、当業者の認めるところである。これらの無線（または有線）通信規格には、例えば、ＧＳＭ進化型高速データレート（Enhanced Data rates for GSM Evolution、ＥＤＧＥ）、汎用パケット無線サービス（General Packet Radio Service、ＧＰＲＳ）または拡張ＧＰＲＳ（Enhanced GPRS、ＥＧＰＲＳ）、拡張データレートブルートゥース（extended data rate Bluetooth）、広帯域符号分割多元接続（ＷＣＤＭＡ）、無線ＬＡＮ（ＷＬＡＮ）、ウルトラワイドバンド（ＵＷＢ）、同軸ケーブル、レーダー、光学式などがある。さらに、本発明は、特定のＰＨＹまたは無線の種類での利用に限定されず、他の互換性のある技術にも同様に適用できる。
【００２１】
この説明の全体を通して、通信装置という用語は、媒体を介してデータを送信、受信、または送受信するよう構成されたあらゆる装置または仕組み、と定義されることに留意されたい。通信装置は、ＲＦ、無線、赤外線、光学式、有線、マイクロ波等といった、あらゆる好適な媒体を介して通信するよう構成されてよい。無線通信の場合、通信装置は、ＲＦ送信機、ＲＦ受信機、ＲＦ送受信機、またはこれらのあらゆる組み合わせを備えてよい。無線通信は、高周波通信、高指向性アンテナを介した長距離見通し内通信もしくは短距離通信などを例とするマイクロ波通信、および／または赤外線（ＩＲ）短距離通信を含む。また、応用例としては、１対１通信、１対多通信、一斉同報通信、セルラーネットワーク等の無線ネットワークを含んでよい。
【００２２】
図１および図２は、クラスタとして動作している移動ノード１２の例示的ネットワーク１０の簡略図であり、ノードどうしを接続する無線リンク１４を示している。ネットワーク１０は、ラップトップコンピュータ、携帯情報端末（ＰＤＡ）、または携帯電話といった複数の移動ノード１２を含み、複数の移動ノード１２は、当業者に理解されるように無線通信リンク１４で接続されている。リンク１４は、ネットワークにおける基本接続であり、単に任意の２つのノード１２の間の物理リンクである。ノードについて記述する情報としては、ノードＩＤ（ＩＰアドレス、ＡＴＭアドレス等）や、入手可能であれば位置情報などが含まれる。このようなネットワークは、移動アドホック無線通信システムとなり得る。このようなネットワークの例は、本発明の譲受人に譲渡された米国特許第６，７６３，０１３号および米国特許第６，７５４，１９２号、ならびに米国特許出願公開第２００５／００５３００３号および米国特許出願公開第２００４／０２０３８２０号に示されており、これらの開示は、引用することにより全体として組み込まれているものとする。
【００２３】
アドホックネットワークにおいて、クラスタは、トポロジ的に接続されたノードの群（グループ）であり、これらのノードは、群において構成員としての地位を共有する。クラスタは、１ホップまたは多数のホップに及ぶことができる。クラスタのヘッダノードは、クラスタの役に立つ特定の機能を有し、また、クラスタヘッドまたは群サーバノード（Group Server Node、ＧＳＮ）と呼ばれてよい。任意のノードがＧＳＮになってよく、ＧＳＮのノードＩＤは、群ＩＤに用いられてよい。群内にはＧＳＮが１つだけ存在するものとされ、また、現在のＧＳＮの電源が落とされた時、または現在のＧＳＮがネットワークもしくは群を離れた時は、新しいＧＳＮが選ばれるものとされる。
【００２４】
ネットワーク内のノードは局所的な知識しか有さないため、ＧＳＮを選出するのに用いられる手法は分散型の方法でなければならない。どのノードが次のＧＳＮになるべきかを裁定するために前もってノードが手動で選ばれるべきではない。ノードが入ったり離れたり、ノードの電源が落ちたり、ノードが姿を消したりするアドホックネットワークにおいては、トポロジが変化しているので、ＧＳＮ選出手法は強固である必要もある。また、例えば、非対称リンク、不安定なリンク、および／または通信接続手順の中断のために、選出されたＧＳＮが、アクセス不能になったり動作不能に見えたりする場合があるので、ＧＳＮは再選出されてよい。
【００２５】
図４を参照しさらに具体的に説明すると、ノード１２は、ＭＡＮＥＴ（移動アドホックネットワーク）内で通信することのできる、任意の好適な種類の移動装置であってよく、例えば無線通信装置２０と、当業者に理解される他の装置を含む。もちろん、必要であれば、いくつかの応用例において、いくつかのノード１２が固定通信インフラに任意に接続されてよいこともまた理解されるであろう。
【００２６】
さらに、移動ノード１２は、制御部２２を例示的に含む。以下、制御部２２の動作について説明する。制御部２２は、例えば、マイクロプロセッサ、メモリ、ソフトウェア等を用いて実装されてよく、これは当業者に理解されるであろう。また、関連付けられたメモリ２４も含まれてよい。さらに、無線通信装置２０は、例示的に示されている１つまたは複数の関連付けられたアンテナ２６だけでなく、無線モデム、無線ローカルエリアネットワーク（ＬＡＮ）装置、携帯電話装置等も含んでよい。例えば、１つ以上のフェーズドアレーアンテナが（他の好適なアンテナと同様に）用いられてもよく、これは当業者に理解されるであろう。
【００２７】
再び図１および図２を参照すると、アドホックネットワークは、現在選出されているクラスタヘッドノードＸとともにクラスタとして動作する少なくとも１群の移動ノード１２を含む。各移動ノード１２は、制御部２２および無線通信装置２０を含み、制御部２２および無線通信装置２０は、共に協働して、現在選出されているクラスタヘッドノードＸが動作不能（非アクティブ、非動作状態、inactive）に見える（判断される）かどうかを決定し、決定に基づいてトークンによるクラスタヘッドノード選出を開始する。例えば、非対称リンク、不安定なリンク、および／または通信接続手順の中断、機器の故障または過負荷との遭遇のために、現在選出されているクラスタヘッドノードＸの電源が落ちていたり、現在選出されているクラスタヘッドノードＸが、姿を消していたり、アクセス不能になっていたりする場合がある。
【００２８】
トークンによるクラスタヘッドノード選出の際、クラスタの移動ノード１２は、例えば図３に示すようなトークン１００を生成して送信する。このようなトークンは、以下に論じるそれぞれのトークン重みを有する。ノード１２は、近隣ノードからトークンを受信し、トークン重みに基づいてトークンを選択的に再送信し、トークン重みに基づいて新しいクラスタヘッドノードを選出する。
【００２９】
トークン１００は、周囲へ中継されることのできる、凝縮された小さなメッセージである。図３に示すように、トークン１００は、選出メッセージであってよく、選出メッセージは、ノードＩＤフィールド１０２と、パラメータ値フィールド１０４とを含み、パラメータ値フィールド１０４は、例えば、該当クラスタノードの近隣ノードの数を示すものである。関連付けられているトークン重みは、ノードＩＤとパラメータ値とに基づく重み値で規定されてよい。選出メッセージは、トークン１００の伝送の境界を規定する群ＩＤフィールド１０６、および／または、トークンが伝送され得る回数を規定する生存回数（時間）フィールド１０８をさらに含んでよい。例えば、トークンの重みは、ノードの近隣ノードの数を表す８ビットおよびノードＩＤを示す２４ビットといった２つのフィールドを含む３２ビットであってよい。この３２ビットの十進値が大きなものほど、そのトークンがより良いということを意味する。
【００３０】
制御部２２および無線通信装置２０は、協働して、現在選出されているクラスタヘッドノードから状態メッセージを所定の期間、受信できないことに基づいて、現在選出されているクラスタヘッドノードＸが動作不能であると決定してよい。また、制御部２２および無線通信装置２０は、協働して、現在選出されているクラスタヘッドノードから応答メッセージを傍受できないことと、現在選出されているクラスタヘッドノードへ確認要求メッセージを送ることと、現在選出されているクラスタヘッドノードから確認メッセージを受信できないこととに基づいて、現在選出されているクラスタヘッドノードＸが動作不能であると決定してもよい。
【００３１】
例えば、クラスタヘッドノードＸは、例えば２秒に１回、キープアライブ（生存維持）メッセージをクラスタノード１２へ送ってよい。もしもノードＡがある期間、キープアライブメッセージを受信できなかったら、それはクラスタヘッドノードＸがなくなったか、もはやクラスタヘッドノードとして動作することができないということを意味する。あるいは、任意のクラスタノード１２が発した要求メッセージに対して、クラスタヘッドノードＸが応答していない場合がある。応答メッセージがクラスタノードＡによって傍受されず、そこでノードＡは、特別な要求メッセージをノードＸへ発して、ノードＸが応答できるか否かを確認することになる。ノードＸが欠けていることが検出されると、ノードＡはトークンによる選出を開始する（引き起こす）。
【００３２】
現在選出されているクラスタヘッドノードＸが動作不能であるかどうかの決定は、制御部２２および無線通信装置２０が共に協働して少なくとも１つの近隣ノードの存在を決定することをさらに含んでよい。換言すると、クラスタを離れたのがノードＡ自身ではないと確認することが望ましい場合があるということである。
【００３３】
図示のように、ノードＡは、クラスタ内の近隣ノードであるノードＢ、ノードＣ、およびノードＥへ自身のトークンＴＡを送信することによって、トークンによるクラスタヘッドノード選出を開始する（図１）。しかし、図２に示すように、例えば、ノードＥの方がより多くの近隣ノードを有するという理由で、ノードＥからのトークンＴＥの方がより良い。従って、トークンＴＥが、クラスタの他のノード１２によって再送信されるトークンとなり、そして本例においては、トークンＴＥは２ホップ以内の他のクラスタノードへ中継されることになる。
【００３４】
各ノード１２の制御部２２および無線通信装置２０は協働して最良トークンを再送信する。最良トークンは、受信されたトークンで最高重み値をもつトークンと定義される。制御部２２は、最良トークンのノードＩＤをクラスタヘッドノードＩＤとして格納してもよい。
【００３５】
好ましくは、トークンは、所定の選出処理において各ノードにより１度だけ作成される。各ノードは、最初の選出トークンを受信したら、自身も自らのトークンを作成する。各ノードは異なる近隣ノードから異なるトークンを受信してよい。収集された中で、最良トークンだけが再送信されることになる。ノードは、将来の比較のため、最良トークンを保持する。また、トークンの生存回数（ＴＴＬ）フィールドがデクリメントされる。そして、最良トークンのノードＩＤが新しいクラスタヘッドノードＩＤとして用いられる。
【００３６】
図５のフローチャートを参照して、本発明による方法の種々のステップについて説明する。本発明の方法の態様は、移動アドホックネットワーク内でクラスタとして動作する一群の移動ノード１２のためのクラスタヘッドノードを選出することを指向したものである。本方法が開始すると（ブロック１２０）、本方法は、現在選出されているクラスタヘッドノードが動作不能に見えるかどうかを決定すること（ブロック１２２）と、決定に基づいて、ブロック１２４においてトークンによるクラスタヘッドノード選出を開始することとを含む。クラスタ移動ノード１２は、選出の際に、それぞれのトークン重みを有するトークン１００を生成して送信し（ブロック１２６）、近隣ノードからトークンを受信し（ブロック１２８）、トークン重みに基づいてトークンを選択的に再送信し（ブロック１３０）、トークン重みに基づいて新しいクラスタヘッドノードを選出して（ブロック１３２）、終了する（ブロック１３４）。
【００３７】
ブロック１２２において、現在選出されているクラスタヘッドノードが動作不能であると決定することは、現在選出されているクラスタヘッドノードから状態メッセージを所定の期間、受信できないことに基づいてよい。また、現在選出されているクラスタヘッドノードが動作不能であると決定することは、現在選出されているクラスタヘッドノードから応答メッセージを傍受できないことと、現在選出されているクラスタヘッドノードへ確認要求メッセージを送ることと、現在選出されているクラスタヘッドノードから確認メッセージを受信できないこととに基づいてもよい。ブロック１３０において、トークンの選択的な再送信は、受信されたトークンで最高重み値をもつものと定義される最良トークンを再送信することを含んでよい。また、ブロック１３２において、選出処理は、最良トークンのノードＩＤをクラスタヘッドノードＩＤとして格納することを含んでよい。
【００３８】
本手法は分散型の手法である。なぜなら、最初は多くの異なるトークン（ＮノードでＮトークン）が作成されてネットワーク内で循環されるが、各ノードから最良トークンだけが跳ね返されるからである。どのノードも、最良トークンを受信したら、それまでに受信した他のトークンを自動的に終了させる。
【００３９】
本手法は強固である。なぜなら、クラスタ内のすべてのノードに最良トークンが記録されることになるからである。また、各ノードは、最良トークンを受信する機会を多数回、有するであろう。本手法では、特定のノードからの特定の確認応答を必要とせず、ネットワーク内の不安定なリンクの影響が緩和される。本手法は、不安定なアドホックネットワーク環境において強固な仕組みである。また、本手法は帯域幅効率にも優れるが、これは、トークンが比較的小さいため、選出に要する帯域幅のオーバーヘッドの総計が小さいからである。
【図面の簡単な説明】
【００４０】
【図１】図１は、本発明における、トークンによるクラスタヘッドノード選出が行われているアドホックネットワークの模式的な簡略図である。
【図２】図２は、本発明における、トークンによるクラスタヘッドノード選出が行われているアドホックネットワークの模式的な簡略図である。
【図３】図３は、本発明における、トークンによるクラスタヘッドノード選出で用いられる選出トークンのフィールドの例を説明する概略図である。
【図４】図４は、図１および図２のアドホックネットワークで用いられる無線ノードの例を説明する概略的なブロック図である。
【図５】図５は、本発明によるクラスタヘッドノード選出方法のステップを示すフローチャートである。
【符号の説明】
【００４１】
１０  ネットワーク
１２  移動ノード
１４  無線リンク
２０  無線通信装置
２２  制御部
２４  メモリ
２６  アンテナ
１００  トークン
１０２  ノードＩＤフィールド
１０４  パラメータ値フィールド
１０６  群ＩＤフィールド
１０８  生存回数フィールド
【図１】
2008283674.tif 000003
【図２】
2008283674.tif 000004
【図３】
2008283674.tif 000005
【図４】
2008283674.tif 000006
【図５】
2008283674.tif 000007
【外国語明細書】
2008283674000001.pdf