基于DPSO的智能WSN分簇路由算法*

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

(浙江工業大學計算機科學與技術學院杭州310023)

無線傳感器網絡WSN(Wireless Sensor Network)是21世紀新興的信息技術之一，并且被美國商業周刊列為21世紀改變世界的十大技術之一。WSN是由許多廉價的具有信息采集功能的傳感器節點組成的網絡，用來感知和采集各種信息，并將采集到的信息傳輸給基站BS(Base Station)對信息做進一步處理。傳感器節點由電池提供能量，因此能量非常有限，而且每個節點的計算存儲能力也很弱［1］。

由于WSN能量有限，設計能量有效的WSN路由協議顯得猶為重要。目前WSN路由協議分為平面路由協議和分層路由協議兩大類。LEACH協議是一種有代表性的低功耗分層路由協議，LEACH相比其他平面路由協議生命周期提高15%以上［2］。然而LEACH依照概率隨機選擇簇頭的機制有很大的隨機性不保證產生均勻的簇結構，不均勻的簇結構會大大縮短WSN的生命周期。而且LEACH中簇首和BS直接通信的機制也會消耗大量的能量。

PSO是一種群智能算法，由Kennedy和Eberhart首先提出［3］。PSO已經被證明是一種解決工程領域NP難問題的有效的解決方法［4－6］。為解決LEACH協議分簇不均勻的問題，本文把基本粒子群優化(PSO)算法改造成適合分簇問題的DPSO。并且直接由基站運行改造后的DPSO計算出最佳簇首的位置。在計算過程中，本文使用PSO慣性權重調整和變異策略來避免PSO的容易陷入局部最優的現象并且通過針對本問題的啟發算法來幫助計算最佳簇首的位置。計算出最佳簇首位置后，本文根據能量傳輸代價為權值計算每個簇首經由其他簇首到基站的最短路徑。另外本文提出讓簇首感應自己的剩余能量，當能量小于一定閾值時，算法會選擇當前簇內節點剩余能量最多的簇內節點當選新的簇首，從而避免LEACH中隔一定時間全部重新選擇簇首帶來的能量消耗。

最后本文使用MATLAB對本文提出的算法進行仿真驗證。實驗比較了DPSO—CR和LEACH的分簇效果，還比較了傳輸數據所消耗的能量情況。實驗結果表明無論從分簇的均勻性還是網絡生命周期來看，DPSO—CR相對LEACH協議都有大幅提高。

1 LEACH協議及其改進

1．1 LEACH協議描述和分析

下面簡要描述LEACH協議的原理并給出分析。

LEACH協議分為兩個階段。第一個階段是產生簇的階段。這個階段中每個傳感器節點產生一個0－1的隨機數，如果該隨機數小于一個閾值公式的值這個節點就成為簇首。這個閾值公式表達式如下:

其中n表示某個傳感器節點的編號，N是傳感器節點的個數，K是期望產生的簇頭個數，r是選舉簇首的輪數，Gr是最近的N/K輪中還沒當選過簇首的節點集合。

節點當選簇首后會廣播其成為簇首的消息，其余普通節點選擇收到信息的信號強度也就是距離自己最近的簇首加入。普通節點發送給簇首加入它的消息，簇就建立了。

第二個階段是穩定的數據傳輸階段，普通節點按TDMA時間片在規定時間給簇首，簇首對數據經過一定的融合后將數據一跳傳給基站。數據傳輸階段進行一個時間段后(遠長于第一階段)進行下一輪簇首的選擇［2］。

LEACH的隨機選擇簇首機制可能導致非常差的分簇效果。首先導致簇首個數不確定，可能出現簇首個數遠小于期望簇首數K的情況;簇首可能分布很不均勻，比如集中某一區域，這樣普通節點可能距離最近的簇首仍然非常遠，這樣在通信中必然耗費大量的能量，簇首分布不均勻還導致簇與簇之間能量消耗不均衡;在簇首選擇的時候也沒有考慮剩余能量因素，剩余能量少的節點擔任簇首將導致節點能量迅速耗盡而死亡。再者簇首直接將數據一跳傳輸給基站也不合理，長距離的傳輸對節點能量的消耗是非常大的;最后LEACH協議按輪重新全局選擇簇首的機制由于當選簇首的廣播消息也耗費大量的能量［10，15］。

1．2 對LEACH協議的改進

