無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布與定位性能之間的關(guān)系分析*

張永強(qiáng)， 張巧榮

(河南財(cái)經(jīng)政法大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，河南 鄭州 450002)

無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布與定位性能之間的關(guān)系分析*

張永強(qiáng)， 張巧榮

(河南財(cái)經(jīng)政法大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，河南 鄭州 450002)

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

無線傳感器網(wǎng)絡(luò)； 節(jié)點(diǎn)定位； 錨節(jié)點(diǎn)

0 引 言

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

為了獲得更加理想的無線傳感器節(jié)點(diǎn)定位結(jié)果，本文對(duì)無線傳感器網(wǎng)絡(luò)的錨節(jié)點(diǎn)分布與定位算法性能之間的關(guān)系進(jìn)行全面分析，并通過具體仿真實(shí)驗(yàn)進(jìn)行測(cè)試。

1 相關(guān)理論

1.1 均勻性的概念

從概念來說，均勻程度比密度和覆蓋程度均要復(fù)雜，當(dāng)前主要采用錨節(jié)點(diǎn)之間的空隙大小和錨節(jié)點(diǎn)控制區(qū)域的面積大小表征錨節(jié)點(diǎn)分布的稀疏程度，進(jìn)而定量地描述錨節(jié)點(diǎn)的均勻程度。

1.2 錨節(jié)點(diǎn)分布示意圖

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

圖1 錨節(jié)點(diǎn)均勻和極不均勻分布示意圖

1.3 節(jié)點(diǎn)的中心對(duì)稱性

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

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

(1)

2 網(wǎng)絡(luò)系統(tǒng)模型

2.1 無線傳感器網(wǎng)絡(luò)結(jié)構(gòu)

節(jié)點(diǎn)分布在如圖2所示的無線傳感器網(wǎng)絡(luò)監(jiān)控區(qū)域內(nèi)，首先節(jié)點(diǎn)不斷對(duì)監(jiān)控范圍內(nèi)的數(shù)據(jù)進(jìn)行感知，然后通過通信把數(shù)據(jù)傳送到Sink節(jié)點(diǎn)，最后Sink節(jié)點(diǎn)通過因特網(wǎng)等進(jìn)行外部網(wǎng)絡(luò)的通信。

圖2 無線傳感器網(wǎng)絡(luò)結(jié)構(gòu)

2.2 能量模型

傳感器節(jié)點(diǎn)能耗的模塊包括傳感器模塊、處理器模塊和無線通信模塊，該模型中節(jié)點(diǎn)發(fā)送lbit信息的能耗為

(2)

節(jié)點(diǎn)接收lbit信息的能耗為

ERX(l)=l·Eelec.

(3)

簇首進(jìn)行數(shù)據(jù)處理和融合時(shí)，處理lbit數(shù)據(jù)，需要的能量損耗為

Eda-fu(l)=l·EDA.

(4)

3 幾種典型距離有關(guān)定位算法

3.1 質(zhì)心定位算法

質(zhì)心算法是一種僅基于聯(lián)通性、與距離無關(guān)的節(jié)點(diǎn)定位算法，其定位原理是：待定位節(jié)點(diǎn)通過接收附近錨節(jié)點(diǎn)所發(fā)出的位置信息，并根據(jù)所接收到的錨節(jié)點(diǎn)位置信息求取這些錨節(jié)點(diǎn)的質(zhì)心，并將所求得的質(zhì)心作為待定位節(jié)點(diǎn)的位置。質(zhì)心定位算法數(shù)學(xué)表達(dá)式如等式(5)所示

(5)

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

最小包含圓(smallest enclosing circle，SEC)是指給定一個(gè)平面中n個(gè)點(diǎn)的集合S，找出包圍它們的最小圓?；谧钚“輬A的節(jié)點(diǎn)定位思想為：計(jì)算目標(biāo)周圍通信半徑內(nèi)的工作錨節(jié)點(diǎn)決定的最小包含圓，使用最小包含圓的圓心估計(jì)目標(biāo)位置。具體步驟如下：

1)從工作錨節(jié)點(diǎn)集合計(jì)算構(gòu)成最小包含圓的節(jié)點(diǎn)集合S。

2)計(jì)算由節(jié)點(diǎn)集合S確定的外接圓CC(C,R)。

3)外接圓圓心C是目標(biāo)位置的估計(jì)。

3.3 DV-Hop定位算法

1)錨節(jié)點(diǎn)將信息傳遞至除自己外的所有節(jié)點(diǎn)，使之獲得與錨節(jié)點(diǎn)的跳數(shù)。

2)網(wǎng)絡(luò)中錨節(jié)點(diǎn)在獲得其他錨節(jié)點(diǎn)的相應(yīng)信息后，計(jì)算網(wǎng)絡(luò)平均每跳距離，然后將其作為校正值廣播至網(wǎng)絡(luò)中。所有網(wǎng)絡(luò)節(jié)點(diǎn)只記錄接收到的第一個(gè)校正值，并通過鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)，接著根據(jù)記錄的最小跳數(shù)，計(jì)算到附近各個(gè)錨節(jié)點(diǎn)的跳段距離。

3)最后當(dāng)未知節(jié)點(diǎn)獲得與3個(gè)或更多錨節(jié)點(diǎn)間的距離時(shí)，采用數(shù)學(xué)方法計(jì)算自身坐標(biāo)。

