一種低延時的無線傳感器網絡MAC 協議*

祝家鈺，龍昭華，馬永建

(重慶郵電大學 計算機網絡與通信技術市級重點實驗室，重慶400065)

0 引 言

媒體訪問控制(medium access control，MAC)層協議決定無線傳感器網絡(wireless sensor networks，WSNs)信道的使用方式并分配有限的無線信道資源。可拓展性和能量利用率是MAC 協議主要考慮的因素［1］，而傳輸延遲和公平原則是其次考慮的性能指標［2］。在現有無線傳感器網絡MAC 協議中，X－MAC 是一種較典型的基于競爭機制的協議，其算法減少了不必要的控制開銷和能量浪費，但它在網絡負載比較大或者多跳的應用場景下，端到端的延遲較大。為了降低X－MAC 協議的傳輸延時，改進設計了一種擴展的X－MAC 協議Ex－MAC(extensible X－MAC)，它在X－MAC 協議中增加了NDC(neighbor’s duty cycle)和虛擬通道(virtual channel，VC)控制算法，使節點之間不需要交換同步控制幀，卻可以近似于同步，從而減小數據傳輸延遲。

1 X－MAC 協議分析

在X－MAC 協議中［3］，長前導碼被劃分成連續的短前導碼，每個短前導碼包含目標節點的ID 號。當一個接收節點周期性醒來并且檢測到短前導碼的時候，若發現前導碼并不是發送給自己的，這個節點將立即進入睡眠狀態，仍然繼續按照自己的工作周期進行調度。如果自己是目標節點，它將一直保持監聽狀態來等待發送節點傳輸實際的數據。在X－MAC 協議中，非目標節點將很快進入睡眠狀態，避免了長時間的串聽，能量消耗受到網絡密度的影響顯著減小了［4］。當發送節點的鄰居節點數目增加的時候，網絡整體的能量消耗并沒有明顯增加。X－MAC 協議還在連續的短前導碼之間插入一個小的時間片，以便發送節點用來監聽信道。當然，接收前導碼的節點就盡可能地利用這個小時間片向發送節點發送和早確認(early acknowledgment，EACK)幀［5］。當發送節點從接收節點那兒收到EACK 幀的時候，它立即停止發送前導碼，緊接著發送數據包。接收節點通過“主動”的方式減小了發送短前導碼的次數，減少了一跳之間的數據延遲和不必要的能量消耗［6］。發送節點發送完數據，很快地進入睡眠狀態。另外，X－MAC 采用了周期信道采樣和低功耗偵聽(low power listening，LPL)機制，不需要交換同步控制幀［7］。

在星型網絡中，X－MAC 協議大大減少了數據的延遲和提高了能量的利用率，但是在網絡的節點和跳數比較多的應用場景，它的效果并不理想，端到端會產生很長的延遲時間。因為每個相鄰節點的喚醒時間與產生前導碼的時間肯定不能夠完全匹配。單獨一跳的時延可能可以滿足要求，如果跳數多了，且每一跳都必須等待下一個節點喚醒之后才可以轉發數據，那么傳輸時延就會累積很多。另外，許多節點同時發送前導碼，導致前導碼沖突，節點必須重新傳輸短前導碼也造成時延。

2 Ex－MAC 協議的設計

在能量消耗不會增加的情況下，為了減少X－MAC 協議端到端的延遲，本文提出了擴展X－MAC 協議Ex－MAC，該協議讓虛通道的所有節點之間獲得近似于同步的工作周期，而且仍然使用X－MAC 的短前導碼協議算法，但增加了NDC 和VC 控制算法，通過估算特定路由的上一跳節點發送前導碼的時間，讓傳輸路徑上的節點獲得近似同步的工作周期［8］。

2.1 基于單跳節點的NDC 算法

無線傳感器網絡的每個節點將會一直管理自己鄰居節點的信息［8］。基于此設計了NDC 算法，該算法中每個節點的路由信息表里面有所有其它鄰居節點的喚醒時間和工作周期的信息，這些信息將會被周期性傳輸的數據及時更新。通過NDC 算法，發送節點不需要發送多次短前導碼之后才可以收到EACK 幀了。相鄰節點的工作周期近似于同步，并且不需要任何周期性控制幀。NDC 控制算法有以下步驟:

1)為了知道鄰居節點部分信息，發送節點在第一次傳輸前導碼的時候必須包括以下信息:重新傳輸間隔時間(retransmission interval time，RIT)、重新傳輸的次數(retransmission count，RC)、持續的工作周期(duty cycle duration，DD)。

