層次傳感器網(wǎng)絡(luò)的交錯(cuò)同步休眠調(diào)度方法研究*

單 洪，馬 濤

(解放軍電子工程學(xué)院網(wǎng)絡(luò)工程系，合肥230037)

在無(wú)線傳感器網(wǎng)絡(luò)中，睡眠機(jī)制是節(jié)點(diǎn)最常用的節(jié)能方法。但在使用睡眠機(jī)制的同時(shí)，會(huì)增加數(shù)據(jù)包的發(fā)送延遲，因?yàn)楫?dāng)節(jié)點(diǎn)有數(shù)據(jù)要發(fā)送時(shí)，節(jié)點(diǎn)必須等待下一跳節(jié)點(diǎn)喚醒，才能發(fā)送數(shù)據(jù)，這樣就產(chǎn)生了額外的延遲［1］。目前，睡眠機(jī)制分為兩類［2］:異步睡眠機(jī)制和同步睡眠機(jī)制。異步睡眠機(jī)制是每個(gè)節(jié)點(diǎn)的喚醒時(shí)間獨(dú)立于其他節(jié)點(diǎn)，會(huì)造成很大的延遲，如RI-MAC［3］和 PA-MAC［4］。同步睡眠機(jī)制要求節(jié)點(diǎn)的睡眠和活動(dòng)狀態(tài)是時(shí)間同步的，然而時(shí)間同步的開銷較大，當(dāng)節(jié)點(diǎn)在同一個(gè)時(shí)間槽喚醒，容易造成沖突，如S-MAC［5］、RLL-MAC［6］、EP-MAC［7］、DW-MAC［8］、WiseMAC［9］、XMAC［10］協(xié)議?？梢钥闯?，現(xiàn)有的睡眠調(diào)度機(jī)制主要是針對(duì)無(wú)線傳感器網(wǎng)絡(luò)的具體應(yīng)用進(jìn)行時(shí)延或能耗的改進(jìn)，并不具有普適性。

本文結(jié)合所設(shè)計(jì)無(wú)線傳感器具有層次性、節(jié)點(diǎn)密度大、傳輸數(shù)據(jù)流差異大等特點(diǎn)，為了達(dá)到能量消耗和時(shí)延均衡提出了一種交錯(cuò)的周期倍增同步休眠調(diào)度方案。通過與現(xiàn)有的同步方案和交錯(cuò)同步方案仿真比較，該方案使節(jié)點(diǎn)盡量多的處在休眠狀態(tài)以降低能耗，同時(shí)能以解決同步休眠調(diào)度帶來的時(shí)延增大問題。

1 網(wǎng)絡(luò)模型

無(wú)線傳感器網(wǎng)絡(luò)由匯聚節(jié)點(diǎn)(Sink)、高級(jí)節(jié)點(diǎn)(H-Sensor)和普通節(jié)點(diǎn)(L-Sensor)組成。節(jié)點(diǎn)依據(jù)不同的感知任務(wù)和地理位置劃分為多個(gè)簇，每個(gè)簇形成一個(gè)子組。H-Sensor因?yàn)榫哂休^高的存儲(chǔ)、計(jì)算和傳輸能力、能量大或者可以補(bǔ)充，所以選定其作為簇首，L-Sensor將監(jiān)測(cè)數(shù)據(jù)通過H-Sensor傳輸?shù)絊ink。網(wǎng)絡(luò)有兩層:所有H-Sensor構(gòu)成一個(gè)組(HSensor Group，HG)，為骨干層;每個(gè)簇構(gòu)成一個(gè)子組(L-Sensor Group，LG)，為基礎(chǔ)層。本文的研究重點(diǎn)是基礎(chǔ)層中的MAC協(xié)議休眠調(diào)度方案。

