JP3860175B2 - アドホックネットワーク環境における効率的なｉｐアドレスの割り当て及び重複検出方法 - Google Patents

Description

本発明は、効率的なＩＰアドレスの割り当て及び重複検出方法に関し、特に、インフラストラクチャー(Infrastructure)のないアドホックネットワーク(Adhoc network)環境で各端末が自ら自分のＩＰアドレスを割り当て、ネックワーク上の他の端末とＩＰアドレスが重複するか否かを検出することにより、全体ネットワークに対する負荷を減らし且つ既存のルーチンプロトコルと共に使用することが可能なＩＰアドレスの割り当て及び重複検出方法に関する。

アドホックネットワークは、インフラストラクチャーのない環境で無線端末間に生成されたネットワークであって、中心となるサーバがないため、ＤＨＣＰサーバなどを用いて無線端末に動的にＩＰアドレスを割り当てることが不可能である。

従って、アドホックネットワークでは、中心となるサーバがないため、それぞれの端末は自らＩＰアドレスを割り当てなければならないとともに、他の端末との通信を可能にするゼロコンフィグレーション(Zero Configuration)機能を持たなければならない。

中心となるサーバのない状況で端末が自らＩＰを割り当てる場合、他の端末のＩＰアドレスと衝突しないようにするため、自分のＩＰアドレスがアドホックネットワーク上において唯一であるか否かを検査しなければならないが、アドホックネットワーク環境でＩＰアドレスの衝突を感知することは、有線ネットワークとは異なり、非常に複雑な問題である。その理由は、アドホックネットワークでは端末が移動するので、互いに異なるネットワークが合併或いは分離するなどの複雑かつ予測不可能なトポロジーの変化があるからである。

従来では、アドホックネットワーク内の各端末毎に唯一のＩＤを有し、この唯一のＩＤが端末のＭＡＣ(Media Access Control)アドレス又は任意の数から生成されると仮定し、このように生成された唯一のＩＤとＩＰアドレスを一対にして、他の端末のＩＰアドレスと重複するか否かを検査する方法を採用している。

他の方法として、１つのアドホックネットワーク毎にネットワークを区分する唯一のＩＤを有すると仮定する。このＩＤも任意の数から生成されることができる。ネットワークのＩＤは、２つのアドホックネットワークが合併することを感知する。

まず、各端末が唯一のＩＤを有すると仮定した場合、各端末はルーチンテーブルの形成過程で自分のＩＰアドレスと唯一のＩＤを他の端末に伝達する。このように伝達されたＩＰアドレスはルーチンテーブルのＩＰアドレスと同一であるが、ＩＤが異なる場合、２つの相異した端末が１つのＩＰアドレスを使用していることを感知することができる。

アドホックネットワーク毎に唯一のＩＤを有すると仮定した場合、各端末は、既に形成されたアドホックネットワークの端末からＩＰアドレスの割り当てを受ける。従って、アドホックネットワークの他の端末とはＩＰアドレスが重複することがない。２つのアドホックネットワークが合併する場合が発生すると、アドホックネットワークのＩＤによって合併を感知する。２つのアドホックネットワークは、ＩＰアドレス割り当てテーブルを交換することにより、アドホックネットワーク間の重複ＩＰアドレスを検出することができる。重複するＩＰアドレスは合併したアドホックネットワークの全体端末に再び割り当てられる。

ところが、従来の技術では、まず唯一の端末のＩＤ、アドホックネットワークのＩＤを生成し得ると仮定するが、両端末がいずれの事前約束又は通信もなく唯一のＩＤを生成することは不可能である。言い換えれば、ＭＡＣアドレスも重複する可能性があるため、これを用いてＩＤを生成するとしても唯一であると保障することはできない。従って、ＩＤが重複する場合、従来の技術は重複ＩＰアドレスを検出することができなくなる。

また、従来の技術では、ネットワーク全体にブロードキャストを行う方式を取るため、アドホックネットワークにおいて、ブロードキャストは相当の負荷が発生するので、ネットワークに多くの負担を与える。

