范興剛，王 翊，介 婧，王萬良，侯佳斌

(浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州310023)

隨著傳感器技術(shù)、嵌入式技術(shù)以及低功耗無線通信技術(shù)的發(fā)展，生產(chǎn)一種聚集感應(yīng)、無線通信和信息處理于一體的微型無線傳感器成為可能。這些廉價(jià)的、低功耗的傳感器節(jié)點(diǎn)可以大量部署在感興趣的區(qū)域，通過無線通信組織成無線傳感器網(wǎng)絡(luò)(WSN)，并采用協(xié)同合作方式來感知、采集和處理覆蓋區(qū)域中對(duì)象的信息，最終傳送各檢測(cè)數(shù)據(jù)給觀察者。通常，無線傳感器通過電池驅(qū)動(dòng)，能量非常有限，但其工作的時(shí)間要求卻長(zhǎng)達(dá)幾個(gè)月甚至幾年［1］，并且存在著部分關(guān)鍵路徑上節(jié)點(diǎn)能量消耗過快，整個(gè)網(wǎng)絡(luò)中各節(jié)點(diǎn)能量消耗不均的現(xiàn)象，最終導(dǎo)致網(wǎng)絡(luò)癱瘓，網(wǎng)絡(luò)的壽命受到限制。因此如何降低網(wǎng)絡(luò)能量消耗，延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間成為WSN研究中的熱點(diǎn)［2］，而改善網(wǎng)絡(luò)通信路由協(xié)議則成為解決問題的一個(gè)重要途徑［3－7］。

無線傳感器網(wǎng)絡(luò)從拓?fù)浣Y(jié)構(gòu)的角度可以分為兩類路由協(xié)議，分別是平面路由協(xié)議，如SPIN，F(xiàn)looding，Directed Diffusion 等;層次路由協(xié)議，如 LEACH［3］，PEGASIS，TEEN等。LEACH協(xié)議是一種自適應(yīng)分簇聚類路由算法，與一般的平面多跳路由算法相比，可以延長(zhǎng)15%的生命周期。PEGASIS(Power-Efficient Gathering in Sensor Information Systems)［4］協(xié)議是由LEACH協(xié)議發(fā)展而來的基于“鏈”的路由協(xié)議，它的設(shè)計(jì)更加節(jié)能，其生存周期比LEACH提高1－3倍［5］。它假定組成網(wǎng)絡(luò)的傳感器節(jié)點(diǎn)是同構(gòu)且靜止的，采用貪婪算法生成一條連接各個(gè)節(jié)點(diǎn)的距離最短的鏈，節(jié)點(diǎn)只需要與它最近的鄰居進(jìn)行通信，并且隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為簇頭與基站通信。但PEGASIS協(xié)議還存在著一些不足之處:

(1)貪婪算法是一種局部?jī)?yōu)化算法，容易陷入局部最優(yōu)解，導(dǎo)致形成的鏈路較長(zhǎng);

(2)隨機(jī)選擇節(jié)點(diǎn)作為簇頭的方法，沒有考慮各節(jié)點(diǎn)能耗差別，導(dǎo)致各個(gè)節(jié)點(diǎn)負(fù)載不均衡，部分節(jié)點(diǎn)過早死亡;

(3)單簇頭節(jié)點(diǎn)可能產(chǎn)生瓶頸效應(yīng);

(4)當(dāng)網(wǎng)絡(luò)規(guī)模增大時(shí)，單鏈模式增加網(wǎng)絡(luò)時(shí)延，可能造成數(shù)據(jù)過期，且一個(gè)節(jié)點(diǎn)出現(xiàn)問題可能會(huì)影響整個(gè)網(wǎng)絡(luò)。

