基于粒子群進(jìn)化的輸電網(wǎng)絡(luò)WSN節(jié)點(diǎn)定位算法*

任鵬飛， 谷靈康

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

當(dāng)前，電力資源在人類(lèi)能源使用中所占據(jù)的比例日益突出，電力網(wǎng)絡(luò)肩負(fù)著電力傳輸和能源供給的重任.以特高壓線(xiàn)路為代表的電力網(wǎng)絡(luò)已經(jīng)開(kāi)始全面鋪設(shè)，網(wǎng)絡(luò)覆蓋面積廣袤，且大部分暴露在野外，布設(shè)環(huán)境較為復(fù)雜，需要通過(guò)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(wireless sensor networks，WSN)來(lái)監(jiān)測(cè)輸電網(wǎng)絡(luò)的實(shí)時(shí)狀態(tài).無(wú)線(xiàn)傳感器網(wǎng)絡(luò)具有成本低廉、易于布設(shè)、自組織等多重優(yōu)點(diǎn)，目前在電力傳輸網(wǎng)絡(luò)系統(tǒng)監(jiān)測(cè)方面已有廣泛應(yīng)用[1-2].在電力網(wǎng)絡(luò)的實(shí)際監(jiān)測(cè)中，首先需要考慮網(wǎng)絡(luò)中各個(gè)位置的電力傳輸情況.由于服務(wù)于輸電網(wǎng)絡(luò)的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)需要能夠?qū)崟r(shí)傳遞系統(tǒng)監(jiān)測(cè)信息，包括電力故障、電網(wǎng)運(yùn)行狀態(tài)等，這些信息與傳感器節(jié)點(diǎn)的位置息息相關(guān)，對(duì)實(shí)時(shí)了解和掌握輸電網(wǎng)絡(luò)的運(yùn)行情況具有重要的意義，因此，無(wú)線(xiàn)傳感器節(jié)點(diǎn)的位置信息對(duì)于電力網(wǎng)絡(luò)系統(tǒng)監(jiān)測(cè)和性能分析極為重要.節(jié)點(diǎn)定位算法能夠直接給出無(wú)線(xiàn)傳感器所在的位置，并避免繁瑣的實(shí)地測(cè)量，可有效地提升電力網(wǎng)絡(luò)監(jiān)測(cè)和信息傳輸?shù)男屎托阅躘3-4].

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

針對(duì)上述問(wèn)題，本文提出一種粒子群進(jìn)化算法，以應(yīng)用于輸電網(wǎng)絡(luò)的WSN節(jié)點(diǎn)定位.該算法通過(guò)區(qū)域估計(jì)，縮小并限制傳感器節(jié)點(diǎn)的預(yù)估計(jì)區(qū)域空間，以簡(jiǎn)化計(jì)算復(fù)雜度，并應(yīng)用粒子群算法快速尋找節(jié)點(diǎn)定位的最優(yōu)解.通過(guò)引入粒子群競(jìng)爭(zhēng)和權(quán)重自適應(yīng)的機(jī)制，以加快節(jié)點(diǎn)定位的搜索速度，并提升算法的搜索能力.通過(guò)仿真和分析發(fā)現(xiàn)，相比同類(lèi)的WSN節(jié)點(diǎn)定位算法，該算法在錨節(jié)點(diǎn)密度、通信距離、測(cè)距誤差等方面都具有一定的性能優(yōu)勢(shì)，能夠顯著提升節(jié)點(diǎn)的定位精度，降低計(jì)算復(fù)雜度，為輸電網(wǎng)絡(luò)的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)提供更高效準(zhǔn)確的定位服務(wù).

1 粒子群算法原理

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

定義1粒子.在粒子群算法中，種群中的單個(gè)個(gè)體稱(chēng)為粒子.在進(jìn)化迭代過(guò)程中，每個(gè)粒子的速度、位置、局部最優(yōu)解(pbesti)和全局最優(yōu)解(gbesti)都需要記錄.

定義2粒子適應(yīng)度函數(shù).粒子適應(yīng)度函數(shù)是用于比較所有粒子候選解的適應(yīng)度.通過(guò)舒服粒子在當(dāng)前迭代的位置，計(jì)算粒子的適應(yīng)值，以此衡量粒子候選解的優(yōu)劣.

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

(1)

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

2 輸電網(wǎng)絡(luò)WSN節(jié)點(diǎn)定位算法

基于WSN網(wǎng)絡(luò)中節(jié)點(diǎn)定位的模式和特點(diǎn)，本文采用了區(qū)域估計(jì)方法限制了傳感器節(jié)點(diǎn)的預(yù)估計(jì)區(qū)域空間，以簡(jiǎn)化計(jì)算復(fù)雜度.引入了粒子群競(jìng)爭(zhēng)和權(quán)重自適應(yīng)策略，粒子群在每次迭代演化中搜索局部最優(yōu)解(pbesti)和全局最優(yōu)解(gbesti)，同步調(diào)整粒子群的位置、速度，以?xún)?yōu)化未知節(jié)點(diǎn)的精確定位.采取上述改進(jìn)策略在粒子群算法的復(fù)雜度和定位性能間獲得最優(yōu)平衡.

