摘  要： 無線傳感器網(wǎng)絡(luò)通過少數(shù)確定錨節(jié)點(diǎn)計(jì)算到其他節(jié)點(diǎn)距離，確定節(jié)點(diǎn)坐標(biāo),。其中DV-Hop定位算法通過最小二乘法求解坐標(biāo),，累計(jì)誤差隨節(jié)點(diǎn)平均距離誤差呈指數(shù)增長(zhǎng)，定位精度較低,。提出了用粒子群PSO離散算法替代DV-Hop中的最小二乘法, 既發(fā)揮PSO全局搜索能力,，又避免標(biāo)準(zhǔn)PSO算法過早收斂的問題。實(shí)驗(yàn)結(jié)果表明,，新算法定位精度很高,，受距離誤差影響不大，能很好地應(yīng)用于無線傳感器網(wǎng)絡(luò)的定位過程,。

　　關(guān)鍵詞： 無線傳感器網(wǎng)絡(luò),；粒子群；DV-Hop定位算法,；離散算法

　　無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Networks)由大量傳感節(jié)點(diǎn)以多跳自組織方式構(gòu)成,，通過數(shù)據(jù)采集,、協(xié)調(diào)感知完成信息搜集和管理任務(wù),。無線傳感器網(wǎng)絡(luò)一般應(yīng)用于惡劣環(huán)境或是人無法抵達(dá)區(qū)域，受鋪設(shè)成本和能源供給限制,，只有少數(shù)匯聚節(jié)點(diǎn)配備GPS定位裝置,，通過與網(wǎng)絡(luò)其他傳感器節(jié)點(diǎn)接力通信完成對(duì)其定位過程,。典型的WSN由傳感器節(jié)點(diǎn)、匯聚節(jié)點(diǎn)和管理節(jié)點(diǎn)組成,，如圖1所示,。傳感器節(jié)點(diǎn)感知目標(biāo)信息后以多跳接力方式傳給匯聚節(jié)點(diǎn)，匯聚節(jié)點(diǎn)對(duì)附近傳感器節(jié)點(diǎn)信息匯總后通過衛(wèi)星基站,、互聯(lián)網(wǎng)傳送給管理用戶[1],。由于傳感器節(jié)點(diǎn)一般可移動(dòng)部署以適應(yīng)環(huán)境變化，如何精確定位傳感器節(jié)點(diǎn)坐標(biāo)成為WSN研究的熱點(diǎn)和難點(diǎn),。

　　1 WSN定位算法分類

　　無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法分為基于測(cè)距和無需測(cè)距算法兩類[2],。對(duì)于大部分傳感節(jié)點(diǎn)而言，當(dāng)定位誤差小于節(jié)點(diǎn)通信半徑的40%時(shí),，定位誤差對(duì)節(jié)點(diǎn)精確度的影響不大[2],。若使用測(cè)距定位不僅要配備額外硬件設(shè)備，增加節(jié)點(diǎn)成本,，還會(huì)加重電源補(bǔ)給負(fù)荷,。無需測(cè)距算法通過節(jié)點(diǎn)之間通信估算彼此之間距離、定位節(jié)點(diǎn)坐標(biāo),，簡(jiǎn)單方便,，得到廣泛應(yīng)用。其中最為經(jīng)典的是DV-Hop算法,。

　　2 DV-Hop算法

　　DV-Hop稱為距離向量跳段定位算法,，用網(wǎng)絡(luò)平均跳距和節(jié)點(diǎn)間最短跳數(shù)乘積表示節(jié)點(diǎn)之間距離，再利用大量冗余信息節(jié)點(diǎn)實(shí)現(xiàn)定位,。整個(gè)過程分為3個(gè)階段：

　　(1)計(jì)算抵達(dá)鄰居節(jié)點(diǎn)跳數(shù),。傳感節(jié)點(diǎn)定期向鄰居節(jié)點(diǎn)交換抵達(dá)網(wǎng)絡(luò)中其他節(jié)點(diǎn)距離，以跳數(shù)為單位,。最終每個(gè)傳感節(jié)點(diǎn){xi,，yi}都獲得自身參考節(jié)點(diǎn)跳數(shù)hi及參考坐標(biāo){xi，yi,，hi},。

　　(2)每個(gè)傳感節(jié)點(diǎn)使用式(1)計(jì)算到達(dá)其他參考節(jié)點(diǎn)的距離。

