改進型DV－Hop 定位模型及其求解的混合視覺進化神經網絡

鄭 悅， 張著洪，2

（1 貴州大學 大數據與信息工程學院， 貴陽 550025； 2 貴州大學 貴州省系統優化與科學計算特色重點實驗室， 貴陽 550025）

0 引 言

無線傳感器網絡（Wireless sensor network，WSN）是一種分布式自組織網絡，是通過節點間相互協作實現對指定監控對象的數據感知、采集和處理，并將數據傳輸給用戶；因其節點具有體積小、成本低、布設靈活及功耗低等特點［1］，使得傳感器在諸如環境監測、醫療、軍事、智能家居等領域中具有廣闊發展前景［2］。WSN 定位包括測距定位和非測距定位［3］。 前者需通過測量節點間的實際距離或利用方位角進行準確定位，但硬件投入高。 相反，后者依據網絡的連通性進行定位，其成本低、功耗小、抗干擾性能好，且實用性強。 距離矢量跳數（Distance Vector-Hop，DV-Hop）節點定位算法是一種基于GPS 定位的非測距定位方法，也是目前WSN 中應用最為廣泛的算法之一［4］。由于其節點定位精度主要依賴WSN 的連通度完成對未知節點的定位，加之初始節點的分布具有隨機性以及采用最小二乘法或數值迭代法估計未知節點的位置［5-7］，導致節點的定位性能有待提升。 例如，Kaur等學者［5］利用高斯-牛頓法估計未知節點的位置，能夠提高未知節點的定位精度，但計算復雜度高。 張兢等學者［6］基于RSSI 與加權質心定位，將已被定位的未知節點轉化為錨節點，進而對剩余節點定位，得到的算法能有效解決因節點連通度小而出現定位精度低的問題，但定位效果受環境干擾因素的影響較大。Ma 等學者［7］提出一種基于多通信半徑的定位算法，其通過錨節點多次廣播，計算錨節點與未知節點間的最小跳數，但未涉及未知節點間的最小跳數計算問題。 另外，智能優化算法已初步被用于未知節點的定位［8-9］。 例如，褚銀菲等學者［8］利用改進型差分進化算法對未知節點進行定位，相較于DV-Hop 定位算法，能較大地提高定位精度，但性能受參數的影響較大，且種群多樣性易于過早消失。

另一方面，視覺神經網絡作為一種模擬視覺神經元響應特性而建立的前饋神經網絡已得到可觀研究進展，迄今為止則應用于機器人導航、目標跟蹤、碰撞檢測等方面［10-12］。 Fu 等學者［10］利用果蠅與蝗蟲兩種生物的視覺響應特性，提出一種混合神經網絡模型，并已用于機器人的運動跟蹤與導航。 另外，本文研究團隊圍繞視覺運動檢測和最優化問題的求解，從視覺神經網絡模型研究及應用角度已展開一些研究；例如，針對平移、旋轉等運動模式的識別，利用蝗蟲與獼猴等生物中的視覺響應特性提出人工蝗蟲視覺神經網絡［13］；基于視覺信息處理機制與種群進化或梯度下降思想，獲得可調參數少且尋優精度高的視覺進化、學習神經網絡［14-16］，并將其應用于RSSI 定位、復雜高維優化問題的求解，但算法的定位精度及搜索效果的穩定性有待提高。

綜上，基于現有求解DV-Hop 節點定位問題的研究現狀，本文在建立改進型節點跳數、平均跳距計算模型基礎上，基于果蠅視覺、蝗蟲視覺信息處理機制及哈里斯鷹優化的種群更新策略，提出一種混合視覺進化神經網絡（Hybrid visual evolutionary neural network，HVENN），并用于DV-Hop 的節點定位。

1 改進型DV－Hop 模型與求解準備

1．1 DV－Hop 的距離計算

假定WSN 由m個錨節點和n個未知節點構成，錨節點i和未知節點j的位置分別為Ai（xi，yi） 及Oj（xj，yj），1 ≤i≤m， 1 ≤j≤n。 基本DV-Hop 定位方法經由錨節點與未知節點間的最小跳數以及錨節點的平均跳距計算未知節點到錨節點的距離。 具體如下:

首先，WSN 網絡中一個錨節點（例如節點A） 向所有其它錨節點和未知節點均發送一個包含自身位置、跳數和地址的包，跳數初始值為0；然后，距離節點A最近的錨節點（例如節點B） 向剩余的錨節點和未知節點也發送一個同類型的包。 如此繼續，直到所有錨節點均發送自身的包為止。 之后，經由DV-Hop 的節點跳數計算方法［4］，可獲WSN 中錨節點Ai到錨節點Aj的最小跳數hopij及到未知節點Oj的最小跳數Hopij。 其次，節點Ai依據式（1） 得到自身的平均跳距:

進而，經由式（2） 計算Oj到Ai的距離:

1．2 改進型節點定位優化模型

由于未知節點的位置具有不確定性，加之節點的位置分布不均勻，導致DV-Hop 定位算法存在以下缺陷:

（1） 在計算錨節點與未知節點的距離時，通過把節點間的連線當作直線來計算最小跳數值，導致因傳感器節點的分布不均勻，跳數的計算存在誤差。

（2） 錨節點與未知節點間的距離是通過節點間的平均跳距而獲得，進而因平均跳距、跳數的計算誤差，使得未知節點的定位精度受到極大影響。

針對DV-Hop 定位存在的以上缺陷，這里對錨節點到錨節點和錨節點到未知節點的最小跳數（hopij、Hopij） 以及平均跳距計算模型做如下改進:

（1） 改進型最小跳數計算模型。 假設錨節點A的通信半徑為R，以其為圓心，R、3R／4、R／2、R／4 為半徑產生4 個同心圓，如圖1 所示。 錨節點A以R／4為半徑向網絡中泛洪廣播數據，接收到節點A信號的未知節點首先查詢是否接收到過該節點的跳數；若有，則維持之前跳數信息不變；否則，將未知節點與該節點A間的跳數記為1／4 跳。 以此類推，直到節點A以R為半徑向網絡中泛洪廣播數據為止。

圖1 4 種通信半徑下的廣播跳數Fig． 1 Number of broadcast hops at four communication radii

若節點Ai與Oj的實際距離為d，則最小跳數Hopij經由式（3） 確定:

其次，在錨節點Ai與未知節點間引入如下加權因子:

獲得節點Ai到Oj的如下改進型最小跳數計算模型:

（2） 改進型平均跳距計算模型。獲得錨節點Ai與Aj間的最小跳數hopij后，經由式（6） 計算錨節點Ai的平均跳距:

在此，dij為錨節點Ai到Aj的距離。 進而，基于二者的最小跳數hopij和式（6），獲得二者間的距離估計模型:

另一方面，為進一步減小跳數計算誤差，利用錨節點間的實際距離與估計距離誤差修正Ahopi，即:

其中，εi為錨節點i的平均每跳誤差。 最后，由該跳距和跳數求出未知節點Oj到錨節點Ai的距離，即:

結合式（10），n個未知節點的位置估計問題可通過求解如下DV-Hop 模型（DV-Hop model， DVHop-M）加以解決:

其中，x表示n個未知節點的位置坐標構成的決策向量。

1．3 模型求解準備

考慮如下最優化問題:

其中，D為p維歐式空間中有界閉區域；f（x）為連續型函數；稱x*為最優解，若對于D中任意候選解或稱為狀態的x，均有f（x*）≤f（x）。 取M×N個狀態構成抽象的狀態矩陣A， 即A＝（xij）M×N；將狀態x對應的目標函數值f（x） 視為灰度值或光強度，A中各狀態對應的灰度值構成的灰度圖記作f（A）。 第t時刻的狀態矩陣A（t）對應的灰度圖記為f（A（t））。 在此，，相應的灰度圖為f（A（t））。 以f（A（t）） 作為視覺輸入圖像，借助果蠅、蝗蟲視覺系統的信息處理機制，在已有神經網絡［17-18］基礎上，建立混合型視覺神經網絡（Hybrid visual neural network，HVNN）。 隨后，借助此神經網絡輸出的局部行為量λij（t）、全局行為量ρ（t），以及哈里斯鷹優化的種群更新策略，經由式（13） 轉移狀態矩陣A（t）中狀態為

在此，λij（t） 和ρ（t） 作為調節因子引導狀態的轉移。

2 混合視覺進化神經網絡

2．1 混合視覺神經網絡