針對LEACH協議存在的問題，國內外學者也提出了不少LEACH的改進策略。

M．J．Handy等人對LEACH協議簇首選擇公式進行改進，考慮了剩余能量的因素，改進后的公式如下［7］:

其中P是簇首所占所有節點百分比，Ecur是現在剩余能量，Emax是初始能量，rs是該節點到目前為止還沒當選簇首的輪數。通過該改進一定程度上避免了低剩余能量的節點當選簇首。但是概率性機制沒有改變，仍然可能選擇低剩余能量成為簇首，而且分簇不均勻這個大問題也沒有解決。

王國芳等人利用Prim算法生成包括基站在內的所有簇首節點的最小生成樹，實現了簇首和基站之間的多跳通信，找到了簇首間短距離通信的最優路徑［8］。

梁英等人采用先使用LEACH算法進行分簇得到候補簇首，然后用粒子群算法進行優化在已經產生的簇內確定最后簇首［13］。雖然先用LEACH算法進行分簇，再在簇內用粒子群選擇最優簇首的方法能在一定程度上解決簇首位置不合理的情況，但是從全局來看先用LEACH進行分簇可能已經產生不合理的簇劃分，再在已經劃分的簇內優化只是一種局部優化。而本文提出利用粒子群算法直接尋找全局最優的簇首位置，從而使簇結構在整個監測區域來看都是分布均勻合理的。

2 本文的協議描述

本文算法假設節點能量有限且能感知剩余能量，并且可以根據發送距離長短調整發射的功率。另外本文假設傳感器節點擁有GPS定位功能能獲取自己相對基站的位置信息。基站能量無限，計算最佳簇首位置和簇首到基站的多跳路徑都由基站來計算。

2．1 計算最佳簇首位置

本文提出算法的第一步就是通過改造的離散粒子群算法計算最佳簇首的位置。下面詳細描述。

2．1．1 粒子群算法的適應度函數

運用粒子群算法的第一步就是要確定適應度函數。本文的問題是從N個節點找出一組處于最佳位置的節點擔當簇首的角色使分成的簇均勻。當一個簇內的節點能緊密地圍繞著簇首節點時可以被認為是個均勻的簇。當簇內所有節點到簇首的距離總和最小且它們到簇首距離都差不多大小時(也就是簇內所有節點到簇首的距離方差最小時)可以刻畫出緊密圍繞的特征。因此從所有節點來看，當所有簇的簇內節點到各自簇首距離總和的平均值與所有簇的簇內節點到各自簇首的距離方差的平均值同時達到最小時，所有的簇的結構應該是均勻合理的。適應度函數定義如下:

其中Dji－jCH代表第j個簇中第i個簇內節點到簇首的距離，i從簇內第一個節點到第m個節點，j從第一個簇到第n個簇。mean是求平均值的函數，var是求方差的函數。

這里還有一點要說明，根據文獻［9］，當簇首節點所占百分比為所有節點5%時，能量最有效。本文中運用了這個研究成果，簇首個數就設定為所有節點的5%，簇內節點個數都相等。

2．1．2 分簇問題的離散粒子群改造

要解決本文提出的計算最佳簇首位置的問題，必須對基本PSO進行相應的離散改造。國內外學者對解決TSP問題(Travelling Salesman Problem)的粒子群離散改造的研究成果比較多，比較著名的是Clerc提出的基于交換子的離散改造方案［11］。但分簇問題并非經典的TSP問題，本文在借鑒Clerc方法的基礎上，提出了針對分簇問題的DPSO模型。

首先本文定義了針對分簇問題的粒子結構:

圖1 本路由算法粒子結構示意圖

如圖1所示，粒子的維數n代表有n個傳感器節點，其中每一維里的數字代表每個節點的編號。m代表每個簇內都有相等的m個節點，這里m應為20(1/5%=20)。CH代表簇首(Cluster Head)假設i是n維粒子的坐標，如果i對20取余結果為1，則i代表的是簇首的坐標，否則為簇內節點坐標。

標準PSO按照以下兩個公式更新粒子的速度和位置:

其中xin=(xi1，xi2，…，xin)代表粒子 i的位置也就是上述粒子的結構，每個位置就是問題的一個解。vin=(vi1，vi2，…，vin)代表粒子 i的速度。pin=(pi1，…，pin)代表粒子 i的最好位置，pgn=(pg1，…，pgn)代表所有粒子的最好位置。C1是粒子個體學習因子，C2是群體學習因子，w是慣性權重因子。

