曾 波,李姍姍,王 輝1,

(1.河南科技大學網(wǎng)絡與通信技術研究所,河南 洛陽 471023;2.河南科技大學網(wǎng)絡信息中心,河南 洛陽 471023)

?

一種基于有限信道的能量高效節(jié)點調度機制*

曾 波1,2*,李姍姍2,王 輝1,2

(1.河南科技大學網(wǎng)絡與通信技術研究所,河南 洛陽 471023;2.河南科技大學網(wǎng)絡信息中心,河南 洛陽 471023)

在低負載、低功耗無線傳感器網(wǎng)絡中,節(jié)點狀態(tài)切換的能量消耗因為用于數(shù)據(jù)傳輸?shù)哪芰枯^小而變得不可忽略。針對此問題,提出了結合多信道技術與時分多路訪問(TDMA)技術的節(jié)點調度算法。該算法設計了基于接收端的連續(xù)時隙分配策略以減少節(jié)點狀態(tài)切換次數(shù),并且在可用無線信道有限的約束條件下,提出了信道分配與時隙調整機制,實現(xiàn)了時隙重用并最小化有限信道約束對優(yōu)化節(jié)點狀態(tài)切換次數(shù)的影響。仿真實驗結果表明,當可用無線信道數(shù)為3～5時,算法能夠有效地改善節(jié)點能量效率。當可用無線信道數(shù)大于3之后,算法能夠獲得優(yōu)化的數(shù)據(jù)匯聚時間。

無線傳感器網(wǎng)絡;能量;TDMA;多信道;調度;仿真

近年來,無線傳感器網(wǎng)絡因其成本低廉、部署靈活、覆蓋范圍廣等特性,廣泛應用于環(huán)境保護、智能交通、文物保護等領域[1]。對大多數(shù)部署在無人監(jiān)管的惡劣環(huán)境下的無線傳感器網(wǎng)絡,因其僅依靠電池供電[2]而使得傳感器節(jié)點不得不采用周期性工作方式來實現(xiàn)數(shù)據(jù)采集與匯聚傳輸,以降低傳感器節(jié)點能量消耗。采用超低功耗傳感器節(jié)點射頻技術[3-4]在進行數(shù)據(jù)發(fā)送之前需要喚醒節(jié)點,雖然降低了能量消耗,卻增加了傳輸延遲。而采用功率控制的能量優(yōu)化[5]需要額外的控制消息。

TDMA調度算法[6]通過對每個節(jié)點訪問信道的時隙進行合理安排,能夠有效避免節(jié)點對無線信道的訪問競爭,讓節(jié)點能夠在指定的時隙無干擾的完成數(shù)據(jù)發(fā)送,并且在數(shù)據(jù)發(fā)送完成之后,節(jié)點立即切換至休眠狀態(tài),極大的節(jié)省了節(jié)點能量。

目前,針對傳感器網(wǎng)絡能量優(yōu)化的TDMA調度算法主要包括降低空閑時隙內傳感器節(jié)點活動[7-9]、延長節(jié)點工作間隔和降低工作循環(huán)時間[10-11]。在前述方法中,主要考慮降低數(shù)據(jù)匯聚過程中節(jié)點在空閑狀態(tài)的能量消耗?；卩従有畔⒐蚕?Luo等人[12]提出了多信道協(xié)同方法以優(yōu)化節(jié)點能量消耗與網(wǎng)絡吞吐量。在基于多信道的節(jié)點調度技術中,更多的是通過信道間的時隙重用來優(yōu)化網(wǎng)絡吞吐量[13-14]或傳輸延遲[15-16]。上述方法中均沒有考慮節(jié)點在各狀態(tài)下的能量消耗差異。