人工果蠅視覺神經網絡（Artificial fly visual neural network， AFVNN）［17］與蝗蟲視覺神經網絡（Locust visual neural network， LVNN）［18］是分別源于果蠅、蝗蟲視覺信息處理機制的前饋神經網絡。AFVNN 由4 個視覺信息處理層（光感受器（Photoreceptor）、視網膜（Retina）、薄膜（Lamina）、髓質（Medulla））和一個小葉板切向細胞（Lobula plate tangential cell， LPTC）構成；在此，光感受器接收視覺環境中的光亮強度；視網膜將光感受器獲取的光亮強度經平滑處理，提取運動目標；薄膜層經側抑制機制產生刻畫運動目標變化狀態的興奮量；髓質層輸出運動目標的局部方向行為量；LPTC 匯集所獲局部方向行為量，并產生刻畫運動目標變化狀態的全局方向行為量。 LVNN 由光感受器層（Photoreceptor）、 興 奮 層（ Excitation）、 抑 制 層（Inhibition）、興奮抑制合成層（Stimulation）和一個蝗蟲視覺神經元構成。 在此，興奮層和抑制層接收當前及上一時刻的灰度圖；興奮抑制合成層匯聚此2 層輸出的行為量，并經由側抑制獲取運動目標的局部方向行為量；蝗蟲視覺神經元聚合此局部方向行為量，并產生刻畫運功目標變化狀態的全局運動方向行為量。 AFVNN 和LVNN 的視覺神經生理學理論和設計原理可由文獻［17-18］獲知。 由于果蠅與蝗蟲的視覺系統均具有特征提取和運動方向檢測神經元，所以如此2 種神經網絡均能輸出刻畫運動目標逼近、偏離攝像頭的全局運動方向量。

HVNN 由AFVNN 中的Retina、Lamina、Medulla、LPTC 以及LVNN 中的Inhibition、Stimulation 層構成，其拓撲結構如圖2 所示。 各層的設計如下:

圖2 混合視覺神經網絡Fig． 2 Hybrid visual neural network

（1） Retina:由M × N個Retina 節點以矩陣形式排列而成， 節點（i，j） 在t時刻接收A（t）中狀態對應的光強度，并經由式（14）生成光強度偏差量:

若節點（i，j） 處的狀態未被激活，則經由以下擾動策略激活:

其中，ζ是每個分量在0 與1 之間服從均勻分布的隨機向量；max 與min 分別是A（t）中所有狀態對應的灰度值中最大和最小值；Gmax為最大時間步。 記B（t）＝（yij（t））M×N。

于是，節點（i，j） 的光強度偏差量由式（16） 確定:

（2） Lamina:由果蠅的cartridge （cart）和蝗蟲的Inhibition （I）層構成，每個子層的節點數均為M ×N。 cartridge 層經由對Retina 層做擴邊處理后，cart節點（i，j） 將接收Retina 層中對應節點處3×3 鄰域內節點的光強度偏差量，并經由高斯卷積獲輸出行為量，即:

其中，w是下列權重矩陣的元素之和:

這里，wkl是W中位置（k，l） 處的元素。

Inhibition 層對cartridge 層做擴邊處理后，節點（i，j） 接收來自cartridge 層中對應節點的3×3 鄰域內節點的行為量，并經由以下側抑制策略獲得該節點的抑制量［15］:

其中，(i，j) ≠(0，0) ，wI（i，j） 是局部抑制權重，即下列權重矩陣中位置（i，j） 處的元素:

（3） Medulla:此層由m1、m2兩個節點子層構成，且各層的規模均為M × N。m1節點（i，j） 首先接收Inhibition 層中節點（i，j） 的3×3 鄰域內節點的輸出，然后基于單向EMD 運動方向檢測器［19］，獲得輸出行為量:

隨后，m2節點（i，j）經由與之匹配的m1節點處3×3 鄰域內節點的方向量， 以及AFVNN 中［17］Medulla 的設計，獲得該節點在水平、豎直方向的方向量m2h（i，j） 及m2v（i，j）。

（4）Stimulation:由M × N個節點以矩陣形式排列而成，節點（i，j） 接收m2節點（i，j） 在水平、豎直方向的輸出行為量，進而通過改進文獻［12］中激勵層的設計，經由式（20） 獲得該節點在水平和豎直方向的行為量:

其中，

其 中，Ceh（i，j） 和Cev（i，j） 由 文 獻［12］的Stimulation 層設計確定。

（5） LPTC:借助Stimulation 層中節點在水平、豎直方向的方向量，獲得LPTC 的輸出，即:

需要指出的是， HVNN 與AFVNN 及LVNN 在設計上存在較大差異，主要體現在4 個方面，分述如下。

（1）結構設計不同:HVNN 是在AFVNN 基礎上，經由利用LVNN 的Inhibition、Stimulation 層分別取代AFVNN 中側抑制層及m2節點層而獲得。HVNN 的各層均由M ×N個神經節點按矩陣形式排列表示，而AFVNN 中各層的神經節點數隨層數的遞增而逐漸減少；LVNN 不含視覺信息投影層，信息處理層過于單一。

（2）視覺信息處理存在差異:HVNN 利用LVNN的Inhibition 層執行側抑制，而AFVNN 通過分流抑制動力學模型計算興奮與抑制量；也利用LVNN 的Stimulation 層生成神經節點的局部方向行為量。

（3）HVNN 利用擾動策略激活狀態不變的節點，而AFVNN 未含狀態擾動策略。

（4）應用對象不同:AFVNN 和LVNN 用于運動目標檢測，而HVNN 適用于求解最優化問題。

2．2 狀態更新

經由式（16）獲知，狀態矩陣A（t）經由HVNN 中Retina 層作用后變為B（t）。 此狀態矩陣中每個狀態依據HVNN 的Stimulation 層中節點（i，j） 輸出的行為量λij（t） （局部學習率）、LPTC 輸出的行為量ρ（t） （全局學習率），以及哈里斯鷹優化算法［20］中哈里斯鷹的位置更新策略進行狀態更新；在此，將哈里斯鷹（i，j） 的位置視為A（t）中位置（i，j） 處的狀態。B（t）中狀態借助哈里斯鷹的局部與全局捕食策略，經由式（24）進行更新:

其中，E為最大時間步T下獵物的逃逸能量，即:

在此，r1～U(-1，1) 。是經由哈里斯鷹（i，j） 在全局學習率ρ（t） 引導下，經由全局開采策略生成的位置，即

其中，ζ、r2和r3為［0，1］上的隨機數，a及b分別為第1.3 節所述候選解所在區域D中各維度的左、右端點值構成的向量；是隨機生成的狀態；為A（t）中所有狀態的平均（即M × N只哈里斯鷹的平均位置）；為B（t）中最好的狀態。

在式（26）中，ρ（t） 作為全局學習率被引入到第一式中，其主要作用在于調節所有哈里斯鷹的位置轉移幅度，增強全局開采能力；第二式的目的是強化哈里斯鷹位置的普遍歷性，擴大捕食范圍。

其中，r ～U（0，1），進而推得:

其中，I是由0～1 之間隨機生成的p個值構成的列向量；u和v為［0，1］ 上的隨機數；β為常數，設置為1.5；σ是Levy 飛行函數；min（x，y） 表示2 個p維向量x與y的相同位置處分量的最小值構成的向量。

在式（27）中，第一式經由局部學習率λij（t） 被引入到包圍獵物搜索策略而獲得，其目的在于借助λij（t） 引導劣質哈里斯鷹（i，j） 逐漸朝更有利于捕食的方向轉移； 第二式經由搜索獵物策略而獲得，其目的是增強狀態轉移的多樣性；第三式通過引導哈里斯鷹進行位置信息交互，確保種群位置的多樣性。

2．3 HVENN 的算法描述

HVENN 作為一種循環神經網絡，由HVNN 和一個M ×N神經節點矩陣順次連接而成。 HVNN 以第t -1、t時刻的狀態矩陣A（t）及A（t-1）對應的灰度圖的差圖作為輸入， 依次經由Retina、Cartridge、Inhibition、Medulla、Stimulation 及神經元LPTC 做視覺信息處理，獲得的局部學習率和全局學習率在以上狀態轉移策略下，引導狀態轉移。 算法描述如下。

步驟1參數設置:灰度圖的分辨率M × N，最大時間步T。

步驟2置t←1，隨機生成M ×N個候選解，構成初始狀態矩陣A（t）。

步驟3計算f（A（t）），且A（t）中灰度值或目標值最小的狀態，記和xgb。

