基于時間調(diào)度表的無線傳感器網(wǎng)絡(luò)MAC協(xié)議

龍昭華，馬永建，蔣貴全，陳丹丹

（重慶郵電大學(xué) 計算機(jī)系統(tǒng)結(jié)構(gòu)研究所，重慶400065）

0 引 言

無線傳感器網(wǎng)絡(luò)是由部署在監(jiān)測區(qū)域內(nèi)的大量微型節(jié)點(diǎn)組成，并且通過無線通信形成一個自組織網(wǎng)絡(luò)系統(tǒng)。傳感器節(jié)點(diǎn)是通過電池供電的，所以在傳感器網(wǎng)絡(luò)中，能量是最重要的。而在整個無線傳感器網(wǎng)絡(luò)的生命周期中，能量浪費(fèi)最多的是節(jié)點(diǎn)的空閑監(jiān)聽部分，浪費(fèi)最少的是節(jié)點(diǎn)的睡眠期。針對傳感器的節(jié)能需求，許多MAC協(xié)議提出了工作／休眠機(jī)制，比如S－MAC[2]，但是它使網(wǎng)絡(luò)的時延增加，吞吐量下降。

為了減少網(wǎng)絡(luò)的延遲時間，PA－MAC[3]（Pattern－MAC）在S－MAC和T－MAC[4]協(xié)議的基礎(chǔ)上，進(jìn)一步減少了空閑偵聽的時間。PA－MAC減少了空閑偵聽的時間，但是傳輸?shù)囊恍┠Ｊ綆]有實(shí)際意義。而且協(xié)議的執(zhí)行非常復(fù)雜，增加了節(jié)點(diǎn)的控制開銷?？傊?，這些協(xié)議[5]并不能使節(jié)點(diǎn)在多跳網(wǎng)絡(luò)傳輸中保持監(jiān)聽狀態(tài)，它們?nèi)匀淮嬖诤荛L的延遲時間。為了減少延遲時間，我們提出了AST－MAC協(xié)議，AST－MAC協(xié)議跟S－MAC類似，也是基于工作／休眠機(jī)制。

在這篇論文中，我們設(shè)計并實(shí)現(xiàn)了AST－MAC協(xié)議，我們增加了提高吞吐率的算法，這個算法讓節(jié)點(diǎn)保存下一個數(shù)據(jù)分組轉(zhuǎn)發(fā)的時間調(diào)度表。通過節(jié)點(diǎn)之間的數(shù)據(jù)分組的傳輸，從而形成了節(jié)點(diǎn)監(jiān)聽／睡眠的同步。利用這個算法，網(wǎng)絡(luò)的吞吐量提高了很多。

1 AST－MAC協(xié)議設(shè)計和改進(jìn)

1.1 AST－MAC的設(shè)計

AST－MAC協(xié)議算法依賴于精確的時鐘信息，因此節(jié)點(diǎn)間的時鐘同步相當(dāng)重要。節(jié)點(diǎn)的全局時鐘同步通過轉(zhuǎn)發(fā)一個同步包來完成。我們提出了一個基于幀格式全局時鐘

在全局同步階段，所有節(jié)點(diǎn)處于監(jiān)聽狀態(tài)。首先葉節(jié)點(diǎn)發(fā)送一個同步控制幀AST－RTS，通過多跳傳輸這個控制幀，每個節(jié)點(diǎn)收到這個控制幀，保存自己的調(diào)度表。ASTRTS幀采用了跨層的路由信息，Source＿id發(fā)送數(shù)據(jù)幀的節(jié)點(diǎn)號，Target＿id是發(fā)送數(shù)據(jù)幀的下一跳節(jié)點(diǎn)號，Send＿time是節(jié)點(diǎn)發(fā)送數(shù)據(jù)幀的時間，Next＿send＿time是節(jié)點(diǎn)發(fā)送下一個數(shù)據(jù)幀的時間，Info＿type是發(fā)送數(shù)據(jù)幀同步[6]的思想。首先，我們給出AST－MAC協(xié)議中各個包的幀格式，如圖1所示，下面是一些幀的格式。

