一種基于多層優先級和差分服務機制的CSMA/CA改進算法

陳 濤1，朱馬鋒

(1.成都理工大學，四川 成都 610000；2.重慶郵電大學，重慶 400065)

·計算機軟件理論、技術與應用·

一種基于多層優先級和差分服務機制的CSMA/CA改進算法

陳 濤1，朱馬鋒2

(1.成都理工大學，四川 成都 610000；2.重慶郵電大學，重慶 400065)

針對CSMA/CA算法的回退指數變化固定、對第2次CCA檢測信道為忙時的處理不當這2個不足，提出一種基于多層優先級和差分服務機制的時隙CSMA/CA算法。通過優先級設定不同的回退指數BE，采用CCA2失敗時再執行1次CCA的方法來克服以上2個不足。OPNET仿真結果表明，該算法在吞吐量、網絡時延、成功接入信道概率方面優于原CSMA/CA算法。

時隙CSMA/CA；多層優先級；差分服務機制；OPNET

IEEE802.15.4 標準定義了媒體訪問層(MAC)和物理層[1]，CSMA/CA算法是媒體訪問層的關鍵技術之一[2]。對于CSMA/CA算法，學者進行了不斷地研究[3-9]。文獻[3]對執行第2次CCA做了重大分析，增加了CW值，使得當第2次CCA檢查信道為忙時，不是立即重新執行算法，而是再執行1次CCA，增大了信道的接入概率。文獻[6]通過改變BE的值來提高接入概率。文獻[7]采用幀裁剪和優先級調度策略，使高優先級的數據在執行CCA時只需要1次，而低優先級的數據需要2次，這有效地提高了包成功發送的概率。文獻[8]采用競爭窗口和回退指數的差分思想來優化時隙CSMA/CA算法。

通過這些文獻可知，現有的基于優先級和差分服務機制的CSMA/CA算法只是針對不同的數據類型的優先級，在同一個數據類型中，并沒有再次引入優先級和差分服務機制。例如：文獻[8]認為來自安全系統和醫學設備的傳感器節點的數據要比來自TV、冰箱等普通設備的數據具有高的優先級；文獻[10]認為命令幀具有高優先級，數據幀為低優先級。這些優先級都是針對不同的幀類型，都是在執行CSMA/CA算法之前由上層指定，而不是在算法過程中動態分配。本文對執行CSMA/CA算法中發生碰撞的情況做了詳細分析，并在此基礎上引入優先級和差分思想以解決原CSMA/CA算法存在的2個主要缺陷。

1 時隙CSMA/CA機制

1.1時隙CSMA/CA機制

IEEE802.15.4定義了一種超幀結構，如圖1所示。超幀結構包括信標幀、活躍部分和非活躍部分[1]。根據屬性macBeaconframeOrder(BO)、macSuperframeOrder(SO)和aBaseSuperframeDuation的值按照式(1)來確定信標的周期BI(beacon interval)和超幀的活動部分長度SD(superframe duration)。

BI=aBaseSuperframeDuation×2BO;

SD=aBaseSuperframeDuation×2SO;

0≤SO≤BO≤14。

(1)

在活躍部分，IEEE802.15.4協議提供了一種GTS機制，在GTS內節點無須競爭，這些GTS有網絡協調器分配。

圖1 超幀結構簡圖

所有節點進行信息傳輸之前都要使用CSMA/CA算法進行信道的競爭。CSMA/CA算法涉及3個重要參數：競爭窗口CW、回退指數BE和回退次數NB。步驟1：對網絡參數(NB、CW、BE)進行初始化。步驟2：在[0,2BE-1]之間隨機選擇幾個作為退避周期數。步驟3：在退避周期邊界處執行CCA。步驟4：如果這時信道為空，就將CW的值減1，判斷其是否為0，若為0則競爭成功，若不為0返回步驟2；如果信道為忙，就將CW置2，NB和BE加1，但是必須保證BE為BE+1和最大回退指數aMaxBE中的最小者。步驟5：判斷NB有沒有達到最大重傳次數，如果達到則競爭失敗，如果沒有則返回步驟2。流程如圖2所示。

圖2 CSMA/CA算法流程圖

1.2 CSMA/CA機制的缺陷

時隙CSMA/CA算法受4個變量影響：最小回退指數(macMinBE)、最大回退指數(aMaxBE)、初始值CW和最大回退次數(macMaxCSMABackoffs)。這4個參數的改變會影響CSMA/CA算法的性能，例如平均網絡時延會隨著macMinBE的增大而變大[11]；因此，選取合適的參數可以優化算法的性能。其不足主要體現在以下2方面。

