JP2012157005A - データ再送方法およびその装置 - Google Patents

Abstract

【課題】再送回数を減少させ、再送効率を向上させるデータ再送方法および再送装置を提供する。
【解決手段】ソースノードが、Ｎ個（Ｎは自然数）のデータパケットの伝送を完了した後、このＮ個のデータパケットのパケットロスパターン行列を取得し、ソースノードが、取得されたパケットロスパターン行列を分析して、再送対象データパケットの組み合わせ方式を得、ソースノードが、再送対象データパケットの組み合わせ方式に従って、再送対象データパケットに対して組み合わせ符号化を行って、再送対象の符号化パケットを得、符号化パケットを順に再送する。
【選択図】図２

Description

本発明は、ネットワーク符号化技術に関し、特に、データ再送方法およびその装置に関する。

ネットワーク符号化技術は、ルーティングと符号化とを融合させた情報交換技術であり、ネットワークの中間ノードが、受信された情報フローに対しある程度の符号化処理を行う、ということが許されることを基本思想とする。これにより、ネットワーク情報フローは、マルチキャスト伝送の最大フローの限界に達することができる一方、伝統的な蓄積転送モードでは、情報フローがマルチキャスト伝送の最大フローの限界に達することができない。ネットワーク符号化では、ネットワークの情報容量が十分に利用され、既存のネットワーク資源の利用率が極めて向上し、幅広く応用される見込みがある。

便宜主義的なネットワーク符号化とは、ノードが全ての隣接ノードからブロードキャストされたデータパケットを監視して記憶し、該ノードが中間ノードから送信された符号化パケットを受信した後、キャッシュされたデータパケットを利用して、符号化パケットに対して復号化演算を行い、最後に、オリジナルデータパケットを回復する、ことである。

無線ネットワークにおけるチャネルのブロードキャスト特性について、便宜主義的なネットワーク符号化は、無線伝送の研究に応用され、情報伝送回数の減少、ネットワークスループットおよびエネルギー利用効率の向上、時間遅延の低下、並びに伝送信頼性の向上に用いられる。同様に、便宜主義的なネットワーク符号化の思想が無線マルチキャストネットワークの再送に応用されると、平均再送回数を明らかに減少させることもできる。現在の段階で、有線チャネルよりも高いビット誤り率およびパケットロス率を無線チャネルが有することに鑑みてなされて、再送効率を如何に向上させるかが、無線通信システムにおける解決すべきキー問題の１つになっている。

本発明の実施例では、データ再送方法およびその装置が提供されている。これにより、再送回数を減少させ、再送効率を向上させる。

本発明の実施例で提出されたデータ再送方法は、ソースノードが、Ｎ個（Ｎは自然数）のデータパケットの伝送を完了した後、このＮ個のデータパケットのパケットロスパターン行列を取得するステップＡと、ソースノードが、取得されたパケットロスパターン行列を分析して、再送対象データパケットの組み合わせ方式を得るステップＢと、ソースノードが、再送対象データパケットの組み合わせ方式に従って、再送対象データパケットに対して組み合わせ符号化を行って、再送対象の符号化パケットを得、符号化パケットを順に再送するステップＣと、を含む。

ここで、このＮ個のデータパケットのパケットロスパターン行列を取得することは、ソースノードが、Ｎ個のデータパケットの伝送を完了した後、端末からフィードバックされたＡＣＫ／ＮＡＫに基づいて、パケットロスパターン行列を作成する、ことを含む。

具体的に、ソースノードが１つのデータパケットの伝送を完了したごとに、全ての端末が、ＡＣＫ／ＮＡＫを利用して、自局のパケットロス状況を同期フィードバックし、ソースノードが、Ｎ個のデータパケットの伝送を完了した後、全ての端末からフィードバックされたＡＣＫ／ＮＡＫに基づいて、パケットロスパターン行列を作成する。あるいは、ソースノードが１つのデータパケットの伝送を完了したごとに、前記データパケットを受信する全ての端末のうちのＭ個の端末が、ＡＣＫ／ＮＡＫを利用して、自局のパケットロス状況を同期フィードバックし、ソースノードが、Ｎ個のデータパケットの伝送を完了した後、前記Ｍ個の端末からフィードバックされたＡＣＫ／ＮＡＫに基づいて、パケットロスパターン行列を作成する。

上記の方法は、ソースノードが、端末から送信された基準信号に基づいて、全ての端末の中から、信号品質が最も悪いＭ個の端末を、ＡＣＫ／ＮＡＫをフィードバックする端末として選択し、下り制御シグナリングを介して、前記Ｍ個の端末に対し、ＡＣＫ／ＮＡＫをフィードバックするよう通知する、ことをさらに含んでもよい。

前記Ｍの好ましい値の範囲は、１０〜１５であり、例えば、１０に等しくてもよい。

ソースノードが、取得されたパケットロスパターン行列を分析して、再送対象データパケットの組み合わせ方式を得ることは、パケットロスパターン行列から、要素が全部ゼロである列を除去して、ゼロ除去パケットロスパターン行列を得、ゼロ除去パケットロスパターン行列を２つのサブ行列に分割し、ここで、第１のサブ行列の各列毎に対応する符号化パケットが、組み合わせて再送されることができる複数のデータパケットである一方、第２のサブ行列の各列毎に対応するデータパケットが、ほかのデータパケットと組み合わせて再送されることができないデータパケットであり、分割後の第１のサブ行列と第２のサブ行列との列をさらに併合して、第２のパケットロスパターン行列と第３のサブ行列とを得、ここで、併合後の第２のパケットロスパターン行列の列の要素のうち、多くとも１つのみが２に等しく、第３のサブ行列の列を第２のパケットロスパターン行列に併合して、再送対象データパケットの組み合わせ方式を反映する第３のパケットロスパターン行列を得、ここで、併合後の列の全ての要素が、いずれも１以下である、ことを含む。

パケットロスパターン行列から、要素が全部ゼロである列を除去することは、パケットロスパターン行列Ωにおける全ての要素がゼロである列を抽出して、１つのサブ行列ω^０を構成し、残りの列でゼロ除去パケットロスパターン行列ω^αを構成する、ことを含む。

ここで、ゼロ除去パケットロスパターン行列を２つのサブ行列に分割することは、ゼロ除去パケットロスパターン行列ω^αの列を順に選択し、ゼロ除去パケットロスパターン行列ω^αから選択された下記の、ほかの列で選択されたことがないという条件（１）と、∀ｉ、併合後のＲ_ｉ（θ_βｋ）≦１であるという条件（２）と、を満たす全ての列を加算して、列θ_βｋを生成し、ここで、Ｒ_ｉ（θ_βｋ）は、列ベクトルθ_βｋ（１≦ｋ≦Ｋ）のｉ行目の要素の値を表し、選択された列に対応するデータパケットに対して、ビットのモジュロ２加算を基本演算とする組み合わせ符号化を行って、符号化パケットＰ_ｋを得、加算後の列を第１のサブ行列ω^βに入れ、併合できない列を第２のサブ行列ω^γに入れる、ことを含む。

