基于遺傳算法的無線傳感器網(wǎng)絡(luò)路由優(yōu)化

丁 凡,賀軍義,陳素霞,黃全振

（1.河南理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,河南 焦作 454003;2.河南工程學(xué)院 計算機(jī)學(xué)院,河南 鄭州 451191;3.河南工程學(xué)院 電氣信息工程學(xué)院,河南 鄭州 451191）

無線傳感器網(wǎng)絡(luò)（wireless sensor network,WSN）[1]是由大批量小型智能傳感器節(jié)點以自組織方式構(gòu)成的無線網(wǎng)絡(luò)。 相比于普通網(wǎng)絡(luò),WSN 以數(shù)據(jù)為中心,網(wǎng)絡(luò)設(shè)置靈活,安全性和可靠性強(qiáng)且成本較低,在軍事[2]、國防[3]、醫(yī)療[4]、農(nóng)業(yè)[5]等領(lǐng)域具有重要的應(yīng)用價值。 但在WSN 的實際應(yīng)用中,由于節(jié)點采用電池供電,工作環(huán)境通常比較復(fù)雜,導(dǎo)致電池不能被充電或更換,所以整個網(wǎng)絡(luò)的能量會受到影響。 因此,為保證網(wǎng)絡(luò)生命周期最大化,必須從源節(jié)點到匯聚節(jié)點的諸多路由路徑中找到一條節(jié)能高效的最優(yōu)路由。

針對WSN 路由優(yōu)化問題,國內(nèi)外已有大量學(xué)者將一些智能優(yōu)化算法應(yīng)用于該領(lǐng)域,遺傳算法就是其中的一種。 Rezaeipanah 等[6]以最大化網(wǎng)絡(luò)生命周期為目的,從數(shù)據(jù)轉(zhuǎn)發(fā)能耗和簇頭節(jié)點數(shù)目選取出發(fā),將遺傳算法應(yīng)用到WSN 簇間路由優(yōu)化中,但其在適應(yīng)度函數(shù)的構(gòu)建中未考慮節(jié)點的剩余能量,若剩余能量較低的節(jié)點被選為路由節(jié)點,在迭代次數(shù)過多時將縮短網(wǎng)絡(luò)生命周期。 陳立萬等[7]將傳統(tǒng)輪盤賭方法進(jìn)行改進(jìn),結(jié)合交叉變異操作,篩選出具有最高適應(yīng)度的個體作為最優(yōu)路由路徑,避免陷入局部最優(yōu),但算法中交叉變異操作均在值域范圍內(nèi)進(jìn)行,產(chǎn)生的新個體并不能保證對應(yīng)一條有效的路由路徑。 Wang 等[8]提出了一種基于遺傳算法的WSN 多路徑路由算法,利用節(jié)點間的距離計算適應(yīng)度函數(shù),在基站生成與所有節(jié)點共享的路由方案,但該方案在生成路由路徑時采用固定長度編碼,使得尋找到的最優(yōu)路徑存在一定約束條件,最優(yōu)路徑可能不是全局最優(yōu)。

由以上國內(nèi)外文獻(xiàn)可以看出,遺傳算法與WSN 的結(jié)合雖存在一定缺陷,但也彌補(bǔ)了網(wǎng)絡(luò)的一些問題。本研究在此基礎(chǔ)上進(jìn)行改進(jìn),依據(jù)遺傳算法模型和WSN 的特點,將改進(jìn)的遺傳算法運(yùn)用到WSN 路由優(yōu)化中,采用可變長度染色體對路由路徑編碼,提前確定網(wǎng)絡(luò)中各個節(jié)點的鄰域節(jié)點,防止交叉、變異操作產(chǎn)生不符合條件的路徑。 在形成路由路徑時,考慮路徑節(jié)點間距離、路徑總能耗、節(jié)點剩余能量等因素,將遺傳算法的快速全局尋優(yōu)能力融入路由優(yōu)化中,高效全面地搜尋目標(biāo)路由路徑。

