陳 樹(shù)，韓 進(jìn)，蔣 偉

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫 214122)

1 概述

無(wú)線傳感器網(wǎng)絡(luò)理論研究模型大都基于高節(jié)點(diǎn)冗余度的網(wǎng)絡(luò)，但在很多應(yīng)用場(chǎng)景中，部署高冗余度的無(wú)線傳感網(wǎng)絡(luò)是不現(xiàn)實(shí)的。通常用于工業(yè)生產(chǎn)的無(wú)線傳感網(wǎng)絡(luò)節(jié)點(diǎn)價(jià)格比較高，不會(huì)有大量的冗余節(jié)點(diǎn)，這就造成了整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的低冗余度。這種低冗余度要求整個(gè)系統(tǒng)數(shù)據(jù)傳輸?shù)哪芎木鶆蚍植己蛡鞲泄?jié)點(diǎn)之間的能耗均勻，避免出現(xiàn)節(jié)點(diǎn)早衰現(xiàn)象。作為傳感器網(wǎng)絡(luò)數(shù)據(jù)傳輸路徑選擇的路由策略對(duì)均衡節(jié)點(diǎn)能耗負(fù)載、節(jié)省通信能量、延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間起決定作用［1］。但常規(guī)的路由協(xié)議不能簡(jiǎn)單直接地應(yīng)用到低冗余度的網(wǎng)絡(luò)中，必須選擇基本的路由算法并進(jìn)行適當(dāng)?shù)匦薷?，以符合?shí)際應(yīng)用場(chǎng)景。通過(guò)對(duì)現(xiàn)有無(wú)線傳感器網(wǎng)絡(luò)路由算法的研究，發(fā)現(xiàn)分簇路由協(xié)議技術(shù)能顯著降低數(shù)據(jù)延遲，提高能量利用率，有效延長(zhǎng)網(wǎng)絡(luò)生命周期，相比之下具有更好的適用性。目前，研究者已就如何延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)生存時(shí)間提出多種分簇路由協(xié)議。例如，Heinzelman 等人提出了經(jīng)典的低功耗自適應(yīng)分簇協(xié)議LEACH［2］，設(shè)計(jì)思想是隨機(jī)按“輪”的形式以一定概率周期性的循環(huán)選擇簇首節(jié)點(diǎn)，即讓節(jié)點(diǎn)輪流擔(dān)任簇首，從而將網(wǎng)絡(luò)中的能量負(fù)載平均分配到每個(gè)傳感器節(jié)點(diǎn)，延長(zhǎng)網(wǎng)絡(luò)生存周期。但此算法是隨機(jī)選取簇頭，難以保證每輪的簇頭數(shù)目一致和簇頭在網(wǎng)絡(luò)中均勻分布，無(wú)法確保整個(gè)網(wǎng)絡(luò)能耗的均衡性，可能會(huì)出現(xiàn)節(jié)點(diǎn)成堆死亡的情況。之后Heinzelman 等人又提出了LEACH-C 算法［3］，該算法雖然提高了成簇質(zhì)量，采用多跳的簇間路由機(jī)制，但是其網(wǎng)絡(luò)流量、時(shí)間延遲及信號(hào)干擾的概率會(huì)增加，成簇開(kāi)銷也增大，存在嚴(yán)重“熱區(qū)”問(wèn)題。文獻(xiàn)［4］提出了一種EECS 的非均勻分簇算法，該算法通過(guò)選舉得到簇首節(jié)點(diǎn)，剩余節(jié)點(diǎn)根據(jù)通信代價(jià)公式，選擇加入到代價(jià)最小的簇中，從而構(gòu)造大小不同的簇以均衡簇首負(fù)載，然后簇首以單跳的方式與基站通信。之后文獻(xiàn)［5］又提出了一種新的非均勻分簇路由算法EEUC，構(gòu)造不同規(guī)模的簇來(lái)改善多跳路由的“熱區(qū)”問(wèn)題。但上述2 種算法都存在簇首數(shù)目隨機(jī)和簇間傳輸方式單一的問(wèn)題，造成簇首能耗不易控制。