針對(duì)這些不足，很多學(xué)者也提出了不同解決方法，主要是從路徑優(yōu)化和分簇多鏈這兩方面來優(yōu)化PEGASIS協(xié)議。GASA協(xié)議［6］采取模擬退火－遺傳混合算法替代貪婪算法的方式尋找一條總距離最短的路由鏈，它類似于解決一個(gè)TSP問題。但GASA協(xié)議仍然保持單鏈形式，因此并未從根本上解決PEGASIS協(xié)議存在的不足。ECR協(xié)議［7］采取劃分區(qū)域的方法，在區(qū)域內(nèi)用C-W節(jié)約法組鏈，選擇各條鏈中能量最大的節(jié)點(diǎn)作為簇頭，并把這些簇頭組成一條簇頭鏈，選舉一個(gè)父簇頭與基站通信。這樣它有效地摒棄了單鏈帶來的缺陷，并使每條鏈中的距離相對(duì)較短。但是ECR協(xié)議在劃分區(qū)域時(shí)已經(jīng)限制了組鏈節(jié)點(diǎn)的選擇，這樣的方式固然在區(qū)域內(nèi)能找到比較短的鏈路，但是從全局上看未必最優(yōu)。

粒子群算法(PSO)［8］自提出以來，以操作簡(jiǎn)單，收斂速度快，解的質(zhì)量高而普遍應(yīng)用于電力，機(jī)械設(shè)計(jì)，神經(jīng)網(wǎng)絡(luò)優(yōu)化，通信，圖像處理等諸多領(lǐng)域。目前用離散粒子群算法(DPSO)來解決組合優(yōu)化問題也是研究的一個(gè)熱點(diǎn)［9－11］。

針對(duì)PEGASIS及其優(yōu)化協(xié)議的優(yōu)缺點(diǎn)和PSO的優(yōu)勢(shì)，本文提出一種基于離散粒子群優(yōu)化算法的分層多鏈無線傳感器網(wǎng)絡(luò)路由算法(DPSOMCRA)。本算法考慮把PEGASIS的單鏈路形式分為多鏈路，這樣能降低通信時(shí)延，同時(shí)結(jié)合DPSO算法則能得到更短的全局最優(yōu)路徑，最終使能量消耗的分布更加合理。通過仿真，與 PEGASIS，GASA，ECR協(xié)議算法進(jìn)行比較，DPSO-MCRA算法能使得整個(gè)網(wǎng)絡(luò)有效生存周期顯著提高，能量消耗也更加均衡。

1 問題描述及算法介紹

1.1 問題描述

本文假設(shè)N個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在一個(gè)正方形區(qū)域A內(nèi)，基站部署在A區(qū)域外，基站位置和節(jié)點(diǎn)位置都已知并固定，基站能量認(rèn)為無窮大，無線發(fā)射功率可控，即節(jié)點(diǎn)可以根據(jù)距離調(diào)整發(fā)射功率大小，每輪節(jié)點(diǎn)能量消耗不統(tǒng)一。

本文的能耗模型參考文獻(xiàn)［4］中的設(shè)定:節(jié)點(diǎn)收發(fā)電路處理信號(hào)能量損耗Eelec=50 nJ/bit，信號(hào)發(fā)射放大器能量消耗 εamp=100 pJ/(bit·m－2)，信號(hào)發(fā)射所需的能量與收發(fā)節(jié)點(diǎn)間距離的平方即d2成正比，數(shù)據(jù)融合所消耗的能量為Efusion=5 nJ/bit。這樣發(fā)送kbit數(shù)據(jù)信息到相距為d的接收位置，所消耗的能量為:

接收kbit數(shù)據(jù)信息消耗的能量為:

融合kbit數(shù)據(jù)信息消耗的能量為:

1.2 算法介紹

本文采用分層多鏈的方式，把整個(gè)網(wǎng)絡(luò)分為高低兩層。低層由m條鏈構(gòu)成，每個(gè)節(jié)點(diǎn)僅有一條鏈路通過，高層為這m條鏈的簇頭構(gòu)成的一條簇頭鏈，并從中選出父簇頭與基站通信。

