基于改進(jìn)獅群優(yōu)化的三維DV-Hop定位算法

鮑美英，申晉祥

（山西大同大學(xué)計(jì)算機(jī)與網(wǎng)絡(luò)工程學(xué)院，山西大同 037009）

廣泛使用的無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks,WSNs）是在一定監(jiān)測區(qū)域內(nèi)通過無線通信技術(shù)把多個(gè)傳感器節(jié)點(diǎn)以自組織的方式形成的感知網(wǎng)絡(luò)[1]。WSNs 采集監(jiān)測信息的關(guān)鍵是節(jié)點(diǎn)位置，感知的信息固然重要，但在實(shí)際應(yīng)用中，更需要獲取信息發(fā)生的位置，若沒有具體位置信息或位置信息不夠準(zhǔn)確，所感知信息的價(jià)值將會(huì)大打折扣。因此，節(jié)點(diǎn)定位就成為了WSNs研究領(lǐng)域的熱點(diǎn)問題。

三維DV-Hop 定位算法因其簡單成本低以及易擴(kuò)展在WSNs 中得到了廣泛應(yīng)用，備受關(guān)注[2]。但是三維DV-Hop 作為無需測距的定位算法存在定位誤差較大、精度不高的問題，因此提出一種基于改進(jìn)獅群優(yōu)化的三維DV-Hop 定位算法，以減小定位誤差、對(duì)定位精度進(jìn)行有效的提高。

1 三維DV-Hop定位算法

三維DV-Hop 定位算法作為一種無需測距的定位算法[3]，基于傳統(tǒng)二維DV-Hop 定位算法的理論基礎(chǔ)上應(yīng)用到三維場景定位中，其定位過程主要分為兩個(gè)步驟：

（1）計(jì)算節(jié)點(diǎn)的平均跳距，依據(jù)跳數(shù)來進(jìn)行距離估計(jì)；

記錄相互通信的所有節(jié)點(diǎn)到錨節(jié)點(diǎn)的最小跳數(shù)，記錄錨節(jié)點(diǎn)坐標(biāo)。未知節(jié)點(diǎn)計(jì)算自身跳距是以最先收到錨節(jié)點(diǎn)的平均跳距為依據(jù)。計(jì)算節(jié)點(diǎn)的平均跳距如式（1）所示。

式中，H表示最小跳數(shù)矩陣，Hij表示錨節(jié)點(diǎn)i和j之間的最小跳數(shù)，（xi，yi，zi）和（xj，yj，zj）表示錨節(jié)點(diǎn)i和j的坐標(biāo)。

根據(jù)式（1）所得節(jié)點(diǎn)的平均跳數(shù)以及最小跳數(shù)，計(jì)算錨節(jié)點(diǎn)到所有未知節(jié)點(diǎn)的距離如式（2）所示。

式中，D表示所得到的距離矩陣，由此可獲得各個(gè)錨節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的估計(jì)距離矩陣。

（2）利用最小二乘法計(jì)算未知節(jié)點(diǎn)的位置。

根據(jù)第一步所得的錨節(jié)點(diǎn)到未知節(jié)點(diǎn)之間的距離矩陣，通過最小二乘法計(jì)算未知節(jié)點(diǎn)的位置。

利用最小二乘法計(jì)算未知節(jié)點(diǎn)位置的三維DVHop 定位算法，定位誤差比較大，而且通過以上定位過程的分析可知，第一步的誤差會(huì)直接傳遞影響到第二步，導(dǎo)致產(chǎn)生更大的誤差，為使三維DV-Hop 定位算法誤差最小化，提高定位精度，需進(jìn)一步優(yōu)化。

2 改進(jìn)的獅群優(yōu)化算法

獅群算法（Lion Swarm Algorithm,LSA）模仿生物界獅子群群體捕獵行為[4]，獅群可分為三種角色：獅王、母獅和幼獅，其分工是獅王作為首領(lǐng)守護(hù)領(lǐng)地，母獅協(xié)作捕獵和幼獅跟隨母獅從旁學(xué)習(xí)或協(xié)助捕獵以及幼獅成年后會(huì)被獅王逐出領(lǐng)地。三種角色在捕獵過程中因分工不同而所處的位置也各不相同，而且獅群中不同角色所占數(shù)量比例對(duì)算法的收斂性能會(huì)產(chǎn)生較大影響。

LSA 搜索速度快、全局尋優(yōu)能力強(qiáng)，但其存在兩個(gè)問題，一是捕獵搜索范圍增大的情況下，母獅和幼獅的位置容易發(fā)生越界，二是算法的位置更新公式適應(yīng)度較差。

