周期性采樣的兩步指數退避算法研究

陶志勇，袁永財

1.遼寧工程技術大學 電子與信息工程學院，遼寧 葫蘆島 125105

2.遼寧工程技術大學 研究生學院，遼寧 葫蘆島 125105

1 引言

無線傳感器網絡（WSN）是一種特殊的無線多跳分布式網絡，它不需要固定的網絡支持，具有快速組網、抗毀滅性強等特點[1]。同時由于WSN自身特性，網絡中節點資源的使用是受到限制的，尤其是電池的使用。因此，如何降低WSN網絡中節點的能耗成為當前研究WSN的熱點之一。

介質訪問控制協議（MAC）決定了無線信道的使用方式，并在節點之間分配有限的無線通信資源[2]。MAC協議處于無線傳感器網絡協議的底層部分，直接影響著網絡的吞吐量、能效、節點公平性等網絡重要性能，特別是MAC協議中的退避算法直接影響節點間碰撞概率、節點公平性與能量效率等關鍵性能。

目前退避算法使用比較廣泛的是由IEEE 802.11DCF[3]標準定義的二進制指數退避算法（BEB）[4]，但BEB算法并不完善，自提出以來，很多學者從不同的方面對其進行了改進。如文獻[5-7]從退避協議的穩定性對BEB進行改進；文獻[8]則關注網絡中節點的公平性等。文獻[9]通過引入競爭窗口復位值Lx來選擇退避窗口大小，其核心思想是：若當前競爭窗口比Lx大則在發送成功時退避窗口變為Lx，再次發送成功競爭窗口才變為最小值，這樣經過兩步窗口復位緩解了競爭窗口震蕩[9]的問題。但是文獻[9]沒有給出在網絡流量快速增加時該如何調整競爭窗口的方法。文獻[10]通過在發送數據前開啟一個觀測窗口來計算時隙利用率S_U，S_U隨網絡負載增大而增大。在數據發送成功后，競爭窗口根據時隙利用率和數據重傳次數來改變，而不是盲目的將競爭窗口變為最小，從而維護了網絡中節點接入信道的公平性，也提高了網絡的吞吐量。但是文獻[10]在數據發送失敗時窗口的增大是通過乘以一個固定的系數來實現的，不能滿足網絡中流量動態變化的需求。本文在BEB的基礎上，結合文獻[9-10]兩種改進算法提出了周期性采樣的兩步指數退避算法PTEB。

2 PTEB算法

根據IEEE 802.11DCF標準的規定，BEB算法具體描述為：若節點通信成功，將競爭窗口降為最小值。若節點通信失敗，則將競爭窗口CW[11]值擴大到原來的2倍，一直到最大值。當此節點的CW值增大到CWmax時，再請求信道要求重傳時CW的值應一直保持為CWmax，直到此節點發送成功或者達到了幀傳輸的最大重傳次數后CW被置為CWmin為止。

IEEE 802.11DCF標準還規定了節點接入信道的方式，當節點有數據要發送時，首先需要偵聽信道，如果偵聽到信道連續空閑時隙超過DIFS，則節點就進入了退避狀態，如果偵聽信道連續空閑時隙沒有超過DIFS則一直偵聽直到超過DIFS為止。節點進入退避狀態后，通過BEB算法計算CW值。計算CW的值是為了給節點選取退避時間。根據公式（1）計算具體的退避時間[12]：

BackoffTime=Random(0，CW)×aSlotTime（1）其中，aSlotTime是一個時隙長度，由物理層決定。例如DSSS（直接序列擴頻）時隙固定為20 μs。Random(0，CW)是在[0，CW]范圍內均勻分布的隨機整數，CW是BEB算法中計算出的結果。初始值為CWmin，最大值為CWmax。退避時間值保存在退避計數器內，當退避計數器的值減為零時，節點才可以開始發送數據。若在退避過程中節點檢測到信道變為忙，則結束退避過程，并重新開始偵聽信道。