從圖1可以看出同步控制幀AST－RTS和數(shù)據(jù)幀DATA的格式基本一致。因此兩個節(jié)點(diǎn)從準(zhǔn)備發(fā)送同步控制幀，并且傳輸同步控制幀，直至收到同步控制幀的時間間隔與節(jié)點(diǎn)傳輸數(shù)據(jù)幀近似一致。我們根據(jù)這個特點(diǎn)提出全局同步機(jī)制。AST－MAC的基本設(shè)計如圖2所示。的類型。

首先，葉節(jié)點(diǎn)A記下自己發(fā)送控制幀AST－RTS的時間Tsend＿time和發(fā)送下一個數(shù)據(jù)幀的時間Tnext＿send＿time，然后保存自己 （葉節(jié)點(diǎn)）的調(diào)度表，見表1。

并且轉(zhuǎn)發(fā)到下個節(jié)點(diǎn)B，節(jié)點(diǎn)B收到AST－RTS幀后記下接收時間Trecv＿time，則葉節(jié)點(diǎn)A傳輸給節(jié)點(diǎn)B的時間為如下

表1 葉節(jié)點(diǎn)的調(diào)度

于是可以確定B節(jié)點(diǎn)接收下一個數(shù)據(jù)幀的時間，根據(jù)控制幀AST－RTS和數(shù)據(jù)幀DATA的格式基本一致，節(jié)點(diǎn)A，B之間傳輸數(shù)據(jù)幀DATA所對應(yīng)的時間也應(yīng)該是TAB，而之前B節(jié)點(diǎn)接收到的控制幀的字段里有A節(jié)點(diǎn)發(fā)送下一個數(shù)據(jù)幀的時間Tnext＿time＿send＿A，可以確定B節(jié)點(diǎn)的接收時間如下

而實(shí)際在射頻模塊[7]中，從睡眠狀態(tài)轉(zhuǎn)化為監(jiān)聽狀態(tài)需要時間Tsleep＿tx，見表2。

表2 射頻模塊的狀態(tài)轉(zhuǎn)換

所以說節(jié)點(diǎn)B接收A節(jié)點(diǎn)發(fā)出下一個數(shù)據(jù)幀時間 （實(shí)際上是節(jié)點(diǎn)B的被喚醒時間）如下

而從接收狀態(tài)轉(zhuǎn)換到發(fā)送狀態(tài)需要時間Trx＿tx，所有調(diào)度表中next＿send＿time的值，如下

計算完畢之后，保存自己 （非葉節(jié)點(diǎn)）的調(diào)度表，見表3。

表3 非葉節(jié)點(diǎn)的調(diào)度

然后B根據(jù)跨層的路由信息將控制幀AST－RTS轉(zhuǎn)發(fā)給下一跳節(jié)點(diǎn)C，節(jié)點(diǎn)C收到控制幀AST－RTS之后，更新AST－RTS幀的發(fā)送時間、發(fā)送幀的節(jié)點(diǎn)號和發(fā)送幀的下一跳節(jié)點(diǎn)號，并且更新調(diào)度表中的next＿recv＿time和next＿send＿time的字段，此時，如圖2，節(jié)點(diǎn)A并沒有在睡眠狀態(tài)，而是在監(jiān)聽狀態(tài)，也會同時接收到節(jié)點(diǎn)B轉(zhuǎn)發(fā)的控制幀AST－RTS，得到A之前發(fā)送的隱式確認(rèn)，并且將葉節(jié)點(diǎn)A調(diào)度表中的send＿time置0，表示A發(fā)送的控制幀已經(jīng)成功轉(zhuǎn)發(fā)，之后A進(jìn)入睡眠狀態(tài)，所以說AST－RTS幀有RTS和CTS的兩個功能，并且在很短的監(jiān)聽時間內(nèi)可以轉(zhuǎn)發(fā)更多的跳數(shù)。在AST－RTS幀到達(dá)最后目的節(jié)點(diǎn)之前，節(jié)點(diǎn)A與節(jié)點(diǎn)B的握手機(jī)制也同樣在其它節(jié)點(diǎn)之間一直重復(fù)著。AST－RTS幀到達(dá)最后目的節(jié)點(diǎn)E，由于后面沒有節(jié)點(diǎn)了，E不需要轉(zhuǎn)發(fā)AST－RTS控制幀了，所以它的上一跳節(jié)點(diǎn)得不到這個隱式確認(rèn)，則節(jié)點(diǎn)E必須發(fā)送顯式確認(rèn)幀LST－ACK。

