JP7003539B2 - アドホックネットワーク経路構築システム、ノード、センターノード及びアドホックネットワーク経路構築方法 - Google Patents

Description

本開示は、１個のセンターノード及び複数のノード（ネクストホップノード）を有するアドホックネットワーク経路構築システム、上記ノード（ネクストホップノード）、上記センターノード及び上記アドホックネットワーク経路構築方法に関する。

１個のセンターノード及び複数のネクストホップノードを有するアドホックネットワーク経路構築システムが知られている（特許文献１乃至特許文献４）。

特開２００６－２１１２００号公報 国際公開ＷＯ２００８／１０５０３９号公報 特開２０１７－８５６４８号公報 特開２０１７－１０２６２７号公報

アドホックネットワーク経路構築システムにおいては、経路探索のパケットを複数回フラッディングする。従って、ネットワークに掛かる負荷を軽減することが望ましい。また、アドホックネットワークは、専用の基地局を含むインフラに依存しないネットワークであるため、短時間で、アドホックネットワークの経路を新規に構築することが望ましい。

以上のような事情に鑑み、本開示の目的は、アドホックネットワーク経路構築システムにおいて、ネットワークに掛かる負荷を軽減するとともに、リアルタイム且つ短時間で、アドホックネットワークの経路を新規に構築することにある。

本開示の一形態に係るアドホックネットワーク経路構築システムは、
１個のセンターノードと、
複数のネクストホップノードと
を具備するアドホックネットワーク経路構築システムであって、
前記センターノードは、
前記センターノードのMAC（Media Access Control）アドレス及び位置情報を記述したデータ部と、生存時間として正の整数値を記述したヘッダ部とを含むリクエストパケットを生成し、
前記センターノードと通信可能なエリアに位置する１以上のネクストホップノードに、前記リクエストパケットを送信し、
各前記ネクストホップノードは、
前記リクエストパケットを受信し、
前記リクエストパケットの前記ヘッダ部に記述された前記生存時間の値が０であると判断すると、
前記受信したリクエストパケットの前記データ部に記述された全ての前記MACアドレス及び全ての前記位置情報を記述したデータ部を含むリプライパケットを生成し、
前記受信したリクエストパケットの送信元であるリクエスト送信元ノードに、前記リプライパケットを送信し、
前記リプライパケットの送信元である前記ネクストホップノードを除く各前記ネクストホップノードは、さらに、
前記リクエスト送信先ノードから、前記リプライパケットを受信し、
前記リクエスト送信元ノードに、前記受信したリプライパケットを送信し、
前記センターノードは、さらに、
１以上の前記リクエスト送信先ノードから、前記リプライパケットを受信すると、
前記受信した１以上のリプライパケットの前記データ部に記述された前記全てのMACアドレス及び前記全ての位置情報に基づき、定期的に、ルーティングテーブルを作成する。

本形態によれば、ネクストホップノードは、受信したリクエストパケットの生存時間の値が０のとき、センターノードに向けてリプライパケットを送信する。また、センターノードは、リプライパケットを最初に受信すると、ルーティングテーブルを定期的に作成する。これにより、センターノードがリプライパケットを最初に受信するまでの時間が短くなり、センターノードがリプライパケットを受信する頻度が高くなり、ルーティングテーブルを最初に作成するまでの時間が短くなる。これにより、センターノードは、リアルタイムに、短時間に、アドホックネットワークの経路を新規に構築することができる。

本形態によれば、さらに、センターノードがルーティングテーブルを作成する。これにより、センターノードだけが、経路を構築する際に必要な情報を格納する。そのため、各ネクストホップノードが消費するリソースを軽減することができる。また、ネットワーク内で送受信されるパケット量が抑えられ、ネットワークに掛かる負荷が軽減される。

各前記ネクストホップノードは、
前記リクエストパケットの前記ヘッダ部に記述された前記生存時間の値が０であると判断すると、さらに、
前記リクエストパケットの送信先となるリクエスト送信先ノードの有無を判断し、
前記リクエスト送信先ノードが有ると判断すると、前記受信したリクエストパケットの前記データ部に前記ネクストホップノード自身のMACアドレス及び位置情報を追加的に記述し、前記受信したリクエストパケットの前記ヘッダ部の前記生存時間をリセットしたリクエストパケットを、前記リクエスト送信先ノードに送信する。

さらに、本形態によれば、ネクストホップノードは、受信したリクエストパケットの生存時間の値が０のとき、センターノードに向けてリプライパケットを送信し、且つ、リクエストパケットの生存時間をリセットして終端ノードに向けてリクエストパケットを送信する。これにより、センターノードに向けてリプライパケットを送信したネクストホップノードから先のネクストホップノードにも、経路を構築することができる。

各前記ネクストホップノードは、
前記リクエストパケットの前記ヘッダ部に記述された前記生存時間の値が０でないと判断すると、
前記リクエストパケットの送信先となるリクエスト送信先ノードの有無を判断し、
前記リクエスト送信先ノードが有ると判断すると、前記受信したリクエストパケットの前記データ部に前記ネクストホップノード自身のMACアドレス及び位置情報を追加的に記述し、前記受信したリクエストパケットの前記ヘッダ部に前記生存時間として記述された値をデクリメントしたリクエストパケットを、前記リクエスト送信先ノードに送信する
アドホックネットワーク経路構築システム。

さらに、本実施形態によれば、ネクストホップノードは、受信したリクエストパケットの生存時間の値が０でないとき、リクエストパケットの生存時間をデクリメントして、ネクストホップノードにリクエストパケットを送信する。リクエストパケットの生存時間をデクリメントすることで、リクエストパケットが生存時間を持たない（即ち、終端ノードだけがリプライパケットを生成する）と仮定した場合に比べて、センターノードがリプライパケットを最初に受信するまでの時間が短くなり、センターノードがリプライパケットを受信する頻度が高くなり、ルーティングテーブルを最初に作成するまでの時間が短くなる。これにより、センターノードは、リアルタイムに、短時間に、アドホックネットワークの経路を新規に構築することができる。

各前記ネクストホップノードは、
前記リクエスト送信先ノードが無いと判断すると、前記ネクストホップノード自身を終端ノードと判断し、
前記終端ノードは、
前記受信したリクエストパケットの前記データ部に記述された全ての前記MACアドレス及び全ての前記位置情報を記述したデータ部を含むリプライパケットを生成し、
前記受信したリクエストパケットの送信元であるリクエスト送信元ノードに、前記リプライパケットを送信する
アドホックネットワーク経路構築システム。

本形態によれば、センターノードがルーティングテーブルを作成する。これにより、センターノードだけが、経路を構築する際に必要な情報を格納する。そのため、各ネクストホップノードが消費するリソースを軽減することができる。また、ネットワーク内で送受信されるパケット量が抑えられ、ネットワークに掛かる負荷が軽減される。

各前記ネクストホップノードは、
前記リクエスト送信先ノードの有無を判断する際、
前記リクエスト送信元ノードの位置情報を、前記受信したリクエストパケットの前記データ部から読み出し、
前記リクエスト送信元ノードの位置情報及び前記ネクストホップノード自身の位置情報に基づき、前記リクエスト送信元ノードの位置から離れた位置にあるリクエスト送信先ノードの有無を判断する。

本形態によれば、全てのネクストホップノードは、リクエスト送信元ノードの位置から離れた位置にあるリクエスト送信先ノードにのみ、リクエストパケットを送信する。これにより、各ネクストホップノードが多数のネクストホップノードからリクエストパケットを受信する可能性を減らすことができる。

各前記ネクストホップノードは、
前記リクエスト送信先ノードの有無を判断する際、
前記リクエスト送信元ノードの位置と前記ネクストホップノード自身の位置とを結んだ線分と直交し且つ前記ネクストホップノード自身の前記位置を通過する直線で、前記ネクストホップノード自身が通信可能なエリアを分断し、前記分断した通信可能なエリアのうち前記リクエスト送信元ノードの位置を含まないエリアに位置するリクエスト送信先ノードの有無を判断する。

本形態によれば、全てのネクストホップノードは、通信可能エリアのうちの一部に位置するネクストホップノードにのみ、リクエストパケットを送信する。これにより、各ネクストホップノードが多数のネクストホップノードからリクエストパケットを受信する可能性を減らすことができる。

各前記ネクストホップノードは、
複数のリクエスト送信元ノードから前記リクエストパケットを受信した場合、
何れか１つの前記受信したリクエストパケットの前記データ部に前記ネクストホップノード自身のMACアドレス及び位置情報を追加的に記述し、前記記述したリクエストパケットを、前記リクエスト送信先ノードに送信する。

本形態によれば、全てのネクストホップノードは、リクエストパケットを１回しか送信しない。これにより、各ネクストホップノードが多数のネクストホップノードからリクエストパケットを受信する可能性を減らすことができる。

各前記ネクストホップノードは、
前記リクエスト送信先ノードの有無を判断する際、
前記ネクストホップノード自身と通信可能なエリアに位置する１以上の別のネクストホップノードに、HELLOパケットを送信し、
前記HELLOパケットに対する応答パケットとして、応答元である別のネクストホップノードの位置情報を追加的に記述した応答パケットを要求し、
前記１以上の別のネクストホップノードから、前記別のネクストホップノードの位置情報を追加的に記述した応答パケットを受信し、
前記受信した応答パケットに追加的に記述された前記別のネクストホップノードの位置情報に基づき、前記リクエスト送信先ノードの有無を判断する。

