孫愛(ài)晶，朱開(kāi)磊

(西安郵電大學(xué) 通信與信息工程學(xué)院，陜西 西安 710121)

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)由大量低功耗、能量有限的微型的傳感器節(jié)點(diǎn)組成，多用于智能家居、智慧農(nóng)業(yè)等場(chǎng)景[1-2]。傳感器節(jié)點(diǎn)通過(guò)無(wú)線(xiàn)鏈路構(gòu)建自組織網(wǎng)絡(luò)，并將感知數(shù)據(jù)發(fā)送至簇首或者基站[3]。傳感器節(jié)點(diǎn)能量有限且通常被隨機(jī)布置在某些環(huán)境惡劣區(qū)域，對(duì)其進(jìn)行充電是不現(xiàn)實(shí)的[4]。因此，延長(zhǎng)網(wǎng)絡(luò)生命周期成為當(dāng)前的熱門(mén)研究課題。

針對(duì)延長(zhǎng)網(wǎng)絡(luò)生命周期的問(wèn)題，研究者們提出了許多基于簇結(jié)構(gòu)的層次性網(wǎng)絡(luò)路由協(xié)議[5-6]。文獻(xiàn)[7]提出的經(jīng)典的低功耗自適應(yīng)集簇分層(Low Energy Adaptive Clustering Hierarchy,LEACH) 協(xié)議以循環(huán)的方式隨機(jī)選擇簇首，使各個(gè)節(jié)點(diǎn)都有機(jī)會(huì)成為簇首均衡網(wǎng)絡(luò)負(fù)載。然而，LEACH協(xié)議中簇首的選舉沒(méi)有考慮節(jié)點(diǎn)剩余能量，當(dāng)能量低的節(jié)點(diǎn)被選為簇首，會(huì)加速網(wǎng)絡(luò)的死亡。針對(duì)LEACH協(xié)議存在簇首選舉不合理的問(wèn)題，文獻(xiàn)[8]提出的LEACH-improve協(xié)議將剩余能量因子、間距因子和密度因子融入到傳統(tǒng)LEACH閾值計(jì)算公式中，使選舉的簇首更具合理性，網(wǎng)絡(luò)生命周期得以提高，但仍會(huì)出現(xiàn)極小、極大簇，不利于簇內(nèi)節(jié)點(diǎn)負(fù)載均衡。文獻(xiàn)[9]提出了非均勻分簇協(xié)議 (Energy-Efficient Uneven Clustering,EEUC)，候選簇首通過(guò)使用非均勻的競(jìng)爭(zhēng)范圍構(gòu)造大小不等的簇，使靠近基站的簇的規(guī)模小于遠(yuǎn)離基站的簇，延長(zhǎng)了網(wǎng)絡(luò)生命周期。文獻(xiàn)[10]將FCM算法(Fuzzy C-means,FCM)和模糊邏輯結(jié)合起來(lái)，先用FCM算法得到均勻分簇，然后結(jié)合能量、距離等因素利用模糊邏輯在簇內(nèi)選舉簇首，有效地均衡了節(jié)點(diǎn)負(fù)載，但該算法未對(duì)簇首規(guī)劃路由，不利于均衡簇首負(fù)載。文獻(xiàn)[11]使用遺傳算法優(yōu)化FCM的初始聚類(lèi)中心以獲取最優(yōu)分簇，并結(jié)合節(jié)點(diǎn)能量及距離因子選舉簇首。但在簇首輪換階段，只說(shuō)明網(wǎng)絡(luò)系數(shù)取值過(guò)大過(guò)小都會(huì)加速網(wǎng)絡(luò)能量消耗，并未給出最優(yōu)網(wǎng)絡(luò)系數(shù)的計(jì)算方式和實(shí)驗(yàn)數(shù)據(jù)。FCM算法雖然得到了均勻分簇，但在大規(guī)模節(jié)點(diǎn)部署環(huán)境下，由于其收斂速度緩慢，不適用于規(guī)模大且對(duì)網(wǎng)絡(luò)實(shí)時(shí)性要求高的環(huán)境。文獻(xiàn)[12]提出了一種基于凝聚嵌套(Agglomerative Nesting,AGENS)聚類(lèi)的能量均衡WSN路由優(yōu)化算法(An Energy-Balanced WSN Routing Optimization Algorithm based AGNES Clustering,EBRAA)。該算法首先使用AGENS分簇，然后結(jié)合簇內(nèi)節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)與基站距離及兩者權(quán)重因子，完成分布式簇首選舉，最后采用改進(jìn)后的Dijkstra算法產(chǎn)生簇首間最短路徑的多跳路由。但是，并未給出最優(yōu)權(quán)重的證明過(guò)程，也未考慮中繼節(jié)點(diǎn)的負(fù)載因素，這會(huì)影響簇首選舉的合理性及加速中繼節(jié)點(diǎn)死亡。

