武小年，張楚蕓，張潤(rùn)蓮,2，孫亞平

（1.桂林電子科技大學(xué)廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004；2.桂林電子科技大學(xué)廣西高校云計(jì)算與復(fù)雜系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004）

1 引言

在無(wú)線傳感器網(wǎng)絡(luò)（WSN,wireless sensor network）中，傳統(tǒng)分簇路由協(xié)議通過簇頭節(jié)點(diǎn)進(jìn)行數(shù)據(jù)融合并發(fā)給基站，以減少網(wǎng)絡(luò)通信量，降低網(wǎng)絡(luò)能耗。但由于簇頭節(jié)點(diǎn)承擔(dān)的任務(wù)過重，加快了其能量消耗，縮短了網(wǎng)絡(luò)生存周期。為分擔(dān)簇頭節(jié)點(diǎn)的任務(wù)并避免簇頭節(jié)點(diǎn)離基站太遠(yuǎn)而加劇消耗，現(xiàn)有的分簇路由協(xié)議通常會(huì)選擇離基站盡可能近的轉(zhuǎn)發(fā)節(jié)點(diǎn)，由簇頭節(jié)點(diǎn)將融合的數(shù)據(jù)發(fā)給轉(zhuǎn)發(fā)節(jié)點(diǎn)，再由轉(zhuǎn)發(fā)節(jié)點(diǎn)將數(shù)據(jù)發(fā)給基站。但若轉(zhuǎn)發(fā)節(jié)點(diǎn)數(shù)量太少，節(jié)點(diǎn)的任務(wù)將非常繁重；若采用單跳方式向基站發(fā)送數(shù)據(jù)，當(dāng)節(jié)點(diǎn)與基站距離超過閾值時(shí)，節(jié)點(diǎn)的通信開銷將激增。如何在WSN路由協(xié)議中合理選舉簇頭節(jié)點(diǎn)與轉(zhuǎn)發(fā)節(jié)點(diǎn)，并優(yōu)化轉(zhuǎn)發(fā)節(jié)點(diǎn)的傳輸路徑、均衡和降低網(wǎng)絡(luò)通信開銷、延長(zhǎng)網(wǎng)絡(luò)生存周期是有待優(yōu)化的問題。

針對(duì)WSN路由協(xié)議面臨的上述問題，文獻(xiàn)[1]采用隨機(jī)分簇策略和周期性簇頭輪換維持節(jié)點(diǎn)的能量平衡；文獻(xiàn)[2]采用基于跳數(shù)和能量的分層自治系統(tǒng)實(shí)現(xiàn)合理的路由選擇；文獻(xiàn)[3]采用中繼節(jié)點(diǎn)分擔(dān)簇頭的數(shù)據(jù)傳輸任務(wù)以降低簇頭的能耗；文獻(xiàn)[4]采用基于虛擬交叉區(qū)域的樹型路由協(xié)議降低數(shù)據(jù)傳輸延遲；文獻(xiàn)[5]通過等間距環(huán)形劃分和等夾角扇形劃分的非均勻分簇方式保證源節(jié)點(diǎn)與基站的通信距離最短；文獻(xiàn)[6]采用基于節(jié)點(diǎn)接收基站信號(hào)強(qiáng)度和剩余能量的簇頭選擇方法避免頻繁更換簇頭；文獻(xiàn)[7]采用基于壓縮感知的聚類路由協(xié)議確定簇的通信半徑以延長(zhǎng)網(wǎng)絡(luò)壽命。

粒子群優(yōu)化（PSO,particle swarm optimization）算法是一種基于種群的群智能優(yōu)化算法，具有實(shí)現(xiàn)簡(jiǎn)單、收斂速度快和搜索精度高等特點(diǎn)，在解決組合優(yōu)化問題上相比其他算法有很大優(yōu)勢(shì)[8]。文獻(xiàn)[9]采用動(dòng)態(tài)調(diào)節(jié)簇內(nèi)節(jié)點(diǎn)數(shù)的改進(jìn)粒子群算法減少簇頭節(jié)點(diǎn)能耗；文獻(xiàn)[10]采用基于粒子位置和速度的重編碼方式增加網(wǎng)絡(luò)覆蓋面積；文獻(xiàn)[11]通過優(yōu)化網(wǎng)絡(luò)覆蓋率和鏈路質(zhì)量的方式提高網(wǎng)絡(luò)能量效率，但這3個(gè)算法未考慮粒子群算法中相關(guān)因素對(duì)最優(yōu)分簇的影響。文獻(xiàn)[12]采用基于離散的粒子群算法選擇簇頭和中繼節(jié)點(diǎn)構(gòu)建最優(yōu)簇結(jié)構(gòu)；文獻(xiàn)[13]通過調(diào)整慣性權(quán)重系數(shù)避免算法陷入局部最優(yōu)；文獻(xiàn)[14]采用基于模糊和網(wǎng)絡(luò)編碼的改進(jìn)型粒子群算法構(gòu)建節(jié)點(diǎn)到基站的最佳傳輸路徑，并未考慮轉(zhuǎn)發(fā)節(jié)點(diǎn)的通信開銷。

綜上所述，現(xiàn)有簇頭節(jié)點(diǎn)選取方法主要根據(jù)剩余能量篩選，部分方法考慮了簇頭節(jié)點(diǎn)與基站的距離，但未考慮簇頭節(jié)點(diǎn)位置的均衡性，而位置分布均衡的簇頭節(jié)點(diǎn)，能夠有效縮短通信的總距離，降低網(wǎng)絡(luò)通信開銷；其次，現(xiàn)有分簇路由協(xié)議大多選取的轉(zhuǎn)發(fā)節(jié)點(diǎn)太少，加大了轉(zhuǎn)發(fā)節(jié)點(diǎn)的能耗，而部分增加了轉(zhuǎn)發(fā)節(jié)點(diǎn)的協(xié)議，主要采用隨機(jī)方式進(jìn)行選取，其有可能與簇頭節(jié)點(diǎn)重復(fù)，且未考慮被選取節(jié)點(diǎn)的剩余能量及位置是否均衡；第三，現(xiàn)有協(xié)議中轉(zhuǎn)發(fā)節(jié)點(diǎn)采用單跳與多跳相結(jié)合的方式發(fā)送數(shù)據(jù)，靠近基站的轉(zhuǎn)發(fā)節(jié)點(diǎn)采取單跳方式，采用多跳方式時(shí)主要考慮相鄰轉(zhuǎn)發(fā)節(jié)點(diǎn)的距離，缺乏考慮節(jié)點(diǎn)能量及面向基站的方向性，導(dǎo)致能量受限和路徑不合理增加開銷?；诹Ｗ尤核惴ǖ膮f(xié)議未能充分利用粒子群算法的優(yōu)勢(shì)，并對(duì)算法存在的不足進(jìn)行優(yōu)化，如粒子初始化的隨機(jī)性容易導(dǎo)致節(jié)點(diǎn)分布不均衡并陷入局部最優(yōu)；在速度更新計(jì)算中，固定的學(xué)習(xí)因子和慣性權(quán)重?zé)o法平衡局部搜索和全局搜索的能力，使算法的收斂速度緩慢，較難獲得高質(zhì)量的簇頭節(jié)點(diǎn)集等。

