JP4807701B2 - 移動端末装置、制御方法及び移動通信システム - Google Patents

Description

本発明は、アドホックネットワークを構成する移動端末装置（以下、単に「端末」ともいう）、制御方法及び移動通信システムに関する。

なお、本明細書では、「送信する」とは、ある移動端末装置がパケットを該パケットの送信起点として隣接の移動端末装置へ送信することを意味し、「転送する」とは、ある移動端末装置が、他の移動端末装置から受信したパケットを隣接の移動端末装置へ転送することを意味する。

移動通信ネットワークの基盤（インフラストラクチャ）となる設備を要せず、複数の移動端末装置のみで構成されるアドホックネットワーク（いわゆるpureアドホックネットワーク）におけるルーティングプロトコルでは、ネットワーク中の全ノードに対してリンク情報などの制御パケットを届けるフラッディングを基本としてルートの制御を行っている。そのため端末数が増加すると制御パケットが大量にネットワークに流れ、通信の帯域を圧迫することとなる。この問題を軽減する方法として、ＯＬＳＲ（Optimized Link State Routing）ではＭＰＲ（Multi Point Relay）集合を用いている（下記の非特許文献１参照）。ＯＬＳＲにおいては、各端末は自身から２ホップで接続されるすべての端末にパケットを届けるために必要な最小限の中継端末（ＭＰＲ）を１ホップで接続される端末から選択する。ある端末が、パケットをネットワーク全体にフラッディングするとき、パケットを送信した端末のＭＰＲとして選択されている端末だけがパケットを中継する。これによりパケットを送信した端末から２ホップの範囲のすべての端末にパケットを届けることが可能である。さらに、パケットを中継した端末のＭＰＲとして選定されている端末がさらに中継していくことで最終的にネットワーク全体にパケットが届けられる。このようにＯＬＳＲでは、フラッディングを効率的に行うことにより、オーバヘッドの少ないルーティングを実現している。
T.Clausen及びP.Jacquet著、Project Hipercom、「Optimized Link State Routing Protocol(OLSR)」、RFC3626、<URL:www.ietf.org/rfc/rfc3626.txt>

しかし、ＯＬＳＲでは、制御パケットのフラッディングの効率化は考慮されているが、ルーティングに必要なリンク情報の選別による最適化は考慮されていない。ＯＬＳＲでは少なくとも一つの端末にＭＰＲとして選択されている端末が、自身と自身をＭＰＲとして選択している端末との間のリンク情報をフラッディングすることで、ネットワーク全体のリンク情報を全端末に知らせ、前記リンク情報を用いてルーティングを行っている。ここでリンク情報とは、自身のＩＤと自身に隣接している端末のＩＤで構成され、前記２つのＩＤを持つ端末間にリンクがあることを示すものである。

このとき、ある２つの端末Ａ、Ｂがお互いをＭＰＲとして選択している場合、端末Ａ、Ｂはお互いのＩＤをフラッディングし合うこととなるため、端末Ａ、Ｂ間のリンク情報は重複して送信されることとなる。また、ある端末Ｃが複数の端末をＭＰＲとして選定している場合、この端末Ｃは当該複数の端末によりＩＤをフラッディングされ、実際には使われないような不必要なリンク情報も送信される。このようにＯＬＳＲでは、重複したリンク情報や、経路として使われないリンク情報なども、全端末に対し不必要に送信され、結果として、ルーティングにかかる制御パケット量が増大し、ルーティングにかかるオーバヘッドが大きくなるという課題があった。

そこで、本発明は、ルーティングにかかる制御パケット量を削減し、オーバヘッドの少ないルーティングを実現することを目的とする。

上記課題を解決するために、本発明に係る移動端末装置は、複数の移動端末装置によってアドホックネットワークが形成されている環境における当該移動端末装置であって、当該移動端末装置自身のＩＤ及び状態を含むパケットを他の移動端末装置との間で送受信することで、自身に隣接する移動端末装置のＩＤ及び状態を認識し、当該隣接する移動端末装置の状態及び自身の状態に基づいて、自身の状態をクラスタヘッド、ゲートウエイ又はメンバに設定するクラスタリング手段と、前記クラスタリング手段により認識された前記隣接する移動端末装置のＩＤ及び状態、並びに、自身の状態を保存する保存手段と、前記保存手段により保存された自身の状態がクラスタヘッドである場合に、保存された１つ以上の前記隣接する移動端末装置のＩＤと自身のＩＤとを含んで構成されるリンク情報を送信するとともに、前記保存された自身の状態がいかなる場合でも、他の移動端末装置から送信された前記リンク情報を受信するリンク情報送受信手段と、前記リンク情報送受信手段により送受信された前記リンク情報に基づいて任意の移動端末装置へのルートを求めるルーティング手段と、を具備し、前記クラスタリング手段は、クラスタヘッド同士は隣接しないことと、メンバはクラスタヘッドに隣接し且つただ１つのクラスタヘッドに属することを指定することと、クラスタヘッド間はただ１つのゲートウエイによって接続されることとを特徴とするクラスタを構成するように、自身の状態をクラスタヘッド、ゲートウエイ又はメンバに設定し、自身のＩＤと自身の状態と自身が親に指定する移動端末装置のＩＤ情報とを含む制御情報を送受信し、受信した制御情報を前記保存手段に保存し、保存した制御情報の中に状態がクラスタヘッドである移動端末装置のＩＤが存在する場合に、自身の状態をメンバに決定し、保存した制御情報の中に状態がクラスタヘッドである移動端末装置のＩＤが存在せず、ゲートウエイである移動端末装置のＩＤが存在する場合に、自身の状態をクラスタヘッドに決定し、保存した制御情報の中に状態がクラスタヘッドである移動端末装置のＩＤもゲートウエイである移動端末装置のＩＤも存在しない場合に、自身の状態をクラスタヘッドに決定し、自身の状態がメンバであり、保存した制御情報の中に状態がクラスタヘッドで自身を親に指定している移動端末装置のＩＤが存在する場合に、自身の状態をゲートウエイに変更する、ことを特徴とする。

かかる発明によれば、クラスタヘッドのみがリンク情報を送信するものの、ゲートウエイ及びメンバの各々は、自身に隣接したクラスタヘッドからリンク情報を受信できるため、各移動端末装置はリンク情報を得ることができ、当該リンク情報に基づいて任意の端末までのルートを求めることができる。このように、全ての移動端末装置がリンク情報を送信する必要はなく、クラスタヘッドのみがリンク情報を送信すればよいので、ルーティングに必要なリンク情報（送受信されるリンク情報）の量を削減することができ、制御パケット量を削減してオーバヘッドの少ないルーティングを実現することができる、という効果が得られる。

また、クラスタリング手段は、自身が親に指定している移動端末装置のＩＤが前記保存した制御情報から削除されたことを契機として、自身の状態を初期化し、前記保存した制御情報を参照し、自身が親に指定している移動端末装置の状態が初期化されたことを契機として、自身の状態を初期化することが望ましい。これにより、移動端末装置の移動にあわせてクラスタを構成することが可能となる。

また、リンク情報送受信手段は、送信されるリンク情報として、自身に隣接するゲートウエイのＩＤと、自身を親に指定しているメンバのＩＤと、自身のＩＤとを含んで構成されるリンク情報を送信することが望ましい。即ち、リンク情報送受信手段が送信するリンク情報には、自身のＩＤと全ての隣接する移動端末装置のＩＤとを含める必要はなく、(1)自身のＩＤと、(2)自身に隣接するゲートウエイのＩＤと、(3)自身に属することを指定しているメンバのＩＤとを含んだ構成とすればよく、この場合、ルーティングに必要なリンク情報のデータ量を削減できる効果が得られる。

また、リンク情報送受信手段は、保存手段により保存された自身の状態がクラスタヘッド又はゲートウエイである場合に、他の移動端末装置から受信されたリンク情報を転送することが望ましい。即ち、メンバは何れかのクラスタヘッドに隣接しているため、メンバがリンク情報を転送せずとも、クラスタヘッドと、クラスタヘッド間を接続するゲートウエイとがリンク情報を転送すれば、全ての移動端末装置がリンク情報を受信することができる。従って、この場合、リンク情報を全ての移動端末装置に伝送するために必要な中継回数を削減できる効果が得られる。

さらに、移動端末装置に関する本発明は、以下のように制御方法に係る発明として記述することができ、制御方法に係る発明は、同様の作用・効果を奏する。

即ち、本発明に係る制御方法は、複数の移動端末装置によってアドホックネットワークが形成されている環境における当該移動端末装置にて実行される制御方法であって、当該移動端末装置自身のＩＤ及び状態を含むパケットを他の移動端末装置との間で送受信することで、自身に隣接する移動端末装置のＩＤ及び状態を認識し、当該隣接する移動端末装置の状態及び自身の状態に基づいて、自身の状態をクラスタヘッド、ゲートウエイ又はメンバに設定するクラスタリングステップと、前記クラスタリングステップにて認識された前記隣接する移動端末装置のＩＤ及び状態、並びに、自身の状態を保存する保存ステップと、前記保存ステップにて保存された自身の状態がクラスタヘッドである場合に、保存された１つ以上の前記隣接する移動端末装置のＩＤと自身のＩＤとを含んで構成されるリンク情報を送信するとともに、前記保存された自身の状態がいかなる場合でも、他の移動端末装置から送信された前記リンク情報を受信するリンク情報送受信ステップと、前記リンク情報送受信ステップにて送受信された前記リンク情報に基づいて任意の移動端末装置へのルートを求めるルーティングステップと、を有し、前記クラスタリングステップでは、当該移動端末装置が、クラスタヘッド同士は隣接しないことと、メンバはクラスタヘッドに隣接し且つただ１つのクラスタヘッドに属することを指定することと、クラスタヘッド間はただ１つのゲートウエイによって接続されることとを特徴とするクラスタを構成するように、自身の状態をクラスタヘッド、ゲートウエイ又はメンバに設定し、自身のＩＤと自身の状態と自身が親に指定する移動端末装置のＩＤ情報とを含む制御情報を送受信し、受信した制御情報を保存し、保存した制御情報の中に状態がクラスタヘッドである移動端末装置のＩＤが存在する場合に、自身の状態をメンバに決定し、保存した制御情報の中に状態がクラスタヘッドである移動端末装置のＩＤが存在せず、ゲートウエイである移動端末装置のＩＤが存在する場合に、自身の状態をクラスタヘッドに決定し、保存した制御情報の中に状態がクラスタヘッドである移動端末装置のＩＤもゲートウエイである移動端末装置のＩＤも存在しない場合に、自身の状態をクラスタヘッドに決定し、自身の状態がメンバであり、保存した制御情報の中に状態がクラスタヘッドで自身を親に指定している移動端末装置のＩＤが存在する場合に、自身の状態をゲートウエイに変更する、ことを特徴とする。

