JP5437504B2

JP5437504B2 - スケジューリングを行う装置、スケジューリング方法及びストレージ媒体

Info

Publication number: JP5437504B2
Application number: JP2012545980A
Authority: JP
Inventors: エックス．ゴーン，ミシェル; ジェイ．ステイシー，ロバート
Original assignee: インテルコーポレイション
Priority date: 2009-12-22
Filing date: 2010-11-29
Publication date: 2014-03-12
Anticipated expiration: 2030-11-29
Also published as: US8687611B2; WO2011087593A3; CN102118308A; EP2517521A2; JP2013515438A; EP2517521A4; CN102118308B; US20110149881A1; WO2011087593A2

Description

開示される発明はスケジューリングを行う装置、スケジューリング方法及びストレージ媒体等に関連する。

複数入力複数出力(MIMO)方式の無線ネットワークは、通常、複数の受信側の通信局に通信可能に結合された複数のアンテナを有するアクセスポイントを含む通信システムである。下りリンクのマルチユーザMIMOネットワークをサポート又は実現するため、アクセスポイント(AP)は、同時に通信する複数の通信局宛の複数のパケットについてスケジューリングを行う必要がある。既存のIEEE802.11-207標準規格は下りリンクのマルチユーザMIMOをサポートしていない。従って現在のアクセスポイント(AP)はアクセスポイント(AP)の送信キューの中にある第1のパケット又は第1のアグリゲートされたパケット(aggregated packet)を選択している。

現在のIEEE802.11通信局(STA)の実装では、パケットは先入れ先出し(FIFO)キュー方式で順番にプッシュされている。アクセスクラスカテゴリ(AC)キュー各々における先頭のパケットは内部の競合に参加する。内部の競合の勝者が外部の競合に参加する。IEEE802.11標準仕様においては、下りリンクの空間分割多重接続(SDMA)方式をサポートする如何なる手段も規定されておらず、アクセスポイント(AP)は同時に送信する複数のパケットを選択しなければならない。

米国特許出願公開第2007-0070964号明細書

本発明の課題は、下りリンクのマルチユーザMIMOにおける通信効率を向上させることである。

一実施形態による装置は、
マルチユーザ複数入力複数出力(MIMO)方式のネットワークにおけるパケット配信をスケジューリングする装置であって、
複数の通信局の各々についてウェイトカウンタを維持するアクセスポイント(AP)を有する装置である。

複数のアンテナを有するアクセスポイント及び複数の通信局を有するワイヤレスマルチユーザ複数入力複数出力(MIMO)方式のネットワークの一例を示すブロック図。アクセスポイント及び複数の通信局を有するワイヤレスマルチユーザ複数入力複数出力(MIMO)方式のネットワークの一例を示すブロック図。下りリンクマルチユーザ複数入力複数出力(MIMO)方式のネットワークにおける重み付けキュー方式の動作例を示すフローチャート。

以下、添付図面を参照しながら実施形態を詳細に説明する。図中、参照番号における左側の最上位の桁は、その参照番号が最初に登場する図番号を示す。各図における同様な参照番号は類似する又は同一の要素を示すために使用されている。

一般に、様々に記述されている図面は必ずしも寸法を描いているわけではなく、本願において特徴的な要素が強調して描かれている。明細書及び図面を通じて同様な要素は同じ参照番号で示されている。

以下の詳細な説明において、添付図面には添付図面の一部をなすリファレンス(参照番号又は参照符号)が付されており、その図面には本発明が使用される特定の実施形態が示されている。これらの実施形態は、いわゆる当業者が本発明を実施できる程度に充分に詳細に説明されている。更に、他の実施形態が使用されてもよいこと及び本発明の精神及び範囲から逸脱することなしに、論理的な変形、構造的な変形及び電気的な変形がなされてもよいことが理解される。従って以下の詳細な説明を限定的な意味に解釈してはならず、本発明の範囲は特許請求の範囲及びその均等物によってのみ規定される。