1)回退指數變化固定。在執行CSMA/CA算法的過程中回退指數成線性變化，每次檢測到信道為忙就會將回退指數加1，但是這樣往往不適應一些特殊情況；因為當網絡狀態已經很好時，隨著回退次數的增加，仍需要回退過多的周期，這樣無疑浪費了資源，增大了網絡的時延。另外，對于本文提到的具有優先級的幀，回退指數仍按照線性變化，這樣就不利于具有優先級幀的優先發送。

2)對第2次CCA檢測信道為忙時的處理不當。在使用CSMA/CA算法中，CCA信道必須連續2次都為閑時才能發送數據，這2次CCA稱為CCA1和CCA2。當出現CCA1信道為閑、CCA2信道為忙時，原算法就會重新開始執行，直到連續2次CCA檢測為閑時才能發送數據，這無疑浪費了1次CCA信道為閑的機會，增加了執行CCA的次數。

CCA2檢測為忙的情況主要由2個原因[12]造成。 1)CCA2檢測與數據幀發送碰撞。當執行CCA2時，這時剛好有數據發送，所以信道檢測為忙。2)CCA2檢測與確認幀(ACK)的碰撞。當執行CCA1時，剛好有數據發送完畢正等待確認幀的到來，這時信道為空，當執行CCA2時，剛好確認幀開始發送，這時CCA2檢測為忙。如圖3所示，假設此時網絡中有3個節點：Note1、Note2、Note3。Note1 連續執行2次CCA，檢測信道都為閑，然后開始發送數據，在Note1發送數據期間，Note2 執行CCA，檢測信道為忙。等Note1 發送完數據，要等待確認幀的發送，此時Note3 執行CCA1，檢測信道為閑；但等Note3 執行CCA2時剛好確認幀開始發送，檢測信道為忙。對于第1種情況因為不知道數據幀長度所以不確定接下來幾個時隙后信道空閑；但是對于第2種情況，因為ACK只有1個時隙，所以只要等2個時隙后信道就為閑，此時就可以發送數據。

圖3 由ACK 引起的CCA2 信道為忙的示意圖

2 基于幀優先級、內部優先級和差分思想的CSMA/CA算法

優先級服務機制是指被網絡標記的具有高優先級的數據幀優先發送。優先發送可以通過改變競爭窗口、回退指數來實現。優先級的大小由MAC層或者上層設置。

差分服務機制分為競爭窗口差分服務機制和回退指數差分服務機制[13]。競爭窗口服務機制是指對于不同的優先級采用不同的競爭窗口大小，即執行不同的CCA；回退指數差分服務機制是指對于不同的優先級采用不同的回退指數。

2.1差分服務機制

文獻[10]以命令幀作為高優先級，本文稱之為外部優先級，其參數用macMinBEHP、macMaxBEHP和CWHP表示；數據幀作為低優先級，本文稱之為內部優先級，其參數用macMinBELP、macMaxBELP和CWLP表示。為表示數據幀內部的優先級，即執行CCA時第1次信道為空，第2次為忙的節點，本文用macMinBELHP、macMaxBELHP、CWLHP和macMinBELLP、macMaxBELLP、CWLLP分別表示內部高優先級和內部低優先級數據。對于數據幀內部的優先級并不是由MAC層或者上層指定，而是在運行CSMA/CA算法時，執行CCA2后由算法臨時指定，其優先級作用時間僅僅為此節點傳輸信息結束，在以后的競爭中它并不一定具有內部高優先級；但是從CSMA/CA算法來看它好像和外部優先級的數據幀一樣由MAC或者上層指定，如圖4所示。

圖4 優先級和差分服務機制

文獻[10]設定了不同的仿真參數來驗證它們對網絡性能的影響，表明在沒有隱藏節點的情況下，當macMinBEHP=macMinBELP=2，macMaxBEHP= macMaxBELP =5，CWHP=2，CWHP=3時較合理。文獻[12]分析并驗證了當執行1次CCA時對系統性能的提高。結合對內部優先級的考慮，本文對參數的設置如表1所示。對于競爭窗口CW，值越大表示優先級越高，值越小表示優先級越低，所以具有外部優先級的幀優先級最高，然后是具有臨時內部優先級的幀，最后是普通幀。

表1 網絡參數

2.2改進的CSMA/CA算法步驟

由以上分析可知，幀優先級由MAC層或者上層指定，對于外部優先級的幀來說，優先發送的權利可以通過改變競爭窗口次數，即改變CCA檢測次數來達到，在此種情況下，只需要執行1次CCA，同時不減少退避周期，從而提高外部優先級幀的接入信道概率。對于內部優先級的數據幀，可以通過改變其原先的優先級來達到其優先競爭的目的，從而保證執行CCA1信道為空后，暫時賦予此節點有內部優先級。另外，改變回退指數BE可以改變其接入信道的概率，對于優先級高的可以減少回退指數，優先級低的可以增大回退指數，從而區分不同優先級的信道競爭情況。對于第2種缺陷，如果是和確認幀碰撞，因為已經知道ACK的長度，節點只需延時1個時隙周期即可；如果是和數據碰撞，因為無法確定數據的長度，所以只能隨機延時幾個時隙周期。算法流程圖如圖5所示。