本発明は、トポロジ管理装置と複数の移動端末装置とを含んで構成される移動通信システムに係る発明として捉えることもできる。即ち、本発明に係る移動通信システムは、移動端末装置のＩＤと前記移動端末装置に隣接する１つ以上の移動端末装置のＩＤとを含んで構成されるリンク情報を受信するリンク情報受信手段と、前記リンク情報に基づいて、複数の移動端末装置間の通信を行うための中継となるべき移動端末装置のＩＤのリストを求め、当該リストを当該通信の起点の移動端末装置に提供するリスト提供手段とを具備するトポロジ管理装置と、特許請求の範囲の請求項１に記載された移動端末装置の複数台とを含んで構成されることを特徴とする。

トポロジ管理装置と複数の移動端末装置とを含んで構成される移動通信システムにおける制御方法であって、各移動端末装置が、当該移動端末装置自身のＩＤ及び状態を含むパケットを他の移動端末装置との間で送受信することで、自身に隣接する移動端末装置のＩＤ及び状態を認識し、当該隣接する移動端末装置の状態及び自身の状態に基づいて、自身の状態をクラスタヘッド、ゲートウエイ又はメンバに設定するクラスタリングステップと、各移動端末装置が、前記クラスタリングステップにて認識された前記隣接する移動端末装置のＩＤ及び状態、並びに、自身の状態を保存する保存ステップと、各移動端末装置が、前記保存ステップにて保存された自身の状態がクラスタヘッドである場合に、保存された１つ以上の前記隣接する移動端末装置のＩＤと自身のＩＤとを含んで構成されるリンク情報を前記トポロジ管理装置へ送信するリンク情報送信ステップと、前記トポロジ管理装置が、前記リンク情報を受信するリンク情報受信ステップと、前記トポロジ管理装置が、受信した前記リンク情報に基づいて、複数の移動端末装置間の通信を行うための中継となるべき移動端末装置のＩＤのリストを求め、当該リストを当該通信の起点の移動端末装置に提供するリスト提供ステップと、を有し、前記クラスタリングステップでは、各移動端末装置が、クラスタヘッド同士は隣接しないことと、メンバはクラスタヘッドに隣接し且つただ１つのクラスタヘッドに属することを指定することと、クラスタヘッド間はただ１つのゲートウエイによって接続されることとを特徴とするクラスタを構成するように、自身の状態をクラスタヘッド、ゲートウエイ又はメンバに設定し、自身のＩＤと自身の状態と自身が親に指定する移動端末装置のＩＤ情報とを含む制御情報を送受信し、受信した制御情報を保存し、保存した制御情報の中に状態がクラスタヘッドである移動端末装置のＩＤが存在する場合に、自身の状態をメンバに決定し、保存した制御情報の中に状態がクラスタヘッドである移動端末装置のＩＤが存在せず、ゲートウエイである移動端末装置のＩＤが存在する場合に、自身の状態をクラスタヘッドに決定し、保存した制御情報の中に状態がクラスタヘッドである移動端末装置のＩＤもゲートウエイである移動端末装置のＩＤも存在しない場合に、自身の状態をクラスタヘッドに決定し、自身の状態がメンバであり、保存した制御情報の中に状態がクラスタヘッドで自身を親に指定している移動端末装置のＩＤが存在する場合に、自身の状態をゲートウエイに変更する、ことを特徴とする。

上記の移動通信システムに係る発明及び制御方法に係る発明では、クラスタヘッドのみがリンク情報をトポロジ管理装置へ送信し、トポロジ管理装置が、受信したリンク情報に基づいて、複数の移動端末装置間の通信を行うための中継となるべき移動端末装置のＩＤのリストを求め、当該リストを当該通信の起点の移動端末装置に提供する。これにより、通信の起点の移動端末装置は、中継となるべき移動端末装置のＩＤのリストを得ることができるため、該リストに基づいてルーティングを行うことができる。この場合、トポロジ管理装置へのリンク情報の送信は、全ての移動端末装置でなく、クラスタヘッドのみが行うので、ルーティングに必要なリンク情報（送受信されるリンク情報）の量を削減することができ、制御パケット量を削減してオーバヘッドの少ないルーティングを実現することができる、という効果が得られる。

本発明によれば、全ての移動端末装置がリンク情報を送信する必要はなく、クラスタヘッドのみがリンク情報を送信すればよいので、ルーティングに必要なリンク情報（送受信されるリンク情報）の量を削減することができ、制御パケット量を削減してオーバヘッドの少ないルーティングを実現することができる、という効果が得られる。

（第１実施形態）
図１乃至図７を参照して、本発明の第１実施形態に係る移動通信システムの構成について説明する。図１に示すように、本実施形態に係る移動通信システム１０は、複数の移動端末装置ＭＴ＃１乃至ＭＴ＃９を具備している。移動端末装置ＭＴ＃１乃至ＭＴ＃９はすべて同様の構成で、同様の機能を持つが、クラスタヘッド、ゲートウエイ、メンバという３つの状態のうち何れか１つの状態となる。各移動端末装置の状態は、固定的ではなく、他の端末との相対的な位置関係により動的に変化する。移動通信システム１０における各移動端末装置の状態は以下の条件を満たすように動的に決定される。
１.ゲートウエイ同士は隣接しない。
２.メンバはクラスタヘッドに隣接し、隣接するクラスタヘッドの中の１つを指定する。
３.クラスタヘッド間はただ１つのゲートウエイによって接続される。

図１の例では、ＭＴ＃３及びＭＴ＃７がクラスタヘッド、ＭＴ＃５がゲートウエイ、ＭＴ＃１、ＭＴ＃２、ＭＴ＃４、ＭＴ＃６、ＭＴ＃８、ＭＴ＃９がメンバとして構成されている。なお、図１では移動端末装置の数は９であるが、上記移動端末装置の状態に関する３つの条件を満たすならば、移動端末装置の数に制限はない。

本実施形態において、クラスタヘッドは、自己の移動端末装置（以下「自身」と称する）に隣接している端末との間のリンク情報を送信する。また、クラスタヘッド又はゲートウエイは、他のクラスタヘッドによって送信されたリンク情報を受信した場合に、受信したリンク情報を転送する。これにより、ネットワーク中の全端末がルーティングに必要なリンク情報を知ることができる。ここで「リンク情報」とは、例えば図１６のように、(1)自身のＩＤと、(2)自身に隣接している１つ以上の端末のＩＤとで構成され、(1)(2)のＩＤを持つ端末間にリンクが存在することを示すものである。例えば、自身のＩＤがＭＴ＃５で、隣接端末のＩＤがＭＴ＃３とＭＴ＃７である場合は、ＭＴ＃５とＭＴ＃３の間と、ＭＴ＃５とＭＴ＃７の間に、それぞれリンクが存在することを示す。

本実施形態にかかる移動端末装置ＭＴ＃１乃至ＭＴ＃９（以下「移動端末装置２０」と総称する）の構成について説明する。図２は本実施形態にかかる移動端末装置２０の機能ブロック構成を示す。移動端末装置２０は、Helloパケット送受信部２１と、リンク情報送受信部２２と、中継判断部２３と、データ送受信部２４と、クラスタリング部２５とルーティング部２６と、隣接端末リスト保存部２７と、状態保存部２８と、トポロジ情報保存部２９と、ルーティングテーブル保存部２１０とを具備している。以下、各構成部について順に説明する。

隣接端末リスト保存部２７は図４のような隣接端末テーブル２７Ａを保持する。隣接端末テーブル２７Ａには、隣接端末ＩＤ、親ＩＤ、当該隣接端末の状態、及び、当該隣接端末が木を構成するかどうかの情報が含まれる。

状態保存部２８は図７のような状態保存テーブル２８Ａを保持する。状態保存テーブル２８Ａには、移動端末装置２０の状態、親ＩＤの情報が含まれる。

ルーティングテーブル保存部２１０は、図６のようなルーティングテーブル２１０Ａを保持する。ルーティングテーブル２１０Ａには、自身以外の端末のＩＤと、当該自身以外の端末に通信パケットを送信する際、中継となる隣接端末のＩＤ(Next Hop)とを含む。

トポロジ情報保存部２９は、図５のようなトポロジテーブル２９Ａを保持する。トポロジテーブル２９Ａには、リンク情報を送信したクラスタヘッドのＩＤと、当該クラスタヘッドに隣接する端末のＩＤとが含まれる。また、トポロジ情報保存部２９は、トポロジテーブル２９Ａを参照し、ルーティングテーブル２１０Ａを作成し、ルーティングテーブル保存部２１０に保存するように構成される。トポロジテーブル２９Ａからルーティングテーブル２１０Ａを求める方法は、例えば、ダイクストラ法などがある。

Helloパケット送受信部２１は、定期的にHelloパケットを送信、又は他の端末からのHelloパケットを受信するように構成される。Helloパケット送受信部２１は自身のＩＤと自身の状態と自身の親となる端末のＩＤとをHelloパケットに入れて定期的にブロードキャスト送信する。ここで「ブロードキャスト」とは、あて先端末を定めず、送信パケットを受信可能な端末すべてが受信する通信形態のことをいう。端末の状態はクラスタヘッド（Ｈ）とゲートウエイ（Ｇ）とメンバ（Ｍ）と状態なし（−）の４種類存在する。また、Helloパケット送受信部２１は、他の端末が送信したHelloパケットを受信し、他の端末のＩＤと該他の端末の状態と該他の端末の親端末のＩＤとを隣接端末リスト保存部２７内の隣接端末テーブル２７Ａに保存する。このようにすることで、各移動端末装置２０は、自身に隣接する端末の存在と、当該隣接する端末の状態と、当該隣接する端末が指定する親端末のＩＤとを把握することができる。

