アドホックネットワークにおけるルーティング方法
【課題】 スループットなどの通信品質の向上及び無線リソースの消費抑制が図られた、アドホックネットワークにおけるルーティング方法を提供すること。
【解決手段】 アドホックネットワークにおいて、ルートリクエストを送信又は転送するノードは、自局が外部の有線網(インターネット等)と通信接続している場合、該有線網における自局の識別子をルートリクエストに付加して送信又は転送する。ルートリクエストの宛先ノードは、受信したルートリクエストに2以上の上記有線網における識別子が含まれていた場合、これら2以上の識別子のうちルート上最も送信元ノードに近いノードを表す1つの識別子と最も宛先ノードに近いノードを表す1つの識別子とを用いて、これら2つの識別子が表すノード間は上記有線網を経由する経路を採用したルートリプライを作成する。
【解決手段】 アドホックネットワークにおいて、ルートリクエストを送信又は転送するノードは、自局が外部の有線網(インターネット等)と通信接続している場合、該有線網における自局の識別子をルートリクエストに付加して送信又は転送する。ルートリクエストの宛先ノードは、受信したルートリクエストに2以上の上記有線網における識別子が含まれていた場合、これら2以上の識別子のうちルート上最も送信元ノードに近いノードを表す1つの識別子と最も宛先ノードに近いノードを表す1つの識別子とを用いて、これら2つの識別子が表すノード間は上記有線網を経由する経路を採用したルートリプライを作成する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、概して、アドホックネットワークにおけるルーティング方法に係り、特に、スループットの向上及び無線リソースの消費抑制が図られたルーティング方法に関する。
【背景技術】
【0002】
従来、基地局や固定局を使わずに、端末間でホッピング(中継)することにより、データ伝送を可能とするアドホックネットワーク(或いは、マルチホップ無線ネットワーク、又は、Mobile Ad−hoc Network;MANET)が知られている。
【0003】
アドホックネットワークでは、すべての端末によって自律的にネットワークが構築されるため、基地局等の設置が不要となり、柔軟性が高く、設置の容易なネットワーク構築が可能となる。
【0004】
アドホックネットワークにおいて用いられるルーティングプロトコル(経路制御プロトコル)については、IETF(Internet Engineering Task Force)のMANETワーキンググループ(http://www.ietf.org/html.charters/manet−charter.html)から種々のものが提案・公開されており、標準化が進められている。
【0005】
現在、提案・公開されているルーティングプロトコルは、大きく分けるとリアクティブ(Reactive)型、プロアクティブ(Proactive)型、及び、これらのハイブリッド(複合)型、に分けられる。
【0006】
リアクティブ型のルーティングプロトコルは、実際にデータを送信する際に初めて起動し、周りにある通信可能な端末の電波を送受信して確かめてからルート構築を行うものであり、代表的なものとしては、「Adhoc On Demand Distance Vector(AODV)」(Experimental RFC 3561)や、「Dynamic Source Routing(DSR)」(Internet Draft;有効期限2005年1月19日)などが挙げられる。
【0007】
プロアクティブ型のルーティングプロトコルは、任意の時間間隔ごとにルーティング可能な端末を確かめており、常にルートが構築されていて通信可能状態となっているものであり、代表的なものとしては、「Optimized Link State Routing(OLSR)」(Experimental RFC 3626)や、「Topology Broadcast based on Reverse−Path Forwarding(TBRPF)」(Experimental RFC 3684)などが挙げられる。
【0008】
すなわち、リアクティブ型プロトコルではデータを送信する際にどの端末を通ってデータをリレーさせるのかが決定されるのに対し、プロアクティブ型プロトコルでは予め決定されているリレーの順番に従ってデータが送信される。前者は各端末における電池効率の点で有利であり、後者は通信タイムアウトや送信データロスが少ないという利点を有する。
【0009】
また、このような標準化への取り組みとは別に、アドホックネットワークにおける独自のパケットルーティング方法も提案されている(例えば、特許文献1参照)。
【0010】
さらに、アドホックネットワークとインターネットなどの有線インフラを組み合わせて利用する際のルーティング等に関する技術も提案されている(例えば、特許文献2〜4参照)。
【特許文献1】特開平11−239176号公報
【特許文献2】特開2002−354016号公報
【特許文献3】特開2003−230167号公報
【特許文献4】特開2004−248180号公報
【発明の開示】
【発明が解決しようとする課題】
【0011】
周知の通り、アドホックネットワークでは、ホップ数が増えるほど、すなわち経由する端末(ノード)が増えるほど、通信品質は劣化する傾向となる。
【0012】
本願発明者らは、アドホックネットワークにおいて、あるルートの中継局となっているアドホック通信端末の中に例えば無線LANなどを利用して例えばインターネットなどの有線網に接続可能なものが2つ以上存在する場合、ルートの一部を有線網経由の経路に置き換えることによって、通信品質を大幅に改善できることに着目した。
【0013】
この点、上述のIETF−MANET−WGにより提案・公開されている種々のルーティングプロトコル及び上記特許文献1記載のルーティング方法はいずれも、アドホックネットワーク内に閉じたルーティングを行うものであり、アドホックネットワークと同時にインターネットなどの有線網を利用することへ拡張されていない。
【0014】
また、上記特許文献2記載の方法は、インターネットに接続されたノードがアドホックネットワーク内に入ったときにインターネット経由でルーティングしないようにするためのものであり、アドホックネットワークと同時にインターネットなどの有線網を利用するものではない。
【0015】
また、上記特許文献3記載の方法は、アドホックネットワークを介してインターネットへ接続する通信において、インターネットへの接続先として関門(ゲートウェイ)となる端末を探索するものであるが、アドホック通信端末同士のルートの一部にインターネットを利用するものではない。また、この従来方法に従ってアドホック端末同士を接続した場合、必ずインターネットを経由した通信経路となり、端末同士が近接している場合であってもアドホック通信ができなくなってしまう。
【0016】
さらに、上記特許文献4記載の方法は、複数の無線通信メディアの中から通信状況に応じていずれかを選択するものであるが、選択されるのはルート全体に利用される通信メディアであって、アドホックネットワークにおいてルートの一部をインターネットなどの有線網経由の経路に置き換えるものではない。
【0017】
このように、従来提案されているアドホックネットワークにおけるルーティング方法では、アドホックネットワークにおいて、あるルートの中継局となっているアドホック通信端末の中に有線網と接続可能なものが2つ以上あったとしても、ルートの一部を有線網経由の経路で置き変えたルーティングを実現させることはできない。
【0018】
仮に、例えばIETF−MANET−WGにおいて提案・公開されているルーティングプロトコルをそのまま用いて、有線網を経由したルートまで含めたルート探索を行おうとすれば、ブロードキャストされたルートリクエスト(RREQ)を受信した端末が有線網と接続している場合、RREQがアドホックネットワーク内だけでなく有線網内にもブロードキャストで転送されるといった構成になりかねない。そのような事態は、有線網の通信トラフィックに甚大な被害を与えかねず、実施不可能である。
【0019】
本発明はこのような課題を解決するためのものであり、アドホックネットワークにおいて、アドホックネットワーク内に閉じたパケット伝送のみによって、アドホックネットワーク内に閉じたルートだけでなく、ルートの一部を有線網経由の経路で置き換えたルートをも探索可能とすることによって、従来方法に比してスループットを向上させ、無線リソースの消費を抑制することが可能なルーティング方法を提供することを主たる目的とする。
【課題を解決するための手段】
【0020】
上記目的を達成するための本発明の第一の態様は、アドホックネットワーク(MANET)におけるルーティング方法であって、ルートリクエスト(RREQ)を送信又は転送するノードは、自局が外部の有線網と通信接続している場合、該有線網における自局の識別子を上記ルートリクエストに付加して送信又は転送する、アドホックネットワークにおけるルーティング方法である。
【0021】
この第一の態様において、上記外部の有線網とは例えばインターネットなどである。その場合、アドホック通信端末(ノード)が、例えば無線LAN機能を備え、例えばホットスポット(hotspot)エリア内に在圏するとき、そのノードはアドホックネットワーク内に閉じたアドホック通信もインターネットを経由した通信も可能となる。
【0022】
この第一の態様によれば、ルートリクエストを受信した宛先ノード(送信先ノード)は、経路中に有線網に接続しているノードが存在するか否か及び存在する場合何台存在するのかを知ることができる。
【0023】
また、このルートリクエストの送信・転送は、アドホックネットワーク内に閉じて行われるものであり、ルートリクエストの宛先ノードは、上記有線網で何らパケット伝送を行うことなく、すなわち該有線網上の通信トラフィックに影響を与えることなく、該有線網を利用する場合の各ノードの識別子を取得することができる。
【0024】
上記目的を達成するための本発明の第二の態様は、上記第一の態様において、上記ルートリクエストの宛先ノードは、受信したルートリクエストに2以上の上記有線網における識別子が含まれていた場合、これら2以上の識別子のうちルート上最も送信元ノードに近いノードを表す1つの識別子と最も宛先ノードに近いノードを表す1つの識別子とを用いて、これら2つの識別子が表すノード間は上記有線網を経由する経路を採用したルートリプライ(RREP)を作成する、アドホックネットワークにおけるルーティング方法である。
【0025】
この第二の態様によれば、アドホック通信経路の一部がアドホックネットワークにおける無線リンクよりも良好な通信品質が見込める有線網を経由した経路で置き換えられるため、アドホックネットワーク内のみを通る経路を採用した場合に比して通信品質が向上する。
【0026】
上記目的を達成するための本発明の第三の態様は、上記第二の態様において、上記ルートリクエストの宛先ノードは、アドホックネットワーク内のみでルーティングした場合に上記2つの識別子が表すノード間に所定数(例えば2ホップ)以上のホップ数が存在する場合のみ、これら2つの識別子が表すノード間は上記有線網を経由する経路を採用したルートリプライを作成する、アドホックネットワークにおけるルーティング方法である。
【0027】
この第三の態様によれば、近接した(例えばホップ数が1の距離にある)ノード間の無線リンクが有線網に置き換えられてしまうことが防止されるため、ホップ数削減の効果が十分に得られる場合のみ、有線網が利用されるようにすることができる。
【0028】
上記目的を達成するための本発明の第四の態様は、上記第三の態様において、ルートリクエストの宛先ノードは、最初のルートリクエストを受信してから所定期間、他の経路を経由した同じ送信元ノードからのルートリクエストの受信を待機し、上記所定期間内に同じ送信元ノードから1以上のルートリクエストが受信された場合、上記最初のルートリクエスト及び前記所定期間中に受信されたルートリクエストのうち2以上の上記有線網における識別子が含まれているルートリクエストについてはこれら2つの識別子が表すノード間は上記有線網を経由するものとして、各ルートリクエストの経路のホップ数を比較し、最もホップ数が少ない経路を有するルートリクエストに対してルートリプライを作成する、アドホックネットワークにおけるルーティング方法である。
【0029】
従来、最初に宛先ノードによって受信されたルートリクエスト以外の遅延して到着したルートリクエストは冗長な経路を通っているものと判断されて破棄されていたが、この第四の態様によれば、アドホックネットワーク内に閉じたルートでは最小ホップ数でなかったルートが上記第三の態様のように経路の一部を有線網でショートカットすることによって最小ホップ数のルートとなる可能性があることに鑑み、遅延して宛先ノードに到着したルートリクエストであってもRREP返信候補に取り上げることによって、有線網を利用して通信品質を向上させる機会を増やすことができる。
【0030】
上記目的を達成するための本発明の第五の態様は、上記第四の態様において、ルートリクエストの宛先ノードは、2以上の上記有線網における識別子が含まれているルートリクエストが受信されたときに上記他の経路を経由した同じ送信元ノードからのルートリクエストの受信の待機を終了する、アドホックネットワークにおけるルーティング方法である。
【0031】
この第五の態様によれば、経路の一部を有線網を経由する経路に置き換えることによるショートカットが可能なルートを示すルートリクエストが1つでも受信された段階で、当該ルートリクエストを選択することによってホップ数の削減が見込めると判断し、上記所定待機時間を速やかに終了させるため、ルートリプライをより迅速に作成することができる。
【0032】
上記目的を達成するための本発明の第六の態様は、上記第四又は第五の態様において、受信したルートリクエストを転送するノードは、受信したルートリクエストに上記有線網における識別子が含まれている場合、その受信したルートリクエストが既に転送済みのルートリクエストであっても破棄せずに初めて受信したルートリクエストと同様に転送する、アドホックネットワークにおけるルーティング方法である。
【0033】
従来、既に転送済みのルートリクエストを受信したノードはそのルートリクエストを破棄していたが、この第六の態様によれば、アドホックネットワーク内に閉じたルートでは最小ホップ数でなかったルートが上記第三の態様のように経路の一部を有線網でショートカットすることによって最小ホップ数のルートとなる可能性があることに鑑み、既に転送済みのルートリクエストであっても有線網における識別子を含み、有線網を利用したショートカットが実現される可能性があるルートリクエストについては破棄せずに再度転送することによって、有線網を利用して通信品質を向上させる機会を増やすことができる。
【0034】
上記目的を達成するための本発明の第七の態様は、上記第四乃至第六の態様のいずれかにおいて、各ノードは、自局周辺の上記有線網と通信接続しているノードを探索し、存在する場合、ルートリクエストを送信又は転送する際に自局からその自局周辺の上記有線網と通信接続しているノードまでのホップ数を該ルートリクエストに付加する、ことを特徴とするアドホックネットワークにおけるルーティング方法である。
【0035】
この第七の態様によれば、このようなルートリクエストを受信した宛先ノードは、ルートリクエストが転送されてきた経路中に有線網へ接続しているノードがない場合であっても、有線網へ接続可能なノードまでのホップ数を知ることができるため、有線網を経由した場合のホップ数を知ることができる。よって、アドホックネットワーク内では冗長なルートも含めて、有線網によるショートカットを利用した場合に最もホップ数が少なくなるルートを探索することができる。
【0036】
なお、ここでは、ルーティング判定の指標としてホップ数を例に挙げたが、当業者には明らかなようにこれは一例に過ぎず、例えば通信帯域や遅延時間などの通信品質に関連する指標などの他の指標を用いてルーティングの判定を行うことも可能である。
【発明の効果】
【0037】
本発明によれば、アドホックネットワークにおいて、経路の一部を積極的に有線網経由の経路に置き換えることによってホップ数の削減を図ることができるため、スループットなどの通信品質の向上及び無線リソースの消費抑制が図られたルーティング方法を提供することができる。
【発明を実施するための最良の形態】
【0038】
以下、本発明を実施するための最良の形態について、添付図面を参照しながら実施例を挙げて説明する。なお、アドホックネットワークの基本概念については当業者には既知であるため、詳しい説明を省略する。
【実施例1】
【0039】
まず、図1〜9を用いて、本発明の一実施例(実施例1)に係るルーティング方法について説明する。本実施例では、ルーティングプロトコルとしてDSRが用いられることを前提し、図1に示すようなアドホック通信端末が点在する通信環境において、送信端末が受信端末へデータを送信するために経路探索(ルートディスカバリー)を実行する場合を考える。
【0040】
また、本実施例において、各通信端末は、アドホック通信が可能であると共に、ホットスポットエリア内にいるときには無線LANを利用してインターネットに接続する能力を有するものとする。図1に例示した通信環境では、端末B及びCがホットスポット(HS)1内に位置し、端末G及びJがホットスポット(HS)2内に位置し、端末I、K、及びMがホットスポット(HS)3内に位置している。
【0041】
本実施例は、これらインターネットに接続した端末を利用して、アドホックネットワーク内に閉じたルーティング処理によって、インターネットを経由する経路も考慮した経路探索を可能にする。
【0042】
図2は、各アドホック通信端末の概略構成を示す。
【0043】
端末200は、無線機である送受信部201と、受信したパケットを転送するか否かを判断するパケット転送部202とを有する。
【0044】
また、端末200は、ルーティングのための経路表(ルーティングテーブル)203を有する。ルーティングテーブルは、各端末に記憶されており、宛先とその宛先へパケットを届けるために送り出す転送先の組(ペア)を表にした参照テーブルである。パケット転送部202は、自局宛でないパケットを受信したとき、ルーティングテーブル203を参照して、宛先に適したノードへ転送する。
【0045】
また、端末200は、ルートリクエスト(RREQ)及びルートリプライ(RREP)を処理するルーティング用パケット処理部204と、各端末(ノード)の識別子(アドレス)を格納したアドレス格納部205とを有する。
【0046】
本実施例は、現行のDSRプロトコルを拡張するものであり、以下に特段の説明がない点については通常のDSRプロトコルに準拠して処理される。
【0047】
本実施例において追加・拡張された主たる点は、ルーティング用パケット処理部204の機能である。現行のDSRプロトコルによれば、ルーティング用パケット処理部204は、RREQを中継する際、受信されたRREQに自局のアドホックネットワーク内での識別子(MANET内端末識別子)を追記してパケット転送部202へ渡し、パケット転送部202がこれを転送する。
【0048】
本実施例において、ルーティング用パケット処理部204は、更に、無線LAN通信機能を備え、ホットスポットのアクセスポイント(AP)が送出しているビーコンを検出し、自局がホットスポットエリア内に位置するか否かを判断する。そして、自局がホットスポットエリア内に位置すると判断した場合、上記MANET内端末識別子に加えて、インターネット上における自局の識別子(グローバル通信用識別子)をRREQに追記する。グローバル通信用識別子が追記されたRREQは、通常のRREQと同様、アドホックネットワーク内だけでフラッディングされ、インターネット上へは送出されない。
【0049】
追記される情報を図3に示す。図3(a)は、端末がホットスポットエリア内に位置する場合に中継するRREQに追記される自局情報であり、図3(b)は、端末がホットスポットエリア内に位置しない場合に中継するRREQに追記される自局情報である。
【0050】
ここで、MANET内端末識別子は、例えば、MACアドレスやIPアドレスなどであり、グローバル通信用識別子は、例えば、IPアドレスである。MANET内端末識別子とグローバル通信用識別子とは、例えば、識別子(アドレス)の割り当て空間を別にする、或いは、専用のフラグ(1ビット)を設け、グローバル通信用識別子が追記された場合にはこのフラグを立てる、などにより区別することができる。
【0051】
このように、本実施例に係る拡張によれば、経路探索時に、中継ノードがホットスポットエリア内にいれば、RREQに追記される情報が増えるが、これは経路探索時のみであり、ルート確立後のデータ送信では特段の追加的情報が付加されない。
【0052】
RREQの中継に関して、その他の点は現行のDSRに準拠する。すなわち、送信端末からブロードキャストされたRREQは、周囲の端末によって受信される。各端末は、受信したRREQの宛先が自局でなければ、上述のような自局情報を追記した上で、RREQをブロードキャストする。このような転送・中継が繰り返され、最終的に受信端末に到達する。
【0053】
また、ある端末から転送されたRREQが転送先ノードによる転送によって再度戻ってきて最初の端末により受信される場合が当然生じるが、「RREQに記述された経路情報に自局が含まれている場合、そのRREQは破棄する」というDSRプロトコルのルールによって、そのRREQは処理済みとして破棄される。
【0054】
図4は、図1に例示した通信環境において、RREQが送信端末から受信端末へ到達した際に経由した経路の一例を示している。
【0055】
RREQがこのようなルートを通った場合、現行のDSRプロトコルによれば、受信端末により受信されたRREQには図5に示すような経路情報が記述されている。この経路情報から、このRREQは、送信端末から、端末B、端末C、端末F、端末I、端末K、及び、端末Mを順に経由して受信端末に届いたことがわかる。
【0056】
一方、本実施例によれば、上述のようにDSRプロトコルが拡張されているため、受信端末により受信されたRREQには図6に示すような経路情報が記述されていることになる。図示するように、ホットスポットエリア内に位置する端末B、端末C、端末I、端末K、及び端末Mに関しては、MANET内端末識別子だけでなく、グローバル通信用識別子も記述されている。
【0057】
RREQは様々な経路でそのRREQの宛先ノードである受信端末に到達するが、受信端末は、最初に到達したRREQが最もホップ数が少ない最短のルートを経由していると判断して、その最初に受信したRREQに基づいてRREPを作成し、送信端末にユニキャスト送信する。現行のDSRプロトコルによれば、図5に示したようなRREQを最初に受信した受信端末はこの経路を選択し、この経路情報を記述されたRREPを作成して送信端末にユニキャストする。このRREPは、図5のRREQに記述された経路を逆にたどって転送されながら送信端末に到達する。
【0058】
一方、本実施例に係るルーティング方法によれば、図6に示すようなRREQを最初に受信した受信端末(=RREQの宛先ノード)は、グローバル通信用識別子が記述された端末の中で最も送信端末に近いもの(ここでは端末B)と最も受信端末に近いもの(ここでは端末M)とをそれぞれ抽出し、それらのグローバル通信用識別子を利用してそれらノード間はインターネットを経由する経路を通るRREPを作成する。
【0059】
図6に示すRREQの場合、受信端末で作成されるRREPは図7のようになる。この図7に示すRREPは、送信端末〜端末B間はアドホックネットワークを経由し、端末B〜端末M間はインターネットを経由し、更に、端末M〜受信端末間はアドホックネットワークを経由した経路が選択されたことを意味する。
【0060】
この本実施例に係るRREPも、現行プロトコルと同様、記述された経路を逆にたどって送信端末にユニキャストされる。したがって、端末Mから端末Bへの転送にはインターネットが利用される。このRREPの転送はブロードキャストであるRREQとは異なりユニキャストであるため、インターネットを経由しても負荷は問題とならない。
【0061】
このように、本実施例によれば、インターネットはアドホックネットワークの無線リンクに比して十分に太く、通信品質が良いという洞察を前提として、アドホックネットワークにおいて探索・確立されるルートの一部をインターネットを経由したルートとすることができる。
【0062】
また、インターネットを経由することにより、いくつかの中継ノードがショートカットされるため、ルート全体でのホップ数の削減も見込める。図8は、現行のDSRプロトコルにより確立されるルートと本実施例により確立されるルートとを比較するものであり、図8(a)は図5に示したRREQ及びRREP経路情報を示し、図8(b)は図7に示したRREP経路情報を示す。図示するように、端末B〜端末M間をインターネットを経由したルートとすることによって、この場合、ホップ数が2ホップ短縮される。
【0063】
以上のような本実施例に係るルーティング方法について、図9を用いてより詳細に説明する。図9は、本実施例において各端末において行われる受信したRREQに対する処理の流れを示すフローチャートである。
【0064】
まず、各端末はRREQの受信を待機する(S901)。
【0065】
RREQが受信されると(S901の「YES」)、受信したRREQに記述された経路情報に自局の情報が含まれているか否かを判断する(S902)。含まれている場合(S902の「YES」)、処理済みのRREQであるものと判断して、そのRREQを破棄する(S912)。
【0066】
受信したRREQの経路情報に自局が含まれていない場合(S902の「NO」)、次いで、そのRREQの宛先ノードが自局であるか否かが判断される(S903)。自局が宛先ノードでない場合、S904〜S907の転送処理が実行され、自局が宛先ノードの場合、S908〜S911のRREP作成・送信処理が実行される。
【0067】
まず、自局が宛先ノードでない場合(S903の「NO」)、従来通り、RREQに自局のMANET内端末識別子を追記する(S904)。そして、更に、自局がホットスポットエリア内にいるか否か、換言すれば無線LANを利用してインターネットに接続している状態であるか否か、について判断し(S905)、ホットスポット内にいる場合(S905の「YES」)、上述のように受信したRREQに更に自局のグローバル通信用識別子も追記する(S906)。ホットスポット内にいない場合(S905の「NO」)、S906の処理はスキップされ、グローバル通信用識別子はRREQに記述されない。
【0068】
このように自局情報が追記されると、追記後のRREQを周囲の端末へフラッディングする(S907)。これで1回の中継処理が終了し、S901へ戻る。
【0069】
一方、自局が宛先ノードである場合(S903の「YES」)、受信したRREQに基づいてRREPを作成し、送信端末へ返信するために、まず、RREQが転送されてきたルートの一部をインターネット経由の経路で置き換えるか否かが判断される(S908)。
【0070】
S908において、「Rreq」は、受信されたRREQ内に記述されていた経路を表し、「H(R)」は、ルートR上で最も送信端末寄りでホットスポット内にいる端末から最も受信端末寄りでホットスポット内にいる端末までの経路を抽出したものを表し、「Hop(R)」は、ルートRのホップ数を表す。
【0071】
なお、H(R)は、ルートR上にホットスポット内に位置する端末が2つ以上存在しない場合、空(=0)とする。また、例えば、ルートR=送信者→A*→B*→C→D→E*→F→受信者であった場合(「*」はホットスポット内)、H(R)=A*→B*→C→D→E*となる。
【0072】
すなわち、S908においては、受信端末により受信されたRREQに記述された経路のうち最も送信端末寄りでホットスポット内にいる端末から最も受信端末寄りでホットスポット内にいる端末までの経路のホップ数が所定の閾値以上であるか否かが判定されている。
【0073】
ここでは、通信品質向上のためなるべくインターネットを経由したいが、しかしながら、端末〜AP間も無線通信の1ホップとカウントされるため、インターネットへのゲートウェイとなるホットスポットエリア内に在圏した2つの端末がアドホックネットワーク上で近接した位置関係にある場合(例えば、ホップ数=1の距離にある場合など)にまでわざわざインターネットを経由させる必要はないとの洞察から、上記所定の閾値は例えば「2ホップ」などに設定される。
【0074】
換言すれば、本実施例では、所定数以上のホップ数が削減される場合のみ、ルートの一部をインターネットを経由した経路に置き換える。
【0075】
このようなS908における判定処理において、削減されるホップ数が所定の閾値以上であると判断された場合(S908の「YES」)、図6に示したRREQから図7に示したRREPを作るように、受信したRREQからインターネットを経由した経路を採用したRREPが作成される(S909)。一方、S908における判定処理において、削減されるホップ数が所定の閾値未満であると判断された場合(S908の「NO」)、図5に示すように、現行のDSRプロトコルに従って受信されたRREQに記述されたのと同じ経路情報が記述されたRREPが作成される(S910)。
【0076】
上述のS908についての説明から明らかなように、受信したRREQに記述された経路情報に含まれる端末の中に含まれるホットスポット内にいる端末の数が2未満であってインターネットによるショートカットが物理的に実現できない場合にも、S908における判定は「NO」となり、従来通り、アドホックネットワークに閉じた経路を示すRREPが作成される。
【0077】
そして、このようにして作成されたRREPは送信端末へ向けてユニキャストで返信される(S911)。これで1回の経路探索処理が終了し、S901へ戻る。
【0078】
このように、本実施例によれば、アドホックネットワーク内でRREQが転送されるというMANET内に閉じたルーティング処理でありながら、インターネットに接続している中継ノードは上述のようなグローバル通信用識別子もRREQに付加して転送するという特徴を備えたことにより、インターネット上に経路要求を流さずにインターネットを経由したルートも考慮した経路探索が可能となる。
【0079】
従来、アドホックネットワーク上での経路探索にはアドホックネットワーク上で経路要求する必要があり、インターネット上での経路探索にはインターネット上で経路要求する必要があったことと比較すれば、本実施例の有益性は明らかである。
【0080】
なお、本実施例においては、RREQを受信した受信端末がインターネットを経由するRREPを作成するか否かを判断する(図9のS908)際に、受信したRREQに記述された経路となった端末の中で最も送信端末寄りのホットスポット内の端末と最も受信端末寄りのホットスポット内の端末とをインターネットへのゲートウェイとして利用するものとした。また、インターネットを経由することにより削減されるホップ数が所定の閾値以上であれば必ずインターネットを経由するルートが選択されるものとした。
【0081】
この点、理論上は、最も送信端末寄りでないホットスポット内の端末を利用することも、最も受信端末寄りでないホットスポット内の端末を利用することも可能であり、さらに、削減されるホップ数が所定の閾値以上の場合であってもあえて現行通りアドホックネットワーク内に閉じたルーティングを行うことも可能である。
【0082】
しかしながら、当業者には既知のように、アドホックネットワークではホップ数が増えるほど通信品質は劣化するため、できる限りアドホックネットワーク内での無線リンクを減らして、インターネットを経由したルートを通った方が通信品質は良好となる。
【0083】
したがって、上記実施例のようにできる限りインターネットを経由させようとすることは、好ましい実施形態であると言える。
【実施例2】
【0084】
次に、図10〜14を用いて、本発明の別の一実施例(実施例2)に係るルーティング方法について説明する。本実施例では、ルーティングプロトコルとしてAODVが用いられることを前提し、上記実施例1と同様に図1に示すようなアドホック通信端末が点在する通信環境において、送信端末が受信端末へデータを送信するために経路探索(ルートディスカバリー)を実行する場合を考える。
【0085】
また、本実施例においても、上記実施例1と同様に、各通信端末は、アドホック通信が可能であると共に、ホットスポットエリア内にいるときには無線LANを利用してインターネットに接続する能力を有するものとする。端末の概略構成は図2に示したのと同様であり、重複する説明は省略する。
【0086】
本実施例によっても、インターネットに接続した端末を利用して、アドホックネットワーク内に閉じたルーティング処理によって、インターネットを経由する経路も考慮した経路探索が可能となる。
【0087】
このように、本実施例は、ルーティングプロトコルとしてAODVを採用している点が異なる以外、基本的特徴は上記実施例1と同じであるため、重複する説明は省略する。したがって、以下の本実施例の説明は、主として、DSRとAODVの違いにより生じる適用方法の違いについての説明である。
【0088】
本実施例においても、RREQを受信した各通信端末は、自局がホットスポットエリア内に位置すると判断した場合、インターネット上における自局の識別子(グローバル通信用識別子)をRREQに追記した上で転送する。本実施例においても、グローバル通信用識別子が追記されたRREQは、通常のRREQと同様、アドホックネットワーク内だけでフラッディングされ、インターネット上へは送出されない。
【0089】
本実施例により拡張されたAODVプロトコルにおけるRREQのパケット構造を図10に示す。図示すように、本実施例に係るRREQは、上段部分が、フラグHを除き、現行のAODVプロトコルに準拠した構造であり、下段部分が拡張された追加部分となっている。
【0090】
上段の「タイプ」フィールドは、メッセージの種類を示すためのものであり、RREQの場合は「1」が入る。「ホップ数」フィールドは、送信元ノードから何回転送されたかを表すフィールドであり、送信端末から送信されるときには0である。
【0091】
本実施例の拡張により追加されたフラグHは、経路中にホットスポットエリア内に位置する端末が存在し、RREQにその端末のグローバル通信用識別子が記述された場合に立てられる。
【0092】
下段の追加部分には、ホットスポットエリア内に位置する端末によって追記されたグローバル通信用識別子と、送信端末からその端末までのホップ数とが記述される。AODVプロトコルでは、ソースルーティングであるDSRプロトコルと異なり、RREQ内にすべての経路が記述されず、各端末は自局が保持するルーティングテーブルに従って転送を行う。したがって、RREQを中継する各端末はRREQに自局のMANET内端末識別子は書き込まず、本実施例による拡張によりグローバル通信用識別子のみが追記される。
【0093】
図1に例示した通信環境において図4に示したようなルートで本実施例に係るRREQが転送された場合に受信端末が受信するRREQを図11に示す。図4の例では、経路上の端末B、端末C、端末I、端末K、及び端末Mがホットスポットエリア内に位置するため、RREQ下段に追加された拡張部分にこれら端末のグローバル通信用識別子及び送信端末からのホップ数が記述されている。ここで、ホップ数=3の端末F(図4)は、ホットスポットエリア内に位置しないため、RREQ内に記述がない。
【0094】
このように、本実施例に係る拡張によれば、経路探索時に、中継ノードがホットスポットエリア内にいれば、RREQに追記される情報が増えるが、これは経路探索時のみであり、ルート確立後のデータ送信では特段の追加的情報が付加されない。
【0095】
RREQの中継に関して、その他の点は現行のAODVプロトコルに準拠する。すなわち、送信端末からブロードキャストされたRREQは、周囲の端末によって受信される。各端末は、受信したRREQの宛先が自局でなければ、上述のような自局情報を追記した上で、RREQをブロードキャストする。このような転送・中継が繰り返され、最終的に受信端末に到達する。
【0096】
このように、本実施例によれば、上述のようにAODVプロトコルが拡張されているため、受信端末は、受信されたRREQから、経路上の端末B、端末C、端末I、端末K、及び端末Mがホットスポットエリア内に位置することを知ることができると共に、それらのグローバル通信用識別子も取得することができる。
【0097】
AODVプロトコルにおいても、RREQは様々な経路でそのRREQの宛先ノードである受信端末に到達し、受信端末は、最初に到達したRREQが最もホップ数が少ない最短のルートを経由していると判断して、その最初に受信したRREQに基づいてルートリプライ(RREP)を作成し、送信端末にユニキャスト送信する。
【0098】
本実施例において、RREQの宛先ノードである受信端末は、最初に受信したRREQの中に記述されたグローバル通信用識別子の数が1以下であった場合、経路の一部をインターネット経由にすることはできないと判断して、現行通り、アドホックネットワーク内に閉じたRREPを作成し、送信端末へ返信する。
【0099】
一方、受信したRREQに2以上のグローバル通信用識別子が含まれていた場合、受信端末は、それら記述されているグローバル通信用識別子の中から、経路上最も送信端末寄りの端末のものと最も受信端末寄りのものとを抽出し、RREPに記述する。
【0100】
本実施例に従って作成されたRREPのフォーマット例を図12に示す。上段の「タイプ」フィールドは、RREPの場合「2」が入る。「ホップ数」フィールドは、宛先ノードから何回転送されたかを表すフィールドであり、受信端末からユニキャスト送信される際には0である。
【0101】
下段の追加部分には、RREQに記述されていたグローバル通信用識別子の中から経路上最も宛先ノードに近いものが「グローバル通信用識別子1」フィールドに記述され、最も送信元ノードに近いものが「グローバル通信用識別子2」フィールドに記述される。
【0102】
図11に例示したRREQを受信した受信端末が返信するRREPを図13に示す。ここでは、「グローバル通信用識別子1」フィールドに端末Mのグローバル通信用識別子が記述され、「グローバル通信用識別子2」フィールドに端末Bのグローバル通信用識別子が記述される。
【0103】
このように作成された本実施例に係るRREPは、現行プロトコルと同様、送信端末にユニキャストされる。ただし、本実施例においては、現行のAODVプロトコルの拡張として、RREPを中継する各端末は、受信したRREPの「グローバル通信用識別子1」フィールドに自局のグローバル通信用識別子が記述されていた場合、自局が保持するアドホックネットワーク用のルーティングテーブルには従わず、そのRREPをインターネット経由で「グローバル通信用識別子2」フィールドに記述されたグローバル通信用識別子(アドレス)宛に送信する。そして、受信したRREPに記述されたホップ数を1インクリメントした値と宛先ノードと関連付けて新たにルーティングテーブルに記憶する。これにより、その中継ノードは、その宛先ノードまで何ホップであるかを自局内のルーティングテーブルに記憶することができる。
【0104】
インターネット経由でRREPを受信した端末は、現行通り、自局が保持するルーティングテーブルに従ってそのRREPをアドホックネットワーク内で送信する。
【0105】
このようにして、RREPの返信には、上記実施例1と同様に、インターネットが利用される。このRREPの転送はブロードキャストであるRREQとは異なりユニキャストであるため、インターネットを経由しても負荷は問題とならない。
【0106】
このように、本実施例によっても、アドホックネットワークにおいて探索・確立されるルートの一部をインターネットを経由したルートとすることができ、図8に示したようなホップ数削減が見込まれる。
【0107】
以上のような本実施例に係るルーティング方法について、図14を用いてより詳細に説明する。図14は、本実施例において各端末において行われる受信したRREQに対する処理の流れを示すフローチャートである。
【0108】
まず、各端末はRREQの受信を待機する(S1401)。
【0109】
RREQが受信されると(S1401の「YES」)、例えば「RREQ ID」フィールドの記述から処理済みのRREQであるか否かを判断する(S1402)。処理済みの場合(S1402の「YES」)、そのRREQを破棄する(S1412)。
【0110】
受信したRREQが処理済みではない場合(S1402の「NO」)、次いで、そのRREQの宛先ノードが自局であるか否かが判断される(S1403)。自局が宛先ノードでない場合、S1404〜S1406の転送処理が実行され、自局が宛先ノードの場合、S1407〜S1411のRREP作成・送信処理が実行される。
【0111】
まず、自局が宛先ノードでない場合(S1403の「NO」)、自局がホットスポットエリア内にいるか否か、換言すれば無線LANを利用してインターネットに接続している状態であるか否か、について判断し(S1404)、ホットスポット内にいる場合(S1404の「YES」)、上述のように受信したRREQに自局のグローバル通信用識別子と送信端末からのホップ数とを追記する(S1405)。ホットスポット内にいない場合(S1404の「NO」)、S1405の処理はスキップされ、グローバル通信用識別子はRREQに記述されない。
【0112】
次いで、RREQは周囲の端末へフラッディングされる(S1406)。これで1回の中継処理が終了し、S1401へ戻る。
【0113】
一方、自局が宛先ノードである場合(S1403の「YES」)、受信したRREQに基づいてRREPを作成し、送信端末へ返信するために、まず、RREQが転送されてきたルートの一部をインターネット経由の経路に置き換えることが可能な否かが判断される(S1407)。具体的には、受信されたRREQにグローバル通信用識別子が2以上記述されているか否かが判断される。
【0114】
S1407において、「Rhot」は、受信されたRREQ内に記述されていたホットスポットエリア内にいるノードのリストを表し、「Num(Rhot)」は、リストRhot内に記述されているノードの数を表す。
【0115】
S1407において、受信されたRREQにグローバル通信用識別子が2以上記述されているか否かが判断されると(S1407の「YES」)、次いで、RREQが転送されてきたルートの一部をインターネット経由の経路で置き換えるか否かが判断される(S1408)。
【0116】
S1408において、「Sub(Rhot)」は、リストRhot内に記述されている端末のうち最も送信元ノード寄りのものと最も宛先ノード寄りのものとの間のアドホックネットワーク上でのホップ数を表す。これは、図11から明らかなように、RREQ下段の拡張部分に記述されたホップ数の中で最も大きいものから最も小さいものを引いた差に等しいため、本実施例に係る拡張されたAODVプロトコルによれば容易に算出される。
【0117】
こうして、S1408においては、受信端末により受信されたRREQが経由した経路において最も送信端末寄りでホットスポット内にいる端末から最も受信端末寄りでホットスポット内にいる端末までの経路のホップ数が所定の閾値以上であるか否かが判定されている。
【0118】
ここでは、通信品質向上のためなるべくインターネットを経由したいが、しかしながら、端末〜アクセスポイント(AP)間も無線通信の1ホップとカウントされるため、インターネットへのゲートウェイとなるホットスポットエリア内に在圏した2つの端末がアドホックネットワーク上で近接した位置関係にある場合(例えば、ホップ数=1の距離にある場合など)にまでわざわざインターネットを経由させる必要はないとの洞察から、上記所定の閾値は例えば「2ホップ」などに設定される。
【0119】
換言すれば、本実施例においても、上記実施例1と同様に、所定数以上のホップ数が削減される場合のみ、ルートの一部をインターネットを経由した経路に置き換える。
【0120】
このようなS1408における判定処理において、削減されるホップ数が所定の閾値以上であると判断された場合(S1408の「YES」)、図11に示したRREQから図13に示したRREPを作るように、受信したRREQからインターネットを経由した経路を採用したRREPが作成される(S1409)。一方、S1408における判定処理において、削減されるホップ数が所定の閾値未満であると判断された場合(S1408の「NO」)、「グローバル通信用識別子1」及び「グローバル通信用識別子2」の両フィールドが空のRREPが作成される(S1410)。ただし、フラグHにより、インターネットを経由しないルートであることが伝達される。
【0121】
当然、そもそも受信したRREQに2以上のグローバル通信用識別子が記述されていない場合(S1407の「NO」)も、S1410においてアドホックネットワークに閉じた経路を示すRREPが作成される。
【0122】
そして、このようにして作成されたRREPは送信端末へ向けてユニキャストで返信される(S1411)。上述のように、フラグHが立っている場合、この返信もインターネットを経由する。これで1回の経路探索処理が終了し、S1401へ戻る。
【0123】
このように、本実施例によれば、アドホックネットワーク内でRREQが転送されるというMANET内に閉じたルーティング処理でありながら、インターネットに接続している中継ノードは上述のようなグローバル通信用識別子をRREQに付加して転送するという特徴を備えたことにより、インターネット上に経路要求を流さずにインターネットを経由したルートも考慮した経路探索が可能となる。
【0124】
従来、アドホックネットワーク上での経路探索にはアドホックネットワーク上で経路要求する必要があり、インターネット上での経路探索にはインターネット上で経路要求する必要があったことと比較すれば、本実施例の有益性は明らかである。
【0125】
なお、本実施例においては、RREQを受信した受信端末がインターネットを経由するRREPを作成するか否かを判断する(図14のS1408)際に、受信したRREQの転送経路となった端末の中で最も送信端末寄りのホットスポット内の端末と最も受信端末寄りのホットスポット内の端末とをインターネットへのゲートウェイとして利用するものとした。また、インターネットを経由することにより削減されるホップ数が所定の閾値以上であれば必ずインターネットを経由するルートが選択されるものとした。
【0126】
この点、理論上は、最も送信端末寄りでないホットスポット内の端末を利用することも、最も受信端末寄りでないホットスポット内の端末を利用することも可能であり、さらに、削減されるホップ数が所定の閾値以上の場合であってもあえて現行通りアドホックネットワーク内に閉じたルーティングを行うことも可能である。
【0127】
しかしながら、当業者には既知のように、アドホックネットワークではホップ数が増えるほど通信品質は劣化するため、できる限りアドホックネットワーク内での無線リンクを減らして、インターネットを経由したルートを通った方が通信品質は良好となる。
【0128】
したがって、上記実施例のようにできる限りインターネットを経由させようとすることは、好ましい実施形態であると言える。
【実施例3】
【0129】
次いで、図15及び16を用いて、本発明の更に別の一実施例(実施例3)について説明する。本実施例は、上述の実施例1及び2に共通する変形例であり、採用されるルーティングプロトコルはDSRでもAODVでもよい。
【0130】
上述の実施例1及び2では、グローバル通信用識別子がRREQに付加される以外の点については現行のプロトコルと同様にMANET内でのルーティング処理を行い、それにより発見されたルート上においてインターネットによるショートカットが可能であるか否かを判断できるようにし、可能であればインターネットを経由したルートを採用する、という実施形態であった。
【0131】
本実施例は、これを更に一歩進めて、インターネットによるショートカットを利用可能なMANET内ルートを積極的に探索するものである。
【0132】
具体的には、上述の実施例1及び2では、現行のDSR及びAODVと同様に、受信端末(RREQの宛先ノード)に最初に到着したRREQだけRREP返信処理の対象となり、遅延して到着したRREQは冗長な(すなわち、ホップ数が多い)経路を通って来たものと判断して破棄していたのに対し、本実施例では、MANET内に閉じたルーティングではホップ数が多く、遅延を伴うルートであっても、上述の実施例1又は2に係るようなインターネットを利用したショートカットを利用すれば、ホップ数が削減され、最もホップ数が少ないルートが得られる可能性があることに鑑み、RREQの宛先ノードは、最初のRREQ受信後、所定時間、同じ送信元ノードからの他のRREQの受信を待機するものとする。
【0133】
そして、本実施例では、RREQ受信を上記所定時間待機したRREQの宛先ノードは、最初に受信されたRREQと該所定時間中に受信された遅延RREQとの中から、上述の実施例1及び2のようにインターネットを利用したショートカットを考慮して、最もホップ数が少ないルートを選択する。
【0134】
図15及び16に一例を挙げる。ここで、図15に示すようにアドホック通信端末が点在する通信環境において、送信端末がRREQを受信端末へ向けてフラッディングしたとき、RREQが2つの経路(ルート1、ルート2)で受信端末(宛先ノード)へ到達した場合を考える。また、いくつかの中継ノードはホットスポット(HS)1〜3のエリア内に在圏している。
【0135】
各ルートが経由する端末について図16にまとめる。図16(a)はルート1が経由する端末(ノード)を示し、図16(b)はルート2が経由する端末(ノード)を示す。図示するように、この例では、ルート2の方がホップ数が多い。したがって、通常であれば、ルート2を経由したRREQの方がルート1を経由したものより遅く受信端末に到達するはずである。
【0136】
上述のように、現行のルーティングプロトコルでは、このような遅延して到達したRREQは破棄されることになるが、本実施例では、上記所定時間内であればこのような遅延したRREQもRREP作成の対象となる。
【0137】
上記所定時間内にルート2を経由したRREQのみが受信されたものとすると、受信端末は、次に、最初に受信されたルート1(図16(a))経由のRREQと、ルート2(図16(b))経由のRREQとを比較し、ホップ数が少ない方を選択する段階となる。
【0138】
ただし、本例では、ルート2上にはホットスポットエリア内に位置する中継ノードが2つ以上存在するため、受信端末は、上述の実施例1及び2のようなショートカットを利用することができる、と判断することができる。
【0139】
図15に示す例では、ルート2上で、最も送信端末寄りのホットスポットエリア内に位置するノードは端末Bであり、最も受信端末寄りのホットスポットエリア内に位置するノードは端末Mであることから、図16(b)に示したルート2は、上述の実施例1及び2のような手法を利用して端末B〜端末M間をインターネットによるショートカットさせることにより、図16(c)に示すようなルート2’とすることができる。
【0140】
すると、図示するように、図16(c)に示すインターネットを利用したルート2’では、図16(b)に示すMANET内に閉じたルート2に比して、ホップ数を2ホップ削減することができることがわかる。
【0141】
したがって、本例において、受信端末は、ルート1(図16(a))のホップ数と、ルート2’(図16(c))のホップ数とを比較して、ホップ数のより少ないルート2’をRREP経路に優先的に選択することができる
このように、本実施例では、受信端末(宛先ノード)が従来は破棄していた遅延したRREQを含めて積極的にインターネットによるショートカットが可能なルートを探索することができるため、より少ないホップ数のルートを優先的に経路として使用することができる。
【0142】
なお、本実施例において、上記所定時間は、原則として任意に定めることができるが、経路探索に要する時間が過度に長くならないように、適度な時間長に設定されるべきである。
【0143】
例えば、最初に受信されたRREQの経路のホップ数に基づいて、遅延した宛先ノードに到達したRREQのMANET内に閉じたルートのホップ数が最初に受信されたRREQ経路のホップ数の所定数分の1のホップ数以内であれば許容するようにしてもよく、或いは、最初に受信されたRREQの経路のホップ数とは無関係に、予め設定された所定ホップ数までの遅延を許容してもよい。
【0144】
また、ホップ数ではなく遅延時間を基準とし、最初にRREQから受信されてから所定時間だけ待機するようにしてもよい。または、受信端末は最初に受信されたRREQが送信端末により送信されてから受信端末により受信されるまでに要した時間のプラス所定パーセントまでの時間が経過するまで待機するようにしてもよい。ただし、この場合、送信端末がRREQ送信時にRREQに送信時刻をタイムスタンプすることが必要となる。
【0145】
また、常に上記所定時間待機するものとせず、例えば、該所定期間の途中でグローバル通信用識別子を2つ以上含んだ(すなわち、インターネットによるショートカットが可能な経路を持つ)RREQが受信されたときには、その時点で遅延したRREQの受信待機を中止するようにしてもよい。
【0146】
また、ここでは、受信端末は、最初にRREQが受信されてから所定時間他のRREQの受信を待機するものとし、受信された1以上のRREQの中から最もホップ数が少ないルートをRREP返信対象に選択するものとしたが、ホップ数に代えて又は加えて、通信帯域や遅延時間などのパラメータを考慮してルートを選択してもよい。これは、例えば、PINGコマンドを利用してスループットやRTT(Round Trip Time)などを測定することにより得られる。
【0147】
さらに、本実施例の好ましい変形例として、インターネットによるショートカットが可能なルートをより積極的に探索するために、宛先ノードが遅延したRREQを待機するだけでなく、各中継ノードがRREQを転送する際に処理済みのRREQであってもグローバル通信用識別子を含んだRREQについては破棄せずに、最初に受信されたRREQと同様に転送処理を行うようにしてもよい。これにより、インターネットによるショートカットが可能なルートを経由したRREQが受信端末に到達する可能性を高めることができ、インターネット経由の経路の利用を促進することができる。
【0148】
以上、本発明の実施例1〜3について具体例を挙げながら説明した。しかしながら、ここに説明及び図示した実施例はあくまで例示に過ぎず、本発明はこれらに限定されるものではない。
【0149】
例えば、上記実施例1〜3では、アドホックネットワークの無線リンクよりも通信品質が良いと想定される有線網の一例としてインターネットを挙げたが、本発明はこれに限られず、インターネット以外の有線網を利用することも当然可能である。
【0150】
また、上記実施例1〜3では、各端末が有線網へ無線LANを利用して有線網に接続するものとしたが、本発明はこれに限られず、例えばDSRC(dedicated short range communication;挟域通信)などの他の通信規格を利用することも当然可能である。
【0151】
また、上記実施例1〜3では、RREQパケット構成などをリアクティブ型のルーティングプロトコルであるDSR又はAODVが用いられるものとして説明したが、本発明はこれらに限定されるものではなく、他のリアクティブ型プロトコルであっても、或いは、プロアクティブ型プロトコルであっても、利用することができる。
【0152】
プロアクティブ型のルーティングプロトコルが用いられる場合、各ノード区間の経路情報が常にやりとりされているため、各端末はホットスポットエリア内に位置する端末まで何ホップの距離にあるかを把握している。そこで、プロアクティブ型ルーティングプロトコルが用いられる場合には、上記実施例1〜3の変形例として、各端末が、自局がホットスポットエリア内に位置すれば上記実施例1〜3と同様に自局のグローバル通信用識別子をRREQに追記すると共に、自局がホットスポットエリア内に位置しなければ自局が持つ周辺ノード情報から自局からも最も近いホットスポットエリア内に位置する端末に到達するまでのホップ数をRREQに追記するようにしてもよい。これにより、インターネットによるショートカット可能なルートをより一層積極的に探索することができる。
【0153】
また、上記実施例1〜3では、一部の中継ノードがホットスポットエリア内に位置する場合について述べたが、上記説明を読んだ当業者には明らかなように、本発明はRREQ送信元ノード及び/又はRREQ宛先ノードがホットスポットエリア内に位置する場合にも等しく適用することが可能である。ただし、当業者には明らかなように、送信元ノードがホットスポットエリア内に位置する場合であっても、当然、RREQはMANET内のみにフラッディングされる。
【0154】
また、現行のルーティングプロトコルでは、ノードの移動や電源オフなどによりルートが切れた場合に再度経路探索が行われるようになっているが、本発明においては、いずれの実施例及び変形例においても、ルート切れの場合に加えて、更に、送信元ノード、ルートに選ばれた中継ノード、及び宛先ノードのいずれかがホットスポットエリア内に入ったとき及びホットスポットエリアから外へ出たときにも経路が再探索されることが好ましい。なぜなら、新たなインターネットを利用した経路により、ホップ数を更に削減して通信品質を向上させることが可能となる可能性があるためである。
【0155】
また、本発明の適用に合わせたインフラ側の工夫として、アドホックネットワークによってインターネットを利用したショートカットに頻繁に利用されるホットスポットエリア(のAP)間をトンネリング(tunneling)やVPN(Virtual Private Network;仮想閉域網)などの技術を利用して仮想上一体化しても有益的である。これにより、一方のホットスポットエリア内でブロードキャストされたRREQは他方のホットスポットエリア内にもブロードキャストされたことになり、MANET内端末識別子の処理のみで有線網を利用したショートカットが可能となる。
【0156】
さらに、上記実施例及び変形例においては、ルーティング判定の指標としてホップ数を例に挙げたが、当業者には明らかなようにこれは一例に過ぎず、例えば通信帯域や遅延時間などの通信品質に関連する指標などの他の指標を用いてルーティングの判定を行うことも可能である。
【産業上の利用可能性】
【0157】
本発明は、アドホックネットワークに利用できる。上述のように、用いられるルーティングプロトコルは問わない。
【0158】
また、アドホック通信端末の種類も問わない。ノードとなる端末は、携帯電話であってもよく、PDA(Personal Digital Assistant;携帯情報端末)であってもよく、又は、車両に搭載された通信装置であってもよい。
【0159】
複数の車両に搭載された通信装置により車車間通信としてアドホックネットワークが構築されている場合、特に本発明に係るルーティング方法を適用すると有益的である。
【0160】
車車間通信の場合、ノードとなる各車両は、ほぼ道路上のみに存在すると言えるため、ルートが探索しやすい。また、車両運転中は、数km前方の交通状況・道路状況を知りたい、というニーズがあると考えられるため、一時的にアドホックネットワークを張って情報を収集する、といった使い方が考えられる。
【0161】
さらに、本発明を車車間通信に適用した場合の最大の利点の1つは、交差点をホットスポットにすることによって、任意の交差点まで有線網によってショートカットできる点である。これは、例えば交差点に設置された信号機や一時停止の標識などに付随して例えば無線LANのビーコンを送出するAPを設置することによって、比較的容易に、多くのノードの滞在・通過が見込めるエリア(交差点近傍)を確実にホットスポットエリアとすることができ、本発明に係るルーティングを利用した通信品質向上の促進が見込まれる。
【図面の簡単な説明】
【0162】
【図1】アドホック通信端末が点在し、一部の端末がホットスポットエリア内にいる通信環境の一例を示す図である。
【図2】本発明の一実施例におけるアドホック通信端末の概略構成図である。
【図3】本発明の一実施例においてRREQを中継するノードによってRREQに追記される自局情報を示す図である。
【図4】図1の通信環境においてRREQが送信端末から受信端末へ到達した際に経由した経路の一例を示す図である。
【図5】現行DSRプロトコルに準拠し、図4の経路において受信端末に到達したRREQに記述された経路情報を示す図である。
【図6】本発明の一実施例により拡張されたDSRプロトコルに準拠し、図4の経路において受信端末に到達したRREQに記述された経路情報を示す図である。
【図7】本発明の一実施例により拡張されたDSRプロトコルに準拠し、図6のRREQに対して作成されたRREPに記述された経路情報を示す図である。
【図8】図4の場合に、現行DSRプロトコルにより確立されるルートと、本発明の一実施例により拡張されたDSRプロトコルにより確立されるルートとを比較する図である。
【図9】本発明の一実施例において各端末において行われる受信したRREQに対する処理の流れを示すフローチャートである。
【図10】本発明の別の一実施例により拡張されたAODVプロトコルに準拠したRREQのパケット構造を示す図である。
【図11】本発明の別の一実施例により拡張されたAODVプロトコルに準拠し、図4の経路において受信端末に到達したRREQのパケット構造を示す図である。
【図12】本発明の別の一実施例により拡張されたAODVプロトコルに準拠したRREPのパケット構造を示す図である。
【図13】本発明の別の一実施例により拡張されたAODVプロトコルに準拠し、図4の経路において受信端末により返信されるRREPのパケット構造を示す図である。
【図14】本発明の別の一実施例において各端末において行われる受信したRREQに対する処理の流れを示すフローチャートである。
【図15】RREQが送信端末から受信端末へ到達した際に経由した2つの経路の一例を示す図である。
【図16】図15の場合に、現行のルーティングプロトコルにより確立されるルートと、本発明の更に別の一実施例に係るルーティングプロトコルにより確立されるルートとを比較する図である。
【符号の説明】
【0163】
200 アドホック通信端末
201 送受信部
202 パケット転送部
203 ルーティングテーブル
204 ルーティング用パケット処理部
205 アドレス格納部
【技術分野】
【0001】
本発明は、概して、アドホックネットワークにおけるルーティング方法に係り、特に、スループットの向上及び無線リソースの消費抑制が図られたルーティング方法に関する。
【背景技術】
【0002】
従来、基地局や固定局を使わずに、端末間でホッピング(中継)することにより、データ伝送を可能とするアドホックネットワーク(或いは、マルチホップ無線ネットワーク、又は、Mobile Ad−hoc Network;MANET)が知られている。
【0003】
アドホックネットワークでは、すべての端末によって自律的にネットワークが構築されるため、基地局等の設置が不要となり、柔軟性が高く、設置の容易なネットワーク構築が可能となる。
【0004】
アドホックネットワークにおいて用いられるルーティングプロトコル(経路制御プロトコル)については、IETF(Internet Engineering Task Force)のMANETワーキンググループ(http://www.ietf.org/html.charters/manet−charter.html)から種々のものが提案・公開されており、標準化が進められている。
【0005】
現在、提案・公開されているルーティングプロトコルは、大きく分けるとリアクティブ(Reactive)型、プロアクティブ(Proactive)型、及び、これらのハイブリッド(複合)型、に分けられる。
【0006】
リアクティブ型のルーティングプロトコルは、実際にデータを送信する際に初めて起動し、周りにある通信可能な端末の電波を送受信して確かめてからルート構築を行うものであり、代表的なものとしては、「Adhoc On Demand Distance Vector(AODV)」(Experimental RFC 3561)や、「Dynamic Source Routing(DSR)」(Internet Draft;有効期限2005年1月19日)などが挙げられる。
【0007】
プロアクティブ型のルーティングプロトコルは、任意の時間間隔ごとにルーティング可能な端末を確かめており、常にルートが構築されていて通信可能状態となっているものであり、代表的なものとしては、「Optimized Link State Routing(OLSR)」(Experimental RFC 3626)や、「Topology Broadcast based on Reverse−Path Forwarding(TBRPF)」(Experimental RFC 3684)などが挙げられる。
【0008】
すなわち、リアクティブ型プロトコルではデータを送信する際にどの端末を通ってデータをリレーさせるのかが決定されるのに対し、プロアクティブ型プロトコルでは予め決定されているリレーの順番に従ってデータが送信される。前者は各端末における電池効率の点で有利であり、後者は通信タイムアウトや送信データロスが少ないという利点を有する。
【0009】
また、このような標準化への取り組みとは別に、アドホックネットワークにおける独自のパケットルーティング方法も提案されている(例えば、特許文献1参照)。
【0010】
さらに、アドホックネットワークとインターネットなどの有線インフラを組み合わせて利用する際のルーティング等に関する技術も提案されている(例えば、特許文献2〜4参照)。
【特許文献1】特開平11−239176号公報
【特許文献2】特開2002−354016号公報
【特許文献3】特開2003−230167号公報
【特許文献4】特開2004−248180号公報
【発明の開示】
【発明が解決しようとする課題】
【0011】
周知の通り、アドホックネットワークでは、ホップ数が増えるほど、すなわち経由する端末(ノード)が増えるほど、通信品質は劣化する傾向となる。
【0012】
本願発明者らは、アドホックネットワークにおいて、あるルートの中継局となっているアドホック通信端末の中に例えば無線LANなどを利用して例えばインターネットなどの有線網に接続可能なものが2つ以上存在する場合、ルートの一部を有線網経由の経路に置き換えることによって、通信品質を大幅に改善できることに着目した。
【0013】
この点、上述のIETF−MANET−WGにより提案・公開されている種々のルーティングプロトコル及び上記特許文献1記載のルーティング方法はいずれも、アドホックネットワーク内に閉じたルーティングを行うものであり、アドホックネットワークと同時にインターネットなどの有線網を利用することへ拡張されていない。
【0014】
また、上記特許文献2記載の方法は、インターネットに接続されたノードがアドホックネットワーク内に入ったときにインターネット経由でルーティングしないようにするためのものであり、アドホックネットワークと同時にインターネットなどの有線網を利用するものではない。
【0015】
また、上記特許文献3記載の方法は、アドホックネットワークを介してインターネットへ接続する通信において、インターネットへの接続先として関門(ゲートウェイ)となる端末を探索するものであるが、アドホック通信端末同士のルートの一部にインターネットを利用するものではない。また、この従来方法に従ってアドホック端末同士を接続した場合、必ずインターネットを経由した通信経路となり、端末同士が近接している場合であってもアドホック通信ができなくなってしまう。
【0016】
さらに、上記特許文献4記載の方法は、複数の無線通信メディアの中から通信状況に応じていずれかを選択するものであるが、選択されるのはルート全体に利用される通信メディアであって、アドホックネットワークにおいてルートの一部をインターネットなどの有線網経由の経路に置き換えるものではない。
【0017】
このように、従来提案されているアドホックネットワークにおけるルーティング方法では、アドホックネットワークにおいて、あるルートの中継局となっているアドホック通信端末の中に有線網と接続可能なものが2つ以上あったとしても、ルートの一部を有線網経由の経路で置き変えたルーティングを実現させることはできない。
【0018】
仮に、例えばIETF−MANET−WGにおいて提案・公開されているルーティングプロトコルをそのまま用いて、有線網を経由したルートまで含めたルート探索を行おうとすれば、ブロードキャストされたルートリクエスト(RREQ)を受信した端末が有線網と接続している場合、RREQがアドホックネットワーク内だけでなく有線網内にもブロードキャストで転送されるといった構成になりかねない。そのような事態は、有線網の通信トラフィックに甚大な被害を与えかねず、実施不可能である。
【0019】
本発明はこのような課題を解決するためのものであり、アドホックネットワークにおいて、アドホックネットワーク内に閉じたパケット伝送のみによって、アドホックネットワーク内に閉じたルートだけでなく、ルートの一部を有線網経由の経路で置き換えたルートをも探索可能とすることによって、従来方法に比してスループットを向上させ、無線リソースの消費を抑制することが可能なルーティング方法を提供することを主たる目的とする。
【課題を解決するための手段】
【0020】
上記目的を達成するための本発明の第一の態様は、アドホックネットワーク(MANET)におけるルーティング方法であって、ルートリクエスト(RREQ)を送信又は転送するノードは、自局が外部の有線網と通信接続している場合、該有線網における自局の識別子を上記ルートリクエストに付加して送信又は転送する、アドホックネットワークにおけるルーティング方法である。
【0021】
この第一の態様において、上記外部の有線網とは例えばインターネットなどである。その場合、アドホック通信端末(ノード)が、例えば無線LAN機能を備え、例えばホットスポット(hotspot)エリア内に在圏するとき、そのノードはアドホックネットワーク内に閉じたアドホック通信もインターネットを経由した通信も可能となる。
【0022】
この第一の態様によれば、ルートリクエストを受信した宛先ノード(送信先ノード)は、経路中に有線網に接続しているノードが存在するか否か及び存在する場合何台存在するのかを知ることができる。
【0023】
また、このルートリクエストの送信・転送は、アドホックネットワーク内に閉じて行われるものであり、ルートリクエストの宛先ノードは、上記有線網で何らパケット伝送を行うことなく、すなわち該有線網上の通信トラフィックに影響を与えることなく、該有線網を利用する場合の各ノードの識別子を取得することができる。
【0024】
上記目的を達成するための本発明の第二の態様は、上記第一の態様において、上記ルートリクエストの宛先ノードは、受信したルートリクエストに2以上の上記有線網における識別子が含まれていた場合、これら2以上の識別子のうちルート上最も送信元ノードに近いノードを表す1つの識別子と最も宛先ノードに近いノードを表す1つの識別子とを用いて、これら2つの識別子が表すノード間は上記有線網を経由する経路を採用したルートリプライ(RREP)を作成する、アドホックネットワークにおけるルーティング方法である。
【0025】
この第二の態様によれば、アドホック通信経路の一部がアドホックネットワークにおける無線リンクよりも良好な通信品質が見込める有線網を経由した経路で置き換えられるため、アドホックネットワーク内のみを通る経路を採用した場合に比して通信品質が向上する。
【0026】
上記目的を達成するための本発明の第三の態様は、上記第二の態様において、上記ルートリクエストの宛先ノードは、アドホックネットワーク内のみでルーティングした場合に上記2つの識別子が表すノード間に所定数(例えば2ホップ)以上のホップ数が存在する場合のみ、これら2つの識別子が表すノード間は上記有線網を経由する経路を採用したルートリプライを作成する、アドホックネットワークにおけるルーティング方法である。
【0027】
この第三の態様によれば、近接した(例えばホップ数が1の距離にある)ノード間の無線リンクが有線網に置き換えられてしまうことが防止されるため、ホップ数削減の効果が十分に得られる場合のみ、有線網が利用されるようにすることができる。
【0028】
上記目的を達成するための本発明の第四の態様は、上記第三の態様において、ルートリクエストの宛先ノードは、最初のルートリクエストを受信してから所定期間、他の経路を経由した同じ送信元ノードからのルートリクエストの受信を待機し、上記所定期間内に同じ送信元ノードから1以上のルートリクエストが受信された場合、上記最初のルートリクエスト及び前記所定期間中に受信されたルートリクエストのうち2以上の上記有線網における識別子が含まれているルートリクエストについてはこれら2つの識別子が表すノード間は上記有線網を経由するものとして、各ルートリクエストの経路のホップ数を比較し、最もホップ数が少ない経路を有するルートリクエストに対してルートリプライを作成する、アドホックネットワークにおけるルーティング方法である。
【0029】
従来、最初に宛先ノードによって受信されたルートリクエスト以外の遅延して到着したルートリクエストは冗長な経路を通っているものと判断されて破棄されていたが、この第四の態様によれば、アドホックネットワーク内に閉じたルートでは最小ホップ数でなかったルートが上記第三の態様のように経路の一部を有線網でショートカットすることによって最小ホップ数のルートとなる可能性があることに鑑み、遅延して宛先ノードに到着したルートリクエストであってもRREP返信候補に取り上げることによって、有線網を利用して通信品質を向上させる機会を増やすことができる。
【0030】
上記目的を達成するための本発明の第五の態様は、上記第四の態様において、ルートリクエストの宛先ノードは、2以上の上記有線網における識別子が含まれているルートリクエストが受信されたときに上記他の経路を経由した同じ送信元ノードからのルートリクエストの受信の待機を終了する、アドホックネットワークにおけるルーティング方法である。
【0031】
この第五の態様によれば、経路の一部を有線網を経由する経路に置き換えることによるショートカットが可能なルートを示すルートリクエストが1つでも受信された段階で、当該ルートリクエストを選択することによってホップ数の削減が見込めると判断し、上記所定待機時間を速やかに終了させるため、ルートリプライをより迅速に作成することができる。
【0032】
上記目的を達成するための本発明の第六の態様は、上記第四又は第五の態様において、受信したルートリクエストを転送するノードは、受信したルートリクエストに上記有線網における識別子が含まれている場合、その受信したルートリクエストが既に転送済みのルートリクエストであっても破棄せずに初めて受信したルートリクエストと同様に転送する、アドホックネットワークにおけるルーティング方法である。
【0033】
従来、既に転送済みのルートリクエストを受信したノードはそのルートリクエストを破棄していたが、この第六の態様によれば、アドホックネットワーク内に閉じたルートでは最小ホップ数でなかったルートが上記第三の態様のように経路の一部を有線網でショートカットすることによって最小ホップ数のルートとなる可能性があることに鑑み、既に転送済みのルートリクエストであっても有線網における識別子を含み、有線網を利用したショートカットが実現される可能性があるルートリクエストについては破棄せずに再度転送することによって、有線網を利用して通信品質を向上させる機会を増やすことができる。
【0034】
上記目的を達成するための本発明の第七の態様は、上記第四乃至第六の態様のいずれかにおいて、各ノードは、自局周辺の上記有線網と通信接続しているノードを探索し、存在する場合、ルートリクエストを送信又は転送する際に自局からその自局周辺の上記有線網と通信接続しているノードまでのホップ数を該ルートリクエストに付加する、ことを特徴とするアドホックネットワークにおけるルーティング方法である。
【0035】
この第七の態様によれば、このようなルートリクエストを受信した宛先ノードは、ルートリクエストが転送されてきた経路中に有線網へ接続しているノードがない場合であっても、有線網へ接続可能なノードまでのホップ数を知ることができるため、有線網を経由した場合のホップ数を知ることができる。よって、アドホックネットワーク内では冗長なルートも含めて、有線網によるショートカットを利用した場合に最もホップ数が少なくなるルートを探索することができる。
【0036】
なお、ここでは、ルーティング判定の指標としてホップ数を例に挙げたが、当業者には明らかなようにこれは一例に過ぎず、例えば通信帯域や遅延時間などの通信品質に関連する指標などの他の指標を用いてルーティングの判定を行うことも可能である。
【発明の効果】
【0037】
本発明によれば、アドホックネットワークにおいて、経路の一部を積極的に有線網経由の経路に置き換えることによってホップ数の削減を図ることができるため、スループットなどの通信品質の向上及び無線リソースの消費抑制が図られたルーティング方法を提供することができる。
【発明を実施するための最良の形態】
【0038】
以下、本発明を実施するための最良の形態について、添付図面を参照しながら実施例を挙げて説明する。なお、アドホックネットワークの基本概念については当業者には既知であるため、詳しい説明を省略する。
【実施例1】
【0039】
まず、図1〜9を用いて、本発明の一実施例(実施例1)に係るルーティング方法について説明する。本実施例では、ルーティングプロトコルとしてDSRが用いられることを前提し、図1に示すようなアドホック通信端末が点在する通信環境において、送信端末が受信端末へデータを送信するために経路探索(ルートディスカバリー)を実行する場合を考える。
【0040】
また、本実施例において、各通信端末は、アドホック通信が可能であると共に、ホットスポットエリア内にいるときには無線LANを利用してインターネットに接続する能力を有するものとする。図1に例示した通信環境では、端末B及びCがホットスポット(HS)1内に位置し、端末G及びJがホットスポット(HS)2内に位置し、端末I、K、及びMがホットスポット(HS)3内に位置している。
【0041】
本実施例は、これらインターネットに接続した端末を利用して、アドホックネットワーク内に閉じたルーティング処理によって、インターネットを経由する経路も考慮した経路探索を可能にする。
【0042】
図2は、各アドホック通信端末の概略構成を示す。
【0043】
端末200は、無線機である送受信部201と、受信したパケットを転送するか否かを判断するパケット転送部202とを有する。
【0044】
また、端末200は、ルーティングのための経路表(ルーティングテーブル)203を有する。ルーティングテーブルは、各端末に記憶されており、宛先とその宛先へパケットを届けるために送り出す転送先の組(ペア)を表にした参照テーブルである。パケット転送部202は、自局宛でないパケットを受信したとき、ルーティングテーブル203を参照して、宛先に適したノードへ転送する。
【0045】
また、端末200は、ルートリクエスト(RREQ)及びルートリプライ(RREP)を処理するルーティング用パケット処理部204と、各端末(ノード)の識別子(アドレス)を格納したアドレス格納部205とを有する。
【0046】
本実施例は、現行のDSRプロトコルを拡張するものであり、以下に特段の説明がない点については通常のDSRプロトコルに準拠して処理される。
【0047】
本実施例において追加・拡張された主たる点は、ルーティング用パケット処理部204の機能である。現行のDSRプロトコルによれば、ルーティング用パケット処理部204は、RREQを中継する際、受信されたRREQに自局のアドホックネットワーク内での識別子(MANET内端末識別子)を追記してパケット転送部202へ渡し、パケット転送部202がこれを転送する。
【0048】
本実施例において、ルーティング用パケット処理部204は、更に、無線LAN通信機能を備え、ホットスポットのアクセスポイント(AP)が送出しているビーコンを検出し、自局がホットスポットエリア内に位置するか否かを判断する。そして、自局がホットスポットエリア内に位置すると判断した場合、上記MANET内端末識別子に加えて、インターネット上における自局の識別子(グローバル通信用識別子)をRREQに追記する。グローバル通信用識別子が追記されたRREQは、通常のRREQと同様、アドホックネットワーク内だけでフラッディングされ、インターネット上へは送出されない。
【0049】
追記される情報を図3に示す。図3(a)は、端末がホットスポットエリア内に位置する場合に中継するRREQに追記される自局情報であり、図3(b)は、端末がホットスポットエリア内に位置しない場合に中継するRREQに追記される自局情報である。
【0050】
ここで、MANET内端末識別子は、例えば、MACアドレスやIPアドレスなどであり、グローバル通信用識別子は、例えば、IPアドレスである。MANET内端末識別子とグローバル通信用識別子とは、例えば、識別子(アドレス)の割り当て空間を別にする、或いは、専用のフラグ(1ビット)を設け、グローバル通信用識別子が追記された場合にはこのフラグを立てる、などにより区別することができる。
【0051】
このように、本実施例に係る拡張によれば、経路探索時に、中継ノードがホットスポットエリア内にいれば、RREQに追記される情報が増えるが、これは経路探索時のみであり、ルート確立後のデータ送信では特段の追加的情報が付加されない。
【0052】
RREQの中継に関して、その他の点は現行のDSRに準拠する。すなわち、送信端末からブロードキャストされたRREQは、周囲の端末によって受信される。各端末は、受信したRREQの宛先が自局でなければ、上述のような自局情報を追記した上で、RREQをブロードキャストする。このような転送・中継が繰り返され、最終的に受信端末に到達する。
【0053】
また、ある端末から転送されたRREQが転送先ノードによる転送によって再度戻ってきて最初の端末により受信される場合が当然生じるが、「RREQに記述された経路情報に自局が含まれている場合、そのRREQは破棄する」というDSRプロトコルのルールによって、そのRREQは処理済みとして破棄される。
【0054】
図4は、図1に例示した通信環境において、RREQが送信端末から受信端末へ到達した際に経由した経路の一例を示している。
【0055】
RREQがこのようなルートを通った場合、現行のDSRプロトコルによれば、受信端末により受信されたRREQには図5に示すような経路情報が記述されている。この経路情報から、このRREQは、送信端末から、端末B、端末C、端末F、端末I、端末K、及び、端末Mを順に経由して受信端末に届いたことがわかる。
【0056】
一方、本実施例によれば、上述のようにDSRプロトコルが拡張されているため、受信端末により受信されたRREQには図6に示すような経路情報が記述されていることになる。図示するように、ホットスポットエリア内に位置する端末B、端末C、端末I、端末K、及び端末Mに関しては、MANET内端末識別子だけでなく、グローバル通信用識別子も記述されている。
【0057】
RREQは様々な経路でそのRREQの宛先ノードである受信端末に到達するが、受信端末は、最初に到達したRREQが最もホップ数が少ない最短のルートを経由していると判断して、その最初に受信したRREQに基づいてRREPを作成し、送信端末にユニキャスト送信する。現行のDSRプロトコルによれば、図5に示したようなRREQを最初に受信した受信端末はこの経路を選択し、この経路情報を記述されたRREPを作成して送信端末にユニキャストする。このRREPは、図5のRREQに記述された経路を逆にたどって転送されながら送信端末に到達する。
【0058】
一方、本実施例に係るルーティング方法によれば、図6に示すようなRREQを最初に受信した受信端末(=RREQの宛先ノード)は、グローバル通信用識別子が記述された端末の中で最も送信端末に近いもの(ここでは端末B)と最も受信端末に近いもの(ここでは端末M)とをそれぞれ抽出し、それらのグローバル通信用識別子を利用してそれらノード間はインターネットを経由する経路を通るRREPを作成する。
【0059】
図6に示すRREQの場合、受信端末で作成されるRREPは図7のようになる。この図7に示すRREPは、送信端末〜端末B間はアドホックネットワークを経由し、端末B〜端末M間はインターネットを経由し、更に、端末M〜受信端末間はアドホックネットワークを経由した経路が選択されたことを意味する。
【0060】
この本実施例に係るRREPも、現行プロトコルと同様、記述された経路を逆にたどって送信端末にユニキャストされる。したがって、端末Mから端末Bへの転送にはインターネットが利用される。このRREPの転送はブロードキャストであるRREQとは異なりユニキャストであるため、インターネットを経由しても負荷は問題とならない。
【0061】
このように、本実施例によれば、インターネットはアドホックネットワークの無線リンクに比して十分に太く、通信品質が良いという洞察を前提として、アドホックネットワークにおいて探索・確立されるルートの一部をインターネットを経由したルートとすることができる。
【0062】
また、インターネットを経由することにより、いくつかの中継ノードがショートカットされるため、ルート全体でのホップ数の削減も見込める。図8は、現行のDSRプロトコルにより確立されるルートと本実施例により確立されるルートとを比較するものであり、図8(a)は図5に示したRREQ及びRREP経路情報を示し、図8(b)は図7に示したRREP経路情報を示す。図示するように、端末B〜端末M間をインターネットを経由したルートとすることによって、この場合、ホップ数が2ホップ短縮される。
【0063】
以上のような本実施例に係るルーティング方法について、図9を用いてより詳細に説明する。図9は、本実施例において各端末において行われる受信したRREQに対する処理の流れを示すフローチャートである。
【0064】
まず、各端末はRREQの受信を待機する(S901)。
【0065】
RREQが受信されると(S901の「YES」)、受信したRREQに記述された経路情報に自局の情報が含まれているか否かを判断する(S902)。含まれている場合(S902の「YES」)、処理済みのRREQであるものと判断して、そのRREQを破棄する(S912)。
【0066】
受信したRREQの経路情報に自局が含まれていない場合(S902の「NO」)、次いで、そのRREQの宛先ノードが自局であるか否かが判断される(S903)。自局が宛先ノードでない場合、S904〜S907の転送処理が実行され、自局が宛先ノードの場合、S908〜S911のRREP作成・送信処理が実行される。
【0067】
まず、自局が宛先ノードでない場合(S903の「NO」)、従来通り、RREQに自局のMANET内端末識別子を追記する(S904)。そして、更に、自局がホットスポットエリア内にいるか否か、換言すれば無線LANを利用してインターネットに接続している状態であるか否か、について判断し(S905)、ホットスポット内にいる場合(S905の「YES」)、上述のように受信したRREQに更に自局のグローバル通信用識別子も追記する(S906)。ホットスポット内にいない場合(S905の「NO」)、S906の処理はスキップされ、グローバル通信用識別子はRREQに記述されない。
【0068】
このように自局情報が追記されると、追記後のRREQを周囲の端末へフラッディングする(S907)。これで1回の中継処理が終了し、S901へ戻る。
【0069】
一方、自局が宛先ノードである場合(S903の「YES」)、受信したRREQに基づいてRREPを作成し、送信端末へ返信するために、まず、RREQが転送されてきたルートの一部をインターネット経由の経路で置き換えるか否かが判断される(S908)。
【0070】
S908において、「Rreq」は、受信されたRREQ内に記述されていた経路を表し、「H(R)」は、ルートR上で最も送信端末寄りでホットスポット内にいる端末から最も受信端末寄りでホットスポット内にいる端末までの経路を抽出したものを表し、「Hop(R)」は、ルートRのホップ数を表す。
【0071】
なお、H(R)は、ルートR上にホットスポット内に位置する端末が2つ以上存在しない場合、空(=0)とする。また、例えば、ルートR=送信者→A*→B*→C→D→E*→F→受信者であった場合(「*」はホットスポット内)、H(R)=A*→B*→C→D→E*となる。
【0072】
すなわち、S908においては、受信端末により受信されたRREQに記述された経路のうち最も送信端末寄りでホットスポット内にいる端末から最も受信端末寄りでホットスポット内にいる端末までの経路のホップ数が所定の閾値以上であるか否かが判定されている。
【0073】
ここでは、通信品質向上のためなるべくインターネットを経由したいが、しかしながら、端末〜AP間も無線通信の1ホップとカウントされるため、インターネットへのゲートウェイとなるホットスポットエリア内に在圏した2つの端末がアドホックネットワーク上で近接した位置関係にある場合(例えば、ホップ数=1の距離にある場合など)にまでわざわざインターネットを経由させる必要はないとの洞察から、上記所定の閾値は例えば「2ホップ」などに設定される。
【0074】
換言すれば、本実施例では、所定数以上のホップ数が削減される場合のみ、ルートの一部をインターネットを経由した経路に置き換える。
【0075】
このようなS908における判定処理において、削減されるホップ数が所定の閾値以上であると判断された場合(S908の「YES」)、図6に示したRREQから図7に示したRREPを作るように、受信したRREQからインターネットを経由した経路を採用したRREPが作成される(S909)。一方、S908における判定処理において、削減されるホップ数が所定の閾値未満であると判断された場合(S908の「NO」)、図5に示すように、現行のDSRプロトコルに従って受信されたRREQに記述されたのと同じ経路情報が記述されたRREPが作成される(S910)。
【0076】
上述のS908についての説明から明らかなように、受信したRREQに記述された経路情報に含まれる端末の中に含まれるホットスポット内にいる端末の数が2未満であってインターネットによるショートカットが物理的に実現できない場合にも、S908における判定は「NO」となり、従来通り、アドホックネットワークに閉じた経路を示すRREPが作成される。
【0077】
そして、このようにして作成されたRREPは送信端末へ向けてユニキャストで返信される(S911)。これで1回の経路探索処理が終了し、S901へ戻る。
【0078】
このように、本実施例によれば、アドホックネットワーク内でRREQが転送されるというMANET内に閉じたルーティング処理でありながら、インターネットに接続している中継ノードは上述のようなグローバル通信用識別子もRREQに付加して転送するという特徴を備えたことにより、インターネット上に経路要求を流さずにインターネットを経由したルートも考慮した経路探索が可能となる。
【0079】
従来、アドホックネットワーク上での経路探索にはアドホックネットワーク上で経路要求する必要があり、インターネット上での経路探索にはインターネット上で経路要求する必要があったことと比較すれば、本実施例の有益性は明らかである。
【0080】
なお、本実施例においては、RREQを受信した受信端末がインターネットを経由するRREPを作成するか否かを判断する(図9のS908)際に、受信したRREQに記述された経路となった端末の中で最も送信端末寄りのホットスポット内の端末と最も受信端末寄りのホットスポット内の端末とをインターネットへのゲートウェイとして利用するものとした。また、インターネットを経由することにより削減されるホップ数が所定の閾値以上であれば必ずインターネットを経由するルートが選択されるものとした。
【0081】
この点、理論上は、最も送信端末寄りでないホットスポット内の端末を利用することも、最も受信端末寄りでないホットスポット内の端末を利用することも可能であり、さらに、削減されるホップ数が所定の閾値以上の場合であってもあえて現行通りアドホックネットワーク内に閉じたルーティングを行うことも可能である。
【0082】
しかしながら、当業者には既知のように、アドホックネットワークではホップ数が増えるほど通信品質は劣化するため、できる限りアドホックネットワーク内での無線リンクを減らして、インターネットを経由したルートを通った方が通信品質は良好となる。
【0083】
したがって、上記実施例のようにできる限りインターネットを経由させようとすることは、好ましい実施形態であると言える。
【実施例2】
【0084】
次に、図10〜14を用いて、本発明の別の一実施例(実施例2)に係るルーティング方法について説明する。本実施例では、ルーティングプロトコルとしてAODVが用いられることを前提し、上記実施例1と同様に図1に示すようなアドホック通信端末が点在する通信環境において、送信端末が受信端末へデータを送信するために経路探索(ルートディスカバリー)を実行する場合を考える。
【0085】
また、本実施例においても、上記実施例1と同様に、各通信端末は、アドホック通信が可能であると共に、ホットスポットエリア内にいるときには無線LANを利用してインターネットに接続する能力を有するものとする。端末の概略構成は図2に示したのと同様であり、重複する説明は省略する。
【0086】
本実施例によっても、インターネットに接続した端末を利用して、アドホックネットワーク内に閉じたルーティング処理によって、インターネットを経由する経路も考慮した経路探索が可能となる。
【0087】
このように、本実施例は、ルーティングプロトコルとしてAODVを採用している点が異なる以外、基本的特徴は上記実施例1と同じであるため、重複する説明は省略する。したがって、以下の本実施例の説明は、主として、DSRとAODVの違いにより生じる適用方法の違いについての説明である。
【0088】
本実施例においても、RREQを受信した各通信端末は、自局がホットスポットエリア内に位置すると判断した場合、インターネット上における自局の識別子(グローバル通信用識別子)をRREQに追記した上で転送する。本実施例においても、グローバル通信用識別子が追記されたRREQは、通常のRREQと同様、アドホックネットワーク内だけでフラッディングされ、インターネット上へは送出されない。
【0089】
本実施例により拡張されたAODVプロトコルにおけるRREQのパケット構造を図10に示す。図示すように、本実施例に係るRREQは、上段部分が、フラグHを除き、現行のAODVプロトコルに準拠した構造であり、下段部分が拡張された追加部分となっている。
【0090】
上段の「タイプ」フィールドは、メッセージの種類を示すためのものであり、RREQの場合は「1」が入る。「ホップ数」フィールドは、送信元ノードから何回転送されたかを表すフィールドであり、送信端末から送信されるときには0である。
【0091】
本実施例の拡張により追加されたフラグHは、経路中にホットスポットエリア内に位置する端末が存在し、RREQにその端末のグローバル通信用識別子が記述された場合に立てられる。
【0092】
下段の追加部分には、ホットスポットエリア内に位置する端末によって追記されたグローバル通信用識別子と、送信端末からその端末までのホップ数とが記述される。AODVプロトコルでは、ソースルーティングであるDSRプロトコルと異なり、RREQ内にすべての経路が記述されず、各端末は自局が保持するルーティングテーブルに従って転送を行う。したがって、RREQを中継する各端末はRREQに自局のMANET内端末識別子は書き込まず、本実施例による拡張によりグローバル通信用識別子のみが追記される。
【0093】
図1に例示した通信環境において図4に示したようなルートで本実施例に係るRREQが転送された場合に受信端末が受信するRREQを図11に示す。図4の例では、経路上の端末B、端末C、端末I、端末K、及び端末Mがホットスポットエリア内に位置するため、RREQ下段に追加された拡張部分にこれら端末のグローバル通信用識別子及び送信端末からのホップ数が記述されている。ここで、ホップ数=3の端末F(図4)は、ホットスポットエリア内に位置しないため、RREQ内に記述がない。
【0094】
このように、本実施例に係る拡張によれば、経路探索時に、中継ノードがホットスポットエリア内にいれば、RREQに追記される情報が増えるが、これは経路探索時のみであり、ルート確立後のデータ送信では特段の追加的情報が付加されない。
【0095】
RREQの中継に関して、その他の点は現行のAODVプロトコルに準拠する。すなわち、送信端末からブロードキャストされたRREQは、周囲の端末によって受信される。各端末は、受信したRREQの宛先が自局でなければ、上述のような自局情報を追記した上で、RREQをブロードキャストする。このような転送・中継が繰り返され、最終的に受信端末に到達する。
【0096】
このように、本実施例によれば、上述のようにAODVプロトコルが拡張されているため、受信端末は、受信されたRREQから、経路上の端末B、端末C、端末I、端末K、及び端末Mがホットスポットエリア内に位置することを知ることができると共に、それらのグローバル通信用識別子も取得することができる。
【0097】
AODVプロトコルにおいても、RREQは様々な経路でそのRREQの宛先ノードである受信端末に到達し、受信端末は、最初に到達したRREQが最もホップ数が少ない最短のルートを経由していると判断して、その最初に受信したRREQに基づいてルートリプライ(RREP)を作成し、送信端末にユニキャスト送信する。
【0098】
本実施例において、RREQの宛先ノードである受信端末は、最初に受信したRREQの中に記述されたグローバル通信用識別子の数が1以下であった場合、経路の一部をインターネット経由にすることはできないと判断して、現行通り、アドホックネットワーク内に閉じたRREPを作成し、送信端末へ返信する。
【0099】
一方、受信したRREQに2以上のグローバル通信用識別子が含まれていた場合、受信端末は、それら記述されているグローバル通信用識別子の中から、経路上最も送信端末寄りの端末のものと最も受信端末寄りのものとを抽出し、RREPに記述する。
【0100】
本実施例に従って作成されたRREPのフォーマット例を図12に示す。上段の「タイプ」フィールドは、RREPの場合「2」が入る。「ホップ数」フィールドは、宛先ノードから何回転送されたかを表すフィールドであり、受信端末からユニキャスト送信される際には0である。
【0101】
下段の追加部分には、RREQに記述されていたグローバル通信用識別子の中から経路上最も宛先ノードに近いものが「グローバル通信用識別子1」フィールドに記述され、最も送信元ノードに近いものが「グローバル通信用識別子2」フィールドに記述される。
【0102】
図11に例示したRREQを受信した受信端末が返信するRREPを図13に示す。ここでは、「グローバル通信用識別子1」フィールドに端末Mのグローバル通信用識別子が記述され、「グローバル通信用識別子2」フィールドに端末Bのグローバル通信用識別子が記述される。
【0103】
このように作成された本実施例に係るRREPは、現行プロトコルと同様、送信端末にユニキャストされる。ただし、本実施例においては、現行のAODVプロトコルの拡張として、RREPを中継する各端末は、受信したRREPの「グローバル通信用識別子1」フィールドに自局のグローバル通信用識別子が記述されていた場合、自局が保持するアドホックネットワーク用のルーティングテーブルには従わず、そのRREPをインターネット経由で「グローバル通信用識別子2」フィールドに記述されたグローバル通信用識別子(アドレス)宛に送信する。そして、受信したRREPに記述されたホップ数を1インクリメントした値と宛先ノードと関連付けて新たにルーティングテーブルに記憶する。これにより、その中継ノードは、その宛先ノードまで何ホップであるかを自局内のルーティングテーブルに記憶することができる。
【0104】
インターネット経由でRREPを受信した端末は、現行通り、自局が保持するルーティングテーブルに従ってそのRREPをアドホックネットワーク内で送信する。
【0105】
このようにして、RREPの返信には、上記実施例1と同様に、インターネットが利用される。このRREPの転送はブロードキャストであるRREQとは異なりユニキャストであるため、インターネットを経由しても負荷は問題とならない。
【0106】
このように、本実施例によっても、アドホックネットワークにおいて探索・確立されるルートの一部をインターネットを経由したルートとすることができ、図8に示したようなホップ数削減が見込まれる。
【0107】
以上のような本実施例に係るルーティング方法について、図14を用いてより詳細に説明する。図14は、本実施例において各端末において行われる受信したRREQに対する処理の流れを示すフローチャートである。
【0108】
まず、各端末はRREQの受信を待機する(S1401)。
【0109】
RREQが受信されると(S1401の「YES」)、例えば「RREQ ID」フィールドの記述から処理済みのRREQであるか否かを判断する(S1402)。処理済みの場合(S1402の「YES」)、そのRREQを破棄する(S1412)。
【0110】
受信したRREQが処理済みではない場合(S1402の「NO」)、次いで、そのRREQの宛先ノードが自局であるか否かが判断される(S1403)。自局が宛先ノードでない場合、S1404〜S1406の転送処理が実行され、自局が宛先ノードの場合、S1407〜S1411のRREP作成・送信処理が実行される。
【0111】
まず、自局が宛先ノードでない場合(S1403の「NO」)、自局がホットスポットエリア内にいるか否か、換言すれば無線LANを利用してインターネットに接続している状態であるか否か、について判断し(S1404)、ホットスポット内にいる場合(S1404の「YES」)、上述のように受信したRREQに自局のグローバル通信用識別子と送信端末からのホップ数とを追記する(S1405)。ホットスポット内にいない場合(S1404の「NO」)、S1405の処理はスキップされ、グローバル通信用識別子はRREQに記述されない。
【0112】
次いで、RREQは周囲の端末へフラッディングされる(S1406)。これで1回の中継処理が終了し、S1401へ戻る。
【0113】
一方、自局が宛先ノードである場合(S1403の「YES」)、受信したRREQに基づいてRREPを作成し、送信端末へ返信するために、まず、RREQが転送されてきたルートの一部をインターネット経由の経路に置き換えることが可能な否かが判断される(S1407)。具体的には、受信されたRREQにグローバル通信用識別子が2以上記述されているか否かが判断される。
【0114】
S1407において、「Rhot」は、受信されたRREQ内に記述されていたホットスポットエリア内にいるノードのリストを表し、「Num(Rhot)」は、リストRhot内に記述されているノードの数を表す。
【0115】
S1407において、受信されたRREQにグローバル通信用識別子が2以上記述されているか否かが判断されると(S1407の「YES」)、次いで、RREQが転送されてきたルートの一部をインターネット経由の経路で置き換えるか否かが判断される(S1408)。
【0116】
S1408において、「Sub(Rhot)」は、リストRhot内に記述されている端末のうち最も送信元ノード寄りのものと最も宛先ノード寄りのものとの間のアドホックネットワーク上でのホップ数を表す。これは、図11から明らかなように、RREQ下段の拡張部分に記述されたホップ数の中で最も大きいものから最も小さいものを引いた差に等しいため、本実施例に係る拡張されたAODVプロトコルによれば容易に算出される。
【0117】
こうして、S1408においては、受信端末により受信されたRREQが経由した経路において最も送信端末寄りでホットスポット内にいる端末から最も受信端末寄りでホットスポット内にいる端末までの経路のホップ数が所定の閾値以上であるか否かが判定されている。
【0118】
ここでは、通信品質向上のためなるべくインターネットを経由したいが、しかしながら、端末〜アクセスポイント(AP)間も無線通信の1ホップとカウントされるため、インターネットへのゲートウェイとなるホットスポットエリア内に在圏した2つの端末がアドホックネットワーク上で近接した位置関係にある場合(例えば、ホップ数=1の距離にある場合など)にまでわざわざインターネットを経由させる必要はないとの洞察から、上記所定の閾値は例えば「2ホップ」などに設定される。
【0119】
換言すれば、本実施例においても、上記実施例1と同様に、所定数以上のホップ数が削減される場合のみ、ルートの一部をインターネットを経由した経路に置き換える。
【0120】
このようなS1408における判定処理において、削減されるホップ数が所定の閾値以上であると判断された場合(S1408の「YES」)、図11に示したRREQから図13に示したRREPを作るように、受信したRREQからインターネットを経由した経路を採用したRREPが作成される(S1409)。一方、S1408における判定処理において、削減されるホップ数が所定の閾値未満であると判断された場合(S1408の「NO」)、「グローバル通信用識別子1」及び「グローバル通信用識別子2」の両フィールドが空のRREPが作成される(S1410)。ただし、フラグHにより、インターネットを経由しないルートであることが伝達される。
【0121】
当然、そもそも受信したRREQに2以上のグローバル通信用識別子が記述されていない場合(S1407の「NO」)も、S1410においてアドホックネットワークに閉じた経路を示すRREPが作成される。
【0122】
そして、このようにして作成されたRREPは送信端末へ向けてユニキャストで返信される(S1411)。上述のように、フラグHが立っている場合、この返信もインターネットを経由する。これで1回の経路探索処理が終了し、S1401へ戻る。
【0123】
このように、本実施例によれば、アドホックネットワーク内でRREQが転送されるというMANET内に閉じたルーティング処理でありながら、インターネットに接続している中継ノードは上述のようなグローバル通信用識別子をRREQに付加して転送するという特徴を備えたことにより、インターネット上に経路要求を流さずにインターネットを経由したルートも考慮した経路探索が可能となる。
【0124】
従来、アドホックネットワーク上での経路探索にはアドホックネットワーク上で経路要求する必要があり、インターネット上での経路探索にはインターネット上で経路要求する必要があったことと比較すれば、本実施例の有益性は明らかである。
【0125】
なお、本実施例においては、RREQを受信した受信端末がインターネットを経由するRREPを作成するか否かを判断する(図14のS1408)際に、受信したRREQの転送経路となった端末の中で最も送信端末寄りのホットスポット内の端末と最も受信端末寄りのホットスポット内の端末とをインターネットへのゲートウェイとして利用するものとした。また、インターネットを経由することにより削減されるホップ数が所定の閾値以上であれば必ずインターネットを経由するルートが選択されるものとした。
【0126】
この点、理論上は、最も送信端末寄りでないホットスポット内の端末を利用することも、最も受信端末寄りでないホットスポット内の端末を利用することも可能であり、さらに、削減されるホップ数が所定の閾値以上の場合であってもあえて現行通りアドホックネットワーク内に閉じたルーティングを行うことも可能である。
【0127】
しかしながら、当業者には既知のように、アドホックネットワークではホップ数が増えるほど通信品質は劣化するため、できる限りアドホックネットワーク内での無線リンクを減らして、インターネットを経由したルートを通った方が通信品質は良好となる。
【0128】
したがって、上記実施例のようにできる限りインターネットを経由させようとすることは、好ましい実施形態であると言える。
【実施例3】
【0129】
次いで、図15及び16を用いて、本発明の更に別の一実施例(実施例3)について説明する。本実施例は、上述の実施例1及び2に共通する変形例であり、採用されるルーティングプロトコルはDSRでもAODVでもよい。
【0130】
上述の実施例1及び2では、グローバル通信用識別子がRREQに付加される以外の点については現行のプロトコルと同様にMANET内でのルーティング処理を行い、それにより発見されたルート上においてインターネットによるショートカットが可能であるか否かを判断できるようにし、可能であればインターネットを経由したルートを採用する、という実施形態であった。
【0131】
本実施例は、これを更に一歩進めて、インターネットによるショートカットを利用可能なMANET内ルートを積極的に探索するものである。
【0132】
具体的には、上述の実施例1及び2では、現行のDSR及びAODVと同様に、受信端末(RREQの宛先ノード)に最初に到着したRREQだけRREP返信処理の対象となり、遅延して到着したRREQは冗長な(すなわち、ホップ数が多い)経路を通って来たものと判断して破棄していたのに対し、本実施例では、MANET内に閉じたルーティングではホップ数が多く、遅延を伴うルートであっても、上述の実施例1又は2に係るようなインターネットを利用したショートカットを利用すれば、ホップ数が削減され、最もホップ数が少ないルートが得られる可能性があることに鑑み、RREQの宛先ノードは、最初のRREQ受信後、所定時間、同じ送信元ノードからの他のRREQの受信を待機するものとする。
【0133】
そして、本実施例では、RREQ受信を上記所定時間待機したRREQの宛先ノードは、最初に受信されたRREQと該所定時間中に受信された遅延RREQとの中から、上述の実施例1及び2のようにインターネットを利用したショートカットを考慮して、最もホップ数が少ないルートを選択する。
【0134】
図15及び16に一例を挙げる。ここで、図15に示すようにアドホック通信端末が点在する通信環境において、送信端末がRREQを受信端末へ向けてフラッディングしたとき、RREQが2つの経路(ルート1、ルート2)で受信端末(宛先ノード)へ到達した場合を考える。また、いくつかの中継ノードはホットスポット(HS)1〜3のエリア内に在圏している。
【0135】
各ルートが経由する端末について図16にまとめる。図16(a)はルート1が経由する端末(ノード)を示し、図16(b)はルート2が経由する端末(ノード)を示す。図示するように、この例では、ルート2の方がホップ数が多い。したがって、通常であれば、ルート2を経由したRREQの方がルート1を経由したものより遅く受信端末に到達するはずである。
【0136】
上述のように、現行のルーティングプロトコルでは、このような遅延して到達したRREQは破棄されることになるが、本実施例では、上記所定時間内であればこのような遅延したRREQもRREP作成の対象となる。
【0137】
上記所定時間内にルート2を経由したRREQのみが受信されたものとすると、受信端末は、次に、最初に受信されたルート1(図16(a))経由のRREQと、ルート2(図16(b))経由のRREQとを比較し、ホップ数が少ない方を選択する段階となる。
【0138】
ただし、本例では、ルート2上にはホットスポットエリア内に位置する中継ノードが2つ以上存在するため、受信端末は、上述の実施例1及び2のようなショートカットを利用することができる、と判断することができる。
【0139】
図15に示す例では、ルート2上で、最も送信端末寄りのホットスポットエリア内に位置するノードは端末Bであり、最も受信端末寄りのホットスポットエリア内に位置するノードは端末Mであることから、図16(b)に示したルート2は、上述の実施例1及び2のような手法を利用して端末B〜端末M間をインターネットによるショートカットさせることにより、図16(c)に示すようなルート2’とすることができる。
【0140】
すると、図示するように、図16(c)に示すインターネットを利用したルート2’では、図16(b)に示すMANET内に閉じたルート2に比して、ホップ数を2ホップ削減することができることがわかる。
【0141】
したがって、本例において、受信端末は、ルート1(図16(a))のホップ数と、ルート2’(図16(c))のホップ数とを比較して、ホップ数のより少ないルート2’をRREP経路に優先的に選択することができる
このように、本実施例では、受信端末(宛先ノード)が従来は破棄していた遅延したRREQを含めて積極的にインターネットによるショートカットが可能なルートを探索することができるため、より少ないホップ数のルートを優先的に経路として使用することができる。
【0142】
なお、本実施例において、上記所定時間は、原則として任意に定めることができるが、経路探索に要する時間が過度に長くならないように、適度な時間長に設定されるべきである。
【0143】
例えば、最初に受信されたRREQの経路のホップ数に基づいて、遅延した宛先ノードに到達したRREQのMANET内に閉じたルートのホップ数が最初に受信されたRREQ経路のホップ数の所定数分の1のホップ数以内であれば許容するようにしてもよく、或いは、最初に受信されたRREQの経路のホップ数とは無関係に、予め設定された所定ホップ数までの遅延を許容してもよい。
【0144】
また、ホップ数ではなく遅延時間を基準とし、最初にRREQから受信されてから所定時間だけ待機するようにしてもよい。または、受信端末は最初に受信されたRREQが送信端末により送信されてから受信端末により受信されるまでに要した時間のプラス所定パーセントまでの時間が経過するまで待機するようにしてもよい。ただし、この場合、送信端末がRREQ送信時にRREQに送信時刻をタイムスタンプすることが必要となる。
【0145】
また、常に上記所定時間待機するものとせず、例えば、該所定期間の途中でグローバル通信用識別子を2つ以上含んだ(すなわち、インターネットによるショートカットが可能な経路を持つ)RREQが受信されたときには、その時点で遅延したRREQの受信待機を中止するようにしてもよい。
【0146】
また、ここでは、受信端末は、最初にRREQが受信されてから所定時間他のRREQの受信を待機するものとし、受信された1以上のRREQの中から最もホップ数が少ないルートをRREP返信対象に選択するものとしたが、ホップ数に代えて又は加えて、通信帯域や遅延時間などのパラメータを考慮してルートを選択してもよい。これは、例えば、PINGコマンドを利用してスループットやRTT(Round Trip Time)などを測定することにより得られる。
【0147】
さらに、本実施例の好ましい変形例として、インターネットによるショートカットが可能なルートをより積極的に探索するために、宛先ノードが遅延したRREQを待機するだけでなく、各中継ノードがRREQを転送する際に処理済みのRREQであってもグローバル通信用識別子を含んだRREQについては破棄せずに、最初に受信されたRREQと同様に転送処理を行うようにしてもよい。これにより、インターネットによるショートカットが可能なルートを経由したRREQが受信端末に到達する可能性を高めることができ、インターネット経由の経路の利用を促進することができる。
【0148】
以上、本発明の実施例1〜3について具体例を挙げながら説明した。しかしながら、ここに説明及び図示した実施例はあくまで例示に過ぎず、本発明はこれらに限定されるものではない。
【0149】
例えば、上記実施例1〜3では、アドホックネットワークの無線リンクよりも通信品質が良いと想定される有線網の一例としてインターネットを挙げたが、本発明はこれに限られず、インターネット以外の有線網を利用することも当然可能である。
【0150】
また、上記実施例1〜3では、各端末が有線網へ無線LANを利用して有線網に接続するものとしたが、本発明はこれに限られず、例えばDSRC(dedicated short range communication;挟域通信)などの他の通信規格を利用することも当然可能である。
【0151】
また、上記実施例1〜3では、RREQパケット構成などをリアクティブ型のルーティングプロトコルであるDSR又はAODVが用いられるものとして説明したが、本発明はこれらに限定されるものではなく、他のリアクティブ型プロトコルであっても、或いは、プロアクティブ型プロトコルであっても、利用することができる。
【0152】
プロアクティブ型のルーティングプロトコルが用いられる場合、各ノード区間の経路情報が常にやりとりされているため、各端末はホットスポットエリア内に位置する端末まで何ホップの距離にあるかを把握している。そこで、プロアクティブ型ルーティングプロトコルが用いられる場合には、上記実施例1〜3の変形例として、各端末が、自局がホットスポットエリア内に位置すれば上記実施例1〜3と同様に自局のグローバル通信用識別子をRREQに追記すると共に、自局がホットスポットエリア内に位置しなければ自局が持つ周辺ノード情報から自局からも最も近いホットスポットエリア内に位置する端末に到達するまでのホップ数をRREQに追記するようにしてもよい。これにより、インターネットによるショートカット可能なルートをより一層積極的に探索することができる。
【0153】
また、上記実施例1〜3では、一部の中継ノードがホットスポットエリア内に位置する場合について述べたが、上記説明を読んだ当業者には明らかなように、本発明はRREQ送信元ノード及び/又はRREQ宛先ノードがホットスポットエリア内に位置する場合にも等しく適用することが可能である。ただし、当業者には明らかなように、送信元ノードがホットスポットエリア内に位置する場合であっても、当然、RREQはMANET内のみにフラッディングされる。
【0154】
また、現行のルーティングプロトコルでは、ノードの移動や電源オフなどによりルートが切れた場合に再度経路探索が行われるようになっているが、本発明においては、いずれの実施例及び変形例においても、ルート切れの場合に加えて、更に、送信元ノード、ルートに選ばれた中継ノード、及び宛先ノードのいずれかがホットスポットエリア内に入ったとき及びホットスポットエリアから外へ出たときにも経路が再探索されることが好ましい。なぜなら、新たなインターネットを利用した経路により、ホップ数を更に削減して通信品質を向上させることが可能となる可能性があるためである。
【0155】
また、本発明の適用に合わせたインフラ側の工夫として、アドホックネットワークによってインターネットを利用したショートカットに頻繁に利用されるホットスポットエリア(のAP)間をトンネリング(tunneling)やVPN(Virtual Private Network;仮想閉域網)などの技術を利用して仮想上一体化しても有益的である。これにより、一方のホットスポットエリア内でブロードキャストされたRREQは他方のホットスポットエリア内にもブロードキャストされたことになり、MANET内端末識別子の処理のみで有線網を利用したショートカットが可能となる。
【0156】
さらに、上記実施例及び変形例においては、ルーティング判定の指標としてホップ数を例に挙げたが、当業者には明らかなようにこれは一例に過ぎず、例えば通信帯域や遅延時間などの通信品質に関連する指標などの他の指標を用いてルーティングの判定を行うことも可能である。
【産業上の利用可能性】
【0157】
本発明は、アドホックネットワークに利用できる。上述のように、用いられるルーティングプロトコルは問わない。
【0158】
また、アドホック通信端末の種類も問わない。ノードとなる端末は、携帯電話であってもよく、PDA(Personal Digital Assistant;携帯情報端末)であってもよく、又は、車両に搭載された通信装置であってもよい。
【0159】
複数の車両に搭載された通信装置により車車間通信としてアドホックネットワークが構築されている場合、特に本発明に係るルーティング方法を適用すると有益的である。
【0160】
車車間通信の場合、ノードとなる各車両は、ほぼ道路上のみに存在すると言えるため、ルートが探索しやすい。また、車両運転中は、数km前方の交通状況・道路状況を知りたい、というニーズがあると考えられるため、一時的にアドホックネットワークを張って情報を収集する、といった使い方が考えられる。
【0161】
さらに、本発明を車車間通信に適用した場合の最大の利点の1つは、交差点をホットスポットにすることによって、任意の交差点まで有線網によってショートカットできる点である。これは、例えば交差点に設置された信号機や一時停止の標識などに付随して例えば無線LANのビーコンを送出するAPを設置することによって、比較的容易に、多くのノードの滞在・通過が見込めるエリア(交差点近傍)を確実にホットスポットエリアとすることができ、本発明に係るルーティングを利用した通信品質向上の促進が見込まれる。
【図面の簡単な説明】
【0162】
【図1】アドホック通信端末が点在し、一部の端末がホットスポットエリア内にいる通信環境の一例を示す図である。
【図2】本発明の一実施例におけるアドホック通信端末の概略構成図である。
【図3】本発明の一実施例においてRREQを中継するノードによってRREQに追記される自局情報を示す図である。
【図4】図1の通信環境においてRREQが送信端末から受信端末へ到達した際に経由した経路の一例を示す図である。
【図5】現行DSRプロトコルに準拠し、図4の経路において受信端末に到達したRREQに記述された経路情報を示す図である。
【図6】本発明の一実施例により拡張されたDSRプロトコルに準拠し、図4の経路において受信端末に到達したRREQに記述された経路情報を示す図である。
【図7】本発明の一実施例により拡張されたDSRプロトコルに準拠し、図6のRREQに対して作成されたRREPに記述された経路情報を示す図である。
【図8】図4の場合に、現行DSRプロトコルにより確立されるルートと、本発明の一実施例により拡張されたDSRプロトコルにより確立されるルートとを比較する図である。
【図9】本発明の一実施例において各端末において行われる受信したRREQに対する処理の流れを示すフローチャートである。
【図10】本発明の別の一実施例により拡張されたAODVプロトコルに準拠したRREQのパケット構造を示す図である。
【図11】本発明の別の一実施例により拡張されたAODVプロトコルに準拠し、図4の経路において受信端末に到達したRREQのパケット構造を示す図である。
【図12】本発明の別の一実施例により拡張されたAODVプロトコルに準拠したRREPのパケット構造を示す図である。
【図13】本発明の別の一実施例により拡張されたAODVプロトコルに準拠し、図4の経路において受信端末により返信されるRREPのパケット構造を示す図である。
【図14】本発明の別の一実施例において各端末において行われる受信したRREQに対する処理の流れを示すフローチャートである。
【図15】RREQが送信端末から受信端末へ到達した際に経由した2つの経路の一例を示す図である。
【図16】図15の場合に、現行のルーティングプロトコルにより確立されるルートと、本発明の更に別の一実施例に係るルーティングプロトコルにより確立されるルートとを比較する図である。
【符号の説明】
【0163】
200 アドホック通信端末
201 送受信部
202 パケット転送部
203 ルーティングテーブル
204 ルーティング用パケット処理部
205 アドレス格納部
【特許請求の範囲】
【請求項1】
アドホックネットワークにおけるルーティング方法であって、
ルートリクエストを送信又は転送するノードは、自局が外部の有線網と通信接続している場合、該有線網における自局の識別子を前記ルートリクエストに付加して送信又は転送する、ことを特徴とするアドホックネットワークにおけるルーティング方法。
【請求項2】
請求項1記載のアドホックネットワークにおけるルーティング方法であって、
前記ルートリクエストの宛先ノードは、受信したルートリクエストに2以上の前記有線網における識別子が含まれていた場合、これら2以上の識別子のうちルート上最も送信元ノードに近いノードを表す1つの識別子と最も宛先ノードに近いノードを表す1つの識別子とを用いて、これら2つの識別子が表すノード間は前記有線網を経由する経路を採用したルートリプライを作成する、ことを特徴とするアドホックネットワークにおけるルーティング方法。
【請求項3】
請求項2記載のアドホックネットワークにおけるルーティング方法であって、
前記ルートリクエストの宛先ノードは、アドホックネットワーク内のみでルーティングした場合に前記2つの識別子が表すノード間に所定数以上のホップ数が存在する場合のみ、これら2つの識別子が表すノード間は前記有線網を経由する経路を採用したルートリプライを作成する、ことを特徴とするアドホックネットワークにおけるルーティング方法。
【請求項4】
請求項3記載のアドホックネットワークにおけるルーティング方法であって、
ルートリクエストの宛先ノードは、
最初のルートリクエストを受信してから所定期間、他の経路を経由した同じ送信元ノードからのルートリクエストの受信を待機し、
前記所定期間内に同じ送信元ノードから1以上のルートリクエストが受信された場合、前記最初のルートリクエスト及び前記所定期間中に受信されたルートリクエストのうち2以上の前記有線網における識別子が含まれているルートリクエストについてはこれら2つの識別子が表すノード間は前記有線網を経由するものとして、各ルートリクエストの経路のホップ数を比較し、最もホップ数が少ない経路を有するルートリクエストに対してルートリプライを作成する、ことを特徴とするアドホックネットワークにおけるルーティング方法。
【請求項5】
請求項4記載のアドホックネットワークにおけるルーティング方法であって、
ルートリクエストの宛先ノードは、
2以上の前記有線網における識別子が含まれているルートリクエストが受信されたときに前記他の経路を経由した同じ送信元ノードからのルートリクエストの受信の待機を終了する、ことを特徴とするアドホックネットワークにおけるルーティング方法。
【請求項6】
請求項4又は5記載のアドホックネットワークにおけるルーティング方法であって、
受信したルートリクエストを転送するノードは、受信したルートリクエストに前記有線網における識別子が含まれている場合、その受信したルートリクエストが既に転送済みのルートリクエストであっても破棄せずに初めて受信したルートリクエストと同様に転送する、ことを特徴とするアドホックネットワークにおけるルーティング方法。
【請求項7】
請求項4乃至6のいずれか一項記載のアドホックネットワークにおけるルーティング方法であって、
各ノードは、自局周辺の前記有線網と通信接続しているノードを探索し、存在する場合、ルートリクエストを送信又は転送する際に自局からその自局周辺の前記有線網と通信接続しているノードまでのホップ数を該ルートリクエストに付加する、ことを特徴とするアドホックネットワークにおけるルーティング方法。
【請求項1】
アドホックネットワークにおけるルーティング方法であって、
ルートリクエストを送信又は転送するノードは、自局が外部の有線網と通信接続している場合、該有線網における自局の識別子を前記ルートリクエストに付加して送信又は転送する、ことを特徴とするアドホックネットワークにおけるルーティング方法。
【請求項2】
請求項1記載のアドホックネットワークにおけるルーティング方法であって、
前記ルートリクエストの宛先ノードは、受信したルートリクエストに2以上の前記有線網における識別子が含まれていた場合、これら2以上の識別子のうちルート上最も送信元ノードに近いノードを表す1つの識別子と最も宛先ノードに近いノードを表す1つの識別子とを用いて、これら2つの識別子が表すノード間は前記有線網を経由する経路を採用したルートリプライを作成する、ことを特徴とするアドホックネットワークにおけるルーティング方法。
【請求項3】
請求項2記載のアドホックネットワークにおけるルーティング方法であって、
前記ルートリクエストの宛先ノードは、アドホックネットワーク内のみでルーティングした場合に前記2つの識別子が表すノード間に所定数以上のホップ数が存在する場合のみ、これら2つの識別子が表すノード間は前記有線網を経由する経路を採用したルートリプライを作成する、ことを特徴とするアドホックネットワークにおけるルーティング方法。
【請求項4】
請求項3記載のアドホックネットワークにおけるルーティング方法であって、
ルートリクエストの宛先ノードは、
最初のルートリクエストを受信してから所定期間、他の経路を経由した同じ送信元ノードからのルートリクエストの受信を待機し、
前記所定期間内に同じ送信元ノードから1以上のルートリクエストが受信された場合、前記最初のルートリクエスト及び前記所定期間中に受信されたルートリクエストのうち2以上の前記有線網における識別子が含まれているルートリクエストについてはこれら2つの識別子が表すノード間は前記有線網を経由するものとして、各ルートリクエストの経路のホップ数を比較し、最もホップ数が少ない経路を有するルートリクエストに対してルートリプライを作成する、ことを特徴とするアドホックネットワークにおけるルーティング方法。
【請求項5】
請求項4記載のアドホックネットワークにおけるルーティング方法であって、
ルートリクエストの宛先ノードは、
2以上の前記有線網における識別子が含まれているルートリクエストが受信されたときに前記他の経路を経由した同じ送信元ノードからのルートリクエストの受信の待機を終了する、ことを特徴とするアドホックネットワークにおけるルーティング方法。
【請求項6】
請求項4又は5記載のアドホックネットワークにおけるルーティング方法であって、
受信したルートリクエストを転送するノードは、受信したルートリクエストに前記有線網における識別子が含まれている場合、その受信したルートリクエストが既に転送済みのルートリクエストであっても破棄せずに初めて受信したルートリクエストと同様に転送する、ことを特徴とするアドホックネットワークにおけるルーティング方法。
【請求項7】
請求項4乃至6のいずれか一項記載のアドホックネットワークにおけるルーティング方法であって、
各ノードは、自局周辺の前記有線網と通信接続しているノードを探索し、存在する場合、ルートリクエストを送信又は転送する際に自局からその自局周辺の前記有線網と通信接続しているノードまでのホップ数を該ルートリクエストに付加する、ことを特徴とするアドホックネットワークにおけるルーティング方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【公開番号】特開2006−229332(P2006−229332A)
【公開日】平成18年8月31日(2006.8.31)
【国際特許分類】
【出願番号】特願2005−37951(P2005−37951)
【出願日】平成17年2月15日(2005.2.15)
【出願人】(000003207)トヨタ自動車株式会社 (59,920)
【出願人】(502087460)株式会社トヨタIT開発センター (232)
【Fターム(参考)】
【公開日】平成18年8月31日(2006.8.31)
【国際特許分類】
【出願日】平成17年2月15日(2005.2.15)
【出願人】(000003207)トヨタ自動車株式会社 (59,920)
【出願人】(502087460)株式会社トヨタIT開発センター (232)
【Fターム(参考)】
[ Back to top ]