　　(3)傳感節(jié)點(diǎn)得到與其他參考節(jié)點(diǎn)距離后,，通過三角或多邊測(cè)量建立方程組,，最后利用最小二乘法求解方程組獲得節(jié)點(diǎn)坐標(biāo)。

　　DV-Hop實(shí)現(xiàn)簡(jiǎn)單,、方便快捷,，但算法中的距離通過節(jié)點(diǎn)跳數(shù)乘以網(wǎng)絡(luò)平均跳距得出[3]，不可避免地存在誤差,，加上最小二乘法求解精度依賴于網(wǎng)絡(luò)跳距初始參數(shù),，導(dǎo)致產(chǎn)生的誤差呈指數(shù)增長(zhǎng),、定位精度不高，并且節(jié)點(diǎn)密度越低,，拓?fù)湓讲灰?guī)則,，誤差越大。

　　3 基于粒子群定位算法思想

　　傳感節(jié)點(diǎn)記為P1(x1,，y1),，P2(x2，y2),，…,，Pn(xn，yn),，根據(jù)DV-Hop前兩階段估算的抵達(dá)網(wǎng)絡(luò)其他節(jié)點(diǎn)距離分別是d1,，d2…，dn,，估算距離與真實(shí)距離之間差值分別為ε1,，ε2，…,，εn,，得以下方程組：

　　傳感節(jié)點(diǎn)坐標(biāo)應(yīng)同時(shí)滿足式(2)方程組要求，若|ε1|+|ε2|+…+|εn|和越小,，則節(jié)點(diǎn)坐標(biāo)越優(yōu),、定位越精確，從而可利用最小二乘法求解過程轉(zhuǎn)換為使用粒子群算法求解全局最小最優(yōu)解的問題,，如式(3)所示,。

　　本文提出將粒子群(PSO)離散算法替代DV-Hop中的最小二乘法，用于求解節(jié)點(diǎn)最優(yōu)坐標(biāo),，既可以發(fā)揮PSO全局搜索能力,，又可以避免標(biāo)準(zhǔn)PSO算法中過早收斂問題，由此減小網(wǎng)絡(luò)跳距誤差對(duì)定位精度的影響范圍,。

　　4 標(biāo)準(zhǔn)粒子群算法

　　粒子群算法是基于鳥類群體行為研究的模擬算法,。鳥群在封閉空間隨機(jī)搜索食物，并且在這個(gè)空間只有一個(gè)全局最優(yōu)值[4],。假如所有鳥只都知道當(dāng)前位置與搜索食物之間的距離,，那么找到全局最優(yōu)解的最優(yōu)方案就是從身邊最近的鳥周圍區(qū)域進(jìn)行搜尋[5]。在粒子群算法中,，尋找最優(yōu)問題的每個(gè)解對(duì)應(yīng)搜索空間的每只鳥,，稱為粒子。每個(gè)粒子的初始化向量代表鳥的飛行位置和速率，每個(gè)粒子通過尋找附近粒子迭代搜尋最優(yōu)解,，具體算法如下：

　　假設(shè)在一個(gè)d維搜索空間中，有n個(gè)粒子組成的粒子群X=(X1,，X2,，…，Xn)T,，其中第i個(gè)粒子位置為Xi=(Xi1,，Xi2，…,，XiD)T,，速率為Vi=(Vi1，Vi2,，…,，Vid)T，極值為Pi=(Pi1,，Pi2,，…，Pid)T,，種群全局極值為Pg=(Pg1,，Pg2，…,，Pgd)T,，每個(gè)粒子找到下一粒子后按以下公式更新當(dāng)前位置和速率[6]：

　　其中，k表示迭代次數(shù),，c1,、c2為加速系數(shù)，rand是[0,，1]區(qū)間選取的隨機(jī)數(shù),，p是第i個(gè)粒子的個(gè)體極值在第d維的分量，p是群體全局極值在第d維的分量,，x,、v分別是第i個(gè)粒子經(jīng)k次迭代后的第d維位置和速率，w是粒子保持運(yùn)動(dòng)慣性權(quán)重,。粒子通過不斷更新當(dāng)前位置和速率最終找到全局最優(yōu)解,，完成搜索過程。

　　5 新算法定位模型

　　5.1 離散粒子群算法

　　粒子群算法前期收斂速率快,，但容易出現(xiàn)前期局部最優(yōu),、后期收斂緩慢的問題。改進(jìn)離散粒子群算法在于更新粒子當(dāng)前位置和速率前引入離散運(yùn)動(dòng)方程式：