根據文獻［11］，本文也將粒子速度定義為vi=swap(j，k)，即代表將粒子位置坐標j的節點編號與坐標k的節點編號進行交換，一個速度可能是若干個這樣的交換序列的集合。同時也更改了公式(4)和式(5)中的“+”，“—”和“* ”的定義。

(位置+速度):舊位置與速度“+”的結果為新位置。讓速度中的所有交換序列依次改變舊位置的節點編號。假設舊位置為(1，4，5，3，2)，速度為((1，2)，(3，5))，則新位置為(4，1，2，3，5)。

(位置—位置):兩個位置的“—”的結果為一個速度。假設p1為第一個位置，p2為第二個位置，p1－p2產生的v應滿足p2+v=p1。如上p1為(4，1，2，3，5)，p2 為(1，4，5，3，2)，則“—”的結果應為((1，2)，(3，5))。

(速度+速度):兩個速度的“+”的結果為新速度。即簡單將兩個速度的交換序列合并。設一個速度為((1，2)，(3，5))，另一個為((3，4))，新速度為((1，2)，(3，5)，(3，4))。

(因子*速度):因子與速度的“*”結果仍然為一速度，定義為速度中的每一個交換序列以因子的值為概率保留(因子都為一個小于1的實數)。

2．1．3 避免PSO的局部最優現象

粒子群算法在迭代過程中容易出現陷入局部最優的現象，本文采用線性慣性權重調整和變異策略來避免這種現象發生。

公式(4)中的w就是慣性權重，它是個重要的參數。較大的w具有較好的全局收斂能力，而較小的w則有較強的局部搜索能力。現在的慣性權重研究一般分為3類:固定慣性權重，線性慣性權重調整，非線性慣性權重調整。其中線性遞減的慣性權重調整策略迭代前期具有較好的全局搜索能力，后期收斂性也較好，但缺點是收斂速度慢［12］。本文采用線性遞減的慣性權重調整來避免陷入局部最優，同時結合啟發算法來提高收斂速度。調整公式如下:

本文還提出使用變異的策略來避免陷入局部最優即如果在粒子群算法迭代過程中判斷如果每個粒子隔一定輪數個體最優解沒有發生變化，并且該粒子位置和全局最優粒子位置的相似度在一定程度以上就使該粒子位置的某些維(即粒子編號)進行交換。本文中具體的做法是如果經過總迭代次數maxiter的10%輪后，如果某個粒子隔一定輪數個體最優解沒有發生變化，并且該粒子位置和全局最優粒子位置相似度在80%以上時，則在粒子位置中的每個簇中隨機選擇一維與當前的簇首所在的維交換即選擇本簇內其他節點當簇首。當然本來就是全局最優粒子不需要變異。這種變異策略可以使粒子在迭代過程中產生一定的概率找到比當前全局最優解更好的解，避免陷入局部最優。

2．1．4 啟發式算法

本文提出兩種啟發式算法來提高粒子群迭代計算最優簇首的效率。

(1)交換簇之間簇內成員的位置

如果在PSO迭代過程中發現某粒子位置中某個簇內節點相比自己當前的簇首更靠近另外某個簇首，那這樣的簇內節點應該被交換到合適的簇中去。

(2)調整簇首位置

使用兩種啟發式算法的策略是每經過總迭代次數maxiter的5%輪數后全局最優解，隨機選擇一半粒子依次使用啟發式算法(1)和算法(2)對粒子結構進行指導調整。

2．1．5 最優簇首計算的流程

整個最優簇首的計算階段的過程如下:

(1)隨機初始化粒子群中每個粒子的位置和速度。由當前粒子位置根據公式(3)計算每個粒子的適應度值，并根據最優適應度值得出全局最優粒子，個體最好粒子初始化為每個粒子的初始位置。

(2)接下來開始粒子群算法的迭代過程，更新迭代輪數。每個粒子根據公式(4)和(5)計算新的位置和速度。

(3)每個粒子根據更新的位置計算各自的適應度函數值，得出最優適應度值。如果新的個體適應度值比個體歷史最優適應度值更好，更新個體最優粒子位置。如果新的最優適應度值比歷史最優適應度值更好則更新最優粒子位置。

(4)判斷迭代輪數，如果達到maxiter的5%則隨機對一半粒子運用兩種啟發式算法，然后轉第(5)步。否則直接轉第(5)步。

