黃河流域生態(tài)環(huán)境監(jiān)測WSN路由優(yōu)化方法研究

王 軍，王超梁，趙雪專

（鄭州航空工業(yè)管理學(xué)院 大數(shù)據(jù)科學(xué)研究院，河南 鄭州450046）

2019年9月18日，習(xí)近平總書記在黃河流域生態(tài)保護(hù)和高質(zhì)量發(fā)展座談會上發(fā)表重要講話，將黃河流域生態(tài)保護(hù)和高質(zhì)量發(fā)展上升為重大國家戰(zhàn)略［1］。新一代信息技術(shù)，如大數(shù)據(jù)、人工智能、物聯(lián)網(wǎng)、云計算等，被廣泛用于促進(jìn)黃河流域生態(tài)保護(hù)和高質(zhì)量發(fā)展［2］。無線傳感器網(wǎng)絡(luò)作為最常用的物聯(lián)網(wǎng)數(shù)據(jù)采集設(shè)施，被廣泛應(yīng)用于智能環(huán)保等生態(tài)環(huán)境監(jiān)測和保護(hù)領(lǐng)域，適用于黃河流域生態(tài)環(huán)境監(jiān)測和保護(hù)，其發(fā)展的好壞直接影響新一代信息技術(shù)在黃河流域生態(tài)保護(hù)方面的應(yīng)用，而無線傳感器網(wǎng)絡(luò)（WSN）路由選擇算法的優(yōu)化，可有效降低WSN運(yùn)行成本，降低傳感器能耗，提高節(jié)點(diǎn)壽命，增強(qiáng)網(wǎng)絡(luò)連接的可靠性和抗毀性，提高無線傳感器網(wǎng)絡(luò)的運(yùn)行效率。Wankhade和Huang等提出的WSN路由算法提高了收斂速度，但不能有效地得到全局最優(yōu)解［3-4］。Costin等將演化算法應(yīng)用于WSN路由選擇優(yōu)化，全局搜索能力極佳，對于WSN路由優(yōu)化能力較強(qiáng)［5］。高霞等對演化算法進(jìn)行改進(jìn)，并將改進(jìn)的演化算法應(yīng)用于WSN路由選擇問題，可避免節(jié)點(diǎn)過早死亡，延長WSN網(wǎng)絡(luò)生存時間［6］。Costin等［5］、Zhao等［7］將其他算法和演化算法相結(jié)合用于WSN路由選擇，也可以有效地進(jìn)行WSN路由優(yōu)化。

筆者在傳統(tǒng)優(yōu)化算法的基礎(chǔ)上，對演化算法進(jìn)行了改進(jìn)，自動調(diào)整演化因子并縮短染色體長度，既能提高算法的收斂速度，又能保證解的全局最優(yōu)性。將改進(jìn)后的自適應(yīng)演化算法應(yīng)用到無線傳感器網(wǎng)絡(luò)路由選擇優(yōu)化，并通過試驗(yàn)與傳統(tǒng)演化算法、蟻群算法進(jìn)行了對比，從收斂時間、能耗、路由時延等方面驗(yàn)證了改進(jìn)算法的適應(yīng)性和優(yōu)越性。

1 黃河流域生態(tài)環(huán)境監(jiān)測WSN應(yīng)用框架及優(yōu)勢

黃河是中華民族的母親河，是人類文明的重要發(fā)源地，加強(qiáng)黃河流域生態(tài)環(huán)境保護(hù)對黃河流域經(jīng)濟(jì)高質(zhì)量發(fā)展至關(guān)重要。黃河流域覆蓋范圍廣、地勢差異大、氣候情況復(fù)雜，造成黃河流域生態(tài)環(huán)境數(shù)據(jù)采集難度大、成本高，傳統(tǒng)生態(tài)環(huán)境監(jiān)測主要依靠便攜式環(huán)境監(jiān)測設(shè)備定期采集數(shù)據(jù)，或者在固定位置布置傳感器來獲取數(shù)據(jù)，數(shù)據(jù)誤差大且時效性差。隨著新一代信息技術(shù)在生態(tài)環(huán)境保護(hù)領(lǐng)域的應(yīng)用，無線傳感器網(wǎng)絡(luò)被廣泛應(yīng)用于生態(tài)環(huán)境保護(hù)數(shù)據(jù)采集和實(shí)時監(jiān)測，極大地提高了黃河流域生態(tài)環(huán)境的監(jiān)測效率與監(jiān)測精度。新一代無線傳感器網(wǎng)絡(luò)WSN在黃河流域生態(tài)環(huán)境監(jiān)測中的應(yīng)用框架設(shè)計如圖1所示。黃河流域WSN應(yīng)用系統(tǒng)主要包括3個層面:無線傳感層、數(shù)據(jù)傳輸層以及遠(yuǎn)程控制層。其中無線傳感層實(shí)現(xiàn)黃河流域生態(tài)環(huán)境空天地一體化的數(shù)據(jù)采集，通過5G通信實(shí)時把數(shù)據(jù)傳輸?shù)竭h(yuǎn)程監(jiān)測端，實(shí)現(xiàn)遠(yuǎn)程控制端的實(shí)時監(jiān)測和控制。

