多優先級無時隙CSMA/ CA算法研究

李 亮，張君利，楊 侃

(中國兵器工業集團第214研究所，江蘇 蘇州 215163)

多優先級無時隙CSMA/ CA算法研究

李 亮，張君利，楊 侃

(中國兵器工業集團第214研究所，江蘇 蘇州 215163)

IEEE802.15.4的無時隙CSMA/CA算法沒有對數據進行分流的能力，基于此，提出了一種針對帶有多優先級數據處理的無時隙改進算法。改進后的算法會對高優先級數據采取減少退避計數器計數和碰撞窗寬的策略，對不同優先級的待發數據采取相應的處理方式。算法通過接入網絡延時和網絡吞吐量來反映數據在網絡中的優先級別；同時引入數據發送的接入概率，提出接入-吞吐積概念作為評價算法優劣的標準。引用馬爾可夫鏈模型對算法進行了分析，并使用MATLAB軟件進行仿真。

接入-吞吐積；退避次數；退避指數；碰撞窗寬；無時隙

0 引言

無線傳感器技術發展迅猛，標準CSMA/CA算法已不能滿足數據多元化要求。CSMA/CA算法是IEEE802.15.4的MAC協議層核心算法。短距離無線通信協議為了避免信息碰撞，在MAC層設計了CSMA/CA算法，而有線通信協議則采用CSMA/CD算法，具體介紹可參見文獻[1]。CSMA/CA算法全稱為：帶沖突避免的載波偵聽多路訪問。顧名思義，該算法的核心即在發送數據前延時一段時間再發送數據，以避讓其它節點發送的數據，從而避免沖突，CSMA/CA的執行步驟和介紹詳見文獻[2]和文獻[3]。

標準的CSMA/CA算法沒有數據的優先級分區服務，網絡節點對要發送的數據不分流，所以有學者提出了基于優先級的CSMA/CA算法作為對CSMA/CA算法的優化和改進。在CSMA/CA算法中有3個重要參數，分別為退避指數BE、退避次數NB和碰撞窗寬CW，參見文獻[2]。對CSMA/CA算法的改進將從這3個參數入手，以實現多優先級的數據分流。每一種優先級都與它相應的參數BE、CW和最大退避次數相匹配，它們是一一映射的。本文引入了常用的馬爾可夫鏈模型，引入兩個重要的變量——吞吐量和接入延時。本文建立的模型放棄了匯聚節點概念，設定每個節點都是平等的，這兩個物理量作為權衡數據優先級的重要依據，使用數學軟件MATLAB對本文模型同標準CSMA/CA模型進行仿真驗證，從而得出相應結論。

1 無時隙CSMA/CA算法

CSMA/CA算法分為時隙和無時隙兩類，兩種方式的根本區別在于是否有同步機制，有時隙的算法含有同步機制，參見文獻[1]。本文對無時隙CSMA/CA算法進行研究。

無時隙CSMA/CA算法工作機理：當網絡節點準備發送數據時，先會延時一段時間，檢測信道是否空閑。若判斷信道為空閑，則發出信號RTS，RTS信號包括發射端的地址、接收端的地址、下一筆數據將持續發送的時間等信息。接收端接收到RTS信號后，將響應短信號CTS，CTS信號包含RTS記錄的持續發送時間。當發射端接收到CTS包后，隨即開始發送數據包。接收端接收到數據包后，檢測校驗包中的CRC數值是否正確。若正確，接收端響應ACK包，告知發射端已成功接收數據。發射端長時間沒有收到接收端的ACK包時，將認為包在傳輸過程中丟失，會重新發送包[1]。

CSMA/CA算法依賴的參數有BE、NB和CW，其中BE為退避指數，退避計數器的計數值由BE決定；NB為退避次數，用來記錄待發送數據退避的次數；CW為碰撞窗寬，表明節點發送數據前監測信道(CCA)空閑的次數[2-3]。

