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

謝宏飛

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

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

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

1 節(jié)點定位初始位置獲取

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

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

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

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

2 約束粒子群初始化

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

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

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

3 基于算法交叉率獲取節(jié)點定位最優(yōu)解

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

4 模擬實驗

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

4.1 實驗準備

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

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

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

4.2 實驗結果與分析

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

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

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

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

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

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

結束語

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