本形態によれば、ネクストホップノードは、１以上の別のネクストホップノードに、HELLOパケットに対する応答パケットとして、応答元である別のネクストホップノードの位置情報を追加的に記述した応答パケットを要求する。これにより、ネクストホップノードは、リクエストパケットを送信する前に、別のネクストホップノードの位置情報を取得することができるので、リクエストパケットを送信する対象を確実に絞り込むことができる。

本開示の一形態に係るノード（ネクストホップノード）は、
１個のセンターノードと、複数のノードとを有するアドホックネットワーク経路構築システムに含まれる各ノードであって、
前記センターノードから、前記センターノードのMAC（Media Access Control）アドレス及び位置情報を記述したデータ部と、生存時間として正の整数値を記述したヘッダ部とを含むリクエストパケットを受信し、
前記リクエストパケットの前記ヘッダ部に記述された前記生存時間の値が０であると判断すると、
前記受信したリクエストパケットの前記データ部に記述された全ての前記MACアドレス及び全ての前記位置情報を記述したデータ部を含むリプライパケットを生成し、
前記受信したリクエストパケットの送信元であるリクエスト送信元ノードに、前記リプライパケットを送信する
パケット制御部を具備する。

前記パケット制御部は、
前記リクエストパケットの前記ヘッダ部に記述された前記生存時間の値が０であると判断すると、さらに、
前記リクエストパケットの送信先となるリクエスト送信先ノードの有無を判断し、
前記リクエスト送信先ノードが有ると判断すると、前記受信したリクエストパケットの前記データ部に前記ノード自身のMACアドレス及び位置情報を追加的に記述し、前記受信したリクエストパケットの前記ヘッダ部の前記生存時間をリセットしたリクエストパケットを、前記リクエスト送信先ノードに送信する。

前記パケット制御部は、
前記リクエストパケットの前記ヘッダ部に記述された前記生存時間の値が０でないと判断すると、
前記リクエストパケットの送信先となるリクエスト送信先ノードの有無を判断し、
前記リクエスト送信先ノードが有ると判断すると、前記受信したリクエストパケットの前記データ部に前記ネクストホップノード自身のMACアドレス及び位置情報を追加的に記述し、前記受信したリクエストパケットの前記ヘッダ部に前記生存時間として記述された値をデクリメントしたリクエストパケットを、前記リクエスト送信先ノードに送信する。

前記パケット制御部は、
前記リクエスト送信先ノードが無いと判断すると、前記ノード自身を終端ノードと判断し、
前記終端ノードと判断すると、
前記受信したリクエストパケットの前記データ部に記述された全ての前記MACアドレス及び全ての前記位置情報を記述したデータ部を含むリプライパケットを生成し、
前記受信したリクエストパケットの送信元であるリクエスト送信元ノードに、前記リプライパケットを送信する。

本開示の一形態に係るセンターノードは、
１個のセンターノードと、
複数のネクストホップノードと
を具備するアドホックネットワーク経路構築システムであって、
前記センターノードは、
前記センターノードのMAC（Media Access Control）アドレス及び位置情報を記述したデータ部と、生存時間として正の整数値を記述したヘッダ部とを含むリクエストパケットを生成し、
前記センターノードと通信可能なエリアに位置する１以上のネクストホップノードに、前記リクエストパケットを送信し、
各前記ネクストホップノードは、
前記リクエストパケットを受信し、
前記リクエストパケットの前記ヘッダ部に記述された前記生存時間の値が０であると判断すると、
前記受信したリクエストパケットの前記データ部に記述された全ての前記MACアドレス及び全ての前記位置情報を記述したデータ部を含むリプライパケットを生成し、
前記受信したリクエストパケットの送信元であるリクエスト送信元ノードに、前記リプライパケットを送信し、
前記リプライパケットの送信元である前記ネクストホップノードを除く各前記ネクストホップノードは、さらに、
前記リクエスト送信先ノードから、前記リプライパケットを受信し、
前記リクエスト送信元ノードに、前記受信したリプライパケットを送信し、
前記センターノードは、さらに、
１以上の前記リクエスト送信先ノードから、前記リプライパケットを受信すると、
前記受信した１以上のリプライパケットの前記データ部に記述された前記全てのMACアドレス及び前記全ての位置情報に基づき、定期的に、ルーティングテーブルを作成する
アドホックネットワーク経路構築システム
に含まれる。

本開示の一形態に係る経路構築方法は、
１個のセンターノードと、
複数のネクストホップノードと
を具備するアドホックネットワーク経路構築方法であって、
前記センターノードは、
前記センターノードのMAC（Media Access Control）アドレス及び位置情報を記述したデータ部と、生存時間として正の整数値を記述したヘッダ部とを含むリクエストパケットを生成し、
前記センターノードと通信可能なエリアに位置する１以上のネクストホップノードに、前記リクエストパケットを送信し、
各前記ネクストホップノードは、
前記リクエストパケットを受信し、
前記リクエストパケットの前記ヘッダ部に記述された前記生存時間の値が０であると判断すると、
前記受信したリクエストパケットの前記データ部に記述された全ての前記MACアドレス及び全ての前記位置情報を記述したデータ部を含むリプライパケットを生成し、
前記受信したリクエストパケットの送信元であるリクエスト送信元ノードに、前記リプライパケットを送信し、
前記リプライパケットの送信元である前記ネクストホップノードを除く各前記ネクストホップノードは、さらに、
前記リクエスト送信先ノードから、前記リプライパケットを受信し、
前記リクエスト送信元ノードに、前記受信したリプライパケットを送信し、
前記センターノードは、さらに、
１以上の前記リクエスト送信先ノードから、前記リプライパケットを受信すると、
前記受信した１以上のリプライパケットの前記データ部に記述された前記全てのMACアドレス及び前記全ての位置情報に基づき、定期的に、ルーティングテーブルを作成する。

本開示によれば、アドホックネットワーク経路構築システムにおいて、ネットワークに掛かる負荷を軽減するとともに、リアルタイム且つ短時間で、アドホックネットワークの経路を新規に構築することができる。

なお、ここに記載された効果は必ずしも限定されるものではなく、本開示中に記載されたいずれかの効果であってもよい。

情報処理装置のハードウェア構成を示す。 アドホックネットワーク経路構築システムの機能的構成を示す。 センターノードの動作フローを示す。 ネクストホップノードの動作フローを示す。 センターノード及びネクストホップノード（終端ノードを含む）の動作シーケンスを示す。 SFRREQパケットを示す。 既存のRREQパケットのヘッダを示す。 リクエスト送信エリア及びリクエスト送信不可エリアを模式的に示す。 SFRREPパケットを示す。 既存のRREPパケットのヘッダを示す。 センターノード及びネクストホップノード（生存時間ゼロノードを含む）の動作シーケンスを示す。

以下、図面を参照しながら、本開示の実施形態を説明する。

１．アドホックネットワーク経路構築システムの概要
アドホックネットワークは、専用の基地局を含むインフラに依存しないネットワークである。具体的には、アドホックネットワークは複数のノードを含み、複数のノードは、Wi-Fi（登録商標）やBluetooth（登録商標）やZigBee（登録商標）による端末装置（ノード）自体の中継機能を利用することにより相互に接続される。

典型的に、アドホックネットワークの経路を新規に構築するためには、複数の端末装置（ノード）のうち、特定の（任意の）１個のノードをセンターノードとする。センターノードは、センターノードと通信可能なエリアに位置する複数のノード（ネクストホップノード）に、経路探索のためのリクエストパケットをフラッディングする。

リクエストパケットを受信したノードは、ノード自身の端末情報を、受信したリクエストパケット内のバッファに追加的に記述する。ノードは、記述したリクエストパケットを、通信可能なエリアに位置する複数のノード（ネクストホップノード）にフラッディングする。このフラッディングの工程がホップの度に何度も繰り返される。

リクエストパケットを受信したノードは、ネクストホップノードが存在しない場合、ノード自身が終端ノードであると判断する。終端ノードは、リクエストパケットのバッファに蓄積された端末情報（リクエストパケット送信時に経由した複数のノード全ての端末情報）を記述したリプライパケットを生成する。終端ノードは、リプライパケットを、複数のネクストホップノード（リクエストパケット送信時に経由した複数のノードと同じ）を経由して、センターノードに送信する。

センターノードは、受信したリプライパケットに記述された、各ノードの端末情報に基づき、各ノード間の経路を計算し、ルーティングテーブル（経路表）を作成する。センターノードは、作成したルーティングテーブルをフラッディングし、全てのノードに供給する。各ノードはルーティングテーブルに基づき経路（ルート）を構築する。

