基于擴散模型和粒子群優化的無線網節點定位

曹昕鷙，韓 玨

(1．浙江機電職業技術學院 智慧交通學院，浙江 杭州 310053；2．浙江理工大學 機械與自動控制學院，浙江 杭州 310018)

0 引言

無線傳感網絡由眾多節點通過自組織方式構成，這些節點靈活性強，隨機分布于某一區域，依據參數對控制對象信息進行采集，幫助管理者及時獲取所需信息[1-2]。無線傳感器網絡通常處于開放式環境中，各節點之間動態且獨立分布，無中心節點監控，因此節點定位非常重要，是無線傳感網絡運行的基礎。準確、快速的節點定位能夠使無線傳感網絡更加高效完成對象控制等處理，節點定位也成為該領域相關研究的重要內容之一[3-4]。

眾多學者對于無線傳感網絡節點定位方法進行了相關研究，并取得一定成果。文獻[5]通過使用移動接收節點來優化傳感器節點的能量，設計了基于質心的路由協議，該協議中傳感器節點形成了各自的集群，每個集群分配一個集群頭節點，用于收集數據，該方法通過路由協議的設計，更好地發揮了傳感節點的數據采集能力，但存在精度不高的問題。文獻[6]在保證數據傳輸成功率高的同時，通過優化具有不同能量采集率節點的網絡，提高網絡連通性效率，該方法根據能量收集能力計算每個節點的權重，然后利用其計算邊緣權重，創建一個最小生成樹完成節點部署，提高節點利用效果，但測距誤差較大。文獻[7]對無線傳感網絡中誤差估計條件下的無距離定位技術進行研究，建立一個定位框架，定義不確定性參數，提出了一種計數定位和計數錨的2階段估計算法，計算局部傳感器節點的數量以及位置，實現定位分析，但容易出現局部最優的問題。文獻[8]主要分析移動無線傳感網絡中的匯聚節點，提出了移動感知占空比循環和動態前置混合算法，在移動接收節點上的移動節點和靜態節點之間建立通信閾值，解決傳感網移動感知問題，該方法對移動節點做出了詳細的分析，然而復雜度高導致耗時長。文獻[9]使用改進鯨魚算法進行無線傳感器網絡定位優化分析，建立節點定位目標函數并求取最優值，定位效果較好，然而召回率相對較低。

在現有研究成果的基礎上，本文提出一種基于擴散模型和粒子群優化的無線網節點定位方法，期望獲取優化無線傳感網絡節點定位方法，提高定位效果，為無線傳感相關領域研究提供理論支持。實驗測試證明，所提方法能夠有效提升無線網節點定位效果，在不同密度、節點數量和占參考節點比例條件下，定位誤差和方差均低于其他方法，精度高達95%左右，召回率始終在95%以上，平均耗時僅13.8 s，性能優越。本研究主要貢獻如下：

① 通過模擬信息擴散過程獲取了無線網關鍵節點，并提取節點特征，為節點定位奠定了基礎。

② 對節點定位過程進行了詳細操作，首先初步定位，然后側重考慮節點測距誤差問題，采用改進粒子群算法修正誤差，提高了定位結果的準確度。

③ 采用多組實驗進行了仿真測試，驗證了本文所提方法的有效性。

1 基于擴散模型的無線網關鍵節點特征提取

無線網關鍵節點特征提取框架如圖1所示。

圖1 無線網關鍵節點特征提取框架Fig.1 Feature extraction framework for key nodes of wireless network

對無線傳感網絡中的全部節點進行歸一化處理，共計包含N個網絡節點，具體計算如下：

(1)

式中，DCi為某一節點鄰近節點的數量；Γ(i)代表節點i的全部鄰近節點集合；j為第j個節點。

1.1 信息擴散模型建立