與PEGASIS類似，本算法由三個(gè)階段組成，分別是組鏈階段;簇頭節(jié)點(diǎn)選取階段;數(shù)據(jù)傳輸階段。

(1)組鏈階段

本階段通過DPSO算法來構(gòu)建低層的節(jié)點(diǎn)間距離的平方和最小的鏈路。

(2)簇頭節(jié)點(diǎn)選取階段

考慮到父簇頭與基站的通信將消耗大量能量。在本階段為了保證能量消耗的均衡，節(jié)點(diǎn)自發(fā)地選擇整個(gè)網(wǎng)絡(luò)中剩余能量與到基站距離平方的比值最大的點(diǎn)作為父簇頭。父簇頭產(chǎn)生后，從它相鄰的鏈內(nèi)選取距離父簇頭最近的一個(gè)節(jié)點(diǎn)作為鄰居鏈的簇頭，依次類推;每個(gè)被選舉的簇頭都把距離它最近的鄰鏈節(jié)點(diǎn)選取為鄰鏈的簇頭，最后，形成了一條簇頭鏈。這樣能保證得到一條相對(duì)較短的簇頭鏈。

(3)數(shù)據(jù)傳輸階段

本階段與PEGASIS數(shù)據(jù)傳輸階段類似。在數(shù)據(jù)傳輸階段，每條低層鏈的兩個(gè)端節(jié)點(diǎn)沿著鏈路將數(shù)據(jù)傳送給自己的鄰居節(jié)點(diǎn)。鄰居節(jié)點(diǎn)將自身數(shù)據(jù)和接收到的數(shù)據(jù)進(jìn)行融合，然后將融合后的數(shù)據(jù)按同樣的方式傳輸給自己的鄰居節(jié)點(diǎn)。這一過程一直持續(xù)到鏈兩端的數(shù)據(jù)都到達(dá)簇頭節(jié)點(diǎn)。簇頭節(jié)點(diǎn)將自身的數(shù)據(jù)與接收到的數(shù)據(jù)融合后再按照上述方式沿高層的簇頭鏈傳遞給父簇頭。父簇頭將融合后的數(shù)據(jù)傳遞給基站。這樣，一輪通信過程結(jié)束。

2 問題模型

根據(jù)本文的算法要求，本問題模型定義 設(shè)點(diǎn)1，…，n表示m條鏈要經(jīng)過的節(jié)點(diǎn)，定義變量:

Cij表示節(jié)點(diǎn)i，j之間距離的平方。目標(biāo)函數(shù)

其中

約束條件

其中S表示鏈路起始點(diǎn)集合，T表示鏈路終結(jié)點(diǎn)集合。

在該模型中，式(1)表示使m條鏈的路徑平方和最小;式(2)表示各條鏈的路徑平方和;式(3)表示所有節(jié)點(diǎn)只有某一條鏈嚴(yán)格訪問一次;式(4)表示任意一條弧上的終點(diǎn)僅有一個(gè)起點(diǎn)與之相連，并且鏈路起始點(diǎn)不會(huì)出現(xiàn)在任何弧的終點(diǎn)上;式(5)表示任意一條弧上的起點(diǎn)僅有一個(gè)終點(diǎn)與之相連，并且鏈路終結(jié)點(diǎn)不會(huì)出現(xiàn)在任何弧的起點(diǎn)上。

3 基于離散粒子群算法的求解

