基于約束粒子群算法的網絡節點定位技術研究

謝宏飛

（湛江科技學院，廣東 湛江 524000）

現代網路通訊技術不斷發展，網絡通訊技術在數據監測、環境保護工程甚至國防領域都在使用該技術。網絡節點的研究引起眾多國內外學者的注意，網絡通訊技術是信息技術發展的重大變革，在網絡通訊技術中信息傳輸要包含信息傳遞的位置，對數據的感知才具有實際意義，因此網絡節點定位技術是網絡通訊技術的關鍵性技術[1]。

網絡節點定位技術的基本功能就是定位采集數據在坐標系中的位置，這種技術在醫療領域中用來定位病人病變部位，在災害監測上的應用結果就是可以定位到災害發生的具體位置。因此，網絡節點定位技術的定位精度越高，在諸多領域中發揮的作用就越大[2]。

1 節點定位初始位置獲取

在網絡通訊傳播中，節點的位置需要依靠三個鄰近節點的錨節點進行位置的確定。錨節點的跳數信息被節點接收一次之后就不會接收第二次。因此，通過這種方式獲取節點的初始定位的方法還是很靠譜的。初始位置不確定的節點在錨節點附近，測試與錨節點只會按實際距離，負責測量的錨節點數量大于3個，基本就可以確定節點的大概位置[3]。

首先設定三個節點的坐標：錨節點1坐標為(X1,Y1)，錨節點2坐標為(X2,Y2)，錨節點3坐標為(X3,Y3)。需要定位的節點T的坐標為(XT,YT)，可以得到公式：

上述公式中字母d代表三個錨節點坐標到節點的距離，取節T上方的兩個錨節點，錨節點1和錨節點2，以兩個錨節點的坐標點為圓心，節點通信的距離r為半徑畫兩個圓，基于通信的距離r必然大于錨節點的原理，兩個圓會有交叉的部分，在兩圓交接的地方進行采樣，采樣的坐標為初始位置的坐標，兩圓心距離為2r，采樣的門限設置為n[4]。節點與錨節點之間的距離為：

上述公式中，U1和U2是兩個圓的圓心，D為圓心與位置加點之間的距離，V是規定的最大誤差。剩余的錨節點的坐標為(X3,Y3)，延續上述方法，以此坐標為圓心，通信距離的2倍為半徑畫圓，與節點圓的相交的陰影部分進行位置節點的采樣，最終確定節點定位初始位置[5]。

2 約束粒子群初始化

約束主導粒子的目標函數中的函數結果分為可行結果和不可行結果。基于兩個函數結果定義約束粒子群的算法原理，函數的結果有三種情況，第一種情況為兩個結果都是不可行結果，但是其中一個結果的值小于另一個結果，兩個結果都是可行結果，但是結果1的適應性比結果2更好。最后一種情況為兩個結果剛好一個可行一個不可行，只取可行結果就好。函數的第一個結果定義為a1，第二個結果定義為a2。則a1結果的特征可以主導a2，函數兩個解之間可行程度和不可信程度的對比，需要用到以下模型：

公式（3）中，g(a1)為關于算法函數結果a1的不等式約束公式，h(a1)為關于算法函數結果a1的等式約束公式。J為不等式的約束數量，n為等式的約束數量。函數結果a2的判斷方式同上，為了利用約束粒子群算法進行節點定位創造可行域空間，使用定位突跳的定位機制，定位機制采用模擬概率理論最為理論支撐。在可行域值空間中隨機選取的數值放到不可行域中都不會被接受，說明兩部分域的范圍劃分正確。

只有可行域和不可行域的范圍劃分是正確的，約束粒子群的規模才不會發生變化，在粒子群中，飛行粒子的飛行速度較高。文獻中提到的算法的飛行粒子的運動速度都很低，在搜索最優解的時候進程會很慢，約束粒子群函數的可行解會隨機產生可帶入算法的變量，編碼形式采用傳統的二進制編碼，需要定位的時段有100個節點，最后一個節點的坐標可以設為（x100，y100）其他節點的坐標以此類推，基于第一步節點定位初始位置的坐標計算出約束粒子群算法函數的最優解，完成約束粒子群初始化。

3 基于算法交叉率獲取節點定位最優解