根據上述無線網關鍵節點特征提取框架可知，需要首先提取無線網絡中的關鍵節點，將節點設定為信息擴散的種子節點，同時借助SEIR(Susceptible Exposed Infectious Recovered)模型對無線網節點信息擴散情況進行模擬分析，建立信息擴散模型[10]。SEIR模型網絡結構如圖2所示。圖中，綠色、紫色、紅色、藍色分別代表SEIR模型中的易感態、潛伏態、 感染態、恢復態4種狀態，可對應看作無線網中的不同狀態節點，不同節點之間建立鏈接。

圖2 SEIR模型網絡結構Fig.2 Network structure of the SEIR model

對鏈接的評價是進行擴散模擬的重要依據，優先需要獲取鏈接的重要排序，同時識別關鍵鏈接，最終獲取無線網的關鍵節點。SEIR模型的設定條件為：

① 無線網絡中全部節點都可以被激活。

② 無線網絡中單一節點被激活之后將一直處于激活狀態。

在SEIR模型中，假設待激活節點周圍有一個或者多個激活節點，則待激活節點將會以一定的概率被激活。設定與節點i相連的2個節點分別為j和k，鏈接(i,j)和鏈接(i,k)的權重分別表示為wij和wik，則節點i在2條鏈接上被激活的概率pij和pik為：

(2)

式中，p為節點信息的初始擴散概率。

(3)

式中，t為模擬實驗次數；T為模擬次數最大值；δt為第t次模擬的權重。通過式(3)，在無線網絡節點情況下進行計算，能夠獲取由鏈接擴散而導致的激活節點數量，進而得到對應鏈接在網絡中的重要程度，獲取對應評估的關鍵指標。通過關鍵指標，能夠得到鏈接的重要排序，獲取關鍵節點，為后續無線網絡中關鍵節點的特征提取提供重要的理論依據。

1.2 關鍵節點特征提取

根據上面獲取的評估指標，可以對關鍵鏈接進行排序獲取所需節點，進而提取無線網絡中關鍵節點的特征信息。以下主要通過最小生成樹方法[11]進行特征提取，詳細的操作步驟如下：

① 優先組建一個無向加權網絡G：

G={V,E,W}，

(4)

式中，V為無線網絡下的節點集；E為邊集；W為權值的集合。

② 對G進行初始化處理。

③ 重復上述操作步驟，直至集合中的值全部完成遍歷。

④ 將G中全部邊的權值按照從小到大的順序進行排列，假設生成樹無法形成圈，則將其加入到對應的集合中；反之，則直接將其刪除。

⑤ 通過點集V和邊集Esub構建無向加權網絡G的一個最小生成樹。

⑥ 輸入關鍵節點信息，利用最小生成樹提取關鍵節點特征，此處主要提取無線節點的通信時間和速度特征，以便后續無線網節點定位分析中對于節點位置的計算和修正。

2 基于粒子群優化的無線網節點定位

2.1 無線網節點初步定位

以上述獲取的無線網關鍵節點為對象，采用最大似然估計方法[12],對無線網節點進行初步定位，對關鍵節點的估計值進行計算，以最大估計值為依據，初步完成無線網節點定位。

(5)

式中，P(Gns)為在真實源節點s下獲取的Gn概率。

在無線網節點定位的過程中，需要借助最優最大似然估計結果檢測單一信息源[13]。網絡隨機節點的向心性可表示為：

(6)

Gn對應的極大似然估計可以表示為：

(7)

在無線網絡下，當網絡結構為一般圖時，無法直接使用式(7)進行計算，但是從直觀角度，能夠借助廣度優先搜索方法構建一個擴散樹，在上述情況下，能夠獲取如下的最優似然估計：

(8)

式中，Tbfs(s)為以s為根節點的廣度優先擴散樹。

通過計算得到的最優似然估計進行無線網節點初步定位，設定真實源節點s被干擾的時間為t*，首先設定一個參考節點ot，則觀察點接收到鄰近節點的時間可以表示為：

(9)

式中，θi為觀察點集合。

在無線網信息傳遞過程中，信息源s是否對其他鄰近節點進行干擾是未知的[14]。因此，在計算過程中，通過該節點獲取無線網通信信息的傳遞時間和速度，相應的傳遞延遲dk表示為：

