基于跳距修正與獅群優(yōu)化的WSNs三維定位算法*

茍平章，劉學(xué)治，孫夢源，何 博

(西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，甘肅 蘭州 730070)

1 引言

無線傳感器網(wǎng)絡(luò)WSNs (Wireless Sensor Networks)中的節(jié)點(diǎn)用來感知、采集和處理網(wǎng)絡(luò)分布在比較危險(xiǎn)的復(fù)雜區(qū)域內(nèi)時(shí)各種環(huán)境和監(jiān)測對(duì)象的信息，如果節(jié)點(diǎn)位置無法確定，收集到的各種監(jiān)測信息將毫無意義[1]。因此，進(jìn)行節(jié)點(diǎn)感知半徑優(yōu)化，減少節(jié)點(diǎn)定位過程中錨節(jié)點(diǎn)能耗，提高節(jié)點(diǎn)定位精度成為WSNs研究中的重要問題之一。實(shí)際應(yīng)用中WSNs節(jié)點(diǎn)一般不會(huì)分布于絕對(duì)的二維平面，三維定位算法更符合實(shí)際定位需求，如何減少基于三維空間的節(jié)點(diǎn)定位誤差已成為研究熱點(diǎn)[2]。

文獻(xiàn)[3]提出一種結(jié)合DV-Hop(Distance Vector-Hop)和RSSI(Received Signal Strength Indicator)的優(yōu)化算法，通過將計(jì)算出的待定位節(jié)點(diǎn)與錨節(jié)點(diǎn)間的距離作為單隱層前饋神經(jīng)網(wǎng)絡(luò)訓(xùn)練好的網(wǎng)絡(luò)模型的輸入，形成完整的拓?fù)溆?xùn)練集，取代網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，得到待定位節(jié)點(diǎn)的位置，使得節(jié)點(diǎn)定位精度和抗干擾性得到提高。文獻(xiàn)[4]使用MAC(Media Access Control)層發(fā)現(xiàn)信標(biāo)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，以減少傳輸過程的沖突，將單跳鄰居節(jié)點(diǎn)分為2種進(jìn)行通信降低了能耗，利用修正因子降低定位誤差。文獻(xiàn)[5]提出一種增強(qiáng)的拉格朗日矩陣填充算法，根據(jù)測量值來填充未測距離并分離噪聲數(shù)據(jù)，采用MDS(Multi-Dimensional Scaling)方法實(shí)現(xiàn)節(jié)點(diǎn)的精確定位。文獻(xiàn)[6]將差分進(jìn)化DE (Differential Evolution)算法和DV-Hop相結(jié)合，使用最小均方誤差準(zhǔn)則計(jì)算每跳平均距離，將改進(jìn)的DE算法應(yīng)用于求解待定位節(jié)點(diǎn)估計(jì)位置對(duì)應(yīng)的全局最優(yōu)解，降低了節(jié)點(diǎn)的平均定位誤差，提高了算法的收斂速度和穩(wěn)定性，但是算法的復(fù)雜度有所增加。文獻(xiàn)[7]結(jié)合粒子群算法和混合復(fù)雜進(jìn)化算法的優(yōu)點(diǎn)，提出2種三維定位算法，提高了節(jié)點(diǎn)的定位精度，但是沒有考慮到定位過程中待定位節(jié)點(diǎn)到錨節(jié)點(diǎn)之間距離的誤差。文獻(xiàn)[8]通過使用RSS(Received Signal Strength)和AOA(Angle Of Arrival)混合測量相結(jié)合的方法，提升了不同場景下的定位性能。文獻(xiàn)[9]使用迭代定位的方法減少了遠(yuǎn)距離待定位節(jié)點(diǎn)的累積誤差，將計(jì)算出坐標(biāo)值的待定位節(jié)點(diǎn)升級(jí)為輔助錨節(jié)點(diǎn)，利用輔助錨節(jié)點(diǎn)平衡了網(wǎng)絡(luò)能量消耗，并對(duì)網(wǎng)絡(luò)跳數(shù)、跳距和計(jì)算方法進(jìn)行了優(yōu)化，減少了算法的定位誤差和計(jì)算量。文獻(xiàn)[10]利用改進(jìn)的二次柵格掃描定位算法完成初步定位，使用三角形質(zhì)心迭代定位算法提升了定位精度。文獻(xiàn)[11]提出一種通過質(zhì)心迭代計(jì)算待定位節(jié)點(diǎn)坐標(biāo)的三維定位方法，提高了節(jié)點(diǎn)定位精度和定位覆蓋率。文獻(xiàn)[12]將三維空間劃分成網(wǎng)格單元，把數(shù)據(jù)對(duì)象嵌入三維空間，使用一個(gè)密度閾值來識(shí)別稠密單位，通過MeanShift算法迭代計(jì)算出概率密度的最優(yōu)解，達(dá)到對(duì)節(jié)點(diǎn)的精確定位。

