(57)【要約】  パケットを中継するための方法、装置、およびコンピュータプログラム製品が提供される。本装置は、少なくとも１つのパケットを受信し、少なくとも１つのパケットの次数を低減する。本装置は、さらに、低減された次数に基づいて少なくとも１つのパケットを処理し、低減された次数と処理済みパケットの各々の重みとに基づいて、少なくとも１つの処理済みパケットを少なくとも１つの他の処理済みパケットと結合することによって結合パケットを生成し、結合パケットを送信する。【選択図】  図４
2016521949.tif 000002
【特許請求の範囲】
【請求項１】
パケットを中継する方法であって、
少なくとも１つのパケットを受信することと、
前記少なくとも１つのパケットの次数を低減することと、
前記低減された次数に基づいて前記少なくとも１つのパケットを処理することと、
結合パケットを生成することと、前記生成することが、前記低減された次数と前記処理済みパケットの各々の重みとに基づいて、前記少なくとも１つの処理済みパケットを少なくとも１つの他の処理済みパケットと結合することを備える、
前記結合パケットを送信することと
を備える、方法。
【請求項２】
前記受信された少なくとも１つのパケットが、ファウンテンコードを使用して符号化される、請求項１に記載の方法。
【請求項３】
前記少なくとも１つのパケットの前記次数が、前記少なくとも１つのパケットを作成するために使用されたネイティブパケットの数を備える、請求項１に記載の方法。
【請求項４】
前記低減することが、
ネイティブパケットの復号セットに属する前記少なくとも１つのパケットのすべてのネイティブパケットを削除することと、
同じ同値類に属する前記少なくとも１つのパケットの２つのネイティブパケットの任意の組合せを削除することと
を備える、請求項１に記載の方法。
【請求項５】
同値類がネイティブパケットのセットを備え、ここにおいて、前記同値類中の任意の２つのネイティブパケットの排他的論理和演算が、次数２処理済みパケットに対して排他的論理和演算を実行することによって生成され得る、請求項４に記載の方法。
【請求項６】
前記処理することが、
前記少なくとも１つのパケットの前記低減された次数を決定すること
を備え、
前記少なくとも１つのパケットの前記低減された次数が１に等しいとき、前記処理することが、
前記少なくとも１つの次数低減パケットで前記復号セットを更新することと、
信念伝搬に基づいて前記復号セットを更新することと、
前記少なくとも１つの次数低減パケットに基づいて同値類を更新することと
をさらに備え、
前記少なくとも１つのパケットの前記低減された次数が２に等しいとき、前記処理することが、前記少なくとも１つの次数低減パケットに基づいて前記同値類を更新することをさらに備える、
請求項４に記載の方法。
【請求項７】
前記結合パケットを前記生成することが、
前記結合パケットのためのターゲット次数を決定することと、
前記少なくとも１つのパケットの各パケットに割り当てられた重みに基づいて、前記ターゲット次数よりも小さいかまたはそれに等しい次数を有する少なくとも１つの次数低減パケットを選択することと、
前記結合パケットを生成するために前記少なくとも１つの選択された次数低減パケットの各々を結合することと
をさらに備える、請求項６に記載の方法。
【請求項８】
前記少なくとも１つの次数低減パケットは、選択されたパケットのそれぞれの次数の和が前記ターゲット次数に等しくなるまで、または最大回数の選択が行われるまで選択される、請求項７に記載の方法。
【請求項９】
前記結合パケット中のネイティブパケットをネイティブパケットの前記復号セットからの別のネイティブパケットと交換することと、
前記結合パケット中の任意のネイティブパケットを、同じ同値類に属する別のネイティブパケットと交換することと
を備える、前記結合パケットを多様化させること
をさらに備える、請求項７に記載の方法。
【請求項１０】
パケットを中継するための装置であって、
少なくとも１つのパケットを受信するための手段と、
前記少なくとも１つのパケットの次数を低減するための手段と、
前記低減された次数に基づいて前記少なくとも１つのパケットを処理するための手段と、
結合パケットを生成するための手段と、生成するための前記手段が、前記低減された次数と前記処理済みパケットの各々の重みとに基づいて、前記少なくとも１つの処理済みパケットを少なくとも１つの他の処理済みパケットと結合するように構成された、
前記結合パケットを送信するための手段と
を備える、装置。
【請求項１１】
前記受信された少なくとも１つのパケットが、ファウンテンコードを使用して符号化される、請求項１０に記載の装置。
【請求項１２】
前記少なくとも１つのパケットの前記次数が、前記少なくとも１つのパケットを作成するために使用されたネイティブパケットの数を備える、請求項１０に記載の装置。
【請求項１３】
低減するための前記手段が、
ネイティブパケットの復号セットに属する前記少なくとも１つのパケットのすべてのネイティブパケットを削除することと、
同じ同値類に属する前記少なくとも１つのパケットの２つのネイティブパケットの任意の組合せを削除することと
を行うように構成された、請求項１０に記載の装置。
【請求項１４】
同値類がネイティブパケットのセットを備え、ここにおいて、前記同値類中の任意の２つのネイティブパケットの排他的論理和演算が、次数２処理済みパケットに対して排他的論理和演算を実行することによって生成され得る、請求項１３に記載の装置。
【請求項１５】
処理するための前記手段が、
前記少なくとも１つのパケットの前記低減された次数を決定すること
を行うように構成され、
前記少なくとも１つのパケットの前記低減された次数が１に等しいとき、処理するための前記手段が、
前記少なくとも１つの次数低減パケットで前記復号セットを更新することと、
信念伝搬に基づいて前記復号セットを更新することと、
前記少なくとも１つの次数低減パケットに基づいて同値類を更新することと
を行うようにさらに構成され、
前記少なくとも１つのパケットの前記低減された次数が２に等しいとき、処理するための前記手段が、前記少なくとも１つの次数低減パケットに基づいて前記同値類を更新することを行うようにさらに構成された、
請求項１３に記載の装置。
【請求項１６】
前記結合パケットを生成するための前記手段が、
前記結合パケットのためのターゲット次数を決定することと、
前記少なくとも１つのパケットの各パケットに割り当てられた重みに基づいて、前記ターゲット次数よりも小さいかまたはそれに等しい次数を有する少なくとも１つの次数低減パケットを選択することと、
前記結合パケットを生成するために前記少なくとも１つの選択された次数低減パケットの各々を結合することと
を行うようにさらに構成された、請求項１５に記載の装置。
【請求項１７】
前記少なくとも１つの次数低減パケットは、選択されたパケットのそれぞれの次数の和が前記ターゲット次数に等しくなるまで、または最大回数の選択が行われるまで選択される、請求項１６に記載の装置。
【請求項１８】
前記結合パケット中のネイティブパケットをネイティブパケットの前記復号セットからの別のネイティブパケットと交換することと、
前記結合パケット中の任意のネイティブパケットを、同じ同値類に属する別のネイティブパケットと交換することと
を行うように構成された、前記結合パケットを多様化させるための手段
をさらに備える、請求項１６に記載の装置。
【請求項１９】
パケットを中継するための装置であって、
メモリと、
前記メモリに結合された少なくとも１つのプロセッサと
を備え、前記少なくとも１つのプロセッサが、
少なくとも１つのパケットを受信することと、
前記少なくとも１つのパケットの次数を低減することと、
前記低減された次数に基づいて前記少なくとも１つのパケットを処理することと、
結合パケットを生成することと、ここにおいて、生成するように構成された前記少なくとも１つのプロセッサが、前記低減された次数と前記処理済みパケットの各々の重みとに基づいて、前記少なくとも１つの処理済みパケットを少なくとも１つの他の処理済みパケットと結合するようにさらに構成された、
前記結合パケットを送信することと
を行うように構成された、装置。
【請求項２０】
前記受信された少なくとも１つのパケットが、ファウンテンコードを使用して符号化される、請求項１９に記載の装置。
【請求項２１】
前記少なくとも１つのパケットの前記次数が、前記少なくとも１つのパケットを作成するために使用されたネイティブパケットの数を備える、請求項１９に記載の装置。
【請求項２２】
低減するように構成された前記少なくとも１つのプロセッサが、
ネイティブパケットの復号セットに属する前記少なくとも１つのパケットのすべてのネイティブパケットを削除することと、
同じ同値類に属する前記少なくとも１つのパケットの２つのネイティブパケットの任意の組合せを削除することと
を行うようにさらに構成された、請求項１９に記載の装置。
【請求項２３】
同値類がネイティブパケットのセットを備え、ここにおいて、前記同値類中の任意の２つのネイティブパケットの排他的論理和演算が、次数２処理済みパケットに対して排他的論理和演算を実行することによって生成され得る、請求項２２に記載の装置。
【請求項２４】
処理するように構成された前記少なくとも１つのプロセッサが、
前記少なくとも１つのパケットの前記低減された次数を決定すること
を行うようにさらに構成され、
前記少なくとも１つのパケットの前記低減された次数が１に等しいとき、処理するように構成された前記少なくとも１つのプロセッサが、
前記少なくとも１つの次数低減パケットで前記復号セットを更新することと、
信念伝搬に基づいて前記復号セットを更新することと、
前記少なくとも１つの次数低減パケットに基づいて同値類を更新することと
を行うようにさらに構成され、
前記少なくとも１つのパケットの前記低減された次数が２に等しいとき、処理するように構成された前記少なくとも１つのプロセッサが、前記少なくとも１つの次数低減パケットに基づいて前記同値類を更新することを行うようにさらに構成された、
請求項２２に記載の装置。
【請求項２５】
前記結合パケットを生成するように構成された前記少なくとも１つのプロセッサが、
前記結合パケットのためのターゲット次数を決定することと、
前記少なくとも１つのパケットの各パケットに割り当てられた重みに基づいて、前記ターゲット次数よりも小さいかまたはそれに等しい次数を有する少なくとも１つの次数低減パケットを選択することと、
前記結合パケットを生成するために前記少なくとも１つの選択された次数低減パケットの各々を結合することと
を行うようにさらに構成された、請求項２４に記載の装置。
【請求項２６】
前記少なくとも１つの次数低減パケットは、選択されたパケットのそれぞれの次数の和が前記ターゲット次数に等しくなるまで、または最大回数の選択が行われるまで選択される、請求項２５に記載の装置。
【請求項２７】
前記少なくとも１つのプロセッサが、
前記結合パケットを多様化させること
を行うようにさらに構成され、ここにおいて、多様化させるように構成された前記少なくとも１つのプロセッサが、
前記結合パケット中のネイティブパケットをネイティブパケットの前記復号セットからの別のネイティブパケットと交換することと、
前記結合パケット中の任意のネイティブパケットを、同じ同値類に属する別のネイティブパケットと交換することと
を行うようにさらに構成された、請求項２５に記載の装置。
【請求項２８】
コンピュータ可読媒体に記憶されたコンピュータプログラム製品であって、少なくとも１つのプロセッサ上で実行されたとき、
少なくとも１つのパケットを受信するステップと、
前記少なくとも１つのパケットの次数を低減するステップと、
前記低減された次数に基づいて前記少なくとも１つのパケットを処理するステップと、
結合パケットを生成するステップと、前記生成するステップが、前記低減された次数と前記処理済みパケットの各々の重みとに基づいて、前記少なくとも１つの処理済みパケットを少なくとも１つの他の処理済みパケットと結合することを備える、
前記結合パケットを送信するステップと
を実行するコードを備える、コンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
[0001]本出願は、その全体が参照により本明細書に明確に組み込まれる、２０１３年６月１２日に出願された「DEGREE REDUCTION AND DEGREE-CONSTRAINED COMBINING FOR RELAYING A FOUNTAIN CODE」と題する米国仮出願第６１／８３４，１２２号、および２０１４年５月３０日に出願された「DEGREE REDUCTION AND DEGREE-CONSTRAINED COMBINING FOR RELAYING A FOUNTAIN CODE」と題する米国非仮出願第１４／２９２，３５９号の利益を主張する。
【０００２】
[0002]本開示は、一般に通信システムに関し、より詳細には、次数低減（degree reduction）と次数条件付き結合（degree-constrained combining）とを使用してファウンテンコード（fountain code）を中継するための方法および装置に関する。
【背景技術】
【０００３】
[0003]専用短距離通信（ＤＳＲＣ：dedicated short-range communication）は、通信ベースのアクティブ安全アプリケーションにおいて重要な極めて速いデータ送信を可能にする２方向短中距離ワイヤレス通信能力である。たとえば、ＤＳＲＣは、車両環境内ワイヤレスアクセス（ＷＡＶＥ：wireless access in vehicular environment）を追加し、インテリジェントトランスポートシステム（ＩＴＳ：Intelligent Transportation Systems）アプリケーションをサポートし得る、ＩＥＥＥ８０２．１１ｐ規格を使用して実装され得る。
【０００４】
[0004]ＤＳＲＣは、メッセージを送信および受信するために車両によって使用され得るメッセージフォーマット（たとえば、基本安全メッセージ（ＢＳＭ：basic safety message）フォーマット）を含む。たとえば、車両は、それの位置、速度および他の属性を他の車両に定期的に告知するためにＢＳＭを送信し得る。他の車両は、次いで、ＢＳＭを受信し、送信車両の位置を追跡し得、したがって、衝突を回避し、交通流を改善し得る。
【０００５】
[0005]ＤＳＲＣはまた、車両が、路側警報メッセージを通して緊急情報を受信するために路側ユニット（ＲＳＵ：roadside unit）と通信することを可能にし得る。車両は、危険な道路状態または警察活動など、公共安全情報を検出するために、ＲＳＵからの路側警報メッセージに主に依拠し得る。
【発明の概要】
【０００６】
[0006]本開示の一態様では、方法、コンピュータプログラム製品、および装置が提供される。本装置は、少なくとも１つのパケットを受信し、少なくとも１つのパケットの次数を低減する。本装置は、さらに、低減された次数に基づいて少なくとも１つのパケットを処理し、低減された次数と処理済みパケットの各々の重みとに基づいて、少なくとも１つの処理済みパケットを少なくとも１つの他の処理済みパケットと結合することによって結合パケットを生成する。その後、本装置は結合パケットを送信／ブロードキャストする。
【図面の簡単な説明】
【０００７】
【図１】[0007]通信システムを示す図。
【図２】[0008]通信システムの例示的な実装形態の図。
【図３】[0009]ファウンテンコードを中継するためのネットワークを示す図。
【図４】[0010]パケットを中継する方法のフローチャート。
【図５】[0011]例示的な装置における異なるモジュール／手段／構成要素間のデータフローを示す概念データフロー図。
【図６】[0012]処理システムを採用する装置のためのハードウェア実装形態の一例を示す図。
【発明を実施するための形態】
【０００８】
[0013]添付の図面に関して以下に示す発明を実施するための形態は、様々な構成を説明するものであり、本明細書で説明する概念が実施され得る唯一の構成を表すものではない。発明を実施するための形態は、様々な概念の完全な理解を与えるための具体的な詳細を含む。ただし、これらの概念はこれらの具体的な詳細なしに実施され得ることが当業者には明らかであろう。いくつかの例では、そのような概念を不明瞭にしないように、よく知られている構造および構成要素をブロック図の形式で示す。
【０００９】
[0014]次に、様々な装置および方法に関して通信システムのいくつかの態様を提示する。これらの装置および方法を、以下の発明を実施するための形態において説明し、（「要素」と総称される）様々なブロック、モジュール、構成要素、回路、ステップ、プロセス、アルゴリズムなどによって添付の図面に示す。これらの要素は、電子ハードウェア、コンピュータソフトウェア、またはそれらの任意の組合せを使用して実装され得る。そのような要素がハードウェアとして実装されるか、ソフトウェアとして実装されるかは、特定の適用例および全体的なシステムに課される設計制約に依存する。
【００１０】
[0015]例として、要素、または要素の任意の部分、または要素の任意の組合せは、１つまたは複数のプロセッサを含む「処理システム」を用いて実装され得る。プロセッサの例としては、マイクロプロセッサ、マイクロコントローラ、デジタル信号プロセッサ（ＤＳＰ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、プログラマブル論理デバイス（ＰＬＤ）、状態機械、ゲート論理、個別ハードウェア回路、および本開示全体にわたって説明する様々な機能を実行するように構成された他の好適なハードウェアがある。処理システム中の１つまたは複数のプロセッサはソフトウェアを実行し得る。ソフトウェアは、ソフトウェア、ファームウェア、ミドルウェア、マイクロコード、ハードウェア記述言語などの名称にかかわらず、命令、命令セット、コード、コードセグメント、プログラムコード、プログラム、サブプログラム、ソフトウェアモジュール、アプリケーション、ソフトウェアアプリケーション、ソフトウェアパッケージ、ルーチン、サブルーチン、オブジェクト、実行ファイル、実行スレッド、プロシージャ、関数などを意味すると広く解釈されたい。
【００１１】
[0016]したがって、１つまたは複数の例示的な実施形態では、説明する機能は、ハードウェア、ソフトウェア、ファームウェア、またはそれらの任意の組合せで実装され得る。ソフトウェアで実装される場合、機能は、コンピュータ可読媒体上に記憶されるか、あるいはコンピュータ可読媒体上に１つまたは複数の命令またはコードとして符号化され得る。コンピュータ可読媒体はコンピュータ記憶媒体を含む。記憶媒体は、コンピュータによってアクセスされ得る任意の利用可能な媒体であり得る。限定ではなく例として、そのようなコンピュータ可読媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ（登録商標）、ＣＤ−ＲＯＭまたは他の光ディスクストレージ、磁気ディスクストレージまたは他の磁気ストレージデバイス、あるいは命令またはデータ構造の形態の所望のプログラムコードを搬送または記憶するために使用され得、コンピュータによってアクセスされ得る、任意の他の媒体を備えることができる。本明細書で使用するディスク（disk）およびディスク（disc）は、コンパクトディスク（disc）（ＣＤ）、レーザーディスク（登録商標）（disc）、光ディスク（disc）、デジタル多用途ディスク（disc）（ＤＶＤ）、およびフロッピー（登録商標）ディスク（disk）を含み、ディスク（disk）は、通常、データを磁気的に再生し、ディスク（disc）は、データをレーザーで光学的に再生する。上記の組合せもコンピュータ可読媒体の範囲内に含まれるべきである。
【００１２】
[0017]車両が、緊急情報（たとえば、公共安全情報）を受信するためにＲＳＵと通信することができない状況において、車両は、他の近くの車両から送信されたＢＳＭから緊急情報を受信する必要があり得る。本明細書で説明する態様によれば、たとえば、警察車両は、近くの警察追跡に関係する情報を他の近くの車両に広めるために交通中の運転者車両を中継器として使用するように構成され得る。別の例として、救急車は、譲歩情報を他の近くの車両に広めるために運転者車両を中継器として使用し得る。別の例として、車両は、他の車両から中継された道路建設および迂回路情報を受信し得る。
【００１３】
[0018]図１は、通信システム１００を示す図である。図１に示されているように、通信システム１００は、デバイス１  １０２と、デバイス２  １０４と、デバイス３  １０６とを含む。一態様では、デバイス１  １０２、デバイス２  １０４、およびデバイス３  １０６は、それぞれ、ＤＳＲＣプロトコルに基づいてメッセージを送信および受信するように構成されたワイヤレス通信デバイスであり得る。そのような態様では、デバイス１  １０２、デバイス２  １０４、およびデバイス３  １０６は異なる車両中にそれぞれインストールされ得る。
【００１４】
[0019]図１に示されているように、デバイス１  １０２は、メッセージまたは（図１では「ＢＳＭ＿Ａ」と呼ばれる）ＢＳＭ１０８をデバイス２  １０４に送り得る。デバイス２  １０４は、ＢＳＭ１０８を受信し、ＢＳＭ１０８に関連する制御情報を決定し得る。たとえば、制御情報は、公共安全情報、交通遅延情報、迂回路情報、所望の送信方向、宛先、および／または気象情報を含み得る。図１にさらに示されているように、デバイス２  １０４は、次いで、決定された制御情報に基づいてＢＳＭ１０８をデバイス３  １０６に送信し得る。たとえば、制御情報が、現在の気象条件が大雪を含むことを示す場合、デバイス２  １０４は、そのような気象条件においてＢＳＭ１０８をデバイス３  １０６に正常に配信するために、増加した送信電力でＢＳＭ１０８をデバイス３  １０６に送信し得る。別の例として、制御情報が、近くの学校など、特定の宛先にＢＳＭ１０８が送信されるべきであることを示す場合、デバイス２  １０４は、そのような宛先に位置するワイヤレス通信デバイス（たとえば、デバイス３  １０６）にＢＳＭ１０８を送信し得る。したがって、デバイス２  １０４は、制御情報に基づいて、デバイス１  １０２から受信されたＢＳＭ１０８をデバイス３  １０６に中継し得る。
【００１５】
[0020]一態様では、デバイス２  １０４は、１つまたは複数のデバイス（たとえば、デバイス３  １０６）の相対ロケーションを決定し得る。たとえば、デバイス２  １０４は、あるデバイスからＢＳＭ中で受信された位置情報を使用して、そのデバイスの相対ロケーションを決定し得る。デバイス２  １０４は、次いで、１つまたは複数のデバイスの相対ロケーションに基づいて、そのデバイスにＢＳＭ１０８を送信し得る。たとえば、相対ロケーションは、ＧＰＳ座標として、あるいは、北または南西など、デバイス２  １０４に関する方向として表され得る。さらなる態様では、デバイス２  １０４は、デバイス３  １０６、およびＢＳＭ１０８を受信することが可能な他のデバイスにＢＳＭ１０８をブロードキャストすることによってＢＳＭ１０８を中継し得る。
【００１６】
[0021]一態様では、デバイス１  １０２は、そのような権限を付与されていないデバイスによって生成されたＢＳＭよりも高い優先度を有する（「制御型ＢＳＭ」、「拡張ＢＳＭ」、または「高優先度ＢＳＭ」とも呼ばれる）ＢＳＭを生成する権限を付与され得る。たとえば、高優先度ＢＳＭを生成する権限は、警察署など、政府機関に付与され得る。高優先度ＢＳＭを受信し、認証するワイヤレス通信デバイスはローカル権限を付与されると言われ得る。
【００１７】
[0022]図２は、通信システム１００の例示的な実装形態の図である。図２を参照すると、ＢＳＭ送信が示されている。図２は第１の車両２０２を含む。第２の車両２０４、第３の車両２０６、および第４の車両２０８は街路２１０上で第１の車両２０２の前方を進む。たとえば、デバイス１  １０２は第１の車両２０２中にインストールされ得、デバイス２  １０４は第２の車両２０４中にインストールされ得、デバイス３  １０６は第３の車両２０６中にインストールされ得る。この例では、第１の車両２０２は第４の車両２０８の高速追跡に関与し得る。一態様では、第２の車両２０４は、第１の車両２０２から受信されたＢＳＭ１０８を第３の車両２０６に特に中継し得る。さらなる態様では、第２の車両２０４は、第４の車両２０８が第３の車両２０６と同様にＢＳＭ１０８を受信し得るように、ＢＳＭ１０８をブロードキャストし得る。
【００１８】
[0023]車両間（Ｖ２Ｖ：vehicle-to-vehicle）通信の展開は安全のために主に推進される。しかしながら、セルラーインフラストラクチャおよびＲＳＵは、車両、住宅、および／または固定配信ロケーションに宛てられたコンテンツを配信するためにＶ２Ｖ通信を利用し得る。ＤＳＲＣは、オフィスオンホイール（office-on-wheel）からピアツーピア（Ｐ２Ｐ）ファイル共有およびナビゲーションソフトウェアアップデートに及ぶ、安全以外のサービスのために割り振られたいくつかのチャネルを有し得る。したがって、ＤＳＲＣを装備した車両ネットワークにおけるコンテンツ配信は、ＤＳＲＣスペクトルを利用するという利点を有する。他の利点は高モビリティのサポートと潜在的ユビキタス展開とを含む。すべての車両への認証局によって作成された証明書失効リスト（ＣＲＬ：Certificate Revocation List）の配信も行われ得る。
【００１９】
[0024]ＤＳＲＣを利用するＶ２Ｖ通信は、小さいおよび大きい地理的エリアにわたる大規模コンテンツ配信を可能にし得る。そのような車両ネットワークにおけるコンテンツ配信はＤＳＲＣのブロードキャスト性質を利用することができるが、動的トポロジー、予測不可能な消去、および肯定応答の欠如に関する課題が生じる。ランダム線形ネットワークコーディング（ＲＬＮＣ：random linear network coding）はこれらの課題に対処することが可能であり得る。しかしながら、ＲＬＮＣに関連する高い復号複雑度が、特に大規模コンテンツ配信について、それの適用可能性を制限する。
【００２０】
[0025]中継器なしの単一ソースの特定のシナリオのための低複雑度手法（low complexity approach）はファウンテンコードである。しかしながら、ファウンテンコードを中継するための技法を開発することが望ましい。本開示では、低複雑度アルゴリズムを用いて実装され得る、ファウンテンコードを中継するための技法について説明する。
【００２１】
[0026]分散ファウンテンネットワークコード（ＤＦＮＣ：distributed-fountain network code）など、車両ネットワークのためのネットワークコーディング方式は、低い符号化、再符号化、および復号複雑度を有する。ＤＦＮＣは、ソースにおいてファウンテンコードを使用し、ファウンテンコードを近似する中間車両において再符号化を使用する。中間車両における再符号化は、ファウンテンコードの次数分布を満たすために、低複雑度次数低減と次数低減パケットのランダム線形結合とを含む。低複雑度信念伝搬（ＢＰ：belief propagation）復号が宛先において適用される。
【００２２】
[0027]図３は、ファウンテンコードを中継するためのネットワークを示す図３００である。図３を参照すると、ソース（たとえば、セルラー基地局、ＲＳＵ）３０２は、ｋ個のパケットを含むファイルを有し得る。各パケットは長さｌのバイナリベクトルであり得る。ソース３０２は、ワイヤレスに接続された車両ネットワーク３０４を通して１つまたは複数の宛先３０６に同じファイルを送ろうとし得る。ソース３０２は、ファウンテンコードを使用してネイティブパケットを符号化し、限られた持続時間の間、符号化パケットを車両ネットワーク３０４に注入する。本開示では、高品質ファイルブロードキャスティング遅延配信を達成する、中間ノード（たとえば、車両３０４Ａ、３０４Ｂ、および３０４Ｃ）において中継するための方法について説明する。
【００２３】
[0028]所与の時間に、各中間車両（または中継器）は、受信されたパケットのセットをバッファ中に有し得る。バッファ中の各パケットはネイティブパケットのセットの線形結合であり得る。各パケットを作成するために使用されたネイティブパケットの数は次数と呼ばれることがある。中継器がパケットを送信する機会を有するとき、中継器は、１）次数低減、および２）次数条件付き結合という２つのステップを実行する。この２段手法は、中継する際に十分な多様性を与える。
【００２４】
[0029]次数低減では、中継器によって受信されたパケットの純次数が低減される。その上、複数のパケットが同じネイティブパケットを有し得ることが利用される。低複雑度手法（たとえば、低複雑度アルゴリズム）が使用され得る。たとえば、１の次数を有するパケット（次数１パケット）、および２の次数を有するパケット（次数２パケット）が、すべてのパケットの次数低減を実行するために効率的な様式で使用され得る。次数低減は、中継器によって新たに受信されたすべてのパケット、または中継バッファ中のすべてのパケットのサブセットに対して実行され得る。次数低減は、次数条件付き結合を実行するための多数のパケット選定を可能にするために、パケットの次数を最小にする。
【００２５】
[0030]一態様では、次数１パケットは信念伝搬のために使用され得る。これは、新しい次数１パケットを利用する反復ステップであり得る。次数２パケットは、同値類（equivalence class）を形成するために使用され得る。同値類中の任意の２つのネイティブパケットが、次数２パケットの排他的論理和をとる（次数２パケットに対して排他的論理和演算を実行する）ことによって取得され得る。この性質が、より高い次数のパケットからそのような組合せを削除するために使用され得る。より高い次数のパケットは次数低減のためにも使用され得る。より高い次数のパケットを使用しながら計算複雑度を制限することが鍵である。
【００２６】
[0031]同値類は以下のように定義され得る。
【００２７】
同値類  −  符号化パケットのセット
【００２８】
【数１】
2016521949.tif 000003
【００２９】
を仮定すると、帰納される類Ｅは、以下の条件を満たす一意のネイティブパケットのセットである。ｘa，ｘb∈Ｅである場合、
【００３０】
【数２】
2016521949.tif 000004
【００３１】
であるような次数２符号化パケットのセットΓ⊆｛１，．．．，ｒ｝が存在する。
[0032]符号化パケットの所与のセットはいくつかの同値類を帰納し得る。同値類は、次数２パケットのみを使用して定義される。
【００３２】
[0033]一態様では、低複雑度をもつ次数低減が行われ得る。したがって、復号ネイティブパケットのセットである復号セットＤと同値類とが、次数低減を実行するために利用され得る。復号セットおよび同値類は次数低減パケットの現在のセットに関して定義され得る。
【００３３】
[0034]次数低減のために、新しいパケットが中間ノード（または中継器）によって受信されたとき、復号セットＤに属する新しいパケット中のすべてのネイティブパケットが削除される。次に、中間ノードは、同じ同値類に属する新しいパケット中のネイティブパケットのうちの２つのパケットがあるかどうかを検査する。そのようなパケットがある場合、ネイティブパケットのこのペアは、対応する同値類から生成された同じペアを追加することによって削除される。このプロセスは、新しいパケット中のネイティブパケットのそのようなペアが削除され得なくなるまで繰り返され得る。次数低減された新しいパケットが２よりも小さいかまたはそれに等しい次数を有する場合、復号セットＤおよび同値類は以下ように更新される。次数低減された新しいパケットの次数が１に等しい場合、中間ノードはさらに信念伝搬（ＢＰ）復号を進める。その後、復号セットＤおよび同値類が更新される。次数低減された新しいパケットの次数が２に等しい場合、同値類が更新される。次数低減の後に、高い次数をもつ符号化パケットは、より低い次数をもつパケットになる。
【００３４】
[0035]ＮEが同値類の数を表す、低複雑度次数低減のためのアルゴリズムの一例（アルゴリズム１）は以下の通りであり得る。
【００３５】
【数３】
2016521949.tif 000005
【００３６】
[0036]次数条件付き結合では、送信のためのパケットが、所与の／適切な次数分布に基づいて次数低減パケットを結合することによって生成される。より詳細には、ファウンテンコードの次数分布が使用され得る。所与の次数について、所与の次数よりも低いかまたはそれに等しい次数をもつパケットが、パケットに割り当てられた重みに基づいて選択される。重み割当ては、前に選択されたパケットに基づいて時間変動し得る。このプロセスは、ターゲット次数に到達するか、または最大回数の選択が使い果たされるまで続き得る。この手法を通して生成された各パケットは、次数１パケットのセットと、次数２パケットによって形成された同値類とを使用して、さらに多様化され得る。
【００３７】
[0037]次数条件付き結合の一態様では、中間ノード（または中継器）が、ブロードキャストすべき新しいパケットを生成しようとするとき、中間ノードは、最初に、分布（たとえば、ロバストソリトン（ＲＳ：Robust Soliton）分布または他の最適化された次数分布）からターゲット次数ｄをランダムに選ぶ。次に、中間ノードは、以下のように次数ｄをもつ新しいパケットを構成する。最初に、ｄよりも小さいかまたはそれに等しい次数をもつパケットがランダムに選択される。この次数をｄ’とする。次に、ｄ−ｄ’よりも小さいかまたはそれに等しい次数をもつパケットがランダムに選択される。このプロセスは、ターゲット次数に到達するか、または最大回数のステップが使用されるまで続き得る。２つの符号化パケットの和の次数は、それらのそれぞれの次数の和である必要はない。パケットを選択する間、同値類を使用する次数低減が適用され得る。次数低減を適用する理由は、復号セットおよび同値類が、パケットが受信された時間と比較して大幅に変化した可能性があることである。
【００３８】
[0038]ターゲット次数ｄよりも小さいかまたはそれに等しい次数をもつパケットは、事前に割り当てられた分布に従ってランダムに選択され得る。分布は、集合Ｓ（ｄ）＝｛ｙ∈Ｙ｜ｄｅｇ（ｙ）≦ｄ｝における重み割当てを正規化することによって生成され得る。ｚを新たに再符号化されたパケットとする。重み割当ては、将来の送信において低い／０の確率をもつ符号化パケットが選択されるように、重みが各ｙ∈ｚに割り当てられることを可能にする。具体的には、Ｗ（ｙ）の初期値は１に設定され得る（すなわち、ｙは、再符号化パケットを生成するために一度も使用されていない）。次いで、ｙがｚを構成する（すなわち、ｙ∈ｚである）ように選択された場合、Ｗ（ｙ）は、ある定数ｃについてＷ（ｙ）ｅ-cに更新される。
【００３９】
[0039]ＮEが同値類の数を表す、分布ベースのパケット構成の擬似コードの一例を以下のアルゴリズム２に提示する。
【００４０】
【数４】
2016521949.tif 000006
【００４１】
[0040]アルゴリズム１における次数低減は一部分にすぎないことがあるので、アルゴリズム２におけるパケット構成プロセスはさらなるパケット多様化から恩恵を受け得る。多様化は、新たに再符号化されたパケットｚ中のネイティブパケットｘが別のネイティブパケットｘ’と交換されることを可能にする。交換は、ｘおよびｘ’が、復号セット中にあるか、または同じ同値類中にある（ｘ’〜ｘによって示される）場合、効率的に実行され得る。パケット多様性を最大にするために、復号セットまたは同値類中のネイティブパケットｘ’はランダムに一様に選択され得る。同値類から選定されたｘ’について、現在利用可能な次数２符号化パケットを使用することによって、
【００４２】
【数５】
2016521949.tif 000007
【００４３】
が生成され得る。（ｘ，ｘ’）の同値連鎖（equivalence chain）Ｃy（ｘ，ｘ’）を、
【００４４】
【数６】
2016521949.tif 000008
【００４５】
に等しい和をもつパケットのセットとする。ペア（ｘ，ｘ’）のためのこの同値連鎖を見つけることは、本質的にツリー探索（tree search）アルゴリズムであり得る。
【００４６】
[0041]ＮEが同値類の数を表す、パケット多様化のためのアルゴリズムの一例（アルゴリズム３）は以下の通りであり得る。
【００４７】
【数７】
2016521949.tif 000009
【００４８】
[0042]図４は、パケットを中継する方法のフローチャート４００である。本方法は、中間ノードまたは中継器（たとえば、図１中のデバイス２  １０４または図２中の第２の車両２０４）によって実行され得る。ステップ４０２において、中間ノードは少なくとも１つのパケットを受信する。少なくとも１つのパケットは、ソース（たとえば、図１中のデバイス１  １０２または図２中の第１の車両２０２）あるいは別の中間ノードまたは中継器から受信され得る。その上、受信された少なくとも１つのパケットは、ファウンテンコードを使用して符号化され得る。
【００４９】
[0043]ステップ４０４において、中間ノードは少なくとも１つのパケットの次数を低減する。少なくとも１つのパケットの次数は、少なくとも１つのパケットを作成するために使用されたネイティブパケットの数を指す。中間ノードは、ネイティブパケットの復号セットに属する少なくとも１つのパケットのすべてのネイティブパケットを削除することによって次数を低減し得る。追加または代替として、中間ノードは、同じ同値類に属する少なくとも１つのパケットの２つのネイティブパケットの任意の組合せを削除することによって次数を低減し得る。特に、同値類はネイティブパケットのセットを指し、ここにおいて、同値類中の任意の２つのネイティブパケットの排他的論理和演算は、次数２処理済みパケットに対して排他的論理和演算を実行することによって生成され得る。
【００５０】
[0044]ステップ４０６において、中間ノードは、低減された次数に基づいて少なくとも１つのパケットを処理する。たとえば、処理は、中間ノードが、少なくとも１つのパケットの低減された次数を決定することを含み得る。少なくとも１つのパケットの低減された次数が１に等しいとき、中間ノードは、少なくとも１つの次数低減パケットで復号セットを更新し、信念伝搬に基づいて復号セットを更新し、少なくとも１つの次数低減パケットに基づいて同値類を更新し得る。少なくとも１つのパケットの低減された次数が２に等しいとき、中間ノードは、少なくとも１つの次数低減パケットに基づいて同値類を更新し得る。
【００５１】
[0045]ステップ４０８において、中間ノードは結合パケットを生成する。結合パケットを生成することは、低減された次数と処理済みパケットの各々の重みとに基づいて、少なくとも１つの処理済みパケットを少なくとも１つの他の処理済みパケットと結合することを含み得る。たとえば、結合パケットを生成することは、結合パケットのためのターゲット次数を決定することと、少なくとも１つのパケットの各パケットに割り当てられた重みに基づいて、ターゲット次数よりも小さいかまたはそれに等しい次数を有する少なくとも１つの次数低減パケットを選択することとを含み得る。少なくとも１つの次数低減パケットは、選択されたパケットのそれぞれの次数の和がターゲット次数に等しくなるまで、または最大回数の選択が行われるまで選択され得る。その後、中間ノードは、結合パケットを生成するために少なくとも１つの選択された次数低減パケットの各々を結合し得る。
【００５２】
[0046]ステップ４１０において、中間ノードは結合パケットを多様化させる。結合パケットを多様化させることは、結合パケット中のネイティブパケットをネイティブパケットの復号セットからの別のネイティブパケットと交換することを含み得る。多様化させることはまた、結合パケット中の任意のネイティブパケットを、同じ同値類に属する別のネイティブパケットと交換することを含み得る。ステップ４１２において、中間ノードは、宛先または中継器（たとえば、図１中のデバイス３  １０６あるいは図２中の第３の車両２０６および／または第４の車両２０８）に結合パケットを送信／ブロードキャストする。
【００５３】
[0047]図５は、例示的な装置５０２中の異なるモジュール／手段／構成要素間のデータフローを示す概念データフロー図５００である。本装置は、中間ノードまたは中継器（たとえば、図１中のデバイス２  １０４または図２中の第２の車両２０４）であり得る。本装置は、受信モジュール５０４と、次数低減モジュール５０６と、パケット処理モジュール５０８と、結合パケット生成モジュール５１０と、メモリ５１２と、送信モジュール５１４とを含む。
【００５４】
[0048]受信モジュール５０４は少なくとも１つのパケットを受信する。少なくとも１つのパケットはソースまたは中継器５１６から受信され得る。その上、受信された少なくとも１つのパケットは、ファウンテンコードを使用して符号化され得る。
【００５５】
[0049]次数低減モジュール５０６は少なくとも１つのパケットの次数を低減する。少なくとも１つのパケットの次数は、少なくとも１つのパケットを作成するために使用されたネイティブパケットの数を指す。次数低減モジュール５０６は、ネイティブパケットの復号セットに属する少なくとも１つのパケットのすべてのネイティブパケットを削除することによって次数を低減し得る。ネイティブパケットの復号セットはメモリ５１２に記憶され得る。追加または代替として、次数低減モジュール５０６は、同じ同値類に属する少なくとも１つのパケットの２つのネイティブパケットの任意の組合せを削除することによって次数を低減し得る。同値類もメモリ５１２に記憶され得る。特に、同値類はネイティブパケットのセットを指し、ここにおいて、同値類中の任意の２つのネイティブパケットの排他的論理和演算は、次数２処理済みパケットに対して排他的論理和演算を実行することによって生成され得る。
【００５６】
[0050]パケット処理モジュール５０８は、低減された次数に基づいて少なくとも１つのパケットを処理する。たとえば、処理は、パケット処理モジュール５０８が、少なくとも１つのパケットの低減された次数を決定することを含み得る。少なくとも１つのパケットの低減された次数が１に等しいとき、パケット処理モジュール５０８は、少なくとも１つの次数低減パケットで、メモリ５１２に記憶された復号セットを更新し、信念伝搬に基づいて、メモリ５１２に記憶された復号セットを更新し、少なくとも１つの次数低減パケットに基づいて、メモリ５１２に記憶された同値類を更新し得る。少なくとも１つのパケットの低減された次数が２に等しいとき、パケット処理モジュール５０８は、少なくとも１つの次数低減パケットに基づいて、メモリ５１２に記憶された同値類を更新し得る。
【００５７】
[0051]結合パケット生成モジュール５１０は結合パケットを生成し得る。結合パケットを生成することは、低減された次数と処理済みパケットの各々の重みとに基づいて、少なくとも１つの処理済みパケットを少なくとも１つの他の処理済みパケットと結合することを含み得る。たとえば、結合パケットを生成することは、結合パケット生成モジュール５１０が、結合パケットのためのターゲット次数を決定することと、少なくとも１つのパケットの各パケットに割り当てられた重みに基づいて、ターゲット次数よりも小さいかまたはそれに等しい次数を有する少なくとも１つの次数低減パケットを選択することとを含み得る。結合パケット生成モジュール５１０は、選択されたパケットのそれぞれの次数の和がターゲット次数に等しくなるまで、または最大回数の選択が行われるまで、少なくとも１つの次数低減パケットを選択し得る。その後、結合パケット生成モジュール５１０は、結合パケットを生成するために少なくとも１つの選択された次数低減パケットの各々を結合し得る。
【００５８】
[0052]結合パケット生成モジュール５１０はまた、結合パケットを多様化させ得る。結合パケットを多様化させることは、結合パケット中のネイティブパケットを、メモリ５１２に記憶されたネイティブパケットの復号セットからの別のネイティブパケットと交換することを含み得る。多様化させることはまた、結合パケット中の任意のネイティブパケットを、メモリ５１２に記憶された同じ同値類に属する別のネイティブパケットと交換することを含み得る。その後、結合パケット生成モジュール５１０は、宛先または中継器５１８（たとえば、図１中のデバイス３  １０６あるいは図２中の第３の車両２０６および／または第４の車両２０８）に結合パケットを（送信モジュール５１４を介して）送信／ブロードキャストし得る。
【００５９】
[0053]本装置は、図４の上述のフローチャート中のアルゴリズムのステップの各々を実行する追加のモジュールを含み得る。したがって、図４の上述のフローチャート中の各ステップは１つのモジュールによって実行され得、本装置は、それらのモジュールのうちの１つまたは複数を含み得る。それらのモジュールは、述べられたプロセス／アルゴリズムを行うように特に構成された１つまたは複数のハードウェア構成要素であるか、述べられたプロセス／アルゴリズムを実行するように構成されたプロセッサによって実装されるか、プロセッサによる実装のためにコンピュータ可読媒体内に記憶されるか、またはそれらの何らかの組合せであり得る。
【００６０】
[0054]図６は、処理システム６１４を採用する装置５０２’のためのハードウェア実装形態の一例を示す図６００である。処理システム６１４は、バス６２４によって概略的に表されるバスアーキテクチャを用いて実装され得る。バス６２４は、処理システム６１４の特定の適用例および全体的な設計制約に応じて、任意の数の相互接続バスおよびブリッジを含み得る。バス６２４は、プロセッサ６０４、モジュール５０４、５０６、５０８、５１０、５１２、５１４およびコンピュータ可読媒体６０６によって表される１つまたは複数のプロセッサおよび／またはハードウェアモジュールを含む様々な回路を互いにリンクする。バス６２４はまた、タイミングソース、周辺機器、電圧調整器、および電力管理回路など、様々な他の回路をリンクし得るが、これらの回路は当技術分野においてよく知られており、したがって、これ以上説明しない。
【００６１】
[0055]処理システム６１４はトランシーバ６１０に結合され得る。トランシーバ６１０は１つまたは複数のアンテナ６２０に結合される。トランシーバ６１０は、伝送媒体を介して様々な他の装置と通信するための手段を与える。トランシーバ６１０は、１つまたは複数のアンテナ６２０から信号を受信し、受信された信号から情報を抽出し、抽出された情報を処理システム６１４、特に受信モジュール５０４に与える。さらに、トランシーバ６１０は、処理システム６１４、特に送信モジュール５１４から情報を受信し、受信された情報に基づいて、１つまたは複数のアンテナ６２０に適用されるべき信号を生成する。処理システム６１４は、コンピュータ可読媒体６０６に結合されたプロセッサ６０４を含む。プロセッサ６０４は、コンピュータ可読媒体６０６に記憶されたソフトウェアの実行を含む一般的な処理を担当する。ソフトウェアは、プロセッサ６０４によって実行されたとき、処理システム６１４に、特定の装置のための上記で説明した様々な機能を実行させる。コンピュータ可読媒体６０６はまた、ソフトウェアを実行するときにプロセッサ６０４によって操作されるデータを記憶するために使用され得る。処理システムは、モジュール５０４、５０６、５０８、５１０、５１２、および５１４のうちの少なくとも１つをさらに含む。それらのモジュールは、プロセッサ６０４中で動作するか、コンピュータ可読媒体６０６中に常駐する／記憶されたソフトウェアモジュールであるか、プロセッサ６０４に結合された１つまたは複数のハードウェアモジュールであるか、またはそれらの何らかの組合せであり得る。
【００６２】
[0056]一構成では、パケットを中継するための装置６０２／６０２’は、少なくとも１つのパケットを受信するための手段と、少なくとも１つのパケットの次数を低減するための手段と、低減された次数に基づいて少なくとも１つのパケットを処理するための手段と、結合パケットを生成するための手段と、生成するための手段が、低減された次数と処理済みパケットの各々の重みとに基づいて、少なくとも１つの処理済みパケットを少なくとも１つの他の処理済みパケットと結合するように構成された、結合パケット中のネイティブパケットをネイティブパケットの復号セットからの別のネイティブパケットと交換することと、結合パケット中の任意のネイティブパケットを、同じ同値類に属する別のネイティブパケットと交換することとを行うように構成された、結合パケットを多様化させるための手段と、結合パケットを送信するための手段とを含む。上述の手段は、上述の手段によって具陳される機能を実行するように構成された、装置５０２、および／または装置５０２’の処理システム６１４の上述のモジュールのうちの１つまたは複数であり得る。
【００６３】
[0057]開示したプロセスにおけるステップの特定の順序または階層は、例示的な手法の一例であることを理解されたい。設計上の選好に基づいて、プロセスにおけるステップの特定の順序または階層は再構成され得ることを理解されたい。さらに、いくつかのステップは組み合わせられるかまたは省略され得る。添付の方法クレームは、様々なステップの要素を例示的な順序で提示したものであり、提示された特定の順序または階層に限定されるものではない。
【００６４】
[0058]以上の説明は、当業者が本明細書で説明した様々な態様を実施することができるようにするために提供したものである。これらの態様に対する様々な変更は当業者には容易に明らかであり、本明細書で定義された一般原理は他の態様に適用され得る。したがって、特許請求の範囲は、本明細書に示された態様に限定されるものではなく、クレーム文言に矛盾しない全範囲を与えられるべきであり、ここにおいて、単数形の要素への言及は、そのように明記されていない限り、「唯一無二の」を意味するものではなく、「１つまたは複数の」を意味するものである。別段に明記されていない限り、「いくつか（some）」という用語は１つまたは複数を指す。「Ａ、Ｂ、またはＣのうちの少なくとも１つ」、「Ａ、Ｂ、およびＣのうちの少なくとも１つ」、ならびに「Ａ、Ｂ、Ｃ、またはそれらの任意の組合せ」などの組合せは、Ａ、Ｂ、および／またはＣの任意の組合せを含み、複数のＡ、複数のＢ、または複数のＣを含み得る。詳細には、「Ａ、Ｂ、またはＣのうちの少なくとも１つ」、「Ａ、Ｂ、およびＣのうちの少なくとも１つ」、ならびに「Ａ、Ｂ、Ｃ、またはそれらの任意の組合せ」などの組合せは、Ａのみ、Ｂのみ、Ｃのみ、ＡおよびＢ、ＡおよびＣ、ＢおよびＣ、またはＡおよびＢおよびＣであり得、ここで、いかなるそのような組合せも、Ａ、Ｂ、またはＣのうちの１つまたは複数のメンバーを含んでいることがある。当業者に知られている、または後に知られることになる、本開示全体にわたって説明した様々な態様の要素のすべての構造的および機能的均等物は、参照により本明細書に明確に組み込まれ、特許請求の範囲に包含されるものである。その上、本明細書で開示したいかなることも、そのような開示が特許請求の範囲に明示的に具陳されているかどうかにかかわらず、公に供するものではない。いかなるクレーム要素も、その要素が「ための手段」という語句を使用して明確に具陳されていない限り、ミーンズプラスファンクションとして解釈されるべきではない。
【図１】
2016521949.tif 000010
【図２】
2016521949.tif 000011
【図３】
2016521949.tif 000012
【図４】
2016521949.tif 000013
【図５】
2016521949.tif 000014
【図６】
2016521949.tif 000015
【手続補正書】
【提出日】平成28年3月1日(2016.3.1)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
パケットを中継する方法であって、
少なくとも１つのパケットを受信することと、
前記少なくとも１つのパケットの次数を低減することと、
前記低減された次数に基づいて前記少なくとも１つのパケットを処理することと、
結合パケットを生成することと、前記生成することが、前記低減された次数と前記処理済みパケットの各々の重みとに基づいて、前記少なくとも１つの処理済みパケットを少なくとも１つの他の処理済みパケットと結合することを備える、
前記結合パケットを送信することとを備える、方法。
【請求項２】
前記受信された少なくとも１つのパケットが、ファウンテンコードを使用して符号化される、請求項１に記載の方法。
【請求項３】
前記少なくとも１つのパケットの前記次数が、前記少なくとも１つのパケットを作成するために使用されたネイティブパケットの数を備える、請求項１に記載の方法。
【請求項４】
前記低減することが、
ネイティブパケットの復号セットに属する前記少なくとも１つのパケットのすべてのネイティブパケットを削除することと、
同じ同値類に属する前記少なくとも１つのパケットの２つのネイティブパケットの任意の組合せを削除することとを備える、請求項１に記載の方法。
【請求項５】
同値類がネイティブパケットのセットを備え、ここにおいて、前記同値類中の任意の２つのネイティブパケットの排他的論理和演算が、次数２処理済みパケットに対して排他的論理和演算を実行することによって生成され得る、請求項４に記載の方法。
【請求項６】
前記処理することが、
前記少なくとも１つのパケットの前記低減された次数を決定することを備え、
前記少なくとも１つのパケットの前記低減された次数が１に等しいとき、前記処理することが、
前記少なくとも１つの次数低減パケットで前記復号セットを更新することと、
信念伝搬に基づいて前記復号セットを更新することと、
前記少なくとも１つの次数低減パケットに基づいて同値類を更新することとをさらに備え、
前記少なくとも１つのパケットの前記低減された次数が２に等しいとき、前記処理することが、前記少なくとも１つの次数低減パケットに基づいて前記同値類を更新することをさらに備える、請求項４に記載の方法。
【請求項７】
前記結合パケットを前記生成することが、
前記結合パケットのためのターゲット次数を決定することと、
前記少なくとも１つのパケットの各パケットに割り当てられた重みに基づいて、前記ターゲット次数よりも小さいかまたはそれに等しい次数を有する少なくとも１つの次数低減パケットを選択することと、
前記結合パケットを生成するために前記少なくとも１つの選択された次数低減パケットの各々を結合することとをさらに備える、請求項６に記載の方法。
【請求項８】
前記少なくとも１つの次数低減パケットは、選択されたパケットのそれぞれの次数の和が前記ターゲット次数に等しくなるまで、または最大回数の選択が行われるまで選択される、請求項７に記載の方法。
【請求項９】
前記結合パケット中のネイティブパケットをネイティブパケットの前記復号セットからの別のネイティブパケットと交換することと、
前記結合パケット中の任意のネイティブパケットを、同じ同値類に属する別のネイティブパケットと交換することとを備える、前記結合パケットを多様化させることをさらに備える、請求項７に記載の方法。
【請求項１０】
パケットを中継するための装置であって、
少なくとも１つのパケットを受信するための手段と、
前記少なくとも１つのパケットの次数を低減するための手段と、
前記低減された次数に基づいて前記少なくとも１つのパケットを処理するための手段と、
結合パケットを生成するための手段と、生成するための前記手段が、前記低減された次数と前記処理済みパケットの各々の重みとに基づいて、前記少なくとも１つの処理済みパケットを少なくとも１つの他の処理済みパケットと結合するように構成された、
前記結合パケットを送信するための手段とを備える、装置。
【請求項１１】
前記受信された少なくとも１つのパケットが、ファウンテンコードを使用して符号化される、請求項１０に記載の装置。
【請求項１２】
前記少なくとも１つのパケットの前記次数が、前記少なくとも１つのパケットを作成するために使用されたネイティブパケットの数を備える、請求項１０に記載の装置。
【請求項１３】
低減するための前記手段が、
ネイティブパケットの復号セットに属する前記少なくとも１つのパケットのすべてのネイティブパケットを削除することと、
同じ同値類に属する前記少なくとも１つのパケットの２つのネイティブパケットの任意の組合せを削除することとを行うように構成された、請求項１０に記載の装置。
【請求項１４】
同値類がネイティブパケットのセットを備え、ここにおいて、前記同値類中の任意の２つのネイティブパケットの排他的論理和演算が、次数２処理済みパケットに対して排他的論理和演算を実行することによって生成され得る、請求項１３に記載の装置。
【請求項１５】
処理するための前記手段が、
前記少なくとも１つのパケットの前記低減された次数を決定することを行うように構成され、
前記少なくとも１つのパケットの前記低減された次数が１に等しいとき、処理するための前記手段が、
前記少なくとも１つの次数低減パケットで前記復号セットを更新することと、
信念伝搬に基づいて前記復号セットを更新することと、
前記少なくとも１つの次数低減パケットに基づいて同値類を更新することとを行うようにさらに構成され、
前記少なくとも１つのパケットの前記低減された次数が２に等しいとき、処理するための前記手段が、前記少なくとも１つの次数低減パケットに基づいて前記同値類を更新することを行うようにさらに構成された、請求項１３に記載の装置。
【請求項１６】
前記結合パケットを生成するための前記手段が、
前記結合パケットのためのターゲット次数を決定することと、
前記少なくとも１つのパケットの各パケットに割り当てられた重みに基づいて、前記ターゲット次数よりも小さいかまたはそれに等しい次数を有する少なくとも１つの次数低減パケットを選択することと、
前記結合パケットを生成するために前記少なくとも１つの選択された次数低減パケットの各々を結合することとを行うようにさらに構成された、請求項１５に記載の装置。
【請求項１７】
前記少なくとも１つの次数低減パケットは、選択されたパケットのそれぞれの次数の和が前記ターゲット次数に等しくなるまで、または最大回数の選択が行われるまで選択される、請求項１６に記載の装置。
【請求項１８】
前記結合パケット中のネイティブパケットをネイティブパケットの前記復号セットからの別のネイティブパケットと交換することと、
前記結合パケット中の任意のネイティブパケットを、同じ同値類に属する別のネイティブパケットと交換することとを行うように構成された、前記結合パケットを多様化させるための手段をさらに備える、請求項１６に記載の装置。
【請求項１９】
パケットを中継するための装置であって、
メモリと、
前記メモリに結合された少なくとも１つのプロセッサとを備え、前記少なくとも１つのプロセッサが、
少なくとも１つのパケットを受信することと、
前記少なくとも１つのパケットの次数を低減することと、
前記低減された次数に基づいて前記少なくとも１つのパケットを処理することと、
結合パケットを生成することと、ここにおいて、生成するように構成された前記少なくとも１つのプロセッサが、前記低減された次数と前記処理済みパケットの各々の重みとに基づいて、前記少なくとも１つの処理済みパケットを少なくとも１つの他の処理済みパケットと結合するようにさらに構成された、
前記結合パケットを送信することとを行うように構成された、装置。
【請求項２０】
前記受信された少なくとも１つのパケットが、ファウンテンコードを使用して符号化される、請求項１９に記載の装置。
【請求項２１】
前記少なくとも１つのパケットの前記次数が、前記少なくとも１つのパケットを作成するために使用されたネイティブパケットの数を備える、請求項１９に記載の装置。
【請求項２２】
低減するように構成された前記少なくとも１つのプロセッサが、
ネイティブパケットの復号セットに属する前記少なくとも１つのパケットのすべてのネイティブパケットを削除することと、
同じ同値類に属する前記少なくとも１つのパケットの２つのネイティブパケットの任意の組合せを削除することとを行うようにさらに構成された、請求項１９に記載の装置。
【請求項２３】
同値類がネイティブパケットのセットを備え、ここにおいて、前記同値類中の任意の２つのネイティブパケットの排他的論理和演算が、次数２処理済みパケットに対して排他的論理和演算を実行することによって生成され得る、請求項２２に記載の装置。
【請求項２４】
処理するように構成された前記少なくとも１つのプロセッサが、
前記少なくとも１つのパケットの前記低減された次数を決定することを行うようにさらに構成され、
前記少なくとも１つのパケットの前記低減された次数が１に等しいとき、処理するように構成された前記少なくとも１つのプロセッサが、
前記少なくとも１つの次数低減パケットで前記復号セットを更新することと、
信念伝搬に基づいて前記復号セットを更新することと、
前記少なくとも１つの次数低減パケットに基づいて同値類を更新することとを行うようにさらに構成され、
前記少なくとも１つのパケットの前記低減された次数が２に等しいとき、処理するように構成された前記少なくとも１つのプロセッサが、前記少なくとも１つの次数低減パケットに基づいて前記同値類を更新することを行うようにさらに構成された、請求項２２に記載の装置。
【請求項２５】
前記結合パケットを生成するように構成された前記少なくとも１つのプロセッサが、
前記結合パケットのためのターゲット次数を決定することと、
前記少なくとも１つのパケットの各パケットに割り当てられた重みに基づいて、前記ターゲット次数よりも小さいかまたはそれに等しい次数を有する少なくとも１つの次数低減パケットを選択することと、
前記結合パケットを生成するために前記少なくとも１つの選択された次数低減パケットの各々を結合することとを行うようにさらに構成された、請求項２４に記載の装置。
【請求項２６】
前記少なくとも１つの次数低減パケットは、選択されたパケットのそれぞれの次数の和が前記ターゲット次数に等しくなるまで、または最大回数の選択が行われるまで選択される、請求項２５に記載の装置。
【請求項２７】
前記少なくとも１つのプロセッサが、
前記結合パケットを多様化させることを行うようにさらに構成され、ここにおいて、多様化させるように構成された前記少なくとも１つのプロセッサが、
前記結合パケット中のネイティブパケットをネイティブパケットの前記復号セットからの別のネイティブパケットと交換することと、
前記結合パケット中の任意のネイティブパケットを、同じ同値類に属する別のネイティブパケットと交換することとを行うようにさらに構成された、請求項２５に記載の装置。
【請求項２８】
ワイヤレス通信のためのコンピュータ実行可能コードを記憶したコンピュータ可読媒体であって、
少なくとも１つのパケットを受信し、
前記少なくとも１つのパケットの次数を低減し、
前記低減された次数に基づいて前記少なくとも１つのパケットを処理し、
結合パケットを生成し、前記生成することが、前記低減された次数と前記処理済みパケットの各々の重みとに基づいて、前記少なくとも１つの処理済みパケットを少なくとも１つの他の処理済みパケットと結合することを備える、
前記結合パケットを送信する
ためのコードを備える、コンピュータ可読媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００６４
【補正方法】変更
【補正の内容】
【００６４】
[0058]以上の説明は、当業者が本明細書で説明した様々な態様を実施することができるようにするために提供したものである。これらの態様に対する様々な変更は当業者には容易に明らかであり、本明細書で定義された一般原理は他の態様に適用され得る。したがって、特許請求の範囲は、本明細書に示された態様に限定されるものではなく、クレーム文言に矛盾しない全範囲を与えられるべきであり、ここにおいて、単数形の要素への言及は、そのように明記されていない限り、「唯一無二の」を意味するものではなく、「１つまたは複数の」を意味するものである。別段に明記されていない限り、「いくつか（some）」という用語は１つまたは複数を指す。「Ａ、Ｂ、またはＣのうちの少なくとも１つ」、「Ａ、Ｂ、およびＣのうちの少なくとも１つ」、ならびに「Ａ、Ｂ、Ｃ、またはそれらの任意の組合せ」などの組合せは、Ａ、Ｂ、および／またはＣの任意の組合せを含み、複数のＡ、複数のＢ、または複数のＣを含み得る。詳細には、「Ａ、Ｂ、またはＣのうちの少なくとも１つ」、「Ａ、Ｂ、およびＣのうちの少なくとも１つ」、ならびに「Ａ、Ｂ、Ｃ、またはそれらの任意の組合せ」などの組合せは、Ａのみ、Ｂのみ、Ｃのみ、ＡおよびＢ、ＡおよびＣ、ＢおよびＣ、またはＡおよびＢおよびＣであり得、ここで、いかなるそのような組合せも、Ａ、Ｂ、またはＣのうちの１つまたは複数のメンバーを含んでいることがある。当業者に知られている、または後に知られることになる、本開示全体にわたって説明した様々な態様の要素のすべての構造的および機能的均等物は、参照により本明細書に明確に組み込まれ、特許請求の範囲に包含されるものである。その上、本明細書で開示したいかなることも、そのような開示が特許請求の範囲に明示的に具陳されているかどうかにかかわらず、公に供するものではない。いかなるクレーム要素も、その要素が「ための手段」という語句を使用して明確に具陳されていない限り、ミーンズプラスファンクションとして解釈されるべきではない。
以下に、本願出願の当初の特許請求の範囲に記載された発明を付記する。
［Ｃ１］
パケットを中継する方法であって、
少なくとも１つのパケットを受信することと、
前記少なくとも１つのパケットの次数を低減することと、
前記低減された次数に基づいて前記少なくとも１つのパケットを処理することと、
結合パケットを生成することと、前記生成することが、前記低減された次数と前記処理済みパケットの各々の重みとに基づいて、前記少なくとも１つの処理済みパケットを少なくとも１つの他の処理済みパケットと結合することを備える、
前記結合パケットを送信することとを備える、方法。
［Ｃ２］
前記受信された少なくとも１つのパケットが、ファウンテンコードを使用して符号化される、Ｃ１に記載の方法。
［Ｃ３］
前記少なくとも１つのパケットの前記次数が、前記少なくとも１つのパケットを作成するために使用されたネイティブパケットの数を備える、Ｃ１に記載の方法。
［Ｃ４］
前記低減することが、
ネイティブパケットの復号セットに属する前記少なくとも１つのパケットのすべてのネイティブパケットを削除することと、
同じ同値類に属する前記少なくとも１つのパケットの２つのネイティブパケットの任意の組合せを削除することとを備える、Ｃ１に記載の方法。
［Ｃ５］
同値類がネイティブパケットのセットを備え、ここにおいて、前記同値類中の任意の２つのネイティブパケットの排他的論理和演算が、次数２処理済みパケットに対して排他的論理和演算を実行することによって生成され得る、Ｃ４に記載の方法。
［Ｃ６］
前記処理することが、
前記少なくとも１つのパケットの前記低減された次数を決定することを備え、
前記少なくとも１つのパケットの前記低減された次数が１に等しいとき、前記処理することが、
前記少なくとも１つの次数低減パケットで前記復号セットを更新することと、
信念伝搬に基づいて前記復号セットを更新することと、
前記少なくとも１つの次数低減パケットに基づいて同値類を更新することとをさらに備え、
前記少なくとも１つのパケットの前記低減された次数が２に等しいとき、前記処理することが、前記少なくとも１つの次数低減パケットに基づいて前記同値類を更新することをさらに備える、Ｃ４に記載の方法。
［Ｃ７］
前記結合パケットを前記生成することが、
前記結合パケットのためのターゲット次数を決定することと、
前記少なくとも１つのパケットの各パケットに割り当てられた重みに基づいて、前記ターゲット次数よりも小さいかまたはそれに等しい次数を有する少なくとも１つの次数低減パケットを選択することと、
前記結合パケットを生成するために前記少なくとも１つの選択された次数低減パケットの各々を結合することとをさらに備える、Ｃ６に記載の方法。
［Ｃ８］
前記少なくとも１つの次数低減パケットは、選択されたパケットのそれぞれの次数の和が前記ターゲット次数に等しくなるまで、または最大回数の選択が行われるまで選択される、Ｃ７に記載の方法。
［Ｃ９］
前記結合パケット中のネイティブパケットをネイティブパケットの前記復号セットからの別のネイティブパケットと交換することと、
前記結合パケット中の任意のネイティブパケットを、同じ同値類に属する別のネイティブパケットと交換することとを備える、前記結合パケットを多様化させることをさらに備える、Ｃ７に記載の方法。
［Ｃ１０］
パケットを中継するための装置であって、
少なくとも１つのパケットを受信するための手段と、
前記少なくとも１つのパケットの次数を低減するための手段と、
前記低減された次数に基づいて前記少なくとも１つのパケットを処理するための手段と、
結合パケットを生成するための手段と、生成するための前記手段が、前記低減された次数と前記処理済みパケットの各々の重みとに基づいて、前記少なくとも１つの処理済みパケットを少なくとも１つの他の処理済みパケットと結合するように構成された、
前記結合パケットを送信するための手段とを備える、装置。
［Ｃ１１］
前記受信された少なくとも１つのパケットが、ファウンテンコードを使用して符号化される、Ｃ１０に記載の装置。
［Ｃ１２］
前記少なくとも１つのパケットの前記次数が、前記少なくとも１つのパケットを作成するために使用されたネイティブパケットの数を備える、Ｃ１０に記載の装置。
［Ｃ１３］
低減するための前記手段が、
ネイティブパケットの復号セットに属する前記少なくとも１つのパケットのすべてのネイティブパケットを削除することと、
同じ同値類に属する前記少なくとも１つのパケットの２つのネイティブパケットの任意の組合せを削除することとを行うように構成された、Ｃ１０に記載の装置。
［Ｃ１４］
同値類がネイティブパケットのセットを備え、ここにおいて、前記同値類中の任意の２つのネイティブパケットの排他的論理和演算が、次数２処理済みパケットに対して排他的論理和演算を実行することによって生成され得る、Ｃ１３に記載の装置。
［Ｃ１５］
処理するための前記手段が、
前記少なくとも１つのパケットの前記低減された次数を決定することを行うように構成され、
前記少なくとも１つのパケットの前記低減された次数が１に等しいとき、処理するための前記手段が、
前記少なくとも１つの次数低減パケットで前記復号セットを更新することと、
信念伝搬に基づいて前記復号セットを更新することと、
前記少なくとも１つの次数低減パケットに基づいて同値類を更新することとを行うようにさらに構成され、
前記少なくとも１つのパケットの前記低減された次数が２に等しいとき、処理するための前記手段が、前記少なくとも１つの次数低減パケットに基づいて前記同値類を更新することを行うようにさらに構成された、Ｃ１３に記載の装置。
［Ｃ１６］
前記結合パケットを生成するための前記手段が、
前記結合パケットのためのターゲット次数を決定することと、
前記少なくとも１つのパケットの各パケットに割り当てられた重みに基づいて、前記ターゲット次数よりも小さいかまたはそれに等しい次数を有する少なくとも１つの次数低減パケットを選択することと、
前記結合パケットを生成するために前記少なくとも１つの選択された次数低減パケットの各々を結合することとを行うようにさらに構成された、Ｃ１５に記載の装置。
［Ｃ１７］
前記少なくとも１つの次数低減パケットは、選択されたパケットのそれぞれの次数の和が前記ターゲット次数に等しくなるまで、または最大回数の選択が行われるまで選択される、Ｃ１６に記載の装置。
［Ｃ１８］
前記結合パケット中のネイティブパケットをネイティブパケットの前記復号セットからの別のネイティブパケットと交換することと、
前記結合パケット中の任意のネイティブパケットを、同じ同値類に属する別のネイティブパケットと交換することとを行うように構成された、前記結合パケットを多様化させるための手段をさらに備える、Ｃ１６に記載の装置。
［Ｃ１９］
パケットを中継するための装置であって、
メモリと、
前記メモリに結合された少なくとも１つのプロセッサとを備え、前記少なくとも１つのプロセッサが、
少なくとも１つのパケットを受信することと、
前記少なくとも１つのパケットの次数を低減することと、
前記低減された次数に基づいて前記少なくとも１つのパケットを処理することと、
結合パケットを生成することと、ここにおいて、生成するように構成された前記少なくとも１つのプロセッサが、前記低減された次数と前記処理済みパケットの各々の重みとに基づいて、前記少なくとも１つの処理済みパケットを少なくとも１つの他の処理済みパケットと結合するようにさらに構成された、
前記結合パケットを送信することとを行うように構成された、装置。
［Ｃ２０］
前記受信された少なくとも１つのパケットが、ファウンテンコードを使用して符号化される、Ｃ１９に記載の装置。
［Ｃ２１］
前記少なくとも１つのパケットの前記次数が、前記少なくとも１つのパケットを作成するために使用されたネイティブパケットの数を備える、Ｃ１９に記載の装置。
［Ｃ２２］
低減するように構成された前記少なくとも１つのプロセッサが、
ネイティブパケットの復号セットに属する前記少なくとも１つのパケットのすべてのネイティブパケットを削除することと、
同じ同値類に属する前記少なくとも１つのパケットの２つのネイティブパケットの任意の組合せを削除することとを行うようにさらに構成された、Ｃ１９に記載の装置。
［Ｃ２３］
同値類がネイティブパケットのセットを備え、ここにおいて、前記同値類中の任意の２つのネイティブパケットの排他的論理和演算が、次数２処理済みパケットに対して排他的論理和演算を実行することによって生成され得る、Ｃ２２に記載の装置。
［Ｃ２４］
処理するように構成された前記少なくとも１つのプロセッサが、
前記少なくとも１つのパケットの前記低減された次数を決定することを行うようにさらに構成され、
前記少なくとも１つのパケットの前記低減された次数が１に等しいとき、処理するように構成された前記少なくとも１つのプロセッサが、
前記少なくとも１つの次数低減パケットで前記復号セットを更新することと、
信念伝搬に基づいて前記復号セットを更新することと、
前記少なくとも１つの次数低減パケットに基づいて同値類を更新することとを行うようにさらに構成され、
前記少なくとも１つのパケットの前記低減された次数が２に等しいとき、処理するように構成された前記少なくとも１つのプロセッサが、前記少なくとも１つの次数低減パケットに基づいて前記同値類を更新することを行うようにさらに構成された、Ｃ２２に記載の装置。
［Ｃ２５］
前記結合パケットを生成するように構成された前記少なくとも１つのプロセッサが、
前記結合パケットのためのターゲット次数を決定することと、
前記少なくとも１つのパケットの各パケットに割り当てられた重みに基づいて、前記ターゲット次数よりも小さいかまたはそれに等しい次数を有する少なくとも１つの次数低減パケットを選択することと、
前記結合パケットを生成するために前記少なくとも１つの選択された次数低減パケットの各々を結合することとを行うようにさらに構成された、Ｃ２４に記載の装置。
［Ｃ２６］
前記少なくとも１つの次数低減パケットは、選択されたパケットのそれぞれの次数の和が前記ターゲット次数に等しくなるまで、または最大回数の選択が行われるまで選択される、Ｃ２５に記載の装置。
［Ｃ２７］
前記少なくとも１つのプロセッサが、
前記結合パケットを多様化させることを行うようにさらに構成され、ここにおいて、多様化させるように構成された前記少なくとも１つのプロセッサが、
前記結合パケット中のネイティブパケットをネイティブパケットの前記復号セットからの別のネイティブパケットと交換することと、
前記結合パケット中の任意のネイティブパケットを、同じ同値類に属する別のネイティブパケットと交換することとを行うようにさらに構成された、Ｃ２５に記載の装置。
［Ｃ２８］
コンピュータ可読媒体に記憶されたコンピュータプログラム製品であって、少なくとも１つのプロセッサ上で実行されたとき、
少なくとも１つのパケットを受信するステップと、
前記少なくとも１つのパケットの次数を低減するステップと、
前記低減された次数に基づいて前記少なくとも１つのパケットを処理するステップと、
結合パケットを生成するステップと、前記生成するステップが、前記低減された次数と前記処理済みパケットの各々の重みとに基づいて、前記少なくとも１つの処理済みパケットを少なくとも１つの他の処理済みパケットと結合することを備える、
前記結合パケットを送信するステップとを実行するコードを備える、コンピュータプログラム製品。
【国際調査報告】
2016521949.tif 000016
2016521949.tif 000017