動態節點質心定位改進算法

張 軍， 王潛平

(中國礦業大學計算機科學與技術學院，江蘇徐州221116)

0 引言

目前，傳感器網絡已經迅速的融入了當今的生活，很好的應用于實時環境。無線傳感器網絡是一種全新的信息獲取平臺，可以在廣泛的應用領域內實現復雜的大范圍監測和追蹤任務，而網絡節點自身定位是大多數應用的基礎和前提[1]，在如今動態環境下，網絡節點的自我定位具有相當大的應用前景，可以應用于城市汽車定位，追蹤任務等。但是，傳感器網絡的一些固有特性使得傳感器節點的實時定位變得十分困難。為了能夠滿足為現實的需要，在應用無線傳感器網絡的環境中，往往會依靠外界的一些硬件設施來進行輔助。為了實現動態環境下的無線傳感器網絡節點定位，在適度的依靠硬件下，本文根據無線傳感器網絡質心定位算法的特點，提出了高定位精確、高覆蓋度且實用的改進定位算法。該算法通過接收到的分組信息來得到虛擬三角形，通過內點測試的方法來判斷未知節點的位置，在確定其位置之后，決定是否保存此三角形。計算出此虛擬三角形的質心位置，最終根據質心算法來確定最終的未知節點位置，相比較與傳統的靜態定位算法，本文算法具有更加的實用性。

1 定位算法介紹

至今，已發展了很多算法來解決無線傳感器網絡節點自身定位問題。目前的定位算法從定位手段上主要分為兩大類：基于測距算法和無需測距算法[2]。基于測距算法通過測量節點間的距離或角度信息，使用三邊測量、三角測量或極大似然估計定位法來計算節點位置，常用的定位算法有：RSSI[3]，TOA，TDOA[4]和AOA；無需測距定位算法則不需要距離和角度信息，算法根據網絡連通性等信息來實現節點定位，常用的定位算法有：質心[5]，凸規劃，DV-Hop，Amorphous，MDS-MAP和APIT。

在測距算法定位過程中，可以通過采用多次測量，以及循環定位來減少誤差，這些算法在獲得相對精確定位結果的同時，會產生大量的計算和通信開銷，因此此定位機制雖然在定位精度上有可取之處，但是卻并不適用于那些低功耗、低成本等應用領域。

而在無需測距算法定位中，在成本、功耗等方面極具有優勢，與此同時對硬件要求較低，也無需任何基礎設施，因此備受關注。但是，此類傳統的定位算法更加的是適用于那些靜態的傳感器網絡定位環境[6]，對于那些應用于動態環境的定位，這些算法就會顯得很不適用，所以本文提出了一種新的定位算法。

本文提出的新的定位改進算法，即能夠實現相對高的定位精度，又能夠滿足動態定位。該改進算法主要是依靠信標節點來幫助進行未知節點自我定位。在定位的過程中，通過依靠節點本身的硬件設備來獲取接收到的信號強度[7]。在接收到分組信息之后，根據接收節點是否為信標節點來判斷對此分組信息是否進行保存。如果接收節點是信標節點，則丟棄此分組信息；否則保存此分組信息。然后，通過循環的形式來選擇3個分組信息進行組合三角形，在本文中被稱為虛擬三角形。同時根據本文所提出的內點測試方法來進行有關判斷此被定位未知節點是否在此三角形中，如果被定位未知節點在此虛擬三角形中，則保留此三角形；否則，丟棄此虛擬三角形，重新組合三角形，直到所需要的次數或者定位的精度。在確定虛擬三角形之后，根據傳統的質心方法進行最終的定位，并且對節點進行升級，避免節點共線，不能夠形成三角形問題[8]。

所以本文的新算法，主要是在傳統的質心算法上增加了未知節點位置判斷這個定位主要環節，使得新算法在擁有自我定位的特點上，避免了傳統三角形質心與未知節點位置誤差太大的情況出現，并且具有更高的定位精度和定位覆蓋度。

2 算法基礎介紹

此改進算法主要是對質心算法的定位誤差和定位覆蓋度進行了有關改進。在算法的實施過程中，首先需要節點的簡單硬件支持，來判斷未知節點所在的三角形，此過程主要是依靠虛擬三角形和內點測試方法，來確定未知節點所存在的虛擬三角形。

2.1 虛擬三角形介紹

虛擬三角形基本思想：假設存在n個端點，那么共有C(3，n)種不同的選取方法來確定不同的三角形，但是為了降低消耗，往往設置循環的次數或者定位所需的精度為限制條件，而在本論文中，此三角形被稱為虛擬三角形，如圖1所示。

圖1 虛擬三角形的形成

2.2 內點測試方法

假如端點的移動存在一個方向，沿著這個方向節點D會同時遠離或接近三角形的3個端點A、B、C，那么可以認為節點D位于△ABC之外，如圖2所示；或者，當遠離二個端點并且接近一個端點，以及靠近二個端點并且遠離一個端點的時，則認為D位于△ABC內，如圖3所示。

圖2 三角形外

圖3 三角形內

