JP4732972B2

JP4732972B2 - アドホックネットワーク、ノード、経路制御方法、及び経路制御プログラム

Info

Publication number: JP4732972B2
Application number: JP2006182457A
Authority: JP
Inventors: 智之小佐野; 良隆内田; 憲洋石川
Original assignee: NTT Docomo Inc
Current assignee: NTT Docomo Inc
Priority date: 2006-06-30
Filing date: 2006-06-30
Publication date: 2011-07-27
Anticipated expiration: 2026-06-30
Also published as: JP2008011448A; US7970933B2; US20080126565A1

Description

本発明は、複数のノードによってアドホックネットワークを構成するアドホックネットワーク、ノード、経路制御方法、及び経路制御プログラムに関する。

近年、移動通信端末の発達と普及が進み、移動通信端末同士で動的にネットワークを構築するモバイルアドホックネットワークへの関心が高まっている。モバイルアドホックネットワークは、従来での移動無線通信ネットワークで不可欠な基地局やコアネットワークといったインフラストラクチャに依存せず、移動通信端末同士が自律的に構成するネットワークである。

期待される適用例としては、センサネットワーク、災害時通信、車車間通信、パーソナルエリアネットワーク、家庭内ネットワーク、イベントにおける一時的なネットワーク、情報交換のためのネットワークがある。このような通信環境においては、携帯電話等の移動端末から、周囲に点在するデバイスを利用することや、異なるネットワークに存在する複数のデバイス同士が連携、協調して動作するサービスなど、新しい形のアプリケーションの実現が求められるようになると考えられる。

モバイルアドホックネットワークのルーティングプロトコルとして、リアクティブ型のＤＳＲ（Dynamic Source Routing）やプロアクティブ型のＯＬＳＲ（Optimized Link State Routing）などが提案されている。

リアクティブ型のＤＳＲはオンデマンド型とも呼ばれ、データ送信開始時に送信相手への経路発見プロセスを起動する。このプロセスは経路が見つかるか、利用可能なすべての経路パターンを試し終えると終了する。一度、経路が発見、確立されると、宛先への通信が不可能になるか経路自体が不必要になるまで、その経路は保持される。データ送信開始の要求後に経路発見を行うため、データ送信を行わない期間においては通信パケットによるネットワークへの負荷は発生しない。一方、データ送信開始要求から実際に通信相手へデータ送信を行うまでに多少の遅延が発生し、さらに、経路が見つかるか、利用可能なすべての経路パターンを試し終えるまで、経路発見プロセスを実行するため、送信相手が発見できない場合にはオーバーヘッドが生じるといった欠点がある。

プロアクティブ型のＯＬＳＲはテーブル駆動型とも呼ばれ、ＩＥＴＦ(Internet Engineering Task Force)によって標準化されたその他のプロアクティブ型ルーティングプロトコルとしてはＴＢＲＰＦ（Topology Broadcast Based on Reverse-Path Forwarding）がある。各ノードは各ノードからネットワーク上のノードへのルーティング情報を格納するテーブルを持つ。各ノードはネットワークトポロジの変化に応じて各ノードのテーブルにある経路情報を更新し、ネットワークトポロジと経路情報の整合性を確保する。定期的にノード間で経路情報の交換を行うため、データ送信開始要求から実際に送信相手へデータ送信を行うまでの遅延は発生しないが、データ送信を行わない間もノード間で通信を行うため、ネットワークの通信負荷が発生する。どの程度の頻度で経路情報の更新を行うのか、どの範囲のノードで経路情報の更新を行うのかを検討することで、通信負荷を軽減することが研究されているが、効率性や利便性とのトレードオフとなっている。
特開２００３−５１６０３５号公報

モバイルアドホックネットワークでは、電源非供給型のセンサを含むことも考えられ、センサ、携帯端末ともにメモリや処理能力は限られている。そのため、データ送信時と非送信時のオーバーヘッドを抑制し、さらにセンサや携帯端末のＣＰＵリソースなどの消費を低減するプロトコルが必要となる。

具体的にはリアクティブ型のルーティングプロトコルにおいてはデータ送信時のオーバーヘッドと遅延を低減することが課題であり、プロアクティブ型のルーティングプロトコルにおいては、データ非送信時におけるノード間の通信量及び、各ノードの持つ情報量（経路情報など）を低減することが課題となる。