對(duì)于低冗余度網(wǎng)絡(luò)，任何節(jié)點(diǎn)的過(guò)早死亡、能耗不均和不穩(wěn)定因素都會(huì)給工業(yè)生產(chǎn)過(guò)程造成較大影響。由于上述各種分簇協(xié)議均存在一些問(wèn)題，因此不能直接應(yīng)用到低冗余度的網(wǎng)絡(luò)。針對(duì)該問(wèn)題，本文提出一種基于粒子群優(yōu)化(Particle Swarm Optimization，PSO)算法和最短路由樹(shù)的分簇路由算法。該算法在EEUC 協(xié)議基礎(chǔ)上引入粒子群算法優(yōu)化非均勻分簇過(guò)程，并將所有簇首節(jié)點(diǎn)以基站為根構(gòu)成最短路由樹(shù)，樹(shù)內(nèi)節(jié)點(diǎn)通過(guò)多跳路由將數(shù)據(jù)傳輸給基站。

2 網(wǎng)絡(luò)模型

2.1 前提假設(shè)

假設(shè)無(wú)線傳感器網(wǎng)絡(luò)的特性如下:

(1)節(jié)點(diǎn)均勻部署在方形網(wǎng)絡(luò)中，且位置不再變動(dòng);基站位于網(wǎng)絡(luò)空間外側(cè)，其能量和計(jì)算能力不受限制，傳輸范圍覆蓋整個(gè)網(wǎng)絡(luò)。

(2)簇首節(jié)點(diǎn)和普通節(jié)點(diǎn)的ID 號(hào)均唯一，且簇首節(jié)點(diǎn)具有數(shù)據(jù)融合和轉(zhuǎn)發(fā)能力。

(3)節(jié)點(diǎn)位置坐標(biāo)已事先測(cè)得，發(fā)射功率可根據(jù)接收節(jié)點(diǎn)的距離自動(dòng)調(diào)節(jié)。

(4)每個(gè)普通節(jié)點(diǎn)最大通信半徑設(shè)為Rmax，簇首節(jié)點(diǎn)的競(jìng)爭(zhēng)半徑設(shè)為Rc。

(5)算法無(wú)需周期性地從普通節(jié)點(diǎn)中選取簇首節(jié)點(diǎn)，由控制中心根據(jù)選簇機(jī)制一次性選取固定數(shù)目的簇首節(jié)點(diǎn)，最后可由工作人員根據(jù)選好的最優(yōu)簇首組合的位置部署簇首節(jié)點(diǎn)。

2.2 能量模型

無(wú)線傳感器網(wǎng)絡(luò)的能耗大部分來(lái)自通信，通信所消耗的能量比感知和計(jì)算所消耗的能量要大得多，本文不考慮節(jié)點(diǎn)運(yùn)算和存儲(chǔ)所消耗的能量，參考文獻(xiàn)［2］得到本文算法的無(wú)線通信能耗模型，發(fā)送和接收l(shuí) 字節(jié)數(shù)據(jù)的消耗能量分別為:

其中，l 表示收發(fā)的字節(jié)數(shù);d 表示通信距離;在文獻(xiàn)［5］中若通信距離小于閾值d0，功率放大損耗采用自由空間模型;若通信距離不小于閾值d0時(shí)，采用多路徑衰減模型;Eelec表示收發(fā)電路的基本功耗系數(shù);Efs，Eamp表示功率放大電路的功耗系數(shù)。

3 本文算法

基于粒子群和最短路由樹(shù)的非均勻分簇路由算法采用集中式控制策略［6］，簇首選舉和最短路由樹(shù)建立過(guò)程的能量開(kāi)銷都由能量不受限制的基站承擔(dān)執(zhí)行，從而減少網(wǎng)絡(luò)傳感節(jié)點(diǎn)的能耗，較好地適應(yīng)了低冗余度無(wú)線傳感網(wǎng)絡(luò)。整個(gè)算法過(guò)程分為3 個(gè)階段:粒子群優(yōu)化的非均勻分簇階段;基站和簇首節(jié)點(diǎn)之間建立最短路由樹(shù)階段;數(shù)據(jù)傳輸和路由更新階段。

3.1 非均勻分簇