4 仿真實(shí)驗(yàn)

4.1 仿真環(huán)境

為了全面分析錨節(jié)點(diǎn)分布對(duì)無線傳感器定位性能的影響，在Intel雙核2.80 GHz CPU，4G RAM，800G硬盤，Windows XP操作系統(tǒng)上進(jìn)行仿真實(shí)驗(yàn)。仿真對(duì)象為：100 m×100 m的矩形區(qū)域內(nèi)隨機(jī)部署36個(gè)錨節(jié)點(diǎn)，1個(gè)未知節(jié)點(diǎn)，各無線傳感器節(jié)點(diǎn)的通信半徑為30 m，全面分析質(zhì)心算法、最小包容圓算法、DV-Hop算法與錨節(jié)點(diǎn)分布的關(guān)系。

4.2 結(jié)果與分析

錨節(jié)點(diǎn)分布與各算法的定位性能關(guān)系如圖3～圖5所示。對(duì)圖3～圖5的結(jié)果進(jìn)行分析，可以得到如下結(jié)論：

1)當(dāng)錨節(jié)點(diǎn)處于十分均勻分布狀態(tài)下，質(zhì)心算法、最小包容圓算法、DV-Hop算法對(duì)未知節(jié)點(diǎn)的定位相當(dāng)精確，可以獲得比較理想的定位結(jié)果，因此，在實(shí)際廣泛應(yīng)用中，盡可能保持錨節(jié)點(diǎn)分布均勻。

2)當(dāng)錨節(jié)點(diǎn)處于較均勻分布情況下，相對(duì)于質(zhì)心算法和最小包容圓算法，DV-Hop算法的定位精度略高，具有一定的優(yōu)勢(shì)，而最小包容圓算法的定位性能次之，質(zhì)心算法最差，但是均可以獲得較好的定位結(jié)果。

圖3 錨節(jié)點(diǎn)分布均勻條件下的定位性能

圖4 錨節(jié)點(diǎn)分布不均勻條件下的定位性能

3)當(dāng)錨節(jié)點(diǎn)處于不均勻分布情況下，質(zhì)心算法和最小包容圓算法，DV-Hop算法的定位精度有所下降，定位誤差變大，其中質(zhì)心定位算法的誤差最大，主要是由于質(zhì)心定位算法認(rèn)為所有錨節(jié)點(diǎn)坐標(biāo)信息對(duì)未知節(jié)點(diǎn)的影響都是相同的，不能準(zhǔn)確描述節(jié)點(diǎn)處于不均勻分布條件；最小包容圓算法的定位精度最高，這主要是最小包容圓算法由錨節(jié)點(diǎn)位置分布決定，而不是由錨節(jié)點(diǎn)的密度決定，對(duì)拓?fù)渚鶆蚨炔幻舾?，這是與質(zhì)心算法等以往定位算法最大的區(qū)別，該特性使得基于最小包含圓的定位算法更加適合錨節(jié)點(diǎn)分布疏密不均的無線傳感器網(wǎng)絡(luò)場(chǎng)合。

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

為了使實(shí)驗(yàn)結(jié)果更具說服力，各進(jìn)行了50次隨機(jī)仿真實(shí)驗(yàn)，它們的定位誤差如圖6所示。從圖6可知，最小包容圓算法的定位誤差最小，定位錯(cuò)誤變化比較平穩(wěn)，定位效果最好，DV-Hop算法次之，最差為質(zhì)心定位算法。

圖5 錨節(jié)點(diǎn)分布極不均勻條件下的定位性能

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

5 結(jié) 論

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

[1] 陳鴻龍,李鴻斌,王 智.基于TDOA測(cè)距的傳感器網(wǎng)絡(luò)安全定位研究[J].通信學(xué)報(bào),2008,29(8):11-21.

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

[3] 皇蘇斌，王忠群，汪千松.能量均衡的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)非均勻分布路由協(xié)議[J].計(jì)算機(jī)應(yīng)用,2011,31(11):2887-2891.

[4] 吳小兵,陳貴海.無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)非均勻分布的能量空洞問題[J].計(jì)算機(jī)學(xué)報(bào),2008,31(2):253-261.

[5] 胡風(fēng)華,李敬兆.無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)分布均勻性分析[J].現(xiàn)代電子技術(shù),2013,36(5):41-47.

[6] 李 磊,劉海濤,李鳳榮,等.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)非均勻分布方法研究[J].小型微型計(jì)算機(jī)系統(tǒng),2010, 31(11):2180-2184.

[7] 凡高娟，孫力娟，王汝傳，等.非均勻分布下無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度機(jī)制[J].通信學(xué)報(bào),2011,32(3):11-19.

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

[9] 宮娜娜,王緩緩.無線傳感器節(jié)點(diǎn)均勻性估計(jì)算法及其應(yīng)用[J].電子科技大學(xué)學(xué)報(bào),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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61202285)； 河南省科技攻關(guān)項(xiàng)目(132102210501)

TP 393

A

1000—9787(2015)04—0052—04

張永強(qiáng)(1972-)，男，河南鄭州人，碩士，副教授，主要研究領(lǐng)域?yàn)閭鞲衅鞫ㄎ患夹g(shù)。