綜合以上研究，本文針對(duì)三維DV-Hop的跳數(shù)劃分、跳距設(shè)置和計(jì)算方法造成的定位精度不高的問題，提出一種基于跳距修正與獅群優(yōu)化LSO(Lion Swarm Optimization)的WSNs三維定位算法HCLSO-3D(3D positioning algorithm based on Hop Correction and Lion Swarm Optimization)來提高節(jié)點(diǎn)定位精度。首先，使用多通信半徑的方法，對(duì)傳統(tǒng)DV-Hop模型中跳數(shù)進(jìn)行細(xì)化，得到更合理的跳數(shù)，減少對(duì)平均跳距和待定位節(jié)點(diǎn)到錨節(jié)點(diǎn)距離計(jì)算帶來的累積誤差。其次，使用相似路徑搜索算法，獲取與待定位節(jié)點(diǎn)到相應(yīng)錨節(jié)點(diǎn)之間最相似的錨節(jié)點(diǎn)對(duì)的路徑，對(duì)此路徑的平均跳距進(jìn)行修正，并作為待定位節(jié)點(diǎn)到對(duì)應(yīng)錨節(jié)點(diǎn)的平均跳距，減少其他錨節(jié)點(diǎn)的影響，降低平均跳距的誤差。最后，使用獅群優(yōu)化算法對(duì)待定位節(jié)點(diǎn)的坐標(biāo)進(jìn)行計(jì)算，得到最優(yōu)的坐標(biāo)值。

2 三維DV-Hop算法和獅群優(yōu)化算法

2.1 傳感器節(jié)點(diǎn)監(jiān)測區(qū)域

無線傳感器節(jié)點(diǎn)被隨機(jī)分布在三維空間的監(jiān)測區(qū)域中，圖1所示為仿真模擬出的一個(gè)典型的含有多個(gè)波峰和波谷的三維空間監(jiān)測區(qū)域地形圖，被隨機(jī)拋灑到區(qū)域中的傳感器節(jié)點(diǎn)通過三維DV-Hop定位算法確定自身位置，然后將自身坐標(biāo)及監(jiān)測信息傳輸?shù)絽R聚節(jié)點(diǎn)，進(jìn)行下一步數(shù)據(jù)處理。

Figure 1 A topographic map of a monitoring area in three-dimensional space圖1 三維空間監(jiān)測區(qū)域地形圖

2.2 三維DV-Hop定位算法

DV-Hop定位算法[13]是一種距離無關(guān)的定位算法，三維DV-Hop定位算法是從二維空間向三維空間的一種推廣，其基本過程與二維DV-Hop定位算法過程類似，主要步驟如下：

步驟1節(jié)點(diǎn)間信息傳播與跳數(shù)估算。網(wǎng)絡(luò)中所有錨節(jié)點(diǎn)廣播自身的位置和跳數(shù)信息，在錨節(jié)點(diǎn)通信半徑內(nèi)的所有節(jié)點(diǎn)將獲得錨節(jié)點(diǎn)的信息并保存，節(jié)點(diǎn)將跳數(shù)信息加1后向鄰居節(jié)點(diǎn)傳播自身的標(biāo)識(shí)信息、更新后的跳數(shù)信息和接收到的錨節(jié)點(diǎn)信息，在信息傳遞過程中，待定位節(jié)點(diǎn)只保存到各個(gè)錨節(jié)點(diǎn)的最小跳數(shù)，網(wǎng)絡(luò)中所有節(jié)點(diǎn)獲得錨節(jié)點(diǎn)信息后傳播過程結(jié)束。

