宮娜娜，王緩緩

(黃河科技學院物聯(lián)網(wǎng)傳感技術(shù)及其應(yīng)用鄭州市重點實驗室 鄭州 450063)

數(shù)學物理領(lǐng)域從1978年開始關(guān)注分布均勻性并取得了一系列的成果。文獻[1]從數(shù)論的角度研究了均勻性設(shè)計，得到了均勻設(shè)計表，與正交法相比，減少了試驗次數(shù)。文獻[2]根據(jù)文獻[1]提出的均勻性判定準則，定義了節(jié)點間f、g距離和理想布點情況下的標準半徑，由此定義了最大空穴半徑和最小空穴半徑，并提出了近似偏差的均勻度準則：以密集性偏差、稀疏性偏差和自偏差作為均勻度的度量測度。

考慮到錨節(jié)點均勻性對節(jié)點定位的影響，將均勻性的相關(guān)研究引入到無線傳感器網(wǎng)絡(luò)[3]。目前，關(guān)于無線傳感器網(wǎng)絡(luò)節(jié)點分布均勻性及其與節(jié)點定位之間的關(guān)系研究文獻較少，研究角度和思路有如下幾個方面：

1) 對均勻程度的定量描述

從概念來說，均勻程度比密度[4]和覆蓋程度都復雜。文獻[5]對基于偏差的均勻度描述方法進行了改進和擴充，使用錨節(jié)點之間的空隙大小和錨節(jié)點控制區(qū)域的面積大小表征錨節(jié)點分布的稀疏程度，進而定量地描述錨節(jié)點的均勻程度。

2) 均勻程度對定位精度的影響

文獻[6-7]采用文獻[2]中提出的方法判斷均勻程度，并且在均勻程度不夠的情況下，通過增大通信半徑，引入更多錨節(jié)點提高均勻程度。利用最小包含圓的思想進行位置估計，有效地改善錨點不均勻帶來的定位誤差；但缺點是增大通信半徑就無形中增大了功耗。

3) 均勻布點

文獻[8]根據(jù)均勻性度量勢函數(shù)模型提出均勻性布點算法，用于調(diào)節(jié)節(jié)點位置使其分布更均勻。

以上方法在均勻性判斷中，均涉及距離的概念，在無線傳感器網(wǎng)絡(luò)中，需要加入測距設(shè)備，因而增加了硬件成本。

文獻[6]中的最小包含圓算法以犧牲功耗換取定位精度。本文認為可以從未知節(jié)點所在區(qū)域的錨節(jié)點位置分布均勻性下手，不同區(qū)域采用不同的算法，以提高整體定位精度，避開了功耗問題。

本文所做的工作涉及均勻性的定量估計與基于該均勻性估計的定位算法兩方面。因為在經(jīng)典的質(zhì)心算法中[9-10]，錨節(jié)點的位置越均勻，定位的誤差越小，而對均勻性概念并沒有做明確的定義和分析。針對這個問題，本文首先提出一種無線傳感器節(jié)點的分布位置均勻性的度量方法，該方法利用接收信號強度指示RSS估計節(jié)點的相對位置，無需測距，減少了成本；然后，將該均勻性估計方法應(yīng)用到定位中。在定位之前先采用該方法對區(qū)域的均勻程度做一評估，再根據(jù)區(qū)域的不同均勻程度采用不同的定位算法，即混合定位算法，以提高整體定位精度。從而克服文獻[6]中通過增大通信半徑提高定位精度的功耗問題，并且減少了計算復雜度。

1 均勻性估計算法原理

1.1 節(jié)點的中心對稱性

研究以未知節(jié)點為圓心，其通信半徑為半徑的圓內(nèi)錨節(jié)點的分布情況，該分布情況對定位精度有很大的影響。在這個圓形區(qū)域中，一種最簡單、最理想的均勻性可理解為各個錨點與未知節(jié)點距離相等，且相鄰錨節(jié)點的距離也相等，即各錨節(jié)點分布在以未知節(jié)點為圓心的圓上，只是該圓的半徑要小于通信半徑，如圖1a所示，錨節(jié)點b1～b8均勻分布在未知節(jié)點N周圍。關(guān)于各點的位置關(guān)系有下列定理。