2.1 問(wèn)題描述

假設(shè)WSN網(wǎng)絡(luò)依托輸電網(wǎng)絡(luò)進(jìn)行布設(shè)，并為其提供定位服務(wù).無(wú)線(xiàn)傳感器網(wǎng)絡(luò)包含M個(gè)錨節(jié)點(diǎn)和N個(gè)普通節(jié)點(diǎn)，其中任意錨節(jié)點(diǎn)的坐標(biāo)可表示為mi(xi，yi)，而普通節(jié)點(diǎn)的位置坐標(biāo)未知.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位就是基于網(wǎng)絡(luò)中位置已知的M個(gè)錨節(jié)點(diǎn)，計(jì)算并確定其余N個(gè)普通節(jié)點(diǎn)的位置，這里稱(chēng)需要定位的普通節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn).尋找N個(gè)目標(biāo)節(jié)點(diǎn)的位置過(guò)程即為粒子群算法的迭代過(guò)程，通過(guò)獲取最小的粒子適應(yīng)度函數(shù)估計(jì)得到未知節(jié)點(diǎn)的精確位置.適應(yīng)度函數(shù)可表示為

(2)

2.2 區(qū)域估計(jì)

區(qū)域估計(jì)是指粒子群在執(zhí)行搜索之前，對(duì)未知節(jié)點(diǎn)所在區(qū)域進(jìn)行合理估計(jì)，限制節(jié)點(diǎn)位置可行解空間，減少粒子群算法的復(fù)雜度和計(jì)算量，提升未知節(jié)點(diǎn)的定位精度.

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

圖1 區(qū)域估計(jì)流程圖Fig.1 Flow chart of regional estimation

在未知節(jié)點(diǎn)的區(qū)域估計(jì)過(guò)程中，未知節(jié)點(diǎn)首先需要收集鄰居錨節(jié)點(diǎn)的位置信息，然后將節(jié)點(diǎn)ID和存儲(chǔ)的鄰居錨節(jié)點(diǎn)信息向鄰居節(jié)點(diǎn)廣播，同時(shí)接收其他目標(biāo)節(jié)點(diǎn)的廣播消息，最后綜合所有鄰居錨節(jié)點(diǎn)的位置信息完成自身的區(qū)域估計(jì).未知節(jié)點(diǎn)i的估計(jì)區(qū)域表示為

(3)

(4)

(5)

(6)

式中：r為輸電網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)的最大通信距離；Lright，i，Lleft，i，Lup，i，Ldown，i分別為未知節(jié)點(diǎn)在4個(gè)方位上的節(jié)點(diǎn)位置，這4項(xiàng)參數(shù)共同確定了節(jié)點(diǎn)i的估計(jì)位置.

在分析區(qū)域估計(jì)的過(guò)程中發(fā)現(xiàn)，改進(jìn)后的區(qū)域估計(jì)只需要完成加減運(yùn)算或min(max)運(yùn)算即可完成未知節(jié)點(diǎn)的位置估計(jì)，這就為后續(xù)粒子群迭代有效地縮小了可行解空間，大大減少了計(jì)算量，節(jié)約了WSN網(wǎng)絡(luò)的節(jié)點(diǎn)能耗，從而促進(jìn)了輸電網(wǎng)絡(luò)的節(jié)點(diǎn)定位服務(wù).

2.3 基于粒子群進(jìn)化的WSN節(jié)點(diǎn)定位算法

為進(jìn)一步加快算法的搜索速度，增強(qiáng)算法的實(shí)用性，基于粒子群進(jìn)化的WSN節(jié)點(diǎn)定位算法還引入了權(quán)重自適應(yīng)的策略，以加快算法的收斂速度.

在粒子群算法中，權(quán)值w對(duì)節(jié)點(diǎn)適應(yīng)度函數(shù)的影響較大.如果w取值過(guò)大，則粒子速度變化較快，使得粒子容易跳出局部極小點(diǎn)，具有較強(qiáng)的全局搜索能力，但也會(huì)降低粒子群的局部搜索能力；反之，如果w取值過(guò)小，則粒子群的局部搜索能力增強(qiáng)，便于算法收斂，卻會(huì)降低粒子群的全局搜索能力.因此，有必要采用自適應(yīng)的權(quán)重w，在實(shí)現(xiàn)算法快速收斂的同時(shí)，保證粒子群進(jìn)化在全局和局部范圍內(nèi)達(dá)到有效的平衡.自適應(yīng)權(quán)重w表示為

(7)

式中，fa為未知節(jié)點(diǎn)的節(jié)點(diǎn)適應(yīng)度滿(mǎn)足要求的門(mén)限閾值.當(dāng)節(jié)點(diǎn)適應(yīng)度劇增時(shí)，自適應(yīng)降低w的權(quán)值；當(dāng)節(jié)點(diǎn)適應(yīng)度劇降時(shí)，自適應(yīng)增加w的權(quán)值.自適應(yīng)地調(diào)整權(quán)重w，使其停留在(wmin，wmax)范圍內(nèi)，能夠保持局部搜索與全局搜索能力的平衡，使得粒子群收斂的速度最快.

