基于爬蟲策略的二次柵格掃描定位算法

趙正健 程良

關(guān)鍵詞：爬蟲策略；二次柵格掃描；RSSI

0 引言

伴隨著互聯(lián)網(wǎng)的快速發(fā)展，信息呈現(xiàn)爆炸性增長(zhǎng)，人們?cè)谙硎苄畔?lái)便利的同時(shí)也會(huì)面臨如何快速定位我們需要的信息問(wèn)題。當(dāng)下的爬蟲技術(shù)可以很好地解決此問(wèn)題，給人們帶來(lái)極大的便利。能否借用爬蟲策略運(yùn)用到現(xiàn)有的無(wú)線傳感器網(wǎng)絡(luò)定位中，是研究者重點(diǎn)關(guān)注的地方。爬蟲技術(shù)的核心策略主要是在整個(gè)網(wǎng)絡(luò)中根據(jù)自己指定的規(guī)則進(jìn)行快速路由，達(dá)到提高效率的作用。無(wú)線傳感器網(wǎng)絡(luò)在定位的過(guò)程中，因?yàn)橐柚鷤鞲衅鞴?jié)點(diǎn)進(jìn)行相互輔助定位，當(dāng)這些傳感器節(jié)點(diǎn)相互通信的時(shí)候，就牽扯到路徑問(wèn)題[1]。最優(yōu)路徑的選擇將直接決定后面定位精度的大小。現(xiàn)有的無(wú)線網(wǎng)絡(luò)定位算法分為兩類，基于測(cè)距以及非測(cè)距[2]。對(duì)于以測(cè)距為基礎(chǔ)的定位算法，研究者基本只在如何提高RSSI精度上縱向研究。以非測(cè)距為基礎(chǔ)的定位算法，基本聚焦在數(shù)學(xué)公式的運(yùn)用上，比如最小二乘法，加權(quán)平均等。總體來(lái)看，這兩類定位技術(shù)目前比較成熟，但在精度上來(lái)說(shuō)力量有限。二次柵格掃描與三角形質(zhì)心定位算法目前屬于較為先進(jìn)的定位算法，但對(duì)于精度要求高的地方還是顯得捉襟見(jiàn)肘。如何能夠再次提高它的定位精度也是廣大研究者一直在討論的話題。所以本文提出借助爬蟲策略思想，在傳感器網(wǎng)絡(luò)相互輔助通信的時(shí)候，針對(duì)各傳感器節(jié)點(diǎn)的路由方式進(jìn)行優(yōu)化，得到相應(yīng)的RSSI 值后再進(jìn)行常規(guī)方式的優(yōu)化[3]。最終來(lái)提高整體無(wú)線傳感器網(wǎng)絡(luò)的定位精度。

1 網(wǎng)格掃描算法

網(wǎng)格掃描算法整體來(lái)看可分為三步：

首先利用傳感器節(jié)點(diǎn)隨機(jī)布置網(wǎng)絡(luò)，待定位點(diǎn)處于該區(qū)域中。該網(wǎng)絡(luò)中有部分節(jié)點(diǎn)帶有GPS功能，稱為錨節(jié)點(diǎn)。待定位位置周圍的錨節(jié)點(diǎn)稱為鄰居錨節(jié)點(diǎn)，最近的鄰居錨節(jié)點(diǎn)稱為最近錨節(jié)點(diǎn)。各個(gè)節(jié)點(diǎn)之間可以進(jìn)行RSSI的相互通信[4]。

其次，以鄰居錨節(jié)點(diǎn)為圓心，通信距離為半徑畫圓。重合區(qū)域?yàn)樵撐粗?jié)點(diǎn)所在區(qū)域。做出該重合區(qū)域的外接矩形，記為ER[5]。如圖1所示。

最后將該外接矩形劃分成邊長(zhǎng)為l 的小矩形。若有一個(gè)鄰居錨節(jié)點(diǎn)的通信范圍覆蓋到這些小格子上，則給小格子賦1，兩個(gè)就賦2以此類推。最后將賦值最大的區(qū)域記為待定位區(qū)域，用Ej 表示。計(jì)算出該區(qū)域的質(zhì)心可作為待定位位置坐標(biāo)[6]。如圖2所示。

外接矩形ER用（lx，ly）表示，（i）為錨節(jié)點(diǎn)的數(shù)目。（x ） i，yi 是錨節(jié)點(diǎn)坐標(biāo)，r是通信半徑。用集合G表示柵格的數(shù)目。所以外接矩形面積可用式（1）表示。集合G可用式（2）表示。

2 算法改進(jìn)

2.1 爬蟲策略

2.1.1 誤差分析