リンク情報送受信部２２は、定期的にリンク情報をフラッディング、他の端末が送信したリンク情報を受信、又は、他の端末から受信したリンク情報を転送するように構成される。ここで「フラッディング」とは、複数の端末同士が他の端末の送信したパケットを転送し合うことで、すべての端末にパケットを届ける通信形態をいう。リンク情報送受信部２２は、状態保存部２８内の状態保存テーブル２８Ａを参照し、自身の状態がクラスタヘッドである場合に、隣接端末リスト保存部２７内の隣接端末テーブル２７Ａを参照して、木を構成しているリンク情報をフラッディングする。ここで、「木」とは、すべての端末を頂点とし、クラスタヘッドとゲートウエイの間のリンクと、メンバとメンバが親に指定するクラスタヘッドとの間のリンクとを、辺とするトポロジのことを言う。このとき、メンバが複数のクラスタヘッドと隣接している場合は、ただ１つのクラスタヘッドとの間のリンクだけが木の要素となるように構成される。例えば、図１の場合、木は、端末ＭＴ＃１〜ＭＴ＃９の９つの端末と、これら端末間を結ぶリンクＭＴ＃１−ＭＴ＃３、ＭＴ＃２−ＭＴ＃３、ＭＴ＃３−ＭＴ＃４、ＭＴ＃３−ＭＴ＃５、ＭＴ＃５−ＭＴ＃７、ＭＴ＃６−ＭＴ＃７、ＭＴ＃７−ＭＴ＃８、ＭＴ＃７−ＭＴ＃９の８つのリンクから構成される。即ち、リンクＭＴ＃２−ＭＴ＃５、ＭＴ＃４−ＭＴ＃５、ＭＴ＃５−ＭＴ＃６、ＭＴ＃５−ＭＴ＃８という４つのリンクは、実際に存在はしているが、木には含まれない。リンクが木に含まれるかどうかは、図４の隣接端末テーブル２７Ａで管理される。隣接端末テーブル２７Ａにおいて、木の構成エントリが「Ｙ」の場合、該当リンクは木に含まれ、一方、木の構成エントリが「Ｎ」の場合、該当リンクは木に含まれない。また、リンク情報送受信部２２は、他の端末からのリンク情報を受信すると、リンク情報をトポロジ情報保存部２９内のトポロジテーブル２９Ａに保存する。また、リンク情報送受信部２２は、受信したリンク情報を転送するかどうかを中継判断部２３に問い合わせる。リンク情報送受信部２２は、中継判断部２３から中継指示があった場合、受信したリンク情報を転送する。

中継判断部２３は、リンク情報送受信部２２からリンク情報を転送するかどうか問い合わせがあった場合、状態保存部２８内の状態保存テーブル２８Ａを参照し、自身の状態がクラスタヘッド又はゲートウエイの場合にリンク情報送受信部２２に転送指示を出すように構成される。ただし、自身の状態がクラスタヘッド又はゲートウエイの場合であっても、過去に受信したリンク情報と同一のリンク情報の場合には、転送指示を出さない。

データ送受信部２４は、端末間で行われるデータ通信や音声通話などの通信パケットをユニキャストで送信、受信、又は転送するように構成される。ここで「ユニキャスト」とは、通信相手端末を指定し、指定した通信相手端末にのみパケットを届ける通信形態である。データ送受信部２４は、通信パケットを送信する場合、あて先端末に通信パケットを届けるための中継端末となる隣接端末のＩＤをルーティング部２６に問い合わせ、当該ＩＤの端末に通信パケットを送信する。データ送受信部２４は他の端末から通信パケットを受信したとき、受信した通信パケットを転送する隣接端末のＩＤをルーティング部２６に問い合わせる。ルーティング部２６からＩＤの回答があった場合、当該ＩＤの端末に通信パケットを転送する。

クラスタリング部２５は隣接端末リスト保存部２７内の隣接端末テーブル２７Ａを参照し、自身の状態と木を構成する端末とを決定し、自身の状態を状態保存部２８内の状態保存テーブル２８Ａに保存し、木を構成する端末を隣接端末リスト保存部２７内の隣接端末テーブル２７Ａに保存するように構成される。移動端末装置２０が新たにネットワークに参加するとき、隣接端末テーブル２７Ａに保存されている端末の中に、一つ又は複数のクラスタヘッドが存在する場合、クラスタリング部２５は、当該クラスタヘッドの中の一つを、木を構成する端末として隣接端末テーブル２７Ａに保存、親として状態保存テーブル２８Ａに保存し、自身の状態をメンバに決定しメンバとして状態保存テーブル２８Ａに保存する。また、隣接端末テーブル２７Ａに保存されている端末の中に、クラスタヘッドが存在せず、一つ又は複数のゲートウエイが存在する場合、クラスタリング部２５は、当該ゲートウエイの中の一つを、木を構成する端末として隣接端末テーブル２７Ａに保存、親として状態保存テーブル２８Ａに保存し、自身の状態をクラスタヘッドに決定しクラスタヘッドとして状態保存テーブル２８Ａに保存する。さらに、隣接端末テーブル２７Ａに保存されている端末の中にはメンバしか存在しない場合、クラスタリング部２５は当該メンバの一つを、木を構成する端末として、隣接端末テーブル２７Ａに保存、親として状態保存テーブル２８Ａに保存し、自身の状態をクラスタヘッドに決定しクラスタヘッドとして状態保存テーブル２８Ａに保存する。そして、自身の状態がメンバ(M)である場合であって、隣接端末テーブル２７Ａに保存されている端末の中に状態がクラスタヘッド(H)でかつ自身を親として指定している端末が存在する場合、クラスタリング部２５は、自身の状態をゲートウエイに変更しゲートウエイとして状態保存テーブル２８Ａに保存する。また、クラスタリング部２５は、自身が親に指定している端末のＩＤが削除されたことを契機として自身の状態を初期化する。さらに、クラスタリング部２５は、状態保存テーブル２８Ａを参照し、自身が親に指定している端末の状態が初期化されたことを契機として、自身の状態を初期化する。以上のようなクラスタリング部２５の動作により、(1)ゲートウエイ同士は隣接しない、(2)メンバはヘッドに隣接する、(3)クラスタヘッド間はただ１つのゲートウエイによって接続される、という特徴をもつトポロジ（クラスタ）が形成される。

本実施形態においては、クラスタリング部２５の動作は、クラスタを構成するための一例であり、他の動作によってクラスタを構成してもよい。

ルーティング部２６はデータ送受信部２４の要求を受け、ルーティングテーブル保存部２１０内のルーティングテーブル２１０Ａを参照することにより、通信パケットを中継する隣接端末のＩＤをデータ送受信部２４に通知するように構成される。ルーティング部２６は通信パケットのあて先端末のNextHopのＩＤをデータ送受信部２４に通知する。

なお、図２のHelloパケット送受信部２１及びクラスタリング部２５は、本発明に係るクラスタリング手段に対応し、隣接端末リスト保存部２７及び状態保存部２８は、本発明に係る保存手段に対応する。また、リンク情報送受信部２２及び中継判断部２３は、本発明に係るリンク情報送受信手段に対応し、ルーティング部２６、トポロジ情報保存部２９及びルーティングテーブル保存部２１０は、本発明に係るルーティング手段に対応する。

次に、本実施形態にかかる移動端末装置２０のハードウェア構成について図３を用いて説明する。移動端末装置２０はＣＰＵ３１、メモリ３２、及びネットワークインタフェース３３を含んで構成される。図２におけるHelloパケット送受信部２１はＣＰＵ３１及びネットワークインタフェース３３により実現される。リンク情報送受信部２２は、ＣＰＵ３１及びネットワークインタフェース３３により実現される。中継判断部２３はＣＰＵ３１により実現される。データ送受信部２４はＣＰＵ３１及びネットワークインタフェース３３により実現される。クラスタリング部２５はＣＰＵ３１により実現される。ルーティング部２６はＣＰＵ３１により実現される。隣接端末リスト保存部２７はメモリ３２により実現される。状態保存部２８はメモリ３２により実現される。トポロジ情報保存部２９はＣＰＵ３１及びメモリ３２により実現される。ルーティングテーブル保存部２１０はメモリ３２により実現される。

続いて、本実施形態にかかる移動端末装置の動作について図８乃至図１５を用いて説明する。以下では、移動端末装置の動作として、(1)クラスタ構成時の動作、(2)リンク情報送信時の動作、(3)通信パケット送信時の動作の３つについて順に説明する。

まず、(1)クラスタ構成時の移動端末装置の動作について図１１を用いて説明する。移動端末装置２０は、移動通信システム１０に参加すると定期的にHelloパケットを送信するため、他の端末からのHelloパケットを受信することとなる。移動端末装置２０は、他の端末からのHelloパケットを受信すると（Ｓ１１１）、図１１の処理を開始し、まず、受信したHelloパケットにより隣接端末テーブル２７Ａを更新する（Ｓ１１２）。このときHelloパケットには、Helloパケットを送信した端末のＩＤ、状態、親となる端末のＩＤが含まれており、それぞれ隣接端末テーブル２７Ａの隣接端末ＩＤ、状態、親ＩＤエントリに追加する。隣接端末ＩＤエントリに同一ＩＤが存在する場合は、該当端末の状態及び親ＩＤエントリを更新するのみである。また、一度、隣接端末テーブル２７Ａの隣接端末ＩＤエントリに書き込まれた端末から一定時間Helloパケットを受信しなかった場合は、隣接端末テーブル２７Ａから該当端末のエントリを削除する。このとき、状態保存テーブル２８Ａを参照し、親として指定している端末が隣接端末テーブル２７Ａから削除された場合、自身の状態をクラスタヘッドでもゲートウエイでもメンバでもないとし、自身の状態「なし（−）」および、親ＩＤ「なし（−）」を状態保存テーブル２８Ａに保存する。また、隣接端末テーブル２７Ａにおいて、親として指定している端末の状態が「なし（−）」に変更された場合、自身の状態をクラスタヘッドでもゲートウエイでもメンバでもないとし、自身の状態「なし（−）」および、親ＩＤ「なし（−）」を状態保存テーブル２８Ａに保存する。このように状態保存テーブル２８Ａを更新(初期化)することにより、移動などによりトポロジが変化したときに、再度自身の状態を決定でき、新たにクラスタを構成できる。

