基于遺傳優(yōu)化的神經(jīng)網(wǎng)絡(luò)分簇路由算法*

隋春江，李 暉

（沈陽工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 沈陽 110870）

0 引 言

無線傳感器網(wǎng)絡(luò)（WSN）是由許多小型低功耗的傳感器節(jié)點(diǎn)部署在目標(biāo)監(jiān)測(cè)區(qū)域內(nèi)所組成的自組織網(wǎng)絡(luò)系統(tǒng)，是一種研究廣泛并融合多個(gè)學(xué)科領(lǐng)域的信息獲取和信息處理技術(shù)，主要對(duì)監(jiān)測(cè)目標(biāo)進(jìn)行數(shù)據(jù)感知、數(shù)據(jù)收集和數(shù)據(jù)處理[1]，并把數(shù)據(jù)處理的結(jié)果及時(shí)反饋到終端用戶，在健康醫(yī)療、智能家居、環(huán)境監(jiān)測(cè)和城市交通等領(lǐng)域有著廣泛的應(yīng)用[2-3]。尤其是在近幾年，隨著5G時(shí)代的來臨，無線傳感器網(wǎng)絡(luò)的應(yīng)用前景越來越好，其中WSN應(yīng)用于車聯(lián)網(wǎng)技術(shù)將會(huì)是未來研究的熱點(diǎn)。車聯(lián)網(wǎng)主要通過車與車間的互聯(lián)來計(jì)算不同車輛之間的最佳行駛路線并及時(shí)匯報(bào)道路狀況和道路周邊信息，有效緩解交通堵塞現(xiàn)象。然而，由于傳感器節(jié)點(diǎn)布置后電池不能進(jìn)行充電，從而導(dǎo)致傳感器節(jié)點(diǎn)的能量十分有限。因此，在無線傳感器網(wǎng)絡(luò)中，如何有效地節(jié)約能量，提高能量利用率，成為WSN的重點(diǎn)研究?jī)?nèi)容之一[4]。

目前，在無線傳感器網(wǎng)絡(luò)分簇路由算法中，基于層次化的分簇路由算法是減緩簇首能量消耗速率的一種有效方法。其中，LEACH算法是Heinzelman等人在2002年提出的一種經(jīng)典的無線傳感器網(wǎng)絡(luò)分簇路由算法[5]，主要思想是依據(jù)預(yù)先給定好的概率選擇簇首，使每個(gè)傳感器節(jié)點(diǎn)輪流充當(dāng)簇首，從而降低節(jié)點(diǎn)能量消耗，達(dá)到延長(zhǎng)無線傳感器網(wǎng)絡(luò)生存時(shí)間的目的。但是，由于隨機(jī)性選擇簇首，低能量的節(jié)點(diǎn)也可能被選為簇首，從而導(dǎo)致簇首節(jié)點(diǎn)的能量過早消失。有人針對(duì)以上存在的問題提出了一種集中式的分簇路由算法LEACH-C[6]，是在每個(gè)周期開始階段時(shí)把所有傳感器節(jié)點(diǎn)的位置信息和剩余能量信息傳輸?shù)交荆缓蠡居?jì)算所有節(jié)點(diǎn)的平均能量值，把其中能量高于平均能量的節(jié)點(diǎn)作為備選節(jié)點(diǎn)，最后利用模擬退火算法尋找節(jié)點(diǎn)位置的最優(yōu)解，以此減緩簇首節(jié)點(diǎn)能量損耗速率，延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。但是，每個(gè)周期傳感器節(jié)點(diǎn)都要向基站發(fā)送數(shù)據(jù)信息，造成了傳感器節(jié)點(diǎn)能量不必要的損耗。文獻(xiàn)[7]提出了一種能耗均衡的多跳路由算法，充分考慮節(jié)點(diǎn)的能量和位置因素，一定程度上減少了簇首能量消耗速率，提高了無線傳感器網(wǎng)絡(luò)的生命周期。還有專家學(xué)者將智能優(yōu)化算法引入到無線傳感器網(wǎng)絡(luò)聚類分簇算法中，如文獻(xiàn)[8]是一種結(jié)合節(jié)點(diǎn)的剩余能量、位置信息和節(jié)點(diǎn)密度等因素提出的人工蜂群分簇路由算法，得到的簇首部署更均衡，有效緩解了能量衰減速率，大大延長(zhǎng)了無線傳感器網(wǎng)絡(luò)的生存時(shí)間，但是自身存在尋優(yōu)能力差、無法快速收斂等問題。文獻(xiàn)[9]是在LEACH算法基礎(chǔ)上將單跳通信方式改為多跳通信方式，并提出了一種基于遺傳算法的優(yōu)化網(wǎng)絡(luò)拓?fù)渌惴āＮ墨I(xiàn)[10]是在智能算法基礎(chǔ)上引入BP神經(jīng)網(wǎng)絡(luò)的知識(shí)，提出一種在無線傳感器網(wǎng)絡(luò)中應(yīng)用粒子群優(yōu)化的BP神經(jīng)網(wǎng)絡(luò)分簇路由算法。該算法由于BP神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值是利用PSO算法進(jìn)行優(yōu)化得到的，因而可有效融合原始數(shù)據(jù)，有效減少數(shù)據(jù)傳輸，進(jìn)而延長(zhǎng)WSN的生存時(shí)間。