針對(duì)問題入手，將狼群算法（Wolf Pack Algorithm,WPA）[5]中狼群捕食游獵行為以及羊群算法（Sheep Behaviors Algorithm,SBA）[6]中羊群受到攻擊時(shí)的聚集互動(dòng)行為融入獅群算法中進(jìn)行改進(jìn)。獅王作為首領(lǐng)處于最優(yōu)位置即距離獵物最近，母獅協(xié)助捕獵會(huì)向獵物移動(dòng)靠近，其位置更新方式如式（3）所示。

式 中，指的是第i只獅子第k代的位置，rand為0到1 之間的一個(gè)隨機(jī)數(shù)，L為獅群以往最佳位置。母獅協(xié)助捕獵過程中的位置變化融入SBA 中羊群受到攻擊時(shí)的聚集互動(dòng)行為進(jìn)行更新，通過母獅個(gè)體之間位置的適應(yīng)度值的比較，更新過程如式（4）所示。

更新后的母獅i和母獅j的位置如式（5）所示。

幼獅跟隨母獅從旁學(xué)習(xí)或協(xié)助捕獵向獵物移動(dòng)靠近，也存在個(gè)別幼獅隨機(jī)游走的情況。幼獅捕獵時(shí)的位置變化融入WPA 中狼群捕食游獵行為進(jìn)行更新，其位置更新方式如式（6）所示。

式中，Max和Min表示獅群捕獵范圍的最大值和最小值，P為幼獅隨機(jī)游走的概率。

改進(jìn)后的獅群算法的性能是否得到優(yōu)化，需要進(jìn)一步實(shí)驗(yàn)驗(yàn)證，將WPA、LSA 和改進(jìn)的獅群優(yōu)化算法（Improved Lion Swarm Optimization Algorithm,ILSOA）進(jìn)行比較，選用單峰函數(shù)中的sphere 函數(shù)測試不同算法的收斂速度，選用多峰函數(shù)中的levy 函數(shù)，其有多個(gè)局部最小值點(diǎn)。不同算法的sphere 函數(shù)各個(gè)指標(biāo)的測試結(jié)果如表1所示。

表1 sphere函數(shù)測試結(jié)果

不同算法的levy 函數(shù)各個(gè)指標(biāo)的測試結(jié)果如表2所示。

表2 levy函數(shù)測試結(jié)果

可以得出，LSA 運(yùn)行時(shí)間最小且速度最快，WPA速度最慢，ILSOA 的各項(xiàng)指標(biāo)測試結(jié)果都是最小的，性能優(yōu)于LSA 和WPA，實(shí)驗(yàn)結(jié)果表明ILSOA 運(yùn)行速度較快、收斂精度高且穩(wěn)定性好，不易陷入局部最優(yōu)。

3 三維DV-Hop定位算法的優(yōu)化

將ILSOA 用于三維DV-Hop 定位算法中進(jìn)行優(yōu)化計(jì)算未知節(jié)點(diǎn)坐標(biāo)，相比采用最小二乘法能夠有效的減小誤差，使平均估計(jì)誤差盡量最小化。算法的適應(yīng)度函數(shù)如式（7）所示。

式中，（x，y，z）表示優(yōu)化的未知節(jié)點(diǎn)的坐標(biāo)，（xi，yi，zi）表示錨節(jié)點(diǎn)i的坐標(biāo)，di是估計(jì)的未知節(jié)點(diǎn)（x，y，z）到錨節(jié)點(diǎn)i的距離。

4 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證所提優(yōu)化定位算法的有效性，在Windows10 系統(tǒng)中利用Matlab2017 對(duì)所提基于ILSOA的三維DV-Hop 定位算法（ILSOA-DV-Hop）、基于LSA 的三維DV-Hop 定位算法（LSA-DV-Hop）和三維DV-Hop 定位算法進(jìn)行仿真實(shí)驗(yàn)。設(shè)定仿真區(qū)域?yàn)?00 m×100 m×100 m 的立體空間中隨機(jī)部署1 000 個(gè)傳感器節(jié)點(diǎn)，選用平均定位誤差作為衡量指標(biāo)對(duì)算法性能進(jìn)行評(píng)價(jià)，平均定位誤差公式如式（8）所示。

式中，（xk，yk，zk）表示未知節(jié)點(diǎn)k的實(shí)際三維坐標(biāo)，表示通過計(jì)算得出的未知節(jié)點(diǎn)k的估計(jì)三維坐標(biāo)，N表示未知節(jié)點(diǎn)數(shù)，R表示通訊半徑。

實(shí)驗(yàn)從錨節(jié)點(diǎn)比例、通訊半徑和節(jié)點(diǎn)總數(shù)三個(gè)方面對(duì)不同算法進(jìn)行分析討論。

4.1 錨節(jié)點(diǎn)比例與平均定位誤差分析