步驟4執行HVNN，將A（t）轉移為B（t），同時獲得局部學習率λij（t） 和全局學習率ρ（t）。

步驟5A（t）中所有狀態依據式（24） 執行狀態更新，獲得狀態矩陣A（t＋1）。

步驟6計算A（t＋1）對應的灰度圖f（A（t＋1）），并借助A（t＋1）中的狀態，更新xgb。

步驟7置t←t ＋1， 若t≤T，則返回步驟4；否則，結束且輸出xgb。

以上算法利用HVNN 輸出的全局學習率控制狀態的變化幅度，防止因狀態轉移的幅度過大而導致狀態遠離最優解的位置，增強算法的收斂性。 同時，對狀態分量進行隨機擾動，防止算法過早陷入局部搜索，增強算法的全局搜索能力。 另外，局部學習率被用于調節狀態局部轉移的幅度，增強算法的局部搜索能力。

HVENN 的計算復雜度由HVNN 和狀態更新策略確定。 在HVNN 中，Retina 層共執行MN次加減運算；Cartridge 層共運行28MN次；Inhibition 層共執行18MN次加減法；Medulla 層執行27MN次運算；Stimulation 層共執行12MN次乘除法運算、10MN次加減運算、MN次求最大值和取絕對值運算；Lobula層共執行7MN次運算。 狀態更新模塊需要執行15MNp次運算以及MNmp次目標函數評價，在此mp表示優化問題中目標函數的計算次數。 于是，在一個執行周期內，HVENN 的運行次數為MN（mp ＋15p ＋104）。 因此，HVENN 的計算復雜度由M、N、p和mp確定。 又因要求M、N的取值較小，所以算法的效率由優化問題本身而定。

3 數值實驗

在配置為Windows10／CPU 3.7 GHz／RAM 4.0 GB／Matlab R2018a 環境下展開數值實驗。 首先，借助基準函數和參與比較的算法測試HVENN 求解函數優化問題的性能；其次，將HVENN 應用于DV-Hop 節點定位問題，測試其應用效果和所獲錨節點與未知節點之間的距離計算模型設計的合理性。

3．1 HVENN 的性能測試

選取6 種元啟發式隨機搜索算法參與HVENN的比較，即灰狼優化（GWO）［20］、麻雀搜索算法（SSA）［9］、飛蛾撲火優化（MFO）［21］、多元宇宙優化（MVO）［22］、蝴蝶優化算法（BOA）［23］及哈里斯鷹優化（HHO）［24］。 測試事例包括維度均為30 的13 種基準測試函數優化問題f1～f13［22］，其中f1～f7是單峰值函數，f8～f13是含大量局部最優解的多峰值函數。 參與比較算法的種群規模均為100，其它參數設置源于相應文獻。 HVENN 的參數設置為M ＝N＝10。 對于每個測試問題，各算法的終止條件是最大迭代數為500 或獲得的最好解的目標值為0，且均獨立運行30 次。 各算法獲得每個問題的30 個最好目標值的均值、均方差及在顯著性水平為5%下的t檢驗值用于算法的比較分析，見表1； 以f1、f3、f5、f7、f9、f11為例，算法的搜索曲線如圖3 所示。

經由表1 的均值和方差可知，HHO 和HVENN求解f1～f13所獲解的質量明顯優于其它參與比較的算法所獲解質量，且均能穩定地獲得優化問題的最優解或近似解，搜索效果穩定。 相對而言，HVENN 比HHO 獲得的解的精度更高，且獲得最優解的基準測試問題個數更多，尤其是求解較為困難的F8， 其搜索效果較為穩定。 其次，GWO 和BOA求解以上13 個優化問題時，無論是解的質量、還是搜索效果的穩定性，均優于SSA、MFO 和MVO，分析其原因在于二者僅分別不能有效求解2、4 個問題。最后，MFO 不能有效求解13 個測試問題；SSA 和MVO 不能求解9 個測試問題。 結合表1 中t檢驗值可知，HVENN 求解以上問題的性能最好，HHO 次之，而MFO 的性能最差。

表1 各算法求解每個問題時，獨立運行30 次后獲得的統計結果比較Tab． 1 Comparison of the statistical results obtained after 30 independent runs when each algorithm solves each problem

