ＷｉＭＡＸ網絡ＭＡＣ層接入算法研究

摘要：介紹了WiMAX網絡的PMP模式和Mesh模式，并比較了兩種無線信道共享模式的性能。同時也對Mesh網絡的集中式和分布式這兩種帶寬調度控制算法進行了廣泛深入的研究，提出了新的協調分布式算法（CDMSA），通過使用該算法來解決協調分布式Mesh網絡的信道時隙接入問題。

關鍵詞：WiMAX； Mesh； 集中式調度； 分布式調度

中圖法分類號：TP393．17文獻標識碼：A

文章編號：1001－3695(2007)01－0305－04

寬帶接入已成為當前接入Internet的主流方式。隨著網絡服務類型的增加和用戶對帶寬需求的日益增長，運營商必須能夠提供高速的、帶寬較大的網絡接入技術來滿足不同網絡應用和用戶需求，諸如視頻點播、視頻電話、在線游戲、家庭辦公、遠程醫療等。

當前運營商主要向用戶提供有線寬帶和無線寬帶這兩種Internet接入方式。有線寬帶接入必須部署Internet網絡到用戶終端，接入和實施的代價均較高。無線寬帶技術(Wireless DSL，WDSL)作為有線寬帶技術的一種補充，允許DSL運營商向那些難以進行有線寬帶接入或還沒有進行有線寬帶接入的用戶提供高速的Internet接入方式。現在世界上已經有很多地方開始向用戶提供高速的無線寬帶接入方式，如歐洲的寬帶無線接入網絡(Broadband Radio Access Networks，BRAN)、美國的本地多點分布式服務(Local Multipoint Distribution System，LMDS)[1]、多點多信道分布式系統(MultichannelMultipoint Distribution System，MMDS)[2，3]，以及IEEE 802.16[4]工作組提出的寬帶無線接入(Broadband Wireless Access，BWA)技術。無線城域網接口標準 (Wireless Metropolitan Area Networks，WMAN)，即全球微波接入互操作性(World Interopera￣bility for Microwave Access，WiMAX)，它的目標是確保各種品牌的無線接入設備能夠保持一定的兼容性和互操作性，加速IEEE 802.16標準的部署和實施過程，將現存的BRAN，LMDS，MMDS標準化[3]。

本文介紹了WiMAX網絡的拓撲架構和組成，對WiMAX網絡的Mesh模式及優點進行了分析，并分別對分布式和集中式兩種Mesh網絡的接入體系結構和調度幀結構進行了詳細的介紹。本文在分析了集中式和分布式Mesh體系結構的基礎上，提出了無線信道的協調分布式調度控制算法。

1WiMAX網絡及其拓撲架構

WiMAX由于其本身的高帶寬特性和易部署性注定成為解決“最后一里”的較優方案。當前IEEE 802.16a標準表明WiMAX主要使用有兩個工作頻段，即10GHz~66GHz頻段與2GHz~11GHz頻段。其中10GHz~66GHz頻段需要獲得使用許可，工作在視距范圍(Line Of Sight， LOS)，可以在50km的視距范圍內提供服務。而2GHz~11GHz頻段為許可頻段和免許可頻段，工作在非視距范圍(NonLine Of Sight， NLOS)，能在10km的非視距范圍內提供服務，對遠距離阻擋物有很強的穿透能力。WiMAX可采用非對稱的數據傳輸方式，上行鏈路的帶寬使用量顯著低于下行鏈路的帶寬使用量，能夠滿足基站覆蓋范圍內的用戶站的常規帶寬需求，做到了隨時隨地接入Internet。

在IEEE 802.16a標準中，WiMAX網絡是由基站(Base Station，BS)和多個固定用戶站(Subscriber Station， SS)組成的無線寬帶網絡。基站位于有線網絡與無線網絡之間，提供數據流的回程。當用戶站SS要傳送數據時，首先它要與各SS競爭傳輸時隙，只有獲得了基站BS的允許，SS才能夠上傳自己的數據。BS則將數據映射到相應的時隙里，傳輸給目標接收SS節點。

IEEE 802.16標準中定義了點對多點(Point to Multipoint， PMP)和Mesh兩種無線帶寬共享模式[5]。在PMP模式中，基站A對自己一跳范圍的各SS節點進行帶寬調度，即基站A同時與多個用戶站建立鏈接。用戶站又可以部署各種網絡接入方式來擴大WiMAX網絡的覆蓋范圍。如在用戶站端部署一個或多個802.11接入點(Access Point， AP)來建立一個無線局域網(Wireless LAN)或部署一個小型的有線局域網。另外一種模式就是Mesh模式。用戶站與自己相鄰的用戶站之間建立鏈接，構成了多點對多點(Multipoint to Multipoint，M2M)體系。圖1中的虛線就是一個M2M Mesh網絡。