該層次網(wǎng)絡(luò)在應(yīng)用中還存在自身的一些特點(diǎn):①?zèng)]有基礎(chǔ)設(shè)施，部署之后自動(dòng)運(yùn)行，組織成網(wǎng)絡(luò);②節(jié)點(diǎn)數(shù)量多、密度大、分布隨機(jī)，拓?fù)洳荒苁孪却_定;同時(shí)節(jié)點(diǎn)不具有移動(dòng)性，故網(wǎng)絡(luò)部署后覆蓋范圍在一段時(shí)間內(nèi)不會(huì)發(fā)生變化;③兩層網(wǎng)絡(luò)的數(shù)據(jù)流有不同的特點(diǎn):基礎(chǔ)層網(wǎng)絡(luò)節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)分組較小，以周期性數(shù)據(jù)為主，具有時(shí)間相關(guān)性;同時(shí)通信信號(hào)活躍區(qū)域可產(chǎn)生大量數(shù)據(jù)，具有空間相關(guān)性。另外，基礎(chǔ)層數(shù)據(jù)有明顯的方向性，向簇首及骨干節(jié)點(diǎn)匯集，并以流向這兩類節(jié)點(diǎn)的數(shù)據(jù)為主。骨干層網(wǎng)絡(luò)產(chǎn)生的數(shù)據(jù)分組較大，通訊信號(hào)活躍區(qū)域網(wǎng)絡(luò)負(fù)載較重，同時(shí)數(shù)據(jù)流不存在向某些節(jié)點(diǎn)匯聚的現(xiàn)象。

圖1給出了簇結(jié)構(gòu)的分層示意圖。

圖1 簇結(jié)構(gòu)的分層示意

在簇狀結(jié)構(gòu)中，根據(jù)到簇首節(jié)點(diǎn)的最小跳數(shù)對(duì)簇內(nèi)節(jié)點(diǎn)進(jìn)行分層，簇首節(jié)點(diǎn)為第0層，距簇首節(jié)點(diǎn)k跳的簇成員節(jié)點(diǎn)為第k層，一個(gè)簇最多有h層。從簇成員節(jié)點(diǎn)發(fā)往簇首節(jié)點(diǎn)的數(shù)據(jù)稱為上行數(shù)據(jù)，上行數(shù)據(jù)經(jīng)歷的平均休眠等待時(shí)延用ti(i代表第i層)表示。從簇首節(jié)點(diǎn)發(fā)往簇成員節(jié)點(diǎn)的數(shù)據(jù)稱為下行數(shù)據(jù)，下行數(shù)據(jù)經(jīng)歷的平均休眠等待時(shí)延用si表示。假設(shè)數(shù)據(jù)產(chǎn)生的過程服從泊松過程。

2 問題描述

基礎(chǔ)層使用分簇結(jié)構(gòu)來降低網(wǎng)絡(luò)中數(shù)據(jù)流的密度，減少跳數(shù)過多的數(shù)據(jù)轉(zhuǎn)發(fā)，用輪換簇首的方法平衡能量消耗?；A(chǔ)層的數(shù)據(jù)具有明顯的方向性，但存在兩個(gè)方向的數(shù)據(jù)流向。

有固定周期的同步休眠調(diào)度在節(jié)約節(jié)點(diǎn)能量的同時(shí)會(huì)帶來一定的休眠等待時(shí)延，而基礎(chǔ)層的數(shù)據(jù)是時(shí)延敏感的，如果經(jīng)過很長(zhǎng)時(shí)間才到達(dá)骨干節(jié)點(diǎn)，可能數(shù)據(jù)已經(jīng)失去了意義。基礎(chǔ)層的MAC協(xié)議在節(jié)約能量的同時(shí)要保證較小的時(shí)延，并且對(duì)從簇成員節(jié)點(diǎn)到簇首節(jié)點(diǎn)的數(shù)據(jù)，以及簇首節(jié)點(diǎn)到骨干節(jié)點(diǎn)的數(shù)據(jù)都要保證較小的時(shí)延。此時(shí)，優(yōu)化一個(gè)方向的數(shù)據(jù)的時(shí)延而犧牲另一個(gè)方向的數(shù)據(jù)時(shí)延是不可取的，需要努力同時(shí)降低簇狀拓?fù)渲猩闲泻拖滦袃蓚€(gè)方向的數(shù)據(jù)時(shí)延。

