WSN 基于節(jié)點位置相對關(guān)系定位的數(shù)學(xué)屬性研究

劉 壯，晁美霞，張 婧，張 昕，劉 妍，張劍飛

(長春理工大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，長春130022)

WSN 基于節(jié)點位置相對關(guān)系定位的數(shù)學(xué)屬性研究

劉 壯，晁美霞，張 婧，張 昕，劉 妍，張劍飛

(長春理工大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，長春130022)

為解決無線傳感器網(wǎng)絡(luò)基于位置相對關(guān)系進(jìn)行定位算法中，定位精度過度依賴信標(biāo)節(jié)點密度問題，通過3種非測距定位算法、質(zhì)心算法、APIT(Approximate Point in Triangulation)算法及AIGS(Annulus Intersection and Grid Scan)算法的原理研究，給出了信標(biāo)節(jié)點密度與定位精度和能耗之間的數(shù)學(xué)關(guān)系，并提出基于迭代的改進(jìn)算法。3種算法定位精度正比于信標(biāo)節(jié)點密度，算法能耗正比于信標(biāo)節(jié)點密度，在同一個監(jiān)測區(qū)域，信標(biāo)節(jié)點比例相同情況下，AIGS算法定位精度最高，質(zhì)心算法定位精度最低。當(dāng)信標(biāo)節(jié)點稀疏時，將部分未知節(jié)點通過質(zhì)心算法轉(zhuǎn)化為信標(biāo)節(jié)點迭代算法，在較低信標(biāo)節(jié)點比例條件下提升3種算法定位精度。

無線傳感器網(wǎng)絡(luò);非測距定位算法;信標(biāo)節(jié)點密度;能耗;迭代

0 引 言

在無線傳感器網(wǎng)絡(luò)(WSN:Wireless Sensor Network)中節(jié)點位置信息十分重要，因為沒有攜帶位置信息的數(shù)據(jù)是毫無價值的。

目前，傳感器的定位機(jī)制是根據(jù)少量的已知信標(biāo)節(jié)點(Anchor Nodes)的位置按照某種定位方法計算未知節(jié)點位置。信標(biāo)節(jié)點采用GPS進(jìn)行定位，能耗較高，通信成本較大，因此無線傳感器網(wǎng)絡(luò)大多采用有限的信標(biāo)節(jié)點［1］。目前無線傳感器網(wǎng)絡(luò)中定位算法一般分為基于測距［2］和基于非測距［3］兩類，基于測距的定位算法需要通過測距硬件測量得到節(jié)點間實際距離或測角度硬件測量得到節(jié)點間發(fā)射夾角，使用三邊或三角或最大似然估計法計算未知節(jié)點位置;基于非測距定位算法無需測量節(jié)點之間的實際距離或方位，節(jié)點可通過某種定位機(jī)制估計未知節(jié)點位置。前者定位精度高，但硬件成本較高，會提高網(wǎng)絡(luò)部署成本;后者測量準(zhǔn)確性較差，但實現(xiàn)簡單，節(jié)點不需要額外硬件支持，成本低，功耗低，在大多數(shù)應(yīng)用場景中能實現(xiàn)滿足要求定位精度。典型的基于非測距定位算法有質(zhì)心算法［4］、APIT［5］、DV-Hop［2］，但它們也存在一些缺點［6］，質(zhì)心算法定位精度過低，APIT算法會出現(xiàn)較大比例的IntoOut和OuttoIn錯誤，DV-Hop算法會出現(xiàn)定位覆蓋不足問題。文獻(xiàn)［7］提出一種基于三角形重心掃描的改進(jìn) APIT (Approximate Point In Triangulation)算法，減少了因邊界效應(yīng)和信標(biāo)節(jié)點密度低而引起OutToIn和InToOut問題。文獻(xiàn)［8］提出一種基于最優(yōu)信標(biāo)節(jié)點的WSN質(zhì)心位置計算算法，以解決質(zhì)心算法較低精度的問題。筆者通過深入分析3種基于非測距的算法:質(zhì)心算法、APIT算法以及文獻(xiàn)［9］提出的一種基于圓環(huán)重疊區(qū)域和網(wǎng)絡(luò)掃描(AIGS:Annulus Intersection and Grid Scan)的定位算法，得出信標(biāo)節(jié)點密度與定位精度的關(guān)系，以及其三者之間的能耗消費(fèi)高低的結(jié)論，從而為非測距定位算法的數(shù)學(xué)屬性方面的研究提供有價值的參考。