このように、典型的に、アドホックネットワークの経路を新規に構築するためには、リクエストパケットをフラッディングする工程を何度も繰り返すため、ネットワークに掛かる負荷が高い。以上に鑑み、本実施形態によれば、アドホックネットワーク経路構築システムにおいて、ネットワークに掛かる負荷の軽減を図る。また、専用の基地局を含むインフラに依存しないアドホックネットワークは、例えば災害時などに用いられ得る。従って、リアルタイムに、短時間に、アドホックネットワークの経路を新規に構築することが望まれる。以上に鑑み、本実施形態によれば、短時間に、アドホックネットワークの経路の新規構築を図る。

２．情報処理装置のハードウェア構成
図１は、情報処理装置のハードウェア構成を示す。

ノードは、Wi-Fi（登録商標）やBluetooth（登録商標）やZigBee（登録商標）による中継機能を有する情報処理装置であり、典型的には、屋内設置型（モバイルで無い）の端末装置である。例えば、情報処理装置は、例えばデスクトップタイプのパーソナルコンピューター、ＭＦＰ（Multifunction Peripheral）等の画像形成装置、ファクシミリ、テレビジョン受像機、家電機器等である。

ノードとしての情報処理装置１０は、制御部１１と、制御部１１とバス１７を介して接続された表示部１２、ネットワークインターフェース１３、操作部１５、記憶部１６及び位置情報取得装置１４とを有する。

制御部１１は、ＣＰＵ（Central Processing Unit）等を含む。制御部１１のＣＰＵ（Central Processing Unit）は、コンピューター読み取り可能な非一過性の記憶媒体の一例であるＲＯＭ（Read Only Memory）に記録されたプログラムをＲＡＭ（Random Access Memory）にロードして実行する。

記憶部１６は、ＲＯＭ（Read Only Memory）と、ＲＡＭと、ＨＤＤ（Hard Disk Drive）などの大容量の記憶装置とを含む。ＲＯＭは、制御部１１が実行するプログラムやデータなどを固定的に格納する。ＲＡＭには、ＲＯＭに格納されたプログラムがロードされる。

表示部１２は、ＬＣＤ（Liquid Crystal Display）や有機ＥＬ（Electroluminescence）ディスプレイ等を含む。表示部１２は、制御部１１から受け取った情報に基づいて演算処理を行い、生成した画像信号を画面に表示する。表示部１２は外付けの表示装置でもよい。

操作部１５は、キーボード、マウス、タッチパネル及び／又は各種スイッチ等を含む。操作部１５は、ユーザーからの操作を検出して制御部１１に出力する。

ネットワークインターフェース１３は、Wi-Fi（登録商標）やBluetooth（登録商標）やZigBee（登録商標）を介して他の情報処理装置１０（ノード）と通信するためのインタフェースである。

位置情報取得装置１４は、情報処理装置１０自身の現在の位置情報を取得する。例えば、位置情報取得装置１４は、複数の無線ＬＡＮ（Local Area Network）アクセスポイントから送信されるWi-Fi（登録商標）の電波が情報処理装置１０に到達する周期をもとに、三角測量を用いて、情報処理装置１０の位置を計測する。あるいは、位置情報取得装置１４は、Bluetooth（登録商標）発信機（ビーコン）の電波が情報処理装置１０に到達する周期をもとに、情報処理装置１０の位置を計測する。また、位置情報取得装置１４は、ＧＰＳ（Global Positioning System）により、情報処理装置１０の位置を計測してもよい。

３．アドホックネットワーク経路構築システムの機能的構成
図２は、アドホックネットワーク経路構築システムの機能的構成を示す。

以下の説明において、センターノードとしての情報処理装置１０を「センターノード１０Ｃ」と称する。アドホックネットワークに含まれる複数のノードのうち、センターノード１０Ｃ以外の複数のノード１０を、センターノードと区別する目的で便宜的に、「ネクストホップノード１０Ｎ」と称することがある。すなわち、アドホックネットワーク経路構築システム１は、１個のセンターノード１０Ｃと、複数のネクストホップノード１０Ｎとを具備する。

センターノード１０Ｃは、ユーザー（管理者）が任意に決めることができる。パーソナルコンピューター等の端末装置（図示せず）は、ユーザーからの操作を受け付け、Wi-Fi（登録商標）やBluetooth（登録商標）やZigBee（登録商標）を介して、任意の情報処理装置１０にセンターノードとして機能するよう要求する。

センターノード１０Ｃは、コンピューター読み取り可能な非一過性の記憶媒体の一例であるＲＯＭに記憶された情報処理プログラムをＲＡＭにロードして実行することで、パケット制御部１０１Ｃ及び構築経路管理部１０２Ｃとして機能する。

ネクストホップノード１０Ｎは、コンピューター読み取り可能な非一過性の記憶媒体の一例であるＲＯＭに記憶された情報処理プログラムをＲＡＭにロードして実行することで、パケット制御部１０１Ｎ及び構築経路管理部１０２Ｎとして機能する。

センターノード１０Ｃのパケット制御部１０１Ｃは、センターノード１０ＣのMACアドレス及び位置情報を記述したデータ部と、生存時間として正の整数値を記述したヘッダ部とを含むSFRREQパケットを生成する。パケット制御部１０１Ｃは、センターノード１０Ｃと通信可能なエリアに位置する１以上のネクストホップノード１０Ｎに、SFRREQパケットを送信（フラッディング）する。

ネクストホップノード１０Ｎのパケット制御部１０１Ｎは、SFRREQパケットを受信し、SFRREQパケットのヘッダ部に記述された生存時間の値が０であるか否かを判断する。パケット制御部１０１Ｎは、生存時間の値が０でないと判断すると、SFRREQパケットの送信先となるネクストホップノード１０Ｎ（リクエスト送信先ノード）の有無を判断する。パケット制御部１０１Ｎは、リクエスト送信先ノードが有ると判断すると、受信したSFRREQパケットのデータ部にネクストホップノード１０Ｎ自身のMACアドレス及び位置情報を追加的に記述し、ヘッダ部に前記生存時間として記述された値をデクリメントしたSFRREQパケットを、ネクストホップノード１０Ｎ（リクエスト送信先ノード）に送信する。パケット制御部１０１Ｎは、リクエスト送信先ノードが無いと判断すると、ネクストホップノード１０Ｎ自身を終端ノードと判断する。終端ノードと判断すると、ネクストホップノード１０Ｎは、受信したSFRREQパケットのデータ部に記述された全てのMACアドレス及び全ての位置情報を記述したデータ部を含むSFRREPパケットを生成し、受信したSFRREQパケットの送信元であるリクエスト送信元ノードに、SFRREPパケットを送信する。終端ノードを除くネクストホップノード１０Ｎは、リクエスト送信先ノードから、SFRREPパケットを受信し、リクエスト送信元ノードに、受信したSFRREPパケットを送信する。

ネクストホップノード１０Ｎのパケット制御部１０１Ｎは、SFRREQパケットのヘッダ部に記述された生存時間の値が０であると判断すると、SFRREPパケットを生成し、リクエスト送信元ノードに、SFRREPパケットを送信する。さらに、パケット制御部１０１Ｎは、リクエスト送信先ノードが有ると判断すると、受信したSFRREQパケットのデータ部にネクストホップノード１０Ｎ自身のMACアドレス及び位置情報を追加的に記述し、ヘッダ部に前記生存時間として記述された値をリセットしたSFRREQパケットを、ネクストホップノード１０Ｎ（リクエスト送信先ノード）に送信する。

センターノード１０Ｃのパケット制御部１０１Ｃは、１以上のネクストホップノード１０Ｎから、SFRREPパケットを受信する。

センターノード１０Ｃの構築経路管理部１０２Ｃは、受信した１以上のSFRREPパケットのデータ部に記述された全てのMACアドレス及び全ての位置情報に基づき、定期的に、ルーティングテーブルを作成する。構築経路管理部１０２Ｃは、作成したルーティングテーブルを、定期的に、ネクストホップノード１０Ｎに供給する。

ネクストホップノード１０Ｎの構築経路管理部１０２Ｎは、センターノード１０Ｃが作成したルーティングテーブルを取得する。

４．センターノード及びネクストホップノードの動作フロー
図３は、センターノードの動作フローを示す。図４は、ネクストホップノードの動作フローを示す。図５は、センターノード及びネクストホップノード（終端ノードを含む）の動作シーケンスを示す。

センターノード１０Ｃの制御部１１Ｃは、ネットワークインターフェース１３Ｃを介して、通信可能な全てのネクストホップノード１０Ｎに、HELLOパケットを送信する（ステップＳ１０１）。以下便宜的に、センターノード１０ＣがHELLOパケットを送信した送信先のネクストホップノード１０Ｎを、「第１のネクストホップノード１０Ｎ１」と称する。

各第１のネクストホップノード１０Ｎ１の制御部１１Ｎは、ネットワークインターフェース１３Ｎを介して、センターノード１０ＣからHELLOパケットを受信する。HELLOパケットを受信した第１のネクストホップノード１０Ｎ１の制御部１１Ｎは、ネットワークインターフェース１３Ｎを介して、センターノード１０Ｃに、HELLOパケットを送信する。

センターノード１０Ｃの制御部１１Ｃは、ネットワークインターフェース１３Ｃを介して、複数の第１のネクストホップノード１０Ｎ１から、HELLOパケットを受信する（ステップＳ１０２、ＹＥＳ）。