したがって、従来の技術は、アドホックネットワークの特性上、トポロジーが予測不可能な形に変化するから、ＩＰ重複を検出するために複雑な方法を用いるうえ、様々な状況に対する様々な対処にも拘らず依然としてトポロジーの変化に弱いため、端末の移動又は通信障害が、これらの技術に致命的な影響を与えるおそれがあるという問題点がある。

本発明は、このような従来の問題点を解決するためのもので、その目的は、このようなアドホックネットワーク環境で端末がＩＰアドレスを自ら割り当て、ＩＰアドレスの衝突を効率よく感知して処理することが可能な方法を提供することにある。

上記目的を達成するために、本発明は、端末に最初のＩＰアドレスを割り当てる段階と、ハローメッセージ(Hello Message)を送受信する段階と、前記ハローメッセージの送受信段階で重複するアドレスを検出する段階と、ＤＡＤテーブルの検索と履歴テーブルの検索によってＤＡＤテーブルを更新する段階と、ＤＡＤタイマーハンドラーを用いて、ＩＰアドレスの衝突が発生したか否かを判断する段階とを含む、アドホックネットワーク環境における効率的なＩＰアドレスの割り当て及び重複検出方法を提供する。

既存の発明は、ネットワーク全体にわたってブロードキャストを行ってネットワークに多くの負荷を与えたが、本発明は、周期的に発生する１ホップブロードキャストを用いて全体ネットワークに対する負荷を減らした。また、既存の発明は、ネットワークが分離或いは合併するなどの変化に弱いが、本発明は、簡単な構造によってさらに優れた安定性を示す。

また、既存の発明は、各端末が唯一のＩＤを持つことができないため、一定の時間の経過後にＩＤが変更されることにより、アドレスとＩＤとが同一であって重複アドレスの検出が不可能であるが、本発明は、このような場合の発生を防止する。

以下、本発明に係るアドホックネットワーク環境における効率的なＩＰアドレスの割り当て及び重複検出方法を添付図面に基づいて詳細に説明する。

アドホックネットワークにある端末はいずれもシーケンス番号（以下、「ＳＥＱ＿ＮＵＭ」と称する）、臨時ＩＤ（以下、「ＴＩＤ」と称する）、ＤＡＤタイマー(DAD Timer)、ＤＡＤテーブル(DAD Table)、履歴テーブル(History Table)を有する。次に、本発明の理解を助けるためにこれらの用語について概略的に説明する。
１．ＤＡＤタイマーはタイムアウトを発生するたびにＳＥＱ＿ＮＵＭとＴＩＤを更新する。
２．ＳＥＱ＿ＮＵＭはＤＡＤタイマーのタイムアウトが発生するたびに１ずつ増加する（初期値は１である）。
３．ＴＩＤはＤＡＤタイマーのタイムアウトが発生するたびにさらに生成される（Ｏｘｆｆｆｆはアドレスの衝突を意味する）。
４．図４に示したＤＡＤ(Duplicate Address Detection)テーブルはルーチンテーブルの一部となることもできるが、ＤＡＤテーブルにおいて、１つのエントリー(Entry)は、ネットワーク内にある端末のＩＰアドレス、端末のＳＥＱ＿ＮＵＭ、端末のＴＩＤ及びフラグからなり、周期的な１ホップ(hop)ブロードキャストメッセージ（以下、「ハローメッセージ」と称する）によって更新される。ここで、ＩＰアドレスは端末がネットワークで通信を行うために使用される固定アドレスであり、ＳＥＱ＿ＮＵＭとＴＩＤはＩＰアドレスを使用する端末が唯一であるか否かを確認するための値であり、フラグはテーブルにおける１つのエントリーの状態を示す。また、ＤＡＤテーブルは、新しい情報を受信すると、エントリーに格納し、フラグ(flag)を１と設定し、ハローメッセージで伝送すると、フラグを０と設定する。
５．図５に示した履歴テーブルは、現在端末が生成した最近のＳＥＱ＿ＮＵＭとＴＩＤを格納する。端末の電源をオンにし、最初のＩＰアドレスを割り当てるために、ＩＰ割り当て要請メッセージ(IP Allocate Request Message)とＩＰ割り当て応答メッセージ(IP Allocate Response Message)が使用される。ＩＰアドレスの割り当てを希望する端末は、図１に示したＩＰ割り当て要請メッセージで、自分が使用しようとするＩＰアドレスを周辺端末に送る。周辺端末は、図２に示したＩＰ割り当て応答メッセージでこれに応答する。ＩＰ割り当て要請メッセージにはメッセージタイプ、メッセージ長さ、使用しようとするＩＰアドレスが含まれる。ＩＰ割り当て応答メッセージにはメッセージタイプ、メッセージ長さ、使用可能なＩＰアドレスが含まれる。

