アドホックネットワークにおけるパケット送信経路設定方法およびこれを用いたネットワーク装置
【課題】アドホックネットワークにおけるパケット送信経路設定方法およびこれを用いたネットワーク装置を提供する。
【解決手段】パケット送信経路設定方法は、予め設定されたホップ数Ｎ（Ｎは２以上の正数）によってソースノードと目的ノードとの間に少なくとも１つのノードを含むＮ−１個のルーティング領域を設定するステップと、チャネル利得に基づき、設定されたそれぞれのルーティング領域内のいずれか１つのノードをパケットリレーノードとして決定するステップとを含む。
【解決手段】パケット送信経路設定方法は、予め設定されたホップ数Ｎ（Ｎは２以上の正数）によってソースノードと目的ノードとの間に少なくとも１つのノードを含むＮ−１個のルーティング領域を設定するステップと、チャネル利得に基づき、設定されたそれぞれのルーティング領域内のいずれか１つのノードをパケットリレーノードとして決定するステップとを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アドホックネットワークにおけるパケットの送信経路設定に関し、より詳細には、送信されるパケットの許容可能な遅延時間およびノード間のチャネル状態に基づいてパケットの送信経路を決定することで、パケットの送信経路を最適化することができるパケット送信経路設定方法およびこれを実行するためのネットワーク装置に関する。
【背景技術】
【０００２】
一般的に、無線ネットワークは、特定した基盤網の援助なくノード間のマルチホップルーティングによって互いに通信することができるネットワーク構造を有する。無線ネットワークにおいて、通信は、帯域幅が制限されて低いエネルギーの使用が要求される。
【０００３】
無線ネットワーク、特にアドホック（ａｄ−ｈｏｃ）ネットワークにおいてルーティングプロトコルは、ソース（ｓｏｕｒｃｅ）ノードから目的（ｄｅｓｔｉｎａｔｉｏｎ）ノードまでの効率的なパケット送信経路を決定する。
【０００４】
アドホックネットワークにおいて、従来技術に係るルーティング方法は、ソースまたはリレー（ｒｅｌａｙ）ノードからパケットを受けたノードのうち、目的ノードに最も近いノードが次のホップにおける送信ノードとなってパケットを転送（ｆｏｒｗａｒｄｉｎｇ）するものである。このようなルーティング方法は、ソースノードから目的ノードまで到達するのに所要する総ホップ数を減らすことができる。
【０００５】
しかしながら、このようなルーティング方法は、ネットワーク内に複数のソースノード−目的ノードのペア（Ｓ−Ｄペア）が存在する場合には、パケット送信経路間の衝突が発生する可能性が高い。
【０００６】
さらに、ソースノードは、目的ノードにより近いノードが送信パケットを成功裏に受信できるようにするために、より高い送信電力を要するようになる。したがって、上述したルーティング方法は、電力が制限されるアドホックネットワークに適用し難い。
【特許文献１】特開２００５−１６００２６号公報
【特許文献２】韓国特許出願公開第２００７−０７４１６３号公報
【特許文献３】米国特許出願公開第２００６／１８２１２６号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、前記のような問題点を解決するために案出されたものであって、マルチホップ基盤のアドホックネットワークのソースノードと目的ノードとの間でパケットをリレーするリレーノードを決定するためのパケット送信経路設定方法およびこれを用いたネットワーク装置を提供することを目的とする。
【０００８】
また、本発明は、チャネル利得に基づいた機会的な（Ｏｐｐｏｒｔｕｎｉｓｔｉｃ）パケット送信経路設定方法およびこれを用いたネットワーク装置を提供することを他の目的とする。
【０００９】
また、本発明は、パケット遅延を考慮してホップ数を設定し、設定されたホップ数によってルーティング領域を設定することで、干渉に強く送信電力の調整が可能なパケット送信経路設定方法およびネットワーク装置を提供することを他の目的とする。
【００１０】
さらに、本発明は、パケット遅延と送信電力間に効率的なトレードオフを提供することができるパケット送信経路設定方法およびこれを用いたネットワーク装置を提供することをさらに他の目的とする。
【課題を解決するための手段】
【００１１】
前記の目的を達成するために、本発明の実施形態に係るパケット送信経路設定方法は、予め設定されたホップ数Ｎ（Ｎは２以上の正数）によってソースノードと目的ノードとの間に少なくとも１つのノードを含むＮ−１個のルーティング領域を設定するステップと、チャネル利得に基づいて前記設定されたそれぞれのルーティング領域内のいずれか１つのノードをパケットリレーノードとして決定するステップとを含む。
【００１２】
このとき、前記予め設定されたホップ数Ｎは、送信されるパケットに対して許容可能な遅延時間を基準として決定されるようになる。
【００１３】
このとき、前記Ｎ−１個のルーティング領域それぞれの中心から境界までの距離ｒおよび送信されるパケットに対するホップ距離ｄの比のｒ／ｄは、０よりも大きく０．５よりも小さい任意の値で設定されるようになる。
【００１４】
このとき、前記ソースノードは、前記予め設定されたホップ数Ｎ、ホップ距離、およびルーティング領域中心から境界までの距離ｒに基づいて送信電力を設定することができる。
【００１５】
このとき、前記ルーティング領域内のいずれか１つのノードをパケットリレーノードとして決定するステップは、ソースノードまたは前記ソースノードから送信されたパケットを受信したリレーノードが隣接したルーティング領域内の各ノードに目的ノードのコーディネート情報を含んでいる制御信号を送信し、前記制御信号を受信した各ノードがチャネル利得を推定し、前記推定されたチャネル利得が所定の設定値以上であるノードを次のパケットリレーノードとして決定することを含むことができる。
【００１６】
このとき、Ｎ−１個のルーティング領域のうちから目的ノードと隣接したルーティング領域内のパケットリレーノードを決定するステップは、前記目的ノードが前記目的ノードと隣接したルーティング領域内の各ノードにＲＴＳ信号を送信し、前記ＲＴＳ信号を受信した各ノードがチャネル利得を推定し、前記推定されたチャネル利得が所定の設定値以上であるノードをパケットリレーノードとして決定することを含むことができる。
【００１７】
本発明の他の実施形態に係るパケット送信経路設定方法は、ソースノードまたは前記ソースノードから受信されたパケットを送信する第１リレーノードが予め設定された領域内のノードにＲＴＳメッセージを送信するステップと、前記ＲＴＳメッセージを受信した各ノードがチャネル利得を推定するステップと、前記推定されたチャネル利得が所定の設定値以上であるノードが前記推定されたチャネル利得値を含むＣＴＳメッセージを送信するステップと、前記ＣＴＳメッセージを送信するノードが１つである場合には、前記ＣＴＳメッセージを送信したノードを第２リレーノードとして決定するステップとを含む。
【００１８】
本発明のさらに他の実施形態に係るパケット送信経路設定方法は、ソースノードまたは前記ソースノードから受信されたパケットを送信する第１リレーノードが予め設定された領域内のノードにＲＴＳメッセージを送信するステップと、前記ＲＴＳメッセージを受信した各ノードがチャネル利得を推定するステップと、前記推定されたチャネル利得値に対応するバック−オフ時間によって前記推定されたチャネル利得値を含むＣＴＳメッセージを送信するステップと、前記ＣＴＳメッセージを最初に送信したノードを第２リレーノードとして決定するステップとを含む。
【００１９】
本発明のさらに他の実施形態に係るネットワーク装置は、送信パケットに許容される遅延時間に基づいてホップ数を決定するソースノードと、前記ソースノードから目的ノードのコーディネート情報を含んでいる制御信号を受信してチャネル利得を推定し、前記推定されたチャネル利得が所定の設定値以上であれば応答メッセージを前記ソースノードに送信する第１リレーノードと、前記目的ノードからメッセージを受信してチャネル利得を推定し、前記推定されたチャネル利得が所定の設定値以上であれば応答メッセージを前記目的ノードに送信する第２リレーノードとを備える。
【発明の効果】
【００２０】
本発明によれば、マルチホップ基盤のアドホックネットワークのソースノードと目的ノードとの間でパケットをリレーするリレーノードを決定するためのパケット送信経路設定方法およびこれを用いたネットワーク装置を提供することができる効果がある。
【００２１】
また、本発明によれば、チャネル利得に基づいて機会的なパケット送信経路設定方法およびこれを用いたネットワーク装置を提供することができる効果がある。
【００２２】
また、本発明によれば、パケット遅延を考慮してホップ数を設定し、設定されたホップ数によってルーティング領域を設定することで、干渉に強く送信電力の調整が可能なパケット送信経路設定方法およびネットワーク装置を提供することができる効果がある。
【００２３】
さらに、本発明によれば、パケット遅延と送信電力間に効率的なトレードオフを提供することができるパケット送信経路設定方法およびこれを用いたネットワーク装置を提供することができる効果がある。
【発明を実施するための最良の形態】
【００２４】
以下、添付の図面および該当する図面に記載された内容を参照しながら、本発明の実施形態について詳細に説明する。
【００２５】
図１は、アドホックネットワークの一例を示した図である。
【００２６】
図１を参照すれば、アドホックネットワークは、ｎ個のノードがランダム（ｒａｎｄｏｍ）に分布している。アドホックネットワークは、ｎよりも小さいか同じ数のＳ−Ｄペアがランダムに存在している。図１において、ソースノード１−目的ノード１およびソースノード２−目的ノード２は、マルチホップ通信によるルーティングの一例を示している。
【００２７】
下記の説明において、アドホックネットワークのチャネルモデルは、下記の数式１のように定義することができるが、これに制限されることはない。
【００２８】
【数１】
【００２９】
前記の数式１において、ｇｉｊは、
【００３０】
【数２】
【００３１】
を満たすレーリー（Ｒａｙｌｅｉｇｈ）フェージングチャネルを示す。γは経路損失指数（ｐａｔｈ ｌｏｓｓ ｅｘｐｏｎｅｎｔ）であって、２よりも大きい値であると仮定する。一方、チャネル状態情報は、ソースノードなどの送信端では分からず、受信端で測定が可能なものと仮定する。
【００３２】
図２は、本発明の実施形態に係るパケット送信経路設定方法を示したフローチャートである。
【００３３】
図２を参照すれば、本発明の実施形態に係るパケット送信経路設定方法は、予め設定されたホップ数Ｎ（Ｎは２以上の正数）によってソースノードと目的ノードとの間に少なくとも１つのノードを含むＮ−１個のルーティング領域（ｒｅｇｉｏｎ）を設定するルーティング領域設定ステップＳ２０１と、チャネル利得に基づき、設定されたそれぞれのルーティング領域内のいずれか１つのノードをパケットリレーノードとして決定するチャネル利得に基づいた経路設定ステップＳ２０３とを含む。
【００３４】
ルーティング領域を設定するステップＳ２０１において、ホップ数Ｎは、送信されるパケットに対して許容される遅延時間に基づいてソースノードで設定される。このとき、送信されるパケットに対して許容される遅延時間は、システム容量やＳ−Ｄペアあたりの平均送信電力などを考慮して設定されるようになる。したがって、送信されるパケットに対して許容される遅延時間が短いほどホップ数は少なく設定される。
【００３５】
ルーティング領域は、図３に示すように、ソースノード３０１と目的ノード３０９との間に設定される。
【００３６】
図３を参照すれば、それぞれのルーティング領域３０３，３０５，３０７は、少なくとも１つのノードを含む。
【００３７】
ソースノード３０１は、隣接したルーティング領域３０３内において、チャネル利得が所定の設定値以上であるノードのうちのいずれか１つのノードを最初のホップにおけるパケット受信ノードとして決定する。最初のホップにおけるパケット受信ノードは、結局、次のホップ（２番目のホップ）におけるリレーノードとなる。また、２番目のホップで決定されたリレーノードは、隣接したルーティング領域３０５内において、チャネル利得が所定の設定値以上であるノードのうちのいずれか１つを次のホップ（三番目のホップ）におけるリレーノードとして決定される。
【００３８】
このように、本発明に係る実施形態は、１つのルーティング領域内からチャネル利得が優れたノードをリレーノードとして選択することで、ＭＵＤ（Ｍｕｌｔｉ Ｕｓｅｒ Ｄｉｖｅｒｓｉｔｙ）利得を得ることができる。このとき、ＭＵＤ利得は、理論的に、ルーティング領域３０３内のノード数の対数（ｌｏｇａｒｉｔｈｍ）に等しい。
【００３９】
設定されたルーティング領域３０３，３０５，３０７内に十分に多くのノードが存在すれば、チャネル利得が高いノードを選択することができる。
【００４０】
したがって、送信ノードは、チャネル利得に対応して送信電力を減少させることができる。このような送信電力の減少は、より多くのＳ−Ｄペアを収容することができる上に、全体システムの容量を増加させることができる。
【００４１】
目的ノード３０９と隣接したルーティング領域３０７は、目的ノード３０９から受信される信号のチャネル利得が所定の設定値以上であるノードをリレーノードとして決定する。
【００４２】
したがって、目的ノード３０９から２ホップ前のリレーノードは、ルーティング領域３０７内のリレーノードにパケットを送信するようになる。
【００４３】
図４は、図３に示したルーティング領域の決定方法を説明するための図である。
【００４４】
図４を参照すれば、各ルーティング領域は四角形（ｓｑｕａｒｅ）で設定されるようになるが、これに制限されることはない。各ルーティング領域の大きさは下記の数式２に関連する。
【００４５】
【数３】
【００４６】
前記の数式２において、ｒはルーティング領域４０３の中心（Ｘ１，Ｙ１）から境界までの距離、ｄはホップ距離である。ｄおよびｒは、ネットワークの要求条件に応じて予め設定することができる。
【００４７】
ｄは、パケット送信ノード（ソースノードまたはリレーノード）から隣接ルーティング領域４０３内のリレーノードまでの距離、または以前のルーティング領域の中心（Ｘ０，Ｙ０）から次のルーティング領域の中心（Ｘ１，Ｙ１）までの距離である。
【００４８】
このとき、隣接したノードへのホッピング（ｈｏｐｐｉｎｇ）は大きい干渉を引き起こすため、ｒはｄに比べて十分に小さい値となるように設定する。ホップ距離ｄはｒに比べて十分に大きい値であるため、ｄは毎ホップあたり同じ値を有するものと仮定することができる。
【００４９】
アドホックネットワークにおいて、各ノードは、ＧＰＳ装置によって自分のコーディネート（ｃｏｏｒｄｉｎａｔｅ）情報を知っている。したがって、各ノードは、どのようなルーティング領域に属しているのか、またはｄおよびｒに関連する情報を知ることができるのである。
【００５０】
ソースノード３０１およびそれぞれのリレーノードは、予め設定されたホップ数Ｎ、ホップ距離、およびルーティング領域中心から境界までの距離ｒに基づいて送信電力を設定することができる。すなわち、ホップ距離を大きく設定すればこれに対応して送信電力は大きく設定され、ホップ距離を小さく設定すればホップ数Ｎは大きく設定されなければならないが、これに対応して送信電力を小さく設定することができる。
【００５１】
図５は、本発明の他の実施形態に係るパケット送信経路設定方法を示したフローチャートである。
【００５２】
図５を参照すれば、パケット送信経路設定方法は、ソースノードまたはソースノードから受信されたパケットを送信する第１リレーノード５０１が予め設定された領域内のノード５０３にＲＴＳメッセージを送信するステップ５０５と、ＲＴＳメッセージを受信した各ノードがチャネル利得を推定するステップ５０７と、推定されたチャネル利得が所定の設定値よりも大きいノードが推定されたチャネル利得値を含むＣＴＳメッセージを送信するステップ５０９，５１１と、ＣＴＳメッセージを送信するノードが１つである場合には、ＣＴＳメッセージを送信したノードを第２リレーノードと決定してパケットを送信するステップ５１３とを含む。
【００５３】
ステップ５０５で、ソースノード（または第１リレーノード）５０１は、目的ノードのコーディネート情報を含むＲＴＳ（Ｒｅｑｕｅｓｔ Ｔｏ Ｓｅｎｄ）メッセージを隣接ルーティング領域内の各ノード（候補ノード）５０３に送信する。
【００５４】
ステップ５０７で、ルーティング領域内の各候補ノード５０３は、ＲＴＳメッセージを用いてチャネル利得を推定する。
【００５５】
ＲＴＳメッセージおよびＣＴＳメッセージは、パケット送信時に用いる周波数とは異なる任意の周波数を用いて送信することができる。
【００５６】
ステップ５０９で、各ノードは、推定されたチャネル利得が閾値よりも大きいか否かを判断する。ステップ５１１で、チャネル利得が閾値よりも大きいノードは、推定されたチャネル利得値を含むＣＴＳ（Ｃｌｅａｒ Ｔｏ Ｓｅｎｄ）メッセージをソースノード（または第１リレーノード）５０１に送信する。
【００５７】
閾値は、下記の数式３のように表すことができる。
【００５８】
【数４】
【００５９】
前記の数式３において、ｍは、ルーティング領域内に存在するノードの数である。ｍが十分に大きいと仮定すれば、最大のチャネル利得は理論的にｌｏｇｍに等しい。
【００６０】
しかしながら、実際的なｍを考慮すれば、チャネル利得に対する誤差εｉ（εｉ＞０）が発生する。閾値は総ＴＴＨ個が設定されるようになり、チャネル利得に対する誤差εｉは
【００６１】
【数５】
【００６２】
のようになる。
【００６３】
ステップ５１３で、ソースノード（または第１リレーノード）５０１は、ＣＴＳメッセージを送信したノードを次のホップにおけるリレーノードとして決定してパケットを送信する。
【００６４】
ステップ５１５で、ＣＴＳを送信したノードは、パケットが受信されればＡＣＫメッセージを送信する。
【００６５】
もし、予め設定された時間区間内にいずれか１つのノードもＣＴＳメッセージを送信しなければ、閾値はγＴＨ，ｉ＋１に変更される。
【００６６】
図６は、目的ノードにパケットを送信するリレーノードの選択方法を説明するための図である。
【００６７】
図６を参照すれば、目的ノード６０９は予め決定されているため、目的ノード６０９と隣接したルーティング領域６０５内のリレーノード選択は、受信ダイバーシティ利得を考慮して決定される。
【００６８】
すなわち、目的ノード６０９から２ホップの前のリレーノード６０３は、目的ノード６０９と隣接したルーティング領域６０５内の代表ノード６０７にリレーノード決定要請メッセージを送信するのである。
【００６９】
目的ノード６０９から２ホップの前のリレーノード６０３は、Ｎ−２（Ｎは予め決定されたホップ数）番目のルーティング領域６０１内に存在する。さらに、目的ノード６０９と隣接したルーティング領域６０５は、Ｎ−１番目のルーティング領域を示す。
【００７０】
リレーノード決定要請メッセージを受信した代表ノード６０７は、目的ノード６０９にリレーノード決定要請メッセージを伝達する。
【００７１】
目的ノード６０９がリレーノード決定要請メッセージを受信すれば、隣接したルーティング領域６０５内の各ノードにＲＴＳ機能のメッセージを送信する。
【００７２】
ＲＴＳ機能のメッセージは、目的ノードが経路設定のために送信するものである。一般的に、ＲＴＳメッセージは、データを送信するノードから送信するメッセージである。ＲＴＳ機能のメッセージは、目的ノードが経路設定のために送信する点を除けば、ＲＴＳメッセージと同じ機能を有する。
【００７３】
ＲＴＳ機能のメッセージを受信した各ノードは、受信されたＲＴＳ機能のメッセージを用いてチャネル利得を推定する。推定されたチャネル利得が所定の設定値よりも大きいノードが推定されたチャネル利得値を含むＣＴＳ機能のメッセージを目的ノード６０９に送信する。
【００７４】
ＣＴＳ機能のメッセージは、ＲＴＳ機能のメッセージに対応する。したがって、ＣＴＳ機能のメッセージは、データを送信するためのノードから目的ノードに送信する点を除けば、ＣＴＳメッセージと同じ機能を有する。
【００７５】
次に、代表ノード６０７は、ＣＴＳ機能のメッセージを目的ノード６０９に送信したノード（最終ホップにおけるリレーノード）を２ホップ前のリレーノード６０３に知らせる。
【００７６】
この後、２ホップ前のリレーノード６０３は、パケットを最終ホップにおけるリレーノードに送信する。
【００７７】
前記の閾値の変更過程とＣＴＳ機能のメッセージの衝突防止過程は、最終ホップにおけるリレーノード決定過程に同じように適用される。
【００７８】
図７は、図５において、いずれか１つのノードもＣＴＳメッセージを送信しない場合のパケット送信経路設定方法を示したフローチャートである。
【００７９】
図７を参照すれば、予め設定された時間区間内にＣＴＳメッセージを送信するノードがない場合には、閾値が変更される（Ｓ７０１）。ソースノード（または第１リレーノード）５０１は、予め設定された時間区間内にＣＴＳメッセージを受信することができなければ閾値をγＴＨ，ｉ＋１に変更し、変更されたγＴＨ，ｉ＋１を含むＲＴＳメッセージを送信する。
【００８０】
隣接ルーティング領域内の各ノード（候補ノード）５０３は、変更されたγＴＨ，ｉ＋１と推定されたチャネル利得とを比較する（Ｓ７０３）。推定されたチャネル利得が変更されたγＴＨ，ｉ＋１よりも大きいノードは、ＣＴＳメッセージを送信する（Ｓ７０５）。もし、閾値がＴ−１番目に変更された場合にも、ＣＴＳが送信されなければノード決定失敗（ｏｕｔａｇｅ）が発生する（Ｓ７０７）。ノード決定失敗が発生すれば、ルーティング領域内の代表ノードは、ＮＡＣＫメッセージを送信する。ルーティング領域内の代表ノードは、ルーティング領域の中心に位置したノードまたは予め設定されたコーディネーターノードであると言える。
【００８１】
このとき、２つ以上のノードからＣＴＳメッセージを送信する場合には、衝突（ｃｏｌｌｉｓｉｏｎ）が発生することがある。
【００８２】
図８は、２つ以上のノードからＣＴＳメッセージを送信する場合のパケット送信経路設定方法を示したフローチャートである。
【００８３】
図８を参照すれば、ルーティング領域内の各候補ノード５０３は、ＲＴＳメッセージを用いてチャネル利得を推定する（Ｓ８０１）。
【００８４】
前記のように、推定されたチャネル利得が閾値よりも大きいノードは、ＣＴＳメッセージをソースノード（または第１リレーノード）５０１に送信する。
【００８５】
ＣＴＳメッセージを送信したノードは、ルーティング領域内の２つ以上のノードからＣＴＳメッセージが送信されたのか否かを判断する（Ｓ８０３）。このとき、ルーティング領域内の代表ノードが２つ以上のノードからＣＴＳメッセージが送信されたのかを判断し、これをＣＴＳメッセージを送信した各ノードに知らせることができる。
【００８６】
もし、１つのノードからＣＴＳメッセージをソースノード（または第１リレーノード）５０１に送信した場合には、前記のように第２リレーノードが決定される（Ｓ８０５）。
【００８７】
もし、２つ以上のノードからＣＴＳメッセージをソースノード（または第１リレーノード）５０１に送信した場合には、ＣＴＳメッセージを送信した各ノードは、チャネル利得に対応する確率値によってＣＴＳメッセージを再送信する（Ｓ８０７）。
【００８８】
このとき、チャネル利得に対応する確率値は予め設定された値であって、チャネル利得が高いほど１に近い確率値で設定することができる。
【００８９】
本発明の実施形態は、チャネル利得が高いほど高い確率値でＣＴＳメッセージを再送信するため、ＣＴＳメッセージの衝突問題を解決することができる。
【００９０】
図９は、複数の送信ノードが存在する場合の一例を示した図である。
【００９１】
図９は、ルーティング領域９０９内のノード９０５，９０７が２つ以上の送信ノード９０１，９０３からＲＴＳメッセージを受信した場合を示している。
【００９２】
このとき、ルーティング領域９０９内のノード９０５，９０７は、それぞれのＲＴＳメッセージに対するチャネル利得を推定する。
【００９３】
このとき、推定されたチャネル利得が所定の設定値以上であれば、ＲＴＳメッセージを送信したソースノードまたは第１リレーノードの識別情報（ＩＤ）および推定されたチャネル利得値を含んでＣＴＳメッセージを送信する。
【００９４】
このとき、それぞれの送信ノード９０１，９０３は、識別情報によってＣＴＳメッセージを送信したノードを知ることができる。それぞれの送信ノード９０１，９０３は、いずれか１つのノードがチャネル利得が最も良い候補ノードを選択し、他の１つのノードがチャネル利得が二番目に良いノードを選択することで、リンク間の衝突を防ぐことができる。
【００９５】
また、複数の送信ノードが存在する場合に、閾値およびＣＴＳメッセージの衝突に対する処理過程は、１つの送信ノードが存在する場合と同じように処理される。
【００９６】
図１０は、本発明のさらに他の実施形態に係るパケット送信経路設定方法を示したフローチャートである。
【００９７】
図１０を参照すれば、パケット送信経路設定方法は、ソースノードまたはソースノードから受信されたパケットを送信する第１リレーノード１００１が予め設定された領域内のノード１００３にＲＴＳメッセージを送信するステップ１００５と、ＲＴＳメッセージを受信した各ノードがチャネル利得を推定するステップ１００７と、推定されたチャネル利得値に対応するバック−オフ時間によって推定されたチャネル利得値を含むＣＴＳメッセージを送信するステップ１００９，１０１１と、ＣＴＳメッセージを最初に送信したノードを第２リレーノードとして決定するステップ１０１３，１０１５とを含む。
【００９８】
ステップ１００５で、ソースノード（または第１リレーノード）１００１は、目的ノードのコーディネート情報を含むＲＴＳメッセージを隣接ルーティング領域内の候補ノード１００３に送信する。
【００９９】
ステップ１００７で、隣接ルーティング領域内の候補各ノード１００３は、ＲＴＳメッセージを用いてチャネル利得を推定する。
【０１００】
ＲＴＳメッセージおよびＣＴＳメッセージは、パケット送信時に用いる周波数とは異なる任意の周波数を用いて送信することができる。
【０１０１】
ステップ１００９で、隣接ルーティング領域内の候補各ノード１００３は、予め設定されたバック−オフ時間によってタイマー（図示せず）を作動させる。
【０１０２】
バック−オフ時間Ｕは、図１１に示すように、チャネル利得値に基づくユーティリティ関数である。ユーティリティ関数は、チャネル利得値に対して単調減少する特性を有するように任意の関数でモデリングして生成することができる。
【０１０３】
ステップ１００７で、隣接ルーティング領域内の候補各ノード１００３は、ＲＴＳメッセージを２つ以上のソースノードまたは第１リレーノードから受信した場合には、各ＲＴＳメッセージに対するチャネル利得を推定する。
【０１０４】
ステップ１０１１で、バック−オフ時間によって作動したタイマーが０となるノードは、推定されたチャネル利得値を含むＣＴＳメッセージをソースノード（または第１リレーノード）１００１に送信する。
【０１０５】
ステップ１０１３で、ソースノード（または第１リレーノード）９０１は、ＣＴＳメッセージを送信したノードにパケットを送信する。パケットを受信したノードは、ＡＣＫ信号をソースノード（または第１リレーノード）１００１に送信する。
【０１０６】
上述したように、本発明の好ましい実施形態を参照して説明したが、該当の技術分野において熟練した当業者にとっては、特許請求の範囲に記載された本発明の思想および領域から逸脱しない範囲内で、本発明を多様に修正および変更させることができることを理解することができるであろう。すなわち、本発明の技術的範囲は、特許請求の範囲に基づいて定められ、発明を実施するための最良の形態により制限されるものではない。
【図面の簡単な説明】
【０１０７】
【図１】アドホックネットワークの一例を示した図面である。
【図２】本発明の実施形態に係るパケット送信経路設定方法を示したフローチャートである。
【図３】本発明の実施形態に係るルーティング領域設定例を示した図である。
【図４】図３に示したルーティング領域の決定方法を説明するための図である。
【図５】本発明の他の実施形態に係るパケット送信経路設定方法を示したフローチャートである。
【図６】目的ノードにパケットを送信するリレーノードの選択方法を説明するための図である。
【図７】図５において、いずれか１つのノードもＣＴＳメッセージを送信しない場合のパケット送信経路設定方法を示したフローチャートである。
【図８】２つ以上のノードにＣＴＳメッセージを送信する場合のパケット送信経路設定方法を示したフローチャートである。
【図９】複数の送信ノードが存在する場合の一例を示した図である。
【図１０】本発明のさらに他の実施形態に係るパケット送信経路設定方法を示したフローチャートである。
【図１１】本発明の実施形態に係るバック−オフ時間に対するユーティリティ関数の一例を示した図である。
【符号の説明】
【０１０８】
３０１ ソースノード
３０３，３０５，３０７ ルーティング領域
３０９ 目的ノード
４０３ ルーティング領域
５０１ ソースノード（またはリレーノード）
５０３ 候補ノード
６０１ ルーティング領域
６０３ リレーノード
６０５ ルーティング領域
６０７ 代表ノード
６０９ 目的ノード
９０１，９０３ 送信ノード
９０５，９０７ ノード
９０９ ルーティング領域
１００１ ソースノード（またはリレーノード）
１００３ 候補ノード
【技術分野】
【０００１】
本発明は、アドホックネットワークにおけるパケットの送信経路設定に関し、より詳細には、送信されるパケットの許容可能な遅延時間およびノード間のチャネル状態に基づいてパケットの送信経路を決定することで、パケットの送信経路を最適化することができるパケット送信経路設定方法およびこれを実行するためのネットワーク装置に関する。
【背景技術】
【０００２】
一般的に、無線ネットワークは、特定した基盤網の援助なくノード間のマルチホップルーティングによって互いに通信することができるネットワーク構造を有する。無線ネットワークにおいて、通信は、帯域幅が制限されて低いエネルギーの使用が要求される。
【０００３】
無線ネットワーク、特にアドホック（ａｄ−ｈｏｃ）ネットワークにおいてルーティングプロトコルは、ソース（ｓｏｕｒｃｅ）ノードから目的（ｄｅｓｔｉｎａｔｉｏｎ）ノードまでの効率的なパケット送信経路を決定する。
【０００４】
アドホックネットワークにおいて、従来技術に係るルーティング方法は、ソースまたはリレー（ｒｅｌａｙ）ノードからパケットを受けたノードのうち、目的ノードに最も近いノードが次のホップにおける送信ノードとなってパケットを転送（ｆｏｒｗａｒｄｉｎｇ）するものである。このようなルーティング方法は、ソースノードから目的ノードまで到達するのに所要する総ホップ数を減らすことができる。
【０００５】
しかしながら、このようなルーティング方法は、ネットワーク内に複数のソースノード−目的ノードのペア（Ｓ−Ｄペア）が存在する場合には、パケット送信経路間の衝突が発生する可能性が高い。
【０００６】
さらに、ソースノードは、目的ノードにより近いノードが送信パケットを成功裏に受信できるようにするために、より高い送信電力を要するようになる。したがって、上述したルーティング方法は、電力が制限されるアドホックネットワークに適用し難い。
【特許文献１】特開２００５−１６００２６号公報
【特許文献２】韓国特許出願公開第２００７−０７４１６３号公報
【特許文献３】米国特許出願公開第２００６／１８２１２６号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、前記のような問題点を解決するために案出されたものであって、マルチホップ基盤のアドホックネットワークのソースノードと目的ノードとの間でパケットをリレーするリレーノードを決定するためのパケット送信経路設定方法およびこれを用いたネットワーク装置を提供することを目的とする。
【０００８】
また、本発明は、チャネル利得に基づいた機会的な（Ｏｐｐｏｒｔｕｎｉｓｔｉｃ）パケット送信経路設定方法およびこれを用いたネットワーク装置を提供することを他の目的とする。
【０００９】
また、本発明は、パケット遅延を考慮してホップ数を設定し、設定されたホップ数によってルーティング領域を設定することで、干渉に強く送信電力の調整が可能なパケット送信経路設定方法およびネットワーク装置を提供することを他の目的とする。
【００１０】
さらに、本発明は、パケット遅延と送信電力間に効率的なトレードオフを提供することができるパケット送信経路設定方法およびこれを用いたネットワーク装置を提供することをさらに他の目的とする。
【課題を解決するための手段】
【００１１】
前記の目的を達成するために、本発明の実施形態に係るパケット送信経路設定方法は、予め設定されたホップ数Ｎ（Ｎは２以上の正数）によってソースノードと目的ノードとの間に少なくとも１つのノードを含むＮ−１個のルーティング領域を設定するステップと、チャネル利得に基づいて前記設定されたそれぞれのルーティング領域内のいずれか１つのノードをパケットリレーノードとして決定するステップとを含む。
【００１２】
このとき、前記予め設定されたホップ数Ｎは、送信されるパケットに対して許容可能な遅延時間を基準として決定されるようになる。
【００１３】
このとき、前記Ｎ−１個のルーティング領域それぞれの中心から境界までの距離ｒおよび送信されるパケットに対するホップ距離ｄの比のｒ／ｄは、０よりも大きく０．５よりも小さい任意の値で設定されるようになる。
【００１４】
このとき、前記ソースノードは、前記予め設定されたホップ数Ｎ、ホップ距離、およびルーティング領域中心から境界までの距離ｒに基づいて送信電力を設定することができる。
【００１５】
このとき、前記ルーティング領域内のいずれか１つのノードをパケットリレーノードとして決定するステップは、ソースノードまたは前記ソースノードから送信されたパケットを受信したリレーノードが隣接したルーティング領域内の各ノードに目的ノードのコーディネート情報を含んでいる制御信号を送信し、前記制御信号を受信した各ノードがチャネル利得を推定し、前記推定されたチャネル利得が所定の設定値以上であるノードを次のパケットリレーノードとして決定することを含むことができる。
【００１６】
このとき、Ｎ−１個のルーティング領域のうちから目的ノードと隣接したルーティング領域内のパケットリレーノードを決定するステップは、前記目的ノードが前記目的ノードと隣接したルーティング領域内の各ノードにＲＴＳ信号を送信し、前記ＲＴＳ信号を受信した各ノードがチャネル利得を推定し、前記推定されたチャネル利得が所定の設定値以上であるノードをパケットリレーノードとして決定することを含むことができる。
【００１７】
本発明の他の実施形態に係るパケット送信経路設定方法は、ソースノードまたは前記ソースノードから受信されたパケットを送信する第１リレーノードが予め設定された領域内のノードにＲＴＳメッセージを送信するステップと、前記ＲＴＳメッセージを受信した各ノードがチャネル利得を推定するステップと、前記推定されたチャネル利得が所定の設定値以上であるノードが前記推定されたチャネル利得値を含むＣＴＳメッセージを送信するステップと、前記ＣＴＳメッセージを送信するノードが１つである場合には、前記ＣＴＳメッセージを送信したノードを第２リレーノードとして決定するステップとを含む。
【００１８】
本発明のさらに他の実施形態に係るパケット送信経路設定方法は、ソースノードまたは前記ソースノードから受信されたパケットを送信する第１リレーノードが予め設定された領域内のノードにＲＴＳメッセージを送信するステップと、前記ＲＴＳメッセージを受信した各ノードがチャネル利得を推定するステップと、前記推定されたチャネル利得値に対応するバック−オフ時間によって前記推定されたチャネル利得値を含むＣＴＳメッセージを送信するステップと、前記ＣＴＳメッセージを最初に送信したノードを第２リレーノードとして決定するステップとを含む。
【００１９】
本発明のさらに他の実施形態に係るネットワーク装置は、送信パケットに許容される遅延時間に基づいてホップ数を決定するソースノードと、前記ソースノードから目的ノードのコーディネート情報を含んでいる制御信号を受信してチャネル利得を推定し、前記推定されたチャネル利得が所定の設定値以上であれば応答メッセージを前記ソースノードに送信する第１リレーノードと、前記目的ノードからメッセージを受信してチャネル利得を推定し、前記推定されたチャネル利得が所定の設定値以上であれば応答メッセージを前記目的ノードに送信する第２リレーノードとを備える。
【発明の効果】
【００２０】
本発明によれば、マルチホップ基盤のアドホックネットワークのソースノードと目的ノードとの間でパケットをリレーするリレーノードを決定するためのパケット送信経路設定方法およびこれを用いたネットワーク装置を提供することができる効果がある。
【００２１】
また、本発明によれば、チャネル利得に基づいて機会的なパケット送信経路設定方法およびこれを用いたネットワーク装置を提供することができる効果がある。
【００２２】
また、本発明によれば、パケット遅延を考慮してホップ数を設定し、設定されたホップ数によってルーティング領域を設定することで、干渉に強く送信電力の調整が可能なパケット送信経路設定方法およびネットワーク装置を提供することができる効果がある。
【００２３】
さらに、本発明によれば、パケット遅延と送信電力間に効率的なトレードオフを提供することができるパケット送信経路設定方法およびこれを用いたネットワーク装置を提供することができる効果がある。
【発明を実施するための最良の形態】
【００２４】
以下、添付の図面および該当する図面に記載された内容を参照しながら、本発明の実施形態について詳細に説明する。
【００２５】
図１は、アドホックネットワークの一例を示した図である。
【００２６】
図１を参照すれば、アドホックネットワークは、ｎ個のノードがランダム（ｒａｎｄｏｍ）に分布している。アドホックネットワークは、ｎよりも小さいか同じ数のＳ−Ｄペアがランダムに存在している。図１において、ソースノード１−目的ノード１およびソースノード２−目的ノード２は、マルチホップ通信によるルーティングの一例を示している。
【００２７】
下記の説明において、アドホックネットワークのチャネルモデルは、下記の数式１のように定義することができるが、これに制限されることはない。
【００２８】
【数１】
【００２９】
前記の数式１において、ｇｉｊは、
【００３０】
【数２】
【００３１】
を満たすレーリー（Ｒａｙｌｅｉｇｈ）フェージングチャネルを示す。γは経路損失指数（ｐａｔｈ ｌｏｓｓ ｅｘｐｏｎｅｎｔ）であって、２よりも大きい値であると仮定する。一方、チャネル状態情報は、ソースノードなどの送信端では分からず、受信端で測定が可能なものと仮定する。
【００３２】
図２は、本発明の実施形態に係るパケット送信経路設定方法を示したフローチャートである。
【００３３】
図２を参照すれば、本発明の実施形態に係るパケット送信経路設定方法は、予め設定されたホップ数Ｎ（Ｎは２以上の正数）によってソースノードと目的ノードとの間に少なくとも１つのノードを含むＮ−１個のルーティング領域（ｒｅｇｉｏｎ）を設定するルーティング領域設定ステップＳ２０１と、チャネル利得に基づき、設定されたそれぞれのルーティング領域内のいずれか１つのノードをパケットリレーノードとして決定するチャネル利得に基づいた経路設定ステップＳ２０３とを含む。
【００３４】
ルーティング領域を設定するステップＳ２０１において、ホップ数Ｎは、送信されるパケットに対して許容される遅延時間に基づいてソースノードで設定される。このとき、送信されるパケットに対して許容される遅延時間は、システム容量やＳ−Ｄペアあたりの平均送信電力などを考慮して設定されるようになる。したがって、送信されるパケットに対して許容される遅延時間が短いほどホップ数は少なく設定される。
【００３５】
ルーティング領域は、図３に示すように、ソースノード３０１と目的ノード３０９との間に設定される。
【００３６】
図３を参照すれば、それぞれのルーティング領域３０３，３０５，３０７は、少なくとも１つのノードを含む。
【００３７】
ソースノード３０１は、隣接したルーティング領域３０３内において、チャネル利得が所定の設定値以上であるノードのうちのいずれか１つのノードを最初のホップにおけるパケット受信ノードとして決定する。最初のホップにおけるパケット受信ノードは、結局、次のホップ（２番目のホップ）におけるリレーノードとなる。また、２番目のホップで決定されたリレーノードは、隣接したルーティング領域３０５内において、チャネル利得が所定の設定値以上であるノードのうちのいずれか１つを次のホップ（三番目のホップ）におけるリレーノードとして決定される。
【００３８】
このように、本発明に係る実施形態は、１つのルーティング領域内からチャネル利得が優れたノードをリレーノードとして選択することで、ＭＵＤ（Ｍｕｌｔｉ Ｕｓｅｒ Ｄｉｖｅｒｓｉｔｙ）利得を得ることができる。このとき、ＭＵＤ利得は、理論的に、ルーティング領域３０３内のノード数の対数（ｌｏｇａｒｉｔｈｍ）に等しい。
【００３９】
設定されたルーティング領域３０３，３０５，３０７内に十分に多くのノードが存在すれば、チャネル利得が高いノードを選択することができる。
【００４０】
したがって、送信ノードは、チャネル利得に対応して送信電力を減少させることができる。このような送信電力の減少は、より多くのＳ−Ｄペアを収容することができる上に、全体システムの容量を増加させることができる。
【００４１】
目的ノード３０９と隣接したルーティング領域３０７は、目的ノード３０９から受信される信号のチャネル利得が所定の設定値以上であるノードをリレーノードとして決定する。
【００４２】
したがって、目的ノード３０９から２ホップ前のリレーノードは、ルーティング領域３０７内のリレーノードにパケットを送信するようになる。
【００４３】
図４は、図３に示したルーティング領域の決定方法を説明するための図である。
【００４４】
図４を参照すれば、各ルーティング領域は四角形（ｓｑｕａｒｅ）で設定されるようになるが、これに制限されることはない。各ルーティング領域の大きさは下記の数式２に関連する。
【００４５】
【数３】
【００４６】
前記の数式２において、ｒはルーティング領域４０３の中心（Ｘ１，Ｙ１）から境界までの距離、ｄはホップ距離である。ｄおよびｒは、ネットワークの要求条件に応じて予め設定することができる。
【００４７】
ｄは、パケット送信ノード（ソースノードまたはリレーノード）から隣接ルーティング領域４０３内のリレーノードまでの距離、または以前のルーティング領域の中心（Ｘ０，Ｙ０）から次のルーティング領域の中心（Ｘ１，Ｙ１）までの距離である。
【００４８】
このとき、隣接したノードへのホッピング（ｈｏｐｐｉｎｇ）は大きい干渉を引き起こすため、ｒはｄに比べて十分に小さい値となるように設定する。ホップ距離ｄはｒに比べて十分に大きい値であるため、ｄは毎ホップあたり同じ値を有するものと仮定することができる。
【００４９】
アドホックネットワークにおいて、各ノードは、ＧＰＳ装置によって自分のコーディネート（ｃｏｏｒｄｉｎａｔｅ）情報を知っている。したがって、各ノードは、どのようなルーティング領域に属しているのか、またはｄおよびｒに関連する情報を知ることができるのである。
【００５０】
ソースノード３０１およびそれぞれのリレーノードは、予め設定されたホップ数Ｎ、ホップ距離、およびルーティング領域中心から境界までの距離ｒに基づいて送信電力を設定することができる。すなわち、ホップ距離を大きく設定すればこれに対応して送信電力は大きく設定され、ホップ距離を小さく設定すればホップ数Ｎは大きく設定されなければならないが、これに対応して送信電力を小さく設定することができる。
【００５１】
図５は、本発明の他の実施形態に係るパケット送信経路設定方法を示したフローチャートである。
【００５２】
図５を参照すれば、パケット送信経路設定方法は、ソースノードまたはソースノードから受信されたパケットを送信する第１リレーノード５０１が予め設定された領域内のノード５０３にＲＴＳメッセージを送信するステップ５０５と、ＲＴＳメッセージを受信した各ノードがチャネル利得を推定するステップ５０７と、推定されたチャネル利得が所定の設定値よりも大きいノードが推定されたチャネル利得値を含むＣＴＳメッセージを送信するステップ５０９，５１１と、ＣＴＳメッセージを送信するノードが１つである場合には、ＣＴＳメッセージを送信したノードを第２リレーノードと決定してパケットを送信するステップ５１３とを含む。
【００５３】
ステップ５０５で、ソースノード（または第１リレーノード）５０１は、目的ノードのコーディネート情報を含むＲＴＳ（Ｒｅｑｕｅｓｔ Ｔｏ Ｓｅｎｄ）メッセージを隣接ルーティング領域内の各ノード（候補ノード）５０３に送信する。
【００５４】
ステップ５０７で、ルーティング領域内の各候補ノード５０３は、ＲＴＳメッセージを用いてチャネル利得を推定する。
【００５５】
ＲＴＳメッセージおよびＣＴＳメッセージは、パケット送信時に用いる周波数とは異なる任意の周波数を用いて送信することができる。
【００５６】
ステップ５０９で、各ノードは、推定されたチャネル利得が閾値よりも大きいか否かを判断する。ステップ５１１で、チャネル利得が閾値よりも大きいノードは、推定されたチャネル利得値を含むＣＴＳ（Ｃｌｅａｒ Ｔｏ Ｓｅｎｄ）メッセージをソースノード（または第１リレーノード）５０１に送信する。
【００５７】
閾値は、下記の数式３のように表すことができる。
【００５８】
【数４】
【００５９】
前記の数式３において、ｍは、ルーティング領域内に存在するノードの数である。ｍが十分に大きいと仮定すれば、最大のチャネル利得は理論的にｌｏｇｍに等しい。
【００６０】
しかしながら、実際的なｍを考慮すれば、チャネル利得に対する誤差εｉ（εｉ＞０）が発生する。閾値は総ＴＴＨ個が設定されるようになり、チャネル利得に対する誤差εｉは
【００６１】
【数５】
【００６２】
のようになる。
【００６３】
ステップ５１３で、ソースノード（または第１リレーノード）５０１は、ＣＴＳメッセージを送信したノードを次のホップにおけるリレーノードとして決定してパケットを送信する。
【００６４】
ステップ５１５で、ＣＴＳを送信したノードは、パケットが受信されればＡＣＫメッセージを送信する。
【００６５】
もし、予め設定された時間区間内にいずれか１つのノードもＣＴＳメッセージを送信しなければ、閾値はγＴＨ，ｉ＋１に変更される。
【００６６】
図６は、目的ノードにパケットを送信するリレーノードの選択方法を説明するための図である。
【００６７】
図６を参照すれば、目的ノード６０９は予め決定されているため、目的ノード６０９と隣接したルーティング領域６０５内のリレーノード選択は、受信ダイバーシティ利得を考慮して決定される。
【００６８】
すなわち、目的ノード６０９から２ホップの前のリレーノード６０３は、目的ノード６０９と隣接したルーティング領域６０５内の代表ノード６０７にリレーノード決定要請メッセージを送信するのである。
【００６９】
目的ノード６０９から２ホップの前のリレーノード６０３は、Ｎ−２（Ｎは予め決定されたホップ数）番目のルーティング領域６０１内に存在する。さらに、目的ノード６０９と隣接したルーティング領域６０５は、Ｎ−１番目のルーティング領域を示す。
【００７０】
リレーノード決定要請メッセージを受信した代表ノード６０７は、目的ノード６０９にリレーノード決定要請メッセージを伝達する。
【００７１】
目的ノード６０９がリレーノード決定要請メッセージを受信すれば、隣接したルーティング領域６０５内の各ノードにＲＴＳ機能のメッセージを送信する。
【００７２】
ＲＴＳ機能のメッセージは、目的ノードが経路設定のために送信するものである。一般的に、ＲＴＳメッセージは、データを送信するノードから送信するメッセージである。ＲＴＳ機能のメッセージは、目的ノードが経路設定のために送信する点を除けば、ＲＴＳメッセージと同じ機能を有する。
【００７３】
ＲＴＳ機能のメッセージを受信した各ノードは、受信されたＲＴＳ機能のメッセージを用いてチャネル利得を推定する。推定されたチャネル利得が所定の設定値よりも大きいノードが推定されたチャネル利得値を含むＣＴＳ機能のメッセージを目的ノード６０９に送信する。
【００７４】
ＣＴＳ機能のメッセージは、ＲＴＳ機能のメッセージに対応する。したがって、ＣＴＳ機能のメッセージは、データを送信するためのノードから目的ノードに送信する点を除けば、ＣＴＳメッセージと同じ機能を有する。
【００７５】
次に、代表ノード６０７は、ＣＴＳ機能のメッセージを目的ノード６０９に送信したノード（最終ホップにおけるリレーノード）を２ホップ前のリレーノード６０３に知らせる。
【００７６】
この後、２ホップ前のリレーノード６０３は、パケットを最終ホップにおけるリレーノードに送信する。
【００７７】
前記の閾値の変更過程とＣＴＳ機能のメッセージの衝突防止過程は、最終ホップにおけるリレーノード決定過程に同じように適用される。
【００７８】
図７は、図５において、いずれか１つのノードもＣＴＳメッセージを送信しない場合のパケット送信経路設定方法を示したフローチャートである。
【００７９】
図７を参照すれば、予め設定された時間区間内にＣＴＳメッセージを送信するノードがない場合には、閾値が変更される（Ｓ７０１）。ソースノード（または第１リレーノード）５０１は、予め設定された時間区間内にＣＴＳメッセージを受信することができなければ閾値をγＴＨ，ｉ＋１に変更し、変更されたγＴＨ，ｉ＋１を含むＲＴＳメッセージを送信する。
【００８０】
隣接ルーティング領域内の各ノード（候補ノード）５０３は、変更されたγＴＨ，ｉ＋１と推定されたチャネル利得とを比較する（Ｓ７０３）。推定されたチャネル利得が変更されたγＴＨ，ｉ＋１よりも大きいノードは、ＣＴＳメッセージを送信する（Ｓ７０５）。もし、閾値がＴ−１番目に変更された場合にも、ＣＴＳが送信されなければノード決定失敗（ｏｕｔａｇｅ）が発生する（Ｓ７０７）。ノード決定失敗が発生すれば、ルーティング領域内の代表ノードは、ＮＡＣＫメッセージを送信する。ルーティング領域内の代表ノードは、ルーティング領域の中心に位置したノードまたは予め設定されたコーディネーターノードであると言える。
【００８１】
このとき、２つ以上のノードからＣＴＳメッセージを送信する場合には、衝突（ｃｏｌｌｉｓｉｏｎ）が発生することがある。
【００８２】
図８は、２つ以上のノードからＣＴＳメッセージを送信する場合のパケット送信経路設定方法を示したフローチャートである。
【００８３】
図８を参照すれば、ルーティング領域内の各候補ノード５０３は、ＲＴＳメッセージを用いてチャネル利得を推定する（Ｓ８０１）。
【００８４】
前記のように、推定されたチャネル利得が閾値よりも大きいノードは、ＣＴＳメッセージをソースノード（または第１リレーノード）５０１に送信する。
【００８５】
ＣＴＳメッセージを送信したノードは、ルーティング領域内の２つ以上のノードからＣＴＳメッセージが送信されたのか否かを判断する（Ｓ８０３）。このとき、ルーティング領域内の代表ノードが２つ以上のノードからＣＴＳメッセージが送信されたのかを判断し、これをＣＴＳメッセージを送信した各ノードに知らせることができる。
【００８６】
もし、１つのノードからＣＴＳメッセージをソースノード（または第１リレーノード）５０１に送信した場合には、前記のように第２リレーノードが決定される（Ｓ８０５）。
【００８７】
もし、２つ以上のノードからＣＴＳメッセージをソースノード（または第１リレーノード）５０１に送信した場合には、ＣＴＳメッセージを送信した各ノードは、チャネル利得に対応する確率値によってＣＴＳメッセージを再送信する（Ｓ８０７）。
【００８８】
このとき、チャネル利得に対応する確率値は予め設定された値であって、チャネル利得が高いほど１に近い確率値で設定することができる。
【００８９】
本発明の実施形態は、チャネル利得が高いほど高い確率値でＣＴＳメッセージを再送信するため、ＣＴＳメッセージの衝突問題を解決することができる。
【００９０】
図９は、複数の送信ノードが存在する場合の一例を示した図である。
【００９１】
図９は、ルーティング領域９０９内のノード９０５，９０７が２つ以上の送信ノード９０１，９０３からＲＴＳメッセージを受信した場合を示している。
【００９２】
このとき、ルーティング領域９０９内のノード９０５，９０７は、それぞれのＲＴＳメッセージに対するチャネル利得を推定する。
【００９３】
このとき、推定されたチャネル利得が所定の設定値以上であれば、ＲＴＳメッセージを送信したソースノードまたは第１リレーノードの識別情報（ＩＤ）および推定されたチャネル利得値を含んでＣＴＳメッセージを送信する。
【００９４】
このとき、それぞれの送信ノード９０１，９０３は、識別情報によってＣＴＳメッセージを送信したノードを知ることができる。それぞれの送信ノード９０１，９０３は、いずれか１つのノードがチャネル利得が最も良い候補ノードを選択し、他の１つのノードがチャネル利得が二番目に良いノードを選択することで、リンク間の衝突を防ぐことができる。
【００９５】
また、複数の送信ノードが存在する場合に、閾値およびＣＴＳメッセージの衝突に対する処理過程は、１つの送信ノードが存在する場合と同じように処理される。
【００９６】
図１０は、本発明のさらに他の実施形態に係るパケット送信経路設定方法を示したフローチャートである。
【００９７】
図１０を参照すれば、パケット送信経路設定方法は、ソースノードまたはソースノードから受信されたパケットを送信する第１リレーノード１００１が予め設定された領域内のノード１００３にＲＴＳメッセージを送信するステップ１００５と、ＲＴＳメッセージを受信した各ノードがチャネル利得を推定するステップ１００７と、推定されたチャネル利得値に対応するバック−オフ時間によって推定されたチャネル利得値を含むＣＴＳメッセージを送信するステップ１００９，１０１１と、ＣＴＳメッセージを最初に送信したノードを第２リレーノードとして決定するステップ１０１３，１０１５とを含む。
【００９８】
ステップ１００５で、ソースノード（または第１リレーノード）１００１は、目的ノードのコーディネート情報を含むＲＴＳメッセージを隣接ルーティング領域内の候補ノード１００３に送信する。
【００９９】
ステップ１００７で、隣接ルーティング領域内の候補各ノード１００３は、ＲＴＳメッセージを用いてチャネル利得を推定する。
【０１００】
ＲＴＳメッセージおよびＣＴＳメッセージは、パケット送信時に用いる周波数とは異なる任意の周波数を用いて送信することができる。
【０１０１】
ステップ１００９で、隣接ルーティング領域内の候補各ノード１００３は、予め設定されたバック−オフ時間によってタイマー（図示せず）を作動させる。
【０１０２】
バック−オフ時間Ｕは、図１１に示すように、チャネル利得値に基づくユーティリティ関数である。ユーティリティ関数は、チャネル利得値に対して単調減少する特性を有するように任意の関数でモデリングして生成することができる。
【０１０３】
ステップ１００７で、隣接ルーティング領域内の候補各ノード１００３は、ＲＴＳメッセージを２つ以上のソースノードまたは第１リレーノードから受信した場合には、各ＲＴＳメッセージに対するチャネル利得を推定する。
【０１０４】
ステップ１０１１で、バック−オフ時間によって作動したタイマーが０となるノードは、推定されたチャネル利得値を含むＣＴＳメッセージをソースノード（または第１リレーノード）１００１に送信する。
【０１０５】
ステップ１０１３で、ソースノード（または第１リレーノード）９０１は、ＣＴＳメッセージを送信したノードにパケットを送信する。パケットを受信したノードは、ＡＣＫ信号をソースノード（または第１リレーノード）１００１に送信する。
【０１０６】
上述したように、本発明の好ましい実施形態を参照して説明したが、該当の技術分野において熟練した当業者にとっては、特許請求の範囲に記載された本発明の思想および領域から逸脱しない範囲内で、本発明を多様に修正および変更させることができることを理解することができるであろう。すなわち、本発明の技術的範囲は、特許請求の範囲に基づいて定められ、発明を実施するための最良の形態により制限されるものではない。
【図面の簡単な説明】
【０１０７】
【図１】アドホックネットワークの一例を示した図面である。
【図２】本発明の実施形態に係るパケット送信経路設定方法を示したフローチャートである。
【図３】本発明の実施形態に係るルーティング領域設定例を示した図である。
【図４】図３に示したルーティング領域の決定方法を説明するための図である。
【図５】本発明の他の実施形態に係るパケット送信経路設定方法を示したフローチャートである。
【図６】目的ノードにパケットを送信するリレーノードの選択方法を説明するための図である。
【図７】図５において、いずれか１つのノードもＣＴＳメッセージを送信しない場合のパケット送信経路設定方法を示したフローチャートである。
【図８】２つ以上のノードにＣＴＳメッセージを送信する場合のパケット送信経路設定方法を示したフローチャートである。
【図９】複数の送信ノードが存在する場合の一例を示した図である。
【図１０】本発明のさらに他の実施形態に係るパケット送信経路設定方法を示したフローチャートである。
【図１１】本発明の実施形態に係るバック−オフ時間に対するユーティリティ関数の一例を示した図である。
【符号の説明】
【０１０８】
３０１ ソースノード
３０３，３０５，３０７ ルーティング領域
３０９ 目的ノード
４０３ ルーティング領域
５０１ ソースノード（またはリレーノード）
５０３ 候補ノード
６０１ ルーティング領域
６０３ リレーノード
６０５ ルーティング領域
６０７ 代表ノード
６０９ 目的ノード
９０１，９０３ 送信ノード
９０５，９０７ ノード
９０９ ルーティング領域
１００１ ソースノード（またはリレーノード）
１００３ 候補ノード
【特許請求の範囲】
【請求項１】
無線通信ネットワークにおけるパケット送信経路の設定方法であって、
予め設定されたホップ数Ｎ（Ｎは２以上の正数）によって少なくとも１つのノードを含むＮ−１個のルーティング領域をソースノードと目的ノードとの間に設定するステップと、
チャネル利得に基づいて前記設定されたＮ−１個のルーティング領域内のいずれか１つのノードをリレーノードとして決定するステップと、
を含むことを特徴とするパケット送信経路設定方法。
【請求項２】
前記予め設定されたホップ数Ｎは、送信されるパケットに対して許容される遅延時間を基準として決定されることを特徴とする請求項１に記載のパケット送信経路設定方法。
【請求項３】
前記Ｎ−１個のルーティング領域それぞれの中心から境界までの距離ｒおよび送信されるパケットに対するホップ距離ｄの比のｒ／ｄは、０よりも大きく０．５よりも小さい値であることを特徴とする請求項１に記載のパケット送信経路設定方法。
【請求項４】
前記ソースノードおよびリレーノードは、前記予め設定されたホップ数Ｎ、ホップ距離、およびルーティング領域中心から境界までの距離ｒに基づいて送信電力を設定することを特徴とする請求項３に記載のパケット送信経路設定方法。
【請求項５】
前記ルーティング領域内のいずれか１つのノードをリレーノードとして決定するステップは、
ソースノードまたは前記ソースノードから送信されたパケットを受信したリレーノードが、それぞれ隣接したルーティング領域内の各ノードに目的ノードのコーディネート情報を含む制御信号を送信し、
前記制御信号を受信したノードがチャネル利得を推定し、
前記推定されたチャネル利得が所定の設定値よりも大きいノードを次のリレーノードとして決定することを含むことを特徴とする請求項１に記載のパケット送信経路設定方法。
【請求項６】
Ｎ−１個のルーティング領域のうちから目的ノードと隣接したルーティング領域内のリレーノードを決定するステップは、
前記目的ノードが前記目的ノードと隣接したルーティング領域内の各ノードにＲＴＳ機能の信号を送信し、
前記ＲＴＳ機能の信号を受信した各ノードがチャネル利得を推定し、
前記推定されたチャネル利得が所定の設定値よりも大きいノードをリレーノードとして決定することを含むことを特徴とする請求項１に記載のパケット送信経路設定方法。
【請求項７】
前記無線通信ネットワークは、マルチホップ基盤のアドホックネットワークであることを特徴とする請求項１に記載のパケット送信経路設定方法。
【請求項８】
無線通信ネットワークにおいてソースノードと目的ノードとの間でパケットをリレーするリレーノードを決定するためのパケット送信経路設定方法であって、
前記ソースノードまたは前記ソースノードから受信されたパケットを送信する第１リレーノードが予め設定された領域内のノードにＲＴＳメッセージを送信するステップと、
前記ＲＴＳメッセージを受信した各ノードがチャネル利得を推定するステップと、
前記推定されたチャネル利得が設定値よりも大きいノードが前記推定されたチャネル利得値を含むＣＴＳメッセージを送信するステップと、
前記ＣＴＳメッセージを送信したノードを第２リレーノードとして決定するステップと、
を含むことを特徴とするパケット送信経路設定方法。
【請求項９】
前記ＣＴＳメッセージを送信したノードを第２リレーノードとして決定するステップにおいて、
前記ＣＴＳメッセージを送信するノードが１つであることを特徴とする請求項８に記載のパケット送信経路設定方法。
【請求項１０】
前記ＣＴＳメッセージを送信するノードがない場合には、
前記設定値を変更し、前記推定されたチャネル利得を前記変更された設定値と比較することを特徴とする請求項8に記載のパケット送信経路設定方法。
【請求項１１】
前記ＣＴＳメッセージを送信するノードが２つ以上である場合には、
前記ＣＴＳメッセージを送信した各ノードは、チャネル利得に対応する確率値によってＣＴＳメッセージを再送信することを含むことを特徴とする請求項８に記載のパケット送信経路設定方法。
【請求項１２】
前記予め設定された領域内のノードが前記ＲＴＳメッセージを２つ以上のソースノードまたは第１リレーノードから受信した場合には、各ＲＴＳメッセージに対するチャネル利得を推定し、
前記推定されたチャネル利得が設定値よりも大きければ、前記ＲＴＳメッセージを送信したソースノードまたは第１リレーノードの識別情報を含んで前記ＣＴＳメッセージを送信することを含むことを特徴とする請求項８に記載のパケット送信経路設定方法。
【請求項１３】
マルチホップ基盤のアドホックネットワークにおいてソースノードと目的ノードとの間でパケットをリレーするリレーノードを決定するためのパケット送信経路設定方法であって、
前記ソースノードまたは前記ソースノードから受信されたパケットを送信する第１リレーノードが予め設定された領域内のノードにＲＴＳメッセージを送信するステップと、
前記ＲＴＳメッセージを受信した各ノードがチャネル利得を推定するステップと、
前記推定されたチャネル利得値に対応するバック−オフ時間によって前記推定されたチャネル利得値を含むＣＴＳメッセージを送信するステップと、
前記ＣＴＳメッセージを最初に送信したノードを第２リレーノードとして決定するステップと、
を含むことを特徴とするパケット送信経路設定方法。
【請求項１４】
前記予め設定された領域内のノードが前記ＲＴＳメッセージを２つ以上のソースノードまたは第１リレーノードから受信した場合には、各ＲＴＳメッセージに対するチャネル利得を推定し、
前記推定されたチャネル利得値に対応するバック−オフ時間によって前記ＲＴＳメッセージを送信したソースノードまたは第１リレーノードの識別情報を含んで前記ＣＴＳメッセージを送信することを含むことを特徴とする請求項１３に記載のパケット送信経路設定方法。
【請求項１５】
マルチホップ基盤のアドホックネットワーク装置であって、
送信パケットに許容される遅延時間に基づいてホップ数を決定するソースノードと、
前記ソースノードから目的ノードのコーディネート情報を受信してチャネル利得を推定し、前記推定されたチャネル利得が所定の設定値以上であれば応答メッセージを前記ソースノードに送信する第１リレーノードと、
前記目的ノードからメッセージを受信してチャネル利得を推定し、前記推定されたチャネル利得が所定の設定値よりも大きければ応答メッセージを前記目的ノードに送信する第２リレーノードと、
を備えることを特徴とするネックワーク装置。
【請求項１６】
前記第１リレーノードおよび第２リレーノードは、それぞれ前記ホップ数に基づいて予め設定される互いに異なるルーティング領域内に位置することを特徴とする請求項１５に記載のネットワーク装置。
【請求項１７】
前記第１リレーノードは、前記推定されたチャネル利得値に対応するバック−オフ時間によって前記応答メッセージを送信することを特徴とする請求項１５に記載のネックワーク装置。
【請求項１】
無線通信ネットワークにおけるパケット送信経路の設定方法であって、
予め設定されたホップ数Ｎ（Ｎは２以上の正数）によって少なくとも１つのノードを含むＮ−１個のルーティング領域をソースノードと目的ノードとの間に設定するステップと、
チャネル利得に基づいて前記設定されたＮ−１個のルーティング領域内のいずれか１つのノードをリレーノードとして決定するステップと、
を含むことを特徴とするパケット送信経路設定方法。
【請求項２】
前記予め設定されたホップ数Ｎは、送信されるパケットに対して許容される遅延時間を基準として決定されることを特徴とする請求項１に記載のパケット送信経路設定方法。
【請求項３】
前記Ｎ−１個のルーティング領域それぞれの中心から境界までの距離ｒおよび送信されるパケットに対するホップ距離ｄの比のｒ／ｄは、０よりも大きく０．５よりも小さい値であることを特徴とする請求項１に記載のパケット送信経路設定方法。
【請求項４】
前記ソースノードおよびリレーノードは、前記予め設定されたホップ数Ｎ、ホップ距離、およびルーティング領域中心から境界までの距離ｒに基づいて送信電力を設定することを特徴とする請求項３に記載のパケット送信経路設定方法。
【請求項５】
前記ルーティング領域内のいずれか１つのノードをリレーノードとして決定するステップは、
ソースノードまたは前記ソースノードから送信されたパケットを受信したリレーノードが、それぞれ隣接したルーティング領域内の各ノードに目的ノードのコーディネート情報を含む制御信号を送信し、
前記制御信号を受信したノードがチャネル利得を推定し、
前記推定されたチャネル利得が所定の設定値よりも大きいノードを次のリレーノードとして決定することを含むことを特徴とする請求項１に記載のパケット送信経路設定方法。
【請求項６】
Ｎ−１個のルーティング領域のうちから目的ノードと隣接したルーティング領域内のリレーノードを決定するステップは、
前記目的ノードが前記目的ノードと隣接したルーティング領域内の各ノードにＲＴＳ機能の信号を送信し、
前記ＲＴＳ機能の信号を受信した各ノードがチャネル利得を推定し、
前記推定されたチャネル利得が所定の設定値よりも大きいノードをリレーノードとして決定することを含むことを特徴とする請求項１に記載のパケット送信経路設定方法。
【請求項７】
前記無線通信ネットワークは、マルチホップ基盤のアドホックネットワークであることを特徴とする請求項１に記載のパケット送信経路設定方法。
【請求項８】
無線通信ネットワークにおいてソースノードと目的ノードとの間でパケットをリレーするリレーノードを決定するためのパケット送信経路設定方法であって、
前記ソースノードまたは前記ソースノードから受信されたパケットを送信する第１リレーノードが予め設定された領域内のノードにＲＴＳメッセージを送信するステップと、
前記ＲＴＳメッセージを受信した各ノードがチャネル利得を推定するステップと、
前記推定されたチャネル利得が設定値よりも大きいノードが前記推定されたチャネル利得値を含むＣＴＳメッセージを送信するステップと、
前記ＣＴＳメッセージを送信したノードを第２リレーノードとして決定するステップと、
を含むことを特徴とするパケット送信経路設定方法。
【請求項９】
前記ＣＴＳメッセージを送信したノードを第２リレーノードとして決定するステップにおいて、
前記ＣＴＳメッセージを送信するノードが１つであることを特徴とする請求項８に記載のパケット送信経路設定方法。
【請求項１０】
前記ＣＴＳメッセージを送信するノードがない場合には、
前記設定値を変更し、前記推定されたチャネル利得を前記変更された設定値と比較することを特徴とする請求項8に記載のパケット送信経路設定方法。
【請求項１１】
前記ＣＴＳメッセージを送信するノードが２つ以上である場合には、
前記ＣＴＳメッセージを送信した各ノードは、チャネル利得に対応する確率値によってＣＴＳメッセージを再送信することを含むことを特徴とする請求項８に記載のパケット送信経路設定方法。
【請求項１２】
前記予め設定された領域内のノードが前記ＲＴＳメッセージを２つ以上のソースノードまたは第１リレーノードから受信した場合には、各ＲＴＳメッセージに対するチャネル利得を推定し、
前記推定されたチャネル利得が設定値よりも大きければ、前記ＲＴＳメッセージを送信したソースノードまたは第１リレーノードの識別情報を含んで前記ＣＴＳメッセージを送信することを含むことを特徴とする請求項８に記載のパケット送信経路設定方法。
【請求項１３】
マルチホップ基盤のアドホックネットワークにおいてソースノードと目的ノードとの間でパケットをリレーするリレーノードを決定するためのパケット送信経路設定方法であって、
前記ソースノードまたは前記ソースノードから受信されたパケットを送信する第１リレーノードが予め設定された領域内のノードにＲＴＳメッセージを送信するステップと、
前記ＲＴＳメッセージを受信した各ノードがチャネル利得を推定するステップと、
前記推定されたチャネル利得値に対応するバック−オフ時間によって前記推定されたチャネル利得値を含むＣＴＳメッセージを送信するステップと、
前記ＣＴＳメッセージを最初に送信したノードを第２リレーノードとして決定するステップと、
を含むことを特徴とするパケット送信経路設定方法。
【請求項１４】
前記予め設定された領域内のノードが前記ＲＴＳメッセージを２つ以上のソースノードまたは第１リレーノードから受信した場合には、各ＲＴＳメッセージに対するチャネル利得を推定し、
前記推定されたチャネル利得値に対応するバック−オフ時間によって前記ＲＴＳメッセージを送信したソースノードまたは第１リレーノードの識別情報を含んで前記ＣＴＳメッセージを送信することを含むことを特徴とする請求項１３に記載のパケット送信経路設定方法。
【請求項１５】
マルチホップ基盤のアドホックネットワーク装置であって、
送信パケットに許容される遅延時間に基づいてホップ数を決定するソースノードと、
前記ソースノードから目的ノードのコーディネート情報を受信してチャネル利得を推定し、前記推定されたチャネル利得が所定の設定値以上であれば応答メッセージを前記ソースノードに送信する第１リレーノードと、
前記目的ノードからメッセージを受信してチャネル利得を推定し、前記推定されたチャネル利得が所定の設定値よりも大きければ応答メッセージを前記目的ノードに送信する第２リレーノードと、
を備えることを特徴とするネックワーク装置。
【請求項１６】
前記第１リレーノードおよび第２リレーノードは、それぞれ前記ホップ数に基づいて予め設定される互いに異なるルーティング領域内に位置することを特徴とする請求項１５に記載のネットワーク装置。
【請求項１７】
前記第１リレーノードは、前記推定されたチャネル利得値に対応するバック−オフ時間によって前記応答メッセージを送信することを特徴とする請求項１５に記載のネックワーク装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２００９−１００４４３（Ｐ２００９−１００４４３Ａ）
【公開日】平成２１年５月７日（２００９．５．７）
【国際特許分類】
【出願番号】特願２００８−１７７３２８（Ｐ２００８−１７７３２８）
【出願日】平成２０年７月７日（２００８．７．７）
【出願人】（３９００１９８３９）三星電子株式会社 (8,520)
【氏名又は名称原語表記】ＳＡＭＳＵＮＧ ＥＬＥＣＴＲＯＮＩＣＳ ＣＯ．，ＬＴＤ．
【住所又は居所原語表記】４１６，Ｍａｅｔａｎ−ｄｏｎｇ，Ｙｅｏｎｇｔｏｎｇ−ｇｕ，Ｓｕｗｏｎ−ｓｉ，Ｇｙｅｏｎｇｇｉ−ｄｏ ４４２−７４２（ＫＲ）
【出願人】（５９２１２７１４９）韓国科学技術院 (129)
【氏名又は名称原語表記】ＫＯＲＥＡ ＡＤＶＡＮＣＥＤ ＩＮＳＴＩＴＵＴＥ ＯＦ ＳＣＩＥＮＣＥ ＡＮＤ ＴＥＣＨＮＯＬＯＧＹ
【住所又は居所原語表記】３７３−１，Ｇｕｓｕｎｇ−ｄｏｎｇ，Ｙｕｓｅｏｎｇ−ｋｕ，Ｄａｅｊｅｏｎ ３０５−７０１ ＫＲ
【Ｆターム（参考）】
【公開日】平成２１年５月７日（２００９．５．７）
【国際特許分類】
【出願日】平成２０年７月７日（２００８．７．７）
【出願人】（３９００１９８３９）三星電子株式会社 (8,520)
【氏名又は名称原語表記】ＳＡＭＳＵＮＧ ＥＬＥＣＴＲＯＮＩＣＳ ＣＯ．，ＬＴＤ．
【住所又は居所原語表記】４１６，Ｍａｅｔａｎ−ｄｏｎｇ，Ｙｅｏｎｇｔｏｎｇ−ｇｕ，Ｓｕｗｏｎ−ｓｉ，Ｇｙｅｏｎｇｇｉ−ｄｏ ４４２−７４２（ＫＲ）
【出願人】（５９２１２７１４９）韓国科学技術院 (129)
【氏名又は名称原語表記】ＫＯＲＥＡ ＡＤＶＡＮＣＥＤ ＩＮＳＴＩＴＵＴＥ ＯＦ ＳＣＩＥＮＣＥ ＡＮＤ ＴＥＣＨＮＯＬＯＧＹ
【住所又は居所原語表記】３７３−１，Ｇｕｓｕｎｇ−ｄｏｎｇ，Ｙｕｓｅｏｎｇ−ｋｕ，Ｄａｅｊｅｏｎ ３０５−７０１ ＫＲ
【Ｆターム（参考）】
[ Back to top ]