一種基于多目標進化的無線傳感器網絡的信號重構算法

張朝霞 蔣 勇 李麗霞 羅智勇

（湖南化工職業技術學院，湖南 株洲 412004）

無線傳感器網絡是一種多跳、自組織的無線通信網絡，部署了大量能量受限的傳感器節點[1]。具有快速展開和抗毀性強等特點，可廣泛應用于軍事偵察、醫療監護、工業生產、環境監測、農業養殖等領域。

WSN 一般采用分簇路由方式，具有拓撲管理方便、數據融合簡單和節省能量等優點。如圖1 所示，在分簇路由算法中，通常將網絡劃分為若干個簇，即為具有某種關聯的網絡節點集合。每個簇由一個簇頭和多個簇內成員組成，由簇頭與基站通信。

圖1 無線傳感器網絡的拓撲結構

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

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

1 系統模型

傳感器節點通常能量受限。為了延長網絡生存時間，簇頭一定要周期性更新。而分簇的結構、大小以及數量取決于簇頭的選擇方法、數量和位置。因此，簇頭的選擇方法要依據以下準則：（1）簇內成員到簇頭的通信代價；（2）簇頭的空間分布；（3）節點剩余能量；（4）能耗均衡。基于以上準則進行建模。

1.1分簇緊密度

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

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

1.2 能耗模型

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

圖2 能耗模型

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

為簡化模型，做如下假設：

（1）n 個傳感器節點隨機分布在M×M的方形區域內，數據匯聚節點（Sink）位于監測區域的中央。

（2）考慮到網絡開銷的能耗遠小于傳輸數據的能耗，本文僅考慮了數據傳輸的能耗。

（3）通信過程中不存在重連和數據傳輸錯誤，且節點傳輸的數據存在冗余。

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

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

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

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

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

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

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

1.3 適應度函數

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

其中，ECHN_average為簇頭節點平均剩余能量，α 為權重因子，其大小可由用戶根據工程實踐中的實際需要進行調整。

1.4 多目標進化模型

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

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

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

1.4.2 選擇交叉與變異

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

具體步驟如下：

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

最后，用H1替換H0重復執行上述步驟，一直到Fmin達到一個穩定值，即達到滿足終止條件時，Fmin對應的個體即為最優的分簇結構。

2 仿真結果分析

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

表1 仿真參數

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

圖3 分簇個數情況

圖4 簇頭節點平均剩余能量情況

圖5 總能耗情況

3 結論

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