2)當接收節點喚醒的時候，收到任何一個前導碼之后，都能通過RIT 和RC 計算發送節點的第一個前導碼的發送時間，還可以通過以上的一些字段和DD 計算發送節點的喚醒時間。

3)最后，接收節點將計算出來的喚醒時間和DD 保存在節點表里面。

NDC 算法已經大大減少了前導碼重新傳輸的次數，也同時減少數據傳輸的延遲。

2.2 基于多跳網絡的VC 算法

VC 算法中的虛通道是基于邏輯層面上的，它將會在第一次數據交換之后建立起來，可以保證多跳環境下的實時性傳輸［9］。具體地說，當一個事件發生，VC 將會被建立起來，當傳輸結束后，VC 被撤銷。

圖1 描述了VC 的形成過程，在開始階段，VC 并沒有形成。當一個突發性事情發生時，節點A 發現異常情況，將現場的信息采集起來，然后將數據轉發到最終目標節點E。由于節點A 與節點E 不在同一個通信范圍內，所以，節點A首先必須將數據發送中間節點B，這個過程并不是為了將數據通過多跳節點傳輸到最終節點E，而是為了建立VC。當節點B 收到A 的數據包之后，立即給節點A 發送一個EACK 幀(與前導碼采樣算法一樣)，EACK 幀里面有TA(tunnel acknowledge)字段，當節點A 收到EACK 幀，并且解析這個幀里面有TA 這個字段，節點A 將不再改變拓撲結構，從而與節點B 形成一個VC。在到達最終目標節點之前，所有的中間節點將不斷地交換數據包和EACK 幀。最后，VC 通過一連串節點建立起來。在建立過程中，只有數據和EACK 幀，并不需要其它多余的數據包。

圖1 VC 的建立過程Fig 1 Creation process of VC

VC 建立的主要目的是與NDC 算法相結合，在多跳網絡中減少數據傳輸的時延。

2.3 NDC 算法在VC 環境下的描述

當一個突發性的事情發生的時候，現場的節點需要采集數據，并將它發送到目的節點，可以完全不用考慮整體的網絡拓撲結構［10］，轉發的拓撲結構臨時地被認為線性結構，數據幀通過這種線性拓撲進行轉發。其中，所有轉發節點都是VC 的成員。該算法將前導碼直接改成了數據幀，用來與喚醒接收節點。算法分為兩個步驟:

1)基于NDC 算法的VC 建立

若現場有事故發生了，如圖2 非陰影部分，現場節點A將采集到的數據連續發送給目的節點D，假設節點A，B，C，D 在同一個線性結構上，A 節點與D 節點不在同一個通信范圍內，在初始化通道階段，所有節點不知道其它鄰居節點的喚醒時間，按照自己的工作周期在監聽和睡眠之間交替。首先，節點D 每隔RIT 時間向節點C 發送數據，每重發一次，RC 自增1，直到節點D 收到節點C 的EACK 確認。其中，EACK 里面有CA 字段，此時節點C、節點D 之間VC 就建立了，緊接著節點C 根據剛才收到的數據中的RC 值，繼續向下一跳節點B 發送數據幀，每重發一次，RC 值不斷加1，直到其收到EACK 確認幀。中間節點不斷交換著數據幀和EACK 幀，直到最終目的節點才結束，這樣，節點D 到節點A 的VC 就建立起來了。

圖2 VC 中的NDC 算法Fig 2 NDC algorithm in VC

2)基于NDC 算法的VC 傳輸

建立VC 之后，如圖2，中間的轉發節點將根據計算出來的Wn+1值自動喚醒，其中，Wn+1表示第n+1 次喚醒時間。當Wn+1時間到了，C 節點在第n+1 次自動喚醒，監聽節點D 發送的第n+1 次數據。同理，當B 節點的Wn+1時間到了，中間節點B 將喚醒，監聽C 節點發送的數據，并且更新RC 的值。最后，A 節點收到數據，同時更新，RC 的值。盡管節點A 與節點D 不在同一個通信范圍內，也完全可以實現兩個節點的同步。

將NDC 和VC 算法結合在一起形成了Ex－MAC 協議，實現了通道內的所有節點同步。

3 仿真與實驗分析

本文采用的是NS 2［11］的2.34 版本作為實驗平臺。測試性能指標為算法的吞吐量、工作負載和端到端的平均時延，同時實現了X－MAC 和Ex－MAC 協議。圖3 是多跳傳輸環境下的端到端平均傳輸時延。在跳數比較少的情況下，X－MAC 與Ex－MAC 傳輸延遲大體相等。這是因為在Ex－MAC 協議中，雖然通過VC 和NDC 算法可以減少端到端的延遲，但是建立VC 需要一定的時間，而且在跳數比較少的情況下，X－MAC 協議延遲較小。但在跳數越來越多的情況下，X－MAC 協議延遲大大增加，而Ex－MAC 協議的延遲與之前相比比較平穩，因為NDC 算法在多跳環境中減少了延遲，多跳路徑的每個節點幾乎同步。

