丁 娟,劉三陽,張 平

（西安電子科技大學 理學院，陜西 西安 710071）

無線傳感器網(wǎng)絡(luò) WSN(Wireless Sensor Network)[1]是將大量微型傳感器節(jié)點隨機部署在目標區(qū)域，以自組織方式形成的網(wǎng)絡(luò)，其目的是讓這些節(jié)點協(xié)作地采集和處理網(wǎng)絡(luò)覆蓋區(qū)域的信息，并傳遞給控制管理中心。WSN將現(xiàn)代通信技術(shù)、微型傳感器技術(shù)和網(wǎng)絡(luò)技術(shù)有機融為一體，在軍事、醫(yī)療、環(huán)境監(jiān)測、智能交通等許多領(lǐng)域有極高的應(yīng)用價值和廣闊的應(yīng)用前景。由于受到節(jié)點能耗的限制，如何在近乎苛刻的能源條件下延長網(wǎng)絡(luò)生命成為WSN首要考慮的問題。

1 LEACH協(xié)議簡介

LEACH(Low Energy Adaptive Clustering Hierarchy)[2]是一種低功耗自適應(yīng)分層路由協(xié)議。該協(xié)議中網(wǎng)絡(luò)運行時間按“輪”計量，每輪循環(huán)分為簇的建立和數(shù)據(jù)通信兩個階段。網(wǎng)絡(luò)節(jié)點動態(tài)成簇，簇頭負責收集、融合成員節(jié)點采集的數(shù)據(jù)，并將融合后的數(shù)據(jù)直接發(fā)送給基站。LEACH協(xié)議一方面能夠保證各節(jié)點等概率地擔任簇頭，使得網(wǎng)絡(luò)能量分布相對均衡；另一方面運用TDMA的MAC層機制來減少簇內(nèi)數(shù)據(jù)發(fā)送沖突，降低了能耗。但該協(xié)議仍存在以下幾點不足：(1)簇頭的選擇未考慮節(jié)點的距離和剩余能量因素，易導致簇頭分布不均或能量低的節(jié)點當選簇頭；(2)該協(xié)議提到了數(shù)據(jù)融合的概念，但并未給出具體的算法；(3)簇頭與基站采用一跳通信模式，如果某個簇頭距離基站較遠，能耗會大幅增加，影響網(wǎng)絡(luò)性能。

[3]針對突發(fā)事件監(jiān)測網(wǎng)絡(luò)利用蟻群算法構(gòu)建數(shù)據(jù)收集鏈路，參考文獻[4]提出了基于區(qū)域的簇頭選擇和采用貪婪算法構(gòu)建簇間鏈式路由的多跳數(shù)據(jù)傳輸方法。以上兩種方法節(jié)能效果都很顯著，但單簇頭使得網(wǎng)絡(luò)的魯棒性較差。參考文獻[5]提出了基于自適應(yīng)數(shù)據(jù)融合的路由協(xié)議，延長了網(wǎng)絡(luò)時間，但未考慮到簇頭的選擇及其路由方式。

針對LEACH協(xié)議的不足，綜合考慮簇頭的選擇、數(shù)據(jù)融合方法以及簇頭與基站的通信方式三個方面，提出了改進算法LEACH-E。

2 改進的數(shù)據(jù)收集和融合算法

2.1 模型假設(shè)

本文對網(wǎng)絡(luò)模型作如下假設(shè)：(1)基站固定;(2)所有節(jié)點同構(gòu)，能量有限，具有定位功能以及數(shù)據(jù)融合能力;

(3)節(jié)點可調(diào)節(jié)功率大小與基站點通信;(4)節(jié)點能量消耗采用一階無線電模式[6]。

2.2 算法描述

2.2.1 簇的建立

節(jié)點n產(chǎn)生隨機數(shù)，當該值小于門限值T(n)時，該節(jié)點成為本輪的一個簇頭，否則節(jié)點等待簇頭發(fā)出公告，根據(jù)信號的強弱來決定自己要加入的簇。為避免節(jié)點因任務(wù)過重而過早死亡，LEACH-E算法中將T(n)定義如下：

其中，p為網(wǎng)絡(luò)中簇頭個數(shù)的百分比，r為當前輪數(shù)，G為最近 1/p輪未當選過簇頭的節(jié)點集，Eo和 Ecureent分別是節(jié)點初始能量和當前能量。