ＩＰアドレスの割り当て以後、重複ＩＰアドレスの検出のために、各ノードは図３に示したハローメッセージを周期的に伝達する。ハローメッセージは、メッセージタイプ、メッセージ長さ、ハローメッセージを送る端末の情報を格納したソースノード(Source Node)フィールドと、ネットワークにある端末の情報を格納した宛先ノード(Destination Node)フィールドとから構成される。

次に、自動アドレス割り当てとアドレス重複検出のための方法を図６ないし図１２に基づいて説明する。

最初に、端末に電源を印加すると、まずＩＰアドレスの割り当てを受けなければならないが、これは図６に示した最初のＩＰアドレス割り当て(Initial IP Address Allocation)方法によって行われる。これについて簡略に説明すると、次の通りである。

端末は最初に自分のＩＰアドレスを任意の数字で割り当てた後、ＩＰ割り当て要請メッセージによって、１ホップ内の周辺端末に臨時アドレスを使用し得るか否かを尋ねる。

その後、周辺端末は、自分のＤＡＤテーブルとＩＰ割り当て要請メッセージによって伝達されたＩＰアドレスを比較するが、もしＩＰアドレスが重複すれば、ＤＡＤテーブルにない任意のＩＰアドレスを選択してＩＰ割り当て応答メッセージによって伝達し、重複しなければ応答しない。

その次、ＩＰアドレスの割り当てを要請した端末は、周辺端末から応答がくる場合、ネットワーク上の他の端末とＩＰアドレスが重複することを意味するので、周辺端末により選択されたＩＰアドレスをもってさらにＩＰ割り当て要請メッセージを送る。

この過程は、周辺端末からＩＰ割り当て応答メッセージを受信しなくなるまでＮ回繰り返し行われる。Ｎ回以上応答がない場合、臨時ＩＰアドレスを端末のＩＰアドレスとして使用する。

このような過程を経て最初のＩＰアドレスの割り当てが行われるが、その後にはハローメッセージの送信と受信が繰り返し行われることにより、重複アドレスを検出する。以下、ハローメッセージの送信方法を図８に基づいて説明する。

まず、端末は自分のＩＰアドレス、ＳＥＱ＿ＮＵＭ及びＴＩＤをソースノードフィールドに格納した後、ＤＡＤテーブルにおいてフラグが１のエントリーが在る場合、これらの内容を宛先ノードフィールドに格納し、ハローメッセージを１ホップ内の周辺端末に伝達するが、このように伝達されたハローメッセージの受信方法は図７に示されている。

図７に示すように、ハローメッセージを受信すると、ソースノードフィールドと宛先ノードフィールドを含んだ全体フィールドから１つのノードフィールドを持ってきた後、そのノードフィールドＦ（ｍ）のＩＰアドレスが現在端末のＩＰアドレスと同一であれば、図１１に示した履歴テーブル検索を行い、ＩＰアドレスと同一でなければ、Ｆ（ｍ）のＩＰアドレスを有するエントリーがＤＡＤテーブルにあるか否かを判断する。Ｆ（ｍ）のＩＰアドレスを有するエントリーがＤＡＤテーブルにあれば、図１０に示したＤＡＤテーブル検索を行う。前記履歴テーブル検索方法とＤＡＤテーブル検索方法については後述する。