上記問題点を鑑み、本発明は、アドホックネットワークにおいて、データ送信時と非送信時のオーバーヘッドを抑制し、さらに各ノードのＣＰＵリソースなどの消費を低減可能とするアドホックネットワーク、ノード、経路制御方法、及び経路制御プログラムを提供することを目的とする。

上記目的を達成するために、本発明の第１の特徴は、複数のノードによって構成されるアドホックネットワークであって、各ノードは、複数の隣接ノードとの間に複数のリンクをそれぞれ設定するリンク設定部と、リンク先に存在する各ノードを一意に識別するノード識別子をキーとしたブルームフィルターを各リンクと対応づけて記憶するブルームフィルター記憶部と、データ送信時において、記憶されたブルームフィルターを経路情報として使用するデータ送信部とを備えることを要旨とする。

本発明の第２の特徴は、複数のノードによって構成されるアドホックネットワークにおけるノードであって、複数の隣接ノードとの間に複数のリンクをそれぞれ設定するリンク設定部と、リンク先に存在する各ノードを一意に識別するノード識別子をキーとしたブルームフィルターを各リンクと対応づけて記憶するブルームフィルター記憶部と、データ送信時において、記憶されたブルームフィルターを経路情報として使用するデータ送信部とを備えることを要旨とする。

第３の特徴は、第２の特徴に係るノードにおいて、アドホックネットワークに新たに参加する参加ノードから、参加ノードのノード識別子を変換して得られたビット列を受信した場合、受信したビット列を参加ノードとのリンクに対応するブルームフィルターとしてブルームフィルター記憶部に追加する追加処理部をさらに備えることを要旨とする。

第４の特徴は、第３の特徴に係るノードにおいて、追加処理部は、参加ノードとのリンク以外の各リンクに対応するブルームフィルターと、自ノードのノード識別子を変換して得られたビット列との演算結果を参加ノードへ送信することを要旨とする。

第５の特徴は、第２の特徴に係るノードにおいて、隣接ノードとのリンクに変化が生じた場合、変化の生じたリンク以外の各リンクに対し、ブルームフィルターの更新を要求する更新要求メッセージを送信する更新要求メッセージ送信部をさらに備えることを要旨とする。

第６の特徴は、第２の特徴に係るノードにおいて、ブルームフィルターの更新を要求する更新要求メッセージを隣接ノードから受信した場合、記憶されたブルームフィルターを更新するか否かを判定し、判定結果に応じて記憶されたブルームフィルターを更新する更新処理部と、ブルームフィルターが更新された場合、更新されたブルームフィルターに対応するリンク以外の各リンクに対し、更新要求メッセージを送信する更新要求メッセージ送信部とを備えることを要旨とする。

第７の特徴は、第５又は第６の特徴に係るノードにおいて、更新要求メッセージ送信部は、更新の要求が許可された場合、更新の要求を許可したノードとのリンク以外の各リンクに対応するブルームフィルターと、自ノードのノード識別子を変換して得られたビット列との演算結果を、更新の要求を許可したノードへ送信することを要旨とする。

第８の特徴は、第２〜第７のいずれかの特徴に係るノードにおいて、データ送信部は、データの送信先ノードのノード識別子を検索キーとして、記憶されたブルームフィルターとリンク毎に比較し、比較結果に応じてデータを送信するリンクを複数のリンクから選択することを要旨とする。

本発明の第９の特徴は、複数のノードによって構成されるアドホックネットワークに適用される経路制御方法であって、各ノードが、複数の隣接ノードとの間に複数のリンクをそれぞれ設定するステップと、リンク先に存在する各ノードを一意に識別するノード識別子をキーとしたブルームフィルターを各リンクと対応づけて記憶するステップと、データ送信時において、記憶されたブルームフィルターを経路情報として使用するステップとを含むことを要旨とする。

本発明の第１０の特徴は、複数のノードによって構成されるアドホックネットワークに用いられる経路制御プログラムであって、各ノードに、複数の隣接ノードとの間に複数のリンクをそれぞれ設定する手順と、リンク先に存在する各ノードを一意に識別するノード識別子をキーとしたブルームフィルターを各リンクと対応づけて記憶する手順と、データ送信時において、記憶されたブルームフィルターを経路情報として使用する手順とを実行させることを要旨とする。