1 WSN 路由模型

1.1 WSN 模型

在WSN 中,大量傳感器節(jié)點隨機(jī)分布在監(jiān)測區(qū)域內(nèi)周期性地感知周圍信息,感知到的信息被融合篩選后經(jīng)過多跳傳輸匯聚到匯聚節(jié)點（sink node） ,最終通過互聯(lián)網(wǎng)到達(dá)終端用戶。 假設(shè)WSN 模型如下:

1） 所有傳感器節(jié)點都具有唯一的身份標(biāo)識ID,編號為1,2,…,n。 網(wǎng)絡(luò)中只含有一個匯聚節(jié)點,編號為n。

2） 網(wǎng)絡(luò)中所有節(jié)點位置固定,各傳感器節(jié)點初始能量相同,所有節(jié)點均可感知周圍鄰域節(jié)點的信息。

3） 節(jié)點的通信半徑相同,當(dāng)兩個節(jié)點間的距離小于等于通信半徑,即兩節(jié)點互為鄰域節(jié)點時,可直接進(jìn)行通信。

4） 每個傳感器節(jié)點的結(jié)構(gòu)、功能相同,傳輸數(shù)據(jù)時節(jié)點可根據(jù)傳輸距離動態(tài)調(diào)整發(fā)射功率。

1.2 WSN 能耗

WSN 路由優(yōu)化關(guān)鍵因素在于解決傳感器節(jié)點能耗問題。 普通傳感器節(jié)點主要由電源、感應(yīng)單元、處理單元和無線通信單元4 個部分組成,如圖1 所示。 收發(fā)單元是無線通信單元的一部分,主要負(fù)責(zé)信息轉(zhuǎn)發(fā),是網(wǎng)絡(luò)中最大的能耗源。 收發(fā)單元存在空閑、接收、傳輸、休眠4種工作狀態(tài),空閑狀態(tài)和休眠狀態(tài)的能量消耗可以忽略不計,僅需要考慮節(jié)點在接收和傳輸狀態(tài)的能量消耗。

圖1 傳感器節(jié)點結(jié)構(gòu)Fig.1 Sensor node structure

從一個節(jié)點發(fā)送kbit 數(shù)據(jù)到另一個節(jié)點,傳感器節(jié)點所消耗的能量ET,以及接收kbit 數(shù)據(jù)傳感器節(jié)點所消耗的能量ER分別為

此外,節(jié)點需要對接收到的數(shù)據(jù)進(jìn)行融合處理,其能耗一般在數(shù)據(jù)傳輸時被消耗,故本研究不考慮該能耗。

1.3 WSN 路由優(yōu)化模型

為找到更好的方法來降低網(wǎng)絡(luò)整體的能量消耗,本研究將WSN 用帶權(quán)無向圖表示。 設(shè)圖G=（V,E） ,其中V為WSN 的節(jié)點集,V=（v1,v2,…,vn） ,E為各傳感器節(jié)點間的通信鏈路集,E=（e1,e2,…,em） ,d（vi,vj） 為節(jié)點vi到節(jié)點vj之間的距離,源節(jié)點到匯聚節(jié)點間可構(gòu)建出多條數(shù)據(jù)傳輸路徑χ,可表示為

式中:vi與vi+1為相鄰節(jié)點;v1為源節(jié)點;vn為匯聚節(jié)點。 路徑χ的總能量成本E（χ） , 即該路徑上所有節(jié)點消耗的總能量成本,可表示為

路徑χ的總長度D（χ） 為該路徑上各個相鄰節(jié)點間的距離總和,可表示為

