動態(tài)節(jié)點質(zhì)心定位改進(jìn)算法

張 軍， 王潛平

(中國礦業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院，江蘇徐州221116)

0 引言

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

1 定位算法介紹

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

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

而在無需測距算法定位中，在成本、功耗等方面極具有優(yōu)勢，與此同時對硬件要求較低，也無需任何基礎(chǔ)設(shè)施，因此備受關(guān)注。但是，此類傳統(tǒng)的定位算法更加的是適用于那些靜態(tài)的傳感器網(wǎng)絡(luò)定位環(huán)境[6]，對于那些應(yīng)用于動態(tài)環(huán)境的定位，這些算法就會顯得很不適用，所以本文提出了一種新的定位算法。

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

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

2 算法基礎(chǔ)介紹

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

2.1 虛擬三角形介紹

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

圖1 虛擬三角形的形成

2.2 內(nèi)點測試方法

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

圖2 三角形外

圖3 三角形內(nèi)

此算法主要是通過傳感器節(jié)點在網(wǎng)絡(luò)中的移動，并且利用無線信號的傳播特性，即信號在傳輸過程中的損耗情況，來判斷是否遠(yuǎn)離或靠近信標(biāo)節(jié)點，現(xiàn)階段的傳感器節(jié)點均具有此特性。

在算法實現(xiàn)的過程中，因為節(jié)點的移動很微小就可以滿足需求，所以假設(shè)在節(jié)點移動前后的時間內(nèi)，信標(biāo)節(jié)點的能量消耗可以簡單的忽略或者信標(biāo)節(jié)點具有一個持續(xù)的供能系統(tǒng)，即具有相同的開始條件。

2.3 質(zhì)心定位算法理論

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

圖4 多邊形質(zhì)心

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

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

當(dāng)網(wǎng)絡(luò)節(jié)點分布不均勻時，如圖2所示，未知節(jié)點與質(zhì)心的位置存在了很大的誤差，此時質(zhì)心算法就很不適用。

3 改進(jìn)的算法及其實現(xiàn)

3.1 有關(guān)節(jié)點描述

鄰居節(jié)點之間的通信如下，在網(wǎng)絡(luò)中所有的節(jié)點具有相同的通信半徑R，如圖5所示。

信標(biāo)節(jié)點：裝有GPS定位系統(tǒng)或其它定位裝置硬件，并且位置信息已知的傳感器節(jié)點。

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

圖5 節(jié)點描述

鄰居節(jié)點：是指在信標(biāo)節(jié)點的信號發(fā)射范圍內(nèi)的所有節(jié)點。

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

3.2 算法流程圖

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

圖6 算法流程

3.3 算法實現(xiàn)過程

在此算法的實施過程中，主要包括節(jié)點信息的發(fā)送階段、接收階段、定位階段以及改進(jìn)階段。在節(jié)點部署之后，信標(biāo)節(jié)點已經(jīng)明確自己的位置坐標(biāo)。

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

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

(3)定位階段：在此階段中，未知節(jié)點已經(jīng)存儲n個分組信息，在這些分組信息信息中隨機選擇3個分組信息合行成虛擬三角形，在組合之后根據(jù)內(nèi)點測試?yán)碚搧砼袛辔粗?jié)點的位置。

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

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

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

(4)改進(jìn)階段：在定位完成后，未知節(jié)點對自己進(jìn)行初始化，將T=1；為的是將其變?yōu)樾艠?biāo)節(jié)點來使用，以提高無線傳感器網(wǎng)絡(luò)的節(jié)點覆蓋度。當(dāng)節(jié)點處于靜止?fàn)顟B(tài)時，可以被看為信標(biāo)節(jié)點，從而提高了節(jié)點的定位精度。

4 算法理論驗證

(1)信標(biāo)節(jié)點發(fā)送的數(shù)據(jù)分組信息格式，如表1所示，其中包括節(jié)點ID和位置信息。

表1 發(fā)送的分組信息格式

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

表2 存儲的分組信息格式

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

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

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

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

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

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

表5 虛擬節(jié)點位置信息

最終根據(jù)質(zhì)心算法，求出未知節(jié)點的位置，即得出

所以，未知節(jié)點的位置坐標(biāo)為(36.67，46.67)。

5 算法仿真結(jié)果

在算法研究的基礎(chǔ)上，借助Matlab，對算法進(jìn)行了仿真，驗證了其有關(guān)的性能。在實驗環(huán)境下，在無線傳感器網(wǎng)絡(luò)規(guī)模中隨即布置大約20個節(jié)點，隨機分布在50×50的正方形區(qū)域中，每個節(jié)點具有相同的通信距離，其中的分組信息分發(fā)方式采用泛洪路由。

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

圖7 節(jié)點定位誤差曲線

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

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

圖8 節(jié)點定位覆蓋率曲線

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

由此可得出我們的算法，對于動態(tài)環(huán)境，具有更大的優(yōu)勢。

6 結(jié)束語

本文根據(jù)無線傳感器網(wǎng)絡(luò)質(zhì)心定位算法的特點，提出了高定位精確度、高覆蓋度且實用的新定位算法。研究發(fā)現(xiàn)該算法結(jié)合了測距算法定位和非測距算法的優(yōu)點，即誤差小和容易實現(xiàn)等特點。其主要通過接收到的分組信息來得到虛擬三角形，通過內(nèi)點測試的方法來判斷未知節(jié)點的位置，然后在確定其位置之后，決定是否保存此三角形。所以此算法主要解決了在定位過程中存在的不準(zhǔn)確和難定位等困難。最后仿真結(jié)果顯示，我們提出的算法與傳統(tǒng)的靜態(tài)定位算法相比，在更加適用于現(xiàn)實的動態(tài)環(huán)境外，大大的提高了節(jié)點的定位精度和無線傳感器網(wǎng)絡(luò)節(jié)點覆蓋度。與此同時，在以后的工作中，我們?nèi)韵Ｍ梢詫Υ怂惴ㄟM(jìn)行有關(guān)的改進(jìn)。

[1] 孫利民.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,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] 安恂.一種用于無線傳感器網(wǎng)絡(luò)的質(zhì)心定位算法[J].計算機工程與應(yīng)用,2007,43(20):136-138.

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

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

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

[9] 趙昭,陳小惠.無線傳感器網(wǎng)絡(luò)中基于RSSI的改進(jìn)定位算法[J].傳感技術(shù)學(xué)報,2009,22(3):391-394.