針對(duì)上述問題，本文提出一種基于改進(jìn)粒子群算法的分簇路由協(xié)議（CRIPSO,clustering routing protocol based on improved PSO algorithm in WSN），基于節(jié)點(diǎn)的能量和位置評(píng)估來(lái)篩選候選簇頭節(jié)點(diǎn)；通過優(yōu)化粒子群算法的慣性系數(shù)和學(xué)習(xí)因子，平衡算法的全局搜索與局部探索能力，選舉出能量和位置合理的簇頭節(jié)點(diǎn)，構(gòu)建最優(yōu)分簇；建立基于最小生成樹的轉(zhuǎn)發(fā)節(jié)點(diǎn)多跳數(shù)據(jù)傳輸路徑，縮短通信距離。

2 系統(tǒng)模型

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

首先對(duì)網(wǎng)絡(luò)模型做如下約定。

1)WSN的實(shí)驗(yàn)區(qū)域形狀為平面規(guī)則圖形，傳感器節(jié)點(diǎn)在監(jiān)測(cè)區(qū)域中隨機(jī)不均勻分布且固定不動(dòng)，每個(gè)節(jié)點(diǎn)由一個(gè)全局唯一的ID標(biāo)識(shí)。

2)基站的能量不受限，其他所有傳感器節(jié)點(diǎn)能量有限，但各節(jié)點(diǎn)的初始能量相同，處理能力和通信能力相等。

3)節(jié)點(diǎn)無(wú)線發(fā)射功率可以自我調(diào)控，可自主選擇發(fā)射功率。

2.2 能耗模型

WSN中，傳感器節(jié)點(diǎn)的能耗主要包括通信能耗（如數(shù)據(jù)發(fā)送能耗與數(shù)據(jù)接收能耗）和數(shù)據(jù)處理能耗（如數(shù)據(jù)融合能耗），通信能耗與通信環(huán)境、傳輸距離、數(shù)據(jù)分組的大小有關(guān)。本文采用低功耗自適應(yīng)分簇分層（LEACH,low energy adaptive clustering hierarchy）[1]的能耗模型，根據(jù)距離的不同分別采用自由空間模型或多路衰減模型。以d表示發(fā)射節(jié)點(diǎn)和接收節(jié)點(diǎn)之間的距離，d0表示門限距離；以Efs和Emp分別表示自由空間模型和多路衰減模型的功放因子參數(shù)；m表示一個(gè)數(shù)據(jù)分組的比特?cái)?shù)，Eelec表示每傳輸1 bit數(shù)據(jù)的能耗，EDA表示每融合1 bit數(shù)據(jù)的能耗，則距離為d的2個(gè)節(jié)點(diǎn)傳輸mbit數(shù)據(jù)的發(fā)送能耗ETX(m,d)和接收能耗ERX(m,d)，以及融合mbit數(shù)據(jù)的融合能耗EDA(m,d)計(jì)算方法分別為

3 基于改進(jìn)粒子群算法的分簇路由算法

合理的分簇劃分及轉(zhuǎn)發(fā)節(jié)點(diǎn)選取，將有利于縮短通信距離，降低并均衡節(jié)點(diǎn)通信開銷，延長(zhǎng)網(wǎng)絡(luò)生存周期。本文改進(jìn)粒子群算法選舉能量與位置最優(yōu)的簇頭節(jié)點(diǎn)和轉(zhuǎn)發(fā)節(jié)點(diǎn)，以降低和均衡網(wǎng)絡(luò)通信開銷。

3.1 簇頭選舉

3.1.1 簇頭初始化

由于粒子群算法計(jì)算相對(duì)復(fù)雜，為避免選舉計(jì)算增加節(jié)點(diǎn)的能耗，基于粒子群算法的分簇及路由選擇計(jì)算都將由能量不受限的基站完成。在初始化過程中，所有節(jié)點(diǎn)將自身剩余能量、位置和編號(hào)信息發(fā)送給基站，基站接收并保存各節(jié)點(diǎn)的信息。在基站完成基于粒子群算法的分簇計(jì)算后，將計(jì)算結(jié)果進(jìn)行廣播，每一個(gè)存活節(jié)點(diǎn)根據(jù)接收的廣播信息獲得被選舉節(jié)點(diǎn)及路由選擇節(jié)點(diǎn)的具體位置信息。由基站完成粒子群算法的計(jì)算工作，實(shí)現(xiàn)選舉和分簇的優(yōu)化；各節(jié)點(diǎn)則不用進(jìn)行復(fù)雜的計(jì)算，以有效節(jié)省節(jié)點(diǎn)的能耗。

粒子群算法采用隨機(jī)方式選取粒子，傳統(tǒng)的分簇路由協(xié)議也大多采用隨機(jī)方式選取簇頭，這容易陷入局部最優(yōu)，導(dǎo)致簇內(nèi)節(jié)點(diǎn)分布不均衡；且若被選取的節(jié)點(diǎn)能量過低，其難以承擔(dān)簇頭節(jié)點(diǎn)的繁重任務(wù)。針對(duì)該問題，對(duì)參與簇頭節(jié)點(diǎn)選舉的節(jié)點(diǎn)能量進(jìn)行限制。

假設(shè)WSN中有N個(gè)存活節(jié)點(diǎn)，節(jié)點(diǎn)i的能量為E(i)，基站計(jì)算WSN中所有節(jié)點(diǎn)的平均剩余能量為

為保證選出的簇頭節(jié)點(diǎn)有充足的能量進(jìn)行簇內(nèi)數(shù)據(jù)的處理，基站將所有能量大于或等于Eavg的節(jié)點(diǎn)構(gòu)成一個(gè)集合EA，再采用隨機(jī)方式，從EA中選擇K個(gè)節(jié)點(diǎn)，存入候選簇頭節(jié)點(diǎn)集，構(gòu)成一個(gè)粒子。在初始確定了一組候選簇頭節(jié)點(diǎn)后，其他的非簇頭節(jié)點(diǎn)分別加入與其距離最近的簇頭節(jié)點(diǎn)，完成初始分簇的建立。

采用隨機(jī)方式在EA中繼續(xù)選擇K個(gè)節(jié)點(diǎn)，一共進(jìn)行M次篩選，最終生成M組初始簇頭節(jié)點(diǎn)集，即M個(gè)粒子，并形成M組的分簇。

3.1.2 適應(yīng)度函數(shù)

因簇頭節(jié)點(diǎn)能耗大，以節(jié)點(diǎn)剩余能量作為一個(gè)評(píng)價(jià)指標(biāo)有利于選出更高能量的簇頭節(jié)點(diǎn)；簇頭所在位置在網(wǎng)絡(luò)中分布越均衡，簇頭與非簇頭節(jié)點(diǎn)、基站的距離越小，通信開銷將越小。為從M組初始簇頭節(jié)點(diǎn)集中選舉出最優(yōu)的候選簇頭節(jié)點(diǎn)集作為簇頭節(jié)點(diǎn)集，以節(jié)點(diǎn)的剩余能量和位置作為評(píng)價(jià)指標(biāo)，構(gòu)建適應(yīng)度函數(shù)對(duì)各個(gè)候選簇頭節(jié)點(diǎn)集進(jìn)行評(píng)估。

適應(yīng)度函數(shù)要對(duì)初始簇頭節(jié)點(diǎn)集中的所有候選簇頭節(jié)點(diǎn)進(jìn)行綜合評(píng)估，這需要考慮所有候選簇頭節(jié)點(diǎn)的平均能量與均衡位置。適應(yīng)度函數(shù)值越大，表明選出的簇頭節(jié)點(diǎn)集越優(yōu)。

1)能量因子

