一種基于灰色模型的預測調度算法

陳鑫杰

(福建八達電信技術有限公司，福建漳州363108)

1.引言

無線傳感器網絡(Wireless Sensor Networks，WSNs)是一種具有廣泛用途的網絡。在應用環境中布置傳感器節點時，為了保證監控的質量，通常需要密集地部署節點。當網絡中的所有節點都處于工作狀態時，一旦檢測到某個事件發生，多個節點都會捕捉到信息向上提交，從而引起無線信道的沖突與感知數據的重傳，不僅增加了通信的時延，降低了網絡的吞吐量，也浪費了節點的能量，縮短了網絡的生存時間。解決這一問題的有效辦法就是對節點的狀態進行調度，讓節點輪流工作和休眠，以減少信息的發送和信道的沖突。

目前科研人員已經提出了許多調度算法。在節點分布滿足泊松靜態點過程條件下，Hisn[1]等把節點調度分為兩種：節點隨機調度和節點協作調度。節點隨機調度算法[2-3]僅執行一次，通過隨機分組形式將每個傳感器節點劃分到某一組或某幾組，算法結束之后，依次調度每一組的節點工作。節點協作調度算法需要節點與周圍節點進行通信，且傳感器節點在每一輪的開始執行一次算法，按照某種競爭機制從所有節點中選擇若干個節點作為活動節點。節點協作調度算法又可以進一步分為基于位置信息的節點調度[4]和無位置信息的節點調度[5]。可以看出，節點調度問題與覆蓋性能、路由規劃和網絡連通性等問題存在一定關聯。

與上述研究的思路不同，本文利用節點采集數據在時間上的相關性，提出了一種基于灰色模型[6]的預測調度算法(PSGM)。PSGM盡量讓能量較低的節點休眠，并采用灰色模型來預測節點休眠時丟失的數據。仿真結果表明，算法能夠有效地延長網絡的生命周期，達到了設計的目標。

2.網絡模型

PSGM算法對WSNs做如下假設：

(1)節點：所有的節點同質，初始能量相同，并具有數據緩存能力。sink節點除了具有較高的能量外，其它設置與一般節點相同。

(2)分布：節點被隨機布置在一個矩形區域內，并假定每個節點可以獲取自己的能量信息。

(3)網絡結構：網絡為一個兩層的簇結構。節點可以按多種方法分簇，如位置相關、應用設定、隨機產生等，簇中成員產生數據后向簇頭節點發送，簇頭節點匯總所有簇成員的數據后，合并成一個數據包發送給sink節點。

3.灰色模型

灰色預測法是一種對含有不確定因素的系統進行預測的方法。自灰色系統理論問世以來，灰色預測的理論與應用研究都取得了較大的進展。灰色預測控制的顯著特點就是在信息不足的情況下獲得較好的控制效果。灰色模型有許多種，其中GM(1，1)模型是由鄧聚龍教授提出的一個經典灰色預測模型。GM(1，1)模型建模的過程是：首先對原始數據進行累加，得到呈一定規律的新的序列，其相應的曲線或折線可以用典型曲線來逼近，然后用逼近的曲線作為模型，以此來對系統進行預測。具體過程闡述如下。

假設GM(1，1)的原始時間序列有n個觀察值，為：X(0)={x(0)(1)，x(0)(2)，…，x(0)(n)}。在實際問題中，這一組數據提供的信息并不完全，具有很大的隨機性。為了使其呈現一定的規律性，一般對其進行一次累加處理，經過數據處理后的時間序列稱為生成列，公式如(1)所示。

得到新的序列后，運用數學中的動態線性模型對生成的數據進行擬合和逼近，得到微分方程式如(2)所示。

其中，a稱為發展系數，u稱作內生控制灰數。此時滿足的臨界條件是x(1)(1)=x(0)(1)。微分方程式中的a和u均為待求解的未知變量。求出a和u的估計值后，將其代入方程式中，得到與時間有關的方程，如(3)所示。

使用式(3)即可進行數據的擬合與預測。

4.基于灰色模型的預測調度算法

PSGM是基于分層拓撲的網絡結構。其主要思路是，簇成員向簇首節點發送數據時，順帶發送自己的剩余能量。簇首節點接收到數據后，將其保存。并根據節點的能量狀況，選取簇中能量較低的節點，通知其休眠。在下一輪提交數據時，簇首節點根據休眠節點前面提交的數據預測出其應提交的數據。

4.1 數據的預測

PSGM算法的核心步驟就是簇首節點對休眠節點進行的數據預測。為了實現這個功能，PSGM算法采用了GM(1，1)模型。算法的主要步驟是：