WSN 路由優(yōu)化的最終目標(biāo)是尋找數(shù)據(jù)傳輸過程中從傳感器節(jié)點到接收器節(jié)點高效節(jié)能的路由路徑,若采用傳統(tǒng)的窮舉法從眾多傳輸路徑中選擇一條最優(yōu)路徑,則會消耗大量的時間和資源。 本研究針對遺傳算法能夠解決大規(guī)模復(fù)雜優(yōu)化問題的特性,將遺傳算法運(yùn)用到WSN 路由優(yōu)化中,能更快、更準(zhǔn)確地尋找最優(yōu)路徑。

2 基于遺傳算法的WSN 路由優(yōu)化

搭建完WSN 路由模型后,開始構(gòu)建初始路由表,即生成遺傳算法中的染色體,初始種群的構(gòu)建需要考慮傳感器節(jié)點間的通信距離。 在路由優(yōu)化過程中,種群中的染色體需要經(jīng)過多輪選擇、交叉和變異,使其朝著符合WSN 路由優(yōu)化的方向不斷延伸和進(jìn)化,從而找到最優(yōu)路由路徑。

2.1 編碼

應(yīng)用遺傳算法解決實際問題時必須考慮編碼問題,網(wǎng)絡(luò)路由問題具有特殊性,路由路徑有多條且長度可能不同。 因此,本研究采用可變長度編碼方法,對網(wǎng)絡(luò)中的每一個節(jié)點賦予唯一身份標(biāo)識ID,個體用從源節(jié)點到匯聚節(jié)點之間經(jīng)過節(jié)點的相應(yīng)ID 序列表示。 在數(shù)據(jù)轉(zhuǎn)發(fā)時,一個節(jié)點不能多次轉(zhuǎn)發(fā)同一個數(shù)據(jù)包,故同一個體內(nèi)不會出現(xiàn)重復(fù)節(jié)點。

2.2 適應(yīng)度函數(shù)

種群中不同個體對環(huán)境的適應(yīng)性不同,適應(yīng)度函數(shù)就是判斷個體適應(yīng)性強(qiáng)弱的函數(shù),適應(yīng)度越高的個體對環(huán)境的適應(yīng)性越強(qiáng),越有可能被保留到下一代。 在遺傳算法中,合適的適應(yīng)度函數(shù)可加快算法收斂,保證算法的可行性。 由此可知,路由的優(yōu)劣是用網(wǎng)絡(luò)生命周期、傳感器節(jié)點能耗、路由路徑長度及其可靠性等因素來評估的,故為保證算法可行,在設(shè)計適應(yīng)度函數(shù)時應(yīng)考慮上述因素。

綜上,適應(yīng)度函數(shù)可表示為

式中:α、β、γ為路由路徑長度與能量消耗間的權(quán)重系數(shù);I（p） 為保證網(wǎng)絡(luò)能量均衡消耗的參數(shù),可防止能量較低的節(jié)點被選為路由節(jié)點,導(dǎo)致節(jié)點過早死亡而縮短網(wǎng)絡(luò)生命周期。I（p） 計算公式如下:

由于路徑短、能量消耗相對較少、節(jié)點負(fù)載均衡的路由路徑為目標(biāo)路徑,故本研究要解決的最優(yōu)化問題可轉(zhuǎn)化為求解目標(biāo)函數(shù)的最小值,需要對目標(biāo)函數(shù)進(jìn)行一定處理,將其映射為求最大值且函數(shù)值非負(fù)的形式,方法如下:

式中:fmax為當(dāng)代種群個體中最大適應(yīng)度;ξ為一個較小常數(shù),可使種群中最差個體仍有繼續(xù)繁殖的機(jī)會,增強(qiáng)種群多樣性。 映射后的適應(yīng)度函數(shù)應(yīng)加大選擇壓力,增強(qiáng)擇優(yōu)功能。

2.3 種群選擇