以下の説明において、先ず、重み付けキュー方式を使用して下りリンクのマルチユーザ複数入力複数出力(MIMO)方式のネットワークのパフォーマンスを改善する通信環境の一例が説明される。次に、そのような例示的な環境の中で使用される例示的な装置及び方法が説明されることに加えて、他の実施形態も説明される。

＜実施形態の詳細な説明＞
図1は、重み付けキュー方式(weighted queuing mechanism)を使用することが可能な例示的な通信環境又はシステム100を示し、重み付けキュー方式は下りリンクのマルチユーザ複数入力複数出力(MIMO)方式のネットワークのパフォーマンスを改善する。通信環境100はトランシーバ104を有するアクセスポイント(AP)102を含むように描かれている。トランシーバ104はプロセッサ106及びメモリ108を一部分として含む。アクセスポイント102は複数のアンテナ110(1)-110(n)を更に有する(整数nは任意のアンテナ数を表す)。図示されているように、アクセスポイント102は4つのアンテナ110(1)、110(2)、110(3)及び110(n)を少なくとも有する。他の実施形態においては異なる数のアンテナが使用されてもよい。

プロセッサコア106は任意のタイプのアーキテクチャによる処理ユニットを表し、例えば、プライマリ論理装置、オペレーション装置、コントローラ、メモリシステム等のアクセスポイント102の構成要素を含む。例えば、プロセッサコア106は、メモリ制御、入出力制御、グラフィックス処理等の処理機能を備えた1つ以上の処理装置及びチップセットを組み込んでいてもよい。

プロセッサコア106は更にメモリバス(図示せず)を介してメモリ108に結合され、一実施形態においてメモリはアクセスポイント102の「メイン」メモリを表し、システムコード及びデータを保存及び/又は実行するために使用される。メモリ108は、ダイナミックランダムアクセスメモリ(DRAM)、スタティックランダムアクセスメモリ(SRAM)又はその他の任意のタイプのメモリ(リフレッシュを要しないメモリを含む)により実現されてもよい。

メモリ108は他のストレージ装置を含んでいてもよい。そのような他のメモリ装置は取り外し可能なメディアドライブ(例えば、CD/DVDドライブ)、カードリーダ、フラッシュメモリ等を含む。メモリ108は様々な方法でプロセッサコア106に接続されてもよく、例えば、IDE(Integrated Drive Electronics)、ATA(Advanced Technology Attachment)、ASTA(Serial ATA)、USB(Universal Serial Bus)等により接続されてもよい。メモリ108は(不図示の)様々なアプリケーションモジュールを格納し、そのアプリケーションモジュールは処理コア106及びメモリ108を介して実行され、アクセスポイント102に様々な機能を提供する。

図1は通信環境100が複数の通信局(STA)112を含むように描かれている。図示されているように通信環境100は少なくとも4つの独立した通信局112(1)、112(2)、112(3)及び112(n)を含む。通信局112の各々はアンテナ114を有する。代替実施形態において通信局112の各々は複数のアンテナ114を有していてもよい。更に、アクセスポイントに備わっているアンテナ数に合致する複数のアンテナを有する単独の通信局(STA)112が、通信環境100に含まれてよいことも、本発明は想定している。

アクセスポイント102のアンテナ110の各々は特定の通信局112のアンテナ114に固有の信号を送信してもよいし、或いはアクセスポイントは特定の通信局112宛のデータパケットを多重化してもよい。本願における多重化(multiplexing)は、1つの信号を複数の信号に分割することと、1つの信号に合成することとを包含する概念である。データパケットが複数の信号に多重化されると、アクセスポイント102はその複数の信号を送信する。

下りリンクのマルチユーザMIMOをサポートするために、スケジューリング手段はアクセスポイントにある必要がある。なぜなら、キューの中の最初のパケットを送信するだけでなく、アクセスポイント(AP)は異なる通信局宛に送信する複数のパケットを選択しなければならないからである。したがって、現在のEDCA(Enhanced Distributed Channel Access)の手段は機能的に拡張されるべきである。