分割後の第１のサブ行列と第２のサブ行列との列をさらに併合して、第２のパケットロスパターン行列と第３のサブ行列とを得ることは、第２のサブ行列ω^γの全ての列を、第１のサブ行列ω^βの末尾に追加して、第２のパケットロスパターン行列ω^βγを構成し、元の第２のサブ行列ω^γの各列θγ_ｌ（１≦ｌ≦Ｌ）に対して、第２のパケットロスパターン行列ω^βγから、θγ_ｌとθ_βγＳとを併合してθ_βγＳ ^＋を得る場合、∀ｉ、Ｒ_ｉ＊（θ_βγＳ ^＋）＝２となるユーザｉ^＊は１つしかないという条件を満たす列θ_βγＳ（１≦ｓ≦Ｌ＋Ｋ，ｓ≠ｌ）を選択し、ここで、Ｒ_ｉ＊（θ_βγＳ ^＋）は、列ベクトルθ_βγＳ ^＋のｉ^＊行目の要素の値を表し、Ｍ次元のゼロ列ベクトルｅを生成して、ｅ（ｉ^＊）＝１かつ列ベクトルｅとθγ_ｌとに対応するデータパケットが同じであるようにし、そして、列ベクトルｅを第３のサブ行列ω^μに入れ、最後に、θγ_ｌに対応するデータパケットを、θ_βγＳに対応する符号化パケットＰｓに組み入れる、ことを含む。

第３のサブ行列の列を第２のパケットロスパターン行列に併合することは、第３のサブ行列ω^μの列ベクトルｅに対して、ｅ（ｉ^＊）＝１であり、ω^βγの列θ_βγｈ（１≦ｈ≦Ｈ）を順に判断し、Ｒ_ｉ＊（ｅ∪θ_βγｈ）＝１を満たす場合、ｅの目標列がθ_βγｈであると判断し、そして、ｅを目標列に加算し、ここで、Ｒ_ｉ＊（ｅ∪θ_βγｈ）＝１であり、列ベクトルｅと列ベクトルθ_βγＳとのｉ^＊行目の要素の値の和を表し、列ベクトルｅに対応するデータパケットを、目標列θ_βγｈに対応する符号化パケットＰ_ｈ（１≦ｈ≦Ｈ）に組み入れて、第３のサブ行列ω^μから、列ベクトルｅを除去し、第３のサブ行列ω^μにおける等しくない列ベクトルをグループ構成して加算し、得られた列を第３のパケットロスパターン行列に入れ、そして、各グループごとに、該グループ内の各列ベクトルに対応するデータパケットに対して、組み合わせ符号化を行って、符号化パケットを得る、ことを含む。

ソースノードが、再送対象データパケットの組み合わせ方式に従って、再送対象データパケットに対して組み合わせ符号化を行って、再送対象の符号化パケットを得ることは、ソースノードが、第３のパケットロスパターン行列の各列毎に対応する符号化パケットまたはデータパケットに示す組み合わせ方式に従って、再送対象データパケットに対して、ビットのモジュロ２加算を基本演算とする組み合わせ符号化を行って、再送対象の符号化パケットを得る、ことを含む。

本発明の実施例に係るデータ再送方法は、ステップＢを実行するとともに、伝送する必要があるデータパケットがあるかどうかを判断し、伝送する必要があるデータパケットがある場合、Ｎ′＝ｆｌｏｏｒ（△Ｔ／Ｔ_Ｓ）＜Ｎ個の新しいデータパケットを続けて伝送し、ここで、△Ｔは、ソースノードがパケットロスパターン行列を分析して、再送対象データパケットの組み合わせ方式を得るために必要な処理時間であり、Ｔ_Ｓは、ソースノードＳが１つのデータパケットを送信するにかかる時間を表し、ｆｌｏｏｒ（Ｘ）関数は、有理数Ｘより大きい最小整数を取ることを表し、ステップＣを実行した後、Ｎ−Ｎ′個のデータパケットを続けて伝送して、新に伝送されたＮ個のデータパケットのパケットロスパターン行列を得てから、ステップＢに戻る、ことをさらに含む。

また、ソースノードが符号化パケットを再送するための最大再送回数は５回以下である。

本発明の実施例に係るデータ再送装置は、Ｎ個（Ｎは自然数）のデータパケットの伝送を完了したごとに、このＮ個のデータパケットのパケットロスパターン行列を取得するパケットロスパターン行列取得手段と、取得されたパケットロスパターン行列を分析して、再送対象データパケットの組み合わせ方式を得る組み合わせ方式決定手段と、再送対象データパケットの組み合わせ方式に従って、再送対象データパケットに対して組み合わせ符号化を行って、再送対象の符号化パケットを得る符号化手段と、符号化パケットを順に再送する再送手段と、を含む。

ここで、組み合わせ方式決定手段は、パケットロスパターン行列から、要素が全部ゼロである列を除去して、ゼロ除去パケットロスパターン行列を得るゼロ除去モジュールと、ゼロ除去パケットロスパターン行列を２つのサブ行列に分割し、ここで、第１のサブ行列の各列毎に対応する符号化パケットが、組み合わせて再送されることができる複数のデータパケットである一方、第２のサブ行列の各列毎に対応するデータパケットが、ほかのデータパケットと組み合わせて再送されることができないデータパケットである分割モジュールと、分割後の第１のサブ行列と第２のサブ行列との列をさらに併合して、第２のパケットロスパターン行列と第３のサブ行列とを得、ここで、併合後の第２のパケットロスパターン行列の列の要素のうち、多くとも１つのみが２に等しい拡張モジュールと、第３のサブ行列の列を第２のパケットロスパターン行列に併合して、再送対象データパケットの組み合わせ方式を反映する第３のパケットロスパターン行列を得、ここで、併合後の列の全ての要素が、いずれも１以下である合併モジュールと、を含む。

本発明の実施例に係るデータ再送方法およびその装置は、パケットロスパターン行列を分析することで、再送対象データパケットを効果的に組み合わせて、再送対象データパケットの組み合わせ方式を得ることができる。これにより、再送回数を減少させ、再送効率を向上させる。

