低占空比、低碰撞的異步無線傳感器網絡MAC協議

李哲濤，朱更明，王志強，裴廷睿，潘高峰

（1. 湘潭大學 信息工程學院，湖南 湘潭 411105；2. 國防科學技術大學 計算機學院，湖南 長沙 410073；3. 湘潭大學 智能計算與信息處理教育部重點實驗室，湖南 湘潭 411105；4. 湖南科技大學 計算機科學與工程學院，湖南 湘潭 411201；5. 西南大學 電子信息工程學院，重慶 400715）

1 引言

無線傳感器網絡（WSN, wireless sensor network）由分布在一定區域內大量電池供電的傳感器節點組成，采用無線通信的方式形成多跳自組織網絡。由于其監控區域廣、無人值守等優點，WSN被廣泛應用到農業種植、醫療監控、智能家居、智能交通等生活的各個領域，尤其是災后重建、突發事件監控等[1]。電池能量直接影響傳感器和網絡生存周期，因此，研究一種低耗能、輕負載協議成為WSN領域的熱點。媒體訪問控制（MAC, medium access control）協議是數據報文和控制消息在無線信道上進行收發的直接控制者，也間接影響上層路由協議和傳輸控制協議性能。因此，高效的MAC協議是保證WSN數據服務質量（QoS, quality of service）的基礎[2]。

根據節點時間是否同步，可將現有MAC協議分為2類：同步和異步MAC協議。同步MAC協議（如 S-MAC[3]、TMAC[4]、SCP[5]和 DW-MAC[6]）通過節點同步的喚醒/休眠機制來減少能量消耗，但全網時間同步會帶來不可忽略的能量消耗[7,8]。

異步 MAC協議又可分為由發送節點發起的MAC 接入協議（如 B-MAC[9]、X-MAC[10]、O-MAC[11]和Wise MAC[12])和由接收節點發起的MAC接入協議（如RI-MAC[13]）2種類型[14]。由發送節點發起的MAC接入協議是指由發送者發送前同步碼報頭（preamble）來通知目標節點準備接收數據；由接收節點發起的MAC接入協議是指發送節點醒來偵聽，等待接收節點發送的信標（beacon）分組的到來再發送數據。異步MAC協議無需時間同步，并且異步周期的工作模式能減少網絡中流量猝發所帶來的碰撞。一般來說，在異步MAC協議中，發送節點的占空比要遠比接收節點的占空比高。

B-MAC是一種基于CSMA的異步MAC協議。它通過使用低能耗偵聽和持續的前同步碼報文實現低能耗通信。另外，它通過動態調節休眠時間表來改變網絡流量負載。然而，串音問題和冗長的前同步碼帶來了較大的能量損耗。

X-MAC通過使用多個較小的前同步碼報文來解決B-MAC中的串音問題。通過在前同步碼中嵌入目標節點地址引導鄰居中非目標接收節點進入休眠，達到節能的目的。然而，持續的前同步碼仍然占據著信道，降低了信道利用率。

Wise MAC通過固定的喚醒間隔減少前同步碼的長度。同時，發送節點通過采樣目標節點時間表預測其下一次喚醒時間，降低了占空比。該協議雖然減少了空閑監聽開銷，但固定的時間表易導致連續的碰撞。

RI-MAC是由接收節點發起建立連接的異步MAC協議，發送節點只需醒來偵聽目標節點的信標幀而不用占據信道，提高了信道利用率。然而，發送節點平均仍需半個周期等待目標節點的信標幀，空閑偵聽耗能較大。

另外，現有的MAC協議大多采用二進制指數退避算法[14]來解決分組丟失重傳問題。這類算法總是給予最后一次發送成功的節點以最大的優先權，易導致不公平現象。當網絡節點較多時，節點每次成功發送后都將競爭窗口重置為最小值，易引起碰撞。

為降低能耗、減少數據碰撞，本文提出了一種由發送節點發起建立連接的異步低占空比、低碰撞的PB-MAC（predict-base MAC）協議算法。在PB-MAC中，節點通過偽隨機數生成偽隨機喚醒時間表。發送節點可通過獲取接收節點的隨機種子、當前時間和最近一次喚醒時間信息精確地推導出接收節點的下一次喚醒時間。與其他具有預測功能的MAC協議(如Wise MAC[12])相比，在PB-MAC中，節點能快速預測目標節點的醒來時間，并能減少碰撞。PB-MAC只需在預測目標節點喚醒時間偵聽信道，因此，在發送節點和接收節點都能保持極低的占空比。另外，PB-MAC報頭僅需攜帶極小量的預測信息，具有通信開銷小和報頭短的特征。

