在無線區域網中實現資源預留的半隨機退避方法
2023-12-11 16:52:57 1
專利名稱：在無線區域網中實現資源預留的半隨機退避方法
技術領域：
本發明一般涉及無線通信，尤其涉及在無線區域網(WLAN)上用於在減少衝突的同時提供增加的吞吐量的資源預留半隨機退避方法。
背景技術：
在組播(multicast) /廣播應用中，在有線和/或無線網絡上將數據從一個伺服器發送給多個接收器。如本文使用的組播系統是其中伺服器同時將相同數據發送給多個接收器的系統，其中這些接收器形成多達並且包括所有接收器的所有接收器的一個子集。廣播系統是其中伺服器同時將相同數據發送給所有接收器的系統。也就是說，組播系統按定義可以包括廣播系統。移動計算設備上語音和視頻應用的流行引起了對媒體訪問控制(MAC)協議的關注，MAC協議負責將共享媒體資源分配給多個通信站並且解決當兩個或更多個站同時訪問媒體時發生的衝突。在當前IEEE 802. 11無線LAN中，MAC協議層的分布式協調功能(DCF) 將二進位指數退避(BEB)算法用於基本信道訪問。BEB算法通過在共享通信媒體的站之間隨機化媒體訪問的定時來緩解網絡衝突的問題。BEB算法中信道訪問的定時通過在每個退避循環中將時隙計數器設置成從競爭窗口
中選擇的隨機整數來隨機化，並且一旦在最後退避循環中數據發送失敗CW加倍。這裡，退避循環是退避時隙計數器從初始最大值遞減到零的過程。BEB的簡單性和良好性能有助於IEEE 802. 11DCF/EDCA的流行。但是，如實際經驗和理論分析所展示，BEB算法存在一些缺陷。首先，發送嘗試的衝突概率隨網絡中的活動站的數量成指數增大。其次，不能限制媒體訪問時延(delay)，以及抖動是可變的，這可能不適合多媒體應用。提供一些可以幫助理解本發明的概念/術語。一個幀是數據的一個單位。也就是說，可以按分組或幀或任何其它方便格式將數據打包。如本文所使用，一個幀用於指示以用於發送的格式打包的數據。退避輪迴(round)/階段/循環是退避時隙計數器從初始值(最大)向下計數到零的過程。當計數器到達零時，嘗試新的發送。一個幀發送可能涉及到多個退避輪迴/階段(由於不成功發送嘗試)。如在此所使用，一個時隙代表在退避時隙計數器被凍結期間的連續時段。它可以指對於物理層足以進行一次載波偵聽的固定時段(通常幾微秒)或當在共享媒體上發送一個幀時的可變時段(取決於分組的長度和物理數據速率，通常在數百微秒到幾毫秒之間)。在具有共享媒體的網絡中，每個站基於媒體的物理或虛擬載波偵聽的結果狀態凍結或減少它的退避時隙計數器。因此，由於媒體的共享性質，在站之間對齊時隙計數變化。時隙可以用作使整個過程離散的基本時間單元。正整數η = 1，2,3,..., N用於指示第1，2，3，...，N時隙，並且In用於指示第η時隙上共享媒體的狀態， 例如，當繁忙時，In= 1，否則，In = 0。第η時隙上站i的退避時隙計數表示成Sloti (η)。在序號為PCT/US09/01179的申請中，描述了減少或避免衝突的確定性退避(DEB) 方法。在DEB方法中，按時隙確定性地調度發送。在序號為PCT/US09/001855的申請中，描述了克服諸如在確定性退避(DEB)方法中固有的向後兼容性和可靠性之類的問題的鬆弛確定性退避(R-DEB)方法。R-DEB方法以儘可能確定的方式選擇退避時隙計數以減少或避免網絡衝突。R-DEB方法還將隨機性引入這個過程中，以保持諸如BEB (二進位指數退避)方法之類的常規隨機退避方法的靈活性和易於部署特徵。因此，R-DEB方法在網絡效率與靈活性之間作了折衷，並且可以視作DEB算法和BEB算法的組合。R-DEB算法的最初動機是在與以前標準保持向後兼容性的同時使確定性退避適用於視頻傳輸系統。R-DEB按如下操作。當站將它的退避時隙計數Sloti(Ii)重新設置成固定數M時 (注意，這裡的η是時間線上的變量)開始退避輪迴。一旦通過物理載波偵聽過程確定在一個時隙中共享媒體是空閒的，則站將它的退避時隙計數減1。如果這個新時隙計數滿足發送觸發條件(也就是，新時隙計數等於觸發集A的元素之一，例如，slot, (n) = k)，則節點(站、客戶設備、移動終端、行動裝置)將獲得啟動數據發送的機會(因此，「觸發發送」)。 如果此時沒有幀要傳送，則節點放棄該機會，並繼續遞減它的時隙計數。數據發送的結果決定元素k是否應該還保留在觸發集中如果成功發送，則這個觸發元素保留在觸發集中；如果未成功發送數據，則將以概率P啟動用來自間隔
中的新元素k'取代舊元素k的觸發元素替代過程。R-DEB方法包括從間隔
中選擇一個元素用於包括在觸發集Qt 中以減少網絡衝突的方法和裝置。應該注意，站可以是計算機、膝上型計算機、個人數字助理(PDA)、雙模式智慧型手機或可以移動的任何其它設備。資源預留的概念是眾所周知的，並且廣泛用在時分多址(TDMA)方案中，以實現高吞吐量和為異步傳輸模式(ATM)網絡提供的某種水平的服務質量OioS)。在典型TDMA預留(R-TDMA)解決方案中，無線電資源被組織成超幀，每個超幀被劃分成等長的多個時隙， 一個站可以通過預留請求預訂每個超幀中的一個或幾個時隙作為它的預留無線電資源。如本文所使用，節點(客戶機、移動站、行動裝置、移動終端、站、膝上型計算機、計算機、個人數字助理(PDA)、雙模式智慧型手機、...)是可以用於指示無線區域網(WLAN)中的終端設備的所有術語。一個站在這些預留時隙中可以具有無衝突信道訪問，因此可以容易地實現 QoS0在R-TDMA的另一種靈活版本中，預留ALOHA(R-ALOHA)中，通過跟蹤前超幀(previous superframe)中數據發送的結果自動預留無線電資源。前超幀中的給定時隙中的成功發送導致在隨後超幀中為傳送者(發送者)預留相同時隙。圖1(a)例示了如何在三個站A、B 和C之間通過R-ALOHA實現預留。站A在第一超幀中成功獲得預留時隙1，而站B和C在第二超幀中獲得它們的預留時隙，因為站B和C在第一超幀中相互衝突。模擬結果示出， R-ALOHA與分時隙ALOHA相比在明顯更高的信道利用上實現了較短的時延。R-ALOHA的優點在於，它自動實現資源預留而不需要像常規TDMA解決方案通常做的那樣涉及中央協調者。本發明借用R-ALOHA的構思，並將它應用於基於載波偵聽多路訪問(CSMA)的無線網絡。更具體地，本發明試圖將R-ALOHA併入分布式協調功能(DCF)/增強型分布式信道訪問(EDCA)中，以便改進在家庭環境下在IEEE 802. 11網絡上輸送內容的
4QoS性能。挑戰是如何在CSMA環境的背景下實現資源預留。由於TDMA網絡中的兩種基本特徵，周期性和同步性，所以在R-ALOHA中資源預留是可能的。周期性意味著每個超幀具有相同數量的等長時隙，使得站可以容易地識別當前超幀中它想再次使用的時隙。同步性因為時隙是與該站在前幀中所使用的完全相同的時隙而使時隙識別成為可能。事實上，只要網絡具有上述兩種特徵，那麼可以按照與R-ALOHA相似的途徑實現資源預留。現在，剩下的問題是確定CSMA網絡是否具有該兩種特徵一同步性和周期性。一般說來，由於在多跳網絡(multi-hop network)中存在隱藏終端，所以不能使CSMA網絡同步。但是，考慮所有站共享相同媒體的單跳網絡(single-hop network)並且假設理想載波偵聽，可以實現同步。CSMA網絡中的同步意味著網絡中的站的退避時隙計數器在一個時隙中根據相同網絡事件(發送或空閒)同時遞減或凍結。CSMA背景下的術語「時隙」具有與在TDMA背景下使用的時隙不同的含義。將它定義成在退避時隙計數器凍結期間的連續時段。它可以持續物理層足以進行一次載波偵聽的極短時段(通常幾微秒)，或足以完成一個幀交換序列的長時段(取決於幀大小和物理數據速率，通常從數百微秒到幾毫秒)。因此， CSMA網絡中的時隙的持續時間隨時間而變。典型地，對於共享相同媒體的站A和B，由於無線信道的廣播性質，每個站獲悉的信道狀態轉變序列應該是相同的。更一般地，如果不考慮隱藏終端，則共享媒體的所有站應該保持反映媒體的利用歷史的相同序列。這種共享性質建立了站之間的退避時隙計數器在相同衝突域中同步的概念。為了在CSMA網絡中實現周期性，當在最後退避循環中發生成功發送時，在退避過程中引入對退避時隙計數器的數值的確定性選擇。這裡，退避循環是當退避時隙計數器從初始值遞減到零時的時段。通過確定性選擇，將站的時隙計數器重新設置成網絡中的所有站共享的公用確定值。這個公用值定義CSMA網絡的周期性(就時隙而言)。
發明內容
在本文中，將回訪IEEE 802. 11無線網絡中多址訪問(multiple access)的問題。圖1 (b)例示了如何在CSMA網絡中實現資源預留。在第一退避循環中，站A、B和 C每一個分別生成如1，3和3的隨機退避時隙計數器。由於站A在第一退避循環的第2時隙中成功發送了數據，所以在其發送數據之後它將它的時隙計數器確定性地重新設置成4， 這允許它在下一個退避循環中再次訪問第2時隙。因此，為站A預留了第2時隙。站B和C 在第一退避循環的第4時隙上衝突，並且站B和C將它們的時隙計數器重新設置成隨機值， 例如，分別是3和5，這允許它們不衝突地在下一個退避循環中分別訪問第3和第5時隙。 此外，通過將它們的時隙計數器設置成4，B和C兩者可以為隨後退避循環中的信道訪問預留時隙。公用值4給出網絡的周期性。因此，在CSMA網絡中，通過將周期性引入退避過程中來實現資源預留。周期性依賴於使網絡同步的低級載波偵聽機制。資源預留的性能受諸如載波偵聽精度、隱藏終端等之類的許多因素影響。本發明描述在IEEE 802. 11無線網絡中實現資源預留的方法。在本發明的方法中，將預留成分引入允許站根據前一個循環中的成功單播發送確定性地設置它的退避時隙計數器的退避算法中。資源預留是通過重用相繼退避循環中的時隙實現的。這種方法可以對當前的軟體和/或硬體修改最小地應用在當前IEEE 802. 11DCF/EDCA中，但帶來了使網絡衝突減少並因此使吞吐量更高和使網絡時延更短的額外優點。相信包括音頻、視頻等的多媒體應用將從本發明的方法中獲益。本文描述方法和裝置，其包括確定是否已經成功發生單播發送；響應該確定將競爭窗口調整到最小值並將退避時隙計數器調整成競爭窗口的數值加1的二分之一；以及使用多種調整方案之一調整競爭窗口並從零與競爭窗口之間的間隔中選擇所述退避時隙計數器。
當結合附圖閱讀時，可以從如下詳細描述中更好地理解本發明。附圖包括如下簡要描述的下列圖圖1 (a)例示了如何在三個站A、B禾Π C之間通過R-ALOHA實現預留；圖1 (b)例示了如何在CSMA網絡中實現資源預留；圖2(a)示出了在離散時間線上的訪問過程；圖2(b)示出了在服務環(service ring)上的訪問過程；圖3是依照本發明的原理的用於資源預留的示例性半隨機退避方法的流程圖；以及圖4是實現本發明的半隨機退避方法的裝置的示例性實施例的框圖。
具體實施例方式1.半隨機退避(SRB)的概念假設用在網絡中的幀從時隙0開始。讓Sloti (η)表示第η時隙上站i的退避時隙計數器的數值。對於給定發送機會(TXOP)，如果通過確認指示，所有數據發送成功，則可以認為這個TXOP是正的；否則，認為這個TXOP是負的。注意，在IEEE 802. IlMAC中，通常不確認廣播和/或組播(B/M)數據，所以如同發送廣播(組播)數據(B/M數據)的TXOP是負的那樣來對待廣播和組播數據。將Itx。p定義成最後退避循環中TXOP的狀態。可以按如下描述本發明的半隨機退避(SRB)方法。每當Sloti(Ii)到達零並且需要重新設置時，通過如下更新它的值
JJt>} Iimp =正數
SlOti{n + l) = \rmid(0,CW)^^ Ilmp=負數⑴其中CW代表如常規隨機退避方法所定義的退避競爭窗口，並且M是網絡中的站共享的公用整數。方程(1)表明，當前TXOP是正數時-通常指示成功發送(只對於單播發送)，將時隙計數器重新設置成確定值M ；否則，像常規隨機退避方案那樣做，將它重新設置成來自退避競爭窗口中的隨機值。可以認識到，SRB包含隨機成分和確定成分。退避過程在隨機成分中遵循常規途徑，但將周期性引入確定成分中。在站確定TXOP在前一個退避循環中是正的還是負的之後，該站選擇將哪個成分重新設置其退避時隙計數器。
6
在方程(1)中，CW是可以通過不同隨機退避方法控制的站之間的時變參數。例如， Cff的變化在將SRB應用於DCF/EDCA時可以遵循二進位指數增加，或遵循像指數增加指數減小(EIED)或線性增加線性減小(LILD)那樣的其它變化圖案。另一方面，對於用於預約的站，M是固定參數。在DCF/EDCA的背景下，將M設置成(CWmin+l)/2，以便使SRB的平均時延保持等於二進位指數退避(BEB)中的最小時延。M對於站也可以不同，在該情況下，通過網絡中的不同M的最大公約數(gcd)定義服務環大小。SRB的確定成分中的參數M定義周期性以便預留信道資源。可以使用包括M個固定時隙的服務環最佳地描述SRB中的訪問過程。確定退避時隙計數器的數值等效於從該環中選擇時隙。當使用隨機成分用於退避時，從該環中隨機選擇時隙，而當使用確定成分用於退避時，因為退避間隔等於允許本發明的方法在隨後退避循環中重複使用相同時隙的環大小，所以預留時隙。圖2 (a)示出作為離散時間線的訪問過程，而圖2(b)示出作為服務環的訪問過程。 當站A在時隙Al上衝突時，它將它的退避計數器重新設置成隨機值，這允許站A在時隙A2 上訪問信道。由於站A在時隙A2成功發送了數據，所以站A確定性地將它的退避計數器設置成M。在服務環上，將退避時隙計數器設置成M意味著再訪問前時隙(previous slot)。 也就是，時隙A2和A3對應於環上的相同時隙。因此實現資源預留。對於站A和B，只要它們預留環上的不同時隙，站A和B可以在網絡中具有無衝突信道訪問。在本文中，將確定成分稱為預留成分。SRB中服務環的作用類似於R-ALOHA中超幀的作用。它們之間的主要差異在於，在 SRB中，時隙的長度是可變的，而在R-ALOHA中，它是固定的。SRB應該比R-ALOHA更有效， 因為由於空閒時隙具有最短時間長度，所以使空閒中浪費的時間最小化。儘管SRB的原理是針對沒有任何錯誤的單跳網絡來描述的，但也可以以降低的性能增益為代價應用於多跳和易出錯網絡。正如所討論的，資源預留在沒有任何載波偵聽錯誤的單跳網絡中最佳地實現。但是，對於多跳和易出錯網絡，隱藏終端的存在、載波偵聽錯誤和信道錯誤可能損害資源預留-前兩種因素導致破壞同步性的站之間的非同步退避過程。後一種因素因為大多數TXOP被認識成負的而導致差的資源預留性能。在這樣的情況下，SRB使用隨機成分用於退避。因此，將降低由資源預留引起的性能增益。當新站加入網絡中時，新站首先使用隨機成分來選擇用於數據發送的時隙，這可能會在新站加入網絡中之後的前幾個退避循環內引起網絡衝突。但是，衝突概率會隨著網絡演變而降低，因為越來越多的站將使用預留的時隙用於數據發送。2. 一般情形下的半隨機退避迄今為止已經假設網絡中的每個站為資源預留保持相同參數M。由於站具有大小相同的服務環，所以只要站選擇服務環中與其它站不同的時隙作為它的預留時隙，則每個站將可以經歷無衝突信道訪問。但是，當站具有不同大小的服務環，或站保持不同預留參數M時，一個站預留的時隙可能與其它站的其它預留時隙仍衝突。考慮單跳網絡中分別具有不同預留參數Mi和％的兩個站i和j。假設在某個退避循環中，兩者具有無衝突信道訪問，並且因此，站i和j在隨後退避循環中進入預留狀態。對於當前退避循環中的時隙，比如說，時隙1，兩個站的時隙計數器應該相互不同(以在這個循環中允許無衝突信道訪問)， Sloti(I) Φ Slotj(I)。有必要找出MiZiMj的什麼數值將導致站i和j在隨後退避循環中的無衝突預留時隙。注意，Mi是站i的服務環大小，而Mj是站j的服務環大小。在k個時隙之後，站i和j的時隙計數器的數值將變成Sloti (k+1) = Sloti (l)-kmod Mi (2)slotj(k+l) = slotj(l)-kmod Mj (3)為了允許無衝突信道訪問，站i和j應該在時隙1之後的所有時隙中保持不同時隙計數器，即，對於所有k彡Odloti (k+1)興Slotj (k+1)。這隱含a · MJsloti (I)^b. Mj+slotj (1)，對於Z ⑷根據同餘理論(congruencetheory)，這等效於說(Iij 不能被(Sloti (I)-Slotj(I) 除，其中Clij是Mi和Mj的最大公約數(gcd)。因此，相信，弓丨理I為了具有站i和j之間的無衝突預留時隙，Sloti(I)和Slotj(I)應該落入不同同餘類模數(1^.( = gcd (Mi，Mj))。對於具有預留參數M1, M2, ...，Mn的N-站網絡，任何一對站應該遵守引理I。讓 Sloti(I) (1 ^ i ^ N)表示時隙1上時隙計數器的數值，然後通過同餘理論，定理I 設d = gcd (M1, M2, ... , Mn)，則系統中具有無衝突預留時隙的充分條件是 slot, (1) (1 ^ i ^ N)應該落入不同同餘類模數d。因子d定義網絡中公用服務環的大小，並且每個站的服務環是這樣的公用服務環的倍數。注意，Sloti(I) (1 < i < N)由SRB的隨機選擇成分決定。因此，只要兩個站從公用服務環中選擇不同時隙作為它們的預留時隙，則它們在隨後退避循環中將具有無衝突信道訪問。此外，在一些情形下，兩個站可以無衝突地多路復用公用服務環中的時隙。當將SRB應用在其中不同優先級的數據使用不同預留參數M用於信道訪問的IEEE 802. IlEDCA中時，有關網絡中的服務環的不同大小的討論尤其有用。3. IEEE 802. 11DCF/EDCA 中的 SRB下面，將討論如何通過將SRB結合到普遍使用的MAC IEEE 802. 11DCF/EDCA協議中來應用SRB的概念。由於兩種協議建立在BEB(二進位指數退避)上，所以重點是如何使 SRB的概念適用於BEB機制。為了清楚起見，像S-BEB、S-DCF和S-EDCA那樣，前綴S用於指代具有SRB能力的方法。如上面所討論，SRB與一般隨機退避方法的主要差異在於，除了普通隨機成分之夕卜，還將預留成分引入SRB中。通過加入預留成分，BEB演變成S-BEB。在S-BEB中，將預留參數M設置成(CWmin+l)/2。注意，在BEB中，立即成功發送之間的平均間隔是(CWmin+l)/2 時隙，因此為M選擇(CWmin+l)/2與BEB中的最小時延(平均起來)相比在預留狀態下保持了 S-BEB的平均時延。S-BEB的偽碼如下
權利要求
1.一種方法，所述方法包含 確定是否已經發生成功的單播發送；響應於所述確定將競爭窗口調整到最小值並且將時隙退避計數器調整成所述競爭窗口的數值加1的二分之一；以及使用多種調整方案之一調整所述競爭窗口並且從零和所述競爭窗口之間的間隔中選擇所述時隙退避計數器。
2.根據權利要求1所述的方法，其中，所述調整方案包括二進位指數退避、成倍增加線性減小、指數增加指數減小和線性增加線性減小。
3.根據權利要求1所述的方法，還包含 確定是否有更多要發送的數據；以及響應於所述確定發送所述數據。
4.一種裝置，包含確定是否已經發生成功的單播發送的部件；響應於所述確定將競爭窗口調整到最小值並且將時隙退避計數器調整成所述競爭窗口的數值加1的二分之一的部件；以及使用多種調整方案之一調整所述競爭窗口並且從零和所述競爭窗口之間的間隔中選擇所述時隙退避計數器的部件。
5.根據權利要求4所述的裝置，其中，所述裝置是行動裝置、伺服器和基站之一。
6.根據權利要求4所述的裝置，還包含 確定是否有更多要發送的數據的部件；以及響應於所述確定發送所述數據的部件。
全文摘要
描述了方法和裝置，包括確定是否已經發生成功的單播發送；響應該確定將競爭窗口調整到最小值並將時隙退避計數器調整成競爭窗口的數值加1的二分之一；以及使用多種調整方案之一調整競爭窗口並從零與競爭窗口之間的間隔中選擇所述時隙退避計數器。
文檔編號H04W74/08GK102474883SQ201080033316
公開日2012年5月23日 申請日期2010年7月13日 優先權日2009年7月29日
發明者何勇, 李鈞, 馬小駿 申請人:湯姆森特許公司