本発明によれば、アドホックネットワークにおいてデータ送信時と非送信時のオーバーヘッドを抑制し、さらに各ノードのＣＰＵリソースなどの消費を低減することのできるアドホックネットワーク、ノード、経路制御方法、及び経路制御プログラムを提供できる。

次に、図面を参照して、本発明の実施形態を説明する。以下の実施形態における図面の記載において、同一又は類似の部分には同一又は類似の符号を付している。

（ブルームフィルター）
本実施形態に係るアドホックネットワークを説明する前に、本実施形態に係るアドホックネットワークで利用されるブルームフィルターについて、文字列検索例を用いて説明する。先ず、図１（ａ）に示すフローチャートを参照して、ブルームフィルターの生成手順例を説明する。

図１（ａ）のステップＳ２０１において、Ｍビットのビット長を持ったビット列と、Ｎ個のハッシュ関数とが用意される（Ｎ，Ｍ；２以上の整数）。また、ビット列は初期状態ではすべてのビットを“０”とし、ハッシュ値は１からＭの範囲の値とする。図２の例では１０ビットのビット列と、３つのハッシュ関数とを用いている。

ステップＳ２０２において、ステップＳ２０１で用意されたハッシュ関数により、検索対象のデータ中のキーのハッシュ値が求められる。図２では、検索対象のデータを“アドホックネットワーク”とし、“モバイル”、“アドホック”、“ネットワーク”のそれぞれをキーとしている。キー“モバイル”は３つのハッシュ関数よりハッシュ値が１，１０，６となっている。

ステップＳ２０３において、ステップＳ２０２で求められた各キーのハッシュ値より、対応するビット列中のビットを“１”とする。図２では、キー“モバイル”は３つのハッシュ関数よりハッシュ値が１，１０，６となるため、キー“モバイル”のビット列では左から１、６、１０番目のビットを“１”としている。

ステップＳ２０４において、検索対象データ中のすべてのキーに対して、ビット列を生成したか否か判断される。検索対象データ中のすべてのキーに対して、ビット列を生成している場合、ステップＳ２０５に移行する。検索対象データ中のすべてのキーに対して、ビット列を生成していない場合、ステップＳ２０１に処理が戻る。この結果、検索対象データ中のすべてのキーについて、ステップＳ２０１〜Ｓ２０３が実行される。図２では、キー“アドホック”のハッシュ値７，１，３に対応するビットに“１”が設定され、キー“ネットワーク”のハッシュ値８，３，２に対応するビットに“１”が設定されている。

ステップＳ２０５において、ステップＳ２０１〜ステップＳ２０４で生成された各キーのビット列の論理和をとり、ブルームフィルターを生成する。図２では、キー“モバイル”のビット列“１００００１０００１”、キー“アドホック”のビット列“１０１０００１０００”、キー“ネットワーク”のビット列“０１１００００１００”の論理和操作を行い、“アドホックネットワーク”のブルームフィルター“１１１００１１１０１”を生成している。

次に、図１（ｂ）に示すフローチャートを参照して、文字列中よりキーを検索する場合を例として、ブルームフィルターの使用例を説明する。

図１（ｂ）のステップＳ３０１において、検索するキーに対して、ブルームフィルターの生成時に用いたハッシュ関数を用いて、ハッシュ値を求める。そして、図１（ａ）のステップＳ２０３と同様にハッシュ値よりキーのビット列を生成する。図２では、検索キーを“アドホック”とし、ステップＳ２０３と同様の方法にてビット列“１０１０００１０００”を生成している。

ステップＳ３０２において、図１（ａ）のステップＳ２０５にて生成したブルームフィルターと、検索キーのビット列とを比較する。検索キーのビット列にて立っているビットが、ステップＳ２０５のブルームフィルターと同位置のビットにおいてすべて立っていれば、検索を行うデータ中に検索キーが含まれている可能性がある。逆に１つでも立っていないものがあれば、検索対象データ中には確実に検索キーは含まれていない。図２では、検索対象データ“アドホックネットワーク”のブルームフィルター“１１１００１１１０１”と、検索キー“アドホック”のビット列“１０１０００１０００”とを比較しており、検索キー“アドホック”のビット列“１０１０００１０００”で立っているビットが検索対象データ“アドホックネットワーク”のブルームフィルター“１１１００１１１０１”においても同位置で立っているため、検索キー“アドホック”は検索対象データ“アドホックネットワーク”中に含まれていることが分かる。