分析以上文獻(xiàn)，無線傳感器網(wǎng)絡(luò)分簇路由算法在選舉簇首時(shí)存在簇首選擇不合理的情況，無線傳感器網(wǎng)絡(luò)的生存時(shí)間有待進(jìn)一步提高。為此，本文提出一種基于遺傳優(yōu)化的BP神經(jīng)網(wǎng)絡(luò)分簇路由算法，將傳感器節(jié)點(diǎn)比作為神經(jīng)網(wǎng)絡(luò)中的神經(jīng)元，通過遺傳算法優(yōu)化的BP神經(jīng)網(wǎng)絡(luò)選擇簇首節(jié)點(diǎn)，解決簇首選擇不合理所造成網(wǎng)絡(luò)能量損耗過快的問題，從而實(shí)現(xiàn)增加無線傳感器網(wǎng)絡(luò)能量利用率、延長(zhǎng)無線傳感器網(wǎng)絡(luò)生存時(shí)間的目的。

1 算法概念

1.1 遺傳算法

1969年，Holland教授首次提出遺傳算法的概念。它是一種遵循“物競(jìng)天擇，適者生存”的自然選擇機(jī)制，通過在科學(xué)和生產(chǎn)實(shí)踐中模擬自然演化機(jī)制找出最符合問題需求的最優(yōu)解。它的原理為把種群個(gè)體看成需要解決問題的參數(shù)編碼，通過重復(fù)迭代進(jìn)行選擇、交叉、突變等遺傳操作產(chǎn)生下一代個(gè)體，適應(yīng)度函數(shù)值小的個(gè)體將會(huì)被淘汰，適應(yīng)度函數(shù)值大的個(gè)體具有更高的生存概率，得到的個(gè)體具有符合優(yōu)化搜索目標(biāo)最優(yōu)解的性質(zhì)，是一種全局優(yōu)化的自組織和自學(xué)習(xí)的概率型算法。GA查找最優(yōu)解的流程是從編碼構(gòu)成初始種群開始，然后對(duì)群體中的個(gè)體進(jìn)行適應(yīng)度函數(shù)值評(píng)估來完成選擇操作，新個(gè)體的產(chǎn)生是由GA在個(gè)體間進(jìn)行交叉和變異操作實(shí)現(xiàn)的，遵從優(yōu)勝劣汰的進(jìn)化過程，最終得到最優(yōu)解。主要步驟如下：

（1）選擇：從種群中選擇優(yōu)勝的種群個(gè)體，淘汰劣質(zhì)的種群個(gè)體。通過選擇操作把優(yōu)良的種群個(gè)體直接或間接地遺傳到下一代，是抉擇優(yōu)良個(gè)體的關(guān)鍵一步。

（2）交叉：交叉操作是遺傳算法起核心作用的操作。交叉操作是把兩個(gè)屬于父代個(gè)體的部分基因交叉重組而重新生成新個(gè)體的操作。

（3）變異：變異是對(duì)群體中的個(gè)體串上的某些基因值做改變，以使遺傳算法可維持種群的多樣性，防止出現(xiàn)未成熟收斂現(xiàn)象。

1.2 BP神經(jīng)網(wǎng)絡(luò)

通過搭建BP神經(jīng)網(wǎng)絡(luò)來完成對(duì)簇首節(jié)點(diǎn)和普通節(jié)點(diǎn)特征的分類任務(wù)。BP神經(jīng)網(wǎng)絡(luò)是一種按誤差傳播訓(xùn)練的多層前饋網(wǎng)絡(luò)。神經(jīng)網(wǎng)絡(luò)由兩部分組成：信息的正向傳輸和誤差的反向傳輸。神經(jīng)網(wǎng)絡(luò)中分布大量的神經(jīng)元節(jié)點(diǎn)，各神經(jīng)元之間通過權(quán)值和閾值連接形成三層神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，包括一個(gè)輸入層、一個(gè)隱含層和一個(gè)輸出層。BP神經(jīng)網(wǎng)絡(luò)能夠逼近任意非線性映射關(guān)系，具有很好的分類能力，能很好地完成基于無線傳感器節(jié)點(diǎn)特征的分類工作。圖1是三層BP神經(jīng)網(wǎng)絡(luò)的模型。