無線マルチキャストネットワークのトポロジーモデルを示す図である。 本発明の実施例に係るデータ再送方法のフローチャートである。 本発明の実施例に係るデータ再送装置の構成を示す図である。 データパケットを受信する端末の数が１０００であり、本実施例のデータ伝送方法を採用するとき、全部フィードバックまたは一部フィードバックの場合での復号化成功確率と再送回数との関係をそれぞれ示すグラフである。 一部フィードバック回数と復号化成功確率との関係を示すグラフである。

無線マルチキャストネットワークの再送効率を向上させるために、本発明の実施例では、データ再送方法が提供されている。

本実施例において、再送アルゴリズムを実施する無線マルチキャストネットワークのトポロジーモデルは、図１に示す通りである。図１に示す無線マルチキャストネットワークにおいて、Ｓは、ソースノードを表し、Ｔ_ｉ（１≦ｉ≦Ｍ）は、Ｍ個の端末を表し、Ｓは、Ｎ個のデータパケットＰ_ｊ（１≦ｊ≦Ｎ）をブロードキャスト送信し、ＭとＮは、自然数であり、１つのデータパケットの送信（または再送）を完成するタイムスロットは、ＳＴであり、その期間で、全ての端末Ｔ_ｉは、ＡＣＫ／ＮＡＫを利用して、自局のパケットロス状況を同期フィードバックするとともに、自局の番号ｉをＳに知らせる。本発明において、ＡＣＫ／ＮＡＫおよび再送パケットの送信は信頼性があり、つまり、ロスがないと仮定する。Ｓは、Ｎ個のデータパケットの送信を完了した後、Ｍ個の端末からフィードバックされたＡＣＫ／ＮＡＫ情報に基づいて、Ｍ個の端末のパケットロスパターン（Ｌｏｓｓ Ｐａｔｔｅｒｎ）を得ることができる。このパケットロスパターンは、１つのＭ×Ｎの行列で表すことができ、パケットロスパターン行列Ωと記す。Ωの要素β_ｉｊは、ｉ番目のユーザがｊ番目のデータパケットを受信したかどうかを表し、β_ｉｊの値の範囲は｛０，１｝であり、ここで、β_ｉｊが０に等しいことは、受信成功を表し、β_ｉｊが１に等しいことは、パケットロスを表す。Ωにおいて、ｉ行目は、端末Ｔ_ｉのパケットロス状況を表し、ｊ列目は、データパケットＰ_ｊの受信状況を表す。下記の表１は、パケットロスパターン行列Ωの一例を示す。表１では、Ｎ＝１０、Ｍ＝５とする。

説明の便宜上、本発明の具体的な実施形態を説明する前に、まず、以下のいくつかの定義を与える。

定義１：サイズがＭ×ｎ（ｎ≦Ｎ）であるパケットロスパターン行列Ωのサブ行列ωである。ここで、Ｍは、端末の数を表し、Ｎは、データパケットの数を表し、かつ、Ｍ，Ｎ≧１である。

定義２：Ｒ_ｉ（ω）は、行列ωのｉ行目の全ての要素の値の和を表し、そのため、０≦Ｒ_ｉ（ω）≦ｎ（１≦ｉ≦Ｍ）であり、Ｃ_ｊ（ω）は、ωのｊ列目の全ての要素の値の和を表し、そのため、０≦Ｃ_ｊ（ω）≦Ｍ（１≦ｊ≦ｎ）であり、Ｏ（ω）は、ωのＲ_ｉ（ω）≠０の数を表し、これにより、０≦Ｏ（ω）≦Ｍを得ることができる。

定義３：Ｄ_ｊ（１≦ｊ≦Ｎ）は、全ての端末がデータパケットＰ_ｊを回復するための計算オーバーヘッドを表す。具体的に、ある端末がＰ_ｊを回復する際に、一回の排他的論理和演算を行うごとに、Ｄ_ｊを１加算する。

１つの端末がε（１≦ε≦Ｎ）個のデータパケットをロスした場合、該端末は、各々の再送パケットから、多くとも１つのデータパケットを得る。そのため、再送アルゴリズムでは、少なくともε回の再送が必要となり、多くともＮ回の再送が必要となる。Ｍ個の端末がε_１，ε_２，…ε_Ｍ個のデータパケットをそれぞれロスした場合、ブロードキャスト方式に従って再送を行う際に、再送アルゴリズムの再送回数Ｒｔは、必ず、下記の数式１に示す条件を満たす。

［数式１］
Ｍａｘ（ε_ｉ）＜Ｒｔ≦Ｍｉｎ（Ｎ，Σε_ｉ），ｉ＝１，２，…，Ｍ

本発明の実施例に係るデータ再送方法の主要な目標は、再送回数Ｒｔをできるだけ減少させることにある。以下、具体例および図面を参照しながら、本発明の実施例を詳しく説明する。図２に示すように、本発明の実施例により提供されたデータ再送方法は、主に下記のステップを含む。

ステップ１で、ソースノードＳは、Ｎ個のデータパケットの伝送を完了した後、パケットロスパターン行列Ωを取得する。

無線マルチキャストネットワークにおいて、端末は、全部フィードバックまたは一部フィードバックという方式を採用して、自局のパケットロス状況をソースノードＳへフィードバックすることができる。

全部フィードバックという方式の場合、ソースノードＳが１つのデータパケットの伝送を完了したごとに、全ての端末は、ＡＣＫ／ＮＡＫを利用して、自局のパケットロス状況を同期フィードバックするとともに、自局の番号ｉをソースノードＳに知らせる。例えば、データパケットを正確に受信した場合、ＡＣＫをフィードバックし、データパケットを受信しなかった場合または受信エラーの場合、ＮＡＫをフィードバックする。このようにして、ソースノードＳは、Ｎ個のデータパケットの伝送を完了した後、全ての端末からフィードバックされたＡＣＫ／ＮＡＫに基づいて、パケットロスパターン行列Ωを作成することができる。例えば、Ｍ×Ｎの行列を作成し、その中の要素β_ｉｊは、ｉ番目のユーザがｊ番目のデータパケットを受信したかどうかを表し、β_ｉｊの値の範囲は｛０，１｝であり、ここで、β_ｉｊが０に等しいことは、受信成功を表し、β_ｉｊが１に等しいことは、パケットロスを表す。

一部フィードバックという方式の場合、ソースノードＳが１つのデータパケットの伝送を完了したごとに、無線マルチキャストネットワークにおける一部の端末は、ＡＣＫ／ＮＡＫを利用して、自局のパケットロス状況を同期フィードバックするとともに、自局の番号ｉをソースノードＳに知らせる一方、それ以外の端末は、自局のパケットロス状況をソースノードＳへフィードバックしない。この場合も、ソースノードＳは、Ｎ個のデータパケットの伝送を完了した後、上記一部の端末からフィードバックされたＡＣＫ／ＮＡＫに基づいて、パケットロスパターン行列Ωを作成することができる。例えば、同様にＭ×Ｎの行列を作成し、その中の要素β_ｉｊは、ｉ番目のユーザがｊ番目のデータパケットを受信したかどうかを表し、β_ｉｊの値の範囲は｛０，１｝であり、ここで、β_ｉｊが０に等しいことは、受信成功を表し、β_ｉｊが１に等しいことは、パケットロスを表し、Ｍは、自身のパケットロス状況をソースノードＳへフィードバックする端末の数を表す。