在全局同步階段，所有節(jié)點(diǎn) （非最終目的節(jié)點(diǎn)）接收到隱式確認(rèn)幀之后，都進(jìn)入睡眠狀態(tài)，如圖2，在sleep狀態(tài)，此時節(jié)點(diǎn)不能發(fā)送或者接收數(shù)據(jù)幀。在射頻處于接收狀態(tài)，節(jié)點(diǎn)接收它下一跳的確認(rèn)幀，然后節(jié)點(diǎn)進(jìn)入sleep狀態(tài)，此時不會接收到其它的節(jié)點(diǎn)發(fā)出的任何數(shù)據(jù)幀。顯然，這些節(jié)點(diǎn)大部分時間都在睡眠狀態(tài)。

在數(shù)據(jù)傳輸階段如圖2，與全局同步階段類似。節(jié)點(diǎn)根據(jù)自己的調(diào)度表喚醒自己，接收或者轉(zhuǎn)發(fā)數(shù)據(jù)幀，當(dāng)葉節(jié)點(diǎn)A調(diào)度表中next＿send＿time時間到了，節(jié)點(diǎn)A及時喚醒自己，將數(shù)據(jù)幀DATA轉(zhuǎn)發(fā)給下一跳節(jié)點(diǎn)B，并且更新數(shù)據(jù)幀DATA的字段和節(jié)點(diǎn)A調(diào)度表next＿send＿time的值，此時經(jīng)過TAB（數(shù)據(jù)幀從A傳輸給B的時間）后，由于先前節(jié)點(diǎn)B的調(diào)度表中已經(jīng)有next＿recv ＿time字段，所以B節(jié)點(diǎn)被喚醒處于監(jiān)聽狀態(tài)了，接收到數(shù)據(jù)幀之后，射頻模塊的狀態(tài)從接收狀態(tài)到發(fā)送狀態(tài)，更新數(shù)據(jù)幀DATA的字段和調(diào)度表next＿recv＿time，next＿send＿time的值，將數(shù)據(jù)幀DATA轉(zhuǎn)發(fā)給下一跳節(jié)點(diǎn)。同時A也會收到，相當(dāng)于A節(jié)點(diǎn)之前發(fā)送的隱式確認(rèn)，接收完之后，進(jìn)入睡眠狀態(tài)。最后一個節(jié)點(diǎn)需要發(fā)送一個顯式的確認(rèn)LAST＿ACK。很顯然，節(jié)點(diǎn)只有在轉(zhuǎn)發(fā)數(shù)據(jù)幀、接收確認(rèn)幀和數(shù)據(jù)幀的時候處在工作狀態(tài)，其余都處于睡眠狀態(tài)。通過保存節(jié)點(diǎn)的時間調(diào)度表，AST－MAC減少了數(shù)據(jù)幀轉(zhuǎn)發(fā)的延遲時間，并且，消除了列如CTS和ACK控制包的使用，從而減少了不必要的能量消耗。

1.2 調(diào)度沖突處理