非均勻分簇階段分為簇首選取和普通節(jié)點(diǎn)加入簇，而簇首選取引入粒子群優(yōu)化算法完成非均勻分簇。PSO 算法具有收斂速度快、算法簡(jiǎn)單和易于實(shí)現(xiàn)等優(yōu)點(diǎn)，在求解單目標(biāo)優(yōu)化問(wèn)題上是一種有效的方法［7］，將其引入簇首選取階段可以減少非均勻分簇算法的復(fù)雜度。

首先，為達(dá)到非均勻分簇效果，分簇時(shí)引入大小不同的競(jìng)爭(zhēng)半徑，如式(3)所示，競(jìng)爭(zhēng)半徑是根據(jù)簇首到基站距離計(jì)算得到，使得遠(yuǎn)離基站的簇首數(shù)量少，成簇規(guī)模大;靠近基站的簇首數(shù)量多，成簇規(guī)模?。?］。

其中，λ 屬于［0，1］的常數(shù);Dmax和Dmin分別表示簇首節(jié)點(diǎn)和基站之間距離的最大值和最小值;d(Cm，BS)表示簇首節(jié)點(diǎn)Cm到基站的距離;R0為競(jìng)爭(zhēng)半徑最大值。

其次，在PSO 算法優(yōu)化分簇過(guò)程時(shí)，適應(yīng)值函數(shù)設(shè)定是否理想直接決定最終選取的簇首優(yōu)劣。根據(jù)本文研究背景，算法將簇內(nèi)通信代價(jià)和簇首位置作為適應(yīng)值函數(shù)的影響因子。因此，PSO 算法的適應(yīng)值函數(shù)可構(gòu)造為:

其中，f1(pi)為成簇緊湊性評(píng)價(jià)因子，等于普通節(jié)點(diǎn)至其簇首的最大平均歐式距離;Cpi，m表示粒子pi中簇首Cm所屬普通節(jié)點(diǎn)數(shù)目;f2(pi)為所有簇首包含節(jié)點(diǎn)數(shù)之和與節(jié)點(diǎn)總數(shù)比值的倒數(shù)，表示簇首節(jié)點(diǎn)覆蓋范圍的大小;α 和β 屬于［0，1］且α+β=1，通過(guò)調(diào)節(jié)f1(pi)和f2(pi)在適應(yīng)值函數(shù)中所占比例，從而優(yōu)化簇分布及簇選擇。根據(jù)適應(yīng)值函數(shù)的定義，本文PSO 優(yōu)化分簇過(guò)程可以簡(jiǎn)單描述為:在假定的網(wǎng)絡(luò)搜索空間中，找到一個(gè)最優(yōu)簇首組合(M 個(gè)簇首)，使得適應(yīng)函數(shù)值最小。PSO 優(yōu)化分簇算法基本步驟如下:

(1)初始化Q 個(gè)粒子，每個(gè)粒子包含M 個(gè)簇首節(jié)點(diǎn)，代表一種可能的分簇方式。

(2)初始化每個(gè)粒子pi:

1)初始化粒子pi的位置，即從［0，L］內(nèi)隨機(jī)產(chǎn)生一個(gè)實(shí)數(shù)作為每個(gè)粒子位置向量中每一維的值。

2)初始化粒子pi的速度，即從［-V，V］內(nèi)隨機(jī)產(chǎn)生一個(gè)實(shí)數(shù)作為每個(gè)粒子速度向量中每一維的值。

(3)計(jì)算每個(gè)粒子的適應(yīng)函數(shù)值:

1)對(duì)于每個(gè)普通節(jié)點(diǎn)ci(i=1，2，…，N)，計(jì)算其到所有簇首節(jié)點(diǎn)Cm(m=1，2，…，M)的距離d(ci，CHpi，m);根據(jù)式(3)計(jì)算每個(gè)簇首的競(jìng)爭(zhēng)半徑，并計(jì)算其競(jìng)爭(zhēng)半徑范圍內(nèi)所包含的的節(jié)點(diǎn)數(shù)Cpi，m。

2)運(yùn)用式(4)～式(6)計(jì)算粒子的適應(yīng)函數(shù)值fit(pi)。

(4)確定每個(gè)粒子的局部最優(yōu)解和種群最優(yōu)解。

(5)根據(jù)文獻(xiàn)［7］中的粒子群算法基本公式更新每個(gè)粒子的位置和速度。

(6)重復(fù)步驟(3)～步驟(5)，直至達(dá)到最大迭代次數(shù)。