如果有數據要發送，網絡節點選擇無時隙模式和非電池延長模式，參數初始化BE=MaxMinBE，CW=2，NB=0。由于沒有時隙，所以算法不需要定位時隙邊緣。節點一旦有數據要發送則立刻執行退避算法。節點延時一段時間再執行信道檢測，等待的那段時間稱為退避時間，退避時間由退避計數器確定，退避計數器的計數值backoffcounter從0到2BE-1之間的整數中隨機選出。隨后每隔一個單位時長退避計數器減1，直到退避計數器減至0則表示退避時間已滿。開始執行CCA，如果CCA的結果表明信道空閑則判定CW是否為0，如果不為0，數據將再次延時一段時間后檢測信道是否空閑。如果信道仍然空閑且此時CW為0時則發送數據；如果信道忙，則執行CW=0，NB=NB+1，即數據退避次數需要加1，BE=min{BE+1,macMaxBE}(下次退避時間就有可能長一些)。最后檢測NB，如果NB已經大于最大退避次數，則舍棄發送該數據；否則就使用更新后的參數執行退避，檢測信道后再次嘗試發送數據，直到放棄數據發送或數據發送成功。時隙CSMA/CA算法流程如圖1所示。

圖1 時隙CSMA/CA算法流程

2 多優先級CSMA/CA算法

網絡平均吞吐量和平均接入延時概念：吞吐量Sthr指網絡中的所有節點單位時間成功發送的數據總數[4]，網絡的平均吞吐量S則是總數據量除以網絡的節點總數。

(1)

M表示整個網絡中的發送節點數。

接入延時T指數據從發出到發送成功所用的時間[5]。平均接入時延Tave是所有已發送的數據包平均接入延時(單位為s/bit)。

(2)

網絡節點發送數據時，總是期望高優先級數據能夠先發送，低優先級數據避開高優先級數據。本文建立的多優先級無時隙CSMA/CA模型將對參數BE、NB和CW進行多選化處理，因而高優先級數據的接入延時更短，在宏觀上反映為：如果網絡中只有一種優先級別的數據傳輸，那么網絡的平均數據吞吐量將會提高。標準的無時隙CSMA/CA算法參數CW為1，此算法卻設定沒有優先級的數據參數CW為2；而對于優先級更高的數據甚至可以將BE固定為一個常量，在統計學上表現為退避時長的期望值一定，優先級最高的數據是前面兩種情形的疊加。第NB次退避時間的期望值Tbackoff為：

(3)

Tslot表示一個單位時長，BE是關于NB的函數，Tbackoff是關于BE的函數，且具有單調遞增特性。圖1為多優先級策略的CSMA/CA算法流程，設優先級1數值化為Q1，Q1=1表示數據具有優先級別1的屬性，Q1=0表示數據不具有優先級別1的屬性；優先級2可以數值化為Q2，Q2=0表示優先級別2的最低屬性，Q2=k為優先級2的最高屬性。所以數據總的優先級Q作如下定義：

(4)

由公式(4)可得Q={0,1,k,k+1…k2,k2+1}，其中Q=k2+1為最高級，Q=0為最低級。在節點要發送的前后兩組數據時間間隔很長的情形下，最大退避次數將對數據發送成功率產生較大影響，而對網絡吞吐量的影響則越來越小，所以本算法又提出了重要級概念。重要級旨在提高某些特定數據的發送成功率，設重要級P={0,1}。

多優先級策略的無時隙CSMA/CA算法流程如下：當有節點要發送數據時，首先確定待發送數據的優先級，若Q1=1，則執行優先級1(令CW=1)，若Q2=1，則執行優先級2(即BE=C固定)。如要發送的數據P=1，則使得MaxBackoffs+1，這樣可以使得最大退避次數多1，以保證特定的數據有高于普通數據的發送成功概率。此處的1理解為一個偏移量，不一定為常數，可以設偏移量為IMP(函數)，而重要級別則可以反映在IMP上。不等式NB

對于CSMA/CA算法常常采用馬爾可夫鏈模型來分析，圖2為馬爾可夫鏈模型[6]，前人對其進行了細致而嚴密的分析，在此處由于篇幅限制不作過多推導，只引用若干結論。

數據成功發送的概率(即接入概率)設為γ，第一次執行CCA信道為忙碌的概率為a，第二次執行CCA信道為忙碌的概率為b，節點個數為n，當數據能夠退避的最大次數為m時，令G=1[7]。文獻[6]指出網絡吞吐量和接入延時成反比關系，即吞吐量越高接入延時就越短，數據的接入時延越短說明數據發送得越快[8]。所以從網絡的數據吞吐量來看，在同等條件下希望高優先級數據的傳輸吞吐量越高越好。

