基于粒子群進化的輸電網絡WSN節點定位算法*

任鵬飛， 谷靈康

(1. 河南工程學院 電氣信息工程學院， 鄭州 451191； 2. 安徽工程大學 計算機與信息學院， 安徽 蕪湖 241000)

當前，電力資源在人類能源使用中所占據的比例日益突出，電力網絡肩負著電力傳輸和能源供給的重任.以特高壓線路為代表的電力網絡已經開始全面鋪設，網絡覆蓋面積廣袤，且大部分暴露在野外，布設環境較為復雜，需要通過無線傳感器網絡(wireless sensor networks，WSN)來監測輸電網絡的實時狀態.無線傳感器網絡具有成本低廉、易于布設、自組織等多重優點，目前在電力傳輸網絡系統監測方面已有廣泛應用[1-2].在電力網絡的實際監測中，首先需要考慮網絡中各個位置的電力傳輸情況.由于服務于輸電網絡的無線傳感器網絡需要能夠實時傳遞系統監測信息，包括電力故障、電網運行狀態等，這些信息與傳感器節點的位置息息相關，對實時了解和掌握輸電網絡的運行情況具有重要的意義，因此，無線傳感器節點的位置信息對于電力網絡系統監測和性能分析極為重要.節點定位算法能夠直接給出無線傳感器所在的位置，并避免繁瑣的實地測量，可有效地提升電力網絡監測和信息傳輸的效率和性能[3-4].

基于無線傳感器網絡的節點定位在輸電網絡中具有諸多應用，是實現輸電網絡系統監測的基礎，也是輸電網絡應用無線傳感器網絡亟需解決的關鍵問題之一[5-7].文獻[8]將粒子群算法(particle swarm optimization，PSO)進行改進，并應用于WSN網絡節點定位，具有計算復雜度低的優點，但該算法只是簡單沿用了粒子群算法完成優化定位，性能提升并不明顯；文獻[9]將節點定位分為兩個階段，首先采用DV-distance算法對節點位置進行粗略估計，然后使用粒子群算法精確定位；文獻[10]則將粒子群算法與DV-Hop算法相融合，利用粒子群算法進一步優化定位結果，但該算法計算復雜度較高，定位精度也受限；文獻[11]使用邊界盒方法預估計節點的所在區域，并通過WSN網絡中的數據交換獲取其他鄰居節點的估計信息，以進一步縮小估計區域，優化定位精度，但該方法在兩次估計間等待時間較長，使得定位過程耗時較長，定位精度提高有限.

針對上述問題，本文提出一種粒子群進化算法，以應用于輸電網絡的WSN節點定位.該算法通過區域估計，縮小并限制傳感器節點的預估計區域空間，以簡化計算復雜度，并應用粒子群算法快速尋找節點定位的最優解.通過引入粒子群競爭和權重自適應的機制，以加快節點定位的搜索速度，并提升算法的搜索能力.通過仿真和分析發現，相比同類的WSN節點定位算法，該算法在錨節點密度、通信距離、測距誤差等方面都具有一定的性能優勢，能夠顯著提升節點的定位精度，降低計算復雜度，為輸電網絡的無線傳感器網絡提供更高效準確的定位服務.

1 粒子群算法原理

粒子群算法是一種基于種群的啟發式智能算法，其搜索策略受鳥群集體活動啟發，并引入了群體的智能策略.相比同類啟發式算法(如退火算法、蟻群算法等)，粒子群算法需要設定的參數少、收斂迅速快且計算復雜度低.

定義1粒子.在粒子群算法中，種群中的單個個體稱為粒子.在進化迭代過程中，每個粒子的速度、位置、局部最優解(pbesti)和全局最優解(gbesti)都需要記錄.

定義2粒子適應度函數.粒子適應度函數是用于比較所有粒子候選解的適應度.通過舒服粒子在當前迭代的位置，計算粒子的適應值，以此衡量粒子候選解的優劣.

假設D表示解空間維度，P表示粒子種群規模，Vi=[vi，1，vi，2，…，vi，D]為粒子i速度，Xi=[xi，1，xi，2，…，xi，D]為粒子i位置，則粒子群算法可進一步表示為

(1)

式中：ω為慣性權重；k為進化代數；c1、c2為進化系數；r1和r2為(0，1)之間的隨機數；i=1，2，…，P，d=1，2，…，D.在粒子群迭代過程中，粒子通過搜索個體最優解pbesti與全局最優解gbesti不斷調整自身的位置和速度，逐步達到全局最優解.

2 輸電網絡WSN節點定位算法

基于WSN網絡中節點定位的模式和特點，本文采用了區域估計方法限制了傳感器節點的預估計區域空間，以簡化計算復雜度.引入了粒子群競爭和權重自適應策略，粒子群在每次迭代演化中搜索局部最優解(pbesti)和全局最優解(gbesti)，同步調整粒子群的位置、速度，以優化未知節點的精確定位.采取上述改進策略在粒子群算法的復雜度和定位性能間獲得最優平衡.