　　d維分量。粒子的位置只有“0”,、“1”兩種狀態(tài),，速率越小，粒子取“0”幾率越大,，反之取“1”,。改進(jìn)離散粒子群算法使得函數(shù)sig(V)不會(huì)過于接近“0”或“1”，保證算法以一定概率從一種狀態(tài)躍遷到另一種狀態(tài),，從而避免算法過早收斂,，出現(xiàn)局部最優(yōu)現(xiàn)象。

　　5.2 新算法適應(yīng)度值選擇

　　新算法通過估計(jì)的距離與真實(shí)距離之間的差值ε1+ε2+…+εn之和判斷粒子所處位置優(yōu)劣,，以此確定是否符合全局最優(yōu)解要求,。差值之和越小，適應(yīng)度值越大,。求解適應(yīng)度公式為：

　　其中,，n為傳感節(jié)點(diǎn)數(shù)量；hi為傳感節(jié)點(diǎn)抵達(dá)網(wǎng)絡(luò)其他節(jié)點(diǎn)跳數(shù),，由DV-Hop算法第一階段獲得,。由于傳感節(jié)點(diǎn)跳數(shù)越多，誤差累積越大,，因此在計(jì)算適應(yīng)度時(shí)加入權(quán)重,，hi越大的傳感節(jié)點(diǎn)對(duì)適應(yīng)值影響越小。

　　5.3 新算法粒子聚集度

　　在標(biāo)準(zhǔn)PSO算法中,，兩個(gè)粒子之間的距離表示其相似程度大小,，距離越近相似度越高。新算法用s(i,，j)表示粒子i和粒子j之間的相似度,，滿足以下條件：

　　其中，d(i,，j)為粒子i和粒子j之間的距離,，dmin、dmax表示所有粒子之間距離的最小值和最大值,。隨著迭代次數(shù)增多,，粒子適應(yīng)度越大，與最優(yōu)粒子相似度越高,，位置越趨于全局最優(yōu)解,，最終聚集在一起。新算法聚集度為：

　　其中,，C(t)是粒子群經(jīng)t次迭代的聚集度,，m為種群規(guī)模,。種群聚集度最密的粒子群收斂于當(dāng)前全局最優(yōu)解。

　　5.4 新算法定位流程

　　新算法采用改進(jìn)PSO離散算法替代DV-Hop算法中第3階段的最小二乘法,，利用離散PSO迭代求解避免網(wǎng)絡(luò)跳距誤差對(duì)定位精度帶來的影響,，并得到3個(gè)全局體極值的幾何質(zhì)心解，最后計(jì)算傳感節(jié)點(diǎn)坐標(biāo),。具體步驟如下,。

　　(1)基于DV-Hop算法第1階段和第2階段，傳感節(jié)點(diǎn)間通過與鄰居節(jié)點(diǎn)通信獲得自身參考坐標(biāo){xi,，yi，hi},，并計(jì)算抵達(dá)網(wǎng)絡(luò)其他節(jié)點(diǎn)距離,。

　　(2)根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模和區(qū)域大小初始化種群，計(jì)算每個(gè)粒子適應(yīng)度,，每個(gè)粒子位置都是節(jié)點(diǎn)定位坐標(biāo)的可行解,。

　　(3)根據(jù)適應(yīng)度大小更新粒子個(gè)體極值，同時(shí)找出全局適應(yīng)度最好的3個(gè)個(gè)體極值保存在近優(yōu)解集合中,。

　　(4)根據(jù)粒子速率利用離散運(yùn)動(dòng)方程式(7)對(duì)粒子群狀態(tài)進(jìn)行躍遷,，避免算法過早收斂。

　　(5)根據(jù)式(4)重新計(jì)算粒子當(dāng)前位置和速率,。

　　(6)根據(jù)式(9)計(jì)算每個(gè)粒子與全局近優(yōu)解相似度,，并根據(jù)式(10)計(jì)算當(dāng)前迭代種群的聚集度。

　　(7)判斷是否滿足結(jié)束條件（達(dá)到最大迭代次數(shù)或保存近優(yōu)數(shù)組中的3個(gè)個(gè)體極值都達(dá)到最優(yōu)要求),，結(jié)束迭代循環(huán),，獲得3個(gè)全局體極值坐標(biāo)，否則跳到步驟(3),。

　　(8)通過極值幾何質(zhì)心坐標(biāo)計(jì)算定位傳感節(jié)點(diǎn)位置,。

　　6 仿真測(cè)試

　　6.1 仿真環(huán)境

