(57)【要約】【課題】本発明は、高効率にデータを伝送できる通信装置を提供することを目的とする。【解決手段】本発明は、マルチホップ通信装置がデータパケットを送信する際に、該データパケットの送信先として直後のホップノードに対してデータパケットを送信すると共に、2ホップ以上先のノードに対してもデータパケットを送信するパケット送信手段と、直前ホップノードから送信されたデータパケットを受信した際に該データパケットを受信したことを直前ホップノードに対して知らせるためのACKを含むパケットを直前ホップノードに対して返信するACK送信手段と、直前ホップノードよりも前のノードからパケットを受信した際にACKを含むパケットの送信よりも早いタイミングで、データパケットを受信したことを直前ホップノードよりも前のノードおよび直前ホップノードに対して知らせるためのACK-Fを含むパケットを返信するACK-F送信手段を備えることを特徴とする通信装置を提供する。【選択図】      図10
2009212865.tif 000002
【特許請求の範囲】
【請求項１】
マルチホップネットワークのための通信装置において、
前記マルチホップ通信装置がデータパケットを送信する際に、該データパケットの送信先として直後のホップノードに対してデータパケットを送信すると共に、2ホップ以上先のノードに対してもデータパケットを送信するパケット送信手段と、  直前ホップノードから送信されたデータパケットを受信した際に、該データパケットを受信したことを前記直前ホップノードに対して知らせるためのACKを含むパケットを、前記直前ホップノードに対して返信するACK送信手段と、  前記直前ホップノードよりも前のノードからパケットを受信した際に、前記ACKを含むパケットの送信よりも早いタイミングで、前記データパケットを受信したことを前記直前ホップノードよりも前のノードおよび前記直前ホップノードに対して知らせるためのACK-Fを含むパケットを返信するACK-F送信手段と、
を備えることを特徴とする通信装置。
【請求項２】
前記マルチホップネットワークのルーチングプロトコルがAODVであり、
ルーチングを行うためのパケットであるRREQおよびRREPを送信するルーチングパケット送信手段を備え、
前記AODVのRREQには、該RREQを転送したノードよりも前のホップのノードのアドレス情報を記述する領域を含み、前記ルーチングパケット送信手段は、該領域に該アドレス情報を記述し、
前記AODVのRREPには、該RREPを転送したノードよりも前のホップのノードのアドレス情報を記述する領域を含み、前記ルーチングパケット送信手段は、該領域に該アドレス情報を記述し、
前記AODVのルーチングテーブルには、該ルーチングテーブルを有するノードから2ホップ先のノードのアドレス情報を記述する領域を含み、前記ルーチングパケット送信手段は、該領域に該アドレス情報を記述し、
前記データパケットのMACヘッダには、該データパケットを送信するノードから2ホップ以上先のノードを指定するための領域を含み、前記パケット送信手段は、該領域を参照して、2ホップ以上先のノードに対してもデータパケットを送信する、
請求項1に記載の通信装置。
【請求項３】
前記マルチホップネットワークのルーチングプロトコルがDSRであり、
前記データパケットには、DSRヘッダ内のルーチングテーブルの自己ノードから2ホップ以上先のノードを指定するための領域を含み、前記パケット送信手段は、該領域を参照して、2ホップ以上先のノードに対してもデータパケットを送信する、
請求項1に記載の通信装置。
【請求項４】
マルチホップネットワークのための通信方法において、
前記マルチホップネットワークのデータパケットの送信の際に、該データパケットの送信先として直後のホップノードに対してデータパケットを送信すると共に、2ホップ以上先のノードに対してもデータパケットを送信するパケット送信工程と、
直前ホップノードから送信されたデータパケットを受信した際に、該データパケットを受信したことを前記直前ホップノードに対して知らせるためのACKを含むパケットを、前記直前ホップノードに対して返信するACK送信工程と、
前記直前ホップノードよりも前のノードからパケットを受信した際に、前記ACKを含むパケットの送信よりも早いタイミングで、前記データパケットを受信したことを前記直前ホップノードよりも前のノードおよび前記直前ホップノードに対して知らせるためのACK-Fを含むパケットを返信するACK-F送信工程と、
を含む通信方法。
【請求項５】
マルチホップネットワークのための通信処理をコンピュータに行わせるプログラムにおいて、
前記マルチホップネットワークのデータパケットの送信の際に、該データパケットの送信先として直後のホップノードに対してデータパケットを送信すると共に、2ホップ以上先のノードに対してもデータパケットを送信するパケット送信工程と、
直前ホップノードから送信されたデータパケットを受信した際に、該データパケットを受信したことを前記直前ホップノードに対して知らせるためのACKを含むパケットを、前記直前ホップノードに対して返信するACK送信工程と、
前記直前ホップノードよりも前のノードからデータパケットを受信した際に、前記ACKを含むパケットの送信よりも早いタイミングで、前記データパケットを受信したことを前記直前ホップノードよりも前のノードおよび前記直前ホップノードに対して知らせるためのACK-Fを含むデータパケットを返信するACK-F送信工程と、
を含むプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信装置および通信方法、並びにプログラムに関する。より詳細には、本発明は、高信頼・高効率マルチホップネットワークのための通信装置および通信方法に関する。
【背景技術】
【０００２】
近年の無線通信技術の発達、並びに無線端末の小型化および高性能化により、無線通信をさまざまなユビキタスデバイスに応用する動きが加速している。このような状況において、インフラストラクチャに依存せずに、無線端末のみによってネットワークを構築して通信を行うアドホックワイヤレスネットワークの研究が活発化している。アドホックワイヤレスネットワークがセンサなどの小さなデバイスで構成される場合、バッテリによる送信電力には限界がある。このため、無線端末間で互いの電波が届かない場合、通信可能な範囲内にある端末を中継することによってデータを目的の端末にマルチホップ伝送する。このとき、限られた電力で長時間動作させるために省電力化が求められる。また、多くの端末を介する場合は、伝送遅延が発生しやすいが、これを軽減する必要がある。したがって、アドホックワイヤレスネットワークの技術面での課題は、ネットワーク全体としてマルチホップ伝送の性能を如何に向上させることができるかにある。この意味で、「マルチホップワイヤレスネットワーク技術」の研究が重要である。
【０００３】
アドホックネットワークを構築するにあたり、中継端末(以下、ノード)の経由の様式を決定する必要がある。これをルーチングといい、このためのプロトコルをルーチングプロトコルという。ルーチングプロトコルには、AODV(Ad-hoc
on Demand Vector)（非特許文献1）およびDSR（Dynamic Source Routing）（非特許文献2）などがある。ルーチングプロトコルは、主に3つのタイプに分けられ、常に経路を維持しているプロアクティブ型、経路の要求が送信から経路を探索するリアクティブ型、両者を組み合わせたハイブリッド型がある。アドホックネットワークの研究では、ルーチングプロトコルの研究が非常に盛んに行われている。例えば、AODVの拡張によって高信頼化を図った経路バイパス法の提案がされている（非特許文献3）。
【０００４】
マルチホップワイヤレスネットワークの応用として、ワイヤレスセンサネットワーク（WSN）がある。WSNでは、マルチホップ中継を行うことにより、広域に分散しているセンサノードが計測したデータを集約することができる。WSNでは、ノードが移動しない場合も多い。このような場合、ノードの移動に対するルーチングの変更は必要ない。しかし、フェージングなどの電波環境の時間的な変化への対応および長期にわたって計測できるように、省電力性のルーチング法が求められる。
【０００５】
ここで、上記AODVについて、さらに詳細に説明する。AODVは、リアクティブ型のルーチングプロトコルである。これは、1994年に発案され、2003年にRFC3561として実験的に標準化されている。このプロトコルは、ユニキャスト、マルチキャスト、ブロードキャストをサポートしている。また、AODVは、各ノードがルータとして、終点アドレスに基づいて次ホップを決定する方式を採用している。このため、データを送信する際のパケットヘッダが大きくならず、パケット送信の効率が良いとされている。
【０００６】
AODVでは、経路を発見するために、送信ノードがRREQ（Route REQuirement）をブロードキャストする。このRREQに含まれる情報は、図1の通りである。RREQを受信したノードは、RREQに記載されている送信先ノードのIPアドレスを参照する。そして、自分のIPアドレスで無い場合は、これを再度ブロードキャストする。これは、RREQが送信先ノードにたどり着くまで繰り返される。この過程で、中継ノードが同じRREQを2度受け取った場合は、これを破棄する。送信先ノードがRREQを受け取った場合は、RREP(Route
REPly)を作成して、RREQが送られてきたノードに対してユニキャストする。RREPに含まれる情報は、図2の通りである。このとき、RREPの送信ノードには、RREQの送信ノードが指定され、このアドレスに向けて送信が行われる。RREPがRREQの送信ノードに到達したときにルートが完成し、データパケットの送信が行われる。
【０００７】
AODVでは、各ノードがルーチングテーブルを保持している。このルーチングテーブルには、複数のエントリが存在し、１つのエントリの情報は、図4の通りである。エントリは、RREQおよびRREPを受け取ったときに作成される。RREQを受け取ったときは、送信ノードを送信先ノードとして、RREQを自分に送信したノードを次ホップノードとする。このエントリは、RREPを受け取ったときに次ホップノードを決定するために利用される。RREPを受け取ったときは、RREPの送信先フィールドに指定されているノードを送信先アドレスとし、RREPを送信してきたノードを次ホップノードとする。これは、データパケットを送信する際に利用される。データパケットを送信すると、各ノードは、IPヘッダに書かれている送信先ノードを参照し、自身が保持するルーチングテーブルのうち、それに合致するエントリを見つけて、次ホップノードを決定する。また、各エントリには、有効時間があり、最後に該当する経路を使用した通信を行ってからの有効時間が過ぎるか、その経路が使えなくなったと判断されたときに、この経路は無効となる。
【０００８】
次に、上記DSRについて、さらに詳細に説明する。DSRは、リアクティブ型のルーチングプロトコルである。1998年に発案され、2007年にRFC4728に実験的に標準化されている。ユニキャスト、マルチキャスト、ブロードキャストをサポートしている。DSRは、始点経路制御方式を採用しており、送信ノードが送信先ノードまでの経路を把握し、これをパケットヘッダに載せて送信する。この情報は、IPヘッダとトランスポートヘッダとの間にあるDSRヘッダと呼ばれる部分に格納される。また、各ノードは、自身に来たデータのDSRヘッダを見て、自分のアドレスが指定されていた場合にパケットを転送する。送信ノードが全ての経路を把握することができるため、経路内にループする箇所が存在する場合も容易に検出することができる。しかし、経由するノードの数が多くなった場合は、DSRヘッダが大きくなってしまい、パケット転送効率が下がる可能性がある。
【０００９】
DSRでは、始点経路の自動短縮を行うことがある。データパケットを受信したノードがDSRヘッダに書かれた始点経路情報を参照したときに、自分自身のアドレスが指定され、かつ直前ホップノードから送られていない場合は、経路の短縮が可能になると判断し、RREPを送信ノードに送るシステムである。このRREPは、RREQの受信無しで発信されるので無償RREPと呼ばれる。この無償RREPを受けた送信ノードは、次に送るパケットからこの短縮された経路を用いることができ、効率よくデータパケットを送信できると考えられる。
【００１０】
802.11無線LANのMAC(Media Access Control)（非特許文献4）では、定義されたMACフレームがある。この構造を図3に示す。このMACフレームには、データの送信を行う自ノードのMACアドレスと次ホップノードのMACアドレスとが記録されている。次ホップノードでないノードが送信されたデータを受信した場合、送信処理を行わずに破棄する。次ホップノードのみがMACヘッダをはずしたデータパケットをネットワーク層に渡す処理を行う。
【００１１】
経路バイパス法（非特許文献3）は、経路の一部が切断されたときにバイパス経路を提供する手法である。通常のAODVにおける経路発見の場合と同様に、RREQおよびRREPの送受信が行われる。そして、RREPの返送およびACK（ACKnowledgement）送信時に、これをAODVが選出した経路周辺のノードも傍受して、バイパス経路として機能できるよう準備する。ノード配置の例およびメッセージのやり取りのタイムチャートを図5および図6に示してある。データパケットが送信されると、バイパス経路として使用される可能性のあるノードは、このデータパケットを傍受して一時的にバッファする。任意のリンクが一時的に途切れたときに、この途切れたリンク周辺にいるノードがバッファしているデータパケットを次ホップノードに送信することにより、転送遅延を減らすことができる。
【非特許文献１】http://ietfreport.isoc.org/all-ids/draft-ietf-manet-aodv-13.txt
【非特許文献２】http://www.ietf.org/rfc/rfc4728.txt
【非特許文献３】長尾研一，山尾泰，“アドホックネットワークにおける高信頼伝送のための環境認識型経路バイパス法”，信学技法，RCS2007-56，pp.19-23，August，2007
【非特許文献４】守倉正博，久保田周治，“改訂版802.11高速無線LAN教科書”，インプレスR&D。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
上記のような従来方式のAODVでは、一度決められたルートが各ノードに保存される。データパケットは、このルートが無効になるまで、この決められた経路を通って運ばれる。しかし、ルート作成の際に最適であったルートは、データパケット送信の際に、フェージングなどにより最適ではなくなっていることがある。逆に、データパケット送信の際に、一時的に伝搬環境が良好な状態になることもある。このような場合に、さらに先のノードがデータパケットを受け取れる状況が発生すれば、経路をより短縮できる可能性がある。
【００１３】
また、DSRには、経路を短縮する機能がある。しかし、DSRの経路始点制御メッセージをやりとりしなければならず、経路の変更に時間を要するため、瞬間的に電波の強さが変化した場合等に対応できないという問題がある。
【００１４】
本発明は、高効率マルチホップワイヤレスネットワークの構築をめざし、高効率にデータを伝送できるルーチング法を提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明は、アドホックワイヤレスネットワークにおけるマルチホップ伝送の高効率化を目指し、マルチホップ経路の決定のためのルーチング技術に焦点をあて、新規経路飛び越し法および該方法を利用した新規通信装置を提供する。
【００１６】
すなわち、本発明は、マルチホップネットワークのための通信装置において、前記マルチホップ通信装置がデータパケットを送信する際に、該データパケットの送信先として直後のホップノードに対してデータパケットを送信すると共に、2ホップ以上先のノードに対してもデータパケットを送信するパケット送信手段と、直前ホップノードから送信されたデータパケットを受信した際に、該データパケットを受信したことを前記直前ホップノードに対して知らせるためのACKを含むパケットを、前記直前ホップノードに対して返信するACK送信手段と、前記直前ホップノードよりも前のノードからパケットを受信した際に、前記ACKを含むパケットの送信よりも早いタイミングで、前記データパケットを受信したことを前記直前ホップノードよりも前のノードおよび前記直前ホップノードに対して知らせるためのACK-Fを含むパケットを返信するACK-F送信手段とを備えることを特徴とする通信装置を提供する。
【００１７】
また、本発明は、前記マルチホップネットワークのルーチングプロトコルがAODVであり、ルーチングを行うためのパケットであるRREQおよびRREPを送信するルーチングパケット送信手段を備え、前記AODVのRREQには、該RREQを転送したノードよりも前のホップのノードのアドレス情報を記述する領域を含み、前記ルーチングパケット送信手段は、該領域に該アドレス情報を記述し、前記AODVのRREPには、該RREPを転送したノードよりも前のホップのノードのアドレス情報を記述する領域を含み、前記ルーチングパケット送信手段は、該領域に該アドレス情報を記述し、前記AODVのルーチングテーブルには、該ルーチングテーブルを有するノードから2ホップ先のノードのアドレス情報を記述する領域を含み、前記ルーチングパケット送信手段は、該領域に該アドレス情報を記述し、前記データパケットのMACヘッダには、該データパケットを送信するノードから2ホップ以上先のノードを指定するための領域を含み、前記パケット送信手段は、該領域を参照して、2ホップ以上先のノードに対してもデータパケットを送信する、上記通信装置を提供する。
【００１８】
また、本発明は、前記マルチホップネットワークのルーチングプロトコルがDSRであり、前記データパケットには、DSRヘッダ内のルーチングテーブルの自己ノードから2ホップ以上先のノードを指定するための領域を含み、前記パケット送信手段は、該領域を参照して、2ホップ以上先のノードに対してもデータパケットを送信する、上記通信装置を提供する。
【００１９】
さらに、本発明は、マルチホップネットワークのための通信方法において、前記マルチホップネットワークのデータパケットの送信の際に、該データパケットの送信先として直後のホップノードに対してデータパケットを送信すると共に、2ホップ以上先のノードに対してもデータパケットを送信するパケット送信工程と、直前ホップノードから送信されたデータパケットを受信した際に、該データパケットを受信したことを前記直前ホップノードに対して知らせるためのACKを含むパケットを、前記直前ホップノードに対して返信するACK送信工程と、前記直前ホップノードよりも前のノードからパケットを受信した際に、前記ACKを含むパケットの送信よりも早いタイミングで、前記データパケットを受信したことを前記直前ホップノードよりも前のノードおよび前記直前ホップノードに対して知らせるためのACK-Fを含むパケットを返信するACK-F送信工程とを含む通信方法を提供する。
【００２０】
さらに、本発明は、マルチホップネットワークのための通信処理をコンピュータに行わせるプログラムにおいて、前記マルチホップネットワークのデータパケットの送信の際に、該データパケットの送信先として直後のホップノードに対してデータパケットを送信すると共に、2ホップ以上先のノードに対してもデータパケットを送信するパケット送信工程と、直前ホップノードから送信されたデータパケットを受信した際に、該データパケットを受信したことを前記直前ホップノードに対して知らせるためのACKを含むパケットを、前記直前ホップノードに対して返信するACK送信工程と、前記直前ホップノードよりも前のノードからデータパケットを受信した際に、前記ACKを含むパケットの送信よりも早いタイミングで、前記データパケットを受信したことを前記直前ホップノードよりも前のノードおよび前記直前ホップノードに対して知らせるためのACK-Fを含むデータパケットを返信するACK-F送信工程とを含むプログラムを提供する。
【発明の効果】
【００２１】
本発明によれば、アドホックワイヤレスネットワークにおけるマルチホップ伝送において、ホップ数を削減することができる。また、本発明によれば、アドホックワイヤレスネットワークにおけるマルチホップ伝送において、転送効率を向上することができる。さらに、本発明によれば、アドホックワイヤレスネットワークにおけるマルチホップ伝送において、無駄な送信を無くすことによって省電力化を図ることができる。
【発明を実施するための最良の形態】
【００２２】
用語説明
本明細書に使用される「送信ノード」とは、データパケットの送信元ノードを意味する。本明細書に使用される「送信先ノード」とは、アドホックワイヤレスネットワークにおけるマルチホップ伝送の最終宛先ノードを意味する。本明細書に使用される「直前ホップノード」とは、データパケット転送の際に、ホップルート上の直前のノードを意味する。したがって、あるノードに対してデータパケットが送信された際に、ホップルートの2ホップ前のノードからデータパケットが送信された場合、該データパケットは、直前ホップノード以外のノードから送信されている。本明細書に使用される「次ホップノード」とは、あるノードからデータパケットを送信する際に、ルーチングテーブルの直後の送信先ノードを意味する。単にパケットと記載した場合、「パケット」には、データパケットとルーチングを行うためのパケットであるRREQおよびRREPとが含まれる。
【００２３】
本発明の通信方法の概要
無線通信では、電波を受信できたノードであれば、そのデータを受け取ることができる。この原理を使用することにより、本発明の通信方法は、マルチホップワイヤレスネットワークにおける「経路飛び越し法」を達成する。
【００２４】
以下の説明では、本発明の通信方法の概要を従来のAODV方式に応用した例について説明する。ノードSからノードDへとデータパケットを送信する場合の位置関係を図７に示す。本発明の通信方法では、データパケットを送信したノード(ノードAとする)が送信したデータを、該データを通常受信するはずの次ホップノード(ノードBとする)、およびさらにノードBの次のノード(ノードCとする)も受信するようにする。このように飛び越しを許容してマルチホップ通信を行うことにより、以下の利点が得られる。  
1.ホップ数が減ることにより、伝送遅延が小さくなる。  
2.ホップ数が減ることにより、送信に消費される電力が節約できる。  
3.無駄な送信が減少するので、他の通信中のノードに与える干渉が減少し、ネットワークのスループットがあがる。
【００２５】
また、以下の説明では、本発明の通信方法についての説明であるが、本発明のプログラムにおいても、同様の工程による処理が行われる。
【００２６】
本発明の通信方法によって経路飛び越しを実現するためには、以下の機能を実現する必要がある。図７において、各ノードは、データパケットを受信した際に、この受信パケットを受信処理するか破棄するかを、MACアドレスを参照して判断する。通常のマルチホップワイヤレスネットワークでは、受信したデータパケット内に自分のアドレスが存在しないときは、基本的にそのパケットを破棄するように処理される。本発明の方法によって経路飛び越しを実現するためには、次ホップであるノードBだけでなく、さらに次のホップのノードであるノードCもノードB宛のアドレスを受信できるようにする必要がある。これは、たとえば以下に記載したように、MACアドレスを含むMACヘッダを拡張することによって行うことができる。
【００２７】
次に、ノードがデータパケットを受信した場合、直前ホップノードに対してデータパケットを受信したことを知らせる必要がある。これは、たとえば以下に記載したように、リンク(MAC層)のACK信号を送信することによって行うことができる。通常のマルチホップワイヤレスネットワークでは、受信したデータパケットを送信したノードに対してACKの返送を行うこととなる。しかし、本発明の方法では、たとえば図7の位置関係において、ノードCがパケットを受信したときに、ノードAに対してACKの返送を行うだけでなく、これをノードBにも傍受させる。ノードAに対するACKの返送を傍受したノードBは、ノードBからノードAに対するACKの送信を抑制するように制御しておく。これにより、ノードBからの無駄な送信を抑止することができる。
【００２８】
また、飛び越し受信の可能なノードをネットワークレイヤに認識させる必要がある。これは、たとえば以下に記載したように、AODVルーチングテーブルを拡張することによって行うことができる。
【００２９】
また、ルーチングテーブルを作成するためには、RREQおよびRREPという制御メッセージが使用される。このメッセージを拡張することによって行うこともできる。このような拡張により、従来の次ホップノードのみならず、さらに次のノードもデータを破棄することなく処理することが可能になる。
【００３０】
MACヘッダの拡張
図7の位置関係において、従来のMACヘッダを本発明の方法に使用したとすると、ノードAが送信ノードのときは、ノードBのみが送信先ノードとなる。したがって、ノードCは、ノードAからのデータパケットを受信できたとしても破棄してしまうこととなる。本発明の方法によって経路飛び越しを実現するためには、MACヘッダに新たに2ホップ先にあるノードの情報を追加する必要がある。このようにMACヘッダを拡張することにより、ノードCがノードAからのデータパケットを受信したときにも処理を行うことができるようになる。たとえば、この2ホップ先のノードの指定を行うためにMACヘッダの最後の部分に「Next
Hop Address」という領域を確保し、ここに2ホップ先のノードについての記述を行うことができる。拡張したMACヘッダの一例を図11に示してある。
【００３１】
リンクACK(ACKnowledgment)のタイミングの拡張
リンクACKは、ノードがデータパケットを受信した際に、直前ホップノードに対してデータを受け取ったことを示すために送られる制御メッセージである。本発明の方法でもこのACKを使用する。しかし、従来のリンクACKでは、図7の位置関係において、ノードBとノードCとがノードAに対して同時にACKを送信してしまい、ACKの衝突が起きる可能性がある。また、ノードBのほうがノードCよりも早くノードAに対してACKを送信してしまうと、ノードAは、ノードCまでデータパケットが送信されたことをノードCからのACKにより確認しているにもかかわらず、ノードBからのACKがノードAに対して無駄に送信されることになる。そこで、ノードCが、通常よりも早いタイミングで（すなわち、ノードBからよりも早いタイミングで）、かつノードAだけでなくノードBに対してもACKを返送することにより、ノードBは、ノードCからACKが送信されたという情報を得ることができる。
【００３２】
上記より、本発明の方法によって経路飛び越しを実現するためには、たとえば通常のACKよりも早いタイミングで返送されるACKを新たに定義することができる。このようなACKを、本明細書において「ACK-F」として定義する。このACK-Fは、パケットを受信したノードから該パケットを送信したノードと直前ノードに対して送信され、かつ通常のACKの送信タイミングよりも前のタイミングで送信される。したがって、ノードBを飛び越してデータパケットが受信されたノードCは、ノードAおよびノードBに対してACK-Fを送信することとなる。このACK-Fを受信したノードBは、ノードBがノードAからのデータパケットの受信に成功していた場合、ノードAに対するACKの送信を中止する。さらに、ノードBからノードCへ無駄にデータパケットを転送することを中止することができる。データパケット、ACKおよびACK-Fの送信の時間の流れを図12に示してある。
【００３３】
ルーチングテーブルの拡張
また、AODVでは、MAC層から受け取ったデータのIPヘッダとルーチングテーブルのエントリとを照らし合わせながら次ホップを決定する。従来のルーチングテーブルのエントリには、2ホップ先のノードのIPアドレスは載っておらず、2ホップ先のノードを特定することができない。本発明の方法によって経路飛び越しを実現するためには、2ホップ先のノードのIPアドレスをはっきりさせるために、たとえばルーチングテーブルのエントリに2ホップ先のIPアドレス情報とを追加することができる。たとえば、AODVルーチングテーブルを拡張する場合、従来のNext
Hopに続いて2 Next Hopとして情報を追加することができる。このように拡張したルーチングテーブルのエントリを図13に示してある。
【００３４】
RREQおよびRREPの拡張
ルーチングテーブルのエントリに記載する内容は、RREQおよびRREPの内容から決定する。従来のRREQおよびRREPから得られる情報は、次ホップノードについての情報のみである。本発明の方法によって経路飛び越しを実現するためには、RREQおよびRREPから2ホップ以上先のノードについての情報を得る必要がある。このRREQおよびRREPの内容に2ホップ以上先のノードについての情報を記載するためには、たとえばこれらのRREQおよびRREPを送信するノードよりも前のホップのアドレス情報を記述する「Previous
Hop Address」という領域を確保することにより行うことができる。この「Previous Hop Address」の情報により、RREQおよびRREPを受信したノードは、RREQに記載されている「Source
IP Address」またはRREPに記載されている「Destination IP Address」宛にデータパケットを送る際に、2ホップ先の情報を知ることができる。RREQおよびRREPの内容を図14および図15に示してある。
【００３５】
本発明の通信方法を実施するための通信装置は、上記拡張を実施することができるいずれの装置であってもよい。特に、マルチホップ通信装置がデータパケットを送信する際に、該データパケットの送信先として直後のホップノードに対してデータパケットを送信すると共に、2ホップ以上先のノードに対してもデータパケットを送信するパケット送信手段と、直前ホップノードから送信されたデータパケットを受信した際に、該データパケットを受信したことを前記直前ホップノードに対して知らせるためのACKを含むパケットを、前記直前ホップノードに対して返信するACK送信手段と、前記直前ホップノードよりも前のノードからパケットを受信した際に、前記ACKを含むパケットの送信よりも早いタイミングで、前記データパケットを受信したことを前記直前ホップノードよりも前のノードおよび前記直前ホップノードに対して知らせるためのACK-Fを含むパケットを返信するACK-F送信手段とを備えることを特徴とする通信装置により、本発明の通信方法を実施することができるであろう。
【００３６】
本発明の通信装置の一つの態様として、図16に装置の構成例を示してある。たとえば、無線送受信処理部161およびアクセス制御部162を含む装置が想定される。アクセス制御部162は、たとえばパケット受信部163、データ処理部164、ACK送信部165およびパケット送信部166を含む。データ処理部164およびパケット送信部166は、請求の範囲におけるパケット送信手段として機能する。データ処理部164およびACK送信部165は、AKC送信手段およびAKC-F送信手段として機能する。  
【００３７】
無線信号として送信された信号は、無線送受信処理部161のアンテナにより受信され、無線受信処理部161により復調などの処理を受ける。復調された信号は、アクセス制御部162のパケット受信部163に入力される。パケット受信部163は、受信したパケットの情報を読み取る。この読み取られたパケットの情報に基づいて、データ処理部164においてパケットの処理がなされる。データ処理部164における処理の結果、パケットをパケット送信部166で処理して無線受信処理部161から次のノードへと送信するか、またはパケットを破棄することとなる。一方、送信されたパケットが自局宛のデータパケットを正常に受信した場合には、データ処理部164は、ACKパケットをACK送信部にて処理して無線受信処理部161を通じてデータパケットの送信元に対してACKを送信するように、処理する。また、データ処理部164は、必要なノードに対するACK-FパケットをACK送信部165にて処理して無線受信処理部161を通じて送信するように、処理する。
【００３８】
また、本発明の通信装置の具体的態様において、IP3層で使用することができる通信装置の一部として、上記手段を備える機器が想定される。一つの態様において、本発明の通信装置が組み込まれた装置には、たとえばルータ、LANカード、コンピュータおよび携帯電話などの種々の機器が含まれる。
【００３９】
図8には、本発明の経路飛び越し法におけるRREQメッセージの処理フローを示してある。図16の装置構成図および図14に示した本発明の方法のRREQの内容を参照しながら、RREQメッセージの処理フローを説明する。各ノードは、無線受信処理部161を通じてパケット受信部163がRREQを受信すると、ステップ801において、データ処理部164がRREQのHop
Countの値を送信されたときの値+1に変更する。
【００４０】
次いで、データ処理部164は、ステップ802において、ノードのRREQ-ID＞送信されてきたRREQのRREQ-IDのときは、このRREQを破棄する処理をする。逆に、ノードのRREQ-ID＜送信されてきたRREQのRREQ-IDのときは、Hop
Countの値を調べる。次いで、ステップ803において、Hop Countの値≧2のときは、ステップ804において、ルーチングテーブル（R-Tbl）（図13）の2
Next Hopに、送信されてきたRREQのPrevious Hop IP Addressを代入する。次いで、ステップ805において、既存のR-Tblを更新する。
【００４１】
また、データ処理部164は、ステップ803においてHop Countの値が1のときは、ステップ805において、直ちに既存のR-Tblを更新する。次いで、ステップ806において、RREQのPrevious
Hop IP AddressにIP-HのSource IP Addressを代入する。次いで、ステップ807において、パケット送信部166がRREQを転送する。
【００４２】
図9には、本発明の経路飛び越し法におけるRREPメッセージの流れを示してある。図16の装置構成図および図15に示した本発明の方法におけるRREPの内容を参照しながら、RREPメッセージの処理フローを説明する。各ノードは、無線受信処理部161を通じてパケット受信部163がRREPを受信すると、ステップ901において、データ処理部164がRREPのHop
Countの値を送信されたときの値+1に変更する。
【００４３】
次いで、データ処理部164は、ステップ902において、ルーチングテーブルのHop
Count＜送信されてきたRREPのHop Countのときは、このRREPを破棄する処理をする。逆に、ルーチングテーブルのHop Count＞送信されてきたRREPのHop
Countのときは、ステップ903において、Hop Countの値を調べる。ステップ903において、Hop Countの値≧2のときは、ステップ904において、ルーチングテーブル（R-Tbl）（図13）の2
Next Hopに、送信されてきたRREPのPrevious Hop Addressを代入する。次いで、ステップ905において、既存のR-Tblを更新する。
【００４４】
また、データ処理部164は、ステップ903においてHop Countの値が1のときは、ステップ905において、直ちに既存のR-Tblを更新する。次いで、ステップ906において、RREPのPrevious
Hop AddressにMACヘッダ（IP-H）のSource Addressを代入する。次いで、ステップ907において、パケット送信部166がRREPを転送する。
【００４５】
また、図10には、データパケット伝送の流れを示してある。図16の装置構成の場合に、ノードAがパケットを送信し、ノードBを経由して、ノードCに転送される際に、ノード、ノードCがノードAからのパケットを傍受する場合を想定する。まず、ノードAがパケットを送信する。次いで、ステップ101において、ノードBのパケット受信部163が送信元ノードからのパケットを受信する。また、ステップ102において、ノードCのパケット受信部163が送信元ノードからのパケットを受信できたときは、データ処理部164がパケットを処理して、ステップ103において、ACK送信部165が通常のACKよりも早いタイミングでACK-FをノードBおよびノードAに送信すると共に、ステップ104において、パケット送信部166がノードBから受信したパケットを次のノードへ送信する。
【００４６】
ステップ105において、上記ノードCからのACK-FをノードBのパケット受信部163が受信できたときは、データ処理部164が、ステップ106においてACK-F
Flag=TRUEと処理して、ステップ107においてノードAからのパケットを廃棄し、ステップ108においてACK-F Flag=FALSEと処理する。
【００４７】
一方、ステップ105において、ノードBがノードCからのACK-Fを受信できなかったときは、データ処理部164が、ステップ109において送信元ノードから受信したパケットをノードBからノードCへ送信するように処理して、パケット送信部166が送信先ノードへの送信処理をする。
【００４８】
図12には、本発明の経路飛び越し法におけるデータ送信のタイムチャートを示してある。ノードAからノードDへパケットを送信する際のタイムチャートを想定すると、ノードAからのパケットをノードBが受信すると共にノードCが傍受したとする。この場合、ノードBからのACKよりも早いタイミングでノードCからACK-Fが送信される。このACK-Fは、ノードAが受信すると共にノードBが傍受する。また、ノードCは、ACK-Fの送信後に受信したパケットをノードDに送信する。
【００４９】
また、上記説明においては、2ホップ先のノードに対して経路飛び越しを行う態様を説明したが、当業者であれば、数ホップ先のノードに対して経路飛び越しを行うこともできることを理解するであろう。たとえば、AODVにおいて、3ホップ先のノードに対して経路飛び越しを行うために、2ホップ先のノードに対して経路飛び越しを行う態様と同様に、MACヘッダの拡張、リンクACKのタイミングの拡張、ルーチングテーブルの拡張、並びにRREQおよびRREPの拡張を行ってもよい。
【００５０】
MACヘッダの拡張の一つの態様において、2ホップ先のノードに対して経路飛び越しを行う場合の「Next
Hop Address」領域に加えて、3ホップ先のノードについての記述を行う「Next Next Hop Address」という領域を確保することができる。同様に、ルーチングテーブルの拡張の一つの態様において、2ホップ先のノードに対して経路飛び越しを行う場合の「2
Next Hop」に加えて、3ホップ先のノードのIPアドレスをはっきりさせるために、「3 Next Hop」として情報を追加することができる。また、RREQおよびRREPの拡張の一つの態様において、RREQおよびRREPの内容に3ホップ以上先のノードについての情報を記載するために、たとえばこれらのRREQおよびRREPを転送するノードよりも2つ前のホップのアドレス情報を記述する「Previous
Previous Hop Address」という領域を確保することができる。さらに、ACKの拡張として、パケットを送信したノードおよび直前ホップノードだけでなく、両者の間のノードに対してもACK-Fを送信してもよい。当業者であれば、このような飛び越しのために必要な拡張は、飛び越しホップ数に応じて、容易に設定することができるであろう。
【００５１】
また、上記説明では、本発明の一つの態様として、AODVにおける経路飛び越しを説明したが、当業者であれば、他のルーチングプロトコルおよび方式においても経路飛び越しを行うことができることを理解するであろう。たとえば、本発明の一つの態様において、DSRにも本発明の通信方法による経路飛び越しを行うことができるであろう。DSRにおける経路飛び越しの一つの態様において、上記AODVの態様と同様に、2ホップ先のノードの指定を行うためにMACヘッダの最後の部分に「Next
Hop Address」という領域を確保し、ここに2ホップ先のノードについての記述を行うことができる。また、DSRにおける経路飛び越しの一つの態様において、上記AODVの態様と同様に、「ACK-F」を定義することができる。一方、DSRでは、DSRヘッダにルートが記載されている。したがって、ルーチングテーブルの拡張、並びにRREQおよびRREPの拡張を行わなくても、経路飛び越しを行うことができるであろう。
【００５２】
本発明の具体的態様において、本発明は、上述した通信方法を実現するソフトウエアのプログラムコードを記録した記憶媒体を、上述した通信装置に供給し、その装置のコンピュータが該プログラムコードを読み出して実行することによっても達成される。したがって、プログラム自体も、本発明の構成し、マルチホップネットワークのデータパケットの送信の際に、該データパケットの送信先として直後のホップノードに対してデータパケットを送信すると共に、2ホップ以上先のノードに対してもデータパケットを送信するパケット送信工程と、直前ホップノードから送信されたデータパケットを受信した際に、該データパケットを受信したことを直前ホップノードに対して知らせるためのACKを含むパケットを、直前ホップノードに対して返信するACK送信工程と、直前ホップノードよりも前のノードからデータパケットを受信した際に、ACKを含むパケットの送信よりも早いタイミングで、データパケットを受信したことを直前ホップノードよりも前のノードおよび直前ホップノードに対して知らせるためのACK-Fを含むデータパケットを返信するACK-F送信工程とを含むプログラムが提供される。
【実施例】
【００５３】
パケット伝送成功率の計算および結果
検討の対象としたノード配置モデルを図17に示してある。さらに理論値計算をする上での条件を表1に示した。
【００５４】
【表１】
2009212865.tif 000003
【００５５】
受信電力をEとする。Eの値が、受信感度レベルEthを超えた電力であるときのデータパケットは、完全に受信したものとする。受信感度レベルEthを超えていない電力であるときのデータパケットは、受信できなかったものとする。パケット伝送成功率Pth(E)は、受信感度レベルEthを超えた電力および受信感度レベルEthを超えていない電力の場合に、それぞれ1および0となる。レイリー分布の式を電力Eの関数PR(E)とする。これにより1ホップにおけるパケット伝送成功率であるPlink(E)は、次式で表現することができる。
【００５６】
【数１】
2009212865.tif 000004
Pth(E)およびPR(E)は、次の式で表される。
【００５７】
【数２】
2009212865.tif 000005
【００５８】
【数３】
2009212865.tif 000006
【００５９】
2ホップする際のパケット伝送成功率を表す式にこれを使用すると、
【００６０】
【数４】
2009212865.tif 000007
となる。
【００６１】
本発明の方法では、従来のAODVが作成した経路と飛び越し経路とのマルチルートになっている。したがって、図17において、ノードAからBへ送信した場合の受信電力をE1、ノードBからCへ送信した場合の電力をE2、および飛び越し経路でノードAからCへ送信した場合の電力をE３とすると、
【００６２】
【数５】
2009212865.tif 000008
と表すことができる。
【００６３】
パケット伝送成功率
上記理論式からパケット伝送成功率を計算し、その結果を図17のグラフに示した。ノードAとBとの距離およびノードBとCとの距離をそれぞれR[m]とし、ノードAとCとによって挟まれるノードBの鋭角側の角度をθとした。グラフの横軸は、通常のAODVで用いられる従来経路の距離である。飛び越し経路を使用した1ホップのパケット伝送成功率および飛び越し経路と従来経路をあわせたパケット伝送成功率を、従来経路の距離を基準としてグラフ化した。θ＝90°および180°の場合を算出した。θの分布は、下に記述したとおり、90°〜180°までの間に多く分布すると考えられる。したがって、パケット伝送成功率は、図18のθ=90°およびθ=180°のカーブの間に多く分布すると考えられる。θ＝180°のときは、ノードA、BおよびCが一直線上に並ぶため、改善効果は小さいが、θ＝90°のときは、改善効果が大きいことが図18の結果からわかる。
【００６４】
θ分布
QualNet3.9.5を使用して、実際にAODVを起動し、各ルートをたどることでθの分布を出した。ノード配置は、ランダム配置であり、ノード数は、25として配置を行った。これによって得られたθの数は、779個であり、その平均は、およそ132°となった。この分布のグラフを図19に示す。グラフを見ると、平均値付近に分布が集中しているのがわかる。また、累積分布のグラフを図20に示す。累積分布が10%、50%および90%となる値は、それぞれおよそ80°、137°および170°であった。したがって、θは、80°以上に多く分布しているといえる。
【００６５】
まとめ
本明細書では、マルチホップネットワークにおいて効率的な伝送を実現するための、経路飛び越し法を提供した。経路飛び越しを可能にするために、リンクACKの拡張、MACヘッダの拡張、ルーチングテーブルの拡張、並びにRREQおよびRREPの拡張を提供した。本発明の方法の効果を確認するために、ノード配置モデルを設定して、3つのノードが作る角度をパラメータとして、レイリーフェージング環境でのパケット伝送成功率を求めた。モデルでの結果から、通常の2ホップの経路と本発明の方法による飛び越し経路とのダイバーシチ効果により、パケット伝送成功率が改善されることが判明した。
【００６６】
本発明の方法および装置の基本となる既存のルーチング方法は、アドホックネットワークのルーチング方法として代表的なAODV(Ad-hoc on Demand Vector)である。AODVで構築された経路には、経路作成途中でのフェージングなどの影響によって最適な経路が作成できない場合や、経路が作成されたときより伝搬状況が一時的に良好となったために、さらに最適な経路が存在する場合などがある。例として，次に中継するノードよりもさらに先のノードがデータパケットを受信できる場合がある。このような場合、経路を一時的に飛び越しすることが考えられる。
【００６７】
本明細書では、レイリーフェージング環境を想定し、本発明の経路飛び越し法の基本検討を行った。3つのノードを二等辺三角形に配置し、パケット伝送成功率を解析した。この解析では、飛び越しを使用した経路とAODVによりあらかじめ構成された経路との二つの経路が使用できるものとした。解析結果は、飛び越しを使用した経路のみの場合は、リンク長が長くなるため、パケット伝送成功率が低いものの、従来の経路と組合せた場合は、パスダイバーシチ効果により、パケット伝送成功率が上がることが判明した。この効果は、3つのノードが作る角度(以下、θとする)に依存し、角度を狭めるほど改善効果があることも判明した。ネットワークシミュレーターにおいて、ランダムにノードを配置させて、AODVによりさまざまな経路を発生させ、θの分布を調べた。この分析の結果、θは、広い範囲に分布し、累積分布が50%になる角度は、137°であった。この結果から、本発明の経路飛び越し法によって、より効率的な経路を提供することができることがわかった。
【図面の簡単な説明】
【００６８】
【図１】従来のAODVのRREQの内容を示す図。
【図２】従来のAODVのRREPの内容を示す図。
【図３】従来のIEEE802.11bのMACヘッダの内容を示す図。
【図４】従来のAODVのルーチングテーブルに含まれる１エントリの内容を示す図。
【図５】従来の経路バイパス法のノード配置例を示す模式図。
【図６】従来の経路バイパス法のタイムチャートおよびメッセージ送信例を示す模式図。
【図７】本発明の飛び越し法のノード配置例を示す模式図。
【図８】本発明の経路飛び越し法のRREQメッセージの処理フローを示す図。
【図９】本発明の経路飛び越し法のRREPメッセージの処理フローを示す図。
【図１０】本発明の経路飛び越し法のパケット伝送の処理フローを示す図。
【図１１】本発明の経路飛び越し法のMACヘッダを示す図。
【図１２】本発明の経路飛び越し法のタイムチャートを示す図。
【図１３】本発明のルーチングテーブルの1エントリを示す図。
【図１４】本発明の経路飛び越し法のRREQの内容を示す図。
【図１５】本発明の経路飛び越し法のRREPの内容を示す図。
【図１６】本発明の装置の構成例を示すブロック図。
【図１７】本発明の経路飛び越し法の理論解析のノード配置例を示す図。
【図１８】本発明の経路飛び越し法のパケット成功率の距離特性を示す図。
【図１９】本発明の経路飛び越し法のθ分布のグラフを示す図。
【図２０】本発明の経路飛び越し法の角度θの累積確率分布を示す図。
【図１】
2009212865.tif 000009
【図２】
2009212865.tif 000010
【図３】
2009212865.tif 000011
【図４】
2009212865.tif 000012
【図５】
2009212865.tif 000013
【図６】
2009212865.tif 000014
【図７】
2009212865.tif 000015
【図８】
2009212865.tif 000016
【図９】
2009212865.tif 000017
【図１０】
2009212865.tif 000018
【図１１】
2009212865.tif 000019
【図１２】
2009212865.tif 000020
【図１３】
2009212865.tif 000021
【図１４】
2009212865.tif 000022
【図１５】
2009212865.tif 000023
【図１６】
2009212865.tif 000024
【図１７】
2009212865.tif 000025
【図１８】
2009212865.tif 000026
【図１９】
2009212865.tif 000027
【図２０】
2009212865.tif 000028