HELLOパケットを受信すると、センターノード１０Ｃのパケット制御部１０１Ｃは、リクエストパケットとしてSFRREQパケットを生成する。センターノード１０Ｃのパケット制御部１０１Ｃは、生成したSFRREQパケットを、受信したHELLOパケットの送信元である複数の第１のネクストホップノード１０Ｎ１（リクエスト送信先ノード）全てに対し、ネットワークインターフェース１３Ｃを介してユニキャストで送信する（ステップＳ１０３）。SFRREQパケットの送信後、センターノード１０Ｃは、SFRREPパケット（後述）の受信待ち状態となる。

ここで「SFRREQパケット」について説明する。「SFRREQパケット」は、AODV（Ad hoc On-Demand Distance Vector）プロトコルで用いられる既存のRREQ（Route Request）パケットを改良した本実施形態特有のパケットであり、「Smart Flooding Route Requestパケット」の意味である。「SFRREQパケット」は、アドホックネットワークの経路を構築のために必要な情報を蓄積する。

図６は、SFRREQパケットを示す。図７は、既存のRREQパケットのヘッダを示す。
本実施形態のSFRREQパケットのヘッダ（SFRREQヘッダ）（図６）において、既存のRREQパケットのヘッダ（RREQヘッダ）（図７）からの変更点は、以下の通りである。即ち、本実施形態のSFRREQヘッダには、既存のRREQヘッダの「送信先IPアドレス」、「送信先シーケンス番号」、「送信元IPアドレス」及び「送信元シーケンス番号」の代わりに、「送信先MACアドレス」、「送信元MACアドレス」及び「生存時間２（TTL2）」が記述されている。「送信先MACアドレス」は、SFRREQパケットの送信先であるノードのMACアドレスである。「送信元MACアドレス」は、SFRREQパケットの送信元であるノードのMACアドレスである。ステップＳ１０３の場合、「送信元MACアドレス」として、センターノード１０ＣのMACアドレスが記述される。「生存時間２（TTL2）」は、正の整数値（例えば「３」）を記述する。「生存時間２（TTL2）」の値は、ホップ毎に変更される（後で説明する）。

SFRREQパケットのデータ部は、RREQ IDと、MACアドレスバッファと、位置情報バッファとを含む。「RREQ ID」は、SFRREQパケットを固有に識別するためのID（identifier）である。「MACアドレスバッファ」は、このSFRREQパケットの送信元のノードのMACアドレスが蓄積（ホップの度に追加的に記述）される。ステップＳ１０３の場合、センターノード１０ＣのMACアドレスが記述される。「位置情報バッファ」には、このSFRREQパケットの送信元のノードの位置情報（位置情報取得装置１４が取得した情報）が蓄積（ホップの度に追加的に記述）される。ステップＳ１０３の場合、位置情報取得装置１４Ｃが取得した、センターノード１０Ｃの位置情報が記述される。

動作フローの説明に戻る。センターノード１０ＣにHELLOパケットを送信した各第１のネクストホップノード１０Ｎ１（リクエスト送信先ノード）のパケット制御部１０１Nは、ネットワークインターフェース１３Ｎを介して、センターノード１０ＣからSFRREQパケットを受信する（ステップＳ２０１、ＹＥＳ）。SFRREQパケットを受信すると、第１のネクストホップノード１０Ｎ１のパケット制御部１０１Nは、今までにSFRREQパケットを送信したことが有るか否かを判断する（ステップＳ２０２）。第１のネクストホップノード１０Ｎ１のパケット制御部１０１Nは、今までにSFRREQパケットを送信したことが無いと判断する（ステップＳ２０２、ＮＯ）。この場合、第１のネクストホップノード１０Ｎ１の制御部１１Ｎは、ネットワークインターフェース１３Ｎを介して、通信可能な全てのネクストホップノード１０Ｎに、HELLOパケットを送信する。以下便宜的に、第１のネクストホップノード１０Ｎ１がHELLOパケットを送信した送信先のネクストホップノード１０Ｎを、「第２のネクストホップノード１０Ｎ２」と称する。このとき、第１のネクストホップノード１０Ｎ１の制御部１１Ｎは、HELLOパケットに対する応答HELLOパケットとして、応答元である第２のネクストホップノード１０Ｎ２の位置情報を追加的に記述した応答HELLOパケットを要求する（ステップＳ２０３）。以下「応答HELLOパケット」は、応答元であるノードの位置情報を追加的に記述したHELLOパケットを意味する。

なお、第１のネクストホップノード１０Ｎ１のパケット制御部１０１Ｎは、今までにSFRREQパケットを送信したことが有ると判断する（ステップＳ２０２、ＹＥＳ）。この場合、第１のネクストホップノード１０Ｎ１は、HELLOパケットを送信することなく、処理を終了する。言い換えれば、各ネクストホップノード１０Ｎは、SFRREQパケットを１回しか送信しない。これにより、各ネクストホップノード１０Ｎが多数のネクストホップノード１０ＮからSFRREQパケットを受信する可能性を減らすことができ、ネットワークに掛かる負荷を軽減することができる。

各第１のネクストホップノード１０Ｎ１のパケット制御部１０１Ｎは、HELLOパケットを送信してから応答HELLOパケットを受信するまでの待機時間を利用し、以下の処理を行う。即ち、第１のネクストホップノード１０Ｎ１のパケット制御部１０１Ｎは、センターノード１０Ｃから受信（ステップＳ２０１、ＹＥＳ）したSFRREQパケットのデータ部のMACアドレスバッファ内に、既に記述されているセンターノード１０ＣのMACアドレスに続いて、第１のネクストホップノード１０Ｎ１自身のMACアドレスを追加的に記述する。さらに、第１のネクストホップノード１０Ｎ１のパケット制御部１０１Ｎは、SFRREQパケットのデータ部の位置情報バッファ内に、既に記述されているセンターノード１０Ｃの位置情報に続いて、第１のネクストホップノード１０Ｎ１自身の位置情報を追加的に記述する。

第１のネクストホップノード１０Ｎ１のパケット制御部１０１Ｎは、SFRREQパケットのヘッダ部にTTL2として記述された値を読み出す。パケット制御部１０１Ｎは、TTL2が０であるか否かを判断する（ステップＳ２０６）。パケット制御部１０１Ｎは、TTL2が０でないと判断すると（ステップＳ２０６、ＮＯ）、SFRREQパケットのヘッダにTTL2として記述された値をデクリメントする（ステップＳ２０７）。一方、パケット制御部１０１Ｎは、TTL2が０であると判断すると（ステップＳ２０６、ＹＥＳ）、TTL2として正の整数値（例えば「３」）を新たに記述（TTL2をリセット）する（ステップＳ２０８）。TTL2として記述する値は、センターノード１０Ｃが生成するSFRREQパケット（ステップＳ１０３）のTTL2の値と同じでもよいし異なってもよい。

このように、第１のネクストホップノード１０Ｎ１のパケット制御部１０１Nは、HELLOパケットを送信してから応答HELLOパケットを受信するまでの待機時間を利用し、SFRREQパケットを更新する。

以下、（１）TTL2が０でない場合（ステップＳ２０６、ＮＯ）、（２）TTL2が０である場合（ステップＳ２０６、ＹＥＳ）に分けて説明する。

（１）TTL2が０でない場合（ステップＳ２０６、ＮＯ）
第１のネクストホップノード１０Ｎ１のパケット制御部１０１Ｎは、SFRREQパケットのデータ部の位置情報バッファ内に記述されているセンターノード１０Ｃの位置情報と、第１のネクストホップノード１０Ｎ１の位置情報とに基づき、第１のネクストホップノード１０Ｎ１のリクエスト送信エリア及びリクエスト送信不可エリアを算出する。単純に言えば、第１のネクストホップノード１０Ｎ１のパケット制御部１０１Ｎは、センターノード１０Ｃの位置情報と、第１のネクストホップノード１０Ｎ１の位置情報とに基づき、SFRREQパケットの送信元であるセンターノード１０Ｃの位置から離れた位置にあるノード１０を、リクエスト送信先ノードとする。リクエスト送信エリア及びリクエスト送信不可エリアの算出方法を以下に説明する。

図８は、リクエスト送信エリア及びリクエスト送信不可エリアを模式的に示す。
通信可能エリアＡ１は、第１のネクストホップノード１０Ｎ１の電波の届く距離範囲である（同図では、模式的に、単に円形で示す）。第１のネクストホップノード１０Ｎ１のパケット制御部１０１Ｎは、SFRREQパケットの送信元であるセンターノード１０Ｃの位置と第１のネクストホップノード１０Ｎ１の位置とを結んだ線分Ｌ１と直交し且つ第１のネクストホップノード１０Ｎ１自身の位置を通過する直線Ｌ２で、第１のネクストホップノード１０Ｎ１自身が通信可能なエリアＡ１を、２つのエリアＡ２、Ａ３に分断する。第１のネクストホップノード１０Ｎ１のパケット制御部１０１Ｎは、通信可能なエリアＡ１を分断した２つのエリアＡ２、Ａ３のうち、SFRREQパケットの送信元であるセンターノード１０Ｃの位置を含まないエリアをリクエスト送信エリアＡ２とし、センターノード１０Ｃの位置を含むエリアをリクエスト送信不可エリアＡ３とする。