在實(shí)驗(yàn)仿真環(huán)境下，設(shè)定仿真區(qū)域隨機(jī)布置1 000 個(gè)傳感器節(jié)點(diǎn)，錨節(jié)點(diǎn)比例從10%變化到70%，假設(shè)通訊半徑為20 m，不同的錨節(jié)點(diǎn)比例下三維DV-Hop、LSA-DV-Hop 和ILSOA-DV-Hop 三種定位算法的平均定位誤差如圖1 所示。

由實(shí)驗(yàn)結(jié)果圖1可得，隨著錨節(jié)點(diǎn)比例的增大三種定位算法的平均定位誤差整體都是逐漸在減小。其中ILSOA-DV-Hop 效果很明顯優(yōu)于LSA-DV-Hop和三維DV-Hop 定位算法，三維DV-Hop 定位算法的效果最差。LSA-DV-Hop比三維DV-Hop定位算法的平均定位誤差減少了52.6%，而ILSOA-DV-Hop 比LSA-DV-Hop 又減少了12.8%。從不同錨節(jié)點(diǎn)比例可看出，比例小于20%的時(shí)候，平均定位誤差較大，比例大于30%的時(shí)候，整體誤差變化相對(duì)平穩(wěn)。因而當(dāng)通訊半徑為20 m 的時(shí)候，錨節(jié)點(diǎn)比例為30%比較合理。

圖1 錨節(jié)點(diǎn)比例對(duì)平均定位誤差的影響

4.2 通訊半徑與平均定位誤差分析

實(shí)驗(yàn)設(shè)定錨節(jié)點(diǎn)比例為30%，即錨節(jié)點(diǎn)數(shù)為300，通訊半徑從10 m 變化到50 m，不同的通訊半徑下的三維DV-Hop、LSA-DV-Hop 和ILSOA-DV-Hop三種定位算法的平均定位誤差如圖2所示。

圖2 通訊半徑對(duì)平均定位誤差的影響

由實(shí)驗(yàn)結(jié)果圖2可得，隨著通訊半徑的增大三種定位算法的平均定位誤差整體都是逐漸在減小，其中三維DV-Hop 定位算法的效果最差，且在通訊半徑大于20 m 的時(shí)候誤差變化相對(duì)平穩(wěn)。LSA-DV-Hop比ILSOA-DV-Hop 要差一些，ILSOA-DV-Hop 效果最好。相比LSA-DV-Hop 的平均定位誤差降低了15.3%，當(dāng)通訊半徑大于30 m 的時(shí)候，LSA-DV-Hop和ILSOA-DV-Hop 的誤差變化相對(duì)平穩(wěn)。因而當(dāng)錨節(jié)點(diǎn)比例為30%的時(shí)候，通訊半徑為30 m比較合理。

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

實(shí)驗(yàn)設(shè)定錨節(jié)點(diǎn)比例為30%，通訊半徑為20 m，節(jié)點(diǎn)總數(shù)從700 變化到1 300，不同的節(jié)點(diǎn)總數(shù)下的三 維DV-Hop、LSA-DV-Hop 和ILSOA-DV-Hop 三 種定位算法的平均定位誤差如圖3所示。

圖3 節(jié)點(diǎn)總數(shù)對(duì)平均定位誤差的影響

由實(shí)驗(yàn)結(jié)果圖3可得，隨著節(jié)點(diǎn)總數(shù)的增大三種定位算法的平均定位誤差都逐漸在減小，其中三維DV-Hop 定位算法受節(jié)點(diǎn)總數(shù)變化影響較小，減小的不明顯，而LSA-DV-Hop和ILSOA-DV-Hop受節(jié)點(diǎn)總數(shù)影響較大，減小的比較明顯。ILSOA-DV-Hop相比LSA-DV-Hop 和三維DV-Hop 定位算法表現(xiàn)仍然最好，比LSA-DV-Hop 降低了43.5%，比三維DV-Hop 定位算法降低了11.9%。因而隨著節(jié)點(diǎn)總數(shù)的變化，所提算法的性能仍然表現(xiàn)最好。

5 結(jié)論

針對(duì)三維DV-Hop 定位算法中定位誤差較大的問題，提出了基于改進(jìn)獅群優(yōu)化的三維DV-Hop 定位算法，算法首先利用WPA 和SBA 對(duì)LSA 進(jìn)行改進(jìn)得到ILSOA，然后再基于ILSOA優(yōu)化三維DV-Hop定位算法中未知節(jié)點(diǎn)坐標(biāo)的計(jì)算，使平均估計(jì)誤差最小化。通過仿真實(shí)驗(yàn)證明，ILSOA-DV-Hop、LSA-DVHop 和三維DV-Hop 定位算法從不同的錨節(jié)點(diǎn)比例、通訊半徑和節(jié)點(diǎn)總數(shù)三個(gè)方面進(jìn)行比較，所提算法ILSOA-DV-Hop 都具有最優(yōu)的定位精度。在后續(xù)的研究中，可嘗試引入其它群智能算法進(jìn)一步優(yōu)化。