IEEE802.11のEDCA(Enhanced Distributed Channel Access)はIEEE802.11のDCF(Distributed Coordination Function)のサービス品質(QoS)を拡張したものである。QoSをサポートするための主な改善点は、EDCAが個々の優先度を用いてパケットを差別化し、それらを、アクセスポイント又は通信局における個々のキューにバッファされる特定のアクセスカテゴリ(AC)に対応づけることである。自身のEDCAパラメータを有するアクセスポイント/通信局における各々のアクセスカテゴリは、互いにチャネル独立性(channel independently of others)を有すると考えられる。アクセスポイントにおけるアクセスカテゴリ各々には、アクセスポイントのパラメータに基づく優先度が指定されている。

送信をスケジューリングする手段を改善するために、アクセスポイント(AP)は関連する通信局(STA)各々に対する内部ウェイトカウンタ(internal weight counter)を維持及び更新する。通信局(STA)毎の内部ウェイトカウンタはWC[STA][AC]のように記述される。ある通信局(STA)はパケットの衝突又は競合を体験するが、別の通信局(STA)は競合を体験しないかもしれないので、トポロジ及び位置の相違に起因して、通信局毎に内部ウェイトカウンタが使用される。これは、個々の通信局(STA)に関連する送信データレートが個々に記録され更新されることと類似している。

同様に、アクセスポイント(AP)は、SSRC[STA][AC]のように記述される通信局(STA)ショート再送カウント(SSRC)とSLRC[STA][AC]のように記述される通信局(STA)ロング再送カウント(SLRC)とを維持する。

アクセスチャネル(AP)102は、アクセスカテゴリ毎に1つのチャネルアクセスタイマを維持する。このアクセスタイマはCW[AC]のように記述される。CW[AC]は、IEEE802.11標準規格で規定されている競合ウィンドウである。

図2にはベーシックサービスセット(BSS)が示されている。空間分割多重(SDMA)方式の送信が、有効な送信機会(TXOP)の中で行われず、アクセスポイント(AP)102が或る通信局(STA)(すなわち、STA1-204)から肯定応答パケット又はアクノリッジメントパケット(ACK)を受信した場合、WC[STA1][AC]＜CW_max[AC]であるならば、STA1の内部ウェイトカウンタはインクリメントされる(WC[STA][AC]=(WC[STA][AC]+1)*2-1)。更に、SSRC又はSLRCの何れかもインクリメントされる。

一実施形態において、内部ウェイトカウンタはランダム化されない。その代わりにWC[STA][AC]はCW_min[AC]の初期値をとる。これは、CW_max[AC]に達するまで、再送の度にインクリメントされる。

別の実施形態においては、内部ウェイトカウンタがランダム化される。この場合、ランダムウェイトアレイRW[STA][AC]と言及される別のアレイが規定される。RW[STA1][AC]は[0，WC[STA1][AC]]の範囲内の一様分布の中から取得された疑似乱数である。ランダムウェイトアレイRW[STA1][AC]は、スロットがフリー(free)であると検出される毎にデクリメントされる。特定のタイムスロットの期間内で如何なる媒体の動きもなかった場合、ランダムウェイトアレイRW[STA1][AC]は1つデクリメントされる。媒体がフリーでなかった場合、媒体がフリーであることが再び検出されるまで、アクセスポイント(AP)は、ランダムウェイトアレイRW[STA1][AC]をデクリメントすることを止める。

空間分割多重接続(SDMA)通信における如何なる送信も成功した場合、アクセスポイント(AP)202はアクセスタイマCW[AC]=CW_min[AC]とともにバックオフを行う。空間分割多重接続(SDMA)通信における何れの送信も成功しなかった場合、アクセスポイント(AP)は、CW[AC]＜CW_max[AC]であるならば、アクセスポイント(AP)はCW[AC]をインクリメントする(CW[AC]=(CW[AC]+1)*2-1)。

