(57)【特許請求の範囲】
【請求項１】
マルチキャストネットワークを構成する複数のノードの間のチャネル状態に関する情報を取得し、前記複数のノードのうちのソースノードを除いた残りのノードが受信したパケットに関する情報に基づいて、前記マルチキャストネットワークのトポロジ情報を抽出するトポロジ情報抽出部と、
前記トポロジ情報に基づいて、前記複数のノードのうちの前記ソースノードを除いた残りのノードの各々の予想パケット受信量（ここで、前記予想パケット受信量は、前記残りのノードの各々が目標パケット受信量以上のパケットを受信する確率が予め定められた閾値確率以上となるようにする前記残りのノードの各々のパケット受信量を意味する）を推定し、
前記残りのノードの各々に対して、前記残りのノードの予想パケット受信量に基づいて、前記残りのノードの各々が異なるノードからパケットを受信した後に追加的に受信しなければならないパケットの量を示す潜在的要求自由度を推定し、
前記予想パケット受信量及び前記潜在的要求自由度に基づいて、前記複数のノードのうちの前記ソースノードから送信されたパケットを中継するリレーノードを選択する、リレーノード選択部と、を備えることを特徴とするソースノード。
【請求項２】
前記トポロジ情報抽出部は、前記複数のノードのうちの前記ソースノードを除いた残りのノードのうちの第１ノードにトレーニングパケットを送信し、前記第１ノードが受信したトレーニングパケットに関する情報を含むトレーニングリポートパケットが前記第１ノードからフィードバックされることを特徴とする請求項１に記載のソースノード。
【請求項３】
前記トポロジ情報抽出部は、前記トレーニングリポートパケットを用いて前記第１ノードのパケット受信率を演算し、前記パケット受信率が予め定められた閾値レベル以上である場合、前記第１ノードをリレーノード候補として選択することを特徴とする請求項２に記載のソースノード。
【請求項４】
前記トポロジ情報抽出部は、前記複数のノードのうちの前記ソースノードを除いた残りのノードのうちから選択されたリレーノード候補が前記残りのノードのうちの第２ノードに前記トレーニングパケットを送信するようにするトレーニング下りパケットを前記リレーノード候補に送信することを特徴とする請求項２に記載のソースノード。
【請求項５】
前記トポロジ情報抽出部は、前記リレーノード候補が複数である場合、予め定められた順序に応じて前記複数のリレーノード候補に前記トレーニング下りパケットを送信することを特徴とする請求項４に記載のソースノード。
【請求項６】
前記トポロジ情報抽出部は、前記第２ノードが受信したトレーニングパケットに関する情報を前記リレーノード候補が取得した場合、前記リレーノード候補から前記第２ノードに関する情報及び前記第２ノードが受信したトレーニングパケットに関する情報を含むネイバーリポートパケットを受信することを特徴とする請求項４に記載のソースノード。
【請求項７】
前記トポロジ情報抽出部は、前記残りのノードのうちの一部のノードが受信したトレーニングパケットに関する情報を前記リレーノード候補が取得した場合、前記リレーノード候補から、前記一部のノードに前記トレーニングパケットを送信したノードに関する情報、前記一部のノードに関する情報、及び前記一部のノードが受信したトレーニングパケットに関する情報を含むブロックトレーニングリポートパケットを受信することを特徴とする請求項４に記載のソースノード。
【請求項８】
前記トポロジ情報抽出部は、前記複数のノードのうちの前記ソースノードを除いた残りのノードのうちの一部のノードをトレーニングノードとして選定し、前記選定されたトレーニングノードが受信したパケットに関する情報に基づいて前記トポロジ情報を抽出することを特徴とする請求項１に記載のソースノード。
【請求項９】
前記トポロジ情報抽出部は、前記複数のノードのうちの前記ソースノードを除いた残りのノードが収集した前記複数のノード間の前記チャネル状態に対する統計情報を受信し、前記統計情報に基づいて前記トポロジ情報を抽出することを特徴とする請求項１に記載のソースノード。
【請求項１０】
前記リレーノード選択部は、前記トポロジ情報に基づいて、前記複数のノードのうちの前記ソースノードを除いた残りのノードを１−ホップノードグループ及び２−ホップノードグループに分類し、複数のリレーノード候補のパケット送信が前記残りのノードのうちの少なくとも一部に及ぼす影響を考慮して前記複数のリレーノード候補のうちから前記リレーノードを選択することを特徴とする請求項１に記載のソースノード。
【請求項１１】
前記リレーノード選択部は、
前記潜在的要求自由度が低いノードを前記１−ホップノードグループに、前記潜在的要求自由度が高いノードを前記２−ホップノードグループに決定することを特徴とする請求項１０に記載のソースノード。
【請求項１２】
前記リレーノード選択部は、前記２−ホップノードグループに含まれる少なくとも１つのノードの各々に対して、前記複数のリレーノード候補の各々に対する前記２−ホップノードグループに含まれる少なくとも１つのノードの各々の前記潜在的要求自由度に基づいて、前記２−ホップノードグループに含まれる少なくとも１つのノードの各々が前記複数のリレーノード候補の各々に対して送信を要求するパケットの量を示す要求送信量を演算し、前記少なくとも１つのノードの各々の前記要求送信量に基づいて前記複数のリレーノード候補のうちから前記リレーノードを選択することを特徴とする請求項１０に記載のソースノード。
【請求項１３】
前記リレーノード選択部は、
前記少なくとも１つのノードの各々に対して、前記少なくとも１つのノードの各々の前記要求送信量のうちから量が最も少ない要求送信量を示す最小要求送信量を推定し、
前記複数のリレーノード候補の各々に対して、前記少なくとも１つのノードのうちの当該リレーノード候補に前記最小要求送信量でパケット送信をリクエストするノードから構成された最適ノードグループを抽出し、
前記複数のリレーノード候補の各々に対して、前記最適ノードグループに含まれるノードの前記最小要求送信量のうちから量が最も多い最小要求送信量を示す最大要求送信量を推定し、
前記複数のリレーノード候補の各々に対して、前記複数のリレーノード候補の各々の前記最大要求送信量による前記最適ノードグループに含まれるノードへのパケット送信が前記残りのノードのうちの少なくとも一部に及ぼす影響を示す第１ユーティリティを推定することを特徴とする請求項１２に記載のソースノード。
【請求項１４】
前記リレーノード選択部は、前記複数のリレーノード候補のうちから前記第１ユーティリティの大きさが最も大きいリレーノード候補を前記リレーノードとして決定することを特徴とする請求項１３に記載のソースノード。
【請求項１５】
前記リレーノード選択部は、前記複数のリレーノード候補のうちから前記最大要求送信量の大きさが最も大きいリレーノード候補を前記リレーノードとして決定することを特徴とする請求項１３に記載のソースノード。
【請求項１６】
前記リレーノード選択部は、前記選択されたリレーノードの総パケット送信量が予め定められた最大パケット送信量よりも小さい場合、前記潜在的要求自由度、前記要求送信量、前記最小要求送信量、前記最大要求送信量、及び前記第１ユーティリティを、前記選択されたリレーノードに基づいてアップデートし、前記複数のリレーノード候補のうちから前記リレーノードを選択することを特徴とする請求項１３に記載のソースノード。
【請求項１７】
前記リレーノード選択部は、
前記２−ホップノードグループに含まれるノードの各々に対して、前記複数のリレーノード候補の各々の前記２−ホップノードグループに含まれるノードへのパケット送信による前記２−ホップノードグループに含まれるノードの満足度を示す第２ユーティリティを推定し、
前記複数のリレーノード候補の各々に対して、前記２−ホップノードグループに含まれるノードの各々の第２ユーティリティに基づいて、前記複数のリレーノード候補の各々の前記パケット送信による前記２−ホップノードグループの満足度を示すネットワークユーティリティを推定し、
前記複数のリレーノード候補の各々のネットワークユーティリティに基づいて、前記複数のリレーノード候補のうちから前記リレーノードを選択することを特徴とする請求項１３に記載のソースノード。
【請求項１８】
前記リレーノード選択部は、前記リレーノード候補に送信するパケットの量による前記ネットワークユーティリティの傾きが変更されるごとに前記複数のリレーノード候補の各々の第２ユーティリティをアップデートし、前記複数のリレーノード候補のうちから前記リレーノード候補に送信するパケットの量による前記第２ユーティリティの傾きが最も大きいリレーノード候補を前記リレーノードとして選択することを特徴とする請求項１７に記載のソースノード。
【請求項１９】
ランダム行列を用いてオリジナルパケットを符号化されたパケットに変換して前記リレーノードに前記符号化されたパケットを送信し、且つ前記リレーノードから受信した前記符号化されたパケットに基づいて生成された生成子行列を用いて前記符号化されたパケットを前記オリジナルパケットに変換する変換部を更に含むことを特徴とする請求項１に記載のソースノード。
【請求項２０】
トポロジ情報抽出部によって、マルチキャストネットワークを構成する複数のノードの間のチャネル状態に関する情報を取得し、前記複数のノードのうちのソースノードを除いた残りのノードが受信したパケットに関する情報に基づいて、前記マルチキャストネットワークのトポロジ情報を抽出するステップと、
リレーノード選択部によって、
前記トポロジ情報に基づいて、前記複数のノードのうちの前記ソースノードを除いた残りのノードの各々の予想パケット受信量（ここで、前記予想パケット受信量は、前記残りのノードの各々が目標パケット受信量以上のパケットを受信する確率が予め定められた閾値確率以上となるようにする前記残りのノードの各々のパケット受信量を意味する）を推定するステップと、
前記残りのノードの各々に対して、前記残りのノードの予想パケット受信量に基づいて、前記残りのノードの各々が異なるノードからパケットを受信した後に追加的に受信しなければならないパケットの量を示す潜在的要求自由度を推定するステップと、
前記予想パケット受信量及び前記潜在的要求自由度に基づいて、前記複数のノードのうちの前記ソースノードから送信されたパケットを中継するリレーノードを選択するステップと、を有することを特徴とするソースノードの動作方法。
【請求項２１】
変換部によって、ランダム行列を用いてオリジナルパケットを符号化されたパケットに変換して前記リレーノードに前記符号化されたパケットを送信し、且つ前記リレーノードから受信した前記符号化されたパケットに基づいて生成された生成子行列を用いて前記符号化されたパケットを前記オリジナルパケットに変換するステップを更に含むことを特徴とする請求項２０に記載のソースノードの動作方法。
【請求項２２】
請求項２０に記載のソースノードの動作方法を実行するためのプログラムが記録されていることを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチキャストネットワークにおけるソースノード及びその動作方法に関する。
【背景技術】
【０００２】
今まで通信システムは主に人と人のみを連結する手段として用いられてきた。そのため現在の地球上に存在する機器のうち１％程度のみがネットワークに互いに接続して用いられている。しかし、通信技術の発達と機器統合による単一化傾向に応じて、スマートフォン、センサ機器、その他の通信機能を備えた様々な機器が巨大なネットワークを構成している。それだけではなく、多くの通信端末のユーザは、機器間の直接接続によってコンテンツ共有、同期化、出力及びゲームなどの様々なアプリケーションをより容易に活用している。このような市場の変化要求に反応するために、既存のインフラストラクチャを用いたセルラ通信を越える機器間の直接接続（Ｄｅｖｉｃｅ−ｔｏ−Ｄｅｖｉｃｅ通信）をサポートできる無線接続技術が生まれた。
マルチキャストは、ユニキャストと多くの面で差異がある。まず、マルチキャストは、サービスを受けるユーザが複数であるため、サービスが充分伝えられたかを判断することが容易ではない。サービス伝送の可否を判断しようとすれば、それに伴うオーバヘッドがユーザ数に応じて急激に増加するためである。また、多くのマルチキャスト／ブロードキャストサービスは、リアルタイムで伝えられなければならず、無線チャネルの特性上、時間、場所及びその他の多くの要因による困難を伴う。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
本発明の目的は、マルチキャストネットワークにおける効率的なリアルタイムサービス伝送を最小限のオーバヘッド追加で具現できるソースノード及びその動作方法を提供することにある。
【課題を解決するための手段】
【０００４】
一実施形態に係るソースノードは、マルチキャストネットワークを構成する複数のノード間のチャネル状態に関する情報を取得し、前記マルチキャストネットワークのトポロジ情報を抽出するトポロジ情報抽出部と、前記トポロジ情報に基づいて前記複数のノードのうちから、ソースノードから送信されたパケットを中継するリレーノードを選択するリレーノード選択部と、を含む。
【０００５】
前記トポロジ情報抽出部は、前記複数のノードのうち前記ソースノードを除いた残りのノードが受信したパケットに関する情報に基づいて前記トポロジ情報を抽出してもよい。
【０００６】
前記トポロジ情報抽出部は、前記複数のノードのうち前記ソースノードを除いた残りのノードのうち第１ノードにトレーニングパケットを送信し、前記第１ノードが受信したトレーニングパケットに関する情報を含むトレーニングリポートパケットが前記第１ノードからフィードバックされてもよい。
【０００７】
前記トポロジ情報抽出部は、前記トレーニングリポートパケットを用いて前記第１ノードのパケット受信率を演算し、前記パケット受信率が予め定められた閾値レベル以上である場合、前記第１ノードを前記リレーノード候補として選択してもよい。
【０００８】
前記トポロジ情報抽出部は、前記複数のノードのうち前記ソースノードを除いた残りのノードのうち選択されたリレーノード候補が前記残りのノードのうち第２ノードに前記トレーニングパケットを送信するようにするトレーニング下りパケットを前記リレーノード候補に送信してもよい。
【０００９】
前記トポロジ情報抽出部は、前記リレーノード候補が複数である場合、予め定められた順序に応じて前記複数のリレーノード候補に前記トレーニング下りパケットを送信してもよい。
【００１０】
前記トポロジ情報抽出部は、前記第２ノードが受信したトレーニングパケットに関する情報を前記リレーノード候補が取得した場合、前記リレーノード候補から、前記第２ノードに関する情報及び前記第２ノードが受信したトレーニングパケットに関する情報を含むネイバーリポートパケットを受信してもよい。
【００１１】
前記トポロジ情報抽出部は、前記残りのノードのうち一部のノードが受信したトレーニングパケットに関する情報を前記リレーノード候補が取得した場合、前記リレーノード候補から、前記一部のノードに前記トレーニングパケットを送信したノードに関する情報、前記一部のノードに関する情報及び前記一部のノードが受信したトレーニングパケットに関する情報を含むブロックトレーニングリポートパケットを受信してもよい。
【００１２】
前記トポロジ情報抽出部は、前記複数のノードのうち前記ソースノードを除いた残りのノードのうち一部のノードをトレーニングノードとして選定し、前記選定されたトレーニングノードが受信したパケットに関する情報に基づいて前記トポロジ情報を抽出してもよい。
【００１３】
前記トポロジ情報抽出部は、前記複数のノードのうち前記ソースノードを除いた残りのノードが収集した前記複数のノード間の前記チャネル状態に対する統計情報を受信し、前記統計情報に基づいて前記トポロジ情報を抽出してもよい。
【００１４】
前記リレーノード選択部は、前記トポロジ情報に基づいて、前記複数のノードのうち前記ソースノードを除いた残りのノードを１−ホップノードグループ及び２−ホップノードグループに分類し、複数のリレーノード候補のパケット送信が前記残りのノードのうち少なくとも一部に及ぼす影響を考慮して前記複数のリレーノード候補のうち前記リレーノードを選択してもよい。
【００１５】
前記リレーノード選択部は、前記トポロジ情報を用いて前記残りのノード各々の予想パケット受信量（ここで、前記予想パケット受信量は、前記残りのノード各々が目標パケット受信量以上のパケットを受信する確率が予め定められた閾値確率以上となるようにする前記残りのノード各々のパケット受信量を意味する）を推定し、前記残りのノード各々に対して、前記残りのノードの予想パケット受信量に基づいて、前記残りのノード各々が異なるノードからパケットを受信した後に追加的に受信しなければならないパケットの量を示す潜在的要求自由度を推定し、前記潜在的要求自由度が低いノードを前記１−ホップノードグループに、前記潜在的要求自由度が高いノードを前記２−ホップノードグループに決定してもよい。
【００１６】
前記リレーノード選択部は、前記２−ホップノードグループに含まれた少なくとも１つのノード各々に対して、前記複数のリレーノード候補各々に対する前記２−ホップノードグループに含まれた少なくとも１つのノード各々の前記潜在的要求自由度に基づいて、前記２−ホップノードグループに含まれた少なくとも１つのノード各々が、前記複数のリレーノード候補各々に対して送信を要求するパケットの量を示す要求送信量を演算し、前記少なくとも１つのノード各々の前記要求送信量に基づいて前記複数のリレーノード候補のうちから前記リレーノードを選択してもよい。
【００１７】
前記リレーノード選択部は、前記少なくとも１つのノード各々に対して、前記少なくとも１つのノード各々の前記要求送信量のうち量が最も少ない要求送信量を示す最小要求送信量を推定し、前記複数のリレーノード候補各々に対して、前記少なくとも１つのノードのうち当該リレーノード候補に前記最小要求送信量でパケット送信をリクエストするノードから構成された最適ノードグループを抽出し、前記複数のリレーノード候補各々に対して、前記最適ノードグループに含まれたノードの前記最小要求送信量のうち量が最も多い最小要求送信量を示す最大要求送信量を推定し、前記複数のリレーノード候補各々に対して、前記複数のリレーノード候補各々の前記最大要求送信量による前記最適ノードグループに含まれたノードへのパケット送信が、前記残りのノードのうち少なくとも一部に及ぼす影響を示す第１ユーティリティを推定してもよい。
【００１８】
前記リレーノード選択部は、前記複数のリレーノード候補のうち前記第１ユーティリティの大きさが最も大きいリレーノード候補を前記リレーノードとして決定してもよい。
【００１９】
前記リレーノード選択部は、前記複数のリレーノード候補のうち前記最大要求送信量の大きさが最も大きいリレーノード候補を前記リレーノードとして決定してもよい。
【００２０】
前記リレーノード選択部は、前記選択されたリレーノードの総パケット送信量が予め定められた最大パケット送信量よりも小さい場合、前記潜在的要求自由度、前記要求送信量、前記最小要求送信量、前記最大要求送信量、及び前記第１ユーティリティを、前記選択されたリレーノードに基づいてアップデートし、前記複数のリレーノード候補のうちから前記リレーノードを選択してもよい。
【００２１】
前記リレーノード選択部は、前記２−ホップノードグループに含まれたノード各々に対して、前記複数のリレーノード候補各々の前記２−ホップノードグループに含まれたノードへのパケット送信による前記２−ホップノードグループに含まれたノードの満足度を示す第２ユーティリティを推定し、前記複数のリレーノード候補各々に対して、前記２−ホップノードグループに含まれたノード各々の第２ユーティリティに基づいて、前記複数のリレーノード候補各々の前記パケット送信による前記２−ホップノードグループの満足度を示すネットワークユーティリティを推定し、前記複数のリレーノード候補各々のネットワークユーティリティに基づいて、前記複数のリレーノード候補のうちｋａｒａ前記リレーノードを選択してもよい。
【００２２】
前記リレーノード選択部は、前記リレーノード候補に送信するパケットの量による前記ネットワークユーティリティの傾きが変更されるごとに、前記複数のリレーノード候補各々の第２ユーティリティをアップデートし、前記複数のリレーノード候補のうち、前記リレーノード候補に送信するパケットの量による前記第２ユーティリティの傾きが最も大きいリレーノード候補を前記リレーノードとして選択してもよい。
【００２３】
一実施形態に係るノードは、ランダム行列を用いてオリジナルパケットを符号化されたパケットに変換する符号化部と、前記符号化されたパケットに基づいて生成された生成子行列を用いて、前記符号化されたパケットを前記オリジナルパケットに変換する復号化部とを含む。
【００２４】
前記符号化部は、前記オリジナルパケットを複数のサブパケットに分類し、前記複数のサブパケットと前記ランダム行列を演算して符号化されたデータを生成してもよい。
【００２５】
前記符号化部は、前記符号化されたデータに、前記符号化されたデータに関する情報を含む第１ヘッダを付加して前記符号化されたパケットを生成してもよい。
【００２６】
前記第１ヘッダは、前記オリジナルパケットの個数に関する情報、前記ランダム行列の長さに関する情報、前記符号化されたパケットの識別子に関する情報、前記ランダム行列の係数に関する情報、及び前記符号化されたパケットのタイプに関する情報のうち少なくとも１つを含んでもよい。
【００２７】
前記符号化されたパケットのタイプに関する情報は、前記符号化されたパケットを無線ＬＡＮモジュールに送信する以前に前記オリジナルパケットを前記無線ＬＡＮモジュールに送信する組織コード、及び前記符号化されたパケットのみを前記無線ＬＡＮモジュールに送信する非組織コードを含んでもよい。
【００２８】
前記符号化部は、前記符号化されたパケットに前記オリジナルパケットのイーサネット（登録商標）タイプに関する情報を含む第２ヘッダを付加してもよい。
【００２９】
前記符号化部は、イーサネット（登録商標）モジュールから受信した前記オリジナルパケットの個数がＫ個である場合、前記Ｋ個のランダム行列を用いて前記Ｋ個のオリジナルパケットをＮ個の符号化されたパケットに変換し、前記Ｎ個の符号化されたパケットを無線ＬＡＮモジュールに送信してもよい。
【００３０】
前記復号化部は、前記符号化されたパケットから抽出された行列係数に基づいて前記生成子行列を生成し、前記符号化されたパケットと前記生成子行列の逆行列を演算して前記オリジナルパケットを抽出してもよい。
【００３１】
前記復号化部は、ＬＵ分解方式を用いて前記符号化されたパケットを前記オリジナルパケットに変換してもよい。
【００３２】
前記復号化部は、前記符号化されたパケットをパケットキューリストに含まれたパケットキューに挿入し、前記パケットキューに挿入された前記符号化されたパケットが予め定められた個数以上である場合、前記符号化されたパケットを前記オリジナルパケットに変換してもよい。
【００３３】
前記パケットキューは、前記パケットキューリストに含まれた残りのパケットキューと連結リストの形態に接続され、前記パケットキューに挿入される前記符号化されたパケットの識別子に関する情報、及び前記符号化されたパケットが前記パケットキューに挿入される時間に関する情報を含んでもよい。
【００３４】
前記復号化部は、前記符号化されたパケットが前記パケットキューに挿入される時間が予め定められた閾時間より先である場合、前記パケットキューリストから前記パケットキューを削除してもよい。
【００３５】
前記復号化部は、無線ＬＡＮモジュールから受信した前記符号化されたパケットの識別子が予め定められた時間の間にオリジナルパケットに変換された符号化されたパケットの識別子と同一ではない場合、前記符号化されたパケットを前記パケットキューに挿入してもよい。
【００３６】
前記復号化部は、無線ＬＡＮモジュールから受信した前記符号化されたパケットの識別子が、前記パケットキューリストに含まれた複数のパケットキューに挿入された符号化されたパケットの識別子と同一ではない場合、前記符号化されたパケットを前記パケットキューに挿入してもよい。
【００３７】
前記復号化部は、前記生成子行列のうち前記符号化されたパケットに対応する成分が線形従属的である場合、前記パケットキューから前記符号化されたパケットを削除してもよい。
【００３８】
一実施形態に係るソースノードは、マルチキャストネットワークを構成する複数のノード間のチャネル状態に関する情報を取得し、前記マルチキャストネットワークのトポロジ情報を抽出するトポロジ情報抽出部と、前記トポロジ情報に基づいて、前記複数のノードのうちソースノードで送信されたパケットを中継するリレーノードを選択するリレーノード選択部と、ランダム行列を用いてオリジナルパケットを符号化されたパケットに変換して前記リレーノードに前記符号化されたパケットを送信し、且つ、前記リレーノードから受信した前記符号化されたパケットに基づいて生成された生成子行列を用いて前記符号化されたパケットを前記オリジナルパケットに変換する変換部と、を含む。
【００３９】
一実施形態に係るソースノードの動作方法は、マルチキャストネットワークを構成する複数のノード間のチャネル状態に関する情報を取得し、前記マルチキャストネットワークのトポロジ情報を抽出するステップと、前記トポロジ情報に基づいて前記複数のノードのうちから、ソースノードから送信されたパケットを中継するリレーノードを選択するステップと、を含む。
【００４０】
一実施形態に係るソースノードの動作方法は、ランダム行列を用いてオリジナルパケットを符号化されたパケットに変換するステップと、前記符号化されたパケットに基づいて、生成された生成子行列を用いて前記符号化されたパケットを前記オリジナルパケットに変換するステップとを含む。
【００４１】
一実施形態に係るソースノードの動作方法は、マルチキャストネットワークを構成する複数のノード間のチャネル状態に関する情報を取得し、前記マルチキャストネットワークのトポロジ情報を抽出するステップと、前記トポロジ情報に基づいて、前記複数のノードのうちソースノードから送信されたパケットを中継するリレーノードを選択するステップと、ランダム行列を用いてオリジナルパケットを符号化されたパケットに変換して前記リレーノードに前記符号化されたパケットを送信し、且つ前記リレーノードから受信した前記符号化されたパケットに基づいて生成された生成子行列を用いて前記符号化されたパケットを前記オリジナルパケットに変換するステップとを含む。
【発明の効果】
【００４２】
本発明によると、マルチキャストネットワークにおいて、ソースノードが、前記マルチキャストネットワークを構成する複数のノード間のチャネル状態に関する情報を取得し前記マルチキャストネットワークのトポロジ情報を抽出するトポロジ情報抽出部と、前記トポロジ情報に基づいて前記複数のノードのうちから、ソースノードから送信されたパケットを中継するリレーノードを選択するリレーノード選択部と、を含むので、効率的なリアルタイムサービス伝送を最小限のオーバヘッド追加で具現できるソースノード及びノード、並びにそれらの動作方法を提供できる。
【図面の簡単な説明】
【００４３】
【図１】一実施形態に係るマルチキャストネットワークにおけるノードを示すブロック図である。
【図２】一実施形態に係るソースノードを示すブロック図である。
【図３】一実施形態に係るパケットの構造を説明するための図である。
【図４】一実施形態に係る複数のノードの動作を説明するための図である。
【図５】一実施形態に係るリレーノード選択方式を説明するための動作フローチャートである。
【図６】他の一実施形態に係るリレーノード選択方式を説明するための動作フローチャートである。
【図７】一実施形態に係るリレーノードの選択を説明するための図である。
【図８】（Ａ）は、一実施形態に係るネットワークユーティリティを説明するための図であり、            （Ｂ）は、一実施形態に係るネットワークユーティリティを説明するための図である。
【図９】更なる一実施形態に係るリレーノード選択方式を説明するための動作フローチャートである。
【図１０】一実施形態に係るリレー選択パケットの構造を説明するための図である。
【図１１】一実施形態に係るノードを示すブロック図である。
【図１２】一実施形態に係る符号化方式を説明するための図である。
【図１３】一実施形態に係る符号化されたパケットの構造を説明するための図である。
【図１４】一実施形態に係る復号化方式を説明するための図である。
【図１５】一実施形態に係るソースノードの動作方法を示した動作フローチャートである。
【図１６】一実施形態に係るノードの動作方法を示した動作フローチャートである。
【図１７】他の一実施形態に係るソースノードの動作方法を示した動作フローチャートである。
【発明を実施するための形態】
【００４４】
以下、添付する図面を参照しながら実施形態を詳細に説明する。各図面に提示される同一の参照符号は同一の部材を示す。
【００４５】
以下で説明する実施形態には様々な変更が加えられ得る。下記で説明する実施形態は本発明の範囲を該実施形態に限定するためのものではなく、これに対応する全ての変更、均等物ないし代替物を含むものとして理解しなければならない。
【００４６】
以下に説明する実施形態で用いる用語は、単に特定の実施形態を説明するために用いられており、実施形態を限定しようとする意図はない。単数の表現は文脈上、明らかに単数の表現を意味しない限り複数の表現を含む。本明細書において、「含む」又は「有する」などの用語は、明細書上に記載された特徴、数字、段階、動作、構成要素、部品又はこれを組み合わせたものの存在を指定するためのものであって、１つ又はそれ以上の他の特徴や数字、段階、動作、構成要素、部品又はこれを組み合わせたものなどの存在又は付加可能性を予め排除しないものとして理解しなければならない。
【００４７】
特別に定義されない限り、ここで用いられる全ての技術的又は科学的な用語を含む用語は実施形態が属する技術分野で通常の知識を有する者によって一般的に理解されるものと同じ意味を有する。一般的に用いられる予め定義されているような用語は、関連技術の文脈上に有する意味と一致する意味を有するものと解釈すべきであり、本出願で明らかに定義しない限り、理想的な意味、又は過度に形式的な意味に解釈すべきではない。
【００４８】
また、添付の図面を参照して説明する際に、図面番号に関係なく同じ構成要素には同じ参照符号を付与し、それに対する重複する説明は省略する。実施形態を説明する際に関連する公知技術に対する具体的な説明が実施形態の要旨を却って曖昧にすると判断される場合、その詳細な説明を省略する。
＜マルチキャストネットワークにおけるノード＞
【００４９】
図１は、一実施形態に係るマルチキャストネットワークにおけるノード１００を示すブロック図である。
【００５０】
図１を参照すると、マルチキャストネットワークは複数のこのようなノード１００を含む。マルチキャストネットワークにおいてソースノードは複数のノード１００にパケットを送信する。この場合、ソースノードは、複数のノード１００のうちからリレーノードを選択し、リレーノードを経由して残りのノードにパケットを送信する。これによりソースノードの送信カバレッジは拡大し、ソースノードのパケット送信効率は向上する。
【００５１】
一実施形態では、マルチキャストネットワークにおいてノード１００は、イーサネット（登録商標）モジュール１１０、無線ＬＡＮモジュール１２０、及びマトリックスネットワークコーディングモジュール１３０を含む。マトリックスネットワークコーディングモジュール１３０は、イーサネット（登録商標）モジュール１１０と無線ＬＡＮモジュール１２０との間に位置する。一実施形態では、マトリックスネットワークコーディングモジュール（ＭＮＣモジュール）１３０の位置は、イーサネット（登録商標）モジュール１１０と無線ＬＡＮモジュール１２０との間に限定されない。例えば、無線ＬＡＮモジュール１２０がイーサネット（登録商標）モジュール１１０を経由することなく、Ｌ３レイヤからパケットを受信する場合、マトリックスネットワークコーディングモジュール１３０は無線ＬＡＮモジュール１２０上に位置することもある。
【００５２】
マトリックスネットワークコーディングモジュール１３０は、トポロジ情報抽出部１４０、リレーノード選択部１５０、及び変換部１６０を含む。トポロジ情報抽出部１４０は、マルチキャストネットワークを構成する複数のノード１００間のチャネル状態に関する情報を取得し、マルチキャストネットワークのトポロジ情報を抽出する。例えば、ノード１００は、マルチキャストネットワーク内の他のノードとパケットを送受信する場合、トポロジ情報抽出部１４０は、無線ＬＡＮモジュール１２０を介して送受信したパケットを取得する。トポロジ情報抽出部１４０は、送受信したパケットに基づいてノード１００と該他のノードとの間のチャネル状態に関する情報を抽出する。また、トポロジ情報抽出部１４０は、ノード１００自身を除く２つの他のノードが相互間に送受信したパケットを無線ＬＡＮモジュール１２０を介して取得し、トポロジ情報抽出部１４０は、無線ＬＡＮモジュール１２０を介して取得したパケットに基づいて、他のノード間のチャネル状態に関する情報を抽出する。このようにして、トポロジ情報抽出部１４０は、ノード１００と他のノードとの間のチャネル状態に関する情報及び他のノード間のチャネル状態に関する情報を用いて、マルチキャストネットワークのトポロジ情報を抽出する。
【００５３】
リレーノード選択部１５０は、トポロジ情報に基づいてマルチキャストネットワークを構成している複数のノードのうち、ノード１００から送信されたパケットを中継するべきリレーノードを選択する。また、リレーノード選択部１５０は、リレーノードのパケット送信量を決定する。一実施形態では、ノード１００がソースノードではない場合、ノード１００はソースノードの選択によってリレーノードになり得る。
【００５４】
変換部１６０はランダム行列を用いて、イーサネット（登録商標）モジュール１１０から受信したオリジナルパケットを符号化されたパケットに変換し、符号化されたパケットを無線ＬＡＮモジュール１２０に送信する。そのようにして、符号化されたパケットは、無線ＬＡＮモジュール１２０を介してリレーノード又は他のノードに送信する。また、ノード１００がリレーノード又は他のノードから符号化されたパケットを受信する場合、変換部１６０は無線ＬＡＮモジュール１２０を介して符号化されたパケットを受信し、符号化されたパケットに基づいて生成された生成子行列を用いて符号化されたパケットをオリジナルパケットに変換し、オリジナルパケットをイーサネット（登録商標）モジュール１１０に送信する。その際、ノード１００がソースノードである場合、ノード１００は、トポロジ情報を取得して複数のノードのうちからリレーノードを選択し、リレーノードに符号化されたパケットを送信し、一方、符号化されたパケットをリレーノードから受信して符号化されたパケットをオリジナルパケットに復号化する。また、ノード１００がソースノードではない場合、ノード１００は、ソースノードの制御によってリレーノードとして選択され得る。ノード１００がリレーノードとして選択される場合、ノード１００はソースノードから符号化されたパケットを受信し、符号化されたパケットを他のノードに中継する。また、ノード１００がリレーノードとして選択されない場合、ノード１００はリレーノードから符号化されたパケットを受信し、符号化されたパケットをオリジナルパケットに復号化する。
＜トポロジ情報抽出方式＞
【００５５】
図２は、一実施形態に係るソースノードを示すブロック図である。
【００５６】
図２を参照すると、ソースノード２００は、トポロジ情報抽出部２１０及びリレーノード選択部２２０を含む。一実施形態では、ソースノード２００は、変換部（図示せず）をさらに含み得る。変換部（図示せず）は、ソースノード２００がランダム行列を用いてオリジナルパケットを符号化されたパケットに符号化し、符号化されたパケットに基づいて生成された生成子行列を用いて符号化されたパケットをオリジナルパケットに復号化する。
【００５７】
トポロジ情報抽出部２１０は、マルチキャストネットワークに含まれる複数のノードのうち、ソースノード２００を除いた残りのノードが受信したパケットに関する情報に基づいてトポロジ情報を抽出する。トポロジ情報抽出部２１０は、残りのノードが受信したパケットに関する情報を用いて、ソースノード２００と残りのノードとの間のチャネル状態及び残りのノード間のチャネル状態に関する情報を取得し、取得したチャネル状態に関する情報を用いてトポロジ情報を推定する。
【００５８】
一実施形態において、トポロジ情報抽出部２１０は、ソースノード２００の周辺ノードにトレーニングパケットを送信し、トレーニングパケットを受信した周辺ノードからトレーニングリポートパケットがフィードバックされる。ここで、特定ノードの周辺ノードは、特定ノードと距離の相対的に近いノード（即ち、特定ノードと相対的に近い位置にあるノード）を意味し、実施形態によってはマルチキャストネットワークに含まれた全てのノードを意味する。トレーニングパケットは、トポロジ情報抽出部２１０がパケット受信率を測定するためにパケット受信率を測定しようとするノードに送信するパケットを意味する。トレーニングリポートパケットは、トレーニングパケットを受信したノードがトレーニングパケットを送信したノードにトレーニングパケットの受信に関する報告を行うためのパケットを意味する。トレーニングリポートパケットは、周辺ノードが受信したトレーニングパケットに関する情報を含む。例えば、トポロジ情報抽出部２１０が第１ノードにＫ個のトレーニングパケットを送信するとき、ソースノード２００と第１ノードとの間のチャネル状態に応じて、第１ノードは（Ｋ−２）個のトレーニングパケットを受信する場合がある。これに対して第１ノードは、受信したトレーニングパケットの個数に関する情報を含むトレーニングリポートパケットを生成し、生成したトレーニングレポートパケットをトポロジ情報抽出部２１０に送信する。
【００５９】
また、トポロジ情報抽出部２１０は、トレーニングリポートパケットを用いてトレーニングリポートパケットを送信した周辺ノードのパケット受信率を演算する。一実施形態では、トポロジ情報抽出部２１０は、パケット受信率が予め定められた閾値レベル以上であるノードをリレーノード候補として選択する。例えば、第１ノードで送信したトレーニングリポートパケットから、トポロジ情報抽出部２１０は、トポロジ情報抽出部２１０が１０個のトレーニングパケットを第１ノードに送信し、第１ノードが８個のトレーニングパケットを受信し、第１ノードのパケット受信率を８０％として算出する。ここで、予め定められた閾値レベルが７０％である場合、トポロジ情報抽出部２１０は、該予め定められた閾値レベル以上のパケット受信率を有する第１ノードをリレーノード候補として決定する。
【００６０】
また、トポロジ情報抽出部２１０は、リレーノード候補にトレーニング下りパケットを送信する。ここで、トレーニング下りパケットは、トレーニング下りパケットを受信したノードがトレーニング下りパケットを受信したノードの周辺ノードにトレーニングパケットを送信するようにするパケットである。その際リレーノード候補は、周辺ノードにトレーニングパケットを送信し、トレーニングパケットを受信した周辺ノードから周辺ノードが受信したトレーニングパケットの個数に関する情報を含むトレーニングリポートパケットを受信する。リレーノード候補は、トレーニングリポートパケットの受信に応答してネイバー（ここで「ネイバー」は、近隣ノードを意味する）リポートパケット（ｎｅｉｇｈｂｏｒ  ｒｅｐｏｒｔ  ｐａｃｋｅｔ）を生成し、ネイバーリポートパケットをトポロジ情報抽出部２１０に送信する。ここで、ネイバーリポートパケットは、トレーニング下りパケットによってリレーノード候補が周辺ノードにトレーニングパケットを送信し、リレーノード候補が周辺ノードからトレーニングリポートパケットを受信した場合、受信したトレーニングリポートパケットをソースノードに報告するためのパケットを意味する。
ネイバーリポートフィールドは、トレーニングリポートパケットを送信した周辺ノードに関する情報、及び周辺ノードが受信したトレーニングパケットに関する情報を含む。例えば、ソースノード２００と第２ノードとの間の距離が相対的に遠い場合、第２ノードのパケット受信率を抽出するためトポロジ情報抽出部２１０はソースノード２００との距離が相対的に近い第１ノードにトレーニング下りパケットを送信し、第１ノードは、トレーニング下りパケットの受信に応答して第２ノードにトレーニングパケットを送信する。第２ノードは、受信したトレーニングパケットの個数に関する情報を含むトレーニングリポートパケットを生成し、該トレーニングリポートパケットを第１ノードに送信する。第１ノードは、受信したトレーニングリポートパケットに基づいて、第２ノードに関する情報及び第２ノードが受信したトレーニングパケットに関する情報を含むネイバーリポートパケットを生成する。ソースノード２００は、第１ノードからネイバーリポートパケットを受信し、ネイバーリポートパケットを用いて、第１ノードに対する第２ノードのパケット受信率を演算する。
【００６１】
一実施形態では、トポロジ情報抽出部２１０が送信するトレーニングパケットとリレーノード候補が送信するトレーニングパケットとを区別する。例えば、ソースノード２００が送信するトレーニングパケットはタイプフィールドのフィールド値が１であり、リレーノード候補が送信するトレーニングパケットはタイプフィールドのフィールド値が２である。また、トポロジ情報抽出部２１０が受信するトレーニングリポートパケットと、リレーノード候補が受信するトレーニングリポートパケットとは区別される。例えば、トポロジ情報抽出部２１０が受信するトレーニングリポートパケットは、タイプフィールドのフィールド値が３であり、リレーノード候補が受信するトレーニングリポートパケットはタイプフィールドのフィールド値が４である。
【００６２】
また、ソースノード２００の周辺ノードが複数の他のノードからトレーニングリポートパケットを取得した場合、トポロジ情報抽出部２１０は、ソースノード２００の周辺ノードからブロックトレーニングリポートパケット（ｂｌｏｃｋ  ｔｒａｉｎｉｎｇ  ｒｅｐｏｒｔ  ｐａｃｋｅｔ）を受信する。ここで、ブロックトレーニングリポートパケットは、ソースノード以外のノードが複数の他のノードからトレーニングリポートパケットを受信した場合、受信したトレーニングリポートパケットをソースノードに報告するためのパケットを意味する。ブロックトレーニングリポートパケットは、複数の他のノードにトレーニングパケットを送信したノードに関する情報、複数の他のノードに関する情報、及び複数の他のノードが受信したトレーニングパケットに関する情報を含む。
例えば、トポロジ情報抽出部２１０がリレーノード候補の第１ノードにトレーニング下りパケットを送信し、トレーニング下りパケットの受信に応答して第１ノードは第２ノード及び第３ノードにトレーニングパケットを送信する。第１ノードは、第２ノード及び第３ノード各々からトレーニングリポートパケットを受信し、受信したトレーニングリポートパケットを用いてブロックトレーニングリポートパケットを生成する。ここで、ブロックトレーニングリポートパケットは、第１ノードに関する情報、第２ノード及び第３ノードに関する情報、及び第２ノード及び第３ノードが受信したトレーニングパケットに関する情報を含む。トポロジ情報抽出部２１０は、第１ノードからブロックトレーニングリポートパケットを受信し、ブロックトレーニングリポートパケットから第２ノード及び第３ノードの各々と第１ノード間のチャネル状態を推定する。
【００６３】
一実施形態において、トポロジ情報抽出部２１０は、マルチキャストネットワークに含まれた複数のノードのうち一部のノードをトレーニングノードとして選定し、複数のノードが一般パケットを送受信する途中周期的又は非周期的に選定されたトレーニングノードが受信したパケットに関する情報に基づいてトポロジ情報を抽出する。従って、トポロジ情報抽出部２１０は、複数のノード全体ではない一部のノードとトポロジ情報を抽出するためのパケットを送受信し、そのためにマルチキャストネットワークの負荷が減少し得る。
【００６４】
一実施形態において、トポロジ情報抽出部２１０は、マルチキャストネットワークに含まれた複数のノードが一般パケットを送受信する際、複数のノードは、該複数のノード間のチャネル状態を持続的にモニタリング及びアップデートしてチャネル状態に対する統計情報をトポロジ情報抽出部２１０に送信する。トポロジ情報抽出部２１０は、受信した複数のノード間のチャネル状態に関する情報に基づいてトポロジ情報を抽出する。
【００６５】
図３は、一実施形態に係るパケットの構造を説明するための図である。図３及び図４に対する説明で、ソースノードの動作は図２に示すトポロジ情報抽出部２１０の動作を示す。
【００６６】
図３を参照すると、ソースノードは、トレーニングパケット３１０、トレーニングリポートパケット３２０、トレーニング下りパケット３３０、ネイバーリポートパケット３４０、及びブロックトレーニングリポートパケット３５０を用いてマルチキャストネットワークを構成する複数のノード間のチャネル状態に関する情報を取得する。
【００６７】
トレーニングパケット３１０は、ソースノードがパケット受信率を測定するためにパケット受信率を測定しようとするノードに送信するパケットを意味する。トレーニングパケット３１０は、イーサヘッダ３１１、タイプフィールド３１２、送信量フィールド３１３、シーケンスフィールド３１４、及びデータフィールド３１５を含む。イーサヘッダ３１１はトレーニングパケット３１０のイーサネット（登録商標）タイプを示し、タイプフィールド３１２はトレーニングパケット３１０の属性を示す。例えば、タイプフィールド３１２のフィールド値が１である場合、トレーニングパケット３１０はソースノードから送信されるトレーニングパケットであり、タイプフィールド３１２のフィールド値が２である場合、トレーニングパケット３１０はソースノード以外の他のノードから送信されるトレーニングパケットである。
送信量フィールド３１３はノードから送信されるトレーニングパケットの全体送信個数を示し、シーケンスフィールド３１４はノードから送信されるトレーニングパケットのうち、トレーニングパケット３１０が何番目のトレーニングパケットであるかに関する情報を含む。データフィールド３１５は、ガロアフィールド（ｇａｌｏｉｓ  ｆｉｅｌｄ）上におけるランダムデータを含む。一実施形態では、データフィールド３１５は、実際ノードが送受信するパケットの長さと同一である。例えば、ソースノードが第１ノードに１３５３ｂｙｔｅｓのパケットを送受信する場合、ソースノードは、データフィールド３１５を１３５３ｂｙｔｅｓに設定する。
【００６８】
トレーニングリポートパケット３２０は、トレーニングパケットを受信したノードがトレーニングパケットを送信したノードにトレーニングパケットの受信に対する報告をするためのパケットを意味する。トレーニングリポートパケット３２０は、イーサヘッダ３２１、タイプフィールド３２２、送信量フィールド３２３、受信量フィールド３２４、及び処理率フィールド３２５を含む。イーサヘッダ３２１はトレーニングリポートパケット３２０のイーサネット（登録商標）タイプを示し、タイプフィールド３２２はトレーニングリポートパケット３２０の属性を示す。
例えば、タイプフィールド３２２のフィールド値が３である場合、トレーニングリポートパケット３２０は、ソースノードから送信されるトレーニングパケットに対するトレーニングリポートパケットであり、タイプフィールド３２２のフィールド値が４である場合、トレーニングリポートパケット３２０は、ソースノード以外の他のノードから送信されるトレーニングパケットに対するトレーニングリポートパケットである。送信量フィールド３２３はトレーニングパケットの全体送信個数を示し、受信量フィールド３２４はノードが実際に受信したトレーニングパケットの個数を示す。処理量フィールド３２５は、トレーニングリポートパケット３２０を送信するノードが測定した処理量を示す。
【００６９】
トレーニング下りパケット３３０は、トレーニング下りパケットを受信したノードがトレーニング下りパケットを受信したノードの周辺ノードにトレーニングパケットを送信するようにするパケットを意味する。トレーニング下りパケット３３０は、イーサヘッダ３３１及びタイプフィールド３３２を含む。イーサヘッダ３３１はトレーニング下りパケット３３０のイーサネット（登録商標）タイプを示し、タイプフィールド３３２はトレーニング下りパケット３３０の属性を示す。一実施形態では、トレーニング下りパケット３３０のタイプフィールド３３２のフィールド値は５である。
【００７０】
ネイバーリポートパケット３４０は、トレーニング下りパケットによりリレーノード候補が周辺ノードにトレーニングパケットを送信し、リレーノード候補が周辺ノードからトレーニングリポートパケットを受信した場合、受信したトレーニングリポートパケットをソースノードに報告するためのパケットを意味する。ネイバーリポートパケット３４０は、イーサヘッダ３４１、タイプフィールド３４２、リポートパケット数量フィールド３４３、アドレスフィールド３４４、送信量フィールド３４５、受信量フィールド３４６、処理量フィールド３４７を含む。
イーサヘッダ３４１はネイバーリポートパケット３４０のイーサネット（登録商標）タイプを示し、タイプフィールド３４２はネイバーリポートパケット３４０の属性を示す。例えば、タイプフィールド３４２のフィールド値は６である。リポートパケット数量フィールド３４３は、ネイバーリポートパケット３４０が報告するトレーニングリポートパケットの個数を示し、アドレスフィールド３４４は、ｎ番目のトレーニングリポートフィールドに対応するノードのＭＡＣアドレスを示し、送信量フィールド３４５は、ｎ番目のトレーニングリポートフィールドに対応するノードに送信したトレーニングパケットの個数を示し、受信量フィールド３４６は、ｎ番目のトレーニングリポートフィールドに対応するノードが実際に受信したトレーニングパケットの個数を示す。処理量フィールド３４７は、ネイバーリポートパケット３４０が報告するトレーニングリポートパケット各々に対応するノードの測定処理量を示す。
【００７１】
ブロックトレーニングリポートパケット３５０は、ソースノード以外のノードが他のノードからトレーニングリポートパケットを受信した場合、受信したトレーニングリポートパケットをソースノードに報告するためのパケットを意味する。ブロックトレーニングリポートパケット３５０は、イーサヘッダ３５１、タイプフィールド３５２、リポートパケット数量フィールド３５３、受信者アドレスフィールド３５４、送信者アドレスフィールド３５５、送信量フィールド３５６、受信量フィールド３５７、処理量フィールド３５８を含む。
【００７２】
イーサヘッダ３５１はブロックトレーニングリポートパケット３５０のイーサネット（登録商標）タイプを示し、タイプフィールド３５２はブロックトレーニングリポートパケット３５０の属性を示す。例えば、タイプフィールド３５２のフィールド値は７である。リポートパケット数量フィールド３５３は、ブロックトレーニングリポートパケット３５０を生成するノードが受信したトレーニングリポートパケットの個数を示し、受信者アドレスフィールド３５４は、ｎ番目のトレーニングリポートフィールドに対応するノードのアドレスを示し、送信者アドレスフィールド３５５は、ｎ番目のトレーニングリポートフィールドに対応するノードにトレーニングパケットを送信したノードのアドレスを示し、送信量フィールド３５６は、ｎ番目のトレーニングリポートフィールドに対応するノードに送信したトレーニングパケットの個数を示し、受信量フィールド３５７は、ｎ番目のトレーニングリポートフィールドに対応するノードが実際に受信したトレーニングパケットの個数を示す。処理量フィールド３５８は、ブロックトレーニングリポートパケット３５０が報告するトレーニングリポートパケット各々に対応するノードが測定した処理量を示す。
【００７３】
図４は、一実施形態に係る複数のノードの動作を説明するための図である。
【００７４】
図４を参照すると、マルチキャストネットワークは、ソースノード４１０、第１ノード４２１、第２ノード４２２、第３ノード４３１、及び第４ノード４３２を含む。ここで例えば、第１ノード４２１及び第２ノード４２２は、ソースノード４１０からパケットを受信する１−ホップノードであり、第３ノード４３１及び第４ノード４３２は、１−ホップノードからパケットを受信する２−ホップノードである。
【００７５】
ソースノード４１０は、予め定められた周期によりトポロジ情報を抽出するか、又は外部からの制御によりトポロジ情報を抽出する。ソースノード４１０は、第１ノード４２１及び第２ノード４２２にマルチキャストでトレーニングパケットを送信する。第１ノード４２１及び第２ノード４２２は、受信したトレーニングパケットの個数を測定し、トレーニングパケットの受信に応答してトレーニングリポートパケットをユニキャストでソースノード４１０に送信する。ソースノード４１０は、受信したトレーニングリポートパケットを用いて第１ノード４２１及び第２ノード４２２のパケット受信率を演算し、第１ノード４２１及び第２ノード４２２のパケット受信率が予め定められた閾値レベル以上である場合、第１ノード４２１及び第２ノード４２２をリレーノード候補として選択する。
ソースノード４１０は、トレーニングリポートパケットを受信した後、予め定められた時間が経過した後に、予め定められた規則に応じてリレーノード候補の第１ノード４２１及び第２ノード４２２のうち第１ノード４２１に先にトレーニング下りパケットを送信する。ソースノード４１０は、第１ノード４２１からネイバーリポートパケットを受信した後、第２ノード４２２にトレーニング下りパケットを送信する。一実施形態では、予め定められた時間の間に第１ノード４２１からネイバーリポートパケットを受信できない場合、ソースノード４１０は、第１ノード４２１にネイバーリポートパケットの再送信を要求する。もし、最大再送信回数に達するまで、ソースノード４１０が第１ノード４２１からネイバーリポートパケットを受信できない場合、ソースノード４１０は、第２ノード４２２にトレーニング下りパケットを送信する。
トレーニング下りパケットを受信した第１ノード４２１は、第３ノード４３１及び第４ノード４３２にトレーニングパケットを送信する。第１ノード４２１は、第３ノード４３１及び第４ノード４３２からトレーニングリポートパケットを受信し、予め定められた時間の経過後、受信したトレーニングリポートパケットに基づいてネイバーリポートパケットを生成し、生成したネイバーリポートパケットをソースノード４１０に送信する。一実施形態では、第１ノード４２１とソースノード４１０との間のチャネル状態が良好ではない場合、第１ノード４２１は、第３ノード４３１及び第４ノード４３２から受信したトレーニングリポートパケットに基づいてブロックトレーニングリポートパケットを生成し、生成したブロックトレーニングリポートパケットを第２ノード４２２に送信する。第２ノード４２２は、第１ノード４２１から受信したブロックトレーニングリポートパケットをソースノード４１０に送信する。ソースノード４１０は、他のノード４２１、４２２、４３１、４３２から受信したトレーニングリポートパケット、ネイバーリポートパケット、又はブロックトレーニングリポートパケットを用いてマルチキャストネットワークのトポロジ情報を抽出できる。
＜リレーノード選択方式＞
【００７６】
図２を参照すると、リレーノード選択部２２０は、トポロジ情報抽出部２１０で抽出されたトポロジ情報に基づいてマルチキャストネットワークを構成する複数のノードのうちからリレーノードを選択する。ここで、リレーノードは、ソースノード２００からパケットを受信し、受信したパケットを他のノードに中継するノード意味する。リレーノード選択部２２０は、トポロジ情報に基づいて複数のノードのうち、ソースノード２００を除いた残りのノードを１−ホップノードグループ及び２−ホップノードグループに分類し、複数のリレーノード候補のパケット送信が残りのノードのうち少なくとも一部に及ぼす影響を考慮して、複数のリレーノード候補のうちからリレーノードを選択する。リレーノード選択部２２０の具体的な動作については、図５乃至図１０を参照して詳細に説明する。図５乃至図１０に関する説明で、ソースノードの動作は図２に示すリレーノード選択部２２０の動作を示す。
【００７７】
図５乃至図１０を説明するために、以下ではリレーノード選択部２２０で用いられるパラメータについて定義する。
【００７８】
［１］予想パケット受信量
予想パケット受信量は、パケット送信成功率が一定の環境で、受信ノードが目標パケット受信量以上のパケットを受信する確率が閾値確率以上になるようにする受信ノードのパケット受信量を示す。ここで、受信ノードは、２−ホップノードを意味する。送信ノードのパケット送信成功率がｐであり、送信ノードのパケット送信と異なるノードへのパケット送信は互いに独立的であると仮定するとき、受信ノードが目標受信量だけパケットを受信する確率は下記の数式（１）のように示される。
【００７９】
【数１】
0006578137.tif 000002
【００８０】
ここで、Ｘは受信ノードのパケット受信量を示し、ｋは目標受信量を示し、Ｎは送信ノードのパケット送信量を示し、ｐは送信ノードのパケット送信成功率を示す。
【００８１】
また、受信ノードが目標パケット受信量以上のパケットを受信する確率が閾値確率以上になるようにする受信ノードのパケット受信量の予想パケット受信量は、下記の数式（２）のように示される。
【００８２】
【数２】
0006578137.tif 000003
【００８３】
ここで、Ｎは送信ノードのパケット送信量を示し、ｐは送信ノードのパケット送信成功率を示し、Ｐｔｈは閾値確率を示す。Ｘは受信ノードのパケット受信量を示し、ｋは目標受信量を示し、ｋ＊は予想パケット受信量を示す。そのため、予想パケット受信量ｋ＊（Ｎ，ｐ，Ｐｔｈ）は、パケット送信成功率がｐである環境で送信ノードがＮ個のパケットを送信するとき、受信ノードが目標パケット受信量以上のパケットを受信する確率が閾値確率Ｐｔｈ以上になるようにする受信ノードのパケット受信量を意味する。予想パケット受信量ｋ＊（Ｎ，ｐ，Ｐｔｈ）の演算は算出複雑度が高い場合がある。そのような演算を回避するため、予想パケット受信量ｋ＊（Ｎ，ｐ，Ｐｔｈ）は、パケット送信量Ｎとパケット送信成功率ｐに対する多項式形態で近似化される。
一実施形態では、閾値確率Ｐｔｈが０．９９である時、予想パケット受信量ｋ＊（Ｎ，ｐ，Ｐｔｈ）はパケット送信量Ｎが１０乃至２０であり、パケット送信成功率ｐが０乃至１である領域に対してａＮｐ２の式で近似化される。例えば、ａが０．７６５６に設定される場合、ａＮｐ２は平均誤差が０．６である。
また、一実施形態では、予想パケット受信量ｋ＊（Ｎ，ｐ，Ｐｔｈ）は、ルックアップテーブルを用いて演算される。例えば、各々のパケット送信量Ｎ、パケット送信成功率ｐ、及び閾値確率Ｐｔｈに対する予想パケット受信量ｋ＊（Ｎ，ｐ，Ｐｔｈ）が予め算出されてルックアップテーブル形態として格納された場合、ノードはルックアップテーブルを参照して予想パケット受信量ｋ＊（Ｎ，ｐ，Ｐｔｈ）を抽出できる。
【００８４】
［２］潜在的要求自由度（Ｐｏｔｅｎｔｉａｌｌｙ  Ｒｅｑｕｉｒｅｄ  Ｄｅｇｒｅｅ  ｏｆ  Ｆｒｅｅｄｏｍ、ＰＲ−ＤｏＦ）
潜在的要求自由度は、送信ノードからパケットを受信した受信ノードが追加的に受信しなければならないパケットの量を示す。ソースノードがノードｉにパケットを送信する場合、ノードｉの潜在的要求自由度は下記の数式（３）のように示される。
【００８５】
【数３】
0006578137.tif 000004
【００８６】
ここで、ＰＲ−ＤｏＦｉはノードｉの潜在的要求自由度を示し、Ｋはソースノードがオリジナルパケットを、ランダム行列を用いて符号化されたパケットに変換して符号化されたパケットをノードｉに送信する場合のオリジナルパケットの個数を示し、Ｎｓはソースノードがノードｉに送信する符号化されたパケットの個数を示し、ｐｓｉはソースノードとノードｉの間のパケット送信成功率を示し、Ｐｔｈは閾値確率を示し、ｋ＊はノードｉの予想パケット受信量を示す。数式（３）は下記の数式（４）のように一般化できる。
【００８７】
【数４】
0006578137.tif 000005
【００８８】
ここで、ＰＲ−ＤｏＦｉｊは送信ノードｉに対する受信ノードｊの潜在的要求自由度を示し、Ｋｊ’は受信ノードｊの以前潜在的要求自由度を示し、Ｎｉは送信ノードｉが受信ノードｊに送信する符号化されたパケットの個数を示し、ｐｉｊは送信ノードｉと受信ノードｊの間のパケット送信成功率を示し、Ｐｔｈは閾値確率を示す。ｋ＊は受信ノードｊの予想パケット受信量を示す。これにより、ノードｊの現在の潜在的要求自由度は、ノードｊの以前潜在的要求自由度からノードｊの予想パケット受信量を引いた値が正値の場合はその値を意味する。
【００８９】
［３］要求送信量（ｎｕｍｂｅｒ  ｏｆ  ｒｅｑｕｉｒｅｄ  ｔｒａｎｓｍｉｓｓｉｏｎｓ、ＲＴＸ）
要求送信量は、ノードがリレーノード候補に送信を要求するパケットの量を意味する。ノードｉのリレーノード候補ｊに対する要求送信量は数式（５）のように示される。
【００９０】
【数５】
0006578137.tif 000006
【００９１】
ここで、Ｍｉｊはノードｉのリレーノード候補ｊに対する要求送信量を示し、ＰＲ−ＤｏＦｉはノードｉに対するリレーノード候補ｊの潜在的要求自由度を示し、Ｋｊ’はリレーノード候補ｊの以前潜在的要求自由度を示し、Ｎｉはノードｉがリレーノード候補ｊに送信する符号化されたパケットの個数を示し、ｐｉｊはノードｉとリレーノード候補ｊの間のパケット送信成功率を示し、Ｐｔｈは閾値確率を示し、ｋ＊は予想パケット受信量を示す。
【００９２】
［４］最小要求送信量（ｍｉｎｉｍｕｍ  ＲＴＸ、ｍＲＴＸ）
受信ノードの複数の送信ノードに対する要求送信量のうち量が最も少ない要求送信量を意味する。受信ノードｊのリレーノード候補ｉに対する最小要求送信量は数式（６）のように示される。
【００９３】
【数６】
0006578137.tif 000007
【００９４】
ここで、ｍＲＴＸ  Ｍｊ＊は受信ノードｊの最小要求送信量を示す。
【００９５】
［５］最適ノードグループ（Ｂｅｓｔ  Ｔｗｏ−ｈｏｐ  ｎｏｄｅ  Ｇｒｏｕｐ、ＢＴＧ）
最適ノードグループは、受信ノードのうち当該リレーノード候補に最小要求量のパケット送信をリクエストするノードから構成されたグループを意味する。リレーノード候補ｉの最適ノードグループは数式（７）のように示される。
【００９６】
【数７】
0006578137.tif 000008
【００９７】
ここで、ＢＴＧｉはリレーノード候補ｉの最適ノードグループを示し、Ｍｊ＊は受信ノードｊの最小要求送信量を示し、Ｍｉｊは受信ノードｊのリレーノード候補ｉに対する要求送信量を示す。これにより、リレーノード候補ｉの最適ノードグループは、複数のノードのうち最小要求送信量がリレーノード候補ｉに関する受信ノードから構成されたグループである。
【００９８】
［６］最大要求送信量（Ｍａｘｉｍｕｍ  ＲＴＸ、ＭｍＲＴＸ）
最大要求送信量は、最適ノードグループに含まれたノードの最小要求送信量のうち量が最も多い最小要求送信量を意味する。リレーノード候補ｉの最大要求送信量は、数式（８）のように示される。
【００９９】
【数８】
0006578137.tif 000009
【０１００】
Ｍｉ’はリレーノード候補ｉの最大要求送信量を示し、Ｍｊ＊は受信ノードｊの最小要求送信量を示し、ＢＴＧｉはリレーノード候補ｉの最適ノードグループを示す。一実施形態では、リレーノード候補ｉの最大要求送信量は、リレーノード候補ｉの最適ノードグループに含まれたノードに送信しなければならないパケットの量を意味する。
【０１０１】
［７］第１ユーティリティ（ｕｔｉｌｉｔｙ）
第１ユーティリティは、リレーノード候補の最大要求送信量による最適ノードグループに含まれたノードへのパケット送信が周辺ノードに及ぼす影響を示す。リレーノード候補ｉの第１ユーティリティは数式（９）のように示される。
【０１０２】
【数９】
0006578137.tif 000010
【０１０３】
ここで、Ｓは受信ノードの集合を示す。マルチキャストネットワークの状況に応じて、集合Ｓはリレーノード候補ｉの最適ノードグループを示すか、又はマルチキャストネットワークを構成する複数のノード全体を示す。Ｕｉはリレーノード候補ｉの第１ユーティリティを示し、Ｋｊ’は受信ノードｊの以前潜在的要求自由度を示し、ｐｉｊはリレーノード候補ｉと受信ノードｊの間のパケット送信成功率を示し、Ｐｔｈは閾値確率を示し、Ｍｉ’はリレーノード候補ｉの最大要求送信量を示し、ｋ＊は受信ノードｊの予想パケット受信量を示す。そのため、数式（９）による第１ユーティリティは、リレーノード候補ｉがＭｉ’個のパケットを再送信する場合、マルチキャストネットワークを構成する複数のノードに送信できるパケットの数を意味する。
【０１０４】
また、第１ユーティリティは数式（１０）のように示される。
【０１０５】
【数１０】
0006578137.tif 000011
【０１０６】
ここで、Ｕｉはリレーノード候補ｉの第１ユーティリティを示し、ＢＴＧｉはリレーノード候補ｉの最適ノードグループを示す。そのため、数式（１０）による第１ユーティリティは、リレーノード候補ｉが満足する受信ノードの個数を意味する。一実施形態において、ソースノードは、リレーノード候補ｉの数式（１０）による第１ユーティリティとリレーノード候補ｊの数式（１０）による第１ユーティリティとが互いに同一である場合、最大要求送信量が小さいリレーノード候補をリレーノードとして決定する。
【０１０７】
また、第１ユーティリティは数式（１１）のように示される。
【０１０８】
【数１１】
0006578137.tif 000012
【０１０９】
ここで、Ｕｉはリレーノード候補ｉの第１ユーティリティを示し、Ｓはマルチキャストネットワークを構成する複数のノードの集合を示し、Ｋｊ’は受信ノードｊの以前潜在的要求自由度を示し、Ｎｉはリレーノード候補ｉが受信ノードｊに送信する符号化されたパケットの個数を示し、ｐｉｊはリレーノード候補ｉと受信ノードｊの間のパケット送信成功率を示し、Ｐｔｈは閾値確率を示す。
【０１１０】
図５は、一実施形態に係るリレーノード選択方式を説明するための動作フローチャートである。
【０１１１】
図５を参照すると、ソースノードはトポロジ情報を取得する（Ｓ５１０）。即ち、ソースノードは、マルチキャストネットワークを構成する複数のノード間のチャネル状態に関する情報を取得してマルチキャストネットワークのトポロジ情報を抽出する。
【０１１２】
また、ソースノードは、マルチキャストネットワークを構成する複数のノードのうち、ソースノードを除いた残りのノードを、１−ホップノードグループ及び２−ホップノードグループに分類する（Ｓ５２０）。ここで、１−ホップノードグループはソースノードからパケットを受信するノードのグループを意味し、２−ホップノードグループはソースノードで送信されたパケットを１−ホップノードの中継により受信するノードのグループを意味する。ソースノードは、トポロジ情報を用いて、マルチキャストネットワークを構成する複数のノードのうち、ソースノードを除いた残りのノード各々の予想パケット受信量を上述した数式（２）により推定する。ここで、予想パケット受信量は、残りのノード各々が目標パケット受信量以上のパケットを受信する確率が予め定められた閾値確率以上にする残りのノード各々のパケット受信量を意味する。
ソースノードは、上述した数式（３）により、残りのノードの予想パケット受信量に基づいて残りのノード各々の潜在的要求自由度を推定する。ここで、潜在的要求自由度は、残りのノード各々が他のノードからパケットを受信した後に追加的に受信しなければならないパケットの量を示す。ソースノードは、潜在的要求自由度が低いノードを１−ホップノードグループに決定し、潜在的要求自由度が高いノードを２−ホップノードグループに決定する。例えば、ソースノードは、潜在的要求自由度が０であるノードを１−ホップノードグループに決定し、潜在的要求自由度が０よりも大きいノードを２−ホップノードグループに決定する。
【０１１３】
また、ソースノードは、システムパラメータを推定する（Ｓ５３０）。ここで、システムパラメータは、要求送信量、最小要求送信量、最大要求送信量、及び第１ユーティリティを含む。
【０１１４】
一実施形態では、ソースノードは２−ホップノードグループに含まれた少なくとも１つのノード各々に対して要求送信量を演算する。そのために、ソースノードは、上述した数式（４）により複数のリレーノード候補各々に対する２−ホップノードグループに含まれた少なくとも１つのノード各々の潜在的要求自由度を演算する。ソースノードは、上述した数式（５）により、複数のリレーノード候補各々に対する２−ホップノードグループに含まれた少なくとも１つのノード各々の潜在的要求自由度に基づいて、２−ホップノードグループに含まれた少なくとも１つのノード各々の複数のリレーノード候補各々に対する要求送信量を演算する。
【０１１５】
一実施形態において、ソースノードは、上述した数式（６）に基づいて２−ホップノードグループに含まれた少なくとも１つのノード各々に対し、２−ホップノードグループに含まれた少なくとも１つのノード各々の要求送信量のうち量が最も少ない要求送信量を示す最小要求送信量を推定する。
【０１１６】
一実施形態では、ソースノードは、上述した数式（７）に基づいて複数のリレーノード候補各々に対して、２−ホップノードグループに含まれた少なくとも１つのノードのうち、当該リレーノード候補に最小要求量のパケット送信をリクエストするノードから構成された最適ノードグループを抽出する。
【０１１７】
一実施形態では、ソースノードは、上述した数式（８）に基づいて複数のリレーノード候補各々に対して、最適ノードグループに含まれたノードの最小要求送信量のうち量が最も多い最小要求送信量を示す最大要求送信量を推定する。
【０１１８】
一実施形態において、ソースノードは、上述した数式（９）、数式（１０）又は数式（１１）のうち少なくとも１つに基づいて、複数のリレーノード候補各々に対して第１ユーティリティを推定する。ここで、第１ユーティリティは、複数のリレーノード候補各々の最大要求送信量による最適ノードグループに含まれたノードへのパケット送信が残りのノードのうち少なくとも一部に及ぼす影響を示す。
【０１１９】
また、ソースノードは、リレーノード及びリレーノードのパケット送信量を決定する（Ｓ５４０）。一実施形態において、ソースノードは、複数のリレーノード候補のうち第１ユーティリティの大きさが最も大きいリレーノード候補をリレーノードとして決定し、選択されたリレーノードのパケット送信量を決定する。他の一実施形態では、ソースノードは、複数のリレーノード候補のうち最大要求送信量の大きさが最も大きいリレーノード候補をリレーノードとして決定し、選択されたリレーノードのパケット送信量を決定する。
【０１２０】
また、ソースノードは、リレーノードの総パケット送信量が予め定められた最大パケット送信量以下であるか否かを判断する（Ｓ５５０）。リレーノードの総パケット送信量が予め定められた最大パケット送信量よりも大きい場合、ソースノードは、リレーノードのパケット送信量が予め定められた最大パケット送信量以下となるようにリレーノードのパケット送信量を修正する（Ｓ５５１）。
【０１２１】
また、ソースノードは、リレーノードの総パケット送信量が予め定められた最大パケット送信量以下である場合、システムパラメータをアップデートする（Ｓ５６０）。一実施形態では、ソースノードは、潜在的要求自由度、要求送信量、最小要求送信量、最大要求送信量、及び第１ユーティリティをリレーノードに基づいてアップデートする。
【０１２２】
また、ソースノードは、残りのノードがパケット受信を完了したか否かを判断する（Ｓ５７０）。残りのノードがパケット受信を完了していない場合、ソースノードは、ステップＳ５３０乃至ステップＳ５７０を繰り返して行う。残りのノードがパケット受信を完了した場合、ソースノードは遊休（ｉｄｌｅ）状態になる。
【０１２３】
図６は、他の一実施形態に係るリレーノード選択方式を説明するための動作フローチャートである。
【０１２４】
図６を参照すると、ソースノードはトポロジ情報を取得する（Ｓ６１０）。ソースノードは、マルチキャストネットワークを構成する複数のノード間のチャネル状態に関する情報を取得して、チャネル状態の情報からマルチキャストネットワークのトポロジ情報を抽出する。
【０１２５】
また、ソースノードは、マルチキャストネットワークを構成する複数のノードのうち、ソースノードを除いた残りのノードの潜在的要求自由度を推定する（Ｓ６２０）。潜在的要求自由度は、残りのノード各々が他のノードからパケットを受信した後に追加的に受信しなければならないパケットの量を示す。ソースノードは、残りのノード各々の上述した数式（２）により予想パケット受信量を予測し、上述した数式（３）により残りのノードの予想パケット受信量に基づいて残りのノード各々の潜在的要求自由度を推定する。
【０１２６】
また、ソースノードは、残りのノードを１−ホップノードグループ及び２−ホップノードグループに分類する（Ｓ６３０）。ソースノードは、潜在的要求自由度の低いノードを１−ホップノードグループに決定し、潜在的要求自由度の高いノードを２−ホップノードグループに決定する。例えば、ソースノードは、潜在的要求自由度が０であるノードを１−ホップノードグループに決定し、潜在的要求自由度が０よりも大きいノードを２−ホップノードグループに決定する。
【０１２７】
また、ソースノードは、２−ホップノードグループに含まれた少なくとも１つのノード各々に対して要求送信量を演算する（Ｓ６４０）。ソースノードは、上述した数式（５）により、複数のリレーノード候補各々に対する２−ホップノードグループに含まれた少なくとも１つのノード各々の潜在的要求自由度に基づいて、２−ホップノードグループに含まれた少なくとも１つのノード各々の複数のリレーノード候補各々に対する要求送信量を演算する。
【０１２８】
また、ソースノードは、最小要求送信量、最大要求送信量、及び第１ユーティリティを推定する（Ｓ６５０）。ソースノードは、上述した数式（６）に基づいて２−ホップノードグループに含まれた少なくとも１つのノード各々の最小要求送信量を推定する。また、ソースノードは、上述した数式（７）に基づいて複数のリレーノード候補各々の最適ノードグループを抽出し、上述した数式（８）に基づいて、複数のリレーノード候補各々の最大要求送信量を推定する。また、ソースノードは、上述した数式（９）、数式（１０）又は数式（１１）のうち少なくとも１つに基づいて、複数のリレーノード候補各々に対して第１ユーティリティを推定する。
【０１２９】
また、ソースノードは、リレーノード及びリレーノードのパケット送信量を決定する（Ｓ６６０）。一実施形態では、ソースノードが上述した数式（９）又は数式（１０）に基づいて複数の候補リレーノード各々に対して第１ユーティリティを推定した場合、ソースノードは、複数のリレーノード候補のうち第１ユーティリティの大きさが最も大きいリレーノード候補をリレーノードとして決定し、選択されたリレーノードの最大要求送信量をリレーノードのパケット送信量として決定する。他の一実施形態において、ソースノードは、複数のリレーノード候補のうち最大要求送信量の大きさが最も大きいリレーノード候補をリレーノードとして決定し、選択されたリレーノードの最大要求送信量をリレーノードのパケット送信量として決定する。
【０１３０】
また、ソースノードは、リレーノードの総パケット送信量が予め定められた最大パケット送信量以下であるか否かを判断する（Ｓ６７０）。一実施形態では、予め定められた最大パケット送信量は、リレーノードが測定した処理量に基づいて設定される。リレーノードの総パケット送信量が予め定められた最大パケット送信量よりも大きい場合、ソースノードは、リレーノードのパケット送信量が予め定められた最大パケット送信量以下となるようにリレーノードのパケット送信量を修正する（Ｓ６７１）。
【０１３１】
また、ソースノードは、リレーノードの総パケット送信量が予め定められた最大パケット送信量以下である場合、残りのノードの潜在的要求自由度をアップデートする（Ｓ６８０）。
【０１３２】
また、ソースノードは、残りのノードの潜在的要求自由度が０であるか否かを判断する（Ｓ６９０）。残りのノードのうちの潜在的要求自由度が０よりも大きいノードが存在する場合、ソースノードはステップＳ６５０乃至ステップＳ６９０を繰り返して行う。残りのノードの潜在的要求自由度が０である場合、ソースノードは遊休状態となる。一実施形態では、マルチキャストネットワークを構成する複数のノードで送信されたパケットの個数が予め定められた閾値個数以上である場合、ソースノードは遊休状態となる。
【０１３３】
図７は、一実施形態に係るリレーノードの選択を説明するための図である。
【０１３４】
図７を参照すると、マルチキャストネットワーク７００は、複数のノード７１０乃至７６０を含む。ソースノード７１０は、複数のノード７１０乃至７６０のトポロジ情報を取得する。図７に示す例として、各ノード間の線上に表示された数は各線に連結されているノード間における送信ノードのパケット送信成功率を示す。ソースノード７１０は、トポロジ情報を用いて複数のノード７１０乃至７６０間のパケット送信成功率に関する情報を抽出する。ソースノード７１０は、１０個のオリジナルパケットを２０個の符号化されたパケットに符号化し、各々のノードに２０個の符号化されたパケットを送信する。
【０１３５】
ソースノード７１０は、上述したように、数式（２）を近似化した式、ａＮｐ２を用いて残りのノード７２０乃至７６０の予想パケット送信量を推定する。ここで、ａは例えば０．８に設定される。また、ソースノード７１０は、上述した数式（３）を用いて残りのノード７２０乃至７６０の潜在的要求自由度を推定する。この場合、第１ノード７２０及び第２ノード７３０の潜在的要求自由度は０と推定され、第３ノード７４０の自由度は８と推定され、第４ノード７５０の自由度は１０と推定され、第５ノード７６０の自由度は１０と推定される。この結果を用いて、ソースノード７１０は、潜在的要求自由度が０である第１ノード７２０及び第２ノード７３０を１−ホップノードグループに分類し、潜在的要求自由度が０を超過する第３ノード７４０、第４ノード７５０及び第５ノード７６０を２−ホップノードグループに分類する。
【０１３６】
ソースノード７１０は、上述した数式（５）に基づいて２−ホップノードグループに含まれたノード７４０乃至７６０の要求送信量を推定する。この場合、第３ノード７４０の第１ノード７２０に対する要求送信量Ｍ１３は１３と推定され、第３ノード７４０の第２ノード７３０に対する要求送信量Ｍ２３は２８と推定される。第４ノード７５０の第１ノード７２０に対する要求送信量Ｍ１４は２０と推定され、第４ノード７５０の第２ノード７３０に対する要求送信量Ｍ２４は１６と推定され、第５ノード７６０の第２ノード７３０に対する要求送信量Ｍ２５は２０と推定される。
【０１３７】
また、ソースノード７１０は上述した数式（６）により、第３ノードの最小要求送信量Ｍ３＊を第３ノード７４０の第１ノード７２０に対する要求送信量Ｍ１３である１３と推定し、第４ノードの最小要求送信量Ｍ４＊を第４ノード７５０の第２ノード７３０に対する要求送信量Ｍ２４である１６と推定し、第５ノードの最小要求送信量Ｍ５＊を第５ノード７６０の第２ノード７３０に対する要求送信量Ｍ２５である２０と推定する。
【０１３８】
また、ソースノード７１０は、上述した数式（７）に基づいて第１ノード７２０の最適ノードグループに第３ノード７４０を含ませ、上述した数式（８）により第１ノード７２０の最大要求送信量Ｍ１’を第３ノード７４０の第１ノード７２０に対する要求送信量Ｍ１３である１３と推定する。また、ソースノード７１０は、上述した数式（７）に基づいて、第２ノード７３０の最適ノードグループに第４ノード７５０及び第５ノード７６０を含ませ、上述した数式（８）により第２ノード７３０の最大要求送信量Ｍ２’を第５ノード７６０の第２ノード７３０に対する要求送信量Ｍ２５である２０と推定する。
【０１３９】
また、ソースノード７１０は、上述した数式（９）に基づいて第１ノード７２０の第１ユーティリティＵ１を１４と推定し、第２ノード７３０の第１ユーティリティＵ２を２５と推定する。一実施形態では、第２ノード７３０の第１ユーティリティＵ２が第１ノード７２０の第１ユーティリティＵ１より値が大きいため、ソースノード７１０は第２ノード７３０をリレーノードとして決定し、第２ノード７３０のパケット送信量を第２ノード７３０の最大要求送信量Ｍ２’である２０に決定する。
【０１４０】
リレーノードである第２ノード７３０のパケット送信量が予め定められた最大パケット送信量よりも小さいと判断された場合、ソースノード７１０は上述した数式（３）を用いて、残りのノード７２０乃至７６０の潜在的要求自由度をアップデートする。この場合、第１ノード７２０、第２ノード７３０、第４ノード７５０、及び第５ノード７６０の潜在的要求自由度は０と推定される、第３ノード７４０の自由度は３と推定される。その場合、ソースノード７１０は、潜在的要求自由度は０である第１ノード７２０、第２ノード７３０、第４ノード７５０、及び第５ノード７６０を１−ホップノードグループに分類し、潜在的要求自由度が０を超過する第３ノード７４０を２−ホップノードグループに分類できる。
【０１４１】
ソースノード７１０は、上述した数式（５）に基づいて２−ホップノードグループに含まれたノードである第３ノード７４０の要求送信量を推定する。この場合、第３ノード７４０の第１ノード７２０に対する要求送信量Ｍ１３は５と推定される。また、ソースノード７１０は上述した数式（６）により、第３ノード７４０の最小要求送信量Ｍ３＊を第３ノード７４０の第１ノード７２０に対する要求送信量Ｍ１３である５と推定し、ソースノード７１０は、上述した数式（７）に基づいて第１ノード７２０の最適ノードグループに第３ノード７４０を含ませ、上述した数式（８）により第１ノード７２０の最大要求送信量Ｍ１’を第３ノード７４０の第１ノード７２０に対する要求送信量Ｍ１３である５と推定する。
【０１４２】
また、ソースノード７１０は、上述した数式（９）に基づいて第１ノード７２０の第１ユーティリティＵ１を３と推定し、第１ノード７２０をリレーノードとして決定する。また、ソースノード７１０は、第１ノード７２０のパケット送信量を第１ノード７２０の最大要求送信量Ｍ１’である３に決定する。その後、リレーノードである第１ノード７２０のパケット送信量が予め定められた最大パケット送信量よりも小さいと判断された場合、ソースノード７１０は、上述した数式（３）を用いて残りのノード７２０乃至７６０の潜在的要求自由度をアップデートする。アップデートの結果、残りのノード７２０乃至７６０の潜在的要求自由度が０である場合、ソースノード７１０は遊休状態になる。
【０１４３】
図８（Ａ）及び（Ｂ）は、一実施形態に係るネットワークユーティリティを説明するための図である。
【０１４４】
図８（Ａ）及び（Ｂ）を参照すると、グラフ８１０は、リレーノード候補ｉに送信するパケットの量Ｎｉによる受信ノードｊの第２ユーティリティの変化を示すグラフである。ここで、受信ノードｊの第２ユーティリティは、リレーノード候補ｉの受信ノードｊへのパケット送信による受信ノードｊの満足度を示す。ここで、受信ノードｊは、２−ホップノードグループに含まれるものとする。リレーノード候補ｉの受信ノードｊへのパケット送信による受信ノードｊの第２ユーティリティは、数式（１２）のように示される。
【０１４５】
【数１２】
0006578137.tif 000013
【０１４６】
Ｕｉｊはリレーノード候補ｉの受信ノードｊへのパケット送信による受信ノードｊの第２ユーティリティを示し、ｋ＊は受信ノードｊの予想パケット受信量を示し、Ｋｊ’は受信ノードｊの以前潜在的要求自由度を示し、Ｎｉはリレーノード候補ｉが受信ノードｊに送信する符号化されたパケットの個数を示し、ｐｉｊはリレーノード候補ｉと受信ノードｊとの間のパケット送信成功率を示し、Ｐｔｈは閾値確率を示す。一実施形態では、受信ノードｊの第２ユーティリティは受信ノードｊの以前潜在的要求自由度Ｋｊ’に収斂する。
【０１４７】
グラフ８２０は、リレーノード候補ｉが送信するパケットの量によるリレーノード候補ｉのネットワークユーティリティの変化を示すグラフである。ここで、リレーノード候補ｉのネットワークユーティリティは、リレーノード候補ｉのパケット送信による２−ホップノードグループの満足度を示す。リレーノード候補ｉのネットワークユーティリティは、数式（１３）のように示される。
【０１４８】
【数１３】
0006578137.tif 000014
【０１４９】
ここで、Ｕｉはリレーノード候補ｉのネットワークユーティリティを示し、Ｕｉｊはリレーノード候補ｉの受信ノードｊへのパケット送信による受信ノードｊの第２ユーティリティを示し、Ｓは受信ノードの集合を示す。マルチキャストネットワークにより、集合Ｓは可変される。集合Ｓに属する受信ノードｊの第２ユーティリティＵｉｊの和は最大値が特定値に収斂する。例えば、集合Ｓに属する受信ノードｊの第２ユーティリティＵｉｊの和は、受信ノードｊの以前潜在的要求自由度Ｋｊ’の和である、
0006578137.tif 000015
に収斂する。一実施形態では、グラフ８２０の「変曲点」（ここでは、傾きが不連続に変化する点）８２１、８２２、８２３のように、リレーノード候補ｉに送信するパケットの量によるリレーノード候補ｉのネットワークユーティリティの傾きが変更されるごとに、ソースノードは新しいリレーノードを選定し、選定されたリレーノードのパケット送信量を決定する。
【０１５０】
図９は、更なる一実施形態に係るリレーノード選択方式を説明するための動作フローチャートである。
【０１５１】
図９を参照すると、ソースノードはトポロジ情報を取得する（Ｓ９１０）。ソースノードは、マルチキャストネットワークを構成する複数のノード間のチャネル状態に関する情報を取得して、チャネル状態の情報からマルチキャストネットワークのトポロジ情報を抽出する。
【０１５２】
また、ソースノードは、マルチキャストネットワークを構成する複数のノードのうち、ソースノードを除いた残りのノードを１−ホップノードグループ及び２−ホップノードグループに分類する（Ｓ９２０）。ソースノードは、トポロジ情報を用いて、マルチキャストネットワークを構成する複数のノードのうち、ソースノードを除いた残りのノード各々の予想パケット受信量を上述した数式（２）により推定する。また、ソースノードは、上述した数式（３）により、残りのノードの予想パケット受信量に基づいて残りのノード各々の潜在的要求自由度を推定する。また、ソースノードは、潜在的要求自由度の低いノードを１−ホップノードグループに決定し、潜在的要求自由度の高いノードを２−ホップノードグループに決定する。
【０１５３】
また、ソースノードは、複数のリレーノード候補各々のネットワークユーティリティを推定する（Ｓ９３０）。ソースノードは、２−ホップノードグループに含まれたノード各々に対して、上述した数式（１２）に基づいて複数のリレーノード候補各々の２−ホップノードグループに含まれたノードへのパケット送信による２−ホップノードグループに含まれたノードの満足度を示す第２ユーティリティを推定し、複数のリレーノード候補各々に対して、上述した数式（１３）に基づいてネットワークユーティリティを推定する。
【０１５４】
また、ソースノードは、リレーノード及びリレーノードのパケット送信量を決定する（Ｓ９４０）。ソースノードは、ソースノードがマルチキャストネットワークを構成する複数のノードのうち、ソースノードを除いた残りのノードにパケットを送信すると仮定するとき、上述した数式（１３）を用いてソースノードのネットワークユーティリティを推定し、ソースノードが送信するパケットの量によるソースノードのネットワークユーティリティの傾きを抽出する。
ソースノードが送信するパケットの量によるソースノードのネットワークユーティリティの傾きが変更される場合、ソースノードは、上述した数式（１３）に基づいて複数のリレーノード候補各々のネットワークユーティリティを推定し、複数のリレーノード候補各々に対して、複数のリレーノード候補各々が送信するパケットの量による複数のリレーノード候補各々のネットワークユーティリティの傾きを抽出する。ソースノードは、抽出されたノードのネットワークユーティリティの傾きを比較し、傾きが最も大きいノードをリレーノードとして決定する。
また、リレーノードに送信するパケットの量によるリレーノードのネットワークユーティリティの傾きが変更されるごとに、ソースノードは複数のリレーノード候補各々の第２ユーティリティをアップデートし、複数のリレーノード候補のうち、リレーノード候補に送信するパケットの量による第２ユーティリティの傾きが最も大きいリレーノード候補をリレーノードとして選択する。
一実施形態では、リレーノードに送信するパケットの量によるリレーノードのネットワークユーティリティの傾きが変更されるとき、ソースノードは、追加されるリレーノード候補があるか否かを判断する。追加されるリレーノード候補が存在する場合、ソースノードは、追加されるリレーノード候補のネットワークユーティリティを推定し、追加されるリレーノード候補が送信するパケットの量による追加されるリレーノード候補のネットワークユーティリティの傾きを抽出する。
また、一実施形態では、リレーノードを選択する場合、リレーノードに送信するパケットの量によるリレーノードのネットワークユーティリティの傾きが変更されるまで、選択されたリレーノードのパケット送信量を決定する。
【０１５５】
また、ソースノードは、リレーノードの総パケット送信量が予め定められた最大パケット送信量以下であるか否かを判断する（Ｓ９５０）。一実施形態では、予め定められた最大パケット送信量は、リレーノードが測定した処理量に基づいて設定され得る。リレーノードの総パケット送信量が予め定められた最大パケット送信量よりも大きい場合、ソースノードは、リレーノードのパケット送信量が予め定められた最大パケット送信量以下となるようにリレーノードのパケット送信量を修正する（Ｓ９５１）。
【０１５６】
また、ソースノードは、残りのノードがパケット受信を完了したか否かを判断する（Ｓ９６０）。残りのノードがパケット受信を完了していない場合、ソースノードは、ステップＳ９４０乃至ステップＳ９６０を繰り返して行う。残りのノードがパケット受信を完了した場合、ソースノードは遊休状態になる。
【０１５７】
図１０は、一実施形態に係るリレー選択パケットの構造を説明するための図である。
【０１５８】
図１０を参照すると、ソースノードが複数のリレーノード候補のうちからリレーノード及びリレーノードのパケット送信量を選択する場合、ソースノードは、リレーノードにリレー選択パケット１０００を送信する。
【０１５９】
一実施形態では、リレー選択パケット１０００は、イーサヘッダ１０１０、タイプフィールド１０２０、オリジナルパケットフィールド１０３０、及び符号化パケットフィールド１０４０を含む。イーサヘッダ１０１０はリレー選択パケット１０００のイーサネット（登録商標）タイプを示し、タイプフィールド１０２０はリレー選択パケット１０００の属性を示す。例えば、タイプフィールド１０２０のフィールド値は８である。オリジナルパケットフィールド１０３０は、符号化されたパケットに変換するオリジナルパケットの数を示し、符号化パケットフィールド１０４０は、変換される符号化されたパケットの数を示す。
＜マトリックスネットワークコーディングを用いた符号化及び復号化方式＞
【０１６０】
図１１は、一実施形態に係るノードを示すブロック図である。
【０１６１】
図１１を参照すると、ノード１１００は、符号化部１１１０及び復号化部１１２０を含む。符号化部１１１０は、イーサネット（登録商標）モジュールからオリジナルパケットを受信し、オリジナルパケットを複数のサブパケットに分類し、複数のサブパケットとランダム行列を演算して符号化されたデータを生成する。一実施形態において、符号化部１１１０は、符号化されたデータに符号化されたデータに関する情報を含む第１ヘッダを付加する。ここで、第１ヘッダは、オリジナルパケットの個数に関する情報、ランダム行列の長さに関する情報、符号化されたパケットの識別子に関する情報、ランダム行列の係数に関する情報、及び符号化されたパケットのタイプに関する情報のうち少なくとも１つを含む。
ここで、符号化されたパケットのタイプに関する情報は、組織コード（ｓｙｓｔｅｍａｔｉｃ  ｃｏｄｅ）及び非組織コード（ｎｏｎ−ｓｙｓｔｅｍａｔｉｃ  ｃｏｄｅ）を含む。組織コードは、符号化されたパケットを無線ＬＡＮモジュールに送信する以前にオリジナルパケットを無線ＬＡＮモジュールに送信するコードを意味し、非組織コードは、符号化されたパケットのみを無線ＬＡＮモジュールに送信するコードを意味する。また、符号化部１１１０は、符号化されたパケットにオリジナルパケットのイーサネット（登録商標）タイプに関する情報を含む第２ヘッダを付加する。
【０１６２】
一実施形態において、符号化部１１１０は、受信したＫ個のオリジナルパケットを、マトリックスネットワークコーディングを用いてＮ個の符号化されたパケットに変換する（Ｎ≧Ｋ）。例えば、符号化部１１１０は、Ｋ個のランダム行列を用いてイーサネット（登録商標）モジュールから受信したＫ個のオリジナルパケットをＮ個の符号化されたパケットに変換し、Ｎ個の符号化されたパケットを無線ＬＡＮモジュールに送信する。ノード１１００は、Ｎ個の符号化されたパケットを他のノードに送信する。
一実施形態では、符号化されたパケットを受信するノードがＮ個の符号化されたパケットのうちＫ個以上の符号化されたパケットを受信する場合、符号化されたパケットを受信するノードがＫ個のオリジナルパケットを取得する確率が高まり、信頼性は増加する。一方、ノード１１００が送信する符号化されたパケットの個数が増加するほど、符号化されたパケットを送受信するノードのオーバヘッドも増加する。これに対処するため、ノード１１００は、オリジナルパケットの個数のＫ個と符号化されたパケットの個数のＮ個の比率を調整し、符号化されたパケットを送受信するノードの信頼度及びオーバヘッドを調整する。
【０１６３】
復号化部１１２０は、他のノードから受信した符号化されたパケットに基づいて生成された生成子行列を用いて符号化されたパケットをオリジナルパケットに変換する。一実施形態では、復号化部１１２０は、受信した符号化されたパケットから行列係数を抽出して生成子行列を生成する。例えば、受信した符号化されたパケットの個数がＫ個である場合、復号化部１１２０は、Ｋ個の符号化されたパケットから行列係数を抽出し、ｐＫ×ｐＫの大きさの生成子行列を生成する。ここで、ｐは、符号化部１１１０でオリジナルパケットが分割された複数のサブパケット各々の長さを意味する。復号化部１１２０は、生成子行列の逆行列を抽出し、符号化されたパケットと生成子行列の逆行列を乗算してオリジナルパケットを抽出する。ここで、復号化部１１２０は、ＬＵ分解（ＬＵ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ）方式を用いてもよい。これにより、復号化部１１２０の復号化速度を向上できる。
【０１６４】
図１２は、一実施形態に係る符号化方式を説明するための図である。図１２及び図１３に対する説明において、ノードの動作は図１１に示す符号化部１１１０の動作を示す。
【０１６５】
図１２を参照すると、Ｋ個のオリジナルパケット１２１０を符号化するために、ノードは、Ｋ個のオリジナルパケット１２１０の各々をｑ個のサブパケットに分割する。ここで、Ｋ個のオリジナルパケット１２１０の各々はＬシンボルの長さを有し、ｑ個のサブパケットの各々はｐシンボルの長さを有する。ノードは、ｐ×ｐの大きさを有するＫ個のランダム行列Ａ１乃至ＡＫを生成し、Ｋ個のオリジナルパケット１２１０の各々に対してインデックスの一致するランダム行列を選択し、当該インデックスを有するオリジナルパケットのサブパケットと選択されたランダム行列を乗算する。
例えば、第１パケット１２２１の各サブパケットは第１ランダム行列Ａ１（１２３１）と乗算され、第２パケット１２２２の各サブパケットは第２ランダム行列Ａ２（１２３２）と乗算され、第Ｋパケット１２２３のサブパケットは第Ｋランダム行列ＡＫ（１２３３）と乗算される。ノードは、ランダム行列と乗算された各々のサブパケットを加算して１つの符号化されたパケット１２４０を生成する。一実施形態では、図１２におけるシンボル及び演算は、ガロアフィールドで定義されたものと仮定する。ノードは上述した過程をＮ番繰り返し、Ｎ個の符号化されたパケットを生成できる。
【０１６６】
図１３は、一実施形態に係る符号化されたパケットの構造を説明するための図である。
【０１６７】
図１３を参照すると、オリジナルパケット１３１０は、イーサヘッダ１３１１、ＩＰフィールド１３１２、ＵＤＰフィールド１３１３、及びデータフィールド１３１４を含む。イーサヘッダ１３１１は、オリジナルパケット１３１０のイーサネット（登録商標）タイプを示す。ノードは、ＩＰフィールド１３１２、ＵＤＰフィールド１３１３、及びデータフィールド１３１４に対して符号化を行う。
【０１６８】
符号化されたパケット１３２０は、イーサヘッダ１３２１、ＭＮＣヘッダ１３２２、及び符号化されたデータフィールド１３２３を含む。符号化されたデータフィールド１３２３は、オリジナルパケット１３１０のＩＰフィールド１３１２、ＵＤＰフィールド１３１３、及びデータフィールド１３１４が変換された部分を意味する。イーサヘッダ１３２１は、符号化されたパケット１３２０のイーサネット（登録商標）タイプを示す。ＭＮＣヘッダ１３２２は、Ｋフィールド１３３１、ｐフィールド１３３２、ｅｉｄフィールド１３３３、ｓｙｓフィールド１３３４、及びｃｏｅｆｆｉｃｉｅｎｔフィールド１３３５を含む。
【０１６９】
Ｋフィールド１３３１はオリジナルパケットの個数Ｋを示し、ｐフィールド１３３２は、符号化を行うときにオリジナルパケット１３１０のサブパケットに乗算されるランダム行列の長さｐを示す。ｅｉｄフィールド１３３３は、符号化されたパケットの識別子を示す。例えば、ノードは符号化を行うごとにｅｉｄフィールド１３３３の値を１ずつ増加し、符号化されたパケットを区別する。ｓｙｓフィールド１３３４は、符号化されたパケットのタイプを示す。ここで、符号化されたパケットのタイプに関する情報は、組織コード及び非組織コードを含む。組織コードは、符号化されたパケットをノードの無線ＬＡＮモジュールに送信する以前に、オリジナルパケットをノードの無線ＬＡＮモジュールに送信するコードを意味し、非組織コードは、符号化されたパケットのみをノードの無線ＬＡＮモジュールに送信するコードを意味する。ｃｏｅｆｆｉｃｉｅｎｔフィールド１３３５は、有限フィールドの元素として、ノードは有限フィールド演算を用いて符号化及び復号化を行う。ｃｏｅｆｆｉｃｉｅｎｔフィールド１３３５の大きさは、符号化にために用いた有限フィールドの大きさｆｉｎｉｔｅ＿ｆｉｅｌｄ＿ｓｉｚｅ、ランダム行列の長さｐ、及びオリジナルパケットの個数Ｋに比例する。一実施形態では、ｃｏｅｆｆｉｃｉｅｎｔフィールド１３３５の大きさは、数式（１４）のように示される。
【０１７０】
【数１４】
0006578137.tif 000016
【０１７１】
ここで、｜ｆｉｎｉｔｅ＿ｆｉｅｌｄ＿ｓｉｚｅ｜は符号化にために用いた有限フィールドの大きさを示し、ｐはランダム行列の長さを示し、Ｋはオリジナルパケットの個数を示す。一実施形態では、ノードは、予め定められた処理方式を用いてＭＮＣヘッダ１３２２の大きさを減し得る。
【０１７２】
一実施形態では、ノードはオリジナルパケットを取得する場合、これをパケットキュー（ｐａｃｋｅｔ＿ｑｕｅｕｅ、以下、ＭＮＣキューともいう）に格納し、パケットキューにＫ個のオリジナルパケットが格納された場合、ノードは符号化を行う。ここで、符号化されたパケットが組織コードに従う場合、ノードはＫ個のオリジナルパケットにＭＮＣヘッダ１３２２を付加し、（Ｎ−Ｋ）個の符号化されたパケットを生成し、符号化されたパケットにＭＮＣヘッダ１３２２を付加する。また、符号化されたパケットが非組織コードに従う場合、ノードはＮ個の符号化されたパケットを生成し、符号化されたパケットにＭＮＣヘッダ１３２２を付加する。一実施形態では、予め定められた時間の間にノードがＫ個のオリジナルパケットを取得できない場合、ノードは格納されているパケットのみを符号化する。これは、符号化の遅延時間が長くなることを防止するためである。
【０１７３】
図１４は、一実施形態に係る復号化方式を説明するための図である。図１４に対する説明において、ノードの動作は図１１に示す復号化部１１２０の動作を示す。
【０１７４】
図１４を参照すると、ノードは、パケットキューリストを用いて符号化されたパケットを復号化する。パケットキューリストは、パケットキューヘッド１４１０と複数のパケットキュー１４２０、１４３０、１４４０を含む。パケットキューヘッド１４１０及び複数のパケットキュー１４２０、１４３０、１４４０は、連結リスト（ｌｉｎｋｅｄ  ｌｉｓｔ）の形態に構成される。パケットキューヘッド１４１０は、パケットキューリストの初期ポインタを示す。パケットキューヘッド１４１０は、「ｎｅｘｔ」データ１４１１及び「ｑｌｅｎ」データ１４１２を含む。「ｎｅｘｔ」データ１４１１は第１パケットキュー１４２０のアドレス値を示し、「ｑｌｅｎ」データ１４１２は複数のパケットキュー１４２０、１４３０、１４４０の個数を示す。第１パケットキュー１４２０は、「ｎｅｘｔ」データ１４２１、「ｐｒｅｖ」データ１４２２、「ｌｉｓｔ」データ１４２３、「ｅｉｄ」データ１４２４、「ｅｔｉｍｅ」データ１４２５、及びパケットデータ１４２６を含んでもよい。「ｎｅｘｔ」データ１４２１は第２パケットキュー１４３０のアドレス値を示し、「ｐｒｅｖ」データ１４２２は以前パケットキューのアドレス値を示す。第１パケットキュー１４２０の場合、以前パケットキューが存在しないため、ｐｒｅｖデータ１４２２は「ｎｕｌｌ」である。「ｌｉｓｔ」データ１４２３は、パケットキューヘッド１４１０の「ｎｅｘｔ」データ１４１１を指示し、パケットデータ１４２６は、第１パケットキュー１４２０に挿入されたパケットを含む。ここでパケットは、符号化されないパケット及び符号化されたパケットを含む。「ｅｔｉｍｅ」データ１４２５は、第１パケットキュー１４２０に最後にパケットが挿入された時間を示し、「ｅｉｄ」データ１４２４は、パケットキュー１４２０に挿入されたパケットの識別子を示す。そのため、１つのパケットキューに挿入されたパケットは全て同一の識別子を有する。
【０１７５】
一実施形態では、他のノードからパケットを受信した場合、ノードは、当該パケットをパケットキューリストに含まれたパケットキューに挿入する。ここで、ノードは、パケットがパケットキューに挿入される時間と予め定められた閾時間とを比較し、パケットキューに挿入される時間が予め定められた閾時間よりも先である場合、パケットキューリストから当該パケットキューを削除する。また、ノードは、パケットの識別子が予め定められた時間の間にオリジナルパケットに変換された符号化されたパケットの識別子と同一である場合、パケットをパケットキューに挿入できないことがある。パケットの識別子が予め定められた時間の間にオリジナルパケットに変換された符号化されたパケットの識別子と同一でない場合、パケットをパケットキューに挿入し、パケットキューの「ｅｔｉｍｅ」データをアップデートする。
【０１７６】
一実施形態において、パケットキューにＫ個のパケットが挿入された場合、ノードは、パケットキューに挿入されたパケットが符号化されないパケットであるか、又は符号化されたパケットであるか否かを判断する。パケットキューに挿入された全てのパケットが符号化されないパケットである場合、ノードは別途の復号化を行うことなく、符号化されていないパケットのうち、オリジナルパケットに挿入されたフィールドのみを除去してオリジナルパケットを抽出する。
パケットキューに挿入されたパケットのうち、符号化されたパケットが１つでも存在する場合、ノードは生成子行列を用いて復号化を行う。この場合、ノードは生成子行列を生成し、生成子行列の逆行列を抽出し、符号化されたパケットと生成子行列の逆行列を乗算してオリジナルパケットを抽出する。一実施形態では、特定符号化されたパケットに対応する成分が線形従属的（ｌｉｎｅａｒｌｙ  ｄｅｐｅｎｄｅｎｔ）である場合、ノードは生成子行列の逆行列を抽出できない場合もある。この場合、ノードは、パケットキューで線形従属的な成分と対応する符号化されたパケットを削除する。
＜マルチキャストネットワークにおけるノードの動作方法＞
【０１７７】
図１５は、一実施形態に係るソースノードの動作方法を示した動作フローチャートである。
【０１７８】
図１５を参照すると、ソースノードは、マルチキャストネットワークを構成する複数のノード間のチャネル状態に関する情報を取得し、チャネル状態の情報からマルチキャストネットワークのトポロジ情報を抽出する（Ｓ１５１０）。
【０１７９】
また、ソースノードは、トポロジ情報に基づいて複数のノードのうちソースノードから送信されたパケットを中継するリレーノードを選択する（Ｓ１５２０）。
【０１８０】
図１５に示された一実施形態に係るソースノードの動作方法は、図１乃至図１４を参照して説明した内容がそのまま適用されるので、より詳細な説明は省略する。
【０１８１】
図１６は、一実施形態に係るノードの動作方法を示した動作フローチャートである。
【０１８２】
図１６を参照すると、ノードは、ランダム行列を用いてオリジナルパケットを符号化されたパケットに変換する（Ｓ１６１０）。
【０１８３】
また、ノードは、符号化されたパケットに基づいて生成された生成子行列を用いて符号化されたパケットを前記オリジナルパケットに変換する（Ｓ１６２０）。
【０１８４】
図１６に示された一実施形態に係るノードの動作方法は、図１乃至図１４を参照して説明した内容がそのまま適用されるので、より詳細な説明は省略する。
【０１８５】
図１７は、他の一実施形態に係るソースノードの動作方法を示した動作フローチャートである。
【０１８６】
図１７を参照すると、ソースノードは、マルチキャストネットワークを構成する複数のノード間のチャネル状態に関する情報を取得し、チャネル状態の情報からマルチキャストネットワークのトポロジ情報を抽出する（Ｓ１７１０）。
【０１８７】
また、ソースノードは、トポロジ情報に基づいて複数のノードのうちソースノードから送信されたパケットを中継するリレーノードを選択する（Ｓ１７２０）。
【０１８８】
また、ソースノードは、ランダム行列を用いてオリジナルパケットを符号化されたパケットに変換し、リレーノードに符号化されたパケットを送信し、リレーノードから受信した符号化されたパケットに基づいて生成された生成子行列を用いて符号化されたパケットをオリジナルパケットに変換する（Ｓ１７３０）。
【０１８９】
図１７に示された一実施形態に係るソースノードの動作方法は、図１乃至図１４を参照して説明した内容がそのまま適用されるので、より詳細な説明は省略する。
【０１９０】
以上で説明された装置は、ハードウェア構成要素、ソフトウェア構成要素、及び／又はハードウェア構成要素及びソフトウェア構成要素の組み合わせで実現される。例えば、プロセッサ、コントローラ、ＡＬＵ（ａｒｉｔｈｍｅｔｉｃ  ｌｏｇｉｃ  ｕｎｉｔ）、デジタル信号プロセッサ（ｄｉｇｉｔａｌ  ｓｉｇｎａｌ  ｐｒｏｃｅｓｓｏｒ）、マイクロコンピュータ、ＦＰＡ（ｆｉｅｌｄ  ｐｒｏｇｒａｍｍａｂｌｅ  ａｒｒａｙ）、ＰＬＵ（ｐｒｏｇｒａｍｍａｂｌｅ  ｌｏｇｉｃ  ｕｎｉｔ）、マイクロプロセッサー、又は、命令（ｉｎｓｔｒｕｃｔｉｏｎ）を実行して応答できる異なる装置のように、１つ以上の汎用コンピュータ又は特殊目的のコンピュータを用いて実現される。処理装置は、オペレーティングシステム（ＯＳ）及び前記オペレーティングシステム上で行われる１つ以上のソフトウェアアプリケーションを行う。また、処理装置は、ソフトウェアの実行に応答してデータをアクセス、格納、操作、処理及び生成する。理解の便宜のために、処理装置は１つ使用されるものと説明される場合もあるが、当該の技術分野で通常の知識を有する者には、処理装置が複数の処理要素（ｐｒｏｃｅｓｓｉｎｇ  ｅｌｅｍｅｎｔ）及び／又は複数類型の処理要素を含んでいることが理解できるであろう。例えば、処理装置は、複数のプロセッサ又は１つのプロセッサ及び１つのコントローラを含む。また、並列プロセッサ（ｐａｒａｌｌｅｌ  ｐｒｏｃｅｓｓｏｒ）のような、他の処理構成も可能である。
【０１９１】
ソフトウェアはコンピュータプログラム、コード、命令、又はこのうちの１つ以上の組み合わせを含み、希望の通りに動作するよう処理装置を構成したり独立的又は結合的に処理装置を命令する。ソフトウェア及び／又はデータは、処理装置によって解釈され、処理装置に命令又はデータを提供するための、何らかの類型の機械、構成要素、物理的装置、仮想装置、コンピュータ格納媒体又は装置、及び／又は、送受信される信号波形として永久的又は一時的に具現化される。ソフトウェアは、ネットワークに接続されたコンピュータシステム上に分散し、分散された方法で格納され、実行され得る。ソフトウェア及びデータは１つ以上のコンピュータで読み出し可能な記録媒体に格納され得る。
【０１９２】
実施形態に係る方法は、多様なコンピュータ手段を介して様々な処理を実行できるプログラム命令の形態で実現され、コンピュータにより読取可能な記録媒体に記録される。コンピュータ読取可能な媒体は、プログラム命令、データファイル、データ構造などのうち１つ又はその組み合わせを含む。媒体に記録されるプログラム命令は、本発明の目的のために特別に設計されて構成されたものであるか、又はコンピュータソフトウェア分野の技術を有する当業者にとって公知、且つ、使用可能なものである。コンピュータ読取可能な記録媒体の例としては、ハードディスク、フロッピー（登録商標）ディスク及び磁気テープのような磁気媒体、ＣＤ−ＲＯＭ、ＤＶＤのような光記録媒体、光ディスクのような光磁気媒体、及び、ＲＯＭ、ＲＡＭ、フラッシュメモリのようなプログラム命令を保存して実行するように特別に構成されたハードウェア装置が含まれる。プログラム命令の例には、コンパイラによって作られるような機械語コードだけでなく、インタープリタなどを用いてコンピュータによって実行できる高級言語コードが含まれる。前記したハードウェア装置は、本発明の動作を行うために１つ以上のソフトウェアモジュールとして動作するように構成され、その逆も同様である。
【０１９３】
上述したように、本発明を限定された実施形態と図面によって説明したが、本発明は、上記の実施形態に限定されることなく、本発明が属する分野における通常の知識を有する者であれば、このような実施形態から多様な修正及び変形が可能であろう。
【０１９４】
従って、本発明の範囲は、開示された実施形態に限定されず、特許請求の範囲だけではなく特許請求の範囲と均等なものによって定められるべきである。
【符号の説明】
【０１９５】
１００      ノード
１１０      イーサネット（登録商標）モジュール
１２０      無線ＬＡＮモジュール
１３０      マトリックスネットワークコーディングモジュール（ＭＮＣモジュール）
１４０      トポロジ情報抽出部
１５０      リレーノード選択部
１６０      変換部
２００      ソースノード
２１０      トポロジ情報抽出部
２２０      リレーノード選択部
３１０      トレーニングパケット
３１１      イーサヘッダ
３１２      タイプフィールド
３１３      送信量フィールド
３１４      シーケンスフィールド
３１５      データフィールド
３２０      トレーニングリポートパケット
３２１      イーサヘッダ
３２２      タイプフィールド
３２３      送信量フィールド
３２４      受信量フィールド
３２５      処理率フィールド
３３０      トレーニング下りパケット
３３１      イーサヘッダ
３３２      タイプフィールド
３４０      ネイバーリポートパケット
３４１      イーサヘッダ
３４２      タイプフィールド
３４３      リポートパケット数量フィールド
３４４      アドレスフィールド
３４５      送信量フィールド
３４６      受信量フィールド
３４７      処理量フィールド
３５０      ブロックトレーニングリポートパケット
３５１      イーサヘッダ
３５２      タイプフィールド
３５３      リポートパケット数量フィールド
３５４      受信者アドレスフィールド
３５５      送信者アドレスフィールド
３５６      送信量フィールド
３５７      受信量フィールド
３５８      処理量フィールド
４１０      ソースノード
４２１      第１ノード
４２２      第２ノード
４３１      第３ノード
４３２      第４ノード
７００      マルチキャストネットワーク  ７１０      ソースノード、ノード
７２０、７３０、７４０、７５０      ノード
８１０      リレーノード候補ｉに送信するパケットの量Ｎｉによる受信ノードｊの第２ユーティリティの変化を示すグラフ
８２０      リレーノード候補ｉが送信するパケットの量によるリレーノード候補ｉのネットワークユーティリティの変化を示すグラフ
８２１、８２２、８２３      グラフ８２０の変曲点
１０００      リレー選択パケット
１０１０      イーサヘッダ
１０２０      タイプフィールド
１０３０      オリジナルパケットフィールド
１０４０      符号化パケットフィールド
１１００      ノード
１１１０      符号化部
１１２０      復号化部
１２１０      Ｋ個のオリジナルパケット
１２２１、１２２２、１２２３      第１、第２、第Ｋパケット
１２４０      符号化されたパケット
１３１０      オリジナルパケット
１３１１      イーサヘッダ
１３１２      ＩＰフィールド
１３１３      ＵＤＰフィールド
１３１４      データフィールド
１３２０      符号化されたパケット
１３２１      イーサヘッダ
１３２２      ＭＮＣヘッダ
１３２３      符号化されたデータフィールド
１３３１      Ｋフィールド
１３３２      ｐフィールド
１３３３      ｅｉｄフィールド
１３３４      ｓｙｓフィールド
１３３５      ｃｏｅｆｆｉｃｉｅｎｔフィールド
１４１０      パケットキューヘッド
１４２０、１４３０、１４４０      パケットキュー
１４１１      「ｎｅｘｔ」データ
１４１２      「ｑｌｅｎ」データ
１４２１      「ｎｅｘｔ」データ
１４２２      「ｐｒｅｖ」データ
１４２３      「ｌｉｓｔ」データ
１４２４      「ｅｉｄ」データ
１４２５      「ｅｔｉｍｅ」データ
１４２６      パケットデータ
【図１】
0006578137.tif 000017
【図２】
0006578137.tif 000018
【図３】
0006578137.tif 000019
【図４】
0006578137.tif 000020
【図５】
0006578137.tif 000021
【図６】
0006578137.tif 000022
【図７】
0006578137.tif 000023
【図８】
0006578137.tif 000024
【図９】
0006578137.tif 000025
【図１０】
0006578137.tif 000026
【図１１】
0006578137.tif 000027
【図１２】
0006578137.tif 000028
【図１３】
0006578137.tif 000029
【図１４】
0006578137.tif 000030
【図１５】
0006578137.tif 000031
【図１６】
0006578137.tif 000032
【図１７】
0006578137.tif 000033