2.1 問題描述

假設WSN網絡依托輸電網絡進行布設，并為其提供定位服務.無線傳感器網絡包含M個錨節點和N個普通節點，其中任意錨節點的坐標可表示為mi(xi，yi)，而普通節點的位置坐標未知.無線傳感器網絡的節點定位就是基于網絡中位置已知的M個錨節點，計算并確定其余N個普通節點的位置，這里稱需要定位的普通節點為目標節點.尋找N個目標節點的位置過程即為粒子群算法的迭代過程，通過獲取最小的粒子適應度函數估計得到未知節點的精確位置.適應度函數可表示為

(2)

2.2 區域估計

區域估計是指粒子群在執行搜索之前，對未知節點所在區域進行合理估計，限制節點位置可行解空間，減少粒子群算法的復雜度和計算量，提升未知節點的定位精度.

在文獻[11]的基礎上，本文提出了未知節點的區域估計方法.對于未知節點i，首先獲取其所有的鄰居錨節點，計算所有鄰居錨節點的正方形覆蓋區域的交集幾何中心，作為傳感器節點i的位置估計.需要指出的是，錨節點的正方形覆蓋區域以該錨節點為中心，邊長是傳感器節點通信距離的2倍.由于計算矩形交集比計算圓形交集更加簡單易實現，這使得后續的粒子群算法得到了簡化，降低了計算量，并有效提升了區域估計的精度.區域估計的具體流程如圖1所示.

圖1 區域估計流程圖Fig.1 Flow chart of regional estimation

在未知節點的區域估計過程中，未知節點首先需要收集鄰居錨節點的位置信息，然后將節點ID和存儲的鄰居錨節點信息向鄰居節點廣播，同時接收其他目標節點的廣播消息，最后綜合所有鄰居錨節點的位置信息完成自身的區域估計.未知節點i的估計區域表示為

(3)

(4)

(5)

(6)

式中：r為輸電網絡中傳感器節點的最大通信距離；Lright，i，Lleft，i，Lup，i，Ldown，i分別為未知節點在4個方位上的節點位置，這4項參數共同確定了節點i的估計位置.

在分析區域估計的過程中發現，改進后的區域估計只需要完成加減運算或min(max)運算即可完成未知節點的位置估計，這就為后續粒子群迭代有效地縮小了可行解空間，大大減少了計算量，節約了WSN網絡的節點能耗，從而促進了輸電網絡的節點定位服務.

2.3 基于粒子群進化的WSN節點定位算法

為進一步加快算法的搜索速度，增強算法的實用性，基于粒子群進化的WSN節點定位算法還引入了權重自適應的策略，以加快算法的收斂速度.

在粒子群算法中，權值w對節點適應度函數的影響較大.如果w取值過大，則粒子速度變化較快，使得粒子容易跳出局部極小點，具有較強的全局搜索能力，但也會降低粒子群的局部搜索能力；反之，如果w取值過小，則粒子群的局部搜索能力增強，便于算法收斂，卻會降低粒子群的全局搜索能力.因此，有必要采用自適應的權重w，在實現算法快速收斂的同時，保證粒子群進化在全局和局部范圍內達到有效的平衡.自適應權重w表示為

(7)

式中，fa為未知節點的節點適應度滿足要求的門限閾值.當節點適應度劇增時，自適應降低w的權值；當節點適應度劇降時，自適應增加w的權值.自適應地調整權重w，使其停留在(wmin，wmax)范圍內，能夠保持局部搜索與全局搜索能力的平衡，使得粒子群收斂的速度最快.

基于粒子群進化的WSN節點定位算法具體步驟如下：

1) 對目標節點進行區域估計，縮小并確定可搜索的空間S.

2) 初始化迭代次數iter=0，粒子群規模為e.

3) 若滿足e

4) 淘汰50%適應度較低的粒子，保留50%適應度較高的優選粒子.

5) 圍繞每個優選粒子的位置設定一個局部的搜索范圍，并進行局部搜索.

6) 獲取每個優先粒子的局部最優解(pbesti)，并將該粒子更新為局部最優解對應的位置，比較所有的局部最優解，獲取并記錄全局最優解(gbesti).

7) 判斷迭代終止條件是否滿足，若滿足，則粒子群迭代結束，以全局最優解(gbesti)作為未知節點的位置估計；若不滿足，補充(E-e)/2個隨機粒子，并跳轉至步驟3).

為便于輸電網絡中實現WSN網絡測距，本文采用RSSI技術實現相鄰節點間的測距.由于實際網絡中節點布設、地形起伏等因素的影響，無線傳感器節點的通信覆蓋范圍不一定是圓形，往往導致測距誤差，因此，在仿真過程中需要考慮環境等因素引起的測距誤差并加以修正.