PTEB算法在標準BEB算法的基礎上進行了改進，二者的不同之處主要有以下幾點：

（1）引入采樣周期概念。

（2）定義了兩個網絡參數，分別是信道競爭能力參數和網絡擁擠參數，用來衡量當前采樣周期內網絡的狀況。

（3）CW的改變不再是按照二進制指數的形式增長，而是按照上面定義的兩個網絡參數進行增大或減小。

（4）節點分兩個階段對CW進行調整：第一階段為節點發送數據后；第二階段為節點剛進入退避階段時。

2.1 采樣周期

為了了解當前網絡工作的實時狀況，把時間分割成連續的相同大小的時間段，這樣的一個時間段稱為采樣周期。一個采樣周期的長度至少能夠滿足節點完成一次數據傳輸所需的時間，即：

采樣周期≥DIFS+CWmax+最大數據長度

同時采樣周期也不可無限制的增大，因為在下文中可以知道，在采樣周期內要對一些參數進行計數，在實際情況中，存儲該數值的變量的范圍是有限制的，所以采樣周期的最大值不能超過該變量的范圍。

采樣周期的取值在其允許的范圍內，值越大越好，因為頻繁的對網絡狀況進行采樣會增加數據的計算時間，從而導致網絡延時的增加。

2.2 信道競爭能力參數

BEB算法中競爭窗口只是根據數據發送的成功還是失敗來進行調整，本文出于對節點公平性的考慮，引入了節點信道競爭能力參數Qc如公式（2）所示；同時還引入了Qc的閾值：QCH、QCL，分別表示Qc的上限和下限。

當一個采樣周期開始時，Ncs初值等于0，節點每成功競爭到信道一次，Ncs的值就加1，表示在此時刻之前，當前采樣周期內節點成功競爭到信道的次數；Nsum初值等于0，節點每參與競爭信道一次，Nsum的值就加1，表示在此時刻之前，當前采樣周期內節點參與競爭信道的總次數。

由于在一個采樣周期的開始，Ncs、Nsum均為0，此時的Qc無法計算，所以規定在采樣周期開始時Qc的初始值為0。但是這樣會導致相鄰的兩個采樣周期中Qc值的突變，因此對公式（2）作如下修正：

其中，α+β=1。Qc(T-1)是前一個采樣周期結束時的Qc值，Qc(T)表示本次采樣周期的Qc值，α、β分別是Qc(T-1)和Qc(T)所占的權重，α為Qc(T-1)與Qc(T)的相關系數的絕對值，由相關系數的定義可知α的取值在[0，1]之間。

2.3 網絡擁擠參數

如果節點知道當前網絡的繁忙程度，那么就可以使節點以此為依據對CW做出相應的調整，而不是根據發送的成功或失敗來盲目的增大或減小CW。本文以Qb來表示網絡的繁忙程度，同時引入閾值QBG來表示網絡可以容忍擁擠的一個限度。

當一個采樣周期開始時，Nsf初值等于0，節點每發送失敗一次，Nsf的值就加1，表示在此時刻之前，當前采樣周期內節點數據發送失敗的次數；Nsum與公式（2）相同。

與Qc一樣，Qb也需要進行修正：

其中α+β=1。下文中的Qc和Qb均為修正后的值，為了表達清晰，仍使用Qc和Qb來表示。

2.4 CW的計算

CW的初始值[13]設為CWmin，之后CW的值會根據PTEB算法進行調整。CW計算分為兩個階段：

第一個階段是在節點發送數據后，

其中CWpre是前一次競爭窗口的值，[X]表示對X做取整運算。

第二階段是在節點偵聽到信道連續空閑時間超過DIFS時，節點根據當前的Qc、Qb計算CW。

3 PTEB算法分析

PTEB算法首先將時間劃分為連續的采樣周期，在每一個采樣周期內，各個節點都有屬于自己的網絡參數Qc和Qb。