ステップＳ３０２で「含まれている可能性がある」としているのは、ステップＳ２０５にてビット列の論理和操作を行っているため、いくつかの他のキーによってブルームフィルターが、検索キーのビット列と重複する可能性があるためである。このように、ブルームフィルターは「存在していないのに、存在している」という判定を確率的に許容する。

（アドホックネットワーク）
本実施形態に係るアドホックネットワークでは、ブルームフィルターをアドホックネットワークのルーティングプロトコルに用いる。上述したように、ブルームフィルターは、キーの存在のみをコンパクトなデータ構造で高速に判定するためのアルゴリズムである。「キーが存在しないのに存在している」という判定を確率的に許しつつデータ構造をコンパクトにしている。ブルームフィルターはビット列であり、キーのひとつひとつをハッシュ関数によりビット列に変換し、それらの論理和操作を行うことで構成される。

図３の例においては、複数のノードＡ〜Ｇによって、アドホックネットワーク２が形成されている。各ノードＡ〜Ｇは、ＣＰＵ、記憶装置、及び入出力装置等のハードウェア資源と、記憶装置に記憶されたソフトウェア資源を備えている。各ノードＡ〜Ｇとしては、例えば携帯電話等の移動通信端末に限らず、センサ等を使用してもかまわない。各ノードＡ〜Ｇでは、隣接ノード間にリンクが設定されている。

本実施形態では、ブルームフィルターを生成するためのキーとして、各ノードＡ〜Ｇを一意に識別するノード識別子（ノードＩＤ）を使用し、アドホックネットワーク２に存在するノードＡ〜Ｇの情報を複数のハッシュ関数を用いてブルームフィルターへ格納する。本実施形態で用いるブルームフィルターは、上述した固定長のビット列を用いるものとする。また、ハッシュ関数は適当数を用いるものとする。

各ノードＡ〜Ｇは、リンク毎にブルームフィルターを保持し、ブルームフィルターには対応するリンク先に存在するノードのノードＩＤの情報されている。各ノードＡ〜Ｇは、データ送信時において、ブルームフィルターを経路情報として参照する。具体的には、送信先ノードのノードＩＤより生成したビット列を各リンクにおけるブルームフィルターと比較し、送信先のノードＩＤによるビット列において立っている（“１”である）ビットが、ブルームフィルターと同位置で立っている場合には、該当するすべてのリンクへデータを送信する。

各ノードＡ〜Ｇは、以下のアルゴリズムに従ってブルームフィルターの更新を行う。各ノードは自ノードのリンクもしくはブルームフィルターに変化（他ノードの参加、離脱）があった場合には、ブルームフィルターの更新を要求する更新要求メッセージを、変化があったリンク以外のすべてのリンクへ送信する。また、更新要求メッセージには、固有のメッセージＩＤが付与されているものとし、更新要求メッセージを受信したノードは更新の可否をレスポンスとして送信する。

更新を受け入れたノードは、ブルームフィルターの更新を行い、受信した更新のメッセージを受信したリンク以外のすべてのリンクへ転送する。ブルームフィルターの更新は、対応するノード間でブルームフィルターの交換等を行うことで実現される。

上記アルゴリズムに沿うことで、各ノードＡ〜Ｇはアドホックネットワーク２に存在するノードに対しての経路情報をブルームフィルターへ集約し格納していくことができる。

本実施形態に係るアドホックネットワーク２によれば、リアクティブ型のルーティングプロトコルと比較し、データ送信要求後のフラッディングによるオーバーヘッドや遅延はなく、データ送信時のネットワーク負荷を最小限に抑えることができるといえる。また、各ノードが保持する経路情報は隣接ノード毎に１つのブルームフィルターであり、各ノードが持つ情報量をコンパクトにすることができる。

さらに、本実施形態のアルゴリズムはプロアクティブ型のルーティングプロトコル等で用いられているDijkstraのアルゴリズムに比べ、単純であり、各ノードの処理量を低減できる。

（ノード）
図４は、各ノードＡ〜Ｇの構成例を示している。図４に示すノードは、無線通信装置３１と、処理装置３２と、記憶装置３３とを備えている。無線通信装置３１は、例えば無線ＬＡＮ又はブルートゥース等を利用して無線通信を行う。記憶装置３３は、複数のハッシュ関数をあらかじめ記憶するハッシュ関数記憶部３３１と、ブルームフィルターを記憶するブルームフィルター記憶部３３２とを備える。具体的には、ブルームフィルター記憶部３３２は、リンク先に存在する各ノードを一意に識別するノードＩＤをキーとしたブルームフィルターを各リンクと対応づけて記憶する。

