基于隊列長度的自適應占空比MAC協(xié)議

張閃閃，甄 雪

(曲阜師范大學 信息科學與工程學院，山東 日照 276826)

0 引 言

無線傳感器網(wǎng)絡(wireless sensor networks，WSNs)是大量小型或微型低能耗傳感器節(jié)點協(xié)作地感知和采集監(jiān)測區(qū)域的各種信息并處理后，通過自組織多跳的方式形成短距離的無線通信網(wǎng)絡。目前，WSNs已經(jīng)廣泛應用于智能建筑[1]、搶險救災[2]、健康監(jiān)測[3]、目標跟蹤[4]等重要領域[5]。WSNs在用來提供更好服務的同時又面臨很多挑戰(zhàn)。由于WSNs中的節(jié)點大都采用電池供電，能量非常有限，并且節(jié)點一旦部署很難回收，所以對WSNs的能量效率研究一直是熱點和難點問題。像所有共享媒體的網(wǎng)絡一樣，MAC是實現(xiàn)網(wǎng)絡成功操作的重要技術。但是現(xiàn)有的無線媒體訪問控制協(xié)議，例如藍牙和802.11MAC協(xié)議都不能被直接應用到WSNs中，因為它們都沒有將節(jié)能作為主要目標。

已有許多研究表明，空閑監(jiān)聽消耗接收所需能量的50%～100%。例如，Stemm和Katz測量到空閑：接收：發(fā)送比率為1∶1.05∶1.4[6]，而Digitan 2 Mbps無線局域網(wǎng)模塊(IEEE 802.11/2 Mbps)規(guī)范中空閑：接收：發(fā)送比率為1∶2∶2.5[7]。因此，為了延長網(wǎng)絡的生存周期，有很多協(xié)議采用占空比機制來減少空閑監(jiān)聽造成的能量消耗。在占空比機制中，每個節(jié)點周期性地在活躍期和睡眠期之間切換。在活躍期，節(jié)點監(jiān)聽信道并且傳輸數(shù)據(jù)，在睡眠期，節(jié)點切換到低功率狀態(tài)(例如關閉收發(fā)器)進入睡眠模式。過低的占空比雖然節(jié)省能量但會造成密集傳輸，所以設計一個好的MAC協(xié)議，選擇合適的占空比數(shù)值來實現(xiàn)高吞吐量低時延是WSNs的設計難點。

采用占空比機制的MAC協(xié)議一般分為兩類：同步競爭和異步競爭。它們都是通過減少空閑監(jiān)聽，增加睡眠時間來節(jié)約能量的。有許多同步占空比協(xié)議被提出，例如S-MAC[8]、T-MAC[9]、CL-MAC[10]、TAS-MAC[11]。但是這類同步協(xié)議要求每個節(jié)點可能會維持一個或多個同步時間表，并且對節(jié)點之間的時鐘同步要求嚴格，這會產(chǎn)生很大的控制開銷以及能量消耗，而且當網(wǎng)絡負載發(fā)生變化時，高負載沖突較多，低負載空閑偵聽較多，所以同步協(xié)議并不能達到很好的效果。依靠前導符采樣的異步協(xié)議，例如B-MAC[12]、Wise-MAC[13]、X-MAC[14]、L-MAC[15]，允許節(jié)點維持自己獨立的工作周期，收發(fā)雙方不需要同步，采用低功率監(jiān)聽(LPL)前導序列技術喚醒接收節(jié)點，消除了同步協(xié)議的限制，在吞吐量延遲以及能量高效性方面超過了許多同步協(xié)議。但是，此類協(xié)議也有自身的缺點，例如長的前導符造成的非目標節(jié)點的串音問題以及異步之間互相等待引起的較高端到端時延等。

文中提出了一種基于緩沖區(qū)隊列長度的異步MAC協(xié)議，不同于其他考慮接收節(jié)點操作的算法，而是從發(fā)送節(jié)點出發(fā)，利用緩沖區(qū)隊列長度判斷網(wǎng)絡負載改變占空比，當網(wǎng)絡負載高時節(jié)點可以延長發(fā)送時間來降低節(jié)點的端到端時延，盡快降低網(wǎng)絡負載，網(wǎng)絡負載低時，在保證數(shù)據(jù)發(fā)送量的條件下增加節(jié)點的睡眠時間，節(jié)省能量。

1 QL-MAC設計