圖1 三層BP神經(jīng)網(wǎng)絡(luò)模型

圖1 中，神經(jīng)網(wǎng)絡(luò)的輸入層為X1到Xn，Wij、Wjk分別為輸入層和隱含層之間的神經(jīng)元權(quán)值與隱含層和輸出層之間的神經(jīng)元權(quán)值，Y1到Y(jié)m是經(jīng)過BP神經(jīng)網(wǎng)絡(luò)優(yōu)化所得的輸出結(jié)果。BP神經(jīng)網(wǎng)絡(luò)采用一種非線性映射并行管理機(jī)制，具有很強(qiáng)的高度自學(xué)能力和很好的泛化能力，能夠快速逼近任意非線性映射[11]。但是，BP神經(jīng)網(wǎng)絡(luò)也存在一定的不足，例如BP神經(jīng)網(wǎng)絡(luò)需要訓(xùn)練大量樣本數(shù)據(jù)才可以確定初始權(quán)值和閾值相關(guān)參數(shù)，導(dǎo)致BP神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)速度慢，易陷于局部極小值。

2 算法流程

在無線傳感器網(wǎng)絡(luò)中應(yīng)用GABP算法時(shí)，BP神經(jīng)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)需要根據(jù)無線傳感器網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)來確定。利用LEACH算法把無線傳感器網(wǎng)絡(luò)規(guī)劃為多個(gè)分簇，所得到的每個(gè)分簇分別對(duì)應(yīng)于每個(gè)BP神經(jīng)網(wǎng)絡(luò)模型結(jié)構(gòu)。BP神經(jīng)網(wǎng)絡(luò)輸入層的個(gè)數(shù)為分簇成員節(jié)點(diǎn)的個(gè)數(shù)，輸出層為簇首的個(gè)數(shù)。LEACH算法選擇簇首的過程是先對(duì)每個(gè)節(jié)點(diǎn)生成一個(gè)0到1的隨機(jī)數(shù)，如果該隨機(jī)數(shù)小于閾值，則該節(jié)點(diǎn)當(dāng)選為簇首[12]，而GABP算法是利用遺傳優(yōu)化的BP神經(jīng)網(wǎng)絡(luò)收斂速度快、泛化能力強(qiáng)等特點(diǎn)來選擇簇首。GABP算法的工作流程圖如圖2所示。

圖2 GABP算法的工作流程

主要包括以下三大步驟。

步驟1：首先對(duì)種群進(jìn)行初始化，通過無線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)確定BP神經(jīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，然后利用GA優(yōu)化的BP神經(jīng)網(wǎng)絡(luò)對(duì)權(quán)值和閾值進(jìn)行編碼，得到初始種群。

步驟2：確定最優(yōu)BP神經(jīng)網(wǎng)絡(luò)參數(shù)。遺傳算法依據(jù)BP神經(jīng)網(wǎng)絡(luò)的實(shí)際輸出和期望輸出的誤差更新種群中的個(gè)體。通過GA的復(fù)制、交叉和變異步驟產(chǎn)生新的種群，并判斷此時(shí)的情況是否需要重復(fù)迭代。如果達(dá)到條件，則把得到的最優(yōu)解傳遞到BP神經(jīng)網(wǎng)絡(luò)中進(jìn)行訓(xùn)練；否則，需要重復(fù)迭代，直到滿足最優(yōu)解為止。

步驟3：訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)。遺傳算法對(duì)BP神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值進(jìn)行優(yōu)化，不斷進(jìn)行網(wǎng)絡(luò)的訓(xùn)練，直到得到確定的參數(shù)為止，然后進(jìn)行無線傳感器網(wǎng)絡(luò)簇首選擇的過程。

GABP算法具體過程如下：

（1）根據(jù)無線傳感器網(wǎng)絡(luò)確定BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)模型，初始化BP神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值，然后根據(jù)式（1）確定隱含層的節(jié)點(diǎn)個(gè)數(shù)。

式中l(wèi)為隱含層節(jié)點(diǎn)個(gè)數(shù)，n為輸入節(jié)點(diǎn)數(shù)，m為輸出節(jié)點(diǎn)數(shù)，a為1到10之間的調(diào)節(jié)常數(shù)。通過多次試驗(yàn)來確定隱含層節(jié)點(diǎn)數(shù)。