同時，為了避免產(chǎn)生的簇頭過于集中，甚至導致簇內(nèi)通信彼此干擾[7]的情況出現(xiàn)，一旦選出的兩個簇頭間距小于通信半徑的1/4，就取消其中能量較小的節(jié)點本次擔任簇頭的資格。

2.2.2 簇頭的數(shù)據(jù)融合

數(shù)據(jù)融合[8]是將來自不同節(jié)點的信息中冗余、無效和可信度較差的部分刪除，并處理成一個較小的、內(nèi)容等價的信息，從而在滿足用戶需求的條件下最小化網(wǎng)絡(luò)傳輸量。在WSN中，相比于數(shù)據(jù)的采集和處理，節(jié)點的能量主要消耗在無線通信模塊，而數(shù)據(jù)融合正是一種能極大程度地減少通信量從而降低能耗的技術(shù)。

由于同一個簇內(nèi)節(jié)點分布相對集中，不同節(jié)點一定時間內(nèi)采集的數(shù)據(jù)有極大的相關(guān)性，本文采用主成分分析法對數(shù)據(jù)降維，即將多個原始變量線性組合為少數(shù)幾個互不相關(guān)的綜合變量（即主成分），從而使這些主成分能夠反映原始變量的絕大部分信息，且所含的信息互不重疊。其具體步驟如下：

(1)簇頭每隔一定時間收到一次N個成員節(jié)點發(fā)送的數(shù)據(jù)，當收到 M次后，構(gòu)成原始數(shù)據(jù)矩陣 XM×N，其中 xij表示第j個節(jié)點第i次發(fā)送的數(shù)據(jù)。

(2)對 XM×N進行標準化處理得到， 記 μ1×N為均值向量，σ1×N為標準差向量。

(3)求標準化后變量的協(xié)方差矩陣 SN×N。

(4)求 S 的特征值 λ1≥λ2≥…≥λN＞0及相應(yīng)的單位正交特征向量 A=(a1,a2,…,aN)。

(6)計算標準化的原始數(shù)據(jù)在提取出的特征向量上的投影Y=。

(7)數(shù)據(jù)的重構(gòu)。簇頭將得到E、Y、μ、σ發(fā)送給基站，基站對數(shù)據(jù)進行重構(gòu)，計算D=YET，同時將μ擴展成UM×N，其中U的每一行均由μ構(gòu)成，將σ對角化為Σ，令X*=DΣ+U，即得到原始數(shù)據(jù)的近似。

2.2.3 簇間的路由

由能量模型可知，節(jié)點間路徑越短，其通信能耗就越小。基于WSN拓撲結(jié)構(gòu)不斷變化的特點，本文采用蟻群算法建立簇間路由，從而將簇頭的一跳通信改為多跳，在縮短單跳距離的同時保證簇頭到基站的路徑之和最短。

蟻群算法[9]是一種自組織的、并行的算法，其基本思想是螞蟻能夠根據(jù)相鄰簇頭間信息素的積累建立正向反饋機制找到通往基站的最短路徑。首先，隨機分配m只螞蟻到n個簇頭上，每條路徑上初始信息素相等，每只螞蟻根據(jù)路徑上的信息素濃度、距離以及剩余能量獨立選擇下一跳節(jié)點，t時刻螞蟻k從簇頭i到相鄰簇頭j的轉(zhuǎn)移概率定義為：

其中，Ni為節(jié)點i在通信半徑以內(nèi)的節(jié)點即鄰居節(jié)點，Mk為第k只螞蟻已走過的節(jié)點集，啟發(fā)式因子ηij=1/dij2,τij、dij分別為兩簇頭間的信息素和距離。在所有螞蟻完成一次搜索之后，按以下規(guī)則更新最優(yōu)路徑上的信息素量：

其中,ρ為信息素揮發(fā)因子，Q為信息素強度，Lk表示第k只螞蟻在本次循環(huán)中所走路徑的總長度。當算法運行達到最大迭代次數(shù)后，選擇值最小的作為當前最優(yōu)解，簇頭將沿著得到的最優(yōu)路徑通過多跳方式將數(shù)據(jù)傳給基站。