能量因子是候選簇頭節(jié)點(diǎn)集中所有候選簇頭節(jié)點(diǎn)的平均剩余能量與所有非簇頭節(jié)點(diǎn)的平均剩余能量的比值。候選簇頭節(jié)點(diǎn)集的平均剩余能量越大，能量因子的值越大。以N表示W(wǎng)SN中的存活節(jié)點(diǎn)數(shù)量，一個(gè)候選簇頭節(jié)點(diǎn)集中有K個(gè)候選簇頭節(jié)點(diǎn)，則非簇頭節(jié)點(diǎn)為N-K個(gè)；以表示第r輪中候選簇頭節(jié)點(diǎn)CHi的剩余能量，表示第r輪中非簇頭節(jié)點(diǎn)NCHj的剩余能量，則能量因子f1的計(jì)算式為

2)位置均衡因子

位置均衡因子通過通信距離來(lái)描述候選簇頭節(jié)點(diǎn)在WSN中的分布狀態(tài)，是候選簇頭節(jié)點(diǎn)集中所有候選簇頭節(jié)點(diǎn)與基站的距離與每個(gè)候選簇頭節(jié)點(diǎn)與該分簇內(nèi)非簇頭節(jié)點(diǎn)的距離之和，與所有非簇頭節(jié)點(diǎn)與基站距離的反比。對(duì)于具有N個(gè)存活節(jié)點(diǎn)的WSN，有K個(gè)候選的簇頭節(jié)點(diǎn)，N–K個(gè)非簇頭節(jié)點(diǎn)；以d(NCHi,BS)表示非簇頭節(jié)點(diǎn)NCHi與基站BS之間的距離，d(CHj,BS)表示簇頭節(jié)點(diǎn)CHj與基站BS之間的距離，d(NCHi,CHj)表示非簇頭節(jié)點(diǎn)NCHi到其對(duì)應(yīng)的候選簇頭節(jié)點(diǎn)CHj的距離，則候選簇頭節(jié)點(diǎn)集位置均衡因子f2的計(jì)算式為

其中，非簇頭節(jié)點(diǎn)NCHi位于簇頭節(jié)點(diǎn)CHj所在的分簇內(nèi)。候選簇頭節(jié)點(diǎn)集距離基站越近，各分簇內(nèi)非簇頭節(jié)點(diǎn)到簇頭節(jié)點(diǎn)的距離越小，則網(wǎng)絡(luò)通信距離越短，候選簇頭節(jié)點(diǎn)集的位置在WSN中分布越均衡，f2的值越大。

基于能量因子和位置均衡因子，對(duì)候選簇頭節(jié)點(diǎn)集采用加權(quán)方式計(jì)算適應(yīng)度，適應(yīng)度值函數(shù)F1計(jì)算方法為

其中，a∈(0,1]是權(quán)重系數(shù)，根據(jù)WSN對(duì)剩余能量和位置均衡的需求不同，可以調(diào)整權(quán)值。在適應(yīng)度函數(shù)中，候選簇頭節(jié)點(diǎn)集的剩余能量越大，位置分布越均衡，則適應(yīng)度值越大，選出的候選簇頭節(jié)點(diǎn)集越優(yōu)。

針對(duì)M組初始簇頭節(jié)點(diǎn)集，完成對(duì)其中各組候選簇頭節(jié)點(diǎn)集的適應(yīng)度函數(shù)計(jì)算后，記錄每個(gè)候選簇頭節(jié)點(diǎn)集本身適應(yīng)度最大的位置作為每一組候選簇頭節(jié)點(diǎn)集的局部最優(yōu)位置（初始時(shí)為每個(gè)候選簇頭節(jié)點(diǎn)集自身的位置），初始M組簇頭節(jié)點(diǎn)集中最大適應(yīng)度函數(shù)值的候選簇頭節(jié)點(diǎn)集所在的位置為全局最優(yōu)位置。

3.1.3 速度與位置的更新方法

根據(jù)初始適應(yīng)度計(jì)算及初始產(chǎn)生的局部最優(yōu)位置和全局最優(yōu)位置，開始進(jìn)行一輪迭代計(jì)算，首先對(duì)候選簇頭節(jié)點(diǎn)集的位置更新，再計(jì)算位置更新后候選簇頭節(jié)點(diǎn)的適應(yīng)度。為完成對(duì)候選簇頭節(jié)點(diǎn)集的位置更新并獲得優(yōu)化結(jié)果，設(shè)置一個(gè)速度來(lái)控制其變化過程。速度是矢量，設(shè)候選簇頭節(jié)點(diǎn)在x和y方向上的速度分量分別為vxid和vyid，位置分量分別為xxid和xyid。2個(gè)速度分量的計(jì)算，初始時(shí)通過隨機(jī)生成，但在后續(xù)的每一輪迭代中根據(jù)候選簇頭節(jié)點(diǎn)集前一輪的速度分量與局部最優(yōu)位置(pxid,pyid)和全局最優(yōu)位置(pxgd,pygd)的變化關(guān)系確定，具體計(jì)算方法[15]為

其中，w是慣性權(quán)值，表示候選簇頭節(jié)點(diǎn)集前一輪t–1迭代的速度對(duì)本輪t迭代的候選簇頭節(jié)點(diǎn)集的速度的影響程度；c1是認(rèn)知學(xué)習(xí)因子，c2是社會(huì)學(xué)習(xí)因子，分別表示候選簇頭節(jié)點(diǎn)集靠近局部最優(yōu)位置和全局最優(yōu)位置的加速權(quán)值；r1,r2∈(0,1)為隨機(jī)數(shù)，借鑒仿生學(xué)中的變異性，使簇頭節(jié)點(diǎn)集具有變異特性。

基于2個(gè)速度分量，候選簇頭節(jié)點(diǎn)在x和y方向上的位置分量xxid和xyid的計(jì)算方法為

3.1.4 具有自適應(yīng)的學(xué)習(xí)因子和慣性權(quán)重

在上述速度更新計(jì)算中，傳統(tǒng)基于粒子群算法的路由協(xié)議中的學(xué)習(xí)因子和慣性權(quán)重通常設(shè)置為固定值，無(wú)法平衡局部搜索能力和全局搜索能力，算法的收斂速度比較緩慢，較難獲得高質(zhì)量的簇頭節(jié)點(diǎn)集。

在最優(yōu)簇頭節(jié)點(diǎn)集的選取過程中，前期的迭代側(cè)重局部最優(yōu)搜索，后期的迭代側(cè)重全局最優(yōu)搜索。局部最優(yōu)搜索若搜索范圍小，算法將容易陷入局部最優(yōu)解，因此需要盡可能地?cái)U(kuò)大尋找最優(yōu)候選簇頭節(jié)點(diǎn)集的局部搜索范圍，以增強(qiáng)群體的多樣性；全局搜索則需要加快算法收斂，保持收斂速度和搜索效果的均衡。為達(dá)到該目標(biāo)，設(shè)置認(rèn)知學(xué)習(xí)因子c1和社會(huì)學(xué)習(xí)因子c2動(dòng)態(tài)變化，在逐步迭代過程中，使c1從大到小變化，c2從小到大變化。

為滿足2個(gè)學(xué)習(xí)因子的上述變化規(guī)律，結(jié)合傳統(tǒng)學(xué)習(xí)因子的固定值設(shè)置情況，構(gòu)造動(dòng)態(tài)變化的學(xué)習(xí)因子，計(jì)算方法為其中，t為本輪迭代次數(shù)，tmax為最大迭代次數(shù)。隨著迭代次數(shù)的變化，c1和c2動(dòng)態(tài)變化，滿足其變化規(guī)律，使算法能夠自適應(yīng)地在迭代前期擴(kuò)大局部搜索范圍，在迭代后期加快全局收斂速度。