基于粒子群進(jìn)化的WSN節(jié)點(diǎn)定位算法具體步驟如下：

1) 對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行區(qū)域估計(jì)，縮小并確定可搜索的空間S.

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

3) 若滿(mǎn)足e

4) 淘汰50%適應(yīng)度較低的粒子，保留50%適應(yīng)度較高的優(yōu)選粒子.

5) 圍繞每個(gè)優(yōu)選粒子的位置設(shè)定一個(gè)局部的搜索范圍，并進(jìn)行局部搜索.

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

7) 判斷迭代終止條件是否滿(mǎn)足，若滿(mǎn)足，則粒子群迭代結(jié)束，以全局最優(yōu)解(gbesti)作為未知節(jié)點(diǎn)的位置估計(jì)；若不滿(mǎn)足，補(bǔ)充(E-e)/2個(gè)隨機(jī)粒子，并跳轉(zhuǎn)至步驟3).

為便于輸電網(wǎng)絡(luò)中實(shí)現(xiàn)WSN網(wǎng)絡(luò)測(cè)距，本文采用RSSI技術(shù)實(shí)現(xiàn)相鄰節(jié)點(diǎn)間的測(cè)距.由于實(shí)際網(wǎng)絡(luò)中節(jié)點(diǎn)布設(shè)、地形起伏等因素的影響，無(wú)線(xiàn)傳感器節(jié)點(diǎn)的通信覆蓋范圍不一定是圓形，往往導(dǎo)致測(cè)距誤差，因此，在仿真過(guò)程中需要考慮環(huán)境等因素引起的測(cè)距誤差并加以修正.

3 仿真結(jié)果與分析

3.1 仿真環(huán)境說(shuō)明

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

3.2 錨節(jié)點(diǎn)密度對(duì)定位性能的影響

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

表1 WSN節(jié)點(diǎn)定位的參數(shù)設(shè)置Tab.1 Parameter setting of WSN node localization

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

3.3 通信距離對(duì)定位性能的影響

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

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

3.4 測(cè)距誤差對(duì)定位性能的影響

節(jié)點(diǎn)定位會(huì)受部署環(huán)境的影響，比如信號(hào)衰減、通信范圍受限等.其中，測(cè)距誤差對(duì)節(jié)點(diǎn)定位影響尤為重要，這里通過(guò)實(shí)驗(yàn)進(jìn)一步進(jìn)行對(duì)比和分析.

圖4為4種算法在不同測(cè)距誤差下的定位誤差.當(dāng)測(cè)距誤差逐步增大，4種算法的定位誤差也呈現(xiàn)不斷增加的趨勢(shì).由于Improved DV算法是測(cè)距定位算法，測(cè)距過(guò)程中需要累加基于接收信號(hào)強(qiáng)度(RSSI)的測(cè)試距離，測(cè)距誤差對(duì)定位誤差的影響尤為明顯.當(dāng)RSSI測(cè)距誤差較小時(shí)，Improved DV算法性能與DPSO算法接近；當(dāng)RSSI測(cè)距誤差較大時(shí)，Improved DV算法性能急劇下降，定位誤差最大.綜合比較4種定位算法，在同等測(cè)距誤差的條件下，本文算法的節(jié)點(diǎn)定位誤差雖然也在逐步增加，但表現(xiàn)較為穩(wěn)定，且在4種算法中定位誤差最小，一直處于所有算法中誤差最低水平.這說(shuō)明本文算法抗測(cè)距誤差性能最佳，穩(wěn)定性最好，能夠適用于多種復(fù)雜惡劣的輸電網(wǎng)絡(luò)環(huán)境.

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

4 結(jié) 論

基于無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位對(duì)于輸電網(wǎng)絡(luò)的信息傳輸和故障判定具有重要意義，為改善輸電網(wǎng)絡(luò)中的節(jié)點(diǎn)定位精度，本文提出一種基于粒子群進(jìn)化的節(jié)點(diǎn)定位算法.該算法通過(guò)區(qū)域估計(jì)，縮小并限制傳感器節(jié)點(diǎn)的預(yù)估計(jì)區(qū)域空間，以簡(jiǎn)化計(jì)算復(fù)雜度，并通過(guò)引入粒子群競(jìng)爭(zhēng)和權(quán)重自適應(yīng)的機(jī)制，改善了無(wú)線(xiàn)傳感器節(jié)點(diǎn)的定位精確.通過(guò)仿真和分析發(fā)現(xiàn)，相比同類(lèi)的WSN節(jié)點(diǎn)定位算法，該算法在錨節(jié)點(diǎn)密度、通信距離、測(cè)距誤差等方面都具有性能優(yōu)勢(shì)，能夠顯著提升節(jié)點(diǎn)的定位精度，降低計(jì)算復(fù)雜度.該算法非常適用于現(xiàn)有的輸電網(wǎng)絡(luò)，利用輸電網(wǎng)絡(luò)搭載的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)，為輸電網(wǎng)絡(luò)監(jiān)測(cè)提供更高效、更準(zhǔn)確的定位服務(wù).