(10)

針對全部延遲向量，可以通過下式表示：

(11)

式中，[Cs]k,l代表一個規格為k×l的矩陣。

(12)

采用上述步驟計算無線網絡中全部關鍵節點的估計值，選取其中的最大估計值進行無線網節點定位描述，實現節點的初步定位。

2.2 采用粒子群優化算法修正節點測距

為進一步提高無線網節點定位效果，在初步定位實現的基礎上，采用粒子群優化算法修正節點之間的測距，進而實現節點的精準定位。

經典的粒子群算法容易出現局部最優的問題，為此，本文對粒子的位置進行變換處理，避免局部最優問題出現[15-16]。建立混沌系統，公式如下：

zi+1=ξzi(1-zi)，

(13)

式中，zi為粒子位置；ξ為混沌系數。根據混沌系統能夠得到粒子的新位置zi+1，對新位置zi+1進行混沌擾動處理，得到z′i+1，對比z′i+1與zi+1，選取較優的數值替換另一數值作為新位置，反復迭代得到最優解。

從信息擴散模型可知，存在潛伏態的節點，在上述優化完成的粒子群算法基礎上，引入距離誤差修正系數τ，對無線網潛伏節點移動形成的潛在區域進行約束，提高距離計算的準確度[17-18]。距離誤差修正系數τ的計算如下：

(14)

式中，ei為距離誤差；d為節點之間的距離。

無線網節點移動的潛在區域約束條件為：

(15)

式中，(ai,bi)，(a′i,b′i)分別為錨節點和潛在區域節點的位置坐標。

在上述約束條件下，構建無線網節點精準定位的目標函數，如下：

f(ai,bi,η)=f(ai,bi)+

(16)

式中，η為誤差懲罰因子。

綜合上述分析，給出基于擴散模型和粒子群優化的無線網節點定位實現流程如圖3所示。

圖3 無線網節點定位實現流程Fig.3 Flow chart of wireless network node positioning implementation

3 仿真實驗

為了驗證所提基于擴散模型和粒子群優化的無線網節點定位方法的綜合有效性，進行仿真實驗模擬算法定位過程。實驗模擬系統在Windows 10操作系統下開發，CPU為Intel Core i7，內存為6 GB，利用VC++6.0進行編程實現無線網節點定位。

3.1 實驗數據及細節

實驗選取6個無線傳感器網絡作為測試對象，分別從每個無線網中采集1 000個數據，平均劃分為樣本數據和測試數據2類，可以獲取3 000個樣本數據和3 000個測試數據。

6個無線傳感器網絡測試場景及無線網節點分布各異，詳細參數如表1所示。

表1 實驗參數設置Tab.1 Experimental parameter settings

將1 000個傳感節點按照5∶5的比例均勻地劃分為參考節點和待定位節點，即參考節點500個、待定位節點500個。

由于每個無線傳感器網絡測試場景不同，采集得到的數據形態等各不相同，為便于后續數據處理，對采集得到的數據集進行預處理。首先，將實驗數據集統一轉換為同樣的格式；然后，對數據集的每個特征進行合并，并處理形成數據串，使用標簽分別標記好不同數據串，從而更好地實現節點定位分析，減少算法運行復雜度。

3.2 實驗指標

(1) 節點定位效果：在不同網絡密度、節點數量和占參考節點比例條件下，計算不同方法的誤差和方差，驗證本文方法節點定位效果。

(2) 定位精度：為了驗證所提方法的優越性，將無線網節點定位的精度作為測試指標，定位精度越高，說明定位結果越好。精度計算如下：

(17)

式中，Psim為利用算法計算得到的節點位置；Prea為節點的實際位置。

(3)定位召回率：召回率又指查全率，是衡量計算結果全面性的指標，適用于無線網節點定位結果驗證，計算如下：

(18)

式中，P′為利用算法計算得到的節點位置與實際位置一致的節點數量；Ptot為所有定位的節點數量。

(4) 定位時間：對比本文方法與文獻[5-9]方法的實際定位運行時間。