1 相關(guān)工作

1.1 質(zhì)心算法

質(zhì)心算法［7］是一種基于網(wǎng)絡(luò)連通性的比較簡單容易實現(xiàn)的定位算法。該算法根據(jù)未知節(jié)點周圍一定范圍內(nèi)不同信標(biāo)節(jié)點組成的二維歐氏空間的多邊形的歐氏幾何中心作為未知節(jié)點的計算估計位置，未知節(jié)點通信半徑內(nèi)的信標(biāo)節(jié)點的選擇，可以是一跳范圍內(nèi)也可以是多跳范圍內(nèi)，這取決于WSN中的信標(biāo)節(jié)點密度。信標(biāo)節(jié)點通過周期內(nèi)向其通信范圍內(nèi)的鄰居節(jié)點廣播數(shù)據(jù)包(位置、ID標(biāo)識)，同時，未知節(jié)點會預(yù)設(shè)閾值K或設(shè)置特定時間t，若收到的數(shù)據(jù)包數(shù)量大于K或收到數(shù)據(jù)包的時間超過t，未知節(jié)點則停止接收這些來自不同信標(biāo)節(jié)點的數(shù)據(jù)，并且以之前收到的信標(biāo)節(jié)點的信息為依據(jù)確定自身位置。未知節(jié)點將這些信標(biāo)節(jié)點所組成多邊形的質(zhì)心(即坐標(biāo)平均值)作為估算坐標(biāo)(見圖1)。

如圖1所示，節(jié)點O(x，y)為需要定位的未知節(jié)點，節(jié)點A(x1，y1)、B(x2，y2)、C(x3，y3)、D(x4，y4)、E(x5，y5)、F(x6，y6)為節(jié)點O通信半徑內(nèi)的信標(biāo)節(jié)點，節(jié)點O在估算自身位置時將這些信標(biāo)節(jié)點組成多邊形并使其充當(dāng)該形狀的頂點，節(jié)點O的坐標(biāo)是多邊形ABCDEF的幾何質(zhì)心，可表示為

圖1 質(zhì)心算法原理圖Fig.1 Principle diagram of centroid algorithm

其中(x，y)代表未知節(jié)點O的坐標(biāo)，(x1，y1)、(x2，y2)、(x3，y3)、(x4，y4)、(x5，y5)、(x6，y6)代表6個信標(biāo)節(jié)點坐標(biāo)。

圖2 APIT原理圖Fig.2 Principle diagram of APIT

1.2 APIT定位

APIT算法原理如圖2所示。近似的三角形的內(nèi)點測試法(APIT)［8］是一種定位簡單，對硬件要求不高的經(jīng)典的非測距定位算法。該算法的主要思想是利用未知節(jié)點周圍與其相鄰3個信標(biāo)節(jié)點組成的三角形，運(yùn)用三角形內(nèi)點測試(PIT)理論［10］，即當(dāng)未知節(jié)點沿著一個方向移動同時能靠近和遠(yuǎn)離組成的三角形時，則表示節(jié)點在三角形外部;反之，節(jié)點在三角形內(nèi)部，從而判斷未知節(jié)點的位置是在三角形內(nèi)部還是其外部。最后，找出未知節(jié)點附近信標(biāo)節(jié)點組成的所有三角形，并把三角形的重疊區(qū)域的中心作為未知節(jié)點的位置。

1.3 AIGS算法

AIGS算法原理如圖3所示。AIGS算法［6］是一種通過對比未知節(jié)點周圍信標(biāo)節(jié)點發(fā)射信號強(qiáng)度的大小，優(yōu)化信標(biāo)節(jié)點，并利用雷達(dá)掃描法求出未知節(jié)點位置的定位算法。