動作フローの説明に戻る。各第２のネクストホップノード１０Ｎ２の制御部１１Ｎは、ネットワークインターフェース１３Ｎを介して、第１のネクストホップノード１０Ｎ１からHELLOパケットを受信する（ステップＳ２０１でＮＯ、ステップＳ２０４でＹＥＳ）。HELLOパケットを受信した第２のネクストホップノード１０Ｎ２の制御部１１Ｎは、HELLOパケットに第２のネクストホップノード１０Ｎ２自身の位置情報（位置情報取得装置１４Ｎが取得した情報）を追加的に記述した応答HELLOパケットを生成する。第２のネクストホップノード１０Ｎ２の制御部１１Ｎは、応答HELLOパケットを、ネットワークインターフェース１３Ｎを介して、第１のネクストホップノード１０Ｎ１に送信する（ステップＳ２０５）。

第１のネクストホップノード１０Ｎ１の制御部１１Ｎは、各第２のネクストホップノード１０Ｎ２から、ネットワークインターフェース１３Ｎを介して、応答HELLOパケットを受信する（又は、既に受信している）（ステップＳ２０９、ＹＥＳ）。

第１のネクストホップノード１０Ｎ１のパケット制御部１０１Ｎは、各応答HELLOパケットに記述された、第２のネクストホップノード１０Ｎ２自身の位置情報を読み出す。第１のネクストホップノード１０Ｎ１の制御部１１Ｎは、各第２のネクストホップノード１０Ｎ２が、上記算出したリクエスト送信エリアＡ２及びリクエスト送信不可エリアＡ３の何れに位置するかを判断する（ステップＳ２１０）。

第１のネクストホップノード１０Ｎ１の制御部１１Ｎは、リクエスト送信エリアＡ２に位置する全ての第２のネクストホップノード１０Ｎ２（リクエスト送信先ノード）に対し（ステップＳ２１０、ＹＥＳ）、ネットワークインターフェース１３Ｎを介してユニキャストで、上記更新後のSFRREQパケットを送信する（ステップＳ２１１）。なお「更新後のSFRREQパケット」は、第１のネクストホップノード１０Ｎ１自身のMACアドレス及び位置情報を追加的に記述し、TTL2の値をデクリメント（ステップＳ２０７）したSFRREQパケットである。

各第２のネクストホップノード１０Ｎ２（リクエスト送信先ノード）のパケット制御部１０１Ｎは、ネットワークインターフェース１３Ｎを介して、第１のネクストホップノード１０Ｎ１からSFRREQパケットを受信する（ステップＳ２０１、ＹＥＳ）。SFRREQパケットを受信すると、第２のネクストホップノード１０Ｎ２自身がリクエスト送信元ノードとなり、ステップＳ２０２以下の処理を繰り返す。

なお、第２のネクストホップノード１０Ｎ２は、以下の様に、SFRREQパケットを更新する。第２のネクストホップノード１０Ｎ２のパケット制御部１０１Ｎは、第１のネクストホップノード１０Ｎ１から受信（ステップＳ２０１、ＹＥＳ）したSFRREQパケットのデータ部のMACアドレスバッファ内に、既に記述されているセンターノード１０ＣのMACアドレス及びそれに続く第１のネクストホップノード１０Ｎ１のMACアドレスに続いて、第２のネクストホップノード１０Ｎ２自身のMACアドレスを追加的に記述する。さらに、第２のネクストホップノード１０Ｎ２のパケット制御部１０１Ｎは、SFRREQパケットのデータ部の位置情報バッファ内に、既に記述されているセンターノード１０Ｃの位置情報及びそれに続く第１のネクストホップノード１０Ｎ１の位置情報に続いて、第２のネクストホップノード１０Ｎ２自身の位置情報を追加的に記述する。第２のネクストホップノード１０Ｎ２のパケット制御部１０１Ｎは、SFRREQパケットのヘッダ部のTTL2の値をデクリメント（ステップＳ２０７）又はリセット（ステップＳ２０８）する。

なお、第２のネクストホップノード１０Ｎ２は、以下の様に、リクエスト送信エリア及びリクエスト送信不可エリアを算出する。第２のネクストホップノード１０Ｎ２のパケット制御部１０１Ｎは、SFRREQパケットの送信元である第１のネクストホップノード１０Ｎ１の位置と第２のネクストホップノード１０Ｎ２の位置とを結んだ線分Ｌ１と直交し且つ第２のネクストホップノード１０Ｎ２自身の位置を通過する直線Ｌ２で、第２のネクストホップノード１０Ｎ２自身が通信可能なエリアＡ１を、２つのエリアＡ２、Ａ３に分断する。第２のネクストホップノード１０Ｎ２のパケット制御部１０１Ｎは、通信可能なエリアＡ１を分断した２つのエリアＡ２、Ａ３のうち、SFRREQパケットの送信元である第１のネクストホップノード１０Ｎ１の位置を含まないエリアをリクエスト送信エリアＡ２とし、第１のネクストホップノード１０Ｎ１の位置を含むエリアをリクエスト送信不可エリアＡ３とする。

一方、ネクストホップノード１０Ｎの制御部１１Ｎは、HELLOパケットを送信したが（ステップＳ２０３）、別のネクストホップノード１０Ｎから応答HELLOパケットを何ら受信しないこともある（ステップＳ２０９、ＮＯ）。あるいは、ネクストホップノード１０Ｎの制御部１１Ｎは、リクエスト送信エリアＡ２に位置する別のネクストホップノード１０Ｎが無いと判断することもある（ステップＳ２１０、ＮＯ）。これらの場合、SFRREQパケットの送信先となるノードが無いことを意味する。従って、ネクストホップノード１０Ｎの制御部１１Ｎは、ネクストホップノード１０Ｎが終端ノードと判断する。以下便宜的に、終端ノードであるネクストホップノード１０Ｎを、「終端ノード１０Ｎ３」と称する。

終端ノード１０Ｎ３のパケット制御部１０１Ｎは、リプライパケットとしてSFRREPパケットを生成する（ステップＳ２１２）。

ここで「SFRREPパケット」について説明する。「SFRREPパケット」は、AODVプロトコルで用いられる既存のSFRREP（Route Reply）パケットを改良した本実施形態特有のパケットであり、「Smart Flooding Route Replyパケット」の意味である。「SFRREPパケット」は、アドホックネットワークの経路を構築のために必要な情報を蓄積する。

図９は、SFRREPパケットを示す。図１０は、既存のRREPパケットのヘッダを示す。
本実施形態のSFRREPパケットのヘッダ（SFRREPヘッダ）（図９）において、既存のRREPパケットのヘッダ（RREPヘッダ）（図１０）からの変更点は、以下の通りである。即ち、本実施形態のSFRREPヘッダには、既存のRREPヘッダの「送信先IPアドレス」、「送信先シーケンス番号」及び「送信元IPアドレス」の代わりに、「送信元MACアドレス」が記述されている。「送信元MACアドレス」は、SFRREPパケットの送信元である終端ノード１０Ｎ３のMACアドレスである。

SFRREPパケットのデータ部は、終端ノード１０Ｎ３が取得したSFRREQパケットのデータ部と完全に同一である。即ち、SFRREPパケットのデータ部は、RREQ IDと、MACアドレスバッファと、位置情報バッファとを含む。「RREQ ID」は、終端ノード１０Ｎ３が取得したSFRREQパケットを固有に識別するためのIDある。「MACアドレスバッファ」には、センターノード１０Ｃから終端ノード１０Ｎ３までの各ノードのMACアドレスが、ホップ順に蓄積される。「位置情報バッファ」には、センターノード１０Ｃから終端ノード１０Ｎ３までの各ノードの位置情報が、ホップ順に蓄積される。

動作フローの説明に戻る。終端ノード１０Ｎ３のパケット制御部１０１Ｎは、生成したSFRREPパケットを、MACアドレスバッファにホップ順に蓄積されたMACアドレスを参照し、MACアドレスバッファに蓄積された順が新しい順（ホップ順）に、複数のネクストホップノード１０Ｎを遡ることで、センターノード１０Ｃまで送信する（ステップＳ２１３）。

具体的には、終端ノード１０Ｎ３のパケット制御部１０１Ｎは、生成したSFRREPパケットを、受信したSFRREQの送信元であるネクストホップノード１０Ｎ（例えば、第２のネクストホップノード１０Ｎ２）（リクエスト送信元ノード）に、SFRREPパケットを送信する。第２のネクストホップノード１０Ｎ２のパケット制御部１０１Ｎは、SFRREPパケットを、終端ノード１０Ｎ３（リクエスト送信先ノード）から受信し、第１のネクストホップノード１０Ｎ１（リクエスト送信元ノード）に送信する。第１のネクストホップノード１０Ｎ１のパケット制御部１０１Ｎは、SFRREPパケットを、第２のネクストホップノード１０Ｎ２（リクエスト送信先ノード）から受信し、センターノード１０Ｃ（リクエスト送信元ノード）に送信する。