3.3 實驗結果分析

3.3.1 節點定位效果

將6個無線傳感器網絡均劃分為二分網絡，設定每個傳感結構下的節點密度分別為網絡密度分別為1，0.5，0.4，0.3，0.2，0.1。為驗證本文方法的節點定位性能，在不同密度、節點數量和占參考節點比例條件下，計算不同方法的誤差和方差，結果如表2和表3所示。

表2 不同密度下節點定位誤差和方差對比Tab.2 Comparison of node positioning error and variance at different densities

表3 不同節點數量和占參考節點比例下節點 定位誤差和方差對比Tab.3 Comparison of node positioning error and variance under different numbers of nodes and different proportions of reference nodes

由表2和表3可以看出，本文方法的平均定位誤差僅為0.125和0.122，平均定位方差僅為2.45和2.20。在不同網絡密度、節點數量和占參考節點比例條件下，本文方法的定位誤差均小于其他幾種文獻方法，且定位計算結果的方差相對其他文獻方法明顯較低，表明本文方法對于節點定位的準確率較高，且運行更為穩定。這是因為本文方法對測距誤差進行了修正，為定位準確率的提高奠定了基礎。同時，采用信息擴散模型模擬節點移動過程，獲取了更為全面的節點信息，提高了分析過程的穩定性。

3.3.2 定位精度

不同方法的定位精度測試結果如圖4所示。

圖4 不同方法的定位精度測試結果Fig.4 Positioning accuracy test results for different methods

由圖4可以看出，隨著實驗測試次數的持續增加，各方法的定位精度開始發生明顯的變化。相比另外5種方法，本文所提方法的定位精度明顯更高，達到95%左右，而其他方法的最高精度均未達到90%，充分證明所提方法能夠獲取精度較高的定位結果。這是因為本文方法先對無線網的關鍵節點進行識別，并提取關鍵節點的特征，為定位精度的提高奠定了基礎。

3.3.3 定位召回率

不同方法的召回率測試結果如圖5所示。

圖5 不同方法的召回率測試結果Fig.5 Recall rate test results for different methods

由圖5可以看出，相比另外5種定位方法，所提方法的召回率明顯更高一些。其中，本文方法的召回率在多次迭代中均在95%以上，文獻[5]方法的召回率在85%～90%，文獻[6]的召回率在85%左右，文獻[7]的召回率波動較大，但最高也不超過90%，文獻[8-9]的最高召回率在92%左右，仍低于本文方法且測試結果不穩定。由此可見，所提方法具有更好的定位性能。原因是本文對無線網的信息擴散過程進行了模擬，充分獲取了每個節點的變化情況，使得分析結果更為全面。

3.3.4 定位時間

為進一步驗證本文方法的性能，分析不同傳感器網絡測試下，各定位方法的定位時間變化情況，如表4所示。

表4 定位時間對比結果Tab.4 Comparison of positioning time 單位：s

由表4可以看出，本文方法的無線網節點定位平均時間僅為13.8 s，而文獻[5-9]的定位耗時均在20 s以上，遠遠高于本文方法，尤其是文獻[7]方法的定位耗時高達25.3 s。這是由于本文方法運行初期對無線網絡關鍵節點特征進行提取，以特征提取結果為依據能夠更好地完成定位，降低了運行復雜度，有效優化了操作流程，進而減少定位時間，提高運行效率。

4 結束語

為有效提高無線網節點定位效果，本文提出一種基于擴散模型和粒子群優化的無線網節點定位方法，通過構建信息擴散源模型識別并提取關鍵節點的特征，以特征信息為基礎進行節點定位分析，且引入了改進粒子群算法修正節點測距誤差，優化定位效果。實驗測試證明，所提方法定位效果較好，具有較高的定位精度和召回率，且定位時間較短。

然而，本研究仍存在許多不足，在下一步的工作中，將針對無線網節點類型以及狀態進行詳細分析，為節點定位及無線網節點的深入分析提供更具價值的參考數據。