利用圖1a中8個錨節(jié)點信息，對未知節(jié)點N的定位結(jié)果必然是N本身，這時的定位是完全準確的。實際上，并不需要各錨節(jié)點之間的距離均相等，只要所有的錨節(jié)點關(guān)于未知節(jié)點均兩兩中心對稱的，其橫縱坐標的代數(shù)平均值，即質(zhì)心必然是圓心，這時定位也沒有誤差。

1.2 均勻性估計的基本思想

若從質(zhì)心算法的定位誤差來考慮均勻性，應(yīng)該與錨節(jié)點相互之間的距離無關(guān)，而與錨節(jié)點和未知節(jié)點的相對位置關(guān)系有關(guān)。從該角度來說，判斷均勻性就可以從錨節(jié)點與未知節(jié)點的相對位置出發(fā)。圖1a為錨節(jié)點均勻分布圖，在進行均勻性估計時，把實際中的節(jié)點分布與其相比，將兩者的差別作為均勻性的衡量指標。顯然差別越大，均勻性越差。從哪種角度衡量兩者差別需要重點研究。

經(jīng)分析，對于圖1a，若未知節(jié)點向各方向移動，圖中虛線圈內(nèi)的箭頭所示，其靠近和遠離的錨節(jié)點數(shù)目是相同的，均為4個。換句話說，若未知節(jié)點周圍的錨節(jié)點分布較均勻，則未知節(jié)點移動后，靠近和遠離的錨節(jié)點數(shù)目相差不大；反之，若錨節(jié)點分布不均勻，則一側(cè)較多，另一側(cè)較少，如圖1b所示。即未知節(jié)點移動后，必然在某些方向上遠離和靠近的錨節(jié)點數(shù)目相差較大。因此，提出以遠離和靠近錨節(jié)點個數(shù)差為線索的估計均勻性的思路。一種極限情況是兩者數(shù)目相等，個數(shù)之差為0，這時最均勻；另一種極限情況是全部靠近或者遠離，則個數(shù)差(絕對值)最大，等于錨節(jié)點總個數(shù)。為了進行統(tǒng)一的比較，將這種個數(shù)差進行歸一化，即除以總的錨節(jié)點個數(shù)和方向個數(shù)之積。

圖1 錨節(jié)點分布示意圖

在實際實現(xiàn)時，有兩個主要問題需解決：

1) 節(jié)點一般是靜態(tài)的，不能運動；

2) 移動方向不能窮盡。

參考APIT算法[11-13]的思想，借助鄰居節(jié)點模擬節(jié)點的運動，只是一個均勻性的估計，需要較高的節(jié)點密度。這樣，移動方向個數(shù)也是有限的，可以進行歸一化。另外，錨節(jié)點的遠離和靠近由接收信號強度(RSS)確定[14-17]，無需額外硬件。

1.3 成立條件的討論

上述均勻性估計的討論，是有一定條件的，這與未知節(jié)點的移動幅度和方向有關(guān)。本文研究在以下前提下進行的。

1) 未知節(jié)點的移動幅度

幅度應(yīng)較小，盡可能在錨節(jié)點集合的外部移動。移動幅度較大時，有可能移進某些錨節(jié)點集合內(nèi)部，或是從某些錨節(jié)點集合移出，造成OutToIn或者InToOut錯誤。如圖2a中箭頭所示，未知節(jié)點N從圓心移到位置1，對于b1,b3,b5,b7是靠近的；從圓心移到位置2時，對于b1是遠離的，對于b3,b5,b7是靠近的，這屬于OutToIn錯誤；從圓心移到位置3時，對于b1和b7是遠離的，對于b3和b5是靠近的，這包含OutToIn和InToOut兩種錯誤。

2) 未知節(jié)點移動的方向