該算法的主要思想是每個信標(biāo)節(jié)通過記錄其他信標(biāo)節(jié)點發(fā)射的位置信息和接收到信號的強(qiáng)度及信號到達(dá)的時間判斷它們之間的距離，并將此信息發(fā)送給未知節(jié)點。未知節(jié)點根據(jù)接收的信息，并以某個信標(biāo)節(jié)點為參照，按最大最小的原理，即以該未知節(jié)點到這個信標(biāo)節(jié)點的強(qiáng)度為參照，找出一定范圍內(nèi)其他信標(biāo)節(jié)點集合中到此信標(biāo)節(jié)點信號強(qiáng)度比自己到此信標(biāo)節(jié)點信號強(qiáng)度大的里面最小的一個和小的里面最大的一個，標(biāo)記這3個信標(biāo)節(jié)點，并以參照的信標(biāo)節(jié)點為圓心，分別以最小信號強(qiáng)度和最大信號的距離為半徑，畫圓并形成圓環(huán)。最后，找出若干個這樣的圓環(huán)，以圓環(huán)之間的重疊區(qū)域內(nèi)的質(zhì)心作為未知節(jié)點的估計坐標(biāo)。

圖3 AIGS原理圖Fig.3 Principle diagram of AIGS

2 位置相對關(guān)系定位算法數(shù)學(xué)屬性分析

2.1 節(jié)點密度與定位精度

定位技術(shù)是傳感器網(wǎng)絡(luò)應(yīng)用的前提，定位精度的提高直接關(guān)系到傳感器節(jié)點采集的數(shù)據(jù)有效性的增強(qiáng)。對于一個定位算法，定位精度顯示了節(jié)點的計算位置與物理位置的匹配程度，節(jié)點定位精度為定位誤差除以通信半徑，表示如下

其中p表示定位精度，e表示定位誤差，R表示節(jié)點的通信半徑。從式(2)中可以得出，e越小，p越小，p定位算法的定位準(zhǔn)確性越好。

基于非測距的節(jié)點定位算法是通過信標(biāo)節(jié)點進(jìn)行定位，所以信標(biāo)節(jié)點密度對評價節(jié)點定位算法非常重要。信標(biāo)節(jié)點密度為信標(biāo)節(jié)點在全網(wǎng)節(jié)點所占的比例，如下所示

其中na表示W(wǎng)SN中的信標(biāo)節(jié)點數(shù)目，N表示W(wǎng)SN中節(jié)點總數(shù)。通常情況下，d越大，p越小，在整個WSN中，當(dāng)na=N時，即d=1，則所有的節(jié)點都是信標(biāo)節(jié)點，不再需要額外的定位即可實現(xiàn)全網(wǎng)定位。

下面從定位精度和信標(biāo)節(jié)點密度兩方面討論筆者方案的質(zhì)心算法(Centroid)、APIT算法和AIGS算法。

質(zhì)心算法完全依賴于網(wǎng)絡(luò)連通能力，無線通信模型為理想的球形，未考慮影響定位精度的噪聲、干擾等環(huán)境，在定位過程中使用迭代方法計算未知節(jié)點的估計坐標(biāo)，會造成誤差累積，而且算法實現(xiàn)過程中無法修正這些誤差;APIT算法對網(wǎng)絡(luò)連通性的依賴較大，定位過程中未知節(jié)點需要與信標(biāo)節(jié)點通信且交換數(shù)據(jù)，對節(jié)點的密度較高，適合于信標(biāo)節(jié)點比例較高的WSN，在信標(biāo)節(jié)點較低的WSN中，該算法無法實現(xiàn)準(zhǔn)確定位;AIGS算法的定位精度在信標(biāo)節(jié)點一定情況下，信標(biāo)節(jié)點的比例越大，定位越準(zhǔn)確，其定位精度隨著通信半徑R的增加而提高。