在簇狀結(jié)構(gòu)中，數(shù)據(jù)從簇成員節(jié)點(diǎn)向簇首節(jié)點(diǎn)匯聚的特點(diǎn)導(dǎo)致處于中間層的節(jié)點(diǎn)不僅需要發(fā)送自己的數(shù)據(jù)，還要承擔(dān)大量的轉(zhuǎn)發(fā)任務(wù)，而大部分休眠調(diào)度中節(jié)點(diǎn)的激活/休眠周期都是相同的，容易造成大量的數(shù)據(jù)在轉(zhuǎn)發(fā)節(jié)點(diǎn)處累積，加劇了轉(zhuǎn)發(fā)過程中競(jìng)爭(zhēng)的激烈程度，也使數(shù)據(jù)時(shí)延較長(zhǎng)。因此，不同層節(jié)點(diǎn)的激活/休眠周期應(yīng)該適應(yīng)它們不同的接收、發(fā)送任務(wù)，簇首以及靠近簇首的成員節(jié)點(diǎn)由于接收、發(fā)送的任務(wù)較重，可以增加它們的激活/休眠的頻率，使其他節(jié)點(diǎn)有更多的接入機(jī)會(huì)，降低多跳數(shù)據(jù)轉(zhuǎn)發(fā)經(jīng)歷的休眠等待時(shí)延，同時(shí)這樣也可以減輕每次競(jìng)爭(zhēng)信道時(shí)的激烈程度。雖然這樣會(huì)增加一部分節(jié)點(diǎn)的能耗，但由于簇是周期輪轉(zhuǎn)的，節(jié)點(diǎn)在不同的時(shí)期會(huì)處在不同簇內(nèi)的不同層，能夠使得節(jié)點(diǎn)間的能耗平衡。出于以上的考慮，提出了一種交錯(cuò)的周期倍增同步休眠調(diào)度方案，該方案主要應(yīng)用在基礎(chǔ)層MAC協(xié)議。

3 交錯(cuò)的周期倍增同步休眠調(diào)度

3.1 休眠調(diào)度方案

圖2 交錯(cuò)的周期倍增同步休眠調(diào)度

3.2 平均休眠等待時(shí)延

交錯(cuò)的周期倍增同步休眠調(diào)度中的上下行數(shù)據(jù)經(jīng)歷的平均休眠等待時(shí)延是不同的，對(duì)上行數(shù)據(jù)的平均休眠等待時(shí)延有式(1)，下行數(shù)據(jù)的平均休眠等待時(shí)延有式(2)。

推導(dǎo)過程如下。

(1)上行數(shù)據(jù)

圖3 交錯(cuò)的周期倍增休眠調(diào)度上行數(shù)據(jù)時(shí)延分析

(2)下行數(shù)據(jù)

圖4 交錯(cuò)的周期倍增休眠調(diào)度下行數(shù)據(jù)時(shí)延分析

4 仿真實(shí)驗(yàn)與分析

將交錯(cuò)的周期倍增同步休眠調(diào)度機(jī)制應(yīng)用到無(wú)線傳感器網(wǎng)絡(luò)的基礎(chǔ)層MAC層協(xié)議(GFN-MAC)中，具體仿真分析如下。

4.1 參數(shù)配置

利用QualNet5對(duì)GFN-MAC進(jìn)行建模及仿真。在仿真實(shí)驗(yàn)中，節(jié)點(diǎn)的能耗計(jì)算使用TR1000技術(shù)手冊(cè)的參數(shù)值，見表1。其中Itx、Irx、Isleep分別代表節(jié)點(diǎn)通信模塊處在發(fā)送、接收和休眠三個(gè)狀態(tài)時(shí)的工作電流，U代表通信模塊的工作電壓，并且通信模塊空閑狀態(tài)時(shí)的電流等于接收狀態(tài)時(shí)的電流，即Iidle=Irx。

基礎(chǔ)層節(jié)點(diǎn)分布密集，平均鄰居節(jié)點(diǎn)數(shù)目大約為10，因此固定的競(jìng)爭(zhēng)窗口設(shè)置為32。通信距離較短，帶寬較窄，分別設(shè)為40 m和40 kbit/s，其它實(shí)驗(yàn)參數(shù)設(shè)置見表1。

表1 GFN-MAC仿真實(shí)驗(yàn)主要參數(shù)設(shè)置

4.2 仿真實(shí)驗(yàn)

(1)實(shí)驗(yàn)1

在一個(gè)到簇首節(jié)點(diǎn)最大5跳的拓?fù)渲?圖5)，相鄰節(jié)點(diǎn)相距40 m。節(jié)點(diǎn)6為簇首節(jié)點(diǎn)，節(jié)點(diǎn)1～5分別在簇中的第1～5層。完全同步和交錯(cuò)同步的節(jié)點(diǎn)激活/休眠周期為1 s，GFM-MAC簇首節(jié)點(diǎn)的激活/休眠周期為62.5 ms，那么第5層節(jié)點(diǎn)的激活/休眠周期為2 s。

圖5 GFN-MAC實(shí)驗(yàn)一拓?fù)?/p>

對(duì)上行數(shù)據(jù)，依次仿真每層簇成員節(jié)點(diǎn)向簇首節(jié)點(diǎn)發(fā)送1 000個(gè)大小為40字節(jié)數(shù)據(jù)分組，對(duì)下行數(shù)據(jù)，依次仿真簇首節(jié)點(diǎn)向每層節(jié)點(diǎn)發(fā)送100個(gè)大小為1 000字節(jié)分組。