步驟1：判斷是否為優先級包。若是，執行步驟2，若不是執行步驟3。

步驟2：初始化NB=0，CW=1，然后執行步驟4。

步驟3：初始化NB=0，CW=3，然后執行步驟4。

步驟4：初始化BE=macMinBE，然后定位退避周期邊界。

步驟5：在0～2BE-1之間隨機選擇幾個作為退避周期。

步驟6：在退避邊界進行信道檢測CCA。如果信道為空閑，則進入步驟7；如果信道忙，則進行步驟8。

步驟7：將CW減1，然后判定CW是否為0。若為0，成功；否則回到步驟5。

步驟8：判斷是否為優先級包。若是執行步驟12；若不是執行步驟9。

步驟9：判斷CW值是否為2。若是執行步驟10；若不是執行步驟11。

步驟10：將CW值減1，然后退避1個周期，執行步驟6。

圖5 改進算法流程圖

步驟11：判斷CW的值是否為1。若是執行步驟13；若不是執行步驟14。

步驟12：CW=1，NB值加1，BE不變，然后執行步驟15。

步驟13：CW=2，NB值加1，BE=min(BE+1,aMaxBE)，然后執行步驟15。

步驟14：CW=3，NB值加1，BE=min(BE+1,aMaxBE)，然后執行步驟15。

步驟15：判定NB是否大于最大退避次數macMax-CSMABackoff。如果大于，則失敗；否則回到步驟5。

3 仿真

為比較方便，本文提出的基于外部優先級和內部優先級的差分CSMA/CA算法用PP-CSMA/CA表示，對于基于外部優先級的CSMA/CA算法用P-CSMA/CA表示。用OPNET[14-15]網絡仿真軟件進行仿真。

圖6 吞吐量與普通節點的關系

圖6顯示的是網絡節點數目對吞吐量的影響。可以看出，隨著網絡中節點數目的增多，吞吐量的變化并不明顯。無論網絡負載是由多少個節點產生，即10、20、30、50或者100個節點，網絡的吞吐量僅與載荷G有關；但是，對于一個給定的網絡負載G，每個節點產生的載荷與節點數成反比。如果網絡中的載荷保持不變，節點個數對于網絡的吞吐量幾乎沒有影響。增加了優先級機制的算法要優于原算法。

圖7 成功接入信道的概率與網絡負載G的關系

圖7示出的是負載與成功接入信道概率的關系。可以看出，引入優先級機制的算法要優于原算法， PP-CSMA/CA算法的信道接入概率要優于P-CSMA/CA和原CSMA/CA算法。PP-CSMA/CA算法有效地考慮了發送碰撞的各種情況，特別是對CCA2發送碰撞的情況做了重點的分析，并對原算法出現的2個主要缺陷做了相應的改進，從而增加了節點接入信道的概率。當節點少的時候，成功接入概率相差不大，隨著負載的增加，其相差增大。這是因為，當負載小的時候，網絡還沒有達到飽和狀態，信道接入成功率都很高，當負載較大時，網絡達到飽和狀態，此時具有優先級的數據包因為其競爭窗口以及回退指數較小，就會優先競爭到信道，其成功接入信道的概率就會增大。

圖8示出的是網絡負載對平均網絡時延的影響，其中虛線表示命令幀網絡時延，實線表示數據幀網絡時延。對于數據幀時延，原CSMA/CA和PCSMA/CA算法大致一樣，這是因為外部優先級只是針對具有優先級的命令幀，并不對其他自身有影響。相同原因還表現在當引入內部優先級時對命令幀的影響很小上。另外，P-CSMA/CA算法在時延上要優于其他2種算法。當負載較小時，時延相差不是很大，當負載較大時，其相差會增大。

圖8 平均時延與網絡負載的關系

4 結論

本文在分析了已有的基于優先級和差分服務思想的CSMA/CA算法缺點的基礎上，提出一種基于外部、內部優先級和差分服務的CSMA/CA算法，通過選取合適的網絡參數、改變競爭窗口的大小和回退指數來區分不同的優先級，以達到良好的網絡效果。仿真驗證的結果表明，在吞吐量、網絡時延和節點成功接入信道的概率方面，本文算法有很好表現。下一步研究重點是節點能耗和根據網絡狀況動態調整網絡參數方面。

[1]IEEE-TG15.4.Part 15.4: Wireless Medium Access Control(MAC)and Physical Layer(PHY)Specification for Low Rate Wireless Personal Area Networks(LR-WPANs)[S].2006.