　　仿真環(huán)境設(shè)為100 m×100 m二維區(qū)域，節(jié)點(diǎn)通信半徑為20 m,，傳感節(jié)點(diǎn)比例為80%,，初始化粒子群規(guī)模200，最大迭代次數(shù)500,，慣性權(quán)重Wmax=0.9,，Wmin=0.4，平均定位誤差評(píng)價(jià)為：

　　6.2 定位誤差分析

　　新算法用PSO離散（DPSO）算法替代DV-Hop中的最小二乘法以計(jì)算節(jié)點(diǎn)坐標(biāo),，減小DV-Hop網(wǎng)絡(luò)跳距誤差對(duì)定位精度的影響,。在相同網(wǎng)絡(luò)環(huán)境下，新算法在測(cè)距誤差為 20%的定位誤差明顯小于DV-Hop算法,，如圖2所示,。

　　6.3 標(biāo)準(zhǔn)偏差分析

　　在測(cè)距誤差逐漸增加時(shí),，開始兩種算法定位標(biāo)準(zhǔn)偏差都有所增長(zhǎng)，但新算法相比DV-Hop中的標(biāo)準(zhǔn)偏差增長(zhǎng)更為緩慢,，如圖3所示,。因?yàn)樾滤惴ㄕ`差增長(zhǎng)受節(jié)點(diǎn)平均距離誤差影響，而DV-Hop算法誤差激增是由于最小二乘法對(duì)節(jié)點(diǎn)平均距離誤差放大的結(jié)果,。當(dāng)新算法測(cè)距誤差增長(zhǎng)到10%時(shí),，標(biāo)準(zhǔn)偏差開始降低，這是由于在計(jì)算適應(yīng)度時(shí)加入權(quán)重,，hi越大的傳感節(jié)點(diǎn)對(duì)適應(yīng)值影響越小,，節(jié)點(diǎn)平均距離誤差隨節(jié)點(diǎn)距離增長(zhǎng)影響越弱，最大測(cè)距標(biāo)準(zhǔn)偏差收斂于2 m以內(nèi),，可見新算法在定位平均測(cè)距誤差較大的情況下更具優(yōu)勢(shì),。

　　6.4 收斂性分析

　　與標(biāo)準(zhǔn)PSO算法相比，兩種算法定位誤差都隨迭代次數(shù)增多而減小,，如圖4所示,。在迭代次數(shù)較少時(shí)兩種算法誤差較大，這是因?yàn)榱Ｗ尤撼跏蓟^程中粒子分布隨機(jī)性造成的,。標(biāo)準(zhǔn)PSO算法在迭代次數(shù)達(dá)到100時(shí),，曲線趨于平穩(wěn)，定位誤差起伏不大,，算法開始收斂,，但定位誤差明顯大于新算法，由此推斷算法過早收斂陷入局部最優(yōu)解,。而新算法在迭代次數(shù)達(dá)到120時(shí),，定位誤差才接近最優(yōu)解，最終定位誤差收斂于2 m以內(nèi),，這與圖3實(shí)驗(yàn)數(shù)據(jù)一致,。

　　本文采用粒子群離散算法替代DV-Hop算法中的最小二乘法，避免網(wǎng)絡(luò)跳距估計(jì)誤差對(duì)定位精度帶來的影響,。接下來的工作將著眼于減少算法復(fù)雜度,，降低無線傳感網(wǎng)絡(luò)能耗問題，以減少實(shí)際部署中對(duì)環(huán)境的依賴程度,。

　　參考文獻(xiàn)

　　[1] NICULESCU D.Localized positioning in ad-hoc networks[J].IEEE International Workshop on Sensor Network Protocols and Applications,，2003，1(2)：42-50.

　　[2] PATWARI N.Relative location estimation in wireless sensor networks[J].IEEE Transactions on Signal Processing,，2003,，51(8)：2137-2148.

　　[3] RANDOLPH.A self-localization method for wireless sensor networks[J].EURASIP Journal on Applied Signal Processing，2003(4)：348-358.

　　[4] LANGENDOEN K.Distributed localization in wireless sensornetworks[J].Computer Networks.2003,，43(4)：499-518.

　　[5] GUSTAFSSON F.Mobile positioning using wireless networks[J].IEEE Signal Processing Magazine,，2005,，22(4)：41-53.

　　[6] YEDAVALLI K.Sequence-based localization in wireless sensor networks[J].IEEE Transactions on Mobile Computing，2008,，7(1)：81-94.