一方、以上の２つの場合に属さなければ、新しいノード情報を受信したはずなので、ＤＡＤテーブルに格納し、フラグを１と設定する。この過程を、ハローメッセージから持ってくるノードフィールドがない時まで繰り返し行う。

以下、ＤＡＤテーブル検索方法を図１０に基づいて説明する。

まず、ハローメッセージから持ってきたノードフィールドＦ（ｍ）と同じＩＰアドレスを有するエントリーＥ（ｔ）とのＳＥＱ＿ＮＵＭを比較するが、Ｆ（ｍ）のＳＥＱ＿ＮＵＭをＳｅｑ＿ｍ、Ｅ（ｔ）のＳＥＱ＿ＮＵＭをＳｅｑ＿ｔとすれば、Ｓｅｑ＿ｔが０の場合、Ｅ（ｔ）をＦ（ｍ）に更新し、Ｓｅｑ＿ｍがＳｅｑ＿ｔより小さい場合、古い情報が入ってきたと判断してＥ（ｔ）を更新しない。

一方、Ｓｅｑ＿ｍとＳｅｑ＿ｔが同一の場合、Ｆ（ｍ）に含まれたＴＩＤとしてのＴＩＤ＿ｍとＥ（ｔ）に含まれたＴＩＤとしてのＴＩＤ＿ｔとを比較するが、ＴＩＤ＿ｍとＴＩＤ＿ｔとが互いに異なる場合、同じＩＰアドレスを使用する端末が２つ以上なので、Ｅ（ｔ）のＴＩＤをＯｘｆｆｆｆに変更し、フラグを１に変更して、次のハローメッセージによってネットワーク全体に衝突事実が伝達されるようにし、もしＴＩＤ＿ｍとＴＩＤ＿ｔとが互いに同一の場合、同一の情報が入ってきたと判断し、Ｅ（ｔ）を変更せずにリターンする。

最後に、Ｓｅｑ＿ｍがＳｅｑ＿ｔより大きい場合、新しい情報が入ってきたと判断し、Ｅ（ｔ）をＦ（ｍ）に更新する。

次に、履歴テーブル検索方法を図１１に基づいて説明する。

ハローメッセージから持ってきたノードフィールドＦ（ｍ）に含まれたＳＥＱ＿ＮＵＭのＳｅｑ＿ｍと、現在端末のＳＥＱ＿ＮＵＭのＳｅｑ＿ｎとを比較するが、Ｓｅｑ＿ｍがＳｅｑ＿ｎより小さい或いは同一であれば、端末の履歴テーブルに、Ｓｅｑ＿ｍのＳＥＱ＿ＮＵＭを有するエントリーがあるか否かを検査し、エントリーがなければ変更せずにリターンする。

一方、端末の履歴テーブルに、Ｓｅｑ＿ｍのＳＥＱ＿ＮＵＭを有するエントリーがあれば、そのエントリーをＥ（ｈ）に設定した後、Ｆ（ｍ）に含まれたＴＩＤ（ＴＩＤ＿ｍ）とＥ（ｈ）のＴＩＤ（ＴＩＤ＿ｈ）とを比較し、ＴＩＤ＿ｍとＴＩＤ＿ｈとが同一であれば変更せずにリターンし、ＴＩＤ＿ｍとＴＩＤ＿ｈとが同一でなければ（Ｓｅｑ＿ｍがＳｅｑ＿ｎより大きい場合）、ＩＰ衝突検出(Detect IP Conflict)方法を実行する。次に、ＩＰ衝突検出方法を図１２に基づいて説明する。

まず、制限時間（例えば、ＤＡＤタイマーのタイムアウト＊Ｎ）内に端末のＩＰアドレスに対するＩＰ衝突検出を実行したか否かを判断するが、制限時間内にＩＰ衝突検出が実行したならば、制限時間内にアドレス衝突感知が２回行われたことを意味し、このような場合、最初のＩＰアドレス割り当てによってＩＰアドレスをさらに端末に割り当てる。

この際、制限時間内にＩＰ衝突検出が実行されたか否かを判断するために、ＤＡＤタイマーハンドラーはタイムアウトの発生有無をチェックし続ける。次に、ＤＡＤタイマーハンドラーの動作について図９を参照して簡略に説明する。