為了改善FCM算法在網(wǎng)絡(luò)分簇時(shí)收斂速度緩慢、簇首選舉不合理和遠(yuǎn)端簇首能耗大的問(wèn)題，在LEACH協(xié)議的分簇思想基礎(chǔ)上擬提出基于改進(jìn)抑制式模糊C-均值和粒子群算法的WSN分簇路由算法(WSN Clustering Routing Algorithm based on Improved S-FCM and PSO Algorithms，CRIS-FCMP)。分簇階段，利用抑制式模糊C-均值算法的目標(biāo)函數(shù)改進(jìn)抑制率，使改進(jìn)的抑制式模糊C-均值(Improved Suppressed Fuzzy C-means，IS-FCM) 算法既能提高收斂速度又能保持良好分簇特性；簇首選舉階段，依據(jù)簇內(nèi)節(jié)點(diǎn)能量關(guān)系構(gòu)建節(jié)點(diǎn)動(dòng)態(tài)能量閾值選舉簇首；數(shù)據(jù)傳輸階段，依據(jù)中繼節(jié)點(diǎn)具有高剩余能量、位置適中等特點(diǎn)設(shè)計(jì)路徑選擇適應(yīng)度函數(shù)，并結(jié)合粒子群算法(Particle Swarm Optimization,PSO)為遠(yuǎn)端簇首搜尋最優(yōu)路由路徑。

1 系統(tǒng)模型

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

為了均衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能耗，對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行分簇，之后在分簇中選舉簇首，最后為簇首規(guī)劃路由。涉及的傳感器網(wǎng)絡(luò)模型如圖1所示。

圖1 傳感器網(wǎng)絡(luò)模型

圖1中基站位于監(jiān)測(cè)區(qū)域中心且假設(shè)具有無(wú)限大的處理能力和穩(wěn)定能量供應(yīng)。白圈代表傳感器節(jié)點(diǎn)，這些節(jié)點(diǎn)隨機(jī)布設(shè)在監(jiān)測(cè)區(qū)域內(nèi)，布設(shè)后將不再移動(dòng)，每個(gè)節(jié)點(diǎn)由一個(gè)全局唯一的ID標(biāo)識(shí)。此外，這些節(jié)點(diǎn)還擁有如下特點(diǎn)：所有節(jié)點(diǎn)初始能量相同且同構(gòu)；節(jié)點(diǎn)能夠根據(jù)接收信息的信號(hào)強(qiáng)度判斷與發(fā)送者的近似距離，從而選取自身發(fā)射功率；節(jié)點(diǎn)可以感知自身位置和其他節(jié)點(diǎn)及基站位置，并可以周期性感知監(jiān)測(cè)數(shù)據(jù)并發(fā)送至相應(yīng)簇首；節(jié)點(diǎn)可以感知自己的剩余能量，且有存儲(chǔ)、查詢(xún)、計(jì)算和數(shù)據(jù)融合能力。

1.2 能耗模型

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)能耗主要來(lái)自于數(shù)據(jù)的收發(fā)，采用與文獻(xiàn)[13]相同的網(wǎng)絡(luò)能耗模型進(jìn)行節(jié)點(diǎn)間的通信。節(jié)點(diǎn)信道模型的選擇主要由其收發(fā)距離d決定。節(jié)點(diǎn)發(fā)送l位數(shù)據(jù)至距離為d的節(jié)點(diǎn)消耗的能量為

(1)

節(jié)點(diǎn)接收融合lbit數(shù)據(jù)消耗能量的表達(dá)式為

Erx=lEelec+lEda

(2)

式中，Eda表示融合1 bit數(shù)據(jù)消耗的能量。

結(jié)合網(wǎng)絡(luò)模型及能耗模型的描述，改進(jìn)路由算法將從均勻分簇選舉合理簇首和為簇首規(guī)劃合理路由的方向進(jìn)行設(shè)計(jì)。具體路由算法的改進(jìn)方案將在下文中進(jìn)行詳細(xì)闡述。

2 改進(jìn)的抑制式模糊C-均值算法

抑制式模糊C-均值S-FCM(Suppressed Fuzzy C-means，S-FCM)算法[14]由范九倫于2003年提出，S-FCM算法是FCM算法[15]的拓展。考慮該算法具有快速收斂和良好分類(lèi)的優(yōu)點(diǎn)，將其應(yīng)用到WSN分簇中。

FCM算法是通過(guò)計(jì)算每個(gè)節(jié)點(diǎn)對(duì)類(lèi)中心的模糊隸屬度、極小化FCM的目標(biāo)函數(shù)得到最優(yōu)分簇。FCM目標(biāo)函數(shù)表示為

(3)

(4)

(5)

由于FCM算法迭代速度慢，在大規(guī)模節(jié)點(diǎn)集合環(huán)境下，聚類(lèi)需要消耗大量時(shí)間。通過(guò)對(duì)隸屬度進(jìn)行合理的修正，可以保證合理分類(lèi)的同時(shí)加快算法收斂速度。對(duì)每一個(gè)節(jié)點(diǎn)xj，節(jié)點(diǎn)j在所有類(lèi)中的最大隸屬度的表達(dá)式為