ステップ２で、ソースノードＳは、パケットロスパターン行列Ωを分析して、再送対象データの組み合わせ方式を得る。つまり、ソースノードＳは、パケットロスパターン行列Ωを分析して、再送パケットが送信されるときのロスパケット組み合わせ方式を得る。

ステップ３で、ソースノードＳは、再送対象データパケットの組み合わせ方式に従って、再送対象データパケットに対して組み合わせ符号化を行って、再送対象の符号化パケットを得、符号化パケットを順に再送する。

本ステップにおける組み合わせ符号化は、具体的に、ビットのモジュロ２加算を基本演算とする組み合わせ符号化である。

本実施例において、ソースノードＳは、パケットロスパターン行列Ωを分析することで、再送対象データパケットを効果的に組み合わせて、再送対象データパケットの組み合わせ方式を得ることができる。これにより、再送回数を減少させ、再送効率を向上させる。

上記のステップ２では、ソースノードＳは、パケットロスパターン行列Ωを分析して、再送対象データパケットの組み合わせ方式を得ることは、具体的に、ゼロ除去、分割、拡張および合併という４つの過程を含む。以下、この４つの過程について、それぞれ詳しく説明する。

ゼロ除去という第１の過程は、即ち、パケットロスパターン行列Ωから、全ての要素がゼロである列を除去することである。

Ｍ個の端末でのパケットロスの発生確率が互いに独立であるため、パケットロスパターン行列Ωにおける値が１である要素の位置もまったくランダムである。Ωの各列における値が１である要素数により、Ωを２つのサブ行列ω^０とω^αに分割することができる。この２つのサブ行列は、行数がいずれもＭであり、列数がそれぞれｎ_０とｎ_αである_。ω^０とω^αは、定義１を満たし、かつ、ｎ_０＋ｎ_α＝Ｎを満たす。ここで、ω^０は、ゼロ行列であり、Ｃ_ｊ（ω^０）＝０を満たす。ω^αは、Ωにおける０＜Ｃ_ｊ（ω^α）≦Ｍを満たす列により構成され、ゼロ除去パケットロスパターン行列と呼ばれる。つまり、上記の過程では、パケットロスパターン行列Ωの中から、全ての要素がゼロである列を抽出して、１つのサブ行列ω^０を構成し、残りの列でゼロ除去パケットロスパターン行列ω^αを構成する。ω^０とω^αのうちの少なくとも１つが存在し、もしいずれかの行列が存在しなければ、該行列の列数が０である。ここで、サブ行列ω^０に対応するデータパケットは、既に全ての端末で正確に受信されたので、再送する必要がないものである。一方、ゼロ除去パケットロスパターン行列ω^αに対応するデータパケットは、再送する必要があるものである。

表１に示すパケットロスパターン行列Ωを例として、ω^０は、Ωの５列目であり、ω^αは、Ωにおける５列目以外の残りの９列により構成される。下記の表２は、表１に示すパケットロスパターン行列Ωに対して、ゼロ除去処理を行って得られたゼロ除去パケットロスパターン行列ω^αを示す。

分割という第２の過程は、即ち、ゼロ除去パケットロスパターン行列ω^αを２つのサブ行列に分割することである。ここで、第１のサブ行列の各列毎に対応する符号化パケットは、組み合わせて再送されることができる複数のデータパケットである一方、第２のサブ行列の各列毎に対応するデータパケットは、ほかのデータパケットと組み合わせて再送されることができないデータパケットである。つまり、ゼロ除去パケットロスパターン行列ω^αの列を処理して、第１のサブ行列ω^βと第２のサブ行列ω^γとの２つの新しいパケットロスパターンサブ行列に分割する。ここで、第１のサブ行列ω^βの列θ_βｋ（１≦ｋ≦Ｋ）は、符号化パケットＰ_ｋに対応する。第１のサブ行列ω^βの要素η_ｉｊは、ｊ番目の符号化パケット組み合わせにおけるｉ番目のユーザのロスパケットの数を表し、η_ｉｊの値の集合は｛０，１｝である。第２のサブ行列ω^γは、ゼロ除去パケットロスパターン行列ω^αのサブ集合である。

上記の分割過程は、具体的に、下記のステップを含む。

１番目のステップで、ゼロ除去パケットロスパターン行列ω^αの列を順に選択し、ゼロ除去パケットロスパターン行列ω^αから選択された下記の、ほかの列で選択されたことがないという条件（１）と、∀ｉ、併合後のＲ_ｉ（θ_βｋ）≦１であるという条件（２）と、を満たす全ての列を加算して、列θ_βｋを生成する。

２番目のステップで、選択された列に対応するデータパケットに対して、ビットのモジュロ２加算を基本演算とする組み合わせ符号化を行って、符号化パケットＰ_ｋを得、加算後の列を第１のサブ行列ω^βに入れる。

３番目のステップで、併合できない列を第２のサブ行列ω^γに入れる。

説明すべきものとして、分割によって得られた符号化パケットＰ_ｋは、完全に復号化できるものである。その理由として、該符号化パケットＰ_ｋには、多くともあるユーザの１つのロスパケットが含まれ、ユーザは、若干回の排他的論理和演算により、ロスパケットを得ることができる。

例えば、上記の表２に示すゼロ除去パケットロスパターン行列ω^αを分割する場合、ω^αの１列目を例として、ω^αからＰ_１とＰ_２とを選択して加算し、θ_β１を生成する。同様に、ω^αからＰ_３とＰ_４とを選択して加算し、θ_β２を生成し、および、ω^αからＰ_６とＰ_８とを選択して加算し、θ_β３を生成することができる。これにより、第１のサブ行列ω^βを得る。ω^αのＰ_７、Ｐ_９、Ｐ_１０は、加算条件を満たさず併合できないデータパケットである。そのため、Ｐ_７、Ｐ_９、Ｐ_１０に対応する列は、第２のサブ行列ω^γに入れられる。下記の表３と表４は、表２に示すゼロ除去パケットロスパターン行列ω^αを分割して得られた第１のサブ行列ω^βと第２のサブ行列ω^γとをそれぞれ示す。

