(57)【要約】      （修正有）【課題】無線マルチホップネットワークにおいて、データを配送する際にネットワークコーディングを行う場合にあっても、パケットの送信回数を削減して効率的にデータを配送する方法を提供する。【解決手段】データ送信端末毎に、当該データ送信端末から送信先の少なくとも１つのデータ受信端末に至る複数経路の中から少なくとも２つの最小ホップ経路を抽出し、前記最小ホップ経路のうちの少なくとも２つの交差経路の組合せ毎に、当該組合せの各交差経路に流れるデータの符号化可否を判定し、得られた符号化可否の判定結果に応じて、当該データ送信端末から送信先のデータ受信端末に至る符号化対応最小ホップ経路を設定し、当該データ送信端末について設定された符号化対応最小ホップ経路を介して、当該データ送信端末から送信先のデータ受信端末にデータを、当該符号化対応最小ホップ経路に対応する符号化可否の判定結果に応じた符号化を施して配送する。【選択図】図２３
2010239196.tif 000002
【特許請求の範囲】
【請求項１】
無線通信リンクを介して各々が隣接間で接続されている複数の端末がマルチホップネットワークを構成する無線通信システムにおけるデータ配送方法であって、
前記端末のうちのデータ送信端末毎に、当該データ送信端末から送信先の少なくとも１つのデータ受信端末に至る複数経路の中から少なくとも２つの最小ホップ経路を抽出する経路抽出ステップと、
前記データ送信端末毎に得られた最小ホップ経路のうちの少なくとも２つの交差経路の組合せ毎に、当該組合せの各交差経路に流れるデータの符号化可否を判定する符号化判定ステップと、
前記交差経路毎に得られた符号化可否の判定結果に応じて、前記データ送信端末毎に、当該データ送信端末から送信先のデータ受信端末に至る符号化対応最小ホップ経路を設定する経路設定ステップと、
前記データ送信端末毎に、当該データ送信端末について設定された符号化対応最小ホップ経路を介して、当該データ送信端末から送信先のデータ受信端末にデータを、当該符号化対応最小ホップ経路に対応する符号化可否の判定結果に応じた符号化を施して配送するデータ配送ステップと、
を含むことを特徴とするデータ配送方法。
【請求項２】
前記経路設定ステップは、当該データ送信端末について符号化対応最小ホップ経路が複数存在したときに、当該データ送信端末から送信先の複数のデータ受信端末に至る複数経路において重複するリンクの数が最小となる符号化対応最小ホップ経路を設定することを特徴とする請求項１記載のデータ配送方法。
【請求項３】
前記符号化判定ステップは、前記最小ホップ経路上に位置するデータ中継端末において、自分が複数経路のデータ中継端末であることを、隣接端末が送信する制御パケットまたはデータパケットから検出し、当該データ中継端末が符号化判定端末として、前記符号化可否を判定することを特徴とする請求項１記載のデータ配送方法。
【請求項４】
前記経路設定ステップは、前記符号化判定端末において、前記符号化可否を可と判定した場合に、前記交差経路のうちの少なくとも１つの経路を基準経路として固定的に設定し、前記基準経路以外の少なくとも１つの他の経路のデータ送信端末から前記基準経路へ最小ホップを与える経路の接点となる端末をデータ符号化端末に設定し、当該他の経路のデータ受信端末から前記基準経路へ最小ホップを与える経路の接点となる端末をマルチキャスト端末に設定することを特徴とする請求項３記載のデータ配送方法。
【請求項５】
前記経路設定ステップは、前記データ符号化判定端末において、制御パケットを前記基準経路上の各データ中継端末に送信し、それを受信した各データ中継端末が自己の端末ＩＤと中継する度に数が１ずつ増加されるホップ数とを含む制御パケットをネットワーク全体にフラッディングすることによって、これを受信した上記経路以外の他の経路上のデータ送信端末及びデータ受信端末において、前記基準経路へ最小ホップを与える経路を発見し、前記基準経路から当該他の経路上のデータ送信端末への最小ホップ経路の接点となるデータ中継端末を前記データ符号化端末又は前記基準経路から当該他の経路上のデータ受信端末への最小ホップ経路の接点となるデータ中継端末をマルチキャスト端末とすることを特徴とする請求項４記載のデータ配送方法。
【請求項６】
前記経路設定ステップは、予めネットワークの各端末がお互いの経路やそのホップ数を認識し、前記データ符号化判定端末が前記基準経路上の各データ中継端末へ制御パケットを送信し，当該制御パケットを受信した前記基準経路上の各データ中継端末は自己の端末ＩＤと上記経路以外の他の経路のデータ送信端末及びデータ受信端末へのホップ数を追加し、前記基準経路上の末端となるデータ中継端末において、当該他の経路のデータ送信端末及びデータ受信端末へのホップ数が最小となる前記基準経路上のデータ中継端末のＩＤとそのホップ数を前記データ符号化判定端末に通知し，前記データ符号化判定端末において，前記基準経路から当該他の経路上のデータ送信端末への最小ホップ経路の接点となるデータ中継端末を前記データ符号化端末又は前記基準経路から当該他の経路上のデータ受信端末への最小ホップ経路の接点となるデータ中継端末をマルチキャスト端末とすることを特徴とする請求項４記載のデータ配送方法。
【請求項７】
あるデータ送信端末があるデータ受信端末に対して複数経路を経由して同一のデータを配送する場合に、当該複数経路のうちの少なくとも１つを非符号化経路に予め設定すると共に当該複数経路のうちの他を符号化可能経路に予め設定する事前設定ステップをさらに含むことを特徴とする請求項１記載のデータ配信方法。
【請求項８】
前記事前設定ステップは、当該あるデータ送信端末が送信元となる経路と、他のデータ送信端末が送信元となる経路が交差するデータ中継端末のうち符号化可能なデータ中継端末の個数を求め、当該個数がある閾値未満の経路を非符号化経路に設定し、ある閾値以上の経路を符号化可能経路に設定することを特徴とする請求項７記載のデータ配送方法。
【請求項９】
前記符号化判定ステップは、当該あるデータ送信端末から当該あるデータ受信端末までの経路上に存在するデータ中継端末またはこれに隣接する端末において、その端末が符号化判定端末として、前記符号化可否を、前記非符号化経路及び／又は前記符号化可能経路の設定に応じて判定することを特徴とする請求項７記載のデータ配送方法。
【請求項１０】
前記データを構成する各データパケットは、送信先のデータ受信端末と、当該データ受信端末に至る経路上の次ホップ端末ＩＤと、当該経路が符号化可能経路であるか否かを示すフラグとを各々が含む少なくとも１つの単位経路情報片を含み、
前記データ配送ステップは、前記データ符号化端末において、受信した複数のパケットのうち、あるデータ受信端末の端末ＩＤを含む単位経路情報片における次ホップ端末ＩＤに、自分の端末ＩＤを含んで、その対応する経路が符号化可能経路であり、かつ自分の端末ＩＤ以外の端末ＩＤを含んで、その対応する経路が非符号化可能経路であるパケットを抽出し、これらパケットに対して符号化を行うことを特徴とする請求項９記載のデータ配信方法。
【請求項１１】
前記経路設定ステップは、前記符号化判定端末において、前記符号化可否を可と判定した場合に、前記交差経路のうちの少なくとも１つの経路を基準経路に固定的に設定し、前記基準経路以外の少なくとも１つの他の経路のデータ送信端末から前記基準経路へ最小ホップを与える経路の接点となる端末をデータ符号化端末に設定することを特徴とする請求項３記載のデータ配送方法。
【請求項１２】
前記データ配送ステップは、前記データ符号化端末において、符号化後のデータパケットに、元のデータパケットのデータのシーケンス番号と、データ受信端末ＩＤと、送信先のデータ受信端末への経路の次ホップＩＤとを記述し、前記符号化後のデータパケットを受信した別のデータ符号化端末において、前記符号化後のデータパケットの記述内容に応じて、これらデータパケットに対してさらに符号化を行うことを特徴とする請求項４記載の無線通信システム。
【請求項１３】
前記データ配送ステップは、前記データ符号化端末において、受信したデータパケットの記述内容から、符号化前の要素データと符号後の要素データの中で、符号化前と符号後の両者の要素データとして含まれる以外の要素データを排他的論理和の要素として含むデータが、前記データ符号化端末を中継しない別経路を経由して送信先のデータ受信端末に配送されると認識された場合に、各要素データが当該送信先のデータ受信端末において復号可能であると判定し、当該受信したデータパケットに対してさらに符号化を行うことを特徴とする請求項４記載のデータ配送方法。
【請求項１４】
前記データを構成する各データパケットは、データ受信端末ＩＤと次ホップ端末ＩＤとの組合せから各々がなる複数の単位経路情報片を含み、
前記データ配送ステップは、前記データ符号化端末において、受信したデータパケットについて、当該端末の自端末ＩＤと一致する次ホップ端末ＩＤを含む単位経路情報片のデータ受信端末ＩＤに一致する少なくとも１つのＩＤが、全てのデータパケットの何れかの単位経路情報片のデータ受信端末ＩＤにあると共に、前記データ受信端末ＩＤに一致するＩＤ毎に、当該ＩＤを含む単位経路情報の次ホップ端末ＩＤと自端末ＩＤとが一致するデータパケットが１つのみである場合に当該受信したデータパケットに対して符号化に行うと共に、
さらに、次ホップ端末ＩＤと自端末ＩＤとが一致するデータパケットが複数存在する場合であって、その対応する経路が符号化可能経路であって、かつ次ホップ端末ＩＤに自分の端末ＩＤと一致せず、かつその対応する経路が非符号化経路ある端末ＩＤが１つ以上含む場合にも当該受信したデータパケットに対して符号化に行うことを特徴とする請求項４記載のデータ配信方法。
【請求項１５】
無線通信リンクを介して各々が隣接間で接続されている複数の端末がマルチホップネットワークを構成する無線通信システムであって、
前記端末のうちのデータ送信端末毎に、当該データ送信端末から送信先の少なくとも１つのデータ受信端末に至る複数経路の中から少なくとも２つの最小ホップ経路を抽出する経路抽出手段と、
前記データ送信端末毎に得られた最小ホップ経路のうちの少なくとも２つの交差経路の組合せ毎に、当該組合せの各交差経路に流れるデータの符号化可否を判定する符号化判定手段と、
前記交差経路毎に得られた符号化可否の判定結果に応じて、前記データ送信端末毎に、当該データ送信端末から送信先のデータ受信端末に至る符号化対応最小ホップ経路を設定する経路設定手段と、
前記データ送信端末毎に、当該データ送信端末について設定された符号化対応最小ホップ経路を介して、当該データ送信端末から送信先のデータ受信端末にデータを、当該符号化対応最小ホップ経路に対応する符号化可否の判定結果に応じた符号化を施して配送するデータ配送手段と、
を含むことを特徴とする無線通信システム。
【請求項１６】
無線通信リンクを介して各々が隣接間で接続され、マルチホップネットワークを構成する複数の端末のうちでデータの中継機能を担うデータ中継端末であって、
前記端末のうちのデータ送信端末毎に、当該データ送信端末から送信先の少なくとも１つのデータ受信端末に至る複数経路の中から少なくとも２つの最小ホップ経路を抽出する経路抽出手段と、
前記データ送信端末毎に得られた最小ホップ経路のうちの少なくとも２つの交差経路の組合せ毎に、当該組合せの各交差経路に流れるデータの符号化可否を判定する符号化判定手段と、
前記交差経路毎に得られた符号化可否の判定結果に応じて、前記データ送信端末毎に、当該データ送信端末から送信先のデータ受信端末に至る符号化対応最小ホップ経路を設定する経路設定手段と、
前記データ送信端末毎に、当該データ送信端末について設定された符号化対応最小ホップ経路を介して、当該データ送信端末から送信先のデータ受信端末にデータを、当該符号化対応最小ホップ経路に対応する符号化可否の判定結果に応じた符号化を施して配送するデータ配送手段と、
を含むことを特徴とするデータ中継端末。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、相互に無線通信可能な複数の無線通信端末から構成され、個々の無線通信端末が単独でデータ発生源としてデータを送信したりデータ終端側としてデータを受信したりする機能、並びにこれら送受信されるデータの中継を行うホップ転送機能を備えるマルチホップネットワークにおけるデータ配送方法、無線通信システム及びデータ中継端末に関する。
【背景技術】
【０００２】
複数の無線通信端末を含む無線マルチホップネットワークにおいては、無線通信端末のうちでデータ送信端末として機能する端末とデータ受信端末として機能する端末との間に複数の通信パスが形成されることからリンク障害に対して高い信頼性を備える。しかし他面、冗長な送信があり得ることからデータ量増加に伴うネットワーク負荷が問題となる。
【０００３】
この点、マルチキャストルーティングによって送信回数を削減する方法が知られている。しかし、かかる方法はリンクを集約して転送するため、リンク障害が発生したときに失われるデータ量が大きくなる危険が高く、また特定の端末にデータ配送のオーバヘッドが集中してしまう虞もある。また、データパケットの送信回数を削減する方法として、複数のデータパケットを集約処理して１つのデータパケットにまとめて送信する方法も考えられている。しかし、かかる方法では、パケット毎のオーバヘッドが削減されるものの、個々のパケットサイズが増大し十分な効率性の改善が望めない。
【０００４】
そこで、ネットワークコーディング（Network Coding）と称される考え方が導入され、データに対して特定の符号化アルゴリズムを適用してデータ量を削減することが提唱されている。例えば、非特許文献１は、複数のパケットのデータに対して一種の線型結合演算である排他的論理和演算を施して得られる符号化データを送信することでデータ量を削減する技術を開示している。
【０００５】
図１Ａ〜図１Ｃは、排他的論理和演算を利用したネットワークコーディングの利点を示している。ネットワークコーディングは、複数のデータの排他的論理和の計算を行って得られるデータを送信することで、送信するデータ量を減らしたり送信回数を減らしたりすることで信頼性を向上させる。背景説明として、図１Ａ及び図１Ｂはネットワークコーディングを行わない状況を示している。ここで、無線通信端末のうちで、２つのデータ送信端末Ｓ１及びＳ２と、２つのデータ受信端末Ｒ１及びＲ２と、４つのデータ中継端末Ｔ１〜Ｔ４が配置されているとする。データ送信端末Ｓ１は自身の生成データであるデータＤ＿Ｓ１をデータ受信端末Ｒ１に配送しようとし、データ送信端末Ｓ２は自身の生成データであるデータＤ＿Ｓ２をデータ受信端末Ｒ２に配送しようとしている。
【０００６】
図１Ａを参照すると、データ送信端末Ｓ１からデータ受信端末Ｒ１まで２回のＤ＿Ｓ１の転送が行われ、一方、データ送信端末Ｓ１からデータ受信端末Ｒ２まで４回のＤ＿Ｓ１の転送が行われる。データ送信端末Ｓ１からデータ中継端末Ｔ１及びＴ２への転送は同報通信（ブロードキャスト）であるから１回と数えられ、合計５回の送信が行われることになる。図１Ｂを参照すると、データ送信端末Ｓ２からＤ＿Ｓ２の転送について同様に合計５回の送信が行われる。結局、データＤ＿Ｓ１及びＤ＿Ｓ２のデータ受信端末Ｒ１及びＲ２への配送に合計１０回の送信が必要となることが分かる。
【０００７】
図１Ｃは、ネットワークコーディングを用いた場合を示している。データＤ＿Ｓ１はデータ中継端末Ｔ３を介し２回の送信を経てデータ受信端末Ｒ１に到達する。また、データＤ＿Ｓ２はデータ中継端末Ｔ４を介し２回の送信を経てデータ受信端末Ｒ２に到達する。データ送信端末Ｓ１及びＳ２の送信は同報通信であることから、データ中継端末Ｔ１は、データ送信端末Ｓ１及びＳ２からそれぞれデータＤ＿Ｓ１及びデータＤ＿Ｓ２を受信する。次いで、データ中継端末Ｔ１は、データＤ＿Ｓ１とデータＤ＿Ｓ２の排他的論理和であるデータＤ＿Ｓ１ XOR Ｄ＿Ｓ２をデータ中継端末Ｔ２に送信する（１回の送信）。データ中継端末Ｔ２は、受信したデータＤ＿Ｓ１ XOR Ｄ＿Ｓ２をそのままデータ中継端末Ｔ３及びＴ４の双方に送信する（１回の送信）。データ中継端末Ｔ３及びＴ４は受信したデータＤ＿Ｓ１ XOR Ｄ＿Ｓ２をデータ受信端末Ｒ１及びデータ受信端末Ｒ２にそれぞれ送信する（２回の送信）。
【０００８】
データ受信端末Ｒ１は、データＤ＿Ｓ１ XOR Ｄ＿Ｓ２とデータＤ＿Ｓ１の排他的論理和を計算することにより復号を行ってデータＤ＿Ｓ２を得る。一方、データ受信端末Ｒ１は、データＤ＿Ｓ１ XOR Ｄ＿Ｓ２とデータＤ＿Ｓ２の排他的論理和を計算することにより復号を行ってデータＤ＿Ｓ１を得る。結果的に、所望のデータ配送はデータ中継端末Ｔ１及びＴ２における送信回数がそれぞれ１回減って合計８回の送信が必要となる。排他的論理和をとったデータを送信することによりデータの送信量も減る。すなわち、ネットワークコーディングを行わない場合と比較してデータ送信数やデータ送信量が削減されることが分かる。
【０００９】
非特許文献１に開示される技術は、「各無線通信端末は、隣接端末が通知するデータ保持情報に従って符号化対象とすべきパケットを選択し、選択したパケットのデータの排他的論理和となるデータに符号化して、そのデータを送信する」とするものである。そして、排他的論理和をとる際の具体的なアルゴリズムは、「ｎ個のデータパケットｐ１、ｐ２、…ｐｎをそれぞれ、宛先のｎ個の次ホップ端末ｒ１、ｒ２、…ｒｎに送信するとき、各次ホップ端末ｒがｐｉ以外のｎ−１個のデータを保持しているときのみ、ｎ個のデータパケットｐ１、ｐ２、…ｐｎの排他的論理和をとったデータを送信する」という規則に基づいている。かかる規則に従うことで符号化データの復号可能性を保証し得る。
【００１０】
また、非特許文献２に開示されるように、無線マルチホップネットワークで動作する既存の多くのルーティングプロトコルは、ホップ数を経路構築のメトリックに設定し、データ送信端末からデータ受信端末までのホップ数が最小となる経路を構築するものである。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft, "XORs in The Air: Practical Wireless Network Coding," in Proc. of ACM, SIGCOMM 2006, Pisa, Italy, Sept. 2006.
【非特許文献２】C.Perkins, E. Belding-Royer, and S. Das, ``Ad-Hoc On-Demand Distance Vector (AODV) Routing,, '' RFC 3561, http://www.ietf.org/rfc/rfc3561.txt
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、非特許文献２の如く個々の端末が最小ホップ経路を構築する経路制御では、ネットワークコーディングを行う場合の、エンドツーエンドのデータ送データ受信端末間の経路制御について考慮されていない。そのため、複数のデータ送信端末が存在する形態においてネットワークコーディングを行う場合、それぞれのデータ送信端末とデータ受信端末の間で最小ホップ経路を構築しても全体のホップ数が最小化されない場合が存在するという課題がある。
【００１３】
また、複数のデータ送信端末やデータ受信端末が存在する場合、マルチキャストを行うことでパケットの送信回数を削減することも考えられる。しかしながら、データを集約して配送するため、あるリンクが切断したときにデータ受信端末への配送率が低下する可能性が高いという課題がある。
【００１４】
ここで図２Ａを参照すると、マルチキャストの形態は、複数のデータ受信端末Ｒ１、Ｒ２にデータを配信する際、共通するリンクでは１回だけデータ送信し、分岐点の端末ではデータをコピーしてそれぞれの経路にデータを配送する方法である。図２Ａではデータ送信端末Ｓ１、Ｓ２がそれぞれデータＤａ、Ｄｂをデータ受信端末Ｒ１、Ｒ２のそれぞれに配送する。経路を共有するため、経路を共有しない場合と比較して送信回数は削減される。データ中継端末ＴａでデータＤａとデータＤｂとの符号化を行うことができ、データ受信端末Ｒ１にはデータＤａとデータ（Ｄａ ＸＯＲ Ｄｂ）、データ受信端末Ｒ２にはデータＤｂとデータ（Ｄａ ＸＯＲ Ｄｂ））がそれぞれ届く。そして、例えばデータＤｂを得るためにデータＤａとデータ（Ｄａ ＸＯＲ Ｄｂ）の排他的論理和をとるというように、それぞれのデータ受信端末Ｒ１、Ｒ２においてデータが復号され、データＤａとデータＤｂをそれぞれ得る。図２Ａの例では総送信回数は２３回となる。あるデータを中継するデータ中継端末Ｔｘが何らかの原因で故障した場合、データ受信端末Ｒ１、Ｒ２にはそれぞれデータＤｂしか届かない。このようにマルチキャスト経路上でネットワークコーディングを行う場合は、総送信回数は抑制されるもの、同じデータが配送される経路が集約されているため、端末の故障やリンクのエラーに対する耐性が低いという問題がある。
【００１５】
さらに図２Ｂを参照すると、最小ホップルーティングでは、データ送信端末Ｓ１、Ｓ２からデータ受信端末Ｒ１、Ｒ２への最小パスが構築される。図２Ｂではデータ中継端末Ｔａでデータの符号化を行うことができ、上記のマルチキャストの場合と同様に、データ受信端末Ｒ１にはデータＤａとデータ（Ｄａ ＸＯＲ Ｄｂ））、データ受信端末Ｒ２にはデータＤｂとデータ（Ｄａ ＸＯＲ Ｄｂ））がそれぞれ届く。そして、それぞれの端末Ｒ１、Ｒ２においてデータが復号され、データＤａとデータＤｂを得る。図２Ｂの例では総送信回数は３５回となる。データ中継端末Ｔｘが何らかの原因で故障した場合においても、データ受信端末Ｒ１、Ｒ２ではそれぞれデータＤａ、データＤｂを得ることができ、データ受信端末Ｒ１、Ｒ２が連携することによってユーザは両方のデータを取得することができる。そのため、最小ホップ経路上でネットワークコーディングを行う場合は、データＤａがどちらのデータ受信端末においても得ることができないマルチキャスト経路上でネットワークコーディングを行う場合と比較して、端末の故障やリンクのエラーに対する耐性が高いものの、総送信回数が大きいという課題がある。
【００１６】
本発明は、上記した問題に鑑みてなされたものであり、その目的は、データ送信端末がデータ中継端末を経由してデータ受信端末宛てデータを配送する際にネットワークコーディングを行う場合にあっても、パケットの送信回数を削減して効率的にデータを配送することのできるデータ配送方法、無線通信システム及びデータ中継端末を提供することである。
【課題を解決するための手段】
【００１７】
請求項１に係る発明は、無線通信リンクを介して各々が隣接間で接続されている複数の端末がマルチホップネットワークを構成する無線通信システムにおけるデータ配送方法であって、前記端末のうちのデータ送信端末毎に、当該データ送信端末から送信先の少なくとも１つのデータ受信端末に至る複数経路の中から少なくとも２つの最小ホップ経路を抽出する経路抽出ステップと、前記データ送信端末毎に得られた最小ホップ経路のうちの少なくとも２つの交差経路の組合せ毎に、当該組合せの各交差経路に流れるデータの符号化可否を判定する符号化判定ステップと、前記交差経路毎に得られた符号化可否の判定結果に応じて、前記データ送信端末毎に、当該データ送信端末から送信先のデータ受信端末に至る符号化対応最小ホップ経路を設定する経路設定ステップと、前記データ送信端末毎に、当該データ送信端末について設定された符号化対応最小ホップ経路を介して、当該データ送信端末から送信先のデータ受信端末にデータを、当該符号化対応最小ホップ経路に対応する符号化可否の判定結果に応じた符号化を施して配送するデータ配送ステップと、を含むことを特徴とする。
【００１８】
請求項１５に係る発明は、無線通信リンクを介して各々が隣接間で接続されている複数の端末がマルチホップネットワークを構成する無線通信システムであって、前記端末のうちのデータ送信端末毎に、当該データ送信端末から送信先の少なくとも１つのデータ受信端末に至る複数経路の中から少なくとも２つの最小ホップ経路を抽出する経路抽出手段と、前記データ送信端末毎に得られた最小ホップ経路のうちの少なくとも２つの交差経路の組合せ毎に、当該組合せの各交差経路に流れるデータの符号化可否を判定する符号化判定手段と、前記交差経路毎に得られた符号化可否の判定結果に応じて、前記データ送信端末毎に、当該データ送信端末から送信先のデータ受信端末に至る符号化対応最小ホップ経路を設定する経路設定手段と、前記データ送信端末毎に、当該データ送信端末について設定された符号化対応最小ホップ経路を介して、当該データ送信端末から送信先のデータ受信端末にデータを、当該符号化対応最小ホップ経路に対応する符号化可否の判定結果に応じた符号化を施して配送するデータ配送手段と、を含むことを特徴とする。
【００１９】
請求項１６に係る発明は、無線通信リンクを介して各々が隣接間で接続され、マルチホップネットワークを構成する複数の端末のうちでデータの中継機能を担うデータ中継端末であって、前記端末のうちのデータ送信端末毎に、当該データ送信端末から送信先の少なくとも１つのデータ受信端末に至る複数経路の中から少なくとも２つの最小ホップ経路を抽出する経路抽出手段と、前記データ送信端末毎に得られた最小ホップ経路のうちの少なくとも２つの交差経路の組合せ毎に、当該組合せの各交差経路に流れるデータの符号化可否を判定する符号化判定手段と、前記交差経路毎に得られた符号化可否の判定結果に応じて、前記データ送信端末毎に、当該データ送信端末から送信先のデータ受信端末に至る符号化対応最小ホップ経路を設定する経路設定手段と、前記データ送信端末毎に、当該データ送信端末について設定された符号化対応最小ホップ経路を介して、当該データ送信端末から送信先のデータ受信端末にデータを、当該符号化対応最小ホップ経路に対応する符号化可否の判定結果に応じた符号化を施して配送するデータ配送手段と、を含むことを特徴とする。
【発明の効果】
【００２０】
本発明によるデータ配送方法、無線通信システム及びデータ中継端末によれば、任意の端末が自律分散的にネットワークコーディングに適した経路を構築する符号化対応（code-aware）ルーティングの方式が用いられる。これにより、従来のマルチキャストを利用した場合よりもデータ配送の信頼性が高く、各端末が最小パスでデータ受信端末までの経路を構築した場合よりも送信回数や送信数を削減することが可能となる。
【図面の簡単な説明】
【００２１】
【図１Ａ】ネットワークコーディングを行わない状況を示すブロック図である。
【図１Ｂ】ネットワークコーディングを行わない他の状況を示すブロック図である。
【図１Ｃ】ネットワークコーディングを行った状況を示すブロック図である。
【図２Ａ】マルチキャストにおけるネットワークコーディングの例を示す図である。
【図２Ｂ】最小ホップルーティングにおけるネットワークコーディングの例を示す図である。
【図３】本発明による１つの実施例を示し、無線通信システムの全体構成を示すブロック図である。
【図４】図３に示された各無線通信端末の内部構成を示すブロック図である。
【図５】経路情報テーブルの設定方法の処理手順を示すシーケンス図である。
【図６】図５に示された処理手順の結果更新される経路情報テーブルの設定例を示す図である。
【図７】データ送信端末がデータ配送を行う際に生成するデータパケットのフォーマットを示す図である。
【図８】データパケットの受信時の処理手順を示すフローチャートである。
【図９】図８に示されたデータ転送処理のより詳細の処理手順を示すフローチャートである。
【図１０】図９に示された処理手順の実際の様子を説明する説明図である。
【図１１】符号化対応（code-aware）ルーティングにおけるネットワークコーディングの例を示す図である。
【図１２】第２の実施例における多対多通信の例を示すブロック図である。
【図１３】第２の実施例における無線通信端末の構成を示すブロック図である。
【図１４】第２の実施例における最小ホップ経路の構築例を示す図である。
【図１５】第２の実施例における経路の交差例を示す図である。
【図１６】第２の実施例における経路の交差を検知する例を示す図である。
【図１７】第２の実施例における符号化判定端末から経路上のデータ中継端末への通知例を示す図である。
【図１８】第２の実施例における経路上のデータ中継端末からネットワーク上の各端末の制御パケットのフラッディング例を示す図である。
【図１９】第２の実施例における送データ受信端末から経路上への最小ホップ経路の構築例を示す図である。
【図２０】第２の実施例におけるデータ符号化端末及びマルチキャスト端末の決定例を示す図である。
【図２１】第２の実施例における送データ受信端末からデータ受信端末へのデータ配送例を示す図である。
【図２２】第２の実施例における再帰的符号化対応最小ホップ経路の構築例を示す図である。
【図２３】第２の実施例における符号化対応（code-aware）ルーティングの効果を示す図である。
【図２４】第３の実施例における多対一通信の例を示すブロック図である。
【図２５】第３の実施例における経路の交差を検知する例を示す図である。
【図２６】第３の実施例における多対一通信における経路情報による符号化判定の例を示す図である。
【図２７】第３の実施例における多対一通信におけるネットワークコーディングの例を示す図である。
【図２８】第３の実施例における多対一通信におけるネットワークコーディングの効果を示す図である。
【図２９】第４の実施例における多対多通信における同一経路上のデータ符号化例を示す図である。
【図３０】第４の実施例における同一経路における複数回のデータ符号化例の１回目のデータ符号化を示す図である。
【図３１】第４の実施例における同一経路における複数回のデータ符号化例の２回目のデータ符号化を示す図である。
【図３２】第５の実施例におけるあるデータ送信端末かあるデータ受信端末への経路が複数存在する多対多通信例を示す図である。
【図３３】第５の実施例における多対多通信におけるパケット情報による符号化判定例を示す図である。
【図３４】第５の実施例における多対多通信におけるパケット情報による符号化判定例を補足する図である。
【発明を実施するための形態】
【００２２】
本発明の第１の実施例について添付の図面を参照しつつ詳細に説明する。
【００２３】
尚、以降の説明において、無線通信端末の名称として、データ符号化判定端末、マルチキャスト端末、データ中継端末、データ受信端末及びデータ送信端末等の多様な名称が用いられるが、これらの名称は当該端末の当該実施例における役割に着目した名称であって、各端末は、特に機能を限定しない限り、基本的に同一の機能を備える無線通信端末を意味する。
【００２４】
＜第１の実施例＞
図３は、本発明による１つの実施例を示し、無線通信システムの全体構成を示している。ここで、ネットワーク状に相互に無線リンクで接続された複数の無線通信端末Ｔ１〜Ｔ１０が存在する。本図では例として１０台の無線通信端末Ｔ１〜Ｔ１０が示されているが、かかる台数は例示であって、２台以上の多数の無線通信端末が想定され得る。
【００２５】
無線通信端末Ｔ１〜Ｔ１０の各端末はデータの送受信が可能であると共に、データの中継が可能である。すなわち、複数の無線通信端末Ｔ１〜Ｔ１０を前提として、それらのうちの任意の端末がデータ送信端末として自身が生成したデータを、それ以外の任意のデータ受信端末に、残りの何れかのデータ中継端末を介して配送する。データの送受信とは、アプリケーションレイヤでのエンドツーエンドの送受信を意味し、データ送信端末が、例えばセンサのデータを計測するセンサ端末として機能し、データ受信端末が配送されたセンサデータを集めるデータ収集端末として機能し得る。一方、データの中継とは、アプリケーションレイヤより下位のレイヤにおいてデータをそのまま転送するのを基本とし、後に説明するアルゴリズムに従って必要に応じてデータの符号化や復号を行うことを意味する。
【００２６】
第１の実施例では、複数のデータ送信端末が複数のデータ受信端末に対してデータを送信する形態を想定している。かかる形態の利点としては、例えばセンサデータを複数のデータ受信端末で収集する場合、あるデータ受信端末で障害が発生しても別の稼働中のデータ受信端末でデータを収集できること、あるデータ受信端末までのデータ配送のリンク経路が障害等により消滅しても、利用できる別のリンク経路でデータを収集できることなどが挙げられる。
【００２７】
図４は、図３に示された各無線通信端末の内部構成を示している。無線通信端末Ｔ１〜Ｔ１０の各々は、経路情報テーブル２０５と、経路情報制御部２０１と、データパケット保持部２０２と、データパケット処理部２０３と、無線通信部２０４とから構成される。経路情報制御部２０１は、経路情報テーブル２０５を設定し、この設定内容に従ってデータ受信端末へのデータ配送のための経路制御を行う。パケット保持部２０２は、送受信するデータパケットを一時的に保持する。データパケット処理部２０３は、センシング等の所定機能に基づいて新たなデータパケットの生成や排他的論理和などの計算を行って新たなデータパケットの生成を行う。無線通信部２０４は、隣接する他の無線通信端末と無線通信によって経路制御パケットやデータパケットを送受信する。
【００２８】
図５は、経路情報テーブル２０５の設定方法の処理手順を示している。かかる処理手順は、各無線通信端末の経路情報制御部２０１（図４参照）によって実行され、データパケットの配送に先立って実行される。以下の説明において、複数の無線通信端末のうちデータ送信の運用を行う端末をデータ送信端末Ｓ１又はＳ２と表し、データ受信の運用を行う端末をデータ受信端末Ｒ１又はＲ２と表し、これらの間で中継を行う端末をデータ中継端末Ｔ１〜Ｔｎ（ｎは正数）で表すものとする。
【００２９】
先ず、データ受信端末Ｒ１は、自分の端末ＩＤ（自端末ＩＤ）と、シーケンス番号と、ホップ数を含む経路制御メッセージを定期的にフラッディング（Flooding）する。すなわち、データ受信端末Ｒ１は、定期の到来を判定し（ステップＳ１１）、もし到来していれば経路制御パケットをフラッディングする（ステップＳ１２）。もし到来していなければ定期到来迄待機して（ステップＳ１３）、ステップＳ１１以降の処理手順を反復継続する。
【００３０】
ここで、フラッディングとは、無線マルチホップネットワーク上に接続された送信可能なすべての無線通信端末に対して経路制御パケットを流すことを意味する。経路制御メッセージのホップ数には初期値として０が設定される。経路制御メッセージのシーケンス番号はフラッディング毎にインクリメントされる。すなわち、定期的に行われる複数のフラッディングのうちの１回のフラッディングにおいて同一シーケンス番号の経路制御パケットがネットワーク上にばらまかれることになる。従って、あるデータ中継端末には同一のシーケンス番号の複数の経路制御パケットが異なるリンク経路を介して到達する可能性がある。
【００３１】
データ中継端末Ｔ１は、フラッディングされた経路制御パケットの受信に応じて、当該パケットのシーケンス番号が当該データ受信端末（データ受信端末Ｒ１）について初めてのシーケンス番号か否かを判定し（ステップＳ１４）、もし以前に受け取ったものと同一である場合、これを破棄する。一方、初めてのシーケンス番号である場合には、データ中継端末Ｔ１は、当該経路制御メッセージに自端末ＩＤを付加し、ホップ数を１インクリメントする（ステップＳ１５）。次いで、当該経路制御パケットをさらにフラッディングする、例えば、図示される他のデータ中継端末Ｔ２に転送する（ステップＳ１６）。次に、データ中継端末Ｔ１は、データ受信端末Ｒから最短ホップとなるパスを選択して制御情報テーブルを更新する（ステップＳ１７）。
【００３２】
データ中継端末Ｔ２は、データ中継端末Ｔ１から転送された経路制御パケットに応じて、同様の処理手順（ステップＳ１４〜Ｓ１７）を実行する（ステップＳ１８）。
【００３３】
図６は、図５に示された処理手順の結果更新される経路情報テーブル２０５の設定例を示している。経路情報テーブル２０５は、データ受信端末の端末ＩＤ（データ受信端末ＩＤ）毎に最短ホップとなる次ホップ端末の端末ＩＤ（次ホップ端末ＩＤ）が設定される。ここでは、端末ＩＤを各無線通信端末の参照符号で代用して示している。本図を参照すると、例えば、データ受信端末Ｒ１へのデータパケットの配送はデータ中継端末Ｔ１に転送することが最短ホップを与えることを意味する。
【００３４】
図７は、データ送信端末がデータ配送を行う際に生成するデータパケットのフォーマットを示している。データがあるデータ送信端末で発生したとすると、当該データ送信端末は、そのデータの宛先となる全てのデータ受信端末ＩＤと、そのデータ受信端末の次ホップ端末ＩＤとの組合せからなる単位経路情報片１〜ｎを作成する。単位経路情報片１〜ｎは予定経路情報を構成し、当該データパケットの今後の予定経路を与える。
【００３５】
データ受信端末ＩＤと次ホップ端末ＩＤとの対応関係は、当該データ送信端末が保持する経路情報テーブル２０５（図６参照）の設定内容を基に作成される。単位経路情報片１〜ｎは宛先となるデータ受信端末の数（ｎ：正数）だけ作成され、データパケットのヘッダ部の一部を構成する。ヘッダ部にはさらに、データ識別部Ｄｉｄを含み、ヘッダ部の直後にデータ部Dが記載される。データ識別部Ｄｉｄは、データ部Ｄに格納されるデータの識別情報や符号化の対象となった元のデータの識別情報を含む。符号化を行う前の元のデータの識別情報の例として、そのデータの送信元端末IDとシーケンス番号が挙げられる。
【００３６】
図８は、データパケットの受信時の処理手順を示している。かかる処理手順の主体は無線通信端末のうちの１つであり、データ転送端末Ｔ１〜Ｔｎの何れか１である場合もあり得るし、最終的なデータパケットの宛先であるデータ受信端末Ｒ１又はＲ２である場合もあり得る。
【００３７】
先ず、無線通信端末は、データ送信端末によって送信（ブロードキャスト）されたデータパケットを受信したとする（ステップＳ２１）。当該データパケットの各単位経路情報片に含まれるデータ受信端末ＩＤと自端末ＩＤとが一致するか否かを判定する（ステップＳ２２）。もし一致する場合には、自身がデータ受信端末であることから、当該データパケットのデータに対して所望のアプリケーション処理を施す（ステップＳ２４）。尚、当該データパケットのデータがデータ符号化されていた場合には、ネットワークコーディングにおける復号処理を行った上で（ステップＳ２３）、アプリケーション処理を施す（ステップＳ２４）。
【００３８】
一方、ステップＳ２２において一致しない場合、無線通信端末は、さらに、当該データパケットの各単位経路情報片に含まれる次ホップ端末ＩＤと自端末ＩＤとが一致するか否かを判定する（ステップＳ２５）。もし一致しない場合には、自身がデータ受信端末でもデータ中継端末でもないことから、当該データパケットを破棄する（ステップＳ２６）。
【００３９】
一方、ステップＳ２５において一致する場合、無線通信端末は、自身がデータ中継端末であることから、当該データパケットを符号化処理した後、それを隣接する他の無線通信端末に転送（ブロードキャスト）する（ステップＳ２７）。
【００４０】
図９は、図８に示されたデータ転送処理のより詳細の処理手順を示している。かかる処理手順は、無線通信端末のうちのデータ中継端末において実行される。
【００４１】
先ず、データ中継端末は、ある待機期間Ｔだけ待機して、転送する必要がある複数のデータパケットを待ち受けて保持する（ステップＳ３１）。保持されるデータパケットはデータパケット保持部に格納される。前提として、図８に示された処理手順の結果、データパケットの単位経路情報片の何れかの次ホップ端末ＩＤに自端末ＩＤに一致するものが含まれている。
【００４２】
次に、データ中継端末は、データパケット保持部に保持された複数のデータパケットのうちから抽出条件を充足する符号化対象グループを抽出する（ステップＳ３２）。符号化対象グループに属するものと設定されるデータパケットの抽出条件は、「データ中継端末の自端末ＩＤと一致する次ホップ端末ＩＤを含む単位経路情報片のデータ受信端末ＩＤに一致する少なくとも１つのＩＤが、全てのデータパケットの何れかの単位経路情報片のデータ受信端末ＩＤにあると共に、該データ受信端末ＩＤに一致するＩＤ毎に、当該ＩＤを含む単位経路情報の次ホップ端末ＩＤと自端末ＩＤとが一致するデータパケットが１つのみである」とする条件である。かかる抽出条件の充足が求められるのは、「一般にあるデータＤｉ（１≦ｉ≦Ｎ）のデータ受信端末において、データＤ１、Ｄ２・・ＤＮの中でＤｉ以外のすべてのＮ−１個のデータを受信している状態で、Ｄｉを線形結合に含む任意のデータを受信すれば、Ｄｉを復号することができる。」とする原理に依拠する。
【００４３】
次に、データ中継端末は、符号化対象グループに属する複数のデータパケットのデータに対してデータ符号化を行い、結合された新たな１つの符号化データパケットを生成して転送する（ステップＳ３３）。この際に、新たな符号化データパケットのヘッダ部には、符号化される前の元のデータパケットにおいて自端末ＩＤと一致する次ホップ端末ＩＤを含む単位経路情報片におけるデータ受信端末ＩＤと、経路情報テーブルから参照された次ホップ端末ＩＤとの組合せが新たな単位経路情報片として記述される。また、それぞれの元のデータパケットにおけるデータの排他的論理和の識別情報（Ｄａ＿ｉｄ、Ｄｂ＿ｉｄ、Ｄｃ＿ｉｄ）もデータ識別部に記述される。新たな符号化データパケットはブロードキャストされることで他の無線通信端末に転送される。
【００４４】
次に、データ中継端末は、保持していたデータパケットについて全ての符号化対象グループが抽出されたか否か判定し（ステップＳ３４）、もし抽出されていなければステップＳ３２〜Ｓ３３を反復する。もし抽出されたならば、データ中継端末は、残った単独のデータパケットを、その単位経路情報片の内容を経路情報テーブルから参照される次ホップ端末ＩＤに振り直した上でデータをそのままにして転送する（ステップＳ３５）。
【００４５】
以上の処理手順における待機時間Ｔの選定は、条件を満たすデータパケットをなるべく多く取り出すことでデータパケットの送信数や送信量を削減できるようにすると共に、過度のデータ遅延が発生しないように適切に調整される必要がある。
【００４６】
図１０は、図９に示された処理手順の実際の様子を示している。データ中継端末Ｔ１がデータパケットａ、データパケットｂ、データパケットｃをある期間Ｔに受信したとする。
【００４７】
データ中継端末Ｔ１は、各データパケットについて、その中の次ホップ端末ＩＤが自端末ＩＤと一致する単位経路情報片、すなわち、単位経路情報片１、単位経路情報片２及び単位経路情報片３を見つける。データパケットａの中に存在する単位経路情報片１のデータ受信端末ＩＤはＲ１であるが、Ｒ１はデータパケットｂ、データパケットｃにも存在する。データパケットｂの中に存在する単位経路情報片２のデータ受信端末ＩＤはＲ３であるが、Ｒ３はデータパケットａ、データパケットｃにも存在する。データパケットｃの中に存在する単位経路情報片３のデータ受信端末ＩＤはＲ４であるが、Ｒ４はデータパケットａ、データパケットｂにも存在する。そこで、データパケットａ、データパケットｂ及びデータパケットｃの３つが符号化対象グループの候補となる。
【００４８】
次に、データ中継端末Ｔ１は、各単位経路情報片のデータ受信端末ＩＤ毎に、その次ホップ端末ＩＤと自分端末ＩＤと一致するデータパケットが１つのみであるか否かを判定する。単位経路情報片１のデータ受信端末ＩＤ＝Ｒ１に着目とすると、データパケットａの１つだけが次ホップ端末ＩＤが自端末ＩＤであるＴ１と等しい。データパケットｂでは、データ受信端末ＩＤ＝Ｒ１の次ホップ端末ＩＤはＴ３であり、データパケットｃでは、データ受信端末ＩＤ＝Ｒ１の次ホップ端末ＩＤはＴ２であり、何れもＴ１以外になっている。
【００４９】
同様に、単位経路情報２のデータ受信端末ＩＤ＝Ｒ３や単位経路情報３のデータ受信端末ＩＤ＝Ｒ４についても上記の条件を満たしている。
【００５０】
以上の結果、データパケットａ、データパケットｂ及びデータパケットｃが１つの符号化対象グループに括られる。そこで、データ中継端末Ｔ１は、データパケットａ、ｂ、ｃのそれぞれのデータパケットに含まれるデータＤａ、Ｄｂ、Ｄｃの排他論理和演算によるデータ符号化を施し、さらに、次ホップ端末ＩＤが自端末ＩＤと一致する単位経路情報片１〜３のデータ受信端末の端末Ｒ１、Ｒ３及びＲ４から自分の経路情報テーブルを参照して新たな単位経路情報片４〜６を作成し、さらに元のデータパケットのデータ識別部を付加して、新たなデータパケットを作成する。
【００５１】
以上の処理手順が複数のデータ中継端末によって実行される結果、データＤａ及びデータＤｂ及びデータＤｃの排他的論理和を含むデータ符号化されたデータパケットがデータ受信端末Ｒ１、Ｒ３及びＲ４に届くことになる。
【００５２】
データ受信端末Ｒ１におけるデータＤａの復号について説明する。データ受信端末Ｒ１には、データＤａ及びデータＤｂ及びデータＤｃの排他的論理和を含むデータが符号化されたデータパケットをデータ中継端末Ｔ１を介して届けられる一方、データＤｂを含むデータパケットｂやデータＤｃを含むデータパケットｃがデータ中継端末Ｔ１以外の経路を経由して届けられる。そこで、データ受信端末Ｒ１は、Ｄａ＝（Ｄａ XOR Ｄｂ XOR Ｄｃ） XOR Ｄｂ XOR Ｄｃの演算をおこなうことでデータＤａを復号することができる。同様に、データ受信端末Ｒ３ではデータ符号化されたデータパケットの他にデータパケットａやデータパケットｃも届く。また、データ受信端末Ｒ４ではデータ符号化されたデータパケットの他にデータパケットａやデータパケットｂも届く。そのため、同様にそれぞれのデータを得ることができる。
【００５３】
以上の第１の実施例から明らかなように、本発明によるデータ配送方法及び無線通信システムは幾つかの作用効果をもたらす。第１に、本発明では、隣接端末がデータを保持したり、その保持情報を管理したりする必要がない。各無線通信端末は、最終的なデータ受信端末のデータ受信情報からデータ符号化の可否を判定してデータ符号化を行い、隣接端末のデータ受信情報が不要となるため、データ符号化の適用範囲を広げることができる。第２に、本発明は消費電力を削減することができる。一般に無線センサネットワークでは計算を行うよりパケットを送信する際の消費電力が大きい。本発明ではデータの増加に伴う計算量は増加するものの、データの送信量を削減できる。第３に、本発明は、特定の端末で集中制御することなく、自律分散的にネットワークコーディングを行うことができる。第４に、本発明は、それぞれのデータの到達する端末で、データの復号が可能となるようにネットワークコーディングを行うことができる。
【００５４】
＜第２の実施例＞
図１１は、本発明において用いられる符号化対応（code-aware）ルーティングの原理を示している。符号化対応（code-aware）ルーティングは、複数のデータ受信端末Ｒ１、Ｒ２にデータを配信する際、ネットワークコーディングを行うことを意識して全体の総送信回数を最小化するルーティングである。データＤａとデータＤｂの符号化をデータ中継端末Ａで行う。符号化されたデータ（Ｄａ ＸＯＲ Ｄｂ）はデータ受信端末Ｒ１、Ｒ２にマルチキャストされる。データ送信端末Ｓ１からデータ受信端末Ｒ２までの経路やデータ送信端末Ｓ２からデータ受信端末Ｒ１までの経路は最短経路ではないものの、データの符号化を経路の上流で行うことで総送信数は３０となり、最小ホップ経路上でネットワークコーディングを行う場合よりも総送信回数は小さくなる。また、最小ホップ経路上でネットワークコーディングを行う場合と同様に、データ中継端末Ｘが何らかの原因で故障したとしても、データ受信端末Ｒ１、Ｒ２ではそれぞれデータＤａ、データＤｂを受信することができる。
【００５５】
このように、符号化対応（code-aware）の経路上でネットワークコーディングを行う場合は、マルチキャスト経路上でネットワークコーディングを行う場合よりも、端末の故障やリンクのエラーに対する耐性が高く、最小ホップ経路上でネットワークコーディングを行う場合よりも総送信回数は小さくなるという効果が得られる。
【００５６】
図１２は、第２の実施例における多対多通信の例を示している。本図に示すように、ネットワーク内の複数のデータ送信端末Ｓ１〜Ｓ５が複数のデータ受信端末Ｒ１〜Ｒ４に対してデータを送信する。
【００５７】
図１３は、第２の実施例における無線通信端末の構成を示している。無線通信端末Ｔ１〜Ｔｎの各々は、第１の実施例と同様に、経路情報テーブル２０５と、経路情報制御部２０１と、データパケット保持部２０２と、データパケット処理部２０３と、無線通信部２０４とから構成される。第２の実施例における経路情報制御部２０１は、さらに、第１の実施例と異なり、最小ホップ経路構築制御部６０１と、データ符号化判定部６０２と、経路再構築制御部６０３と、を含む。最小ホップ経路構築制御部６０１は、本発明の構成要素である経路抽出手段を実現し、データ送信端末からデータ受信端末までの最小ホップ経路の構築を行う機能を備える。データ符号化判定部６０２は、本発明の構成要素である符号化判定手段を実現し、複数の経路が交差した場合にその経路を流れるデータの符号化が可能かどうか判定する機能を備える。経路再構築制御部６０３は、本発明の構成要素である経路設定手段を実現し、データ符号化判定部の判定結果に基づいて経路を構築する機能を備える。
【００５８】
符号化対応（code-aware）経路の構築は、３つのフェーズを経て行われる。すなわち、第１のフェーズとして、最小ホップ経路構築制御部６０１によって実行される「データ送信端末からデータ受信端末までの最小ホップ経路の構築するフェーズ」と、第２のフェーズとして、データ符号化判定部６０２によって実行される「経路の交差の検知とデータの符号化の判定するフェーズ」と、第３のフェーズとして、経路再構築制御部６０３によって実行される「経路を再構築するフェーズ」との３つのフェーズがある。
【００５９】
＜データ送信端末からデータ受信端末までの最小ホップ経路の構築＞
図１４は、第２の実施例における最小ホップ経路の構築例を示している。第２の実施例においては、通常の最小ホップ経路構築方法に比してより送信コスト削減の効果の大きい方法が説明される。すなわち、ある１つのデータ送信端末からあるデータ受信端末への最短経路が複数あった場合、ある１つのデータ送信端末からの経路上のリンクがなるべく重複しないように、リンクの重複回数が最小となる経路を生成する。
【００６０】
本図を参照すると、データ受信端末Ｒ１及びデータ受信端末Ｒ２は自分からのホップ数とデータ中継端末の端末ＩＤを記述した制御パケットをフラッディングする。データ中継端末を経由するごとに制御パケットのホップ数は１ずつ増加し、データ中継端末の端末ＩＤが追加される。データ送信端末Ｓ１はデータ受信端末Ｒ１がフラッディングした制御パケットをデータ中継端末Ｔ１及びＴ２を経由して受信する。またデータ送信端末Ｓ１はデータ受信端末Ｒ２がフラッディングした制御パケットをデータ中継端末Ｔ１及びＴ２、またデータ中継端末Ｔ３及びＴ４を経由して受信する。データ送信端末Ｓ１からデータ受信端末Ｒ２までの最小ホップ経路として、データ中継端末Ｔ１及びＴ２を経由する経路Ａが存在し、また、データ受信端末Ｒ２までの最小ホップ経路として、データ中継端末Ｔ１及びＴ２を経由する経路Ｂと、データ中継端末Ｔ３及びＴ４を経由する経路Ｃとの２本が存在することが分かったとする。この場合、経路Ａと経路Ｂは経路上の一部のリンクが重複する。一方、経路Ａと経路Ｃは重複するリンクがないため、データ送信端末Ｓ１は経路Ｂではなく、経路Ｃをデータ受信端末Ｒ２までの最小ホップ経路として採用する。各データ送信端末は自分が採用した各データ受信端末への経路上の端末に「経路上の端末」であることを通知する。
【００６１】
このようにあるデータ送信端末からあるデータ受信端末への複数の経路がなるべく重複しないように構築されることで、異なるデータ送データ受信端末間で構築される経路上の端末が重複した際、データの符号化を行われる機会を増加することができる。
【００６２】
＜経路の交差の検知とデータの符号化の判定＞
図１５は、第２の実施例における経路の交差例を示している。複数のデータ送データ受信端末が上記のように最小ホップ経路を構築した場合、経路が交差することがある。本図の例ではデータ送信端末Ｓ１からデータ受信端末Ｒ２までの経路Ａとデータ送信端末Ｓ２からデータ受信端末Ｒ１までの経路Ｂが交差している。このような場合、データ中継端末が経路の交差を以下のように検知する。
【００６３】
図１６は、第２の実施例における経路の交差を検知する例を示している。図１６の（ａ）の場合、ある端末が複数の経路のデータ中継端末Ｔ１となる場合、データ中継端末Ｔ１は経路の交差を検知可能である。データ中継端末Ｔ１は符号化判定端末Ｔｄとなる。一方、図１６の（ｂ）の場合、２つの経路が交差する部分において、ある端末が複数の経路のデータ中継端末とならない場合がある。各データ中継端末は自分が中継するデータの送信元であるデータ送信端末やデータの宛先であるデータ受信端末のＩＤなどの情報を広告する。それによって隣接端末の中継するデータやそのデータ送信端末やデータ受信端末のＩＤを知ることができ、経路の交差を検知する。経路の交差を検知したデータ中継端末は、交差した経路上を流れるデータが符号化可能かどうか判定する符号化判定端末となる。図１６の（ｂ）の場合は、２つのデータ中継端末Ｔ１及びＴ２が経路の交差を検知するが、２つのデータ中継端末Ｔ１及びＴ２が情報交換するなどして、どちらか片方のデータ中継端末（本図の場合Ｔ１）が符号化判定端末Ｔｄとなる。符号化可能かどうかの判定アルゴリズムは、例えば、第１の実施例おいて説明されたアルゴリズムに従う。
【００６４】
＜経路の再構築＞
符号化判定端末において、符号化可能と判定した場合に、交差経路のうちの少なくとも１つの経路を基準経路として固定的に設定し、当該基準経路以外の少なくとも１つの他の経路のデータ送信端末から当該固定的に設定した経路へ最小ホップを与える経路の接点となる端末をデータ符号化端末に設定し、当該他の経路のデータ受信端末から当該基準経路へ最小ホップを与える経路の接点となる端末をマルチキャスト端末に設定して経路の再構築を行う。かかる経路の再構築は、以下の２つの方法の何れかを用いて行うことができる。尚、下記の経路Ａは基準経路を示している。
【００６５】
＜第１の構築方法＞
図１７〜図１９は、第２の実施例における第１の構築方法を示している。図１７に示すように、符号化判定端末Ｔｄは、１つの経路Ａの各データ中継端末に制御パケットを転送する。経路Ａの始点はデータ送信端末Ｓ１であり、終点はデータ受信端末Ｒ２である。
【００６６】
図１８に示すように、符号化判定端末Ｔｄからの制御パケットの転送に応じて、各データ中継端末Ｔｉ（ｉ＝１〜ｎ、ｎは経路上のデータ中継端末の数）は自分の端末ＩＤとホップ数を記述した制御パケットをネットワーク全体にフラッディングする。制御パケット内のホップ数は、発信するデータ中継端末Ｔｉにおいて０に設定され、途中のデータ中継端末Ｔｉを経由するたびに１ずつ増加される。
【００６７】
図１９に示すように、データ中継端末からの制御パケットの受信に応じて、データ送信端末Ｓ２は、経路Ａのデータ中継端末からのホップ数を知って、経路Ａへの最小ホップ経路Ｃを知る。そして、データ送信端末Ｓ２は、自分からその経路Ｃへの最小ホップ経路の接点となるデータ中継端末に通知し、通知されたデータ中継端末はデータ符号化端末Ｔｃとなる。一方、データ受信端末Ｒ１は、自分から経路Ａへの最小ホップ経路Ｄの接点となるデータ中継端末に通知し、通知されたデータ中継端末はマルチキャスト端末Ｔｍとなる。データ符号化端末Ｔｃはデータの符号化を行う端末であり、マルチキャスト端末Ｔｍは符号化されたデータをマルチキャストする端末である。
【００６８】
＜第２の構築方法＞
図２０は、第２の実施例における第２の構築方法を示している。第２の構築方法は、予めネットワーク内の各端末がネットワーク全体に制御パケットをフラッディングする例である。前提として、ネットワーク内の各端末は相手端末への経路の次ホップ端末ＩＤとホップ数を知っているものとする。
【００６９】
先ず、第２の構築方法は、第１の構築方法と同様に、データ符号化判定端末Ｔｄは、経路Ａの端末上に制御パケットを転送する。経路Ａ上のデータ中継端末は自分の端末ＩＤや、データ送信端末Ｓ１及びデータ受信端末Ｒ２へのホップ数を制御パケットに追加し、経路Ａの両末端のデータ中継端末Ｔａ及びＴｂまで制御パケットが転送される（図２０の丸１）。
【００７０】
次に、経路Ａの末端のデータ中継端末Ｔａ及びＴｂの各々は、経路Ａ上のデータ中継端末の中で、データ送信端末Ｓ２へのホップ数が最も小さいデータ中継端末のＩＤとそのホップ数、およびデータ受信端末Ｒ１へのホップ数が最も小さいデータ中継端末のＩＤとそのホップ数をデータ符号化判定端末Ｔｄに通知する（図２０の丸２）。
【００７１】
次に、データ符号化判定端末Ｔｄは、これら両端末からの情報を基にして、データ送信端末Ｓ２へのホップ数が最も小さい端末と、データ受信端末Ｒ１へのホップ数が最も小さいデータ中継端末を判別する。次いで、データ送信端末へのホップ数が最も小さいデータ中継端末をデータ符号化端末Ｔｃに決定し、データ受信端末へホップ数が最も小さいデータ中継端末をマルチキャスト端末Ｔｍに決定する。そして、データ符号化判定端末Ｔｄは、この決定結果を、データ符号化端末Ｔｃ及びマルチキャスト端末Ｔｍに通知する（図２０の丸３）。
【００７２】
次に、データ符号化端末Ｔｃは自分がデータ符号化端末であることをデータ送信端末Ｓ１及びＳ２に通知し、マルチキャスト端末Ｔｍは自分がマルチキャスト端末であることをデータ受信端末Ｒ１及びＲ２に通知する。
【００７３】
以上の第２の構築方法では、ネットワークの初期化においては各端末がネットワーク全体にフラッディングするため、第１の構築方法と比較して制御パケットの送信回数が多い。しかし、経路を再構築する動作において、第１の構築方法のようにデータ中継端末が経路を再構築する度にフラッディングする必要がないため、第１の構築方法と比較して経路を再構築する際の制御パケットの送信回数が少ない。
【００７４】
図２１は、第２の実施例におけるデータ送信端末からデータ受信端末へのデータ配送例を示している。ここでは、第１の構築方法または第２の構築方法の実行を経て、構築された経路上でデータが流れる様子を示している。データ送信端末Ｓ１とデータ送信端末Ｓ２からそれぞれ送信されるデータＤａとデータＤｂとは、データ符号化端末Ｔｃにおいて符号化され、データ（Ｄａ ＸＯＲ Ｄｂ）となる。データ（Ｄａ ＸＯＲ Ｄｂ）はデータ送信端末Ｓ１、Ｓ２からの共通経路を経由してマルチキャスト端末Ｔｍに配送される。マルチキャスト端末Ｔｍにおいて、データ（Ｄａ ＸＯＲ Ｄｂ）はデータ受信端末Ｒ１、Ｒ２のそれぞれに対してマルチキャストされる。
【００７５】
図２２は、第２の実施例における再帰的最小ホップ経路の構築例を示している。本図に示すように、上記方法によって構築された経路がさらに他の経路Ｃと交差する場合がある。この場合、まずデータ送信端末からのホップ数が小さいデータ符号化判定端末が経路再構築の動作の起点となって再構築を行う。再構築した経路においても、さらに同様に再帰的に経路を再構築する。
【００７６】
図２２を参照すると、本図の点線で示された経路Ｅは、矢印の始点に近い方が終点に近いほうに向かって、データ送信端末がデータ受信端末への経路を示している。経路Ｅは、実線で示された経路と３点で交差している。その交差する場所を、矢印の始点から終点方向に順番に交差点１、交差点２、交差点３とすると、交差点１に対応するデータ中継端末がデータ送信端末からのホップ数が小さいデータ符号化判定端末となる。そのため、そのデータ符号化判定端末が経路再構築の動作の起点となって、上記した２つの経路が１点で交差する場合と同様の方法で経路を再構築する。
【００７７】
経路を再構築するとその再構築された経路では、別の経路と別の交差点で交差する可能性がある（その交差点は交差点１〜３とは限らない）。その場合も同様にデータ送信端末側に近い交差点に対応するデータ中継端末がデータ符号化判定端末となって経路を再構築する。この動作は再構築された経路と、別の経路が交差しなくなるまで再帰的に行われる。
【００７８】
図２３は、第２の実施例における符号化対応（code-aware）ルーティングの効果を示している。図２３（ａ）はデータ送信端末Ｓ１とデータ送信端末Ｓ２からデータ受信端末Ｒ１とデータ受信端末Ｒ２への最小ホップ経路を構築し、データ符号化端末Ｔｃとマルチキャスト端末Ｔｍとが一致する場合である。この場合、総送信回数は３５回となる。一方、図２３（ｂ）の符号化対応（code-aware）ルーティングの場合は、データ送信端末Ｓ２及びデータ受信端末Ｒ１から経路Ａ（データ送信端末Ｓ１→データ受信端末Ｒ２）へのホップ数が短くなる。そして、符号化されたデータ（Ｄａ ＸＯＲ Ｄｂ）が流れる共通のリンクの数が増加するため、総送信回数は３２回に減少する。
【００７９】
以上のように、第２の実施例によれば、第１に、マルチキャスト経路上でネットワークコーディングを行う場合よりも、端末やリンクのエラーが起きたときのデータの損失する可能性が少ない。第２に、各端末が自律分散的にネットワークコーディングに適した経路（符号化対応最小ホップ経路）を構築することができ、データの送信量や送信回数を削減できる。
【００８０】
＜第３の実施例＞
第３の実施例では、あるデータ送信端末からあるデータ受信端末への経路が複数存在し、データ送信端末が複数存在する多対一通信における符号化対応（code-aware）ルーティング方法について説明する。また、その効果について説明する。
【００８１】
図２４は、第３の実施例における多対一通信の例を示している。本図に示すように、第３の実施例は、第２の実施例とは異なり、１つのデータ受信端末Ｒ１に対して複数のデータ送信端末Ｓ１〜Ｓ５が複数の経路でデータを配信する。各無線通信端末の構成は第２の実施例と同様である。
【００８２】
先ず、各データ送信端末Ｓ１〜Ｓ５はデータ受信端末Ｒ１に対して同じデータが流れる複数の経路を構築する。構築のアルゴリズムは既存のマルチパスル−ティングを用いる。その際、データ送信端末Ｓ１〜Ｓ５が異なる経路同士がなるべく交差するような経路を構築すれば、符号化対応（code-aware）ルーティングの効果が大きい経路が構築されやすい。データ送信端末Ｓ１〜Ｓ５はデータ受信端末Ｒ１への複数の経路の中で、符号化されないデータを流す１つ以上の非符号化経路を決定する。また、非符号化経路以外の経路を符号化可能経路とする。符号化可能経路上を流れるデータを符号化することは可能であるが、データが必ずしも符号化されるとは限らない。どの経路を非符号化経路とするかの選択は任意であるが、予め事前に設定される必要がある。
【００８３】
どの経路を非符号化経路とするかを選択する方法として、例えば、あるデータ送信端末が送信元となる経路と、他のデータ送信端末が送信元となる経路が交差するデータ中継端末のうち符号化可能なデータ中継端末の個数を求め、当該個数がある閾値未満の経路を非符号化経路に設定し、ある閾値以上の経路を符号化可能経路に設定することが考えられる。
【００８４】
また、例えば、データ送信端末からデータ受信端末への複数の経路のうち、他の経路と交差するリンクや端末の数が最も少ない経路を非符号化経路とし、それ以外を符号化可能経路とする。データ送信端末が異なる経路のうち、符号化可能経路同士が交差した場合はデータの符号化が可能であると判定する。
【００８５】
図２５は、第３の実施例における経路の交差例を示している。本図に示すように、符号化判定を行うデータ中継端末Ｔｄは、第２の実施例と同様、経路の交差を検知したデータ中継端末である。以下にデータパケットの内容からデータの符号化が可能かどうかの判定を行う方法を説明する。
【００８６】
図２６は、多対一通信における経路情報を用いた符号化判定を行う例を示している。本図に示すように、データパケットは、データ受信端末ＩＤと、当該経路への次ホップの端末ＩＤと、当該経路が符号化可能経路か否かを示す符号化経路フラグとからなる単位経路情報片を少なくとも１つ含む。符号化経路フラグには、符号化可能経路の場合には１が立てられ、非符号化可能経路の場合には０が立てられる。
【００８７】
そこでまず、データ中継端末が受信した各データパケットの次ホップの端末ＩＤが自分の端末ＩＤと一致し、かつその経路の符号化経路フラグが１であり、かつ各データパケットに自分以外の次ホップの端末ＩＤがあって、その符号化経路フラグが０であるものが存在する場合には、それらのデータパケットのデータは符号化可能であると判定する。「次ホップの端末ＩＤが自分の端末ＩＤと位置する経路の符号化経路フラグが１」ということは自分が中継するデータの符号化が可能であるということを意味する。また「各データパケットに自分以外の次ホップの端末ＩＤがあって、それらを経由する経路の符号化経路フラグが０である」というのは元のデータが符号化されないまま他の経路を経由してデータ受信端末に届くことを意味している。
【００８８】
図２６の例では、データ中継端末Ｎ１が受信したデータパケットａ及びデータパケットｂは、データ中継端末Ｎ１の端末ＩＤ（すなわち、Ｎ１）を含み、それぞれのデータパケットにおける符号化経路フラグが１、しかもデータパケットａ及びデータパケットｂにはそれぞれデータ中継端末Ｎ１以外の次ホップの端末ＩＤであるＮＡやＮＣが各々存在し、それらを経由する経路における符号化経路フラグが０である。従って、データパケットａ及びデータパケットｂは符号化可能であると判定される。
【００８９】
図２５を再び参照すると、データ送信端末Ｓ１、Ｓ２は、それぞれのデータＤａ、データＤｂをそれぞれ２つの経路を構築して端末Ｒ１まで配送する。そして、上記判定の結果、データ送信端末Ｓ１は、符号化可能経路Ａと非符号化経路Ｃを持ち、データ送信端末Ｓ２は、符号化可能経路Ｂと非符号化経路Ｄを持つ。符号化可能経路Ａと符号化可能経路Ｂとが交差する。この場合、第２の実施例と同様に、交差を検知した端末がデータ符号化判定端末Ｔｄとなり経路を再構築する。
【００９０】
図２７は、第３の実施例における多対一通信におけるネットワークコーディングの例を示している。本図に示すように、データ送信端末Ｓ２は、データ送信端末Ｓ１から張られる符号化可能経路Ａへの最小ホップ経路Ｃを構築し、接点となる端末をデータ符号化端末Ｔｃとする。
【００９１】
図２８は、第３の実施例における多対一通信におけるネットワークコーディングの効果を示している。図２８（ａ）は、データ送信端末Ｓ１、Ｓ２からデータ受信端末Ｒ１への最小ホップ経路を構築し、データ符号化端末Ｔｃにおいてデータの符号化を行う場合であり、総送信回数は３５回となる。一方、図２８（ｂ）は、符号化対応（code-aware）ルーティングを行う場合であり、データ送信端末Ｓ２から経路Ａ（データ送信端末Ｓ１→データ受信端末Ｒ１）へのホップ数が短くなり、かつデータ符号化端末Ｔｃによって符号化されたデータ（Ｄａ ＸＯＲ Ｄｂ）が流れる共通のリンクの数が増加するため、総送信回数は３０回に減少する。
【００９２】
以上のように、第３の実施例によれば、各端末が自律分散的にネットワークコーディングに適した経路を構築することができ、データの送信量や送信回数を削減できる。
【００９３】
尚、第３の実施例では、図２６に示されたように、経路情報がデータパケットごとに記述されている例が説明されたが、データパケットごとに記述されるのではなく、これらの情報を予め制御パケットでデータ中継端末に通知しておくようにしても良い。
【００９４】
＜第４の実施例＞
第４の実施例では第１の実施例のデータ符号化の判定法を拡張した方式に説明する。第１の実施例では、ある経路上に流れるデータを１回符号化する例について説明したが、第４の実施例では同じ経路上で複数回データの符号化を行う例について説明する。第４の実施例における端末構成は、多対多通信以外は第２の実施例の構成と同じである（図１３参照）。
【００９５】
図２９は、第４の実施例における多対多通信における同一経路上のデータ符号化例を示している。本図に示されるように、ある経路を流れる複数のデータが各々符号化される。データ送信端末Ｓ１、Ｓ２及びＳ３からそれぞれデータＤａ、Ｄｂ、Ｄｃがデータ受信端末Ｒ１、Ｒ２、Ｒ３へデータに配送される。データ送信端末Ｓ１からデータ受信端末Ｒ３までの経路上のデータ中継端末Ｎ１、Ｎ４においてそれぞれデータの符号化が可能である。同様にデータ中継端末Ｎ２、Ｎ３、Ｎ４、Ｎ５においてもデータの符号化が可能である。結果として、データ受信端末Ｒ１、Ｒ２、Ｒ３ではそれぞれ、データＤａ、Ｄｂ、Ｄｃを要素として含む線形独立な３つのデータを受信するため、データＤａ、Ｄｂ、Ｄｃを得ることができる。以下、あるデータ送信端末からデータ受信端末への経路において複数回符号化を行うために、経路情報からデータ符号化の判定を行う方法について説明する。  
【００９６】
図３０は、第４の実施例における同一経路における複数回のデータ符号化例の１回目のデータ符号化を示している。ここで、データ中継端末Ｎ１は、データ送信端末Ｓ１及びＳ２からそれぞれデータＤａ、Ｄｂを受信する。データＤａ、Ｄｂの各パケットの各々は、シーケンス番号を含み、さらに、データ受信端末ＩＤ及び次ホップ端末ＩＤからなる単位経路情報片を少なくとも１つ含む。データＤａ、Ｄｂは符号化がまだ１回も行われていないため、符号化の判定は、第１の実施例において説明した方法に従って行われる。第４の実施例では、第１の実施例と異なり、同一経路においてデータの符号化を複数回行うことを想定している。そのため、符号化後のデータパケットには、符号化されたデータのシーケンス番号と、データ受信端末ＩＤと、次ホップ端末ＩＤとが記述され、さらに、元のデータパケットのシーケンス番号と、データ受信端末ＩＤと、データ受信端末への経路の次ホップ端末ＩＤとが記述される。
【００９７】
図３１は、第４の実施例における同一経路における複数回のデータ符号化例の２回目のデータ符号化を示している。ここで、データ中継端末Ｎ４は、符号化されたデータ（Ｄａ ＸＯＲ Ｄｂ）及び（Ｄｂ ＸＯＲ Ｄｃ）を受信する。仮に符号化を行わないでそのままデータパケットを転送する場合、データ（Ｄａ ＸＯＲ Ｄｂ）はデータ受信端末Ｒ３に届き、データ（Ｄｂ ＸＯＲ Ｄｃ）はデータ受信端末Ｒ１に届く。一方、データの符号化を行った場合、符号化されたデータは（Ｄａ ＸＯＲ Ｄｃ）となる。
【００９８】
図２９を再び参照すると、符号化を行わない場合のデータ受信端末Ｒ３へのデータ（Ｄａ ＸＯＲ Ｄｂ）を基準として、符号化を行うことによって無くなる要素データＤｂと新たに追加される要素データＤｃとは、元のデータであるデータＤｂ及びＤｃを含むデータパケット（Ｄｂ ＸＯＲ Ｄｃ）が端末Ｎ４を経由しない別の経路Ｄを通ってデータ受信端末Ｒ３に届くことから、データ受信端末Ｒ３においてそれぞれデータＤｂ及びＤｃに復号可能である。
【００９９】
同様に、符号化を行わない場合のデータ受信端末Ｒ１へのデータ（Ｄｂ ＸＯＲ Ｄｃ）を基準として、符号化を行うことによって変化する元のデータであるデータＤｂ及びＤａを含むデータパケット（Ｄａ ＸＯＲ Ｄｂ）が端末Ｎ４を経由しない別の経路Ｃを通ってデータ受信端末Ｒ１に届くことから、データ受信端末Ｒ１においてそれぞれデータＤａ及びＤｂに復号可能である。
【０１００】
従って、たとえ符号化されたデータ（Ｄａ ＸＯＲ Ｄｃ）が経路Ａを通ってデータ受信端末Ｒ１に配送され且つ経路Ｂを通ってデータ受信端末Ｒ３に配送されたとしても、データＤａ及びＤｂ及びＤｃへの復号が可能である。よって、データ中継端末Ｎ１においてデータ（Ｄａ ＸＯＲ Ｄｂ）及びデータ（Ｄｂ ＸＯＲ Ｄｃ）の符号化が可能であることが分かる。
【０１０１】
以上の第４の実施例によれば、経路を流れるデータが複数回符号化されるため、１回だけ符号化されるよりもデータの総送信回数が削減される。
【０１０２】
＜第５の実施例＞
第５の実施例では、第２の実施例及び第３の実施例のそれぞれで述べた、多対多通信と１つのデータ受信端末までの経路が複数存在する多対一通信とを組み合わせて、あるデータ送信端末からデータ受信端末への経路が複数存在する多対多通信におけるデータ符号化の判定法について説明する。第５の実施例における端末構成は第２の実施例の構成と同じである（図１３参照）。
【０１０３】
図３２は、第５の実施例におけるあるデータ送信端末かあるデータ受信端末への経路が複数存在する多対多通信例を示している。本図に示すように、データ送信端末Ｒ１〜Ｒ３のそれぞれから、あるデータ受信端末Ｒ１またはＲ２へは複数の経路が存在する。また第３の実施例のように、あるデータ受信端末Ｒ１またはＲ２への複数の経路は符号化可能経路と非符号化経路とを含む。
【０１０４】
第１の実施例においては、符号化可能なパケットを判定するための抽出条件として、「抽出条件は、「データ中継端末の自端末ＩＤと一致する次ホップ端末ＩＤを含む単位経路情報片のデータ受信端末ＩＤに一致する少なくとも１つのＩＤが、全てのデータパケットの何れかの単位経路情報片のデータ受信端末ＩＤにあると共に、該データ受信端末ＩＤに一致するＩＤ毎に、当該ＩＤを含む単位経路情報の次ホップ端末ＩＤと自端末ＩＤとが一致するデータパケットが１つのみである」とする条件が設定されていた。
【０１０５】
これに対して第３の実施例においては、あるデータ送信端末からあるデータ受信端末への複数の経路が存在することから、「一致するデータパケットが１つのみ」である場合に限られず、「またはその一致するデータパケットが複数存在する場合にも、それらの一致するデータパケットにおいて、自分がデータ中継端末となる経路が符号化可能経路であって、かつ次ホップ端末ＩＤが自分の端末ＩＤ以外である端末ＩＤを含み、かつその自分の端末以外である端末がデータ中継端末となる経路が非符号化経路である」とする条件に拡張する。
【０１０６】
これは、第３の実施例においては、あるデータ送信端末からあるデータ受信端末への複数の経路が存在し、たとえ次ホップ端末ＩＤと自分の端末ＩＤとが一致するデータパケットが複数存在しても、符号化されない元のデータが別経路で対応するデータ受信端末に到達すること分かっているために、データの符号化が可能であると判断されるからである。
【０１０７】
図３３は、第５の実施例における多対多通信におけるパケット情報による符号化判定例を示している。データ中継端末Ｎ１がデータパケットａ及びｂを受信したとする。データパケットａ及びｂのそれぞれには、次ホップＩＤがデータ中継端末Ｎ１のＩＤである単位経路情報片としてデータ受信端末ＩＤをＲ１とする単位経路情報片と、次ホップ端末ＩＤが自分の端末ＩＤ以外である端末ＩＤを含む単位経路情報片としてデータ受信端末ＩＤをＲ２とする単位経路情報片との両方を含んでいる。すなわち、「次ホップ端末ＩＤと自分の端末ＩＤとが一致するデータパケットが複数存在している」とする条件に合致する。
【０１０８】
さらに、データパケットａに着目すると、データ受信端末Ｒ１の単位経路情報片において、次ホップ端末ＩＤをＮ１とする経路はデータ符号化可能フラグが１であり、他方のデータパケットｂには次ホップＩＤが自分以外の端末ＩＤ（ＮＤ及びＮＥ）の単位経路情報片を含み、かつ次ホップＩＤをＮＥとする経路の符号化可能フラグが０である。データパケットｂに着目しても同様である。以上の如く判定するのは、符号化されないデータＤａ、Ｄｂがデータ中継端末Ｎ１以外の経路を通ってデータ受信端末Ｒ１、Ｒ２にそれぞれ配送され、符号化されたデータ（Ｄａ ＸＯＲ Ｄｂ）が届いても復号可能であるという原理に基づいている。
【０１０９】
図３４は、図３３に示された符号化判定例を補足説明している。ここで、データＤａは、データ中継端末Ｎ１、ＮＡ、ＮＢを経由してデータ受信端末Ｒ１へ、データ中継端末ＮＣを中継してデータ受信端末Ｒ２へ配送される。一方、データＤｂは、データ中継端末Ｎ１、ＮＤ、ＮＥを経由してデータ受信端末Ｒ１へ、データ中継端末Ｎ１、ＮＦを中継してデータ受信端末Ｒ２へ配送される。データＤｂがデータ中継端末Ｎ１を経由してデータ受信端末Ｒ１、Ｒ２に配送される経路は1つの共通した経路になる。また、本図において、符号化経路フラグが１の場合は「符号化○」と表記され、０の場合は「符号化×」と表記されている。データ中継端末Ｎ１はデータＤａを含むデータパケットａ、データパケットｂを受信する。
【０１１０】
符号化可能であると判定するための条件の１つであるである「データパケットａの中の単位経路情報片の中で次ホップのデータ中継端末Ｎ１である単位経路情報片の符号化経路フラグが１で、データ受信端末はＲ１である。データパケットｂもデータ受信端末Ｒ１を含み、かつ次ホップＩＤにＮ１以外のデータ中継端末を含みその符号化経路フラグが０の単位経路情報片（データ中継端末ＮＥを含む単位経路情報片）が存在する」はデータＤｂが自分（Ｎ１）以外の経路（ＮＥを経由する経路）で符号化されずにＲ１に届くことを示している。
【０１１１】
符号化可能であると判定するためのもう１つの「データパケットｂの中の単位経路情報片の中で次ホップのデータ中継端末Ｎ１である単位経路情報片の符号化経路フラグが１でデータ受信端末はＲ１とＲ２である。データパケットａもデータ受信端末Ｒ１、Ｒ２を含み、かつ次ホップＩＤにＮ１以外のデータ中継端末を含みその符号化経路フラグが０の単位経路情報片（データ中継端末ＮＡを含む単位経路情報片とデータ中継端末ＮＣを含む単位経路情報）が存在する」はデータＤａが自分（Ｎ１）以外の経路（ＮＡを経由する経路とＮＣを経由する経路）で符号化されずにそれぞれＲ１、Ｒ２に届くことを示している。つまり、自分（Ｎ１）が各データ受信端末に対して中継すべきデータがＤａ、Ｄｂが符号化されずに別経路で届くことが分かるため、自分はデータを符号化することが可能となる。  以上の第５の実施例によれば、データ受信端末への経路が複数存在する多対多通信におけるデータ符号化の判定を行うことができる。
【０１１２】
尚、第５の実施例と第４の実施例とを組み合わせて利用することも可能である。つまり、データ送信端末が複数存在し、それぞれのデータ送信端末から少なくとも１つのデータ受信端末へ複数の経路を経由してデータを配送する際に、あるデータ送信端末からデータ受信端末への経路に複数回のデータ符号化を行う符号化対応（code-aware）ルーティングが可能である。
【符号の説明】
【０１１３】
２０１  経路制御部
２０２  データパケット保持部
２０３  データパケット処理部
２０４  無線通信部
２０５  経路情報テーブル
６０１  最小ホップ経路構築制御部
６０２  データ符号化判定部
６０３  経路再構築性制御部
Ｎ１〜Ｎ５  データ中継端末
Ｒ１〜Ｒ５  データ受信端末
Ｓ１〜Ｓ５  データ送信端末
Ｔ１〜Ｔ１０  無線通信端末（各種端末）
Ｔｃ    データ符号化端末
Ｔｘ    故障端末
Ｔｄ    データ符号化判定端末
Ｔｍ    マルチキャスト端末
【図１Ａ】
2010239196.tif 000003
【図１Ｂ】
2010239196.tif 000004
【図１Ｃ】
2010239196.tif 000005
【図２Ａ】
2010239196.tif 000006
【図２Ｂ】
2010239196.tif 000007
【図３】
2010239196.tif 000008
【図４】
2010239196.tif 000009
【図５】
2010239196.tif 000010
【図６】
2010239196.tif 000011
【図７】
2010239196.tif 000012
【図８】
2010239196.tif 000013
【図９】
2010239196.tif 000014
【図１０】
2010239196.tif 000015
【図１１】
2010239196.tif 000016
【図１２】
2010239196.tif 000017
【図１３】
2010239196.tif 000018
【図１４】
2010239196.tif 000019
【図１５】
2010239196.tif 000020
【図１６】
2010239196.tif 000021
【図１７】
2010239196.tif 000022
【図１８】
2010239196.tif 000023
【図１９】
2010239196.tif 000024
【図２０】
2010239196.tif 000025
【図２１】
2010239196.tif 000026
【図２２】
2010239196.tif 000027
【図２３】
2010239196.tif 000028
【図２４】
2010239196.tif 000029
【図２５】
2010239196.tif 000030
【図２６】
2010239196.tif 000031
【図２７】
2010239196.tif 000032
【図２８】
2010239196.tif 000033
【図２９】
2010239196.tif 000034
【図３０】
2010239196.tif 000035
【図３１】
2010239196.tif 000036
【図３２】
2010239196.tif 000037
【図３３】
2010239196.tif 000038
【図３４】
2010239196.tif 000039