則最大隸屬度和其他隸屬度的修正表達(dá)式分別為

(6)

Uij=αuij(i≠p)

(7)

式中，0≤α≤1，表示抑制率。對(duì)FCM的隸屬度進(jìn)行抑制的算法稱(chēng)為S-FCM。當(dāng)α=0時(shí)，S-FCM變?yōu)镠CM，即K-means算法；當(dāng)α=1時(shí)，S-FCM變?yōu)镕CM算法。α作為HCM與FCM之間的折中因子，通常α取值為0.5。為了達(dá)到更快分類(lèi)目的，采用不固定抑制率α的機(jī)制，第r輪的改進(jìn)抑制率和改進(jìn)抑制式模糊C-均值算法目標(biāo)函數(shù)表達(dá)式分別為

(8)

(9)

式中：JIS-FCM(r-1)和JIS-FCM(1)分別為改進(jìn)抑制式模糊C均值算法的第r-1輪與首輪目標(biāo)函數(shù)；α(r)表示第r輪的抑制率。通過(guò)式(8)可以看出，抑制率α每輪隨著上輪的目標(biāo)函數(shù)變化而變化。當(dāng)分類(lèi)不合理時(shí)JIS-FCM值較大，通過(guò)式(6)與式(8)可知，每個(gè)節(jié)點(diǎn)最大隸屬度的獎(jiǎng)勵(lì)降低，進(jìn)而減慢了節(jié)點(diǎn)向自身所在類(lèi)的收斂速度，算法性能向FCM靠近；當(dāng)節(jié)點(diǎn)分類(lèi)趨于合理時(shí)，JIS-FCM變小，α變小，此時(shí)增加了對(duì)每個(gè)節(jié)點(diǎn)最大隸屬度的獎(jiǎng)勵(lì)程度，節(jié)點(diǎn)向自身所在類(lèi)的收斂速度加快，算法性能向HCM靠近。通過(guò)以上分析，IS-FCM算法根據(jù)分類(lèi)情況動(dòng)態(tài)地調(diào)整抑制率，從而使節(jié)點(diǎn)根據(jù)分類(lèi)情況對(duì)聚類(lèi)中心的“吸引力”作實(shí)時(shí)動(dòng)態(tài)變化，在保證合理分類(lèi)的同時(shí)，加快算法收斂速度。

IS-FCM聚類(lèi)算法步驟如下。

步驟2依據(jù)式(3)計(jì)算第r輪節(jié)點(diǎn)對(duì)各聚類(lèi)的隸屬度ur。

步驟3結(jié)合步驟2得到的隸屬度ur，依據(jù)式(6)、式(7)和式(8)計(jì)算修正后的隸屬度。

具體的IS-FCM聚類(lèi)算法的流程如圖2所示。

圖2 IS-FCM聚類(lèi)算法流程

3 CRIS-FCMP算法

為了加快網(wǎng)絡(luò)分簇速度和降低簇首傳輸數(shù)據(jù)能耗，提出了基于改進(jìn)抑制式模糊C-均值和粒子群算法的WSN分簇路由算法CRIS-FCMP。

3.1 簇的形成

網(wǎng)絡(luò)初始化階段，基站首先為監(jiān)測(cè)區(qū)域的每一個(gè)節(jié)點(diǎn)分配唯一的通信ID，然后各個(gè)節(jié)點(diǎn)將自身的剩余能量、位置坐標(biāo)發(fā)送給基站，基站獲得節(jié)點(diǎn)信息后進(jìn)行分簇，最終將分簇信息廣播至各節(jié)點(diǎn)，廣播信息中包含簇ID、節(jié)點(diǎn)與基站的距離。

合理的分簇?cái)?shù)目能夠進(jìn)一步均衡無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的負(fù)載，因此采用文獻(xiàn)[11]計(jì)算最優(yōu)分簇?cái)?shù)目，最優(yōu)簇首數(shù)目表達(dá)式為

(10)

式中：M表示監(jiān)測(cè)區(qū)域的邊長(zhǎng)；dBS表示簇首到基站的平均距離。由式(10)得到最優(yōu)分簇?cái)?shù)后，將監(jiān)測(cè)區(qū)域內(nèi)的節(jié)點(diǎn)視為分類(lèi)對(duì)象，采用改進(jìn)抑制式模糊C-均值算法進(jìn)行節(jié)點(diǎn)的分簇。此外，隨著網(wǎng)絡(luò)的運(yùn)行，存活節(jié)點(diǎn)數(shù)目不斷下降，網(wǎng)絡(luò)特征發(fā)生了變化，當(dāng)初的最優(yōu)簇首數(shù)不再適合網(wǎng)絡(luò)狀態(tài)。因此，CRIS-FCMP算法在每輪結(jié)束時(shí)，基站會(huì)根據(jù)式(3)計(jì)算最優(yōu)簇首數(shù)，當(dāng)最優(yōu)簇首數(shù)改變時(shí)，利用IS-FCM算法進(jìn)行重新分簇，直至分簇?cái)?shù)為1。動(dòng)態(tài)分簇避免了因節(jié)點(diǎn)死亡造成的分簇不均勻，從而均衡了簇內(nèi)負(fù)載，延長(zhǎng)網(wǎng)絡(luò)生命周期。