在迭代過程中，慣性權(quán)值可以根據(jù)上一輪的速度影響本輪的搜索范圍。在每一輪迭代結(jié)束都要對(duì)選取的候選簇頭節(jié)點(diǎn)集進(jìn)行適應(yīng)度函數(shù)計(jì)算，以適應(yīng)度值的結(jié)果動(dòng)態(tài)調(diào)整慣性權(quán)值，使本輪迭代中選取的簇頭節(jié)點(diǎn)集具有更均衡的位置。在此，采用非線性自適應(yīng)慣性權(quán)重策略[16]計(jì)算慣性權(quán)值，方法為

其中，wmax和wmin分別為設(shè)置的最大和最小慣性權(quán)重，fi為候選簇頭節(jié)點(diǎn)CHi的適應(yīng)度值，fmin、fmax和favg分別表示本輪候選簇頭節(jié)點(diǎn)集的最小、最大和平均適應(yīng)度值。當(dāng)fi＞favg時(shí)，本次候選簇頭節(jié)點(diǎn)的速度主要參考上一輪的速度，增加候選簇頭節(jié)點(diǎn)集的活躍度；反之，本次候選簇頭節(jié)點(diǎn)的速度主要參考局部最優(yōu)位置和全局最優(yōu)位置，加速候選簇頭節(jié)點(diǎn)集向優(yōu)勢(shì)空間靠近。

3.1.5 位置映射策略

在每一輪迭代后，候選簇頭節(jié)點(diǎn)集的位置都將被更新，可能會(huì)出現(xiàn)更新后的節(jié)點(diǎn)位置在WSN中找不到匹配的存活節(jié)點(diǎn)。此時(shí)，需要進(jìn)行位置映射處理[11]，基本思路是采取就近原則，將更新后的位置映射到距離該位置最近的存活節(jié)點(diǎn)所在的位置。以Xxid、Xyid為更新后的節(jié)點(diǎn)坐標(biāo)，CMnx、CMny為網(wǎng)絡(luò)中存活節(jié)點(diǎn)CMn的坐標(biāo)，位置映射處理過程為

位置映射策略解決了網(wǎng)絡(luò)節(jié)點(diǎn)分布離散所帶來(lái)的更新后的位置與實(shí)際存活節(jié)點(diǎn)位置不匹配的情況。當(dāng)出現(xiàn)多個(gè)節(jié)點(diǎn)更新后的位置坐標(biāo)一樣時(shí)，需要在更新節(jié)點(diǎn)的同時(shí)設(shè)置一個(gè)標(biāo)志位，其他節(jié)點(diǎn)更新并進(jìn)行位置映射時(shí)先檢查標(biāo)志位是否已經(jīng)被標(biāo)識(shí)為簇頭節(jié)點(diǎn)，若是則依次選擇距離次近的節(jié)點(diǎn)位置進(jìn)行映射。

完成位置映射后，將位置更新后的各候選簇頭節(jié)點(diǎn)集作為優(yōu)化結(jié)果，計(jì)算各候選簇頭節(jié)點(diǎn)集的適應(yīng)度值。根據(jù)計(jì)算結(jié)果，更新每一組候選簇頭節(jié)點(diǎn)集的局部最優(yōu)位置以及本輪M組簇頭節(jié)點(diǎn)集的全局最優(yōu)位置。若迭代未結(jié)束，則繼續(xù)進(jìn)行候選簇頭節(jié)點(diǎn)的位置更新與映射；否則，最后計(jì)算出的全局最優(yōu)位置的候選簇頭節(jié)點(diǎn)集作為最優(yōu)簇頭節(jié)點(diǎn)集，簇頭選舉完成。

基站在完成簇頭選舉后，進(jìn)一步計(jì)算非簇頭節(jié)點(diǎn)到各個(gè)簇頭節(jié)點(diǎn)的距離，將非簇頭節(jié)點(diǎn)加入距離最近的簇頭節(jié)點(diǎn)，完成分簇。此時(shí)，傳感器節(jié)點(diǎn)分為簇頭節(jié)點(diǎn)和普通節(jié)點(diǎn)。普通節(jié)點(diǎn)僅進(jìn)行數(shù)據(jù)發(fā)送，將自身監(jiān)測(cè)的數(shù)據(jù)融合后單跳發(fā)送給簇頭節(jié)點(diǎn)；簇頭節(jié)點(diǎn)接收來(lái)自普通節(jié)點(diǎn)的數(shù)據(jù)后進(jìn)行數(shù)據(jù)融合，再發(fā)送給相應(yīng)的轉(zhuǎn)發(fā)節(jié)點(diǎn)。轉(zhuǎn)發(fā)節(jié)點(diǎn)需要進(jìn)一步從普通節(jié)點(diǎn)中選取，其接收來(lái)自簇頭的數(shù)據(jù)，并選擇到基站的最優(yōu)路徑，將數(shù)據(jù)發(fā)送給基站。

在上述基于粒子群算法的分簇計(jì)算中，每一次分簇都需要重新獲取各節(jié)點(diǎn)的剩余能量。針對(duì)下一次分簇的開啟和期間各節(jié)點(diǎn)的通信交互，在此采用捎帶技術(shù)以減少通信開銷，即各節(jié)點(diǎn)完成數(shù)據(jù)采集和處理后，將自身剩余能量添加在數(shù)據(jù)后面一起發(fā)送給簇頭節(jié)點(diǎn)；簇頭節(jié)點(diǎn)進(jìn)行數(shù)據(jù)融合，也將自身剩余能量與融合數(shù)據(jù)通過轉(zhuǎn)發(fā)節(jié)點(diǎn)發(fā)送到基站；同樣，轉(zhuǎn)發(fā)節(jié)點(diǎn)將自身剩余能量捎帶一起發(fā)送；基站在收到數(shù)據(jù)后，記錄收到的各節(jié)點(diǎn)的剩余能量信息和數(shù)據(jù)，根據(jù)收到的節(jié)點(diǎn)剩余能量信息進(jìn)行新一輪的分簇選舉。各節(jié)點(diǎn)捎帶的剩余能量信息為當(dāng)前節(jié)點(diǎn)能量減去本次數(shù)據(jù)發(fā)送需要消耗的能量。

3.2 轉(zhuǎn)發(fā)節(jié)點(diǎn)的選舉與多跳傳輸

3.2.1 選舉轉(zhuǎn)發(fā)節(jié)點(diǎn)

在完成簇頭節(jié)點(diǎn)選舉后，將為簇頭節(jié)點(diǎn)選擇對(duì)應(yīng)的轉(zhuǎn)發(fā)節(jié)點(diǎn)。若網(wǎng)絡(luò)中的轉(zhuǎn)發(fā)節(jié)點(diǎn)過少，多個(gè)簇頭節(jié)點(diǎn)通過少量轉(zhuǎn)發(fā)節(jié)點(diǎn)向基站發(fā)送數(shù)據(jù)，將加大轉(zhuǎn)發(fā)節(jié)點(diǎn)的能耗。針對(duì)該問題，現(xiàn)有的WSN路由協(xié)議采取一個(gè)簇頭節(jié)點(diǎn)對(duì)應(yīng)一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)的方式[11]，增加轉(zhuǎn)發(fā)節(jié)點(diǎn)的數(shù)量，但其采用隨機(jī)方式在所有節(jié)點(diǎn)中選取，未考慮被選取節(jié)點(diǎn)的剩余能量及位置是否均衡。