由于數(shù)據(jù)匯聚過程中的Many-to-One數(shù)據(jù)傳輸特性,樹中非Sink與非葉子節(jié)點均可能需要接收并轉發(fā)來自子節(jié)點的數(shù)目不定的數(shù)據(jù)包,如果其子節(jié)點的數(shù)據(jù)包無法在連續(xù)時間內發(fā)送完成,將導致節(jié)點需要進行多次狀態(tài)切換才能夠完成數(shù)據(jù)匯聚。注意,節(jié)點狀態(tài)切換指的是將節(jié)點從休眠狀態(tài)喚醒,或者將節(jié)點從活動狀態(tài)切換至休眠狀態(tài)的過程。在文獻[17-18]中,作者證明了在低負載、低功耗的無線傳感器網(wǎng)絡中,節(jié)點消耗在狀態(tài)切換上的能量因數(shù)據(jù)傳輸過程消耗能量較小而不可忽略。本文以Mica2 Mote傳感器節(jié)點為例進行說明。表1列出了該傳感器節(jié)點在各狀態(tài)下的能量消耗情況[19]。圖1顯示了在不同傳輸速率與數(shù)據(jù)包大小情況下節(jié)點狀態(tài)切換能量與傳輸一個數(shù)據(jù)包的總能量消耗的比例P,P由式進行計算。

(1)

其中,Esw表示節(jié)點狀態(tài)切換能量消耗,Csw表示節(jié)點狀態(tài)切換功率,Tsw表示節(jié)點狀態(tài)切換時間,Et表示傳輸一個包含若干位數(shù)據(jù)包的能量消耗。Ct表示數(shù)據(jù)發(fā)送功率,Tt表示數(shù)據(jù)包發(fā)送時間。

圖1 Mica2 Mote節(jié)點狀態(tài)切換能量消耗

表1 Mica2 Mote節(jié)點各狀態(tài)下的能量消耗

從圖1中可知,當節(jié)點負載與傳輸速率都較低時(如4 byte,10 kbyte/s),節(jié)點狀態(tài)切換能量消耗占據(jù)了傳輸一個數(shù)據(jù)包總能耗的75%,即P=75%。隨著傳輸速率的增大,在相同負載情況下P最終能夠達到90%左右。因此,在低負載、低功耗的情況下,優(yōu)化節(jié)點能量消耗可以轉化為降低節(jié)點狀態(tài)切換能量消耗問題加以解決。

針對最小化節(jié)點狀態(tài)切換能量消耗問題,Ma等人[20]提出了集中式連續(xù)鏈路調度算法,該方法雖然優(yōu)化了節(jié)點狀態(tài)切換能量消耗,但是無法保證節(jié)點的所有數(shù)據(jù)能夠在一個周期內完成匯聚。與該算法不同,本文提出了結合多信道與TDMA技術的集中式能量優(yōu)化算法。利用多信道的正交特性,將不同節(jié)點的數(shù)據(jù)分派至不同信道,實現(xiàn)了數(shù)據(jù)并發(fā)傳輸,優(yōu)化了數(shù)據(jù)匯聚時間并保障了數(shù)據(jù)匯聚可靠性。然而,由于無線通信系統(tǒng)中可用的信道數(shù)有限,在考慮信道數(shù)約束基礎上,設計了基于接收端的連續(xù)時隙分配策略,優(yōu)化了節(jié)點的狀態(tài)切換次數(shù)及能量消耗。

1 問題定義

考慮數(shù)據(jù)匯聚樹T,由n個無線傳感器節(jié)點V={v1,v2,…,vn},單個匯聚節(jié)點Sink構成。在正常情況下,傳感器節(jié)點以固定周期采集與發(fā)送感知數(shù)據(jù)至Sink。

對于T而言,由于每個節(jié)點周期性進行數(shù)據(jù)匯聚,因此,可采用式(2)計算數(shù)據(jù)匯聚周期內的總能量開銷:

(2)

(3)

結合式(2)與式(3),對于任意樹T,可得E≥Emin。

在無線通信系統(tǒng)中,信道數(shù)受限于頻譜、帶寬等因素?？紤]最大可用信道數(shù)約束Ch,本文算法在實現(xiàn)連續(xù)時隙分配時所使用的信道數(shù)需要滿足如下條件:

Cu≤Ch

其中,Cu表示算法所使用的信道數(shù)。

2 算法設計

對任意數(shù)據(jù)匯聚樹T,本文算法的詳細執(zhí)行步驟如下:

Step2:基于接收端的連續(xù)時隙分配策略:采用自上而下的方式為每個節(jié)點分配時隙。具體而言,Sink為時隙分配起始節(jié)點,首先為其子節(jié)點,即樹T中第1層節(jié)點分配連續(xù)時隙。隨后第1層節(jié)點為第2層節(jié)點分配連續(xù)時隙,……,逐層往下為樹T中的節(jié)點分配連續(xù)時隙。

(4)

Step4:時隙分配調整:在Step2中,非葉子節(jié)點vi為其子節(jié)點集Li分配的發(fā)送時隙是以vi的最后一個發(fā)送時隙ti為起點,這將導致其所有子節(jié)點vj的發(fā)送時隙都位于節(jié)點vi之后。為了保證節(jié)點vi能夠按照“接收-發(fā)送”的活動模式進行數(shù)據(jù)匯聚,在完成所有節(jié)點的時隙分配之后,算法將對所有節(jié)點的時隙進行調整,確保節(jié)點vi的所有子節(jié)點的發(fā)送時隙位于其發(fā)送時隙之前。時隙調整方法如下:①求得網(wǎng)絡中已分配時隙的最大序號tmax。②將tmax減去節(jié)點的時隙,所得結果即為節(jié)點執(zhí)行數(shù)據(jù)發(fā)送時的最終時隙分配。對于節(jié)點vj,其最終發(fā)送時隙為:(tmax-tj′,tmax-tj)。

綜上所述,為了保證節(jié)點調度的正確執(zhí)行,每個節(jié)點需要維護一張節(jié)點活動調度表S,S的項由<信道,時隙列表>構成。節(jié)點按照其活動調度表S,在所分配的時隙內,使用對應的信道,執(zhí)行數(shù)據(jù)接收或發(fā)送,完成后節(jié)點將由活動狀態(tài)切換至睡眠狀態(tài),以節(jié)省能量消耗。

3 性能評估

本文采用MATLAB仿真實驗平臺對算法性能進行評估。為了便于比較,文中提出算法命名為CE-TDMA,而用于比較的算法包括能量優(yōu)化的集中式TDMA調度算法[20](命名為E-TDMA),支持多跳數(shù)據(jù)傳輸?shù)腡DMA算法(命名為M-TDMA)。在所有實驗中,傳感器節(jié)點數(shù)在200～1 000之間,且隨機部署在100m×100m的區(qū)域。節(jié)點有效通信范圍為10m。為實現(xiàn)E-TDMA的時隙重用,本文采用UnitDiskGraph傳輸模型,因而將節(jié)點干擾距離設置為20m,即兩倍于有效通信距離。數(shù)據(jù)匯聚樹采用最短路徑路由算法生成。本文以傳感器節(jié)點Mica2Mote的能量消耗為例來分析所提出算法的能量效率。節(jié)點各狀態(tài)的能量消耗情況如表1所示。節(jié)點狀態(tài)切換能量消耗=節(jié)點狀態(tài)切換次數(shù)x節(jié)點單次狀態(tài)切換的能量消耗。

圖2展示了一個數(shù)據(jù)匯聚周期內,傳感器節(jié)點的狀態(tài)切換次數(shù)比較。從該圖中可以看出,與E-TDMA算法和M-TDMA算法相比,CE-TDMA算法在信道數(shù)為3與5時降低了節(jié)點狀態(tài)切換次數(shù)。這表明,在大多數(shù)規(guī)模較小的網(wǎng)絡中,3～5條信道已經足夠優(yōu)化網(wǎng)絡在節(jié)點狀態(tài)切換上耗費的能量。除此之外,當信道數(shù)為5時,節(jié)點狀態(tài)切換次數(shù)與節(jié)點數(shù)基本呈線性關系,表明在數(shù)據(jù)匯聚過程中,大部分節(jié)點均只需要從休眠切換至喚醒狀態(tài)一次,并在數(shù)據(jù)匯聚結束后切換至休眠狀態(tài),然后節(jié)點將保持休眠直至下一數(shù)據(jù)匯聚周期到來。

圖2 傳感器節(jié)點狀態(tài)切換次數(shù)