此算法主要是通過傳感器節點在網絡中的移動，并且利用無線信號的傳播特性，即信號在傳輸過程中的損耗情況，來判斷是否遠離或靠近信標節點，現階段的傳感器節點均具有此特性。

在算法實現的過程中，因為節點的移動很微小就可以滿足需求，所以假設在節點移動前后的時間內，信標節點的能量消耗可以簡單的忽略或者信標節點具有一個持續的供能系統，即具有相同的開始條件。

2.3 質心定位算法理論

質心算法：多邊形的幾何中心稱為質心，多邊形頂點坐標的平均值就是質心節點的坐標。質心定位算法首先確定包含未知節點的區域，然后計算這個區域的質心，最終將其作為未知節點的位置，如圖4所示。

圖4 多邊形質心

在質心算法中，信標節點周期性地向鄰近節點廣播信標分組信息，信標分組信息中包含信標節點的標識號和位置信息。當未知節點接收到來自不同信標節點的信標分組信息數量超過某一個門限k或接收一定時間后，就確定自身位置為這些信標節點所組成的多邊形的質心。

質心算法完全基于網絡連通性，無需信標節點和未知節點之間的協調，因此比較簡單，容易實現。但質心算法假設節點都擁有理想的球型無線信號傳播模型，而實際上無線信號的傳播模型并非如此。同時，質心定位算法對傳感器節點的布置有很大的關系，密度越大，分布的越均勻，定位精度越高，所以很難實現理想的需求。

當網絡節點分布不均勻時，如圖2所示，未知節點與質心的位置存在了很大的誤差，此時質心算法就很不適用。

3 改進的算法及其實現

3.1 有關節點描述

鄰居節點之間的通信如下，在網絡中所有的節點具有相同的通信半徑R，如圖5所示。

信標節點：裝有GPS定位系統或其它定位裝置硬件，并且位置信息已知的傳感器節點。

未知節點：未知自己的位置信息，但是同樣具有GPS定位系統或其它定位裝置硬件的傳感器節點。

圖5 節點描述

鄰居節點：是指在信標節點的信號發射范圍內的所有節點。

虛擬節點：此節點是根據算法所虛擬得到，在未知節點收到分組信息，組合成三角形，進行三角形判斷后計算所得出的三角形質心節點被稱之為虛擬節點。

3.2 算法流程圖

算法的流程圖，如圖6所示。

圖6 算法流程

3.3 算法實現過程

在此算法的實施過程中，主要包括節點信息的發送階段、接收階段、定位階段以及改進階段。在節點部署之后，信標節點已經明確自己的位置坐標。

(1)初始化階段：此階段設定所有信標節點以一定的周期來廣播自己的分組信息，包括位置(x，y)，ID號；對于未知節點，T=0；對于信標節點，T=1；其中的ID號被用于唯一的區別節點。

(2)接收階段：在此定位算法中，未知節點會接收到二次分組信息，分別是移動前和移動后，在接收數據后，根據信號的信息，得到信號的強度，并存儲。但是，信標節點會丟棄同是信標節點發送的分組信息。

(3)定位階段：在此階段中，未知節點已經存儲n個分組信息，在這些分組信息信息中隨機選擇3個分組信息合行成虛擬三角形，在組合之后根據內點測試理論來判斷未知節點的位置。

通常在未知節點的移動過程中，未知節點距信標節點越遠，其接收到信標節點的信號強度就越弱，根據未知節點移動前所接收到信標節點所發出的分組信息中的信號強度值和在自己移動后所接收到的信號強度值進行比較，以此來判斷此未知節點的移動情況，判斷是否在此虛擬三角形中。由于節點的移動往往很快，距離很小，所以可以考慮忽略信標節點的能量消耗。

此判斷過程主要是根據節點的信號強度參數，來決定三角形是否被放棄。在確定未知節點存在于此三角形中之后，計算出三角形的質心，稱為虛擬節點，位置(Xn，Yn)；否則，放棄此三角形，如此的循環下去，直到完成所有的C(3，n)種組合或者得到算法所需的精度。

在得出所有的虛擬節點位置信息之后，根據質心定位算法來進行最終的未知節點自我定位，未知節點的坐標為(X，Y)

(4)改進階段：在定位完成后，未知節點對自己進行初始化，將T=1；為的是將其變為信標節點來使用，以提高無線傳感器網絡的節點覆蓋度。當節點處于靜止狀態時，可以被看為信標節點，從而提高了節點的定位精度。

4 算法理論驗證

(1)信標節點發送的數據分組信息格式，如表1所示，其中包括節點ID和位置信息。

表1 發送的分組信息格式

(2)在鄰居節點接收到此分組信息后，首先會判斷自己的T，若為是1，表示自己是信標節點，則丟棄此分組信息；否則，表示自己是未知節點，于是根據接收到的信號得到信號強度，并存儲，存儲的分組信息格式如表2所示。

表2 存儲的分組信息格式

(3)在存儲n個分組信息之后，進行內點測試，判斷過程如下：