移動方向不應(yīng)與兩錨節(jié)點的連線垂直，如圖2b中b1和b2與N共線，按照位置1的方向移動，與b1和b2的連線相垂直，這時遠離b1,b2,b4,b6,b8，靠近b3,b5,b7。導致遠離與靠近的錨節(jié)點數(shù)量不相同。

圖2 影響因素

2 均勻性估計算法流程

設(shè)錨節(jié)點的通信半徑為R1，未知節(jié)點的通信半徑為R2，為保證在未知節(jié)點的通信區(qū)域中，也就是半徑為R2圓內(nèi)的未知節(jié)點均能收到錨節(jié)點發(fā)送的數(shù)據(jù)，要求R1≥2R2。以未知節(jié)點為研究對象，研究其通信范圍內(nèi)錨節(jié)點分布的均勻性。均勻性估計算法的具體步驟如下：

1) 建立信息表

首先，錨節(jié)點發(fā)送數(shù)據(jù)包含自身的ID和位置，在其通信半徑R2圓內(nèi)的未知節(jié)點均能接收數(shù)據(jù)。收到數(shù)據(jù)后，未知節(jié)點記錄錨節(jié)點的ID及相應(yīng)的RSS值，建立自身的錨節(jié)點信息表X1；然后，未知節(jié)點發(fā)送數(shù)據(jù)，包含自身的ID，接收數(shù)據(jù)的節(jié)點包含錨節(jié)點與未知節(jié)點兩種類型。節(jié)點接收到數(shù)據(jù)后，記錄下ID及相應(yīng)接收信號的RSS值，并將其反饋給發(fā)送數(shù)據(jù)的未知節(jié)點。未知節(jié)點根據(jù)反饋信息，記錄錨節(jié)點的ID、位置及接收信號RSS值，建立自身的錨鄰居信息表X2；記錄未知節(jié)點的ID及接收信號RSS值，建立自身的未知節(jié)點信息表X3。

顯然，若錨節(jié)點的通信半徑與未知節(jié)點的通信半徑相等，即R1=R2，此時X1=X2；而對于R1>2R2，錨節(jié)點信息表X1應(yīng)包含錨鄰居信息表X2中的信息。

2) 確定未知鄰居

為減少OutToIn或者InToOut錯誤，選擇未知節(jié)點要縮小范圍。首先，由錨鄰居信息表X2，根據(jù)RSS值最大原則，找出距離自己最近的錨節(jié)點；在未知節(jié)點信息表X3中，找出比最近的錨鄰居RSS值更大的未知節(jié)點，作為未知鄰居，建立未知鄰居信息表X4，包含ID及相應(yīng)的RSS值。

3) 考查未知鄰居

根據(jù)未知節(jié)點的錨鄰居信息表X2中的信息，依次考查未知鄰居信息表X4中各未知鄰居的錨節(jié)點信息表X1，找出與X2對應(yīng)的相同ID號的錨節(jié)點RSS值。若RSS增大，則說明此未知鄰居比該未知節(jié)點離錨節(jié)點要近；否則，要遠。依此確定每個未知鄰居遠離或靠近的錨節(jié)點個數(shù)。

4) 計算歸一化均勻性偏差NUD

設(shè)總的錨鄰居個數(shù)為m，未知鄰居節(jié)點個數(shù)為n，設(shè)第i個未知鄰居與未知節(jié)點本身相比，遠離的錨節(jié)點個數(shù)為mi1，靠近的個數(shù)則為mi2=m-mi1。那么，歸一化均勻度偏差(normalized uniformity discrepancy,NUD)為：

式中，當mi1= mi2時，即遠離與靠近錨節(jié)點個數(shù)相同，NUD=0，最均勻；當mi1或mi2有一個等于0時，即全部遠離或全部靠近，NUD=1，最不均勻。

3 均勻性估計算法驗證

在100 m′100 m的區(qū)域中仿真，隨機產(chǎn)生若干個未知節(jié)點和錨節(jié)點，然后隨機選擇一個未知節(jié)點的通信區(qū)域作為研究區(qū)域。錨節(jié)點的通信半徑R1=60 m，未知節(jié)點的通信半徑R2=30 m。