（2）將步驟1初始化的權(quán)值和閾值傳遞給遺傳算法，計(jì)算適應(yīng)度函數(shù)值并把適應(yīng)度值大的個(gè)體進(jìn)行交叉、變異等操作，更新種群，判斷是否滿足條件，如滿足則執(zhí)行步驟3，否則，重復(fù)迭代直到滿足條件終止。其中，適應(yīng)度函數(shù)計(jì)算為：

式中d(i)為節(jié)點(diǎn)傳輸距離，En_res表示節(jié)點(diǎn)n剩余的能量，EN_res表示所有節(jié)點(diǎn)剩余能量，D(i)為鄰居節(jié)點(diǎn)密度，a、β、μ為權(quán)值系數(shù)，且α+β+μ=1。

（2）將步驟2產(chǎn)生的最優(yōu)解傳遞到BP神經(jīng)網(wǎng)絡(luò)中，BP神經(jīng)網(wǎng)絡(luò)中的誤差en是由預(yù)測(cè)輸出Yn和實(shí)際輸出On決定的，計(jì)算方法為：

式中，n為輸出層數(shù)量，且n=1,2,…,m。

（4）根據(jù)誤差en更新閾值和權(quán)值。

式中，wij表示為神經(jīng)網(wǎng)絡(luò)輸入層第i個(gè)神經(jīng)元與隱含層第j個(gè)神經(jīng)元之間的權(quán)值，Hi是神經(jīng)網(wǎng)絡(luò)輸入層數(shù)值。

式中，wjk表示為神經(jīng)網(wǎng)絡(luò)隱含層j個(gè)神經(jīng)元與輸出層第k個(gè)神經(jīng)元之間的權(quán)值，Hj為隱含層輸出。

（5）假如經(jīng)過BP神經(jīng)網(wǎng)絡(luò)處理得到的輸出誤差en達(dá)到事先設(shè)定好的理想值，則終止算法繼續(xù)運(yùn)行，否則返回步驟3繼續(xù)執(zhí)行。

3 仿真結(jié)果與分析

為了驗(yàn)證所提算法的效果，本文選擇Matlab2016a工作環(huán)境進(jìn)行仿真，且計(jì)算機(jī)所采用的硬件配置為英特爾酷睿i5處理器和4 GB運(yùn)行內(nèi)存。實(shí)驗(yàn)仿真是在100 m×100 m的區(qū)域隨機(jī)部署100個(gè)傳感器節(jié)點(diǎn)，主要仿真參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)設(shè)置

本文分別從節(jié)點(diǎn)存活數(shù)量、傳輸?shù)交镜臄?shù)據(jù)量、能量消耗三個(gè)方面進(jìn)行仿真分析對(duì)比，得到如圖3、圖4和圖5的仿真結(jié)果。

圖3 LEACH和GABP算法存活節(jié)點(diǎn)關(guān)系

從圖3可以看出，隨著時(shí)間的增加，GABP算法節(jié)點(diǎn)存活數(shù)量始終高于LEACH算法節(jié)點(diǎn)存活數(shù)量，說明GABP算法在簇首選擇方面效果要優(yōu)于LEACH算法。

圖4 LEACH和GABP數(shù)據(jù)傳輸班對(duì)比

圖4 是對(duì)基站接收簇首節(jié)點(diǎn)數(shù)據(jù)傳輸量進(jìn)行對(duì)比，可以看出本文所提算法相比于LEACH算法，基站接收數(shù)量值更大。這是由于GABP算法利用遺傳算法對(duì)BP神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值進(jìn)行優(yōu)化，可以找到全局最優(yōu)解，提高選舉簇首的有效性。

圖5 LEACH和GABP算法能量消耗對(duì)比

從圖5中可知，隨著迭代次數(shù)的增加，LEACH算法相比于GABP算法能量消耗速率更大，這是因?yàn)檫z傳算法優(yōu)化的BP神經(jīng)網(wǎng)絡(luò)算法能夠更好地融合傳感器節(jié)點(diǎn)的數(shù)據(jù)，減少數(shù)據(jù)傳輸量，從而提高網(wǎng)絡(luò)的生存時(shí)間。

4 結(jié) 語

本文在無線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)基礎(chǔ)上，提出一種基于遺傳算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的分簇路由算法。GABP算法利用GA優(yōu)化了BP神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值，有效提高了BP神經(jīng)網(wǎng)絡(luò)的收斂速度和泛化能力，使之簇首選擇更合理。與經(jīng)典的LEACH算法進(jìn)行綜合對(duì)比，GABP算法簇首選擇過程更優(yōu)，達(dá)到了延長(zhǎng)無線傳感器網(wǎng)絡(luò)生存時(shí)間的目的。