伝送レート許容性判定装置、伝送レート許容性判定方法、及びプログラム
【課題】伝送レートが制限された複数の伝送路から構成され、ネットワーク符号化を行うネットワークにおいて、複数のメッセージを複数の終端ノードに対して伝送する際に、与えられた伝送レートで各メッセージを伝送することが可能か否かを判定する。
【解決手段】伝送レート許容性判定装置において、対象となるネットワークを表す非周期有効グラフG、各伝送路のレート制限Ｒ、および各終端ノードが受け取るべきメッセージのインデックスKTを記憶する記憶手段と、各メッセージの伝送レートωを入力する入力手段と、対象ネットワークの各値を前記記憶手段から読み出し、所定の複数の拘束条件に代入し、当該複数の拘束条件を満足するフロー変数ζ(Λ)e（for e∈E,Λ∈2K、Λは各辺のサブチャンネルのインデックス）の解の有無を線形計画法を用いて判定する伝送レート許容性判定処理手段と、判定結果に基づき、伝送レートが許容か否かを出力する出力手段と、を備える。
【解決手段】伝送レート許容性判定装置において、対象となるネットワークを表す非周期有効グラフG、各伝送路のレート制限Ｒ、および各終端ノードが受け取るべきメッセージのインデックスKTを記憶する記憶手段と、各メッセージの伝送レートωを入力する入力手段と、対象ネットワークの各値を前記記憶手段から読み出し、所定の複数の拘束条件に代入し、当該複数の拘束条件を満足するフロー変数ζ(Λ)e（for e∈E,Λ∈2K、Λは各辺のサブチャンネルのインデックス）の解の有無を線形計画法を用いて判定する伝送レート許容性判定処理手段と、判定結果に基づき、伝送レートが許容か否かを出力する出力手段と、を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の伝送路から構成されるネットワークの各ノードが符号化を行うネットワーク符号化(Network Coding)の技術に関連するものであり、特に、各辺（各伝送路に対応）にレート制限を持つ非周期有向グラフとして与えられたネットワークにおいて、複数のメッセージを複数の終端ノードに対して伝送する際に、メッセージの伝送レートの候補が与えられたとき、実際にメッセージをこのレートで伝送することが可能か否かを判定するための技術に関するものである。
【背景技術】
【０００２】
ネットワーク符号化は、各辺にレート制限を持つ非周期有向グラフとしてネットワークが与えられた際に、情報源ノードから終端ノードへメッセージを伝送するための符号化方式を与えるものである（非特許文献１、及び非特許文献２）。
【０００３】
ネットワーク符号化における最も一般的な枠組みは、同一のメッセージを複数の終端ノードへ伝送するものである。この場合、伝送可能なレートは、
【０００４】
【数１】
で与えられる。ただし、上記式１におけるTは終端ノードの集合である。また、maxflow(s, t)は、情報源ノードｓと終端ノードｔとの間のmaxflow（最大フロー）を表わす関数である（非特許文献２の(18.8)式および定理18.1を参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】[Ahlswede00] R. Ahlswede, N. Cai, S. -Y. R. Li, and R. W. Yeung, "Network information flow,"IEEE Trans. Inform. Theory, vol. 46, pp. 1204-1216, 2000.
【非特許文献２】[Yeung08]R. W. Yeung, Information Theory and Network Coding, Springer, 2008, (18. The Max-Flow Bound (pp. 421-434), 21. Multi-Source Network Coding (pp. 505-539))
【非特許文献３】[Yan07]X. Yan, R. W. Yeung, and Z. Zhang, "The capacity region for multi-source multi-sink network coding," Proc. 2007 IEEE International Symposium on Information Theory, pp. 116-120, 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記のように、同一のメッセージを複数の終端ノードへ伝送する場合における伝送可能なレートは式１で与えられる。
【０００７】
しかしながら、必ずしも同一でないメッセージの集合を終端ノードへ伝送する場合、伝送可能なレートの条件は必ずしも明らかでない。非特許文献２や非特許文献３では伝送可能なレート条件が与えられているが、具体的な計算方法は自明ではない。
【０００８】
すなわち、各メッセージに対して伝送レートの候補が与えられているとき、このレートの組みが実際に伝送可能（許容）であるか否かを判定するためには、
１）与えられたネットワークに対して、伝送可能（許容）なレートの条件が明らかであること。
【０００９】
２）上記１）で明らかにされた条件が計算可能であること。
の２つをクリアする必要があるが、従来においては１）および２）の両者を満足する技術はなかった。
【００１０】
この点に鑑みて、本発明は、各メッセージに対して伝送レートの候補が与えられているとき、このレートの組みが実際に伝送可能（許容）であるか否かを判定する技術を提供することを課題としている。この課題を以下でより具体的に説明する。
【００１１】
非周期有向グラフG=(V,E)（ただし、Vはノードの集合、Eは辺の集合）と各辺(i,j)∈Eに対するレート制限Rijの組Rが与えられたとき、(G, R)でネットワークが定まる。このようなネットワークの例を図１に示す。更に、情報源ノードsが送出するメッセージを、
【００１２】
【数２】
とし、また、ネットワークの終端ノードの集合をTとした場合、各終端ノードtが受け取るメッセージ（のインデックス）の集合を
【００１３】
【数３】
とする。上記非周期有向グラフG、レート制限の組R、及びメッセージのインデックスの集合KTの３つからなる組
【００１４】
【数４】
を与えることにより、マルチソースマルチキャスティング（multi-source multicasting）システムが定まる。
【００１５】
各メッセージに関しては、
【００１６】
【数５】
とする。上記式におけるｎはメッセージ伝送の際に各辺が使用される回数を表わし、ωiはメッセージxiの伝送レートを表わす。また、Fは有限体である。
【００１７】
このときノードiからノードjへ通信路n回使用あたり送られるビット数をkijとすると、レート制限は
kij/n<Rij （式２）
として表わすことができる。
【００１８】
本発明が解決しようとする課題は、multi-source multicastingシステムが
【００１９】
【数６】
で与えられ、伝送レートの組
【００２０】
【数７】
で各メッセージが送出されるとき、式２で示されるレート制限を満足しながら各終端ノードtにおいてKt （をインデックスとするようなメッセージ）が正しく復号されるような符号が存在するか否かを判定することである。ここで、正しく復号されるような符号が存在するとき、式３で示される伝送レートは、許容であると呼ぶことにする。
【課題を解決するための手段】
【００２１】
上記の課題を解決するために、本発明は、伝送レートが制限された複数の伝送路から構成され、ネットワーク符号化を行うネットワークにおいて、複数のメッセージを複数の終端ノードに対して伝送する際に、与えられた伝送レートで各メッセージを伝送することが可能か否かを示す伝送レートの許容性を判定する伝送レート許容性判定装置であって、対象となるネットワークを表す非周期有効グラフG、各伝送路のレート制限Ｒ、および各終端ノードが受け取るべきメッセージのインデックスKTを記憶する記憶手段と、各メッセージの伝送レートωを入力する入力手段と、ノードの集合V及び伝送路に対応する辺の集合Eからなる非周期有効グラフG、レート制限Ｒ、メッセージのインデックスKT、及び伝送レートωの各値を前記記憶手段から読み出し、所定の複数の拘束条件に代入し、当該複数の拘束条件を満足するフロー変数ζ(Λ)e（for e∈E,Λ∈2K、Λは各辺のサブチャンネルのインデックス）の解の有無を線形計画法を用いて判定する伝送レート許容性判定処理手段と、前記伝送レート許容性判定処理手段の判定結果に基づき、入力された伝送レートが許容か否かを示す情報を出力する出力手段とを備えることを特徴とする伝送レート許容性判定装置として構成される。
【発明の効果】
【００２２】
本発明によれば、各辺にレート制限を持つ非周期有向グラフとして与えられたネットワークにおいて、複数のメッセージを複数の終端ノードに対して伝送する際に、メッセージの伝送レートの候補が与えられたとき、実際にメッセージをこのレートで伝送することが可能か否かを判定することが可能となり、ネットワークの資源をより有効に利用可能とするようなレートの割り当てを行うことが可能となる。
【図面の簡単な説明】
【００２３】
【図１】ネットワークの例を示す図である。
【図２】本発明の実施の形態に係る伝送レート許容性判定装置１０の機能構成図である。
【図３】伝送レート許容性判定装置１０の処理手順を示すフローチャートである。
【図４】終端ノードが復号の際に自分が受け取るメッセージに関する情報しか利用できない場合の伝送可能なレートの集合を示す図である。
【発明を実施するための形態】
【００２４】
以下、図面を参照して、本発明の実施の形態について説明する。
【００２５】
本実施の形態において対象とするmulti-source multicastingシステムは、前述した
【００２６】
【数８】
で定められ、これは所与のものとする。
【００２７】
本実施の形態では、この所与のmulti-source multicastingシステムにおいて、伝送レートの組
【００２８】
【数９】
が許容であるか否かを判定する伝送レート許容性判定装置１０が提供される。
【００２９】
（装置構成）
図２に、本発明の実施の形態に係る伝送レート許容性判定装置１０の機能構成図を示す。図２に示すように、伝送レート許容性判定装置１０は、入力部１１、伝送レート許容性判定処理部１２、データ記憶部１３、出力部１４を備える。また、伝送レート許容性判定処理部１２は、サブチャンネル生成部１２１、線形計画法求解演算部１２２、及び演算用記憶部１２３を備える。各機能部の機能概要は以下のとおりである。
【００３０】
入力部１１は、許容性を判定したい伝送レートの組を入力として受け取り、伝送レート許容性判定処理部１２へ渡す機能部である。データ記憶部１３は、伝送レート許容性判定処理部１２による線形計画法の演算実行の際に用いるネットワークに関するデータ
【００３１】
【数１０】
を記憶している。すなわち、データ記憶部１３は、有向グラフGのパラメータVおよびE、および各辺のレート制限R、および各終端ノードがどのメッセージを受け取るかに関するデータ（メッセージのインデックス）KTを記憶している。
【００３２】
伝送レート許容性判定処理部１２は、入力部１１により入力されたデータを受信し、更に、データ記憶部１３から、後述する複数の拘束条件を満足する解の探索処理を線形計画法を用いて実行する際に必要なデータを読み出して、これらのデータを用いて、線形計画法の解法アルゴリズム（シンプレックス法など）を実行し、拘束条件を満足する解の有無を判定する機能部である。
【００３３】
ここで、伝送レート許容性判定処理部１２におけるサブチャンネル生成部１２１は、線形計画法での演算を行う準備として、グラフGにおける各辺をサブチャンネルに分ける処理等を行う機能部である。線形計画法求解演算部１２２は、線形計画法の解法アルゴリズムを用いた演算を実行する機能部である。
【００３４】
また、演算用記憶部１２３は、線形計画法の解法アルゴリズムを用いた演算を実行するにあたって、変数等の領域を確保して、演算途中のデータや、演算結果を記憶する機能部であり、線形計画法求解演算部１２２は、演算用記憶部１２３に対してデータの読み書きをしながら線形計画法の解法アルゴリズムを用いた演算を進める。
伝送レート許容性判定処理部１２は、線形計画法求解演算部１２２による演算実行結果を出力部１４に渡し、出力部１４は、当該実行結果を受けて、もし解が存在した場合には「許容」を、そうでない場合には「非許容」を出力する。
【００３５】
伝送レート許容性判定装置１０は、例えば、ＣＰＵやメモリ、ハードディスク等を備えた一般的なコンピュータに本実施の形態で説明するアルゴリズム（処理手順）に対応するプログラムを実行させることにより実現可能である。すなわち、当該プログラムは、コンピュータを、本実施の形態で説明する伝送レート許容性判定装置１０の各部として機能させるためのプログラムである。
【００３６】
当該プログラムは、可搬メモリ等のコンピュータ読み取り可能な記録媒体に記録して配布してもよいし、ネットワーク上のサーバからダウンロードすることもできる。
【００３７】
また、例えば、伝送レート許容性判定装置１０を、コンピュータに、線形計画法求解演算部１２２に対応するハードウェアロジック回路を組み込んだ装置として実現することもできる。また、伝送レート許容性判定装置１０の全体をハードウェアロジック回路で実現することも可能である。また、伝送レート許容性判定装置１０を、実際のネットワークを構成する伝送装置内に組み込むことにより、伝送レート許容性判定機能を備えた伝送装置を提供することもできる。
【００３８】
（処理動作）
以下、図２に示す機能構成を有する伝送レート許容性判定装置１０の処理動作について、図３に示すフローチャートの手順に沿って説明する。
【００３９】
まず、入力部１１から許容性を判定したい伝送レートの組
【００４０】
【数１１】
が入力され、入力部１１は、上記伝送レートの組を伝送レート許容性判定処理部１２に渡す（ステップ１）。伝送レート許容性判定処理部１２において、当該伝送レートの組のデータが演算用記憶部１２３に格納される。
【００４１】
伝送レート許容性判定処理部１２におけるサブチャンネル生成部１２１は、データ記憶部１３からネットワークのデータを読み出し、有向グラフGの各辺e∈Eをサブチャンネルに分け、サブチャンネルのインデックスをΛ∈2Kとする（ステップ２）。ここで、集合Kに対して２Kは集合Kの全ての部分集合の族を表わすものとする。サブチャンネルのデータは、演算用記憶部１２３に格納される。
【００４２】
次に、伝送レート許容性判定処理部１２における線形計画法求解演算部１２２は、以下で説明する最適化問題の求解対象となるフロー変数を、
【００４３】
【数１２】
として設定する（ステップ３）。当該フロー変数は、下記の条件１〜条件３（式４〜式６）を満足するものとする。
【００４４】
線形計画法求解演算部１２２は、データ記憶部１３から、非周期有効グラフG、レート制限Ｒ、メッセージのインデックスKT、及び伝送レートωの各データを読み出し、これらを下記の条件１〜条件３（式４〜式６）、及び式７で示される拘束条件に代入し、これらの拘束条件を満足する解
【００４５】
【数１３】
の有無を判定するための線形計画法求解演算処理を行う（ステップ４）。
【００４６】
【数１４】
【００４７】
【数１５】
ただし、式５において、fin(e)=vは有向辺eの終端ノードがｖであることを示す。また、ini(e)=vは有向辺eの開始ノードがｖであることを示す。
【００４８】
【数１６】
は、辺eに関する足し合わせをfin(e)=vを満足する有向辺eに関して行うことを表す。
【００４９】
【数１７】
上記の条件１はフローの正値性を表わし、条件２はフローの保存を表わし、条件３はレート制限（（式２）に対応する）を表わしている。
【００５０】
ステップ４において、線形計画法求解演算部１２２は、上記の条件１〜３の下で、
【００５１】
【数１８】
を満足する解を求めるための演算を行う。
【００５２】
なお、式７において、
【００５３】
【数１９】
は、集合
【００５４】
【数２０】
に関する足し合わせを、
【００５５】
【数２１】
を満足する集合
【００５６】
【数２２】
に関して行うことを表わしている。また、
【００５７】
【数２３】
は、ノードｖに関する足し合わせを(v,t)が有向辺の集合Eに含まれているときにのみ行うことを表している。
【００５８】
上記の条件１〜３の下で、式７を満足する解
【００５９】
【数２４】
が存在するならば、許容性を判定する対象である伝送レートの組
【００６０】
【数２５】
は許容であり、上記の解が存在しないならば上記伝送レートの組は許容ではない。
【００６１】
条件１〜３（式４〜６）および式７は、フロー変数
【００６２】
【数２６】
に関して線形の拘束条件であるので、この解を求めることは、フロー変数に関する線形計画法の問題を解くことと見なすことができる。従って、ステップ４において、線形計画法求解演算部１２２は、線形計画法を解くためのアルゴリズム（シンプレックス法など）を用いることで、上記の解を求める演算を行うことにより、許容性の判定を実行することが可能である。
【００６３】
図３のフローチャートにおいて、ステップ４の演算の実行結果が得られると、線形計画法求解演算部１２２は、実行結果（解が存在する場合には解の値、解が存在しない場合には解が存在しないことを示す情報）を出力部１４に渡す。
【００６４】
そして、解が存在する場合（ステップ５のYes)、出力部１４は、「許容」を示す情報を出力し（ステップ６）、解が存在しない場合（ステップ５のNo)、出力部１４は、「非許容」を示す情報を出力する（ステップ７）。すなわち、出力部１４は、入力された許容性判定対象の伝送レートの組が許容されるか否かを示す情報を出力する。
【００６５】
以上の処理により、ネットワーク符号化を行うネットワークの伝送レートに関する「許容」、「非許容」の判定結果を得ることができる。
【００６６】
なお、「発明が解決しようとする課題」の部分で説明したレートの許容性判定可能であるための条件１）については、その領域が具体的な形で図４に示すように与えられている。図４は、終端ノードが復号の際に自分が受け取るメッセージに関する情報しか利用できない場合の伝送可能なレートの集合を示すものであるが、終端ノードが自分が受け取るメッセージ以外の情報も利用できる場合の伝送可能なレート集合も同様に表わすことができ、本発明に係るアルゴリズムの適用も容易である。
【００６７】
（実施の形態の効果等）
これまでに説明したように、本実施の形態に係る伝送レート許容性判定装置１０が実行する処理のアルゴリズムは線形計画法で実現できるので、ネットワークのパラメータ(グラフ構造Gなど)が固定であるならば、各辺の使用回数nに関しては定数オーダーで与えられたレートの組の許容性に関する判定が可能となる。
【００６８】
そして、与えられた伝送レートの組が許容か否かを判定することによって、ネットワークの資源をより有効に利用可能とするようなレートの割り当てを行うことが可能となる。
【産業上の利用可能性】
【００６９】
本発明は、各辺にレート制限を持つ非周期有向グラフとして与えられたネットワークにおいて、複数のメッセージを複数の終端ノードに対して伝送する際に、メッセージの伝送レートの候補が与えられたとき、実際にメッセージをこのレートで伝送することが可能か否かを判定する技術に適用できる。
【００７０】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００７１】
１０ 伝送レート許容性判定装置
１１ 入力部
１２ 伝送レート許容性判定処理部
１３ データ記憶部
１４ 出力部
１２１ サブチャンネル生成部
１２２ 線形計画法求解演算部
１２３ 演算用記憶部
【技術分野】
【０００１】
本発明は、複数の伝送路から構成されるネットワークの各ノードが符号化を行うネットワーク符号化(Network Coding)の技術に関連するものであり、特に、各辺（各伝送路に対応）にレート制限を持つ非周期有向グラフとして与えられたネットワークにおいて、複数のメッセージを複数の終端ノードに対して伝送する際に、メッセージの伝送レートの候補が与えられたとき、実際にメッセージをこのレートで伝送することが可能か否かを判定するための技術に関するものである。
【背景技術】
【０００２】
ネットワーク符号化は、各辺にレート制限を持つ非周期有向グラフとしてネットワークが与えられた際に、情報源ノードから終端ノードへメッセージを伝送するための符号化方式を与えるものである（非特許文献１、及び非特許文献２）。
【０００３】
ネットワーク符号化における最も一般的な枠組みは、同一のメッセージを複数の終端ノードへ伝送するものである。この場合、伝送可能なレートは、
【０００４】
【数１】
で与えられる。ただし、上記式１におけるTは終端ノードの集合である。また、maxflow(s, t)は、情報源ノードｓと終端ノードｔとの間のmaxflow（最大フロー）を表わす関数である（非特許文献２の(18.8)式および定理18.1を参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】[Ahlswede00] R. Ahlswede, N. Cai, S. -Y. R. Li, and R. W. Yeung, "Network information flow,"IEEE Trans. Inform. Theory, vol. 46, pp. 1204-1216, 2000.
【非特許文献２】[Yeung08]R. W. Yeung, Information Theory and Network Coding, Springer, 2008, (18. The Max-Flow Bound (pp. 421-434), 21. Multi-Source Network Coding (pp. 505-539))
【非特許文献３】[Yan07]X. Yan, R. W. Yeung, and Z. Zhang, "The capacity region for multi-source multi-sink network coding," Proc. 2007 IEEE International Symposium on Information Theory, pp. 116-120, 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記のように、同一のメッセージを複数の終端ノードへ伝送する場合における伝送可能なレートは式１で与えられる。
【０００７】
しかしながら、必ずしも同一でないメッセージの集合を終端ノードへ伝送する場合、伝送可能なレートの条件は必ずしも明らかでない。非特許文献２や非特許文献３では伝送可能なレート条件が与えられているが、具体的な計算方法は自明ではない。
【０００８】
すなわち、各メッセージに対して伝送レートの候補が与えられているとき、このレートの組みが実際に伝送可能（許容）であるか否かを判定するためには、
１）与えられたネットワークに対して、伝送可能（許容）なレートの条件が明らかであること。
【０００９】
２）上記１）で明らかにされた条件が計算可能であること。
の２つをクリアする必要があるが、従来においては１）および２）の両者を満足する技術はなかった。
【００１０】
この点に鑑みて、本発明は、各メッセージに対して伝送レートの候補が与えられているとき、このレートの組みが実際に伝送可能（許容）であるか否かを判定する技術を提供することを課題としている。この課題を以下でより具体的に説明する。
【００１１】
非周期有向グラフG=(V,E)（ただし、Vはノードの集合、Eは辺の集合）と各辺(i,j)∈Eに対するレート制限Rijの組Rが与えられたとき、(G, R)でネットワークが定まる。このようなネットワークの例を図１に示す。更に、情報源ノードsが送出するメッセージを、
【００１２】
【数２】
とし、また、ネットワークの終端ノードの集合をTとした場合、各終端ノードtが受け取るメッセージ（のインデックス）の集合を
【００１３】
【数３】
とする。上記非周期有向グラフG、レート制限の組R、及びメッセージのインデックスの集合KTの３つからなる組
【００１４】
【数４】
を与えることにより、マルチソースマルチキャスティング（multi-source multicasting）システムが定まる。
【００１５】
各メッセージに関しては、
【００１６】
【数５】
とする。上記式におけるｎはメッセージ伝送の際に各辺が使用される回数を表わし、ωiはメッセージxiの伝送レートを表わす。また、Fは有限体である。
【００１７】
このときノードiからノードjへ通信路n回使用あたり送られるビット数をkijとすると、レート制限は
kij/n<Rij （式２）
として表わすことができる。
【００１８】
本発明が解決しようとする課題は、multi-source multicastingシステムが
【００１９】
【数６】
で与えられ、伝送レートの組
【００２０】
【数７】
で各メッセージが送出されるとき、式２で示されるレート制限を満足しながら各終端ノードtにおいてKt （をインデックスとするようなメッセージ）が正しく復号されるような符号が存在するか否かを判定することである。ここで、正しく復号されるような符号が存在するとき、式３で示される伝送レートは、許容であると呼ぶことにする。
【課題を解決するための手段】
【００２１】
上記の課題を解決するために、本発明は、伝送レートが制限された複数の伝送路から構成され、ネットワーク符号化を行うネットワークにおいて、複数のメッセージを複数の終端ノードに対して伝送する際に、与えられた伝送レートで各メッセージを伝送することが可能か否かを示す伝送レートの許容性を判定する伝送レート許容性判定装置であって、対象となるネットワークを表す非周期有効グラフG、各伝送路のレート制限Ｒ、および各終端ノードが受け取るべきメッセージのインデックスKTを記憶する記憶手段と、各メッセージの伝送レートωを入力する入力手段と、ノードの集合V及び伝送路に対応する辺の集合Eからなる非周期有効グラフG、レート制限Ｒ、メッセージのインデックスKT、及び伝送レートωの各値を前記記憶手段から読み出し、所定の複数の拘束条件に代入し、当該複数の拘束条件を満足するフロー変数ζ(Λ)e（for e∈E,Λ∈2K、Λは各辺のサブチャンネルのインデックス）の解の有無を線形計画法を用いて判定する伝送レート許容性判定処理手段と、前記伝送レート許容性判定処理手段の判定結果に基づき、入力された伝送レートが許容か否かを示す情報を出力する出力手段とを備えることを特徴とする伝送レート許容性判定装置として構成される。
【発明の効果】
【００２２】
本発明によれば、各辺にレート制限を持つ非周期有向グラフとして与えられたネットワークにおいて、複数のメッセージを複数の終端ノードに対して伝送する際に、メッセージの伝送レートの候補が与えられたとき、実際にメッセージをこのレートで伝送することが可能か否かを判定することが可能となり、ネットワークの資源をより有効に利用可能とするようなレートの割り当てを行うことが可能となる。
【図面の簡単な説明】
【００２３】
【図１】ネットワークの例を示す図である。
【図２】本発明の実施の形態に係る伝送レート許容性判定装置１０の機能構成図である。
【図３】伝送レート許容性判定装置１０の処理手順を示すフローチャートである。
【図４】終端ノードが復号の際に自分が受け取るメッセージに関する情報しか利用できない場合の伝送可能なレートの集合を示す図である。
【発明を実施するための形態】
【００２４】
以下、図面を参照して、本発明の実施の形態について説明する。
【００２５】
本実施の形態において対象とするmulti-source multicastingシステムは、前述した
【００２６】
【数８】
で定められ、これは所与のものとする。
【００２７】
本実施の形態では、この所与のmulti-source multicastingシステムにおいて、伝送レートの組
【００２８】
【数９】
が許容であるか否かを判定する伝送レート許容性判定装置１０が提供される。
【００２９】
（装置構成）
図２に、本発明の実施の形態に係る伝送レート許容性判定装置１０の機能構成図を示す。図２に示すように、伝送レート許容性判定装置１０は、入力部１１、伝送レート許容性判定処理部１２、データ記憶部１３、出力部１４を備える。また、伝送レート許容性判定処理部１２は、サブチャンネル生成部１２１、線形計画法求解演算部１２２、及び演算用記憶部１２３を備える。各機能部の機能概要は以下のとおりである。
【００３０】
入力部１１は、許容性を判定したい伝送レートの組を入力として受け取り、伝送レート許容性判定処理部１２へ渡す機能部である。データ記憶部１３は、伝送レート許容性判定処理部１２による線形計画法の演算実行の際に用いるネットワークに関するデータ
【００３１】
【数１０】
を記憶している。すなわち、データ記憶部１３は、有向グラフGのパラメータVおよびE、および各辺のレート制限R、および各終端ノードがどのメッセージを受け取るかに関するデータ（メッセージのインデックス）KTを記憶している。
【００３２】
伝送レート許容性判定処理部１２は、入力部１１により入力されたデータを受信し、更に、データ記憶部１３から、後述する複数の拘束条件を満足する解の探索処理を線形計画法を用いて実行する際に必要なデータを読み出して、これらのデータを用いて、線形計画法の解法アルゴリズム（シンプレックス法など）を実行し、拘束条件を満足する解の有無を判定する機能部である。
【００３３】
ここで、伝送レート許容性判定処理部１２におけるサブチャンネル生成部１２１は、線形計画法での演算を行う準備として、グラフGにおける各辺をサブチャンネルに分ける処理等を行う機能部である。線形計画法求解演算部１２２は、線形計画法の解法アルゴリズムを用いた演算を実行する機能部である。
【００３４】
また、演算用記憶部１２３は、線形計画法の解法アルゴリズムを用いた演算を実行するにあたって、変数等の領域を確保して、演算途中のデータや、演算結果を記憶する機能部であり、線形計画法求解演算部１２２は、演算用記憶部１２３に対してデータの読み書きをしながら線形計画法の解法アルゴリズムを用いた演算を進める。
伝送レート許容性判定処理部１２は、線形計画法求解演算部１２２による演算実行結果を出力部１４に渡し、出力部１４は、当該実行結果を受けて、もし解が存在した場合には「許容」を、そうでない場合には「非許容」を出力する。
【００３５】
伝送レート許容性判定装置１０は、例えば、ＣＰＵやメモリ、ハードディスク等を備えた一般的なコンピュータに本実施の形態で説明するアルゴリズム（処理手順）に対応するプログラムを実行させることにより実現可能である。すなわち、当該プログラムは、コンピュータを、本実施の形態で説明する伝送レート許容性判定装置１０の各部として機能させるためのプログラムである。
【００３６】
当該プログラムは、可搬メモリ等のコンピュータ読み取り可能な記録媒体に記録して配布してもよいし、ネットワーク上のサーバからダウンロードすることもできる。
【００３７】
また、例えば、伝送レート許容性判定装置１０を、コンピュータに、線形計画法求解演算部１２２に対応するハードウェアロジック回路を組み込んだ装置として実現することもできる。また、伝送レート許容性判定装置１０の全体をハードウェアロジック回路で実現することも可能である。また、伝送レート許容性判定装置１０を、実際のネットワークを構成する伝送装置内に組み込むことにより、伝送レート許容性判定機能を備えた伝送装置を提供することもできる。
【００３８】
（処理動作）
以下、図２に示す機能構成を有する伝送レート許容性判定装置１０の処理動作について、図３に示すフローチャートの手順に沿って説明する。
【００３９】
まず、入力部１１から許容性を判定したい伝送レートの組
【００４０】
【数１１】
が入力され、入力部１１は、上記伝送レートの組を伝送レート許容性判定処理部１２に渡す（ステップ１）。伝送レート許容性判定処理部１２において、当該伝送レートの組のデータが演算用記憶部１２３に格納される。
【００４１】
伝送レート許容性判定処理部１２におけるサブチャンネル生成部１２１は、データ記憶部１３からネットワークのデータを読み出し、有向グラフGの各辺e∈Eをサブチャンネルに分け、サブチャンネルのインデックスをΛ∈2Kとする（ステップ２）。ここで、集合Kに対して２Kは集合Kの全ての部分集合の族を表わすものとする。サブチャンネルのデータは、演算用記憶部１２３に格納される。
【００４２】
次に、伝送レート許容性判定処理部１２における線形計画法求解演算部１２２は、以下で説明する最適化問題の求解対象となるフロー変数を、
【００４３】
【数１２】
として設定する（ステップ３）。当該フロー変数は、下記の条件１〜条件３（式４〜式６）を満足するものとする。
【００４４】
線形計画法求解演算部１２２は、データ記憶部１３から、非周期有効グラフG、レート制限Ｒ、メッセージのインデックスKT、及び伝送レートωの各データを読み出し、これらを下記の条件１〜条件３（式４〜式６）、及び式７で示される拘束条件に代入し、これらの拘束条件を満足する解
【００４５】
【数１３】
の有無を判定するための線形計画法求解演算処理を行う（ステップ４）。
【００４６】
【数１４】
【００４７】
【数１５】
ただし、式５において、fin(e)=vは有向辺eの終端ノードがｖであることを示す。また、ini(e)=vは有向辺eの開始ノードがｖであることを示す。
【００４８】
【数１６】
は、辺eに関する足し合わせをfin(e)=vを満足する有向辺eに関して行うことを表す。
【００４９】
【数１７】
上記の条件１はフローの正値性を表わし、条件２はフローの保存を表わし、条件３はレート制限（（式２）に対応する）を表わしている。
【００５０】
ステップ４において、線形計画法求解演算部１２２は、上記の条件１〜３の下で、
【００５１】
【数１８】
を満足する解を求めるための演算を行う。
【００５２】
なお、式７において、
【００５３】
【数１９】
は、集合
【００５４】
【数２０】
に関する足し合わせを、
【００５５】
【数２１】
を満足する集合
【００５６】
【数２２】
に関して行うことを表わしている。また、
【００５７】
【数２３】
は、ノードｖに関する足し合わせを(v,t)が有向辺の集合Eに含まれているときにのみ行うことを表している。
【００５８】
上記の条件１〜３の下で、式７を満足する解
【００５９】
【数２４】
が存在するならば、許容性を判定する対象である伝送レートの組
【００６０】
【数２５】
は許容であり、上記の解が存在しないならば上記伝送レートの組は許容ではない。
【００６１】
条件１〜３（式４〜６）および式７は、フロー変数
【００６２】
【数２６】
に関して線形の拘束条件であるので、この解を求めることは、フロー変数に関する線形計画法の問題を解くことと見なすことができる。従って、ステップ４において、線形計画法求解演算部１２２は、線形計画法を解くためのアルゴリズム（シンプレックス法など）を用いることで、上記の解を求める演算を行うことにより、許容性の判定を実行することが可能である。
【００６３】
図３のフローチャートにおいて、ステップ４の演算の実行結果が得られると、線形計画法求解演算部１２２は、実行結果（解が存在する場合には解の値、解が存在しない場合には解が存在しないことを示す情報）を出力部１４に渡す。
【００６４】
そして、解が存在する場合（ステップ５のYes)、出力部１４は、「許容」を示す情報を出力し（ステップ６）、解が存在しない場合（ステップ５のNo)、出力部１４は、「非許容」を示す情報を出力する（ステップ７）。すなわち、出力部１４は、入力された許容性判定対象の伝送レートの組が許容されるか否かを示す情報を出力する。
【００６５】
以上の処理により、ネットワーク符号化を行うネットワークの伝送レートに関する「許容」、「非許容」の判定結果を得ることができる。
【００６６】
なお、「発明が解決しようとする課題」の部分で説明したレートの許容性判定可能であるための条件１）については、その領域が具体的な形で図４に示すように与えられている。図４は、終端ノードが復号の際に自分が受け取るメッセージに関する情報しか利用できない場合の伝送可能なレートの集合を示すものであるが、終端ノードが自分が受け取るメッセージ以外の情報も利用できる場合の伝送可能なレート集合も同様に表わすことができ、本発明に係るアルゴリズムの適用も容易である。
【００６７】
（実施の形態の効果等）
これまでに説明したように、本実施の形態に係る伝送レート許容性判定装置１０が実行する処理のアルゴリズムは線形計画法で実現できるので、ネットワークのパラメータ(グラフ構造Gなど)が固定であるならば、各辺の使用回数nに関しては定数オーダーで与えられたレートの組の許容性に関する判定が可能となる。
【００６８】
そして、与えられた伝送レートの組が許容か否かを判定することによって、ネットワークの資源をより有効に利用可能とするようなレートの割り当てを行うことが可能となる。
【産業上の利用可能性】
【００６９】
本発明は、各辺にレート制限を持つ非周期有向グラフとして与えられたネットワークにおいて、複数のメッセージを複数の終端ノードに対して伝送する際に、メッセージの伝送レートの候補が与えられたとき、実際にメッセージをこのレートで伝送することが可能か否かを判定する技術に適用できる。
【００７０】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００７１】
１０ 伝送レート許容性判定装置
１１ 入力部
１２ 伝送レート許容性判定処理部
１３ データ記憶部
１４ 出力部
１２１ サブチャンネル生成部
１２２ 線形計画法求解演算部
１２３ 演算用記憶部
【特許請求の範囲】
【請求項１】
伝送レートが制限された複数の伝送路から構成され、ネットワーク符号化を行うネットワークにおいて、複数のメッセージを複数の終端ノードに対して伝送する際に、与えられた伝送レートで各メッセージを伝送することが可能か否かを示す伝送レートの許容性を判定する伝送レート許容性判定装置であって、
対象となるネットワークを表す非周期有効グラフG、各伝送路のレート制限Ｒ、および各終端ノードが受け取るべきメッセージのインデックスKTを記憶する記憶手段と、
各メッセージの伝送レートωを入力する入力手段と、
ノードの集合V及び伝送路に対応する辺の集合Eからなる非周期有効グラフG、レート制限Ｒ、メッセージのインデックスKT、及び伝送レートωの各値を前記記憶手段から読み出し、所定の複数の拘束条件に代入し、当該複数の拘束条件を満足するフロー変数ζ(Λ)e（for e∈E,Λ∈2K、Λは各辺のサブチャンネルのインデックス）の解の有無を線形計画法を用いて判定する伝送レート許容性判定処理手段と、
前記伝送レート許容性判定処理手段の判定結果に基づき、入力された伝送レートが許容か否かを示す情報を出力する出力手段と
を備えることを特徴とする伝送レート許容性判定装置。
【請求項２】
前記複数の拘束条件は、
【数１】
【数２】
（ただし、fin(e)=vは有向辺eの終端ノードがｖであることを示し、ini(e)=vは有向辺eの開始ノードがｖであることを示す。）
【数３】
【数４】
の４つの条件式で表わされる条件であることを特徴とする請求項１に記載の伝送レート許容性判定装置。
【請求項３】
伝送レートが制限された複数の伝送路から構成され、ネットワーク符号化を行うネットワークにおいて、複数のメッセージを複数の終端ノードに対して伝送する際に、与えられた伝送レートで各メッセージを伝送することが可能か否かを示す伝送レートの許容性を判定する伝送レート許容性判定装置により実行される伝送レート許容性判定方法であって、
前記伝送レート許容性判定装置は、対象となるネットワークを表す非周期有効グラフG、各伝送路のレート制限Ｒ、および各終端ノードが受け取るべきメッセージのインデックスKTを記憶する記憶手段を備えており、
各メッセージの伝送レートωを入力する入力ステップと、
ノードの集合V及び伝送路に対応する辺の集合Eからなる非周期有効グラフG、レート制限Ｒ、メッセージのインデックスKT、及び伝送レートωの各値を前記記憶手段から読み出し、所定の複数の拘束条件に代入し、当該複数の拘束条件を満足するフロー変数ζ(Λ)e（for e∈E,Λ∈2K、Λは各辺のサブチャンネルのインデックス）の解の有無を線形計画法を用いて判定する伝送レート許容性判定処理ステップと、
前記伝送レート許容性判定処理ステップでの判定結果に基づき、入力された伝送レートが許容か否かを示す情報を出力する出力ステップと
を備えることを特徴とする伝送レート許容性判定方法。
【請求項４】
前記複数の拘束条件は、
【数５】
【数６】
（ただし、fin(e)=vは有向辺eの終端ノードがｖであることを示し、ini(e)=vは有向辺eの開始ノードがｖであることを示す。）
【数７】
【数８】
の４つの条件式で表わされる条件であることを特徴とする請求項３に記載の伝送レート許容性判定方法。
【請求項５】
コンピュータを、請求項１又は２に記載の伝送レート許容性判定装置の各手段として機能させるためのプログラム。
【請求項１】
伝送レートが制限された複数の伝送路から構成され、ネットワーク符号化を行うネットワークにおいて、複数のメッセージを複数の終端ノードに対して伝送する際に、与えられた伝送レートで各メッセージを伝送することが可能か否かを示す伝送レートの許容性を判定する伝送レート許容性判定装置であって、
対象となるネットワークを表す非周期有効グラフG、各伝送路のレート制限Ｒ、および各終端ノードが受け取るべきメッセージのインデックスKTを記憶する記憶手段と、
各メッセージの伝送レートωを入力する入力手段と、
ノードの集合V及び伝送路に対応する辺の集合Eからなる非周期有効グラフG、レート制限Ｒ、メッセージのインデックスKT、及び伝送レートωの各値を前記記憶手段から読み出し、所定の複数の拘束条件に代入し、当該複数の拘束条件を満足するフロー変数ζ(Λ)e（for e∈E,Λ∈2K、Λは各辺のサブチャンネルのインデックス）の解の有無を線形計画法を用いて判定する伝送レート許容性判定処理手段と、
前記伝送レート許容性判定処理手段の判定結果に基づき、入力された伝送レートが許容か否かを示す情報を出力する出力手段と
を備えることを特徴とする伝送レート許容性判定装置。
【請求項２】
前記複数の拘束条件は、
【数１】
【数２】
（ただし、fin(e)=vは有向辺eの終端ノードがｖであることを示し、ini(e)=vは有向辺eの開始ノードがｖであることを示す。）
【数３】
【数４】
の４つの条件式で表わされる条件であることを特徴とする請求項１に記載の伝送レート許容性判定装置。
【請求項３】
伝送レートが制限された複数の伝送路から構成され、ネットワーク符号化を行うネットワークにおいて、複数のメッセージを複数の終端ノードに対して伝送する際に、与えられた伝送レートで各メッセージを伝送することが可能か否かを示す伝送レートの許容性を判定する伝送レート許容性判定装置により実行される伝送レート許容性判定方法であって、
前記伝送レート許容性判定装置は、対象となるネットワークを表す非周期有効グラフG、各伝送路のレート制限Ｒ、および各終端ノードが受け取るべきメッセージのインデックスKTを記憶する記憶手段を備えており、
各メッセージの伝送レートωを入力する入力ステップと、
ノードの集合V及び伝送路に対応する辺の集合Eからなる非周期有効グラフG、レート制限Ｒ、メッセージのインデックスKT、及び伝送レートωの各値を前記記憶手段から読み出し、所定の複数の拘束条件に代入し、当該複数の拘束条件を満足するフロー変数ζ(Λ)e（for e∈E,Λ∈2K、Λは各辺のサブチャンネルのインデックス）の解の有無を線形計画法を用いて判定する伝送レート許容性判定処理ステップと、
前記伝送レート許容性判定処理ステップでの判定結果に基づき、入力された伝送レートが許容か否かを示す情報を出力する出力ステップと
を備えることを特徴とする伝送レート許容性判定方法。
【請求項４】
前記複数の拘束条件は、
【数５】
【数６】
（ただし、fin(e)=vは有向辺eの終端ノードがｖであることを示し、ini(e)=vは有向辺eの開始ノードがｖであることを示す。）
【数７】
【数８】
の４つの条件式で表わされる条件であることを特徴とする請求項３に記載の伝送レート許容性判定方法。
【請求項５】
コンピュータを、請求項１又は２に記載の伝送レート許容性判定装置の各手段として機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１１−２５４３２７（Ｐ２０１１−２５４３２７Ａ）
【公開日】平成２３年１２月１５日（２０１１．１２．１５）
【国際特許分類】
【出願番号】特願２０１０−１２７１７９（Ｐ２０１０−１２７１７９）
【出願日】平成２２年６月２日（２０１０．６．２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（５０４１３７９１２）国立大学法人 東京大学 (1,942)
【Ｆターム（参考）】
【公開日】平成２３年１２月１５日（２０１１．１２．１５）
【国際特許分類】
【出願日】平成２２年６月２日（２０１０．６．２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（５０４１３７９１２）国立大学法人 東京大学 (1,942)
【Ｆターム（参考）】
[ Back to top ]