祝家鈺，龍昭華，馬永建

(重慶郵電大學(xué) 計算機網(wǎng)絡(luò)與通信技術(shù)市級重點實驗室，重慶400065)

0 引 言

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

1 X－MAC 協(xié)議分析

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

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

2 Ex－MAC 協(xié)議的設(shè)計

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

2.1 基于單跳節(jié)點的NDC 算法

無線傳感器網(wǎng)絡(luò)的每個節(jié)點將會一直管理自己鄰居節(jié)點的信息［8］?；诖嗽O(shè)計了NDC 算法，該算法中每個節(jié)點的路由信息表里面有所有其它鄰居節(jié)點的喚醒時間和工作周期的信息，這些信息將會被周期性傳輸?shù)臄?shù)據(jù)及時更新。通過NDC 算法，發(fā)送節(jié)點不需要發(fā)送多次短前導(dǎo)碼之后才可以收到EACK 幀了。相鄰節(jié)點的工作周期近似于同步，并且不需要任何周期性控制幀。NDC 控制算法有以下步驟:

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

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

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

NDC 算法已經(jīng)大大減少了前導(dǎo)碼重新傳輸?shù)拇螖?shù)，也同時減少數(shù)據(jù)傳輸?shù)难舆t。

2.2 基于多跳網(wǎng)絡(luò)的VC 算法

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

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

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

VC 建立的主要目的是與NDC 算法相結(jié)合，在多跳網(wǎng)絡(luò)中減少數(shù)據(jù)傳輸?shù)臅r延。

2.3 NDC 算法在VC 環(huán)境下的描述

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

1)基于NDC 算法的VC 建立

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

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

2)基于NDC 算法的VC 傳輸

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

將NDC 和VC 算法結(jié)合在一起形成了Ex－MAC 協(xié)議，實現(xiàn)了通道內(nèi)的所有節(jié)點同步。

3 仿真與實驗分析

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

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

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

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

圖5 能量的消耗Fig 5 Energy consumption

綜上所述，Ex－MAC 協(xié)議通過NDC 算法和VC 算法，讓節(jié)點之間獲得近似于同步的工作周期，但是它仍然使用短前導(dǎo)碼協(xié)議算法，不需要像同步MAC 協(xié)議需要周期性交換自身的信息，減少了網(wǎng)絡(luò)傳輸?shù)难舆t、提高了網(wǎng)絡(luò)的健壯性。

4 結(jié) 論

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

［1］ 蹇 強，龔正虎，朱培棟，等.無線傳感器網(wǎng)絡(luò)MAC 協(xié)議研究進展［J］.軟件學(xué)報，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］ 李洪峻，李 迅，馬宏緒.無線傳感器網(wǎng)絡(luò)MAC 協(xié)議實時性研究［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］洪 利，黃庭培，鄒衛(wèi)霞，等.基于鏈路可用性預(yù)測的AODV路由協(xié)議研究［J］.通信學(xué)報，2008，29(7):118－123.

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