在調(diào)度表保存期間，一些節(jié)點(diǎn)可能需要多個調(diào)度表，對于單個節(jié)點(diǎn)而言，調(diào)度時間可能會相同，導(dǎo)致傳輸數(shù)據(jù)幀發(fā)送沖突，也叫做調(diào)度沖突。圖3中顯示了調(diào)度沖突處理算法的處理流程。在圖3中，一個路由是從節(jié)點(diǎn)A到節(jié)點(diǎn)E，另外一個路由是從F到G。首先，節(jié)點(diǎn)F傳輸全局同步控制幀到節(jié)點(diǎn)G。節(jié)點(diǎn)D保存節(jié)點(diǎn)F到節(jié)點(diǎn)G的調(diào)度表。然后節(jié)點(diǎn)A傳輸全局同步控制幀到節(jié)點(diǎn)E，此時節(jié)點(diǎn)D又保存節(jié)點(diǎn)A到節(jié)點(diǎn)E的調(diào)度表。在實(shí)際應(yīng)用中，節(jié)點(diǎn)D的兩個調(diào)度表中的next＿send＿time的值大體接近，也就是D發(fā)送下一個數(shù)據(jù)幀，會產(chǎn)生沖突。此時節(jié)點(diǎn)D發(fā)送錯誤調(diào)度確認(rèn)幀ESK （ERROR－SCUDULE－ACK），通知這條路由上一跳節(jié)點(diǎn)C，C收到ESK幀后，在調(diào)度表中調(diào)整節(jié)點(diǎn)C發(fā)送時間Tadjust＿c，ESK幀包含時間戳t這個字段，Tadjust＿c是通過之前的調(diào)度表中的發(fā)送時間向下平移t，如下

節(jié)點(diǎn)D中的調(diào)度表 （路由從節(jié)點(diǎn)A到E）的next＿recv＿time，next＿send＿time字段的值也必須平移t個單位，如下

通過以上算法，避免了調(diào)度沖突。

1.3 數(shù)據(jù)錯誤傳輸處理

AST－MAC協(xié)議中，每個節(jié)點(diǎn)保存了自己的調(diào)度信息，并且根據(jù)自己的調(diào)度信息轉(zhuǎn)發(fā)數(shù)據(jù)幀，所有節(jié)點(diǎn)工作／休眠的時間是同步的。因此，如果一個路由中的兩個節(jié)點(diǎn)數(shù)據(jù)傳輸失敗，接下來后面所有節(jié)點(diǎn)的數(shù)據(jù)傳輸都將會失敗。

為了避免連鎖反應(yīng)的數(shù)據(jù)幀轉(zhuǎn)發(fā)失敗，我們采用了與類似于調(diào)度沖突的算法，利用時間平移，如圖表中所示，通過時間平移的方法來恢復(fù)節(jié)點(diǎn)之間的正常傳輸，這個平移時間的大小為如下

式中:Tdata1——兩個節(jié)點(diǎn)之間傳輸數(shù)據(jù)幀的時間，Tdata2——收到隱身確認(rèn)的時間，Δt——節(jié)點(diǎn)處理數(shù)據(jù)幀的時間。Tshift包括了一個節(jié)點(diǎn)的發(fā)送、接收確認(rèn)時間和處理數(shù)據(jù)幀的時間，可以通過這個時間來判斷數(shù)據(jù)幀的傳輸是否發(fā)生了錯誤。

我們可以通過圖4中看出，節(jié)點(diǎn)B向節(jié)點(diǎn)C傳輸數(shù)據(jù)，當(dāng)節(jié)點(diǎn)C收到數(shù)據(jù)幀之后，節(jié)點(diǎn)C發(fā)現(xiàn)這個數(shù)據(jù)幀是有問題的。于是節(jié)點(diǎn)C放棄了轉(zhuǎn)發(fā)這個數(shù)據(jù)幀，并調(diào)整自己的調(diào)度表，將自己的調(diào)度表中的所有時間向下平移Tshift，節(jié)點(diǎn)B在一定時間內(nèi)沒有得到隱式確認(rèn)，則將自己的調(diào)度表中的send＿time向下平移Tshift。同樣的，后面節(jié)點(diǎn)在監(jiān)聽時間內(nèi)沒有收到任何數(shù)據(jù)幀，則都將自己的調(diào)度表的時間向下平移Tshift時間，然后進(jìn)入睡眠狀態(tài)。

