無線傳感器網絡質心算法定位參數研究與性能分析

鄒東堯，李晨，韓騰飛

（鄭州輕工業學院計算機與通信工程學院，鄭州　450001）

無線傳感器網絡質心算法定位參數研究與性能分析

鄒東堯，李晨，韓騰飛

（鄭州輕工業學院計算機與通信工程學院，鄭州450001）

0　引言

無線傳感器網絡 （Wireless Sensor Network，WSN）作為一種新型的網絡技術近些年得到了很多研究者的關注，廣泛應用在軍事國防、目標跟蹤、環境保護、醫療衛生、智能家居和精細農業等領域［1］。在無線傳感器網絡的定位應用中，是否能精確地獲得節點的位置信息至關重要。如果無線傳感器網絡中所得到的感知數據，沒有得到對應的位置信息，通常是沒有實際意義的［2］。

WSN節點定位根據是否需要測量節點間距離和角度信息可將定位算法分為基于測距 （range-based）［3］和基于非測距（range-free）［4］。目前，基于測距的定位算法主要有TDOA、AOA、TOA、RSSI［5］等；典型的基于非測距的定位算法主要有質心算法、Amorphous算法［6］和DV-hop算法等。質心定位算法的設計相對簡單而且對節點的計算能力要求較低，目前的研究及應用較為廣泛。張愛清［7］等人提出一種基于最小包圍的多邊形定位算法，該算法以包圍未知節點鄰居錨節點的最小多邊形質心作為未知節點的估計位置。劉峰［8］等人提出將接收到的RSSI值與網絡劃分區域相結合的方法，構成未知節點的估計區域從而進行節點定位。張軍［9］等人提出了一種動態節點定位算法，由未知節點接收和保存三個點的分組信息循環組成三角形，同時依靠內點測試方法判斷未知節點的位置，再通過質心算法進行定位。衣曉［10］等人提出了WCSA定位算法，根據對定位信息的影響對不同的錨節點賦予不同的權值，對不可定位節點和邊緣節點引入次錨節點并進行二次定位。

現階段，質心算法中對其本身參數的優化和改進研究相對較少。本文通過對影響質心定位算法定位精度的錨節點數目、通信半徑R等參數進行實驗仿真分析，然后對這些參數進行了優化。仿真實驗結果表明，通過仿真分析和參數優化，可以達到提高算法定位精度的目的。

1　質心定位算法及算法應用模型

1.1質心定位算法介紹

20世紀中期，美國Bulusu教授［11］提出了質心定位算法。算法設計比較簡單，僅根據網絡的連通性就能得到未知節點的位置信息。質心定位算法的基本思想為：在一定的時間內，未知節點先尋找在自己通信范圍內的信標節點，主要通過接收目標的成功率的方法，然后把所能接收到信息的錨節點組成的多邊形的幾何質心作為未知節點的估計坐標值。如圖1所示：

圖1　質心定位算法示意圖

在質心定位算法過程中，首先所有信標節點向網絡中廣播包含自身的位置信息和信標號的信息分組。待節點廣播信息分組結束之后，未知節點保存所能接收到的錨節點的信息分組，未知節點的坐標信息就是接收到的信標節點組所成多邊形的幾何中心，即是多邊形的各個頂點位置坐標的平均值。設n個信標節點依次是P1（a1，b1），P2（a2，b2），…，Pn（an，bn），則未知節點的坐標可表示為：

質心定位算法的具體步驟：

（1）網絡初始化，各個信標節點都會在一段時間內以廣播的方式不停地在全網內發送自己的信息分組，信息分組包含自身的唯一ID標識信息和自身的坐標信息。

（2）當未知節點接收到廣播的信息分組，保存對應信標節點ID標識和坐標信息。

（3）當未知節點接收到的錨節點發送的信息組數量超過某一門限值時 （假設為n），則未知節點的坐標（A，B）可由公式（1）計算得到。

在一般的定位過程中，未知節點可能會因為通信半徑內鄰居錨節點個數少于三個而無法定位。本文質心定位算法中將解決這一問題。未知節點完成定位后就自動升級為次級信標節點，當等到自己的鄰居未知節點定位之后，沒有鄰居錨節點的未知節點就可以進行定位了。

1.2自由空間傳播模型

本實驗采用理想環境下的自由空間傳播模型［12］進行實驗，假設實驗采用的是無方向性的天線，當接收天線增益GR和發射天線增益GT相同都為1時，距離d米處接收端天線所接收到的功率PR可表示為：