処理装置３２は、ブルームフィルター生成部３２１と、リンク設定部３２２と、データ送信部３２３と、追加処理部３２４と、更新処理部３２５と、更新要求メッセージ送信部３２６とを備える。リンク設定部３２２は、複数の隣接ノードとの間に複数のリンクをそれぞれ設定する。

データ送信部３２３は、データ送信時において、ブルームフィルター記憶部３３２に記憶されたブルームフィルターを経路情報として使用する。具体的には、データ送信部３２３は、データの送信先ノードのノードＩＤを検索キーとして、ブルームフィルター記憶部３３２に記憶されたブルームフィルターとリンク毎に比較し、比較結果に応じてデータを送信するリンクを複数のリンクから選択する。

追加処理部３２４は、アドホックネットワークに新たに参加する参加ノードから、参加ノードのノードＩＤを変換して得られたビット列を受信した場合、受信したビット列を参加ノードとのリンクに対応するブルームフィルターとしてブルームフィルター記憶部３３２に追加する。また、追加処理部３２４は、参加ノードとのリンク以外の各リンクに対応するブルームフィルターと、自ノードのノードＩＤを変換して得られたビット列との演算結果を参加ノードへ送信する。

更新要求メッセージ送信部３２６は、隣接ノードとのリンクに変化が生じた場合、変化の生じたリンク以外の各リンクに対し、更新要求メッセージを送信する。

更新処理部３２５は、ブルームフィルターの更新を要求する更新要求メッセージを隣接ノードから受信した場合、ブルームフィルター記憶部３３２に記憶されたブルームフィルターを更新するか否かを判定し、判定結果に応じてブルームフィルター記憶部３３２に記憶されたブルームフィルターを更新する。また、更新要求メッセージ送信部３２６は、ブルームフィルターが更新された場合、更新されたブルームフィルターに対応するリンク以外の各リンクに対し、更新要求メッセージを送信する。

さらに、更新要求メッセージ送信部３２６は、更新の要求が許可された場合、更新の要求を許可したノードとのリンク以外の各リンクに対応するブルームフィルターと、自ノードのノードＩＤを変換して得られたビット列との演算結果を、更新の要求を許可したノードへ送信する。

（ノード参加処理）
次に、ネットワークに新たなノードが参加した場合において、参加ノードと参加ノードの接続先ノード間でのブルームフィルターの更新について、図５（ａ）の構成図及び図５（ｂ）のフローチャートを用いて説明する。図５（ａ）では参加ノードＢが接続先ノードＡへ接続をしており、両ノード間でビット列をやり取りすることで、ブルームフィルターの更新をしている。

（１）図５（ｂ）のステップＳ５０１において、参加ノードは、自分のノードＩＤのハッシュ値をハッシュ関数より求める。その後、ハッシュ値よりビット列（ブルームフィルター）を生成し、接続先ノードへ送信する。図５（ａ）では、参加ノードＢがノードＩＤよりビット列を生成し、接続先ノードＡへ送信を行っている。

（２）ステップＳ５０２において、接続先ノードは、ステップＳ５０１で受信したビット列を、受信したリンクのブルームフィルターとして保持する。図５（ａ）では、接続先ノードＡは、受信したビット列をノードＢ間とのブルームフィルター４１２として保持している。

（３）ステップＳ５０３において、接続先ノードは、ステップＳ５０２にてビット列を受信したリンク以外のリンクのブルームフィルターと、自分のノードＩＤによるビット列の論理和をとり、参加ノードへ送信する。図５（ａ）では、接続先ノードＡが、ステップＳ５０２にてビット列を受信したリンク以外のリンクのブルームフィルター４１３〜４１５と、自分のノードＩＤによるビット列の論理和をとり、参加ノードＢへ送信を行っている。

（４）ステップＳ５０４において、参加ノードは、ステップＳ５０３にて接続先ノードから受信したビット列を、受信したリンクのブルームフィルターとして保持する。図５（ａ）では、参加ノードＢが、接続先ノードＡから受信したビット列を受信したリンクのブルームフィルター４１１として保持している。

