WSN中基于改進粒子群優化算法的分簇路由協議

武小年，張楚蕓，張潤蓮,2，孫亞平

（1.桂林電子科技大學廣西密碼學與信息安全重點實驗室，廣西 桂林 541004；2.桂林電子科技大學廣西高校云計算與復雜系統重點實驗室，廣西 桂林 541004）

1 引言

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

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

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

綜上所述，現有簇頭節點選取方法主要根據剩余能量篩選，部分方法考慮了簇頭節點與基站的距離，但未考慮簇頭節點位置的均衡性，而位置分布均衡的簇頭節點，能夠有效縮短通信的總距離，降低網絡通信開銷；其次，現有分簇路由協議大多選取的轉發節點太少，加大了轉發節點的能耗，而部分增加了轉發節點的協議，主要采用隨機方式進行選取，其有可能與簇頭節點重復，且未考慮被選取節點的剩余能量及位置是否均衡；第三，現有協議中轉發節點采用單跳與多跳相結合的方式發送數據，靠近基站的轉發節點采取單跳方式，采用多跳方式時主要考慮相鄰轉發節點的距離，缺乏考慮節點能量及面向基站的方向性，導致能量受限和路徑不合理增加開銷。基于粒子群算法的協議未能充分利用粒子群算法的優勢，并對算法存在的不足進行優化，如粒子初始化的隨機性容易導致節點分布不均衡并陷入局部最優；在速度更新計算中，固定的學習因子和慣性權重無法平衡局部搜索和全局搜索的能力，使算法的收斂速度緩慢，較難獲得高質量的簇頭節點集等。

針對上述問題，本文提出一種基于改進粒子群算法的分簇路由協議（CRIPSO,clustering routing protocol based on improved PSO algorithm in WSN），基于節點的能量和位置評估來篩選候選簇頭節點；通過優化粒子群算法的慣性系數和學習因子，平衡算法的全局搜索與局部探索能力，選舉出能量和位置合理的簇頭節點，構建最優分簇；建立基于最小生成樹的轉發節點多跳數據傳輸路徑，縮短通信距離。

2 系統模型

2.1 網絡模型

首先對網絡模型做如下約定。

1)WSN的實驗區域形狀為平面規則圖形，傳感器節點在監測區域中隨機不均勻分布且固定不動，每個節點由一個全局唯一的ID標識。

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

3)節點無線發射功率可以自我調控，可自主選擇發射功率。

2.2 能耗模型

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

3 基于改進粒子群算法的分簇路由算法

合理的分簇劃分及轉發節點選取，將有利于縮短通信距離，降低并均衡節點通信開銷，延長網絡生存周期。本文改進粒子群算法選舉能量與位置最優的簇頭節點和轉發節點，以降低和均衡網絡通信開銷。

3.1 簇頭選舉

3.1.1 簇頭初始化

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

粒子群算法采用隨機方式選取粒子，傳統的分簇路由協議也大多采用隨機方式選取簇頭，這容易陷入局部最優，導致簇內節點分布不均衡；且若被選取的節點能量過低，其難以承擔簇頭節點的繁重任務。針對該問題，對參與簇頭節點選舉的節點能量進行限制。

假設WSN中有N個存活節點，節點i的能量為E(i)，基站計算WSN中所有節點的平均剩余能量為

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

采用隨機方式在EA中繼續選擇K個節點，一共進行M次篩選，最終生成M組初始簇頭節點集，即M個粒子，并形成M組的分簇。

3.1.2 適應度函數

因簇頭節點能耗大，以節點剩余能量作為一個評價指標有利于選出更高能量的簇頭節點；簇頭所在位置在網絡中分布越均衡，簇頭與非簇頭節點、基站的距離越小，通信開銷將越小。為從M組初始簇頭節點集中選舉出最優的候選簇頭節點集作為簇頭節點集，以節點的剩余能量和位置作為評價指標，構建適應度函數對各個候選簇頭節點集進行評估。