如表3和表4所示，其中表3為未知節點在移動前所接收到的周圍信標節點的分組信息后存儲的信息，其中包含信標節點的節點ID號，位置信息，以及計算得到的信號強度；表4為未知節點在移動后所接收到的周圍信標節點的分組信息后存儲的信息，其中包含信標節點的節點ID號，位置信息，以及計算得到的信號強度。

根據未知節點所接收到的二個分組信息中的信號強度，可以得出：在移動過程中，未知節點對信標節點A和C的信號強度在減小，即可以得出遠離信標節點A和C；同時對B的信號強度在增加，即可以得出接近信標節點B。所以根據內點測試方法理論，可以得出未知節點存在于此3個信標節點A、B和C所組成的虛擬三角形中，所以保留此三角形。

表3 移動前的存儲分組信息

表4 移動后的存儲分組信息

(4)計算虛擬三角形的質心，在此算法中被稱為虛擬節點(Xn，Yn)，存儲在未知節點中，格式如表5所示。

表5 虛擬節點位置信息

最終根據質心算法，求出未知節點的位置，即得出

所以，未知節點的位置坐標為(36.67，46.67)。

5 算法仿真結果

在算法研究的基礎上，借助Matlab，對算法進行了仿真，驗證了其有關的性能。在實驗環境下，在無線傳感器網絡規模中隨即布置大約20個節點，隨機分布在50×50的正方形區域中，每個節點具有相同的通信距離，其中的分組信息分發方式采用泛洪路由。

有關算法的性能主要從定位精度和定位覆蓋率兩個方面對其進行評估，每種算法仿真隨機運行10次，然后取平均值，仿真結果如圖7所示。

圖7 節點定位誤差曲線

圖7是定位誤差的仿真曲線，由于當信標節點較少時，并且在未知節點周圍的多邊形面積較小時，改進的定位算法誤差和原算法的誤差相當。這是因為，改進算法是采用取多個包含未知節點的三角形質心來縮小多邊形面積，以減少誤差，當未知節點的多邊形面積較少時，就沒有很大的必要去進一步縮小，從而效果不是很明顯。

但是，隨著未知節點多邊形面積的增加，以及信標節點的分布不均勻，誤差會明顯的增大，此時改進的算法就起到了很大的作用。在未知節點被定位之后，可以通過升級的形式使得其變為信標節點。仿真結果如圖8所示。

圖8 節點定位覆蓋率曲線

圖8是節點定位覆蓋率的分析曲線圖，當信標節點個數較少時，有些節點無法找到3個以上的信標節點去進行自我定位，從而不能計算出自己坐標的位置信息，但是隨著未知節點被確定后進行升級為信標節點的做法，勢必會提高信標節點的數量，節點的覆蓋率達到提高。所以改進后的算法，提高了定位的精確度。

由此可得出我們的算法，對于動態環境，具有更大的優勢。

6 結束語

本文根據無線傳感器網絡質心定位算法的特點，提出了高定位精確度、高覆蓋度且實用的新定位算法。研究發現該算法結合了測距算法定位和非測距算法的優點，即誤差小和容易實現等特點。其主要通過接收到的分組信息來得到虛擬三角形，通過內點測試的方法來判斷未知節點的位置，然后在確定其位置之后，決定是否保存此三角形。所以此算法主要解決了在定位過程中存在的不準確和難定位等困難。最后仿真結果顯示，我們提出的算法與傳統的靜態定位算法相比，在更加適用于現實的動態環境外，大大的提高了節點的定位精度和無線傳感器網絡節點覆蓋度。與此同時，在以后的工作中，我們仍希望可以對此算法進行有關的改進。

[1] 孫利民.無線傳感器網絡[M].北京:清華大學出版社,2005:148-155.

[2] He T,Huang C D,Blum B M,et al.Range-free localization schemes in large scale sensor networks[C].Proc of the 9th Annual Int'l Conf on Mobile Computing and Networking.San Diego:ACM Press,2003:81-95.

[3] Yu N,Wan J.SL-R distributed localization algorithm for wireless sensor networks[C].Proceedings of IEEE International Conference on Wireless Communications,Networking and Mobile Computing,2007:2360-2363.

[4] Girod L,Estrin D.Robust range estimation using acoustic and multimodal sensing[C].Proc of the IEEE/RSJ Int Conf on Intelligent Robots and Systems,2001:1312-1320.

[5] 安恂.一種用于無線傳感器網絡的質心定位算法[J].計算機工程與應用,2007,43(20):136-138.

[6] 王福豹,史龍,任豐原.無線傳感器網絡中的自身定位系統和算法[J].軟件學報,2005,16(5):857-868.

[7] 陳維克,李文鋒.基于RSSI的無線傳感器網絡加權質心定位算法[J].武漢理工大學學報(交通科學與工程版),2006,30(2):265-268.

[8] 于寧,萬江文,吳銀鋒.無線傳感器網絡定位算法研究[J].傳感技術學報,2007,20(1):187-192.

[9] 趙昭,陳小惠.無線傳感器網絡中基于RSSI的改進定位算法[J].傳感技術學報,2009,22(3):391-394.