圖1802.16 PMP，Mesh網絡基本結構

1．1Mesh網絡的介紹及其優點

Mesh模式在MAC層中存在兩種時隙調度方式，即集中式調度(Mesh Centralized Scheduling， Mesh_CS)和分布式調度(Mesh Distributed Scheduling， Mesh_DS)。如圖1中，用戶站與用戶站之間可以進行直接傳輸而不必通過基站來轉發，但是請求帶寬、時隙及頻率分配等控制信號還是要通過BS調度(在此圖中本文將基站作為BS)，這是一種基于BS的Mesh網絡，稱為集中式的Mesh調度。還有一種是在不需要中心控制站(BS站)鏈接的Mesh網，就像圖1中的用戶站與用戶站間可單獨地組成自己的Mesh網絡來進行通信，并且它們的控制信號由各節點間調用分布式調度程序或請求/發送機制來協調，我們稱它為分布式的Mesh調度。Mesh模式相對于PMP模式擁有更多的優點。

(1)高帶寬：無線通信的物理特性表明在短距離內的數據傳輸帶寬最高。隨著傳輸設備之間距離的增加，干擾和衰減等因素也會逐漸增強，導致數據丟失，數據的傳輸率急劇下降。在Mesh模式中，各個節點只與其鄰居節點進行通信，擁有較高的傳輸速率。

(2)覆蓋面積廣：PMP模式現在還不支持中間節點的接力。Mesh模式通過中間節點進行接力，可以極大地擴大基站信號的覆蓋范圍。

(3)穩健性：使用Mesh模式的無線網絡比PMP模式的無線網絡擁有更高的穩定性。在PMP模式中，基站作為網絡的中心節點，成為網絡穩定性的瓶頸。如果基站崩潰了，周邊的用戶站節點也同時失效。而當Mesh模式中的節點崩潰時，在源節點和目的節點間存在多條路徑可以選擇。

1．2Mesh網MAC幀結構

在IEEE 802.16中，Mesh模式采用了時分復用幀結構，如圖2所示。Mesh模式使用的幀由長度固定的控制子幀或數據子幀組成。控制子幀分為調度控制子幀和網絡控制子幀。

圖2IEEE 802.16 Mesh網MAC幀結構

控制子幀周期性地在各個SS節點之間進行廣播。當SS節點想要加入網絡時，它將會收到當前網絡中SS節點提供的網絡同步和初始化的信息。同樣，當SS節點想要退出網絡時，它需要將其退出信息通過廣播給網絡中的其他節點。各個SS節點利用數據幀中的TDM部分來傳輸數據。通過節點之間使用調度控制子幀來決定無線鏈路的帶寬資源分配，即將具體的時隙分配給網絡中的各個SS節點或SS節點通過獲取該幀來獲得發送和接收數據的時隙。

2Mesh模式的調度方式及其算法

Mesh模式主要有兩種調度模式，即集中式調度與分布式調度，其幀結構如圖3所示。由2symbols的前導碼，集中式調度信息或分布式調度信息，保護symbol組成了一個調度單元。

圖3IEEE 802.16Mesh網的兩種調度子幀結構

在Mesh模式中每一個SS節點與BS一樣既是數據接收端又是中轉發送端。各SS節點為其頻譜覆蓋范圍內的網絡設備提供數據上傳和下載。當鄰居SS節點需要傳輸數據時，它將使用特定的調度機制與其鄰居SS節點競爭時隙或通過Mesh BS集中調度時隙。SS節點只有獲得時隙后才能進行數據傳輸。

2．1集中式Mesh網及其帶寬調度

在集中式Mesh網中，Mesh BS對距離自己一定跳數的SS節點進行帶寬調度。Mesh_CS與PMP模式獲取信道資源的方式是相同的，但是它們也有不同之處。在PMP模式中所有的SS節點的所有數據必須通過BS才能進行傳輸。而在Mesh_CS中SS節點在獲得Mesh BS的傳輸時隙后可以不通過Mesh BS，而直接與其他節點進行通信。在Mesh_CS中，SS節點可通過其他SS節點中繼調度信號給Mesh BS節點，如圖1中的用戶站g通過用戶站a中繼到基站A。當SS節點之間需要傳輸數據時，它將通過公用調度信道發送一個包含集中式調度請求的子幀給Mesh BS，即802.16標準中的MSHCSCH。Mesh BS收到各個SS的帶寬請求時隙后，它將查看存儲在本地數據庫中的時隙分配表。當此時隙沒有被其他SS節點請求或使用時，Mesh BS將同意該時隙請求，并響應一個包含有具體分配時隙的報文，廣播給各SS節點。如果請求節點不在Mesh BS的頻譜覆蓋范圍內，該響應信息將通過鄰居SS節點中繼給該請求SS節點。SS節點獲得發送時隙后將與通信目標SS建立鏈接，進行數據傳輸。