本文在轉(zhuǎn)發(fā)節(jié)點(diǎn)選舉時(shí)，采用上述簇頭節(jié)點(diǎn)選舉的改進(jìn)粒子群算法，為每個(gè)簇頭節(jié)點(diǎn)在其分簇內(nèi)的普通節(jié)點(diǎn)中選舉一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)，使被選舉出的轉(zhuǎn)發(fā)節(jié)點(diǎn)具有最優(yōu)的能量和位置關(guān)系，并避免WSN中轉(zhuǎn)發(fā)節(jié)點(diǎn)過少而加快其能量消耗。

在對(duì)轉(zhuǎn)發(fā)節(jié)點(diǎn)計(jì)算和評(píng)估中，由于轉(zhuǎn)發(fā)節(jié)點(diǎn)只能在一個(gè)分簇內(nèi)選舉，能量因子和位置均衡因子的計(jì)算方法與簇頭節(jié)點(diǎn)選舉的計(jì)算方法有所區(qū)別。

同樣以N表示W(wǎng)SN中的存活節(jié)點(diǎn)數(shù)量，在選舉出K個(gè)簇頭節(jié)點(diǎn)后，WSN被分為K個(gè)分簇，初始化時(shí)根據(jù)簇頭節(jié)點(diǎn)篩選的方法，在各個(gè)分簇內(nèi)篩選出較高剩余能量的候選轉(zhuǎn)發(fā)節(jié)點(diǎn)，組成候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集，每個(gè)候選集中包含K個(gè)節(jié)點(diǎn)。

在初始化后，普通節(jié)點(diǎn)數(shù)量為N–2K，以表示第r輪中候選轉(zhuǎn)發(fā)節(jié)點(diǎn)RNi的剩余能量，表示第r輪中普通節(jié)點(diǎn)CNj的剩余能量，能量因子fit1的計(jì)算式為

以d(CNk,CHj)表示普通節(jié)點(diǎn)CNk到對(duì)應(yīng)的簇頭節(jié)點(diǎn)CHj之間距離，d(RNi,BS)表示轉(zhuǎn)發(fā)節(jié)點(diǎn)RNi到基站BS的距離，d(RNi,CHj)表示轉(zhuǎn)發(fā)節(jié)點(diǎn)RNi到對(duì)應(yīng)的簇頭節(jié)點(diǎn)CHj的距離，d(RNi,RNm)表示轉(zhuǎn)發(fā)節(jié)點(diǎn)RNi和RNm之間的距離，轉(zhuǎn)發(fā)節(jié)點(diǎn)位置均衡因子fit2計(jì)算方法為

其中，普通節(jié)點(diǎn)CNk位于簇頭節(jié)點(diǎn)CHj所在的分簇內(nèi)；候選轉(zhuǎn)發(fā)節(jié)點(diǎn)RNi對(duì)應(yīng)于簇頭節(jié)點(diǎn)CHj。候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集距離基站越近，各分簇內(nèi)簇頭節(jié)點(diǎn)與轉(zhuǎn)發(fā)節(jié)點(diǎn)的距離越小，候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集中各轉(zhuǎn)發(fā)節(jié)點(diǎn)之間的距離越小，候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集的位置分布越均衡，fit2值越大。

基于候選轉(zhuǎn)發(fā)節(jié)點(diǎn)選舉的能力因子和位置均衡因子，采用加權(quán)方法構(gòu)建的對(duì)候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集評(píng)價(jià)的適應(yīng)度函數(shù)F2為

其中，b∈(0,1]為權(quán)值。候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集剩余能量越高，位置越均衡，則候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集的適應(yīng)度值將越大，表明候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集越優(yōu)。

在候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集的多次迭代選舉過程中，采用與簇頭節(jié)點(diǎn)選舉類似的速度更新及位置映射方法，選出最優(yōu)的轉(zhuǎn)發(fā)節(jié)點(diǎn)集。

3.2.2 轉(zhuǎn)發(fā)節(jié)點(diǎn)的多跳傳輸

基于LEACH能耗模型[1]，若基站遠(yuǎn)離WSN，轉(zhuǎn)發(fā)節(jié)點(diǎn)與基站的距離d大于門限距離d0，發(fā)送能耗量級(jí)為d4；但若d≤d0，則節(jié)點(diǎn)間數(shù)據(jù)傳輸能耗大大降低，其能耗級(jí)數(shù)為d2。在實(shí)際應(yīng)用中，基站通常遠(yuǎn)離WSN。現(xiàn)有WSN路由算法中轉(zhuǎn)發(fā)節(jié)點(diǎn)常采用單跳的方式向基站轉(zhuǎn)發(fā)數(shù)據(jù)[13]，能耗過大；而采用多跳方式的算法主要根據(jù)轉(zhuǎn)發(fā)節(jié)點(diǎn)間的最短距離選擇多跳[17]，沒有考慮轉(zhuǎn)發(fā)節(jié)點(diǎn)的剩余能量；且未考慮基站方向，多跳路徑可能并非最短距離。

本文在選舉出最優(yōu)的轉(zhuǎn)發(fā)節(jié)點(diǎn)集后，將根據(jù)轉(zhuǎn)發(fā)節(jié)點(diǎn)與基站的距離d確定轉(zhuǎn)發(fā)節(jié)點(diǎn)采用單跳還是多跳方式向基站傳輸數(shù)據(jù)，若d＞d0，則該轉(zhuǎn)發(fā)節(jié)點(diǎn)采用多跳方式傳輸；否則該轉(zhuǎn)發(fā)節(jié)點(diǎn)采用單跳方式傳輸。

在轉(zhuǎn)發(fā)節(jié)點(diǎn)多跳路徑選擇中，本文利用構(gòu)造最小生成樹的方法搜索轉(zhuǎn)發(fā)節(jié)點(diǎn)多跳傳輸?shù)淖疃搪窂剑瑫r(shí)兼顧節(jié)點(diǎn)剩余能量，以在降低網(wǎng)絡(luò)能耗時(shí)，維持轉(zhuǎn)發(fā)節(jié)點(diǎn)消耗的均衡性。

轉(zhuǎn)發(fā)節(jié)點(diǎn)之間的路由以基站為樹根，開始時(shí)將每個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)抽象為點(diǎn)，把轉(zhuǎn)發(fā)節(jié)點(diǎn)用邊連接起來(lái)，構(gòu)造為一個(gè)帶權(quán)的連通圖G=(V,E)，其中，V包括所有轉(zhuǎn)發(fā)節(jié)點(diǎn)，E包括V中任意2個(gè)節(jié)點(diǎn)間的邊的集合。為搜索某個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)到基站的最優(yōu)路徑，需要綜合考慮在每一跳中相鄰2個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)間的距離與剩余能量。