粒子群優(yōu)化算法(PSO)是一種基于群智能方法的演化計(jì)算技術(shù)，有較高的搜索效率，目前已被應(yīng)用于多目標(biāo)優(yōu)化、模式識(shí)別、信號(hào)處理和決策支持等領(lǐng)域。本文分層多鏈問題的目標(biāo)是把所有節(jié)點(diǎn)組合成多條鏈，且總距離最短。如把問題抽象起來看，則就是出發(fā)點(diǎn)不同的開放式多旅行商問題(MTSP)［9］，或是不考慮載重的開放式車輛路徑問題(OVRP)［12］。因此分層多鏈問題是一個(gè)組合優(yōu)化問題，可以使用基于離散PSO算法對(duì)問題進(jìn)行求解。目前對(duì)PSO算法的離散改造有很多種，M.Clerc［11］重新定義了運(yùn)算符號(hào)和規(guī)則，黃嵐［13］等引入了交換子和交換序的概念，郭文忠［14］，王文鋒［10］等建立了局部極小區(qū)域的擾動(dòng)機(jī)制。本文借鑒黃嵐等人定義的PSO速度和位置公式，并針對(duì)本問題的特點(diǎn)對(duì)其進(jìn)行改造。

3.1 編碼方式

為支持尋找WSN內(nèi)遍歷所有傳感器節(jié)點(diǎn)的最優(yōu)多鏈的計(jì)算，本文的粒子采用“兩段式”整數(shù)編碼［15］，這種設(shè)計(jì)適合本問題的求解，并擁有較少的解空間。

設(shè)某粒子是一長(zhǎng)度為n+m的整數(shù)S，由前后兩部分X和R組成。前段X表示鏈路按順序經(jīng)過的節(jié)點(diǎn)序號(hào)，它由整數(shù)1到n的排列構(gòu)成，長(zhǎng)度為n;后段R中的每個(gè)數(shù)字分別表示第1條到第m條鏈路的長(zhǎng)度，且這m個(gè)數(shù)的和等于節(jié)點(diǎn)總數(shù)n，R的長(zhǎng)度為m。如圖1所示，有一個(gè)n=10，m=2的粒子，它有兩條長(zhǎng)度分別為4和6的鏈路，鏈路1依次經(jīng)過第1、5、8、7號(hào)節(jié)點(diǎn)，鏈路2依次經(jīng)過第2、3、4、9、10、6 號(hào)節(jié)點(diǎn)。

圖1 “兩段式”整數(shù)編碼粒子

3.2 初始化種群

本文使用隨機(jī)方式生成初始解。首先，隨機(jī)生成網(wǎng)絡(luò)節(jié)點(diǎn)的排列;然后，把排列按照鏈路的數(shù)目隨機(jī)分為幾段;最后，把整個(gè)鏈路的序列按照本文的編碼方式映射到一個(gè)粒子上。如此重復(fù)，產(chǎn)生最初的種群。

3.3 啟發(fā)式算法

在求解WNS的路由中，為提高尋找最優(yōu)解的速度，考慮使用一些啟發(fā)式算法，通過這些算法對(duì)解進(jìn)行改進(jìn):

(1)消除鏈內(nèi)交叉 真正的最優(yōu)解中必定不包含交叉路徑，因此對(duì)于在一條鏈內(nèi)出現(xiàn)交叉的情況，需要把它消除掉，如圖2所示。方法是找到兩個(gè)交叉的線段ab和ef后，拆除a與b、e與f的連接，改為a與e、b與f連，然后把原先夾在兩線段間的路徑倒序排列。

圖2 消除鏈內(nèi)交叉

(2)消除鏈間交叉 雖然方法1保證鏈內(nèi)不出現(xiàn)交叉，但在存在多條鏈路的區(qū)域中，鏈路之間還會(huì)遇到交叉的情況，如圖3所示。消除鏈間交叉的方法是:找到兩條交叉的線段(cd和mn)后，拆除c與d以及m與n的連接，改為c與n、d與m連。

圖3 消除鏈間交叉

(3)消除長(zhǎng)路徑 在本算法中，把功耗較大的父簇頭與基站通信的任務(wù)讓某一剩余能量與到基站距離平方的比值最大的節(jié)點(diǎn)完成。在網(wǎng)絡(luò)中所有節(jié)點(diǎn)的剩余能量都在不停變化的情況下，這樣做可以使得每個(gè)節(jié)點(diǎn)都有機(jī)會(huì)擔(dān)任父簇頭，提高了網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)能量分布的均衡性，延長(zhǎng)網(wǎng)絡(luò)壽命。