圖2 馬爾可夫鏈模型

3 仿真結果

基于下面3個假設進行仿真：①發送的數據需要回復信息，在仿真時也將回復時間計算在內，且發送數據的時間為整數倍單位時長；②不存在暴露節點問題和隱藏節點問題，認為在一定范圍內的所有節點都可以相互檢測到；③每一個節點都有數據發送，數據長度和相鄰數據之間的間隔滿足泊松分布。

如圖3(a)和圖3(b)所示，BE遵循標準CSMA/CA算法規則，每一次退避后自加1，直至達到最大退避指數macMaxBE為止，保持不變，本文稱為標準模式。MaxNB表示最大的退避次數，圖3(a)中每條曲線對應一個參數CW值，圖3(b)～圖3(d)可以類比于圖3(a)。圖3(a)中參數MaxNB=1，圖3(b)中參數MaxNB=2，在這兩種情形下反映CW對于網絡平均吞吐量的影響。圖3(c)和圖3(d)分別和圖3(a)和圖3(b)類似，不同之處只是將BE=C固定，在仿真中令BE=2固定，即BE值不會更新，圖3(c)中參數MaxNB=1，圖3(d)中參數MaxNB=2。

由此可知，在其它條件相同的情況下，CW越小，網絡的平均吞吐量就越大，待發送數據的平均時延就越小。因為CW=1代表只要檢測到信道空閑就立即發送數據，而CW=2則必須連續兩次檢測信道均為空閑才會發送數據。

如圖4(a)～圖4(d)所示，仿真在其它外部因素完全相同的條件下，對BE=2固定和標準CSMA/CA算法處理BE(下文稱之為標準模式)這兩種方式進行平均吞吐量對比。在節點數相同時，將BE=2固定，其網絡的平均吞吐量得到了大幅提升。當然這樣付出的代價就是會使得節點功耗加大，因為BE=2固定，會使待發送數據的平均退避時間縮短，節點執行CCA次數明顯增加，從而導致節點功耗加大[9]。為兼顧功耗和網絡平均吞吐量，直接的方法就是適當減少執行CCA的次數[10]。可以將BE=C中的參數C定高一些。注意參數C的值應該比標準模式下BE的平均值小。

圖3 標準模式及BE固定模式

圖4 平均吞吐量對比

圖5為BE=C固定模式下的平均吞吐量與節點數仿真，不同的C值對應不同的函數曲線圖，從圖中可以看到網絡的平均吞吐量隨C的增大而減少，C越大則退避時間期望值越大，直接導致接入延時變長，其宏觀表征為網絡平均吞吐量降低。在標準模式下，BE的初始值越大則接入延時越大，平均吞吐量越小[11]，道理同BE=C的固定模式是相同的。

圖6為不同的最大退避次數MaxNB的數據平均接入時延比較，由圖可知，最大退避次數MaxNB越大則數據的平均接入時延越長，待發送數據的接入時延越長網絡的平均吞吐量越低，所以最大退避次數越大網絡平均吞吐量則越低。

圖7(a)～圖7(d)表示待發送數據發送成功率和節點數目之間的函數關系，為其它條件相同而最大退避次數MaxNB不同時進行的比較。從仿真圖可以看出，最大退避次數MaxNB越大則待發送數據成功率越高；分別對圖7(a)和圖7(b)、圖7(c)和圖7(d)兩組仿真圖對比，可以發現此時CW對于待發送數據的成功率幾乎沒有影響，這一仿真結果可以理解。一旦檢測到信道忙碌便丟掉數據，立刻準備發送新的數據；如果檢測信道忙碌就執行退避過程，一次又一次執行，且每次的退避時間都會變長一些，這個數據就會滯留(仍然有發送出去的可能性)，導致網絡的平均吞吐量不如前者，但是有利于提高數據發送的成功率。所以有些時候要權衡網絡的平均吞吐量與數據接入概率之間的關系，使二者達到一個平衡。權衡的方法為：在不同的MaxNB下，使數據的接入概率和平均吞吐量減去一個特定值所得的結果相乘，稱為接入-吞吐積，最大的那個接入-吞吐積對應的MaxNB即認為是最優的選擇。