2 PB-MAC的算法設計

PB-MAC的目標是設計一種以發送節點發起建立連接的低占空比、低碰撞的異步MAC協議。

2.1 基本工作原理

PB-MAC協議基于RTS/CTS/Data/ACK的通信過程，節點隨機喚醒偵聽，如果在一個給定的信道偵聽時間（TA，time active）內沒有發生激活事件，則進入休眠狀態。節點醒來后偵聽信道時間需滿足：

其中，RTT為端到端往返時延，sT為節點由休眠狀態啟動為工作狀態所需要的時間。

圖1 PB-MAC協議的基本機制

在PB-MAC中，節點首次在[0,T]（T為節點喚醒的平均時間周期）之間隨機喚醒進入活動狀態，之后仍采取隨機喚醒機制。圖1為PB-MAC協議的基本機制，圖中向上的箭頭表示發送消息，向下的箭頭表示接收消息，上面部分的信息流表示節點一直處于偵聽方式下的消息收發序列，下面部分的信息流表示采用PB-MAC協議時的消息收發序列。圖1中節點首次在14 ms喚醒，隨后依隨機數89、129和76在103 ms、232 ms和308 ms分別喚醒。

2.2 偽隨機喚醒時間表機制

為了預測目標節點的喚醒時間和避免鄰居節點喚醒時間頻繁接近，PB-MAC中每個節點采用偽隨機喚醒時間表。節點通過與鄰居節點共享隨機種子來推導對方產生偽隨機喚醒時間表的偽隨機數。

為了使節點間隨機種子不同并且可在相鄰節點種子相近的情況下更改，節點產生偽隨機數的隨機種子Seed采用線性同余(LCG, linear congruential generator)[15]的方法產生，如式(2)所示。

其中，m(m＞0)是模數，a(0

其中，RandNum為每調用一次rand方法產生的隨機數。節點將產生的隨機數RandNum作為節點喚醒時間間隔，生成偽隨機時間表。

因此，通過獲取鄰居節點的隨機種子同樣可以推導出其喚醒時間表的喚醒時間間隔。

2.3 預測目標節點喚醒時間算法

PB-MAC協議的報頭（beacon分組）包含節點的隨機種子Seed、最近一次喚醒時間lastT 和節點當前時間curT 。節點根據收到目標節點的 beacon分組可據式(2)和式(3)計算出其下一次喚醒時間NextTimeWakeup。

其中，locT 為本地節點時間，diffT 為本地節點與目標節點的時差。

圖 2是發送節點 S通過目標接收節點 R的beacon分組來預測R下一次喚醒時間的偽代碼。其算法的核心思想是：如果R的相關參數未知，則立即偵聽信道；否則根據R的隨機種子、當前時間和最近一次喚醒時間信息計算R的下一次喚醒時間。

圖2 節點S預測節點R喚醒時間的偽代碼

其中，Seed[R]為目標接收節點 R的隨機種子，currentTime[R]為 R的當前時間，Tcur[R]為 R發送beacon分組的時間，Tlast[R]為R的最近一次喚醒時間，nextWakeupTime[R]是預測下一次R的喚醒時間(初始值為R的最近一次喚醒時間)。

圖3 發送節點與接收節點數據傳輸

如圖3所示，發送節點S首次向目標接收節點R建立連接需要一直醒來偵聽R的beacon分組，S在收到R的beacon分組后向R發起建立連接傳輸數據。當S下一次需要向R發送數據時，根據式(3)和式(4)來精確推導目標節點喚醒時間，在此時間喚醒偵聽R的beacon分組，并在收到R的beacon分組后向R發起建立連接。

綜上所述，PB-MAC報頭beacon分組僅需攜帶2 byte Seed、4 bytelastT 和4 bytecurT 共10 byte的預測信息，即可完成對鄰居節點喚醒時間的預測，具有報頭短和低開銷的特征。

2.4 預測重建連接機制

針對2個隱藏終端節點可能同時向目標節點發起建立連接請求而導致建立連接失敗的情況，PB-MAC采用隨機延退和釋放預測的方法規避沖突和提高重連接效率。

隨機延退是指多個發送節點收到同一目標接收節點R的廣播beacon分組后，在[0,cT]內各自隨機延退一段時間dT，再向R發起建立連接，實現規避沖突，提高連接成功率，dT需滿足

其中，Tdelay為端到端傳輸時延，即 R TT / 2。結合式(1)和式(5)可得：Td≤RTT/2，因此取Tc=RTT/2。

以圖4為例，在發送節點S1和S2同時收到R的beacon分組后不是立即向R發起建立連接，而是在延退[0, /2RTT ]區間的隨機時間后再向R發起建立連接。由于 S2延退時間小于 S1延退時間，所以S2成功與R建立連接。

針對建立連接失敗的節點，PB-MAC采用釋放預測機制來重建連接。具體預測規則分以下情況進行計算。

圖4 預測重建連接機制

1) 若收到目標節點發送給其他節點的CTS幀，則目標節點傳完數據后釋放連接的預計時間nextT 為