3.2 簇首選舉

簇首擔(dān)任簇內(nèi)節(jié)點(diǎn)數(shù)據(jù)的接收、融合和轉(zhuǎn)發(fā)任務(wù)，較簇內(nèi)節(jié)點(diǎn)每輪消耗更多能量。為了均衡簇內(nèi)節(jié)點(diǎn)的負(fù)載，選擇一個(gè)剩余能量充沛，距離聚類(lèi)中心較近的節(jié)點(diǎn)作為簇首，以均衡簇內(nèi)節(jié)點(diǎn)負(fù)載，延長(zhǎng)網(wǎng)絡(luò)生命周期。

首先，為了保證選舉的簇首能量充沛，設(shè)計(jì)了節(jié)點(diǎn)動(dòng)態(tài)能量閾值，當(dāng)節(jié)點(diǎn)剩余能量大于其動(dòng)態(tài)能量閾值時(shí)，該節(jié)點(diǎn)當(dāng)選為簇首。節(jié)點(diǎn)動(dòng)態(tài)能量閾值主要由動(dòng)態(tài)權(quán)重和簇內(nèi)平均剩余能量組成，動(dòng)態(tài)能量閾值和動(dòng)態(tài)權(quán)重表達(dá)式分別為

θ(i)=F(i)Ecluster_avg

(11)

(12)

式中：Ecluster_avg表示簇內(nèi)節(jié)點(diǎn)平均剩余能量；Emax表示節(jié)點(diǎn)i所在簇的最大節(jié)點(diǎn)剩余能量；Eres(i)表示節(jié)點(diǎn)i的剩余能量。Ecluster_avg作為閾值基數(shù)可避免選舉簇首的能量太低，此外，為了降低簇首能量與簇內(nèi)節(jié)點(diǎn)能量的差距，利用節(jié)點(diǎn)i的剩余能量Eres(i)和Emax構(gòu)造F(i)作為動(dòng)態(tài)權(quán)重。由式(11)與式(12)可以看出，當(dāng)Eres(i)與Emax的值相差較小時(shí)，θ(i)變小，節(jié)點(diǎn)i當(dāng)選為簇首的概率變高。

簇首擁有充沛合理的剩余能量很關(guān)鍵，但仍需要考慮簇首與聚類(lèi)中心的距離以均衡簇內(nèi)節(jié)點(diǎn)負(fù)載。因此，根據(jù)簇內(nèi)節(jié)點(diǎn)與聚類(lèi)中心的距離，按從小到大的順序比較節(jié)點(diǎn)i的剩余能量Eres(i)與節(jié)點(diǎn)動(dòng)態(tài)能量閾值θ(i)的大小，當(dāng)Eres(i)≥θ(i)時(shí)，節(jié)點(diǎn)i選為簇首，否則進(jìn)行下一節(jié)點(diǎn)的比較，直至選舉出簇首，若簇內(nèi)沒(méi)有符合條件的節(jié)點(diǎn)，選擇簇內(nèi)擁有最大剩余能量的節(jié)點(diǎn)作為簇首。

3.3 數(shù)據(jù)傳輸

分簇階段完成后，簇內(nèi)節(jié)點(diǎn)采用時(shí)分多址(Time Division Multiple Access,TDMA)協(xié)議將數(shù)據(jù)發(fā)送至簇首，然后簇首再將接收的簇內(nèi)數(shù)據(jù)融合并發(fā)送至基站。但是，隨著節(jié)點(diǎn)間距離的增大，數(shù)據(jù)傳輸能耗按指數(shù)級(jí)增加[16]。為了減輕簇首因長(zhǎng)距離傳輸數(shù)據(jù)消耗的能量，實(shí)現(xiàn)網(wǎng)絡(luò)能耗均衡，對(duì)簇首進(jìn)行路由規(guī)劃。

針對(duì)數(shù)據(jù)傳輸階段均衡簇首負(fù)載的問(wèn)題，已有的算法[17-18]都是通過(guò)簇首到簇首的轉(zhuǎn)發(fā)形式均衡簇首負(fù)載，雖然能夠減輕遠(yuǎn)端簇首的負(fù)載，卻加劇了靠近基站的簇首的負(fù)載。因此，利用PSO算法為簇首規(guī)劃最優(yōu)路由路徑，以降低簇首被選為中繼節(jié)點(diǎn)的概率。