（２）TTL2が０である場合（ステップＳ２０６、ＹＥＳ）
TTL2が０である場合とは、SFRREQパケットが何回かホップされたことを意味する。TTL2が０であるSFRREQパケットを受信したネクストホップノードを、便宜的に、「生存時間ゼロノード１０Ｎ４」と称する。生存時間ゼロノード１０Ｎ４のパケット制御部１０１Ｎは、リプライパケットとしてSFRREPパケット（図９）を生成する（ステップＳ２１２Ａ）。SFRREPパケットのヘッダ（SFRREPヘッダ）に記述されている「送信元MACアドレス」は、SFRREPパケットの送信元である生存時間ゼロノード１０Ｎ４のMACアドレスである。SFRREPパケットのデータ部は、生存時間ゼロノード１０Ｎ４が取得したSFRREQパケットのデータ部と完全に同一である。「RREQ ID」は、生存時間ゼロノード１０Ｎ４が取得したSFRREQパケットを固有に識別するためのIDある。「MACアドレスバッファ」には、センターノード１０Ｃから生存時間ゼロノード１０Ｎ４までの各ノードのMACアドレスが、ホップ順に蓄積される。「位置情報バッファ」には、センターノード１０Ｃから生存時間ゼロノード１０Ｎ４までの各ノードの位置情報が、ホップ順に蓄積される。

図１１は、センターノード及びネクストホップノード（生存時間ゼロノードを含む）の動作シーケンスを示す。
図１１のステップＳ１０１乃至Ｓ１０３と、ステップＳ２０１及びＳ２０２とは、図５の各ステップと同様なので図示を省略する。

生存時間ゼロノード１０Ｎ４のパケット制御部１０１Ｎは、生成したSFRREPパケットを、MACアドレスバッファにホップ順に蓄積されたMACアドレスを参照し、MACアドレスバッファに蓄積された順が新しい順（ホップ順）に、複数のネクストホップノード１０Ｎを遡ることで、センターノード１０Ｃまで送信する（ステップＳ２１３Ａ）。その方法はステップＳ２１３で説明した方法と同様である。

ところで、生存時間ゼロノード１０Ｎ４の制御部１１Ｎは、各第２のネクストホップノード１０Ｎ２から、ネットワークインターフェース１３Ｎを介して、応答HELLOパケットを受信する（又は、既に受信している）（ステップＳ２０９Ａ、ＹＥＳ）。

生存時間ゼロノード１０Ｎ４のパケット制御部１０１Ｎは、各応答HELLOパケットに記述された、第２のネクストホップノード１０Ｎ２自身の位置情報を読み出す。生存時間ゼロノード１０Ｎ４の制御部１１Ｎは、各第２のネクストホップノード１０Ｎ２が、上記算出したリクエスト送信エリアＡ２及びリクエスト送信不可エリアＡ３の何れに位置するかを判断する（ステップＳ２１０Ａ）。その方法はステップＳ２１０で説明した方法と同様である。

生存時間ゼロノード１０Ｎ４の制御部１１Ｎは、リクエスト送信エリアＡ２に位置する全ての第２のネクストホップノード１０Ｎ２（リクエスト送信先ノード）に対し（ステップＳ２１０Ａ、ＹＥＳ）、ネットワークインターフェース１３Ｎを介してユニキャストで、上記更新後のSFRREQパケットを送信する（ステップＳ２１１Ａ）。なお「更新後のSFRREQパケット」は、生存時間ゼロノード１０Ｎ４自身のMACアドレス及び位置情報を追加的に記述し、TTL2の値をリセット（ステップＳ２０８）したSFRREQパケットである。

各第２のネクストホップノード１０Ｎ２（リクエスト送信先ノード）のパケット制御部１０１Ｎは、ネットワークインターフェース１３Ｎを介して、第１のネクストホップノード１０Ｎ１からSFRREQパケットを受信する（ステップＳ２０１、ＹＥＳ）。SFRREQパケットを受信すると、第２のネクストホップノード１０Ｎ２自身がリクエスト送信元ノードとなり、ステップＳ２０２以下の処理を繰り返す。

図３を再び参照し、センターノード１０Ｃのパケット制御部１０１ＣがSFRREPパケットを受信するときの動作を説明する。

センターノード１０Ｃのパケット制御部１０１Ｃは、ネットワークインターフェース１３Ｃを介して、SFRREQパケットの送信先である複数の第１のネクストホップノード１０Ｎ１（リクエスト送信先ノード）全てから、SFRREPパケットを受信する（ステップＳ１０４、ステップＳ１０５）。具体的には、センターノード１０Ｃのパケット制御部１０１Ｃは、最初にSFRREPパケットを受信してから特定時間（任意の時間長）以内に、複数の第１のネクストホップノード１０Ｎ１から、SFRREPパケットを受信する。センターノード１０Ｃのパケット制御部１０１Ｃは、受信したSFRREPパケットを、構築経路管理部１０２Ｃに供給する。

センターノード１０Ｃの構築経路管理部１０２Ｃは、受信した複数のSFRREPパケットを、到着した順にキューに入れ、各SFRREPパケットに記述された情報を、SFRREPパケット毎に、順に記憶部１６Ｃに蓄積する。具体的には、構築経路管理部１０２Ｃは、各SFRREPパケットのデータ部に含まれる、MACアドレスバッファに記述された全てのMACアドレスと、位置情報バッファに記述された全ての位置情報とを、記憶部１６Ｃの受信データ格納部１０４Ｃに蓄積する（ステップＳ１０６）。

続いて、センターノード１０Ｃの構築経路管理部１０２Ｃは、受信データ格納部１０４Ｃに蓄積したMACアドレス及び位置情報に基づき、ルーティングテーブルを作成する。具体的には、構築経路管理部１０２Ｃは、各ネクストホップノード１０ＮのMACアドレス毎に、各ネクストホップノード１０ＮにIPアドレスを割り振り、ルーティングテーブルを作成する（ステップＳ１０７）。ルーティングテーブルは、各ノード１０同士の繋がりを示す。構築経路管理部１０２Ｃは、作成したルーティングテーブルを、記憶部１６Ｃの構築経路格納部１０３Ｃに蓄積する。

センターノード１０Ｃの構築経路管理部１０２Ｃは、作成したルーティングテーブルの経路情報に基づき、各ネクストホップノード１０Ｎに向けて、IPアドレスとルーティングテーブルとを含んだパケットを送信する（ステップＳ１０８）。

各ネクストホップノード１０Ｎの構築経路管理部１０２Ｎは、ネットワークインターフェース１３Ｎを介して、IPアドレスとルーティングテーブルとを含んだパケットを受信する。構築経路管理部１０２Ｎは、受信したパケットに含まれる、IPアドレスとルーティングテーブルとを、記憶部１６Ｎの受信データ格納部１０５Ｎに蓄積する。各ネクストホップノード１０Ｎは、IPアドレスとルーティングテーブルとに基づき、データリンクを確立し、アドホックネットワークを構築する。

センターノード１０Ｃのパケット制御部１０１Ｃは、定期的に（ステップＳ１０９のLOOP）、新たに受信したSFRREPパケット（ステップＳ１０４、ステップＳ１０５）に基づき、ルーティングテーブルを作成する（ステップＳ１０７）。センターノード１０Ｃのパケット制御部１０１Ｃは、定期的に（ステップＳ１０９のLOOP）、各ネクストホップノード１０Ｎに向けて、IPアドレスとルーティングテーブルとを含んだパケットを送信する（ステップＳ１０８）。

５．まとめ
典型的に、アドホックネットワークの経路を新規に構築するため、各ノードが、周囲のネクストホップノードに向けて、無差別にブロードキャストしてパケットを送信する技術が知られている。この技術によれば、ノードの数が増加するに従って、ネットワークに掛かる負荷やメモリリソースの消費が増大する。また、通信経路を探索するために、人間による手入力が必要であるとすれば、ノードのが増加するに従って、人的な手間も掛かる。

これに対して、本実施形態によれば、センターノード１０Ｃを除き、全てのネクストホップノード１０Ｎは、SFRREQパケットを１回しか送信しない（ステップＳ２０２、Ｓ２０３）。これにより、各ネクストホップノード１０Ｎが多数のネクストホップノード１０ＮからSFRREQパケットを受信する可能性を減らすことができる。

また、本実施形態によれば、センターノード１０Ｃを除き、全てのネクストホップノード１０Ｎは、通信可能エリアＡ１のうちの一部（リクエスト送信エリアＡ２）に位置するネクストホップノード１０Ｎにのみ、SFRREQパケットを送信する（ステップＳ２１０、Ｓ２１１）。これにより、各ネクストホップノード１０Ｎが多数のネクストホップノード１０ＮからSFRREQパケットを受信する可能性をさらに減らすことができる。

具体的には、本実施形態によれば、ネクストホップノード１０Ｎは、１以上の別のネクストホップノード１０Ｎに、HELLOパケットに対する応答パケットとして、応答元である別のネクストホップノード１０Ｎの位置情報を追加的に記述した応答HELLOパケットを要求する（ステップＳ２０３）。これにより、ネクストホップノード１０Ｎは、SFRREQパケットを送信する前に、別のネクストホップノード１０Ｎの位置情報を取得することができるので、SFRREQパケットを送信する対象を確実に絞り込むことができる。