其中，hT為處理單位數據的時間，dIR為目標節點還需接收數據分組的個數，ctsT 為收到目標節點CTS幀的時間。

2) 若收到目標節點發送給其他節點的Data數據分組，則目標節點傳完數據后釋放連接的預計時間nextT 為

其中， I Sd為目標節點還需發送數據分組的個數，Tdata為收到目標節點Data數據分組的時間。

3) 其他情況，立即進入休眠。如圖4所示發送節點S1在建立連接失敗后，收到目標節點R發送給節點S2的CTS幀。S1根據收到R的CTS幀，依式(6)推導R接收完數據釋放的連接時間，并在此時間向R發起建立連接。

2.5 預測數據重傳機制

基于無線網絡的不穩定性和網絡去擁塞的時滯性，在出現分組丟失時，PB-MAC要求發送節點和接收節點盡快進入休眠模式，達到降低占空比的目的。

在分組丟失后，發送節點和接收節點的具體表現為：發送節點首先啟動2.3節所述的預測目標喚醒算法計算接收節點下一次的喚醒時間，然后轉入休眠狀態；接收節點在沒有收到后續有效數據或者數據已經傳送完畢時進入休眠狀態。

由于發送節點和接收節點均進入休眠狀態，等待目標節點下一次醒來再重傳該數據。如圖3所示，當S發送第二個數據分組出現分組丟失后馬上進入休眠，在R第3次醒來后再重傳該數據。

3 仿真與分析

3.1 仿真參數與環境說明

實驗采用OMNet++軟件對比分析了PB-MAC、RI-MAC和X-MAC的性能，采用MATLAB輔助分析實驗數據。為了保障3個協議的可比性，分別對每個協議進行如表1所示設置。

表1 協議參數設置

在PB-MAC中，為保障節點間隨機種子盡可能不相近，隨機種子產生式的參數a、c、m分別設置為20、7和999。

實驗模擬運行500 s，節點每隔[500，1 500] ms產生一個數據分組，數據傳輸時延設定為5 ms。為了檢測節點的消息負載量，假設節點的消息緩沖區是無限大。仿真中測量以下指標。

1) 平均占空比：節點處于偵聽狀態占整個實驗時間的比率。

2) 數據傳遞率：基站接收到的數據總量占所有節點產生的數據總量的比率。

3) 端到端的數據延遲：從節點產生數據或收到數據開始到該數據成功被下一跳節點接收的平均時間。

4) 消息負載量：節點在整個實驗時間中消息隊列的最大數據量。

5) 發送耗能：發送消息消耗的能量，以發送單位數據消耗1個單位的能量來計量。

6) 碰撞次數：節點在激活狀態同時收到2個及以上發送節點數據的次數。

3.2 隨機網絡評估

在900 m×900 m的方形區域內隨機部署49個節點，在中心部署1個基站，節點通信半徑為200 m。表2為PB-MAC、RI-MAC和X-MAC在消息傳遞率、占空比、端到端延遲、最大消息負載量、發送數據耗能和平均碰撞次數指標的對比。

表2 隨機網絡性能對比

表2表明，PB-MAC在保持高傳遞率和低延遲的情況下，占空比、平均發送數據耗能和碰撞次數3個性能分別比RI-MAC降低了68.60%、24.75%、68.05%，比 X-MAC降低了 64.39%、64.05%、70.54%。這是因為PB-MAC通過精確估計目標節點的喚醒時間，避免像RI-MAC和X-MAC那樣每次醒來偵聽信道，等待與目標節點建立連接。在隨機網絡中由于節點分布不均，容易導致數據分組丟失，而PB-MAC協議在數據分組丟失后采用2.5節所示的快速進入休眠狀態的重傳機制，故在延遲性能上比RI-MAC和X-MAC略高。

