(57)【要約】【課題】アッドホックネットワークにおいて、クラスタ間の境界付近におけるネットワークの輻輳を抑えつつ通信経路を決定すること。【解決手段】アドホックネットワークシステムにおける第１の端末装置であって、第１の端末装置から、第１の端末装置を中心とする正六角形状の第１のクラスタの辺上に位置する第２の端末装置までの、第１の通信経路を探索する第１の通信経路探索部と、第１の端末装置から、第１の端末装置が辺上に位置する正六角形状の第２のクラスタの辺上に位置する第３の端末装置までの、第２の通信経路を探索する第２の通信経路探索部と、第１の通信経路および第２の通信経路を保持する記憶部と、を備える。【選択図】図１
2013162463.tif 000002
【特許請求の範囲】
【請求項１】
アドホックネットワークシステムにおいて第１の端末装置から目的の端末装置までの通信経路を決定する通信経路決定方法であって、
前記第１の端末装置が、前記第１の端末装置から、前記第１の端末装置を中心とする正六角形状の第１のクラスタの辺上に位置する第２の端末装置までの、第１の通信経路を探索する第１の探索工程と、
前記第２の端末装置が、前記第２の端末装置から、前記第２の端末装置が位置する辺を前記第１のクラスタとの間で共有する正六角形状の第２のクラスタの辺上に位置する第３の端末装置までの、第２の通信経路を探索する第２の探索工程と、を含み、
前記第１の端末装置から前記目的の端末装置までの通信経路が、少なくとも前記第１の通信経路および前記第２の通信経路を含むことを特徴とする通信経路決定方法。
【請求項２】
前記第３の端末装置は、前記第２のクラスタの辺のうちの、前記第２の端末装置が位置する辺との間で頂点を共有しない辺上に位置することを特徴とする、請求項１に記載の通信経路決定方法。
【請求項３】
前記第１の端末装置が、前記第１の端末装置との距離が前記第１のクラスタの一辺の長さの少なくとも２倍の距離以内の他の端末装置の位置を示す第１の位置情報を取得する工程を含み、
前記第１の探索工程において、前記第１の端末装置は、前記第１の位置情報に基づいて前記第１の通信経路を探索することを特徴とする、請求項２に記載の通信経路決定方法。
【請求項４】
前記第２の端末装置が、前記第２の端末装置との距離が前記距離以内の他の端末装置の位置を示す第２の位置情報を取得する工程を含み、
前記第２の探索工程において、前記第２の端末装置は、前記第２の位置情報に基づいて前記第２の通信経路を探索することを特徴とする、請求項３に記載の通信経路決定方法。
【請求項５】
前記第１の端末装置が、前記第１の端末装置との距離が前記第１のクラスタの一辺の長さの少なくとも２倍の距離以内の他の端末装置を識別する第１の識別情報を取得する工程を含み、
前記目的の端末装置を示す情報が前記第１の識別情報に含まれない場合に、前記第１の端末装置は前記第１の通信経路を探索することを特徴とする、請求項４に記載の通信経路決定方法。
【請求項６】
前記第２の端末装置が、前記第２の端末装置との距離が前記距離以内の他の端末装置を識別する第２の識別情報を取得する工程を含み、
前記目的の端末装置を示す情報が前記第２の識別情報に含まれない場合に、前記第２の端末装置は前記第２の通信経路を探索することを特徴とする、請求項５に記載の通信経路決定方法。
【請求項７】
前記第３の端末装置が、前記第３の端末装置から、前記第３の端末装置が位置する辺を前記第２のクラスタとの間で共有する正六角形の第３のクラスタの辺上に位置する第４の端末装置までの、第３の通信経路を探索する工程を含み、
前記第１の端末装置から前記目的の端末装置までの通信経路が、さらに前記第３の通信経路を含むことを特徴とする、請求項６に記載の通信経路決定方法。
【請求項８】
前記第３の端末装置が、前記第３の端末装置との距離が前記距離以内の他の端末装置を識別する第３の識別情報を取得する工程を含み、
前記目的の端末装置を示す情報が前記第３の識別情報に含まれない場合に、前記第３の端末装置は前記第３の通信経路を探索することを特徴とする、請求項７に記載の通信経路決定方法。
【請求項９】
アドホックネットワークシステムにおける第１の端末装置であって、
前記第１の端末装置から、前記第１の端末装置を中心とする正六角形状の第１のクラスタの辺上に位置する第２の端末装置までの、第１の通信経路を探索する第１の通信経路探索部と、
前記第１の端末装置から、前記第１の端末装置が辺上に位置する正六角形状の第２のクラスタの辺上に位置する第３の端末装置までの、第２の通信経路を探索する第２の通信経路探索部と、
前記第１の通信経路および前記第２の通信経路を保持する記憶部と、を備えることを特徴とする端末装置。
【請求項１０】
アドホックネットワークシステムにおける第１の端末装置から、前記第１の端末装置を中心とする正六角形状の第１のクラスタの辺上に位置する第２の端末装置までの、第１の通信経路を探索する第１の探索処理と、
前記第１の端末装置から、前記第１の端末装置が辺上に位置する正六角形状の第２のクラスタの辺上に位置する第３の端末装置までの、第２の通信経路を探索する第２の探索処理と、を前記第１の端末装置に設けられたコンピュータに対して実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信経路決定方法、端末装置およびプログラムに関し、特に、大規模アドホックネットワークにおける通信経路決定方法、端末装置およびプログラムに関する。
【背景技術】
【０００２】
アドホックネットワーク（Ad Hoc Network）においては、ネットワーク中の各端末装置がデータを中継する機能を有する。これにより、基地局から直接データを転送することができない場所に位置する端末装置に対しても、中継機能を担う端末装置を経由してデータを伝達することが可能となる。
【０００３】
大規模なアドホックネットワークにおいて、通信先の端末装置の位置情報等がない場合には、ネットワーク中の端末装置を全検索する必要がある。しかしながら、新たに通信を行うごとに、端末装置の全検索を行うと、制御パケットによって通信帯域が占有されてしまうという問題がある。
【０００４】
この問題を解消するために、クラスタリング方式（Clustering Scheme）に基づくルーティング手法が研究されている（非特許文献１）。クラスタリング（Clustering）とは、大規模なネットワークを複数のクラスタに分割することをいう。ネットワークを分割することにより、フラッティングされる制御パケットがクラスタ内に限定され、無駄な制御パケットを削減することができる。
【０００５】
なお、関連技術として、特許文献１には、アドホックネットワークにおいて、移動端末装置がＧＰＳ（Global Positioning System）機能に依らずに自身の位置を求める方法が記載されている。また、特許文献２には、アドホックネットワークにおいて、中継局における輻輳を回避しつつ、通信経路を形成する方法が記載されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００６−２２９８４５号公報
【特許文献２】特開２０１１−０５５２６５号公報
【非特許文献】
【０００７】
【非特許文献１】J.Y.Yu and P.H.J.Chong, “A Survey of Clustering Schemes for Mobile Ad Hoc Networks,” IEEE Communications Surveys & Tutorials, vol.7, pp.32-48, 2005
【発明の概要】
【発明が解決しようとする課題】
【０００８】
以下の分析は、本発明者によってなされたものである。
【０００９】
非特許文献１に記載されたクラスタリング方式によると、ネットワークのトポロジ等の変更が生じた場合に、次のような問題が起こり得る。すなわち、トポロジの変更に伴ってクラスタが再編されると、クラスタ内のデータ転送等を調整する端末装置であるクラスタヘッド（Clusterhead）が変更されることがある。このとき、変更後のクラスタヘッドは、新たにクラスタ内の端末装置に関する情報を収集する必要があり、制御パケットの数が増大するおそれがある。
【００１０】
また、図８に示すような形状のクラスタＣ１０１〜Ｃ１０３が形成された場合には、クラスタ間の境界（例えば、クラスタＣ１０１とＣ１０２の境界、クラスタＣ１０１とＣ１０３の境界）の近傍に位置する端末装置の間で頻繁に情報のやり取りが行われる。したがって、クラスタ間の境界付近において、ネットワークの輻輳が起こり易いという問題もある。
【００１１】
そこで、アッドホックネットワークにおいて、クラスタ間の境界付近におけるネットワークの輻輳を抑えつつ通信経路を決定することが課題となる。本発明の目的は、かかる課題を解決する通信経路決定方法、端末装置およびプログラムを提供することにある。
【課題を解決するための手段】
【００１２】
本発明の第１の視点に係る通信経路決定方法は、
アドホックネットワークシステムにおいて第１の端末装置から目的の端末装置までの通信経路を決定する通信経路決定方法であって、
前記第１の端末装置が、前記第１の端末装置から、前記第１の端末装置を中心とする正六角形状の第１のクラスタの辺上に位置する第２の端末装置までの、第１の通信経路を探索する第１の探索工程と、
前記第２の端末装置が、前記第２の端末装置から、前記第２の端末装置が位置する辺を前記第１のクラスタとの間で共有する正六角形状の第２のクラスタの辺上に位置する第３の端末装置までの、第２の通信経路を探索する第２の探索工程と、を含み、
前記第１の端末装置から前記目的の端末装置までの通信経路が、少なくとも前記第１の通信経路および前記第２の通信経路を含む。
【００１３】
本発明の第２の視点に係る端末装置は、
アドホックネットワークシステムにおける第１の端末装置であって、
前記第１の端末装置から、前記第１の端末装置を中心とする正六角形状の第１のクラスタの辺上に位置する第２の端末装置までの、第１の通信経路を探索する第１の通信経路探索部と、
前記第１の端末装置から、前記第１の端末装置が辺上に位置する正六角形状の第２のクラスタの辺上に位置する第３の端末装置までの、第２の通信経路を探索する第２の通信経路探索部と、
前記第１の通信経路および前記第２の通信経路を保持する記憶部と、を備える。
【００１４】
本発明の第３の視点に係るプログラムは、
アドホックネットワークシステムにおける第１の端末装置から、前記第１の端末装置を中心とする正六角形状の第１のクラスタの辺上に位置する第２の端末装置までの、第１の通信経路を探索する第１の探索処理と、
前記第１の端末装置から、前記第１の端末装置が辺上に位置する正六角形状の第２のクラスタの辺上に位置する第３の端末装置までの、第２の通信経路を探索する第２の探索処理と、を前記第１の端末装置に設けられたコンピュータに対して実行させる。なお、プログラムは、非トランジエントなコンピュータ読み取り可能な記録媒体（Non-Transient Computer-Readable Storage Device）に記録されたプログラム製品として提供することができる。
【発明の効果】
【００１５】
本発明に係る通信経路決定方法、端末装置およびプログラムによると、アッドホックネットワークにおいて、クラスタ間の境界付近におけるネットワークの輻輳を抑えつつ通信経路を決定することが可能となる。
【図面の簡単な説明】
【００１６】
【図１】実施形態に係る端末装置の構成を一例として示すブロック図である。
【図２】実施形態に係る端末装置における位置情報取得部および識別情報取得部の動作を一例として示す図である。
【図３】実施形態に係る端末装置における第１の通信経路探索部の動作を一例として示す図である。
【図４】実施形態に係る端末装置における第２の通信経路探索部の動作を一例として示す図である。
【図５】実施形態に係る端末装置における記憶部が保持する情報を一例として示す図である。
【図６】実施形態に係る端末装置に基づく通信経路決定動作を一例として示すフロー図である。
【図７】実施形態に係る端末装置に基づく通信経路決定動作について説明するための図である。
【図８】クラスタリング技術に基づく関連技術における、クラスタの構成を例示する図である。
【発明を実施するための形態】
【００１７】
はじめに、本発明の概要について説明する。なお、この概要に付記する図面参照符号は、専ら理解を助けるための例示であり、本発明を図示の態様に限定することを意図するものではない。
【００１８】
図１は、本発明に係る端末装置の構成を一例として示すブロック図である。図１を参照すると、端末装置（ＴＥ）は、アドホックネットワークシステムにおける端末装置であって、第１の通信経路探索部（１１）、第２の通信経路探索部（１２）、記憶部（１３）、位置情報取得部（１４）、および、識別情報取得部（１５）を備える。
【００１９】
図３は、第１の通信経路探索部（１１）の動作を説明するための図である。図３（ａ）を参照すると、通信経路探索部（１１）は、端末装置（ＴＥ）自身である第１の端末装置（ＴＥ１）から、第１の端末装置（ＴＥ１）を中心とする正六角形状の第１のクラスタ（Ｃ１）の辺上に位置する第２の端末装置（例えばＴＥ２）までの、第１の通信経路（例えばＰ１）を探索する。
【００２０】
図４は、第２の通信経路探索部（１２）の動作を説明するための図である。図４（ｂ）を参照すると、通信経路探索部（１２）は、端末装置（ＴＥ）自身である第１の端末装置（ＴＥ１）から、第１の端末装置（ＴＥ１）が辺上に位置する正六角形状の第２のクラスタ（Ｃ２ａ〜Ｃ２ｆ）の辺上に位置する第３の端末装置（例えばＴＥ３）までの、第２の通信経路（例えばＰ２）を探索する。
【００２１】
記憶部（１３）は、通信経路探索部（１１）および通信経路探索部（１２）によって得られた、第１の通信経路（Ｐ１）および第２の通信経路（Ｐ２）を保持する。
【００２２】
図４（ｂ）において、第３の端末装置（ＴＥ３）は、第２のクラスタ（Ｃ２ａ）の辺のうちの、第１の端末装置（ＴＥ１）が位置する辺との間で頂点を共有しない辺上に位置することが好ましい。
【００２３】
図２は、位置情報取得部（１４）および識別情報取得部（１５）の動作を説明するための図である。図２（ａ）を参照すると、位置情報取得部（１４）は、第１の端末装置（ＴＥ１）との距離が第１のクラスタ（図３（ａ）のクラスタＣ１）の一辺の長さ（Ｒ）の少なくとも２倍（２Ｒ）の距離以内の他の端末装置の位置を示す位置情報を取得して記憶部（１３）に格納する。
【００２４】
通信経路探索部（１１）は、記憶部（１３）に格納された上記位置情報に基づいて、上記第１の通信経路（図３（ａ）の通信経路Ｐ１）を探索するようにしてもよい。また、通信経路探索部（１２）は、記憶部（１３）に格納された上記位置情報に基づいて、第２の通信経路（図４（ｂ）の通信経路Ｐ２）を探索するようにしてもよい。
【００２５】
図２を参照すると、識別情報取得部（１５）は、第１の端末装置（ＴＥ１）との距離が第１のクラスタ（図３（ａ）のクラスタＣ１）の一辺の長さ（Ｒ）の少なくとも２倍（２Ｒ）の距離以内の他の端末装置を識別する識別情報を取得して記憶部（１３）に格納する。
【００２６】
図７は、本発明に係る端末装置を備えたアドホックネットワークシステムにおいて、第１の端末装置から目的の端末装置までの通信経路を決定する動作を説明するための図である。図７を参照すると、まず、第１の端末装置（ＴＥ１）は、第１の端末装置（ＴＥ１）から、第１の端末装置（ＴＥ１）を中心とする正六角形状の第１のクラスタ（Ｃ１）の辺上に位置する第２の端末装置（例えば端末装置ＴＥ２ａ）までの、第１の通信経路（例えば通信経路Ｐ１ａ）を探索する。次に、第２の端末装置（ＴＥ２ａ）が、第２の端末装置（ＴＥ２ａ）から、第２の端末装置（ＴＥ２ａ）が位置する辺を第１のクラスタ（Ｃ１）との間で共有する正六角形状の第２のクラスタ（Ｃ２ｃ）の辺上に位置する第３の端末装置（例えば端末装置ＴＥ３ａ）までの、第２の通信経路を探索する。
【００２７】
このように、逐次的に通信経路を構築することで、第１の端末装置（ＴＥ１）から、目的の端末装置（非図示）までの通信経路が、例えば、第１の通信経路（Ｐ１ａ）および第２の通信経路（Ｐ２ａ）を含むようにして形成される。
【００２８】
本発明に係る端末装置によると、アッドホックネットワークにおいて、クラスタ間の境界におけるネットワークの輻輳を抑えつつ通信経路を決定することが可能となる。なぜなら、目的とする端末装置までの通信経路がクラスタ間の境界に位置する端末装置を経由して形成されるため、異なるクラスタに属する端末装置間で情報のやりとりによるネットワークの輻輳を回避することができるからである。
【００２９】
なお、本発明において、下記の形態が可能である。
[形態１］
上記第１の視点に係る通信経路決定方法のとおりである。
[形態２］
前記第３の端末装置は、前記第２のクラスタの辺のうちの、前記第２の端末装置が位置する辺との間で頂点を共有しない辺上に位置することが好ましい。
[形態３］
前記通信経路決定方法において、
前記第１の端末装置が、前記第１の端末装置との距離が前記第１のクラスタの一辺の長さの少なくとも２倍の距離以内の他の端末装置の位置を示す第１の位置情報を取得する工程を含み、
前記第１の探索工程において、前記第１の端末装置は、前記第１の位置情報に基づいて前記第１の通信経路を探索するようにしてもよい。
[形態４］
前記通信経路決定方法において、
前記第２の端末装置が、前記第２の端末装置との距離が前記距離以内の他の端末装置の位置を示す第２の位置情報を取得する工程を含み、
前記第２の探索工程において、前記第２の端末装置は、前記第２の位置情報に基づいて前記第２の通信経路を探索するようにしてもよい。
[形態５］
前記通信経路決定方法において、
前記第１の端末装置が、前記第１の端末装置との距離が前記第１のクラスタの一辺の長さの少なくとも２倍の距離以内の他の端末装置を識別する第１の識別情報を取得する工程を含み、
前記目的の端末装置を示す情報が前記第１の識別情報に含まれない場合に、前記第１の端末装置は前記第１の通信経路を探索するようにしてもよい。
[形態６］
前記通信経路決定方法において、
前記第２の端末装置が、前記第２の端末装置との距離が前記距離以内の他の端末装置を識別する第２の識別情報を取得する工程を含み、
前記目的の端末装置を示す情報が前記第２の識別情報に含まれない場合に、前記第２の端末装置は前記第２の通信経路を探索するようにしてもよい。
[形態７］
前記通信経路決定方法において、
前記第３の端末装置が、前記第３の端末装置から、前記第３の端末装置が位置する辺を前記第２のクラスタとの間で共有する正六角形の第３のクラスタの辺上に位置する第４の端末装置までの、第３の通信経路を探索する工程を含み、
前記第１の端末装置から前記目的の端末装置までの通信経路が、さらに前記第３の通信経路を含んでいてもよい。
[形態８］
前記通信経路決定方法において、
前記第３の端末装置が、前記第３の端末装置との距離が前記距離以内の他の端末装置を識別する第３の識別情報を取得する工程を含み、
前記目的の端末装置を示す情報が前記第３の識別情報に含まれない場合に、前記第３の端末装置は前記第３の通信経路を探索するようにしてもよい。
[形態９］
上記第２の視点に係る端末装置のとおりである。
[形態１０］
前記第３の端末装置は、前記第２のクラスタの辺のうちの、前記第１の端末装置が位置する辺との間で頂点を共有しない辺上に位置することが好ましい。
[形態１１］
前記第１の端末装置は、前記第１の端末装置との距離が前記第１のクラスタの一辺の長さの少なくとも２倍の距離以内の他の端末装置の位置を示す位置情報を取得して前記記憶部に格納する位置情報取得部を備えていてもよい。
[形態１２］
前記第１の通信経路探索部は、前記記憶部に格納された前記位置情報に基づいて、前記第１の通信経路を探索するようにしてもよい。
[形態１３］
前記第２の通信経路探索部は、前記記憶部に格納された前記位置情報に基づいて、前記第２の通信経路を探索するようにしてもよい。
[形態１４］
前記第１の端末装置は、前記第１の端末装置との距離が前記第１のクラスタの一辺の長さの少なくとも２倍の距離以内の他の端末装置を識別する識別情報を取得して前記記憶部に格納する識別情報取得部を備えていてもよい。
[形態１５］
上記第３の視点に係るプログラムのとおりである。
[形態１６］
上記プログラムにおいて、前記第２の端末装置は、前記第２のクラスタの辺のうちの、前記端末装置が位置する辺との間で頂点を共有しない辺上に位置することが好ましい。
[形態１７］
上記プログラムにおいて、
前記第１の端末装置との距離が前記第１のクラスタの一辺の長さの少なくとも２倍の距離以内の他の端末装置の位置を示す位置情報を取得する処理を前記コンピュータに実行させ、
前記第１の探索処理において、前記位置情報に基づいて前記第１の通信経路を探索するようにしてもよい。
[形態１８］
上記プログラムは、前記第２の探索処理において、前記位置情報に基づいて、前記第２の通信経路を探索するようにしてもよい。
【００３０】
（実施形態）
実施形態に係る端末装置について、図面を参照して説明する。図１は、本実施形態の端末装置ＴＥの構成を一例として示すブロック図である。図１を参照すると、アドホックネットワークシステムにおける端末装置ＴＥは、通信経路探索部１１、１２、記憶部１３、位置情報取得部１４、および、識別情報取得部１５を備える。
【００３１】
通信経路探索部１１は、端末装置ＴＥから、端末装置ＴＥを中心とする正六角形状の第１のクラスタの辺上に位置する第２の端末装置までの、第１の通信経路を探索する。一方、通信経路探索部１２は、端末装置ＴＥから、端末装置ＴＥが辺上に位置する正六角形状の第２のクラスタの辺上に位置する第３の端末装置までの、第２の通信経路を探索する。
【００３２】
記憶部１３は、通信経路探索部１１、１２によって得られた、第１および第２の通信経路を保持する。
【００３３】
位置情報取得部１４は、端末装置ＴＥとの距離が第１のクラスタの一辺の長さの少なくとも２倍の距離以内の他の端末装置の位置を示す位置情報を取得して記憶部１３に格納する。通信経路探索部１１は、記憶部１３に格納された上記位置情報に基づいて、上記第１の通信経路を探索する。また、通信経路探索部１２は、記憶部１３に格納された上記位置情報に基づいて、上記第２の通信経路を探索する。
【００３４】
識別情報取得部１５は、端末装置ＴＥとの距離が第１のクラスタの一辺の長さの少なくとも２倍の距離以内の他の端末装置を識別する識別情報を取得して記憶部１３に格納する。
【００３５】
以下では、端末装置ＴＥ（図１）の各部の動作、および、複数の端末装置ＴＥが配置されたアドホックネットワークシステムにおける通信経路の決定動作について、図２〜図７を参照しつつさらに詳細に説明する。
【００３６】
図２は、位置情報取得部１４および識別情報取得部１５の動作を一例として示す図である。図２（ａ）を参照すると、位置情報取得部１４および識別情報取得部１５は、それぞれ、端末装置ＴＥから半径２Ｒ以内に存在する他の端末装置の位置情報および識別情報を取得する。Ｒは後述のクラスタの形状を示す正六角形の一辺の長さを表す。
【００３７】
ここで、アドホックネットワークシステム内の各端末装置は、予め自身の位置を示す情報を保持しているものとする。なお、自身の位置を示す情報を保持していない端末装置は、例えば、特許文献1の方法に基づいて、自身の位置を推定するようにしてもよい。
【００３８】
各端末装置に設けられた位置情報取得部１４および識別情報取得部１５は、図２（ｂ）に示すフロー図に従って、自身から半径２Ｒ以内の距離に存在する他の端末装置に関する情報（例えば、位置情報、端末装置番号）を取得する。図２（ｂ）を参照すると、位置情報取得部１４は、アドホック通信によって、隣接端末装置に情報パケットを転送し、その端末装置の位置情報を取得する（ステップＳ１１）。
【００３９】
位置情報取得部１４は、取得した端末装置の位置が自身から半径２Ｒ以内の距離であるかどうかを判定する（ステップＳ１２）。取得した端末装置の位置が自身から半径２Ｒ以内でない場合（ステップＳ１２のＮｏ）、位置情報取得部１４は、その経路の調査を終了する（ステップＳ１５）。
【００４０】
一方、取得した端末装置の位置が自身から半径２Ｒ以内である場合（ステップＳ１２のＹｅｓ）、位置情報取得部１４は、取得した端末装置が未登録の端末装置であるかどうかを判定する（ステップＳ１３）。取得した端末装置が未登録の端末装置でない場合（ステップＳ１３のＮｏ）、位置情報取得部１４は、その経路の調査を終了する（ステップＳ１５）。
【００４１】
一方、取得した端末装置が未登録の端末装置である場合（ステップＳ１３のＹｅｓ）、位置情報取得部１４は、経路を遡り、取得した端末装置の情報（端末装置番号、位置情報等）を記憶部１３に登録する（ステップＳ１４）。
【００４２】
図３は、第１の通信経路探索部１１の動作を一例として示す図である。図３（ａ）を参照すると、発信端末である端末装置（ＴＥ１とする。）の通信経路探索部１１は、一辺の長さＲの正六角形の各辺への経路を発信用の経路として探索する。
【００４３】
図３（ｂ）を参照すると、位置情報取得部１４は、図２（ｂ）に示したフロー図に従って半径２Ｒ以内に存在する他の端末装置の位置情報を取得して記憶部１３に格納する（ステップＳ２１）。次に、通信経路探索部１１は、半径２Ｒ以内に存在する各端末装置の位置情報に基づいて、正六角形のクラスタＣ１の中心に位置する発信端末装置ＴＥ１から正六角形の各辺上に存在する端末装置（例えば端末装置ＴＥ２）への経路を探索する（ステップＳ２２）。
【００４４】
ここで、通信経路探索部１１は、端末装置ＴＥ１から端末装置ＴＥ２への通信経路を探索する方法として、一例として、特許文献２に記載された方法を用いることができる。ただし、通信経路探索部１１が用いる探索方法は、これに限定されない。
【００４５】
また、通信経路探索部１１は、探索した経路を示す経路情報を記憶部１３に格納する（ステップＳ２３）。なお、経路が維持される確率を向上させるために、通信経路探索部１１は、端末装置Ｔ１から各辺の複数の端末装置に至る複数の経路を取得し、記憶部１３に格納するようにしてもよい。
【００４６】
図４は、第２の通信経路探索部１２の動作を一例として示す図である。図４（ａ）を参照すると、クラスタ（例えばクラスタＣ２ａ）の一辺上に位置する端末装置（端末装置ＴＥ１とする）は、クラスタＣ２ａの辺であって、自身が存在する辺と頂点を共有しない辺（すなわち、自身が存在する辺と向かい合った辺およびその両隣の辺）上に位置する端末装置（例えば図４（ａ）の端末装置ＴＥ３）への経路を探索する。
【００４７】
図４（ｃ）を参照すると、端末装置ＴＥ１の位置情報取得部１４は、図２（ｂ）に示したフロー図に従って半径２Ｒ以内に存在する他の端末装置の位置情報を取得して記憶部１３に格納する（ステップＳ３１）。端末装置ＴＥ１の通信経路探索部１２は、記憶部１３の記録された他の端末の位置情報に基づいて、クラスタＣ２ａの辺であって、自身が存在する辺の対辺およびその両隣の辺上に位置する端末装置ＴＥ３への経路を探索する（ステップＳ３２）。
【００４８】
ここで、通信経路探索部１２は、端末装置ＴＥ１から端末装置ＴＥ３への通信経路を探索する方法として、一例として、特許文献２に記載された方法を用いることができる。ただし、通信経路探索部１２が用いる探索方法は、これに限定されない。
【００４９】
また、通信経路探索部１２は、探索した経路を示す経路情報を記憶部１３に格納する（ステップＳ３３）。なお、経路が維持される確率を向上させるために、通信経路探索部１２は、端末装置Ｔ１から、端末装置Ｔ１が存在する辺の対辺およびその両隣の辺各辺に存在する複数の端末装置に至る、複数の経路を取得し、記憶部１３に格納するようにしてもよい。
【００５０】
通信経路探索部１２は、図４（ｃ）のフロー図に従った経路の探索を、図４（ａ）のクラスタＣ２ａ〜Ｃ２ｆのそれぞれについて行う。
【００５１】
図５は、各端末装置の記憶部１３に格納された情報を示す図である。各端末装置の記憶部１３は、図２ないし図４のフロー図に示した動作によって得られた、周辺の端末装置の情報を保持する。
【００５２】
図５（ａ）、（ｂ）を参照すると、記憶部１３は、位置情報取得部１４および識別情報取得部１５により、図２（ｂ）のフロー図に従って得られた情報（情報Ａ）を保持する。すなわち、記憶部１３は、自身から距離２Ｒ以内の距離に存在するすべて端末装置の情報（位置情報、識別子等）を保持する。
【００５３】
また、図５（ａ）、（ｂ）を参照すると、記憶部１３は、通信経路探索部１１により、図３（ｂ）のフロー図に従って得られた情報（情報Ｂ）を保持する。すなわち、記憶部１３は、自身から、自身を中心とする一辺の長さＲの正六角形のクラスタの各辺上に位置する端末装置への経路に関する情報（情報Ｂ）を保持する。
【００５４】
さらに、図５（ａ）〜（ｃ）を参照すると、記憶部１３は、通信経路探索部１２により、図４（ｃ）のフロー図に従って得られた情報（情報Ｃ）を保持する。すなわち、記憶部１３は、自身が一辺上に存在する一辺の長さＲの正六角形のクラスタＣ２ａ〜Ｃ２ｆにおいて、自身から、自身が存在する辺に対向する辺とその両隣の辺上に位置する端末装置への経路に関する情報（情報Ｃ）を保持する。
【００５５】
また、記憶部１３は、図６を参照して後述する、クラスタを単位とする途中経路情報（情報Ｄ）も保持する。
【００５６】
図６は、アドホックネットワークシステムにおける各端末装置が図５に示す情報を保持している場合において、発信端末装置（端末装置ＴＥ１とする。）から目的とする端末装置までの通信経路を決定するときの動作を示すフロー図である。
【００５７】
図６を参照すると、端末装置ＴＥ１は、目的とする端末装置の識別子（例えば端末装置番号）を受け付ける（ステップＳ４１）。
【００５８】
次に、端末装置ＴＥ１は、端末装置ＴＥ１が保持する情報Ａ（図５（ｂ））に目的とする端末装置が含まれるかどうかを判定する（ステップＳ４２）。目的とする端末装置の情報が情報Ａに含まれる場合（ステップＳ４２のＹｅｓ）、端末装置ＴＥ１は、目的とする端末装置までの経路を確定し、経路探索を終了する（ステップＳ４３）。端末装置ＴＥ１は、目的とする端末装置までの経路を、特許文献２に記載された方法に基づいて決定してもよいし、これ以外の方法を用いて決定するようにしてもよい。
【００５９】
一方、目的とする端末装置が情報Ａに含まれない場合（ステップＳ４２のＮｏ）、端末装置ＴＥ１は、情報Ｂ（図５（ｂ））に基づいて、自身を中心とするクラスタの各辺に存在する端末装置に対して、目的とする端末装置の情報と経路情報を送付する（ステップＳ４４）。
【００６０】
端末装置ＴＥ１から上記情報を送付された端末装置（端末装置ＴＥｎ；ｎの初期値は２）は、自身が保持する情報Ａ（図５（ｂ））に、目的とする端末装置が含まれるかどうかを判定する（ステップＳ４５）。目的とする端末装置の情報が情報Ａに含まれる場合（ステップＳ４５のＹｅｓ）、端末装置ＴＥｎは、目的とする端末装置までの経路を確定し、経路探索を終了する（ステップＳ４６）。端末装置ＴＥｎは、目的とする端末装置までの経路を、特許文献２に記載された方法に基づいて決定してもよいし、これ以外の方法を用いて決定するようにしてもよい。
【００６１】
一方、目的とする端末装置が情報Ａに含まれない場合（ステップＳ４５のＮｏ）、端末装置ＴＥｎは、情報Ｃ（図５（ｂ））に基づいて、自身が一辺に存在するクラスタの対辺およびその両隣の辺に位置する端末装置ＴＥｎ＋１に対して、目的とする端末装置の情報と経路情報を送付するとともに（ステップＳ４７）、端末装置ＴＥｎから端末装置ＴＥｎ＋１への通信経路（すなわち、クラスタ単位での通信経路）を情報Ｄとして保持し、ステップＳ４５に戻る。
【００６２】
図７は、複数の通信経路が存在する場合に優先すべき通信経路を選択する方法を示す。複数の通信経路が存在する場合には、通信経路の短い方を選択することが好ましい。例えば、目的とする端末装置に至るまでに、途中で通過するクラスタの個数が少ない通信経路を選択するようにしてもよい。
【００６３】
図７を参照すると、発信端末である端末装置ＴＥ１から、端末装置ＴＥ２ａを経由して端末装置ＴＥ３ａに至る通信経路Ｒａは、通信経路Ｐ１ａおよびＰ２ａを含む。一方、端末装置ＴＥ１から、端末装置ＴＥ２ｂ、ＴＥ３ｂを経由して端末装置ＴＥ４ｂに至る通信経路Ｒｂは、通信経路Ｐ１ｂ、Ｐ２ｂおよびＰ３ｂを含む。このような場合には、通信経路Ｐｂよりも通信経路Ｐａを優先しつつ、目的とする端末装置までの通信経路を決定することが好ましい。
【００６４】
本発明においては、発信の際には、その発信端末装置を中心として、一定の辺の長さＲの正六角形をその端末装置のクラスタとし、通信経路として、その正六角形の辺上にある端末装置が次のクラスタへの最短経路を提示することにより、目的の端末装置への通信を行う。このとき、各クラスタは、図８を参照して説明した関連技術のようにトポロジに依存せず、発信端末装置にのみ依存することから、クラスタ間の輻輳が軽減される。
【００６５】
すなわち、本発明によると、トポロジに依存せず、発信端末装置の位置のみに依存したクラスタアドホックネットワークを実現することができる。また、本発明によると、端末装置の全検索による余計な制御パケットを削減することもできる。他の端末装置が発信した場合にも、他の端末のクラスタはその発信位置のみに依存するため、クラスタ間の輻輳を回避することができる。
【００６６】
本発明によると、大規模なアドホックネットワーク通信において、目的の端末装置への通信の際、探査経路が少なく、かつ、関連技術におけるクラスタリング方式に基づくアドホックネットワークと比較して制御パケットを削減し、クラスタ間の輻輳を防ぐことができる。
【００６７】
なお、上記の特許文献等の先行技術文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素（各請求項の各要素、各実施形態の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし、選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【００６８】
１１  通信経路探索部
１２  通信経路探索部
１３  記憶部
１４  位置情報取得部
１５  識別情報取得部
Ｃ１、Ｃ２ａ〜Ｃ２ｆ  クラスタ
Ｃ１０１〜Ｃ１０３    クラスタ
Ｐ１、Ｐ２    通信経路
Ｐ１ａ、Ｐ１ｂ、Ｐ２ａ、Ｐ２ｂ、Ｐ３ｂ    通信経路
Ｒａ、Ｒｂ    通信経路
ＴＥ、ＴＥ１〜ＴＥ３  端末装置
ＴＥ２ａ、ＴＥ２ｂ、ＴＥ３ａ、ＴＥ３ｂ、ＴＥ４ｂ    端末装置
【図１】
2013162463.tif 000003
【図２】
2013162463.tif 000004
【図３】
2013162463.tif 000005
【図４】
2013162463.tif 000006
【図５】
2013162463.tif 000007
【図６】
2013162463.tif 000008
【図７】
2013162463.tif 000009
【図８】
2013162463.tif 000010