また、本実施形態によれば、センターノード１０Ｃが、各ネクストホップノード１０ＮにIPアドレスを割り振り、ルーティングテーブルを作成する（ステップＳ１０７）。これにより、センターノード１０Ｃだけが、経路を構築する際に必要な情報を格納する構築経路格納部１０３Ｃを有し、各ネクストホップノード１０Ｎは有しない。そのため、各ネクストホップノード１０Ｎが消費するリソースを軽減することができる。また、ネットワーク内で送受信されるパケット量が抑えられ、ネットワークに掛かる負荷が軽減される。

以上のように、本実施形態によれば、ネットワークに掛かる負荷を軽減し、各ノードのメモリリソースの消費を抑え、人的な作業をなくすことができる。

さらに、本実施形態によれば、ネクストホップノードは、受信したリクエストパケットの生存時間の値が０のとき、センターノードに向けてリプライパケットを送信し、且つ、リクエストパケットの生存時間をリセットして終端ノードに向けてリクエストパケットを送信する。また、センターノードは、リプライパケットを最初に受信すると、ルーティングテーブルを定期的に作成する。これにより、リクエストパケットが生存時間を持たない（即ち、終端ノードだけがリプライパケットを生成する）と仮定した場合に比べて、センターノードがHELLOパケットを送信してからリプライパケットを最初に受信するまでの時間が短くなり、センターノードがリプライパケットを受信する頻度が高くなる。従って、センターノードがHELLOパケットを送信してからルーティングテーブルを最初に作成するまでの時間が短くなる。これにより、センターノードは、リアルタイムに、短時間に、アドホックネットワークの経路を新規に構築することができる。専用の基地局を含むインフラに依存しないアドホックネットワークは、例えば災害時などに用いられ得るが、災害時などに、リアルタイムに、短時間に、アドホックネットワークの経路を新規に構築することは有益である。

さらに、本実施形態によれば、ネクストホップノードは、受信したリクエストパケットの生存時間の値が０でないとき、リクエストパケットの生存時間をデクリメントして、ネクストホップノードにリクエストパケットを送信する。リクエストパケットの生存時間をデクリメントすることで、リクエストパケットが生存時間を持たない（即ち、終端ノードだけがリプライパケットを生成する）と仮定した場合に比べて、センターノードがHELLOパケットを送信してからリプライパケットを最初に受信するまでの時間が短くなり、センターノードがリプライパケットを受信する頻度が高くなる。従って、センターノードがHELLOパケットを送信してからルーティングテーブルを最初に作成するまでの時間が短くなる。

本技術の各実施形態及び各変形例について上に説明したが、本技術は上述の実施形態にのみ限定されるものではなく、本技術の要旨を逸脱しない範囲内において種々変更を加え得ることは勿論である。

１…アドホックネットワーク経路構築システム
１０…情報処理装置（ノード）
１０Ｃ…センターノード
１０Ｎ…ネクストホップノード
１０Ｎ１…第１のネクストホップノード
１０Ｎ２…第２のネクストホップノード
１０Ｎ３…終端ノード
１０Ｎ４…生存時間ゼロノード
１０１Ｃ、１０１Ｎ…パケット制御部
１０２Ｃ、１０２Ｎ…構築経路管理部
１０３Ｃ…構築経路格納部
１０４Ｃ、１０５Ｎ…受信データ格納部

Claims (13)

1. １個のセンターノードと、
   複数のネクストホップノードと
   を具備するアドホックネットワーク経路構築システムであって、
   前記センターノードは、
   前記センターノードのMAC（Media Access Control）アドレス及び位置情報を記述したデータ部と、生存時間として正の整数値を記述したヘッダ部とを含むリクエストパケットを生成し、
   前記センターノードを起点とする往路ルートで、前記センターノードと通信可能なエリアに位置する１以上のネクストホップノードに、前記リクエストパケットを送信し、
   各前記ネクストホップノードは、
   前記センターノード又は自身以外のネクストホップノードである別のネクストホップノードが送信した、リクエストパケットを、前記往路ルートで受信し、
   前記往路ルートで受信したリクエストパケットの前記ヘッダ部に記述された前記生存時間の値が０であると判断すると、
   前記往路ルートで受信したリクエストパケットの前記データ部に記述された全ての前記MACアドレス及び全ての前記位置情報を記述したデータ部を含むリプライパケットを生成し、
   前記往路ルートで受信したリクエストパケットの送信元である前記センターノード又は前記別のネクストホップノードに、前記センターノードへ遡る逆のルートである復路ルートで、前記リプライパケットを送信し、
   前記往路ルートで前記リクエストパケットの送信先となるさらに別のネクストホップノードの有無を判断し、
   前記リクエストパケットの送信先となるさらに別のネクストホップノードが有ると判断すると、前記受信したリクエストパケットの前記データ部に前記ネクストホップノード自身のMACアドレス及び位置情報を追加的に記述し、前記受信したリクエストパケットの前記ヘッダ部の前記生存時間をリセットしたリクエストパケットを、判断した前記さらに別のネクストホップノードに、前記往路ルートで送信し、
   自身がリクエストパケットを前記往路ルートで送信した先である前記さらに別のネクストホップノードが、当該リクエストパケットを受信したときに生成及び前記復路ルートで送信した、当該リクエストパケットの前記データ部に記述された全ての前記MACアドレス及び全ての前記位置情報を記述したデータ部を含む、リプライパケットを、前記復路ルートで受信し、
   自身が前記往路ルートで受信したリクエストパケットの送信元である前記センターノード又は前記別のネクストホップノードに、前記復路ルートで受信したリプライパケットを、前記復路ルートで送信し、
   前記センターノードは、さらに、
   前記センターノードが前記リクエストパケットを前記往路ルートで送信した先である１以上の前記ネクストホップノードが前記復路ルートで送信した、前記リプライパケットを前記復路ルートで受信すると、
   前記復路ルートで受信した１以上のリプライパケットの前記データ部に記述された前記全てのMACアドレス及び前記全ての位置情報に基づき、定期的に、ルーティングテーブルを作成する
   アドホックネットワーク経路構築システム。
2. 請求項１に記載のアドホックネットワーク経路構築システムであって、
   各前記ネクストホップノードは、
   前記リクエストパケットの前記ヘッダ部に記述された前記生存時間の値が０でないと判断すると、
   前記リクエストパケットの送信先となるさらに別のネクストホップノードの有無を判断し、
   前記リクエストパケットの送信先となる別のネクストホップノードが有ると判断すると、前記受信したリクエストパケットの前記データ部に前記ネクストホップノード自身のMACアドレス及び位置情報を追加的に記述し、前記受信したリクエストパケットの前記ヘッダ部に前記生存時間として記述された値をデクリメントしたリクエストパケットを、前記さらに別のネクストホップノードに送信する
   アドホックネットワーク経路構築システム。
3. 請求項１に記載のアドホックネットワーク経路構築システムであって、
   各前記ネクストホップノードは、
   前記リクエストパケットの送信先となるさらに別のネクストホップノードが無いと判断すると、前記ネクストホップノード自身を終端ノードと判断し、
   前記終端ノードは、
   前記受信したリクエストパケットの前記データ部に記述された全ての前記MACアドレス及び全ての前記位置情報を記述したデータ部を含むリプライパケットを生成し、
   前記受信したリクエストパケットの送信元である前記センターノード又は前記別のネクストホップノードに、前記リプライパケットを送信する
   アドホックネットワーク経路構築システム。
4. 請求項１乃至３の何れか一項に記載のアドホックネットワーク経路構築システムであって、
   各前記ネクストホップノードは、
   前記リクエストパケットの送信先となるさらに別のネクストホップノードの有無を判断する際、
   前記受信したリクエストパケットの送信元である前記センターノード又は前記別のネクストホップノードの位置情報を、前記受信したリクエストパケットの前記データ部から読み出し、
   前記受信したリクエストパケットの送信元である前記センターノード又は前記別のネクストホップノードの位置情報及び前記ネクストホップノード自身の位置情報に基づき、前記受信したリクエストパケットの送信元である前記センターノード又は前記別のネクストホップノードの位置から離れた位置にあるさらに別のネクストホップノードの有無を判断する
   アドホックネットワーク経路構築システム。
5. 請求項４に記載のアドホックネットワーク経路構築システムであって、
   各前記ネクストホップノードは、
   前記リクエストパケットの送信先となるさらに別のネクストホップノードの有無を判断する際、
   前記受信したリクエストパケットの送信元である前記センターノード又は前記別のネクストホップノードの位置と前記ネクストホップノード自身の位置とを結んだ線分と直交し且つ前記ネクストホップノード自身の前記位置を通過する直線で、前記ネクストホップノード自身が通信可能なエリアを分断し、前記分断した通信可能なエリアのうち前記受信したリクエストパケットの送信元である前記センターノード又は前記別のネクストホップノードの位置を含まないエリアに位置するさらに別のネクストホップノードの有無を判断する
   アドホックネットワーク経路構築システム。
