(57)【要約】【課題】方法は、ワイヤレスネットワークのチャネルを介してノードにおいて受信したパケットをリブロードキャストする遅延を確定する。【解決手段】ノードは、パケット受信後、ネットワークのチャネルの品質を測定する。受信ノードのブロードキャスト度が求められ、パケットをリブロードキャストする遅延が品質及びブロードキャスト度に応じて設定される。
2008510350.tif 000002
【特許請求の範囲】
【請求項１】
ワイヤレスネットワークのチャネルを介してノードにおいて受信したパケットをリブロードキャストする遅延を確定する方法であって、
受信ノードにおいてパケットを受信すること、
前記受信ノードにおいてネットワークのチャネルの品質を測定すること、
前記受信ノードのブロードキャスト度を求めること、
並びに
前記品質及び前記ブロードキャスト度に応じて前記パケットをリブロードキャストする遅延を設定すること
を含む方法。
【請求項２】
前記受信ノードのツリー度を求めること、
及び
前記ツリー度がゼロよりも大きい場合のみ前記パケットをリブロードキャストすることをさらに含む
請求項１記載の方法。
【請求項３】
前記受信パケットの信号強度から前記品質を推定することをさらに含む
請求項１記載の方法。
【請求項４】
前記受信パケットの信号対雑音比から前記品質を推定することをさらに含む
請求項１記載の方法。
【請求項５】
前記受信パケットの信号強度及び信号対雑音比から前記品質を推定することをさらに含む
請求項１記載の方法。
【請求項６】
前記遅延は、前記品質に反比例し、前記ブロードキャスト度に正比例する
請求項１記載の方法。
【請求項７】
前記ブロードキャスト度は、前記パケットを受信していない前記受信ノードへの隣接ノード数である
請求項１記載の方法。
【請求項８】
前記品質及び前記ブロードキャスト度にはそれぞれ重みが付される
請求項１記載の方法。
【請求項９】
前記ツリー度は、前記パケットを受信していない前記ノードのツリー近傍の総数である
請求項２記載の方法。
【請求項１０】
前記遅延Ｔを
Ｔ＝ｆ（α（ＬＱＩ），β（ブロードキャスト度））
としての閉形で表現することをさらに含み、式中、α及びβは重みであり、これは、
｛∂ｆ／（α．ＬＱＩ）｝＞０，｛∂ｆ／（β．ブロードキャスト度）｝＜０
を満たす
請求項１記載の方法。
【請求項１１】
前記関数ｆは、
ｋ．αＬＱＩ／β度
であり、式中、ｋは前記遅延Ｔをスケーリングするパラメータである
請求項１０記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはワイヤレスネットワークに関し、特にブロードキャスト中の衝突回避に関する。
【背景技術】
【０００２】
ワイヤレスネットワーク全体のノードにパケットをブロードキャストするには、ノードがネットワーク全体の範囲よりも小さい通信範囲を有する場合、いくつかのノードがパケットをリブロードキャストすることが必要なことがある。これはマルチホッピングと呼ばれる。
【０００３】
１つの従来技術による方法では、ネットワーク内のあらゆるノードが厳密に１回、受信パケットをリブロードキャストする。しかし、この方法は「ブロードキャストストーム問題」を生じさせる。
【０００４】
或る方法は、各ノードに、パケットをリブロードキャストするに先立って異なる遅延を使用させることによって衝突を回避する。別の方法は、複製パケットの数に基づいた確率方式を用いてパケットをそもそもリブロードキャストする必要があるか否かを判断する。Ni等著「The Broadcast Storm Problem in a Mobile Ad Hoc Network」MobiCom, August 1999。
【０００５】
別の方法は、ランダム分布から選択される遅延を用いる。Williams等著「Comparison of Broadcasting Techniques for Mobile Ad Hoc Networks」MobiHoc, 2002。
【０００６】
別の方法は、ランダム遅延及び送信器と受信器の間の相対距離を用いて、パケットをリブロードキャストすべきか否かを判断する。Tseng等著「Adaptive Approaches to Relieving Broadcast Storms in a Wireless Multi-hop Mobile Ad Hoc Network」IEEE Trans. on Computers, 52(5): pp.545-557, 2003。
【０００７】
グローバルネットワークトポロジ情報が分かる場合、最小数のリブロードキャストノードを選択する問題はＮＰ完全である。しかし、ノード位置情報が利用可能な場合、この問題は一定の比で近似することができる。Lim等著「Flooding in Wireless Ad Hoc Networks」Computer Communication Journal, 24(3-4), pp.353-363, 2001。
【０００８】
リブロードキャストポリシーは、１ホップ隣接又は２ホップ隣接のリスト等、ローカルネットワークトポロジ情報に基づくこともできる。Dai等著「Performance Analysis of Broadcast Protocols in Ad Hoc Networks Based on Self-Pruning」IEEE Trans. on Parallel and Distributed Systems, September 2004。別法として、ノードは近傍のサブセットをパケットのリブロードキャストに割り当てることができる。Lou等著「Localized Broadcasting in Mobile Ad Hoc Networks Using Neighbor Designation」Handbook of Mobile Computing, CRC Press, July 2003参照。
【０００９】
ブロードキャストのエネルギー効率については広く研究されてきた。或る方法は集中手順を用いる。Cagalj等著「Minimum-Energy Broadcast in All-Wireless Networks: NP-Completeness and Distribution Issues」MobiCom, 2002。しかし、これはＮＰ完全問題である。ローカル手順は最適解を近似することができない。Cartigny等著「Localized Minimum-Energy Broadcasting in Ad-Hoc Networks」InfoCom 2003。
【００１０】
ブロードキャストストームは、Valdevitに１９９７年６月３日に発行された米国特許第５，６３６，３４５号、Fowlerに１９９８年８月１１日に発行された第５，７９３，９７８号、Bass等に２００１年２月６日に発行された第６，１８５，１８５号、及びJohに２００１年７月３日に発行された第６，２５６，３１２号においても扱われている。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
したがって、従来技術を改良するリブロードキャストポリシーが必要である。
【課題を解決するための手段】
【００１２】
方法は、ワイヤレスネットワークのチャネルを介してノードにおいて受信したパケットのリブロードキャストの遅延を確定する。
【００１３】
ノードは、パケット受信後、ネットワークのチャネルの品質を測定する。
【００１４】
受信ノードのブロードキャスト度が求められ、パケットをリブロードキャストする遅延が品質及びブロードキャスト度に応じて設定される。
【００１５】
ノードはまたツリー度も求め、ツリー度が０よりも大きい場合のみリブロードキャストすることもできる。
【発明を実施するための最良の形態】
【００１６】
図１に示すように、本発明は、ワイヤレスネットワークのノードにおいてパケットをリブロードキャストする遅延１３１を確定する方法を提供する。方法は、チャネルの品質（ＬＱＩ）１１１を測定し１１０、ブロードキャスト度１２１を求めて１２０、特定のノードが受信パケットをリブロードキャストする前に遅延Ｔ１３１を確定する１３０。方法はまた、ツリー度１４１も求める１４０。ツリー度１４１がゼロの場合、ブロードキャストは行われない。
【００１７】
チャネル品質
ＩＥＥＥ８０２．１５．４規格に従って設計されたネットワークでは、チャネル又はリンク品質インデックス（ＬＱＩ）を信号強度、信号対雑音比（ＳＮＲ）、又はパケットが干渉を受けて低信号強度又は高信号強度により破損しているか否かを判断することが必要な場合には両方から推定することができる。
【００１８】
チャネルの品質が比較的良い場合、遅延は比較的長くなり、チャネルの品質が比較的悪い場合、遅延は比較的短くなる。ここでの仮定は、品質が比較的良い場合、送信ノードは受信ノードに比較的近く、送信ノード受信ノードのブロードキャスト範囲が実質的に重複するというものである。この場合、リブロードキャストは、パケットを受信していないノードに到達する可能性は低い。しかし、品質が低い場合、送信ノードと受信ノードの範囲はわずかに重複し、リブロードキャストが、パケットを受信していないより多くのノードに到達する可能性は高い。
【００１９】
ブロードキャスト度
ブロードキャスト度は、ネットワークのローカルトポロジ、すなわち１ホップ隣接ノードのリストから導出される。ブロードキャスト度は、パケットを受信しておらず、リブロードキャストを行うべき隣接ノード数である。
【００２０】
ブロードキャスト度は、各ノードが保持する隣接ノードのリストから求められる。ノードリストは、ネットワークトラフィックでの「傍受」により構築することができる。本発明によるアドホックネットワークでは、ノードのアドレスは、ネットワークが構築される際に階層的に分配される。すなわち、各親が或る範囲のアドレスを子ノードに分配し、子ノードがその範囲の部分を子に再分配し、以下同様である。したがって、傍受ノードは、ブロードキャスト範囲内にあるノードの階層を「学習」し、階層、すなわち親ノード及び子ノードを示す隣接リストを構築することができる。
【００２１】
ここで、特定のノードが、この特定のノードのブロードキャスト範囲内の宛先ノードの親であるソースノードからパケットを受信する場合、十中八九、子ノードもパケットを受信することになるため、パケットのリブロードキャストは子ノードに対して有用ではないであろう。
【００２２】
したがって、ブロードキャスト度はパケットを受信していないノードの総数である。ブロードキャスト度が比較的大きい場合、遅延は比較的短く、ブロードキャスト度が小さい場合、遅延は長くあるべきである。本発明は、早期のリブロードキャストがパケットを受信していない多数のノードに到達する可能性が高い場合に早期のリブロードキャストを好む。
【００２３】
ツリー度
ツリー度は、パケットを受信していない可能性が高いノードのツリー近傍の総数である。ツリー度は最初は、親ノード及びリブロードキャストを行うべきパケットを受信しているノードのすべての兄弟ノードを含む。「傍受」を用いて、ノードは、ツリー近傍のいずれがブロードキャスト範囲内にあるかを学習することができる。このようなノードが検出される都度、ツリー度は１だけ下げられる。ツリー度がゼロに達すると、そのノードは受信パケットをリブロードキャストする。
【００２４】
遅延Ｔ
遅延Ｔは、
ａ．Ｔ＝ｆ（α（ＬＱＩ），β（ブロードキャスト度））
としての閉形関数で表現される。式中、α及びβは重みであり、関数は、
｛∂ｆ／（α．ＬＱＩ）｝＞０，｛∂ｆ／（β．ブロードキャスト度）｝＜０
を満たす。
【００２５】
上記制約を満たす１つの関数はＴ＝ｋ．αＬＱＩ／β（ブロードキャスト度）であり、式中、ｋは適切な時間分解能へのスケールＴに対するパラメータである。ＬＱＩ及びブロードキャスト度は、パケットリブロードキャストによる衝突の可能性を低減することへのそれぞれの相対的な効果を反映するように重みが付される。ツリー度＝０を有するノードは決してリブロードキャストされないことにも留意されたい。また、待ち時間Ｔ中、ツリー度がゼロになる場合、ノードはリブロードキャストされない。
【００２６】
図２は、本発明による方法を実施する手順の疑似コードを示す。パケットｐを最初に受信する２０１場合、パケットをバッファに記憶し２０２、送信者ＩＤを記録し２０３、チャネル品質（ＬＱＩ）を測定し２０４、ブロードキャスト度を求め２０５、ツリー度がゼロではない場合に遅延Ｔを設定する２０６。その他の場合で、前にパケットを受信していた２０７場合、遅延を更新し２０８、その他の場合、パケットを破棄する２０９。
【００２７】
本発明について好ましい実施形態の例として説明したが、他の様々な適応及び変更を本発明の精神及び範囲内で行うことが可能であることを理解されたい。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲内のこのような変形及び変更をすべて包含することである。
【図面の簡単な説明】
【００２８】
【図１】ワイヤレスネットワークにおいてパケットのリブロードキャストを遅らせる方法のブロック図である。
【図２】本発明による手順の図である。
【図１】
2008510350.tif 000003
【図２】
2008510350.tif 000004
【国際調査報告】
2008510350.tif 000005
2008510350.tif 000006
2008510350.tif 000007