鄭學偉

（1.遼寧廣播電視大學，沈陽110034；2.遼寧裝備制造職業(yè)技術(shù)學院，沈陽110161）

基于能量探測的WSN節(jié)點調(diào)度算法研究*

鄭學偉1，2*

（1.遼寧廣播電視大學，沈陽110034；2.遼寧裝備制造職業(yè)技術(shù)學院，沈陽110161）

針對無線傳感器網(wǎng)絡在節(jié)點傳輸過程中的延遲與鏈路質(zhì)量問題，設計一種基于能量探測的節(jié)點休眠調(diào)度算法EAS，通過對節(jié)點插入蘇醒時隙來減小端到端之間的延遲，并根據(jù)每個節(jié)點的剩余能量值進行能量探測，使整個網(wǎng)絡中各節(jié)點的能量相對均衡地消耗，在保證傳輸質(zhì)量的基礎上達到延長網(wǎng)絡的生命周期的目的。實驗結(jié)果表明，對比現(xiàn)有算法，EAS算法能夠在保證使WSN網(wǎng)絡在延遲一定的情況下明顯降低能耗，延長整個網(wǎng)絡的工作壽命。

WSN；傳輸延遲；節(jié)點休眠調(diào)度；能量探測

無線傳感器網(wǎng)絡WSN（Wireless Sensor Networks）是由在一定區(qū)域內(nèi)大量部署的微型傳感器節(jié)點組成的，將被監(jiān)控對象的監(jiān)測信息發(fā)給監(jiān)控者，集中了傳感器技術(shù)、分布式處理技術(shù)及嵌入式技術(shù)，是一種自組織多跳的無線網(wǎng)絡［1］。由于WSN的節(jié)點采用電池供電，能量壽命一直是WSN生存周期中的核心問題。如何降低WSN在傳輸過程中的能耗，最大限度地延長節(jié)點的使用周期進而延長整個WSN的生存時間一直研究者關(guān)注的焦點。目前的研究主要集中在硬件設計和電源管理方面。通過改變節(jié)點占空比技術(shù)來節(jié)省能量是近一年新興起的研究方向［2］。降低節(jié)點的占空比可以有效地延長節(jié)點的使用壽命，但是降低占空比會導致整個WSN在傳輸過程中延遲增大，只有有效地降低節(jié)點傳輸過程中的延遲才能保證低占空比節(jié)點的WSN達到預期的性能指標。傳統(tǒng)的降低延遲算法往往忽略鏈路質(zhì)量的因素，對節(jié)點能量的變化沒有進行深入的研究。目前，國內(nèi)外的一些學者也針對節(jié)點剩余能量和鏈路質(zhì)量等問題提出了一些解決方法。ESC協(xié)議［3］通過引入一個透明的中間件來最大程度減小網(wǎng)絡傳輸延遲，從而延長節(jié)點壽命。MMSPEED提出了一種多路徑多速度的路由協(xié)議用來在一定程度上保證網(wǎng)絡的鏈路質(zhì)量［4］。PTW（Pipelined Tone Wakeup）［5］介紹了一種在能耗節(jié)省和端到端延遲之間的平衡方法。Gu［6］等人提出了SDC算法，SDC算法能夠在特定條件下控制延遲，節(jié)省節(jié)點的能量消耗。但是，該算法仍然存在著一些不足之處，如并沒有考慮鏈路質(zhì)量可能引起的數(shù)據(jù)重傳，從而導致節(jié)點間的傳輸延遲增大。

本文提出了基于能量檢測的節(jié)點休眠調(diào)度算法EAS（Energy-Aware based Scheduling Scheme），通過對節(jié)點插入蘇醒時隙來減小端到端之間的延遲，并根據(jù)每個節(jié)點的剩余能量值進行能量探測，從而有效地避免節(jié)點過早死亡，使整個網(wǎng)絡中各節(jié)點的能量相對均衡地消耗，延長網(wǎng)絡的生命周期。

項目來源：遼寧省教育廳科技項目（L2014579）；遼寧省現(xiàn)代遠程教育學會重點課題項目（2014XH02-12）；國家開放大學規(guī)劃課題項目（G14A0602Y）

收稿日期：2015-06-15修改日期：2015-08-12

1　系統(tǒng)模型

1.1網(wǎng)絡模型

一個已經(jīng)部署完成的WSN系統(tǒng)中的節(jié)點一般處于工作和休眠兩種狀態(tài)，處于休眠狀態(tài)的節(jié)點關(guān)閉除定時以外的一切功能，而處于工作狀態(tài)的節(jié)點將提供感知、偵聽與數(shù)據(jù)通信功能。