為避免算法過早陷入局部收斂,本研究在種群選擇時采用最優(yōu)個體保留策略[9]與輪盤賭算法[10]相結(jié)合的方法。 設(shè)種群大小為M,每輪選取N個適應(yīng)度最高的最優(yōu)個體直接保留到下一代種群中,剩余M-N個種群個體采用輪盤賭算法選擇。 在輪盤賭算法中,個體被選中的概率與適應(yīng)度成正比,即個體i被選中的概率如下:

2.4 交叉操作

交叉操作模擬自然界生物繁殖的特性,運(yùn)用個體間的基因重組產(chǎn)生新的個體。 不同的交叉操作適用于不同的優(yōu)化場景,常見的交叉操作有單點交叉[11]、多點交叉[12]、均勻交叉[13]及順序交叉[14-15]等,本研究采取的方式為單點交叉。 傳統(tǒng)單點交叉操作未考慮交叉位置前的節(jié)點與選擇節(jié)點間是否存在鏈路,導(dǎo)致可能產(chǎn)生不符合條件的路由路徑而影響網(wǎng)絡(luò)運(yùn)行,本研究對此進(jìn)行了改進(jìn),使其能夠有效地找到合適的路由路徑。 交叉操作的具體方法如下:

1） 按照一定規(guī)則從種群中選取個體p1和p2,判斷兩個個體之間是否存在公共節(jié)點,若存在,則將公共節(jié)點后的基因片段進(jìn)行交換重組。

2） 若不存在公共節(jié)點則隨機(jī)選取交叉位置n1,判斷p1中n1處的節(jié)點與p2中n1+ 1 處的節(jié)點是否能夠組成鏈路,p2中n1處的節(jié)點與p1中n1+ 1 處的節(jié)點是否能夠組成鏈路。

3） 若可以,則按照交叉概率判斷是否交換兩個染色體n1位置后的基因片段,否則不進(jìn)行交叉。

在具體執(zhí)行過程中,交叉概率過大可能破壞最優(yōu)個體,過小可能導(dǎo)致算法收斂速度緩慢,故交叉概率應(yīng)慎重設(shè)置。 同時,對于交叉后的個體應(yīng)考慮是否存在重復(fù)基因,若存在,則將兩個重復(fù)基因間的基因片段全部刪除。

2.5 變異操作

變異操作可保持種群的多樣性,防止遺傳算法陷入早熟和局部收斂。 在進(jìn)行變異操作時通常選取基因順序交換變異和基因編號變異這兩種方式,本研究采用基因編號變異。 具體操作過程如下:

1） 按照一定的規(guī)則從種群中選取個體p3,依據(jù)p3的編碼長度隨機(jī)選擇除源節(jié)點與匯聚節(jié)點所在位置外的變異位置n2。

2） 觀察n2前后位置節(jié)點的鄰域,若兩個鄰域內(nèi)存在重復(fù)節(jié)點,則依據(jù)變異概率決定是否將該節(jié)點作為變異節(jié)點來替換n2位置的節(jié)點,否則不進(jìn)行變異。

變異操作后的個體同樣可能存在重復(fù)基因,若存在,則依據(jù)上一小節(jié)的操作,將兩個重復(fù)基因間的基因片段全部刪除。

3 仿真實驗與分析

3.1 仿真環(huán)境及參數(shù)設(shè)置

為驗證本研究提出的算法對WSN 路由優(yōu)化的效果,利用MATLAB R2016b 仿真軟件搭建相應(yīng)的仿真平臺進(jìn)行實驗,仿真所用的具體參數(shù)如表1 所示。

表1 實驗仿真參數(shù)Tab.1 Experimental simulation parameters

仿真環(huán)境中傳感器節(jié)點將感知收集到的數(shù)據(jù)融合為大小相同的數(shù)據(jù)包,起始節(jié)點與匯聚節(jié)點的位置已經(jīng)指定。 設(shè)定種群數(shù)量為20,主要探究從起始節(jié)點到匯聚節(jié)點多條路由路徑中的最優(yōu)路徑。