そして移動端末装置20は、状態保存テーブル２８Ａを参照し、自身の状態を判定する(S1112)。自身の状態がクラスタヘッド(H)またはゲートウエイ(G)である場合、隣接端末テーブル２７Ａを参照し、自身を親として指定している端末を木を構成する端末に指定し、隣接端末テーブル２７Ａの該当端末の「木の構成」欄を「Y」に変更する(s1115)。自身の状態がメンバ(M)である場合、隣接端末テーブル２７Ａを参照し、隣接端末の中に状態がヘッド(H)でかつ自身を親に指定している(親ＩＤエントリが自身のＩＤ)端末が存在するかどうか確認する(S1113)。前記端末が存在しない場合、処理を終了する。前記端末が存在する場合、自身はクラスタヘッドになる(S1114)。このとき、クラスタリング部２５は、自身の状態「クラスタヘッド(H)」を状態保存テーブル２８Ａに保存する。

自身の状態がなしの場合、移動端末装置２０は、自身の状態を決定するため、隣接端末テーブル２７Ａを参照し、隣接端末テーブル２７Ａにエントリが存在するか否かを判断する（Ｓ１１３）。ここで、隣接端末テーブル２７Ａにエントリが存在しない場合、自身以外に移動端末装置が存在しないということであるため、自身はクラスタヘッドになる（Ｓ１１４）。このとき、クラスタリング部２５は、自身の状態「クラスタヘッド（Ｈ）」を状態保存テーブル２８Ａに保存する。

一方、Ｓ１１３で隣接端末テーブル２７Ａにエントリが存在するとき、当該エントリ内の隣接端末の中にクラスタヘッドが存在するか否かを確認する（Ｓ１１５）。ここでクラスタヘッドが存在する場合、自身はメンバとなり（Ｓ１１６）、存在するクラスタヘッドのうちの１つの端末を、木を構成する端末として指定する（Ｓ１１７）。クラスタヘッドのうち1つを選択する方法は、ＩＤが最も小さいものを選択してもよいし、ＩＤが最も大きいものを選択してもよいし、ランダムに選択してもよいし、通信が最も安定しているものを選択してもよい。このとき、クラスタリング部２５は、自身の状態「メンバ（Ｍ）」および、親ＩＤとして上記1つの端末のＩＤを状態保存テーブル２８Ａに保存するとともに、隣接端末テーブル２７Ａにおける上記１つの端末に関する「木の構成」欄を「Ｙ」に設定する。

一方、Ｓ１１５で隣接端末テーブル２７Ａにクラスタヘッドが存在しないとき、上記エントリ内の隣接端末の中にゲートウエイが存在するか否かを確認する（Ｓ１１８）。ここでゲートウエイが存在する場合、自身はクラスタヘッドとなり（Ｓ１１９）、存在するゲートウエイのうち１つを、木を構成する端末として指定する（Ｓ１１１０）。ゲートウエイのうち1つを選択する方法は、ＩＤが最も小さいものを選択してもよいし、ＩＤが最も大きいものを選択してもよいし、ランダムに選択してもよいし、通信が最も安定しているものを選択してもよい。このとき、クラスタリング部２５は、自身の状態「クラスタヘッド（Ｈ）」および、親ＩＤとして上記ゲートウエイのうちひとつの端末のＩＤを状態保存テーブル２８Ａに保存するとともに、隣接端末テーブル２７Ａにおける上記ゲートウエイのうち１つに関する「木の構成」欄を「Ｙ」に設定する。

一方、Ｓ１１８で隣接端末テーブル２７Ａにゲートウエイが存在しないとき、自身はクラスタヘッドとなり（Ｓ１１１１）、存在するメンバの一つを、木を構成する端末に指定する。メンバのうち1つを選択する方法は、ＩＤが最も小さいものを選択してもよいし、ＩＤが最も大きいものを選択してもよいし、ランダムに選択してもよいし、通信が最も安定しているものを選択してもよい。このとき、クラスタリング部２５は、自身の状態「クラスタヘッド（Ｈ）」および、親ＩＤとして上記1つのメンバのうちひとつの端末ＩＤを隣接端末テーブル２７Ａに保存し、状態保存テーブル２８Ａにおける上記指定したメンバに関する「木の構成」欄を「Ｙ」にする。

次に、クラスタ構成時の移動通信システム全体の動作シーケンスについて図８を用いて説明する。ここでは、ＭＴ＃３、ＭＴ＃１、ＭＴ＃２、ＭＴ＃４、ＭＴ＃５、ＭＴ＃７、ＭＴ＃６、ＭＴ＃８、ＭＴ＃９の順にネットワークに参加する場合を例に説明する。

まず、ＭＴ＃３がネットワークに参加する。ＭＴ＃３は定期的にHelloパケットを送信するが、この時点では他に端末は存在しないので、隣接端末テーブル２７Ａにエントリは存在しない。そのためＭＴ＃３のクラスタリング部２５は状態保存テーブル２８Ａに、自身がクラスタヘッド（Ｈ）、親ＩＤがなし（−）であることを保存する（Ｓ８１）。

次に、ＭＴ＃１がネットワークに参加する。ＭＴ＃１はＭＴ＃３との間でHelloパケットを交換し（Ｓ８２）、ＭＴ＃１内の隣接端末テーブル２７ＡにはＭＴ＃３が登録される。このときＭＴ＃３はクラスタヘッドであるため、ＭＴ＃１のクラスタリング部２５は、ＭＴ＃１内の状態保存テーブル２８Ａに、自身の状態としてメンバ（Ｍ）、親ＩＤとしてＭＴ＃３を保存し、隣接端末テーブル２７Ａ内のＭＴ＃３に関する木の構成エントリを「Ｙ」に設定する（Ｓ８３）。他方、ＭＴ＃３内の隣接端末テーブル２７ＡにはＭＴ＃１が登録され、ＭＴ＃３のクラスタリング部２５は、隣接端末テーブル２７Ａ内のＭＴ＃１に関する木の構成エントリを「Ｙ」に設定する。これにより、この時点で、ＭＴ＃３がクラスタヘッドで、ＭＴ＃１がメンバであるクラスタが構成される。

次に、ＭＴ＃２がネットワークに参加する。ＭＴ＃２はＭＴ＃３との間でHelloパケットを交換し（Ｓ８４）、ＭＴ＃２内の隣接端末テーブル２７ＡにはＭＴ＃３が登録される。このときＭＴ＃３はクラスタヘッドであるため、ＭＴ＃２のクラスタリング部２５は、ＭＴ＃２内の状態保存テーブル２８Ａに、自身の状態としてメンバ（Ｍ）、親ＩＤとしてＭＴ＃３を保存し、隣接端末テーブル２７Ａ内のＭＴ＃３に関する木の構成エントリを「Ｙ」に設定する（Ｓ８５）。他方、ＭＴ＃３内の隣接端末テーブル２７ＡにはＭＴ＃２が登録され、ＭＴ＃３のクラスタリング部２５は、隣接端末テーブル２７Ａ内のＭＴ＃２に関する木の構成エントリを「Ｙ」に設定する。これにより、この時点で、ＭＴ＃３がクラスタヘッドで、ＭＴ＃１及びＭＴ＃２がメンバであるクラスタが構成される。

次に、ＭＴ＃４がネットワークに参加し、上記と同様の処理により、ＭＴ＃３がクラスタヘッドで、ＭＴ＃１、ＭＴ＃２及びＭＴ＃４がメンバであるクラスタが構成される（Ｓ８６〜Ｓ８７）。

次に、ＭＴ＃５がネットワークに参加する。ＭＴ＃５はＭＴ＃２、ＭＴ＃３、ＭＴ＃４と隣接しているため、ＭＴ＃２、ＭＴ＃３、ＭＴ＃４の各々との間でHelloパケットを交換する（Ｓ８８）。これにより、ＭＴ＃５内の隣接端末テーブル２７ＡにはＭＴ＃２、ＭＴ＃３、ＭＴ＃４が登録される。この時点ではＭＴ＃３がクラスタヘッドであるため、ＭＴ＃５はメンバとなり（Ｓ８９）、ＭＴ＃３がクラスタヘッドで、ＭＴ＃１、ＭＴ＃２、ＭＴ＃４、ＭＴ＃５がメンバであるクラスタが構成される。

次に、ＭＴ＃７がネットワークに参加する。ＭＴ＃７は、隣接するＭＴ＃５との間でHelloパケットを交換し（Ｓ８１０）、ＭＴ＃７内の隣接端末テーブル２７ＡにはＭＴ＃５が登録される。この時点でＭＴ＃５はメンバであるため、ＭＴ＃７のクラスタリング部２５は、ＭＴ＃７内の状態保存テーブル２８Ａに自身の状態として「クラスタヘッド（H）」、親ＩＤとしてＭＴ＃５を保存し、隣接端末テーブル２７Ａ内のＭＴ＃５に関する木のエントリを「Ｙ」に、ＭＴ＃５に関する状態を「ゲートウエイ（Ｇ）」に設定する（Ｓ８１１）。他方、ＭＴ＃５内の隣接端末テーブル２７ＡにはＭＴ＃７が登録され、ＭＴ＃５のクラスタリング部２５は、ＭＴ＃５内の隣接端末テーブル２７ＡのＭＴ＃７に関する木の構成エントリを「Ｙ」に、状態保存テーブル２８Ａ内の自身の状態エントリを「ゲートウエイ（Ｇ）」に設定する。これにより、ＭＴ＃５の状態はメンバからゲートウエイに変わることとなる（Ｓ８１２）。この時点で、ＭＴ＃３、ＭＴ＃７がクラスタヘッドで、ＭＴ＃５がゲートウエイで、ＭＴ＃１、ＭＴ＃２、ＭＴ＃４がメンバであるクラスタが構成される。

その後、ＭＴ＃６、ＭＴ＃８、ＭＴ＃９が順次、ネットワークに参加し、同様の処理が行われることにより、最終的に、ＭＴ＃３、ＭＴ＃７がクラスタヘッドで、ＭＴ＃５がゲートウエイで、ＭＴ＃１、ＭＴ＃２、ＭＴ＃４、ＭＴ＃６、ＭＴ＃８、ＭＴ＃９がメンバであるクラスタが構成される（Ｓ８１３〜Ｓ８１８）。

次に、(2)リンク情報送信時の動作（リンク情報の送信方法）について説明する。なお、リンク情報の送信は上記クラスタの構成を利用することを特徴としている。具体的には、クラスタヘッドが、隣接する端末との間のリンク情報を送信し、クラスタヘッドとゲートウエイのみが上記リンク情報を転送することで、ルーティングに必要なルート情報を全端末に送信することを実現する。