（５）ステップＳ５０５において、接続先ノードは、自ノードのリンクに変化が生じたので、変化の生じたリンク以外のリンクへ更新要求メッセージを送信する。図５（ａ）では、ノードＡはリンクに変化が生じたため、変化が生じたリンク以外の各リンクへ更新要求メッセージを送信している。

（ブルームフィルター更新処理）
次に、更新要求メッセージを受信し、更新を受け入れた場合について、図６（ａ）の構成図及び図６（ｂ）のフローチャートを用いて説明する。図６（ａ）の例では、ノードＣが、ノードＡより更新要求メッセージを受信し、更新を許可した場合の図を示している。

（１）図６（ｂ）のステップＳ７０１において、送信元ノードは、自分のノードＩＤのハッシュ値をハッシュ関数より求める。その後、ハッシュ値よりビット列を生成したものと、送信先リンク以外の各リンクのブルームフィルターの論理和をとり、送信先ノードへ送信する。図６（ａ）では、ノードＡは、自ノードのノードＩＤによるビット列と、送信先ノードＣとのリンク以外の各リンクのブルームフィルター６１２，６１３，６１５の論理和をとり、ノードＣへ送信している。

（２）ステップＳ７０２において、送信先ノードは、ステップＳ７０１で受信したビット列を、受信したリンクのブルームフィルターとして保持する。図６（ａ）では、ノードＣは、ノードＡより受信したビット列を、ノードＡとのリンクのブルームフィルター６１６として保持している。

（３）ステップＳ７０３において、送信先ノードは、自ノードのリンクのブルームフィルターに変化が生じたため、変化が生じたリンク以外のリンクへ更新要求メッセージを送信する。図６（ａ）では、ノードＣが持つブルームフィルター６１６に変化が生じたため、ノードＣは、変化があったリンク以外の各リンクへ更新要求メッセージを送信している。

（ノード離脱処理）
次に、ノードがネットワークから離脱した場合について、図７（ａ）の構成図及び図７（ｂ）のフローチャートを用いて説明する。図７（ａ）では、ノードＢがアドホックネットワークより離脱し、ノードＡがそれを検知した場合を表している。

（１）ステップＳ９０１において、ノードは、隣接ノードの離脱を検知するとすべてのリンクへブルームフィルター更新のメッセージを送信する。図７（ａ）では、ノードＡが、ノードＢの離脱を検知し、すべてのリンクへブルームフィルター更新のメッセージを送信している。
（データ送信処理）
次に、データ送信時の手順について説明する。データ送信時にて、データ送信元ノードは、送信先をノードＩＤとして指定するものとする。以下、図８のフローチャートを用いて説明する。

ステップＳ１００１において、データ送信元ノードは、送信先のノードＩＤとハッシュ関数を用いてビット列を生成する。ここで用いるハッシュ関数、ブルームフィルターのビット数はブルームフィルターの更新で用いられたものと同様とする。

ステップＳ１００２において、データ送信元ノードは、ステップＳ１００１で生成したビット列と、送信元ノードがリンク毎に保持するブルームフィルターを比較する。

ステップＳ１００３において、データ送信元ノードは、ステップＳ１００１で生成したビット列において立っているビットが比較しているブルームフィルターにおいて同位置で立っているかチェックする。立っていればステップＳ１００４へ進む。立っていなければ他のリンクのブルームフィルターと比較する。

ステップＳ１００４において、リンクの先に送信先のノードが存在する可能性があるとみなし、データを送信する。

（その他の実施形態）
上記のように、本発明は実施形態によって記載したが、この開示の一部をなす論述及び図面はこの発明を限定するものであると理解すべきではない。この開示から当業者には様々な代替実施形態、実施例及び運用技術が明らかとなる。

例えば、上述した実施形態の手法においては、ネットワーク構成に変化が発生する度に、ネットワーク上に各ノードが対応する更新要求メッセージが流れることになる。そのため、トラヒックを最適化するため、ブルームフィルター更新の操作に以下の条件を追加しても良い。

（条件１）ブルームフィルター更新メッセージのメッセージＩＤが、以前に受け取ったブルームフィルター更新メッセージのメッセージＩＤと一致した場合には、ブルームフィルターの更新を行わず、メッセージを転送しない。

（条件２）他ノードから受信したブルームフィルターが、現在、受信したリンクで保持しているブルームフィルターと差異が無い場合、ブルームフィルターの更新を行わず、メッセージを転送しない。