3.2 適應(yīng)度變化

本研究提出將遺傳算法運(yùn)用到WSN 路由優(yōu)化中,經(jīng)過多次仿真實驗,得到前50 代種群平均適應(yīng)度及最優(yōu)個體的進(jìn)化情況,如圖2 所示。 由于遺傳算法中存在交叉、變異等操作,每次得到的結(jié)果具有一定的隨機(jī)性,故不同個體得到的適應(yīng)度具有一定差異,但根據(jù)運(yùn)行結(jié)果可以看出,種群內(nèi)大部分個體的適應(yīng)度接近最優(yōu)結(jié)果。

圖2 適應(yīng)度變化Fig.2 Change of fitness

由圖2 可以看出,前6 次迭代內(nèi)最優(yōu)個體與種群均值的適應(yīng)度均處于上升趨勢且兩者間的差值較大,此時種群內(nèi)的個體多為隨機(jī)生成個體;之后隨著種群不斷進(jìn)化,適應(yīng)度也不斷下降,迭代到25 次左右變化趨勢逐漸放緩,兩條曲線的差值也逐漸減少;迭代45 次左右兩條曲線基本收斂,表示已經(jīng)形成最優(yōu)路徑。

3.3 網(wǎng)絡(luò)最優(yōu)路徑

隨機(jī)運(yùn)行本研究提出的算法,得到的網(wǎng)絡(luò)最優(yōu)路徑如圖3 所示。 從圖3 中可以看出,算法在指定起始節(jié)點處找到最優(yōu)路徑,該路徑同時考慮節(jié)點間的距離及節(jié)點剩余能量,證明了該算法在WSN 路由優(yōu)化中的應(yīng)用具有高效性。

圖3 仿真實驗得到的最優(yōu)路徑Fig.3 Optimal path obtained from simulation experiment

3.4 網(wǎng)絡(luò)能量消耗

Flooding 算法與本算法在數(shù)據(jù)傳輸過程中的能耗對比見圖4。 從圖4 可以看出,300 s 內(nèi),相較本算法,Flooding 算法的能量消耗上升斜率更陡,大約消耗了143 J 能量,而本算法大約消耗了46 J 能量,相比Flooding 算法下降了約68%。

圖4 總消耗能量對比Fig.4 Comparison of total energy consumption

3.5 網(wǎng)絡(luò)生命周期

本算法將網(wǎng)絡(luò)生命周期定義為從開始運(yùn)行到節(jié)點全部死亡經(jīng)過的輪數(shù),Flooding 算法與本算法在數(shù)據(jù)傳輸時的死亡節(jié)點數(shù)如圖5 所示。 圖5 中,Flooding算法在第90 輪就開始出現(xiàn)死亡節(jié)點,在第505 輪時節(jié)點全部死亡,而本算法在第503 輪才開始出現(xiàn)死亡節(jié)點,在第829 輪節(jié)點全部死亡。 就整個生命周期而言,本算法相比Flooding 算法提高了約64%,有效延長了網(wǎng)絡(luò)生命周期。

圖5 死亡節(jié)點數(shù)對比Fig.5 Comparison of the number of dead nodes

4 結(jié)語

路由優(yōu)化是保證WSN 壽命最大化的可靠途徑。本研究在傳統(tǒng)遺傳算法的基礎(chǔ)上,綜合考慮多種約束條件,提出了一種基于遺傳算法的WSN 路由優(yōu)化算法。 該算法不僅考慮整個網(wǎng)絡(luò)能量的均衡消耗,還根據(jù)路徑規(guī)劃及WSN 特點,設(shè)計了相應(yīng)的遺傳操作算子,保證經(jīng)過多輪選擇、交叉、變異后產(chǎn)生全局最優(yōu)個體。 仿真結(jié)果表明,與Flooding 算法相比,本算法能有效減少能量損耗,延長網(wǎng)絡(luò)生命周期。