適應度函數要對初始簇頭節點集中的所有候選簇頭節點進行綜合評估，這需要考慮所有候選簇頭節點的平均能量與均衡位置。適應度函數值越大，表明選出的簇頭節點集越優。

1)能量因子

能量因子是候選簇頭節點集中所有候選簇頭節點的平均剩余能量與所有非簇頭節點的平均剩余能量的比值。候選簇頭節點集的平均剩余能量越大，能量因子的值越大。以N表示WSN中的存活節點數量，一個候選簇頭節點集中有K個候選簇頭節點，則非簇頭節點為N-K個；以表示第r輪中候選簇頭節點CHi的剩余能量，表示第r輪中非簇頭節點NCHj的剩余能量，則能量因子f1的計算式為

2)位置均衡因子

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

其中，非簇頭節點NCHi位于簇頭節點CHj所在的分簇內。候選簇頭節點集距離基站越近，各分簇內非簇頭節點到簇頭節點的距離越小，則網絡通信距離越短，候選簇頭節點集的位置在WSN中分布越均衡，f2的值越大。

基于能量因子和位置均衡因子，對候選簇頭節點集采用加權方式計算適應度，適應度值函數F1計算方法為

其中，a∈(0,1]是權重系數，根據WSN對剩余能量和位置均衡的需求不同，可以調整權值。在適應度函數中，候選簇頭節點集的剩余能量越大，位置分布越均衡，則適應度值越大，選出的候選簇頭節點集越優。

針對M組初始簇頭節點集，完成對其中各組候選簇頭節點集的適應度函數計算后，記錄每個候選簇頭節點集本身適應度最大的位置作為每一組候選簇頭節點集的局部最優位置（初始時為每個候選簇頭節點集自身的位置），初始M組簇頭節點集中最大適應度函數值的候選簇頭節點集所在的位置為全局最優位置。

3.1.3 速度與位置的更新方法

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

其中，w是慣性權值，表示候選簇頭節點集前一輪t–1迭代的速度對本輪t迭代的候選簇頭節點集的速度的影響程度；c1是認知學習因子，c2是社會學習因子，分別表示候選簇頭節點集靠近局部最優位置和全局最優位置的加速權值；r1,r2∈(0,1)為隨機數，借鑒仿生學中的變異性，使簇頭節點集具有變異特性。

基于2個速度分量，候選簇頭節點在x和y方向上的位置分量xxid和xyid的計算方法為

3.1.4 具有自適應的學習因子和慣性權重

在上述速度更新計算中，傳統基于粒子群算法的路由協議中的學習因子和慣性權重通常設置為固定值，無法平衡局部搜索能力和全局搜索能力，算法的收斂速度比較緩慢，較難獲得高質量的簇頭節點集。

在最優簇頭節點集的選取過程中，前期的迭代側重局部最優搜索，后期的迭代側重全局最優搜索。局部最優搜索若搜索范圍小，算法將容易陷入局部最優解，因此需要盡可能地擴大尋找最優候選簇頭節點集的局部搜索范圍，以增強群體的多樣性；全局搜索則需要加快算法收斂，保持收斂速度和搜索效果的均衡。為達到該目標，設置認知學習因子c1和社會學習因子c2動態變化，在逐步迭代過程中，使c1從大到小變化，c2從小到大變化。

為滿足2個學習因子的上述變化規律，結合傳統學習因子的固定值設置情況，構造動態變化的學習因子，計算方法為其中，t為本輪迭代次數，tmax為最大迭代次數。隨著迭代次數的變化，c1和c2動態變化，滿足其變化規律，使算法能夠自適應地在迭代前期擴大局部搜索范圍，在迭代后期加快全局收斂速度。

在迭代過程中，慣性權值可以根據上一輪的速度影響本輪的搜索范圍。在每一輪迭代結束都要對選取的候選簇頭節點集進行適應度函數計算，以適應度值的結果動態調整慣性權值，使本輪迭代中選取的簇頭節點集具有更均衡的位置。在此，采用非線性自適應慣性權重策略[16]計算慣性權值，方法為