在這種父簇頭選取的策略下，如果兩點(diǎn)間存在一條較長(zhǎng)的線路，隨著輪數(shù)的增加，可能會(huì)遇到其他節(jié)點(diǎn)還有較多能量，但長(zhǎng)路徑上的點(diǎn)過早把能量消耗完的情況。通過仿真發(fā)現(xiàn)大于平均長(zhǎng)度的3倍的路徑較有可能出現(xiàn)這種情況。我們的方法是找到那些線段，在線段中增加中間節(jié)點(diǎn)，或者把該線段刪除另找其他路徑，如圖4。

圖4 消除長(zhǎng)路徑

把上述的啟發(fā)式算法應(yīng)用在DPSO中將提高整個(gè)算法的收斂速度，并保證解的質(zhì)量。但與此同時(shí)也需要考慮它們?cè)谡麄€(gè)算法中應(yīng)用的層面，因?yàn)槿绻麘?yīng)用在每個(gè)粒子的每輪更新中則會(huì)帶來較大的時(shí)間復(fù)雜度，效率并不高。

對(duì)此，考慮到DPSO的特點(diǎn)是所有粒子必須從種群最優(yōu)點(diǎn)(pgbest)處學(xué)習(xí)，這樣對(duì)pgbest的改進(jìn)能夠影響到所有粒子。因此上述的啟發(fā)式算法可以在pgbest更新時(shí)運(yùn)行，這樣更為高效［9］。

3.4 自逃逸算法

PSO算法在理論上并不能保證一定能收斂到全局最優(yōu)點(diǎn)，而是有可能僅收斂到種群最優(yōu)點(diǎn)。當(dāng)多數(shù)粒子的解都集中在某一個(gè)路由方案，并在幾輪中全局最優(yōu)解都沒更新時(shí)，則可以認(rèn)為粒子群可能找到全局最優(yōu)解或者可能陷入局部最優(yōu)區(qū)域，對(duì)于后者需要用某種策略來跳出，本文則采取自逃逸算法。自逃逸思想能夠在粒子群算法陷入局部區(qū)域時(shí)，讓種群自動(dòng)逃離并尋找新的區(qū)域，同時(shí)還記著群體中的目前最好的位置［10］。

定義 設(shè)l為種群中所有粒子與各自pibest及pgbest的弧都重合的比率，即相似度;w’為pgbest連續(xù)沒有更新的輪數(shù)，如更新則歸零;ρ和w分別為l和w’所對(duì)應(yīng)的閾值。

自逃逸算法可描述為:

其中:

這里，E(Pi)表示Pi的弧集合;|E(Pi)|表示E(Pi)中弧的數(shù)目;|Li|表示Pi的弧與pibest和pgbest都重合的弧的數(shù)目;n為網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)總數(shù);λ為種群中粒子總數(shù)。

當(dāng)種群中大部分粒子都搜索某一區(qū)域內(nèi)時(shí)，基本能保證找到局部最優(yōu)解或次優(yōu)解，再繼續(xù)收斂則可能陷入局部最優(yōu)。對(duì)于這樣的情況，種群中的粒子就會(huì)被初始化的新粒子替代，以保持種群的多樣性，跳出局部最優(yōu)區(qū)域。

3.5 適應(yīng)度計(jì)算

在每次迭代粒子更新位置后，根據(jù)公式(1)計(jì)算出目標(biāo)函數(shù)值Z，則適應(yīng)度為:

3.6 求解步驟

在本算法設(shè)計(jì)中定義粒子為兩段式，且含義不同。因此需要在每次運(yùn)算中分別計(jì)算粒子的前后兩段，這樣才能保證粒子既能進(jìn)化各鏈中的位置又能進(jìn)化各鏈的長(zhǎng)度。

本文算法的步驟如下:

步驟1 初始化粒子群;