圖3 不同跳數的端到端延遲Fig 3 End-to-end latency under different number of hops

從圖3 ～圖5 中可以看出:在網絡中的傳輸量比較小的情況下，Ex－MAC 協議與X－MAC 協議的延遲和能量消耗相似。因為此時網絡負載比較小，碰撞幾率都比較低，所以，重新傳輸的幾率也不大，導致數據產生延遲和能量消耗也不是很大。當負載比較大的時候，X－MAC 協議的延遲和能量消耗陡然提高，甚至遠遠超過Ex－MAC 協議，這是由于X－MAC 協議中每個節點不知道鄰居節點的工作周期，均以自己的工作周期工作，數據包之間容易產生碰撞，發送節點可能發送數次短前導碼才能收到EACK 幀，網絡會消耗更多的能量和產生數據延遲。Ex－MAC 協議中，多跳路徑上的所有節點近似于同步，能量消耗不隨著網絡負載增加而增加。

圖4 不同傳輸節點個數的端到端延遲Fig 4 End-to-end latency with different number of transmission nodes

圖5 能量的消耗Fig 5 Energy consumption

綜上所述，Ex－MAC 協議通過NDC 算法和VC 算法，讓節點之間獲得近似于同步的工作周期，但是它仍然使用短前導碼協議算法，不需要像同步MAC 協議需要周期性交換自身的信息，減少了網絡傳輸的延遲、提高了網絡的健壯性。

4 結 論

本文在X－MAC 協議的基礎上提出了Ex－MAC 協議。針對X－MAC 協議在節點密度大和多跳環境端到端的平均延遲比較大的情況，提出了NDC 和VC 算法，使得VC 的所有節點將會有與源節點保持近似同步的工作周期。仿真結果表明:Ex－MAC 保持了與X－MAC 相近的節能效率，卻能明顯改善X－MAC 端到端的平均延遲。。

［1］ 蹇 強，龔正虎，朱培棟，等.無線傳感器網絡MAC 協議研究進展［J］.軟件學報，2008，19(2):389－403.

［2］ Halkes G P，Langendoen K G.Experimental evaluation of simulation abstractions for wireless sensor networks Mac protocols［J］.EURASIP Journal on Wireless Communications and Networking，2010(4):139－145.

［3］ Yang O，Heinzelman W B.Modeling and throughput analysis for X－MAC with a finite queue capacity［C］∥2010 IEEE Global Telecommunications Conference，GLOBECOM 2010，IEEE，2010:1－5.

［4］ Bachir A，Dohler M，Watteyne T，et al.MAC exsentials for wireless sensor networks［J］.Communications Surveys＆Tutorials，IEEE，2010，12(2):222－248.

［5］ 李洪峻，李 迅，馬宏緒.無線傳感器網絡MAC 協議實時性研究［J］.計算機工程，2009，35(23):78－80.

［6］ Yang O，Heinzelman W B.Modeling and performance analysis for duty－cycled MAC protocols with applications to S－MAC and XMAC［J］.IEEE Transactions on Mobile Computing，2012，11(6):905－921.

［7］ Wu Y，Li X Y，Li M，et al.Energy－efficient wake－up scheduling for data collection and aggregation［J］.IEEE Transactions on Parallel and Distributed Systems，2010，21(2):275－287.

［8］ Noh k，Serpedin E，Qaraqe k.A new approach for time synchronization in wireless sensor networks:Pairwise broadcast synchronization［J］.IEEE Transations on Wireless Communications，2008，7(9):3318－3322.

［9］ Khan B M，Ali F H.Collision free mobility adaptive(CFMA)MAC for wireless sensor networks［J］.Telecommunication Systems，2013，52(4):2459－2474.

［10］Lee M，Kim Y，Cgo C.Period－controlled MAC for high performance in wireless networks［J］.IEEE/ACM Transactions on Networking，2011，19(4):1237－1250.

［11］洪 利，黃庭培，鄒衛霞，等.基于鏈路可用性預測的AODV路由協議研究［J］.通信學報，2008，29(7):118－123.

［12］石為人，黃 河，鮮曉東，等.OMNET++與NS2 在無線傳感器網絡仿真中的比較研究［J］.計算機科學，2008，35(10):53－57.