圖3描述的是網(wǎng)絡完成了100個數(shù)據(jù)匯聚周期后,網(wǎng)絡中傳感器節(jié)點狀態(tài)切換能量消耗結果。該實驗結果表明:在網(wǎng)絡規(guī)模相同的情況下,CE-EDMA算法因減少了節(jié)點狀態(tài)切換次數(shù),消耗在節(jié)點狀態(tài)切換上的能量較M-TDMA算法與E-TDMA算法低。當信道數(shù)為5時,CE-TDMA算法節(jié)省的能量明顯降低。

圖3 傳感器網(wǎng)絡的節(jié)點狀態(tài)切換能量消耗

由于在采用Mica2 Mote節(jié)點的傳感器網(wǎng)絡中,其典型速率為19.2 kbit/s[19],因此在需要長時間低功耗、周期性運行的低負載無線傳感器網(wǎng)絡,如用于獲取溫濕度、CO2濃度等參數(shù)信息的微環(huán)境監(jiān)控系統(tǒng),CE-TDMA算法將能夠有效地延長網(wǎng)絡壽命。

為了驗證多信道技術在優(yōu)化數(shù)據(jù)匯聚時間上的性能,本文通過實驗比較了3種算法在相同網(wǎng)絡規(guī)模情況下的TDMA調度幀長度,其表示的是在一個數(shù)據(jù)匯聚周期內,將所有傳感器節(jié)點采集的感知數(shù)據(jù)投遞至數(shù)據(jù)匯聚節(jié)點需要的TDMA時隙的數(shù)量,即數(shù)據(jù)匯聚時間。從圖4顯示的實驗結果可以看出,由于采用了時隙重用策略,CE-TDMA和E-TDMA算法能夠讓多個節(jié)點在同一時隙內進行無沖突數(shù)據(jù)傳輸,從而明顯降低了數(shù)據(jù)匯聚時間。值得注意的是CE-TDMA算法在分別使用3條信道與5條信道時,算法在TDMA調度幀長度上沒有明顯變化。由于缺乏時隙重用,傳感器節(jié)點的數(shù)據(jù)傳輸活動無法并發(fā)執(zhí)行,M-TDMA無法有效優(yōu)化數(shù)據(jù)匯聚時間。

圖4 TDMA調度幀長度

為了明確信道數(shù)對網(wǎng)絡性能的影響,本文將信道數(shù)從2增加到10,并比較了網(wǎng)絡規(guī)模從200變化至600個節(jié)點時,CE-TDMA算法的性能變化情況。

圖5顯示了在不同的網(wǎng)絡規(guī)模中,信道數(shù)與節(jié)點狀態(tài)切換次數(shù)的關系。實驗結果表明,當信道數(shù)為2時,網(wǎng)絡中的節(jié)點為完成數(shù)據(jù)匯聚進行的狀態(tài)切換(即從休眠切換至活動狀態(tài)的過程)次數(shù)約為1.5。而隨著可用信道數(shù)增加至5條～6條,CE-TDMA算法能夠保證網(wǎng)絡中大部分節(jié)點均只需要切換一次狀態(tài)即可實現(xiàn)數(shù)據(jù)匯聚傳輸,即能夠保證大多數(shù)節(jié)點在數(shù)據(jù)匯聚過程中的模式為“接收-發(fā)送”,隨后節(jié)點切換至休眠狀態(tài)直到下一周期到來。

圖5 可用信道數(shù)與節(jié)點狀態(tài)切換次數(shù)的關系

圖6顯示了在可用信道數(shù)持續(xù)增加的情況下,各種網(wǎng)絡規(guī)模的節(jié)點狀態(tài)切換能量消耗變化情況。由于節(jié)點狀態(tài)切換能量與節(jié)點狀態(tài)切換次數(shù)密切相關,因此,圖6表現(xiàn)出與圖5類似的趨勢。

圖6 可用信道數(shù)與節(jié)點狀態(tài)切換能量消耗的關系

圖7 可用信道數(shù)與TDMA調度幀長度的關系