由于固定的占空比在網(wǎng)絡負載變化時不能表現(xiàn)更好的性能，因此希望設計一個能根據(jù)網(wǎng)絡負載大小改變占空比的異步MAC協(xié)議。首先將每個節(jié)點的周期分為非活躍階段和活躍階段，非活躍階段即睡眠期，活躍階段包括監(jiān)聽和傳輸，節(jié)點在這兩個周期之間進行轉換。設每個節(jié)點開始的睡眠-喚醒周期長度為T。

活躍階段：此階段包括檢測事件、競爭信道、信標包和數(shù)據(jù)包的傳輸和確認。協(xié)議開始時設定的活躍時間為Tactive，其中包括檢測事件Td，競爭時間為Tcontend，每個信標包的傳輸時間為tbeacon，接收一個確認包的時間為tack，傳輸數(shù)據(jù)時間為Tdata，包括對分組的確認時間。

睡眠階段：此階段節(jié)點轉入睡眠狀態(tài)來節(jié)約能量，設睡眠時間開始時為Tsleep。在睡眠狀態(tài)下，節(jié)點將采集的數(shù)據(jù)放入自己的緩沖隊列中。

從以下幾個階段來詳細介紹設計的MAC協(xié)議在這兩個階段的通信過程：

1.1 異步喚醒競爭信道

眾所周知，兩個節(jié)點通信時雙方必須都處于活躍階段，所以源節(jié)點發(fā)送數(shù)據(jù)時要等待目的節(jié)點喚醒才可以。異步通信中普通的前導符采樣采用以下原理：節(jié)點周期性地喚醒一小段時間來對信道進行采樣。如果信道是空閑的，那么節(jié)點立刻回到睡眠狀態(tài)。如果檢測到信道忙，則節(jié)點保持監(jiān)聽狀態(tài)直到所有的數(shù)據(jù)都被接收或者是發(fā)生超時。這個方法要求在第一個數(shù)據(jù)幀前加上一個前導符，這個前導符的長度至少是一個信道采樣間隔的長度，以免接收節(jié)點睡眠過程錯過前導序列。但是此種方法非目標節(jié)點在長前導符發(fā)完之前不能發(fā)現(xiàn)該包并不是發(fā)給自己的，這造成了很大的能量浪費并且與節(jié)點密度成正比。為了避免這種問題，采用分組的前導符采樣來進行異步喚醒。使用文獻[16]中提出的STEM-B前導符變形，利用一系列的信標包來作為前導符，每個信標包包含了發(fā)送端和接受端的MAC地址以及此信標包的序列號。因此節(jié)點能夠判斷它是不是即將進行數(shù)據(jù)傳輸?shù)哪繕斯?jié)點，與傳統(tǒng)的前導符采集協(xié)議相比，非目標節(jié)點可以盡早丟棄分組從而更早進入睡眠。當源節(jié)點喚醒時，在Td時間內檢測是否有事件發(fā)生，如果有事件發(fā)生則發(fā)送信標包等待目標節(jié)點喚醒。因為每個節(jié)點周期性的喚醒和睡眠，當網(wǎng)絡中節(jié)點密度大，網(wǎng)絡負載高時，可能有多個節(jié)點同時喚醒想要發(fā)送數(shù)據(jù)，所以會產(chǎn)生沖突，因此利用CSMA機制進行信道爭用。設信道爭用時間為Tcontend，在此時間內沒有收到任何信息則獲得信道發(fā)信標等待目的節(jié)點喚醒，bn就是信標包，如果接收到信標，則判斷信標是否發(fā)給自己，如果是則回復ACK等待接收數(shù)據(jù)，如果不是則轉入睡眠，等待下一周期重復上述過程。

1.2 數(shù)據(jù)傳輸

當節(jié)點獲得信道與目的節(jié)點建立通信后開始傳輸數(shù)據(jù)，如果將一個長消息裝入數(shù)據(jù)包后，一旦損壞就需要重傳整個長消息，而無線信道中傳輸差錯與消息的長度成正比例關系，因此長消息有著比短消息更低的成功傳輸概率，這會有很大的能量時間以及帶寬消耗。因此該協(xié)議不像SW-MAC[17]和DS-MAC[18]那樣發(fā)送大分組轉入睡眠，而是將長消息分段，在喚醒時間連續(xù)發(fā)送數(shù)據(jù)包，并等待確認，直到喚醒時間到期，如圖1所示。

圖1 QL-MAC協(xié)議數(shù)據(jù)傳輸