圖1 黃河流域生態(tài)環(huán)境監(jiān)測WSN應(yīng)用框架

新一代無線傳感器網(wǎng)絡(luò)與傳統(tǒng)數(shù)據(jù)采集傳感器相比，有以下三方面的優(yōu)勢:

（1）傳感器節(jié)點(diǎn)布置簡單?？梢圆捎蔑w機(jī)播撒的方式大范圍布置傳感器網(wǎng)絡(luò)節(jié)點(diǎn)，特別適用于黃河流域復(fù)雜地貌的傳感器布置和數(shù)據(jù)采集。

（2）網(wǎng)絡(luò)自組。傳感器節(jié)點(diǎn)可快速和周圍節(jié)點(diǎn)建立無線連接，建立功能完善的傳感器網(wǎng)絡(luò)，且不受外界環(huán)境限制地進(jìn)行網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)的維護(hù)和管理，適用于黃河流域復(fù)雜氣象和環(huán)境變化條件下的數(shù)據(jù)傳輸。

（3）實(shí)時監(jiān)測。傳感器節(jié)點(diǎn)采集的數(shù)據(jù)可通過5G網(wǎng)絡(luò)實(shí)時傳輸?shù)竭h(yuǎn)程終端，實(shí)現(xiàn)黃河流域水質(zhì)、氣象、汛情等實(shí)時監(jiān)測。

基于無線傳感器網(wǎng)絡(luò)的優(yōu)勢，WSN可有效解決黃河流域生態(tài)環(huán)境監(jiān)測過程中的傳感器位置選擇困難、維護(hù)和組網(wǎng)成本高、數(shù)據(jù)采集時效性差等難題，更適用于有著復(fù)雜地貌的黃河流域的生態(tài)環(huán)境監(jiān)測。

2 WSN優(yōu)化算法模型

2.1 演化算法

演化算法是一種仿生學(xué)多目標(biāo)優(yōu)化算法，采用生物進(jìn)化的機(jī)制構(gòu)造問題，優(yōu)化系統(tǒng)的模型，從待解決問題的潛在解集的一個初始種群開始，種群由基因編碼的一定數(shù)目的個體組成，個體實(shí)際上是染色體帶有特征的實(shí)體［8］。算法開始時，需要對問題進(jìn)行映射編碼，通常以簡化后的二進(jìn)制編碼表示。初始種群通常隨機(jī)產(chǎn)生，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生越來越好的近似體，使種群像自然進(jìn)化一樣，后代種群比前代更加適應(yīng)環(huán)境，每一代的個體通過適應(yīng)度值來評價個體的優(yōu)劣，末代種群中適應(yīng)度值最大的個體經(jīng)過解碼，作為問題的最優(yōu)解。演化過程中基因交叉概率pc和變異概率pm的選取是影響算法行為和性能的關(guān)鍵所在，直接影響算法的收斂性。pc越大，新個體產(chǎn)生的速度越快，pc過大時演化模式被破壞的可能性也大，過小又會使搜索過程緩慢甚至停滯不前。變異概率pm過小就不易產(chǎn)生新的個體結(jié)構(gòu)，過大時演化算法就成了純粹的隨機(jī)搜索。針對不同的優(yōu)化問題，需要反復(fù)試驗(yàn)來確定pc和pm，而且很難找到適應(yīng)問題的最優(yōu)值，算法優(yōu)化過程如圖2所示。