步驟2待定位節(jié)點(diǎn)與錨節(jié)點(diǎn)之間跳距的估算。所有錨節(jié)點(diǎn)保存了到其余錨節(jié)點(diǎn)的最小跳數(shù)，每個(gè)錨節(jié)點(diǎn)計(jì)算平均距離，并且在網(wǎng)絡(luò)中傳播平均跳距信息，錨節(jié)點(diǎn)最近范圍內(nèi)的待定位節(jié)點(diǎn)保存平均跳距并計(jì)算到各個(gè)錨節(jié)點(diǎn)的距離。

Hopsizei=

(1)

其中，(xi,yi,zi)和(xj,yj,zj)為錨節(jié)點(diǎn)i和錨節(jié)點(diǎn)j的實(shí)際坐標(biāo)位置；i、j為錨節(jié)點(diǎn)的標(biāo)識(shí)，其值的范圍由網(wǎng)絡(luò)中的錨節(jié)點(diǎn)個(gè)數(shù)決定；hij是錨節(jié)點(diǎn)i和錨節(jié)點(diǎn)j的最小跳數(shù);Hopsizei表示錨節(jié)點(diǎn)i的平均跳距。錨節(jié)點(diǎn)i和錨節(jié)點(diǎn)j之間的估算距離dij為：

dij=Hopsizei×hij

(2)

步驟3待定位節(jié)點(diǎn)坐標(biāo)計(jì)算。在三維空間中，得到4個(gè)及以上的待定位節(jié)點(diǎn)到錨節(jié)點(diǎn)之間的估計(jì)距離后，通過極大似然估計(jì)法計(jì)算出待定位節(jié)點(diǎn)的坐標(biāo)。

2.3 獅群優(yōu)化算法

獅群優(yōu)化LSO算法[14,15]是一種群體智能算法，模擬自然界中獅群的行為模式，算法中有3種角色，分別為：獅王、母獅及幼獅。按照自然界的“適者生存”法則，不同角色的獅子具有不同的位置更新方式。獅子位置更新方式的多樣化保證算法快速收斂，不易陷入局部最優(yōu)，精度較高，能較好地獲得全局最優(yōu)解。

在D維空間中初始化獅群數(shù)量為N，成年獅數(shù)量為NL。

(3)

其中，成年獅所占比例因子β為(0,1)的隨機(jī)數(shù)，一般取值小于0.5。成年獅中僅有一頭為公獅，剩余為母獅，幼獅數(shù)量為N-NL,第i頭獅子位置表示為：

xi=(xi1,xi2,xi3,…,xiD),1≤i≤N

(4)

獅王、母獅及幼獅分別按照式(5)～式(7)更新自身位置：

(5)

(6)

(7)

(8)

(9)

(10)

(11)

3 HCLSO-3D定位算法

3.1 多通信半徑設(shè)置和跳數(shù)優(yōu)化

傳統(tǒng)的三維 DV-Hop算法在劃分跳數(shù)時(shí)，錨節(jié)點(diǎn)通信半徑內(nèi)的所有節(jié)點(diǎn)都稱為單跳節(jié)點(diǎn)，但這些節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離往往并不相等，導(dǎo)致距離估計(jì)產(chǎn)生誤差。在計(jì)算平均跳距時(shí)，跳數(shù)的誤差會(huì)影響平均跳距的值，估計(jì)距離與待定位節(jié)點(diǎn)和錨節(jié)點(diǎn)之間的真正距離有明顯差異。本文采用多通信半徑的方式對(duì)錨節(jié)點(diǎn)所有通信范圍內(nèi)的節(jié)點(diǎn)跳數(shù)進(jìn)行重新計(jì)算和劃分，進(jìn)而影響多跳的劃分，減少由跳數(shù)不合實(shí)際帶來的累積誤差，其基本步驟如下：