節(jié)點i的一個工作周期是由工作和休眠兩種狀態(tài)組成的集合Γi，假定T為節(jié)點i的一個周期持續(xù)的時間，用數(shù)組表示節(jié)點i在第 j次的工作狀態(tài)，式中tij表示第 j次的工作狀態(tài)的開始時間；τ表示該次工作狀態(tài)持續(xù)的時間，即時隙個數(shù)，整個周期T時隙大小固定，節(jié)點i在周期T中蘇醒的次數(shù)為n，則節(jié)點i的一個周期工作調(diào)度表，見式（1）。

節(jié)點占空比DC（Duty Cycle）指的是傳感器節(jié)點i在周期T中處于工作狀態(tài)所花費的時間同整個周期的比值，用DCi表示節(jié)點i的占空比，根據(jù)式（1）得出：

圖1表示了節(jié)點i的一個工作周期，一個方框表示一個時隙，周期T為10個時隙。圖中用陰影代表節(jié)點的工作狀態(tài)，空白代表節(jié)點的休眠狀態(tài)，因此，可以計算出節(jié)點i在一個工作周期內(nèi)的工作調(diào)度表為，從而可以算出節(jié)點i的占空比為DCi==40%。

圖1　節(jié)點工作調(diào)度表

1.2傳輸延遲

當一個普通的WSN中所有節(jié)點都處于工作狀態(tài)時，相鄰節(jié)點間可以隨時發(fā)送或接收信息，節(jié)點的數(shù)據(jù)延遲一般是毫秒級。但是當處于一個低占空比的WSN中時，由于有相當數(shù)量的節(jié)點處于休眠狀態(tài)，節(jié)點間傳送數(shù)據(jù)的延遲可能是幾秒甚至是十幾秒。我們將節(jié)點數(shù)據(jù)傳送時所等待的時間定義為休眠延遲，由于在低占空比的WSN數(shù)據(jù)傳輸中由于休眠節(jié)點產(chǎn)生的數(shù)據(jù)延遲要遠遠大于正常通信的數(shù)據(jù)延遲，我們在算法設計時忽略不考慮通信延遲。考慮問題的關(guān)鍵是鏈路數(shù)據(jù)傳輸?shù)馁|(zhì)量，不考慮鏈路質(zhì)量的話，延遲計算比較簡單，直接計算數(shù)據(jù)傳輸時的休眠延遲之和即可，考慮鏈路質(zhì)量則比較復雜，由于數(shù)據(jù)傳輸可能失敗，則要考慮到數(shù)據(jù)重傳帶來的傳輸成本。

1.2.1不考慮鏈路質(zhì)量

圖2所示的傳輸網(wǎng)絡中，有A，B，C 3個傳輸節(jié)點，3個節(jié)點的工作周期都為10τ，τ取值為1 s。節(jié)點A的工作調(diào)度是，同理可知。如果用dij（）t表示發(fā)送節(jié)點i在時間t收到數(shù)據(jù)信息，然后將該數(shù)據(jù)信息發(fā)送給其鄰居節(jié)點 j的休眠延遲，Dij（t）表示非相鄰節(jié)點i，j的休眠延遲，那么可以計算出節(jié)點A和節(jié)點B之間的休眠延遲為dAB（1）=（4，1）·τ=3×1=3 s，則可以計算出DAc（1）=8 s。

圖2　不考慮鏈路質(zhì)量的網(wǎng)絡傳輸模型

1.2.2考慮鏈路質(zhì)量

在實際的工作環(huán)境中，WSN節(jié)點數(shù)據(jù)傳輸?shù)逆溌焚|(zhì)量不可能是100%，我們假定pij為節(jié)點i到j之間的鏈路質(zhì)量，nij節(jié)點i到j之間數(shù)據(jù)傳輸?shù)闹貍鞔螖?shù)，若重傳次數(shù)大于最大重傳次數(shù)nmax則將數(shù)據(jù)包丟棄，如圖3所示，假設一個WSN的T為100 s，nmax=3（本文以下的例子中都采取以上數(shù)據(jù)假設）。假設節(jié)點A至B的數(shù)據(jù)傳輸鏈路質(zhì)量為pAB=0.8，節(jié)點B至節(jié)點C的數(shù)據(jù)傳輸鏈路質(zhì)量為pBC=0.6，則節(jié)點A到節(jié)點C之間端到端的休眠延遲DAc（1）的期望值為：

圖3　考慮鏈路質(zhì)量的網(wǎng)絡傳輸模型

