無線傳感器網絡節點分布與定位性能之間的關系分析*

張永強， 張巧榮

(河南財經政法大學 計算機與信息工程學院，河南 鄭州 450002)

無線傳感器網絡節點分布與定位性能之間的關系分析*

張永強， 張巧榮

(河南財經政法大學 計算機與信息工程學院，河南 鄭州 450002)

無線傳感器網絡中錨節點分布情況在很大程度上影響未知節點定位的精度，但目前對均勻性的分析相對較少，針對這一問題，對錨節點分布與無線傳感器網絡定位算法性能之間的關系進行全面分析。首先提出了錨節點均勻分布的相關概念，并設計建立了相應的網絡系統模型，然后對質心算法、DV-Hop算法、最小包容圓算法性能與錨節點分布之間的關系進行了仿真實驗。結果表明:錨節點的分布情況對所有定位算法均有影響，其中質心算法對錨節點均勻性最敏感，DV-Hop算法次之，最小包容圓算法對錨節點均勻性最不敏感，分析結果對無線傳感網絡實際應用具有指導意義。

無線傳感器網絡； 節點定位； 錨節點

0 引 言

無線傳感器網絡(wireless sensor networks，WSNs)節點的定位一直是無線網絡研究中的重點和難點[1]，國內外學者對此展開了大量、深入的研究，目前主要有基于距離有關和基于距離無關的節點定位算法。距離有關定位算法包括：接收信號強度指示(received signal strength indication，RSSI)、到達時間差(time difference of arrival，TDOA)和到達角度(angle of arrival，AOA)等[2]，這些算法一般精度較高，但是需要額外的測量設備，增加了無線傳感器的定位成本，應用范圍受限；距離無關定位算法主要有質心算法、凸規劃算法、DV-Hop算法，這些算法只需要獲得網絡連通性等少量信息就可實現定位，且不需要節點額外的硬件開銷，因此,倍受關注[3,4]。在實際應用過程中，錨節點的分布對節點定位性能影響較大，胡風華等人提出基于密集性偏差稀疏性偏差評價節點分布均勻性的方法，結果表明，無線傳感器網絡節點分布越均勻，相同覆蓋條件下網絡能耗越少[5]；李磊等人提出一種無線傳感器網絡節點非均勻分布方法，對圓形區域和帶狀區域的節點能耗進行了分析[6]；凡高娟等人提出一種非均勻分布下無線傳感器網絡節點調度機制[7]；趙亞濤等人提出了一種無線傳感器網絡非均勻分布節點定位算法[8]。然而在實際應用中，如何定義節點分布均勻性概念，尤其是錨節點分布對定位算法性能影響的相關研究較少，有待進一步深入分析[9]。

為了獲得更加理想的無線傳感器節點定位結果，本文對無線傳感器網絡的錨節點分布與定位算法性能之間的關系進行全面分析，并通過具體仿真實驗進行測試。

1 相關理論

1.1 均勻性的概念

從概念來說，均勻程度比密度和覆蓋程度均要復雜，當前主要采用錨節點之間的空隙大小和錨節點控制區域的面積大小表征錨節點分布的稀疏程度，進而定量地描述錨節點的均勻程度。

1.2 錨節點分布示意圖

錨節點分布的均勻性是相對于未知節點來說的，如果從基于距離無關算法的定位誤差來考慮均勻性，如DV-Hop算法，應該與錨節點相互之間的距離無關，而與錨節點和未知節點的相對位置關系有關。從該角度來說，判斷均勻性就可以從錨節點與未知節點的相對位置出發。圖1(a)為錨節點均勻分布圖，若錨節點分布不均勻，則一側較多，另一側較少，如圖1(b)所示。

圖1 錨節點均勻和極不均勻分布示意圖

1.3 節點的中心對稱性

以未知節點為圓心，其通信半徑為半徑的圓內錨節點的分布情況，該分布情況對定位精度有很大的影響，在該圓形區域中，一種最簡單、最理想的均勻性可理解為各個錨點與未知節點距離相等，且相鄰錨節點的距離也相等，即各錨節點分布在以未知節點為圓心的圓上，只是該圓的半徑要小于通信半徑。