最初に、リンク情報送信時の移動端末装置２０の動作について図１２を用いて説明する。まず、移動端末装置２０は、状態保存テーブル２８Ａを参照することで、自身がクラスタヘッドであるか否かを確認する（Ｓ１２１）。リンク情報はクラスタヘッドのみが送信するため、Ｓ１２１で自身がクラスタヘッドでない場合は、処理を終了する。一方、Ｓ１２１で自身がクラスタヘッドである場合は、リンク情報を生成し（Ｓ１２２）、生成したリンク情報を送信して（Ｓ１２３）、処理を終了する。

なお、Ｓ１２２のリンク情報の生成時には、隣接端末テーブル２７Ａを参照し、隣接する端末全てをリスト化してリンク情報を生成してもよいし、隣接する端末の中で木の構成エントリが「Ｙ」となっているものだけをリスト化してリンク情報を生成してもよい。このうち、木の構成エントリが「Ｙ」となっているものだけをリスト化してリンク情報を生成する場合は、隣接する端末全てをリスト化する必要がないため、リンク情報のデータ量をさらに削減することができる、という更なる効果が得られる。

次に、リンク情報を転送する際の移動端末装置２０の動作について図１３を用いて説明する。移動端末装置２０は、他の端末からのリンク情報を受信すると（Ｓ１３１）、図１３の処理を開始し、上記受信したリンク情報をトポロジテーブル２９Ａに保存する（Ｓ１３２）。そして、移動端末装置２０は、上記受信したリンク情報が、以前に受信したことがあるか否かを判断する（Ｓ１３３）。ここで、上記受信したリンク情報が、以前に受信したことがある場合は、リンク情報を転送せずに処理を終える。一方、Ｓ１３３で、上記受信したリンク情報が、以前に受信したことがない場合は、状態保存テーブル２８Ａを参照することで、自身がクラスタヘッド又はゲートウエイであるか否かを確認する（Ｓ１３４）。自身がクラスタヘッド又はゲートウエイである場合は、上記受信したリンク情報を転送する（Ｓ１３５）。一方、Ｓ１３４で、自身がクラスタヘッドでもゲートウエイでもなくメンバである場合は、リンク情報を転送せずに処理を終える。以上のように、移動端末装置２０は、自身がクラスタヘッド又はゲートウエイである場合のみ、上記受信したリンク情報を転送する。

次に、リンク情報送信時の移動通信システム全体の動作シーケンスについて図９を用いて説明する。

クラスタヘッドであるＭＴ＃３のリンク情報送受信部２２は、定期的にリンク情報を送信する。ＭＴ＃３のリンク情報送受信部２２は、まず、ＭＴ＃３内の隣接端末テーブル２７Ａを参照し、木の構成エントリが「Ｙ」である隣接端末ＩＤをリストにする。この場合、ＭＴ＃１、ＭＴ＃２、ＭＴ＃４、ＭＴ＃５がリストに挙げられる。次に、上記リストに自身のＩＤ（ＭＴ＃３）を加えたものをリンク情報としてブロードキャストで送信する（Ｓ９１）。

送信されたリンク情報は、ＭＴ＃３に隣接するＭＴ＃１、ＭＴ＃２、ＭＴ＃４、ＭＴ＃５により受信される。

ここで、メンバであるＭＴ＃１、ＭＴ＃２、ＭＴ＃４のリンク情報送受信部２２は、リンク情報を自端末内のトポロジテーブル２９Ａに保存する。この場合、クラスタヘッドのＩＤ（ＭＴ＃３）、及び当該クラスタヘッドに隣接する端末のＩＤ（ＭＴ＃１、ＭＴ＃２、ＭＴ＃４、ＭＴ＃５）がトポロジテーブル２９Ａに保存される。さらに、メンバであるＭＴ＃１、ＭＴ＃２、ＭＴ＃４のリンク情報送受信部２２は、受信したリンク情報を中継するか否かを自端末内の中継判断部２３に問い合わせる。問合せを受けた中継判断部２３は、状態保存テーブル２８Ａを参照する。この場合、状態保存テーブル２８Ａのエントリは「メンバ（Ｍ）」となっているので、中継判断部２３は、リンク情報送受信部２２に対し中継指示を出さない。これにより、メンバであるＭＴ＃１、ＭＴ＃２、ＭＴ＃４はリンク情報の転送を行わない。

一方、リンク情報を受信したゲートウエイであるＭＴ＃５のリンク情報送受信部２２はリンク情報をトポロジテーブル２９Ａに保存する。この場合、クラスタヘッドのＩＤ（ＭＴ＃３）、及び当該クラスタヘッドに隣接する端末のＩＤ（ＭＴ＃１、ＭＴ＃２、ＭＴ＃４、ＭＴ＃５）がトポロジテーブル２９Ａに保存される。さらに、ゲートウエイであるＭＴ＃５のリンク情報送受信部２２は、受信したリンク情報を中継するか否かを中継判断部２３に問い合わせる。問合せを受けた中継判断部２３は状態保存テーブル２８Ａを参照する。この場合、状態保存テーブル２８Ａのエントリは「ゲートウエイ（Ｇ）」となっているので、中継判断部２３は、リンク情報送受信部２２に対し中継指示を出す。中継指示を受けたリンク情報送受信部２２は、受信したリンク情報をブロードキャストで転送する（Ｓ９２）。

転送されたリンク情報は、転送を行ったＭＴ＃５に隣接する端末（ＭＴ＃２、ＭＴ＃３、ＭＴ＃４、ＭＴ＃６、ＭＴ＃７、ＭＴ＃８）が受信する。

隣接する端末のうちメンバであるＭＴ＃２、ＭＴ＃４、ＭＴ＃６、ＭＴ＃８のリンク情報送受信部２２は、リンク情報をトポロジテーブル２９Ａに保存する。この場合、クラスタヘッドのＩＤ（ＭＴ＃３）、及び当該クラスタヘッドに隣接する端末のＩＤ（ＭＴ＃１、ＭＴ＃２、ＭＴ＃４、ＭＴ＃５）がトポロジテーブル２９Ａに保存される。さらに、メンバであるＭＴ＃２、ＭＴ＃４、ＭＴ＃６、ＭＴ＃８のリンク情報送受信部２２は、受信したリンク情報を中継するか否かを中継判断部２３に問い合わせる。問合せを受けた中継判断部２３は状態保存テーブル２８Ａを参照する。この場合、状態保存テーブル２８Ａのエントリは「メンバ（Ｍ）」となっているので、中継判断部２３は、リンク情報送受信部２２に対し中継指示を出さない。これにより、メンバであるＭＴ＃２、ＭＴ＃４、ＭＴ＃６、ＭＴ＃８は、リンク情報の転送を行わない。

また、リンク情報を受信したクラスタヘッドであるＭＴ＃３のリンク情報送受信部２２は、該リンク情報をトポロジテーブル２９Ａに保存する。この場合、クラスタヘッドのＩＤ（ＭＴ＃３）、及び当該クラスタヘッドに隣接する端末のＩＤ（ＭＴ＃１、ＭＴ＃２、ＭＴ＃４、ＭＴ＃５）がトポロジテーブル２９Ａに保存される。さらに、クラスタヘッドであるＭＴ＃３のリンク情報送受信部２２は、受信したリンク情報を中継するか否かを中継判断部２３に問い合わせる。問合せを受けた中継判断部２３は状態保存テーブル２８Ａを参照する。この場合、状態保存テーブル２８Ａのエントリは「クラスタヘッド（Ｈ）」となっているが、上記受信したリンク情報は、一度送信したリンク情報と同一のリンク情報なので、中継判断部２３はリンク情報送受信部２２に対し中継指示を出さない。これにより、クラスタヘッドであるＭＴ＃３はリンク情報の転送を行わない。

また、リンク情報を受信したクラスタヘッドであるＭＴ＃７のリンク情報送受信部２２も、該リンク情報をトポロジテーブル２９Ａに保存する。この場合、クラスタヘッドのＩＤ（ＭＴ＃３）、及び当該クラスタヘッドに隣接する端末のＩＤ（ＭＴ＃１、ＭＴ＃２、ＭＴ＃４、ＭＴ＃５）がトポロジテーブル２９Ａに保存される。さらに、クラスタヘッドであるＭＴ＃７のリンク情報送受信部２２は、受信したリンク情報を中継するか否かを中継判断部２３に問い合わせる。問合せを受けた中継判断部２３は状態保存テーブル２８Ａを参照する。この場合、状態保存テーブル２８Ａのエントリは「クラスタヘッド（Ｈ）」となっており、かつ、上記受信したリンク情報は、一度も送信したことがないリンク情報であるため、中継判断部２３はリンク情報送受信部２２に対し中継指示を出す。中継指示を受けたリンク情報送受信部２２は、上記受信したリンク情報をブロードキャストで転送する（Ｓ９３）。

転送されたリンク情報は、転送を行ったＭＴ＃７に隣接する端末（ＭＴ＃５、ＭＴ＃６、ＭＴ＃８、ＭＴ＃９）が受信する。

隣接する端末のうちメンバであるＭＴ＃６、ＭＴ＃８、ＭＴ＃９のリンク情報送受信部２２は、リンク情報をトポロジテーブル２９Ａに保存する。この場合、クラスタヘッドのＩＤ（ＭＴ＃３）、及び当該クラスタヘッドに隣接する端末のＩＤ（ＭＴ＃１、ＭＴ＃２、ＭＴ＃４、ＭＴ＃５）がトポロジテーブル２９Ａに保存される。さらに、メンバであるＭＴ＃６、ＭＴ＃８、ＭＴ＃９のリンク情報送受信部２２は、受信したリンク情報を中継するか否かを中継判断部２３に問い合わせる。問合せを受けた中継判断部２３は状態保存テーブル２８Ａを参照する。この場合、状態保存テーブル２８Ａのエントリは「メンバ（Ｍ）」となっているので、中継判断部２３はリンク情報送受信部２２に対し中継指示を出さない。これにより、リンク情報の転送は行われない。

一方、リンク情報を受信したゲートウエイであるＭＴ＃５のリンク情報送受信部２２は、リンク情報をトポロジテーブル２９Ａに保存する。この場合、クラスタヘッドのＩＤ（ＭＴ＃３）、及び当該クラスタヘッドに隣接する端末のＩＤ（ＭＴ＃１、ＭＴ＃２、ＭＴ＃４、ＭＴ＃５）がトポロジテーブル２９Ａに保存される。さらに、ゲートウエイであるＭＴ＃５のリンク情報送受信部２２は、受信したリンク情報を中継するか否かを中継判断部２３に問い合わせる。問合せを受けた中継判断部２３は状態保存テーブル２８Ａを参照する。この場合、状態保存テーブル２８Ａのエントリは「ゲートウエイ（Ｇ）」となっているが、上記受信したリンク情報は、一度送信したリンク情報と同一なので、中継判断部２３はリンク情報送受信部２２に対し中継指示を出さない。これにより、リンク情報の転送は行われない。