自由空間的傳輸損耗為：

當GT=GR=1時，自由空間的傳輸損耗可表示為：

公式（4）中，f為工作頻率（單位為Hz）；d為收發天線間的距離（單位為m）；c為光波的傳輸速度（單位為m/s）。計算過程中，通常取頻率f的單位為MHz，距離d的單位為km，此時公式（4）可改寫為：

這里信號的傳輸損耗，實際上指電磁波在遠距離的傳輸過程中，電磁波的能量會自然擴散，能量因擴散而產生的損耗跟電磁波的頻率f和傳播距離d密切相關。實際上接收天線所捕獲的信號能量只是發射機天線發射的一小部分，大部分能量都擴散掉了。

2　質心定位算法參數

2.1節點通信半徑

在定位過程中，如果節點通信半徑變大而數量不變，則節點的能耗自然將會變大。圖2中N為未知節點，m1，m2，m3為信標節點，Ra為變化之前的半徑、Rb為變化后的半徑。A1點為當半徑為Ra時，由節點m1，m2得到的N的估計位置；A2點為當半徑變化為Rb時，由節點m1，m2，m3得到N的估計位置。

圖2　通信半徑變大，定位誤差變小

從圖2可以看到未知節點的定位誤差易受網絡中錨節點的分布情況和節點通信半徑大小的影響。當通信半徑從Ra變化為Rb時，在圖2中，未知節點N的估計位置由A1變為A2，定位誤差有所減小；相反在圖3中，未知節點N的估計位置由A1變為A2，未知節點的定位誤差卻有所增大。因此，通信半徑對定位誤差的影響要根據所在網絡信標節點的分布情況去判斷，之間沒有相對應的函數關系。

圖3　通信半徑變大，定位誤差變大

2.2錨節點數量

質心定位算法是把未知節點所有能接受到信息分組的信標節點組成的多邊形的質心作為未知節點的位置，因此，錨節點數量的增多可以提高未知節點的定位精度，但同時也會增加節點間的通信開銷，這也使得節點間的資源的消耗有所增加。另外，定位時隨機生成未知節點和錨節點的分布位置，當錨節點彼此之間的距離很近時，特別是在或者近似在一條直線上，對定位精度影響很大。

3　參數仿真研究及結果分析

通過本文第2節的分析可知，網絡中節點的分布情況、錨節點個數和通信半徑等參數都會對算法的定位精度產生影響。如圖4所示，圖4中o號表示未知節點，*號表示信標節點。實驗中錨節點和未知節點隨機分布在100m×100m的網格區域內，依次改變上述參數信息，從實驗結果中研究分析得出最佳參數。

當錨節點的個數和節點的通信半徑不同時，節點的定位誤差沒有呈現出一定的規律性。實驗中節點總數為100個，隨機分布在100m×100m的正方形網格區域內，節點通信半徑的依次取值為15m、25m、45m，錨節點個數在［2，28］之間變化。實驗結果如下圖所示：

圖4　節點分布圖

圖5　節點總數為100個

從圖5可以看出：在錨節點的數量在［2，14］之間變化時，節點定位誤差減小的趨勢較為明顯；當個數在［14，28］之間變化時，節點定位誤差的趨勢趨近平緩。當通信半徑不變時，錨節點個數為14個，節點定位誤差為最優。當R=45m時，節點的定位誤差是三個里面最大的。當R=15m和R=25m時，錨節點數量在［2，10］之間變化時，節點定位誤差的趨勢基本相同；當錨節點數量大于10個時，節點定位誤差變動的趨勢不明顯。

為了研究通信半徑對節點定位誤差的影響，在100m×100m的無線傳感器網格內，總節點數量設為100個，錨節點個數分別為6個、8個、10個、12個、14個，當通信半徑從12m到50m的變化時，定位誤差情況如圖6所示。

從圖6中可以看出：通信半徑不變，隨著錨節點數量的增加，節點的定位誤差會相對降低；錨節點個數不同時，通信半徑從12m到28m變化時，節點定位誤差變化的趨勢比較平緩，有的幾乎沒有變化，通信半徑在28m處達到平均誤差最優；通信半徑大于28m時，通信半徑越大造成定位誤差越大，仿真實驗結果表明：當總節點數為100時，R=28m為最優通信半徑。

圖6　定位誤差圖