6. 請求項５に記載のアドホックネットワーク経路構築システムであって、
   各前記ネクストホップノードは、
   複数の別のネクストホップノードから又は前記センターノード及び１以上の別のネクストホップノードから前記リクエストパケットを受信した場合、
   何れか１つの前記受信したリクエストパケットの前記データ部に前記ネクストホップノード自身のMACアドレス及び位置情報を追加的に記述し、前記記述したリクエストパケットを、前記ノードの位置を含まないエリアに位置するさらに別のネクストホップノードに送信する
   アドホックネットワーク経路構築システム。
7. 請求項６に記載のアドホックネットワーク経路構築システムであって、
   各前記ネクストホップノードは、
   前記リクエストパケットの送信先となるさらに別のネクストホップノードの有無を判断する際、
   前記ネクストホップノード自身と通信可能なエリアに位置する１以上の別のネクストホップノードに、HELLOパケットを送信し、
   前記HELLOパケットに対する応答パケットとして、応答元である別のネクストホップノードの位置情報を追加的に記述した応答パケットを要求し、
   前記１以上の別のネクストホップノードから、前記別のネクストホップノードの位置情報を追加的に記述した応答パケットを受信し、
   前記受信した応答パケットに追加的に記述された前記別のネクストホップノードの位置情報に基づき、前記さらに別のネクストホップノードの有無を判断する
   アドホックネットワーク経路構築システム。
8. １個のセンターノードと、複数のノードとを有するアドホックネットワーク経路構築システムに含まれる各ノードであって、
   前記センターノードから、前記センターノードのMAC（Media Access Control）アドレス及び位置情報を記述したデータ部と、生存時間として正の整数値を記述したヘッダ部とを含むリクエストパケットを受信し、
   前記リクエストパケットの前記ヘッダ部に記述された前記生存時間の値が０であると判断すると、
   前記受信したリクエストパケットの前記データ部に記述された全ての前記MACアドレス及び全ての前記位置情報を記述したデータ部を含むリプライパケットを生成し、
   前記受信したリクエストパケットの送信元であるリクエスト送信元ノードに、前記リプライパケットを送信する
   パケット制御部を具備する
   ノード。
9. 請求項８に記載のノードであって、
   前記パケット制御部は、
   前記リクエストパケットの前記ヘッダ部に記述された前記生存時間の値が０であると判断すると、さらに、
   前記リクエストパケットの送信先となるリクエスト送信先ノードの有無を判断し、
   前記リクエスト送信先ノードが有ると判断すると、前記受信したリクエストパケットの前記データ部に前記ノード自身のMACアドレス及び位置情報を追加的に記述し、前記受信したリクエストパケットの前記ヘッダ部の前記生存時間をリセットしたリクエストパケットを、前記リクエスト送信先ノードに送信する
   ノード。
10. 請求項８又は９に記載のノードであって、
    前記パケット制御部は、
    前記リクエストパケットの前記ヘッダ部に記述された前記生存時間の値が０でないと判断すると、
    前記リクエストパケットの送信先となるリクエスト送信先ノードの有無を判断し、
    前記リクエスト送信先ノードが有ると判断すると、前記受信したリクエストパケットの前記データ部に前記ネクストホップノード自身のMACアドレス及び位置情報を追加的に記述し、前記受信したリクエストパケットの前記ヘッダ部に前記生存時間として記述された値をデクリメントしたリクエストパケットを、前記リクエスト送信先ノードに送信する
    ノード。
11. 請求項９に記載のノードであって、
    前記パケット制御部は、
    前記リクエスト送信先ノードが無いと判断すると、前記ノード自身を終端ノードと判断し、
    前記終端ノードと判断すると、
    前記受信したリクエストパケットの前記データ部に記述された全ての前記MACアドレス及び全ての前記位置情報を記述したデータ部を含むリプライパケットを生成し、
    前記受信したリクエストパケットの送信元であるリクエスト送信元ノードに、前記リプライパケットを送信する
    ノード。
12. １個のセンターノードと、
    複数のネクストホップノードと
    を具備するアドホックネットワーク経路構築システムであって、
    前記センターノードは、
    前記センターノードのMAC（Media Access Control）アドレス及び位置情報を記述したデータ部と、生存時間として正の整数値を記述したヘッダ部とを含むリクエストパケットを生成し、
    前記センターノードを起点とする往路ルートで、前記センターノードと通信可能なエリアに位置する１以上のネクストホップノードに、前記リクエストパケットを送信し、
    各前記ネクストホップノードは、
    前記センターノード又は自身以外のネクストホップノードである別のネクストホップノードが送信した、リクエストパケットを、前記往路ルートで受信し、
    前記往路ルートで受信したリクエストパケットの前記ヘッダ部に記述された前記生存時間の値が０であると判断すると、
    前記往路ルートで受信したリクエストパケットの前記データ部に記述された全ての前記MACアドレス及び全ての前記位置情報を記述したデータ部を含むリプライパケットを生成し、
    前記往路ルートで受信したリクエストパケットの送信元である前記センターノード又は前記別のネクストホップノードに、前記センターノードへ遡る逆のルートである復路ルートで、前記リプライパケットを送信し、
    前記往路ルートで前記リクエストパケットの送信先となるさらに別のネクストホップノードの有無を判断し、
    前記リクエストパケットの送信先となるさらに別のネクストホップノードが有ると判断すると、前記受信したリクエストパケットの前記データ部に前記ネクストホップノード自身のMACアドレス及び位置情報を追加的に記述し、前記受信したリクエストパケットの前記ヘッダ部の前記生存時間をリセットしたリクエストパケットを、判断した前記さらに別のネクストホップノードに、前記往路ルートで送信し、
    自身がリクエストパケットを前記往路ルートで送信した先である前記さらに別のネクストホップノードが、当該リクエストパケットを受信したときに生成及び前記復路ルートで送信した、当該リクエストパケットの前記データ部に記述された全ての前記MACアドレス及び全ての前記位置情報を記述したデータ部を含む、リプライパケットを、前記復路ルートで受信し、
    自身が前記往路ルートで受信したリクエストパケットの送信元である前記センターノード又は前記別のネクストホップノードに、前記復路ルートで受信したリプライパケットを、前記復路ルートで送信し、
    前記センターノードは、さらに、
    前記センターノードが前記リクエストパケットを前記往路ルートで送信した先である１以上の前記ネクストホップノードが前記復路ルートで送信した、前記リプライパケットを前記復路ルートで受信すると、
    前記復路ルートで受信した１以上のリプライパケットの前記データ部に記述された前記全てのMACアドレス及び前記全ての位置情報に基づき、定期的に、ルーティングテーブルを作成する
    アドホックネットワーク経路構築システム
    に含まれる
    センターノード。
13. １個のセンターノードと、
    複数のネクストホップノードと
    を具備するアドホックネットワーク経路構築方法であって、
    前記センターノードは、
    前記センターノードのMAC（Media Access Control）アドレス及び位置情報を記述したデータ部と、生存時間として正の整数値を記述したヘッダ部とを含むリクエストパケットを生成し、
    前記センターノードを起点とする往路ルートで、前記センターノードと通信可能なエリアに位置する１以上のネクストホップノードに、前記リクエストパケットを送信し、
    各前記ネクストホップノードは、
    前記センターノード又は自身以外のネクストホップノードである別のネクストホップノードが送信した、リクエストパケットを、前記往路ルートで受信し、
    前記往路ルートで受信したリクエストパケットの前記ヘッダ部に記述された前記生存時間の値が０であると判断すると、
    前記往路ルートで受信したリクエストパケットの前記データ部に記述された全ての前記MACアドレス及び全ての前記位置情報を記述したデータ部を含むリプライパケットを生成し、
    前記往路ルートで受信したリクエストパケットの送信元である前記センターノード又は前記別のネクストホップノードに、前記センターノードへ遡る逆のルートである復路ルートで、前記リプライパケットを送信し、
    前記往路ルートで前記リクエストパケットの送信先となるさらに別のネクストホップノードの有無を判断し、
    前記リクエストパケットの送信先となるさらに別のネクストホップノードが有ると判断すると、前記受信したリクエストパケットの前記データ部に前記ネクストホップノード自身のMACアドレス及び位置情報を追加的に記述し、前記受信したリクエストパケットの前記ヘッダ部の前記生存時間をリセットしたリクエストパケットを、判断した前記さらに別のネクストホップノードに、前記往路ルートで送信し、
    自身がリクエストパケットを前記往路ルートで送信した先である前記さらに別のネクストホップノードが、当該リクエストパケットを受信したときに生成及び前記復路ルートで送信した、当該リクエストパケットの前記データ部に記述された全ての前記MACアドレス及び全ての前記位置情報を記述したデータ部を含む、リプライパケットを、前記復路ルートで受信し、
    自身が前記往路ルートで受信したリクエストパケットの送信元である前記センターノード又は前記別のネクストホップノードに、前記復路ルートで受信したリプライパケットを、前記復路ルートで送信し、
    前記センターノードは、さらに、
    前記センターノードが前記リクエストパケットを前記往路ルートで送信した先である１以上の前記ネクストホップノードが前記復路ルートで送信した、前記リプライパケットを前記復路ルートで受信すると、
    前記復路ルートで受信した１以上のリプライパケットの前記データ部に記述された前記全てのMACアドレス及び前記全ての位置情報に基づき、定期的に、ルーティングテーブルを作成する
    アドホックネットワーク経路構築方法。

Images