所以節(jié)點喚醒之后有以下幾種情況發(fā)生：

(1)節(jié)點有數(shù)據(jù)發(fā)送且獲得信道，發(fā)送一系列含有目標地址和序列號的信標包，然后在信標包之間預留接收目的節(jié)點確認的時間tack。然后開始傳輸數(shù)據(jù)，所以此時數(shù)據(jù)傳輸總時間為：

Ta-Td-Tcontend-p(tbeacon+tack)

(1)

此處p為傳輸?shù)降趐個信標包時目的節(jié)點喚醒。若在Tcontend期間收到了信標，則判斷此信標是否是發(fā)給自己的，如果是則回復ACK準備接收數(shù)據(jù)，如果不是則丟棄。

(2)節(jié)點有數(shù)據(jù)發(fā)送但沒有獲得信道，為節(jié)省能量節(jié)點轉入睡眠，所以活躍時間為：

(2)

(3)節(jié)點喚醒但是在Td時間沒有數(shù)據(jù)要發(fā)送，此時設置監(jiān)聽時間為Tlisten=tbeacon+tack，在此時間內如果有信標包接收則接收信標包，回復ACK并轉發(fā)數(shù)據(jù)，此時數(shù)據(jù)傳輸時間為：

(3)

如果沒有接收到信標包則睡眠，此時

(4)

1.3 改變占空比

文中希望利用提出的協(xié)議根據(jù)網(wǎng)絡負載的大小來自適應調整節(jié)點的睡眠時間。因此，就需要提出一種方法來度量網(wǎng)絡負載情況。檢測網(wǎng)絡負載一般有以下幾種方法：一是通過串聽RTS/CTS等控制分組，二是通過估算傳輸分組之間的端到端時延，三是通過緩沖區(qū)隊列長度。這是因為在采用CSMA協(xié)議的數(shù)據(jù)傳輸中，對于競爭失敗的節(jié)點，數(shù)據(jù)會積壓在此節(jié)點本身的緩沖區(qū)隊列中等待下一次爭用信道。所以當網(wǎng)絡負載處于較高情境時，緩沖區(qū)內積壓的數(shù)據(jù)分組就會增加，可以傳輸?shù)墓?jié)點很難在較短的活躍期內傳輸完所有數(shù)據(jù)，并且其他沒有獲得信道從而處于退避階段的節(jié)點也會有很多數(shù)據(jù)分組在緩沖區(qū)內積壓。所以可以通過緩沖區(qū)隊列長度反應網(wǎng)絡負載。因此傳感器節(jié)點通過本地緩沖區(qū)隊列內待發(fā)數(shù)據(jù)分組的積壓情況就可以真實迅速反映網(wǎng)絡當前的負載情況，于是就利用這個特性來自適應調整節(jié)點在該周期的睡眠時間。

對于發(fā)送節(jié)點：

因為希望設計的協(xié)議能根據(jù)網(wǎng)絡負載調整占空比，文中的重點在于找到一個緩沖區(qū)隊列的閾值來判斷網(wǎng)絡負載大小。所以計算在整個睡眠-喚醒周期中能傳輸?shù)姆纸M數(shù)量為：

(5)

其中，tpacket是一個分組傳輸?shù)臅r間。

在最好的情況下信道空閑，節(jié)點僅傳輸一個信標就接收到來自接收端的ACK，此時時間為tpacket+tack，那么可求出最大傳輸分組個數(shù)nmax為：

(6)

實際情況中，由于可能產(chǎn)生信道爭用，并且接收節(jié)點的喚醒時間可能不會那么及時，所以一次能發(fā)送的分組個數(shù)遠小于nmax。

假設每個節(jié)點在Td時間計算其緩沖區(qū)當前隊列長度即緩沖區(qū)中分組數(shù)量，記為L。雖然一次能發(fā)送分組的個數(shù)遠小于nmax，但是單純的nmax作為閾值來和隊列長度比較，當出現(xiàn)L和nmax很接近的時候，占空比調整會過于頻繁，所以將2nmax和nmax/2作為閾值。L>2nmax，說明此時網(wǎng)絡負載大，L

圖2 改變節(jié)點占空比