圖7顯示的是算法在可用信道數(shù)增加的情況下所得出的TDMA調度幀長度變化情況。實驗結果表明,在大多數(shù)網(wǎng)絡中,當可用信道數(shù)從2條增加至3條時,信道數(shù)的增加明顯降低了TDMA調度幀長度。其原因在于,多信道技術的加入主要是為了優(yōu)化節(jié)點能量消耗,時隙重用僅會發(fā)生在節(jié)點使用不同信道時,當時隙分配在同一信道時,時隙必然是不重用的,這些限制了節(jié)點間的時隙重用。由于信道數(shù)為2時,沒有足夠多的信道實現(xiàn)時隙重用,引起節(jié)點無法最小化其狀態(tài)切換次數(shù)(由圖5可證),也同樣導致TDMA幀長度無法得以優(yōu)化。隨著可用信道的加入,當信道數(shù)為3時,時隙能夠充分在信道間重用,因而,其TDMA幀長度有了明顯減小。然而,在網(wǎng)絡規(guī)模較小的情況下,由于在同一區(qū)域內,數(shù)據(jù)匯聚樹的最大跳數(shù)、節(jié)點分布情況的差異比較大規(guī)模網(wǎng)絡中明顯,可用信道數(shù)的變化將導致TDMA調度幀長度明顯變化。

4 結論

針對低負載、低功耗無線傳感器網(wǎng)絡在節(jié)點狀態(tài)切換上能量消耗較大的問題,在考慮了可用信道數(shù)有限的情況下,提出了結合多信道與TDMA技術的節(jié)點調度算法。算法結合了基于接收端的連續(xù)時隙分配策略、多信道分配與時隙調整機制實現(xiàn)了對節(jié)點喚醒能量消耗與數(shù)據(jù)匯聚時間的優(yōu)化,并通過仿真實驗證明了算法的性能。

本文所提出的節(jié)點調度算法充分利用了無線信道間的無沖突數(shù)據(jù)并發(fā)傳輸能力與TDMA在消除節(jié)點空閑偵聽與信道訪問競爭的先天優(yōu)勢,與常用的僅以節(jié)點能量消耗優(yōu)化為目標的調度方法相比較,算法能夠同時實現(xiàn)數(shù)據(jù)匯聚時間與節(jié)點能量消耗優(yōu)化。

本文的工作可以為無線傳感器網(wǎng)絡能量效率優(yōu)化方法設計提供參考。未來我們將在無線傳感器網(wǎng)絡測試平臺上實現(xiàn)并評估算法的性能,而且采用分布式的方法實現(xiàn)本文算法也需要進一步研究。

[1] 任豐原,黃海寧,林闖.無線傳感器網(wǎng)絡[J].軟件學報,2003,14(7):1282-1291.

[2]呂濤,施偉斌,范坤坤,等.WSN節(jié)點電池供電性能測試研究[J].傳感技術學報,2013,26(10):1457-1462.

[3]Magno M,Marinkovic S,Brunelli D,et al.Smart Power Unit with Ultra Low Power Radio Trigger Capabilities for Wireless Sensor Networks[C]//Proceedings of the Conference on Design,Automation and Test in Europe.EDA Consortium,2012:75-80.

[4]Zhang Y,Dolmans G.Wake-Up Radio Assisted Energy-Aware Multi-Hop Relaying for Low Power Communications[C]//IEEE Wireless Communications and Networking Conference(WCNC),2012:2498-2503.

[5]陳立建,周雪,雷艷靜,等.一種基于功率控制的WSN自適應能量高效傳輸模式研究[J].傳感技術學報,2014,27(6):835-841.

[6]張曉玲,梁煒,于海斌,等.無線傳感器網(wǎng)絡傳輸調度方法綜述[J].通信學報,2012,33(5):143-157.

[7]Zhang L,Ye Q,Cheng J,et al.Fault-Tolerant Scheduling for Data Collection in Wireless Sensor Networks[C]//IEEE Global Communications Conference(GLOBECOM),2012:5345-5349.