定理任意兩點關于它們所連線段的中點成中心對稱。在平面直角坐標系中，任意兩點P(x1,y1),Q(x2,y2)的對稱中心的坐標為((x1+x2)/2,(y1+y2)/2)，由此，b1和b2,b3和b4,b5和b6,b7和b8是關于N點中心對稱的。從經典質心算法定位公式分析

(1)

2 網絡系統模型

2.1 無線傳感器網絡結構

節點分布在如圖2所示的無線傳感器網絡監控區域內，首先節點不斷對監控范圍內的數據進行感知，然后通過通信把數據傳送到Sink節點，最后Sink節點通過因特網等進行外部網絡的通信。

圖2 無線傳感器網絡結構

2.2 能量模型

傳感器節點能耗的模塊包括傳感器模塊、處理器模塊和無線通信模塊，該模型中節點發送lbit信息的能耗為

(2)

節點接收lbit信息的能耗為

ERX(l)=l·Eelec.

(3)

簇首進行數據處理和融合時，處理lbit數據，需要的能量損耗為

Eda-fu(l)=l·EDA.

(4)

3 幾種典型距離有關定位算法

3.1 質心定位算法

質心算法是一種僅基于聯通性、與距離無關的節點定位算法，其定位原理是：待定位節點通過接收附近錨節點所發出的位置信息，并根據所接收到的錨節點位置信息求取這些錨節點的質心，并將所求得的質心作為待定位節點的位置。質心定位算法數學表達式如等式(5)所示

(5)

3.2 基于最小包容圓的定位算法

最小包含圓(smallest enclosing circle，SEC)是指給定一個平面中n個點的集合S，找出包圍它們的最小圓。基于最小包容圓的節點定位思想為：計算目標周圍通信半徑內的工作錨節點決定的最小包含圓，使用最小包含圓的圓心估計目標位置。具體步驟如下：

1)從工作錨節點集合計算構成最小包含圓的節點集合S。

2)計算由節點集合S確定的外接圓CC(C,R)。

3)外接圓圓心C是目標位置的估計。

3.3 DV-Hop定位算法

1)錨節點將信息傳遞至除自己外的所有節點，使之獲得與錨節點的跳數。

2)網絡中錨節點在獲得其他錨節點的相應信息后，計算網絡平均每跳距離，然后將其作為校正值廣播至網絡中。所有網絡節點只記錄接收到的第一個校正值，并通過鄰居節點轉發，接著根據記錄的最小跳數，計算到附近各個錨節點的跳段距離。

3)最后當未知節點獲得與3個或更多錨節點間的距離時，采用數學方法計算自身坐標。

4 仿真實驗

4.1 仿真環境

為了全面分析錨節點分布對無線傳感器定位性能的影響，在Intel雙核2.80 GHz CPU，4G RAM，800G硬盤，Windows XP操作系統上進行仿真實驗。仿真對象為：100 m×100 m的矩形區域內隨機部署36個錨節點，1個未知節點，各無線傳感器節點的通信半徑為30 m，全面分析質心算法、最小包容圓算法、DV-Hop算法與錨節點分布的關系。

4.2 結果與分析

錨節點分布與各算法的定位性能關系如圖3～圖5所示。對圖3～圖5的結果進行分析，可以得到如下結論：

1)當錨節點處于十分均勻分布狀態下，質心算法、最小包容圓算法、DV-Hop算法對未知節點的定位相當精確，可以獲得比較理想的定位結果，因此，在實際廣泛應用中，盡可能保持錨節點分布均勻。

2)當錨節點處于較均勻分布情況下，相對于質心算法和最小包容圓算法，DV-Hop算法的定位精度略高，具有一定的優勢，而最小包容圓算法的定位性能次之，質心算法最差，但是均可以獲得較好的定位結果。

圖3 錨節點分布均勻條件下的定位性能

圖4 錨節點分布不均勻條件下的定位性能

3)當錨節點處于不均勻分布情況下，質心算法和最小包容圓算法，DV-Hop算法的定位精度有所下降，定位誤差變大，其中質心定位算法的誤差最大，主要是由于質心定位算法認為所有錨節點坐標信息對未知節點的影響都是相同的，不能準確描述節點處于不均勻分布條件；最小包容圓算法的定位精度最高，這主要是最小包容圓算法由錨節點位置分布決定，而不是由錨節點的密度決定，對拓撲均勻度不敏感，這是與質心算法等以往定位算法最大的區別，該特性使得基于最小包含圓的定位算法更加適合錨節點分布疏密不均的無線傳感器網絡場合。