假設(shè)以轉(zhuǎn)發(fā)節(jié)點(diǎn)RNi為起點(diǎn)，要搜索到基站所途經(jīng)的下一跳節(jié)點(diǎn)；若轉(zhuǎn)發(fā)節(jié)點(diǎn)RNj為RNi的鄰居轉(zhuǎn)發(fā)節(jié)點(diǎn)，則需要評(píng)估節(jié)點(diǎn)RNj能否作為下一跳節(jié)點(diǎn)，在此，以這2個(gè)節(jié)點(diǎn)的邊的權(quán)值來(lái)衡量，權(quán)值由2個(gè)節(jié)點(diǎn)的距離與剩余能量確定，并以wi,j表示。若節(jié)點(diǎn)RNj到基站的距離大于或等于節(jié)點(diǎn)RNi到基站的距離，則節(jié)點(diǎn)RNj不能作為下一跳節(jié)點(diǎn)，設(shè)置wi,j為∞；否則以2個(gè)節(jié)點(diǎn)的距離與剩余能量計(jì)算wi,j，計(jì)算方法為

其中，di,j表示轉(zhuǎn)發(fā)節(jié)點(diǎn)RNi與RNj之間的距離，di,BS表示轉(zhuǎn)發(fā)節(jié)點(diǎn)RNi與基站之間的距離，和分別表示第r輪轉(zhuǎn)發(fā)節(jié)點(diǎn)RNi、RNj的剩余能量。若2個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)的距離越大，剩余能量越小，則2個(gè)節(jié)點(diǎn)的權(quán)值越大，該鄰居轉(zhuǎn)發(fā)節(jié)點(diǎn)被選為下一跳的概率越小。若轉(zhuǎn)發(fā)節(jié)點(diǎn)RNi有多個(gè)相鄰的轉(zhuǎn)發(fā)節(jié)點(diǎn)，則分別計(jì)算轉(zhuǎn)發(fā)節(jié)點(diǎn)RNi與其他相鄰節(jié)點(diǎn)的權(quán)值，并選取權(quán)值最小的轉(zhuǎn)發(fā)節(jié)點(diǎn)作為其下一跳節(jié)點(diǎn)。

在每輪轉(zhuǎn)發(fā)節(jié)點(diǎn)選舉結(jié)束后，將采用上述最小生成樹方式建立轉(zhuǎn)發(fā)節(jié)點(diǎn)到基站的多跳路徑?；谧钚∩蓸涞亩嗵窂浇⒎椒ň唧w過程如下所示。在上述構(gòu)造的帶權(quán)連通圖G=(V,E)中，將基站v0作為樹的根節(jié)點(diǎn)加入V中，以U記錄最小生成樹的節(jié)點(diǎn)集合，W記錄待選擇的轉(zhuǎn)發(fā)節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)所構(gòu)成邊的權(quán)值集合，T記錄最小生成樹中邊的權(quán)值集合。

步驟1初始將根節(jié)點(diǎn)v0加入集合U中，T和W為空。

步驟2根據(jù)設(shè)置的門限距離d0，依次計(jì)算V中除v0外的某節(jié)點(diǎn)vi到v0的距離di,0，若di,0≤d0，則vi將采用單跳方式向基站傳輸數(shù)據(jù)，將vi加入U(xiǎn)中，設(shè)置vi與v0的邊的權(quán)值wi,0=0，并將wi,0加入T，轉(zhuǎn)至步驟5；否則，轉(zhuǎn)至步驟3，計(jì)算建立vi到v0的多跳路徑。

步驟3根據(jù)式(13)計(jì)算vi到其他所有轉(zhuǎn)發(fā)節(jié)點(diǎn)的邊的權(quán)值，并將其加入W中。

步驟4在W中選出最小的權(quán)值wi,k，此時(shí)，vi到v0的距離為di,0，vk到v0的距離為dk,0，計(jì)算vi到vk的距離di,k。若di,0≤di,k，或者ETX(m,di,BS)＜(ETX(m,di,j)+ETX(m,di,BS))，則由vi經(jīng)vk發(fā)送數(shù)據(jù)到v0的開銷更大，此時(shí)，vi將直接發(fā)送數(shù)據(jù)到v0，將節(jié)點(diǎn)vi加入U(xiǎn)中，設(shè)置vi與v0的邊的權(quán)值wi,0=0，并將wi,0加入T，并置W為空；否則，將節(jié)點(diǎn)vi加入U(xiǎn)中，并將wi,k加入T中，并置W為空。

步驟5若U=V，結(jié)束搜索，轉(zhuǎn)至步驟6；否則，轉(zhuǎn)至步驟2。

步驟6對(duì)于T中權(quán)值為0且后一個(gè)節(jié)點(diǎn)為v0的權(quán)值，將該權(quán)值對(duì)應(yīng)邊的前一個(gè)節(jié)點(diǎn)作為單跳節(jié)點(diǎn)輸出；否則，將權(quán)值對(duì)應(yīng)邊的前一個(gè)節(jié)點(diǎn)作為起點(diǎn)，后一個(gè)節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)，繼續(xù)查找下一跳節(jié)點(diǎn)，直到下一跳節(jié)點(diǎn)為v0，形成多跳路徑輸出。

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

在Matlab中模擬生成WSN，基站位于網(wǎng)絡(luò)之外。在此環(huán)境下實(shí)現(xiàn)基于改進(jìn)粒子群算法的路由協(xié)議并進(jìn)行測(cè)試。測(cè)試計(jì)算機(jī)配置為2.3 GHz Intel Core i5，8 GB內(nèi)存，64位Windows10。WSN初始化、簇頭節(jié)點(diǎn)與轉(zhuǎn)發(fā)節(jié)點(diǎn)選舉、數(shù)據(jù)處理的相關(guān)實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置如表1所示。

表1 實(shí)驗(yàn)參數(shù)設(shè)置

考慮到WSN一般相對(duì)穩(wěn)定，數(shù)據(jù)采集與數(shù)據(jù)處理的頻率不高，在此主要根據(jù)WSN的數(shù)據(jù)處理頻率來(lái)開啟新一輪的分簇選舉，即當(dāng)簇頭節(jié)點(diǎn)完成對(duì)簇內(nèi)節(jié)點(diǎn)數(shù)據(jù)的融合并發(fā)送給基站，基站收到數(shù)據(jù)后，將開始新一輪的分簇選舉。對(duì)于數(shù)據(jù)處理頻率較快的WSN情況，本文暫未考慮，但可以采用事件觸發(fā)發(fā)送，通過判斷簇頭節(jié)點(diǎn)的剩余能量來(lái)確定是否開啟新一輪的分簇選舉。

基于上述實(shí)驗(yàn)環(huán)境，測(cè)試適應(yīng)度函數(shù)不同權(quán)值對(duì)網(wǎng)絡(luò)的影響及本文協(xié)議CRIPSO下的節(jié)點(diǎn)能耗及網(wǎng)絡(luò)生存周期變化情況，并與LEACH[1]、IPSOCH[12]和NAPSO[13]進(jìn)行對(duì)比測(cè)試。

4.1 適應(yīng)度函數(shù)權(quán)值的選取實(shí)驗(yàn)

在式(4)和式(12)中，權(quán)值a與b體現(xiàn)能量因子與位置均衡因子對(duì)適應(yīng)度的影響程度。為設(shè)置合理的權(quán)值，根據(jù)節(jié)點(diǎn)剩余能量均方差評(píng)判協(xié)議采用不同權(quán)值進(jìn)行迭代計(jì)算和網(wǎng)絡(luò)運(yùn)行中節(jié)點(diǎn)能耗的均衡程度。均方差越小，不同節(jié)點(diǎn)的剩余能量差別較小，均衡性較好?；谏鲜龇抡姝h(huán)境，測(cè)試了本文協(xié)議在不同權(quán)值下運(yùn)行的節(jié)點(diǎn)剩余能量均方差，結(jié)果如圖1所示。

