データ伝送方法および通信システム
【課題】セキュリティの高いデータ伝送を行うことができるデータ伝送方法を得ること。
【解決手段】送信情報を生成するソースノードと送信情報の宛先ノードまたは中継ノードである一般ノードとで構成される通信システムにおいて、ソースノードおよび一般ノードで符号化を行う場合のデータ伝送方法であって、ソースノードを始点とし一般ノードを終点とする独立経路の数の最大値を求めるステップ（Ｓ１２）と、送信情報および符号化に用いる行列の各要素を構成要素とする集合の大きさを設定するステップ（Ｓ１１）と、前記最大値と前記大きさに基づいて盗聴に対する頑健性を示す盗聴頑健性指標を算出するステップ（Ｓ１３）と、前記盗聴頑健性指標に基づいて通信システムのセキュリティに関するパラメータを設定するステップと、を含む。
【解決手段】送信情報を生成するソースノードと送信情報の宛先ノードまたは中継ノードである一般ノードとで構成される通信システムにおいて、ソースノードおよび一般ノードで符号化を行う場合のデータ伝送方法であって、ソースノードを始点とし一般ノードを終点とする独立経路の数の最大値を求めるステップ（Ｓ１２）と、送信情報および符号化に用いる行列の各要素を構成要素とする集合の大きさを設定するステップ（Ｓ１１）と、前記最大値と前記大きさに基づいて盗聴に対する頑健性を示す盗聴頑健性指標を算出するステップ（Ｓ１３）と、前記盗聴頑健性指標に基づいて通信システムのセキュリティに関するパラメータを設定するステップと、を含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信装置（以下、ノードという）を通信路（以下、リンクという）で接続した有線または無線のネットワークにおいて、発信元ノードから宛先ノードに向けて情報を伝送するデータ伝送方法に関する。
【背景技術】
【０００２】
ノードをリンクで接続したネットワークで、発信元ノードから宛先ノードに向けて情報を伝送する場合、従来の一般のパケット通信では、伝送経路上の各ノードは入力情報を所望の宛先に向けて出力する交換処理を行っていた。交換処理では、パケットを宛先に向けて振り分けるだけで、パケット内のユーザ情報に処理を施すことはなかった。
【０００３】
これに対し、たとえば、ネットワークコーディング技術では、各ノードで交換だけでなく、コーディング（符号化）も行ない、ネットワーク全体として効率的な伝送ができるように工夫している（たとえば、下記非特許文献１、２および３参照）。
【０００４】
ネットワークコーディングの第１の特長は、伝送の効率化すなわち帯域等の通信資源の有効利用であるが、もう１つの特長は、情報秘匿性の向上である。従来の一般の通信では、発信元から宛先にいたる途中のリンクやノードでは、送信したユーザ情報がそのまま伝送されているのに対し、ネットワークコーディングでは各ノードでコーディング処理が施されている。このため、外部の者が途中の情報を盗聴しても、盗聴した情報は内容の全くわからない一種の暗号であり、セキュリティが確保される。
【０００５】
【非特許文献１】R. Ahlswede et. Al.， “Network information flow”, IEEE trans. on Information Theory， Vol. 46， no. 4， July， 2000， pp． 1204-1216
【非特許文献２】山本幹，“ネットワークコーディング”，電子情報通信学会誌， Vol.90，No.2，2007年2月，pp.111−116
【非特許文献３】S-Y. R. Li et. al.， “Linear network coding”， vol. 49， no.2， Feb. 2003， pp. 371-381
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記従来のネットワークコーティングの技術によれば、このセキュリティ（安全性）の度合いについて定量的に評価されていなかった。そのため、安全性の低い符号化が行われているかどうかが判別できず、その通信システムに必要な安全性が確保されているとは限らない、という問題があった。
【０００７】
本発明は、上記に鑑みてなされたものであって、ネットワークコーティング技術を用いたデータ伝送において、高いセキュリティを確保することができるデータ伝送方法および通信システムを得ることを目的とする。
【課題を解決するための手段】
【０００８】
上述した課題を解決し、目的を達成するために、本発明は、送信情報を生成するソースノードと前記送信情報の宛先ノードまたは前記送信情報を中継する中継ノードである一般ノードとで構成される通信システムにおいて、前記ソースノードおよび前記一般ノードで符号化を行ってデータを伝送する場合のデータ伝送方法であって、前記ソースノードを始点とし前記一般ノードを終点とする独立経路の数の最大値を求める独立経路最大値算出ステップと、前記送信情報および符号化に用いる行列の各要素を構成要素とする集合の大きさを設定する集合設定ステップと、前記最大値と前記大きさに基づいて盗聴に対する頑健性を示す盗聴頑健性指標を算出する盗聴頑健性指標算出ステップと、前記盗聴頑健性指標に基づいて通信システムのセキュリティに関するパラメータを設定するパラメータ設定ステップと、を含むことを特徴とする。
【発明の効果】
【０００９】
この発明によれば、通信システムを構成する各ノードで符号化を行い、独立経路の最大値と通信システムで送信するデータの要素の集合の大きさに基づいて盗聴頑健性の指標を算出し、盗聴頑健性の指標が所定の閾値より大きくなるか否かによって安全性を判定して、安全性が所定の閾値より高くなるようにしたので、セキュリティの高いデータ伝送を行うことができる、という効果を奏する。
【発明を実施するための最良の形態】
【００１０】
以下に、本発明にかかるデータ伝送方法および通信システムの実施の形態を図面に基づいて詳細に説明する。なお、この実施の形態によりこの発明が限定されるものではない。
【００１１】
実施の形態１．
図１は、本発明にかかる通信システムの実施の形態１の構成例を示す図である。図１に示すように、本実施の形態の通信システムは、通信装置であるノード１−１〜１−８で、構成され、図中の矢印は、ノード間をつなぐ通信路であるリンクＬを示している。本実施の形態では、図１のように、各ノード１−１〜１−８が、通信方向が規定されたリンクＬで結ばれているとし、矢印の向きが通信方法を示す。たとえば、リンクＬ１は、ノード１−３からノード１−４へ向かうリンクを示している。すなわち、リンクＬ１はノード１−３をノード１−４へつなげているが、ノード１−４をノード１−３へはつなげていない。
【００１２】
図２は、本実施の形態が想定しない通信システムの一例を示す図である。本実施の形態では、図２に示すように、たとえば、ノード１−１からリンクＬの向きに沿ってすすむと１周してもとのノード１−１に戻るような巡回路が存在する通信システムについては、想定の対象としないこととする。
【００１３】
図３は、本実施の形態の通信システムの別の構成例を示す図である。図３の例を用いて、本実施の形態の処理手順を説明することとする。図３の例では、最初に情報の送信元となるソースノード２と、ソースノード以外の一般ノード（情報の宛先となるノードまたは情報の中継を行うノード）であるノード１−１〜１−１２と、で構成される。ここで、ソースノード２から各ノードへの独立経路の数を数える。独立経路とは、始点のノードから終点のノードまで、それぞれの経路が同一のリンクＬを含まない経路である。たとえば、始点のノードをソースノード２とし、終点のノードをノード１−３とする。このとき、独立経路は、ノード１−１，１−３を経由する経路ＲＴ１と、ノード１−４を経由する経路ＲＴ２と、ノード１−７，１−６を経由する経路ＲＴ３と、の合計３つである。
【００１４】
ソースノード２を始点としノード１−１〜１−１２を終点とする独立経路の数を、終点ノード１−１〜１−１２ごとに数え、そのうちの最大値をｄとする。たとえば、図３の場合、終点をノード１−９とするときに独立経路の数が最大となり、ｄ＝４である。
【００１５】
つづいて、本実施の形態の符号化について説明する。整数Ｚを素数ｐで割った余りの集合をＫとする。このＫでは、加減乗除が自由にできる。Ｋは任意の有限体（加減乗除ができる集合で要素が有限個のもの）でよいが、ここでは簡単のため次のように仮定する。集合Ｋのサイズ（集合の要素の数）をｋとする。Ｋは整数Ｚをｐで割った余りであるから、ｋの値はｐと同一である。これを式で示すと、以下の式（１）のようになる。
Ｋ＝｛ｘ｜ｘ＝ｍｏｄ（Ｚ，ｐ）｝＝｛０，１，２，・・・，ｐ−１｝ ・・・（１）
【００１６】
以下、説明を簡単にするため、ｐ＝２とする。このＫの要素を成分とするｄ次元ベクトルを、本実施の形態の符号化の単位とする。すなわち送信すべきデータを数値化して、Ｋの要素を成分とするｄ次元ベクトル１本を単位として、符号化（暗号化）したものを送信する。
【００１７】
図４は、データ送信の始点であるソースノード２から送信される送信データを示す図である。図中のベクトル３−１〜３−３は、それぞれＫの要素である元ＫＧを成分とするｄ次元のベクトルである。以下、このベクトル３−１〜３−３のようなｄ次元ベクトルのうちの１つ示す場合、ベクトル３と表記する。この場合は、Ｋの要素の数ｐ＝２個であるため、ＫＧは０または１の２値である。図４に示すように、ソースノード２は、まず、１本目のベクトル３−１を送信し、２本目のベクトル３−２を送信し、というようにｄ次元ベクトルを単位として送信される。各ベクトルの要素は、それぞれのｄ本の独立経路に送信される。
【００１８】
つづいて、ソースノード２での符号化について説明する。図５は、本実施の形態のソースノード２を始点とするリンクＬの一例を示す図である。図５に示すように、ここでは、ソースノード２を始点とするｓ本のリンクＬが存在するとする。このとき、ソースノード２では、最初にＫの任意の要素を成分とする送信情報であるｄ次元ベクトルＶＳ１に、ｓ行ｄ列の行列ＭＳ１を乗じた結果をソースノード２から各リンクＬへ送出するデータＶＳＤ１とし、ＶＳＤ１を符号化されたベクトル３として算出する。そして、算出したベクトル３の各成分をｄ本の独立経路に対応するリンクＬにそれぞれ送出する。ｐ＝２，ｄ＝３，ｓ＝４とした場合のＶＳＤ１の一例を、以下の式（２）に示す。
【００１９】
【数１】
【００２０】
なお、上記の式（２）のＭＳ１は一例であり、ＭＳ１は、これに限らず、Ｋの要素を成分とするｓ行ｄ列の行列であればよい。
【００２１】
つづいて、ノード１−ｎ（ｎはノード番号を示す自然数）での符号化について説明する。図６は、ノード１−ｎに入ってくるリンクＬの数をｌ本とし、ノード１−ｎから出て行くリンクＬの数をｓ本とした場合のノード１−ｎとリンクＬの関係の一例を示す図である。このとき、ｌ本のリンクＬをそれぞれリンクＬの接続元であるノードからデータが流れてくる。ソースノード２から送信される各データは、前述のとおりＫの元であり、後述のように各ノードはＫの元を送信するため、ノード１−ｎに入ってくるリンクＬを流れるデータは、Ｋの元である。ここで、ノード１−ｎにはいってくる各リンクＬからのデータをｌ次元ベクトルＶＴ２と表すこととする。ノード１−ｎは、ＶＴ２にｓ行ｌ列の行列ＭＴをかけて得られるｓ次元ベクトルＶＴＤ２の成分をそれぞれ、ノード１−ｎから出ていくリンクＬに送出する。ｐ＝２，ｌ＝４，ｓ＝２とした場合のＶＳＤ２の一例を、以下の式（３）に示す。
【００２２】
【数２】
【００２３】
なお、上記の式（２）のＭＴは一例であり、ＭＴは、これに限らず、Ｋの要素を成分とするｓ行ｄ列の行列であればよい。本実施の形態では、巡回する経路がネットワーク上にないと仮定しているので、この繰り返しによって順々に、各リンクＬを流れるデータが決まっていく。
【００２４】
以上のように、ソースノード２およびノード１−ｎの処理繰り返して、あらかじめ決められた宛先のノードにデータが到達する。このような符号化を行う場合、盗聴者から守るべき対象は、各リンクＬを流れる個々のデータではなく、各ノードで行う符号化の方法、すなわち行列ＭＳ１およびＭＴである。各リンクＬを流れるデータをすべて盗聴されたとしても、各ノードが行っている符号化の方法が察知されなければ、元の送信情報は保護されるため、セキュリティの観点から評価する場合、符号化の方法が察知されることをできるだけ防いで察知されるまでの時間を引き伸ばすことが望ましい。
【００２５】
このため、以下では、上述のような符号化を行う場合に、盗聴者が符号化の方法、すなわち行列ＭＳ１およびＭＴ、を盗む際には平均何回の盗聴が必要かということを考える。本実施の形態では、この回数を盗聴頑健性の指標として定義して、セキュリティ（安全性）の高さを判定する。具体的には、盗聴頑健性の指標Ｆ（ｋ，ｄ）は以下の式（４）で表すことができる。
【００２６】
【数３】
【００２７】
この値が、所定の閾値より上ならば、盗聴に対して十分に頑健であると判定し、そうでなければ盗聴に対して弱いと判定する。図７は、盗聴頑健性の判定を行う手順の一例を示す図である。まず、集合Ｋを決定する、すなわち、ｐを決定する（ステップＳ１１）。つぎに、ソースノード２からノード１−ｎへの独立経路のうちの最大値ｄを求める（ステップＳ１２）。そして、ｄとｐに基づいて式（４）に従って盗聴頑健性の指標を求める（ステップＳ１３）。つぎに、ステップＳ１３で求めた盗聴頑健性の指標が所定の閾値より大きいか否かを判定し（ステップＳ１４）、閾値より大きい場合（ステップＳ１４ Ｙｅｓ）は盗聴に強い、すなわち安全性が高いと判定する（ステップＳ１５）。閾値より小さい場合（ステップＳ１４ Ｎｏ）は、盗聴に弱い、すなわち安全性が低いと判定する（ステップＳ１６）。
【００２８】
以上の手順を行うことにより、決定した集合Ｋについて、安全性を判定することができる。この判定を、たとえば、ソースノード２またはノード１−ｎで行い、安全性が高いと判定されるようにＫを決定し、決定したＫを全てのノード（ソースノード２およびノード１−ｎ）に通知するようにすれば、安全性の高い符号化を行うことができる。また、あらかじめ、本実施の形態の通信システム外の手段（他の計算機など）により、この判定を行って、判定結果をもとに安全性が高くなるようにＫを決定しておき、それを各ノードに設定するようにしてもよい。
【００２９】
また、Ｋに別の制約があり、安全性が高くなるようにＫを決定することができない場合には、安全性が低いことを考慮して通信システム内の安全性に関連する他のパラメータを調整するなどの他の対策を講じることにより安全性を確保ようにしてもよい。
【００３０】
なお、上記式（４）の盗聴頑健性の指標は、各リンクＬを流れるデータをすべて盗聴された場合を考慮して導入した計算式であるが、式（４）の指標は以下に示すようなケースを考慮した場合にも使用可能である。図８は、他の盗聴方法を考慮した場合を説明するための通信システムの一例を示す図である。図８では、破線は、その間のノード１−ｎとリンクＬの接続を省略していることを示している。
【００３１】
盗聴者は、ソースノード２から送信される送信情報であるデータ、すなわちｄ次元ベクトルと、ある特定のリンクＬＴ流れるデータ、すなわちＫの元を盗聴すると仮定する。この盗聴を１セットとする盗聴を何回か繰り返し、もとの送信情報であるｄ次元ベクトルとリンクＬを流れるデータの関係を盗み出したいとする。この場合に、この関係を明らかにするために、そのような盗聴を平均何回（何セット）しなければならないか、という指標を盗聴頑健性の指標とする場合にも、式（４）で示したのと同様となる。つまり、行列行列ＭＳ１およびＭＴを盗聴すると仮定した場合だけでなく、ｄ次元ベクトルと、リンクＬ流れるデータを盗聴すると仮定した場合にも式（４）の盗聴頑健性の指標を用いることができる。
【００３２】
このように、本実施の形態では、通信システムを構成する各ノードで符号化を行い、独立経路の最大値ｄと通信システムで送信するデータの要素の集合Ｋの大きさに基づいて盗聴頑健性の指標を算出し、盗聴頑健性の指標が所定の閾値より大きくなるか否かによって安全性を判定するようにした。このため、盗聴頑健性の指標が所定の閾値より大きくようにＫを決定することで、安全性の高いデータ伝送を行うことができる。
【００３３】
実施の形態２．
実施の形態１では、盗聴頑健性の指標に基づいて安全性の評価ができるデータ伝送方法について述べたが、本実施の形態では、実施の形態１の符号化方法では、符号化に用いる行列の要素の値によっては生のデータが流れる場合がある。データ全体の盗聴や暗号化の仕組み全体を盗聴することが困難であったとしても、一部でも暗号化されていない生のデータがネットワーク上を流れることは好ましくない。たとえば、クレジットカード番号の一部がそのまま流れるようなことは防ぐことが望ましい。本実施の形態では、ネットワーク上を生のデータが流れることをできるだけ防ぐ新たな符号化方法について述べる。なお、本実施の形態の通信システムの構成は実施の形態１と同様である。
【００３４】
実施の形態１の符号化方法では、ノード１−ｎに入ってくるデータに対し行列ＭＴを乗算した。この行列は、出力先のリンクＬにそれぞれ対応する１行のｄ次元横ベクトルがリンクＬの数だけ縦に並んでいる行列と考えることができる。すなわち、ソースノード２における最初の送信情報であるデータを与えるｄ次元縦ベクトルＶＳ１とある特定のリンクＬを流れるデータ（Ｋの元）との対応について注目すると、ＶＳ１に対し、リンクＬごとにｄ次元横ベクトルを乗算していると考えることができる。このように考えたときのｄ次元横ベクトルを符号化ベクトルＥＣＶＴと呼ぶこととする。図９は、ｄ＝４とした場合の符号化ベクトルＥＣＶＴの一例を示す図である。本実施の形態では、リンクＬ毎に、符号化ベクトルを決定すると考えて、その符号化ベクトルの要素の選び方を工夫することで生のデータの一部がネットワーク上を流れることを防ぐ。
【００３５】
図１０は、本実施の形態の符号化方法を説明するための通信システムの一例を示す図である。まず、ノードに番号をつける。ここでは、図１０の各ノードに付した符号の枝番号をノード番号とし、各リンクＬはノード番号の少ないほうから多い方に向かっているとする。本実施の形態では、実施の形態１と同様にネットワーク内に巡回経路と家庭するため、このような番号付けが可能である。そして、始点となるノードから始めて、順にノード番号の小さい順にリンクＬごとに符号化ベクトルを選んでいく。
【００３６】
ノード１−ｎを始点に持つリンクＬの符号化ベクトルＥＣＶＴは、次のように選ぶ。まず、ノード１−ｎに入ってくるリンクＬの持つリンクＬの個数分の符号化ベクトルＥＣＶＴの１次結合で得られるベクトルのなす線形結合Ｖを考える。２つの符号化ベクトルＥＣＶＴの１次結合で得られる線形結合Ｖは、たとえば、２つの符号化ベクトルＥＣＶＴを含む平面となる。上記非特許文献３では、この線形空間Ｖの中から、「一般的」なベクトルを選べば、最大効率が達成できると示されている。
【００３７】
本実施の形態では、この「一般的」なベクトルを選ぶステップで新たな条件を追加することにより、生のデータの一部がネットワーク上を流れることを防ぐ。まず、ｄ次元の第ｊ成分だけが１で残りの成分がすべて０であるベクトルをｅｊとする。あるノード１−ｎに入ってくるリンクＬの本数をｔとする。このリンクＬにそれぞれ対応するｔ本の符号化ベクトルの張る部分空間をＶとする。ノード１−ｎよりノード番号の若いノードから出るリンクＬの符号化ベクトルとしてすでに決定された符号化ベクトルのなかから（ｄ−１）本以下のベクトルを選ぶ。この本数がちょうど（ｄ−１）本でないときは、ｅｊを一つ選ぶ。このとき、ｔ本の符号化ベクトルとｅｊの張る部分空間をＷとする。ＷがＶを含んでいるときはそのＷは捨てる。また、選んだ符号化ベクトルがちょうど（ｄ−１）本のときは、それらの張る部分空間をＷとする。やはりＷがＶを含んでいるときはそのＷは捨てる。（ｄ−１）本以下の符号化ベクトルとｅｊをどのように選んだとしても、それらの張るＷに含まれないＶの元を、ノード１−ｎから出るリンクＬの符号化ベクトルとする。
【００３８】
図１１−１，１１−２は本実施の形態の符号化ベクトルの選択手順の一例をリンク１本分について示したフローチャートである。まず、ノード１−ｎに入ってくるｔ本のリンクＬの符号化ベクトルの張る部分空間Ｖを求める（ステップＳ２１）。つぎに、よけるべき部分空間の集合Ｘを空集合におく（ステップＳ２２）。そして、ノード１−ｎよりノード番号の若いノードから出るリンクＬの符号化ベクトルとしてすでに決定された符号化ベクトルの中から、（ｄ−１）本以下の組合せを選択する（ステップＳ２３）。このとき、２回目以降のステップＳ２３の実行の場合（ステップＳ３３から戻ってステップＳ２３を実行した場合）には、それ以前のステップＳ２３で選ばれていない組み合わせを除いて選択する。
【００３９】
つぎに、選んだ符号化ベクトルの本数が（ｄ−１）本であるかを判定する（ステップＳ２４）。選んだ符号化ベクトルの本数が（ｄ−１）本の場合（ステップＳ２４ Ｙｅｓ）は、ステップＳ３０に進む。選んだ符号化ベクトルの本数が（ｄ−１）本でない場合（ステップＳ２４ Ｎｏ）には、１本のｅｊを選択する（ステップＳ２５）。このとき、２回以降のステップＳ２５の実行の場合は、それ以前のステップＳ２５で選んでいないｅｊのうちから１本を選択する（ステップＳ２５）。
【００４０】
つぎに、ステップＳ２３で選んだ符号化ベクトルとステップＳ２５で選択したｅｊの張る空間をＷとする。つぎに、ＶがＷに含まれるかを判定する（ステップＳ２７）。ＶがＷに含まれると判定した場合（ステップＳ２７ Ｙｅｓ）には、ステップＳ２９に進み、ＶがＷに含まれないと判定した（ステップＳ２７ Ｎｏ）場合にはステップＳ２８に進む（ステップＳ２８）。ステップＳ２８では、ＷをＸに追加する。
【００４１】
ステップＳ２９では、ステップＳ２５でまだ選んでいないｅｊがあるかを判定する。選んでいないｅｊがまだあると判定した場合（ステップＳ２９ Ｙｅｓ）には、ステップＳ２５に戻る。選んでいないｅｊがない（すべてのｅｊが既に選ばれた）と判定した場合（ステップＳ２９ Ｎｏ）には、ステップＳ３０に進む。つぎに、ステップＳ２３で選んだ符号化ベクトルの張る空間をＷとする（ステップＳ３０）。そして、ＶがＷに含まれるかを判定する（ステップＳ３１）。ＶがＷに含まれる場合（ステップＳ３１ Ｙｅｓ）には、ステップＳ３３に進む。ＶがＷに含まれない場合（ステップＳ３１ Ｎｏ）には、ＷをＸに追加する（ステップＳ３２）。
【００４２】
つぎに、ステップＳ３３で、すでに選んだ符号化ベクトルの中から（ｄ−１）本以下の組合せを選ぶ方法がまだあるかを判定する（ステップＳ３３）。まだ選ぶ方法がある場合（ステップＳ３３ Ｙｅｓ）には、ステップＳ２３に戻る。もう選ぶ方法がない場合（すでに選んだ符号化ベクトルのなかから、（ｄ−１）本以下のすべての組み合わせの選択が終了した）場合は、Ｘに含まれるどのＷにも入らない符号化ベクトルをＶの中から選び、対応するリンクＬの符号化ベクトルとする（ステップＳ３４）。
【００４３】
そして、以上の処理をノード１−ｎから出るすべてのリンクＬについて実行すればよい。図１２は、通信システム全体のノード（ソースノード２およびノード１−ｎ）の処理手順の一例を示すフローチャートである。まず、まだ符号化ベクトル処理を行っていないノードのなかから符号化ベクトル処理の対象とするノードを選択する（ステップＳ４１）。そして、選択したノードから出るリンクのうち、符号化ベクトルの選択が終了していないリンクＬを１つ選択する（ステップＳ４２）。つぎに、選択したリンクＬについて図１１−１，図１１−２で説明した処理により符号化ベクトルを選ぶ（ステップＳ４３）。そして、選択したノードから出るリンクのうち、符号化ベクトルが選ばれていないリンクがまだあるかを判定する（ステップＳ４４）。符号化ベクトルが選ばれていないリンクがまだある場合（ステップＳ４４ Ｙｅｓ）には、ステップＳ４２に戻る。符号化ベクトルが選ばれていないリンクがない場合（ステップＳ４４ Ｎｏ）には、まだ符号化ベクトル処理を行っていないノードがあるか否かを判断する（ステップＳ４５）。
【００４４】
符号化ベクトル処理を行っていないノードがあると判断した場合（ステップＳ４５ Ｙｅｓ）にステップＳ４２に戻る。符号化ベクトル処理を行っていないノードがないと判断した場合（ステップＳ４５ Ｎｏ）は、処理を終了する。
【００４５】
このようにしてすべてのノードについて、そのノードから出るリンクＬについての符号化ベクトルを決定する。なお、この決定処理を通信システム内の特定のノードで行い、符号化ベクトルを対応するノードにそれぞれ通知するようにしてもよいし、通信システム外の別の計算機などで符号化ベクトルを算出して、各ノードに設定するようにしてもよい。
【００４６】
以上のように、本実施の形態では、ＷがＶに含まれる場合には、そのＷをすて、すべてのｅｊについてＷがＶに含まれないように符号化ベクトルを選択するようにした。このため実施の形態１の効果に加え、ネットワーク上を生のデータができるだけ流れないようにすることができ、秘匿性・安全性がさらに向上する。
【産業上の利用可能性】
【００４７】
以上のように、本発明にかかるデータ伝送方法および通信システムは、ネットワークコーディングを採用する通信システムに有用であり、特に、高いセキュリティを要求される通信システムに適している。
【図面の簡単な説明】
【００４８】
【図１】本発明にかかる通信システムの実施の形態１の構成例を示す図である。
【図２】本発明で想定しない通信システムの一例を示す図である。
【図３】実施の形態１の通信システムの別の構成例を示す図である。
【図４】ソースノードから送信される送信データを示す図である。
【図５】ソースノードを始点とするリンクＬの一例を示す図である。
【図６】ノードとリンクの関係の一例を示す図である。
【図７】盗聴頑健性の判定を行う手順の一例を示す図である。
【図８】他の盗聴方法を考慮した場合を説明するための通信システムの一例を示す図である。
【図９】符号化ベクトルの一例を示す図である。
【図１０】実施の形態２の符号化方法を説明するための通信システムの一例を示す図である。
【図１１−１】符号化ベクトルの選択手順の一例をリンク１本分について示したフローチャートである。
【図１１−２】符号化ベクトルの選択手順の一例をリンク１本分について示したフローチャートである。
【図１２】ネットワーク全体の処理手順の一例を示すフローチャートである。
【符号の説明】
【００４９】
１，１−１〜１−８ ノード
２ ソースノード
３−１〜３−３ ベクトル
ＲＴ１，ＲＴ２，ＲＴ３ 経路
Ｌ，Ｌ１，ＬＴ リンク
【技術分野】
【０００１】
本発明は、通信装置（以下、ノードという）を通信路（以下、リンクという）で接続した有線または無線のネットワークにおいて、発信元ノードから宛先ノードに向けて情報を伝送するデータ伝送方法に関する。
【背景技術】
【０００２】
ノードをリンクで接続したネットワークで、発信元ノードから宛先ノードに向けて情報を伝送する場合、従来の一般のパケット通信では、伝送経路上の各ノードは入力情報を所望の宛先に向けて出力する交換処理を行っていた。交換処理では、パケットを宛先に向けて振り分けるだけで、パケット内のユーザ情報に処理を施すことはなかった。
【０００３】
これに対し、たとえば、ネットワークコーディング技術では、各ノードで交換だけでなく、コーディング（符号化）も行ない、ネットワーク全体として効率的な伝送ができるように工夫している（たとえば、下記非特許文献１、２および３参照）。
【０００４】
ネットワークコーディングの第１の特長は、伝送の効率化すなわち帯域等の通信資源の有効利用であるが、もう１つの特長は、情報秘匿性の向上である。従来の一般の通信では、発信元から宛先にいたる途中のリンクやノードでは、送信したユーザ情報がそのまま伝送されているのに対し、ネットワークコーディングでは各ノードでコーディング処理が施されている。このため、外部の者が途中の情報を盗聴しても、盗聴した情報は内容の全くわからない一種の暗号であり、セキュリティが確保される。
【０００５】
【非特許文献１】R. Ahlswede et. Al.， “Network information flow”, IEEE trans. on Information Theory， Vol. 46， no. 4， July， 2000， pp． 1204-1216
【非特許文献２】山本幹，“ネットワークコーディング”，電子情報通信学会誌， Vol.90，No.2，2007年2月，pp.111−116
【非特許文献３】S-Y. R. Li et. al.， “Linear network coding”， vol. 49， no.2， Feb. 2003， pp. 371-381
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記従来のネットワークコーティングの技術によれば、このセキュリティ（安全性）の度合いについて定量的に評価されていなかった。そのため、安全性の低い符号化が行われているかどうかが判別できず、その通信システムに必要な安全性が確保されているとは限らない、という問題があった。
【０００７】
本発明は、上記に鑑みてなされたものであって、ネットワークコーティング技術を用いたデータ伝送において、高いセキュリティを確保することができるデータ伝送方法および通信システムを得ることを目的とする。
【課題を解決するための手段】
【０００８】
上述した課題を解決し、目的を達成するために、本発明は、送信情報を生成するソースノードと前記送信情報の宛先ノードまたは前記送信情報を中継する中継ノードである一般ノードとで構成される通信システムにおいて、前記ソースノードおよび前記一般ノードで符号化を行ってデータを伝送する場合のデータ伝送方法であって、前記ソースノードを始点とし前記一般ノードを終点とする独立経路の数の最大値を求める独立経路最大値算出ステップと、前記送信情報および符号化に用いる行列の各要素を構成要素とする集合の大きさを設定する集合設定ステップと、前記最大値と前記大きさに基づいて盗聴に対する頑健性を示す盗聴頑健性指標を算出する盗聴頑健性指標算出ステップと、前記盗聴頑健性指標に基づいて通信システムのセキュリティに関するパラメータを設定するパラメータ設定ステップと、を含むことを特徴とする。
【発明の効果】
【０００９】
この発明によれば、通信システムを構成する各ノードで符号化を行い、独立経路の最大値と通信システムで送信するデータの要素の集合の大きさに基づいて盗聴頑健性の指標を算出し、盗聴頑健性の指標が所定の閾値より大きくなるか否かによって安全性を判定して、安全性が所定の閾値より高くなるようにしたので、セキュリティの高いデータ伝送を行うことができる、という効果を奏する。
【発明を実施するための最良の形態】
【００１０】
以下に、本発明にかかるデータ伝送方法および通信システムの実施の形態を図面に基づいて詳細に説明する。なお、この実施の形態によりこの発明が限定されるものではない。
【００１１】
実施の形態１．
図１は、本発明にかかる通信システムの実施の形態１の構成例を示す図である。図１に示すように、本実施の形態の通信システムは、通信装置であるノード１−１〜１−８で、構成され、図中の矢印は、ノード間をつなぐ通信路であるリンクＬを示している。本実施の形態では、図１のように、各ノード１−１〜１−８が、通信方向が規定されたリンクＬで結ばれているとし、矢印の向きが通信方法を示す。たとえば、リンクＬ１は、ノード１−３からノード１−４へ向かうリンクを示している。すなわち、リンクＬ１はノード１−３をノード１−４へつなげているが、ノード１−４をノード１−３へはつなげていない。
【００１２】
図２は、本実施の形態が想定しない通信システムの一例を示す図である。本実施の形態では、図２に示すように、たとえば、ノード１−１からリンクＬの向きに沿ってすすむと１周してもとのノード１−１に戻るような巡回路が存在する通信システムについては、想定の対象としないこととする。
【００１３】
図３は、本実施の形態の通信システムの別の構成例を示す図である。図３の例を用いて、本実施の形態の処理手順を説明することとする。図３の例では、最初に情報の送信元となるソースノード２と、ソースノード以外の一般ノード（情報の宛先となるノードまたは情報の中継を行うノード）であるノード１−１〜１−１２と、で構成される。ここで、ソースノード２から各ノードへの独立経路の数を数える。独立経路とは、始点のノードから終点のノードまで、それぞれの経路が同一のリンクＬを含まない経路である。たとえば、始点のノードをソースノード２とし、終点のノードをノード１−３とする。このとき、独立経路は、ノード１−１，１−３を経由する経路ＲＴ１と、ノード１−４を経由する経路ＲＴ２と、ノード１−７，１−６を経由する経路ＲＴ３と、の合計３つである。
【００１４】
ソースノード２を始点としノード１−１〜１−１２を終点とする独立経路の数を、終点ノード１−１〜１−１２ごとに数え、そのうちの最大値をｄとする。たとえば、図３の場合、終点をノード１−９とするときに独立経路の数が最大となり、ｄ＝４である。
【００１５】
つづいて、本実施の形態の符号化について説明する。整数Ｚを素数ｐで割った余りの集合をＫとする。このＫでは、加減乗除が自由にできる。Ｋは任意の有限体（加減乗除ができる集合で要素が有限個のもの）でよいが、ここでは簡単のため次のように仮定する。集合Ｋのサイズ（集合の要素の数）をｋとする。Ｋは整数Ｚをｐで割った余りであるから、ｋの値はｐと同一である。これを式で示すと、以下の式（１）のようになる。
Ｋ＝｛ｘ｜ｘ＝ｍｏｄ（Ｚ，ｐ）｝＝｛０，１，２，・・・，ｐ−１｝ ・・・（１）
【００１６】
以下、説明を簡単にするため、ｐ＝２とする。このＫの要素を成分とするｄ次元ベクトルを、本実施の形態の符号化の単位とする。すなわち送信すべきデータを数値化して、Ｋの要素を成分とするｄ次元ベクトル１本を単位として、符号化（暗号化）したものを送信する。
【００１７】
図４は、データ送信の始点であるソースノード２から送信される送信データを示す図である。図中のベクトル３−１〜３−３は、それぞれＫの要素である元ＫＧを成分とするｄ次元のベクトルである。以下、このベクトル３−１〜３−３のようなｄ次元ベクトルのうちの１つ示す場合、ベクトル３と表記する。この場合は、Ｋの要素の数ｐ＝２個であるため、ＫＧは０または１の２値である。図４に示すように、ソースノード２は、まず、１本目のベクトル３−１を送信し、２本目のベクトル３−２を送信し、というようにｄ次元ベクトルを単位として送信される。各ベクトルの要素は、それぞれのｄ本の独立経路に送信される。
【００１８】
つづいて、ソースノード２での符号化について説明する。図５は、本実施の形態のソースノード２を始点とするリンクＬの一例を示す図である。図５に示すように、ここでは、ソースノード２を始点とするｓ本のリンクＬが存在するとする。このとき、ソースノード２では、最初にＫの任意の要素を成分とする送信情報であるｄ次元ベクトルＶＳ１に、ｓ行ｄ列の行列ＭＳ１を乗じた結果をソースノード２から各リンクＬへ送出するデータＶＳＤ１とし、ＶＳＤ１を符号化されたベクトル３として算出する。そして、算出したベクトル３の各成分をｄ本の独立経路に対応するリンクＬにそれぞれ送出する。ｐ＝２，ｄ＝３，ｓ＝４とした場合のＶＳＤ１の一例を、以下の式（２）に示す。
【００１９】
【数１】
【００２０】
なお、上記の式（２）のＭＳ１は一例であり、ＭＳ１は、これに限らず、Ｋの要素を成分とするｓ行ｄ列の行列であればよい。
【００２１】
つづいて、ノード１−ｎ（ｎはノード番号を示す自然数）での符号化について説明する。図６は、ノード１−ｎに入ってくるリンクＬの数をｌ本とし、ノード１−ｎから出て行くリンクＬの数をｓ本とした場合のノード１−ｎとリンクＬの関係の一例を示す図である。このとき、ｌ本のリンクＬをそれぞれリンクＬの接続元であるノードからデータが流れてくる。ソースノード２から送信される各データは、前述のとおりＫの元であり、後述のように各ノードはＫの元を送信するため、ノード１−ｎに入ってくるリンクＬを流れるデータは、Ｋの元である。ここで、ノード１−ｎにはいってくる各リンクＬからのデータをｌ次元ベクトルＶＴ２と表すこととする。ノード１−ｎは、ＶＴ２にｓ行ｌ列の行列ＭＴをかけて得られるｓ次元ベクトルＶＴＤ２の成分をそれぞれ、ノード１−ｎから出ていくリンクＬに送出する。ｐ＝２，ｌ＝４，ｓ＝２とした場合のＶＳＤ２の一例を、以下の式（３）に示す。
【００２２】
【数２】
【００２３】
なお、上記の式（２）のＭＴは一例であり、ＭＴは、これに限らず、Ｋの要素を成分とするｓ行ｄ列の行列であればよい。本実施の形態では、巡回する経路がネットワーク上にないと仮定しているので、この繰り返しによって順々に、各リンクＬを流れるデータが決まっていく。
【００２４】
以上のように、ソースノード２およびノード１−ｎの処理繰り返して、あらかじめ決められた宛先のノードにデータが到達する。このような符号化を行う場合、盗聴者から守るべき対象は、各リンクＬを流れる個々のデータではなく、各ノードで行う符号化の方法、すなわち行列ＭＳ１およびＭＴである。各リンクＬを流れるデータをすべて盗聴されたとしても、各ノードが行っている符号化の方法が察知されなければ、元の送信情報は保護されるため、セキュリティの観点から評価する場合、符号化の方法が察知されることをできるだけ防いで察知されるまでの時間を引き伸ばすことが望ましい。
【００２５】
このため、以下では、上述のような符号化を行う場合に、盗聴者が符号化の方法、すなわち行列ＭＳ１およびＭＴ、を盗む際には平均何回の盗聴が必要かということを考える。本実施の形態では、この回数を盗聴頑健性の指標として定義して、セキュリティ（安全性）の高さを判定する。具体的には、盗聴頑健性の指標Ｆ（ｋ，ｄ）は以下の式（４）で表すことができる。
【００２６】
【数３】
【００２７】
この値が、所定の閾値より上ならば、盗聴に対して十分に頑健であると判定し、そうでなければ盗聴に対して弱いと判定する。図７は、盗聴頑健性の判定を行う手順の一例を示す図である。まず、集合Ｋを決定する、すなわち、ｐを決定する（ステップＳ１１）。つぎに、ソースノード２からノード１−ｎへの独立経路のうちの最大値ｄを求める（ステップＳ１２）。そして、ｄとｐに基づいて式（４）に従って盗聴頑健性の指標を求める（ステップＳ１３）。つぎに、ステップＳ１３で求めた盗聴頑健性の指標が所定の閾値より大きいか否かを判定し（ステップＳ１４）、閾値より大きい場合（ステップＳ１４ Ｙｅｓ）は盗聴に強い、すなわち安全性が高いと判定する（ステップＳ１５）。閾値より小さい場合（ステップＳ１４ Ｎｏ）は、盗聴に弱い、すなわち安全性が低いと判定する（ステップＳ１６）。
【００２８】
以上の手順を行うことにより、決定した集合Ｋについて、安全性を判定することができる。この判定を、たとえば、ソースノード２またはノード１−ｎで行い、安全性が高いと判定されるようにＫを決定し、決定したＫを全てのノード（ソースノード２およびノード１−ｎ）に通知するようにすれば、安全性の高い符号化を行うことができる。また、あらかじめ、本実施の形態の通信システム外の手段（他の計算機など）により、この判定を行って、判定結果をもとに安全性が高くなるようにＫを決定しておき、それを各ノードに設定するようにしてもよい。
【００２９】
また、Ｋに別の制約があり、安全性が高くなるようにＫを決定することができない場合には、安全性が低いことを考慮して通信システム内の安全性に関連する他のパラメータを調整するなどの他の対策を講じることにより安全性を確保ようにしてもよい。
【００３０】
なお、上記式（４）の盗聴頑健性の指標は、各リンクＬを流れるデータをすべて盗聴された場合を考慮して導入した計算式であるが、式（４）の指標は以下に示すようなケースを考慮した場合にも使用可能である。図８は、他の盗聴方法を考慮した場合を説明するための通信システムの一例を示す図である。図８では、破線は、その間のノード１−ｎとリンクＬの接続を省略していることを示している。
【００３１】
盗聴者は、ソースノード２から送信される送信情報であるデータ、すなわちｄ次元ベクトルと、ある特定のリンクＬＴ流れるデータ、すなわちＫの元を盗聴すると仮定する。この盗聴を１セットとする盗聴を何回か繰り返し、もとの送信情報であるｄ次元ベクトルとリンクＬを流れるデータの関係を盗み出したいとする。この場合に、この関係を明らかにするために、そのような盗聴を平均何回（何セット）しなければならないか、という指標を盗聴頑健性の指標とする場合にも、式（４）で示したのと同様となる。つまり、行列行列ＭＳ１およびＭＴを盗聴すると仮定した場合だけでなく、ｄ次元ベクトルと、リンクＬ流れるデータを盗聴すると仮定した場合にも式（４）の盗聴頑健性の指標を用いることができる。
【００３２】
このように、本実施の形態では、通信システムを構成する各ノードで符号化を行い、独立経路の最大値ｄと通信システムで送信するデータの要素の集合Ｋの大きさに基づいて盗聴頑健性の指標を算出し、盗聴頑健性の指標が所定の閾値より大きくなるか否かによって安全性を判定するようにした。このため、盗聴頑健性の指標が所定の閾値より大きくようにＫを決定することで、安全性の高いデータ伝送を行うことができる。
【００３３】
実施の形態２．
実施の形態１では、盗聴頑健性の指標に基づいて安全性の評価ができるデータ伝送方法について述べたが、本実施の形態では、実施の形態１の符号化方法では、符号化に用いる行列の要素の値によっては生のデータが流れる場合がある。データ全体の盗聴や暗号化の仕組み全体を盗聴することが困難であったとしても、一部でも暗号化されていない生のデータがネットワーク上を流れることは好ましくない。たとえば、クレジットカード番号の一部がそのまま流れるようなことは防ぐことが望ましい。本実施の形態では、ネットワーク上を生のデータが流れることをできるだけ防ぐ新たな符号化方法について述べる。なお、本実施の形態の通信システムの構成は実施の形態１と同様である。
【００３４】
実施の形態１の符号化方法では、ノード１−ｎに入ってくるデータに対し行列ＭＴを乗算した。この行列は、出力先のリンクＬにそれぞれ対応する１行のｄ次元横ベクトルがリンクＬの数だけ縦に並んでいる行列と考えることができる。すなわち、ソースノード２における最初の送信情報であるデータを与えるｄ次元縦ベクトルＶＳ１とある特定のリンクＬを流れるデータ（Ｋの元）との対応について注目すると、ＶＳ１に対し、リンクＬごとにｄ次元横ベクトルを乗算していると考えることができる。このように考えたときのｄ次元横ベクトルを符号化ベクトルＥＣＶＴと呼ぶこととする。図９は、ｄ＝４とした場合の符号化ベクトルＥＣＶＴの一例を示す図である。本実施の形態では、リンクＬ毎に、符号化ベクトルを決定すると考えて、その符号化ベクトルの要素の選び方を工夫することで生のデータの一部がネットワーク上を流れることを防ぐ。
【００３５】
図１０は、本実施の形態の符号化方法を説明するための通信システムの一例を示す図である。まず、ノードに番号をつける。ここでは、図１０の各ノードに付した符号の枝番号をノード番号とし、各リンクＬはノード番号の少ないほうから多い方に向かっているとする。本実施の形態では、実施の形態１と同様にネットワーク内に巡回経路と家庭するため、このような番号付けが可能である。そして、始点となるノードから始めて、順にノード番号の小さい順にリンクＬごとに符号化ベクトルを選んでいく。
【００３６】
ノード１−ｎを始点に持つリンクＬの符号化ベクトルＥＣＶＴは、次のように選ぶ。まず、ノード１−ｎに入ってくるリンクＬの持つリンクＬの個数分の符号化ベクトルＥＣＶＴの１次結合で得られるベクトルのなす線形結合Ｖを考える。２つの符号化ベクトルＥＣＶＴの１次結合で得られる線形結合Ｖは、たとえば、２つの符号化ベクトルＥＣＶＴを含む平面となる。上記非特許文献３では、この線形空間Ｖの中から、「一般的」なベクトルを選べば、最大効率が達成できると示されている。
【００３７】
本実施の形態では、この「一般的」なベクトルを選ぶステップで新たな条件を追加することにより、生のデータの一部がネットワーク上を流れることを防ぐ。まず、ｄ次元の第ｊ成分だけが１で残りの成分がすべて０であるベクトルをｅｊとする。あるノード１−ｎに入ってくるリンクＬの本数をｔとする。このリンクＬにそれぞれ対応するｔ本の符号化ベクトルの張る部分空間をＶとする。ノード１−ｎよりノード番号の若いノードから出るリンクＬの符号化ベクトルとしてすでに決定された符号化ベクトルのなかから（ｄ−１）本以下のベクトルを選ぶ。この本数がちょうど（ｄ−１）本でないときは、ｅｊを一つ選ぶ。このとき、ｔ本の符号化ベクトルとｅｊの張る部分空間をＷとする。ＷがＶを含んでいるときはそのＷは捨てる。また、選んだ符号化ベクトルがちょうど（ｄ−１）本のときは、それらの張る部分空間をＷとする。やはりＷがＶを含んでいるときはそのＷは捨てる。（ｄ−１）本以下の符号化ベクトルとｅｊをどのように選んだとしても、それらの張るＷに含まれないＶの元を、ノード１−ｎから出るリンクＬの符号化ベクトルとする。
【００３８】
図１１−１，１１−２は本実施の形態の符号化ベクトルの選択手順の一例をリンク１本分について示したフローチャートである。まず、ノード１−ｎに入ってくるｔ本のリンクＬの符号化ベクトルの張る部分空間Ｖを求める（ステップＳ２１）。つぎに、よけるべき部分空間の集合Ｘを空集合におく（ステップＳ２２）。そして、ノード１−ｎよりノード番号の若いノードから出るリンクＬの符号化ベクトルとしてすでに決定された符号化ベクトルの中から、（ｄ−１）本以下の組合せを選択する（ステップＳ２３）。このとき、２回目以降のステップＳ２３の実行の場合（ステップＳ３３から戻ってステップＳ２３を実行した場合）には、それ以前のステップＳ２３で選ばれていない組み合わせを除いて選択する。
【００３９】
つぎに、選んだ符号化ベクトルの本数が（ｄ−１）本であるかを判定する（ステップＳ２４）。選んだ符号化ベクトルの本数が（ｄ−１）本の場合（ステップＳ２４ Ｙｅｓ）は、ステップＳ３０に進む。選んだ符号化ベクトルの本数が（ｄ−１）本でない場合（ステップＳ２４ Ｎｏ）には、１本のｅｊを選択する（ステップＳ２５）。このとき、２回以降のステップＳ２５の実行の場合は、それ以前のステップＳ２５で選んでいないｅｊのうちから１本を選択する（ステップＳ２５）。
【００４０】
つぎに、ステップＳ２３で選んだ符号化ベクトルとステップＳ２５で選択したｅｊの張る空間をＷとする。つぎに、ＶがＷに含まれるかを判定する（ステップＳ２７）。ＶがＷに含まれると判定した場合（ステップＳ２７ Ｙｅｓ）には、ステップＳ２９に進み、ＶがＷに含まれないと判定した（ステップＳ２７ Ｎｏ）場合にはステップＳ２８に進む（ステップＳ２８）。ステップＳ２８では、ＷをＸに追加する。
【００４１】
ステップＳ２９では、ステップＳ２５でまだ選んでいないｅｊがあるかを判定する。選んでいないｅｊがまだあると判定した場合（ステップＳ２９ Ｙｅｓ）には、ステップＳ２５に戻る。選んでいないｅｊがない（すべてのｅｊが既に選ばれた）と判定した場合（ステップＳ２９ Ｎｏ）には、ステップＳ３０に進む。つぎに、ステップＳ２３で選んだ符号化ベクトルの張る空間をＷとする（ステップＳ３０）。そして、ＶがＷに含まれるかを判定する（ステップＳ３１）。ＶがＷに含まれる場合（ステップＳ３１ Ｙｅｓ）には、ステップＳ３３に進む。ＶがＷに含まれない場合（ステップＳ３１ Ｎｏ）には、ＷをＸに追加する（ステップＳ３２）。
【００４２】
つぎに、ステップＳ３３で、すでに選んだ符号化ベクトルの中から（ｄ−１）本以下の組合せを選ぶ方法がまだあるかを判定する（ステップＳ３３）。まだ選ぶ方法がある場合（ステップＳ３３ Ｙｅｓ）には、ステップＳ２３に戻る。もう選ぶ方法がない場合（すでに選んだ符号化ベクトルのなかから、（ｄ−１）本以下のすべての組み合わせの選択が終了した）場合は、Ｘに含まれるどのＷにも入らない符号化ベクトルをＶの中から選び、対応するリンクＬの符号化ベクトルとする（ステップＳ３４）。
【００４３】
そして、以上の処理をノード１−ｎから出るすべてのリンクＬについて実行すればよい。図１２は、通信システム全体のノード（ソースノード２およびノード１−ｎ）の処理手順の一例を示すフローチャートである。まず、まだ符号化ベクトル処理を行っていないノードのなかから符号化ベクトル処理の対象とするノードを選択する（ステップＳ４１）。そして、選択したノードから出るリンクのうち、符号化ベクトルの選択が終了していないリンクＬを１つ選択する（ステップＳ４２）。つぎに、選択したリンクＬについて図１１−１，図１１−２で説明した処理により符号化ベクトルを選ぶ（ステップＳ４３）。そして、選択したノードから出るリンクのうち、符号化ベクトルが選ばれていないリンクがまだあるかを判定する（ステップＳ４４）。符号化ベクトルが選ばれていないリンクがまだある場合（ステップＳ４４ Ｙｅｓ）には、ステップＳ４２に戻る。符号化ベクトルが選ばれていないリンクがない場合（ステップＳ４４ Ｎｏ）には、まだ符号化ベクトル処理を行っていないノードがあるか否かを判断する（ステップＳ４５）。
【００４４】
符号化ベクトル処理を行っていないノードがあると判断した場合（ステップＳ４５ Ｙｅｓ）にステップＳ４２に戻る。符号化ベクトル処理を行っていないノードがないと判断した場合（ステップＳ４５ Ｎｏ）は、処理を終了する。
【００４５】
このようにしてすべてのノードについて、そのノードから出るリンクＬについての符号化ベクトルを決定する。なお、この決定処理を通信システム内の特定のノードで行い、符号化ベクトルを対応するノードにそれぞれ通知するようにしてもよいし、通信システム外の別の計算機などで符号化ベクトルを算出して、各ノードに設定するようにしてもよい。
【００４６】
以上のように、本実施の形態では、ＷがＶに含まれる場合には、そのＷをすて、すべてのｅｊについてＷがＶに含まれないように符号化ベクトルを選択するようにした。このため実施の形態１の効果に加え、ネットワーク上を生のデータができるだけ流れないようにすることができ、秘匿性・安全性がさらに向上する。
【産業上の利用可能性】
【００４７】
以上のように、本発明にかかるデータ伝送方法および通信システムは、ネットワークコーディングを採用する通信システムに有用であり、特に、高いセキュリティを要求される通信システムに適している。
【図面の簡単な説明】
【００４８】
【図１】本発明にかかる通信システムの実施の形態１の構成例を示す図である。
【図２】本発明で想定しない通信システムの一例を示す図である。
【図３】実施の形態１の通信システムの別の構成例を示す図である。
【図４】ソースノードから送信される送信データを示す図である。
【図５】ソースノードを始点とするリンクＬの一例を示す図である。
【図６】ノードとリンクの関係の一例を示す図である。
【図７】盗聴頑健性の判定を行う手順の一例を示す図である。
【図８】他の盗聴方法を考慮した場合を説明するための通信システムの一例を示す図である。
【図９】符号化ベクトルの一例を示す図である。
【図１０】実施の形態２の符号化方法を説明するための通信システムの一例を示す図である。
【図１１−１】符号化ベクトルの選択手順の一例をリンク１本分について示したフローチャートである。
【図１１−２】符号化ベクトルの選択手順の一例をリンク１本分について示したフローチャートである。
【図１２】ネットワーク全体の処理手順の一例を示すフローチャートである。
【符号の説明】
【００４９】
１，１−１〜１−８ ノード
２ ソースノード
３−１〜３−３ ベクトル
ＲＴ１，ＲＴ２，ＲＴ３ 経路
Ｌ，Ｌ１，ＬＴ リンク
【特許請求の範囲】
【請求項１】
送信情報を生成するソースノードと前記送信情報の宛先ノードまたは前記送信情報を中継する中継ノードである一般ノードとで構成される通信システムにおいて、前記ソースノードおよび前記一般ノードで符号化を行ってデータを伝送する場合のデータ伝送方法であって、
前記ソースノードを始点とし前記一般ノードを終点とする独立経路の数の最大値を求める独立経路最大値算出ステップと、
前記送信情報および符号化に用いる行列の各要素を構成要素とする集合の大きさを設定する集合設定ステップと、
前記最大値と前記大きさに基づいて盗聴に対する頑健性を示す盗聴頑健性指標を算出する盗聴頑健性指標算出ステップと、
前記盗聴頑健性指標に基づいて通信システムのセキュリティに関するパラメータを設定するパラメータ設定ステップと、
を含むことを特徴とするデータ伝送方法。
【請求項２】
前記パラメータ設定ステップでは、前記盗聴頑健性指標が所定の閾値より大きいか否かを判定し、前記盗聴頑健性指標が所定の閾値未満である場合には、前記盗聴頑健性指標が所定の閾値より大きくなるように前記大きさを再設定することを特徴とする請求項１に記載のデータ伝送方法。
【請求項３】
送信情報を生成するソースノードと前記送信情報の宛先ノードまたは前記送信情報を中継する中継ノードである一般ノードとで構成される通信システムにおいて、前記ソースノードおよび前記一般ノードで符号化を行ってデータを伝送する場合に、前記ソースノードと前記一般ノードとの間または前記一般ノード間を接続する通信路である各々のリンクに対応する符号化ベクトルを算出し、各リンクを通過する情報にそのリンクに対応する前記符号化ベクトルを乗じることにより符号化を行うデータ伝送方法であって、
前記一般ノードが接続先となるリンクに対応する前記符号化ベクトルの張る部分空間を決定済み符号化ベクトル空間として求める符号化ベクトル空間算出ステップと、
すでに符号化ベクトルとして決定された符号化ベクトルのなかから、前記最大値から１を減じた数以下の本数の符号化ベクトルを選択する符号化ベクトル選択ステップと、
前記選択した符号化ベクトルの本数が前記最大値から１を減じた数未満である場合には、前記選択した符号化ベクトルと、次元数を前記最大値としいずれか１つの成分のみを１とし他の成分を０とするベクトル群のなかから選択した１つのベクトルである選択ベクトルと、の張る空間を選択符号化ベクトル空間として求める第１の選択符号化ベクトル算出ステップと、
前記選択した符号化ベクトルの本数が前記最大値から１を減じた数である場合には、前記選択した符号化ベクトルの張る空間を選択符号化ベクトル空間として求める第２の選択符号化ベクトル空間算出ステップと、
前記決定済み符号化ベクトル空間が前記選択符号化ベクトル空間に含まれる場合には、前記選択符号化ベクトル空間を除外空間とする除外空間算出ステップと、
第１の選択符号化ベクトル算出ステップで前記ベクトル群の全てを選択し、かつ、前記符号化ベクトル選択ステップで、すでに符号化ベクトルとして決定された符号化ベクトルのなかから前記最大値から１を減じた数以下の本数の符号化ベクトルの全ての組み合わせを選択するまで、前記符号化ベクトル選択ステップと前記第１の選択符号化ベクトル算出ステップと前記第２の選択符号化ベクトル算出ステップと前記除外空間算出ステップとを繰り返し実行し、前記繰り返しの後に、前記決定済み符号化ベクトル空間のなかから、前記除外空間とされなかった符号化ベクトルを選択して、前記選択した符号化ベクトルを、前記一般ノードを接続元とするリンクに対応する符号化ベクトルとして決定する符号化ベクトル決定ステップと、
を含むことを特徴とするデータ伝送方法。
【請求項４】
送信情報を生成するソースノードと前記送信情報の宛先ノードまたは前記送信情報を中継する中継ノードである一般ノードとで構成され、前記ソースノードおよび前記一般ノードが符号化を行ってデータを伝送する通信システムであって、
前記ソースノードまたは一般ノードは、
前記ソースノードを始点とし前記一般ノードを終点とする独立経路の数の最大値を求める独立経路最大値算出手段と、
前記送信情報および符号化に用いる行列の各要素を構成要素とする集合の大きさを設定する集合設定手段と、
前記最大値と前記大きさに基づいて盗聴に対する頑健性を示す盗聴頑健性指標を算出する盗聴頑健性指標算出手段と、
前記盗聴頑健性指標に基づいて通信システムのセキュリティに関するパラメータを設定するパラメータ設定手段と、
を備えることを特徴とする通信システム。
【請求項５】
送信情報を生成するソースノードと前記送信情報の宛先ノードまたは前記送信情報を中継する中継ノードである一般ノードとで構成され、前記ソースノードと前記一般ノードとの間または前記一般ノード間を接続する通信路である各々のリンクに対応する符号化ベクトルを算出し、各リンクを通過する情報にそのリンクに対応する前記符号化ベクトルを乗じることにより前記符号化を行う通信システムであって、
前記ソースノードまたは一般ノードは、
前記一般ノードが接続先となるリンクに対応する前記符号化ベクトルの張る部分空間を決定済み符号化ベクトル空間として求める符号化ベクトル空間算出手段と、
すでに符号化ベクトルとして決定された符号化ベクトルのなかから、前記最大値から１を減じた数以下の本数の符号化ベクトルを選択する符号化ベクトル選択手段と、
前記選択した符号化ベクトルの本数が前記最大値から１を減じた数未満である場合には、前記選択した符号化ベクトルと、次元数を前記最大値としいずれか１つの成分のみを１とし他の成分を０とするベクトル群のなかから選択した１つのベクトルである選択ベクトルと、の張る空間を選択符号化ベクトル空間として求める第１の選択符号化ベクトル算出手段と、
前記選択した符号化ベクトルの本数が前記最大値から１を減じた数である場合には、前記選択した符号化ベクトルの張る空間を選択符号化ベクトル空間として求める第２の選択符号化ベクトル空間算出手段と、
前記決定済み符号化ベクトル空間が前記選択符号化ベクトル空間に含まれる場合には、前記選択符号化ベクトル空間を除外空間とする除外空間算出手段と、
第１の選択符号化ベクトル算出手段が前記ベクトル群の全てを選択し、かつ、前記符号化ベクトル選択手段で、すでに符号化ベクトルとして決定された符号化ベクトルのなかから前記最大値から１を減じた数以下の本数の符号化ベクトルの全ての組み合わせを選択するまで、前記符号化ベクトル選択手段と前記第１の選択符号化ベクトル算出手段と前記第２の選択符号化ベクトル算出手段と前記除外空間算出手段との処理を繰り返し実行する制御手段と、
前記繰り返しの後に、前記決定済み符号化ベクトル空間のなかから、前記除外空間とされなかった符号化ベクトルを選択して、前記選択した符号化ベクトルを、前記一般ノードを接続元とするリンクに対応する符号化ベクトルとして決定する符号化ベクトル決定手段と、
を備えることを特徴とする通信システム。
【請求項１】
送信情報を生成するソースノードと前記送信情報の宛先ノードまたは前記送信情報を中継する中継ノードである一般ノードとで構成される通信システムにおいて、前記ソースノードおよび前記一般ノードで符号化を行ってデータを伝送する場合のデータ伝送方法であって、
前記ソースノードを始点とし前記一般ノードを終点とする独立経路の数の最大値を求める独立経路最大値算出ステップと、
前記送信情報および符号化に用いる行列の各要素を構成要素とする集合の大きさを設定する集合設定ステップと、
前記最大値と前記大きさに基づいて盗聴に対する頑健性を示す盗聴頑健性指標を算出する盗聴頑健性指標算出ステップと、
前記盗聴頑健性指標に基づいて通信システムのセキュリティに関するパラメータを設定するパラメータ設定ステップと、
を含むことを特徴とするデータ伝送方法。
【請求項２】
前記パラメータ設定ステップでは、前記盗聴頑健性指標が所定の閾値より大きいか否かを判定し、前記盗聴頑健性指標が所定の閾値未満である場合には、前記盗聴頑健性指標が所定の閾値より大きくなるように前記大きさを再設定することを特徴とする請求項１に記載のデータ伝送方法。
【請求項３】
送信情報を生成するソースノードと前記送信情報の宛先ノードまたは前記送信情報を中継する中継ノードである一般ノードとで構成される通信システムにおいて、前記ソースノードおよび前記一般ノードで符号化を行ってデータを伝送する場合に、前記ソースノードと前記一般ノードとの間または前記一般ノード間を接続する通信路である各々のリンクに対応する符号化ベクトルを算出し、各リンクを通過する情報にそのリンクに対応する前記符号化ベクトルを乗じることにより符号化を行うデータ伝送方法であって、
前記一般ノードが接続先となるリンクに対応する前記符号化ベクトルの張る部分空間を決定済み符号化ベクトル空間として求める符号化ベクトル空間算出ステップと、
すでに符号化ベクトルとして決定された符号化ベクトルのなかから、前記最大値から１を減じた数以下の本数の符号化ベクトルを選択する符号化ベクトル選択ステップと、
前記選択した符号化ベクトルの本数が前記最大値から１を減じた数未満である場合には、前記選択した符号化ベクトルと、次元数を前記最大値としいずれか１つの成分のみを１とし他の成分を０とするベクトル群のなかから選択した１つのベクトルである選択ベクトルと、の張る空間を選択符号化ベクトル空間として求める第１の選択符号化ベクトル算出ステップと、
前記選択した符号化ベクトルの本数が前記最大値から１を減じた数である場合には、前記選択した符号化ベクトルの張る空間を選択符号化ベクトル空間として求める第２の選択符号化ベクトル空間算出ステップと、
前記決定済み符号化ベクトル空間が前記選択符号化ベクトル空間に含まれる場合には、前記選択符号化ベクトル空間を除外空間とする除外空間算出ステップと、
第１の選択符号化ベクトル算出ステップで前記ベクトル群の全てを選択し、かつ、前記符号化ベクトル選択ステップで、すでに符号化ベクトルとして決定された符号化ベクトルのなかから前記最大値から１を減じた数以下の本数の符号化ベクトルの全ての組み合わせを選択するまで、前記符号化ベクトル選択ステップと前記第１の選択符号化ベクトル算出ステップと前記第２の選択符号化ベクトル算出ステップと前記除外空間算出ステップとを繰り返し実行し、前記繰り返しの後に、前記決定済み符号化ベクトル空間のなかから、前記除外空間とされなかった符号化ベクトルを選択して、前記選択した符号化ベクトルを、前記一般ノードを接続元とするリンクに対応する符号化ベクトルとして決定する符号化ベクトル決定ステップと、
を含むことを特徴とするデータ伝送方法。
【請求項４】
送信情報を生成するソースノードと前記送信情報の宛先ノードまたは前記送信情報を中継する中継ノードである一般ノードとで構成され、前記ソースノードおよび前記一般ノードが符号化を行ってデータを伝送する通信システムであって、
前記ソースノードまたは一般ノードは、
前記ソースノードを始点とし前記一般ノードを終点とする独立経路の数の最大値を求める独立経路最大値算出手段と、
前記送信情報および符号化に用いる行列の各要素を構成要素とする集合の大きさを設定する集合設定手段と、
前記最大値と前記大きさに基づいて盗聴に対する頑健性を示す盗聴頑健性指標を算出する盗聴頑健性指標算出手段と、
前記盗聴頑健性指標に基づいて通信システムのセキュリティに関するパラメータを設定するパラメータ設定手段と、
を備えることを特徴とする通信システム。
【請求項５】
送信情報を生成するソースノードと前記送信情報の宛先ノードまたは前記送信情報を中継する中継ノードである一般ノードとで構成され、前記ソースノードと前記一般ノードとの間または前記一般ノード間を接続する通信路である各々のリンクに対応する符号化ベクトルを算出し、各リンクを通過する情報にそのリンクに対応する前記符号化ベクトルを乗じることにより前記符号化を行う通信システムであって、
前記ソースノードまたは一般ノードは、
前記一般ノードが接続先となるリンクに対応する前記符号化ベクトルの張る部分空間を決定済み符号化ベクトル空間として求める符号化ベクトル空間算出手段と、
すでに符号化ベクトルとして決定された符号化ベクトルのなかから、前記最大値から１を減じた数以下の本数の符号化ベクトルを選択する符号化ベクトル選択手段と、
前記選択した符号化ベクトルの本数が前記最大値から１を減じた数未満である場合には、前記選択した符号化ベクトルと、次元数を前記最大値としいずれか１つの成分のみを１とし他の成分を０とするベクトル群のなかから選択した１つのベクトルである選択ベクトルと、の張る空間を選択符号化ベクトル空間として求める第１の選択符号化ベクトル算出手段と、
前記選択した符号化ベクトルの本数が前記最大値から１を減じた数である場合には、前記選択した符号化ベクトルの張る空間を選択符号化ベクトル空間として求める第２の選択符号化ベクトル空間算出手段と、
前記決定済み符号化ベクトル空間が前記選択符号化ベクトル空間に含まれる場合には、前記選択符号化ベクトル空間を除外空間とする除外空間算出手段と、
第１の選択符号化ベクトル算出手段が前記ベクトル群の全てを選択し、かつ、前記符号化ベクトル選択手段で、すでに符号化ベクトルとして決定された符号化ベクトルのなかから前記最大値から１を減じた数以下の本数の符号化ベクトルの全ての組み合わせを選択するまで、前記符号化ベクトル選択手段と前記第１の選択符号化ベクトル算出手段と前記第２の選択符号化ベクトル算出手段と前記除外空間算出手段との処理を繰り返し実行する制御手段と、
前記繰り返しの後に、前記決定済み符号化ベクトル空間のなかから、前記除外空間とされなかった符号化ベクトルを選択して、前記選択した符号化ベクトルを、前記一般ノードを接続元とするリンクに対応する符号化ベクトルとして決定する符号化ベクトル決定手段と、
を備えることを特徴とする通信システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１−１】
【図１１−２】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１−１】
【図１１−２】
【図１２】
【公開番号】特開２００９−５５３３９（Ｐ２００９−５５３３９Ａ）
【公開日】平成２１年３月１２日（２００９．３．１２）
【国際特許分類】
【出願番号】特願２００７−２２００４６（Ｐ２００７−２２００４６）
【出願日】平成１９年８月２７日（２００７．８．２７）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
【公開日】平成２１年３月１２日（２００９．３．１２）
【国際特許分類】
【出願日】平成１９年８月２７日（２００７．８．２７）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
[ Back to top ]