如圖2所示，在加倍占空比操作中，保持周期T不變，通過延長活躍時間來實現(xiàn)。在減半占空比操作中，保持活躍時間不變通過延長睡眠時間增大周期T來實現(xiàn)。這樣做的好處是：當網(wǎng)絡負載大時，喚醒時間加倍，這樣可以盡快發(fā)送完分組且降低節(jié)點的端到端時延；當網(wǎng)絡負載小時，喚醒時間不變，睡眠時間延長，這可以在保證節(jié)點每個周期發(fā)送數(shù)據(jù)量的情況下增加節(jié)點的睡眠時間，節(jié)省能量。

對于接收節(jié)點：

當發(fā)送節(jié)點的占空比改變時，接收節(jié)點也要做出相應改變，這種情況只需要在占空比加倍時候改變，否則就會出現(xiàn)當占空比加倍時發(fā)送端沒有發(fā)送完但接收端的活躍時間已經(jīng)到期的情況。為了避免此類情況發(fā)生，在信標包和確認包中加入一個1 bit的Flag字段，正常占空比用0來表示，如果占空比加倍則改為1，接收節(jié)點根據(jù)Flag位對自己做出調整。而發(fā)送節(jié)點占空比減半時接收節(jié)點不需要改變，因為接收節(jié)點也會接收到其他節(jié)點的數(shù)據(jù)包，不能僅根據(jù)其中一個發(fā)送節(jié)點就延長自己的睡眠時間。

1.4 虛擬載波監(jiān)聽

在數(shù)據(jù)傳輸?shù)倪^程中，當另一個節(jié)點在發(fā)送的時候節(jié)點喚醒，那么可能發(fā)生串聽。為了解決這個問題，使用虛擬載波監(jiān)聽(virtual carrier sense，VCS)。VCS采用網(wǎng)絡分配向量NAV獲得信道控制信息。在通信范圍內的任何節(jié)點都能看到此值，它采用單位時間來維護并基于本地時鐘遞減。當NAV的值不為0的時候表明信道被占用。在睡眠階段NAV計時器保持工作直到減為0。當NAV的值為0的時候節(jié)點處在活躍狀態(tài)，那么節(jié)點喚醒競爭信道，如果節(jié)點處于睡眠狀態(tài)則繼續(xù)睡眠等待下一個周期。

圖3 信標包和確認包格式

如圖3所示，可以在信標包和確認包中的duration字段添加兩個節(jié)點的通信時間來配置NAV值。這可以在發(fā)送端和接收端占用信道的時候，告知其他節(jié)點信道忙，無須爭用信道，對于其他節(jié)點來說，可以減少不必要的爭用，并且減少串聽。占空比變化和NAV配置如下所示：

(1)若L>2nmax，則表明緩沖區(qū)隊列長度遠大于此周期內能傳輸?shù)淖畲蠓纸M數(shù)量，說明節(jié)點此時的網(wǎng)絡負載已經(jīng)偏高，此時需要盡快發(fā)送分組，睡眠時間不變，通過延長喚醒時間將占空比加倍，此時Ta=2Ta，NAV=2Ta-Td-Tcontend。

(2)若L

(3)其余情況執(zhí)行原占空比，NAV=Ta-Td-Tcontend。

2 節(jié)點操作

具體節(jié)點操作的偽代碼如下所示。State(NAV，channel state，node state)分別代表NAV值，信道狀態(tài)和節(jié)點狀態(tài)。在NAV值中，0代表NAV=0，1代表NAV≠0。信道狀態(tài)分為忙和空閑。節(jié)點狀態(tài)包括活躍和睡眠。φ代表任意狀態(tài)。

算法：節(jié)點數(shù)據(jù)傳輸。

1 if node A has data to transmit then

2 node A contends the channel;

3 node A detects the queue length L;

4 switch the state(NAV,channel state,node state) do

5 case(0,idle,active);

6 ifL>2nmaxthen

7 double the dutycycle

8 set NAV=2Ta-Td-Tcontend

9 else ifL

10 half the dutycycle

11set NAV=L*(tpacket+tack)

12 end if

13 else

14 keep original dutycycle

15 set NAV=Ta-Td-Tcontend

16 end if

17 node A send beacon packet to node B

18 case(0,φ,sleep)

19 node continues sleep and waits for next cycle

20 case(0,φ,φ)

21 node countdowns NAV

22 else if node A received the beacon packet then

23 check flag

24 if flag=1 then

25 setTa=2Ta

26Ts=T-2Ta

27 node A replies ACK to sender

28 else

29 node A replies ACK to sender

30 end if

31 end if

32 else

33 node keeps active until the end ofTlisten

34 node turns to sleep and wakes up in the next cycle

