(57)【要約】【課題】本発明は経路確立方法を開示する。【解決手段】宛先ノードまでの経路がソースノードに存在し、かつ当該経路内の中間ノードのエネルギーとトラフィック量とに基づいて、当該経路が有効な経路に決定された場合、当該経路を通じてデータパケットを送信し、そうでない場合、トラフィック量の付けられているRREQをブロードキャストするステップAと、RREQを受信したノードは自分が宛先ノードであるか否かを判断して、宛先ノードである場合、ステップDを実行し、宛先ノードでない場合、ステップCを実行するステップBと、当該中間ノードが有効なノードに決定された場合、当該ノードから宛先ノードまでの有効な経路を探索するステップCと、ソースノードから宛先ノードまでの経路及び当該経路上の各ノードのエネルギーの付けられているRREPをソースノードに返信し、ソースノードはRREP内の経路に従ってデータパケットを送信するステップDとを含む。【選択図】図３
2007325261.tif 000002
【特許請求の範囲】
【請求項１】
経路確立方法であって、
今回伝送するデータパケットに対応する宛先ノードまでの経路がソースノードに存在するか否かを判断して、宛先ノードまでの経路がソースノードに存在し、かつ当該経路内の中間ノードのエネルギーと当該データパケットに対応するトラフィック量とに基づいて、当該経路が有効な経路に決定された場合、当該経路を通じてデータパケットを送信し、そうでない場合、ソースノードが前記トラフィック量の付けられている経路要求パケットRREQをブロードキャストするステップAと、
RREQを受信したノードは自分が宛先ノードであるか否かを判断して、宛先ノードである場合、直接ステップDを実行し、宛先ノードでない場合、ステップCを実行するステップBと、
ノードのエネルギーとデータパケットに対応するトラフィック量とに基づいて、当該中間ノードが有効なノードに決定された場合、当該ノードから宛先ノードまでの有効な経路を探索するステップCと、
ソースノードから宛先ノードまでの経路及び当該経路上の各ノードのエネルギーの付けられている経路応答パケットRREPをソースノードに返信し、ソースノードは前記RREP内の経路に従ってデータパケットを送信するステップDと
を含むことを特徴とする経路確立方法。
【請求項２】
ステップAにおいて前記宛先ノードまでの経路がソースノードに存在するか否かを判断することは、
ソースノードは前記データパケット内の宛先ノードを索引として、自分の経路情報記録で当該宛先ノードに対応する項目を探索して、見付けた場合、宛先ノードまでの経路がソースノードに存在すると判定し、見付けなかった場合、宛先ノードまでの経路がソースノードに存在しないと判定することであることを特徴とする請求項１に記載の経路確立方法。
【請求項３】
前記経路情報記録に中間ノードのエネルギーが含まれる場合、ステップAにおいて前記当該経路が有効な経路に決定されることは、
宛先ノードまでの経路内の各中間ノードのエネルギーが全て今回データパケットの伝送を満足できると確定した場合に、当該経路が有効な経路に判定されることを含むことを特徴とする請求項2に記載の経路確立方法。
【請求項４】
前記ステップAにおいて、前記宛先ノードまでの経路内に、そのエネルギーが今回データパケットの伝送を満足できない中間ノードが存在すると決定された場合、ステップAにおいて前記ソースノードがトラフィック量の付けられているRREQをブロードキャストする操作を実行することを更に含むことを特徴とする請求項3に記載の経路確立方法。
【請求項５】
ステップCにおいて前記当該中間ノードが有効なノードに決定されることは、
当該中間ノードのエネルギーが今回データパケットの伝送を満足できると決定された場合、当該中間ノードが有効なノードに判定されすることであることを特徴とする請求項１に記載の経路確立方法。
【請求項６】
前記ステップCにおいて、当該中間ノードのエネルギーが今回データパケットの伝送を満足できないと決定された場合、前記RREQを捨て、前記ステップBに戻ることを更に含むことを特徴とする請求項5に記載の経路確立方法。
【請求項７】
前記経路情報記録に中間ノードのエネルギーが含まれる場合、ステップCにおいて前記宛先ノードまでの有効な経路を探索することは、
前記中間ノードの経路情報記録で前記宛先ノードまでの経路を探索し、当該経路内各中間ノードのエネルギーが全て今回データパケットの伝送を満足できる場合、当該経路が有効な経路に判定されることであることを特徴とする請求項2に記載の経路確立方法。
【請求項８】
前記ステップCにおいて、前記中間ノードの経路情報記録で宛先ノードまでの経路を見付けなかった場合、当該中間ノードのアドレスとエネルギーの付けられているRREQをブロードキャストし、前記ステップBに戻ることを更に含むことを特徴とする請求項7に記載の経路確立方法。
【請求項９】
ステップCにおいて、前記宛先ノードまでの経路内に、そのエネルギーが今回データパケットの伝送を満足できない中間ノードが存在すると決定された場合、RREQを受信した中間ノードのアドレスとエネルギーの付けられているRREQをブロードキャストし、前記ステップBに戻ることを更に含むことを特徴とする請求項7に記載の経路確立方法。
【請求項１０】
予めエネルギーの下限を設定し、
前記中間ノードのエネルギーが今回データパケットの伝送を満足できると決定されることは、
前記データパケットに対応するトラフィック量に基づいて、当該データパケットの伝送に必要なエネルギーを計算し、
中間ノードのエネルギーと前記データパケットの伝送に必要なエネルギーとの差を計算することによって、前記中間ノードの残存エネルギーを得、
中間ノードの残存エネルギーが前記エネルギーの下限以上であるか否かを判断して、下限以上である場合、中間ノードのエネルギーが今回データパケットの伝送を満足できると判定される、ことを含む
ことを特徴とする請求項3、請求項5又は請求項7に記載の経路確立方法。
【請求項１１】
予め最高エネルギーの消費率を設定し、
前記中間ノードのエネルギーが今回データパケットの伝送を満足できると決定されることは、
前記データパケットに対応するトラフィック量に基づいて、当該データパケットの伝送に必要なエネルギーを計算し、
前記データパケットの伝送に必要なエネルギーと中間ノードのエネルギーとの比を計算し、
計算された比値の各々が前記最高エネルギーの消費率より小さいか否かを判断して、小さい場合、中間ノードのエネルギーが今回データパケットの伝送を満足できると判定される
ことを含むことを特徴とする請求項3、請求項5又は請求項7に記載の経路確立方法。
【請求項１２】
予め最低エネルギーの残存率を設定し、
前記中間ノードのエネルギーが今回データパケットの伝送を満足できると決定されることは、
前記データパケットに対応するトラフィック量に基づいて、当該データパケットの伝送に必要なエネルギーを計算し、
中間ノードのエネルギーと前記データパケットの伝送に必要なエネルギーとの差を計算することによって、中間ノードの剰余エネルギーを取得し、残存エネルギーと対応の中間ノードの初期エネルギ―との比を計算し、
計算された比値の各々が前記最低エネルギーの残存率以上であるか否かを判断して、残存率以上である場合、中間ノードのエネルギーが今回データパケットの伝送を満足できると判定される
ことを含むことを特徴とする請求項3、請求項5又は請求項7に記載の経路確立方法。
【請求項１３】
前記RREQをブロードキャストすることは全確率に従って当該RREQをブロードキャストすることであることを特徴とする請求項1、請求項4、請求項8、又は請求項9に記載の経路確立方法。
【請求項１４】
予めエネルギーレベル及び各エネルギーレベルに対応するブロードキャスト確率を設定し、
前記RREQをブロードキャストすることは、
当該RREQをブロードキャストする中間ノードのエネルギーと前記データパケットの伝送に必要なエネルギーとの差に対応するエネルギーレベルを決定し、又は、前記データパケットの伝送に必要なエネルギーと当該中間ノードのエネルギーとの比に対応するエネルギーレベルを決定し、又は、当該中間ノードのエネルギーと前記データパケットの伝送に必要なエネルギーとの差と、当該中間ノードの初期エネルギーとの比に対応するエネルギーレベルを決定し、
当該エネルギーレベルに対応するブロードキャスト確率に従ってRREQをブロードキャストする
ことであることを特徴とする請求項4、請求項8、又は請求項9に記載の経路確立方法。
【請求項１５】
前記ステップAの前に、ソースノードが、今回伝送しようとするデータパケットを受信し、当該データパケットに対応するトラフィック量と宛先ノードを決定することを更に含むことを特徴とする請求項1に記載の経路確立方法。
【請求項１６】
ステップBにおける前記判断の前に、当該方法は、RREQを受信した中間ノードが前記RREQに基づいて自分の経路情報記録を更新することを更に含むことを特徴とする請求項2に記載の経路確立方法。
【請求項１７】
ステップDにおいて前記ソースノードが前記RREP内の経路に従ってデータパケットを送信する前に、当該方法は、ソースノードが前記RREPに基づいて自分の経路情報記録を更新することを更に含むことを特徴とする請求項2、請求項15、又は請求項16に記載の経路確立方法。
【請求項１８】
ステップBにおいて前記ステップCを実行する前に、当該方法は、前記RREQを受信した中間ノードが初めて当該RREQを受信したか否かを判断して、初めて当該RREQを受信した場合、当該RREQを捨て、ステップBにおける前記判断に戻し、そうでない場合、続いてステップCを実行することを更に含むことを特徴とする請求項1に記載の経路確立方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はルーティング技術に関し、特にノードがルーティング機能を有する無線ネットワークにおける経路確立方法に関する。
【背景技術】
【０００２】
有線ネットワークの束縛から脱却して時間・場所に問わず自由な通信が人々に要望されてきたため、近年、無線ネットワークが速やかに発展されてきた。固定有線インフラストラクチャのない地域での無線通信を可能にするために、アドホック（Ad hoc）ネットワーク技術が時運に応じて現れた。このネットワークにおいて、無線送受器を備える一組の移動ノードによって基地局のないマルチホップの、臨時的な自律ネットワークが構成されている。且つ、各移動ノードはすべてがルータ機能を有しており、データ通信過程においてデータパケットの送受信及び転送の機能を行うことができる。
【０００３】
Ad hocネットワークは固定の有線インフラストラクチャのサポートを必要としないため、伝統的な通信ネットワークに比べて、Ad hocネットワークの自己組織化特徴によって安価で高速なネットワーク配置が可能になり、かつ、マルチホップルートと中間ノードの転送特性とによってネットワークカバー範囲を低下しない上で各端末の送信範囲を減少することが可能になっている。これにより、アンテナと関連送信/受信素子の設計の難しさ及び設備のパワー消耗が低減され、移動端末の小型化、低パワー消耗が可能になっている。また、Ad hocネットワークの安定性、破壊抵抗性によっては軍事通信、災難救助と臨時通信など特定の応用ニーズを満たすことが可能になっている。
【０００４】
図1はAd hocネットワークの構成図である。通常、Ad hocネットワーク内の移動ノードはノードと略称される。図1を参照して、例えば、Ad hocネットワークにはノードA、BとCが含まれ、その中で、ノードBは同時にノードAとノードCのカバー範囲内にあり、ノードAとCのそれぞれは相手ノードのカバー範囲外にある。Ad hocネットワークにおいて、一つのノードのカバー範囲内に位置している他のノードは当該ノードの隣接ノードとなり、ノードの各々は自分の隣接ノードと直接通信することができる。しかし、各ノードの送信パワーとカバー範囲が有限であるため、ノードがそのカバー範囲外のノードと通信を行う必要がある場合、ネットワークにおける他のノードの転送を必要とし、ここで、転送に加わるノードが中間ノード（intermediate node）と称される。ノードAとノードCとの通信を例として、中間ノードとしてのノードBはA、Cという二つのノード間に経路を提供し転送の役割を果たす。このようにマルチホップルートの方式を通じてノード間の通信が実現されている。
【０００５】
上記から、経路の確立はAd hocネットワークの正常な運行を保証する重要な要素であることがわかる。現在、最も常用されるAd hocネットワークルーティングプロトコルは国際インターネット・エンジニアリング・タスクフォース（IETF）のモバイルアドホックネットワーク（MANET）ワーキンググループによって制定されたダイナミックソースルーティング（DSR）とAd hocオンデマンド距離ベクトル（AODV）ルーティングプロトコルである。
【０００６】
図2は従来のDSRプロトコルに基づく経路確立方法のフロチャートである。図2を参照して、当該方法は、以下のステップを含む。
【０００７】
ステップ201において、ソースノードはネットワークの上位層からのデータパケットを受信する。
【０００８】
ステップ202〜204において、宛先ノードまでの経路がソースノードに保存されているか否かを判断して、保存されている場合、保存されている経路に従って当該データパケットを送信し、本経路確立のプロセスを終了し、保存されていない場合、ソースノードはソースノードのアドレスと宛先ノードのアドレスの付けられている経路要求パケット（RREQ）をブロードキャストすることによって、宛先ノードまでの経路を探索し、続いてステップ205を実行する。
【０００９】
ステップ205〜206において、他のノードによってブロードキャストされたRREQが中間ノードに受信され、受信されたRREQに基づいて当該中間ノード内の経路情報記録を更新し、当該中間ノードがRREQに対応する宛先ノードであるか否かを判断して、RREQに対応する宛先ノードである場合、ステップ209を実行し、そうでない場合、ステップ207を実行する。
【００１０】
Ad hocネットワークのノードの各々には、当該ノードをソースノードとし、他のノードを宛先ノードとする際の経路情報を保存する経路情報記録が存在する。RREQには、ソースノードと宛先ノードのアドレスだけではなく、当該RREQの通過した中間ノードの経路情報も付けられているため、本ステップにおける中間ノードは受信したRREQから経路情報を解析し、解析した経路情報を用いて自分の経路情報記録を更新する。
【００１１】
ステップ207〜208において、宛先ノードまでの経路が中間ノードに存在するか否かを判断して、存在する場合、ステップ209を実行する。存在しない場合に、当該中間ノードはRREQに自分の経路情報を追加し、追加操作をされたRREQをブロードキャストしていき、ステップ205に戻る。
【００１２】
ステップ209〜210において、経路応答パケット（RREP）をソースノードに返信し、ソースノードは受信したRREPに基づいて自分の経路情報記録を更新し、ステップ202に戻る。
【００１３】
中間ノードからソースノードに返信されるRREPにはソースノードから当該中間ノードまでの経路情報と当該中間ノードから宛先ノードまでの経路情報が付けられている。宛先ノードからソースノードに返信されるRREPにはソースノードから宛先ノードまでの経路情報が付けられている。ソースノードは、RREPに付けられている経路情報に基づいて自分の経路情報記録を更新することによって、当該ソースノードから他のノードまでの経路情報を取得する。
【００１４】
ここまで、従来の経路確立のプロセスが完了する。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
上記の各ステップからわかるように、従来の経路確立方法において、中間ノードはRREQを受信した後で続いてブロードキャストしていく。実際のアプリケーションにおいて、ノードは電池から電力を供給されるため、自分のエネルギーが有限である。こうして、経路の確立後のデータ伝送の過程で、中間ノードのエネルギーが足らないため、データが転送できない場合がある。この場合、経路確立プロセスを再スタートして他の経路を探索することしかできない。従って、従来の経路確立方法の効率が比較的低いことがわかる。
【００１６】
本発明は上記に鑑みてなされたものであり、ノードがルーティング機能を有する無線ネットワークにおいて経路確立の効率を高める経路確立方法を提供する。
【課題を解決するための手段】
【００１７】
本発明の発明構想に基づく方法は、
今回伝送するデータパケットに対応する宛先ノードまでの経路がソースノードに存在するか否かを判断して、宛先ノードまでの経路がソースノードに存在し、かつ当該経路内の中間ノードのエネルギーと当該データパケットに対応するトラフィック量とに基づいて、当該経路が有効な経路に決定された場合、当該経路を通じてデータパケットを送信し、そうでない場合、ソースノードが前記トラフィック量の付けられている経路要求パケットRREQをブロードキャストするステップAと、
RREQを受信したノードは自分が宛先ノードであるか否かを判断して、宛先ノードである場合、直接ステップDを実行し、宛先ノードでない場合、ステップCを実行するステップBと、
ノードのエネルギーとデータパケットに対応するトラフィック量とに基づいて、当該中間ノードが有効なノードに決定された場合、当該ノードから宛先ノードまでの有効な経路を探索するステップCと、
ソースノードから宛先ノードまでの経路及び当該経路上の各ノードのエネルギーの付けられている経路応答パケットRREPをソースノードに返信し、ソースノードは前記RREP内の経路に従ってデータパケットを送信するステップDと、を含む。
【００１８】
ここで、ステップAにおいて前記宛先ノードまでの経路がソースノードに存在するか否かを判断することは、
ソースノードは前記データパケット内の宛先ノードを索引として、自分の経路情報記録で当該宛先ノードに対応する項目を探索して、見付けた場合、宛先ノードまでの経路がソースノードに存在すると判定し、見付けなかった場合、宛先ノードまでの経路がソースノードに存在しないと判定することである。
【００１９】
ここで、前記経路情報記録に中間ノードのエネルギーが含まれる場合、ステップAにおいて前記当該経路が有効な経路に決定されることは、
宛先ノードまでの経路内の各中間ノードのエネルギーが全て今回データパケットの伝送を満足できると確定した場合に、当該経路が有効な経路に判定されることを含む。
【００２０】
ここで、前記ステップAにおいて、前記宛先ノードまでの経路内に、そのエネルギーが今回データパケットの伝送を満足できない中間ノードが存在すると決定された場合、ステップAにおいて前記ソースノードがトラフィック量の付けられているRREQをブロードキャストする操作を実行することを更に含む。
【００２１】
ここで、ステップCにおいて前記当該中間ノードが有効なノードに決定されることは、
当該中間ノードのエネルギーが今回データパケットの伝送を満足できると決定された場合、当該中間ノードが有効なノードに判定されすることである。
【００２２】
ここで、前記ステップCにおいて、当該中間ノードのエネルギーが今回データパケットの伝送を満足できないと決定された場合、前記RREQを捨て、前記ステップBに戻ることを更に含む。
【００２３】
ここで、前記経路情報記録に中間ノードのエネルギーが含まれる場合、ステップCにおいて前記宛先ノードまでの有効な経路を探索することは、
前記中間ノードの経路情報記録で前記宛先ノードまでの経路を探索し、当該経路内各中間ノードのエネルギーが全て今回データパケットの伝送を満足できる場合、当該経路が有効な経路に判定されることである。
【００２４】
ここで、前記ステップCにおいて、前記中間ノードの経路情報記録で宛先ノードまでの経路を見付けなかった場合、当該中間ノードのアドレスとエネルギーの付けられているRREQをブロードキャストし、前記ステップBに戻ることを更に含む。
【００２５】
ここで、ステップCにおいて、前記宛先ノードまでの経路内に、そのエネルギーが今回データパケットの伝送を満足できない中間ノードが存在すると決定された場合、RREQを受信した中間ノードのアドレスとエネルギーの付けられているRREQをブロードキャストし、前記ステップBに戻ることを更に含む。
【００２６】
ここで、予めエネルギーの下限を設定し、
前記中間ノードのエネルギーが今回データパケットの伝送を満足できると決定されることは、
前記データパケットに対応するトラフィック量に基づいて、当該データパケットの伝送に必要なエネルギーを計算し、
中間ノードのエネルギーと前記データパケットの伝送に必要なエネルギーとの差を計算することによって、前記中間ノードの残存エネルギーを得、
中間ノードの残存エネルギーが前記エネルギーの下限以上であるか否かを判断して、下限以上である場合、中間ノードのエネルギーが今回データパケットの伝送を満足できると判定される、ことを含む。
【００２７】
ここで、予め最高エネルギーの消費率を設定し、
前記中間ノードのエネルギーが今回データパケットの伝送を満足できると決定されることは、
前記データパケットに対応するトラフィック量に基づいて、当該データパケットの伝送に必要なエネルギーを計算し、
前記データパケットの伝送に必要なエネルギーと中間ノードのエネルギーとの比を計算し、
計算された比値の各々が前記最高エネルギーの消費率より小さいか否かを判断して、小さい場合、中間ノードのエネルギーが今回データパケットの伝送を満足できると判定される、ことを含む。
【００２８】
ここで、予め最低エネルギーの残存率を設定し、
前記中間ノードのエネルギーが今回データパケットの伝送を満足できると決定されることは、
前記データパケットに対応するトラフィック量に基づいて、当該データパケットの伝送に必要なエネルギーを計算し、
中間ノードのエネルギーと前記データパケットの伝送に必要なエネルギーとの差を計算することによって、中間ノードの剰余エネルギーを取得し、残存エネルギーと対応の中間ノードの初期エネルギ―との比を計算し、
計算された比値の各々が前記最低エネルギーの残存率以上であるか否かを判断して、残存率以上である場合、中間ノードのエネルギーが今回データパケットの伝送を満足できると判定される、ことを含む。
【００２９】
前記RREQをブロードキャストすることは全確率に従って当該RREQをブロードキャストすることである。
【００３０】
ここで、予めエネルギーレベル及び各エネルギーレベルに対応するブロードキャスト確率を設定し、
前記RREQをブロードキャストすることは、
当該RREQをブロードキャストする中間ノードのエネルギーと前記データパケットの伝送に必要なエネルギーとの差に対応するエネルギーレベルを決定し、又は、前記データパケットの伝送に必要なエネルギーと当該中間ノードのエネルギーとの比に対応するエネルギーレベルを決定し、又は、当該中間ノードのエネルギーと前記データパケットの伝送に必要なエネルギーとの差と、当該中間ノードの初期エネルギーとの比に対応するエネルギーレベルを決定し、
当該エネルギーレベルに対応するブロードキャスト確率に従ってRREQをブロードキャストする、ことである。
【００３１】
ここで、前記ステップAの前に、ソースノードが、今回伝送しようとするデータパケットを受信し、当該データパケットに対応するトラフィック量と宛先ノードを決定することを更に含む。
【００３２】
ここで、ステップBにおける前記判断の前に、当該方法は、RREQを受信した中間ノードが前記RREQに基づいて自分の経路情報記録を更新することを更に含む。
【００３３】
ここで、ステップDにおいて前記ソースノードが前記RREP内の経路に従ってデータパケットを送信する前に、当該方法は、ソースノードが前記RREPに基づいて自分の経路情報記録を更新することを更に含む。
【００３４】
ここで、ステップBにおいて前記ステップCを実行する前に、当該方法は、前記RREQを受信した中間ノードが初めて当該RREQを受信したか否かを判断して、初めて当該RREQを受信した場合、当該RREQを捨て、ステップBにおける前記判断に戻し、そうでない場合、続いてステップCを実行することを更に含む。
【発明の効果】
【００３５】
本発明によると、ノードがルーティング機能を有する無線ネットワークにおいて経路確立の効率を高めることができる。具体的に、本発明は以下のような有益な効果を有している。
【００３６】
本発明において、ソースノードから送信される経路要求パケットには伝送する必要のあるトラフィック量が付けられており、ソースノードから宛先ノードまでの経路内の各中間ノードのエネルギーが全て現在のデータパケットの伝送に十分である場合のみに、当該経路を有効な経路と決定し、当該有効な経路を用いてデータパケットを宛先ノードに伝送する。経路確立過程において、本発明はデータ伝送過程で中間ノードのエネルギー不足による経路の再構築を有効に避け、エネルギー十分なノードと経路をスピーディに見付けることができることにより、経路確立の効率を向上させている。
【００３７】
また、本発明では中間ノードのエネルギーに基づいてRREQブロードキャストの確率を決定することができる。この方式において、中間ノードのエネルギーレベルが高ければ高いほど、RREQブロードキャストの確率も高くなり、逆に、中間ノードのエネルギーレベルが低ければ低いほど、RREQブロードキャストの確率も低くなる。こうして、ノードのエネルギー消費の公平性の向上に有利になり、一部のノードのエネルギー過消費状況の減少に有効になっている。
【発明を実施するための最良の形態】
【００３８】
本発明の目的、技術方案を更に明確にするように、以下、図面を参照して実施例を挙げて本発明を更に詳しく説明する。
【００３９】
本発明はノードがルーティング機能を有する無線ネットワークにおける経路確立方法である。その核心的発明構想として、ノードデバイス（node device)は自分のエネルギーがトラフィック量のニーズを十分に満たすときこそ、経路確立に加わる。
【００４０】
図3は本発明における経路確立方法の例を示すフローチャートである。図3を参照して、当該方法は、以下のステップを含む。
【００４１】
ステップ301において、今回伝送するデータパケットに対応する宛先ノードまでの経路がソースノードに存在するか否かを判断して、宛先ノードまでの経路がソースノードに存在し、かつ当該経路の中間ノードのエネルギーと当該データパケットに対応するトラフィック量とに基づいて、当該経路が有効な経路に決定された場合、当該経路を通じてデータパケットを送信する。そうでない場合、ソースノードがトラフィック量の付けられている経路要求パケットRREQをブロードキャストする。
【００４２】
ステップ302において、RREQを受信したノードは自分が宛先ノードであるか否かを判断して、宛先ノードである場合、ステップ304を実行し、そうでない場合、ステップ303を実行する。
【００４３】
ステップ303において、ノードのエネルギーとデータパケットに対応するトラフィック量とに基づいて、当該ノードが有効なノードに決定された場合、宛先ノードまでの有効な経路を当該ノードで探索する。
【００４４】
ステップ304において、経路応答パケットRREPがソースノードに返信され、当該RREPには、ソースノードから宛先ノードまでの経路及び当該経路上の各ノードのエネルギー情報が付けられており、ソースノードはRREP内の経路に従ってデータパケットを送信する。
【００４５】
以下、DSRプロトコルに基づく例で本発明の経路確立方法を説明する。
【００４６】
本実施例において、ソースノードと宛先ノードは両方とも十分なエネルギーを有し、且つ各ノードの経路情報記録には当該ノードから他のノードまでの各経路のアドレス情報が保存されているだけではなく、各経路上のノードのエネルギー情報も保存されるていると黙認する。本実施例におけるノード内の経路情報記録について、表1に示すような様式を採用することができる。
【表１】
2007325261.tif 000003
【００４７】
上表において、1行目の内容を例として説明する場合、当該表の所在ノードは中間ノードN1、N2とN3を通過して宛先ノードAに到達し、上記三つの中間ノードに対応するエネルギーはそれぞれE1、E2とE3であり、且つ宛先ノードAに対応するエネルギーはEAである。
【００４８】
図4は本実施例による経路確立方法のフロチャートである。図4に示すように、本実施例の経路確立方法は以下のステップを含む。
【００４９】
ステップ401〜402において、ソースノードはアプリケーションレイヤーからのデータパケットを受信し、当該データパケットに対応するトラフィック量と宛先ノードを決定する。
【００５０】
ここで、ソースノードはデータパケットを受信した後、まず、当該データパケットに付けられている情報、例えば、データパケットの大きさ、宛先アドレスなどを読み取り、次に、読み取ったデータパケットの大きさを対応のトラフィック量とし、宛先アドレスに基づいて宛先ノードを決定する。
【００５１】
ステップ403において、宛先ノードまでの経路がソースノードに存在するか否かを判断して，存在する場合、ステップ404を実行し、存在しない場合、ステップ405を実行する。
【００５２】
本ステップにおいて、ソースノードはデータパケット内の宛先ノードを索引として、自分の経路情報記録で当該宛先ノードに対応する項目を探索する。見付けた場合、宛先ノードまでの経路がソースノードに存在すると判定し、見付けなかった場合、宛先ノードまでの経路がソースノードに存在しないと判定する。
【００５３】
ステップ404において、宛先ノードまでの経路内の各中間ノードのエネルギーが全て今回データパケット伝送の要求を満足できるか否かを判断して、満足できる場合、ステップ408を実行し、満足できない場合、続いてステップ405を実行する。
【００５４】
Ad hocネットワークにおいて、ノードがブロードキャスト方式でデータパケットを送受信するに必要なエネルギーはそれぞれ以下の通りである。
【００５５】
送信の場合、1.9×データパケットの大きさ＋266。
【００５６】
受信の場合、0.5×データパケットの大きさ＋56。
【００５７】
上式によって計算されたエネルギーの各々はマイクロワット・秒/バイト（μW・sec/byte）を単位とする。
【００５８】
中間ノードが上式に基づいてデータパケットを送受信する必要であるため、中間ノードがデータパケットを伝送するに必要なエネルギーは（1.9×データパケットの大きさ＋266）＋（0.5×データパケットの大きさ＋56）＝2.4×データパケットの大きさ＋322である。
【００５９】
本実施例において、予めエネルギーの下限が設定され、ノード内のエネルギーとデータパケットの伝送に必要なエネルギーとの差がエネルギーの下限より低い場合、当該ノードのエネルギーが足りないと判定する。ここで、データパケットの伝送に必要なエネルギーを得た後、宛先ノードまでの経路で各ノードのエネルギーが全て今回データパケットの伝送を満足できるか否かを判断する方法として、まず、経路情報記録から中間ノードのエネルギーを読み取り、次に、取得されたエネルギーとデータパケットの伝送に必要なエネルギーとの差を計算することによって、各中間ノードの残存エネルギーを得、且つ、得られた各残存エネルギーが全てエネルギーの下限以上であるか否かを判断して、得られた残存エネルギーが全てエネルギーの下限以上である場合、あらゆるノードのエネルギーが全て今回データパケットの伝送を満足できると判定し、そうでない場合、そのエネルギーが今回データパケットの伝送を満足できないノードが存在すると判定する。エネルギーの下限がEminであり、ノードのエネルギーがEであり、データパケットの伝送に必要なエネルギーがEtであるとする場合、当該ノードの残存エネルギーErはEr＝E−Etである。
【数１】
2007325261.tif 000004
【００６０】
の場合、当該ノードのエネルギーが今回データパケットの伝送を満足できることになり、これに反する場合は、今回データパケットの伝送を満足できないことになる。
【００６１】
また、予め最高エネルギーの消費率が設定されてもよい。この場合は、データパケットの伝送に必要なエネルギーと中間ノードのエネルギーとの比と、最高エネルギーの消費率との間の関係によって、ノードのエネルギーが今回データパケットの伝送を満足できるか否かを決定する。具体的に、計算された各比率が全て上記最高エネルギーの消費率より小さい場合、中間ノードのエネルギーが今回データパケットの伝送を満足できると判定する。
【００６２】
なお、本実施例において、予め最低のエネルギーの残存率が設定されることができ、この場合、宛先ノードまでの経路で各ノードのエネルギーが全て今回データパケットの伝送を満足できるか否かを判断する別の方法として、ソースノード自分のエネルギーを取得した後、経路情報記録から中間ノードの現在エネルギーを読み取り、次に、各ノードの現在エネルギーとデータパケットの伝送に必要なエネルギーとの差を計算し、計算された差値と対応のノードの初期エネルギーとの比を決定し、その後、決定された比値が最低エネルギーの残存率以上であるか否かを判断して、残存率以上である場合、各ノードのエネルギーが全て今回データパケットの伝送を満足できると判定し、残存率以上でない場合、そのエネルギーが今回データパケットの伝送を満足できないノードが存在すると判定する。最低エネルギーの残存率がrであり、ノードの初期エネルギーがE0であり、ノードの現在エネルギーがEcであり、データパケットの伝送に必要なエネルギーがEtであるとする場合、当該ノードの残存エネルギーErはEr＝Ec−Etである。
【数２】
2007325261.tif 000005
【００６３】
の場合、当該ノードのエネルギーが今回データパケットの伝送を満足できることになり、これに反する場合、今回データパケットの伝送を満足できないことになる。
【００６４】
ステップ405において、ソースノードはデータパケットに対応するエネルギーの付けられているRREQをブロードキャストする。
【００６５】
ソースノードに保存された経路内の各中間ノードのエネルギーが全て今回データパケットの伝送を満足できることでない場合、ソースノードは当該データパケットに対応するトラフィック量をRREQにカプセル化し、ブロードキャスト方式により、当該RREQをブロードキャストしていく。
【００６６】
ステップ406において、RREQを受信したノードはエネルギー及びデータパケットに対応するトラフィック量に基づいて有効な経路を決定し、有効な経路情報をソースノードに返信する。
【００６７】
ステップ407において、ソースノードは受信したRREPに基づいて自分の経路情報記録を更新する。
【００６８】
ステップ408において、RREP内の経路を通じてデータパケットを送信し、今回経路確立のプロセスを終了する。
【００６９】
ここまで、本実施例による経路確立のプロセスを完了する。
【００７０】
ステップ406でRREQを受信したノードが有効な経路を決定して有効な経路情報をソースノードに返信する具体的な方法は図5に示す通りである。図5に示すように、当該方法は、以下のステップを含む。
【００７１】
ステップ501〜502において、RREQを受信したノードはRREQに基づいて自分の経路情報記録を更新し、本ノードが宛先ノードであるか否かを判断して、宛先ノードである場合、ステップ510を実行し、宛先ノードでない場合、続いてステップ502を実行する。
【００７２】
RREQは既に複数の中間ノードによって転送された可能性があり、各中間ノードは、RREQの転送過程で、全て自分のアドレスとエネルギー情報をRREQに追加する。即ち、当該RREQにはその通過したノードの経路とエネルギー情報が付けられているため、RREQを受信したノードは受信したRREQに対して解析を行い、解析結果に基づいて自分の経路情報記録を更新し、当該中間ノードから他のノードまでの経路及び対応のノードのエネルギー情報を追加する。
【００７３】
ステップ503において、当該RREQが当該ノードに初めて受信されたか否かを判断して、初めて受信された場合、ステップ504を実行し、そうでない場合、ステップ506における当該RREQを捨てる操作を実行し、そしてステップ501に戻る。
【００７４】
RREQにとって、ソースノード、宛先ノード及び当該RREQのブロードキャストシーケンス番号が共同で当該RREQの核心部分を構成し、この三つの核心部分が全て同じであるRREQは重複RREQである。重複RREQに対する複数回の同じ処理操作がノードによって行われることを防ぐために、本実施例では、同じRREQを受信しなかった場合こそ、後続の操作を実行する。
【００７５】
ステップ504〜506において、RREQを受信したノードは自分の残存エネルギーを取得し、取得した残存エネルギーが今回データパケットの伝送を満足できるか否かを判断して、満足できる場合、ステップ507を実行し、満足できない場合、受信したRREQを捨て、ステップ501に戻る。
【００７６】
RREQを受信したノードで、宛先ノードではないノードは中間ノードである。ここで、ステップ404と同じ方法に従ってデータパケットの伝送に必要なエネルギーを決定し、RREQを受信したノードの現在エネルギーからデータパケット伝送に対応するエネルギーを減算することによって、当該ノードの見通しの残存エネルギーを得る。予めエネルギーの下限が設定された場合、ここでは、ノードの残存エネルギーとエネルギーの下限を比較することによって、当該ノードが今回データパケットの伝送を満足できるか否かを判定する。予め最高エネルギーの消費率が設定された場合、ここでは、データパケットの伝送に必要なエネルギーと当該中間ノードのエネルギーとの比と、最高エネルギーの消費率とを比較することによって、当該ノードが今回データパケットの伝送を満足できるか否かを判定する。予め最低エネルギーの残存率が設定された場合、ここでは、残存エネルギーとノードの初期エネルギーとの比値と、最低エネルギーの残存率とを比較することによって、当該ノードが今回データパケットの伝送を満足できるか否かを判定する。
【００７７】
RREQを受信したノードが今回データパケットの伝送を実行することができない場合、当該ノードが有効な中間ノードではないことになる。ソースノードが当該ノードの所在経路を選択してデータパケットを伝送する場合は、データパケットの伝送過程でエネルギー不足によって経路の使用不可能になるため、経路を再構築してデータパケットを再送しなければならない。従って、この場合、RREQに対して何の処理もせず、直接に捨ててよい。
【００７８】
ステップ507において、RREQを受信したノードに宛先ノードまでの経路が存在するか否かを判断して，存在する場合、続いてステップ508を実行し、存在しない場合、直接ステップ509を実行する。
【００７９】
ステップ508において、当該経路内の中間ノードのエネルギーが今回データパケットの伝送を満足できるか否かを判断して、満足できる場合、ステップ510を実行し、満足できない場合、ステップ509を実行する。
【００８０】
本ステップではステップ404と同じ方法を用いて判断を実行する。
【００８１】
上記ステップ504〜ステップ508は有効な経路を決定する操作である。
【００８２】
ステップ509において、RREQを受信したノードのアドレスとエネルギーの付けられているRREQをブロードキャストし、ステップ501に戻る。
【００８３】
RREQを受信した中間ノードのエネルギーが十分であり、且つ当該中間ノードに宛先ノードまでの有効な経路が存在しない場合、当該中間ノードは自分のアドレスとエネルギー情報の追加されているRREQをブロードキャストする。
【００８４】
図6は本実施例によるRREQの内部構成を示す図である。図6を参照して、RREQには、ソースノードアドレス、宛先ノードアドレス、ブロードキャストシーケンス番号、ソースノードエネルギーEソースノード、中間ノードアドレスN1…Nm、中間ノードに対応するエネルギーE1…Em及びデータパケットに対応するトラフィック量が含まれる。
【００８５】
ステップ510において、RREQを受信したノードは自分から宛先ノードまでの経路情報及び各ノードに対応するエネルギーの付けられているRREPをソースノードに返信する。
【００８６】
RREQを受信したノードが宛先ノードであり、又は宛先ノードまでの有効な経路の存在する中間ノードである場合、ソースノードに返信するRREPには、ソースノードから宛先ノードまでの経路情報、即ちノードのアドレス及び対応のエネルギー情報が付けられている。
【００８７】
ここまで、有効な経路を決定して有効な経路情報を返信するプロセスを終了する。
【００８８】
上記の説明からわかるように、本実施例において、ソースノードから送信される経路要求パケットには伝送する必要のあるトラフィック量が付けられており、ソースノードから宛先ノードまでの経路内の各中間ノードのエネルギーが全て現在のデータパケットの伝送に十分できるときのみに、当該経路を有効な経路と決定し、かつ、当該有効な経路を用いてデータパケットを宛先ノードに伝送する。上記技術方案では、エネルギー十分なノードと経路を迅速に選定することができて、データ伝送過程で中間ノードのエネルギー不足による経路の再構築が低下され、経路確立の効率が向上される。
【００８９】
本実施例において、中間ノード自分は有効なノードであるが、即ちそのエネルギーがデータパケットの伝送を満足できるノードであるが、宛先ノードまでの有効な経路を見付けなかった場合、ブロードキャストによってRREQを転送し、即ち全確率に従ってRREQをブロードキャストする。RREQの過度なブロードキャストを避けるために、本実施例のステップ509ではノードのエネルギーに基づくブロードキャスト確率の決定方式を用いてRREQをブロードキャストすることもできる。この方式において、予め一つ又は複数のエネルギーレベル閾値t1、t2…tiが設定され、各エネルギーレベルに対応するブロードキャスト確率ρ1、ρ2…ρiが設定され、ここで、t1>t2>…>ti、ρ1>ρ2>…>ρiである。中間ノードの残存エネルギーがt1以上である場合、残存エネルギーがエネルギーレベル1になり、そうすれば、確率ρ1を用いてRREQをブロードキャストする。中間ノードの残存エネルギーがt2以上であり、且つt1より小さい場合、残存エネルギーがエネルギーレベル2になり、そうすれば、確率ρ2を用いてRREQをブロードキャストする。これによって類推して、中間ノードの残存エネルギーとエネルギーレベル閾値との関係に基づいて、RREQブロードキャストの確率を決定する。最低エネルギーの残存率に基づいてノードが有効であるか否かを判断する場合に対しても、ここの異なるブロードキャスト確率に従ってRREQをブロードキャストする方式を用いることができる。
【００９０】
ネットワーク運営の初期、各ノードのエネルギーレベルが全て比較的高いときは、大部分中間ノードのエネルギーが全てエネルギーのニーズを満足できるが、通信回数の増加に伴っては、ノードのエネルギーがある程度低下される。従って、中間ノードのエネルギーに基づいてRREQブロードキャストの確率を決定することができる。中間ノードのエネルギーレベルが高ければ高いほど、RREQブロードキャストの確率も高くなり、逆に、中間ノードのエネルギーレベルが低ければ低いほど、RREQブロードキャストの確率も低くなる。こうして、ノードのエネルギー消費の公平性の向上に有利になり、ノードのエネルギー過消費状況の減少に有効になっている。
【００９１】
また、本実施例において、ノードにより自分の経路情報記録を更新することで以下の二つの方式を用いることができる。一つは、経路情報記録に新しい項目を追加し、ステップ404と508で同一ノードのエネルギーの最小値を取得して当該ノードの現在エネルギーとすること。もう一つは、受信したばかりのエネルギーで当該ノードの元の記録を切り替え、こうしてステップ404と508では当該ノードに対応するエネルギーを直接読み取ること。
【００９２】
以上はDSRプロトコルを例とした経路確立方法である。上記方法はAODVプロトコルなどに基づくアドホックネットワークにも応用されることができる。要するに、本発明の方法はノードがルーティング機能を有する無線ネットワークに適用される。
【００９３】
上記は、本発明の好ましい実施例にすぎず、本発明の保護範囲を限定するものではない。本発明の精神と原則内で行われる種々の修正、均等切替、改善などは全て本発明の保護範囲内に含まれるべきである。
【図面の簡単な説明】
【００９４】
【図１】Ad hocネットワークの構成図である。
【図２】従来のDSRプロトコルに基づく経路確立方法のフローチャートである。
【図３】本発明の経路確立方法の例を示すフローチャートである。
【図４】本発明の実施例による経路確立方法のフロチャートである。
【図５】本発明の実施例によるRREQを受信したノードが有効な経路を決定して有効な経路情報をソースノードに返信する方法のフローチャートである。
【図６】本発明の実施例によるRREQの構成図である。
【符号の説明】
【００９５】
Ａ、Ｂ、Ｃ…ノード、Eソースノード…ソースノードエネルギー、N1〜Nm…中間ノードアドレス、E1〜Em…中間ノードに対応するエネルギー
【図１】
2007325261.tif 000006
【図２】
2007325261.tif 000007
【図３】
2007325261.tif 000008
【図４】
2007325261.tif 000009
【図５】
2007325261.tif 000010
【図６】
2007325261.tif 000011