步驟1設(shè)置預(yù)傳播半徑?？紤]錨節(jié)點(diǎn)和待定位節(jié)點(diǎn)在總節(jié)點(diǎn)中所占的比例，設(shè)置預(yù)傳播半徑R:

(12)

其中，R為預(yù)傳播半徑；n為多通信半徑數(shù)量，其值為錨節(jié)點(diǎn)占總節(jié)點(diǎn)比例的倒數(shù)值取整；r為最大通信半徑。錨節(jié)點(diǎn)比例越大，WSNs三維空間中錨節(jié)點(diǎn)覆蓋的待定位節(jié)點(diǎn)數(shù)越少，預(yù)傳播半徑的劃分越粗糙，反之，預(yù)傳播半徑的劃分越精細(xì)。

步驟2預(yù)傳播。預(yù)傳播階段中，各個(gè)錨節(jié)點(diǎn)使用設(shè)置的預(yù)傳播半徑進(jìn)行多通信半徑的傳播，將原本通信范圍內(nèi)的所有單跳節(jié)點(diǎn)通過不同的通信半徑進(jìn)行劃分，使得待定位節(jié)點(diǎn)到錨節(jié)點(diǎn)的跳數(shù)計(jì)算得更加準(zhǔn)確。

步驟3全網(wǎng)絡(luò)傳播階段。按照傳統(tǒng)三維DV-Hop步驟1進(jìn)行節(jié)點(diǎn)信息的傳播和跳數(shù)估計(jì)，此時(shí)各個(gè)錨節(jié)點(diǎn)和單跳范圍內(nèi)被細(xì)化跳數(shù)值的節(jié)點(diǎn)向外傳播信息，多跳的跳數(shù)值受到單跳值的影響，被劃分得更加細(xì)致、精確。

3.2 跳距修正

在傳統(tǒng)三維DV-Hop定位模型中，待定位節(jié)點(diǎn)的平均跳距由距離其最近的錨節(jié)點(diǎn)計(jì)算得出，待定位節(jié)點(diǎn)保存并利用平均跳距計(jì)算到各個(gè)錨節(jié)點(diǎn)之間的距離。傳統(tǒng)的計(jì)算方法使用同一個(gè)平均跳距計(jì)算待定位節(jié)點(diǎn)到所有不同錨節(jié)點(diǎn)之間的距離，由于不同錨節(jié)點(diǎn)對(duì)待定位節(jié)點(diǎn)的影響不同，會(huì)使得平均跳距產(chǎn)生較大的誤差，影響距離的計(jì)算。本文采用相似路徑搜索算法[16]得到一條與待定位節(jié)點(diǎn)到對(duì)應(yīng)錨節(jié)點(diǎn)之間路徑最相似的錨節(jié)點(diǎn)對(duì)的路徑，計(jì)算此路徑的平均跳距并進(jìn)行修正，作為此待定位節(jié)點(diǎn)到對(duì)應(yīng)錨節(jié)點(diǎn)的平均跳距值。隨著對(duì)應(yīng)錨節(jié)點(diǎn)的改變，平均跳距值也會(huì)相應(yīng)地改變，最終利用平均跳距與被優(yōu)化的跳數(shù)值相乘得到精確的距離。其基本步驟如下：

步驟1相似路徑搜索。節(jié)點(diǎn)在網(wǎng)絡(luò)中傳播信息時(shí)會(huì)將自身的標(biāo)識(shí)和到各個(gè)錨節(jié)點(diǎn)的跳數(shù)信息傳遞給鄰居節(jié)點(diǎn)，在網(wǎng)絡(luò)傳播完成之后，每個(gè)待定位節(jié)點(diǎn)會(huì)存儲(chǔ)到各個(gè)錨節(jié)點(diǎn)所經(jīng)過的最短路徑節(jié)點(diǎn)序列，每個(gè)錨節(jié)點(diǎn)會(huì)存儲(chǔ)到各個(gè)錨節(jié)點(diǎn)所經(jīng)過的最短路徑節(jié)點(diǎn)序列。本文使用相似度系數(shù)SC來表示路徑間的相似程度，其定義如式(13)所示：