拡張という第３の過程は、即ち、分割後の第１のサブ行列ω^βと第２のサブ行列ω^γとの列をさらに併合して、第２のパケットロスパターン行列ω^βγおよび第３のサブ行列ω^μを得ることである。ここで、併合後の列の要素のうち、多くとも１つのみが２に等しい。この拡張過程は、具体的に、下記のステップを含む。

１番目のステップで、第２のサブ行列ω^γの全ての列を、第１のサブ行列ω^βの末尾に追加して、第２のパケットロスパターン行列ω^βγと呼ばれる新しいパケットロスパターン行列を構成する。

２番目のステップで、元の第２のサブ行列ω^γの各列θ_γｌ（１≦ｌ≦Ｌ）に対して、第２のパケットロスパターン行列ω^βγから、θ_γｌとθ_βγＳとを併合してθ_βγＳ ^＋を得る場合、∀ｉ、Ｒ_ｉ＊（θ_βγＳ ^＋）＝２となるユーザｉ^＊は１つしかないという条件を満たす列θ_βγＳ（１≦ｓ≦Ｌ＋Ｋ，ｓ≠ｌ）を選択する。

３番目のステップで、Ｍ次元のゼロ列ベクトルｅを生成して、ｅ（ｉ^＊）＝１かつ列ベクトルｅとθ_γｌとに対応するデータパケットが同じであるようにし、そして、列ベクトルｅを第３のサブ行列ω^μに入れ、最後に、θ_γｌに対応するデータパケットを、θ_βγＳに対応する符号化パケットＰ_sに組み入れる。

拡張完了して得られた第２のパケットロスパターン行列ω^βγの列は、θ_βγｈ（１≦ｈ≦Ｈ）である。端末にとって、この段階の符号化パケットには、自局に必要な２つのロスパケットが含まれる可能性がある。そのため、端末はロスパケットを回復できない。

上記の表３と表４に示す第１のサブ行列ω^βと第２のサブ行列ω^γとを拡張する過程では、Ｐ_９のみが拡張条件を満たして第１の符号化パケットに組み入れられる。下記の表５と表６は、表３と表４に示す第１のサブ行列ω^βと第２のサブ行列ω^γとを拡張して得られた第２のパケットロスパターン行列ω^βγと第３のサブ行列ω^μとをそれぞれ示す。

合併という第４の過程は、即ち、第３のサブ行列ω^μの列を第２のパケットロスパターン行列ω^βγに併合して、第３のパケットロスパターン行列を得ることである。ここで、併合された列の全ての要素は、いずれも１以下である。合併は、拡張に起因する端末がロスパケットを回復できないという問題を解決することを目的とする。

上記の合併過程は、具体的に、下記のステップを含む。

１番目のステップで、ω^μの列ベクトルｅに対して、ｅ（ｉ^＊）＝１であり、ω^βγの列θ_βγｈを順に判断し、Ｒ_ｉ＊（ｅ∪θ_βγｈ）＝１を満たす場合、ｅの目標列がθ_βγｈであると判断し、そして、ｅを目標列に加算する。

２番目のステップで、ｅに対応するデータパケットを、目標列θ_βγｈに対応する符号化パケットＰ_ｈ（１≦ｈ≦Ｈ）に組み入れて、第３のサブ行列ω^μから、列ベクトルｅを除去する。

３番目のステップで、第３のサブ行列ω^μにおける等しくない列ベクトルをグループ構成して加算し、得られた列を第３のパケットロスパターン行列に入れ、そして、各グループごとに、該グループ内の各列ベクトルに対応するデータパケットに対して、組み合わせ符号化を行って、符号化パケットを得る。

表５と表６に示す第２のパケットロスパターン行列ω^βγおよび第３のサブ行列ω^μに対して合併処理を行う際に、拡張されたＰ_９に対応する列ベクトルｅの目標列がθ_β２であるので、ｅをθ_β２に併合するとともに、Ｐ_９をθ_β２に対応する符号化パケットに組み入れる。下記の表７は、表５と表６に示す第２のパケットロスパターン行列ω^βγと第３のサブ行列ω^μとを合併して得られた第３のパケットロスパターン行列を示す。

上記の第３のパケットロスパターン行列は、再送対象データパケットの組み合わせ方式を反映し、つまり、第３のパケットロスパターン行列の各列毎に対応する符号化パケットまたはデータパケットは、再送対象データパケットの組み合わせ方式を反映する。

上記の第３のパケットロスパターン行列を得ると、ステップ３で、ソースノードＳは、第３のパケットロスパターン行列の各列毎に対応する符号化パケットまたはデータパケットに示す組み合わせ方式に従って、再送対象データパケットに対して、ビットのモジュロ２加算を基本演算とする組み合わせ符号化を行って、再送対象の符号化パケットを得、符号化パケットを順に再送することができる。

上記の方法から分かるように、ソースノードＳは、ゼロ除去、分割、拡張および合併という４つの過程によって、再送対象データパケットの組み合わせ方式を得ることができ、データパケットの再送回数を大幅に減少できるとともに、端末によるデータパケットに対する正しい回復を保証できる。特に、ユーザ端末の数が比較的多いが、データパケットの数が比較的少ない場合、効果はさらに明らかになる。例えば、表１に示すパケットロスパターン行列Ωに対応して、上記４つの過程の処理によって、再送する必要があるデータパケットＰ_１、Ｐ_２、Ｐ_３、Ｐ_４、Ｐ_６、Ｐ_７、Ｐ_８、Ｐ_９およびＰ_１０を、

並びにデータパケットＰ_７およびＰ_１０に、改めて組み合わせることができる。このようにして、５回の再送だけで、９個の再送対象データパケットの再送を完成することができる。具体的に、端末Ｔ_３は、１番目の再送パケットを受信した時、

を回復することができ、次に、２番目の再送パケットから、Ｐ_９を回復して、もう一度排他的論理和処理を行うと、Ｐ_１を得ることができる。一方、ほかのユーザにとって、すべての符号化パケットは、完全に復号化できるものである。ここから分かるように、ゼロ除去、分割、拡張および合併という４つの過程により得られた再送対象データパケットの組み合わせ方式では、データパケットの再送回数を大幅に減少できるとともに、端末によるデータパケットに対する正しい回復を保証できる。

下記の内容は、ソースノードＳがパケットロスパターン行列Ωに対して、分割、拡張および合併を行う疑似コードである。

