基于最小跳數(shù)和飛行策略改進(jìn)的三維狼群算法

基于最小跳數(shù)和飛行策略改進(jìn)的三維狼群算法

1基于等式的數(shù)學(xué)模型無(wú)線傳感器網(wǎng)絡(luò)（無(wú)線傳感器網(wǎng)絡(luò)）廣泛應(yīng)用于邊緣計(jì)算?，F(xiàn)有的定位算法依據(jù)需要測(cè)距與否的標(biāo)準(zhǔn)，將定位算法分為兩種。第一種算法為測(cè)距式算法，一般是利用距離信息建立數(shù)學(xué)等式或是利用能量數(shù)據(jù)創(chuàng)建數(shù)學(xué)模型，通過(guò)測(cè)量所得到的數(shù)據(jù)信息的準(zhǔn)確度就是關(guān)鍵信息所在。該算法雖然定位誤差較低，但對(duì)嵌入式設(shè)備有一定的要求。另一種定位算法不需測(cè)距，且節(jié)約成本，耗能低，此外對(duì)所需嵌入式裝備無(wú)過(guò)多要求，其代表為我們所熟知的傳統(tǒng)DV-hop算法。DV-hop算法思想來(lái)源于貝爾曼-福特路由所改進(jìn)的分布式定位方法針對(duì)以上問(wèn)題，因此本文針對(duì)不同節(jié)點(diǎn)之間計(jì)算跳距、跳數(shù)不夠精準(zhǔn)及使用最小二乘法（Leastsqauremethod,LS）或極大似然值估計(jì)算法定位未知節(jié)點(diǎn)的精確度不高，而導(dǎo)致無(wú)法準(zhǔn)確定位，誤差較大的情況，提出一種2理論背景2.1節(jié)點(diǎn)最小跳數(shù)hop傳統(tǒng)DV-hop算法是利用貝爾曼-福特路由所引導(dǎo)出的定位算法，該算法的主要步驟主要分為三步：①信標(biāo)節(jié)點(diǎn)（錨節(jié)點(diǎn)）通過(guò)傳統(tǒng)的貝爾曼-福特路由交換協(xié)議向節(jié)點(diǎn)播送自己的信息數(shù)據(jù)，以此獲得所有節(jié)點(diǎn)到每一個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)hop②每個(gè)信標(biāo)節(jié)點(diǎn)利用其它錨節(jié)點(diǎn)的位置數(shù)據(jù)以及相隔的最小跳數(shù)hop式（1）中，③根據(jù)以上兩步所獲得的最小跳數(shù)hop設(shè)其中，hop根據(jù)信標(biāo)節(jié)點(diǎn)的實(shí)際位置以及預(yù)估到未知節(jié)點(diǎn)的距離，可形成如下方程組：將方程組中的每一個(gè)方程等號(hào)兩邊開(kāi)根號(hào)，所形成的新方程組轉(zhuǎn)換成矩陣通過(guò)LS獲得該矩陣方程，可以確定未知節(jié)點(diǎn)K的預(yù)估位置：從以上算法的運(yùn)行過(guò)程來(lái)看，計(jì)算的誤差主要來(lái)自于最小跳數(shù)和平均跳距計(jì)算精度以及多個(gè)位置節(jié)點(diǎn)目標(biāo)定位的優(yōu)化。本文主要使用跳數(shù)加權(quán)對(duì)平均跳距進(jìn)行改進(jìn)以及使用飛行策略改進(jìn)的三維狼群算法在多目標(biāo)定位階段增加定位精度。3之前的字典算法得到了改進(jìn)3.1跳躍數(shù)加權(quán)改善由式中，3.2基于gwo優(yōu)化的目標(biāo)定位算法基本的灰狼算法（GWO）是由澳籍研究者灰狼隸屬于犬科群居動(dòng)物，處于食物鏈頂層的他們嚴(yán)格遵守著社會(huì)等級(jí)支配關(guān)系，如圖1所示;社會(huì)等級(jí)最高的灰狼稱為α，α灰狼具有最高統(tǒng)治地位，對(duì)其他的狼具有絕對(duì)的支配能力，社會(huì)等級(jí)第二與第三的灰狼稱為β狼和δ狼，社會(huì)等級(jí)最底層的狼稱為ω狼，ω狼需要服從其他層次的狼，ω狼的作用是為了防止狼群內(nèi)部的自相殘殺。GWO的具體步驟如下：①社會(huì)階級(jí)分層（SocialHierarchy）：在設(shè)計(jì)灰狼算法時(shí)，首先根據(jù)適應(yīng)度函數(shù)，將適應(yīng)度最好的三只狼分別標(biāo)記為α狼、β狼和δ狼，剩下的灰狼則稱為ω狼。GWO優(yōu)化就是由迭代更新過(guò)程中最好的三個(gè)解α、β和δ來(lái)完成。②圍困獵物（Encirclingprey）:灰狼群在搜尋獵物時(shí)，會(huì)逐漸形成一個(gè)包圍圈圍困獵物目標(biāo)，該行徑數(shù)學(xué)模型如下：式（8）中：③狩獵（Venery）：灰狼擁有分辨潛在目標(biāo)定位的天賦，搜索過(guò)程中主要由α、β和δ三匹高階灰狼來(lái)引領(lǐng)完成，但由于解空間特征的未知性，狼群確定不了最優(yōu)目標(biāo)的完美定位，所以為更好地模擬灰狼的捕獵行為，假定α、β和δ具有很好的區(qū)分目標(biāo)定位天賦，所以在每次迭代時(shí)保留灰狼群中的等級(jí)高層狼α、β和δ，再根據(jù)他們的位置數(shù)據(jù)來(lái)更新其他ω狼的位置，該行為的數(shù)學(xué)模型如下：式中由圖2可見(jiàn)，④攻擊目標(biāo)（Attackingtarget）：創(chuàng)建模型時(shí)，根據(jù)步驟②可知，a數(shù)值的降低也會(huì)改變A的值，A是[-a,a]區(qū)間的隨機(jī)向量。當(dāng)A在區(qū)間[-1,1]上時(shí)，則此時(shí)灰狼與目標(biāo)之間的位置就是代理搜索的下一刻位置。⑤尋找獵物（Lookforprey）：主要依靠GWO算法是一種模仿灰狼群體捕獵啟發(fā)的一種新型仿生群體智能算法，具有收斂性能較高，且易于實(shí)現(xiàn)等特點(diǎn)，可用于WSN節(jié)點(diǎn)定位，降低算法誤差，但與眾多仿生算法一樣，有著過(guò)早收斂，全局搜索能力較弱等問(wèn)題，以至于所得到的最終解精度不高。3.3灰狼算法的改進(jìn)根據(jù)在式（11）中3.4改進(jìn)的灰狼算法修正未知節(jié)點(diǎn)位置在經(jīng)典DV-hop第三階段，使用極大似然值估計(jì)算法確定待求節(jié)點(diǎn)方位，由于該方法的局限性不能有效提高計(jì)算精度，因此使用三維狼群算法對(duì)最后未知節(jié)點(diǎn)的位置進(jìn)行改進(jìn)，改進(jìn)如下：1）首先初始化2）根據(jù)式（10）適應(yīng)度函數(shù)得到所有灰狼的初步適應(yīng)度值3）灰狼群根據(jù)之前提到的式（8）和式（9）進(jìn)行更新狼群位置信息X，如果α狼已達(dá)到最大迭代次數(shù)或者滿足迭代循環(huán)結(jié)束條件，則停止循環(huán)，輸出的α狼坐標(biāo)信息即為未知節(jié)點(diǎn)最終改進(jìn)位置。4算法的模擬分析4.1matlab2004仿真實(shí)驗(yàn)為驗(yàn)證改進(jìn)后的DV-hop算法與之前傳統(tǒng)的DV-hop算法相比定位更精確，分別將4種算法在Matlab2016a軟件上進(jìn)行仿真實(shí)驗(yàn)在邊長(zhǎng)為100的正方體三維立體空間中，任意投放400個(gè)WSN節(jié)點(diǎn)，如圖3所示。以全部未知節(jié)點(diǎn)的平均定位精確度數(shù)據(jù)作為實(shí)驗(yàn)對(duì)照?qǐng)D的縱坐標(biāo)，以對(duì)比不同算法的精度，未知節(jié)點(diǎn)的平均定位精確度數(shù)據(jù)Ave_er計(jì)算公式（13）如下：式（13）中，4.2實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)定實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)定：在Matlab2016a軟件由圖4可知，當(dāng)錨節(jié)點(diǎn)個(gè)數(shù)為120時(shí)，本文改進(jìn)的算法與原始DV-hop算法、三維加權(quán)DV-hop算法以及未使用飛行策略的灰狼算法相比，Ave_er分別降低了0.6342、0.2004、0.0222；當(dāng)錨節(jié)點(diǎn)個(gè)數(shù)為180時(shí)，本文改進(jìn)的算法與經(jīng)典DV-hop算法、三維加權(quán)DV-hop算法以及未使用飛行策略的灰狼算法相比，Ave_er分別降低了0.6562、0.1741、0.0286；當(dāng)錨節(jié)點(diǎn)個(gè)數(shù)為240時(shí)，本文改進(jìn)的算法與經(jīng)典DV-hop算法、三維加權(quán)DV-hop算法以及未使用飛行策略的灰狼算法相比，Ave_er分別降低了0.6675、0.1669、0.0176。由此將實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)定：在Matlab2016a軟件上進(jìn)行實(shí)驗(yàn)，將錨節(jié)點(diǎn)數(shù)設(shè)為160，節(jié)點(diǎn)總數(shù)設(shè)為400，在不同通訊半徑條件下，設(shè)定灰狼算法迭代次數(shù)為350次，狼群數(shù)量為100，Levy飛行策略中的由圖5可知，當(dāng)通訊半徑r為40時(shí)，本文改進(jìn)的算法與原始DV-hop算法、三維加權(quán)DV-hop算法以及未使用飛行策略的灰狼算法相比，Ave_er分別降低了0.7187、0.1502、0.0756；當(dāng)r為55時(shí)，本文算法與原始DV-hop算法、三維加權(quán)DV-hop算法以及未使用飛行策略的灰狼算法相比，Ave_er分別降低了0.6588、0.2016、0.0488；當(dāng)r為70時(shí)，本文改進(jìn)的算法與原始DV-hop算法、三維加權(quán)DV-hop算法以及未使用飛行策略的灰狼算法相比，Ave_er分別降低了0.4030、0.1388、0.0309。由此將實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)定：在Matlab2016a軟件上進(jìn)行實(shí)驗(yàn)，將錨節(jié)點(diǎn)數(shù)設(shè)為總結(jié)點(diǎn)數(shù)的40%，通訊半徑設(shè)為50，在不同的節(jié)點(diǎn)總數(shù)條件下，設(shè)定灰狼算法迭代次數(shù)為350次，狼群數(shù)量為100，Levy飛行策略中的由圖6可知，當(dāng)節(jié)點(diǎn)總數(shù)設(shè)為100時(shí)，本文改進(jìn)的算法與經(jīng)典DV-hop算法、三維加權(quán)DV-hop算法以及未使用飛行策略的灰狼算法相比，Ave_er分別降低了0.5684、0.1402、0.0533；當(dāng)節(jié)點(diǎn)總數(shù)設(shè)為250時(shí)，本文改進(jìn)的算法與原始DV-hop算法、三維加權(quán)DV-hop算法以及未使用飛行策略的灰狼算法相比，Ave_er分別降低了0.6580、0.1881、0.0478；當(dāng)通訊半徑為400時(shí)，本文改進(jìn)的算法與原始DV-hop算法、三維加權(quán)DV-hop算法以及未使用飛行策略的灰狼算法相比，Ave_er分別降低了0.6973、0.1974、0.0203。由實(shí)驗(yàn)結(jié)果表明，4種算法對(duì)平均定位精確度數(shù)據(jù)Ave_er在不同的錨節(jié)點(diǎn)數(shù)，節(jié)點(diǎn)總數(shù)以及通訊半徑的不同數(shù)據(jù)條件下，本文算法的精確度明顯優(yōu)于原始DV-hop算法、三維加權(quán)DV-hop算法以及未