在仿真試驗(yàn)中，簇成員節(jié)點(diǎn)從第10 s開始發(fā)送數(shù)據(jù)，數(shù)據(jù)發(fā)送間隔為5.01 s，發(fā)送多個(gè)分組時(shí)可以使數(shù)據(jù)的發(fā)送的時(shí)間較均勻的分布在節(jié)點(diǎn)的激活/休眠周期中。仿真時(shí)間為5 020 s。簇首節(jié)點(diǎn)從第10 s開始發(fā)送數(shù)據(jù)，數(shù)據(jù)發(fā)送間隔5.01 s，仿真時(shí)間512 s。

對(duì)使用完全同步［11］、交錯(cuò)同步［12］和交錯(cuò)的周期倍增同步三種休眠調(diào)度方案時(shí)數(shù)據(jù)傳輸經(jīng)歷的平均休眠等待時(shí)延進(jìn)行比較，仿真結(jié)果如圖6所示。由于沒有沖突重傳和排隊(duì)等待，影響時(shí)延的主要因素是等待目的節(jié)點(diǎn)激活的休眠等待時(shí)延。從圖中可以看出，由于下行的數(shù)據(jù)分組較大，傳輸時(shí)間較大，因此完全同步和交錯(cuò)同步兩種休眠調(diào)度的下行數(shù)據(jù)時(shí)延沒有和上行數(shù)據(jù)時(shí)延重合，而是略大于上行數(shù)據(jù)的時(shí)延。在GFN-MAC中，最外層簇成員節(jié)點(diǎn)上行數(shù)據(jù)的時(shí)延能保持在1 s左右，從簇首節(jié)點(diǎn)發(fā)到第外層成員節(jié)點(diǎn)的數(shù)據(jù)經(jīng)歷的時(shí)延大約1.7 s，而交錯(cuò)同步此時(shí)的時(shí)延已達(dá)2.5 s以上，完全同步的調(diào)度更是達(dá)到了4.5 s。

圖6 不同休眠調(diào)度時(shí)延仿真驗(yàn)證

(2)實(shí)驗(yàn)2

實(shí)驗(yàn)二是比較負(fù)載不同時(shí)GFN-MAC與完全同步的、交錯(cuò)同步的休眠調(diào)度協(xié)議的時(shí)延、吞吐量和每字節(jié)能耗三個(gè)方面的性能。實(shí)驗(yàn)拓?fù)錇樯刃螀^(qū)域，如圖7所示。圓心為簇首節(jié)點(diǎn)，簇最外層節(jié)點(diǎn)距簇首5跳。

圖7 GFN-MAC仿真拓?fù)浣Y(jié)構(gòu)

所有簇成員節(jié)點(diǎn)從第10 s開始同時(shí)向簇首節(jié)點(diǎn)發(fā)送大小40字節(jié)的恒定比特速率數(shù)據(jù)，仿真時(shí)間1 000 s。為保證數(shù)據(jù)到達(dá)時(shí)間在休眠周期中均勻分布，發(fā)送間隔分別為1.01 s和5.01 s。完全同步和交錯(cuò)同步的節(jié)點(diǎn)激活/休眠周期為1 s，GFN-MAC簇首節(jié)點(diǎn)的周期為62.5 ms和125 ms，此時(shí)簇的最外層成員節(jié)點(diǎn)的激活/休眠周期為2 s和4 s。實(shí)驗(yàn)結(jié)果如圖8所示。

圖8 不同負(fù)載下各休眠調(diào)度協(xié)議的性能比較

從圖8可以看出，兩種不同休眠調(diào)度的GFNMAC在不同的數(shù)據(jù)發(fā)送間隔下，比完全同步和交錯(cuò)同步的休眠調(diào)度方案，具有更高的吞吐量，更低的時(shí)延和能耗。這是由于GFN-MAC中使用的的休眠調(diào)度通過使靠近簇首的節(jié)點(diǎn)的更頻繁的激活給其他節(jié)點(diǎn)更多的接入機(jī)會(huì)，讓數(shù)據(jù)能夠更快的轉(zhuǎn)發(fā)。由于減輕了數(shù)據(jù)在轉(zhuǎn)發(fā)節(jié)點(diǎn)的堆積，降低了沖突碰撞的概率，減少了因沖突重發(fā)帶來的能耗，因此GFNMAC的平均每個(gè)成功收發(fā)字節(jié)消耗的能量也小于其他兩種休眠調(diào)度的。