圖1 適應(yīng)度函數(shù)不同權(quán)值下的節(jié)點(diǎn)剩余能量均方差

圖1表明，能量因子和位置均衡因子在不同權(quán)值下，對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)的剩余能量與網(wǎng)絡(luò)生存周期的影響不同。當(dāng)能量因子與位置均衡因子對(duì)適應(yīng)度函數(shù)的影響不平衡時(shí)，即能量因子影響較大位置均衡因子影響較小，或者反過來(lái)，所測(cè)得的均方差都較大，表明網(wǎng)絡(luò)中節(jié)點(diǎn)的剩余能量差異較大，節(jié)點(diǎn)死亡較快，最終導(dǎo)致網(wǎng)絡(luò)生存周期下降。當(dāng)能量因子與位置權(quán)衡因子對(duì)適應(yīng)度函數(shù)的影響均衡，特別是當(dāng)a=b=0.5時(shí)，所測(cè)得的均方差最小，網(wǎng)絡(luò)迭代執(zhí)行的過程最長(zhǎng)，網(wǎng)絡(luò)生存周期最長(zhǎng)。在后續(xù)的實(shí)驗(yàn)中，令a=b=0.5。

4.2 協(xié)議性能對(duì)比實(shí)驗(yàn)與結(jié)果分析

實(shí)驗(yàn)1協(xié)議運(yùn)行能耗與生存周期

本文協(xié)議通過改進(jìn)粒子群算法及設(shè)計(jì)的轉(zhuǎn)發(fā)節(jié)點(diǎn)多跳傳輸路徑選擇方法，力圖構(gòu)建最優(yōu)分簇和最短多跳傳輸路徑。在上述實(shí)驗(yàn)環(huán)境下，對(duì)比測(cè)試了本文協(xié)議CRIPSO與LEACH、IPSOCH和NAPSO在2 500輪迭代中的節(jié)點(diǎn)存活數(shù)量及網(wǎng)絡(luò)生存周期的變化情況，實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 不同算法的網(wǎng)絡(luò)生存周期對(duì)比測(cè)試結(jié)果

圖2表明，隨著迭代次數(shù)的增加，4種協(xié)議的節(jié)點(diǎn)能耗增加，WSN中存活的節(jié)點(diǎn)數(shù)量逐漸減少，直至最終節(jié)點(diǎn)全部死亡。

LEACH協(xié)議中簇頭選舉采用基于閾值的方法且簇頭節(jié)點(diǎn)采用單跳傳輸，節(jié)點(diǎn)的能耗較大，在較短的時(shí)間內(nèi)，死亡的節(jié)點(diǎn)較多，WSN生存周期最短。IPSOCH協(xié)議利用改進(jìn)粒子群算法，通過節(jié)點(diǎn)的剩余能量信息和位置信息選擇簇頭和轉(zhuǎn)發(fā)節(jié)點(diǎn)，優(yōu)化了分簇，降低了節(jié)點(diǎn)能耗，相對(duì)LEACH協(xié)議節(jié)點(diǎn)死亡減緩，WSN生存周期延長(zhǎng)。但I(xiàn)PSOCH協(xié)議在計(jì)算位置時(shí)僅考慮節(jié)點(diǎn)與基站的距離，其選舉出來(lái)的簇頭節(jié)點(diǎn)集難以達(dá)到全局最優(yōu)。NAPSO協(xié)議增加了對(duì)慣性權(quán)重的改進(jìn)，相比于IPSOCH協(xié)議進(jìn)一步優(yōu)化了分簇，降低了節(jié)點(diǎn)能耗，其WSN生存周期較IPSOCH協(xié)議有所延長(zhǎng)。

本文協(xié)議CRIPSO基于能量因子與位置均衡因子評(píng)估候選簇頭節(jié)點(diǎn)集，并通過自適應(yīng)學(xué)習(xí)因子與慣性權(quán)重，選舉出最優(yōu)簇頭節(jié)點(diǎn)集和轉(zhuǎn)發(fā)節(jié)點(diǎn)集，并通過設(shè)計(jì)的最小生成樹多跳傳輸路徑選擇方法建立路由，并采用捎帶技術(shù)減少信息交互的開銷，相對(duì)于對(duì)比協(xié)議，降低了轉(zhuǎn)發(fā)節(jié)點(diǎn)的通信距離，降低并均衡了節(jié)點(diǎn)能耗，大大延長(zhǎng)了WSN生存周期。

實(shí)驗(yàn)2簇頭節(jié)點(diǎn)的位置均衡測(cè)試

位置均衡因子體現(xiàn)了簇頭節(jié)點(diǎn)集與轉(zhuǎn)發(fā)節(jié)點(diǎn)集在WSN中的分布均衡情況，節(jié)點(diǎn)分布的越均衡，則WSN通信中總的通信距離越小，節(jié)點(diǎn)能耗越低?；谏鲜鰧?shí)驗(yàn)環(huán)境，分別測(cè)試了本文協(xié)議CRIPSO與LEACH、IPSOCH和NAPSO協(xié)議在多次迭代中所有普通節(jié)點(diǎn)到簇頭距離的總和、所有簇頭節(jié)點(diǎn)到基站距離的總和，實(shí)驗(yàn)結(jié)果分別如圖3和圖4所示。

圖3 不同協(xié)議中普通節(jié)點(diǎn)到簇頭距離的總和

圖4 不同協(xié)議中簇頭到基站距離的總和

由圖3與圖4可知，隨著迭代次數(shù)的增加，4種協(xié)議中所有普通節(jié)點(diǎn)到簇頭的總距離、所有簇頭到基站的總距離都越來(lái)越小。

LEACH協(xié)議在簇頭選舉中未考慮節(jié)點(diǎn)的能量和位置，初始時(shí)圖3和圖4的2個(gè)距離都最大，但在987輪后2個(gè)距離迅速下降，這是因?yàn)槠渫ㄐ啪嚯x大，能耗大且不均衡，節(jié)點(diǎn)死亡較快，隨著存活節(jié)點(diǎn)大量減少，其通信距離減小，WSN生存周期大大縮短。IPSOCH協(xié)議考慮了位置信息，初始時(shí)其2個(gè)距離相對(duì)縮小，能耗有所降低，WSN生存周期延長(zhǎng)。NAPSO協(xié)議在慣性權(quán)重中的優(yōu)化，使選舉的簇頭節(jié)點(diǎn)向全局最優(yōu)靠攏，初始時(shí)測(cè)得的2個(gè)距離低于IPSOCH協(xié)議，節(jié)點(diǎn)能耗降低，WSN生存周期較IPSOCH有所延長(zhǎng)。IPSOCH和NAPSO協(xié)議同樣在迭代后期因死亡節(jié)點(diǎn)激增，存活節(jié)點(diǎn)較少，測(cè)得的2個(gè)距離都小于本文協(xié)議，但生存周期都更小。

本文協(xié)議CRIPSO在位置均衡因子中考慮了簇頭節(jié)點(diǎn)與基站的距離、每個(gè)簇頭節(jié)點(diǎn)與該分簇內(nèi)非簇頭節(jié)點(diǎn)的距離，以及所有非簇頭節(jié)點(diǎn)與基站的距離，且設(shè)計(jì)了優(yōu)化轉(zhuǎn)發(fā)節(jié)點(diǎn)通信路徑的多跳傳輸路徑選擇方法，使篩選的簇頭節(jié)點(diǎn)和轉(zhuǎn)發(fā)節(jié)點(diǎn)在WSN中位置均衡，初始時(shí)2個(gè)距離都最小，有效降低并均衡了節(jié)點(diǎn)能耗，死亡的節(jié)點(diǎn)數(shù)量呈線性緩慢下降，變化較為穩(wěn)定，延長(zhǎng)了WSN生存周期。

