基于離散PSO的分層多鏈無線傳感器網(wǎng)絡(luò)路由算法*

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

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

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

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

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

(2)隨機選擇節(jié)點作為簇頭的方法，沒有考慮各節(jié)點能耗差別，導致各個節(jié)點負載不均衡，部分節(jié)點過早死亡;

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

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

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

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

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

1 問題描述及算法介紹

1.1 問題描述

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

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

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

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

1.2 算法介紹

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

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

(1)組鏈階段

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

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

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

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

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

2 問題模型

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

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

其中

約束條件

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

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

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

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

3.1 編碼方式

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

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

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

3.2 初始化種群

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

3.3 啟發(fā)式算法

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

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

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

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

圖3 消除鏈間交叉

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

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

圖4 消除長路徑

把上述的啟發(fā)式算法應(yīng)用在DPSO中將提高整個算法的收斂速度，并保證解的質(zhì)量。但與此同時也需要考慮它們在整個算法中應(yīng)用的層面，因為如果應(yīng)用在每個粒子的每輪更新中則會帶來較大的時間復雜度，效率并不高。

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

3.4 自逃逸算法

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

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

自逃逸算法可描述為:

其中:

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

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

3.5 適應(yīng)度計算

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

3.6 求解步驟

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

本文算法的步驟如下:

步驟1 初始化粒子群;

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

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

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

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

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

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

4 實驗結(jié)果及分析

為了驗證DPSO-MCRA算法的性能，本文對該算法進行了Matlab仿真，并同時模擬PEGASIS、GASA、ECR算法與其進行對比。

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

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

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

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

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

表1 DPSO-MCRA與其他算法對比

圖6 各算法鏈路圖

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

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

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

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

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

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

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

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

5 結(jié)束語

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

［7］田瑩，王瑩，張淑芳，等.高效節(jié)能的鏈式分層無線傳感器網(wǎng)絡(luò)路由協(xié)議［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］王文峰，劉光遠，溫萬惠，等.求解TSP問題的自逃逸混合離散粒子群算法研究［J］.計算機科學，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］.吉林大學學報(理學版)，2003，41(4):477 －480.

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

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