僅僅是在鏈條路徑的運算中，在考慮鏈路質(zhì)量因素后，節(jié)點A至節(jié)點C的休眠延遲就由8 s增長到約81.64 s，整整增長了10倍，可見隨著網(wǎng)絡傳輸過程中節(jié)點跳數(shù)的增加，休眠延遲的增長將是幾何級數(shù)的增加。

2　算法設計

EAS算法的核心思想是：針對WSN鏈路傳輸過程中的能量消耗問題，增加節(jié)點蘇醒時隙的次數(shù)進行節(jié)點休眠調(diào)度，在進行節(jié)點休眠調(diào)度的同時進行以保證能量探測使得網(wǎng)絡均勻地消耗能量，從而延長網(wǎng)絡的工作時間。能量消耗最小。

2.1節(jié)點休眠調(diào)度算法

2.1.1節(jié)點相鄰

由于在鏈路質(zhì)量不可靠的WSN中延遲大而不能夠滿足實際的應用，圖4中，節(jié)點A向節(jié)點B傳輸?shù)男菝哐舆t期望值約為69.02 s，在節(jié)點B增加一次蘇醒時隙后，休眠延遲期望值值變?yōu)?1.55 s，延遲降低83%。

對于WSN中鄰居節(jié)點i和 j，節(jié)點j在增加一次蘇醒時隙后其工作周期由Γj=｛｝時，如果此時+1，則新的延遲期望值如式（4）所示。

圖4　增加蘇醒時隙減小延遲

但是一味的增加節(jié)點的蘇醒時隙次數(shù)會大大增加節(jié)點的能量消耗，算法的關(guān)鍵在于取得增加的蘇醒時隙次數(shù)與能量消耗的平衡，即在增加蘇醒時隙次數(shù)最少的情況下達到符合要求的數(shù)據(jù)傳輸延遲。算法設計的關(guān)鍵在于節(jié)點間休眠延遲的計算。假定節(jié)點i在t時刻收到數(shù)據(jù)包并準備發(fā)送給節(jié)點 j，中間跳數(shù)為m，達到理想休眠延遲期望值時所需的蘇醒時隙次數(shù)為h次，h≤m，首先根據(jù)節(jié)點i到 j計算出延遲期望值。若，即延遲期望值小于等于實際延遲值B，滿足實際應用需要，停止計算。若，即延遲期望值大于實際延遲值B，則繼續(xù)運算，逐步對蘇醒時隙增加，每增加一次重新計算延遲期望值，直至滿足，假設此時增加h=m次蘇醒時隙，此時的h值最小，消耗的能量也最少。對于相鄰節(jié)點i和j，可通過增加蘇醒時隙減少休眠延遲，延遲期望值計算如下所示：

2.1.2節(jié)點不相鄰

上節(jié)研究的是理想狀況，即節(jié)點i和j相鄰?，F(xiàn)假設節(jié)點i和j不相鄰，節(jié)點i向j發(fā)送數(shù)據(jù)的話須經(jīng)過某條路徑，假設須經(jīng)過m-1跳節(jié)點。這樣，對于節(jié)點j接收從節(jié)點i發(fā)送過來的數(shù)據(jù)可能會出現(xiàn)兩種情況：

節(jié)點i和j相鄰數(shù)據(jù)傳輸過程，存在節(jié)點1，如果節(jié)點1不增加蘇醒時隙，則從節(jié)點1到節(jié)點j增加蘇醒時隙h次；如果從節(jié)點1開始增加蘇醒時隙，則從節(jié)點1到節(jié)點j增加蘇醒時隙h-1次。根據(jù)以上分析，通過迭代計算節(jié)點i向j的延遲期望值為：

圖5　EAS算法示意圖

圖5（a）為節(jié)點A到節(jié)點C初始休眠延遲期望值約為135.32 s，圖5（b）增加一次蘇醒時隙后能夠取得的最小值為72.15 s，圖5（c）增加兩次蘇醒時隙的值為38.22 s。

2.2能量探測

通過實際應用檢測發(fā)現(xiàn)，在WSN網(wǎng)絡中，由于實際應用環(huán)境很復雜，導致不同的節(jié)點對能量的消耗差異往往會很大。低能量值節(jié)點可能會比預期更早的失效，而每增加一個失效點都會大大降低整個WSN的性能，縮短WSN的生存周期。為保證WSN的效能與生存周期，需要在節(jié)點休眠調(diào)度算法的基礎上增加能量探測，通過能量探測使能量值較低的節(jié)點盡可能的處于休眠狀態(tài)，用Eavg表示網(wǎng)絡平均能量，節(jié)點j自身的剩余能量用jEres表示。具體算法見式（7）。