3.1 主觀驗證

經(jīng)過3次仿真實驗，分別求得3個區(qū)域的節(jié)點分布和NUD，如圖3所示?？梢?，越均勻，NUD值越小。

圖3 3種不同的分布情況

3.2 客觀驗證

結(jié)合質(zhì)心算法的定位誤差大小，從客觀上驗證該算法的有效性。因為在一般情況下，區(qū)域中的錨節(jié)點越不均勻，質(zhì)心算法定位誤差越大，歸一化均勻性偏差NUD越大。隨機選取10個區(qū)域NUD值與定位誤差值的計算結(jié)果進行分析比較，如表1所示，隨著NUD值的增大，即越不均勻，定位誤差也逐漸增大，即均勻性高的錨節(jié)點分布，其定位精度越高，從而驗證了該方法得到的均勻性度量指標是有效的。

表1 均勻性與定位誤差

4 基于均勻性估計的混合定位算法

最小包含圓的定位算法[6]是找出包含鄰居錨節(jié)點的最小圓，將其圓心作為未知的估計值。與質(zhì)心定位算法相比，它對錨節(jié)點分布的均勻性要求不高，更適于錨節(jié)點分布不均勻的場合，其算法的復雜度比質(zhì)心算法高很多，因質(zhì)心算法的運算復雜度是O(n)，而采用暴力算法的最小包含圓的運算復雜度是O(n4)。并且，在均勻程度不夠時，它依靠增大通信半徑提高均勻程度，從而提高定位精度，必然增加功耗，其本質(zhì)是以功耗換取定位精度，而本文以定位算法的選擇來提高定位精度。因此，綜合質(zhì)心算法和最小包含圓算法的特點，提出如下的混合定位算法：

1) 應(yīng)用上述均勻性估計方法，對每個未知節(jié)點的區(qū)域進行均勻性評價，計算出相應(yīng)的NUD值。

2) 設(shè)定NUD閾值，對于NUD值小于該閾值的區(qū)域，相對均勻，采用質(zhì)心算法，定位精度高，而且算法復雜度??；而NUD值大于該閾值的區(qū)域，相對不均勻，采用最小包含圓算法，以提高定位精度。

該算法與文獻[6]相比，在一定程度上提高了定位精度，減少了算法復雜度。

5 混合定位算法的仿真與分析

對于NUD值不同的區(qū)域，采用不同的定位算法，定義精度是不同的，仿真效果如圖4所示。圖4a為區(qū)域1，NUD=0.093 3，錨節(jié)點分布相對均勻，質(zhì)心算法的誤差為0.374 9 m，最小包含圓算法的誤差為5.246 4 m；圖4b為區(qū)域2，NUD=0.303 6，錨節(jié)點分布相對不均勻，質(zhì)心算法的誤差為12.300 4 m，最小包含圓算法的誤差較小，為4.933 9 m。所以，對于具有這種特點的兩種區(qū)域，應(yīng)分別采用質(zhì)心算法和最小包含圓算法。

隨機選擇10個區(qū)域進行定位，設(shè)定閾值為0.18，得到3種算法的定位誤差數(shù)據(jù)如圖5所示。其中，質(zhì)心算法的平均誤差為7.548 9 m，最小包含圓算法平均誤差為5.760 8 m，混合定位算法誤差為4.479 9 m?；旌纤惴▽τ谫|(zhì)心算法的定位精度提高了40.65%，對于最小包含圓的定位精度提高了22.23%?？梢姡旌隙ㄎ凰惴ㄓ行У靥岣吡硕ㄎ痪?。

圖4 質(zhì)心算法與最小包含圓算法的定位效果比較

圖5 3種算法定位誤差比較

下邊討論不同參數(shù)對定位精度和功耗的影響，并對3種算法的計算復雜度進行分析。

5.1 閾值的選取對定位精度的影響

對于圖5中的10個區(qū)域，變換不同的閾值，進行混合算法的仿真，得到定位誤差的結(jié)果如表2所示?？梢钥闯鑫闹虚撝颠x擇0.18是比較合適的，閾值選取得過大或過小，都會增大定位誤差。