其中，wmax和wmin分別為設置的最大和最小慣性權重，fi為候選簇頭節點CHi的適應度值，fmin、fmax和favg分別表示本輪候選簇頭節點集的最小、最大和平均適應度值。當fi＞favg時，本次候選簇頭節點的速度主要參考上一輪的速度，增加候選簇頭節點集的活躍度；反之，本次候選簇頭節點的速度主要參考局部最優位置和全局最優位置，加速候選簇頭節點集向優勢空間靠近。

3.1.5 位置映射策略

在每一輪迭代后，候選簇頭節點集的位置都將被更新，可能會出現更新后的節點位置在WSN中找不到匹配的存活節點。此時，需要進行位置映射處理[11]，基本思路是采取就近原則，將更新后的位置映射到距離該位置最近的存活節點所在的位置。以Xxid、Xyid為更新后的節點坐標，CMnx、CMny為網絡中存活節點CMn的坐標，位置映射處理過程為

位置映射策略解決了網絡節點分布離散所帶來的更新后的位置與實際存活節點位置不匹配的情況。當出現多個節點更新后的位置坐標一樣時，需要在更新節點的同時設置一個標志位，其他節點更新并進行位置映射時先檢查標志位是否已經被標識為簇頭節點，若是則依次選擇距離次近的節點位置進行映射。

完成位置映射后，將位置更新后的各候選簇頭節點集作為優化結果，計算各候選簇頭節點集的適應度值。根據計算結果，更新每一組候選簇頭節點集的局部最優位置以及本輪M組簇頭節點集的全局最優位置。若迭代未結束，則繼續進行候選簇頭節點的位置更新與映射；否則，最后計算出的全局最優位置的候選簇頭節點集作為最優簇頭節點集，簇頭選舉完成。

基站在完成簇頭選舉后，進一步計算非簇頭節點到各個簇頭節點的距離，將非簇頭節點加入距離最近的簇頭節點，完成分簇。此時，傳感器節點分為簇頭節點和普通節點。普通節點僅進行數據發送，將自身監測的數據融合后單跳發送給簇頭節點；簇頭節點接收來自普通節點的數據后進行數據融合，再發送給相應的轉發節點。轉發節點需要進一步從普通節點中選取，其接收來自簇頭的數據，并選擇到基站的最優路徑，將數據發送給基站。

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

3.2 轉發節點的選舉與多跳傳輸

3.2.1 選舉轉發節點

在完成簇頭節點選舉后，將為簇頭節點選擇對應的轉發節點。若網絡中的轉發節點過少，多個簇頭節點通過少量轉發節點向基站發送數據，將加大轉發節點的能耗。針對該問題，現有的WSN路由協議采取一個簇頭節點對應一個轉發節點的方式[11]，增加轉發節點的數量，但其采用隨機方式在所有節點中選取，未考慮被選取節點的剩余能量及位置是否均衡。

本文在轉發節點選舉時，采用上述簇頭節點選舉的改進粒子群算法，為每個簇頭節點在其分簇內的普通節點中選舉一個轉發節點，使被選舉出的轉發節點具有最優的能量和位置關系，并避免WSN中轉發節點過少而加快其能量消耗。

在對轉發節點計算和評估中，由于轉發節點只能在一個分簇內選舉，能量因子和位置均衡因子的計算方法與簇頭節點選舉的計算方法有所區別。

同樣以N表示WSN中的存活節點數量，在選舉出K個簇頭節點后，WSN被分為K個分簇，初始化時根據簇頭節點篩選的方法，在各個分簇內篩選出較高剩余能量的候選轉發節點，組成候選轉發節點集，每個候選集中包含K個節點。

在初始化后，普通節點數量為N–2K，以表示第r輪中候選轉發節點RNi的剩余能量，表示第r輪中普通節點CNj的剩余能量，能量因子fit1的計算式為

