(57)【要約】  【課題】  重複アドレスのエントリがルーティングテーブルから全て破棄されてしまうので、アドレスが重複する一方のノード宛に送信されたパケットが他方のノードに誤って転送されることはないが、正規の宛先である一方のノードへも転送されなくなってしまう。  【解決手段】  自ノードを宛先とする経路要求メッセージを解析して、その送信元アドレスおよび宛先シーケンス番号を抽出する手段と、前記抽出された送信元アドレスに基づいて、送信元ノードとの通信履歴の有無を判定する手段と、前記送信元ノードとの通信履歴が存在せず、かつ前記抽出された宛先シーケンスが、これが未知であるときに付される所定の識別子以外であるときに重複アドレスの存在を検出する重複アドレス検出手段と、前記経路要求メッセージに基づいて重複アドレスの存在を検出できないときに経路応答メッセージを返信する手段とを含む。  【選択図】  図１
2005064848.tif 000002
【特許請求の範囲】
【請求項１】
複数の無線ノードを含み、送信元ノードと宛先ノードとが少なくとも１つの中継ノードを経由してパケット交換を行うアドホックネットワークにおける重複アドレス検出方法において、
宛先ノードが送信元ノードから受信した経路要求メッセージを解析し、その送信元アドレスに基づいて送信元ノードとの通信履歴を判定する手順と、
前記宛先ノードが、前記送信元ノードとの通信履歴が存在しないにもかかわらず前記経路要求メッセージに宛先シーケンス番号が登録されているときに重複アドレスの存在を検出する手順と、
前記宛先ノードが、前記重複アドレスの存在を検出できないときに経路応答メッセージを返信する手順と、
中継ノードが前記経路応答メッセージを受信し、宛先アドレス、送信元アドレスおよび次ホップを含むルーティング情報をルーティングテーブルへ登録する手順と、
前記中継ノードが、前記送信元ノードから宛先ノード宛に送信されたパケットの次ホップを、その宛先アドレスおよび送信元アドレスに基づいて前記ルーティングテーブルから検索する手順とを含むことを特徴とするアドホックネットワークにおける重複アドレス検出方法。
【請求項２】
前記送信元ノードは、宛先シーケンス番号が既知の宛先へは当該宛先シーケンス番号を付与し、宛先シーケンス番号が未知の宛先へは所定の識別子を付与した経路要求メッセージを送信し、
前記宛先ノードは、前記送信元ノードとの通信履歴が存在しないにもかかわらず前記経路要求メッセージに前記所定の識別子が付与されていないときに重複アドレスの存在を検出することを特徴とする請求項１に記載のアドホックネットワークにおける重複アドレス検出方法。
【請求項３】
前記重複アドレスの存在を検出した宛先ノードが、重複アドレス解消用のデータをネットワーク上に送信する手順を含むことを特徴とする請求項１または２に記載のアドホックネットワークにおける重複アドレス検出方法。
【請求項４】
アドホックネットワークを構成する各無線ノードに実装される重複アドレス検出装置において、
自ノードを宛先とする経路要求メッセージを解析し、その送信元アドレスに基づいて送信元ノードとの通信履歴の有無を判定する手段と、
前記送信元ノードとの通信履歴が存在しないにもかかわらず前記経路要求メッセージに宛先シーケンス番号が登録されているときに重複アドレスの存在を検出する重複アドレス検出手段と、
前記重複アドレスの存在を検出できないときに経路応答メッセージを返信する手段とを含むことを特徴とするアドホックネットワークにおける重複アドレス検出装置。
【請求項５】
前記重複アドレス検出手段は、前記送信元ノードとの通信履歴が存在しないにもかかわらず、前記経路要求メッセージに、宛先シーケンス番号が未知であることを示す所定の識別子が付与されていないときに重複アドレスの存在を検出することを特徴とする請求項４に記載のアドホックネットワークにおける重複アドレス検出装置。
【請求項６】
重複アドレス解消用のデータを送信する重複アドレス解消手段を含むことを特徴とする請求項４または５に記載のアドホックネットワークにおける重複アドレス検出装置。
【請求項７】
経路応答メッセージを受信し、宛先アドレス、送信元アドレスおよび次ホップを含むルーティング情報をルーティングテーブルへ登録する手段と、
他ノード宛のパケットの次ホップを、その宛先アドレスおよび送信元アドレスに基づいて前記ルーティングテーブルから検索する手段と、
前記他ノード宛のパケットを前記検索された次ホップへ転送する手段とを含むことを特徴とする請求項４ないし６のいずれかに記載のアドホックネットワークにおける重複アドレス検出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、重複アドレスの検出方法および検出装置に係り、特に、マルチホップ・ワイヤレス・モバイル・アドホックネットワーク（以下、アドホックネットワークと呼ぶ）において重複アドレスを検出できる重複アドレス検出方法および検出装置に関する。
【背景技術】
【０００２】
重複アドレスの検出を行うために、従来はルーティングプロトコルに重複アドレスを検出する機能が導入されていた。ネットワーク内でのノードの識別には、IPアドレスのみならずMACアドレスもしくはランダムに生成した識別情報が用いられる。従来技術では、ルーティングプロトコルの経路探索要求メッセージ（Route Request: RREQ）や経路探索要求応答メッセージ（Route Reply:RREP）などの経路制御メッセージに、通常記載されるIPアドレスに加えて、MACアドレスもしくはランダムに生成した識別情報がKeyとして付加される。これより、RREQには（宛先IPアドレスと宛先Keyの組）および（送信元IPアドレスと送信元Keyの組）とが記載されることになる。宛先および送信元の（IPアドレス＋Key）の組は、経路探索に伴いRREQやRREPに含められ、これらの経路制御メッセージを受信した各ノードのルーティングテーブルのエントリに保存される。
【０００３】
各ノードは、新たな経路制御メッセージを受信するたびに、その経路制御メッセージに含まれる（IPアドレス＋Key）の組とルーティングテーブルの各エントリに既登録の（IPアドレス＋Key）の組とを比較し、IPアドレスが一致するにもかかわらずKeyが異なる場合、重複したアドレスを持つノードがネットワーク内に存在することを検出する。重複アドレスが検出されると、重複アドレスのエントリは全て破棄され、重複アドレスを持つ各ノードは新たなアドレスを得るための処理（リナンバリング）を行う。これより、宛先が重複アドレスであるパケットは転送されなくなるので、アドレスが重複する一方のノード宛に送信されたパケットが、アドレスが重複する他方のノードに誤って転送されることが防止される。
【非特許文献１】N. H. Vaidya,"Weak duplicate address detection in mobile ad hoc networks", In the Proc. of ACM MobiHoc 2002, June 2002, RR. 206-216.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
上記した従来技術では、重複アドレスのエントリがルーティングテーブルから全て破棄されてしまうので、アドレスが重複する一方のノード宛に送信されたパケットが、アドレスが重複する他方のノードに誤って転送されることが防止される一方で、正規の宛先である一方のノードへも転送されなくなってしまうという技術課題があった。
【課題を解決するための手段】
【０００５】
本発明は、複数の無線ノードを含み、送信元ノードと宛先ノードとが少なくとも１つの中継ノードを経由してパケット交換を行うアドホックネットワークにおける重複アドレス検出方法および装置において、以下のような手段を講じた点に特徴がある。
【０００６】
(1)本発明の重複アドレス検出方法は、宛先ノードが送信元ノードから受信した経路要求メッセージを解析し、その送信元アドレスに基づいて送信元ノードとの通信履歴を判定する手順と、前記宛先ノードが、前記送信元ノードとの通信履歴が存在しないにもかかわらず前記経路要求メッセージに宛先シーケンス番号が登録されているときに重複アドレスの存在を検出する手順と、前記宛先ノードが、前記重複アドレスの存在を検出できないときに経路応答メッセージを返信する手順と、中継ノードが前記経路応答メッセージを受信し、宛先アドレス、送信元アドレスおよび次ホップを含むルーティング情報をルーティングテーブルへ登録する手順と、前記中継ノードが、前記送信元ノードから宛先ノード宛に送信されたパケットの次ホップを、その宛先アドレスおよび送信元アドレスに基づいて前記ルーティングテーブルから検索する手順とを含むことを特徴とする。
【０００７】
(2)本発明の重複アドレス検出方法はさらに、前記送信元ノードが、宛先シーケンス番号が既知の宛先へは当該宛先シーケンス番号を付与し、宛先シーケンス番号が未知の宛先へは所定の識別子を付与した経路要求メッセージを送信し、前記宛先ノードが、前記送信元ノードとの通信履歴が存在しないにもかかわらず前記経路要求メッセージに前記所定の識別子が付与されていないときに重複アドレスの存在を検出することを特徴とする。
【０００８】
(3)本発明の重複アドレス検出方法はさらに、前記重複アドレスの存在を検出した宛先ノードが、重複アドレス解消用のデータをネットワーク上に送信する手順を含むことを特徴とする。
【０００９】
(4)本発明の重複アドレス検出装置は、自ノードを宛先とする経路要求メッセージを解析し、その送信元アドレスに基づいて送信元ノードとの通信履歴の有無を判定する手段と、前記送信元ノードとの通信履歴が存在しないにもかかわらず前記経路要求メッセージに宛先シーケンス番号が登録されているときに重複アドレスの存在を検出する重複アドレス検出手段と、前記重複アドレスの存在を検出できないときに経路応答メッセージを返信する手段とを含むことを特徴とする。
【００１０】
(5)本発明の重複アドレス検出装置はさらに、前記重複アドレス検出手段が、前記送信元ノードとの通信履歴が存在しないにもかかわらず、前記経路要求メッセージに、宛先シーケンス番号が未知であることを示す所定の識別子が付与されていないときに重複アドレスの存在を検出することを特徴とする。
【００１１】
(6)本発明の重複アドレス検出装置はさらに、重複アドレス解消用のデータを送信する重複アドレス解消手段を含むことを特徴とする。
【００１２】
(7)本発明の重複アドレス検出装置はさらに、経路応答メッセージを受信し、宛先アドレス、送信元アドレスおよび次ホップを含むルーティング情報をルーティングテーブルへ登録する手段と、他ノード宛のパケットの次ホップを、その宛先アドレスおよび送信元アドレスに基づいて前記ルーティングテーブルから検索する手段と、前記他ノード宛のパケットを前記検索された次ホップへ転送する手段とを含むことを特徴とする。
【発明の効果】
【００１３】
本発明によれば、宛先ノードでは、ルーティングテーブルに通信履歴がなく、したがって初めて通信する送信元ノードからの経路要求メッセージに宛先シーケンス番号が登録されていれば、この宛先シーケンス番号は、アドレスが同一である他のノードに関するシーケンス番号であると判断できるので、自ノードのアドレスが同一ネットワーク内で重複して割り当てられていることを検出できる。
【００１４】
また、中継ノードでは、経路応答メッセージに基づいてルーティングテーブル情報をルーティングテーブルに登録する際、宛先アドレスと送信元アドレスとを対応付けて登録し、その後、パケットをルーティングする際には、その宛先アドレスと送信元アドレスとを抽出し、これをルーティングテーブルに登録されている各エントリで相互に対応付けられた宛先アドレスと送信元アドレスとの組み合わせと比較するので、アドレスが重複する一方のノード宛に送信されたパケットが他方のノードに誤って転送されることが防止される一方で、正規の宛先である一方のノードへは転送できるようになる。
【発明を実施するための最良の形態】
【００１５】
以下、図面を参照して本発明の好ましい実施の形態について詳細に説明する。図１は、本発明に係るネットワーク端末（無線ノード）の主要部の構成を示した機能ブロック図であり、ここでは、本発明の説明に不用な構成は図示を省略している。
【００１６】
ネットワークI/F１は、自ノードとアドホックネットワークとの通信を制御する。ルーティング制御部２は、受信したRREQを解析するRREQ解析部２０１、受信したRREPを解析するRREP解析部２０２、受信したRREQおよびRREPに基づいてルーティングテーブル３を更新するルーティングテーブル管理部２０３、ルーティングテーブル３に登録されているルーティング情報に基づいて受信パケットをルーティングするルーティング部２０４、RREQを生成するRREQ生成部２０５、およびRREPを生成するRREP生成部２０６等を含む。
【００１７】
重複アドレス検出部４は、自ノードを宛先とするRREQを受信した際に、その送信元ノードとの通信履歴の有無、および前記RREQに登録されている宛先シーケンス番号に基づいて重複アドレスの存在を検出する。重複アドレス解消部５は、前記重複アドレス検出部４により重複アドレスの存在が検出されると、これを解消するためのデータを対象ノードへ送信する。
【００１８】
図２は、前記ルーティングテーブル３の一例を示した図であり、本実施形態では、宛先ノードのIPアドレスごとに、従来から登録されていた次ホップのIPアドレスやシーケンス番号等に加えて、送信元ノードのIPアドレスが新たに登録される。
【００１９】
次いで、本実施形態による重複アドレスの検出手順について説明する。ここでは、図３に示したように、ノードＡとノードＤとがノードＢ，Ｃを中継して送信するアドホックネットワークと、ノードＥとノードＧとがノードＦを中継して送信するアドホックネットワークとが独立して確立されている状態から説明する。本実施形態では、ノードＡのIPアドレスが「１」であり、以下同様に、ノードＢ，Ｃ，Ｄ，Ｅ，Ｆ，ＧのIPアドレスが、それぞれ「２」、「３」、「４」、「５」、「６」、「４」である。したがって、ノードＤとノードＧとはIPアドレスが共に「４」であるが、図３のトポロジでは各アドホック網が独立しているので重複アドレスが生じていない。
【００２０】
ノードＥからノードＧへ初めて送信する場合、ノードＥは宛先アドレスがノードＧの「４」であって、宛先シーケンス番号が未知であることを示す「Ｕ」（Unknown sequence number）フラグの登録されたRREQを前記RREQ生成部２０５で生成し、これをブロードキャストする。
【００２１】
ノードＦでは、このRREQの受信に応答して図５のRREQ受信処理が起動され、ステップＳ１０では、前記RREQ解析部２０１において前記RREQが解析され、その宛先ノードが判別される。ここでは、宛先が自ノード以外の他ノードなのでステップＳ１１へ進む。ステップＳ１１では、図７(a)に示したように、ノードＦのルーティングテーブル３に、宛先アドレスがノードＥの「５」、送信元アドレスがノードＧの「４」、次ホップがノードＥの「５」であるエントリ１が登録される。ステップＳ１２では、前記受信したRREQがブロードキャストされる。
【００２２】
宛先のノードＧでも、このRREQの受信に応答して図５のRREQ受信処理が起動され、ステップＳ１０では宛先が自ノードと判別されてステップＳ１３へ進む。ステップＳ１３では、前記重複アドレス検知部４において、送信元であるノードＥからの初めての受信であるか否かが判定される。本実施形態では、ノードＥに関するエントリがルーティングテーブル３に登録されているか否かに基づいて、初めての受信であるか否かが判別される。ここでは初めての受信と判定されるのでステップＳ１４へ進む。ステップＳ１４では、前記RREQに登録されている宛先シーケンス番号がRREQ解析部２０１において参照される。ここでは、宛先シーケンス番号の代わりに「Ｕ」フラグがセットされているのでステップＳ１５へ進む。ステップＳ１５では、図８に示したように、ノードＧのルーティングテーブル３に、宛先アドレスがノードＥの「５」、送信元アドレスが自ノードの「４」、次ホップがノードＦの「６」であるエントリ１が登録される。ステップＳ１６では、宛先アドレスがノードＥの「５」であって、発信元シーケンス番号が自身のシーケンス番号Nseq-gであるRREPがRREP生成部２０６において生成され、ノードＦへ転送される。
【００２３】
ノードＦでは、このRREPの受信に応答して図６のRREP受信処理が起動され、ステップＳ３０では、前記RREP解析部２０２において宛先が判別される。ここでは宛先が自ノード以外なのでステップＳ３１へ進む。ステップＳ３１では、図７(b)に示したように、宛先アドレスがノードＧの「４」、次ホップがノードＧの「４」、送信元アドレスが今回の宛先であるノードＥの「５」であるエントリ２が、ノードＦのルーティングテーブル３に追加される。ステップＳ３２では、前記RREPがノードＥへ転送される。
【００２４】
ノードＥでも、このRREPの受信に応答して図６のRREP受信処理が起動され、ステップＳ３０において宛先が判別される。ここでは自ノード宛と判定されるのでステップＳ３３へ進み、受信したRREPに基づいて、ルーティングテーブル管理部２０３によってルーティングテーブル３が更新される。ステップＳ３４では、RREPに登録されていたシーケンス番号Nseq-gがノードＧの宛先シーケンス番号としてルーティングテーブル３に登録される。
【００２５】
その後、図３の状態からノードＢ，Ｆが移動して、図４に示したように２つのアドホック網が結合されると、ノードＥとノードＦとを結ぶリンクが切断されているので、ノードＥが再びノードＧと通信しようとする場合には改めてRREQがブロードキャストされる。
【００２６】
このRREQには、宛先シーケンス番号として前記RREPにより通知されたノードＧのシーケンス番号Nseq-gが登録され、それ以外は前記と同様にしてノードＢ，Ｆを中継してノードＧへ転送されると共に、IPアドレスが同一であるノードＤへも、ノードＢ，Ｆ，Ｃを中継して転送される。
【００２７】
ノードＧでは、このRREQの受信に応答して図５のRRPQ受信処理が起動され、ステップＳ１０では宛先が判別される。ここでは、宛先が自ノードと判定されてステップＳ１３へ進み、ノードＥからの初めての受信であるか否かが判定される。ここでは、ノードＥに関するエントリがルーティングテーブル３に既登録なので、ステップＳ１５へ進んでルーティングテーブル３が更新される。ステップＳ１６では、前記と同様にRREPが生成されてノードＦへ転送される。
【００２８】
一方、ノードＤでも、このRREQの受信に応答して図５のRRPQ受信処理が起動され、ステップＳ１０では宛先が判別される。ここでは、宛先が自ノードなのでステップＳ１３へ進み、ノードＥからの初めての受信であるか否かが判定される。ノードＤはノードＥから初めて受信するのでステップＳ１４へ進む。ステップＳ１４では、RREQに登録されている宛先シーケンス番号が参照される。本来であれば、初めての通信相手からのRREQには宛先シーケンス番号の代わりに「Ｕ」フラグがセットされているべきであるにもかかわらず、ここでは宛先シーケンス番号Nseq-gが登録されているので、前記重複アドレス検出部４により、同一アドレスのノードが他にも存在していると認識されてステップＳ１８へ進む。ステップＳ１８では、重複アドレス解消部５において、後述する重複アドレス処理が実行され、その後はRREPを返信することなく当該処理を終了する。
【００２９】
その後、前記ノードＧから返信されたRREPを受信したノードＥから、宛先アドレスが「４」のデータパケットを受信したノードＦは、自身のルーティングテーブルのエントリ２（図７）に基づいて、このデータパケットをノードＧへ転送できる。
【００３０】
一方、図４のネットワークトポロジにおいて、ノードＡからノードＤへ改めて送信する場合も、ノードＡからノードＤへRREQがブロードキャストされる。このRREQには、宛先シーケンス番号としてノードＤのシーケンス番号Nseq-dが登録され、それ以外は前記と同様にしてノードＢ，Ｆ，Ｃを中継してノードＤへ転送されると共に、IPアドレスが同一であるＧへも、ノードＢ，Ｆを中継して転送される。
【００３１】
ノードＤでは、このRREQの受信に応答して図５のRRPQ受信処理が起動され、ステップＳ１０では宛先が判別される。ここでは、宛先が自ノードと判定されてステップＳ１３へ進み、ノードＡからの初めての受信であるか否かが判定される。ここでは、ノードＡに関するエントリがルーティングテーブル３に既登録なので、ステップＳ１５へ進んでルーティングテーブル３が更新される。ステップＳ１６では、前記と同様にRREPが生成されてノードＦへ転送される。
【００３２】
一方、ノードＧでも、このRREQの受信に応答して図５のRRPQ受信処理が起動され、ステップＳ１０では宛先が判別される。ここでは、宛先が自ノードなのでステップＳ１３へ進み、ノードＡからの初めての受信であるか否かが判定される。ノードＤはノードＡから初めて受信するのでステップＳ１４へ進む。ステップＳ１４では、RREQに登録されている宛先シーケンス番号が参照される。本来であれば、初めての通信相手からのRREQには「Ｕ」フラグがセットされているべきであるにもかかわらず、ここでは宛先シーケンス番号Nseq-dが登録されているので、前記重複アドレス検出部４により、同一アドレスのノードが他にも存在していると認識されてステップＳ１８へ進む。ステップＳ１８では、重複アドレス解消部５において、後述する重複アドレス処理が実行され、その後はRREPを返信することなく当該処理を終了する。
【００３３】
ノードＦでは、前記ノードＡから転送されたRREPの受信に応答して図６のRREP受信処理が起動され、そのルーティングテーブルには、図７(d)に示したように、宛先アドレスがノードＤの「４」、次ホップがノードＣの「３」、送信元アドレスがノードＡの「１」であるエントリ４が追加登録される。
【００３４】
その後、ノードＦはノードＥからノードＧ宛に送信されたデータパケットを受信すると、その宛先アドレス「４」と送信元アドレス「５」に基づいて図７(b)のルーティングテーブルが参照され、前記ルーティング部２０４がエントリ２のルーティング情報に基づいて、当該パケットをIPアドレスが「４」のノードＧへ転送する。また、ノードＦはノードＡからノードＤ宛に送信されたデータパケットを受信すると、その宛先アドレス「４」と送信元アドレス「１」に基づいて図７(d)のルーティングテーブルを参照し、エントリ４のルーティング情報に基づいて、当該パケットをIPアドレスが「３」のノードＣへ転送する。
【００３５】
一方、重複アドレスを検出した前記宛先ノードＧでは、重複アドレス解消部５が、従来技術と同様にして、ネットワーク内で重複しない新しいアドレスを決定する。そして、新しいアドレスと重複していたアドレスとが対応付けられた重複解消メッセージを送信元ノード宛に送信する。このメッセージを受信した中継ノードは、受信したメッセージに基づいて、ルーティングテーブル３に登録されているルーティング情報を更新する。このメッセージを受信した送信元ノードでは、前記中継ノードと同様にルーティングテーブルを更新すると共に、送信しようとするパケットのIPヘッダの宛先アドレスを前記新しいアドレスに書き換える。
【図面の簡単な説明】
【００３６】
【図１】本発明に係るネットワーク端末の主要部の構成を示した機能ブロック図である。
【図２】ルーティングテーブルの一例を示した図である。
【図３】ネットワークトポロジの変更前の一例を示した図である。
【図４】ネットワークトポロジの変更後の一例を示した図である。
【図５】RREQ受信処理のフローチャートである。
【図６】RREP受信処理のフローチャートである。
【図７】ノードＦのルーティングテーブルを示した図である。
【図８】ノードＧのルーティングテーブルを示した図である。
【符号の説明】
【００３７】
１…ネットワークI/F，２…ルーティング制御部，３…ルーティングテーブル，４…重複アドレス検出部，５…重複アドレス解消部
【図１】
2005064848.tif 000003
【図２】
2005064848.tif 000004
【図３】
2005064848.tif 000005
【図４】
2005064848.tif 000006
【図５】
2005064848.tif 000007
【図６】
2005064848.tif 000008
【図７】
2005064848.tif 000009
【図８】
2005064848.tif 000010