(13)

其中，A表示待定位節(jié)點(diǎn)到目標(biāo)錨節(jié)點(diǎn)的最短路徑序列集合，B表示其余錨節(jié)點(diǎn)到目標(biāo)錨節(jié)點(diǎn)的最短路徑序列集合，n()為集合中元素的個(gè)數(shù)。計(jì)算集合A與不同集合B之間的相似度系數(shù)，其中相似度系數(shù)值最大的路徑即為搜索結(jié)果。

步驟2平均跳距計(jì)算。相似路徑搜索得到的結(jié)果是與待定位節(jié)點(diǎn)到目標(biāo)錨節(jié)點(diǎn)路徑最為相似的2個(gè)錨節(jié)點(diǎn)之間的路徑。2個(gè)錨節(jié)點(diǎn)通過式(1)得到它們之間的平均跳距值，作為此待定位節(jié)點(diǎn)到目標(biāo)錨節(jié)點(diǎn)的平均跳距。

步驟3平均跳距修正。在三維空間中，網(wǎng)絡(luò)拓?fù)涓訌?fù)雜，2個(gè)錨節(jié)點(diǎn)計(jì)算得出的平均跳距與它們之間的實(shí)際最優(yōu)跳距(最大通信半徑)存在偏差。本文計(jì)算得出平均跳距和最大通信半徑之間的修正量φi，進(jìn)而對(duì)平均跳距進(jìn)行修正，定義誤差系數(shù)ωi為：

ωi=(r-Hopsize)/r

(14)

其中，r為最大通信半徑，Hopsize為計(jì)算得到的平均跳距。定義修正量φi為：

φi=Hopsize×ωi

(15)

修正量φi表示平均跳距與最大通信半徑r之間的校正值，反映了平均跳距與理想距離r之間的差異。修正之后的平均跳距Hopsize′由式(16)計(jì)算得出：

Hopsize′=Hopsize+φi

(16)

步驟4依次計(jì)算所有待定位節(jié)點(diǎn)到各個(gè)錨節(jié)點(diǎn)之間修正后的平均跳距值。

通過多通信半徑進(jìn)行跳數(shù)優(yōu)化及跳距修正的算法偽代碼描述如算法1所示：

算法1跳數(shù)優(yōu)化與跳距修正

輸入:錨節(jié)點(diǎn)個(gè)數(shù)，總節(jié)點(diǎn)個(gè)數(shù)，最大通信半徑r，多通信半徑數(shù)量n。

輸出:待定位節(jié)點(diǎn)到各個(gè)錨節(jié)點(diǎn)的距離。

1. Initial network environment;//初始化網(wǎng)絡(luò)環(huán)境

2.fori=1 tondo //多通信半徑廣播

4.if(unknown nodes don’t receive the same signal)then

6.endif

7.endfor

8. Anchor nodes broadcast their packets;//多跳傳播

9.if(unknown nodes receive the anchor nodes packets)then

10.Hop++;

11.Forward the message;

12.endif

13.if( the unknown node receive anchor nodes messages numbers < 4 )then//定位條件判斷

14. the unknown node can’t be located;

15.else

16. Search path set ofB;//路徑搜索

17. ComputingSCandHopsizeunknownby equation(13) and equation(1);//計(jì)算相似度與平均跳距

18. Corrected forHopsizeunknown;//平均跳距修正

19. Computing the distance from unknown nodes to anchor nodes by equation(2);//計(jì)算距離

20.endif

3.3 LSO算法求解待定位節(jié)點(diǎn)坐標(biāo)