圖5 固定BE=C吞吐量對比 圖6 不同MaxNB平均接入時延

圖7 發送成功率對比

4 結語

基于優先級的無時隙CSMA/CA算法主要特征為：依據多種優先級和重要級進行數據分區，經過分析和仿真可以看出，在發送數據速率和其它參數一定的情況下，參數BE越小，CW越小，網絡吞吐能力越強，數據的平均延時就越短；數據優先級數值Q越大，對應的參數BE數值越小，參數CW越小。在相鄰待發送數據間隔時間遠遠大于數據發送時間的情況下，評價平均接入概率和平均吞吐量的關系，確定最大退避次數MaxNB的方法為計算接入-吞吐積的值，最大接入-吞吐積對應的最大退避次數MaxNB則認為是最合適的。

[1] 謝希仁. 計算機網絡 [M].第6版. 北京:電子工業出版社,2013：365-378.

[2]SHAHINFARAHANI.ZigBeewirelessnetworksandtransceivers[M].ElsevierLtd,2008： 47-79.

[3]IEEE-SASTANDARDSBOARD.Wirelessmediumaccesscontrol(MAC)andphysicallayer(PHY)SpecificationsforLow-RateWirelessPersonalAreaNetworks(LR-WPANs)，IEEE802 15.4 [S].IEEEstandardforInformationTechnology, 2006：166-200.

[4]ANISKOUBAA,MRIOALVES,EDUARDOTOVAR.AcomprehensivesimulationstudyofslottedCSMA/CAforIEEE802.15.4WirelessSensorNetworks[J].FactoryCommunicationSystems,IEEEInternationalWorkshopon，2006(5)：183-192.

[5]LKLEINROCK,FATOUBAGI.Packetswitchinginradiochannels:partI-carriersensemultipleaccessmodesandtheirthroughput-delaycharacteristics[J].IEEETransonCommunications, 1975，23(12)： 1400-1416.

[6]RAJAVARAPRASADY,RAJALAKSHMIPACHAMUTHU.AnalyticalmodelofadaptiveCSMA-CAMACforreliableandtimelyclusteredwirelessmulti-hopcommunication[C].InternetofThings(WF-IoT),IEEEWorldForumon，2014：212-217.

[7]HAOWEN,CHUANGLIN,ZHI-JIACHEN,etal.AnimprovedmarkovmodelforIEEE802.15.4slottedCSMA/CAmechanism[J].Journalofcomputerscienceandtechnology,2009,24(3):495-504.

[8]JNI，BTAN，RSRIKANT.Q-CSMA:queue-length-basedCSMA/CAalgorithmsforachievingmaximumthroughputandlowdelayinwirelessnetworks[J].IEEE/ACMTransactionsonNetworking,2012，20(3)： 825-836.

[9]APOORVAJINDAL,KONSTANTINOSPSOUNIS.OntheefficiencyofCSMA-CAschedulinginwirelessmultihopnetworks[J].IEEE/ACMTransactionsonNetworking，2013，21(5)：1392-1406.

[10]KLEE,PMITCHELL,DGRACE.Energyefficientdistributedreservationmultipleaccesswithadaptiveswitchingrequestsforwirelessnetworks[J].IEEETransactionsonWirelessCommunications,2014,13(1):259-267.

[11]RLAUFER,LKLEINROCK.OnthecapacityofwirelessCSMA/CAmultihopnetworks[C].INFOCOM,2013ProceedingsIEEE,2013:1312-1320.

(責任編輯：杜能鋼)

李亮(1991-)，男，河北張家口人，中國兵器工業集團第214研究所碩士研究生，研究方向為無線傳感器網絡技術；張君利(1967-)，女，安徽阜陽人，中國兵器工業集團第214研究所研究員，研究方向為厚膜電路；楊侃(1979-)，男，江蘇鹽城人，中國兵器工業集團第214研究所高級工程師，研究方向為教學電路設計。

10.11907/rjdk.171022

TP312

A

1672-7800(2017)003-0030-04