35 end if

當節(jié)點喚醒之后，先監(jiān)聽信道，若檢測到信道忙則進入睡眠狀態(tài)倒計時NAV，當NAV=0時且節(jié)點處于活躍狀態(tài)則再次接入信道，否則繼續(xù)睡眠等待下一周期。若檢測到信道空閑且NAV=0，那么根據(jù)當前緩沖區(qū)長度判斷是否需要更改占空比，若負載過大，則將占空比加倍，過小則將占空比減半，并且設置NAV持續(xù)時間占用信道發(fā)送數(shù)據(jù)，若負載正常則占空比不變；如果一個節(jié)點在最大監(jiān)聽時間內沒有事件發(fā)生，即不發(fā)送數(shù)據(jù)也不接收數(shù)據(jù)，直接轉入睡眠狀態(tài)節(jié)省能量。圖4給出了節(jié)點的有限狀態(tài)機轉換圖。

圖4 有限狀態(tài)機

3 仿真與分析

為了驗證QL-MAC的性能，在OMNET++(Version：5.2.1)仿真器中對QL-MAC協(xié)議和X-MAC,S-MAC協(xié)議在端到端時延和能量有效性方面作性能比較。S-MAC是無線傳感器網(wǎng)絡的典型同步MAC協(xié)議，而X-MAC解決了異步MAC協(xié)議中前導符過長的缺點，二者在無線傳感器網(wǎng)絡中都表現(xiàn)出了很好的性能。使用鏈式拓撲和星型拓撲。在仿真中，每個節(jié)點之間的距離是200 m，通信范圍是250 m,確保節(jié)點僅能和一跳鄰居通信。采用單信道進行通信，節(jié)點工作在半雙工模式下，不考慮干擾，利用源節(jié)點產(chǎn)生數(shù)據(jù)分組的時間間隔來表示網(wǎng)絡中的負載情況。設置此間隔從1 s變化到10 s，當間隔為1 s的時候表示此時網(wǎng)絡負載最高，10 s時表示網(wǎng)絡負載最低。在實驗過程中，每個仿真運行60 s,節(jié)點初始占空比為10%，每個周期為1 s。

圖5 端到端時延對比

如圖5所示，不論鏈式拓撲還是星型拓撲，隨著包間隔時間的增加，X-MAC的網(wǎng)絡延遲逐漸降低并趨于平穩(wěn)，當包間隔時間為10 s時,網(wǎng)絡延遲最小。在鏈式拓撲下，QL-MAC的時延逐漸增加然后趨于平穩(wěn)，這是因為QL-MAC在高負載時，增加活躍時間，減少睡眠可以獲得比低負載下更好的時延，即使后來時延增加也是低于X-MAC。在星型拓撲下，高負載時節(jié)點競爭激烈，X-MAC的preamble包競爭變強，導致比鏈式更高的時延，但是當負載低時，由于跳數(shù)減少時延下降明顯，此后趨于平穩(wěn)。QL-MAC在星型的高負載下也是競爭激烈，相比鏈式時延增加，但是仍然低于X-MAC，隨負載變低，QL-MAC的優(yōu)勢逐漸降低，但是仍然和X-MAC不相上下。

圖6 節(jié)點平均能量消耗對比

從圖6可以看出，隨著網(wǎng)絡負載變低，系統(tǒng)消耗的平均功率在降低。當高負載時，X-MAC數(shù)據(jù)傳輸效率低，節(jié)點需要喚醒睡眠多次才可傳完，而QL-MAC協(xié)議會根據(jù)高負載延長活躍時間，減少多次睡眠喚醒之間消耗的能量，從而節(jié)約小部分能量，在低負載下QL-MAC優(yōu)勢更加明顯。總之，QL-MAC協(xié)議在能量有效性方面比S-MAC和X-MAC要好。

4 結束語

提出了一種基于CSMA和緩沖區(qū)隊列長度的異步MAC協(xié)議，主要目的是用來減少動態(tài)鏈路負載下的端到端時延。該協(xié)議使用CSMA爭用信道，從發(fā)送節(jié)點出發(fā)根據(jù)緩沖區(qū)隊列長度自適應改變節(jié)點的睡眠時間，當網(wǎng)絡負載較大時，增大活躍時間，當網(wǎng)絡負載較小時，延長睡眠時間，并通知接收節(jié)點做出相應改變。最后通過仿真表明，該協(xié)議獲得了良好的時延和高能效。