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

趙正健 程良

關鍵詞：爬蟲策略；二次柵格掃描；RSSI

0 引言

伴隨著互聯網的快速發展，信息呈現爆炸性增長，人們在享受信息帶來便利的同時也會面臨如何快速定位我們需要的信息問題。當下的爬蟲技術可以很好地解決此問題，給人們帶來極大的便利。能否借用爬蟲策略運用到現有的無線傳感器網絡定位中，是研究者重點關注的地方。爬蟲技術的核心策略主要是在整個網絡中根據自己指定的規則進行快速路由，達到提高效率的作用。無線傳感器網絡在定位的過程中，因為要借助傳感器節點進行相互輔助定位，當這些傳感器節點相互通信的時候，就牽扯到路徑問題[1]。最優路徑的選擇將直接決定后面定位精度的大小?，F有的無線網絡定位算法分為兩類，基于測距以及非測距[2]。對于以測距為基礎的定位算法，研究者基本只在如何提高RSSI精度上縱向研究。以非測距為基礎的定位算法，基本聚焦在數學公式的運用上，比如最小二乘法，加權平均等。總體來看，這兩類定位技術目前比較成熟，但在精度上來說力量有限。二次柵格掃描與三角形質心定位算法目前屬于較為先進的定位算法，但對于精度要求高的地方還是顯得捉襟見肘。如何能夠再次提高它的定位精度也是廣大研究者一直在討論的話題。所以本文提出借助爬蟲策略思想，在傳感器網絡相互輔助通信的時候，針對各傳感器節點的路由方式進行優化，得到相應的RSSI 值后再進行常規方式的優化[3]。最終來提高整體無線傳感器網絡的定位精度。

1 網格掃描算法

網格掃描算法整體來看可分為三步：

首先利用傳感器節點隨機布置網絡，待定位點處于該區域中。該網絡中有部分節點帶有GPS功能，稱為錨節點。待定位位置周圍的錨節點稱為鄰居錨節點，最近的鄰居錨節點稱為最近錨節點。各個節點之間可以進行RSSI的相互通信[4]。

其次，以鄰居錨節點為圓心，通信距離為半徑畫圓。重合區域為該未知節點所在區域。做出該重合區域的外接矩形，記為ER[5]。如圖1所示。

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

外接矩形ER用（lx，ly）表示，（i）為錨節點的數目。（x ） i，yi 是錨節點坐標，r是通信半徑。用集合G表示柵格的數目。所以外接矩形面積可用式（1）表示。集合G可用式（2）表示。

2 算法改進

2.1 爬蟲策略

2.1.1 誤差分析

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

由于RSSI對環境較為敏感，所以當選擇未知節點周圍的鄰居錨節點時，由于干擾的影響，距離最近的鄰居錨節點所組成的區域并不一定是該未知節點真實存在的區域。針對此問題，利用爬蟲策略對數據進行分析，因為三個錨節點就可以進行定位。假設在無線傳感器網絡中，未知節點周圍有n 個錨節點，從而組成C3n種定位區域，每個定位區域的質心都可以當作未知節點的坐標。又因為該定位區中也存在錨節點，所以為了解決環境干擾，我們以定位區域的這些錨節點作為參考節點，來對比哪一組定位區域所受環境干擾最小，就選擇那一組作為待定位區域，進而來進行下一步的定位工作。

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

2.1.2 CSTG-TCLLA 算法

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

1） 一次位置預估

設未知節點周圍存在N個錨節點，通過這幾個錨節點做的通信圓形成的區域叫作首次定位區域記為Ej，通過求得該區域的質心，可當作一次定位的位置，記為S1（xt0，yt0）。

2） 優化可再定位性

對于二次柵格掃描定位主要是基于RSSI值進行的定位算法，所以對該算法精度的提高取決于RSSI值的精確性。由于RSSI值受環境因素較大，進而提高了定位過程體中精度的不穩定性，為了解決此問題，本文引入爬蟲策略解決RSSI值精確性問題。使錨節點在接收未知節點發送的RSSI值的時候，避免了極端數值對實驗造成的巨大誤差，為后續二次柵格掃描的穩定性打下基礎。

3） 柵格二次賦值

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

為了縮小定位區域，將集合D 中所有距離和未知節點到最近錨節點之間的距離，記為dist，進行對比。如果dm < dist，則稱為可再定位區域，并且給柵格內賦值為N + 1，新的區域稱為ENj，將ENj 的質心當作未知節點的坐標。如圖3，若未知節點周圍有三個錨節點，分別記為A1，A2，A3，以最近錨節點A1為圓心，再次掃描可得ENj區域。

3 仿真實驗

3.1 實驗設計

本文以Matlab為仿真環境，通過隨機拓撲節點的方式來模擬現實環境中的定位場景。給定部分節點固定的位置坐標以及未知節點的坐標。通過定位算法定位出未知節點坐標，進而與給定的未知節點坐標做對比，以此來衡量不同算法的誤差程度。文中所提出的新算法記為CSTG-TCLLA算法，傳統的二次柵格掃描算法，二次柵格掃描算法以及文獻[4]中的算法分別記為TGTCL-LA算法，Grid-scan算法和VGrid-scan 算法。利用式（4）計算每種算法的定位誤差，并且將從通信半徑，節點個數，錨節點個數以及柵格邊長這4種情況下充分來比較幾種算法的定位精度。

E為平均誤差，（xr，yr），（xt，yt）分別為未知節點的估計坐標和未知節點的真實坐標，k為拓撲次數，nr 參與定位的未知節點個數。

3.2 通信半徑對定位誤差的影響

為了驗證通信半徑的不同對定位誤差的影響，實驗中選取固定的節點個數200個，以及錨節點個數30 個，規定小格子的長度為2米，以此來進行仿真實驗，結果如圖4所示。

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

3.3 節點個數對定位誤差的影響

同理為了測驗節點個數對算法精度的影響，控制其他量都不變的情況下，改變節點個數的數量，對比這幾種算法的定位誤差，仿真圖如圖5所示。

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

3.4 錨節點個數對定位誤差的影響

給定節點總數為200個，通信半徑為20米，柵格長2米，分析幾種算法的定位誤差，如圖6所示。

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

3.5 柵格邊長對定位誤差的影響

規定節點個數為200，通信半徑為20米，錨節點為30個，仿真結果如圖7所示。

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

4 結束語

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