以上のような動作により、クラスタヘッドＭＴ＃３が送信したリンク情報はネットワーク上の全端末ＭＴ＃１〜ＭＴ＃９に伝送される。

また、上記と同様の動作により、クラスタヘッドＭＴ＃７が送信したリンク情報も、ネットワーク上の全端末ＭＴ＃１〜ＭＴ＃９に伝送される（Ｓ９４〜Ｓ９６）。

このように、各端末は、ＭＴ＃３が送信したリンク情報とＭＴ＃７が送信したリンク情報とを受信することにより、これらのリンク情報に基づいてルーティングテーブル２１０Ａを作成し、作成したルーティングテーブル２１０Ａに基づいてルーティングを行うことが可能となる。

次に、(3)通信パケット（データ通信や音声通話などのためのパケット）の送信時の動作について説明する。

まず、通信パケット送信時の移動端末装置の動作について図１４を用いて説明する。通信パケットを送信する際、移動端末装置２０は、ルーティングテーブル２１０Ａを参照して、あて先端末に通信パケットを送るために中継するべき隣接端末のＩＤを確認する（Ｓ１４２）。次に、移動端末装置２０は、確認により得られた隣接端末（中継するべき隣接端末）に対して通信パケットを送信する（Ｓ１４３）。

次に、通信パケットを転送する際の移動端末装置の動作について図１５を用いて説明する。移動端末装置２０は通信パケットを受信すると（Ｓ１５１）、図１５の処理を開始し、上記受信した通信パケットが自分あてか否かを確認する（Ｓ１５２）。ここで、受信した通信パケットが自分宛である場合は、当該通信パケットの転送は不要なので、処理を終了する。一方、Ｓ１５２で、上記受信した通信パケットが自分宛でない場合は、ルーティングテーブル２１０Ａを参照し、次に中継するべき隣接端末のＩＤを確認する（Ｓ１５３）。次に、移動端末装置２０は、確認により得られた隣接端末（次に中継するべき隣接端末）に対して通信パケットを転送する（Ｓ１５４）。

次に、通信パケット送信時の移動通信システム全体の動作シーケンスについて図１０を用いて説明する。図１０には、通信パケットをＭＴ＃１からＭＴ＃９へ送信するシーケンスを示している。

通信パケットを送信するＭＴ＃１のデータ送受信部２４は、あて先端末ＭＴ＃９に通信パケットを送信するために中継すべき端末を、ルーティング部２６に問い合わせる。問合せを受けたルーティング部２６は、ルーティングテーブル２１０Ａ内のNextHopエントリを参照して、あて先端末ＭＴ＃９に通信パケットを送信するために中継すべき端末ＭＴ＃３を得て、中継すべき端末情報（ＭＴ＃３）をデータ送受信部２４に通知する。通知を受けたデータ送受信部２４は通信パケットを、中継すべき端末であるＭＴ＃３に転送する（Ｓ１０１）。

次に、通信パケットを受信したＭＴ＃３のデータ送受信部２４は、あて先端末ＭＴ＃９に通信パケットを送信するために中継すべき端末を、ルーティング部２６に問い合わせる。問合せを受けたルーティング部２６は、ルーティングテーブル２１０Ａ内のNextHopエントリを参照して、あて先端末ＭＴ＃９に通信パケットを送信するために中継すべき端末ＭＴ＃５を得て、中継すべき端末情報（ＭＴ＃５）をデータ送受信部２４に通知する。通知を受けたデータ送受信部２４は通信パケットを、中継すべき端末であるＭＴ＃５に転送する（Ｓ１０２）。

次に、通信パケットを受信したＭＴ＃５のデータ送受信部２４は、あて先端末ＭＴ＃９に通信パケットを送信するために中継すべき端末を、ルーティング部２６に問い合わせる。問合せを受けたルーティング部２６は、ルーティングテーブル２１０Ａ内のNextHopエントリを参照して、あて先端末ＭＴ＃９に通信パケットを送信するために中継すべき端末ＭＴ＃７を得て、中継すべき端末情報（ＭＴ＃７）をデータ送受信部２４に通知する。通知を受けたデータ送受信部２４は通信パケットを、中継すべき端末であるＭＴ＃７に転送する（Ｓ１０３）。

次に、通信パケットを受信したＭＴ＃７のデータ送受信部２４は、あて先端末ＭＴ＃９に通信パケットを送信するために中継すべき端末を、ルーティング部２６に問い合わせる。問合せを受けたルーティング部２６は、ルーティングテーブル２１０Ａ内のNextHopエントリを参照して、あて先端末ＭＴ＃９へ直接送信可能であることをデータ送受信部２４へ通知する。通知を受けたデータ送受信部２４は通信パケットをＭＴ＃９に直接転送する（Ｓ１０４）。

以上の動作により、ＭＴ＃１からＭＴ＃９へ通信パケットが送信される。

続いて、第１実施形態の効果について説明する。第１実施形態に係る移動端末装置によれば、クラスタヘッドのみが隣接端末の間のリンク情報をネットワーク上の全端末に送信するだけで、全端末は任意の端末との間のルートを計算することができる。また、本実施形態に係る移動端末装置によれば、クラスタヘッドとゲートウエイのみがリンク情報を転送するだけで、リンク情報をネットワーク上の全端末に送信することができる。上記２つの効果により、オーバヘッドの少ないルーティングを実現することができる。

（第２実施形態）
図１７乃至図２２を参照して、本発明の第２実施形態に係る移動通信システムの構成について説明する。図１７に示すように、本実施形態に係る移動通信システム１１は、複数の移動端末装置ＭＴ＃１乃至ＭＴ＃９と、セルラネットワークのようなインフラネットワーク上に設置されたトポロジ管理装置ＴＳとを含んで構成される。移動端末装置ＭＴ＃１乃至ＭＴ＃９はすべて同様の構成で、同様の機能を持つが、クラスタヘッド、ゲートウエイ、メンバという３つの状態のうち何れか１つの状態となる。各移動端末装置の状態は、固定的ではなく、他の端末との相対的な位置関係により動的に変化する。移動通信システム１０における各移動端末装置の状態は以下の条件を満たすように動的に決定される。
１.ゲートウエイ同士は隣接しない。
２.メンバはクラスタヘッドに隣接し、隣接するクラスタヘッドの中の１つを指定する。
３.クラスタヘッド間はただ１つのゲートウエイによって接続される。

図１７の例では、ＭＴ＃３及びＭＴ＃７がクラスタヘッド、ＭＴ＃５がゲートウエイ、ＭＴ＃１、ＭＴ＃２、ＭＴ＃４、ＭＴ＃６、ＭＴ＃８、ＭＴ＃９がメンバとして構成されている。

なお、図１７では移動端末装置の数は９であるが、上記移動端末装置の状態に関する３つの条件を満たすならば、移動端末装置の数に制限はない。

本実施形態において、クラスタヘッドは、自身に隣接している端末との間のリンク情報をトポロジ管理装置ＴＳに送信する。これにより、トポロジ管理装置ＴＳはルーティングに必要なリンク情報を得ることができ、任意の端末間のルートを計算することが可能である。ここで「リンク情報」の意味内容は第１実施形態のリンク情報と同様である。

次に、本実施形態にかかる移動端末装置ＭＴ＃１乃至ＭＴ＃９（第２実施形態では「移動端末装置１８０」と総称する）の構成について説明する。図１８は本実施形態にかかる移動端末装置１８０の機能ブロック構成を示す。移動端末装置１８０は、Helloパケット送受信部１８１と、リンク情報送受信部１８２と、データ送受信部１８３と、クラスタリング部１８４とルーティング部１８５と、隣接端末リスト保存部１８６と、状態保存部１８７とを具備している。以下、各構成部について順に説明する。

Helloパケット送受信部１８１、クラスタリング部１８４、隣接端末リスト保存部１８６、状態保存部１８７については第１実施形態と同様である。

リンク情報送受信部１８２は、リンク情報をトポロジ管理装置ＴＳに送信するように構成される。リンク情報送受信部１８２は、状態保存部１８７を参照し、自身の状態がクラスタヘッドである場合に、隣接端末リスト保存部１８６を参照して、木を構成しているリンク情報をトポロジ管理装置ＴＳに送信する。ここで、「木」の意味内容は、第１実施形態と同様である。

データ送受信部１８３は、端末間でのデータ通信や音声通話などで送信されるパケット（通信パケット）をユニキャストで送信、受信、又は転送するように構成される。データ送受信部１８３は、通信パケットを送信する場合、ルーティング部１８５に、あて先端末に通信パケットを届けるための中継端末となる隣接端末のＩＤのリストを問い合わせ、当該隣接端末のＩＤのリストにおける最初のＩＤの端末に対して、通信パケット及び当該ＩＤのリストを送信する。ここで、ＩＤのリストは、例えば図２２のように構成され、送信端末から宛先端末に至るまでに通信パケットを中継する端末を中継順に示している。データ送受信部１８３は、他の端末から通信パケットを受信したとき、宛先が自身でなければ、受信したＩＤのリストを参照し、自身のＩＤの次に記載されているＩＤの端末に通信パケット及び当該ＩＤのリストを転送する。このとき自身のＩＤがリストの最後に記載されている場合は、宛先端末へ通信パケットを送信する。例えば図２２のＩＤのリストを受信し、自身のＩＤがＭＴ＃５であるならば、ＭＴ＃５の次に記載されているＩＤ（ＭＴ＃７）の端末へ転送する。

ルーティング部１８５は、データ送受信部１８３の要求を受け、トポロジ管理装置ＴＳに問い合わせを行うことにより、通信パケットを中継する中継端末のＩＤのリストをデータ送受信部１８３に通知するように構成される。