信標(biāo)節(jié)點分布隨機(jī)，監(jiān)測區(qū)域內(nèi)密度不均勻，每個未知節(jié)點接收到信息的信標(biāo)節(jié)點的數(shù)量也不相同。質(zhì)心算法中，一個未知節(jié)點每增加一個信標(biāo)節(jié)點的信息就會引起幾何圖形的改變而使質(zhì)心變化即節(jié)點估計位置發(fā)生變化;APIT算法中，每多接收一個信標(biāo)節(jié)點信息，三角形的組成數(shù)目由增加到，這表示從n個信標(biāo)節(jié)點增加到n+1個信標(biāo)節(jié)點，三角形數(shù)量通過組合公式也相應(yīng)增加。因而最多三角形的覆蓋區(qū)域發(fā)生改變，中心也會發(fā)生改變;AIGS算法中，每增加一個信標(biāo)節(jié)點都會改變圓環(huán)寬度，改變未知節(jié)點估計坐標(biāo)值。

綜上所述，在信標(biāo)節(jié)點密度d相同情況下，pc＜pa＜po，其中Pc表示質(zhì)心算法定位精度，Pa表示APIT定位精度，Po表示AIGS算法定位精度。通常，定位精度很大程度上受網(wǎng)絡(luò)初始化時所部屬的信標(biāo)節(jié)點的比例及分布情況影響。信標(biāo)節(jié)點密度越大，分布越均勻，未知節(jié)點定位精度越高。因此評價一個定位算法的指標(biāo)為R越高，d越低，表明這種算法性能越好。

2．2 通信能耗和計算能耗

無線傳感器網(wǎng)絡(luò)中，在對未知節(jié)點進(jìn)行定位過程中，通常利用信標(biāo)節(jié)點位置計算未知節(jié)點位置。在此過程中，信標(biāo)節(jié)點和未知節(jié)點不斷發(fā)送或接收廣播信息，并根據(jù)接收信息，計算未知節(jié)點位置，同時將產(chǎn)生通信能耗和數(shù)據(jù)能耗。根據(jù)Heinzelman提出的無線通信能耗模型［11］，發(fā)送n比特字節(jié)無線傳感器節(jié)點所需要能量為

其中Eelec為發(fā)射裝置和接收裝置電路單位bit能耗，εamp為發(fā)射放大器將每bit傳送單元平方米所耗能量，εfs為空閑空間能耗，d為兩個傳感器節(jié)點請求數(shù)據(jù)傳輸距離，R為通信半徑。

下面從通信能耗和計算能耗兩方面討論筆者方案的質(zhì)心算法、APIT算法和AIGS算法。

根據(jù)式(4)，通信能耗ETx(n，d)為發(fā)射接收電路能耗Eelec與空閑空間能耗εfs之和。信標(biāo)節(jié)點密度越大，發(fā)送廣播信息就越多，即n越大，質(zhì)心算法、APIT和AIGS等3種算法通信能耗越大。質(zhì)心算法每增加一個信標(biāo)節(jié)點，就會增加一次一跳范圍內(nèi)廣播，APIT算法每增加一個信標(biāo)節(jié)點，就會增加一次與一跳范圍內(nèi)未知節(jié)點的信號強(qiáng)度對比廣播，AIGS算法每增加一個信標(biāo)節(jié)點，會增加一次與一跳范圍內(nèi)信標(biāo)節(jié)點的信號強(qiáng)度對比廣播。

根據(jù)質(zhì)心算法的原理，未知節(jié)點位置根據(jù)信標(biāo)節(jié)點組成的多變形質(zhì)心求出，信標(biāo)個數(shù)m每增加一個，成為m+1的計算能耗，相應(yīng)計算能耗越大。APIT根據(jù)未知節(jié)點附近所有信標(biāo)節(jié)點組成的三角形重疊區(qū)域中心即為未知節(jié)點位置，假設(shè)某個未知節(jié)點周圍有m個信標(biāo)節(jié)點，此時組成三角形的個數(shù)為，每增加一個信標(biāo)節(jié)點，三角形的個數(shù)將變?yōu)?，將會增加個三角形的網(wǎng)格掃描計算能耗。AIGS運(yùn)用未知節(jié)點附近信標(biāo)節(jié)點強(qiáng)度，優(yōu)選一些信標(biāo)節(jié)點，根據(jù)最大最小原理，形成m個圓環(huán)，每增加一個信標(biāo)節(jié)點，多一次對比信號強(qiáng)度的廣播通信能耗，會多一次計算信號強(qiáng)度大小關(guān)系的計算能耗。