最后，當(dāng)基站從上位機(jī)得到最優(yōu)簇首組合及簇成員信息后，廣播非均勻分簇結(jié)果給每個(gè)節(jié)點(diǎn)，普通節(jié)點(diǎn)加入簇，組建網(wǎng)絡(luò)的分簇階段基本完成。

3.2 最短路由樹(shù)的建立

本文采用Dijkstra 算法建立基站和簇首之間的最短路由樹(shù)。Dijkstra 算法是解決關(guān)于帶權(quán)有向圖的最短路徑問(wèn)題的一種貪心算法，它要逐個(gè)地找出從源節(jié)點(diǎn)出發(fā)到所有其他節(jié)點(diǎn)的最短路徑，算法的本質(zhì)特征是能夠確定路徑順序，按照加權(quán)長(zhǎng)度順序首先找出最短路徑，直至最后找出從源節(jié)點(diǎn)到所有節(jié)點(diǎn)的最短路徑［9］。

為了均衡簇間多跳傳輸?shù)哪芎?，將?jié)點(diǎn)的傳輸能耗、剩余能量和成簇規(guī)模作為路由樹(shù)邊的權(quán)值公式影響因子，公式如式(7)所示。

其中，W(i，j)表示圖中連接相鄰簇首節(jié)點(diǎn)i 和節(jié)點(diǎn)j的邊的權(quán)值;Etx(l，d)表示節(jié)點(diǎn)j 向節(jié)點(diǎn)i 發(fā)送l 比特?cái)?shù)據(jù)所消耗的能量，其大小可根據(jù)式(1)計(jì)算得到;Re(i)，Re(j)分別表示節(jié)點(diǎn)i 和節(jié)點(diǎn)j 的剩余能量;Cn(i)和N 分別表示節(jié)點(diǎn)i 的簇成員數(shù)和網(wǎng)絡(luò)普通節(jié)點(diǎn)總數(shù);ε 和θ 是屬于［0，1］的常數(shù);ω 為公式歸一化常數(shù)。

根據(jù)前提假設(shè)，網(wǎng)絡(luò)中簇首一旦選定，其拓?fù)浣Y(jié)構(gòu)不再改變，因此，在每輪采集周期中，所有簇首節(jié)點(diǎn)間的拓?fù)浣Y(jié)構(gòu)可用一個(gè)帶權(quán)值的有向連通圖G=(V，E)表示，其中，V 表示網(wǎng)絡(luò)中所有的簇首節(jié)點(diǎn)(包括基站)的集合;E 表示圖中所有邊的集合。本文為了便于簇間多跳路徑的建立，根據(jù)簇首到基站的距離將所有簇首節(jié)點(diǎn)分屬不同的層次，處于n 層的簇首和基站通信需要n -1 層的簇首節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，且簇首節(jié)點(diǎn)不對(duì)來(lái)自上一層的簇首數(shù)據(jù)包進(jìn)行融合處理，只是轉(zhuǎn)發(fā)給自己的下一跳簇首，這樣可以形成較好的樹(shù)型結(jié)構(gòu)［10］。假設(shè)源頂點(diǎn)到某個(gè)節(jié)點(diǎn)v的通信代價(jià)為D(v)，表示從源頂點(diǎn)到節(jié)點(diǎn)v 所經(jīng)過(guò)的整條鏈路權(quán)值之和。則利用Dijkstra 算法構(gòu)造最短路由樹(shù)的步驟如下:

(1)初始化。設(shè)網(wǎng)絡(luò)頂點(diǎn)集合為U，選擇基站為源頂點(diǎn)S0，并加入到集合U 中，此時(shí)U={S0}，對(duì)于所有不在U 中的節(jié)點(diǎn)v，有如下公式:

其中，W(s0，v)可根據(jù)式(7)計(jì)算得到;∞可以用一很大的數(shù)值代替，只要比樹(shù)中任何邊的權(quán)值大就行。

(2)從V-U 的集合中找到節(jié)點(diǎn)u，且其D(u)的值最小，然后將其加入到U 中。接著對(duì)所有其他V-U中的節(jié)點(diǎn)v，用{D(v)，D(u)+W(u，v)}中的較小的值去更新原有的D(v)值，即:

(3)重復(fù)步驟(2)，直至所有簇首節(jié)點(diǎn)都在U 中為止，即U=V。

最終建立完成以基站為根的最短路由樹(shù)。基站則根據(jù)最短路由樹(shù)計(jì)算出每個(gè)簇首節(jié)點(diǎn)的路由表信息并將其廣播給所有簇首節(jié)點(diǎn)，然后簇首節(jié)點(diǎn)可以按照路由表，將數(shù)據(jù)發(fā)送給各自的下一跳節(jié)點(diǎn)，最終將數(shù)據(jù)轉(zhuǎn)發(fā)給基站。網(wǎng)絡(luò)模型如圖1 所示。

圖1 最短路由樹(shù)網(wǎng)絡(luò)模型

3.3 數(shù)據(jù)傳輸和路由更新

數(shù)據(jù)傳輸主要分為簇內(nèi)傳輸和簇間傳輸2 個(gè)階段。簇內(nèi)傳輸時(shí)，節(jié)點(diǎn)按照時(shí)分多址(Time Division Multiple Address，TDMA)的方式將檢測(cè)數(shù)據(jù)傳輸給簇首節(jié)點(diǎn);簇間傳輸時(shí)，簇首節(jié)點(diǎn)根據(jù)已經(jīng)建立好的最短路由樹(shù)將融合好的數(shù)據(jù)傳輸給自己的父節(jié)點(diǎn)，然后經(jīng)過(guò)轉(zhuǎn)發(fā)，最終到達(dá)基站［11］。

簇間多跳傳輸階段，必須考慮某一條路徑中轉(zhuǎn)發(fā)節(jié)點(diǎn)能耗過(guò)快而提早死亡的情況。因此，在每一輪傳輸結(jié)束后，基站重新計(jì)算路由樹(shù)中各邊的權(quán)值，當(dāng)某條邊的權(quán)值高于設(shè)定的閾值時(shí)，則對(duì)最短路由樹(shù)進(jìn)行動(dòng)態(tài)更新。參考文獻(xiàn)［12］得到本文算法動(dòng)態(tài)路由更新的基本過(guò)程如下:

(1)網(wǎng)絡(luò)中某條邊的權(quán)值過(guò)高導(dǎo)致網(wǎng)絡(luò)路徑被割斷，原來(lái)的最短路由樹(shù)被分為了2 棵獨(dú)立的樹(shù)，此時(shí)需要變更路徑。

(2)將原來(lái)最短路由樹(shù)中到源頂點(diǎn)的最短路徑?jīng)]有改變的樹(shù)中節(jié)點(diǎn)構(gòu)成集合TN1，而被切斷的樹(shù)中的節(jié)點(diǎn)構(gòu)成集合TN2。

(3)將集合TN2 中的節(jié)點(diǎn)再按照上一節(jié)中Dijkstra 算法的基本思路逐個(gè)地加入到集合TN1 中，同時(shí)將對(duì)應(yīng)節(jié)點(diǎn)從TN2 中刪除，直到集合TN2為空。

最后便得到了動(dòng)態(tài)更新后的最短路由樹(shù)。利用此方法不需要重新計(jì)算生成整個(gè)網(wǎng)絡(luò)的最短路由樹(shù)，不但節(jié)省了計(jì)算時(shí)間，而且還避免了不必要的網(wǎng)絡(luò)能耗。

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

為評(píng)估本文算法在低冗余度的無(wú)線傳感器網(wǎng)絡(luò)中的可用性和有效性，筆者引入EECS 和EEUC 算法與之比較。仿真環(huán)境和具體參數(shù)如下:在100 ×100的方形區(qū)域均勻部署200 個(gè)傳感器節(jié)點(diǎn);控制包大小200 bit;數(shù)據(jù)包大小4 000 bit;節(jié)點(diǎn)初始能量總和100 J，簇首數(shù)目M=10，基站坐標(biāo)(50，125);λ=0.5，R0=70 m;ε=0.3，θ=0.5，ω=1 000。PSO 參數(shù)設(shè)置［7］:種群規(guī)模Q=50;學(xué)習(xí)因子c1=c2=2;慣性因子w=0.8;r1，r2 隨機(jī)給出;α=0.7，β=0.3;最大迭代次數(shù)為100。