また、説明すべきものとして、上記のデータ再送方法では、Ｎ個のデータパケットのパケットロスパターン行列Ωを取得した後、ソースノードＳは、Ωを分析することで再送パケットの組み合わせ方法を得てから、再送を開始する必要がある。従って、パケットロスパターン行列Ωの取得から再送開始まで、ある程度の時間遅延がある。この時間遅延が△Ｔであると仮定すると、△Ｔは、ソースノードＳがパケットロスパターン行列Ωを分析して、再送対象データパケットの組み合わせ方式を得るために必要な処理時間である。システムのデータ伝送効率を影響しないために、上記のステップ２を実行するとともに、伝送する必要がある新しいデータパケットがあるかどうかを判断し、伝送する必要がある新しいデータパケットがある場合、Ｎ′＝ｆｌｏｏｒ（△Ｔ/Ｔ_Ｓ）＜Ｎ個の新しいデータパケットを続けて伝送し、ここで、Ｔ_Ｓは、ソースノードＳが１つのデータパケットを送信するにかかる時間を表し、ｆｌｏｏｒ（Ｘ）関数は、有理数Ｘより大きい最小整数を取ることを表し、それから、上記のステップ３を実行し、ステップ３の実行を完了した後、Ｎ−Ｎ′個のデータパケットを続けて伝送して、新しいＮ個のデータパケットのパケットロスパターン行列Ωを取得してから、ステップ２に戻るようにしてもよい。

上述したように、ソースノードは、Ωを処理するとともに、次のグループのデータパケットを続けて送信する。パケットロスパターン行列Ωに対する最終回の分析時にデータ送信の中断を引き起こす以外、残りの時間で、ソースノードはデータを連続的に送信することができる。これにより、システムのデータ伝送効率が保証される。

上記のデータ再送方法に対応して、本発明の実施例では、データ再送装置も提供されている。図３に示すように、該装置は、Ｎ個のデータパケットの伝送を完了したごとに、このＮ個のデータパケットのパケットロスパターン行列を取得するパケットロスパターン行列取得手段と、取得されたパケットロスパターン行列を分析して、再送対象データパケットの組み合わせ方式を得る組み合わせ方式決定手段と、再送対象データパケットの組み合わせ方式に従って、再送対象データパケットに対して組み合わせ符号化を行って、再送対象の符号化パケットを得る符号化手段と、符号化パケットを順に再送する再送手段と、を含む。

ここで、上記の組み合わせ方式決定手段は、パケットロスパターン行列から、要素が全部ゼロである列を除去して、ゼロ除去パケットロスパターン行列を得るゼロ除去モジュールと、ゼロ除去パケットロスパターン行列を２つのサブ行列に分割し、ここで、第１のサブ行列の各列毎に対応する符号化パケットが、組み合わせて再送されることができる複数のデータパケットである一方、第２のサブ行列の各列毎に対応するデータパケットが、ほかのデータパケットと組み合わせて再送されることができないデータパケットである分割モジュールと、分割後の第１のサブ行列と第２のサブ行列との列をさらに併合して、第２のパケットロスパターン行列と第３のサブ行列とを得、ここで、併合後の列の要素のうち、多くとも１つのみが２に等しい拡張モジュールと、第３のサブ行列の列を第２のパケットロスパターン行列に併合して、再送対象データパケットの組み合わせ方式を反映する第３のパケットロスパターン行列を得、ここで、併合後の列の全ての要素が、いずれも１以下である合併モジュールと、を含む。

具体的に、上記のゼロ除去モジュール、分割モジュール、拡張モジュールおよび合併モジュールは、上記のゼロ除去、分割、拡張および合併という過程をそれぞれ実行して、パケットロスパターン行列Ωに対する分析と処理とを完成する。

同様に、本実施例において、データ再送装置は、ゼロ除去モジュール、分割モジュール、拡張モジュールおよび合併モジュールの処理によって、再送対象データパケットを効果的に組み合わせることができ、データパケットの再送回数を大幅に減少できるとともに、端末によるデータパケットに対する正しい回復も保証できる。

説明すべきものとして、本発明の実施例で提供されたデータ再送方法およびその装置は、パケットロスパターン行列Ωに基づいたものである。従って、無線マルチキャストネットワークでは、全部フィードバックまたは一部フィードバックの方式を採用して、端末から自局のパケットロス情報をソースノードＳへフィードバックすることが要求される。そのため、フィードバックなしの無線マルチキャストネットワークのデータ再送に適用されない。

上記のように、上記のステップ１では、ソースノードＳは、Ｎ個のデータパケットの伝送を完了した後、一部の端末からフィードバックされたＡＣＫ／ＮＡＫに基づいて、パケットロスパターン行列Ωを取得することができる。すると、一部フィードバックの場合、ＡＣＫ／ＮＡＫをフィードバックする端末の数を如何に決定するかが、一部フィードバックの場合に解決すべき問題の１つである。大量のシミュレーションにより、下記の結論を得ることができる。即ち、実際にデータパケットを受信する端末の数にかかわらず、ＡＣＫ／ＮＡＫをフィードバックする端末の数を１０個または約１０個に設定すれば、よりよい復号化成功確率を得ることができる。この場合、単にＡＣＫ／ＮＡＫをフィードバックする端末の数を増加すると、復号化成功確率を大幅に増加させることなく、逆に、復号化および再送過程の計算複雑度およびオーバヘッドを大幅に増加させることになる。

また、ＡＣＫ／ＮＡＫをフィードバックする端末をどのように選択するかも、一部フィードバックの場合に解決すべき問題の１つである。本実施例において、最も悪いチャネルでフィードバックするというルールを採用することができる。つまり、チャネル条件が最も悪いそれらのノードに、自局のデータパケットの受信状況をフィードバックさせる。実際の応用では、まず、データパケットを受信する端末に対し、基準信号をソースノードへ送信するよう要求することができる。次に、ソースノードは、各端末から送信された基準信号に基づいて、各端末の中から、信号品質が最も悪いＭ個の端末を、ＡＣＫ／ＮＡＫをフィードバックする端末として選択し、下り制御シグナリングを介して、このＭ個の端末に対し、ＡＣＫ／ＮＡＫをフィードバックする必要がある旨を通知する。このようにして、ソースノードは、このＭ個の端末からフィードバックされたＡＣＫ／ＮＡＫを受信すると、パケットロスパターン行列Ωを生成することができる。

次に、大量のシミュレーションの結果により、ソースノードがデータパケットを再送する際の最大再送回数を５以下とすることが比較的に適合であると決定できる。このように、ユーザによる復号化成功確率に対する要求（例えば、９５％より大きい）を満足できるとともに、再送に必要なオーバヘッドも制御可能な範囲にある。つまり、再送回数が５回に達した後、単に再送回数を増加すると、復号化成功確率を大幅に増加させることなく、逆に、再送のオーバーヘッドを大幅に増加させることになる。

