《電子技術應用》
您所在的位置:首頁 > 顯示光電 > 設計應用 > 基于802.11標準WLAN芯片指數(shù)回歸算法
基于802.11標準WLAN芯片指數(shù)回歸算法
OFweek通信國際
摘要: 當802.11WLAN網(wǎng)絡上的數(shù)個裝置同時傳送數(shù)據(jù)時,由于頻寬的限制,,會發(fā)生“封包碰撞”(collision)的情況,。一般以太網(wǎng)絡是使用“指數(shù)回歸算法”(exponentialbackoffalgorithm)來解決這種問題。
Abstract:
Key words :

  當802.11 WLAN網(wǎng)絡上的數(shù)個裝置同時傳送數(shù)據(jù)時,,由于頻寬的限制,,會發(fā)生“封包碰撞”(collision)的情況。一般以太網(wǎng)絡是使用“指數(shù)回歸算法”(exponential backoff algorithm)來解決這種問題,,而802.11標準也不例外,。802.11的MAC標準稱作“分布式基礎無線媒體擷取控制”(distributed foundation wireless MAC;DFWMAC)。

  如果真要自行設計“專屬的WLAN”,,必須先行克服從射頻實體層至MAC層的通信協(xié)議問題,。假設他們已經(jīng)具有很純熟的27MHz無線電傳收機技術,,則剩下的就是要解決MAC層的通信協(xié)議問題,,這主要包含兩個重要的問題:CSMA/CA和回歸(backoff)。當然,,除此之外,,RTS/CTS流量控制和“分布式協(xié)調(diào)功能(distributed coordination function;DCF)”,以及更上層的驅(qū)動程序,、應用軟件,、各通信層之間的接口….等,都要嚴格考慮在內(nèi),。不過,,本文將專注于回歸技術的探討,。

  碰撞的問題

  當兩臺裝置同時開始傳送數(shù)據(jù)時,它們將會先檢查纜線中是否有載波存在,,若載波有存在,,而且纜線是處于閑置狀態(tài),它們就會馬上傳送封包,。因為它們所發(fā)射的電子信號會彼此干擾,,這種干擾會造成“封包碰撞”的結果。碰撞會使封包內(nèi)的數(shù)據(jù)混淆不清,,致使接收到的封包無法還原成正確的數(shù)據(jù),。

  雖然,CSMA/CA和回歸都能解決碰撞的問題,,不過,,在功能上,它們是有差別的,。CSMA/CA是一種“競爭”(contention)通信協(xié)議,,它傾聽WLAN網(wǎng)絡,避免碰撞發(fā)生,。它和傳統(tǒng)的CSMA/CD(被以太網(wǎng)絡使用)不同,,CSMA/CD是在碰撞發(fā)生之后,才起來處理后續(xù)的傳送作業(yè),。CSMA/CA則是防患未然,,所以比較有助于網(wǎng)絡通信。因為它在任何真正的數(shù)據(jù)被傳送之前,,會先在網(wǎng)絡上廣播(broadcast)一個信號,,傾聽是否有碰撞發(fā)生,同時告訴其它裝置不要廣播,。

  當發(fā)生碰撞時,,裝置必須等待一段時間,等纜線恢復閑置時,,才能再傳送,。不過,若兩個裝置

  同時再次發(fā)射信號,,則另一個碰撞又將再次發(fā)生,。為了避免這個情況發(fā)生,就必須采用“二進制指數(shù)回歸算法”來解決,。

  當802.11 WLAN網(wǎng)絡上的數(shù)個裝置同時傳送數(shù)據(jù)時,,由于頻寬的限制,會發(fā)生“封包碰撞”(collision)的情況,。一般以太網(wǎng)絡是使用“指數(shù)回歸算法”(exponential backoff algorithm)來解決這種問題,,而802.11標準也不例外,。802.11的MAC標準稱作“分布式基礎無線媒體擷取控制”(distributed foundation wireless MAC;DFWMAC)。

  如果真要自行設計“專屬的WLAN”,,必須先行克服從射頻實體層至MAC層的通信協(xié)議問題,。假設他們已經(jīng)具有很純熟的27MHz無線電傳收機技術,則剩下的就是要解決MAC層的通信協(xié)議問題,,這主要包含兩個重要的問題:CSMA/CA和回歸(backoff),。當然,除此之外,,RTS/CTS流量控制和“分布式協(xié)調(diào)功能(distributed coordination function;DCF)”,,以及更上層的驅(qū)動程序、應用軟件,、各通信層之間的接口….等,,都要嚴格考慮在內(nèi)。不過,,本文將專注于回歸技術的探討,。

  碰撞的問題

  當兩臺裝置同時開始傳送數(shù)據(jù)時,它們將會先檢查纜線中是否有載波存在,,若載波有存在,,而且纜線是處于閑置狀態(tài),它們就會馬上傳送封包,。因為它們所發(fā)射的電子信號會彼此干擾,,這種干擾會造成“封包碰撞”的結果。碰撞會使封包內(nèi)的數(shù)據(jù)混淆不清,,致使接收到的封包無法還原成正確的數(shù)據(jù),。

  雖然,CSMA/CA和回歸都能解決碰撞的問題,,不過,,在功能上,它們是有差別的,。CSMA/CA是一種“競爭”(contention)通信協(xié)議,,它傾聽WLAN網(wǎng)絡,避免碰撞發(fā)生,。它和傳統(tǒng)的CSMA/CD(被以太網(wǎng)絡使用)不同,,CSMA/CD是在碰撞發(fā)生之后,,才起來處理后續(xù)的傳送作業(yè),。CSMA/CA則是防患未然,所以比較有助于網(wǎng)絡通信,。因為它在任何真正的數(shù)據(jù)被傳送之前,,會先在網(wǎng)絡上廣播(broadcast)一個信號,,傾聽是否有碰撞發(fā)生,同時告訴其它裝置不要廣播,。

  當發(fā)生碰撞時,,裝置必須等待一段時間,等纜線恢復閑置時,,才能再傳送,。不過,若兩個裝置

  同時再次發(fā)射信號,,則另一個碰撞又將再次發(fā)生,。為了避免這個情況發(fā)生,就必須采用“二進制指數(shù)回歸算法”來解決,。

  回歸的概念

  在碰撞之后,,再次嘗試發(fā)射信號之前,每一個傳送裝置必須等待一段時間,。不過,,如果它們的等待或延遲時間都一樣,則下次還是會有碰撞發(fā)生,。因此,,每個裝置必須選擇一個0到D的隨機數(shù),當成必須等待的時間長度,。D是標準的延遲時間值,。若又發(fā)生碰撞,則每個裝置會將之前所選擇的隨機數(shù)大小加倍,,這表示現(xiàn)在的隨機延遲時間是在0到2D之間,。如果又有另一個碰撞發(fā)生,則延遲范圍將在0到4D之間,。以此類推,。每碰撞一次,隨機延遲時間會以指數(shù)增加,,所以下次會發(fā)生碰撞的機率將會大幅降低,,而且重復回歸所花費的時間很短,可以忽略不計,。

  802.11的回歸機制

  802.11/DFWMAC的回歸機制和以太網(wǎng)絡的不完全一樣,,因為前者還牽涉到DCF。DCF是以CSMA/CA為基礎的通信協(xié)議,。DFWMAC整合了兩個協(xié)調(diào)功能—PCF和DCF,。PCF支持同步數(shù)據(jù)傳輸,DCF支持異步數(shù)據(jù)傳輸,。這兩個模式共享媒體頻寬,,以多時分工(time-multiplex)的方式,,將彼此的數(shù)據(jù)組合成一個“超大訊框(superframe)”的結構。

  利用訊框之間不同的間距(interframe space;IFS),,DCF和PCF可以并存,。由于具有PCF的橋接器(AP)的IFS比較小,因此它的通信優(yōu)先級會比處于DCF模式中的工作站高,。所以,,AP可以在CSMA/CA網(wǎng)絡上建立一個超大訊框。

  在沒有AP裝置的WLAN網(wǎng)絡環(huán)境之中,,存取數(shù)據(jù)要靠DCF,。一旦媒體閑置了一段特定的時間(DIFS),并且可以在“競爭窗口”(contention window;CW)的大小范圍內(nèi),,選擇一個隨機的回歸值當成延遲時間,。競爭窗口或回歸時間都是被分割成數(shù)個時槽(slot),每個時槽至少要包含:發(fā)射機開啟所需的時間+媒體傳播所需的時間+偵測忙碌的媒體所需的時間,。每個時槽的大小和實體層非常有關,。

  選擇最小延遲時間的工作站,將是最早存取媒體的;其它工作站則暫停它們的回歸定時器,,等待別人傳送完畢;而且,,在下一個周期內(nèi),繼續(xù)等待所剩余的延遲時間,。通常,,已經(jīng)等待很久的工作站,會比剛加入的工作站,,能更早存取媒體,。等待的時間愈久,獲得存取權的機率就愈高,。碰撞只發(fā)生在兩個或更多個工作站選擇了相同的時槽的時候,。若持續(xù)發(fā)生碰撞,它們必須重新競爭,,并使用以指數(shù)增加的CW值,,亦即,2倍的CW,、4倍的CW,、……,直到最大的CW限制值,。

  碰撞機率的分布

  下面我們來探討一下DFWMAC的碰撞機率,。不過,不對碰撞問題做完整的數(shù)學分析,只針對它的性質(zhì),,做判定和說明。仔細檢視CW,,和從CW選出的一個時槽的機率:假設有許多個工作站一起競奪媒體的存取權,,剛開始時,這種設計會使回歸時間的機率函數(shù)呈現(xiàn)平均分布,,每一個時槽的被選中機率是相同的,。

  在第二個周期之內(nèi),假設有一個工作站A獲得存取權,,其工作站在工作站A開始發(fā)射信號之前都會等待或延遲,,假設這個延遲時間是CWselected—這就是前面所介紹的“隨機延遲時間”。現(xiàn)在,,剩下的“競爭窗口”是從0到CW-CWselected,,剩余的工作站(除了工作站A以外的其它工作站)在0到CW-CWselected的范圍內(nèi)競爭。這范圍內(nèi)的時槽的被選中機率也是相同的,,因為它們是重新進行競爭之故,。

  如果這時有一個新工作站加入競爭;或者在前一個周期內(nèi),有兩個或以上的工作站發(fā)生碰撞,,它們將會在CW或2倍的CW或數(shù)倍的CW中選擇時槽,,它們選擇時槽的機率應該是較小的。直覺上,,新進者本來就要等久一點才能獲得存取權;至于發(fā)生碰撞的工作站的獲得存取權之機率,,應該比新進的工作站的獲得存取權之機率少一半才對。不過為了便于說明,,這里將新進的工作站和發(fā)生碰撞的工作站視為同類;此時,,它們的機率都遠小于其它剩余工作站的機率;而它們的機率的些微差異是可以省略不計的,其中,,時槽超過CW-CWselected范圍的被選中機率,,遠低于從0到CW-CWselected范圍內(nèi)的時槽被選中機率。請注意,,實際上,,新進的和碰撞重來的工作站之時槽被選中機率,占有0到CW-CWselected和CW-CWselected的完整CW范圍,。

  假設WLAN處于高負載的情況(一直有工作站離開,,也一直有工作站加入競爭,且離開和加入的數(shù)量是均衡的),,這時,,可以發(fā)現(xiàn)位于CW前面的時槽(即較早生成的時槽),具有比較高的被選中機率。因此,,時槽的被選中機率是一個遞減的階梯函數(shù)(staircase function),。

  不過,這會導致一種我們很不想看到的現(xiàn)象:愈可能被選中的時槽,,也愈可能被選中兩次或更多次,,所以它發(fā)生碰撞的機會也愈高。為了盡量避免碰撞的發(fā)生,,應該使每一個時槽的分布機率維持相等,。

  改良的回歸機制

  為了解決上述的問題,有許多方法可以采用,。其中一種方法是,,令剩余的工作站于每個周期,在完整的CW內(nèi),,選擇一個新的隨機回歸時間,。不過,這可能會造成某一個工作站都一直在等待存取的機會,,因為此方法并沒有限制最大的等待時間,。底下分別以兩種方法來解決這個問題,它們都企圖將新進的工作站和前一次競爭失敗的(剩余的)工作站之機率區(qū)分開來,。這兩種方法是:加權的選擇機率,、負載自適性(load adaptive)選擇。為了追求精確和精致,,必須使用簡要的數(shù)學觀念和方程式來說明它們,。
 

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權禁止轉載,。