（条件３）他ノードから受信したブルームフィルターに対して自分のノードＩＤによるビット列がすべて立っている場合、ブルームフィルターの更新、又は更新のメッセージを転送しない。

このように本発明は、ここでは記載していない様々な実施形態等を包含するということを理解すべきである。したがって、本発明はこの開示から妥当な特許請求の範囲の発明特定事項によってのみ限定されるものである。

図１（ａ）は本発明の実施形態に係るアドホックネットワークで使用されるブルームフィルターの生成処理手順を示すフローチャートであり、図１（ｂ）は本発明の実施形態に係るアドホックネットワークで使用されるブルームフィルターのキー検索手順を示すフローチャートである。本発明の実施形態に係るアドホックネットワークで使用されるブルームフィルターを説明するための模式図である。本発明の実施形態に係るアドホックネットワークの一例を示すネットワーク構成図である。本発明の実施形態に係るアドホックネットワークにおけるノードの構成例を示すブロック図である。図５（ａ）は本発明の実施形態に係るアドホックネットワークにおけるノード追加処理を説明するためのネットワーク構成図であり、図５（ｂ）は本発明の実施形態に係るアドホックネットワークにおけるノード追加処理手順を示すフローチャートである。図６（ａ）は本発明の実施形態に係るアドホックネットワークにおけるブルームフィルター更新処理を説明するための模式図であり、図６（ｂ）は本発明の実施形態に係るアドホックネットワークにおけるブルームフィルター更新処理手順を示すフローチャートである。図７（ａ）は本発明の実施形態に係るアドホックネットワークにおけるノード離脱処理を説明するためのネットワーク構成図であり、図７（ｂ）は本発明の実施形態に係るアドホックネットワークにおけるノード離脱処理手順を示すフローチャートである。本発明の実施形態に係るアドホックネットワークにおけるデータ送信処理手順を示すフローチャートである。

符号の説明

Ａ〜Ｇ…ノード
２…アドホックネットワーク
３１…無線通信装置
３２…処理装置
３３…記憶装置
３２１…ブルームフィルター生成部
３２２…リンク設定部
３２３…データ送信部
３２４…追加処理部
３２５…更新処理部
３２６…更新要求メッセージ送信部
３３１…ハッシュ関数記憶部
３３２…ブルームフィルター記憶部
４１１〜４１８，６１１〜６１８，８１１〜４１６…ブルームフィルター

Claims