將本文算法和EECS、EEUC 算法進(jìn)行比較后可知，EECS 算法為均衡節(jié)點(diǎn)能耗，將節(jié)點(diǎn)分成大小不同的簇，但是簇首與基站的通信采用簡(jiǎn)單的單跳機(jī)制，容易過(guò)快地消耗簇首能量，而導(dǎo)致整個(gè)網(wǎng)絡(luò)的生存周期變短。EEUC 算法則在非均勻分簇的基礎(chǔ)上，簇間采用多跳路由方式傳輸和轉(zhuǎn)發(fā)數(shù)據(jù)，所以消耗的能量更少，一定程度上延長(zhǎng)了網(wǎng)絡(luò)生命周期。不同于上述2 種算法，本文算法不僅在分簇階段引入粒子群算法優(yōu)化選簇過(guò)程，而且在數(shù)據(jù)傳輸和轉(zhuǎn)發(fā)階段，采用多跳路由并通過(guò)建立最短路由樹(shù)的形式尋求最優(yōu)路徑，以及動(dòng)態(tài)路由更新機(jī)制，使得能量消耗比其他算法要慢的多，顯著地延長(zhǎng)了網(wǎng)絡(luò)有效生命時(shí)間。

EEUS、EECS 和本文算法存活節(jié)點(diǎn)數(shù)隨著網(wǎng)絡(luò)生命時(shí)間的變化情況如圖2 所示。

圖2 網(wǎng)絡(luò)節(jié)點(diǎn)存活數(shù)量比較

可以看出，在相對(duì)有效的網(wǎng)絡(luò)生命時(shí)間里(存活節(jié)點(diǎn)數(shù)大于100)，EECS 和EEUC 算法分別在243 輪和345 輪時(shí)開(kāi)始出現(xiàn)第1 個(gè)節(jié)點(diǎn)的死亡，而本文算法將第1 個(gè)節(jié)點(diǎn)的死亡時(shí)間推遲到649 輪，這是因?yàn)楸疚乃惴ㄏ啾扔谄渌? 種算法有如下優(yōu)勢(shì):

(1)為了均衡網(wǎng)絡(luò)能耗，在選擇簇首時(shí)，利用PSO 算法選取最優(yōu)簇首組合分布信息，而EECS 和EEUC 的簇首數(shù)目都是隨機(jī)的，很容易造成能耗不均的問(wèn)題。

(2)通過(guò)在基站與簇首之間建立最短路由樹(shù)的形式尋找最優(yōu)路徑以及采用動(dòng)態(tài)更新路由機(jī)制，減少了多跳傳輸?shù)哪芎模行У匮娱L(zhǎng)了網(wǎng)絡(luò)生命周期。

(3)根據(jù)低冗余度WSN 的特點(diǎn)，本文算法在WSN 初始能量相同的情況下，采用簇首和普通節(jié)點(diǎn)能量差異化分配機(jī)制，使得簇首節(jié)點(diǎn)的初始能量略高于普通節(jié)點(diǎn)的初始能量，這樣可以延長(zhǎng)固定簇首生命時(shí)間，保證網(wǎng)絡(luò)有效運(yùn)行。

EEUS、EECS 和本文算法前100 輪采集周期各個(gè)協(xié)議簇首平均能耗變化如圖3 所示?？梢钥闯觯珽ECS 算法的簇首平均能耗處于偏高的位置振蕩，原因是EECS 算法中所有簇首采用單跳方式與基站通信，比EEUC 算法和本文算法的簇間多跳傳輸方式要消耗更多的能量。而EECS 和EEUC 算法簇首平均能耗出現(xiàn)不穩(wěn)定的振蕩現(xiàn)象，則是由于2 種算法在選擇簇首時(shí)數(shù)目是隨機(jī)的，導(dǎo)致簇首多時(shí)，能耗低;反之，能耗高的問(wèn)題，造成節(jié)點(diǎn)能耗不均衡。所以，本文算法所采用的選簇方式和簇間多跳路徑選擇機(jī)制使得簇首平均能耗處于低位穩(wěn)定的狀態(tài)，能夠較好地均衡節(jié)點(diǎn)能耗，延長(zhǎng)網(wǎng)絡(luò)壽命。