以d(CNk,CHj)表示普通節點CNk到對應的簇頭節點CHj之間距離，d(RNi,BS)表示轉發節點RNi到基站BS的距離，d(RNi,CHj)表示轉發節點RNi到對應的簇頭節點CHj的距離，d(RNi,RNm)表示轉發節點RNi和RNm之間的距離，轉發節點位置均衡因子fit2計算方法為

其中，普通節點CNk位于簇頭節點CHj所在的分簇內；候選轉發節點RNi對應于簇頭節點CHj。候選轉發節點集距離基站越近，各分簇內簇頭節點與轉發節點的距離越小，候選轉發節點集中各轉發節點之間的距離越小，候選轉發節點集的位置分布越均衡，fit2值越大。

基于候選轉發節點選舉的能力因子和位置均衡因子，采用加權方法構建的對候選轉發節點集評價的適應度函數F2為

其中，b∈(0,1]為權值。候選轉發節點集剩余能量越高，位置越均衡，則候選轉發節點集的適應度值將越大，表明候選轉發節點集越優。

在候選轉發節點集的多次迭代選舉過程中，采用與簇頭節點選舉類似的速度更新及位置映射方法，選出最優的轉發節點集。

3.2.2 轉發節點的多跳傳輸

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

本文在選舉出最優的轉發節點集后，將根據轉發節點與基站的距離d確定轉發節點采用單跳還是多跳方式向基站傳輸數據，若d＞d0，則該轉發節點采用多跳方式傳輸；否則該轉發節點采用單跳方式傳輸。

在轉發節點多跳路徑選擇中，本文利用構造最小生成樹的方法搜索轉發節點多跳傳輸的最短路徑，同時兼顧節點剩余能量，以在降低網絡能耗時，維持轉發節點消耗的均衡性。

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

假設以轉發節點RNi為起點，要搜索到基站所途經的下一跳節點；若轉發節點RNj為RNi的鄰居轉發節點，則需要評估節點RNj能否作為下一跳節點，在此，以這2個節點的邊的權值來衡量，權值由2個節點的距離與剩余能量確定，并以wi,j表示。若節點RNj到基站的距離大于或等于節點RNi到基站的距離，則節點RNj不能作為下一跳節點，設置wi,j為∞；否則以2個節點的距離與剩余能量計算wi,j，計算方法為

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

在每輪轉發節點選舉結束后，將采用上述最小生成樹方式建立轉發節點到基站的多跳路徑。基于最小生成樹的多跳路徑建立方法具體過程如下所示。在上述構造的帶權連通圖G=(V,E)中，將基站v0作為樹的根節點加入V中，以U記錄最小生成樹的節點集合，W記錄待選擇的轉發節點與其鄰居節點所構成邊的權值集合，T記錄最小生成樹中邊的權值集合。

步驟1初始將根節點v0加入集合U中，T和W為空。

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

步驟3根據式(13)計算vi到其他所有轉發節點的邊的權值，并將其加入W中。

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

步驟5若U=V，結束搜索，轉至步驟6；否則，轉至步驟2。

步驟6對于T中權值為0且后一個節點為v0的權值，將該權值對應邊的前一個節點作為單跳節點輸出；否則，將權值對應邊的前一個節點作為起點，后一個節點作為下一跳節點，繼續查找下一跳節點，直到下一跳節點為v0，形成多跳路徑輸出。

4 仿真實驗及結果分析

在Matlab中模擬生成WSN，基站位于網絡之外。在此環境下實現基于改進粒子群算法的路由協議并進行測試。測試計算機配置為2.3 GHz Intel Core i5，8 GB內存，64位Windows10。WSN初始化、簇頭節點與轉發節點選舉、數據處理的相關實驗環境及參數設置如表1所示。

表1 實驗參數設置