LSO算法對(duì)初值的要求不高，算法尋優(yōu)速度較快，有較強(qiáng)的全局尋優(yōu)能力。表1為在30維空間中，LSO算法、標(biāo)準(zhǔn)粒子群算法和人工蜂群算法對(duì)Sphere函數(shù)的尋優(yōu)結(jié)果[14]。可以看出，LSO在高維空間中，具有收斂速度快、精度高和能較好地獲得全局最優(yōu)解的優(yōu)點(diǎn)。本文將待定位節(jié)點(diǎn)坐標(biāo)值的計(jì)算看作一種尋優(yōu)問題，通過設(shè)置適應(yīng)值函數(shù)，使用LSO在問題的求解空間中找到符合條件最優(yōu)解，即為待定位節(jié)點(diǎn)的坐標(biāo)值。

Table 1 Test results of three algorithms on Sphere function 表1 3種算法在Sphere函數(shù)上的測試結(jié)果

目標(biāo)函數(shù)和LSO的適應(yīng)值函數(shù)定義如下：

(17)

(18)

(19)

其中，(x,y,z)為獅群優(yōu)化算法求解的待定位節(jié)點(diǎn)坐標(biāo)；(xi,yi,zi)為錨節(jié)點(diǎn)坐標(biāo)；di為待定位節(jié)點(diǎn)到錨節(jié)點(diǎn)i的距離；M為錨節(jié)點(diǎn)數(shù)量；εi為錨節(jié)點(diǎn)與搜索得到的待定位節(jié)點(diǎn)的距離與優(yōu)化后的三維DV-Hop算法計(jì)算出的距離的差值；f(x,y,z)是在不同的權(quán)值條件下每一個(gè)εi的和，當(dāng)求和最小時(shí)，得到的解即為最優(yōu)解；fit為適應(yīng)值函數(shù)，在進(jìn)行尋優(yōu)時(shí)，適應(yīng)值越大，解越接近最優(yōu)值。

獅群優(yōu)化算法求解坐標(biāo)的步驟如下：

步驟1在三維空間中隨機(jī)初始化N個(gè)坐標(biāo)值作為獅群中獅子的位置，設(shè)置最大迭代次數(shù)T，成年獅比例因子β。

步驟2計(jì)算獅群中不同角色獅子數(shù)量，獅王位置設(shè)置為初始種群最優(yōu)位置，設(shè)置個(gè)體歷史最優(yōu)位置為各獅的當(dāng)前位置。

步驟3根據(jù)式(5)～式(7)更新獅王、母獅和幼獅的位置，并根據(jù)式(19)計(jì)算適應(yīng)度值。

步驟4更新自身和獅群歷史最優(yōu)位置。判斷算法是否滿足結(jié)束條件(發(fā)現(xiàn)理論值最優(yōu)值或與最后2次最優(yōu)值之差的絕對(duì)值小于設(shè)定精度)，如果滿足轉(zhuǎn)步驟6，否則轉(zhuǎn)步驟5。

步驟5每隔一定迭代次數(shù)，重新排序(約10次)，確定獅王、母獅及幼獅位置，轉(zhuǎn)步驟3。

步驟6輸出獅王的位置，即待定位節(jié)點(diǎn)的坐標(biāo)值，算法結(jié)束。

利用LSO算法求解待定位節(jié)點(diǎn)坐標(biāo)的偽代碼描述如算法2所示：

算法2獅群優(yōu)化算法求解坐標(biāo)值

輸入:錨節(jié)點(diǎn)坐標(biāo)，待定位節(jié)點(diǎn)到對(duì)應(yīng)錨節(jié)點(diǎn)距離。

輸出:待定位節(jié)點(diǎn)估計(jì)坐標(biāo)值。

1. Initial number of lions:N, adult lion population:NL,Dimension:D,generation:G;//初始化參數(shù)值

2.g=-1;

3.fori=1 toNdo//初始化獅群位置

4.forj=1 toDdo

6.endfor

7.endfor

8.fori=1 toNdo

10.endfor

12.while(|fit(x)|>=ε)‖(g≤G)do/*迭代終止條件判斷*/

17. Update;//更新個(gè)體最優(yōu)和全局最優(yōu)

18.endwhile

19.returnthe best solutionkingx.

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

4.1 仿真實(shí)驗(yàn)設(shè)計(jì)與環(huán)境設(shè)置