實(shí)驗(yàn)3自適應(yīng)學(xué)習(xí)因子的影響

在最優(yōu)簇頭節(jié)點(diǎn)集的選取過程中，前期的迭代側(cè)重局部最優(yōu)搜索，后期的迭代側(cè)重全局最優(yōu)搜索。在速度更新中，2個(gè)學(xué)習(xí)因子分別控制候選簇頭節(jié)點(diǎn)集靠近局部最優(yōu)位置和全局最優(yōu)位置的加速度。固定學(xué)習(xí)因子無(wú)法滿足迭代過程中的局部和全局最優(yōu)搜索變化需求，自適應(yīng)學(xué)習(xí)因子則給出了有效的解決方法。基于上述實(shí)驗(yàn)環(huán)境，分別對(duì)比測(cè)試了本文協(xié)議在固定學(xué)習(xí)因子和自適應(yīng)學(xué)習(xí)因子下的網(wǎng)絡(luò)生存周期變化情況。其中，固定學(xué)習(xí)因子時(shí)2個(gè)學(xué)習(xí)因子都設(shè)置為當(dāng)前常用的固定值，令c1=2，c2=2。實(shí)驗(yàn)結(jié)果如圖5所示。

圖5表明，隨著迭代次數(shù)增加，2種協(xié)議下的網(wǎng)絡(luò)節(jié)點(diǎn)能耗增加，存活節(jié)點(diǎn)逐步減少。采用固定學(xué)習(xí)因子的協(xié)議在2 004輪節(jié)點(diǎn)全部死亡，采用自適應(yīng)學(xué)習(xí)因子的協(xié)議的網(wǎng)絡(luò)生存周期延長(zhǎng)了100多輪。其原因在于自適應(yīng)學(xué)習(xí)因子在迭代前期加速候選簇頭節(jié)點(diǎn)集向局部最優(yōu)位置靠攏，擴(kuò)大了局部搜索能力，使選取的候選簇頭節(jié)點(diǎn)集能夠根據(jù)節(jié)點(diǎn)的剩余能量與位置均衡性進(jìn)行有效調(diào)整，并傾向于局部最優(yōu)；在迭代后期則逐步加速候選簇頭節(jié)點(diǎn)集向全局最優(yōu)位置靠攏，即加速算法進(jìn)行全局收斂，獲得節(jié)點(diǎn)剩余能量與位置均衡性全局最優(yōu)的簇頭節(jié)點(diǎn)，降低通信距離，降低并均衡網(wǎng)絡(luò)能耗，延長(zhǎng)了WSN生存周期。

圖5 不同的學(xué)習(xí)因子值對(duì)網(wǎng)絡(luò)的影響

實(shí)驗(yàn)4轉(zhuǎn)發(fā)節(jié)點(diǎn)傳輸路徑對(duì)比

轉(zhuǎn)發(fā)節(jié)點(diǎn)承擔(dān)了將WSN中的數(shù)據(jù)傳輸?shù)交镜娜蝿?wù)，數(shù)據(jù)量大且通信距離較長(zhǎng)。根據(jù)LEACH能耗模型，若轉(zhuǎn)發(fā)節(jié)點(diǎn)與基站的距離d大于門限距離d0，則發(fā)送能耗激增?？s短轉(zhuǎn)發(fā)節(jié)點(diǎn)集與基站的通信距離，將可以大大降低網(wǎng)絡(luò)能耗，延長(zhǎng)WSN生存周期?；谏鲜鐾瑯拥膶?shí)驗(yàn)環(huán)境，對(duì)比測(cè)試了本文協(xié)議CRIPSO與IPSOCH、NAPSO的轉(zhuǎn)發(fā)節(jié)點(diǎn)通信距離與網(wǎng)絡(luò)生存周期情況，實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 不同協(xié)議下的轉(zhuǎn)發(fā)節(jié)點(diǎn)到基站的總距離

圖6表明，隨著迭代次數(shù)的增加，3種協(xié)議中轉(zhuǎn)發(fā)節(jié)點(diǎn)到基站的總距離減少。IPSOCH協(xié)議和NAPSO協(xié)議在1 113輪后轉(zhuǎn)發(fā)節(jié)點(diǎn)到基站的總距離快速下降，低于本文協(xié)議CRIPSO，這是因?yàn)?種協(xié)議中轉(zhuǎn)發(fā)節(jié)點(diǎn)與基站均采用單跳方式進(jìn)行數(shù)據(jù)傳輸，遠(yuǎn)離基站的轉(zhuǎn)發(fā)節(jié)點(diǎn)在數(shù)據(jù)傳輸過程中采用多路衰減模型，節(jié)點(diǎn)能量衰減較快，轉(zhuǎn)發(fā)節(jié)點(diǎn)死亡較快，網(wǎng)絡(luò)中存活節(jié)點(diǎn)數(shù)量下降迅速，因此在開始時(shí)2種協(xié)議的總距離大于本文協(xié)議，在后期低于本文協(xié)議。

本文協(xié)議CRIPSO通過轉(zhuǎn)發(fā)節(jié)點(diǎn)的優(yōu)化選舉，及基于最小生成樹構(gòu)建轉(zhuǎn)發(fā)節(jié)點(diǎn)多跳傳輸路徑，大大縮短了轉(zhuǎn)發(fā)節(jié)點(diǎn)的通信距離，降低了網(wǎng)絡(luò)能耗，節(jié)點(diǎn)死亡速度較慢，故在0～1 002輪期間本文協(xié)議的總距離最?。缓笃谝虼婊罟?jié)點(diǎn)遠(yuǎn)多于2個(gè)對(duì)比協(xié)議，其通信距離高于2個(gè)對(duì)比協(xié)議，WSN生存周期更長(zhǎng)。

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

針對(duì)WSN分簇路由協(xié)議的分簇優(yōu)化與轉(zhuǎn)發(fā)節(jié)點(diǎn)的通信傳輸方法問題，提出一種基于改進(jìn)粒子群算法的WSN分簇路由協(xié)議。該協(xié)議基于節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)位置關(guān)系，優(yōu)化粒子群算法中的初始化篩選、適應(yīng)度函數(shù)及學(xué)習(xí)因子，實(shí)現(xiàn)簇頭節(jié)點(diǎn)的優(yōu)化選舉和分簇，保證簇頭節(jié)點(diǎn)的高能量，縮短網(wǎng)絡(luò)通信距離，均衡和降低通信開銷；并針對(duì)選舉的轉(zhuǎn)發(fā)節(jié)點(diǎn)，設(shè)計(jì)一種基于最小生成樹的多跳路徑選擇方法優(yōu)化通信路徑，降低節(jié)點(diǎn)通信能耗，以延長(zhǎng)網(wǎng)絡(luò)生存周期。實(shí)驗(yàn)測(cè)試結(jié)果表明，本文提出的協(xié)議前期的局部搜索明顯擴(kuò)大，后期迭代的收斂速度加快，選舉的簇頭節(jié)點(diǎn)能量高、位置分布較為均衡，轉(zhuǎn)發(fā)節(jié)點(diǎn)的傳輸路徑較短，網(wǎng)絡(luò)的能耗降低并比較均衡，延長(zhǎng)了網(wǎng)絡(luò)生存周期。