當發送節點有數據需要發送時，RI-MAC采用被動等待方式，X-MAC采用不斷向目標節點發送請求分組的主動建立連接方式，所以RI-MAC的發送耗能遠小于X-MAC。PB-MAC中的預測機制使得發送節點與接收節點建立起連接的無效請求較少，發送數據耗能也較小。

表2顯示在消息傳遞率相近的情況下，發送數據耗能與碰撞次數成正相關。由于RI-MAC碰撞窗口每次從0開始增加，而X-MAC的碰撞窗口固定為32，故RI-MAC的碰撞次數偏高。PB-MAC采用預測重建連接機制能提高連接的成功率和減少擁塞時的無效傳輸，故碰撞次數最少。

3.3 網格網絡評估

在網格網絡中，基站處于網絡的中央位置，每個節點與其鄰居節點的距離為100 m，節點通信半徑為100 m。網格規模從4×4（16節點）逐步擴大到 9×9（81 節點）。

圖5是PB-MAC、RI-MAC和X-MAC在網格網絡環境中的各項性能對比圖。圖5(a)是PB-MAC、RI-MAC和X-MAC協議在網格網絡環境中的占空比性能對比圖。由于RI-MAC和X-MAC協議中發送節點平均需醒來等待半個RTT的空閑偵聽時間，才能與目標接收節點建立起連接，而使用預測機制的PB-MAC等待的偵聽時間接近0。因此，PB-MAC中發送節點具有占空比較低的顯著優勢。RI-MAC中發送節點避免了X-MAC中大量的preamble分組占用信道，信道利用率較高。因此，RI-MAC較X-MAC略占優勢。

圖5（b）是PB-MAC、RI-MAC和X-MAC協議在網格網絡環境中的平均發送消息能耗對比圖。由于 PB-MAC采用預測機制使得發送節點與目標節點成功建立連接的幾率較高，僅需要少量的RTS請求分組，失效請求少。因此，平均發送消息耗能單位在 3個協議中最少。X-MAC中大量無效的preamble請求分組使耗能較RI-MAC高。

圖5（c）是PB-MAC、RI-MAC和X-MAC協議在網格網絡環境中的平均和最大碰撞次數對比圖。3 種協議在奇網格（5×5、7×7、9×9）和偶網格（4×4、6×6、8×8）下的平均碰撞次數分別呈現遞增狀態。另外，由于基站一直處于偵聽狀態，偶網格中的碰撞次數要明顯多于奇網格。

圖5(d)是PB-MAC、RI-MAC和X-MAC協議在網格網絡環境中的端到端延遲對比圖。3種協議的端到端延遲隨網格規模的變化基本保持一致。RI-MAC與X-MAC以付出高占空比的代價減少延遲，而PB-MAC以高效的預測重建連接機制，保障低延遲。

圖5 網格網絡性能參數對比

圖 5（e）是 PB-MAC、RI-MAC和 X-MAC協議在網格網絡環境中的分組傳遞率對比圖。從圖中可以看出，當網絡邊緣節點大于7時，所有協議分組傳遞率急劇下降，這與圖 5（d）中網絡邊緣節點大于 7后延遲劇增相對應。實驗發現，當規模超過 7×7（49節點）后，網絡開始出現擁塞。

圖5（f）是PB-MAC、RI-MAC和X-MAC協議在網格網絡環境中的平均和最大消息負載量對比圖。在網絡邊緣節點數小于7時，3種協議的平均消息負載量基本維持在 20左右。當網絡邊緣節點數大于7后，平均消息負載量急劇上升，也印證了網絡出現擁塞。

總體來看，PB-MAC在占空比、發送消息耗能、碰撞次數3個性能上表現出明顯優勢。另外，在網絡出現擁塞之前，隨著節點規模的增大，PB-MAC在占空比、發送消息耗能、最大碰撞次數和平均碰撞次數指標上基本呈線性增長，穩定性好。在網絡出現嚴重擁塞之后，在占空比、碰撞次數指標上，PB-MAC仍優于RI-MAC和X-MAC。

4 結束語

本文著重研究如何優化異步MAC協議來減少網絡耗能和提高通信質量，提出了一種低占空比、低碰撞的異步無線傳感器網絡 MAC協議——PB-MAC協議。該協議以共享隨機種子為基礎，通過預測方式估計鄰居節點的喚醒時間表，達到降低占空比的目的；通過預測重連接機制和預測數據重傳機制，避免數據碰撞和實現高效重傳。仿真結果表明：在隨機網絡和網格網絡中，PB-MAC協議在保持低延遲和高傳遞率的情況下，其占空比、碰撞次數和能耗方面明顯優于RI-MAC和X-MAC。