CW_max[AC]は特定のアクセスカテゴリ[AC]についての最小競合ウィンドウを含む。このパラメータは、送信のための初期ランダムバックオフ待ち時間(すなわち、「ウィンドウ」)を決定するアルゴリズムに入力される。最小競合ウィンドウで指定されている値は、初期ランダムバックオフ待ち時間が決定される範囲の上限(典型的には、ミリ秒)である。

生成される第1の乱数は、最小競合ウィンドウCW_min[AC]について指定されている数と0との間の数である。送信が不成功だった場合、再送カウンタがインクリメントされ、ランダムバックオフ値(ウィンドウ)が2倍になる(倍増される)。データの送信が成功するまで又はランダムバックオフ値の大きさが最大競合ウィンドウで規定されている数に到達するまで、以後の通信の失敗に備えて倍増処理(Doubling)が続く。送信が成功した後、CW[AC]はCW_min[AC]にリセットされる。「CW_min」に有効な値は1、3、7、15、31、63、127、255、511又は1024である。「CW_min」の値は「CW_max」の値より小さくなければならない。

CW_maxは最大競合ウィンドウを表す。最大競合ウィンドウで指定されている値はランダムバックオフ値を倍増する際の上限(ミリ秒)である。データフレームの送信が成功するまで又は最大競合ウィンドウサイズに到達するまで、その倍増化が続く。最大競合ウィンドウサイズに到達すると、許容されている最大再送回数に達するまで、後続の競合の際に再送が続く。「CW_max」に有効な値は1、3、7、15、31、63、127、255、511又は1024である。「CW_max」の値は「CW_min」の値より大きくなければならない。

以下、上記のプロセスに関する擬似コードを示す：

一実施形態の場合、各々の送信の前に、アクセスポイント(AP)は、内部ウェイトカウンタを確認し、かつ同じACであって最小のウェイトに関連付けられているパケットを通信局(STA)から選択する。別の実施形態の場合、各々の送信の前に、アクセスポイント(AP)は、内部ウェイトカウンタを確認し、同じアクセスカテゴリ(AC)であってゼロのウェイトに関連付けられているパケットを通信局(STA)から選択する。

パケットに関連付けられている再送カウンタに依存して、アクセスポイント(AP)202は以下の方法の何れかによりパケットをSTA1-204に送信する：
SLRC[STA1][AC]≦1及びSSRC[STA1][AC]=0であった場合、リクエストトゥセンド(RTS)/クリアトゥセンド(CTS)を用いてパケットが再送されることを意味し、アクセスポイント(AP)202はRTSを通信局STA1-204に最初に送信する。通信局STA1-204からCTSを受信すると、アクセスポイントは、通信局STA1-204を含む複数の通信局(STAs)に同時にデータパケットを送信する。RTS/CTSは、フレームの衝突を減らすためにIEEE802.11無線ネットワーキングプロトコルにおいて使用されているオプション手段である。

データを送信しようとしているノードはリクエストトゥセンドフレーム(RTS)を送信することでプロセスを開始する。宛先ノードはクリアトゥセンド(CTS)により応答する。RTS又はCTSフレームを受信している他の如何なるノードも所与の時間の間にデータを送信することを控えるべきである。媒体にアクセスしようとする前にノードが待機する時間の長さは、RTS及びCTSフレームの双方に含められてもよい。

SLRC[STA1][AC]≧1及びSSRC[STA1][AC]≧1であった場合、RTS/CTSプロテクションを用いてパケットが再送されることを意味し、アクセスポイント(AP)は通信局STA1宛のパケットについてのデータレートを下げる。

SLRC[STA1][AC]=0及びSSRC[STA1][AC]=0であった場合、それは新たなパケットであって再送されていないことを意味し、アクセスポイント(AP)は媒体アクセス制御(MAC)プロテクションなしにパケットを送信する。