通過以上數(shù)學(xué)屬性分析，可以設(shè)置節(jié)點密度，信標(biāo)節(jié)點密度和通信半徑的合理取值范圍，在節(jié)點密度稀疏情況下，可以使用迭代方式將部分定位的未知節(jié)點轉(zhuǎn)換為信標(biāo)節(jié)點進(jìn)行計算，下面是筆者提出的改進(jìn)方案。

3 基于信標(biāo)節(jié)點迭代的改進(jìn)定位方案

筆者對質(zhì)心算法、APIT和AIGS3種算法在Matlab 2011Rb下進(jìn)行仿真實驗，分析節(jié)點密度對通信誤差影響。在通信半徑為30 m情況下，定位精度對比圖如圖4所示。

從圖4中可以看出，定位精度隨著信標(biāo)節(jié)點比例增加而提高，所以在信標(biāo)節(jié)點稀疏時，筆者提出一種基于迭代改進(jìn)算法。在監(jiān)測區(qū)域中信標(biāo)節(jié)點比例過低時，一個未知節(jié)點接收到信標(biāo)節(jié)點總數(shù)就會很少，使用幾何圖形中相關(guān)屬性進(jìn)行估測未知節(jié)點位置時將會出現(xiàn)很大誤差。為了降低此種誤差，當(dāng)一個未知節(jié)點獲得本身位置信息時，會模擬信標(biāo)節(jié)點廣播信息(ID、位置信息)，而另一個未知節(jié)點接收到其信息和其他信標(biāo)節(jié)點信息確定其位置，以此類推，可確定全部未知節(jié)點位置。這種定位思想在信標(biāo)節(jié)點稀疏時動態(tài)增加了信標(biāo)節(jié)點密度，提高了定位精度，但也使能量消耗增大。

圖4 定位精度對比圖Fig.4 Comparison diagram of localization accuracy

根據(jù)圖4對比的3種算法，下一步研究需要分別降低這3種算法部署時的信標(biāo)節(jié)點比例，定位一部分未知節(jié)點，通過迭代方式，將已定位未知節(jié)點作為新信標(biāo)節(jié)點，對未定位未知節(jié)點進(jìn)行定位，對比定位精度變化情況。

4 結(jié) 語

筆者通過無線傳感器網(wǎng)絡(luò)中質(zhì)心算法，APIT和AIGS3種基于非測距定位算法分析，得出信標(biāo)節(jié)點密度越大，定位精度越準(zhǔn)確，但會引起更高的通信能耗和計算能耗。在信標(biāo)節(jié)點密度稀疏條件下，提出一種基于迭代改進(jìn)方案，該思路可提高定位精度，降低了網(wǎng)絡(luò)部署成本，但此改進(jìn)也增加了通信能耗和計算能耗，因此如何減少通信能耗和計算能耗并實現(xiàn)高定位精度成為進(jìn)一步研究方向。

［1］孫利民，李建中，陳渝.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2005. SUN Limin，LIJianzhong，CHEN Yu.Wireless Sensor Networks［M］.Beijing:Tsinghua University Press，2005.

［2］ZHANG D，LIU Y，GUO X，et al.On Distinguishing the Multiple Radio Paths in RSS-Based Ranging［C］∥Proceedings of IEEE INFOCOM.Orlando，F(xiàn)L:IEEE Press，2012:2201-2209.

［3］XIW，ZHAO J，LIU X，et al.EUL:An Efficient and Universal Localization Method for Wireless Sensor Network［C］∥Proceedings of IEEE ICDCS.Montreal，QC:IEEE Press，2009:192-210.

［4］朱博，陳曙.一種無線傳感器網(wǎng)絡(luò)質(zhì)心定位算法［J］.傳感技術(shù)學(xué)報，2010，23(6):868-872. ZHU Bo，CHEN Shu.An Improved Centroid Localization Algorithm for Wireless Sensor Network［J］.Chinese Journal of Sensors and Actuators，2010，23(6):868-872.

［5］HE T，HUANG C，BLUM B M，et al.Range-Free Localization Schemes for Large Scale Sensor Networks［C］∥Proc 9thAnnual Int'l Conf on Mobile Computing and Networking(MobiCom).San Diego，CA:Department of Computer Science School of Engineering University Virginia，2003:81-95.

