(57)【特許請求の範囲】
【請求項１】
複数のノードを有するマルチホップネットワークにおいて、コンテンション方式の情報を転送する方法であって、
−  複数の送信ノード（２００）のうち少なくとも一つのノードが、データパケット信号を複数の中継候補ノード（１００）に送信するステップ、
−  少なくとも一つの中継候補ノード（１００）において、複数の送信ノードから送信される重畳信号を受信するステップ、
−  マルチユーザ検出を用いて、受信した重畳信号の複数のデータパケットを復号化するステップ、
−  正しく復号化されたパケット間の優先順位付けを行って、転送に適する少なくとも一つのデータパケットを選択するステップ、
−  前記少なくとも一つの選択されたパケットについてパケットアクノリッジメントで応答するステップ、
−  アクノリッジメントを受信した中継候補ノードの優先順位付けを行い、少なくとも一つの適切な中継ノードを選択するステップ、及び
−  前記少なくとも一つの選択された中継ノードに転送命令を送信し、情報を転送する役割を持たせるステップ、
を含む方法。
【請求項２】
前記パケット間の優先順位付けを行なうステップは、転送に適する複数のデータパケットを選択するステップを含み、複数のパケットアクノリッジメントが複数の対応する送信ノードに送信される、請求項１記載の方法。
【請求項３】
前記複数のパケットアクノリッジメントを単一のアクノリッジメントメッセージに集約する、請求項２記載の方法。
【請求項４】
更に、転送命令に応答して、対応する選択パケットの転送を行なうステップを含む、請求項１記載の方法。
【請求項５】
更に、転送命令に応答して、前記少なくとも一つの受信ノード（１００）が対応する転送命令アクノリッジメントで応答するステップを含む、請求項１記載の方法。
【請求項６】
更に、前記少なくとも一つの受信ノードが選択パケットの数を制限するステップを含む、請求項１記載の方法。
【請求項７】
前記パケット優先順位付けステップは、所定の目的関数の最適化に基づいて実行される、請求項１記載の方法。
【請求項８】
前記所定の目的関数は情報コストから見た進行度（ｉｎｆｏｒｍａｔｉｏｎ  ｃｏｓｔ  ｐｒｏｇｒｅｓｓ）を含む、請求項７記載の方法。
【請求項９】
前記パケット優先順位付けステップは、少なくとも一つのサービス品質（ＱｏＳ）要件に基づいて実行される、請求項１記載の方法。
【請求項１０】
前記転送は、コンテンション方式の多重アクセスプロトコルに基づいて行なわれる、請求項１記載の方法。
【請求項１１】
前記コンテンション方式の多重アクセスプロトコルはダイバーシチを適用した構成である、請求項１０記載の方法。
【請求項１２】
前記ダイバーシチを適用した構成のプロトコルは選択ダイバーシチフォワーディング（ＳＤＦ）プロトコルである、請求項１１記載の方法。
【請求項１３】
前記コンテンション方式の多重アクセスプロトコルはオポチュニスティックプロトコルである、請求項１０記載の方法。
【請求項１４】
前記中継候補ノード群の優先順位付けを行なうステップは、所定の目的関数の最適化に基づいて実行される、請求項１記載の方法。
【請求項１５】
前記複数の中継候補ノードの少なくとも一つは、この中継候補ノードが、他の中継候補ノードに隣接するノードであるという示唆に基づいてアドレス指定される、請求項１記載の方法。
【請求項１６】
更に、前に送信されたパケットのアクノリッジメントに応答して、各送信ノードが、送信ノードのデータバッファからアクノリッジされたパケットデータを取り除くステップを含む、請求項１記載の方法。
【請求項１７】
前記マルチホップネットワークはブロードキャスト／マルチキャストパケット無線ネットワークである、請求項１記載の方法。
【請求項１８】
複数のノードを有するマルチホップネットワークにおいて、コンテンション方式の情報を転送するシステムであって、複数の送信ノード（２００）のうち少なくとも一つのノードが、そのデータパケット信号を複数の中継候補ノードに送信し、当該システムが、
−  少なくとも一つの中継受信候補ノード（１００）において、複数の送信ノードから送信される重畳信号を受信する手段（１１０）、
−  マルチユーザ検出を用いて、受信された重畳信号の複数のデータパケットを復号化する手段（１２０）、
−  正しく復号化されたパケット間の優先順位付けを行って、転送に適する少なくとも一つのデータパケットを選択する手段（１４０）、
−  前記少なくとも一つの選択されたパケットについてパケットアクノリッジメントで応答する手段（１５０，１６０，１７０，１８０）、
−  アクノリッジメントを受信した中継候補ノードのうち少なくとも一つの、適切な中継ノードを選択するために優先順位を付ける手段（２７０）、及び
−  前記少なくとも一つの選択された中継ノードに転送命令を送信し、情報を転送する役割を持たせる手段（２７０，２２０，２３０，２４０）、
を備えるシステム。
【請求項１９】
前記パケット間の優先順位付け手段（１４０）は、転送に適する複数のデータパケットを選択するように動作し、前記応答する手段は、複数のパケットアクノリッジメントを複数の対応する送信ノードに送信するように動作する、請求項１８記載のシステム。
【請求項２０】
前記応答する手段は、複数のパケットアクノリッジメントを単一のアクノリッジメントメッセージに集約するように動作する、請求項１９記載のシステム。
【請求項２１】
更に、転送命令に応答して、対応する選択パケットの転送を行なう手段を備える、請求項１８記載のシステム。
【請求項２２】
更に、転送命令に応答して、対応する転送命令アクノリッジメントで応答する手段を備える、請求項１８記載のシステム。
【請求項２３】
更に、選択パケットの数を制限する手段を備える、請求項１８記載のシステム。
【請求項２４】
前記パケット優先順位付け手段（１４０）は、所定の目的関数の最適化に基づいてパケット優先順位付けを行なうように構成される、請求項１８記載のシステム。
【請求項２５】
前記所定の目的関数は情報コストから見た進行度を含む、請求項２４記載のシステム。
【請求項２６】
前記パケット優先順位付け手段（１４０）は、少なくとも一つのサービス品質（ＱｏＳ）要件に基づいてパケット優先順位付けを行なうように構成される、請求項１８記載のシステム。
【請求項２７】
前記中継候補ノード群の優先順位付けを行なう手段（２７０）は、所定の目的関数の最適化に基づいて候補ノードの優先順位付けを行なうように構成される、請求項１８記載のシステム。
【請求項２８】
前記少なくとも一つの送信ノードは更に、前記複数の中継候補ノードの少なくとも一つを、この中継候補ノードが、他の中継候補ノードに隣接するノードであるという示唆に基づいて、アドレス指定する手段を備える、請求項１８記載のシステム。
【請求項２９】
前記マルチホップネットワークはブロードキャスト／マルチキャストパケット無線ネットワークである、請求項１８記載のシステム。
【請求項３０】
パケット無線マルチホップネットワーク用の通信ノード（１００）であって、
−  複数の送信ノードから送信される重畳信号を受信する手段（１１０）、
−  マルチユーザ検出（ＭＵＤ）を用いて、受信された重畳信号の複数のデータパケットを復号化する手段（１２０）、
−  正しく復号化されたパケット群の優先順位付けを行って、転送に適する少なくとも一つのデータパケットを選択する手段（１４０）、
−  各選択パケットについてパケットアクノリッジメントで応答する手段（１５０，１６０，１７０，１８０）、及び
−  複数の中継受信候補ノードに、データパケットを送信した送信ノードのうち少なくとも一つからデータパケットを受信し、複数の中継候補ノードからアクノリッジメントに基づいて、適切な中継ノードを選択し、当該選択された中継ノードに転送命令を送信し、情報を転送する役割を持たせる手段、
を備える通信ノード。
【請求項３１】
前記パケット間の優先順位付け手段（１４０）は、転送に適する複数のデータパケットを選択するように動作し、前記応答する手段は、複数のパケットアクノリッジメントを複数の対応する送信ノードに送信するように動作する、請求項３０記載の通信ノード。
【請求項３２】
前記応答する手段は、複数のパケットアクノリッジメントを単一のアクノリッジメントメッセージに集約するように動作する、請求項３１記載の通信ノード。
【請求項３３】
更に、選択パケットの数を制限する手段を備える、請求項３０記載の通信ノード。
【請求項３４】
前記パケット優先順位付け手段（１４０）は、所定の目的関数の最適化に基づいてパケット優先順位付けを行なうように構成される、請求項３０記載の通信ノード。
【請求項３５】
前記所定の目的関数は情報コストから見た進行度を含む、請求項３４記載の通信ノード。
【請求項３６】
前記パケット優先順位付け手段（１４０）は、少なくとも一つのサービス品質（ＱｏＳ）要件に基づいてパケット優先順位付けを行なうように構成される、請求項３０記載の通信ノード。
【発明の詳細な説明】
【発明の開示】
【０００１】
技術分野
本発明は概して通信ネットワークに関し、具体的にはマルチホップネットワークに関する。
【０００２】
背景技術
無線媒体を効果的に複数ユーザの間で共有するプロトコルは通常、多重アクセスプロトコル、チャネルアクセス方式、又はメディアアクセス方式と呼ばれる。多重アクセスプロトコルは参考文献［１］に示されるように、２つの主要なカテゴリー、すなわち衝突回避プロトコル及びコンテンション方式プロトコルに分類することができる。
衝突回避プロトコルは、送信が常に無事に行われる、すなわち他の送信によって干渉されないことを保証するプロトコルである。衝突回避伝送は、チャネルを静的に、又は動的にユーザに割り当てることにより行なうことができる。これは、それぞれ固定スケジューリング及び動的スケジューリングと呼ばれることが多い。局間の調整を正確に行なうことによって、高い効率が実現すると考えられるが、大量の制御トラフィックの複雑な切り替えを伴う場合がある。
コンテンション方式プロトコルは、原理的に、送信が無事に行なわれることが保証されない点で衝突回避プロトコルとは異なる。従って、このプロトコルは、衝突が生じた場合にこれらの衝突を解消して全てのメッセージが最終的に無事に送信されるようにする手順を規定する必要がある。
【０００３】
多重アクセスプロトコルはまた、これらのプロトコルを設計する目的となるシナリオ又はアプリケーションに基づいて分類することができる。プロトコルには、例えばセルラーシステムの基地局のような単一局との接続に適しているものと、分散環境下で動作するように設計されているものがある。分散環境で動作するプロトコルにとって重要なのは、プロトコルが主としてシングルホップ用に設計されているかどうか、すなわち通信可能領域内の指定隣接体のみとの通信のために設計されているかどうか、又は特にマルチホップシナリオ用に設計されているかどうかである。
マルチホップシナリオにおいては、情報は、シングルホップ内で直接ではなく、送信元と宛先との間の複数のホップを通して送信することができる。一般的に、マルチホップ方式は、直接ワンホップ方式に比べて小さい消費電力及び高い情報スループットなどの複数の利点を持つ。マルチホップネットワークでは、互いに通信ができない距離に位置するノードが、送信元からのメッセージを宛先に転送する中間に位置するノードを利用することができるという利点がある。マルチホップネットワークは、ノード群のほとんどが移動性を有し、中央調整インフラストラクチャが無い、いわゆるアドホックネットワークと定義することができるが、マルチホップネットワークの考えは、ノード群が固定される場合に適用することもできる。
【０００４】
下位の最短パスルーティングプロトコルに基づく先行技術によるルーティング方法（例えばＢｅｌｌｍａｎ−Ｆｏｒｄルーティング）では、明確に定義された送信元から宛先に至るマルチホップルートは、システムを通して渡されるルーティングコスト情報に基づいて決定される。簡易化した各ノード又は局はその送出リンクのコストを認識し、この情報を隣接ノード群の各々に同報通信する。このようなリンクコスト情報は通常、各ノードの自前のデータベースに保持され、且つデータベースの情報に基づいており、ルーティングテーブルが適切なルーティングアルゴリズムを使用して計算される。一般的に、最短パスルーティング方法及び同様のルーティング方法によって、送信元−宛先の各組に単一ルートが生じる。最も効率的であるという訳ではないが、非常に簡単な最短パスルーティング方法では、例えば良く知られたＡＬＯＨＡコンテンション方式の多重アクセスプロトコルを使用することができる。
転送プロセスにおいて、ある程度能動的なルーティング選択を用いて複数ノードを利用するというコンセプトに基づく既存のプロトコル（このプロトコルは下位の最短パスプロトコルを使用することができる）が存在する。例えば、ＥＩＧＲＰ（Ｅｎｈａｎｃｅｄ  Ｉｎｔｅｒｉｏｒ  Ｇａｔｅｗａｙ  Ｒｏｕｔｉｎｇ  Ｐｒｏｔｏｃｏｌ：参考文献［２］）と呼ばれるプロトコルはルーティングプロトコルであり、複数のルータの１つに対するランダムフォワーディングを可能にする固定ネットワークに主として使用される。Ｓｙｌｖｅｓｔｅｒ及びＫｌｅｉｎｒｏｃｋによるランダムフォワードルーティング（参考文献［３］）はＥＩＧＲＰ、すなわち複数のパケット無線ネットワークルータの１つに対するパケットのランダムフォワーディングに類似するが、このランダムフォワードルーティングには重要な補正が含まれており、パケットが常にほぼ正しい方向に確実に向かう。ＤＡＲＰＡ（Ｄｅｆｅｎｓｅ  Ａｄｖａｎｃｅ  Ｒｅｓｅａｒｃｈ  Ｐｒｏｊｅｃｔ  Ａｇｅｎｃｙ）による別のパスルーティング（参考文献［４］）は、リンクを介して再送信されるパケットを複製すると同時に複数のノードに同報通信することを可能にしており、これらのノードからパケットは再度最短パスルーティング方法に従って進む。１次Ｎ／Ｍフォワーディング（参考文献［５］）は、１のノードが１のノードに向かって最大Ｎ回のパケット送信を試み、送信に失敗すると、次のノードに対して最大Ｎ回の送信を試みる、という考え方に基づく。この手順は、パケット欠落が生じる前に最大Ｍ個のノードに対して繰り返される。代替パスルーティング及び１次Ｎ／Ｍフォワーディングの利点は、これらの方法を、例えばフェージング又は干渉変動に起因する輻輳及び一時的悪化通信を含む局所的な通信状態に適合させることができることである。
【０００５】
システム内の経時的な変化又は変動によって、信号送信の確実性を他の時間及び状態におけるよりも高くすることができるオポチュニティのウィンドウ又はピークが生成される。普通の最短パス技術及び先行技術による関連ルーティング方法は、相対情報が各ノード又は局には保存されないため、これらオポチュニティのウィンドウを認識する機能を持たない。対照的に、オポチューンルーティング（参考文献［６，７］）は、システム変化及び変動によって提供されるオポチュニティをある程度利用する。特に無線ルーティングに関連して、リンク品質が経時的に急激に変化する（例えば、レイリーフェージングによって）とシステム性能全体が低下する。しかしながら、オポチューンルーティングは、これらの変動によって提供されるオポチュニティのウィンドウを利用することによってこの性能低下を部分的に緩和する。オポチューンルーティングの場合、送信元−宛先の各組に単一のルートは存在しない。すなわちオポチューンルーティングはＥＩＧＲＰランダムフォワードに類似し、或る程度、代替パスルーティング及び１次Ｎ／Ｍフォワーディングにも類似する。但し、データパケットは、送信元から宛先に導かれながらも、いくらかランダムなルートに沿って進む。その結果、最短パス方法を使用する場合、連続パケットは通常同じルートに沿って送信されるが、一方、オポチューンルーティングを使用する場合は、連続パケットは同じ方向であるが異なるパスに沿ってルーティングすることができる。
しかしながら、参考文献［６，７］の全体モニタリングは遅いプロセスである。モニタリングは、迂回メッセージを受信することによって、又は時々いわゆるプローブを送出することによって行われる。プローブが送出されると、例えばパス損失に関する情報を含む応答が返信されると予測される。プローブとデータ送信との間に遅延がある場合、フォワーディングアルゴリズムに関する返信入力情報は、データが送信される時にはもう古くなっている可能性がある。特に望ましくない結果は、既存のオポチューンルーティングと、それに加えて普通の最短パスルーティング方法が、使用可能なダイバーシチ効果を効率的に利用しないということである。
【０００６】
選択ダイバーシチフォワーディング（ＳＤＦ：参考文献［８］）は、ダイバーシチ効果をほぼ最適な形で効率的に利用する技術である。この新規のアプローチは、送信元の局からの送信を、近傍の受信機グループ又は局グループに振り向ける操作に基づく。受信ノード群の一つ以上の局が応答すると、中継局群の一つが選択され、命令メッセージが選択局に送信されて、この中継ノードに指示してデータメッセージを転送する責任を負わせる。情報が宛先に到達するまで、このプロセスを全ての後続の責任局に繰り返す。このアプローチに従うことによって、ブランチダイバーシチ及びキャプチャ効果の両方をデータ転送プロセスに利用することができる。特に、ブランチダイバーシチによって、インターリーブデータを符号化と一緒に使用してフェージングチャネルを克服する必要性が小さくなり、これによって今度は、遅延が小さくなり、その結果更に高いスループットが実現する。キャプチャ効果とは、同じ周波数の、又はほぼ同じ周波数の２つの信号の強い方の信号のみが変調され、弱い方の信号が抑制され、雑音として拒絶される現象を指す。複数の受信局に関連して、キャプチャ効果は、データ送信が衝突するときに非常に大きな堅牢性を実現する。ＳＤＦは、時間の掛かる下位のコストプロトコルを利用するが、ＳＤＦによって高速のチャネル変動自体に対する瞬時の適合が可能になる。
変動を利用する考えであって、シングルホップ方式の普通のセルラーネットワークに関する類似の考えは、参考文献［９，１０，及び１１］に見ることができ、これらの参考文献はそれぞれ、高速ダウンリンクパケットアクセス（ＨＳＤＰＡ）、高データレート（ＨＤＲ）、及びオポチュニスティックビームフォーミング（ＯＢ）について記載している。ＨＳＤＰＡ及びＨＤＲは互いに非常に類似する。しかしながら、オポチュニスティックビームフォーミングは、機能の点で異なり、ＯＢがアンテナビームを異なる方向にランダムに振り向けるか、又は連続的に掃引するのに対し、ＨＳＤＰＡ及びＨＤＲはビームフォーミングという概念は持たない。特に、オポチュニスティックビームフォーミング（参考文献［１１］）では、オポチュニスティックアイデアを利用し、次にビームフォーミングに関してオポチュニスティックアプローチを利用して、セルラーシステム又は基地局におけるシステム容量を大きくする。しかしながら、このようなＨＳＤＰＡ、ＨＤＲ、及びＯＢのコンセプトはマルチホッピングには関連していない。ＯＢは基本的に、高速のチャネル変動を考慮に入れた基地局における高速スケジューリングの拡張版であり、ＣＤＭＡ２０００ＨＤＲ及びＷＣＤＭＡ  ＨＳＤＰＡの両方に提案されている。
【０００７】
発明の概要
本発明は先行技術による構成の上記欠点及び他の欠点を解決する。
本発明の主たる目的は、マルチホップネットワークにおいて情報を転送するための効率的なメカニズムを提供することにある。
【０００８】
本発明の別の目的は、受信エネルギーをパケット無線ネットワークにおいて更に最適な方法で利用するマルチホップルーティング方法を提供することにある。
本発明の更に別の目的は、マルチホップネットワークの性能をスループット、遅延特性及び／又は消費電力に関して改善することにある。
【０００９】
本発明の目的はまた、ネットワークにおけるサービス品質（ＱｏＳ）を向上させることにある。
本発明の目的はまた、輻輳及びバッファ溢れのリスクを減らすことにある。
【００１０】
本発明の特定の目的は、マルチホップネットワークにおいて効率的に情報を転送する方法及びシステムを提供することにある。
また、パケット無線マルチホップネットワークにおける情報の効率的な転送をサポートする通信ノードを実現することにある。
【００１１】
これらの目的及び他の目的は、特許請求の範囲に定義される本発明によって達成することができる。
【００１２】
本発明者の理解では、オポチューンルーティング及び選択ダイバーシチフォワーディングはそれぞれ、従来のルーティングに比べると非常に大きな改善をもたらすが、これら最先端のマルチホップ／ルーティング方法はいずれも、受信エネルギーを完全に最適な方法で利用することがなく、これは、スループット及び遅延特性、並びに消費電力に関して改善の余地があることを意味している。
本発明は、パケット無線マルチホップネットワークのようなマルチホップネットワークの受信側で最大限の効果を発揮するようにコンテンション方式の転送とマルチユーザ検出（ＭＵＤ）とを組み合わせ、ＭＵＤの設計上の選択を効率的に組み込んで利用する。
【００１３】
基本的な考え方は、ＭＵＤを受信側で用いて、複数のノードから最初に送信される複数のパケットを同時に復号化し、正しく復号化されたパケット群の優先順位付けを行って転送に適する一つ以上のパケットを選択し、更に最終的に、各選択パケットのパケットアクノリッジメントで応答する、というものである。このように、ＭＵＤの設計上の選択を転送手順において利用する。
通常、受信側は、所定の優先順位付け基準に基づいてＭＵＤによる復号化パケット群の優先順位付けを行なう。通常、何らかの面で最適であるパケットを選択することが望ましい。明確な定義付けを行なった上で最適性を考えるために、目的関数を導入することが好ましい。この関数は、多くの性能目標のいずれかを反映することができる。この点に関して、情報コストから見た進行度が特に有用な目的関数であることが認識されている。情報コストから見た進行度、及び特に情報転送進行度を考慮しながら、自然優先順位付け基準では、最大転送進行度を有するパケット群を選択する。通常、大きい転送進行度を有するパケット群は、受信され、正しく復号化されていると同時に、低い受信電力レベルを有するパケット群（例えば、遠い送信ノード群から送信される）である。大きい転送進行度は多くの場合、パケットがネットワークにおいて相対的に短い時間を費やし、従って遅延が小さくなり、スループットが高くなり、短時間でネットワークから離れて消えてしまうことにより、他のトラフィックに無線リソースを提供することを意味する。
【００１４】
好適には、複数のデータパケットが転送のために選択され、従って複数のパケットアクノリッジメントが複数の対応する送信ノードに送信される。この場合、複数のパケットアクノリッジメントは、送信ノード群にブロードキャスト又はマルチキャストされる単一のアクノリッジメントメッセージに集約させると便利である。
堅牢性を強化するために、各送信ノードは、自動転送ではなく、代わりにパケットアクノリッジメントに応答して受信ノードに転送命令を送信することができ、次いで、受信ノードが、任意で、対応する転送命令アクノリッジメントで応答することができる。前に送信したパケットに関連するアクノリッジメントを受信する送信ノードは、必要に応じてパケットをこのノードの送信キューから取り除くことができる。
【００１５】
ＭＵＤとの統合に適したコンテンション方式のマルチホッププロトコルの例は、標準の最短パスベースの転送プロトコル、並びにダイバーシチを適用したプロトコル及びオポチュニスティックフォワーディングプロトコルを含む。これの良い例は、ｉ）最短パスベースの転送、及びｉｉ）選択ダイバーシチフォワーディングそれぞれと連動させた従来のＡＬＯＨＡである。ＭＵＤと統合させることができる他の転送方式は、オポチューンルーティング、ランダムフォワードルーティング、１次Ｎ／Ｍフォワーディング、及び代替パスルーティング、並びに、場合によっては後述するようなＳＴＤＭＡ（空間時分割多元接続）のような多重アクセスプロトコルを含む。
ダイバーシチフォワーディングをマルチユーザ検出と統合し、複数の隣接中継局／ユーザが存在することにより可能になるダイバーシチを併せて利用すると特に便利である。データパケット信号を複数の中継候補ノードに送信し、次に中継候補ノード群の少なくとも２つからアクノリッジメントを受信する送信ノードは、優先順位付け手順を実行して一組のアクノリッジメント送出中継ノードから適切な中継ノードを選択することが好ましい。次に送信ノードは、通常、選択された中継ノードに転送命令を送信し、候補ノードに指示して次のノードに情報を転送する役割を持たせる。
【００１６】
本発明は次の利点を提供する。
・マルチホップ転送が効率的に行なわれる。
・ネットワーク性能が向上する。
・パケット無線ネットワークにおいて受信エネルギーを効率的に利用できる。
・スループット及び遅延特性が改善される。
・ＱｏＳサポートが向上する。
・輻輳及びバッファ溢れのリスクが低減する。
・コストから見た進行度及び転送進行度が増大する。
本発明が提供する他の利点は、本発明の実施形態についての以下の記述を一読することにより明らかになる。
本発明、及び本発明の更なる目的及び利点は、添付図面と一緒に次の記述を参照することによって最も深く理解できる。
【実施例】
【００１７】
図面全体を通じて、同じ参照記号は対応する構成要素、又は同様の構成要素に使用される。
ＭＵＤを衝突回避多重アクセスプロトコルに取り入れようとする試みが行なわれてきた。例えば、参考文献［１２，１３］は、ユーザがＭＵＤを用いる場合の、マルチホップパケット無線ネットワークにおけるスケジューリングされた多重アクセス（空間時分割多元接続：ＳＴＤＭＡ）に言及している。しかしながら、このようなＳＴＤＭＡにおいて最短スケジュールを決定するタスクは現実には処理が困難であり、且つＮＰ−ｃｏｍｐｌｅｔｅである（実行時間が多項式時間では計算できない、すなわち通常は入力の大きさに指数関数的である）ことが知られており、従ってヒューリスティック（発見的）解法で妥協するしかない。しかしながら、場合によってはヒューリスティック解法も非常に複雑になり易い。ＭＵＤを用いるＳＴＤＭＡでは、送信電力（及びレート）及び送信／受信インスタンスを連携させると、自由度が追加されるので一段と複雑さが増す。また、無線チャネルは、例えばフェージングに起因して予測不能な変化をするので、正しい受信電力レベルを制御且つ維持し、ＭＵＤを用いるスケジュールが正しく動作することを保証するのが難しい。固定スケジュールの場合、フェージングピーク又は突然現われる中継ノード群によって、スケジュールが古くなってしまい、時としてパケット衝突を起こし、性能が全体的に低下する。参考文献［１２］は、ＳＴＤＭＡに関してしばしば想定されるように、場合によってはトラフィックパターンが変化しない静的状態においても用いられる集中管理スケジュール（ｃｅｎｔｒａｌｉｚｅｄ  ｓｃｈｅｄｕｌｅ）に焦点を当てている。
【００１８】
参考文献［１４］に開示される方式は、マルチホップネットワーク構成におけるＭＡＣ（メディアアクセス制御）レイヤに対応せず、（分散）シングルホップネットワークにＭＵＤを用いるＣＤＭＡ（符号分割多重接続）のみに対応している。
本発明は先行技術による構成に見られるこれらの不具合及び他の不具合を解決する。
【００１９】
本発明者が行なった本質的な発見は、優先順位付け手順をメッセージ交換方式と組み合わせることにより、マルチユーザ検出（ＭＵＤ）をコンテンション方式の転送のフレームワークに効率的に組み込むことができるということである。
パケット無線マルチホップネットワークのようなマルチホップネットワークにおける各情報転送ノードは、通常、受信機能及び送信機能の両方を備え、これらの機能は必要に応じて、且つ必要時に起動することができる。しかしながら、説明を簡単にするために、送信機能に焦点を当てる場合は一般に送信側について述べ、ノードを単に送信ノードと呼び、受信機能に焦点を当てる場合は一般に受信側について述べ、ノードを単に受信ノードと呼ぶ。
【００２０】
最短パスルーティングを用いる一般的なコンテンション方式の多重アクセス方式に関する概念レベルで、第１の好適な実施形態による例示的な方式について以下に記載する。
一又は複数の宛先に向かうそれぞれのルートに沿って進む多くのデータパケットが、特定の受信ノードにたまたま同じ時間に到着することが起き得る。従来は、このような状況は受信ノードでの衝突として処理され、その場合この受信ノードは、普通最大強度の受信信号（復号化可能の場合）のみを転送する。しかしながら本発明によれば、同時に到着する複数の信号を受信するノードは、ＭＵＤ復号化を行ない、複数の送信ノードから送信されて正しく復号化されたパケット群の優先順位付けを行ない、一つ以上の優先順位付けしたパケットの（一又は複数の）アクノリッジメントを対応する送信ノードに送信し、次に優先順位付けしたパケット（群）をこれらのパケットの（一又は複数の）宛先に向かうそれぞれのパスに沿って引き続き転送する（ノードが宛先でない限り）役割を担う。
【００２１】
図１の模式的なプロセスフローを参照する。
ｔ１において、一連の送信局又は送信ノードＴ１，Ｔ２，Ｔ３は、一つ以上の宛先に向かうそれぞれのパス上に位置する特定の指定受信ノードＲに送信されるデータパケットＤ１，Ｄ２，Ｄ３を有する。
ｔ２において、受信モードの全ての局又はノードが無線媒体へのアクセスを行ない、重畳した（受信する可能性のある）複数の送信信号を受信する。詳細には、ノードＲは重畳信号を送信ノードＴ１，Ｔ２，Ｔ３から受信する。
ｔ３において、受信ノードはＭＵＤを使用して複数のパケットＤ１，Ｄ２及びＤ３を無事に復号化する。
続いて、ｔ４において、正しく復号化したパケット群に対する優先順位付けを行って、転送するのが最も望ましいパケットの組であるＤ１及びＤ３を決定する。転送することを承認することができるパケットの数は、例えば利用可能なバッファ空間が小さいことに起因して、少ない場合もある。
続いて、ｔ５において、衝突が生じない、又は衝突がほとんど生じないフィードバックアクノリッジメントを受信ノードＲから対応する送信ノードＴ１及びＴ３に送信し、受け入れられ（すなわち、受信され、復号化され、一時保存され）、次いで転送されるパケット群を通知する。好適には、これらのアクノリッジメントは単一のアクノリッジメントメッセージＡＣＫに集約し、このメッセージを送信ノード群にマルチキャスト又はブロードキャストする。アクノリッジメント（送信側自体に向けられた）を受信する送信側は全て、任意で、送信データパケットをその送信バッファから除去することができる。受信ノードがＮＡＣＫ（ネガティブアクノリッジメント）で応答することにより、対応する送信ノードに対し、送信パケットが受け入れられなかったことを通知することもできる。
【００２２】
プロセスは、送信元ノードにより生成且つ送信される各データパケットに対して実行され、情報が所望の宛先に到着するまで繰り返される。ここで、受信ノードから転送されることがない復号化されたパケット群は廃棄することができ、新規パケットが到着して所定の最適化基準を全て満たす場合には、必要に応じて、送信バッファをスケジューリングし直すことができることに留意されたい。
提案するＭＵＤ統合多重アクセスプロトコルの核心部分は、受信側が、優先順位付け手順において同時に復号化される複数のパケットの中から選択を行って、新形式のダイバーシチの利用を可能にする機能である。パケットの優先順位付けは、所与の目標性能関数の最適化に基づくことが好ましい。このようにして、受信ノードは、同時に復号化された複数のパケットの中から選択を行って、性能の観点から何らかの面で最高の生産性をもたらす一つ以上のパケットの組を見つけることができる。例えば異なるパケットは異なるＱｏＳ要件を有する可能性があるので、優先順位付けプロセスにおいてＱｏＳ（サービス品質）要素を考慮することも可能である。一例として、厳しい遅延要件を有するパケットの優先度を、それよりも緩い遅延要件を有するパケットより高くすることができる。
【００２３】
図２は、受信ノードから異なる距離に位置する２つの送信ノードから信号の送信を行なう一実施例を示す模式図である。受信ノードＲは２つの送信ノードＴ１及びＴ２から信号を受信する。送信ノードＴ１からの信号情報は、送信ノードＴ２からの情報よりも長い距離を送信され、両方の信号はノイズフロアを超える受信電力レベルで受信されるので、これらの信号は両方とも、通常、ＭＵＤを受信ノードＲで使用することにより正しく復号化することができることが分かる。一般的に、使用レートと受信電力との組合せによって、パケットを復号化することができるかどうか、及びどのパケットを復号化することができるかが決まる。送信ノードＴ１からの信号情報の受信電力レベルＰＲＸ１は低いが、ノードＴ１からの信号情報を選択して転送する操作は、いずれにしろ性能面で大きな利点をもたらす。情報転送進行度を考慮する場合、大きい情報転送進行度を有するパケット群は通常、受信され、正しく復号化され、同時に低い受信電力レベルを有する（これは普通、パケット群が遠い送信ノードから送信されることを示す）パケット群である。情報転送進行度が大きいということは、多くの場合、パケットがネットワークにおいて相対的に短い時間を費やしており、従って遅延が小さく、スループットが高く、短時間でネットワークから離れて消えてしまうことにより、無線リソースを他のトラフィックに提供することを意味する。
図１の例では、選択されたパケット群は、これらのパケットの宛先に向かう方向に、受信ノードから自動的にネットワーク内を更に転送される。しかしながら、堅牢性を強化するために、各送信ノードは、別の方法として、パケットアクノリッジメントに応答して受信ノードに転送命令を送信することができ、次に任意で受信ノードが対応する転送命令アクノリッジメントで応答することができる。このような拡張メッセージ交換方式を図３に示す。
【００２４】
図３は、本発明の第２の好適な実施形態による複数の送信ノード及び一つの受信ノードに関する動作及び信号伝達の様子を示す模式的なプロセスフロー図である。時間ｔ１〜ｔ５における動作及び信号伝達は図１に関して記載したものと同じである。しかしながらｔ６において、それぞれのパケットアクノリッジメントを受信した送信ノードＴ１及びＴ３の各ノードは、受信ノードＲに対して転送命令ＦＯで応答する。ｔ７において、受信ノードＲは、関連する送信ノードＴ１及びＴ３に向けて対応する転送命令アクノリッジメントで応答する。転送命令アクノリッジメントは、送信ノード群にマルチキャスト又はブロードキャストされる単一のアクノリッジメントメッセージに集約することが好ましい。ノード内の送信キューに格納されるパケットに関連するアクノリッジメントを受信する送信ノードは、必要に応じてキューからパケットを取り除くことができる。次いで、ｉ）新規のデータパケット群が送信される場合、及びｉｉ）情報が所望の宛先に達するまで、全プロセスが繰り返される。
解析及びシミュレーションによって、ダイバーシチフォワーディングをマルチユーザ検出と統合して、複数の隣接中継局／ユーザが存在することにより可能になるダイバーシチも利用すると大きな利点が生じることが判明した。
【００２５】
簡単に言うと、ＳＤＦのような、ダイバーシチに基づくプロトコルに関する例示的なメッセージ交換方式は次のように動作する。送信すべきパケットを有する全ての送信側は、一連の候補ノードを決定し、マルチキャストか、又は場合によってはブロードキャストを使用して保留中のパケットを送信することができる。候補ノード群は通常、目標コストメトリックの観点又は単なる地理的位置の観点から宛先に近いノード群である。コスト情報は、最短パスプロトコルのような、従来の、又は将来のあらゆる下位ルート決定プロトコル、又はダイバーシチフォワーディングに更にカスタマイズされたルート決定プロトコルから得ることができる。ダイバーシチフォワーディングを下位の最短ルート決定プロトコルと一緒に使用するということは、実際に選択する転送パスが、最短パスプロトコルが提案する最短パスから外れる可能性があることを意味する。コスト情報はむしろ、候補ノード群の選択及びパケット優先順位付けの基礎として使用される。データパケットのレートも、例えば候補中継ノード群までの平均パス損失及び予測干渉アクティビティなどに基づいて選択することができる。送信電力は同様にして同じ方法により選択することができる。一般的に、レート及び送信電力は、ＭＵＤを用いるという認識に基づいて決定することができる。受信モードの全ての局は、無線媒体へのアクセスを行ない、重畳した（受信する可能性のある）複数の送信信号を受信する。受信側はＭＵＤを使用してデータを復号化する。一つ又は複数のパケットは無事に復号化することができ、正しく復号化されたパケットに対して後続の優先順位付けを実行して転送に最も望ましいと考えられる一組のパケットを決定する。更に、受け入れることができるパケットの数は、（例えばバッファ空間に起因して）少ない場合もある。続いて、衝突を生じないか、又は衝突をほとんど生じないフィードバック（アクノリッジメント）パケット群を受信ノードから送信し、受け入れられ（すなわち、受信され、復号化され、一時保存され）、次いで転送されるパケット群を通知する。アクノリッジメント（それ自体に向けられた）を受信する全ての送信側は、アクノリッジメントの優先順位付けを行ない、送信側の送信パケットを更に中継する役割を担う必要のある好適なノードを決定することが好ましい。続いて、選択された好適なノードは、衝突を生じないか、又は衝突をほとんど生じないチャネルを通して転送命令を通知され、次にこの好適なノードは転送を実行し、任意で、転送命令アクノリッジメントで応答することができる。このプロセスは、情報が宛先に到達するまで繰り返される。ここで、転送されない復号化されたパケット群は廃棄することができ、且つ新規のパケットが到着して全ての所定の最適化基準を満たす場合、送信バッファに対して順序入れ替え／スケジューリングし直しを行なうことができることに留意されたい。
特に有利な実施形態は、ダイバーシチを適用したコンテンション方式プロトコルに複数の隣接中継局／ユーザの存在を利用する場合に実現することが判明している。一例として、局又はノードから送信されるパケットは、その宛先に向かう途中で単一のルーティングパスに限定されてはならず、むしろ、通信条件に応じて、且つ局所的送信適応により、良好な品質のリンクを有する一つ以上の隣接中継局又は中継ノードをルーティングプロセスに利用することができる。所望のダイバーシチの利点及び堅牢性からもたらされ、且つこれらの利点及び堅牢性を実現する通信条件には、とりわけ、無線チャネルの固有のブロードキャスト特性、フェージングに起因する変動パス損失、フェージングに起因する変動干渉レベル、送信の有／無によって変わる変動干渉のような伝搬条件が含まれる。伝搬条件に加えて、通常は、他の要素も、複数の局／ノード／ユーザがマルチホップパケット無線ネットワークにおいて使用される、ダイバーシチを適用したコンテンション方式プロトコルに関連して含まれる場合の局所的適応において考慮される。
【００２６】
次に、基本的な考え方について、図４を参照しながら更に詳細に例示する。この考え方は、選択ダイバーシチフォワーディング（ＳＤＦ）の特定のフレームワークの内部で示される。しかしながら、本発明は、通常、オポチューンルーティングプロトコル、選択ダイバーシチフォワーディング（ＳＤＦ）プロトコル、又はダイバーシチを適用した他の全てのコンテンション方式プロトコル等のあらゆるコンテンション方式プロトコルに適用することができ、更にはランダムフォワードルーティング、１次Ｎ／Ｍフォワーディング、及び代替パスルーティングだけでなく、最短パスルーティングを備えるＡＬＯＨＡのようなプロトコルにも適用可能である。
次の実施例では、システムは通常、制御情報パケットが少なく、且つデータパケットよりも有意に少ないリソース及び小さいエネルギーしか消費しないように構成されると仮定する。
【００２７】
図４は、マルチユーザ検出と、パケット及び候補ノードの優先順位付けとを取り入れたＳＤＦベースのメッセージ交換方式の一実施例を示しており、この例では、時間ｔ１において、２つのノードＴ１及びＴ２はそれぞれ送信すべきパケットを有する。この段階では、候補ノードＴ１：Ｒ１，Ｒ２，Ｒ３及びＴ２：Ｒ２，Ｒ３を、これらのノードがデータパケットを所望の宛先に向けて転送すると予測されることを示す情報に基づいて選択する。下位のコスト決定プロトコル（例えば、最短パスプロトコル）はこのような情報を提供することができるので、安定的な「コストから見た進行度（ｃｏｓｔ  ｐｒｏｇｒｅｓｓ）」が存在することが保証される。
ｔ２において、パケット群が、マルチキャスト法又はブロードキャスト法を使用して送信ノード群から候補ノード群に送信される。好適には、候補ノードの数が少なく、よって普通マルチキャストを使用して情報を正しい「概略方向（ｇｅｎｅｒａｌ  ｄｉｒｅｃｔｉｏｎ）」に送信する。
ｔ３において、マルチユーザ検出を使用してパケット群を復号化する。この特定の実施例では、候補ノードＲ１はいずれのパケットも復号化することができないが、候補ノードＲ２及びＲ３はパケットＤ１及びＤ２を同時に復号化する。
ｔ４では、各中継候補ノードにおいて復号化されたパケット群に対する優先順位付けが行なわれる。優先順位付けを行なう目的は、スループットの最適化、サービス品質（ＱｏＳ）特性の向上、バッテリ管理、輻輳制御、及び受信バッファ溢れの回避（フロー制御）に関連している。何らかの面において最適なパケット群を選択するのが望ましい。明確な定義付けを行なった上で最適性について考えるために、復号化されたパケット群に関して目的関数を導入し、最適化することが好ましい。目的関数は、多数の性能目標の内のいずれかを表わすことができる。優先順位付けは、送信ノードから受信ノードまでのコストから見た進行度、遅延情報、優先順位付けパラメータ、又はパケット優先順位付けのその他関連情報全てに基づく。コストから見た進行度に基づく優先順位付けには、普通、データパケット群と一緒に送信されるコスト情報、又は送信ＩＤを全てのデータパケットに格納することにより下位のコスト決定プロトコルによって生成されるコスト情報が必要とされる。特に、スループットの観点から、コストから見た進行度が大きいパケット群を優先することが望ましい。
【００２８】
有用な目的関数の特定の例は、次式により与えられる情報コストから見た進行度を表わす関数である。
Ｚｉｊ（Ｄ）＝ｆ（Ｃｏｓｔｉ（Ｄ），Ｃｏｓｔｊ（Ｄ），．．．）
上式において、
Ｚｉｊ（Ｄ）は、宛先Ｄに向かうパケットの情報コストから見た進行度であり、ｉは送信ノードであり、ｊは受信ノードである。更に、Ｃｏｓｔｉ（Ｄ）及びＣｏｓｔｊ（Ｄ）は、宛先Ｄに向かうパケットから見た場合のコストである。次に、情報コストから見た進行度を表わす関数を全ての復号化済みパケットに渡って最適化し、コストから見た進行度が最も大きい一又は複数のパケットを選択する。コスト及び／又は目的関数ｆは、多数の要素の内のいずれかを表わすことができる。例えば、コスト及び目的関数は、転送進行度を地理的距離で表わすことができるが、コストから見た進行度を表わす他の指標を使用することもできる。地理的距離で表わされる転送進行度は、例えばＧＰＳ（全地球測位システム）情報のような位置特定情報か、又はパス損失計算値（ｐａｔｈ  ｌｏｓｓ  ｃａｌｃｕｌａｔｉｏｎｓ）に基づいて推定することができる。
パケット群は通常、それぞれのフローに属するので、情報コストから見た進行度を表わす上述の関数の別の公式化を使用し、宛先ではなくフローに関する最適化を実行することができる。このようにして、異なるフローに関するＱｏＳ要件を、自然な方法で最適化に取り入れることができる。
【００２９】
優先順位付けプロセスでは、低い優先度のパケット群を必要に応じて適宜廃棄することができる。使用する見込みがないパケットは全て即時廃棄するか、又は後の段階において随意で廃棄することができる。この実施例では、候補ノードＲ２はパケットＤ１及びＤ２を選択するが、候補ノードＲ３はパケットＤ２しか選択しない（例えばバッファ溢れの理由により）。
全体として、ｔ４におけるステップ及び選択肢は、シングルユーザＳＤＦと比較して、新規の、且つ大きな利点をもたらす。
【００３０】
ｔ５において、データアクノリッジメントが送信される。アクノリッジメントは、例えば効率的なスケジュールによってオーバーヘッドを確実に小さくしながら、衝突のリスクが最小になるように送信されることが好ましい。ＭＵＤを使用して複数の制御パケットを同時に受信することも可能である。ここで、単一のアクノリッジメントメッセージは、無線リソースを効率的に使用するために、複数のデータアクノリッジメントを含むことができる（且つ含むことが好ましい）。
ｔ６において、少なくとも一つのアクノリッジメントが送信ノードに達するとすると、転送の役割を担うべき一又は複数の候補ノードが決定される。幾つかの中継ノードを転送のために選択することにより、高いレベルの堅牢性が実現するが、通常、スループットが下がる。優先順位付けは、例えばコストから見た進行度、キューステータス情報、及び／又はバッテリ残量に基づくことができる。このような情報は、アクノリッジメントメッセージに明示的に格納することができる、及び／又は既に受信している情報から暗示的に生成することができ、例えばコストから見た進行度は下位のルート決定プロトコルからアプリオリ（演繹的）に認識することができる。キューステータス及びバッテリ残量のような要素を考慮に入れることが望ましい場合、これらの要素はコスト情報に取り込むことができるか、又はコストから見た進行度の基本計算の補足事項として個別に見積もることができる。例えば、バッテリ残量の少ないか、又は読み込みキューがたまっている中継候補ノードは、コストから見た進行度が大きい場合でも優先してはならない。
【００３１】
シングルユーザ検出ＳＤＦと比べた場合の差は、本シナリオでは、送信ノードが、通常、より多くのアクノリッジメント（ＡＣＫ）を受け取るので、優先順位付け対象となる候補ノードをより多く有し、その結果、ＱｏＳ調整を行なう際の自由度が一層高くなるので、スループット、コストから見た進行度、又は他の重要な指標を最大化することができることである。本実施例では、送信ノードＴ１はパケットアクノリッジメントを中継候補ノードＲ２から受け取るだけであるので、中継ノードＲ２を単に選択するだけで済む。送信ノードＴ２はパケットアクノリッジメントを中継候補ノードＲ２及びＲ３から受け取り、この特定の実施例における優先順位付けプロセスの結果は中継ノードＲ２である。
ｔ７においては、データ転送の役割を担う一又は複数の選択ノードに転送命令を送信することが好ましい。一般的に、受け入れパケット群は、一又は複数の選択中継ノードの送信バッファに所定の最適化基準に従って挿入するが、任意で送信キューのスケジューリングを全体的にやり直すことができる。この操作に関する種々の基準は、例えば遅延クラス又は優先クラスに基づいて想定することができる。
ｔ８において、一又は複数の選択ノードは転送命令アクノリッジメントで応答する。更に、ｔ８においては、使用する予定のない（例えば、別のノードが転送ノードとして選択されてしまったことにより）パケットは全て、即時廃棄するか、又は後の段階で随意で廃棄することができる。転送命令アクノリッジメントは、衝突のリスクが最小になるように送信することが好ましい。また、データアクノリッジメントと同様に、転送命令アクノリッジメントは、各応答ノードにつき一つの転送命令アクノリッジメントメッセージに集約することができる。ここで、複数の転送命令及び転送命令アクノリッジメントは、転送命令ＡＲＱ（オートマティックリピートリクエスト）状態を確実に制御するために取り交わす必要がある。これは、従来のＡＲＱにおける問題と同じ問題であり、公知のＡＲＱ技術を適用することができる。
【００３２】
最適化
大量の制御メッセージが送信されると、オーバーヘッド及びエネルギー消費をできる限り小さく維持することが不可欠である。これは、パケット群に含まれる情報の量を暗示的なシグナリングによって最小化することにより行なうことができる。例えば、候補ノード群の完全なアドレスを使用するのではなく、局所的（且つ固有）に割り当てられるアドレスを使用することができる（例えば、ルート制御プロトコルによる制御の下に）。これらのアドレスは局所的に割り当てられるものであるので、短いアドレスで十分である。別の方法では、コストから見た正の進行度又は特定範囲又は特定区間内のコストから見た進行度を有する（例えば正のしきい値を超える）候補ノード群のみに送信を行なう。つまり、アドレスフィールドが短いコスト要件フィールドに置き換えられる。送信ノードの複数の隣接ノードに隣接する（一組の）ノード群であることを示唆することにより、候補ノード群を暗示的に指定することもできる。例えば、一つの候補ノードのアドレスがパケット中に明示的に指定し、明示的にアドレスが指定された候補ノードの隣接ノード群であることを示唆することにより、一つ以上の他の適切な中継候補ノードのアドレスがパケットの中で暗示的に指定される。この操作では、インターネットにおいて良く知られているような（ハローメッセージ）隣接関係、例えばルート決定プロトコルの組み込み関数を構築するプロトコルを実行する必要がある。これは、オーバーヘッドが最初に仮定したものと同じ大きさである必要がないことを意味する。
またここで、ｔ１に先行するステップ、すなわち、何がノードを起動して送信を行わせるかは、普通、使用するチャネル又はメディアアクセス法によって決まることに留意されたい。例えば、スロット化ＡＬＯＨＡ、ＣＳＭＡ（Ｃａｒｒｉｅｒ  Ｓｅｎｓｅ  Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ）を使用することができるか、又は場合によってはスケジューリングされた送信機会を有する方式（ＳＴＤＭＡにおけるような）も使用することができる。ＳＴＤＭＡはそれ自体が複雑であるが、ここに提案する発明を別々のタイムスロットに展開することにより、新規の（ノードにおいてスケジューリングされた）ＳＴＤＭＡ派生物が得られ、それによってＳＴＤＭＡ方式がフェージング及びモビリティに対して更に堅牢になるので、スケジュールの更新頻度が少なくて済むことを理解されたい。
【００３３】
データパケットを送信するノードは、どのノードにデータパケットを転送させるべきかについて決定する役割を担うと考えられてきたが、別のノード（又は任意で、一連のノード群）を指定して、転送命令を決定し、続いて送信する役割を負わせることも可能である。従ってこの情報は、データパケットと一緒に格納する必要がある。この操作はＳＤＦに関しても記載されており、この操作によって、ノード集団が共同して通信の忠実度（ｃｏｍｍｕｎｉｃａｔｉｏｎ  ｆｉｄｅｌｉｔｙ）を、例えばダイバーシチを利用して向上させるように動作するという利点がある。転送命令決定に関するこの局所的処理の更なる利点は、エネルギー消費が小さくなり、且つ干渉が小さくなるにつれてリソースを空間的に更に効率的に再使用することができるということである。制御トラフィックはＭＵＤ関連の制御シグナリングに起因して比較的平易なＳＤＦを増大させるので、これは特に、提案するＭＵＤによって可能になるＳＤＦのようなプロトコルにおいて有用である。更に別の選択肢では、制御メッセージを受信及び送信することにより、制御機能を実行する所定の局を指定する。
キューイング規則は、公平にネットワークリソースを共有し、性能に敏感なアプリケーションに対して性能を保証する主要な要素であるので重要である。一般的に、ベストエフォート型アプリケーション（すなわち、ＱｏＳ要件のないアプリケーション）のために開発されたキューイング規則と、サービス保証アプリケーション（すなわち、ＱｏＳ要件付きのアプリケーション）のために開発された規則との間には差が設けられている。ベストエフォート型接続の場合、最も重要な目的は、リソースを均等に共有することであり、このサービスタイプのために開発されたキューイングアルゴリズムの例として、１）重み付けラウンドロビン、２）不足ラウンドロビン、及び３）重み付け均等化キューイングを挙げることができ、これらの全ては汎用プロセッサ共有アルゴリズムをエミュレートしようとする。当然のことであるが、サービス保証アプリケーションの場合、最も重要な目的は性能を保証することであり、このタスクを満たすキューイング規則の例として、１）重み付け均等化キューイング、２）仮想クロック、及び３）最早納期順を挙げることができる。
【００３４】
図５は、異なるユーザからの受信電力がどのように受信ノードに分散しているかの一例を示している。本例では、ＭＵＤ検出器は、ノードＴｔ，Ｔｕ，及びＴｖから受信する大きい方から３番目までの強度を有する３つの信号を復号化することができるが、４番目の送信ノードＴｗからの強度の小さい信号は復号化することができない。パス利得は送信ノードと他の候補ノード群との間で異なるので、受信電力レベルはこれらのノードにおいて異なることになり、従って復号化可能なデータパケットの順番だけでなく数が異なる。
ここで、転送（コストから見た）進行度基準を優先順位付けに採用する場合、最低の受信電力レベルを有するパケット（群）の優先度が最も高くなる場合が多いことに留意されたい。従って、このようなパケットは、通常、ノード群を「飛び越え」、更に距離が離れた候補ノードがこのパケットを受け取り、受け入れるまで、パケットの伝搬途中で減衰する。この様子を図６に示すが、この場合、送信電力を示す横棒は、データパケット群の受信電力レベルを示し、矢印は、候補ノード群及び送信ノード群における優先順位付けから得られる効果的な結果の例を示す。
【００３５】
議論
要約すると、本発明の重要な態様は、例えばコンテンション方式プロトコル、及び特にＳＤＦのような、ダイバーシチを適用したフォワーディングプロトコルのフレームワークへのＭＵＤの効果的な組み込みを可能にする優先順位付け（複数の優先順位付け）及びメッセージ交換に関する。
複数の中継候補ノードの存在を利用する、ダイバーシチを適用したフォワーディングの場合、複数のデータパケットは候補ノード群において復号化することができる。候補ノードは正しく復号化されたパケット群の優先順位付けを、種々の選択／性能基準に基づいて行なう。この操作は、例えばフロー制御（バッファ溢れを回避する）、輻輳制御（スループットの最適化を目的とする）、又は性能調整（例えばＱｏＳ指標に基づく優先順位付け）に関連付けることができる。
【００３６】
候補ノードは、集約させたアクノリッジメントメッセージ内で、又は別個に送信される優先順位付けされたデータパケット群に関するアクノリッジメントで応答することができる。集約されたアクノリッジメントメッセージを受信すると、送信ノード群はそれらに対応するアクノリッジメントを抽出する。
ダイバーシチを利用しない場合、例えば最短パスルーティングと連動するＡＬＯＨＡに関しては、送信ノードが単にデータを送信し、（マルチキャストされる）アクノリッジメントを受信するだけで十分である。
【００３７】
送信ノードは所望の性能目的に基づいて複数の受信アクノリッジメントの優先順位付けを行ない、続いて対応する転送命令が送信される候補ノードを選択する。
選択された候補ノードは、更に転送命令を受け取った対象となった、復号化されて受け入れられたパケット群を、ノードの送信バッファに挿入することにより、所望の性能目的を最適化する。
【００３８】
本発明の別の重要な態様は、候補ノードにおいて内部的に、送信ノードにおいて内部的に、又は候補ノード及び送信ノードの両方に用いることができる最大の転送進行度、又はコストから見た最大の進行度に基づく例示的優先順位付け基準に関する。
新規の優先順位付け及びメッセージ交換方式によって可能になる、ＭＵＤ及びダイバーシチを適用したフォワーディングの特殊な組合せによって、先行技術よりも優れた幾つかの利点がもたらされる。
【００３９】
マルチホップネットワークにおいてＳＴＤＭＡと連携させて使用するＭＵＤと比較すると、本発明は次のような利点をもたらす。まず、本発明は、ＭＵＤによって可能になる利点を提供しながらも、スケジューリングを行なう必要が全くないので、従来のＭＵＤ及びＳＴＤＭＡよりも複雑さがずっと低減される。次に、モビリティに起因して頻繁に更新する必要があるか、又はチャネルに急激にフェージングが生じる場合に極端に速く更新する必要のある厳しいＭＵＤ制限を有するスケジュールが生じない。更に、トラフィックパターンが変わる度に変える必要のあるＭＵＤ制限を有するスケジュールが生じない。つまり、ＭＵＤと組み合わせたＳＴＤＭＡと比較すると、本発明は、複雑さを有意に低減しつつＭＵＤの利点を提供する。更に、チャネルにフェージングが生じるとき、本発明は有利な形で使用することができるが、ＳＴＤＭＡのようなスケジューリングされた多重アクセスプロトコルは性能劣化を伴なう。
【００４０】
ＭＵＤに適合するダイバーシチフォワーディングメッセージ交換方式の構成では、ダイバーシチフォワーディングの利点が維持される（例えば、フェージングチャネルの利用が可能になる）だけでなく、スループットを非常に高くすることができる。これには２つの主要な理由がある。
・受信パケットの所与の使用リンクモード（例えば、符号化レート）の受信電力レベルが十分に高い場合、ＭＵＤにより、各ノードにおいて複数のデータパケットを同時に復号化することができる。
・好適な優先順位付け基準では、最も大きい（情報）転送（コストから見た）進行度を有するパケット群を選択するので、転送進行度が通常大きくなる。多くの場合、これは、選択パケット群が、受信されて正しく復号化されると同時に、低い受信電力レベルを有するパケット群であることを意味する。しかしながら、例えば普通のＳＤＦでは、この現象は生じ得ない。特に、フェージング利得は、低い電力レベルのパケット群に対しても利用することができることに注目されたい。大きい転送進行度は、パケットがネットワークにおいて相対的に短い時間を費やし、従って遅延が小さく、短時間でネットワークから離れて消えてしまうことにより、他のトラフィックに無線リソースを提供することを意味する。
【００４１】
更に、交換方式は、候補ノード群及びパケット送信ノード群における自由度を高くして、シングルユーザ検出ベースのＳＤＦに比べて全体性能を向上させるように作用する。候補ノード群では、複数のパケットの優先順位付けを使用して転送進行度を最大化し（上述）、ＱｏＳを調整することができ、また、この優先順位付けは、他の最適化基準に関しては、データ受信時及び後続の転送命令受信時の両方において使用することができる。さらに多くのアクノリッジメントを受信する際には、送信ノードにおける追加の自由度を使用して、転送進行度、輻輳制御、ＱｏＳ調整を最適化することができ、且つこの追加の自由度は他の最適化基準に使用することができる。
【００４２】
実行局面
図７は、本発明の例示的実施形態による送信側の関連部品の模式ブロック図である。特に、図７の実施形態は、ＭＵＤに適合するダイバーシチフォワーディングプロトコルにおける動作にカスタマイズされた中継候補ノードに適する。図７の中継候補ノード１００は基本構成要素として、アンテナ又はアンテナシステムに接続される従来型受信チェーン１１０、ＭＵＤデコーダ１２０、受信バッファ１３０、パケット優先順位付けユニット１４０、アクノリッジメントユニット１５０、従来型カプセルユニット１６０、符号化兼変調ユニット１７０、アンテナ又はアンテナシステムに接続される従来型送信チェーン１８０、送信バッファ１９０、更にはマルチホップコスト情報を提供するユニット１９５を備える。
中継候補ノード１００は、複数の送信ノードから、Ａ／Ｄ変換及び可能であれば周波数変換のような動作も含む受信チェーン１１０を通して送信される重畳信号を受信する。ＭＵＤデコーダ１２０は、受信する重畳信号に作用して複数のデータパケットを同時に復号化し、復号化された信号は第１ラウンド（１）において、受信バッファ１３０に転送される。ＭＵＤデコーダ１２０は、通常、マルチユーザ復号化と同時に復調を行なう。
【００４３】
パケット優先順位付けユニット１４０は、目的性能関数に基づいて適切な優先順位付けを行ない、転送に適する一つ以上のパケットを選択する。優先順位付けプロセスでは、優先順位付けユニット１４０は、普通、Ｂｅｌｌｍａｎ−Ｆｏｒｄのような下位のコスト決定プロトコル又は類似のプロトコルから得られるマルチホップコスト情報を利用する。中継候補ノード１００では、このようなコスト情報は、パケット優先順位付けユニットに接続されるマルチホップコスト情報ユニット１９５において収集する、及び／又は生成することが好ましい。受け入れられ、転送されるパケットの数は、利用可能なバッファ空間に起因して少ないことがあり、従って、通常はパケット限界を決定する目的でバッファ空間情報が送信バッファ１９０から優先順位付けユニット１４０に転送される。パケット優先順位付けユニット１４０は、アクノリッジメントユニット１５０と連動するか、又はアクノリッジメントユニット１５０と一体化され、このアクノリッジメントユニット１５０は、第１ラウンド（１）において、各選択パケットに関するパケットアクノリッジメントを発行し、対応するパケット送信ノードに送信する。
パケットアクノリッジメントは、集約させたアクノリッジメントメッセージに格納して送信するか、又はカプセル化及びアドレス指定を行なうカプセルユニット１６０、符号化１７２及び変調１７４を行なう結合ユニット１７０、並びに周波数変換及びＡ／Ｄ変換のような動作を含む送信チェーン１８０を使用することにより個別に送信する。
【００４４】
第２ラウンド（２）では、中継候補ノード１００は、候補ノードを選択した送信ノード群から一つ以上の転送命令を受信することが好ましい。受信する一又は複数の転送命令は、通常、パケット優先順位付けユニット１４０に転送される。パケット優先順位付けユニット１４０と連動するアクノリッジメントユニット１５０は、転送命令アアクノリッジメントを発行して対応する送信ノード又は送信ノード群に送信する。
パケット優先順位付けユニット１４０は、対応する転送命令を有する選択パケット群を送信バッファ１９０に挿入する。通常、パケット群は所定の最適化基準に従って挿入される。しかしながら、任意で、送信バッファ１９０に対し、例えば遅延クラス又は優先度クラスに基づいて、スケジュールのやり直しを行なうことができる。ＱｏＳサポートを望まない場合、単純な先入れ先出し（ＦＩＦＯ）キューを使用することができる。
続いて、送信バッファ１９０内のパケット群は、カプセル化及びアドレス指定を行なうカプセルユニット１６０、符号化１７２及び変調１７４を行なう結合ユニット１７０、並びに送信チェーン１８０を使用することにより、マルチホップネットワーク内を中継候補ノード群に向けて更に送信される。
【００４５】
図８は、本発明の例示的実施形態による送信側の関連部品のブロック模式図である。特に、図８の実施形態は、ＭＵＤに適合するダイバーシチフォワーディングプロトコルにおける動作にカスタマイズされた送信ノードに適する。図８の送信ノード２００は、基本構成要素として、送信バッファ２１０、カプセルユニット２２０、符号化兼変調ユニット２３０、アンテナ又はアンテナシステムに接続される従来型送信チェーン２４０、従来型受信チェーン２５０、復調兼復号化ユニット２６０、ノード優先順位付けユニット２７０、及び受信バッファ２８０を備える。
送信ノード２００は、一つ以上の宛先ノードに向けて送信する準備が整ったデータパケット群を、このノードの送信バッファ２１０に有する。ラウンド（１）では、パケット群は送信バッファ２１０から、カプセル化及びアドレス指定を行なうカプセルユニット２２０に転送される。アドレス指定に基づいて、送信ノード２００は、マルチキャスト又は可能であればブロードキャストを用いて、マルチホップネットワーク内の多数の中継候補ノードにパケット群を送信する。この特定の局面の更なる詳細については、参考文献［８］を参照されたい。カプセル化されたパケット情報は、符号化２３２及び変調２３４を行なう結合ユニット２３０と、中継候補ノード群に向けての送信を行なう送信チェーン２４０とに転送される。
【００４６】
第２ラウンド（２）では、送信ノード２００は、一つ以上の中継候補ノードから受信チェーン２５０、及び復調２６２及び復号化２６４を行なう結合ユニット２６０を通して一又は複数のパケットアクノリッジメントを受信する。パケットアクノリッジメントは、ノード優先順位付けユニット２７０に転送され、この優先順位付けユニットは目的性能関数に基づいて適切な中継候補ノードを選択する。次に、優先順位付けユニット２７０は、転送命令を発行して選択中継候補ノードに送信する。
第３ラウンド（３）では、一つ以上の選択中継ノードから受信する転送命令アクノリッジメントを任意に用いて、送信バッファ２１０から対応するパケット群を取り除くことができる。
【００４７】
ＭＵＤ検出器／デコーダに関する詳細情報は、例えば参考文献［１５］のような刊行物に記載されており、この参考文献は、最先端のリニアマルチユーザ検出器ファミリーについて記載している。
ここで、受信側におけるパケット優先順位付けを、一つ以上の受信ノードを受け持つ関連制御ノードに分散することができることを理解されたい。同じようにして、送信側において適切な中継ノードを選択するための優先順位付けも、関連制御ノードに分散することができる。
【００４８】
上に記載した実施形態は単に例示として示したに過ぎず、本発明はこれらの実施形態には限定されないことを理解されたい。本明細書において開示及び特許請求する基本原理に従う更なる変形、変更及び改善は本発明の範囲に含まれる。
【００４９】
参考文献
［１］Ｒ．Ｒｏｍ，  Ｍ．  Ｓｉｄｉ，  “Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ  Ｐｒｏｔｏｃｏｌｓ，  Ｐｅｒｆｏｒｍａｎｃｅ  ａｎｄ  Ａｎａｌｙｓｉｓ"，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  Ｎｅｗ  Ｙｏｒｋ，  １９９０，  ＩＳＢＮ−０−３８７−９７２５３−６，  ｐｐ．１−５．
［２］“Ｅｎｈａｎｃｅｄ  Ｉｎｔｅｒｉｏｒ  Ｇａｔｅｗａｙ  Ｒｏｕｔｉｎｇ  Ｐｒｏｔｏｃｏｌ"  ａｓ  ｐｒｉｎｔｅｄ  Ａｐｒｉｌ  ７，  ２００３  ｆｒｏｍ  ｗｗｗ．ｃｉｓｃｏ．ｃｏｍ／ｗａｒｐ／ｐｕｂｌｉｃ／１０３／ｅｉｇｒｐ−ｔｏｃ．ｐｄｆ．
［３］Ｒ．Ｎｅｌｓｏｎ  ａｎｄ  Ｌ．  Ｋｌｅｉｎｒｏｃｋ，  “Ｔｈｅ  ｓｐａｔｉａｌ  Ｃａｐａｃｉｔｙ  ｏｆ  ａ  ｓｌｏｔｔｅｄ  ＡＬＯＨＡ  ｍｕｌｔｉｈｏｐ  ｐａｃｋｅｔ  ｒａｄｉｏ  ｎｅｔｗｏｒｋ  ｗｉｔｈ  ｃａｐｔｕｒｅ"，  ｉｎ  Ｔｒａｎｓ．  Ｏｎ  Ｃｏｍ．，  Ｊｕｎ  ８４．
［４］Ｊ．  Ｊｕｂｉｎ  ａｎｄ  Ｊ．Ｄ．Ｔｏｒｎｏｗ，  “Ｔｈｅ  ＤＡＲＰＡ  ｐａｃｋｅｔ  ｒａｄｉｏ  ｎｅｔｗｏｒｋ  ｐｒｏｔｏｃｏｌｓ"，  ｉｎ  ＩＥＥＥ  Ｐｒｏｃｅｅｄｉｎｇｓ，  Ｊａｎ．  ８７．  ｐｐ．２１−３２．
［５］Ｍ．Ｂ．  Ｐｕｒｓｅｌｙ  ａｎｄ  Ｈ．Ｂ．  Ｒｕｓｓｅｌ，  “Ｎｅｔｗｏｒｋ  ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  ｆｒｅｑｕｅｎｃｙ−ｈｏｐ  ｐａｃｋｅｔ  ｒａｄｉｏｓ  ｗｉｔｈ  ｄｅｃｏｄｅｒ  ｓｉｄｅ  ｉｎｆｏｒｍａｔｉｏｎ"，  ｉｎ  ＩＥＥＥ  Ｊ．  Ｓｅｌｅｃｔｅｄ  Ａｒｅａｓ  ｏｆ  Ｃｏｍ．，  １２（４）  １９９４，  ｐｐ．１５５−１７４．
［６］ＵＳ  Ｐａｔｅｎｔ  ６，０９７，７０３．
［７］Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｐａｔｅｎｔ  Ａｐｐｌｉｃａｔｉｏｎ  Ｐｕｂｌｉｃａｔｉｏｎ  ＷＯ  ９８／５６１４０．
［８］ＵＳ  Ｐａｔｅｎｔ  Ａｐｐｌｉｃａｔｉｏｎ  Ｐｕｂｌｉｃａｔｉｏｎ  ＵＳ  ２００２／００５１４２５  Ａ１．
［９］“ＵＴＲＡ  （Ｕｎｉｖｅｒｓａｌ  Ｔｅｒｒｅｓｔｒｉａｌ  Ｒａｄｉｏ  Ａｃｃｅｓｓ）  Ｈｉｇｈ  Ｓｐｅｅｄ  Ｄｏｗｎｌｉｎｋ  Ｐａｃｋｅｔ  Ａｃｃｅｓｓ  （ＨＳＤＰＡ）"，  ３ＧＰＰ，  ＴＳ  ［２５．３０８］，  ｖ．  ０．１．０，  Ｓｅｐｔｅｍｂｅｒ，  ２００１．
［１０］ＴＩＡ／ＥＩＡ  ＩＳ−８５６，  “ＣＤＭＡ  ２０００：  Ｈｉｇｈ  ｒａｔｅ  ｐａｃｋｅｔ  ｄａｔａ  ａｉｒ  ｉｎｔｅｒｆａｃｅ  ｓｐｅｃｉｆｉｃａｔｉｏｎ"，  Ｓｔｄ．，  Ｎｏｖ．  ２０００．
［１１］Ｐ．  Ｖｉｓｗａｎａｔｈ，  Ｄ．  Ｔｓｅ  ａｎｄ  Ｒ．  Ｌａｒｏｉａ，  “Ｏｐｐｏｒｔｕｎｉｓｔｉｃ  Ｂｅａｍｆｏｒｍｉｎｇ  ｕｓｉｎｇ  Ｄｕｍｂ  Ａｎｔｅｎｎａｓ"，  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，  ｖｏｌ．  ４８（６），  Ｊｕｎｅ，  ２００２．
［１２］Ｂ．  Ｓｈｒａｄｅｒ，  Ｔ．  Ｇｉｌｅｓ，  “Ｓｃｈｅｄｕｌｉｎｇ  ａｎｄ  ｐｅｒｆｏｒｍａｎｃｅ  ｏｆ  ｍｕｌｔｉ−ｈｏｐ  ｒａｄｉｏ  ｎｅｔｗｏｒｋｓ  ｗｉｔｈ  ｍｕｌｔｉ−ｕｓｅｒ  ｄｅｔｅｃｔｉｏｎ"，  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２ｎｄ  Ｓｅｄｉｓｈ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｗｉｒｅｌｅｓｓ  Ａｄ−Ｈｏｃ  Ｎｅｔｗｏｒｋｓ，  Ｓｔｏｃｋｈｏｌｍ，  Ｊｏｈａｎｎｅｓｂｅｒｇｓ  Ｓｌｏｔｔ，  Ｍａｒｃｈ  ５−６，  ２００２．
［１３］Ａ．−Ｍ．  Ｃｈｏｕ，  ａｎｄ  Ｖ．Ｏ．Ｋ．  Ｌｉ，  “Ｓｌｏｔ  ａｌｌｏｃａｔｉｏｎ  ｓｔｒａｔｅｇｉｅｓ  ｆｏｒ  ＴＤＭＡ  ｐｒｏｔｏｃｏｌｓ  ｉｎ  ｍｕｌｔｉ−ｈｏｐ  ｐａｃｋｅｔ  ｒａｄｉｏ  ｎｅｔｗｏｒｋｓ"，  ＩＮＦＯＣＯＭ，  Ｍａｙ  １９９２，  Ｖｏｌ．２，  ｐｐ．７１０−７１６．
［１４］Ｖ．  Ｒｏｄｏｐｌｕ  ａｎｄ  Ｔ．  Ｍｅｎｇ，  “Ｐｏｓｉｔｉｏｎ  ｂａｓｅｄ  ＣＤＭＡ  ｗｉｔｈ  ｍｕｌｔｉ−ｕｓｅｒ  ｄｅｔｅｃｔｉｏｎ  （Ｐ−ＣＤＭＡ／ＭＵＤ）  ｆｏｒ  ｗｉｒｅｌｅｓｓ  ａｄ  ｈｏｃ  ｎｅｔｗｏｒｋｓ"，  ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｓｐｒｅａｄ−Ｓｐｅｃｔｒｕｍ  Ｔｅｃｈｎｏｌｏｇｙ  ＆  Ａｐｐｌｉｃａｔｉｏｎｓ，  Ｓｅｐｔ．  ６−８，  ２０００．
［１５］ＵＳ  Ｐａｔｅｎｔ  ６，６１８，４３３．
【図面の簡単な説明】
【００５０】
【図１】本発明の第１の好適な実施形態による複数の送信ノード及び一つの受信ノードに関する動作及び信号伝達を示すプロセスフロー模式図である。
【図２】受信ノードから異なる距離に位置する２つの送信ノードからの信号送信の一実施例を示す模式図である。
【図３】本発明の第２の好適な実施形態による複数の送信ノード及び一つの受信ノードに関する動作及び信号伝達を示すプロセスフロー模式図である。
【図４】本発明の第３の好適な実施形態による複数の送信ノード及び複数の受信ノードに関する動作及び信号伝達を示すプロセスフロー模式図である。
【図５】中継候補ノードにおける受信電力レベルの一例を示す模式図である。
【図６】本発明の一実施例による、優先順位付け及び対応する転送命令後の効果的な転送結果を示す、送信ノード群及び受信ノード群の模式図である。
【図７】本発明の例示的実施形態による受信側の関連部品のブロック模式図である。
【図８】本発明の例示的実施形態による送信側の関連部品のブロック模式図である。
【図１】
0004526533.tif 000002
【図２】
0004526533.tif 000003
【図３】
0004526533.tif 000004
【図４】
0004526533.tif 000005
【図５】
0004526533.tif 000006
【図６】
0004526533.tif 000007
【図７】
0004526533.tif 000008
【図８】
0004526533.tif 000009