本節(jié)使用Matlab進(jìn)行編程仿真，對(duì)比分析錨節(jié)點(diǎn)個(gè)數(shù)、通信半徑和節(jié)點(diǎn)個(gè)數(shù)3個(gè)參數(shù)的變化對(duì)HCLSO-3D定位算法、3D-DVHop和文獻(xiàn)[16]定位算法的影響，證明HCLSO-3D定位算法的有效性和優(yōu)越性。在相同環(huán)境下進(jìn)行100次仿真實(shí)驗(yàn)，取平均值作為仿真實(shí)驗(yàn)最終結(jié)果，仿真實(shí)驗(yàn)區(qū)域設(shè)定為正立方體，在設(shè)定區(qū)域內(nèi)隨機(jī)生成100個(gè)包括待定位節(jié)點(diǎn)和錨節(jié)點(diǎn)的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)。

網(wǎng)絡(luò)環(huán)境與相關(guān)參數(shù)值設(shè)置如表2所示。

Table 2 Network environment and parameter settings表2 網(wǎng)絡(luò)環(huán)境與參數(shù)設(shè)置

圖2為仿真實(shí)驗(yàn)區(qū)域內(nèi)WSNs隨機(jī)生成的節(jié)點(diǎn)分布圖，其中方形代表信標(biāo)節(jié)點(diǎn)即錨節(jié)點(diǎn)，圓形代表待定位節(jié)點(diǎn)。

Figure 2 Random distribution of three-dimensional spatial nodes圖2 三維空間節(jié)點(diǎn)隨機(jī)分布圖

在不同環(huán)境下的仿真實(shí)驗(yàn)結(jié)果需要相同的定位標(biāo)準(zhǔn)來衡量算法的定位效果，本文采用所有節(jié)點(diǎn)的平均定位誤差作為衡量標(biāo)準(zhǔn)，其計(jì)算方法如式(20)所示：

ErrEavg=

(20)

其中，ErrEavg代表平均定位誤差,(x′i,y′i,z′i)代表待定位節(jié)點(diǎn)i的實(shí)際坐標(biāo)值，(xi,yi,zi)代表待定位節(jié)點(diǎn)i的估計(jì)坐標(biāo)值，r為節(jié)點(diǎn)的最大通信半徑，P為待定位節(jié)點(diǎn)的總數(shù)。

4.2 錨節(jié)點(diǎn)數(shù)與平均定位誤差分析

圖3為節(jié)點(diǎn)總數(shù)為100，通信半徑為15 m條件下的不同錨節(jié)點(diǎn)數(shù)對(duì)3種算法定位效果的影響，3種定位算法的誤差隨著錨節(jié)點(diǎn)數(shù)量的增加都有不同程度的減小。HCLSO-3D定位算法在不同條件下定位誤差置信區(qū)間為[45.9%,56.1%],[36%,44%],[28.8%,35.2%],[26.1%,31.9%],[23.94%,29.26%]。當(dāng)錨節(jié)點(diǎn)數(shù)量為15～25時(shí)，HCLSO-3D定位算法平均定位誤差低于3D-DVHop定位算法和文獻(xiàn)[16]定位算法24.5%～27%和2%～6%，表明HCLSO-3D定位算法優(yōu)勢明顯，具有較高的定位精度。因?yàn)镠CLSO-3D定位算法不僅考慮了跳距和計(jì)算方法的影響，同時(shí)還對(duì)跳數(shù)進(jìn)行了優(yōu)化，文獻(xiàn)[16]算法只對(duì)跳距和節(jié)點(diǎn)計(jì)算方法進(jìn)行了優(yōu)化。

Figure 3 Effect of the number of anchor nodes on the average positioning error of the algorithm圖3 錨節(jié)點(diǎn)個(gè)數(shù)對(duì)算法平均定位誤差的影響

4.3 不同通信半徑與平均定位誤差分析