(5)判斷每個粒子是否連續maxiter的10%輪個體最優解未發生變化，若是則對該粒子進行變異，然后轉第(6)步，否則直接轉第(6)步。

(6)判斷是否達到迭代最大輪數，若是則結束迭代，否則更新慣性權值然后轉第(2)步繼續迭代。

2．2 計算簇首與基站之間多跳路徑

LEACH協議的另外一個嚴重的缺點就是簇首和基站之間都是單跳的，每個簇首無論距離基站多遠，簇首都將收集到的數據直接發給基站。

下面先來看一下無線傳感網絡的傳輸能量模型:

在文獻［8］中，王國芳等人提出建立包括所有簇首和基站在內的最小生成樹來減少LEACH中簇首與基站單跳通信消耗的能量。但是最小生成樹的目的是使圖上各點連通且使這棵生成樹的權值總和最小，而本文認為計算每個簇首到基站的最小能量代價更符合改進簇首與基站單跳傳輸能量消耗過大的缺點這個目標。且在文獻［14］中，過文亮用理論和實驗證明了以能量傳輸代價為權值的最段路徑算法比最小生成樹的方法更節省能量。文獻［14］將此算法用于LEACH協議中簇內各節點到簇首的多跳路徑。文獻［14］主要考慮LEACH的分簇不均勻，有些簇內節點到簇首距離非常遠，于是考慮在簇內采用多跳傳輸，但這樣將增加數據傳輸的時延。本文由于采用了基于群智能算法對選舉簇首經過改造后，簇變的很均勻，簇內節點到簇首距離相對比較小，然而仍然存在簇首距離基站過大的情況，因此本文在簇首與基站之間運用此算法建立多跳路徑。

本文以下面公式作為最短路徑計算時的權值:

2．3 局部簇首更新機制

和LEACH協議多次進行簇首選舉不同，本文提出只由基站進行一次簇首選舉出最好位置的簇首，在后面輪次中不再進行全局簇首選舉，而通過節點自感知剩余能量局部更新簇首從而進一步節省能量。具體過程如下:在傳輸數據給簇首時，簇內節點都會捎帶一個剩余能量信息。簇首會將其簇內節點當前剩余能量記錄下來，同時簇首檢查自己的剩余能量，當剩余能量低于初始能量的10%時，簇首選出本簇內剩余能量最多的簇內節點，讓它成為新的簇首。在本次數據傳輸給基站時將這個新節點ID報告給基站。然后由基站來通知該簇內節點新的簇首信息以及向多跳簇首間的相關簇首(指老簇首的上跳和下跳簇首)報告新簇首信息。可以看到基于能量感應機制的局部簇首更新機制基本不需要耗費額外的能量，大部分廣播新簇首相關信息耗費的能量都由基站來完成，這樣相比LEACH的全局更新簇首機制可以大大節省能量。當然付出的代價是需要記錄簇內節點的剩余能量信息。

2．4 路由算法的整體描述

DPSO—CR和LEACH協議一樣，也分為簇首選舉階段和數據傳輸階段。

在簇首選舉階段首先由所有傳感器節點向基站報告位置信息，由基站根據所有節點的位置信息來運行改造的DPSO算法計算出全局最優簇首。這個過程前面已經詳細說明，這里不再贅述。然后基站再根據簇首運行以能量代價為權值計算簇首到基站的多跳路徑。然后基站將廣播它的計算結果，包括簇首ID及位置(每個節點都有自己預先設置的ID)，以及簇首通信的上一跳和下一跳信息。每個節點收到自己的身份，簇內節點記錄各自的簇首ID。簇首節點記錄它的簇成員ID以及上下跳簇首ID以及位置，然后就可以進入數據傳輸階段。

在數據傳輸階段，也和LEACH協議一樣，簇內節點將數據發送給各自的簇首，簇首收集所有簇內節點的數據后將數據經過簇首間的多跳路徑傳送給基站。當全部簇內節點都死亡只剩簇首節點時，簇首直接感知數據并將采集的數據傳給簇首。

3 仿真實驗分析

本文以MATLAB為仿真工具，對LEACH協議和DPSO—CR算法從分簇效果和生命周期兩方面進行比較。

首先介紹實驗的場景:100個傳感器節點隨機地分布在一個200 m為邊長的正方形區域。基站位于正方形的正中心且能量無限。

3．1 分簇效果的比較