當節點在一個采樣周期內有數據要發送時，與BEB算法一樣，要先偵聽信道的狀態，直到進入退避狀態。當節點進入到了退避狀態后，節點根據公式（5）計算此時的CW，然后進行退避。退避結束后，節點發送數據，發送數據后按照公式（4）再次計算CW值，此時如果還有數據要發送，節點重新偵聽信道，并重復以上的過程。

3.1 公平性分析

網絡中節點的公平性指的就是節點接入信道的機會的均等性，而CW則關系到節點接入信道的能力，CW值越大接入信道的概率就越低，競爭能力就越差；相反，節點的競爭能力就越強。

節點的公平性影響著網絡的吞吐率以及數據傳輸的實時性，因此維護WSN中節點的公平性也是一項重要的任務。

維護網絡中節點的公平性問題其實就是平衡節點接入信道能力的問題。如果節點接入信道能力過強，可以通過增大CW來減小其競爭力；相反的，可以通過減小CW來增大節點接入信道的能力。

從公式（5）中可以看出，當節點接入信道能力小于規定的下限并且網絡負荷較輕時，這說明Qc＜QCL是因為本節點的競爭信道能力較其他節點弱，所以用Qc乘以當前的CW來減小競爭窗口的值，從而使本節點競爭信道能力變強。

而當節點接入信道能力大于規定的上限時，無論當前網絡負載是重還是輕，都應該增大CW。這是因為當網絡負載較輕時，本節點擁有較大的Qc就說明其他節點的競爭信道能力比本節點小的多，所以用1+Qc乘以當前的CW來增大競爭窗口的值，從而使本節點競爭信道能力變弱；相反，當網絡負載較重時，為了避免數據碰撞的加劇，也應該增大CW。

而在節點接入信道能力適中且網絡負載較輕時，不對CW進行調整。

經過上面的分析可知，CW在經過公式（5）的調整后，在不加劇節點間數據碰撞的前提下，網絡的公平性得到了改善。

3.2 窗口自適應性分析

網絡中的流量是動態變化的，希望競爭窗口能夠根據網絡流量的變化而自動的調整，從而減小數據的碰撞，增大網絡的吞吐率。

數據發送失敗后，當Qb＜QBG時，說明網絡負載較輕，如果CW變為原來的2倍，會使網絡中空閑的時隙變多，降低了網絡的吞吐量。而當網絡負載很重時，即Qb＞QBG，窗口還是變為原來的2倍，這樣窗口的變化速度又相對過慢，會使網絡中數據碰撞次數慢慢增多。

公式（4）中，數據發送失敗后CW變為原來倍。當Qb/QBG＜1時說明網絡負載較輕，根據指數增長的規律，此時的值在（1，2）之間，且增長速度比較緩慢；當Qb/QBG＞1時說明網絡負載較重，根據指數增長規律，此時的值在(2，+∝)之間，且增長速度比較迅速。這樣改進后，在網絡負載輕時節點接入信道的速度會變快，網絡中空閑時隙會減少；在網絡負載較重時數據碰撞次數會減少，由碰撞而引起的能量消耗也會減少。

4 仿真分析

本文使用Matlab進行仿真測試。物理信道使用的是文獻[14]中多址接入信道模型，以CSMA/CA作為信道的接入方式。由于本文只是研究碰撞算法，并沒有將完整的MAC層加以實現，只是對IEEE 802.11協議的MAC層進行裁減，使用了簡化后的MAC層。每個節點數據包到達的時間服從參數λ為100 aSlotTime的泊松分布。

仿真環境參數設定如表1所示。

表1 仿真環境參數

4.1 仿真參數

通過以下3個性能指標來評估PTEB算法的性能。

（1）歸一化吞吐率throughput

定義為整個網絡單位時間內成功交互的數據比特數同物理信道數據速率的比值，即：

（2）網絡中節點公平因數G

網絡中節點的競爭窗口大小可以間接反映網絡中的公平性，如公式（7）所示，用競爭窗口的標準差來表示公平因數G：

（3）平均碰撞次數Coll_Num_Avrg

其中Coll_Numi為節點i一個周期內的碰撞次數。