図3は、マルチユーザMIMO方式のネットワークにおけるパケット配信をスケジューリングする一実施形態による方法をフローチャートで示す。フローチャート300を説明する際に、図1のアクセスポイント102が参照される。しかしながら、フローチャート300による方法は非常に広範囲に及ぶ装置に広く適用可能であるように想定されており、図1の一実施形態に使用することのみに限定されないことが理解される。

ステップ302において、アクセスポイント(AP)が通信局(STA)各々についてアクセスカテゴリ(AC)毎にウェイトカウンタを初期化する。ウェイトカウンタWC[STA][AC]が、アクセスカテゴリCW_min[AC]についての最小競合ウィンドウに初期化される。最小競合ウィンドウに指定される値は、初期ランダムバックオフ待機時間が決定される範囲の上限(典型的にはミリ秒)である。

ステップ304において、送信に失敗した後、失敗した通信局の対応するウェイトカウンタWCが増やされる。ウェイトカウンタWC[STA][AC]は(WC[STA][AC]+1)×2-1になるように増やされる。

ステップ306において、ランダムウェイトRWは[0，WC[STA][AC]]の範囲内で一様に分散される。

ステップ308において、タイムスロットがアイドルであることが検出される毎にRWが1つだけ減らされる。

ステップ310において、アクセスポイントが、ランダムウェイトがゼロに達している通信局(STA)から送信するパケットを選択する。

以上例示的な方法の具体的な詳細が図面及び他のフローチャートの観点から説明されてきたが、図中の所定の処理は説明された順序で実行されなければならないわけではなく、変更されてもよいし、及び/又は状況に応じて前提的に省略されてもよいことが、理解されなければならない。本願において説明されているように、モジュール及びエンジンはソフトウェア、ハードウェア、ファームウェア又はそれらの任意の組み合わせにより実現されてもよい。更に、説明された処理及び方法は、メモリに保存された命令に基づいて、コンピュータ、プロセッサ又はその他のコンピュータ装置により実現されてもよい。そのメモリは1つ以上のコンピュータ読み取り可能なストレージ媒体(CRSM)を含む。

CRSMは、保存されている命令を実行するコンピュータ装置がアクセスできる利用可能な任意の物理的な媒体であってよい。CRSMは、ランダムアクセスメモリ(RAM)、リードオンリメモリ(ROM)、電気的に消去可能なリードオンリメモリ(EEPROM)、フラッシュメモリ又はその他のソリッドステートメモリ、コンパクトディスクリオードオンリメモリ(CD-ROM)、ディジタル多用途ディスク(DVD)又はその他の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージ又はその他の磁気ストレージ装置、又はその他の任意の媒体(所望の情報を保存するために使用可能でありかつコンピュータ装置がアクセスできる媒体)等を含むがこれらに限定されない。

Claims

