一種基于灰色模型的預(yù)測(cè)調(diào)度算法

陳鑫杰

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

1.引言

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

目前科研人員已經(jīng)提出了許多調(diào)度算法。在節(jié)點(diǎn)分布滿足泊松靜態(tài)點(diǎn)過程條件下，Hisn[1]等把節(jié)點(diǎn)調(diào)度分為兩種：節(jié)點(diǎn)隨機(jī)調(diào)度和節(jié)點(diǎn)協(xié)作調(diào)度。節(jié)點(diǎn)隨機(jī)調(diào)度算法[2-3]僅執(zhí)行一次，通過隨機(jī)分組形式將每個(gè)傳感器節(jié)點(diǎn)劃分到某一組或某幾組，算法結(jié)束之后，依次調(diào)度每一組的節(jié)點(diǎn)工作。節(jié)點(diǎn)協(xié)作調(diào)度算法需要節(jié)點(diǎn)與周圍節(jié)點(diǎn)進(jìn)行通信，且傳感器節(jié)點(diǎn)在每一輪的開始執(zhí)行一次算法，按照某種競(jìng)爭(zhēng)機(jī)制從所有節(jié)點(diǎn)中選擇若干個(gè)節(jié)點(diǎn)作為活動(dòng)節(jié)點(diǎn)。節(jié)點(diǎn)協(xié)作調(diào)度算法又可以進(jìn)一步分為基于位置信息的節(jié)點(diǎn)調(diào)度[4]和無(wú)位置信息的節(jié)點(diǎn)調(diào)度[5]?？梢钥闯觯?jié)點(diǎn)調(diào)度問題與覆蓋性能、路由規(guī)劃和網(wǎng)絡(luò)連通性等問題存在一定關(guān)聯(lián)。

與上述研究的思路不同，本文利用節(jié)點(diǎn)采集數(shù)據(jù)在時(shí)間上的相關(guān)性，提出了一種基于灰色模型[6]的預(yù)測(cè)調(diào)度算法(PSGM)。PSGM盡量讓能量較低的節(jié)點(diǎn)休眠，并采用灰色模型來(lái)預(yù)測(cè)節(jié)點(diǎn)休眠時(shí)丟失的數(shù)據(jù)。仿真結(jié)果表明，算法能夠有效地延長(zhǎng)網(wǎng)絡(luò)的生命周期，達(dá)到了設(shè)計(jì)的目標(biāo)。

2.網(wǎng)絡(luò)模型

PSGM算法對(duì)WSNs做如下假設(shè)：

(1)節(jié)點(diǎn)：所有的節(jié)點(diǎn)同質(zhì)，初始能量相同，并具有數(shù)據(jù)緩存能力。sink節(jié)點(diǎn)除了具有較高的能量外，其它設(shè)置與一般節(jié)點(diǎn)相同。

(2)分布：節(jié)點(diǎn)被隨機(jī)布置在一個(gè)矩形區(qū)域內(nèi)，并假定每個(gè)節(jié)點(diǎn)可以獲取自己的能量信息。

(3)網(wǎng)絡(luò)結(jié)構(gòu)：網(wǎng)絡(luò)為一個(gè)兩層的簇結(jié)構(gòu)。節(jié)點(diǎn)可以按多種方法分簇，如位置相關(guān)、應(yīng)用設(shè)定、隨機(jī)產(chǎn)生等，簇中成員產(chǎn)生數(shù)據(jù)后向簇頭節(jié)點(diǎn)發(fā)送，簇頭節(jié)點(diǎn)匯總所有簇成員的數(shù)據(jù)后，合并成一個(gè)數(shù)據(jù)包發(fā)送給sink節(jié)點(diǎn)。

3.灰色模型

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

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

得到新的序列后，運(yùn)用數(shù)學(xué)中的動(dòng)態(tài)線性模型對(duì)生成的數(shù)據(jù)進(jìn)行擬合和逼近，得到微分方程式如(2)所示。

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

使用式(3)即可進(jìn)行數(shù)據(jù)的擬合與預(yù)測(cè)。

4.基于灰色模型的預(yù)測(cè)調(diào)度算法

PSGM是基于分層拓?fù)涞木W(wǎng)絡(luò)結(jié)構(gòu)。其主要思路是，簇成員向簇首節(jié)點(diǎn)發(fā)送數(shù)據(jù)時(shí)，順帶發(fā)送自己的剩余能量。簇首節(jié)點(diǎn)接收到數(shù)據(jù)后，將其保存。并根據(jù)節(jié)點(diǎn)的能量狀況，選取簇中能量較低的節(jié)點(diǎn)，通知其休眠。在下一輪提交數(shù)據(jù)時(shí)，簇首節(jié)點(diǎn)根據(jù)休眠節(jié)點(diǎn)前面提交的數(shù)據(jù)預(yù)測(cè)出其應(yīng)提交的數(shù)據(jù)。

4.1 數(shù)據(jù)的預(yù)測(cè)