PSO算法[19]是Eberhart和Kennedy于1995年提出的多目標(biāo)優(yōu)化算法?？紤]其能有效解決大規(guī)模的非線(xiàn)性問(wèn)題，將該算法應(yīng)用到簇首路由路徑規(guī)劃中。算法中每一個(gè)粒子可以看作問(wèn)題的一個(gè)可行解，根據(jù)適應(yīng)度函數(shù)可以計(jì)算出每個(gè)粒子的適應(yīng)度值，從而得到全局最優(yōu)位置G和局部最優(yōu)位置P，即規(guī)定粒子適應(yīng)度值越小則對(duì)應(yīng)的解越優(yōu)。根據(jù)全局最優(yōu)位置和局部最優(yōu)位置，粒子的速度更新和位置更新的表達(dá)式分別為

Vi(t+1)=ωVi(t)+c1rand1[Pi(t)-Xi(t)]+
c2rand2[G(t)-Xi(t)]

(13)

Xi(t+1)=Xi(t)+Vi(t+1)

(14)

式中：c1,c2為學(xué)習(xí)因子，通常取2；Vi(t)表示第i個(gè)粒子第t代的速度，|Vi(t)|∈[vmin,vmax]，ωmax和ωmin分別表示設(shè)置的最大、最小權(quán)重；Pi(t)表示第i個(gè)粒子在第t代自身搜索到的最好位置；G(t)表示第t代時(shí)所有粒子搜索到的最優(yōu)位置；Xi(t)表示第i個(gè)粒子第t代的位置；rand1,rand2為0～1之間的隨機(jī)數(shù)；ω為慣性權(quán)重系數(shù)。為了提高PSO算法的尋優(yōu)能力，ω采用文獻(xiàn)[20]的非線(xiàn)性自適應(yīng)慣性權(quán)重系數(shù)，表達(dá)式為

ω=

(15)

式中：fmin，fmax，favg分別表示本輪粒子群的最小、最大和平均適應(yīng)度值；f(i)表示第i個(gè)粒子的適應(yīng)度值。

在利用PSO算法進(jìn)行簇首路由尋優(yōu)之前，需要確定路由跳數(shù)，為了能夠進(jìn)一步均衡簇首負(fù)載，根據(jù)最佳傳輸距離[21]dbest、簇首j到基站的距離dj-bs，計(jì)算簇首j經(jīng)幾跳將數(shù)據(jù)發(fā)送至基站，簇首j的路由跳數(shù)的表達(dá)式為

(16)

式中，round()表示四舍五入操作。

簇首路由跳數(shù)確定后，粒子的編碼形式設(shè)為X={xCH,x1,x2,…,xh-1,xBS}，其中：xCH,xBS分別表示簇首和基站的位置；x1,x2,…,xh-1表示簇首的隨機(jī)初始中繼節(jié)點(diǎn)位置。當(dāng)PSO算法進(jìn)行更新時(shí)，x1,x2,…,xh-1也進(jìn)行更新，最終的最優(yōu)粒子解就是簇首的最優(yōu)路由路徑。其他簇首按相同方法進(jìn)行粒子編碼。

PSO算法在為簇首規(guī)劃路由時(shí)，需要一個(gè)標(biāo)準(zhǔn)評(píng)價(jià)路由的優(yōu)劣，以得到最優(yōu)簇首路由路徑。因此，需要為PSO算法設(shè)計(jì)一個(gè)簇首路徑選擇適應(yīng)度函數(shù)。由式(16)可知，簇首j需經(jīng)hj跳將數(shù)據(jù)發(fā)送至基站，即經(jīng)hj-1個(gè)中繼節(jié)點(diǎn)。中繼節(jié)點(diǎn)應(yīng)具備以下幾個(gè)特點(diǎn)：中繼節(jié)點(diǎn)剩余能量應(yīng)足夠充沛，保證數(shù)據(jù)傳輸?shù)姆€(wěn)定；中繼節(jié)點(diǎn)與簇首和基站的距離要適中，以均衡簇首和中繼節(jié)點(diǎn)的負(fù)載；簇首前向路由路徑的長(zhǎng)度要盡量的??；中繼節(jié)點(diǎn)的選取不應(yīng)局限于簇首之中，以降低簇首負(fù)載；中繼節(jié)點(diǎn)不宜作為多個(gè)簇首的中繼，以均衡中繼節(jié)點(diǎn)負(fù)載。

根據(jù)上述幾個(gè)特點(diǎn)，設(shè)計(jì)了路徑選擇適應(yīng)度函數(shù)，表達(dá)式為

(17)

