李 亮，張君利，楊 侃

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

多優(yōu)先級無時隙CSMA/ CA算法研究

李 亮，張君利，楊 侃

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

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

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

0 引言

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

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

1 無時隙CSMA/CA算法

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

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

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

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

圖1 時隙CSMA/CA算法流程

2 多優(yōu)先級CSMA/CA算法

網(wǎng)絡平均吞吐量和平均接入延時概念：吞吐量Sthr指網(wǎng)絡中的所有節(jié)點單位時間成功發(fā)送的數(shù)據(jù)總數(shù)[4]，網(wǎng)絡的平均吞吐量S則是總數(shù)據(jù)量除以網(wǎng)絡的節(jié)點總數(shù)。

(1)

M表示整個網(wǎng)絡中的發(fā)送節(jié)點數(shù)。

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

(2)

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

(3)

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

(4)

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

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

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

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

圖2 馬爾可夫鏈模型

3 仿真結果

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

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

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

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

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

圖4 平均吞吐量對比

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

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

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

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

圖7 發(fā)送成功率對比

4 結語

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

[1] 謝希仁. 計算機網(wǎng)絡 [M].第6版. 北京:電子工業(yè)出版社,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-)，男，河北張家口人，中國兵器工業(yè)集團第214研究所碩士研究生，研究方向為無線傳感器網(wǎng)絡技術；張君利(1967-)，女，安徽阜陽人，中國兵器工業(yè)集團第214研究所研究員，研究方向為厚膜電路；楊侃(1979-)，男，江蘇鹽城人，中國兵器工業(yè)集團第214研究所高級工程師，研究方向為教學電路設計。

10.11907/rjdk.171022

TP312

A

1672-7800(2017)003-0030-04