一種基于多目標進化的無線傳感器網(wǎng)絡(luò)的信號重構(gòu)算法

張朝霞 蔣 勇 李麗霞 羅智勇

（湖南化工職業(yè)技術(shù)學(xué)院，湖南 株洲 412004）

無線傳感器網(wǎng)絡(luò)是一種多跳、自組織的無線通信網(wǎng)絡(luò)，部署了大量能量受限的傳感器節(jié)點[1]。具有快速展開和抗毀性強等特點，可廣泛應(yīng)用于軍事偵察、醫(yī)療監(jiān)護、工業(yè)生產(chǎn)、環(huán)境監(jiān)測、農(nóng)業(yè)養(yǎng)殖等領(lǐng)域。

WSN 一般采用分簇路由方式，具有拓撲管理方便、數(shù)據(jù)融合簡單和節(jié)省能量等優(yōu)點。如圖1 所示，在分簇路由算法中，通常將網(wǎng)絡(luò)劃分為若干個簇，即為具有某種關(guān)聯(lián)的網(wǎng)絡(luò)節(jié)點集合。每個簇由一個簇頭和多個簇內(nèi)成員組成，由簇頭與基站通信。

圖1 無線傳感器網(wǎng)絡(luò)的拓撲結(jié)構(gòu)

LEACH 協(xié)議是Heinzelman W[2]等最早提出的用于WSN 中分簇路由協(xié)議，它采用等概率循環(huán)隨機選擇簇頭，通過簇成員節(jié)點根據(jù)簇頭廣播信號強度加入分簇的方式形成分簇。Handy MJ[3]引入了能量因素，對LEACH 算法中節(jié)點當選為簇頭的閾值計算進行改進，提出了DCHS 算法來延長了網(wǎng)絡(luò)生存時間。Heinzelman W.[4]針對LEACH 協(xié)議每輪產(chǎn)生簇頭數(shù)目和位置不確定的缺陷，提出LEACH-C(LEACH-centralized)和LEACH-F(LEACH-fixed)。每個節(jié)點把自身信息報告給基站，由基站根據(jù)收到的信息來選擇簇頭，并將分簇結(jié)構(gòu)和簇頭集合廣播出去。Younis O.等人提出HEED (Hybrid Energy-efficient Distributed Clustering)[5]，簇頭的產(chǎn)生主要依賴主、次兩個參數(shù)，分別依賴于剩余能量和簇內(nèi)通信代價。能產(chǎn)生分布均勻的簇頭和更加合理的網(wǎng)絡(luò)拓撲[6]。LEACH 路由算法的分簇思想對后續(xù)提出的分簇路由算法產(chǎn)生了較大的促進作用。

本文提出基于多目標進化的無線傳感器網(wǎng)絡(luò)分簇信號重構(gòu)算法，基于LEACH 算法，主要對無線傳感器網(wǎng)絡(luò)中的簇頭節(jié)點個數(shù)、節(jié)點剩余能量、分簇空間分布、和總能耗四個方面進行分析評價。包括：首先建立基于多目標進化的系統(tǒng)模型；再進行種群初始化，選擇交叉和動態(tài)變異等操作，得出最優(yōu)的分簇重構(gòu)解決方案，并通過實驗仿真進行驗證。

1 系統(tǒng)模型

傳感器節(jié)點通常能量受限。為了延長網(wǎng)絡(luò)生存時間，簇頭一定要周期性更新。而分簇的結(jié)構(gòu)、大小以及數(shù)量取決于簇頭的選擇方法、數(shù)量和位置。因此，簇頭的選擇方法要依據(jù)以下準則：（1）簇內(nèi)成員到簇頭的通信代價；（2）簇頭的空間分布；（3）節(jié)點剩余能量；（4）能耗均衡?；谝陨蠝蕜t進行建模。

1.1分簇緊密度

針對上述準則（2）（3）定義分簇緊密度fT如下：

其中，K為分簇個數(shù)，Ci和Cj分別為第i 和第j 個簇。為第i 個簇內(nèi)成員n 到簇頭的距離。為簇頭i 到簇頭j的距離。由分簇緊密度表達式可知，當簇頭分布越分散，同時簇內(nèi)成員到簇頭之間的距離越小時，fT越小。

1.2 能耗模型

針對上述準則（4）之節(jié)能的目標，建立能耗模型并給出總能耗計算方法。如圖2 所示，當傳輸距離為d 時，在一定信噪比（Signal-to-Noise Ratio，SNR）條件下傳輸L-bit 數(shù)據(jù)的能耗為：

圖2 能耗模型

根據(jù)發(fā)送端和接收端之間的距離遠近，我們選擇不同的傳輸模型(即采用Efs或是Emp)。Eelec發(fā)送/接收端傳輸每bit 數(shù)據(jù)的電路能耗。接收端每接收1bit 數(shù)據(jù)的能耗為ERX=Eelec。

為簡化模型，做如下假設(shè)：

（1）n 個傳感器節(jié)點隨機分布在M×M的方形區(qū)域內(nèi)，數(shù)據(jù)匯聚節(jié)點（Sink）位于監(jiān)測區(qū)域的中央。

（2）考慮到網(wǎng)絡(luò)開銷的能耗遠小于傳輸數(shù)據(jù)的能耗，本文僅考慮了數(shù)據(jù)傳輸?shù)哪芎摹?/p>

（3）通信過程中不存在重連和數(shù)據(jù)傳輸錯誤，且節(jié)點傳輸?shù)臄?shù)據(jù)存在冗余。

基于上述假設(shè)，我們可以得出一個時間輪中簇頭節(jié)點的能耗如下：