［6］楊錚，吳陳沭，劉云浩.位置計算:無線網(wǎng)絡(luò)定位與可定位性［M］.北京:清華大學(xué)出版社，2014. YANG Zheng，WU Chenshu，LIU Yunhao.Location-Based Computing:Localization and Localizability of Wireless Networks［M］.Beijing:Tsinghua University Press，2014.

［7］周勇，夏士雄，丁世飛，等.基于三角形重心掃描的改進(jìn)APIT無線傳感器網(wǎng)絡(luò)自定位算法［J］.計算機(jī)研究與發(fā)展，2009，46(4):566-574. ZHOU Yong，XIA Shixiong，DING Shifei，et al.An Improved APIT Node Self-Localization Algorithm in WSN Based on Triangle Center Scan［J］.Journal of Computer Research and Development，2009，46(4):566-574.

［8］陳曉海，彭艦，劉唐.基于最優(yōu)信標(biāo)節(jié)點的無線傳感器網(wǎng)絡(luò)質(zhì)心定位算法［J］.計算機(jī)應(yīng)用，2015，35(1):5-9. CHEN Xiaohai，PENG Jian，LIU Tang.Optimal Beacon Nodes-Based Centroid Localization Algorithm for Wireless Sensor Network［J］.Journal of Computer Application，2015，35(1):5-9.

［9］LIU Zhuang，F(xiàn)ANG Zhiyi，REN Naiji，et al.A New Range-Free Localization Algorithm Based on Annulus Intersection and Grid Scan in Wireless Sensor Networks［J］.Journal of Information and Computational Science，2012，9(4):831-841.

［10］陳銳標(biāo).無線傳感器網(wǎng)絡(luò)APIT定位算法研究［D］.廣州:暨南大學(xué)信息科學(xué)技術(shù)學(xué)院，2008. CHEN Ruibiao.Research on APIT Localization［D］.Gaungzhou:College of Information Science and Technology，Jinan University，2008.

［11］WENDI B HEINZELMAN，ANANTHA P CANDRAKSAN，HARI BALAKRISHNAN.An Application-Specific Protocol Architecture forWireless Microsensor Network［J］.IEEE Transactions on Wireless Communications，2002，1(4):660-670.

(責(zé)任編輯:劉東亮)

Research on Mathematical Properties of Localization Algorithm Based on Sensor Relative Position in WSN

LIU Zhuang，CHAO Meixia，ZHANG Jing，ZHANG Xin，LIU Yan，ZHANG Jianfei

(College of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022，China)

Three kinds of range-free localization algorithms including Centroid algorithm，APIT(Approximate Point In Triangulation)algorithm and AIGS(Annulus Intersection and Grid Scan)algorithm are studied.We research on the mathematical relationship between density of anchors，location precision，and energy consumption.Research shows that the three algorithms can all getmore accurate location when enhance the density of anchors.However，all of those causemore energy consumption.In themonitoring area with the same proportion of anchors，comparing about positioning accuracy，AIGS algorithm is better than APIT algorithm，but APIT algorithm is better than Centroid algorithm.When density of anchors is low，we propose an iterative scheme which transforms unknown nodes after localization to beacon nodes.The new scheme can increase localization accuracy ofWSN(Wireless Sensor Network)with low density of anchors.

wireless sensor network(WSN);range-free localization algorithms;density of anchors;energy consumption;iterative ideology

TP393

A

1671-5896(2015)06-0685-05

2015-09-28

國家自然科學(xué)基金資助項目(61275080)

劉壯(1980— )，男，長春人，長春理工大學(xué)講師，博士，主要從事物聯(lián)網(wǎng)、無線傳感器網(wǎng)絡(luò)和復(fù)雜網(wǎng)絡(luò)研究，(Tel)86-13159539927(E-mail)liuz@cust.edu.cn;通訊作者:張婧(1986— )，女，長春人，長春理工大學(xué)講師，博士，主要從事物聯(lián)網(wǎng)、無線傳感器網(wǎng)絡(luò)和計算機(jī)網(wǎng)絡(luò)研究，(Tel)86-18686657001(E-mail)zhang_jing@cust.edu.cn。