首先，簇首節點為每一個簇成員節點k建立一個數組data，用于保存該節點k的前n個數據。這n個數據可以是節點k提交過來的，也可以是節點k休眠時由簇首節點計算出來的。

如果節點在本輪中沒有休眠，則簇首節點將其提交的數據放入data中，并剔除最舊的數據。如果節點被調度休眠，則簇首節點取出data數組中的數據，作為X(0)序列，進行累加處理后得到X(1)序列，將其帶入(2)中，解出a和u的值后，生成(3)式，并計算出n+1項的值，即作為此輪的預測值。同樣的，該預測值也應放入data數組中，并剔除最舊的數據。

n的選擇跟具體的應用相關，數據波動較大的環境n值應相應增大，否則可以減小。在我們的試驗中，n取值15。

為了防止誤差的累積，盡可能提高預測的精度，在PSGM算法中，節點不能連續休眠兩輪。即休眠節點即使其能量仍為最低，下一輪也必須工作，這樣可以確保序列中至少有50%的真實數據。

4.2 算法流程

PSGM算法的具體步驟如下：

(1)初始化：網絡進行初始化分簇工作。分簇算法可以采用已有的算法，也可以人工設定。

(2)獲得初始的時間序列：所有的節點先工作n輪，向簇首節點提交n個數據，發送數據時順帶提交自己的剩余能量。簇首節點一方面將收集的數據聚合后提交給sink節點，另一方面保存每個節點的n個數據。

(3)調度休眠：從第n+1輪開始，簇首節點根據簇內成員的能量情況按照一定的比率r來選擇節點，通知其休眠。選擇節點時，忽略上輪已休眠過的節點。

(4)預測數據：預測節點針對休眠節點進行數據預測，并更新其data數組。然后簇首節點將預測數據與收集的真實數據一起聚合后向上提交。

(5)喚醒節點：休眠節點休息一輪后，進入工作狀態。

(6)循環(3)～(5)，直至網絡重新分簇或死亡。

5.仿真試驗

為了驗證算法的性能，本文在NS2仿真平臺下實現了PSGM算法，并采用實際收集的溫度數據作為測試樣本。仿真場景的參數如表1所示。

表1 仿真場景的設置

節點的分布如圖1所示。為了驗證算法的性能，我們主要考察兩個指標：網絡生命周期和數據誤差率。

(1)網絡的生命周期：本文將網絡中第一個節點死亡的時間定義為網絡生命周期。當節點剩余能量低于0.005J時，我們認為該節點已不能工作。

(2)數據誤差率：數據誤差率是衡量預測算法性能的重要指標。本文的數據誤差率定義為所有休眠節點的誤差率的平均值。

網絡生命周期的測試結果如圖2所示。圖中橫坐標為休眠比率r。r=0時即對應所有節點都工作的情況，由圖2可以看出，休眠的節點數越多，網絡節約的能耗越多，網絡的生命周期也越長。

數據誤差率的測試結果如圖3所示。由圖3可以看出，數據的誤差隨著休眠節點的增多而有所提高，但即使節點休眠率r=0.7時，數據的誤差率也不超過2%，效果較好。

6.結束語

本文利用傳感數據的相關性，提出了一種基于預測的調度算法PSGM。仿真結果表明，該算法不僅有效地延長了網絡生命周期，而且數據的精度也較高，誤差控制在可接受的范圍內，因而可以在很多應用領域中推廣。

[1]Hsin C，Liu M.Network coverage using low duty-cycled sensors：random&coordinated sleep algorithms[C].Proceedings of the Third International Symposium on Information Processing in Sensor Networks(IPSN’04)，ACM，2004，433-442.

[2]Kumar S，Lai T H，Balogh J.On k-coverage in a mostly sleeping sensor networks[C].Proceeding of the 10th annual international conference on Mobile computing and networking，ACM，2004，144-158.

[3]Slijepcevic S，Potkonjak M.Power efficient organization of wireless sensor networks[C].Proceeding of the IEEE International Conference on Communications(ICC’01)，2001，472-476.

[4]Zhang H，Hou J.Maintaining sensing coverage and connectivity in large sensor networks[J].Ad Hoc&Sensor Wireless Networks，2005，1(1-2)：89-124.

[5]Gao Y，Wu K，Li F.Analysis on the redundancy of wireless sensor networks[C].Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications，2003，108-114.

[6]Xue-liang Bi，Tie Yan，Lei Chang，Chang-jiang Wang.Gray Correlation Analysis Method and Its Application in Drill Stem Failure in Oil and Gas Engineering[C].International Conference on Natural Computation，2008，502-505.