[2]RAMACHANDRAN I,DAS K A,ROY S. Analysis of the Contention Access Period of IEEE802.15.4 MAC[J].ACM Trans on Sensor Networks,2007,3(1):1-29.

[3]CHI-MING WONG,RUER-LUNG LAI , I-TING LAI. An Enhanced Carrier Sensing Algorithm for IEEE802.15.4 Low-Rate Wireless Sensor Networks[J].Industrial Electronics & Applications (ISIEA),2010,3(5):10-15.

[4]Jianhua He,Zuoyin Tang,Hsiao-Hwa Chen,et al. An Accurat and Scalable Analytical Model for IEEE802.15.4 Slotted CSMA/CA Networks[C]//IEEE Transactions on Wireless Communication. Singapore： IEEE, 2007:899-904.

[5]LEE B H , WU H-K . Study on a Delayed Backoff Algorithm for IEEE802.15.4 Low-Rate Wireless Personal Area Networks[J].The Institution of Engineering and Technology(IET)Communications,2009,3(7):1089-1096.

[6]吉城，徐友云，鄭寶玉.基于IEEE802.15.4 退避算法的改進機制[J].信息技術,2008 (8):8-12.

[7]KIM T,CHOI S. Priotity-based Delay Mitigation for Event Monitoring IEEE802.15.4 LR-WPANs[J]. IEEE Communications Letters,2006,10(3):213-215.

[8]KIM M,KANG C H. Priotity-based Service-differention Scheme for IEEE802.15.4 Sensor Networks in Nonsaturation Environments[J]. IEEE Transations on Vehicular Technology,2010,59(7):3524-3535.

[9]NDIH E D N,K N De M G. An Analytical Model for the Contention Access Period of the Slotted IEEE802.15.4 with Service Differentiation[C]// Communications,2009(ICC’09),IEEE International Conference on. Dresden： IEEE, 2009:1-6.

[10]ANIS KOUBAA,MARIO ALVES,Bilel NEFZI,et al. Improving the IEEE802.15.4 Slotted CSMA/CA MAC for Time-Critical Events in Wireless Sensor Networks[C]//Proceedings of the Workshop of Real-time Networks. Shenzhen： IEEE, 2006:1-6.

[11]ALVER A K M, TOVAR E. A Comprehensive Simulation Study of Slotted CSMA/CA for IEEE802.15.4 Wireless Sensor Network[C]//The 6thIEEE International Workshop on Factory Communication Systems(WFCS2006). Torino： IEEE, 2006,183-192.

[12]PATRO R K, MANIK M, RAINA G V,et al. Analysis and Improvement of Contention Access Prtocol in IEEE802.15.4 Star Network[C]//Mobile Adhoc and Sensor Systems, IEEE Internatonal Conference on. Pisa： IEEE, 2007: 1-8.

[13]陳金，樊曉平，劉少強,等. 非飽和狀態下時隙CSMA/CA機制改進與性能分析[J]. 計算機工程與應用, 2012,48(30):140-146.

[14]PETR JURCIK, ANIS KOUBAA,MARIO ALVES. A Simulation Model for the IEEE 802.15.4 Protocol: Delay/Throughput Evaluation of the GTS Mechanism[C]// The 07th IEEE International Symposium on Modeling,Analysis and Simulation of Computer and Telecommunication Systems(MASCOTS’07). Istanbul：IEEE，2007：109-116.

[15]吳志玲，靳鴻，馮彥君. 基于OPNET 的信道接入協議網絡性能研究[J]. 伺服控制, 2012 (2):79-81.

(編校：饒莉)

AnImprovementAlgorithmofSlottedCSMA/CAwithServiceDifferentiationandPriorityMechanism

CHEN Tao1,ZHU Ma-feng2

(1.ChengduUniversityofTechnology，Chengdu610000China；2.ChongqingUniversityofPostsandTelecommunications,Chongqing400065China)

There are two shortages exiting in CSMA/CA: the backoff exponent(BE) increases linearly and it perform not well in the case of CAA2 detected being busy.In this paper, a kind of CSMA/CA algorithm with multi-level priority strategy and service differentiation mechanisms is proposed. Two problems are overcome with different BE based on priority strategy and performing the CAA again after the CCA2 failed slot. Results of experiment on OPNET platform show that the proposed algorithm performs better than the original one in aspects of the throughput, network delay and the probability of successfully access to channel.

slotted CSMA/CA; multi-level priority; service differentiation mechanism; OPNET

2014-04-19

國家自然科學基金“基于物聯網技術的呼吸、脈搏異變及跌落的實時檢測與報警的關鍵技術研究”(61171190)。

陳濤(1988—)男，碩士研究生，主要研究方向為網絡通信。E-mail:1991920158@qq.com

TP212;TN929.5

：A

：1673-159X(2015)02-0016-6

10.3969/j.issn.1673-159X.2015.02.004