由于蟻群算法是一種啟發(fā)式算法，下一跳節(jié)點的選擇有一定的隨機性，因此不能保證每次都能找到最短路徑，這樣可能會增加傳輸延遲和節(jié)點能耗，但同時也避免了一定時間內(nèi)總是沿著唯一一條最短路徑進行通信，進而導致該路徑上的簇頭承擔了太多的發(fā)送任務(wù)而過早死亡的情況出現(xiàn)。

3 仿真實驗與分析

本文運用MATLAB7.0進行仿真，分別從簇頭向基站發(fā)送數(shù)據(jù)包的數(shù)目、節(jié)點的平均能耗和網(wǎng)絡(luò)存活節(jié)點個數(shù)三個方面來比較改進前后算法的性能。

在100 m×100 m的區(qū)域內(nèi)隨機分布100個節(jié)點，基站位于(50,175)。具體參數(shù)設(shè)置如表1。

圖1是簇頭發(fā)送給基站的數(shù)據(jù)包數(shù)目。當簇頭基于主成分分析法對數(shù)據(jù)融合之后，原本每個簇頭要發(fā)送M×N個數(shù)據(jù)，如今只需傳送(M×p+N×p+2N)個數(shù)據(jù)，從而大幅地減少了數(shù)據(jù)通信量，緩解了網(wǎng)絡(luò)擁塞。圖2直觀地表明LEACH-E算法能有效減少節(jié)點的平均能耗。圖3是網(wǎng)絡(luò)存活節(jié)點個數(shù)隨輪數(shù)的變化情況。LEACH中網(wǎng)絡(luò)運行至第449輪時第一個節(jié)點死亡，當LEACHE在560輪時才出現(xiàn)死亡節(jié)點，前者在518輪時半數(shù)節(jié)點死亡，而后者在599輪時50%節(jié)點死亡，可見改進后的算法能將網(wǎng)絡(luò)周期延長15%左右。這正是由于LEACH-E充分考慮了簇頭的位置分布、剩余能量、通信方式等因素，使網(wǎng)絡(luò)能量被均勻分擔到每個節(jié)點上，避免了部分節(jié)點負載重而過早失效，從而有效延長了網(wǎng)絡(luò)的生存時間。

表1 仿真參數(shù)表

本文基于LEACH協(xié)議，針對簇頭的選擇、數(shù)據(jù)融合算法以及簇頭到基站的通信方式做了一系列優(yōu)化。實驗結(jié)果表明,該算法相比于LEACH協(xié)議能有效地節(jié)省節(jié)點能耗，保證網(wǎng)絡(luò)負載均勻，延長網(wǎng)絡(luò)生命。但本文未考慮數(shù)據(jù)融合帶來的延遲問題，因此如何平衡數(shù)據(jù)融合的時效性是進一步探索和研究的方向。

參考文獻

[1]王殊,閻毓杰,胡富平.無線傳感器網(wǎng)絡(luò)的理論及應(yīng)用[M].北京：北京航空航天大學出版社，2007.

[2]HEINZELMAN W,CHANDRAKASAN A,BALAKRISHNAN H.Energy-efficient communication protocol for wireless microsensor networks[J].IEEE Computer Society,2002:3005-3014.

[3]楊靖,熊偉麗,秦寧寧,等.用于無線傳感器網(wǎng)絡(luò)的高效能數(shù)據(jù)收集算法[J].吉林大學學報（工學版）,2011,41(6):1720-1725.

[4]李雅卿,李臘元.WSN中LEACH路由協(xié)議的改進及其仿真[J].計算機工程,2009,35(10):104-106.

[5]王培東,袁召蘭,王瑜.基于自適應(yīng)數(shù)據(jù)融合的 LEACH路由協(xié)議[J].電子技術(shù)應(yīng)用,2011,37(7):123-126.

[6]廖明華,張華,謝建全.基于蟻群算法的 WSN能量預(yù)測路由協(xié)議[J].計算機工程,2012,38(3):88-90.

[7]張路橋,朱清新,呂濤,等.無線傳感器網(wǎng)絡(luò)中考慮干擾的拓撲優(yōu)化[J].電子科技大學學報,2011,40(4):564-567.

[8]孫利民,李建中,陳渝.無線傳感器網(wǎng)絡(luò)[M]．北京:清華大學出版社,2005:260-272.

[9]Duan Haibing.Ant colony algorithms:theory and applications[M].Beijing:Science and Technology Press,2007.