基于算法函數結果的可行解適應度，進行算子的選取，集中變量在適應度值單位內的算法環境中進行變量淘汰，剩余的優質變量繼續參與定位工作。選取群體中的兩個優質變量進行約束粒子交換，交叉概率為P，優質變量結合后交叉概率越大，說明約束粒子群的定位精準度越高，優質變量結合后交叉概率越小，說明約束粒子群的定位精準度越低。需要進行實驗驗證變量的交換概率，當P的概率大于百分之五十，粒子重組，優質變量A的編碼為：0001110101111000，優質變量B的編碼為：0101110101111011新個體的編碼A1為：1000010101111011，新個體的編碼B1為：1000010101111000。A1、B1與A、B的契合度也高于百分之五十。基于上述條件，在傳感器中隨機產生N個節點，M個錨節點。基于上述交叉率進行采樣組成粒子組群，約束粒子群已經做到了組群初始化，在初始化環境中可以直接計算采樣點中的粒子的適度性，并記錄適度性最好的錨節點坐標，粒子的適應度值高的在產生個體時被選中的概率也隨之變高。記錄每個約束粒子的最佳適度性數據，目標值小于最佳適度性數據將會進入最優解計算迭代，直到計算出最優解，才可以確定節點的最終定位。

4 模擬實驗

為了驗證本文基于約束粒子群算法改進的網絡節點定位技術與傳統方式比較是否都具有優勢。進行模擬測試實驗，對比該技術與傳統技術相比，噪聲的標準方差的對比，在定位測試中噪聲的標準方差越大說明在定位中受到的干擾越多，定位的精度就越不準確。

4.1 實驗準備

設置模擬測試環境為室內環境，在模擬環境中設置兩個障礙物，命名為障礙物A和障礙物B。兩個障礙物之間的間距不宜過短，大小和重量也要設置成不同規格。信號發射器在室內左上角最邊緣處，信號接收機和信號發射機之間保證信號發射路徑會路過兩個設置好的障礙物。

實驗分別在四種實驗條件下進行，模擬實驗條件信息如下：1號場景為13*10*6，障礙物為0；2號場景為20*12*6.2，障礙物為1；3號場景為25*13*6.5，障礙物為2；4號場景為30*15*7，障礙物為2。

四種場景室內環境的長、寬、高是逐漸增長的。在模擬場景1中，室內環境的長高寬數值設置都較小，室內環境的構造較小。信號發射和信號接收之間未設置障礙物，信號發射距離也較短。模擬場景2中設置1和障礙物，模擬場景3和4中都設置2個障礙物，在每個場景中都需要收集30個隨機數據。測試的距離值設定為間距0.05 m以上，這樣即使在面積最小的模擬場景1中也能保證收集數據的預留位置在80個以上。距離值隨著測試次數增加。隨著數據采集的進行，算法計算原始參數數據，隨著障礙物對信號的干擾，參數開始發生變化。

4.2 實驗結果與分析

基于上述實驗環境對比該技術與傳統方法相比，信號傳播中噪聲的標準方差，結果如下圖所示：

由圖1可以看出，本文設計的方法的定位精度更高，定位結果受到的干擾更小。

圖1 四種模擬場景標準差對比曲線

基于上述實驗環境，對比傳統算法和本文選用的約束粒子群算法所用的時間開銷，實驗結果如表1所示：

表1 定位過程的時間開銷對比/ms

由上表所知，傳統方式所選用的算法的時間開銷隨著節點數量的增多在不斷延長，傳統算法2點位13個節點所用的時間竟然達到了40ms，在實際的通訊過程中，節點數量較多，且本實驗的實驗環境在室內，障礙物只有兩個。與實際狀況相比，環境已經優化了不少。約束粒子群算法的時間開銷穩定在20ms之內，在時間開銷上遠勝于傳統算法。因此基于約束粒子群算法網絡節點定位技術比傳統技術更加節省點位時間。

結束語

本文基于約束粒子群算法改良傳統的網絡節點定位技術，基于約束粒子群算法的路徑損耗和算法精度使改良過后的定位技術更加精準，但本問設計的方法對減弱環境噪聲這一技術難題研究的還不夠透徹，希望日后的研究中可以突破這一技術難關。