5 結(jié)束語(yǔ)

本文根據(jù)基礎(chǔ)層數(shù)據(jù)以周期性短數(shù)據(jù)為主的特點(diǎn)選擇使用同步的休眠調(diào)度，使節(jié)點(diǎn)盡量多的處在休眠狀態(tài)以降低能耗。又提出了一種交錯(cuò)的周期倍增的同步休眠調(diào)度，以解決同步休眠調(diào)度帶來的時(shí)延增大的問題。最后通過仿真實(shí)驗(yàn)，驗(yàn)證了GFNMAC可以保證簇中上下行兩個(gè)方向的數(shù)據(jù)都有較低的時(shí)延，適合基礎(chǔ)層的數(shù)據(jù)特點(diǎn)，并且由于降低了沖突碰撞和快速轉(zhuǎn)發(fā)數(shù)據(jù)，協(xié)議在節(jié)能和降低時(shí)延的同時(shí)擁有較大的吞吐量，能夠較好的滿足群系統(tǒng)基礎(chǔ)層的要求。

［1］ 蹇強(qiáng)，龔正虎，朱培棟，等.無(wú)線傳感器網(wǎng)絡(luò)MAC協(xié)議研究進(jìn)展［J］.軟件學(xué)報(bào)，2008，19(2):389－403.

［2］ 楊建，李金寶，郭龍江，等.Dual-Radio無(wú)線傳感器網(wǎng)絡(luò)睡眠調(diào)度機(jī)制［J］.軟件學(xué)報(bào)，2011，22(1):62－72.

［3］ 唐震洲，施曉秋，金可仲.PA-MAC:一種被動(dòng)的異步低占空比無(wú)線傳感器網(wǎng)絡(luò)MAC協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，2011，24(3):423－428.

［4］ Sun Y J，Gurewitz O，Johnson D B.RI-MAC:A Receiver Initiated Asynchronous Duty Cycle MAC Protocol for Dynamic Traffic Loads in Wireless Sensor Networks［C］//Abdelzaher T，ed.Proc.of the 6th ACM Conf.on Embedded Network Sensor Systems.New York:ACM Press，2008.1－14.

［5］ Kim J，Lin X J，Shroff N B，et al.Minimizing Delay and Maximizing Lifetime for Wireless Sensor Networks with any Cast［J］.IEEE/ACM Trans.on Networking，2009，18(2):515－528.

［6］ 唐震洲，胡倩.基于數(shù)據(jù)重排序的無(wú)線傳感器網(wǎng)絡(luò)低延時(shí)節(jié)能MAC 協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，2010，23(7):1037－1043.

［7］ 崔海霞，黎文樓，丁志文.無(wú)線傳感器網(wǎng)絡(luò)中基于能量效率的分布式 MAC 協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，2010，23(1):104－109.

［8］ Sun Y J，Du S，Gurewitz O，et a;.DW-MAC:A Low Latency，Energy Efficient Demand-Wakeup Mac Protocol for Wireless Sensor Networks［C］//Jia XH，ed.Proc.of the 9th ACM Int’l Symp.on Mobile Ad Hoc Networking and Computing.New York:ACM Press，2008.53－62.

［9］ El-Hoiydi A，Decotignie J D.WiseMAC:An Ultra Low Power MAC Protocol for Multi-Hop Wireless Sensor Networks［C］//Nikoletseas S，ed.Proc.of the 1st Int’l workshop on Algorithmic Aspects of Wireless Sensor Network.Turku:Springer-Verlag，2004.

［10］ Lai S W，Ravindran B.On Distributed Time-Dependent Shortest Paths over Duty-Cycled Wireless Sensor Networks［C］//Mandyam G，ed.Proc.of the 29th Annual Joint Conf.of the IEEE Computer and Communications Societies.Washington:IEEE Press，2010.1－9.

［11］ Wan C Y，Eisenman S E，Campbell A T，et al.Siphon:Overload Traffic Management Using Multi-Radio Virtual Sinks［C］//Proc.of 3rdACM Conf.on Embedded Networked SensorSystems(SenSys).San Diego:ACM Press，116－119，2005.

［12］ Gang Lu，Narayanan Sadagopan，Bhaskar Krishnamachari.Ashish Goel:Delay Efficient Sleep Scheduling in Wireless Sensor Networks［J］.IEEE Infocom，2005.