図４は、データパケットを受信する端末の数が１０００であり、本実施例のデータ伝送方法を採用するとき、全部フィードバックまたは一部フィードバック（１０個のユーザがＡＣＫ／ＮＡＫをフィードバックする）の場合での復号化成功確率と再送回数との関係をそれぞれ示す。ここで、図４の横軸は、再送回数を代表し、縦軸は、復号化成功確率を代表し、図４における実線で示す曲線は、全部フィードバックを採用する場合での復号化成功確率と再送回数との関係を代表し、図４における十字印の曲線は、一部フィードバックを採用する場合での復号化成功確率と再送回数との関係を代表する。図４から分かるように、再送回数が５回以下であるとき、一部フィードバックを採用する場合に得られた復号化成功確率は、全部フィードバックを採用する場合に得られた復号化成功確率より高い。つまり、最大再送回数が定められたという限定で、本実施例に係るアルゴリズムは、一部フィードバックを採用する場合にさらに適用される。

また、図４のシミュレーション結果から分かるように、一部フィードバックを採用する場合、チャネル条件が比較的悪い（パケットロス率が０．１である）のであれば、復号化成功確率は９９％に達することができない。映像への要求が比較的高いユーザにとって、このような映像品質は、我慢できないものである。映像品質をさらに向上させるために、本発明では、複数回の一部フィードバックという概念が提案されている。つまり、１回目のフィードバック結果に基づいて、１つの再送周期を完了した後、１０個の最も悪いユーザを再選択してフィードバックを行うことができ、それから、もう１つの再送周期を行う。図５に示すように、このような簡単な拡張を採用すれば、復号化成功確率が９９％以上に達することができる。図５は、一部フィードバック回数と復号化成功確率との関係を示す。図５から分かるように、一部フィードバック回数の増加につれて、復号化成功確率が増加される。

上記は、本発明の好ましい実施例にすぎず、本発明を限定するものではない。本発明の精神と原則内で行われる種々の修正、均等置換え、改善などは全て本発明の保護範囲内に含まれるべきである。

Claims (16)

1. データ再送方法であって、
   ソースノードは、Ｎ個（Ｎは自然数）のデータパケットの伝送を完了した後、このＮ個のデータパケットのパケットロスパターン行列を取得するステップＡと、
   ソースノードは、取得されたパケットロスパターン行列を分析して、再送対象データパケットの組み合わせ方式を得るステップＢと、
   ソースノードは、再送対象データパケットの組み合わせ方式に従って、再送対象データパケットに対して組み合わせ符号化を行って、再送対象の符号化パケットを得、符号化パケットを順に再送するステップＣと、
   を含むことを特徴とする方法。
2. このＮ個のデータパケットのパケットロスパターン行列を取得することは、
   ソースノードが、Ｎ個のデータパケットの伝送を完了した後、端末からフィードバックされたＡＣＫ／ＮＡＫに基づいて、パケットロスパターン行列を作成する、
   ことを含むことを特徴とする請求項１に記載の方法。
3. ソースノードが、Ｎ個のデータパケットの伝送を完了した後、端末からフィードバックされたＡＣＫ／ＮＡＫに基づいて、パケットロスパターン行列を作成することは、
   ソースノードが１つのデータパケットの伝送を完了したごとに、全ての端末が、ＡＣＫ／ＮＡＫを利用して、自局のパケットロス状況を同期フィードバックし、
   ソースノードが、Ｎ個のデータパケットの伝送を完了した後、全ての端末からフィードバックされたＡＣＫ／ＮＡＫに基づいて、パケットロスパターン行列を作成する、
   ことを含むことを特徴とする請求項２に記載の方法。
4. ソースノードが、Ｎ個のデータパケットの伝送を完了した後、端末からフィードバックされたＡＣＫ／ＮＡＫに基づいて、パケットロスパターン行列を作成することは、
   ソースノードが１つのデータパケットの伝送を完了したごとに、前記データパケットを受信する全ての端末のうちのＭ個の端末が、ＡＣＫ／ＮＡＫを利用して、自局のパケットロス状況を同期フィードバックし、
   ソースノードが、Ｎ個のデータパケットの伝送を完了した後、前記Ｍ個の端末からフィードバックされたＡＣＫ／ＮＡＫに基づいて、パケットロスパターン行列を作成する、
   ことを含むことを特徴とする請求項２に記載の方法。
5. ソースノードは、端末から送信された基準信号に基づいて、全ての端末の中から、信号品質が最も悪いＭ個の端末を、ＡＣＫ／ＮＡＫをフィードバックする端末として選択し、下り制御シグナリングを介して、前記Ｍ個の端末に対し、ＡＣＫ／ＮＡＫをフィードバックするよう通知する、
   ことをさらに含むことを特徴とする請求項４に記載の方法。
6. 前記Ｍの値の範囲は、１０〜１５である、
   ことを特徴とする請求項４または５に記載の方法。
7. ソースノードが、取得されたパケットロスパターン行列を分析して、再送対象データパケットの組み合わせ方式を得ることは、
   パケットロスパターン行列から、要素が全部ゼロである列を除去して、ゼロ除去パケットロスパターン行列を得、
   ゼロ除去パケットロスパターン行列を２つのサブ行列に分割し、ここで、第１のサブ行列の各列毎に対応する符号化パケットが、組み合わせて再送されることができる複数のデータパケットである一方、第２のサブ行列の各列毎に対応するデータパケットが、ほかのデータパケットと組み合わせて再送されることができないデータパケットであり、
   分割後の第１のサブ行列と第２のサブ行列との列をさらに併合して、第２のパケットロスパターン行列と第３のサブ行列とを得、ここで、併合後の第２のパケットロスパターン行列の列の要素のうち、多くとも１つのみが２に等しく、
   第３のサブ行列の列を第２のパケットロスパターン行列に併合して、再送対象データパケットの組み合わせ方式を反映する第３のパケットロスパターン行列を得、ここで、併合後の列の全ての要素が、いずれも１以下である、
   ことを含むことを特徴とする請求項１に記載の方法。
8. パケットロスパターン行列から、要素が全部ゼロである列を除去することは、
   パケットロスパターン行列Ωにおける全ての要素がゼロである列を抽出して、１つのサブ行列ω^０を構成し、残りの列でゼロ除去パケットロスパターン行列ω^αを構成する、
   ことを含むことを特徴とする請求項７に記載の方法。
9. ゼロ除去パケットロスパターン行列を２つのサブ行列に分割することは、
   ゼロ除去パケットロスパターン行列ω^αの列を順に選択し、ゼロ除去パケットロスパターン行列ω^αから選択された下記の、
   ほかの列で選択されたことがないという条件（１）と、
   ∀ｉ、併合後のＲ_ｉ（θ_βｋ）≦１であるという条件（２）と、
   を満たす全ての列を加算して、列θ_βｋを生成し、ここで、Ｒ_ｉ（θ_βｋ）は、列ベクトルθ_βｋ（１≦ｋ≦Ｋ）のｉ行目の要素の値を表し、
   選択された列に対応するデータパケットに対して、ビットのモジュロ２加算を基本演算とする組み合わせ符号化を行って、符号化パケットＰ_ｋを得、加算後の列を第１のサブ行列ω^βに入れ、
   併合できない列を第２のサブ行列ω^γに入れる、
   ことを含むことを特徴とする請求項７に記載の方法。