[1] 馬祖長, 孫怡寧, 梅濤. 無線傳感器網絡綜述[J]. 通信學報, 2004,25(4)：114-123.MA Z C, SUN Y N, MEI T. Survey on wireless sensors network[J].Journal on Communications, 2004, 25(4)：114-123.

[2] 李瑞芳, 李仁發, 羅娟. 無線多媒體傳感器網絡 MAC協議研究綜述[J].通信學報, 2008, 29(8)：111-123.LI R F, LI R F, LUO J. Survey of MAC protocol in wireless multimedia sensor networks[J]. Journal on Communications, 2008, 29(8)：111-123.

[3] WEI Y, HEIDEMANN J, ESTRIN D. An energy-efficient MAC protocol for wireless sensor networks[A]. Proceedings of the IEEE INFOCOM'02[C]. New York, NY, USA, 2002.1567-1576.

[4] DAM T V, LANGENDOEN K. An adaptive energy-efficient MAC protocol for wireless sensor networks[A]. Proceedings of the First International Conference on Embedded Networked Sensor Systems(SenSys'03)[C]. Los Angeles, CA, USA, 2003.171-180.

[5] WEI Y, SILVA F, HEIDEMANN J. Ultra-low duty cycle MAC with scheduled channel polling[A]. Proceedings of the 4th ACM SenSys Conference(SenSys'06)[C]. Boulder, CO, USA, 2006.321-334.

[6] SUN Y, DU S, GUREWITZ O. DW-MAC： a low latency, energy efficient demand-wakeup mac protocol for wireless sensor networks[A].Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc'08)[C]. Hong Kong, China,2008.53-62.

[7] 胡玉鵬, 林亞平, 周四望. 面向異步通信機制的無線傳感器網絡及其MAC協議研究[J].計算機學報, 2011, 34(8)：1163-1477.HU Y P, LIN Y P, ZHOU S W. Asynchronous communication mechanism oriented wireless sensor networks and MAC protocols[J]. Journal on Computers, 2011, 34(8)：1163-1477.

[8] 李哲濤，李仁發，魏葉華. 無線傳感器網絡中時間同步與測距協同算法[J]. 計算機研究與發展, 2010,47(4)：638-644.LI Z T, LI R F, WEI Y H. Coordinated algorithm for time synchronization and distance measurement in wireless sensor networks[J]. Journal of Computer Research and Development, 2010,47(4)：638-644.

[9] POLASTRE J, HILL J, CULLER D. Versatile low power media access for wireless sensor networks[A]. Proceedings of the Second ACM SenSys Conference (SenSys’04)[C]. Baltimore, MD, USA, 2004. 95-107.

[10] BUETTNER M, YEE G V, ANDERSON E. X-MAC： a short preamble MAC protocol for duty-cycled wireless sensor networks[A]. Proceedings of the 4th ACM SenSys Conference (SenSys'06)[C]. Boulder, CO,USA, 2006.307-320.

[11] CAO H, PARKER K W, ARORA A. O-MAC： a receiver centric power management protocol[A]. Proceedings of the 14th IEEE International Conference on Network Protocols(ICNP'06)[C]. Santa Barbara, CA,USA, 2006.311-320.

[12] WEI Y, SILVA F, HEIDEMANN J. Ultra-low duty cycle MAC with scheduled channel polling[A]. Proceedings of the 4th ACM SenSys Conference(SenSys'06)[C]. Boulder, CO, USA, 2006.321-334.

[13] SUN Y, GUREWITZ O, JOHNSON D B. RI-MAC： a receiver initiated asynchronous duty cycle MAC protocol for dynamic traffic loads in wireless sensor networks[A]. Proceedings of the 6th ACM SenSys Conference (SenSys'08)[C]. Raleigh, NC, USA, 2008.1-14.

[14] Wireless LAN medium access control (MAC) and physical layer (PHY)specifications[EB/OL]. www.ieee.org, 1997.

[15] KNUTH D E. 計算機程序設計藝術, 第2卷： 半數值算法[M]. 北京： 人民郵電出版社, 2010.KNUTH D E. The Art of Computer Programming, Volume 2： Seminumerical Algorithms[M]. Beijing： Posts & Telecom Press, 2010.