(57)【特許請求の範囲】
【請求項１】
ネットワーク符号化を用いて通信ネットワークにおけるスループットを増加させる方法であって、
符号化実行ノードとなりうるノードのｎホップ半径の近傍において、非連結な２つのノードまたはノード群が、２以上の異なるルートを通してパケットを交換しているか否かを検出するステップと、
前記非連結なノードまたはノード群が交換している逆方向に向かうパケットを前記符号化実行ノードとなりうるノードが線形結合することのできる代替的な双方向経路または複数の単方向経路が存在するか否かを決定するステップと、
ネットワーク符号化が適用できる前記代替的な双方向経路または前記複数の単方向経路が、あるメトリックに基づく利得を提供するか否かを決定するステップと、
前記メトリックがネットワーク符号化による利得を示す場合には、前記符号化実行ノードとなりうるノードによるネットワーク符号化が利用できるものとなるように、前記非連結な２つのノードまたはノード群がパケットを交換するルートを変更するステップと
を含み、ここで、前記メトリックは、基礎となるルーティングプロトコルによって使用されるルーティングメトリックであり、該ルーティングメトリックは、ネットワーク符号化により得られる送信コストについての利得と、ノード間のリンク品質とに基づくものであり、更に、
前記符号化実行ノードとなりうるノードが、そのｎホップの近傍領域のトポロジーとアクティブな経路とについての情報を受信するステップであって、前記ｎが２以上の自然数である、ステップと、
前記符号化実行ノードとなりうるノードがそのｎホップの近傍領域のトポロジーのリンク状態マップを生成し、かつ、検出された周辺の状態に基づいてネットワーク符号化を行うノードの候補として自己を取捨選択することを可能とするために、前記ネットワーク内の各ノードが、その（ｎ−１）ホップの近傍領域内の近隣ノードに関する情報と、その（ｎ−１）ホップの近傍領域内の近隣ノードへの各リンクの品質についての指標とを同報するステップと、
ネットワーク符号化を利用した新たなルートのリンクコストの指標を前記符号化実行ノードとなりうるノードが通知するステップであって、前記リンクコストがネットワーク符号化により得られるスループット利得を表すものである、ステップと、
前記非連結なノード群がパケットを交換するためにこれまでに使用されたルートと比べて、前記新たなルートがリンクコストの点で好ましいか否かを決定するステップと、
前記新たなルートが好ましい場合には、前記新たなルートにより前記パケットを交換するために、ルーティングテーブルのエントリを更新するステップと
を含む方法。
【請求項２】
代替的な双方向経路を決定する前記ステップは、前記非連結な２つのノードまたはノード群の間の経路を一つ以上発見するために、ソースルーティングメカニズムを実行するステップを含むものであり、
前記経路内のノードがネットワーク符号化を実行するために、前記ソースルーティングメカニズムによって検出された一つ以上の経路を選択するステップを含む請求項１に記載の方法。
【請求項３】
同じ経路に沿って逆方向に向かうデータレートのバランスを取るステップを更に含む請求項２に記載の方法。
【請求項４】
前記ノードまたは前記ノード群によって交換されるデータファイルをいくつかの断片に分割して、それを複数の経路により送信するステップを更に含む請求項２または３に記載の方法。
【請求項５】
ネットワーク符号化を用いて通信ネットワークにおけるスループットを増加させるための装置であって、
非連結な２つのノードまたはノード群が、符号化実行ノードとなりうるノードのｎホップ半径の近傍において、２つ以上の異なるルートを通してパケットを交換しているか否かを検出する手段と、
前記非連結なノードまたはノード群が交換している逆方向に向かうパケットを前記符号化実行ノードとなりうるノードが線形結合することのできる代替的な双方向経路または複数の単方向経路が存在するか否かを決定する手段と、
ネットワーク符号化が適用できる前記代替的な双方向経路または複数の単方向経路が、あるメトリックに基づく利得を提供するか否かを決定する手段と、
前記メトリックがネットワーク符号化による利得を示す場合には、前記符号化実行ノードとなりうるノードによるネットワーク符号化が利用できるものとなるように、前記非連結な２つのノードまたはノード群がパケットを交換するルートを変更する手段と
を備え、ここで、前記メトリックは、基礎となるルーティングプロトコルによって使用されるルーティングメトリックであり、該ルーティングメトリックは、ネットワーク符号化により得られる送信コストについての利得と、ノード間のリンク品質とに基づくものであり、更に、
前記符号化実行ノードとなりうるノードが、そのｎホップの近傍領域のトポロジーとアクティブな経路とについての情報を受信するための手段であって、前記ｎが２以上の自然数である、手段と、
前記符号化実行ノードとなりうるノードがそのｎホップの近傍領域のトポロジーのリンク状態マップを生成し、かつ、検出された周辺の状態に基づいてネットワーク符号化を行うノードの候補として自己を取捨選択することを可能とするために、前記ネットワーク内の各ノードが、その（ｎ−１）ホップの近傍領域内の近隣ノードに関する情報と、その（ｎ−１）ホップの近傍領域内の近隣ノードへの各リンクの品質についての指標とを同報するための手段と、
ネットワーク符号化を利用した新たなルートのリンクコストの指標を前記符号化実行ノードとなりうるノードが通知するための手段であって、前記リンクコストがネットワーク符号化により得られるスループット利得を表すものである、手段と、
前記非連結なノード群がパケットを交換するためにこれまでに使用されたルートと比べて、前記新たなルートがリンクコストの点で好ましいか否かを決定し、前記新たなルートが好ましい場合には、前記新たなルートにより前記パケットを交換するために、ルーティングテーブルのエントリを更新する手段と
を備えた装置。
【請求項６】
符号化実行ノードとなりうるノードが、そのｎホップの近傍領域内のトポロジーとアクティブな経路とについての情報を受信するための手段であって、前記ｎは２以上の自然数である、手段を更に備える請求項５に記載の装置。
【請求項７】
請求項１から４のいずれか一項に記載の方法をコンピュータに実行させるコンピュータプログラムコードを有するコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク符号化（network coding）によって通信ネットワークにおけるスループットを増加させるための方法および装置に関する。
【背景技術】
【０００２】
帯域幅リソースをより有効に利用することは、今日の通信ネットワークにおける主要な課題である。近年、通信ネットワークの研究において「ネットワーク符号化（network coding）」と呼ばれる技術が多くの注目を集めている。この技術によれば、パケットの線形結合（linear combination）に基づいてネットワーク容量を大きく改善することができるからである。そのうえ、実装が自由かつ容易な暗号化（cipher）であるとして、その有用性が非特許文献１に記載されている。
【０００３】
ネットワーク符号化に関する研究のほとんどは、これまで理論的な解析と有線ネットワーク上でファイルを共有するためのマルチキャストシナリオにおけるネットワーク符号化の適用に焦点を置いてきた。無線ネットワークにおけるネットワーク符号化の適用に関する研究は、その特有の同報性およびマルチキャスト性により、ＷＬＡＮ環境において小規模なマルチキャストデータ配信を行うセンサネットワークに主に集中している。ごく少数の研究のみがネットワーク符号化をマルチホップ無線ネットワーク上のルーティングに実際に利用することに焦点を置いているに過ぎない。以下、提案されているメカニズムの中でもＣＯＰＥ（非特許文献２参照）とＭＯＲＥ（非特許文献３参照）の２つについて簡潔に説明する。
【０００４】
ＣＯＰＥと呼ばれるメカニズムは、マルチホップ８０２．１１ネットワークにおいて、非常にローカルな方法で、つまり宛先ノードのルートまたはアドレスを考慮することなく、ユニキャストフローのパケットをスマートかつ日和見的（opportunistic）に結合する。ＣＯＰＥにおけるパケット符号化のアルゴリズムは完全に日和見的であり、良い経路を特定するためにあらゆるペアのノードの間の配信確率を考慮する。効率的かつ日和見的にパケットを結合した結果として、ＣＯＰＥの論文に記載されているように、２０個のノードが存在するアドホックネットワークテストベッドにおいて、スループットは３倍または４倍にまで増加する。しかしながら、ＣＯＰＥアルゴリズムはルーティングアルゴリズムと見なすことはできない。なぜなら、これはあらゆるノードのルーティングテーブルの経路エントリを変更せず、基礎となるルーティングアルゴリズム（例えばＡＯＤＶまたはＯＬＳＲ）と、ＥＴＸ（Expected Transmission Count）（例えば非特許文献４参照）などのパケット配信確率推定（delivery probability estimator）とにより定まる既存のユニキャスト経路を利用するだけで、できる限りパケットの最良の結合を作り出そうとするものであるからである。
【０００５】
ＭＯＲＥと呼ばれるメカニズムは、日和見的なルーティングに対するあるネットワーク符号化のアプローチを定めるものである。ルータは、同じ宛先に向かうパケットを線形結合し、これらを符号化したものを転送する。宛先ノードはオリジナルのパケットを復号化し、再生する。ＭＯＲＥにおいては、発信元（ソース）はＫ個のパケットのバッチ（batch）を送信する。ここで、Ｋはバッチごとに異なるものである。各ＭＯＲＥパケットは、ネイティブパケットと、バッチシーケンス番号と、送信機と宛先との距離と、ＡＣＫからデータパケットを特定するタイプフィールドとに関する情報（contents）を記述するコードベクトル（code vector）を含む。中間のノードは全ての送信を受信（listen）する。ノードがパケットを受信（hear）すると、ノードはそのパケットがイノベーティブかどうか、すなわち、このバッチから既に受信したものとは線形独立かどうかをチェックする。パケットがイノベーティブではない場合には、ノードはそのパケットを即座に破棄することができる。次に、ノードは、受信したパケットの以前のホップよりも宛先に近いかどうかをチェックする。近い場合には、この新しいパケットの到来を契機に、そのノードは最近受信したパケットと同じバッチのパケットの線形結合を同報する。最後に、宛先ノードは、受信した各パケットがイノベーティブかどうかをチェックし、イノベーティブではないパケットを破棄する。宛先ノードがバッチを復号化するために十分にイノベーティブなパケットを受信すると、宛先ノードは最短経路で発信元（ソース）へ確認応答（Acknowledgement）を送信する。ＭＯＲＥの主な利点は、ノード間の調整が必要ないことである。しかしながら、経路に沿ったノードは、オートレート（autorate）な選択を使用することはできないが、ＭＡＣレイヤの観点から明らかに不十分な単一のビットレート値のみを使用することはできる。さらに、宛先ノードが最短経路に沿って送信した確認応答パケットを受信していない転送ノード（forwarders）によって、かなりの量の不要なトラフィックが生成される可能性があり、確認応答の送信前に更なるパケット衝突が起こる可能性がある。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】L. Lima, M. Medard, J.Barros, “Random Linear Coding: A Free Cypher?”, IEEE International Symposium in Information Theory 2007, 24th - 29th June 2007, Nice, France
【非特許文献２】S.Katti, H.Rahul, W.Hu, D.Katabi, M.Medardand J.Crowcroft, “XoRs in the air: Practical Network Coding”, SIGCOMM’06, September 11-15, 2006, Pisa, Italy
【非特許文献３】S.Chachulski, M.Jennings, S.Katti and D.Katabi, “Trading Structure for Randomness in Wireless Opportunistic Routing”, SIGCOMM’07, August 27-31, 2007, Kyoto, Japan
【非特許文献４】D. de Couto, D. Aguayo, J.Bicket and R. Morris, “A HighThroughput Path Metric for MultiHopWireless Routing”, MOBICOM’03, September 14-19, 2003, San Diego, California, USA
【発明の概要】
【０００７】
一実施形態によれば、ネットワーク符号化を用いて通信ネットワークにおけるスループットを増加させる方法であって、
符号化実行ノードとなりうるあるノードについてのｎ回のホップの半径を有する近傍領域において、非連結な２つのノードまたはノード群が、２以上の異なるルートを通してパケットを交換しているか否かを検出するステップと、
前記非連結なノードまたはノード群が交換している逆方向に向かうパケットを前記符号化実行ノードとなりうるノードが線形結合することのできる代替的な双方向経路または複数の単方向経路が存在するか否かを決定するステップと、
ネットワーク符号化が適用可能である前記代替的な双方向経路または前記複数の単方向経路が、あるメトリックに基づく利得を提供するか否かを決定するステップと、
前記メトリックがネットワーク符号化による利得を示す場合には、前記符号化実行ノードとなりうるノードによるネットワーク符号化が利用できるものとなるように、前記非連結な２つのノードまたはノード群がパケットを交換するルートを変更するステップと
を含む方法が提供される。
【０００８】
このアプローチにより、異なる経路を単一の双方向無線通信路に統合することができ、その結果、共有媒体のより有効な利用を実現するネットワーク符号化を利用することによって総スループットを増加させることができる。
【０００９】
一実施形態によれば、前記メトリックは、基礎となるルーティングプロトコルによって使用されるルーティングメトリックであり、該ルーティングメトリックは、ネットワーク符号化により得られる送信コストについての利得に基づくものとすることができる。
【００１０】
このようにして、かかるメカニズムは、ルーティングメトリックにおいて追加のパラメータとしてネットワーク符号化の利得を用いることにより、既存のルーティングプロトコルに容易に統合することができる。ルーティングメトリックは、一態様によればネットワーク符号化の利得に加えて更にノード間のリンク品質に基づくことができる。このとき、結果として得られるメトリックを、ルートを決定するためのルーティングアルゴリズムおいて使用することができる。
【００１１】
前記方法は、その一態様として、符号化実行ノードとなりうるノードが、そのｎ回のホップの半径を有する近傍領域内のトポロジーとアクティブな経路とについての情報を受信するステップであって、前記ｎは２以上の自然数である、ステップを更に含むことができる。
【００１２】
これにより、符号化実行ノードとなりうるノードは、その周辺のトポロジーとその中のアクティブなフローに基づいて、ネットワーク符号化を適用できる新たなルート内のノードとして自己をオファーできるかどうかを決定することができる。
【００１３】
前記方法は、その一態様として、符号化実行ノードとなりうるノードがそのｎホップの近傍領域のトポロジーのリンク状態マップを生成し、かつ、検出された周辺の状態に基づいてネットワーク符号化を行うノードの候補として自己を取捨選択することを可能とするために、前記ネットワーク内の各ノードが、その（ｎ−１）ホップの近傍領域内の近隣ノードに関する情報と、その（ｎ−１）ホップの範囲内の近隣ノードへの各リンクの品質についての指標とを同報するステップを更に含むことができる。
【００１４】
このようにして、ネットワーク内の各ノードは、ネットワーク符号化が適用できる新たなルートを提供することが可能かどうかを符号化となりうるノードが決定するために必要な情報を配信することができる。
【００１５】
本方法は、その一態様として、
ネットワーク符号化を利用した新たなルートのリンクコストの指標を符号化実行ノードとなりうるノードが通知するステップであって、前記リンクコストは、ネットワーク符号化により得られるスループット利得を表すものである、ステップと、
前記非連結なノード群がパケットを交換するためにこれまでに使用されたルートと比べて、前記新たなルートがリンクコストの点で好ましいか否かを決定するステップと、
前記新たなルートが好ましい場合には、前記新たなルートにより前記パケットを交換するために、ルーティングテーブルのエントリを更新するステップと
を更に含むことができる。
【００１６】
このようにして、符号化実行ノードとなりうるあるノードのｎホップの近傍領域内の局所的なエリアにおいて新たなルートを選ぶべきかどうかを決定することができ、選ぶべき場合にはルートを更新することができる。
【００１７】
一態様によれば、代替的な双方向経路を決定する前記ステップは、前記非連結な２つのノードまたはノード群の間の経路を一つ以上発見するために、ソースルーティングメカニズムを実行するステップを含むものであり、
前記方法は、前記経路内のノードがネットワーク符号化を実行するために、前記ソースルーティングメカニズムによって検出された一つ以上の経路を選択するステップを含むことができる。
【００１８】
このようにして、局所的ではないものの大きなｎに対するｎホップの近傍領域にわたって作用するメカニズムを実施することができる。これは、前記非連結なノードまたはノード群の間のソースルーティングにより、ネットワーク符号化がエンド・ツー・エンドで適用できる経路を選択することによって達成される。
【００１９】
前記方法は、その一態様として、同じ経路に沿って逆方向に向かうデータレートのバランスを取るステップを更に含むことができる。
【００２０】
データレートのバランスを取ることにより、ネットワーク符号化の効率的な利用が可能となる。
【００２１】
前記方法は、その一態様として、前記ノードまたは前記ノード群によって交換されるデータファイルをいくつかの断片に分割して、それを複数の経路により送信するステップを更に含むことができる。
【００２２】
これによりセキュリティが向上し、傍受（eavesdropping）がより困難となる。
【００２３】
一実施形態によれば、ネットワーク符号化を用いて通信ネットワークにおけるスループットを増加させるための装置であって、
非連結な２つのノードまたはノード群が、符号化実行ノードとなりうるノードのｎホップの半径の近傍領域内において、２つ以上の異なるルートを通してパケットを交換しているか否かを検出する手段と、
前記非連結なノードまたはノード群が交換している逆方向に向かうパケットを前記符号化実行ノードとなりうるノードが線形結合することのできる代替的な双方向経路または複数の単方向経路が存在するか否かを決定する手段と、
ネットワーク符号化が適用可能である前記代替的な双方向経路または複数の単方向経路が、あるメトリックに基づく利得を提供するか否かを決定する手段と、
前記メトリックがネットワーク符号化による利得を示す場合には、前記符号化実行ノードとなりうるノードによるネットワーク符号化が利用できるものとなるように、前記非連結な２つのノードまたはノード群がパケットを交換するルートを変更する手段と
を備える装置が提供される。
【００２４】
このようにして、スループットを増加させるための装置を実施することができる。
【００２５】
前記装置は、その一態様として、符号化実行ノードとなりうるノードが、そのｎホップの近傍領域内のトポロジーとアクティブな経路とについての情報を受信するための手段であって、前記ｎは２以上の自然数である、手段を更に備えることができる。
【００２６】
前記装置は、その一態様として、上記いずれかの態様の方法を実行する手段を更に備えることができる。
【００２７】
一実施形態によれば、上記いずれかの態様の方法をコンピュータに実行させることを可能にするコンピュータプログラムコードを有するコンピュータプログラムが提供される。
【図面の簡単な説明】
【００２８】
【図１Ａ−１Ｄ】各図とも本発明の実施の一形態による方法が適用できる状況の一例を示す図である。
【図２】本発明の実施の一形態による方法のフロー図である。
【図３】本発明の実施の一形態による方法が適用できる状況の更なる例を示す図である。
【図４】本発明の更なる実施形態による方法が適用できる状況の更なる例を示す図である。
【発明を実施するための形態】
【００２９】
最初に以下の説明で用いられる技術用語について説明する。
・ＤＳＲ：Dynamic Source Routing
・ＥＴＸ：Expected Transmission Count
・ＸｏＲ：exclusive OR operation（排他的論理和演算）
・ＡＣＫ：Acknowledgement（確認応答）
・ＭＡＣ：Medium Access Control（媒体アクセス制御）
・ＡＯＤＶ：Ad-hoc On-demand Distance Vector
・ＯＬＳＲ：Optimized Link State Routing
・ＣＯＰＥ：Cooperative Routing
・ＭＯＲＥ：MAC-independent Routing
【００３０】
本発明の実施形態によれば、ルーティングトポロジーを最適化してネットワーク符号化の機会を改善するためのメカニズムが提供される。これはローカルかつエンド・ツー・エンドな方法で実行できる。本発明の実施形態によれば、次の２つのアプローチを使用することができる。
（１）ネットワークにおけるネットワーク符号化の機会を可能なときはいつでも利用しながら、あるノードの近傍のルーティングテーブル内のユニキャスト経路を変更する。本提案手法は、パケットの結合および符号化を行うノード（packet-combining coding node）を生み出す。パケットの結合および符号化を行うノードは、ネットワークの全体のスループットを増加させるために、周辺を移動するパケットを吸収し、それらのパケットを日和見的に結合する。
（２）ネットワークトポロジー内でいくつかの中間ノードを介してマルチホップ接続された２以上のノード群が、既に定められていて、かつ承諾されたネットワーク符号化が使用可能な一連の経路を通じてトラフィックを交換する。
【００３１】
前者のアルゴリズムはローカルでかつ分散型である。これに対して後者はエンド・ツー・エンドで機能し、エンド・ツー・エンドの（例えばソースルーティング型の）ルーティング制御を必要とする。しかしながら、２つ目のアプローチは経路に沿った全てのノードの近傍の情報を必要とするのに対し、１つ目のアプローチはそれぞれのノード群（符号化実行ノードとなりうるあるノード（possible coding node）のｎ回のホップの近傍領域にあるノード。ｎは小さな値であり、例えばｎ＝２。）についての情報を必要とするだけである。２つ目のアプローチは、あるノードを取り囲む一部のノードに対してだけでなくネットワーク内の全てのノード（大きなｎ）に対しても近傍の情報が利用できる場合には、最初のアプローチの「一般化」と見なすことができる。
【００３２】
本発明の実施の一形態によるメカニズムは、反対方向に向かうパケットの異なる経路を単一の双方向無線通信路（bidirectional trunk）に統合して、共有媒体をより有効に利用することによってネットワークの総スループットを増加させる。本発明の実施の一形態によれば、これは、例えば基礎となるルーティングメトリックを修正することによって、ＡＯＤＶまたはＯＬＳＲ等の既存のルーティングアルゴリズムに容易に組み込むことができる。これにより完全にローカライズされたメカニズムが得られる。代わりに、本発明の実施の一形態によれば、ルート変更の決定は、ソースルーティングプロトコルの経路選択メカニズムを修正するかまたは適応させることによってエンド・ツー・エンドで行うことができる。
【００３３】
後者は、既に言及した利点に加えて２つの更なる利点をもたらす。
・異なるノード群の間で情報を交換するための異なる経路を、負荷のバランスをとるために使用することができる。
・異なるペアのノードの間でデータを交換するための異なる経路を、これらの経路に沿って送信されたデータのセキュリティを改善するために使用することができる。
【００３４】
以下、本発明の実施形態を詳しく説明する。
【００３５】
本発明の実施の一形態によれば、パケットの結合および符号化を行うノード（packet-combining coding node）が生まれる。パケットの結合および符号化を行うノードは、それらの周辺を移動する全てのパケットを受信し、それらを日和見的に結合してネットワークの全体のスループットを増加させる働きをする。
【００３６】
本メカニズムの働きのいくつかの例を図１Ａから図１Ｄに概略的に示している。図１Ａから図１Ｄは、符号化の機会を与えてそれにより送信数を減らすために、つまりシステムのスループットを増やすために、ルートをどのように変更するかを示している。
【００３７】
図１Ａにおいて、ノード１はパケットをノード６へ送信しており、同時にノード６はパケットをノード２へ送信している。ノード２は、ノード１の送信範囲に入っているため、ノード１による送信をオーバーヒア（overhear）することができる。従って、ノード３は、送信を節約するためにノード１から受信したパケットとノード６から受信したパケットとを結合することができる。
【００３８】
図１Ｂでは、ノード１およびノード５が、それぞれノード４およびノード２を介してパケットを交換している。しかしながら、ノード３がその特権的な位置（privileged location）を利用して、ノード１およびノード５から受信したパケットの線形結合を実行すると、パケットの交換を行うために必要な送信数を減らすことができる。
【００３９】
図１Ｃでは、ノード５はノード１とノード２をオーバーヒアすることができ、ノード６はノード１とノード３をオーバーヒアすることができ、ノード７はノード２とノード３をオーバーヒアすることができると同時に、ノード４は他の全てのノードをオーバーヒアすることができる。ノード１、ノード２およびノード３は、それぞれパケットＡ、パケットＢおよびパケットＣを連続する３つの時間スロットにおいて送信し、第３番目の時間スロットの最後に、ノード４がパケットＡ、パケットＢおよびパケットＣをバッファに格納したとする。この後、全てのノードがパケットを復号化することができるように、このノード４は第４の時間スロットにおいて一度だけ送信する必要がある。ノード４は、その２ホップ内の近傍領域のリンク状態を認識している（つまり、ノードがどの程度相互に受信（hear）できるかを知っている）だけではなく、その近傍領域におけるアクティブな経路（つまり誰が誰にパケットを送っているか）も認識しているので、これを実行することができる。それ故、ノード４は、図１Ｃに示すように３つの符号化されたパケットを単一の送信コストで送信する３つの単方向経路を提供することができる。
【００４０】
図１Ｄは、２本の別個のフローがネットワークトポロジーにおいて互いに非常に近い経路を逆方向に向かう比較的シンプルな例を示している。両方のルートの中間に位置する経路内の全てのノードが、逆方向に向かうパケットの線形結合を開始すると、送信総数をかなり減少させることができる。図１Ｄにおいて最上部のノードは、一連のパケット｛Ｃ１，Ｃ２，Ｃ３，Ｃ４，Ｃ５およびＣ６｝を最下部のノードへ送信しており、最下部のノードは、一連のパケット｛Ｄ１，Ｄ２，Ｄ３，Ｄ４，Ｄ５およびＤ６｝を最上部のノードへ送信していると想定することができる。最初の時間スロットにおいて最上部のノードと最下部のノードは、Ｃ１とＤ１をそれぞれ送信する。第２番目の時間スロットにおいては、上から２番目のノードと下から２番目のノードがＣ１とＤ１をそれぞれ中継すると同時に、最上部のノードと最下部のノードはＣ２とＤ２をそれぞれ送信する。パケットの送信は、パケットの線形結合が実行されることなく、第４番目の時間スロットまでこのように継続する。第４番目のスロットにおいて、中間のノードは互いに逆方向に向かうパケットＣ１とＤ１の線形結合、すなわちＬ（Ｃ１，Ｄ１）を送信する。第５番目の時間スロットにおいて、中間のノードはＬ（Ｃ２，Ｄ２）を送信すると同時に、隣接する上のノードはＬ（Ｃ３，Ｄ１）を送信し、隣接する下のノードはＬ（Ｃ１，Ｄ３）を送信する。同様に、次の第６番目の時間スロットにおいて、中間のノードはＬ（Ｃ３，Ｄ３）を送信し、隣接する上のノードと隣接する下のノードは、Ｌ（Ｃ４，Ｄ２）とＬ（Ｃ２，Ｄ４）をそれぞれ送信する。パケットの移動は、最上部と最下部のノードがネットワークの他端にあるノードから６つのパケットを受信し終わるまで同じようにして継続する。最後にトータルで５４回の送信が行われ、これは当初の７２回の送信と比べて２５％減少することを示している。ノードごとに実行される送信の回数が図１Ｄに示されている。
【００４１】
一つの問題は、好ましくは近隣ノードが交換しなければならない情報を減らしながら、理想的なパケットの結合および符号化を行うノードをいかにして選択するかである。かかる情報を持つメッセージの明示的または専用の交換は、ある特定のノードが結合および符号化を行うノードになる可能性の尺度または評価をルーティングメトリックに組み込むことにより、完全に回避できる。このときルーティングメトリックは、ネットワーク符号化によって達成可能な潜在的なスループット利得を表すパラメータに基づくとともに、このルーティングメトリックに基づいて、基礎となるルーティングアルゴリズムは、更なる変更を加えることなく、ネットワーク符号化により達成できる利得を考慮したルートを選ぶことができる。
【００４２】
あるいは、ネットワーク符号化を用いて総スループットを増加させるために、自ら選択した符号化実行ノードがその近傍に位置する特定のノードにその中継サービスを明示的に提供することができる。
【００４３】
実施の一形態による符号化実行ノード（coding node）としての自己選択（self-selection）は、主として次の２つの情報、すなわち、１）近隣ノードによって送信されたパケットの次のホップのアドレス（最終の送信先でない）と、２）各ノードのｎホップの近傍領域内のノード間リンクの品質とに依存する。周辺エリア内で送信されたあらゆるパケットの次のホップに関する情報は、ＭＡＣパケットヘッダの宛先アドレスフィールドをオーバーヒアすることによって容易に得ることができる。本発明の実施の一形態によれば、近傍領域内のノード間リンクについての情報は、あらゆるノードにその近傍の各近隣ノードに対するＥＴＸ、あるいは無線マルチホップネットワークの類似のルーティングメトリックを計算させて、選択されたパケットのヘッダに（ｎ−１）ホップの近傍領域内の近隣ノードの最新の完全なリストとそれらに関連するリンクのＥＴＸ値とを含ませることによって収集できる。一実施形態ではｎの値として２を選択するが、他の選択も可能である。これによって、ネットワーク内のあらゆるノードは、ｎ回のホップの範囲内にある近傍領域内の周辺トポロジーについての最新情報を得る。この手順により、全てのノードは、ｎホップの半径内の周辺トポロジーのリンク状態マップを生成し、周辺状態を検出した際にパケットの結合および符号化を行うノードになるための良い候補として自己を取捨選択することができる。符号化実行ノードの自己選択は、ｎホップの近傍領域内だけのルートに直接影響を及ぼすが、近隣ノードのチェーン（chain）における符号化実行ノードの自己選択の継続的な計算は、図１Ｄに示すようにマルチホップ経路を変更することで終わることもある。
【００４４】
本発明の実施の一形態によれば、システム内のあらゆるノードは、定期的に（ｎ−１）ホップの近傍領域内のノードのリストと、それらの各リンクのＥＴＸ測定値（またはノード間リンクの任意の他の品質指標）、すなわち｛近隣ノード、ＥＴＸ｝とを同報する。実際は、本発明の実施の一形態によれば、ＥＴＸ情報を交換するためのオーバヘッドを制限するために、例えばｎ＝２などの小さな値が選ぶことができる。
【００４５】
一般に、本発明の実施の一形態によれば、任意のノードＡが自己を符号化実行ノード（coding node）として選択するには、以下の２つの条件が同時に検出されなければならない。
条件１：  ｎ回のホップを有する半径の近傍領域内の非連結な２つのノードまたは（いずれのノードも他のドメイン内のノードと直接的に通信することができない）一連のノードが、ノードＡを経由するかまたは経由しなくてもよいトポロジー内の２以上の異なるルートを通してパケットを交換している。
条件２：  ノードＡは、関与する通信領域において、特定のルーティングメトリックに基づいて、代替の「良質の双方向経路または複数の単方向経路」を有する。かかる双方向経路または複数の単方向経路において、ノードＡは、連結していない領域（連結していないノードまたは一連のノード）によって交換されている逆方向に向かうパケットを線形結合することができる。
【００４６】
代替的に、双方向経路または複数の単方向経路のどちらかが使用できる。例えば、図３では、ノードＦ２から中間ノードへのリンクは、ちょうどノードＦ１から中間ノードへ向かうリンクのように単方向とすることができ、それらは中間ノードをヒアする必要はない。また、受信機は中間ノードへ送信する必要はない。
【００４７】
本発明の実施の一形態によれば、上記２つの条件を満足するノードは、ｎ回のホップの近傍領域における当初のルート内のノードへ新たな双方向経路を提供する。これらのノードは、その提供を受理または拒否する。ノードが提供を受理する場合、一つまたは複数の符号化実行ノードは、それらの全てに確認メッセージ（confirmation）を送信する。確認メッセージを受信すると、ノードは一つまたは複数の結合ノードに向けてパケットの送信を開始する。
【００４８】
図２は、かかるメカニズムの疑似アルゴリズム（pseudo-algorithm）を示している。最初に、アクティブフロー（またはルート）を検出し、ネットワーク符号化が適用された場合のＮＣ（network coding）利得を決定する。結果として得られるリンクコストをフローに参加しているノードへ通知し、続いて新たなルートをこれらのノードが受理（または拒否）する。受理すると、ノードがそれらのルーティングテーブルのエントリを更新することができるように確認メッセージを送信する。
【００４９】
図３は、符号化実行ノードとなりうるノード（potential coding node）が、２回のホップの近傍内を逆方向に向かう２本のアクティブデータストリームを検出する一般的な例を示している。このケースでは、符号化実行ノードは、図２に示した疑似アルゴリズムに従い、ＮＣ利得を考慮したより低いリンクコストをノードＦ１およびノードＦ２に通知する。ルーティングアルゴリズムが使用する下記のリンクコスト（例えばＥＴＸ値とすることができる）は、次の様にＮＣ利得を表す係数によって修正することができる。
Ｌｉｎｋ＿Ｃｏｓｔ＝ＮＣ＿Ｇａｉｎ・ＥＴＸ
ここで、ＮＣ＿Ｇａｉｎは、主にスループット利得（例えば１／２または１／３）を表す。このようにして、ネットワーク符号化によって実現されるスループット利得を表すルーティングメトリックが得られる。関与する全てのノードがそれらのルートの変更を承諾する場合には、それらは符号化実行ノードへフィードバックを送信する。続いて符号化実行ノードは確認メッセージを送信し、対応するルーティングテーブルのエントリが変更される。
【００５０】
次にもう一度、図１Ａから図１Ｄに示された例を参照する。図１Ａにおいてノード３は、その通信範囲内にあるノード（ノード６）がやはり同じくその通信範囲内にあるノードのペアと送受信を行っていることを検出した後に、自己を符号化実行ノードとして選択する。自己を符号化実行ノードとして選択した後に、ノード３は、ノード４およびノード５がそれぞれノード６およびノード２に到達するためにノード１およびノード６の中継として動作する場合よりも低いルーティングコストを通知する。あるいは、ノード３は、ノード１およびノード６に対し、それぞれノード６とノード２に到達するための中継となることをオファーすることができる。そのオファーをノード６およびノード２の両方が受理すると、ノード３はノード２に対しオーバヒアリングメカニズムを動作させるよう指示し、ノード２がノード１によって送信されたパケットをオーバーヒアできるようにする。ノード３は、近傍リンクのＥＴＸ測定値の同報により、ノード１およびノード２が通信範囲内にあることを認識している。
【００５１】
図１Ｂでは、ノード３はノード１およびノード５がパケットを交換していることを検出し、それらの両方にそれぞれノード４およびノード２の代わりに中継の役割を果たすことができることをオファーする。
【００５２】
図１Ｃでは、ノード４は、ノード１、ノード２およびノード３がノード７、ノード６およびノード５にそれぞれデータを送信していることを検出する。ノード４は、ノード６およびノード５がノード１の送信をオーバーヒアすることができ、ノード５およびノード７がノード２の送信をオーバーヒアすることができ、ノード６およびノード７がノード３の送信をオーバーヒアすることができることを観測する。受信端末はそれ自身の発信元以外の他の発信元ノードをオーバーヒアできるため、ノード４は、ノード１、ノード２およびノード３に対し、対応する宛先ノードに到達するための中継としての役割を果たすことをオファーする。
【００５３】
図１Ｄでは、ノードＣとノードＤが、異なる２本の経路を通して複数のパケットを交換している。この２本の経路の中間にあるノードは、逆方向に向かうパケットを結合してネットワークスループットをかなり増加させるため、（ＥＴＸの点で）「良質の」双方向経路をオファーできることを認識する。
【００５４】
これまで述べてきたメカニズムは、ローカルなレベル、つまりｎを例えばｎ＝２といった小さな整数としてｎホップの近傍領域内で機能している。しかしながら、より大きなｎの範囲に拡張することもできる。
【００５５】
次に、かかるメカニズムの例を説明する。これらのメカニズムは図１Ｄで説明した例の拡張と考えることができる。ここでは、逆方向に向かうパケットを線形結合できるマルチホップ経路の確立を取り扱う。以下の実施形態は、かかるエンド・ツー・エンド型メカニズムに基づく。
【００５６】
実施の一形態によれば、データトラフィックを交換するトポロジー的には非連結な２つの近隣ノードの集合は、逆方向に向かうパケットを線形結合することによりネットワーク符号化を双方向トラフィックに適用できる一連のソースルーティング経路を承諾（agree）することができる。より良いスループット利得を得るため、単方向パケットサイズおよびデータレートは、経路の共通区分に沿って両方向で均一化できる。従って、例えば図４に示すように、非連結な２つのノード群は、パケットが符号化される複数の経路を通してパケットを交換している。あるノード群においてあらゆるノードに全ての交換パケットの複製が存在すると仮定することができる。複製（レプリカ）を群内部に分散させるためのメカニズムに関して、群内のノードも例えばEthernet（登録商標）ネットワークまたは高速無線ネットワーク等の高速かつセキュアな接続により相互接続されていると仮定することができる。
【００５７】
本発明の実施の一形態によれば、メカニズムは以下に示す一般的なルールに基づいて動作する。
（１）ノード群１またはノード群２は、この２つのノード群の間でパケットの交換が行われていることを、その群内のアクティブフローについての情報を取得することによって検出する。
（２）ノード群１およびノード群２は、交換されている流出入パケットの平均データレートについての情報を収集し、交換する。
（３）ノード群１およびノード群２は、（好ましくはセキュリティに関する）ソースルーティングメカニズムを実行して、それらの間の（好ましくは良いエンド・ツー・エンドの品質と、場合によっては確認済みの信頼できるノードを有する）既存の経路を発見する。
（４）ステップ（３）で見つかった経路のリストからノード群１およびノード群２は、パケットを交換するためにいくつかの経路を選択し、同じ経路に沿って逆方向に向かうデータレートにバランスをとる試みを行う。一般に、ソースルーティング経路は、逆方向に向かう平均データレートを相殺（オフセット）するように構築すべきである。
（５）両方のノード群の間で交換される非リアルタイムデータファイルは、数個の断片（ピース）に分割され、ソースルーティングメカニズムを使って複数の経路を通して送信することができる（例えば非特許文献「David B. Johnson, “Routing in Ad Hoc Networks of Mobile Hosts", Proceedings of the Workshop on Mobile Computing Systems and Applications, pp. 158-163, IEEE Computer Society, Santa Cruz, CA, December 1994」参照）。ただし、リアルタイムトラフィックは、遅延時間とジッター（jitter）の制約を観察するために原則としてただ１つの経路で送信されなければならない。双方向経路は動的に変更できるが、これらの変更は、データを交換する両方の群によって調整されなければならない。
【００５８】
図４は、ノード群１およびノード群２が６つの異なるファイル｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ｝を交換している例を示している。図中の代数的演算子（algebraic operator）Ｌ（＊）は、ランダムな係数を使用してパケットの線形結合を生成する。パケットの交換を開始する前に、ノード群１およびノード群２は、ソースルーティングの方法で各パケットのヘッダに付け加えられた一連の経路を承諾（agree）する。本発明の実施の一形態によれば、経路は、エンド・ツー・エンド容量および／またはどのノードが信頼できてどのノードが信頼できないかといったセキュリティに基づいて決定される。
【００５９】
容量の検討に関して、本発明の実施の一形態によれば、全ての経路は、逆方向に向かうデータトラフィック量の間のバランスを保つように生成されるべきである。各ファイルは単一経路で送信されるか、または図４に示すように複数の部分に分割された上で部分ごとに異なる経路で逐次的に送信される。経路は、トラフィックの状態に応じて、またはセキュリティもしくはプライバシーの理由により動的に変更することができる。図４において、Ａ１およびＡ２のようなファイルＡのファイル断片またはＤ１およびＤ２のようなファイルＤのファイル断片は、ソースルーティング経路にわたってランダムな係数を用いて線形結合される。結合するファイルの断片が異なるサイズを持つ場合には、パッディングの手法を利用してそれらのサイズを等しくすることができる。本発明の実施の一形態によるパケットの線形結合は、ランダムな係数で重み付けするとともに送信バッファで待機している全てのパケットを、２を法として加える（modulo-2 adding）日和見的な方法で実行しなければならない。本発明の実施の一形態によれば、例えば送信バッファにたった１つのパケットしか存在しない場合などに更なる待機遅延（queuing delay）が一切生じないように、線形結合は即座に生成される。
【００６０】
上記の実施形態は、ハードウェア、ソフトウェア、あるいはハードウェアとソフトウェアの組み合わせによって実施することができることは当業者であれば理解できよう。本発明の実施形態に関連して説明されたモジュールおよび機能は、全体的または部分的に、本発明の実施形態に関連して説明された方法の通りに動作するように適切にプログラムされたマイクロプロセッサまたはコンピュータによって実現することができる。本発明の実施形態を実現する装置は例えば、本発明の実施形態で説明されたメカニズムを実行することが可能なように適切にプログラムされたネットワーク内のノードその他の構成要素を構成することができる。例えば、ネットワークノードがそれらが本発明の実施形態に関連して述べたノードとして機能するようにプログラムされることがあり、それより本発明の実施形態が実際に実現される。
【００６１】
本発明の実施の一形態として、データキャリアに格納された、あるいは他の方法で記録媒体もしくは伝送リンクといった何らかの物理的手段によって具現化されたコンピュータプログラムであって、コンピュータ上で実行されたときにこのコンピュータが上記実施形態に従って動作することを可能にするコンピュータプログラムが提供される。
【００６２】
本発明の実施形態は、例えば、上述したメカニズムに従って動作するようにプログラムされた、ネットワーク内のノードまたはネットワーク内の任意のエンティティによって実施することが可能である。
【符号の説明】
【００６３】
１〜６  ネットワークノード
Ａ〜Ｆ  データファイル
Ａ＊〜Ｆ＊  データファイル断片
Ｌ（＊）  線形結合演算子
【図２】
0004783839.tif 000002
【図１Ａ】
0004783839.tif 000003
【図１Ｂ】
0004783839.tif 000004
【図１Ｃ】
0004783839.tif 000005
【図１Ｄ】
0004783839.tif 000006
【図３】
0004783839.tif 000007
【図４】
0004783839.tif 000008