其中，K 為分簇個數(shù)，EDA為數(shù)據(jù)融合每bit的能耗，dCHN-SINK為簇頭節(jié)點到sink 節(jié)點的距離，R(i)為數(shù)據(jù)融合率，第i 個簇內(nèi)數(shù)據(jù)融合率可表述為：

式（4）中，Cnodes(i)簇內(nèi)節(jié)點個數(shù)，b 為一個僅依賴于Cnodes(i)的常數(shù)。R(i)的期望值為：

一個時間輪中普通節(jié)點的能耗如下：

其中dCN-CHN為普通節(jié)點到簇頭節(jié)點之間的距離，其期望值[8]為：

其中ρ(x,y)為節(jié)點分布函數(shù)，本文假設(shè)節(jié)點服從均勻分布，因此，ρ(x,y)=1/(M2/K)。

聯(lián)合上述（3）-（7）式可以得出一個時間輪中總能耗如下：

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

衡量一個進化算法成功與否的重要標準是選取一個合適的適應(yīng)度函數(shù)，它影響著進化的方向。因此，根據(jù)上述簇頭的選擇方法必須遵循的4 條準則設(shè)計適應(yīng)度函數(shù)如下：

其中，ECHN_average為簇頭節(jié)點平均剩余能量，α 為權(quán)重因子，其大小可由用戶根據(jù)工程實踐中的實際需要進行調(diào)整。

1.4 多目標進化模型

進化算法是一種通過模擬生物自然進化過程的隨機搜索算法，利用它能有效的解決該問題。本文針對WSN的自身特點，建立基于多目標進化的WSN 分簇信號重構(gòu)分析模型。主要步驟包括初始種群的獲取，基因編碼，適應(yīng)度計算，根據(jù)條件進行選擇，交叉和變異，得出最優(yōu)解決方案。

1.4.1 獲取初始種群和基因編碼

首先，監(jiān)測網(wǎng)絡(luò)區(qū)域內(nèi)所有節(jié)點完成定位和統(tǒng)一后，發(fā)送廣播消息，消息內(nèi)容包括節(jié)點ID、位置信息和一個長度為L（L 為正整數(shù)）的二進制隨機序列。當Sink 收到所有節(jié)點的廣播消息后，則逐位讀取隨機序列中的值，并構(gòu)造成一個矩陣H0，，元素等于0 或1）是ID 為i的節(jié)點所發(fā)送的隨機序列的第j 位；僅當hij為“1”時表示節(jié)點i 被選成簇頭，否則不是簇頭。列向量表示為一種可能的分簇結(jié)構(gòu)，即，一個只含一條染色體的個體，L 個個體構(gòu)成初始種群，用矩陣H0表示。

1.4.2 選擇交叉與變異

Sink 節(jié)點對每個個體進行評估，分別計算出各個個體的評估值，并保存評估值的最小值Fmin。根據(jù)每一個個體的評估值來對初始種群進行二進制錦標賽選擇，交叉和變異，構(gòu)成新的矩陣H1，

具體步驟如下：

首先，對矩陣H0中的每個元素以概率P 進行運算。

最后，用H1替換H0重復(fù)執(zhí)行上述步驟，一直到Fmin達到一個穩(wěn)定值，即達到滿足終止條件時，F(xiàn)min對應(yīng)的個體即為最優(yōu)的分簇結(jié)構(gòu)。

2 仿真結(jié)果分析

仿真過程中，假設(shè)100 個節(jié)點隨機分布在100mm×100mm的監(jiān)測區(qū)域內(nèi)，Sink 節(jié)點位于監(jiān)測區(qū)域的中央，節(jié)點采集的數(shù)據(jù)大小為1bit，10%的節(jié)點的初始能量為0.8J，其余節(jié)點的初始剩余能量為0.4J。表1 給出了部分仿真參數(shù)。

表1 仿真參數(shù)

仿真對比更具說服性，在對LEACH 協(xié)議進行仿真前，先用本文信號重構(gòu)算法給出最優(yōu)分簇的個數(shù)，確定節(jié)點選為簇頭的概率，再進行對比分析。如圖3 所示，用本文提出的多目標分簇信號重構(gòu)算法在穩(wěn)定后，分簇個數(shù)能產(chǎn)生和LEACH 協(xié)議數(shù)目相近的分簇。簇頭的平均剩余能量一定程度上反映了網(wǎng)絡(luò)的存活時間。通過實驗仿真，如圖4 所示，本文提出的分簇信號重構(gòu)方法選擇的簇頭平均剩余能量要高于LEACH 協(xié)議。根據(jù)兩種算法選擇的簇頭平均剩余能量情況，可推測出LEACH 分簇下會存在能耗不均勻。因此，將兩種算法的總能耗進行對比分析。如圖5 所示，仿真結(jié)果表明，本文提出的算法的總耗能低于LEACH 算法。

圖3 分簇個數(shù)情況

圖4 簇頭節(jié)點平均剩余能量情況

圖5 總能耗情況

3 結(jié)論

針對無線傳感器網(wǎng)絡(luò)的分簇信號重構(gòu)算法的研究問題，提出基于多目標進化的分簇信號重構(gòu)分析方法。主要考慮分簇頭節(jié)點個數(shù)、簇空間分布、節(jié)點剩余能量和網(wǎng)絡(luò)總能耗四個因素對基于LEACH的無線傳感器網(wǎng)絡(luò)分簇信號重構(gòu)算法進行優(yōu)化改進，并給出了較優(yōu)的分簇個數(shù)和分簇結(jié)構(gòu)。相同條件下對最后以LEACH 協(xié)議為例進行分析，實驗仿真結(jié)果表明，本文提出的方法能給出較優(yōu)的分簇信號重構(gòu)方案。