鄒東堯，李晨，韓騰飛

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

無線傳感器網(wǎng)絡質(zhì)心算法定位參數(shù)研究與性能分析

鄒東堯，李晨，韓騰飛

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

0　引言

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

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

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

1　質(zhì)心定位算法及算法應用模型

1.1質(zhì)心定位算法介紹

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

圖1　質(zhì)心定位算法示意圖

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

質(zhì)心定位算法的具體步驟：

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

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

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

在一般的定位過程中，未知節(jié)點可能會因為通信半徑內(nèi)鄰居錨節(jié)點個數(shù)少于三個而無法定位。本文質(zhì)心定位算法中將解決這一問題。未知節(jié)點完成定位后就自動升級為次級信標節(jié)點，當?shù)鹊阶约旱泥従游粗?jié)點定位之后，沒有鄰居錨節(jié)點的未知節(jié)點就可以進行定位了。

1.2自由空間傳播模型

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

自由空間的傳輸損耗為：

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

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

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

2　質(zhì)心定位算法參數(shù)

2.1節(jié)點通信半徑

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

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

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

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

2.2錨節(jié)點數(shù)量

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

3　參數(shù)仿真研究及結(jié)果分析

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

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

圖4　節(jié)點分布圖

圖5　節(jié)點總數(shù)為100個

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

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

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

圖6　定位誤差圖

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

4　結(jié)語

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

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

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

［3］梅舉，陳滌辛玲.基于蒙特卡洛方法的移動傳感網(wǎng)節(jié)點定位優(yōu)化算法［J］.傳感技術(shù)學報，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］.鄭州輕工業(yè)學院學報（自然科學版），2014，29（2）：62-66.

［6］于海存，石為人，冉啟可.基于虛擬靜態(tài)錨節(jié)點的加權(quán)質(zhì)心定位算法［J］.傳感技術(shù)學報，2013，26（9）：1276-1283.

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

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

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

［10］衣曉，王梓有，薛興亮.一種基于次錨節(jié)點的無線傳感器網(wǎng)絡質(zhì)心定位算法［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］.傳感技術(shù)學報，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-），男，河南許昌人，博士，副教授，研究方向為物聯(lián)網(wǎng)定位、分布式網(wǎng)絡

李晨（1991-），女，河南南陽人，碩士研究生，研究方向為物聯(lián)網(wǎng)定位

韓騰飛（1987-），男，河南洛陽人，碩士研究生，研究方向為物聯(lián)網(wǎng)定位

2015-05-05

2015-07-08

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

無線傳感器網(wǎng)絡；質(zhì)心定位算法；定位誤差；通信半徑

河南省科技廳科技攻關(guān)項目（No.112102210321）、河南省產(chǎn)學研合作項目（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.