3 仿真結果與分析

3.1 仿真環境說明

為驗證節點定位算法的有效性，本文采用MATLAB 2010的平臺進行仿真.在WSN網絡的覆蓋范圍內(100 m×100 m)，隨機生成100個無線傳感器節點.其中，錨節點個數20～50，位置已知，其余個節點位置未知.輸電網絡中無線傳感器節點定位的評價指標為：對未知節點重復10次節點定位，計算平均定位誤差，即定位位置與實際位置的距離與節點通信半徑之比.同類算法中，選取了經典的DPSO算法[12]、Standard PSO算法[13]進行對比；不同類算法中，選取了經典的測距定位算法Improved DV[14]來比較.測距定位算法Improved DV不需要設置粒子群參數，其余3種算法的參數設置如表1所示.

3.2 錨節點密度對定位性能的影響

圖2為在不同錨節點密度下4種算法的定位誤差.隨著錨節點密度的逐步增加，所有算法的定位誤差都呈不斷縮小的趨勢，其中，Improved DV算法的定位誤差下降幅度最大.因為隨著錨節點的增多，輸電網絡中未知節點有了更多的位置參考，在節點定位過程中能夠獲取更多的鄰居節點位置信息，從而有效地降低定位誤差.綜合比較4種定位算法，本文算法的定位性能最優.當錨節點密度為10%時，其定位誤差為33.5%；而當錨節點密度為40%時，其定位誤差約為8.1%，一直處于所有算法中的誤差最低水平.在同等錨節點密度下，本文的定位算法具有最優的定位精度，從而需要最少的錨節點，有效降低了輸電網絡的部署成本.

表1 WSN節點定位的參數設置Tab.1 Parameter setting of WSN node localization

圖2 不同錨節點密度下4種算法的定位誤差Fig.2 Localization error of 4 algorithms under different anchor node density

3.3 通信距離對定位性能的影響

圖3為4種算法在不同通信距離下的定位誤差，其中節點通信距離限定在20～50 m.如圖3所示，隨著節點通信距離的不斷擴大，定位誤差都呈現出逐步縮小的趨勢.綜合比較4種定位算法，在同等通信距離的條件下，本文算法的節點定位誤差最小.當節點通信距離為25 m時，其定位誤差為12.4%；而當節點通信距離為50 m時，其定位誤差約為9.3%，一直處于所有算法中的誤差最低水平.在相同的定位誤差要求下，本文算法所需節點通信距離最小，即要求無線傳感器節點的通信半徑最小，需要消耗的信號功率最低，有效降低網絡的通信能耗，提升網絡的工作壽命，提升無線傳感器網絡的穩定性和有效性.

圖3 不同通信距離下4種算法的定位誤差Fig.3 Localization error of 4 algorithms under different communication distances

3.4 測距誤差對定位性能的影響

節點定位會受部署環境的影響，比如信號衰減、通信范圍受限等.其中，測距誤差對節點定位影響尤為重要，這里通過實驗進一步進行對比和分析.

圖4為4種算法在不同測距誤差下的定位誤差.當測距誤差逐步增大，4種算法的定位誤差也呈現不斷增加的趨勢.由于Improved DV算法是測距定位算法，測距過程中需要累加基于接收信號強度(RSSI)的測試距離，測距誤差對定位誤差的影響尤為明顯.當RSSI測距誤差較小時，Improved DV算法性能與DPSO算法接近；當RSSI測距誤差較大時，Improved DV算法性能急劇下降，定位誤差最大.綜合比較4種定位算法，在同等測距誤差的條件下，本文算法的節點定位誤差雖然也在逐步增加，但表現較為穩定，且在4種算法中定位誤差最小，一直處于所有算法中誤差最低水平.這說明本文算法抗測距誤差性能最佳，穩定性最好，能夠適用于多種復雜惡劣的輸電網絡環境.

圖4 不同測距誤差下4種算法的定位誤差Fig.4 Localization error of 4 algorithms under different ranging errors

4 結 論

基于無線傳感器網絡的節點定位對于輸電網絡的信息傳輸和故障判定具有重要意義，為改善輸電網絡中的節點定位精度，本文提出一種基于粒子群進化的節點定位算法.該算法通過區域估計，縮小并限制傳感器節點的預估計區域空間，以簡化計算復雜度，并通過引入粒子群競爭和權重自適應的機制，改善了無線傳感器節點的定位精確.通過仿真和分析發現，相比同類的WSN節點定位算法，該算法在錨節點密度、通信距離、測距誤差等方面都具有性能優勢，能夠顯著提升節點的定位精度，降低計算復雜度.該算法非常適用于現有的輸電網絡，利用輸電網絡搭載的無線傳感器網絡，為輸電網絡監測提供更高效、更準確的定位服務.