考慮到WSN一般相對穩定，數據采集與數據處理的頻率不高，在此主要根據WSN的數據處理頻率來開啟新一輪的分簇選舉，即當簇頭節點完成對簇內節點數據的融合并發送給基站，基站收到數據后，將開始新一輪的分簇選舉。對于數據處理頻率較快的WSN情況，本文暫未考慮，但可以采用事件觸發發送，通過判斷簇頭節點的剩余能量來確定是否開啟新一輪的分簇選舉。

基于上述實驗環境，測試適應度函數不同權值對網絡的影響及本文協議CRIPSO下的節點能耗及網絡生存周期變化情況，并與LEACH[1]、IPSOCH[12]和NAPSO[13]進行對比測試。

4.1 適應度函數權值的選取實驗

在式(4)和式(12)中，權值a與b體現能量因子與位置均衡因子對適應度的影響程度。為設置合理的權值，根據節點剩余能量均方差評判協議采用不同權值進行迭代計算和網絡運行中節點能耗的均衡程度。均方差越小，不同節點的剩余能量差別較小，均衡性較好。基于上述仿真環境，測試了本文協議在不同權值下運行的節點剩余能量均方差，結果如圖1所示。

圖1 適應度函數不同權值下的節點剩余能量均方差

圖1表明，能量因子和位置均衡因子在不同權值下，對網絡中節點的剩余能量與網絡生存周期的影響不同。當能量因子與位置均衡因子對適應度函數的影響不平衡時，即能量因子影響較大位置均衡因子影響較小，或者反過來，所測得的均方差都較大，表明網絡中節點的剩余能量差異較大，節點死亡較快，最終導致網絡生存周期下降。當能量因子與位置權衡因子對適應度函數的影響均衡，特別是當a=b=0.5時，所測得的均方差最小，網絡迭代執行的過程最長，網絡生存周期最長。在后續的實驗中，令a=b=0.5。

4.2 協議性能對比實驗與結果分析

實驗1協議運行能耗與生存周期

本文協議通過改進粒子群算法及設計的轉發節點多跳傳輸路徑選擇方法，力圖構建最優分簇和最短多跳傳輸路徑。在上述實驗環境下，對比測試了本文協議CRIPSO與LEACH、IPSOCH和NAPSO在2 500輪迭代中的節點存活數量及網絡生存周期的變化情況，實驗結果如圖2所示。

圖2 不同算法的網絡生存周期對比測試結果

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

LEACH協議中簇頭選舉采用基于閾值的方法且簇頭節點采用單跳傳輸，節點的能耗較大，在較短的時間內，死亡的節點較多，WSN生存周期最短。IPSOCH協議利用改進粒子群算法，通過節點的剩余能量信息和位置信息選擇簇頭和轉發節點，優化了分簇，降低了節點能耗，相對LEACH協議節點死亡減緩，WSN生存周期延長。但IPSOCH協議在計算位置時僅考慮節點與基站的距離，其選舉出來的簇頭節點集難以達到全局最優。NAPSO協議增加了對慣性權重的改進，相比于IPSOCH協議進一步優化了分簇，降低了節點能耗，其WSN生存周期較IPSOCH協議有所延長。

本文協議CRIPSO基于能量因子與位置均衡因子評估候選簇頭節點集，并通過自適應學習因子與慣性權重，選舉出最優簇頭節點集和轉發節點集，并通過設計的最小生成樹多跳傳輸路徑選擇方法建立路由，并采用捎帶技術減少信息交互的開銷，相對于對比協議，降低了轉發節點的通信距離，降低并均衡了節點能耗，大大延長了WSN生存周期。

實驗2簇頭節點的位置均衡測試

位置均衡因子體現了簇頭節點集與轉發節點集在WSN中的分布均衡情況，節點分布的越均衡，則WSN通信中總的通信距離越小，節點能耗越低。基于上述實驗環境，分別測試了本文協議CRIPSO與LEACH、IPSOCH和NAPSO協議在多次迭代中所有普通節點到簇頭距離的總和、所有簇頭節點到基站距離的總和，實驗結果分別如圖3和圖4所示。