為了得到最優仿真結果，我們進行了500次實驗，并對每個點的取值進行平均。從圖5和圖6中可以看出：在100m×100m的無線傳感器網格內，總節點數量為100個，當錨節點個數為14個，節點通信半徑為28m時，節點的定位誤差為最優值。

4　結語

本文首先介紹了質心定位算法的詳細步驟及理想環境下的算法模型，其次分析了影響質心定位算法中定位精度的節點通信半徑、錨節點個數等參數。經過仿真實驗及分析表明：節點總數為100，隨機分布在100m×100m的網格區域內，當錨節點個數為14個且通信半徑為28m時，可使算法的定位精度達到最高值。

［1］史躍飛，馮秀芳，高昊.一種基于動態錨節點的改進加權定位算法［J］.計算機應用與軟件，2013，30（10）：151-154.

［2］王焱，單欣欣，姜偉.無線傳感網絡中移動節點定位技術研究［J］.傳感技術學報，2011，24（9）：1326-1330.

［3］梅舉，陳滌辛玲.基于蒙特卡洛方法的移動傳感網節點定位優化算法［J］.傳感技術學報，2013，26（5）：689-694.

［4］HE Qin-bin，CHEN Fang-yue，CAI Shui-ming，et al.An efficient range-free localization algorithm for wireless sensor networks［J］. Science China Technological Sciences，2011，54（5）：1053-1060.

［5］鄒東堯，鄭道理，李晨.RSSI曲線擬合的誤差分析與分段方法［J］.鄭州輕工業學院學報（自然科學版），2014，29（2）：62-66.

［6］于海存，石為人，冉啟可.基于虛擬靜態錨節點的加權質心定位算法［J］.傳感技術學報，2013，26（9）：1276-1283.

［7］張愛清，葉新榮，胡海峰.無線傳感器網絡質心定位新算法及性能分析［J］.計算機應用，2012，32（9）：2429-2431，2435.

［8］劉峰，章登義.基于RSSI的無線傳感器網絡質心定位算法［J］．計算機科學，2012，39（6）：96-98.

［9］張軍，劉潛平.動態節點質心定位改進算法［J］.計算機工程與設計，2011，32（2）：446-449，538.

［10］衣曉，王梓有，薛興亮.一種基于次錨節點的無線傳感器網絡質心定位算法［J］.計算機應用與軟件，2013，30（6）：116-120.

［11］Bulusu N，Heidemann J，Estrin D．GPS-less low-cost outdoor localization for very small devices［J］．IEEE Personal Communication，2000，7（5）：28-34．

［12］程秀芝，朱達榮，張申等.基于RSSI差分校正的最小二乘-擬牛頓定位算法［J］.傳感技術學報，2014，27（1）：123-127.

Wireless Sensor Network；Centroid Localization Algorithm；Positioning Error；Communication Range

Positioning Parameter Research and Performance Analysis for Wireless Sensor Network Based on Centroid Algorithm

ZOU Dong-yao，LI Chen，HAN Teng-fei
（College of Computer and Communication Engineering，Zhengzhou University of Light Industry，Zhengzhou 450001）

1007-1423（2015）20-0028-05

10.3969/j.issn.1007-1423.2015.20.007

鄒東堯（1973-），男，河南許昌人，博士，副教授，研究方向為物聯網定位、分布式網絡

李晨（1991-），女，河南南陽人，碩士研究生，研究方向為物聯網定位

韓騰飛（1987-），男，河南洛陽人，碩士研究生，研究方向為物聯網定位

2015-05-05

2015-07-08

質心定位算法是WSN中一種典型的定位算法。首先對質心定位算法和自由空間傳播模型進行分析，然后在網格中隨機部署未知節點和錨節點，通過改變錨節點個數、節點通信半徑等參數，研究其對節點定位誤差的影響。實驗結果表明，總節點數量一定時，錨節點數量和通信半徑對定位精度存在較優值。

無線傳感器網絡；質心定位算法；定位誤差；通信半徑

河南省科技廳科技攻關項目（No.112102210321）、河南省產學研合作項目（No.122107000022）

Centroid localization algorithm is a typical algorithm in wireless sensor networks.Analyzes centroid localization algorithm and free space propagation model.Then distributes the unknown nodes and anchor nodes randomly in the grid，by changing the number of anchor nodes and communication range，analyzes the effects of the parameters like the number of anchor nodes and communication range on the positioning error.The test results indicate that when the total number of nodes is fixed，anchor nodes and communication range would optimize the positioning accuracy.