複数のノードによって構成されるアドホックネットワークであって、
各ノードは、
複数の隣接ノードとの間に複数のリンクをそれぞれ設定するリンク設定部と、
リンク先に存在する各ノードを一意に識別するノード識別子をキーとし、前記ノード識別子を構成するビット列の論理和をとることによって生成されたブルームフィルターを各リンクと対応づけて記憶するブルームフィルター記憶部と、
データ送信時において、送信先ノードのノード識別子より生成したビット列を各リンクにおけるブルームフィルターと比較し、前記送信先ノードのノード識別子によるビット列において立っているビットが、前記ブルームフィルターと同位置で立っている場合には、該当するすべてのリンクへデータを送信するデータ送信部と、
隣接ノードとのリンクに変化が生じた場合、前記変化の生じたリンク以外の各リンクに対し、ブルームフィルターの更新を要求する更新要求メッセージを送信する更新要求メッセージ送信部と、
ブルームフィルターの更新を要求する更新要求メッセージを隣接ノードから受信した場合、前記記憶されたブルームフィルターを更新するか否かを判定し、判定結果に応じて前記記憶されたブルームフィルターを更新する更新処理部と、
前記ブルームフィルターが更新された場合、前記更新されたブルームフィルターに対応するリンク以外の各リンクに対し、前記更新要求メッセージを送信する更新要求メッセージ送信部
とを備えることを特徴とするアドホックネットワーク。
複数のノードによって構成されるアドホックネットワークにおけるノードであって、
複数の隣接ノードとの間に複数のリンクをそれぞれ設定するリンク設定部と、
リンク先に存在する各ノードを一意に識別するノード識別子をキーとし、前記ノード識別子を構成するビット列の論理和をとることによって生成されたブルームフィルターを各リンクと対応づけて記憶するブルームフィルター記憶部と、
データ送信時において、送信先ノードのノード識別子より生成したビット列を各リンクにおけるブルームフィルターと比較し、前記送信先ノードのノード識別子によるビット列において立っているビットが、前記ブルームフィルターと同位置で立っている場合には、該当するすべてのリンクへデータを送信するデータ送信部と、
隣接ノードとのリンクに変化が生じた場合、前記変化の生じたリンク以外の各リンクに対し、ブルームフィルターの更新を要求する更新要求メッセージを送信する更新要求メッセージ送信部と、
ブルームフィルターの更新を要求する更新要求メッセージを隣接ノードから受信した場合、前記記憶されたブルームフィルターを更新するか否かを判定し、判定結果に応じて前記記憶されたブルームフィルターを更新する更新処理部と、
前記ブルームフィルターが更新された場合、前記更新されたブルームフィルターに対応するリンク以外の各リンクに対し、前記更新要求メッセージを送信する更新要求メッセージ送信部
とを備えることを特徴とするノード。
前記アドホックネットワークに新たに参加する参加ノードから、前記参加ノードのノード識別子を変換して得られたビット列を受信した場合、前記受信したビット列を前記参加ノードとのリンクに対応するブルームフィルターとして前記ブルームフィルター記憶部に追加する追加処理部をさらに備えることを特徴とする請求項２に記載のノード。
前記追加処理部は、前記参加ノードとのリンク以外の各リンクに対応するブルームフィルターと、自ノードのノード識別子を変換して得られたビット列との演算結果を前記参加ノードへ送信することを特徴とする請求項３に記載のノード。
前記更新要求メッセージ送信部は、前記更新の要求が許可された場合、前記更新の要求を許可したノードとのリンク以外の各リンクに対応するブルームフィルターと、自ノードのノード識別子を変換して得られたビット列との演算結果を、前記更新の要求を許可したノードへ送信することを特徴とする請求項２に記載のノード。
複数のノードによって構成されるアドホックネットワークに適用される経路制御方法であって、各ノードが、
複数の隣接ノードとの間に複数のリンクをそれぞれ設定するステップと、
リンク先に存在する各ノードを一意に識別するノード識別子をキーとし、前記ノード識別子を構成するビット列の論理和をとることによって生成されたブルームフィルターを各リンクと対応づけて記憶するステップと、
データ送信時において、送信先ノードのノード識別子より生成したビット列を各リンクにおけるブルームフィルターと比較し、前記送信先ノードのノード識別子によるビット列において立っているビットが、前記ブルームフィルターと同位置で立っている場合には、該当するすべてのリンクへデータを送信するステップと、
隣接ノードとのリンクに変化が生じた場合、前記変化の生じたリンク以外の各リンクに対し、ブルームフィルターの更新を要求する更新要求メッセージを送信するステップと、
ブルームフィルターの更新を要求する更新要求メッセージを隣接ノードから受信した場合、前記記憶されたブルームフィルターを更新するか否かを判定し、判定結果に応じて前記記憶されたブルームフィルターを更新するステップと、
前記ブルームフィルターが更新された場合、前記更新されたブルームフィルターに対応するリンク以外の各リンクに対し、前記更新要求メッセージを送信するステップ
とを含むことを特徴とする経路制御方法。
複数のノードによって構成されるアドホックネットワークに用いられる経路制御プログラムであって、各ノードに、
複数の隣接ノードとの間に複数のリンクをそれぞれ設定する手順と、
リンク先に存在する各ノードを一意に識別するノード識別子をキーとし、前記ノード識別子を構成するビット列の論理和をとることによって生成されたブルームフィルターを各リンクと対応づけて記憶する手順と、
データ送信時において、送信先ノードのノード識別子より生成したビット列を各リンクにおけるブルームフィルターと比較し、前記送信先ノードのノード識別子によるビット列において立っているビットが、前記ブルームフィルターと同位置で立っている場合には、該当するすべてのリンクへデータを送信する手順と、
隣接ノードとのリンクに変化が生じた場合、前記変化の生じたリンク以外の各リンクに対し、ブルームフィルターの更新を要求する更新要求メッセージを送信する手順と、
ブルームフィルターの更新を要求する更新要求メッセージを隣接ノードから受信した場合、前記記憶されたブルームフィルターを更新するか否かを判定し、判定結果に応じて前記記憶されたブルームフィルターを更新する手順と、
前記ブルームフィルターが更新された場合、前記更新されたブルームフィルターに対応するリンク以外の各リンクに対し、前記更新要求メッセージを送信する手順
とを実行させることを特徴とする経路制御プログラム。