4) 當錨節點處于極不均勻分布情況，全部錨節點均集中在未知傳感器節點一側，此時質心算法和最小包容圓算法，DV-Hop算法的定位誤差相當大，定位結果極不理想，難以滿足無線傳感器定位精度的實際要求。

為了使實驗結果更具說服力，各進行了50次隨機仿真實驗，它們的定位誤差如圖6所示。從圖6可知，最小包容圓算法的定位誤差最小，定位錯誤變化比較平穩，定位效果最好，DV-Hop算法次之，最差為質心定位算法。

圖5 錨節點分布極不均勻條件下的定位性能

圖6 不同算法的定位誤差變化曲線

5 結 論

本文研究了圓形區域內節點分布均勻性及其對定位算法的影響。首先通過分析給出了一種圓形區域中節點理想均勻分布的模型。進而結合質心算法，討論了實際中均勻性的特點，最后，在不同分布情況下，對于三種無需測距的算法，在定位誤差、通信數據量、存儲數據量和算法復雜度等幾方面進行了對比分析，為實際定位中算法的選擇提供了一定的依據。

[1] 陳鴻龍,李鴻斌,王 智.基于TDOA測距的傳感器網絡安全定位研究[J].通信學報,2008,29(8):11-21.

[2] 葉 娟,許利軍,劉 明,等.無線傳感器網絡中非均勻的最少分簇能耗均衡算法[J].計算機應用,2008,28(11):2784-2787.

[3] 皇蘇斌，王忠群，汪千松.能量均衡的無線傳感器網絡節點非均勻分布路由協議[J].計算機應用,2011,31(11):2887-2891.

[4] 吳小兵,陳貴海.無線傳感器網絡中節點非均勻分布的能量空洞問題[J].計算機學報,2008,31(2):253-261.

[5] 胡風華,李敬兆.無線傳感器網絡的節點分布均勻性分析[J].現代電子技術,2013,36(5):41-47.

[6] 李 磊,劉海濤,李鳳榮,等.無線傳感器網絡節點非均勻分布方法研究[J].小型微型計算機系統,2010, 31(11):2180-2184.

[7] 凡高娟，孫力娟，王汝傳，等.非均勻分布下無線傳感器網絡節點調度機制[J].通信學報,2011,32(3):11-19.

[8] 趙亞濤，王玉寶.一種無線傳感器網絡非均勻分布節點定位算法[J].傳感器與微系統,2008,29(11):84-90.

[9] 宮娜娜,王緩緩.無線傳感器節點均勻性估計算法及其應用[J].電子科技大學學報,2014,43(3):5-8.

Analysis on relationship between node distribution and

localization performance of WSNs*ZHANG Yong-qiang， ZHANG Qiao-rong

(College of Computer and Information，Henan University of Economics and Law， Zhengzhou 450002，China)

Uniformity of anchor nodes distribution has a very important impact on localization precision in wireless sensor networks(WSNs),but related research is limited,in order to solve this problem,relationship between anchor node distribution and localization performance of WSNs is analyzed.Firstly,related concept of anchor nodes uniformly distribution is proposed,and corresponding network system model is designed and set up,then simulation experiments are carried out to test relationship between performance of centroid algorithm,DV-Hop algorithm,smallest enclosing circle algorithm and anchor node distribution.Results show that all localization algorithms are effected by anchor node distribution,centroid algorithm is the most sensitive to uniformity of anchor node,the next is DV-Hop algorithm,smallest enclosing circle algorithm is the most insensitive to uniformity of anchor nodes,the analysis results has guiding significance for applications of WSNs.

wireless sensor networks(WSNs); node localization; anchor node

10.13873/J.1000—9787(2015)04—0052—04

2014—08—15

國家自然科學基金資助項目(61202285)； 河南省科技攻關項目(132102210501)

TP 393

A

1000—9787(2015)04—0052—04

張永強(1972-)，男，河南鄭州人，碩士，副教授，主要研究領域為傳感器定位技術。