這里比較LEACH協議和DPSO—CR的分簇效果。LEACH協議和DPSO—CR使用的節點位置都一樣。改造的DPSO的參數如下:最大迭代次數maxiter為1000輪，初始慣性權重，迭代結束的慣性權重，個體學習因子 C1=0．2，群體學習因子C2=0．2，在以后的迭代過程中慣性權重w線性遞減，且始終保持C1=C2并且C1+C2+w=1。而LEACH協議中期望簇首概率P(即K/N)=0．05。

圖2顯示了運行LEACH協議的分簇效果。相同圖形代表同個簇，某個簇當中下三角形代表簇首節點，其他圍繞簇首的相同圖形代表簇內節點。可以看出，雖然期望簇頭個數為5個，但由于LEACH依照概率選簇頭的機制導致簇頭個數可能少于5個;簇內成員個數嚴重不均衡，簇首和簇內各節點的距離可能很大;簇首位置可能非常不合理。

圖2 LEACH分簇效果(期望簇首個數為5)

圖3顯示同樣位置的節點分布運行DPSO—CR的分簇效果，可以看出DPSO—CR的分簇效果明顯要比LEACH協議好。簇首均勻地分布在整個區域，且簇內節點個數都一樣，除了節點隨機布撒比較稀疏的區域外簇內節點都比較緊密地圍繞在簇首周圍，沒有出現簇首與簇內節點距離過大的情況。

圖3 本文路由算法分簇效果

這里比較LEACH協議和DPSO—CR算法的適應度函數(公式3)的值，可以對兩種算法的分簇效果有更直觀的認識。公式3分成f1和f2，其中

表1 LEACH和DPSO—CR的適應度函數值比較

上表數據是相同分布的傳感器節點連續各運行3次LEACH協議和DPSO—CR適應度函數的平均值。從表中可以看出，無論是f1的值還是f2的值，LEACH協議的值都比DPSO—CR大好幾倍，總適應度函數值LEACH協議是DPSO—CR的20倍左右。這說明LEACH協議中簇首和簇內節點不但距離總和過大而且距離大小非常不均勻，這將大大縮短網絡生命周期，這可以從生命周期比較中看出。

3．2 網絡生命周期和能量消耗比較

這里通過模擬傳感器節點周期性的數據傳輸來比較LEACH協議和DPSO—CR的生命周期和能量消耗情況。每個傳感器節點初始能量均為0．5 J，按公式(7)和公式(8)的能量傳輸模型計算能量消耗，其中參數為 Eelec=50 nJ/bit，Efs=10 pJ/(bit*m2)，Emp=0．0013 pJ/(bit*m4)，d0=87 m。實驗比較兩個協議中從分簇到數據傳輸的能量消耗情況。實驗中分兩種控制信息包和數據包兩種，控制信息包為分簇階段信息傳遞的數據包，大小為100 bit，數據包為傳輸數據所用的數據包，大小為4 000 bit。數據傳輸階段按輪進行，兩個協議中都規定每輪中每個簇內節點采集一個數據包，并發送給它的簇首，簇首收集本簇內所有簇內節點的數據包，并且按照兩種協議中單跳或多跳方式傳給基站。

其中橫軸是實驗中規定的輪數，縱軸是仍然存活的節點數量。下面表2對圖4中的關鍵數據進行了描述。

表2 LEACH和DPSO—CR的網絡生命周期數據比較

圖4 網絡生命周期比較

從圖4和表2中可以看到，LEACH協議第一個節點死亡的輪數是80輪，而DPSO—CR第一個節點死亡輪數是243輪，DPSO—CR比LEACH協議晚了兩倍左右的時間。LEACH協議中最后一個節點死亡的輪數605輪，而DPSO—CR最后一個節點死亡的輪數是1008輪。網絡每輪平均能耗也是個重要的指標，它反映了路由算法的能量有效性，可以看到LEACH算法每個節點每輪的能耗是DPSO—CR的1．7倍，這正是本文提出的三種節省能量機制的效果體現。

圖5中顯示了整個網絡總能耗情況。縱軸代表網絡總能量50 J(0．5 J×100)，橫軸代表實驗輪數。可見，從整個網絡能量消耗來看，DPSO—CR與LEACH協議相比大大節省了能量。文獻［13］先LEACH分簇然后通過粒子群局部優化簇首的方法在相近的實驗條件下只比LEACH延長20%左右的生命周期，可見本文提出的路由算法要優于文獻［13］的方法。