式中：Edelay-avg表示中繼節(jié)點(diǎn)的平均剩余能量；Eavg表示所有存活節(jié)點(diǎn)平均剩余能量，中繼節(jié)點(diǎn)充沛的剩余能量保證了數(shù)據(jù)傳輸?shù)姆€(wěn)定；dmin和dmax分別表示簇首前向路由路徑中相鄰節(jié)點(diǎn)的最小、最大距離，兩者之間差距越小，則中繼節(jié)點(diǎn)位置越適中，中繼節(jié)點(diǎn)負(fù)載越均衡；dCH-BS表示簇首到基站的直線(xiàn)距離；dtotal表示簇首前向路由路徑的距離之和。節(jié)點(diǎn)被選為中繼節(jié)點(diǎn)的次數(shù)定義為負(fù)載L，其值越小表示中繼節(jié)點(diǎn)的負(fù)載越小，有利于均衡中繼節(jié)點(diǎn)的負(fù)載。由于L的值在非零時(shí)通常大于前兩項(xiàng)，且當(dāng)其值越大時(shí)，節(jié)點(diǎn)多次作為中繼節(jié)點(diǎn)的概率越小。因此，不在L因素前添加權(quán)重系數(shù)。通過(guò)分析，當(dāng)froute值越小，結(jié)合PSO算法得到的簇首路由路徑就越合理。

此外，隨著網(wǎng)絡(luò)的運(yùn)行，中繼節(jié)點(diǎn)的能量顯得尤為重要，故定義權(quán)重系數(shù)a，b分別為

a=1-b

(18)

(19)

式中，Einit表示節(jié)點(diǎn)初始能量。網(wǎng)絡(luò)初始階段，Eavg較大，故b值也較大，路徑選擇適應(yīng)度函數(shù)以距離因素為主；隨著網(wǎng)絡(luò)運(yùn)行，Eavg變小，a值變大，路徑選擇適應(yīng)度函數(shù)以能量因素為主。依據(jù)節(jié)點(diǎn)剩余能量設(shè)計(jì)的動(dòng)態(tài)權(quán)重系數(shù)均衡了整個(gè)網(wǎng)絡(luò)運(yùn)行階段的簇首路由能耗。

基于PSO的簇首路由算法步驟如下。

步驟1初始化粒子群初始位置、速度及其他參數(shù)。

步驟2依據(jù)式(17)計(jì)算粒子適應(yīng)度值并依據(jù)適應(yīng)度值判斷全局最優(yōu)解G和局部最優(yōu)解P。

步驟3根據(jù)式(13)和式(14)更新粒子速度與位置。

步驟4重復(fù)步驟2和步驟3，直到最優(yōu)適應(yīng)度值收斂或達(dá)到最大迭代次數(shù)。

步驟5輸出最優(yōu)解。

輸出的最優(yōu)解即可解碼為簇首最終路由。CRIS-FCMP算法的總體偽代碼可參考附錄A。

3.4 算法復(fù)雜度分析

初始化網(wǎng)絡(luò)有k個(gè)簇首，N個(gè)無(wú)線(xiàn)傳感器節(jié)點(diǎn)，從CRIS-FCMP算法的簇的形成、簇首選舉和數(shù)據(jù)傳輸?shù)?個(gè)階段分析算法的復(fù)雜度。

簇的形成階段，IS-FCM算法迭代次數(shù)為z，聚類(lèi)維度為2k，因此，IS-FCM算法的復(fù)雜度為O(zk)；簇首選舉時(shí)遍歷N個(gè)節(jié)點(diǎn)，復(fù)雜度為O(N)；數(shù)據(jù)傳輸階段，PSO算法迭代次數(shù)為z，種群規(guī)模為c，簇首數(shù)為k，那么簇首路由路徑規(guī)劃過(guò)程的復(fù)雜度為O(zck)。

因此，CRIS-FCMP算法每輪復(fù)雜度為O(zck)，復(fù)雜度等同于算法執(zhí)行所需要的基本運(yùn)算次數(shù)。CRIS-FCMP算法由簇的形成、簇首選舉和數(shù)據(jù)傳輸?shù)?階段組成。因此CRIS-FCMP算法每輪能在zck運(yùn)算次數(shù)中得到結(jié)果，算法可行。

4 分析及其仿真

釆用計(jì)算機(jī)仿真軟件對(duì)所提的CRIS-FCMP算法和LEACH-improve[8]、GAFCMCR[11]、EBRAA[12]進(jìn)行仿真，并在相同的仿真環(huán)境下對(duì)算法進(jìn)行對(duì)比分析，仿真參數(shù)如表1所示。

表1 仿真參數(shù)

4.1 分簇速度對(duì)比分析

為了驗(yàn)證IS-FCM算法的迭代速度較FCM[15]、Iα-SFCM[22]和S-FCM(α=0.5)[14]算法是否提升，在同一仿真環(huán)境和相同參數(shù)設(shè)置下，運(yùn)用IS-FCM、Iα-SFCM、S-FCM(α=0.5)和FCM算法分別對(duì)100～500個(gè)節(jié)點(diǎn)(間隔為100)進(jìn)行分簇運(yùn)算。為了避免偶然性，對(duì)每次分簇的迭代次數(shù)和迭代時(shí)間分別取50次實(shí)驗(yàn)的平均值。IS-FCM、Iα-SFCM、S-FCM(α=0.5)和FCM算法的迭代次數(shù)、迭代時(shí)間分別如表2和表3所示。