マルチユーザ複数入力複数出力(MIMO)方式のネットワークにおけるパケット配信をスケジューリングを行う装置であって、
複数の通信局の各々についてウェイトカウンタを維持するアクセスポイント(AP)を有し、
前記アクセスポイント(AP)は、前記ウェイトカウンタWC[STA][AC]を初期化することで前記ウェイトカウンタを維持し、前記ウェイトカウンタWC[STA][AC]を初期化する際に、前記ウェイトカウンタWC[STA][AC]を、あるアクセスカテゴリについての最小競合ウィンドウCW _min [AC]に等しく設定する、装置。
前記アクセスポイント(AP)は、
送信に失敗した後に、前記ウェイトカウンタWC[STA][AC]を増やし、
送信に成功した後に、対応する通信局(STA)のアクセスカテゴリCW_min[AC]についての最小競合ウィンドウに等しくなるように前記ウェイトカウンタWC[STA][AC]をリセットする、請求項１に記載の装置。
前記ウェイトカウンタWC[STA][AC]は、
WC[STA][AC]=(WC[STA][AC]+1)×2-1
となるようにインクリメントされる、請求項２に記載の装置。
前記アクセスポイント(AP)は、通信局(STA)毎にかつアクセスカテゴリ(AC)毎にランダムウェイト(RW)を維持する、請求項１に記載の装置。
前記ランダムウェイト(RW)が、[0，WC[STA][AC]]の範囲内に一様に分布する疑似乱数である、請求項４に記載の装置。
前記アクセスポイント(AP)が、タイムスロットがアイドルであることを検出する毎にランダムウェイト(RW)を1つ減らす、請求項４に記載の装置。
前記アクセスポイント(AP)が、特定の通信局に対する通信局(STA)ショート再送カウント(SSRC)を維持する、請求項１に記載の装置。
前記アクセスポイント(AP)が、特定の通信局に対する通信局(STA)ロング再送カウント(SLRC)を維持する、請求項１に記載の装置。
前記アクセスポイント(AP)が、内部ウェイトカウンタを確認し、同じアクセスカテゴリ(AC)の中にありかつ最小のウェイトに関連付けられている特定の通信局(STA)のパケットを選択する、請求項１に記載の装置。
マルチユーザ複数入力複数出力(MIMO)方式のネットワークにおけるパケット配信をスケジューリングする、コンピュータで実行されるスケジューリング方法であって、
下りリンクマルチユーザMIMO送信における関連付けられたに通信局宛のトラフィックをスケジューリングするために、マルチユーザMIMO方式のネットワークにおいて特定の関連付けられた通信局各々について内部ウェイトカウンタを維持するステップと、
前記アクセスポイント(AP)が、特定の通信局に対する通信局(STA)ショート再送カウント(SSRC)を維持するステップと、
前記アクセスポイント(AP)が、特定の通信局に対する通信局(STA)ロング再送カウント(SLRC)を維持するステップと
を有し、前記内部ウェイトカウンタを維持するステップにおいて、前記ウェイトカウンタWC[STA][AC]を初期化する際に、前記ウェイトカウンタWC[STA][AC]を、あるアクセスカテゴリについての最小競合ウィンドウCW _min [AC]に等しく設定する、スケジューリング方法。
前記アクセスポイント(AP)が、送信に失敗した後に、前記ウェイトカウンタWC[STA][AC]を増やし、
前記アクセスポイント(AP)が、送信に成功した後に、対応する通信局(STA)のアクセスカテゴリCW_min[AC]についての最小競合ウィンドウに等しくなるように前記ウェイトカウンタWC[STA][AC]をリセットする、請求項１０に記載のスケジューリング方法。
前記ウェイトカウンタWC[STA][AC]は、
WC[STA][AC]＜CW_max[AC]の条件の下で、
WC[STA][AC]=(WC[STA][AC]+1)×2-1
となるようにインクリメントされ、
CW_max[AC]はランダムバックオフ値を倍増する際の上限値を表す最大競合ウィンドウを含む、請求項１１に記載のスケジューリング方法。
前記アクセスポイント(AP)はランダムウェイト(RW)を有する、請求項１０に記載のスケジューリング方法。
スケジューリング方法をプロセッサに実行させる命令を保存する1つ以上のコンピュータ読み取り可能なストレージ媒体であって、前記スケジューリング方法は、
下りリンクマルチユーザMIMO送信における関連付けられたに通信局宛のトラフィックをスケジューリングするために、マルチユーザMIMO方式のネットワークにおいて特定の関連付けられた通信局各々について内部ウェイトカウンタを維持するステップと、
前記アクセスポイント(AP)が、特定の通信局に対する通信局(STA)ショート再送カウント(SSRC)を維持するステップと、
前記アクセスポイント(AP)が、特定の通信局に対する通信局(STA)ロング再送カウント(SLRC)を維持するステップと
を有し、前記内部ウェイトカウンタを維持するステップにおいて、前記ウェイトカウンタWC[STA][AC]を初期化する際に、前記ウェイトカウンタWC[STA][AC]を、あるアクセスカテゴリについての最小競合ウィンドウCW _min [AC]に等しく設定する、ストレージ媒体。