次に、図２０を用いて第２実施形態の移動端末装置１８０のハードウェア構成について説明する。移動端末装置１８０は、ＣＰＵ２０１、メモリ２０２、及びネットワークインタフェース２０３を含んで構成される。図１８におけるHelloパケット送受信部１８１はＣＰＵ２０１及びネットワークインタフェース２０３により実現される。リンク情報送受信部１８２は、ＣＰＵ２０１及びネットワークインタフェース２０３により実現される。データ送受信部１８３はＣＰＵ２０１及びネットワークインタフェース２０３により実現される。クラスタリング部１８４はＣＰＵ２０１により実現される。ルーティング部１８５はＣＰＵ２０１及びネットワークインタフェース２０３により実現される。隣接端末リスト保存部１８６はメモリ２０２により実現される。状態保存部１８７はメモリ２０２により実現される。

次に、本実施形態におけるトポロジ管理装置ＴＳの構成について図１９を用いて説明する。トポロジ管理装置ＴＳは、リンク情報受信部１９１、ルーティング部１９２、及びトポロジ情報保存部１９３を含んで構成される。なお、リンク情報受信部１９１は、本発明に係るリンク情報受信手段に対応し、ルーティング部１９２及びトポロジ情報保存部１９３は、本発明に係るリスト提供手段に対応する。

リンク情報受信部１９１は、移動端末装置１８０からのリンク情報を受信し、トポロジ情報保存部１９３に保存するように構成される。トポロジ情報保存部１９３は、図５のようなトポロジテーブル２９Ａを保持する。トポロジテーブル２９Ａには、リンク情報を送信したクラスタヘッドのＩＤと、当該クラスタヘッドに隣接する端末のＩＤとが含まれる。

ルーティング部１９２は、移動端末装置１８０からの要求を受け、トポロジ情報保存部１９３を参照し、中継端末のＩＤのリストを計算し、移動端末装置１８０に送信するように構成される。ＩＤのリストの計算は、例えばダイクストラ法によって行われる。

次に、トポロジ管理装置ＴＳのハードウェア構成について図２１を用いて説明する。トポロジ管理装置ＴＳは、ＣＰＵ２１１、メモリ２１２、及びネットワークインタフェース２１３を含んで構成される。図１９におけるリンク情報受信部１９１は、ＣＰＵ２１１及びネットワークインタフェース２１３により実現される。ルーティング部１９２はＣＰＵ２１１及びネットワークインタフェース２１３により実現され、トポロジ情報保存部１９３はメモリ２１２により実現される。

続いて本実施形態における移動端末装置１８０及びトポロジ管理装置ＴＳの動作について図２３乃至図２６を用いて説明する。なお、(1)クラスタ構成時の動作、(2)リンク情報送信時の動作、(3)通信パケット送信時の動作のうち、(1)クラスタ構成時の移動端末装置の動作については第１実施形態と同様であるので、説明を省略する。また、(2)リンク情報送信時における移動端末装置１８０の動作は、リンク情報をブロードキャストする代わりに、リンク情報をトポロジ管理装置ＴＳに送信する点とリンク情報の転送は行わない点とが第１実施形態と異なる。

まず、(2)リンク情報送信時における移動通信システム１１全体の動作について図２３を用いて説明する。クラスタヘッドであるＭＴ＃３のリンク情報送受信部１８２は、定期的にリンク情報をトポロジ管理装置ＴＳに送信する。ＭＴ＃３のリンク情報送受信部２２は、まず、隣接端末テーブル２７Ａを参照し、木の構成エントリが「Ｙ」である隣接端末ＩＤをリストにする。この場合、ＭＴ＃１、ＭＴ＃２、ＭＴ＃４、ＭＴ＃５が当該リストに挙げられる。次に、当該リストに自身のＩＤ（ＭＴ＃３）を加えたものをリンク情報としてトポロジ管理装置ＴＳに送信する（図２３のＳ２３１）。リンク情報を受信したトポロジ管理装置ＴＳのリンク情報受信部１９１は、受信されたリンク情報をトポロジ情報保存部１９３に保存する。この場合、クラスタヘッドのＩＤ（ＭＴ＃３）及び当該クラスタヘッドに隣接する端末のＩＤ（ＭＴ＃１、ＭＴ＃２、ＭＴ＃４、ＭＴ＃５）がトポロジ情報保存部１９３に保存される。同様に、クラスタヘッドであるＭＴ＃７もトポロジ管理装置ＴＳにリンク情報を送信し（Ｓ２３２）、トポロジ管理装置ＴＳのリンク情報受信部１９１は、受信したリンク情報をトポロジ情報保存部１９３に保存する。

次に、(3)通信パケット（データ通信や音声通話などのパケット）の送信時における移動端末装置１８０の動作について図２５を用いて説明する。移動端末装置１８０はまず、中継端末のＩＤのリストをトポロジ管理装置ＴＳに問い合わせる（Ｓ２５１）。そして、問合せに対しトポロジ管理装置ＴＳから得られたＩＤのリストの最初に記載されているＩＤの端末に、通信パケット及びＩＤのリストを送信する（Ｓ２５２）。

次に、(3)通信パケットの転送時における移動端末装置１８０の動作について図２６を用いて説明する。移動端末装置１８０は、他の端末から通信パケットを受信すると（Ｓ２６１）、図２６の処理を開始し、まず、受信した通信パケットの宛先端末が自身であるか否かを確認する（Ｓ２６２）。ここで、宛先端末が自身である場合は、受信した通信パケットの転送は不要なので、当該通信パケットを転送せずに処理を終了する。一方、Ｓ２６２で宛先端末が自身で無い場合は、自身のＩＤがリストの最後であるか否かを確認する（Ｓ２６３）。ここで、自身のＩＤがリストの最後である場合は、宛先端末は隣接していることになるので、宛先端末に対し通信パケット及びＩＤのリストを転送する（Ｓ２６５）。一方、Ｓ２６３で自身のＩＤがリストの最後でない場合は、ＩＤのリストを参照して自身のＩＤの次にあるＩＤの端末に対し通信パケット及び自身のＩＤを転送する（Ｓ２６４）。

次に、(3)通信パケットの転送時における移動通信システム１１全体の動作について図２４を用いて説明する。図２４は通信パケットをＭＴ＃１からＭＴ＃９へ送信するシーケンスを示している。通信パケットを送信するＭＴ＃１のデータ送受信部１８３は、宛先端末に通信パケットを届けるための中継端末のＩＤのリストをルーティング部１８５に問い合わせ、該ルーティング部１８５は、トポロジ管理装置ＴＳに中継端末のＩＤのリストを問い合わせる（Ｓ２４１）。問合せを受けたトポロジ管理装置ＴＳのルーティング部１９２は、トポロジ情報保存部１９３を参照して中継端末のＩＤのリストを作成し、該中継端末のＩＤのリストをＭＴ＃１のルーティング部１８５に返信する（Ｓ２４２）。これにより、ＭＴ＃１のルーティング部１８５は該中継端末のＩＤのリストを得る。

そして、ＭＴ＃１のルーティング部１８５は、データ送受信部１８３に対し中継端末のＩＤのリストを通知する。通知を受けたデータ送受信部１８３は、該中継端末のＩＤのリストにおいて最初に記載されているＭＴ＃３に対し通信パケット及びＩＤのリストを送信する（Ｓ２４３）。そして、通信パケット及びＩＤのリストを受信したＭＴ＃３のデータ送受信部１８３は、該ＩＤのリストを参照し、該ＩＤのリストにおいて自身の次に記載されているＭＴ＃５に対し通信パケット及びＩＤのリストを転送する（Ｓ２４４）。

次に、通信パケット及びＩＤのリストを受信したＭＴ＃５のデータ送受信部１８３は、該ＩＤのリストを参照し、該ＩＤのリストにおいて自身の次に記載されているＭＴ＃７に対し通信パケット及びＩＤのリストを転送する（Ｓ２４５）。さらに、通信パケット及びＩＤのリストを受信したＭＴ＃７のデータ送受信部１８３は、該ＩＤのリストを参照し、自身のＩＤ（ＭＴ＃７）がリストの最後であると判断する。即ち、宛先端末（ＭＴ＃９）は、自身に隣接していることになるので、ＭＴ＃７のデータ送受信部１８３は、宛先端末（ＭＴ＃９）に対し通信パケット及びＩＤのリストを転送する（Ｓ２４６）。このようにして通信パケット及びＩＤのリストは宛先端末ＭＴ＃９まで届けられる。

最後に、第２実施形態の効果について説明する。本実施形態に係る移動端末装置１８０及びトポロジ管理装置ＴＳによれば、クラスタヘッドのみが隣接端末の間のリンク情報をトポロジ管理装置ＴＳに送信するだけで、トポロジ管理装置ＴＳは任意の端末間のルートを計算することが可能である。上記の効果により、オーバヘッドの少ないルーティングを実現することができる。

第１実施形態の移動通信システムのネットワーク構成図である。 第１実施形態の移動端末装置の機能ブロック構成図である。 第１実施形態の移動端末装置のハードウェア構成図である。 隣接端末テーブルの一例を示す図である。 トポロジテーブルの一例を示す図である。 ルーティングテーブルの一例を示す図である。 状態保存テーブルの一例を示す図である。 第１、第２実施形態でのクラスタ構成時の移動通信システム全体の動作シーケンスを示す図である。 第１実施形態でのリンク情報送信時の移動通信システム全体の動作シーケンスを示す図である。 第１実施形態での通信パケット送信時の移動通信システム全体の動作シーケンスを示す図である。 第１、第２実施形態でのクラスタ構成時の移動端末装置の動作シーケンスを示す図である。 第１実施形態でのリンク情報送信時の移動端末装置の動作シーケンスを示す図である。 第１実施形態でのリンク情報転送時の移動端末装置の動作シーケンスを示す図である。 第１実施形態での通信パケット送信時の移動端末装置の動作シーケンスを示す図である。 第１実施形態での通信パケット転送時の移動端末装置の動作シーケンスを示す図である。 リンク情報の構成例を示す図である。 第２実施形態の移動通信システムのネットワーク構成図である。 第２実施形態の移動端末装置の機能ブロック構成図である。 第２実施形態のトポロジ管理装置の機能ブロック構成図である。 第２実施形態の移動端末装置のハードウェア構成図である。 第２実施形態のトポロジ管理装置のハードウェア構成図である。 中継端末ＩＤリストの構成例を示す図である。 第２実施形態でのリンク情報送信時の移動通信システム全体の動作シーケンスを示す図である。 第２実施形態での通信パケット送信時の移動通信システム全体の動作シーケンスを示す図である。 第２実施形態での通信パケット送信時の移動端末装置の動作シーケンスを示す図である。 第２実施形態での通信パケット転送時の移動端末装置の動作シーケンスを示す図である。

