証明書失効リストの配布方法、及びそれに用いられる送信ノードと中継ノード
【課題】車両が高密度な環境下でも、車々間通信により効率的に証明書失効リストを配布する証明書失効リストの配布方法、及びそれに用いられる送信ノードと中継ノードを提供する。
【解決手段】送信ノードは、認証局から受け取った証明書失効リストを、ランダムネットワーク符号化を用いて符号化し、符号化データを路車間通信でブロードキャストにより配布し、中継ノードは、一定間隔ごとに、受信した符号化データを再符号化して車々間通信によりブロードキャストする。
【解決手段】送信ノードは、認証局から受け取った証明書失効リストを、ランダムネットワーク符号化を用いて符号化し、符号化データを路車間通信でブロードキャストにより配布し、中継ノードは、一定間隔ごとに、受信した符号化データを再符号化して車々間通信によりブロードキャストする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、車々間通信により証明書失効リストを配布する証明書失効リストの配布方法、及びそれに用いられる送信ノードと中継ノードに関する。
【背景技術】
【０００２】
車両アドホックネットワークにより車両位置情報などの様々な情報を交換し、収集した情報をもとにドライバーに対して注意喚起などの運転支援が行われる。もしも、交換される情報が誤っていた場合、ドライバーに対して誤った誘導をしてしまう。
【０００３】
情報の信頼性確保のための暗号・認証技術では鍵が用いられ、信頼できる第三者が発行する公開鍵証明書によりその鍵を信頼するモデルがある。証明書の有効性検証は一般に証明書失効リストに基づいて行われる。証明書失効リストのバーション更新が遅いとすでに失効された証明書を誤って有効であるとしてしまう可能性がある。したがって、証明書失効リストの配布は高速に行う必要がある。
【０００４】
非特許文献１では、コストのかかる路側機の設置を少なくして、可能な限り早く、多数の車両に証明書失効リストを配布するための車々間通信による配布方式を提案している。
【０００５】
車両アドホックネットワークのようなネットワーク接続コンピューティング環境における大規模コンテンツ配信に使用される１つの機構は、ネットワークコーディングを使用したコンテンツ配信システムである。特許文献１では高速かつスケーラブルなコンテンツ配信を提供する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００６−３１６９３号公報
【非特許文献】
【０００７】
【非特許文献１】K.P. Laberteaux, J.J. Haas, Y.-C. Hu, “Security Certificate Revocation List Distribution for VANET”, Proceedings of the Fifth ACM International Workshop on VehiculAr Inter-NETworking (VANET 2008), ACM, San Francisco, 2008.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ある領域の車両が高密度になった場合、非特許文献１および特許文献１の方式では、証明書失効リストの要素を含んだパケット、または要素を符号化したパケットが、車両から同時に送信されるとパケット衝突が増大し、配信性能が劣化する。
【０００９】
本発明は上記点に鑑みて、車両が高密度な環境下でも効率的に証明書失効リストを配布できるようにすることを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するため、請求項１に記載の発明は、送信ノードから発信される証明書失効リストを、ランダムネットワーク符号化を用いた車々間通信により配布する証明書失効リストの配布方法を特徴としている。
【００１１】
請求項２に記載の発明は、請求項１に記載の証明書失効リストの配布方法に用いられる送信ノードであって、受け取った証明書失効リストをランダムネットワーク符号化で符号化し路車間通信で符号化データをブロードキャストする送信ノードを特徴としている。
【００１２】
請求項３に記載の発明は、請求項１に記載の証明書失効リストの配布方法に用いられる中継局であって、一定間隔ごとに、受信した符号化データを再符号化してブロードキャストする中継ノードを特徴としている。
【図面の簡単な説明】
【００１３】
【図１】本発明の各ノード間の関係を示す図である。
【図２】本発明の送信ノードの処理の流れを示す図である。
【図３】本発明の中継ノードの処理の流れを示す図である。
【図４】本発明の受信ノードの処理の流れを示す図である。
【図５】本発明のシミュレーション結果を示す図である。
【発明を実施するための形態】
【００１４】
本実施形態は、ネットワークコーディングを使用した無線マルチホップ通信により証明書失効リストの配布を行うもので、車両が高密度な環境下でも効率的に証明書失効リストを配布できるようにするために、ランダムネットワーク符号化を用いた車々間通信により証明書失効リストの配布を行う。
【００１５】
車両アドホックネットワークのような無線ネットワークでは複数のパケットの衝突によるパケットロスが発生する。複数のパケットを1つのパケットにネットワーク符号化して送信すれば、ネットワーク全体を伝搬するパケット数が減る。それに伴い衝突が減少し通信品質が向上する。
【００１６】
ネットワーク符号化とは、複数のデータを1つのデータに符号化して中継する符号化技術である。元のデータは複数経路から送られてきた相異なる符号化データから復号できる。
【００１７】
ネットワーク符号化の実装方法の1つにランダムネットワーク符号化がある。
【００１８】
ランダムネットワーク符号化では入力データをランダムな符号化ベクトルで符号化し、毎回異なる符号化データを出力する。符号化データは、復号せずにさらに再符号化できる。そして、送信ノードが直接に符号化したデータだけではなく、中継ノードが再符号化したデータと合わせて、受信ノードが入力データと同じ個数のデータを受信すれば元のデータを復号できる。
【００１９】
符号化ベクトルは復号に必要である。復号するノードに対する事前通信を不要にするために、符号化ベクトルと符号化データをパケットに含めて送信することがランダムネットワーク符号化の特徴である。
【００２０】
本実施形態は、路側機のような送信ノードから発信される証明書失効リストを配布するためのランダムネットワーク符号化を用いた車両アドホックネットワーク上のブロードキャスト通信方式である。
【００２１】
本実施形態では、図１に示した送信ノード（路側機）は認証局からインフラ通信で証明書失効リストを受け取る。受け取った証明書失効リストをランダムネットワーク符号化でＮ回符号化し路車間通信でＮ個の符号化データをブロードキャストする。中継ノードは受け取った複数の符号化データを1個の符号化データに再符号化して中継する。受信ノードは送信された符号化データと同じＮ個のデータを受信すれば復号する。
【００２２】
図２は送信ノード（路側機）が証明書失効リストを符号化して送信する流れを示している。送信ノードは認証局から証明書失効リストＸを受け取る（S01）。受け取った証明書失効リストＸはＮ個のデータに分割する（S02）。受け取った証明書失効リストはランダムな符号化ベクトルでＮ回符号化するため、現在の符号化回数をカウントする変数を用意し（S03）、証明書失効リストをＮ回符号化するまで符号化・送信処理を繰り返す（S04）。
【００２３】
符号化では、まず符号化に必要なランダムな符号化ベクトルＣを作成する（S05）。符号化ベクトルＣとデータＸを線形演算することで符号化し、符号化データｙを作成する（S06）。符号化ベクトルＣは復号に必要なため、符号化ベクトルＣと符号化データｙをパケットに含めてブロードキャストする（S07）。ブロードキャスト後は一定時間待機し（S08）、符号化回数をインクリメントしてから（S09）、次の符号化・送信処理を行う（S10）。
【００２４】
図３は受信した符号化データを再符号化してブロードキャストする中継ノードの流れを示している。中継ノードは一定間隔ごとに受信データを再符号化して中継するため、再符号化・中継処理を繰り返す（S11）。
【００２５】
受信パケットが送信データ数Ｎより少なくても一定間隔ごとに再符号化・中継処理を行う（S12）。まず、受信パケットｐｉから符号化データｙｉと符号化ベクトルＤｉを取り出す（S13）。符号化と同様再符号化でもランダムな符号化ベクトルで符号化するので符号化ベクトルＣを作成する（S14）。符号化ベクトルＣと符号化データｙｉを線形演算し、再符号化する（S15）。
【００２６】
復号には符号化データＹの係数ＣではなくＸの係数に相当する符号化ベクトルＤ’が必要なので符号化ベクトルを更新する。符号化ベクトルのＮ個の要素全てを更新するため、符号化ベクトルの何番目の要素を更新しているかを示す変数を用意する（S16）。符号化ベクトルのＮ個の要素全てを更新するまで更新処理を繰り返す（S17）。受信パケットに含まれる符号化ベクトルからなる行列Ｄに含まれる符号化ベクトルのｉ番目の要素の更新は、受信パケットに含まれる符号化ベクトルからなる行列Ｄに含まれる符号化ベクトルのｉ番目の要素からなるベクトルと符号化ベクトルＣの線形演算で行う（S18）。符号化ベクトルの更新後は更新回数をインクリメントし（S19）、符号化ベクトルＤのＮ番目の要素を更新するまで繰り返す（S20）。
【００２７】
符号化ベクトルの更新が終われば、更新した符号化ベクトルＤ’と再符号化したデータＺをパケットに含めてブロードキャストする（S21）。再符号化・中継処理の後は一定時間待機し（S22）、次の再符号化・中継処理を行う（S23）。
【００２８】
図４は受信した符号化データを復号する受信ノードの流れを示している。復号にはＮ個の符号化データが必要なので、現在の受信パケット数を格納する変数を用意する（S24）。Ｎ個のパケットを受信するまで受信処理を繰り返す（S25）。受信処理では、まず送信ノード／中継ノードがブロードキャストしたパケットが届くまで受信待機する（S26）。パケットｐｉを受信すると（S27）、パケットｐｉから符号化データＺｉと符号化ベクトルＤｉを取り出す（S28）。パケットの受信後は現在の受信パケット数をインクリメントし（S29）、Ｎ個のパケットを受信するまで受信処理を繰り返す（S30）。
【００２９】
復号に必要なＮ個のデータを受信すると復号する。受信パケットに含まれるＤはＸの係数に相当する符号化ベクトルなので、元のデータＸと受信した符号化ベクトルＤと符号化データＺの間にはＺ＝ＤＸの関係式が成り立つ（S31）。Ｄは受信パケットに含まれる符号化ベクトルＤｉからなる行列であり、これに逆行列が存在すればＸ＝Ｄ−１Ｚが成り立ち、ＤとＺからＸを復号する（S32）。
【００３０】
図５は、本実施形態（提案方式）と、符号化しない車々間通信（フラッディング）、複数台の路側機による路車間通信のみでの配信のシミュレーション結果を示している。
【００３１】
車両が高密度な環境下では、フラッディングではパケットロスが多数発生し、路側機１台での路車間通信のみで配信するよりも大きなリストを配信できるが、路側機４台での路車間通信のみで配信するよりも性能が良くない。本実施形態（提案方式）は、フラッディングよりも配信性能が高い。
【００３２】
１台の路側機が配信したデータを車々間通信で中継・配布する本実施形態（提案方式）は、１２台の路側機による路車間通信のみでの配布と同等の性能でデータを配信でき、路側機の台数を減らせるので、路側設備の設置コストを削減できる。
【００３３】
なお、上記した実施形態において、図２〜図４に示す各ステップは、それぞれの機能を実現する手段として把握されるものであり、具体的には送信ノード、中継ノード、受信ノードに備えられたコンピュータによって実行される。
【技術分野】
【０００１】
本発明は、車々間通信により証明書失効リストを配布する証明書失効リストの配布方法、及びそれに用いられる送信ノードと中継ノードに関する。
【背景技術】
【０００２】
車両アドホックネットワークにより車両位置情報などの様々な情報を交換し、収集した情報をもとにドライバーに対して注意喚起などの運転支援が行われる。もしも、交換される情報が誤っていた場合、ドライバーに対して誤った誘導をしてしまう。
【０００３】
情報の信頼性確保のための暗号・認証技術では鍵が用いられ、信頼できる第三者が発行する公開鍵証明書によりその鍵を信頼するモデルがある。証明書の有効性検証は一般に証明書失効リストに基づいて行われる。証明書失効リストのバーション更新が遅いとすでに失効された証明書を誤って有効であるとしてしまう可能性がある。したがって、証明書失効リストの配布は高速に行う必要がある。
【０００４】
非特許文献１では、コストのかかる路側機の設置を少なくして、可能な限り早く、多数の車両に証明書失効リストを配布するための車々間通信による配布方式を提案している。
【０００５】
車両アドホックネットワークのようなネットワーク接続コンピューティング環境における大規模コンテンツ配信に使用される１つの機構は、ネットワークコーディングを使用したコンテンツ配信システムである。特許文献１では高速かつスケーラブルなコンテンツ配信を提供する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００６−３１６９３号公報
【非特許文献】
【０００７】
【非特許文献１】K.P. Laberteaux, J.J. Haas, Y.-C. Hu, “Security Certificate Revocation List Distribution for VANET”, Proceedings of the Fifth ACM International Workshop on VehiculAr Inter-NETworking (VANET 2008), ACM, San Francisco, 2008.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ある領域の車両が高密度になった場合、非特許文献１および特許文献１の方式では、証明書失効リストの要素を含んだパケット、または要素を符号化したパケットが、車両から同時に送信されるとパケット衝突が増大し、配信性能が劣化する。
【０００９】
本発明は上記点に鑑みて、車両が高密度な環境下でも効率的に証明書失効リストを配布できるようにすることを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するため、請求項１に記載の発明は、送信ノードから発信される証明書失効リストを、ランダムネットワーク符号化を用いた車々間通信により配布する証明書失効リストの配布方法を特徴としている。
【００１１】
請求項２に記載の発明は、請求項１に記載の証明書失効リストの配布方法に用いられる送信ノードであって、受け取った証明書失効リストをランダムネットワーク符号化で符号化し路車間通信で符号化データをブロードキャストする送信ノードを特徴としている。
【００１２】
請求項３に記載の発明は、請求項１に記載の証明書失効リストの配布方法に用いられる中継局であって、一定間隔ごとに、受信した符号化データを再符号化してブロードキャストする中継ノードを特徴としている。
【図面の簡単な説明】
【００１３】
【図１】本発明の各ノード間の関係を示す図である。
【図２】本発明の送信ノードの処理の流れを示す図である。
【図３】本発明の中継ノードの処理の流れを示す図である。
【図４】本発明の受信ノードの処理の流れを示す図である。
【図５】本発明のシミュレーション結果を示す図である。
【発明を実施するための形態】
【００１４】
本実施形態は、ネットワークコーディングを使用した無線マルチホップ通信により証明書失効リストの配布を行うもので、車両が高密度な環境下でも効率的に証明書失効リストを配布できるようにするために、ランダムネットワーク符号化を用いた車々間通信により証明書失効リストの配布を行う。
【００１５】
車両アドホックネットワークのような無線ネットワークでは複数のパケットの衝突によるパケットロスが発生する。複数のパケットを1つのパケットにネットワーク符号化して送信すれば、ネットワーク全体を伝搬するパケット数が減る。それに伴い衝突が減少し通信品質が向上する。
【００１６】
ネットワーク符号化とは、複数のデータを1つのデータに符号化して中継する符号化技術である。元のデータは複数経路から送られてきた相異なる符号化データから復号できる。
【００１７】
ネットワーク符号化の実装方法の1つにランダムネットワーク符号化がある。
【００１８】
ランダムネットワーク符号化では入力データをランダムな符号化ベクトルで符号化し、毎回異なる符号化データを出力する。符号化データは、復号せずにさらに再符号化できる。そして、送信ノードが直接に符号化したデータだけではなく、中継ノードが再符号化したデータと合わせて、受信ノードが入力データと同じ個数のデータを受信すれば元のデータを復号できる。
【００１９】
符号化ベクトルは復号に必要である。復号するノードに対する事前通信を不要にするために、符号化ベクトルと符号化データをパケットに含めて送信することがランダムネットワーク符号化の特徴である。
【００２０】
本実施形態は、路側機のような送信ノードから発信される証明書失効リストを配布するためのランダムネットワーク符号化を用いた車両アドホックネットワーク上のブロードキャスト通信方式である。
【００２１】
本実施形態では、図１に示した送信ノード（路側機）は認証局からインフラ通信で証明書失効リストを受け取る。受け取った証明書失効リストをランダムネットワーク符号化でＮ回符号化し路車間通信でＮ個の符号化データをブロードキャストする。中継ノードは受け取った複数の符号化データを1個の符号化データに再符号化して中継する。受信ノードは送信された符号化データと同じＮ個のデータを受信すれば復号する。
【００２２】
図２は送信ノード（路側機）が証明書失効リストを符号化して送信する流れを示している。送信ノードは認証局から証明書失効リストＸを受け取る（S01）。受け取った証明書失効リストＸはＮ個のデータに分割する（S02）。受け取った証明書失効リストはランダムな符号化ベクトルでＮ回符号化するため、現在の符号化回数をカウントする変数を用意し（S03）、証明書失効リストをＮ回符号化するまで符号化・送信処理を繰り返す（S04）。
【００２３】
符号化では、まず符号化に必要なランダムな符号化ベクトルＣを作成する（S05）。符号化ベクトルＣとデータＸを線形演算することで符号化し、符号化データｙを作成する（S06）。符号化ベクトルＣは復号に必要なため、符号化ベクトルＣと符号化データｙをパケットに含めてブロードキャストする（S07）。ブロードキャスト後は一定時間待機し（S08）、符号化回数をインクリメントしてから（S09）、次の符号化・送信処理を行う（S10）。
【００２４】
図３は受信した符号化データを再符号化してブロードキャストする中継ノードの流れを示している。中継ノードは一定間隔ごとに受信データを再符号化して中継するため、再符号化・中継処理を繰り返す（S11）。
【００２５】
受信パケットが送信データ数Ｎより少なくても一定間隔ごとに再符号化・中継処理を行う（S12）。まず、受信パケットｐｉから符号化データｙｉと符号化ベクトルＤｉを取り出す（S13）。符号化と同様再符号化でもランダムな符号化ベクトルで符号化するので符号化ベクトルＣを作成する（S14）。符号化ベクトルＣと符号化データｙｉを線形演算し、再符号化する（S15）。
【００２６】
復号には符号化データＹの係数ＣではなくＸの係数に相当する符号化ベクトルＤ’が必要なので符号化ベクトルを更新する。符号化ベクトルのＮ個の要素全てを更新するため、符号化ベクトルの何番目の要素を更新しているかを示す変数を用意する（S16）。符号化ベクトルのＮ個の要素全てを更新するまで更新処理を繰り返す（S17）。受信パケットに含まれる符号化ベクトルからなる行列Ｄに含まれる符号化ベクトルのｉ番目の要素の更新は、受信パケットに含まれる符号化ベクトルからなる行列Ｄに含まれる符号化ベクトルのｉ番目の要素からなるベクトルと符号化ベクトルＣの線形演算で行う（S18）。符号化ベクトルの更新後は更新回数をインクリメントし（S19）、符号化ベクトルＤのＮ番目の要素を更新するまで繰り返す（S20）。
【００２７】
符号化ベクトルの更新が終われば、更新した符号化ベクトルＤ’と再符号化したデータＺをパケットに含めてブロードキャストする（S21）。再符号化・中継処理の後は一定時間待機し（S22）、次の再符号化・中継処理を行う（S23）。
【００２８】
図４は受信した符号化データを復号する受信ノードの流れを示している。復号にはＮ個の符号化データが必要なので、現在の受信パケット数を格納する変数を用意する（S24）。Ｎ個のパケットを受信するまで受信処理を繰り返す（S25）。受信処理では、まず送信ノード／中継ノードがブロードキャストしたパケットが届くまで受信待機する（S26）。パケットｐｉを受信すると（S27）、パケットｐｉから符号化データＺｉと符号化ベクトルＤｉを取り出す（S28）。パケットの受信後は現在の受信パケット数をインクリメントし（S29）、Ｎ個のパケットを受信するまで受信処理を繰り返す（S30）。
【００２９】
復号に必要なＮ個のデータを受信すると復号する。受信パケットに含まれるＤはＸの係数に相当する符号化ベクトルなので、元のデータＸと受信した符号化ベクトルＤと符号化データＺの間にはＺ＝ＤＸの関係式が成り立つ（S31）。Ｄは受信パケットに含まれる符号化ベクトルＤｉからなる行列であり、これに逆行列が存在すればＸ＝Ｄ−１Ｚが成り立ち、ＤとＺからＸを復号する（S32）。
【００３０】
図５は、本実施形態（提案方式）と、符号化しない車々間通信（フラッディング）、複数台の路側機による路車間通信のみでの配信のシミュレーション結果を示している。
【００３１】
車両が高密度な環境下では、フラッディングではパケットロスが多数発生し、路側機１台での路車間通信のみで配信するよりも大きなリストを配信できるが、路側機４台での路車間通信のみで配信するよりも性能が良くない。本実施形態（提案方式）は、フラッディングよりも配信性能が高い。
【００３２】
１台の路側機が配信したデータを車々間通信で中継・配布する本実施形態（提案方式）は、１２台の路側機による路車間通信のみでの配布と同等の性能でデータを配信でき、路側機の台数を減らせるので、路側設備の設置コストを削減できる。
【００３３】
なお、上記した実施形態において、図２〜図４に示す各ステップは、それぞれの機能を実現する手段として把握されるものであり、具体的には送信ノード、中継ノード、受信ノードに備えられたコンピュータによって実行される。
【特許請求の範囲】
【請求項１】
送信ノードから発信される証明書失効リストを、ランダムネットワーク符号化を用いた車々間通信により配布することを特徴とする証明書失効リストの配布方法。
【請求項２】
請求項１に記載の証明書失効リストの配布方法に用いられる送信ノードであって、受け取った証明書失効リストをランダムネットワーク符号化で符号化し路車間通信で符号化データをブロードキャストすることを特徴とする送信ノード。
【請求項３】
請求項１に記載の証明書失効リストの配布方法に用いられる中継局であって、一定間隔ごとに、受信した符号化データを再符号化してブロードキャストすることを特徴とする中継ノード。
【請求項１】
送信ノードから発信される証明書失効リストを、ランダムネットワーク符号化を用いた車々間通信により配布することを特徴とする証明書失効リストの配布方法。
【請求項２】
請求項１に記載の証明書失効リストの配布方法に用いられる送信ノードであって、受け取った証明書失効リストをランダムネットワーク符号化で符号化し路車間通信で符号化データをブロードキャストすることを特徴とする送信ノード。
【請求項３】
請求項１に記載の証明書失効リストの配布方法に用いられる中継局であって、一定間隔ごとに、受信した符号化データを再符号化してブロードキャストすることを特徴とする中継ノード。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２０１２−１８２６４１（Ｐ２０１２−１８２６４１Ａ）
【公開日】平成２４年９月２０日（２０１２．９．２０）
【国際特許分類】
【出願番号】特願２０１１−４３９１７（Ｐ２０１１−４３９１７）
【出願日】平成２３年３月１日（２０１１．３．１）
【出願人】（３０４０２１２７７）国立大学法人 名古屋工業大学 (784)
【Ｆターム（参考）】
【公開日】平成２４年９月２０日（２０１２．９．２０）
【国際特許分類】
【出願日】平成２３年３月１日（２０１１．３．１）
【出願人】（３０４０２１２７７）国立大学法人 名古屋工業大学 (784)
【Ｆターム（参考）】
[ Back to top ]