表2 閾值對定位誤差的影響

5.2 錨鄰居與未知鄰居對定位精度和功耗的影響

對圖5中的10個區(qū)域，統(tǒng)計節(jié)點的錨鄰居、未知鄰居個數(shù)如表3所示。

表3 錨鄰居、未知鄰居個數(shù)

錨鄰居的個數(shù)對于3種算法的定位精度一般影響不大，但其分布均勻情況會影響定位精度，其質(zhì)心算法比最小包含圓算法對于均勻程度更敏感。未知鄰居不影響質(zhì)心算法和最小包含圓算法的定位精度，但是對于混合算法，由于未知鄰居的個數(shù)及分布情況，會影響歸一化均勻性偏差NUD值的計算，進而影響閾值的選擇，最終影響定位的精度。

從功耗方面分析，錨鄰居與未知鄰居節(jié)點個數(shù)越多，節(jié)點間通信越多，功耗越大。單個節(jié)點分析，錨節(jié)點的通信半徑比未知節(jié)點大，功耗也會大一些。

5.3 3種算法計算復雜度的分析

顯然，混合算法的計算復雜度處于質(zhì)心算法與最小包含圓算法之間。從這個意義來說，與質(zhì)心算法相比，混合算法可以說是犧牲算法的復雜度換取定位精度；而與最小包含圓算法相比，混合算法既減小了復雜度，又提高了定位的精度。

6 結(jié) 論

本文提出混合定位算法的中心思想是根據(jù)區(qū)域的不同均勻程度，采用不同算法，以從整體上提高定位精度。為此，首先，采用歸一化均勻性偏差NUD值定量評估錨節(jié)點分布的均勻性，無需測距，成本較低。另外在均勻性估計過程中建立包含錨節(jié)點的位置信息，可以直接用于定位；并以此為基礎(chǔ)，利用質(zhì)心算法和最小包含圓算法進行混合定位，有效地提高了定位精度。

在定位中，均勻性度量NUD閾值的設(shè)定，會影響到定位精度，如何通過盡可能簡單的方法得到有效閾值，有待進一步的研究。

本文研究工作得到了鄭州市物聯(lián)網(wǎng)信息技術(shù)科技創(chuàng)新項目(112PCXTD343)和鄭州市智能圖像處理與識別重點實驗室的支持，在此表示感謝！

[1] 方開泰. 均勻設(shè)計——數(shù)論方法在試驗設(shè)計中的應(yīng)用[J].應(yīng)用數(shù)學學報, 1980, 3(4): 363-372.

FANG Kai-tai. Uniform design-application of number theory in pbibd[J]. Acta Mathematicae Applicatae Sinica,1980, 3(4): 363-372.

[2] 胡東紅, 李德華, 王祖喜. 均勻性度量中的密集性偏差與稀疏性偏差[J]. 數(shù)學物理學報, 2002, 22(1): 128-134.

HU Dong-hong, LI De-hua, WANG Zu-xi. New measurements of uniformity-compression discrepancy and sparseness discrepancy[J]. Acta Mathematica Scientia. 2002,22(1): 128-134.

[3] ZHU Gui-bin, ZHANG Hai-cheng, YE Jiu-zhi, et al. An anchor-free position algorithm for evenly deployed w ireless sensor networks[C]//2011 Third International Conference on Measuring Technology and Mechatronics Automation.Shanghai: IEEE Computer Society, 2011: 379-382.

[4] 韓金枝. 基于節(jié)點密度的無線傳感器網(wǎng)絡(luò)分區(qū)域節(jié)點定位技術(shù)研究[D]. 西安: 西北大學, 2012.

HAN Jin-zhi. Research on node localization based on node density for w ireless sensor network[D]. Xi’an: Northwest University, 2012.

[5] 周全, 朱紅松, 羅海勇, 等. 無線網(wǎng)絡(luò)節(jié)點的均勻性度量[J]. 高技術(shù)通訊, 2010, 20(5): 448-453.

