基于時間調度表的無線傳感器網絡MAC協議

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

（重慶郵電大學 計算機系統結構研究所，重慶400065）

0 引 言

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

為了減少網絡的延遲時間，PA－MAC[3]（Pattern－MAC）在S－MAC和T－MAC[4]協議的基礎上，進一步減少了空閑偵聽的時間。PA－MAC減少了空閑偵聽的時間，但是傳輸的一些模式幀，并沒有實際意義。而且協議的執行非常復雜，增加了節點的控制開銷?？傊?，這些協議[5]并不能使節點在多跳網絡傳輸中保持監聽狀態，它們仍然存在很長的延遲時間。為了減少延遲時間，我們提出了AST－MAC協議，AST－MAC協議跟S－MAC類似，也是基于工作／休眠機制。

在這篇論文中，我們設計并實現了AST－MAC協議，我們增加了提高吞吐率的算法，這個算法讓節點保存下一個數據分組轉發的時間調度表。通過節點之間的數據分組的傳輸，從而形成了節點監聽／睡眠的同步。利用這個算法，網絡的吞吐量提高了很多。

1 AST－MAC協議設計和改進

1.1 AST－MAC的設計

AST－MAC協議算法依賴于精確的時鐘信息，因此節點間的時鐘同步相當重要。節點的全局時鐘同步通過轉發一個同步包來完成。我們提出了一個基于幀格式全局時鐘

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

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

首先，葉節點A記下自己發送控制幀AST－RTS的時間Tsend＿time和發送下一個數據幀的時間Tnext＿send＿time，然后保存自己 （葉節點）的調度表，見表1。

并且轉發到下個節點B，節點B收到AST－RTS幀后記下接收時間Trecv＿time，則葉節點A傳輸給節點B的時間為如下

表1 葉節點的調度

于是可以確定B節點接收下一個數據幀的時間，根據控制幀AST－RTS和數據幀DATA的格式基本一致，節點A，B之間傳輸數據幀DATA所對應的時間也應該是TAB，而之前B節點接收到的控制幀的字段里有A節點發送下一個數據幀的時間Tnext＿time＿send＿A，可以確定B節點的接收時間如下

而實際在射頻模塊[7]中，從睡眠狀態轉化為監聽狀態需要時間Tsleep＿tx，見表2。

表2 射頻模塊的狀態轉換

所以說節點B接收A節點發出下一個數據幀時間 （實際上是節點B的被喚醒時間）如下

而從接收狀態轉換到發送狀態需要時間Trx＿tx，所有調度表中next＿send＿time的值，如下

計算完畢之后，保存自己 （非葉節點）的調度表，見表3。

表3 非葉節點的調度

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

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

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

1.2 調度沖突處理

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

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

通過以上算法，避免了調度沖突。

1.3 數據錯誤傳輸處理

AST－MAC協議中，每個節點保存了自己的調度信息，并且根據自己的調度信息轉發數據幀，所有節點工作／休眠的時間是同步的。因此，如果一個路由中的兩個節點數據傳輸失敗，接下來后面所有節點的數據傳輸都將會失敗。

為了避免連鎖反應的數據幀轉發失敗，我們采用了與類似于調度沖突的算法，利用時間平移，如圖表中所示，通過時間平移的方法來恢復節點之間的正常傳輸，這個平移時間的大小為如下

式中:Tdata1——兩個節點之間傳輸數據幀的時間，Tdata2——收到隱身確認的時間，Δt——節點處理數據幀的時間。Tshift包括了一個節點的發送、接收確認時間和處理數據幀的時間，可以通過這個時間來判斷數據幀的傳輸是否發生了錯誤。

我們可以通過圖4中看出，節點B向節點C傳輸數據，當節點C收到數據幀之后，節點C發現這個數據幀是有問題的。于是節點C放棄了轉發這個數據幀，并調整自己的調度表，將自己的調度表中的所有時間向下平移Tshift，節點B在一定時間內沒有得到隱式確認，則將自己的調度表中的send＿time向下平移Tshift。同樣的，后面節點在監聽時間內沒有收到任何數據幀，則都將自己的調度表的時間向下平移Tshift時間，然后進入睡眠狀態。

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

2 仿真測試與性能評估

2.1 實驗的主要目標

我們實驗的主要目標是通過與其它的一些MAC協議如S－MAC，802.15.4[8]，PAMC，對 AST－MAC協議的性能進行評估。我們通過3個性能指標能衡量MAC協議性能:端 到端的平均延遲[9]；吞吐率[9]，即單位時間接收數據幀的總字節數；網絡的能量消耗[9]，即完成某項任務的消耗的總能量。

2.2 端到端的平均延遲

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

2.3 吞吐量

通過圖6中，我們可以看出AST－MAC協議具有最好的吞吐量。802.15.4協議的吞吐率中略低于AST－MAC協議，因為802.15.4協議隨著傳輸時間間隔減少，碰撞的幾率增加，導致數據幀的重傳，所以吞吐量略有降低。而SMAC和PA－MAC協議吞吐量降低了很多。

2.4 能量消耗

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

一個數據幀被轉發所消耗的能量如圖8，以上測試的所有協議中，AST－MAC協議消耗最少的能量。

3 結束語

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

[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）.[張佳薇，陳巖，李明寶.用于無線傳感器網絡的高能效分幀MAC協議[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－hop 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）.[丁凡，周永明.無線傳感器網絡吞吐量的自適應跨層優化策略[J].單片機與嵌入式系統應用，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）.[王明超.一種適用于低速無線傳感器網絡的LRMAC機制研究[J].鄭州輕工業學院學報 （自然科學版），2012，32 （6）:101－104.]

[6]Xiao Y，Pan Y.Differentiation，QoS guarantee，and optimization for real－time traffic over one－hop 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動態自適應CSMA／CA算法設計與仿真[J].計算機技術與發展，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.