式（7）中，α為動態(tài)權(quán)重值。當節(jié)點1要想增加蘇醒時隙時，先將自己的剩余能量和網(wǎng)絡平均能量進行比較，檢測條件，只有當剩余能量大于α倍的網(wǎng)絡平均能量時會增加蘇醒時隙，否則按照原來的工作調(diào)度表工作。通過仿真數(shù)據(jù)測試，當α=1.2為宜。

圖6中，假設節(jié)點B剩余能量不足，不考慮節(jié)點剩余能量的情況下，節(jié)點A到節(jié)點C的休眠延遲期望值約為］≈45.8 s?？紤]節(jié)點剩余能量，節(jié)點B不動而節(jié)點C增加蘇醒時隙，得到］≈80.7 s，根據(jù)結(jié)果可得網(wǎng)絡中延遲期望值變大，但是網(wǎng)絡生存周期卻得到延長。

圖6　EAS能量探測過程

3　仿真實驗與性能評價

3.1EAS算法性能仿真

為驗證EAS算法的性能，我們在延遲要求分別為1 000 s、700 s、400 s、100 s和10 s的情況下對算法進行驗證，在0～1之間每次產(chǎn)生一個隨機數(shù)，如果該數(shù)值不小于鏈路的質(zhì)量則表示傳輸成功，小于則傳輸失敗，每次增加蘇醒時隙的仿真次數(shù)為50次，實驗結(jié)果如圖7所示。

由圖7可得，不同的延遲條件對實驗結(jié)果有較大的影響，但如果延遲條件一定的話，隨著蘇醒時隙次數(shù)的增加，滿足條件的百分比會迅速提高，以延遲要求為1 000 s為例，當蘇醒時隙增加1次時滿足條件的百分比約為53.31%，蘇醒時隙增加2次時滿足條件的百分比約為79.84%，蘇醒時隙增加3次時滿足條件的百分比約為91.2%，但當延遲要求縮短為10 s時，已經(jīng)很難通過增加蘇醒時隙來提高滿足條件的百分比。

圖7　EAS算法在不同延遲要求下滿足條件百分比

3.2不同參數(shù)對算法性能的影響

本節(jié)對不同條件下的EAS［7］算法和TOSS算法［8］就前面指出的標準進行仿真實驗已驗證算法性能。

3.2.1延遲要求的影響

在EAS算法中，為滿足不同要求的延遲值，蘇醒時隙次數(shù)需要不同程度的增加，但是隨著蘇醒時隙次數(shù)的增加，網(wǎng)絡的生存周期也會受到不同程度的影響。在不同的延遲值下，EAS和TOSS算法兩種算法的仿真結(jié)果如圖8所示。

由圖8（a）可以看出，隨著延遲要求的增大，為滿足該要求值而要增加的蘇醒時隙次數(shù)最小值會隨之減小。這是因為隨著要求延遲增大，只需要增加很少的幾次蘇醒時隙就能滿足。但是在相同延遲要求的情況下，EAS算法比TOSS算法要增加的蘇醒時隙次數(shù)少。比如說延遲要求值在800 s的情況下，EAS算法要增加的蘇醒時隙次數(shù)最小值為9次，而TOSS算法要增加的蘇醒時隙次數(shù)最小值為11次，EAS算法較TOSS算法要增加的蘇醒時隙次數(shù)最小值較少了18%。在要求的延遲值為500 s的情況下，TOSS算法要增加的蘇醒時隙次數(shù)最小值為17次，而EAS算法要增加的蘇醒時隙次數(shù)為15次，EAS算法仍比TOSS要增加的時隙小。EAS算法比TOSS算法要增加的蘇醒時隙次數(shù)少，就表明EAS算法使節(jié)點在更多的時間內(nèi)將會處于休眠狀態(tài)，從而可以節(jié)省節(jié)點能量消耗，延長網(wǎng)絡的工作壽命。由圖8（b）可以看出，隨著要求的延遲值減小，在EAS算法和TOSS算法下都會延長網(wǎng)絡的生命周期。EAS算法比TOSS算法在差距最大時延長46%的生命周期，在差距最小的情況下也會延長27%的生命周期。

3.2.2節(jié)點占空比的影響

節(jié)點占空比對休眠延遲期望值和節(jié)點能量消耗都會產(chǎn)生明顯的影響，也將會影響要增加的蘇醒時隙次數(shù)最小值和網(wǎng)絡生命周期。本次仿真在固定延遲要求條件下，考察節(jié)點占空比對EAS算法性能的影響（如圖9所示）。