表2 4種算法迭代次數(shù)對(duì)比

表3 4種算法迭代時(shí)間對(duì)比

從表2、表3中可以看出，在100～500個(gè)節(jié)點(diǎn)分簇仿真中，IS-FCM算法的迭代次數(shù)較FCM算法、Iα-SFCM和S-FCM(α=0.5)平均減少了83.6%、29.9%和-3.6%，迭代時(shí)間平均減少了81.8%、31.4%和9.3%。IS-FCM算法的收斂速度較FCM算法顯著提高，這得益于IS-FCM算法采用了自身的目標(biāo)函數(shù)構(gòu)造抑制率，通過(guò)上輪的分簇效果反饋給抑制率，對(duì)最大節(jié)點(diǎn)隸屬度進(jìn)行了獎(jiǎng)勵(lì)，而抑制了其他隸屬度，加快了節(jié)點(diǎn)向自身所在類(lèi)的收斂速度。IS-FCM迭代次數(shù)高于S-FCM(α=0.5)算法，是因?yàn)镾-FCM(α=0.5)算法一直處于獎(jiǎng)勵(lì)最大隸屬度的狀態(tài)(α=0.5)，即一直處于加快收斂的狀態(tài)，而IS-FCM根據(jù)分簇效果動(dòng)態(tài)調(diào)整抑制系數(shù)，收斂速度忽快忽慢，但分簇效果要比S-FCM(α=0.5)的好。由于Iα-SFCM算法未對(duì)噪聲及最大隸屬度低于0.5的節(jié)點(diǎn)進(jìn)行隸屬度的修正，收斂速度要低于IS-FCM算法。

4.2 分簇效果對(duì)比分析

4.1節(jié)已經(jīng)驗(yàn)證了IS-FCM較FCM、Iα-SFCM和S-FCM(α=0.5)算法收斂速度顯著提高，但分簇的合理性同樣重要，那么在同一條件下，對(duì)FCM算法、S-FCM(α=0.5)、Iα-SFCM和IS-FCM算法的分簇進(jìn)行了仿真，分簇結(jié)果分別如圖3(a)至圖3(d)所示，圖中實(shí)心點(diǎn)表示分簇中心，空心點(diǎn)表示分簇成員。

圖3 4種算法分簇效果

比較圖3(a)、圖3(c)和圖3(d)，可以發(fā)現(xiàn)IS-FCM與FCM算法和Iα-SFCM算法的分簇效果幾乎相同，從表4中可以看出其簇成員方差數(shù)區(qū)別不大，也未出現(xiàn)極小極大簇。雖然圖3(a)、圖3(c)的分簇效果相似，從以上分析中可以發(fā)現(xiàn)Iα-SFCM算法的收斂速度要比FCM算法快。因此，Iα-SFCM算法要優(yōu)于FCM算法，然而IS-FCM算法收斂要快于Iα-SFCM算法，這說(shuō)明IS-FCM算法比FCM與Iα-SFCM算法收斂速度快的同時(shí)保持了均勻分簇的良好特性。

表4 簇成員數(shù)對(duì)比

對(duì)比圖3(b)和圖3(d)，可以明顯看出圖3(b)中的左右兩側(cè)出現(xiàn)了極小、極大簇，說(shuō)明S-FCM(α=0.5)算法的分簇沒(méi)有IS-FCM算法的合理。這主要由于S-FCM(α=0.5)采用了固定的抑制率，不能根據(jù)分簇情況對(duì)抑制率做出實(shí)時(shí)調(diào)整，導(dǎo)致了S-FCM(α=0.5)算法盲目的獎(jiǎng)勵(lì)節(jié)點(diǎn)最大隸屬度，雖然加快了算法收斂速度，但容易使算法陷入局部最優(yōu)，而IS-FCM算法則利用分簇效果動(dòng)態(tài)調(diào)整抑制系數(shù)，加速收斂的同時(shí)避免算法陷入局部最優(yōu)。

綜合仿真分析，IS-FCM相較于FCM、Iα-SFCM和S-FCM(α=0.5)算法收斂速度得到提升的同時(shí)，仍然保持了良好的分簇特性。IS-FCM的快速良好分簇特性使其可以應(yīng)用于對(duì)實(shí)時(shí)性要求高的網(wǎng)絡(luò)中，特別是大規(guī)模網(wǎng)絡(luò)環(huán)境中。

4.3 網(wǎng)絡(luò)生命周期