圖3 網(wǎng)絡(luò)簇首平均能耗比較

5 結(jié)束語(yǔ)

本文針對(duì)低冗余度的無(wú)線傳感器網(wǎng)絡(luò)，提出一種基于粒子群和最短路由樹(shù)的非均勻分簇路由算法，該算法具有如下特點(diǎn):(1)利用PSO 算法優(yōu)化分簇過(guò)程，一次性選擇固定數(shù)目簇首，不僅滿足實(shí)際網(wǎng)絡(luò)簡(jiǎn)單穩(wěn)定的要求，還降低了算法復(fù)雜度，提高了分簇效率;(2)通過(guò)建立最短路由樹(shù)的方式進(jìn)行數(shù)據(jù)的傳輸和轉(zhuǎn)發(fā)以及動(dòng)態(tài)地更新最短路由樹(shù)，能夠很好地均衡網(wǎng)絡(luò)節(jié)點(diǎn)能耗;(3)用來(lái)檢測(cè)參數(shù)的普通節(jié)點(diǎn)不擔(dān)任簇首，節(jié)點(diǎn)能耗更均衡、壽命更長(zhǎng)，保證了檢測(cè)質(zhì)量。仿真結(jié)果表明，本文算法在應(yīng)用到節(jié)點(diǎn)冗余度低的無(wú)線傳感器網(wǎng)絡(luò)中時(shí)，能有效降低節(jié)點(diǎn)死亡速度，延長(zhǎng)網(wǎng)絡(luò)有效生存時(shí)間，為進(jìn)一步應(yīng)用到工業(yè)生產(chǎn)中的低冗余度無(wú)線傳感器網(wǎng)絡(luò)提供理論依據(jù)。

［1］沈 波，張世永，鐘亦平.無(wú)線傳感器網(wǎng)絡(luò)分簇路由協(xié)議［J］.軟件學(xué)報(bào)，2006，17(7):1588-1600.

［2］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy Efficient Communication Protocol for Wireless Sensor Networks ［C］//Proceedings of the 33rd Hawaii International Conference on System Sciences.Hawaii，USA:［s.n.］，2000:3005-3014.

［3］Heinzelman W.An Application-specific Protocol Architecture for Wireless MicroSensor Networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660-670.

［4］Ye Mao，Li Chengfa，Chen Guihai，et al.EECS:An Energy Efficient Cluster Scheme in Wireless Senor Networks［C］//Proceedings of the 24th IEEE Inter-national Conference on Performance，Computing，and Communications.Phoenix，USA:IEEE Press，2005:535-540.

［5］李成法，陳貴海，吳 杰，等.一種基于非均勻分簇的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30(1):27-36.

［6］蔣暢江，石為人，唐賢倫，等.能量均衡的無(wú)線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議［J］.軟件學(xué)報(bào)，2012，23(5):1223-1231.

［7］蘇 兵，黃冠發(fā).基于粒子群優(yōu)化的WSN 非均勻分簇路由算法［J］.計(jì)算機(jī)應(yīng)用，2011，31(9):2340-2343.

［8］李 鑒，石 馨，劉賀平.煤礦巷道無(wú)線傳感器網(wǎng)絡(luò)非均勻分簇?cái)?shù)據(jù)傳送機(jī)制［J］.中國(guó)地質(zhì)大學(xué)學(xué)報(bào)，2013，38(1):196-200.

［9］Conmen T H，Leiserson C E，Rivest R L，et al.算法導(dǎo)論［M］.2 版.潘金貴，顧鐵成，李成法，等，譯.北京:機(jī)械工業(yè)出版社，2006.

［10］尚鳳軍，任東海.無(wú)線傳感器網(wǎng)絡(luò)中分布式多跳路由算法研究［J］.傳感技術(shù)學(xué)報(bào)，2012，25(4):530-534.

［11］張明才，薛安榮，王 偉.基于最小生成樹(shù)的非均勻分簇路由算法［J］.計(jì)算機(jī)應(yīng)用，2012，32(3):787-790.

［12］Narvaez P，Siu K Y，Tzeng H Y.New Dynamic Algorithms for Shortest Path Tree Computation［J］.IEEE/ACM Transactions on Networking，2000，8(9):734-746.