符号の説明

１０、１１…移動通信システム、２０…移動端末装置、２１…Helloパケット送受信部、２２…リンク情報送受信部、２３…中継判断部、２４…データ送受信部、２５…クラスタリング部、２６…ルーティング部、２７…隣接端末リスト保存部、２７Ａ…隣接端末テーブル、２８…状態保存部、２８Ａ…状態保存テーブル、２９…トポロジ情報保存部、２９Ａ…トポロジテーブル、３１…ＣＰＵ、３２…メモリ、３３…ネットワークインタフェース、１８０…移動端末装置、１８１…Helloパケット送受信部、１８２…リンク情報送受信部、１８３…データ送受信部、１８４…クラスタリング部、１８５…ルーティング部、１８６…隣接端末リスト保存部、１８７…状態保存部、１９１…リンク情報受信部、１９２…ルーティング部、１９３…トポロジ情報保存部、２０１…ＣＰＵ、２０２…メモリ、２０３…ネットワークインタフェース、２１０…ルーティングテーブル保存部、２１０Ａ…ルーティングテーブル、２１１…ＣＰＵ、２１２…メモリ、２１３…ネットワークインタフェース、ＴＳ…トポロジ管理装置。

Claims (7)

1. 複数の移動端末装置によってアドホックネットワークが形成されている環境における当該移動端末装置であって、
   当該移動端末装置自身のＩＤ及び状態を含むパケットを他の移動端末装置との間で送受信することで、自身に隣接する移動端末装置のＩＤ及び状態を認識し、当該隣接する移動端末装置の状態及び自身の状態に基づいて、自身の状態をクラスタヘッド、ゲートウエイ又はメンバに設定するクラスタリング手段と、
   前記クラスタリング手段により認識された前記隣接する移動端末装置のＩＤ及び状態、並びに、自身の状態を保存する保存手段と、
   前記保存手段により保存された自身の状態がクラスタヘッドである場合に、保存された１つ以上の前記隣接する移動端末装置のＩＤと自身のＩＤとを含んで構成されるリンク情報を送信するとともに、前記保存された自身の状態がいかなる場合でも、他の移動端末装置から送信された前記リンク情報を受信するリンク情報送受信手段と、
   前記リンク情報送受信手段により送受信された前記リンク情報に基づいて任意の移動端末装置へのルートを求めるルーティング手段と、
   を具備し、
   前記クラスタリング手段は、
   クラスタヘッド同士は隣接しないことと、メンバはクラスタヘッドに隣接し且つただ１つのクラスタヘッドに属することを指定することと、クラスタヘッド間はただ１つのゲートウエイによって接続されることとを特徴とするクラスタを構成するように、自身の状態をクラスタヘッド、ゲートウエイ又はメンバに設定し、
   自身のＩＤと自身の状態と自身が親に指定する移動端末装置のＩＤ情報とを含む制御情報を送受信し、
   受信した制御情報を前記保存手段に保存し、
   保存した制御情報の中に状態がクラスタヘッドである移動端末装置のＩＤが存在する場合に、自身の状態をメンバに決定し、
   保存した制御情報の中に状態がクラスタヘッドである移動端末装置のＩＤが存在せず、ゲートウエイである移動端末装置のＩＤが存在する場合に、自身の状態をクラスタヘッドに決定し、
   保存した制御情報の中に状態がクラスタヘッドである移動端末装置のＩＤもゲートウエイである移動端末装置のＩＤも存在しない場合に、自身の状態をクラスタヘッドに決定し、
   自身の状態がメンバであり、保存した制御情報の中に状態がクラスタヘッドで自身を親に指定している移動端末装置のＩＤが存在する場合に、自身の状態をゲートウエイに変更する、
   ことを特徴とする移動端末装置。
2. 前記クラスタリング手段は、
   自身が親に指定している移動端末装置のＩＤが前記保存した制御情報から削除されたことを契機として、自身の状態を初期化し、
   前記保存した制御情報を参照し、自身が親に指定している移動端末装置の状態が初期化されたことを契機として、自身の状態を初期化する、
   ことを特徴とする請求項１記載の移動端末装置。
3. 前記リンク情報送受信手段は、
   送信されるリンク情報として、自身に隣接するゲートウエイのＩＤと、自身を親に指定しているメンバのＩＤと、自身のＩＤとを含んで構成されるリンク情報を送信することを特徴とする請求項１に記載の移動端末装置。
4. 前記リンク情報送受信手段は、
   前記保存手段により保存された自身の状態がクラスタヘッド又はゲートウエイである場合に、他の移動端末装置から受信された前記リンク情報を転送することを特徴とする請求項１に記載の移動端末装置。
5. 複数の移動端末装置によってアドホックネットワークが形成されている環境における当該移動端末装置にて実行される制御方法であって、
   当該移動端末装置自身のＩＤ及び状態を含むパケットを他の移動端末装置との間で送受信することで、自身に隣接する移動端末装置のＩＤ及び状態を認識し、当該隣接する移動端末装置の状態及び自身の状態に基づいて、自身の状態をクラスタヘッド、ゲートウエイ又はメンバに設定するクラスタリングステップと、
   前記クラスタリングステップにて認識された前記隣接する移動端末装置のＩＤ及び状態、並びに、自身の状態を保存する保存ステップと、
   前記保存ステップにて保存された自身の状態がクラスタヘッドである場合に、保存された１つ以上の前記隣接する移動端末装置のＩＤと自身のＩＤとを含んで構成されるリンク情報を送信するとともに、前記保存された自身の状態がいかなる場合でも、他の移動端末装置から送信された前記リンク情報を受信するリンク情報送受信ステップと、
   前記リンク情報送受信ステップにて送受信された前記リンク情報に基づいて任意の移動端末装置へのルートを求めるルーティングステップと、
   を有し、
   前記クラスタリングステップでは、当該移動端末装置が、
   クラスタヘッド同士は隣接しないことと、メンバはクラスタヘッドに隣接し且つただ１つのクラスタヘッドに属することを指定することと、クラスタヘッド間はただ１つのゲートウエイによって接続されることとを特徴とするクラスタを構成するように、自身の状態をクラスタヘッド、ゲートウエイ又はメンバに設定し、
   自身のＩＤと自身の状態と自身が親に指定する移動端末装置のＩＤ情報とを含む制御情報を送受信し、
   受信した制御情報を保存し、
   保存した制御情報の中に状態がクラスタヘッドである移動端末装置のＩＤが存在する場合に、自身の状態をメンバに決定し、
   保存した制御情報の中に状態がクラスタヘッドである移動端末装置のＩＤが存在せず、ゲートウエイである移動端末装置のＩＤが存在する場合に、自身の状態をクラスタヘッドに決定し、
   保存した制御情報の中に状態がクラスタヘッドである移動端末装置のＩＤもゲートウエイである移動端末装置のＩＤも存在しない場合に、自身の状態をクラスタヘッドに決定し、
   自身の状態がメンバであり、保存した制御情報の中に状態がクラスタヘッドで自身を親に指定している移動端末装置のＩＤが存在する場合に、自身の状態をゲートウエイに変更する、
   ことを特徴とする制御方法。
6. 移動端末装置のＩＤと、前記移動端末装置に隣接する１つ以上の移動端末装置のＩＤとを含んで構成されるリンク情報を受信するリンク情報受信手段と、
   前記リンク情報に基づいて、複数の移動端末装置間の通信を行うための中継となるべき移動端末装置のＩＤのリストを求め、当該リストを当該通信の起点の移動端末装置に提供するリスト提供手段と、
   を具備するトポロジ管理装置と、
   複数の請求項１記載の移動端末装置と、
   を含んで構成されることを特徴とする移動通信システム。
7. トポロジ管理装置と複数の移動端末装置とを含んで構成される移動通信システムにおける制御方法であって、
   各移動端末装置が、当該移動端末装置自身のＩＤ及び状態を含むパケットを他の移動端末装置との間で送受信することで、自身に隣接する移動端末装置のＩＤ及び状態を認識し、当該隣接する移動端末装置の状態及び自身の状態に基づいて、自身の状態をクラスタヘッド、ゲートウエイ又はメンバに設定するクラスタリングステップと、
   各移動端末装置が、前記クラスタリングステップにて認識された前記隣接する移動端末装置のＩＤ及び状態、並びに、自身の状態を保存する保存ステップと、
   各移動端末装置が、前記保存ステップにて保存された自身の状態がクラスタヘッドである場合に、保存された１つ以上の前記隣接する移動端末装置のＩＤと自身のＩＤとを含んで構成されるリンク情報を前記トポロジ管理装置へ送信するリンク情報送信ステップと、
   前記トポロジ管理装置が、前記リンク情報を受信するリンク情報受信ステップと、
   前記トポロジ管理装置が、受信した前記リンク情報に基づいて、複数の移動端末装置間の通信を行うための中継となるべき移動端末装置のＩＤのリストを求め、当該リストを当該通信の起点の移動端末装置に提供するリスト提供ステップと、
   を有し、
   前記クラスタリングステップでは、各移動端末装置が、
   クラスタヘッド同士は隣接しないことと、メンバはクラスタヘッドに隣接し且つただ１つのクラスタヘッドに属することを指定することと、クラスタヘッド間はただ１つのゲートウエイによって接続されることとを特徴とするクラスタを構成するように、自身の状態をクラスタヘッド、ゲートウエイ又はメンバに設定し、
   自身のＩＤと自身の状態と自身が親に指定する移動端末装置のＩＤ情報とを含む制御情報を送受信し、
   受信した制御情報を保存し、
   保存した制御情報の中に状態がクラスタヘッドである移動端末装置のＩＤが存在する場合に、自身の状態をメンバに決定し、
   保存した制御情報の中に状態がクラスタヘッドである移動端末装置のＩＤが存在せず、ゲートウエイである移動端末装置のＩＤが存在する場合に、自身の状態をクラスタヘッドに決定し、
   保存した制御情報の中に状態がクラスタヘッドである移動端末装置のＩＤもゲートウエイである移動端末装置のＩＤも存在しない場合に、自身の状態をクラスタヘッドに決定し、
   自身の状態がメンバであり、保存した制御情報の中に状態がクラスタヘッドで自身を親に指定している移動端末装置のＩＤが存在する場合に、自身の状態をゲートウエイに変更する、
   ことを特徴とする制御方法。

Images