步驟2 計(jì)算每個(gè)粒子適應(yīng)度值;

步驟3 比較適應(yīng)度，選擇pibest和pgbest;

步驟4 使用啟發(fā)式算法改進(jìn)pgbest;

步驟5 計(jì)算種群的相似度l，如果相似度大于閾值ρ且w’大于w，啟動(dòng)逃逸算法;

步驟6 根據(jù)DPSO公式進(jìn)行位置更新;

步驟7 判斷是否達(dá)到結(jié)束條件，是則結(jié)束，否則轉(zhuǎn)入步驟2。

4 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證DPSO-MCRA算法的性能，本文對(duì)該算法進(jìn)行了Matlab仿真，并同時(shí)模擬PEGASIS、GASA、ECR算法與其進(jìn)行對(duì)比。

仿真環(huán)境的設(shè)定:在100 m×100 m的正方形區(qū)域內(nèi)隨機(jī)產(chǎn)生100個(gè)節(jié)點(diǎn)，Sink節(jié)點(diǎn)位于監(jiān)測(cè)區(qū)域外的(50，150)，節(jié)點(diǎn)初始能量 E0=0.25 J，數(shù)據(jù)傳輸包大小k=2 000 bit，數(shù)據(jù)融合后包大小不變，采用按工作周期“輪”(Round)進(jìn)行數(shù)據(jù)采集的方式運(yùn)行整個(gè)網(wǎng)絡(luò)，并用輪數(shù)衡量網(wǎng)絡(luò)的壽命。

仿真中自逃逸參數(shù)ρ設(shè)為0.8，w為8。對(duì)于本算法分鏈數(shù)目m的選擇問題，我們分別對(duì)2，3，5，7，10條鏈路進(jìn)行仿真，以50%節(jié)點(diǎn)死亡的生存周期為對(duì)比值，各運(yùn)行20次取平均值，結(jié)果見圖5。

圖5 不同分鏈數(shù)m對(duì)比圖

從仿真結(jié)果看，當(dāng)m取5時(shí)，網(wǎng)絡(luò)在50%節(jié)點(diǎn)失效的情況下輪數(shù)達(dá)到最高。隨著網(wǎng)絡(luò)m的減少，運(yùn)行輪數(shù)迅速減小。這是由于鏈路的減少造成了相鄰節(jié)點(diǎn)選擇余地的減少，造成總路徑距離的增加。相反，當(dāng)m增加時(shí)，輪數(shù)略微減少。這是由于雖然鏈路的增多能使相鄰節(jié)點(diǎn)的距離普遍減小，但鏈路中簇頭的增多卻帶來了更多的簇頭間的通信能耗。因此根據(jù)實(shí)際情況選擇適當(dāng)?shù)逆溌窋?shù)目才能使節(jié)點(diǎn)及簇頭的能耗達(dá)到平衡。本文的仿真中均取m=5。

從通信距離看本算法得到的鏈路也是最短的，圖6是它們各自的通訊鏈路情況。從表1中可以看到PEGASIS的鏈路最長(zhǎng)，比本算法大了3倍多;ECR雖然根據(jù)區(qū)域劃分為5條不交叉的鏈路，但由于未采用優(yōu)化算法故距離要比GASA長(zhǎng);GASA在單鏈的情況下能找到一條最短的鏈路，但比本算法還是多了將近20%的距離。本算法采用多條鏈的形式，既降低網(wǎng)絡(luò)內(nèi)鏈路距離，又減少傳遞延時(shí)，并采取策略消除長(zhǎng)鏈，使各個(gè)節(jié)點(diǎn)能耗差別減小，有利于網(wǎng)絡(luò)能量消耗的平衡，防止節(jié)點(diǎn)過早死亡，延長(zhǎng)網(wǎng)絡(luò)壽命。

表1 DPSO-MCRA與其他算法對(duì)比

圖6 各算法鏈路圖