通過這種方法，節(jié)點(diǎn)之前保存的調(diào)度表并沒有丟棄，而是被充分利用了。但是，太多的平移調(diào)度會消耗更多的能量，所以說，對于整個網(wǎng)絡(luò)而言，平移調(diào)度的次數(shù)是受限制的。整個網(wǎng)絡(luò)時間平移一次后，基本恢復(fù)正常了。

2 仿真測試與性能評估

2.1 實(shí)驗(yàn)的主要目標(biāo)

我們實(shí)驗(yàn)的主要目標(biāo)是通過與其它的一些MAC協(xié)議如S－MAC，802.15.4[8]，PAMC，對 AST－MAC協(xié)議的性能進(jìn)行評估。我們通過3個性能指標(biāo)能衡量MAC協(xié)議性能:端 到端的平均延遲[9]；吞吐率[9]，即單位時間接收數(shù)據(jù)幀的總字節(jié)數(shù)；網(wǎng)絡(luò)的能量消耗[9]，即完成某項(xiàng)任務(wù)的消耗的總能量。

2.2 端到端的平均延遲

每個MAC協(xié)議的端到端平均延遲如圖5所示。為了測量這個延遲時間，網(wǎng)絡(luò)中的源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的時鐘是同步的。首先，源節(jié)點(diǎn)將發(fā)送的起始時間加入發(fā)送幀，然后通過最終的目標(biāo)節(jié)點(diǎn)計算端到端的平均延遲。與其它MAC協(xié)議相比，盡管AST－MAC也采用偵聽和睡眠交替的策略，但它具有更少的延遲時間。

2.3 吞吐量

通過圖6中，我們可以看出AST－MAC協(xié)議具有最好的吞吐量。802.15.4協(xié)議的吞吐率中略低于AST－MAC協(xié)議，因?yàn)?02.15.4協(xié)議隨著傳輸時間間隔減少，碰撞的幾率增加，導(dǎo)致數(shù)據(jù)幀的重傳，所以吞吐量略有降低。而SMAC和PA－MAC協(xié)議吞吐量降低了很多。

2.4 能量消耗

射頻狀態(tài)時間比如圖7所示，其中源節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)幀的間隔時間為2s，測量時間是500s，其中，由圖7可以看出，802.15.4協(xié)議的大部分時間用在空閑監(jiān)聽上，其它的MAC協(xié)議通過偵聽和睡眠交替的策略減少了空閑監(jiān)聽時間。在源節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)幀的間隔時間為2s的時候如圖6，AST－MAC協(xié)議與PAMAC有相同的吞吐率。但是ASTMAC有更少的空閑的監(jiān)聽時間。

一個數(shù)據(jù)幀被轉(zhuǎn)發(fā)所消耗的能量如圖8，以上測試的所有協(xié)議中，AST－MAC協(xié)議消耗最少的能量。

3 結(jié)束語

基于非競爭類的MAC[10]大都采用周期性偵聽／睡眠機(jī)制來減少空閑監(jiān)聽能耗，但是過多的睡眠帶來了通信延遲和很低的吞吐量。針對這些問題，本文提出了一種新型的能夠?qū)崿F(xiàn)快速轉(zhuǎn)發(fā)的傳感器網(wǎng)絡(luò)AST－MAC協(xié)議。這個協(xié)議[11]也是基于周期性的偵聽／睡眠，它可以減少不必要的能耗，而且大大減少了通信延遲，提高了吞吐量。ASTMAC協(xié)議通過轉(zhuǎn)發(fā)數(shù)據(jù)包的時候，保存節(jié)點(diǎn)監(jiān)聽／睡眠的時間調(diào)度表。在實(shí)際應(yīng)用中，針對存在調(diào)度沖突數(shù)、數(shù)據(jù)包錯誤傳輸?shù)膯栴}，AST－MAC協(xié)議提出了時間戳平移的算法。我們的仿真實(shí)驗(yàn)表明AST－MAC協(xié)議有延遲低，高吞吐率，能耗低的特點(diǎn)。