圖5 網絡總能耗比較

4 總結和展望

本文針對LEACH協議中存在的三個使能量消耗過大的機制，提出了基于離散粒子群算法的智能無線傳感網絡分簇路由算法DPSO—CR。該算法主要包含三種新的機制來分別改進LEACH協議中存在的三個問題。其中基于離散粒子群算法計算全局最優位置的簇首是本文的核心和主要創新點，這個機制能大大改進LEACH協議分簇不均勻的缺點。在簇首間基于能耗代價的最短路徑算法也改善了LEACH協議簇首和基站單跳通信能耗過大的缺點。基于能量自感應的局部簇首更新機制通過將廣播消息所耗費的能量轉嫁到基站上的方法又進一步延長了網絡的生命周期。

當然DPSO—CR算法是有一定代價和前提條件的。首先計算全局最優簇首需要節點的位置信息，這要求傳感器節點具有GPS定位功能或者先通過無線傳感網絡定位算法計算出每個節點相對于基站的位置。局部簇首更新機制也需要付出一定的節點存儲代價。但節能是無線傳感網絡的首要考慮因素，通過一定的代價來延長網絡的生命周期還是很有必要的。

接下來的工作是要進一步提高全局最優簇首的精度，因為粒子群算法不保證能找到全局最優解，這還需要結合智能算法研究領域來進一步深入研究。另外可以結合其他新型智能算法來研究簇首間的多跳路徑，比如蟻群算法。

［1］ 孫利民，李建中，陳渝等．無線傳感器網絡［M］．北京:清華大學出版社，2005．

［2］ 胡鋼，謝冬梅，吳元忠．無線傳感器網絡路由協議LEACH的研究與改進［J］．傳感技術學報．2007，20(6):1391 －1396．

［3］ Kennedy J，Eberhart R．Particle Swarm Optimiaztion［C］//Proceeding of The IEEE International Conference on Neural Networks．Piscataway，NJ:IEEE Service Center，pp 1942 －1948，1995．

［4］ Coello C A C，Pulido G T，Lechuga MS M S．Handling multiple objectives with particle swarm optimization［C］//IEEE Transactions on Evolutionary Computation，2004，8(3):256 －279．

［5］ Wachowiak，M．P．，Smolikova，R．，Zheng，Y．F．，Zurada，J．M．，and Elmaghraby A．S．:An approach to multimodal biomedical image registration utilizing particle swarm optimization［J］．IEEE Trans．Evol．Comput．，2004，8(3):289 －301．

［6］ Fukuyama，Y．，Yoshida，H．:A Particle Swarm Optimization for Reactive Power and Voltage Control in Electric Power Systems［C］//Proc．Congress on Evolutionary Computation，Seoul，Korea．Piscataway，NJ:IEEE Service Center，2001:87 －93．

［7］ Handy M J，Haase M，Timmermann D．Low Energy Adaptive Clustering Hierarchy with Deterministic Cluster-Head Selection．2002．

［8］ 王國芳，李臘元，李春林，劉會靜．無線傳感器網絡中基于能量約束的簇首多跳算法［J］．傳感技術學報，2009，22(7):997 －1001．

［9］ Wendi B Heinzelman，Anant ha P Chandrakasan，Hari Bal2 akrishnan．An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］．IEEE Transactions on Wireless Communications，2002，1(4):660 －670．

［10］張偉華，李臘元，張留敏，王選政．無線傳感器網絡LEACH協議能耗均衡改進［J］．傳感技術學報，2008，21(11):1918 －1922．

［11］ M．Clerc，in:Discrete Particle Swarm Optimization，illustrated by the Traveling Salesman Problem New Optimization Techniques in Engineering［M］．Springer，2004:219 －239．

［12］田雨波，朱人杰，薛權祥．粒子群優化算法中慣性權重的研究進展［J］．計算機工程與應用，2008，44(23):39 －41．

［13］梁英，于海斌，曾鵬．應用PSO優化基于分簇的無線傳感器網絡路由協議［J］．控制與決策，2006，21(4):453 －457．

［14］過文亮．無線傳感器網絡節能路由協議研究［D］，上海大學碩士論文，2009．

［15］ Wairagu G．Richard，Extending Leach Routing Algorithm for Wireless Sensor Networks［D］，in Msc．Thesis，Makerere University，March，2009．