圖2 演化算法優(yōu)化過程

2.2 自適應(yīng)演化算法

改進(jìn)的演化算法中，pc和pm能隨適應(yīng)度值自動改變，當(dāng)種群個體適應(yīng)度值趨于一致或局部最優(yōu)時，使pc和pm增大，而當(dāng)群體適應(yīng)度值比較分散時，使pc和pm減小。因此，自適應(yīng)的pc和pm能提供相對某個解的最佳的pc和pm，既保證了種群的多樣性，又保證了算法的收斂性［9］。在改進(jìn)的演化算法中，pc和pm按下式進(jìn)行自動調(diào)整:

式中:k1、k2、k3、k4為常數(shù)，具體值根據(jù)實(shí)際情況確定；fmax為群體中最大適應(yīng)度值；favg為每代群體的平均適應(yīng)度值；f′為要交叉的兩個個體中較大的適應(yīng)度值；f為變異個體的適應(yīng)度值。

演化算法常采用的演化編碼方式為二進(jìn)制編碼，搜索能力強(qiáng)，但該編碼方式存在串碼過長問題，對其收斂速度有較大影響。在WSN路由選擇問題優(yōu)化過程中，有很多約束變量需要處理，如果采用二進(jìn)制編碼，其出現(xiàn)的串碼長度可達(dá)幾十位甚至上百位，降低了搜索性能，筆者對編碼方式進(jìn)行改進(jìn)，采用十進(jìn)制的編碼方式，不需要編碼和解碼操作，有效提高了運(yùn)算速度和效率，具有收斂速度快且精度高的特點(diǎn)。采用十進(jìn)制編碼方式會影響演化操作的交叉和變異操作，但算法的演化實(shí)質(zhì)沒有變化，能適應(yīng)很多變化的環(huán)境變量，采用十進(jìn)制編碼策略，待選路由可能存在的狀態(tài)決定了編碼位數(shù)，只需將待選路由的編碼串聯(lián)起來就形成了一個染色體，然后按照演化算法進(jìn)行種群個體選擇、交叉和變異運(yùn)算，直到搜尋出最優(yōu)解［10-11］。

2.3 優(yōu)化步驟

（1）待優(yōu)化無線傳感器網(wǎng)絡(luò)原始參數(shù)輸入。主要包括網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、節(jié)點(diǎn)個數(shù)、節(jié)點(diǎn)密度、路由跳數(shù)、演化算法初始參數(shù)等。

（2）確定編碼方案，生成染色體并初始化種群。采用十進(jìn)制編碼方式，將待選路由的編碼串聯(lián)起來生成染色體，為了保證優(yōu)化群體中樣本的可行性和多樣性，根據(jù)WSN路由選擇滿足的約束條件，采用隨機(jī)生成的方式產(chǎn)生初始個體，初始種群規(guī)模大小取決于WSN網(wǎng)絡(luò)的規(guī)模。

（3）根據(jù)約束條件建立適應(yīng)度函數(shù)，計算適應(yīng)度值。WSN路由選擇優(yōu)化適應(yīng)度函數(shù)為

式中:i為當(dāng)前傳感器節(jié)點(diǎn)選擇；為第i+1傳感器節(jié)點(diǎn)的能量；p為種群演化變異概率；n x為x路由跳數(shù)；λ為平均節(jié)點(diǎn)能耗；α為種群演化遺傳概率；R i為相鄰傳感器節(jié)點(diǎn)密度。

WSN路徑優(yōu)化適應(yīng)度函數(shù)滿足約束條件的情況下，獲得全局最優(yōu)的適應(yīng)度值，并采用式（1）和式（2）對演化參數(shù)進(jìn)行優(yōu)化，分別計算各優(yōu)化方案的適應(yīng)度值，根據(jù)適應(yīng)度值高低排序，然后按照演化因子選擇若干個適應(yīng)度高的個體直接遺傳到下一代。

（4）演化操作。根據(jù)WSN拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)分布，對WSN路由選擇的編碼染色體按照確定的演化因子概率進(jìn)行遺傳、交叉和變異等操作，產(chǎn)生新一代演化種群。