從圖9（a）的仿真結(jié)果可以看出，隨著節(jié)點占空比越來越高，要滿足給定延遲要求所需增加的蘇醒時隙最小值也會減少。在同一占空比下，EAS算法比TOSS算法要增加的蘇醒時隙次數(shù)最小值要小。在占空比為2%的情況下，EAS算法要增加的次數(shù)最小值為12次，而TOSS算法則需要15次。EAS算法和TOSS就需要增加的次數(shù)最小值相比，根據(jù)仿真結(jié)果，在最好的情況下，EAS算法將比TOSS少60%左右。隨著節(jié)點占空比越來越高，網(wǎng)絡的生命周期會顯著下降，這是因為節(jié)點處于空閑狀態(tài)的時間會越來越多。在節(jié)點占空比從1%～5%變化的過程中，使用EAS算法比TOSS算法更能夠延長網(wǎng)絡的工作時間。在最好的情況下延長近42%，在最壞的情形下也會比TOSS算法延長21%的生命周期。

圖8　延遲要求的影響

圖9　節(jié)點占空比的影響

4　結(jié)束語

針對低占空比無線傳感器網(wǎng)絡中鏈路質(zhì)量不高、延遲大等特點，提出了EAS算法。該算法在考慮鏈路質(zhì)量的基礎上，使得網(wǎng)絡能夠在滿足一定延遲要求的情況下所消耗的能量最??；同時加入能量探測技術(shù)，使得節(jié)點能夠均勻地消耗能量，從而延長網(wǎng)絡的工作時間。EAS算法可以為限定延遲下的節(jié)點休眠調(diào)度算法提供研究基礎，同時，在通過能量探測來延長網(wǎng)絡生命周期方面提供思路。實驗結(jié)果表明，對比現(xiàn)有算法，EAS算法能夠在保證WSN網(wǎng)絡延遲一定的情況下能夠明顯降低能耗，可以延長整個網(wǎng)絡的工作壽命。

［1］ 高建良，徐勇軍，李曉維.基于加權(quán)中值的分布式傳感器故障檢測［J］.軟件學報，2007，18（5）：1208-1217.

［2］ 閆丹，雷霖.基于免疫神經(jīng)網(wǎng)絡的無線傳感器網(wǎng)絡節(jié)點的故障診斷［J］.自動化信息，2009，95（3）：37-39.

［3］ 邢倩，郝鵬，劉維亭，等.基于WLSE-KF的傳感器融合定位算法研究［J］.電子器件，2014，37（6）：1199-1203.

［4］ 托乎提努爾，陳曙.一種無需測距的無線傳感器網(wǎng)絡定位算法研究［J］.電子器件，2013，36（4）：527-530.

［5］ 胡中棟，謝金偉.基于近似投影校正的無線傳感器網(wǎng)絡三維定位機制［J］.傳感技術(shù)學報，2014，27（11）：1573-1577.

［6］ Perspective MLAP.Machine Learning：A Probabilistic Perspective ［J］.The MIT Press，2012：348-352.

［7］ Chang C，Lin C，Hsieh C，et al.Patrolling Mechanisms for Disconnected Targets in Wireless Mobile Data Mules Networks：Parallel Processing（ICPP）［C］//2011 International Conference on.2011，93-98.

［8］ 吳凡，彭力.基于節(jié)點密度及路徑優(yōu)化的無線傳感器網(wǎng)絡定位算法研究［J］.傳感技術(shù)學報，2014，27（11）：1539-1544.

鄭學偉（1979-），男，滿族，遼寧撫順人，遼寧廣播電視大學副教授。碩士，研究方向為無線傳感器網(wǎng)絡、移動通信。

WSN Nodes Scheduling Algorithms Based on Energy Detection*

ZHENG Xuewei1，2*
（1.Liaoning Radio and TV University，Shenyang 110034，China；2.Liaoning Vocational and Technical College of Equipment Manufacturing，Shenyang 110161，China）

During the process of node transmission，an energy-aware based scheduling scheme（EAS）can be designed against the delay and link quality problem in WSN.Through inserting time slot into the node，the port-to-port delay can be reduced；in the meanwhile，the remaining energy value of each node can be detected，thereby relatively consuming the energy of each node in the network on a balanced basis，and extending the network lifecycle on the premise of ensuring the transmission quality.Test finding shows that EAS scheme can significantly reduce energy consumption by stabilizing WSN delay，thus extending the working life of entire network.

WSN；delay transmission；node scheduling scheme；energy detection

TN923

A

1005-9490（2016）03-0581-05

EEACC：6150P10.3969/j.issn.1005-9490.2016.03.016