[8]Zhao W,Tang X.Scheduling Sensor Data Collection with Dynamic Traffic Patterns[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(4):789-802.

[9]Niu J,Deng Z.Distributed Self-Learning Scheduling Approach for Wireless Sensor Network[J].Ad Hoc Networks,2013,11(4):1276-1286.

[10]Luo T,Motani M,Srinivasan V.Energy-Efficient Strategies for Cooperative Multichannel MAC Protocols[J].IEEE Transactions on Mobile Computing,2012,11(4):553-566.

[11]Hsu T H,Kim T H,Chen C C,et al.A Dynamic Traffic-Aware Duty Cycle Adjustment MAC Protocol for Energy Conserving in Wireless Sensor Networks[J].International Journal of Distributed Sensor Networks,2012.

[12]Luo T,Motani M,Srinivasan V.Energy-Efficient Strategies for Cooperative Multichannel MAC Protocols[J].Mobile Computing,IEEE Transactions on,2012,11(4):553-566.

[13]Soua R,Livolant E,Minet P.An Adaptive Strategy for An Optimized Collision-Free Slot Assignment in Multichannel Wireless Sensor Networks[J].Journal of Sensor and Actuator Networks,2013,2(3):449-485.

[14]Soua R,Minet P,Livolant E.MODESA:An Optimized Multichannel Slot Assignment for Raw Data Convergecast in Wireless Sensor Networks[C]//2012 IEEE 31st International Performance Computing and Communications Conference(IPCCC),2012:91-100.

[15]Guo P,Jiang T,Zhang Q,et al.Sleep Scheduling for Critical Event Monitoring in Wireless Sensor Networks[J].Parallel and Distributed Systems,IEEE Transactions on,2012,23(2):345-352.

[16]Nasser N,Karim L,Taleb T.Dynamic Multilevel Priority Packet Scheduling Scheme for Wireless Sensor Network[J].IEEE Transactions on Wireless Communications,2013,12(4):1448-1459.

[17]van L H,Havinga P.A Lightweight Medium Access Protocol(Lmac)for Wireless Sensor Networks:Reducing Preamble Transmissions and Transceiver State Switches[C]//1st International Workshop on Networked Sensing Systems,2004:205-208.

[18]Xing G,Lu C,Zhang Y,et al.Minimum Power Configuration in Wireless Sensor Networks[C]//Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computting,2005:390-401.

[19]Lee W L,Datta A,Cardell-Oliver R.Flexi TP:A Flexible-Schedule-Based TDMA Protocol for Fault-Tolerant and Energy-Efficient Wireless Sensor Networks[J].IEEE Transactions on Parallel and Distributed Systems,2008,19(6):851-864.

[20]Ma J,Lou W,Wu Y,et al.Energy Efficient TDMA Sleep Scheduling in Wireless Sensor Networks[C]//IEEE INFOCOM 2009,2009:630-638.

A Finite Channel Based Energy-Efficient Node-Scheduling Mechanism*

ZENGBo1,2*,LiShanshan2,WANGHui1,2

(1.The Institute of Network and Communication Technology,Henan University of Science and Technology,Luoyang He’nan 471023,China;2.Network and Information Center,Henan University of Science and Technology,Luoyang He’nan 471023,China)

In a low-load,low-power wireless sensor network,energy consumption of the node state switching should notbe neglected because energy for data transmission is less.Focusing on this problem,a node scheduling algorithm combine with multi-channel technology and time division multiple access(TDMA)technology is proposed.The algorithm designs a consecutive slots allocation strategy based on receiver to reduce the node status switching times,proposes a channel allocation and slot adjustment mechanism under the constraints that the available wireless channels are limited,and implements slots reusing and minimizes the limited channels constraints effects on optimizing times of node status switching.The simulation experiments results show the algorithm can effectively improve the node energy efficiency when the number of available wireless channel is between 3 and 5,while the algorithm can achieve the optimized data collection time when the number of available wireless channel is greater than 3.

wireless sensor networks;energy;TDMA;multichannel;schedule;simulation

曾 波(1981-),男,河南科技大學講師,目前的主要研究領域是無線傳感器網(wǎng)絡和異構網(wǎng)絡性能優(yōu)化,bozeng@haust.edu.cn;

李姍姍(1987-),女,河南科技大學助教,主要研究方向為無線網(wǎng)絡技術,lss@haust.edu.cn。

項目來源:河南省科技攻關項目(13B510001)

2014-10-11 修改日期:2014-11-21

C:7230

10.3969/j.issn.1004-1699.2015.02.019

TP393

A

1004-1699(2015)02-0254-06