本文對(duì)DPSO-MCRA算法生存周期進(jìn)行仿真，分別與PEGASIS，GASA，ECR協(xié)議比較。比較結(jié)果見表2及圖7。

圖7 DPSO-MCRA與其他算法生存周期對(duì)比圖

表2 DPSO-MCRA與其他算法的生存周期對(duì)比

表2的結(jié)果顯示，本算法出現(xiàn)第一個(gè)節(jié)點(diǎn)死亡的輪數(shù)較晚，比PEGASIS的輪數(shù)提高近3倍。在能保證網(wǎng)絡(luò)有效性的20%、50%、80%節(jié)點(diǎn)死亡的情況下，本算法與PEGASIS，GASA，ECR協(xié)議的生存周期相比是最長(zhǎng)的。這是因?yàn)槭紫缺舅惴ㄟx取網(wǎng)絡(luò)中剩余能量與到基站距離的比值最大的節(jié)點(diǎn)作為父簇頭節(jié)點(diǎn)，使網(wǎng)絡(luò)的能量消耗均勻，有效延長(zhǎng)了網(wǎng)絡(luò)中第一個(gè)死亡節(jié)點(diǎn)存活的時(shí)間;其次，采取多條鏈路的形式，并結(jié)合離散粒子群優(yōu)化算法組建網(wǎng)絡(luò)通信路徑，得到總路徑平方和最小的路徑，減小每輪節(jié)點(diǎn)間信號(hào)傳輸?shù)木嚯x，降低能耗，并在整體上均衡能耗的分布，延長(zhǎng)了網(wǎng)絡(luò)失效的時(shí)間。

值得一提的是，在圖7中，PEGASIS協(xié)議最后全部節(jié)點(diǎn)死亡的生存周期比本算法要長(zhǎng)一些。這是因?yàn)槠淠芎姆植疾痪庵率共糠止?jié)點(diǎn)消耗的能量比其他節(jié)點(diǎn)少，因而這些節(jié)點(diǎn)的存活壽命會(huì)相對(duì)較長(zhǎng)。但當(dāng)網(wǎng)絡(luò)中大部分節(jié)點(diǎn)死亡時(shí)，網(wǎng)絡(luò)監(jiān)測(cè)就失去意義了，網(wǎng)絡(luò)的生命周期實(shí)際上已經(jīng)結(jié)束。而本算法在50%節(jié)點(diǎn)開始死亡后整個(gè)網(wǎng)絡(luò)就在近20輪內(nèi)迅速死亡，這是由于節(jié)點(diǎn)間剩余能量差異并不顯著，也是其網(wǎng)絡(luò)能耗分布均衡的表現(xiàn)。

在WSN設(shè)計(jì)中，保持能量的有效性所帶來的過高延遲也是實(shí)際情況中所需要避免的。因此必須尋求能量消耗和延遲兩者之間的一個(gè)折衷。本算法中描述的分層多鏈構(gòu)建法能有效減少延遲。

假設(shè)一個(gè)節(jié)點(diǎn)將數(shù)據(jù)傳遞給另外一個(gè)節(jié)點(diǎn)所需的時(shí)間為一個(gè)時(shí)間單位。對(duì)于一個(gè)100個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，PEGASIS協(xié)議和GASA協(xié)議每輪數(shù)據(jù)傳輸?shù)臅r(shí)延都達(dá)到100個(gè)單位時(shí)間。ECR協(xié)議則與本算法的時(shí)延類似，按照分5條鏈來算，總共大概需要25個(gè)單位時(shí)間。表1顯示了PEGASIS，ECR，GASA協(xié)議和本算法的時(shí)延開銷比較，從中可以看出本算法在降低網(wǎng)絡(luò)時(shí)延上還是比較有效的。

與其他算法對(duì)比，本算法在優(yōu)化能耗和降低時(shí)延這兩個(gè)問題上能做到兩者兼顧，既能保證較長(zhǎng)的生存周期又擁有較低的通信時(shí)延。