圖3 中，n表示迭代次數，f表示適應度值。 圖3 表明，相較于參與比較的算法，HVENN 的全局搜索能力強且收斂速度最快；HHO 相比于其它參與比較的算法，搜索速度快，但獲得的解的精度有待提高，且易于收斂到近似解；BOA 的進化能力比GWO、SSA、MFO、MVO 的能力強，但收斂速度比GWO 的慢。

圖3 算法的平均搜索曲線比較Fig． 3 Comparison of the average search curves of the algorithms

3．2 DV－Hop 定位

為測試HVENN 求解1.2 節中DV-Hop-M 的性能，選取經典DV-Hop 算 法［4］、MVODV-hop［21］、GWODV-Hop［9］、BOADV-Hop［23］參與節點定位誤差比較。 設置錨節點和未知節點所在矩形的面積為100 m×100 m，且隨機拋撒m個錨節點及n個未知節點，如圖4 所示。 圖4 中，“*”表示紅色信標節點，“?”表示黑色未知節點。 依據以下節點定位的平均誤差指標檢測各算法的性能:

圖4 網絡節點分布：m＝20，n＝80Fig． 4 Network node distribution： m＝20，n＝80

其中，（xi，yi）和分別是未知節點i的估計和實際位置；R是通信半徑；Err是n個未知節點的平均定位誤差。 式（31） 表明，Err越小，則算法的節點定位精度越高；反之，精度越低。 這里，給出研究內容詳述如下。

（1）情形1:錨節點數量。 設置R＝25 m，錨節點數為m＝10＋5k（0 ≤k≤8），未知節點數為n＝100 -m，節點總數為100。

在給定的k值下，各算法求解DV-Hop-M 100次，獲得的100 個Err的均值形成的曲線如圖5（a）所示。 經由圖5（a）獲知，隨著k的增大，錨節點數量逐漸增多，因而未知節點數逐漸減少，定位精度逐漸提高。 HVENN 的Err為28.7%，參與比較的4 種算法的Err分別為66.5%、57.2%、52.2%及45.3%。因此，HVENN 的節點定位偏差最小，而DV-Hop 的節點定位偏差最大。

（2）情形2:節點通信半徑。 矩形區域面積同上；設置m＝30，n＝70，通信半徑R＝15＋5k（單位為m），0≤k≤5。 同上，在給定k值下，各算法獲得的定位精度曲線如圖5（b）所示。 經由圖5（b）獲知，當20≤R≤35 時，隨著通信半徑的加大，未知節點收集到的定位信息越多，網絡連通性越強，定位精度逐漸提高；當R ＞35 時，各算法獲得的節點定位精度逐漸趨于平穩。 主要原因在于，當通信半徑較小時，每個節點的相鄰節點較少，網絡連通性較低，導致平均跳距存在一定誤差，進而定位效果較差。 當通信半徑增大時，節點間的跳距變小，從而定位誤差減小；當通信半徑達到35 m 時，區域內的2個節點間的跳距都在3 跳之內，所以隨著R的增大，定位誤差趨于穩定且較小。 相較于其它基準對比算法，HVENN 的定位精度最高，但DV-Hop 的定位精度最低。

圖5 定位誤差對比Fig． 5 Comparison of positioning errors

4 結束語

為了解決DV-Hop 定位模型存在定位誤差大的問題，在改進節點跳數和平均跳距計算模型基礎上，將未知節點的定位問題描述為非約束確定性優化問題，進而利用果蠅和蝗蟲視覺系統的信息處理機制獲得混合視覺神經網絡，并將其輸出與哈里斯鷹的位置更新策略結合，獲得混合視覺進化神經網絡（HVENN）。 理論分析表明，該神經網絡的計算復雜度由其分辨率和優化問題的維度確定。 實驗結果表明，將視覺神經網絡與元啟發方法結合，探討求解優化問題的視覺進化神經網絡，是一條切實可行的新路徑；相比于其它基準對比算法，HVENN 在求解精度和收斂速度方面均有明顯優勢，且能較好地解決WSN 的節點定位問題，HHO 次之，而其它基準對比算法的性能較差。 另外，本文僅涉及到靜態環境下的節點定位問題及其求解，至于如何探討不確定環境下的節點定位以及HVENN 是否具有適應環境的能力，仍需做后續進一步的研究探討。