（5）根據(jù)設(shè)定的演化適應(yīng)度值判斷標(biāo)準(zhǔn)或固定的演化代數(shù)，判斷算法的收斂性，本文固定演化代數(shù)為200代。如果滿足適應(yīng)度值的要求，則輸出優(yōu)化結(jié)果，如果不滿足要求則返回步驟（3），直到得到滿意的優(yōu)化結(jié)果。

本文算法流程見圖3。

圖3 改進(jìn)算法流程

3 仿真結(jié)果分析

為驗(yàn)證本文算法的適應(yīng)性和有效性，隨機(jī)選擇黃河流域100個節(jié)點(diǎn)的無線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，分別對比本文算法、傳統(tǒng)演化算法和蟻群算法在路由選擇優(yōu)化過程中的耗費(fèi)、算法收斂時間、節(jié)點(diǎn)能耗和路由時延。

3.1 路由選擇耗費(fèi)和算法收斂時間

由圖4和圖5可知:隨著傳感器節(jié)點(diǎn)數(shù)量增多，路由選擇耗費(fèi)和算法收斂時間逐漸升高，而且隨著節(jié)點(diǎn)規(guī)模增大，這種趨勢變得更加明顯。對比不同路由選擇優(yōu)化算法發(fā)現(xiàn)，本文改進(jìn)的演化算法性能明顯優(yōu)于傳統(tǒng)演化算法和蟻群算法。

3.2 節(jié)點(diǎn)能耗和路由時延

節(jié)點(diǎn)能耗和路由時延仿真采用100個節(jié)點(diǎn)的無線傳感網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，各節(jié)點(diǎn)初始能量均為1，得到不同算法和不同節(jié)點(diǎn)數(shù)量的路由選擇優(yōu)化能耗和時延，由圖6和圖7可知:隨著傳感器節(jié)點(diǎn)數(shù)量增多，各傳感器節(jié)點(diǎn)能耗和路由時延逐漸增加。對比不同路由選擇優(yōu)化算法發(fā)現(xiàn)，本文改進(jìn)的演化算法搜索尋優(yōu)性能優(yōu)于傳統(tǒng)演化算法和蟻群算法。

圖4 不同算法傳感器節(jié)點(diǎn)數(shù)量與路由選擇耗費(fèi)的關(guān)系

圖5 不同算法傳感器節(jié)點(diǎn)數(shù)量與算法收斂時間的關(guān)系

圖6 不同算法傳感器節(jié)點(diǎn)數(shù)量與節(jié)點(diǎn)能耗的關(guān)系

圖7 不同算法傳感器節(jié)點(diǎn)數(shù)量與路由時延的關(guān)系

4 結(jié) 論

黃河流域生態(tài)環(huán)境實(shí)時監(jiān)測和保護(hù)實(shí)施難度大、維護(hù)成本高，利用新一代信息技術(shù)可促進(jìn)黃河流域生態(tài)保護(hù)和高質(zhì)量發(fā)展，WSN被廣泛應(yīng)用于生態(tài)環(huán)境實(shí)時監(jiān)測和保護(hù)。本文提出把自適應(yīng)演化算法用于解決無線傳感網(wǎng)絡(luò)路由選擇優(yōu)化問題，相比于傳統(tǒng)演化算法、蟻群算法，在具有相同數(shù)量傳感器節(jié)點(diǎn)時，路由時延和節(jié)點(diǎn)能耗均具有明顯優(yōu)勢，而且算法收斂時間明顯縮短，適用于解決黃河流域大規(guī)模無線傳感網(wǎng)絡(luò)路由選擇優(yōu)化問題，具有一定的應(yīng)用價值。

（1）傳感器節(jié)點(diǎn)數(shù)量較少時（小于30個），本文算法和傳統(tǒng)優(yōu)化算法性能相當(dāng)；當(dāng)傳感器節(jié)點(diǎn)數(shù)量超過30時，本文算法具有更優(yōu)越的性能。

（2）無線傳感器網(wǎng)絡(luò)傳感器節(jié)點(diǎn)增加相同數(shù)量時，本文算法具有能耗、路由時延增幅最小，算法收斂速度最快的優(yōu)點(diǎn)，更適用于大規(guī)模WSN網(wǎng)絡(luò)結(jié)構(gòu)。