二次柵格掃描算法的實(shí)現(xiàn)離不開節(jié)點(diǎn)之間RSSI 值的交互。通過(guò)將節(jié)點(diǎn)多次接收的RSSI值求平均來(lái)得到相應(yīng)的距離，如式（3）。研究發(fā)現(xiàn)，如果一組數(shù)據(jù)中有一兩個(gè)粗差存在，那么對(duì)整個(gè)實(shí)驗(yàn)誤差是非常大的。同理，在統(tǒng)計(jì)RSSI值時(shí)，若將邊緣節(jié)點(diǎn)參與計(jì)算，帶來(lái)的誤差也是非常大的。這里，我們采用爬蟲策略，先將每個(gè)節(jié)點(diǎn)進(jìn)行遍歷一遍，設(shè)定閾值，將不符合條件的節(jié)點(diǎn)當(dāng)作邊緣節(jié)點(diǎn)進(jìn)行舍棄。這樣在原始數(shù)據(jù)上進(jìn)行了一次篩選，避免了粗差帶來(lái)的影響。

由于RSSI對(duì)環(huán)境較為敏感，所以當(dāng)選擇未知節(jié)點(diǎn)周圍的鄰居錨節(jié)點(diǎn)時(shí)，由于干擾的影響，距離最近的鄰居錨節(jié)點(diǎn)所組成的區(qū)域并不一定是該未知節(jié)點(diǎn)真實(shí)存在的區(qū)域。針對(duì)此問(wèn)題，利用爬蟲策略對(duì)數(shù)據(jù)進(jìn)行分析，因?yàn)槿齻€(gè)錨節(jié)點(diǎn)就可以進(jìn)行定位。假設(shè)在無(wú)線傳感器網(wǎng)絡(luò)中，未知節(jié)點(diǎn)周圍有n 個(gè)錨節(jié)點(diǎn)，從而組成C3n種定位區(qū)域，每個(gè)定位區(qū)域的質(zhì)心都可以當(dāng)作未知節(jié)點(diǎn)的坐標(biāo)。又因?yàn)樵摱ㄎ粎^(qū)中也存在錨節(jié)點(diǎn)，所以為了解決環(huán)境干擾，我們以定位區(qū)域的這些錨節(jié)點(diǎn)作為參考節(jié)點(diǎn)，來(lái)對(duì)比哪一組定位區(qū)域所受環(huán)境干擾最小，就選擇那一組作為待定位區(qū)域，進(jìn)而來(lái)進(jìn)行下一步的定位工作。

上式中d為接收端與發(fā)射端的距離，d0為發(fā)射端的參考距離PL （d0 ）為距離d0時(shí)的路徑損耗功率PL （d） 表示距離為d時(shí)的平均接收功率。n是當(dāng)下環(huán)境的路徑損耗指數(shù)。

2.1.2 CSTG-TCLLA 算法

文中提出的算法稱為CSTG-TCLLA算法，具體分為三個(gè)步驟。

1） 一次位置預(yù)估

設(shè)未知節(jié)點(diǎn)周圍存在N個(gè)錨節(jié)點(diǎn)，通過(guò)這幾個(gè)錨節(jié)點(diǎn)做的通信圓形成的區(qū)域叫作首次定位區(qū)域記為Ej，通過(guò)求得該區(qū)域的質(zhì)心，可當(dāng)作一次定位的位置，記為S1（xt0，yt0）。

2） 優(yōu)化可再定位性

對(duì)于二次柵格掃描定位主要是基于RSSI值進(jìn)行的定位算法，所以對(duì)該算法精度的提高取決于RSSI值的精確性。由于RSSI值受環(huán)境因素較大，進(jìn)而提高了定位過(guò)程體中精度的不穩(wěn)定性，為了解決此問(wèn)題，本文引入爬蟲策略解決RSSI值精確性問(wèn)題。使錨節(jié)點(diǎn)在接收未知節(jié)點(diǎn)發(fā)送的RSSI值的時(shí)候，避免了極端數(shù)值對(duì)實(shí)驗(yàn)造成的巨大誤差，為后續(xù)二次柵格掃描的穩(wěn)定性打下基礎(chǔ)。

3） 柵格二次賦值

通過(guò)爬蟲策略去除邊緣節(jié)點(diǎn)之后，參與計(jì)算的RSSI值更加平滑，根據(jù)最近錨節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)進(jìn)行二次掃描，掃描區(qū)域記為Ej。計(jì)算該區(qū)域中所有柵格中心到最近錨節(jié)點(diǎn)的距離記為D，如式（4）。

為了縮小定位區(qū)域，將集合D 中所有距離和未知節(jié)點(diǎn)到最近錨節(jié)點(diǎn)之間的距離，記為dist，進(jìn)行對(duì)比。如果dm < dist，則稱為可再定位區(qū)域，并且給柵格內(nèi)賦值為N + 1，新的區(qū)域稱為ENj，將ENj 的質(zhì)心當(dāng)作未知節(jié)點(diǎn)的坐標(biāo)。如圖3，若未知節(jié)點(diǎn)周圍有三個(gè)錨節(jié)點(diǎn)，分別記為A1，A2，A3，以最近錨節(jié)點(diǎn)A1為圓心，再次掃描可得ENj區(qū)域。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)計(jì)