將CRIS-FCMP算法分別與LEACH-improve、GAFCMCR和EBRAA算法進(jìn)行節(jié)點(diǎn)存活數(shù)量變化的仿真比較，相關(guān)參數(shù)如表1定義，網(wǎng)絡(luò)生命周期對(duì)比結(jié)果如圖4所示。經(jīng)仿真得出，CRIS-FCMP算法首節(jié)點(diǎn)死亡時(shí)間出現(xiàn)在第1 025輪，而LEACH-improve、GAFCMCR和EBRAA算法首節(jié)點(diǎn)死亡時(shí)間分別出現(xiàn)在第472、第700和第715輪。因此，CRIS-FCMP算法較LEACH-improve、GAFCMCR和EBRAA算法分別提高117.2%、46.4%和43.3%。

圖4給出了CRIS-FCMP算法與其他3個(gè)算法的網(wǎng)絡(luò)生命周期的具體情況，從圖4中可以看出，CRIS-FCMP算法的生命周期明顯大于LEACH-improve、GAFCMCR和EBRAA。LEACH-improve、GAFCMCR和EBRAA算法分別大約在900輪、900輪和1 000輪，僅剩1/5存活節(jié)點(diǎn)，而CRIS-FCMP算法此時(shí)仍未出現(xiàn)節(jié)點(diǎn)死亡的情況，說(shuō)明了CRIS-FCMP算法有效地延長(zhǎng)了網(wǎng)絡(luò)生命周期。此外，CRIS-FCMP算法第一個(gè)節(jié)點(diǎn)死亡后，節(jié)點(diǎn)死亡趨勢(shì)陡直，說(shuō)明了該算法有效地均衡了節(jié)點(diǎn)的能耗。

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

4.4 網(wǎng)絡(luò)能耗

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)生命周期的延長(zhǎng)主要由節(jié)點(diǎn)能量消耗的快慢決定。圖5為L(zhǎng)EACH-improve、GAFCMCR、EBRAA和CRIS-FCMP算法的節(jié)點(diǎn)能量剩余對(duì)比結(jié)果。

圖5 節(jié)點(diǎn)剩余能量對(duì)比

從圖5中可以看出，在整個(gè)網(wǎng)絡(luò)生命周期中，CRIS-FCMP算法的節(jié)點(diǎn)剩余能量始終高于LEACH-improve、GAFCMCR和BERAA算法，說(shuō)明CRIS-FCMP算法降低了每輪節(jié)點(diǎn)的能量消耗，從而能夠延長(zhǎng)CRIS-FCMP算法的網(wǎng)絡(luò)生命周期。這主要得益于均勻的網(wǎng)絡(luò)分簇均衡了簇首的負(fù)載；其次簇首的選舉考慮了與簇內(nèi)其他成員的距離的均衡性，降低了簇內(nèi)其他節(jié)點(diǎn)的能耗，簇首的選舉還考慮了與平均剩余能量和最大剩余能量的關(guān)系，降低了低能量節(jié)點(diǎn)選為簇首的概率。最重要的是CRIS-FCMP算法為簇首規(guī)劃了路由，且考慮了中繼節(jié)點(diǎn)的合理性，進(jìn)一步均衡了簇首的負(fù)載，而EBRAA算法雖然為簇首規(guī)劃了路由，但中繼節(jié)點(diǎn)僅在簇首中選取，且未考慮中繼節(jié)點(diǎn)的負(fù)載因素，加劇了簇首能耗。

5 結(jié)語(yǔ)

為了提升FCM算法的收斂速度使其可應(yīng)用于大規(guī)模且對(duì)實(shí)時(shí)性要求高的網(wǎng)絡(luò)環(huán)境，并延長(zhǎng)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)生命周期，提出了CRIS-FCMP算法。簇的形成階段，采用改進(jìn)SFCM算法進(jìn)行網(wǎng)絡(luò)分簇，以進(jìn)一步提升網(wǎng)絡(luò)分簇時(shí)的收斂速度。簇首選舉階段結(jié)合簇內(nèi)節(jié)點(diǎn)的剩余能量關(guān)系設(shè)計(jì)節(jié)點(diǎn)動(dòng)態(tài)能量閾值，并參照距離順序選舉簇首。數(shù)據(jù)傳輸階段，依據(jù)中繼節(jié)點(diǎn)能量、距離及負(fù)載因素結(jié)合PSO算法搜尋簇首路由。仿真分析表明，網(wǎng)絡(luò)分簇階段所用的IS-FCM算法相對(duì)FCM、S-FCM-(α=0.5)算法能夠有效提升合理分類(lèi)的收斂速度。此外，CRIS-FCMP算法相對(duì)已有算法能夠有效均衡節(jié)點(diǎn)負(fù)載，延長(zhǎng)網(wǎng)絡(luò)生命周期。

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)生命周期還受到其他因素的影響，比如移動(dòng)基站環(huán)境下的網(wǎng)絡(luò)路由規(guī)劃、三維網(wǎng)絡(luò)的拓?fù)渥兓龋祟?lèi)影響因素的問(wèn)題有待進(jìn)一步研究。