Mesh_CS網的優點是簡單性和易實現性，通過Mesh BS進行調度可避免信道使用時發生沖突。但是對于距離網關Mesh BS多跳的SS節點，Mesh_CS調度方式只能有一個SS節點具有傳輸數據的機會，信道利用效率明顯降低。因此Mesh_CS的調度方式對于距離Mesh BS一跳或兩跳的SS節點是很適合的，對距離Mesh BS多跳的SS節點的信道利用率和協調性就會很差。當中心站Mesh BS崩潰時，整個網絡就不能再繼續進行帶寬調度。因此系統的穩定性不是很好。

2．2分布式Mesh網及其帶寬調度

在分布式Mesh網中，網絡帶寬的調度決策由部分或所有節點通過特定的方式進行協商，無須經過Mesh BS。Mesh_DS擁有較高的穩定性和可擴展性。節點能夠根據自身負載來動態調整節點的接入算法和帶寬分配方式。在分布式Mesh網中Mesh BS與SS節點的功能是一樣的，唯一的不同就是Mesh BS節點會與有線網絡進行鏈接。在本文中它們均被認為是SS節點。根據帶寬調度過程中的請求方式不同，Mesh_DS的MAC層帶寬調度方式可分為協調分布式調度與非協調分布式調度。

2．2．1協調分布式調度

當SS節點需要傳輸數據時，它必須首先獲得信道時隙的使用許可，即它要通過公共控制信道向距離自己k跳范圍的鄰居節點發送請求發送幀RTS來獲得某個時隙或多個時隙的使用許可。當且僅當該節點k跳范圍內的所有SS節點均不使用此時隙時，請求節點才能獲得此時隙的使用權。如果鄰居節點同意該節點使用此時隙時，鄰居節點將保持沉默，不會作出任何響應。當其他鄰居節點也想使用這些時隙時，該節點會在一定時間間隔內向請求節點返回確認幀，通知請求節點它們在競爭此時隙時發生了沖突，然后各自調用截短二進制退避算法再隨機選擇一個或多個時隙來重新請求時隙。具體的分布式Mesh 網信道請求算法（Coordination Distributed Mesh Schedule Algorithm， CDMSA）如下：

Mesh Distributed schedule algorithm

If (the CID is located in the database)

{If (the flag=0)

{Judge the request time slot

If (disagree the request time slot)

Transmission the disagree frame to the requester

Else

Silence and set the flag=1 and transmission the request frame to the neighbors

}

Else

{Judge the request time slot

If (disagree)

Transmission the disagree frame to the sender

Else

Silence

}}

Else

Measurement and judge whether a new neighbor wants to joining and call the initiation procedure

在分布式協調調度算法中每個節點均將在本地數據庫里維持一個鄰居節點的鏈接標志(Connection Identity， CID)數據表。圖4對協調分布式調度算法進行了說明，節點A想要給節點D發送數據，首先它通過專用信道向在自己一跳范圍的節點B與D等節點發送請求時隙幀，如通過廣播；然后節點B會對此請求幀中Flag標志進行判斷。在這里我們認為k=2，Flag如果為0，則表示此請求是來自于鄰居節點，當它對被請求的時隙允許時，它就轉發此請求給距請求節點兩跳范圍的節點即自己的鄰居節點。否則可以判斷為是來自于兩跳范圍的節點，它只作出判斷允許還是不允許。允許就會保持沉默，不然就會回送一個幀給發送節點。圖4中，由于節點A想獲得的時隙和節點C想要的時隙沖突，所以節點C需再通過D點返回一個幀告訴A點(雙箭頭所示)。節點C與A就需要調用截短二進制退避算法來隨機選擇另外的時隙來請求。

圖4協調分布式調度時隙分配原理