圖4是錨節(jié)點(diǎn)比例為15%情況下，不同通信半徑對(duì)待定位節(jié)點(diǎn)平均定位誤差的影響。HCLSO-3D定位算法在不同條件下定位誤差置信區(qū)間為[45%,55%],[40.5%,49.5%],[34.2%,41.8%],[27%,33%],[22.5%,27.5%]。可以看出，HCLSO-3D定位算法在通信半徑增加時(shí)，定位效果優(yōu)于前2種算法。這是因?yàn)楸疚牟捎枚嗤ㄐ虐霃胶吞嘈拚姆绞剑沟美脙?yōu)化跳數(shù)計(jì)算出的估計(jì)距離更接近實(shí)際距離，獅群優(yōu)化算法求解的目標(biāo)更準(zhǔn)確，而前2種算法并沒有考慮到這些因素對(duì)定位精度的影響。

Figure 4 Effect of communication radius on the average positioning error of the algorithm圖4 通信半徑對(duì)算法平均定位誤差的影響

4.4 節(jié)點(diǎn)總數(shù)與平均定位誤差分析

圖5為節(jié)點(diǎn)總數(shù)的變化對(duì)待定位節(jié)點(diǎn)平均定位誤差的影響。HCLSO-3D定位算法在不同條件下定位誤差置信區(qū)間為[45.9%,56.1%],[40.95%,50.05%],[37.8%,46.2%],[32.4%,39.6%],[26.55%,32.45%],[24.12%,29.48%]。本文提出的算法整體性能相對(duì)穩(wěn)定，定位效果相比3D-DVHop定位算法和文獻(xiàn)[16]定位算法明顯更好。仿真區(qū)域內(nèi)節(jié)點(diǎn)總數(shù)的增加導(dǎo)致網(wǎng)絡(luò)的連通性更好，錨節(jié)點(diǎn)通信范圍內(nèi)覆蓋的待定位節(jié)點(diǎn)增加，使得節(jié)點(diǎn)的定位精度有所提高。

Figure 5 Effect of the number of nodes on the average positioning error of the algorithm圖5 節(jié)點(diǎn)總數(shù)對(duì)算法平均定位誤差的影響

4.5 計(jì)算開銷分析

本節(jié)將算法的平均運(yùn)行時(shí)間作為算法計(jì)算開銷指標(biāo)進(jìn)行分析。表3為相同實(shí)驗(yàn)條件下所統(tǒng)計(jì)的HCLSO-3D定位算法、3D-DVHop算法和文獻(xiàn)[16]算法的平均運(yùn)行時(shí)間。由實(shí)驗(yàn)結(jié)果可以看出，HCLSO-3D定位算法平均運(yùn)行時(shí)間略大于3D-DVHop算法和文獻(xiàn)[16]算法的。因?yàn)镠CLSO-3D定位算法使用多通信半徑和智能算法求解待定位節(jié)點(diǎn)坐標(biāo)，導(dǎo)致運(yùn)算量加大，計(jì)算開銷略有增加，但是定位精度明顯提高。

Table 3 Average running time of the three algorithms表3 3種算法的平均運(yùn)行時(shí)間

5 結(jié)束語

本文使用多通信半徑的方法細(xì)化傳統(tǒng)DV-Hop模型中的跳數(shù)，考慮跳數(shù)以及不同錨節(jié)點(diǎn)對(duì)待定位節(jié)點(diǎn)的影響不同，為減少對(duì)平均跳距和待定位節(jié)點(diǎn)到錨節(jié)點(diǎn)距離計(jì)算帶來的累積誤差，使用相似路徑搜索算法獲取與待定位節(jié)點(diǎn)到相應(yīng)錨節(jié)點(diǎn)之間最相似的錨節(jié)點(diǎn)對(duì)的路徑，修正此路徑平均跳距為待定位節(jié)點(diǎn)到對(duì)應(yīng)錨節(jié)點(diǎn)的平均跳距，減少其他錨節(jié)點(diǎn)的影響，降低平均跳距誤差。由于獅群算法對(duì)初值的要求不高，算法尋優(yōu)速度較快，有較強(qiáng)的全局尋優(yōu)能力，本文使用獅群優(yōu)化算法對(duì)待定位節(jié)點(diǎn)的坐標(biāo)進(jìn)行計(jì)算，得到了最優(yōu)的坐標(biāo)值，從而提高了定位精度。