10. 分割後の第１のサブ行列と第２のサブ行列との列をさらに併合して、第２のパケットロスパターン行列と第３のサブ行列とを得ることは、
    第２のサブ行列ω^γの全ての列を、第１のサブ行列ω^βの末尾に追加して、第２のパケットロスパターン行列ω^βγを構成し、
    元の第２のサブ行列ω^γの各列θγ_ｌ（１≦ｌ≦Ｌ）に対して、第２のパケットロスパターン行列ω^βγから、θγ_ｌとθ_βγＳとを併合してθ_βγＳ ^＋を得る場合、∀ｉ、Ｒ_ｉ＊（θ_βγＳ ^＋）＝２となるユーザｉ^＊は１つしかないという条件を満たす列θ_βγＳ（１≦ｓ≦Ｌ＋Ｋ，ｓ≠ｌ）を選択し、ここで、Ｒ_ｉ＊（θ_βγＳ ^＋）は、列ベクトルθ_βγＳ ^＋のｉ^＊行目の要素の値を表し、
    Ｍ次元のゼロ列ベクトルｅを生成して、ｅ（ｉ^＊）＝１かつ列ベクトルｅとθγ_ｌとに対応するデータパケットが同じであるようにし、そして、列ベクトルｅを第３のサブ行列ω^μに入れ、最後に、θγ_ｌに対応するデータパケットを、θ_βγＳに対応する符号化パケットＰｓに組み入れる、
    ことを含むことを特徴とする請求項７に記載の方法。
11. 第３のサブ行列の列を第２のパケットロスパターン行列に併合することは、
    第３のサブ行列ω^μの列ベクトルｅに対して、ｅ（ｉ^＊）＝１であり、ω^βγの列θ_βγｈ（１≦ｈ≦Ｈ）を順に判断し、Ｒ_ｉ＊（ｅ∪θ_βγｈ）＝１を満たす場合、ｅの目標列がθ_βγｈであると判断し、そして、ｅを目標列に加算し、ここで、Ｒ_ｉ＊（ｅ∪θ_βγｈ）＝１であり、列ベクトルｅと列ベクトルθ_βγＳとのｉ^＊行目の要素の値の和を表し、
    列ベクトルｅに対応するデータパケットを、目標列θ_βγｈに対応する符号化パケットＰ_ｈ（１≦ｈ≦Ｈ）に組み入れて、第３のサブ行列ω^μから、列ベクトルｅを除去し、
    第３のサブ行列ω^μにおける等しくない列ベクトルをグループ構成して加算し、得られた列を第３のパケットロスパターン行列に入れ、そして、各グループごとに、該グループ内の各列ベクトルに対応するデータパケットに対して、組み合わせ符号化を行って、符号化パケットを得る、
    ことを含むことを特徴とする請求項７に記載の方法。
12. ソースノードが、再送対象データパケットの組み合わせ方式に従って、再送対象データパケットに対して組み合わせ符号化を行って、再送対象の符号化パケットを得ることは、
    ソースノードが、第３のパケットロスパターン行列の各列毎に対応する符号化パケットまたはデータパケットに示す組み合わせ方式に従って、再送対象データパケットに対して、ビットのモジュロ２加算を基本演算とする組み合わせ符号化を行って、再送対象の符号化パケットを得る、
    ことを含むことを特徴とする請求項７に記載の方法。
13. ステップＢを実行するとともに、伝送する必要があるデータパケットがあるかどうかを判断し、伝送する必要があるデータパケットがある場合、Ｎ′＝ｆｌｏｏｒ（△Ｔ／Ｔ_Ｓ）＜Ｎ個の新しいデータパケットを続けて伝送し、ここで、△Ｔは、ソースノードがパケットロスパターン行列を分析して、再送対象データパケットの組み合わせ方式を得るために必要な処理時間であり、Ｔ_Ｓは、ソースノードＳが１つのデータパケットを送信するにかかる時間を表し、ｆｌｏｏｒ（Ｘ）関数は、有理数Ｘより大きい最小整数を取ることを表し、
    ステップＣを実行した後、Ｎ−Ｎ′個のデータパケットを続けて伝送して、新に伝送されたＮ個のデータパケットのパケットロスパターン行列を得てから、ステップＢに戻る、
    ことをさらに含むことを特徴とする請求項１に記載の方法。
14. ソースノードが符号化パケットを再送するための最大再送回数は５回以下である、
    ことをさらに含むことを特徴とする請求項１に記載の方法。
15. データ再送装置であって、
    Ｎ個（Ｎは自然数）のデータパケットの伝送を完了したごとに、このＮ個のデータパケットのパケットロスパターン行列を取得するパケットロスパターン行列取得手段と、
    取得されたパケットロスパターン行列を分析して、再送対象データパケットの組み合わせ方式を得る組み合わせ方式決定手段と、
    再送対象データパケットの組み合わせ方式に従って、再送対象データパケットに対して組み合わせ符号化を行って、再送対象の符号化パケットを得る符号化手段と、
    符号化パケットを順に再送する再送手段と、
    を含むことを特徴とする装置。
16. 前記組み合わせ方式決定手段は、
    パケットロスパターン行列から、要素が全部ゼロである列を除去して、ゼロ除去パケットロスパターン行列を得るゼロ除去モジュールと、
    ゼロ除去パケットロスパターン行列を２つのサブ行列に分割し、ここで、第１のサブ行列の各列毎に対応する符号化パケットが、組み合わせて再送されることができる複数のデータパケットである一方、第２のサブ行列の各列毎に対応するデータパケットが、ほかのデータパケットと組み合わせて再送されることができないデータパケットである分割モジュールと、
    分割後の第１のサブ行列と第２のサブ行列との列をさらに併合して、第２のパケットロスパターン行列と第３のサブ行列とを得、ここで、併合後の第２のパケットロスパターン行列の列の要素のうち、多くとも１つのみが２に等しい拡張モジュールと、
    第３のサブ行列の列を第２のパケットロスパターン行列に併合して、再送対象データパケットの組み合わせ方式を反映する第３のパケットロスパターン行列を得、ここで、併合後の列の全ての要素が、いずれも１以下である合併モジュールと、
    を含むことを特徴とする請求項１５に記載の装置。

Images