4.2 歸一化吞吐率比較

本文對BEB、PTEB、MILD（乘性增加線性減小算法）3種退避機制在不同節點數目情況下的吞吐率進行對比，如圖1所示。

圖1 歸一化吞吐率比較

從圖1可以看出，當節點數量較少時，3種算法的吞吐率相差不大，MILD的吞吐率要略高于BEE，BEB的吞吐率略高于PTEB；而當節點數量超過某一值時，PTEB算法的吞吐率相對于BEB和MILD算法的吞吐率總是處于較高的水平上，隨著節點數量的繼續增多，網絡中空閑時隙越來越少，數據碰撞會越來越嚴重，3種算法的吞吐率也會逐漸下降并逐漸接近。

4.3 節點公平因數的比較

不同算法下的公平因數隨節點數量的變化曲線，如圖2所示。

圖2 網絡公平因數比較

從圖2可以看出當節點數量較小時，PTEB算法的公平性要低于其他兩種算法；而當節點數量大于某一值時，PTEB算法的公平性要遠遠優于其他兩種算法。

4.4 平均碰撞次數比較

不同算法下的數據平均碰撞次數隨節點數量的變化曲線，如圖3所示。

圖3 平均碰撞次數比較

從圖3可以看出，PTEB算法下的平均碰撞次數總是小于其他兩種算法中的平均碰撞次數，隨著節點數量的增多三者的平均碰撞次數也逐漸趨于相等。

5 結束語

本文通過理論分析和實驗仿真，證明了PTEB算法能夠根據網絡流浪的動態變化來調整競爭窗口CW的大小，并且在節點數量不是很小的時候（大于20），其在減少數據碰撞，增加網絡吞吐率，維持節點公平性等方面要優于BEB與MILD算法。

[1]古連華，程良倫.Au-MAC：一種自適應的無線傳感器網絡MAC協議[J].自動化學報，2010，36（1）：54-59.

[2]唐震洲，胡倩.基于數據重排序的無線傳感器網絡低延時節能MAC協議[J].傳感技術學報，2010，23（7）：1037-1043.

[3]IEEE Std 802.11.Part 11 Wireless LAN Medium Access Control（MAC）and Physical Layer（PHY）specifications[S].New York：IEEE Press，2007.

[4]Pantazi A，Antonakopoulos T.E-quilibrium point analysis of the binary exponential backoff algorithm[J].Computer Communications，2001，24（18）：1759-1768.

[5]Zhang Y，Piunovskiy A，Ayesta U，et al.Converge-nce of trajectories and optimal buffer sizing for MIMD congestion control[J].Computer Communications，2010，33（2）：149-159.

[6]Wang C，Li B，Li L.A new collision resolution mechanism to enhance the performance of IEEE 802.11 DCF[J].IEEE Transactions on Vehicular Technology，2004，53（4）：1235-1246.

[7]姚為錫，蔡保國，繆學寧.競爭窗口線性變化的分級沖突解析算法[J].計算機工程與應用，2013，49（22）：72-76.

[8]唐勇，周滿元.Ad hoc網絡中MAC不公平性的研究與改進[J].計算機工程，2010，36（22）：100-102.

[9]彭靜，朱藝華.IEEE802.11無線局域網二進制指數退避算法改進與分析[J].計算機工程與科學，2012，34（12）：39-44.

[10]張強，付敬奇.一種IEEE 802.11接入機制的新退避算法[J].傳感技術學報，2008，21（12）：2073-2077.

[11]王二飛.無線傳感器網絡MAC層CSMA/CA機制的研究[D].北京：北京郵電大學，2012.

[12]陳忠真.IEEE802.11 DCF算法的研究[D].西安：西安電子科技大學，2012.

[13]王葉群，黃國策.一種時效性約束的二進制指數退避算法[J].計算機科學，2012，39（4）：56-59.

[14]劉學勇.詳解MATLAB/SIMULINK通信系統建模與仿真[M].北京：電子工業出版社，2011.