PSGM算法的核心步驟就是簇首節(jié)點(diǎn)對(duì)休眠節(jié)點(diǎn)進(jìn)行的數(shù)據(jù)預(yù)測(cè)。為了實(shí)現(xiàn)這個(gè)功能，PSGM算法采用了GM(1，1)模型。算法的主要步驟是：

首先，簇首節(jié)點(diǎn)為每一個(gè)簇成員節(jié)點(diǎn)k建立一個(gè)數(shù)組data，用于保存該節(jié)點(diǎn)k的前n個(gè)數(shù)據(jù)。這n個(gè)數(shù)據(jù)可以是節(jié)點(diǎn)k提交過來(lái)的，也可以是節(jié)點(diǎn)k休眠時(shí)由簇首節(jié)點(diǎn)計(jì)算出來(lái)的。

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

n的選擇跟具體的應(yīng)用相關(guān)，數(shù)據(jù)波動(dòng)較大的環(huán)境n值應(yīng)相應(yīng)增大，否則可以減小。在我們的試驗(yàn)中，n取值15。

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

4.2 算法流程

PSGM算法的具體步驟如下：

(1)初始化：網(wǎng)絡(luò)進(jìn)行初始化分簇工作。分簇算法可以采用已有的算法，也可以人工設(shè)定。

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

(3)調(diào)度休眠：從第n+1輪開始，簇首節(jié)點(diǎn)根據(jù)簇內(nèi)成員的能量情況按照一定的比率r來(lái)選擇節(jié)點(diǎn)，通知其休眠。選擇節(jié)點(diǎn)時(shí)，忽略上輪已休眠過的節(jié)點(diǎn)。

(4)預(yù)測(cè)數(shù)據(jù)：預(yù)測(cè)節(jié)點(diǎn)針對(duì)休眠節(jié)點(diǎn)進(jìn)行數(shù)據(jù)預(yù)測(cè)，并更新其data數(shù)組。然后簇首節(jié)點(diǎn)將預(yù)測(cè)數(shù)據(jù)與收集的真實(shí)數(shù)據(jù)一起聚合后向上提交。

(5)喚醒節(jié)點(diǎn)：休眠節(jié)點(diǎn)休息一輪后，進(jìn)入工作狀態(tài)。

(6)循環(huán)(3)～(5)，直至網(wǎng)絡(luò)重新分簇或死亡。

5.仿真試驗(yàn)

為了驗(yàn)證算法的性能，本文在NS2仿真平臺(tái)下實(shí)現(xiàn)了PSGM算法，并采用實(shí)際收集的溫度數(shù)據(jù)作為測(cè)試樣本。仿真場(chǎng)景的參數(shù)如表1所示。

表1 仿真場(chǎng)景的設(shè)置

節(jié)點(diǎn)的分布如圖1所示。為了驗(yàn)證算法的性能，我們主要考察兩個(gè)指標(biāo)：網(wǎng)絡(luò)生命周期和數(shù)據(jù)誤差率。

(1)網(wǎng)絡(luò)的生命周期：本文將網(wǎng)絡(luò)中第一個(gè)節(jié)點(diǎn)死亡的時(shí)間定義為網(wǎng)絡(luò)生命周期。當(dāng)節(jié)點(diǎn)剩余能量低于0.005J時(shí)，我們認(rèn)為該節(jié)點(diǎn)已不能工作。

(2)數(shù)據(jù)誤差率：數(shù)據(jù)誤差率是衡量預(yù)測(cè)算法性能的重要指標(biāo)。本文的數(shù)據(jù)誤差率定義為所有休眠節(jié)點(diǎn)的誤差率的平均值。

網(wǎng)絡(luò)生命周期的測(cè)試結(jié)果如圖2所示。圖中橫坐標(biāo)為休眠比率r。r=0時(shí)即對(duì)應(yīng)所有節(jié)點(diǎn)都工作的情況，由圖2可以看出，休眠的節(jié)點(diǎn)數(shù)越多，網(wǎng)絡(luò)節(jié)約的能耗越多，網(wǎng)絡(luò)的生命周期也越長(zhǎng)。

數(shù)據(jù)誤差率的測(cè)試結(jié)果如圖3所示。由圖3可以看出，數(shù)據(jù)的誤差隨著休眠節(jié)點(diǎn)的增多而有所提高，但即使節(jié)點(diǎn)休眠率r=0.7時(shí)，數(shù)據(jù)的誤差率也不超過2%，效果較好。

6.結(jié)束語(yǔ)

本文利用傳感數(shù)據(jù)的相關(guān)性，提出了一種基于預(yù)測(cè)的調(diào)度算法PSGM。仿真結(jié)果表明，該算法不僅有效地延長(zhǎng)了網(wǎng)絡(luò)生命周期，而且數(shù)據(jù)的精度也較高，誤差控制在可接受的范圍內(nèi)，因而可以在很多應(yīng)用領(lǐng)域中推廣。

[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.