[1]ZHANG Jiawei，CHEN Yan，LI Mingbao.Energy－efficient framing MAC protocol for wireless sensor networks[J].Information and Control，2013，35 （22）:95－99 （in Chinese）.[張佳薇，陳巖，李明寶.用于無線傳感器網(wǎng)絡(luò)的高能效分幀MAC協(xié)議[J].信息與控制，2013，35 （22）:95－99.]

[2]Liu Ana，Li Lin，Yu Hongyi，et al.An energy—eficient MAC protocol based on routing information for wireless sensor networks[C]／／Hong Kong，China:Proceedings of IEEE Wireless Communications and Networking Conference，2008.

[3]Zhang Ye，Chen He，Jiang Lingge.Modeling the S－MAC protocol in single－h(huán)op wireless sensor networks[C]／／IEEE Technology Management Council，IEEE Communications Society.Proceedings of the Symposium on Communication Quality，Reliability，and Performance Modeling of ICC，2008:5－6.

[4]DING Fan，ZHOU Yongming.Adaptive cross－layer optimization strategy for the throughput of wireless sensor network[J].Microcontroller and Embedded Systems，2013，25 （5）:5－8（in Chinese）.[丁凡，周永明.無線傳感器網(wǎng)絡(luò)吞吐量的自適應(yīng)跨層優(yōu)化策略[J].單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2013，25 （5）:5－8.]

[5]WANG Mingchao.LR－MAC mechanism for the low－speed wireless sensor networks[J].Zhengzhou Institute of Light Industry（Natural Science Edition），2012，32 （6）:101－104 （in Chinese）.[王明超.一種適用于低速無線傳感器網(wǎng)絡(luò)的LRMAC機(jī)制研究[J].鄭州輕工業(yè)學(xué)院學(xué)報 （自然科學(xué)版），2012，32 （6）:101－104.]

[6]Xiao Y，Pan Y.Differentiation，QoS guarantee，and optimization for real－time traffic over one－h(huán)op Ad hoc networks[C]／／IEEE Transaction on Parallel Distributed Systems，2009:100－101

[7]Omprakash G，Rodrigo F.Collection tree protocol[C]／／Proc of the 7th ACM Conf on Embedded Networked Sensor Systems，2009.

[8]Ye W，Heidemann J，Estrin D.An energy－elficient MAC protocol for wireless sensor network[C]／／Proceedings of the 12th IEEE International Conference on Computer Networks，2011:1567－1576.

[9]Randran V，Obraczka K，Gareia－Luna－Aceves J J.energy—eficient，collision—free medium access control for wireless sensor networksp[C]／／Los Angeles，CA:Proc1st int’l Conf on Embedded Networked Sensor Systems，2003:181－192.

[10]JIANG Ziifeng，LU Jiande.Dynamic adaptive CSMA／CA algorithm design and simulation for the IEEE 802.15.4[J].Computer Technology and Development，2010，33 （2）:69－73 （in Chinese）.[蔣子峰，陸建德.IEEE 802.15.4動態(tài)自適應(yīng)CSMA／CA算法設(shè)計與仿真[J].計算機(jī)技術(shù)與發(fā)展，2010，33 （2）:69－73.]

[11]Wei Ye，John Heidemann，Deborah Estrin.Medium access control with coordinated adaptive sleeping for wireless sensor networks[C]／／IEEE／ACM Trans Netw，2009:493－506.