本文以Matlab為仿真環(huán)境，通過(guò)隨機(jī)拓?fù)涔?jié)點(diǎn)的方式來(lái)模擬現(xiàn)實(shí)環(huán)境中的定位場(chǎng)景。給定部分節(jié)點(diǎn)固定的位置坐標(biāo)以及未知節(jié)點(diǎn)的坐標(biāo)。通過(guò)定位算法定位出未知節(jié)點(diǎn)坐標(biāo)，進(jìn)而與給定的未知節(jié)點(diǎn)坐標(biāo)做對(duì)比，以此來(lái)衡量不同算法的誤差程度。文中所提出的新算法記為CSTG-TCLLA算法，傳統(tǒng)的二次柵格掃描算法，二次柵格掃描算法以及文獻(xiàn)[4]中的算法分別記為TGTCL-LA算法，Grid-scan算法和VGrid-scan 算法。利用式（4）計(jì)算每種算法的定位誤差，并且將從通信半徑，節(jié)點(diǎn)個(gè)數(shù)，錨節(jié)點(diǎn)個(gè)數(shù)以及柵格邊長(zhǎng)這4種情況下充分來(lái)比較幾種算法的定位精度。

E為平均誤差，（xr，yr），（xt，yt）分別為未知節(jié)點(diǎn)的估計(jì)坐標(biāo)和未知節(jié)點(diǎn)的真實(shí)坐標(biāo)，k為拓?fù)浯螖?shù)，nr 參與定位的未知節(jié)點(diǎn)個(gè)數(shù)。

3.2 通信半徑對(duì)定位誤差的影響

為了驗(yàn)證通信半徑的不同對(duì)定位誤差的影響，實(shí)驗(yàn)中選取固定的節(jié)點(diǎn)個(gè)數(shù)200個(gè)，以及錨節(jié)點(diǎn)個(gè)數(shù)30 個(gè)，規(guī)定小格子的長(zhǎng)度為2米，以此來(lái)進(jìn)行仿真實(shí)驗(yàn)，結(jié)果如圖4所示。

由實(shí)驗(yàn)結(jié)果得，對(duì)比較為流行的這幾種算法。CSTG-TCLLA算法與TG-TCLLA算法，VGrid-scan算法以及Grid-scan算法相比，平均定位誤差分別減少了7.2%，10.68%以及12.83%。

3.3 節(jié)點(diǎn)個(gè)數(shù)對(duì)定位誤差的影響

同理為了測(cè)驗(yàn)節(jié)點(diǎn)個(gè)數(shù)對(duì)算法精度的影響，控制其他量都不變的情況下，改變節(jié)點(diǎn)個(gè)數(shù)的數(shù)量，對(duì)比這幾種算法的定位誤差，仿真圖如圖5所示。

由圖5可得，給定節(jié)點(diǎn)個(gè)數(shù)為N、錨節(jié)點(diǎn)個(gè)數(shù)為0.3N、通信半徑為20米、柵格邊長(zhǎng)為2米。文中提出的算法相比于Grid-scan算法、VGrid-Scan算法以及TG-TCLLA 算法，在平均定位誤差上分別減少了13.62%、11.58%以及9.26%。

3.4 錨節(jié)點(diǎn)個(gè)數(shù)對(duì)定位誤差的影響

給定節(jié)點(diǎn)總數(shù)為200個(gè)，通信半徑為20米，柵格長(zhǎng)2米，分析幾種算法的定位誤差，如圖6所示。

仿真可得，文中提出的算法相比于傳統(tǒng)的Gridscan算法、VGrid-Scan 算法以及TG-TCLLA 算法，在平均定位誤差上分別減少了11.2%，5.8%以及3.6%。

3.5 柵格邊長(zhǎng)對(duì)定位誤差的影響

規(guī)定節(jié)點(diǎn)個(gè)數(shù)為200，通信半徑為20米，錨節(jié)點(diǎn)為30個(gè)，仿真結(jié)果如圖7所示。

由仿真圖可得，柵格邊長(zhǎng)的大小也是影響定位算法誤差的主要因素。文中提到的算法相比較于傳統(tǒng)的Grid-scan算法、VGrid-Scan算法和TG-TCLLA算法在定位誤差上分別減少了8.26%，6.24%以及2.68%。

4 結(jié)束語(yǔ)

二次柵格掃描算法主要依靠節(jié)點(diǎn)間RSSI值的大小關(guān)系進(jìn)行相關(guān)定位計(jì)算。由于RSSI值受環(huán)境因素影響明顯，常規(guī)處理方式通過(guò)求平均或采用卡爾曼濾波算法來(lái)平滑RSSI值。但并不能避免RSSI粗差帶來(lái)的影響。同時(shí)在具體定位過(guò)程中，多徑效應(yīng)的影響使得距離最近的錨節(jié)點(diǎn)所組成的定位區(qū)域并不一定是未知節(jié)點(diǎn)所在區(qū)域，從而造成定位誤差。本文采用爬蟲策略解不僅舍棄邊緣節(jié)點(diǎn)，而且在最終的定位區(qū)域選擇上，借助已知錨節(jié)點(diǎn)的位置，進(jìn)行了客觀上的對(duì)比，選擇出最優(yōu)的定位區(qū)域。從而系統(tǒng)性地提高定位精度，改進(jìn)了二次柵格掃描算法。