図９に示すように、ＤＡＤタイマーは、タイムアウトが発生すると、現在端末のＳＥＱ＿ＮＵＭを１だけ増加させ、現在端末のＴＩＤを新たに生成するが、ＤＡＤタイマーハンドラーがＮ回実行される間、更新していないＤＡＤテーブルのエントリーがあればこのエントリーのＳＥＱ＿ＮＵＭを０と設定し（０と設定した効果は図１０に示されている）、ＤＡＤタイマーハンドラーがＭ回実行される間、更新されていないＤＡＤテーブルのエントリーはＤＡＤテーブルから削除する（ＭはＮより充分大きい値である）。

一方、制限時間内にＩＰ衝突検出を実行しない場合、端末のＩＰアドレスを変更するか或いはそのまま使用し続けるかを決定するが、もしＩＰアドレスを変更すれば、最初のＩＰアドレス割り当てを実行し、ＩＰアドレスを変更しなければ、ＩＰアドレスが衝突したことを同じアドレスを使う相手に知らせるために、現在端末のＳＥＱ＿ＮＵＭをＦ（ｍ）のＳＥＱ＿ＮＵＭ＋１に設定した後、ＴＩＤをさらに生成する。この際、更新した情報は次のハローメッセージによってネットワークに伝達される。

ＩＰ割り当て要請メッセージの形式を示す図である。 ＩＰ割り当て応答メッセージの形式を示す図である。 ハローメッセージの形式を示す図である。 ＤＡＤテーブルの形式を示す図である。 履歴テーブルの形式を示す図である。 最初のＩＰアドレスの割り当て方法を示すフローチャートである。 ハローメッセージの受信を処理する方法を示すフローチャートである。 ハローメッセージの送信を処理する方法を示すフローチャートである。 ＤＡＤタイマーハンドラーの動作を示すフローチャートである。 ＤＡＤテーブルを更新し、重複アドレスを検出する方法を示すフローチャートである。 履歴テーブルを用いて重複アドレスを検出する方法を示すフローチャートである。 重複アドレスを検出したときの処理を示すフローチャートである。

Claims (1)

1. アドホックネットワーク環境で端末にＩＰアドレスを割り当て、ＩＰアドレスの重複を検出する方法において、
   端末に最初のＩＰアドレスを割り当てる段階と、
   ハローメッセージを送受信する段階と、
   前記ハローメッセージの送受信段階で重複するアドレスを検出する段階と、
   ＤＡＤテーブルの検索と履歴テーブルの検索によってＤＡＤテーブルを更新する段階と
   を含み、
   前記ＤＡＤテーブルは、ＩＰアドレスと、所定時間が経過する度にインクリメントされるシーケンス番号と、該所定時間が経過する度にさらに生成される臨時ＩＤとを有するエントリーを、前記アドホックネットワーク内の複数の端末について具備し、
   前記履歴テーブルは、前記端末の前記シーケンス番号と前記臨時ＩＤとの履歴を具備し、
   前記ハローメッセージは、周期的な１ホップブロードキャストメッセージであり、前記ＩＰアドレスと前記シーケンス番号と前記臨時ＩＤとを有するノードフィールドを、該ハローメッセージの送信端末を含む複数の端末について具備し、
   前記ハローメッセージを受信した受信端末が、該ハローメッセージから１つのノードフィールドを取り出し、該ノードフィールド内のＩＰアドレスが該受信端末のＩＰアドレスと異なり、かつ、該ノードフィールド内のＩＰアドレスを有するエントリーが該受信端末のＤＡＤテーブル内にあり、かつ、該ノードフィールド内のシーケンス番号が該エントリーのシーケンス番号と同一であり、かつ、該ノードフィールド内の臨時ＩＤが該エントリーの臨時ＩＤと異なる場合、ＩＰアドレスの重複が発生したと判断し、該エントリーの臨時ＩＤを該重複を示す値に更新する
   ことを特徴とするアドホックネットワーク環境における効率的なＩＰアドレスの割り当て及び重複検出方法。

Images