當Mesh_DS中有很多節點時，就會出現如圖4的情形，為了簡單化本文只列出少數節點，即節點B在節點A的一跳范圍同時也在節點F的兩跳范圍，當A節點向B節點發送請求幀。而節點F也想發送數據，它也會給距離自己一跳和兩跳范圍的節點發送請求幀，如節點F通過節點G向B發送請求幀。所以B節點會收到兩個請求幀，因此對于Mesh_DS系統來說整個網絡節點的時隙同步就顯得非常重要。然而這里面臨著一個問題就是當在鄰居節點中同時有多個節點請求時隙時，請求信道使用也會產生沖突，即會出現無線網絡中的隱藏終端和暴露終端問題[6]。解決此類問題可采用802.11MAC網絡中的RTS/CTS解決方法，發送節點在發送請求時隙之前與接收鄰居節點進行一次控制消息握手交換，以短消息的方式通知鄰居節點，它即將進行接收。

2．2．2非協調分布式調度

分布式帶寬調度的另一種方式是非協調分布式調度（NonCoordination Distributed Mesh Schedule Algorithm， NCDMSA）。它與早期的ALOHA時隙系統相似，節點有數據要發送它就直接發送，在傳輸前無須對自己鄰居節點是否在發送數據進行幀聽。當數據成功地被發送時，發送節點將會收到一個從接收節點發送的ACK確認幀。如果數據沖突或損壞，發送站點也會調用截短二進制退避算法再隨機選擇一個時隙來發送數據。如果傳輸過程再次出現沖突，發送節點繼續隨機選擇時隙發送數據。當沖突的次數達到特定的閾值時，發送節點就放棄此次數據傳輸。非協調分布式調度方式的信道利用率會隨著節點密度增加而顯著降低。

3算法仿真

本節對CDMSA算法的性能進行仿真，并與非協調式調度方式算法NCDMSA進行比較，得出算法的接入平均成功率和平均延遲。

圖5給出了CDMSA算法和NCDMSA算法的平均接入成功率。圖中可以看出，隨著SS節點數目的增加，兩種算法的接入成功率均會逐漸增加。當活動SS節點數量為20時，平均接入成功率分別為0.2和0.24；當活動SS節點數量達到50時，接入成功率會增加為0.28和0.36。在整個仿真過程中可以看出CDMSA算法比NCDMSA擁有較高的接入成功概率。兩種調度算法在接入過程中的平均延遲在圖6中給出。可以看出，CDMSA算法的接入延遲隨著節點數量的增加緩慢增長，而NCDMSA算法的接入延遲增加較快。在NCDMSA算法中，當活動SS節點較多時，由于各個SS節點再次請求帶寬資源的時間相互獨立，從而增加了沖突產生的概率，導致接入延遲增加。可以得出CDMSA算法相對與NCDMSA算法擁有較低的接入延遲。

4總結

本文介紹了WiMAX網絡及其常見的兩種網絡拓撲結構，即PMP與Mesh。在對PMP和Mesh模式的介紹過程中討論了兩種無線信道共享模式中的帶寬分配問題。本文針對Mesh模式中的信道使用方式進行了重點討論，介紹了Mesh網絡的幀結構和MAC層的兩種信道競爭方式，即集中式和分布式接入調度算法，并提出了協調分布式CDMSA算法， 及其與非協調分布式的模擬仿真，證實了CDMSA在接入概率和延遲方面均有比較好的性能。

參考文獻：

［1］Mahonen P， Saarinen T， Shelby Z， et al. Wireless Internet over LMDS: Architecture and Experimental Implementation [J]. IEEE Communications Magazine， 2001，39(5):126132.

［2］Nordbotten Agne. LMDS Systems and Their Application [J]. IEEE Communications Magazine， 2000，38(12):150154.

［3］Paul Piggin. WiMAX INDEPTH [J]. IEE Communications Engineer， 20-04，2(5):3639.

［4］Eklund Carl， Marks Roqer B， Stanwood Kenneth L. IEEE Standard 802.16: A Technical Overview of the Wireless MAN Air Interface for Broadband Wireless Access [J]. IEEE Communications Magazine，2002，40(6):98107.

［5］IEEE Std 20-04， IEEE Standard for Local and Metropolitan Area Networks——Part 16: Air Interface for Fixed Broadband Wireless Access Systems [S].

［6］鄭相全，等.無線自組網技術實用教程[M]. 北京:清華大學出版社，20-04.72111.

作者簡介:

周志東(1977），男，湖南衡山人，碩士研究生，主要研究方向為無線網絡；杜文峰(1977），男，博士研究生；賈維嘉(1957），男，中南大學教授，香港城市大學副教授，博導，博士。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文