5 結(jié)束語

本文在分析了 PEGASIS、GASA、ECR協(xié)議優(yōu)缺點(diǎn)的基礎(chǔ)上，提出了基于離散粒子群優(yōu)化算法的分層多鏈無線傳感器網(wǎng)絡(luò)路由算法DPSOMCRA。它把網(wǎng)絡(luò)分層后，采用離散粒子群優(yōu)化算法并結(jié)合多種啟發(fā)式算法快速得到全局最優(yōu)的多條鏈路的路徑，即降低能耗又減小延遲。同時(shí)改進(jìn)簇頭選擇方法，有效地減少能耗并保證能耗的均衡，延長(zhǎng)網(wǎng)絡(luò)壽命。仿真結(jié)果顯示，本算法比其他協(xié)議在20%—80%節(jié)點(diǎn)死亡的情況下，生存周期顯著提高。首節(jié)點(diǎn)死亡時(shí)的生存周期比PEGASIS協(xié)議提高了近3倍。

［1］Shih E，Cho S，Ickes N，et al.Physical Layer Driven Protocol and Algorithm Design for Energy-Efficient Wireless Sensor Networks［C］.Proceedings of ACM MobiCom’01，Rome，Italy，2001:272－287.

［2］Sohrabi K，Gao J，Ailawadhi V，et al.Protocols for Self-Organization of a Wireless Sensor Network［J］.IEEE Personal Communications，2000，7(5):16－27.

［3］Heinzelman W，Chandrakasan A，Balakrishnan H，et al.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［C］//IEEE Trans，on Wireless Communications，2002，1(4):660－670.

［4］Lindsey S，Raghavendra C S.PEGASIS:Power-Efficient Gathering in Sensor Information Systems［J］.Aerospace Conference Proceddings，2002(3):1125 －1130.

［5］Al-Karaki JN，Kamal AE.Routing Techniques in Wireless Sensor Networks:a Survey［J］.IEEE Wireless Communications，2004，11(6):6－28.

［6］黃飛，金心宇，張昱，等.基于GASA的能耗均衡WSN路由協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，2009(4):586－592.

［7］田瑩，王瑩，張淑芳，等.高效節(jié)能的鏈?zhǔn)椒謱訜o線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43(35):22－26.

［8］Kennedy J，Eberhart R C.Particle Swarm Optimization［C］//Proc IEEE International Conference on Neural Net-Works，IV.Piscataway，NJ:IEEE Service Center，1995:1942 －1948.

［9］Shi X H，Liang Y C，Lee H P，et al.Particle Swarm Optimization Based Algorithms for TSP and Generalized TSP［J］.Information Processing Letters，2007，103(5):169 －176.

［10］王文峰，劉光遠(yuǎn)，溫萬惠，等.求解TSP問題的自逃逸混合離散粒子群算法研究［J］.計(jì)算機(jī)科學(xué)，2007(10):2478－2480.

［11］Clerc M.Discrete Particle Swarm Optimization，Illustrated by the Traveling Salesman Problem［C］//New Optimization Techniques in Engineering.Heidelberg，Germany，2004，219 －239.

［12］趙燕偉，吳斌，王萬良，等.Particle Swarm Optimization for Open Vehicle Routing Problem with Time Dependent Travel Time［C］//Proceedings of the 17 th IFAC World Congress，July.2008:12843－12848.

［13］黃嵐，王康平，周春光，等.粒子群優(yōu)化算法求解旅行商問題［J］.吉林大學(xué)學(xué)報(bào)(理學(xué)版)，2003，41(4):477 －480.

［14］郭文忠，陳國(guó)龍.求解TSP問題的模糊自使用粒子群算法［J］.計(jì)算機(jī)科學(xué)，2006(6):161－162.

［15］歐陽(yáng)杰平.使用遺傳算法解決MTSP問題的一種新的染色體設(shè)計(jì)［J］.艦船電子工程，2006(3):107－109.