基于約束粒子群算法的網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)研究

謝宏飛

（湛江科技學(xué)院，廣東 湛江 524000）

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

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

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

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

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

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

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

2 約束粒子群初始化

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

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

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

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

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

4 模擬實(shí)驗(yàn)

為了驗(yàn)證本文基于約束粒子群算法改進(jìn)的網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)與傳統(tǒng)方式比較是否都具有優(yōu)勢(shì)。進(jìn)行模擬測(cè)試實(shí)驗(yàn)，對(duì)比該技術(shù)與傳統(tǒng)技術(shù)相比，噪聲的標(biāo)準(zhǔn)方差的對(duì)比，在定位測(cè)試中噪聲的標(biāo)準(zhǔn)方差越大說(shuō)明在定位中受到的干擾越多，定位的精度就越不準(zhǔn)確。

4.1 實(shí)驗(yàn)準(zhǔn)備

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

實(shí)驗(yàn)分別在四種實(shí)驗(yàn)條件下進(jìn)行，模擬實(shí)驗(yàn)條件信息如下：1號(hào)場(chǎng)景為13*10*6，障礙物為0；2號(hào)場(chǎng)景為20*12*6.2，障礙物為1；3號(hào)場(chǎng)景為25*13*6.5，障礙物為2；4號(hào)場(chǎng)景為30*15*7，障礙物為2。

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

4.2 實(shí)驗(yàn)結(jié)果與分析

基于上述實(shí)驗(yàn)環(huán)境對(duì)比該技術(shù)與傳統(tǒng)方法相比，信號(hào)傳播中噪聲的標(biāo)準(zhǔn)方差，結(jié)果如下圖所示：

由圖1可以看出，本文設(shè)計(jì)的方法的定位精度更高，定位結(jié)果受到的干擾更小。

圖1 四種模擬場(chǎng)景標(biāo)準(zhǔn)差對(duì)比曲線

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

表1 定位過(guò)程的時(shí)間開(kāi)銷對(duì)比/ms

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

結(jié)束語(yǔ)

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