基于能量探測的WSN節點調度算法研究*

鄭學偉

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

基于能量探測的WSN節點調度算法研究*

鄭學偉1，2*

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

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

WSN；傳輸延遲；節點休眠調度；能量探測

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

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

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

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

1　系統模型

1.1網絡模型

一個已經部署完成的WSN系統中的節點一般處于工作和休眠兩種狀態，處于休眠狀態的節點關閉除定時以外的一切功能，而處于工作狀態的節點將提供感知、偵聽與數據通信功能。

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

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

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

圖1　節點工作調度表

1.2傳輸延遲

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

1.2.1不考慮鏈路質量

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

圖2　不考慮鏈路質量的網絡傳輸模型

1.2.2考慮鏈路質量

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

圖3　考慮鏈路質量的網絡傳輸模型

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

2　算法設計

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

2.1節點休眠調度算法

2.1.1節點相鄰

由于在鏈路質量不可靠的WSN中延遲大而不能夠滿足實際的應用，圖4中，節點A向節點B傳輸的休眠延遲期望值約為69.02 s，在節點B增加一次蘇醒時隙后，休眠延遲期望值值變為11.55 s，延遲降低83%。

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

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

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

2.1.2節點不相鄰

上節研究的是理想狀況，即節點i和j相鄰。現假設節點i和j不相鄰，節點i向j發送數據的話須經過某條路徑，假設須經過m-1跳節點。這樣，對于節點j接收從節點i發送過來的數據可能會出現兩種情況：

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

圖5　EAS算法示意圖

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

2.2能量探測

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

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

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

圖6　EAS能量探測過程

3　仿真實驗與性能評價

3.1EAS算法性能仿真

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

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

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

3.2不同參數對算法性能的影響

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

3.2.1延遲要求的影響

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

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

3.2.2節點占空比的影響

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

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

圖8　延遲要求的影響

圖9　節點占空比的影響

4　結束語

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

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

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

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

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

［5］ 胡中棟，謝金偉.基于近似投影校正的無線傳感器網絡三維定位機制［J］.傳感技術學報，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］ 吳凡，彭力.基于節點密度及路徑優化的無線傳感器網絡定位算法研究［J］.傳感技術學報，2014，27（11）：1539-1544.

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

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