ZHOU Quan, ZHU Hong-song, LUO Hai-yong, et al. A uniform ity metric for w ireless sensor networks[J]. Chinese High Technology Letters, 2010, 20(5): 448-453.

[6] 周全, 朱紅松, 徐勇軍, 等. 基于最小包含圓的無線傳感器網(wǎng)絡(luò)定位算法[J]. 通信學報, 2008, 29(11): 84-90.

ZHOU Quan, ZHU Hong-song, XU Yong-jun, et al.Smallest enclosing circle based localization approach for w ireless sensor networks[J]. Journal on Communications,2008, 29(11): 84-90.

[7] ZHOU Quan, LI Xiao-wer, Xu Yong-jun. Smallest enclosing circle based localization approach for w ireless sensor networks[C]//Proceedings of 2009 WRI International Conference on Communications and Mobile Computing.Kunm ing: IEEE, 2009: 61-65.

[8] 張玲, 張勝蘭, 艾君, 等. 基于勢函數(shù)的均勻性度量與均勻性布點方法[J]. 湖北大學學報(自然科學版), 2007,29(2): 144-146.

ZHANG Ling, ZHANG Sheng-lan, AI Jun, et al. Uniform measurement and uniform dots distribution based on potential function[J]. Journal of Hubei University(Natural Science) , 2007, 29(2): 144-146.

[9] BULUSU N, HEIDEMANN J, ESTRIN D. GPS less low cost outdoor location for very small devise[J]. IEEE Personal Communications Magazine, 2000, 7(5): 28-34.

[10] 何艷麗. 無線傳感器網(wǎng)絡(luò)質(zhì)心定位算法研究[J]. 計算機仿真, 2011, 28(5): 163-166.

HE Yan-li. Research on centroid Localization algorithm for w ireless sensor networks based RSS[J]. Computer Simulation, 2011, 28(5): 163-166.

[11] HE T, HUANG C, BLUM B M, et al. Range-free localization schemes for large scale sensor networks[C]//Proceedings of the 9th Annual International Conference on Mobile Computing and Networking. New York, NY, USA:ACM, 2003: 81-95.

[12] 戴佩華, 薛小平, 邵玉華. 基于垂直平分線的區(qū)域定位算法[J]. 計算機工程, 2009, 35(2): 105-108.

DAI Pei-hua, XUE Xiao-ping, SHAO Yu-hua. M idnormalbased area localization algorithm[J]. Computer Engineering, 2009, 35(2): 105-108.

[13] 萬國峰, 鐘俊. 基于三角形理論的無線傳感器網(wǎng)絡(luò)定位算法[J]. 計算機應(yīng)用研究, 2013, 30(1): 249-251.

WAN Guo-feng, ZHONG Jun. Triangle-based localization algorithm for w ireless sensor networks[J]. Application Research of Computers, 2013, 30(1): 249-251.

[14] 任重遠. 基于RSS技術(shù)的無線傳感器網(wǎng)絡(luò)定位方法研究[D]. 上海: 上海交通大學, 2012.

REN Zhong-yuan. Research of RSS Technology Based Localization Method in Wireless Sensor Networks[D].Shanghai: Shanghai Jiaotong University, 2012.

[15] 王緩緩, 胡愛娜. RSS和距離區(qū)間映射的測距方法[J]. 電子科技大學學報, 2012, 41(4): 522-526.

WANG Huan-huan, HU Ai-na. Ranging method based on the mapping between RSS and distance scope[J]. Journal of University of Electronic Science and Technology, 2012,41(4): 522-526.

[16] HUANG Wei , ZHANG Zhen-hua, WANG Ri-bin, et al. An adaptive distance correction localization algorithm based on RSS for WSNs[J]. Lecture Notes in Electrical Engineering, 2012, 143(1): 369-378.

[17] FENG Wen-jiang, BI Xiao-wei, JIANG Rong. A novel adaptive cooperative location algorithm for w ireless sensor networks[J]. International Journal of Automation and Computing, 2012, 9(5): 539-544.

編 輯 張 俊