無線傳感器節點均勻性估計算法及其應用

宮娜娜，王緩緩

(黃河科技學院物聯網傳感技術及其應用鄭州市重點實驗室 鄭州 450063)

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

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

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

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

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

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

3) 均勻布點

文獻[8]根據均勻性度量勢函數模型提出均勻性布點算法，用于調節節點位置使其分布更均勻。

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

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

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

1 均勻性估計算法原理

1.1 節點的中心對稱性

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

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

1.2 均勻性估計的基本思想

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

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

圖1 錨節點分布示意圖

在實際實現時，有兩個主要問題需解決：

1) 節點一般是靜態的，不能運動；

2) 移動方向不能窮盡。

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

1.3 成立條件的討論

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

1) 未知節點的移動幅度

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

2) 未知節點移動的方向

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

圖2 影響因素

2 均勻性估計算法流程

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

1) 建立信息表

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

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

2) 確定未知鄰居

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

3) 考查未知鄰居

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

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

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

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

3 均勻性估計算法驗證

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

3.1 主觀驗證

經過3次仿真實驗，分別求得3個區域的節點分布和NUD，如圖3所示。可見，越均勻，NUD值越小。

圖3 3種不同的分布情況

3.2 客觀驗證

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

表1 均勻性與定位誤差

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

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

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

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

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

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

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

隨機選擇10個區域進行定位，設定閾值為0.18，得到3種算法的定位誤差數據如圖5所示。其中，質心算法的平均誤差為7.548 9 m，最小包含圓算法平均誤差為5.760 8 m，混合定位算法誤差為4.479 9 m。混合算法對于質心算法的定位精度提高了40.65%，對于最小包含圓的定位精度提高了22.23%。可見，混合定位算法有效地提高了定位精度。

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

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

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

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

對于圖5中的10個區域，變換不同的閾值，進行混合算法的仿真，得到定位誤差的結果如表2所示。可以看出文中閾值選擇0.18是比較合適的，閾值選取得過大或過小，都會增大定位誤差。

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

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

對圖5中的10個區域，統計節點的錨鄰居、未知鄰居個數如表3所示。

表3 錨鄰居、未知鄰居個數

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

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

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

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

6 結 論

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

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

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

[1] 方開泰. 均勻設計——數論方法在試驗設計中的應用[J].應用數學學報, 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]. 數學物理學報, 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] 韓金枝. 基于節點密度的無線傳感器網絡分區域節點定位技術研究[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] 周全, 朱紅松, 羅海勇, 等. 無線網絡節點的均勻性度量[J]. 高技術通訊, 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] 周全, 朱紅松, 徐勇軍, 等. 基于最小包含圓的無線傳感器網絡定位算法[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] 張玲, 張勝蘭, 艾君, 等. 基于勢函數的均勻性度量與均勻性布點方法[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] 何艷麗. 無線傳感器網絡質心定位算法研究[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] 戴佩華, 薛小平, 邵玉華. 基于垂直平分線的區域定位算法[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] 萬國峰, 鐘俊. 基于三角形理論的無線傳感器網絡定位算法[J]. 計算機應用研究, 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技術的無線傳感器網絡定位方法研究[D]. 上海: 上海交通大學, 2012.

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

[15] 王緩緩, 胡愛娜. RSS和距離區間映射的測距方法[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.

編 輯 張 俊