圖3 不同協議中普通節點到簇頭距離的總和

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

由圖3與圖4可知，隨著迭代次數的增加，4種協議中所有普通節點到簇頭的總距離、所有簇頭到基站的總距離都越來越小。

LEACH協議在簇頭選舉中未考慮節點的能量和位置，初始時圖3和圖4的2個距離都最大，但在987輪后2個距離迅速下降，這是因為其通信距離大，能耗大且不均衡，節點死亡較快，隨著存活節點大量減少，其通信距離減小，WSN生存周期大大縮短。IPSOCH協議考慮了位置信息，初始時其2個距離相對縮小，能耗有所降低，WSN生存周期延長。NAPSO協議在慣性權重中的優化，使選舉的簇頭節點向全局最優靠攏，初始時測得的2個距離低于IPSOCH協議，節點能耗降低，WSN生存周期較IPSOCH有所延長。IPSOCH和NAPSO協議同樣在迭代后期因死亡節點激增，存活節點較少，測得的2個距離都小于本文協議，但生存周期都更小。

本文協議CRIPSO在位置均衡因子中考慮了簇頭節點與基站的距離、每個簇頭節點與該分簇內非簇頭節點的距離，以及所有非簇頭節點與基站的距離，且設計了優化轉發節點通信路徑的多跳傳輸路徑選擇方法，使篩選的簇頭節點和轉發節點在WSN中位置均衡，初始時2個距離都最小，有效降低并均衡了節點能耗，死亡的節點數量呈線性緩慢下降，變化較為穩定，延長了WSN生存周期。

實驗3自適應學習因子的影響

在最優簇頭節點集的選取過程中，前期的迭代側重局部最優搜索，后期的迭代側重全局最優搜索。在速度更新中，2個學習因子分別控制候選簇頭節點集靠近局部最優位置和全局最優位置的加速度。固定學習因子無法滿足迭代過程中的局部和全局最優搜索變化需求，自適應學習因子則給出了有效的解決方法。基于上述實驗環境，分別對比測試了本文協議在固定學習因子和自適應學習因子下的網絡生存周期變化情況。其中，固定學習因子時2個學習因子都設置為當前常用的固定值，令c1=2，c2=2。實驗結果如圖5所示。

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

圖5 不同的學習因子值對網絡的影響

實驗4轉發節點傳輸路徑對比

轉發節點承擔了將WSN中的數據傳輸到基站的任務，數據量大且通信距離較長。根據LEACH能耗模型，若轉發節點與基站的距離d大于門限距離d0，則發送能耗激增。縮短轉發節點集與基站的通信距離，將可以大大降低網絡能耗，延長WSN生存周期。基于上述同樣的實驗環境，對比測試了本文協議CRIPSO與IPSOCH、NAPSO的轉發節點通信距離與網絡生存周期情況，實驗結果如圖6所示。

圖6 不同協議下的轉發節點到基站的總距離

圖6表明，隨著迭代次數的增加，3種協議中轉發節點到基站的總距離減少。IPSOCH協議和NAPSO協議在1 113輪后轉發節點到基站的總距離快速下降，低于本文協議CRIPSO，這是因為2種協議中轉發節點與基站均采用單跳方式進行數據傳輸，遠離基站的轉發節點在數據傳輸過程中采用多路衰減模型，節點能量衰減較快，轉發節點死亡較快，網絡中存活節點數量下降迅速，因此在開始時2種協議的總距離大于本文協議，在后期低于本文協議。

本文協議CRIPSO通過轉發節點的優化選舉，及基于最小生成樹構建轉發節點多跳傳輸路徑，大大縮短了轉發節點的通信距離，降低了網絡能耗，節點死亡速度較慢，故在0～1 002輪期間本文協議的總距離最小；后期因存活節點遠多于2個對比協議，其通信距離高于2個對比協議，WSN生存周期更長。

5 結束語

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