ネットワークにおけるルートディスカバリのための方法及びノード
【課題】有効にＲＲＥＱパケットの伝送を減らし、データパケットのコリジョンの可能性を減らし、ネットワーク性能を改善することができる、ネットワークにおけるルートディスカバリのための方法等を提供する
【解決手段】方法は、ネットワークにおけるノードのレベルを分類し、当該ノードに隣接するノードからルート要求パケットを受信し、受信された前記ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルを当該ノードのレベルと比較し、当該ノードのレベルがルート要求パケットに含まれるノードレベル情報によって示されるノードレベルよりも高い場合に、ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルを当該ノードのレベルであるよう更新し、更新されたルート要求パケットを当該ノードに隣接する他のノードへ転送する。
【解決手段】方法は、ネットワークにおけるノードのレベルを分類し、当該ノードに隣接するノードからルート要求パケットを受信し、受信された前記ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルを当該ノードのレベルと比較し、当該ノードのレベルがルート要求パケットに含まれるノードレベル情報によって示されるノードレベルよりも高い場合に、ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルを当該ノードのレベルであるよう更新し、更新されたルート要求パケットを当該ノードに隣接する他のノードへ転送する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク通信の分野、特に、ネットワークにおけるルートディスカバリのための方法及びノードに係る。
【背景技術】
【０００２】
ＡＯＤＶ（Ad hoc On-Demand Distance Vector Routing）、ＤＳＲ（Dynamic Source Routing）、ＤＳＤＶ（Destination-Sequenced Distance-Vector Routing）等の、無線アドホックネットワークのための幾つかのルーティング方法が提案されている。それらの中で、ＡＯＤＶプロトコルが研究の焦点であり、幅広く使用されている。ＡＯＤＶにおいては、ルーティング確立及びルーティング選択は２つの重要な段階である。ルーティング確立の段階で、ソースノードはあて先ノードへルート要求（ＲＲＥＱ）パケットを送信する。ルート要求パケットは、フラッディング態様で中間ノードによって転送されるブロードキャスティングパケットである。ルーティング選択の段階で、最小のホップ数を有するルートが、ソースノードからあて先ノードへの有効な経路として使用される。このルーティング方法は、ルーティング制御オーバーヘッドを減らすとともに、効率を改善するのに極めて有用である。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
しかし、ルーティング確立の段階では、ノードは、フラッディング態様でソースノードによって送信されたＲＲＥＱパケットを転送し、次のような問題を引き起こす。第一に、各ノードは、無分別に（フラッディング態様で）ＲＲＥＱパケットを転送し、ネットワーク上で多数の冗長情報をもたらす。第二に、ネットワークを介してノードによって送信される多数のＲＲＥＱパケットは、データパケットのコリジョンの可能性を高める。第三に、ＲＲＥＱパケットの送信及び受信はネットワークリソースを占有し、そのため、多数の冗長なＲＲＥＱパケットの送信は、ネットワーク性能の低下を引き起こす。
【０００４】
先行技術におけるそのような状況を鑑み、本発明の目的は、有効にＲＲＥＱパケットの伝送を減らし、データパケットのコリジョンの可能性を減らし、ネットワーク性能を改善することができる、ネットワークにおけるルートディスカバリのための方法及びノードを提供することである。
【課題を解決するための手段】
【０００５】
以下、本発明の特定の態様に対する基本的な理解を提供するために、本発明に関する概要が与えられる。しかし、当然、この概要は、本発明に関する完全な要約ではない。それは、本発明の決定的な部分又は重要な部分を決定するものでも、本発明の適用範囲を限定するものでもない。その目的は、単に、簡単に本発明に関して幾つかの概念を提示して、後述されるより詳細な説明の前置きとすることである。
【０００６】
上記目的を達成するために、本発明の態様に従って、ネットワークにおけるルートディスカバリのための方法であって、前記ネットワークにおけるノードのレベルを分類し、前記ノードに隣接するノードからルート要求パケットを受信し、受信された前記ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルを前記ノードのレベルと比較し、前記ノードのレベルが前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルよりも高い場合に、前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルを前記ノードのレベルであるよう更新し、更新された前記ルート要求パケットを前記ノードに隣接する他のノードへ転送する、方法が提供される。
【０００７】
本発明の他の態様に従って、ネットワークにおけるルートディスカバリのためのノードであって、当該ノードのレベルを分類するレベル分類部と、当該ノードに隣接するノードからルート要求パケットを受信する受信部と、前記受信部によって受信された前記ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルを、前記レベル分類部によって得られた当該ノードのレベルと比較する比較部と、前記ノードのレベルが前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルよりも高い場合に、前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルを前記ノードのレベルであるよう更新する更新部と、前記更新部によって更新された前記ルート要求パケットを当該ノードに隣接する他のノードへ転送する転送部とを有するノードがさらに提供される。
【０００８】
本発明の他の態様に従って、ネットワークにおけるルートディスカバリのための上記方法を実施するコンピュータプログラムプロダクトがさらに提供される。
【０００９】
本発明の他の態様に従って、ネットワークにおけるルートディスカバリのための上記方法を実施するコンピュータプログラムプロダクトが坦持される機械可読記憶媒体がさらに提供される。
【発明の効果】
【００１０】
上述される本発明の課題解決手段によれば、ルートディスカバリが行われる場合に多数の冗長なパケットを減らすことができ、多数の冗長情報が取り除かれることでコリジョンの可能性が減る。このようにして、本発明の課題解決手段は、パケット伝達比及びネットワークトラフィックを増大させ且つエンド間遅延を小さくすることができる。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施形態に従うネットワークにおけるルートディスカバリのための方法を説明するフローチャートである。
【図２】本発明の実施形態に従うネットワークにおけるルートディスカバリの実施の具体例を表す図である。
【図３】本発明の実施形態に従うネットワークにおけるルートディスカバリのためのノードを説明するブロック図である。
【図４】本発明の実施形態に従う方法及び／又はノードが実施され得る汎用のパーソナルコンピュータの構成例を表すブロック図である。
【発明を実施するための形態】
【００１２】
本発明は、添付の図面に関連して以下で与えられる詳細な説明を参照して、より良く理解され得る。図面において、同じ又は類似する構成要素は、同じ又は類似する参照符号によって表されている。添付の図面は、以下の詳細な説明とともに、本発明の好ましい実施形態を例示し且つ一例として本発明の原理及び利点を説明するよう、本願に含まれ且つ本願の一部を形成する。
【００１３】
当業者には明らかなように、図中の要素は、簡単さ及び明りょうさのためだけに示されており、必ずしも実寸ではない。例えば、図中の特定の要素の大きさは、本発明の実施形態に対する理解を改善するのに有用であるように、他の要素と比べて拡大されることがある。
【００１４】
以降、本発明の実施例について、図面に関連して記載する。明りょうさ及び簡単さのために、実際の実施形態の全ての特徴が本明細書中で説明されるわけではない。しかし、例えば、システム及び動作に関連する制限条件を満足するといった、開発者の明確な目標を達成するために、そのような実際の実施形態を開発する工程において実施形態に特有の多数の決定を行わなければならないことは明らかであり、また、制限条件は実施形態ごとに様々である。更に、開発作業は非常に複雑であり且つ時間がかかるが、そのような開発作業は、本開示の利益を享受する当業者にとってルーチンタスクに過ぎないことは明らかである。
【００１５】
ここで、不必要な詳細が本発明を不明りょうにすることを防ぐよう、本発明に従う方法及びノードに密接に関連する装置構造及び／又は処理ステップのみが図面において示され、本発明とほとんど関係ない他の詳細は省略されることに留意されたい。
【００１６】
本発明に従うネットワークにおけるルートディスカバリのための方法は、以下で図面を参照して記載される。
【００１７】
図１は、本発明の実施形態に従うネットワークにおけるルートディスカバリのための方法を説明するフローチャートである。
【００１８】
最初に、ステップＳ１１０で、ネットワークにおけるノードのレベルが分類される。
【００１９】
ステップＳ１１０における工程を通じて、ネットワークにおけるノードの夫々は様々なレベルに分類される。当業者には明らかなように、必要に応じて多種多様な態様でネットワークにおけるノードのレベルを分類することが可能である。
【００２０】
本発明の好ましい実施形態に従って、ネットワークにおけるノードのレベルが分類される場合に、最初にノードのコストが計算されてよく、次いでノードのレベルがコストに応じて分類されてよい。
【００２１】
本発明の好ましい実施形態に従って、ノードのコストは、次のコスト方程式（１）により計算されてよい：
cost＝a×remaining_energy＋b×hop_count＋c×neighbor_density＋d×bandwidth （１）
costは当該ノードのコストを表し、remaining_energyは当該ノードの残りのエネルギを表し、hop_countは当該ノードからあて先ノードへの最小ホップ数を表し、neighbor_densityは当該ノードの隣接ノード密度を表し、bandwidthは当該ノードのバンド幅を表し、a、b、c及びdは重み係数を表す。
【００２２】
当業者には明らかなように、上記の重み係数a、b、c及びdは、適用場面の必要条件に従って決定される。例えば、hop_countの重み係数bが最小であるよう設定される場合、それは、その適用場面におけるhop_countの重要性が最低であることを意味する。対照的に、hop_countの重み係数bが最大であるよう設定される場合、それは、その適用場面におけるhop_countの重要性が最高であることを意味する。
【００２３】
また、当業者には明らかなように、他のパラメータ及び対応する重み係数が、上記のパラメータremaining_energy、hop_count、neighbor_density及びbandwidthに加えて、適用場面の必要条件に従ってコスト方程式に加えられるよう考慮されてよい。
【００２４】
本発明の好ましい実施形態に従って、ノードのコストは初期設定段階で計算されてよい。初期設定段階では、ノードごとに、ある期間の学習の後、現在のノードからあて先ノードへのコストに関する情報が取得され得る。具体的に、初期設定段階では、ノードは、データパケットをあて先ノードへ送信することによって、現在のノードからあて先ノードへのコストのサンプル値を知り収集する。それによって、ノードのレベルは、得られたノードのコストに応じて分類され得る。
【００２５】
本発明の好ましい実施形態に従って、ノードのコストはデータ伝送の工程において更新されてよい。具体的に、データ伝送段階では、ノードがデータパケットを送信又は転送するたびに、現在のコスト値がこの工程から一度計算され、計算された現在のコスト値はノードのコストサンプル空間に加えられる。次いで、ノードのコストは、コストサンプル空間に従って更新される。このように、コスト情報の実時間の性能が改善され、ネットワークの実時間の状態変化が適応され得る。
【００２６】
次に、ステップＳ１２０で、現在のノードに隣接するノードからのルート要求（ＲＲＥＱ）パケットが受信される。
【００２７】
本発明の実施形態におけるＲＲＥＱパケットは、最後のホップノード（すなわち、現在のノードに隣接し、このＲＲＥＱパケットを送信するノード）のノードレベル情報が、現在のノードによって受信されるＲＲＥＱパケットに含まれる点で、先行技術におけるＲＲＥＱパケットと相違する。
【００２８】
次に、ステップＳ１３０で、受信されたルート要求パケットに含まれるノードレベル情報によって示されるノードレベルは、現在のノードのレベルと比較される。言い換えると、ステップＳ１３０では、現在のノードのレベルが最後のホップノードのレベルよりも高いかどうかが判断される。
【００２９】
ステップＳ１３０で現在のノードのレベルが最後のホップノードのレベルよりも高いと判断された場合、処理はステップＳ１４０に進む。
【００３０】
ステップＳ１３０で現在のノードのレベルが最後のホップノードのレベルよりも高くないと判断された場合、処理は終了する。
【００３１】
本発明の好ましい実施形態に従って、現在のノードのレベルが、ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルよりも高くない場合に、ルート要求パケットは、転送されるのではなく、捨てられてよい。
【００３２】
処理がステップＳ１４０に進むと、ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルは、ステップＳ１４０で、現在のノードのレベルであるよう更新される。
【００３３】
このように、現在のノードのレベルを示すノードレベル情報が、更新されたルート要求パケットに含まれる。
【００３４】
最後に、ステップＳ１５０で、更新されたルート要求パケットは、現在のノードに隣接する他のノードへ転送される。
【００３５】
本発明に従うネットワークにおけるルートディスカバリのための上記方法によれば、ＲＲＥＱパケットの送信を有効に減らすことができ、データパケットのコリジョンの可能性は低下し、ネットワーク性能は改善され得る。本発明に従う方法は、ネットワークトポロジが極めてゆっくりと変化し且つあて先ノードが決定されているところの適用場面におけるインテリジェントメーター読取システムに特に適している。
【００３６】
本発明の好ましい実施形態に従って、ルーティング確立の段階で、ソースノードがルート要求パケットを自身に隣接するノードへ送信し始める前に、ソースノードのレベルに関する情報はノードレベル情報としてルート要求パケットに加えられる。その後に、ソースノードは、修正されたルート要求パケットを自身に隣接するノードへ送信する。
【００３７】
本発明の好ましい実施形態に従って、あて先ノードが自身に隣接するノードからルート要求パケットを受信した後、ルートディスカバリが行われる。
【００３８】
以降、本発明に従うネットワークにおけるルートディスカバリのための方法が、図２を参照して詳細に記載される。
【００３９】
図２は、本発明の実施形態に従うネットワークにおけるルートディスカバリの実施の具体例を表す図である。図２に示されるネットワークには、ソースノード、中間ノード及びあて先ノードが含まれている。ソースノード及びあて先ノードの位置が図２（ａ）に示されている。
【００４０】
ノードのコストが初期設定段階で計算され、次いで、ノードのレベルが、計算されたコストに応じて分類される。説明の便宜上、ノードのコストが計算される場合に、現在のノードからあて先ノードへの最小ホップ数のみが考慮される。すなわち、上記のコスト方程式（１）において、重み係数a、c及びdは零に設定され、重み係数bは１に設定される。図２（ｂ）に示されるように、ネットワークにおけるノードは様々なレベルに分類される。ここで、ソースノードのレベルはレベル４である。目下の例では、ノードのレベル数が高ければ高いほど、ノードのレベルは低い。
【００４１】
ルーティング確立の段階で、ソースノードが自身に隣接するノードへルート要求パケットを送信し始める前に、ソースノードのレベル（レベル４）に関する情報は、ノードレベル情報としてルート要求パケットに加えられる。その後に、ソースノードは、修正されたルート要求パケットを自身に隣接するノードへ送信する。
【００４２】
レベル４のノースノードに隣接し、レベル３、４及び５を夫々有する中間ノードは、ソースノードからルート要求パケットを受信する。ソースノードのレベル（レベル４）を示すノードレベル情報は、それらの中間ノードによって受信されるルート要求パケットに含まれる。次いで、ソースノードからルート要求パケットを受信した中間ノードは、受信されたルート要求パケットに含まれるノードレベル情報によって示されるノードレベルを、現在のノードのレベルと比較して、現在のノードのレベルがソースノードのレベルよりも高いかどうかを判断する。
【００４３】
レベル３の中間ノードは、現在のノードのレベルがレベル４を有するソースノードのレベルよりも高いと判断し、次いで、ルート要求パケットに含まれるノードレベル情報によって示されるノードレベル（レベル４）を現在のノードのレベル（レベル３）であるよう更新する。
【００４４】
このようにして、現在のノードのレベル（レベル３）を示すノードレベル情報は、更新されたルート要求パケットに含まれる。
【００４５】
その後に、レベル３を有する中間ノードは、更新されたルート要求パケットを、この中間ノードに隣接する他のノードへ転送する。
【００４６】
一方、レベル４又は５を有する中間ノードは、現在のノードのレベルがレベル４を有するソースノードのレベルよりも高くない（すなわち、ソースノードのレベル以下である）と判断し、次いで、ルート要求パケットを転送するのではなく捨てる。
【００４７】
同様に、現在のノードが最後のホップノードからルート要求パケットを受信した場合に、現在のノードは、最初に、現在のノードのレベルが最後のホップノードのレベルよりも高いかどうかを判断する。現在のノードのレベルが最後のホップノードのレベルよりも高い場合には、現在のノードは自身のレベルをルート要求パケット内に更新し、次いで、更新されたルート要求パケットを次のホップノードへ転送する。現在のノードが最後のホップノードのレベルよりも高くない場合には、ルート要求パケットは転送されずに捨てられる。
【００４８】
最後に、図２（ｃ）に示されるように、あて先ノードが自身に隣接するノードからルート要求パケットを受信する場合に、ソースノードからあて先ノードへのルートディカバリが行われる。
【００４９】
本発明の実施形態に従うネットワークにおけるルートディスカバリのためのノードは、以下で図面を参照して詳細に記載される。
【００５０】
図３は、本発明の実施形態に従うネットワークにおけるルートディスカバリのためのノード３００を説明するブロック図である。
【００５１】
図３に示されるように、本発明の実施形態に従うノード３００は、レベル分類部３００と、受信部３２０と、比較部３３０と、更新部３４０と、転送部３５０とを有する。
【００５２】
レベル分類部３１０は、ノード３００のレベルを分類するよう構成される。
【００５３】
受信部３２０は、ノード３００に隣接するノードからルート要求パケットを受信するよう構成される。
【００５４】
比較部３３０は、受信部３２０によって受信されたルート要求パケットに含まれるノードレベル情報によって示されるノードレベルを、レベル分類部３１０によって得られたノード３００のレベルと比較するよう構成される。
【００５５】
更新部３４０は、ノード３００のレベルが、ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルよりも高い場合に、ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルをノード３００のレベルであるように更新するよう構成される。
【００５６】
転送部３５０は、更新部３４０によって更新されたルート要求パケットを、ノード３００に隣接する他のノードへ転送するよう構成される。
【００５７】
本発明の好ましい実施形態に従って、レベル分類部３１０は、ノード３００のコストを計算するコスト計算部（図示せず。）を更に有してよい。レベル分類部３１０は、コスト計算部によって計算されたコストに応じて、ノード３００のレベルを分類する。
【００５８】
本発明の好ましい実施形態に従って、コスト計算部は、上記のコスト方程式（１）によりノード３００のコストを計算してよい。
【００５９】
本発明の好ましい実施形態に従って、コスト計算部は、初期設定段階でノード３００のコストを計算してよい。
【００６０】
本発明の好ましい実施形態に従って、コスト計算部は、ノード３００によるデータ伝送の工程においてノード３００のコストを更新してよい。
【００６１】
ノード３００における上記の夫々のユニットの様々な特定の実施は、先に詳細に記載されており、従って、その説明は、ここでは繰り返されない。
【００６２】
明らかに、本発明に従う上記の方法の夫々の動作工程は、機械可読記憶媒体に記憶されるコンピュータ実行可能なプログラムの態様で、実施されてよい。
【００６３】
そして、本発明の対象は、上記のコンピュータ実行可能なプログラムが坦持される記憶媒体が、コンピュータ実行可能なプログラムを読み出して実行するコンピュータ又は中央処理演算装置（ＣＰＵ）を備えるシステム又は装置へ直接に又は間接に提供される態様で、実施可能である。このとき、本発明の実施は、システム又は装置がプログラムを実行する機能を有する限りプログラムに限定されず、プログラムは、オブジェクト指向プログラム、インタープリタによって実行されるプログラム、オペレーティングシステムへ提供されるスクリプトプログラム等の任意の形態であってよい。
【００６４】
上記の機械可読記憶媒体は、様々なメモリ及び記憶ユニット、半導体素子、光ディスク、磁気ディスク及び光磁気ディスク等のディスク、並びに、情報を記憶するのに適したその他の媒体を含むが、これらに限られない。
【００６５】
更に、本発明は、コンピュータを通じてインターネット上の対応するウェブサイトに接続し、本発明に従うコンピュータ実行可能なプログラムをコンピュータにダウンロードしてインストールし、そのプログラムを実行することによって、実施されてもよい。
【００６６】
図４は、本発明の実施形態に従う方法及び／又はノードが実施され得る汎用のパーソナルコンピュータの構成例を表すブロック図である。
【００６７】
図４に示されるように、ＣＰＵ１３０１は、読出専用メモリ（ＲＯＭ）１３０２に記憶されているプログラム又は記憶部１３０８からランダムアクセスメモリ（ＲＡＭ）１３０３に読み込まれたプログラムに従って、様々な処理を実行する。ＲＡＭ１３０３には、必要に応じて、様々な処理を実行する際にＣＰＵ１３０１に必要とされるデータ等も格納される。ＣＰＵ１３０１、ＲＯＭ１３０２及びＲＡＭ１３０３は、バス１３０４を介して互いに接続されている。入出力インターフェース１３０５もバス１３０４へ接続されている。
【００６８】
入出力インターフェース１３０５には、次の構成要素、すなわち、キーボード、マウス等を含む入力部１３０６と、陰極線管（ＣＲＴ）及び液晶ディスプレイ（ＬＣＤ）等のディスプレイ、スピーカ等を含む出力部１３０７と、ハードディスク等を含む記憶部１３０８と、ＬＡＮカード等のネットワークインターフェースカード、モデム等を含む通信部１３０９とが接続されている。通信部１３０９は、インターネット等のネットワークを介して通信処理を実行する。必要に応じて、ドライブ１３１０が入出力インターフェース１３０５へ接続されてもよい。磁気ディスク、光ディスク、光磁気ディスク、半導体メモリ等のリムーバブル媒体１３１１が、必要に応じて、ドライブ１３１０に実装されて、リムーバブル媒体１３１１から読み出されたコンピュータプログラムが、記憶部１３０８にインストールされる。
【００６９】
上記の一連の処理がソフトウェアで実施される場合に、そのソフトウェアを構成するプログラムは、インターネット等のネットワーク又はリムーバブル媒体１３１１等の記憶媒体からインストールされる。
【００７０】
当業者には明らかなように、記憶媒体は、プログラムが記憶され且つ装置とは別に分配されてプログラムをユーザに提供する、図４に示されるリムーバブル媒体１３１１に限定されない。リムーバブル媒体１３１１の例には、フロッピー（登録商標）ディスクを含む磁気ディスクと、コンパクトディスク読出専用メモリ（ＣＤ−ＲＯＭ）及びデジタルバーサタイルディスク（ＤＶＤ）を含む光ディスクと、ミニディスク（登録商標）（ＭＤ）を含む光磁気ディスクと、半導体メモリとがある。代替的に、記憶媒体は、ＲＯＭ１３０２、記憶部１３０８に含まれるハードディスク等であってよい。このとき、プログラムは記憶媒体に記憶され、記憶媒体は当該記憶媒体を含む装置とともにユーザに分配される。
【００７１】
本発明のノード及び方法において、夫々の構成要素又はステップが分解及び／又は再結合されてよいことは明らかである。そのような分解及び／又は再結合は、本発明の同等の解決手段と考えられるべきである。そして、上記の一連の処理を実行するステップは、もちろん記述されている順序で実行されてよいが、それは必須ではない。一部のステップは、互いに同時に又は独立して実行されてよい。
【００７２】
本発明の実施形態について図面を参照して記載してきたが、当然に、上記の実施形態は本発明を説明するためにのみ用いられ、本発明の限定として解されるべきではない。当業者は、本発明の技術的範囲内で変形及び代替を上記の実施形態に対して行うことができる。従って、本発明の技術的範囲は、添付の特許請求の範囲及びその均等によってのみ定義される。
【００７３】
以上の実施形態に関し、更に以下の付記を開示する。
（付記１）
ネットワークにおけるルートディスカバリのための方法であって、
前記ネットワークにおけるノードのレベルを分類し、
前記ノードに隣接するノードからルート要求パケットを受信し、
受信された前記ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルを前記ノードのレベルと比較し、
前記ノードのレベルが前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルよりも高い場合に、前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルを前記ノードのレベルであるよう更新し、
更新された前記ルート要求パケットを前記ノードに隣接する他のノードへ転送する、方法。
（付記２）
前記ネットワークにおけるノードのレベルを分類することは、
前記ノードのコストを計算し、
前記コストに応じて前記ノードのレベルを分類すること
をさらに含む、付記１に記載の方法。
（付記３）
前記ノードのコストは、
cost＝a×remaining_energy＋b×hop_count＋c×neighbor_density＋d×bandwidth
のコスト方程式により計算され、costは前記ノードのコストを表し、remaining_energyは前記ノードの残りのエネルギを表し、hop_countは前記ノードからあて先ノードへの最小ホップ数を表し、neighbor_densityは前記ノードの隣接ノード密度を表し、bandwidthは前記ノードのバンド幅を表し、a、b、c及びdは重み係数を表す、
付記２に記載の方法。
（付記４）
前記ノードのコストは、初期設定段階で計算される、
付記２又は３に記載の方法。
（付記５）
前記ノードのコストは、データ伝送の工程において更新される、
付記２又は３に記載の方法。
（付記６）
前記ノードのレベルが前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルよりも高くない場合に、前記ルート要求パケットを捨てる、
付記１に記載の方法。
（付記７）
ソースノードであるノードによって、前記ルート要求パケットに対してノードレベル情報として前記ソースノードのレベルに関する情報を加え、
前記ソースノードに隣接するノードへ前記ルート要求パケットを送信する、
付記１に記載の方法。
（付記８）
あて先ノードによって、該あて先ノードに隣接するノードからのルート要求パケットが受信された後、前記ルートディスカバリを行う、
付記１に記載の方法。
（付記９）
ネットワークにおけるルートディスカバリのためのノードであって、
当該ノードのレベルを分類するレベル分類部と、
当該ノードに隣接するノードからルート要求パケットを受信する受信部と、
前記受信部によって受信された前記ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルを、前記レベル分類部によって得られた当該ノードのレベルと比較する比較部と、
前記ノードのレベルが前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルよりも高い場合に、前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルを前記ノードのレベルであるよう更新する更新部と、
前記更新部によって更新された前記ルート要求パケットを当該ノードに隣接する他のノードへ転送する転送部と
を有するノード。
（付記１０）
前記レベル分類部は、当該ノードのコストを計算するコスト計算部を有し、該コスト計算部によって計算された前記コストに応じて当該ノードのレベルを分類する、
付記９に記載のノード。
（付記１１）
前記コスト計算部は、
cost＝a×remaining_energy＋b×hop_count＋c×neighbor_density＋d×bandwidth
のコスト方程式により当該ノードのコストを計算し、costは当該ノードのコストを表し、remaining_energyは当該ノードの残りのエネルギを表し、hop_countは当該ノードからあて先ノードへの最小ホップ数を表し、neighbor_densityは当該ノードの隣接ノード密度を表し、bandwidthは当該ノードのバンド幅を表し、a、b、c及びdは重み係数を表す、
付記１０に記載のノード。
（付記１２）
前記コスト計算部は、初期設定段階で当該ノードのコストを計算する、
付記１０又は１１に記載のノード。
（付記１３）
前記コスト計算部は、当該ノードによるデータ伝送の工程において当該ノードのコストを更新する、
付記１０又は１１に記載のノード。
（付記１４）
コンピュータによって読み出されて実行される場合に、該コンピュータに、付記１乃至８のうちいずれか１つに記載の方法を実行させることができる機械可読命令コードを記憶するプログラムプロダクト。
（付記１５）
付記１４に記載のプログラムプロダクトが坦持される機械可読記憶媒体。
【符号の説明】
【００７４】
ＳＲＣ ソースノード
ＳＩＮＫ あて先ノード
３００ ノード
３１０ レベル分類部
３２０ 受信部
３３０ 比較部
３４０ 更新部
３５０ 転送部
１３０１ ＣＰＵ
１３０２ 読出専用メモリ（ＲＯＭ）
１３０３ ランダムアクセスメモリ（ＲＡＭ）
１３０４ バス
１３０５ 入出力インターフェース
１３０６ 入力部
１３０７ 出力部
１３０８ 記憶部
１３０９ 通信部
１３１０ ドライブ
１３１１ リムーバブル媒体
【技術分野】
【０００１】
本発明は、ネットワーク通信の分野、特に、ネットワークにおけるルートディスカバリのための方法及びノードに係る。
【背景技術】
【０００２】
ＡＯＤＶ（Ad hoc On-Demand Distance Vector Routing）、ＤＳＲ（Dynamic Source Routing）、ＤＳＤＶ（Destination-Sequenced Distance-Vector Routing）等の、無線アドホックネットワークのための幾つかのルーティング方法が提案されている。それらの中で、ＡＯＤＶプロトコルが研究の焦点であり、幅広く使用されている。ＡＯＤＶにおいては、ルーティング確立及びルーティング選択は２つの重要な段階である。ルーティング確立の段階で、ソースノードはあて先ノードへルート要求（ＲＲＥＱ）パケットを送信する。ルート要求パケットは、フラッディング態様で中間ノードによって転送されるブロードキャスティングパケットである。ルーティング選択の段階で、最小のホップ数を有するルートが、ソースノードからあて先ノードへの有効な経路として使用される。このルーティング方法は、ルーティング制御オーバーヘッドを減らすとともに、効率を改善するのに極めて有用である。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
しかし、ルーティング確立の段階では、ノードは、フラッディング態様でソースノードによって送信されたＲＲＥＱパケットを転送し、次のような問題を引き起こす。第一に、各ノードは、無分別に（フラッディング態様で）ＲＲＥＱパケットを転送し、ネットワーク上で多数の冗長情報をもたらす。第二に、ネットワークを介してノードによって送信される多数のＲＲＥＱパケットは、データパケットのコリジョンの可能性を高める。第三に、ＲＲＥＱパケットの送信及び受信はネットワークリソースを占有し、そのため、多数の冗長なＲＲＥＱパケットの送信は、ネットワーク性能の低下を引き起こす。
【０００４】
先行技術におけるそのような状況を鑑み、本発明の目的は、有効にＲＲＥＱパケットの伝送を減らし、データパケットのコリジョンの可能性を減らし、ネットワーク性能を改善することができる、ネットワークにおけるルートディスカバリのための方法及びノードを提供することである。
【課題を解決するための手段】
【０００５】
以下、本発明の特定の態様に対する基本的な理解を提供するために、本発明に関する概要が与えられる。しかし、当然、この概要は、本発明に関する完全な要約ではない。それは、本発明の決定的な部分又は重要な部分を決定するものでも、本発明の適用範囲を限定するものでもない。その目的は、単に、簡単に本発明に関して幾つかの概念を提示して、後述されるより詳細な説明の前置きとすることである。
【０００６】
上記目的を達成するために、本発明の態様に従って、ネットワークにおけるルートディスカバリのための方法であって、前記ネットワークにおけるノードのレベルを分類し、前記ノードに隣接するノードからルート要求パケットを受信し、受信された前記ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルを前記ノードのレベルと比較し、前記ノードのレベルが前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルよりも高い場合に、前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルを前記ノードのレベルであるよう更新し、更新された前記ルート要求パケットを前記ノードに隣接する他のノードへ転送する、方法が提供される。
【０００７】
本発明の他の態様に従って、ネットワークにおけるルートディスカバリのためのノードであって、当該ノードのレベルを分類するレベル分類部と、当該ノードに隣接するノードからルート要求パケットを受信する受信部と、前記受信部によって受信された前記ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルを、前記レベル分類部によって得られた当該ノードのレベルと比較する比較部と、前記ノードのレベルが前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルよりも高い場合に、前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルを前記ノードのレベルであるよう更新する更新部と、前記更新部によって更新された前記ルート要求パケットを当該ノードに隣接する他のノードへ転送する転送部とを有するノードがさらに提供される。
【０００８】
本発明の他の態様に従って、ネットワークにおけるルートディスカバリのための上記方法を実施するコンピュータプログラムプロダクトがさらに提供される。
【０００９】
本発明の他の態様に従って、ネットワークにおけるルートディスカバリのための上記方法を実施するコンピュータプログラムプロダクトが坦持される機械可読記憶媒体がさらに提供される。
【発明の効果】
【００１０】
上述される本発明の課題解決手段によれば、ルートディスカバリが行われる場合に多数の冗長なパケットを減らすことができ、多数の冗長情報が取り除かれることでコリジョンの可能性が減る。このようにして、本発明の課題解決手段は、パケット伝達比及びネットワークトラフィックを増大させ且つエンド間遅延を小さくすることができる。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施形態に従うネットワークにおけるルートディスカバリのための方法を説明するフローチャートである。
【図２】本発明の実施形態に従うネットワークにおけるルートディスカバリの実施の具体例を表す図である。
【図３】本発明の実施形態に従うネットワークにおけるルートディスカバリのためのノードを説明するブロック図である。
【図４】本発明の実施形態に従う方法及び／又はノードが実施され得る汎用のパーソナルコンピュータの構成例を表すブロック図である。
【発明を実施するための形態】
【００１２】
本発明は、添付の図面に関連して以下で与えられる詳細な説明を参照して、より良く理解され得る。図面において、同じ又は類似する構成要素は、同じ又は類似する参照符号によって表されている。添付の図面は、以下の詳細な説明とともに、本発明の好ましい実施形態を例示し且つ一例として本発明の原理及び利点を説明するよう、本願に含まれ且つ本願の一部を形成する。
【００１３】
当業者には明らかなように、図中の要素は、簡単さ及び明りょうさのためだけに示されており、必ずしも実寸ではない。例えば、図中の特定の要素の大きさは、本発明の実施形態に対する理解を改善するのに有用であるように、他の要素と比べて拡大されることがある。
【００１４】
以降、本発明の実施例について、図面に関連して記載する。明りょうさ及び簡単さのために、実際の実施形態の全ての特徴が本明細書中で説明されるわけではない。しかし、例えば、システム及び動作に関連する制限条件を満足するといった、開発者の明確な目標を達成するために、そのような実際の実施形態を開発する工程において実施形態に特有の多数の決定を行わなければならないことは明らかであり、また、制限条件は実施形態ごとに様々である。更に、開発作業は非常に複雑であり且つ時間がかかるが、そのような開発作業は、本開示の利益を享受する当業者にとってルーチンタスクに過ぎないことは明らかである。
【００１５】
ここで、不必要な詳細が本発明を不明りょうにすることを防ぐよう、本発明に従う方法及びノードに密接に関連する装置構造及び／又は処理ステップのみが図面において示され、本発明とほとんど関係ない他の詳細は省略されることに留意されたい。
【００１６】
本発明に従うネットワークにおけるルートディスカバリのための方法は、以下で図面を参照して記載される。
【００１７】
図１は、本発明の実施形態に従うネットワークにおけるルートディスカバリのための方法を説明するフローチャートである。
【００１８】
最初に、ステップＳ１１０で、ネットワークにおけるノードのレベルが分類される。
【００１９】
ステップＳ１１０における工程を通じて、ネットワークにおけるノードの夫々は様々なレベルに分類される。当業者には明らかなように、必要に応じて多種多様な態様でネットワークにおけるノードのレベルを分類することが可能である。
【００２０】
本発明の好ましい実施形態に従って、ネットワークにおけるノードのレベルが分類される場合に、最初にノードのコストが計算されてよく、次いでノードのレベルがコストに応じて分類されてよい。
【００２１】
本発明の好ましい実施形態に従って、ノードのコストは、次のコスト方程式（１）により計算されてよい：
cost＝a×remaining_energy＋b×hop_count＋c×neighbor_density＋d×bandwidth （１）
costは当該ノードのコストを表し、remaining_energyは当該ノードの残りのエネルギを表し、hop_countは当該ノードからあて先ノードへの最小ホップ数を表し、neighbor_densityは当該ノードの隣接ノード密度を表し、bandwidthは当該ノードのバンド幅を表し、a、b、c及びdは重み係数を表す。
【００２２】
当業者には明らかなように、上記の重み係数a、b、c及びdは、適用場面の必要条件に従って決定される。例えば、hop_countの重み係数bが最小であるよう設定される場合、それは、その適用場面におけるhop_countの重要性が最低であることを意味する。対照的に、hop_countの重み係数bが最大であるよう設定される場合、それは、その適用場面におけるhop_countの重要性が最高であることを意味する。
【００２３】
また、当業者には明らかなように、他のパラメータ及び対応する重み係数が、上記のパラメータremaining_energy、hop_count、neighbor_density及びbandwidthに加えて、適用場面の必要条件に従ってコスト方程式に加えられるよう考慮されてよい。
【００２４】
本発明の好ましい実施形態に従って、ノードのコストは初期設定段階で計算されてよい。初期設定段階では、ノードごとに、ある期間の学習の後、現在のノードからあて先ノードへのコストに関する情報が取得され得る。具体的に、初期設定段階では、ノードは、データパケットをあて先ノードへ送信することによって、現在のノードからあて先ノードへのコストのサンプル値を知り収集する。それによって、ノードのレベルは、得られたノードのコストに応じて分類され得る。
【００２５】
本発明の好ましい実施形態に従って、ノードのコストはデータ伝送の工程において更新されてよい。具体的に、データ伝送段階では、ノードがデータパケットを送信又は転送するたびに、現在のコスト値がこの工程から一度計算され、計算された現在のコスト値はノードのコストサンプル空間に加えられる。次いで、ノードのコストは、コストサンプル空間に従って更新される。このように、コスト情報の実時間の性能が改善され、ネットワークの実時間の状態変化が適応され得る。
【００２６】
次に、ステップＳ１２０で、現在のノードに隣接するノードからのルート要求（ＲＲＥＱ）パケットが受信される。
【００２７】
本発明の実施形態におけるＲＲＥＱパケットは、最後のホップノード（すなわち、現在のノードに隣接し、このＲＲＥＱパケットを送信するノード）のノードレベル情報が、現在のノードによって受信されるＲＲＥＱパケットに含まれる点で、先行技術におけるＲＲＥＱパケットと相違する。
【００２８】
次に、ステップＳ１３０で、受信されたルート要求パケットに含まれるノードレベル情報によって示されるノードレベルは、現在のノードのレベルと比較される。言い換えると、ステップＳ１３０では、現在のノードのレベルが最後のホップノードのレベルよりも高いかどうかが判断される。
【００２９】
ステップＳ１３０で現在のノードのレベルが最後のホップノードのレベルよりも高いと判断された場合、処理はステップＳ１４０に進む。
【００３０】
ステップＳ１３０で現在のノードのレベルが最後のホップノードのレベルよりも高くないと判断された場合、処理は終了する。
【００３１】
本発明の好ましい実施形態に従って、現在のノードのレベルが、ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルよりも高くない場合に、ルート要求パケットは、転送されるのではなく、捨てられてよい。
【００３２】
処理がステップＳ１４０に進むと、ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルは、ステップＳ１４０で、現在のノードのレベルであるよう更新される。
【００３３】
このように、現在のノードのレベルを示すノードレベル情報が、更新されたルート要求パケットに含まれる。
【００３４】
最後に、ステップＳ１５０で、更新されたルート要求パケットは、現在のノードに隣接する他のノードへ転送される。
【００３５】
本発明に従うネットワークにおけるルートディスカバリのための上記方法によれば、ＲＲＥＱパケットの送信を有効に減らすことができ、データパケットのコリジョンの可能性は低下し、ネットワーク性能は改善され得る。本発明に従う方法は、ネットワークトポロジが極めてゆっくりと変化し且つあて先ノードが決定されているところの適用場面におけるインテリジェントメーター読取システムに特に適している。
【００３６】
本発明の好ましい実施形態に従って、ルーティング確立の段階で、ソースノードがルート要求パケットを自身に隣接するノードへ送信し始める前に、ソースノードのレベルに関する情報はノードレベル情報としてルート要求パケットに加えられる。その後に、ソースノードは、修正されたルート要求パケットを自身に隣接するノードへ送信する。
【００３７】
本発明の好ましい実施形態に従って、あて先ノードが自身に隣接するノードからルート要求パケットを受信した後、ルートディスカバリが行われる。
【００３８】
以降、本発明に従うネットワークにおけるルートディスカバリのための方法が、図２を参照して詳細に記載される。
【００３９】
図２は、本発明の実施形態に従うネットワークにおけるルートディスカバリの実施の具体例を表す図である。図２に示されるネットワークには、ソースノード、中間ノード及びあて先ノードが含まれている。ソースノード及びあて先ノードの位置が図２（ａ）に示されている。
【００４０】
ノードのコストが初期設定段階で計算され、次いで、ノードのレベルが、計算されたコストに応じて分類される。説明の便宜上、ノードのコストが計算される場合に、現在のノードからあて先ノードへの最小ホップ数のみが考慮される。すなわち、上記のコスト方程式（１）において、重み係数a、c及びdは零に設定され、重み係数bは１に設定される。図２（ｂ）に示されるように、ネットワークにおけるノードは様々なレベルに分類される。ここで、ソースノードのレベルはレベル４である。目下の例では、ノードのレベル数が高ければ高いほど、ノードのレベルは低い。
【００４１】
ルーティング確立の段階で、ソースノードが自身に隣接するノードへルート要求パケットを送信し始める前に、ソースノードのレベル（レベル４）に関する情報は、ノードレベル情報としてルート要求パケットに加えられる。その後に、ソースノードは、修正されたルート要求パケットを自身に隣接するノードへ送信する。
【００４２】
レベル４のノースノードに隣接し、レベル３、４及び５を夫々有する中間ノードは、ソースノードからルート要求パケットを受信する。ソースノードのレベル（レベル４）を示すノードレベル情報は、それらの中間ノードによって受信されるルート要求パケットに含まれる。次いで、ソースノードからルート要求パケットを受信した中間ノードは、受信されたルート要求パケットに含まれるノードレベル情報によって示されるノードレベルを、現在のノードのレベルと比較して、現在のノードのレベルがソースノードのレベルよりも高いかどうかを判断する。
【００４３】
レベル３の中間ノードは、現在のノードのレベルがレベル４を有するソースノードのレベルよりも高いと判断し、次いで、ルート要求パケットに含まれるノードレベル情報によって示されるノードレベル（レベル４）を現在のノードのレベル（レベル３）であるよう更新する。
【００４４】
このようにして、現在のノードのレベル（レベル３）を示すノードレベル情報は、更新されたルート要求パケットに含まれる。
【００４５】
その後に、レベル３を有する中間ノードは、更新されたルート要求パケットを、この中間ノードに隣接する他のノードへ転送する。
【００４６】
一方、レベル４又は５を有する中間ノードは、現在のノードのレベルがレベル４を有するソースノードのレベルよりも高くない（すなわち、ソースノードのレベル以下である）と判断し、次いで、ルート要求パケットを転送するのではなく捨てる。
【００４７】
同様に、現在のノードが最後のホップノードからルート要求パケットを受信した場合に、現在のノードは、最初に、現在のノードのレベルが最後のホップノードのレベルよりも高いかどうかを判断する。現在のノードのレベルが最後のホップノードのレベルよりも高い場合には、現在のノードは自身のレベルをルート要求パケット内に更新し、次いで、更新されたルート要求パケットを次のホップノードへ転送する。現在のノードが最後のホップノードのレベルよりも高くない場合には、ルート要求パケットは転送されずに捨てられる。
【００４８】
最後に、図２（ｃ）に示されるように、あて先ノードが自身に隣接するノードからルート要求パケットを受信する場合に、ソースノードからあて先ノードへのルートディカバリが行われる。
【００４９】
本発明の実施形態に従うネットワークにおけるルートディスカバリのためのノードは、以下で図面を参照して詳細に記載される。
【００５０】
図３は、本発明の実施形態に従うネットワークにおけるルートディスカバリのためのノード３００を説明するブロック図である。
【００５１】
図３に示されるように、本発明の実施形態に従うノード３００は、レベル分類部３００と、受信部３２０と、比較部３３０と、更新部３４０と、転送部３５０とを有する。
【００５２】
レベル分類部３１０は、ノード３００のレベルを分類するよう構成される。
【００５３】
受信部３２０は、ノード３００に隣接するノードからルート要求パケットを受信するよう構成される。
【００５４】
比較部３３０は、受信部３２０によって受信されたルート要求パケットに含まれるノードレベル情報によって示されるノードレベルを、レベル分類部３１０によって得られたノード３００のレベルと比較するよう構成される。
【００５５】
更新部３４０は、ノード３００のレベルが、ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルよりも高い場合に、ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルをノード３００のレベルであるように更新するよう構成される。
【００５６】
転送部３５０は、更新部３４０によって更新されたルート要求パケットを、ノード３００に隣接する他のノードへ転送するよう構成される。
【００５７】
本発明の好ましい実施形態に従って、レベル分類部３１０は、ノード３００のコストを計算するコスト計算部（図示せず。）を更に有してよい。レベル分類部３１０は、コスト計算部によって計算されたコストに応じて、ノード３００のレベルを分類する。
【００５８】
本発明の好ましい実施形態に従って、コスト計算部は、上記のコスト方程式（１）によりノード３００のコストを計算してよい。
【００５９】
本発明の好ましい実施形態に従って、コスト計算部は、初期設定段階でノード３００のコストを計算してよい。
【００６０】
本発明の好ましい実施形態に従って、コスト計算部は、ノード３００によるデータ伝送の工程においてノード３００のコストを更新してよい。
【００６１】
ノード３００における上記の夫々のユニットの様々な特定の実施は、先に詳細に記載されており、従って、その説明は、ここでは繰り返されない。
【００６２】
明らかに、本発明に従う上記の方法の夫々の動作工程は、機械可読記憶媒体に記憶されるコンピュータ実行可能なプログラムの態様で、実施されてよい。
【００６３】
そして、本発明の対象は、上記のコンピュータ実行可能なプログラムが坦持される記憶媒体が、コンピュータ実行可能なプログラムを読み出して実行するコンピュータ又は中央処理演算装置（ＣＰＵ）を備えるシステム又は装置へ直接に又は間接に提供される態様で、実施可能である。このとき、本発明の実施は、システム又は装置がプログラムを実行する機能を有する限りプログラムに限定されず、プログラムは、オブジェクト指向プログラム、インタープリタによって実行されるプログラム、オペレーティングシステムへ提供されるスクリプトプログラム等の任意の形態であってよい。
【００６４】
上記の機械可読記憶媒体は、様々なメモリ及び記憶ユニット、半導体素子、光ディスク、磁気ディスク及び光磁気ディスク等のディスク、並びに、情報を記憶するのに適したその他の媒体を含むが、これらに限られない。
【００６５】
更に、本発明は、コンピュータを通じてインターネット上の対応するウェブサイトに接続し、本発明に従うコンピュータ実行可能なプログラムをコンピュータにダウンロードしてインストールし、そのプログラムを実行することによって、実施されてもよい。
【００６６】
図４は、本発明の実施形態に従う方法及び／又はノードが実施され得る汎用のパーソナルコンピュータの構成例を表すブロック図である。
【００６７】
図４に示されるように、ＣＰＵ１３０１は、読出専用メモリ（ＲＯＭ）１３０２に記憶されているプログラム又は記憶部１３０８からランダムアクセスメモリ（ＲＡＭ）１３０３に読み込まれたプログラムに従って、様々な処理を実行する。ＲＡＭ１３０３には、必要に応じて、様々な処理を実行する際にＣＰＵ１３０１に必要とされるデータ等も格納される。ＣＰＵ１３０１、ＲＯＭ１３０２及びＲＡＭ１３０３は、バス１３０４を介して互いに接続されている。入出力インターフェース１３０５もバス１３０４へ接続されている。
【００６８】
入出力インターフェース１３０５には、次の構成要素、すなわち、キーボード、マウス等を含む入力部１３０６と、陰極線管（ＣＲＴ）及び液晶ディスプレイ（ＬＣＤ）等のディスプレイ、スピーカ等を含む出力部１３０７と、ハードディスク等を含む記憶部１３０８と、ＬＡＮカード等のネットワークインターフェースカード、モデム等を含む通信部１３０９とが接続されている。通信部１３０９は、インターネット等のネットワークを介して通信処理を実行する。必要に応じて、ドライブ１３１０が入出力インターフェース１３０５へ接続されてもよい。磁気ディスク、光ディスク、光磁気ディスク、半導体メモリ等のリムーバブル媒体１３１１が、必要に応じて、ドライブ１３１０に実装されて、リムーバブル媒体１３１１から読み出されたコンピュータプログラムが、記憶部１３０８にインストールされる。
【００６９】
上記の一連の処理がソフトウェアで実施される場合に、そのソフトウェアを構成するプログラムは、インターネット等のネットワーク又はリムーバブル媒体１３１１等の記憶媒体からインストールされる。
【００７０】
当業者には明らかなように、記憶媒体は、プログラムが記憶され且つ装置とは別に分配されてプログラムをユーザに提供する、図４に示されるリムーバブル媒体１３１１に限定されない。リムーバブル媒体１３１１の例には、フロッピー（登録商標）ディスクを含む磁気ディスクと、コンパクトディスク読出専用メモリ（ＣＤ−ＲＯＭ）及びデジタルバーサタイルディスク（ＤＶＤ）を含む光ディスクと、ミニディスク（登録商標）（ＭＤ）を含む光磁気ディスクと、半導体メモリとがある。代替的に、記憶媒体は、ＲＯＭ１３０２、記憶部１３０８に含まれるハードディスク等であってよい。このとき、プログラムは記憶媒体に記憶され、記憶媒体は当該記憶媒体を含む装置とともにユーザに分配される。
【００７１】
本発明のノード及び方法において、夫々の構成要素又はステップが分解及び／又は再結合されてよいことは明らかである。そのような分解及び／又は再結合は、本発明の同等の解決手段と考えられるべきである。そして、上記の一連の処理を実行するステップは、もちろん記述されている順序で実行されてよいが、それは必須ではない。一部のステップは、互いに同時に又は独立して実行されてよい。
【００７２】
本発明の実施形態について図面を参照して記載してきたが、当然に、上記の実施形態は本発明を説明するためにのみ用いられ、本発明の限定として解されるべきではない。当業者は、本発明の技術的範囲内で変形及び代替を上記の実施形態に対して行うことができる。従って、本発明の技術的範囲は、添付の特許請求の範囲及びその均等によってのみ定義される。
【００７３】
以上の実施形態に関し、更に以下の付記を開示する。
（付記１）
ネットワークにおけるルートディスカバリのための方法であって、
前記ネットワークにおけるノードのレベルを分類し、
前記ノードに隣接するノードからルート要求パケットを受信し、
受信された前記ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルを前記ノードのレベルと比較し、
前記ノードのレベルが前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルよりも高い場合に、前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルを前記ノードのレベルであるよう更新し、
更新された前記ルート要求パケットを前記ノードに隣接する他のノードへ転送する、方法。
（付記２）
前記ネットワークにおけるノードのレベルを分類することは、
前記ノードのコストを計算し、
前記コストに応じて前記ノードのレベルを分類すること
をさらに含む、付記１に記載の方法。
（付記３）
前記ノードのコストは、
cost＝a×remaining_energy＋b×hop_count＋c×neighbor_density＋d×bandwidth
のコスト方程式により計算され、costは前記ノードのコストを表し、remaining_energyは前記ノードの残りのエネルギを表し、hop_countは前記ノードからあて先ノードへの最小ホップ数を表し、neighbor_densityは前記ノードの隣接ノード密度を表し、bandwidthは前記ノードのバンド幅を表し、a、b、c及びdは重み係数を表す、
付記２に記載の方法。
（付記４）
前記ノードのコストは、初期設定段階で計算される、
付記２又は３に記載の方法。
（付記５）
前記ノードのコストは、データ伝送の工程において更新される、
付記２又は３に記載の方法。
（付記６）
前記ノードのレベルが前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルよりも高くない場合に、前記ルート要求パケットを捨てる、
付記１に記載の方法。
（付記７）
ソースノードであるノードによって、前記ルート要求パケットに対してノードレベル情報として前記ソースノードのレベルに関する情報を加え、
前記ソースノードに隣接するノードへ前記ルート要求パケットを送信する、
付記１に記載の方法。
（付記８）
あて先ノードによって、該あて先ノードに隣接するノードからのルート要求パケットが受信された後、前記ルートディスカバリを行う、
付記１に記載の方法。
（付記９）
ネットワークにおけるルートディスカバリのためのノードであって、
当該ノードのレベルを分類するレベル分類部と、
当該ノードに隣接するノードからルート要求パケットを受信する受信部と、
前記受信部によって受信された前記ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルを、前記レベル分類部によって得られた当該ノードのレベルと比較する比較部と、
前記ノードのレベルが前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルよりも高い場合に、前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルを前記ノードのレベルであるよう更新する更新部と、
前記更新部によって更新された前記ルート要求パケットを当該ノードに隣接する他のノードへ転送する転送部と
を有するノード。
（付記１０）
前記レベル分類部は、当該ノードのコストを計算するコスト計算部を有し、該コスト計算部によって計算された前記コストに応じて当該ノードのレベルを分類する、
付記９に記載のノード。
（付記１１）
前記コスト計算部は、
cost＝a×remaining_energy＋b×hop_count＋c×neighbor_density＋d×bandwidth
のコスト方程式により当該ノードのコストを計算し、costは当該ノードのコストを表し、remaining_energyは当該ノードの残りのエネルギを表し、hop_countは当該ノードからあて先ノードへの最小ホップ数を表し、neighbor_densityは当該ノードの隣接ノード密度を表し、bandwidthは当該ノードのバンド幅を表し、a、b、c及びdは重み係数を表す、
付記１０に記載のノード。
（付記１２）
前記コスト計算部は、初期設定段階で当該ノードのコストを計算する、
付記１０又は１１に記載のノード。
（付記１３）
前記コスト計算部は、当該ノードによるデータ伝送の工程において当該ノードのコストを更新する、
付記１０又は１１に記載のノード。
（付記１４）
コンピュータによって読み出されて実行される場合に、該コンピュータに、付記１乃至８のうちいずれか１つに記載の方法を実行させることができる機械可読命令コードを記憶するプログラムプロダクト。
（付記１５）
付記１４に記載のプログラムプロダクトが坦持される機械可読記憶媒体。
【符号の説明】
【００７４】
ＳＲＣ ソースノード
ＳＩＮＫ あて先ノード
３００ ノード
３１０ レベル分類部
３２０ 受信部
３３０ 比較部
３４０ 更新部
３５０ 転送部
１３０１ ＣＰＵ
１３０２ 読出専用メモリ（ＲＯＭ）
１３０３ ランダムアクセスメモリ（ＲＡＭ）
１３０４ バス
１３０５ 入出力インターフェース
１３０６ 入力部
１３０７ 出力部
１３０８ 記憶部
１３０９ 通信部
１３１０ ドライブ
１３１１ リムーバブル媒体
【特許請求の範囲】
【請求項１】
ネットワークにおけるルートディスカバリのための方法であって、
前記ネットワークにおけるノードのレベルを分類し、
前記ノードに隣接するノードからルート要求パケットを受信し、
受信された前記ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルを前記ノードのレベルと比較し、
前記ノードのレベルが前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルよりも高い場合に、前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルを前記ノードのレベルであるよう更新し、
更新された前記ルート要求パケットを前記ノードに隣接する他のノードへ転送する、方法。
【請求項２】
前記ネットワークにおけるノードのレベルを分類することは、
前記ノードのコストを計算し、
前記コストに応じて前記ノードのレベルを分類すること
をさらに含む、請求項１に記載の方法。
【請求項３】
前記ノードのコストは、
cost＝a×remaining_energy＋b×hop_count＋c×neighbor_density＋d×bandwidth
のコスト方程式により計算され、costは前記ノードのコストを表し、remaining_energyは前記ノードの残りのエネルギを表し、hop_countは前記ノードからあて先ノードへの最小ホップ数を表し、neighbor_densityは前記ノードの隣接ノード密度を表し、bandwidthは前記ノードのバンド幅を表し、a、b、c及びdは重み係数を表す、
請求項２に記載の方法。
【請求項４】
前記ノードのコストは、初期設定段階で計算される、
請求項２又は３に記載の方法。
【請求項５】
前記ノードのコストは、データ伝送の工程において更新される、
請求項２又は３に記載の方法。
【請求項６】
ネットワークにおけるルートディスカバリのためのノードであって、
当該ノードのレベルを分類するレベル分類部と、
当該ノードに隣接するノードからルート要求パケットを受信する受信部と、
前記受信部によって受信された前記ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルを、前記レベル分類部によって得られた当該ノードのレベルと比較する比較部と、
前記ノードのレベルが前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルよりも高い場合に、前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルを前記ノードのレベルであるよう更新する更新部と、
前記更新部によって更新された前記ルート要求パケットを当該ノードに隣接する他のノードへ転送する転送部と
を有するノード。
【請求項７】
前記レベル分類部は、当該ノードのコストを計算するコスト計算部を有し、該コスト計算部によって計算された前記コストに応じて当該ノードのレベルを分類する、
請求項６に記載のノード。
【請求項８】
前記コスト計算部は、
cost＝a×remaining_energy＋b×hop_count＋c×neighbor_density＋d×bandwidth
のコスト方程式により当該ノードのコストを計算し、costは当該ノードのコストを表し、remaining_energyは当該ノードの残りのエネルギを表し、hop_countは当該ノードからあて先ノードへの最小ホップ数を表し、neighbor_densityは当該ノードの隣接ノード密度を表し、bandwidthは当該ノードのバンド幅を表し、a、b、c及びdは重み係数を表す、
請求項７に記載のノード。
【請求項９】
前記コスト計算部は、初期設定段階で当該ノードのコストを計算する、
請求項７又は８に記載のノード。
【請求項１０】
前記コスト計算部は、当該ノードによるデータ伝送の工程において当該ノードのコストを更新する、
請求項７又は８に記載のノード。
【請求項１】
ネットワークにおけるルートディスカバリのための方法であって、
前記ネットワークにおけるノードのレベルを分類し、
前記ノードに隣接するノードからルート要求パケットを受信し、
受信された前記ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルを前記ノードのレベルと比較し、
前記ノードのレベルが前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルよりも高い場合に、前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルを前記ノードのレベルであるよう更新し、
更新された前記ルート要求パケットを前記ノードに隣接する他のノードへ転送する、方法。
【請求項２】
前記ネットワークにおけるノードのレベルを分類することは、
前記ノードのコストを計算し、
前記コストに応じて前記ノードのレベルを分類すること
をさらに含む、請求項１に記載の方法。
【請求項３】
前記ノードのコストは、
cost＝a×remaining_energy＋b×hop_count＋c×neighbor_density＋d×bandwidth
のコスト方程式により計算され、costは前記ノードのコストを表し、remaining_energyは前記ノードの残りのエネルギを表し、hop_countは前記ノードからあて先ノードへの最小ホップ数を表し、neighbor_densityは前記ノードの隣接ノード密度を表し、bandwidthは前記ノードのバンド幅を表し、a、b、c及びdは重み係数を表す、
請求項２に記載の方法。
【請求項４】
前記ノードのコストは、初期設定段階で計算される、
請求項２又は３に記載の方法。
【請求項５】
前記ノードのコストは、データ伝送の工程において更新される、
請求項２又は３に記載の方法。
【請求項６】
ネットワークにおけるルートディスカバリのためのノードであって、
当該ノードのレベルを分類するレベル分類部と、
当該ノードに隣接するノードからルート要求パケットを受信する受信部と、
前記受信部によって受信された前記ルート要求パケットに含まれるノードレベル情報によって示されるノードレベルを、前記レベル分類部によって得られた当該ノードのレベルと比較する比較部と、
前記ノードのレベルが前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルよりも高い場合に、前記ルート要求パケットに含まれる前記ノードレベル情報によって示される前記ノードレベルを前記ノードのレベルであるよう更新する更新部と、
前記更新部によって更新された前記ルート要求パケットを当該ノードに隣接する他のノードへ転送する転送部と
を有するノード。
【請求項７】
前記レベル分類部は、当該ノードのコストを計算するコスト計算部を有し、該コスト計算部によって計算された前記コストに応じて当該ノードのレベルを分類する、
請求項６に記載のノード。
【請求項８】
前記コスト計算部は、
cost＝a×remaining_energy＋b×hop_count＋c×neighbor_density＋d×bandwidth
のコスト方程式により当該ノードのコストを計算し、costは当該ノードのコストを表し、remaining_energyは当該ノードの残りのエネルギを表し、hop_countは当該ノードからあて先ノードへの最小ホップ数を表し、neighbor_densityは当該ノードの隣接ノード密度を表し、bandwidthは当該ノードのバンド幅を表し、a、b、c及びdは重み係数を表す、
請求項７に記載のノード。
【請求項９】
前記コスト計算部は、初期設定段階で当該ノードのコストを計算する、
請求項７又は８に記載のノード。
【請求項１０】
前記コスト計算部は、当該ノードによるデータ伝送の工程において当該ノードのコストを更新する、
請求項７又は８に記載のノード。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１２−７０３７６（Ｐ２０１２−７０３７６Ａ）
【公開日】平成２４年４月５日（２０１２．４．５）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１１−２０３２６７（Ｐ２０１１−２０３２６７）
【出願日】平成２３年９月１６日（２０１１．９．１６）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２４年４月５日（２０１２．４．５）
【国際特許分類】
【出願番号】特願２０１１−２０３２６７（Ｐ２０１１−２０３２６７）
【出願日】平成２３年９月１６日（２０１１．９．１６）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]