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

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

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

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

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

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

1 LEACH協(xié)議及其改進

1．1 LEACH協(xié)議描述和分析

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

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

其中n表示某個傳感器節(jié)點的編號，N是傳感器節(jié)點的個數(shù)，K是期望產(chǎn)生的簇頭個數(shù)，r是選舉簇首的輪數(shù)，Gr是最近的N/K輪中還沒當(dāng)選過簇首的節(jié)點集合。

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

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

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

1．2 對LEACH協(xié)議的改進

針對LEACH協(xié)議存在的問題，國內(nèi)外學(xué)者也提出了不少LEACH的改進策略。

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

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

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

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

2 本文的協(xié)議描述

本文算法假設(shè)節(jié)點能量有限且能感知剩余能量，并且可以根據(jù)發(fā)送距離長短調(diào)整發(fā)射的功率。另外本文假設(shè)傳感器節(jié)點擁有GPS定位功能能獲取自己相對基站的位置信息?；灸芰繜o限，計算最佳簇首位置和簇首到基站的多跳路徑都由基站來計算。

2．1 計算最佳簇首位置

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

2．1．1 粒子群算法的適應(yīng)度函數(shù)

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

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

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

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

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

首先本文定義了針對分簇問題的粒子結(jié)構(gòu):

圖1 本路由算法粒子結(jié)構(gòu)示意圖

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

標(biāo)準(zhǔn)PSO按照以下兩個公式更新粒子的速度和位置:

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

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

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

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

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

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

2．1．3 避免PSO的局部最優(yōu)現(xiàn)象

粒子群算法在迭代過程中容易出現(xiàn)陷入局部最優(yōu)的現(xiàn)象，本文采用線性慣性權(quán)重調(diào)整和變異策略來避免這種現(xiàn)象發(fā)生。

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

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

2．1．4 啟發(fā)式算法

本文提出兩種啟發(fā)式算法來提高粒子群迭代計算最優(yōu)簇首的效率。

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

如果在PSO迭代過程中發(fā)現(xiàn)某粒子位置中某個簇內(nèi)節(jié)點相比自己當(dāng)前的簇首更靠近另外某個簇首，那這樣的簇內(nèi)節(jié)點應(yīng)該被交換到合適的簇中去。

(2)調(diào)整簇首位置

使用兩種啟發(fā)式算法的策略是每經(jīng)過總迭代次數(shù)maxiter的5%輪數(shù)后全局最優(yōu)解，隨機選擇一半粒子依次使用啟發(fā)式算法(1)和算法(2)對粒子結(jié)構(gòu)進行指導(dǎo)調(diào)整。

2．1．5 最優(yōu)簇首計算的流程

整個最優(yōu)簇首的計算階段的過程如下:

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

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

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

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

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

(6)判斷是否達到迭代最大輪數(shù)，若是則結(jié)束迭代，否則更新慣性權(quán)值然后轉(zhuǎn)第(2)步繼續(xù)迭代。

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

LEACH協(xié)議的另外一個嚴(yán)重的缺點就是簇首和基站之間都是單跳的，每個簇首無論距離基站多遠，簇首都將收集到的數(shù)據(jù)直接發(fā)給基站。

下面先來看一下無線傳感網(wǎng)絡(luò)的傳輸能量模型:

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

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

2．3 局部簇首更新機制

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

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

DPSO—CR和LEACH協(xié)議一樣，也分為簇首選舉階段和數(shù)據(jù)傳輸階段。

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

在數(shù)據(jù)傳輸階段，也和LEACH協(xié)議一樣，簇內(nèi)節(jié)點將數(shù)據(jù)發(fā)送給各自的簇首，簇首收集所有簇內(nèi)節(jié)點的數(shù)據(jù)后將數(shù)據(jù)經(jīng)過簇首間的多跳路徑傳送給基站。當(dāng)全部簇內(nèi)節(jié)點都死亡只剩簇首節(jié)點時，簇首直接感知數(shù)據(jù)并將采集的數(shù)據(jù)傳給簇首。

3 仿真實驗分析

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

首先介紹實驗的場景:100個傳感器節(jié)點隨機地分布在一個200 m為邊長的正方形區(qū)域?；疚挥谡叫蔚恼行那夷芰繜o限。

3．1 分簇效果的比較

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

圖2顯示了運行LEACH協(xié)議的分簇效果。相同圖形代表同個簇，某個簇當(dāng)中下三角形代表簇首節(jié)點，其他圍繞簇首的相同圖形代表簇內(nèi)節(jié)點?？梢钥闯觯m然期望簇頭個數(shù)為5個，但由于LEACH依照概率選簇頭的機制導(dǎo)致簇頭個數(shù)可能少于5個;簇內(nèi)成員個數(shù)嚴(yán)重不均衡，簇首和簇內(nèi)各節(jié)點的距離可能很大;簇首位置可能非常不合理。

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

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

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

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

表1 LEACH和DPSO—CR的適應(yīng)度函數(shù)值比較

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

3．2 網(wǎng)絡(luò)生命周期和能量消耗比較

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

其中橫軸是實驗中規(guī)定的輪數(shù)，縱軸是仍然存活的節(jié)點數(shù)量。下面表2對圖4中的關(guān)鍵數(shù)據(jù)進行了描述。

表2 LEACH和DPSO—CR的網(wǎng)絡(luò)生命周期數(shù)據(jù)比較

圖4 網(wǎng)絡(luò)生命周期比較

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

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

圖5 網(wǎng)絡(luò)總能耗比較

4 總結(jié)和展望

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

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

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

［1］ 孫利民，李建中，陳渝等．無線傳感器網(wǎng)絡(luò)［M］．北京:清華大學(xué)出版社，2005．

［2］ 胡鋼，謝冬梅，吳元忠．無線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的研究與改進［J］．傳感技術(shù)學(xué)報．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］ 王國芳，李臘元，李春林，劉會靜．無線傳感器網(wǎng)絡(luò)中基于能量約束的簇首多跳算法［J］．傳感技術(shù)學(xué)報，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］張偉華，李臘元，張留敏，王選政．無線傳感器網(wǎng)絡(luò)LEACH協(xié)議能耗均衡改進［J］．傳感技術(shù)學(xué)報，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］田雨波，朱人杰，薛權(quán)祥．粒子群優(yōu)化算法中慣性權(quán)重的研究進展［J］．計算機工程與應(yīng)用，2008，44(23):39 －41．

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

［14］過文亮．無線傳感器網(wǎng)絡(luò)節(jié)能路由協(xié)議研究［D］，上海大學(xué)碩士論文，2009．

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