基于虛擬靜態(tài)錨節(jié)點(diǎn)的加權(quán)質(zhì)心定位算法*

于海存，石為人，冉啟可，王開(kāi)通

(重慶大學(xué)自動(dòng)化學(xué)院，重慶400030)

無(wú)線傳感器網(wǎng)絡(luò)是由部署在監(jiān)測(cè)區(qū)域內(nèi)大量的廉價(jià)微型傳感器節(jié)點(diǎn)組成，通過(guò)無(wú)線通信方式形成的一個(gè)多跳自組織網(wǎng)絡(luò)。而隨著數(shù)據(jù)業(yè)務(wù)和多媒體業(yè)務(wù)的快速增加，人們對(duì)定位與導(dǎo)航的需求日益增大。在室內(nèi)目標(biāo)定位和跟蹤等應(yīng)用中，無(wú)線傳感器網(wǎng)絡(luò)正好彌補(bǔ)了GPS衛(wèi)星定位在室內(nèi)難于獲得準(zhǔn)確位置信息的弊端［1］，可以為監(jiān)獄、倉(cāng)庫(kù)、礦井、大型場(chǎng)館等提供安全防護(hù)、人員跟蹤等實(shí)時(shí)位置信息。

根據(jù)是否需要測(cè)量距離，無(wú)線傳感器網(wǎng)絡(luò)定位算法可分為基于測(cè)距(Range-Based)的定位算法和非測(cè)距(Range-Free)的定位算法［2］。前者是利用測(cè)量得到的距離或角度信息來(lái)進(jìn)行定位計(jì)算;后者一般是利用網(wǎng)絡(luò)的節(jié)點(diǎn)的連通性和多跳路由交換信息等方法來(lái)間接估計(jì)兩點(diǎn)間的距離［3］。目前比較典型的基于測(cè)距的定位算法有 RSSI、TOA、TDOA、AOA［4］;基于非測(cè)距的定位算法有質(zhì)心算法、APIT算法、DV-Hop 算法以及 MAP 算法［5－6］。

加權(quán)質(zhì)心定位算法繼承了質(zhì)心算法運(yùn)算較為簡(jiǎn)單的特點(diǎn)，并利用RSSI測(cè)距作為依據(jù)合理的分配權(quán)重，經(jīng)過(guò)加權(quán)之后可以得到較高的定位精度［7］。該算法的缺陷是:為了達(dá)到較高的定位精度，往往需要布置數(shù)量較多的錨節(jié)點(diǎn)［8］，造成硬件成本的增加，大大限制了該算法在實(shí)際中的應(yīng)用。針對(duì)該算法的缺陷，本文結(jié)合余弦定理，構(gòu)造虛擬靜態(tài)錨節(jié)點(diǎn)參與定位。僅需布置較少的錨節(jié)點(diǎn)就可以取得較高的定位精度，提高了加權(quán)質(zhì)心算法的實(shí)用性。

1 加權(quán)質(zhì)心算法

本節(jié)首先簡(jiǎn)要介紹目前應(yīng)用最廣泛的無(wú)線電磁波信號(hào)測(cè)距模型。第二部分內(nèi)容是對(duì)加權(quán)質(zhì)心算法進(jìn)行數(shù)學(xué)分析，從導(dǎo)數(shù)的角度闡述了權(quán)重系數(shù)和RSSI測(cè)距在加權(quán)質(zhì)心算法中的影響作用。第三部分內(nèi)容著重分析布置錨節(jié)點(diǎn)數(shù)量較少的情況下，定位誤差較大的原因。

1.1 無(wú)線電磁波信號(hào)RSSI測(cè)距模型

在自由空間中，最常用的無(wú)線信號(hào)傳播模型是對(duì)數(shù)—常態(tài)分布模型［9］，距發(fā)射端d米處的天線接收到的信號(hào)強(qiáng)度由式(1)給出:

式(1)中，d為接收端與發(fā)射端之間的距離;d0為參考距離，一般取1 m;Pr(d)是接收端的接收信號(hào)功率;Pr(d0)是參考距離d0點(diǎn)對(duì)應(yīng)的接收信號(hào)功率;Xσ是一個(gè)均值為0的高斯隨機(jī)變量;β為路徑損耗指數(shù)。通過(guò)測(cè)量接收信號(hào)的功率強(qiáng)度，利用式(2)可計(jì)算出信號(hào)發(fā)射端和接收端之間的距離:

1.2 加權(quán)質(zhì)心算法分析

質(zhì)心算法只單純考慮了網(wǎng)絡(luò)的連通度，未考慮錨節(jié)點(diǎn)與未知節(jié)點(diǎn)的遠(yuǎn)近程度對(duì)未知節(jié)點(diǎn)定位的影響［10］，故定位精度較低。顯然，當(dāng)某錨節(jié)點(diǎn)與未知節(jié)點(diǎn)距離越近時(shí)，該錨節(jié)點(diǎn)的坐標(biāo)對(duì)未知節(jié)點(diǎn)的定位結(jié)果影響越大;反之，則影響越小。據(jù)此，運(yùn)用權(quán)重的概念，令該值與錨節(jié)點(diǎn)到未知節(jié)點(diǎn)的距離的n次方成反比，利用權(quán)重值進(jìn)行加權(quán)之后的質(zhì)心定位算法可表示為［11］:

其中，Pi(x，y)為未知節(jié)點(diǎn)估計(jì)位置的坐標(biāo);Bj(x，y)為錨節(jié)點(diǎn)j的坐標(biāo);wij為錨節(jié)點(diǎn)j對(duì)未知節(jié)點(diǎn)i的權(quán)重值;n為權(quán)重系數(shù)，取值一般在1～4之間;dij為錨節(jié)點(diǎn)j到未知節(jié)點(diǎn)i的距離值;N為錨節(jié)點(diǎn)個(gè)數(shù)。

加權(quán)質(zhì)心定位算法的關(guān)鍵在于如何合理分配權(quán)重值。由式(4)可知，加權(quán)質(zhì)心算法權(quán)重只與兩因素有關(guān):權(quán)重系數(shù)和未知節(jié)點(diǎn)到各個(gè)錨節(jié)點(diǎn)的距離值。接下來(lái)將就這兩因素分別分析它們對(duì)定位算法的影響作用。

1.2.1 權(quán)重系數(shù)變化對(duì)加權(quán)質(zhì)心算法的影響作用分析

研究表明，權(quán)重系數(shù)n取值不同，定位結(jié)果也會(huì)有所差異，且在不同的子區(qū)域?qū)?yīng)的最優(yōu)權(quán)重系數(shù)也不盡相同［12］。

由式(3)可變換為式(5)和式(6):

Pi，j(x，y)表示錨節(jié)點(diǎn) Bj(x，y)對(duì)最終定位結(jié)果的貢獻(xiàn)大小。為了分析權(quán)重系數(shù)變化對(duì)Pi，j(x，y)的影響，對(duì)權(quán)重系數(shù)n求導(dǎo)可得:

假設(shè)未知節(jié)點(diǎn)到錨節(jié)點(diǎn)Bk(x，y)距離最近，到錨節(jié)點(diǎn) Bm(x，y)的距離最遠(yuǎn)，即 dik=min(di1，di2，di3，…，diN)，dim=max(di1，di2，di3，…，diN)，則可得到式(8)、式(9):

即 Pi，k(x，y)的導(dǎo)數(shù)恒大于零，Pi，m(x，y)的導(dǎo)數(shù)恒小于零。所代表的物理意義是:隨著n增大，距離未知節(jié)點(diǎn)最近的錨節(jié)點(diǎn)Bk(x，y)對(duì)最終定位結(jié)果Pi(x，y)的影響越大，Pi，k(x，y)相對(duì)于 Pi(x，y)所占的比例越大，未知節(jié)點(diǎn)的估計(jì)位置越接近于錨節(jié)點(diǎn)k;距離未知節(jié)點(diǎn)最遠(yuǎn)的錨節(jié)點(diǎn)Bm(x，y)對(duì)最終定位結(jié)果Pi(x，y)的影響越小，Pi，m(x，y)相對(duì)于 Pi(x，y)所占的比例越小，未知節(jié)點(diǎn)的估計(jì)位置越遠(yuǎn)離錨節(jié)點(diǎn)m。當(dāng)系數(shù)n減小時(shí)，亦可以推導(dǎo)出與上相反的結(jié)論。

1.2.2 RSSI測(cè)距變化對(duì)加權(quán)質(zhì)心算法的影響作用分析

類似的，當(dāng)要研究未知節(jié)點(diǎn)到某一錨節(jié)點(diǎn)距離變化對(duì)該錨節(jié)點(diǎn)權(quán)重值的影響時(shí)，就要把權(quán)重系數(shù)當(dāng)作常量，距離值當(dāng)變量。這里假定錨節(jié)點(diǎn)k到未知節(jié)點(diǎn)i的距離dik減小，推導(dǎo)Pi，k(x，y)的變化。由式(6)中1/dik求導(dǎo)可得:

即 dik減小，1/dik增大，而 P'i，k(1/dik)恒大于零，故可得到 Pi，k(x，y)增大，Pi，k(x，y)相對(duì)于 Pi(x，y)所占的比例越大，未知節(jié)點(diǎn)的估計(jì)位置越接近于錨節(jié)點(diǎn)k。

1.3 錨節(jié)點(diǎn)數(shù)量較少導(dǎo)致定位誤差較大的原因分析

覆蓋一個(gè)矩形的平面定位區(qū)域最少需要布置四個(gè)錨節(jié)點(diǎn)，接下來(lái)就以錨節(jié)點(diǎn)布置數(shù)量最少為應(yīng)用背景分析在此情況下加權(quán)質(zhì)心算法出現(xiàn)定位誤差較大的原因，如圖1所示。

圖1 權(quán)重系數(shù)作用分析

情形1:未知節(jié)點(diǎn)位于O1時(shí)被定位在O'1，定位誤差較小，原因是錨節(jié)點(diǎn)B2距離O1很近，分配的權(quán)重值遠(yuǎn)大于其他幾個(gè)錨節(jié)點(diǎn)，故定位位置會(huì)非常接近錨節(jié)點(diǎn)B2。

情形2:未知節(jié)點(diǎn)位于O2時(shí)定位位置在O'2，誤差較大，原因是缺少一個(gè)對(duì)定位結(jié)果起主導(dǎo)作用的錨節(jié)點(diǎn)。此時(shí)由于未知節(jié)點(diǎn)到錨節(jié)點(diǎn)B1、B2的距離與到錨節(jié)點(diǎn)B3、B4的距離差距不足以讓錨節(jié)點(diǎn)B1、B2獲得足夠大的權(quán)重值。假設(shè)在未知節(jié)點(diǎn)O2附近增設(shè)一個(gè)能起主導(dǎo)作用的錨節(jié)點(diǎn)，該未知節(jié)點(diǎn)的定位誤差就會(huì)減小，分析如情形1。

通過(guò)上面的分析，定位計(jì)算過(guò)程可以理解為多個(gè)錨節(jié)點(diǎn)之間的“博弈”過(guò)程，即在權(quán)重系數(shù)選取適當(dāng)?shù)那疤嵯拢鄠€(gè)錨節(jié)點(diǎn)之間根據(jù)RSSI測(cè)距合理分配權(quán)重的過(guò)程;適當(dāng)增加錨節(jié)點(diǎn)數(shù)量，能有效的提高加權(quán)質(zhì)心算法的定位精度。在下節(jié)基于VSAN的加權(quán)質(zhì)心算法中，我們將結(jié)合該算法仿真結(jié)果進(jìn)行更加具體的論述。

2 基于VSAN的加權(quán)質(zhì)心算法

前文已經(jīng)提到，錨節(jié)點(diǎn)布置數(shù)量較少時(shí)，必然會(huì)導(dǎo)致某些位置的未知節(jié)點(diǎn)定位誤差較大，而限制加權(quán)質(zhì)心定位算法在實(shí)際中應(yīng)用的主要因素又恰好是定位所需的硬件成本較大，因此在滿足所需定位精度的前提下如何減少錨節(jié)點(diǎn)的布置數(shù)量就變得非常具有意義。本文主要的研究思路是以虛擬錨節(jié)點(diǎn)替代部分真實(shí)錨節(jié)點(diǎn)參與節(jié)點(diǎn)，變相減少錨節(jié)點(diǎn)的布置數(shù)量。本節(jié)將詳細(xì)闡述基于虛擬靜態(tài)錨節(jié)點(diǎn)VSAN的加權(quán)質(zhì)心算法的實(shí)現(xiàn)方法和算法流程。

2.1 增設(shè)VSAN的實(shí)現(xiàn)方法

加權(quán)質(zhì)心算法的計(jì)算過(guò)程需要獲取兩部分信息，即各個(gè)錨節(jié)點(diǎn)的位置坐標(biāo)和未知節(jié)點(diǎn)到各個(gè)錨節(jié)點(diǎn)的相應(yīng)距離值［13］。因此，只要獲得了某個(gè)錨節(jié)點(diǎn)的位置坐標(biāo)以及未知節(jié)點(diǎn)到該錨節(jié)點(diǎn)的距離值，就等價(jià)于在物理空間布置了該錨節(jié)點(diǎn)并實(shí)現(xiàn)了該錨節(jié)點(diǎn)和未知節(jié)點(diǎn)之間的通信，而該錨節(jié)點(diǎn)并不一定是真實(shí)存在的。我們將具有這樣功能的“節(jié)點(diǎn)”稱之為虛擬靜態(tài)錨節(jié)點(diǎn)VSAN(Virtual Static Anchor Node)。

基于VSAN的加權(quán)質(zhì)心算法的核心思想是在定位區(qū)域布置少量真實(shí)的錨節(jié)點(diǎn)作為前提，通過(guò)間接方法獲得虛擬靜態(tài)錨節(jié)點(diǎn)的上述兩種信息。虛擬靜態(tài)錨節(jié)點(diǎn)的位置必須位于連接任意兩個(gè)真實(shí)錨節(jié)點(diǎn)的直線上。未知節(jié)點(diǎn)到虛擬靜態(tài)錨節(jié)點(diǎn)的距離值的獲得主要由余弦定理計(jì)算完成。以在定位邊界中點(diǎn)增加四個(gè)虛擬靜態(tài)錨節(jié)點(diǎn)為例，原理圖如圖2所示。

圖2 虛擬靜態(tài)錨節(jié)點(diǎn)構(gòu)造原理圖

圖2中，L1×L2的矩形平面代表定位區(qū)域，黑色信號(hào)發(fā)射源{B1，B2，B3B4}代表真實(shí)布置的錨節(jié)點(diǎn)，位置坐標(biāo)已知;白色信號(hào)發(fā)射源{B5，B6，B7，B8}代表在該位置增設(shè)相應(yīng)的虛擬靜態(tài)錨節(jié)點(diǎn);灰色標(biāo)志物表示未知節(jié)點(diǎn);{d1，d2，d3，d4}分別代表未知節(jié)點(diǎn)分別到四個(gè)真實(shí)錨節(jié)點(diǎn)的距離值，是根據(jù)式(2)求得，在圖中用黑色實(shí)線表示;{d5，d6，d7，d8}則代表未知節(jié)點(diǎn)到四個(gè)虛擬靜態(tài)錨節(jié)點(diǎn)的距離值，是利用{d1，d2，d3，d4}及真實(shí)錨節(jié)點(diǎn)的坐標(biāo)值由余弦定理計(jì)算得出，在上圖中用虛線表示;{α，β，θ}為上圖中邊集合{d1，d2，L1}組成的三角形的內(nèi)角集合;Lx為圖中矩形框左邊界虛擬靜態(tài)錨節(jié)點(diǎn)到矩形框上邊界的距離值。根據(jù)上圖2以及余弦定理，可得:

聯(lián)立式(11)、式(12)可解得:

這里以虛擬靜態(tài)錨節(jié)點(diǎn)布置在定位區(qū)域邊界中點(diǎn)處為例，即Lx=L1/2

同樣方法，可獲得其他幾個(gè)虛擬靜態(tài)錨節(jié)點(diǎn)的坐標(biāo)和到未知節(jié)點(diǎn)的相應(yīng)距離值。

必須提及的是，虛擬靜態(tài)錨節(jié)點(diǎn)到未知節(jié)點(diǎn)的距離計(jì)算結(jié)果與兩者之間的實(shí)際距離同樣是有誤差的，但不代表該信息不是有用信息(實(shí)際布置的參考錨節(jié)點(diǎn)測(cè)距信息也同樣包含誤差，從測(cè)距結(jié)果是否包含誤差這一點(diǎn)來(lái)說(shuō)，實(shí)際布置的錨節(jié)點(diǎn)和虛擬錨節(jié)點(diǎn)是等效的)。事實(shí)上，每增加一個(gè)虛擬錨節(jié)點(diǎn)，便會(huì)增加一條信息，即該虛擬錨節(jié)點(diǎn)到未知節(jié)點(diǎn)的距離值。即便這個(gè)距離值是不準(zhǔn)確的(測(cè)距值也不可能準(zhǔn)確)，它對(duì)確定一個(gè)未知節(jié)點(diǎn)的位置也是有益的，因?yàn)樗梢詫⑽粗?jié)點(diǎn)位置確定在以虛擬錨節(jié)點(diǎn)為中心的一個(gè)大致范圍內(nèi)，當(dāng)虛擬錨節(jié)點(diǎn)較多時(shí)，這些區(qū)域的重疊部分就是未知節(jié)點(diǎn)位置可能性較大的區(qū)域，這也是APIT定位算法的思想。進(jìn)一步講，從上節(jié)的數(shù)學(xué)分析可知，在加權(quán)質(zhì)心算法中對(duì)定位精度影響最大的是距離未知節(jié)點(diǎn)最近的錨節(jié)點(diǎn)，且該錨節(jié)點(diǎn)距離未知節(jié)點(diǎn)越近，加權(quán)質(zhì)心定位算法越容易得到較精確的定位結(jié)果。而在本文中構(gòu)造了若干個(gè)虛擬靜態(tài)錨節(jié)點(diǎn)，相當(dāng)于增加了定位區(qū)域內(nèi)的參考錨節(jié)點(diǎn)，使未知節(jié)點(diǎn)很容易找到一個(gè)距離自己“相對(duì)較近”的最近錨節(jié)點(diǎn)，而該錨節(jié)點(diǎn)擁有較大的加權(quán)權(quán)重，可以將未知節(jié)點(diǎn)的定位位置大致確定在該錨節(jié)點(diǎn)自身附近，即便考慮到誤差的因素，該錨節(jié)點(diǎn)的信息仍能使未知節(jié)點(diǎn)的定位更加準(zhǔn)確。

2.2 算法流程

增加了獲取虛擬靜態(tài)錨節(jié)點(diǎn)信息的環(huán)節(jié)，改進(jìn)后的算法流程具體步驟如下:

步驟1:錨節(jié)點(diǎn)周期性地向定位區(qū)域發(fā)送有關(guān)自身的信息，包括:節(jié)點(diǎn)ID、自身位置坐標(biāo)。

步驟2:未知節(jié)點(diǎn)接受錨節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包，并對(duì)數(shù)據(jù)包進(jìn)行解析和處理:建立錨節(jié)點(diǎn)集合{B1，B2，B3B4};由式(2)將 RSSI轉(zhuǎn)化為距離，建立未知節(jié)點(diǎn)到相應(yīng)錨節(jié)點(diǎn)的距離值集合{d1，d2，d3，d4}。

步驟3:由式(13)和錨節(jié)點(diǎn)集合{B1，B2，B3B4}得到合適的虛擬靜態(tài)錨節(jié)點(diǎn)集合{B5，B6，…，BN};由式(13)得到未知節(jié)點(diǎn)到虛擬靜態(tài)錨節(jié)點(diǎn)的相應(yīng)距離值集合{d5，d6，…，dN}。

步驟4:由上面兩步建立擴(kuò)展后的錨節(jié)點(diǎn)集合{B1，B2，B3，B4，B5，B6，…，BN}和未知節(jié)點(diǎn)到相應(yīng)錨節(jié)點(diǎn)的距離值集合{d1，d2，d3，d4，d5，d6，…，dN}。利用上述兩個(gè)擴(kuò)展后的集合信息，由式(3)和式(4)計(jì)算出未知節(jié)點(diǎn)位置坐標(biāo)。

3 仿真及實(shí)驗(yàn)

3.1 VSAN算法仿真

3.1.1 仿真環(huán)境設(shè)置

為了驗(yàn)證本文算法的有效性，首先在MATLAB環(huán)境中進(jìn)行仿真實(shí)驗(yàn)。為了更貼近實(shí)際環(huán)境，在測(cè)試中我們?cè)O(shè)置仿真區(qū)域?yàn)?0 m×20 m大小的平面區(qū)域，并將四個(gè)錨節(jié)點(diǎn)放置在該區(qū)域的四個(gè)頂點(diǎn)處;在定位區(qū)域內(nèi)劃分1 m×1 m的網(wǎng)格，并將待定位的未知節(jié)點(diǎn)布置在網(wǎng)格連接點(diǎn)處，由此得到21×21總計(jì)441個(gè)未知節(jié)點(diǎn)使其能夠密集覆蓋整個(gè)待定位區(qū)域。假設(shè)未知節(jié)點(diǎn)的通信半徑R=30 m，故在該仿真區(qū)域內(nèi)不存在未知節(jié)點(diǎn)接收不到錨節(jié)點(diǎn)信息的現(xiàn)象。對(duì)于式(1)和式(2)表示的RSSI測(cè)距模型，為了盡可能的模擬真實(shí)環(huán)境，模型參數(shù)取如下數(shù)值:Pr=0 dBm，d0=1 m，β=2，Xσ=(0，4)，權(quán)重系數(shù)n在1～4之間取值。

3.1.2 仿真方案及結(jié)果

根據(jù)“增設(shè)”虛擬靜態(tài)錨節(jié)點(diǎn)數(shù)量和布置位置的異同，設(shè)計(jì)4種不同的方案對(duì)比驗(yàn)證算法的有效性，分別是:“增設(shè)”0個(gè)虛擬靜態(tài)錨節(jié)點(diǎn)、“增設(shè)”4個(gè)虛擬靜態(tài)錨節(jié)點(diǎn){B5，B6，B7，B8}、“增設(shè)”12 個(gè)虛擬靜態(tài)錨節(jié)點(diǎn){B5，B6，…，B15，B16}、“增設(shè)”17 個(gè)虛擬靜態(tài)錨節(jié)點(diǎn){B5，B6，…，B20，B21}。每一種方案相對(duì)應(yīng)的算法分別簡(jiǎn)稱為:0-VSAN算法、4-VSAN算法、12-VSAN算法、17-VSAN算法。虛擬靜態(tài)錨節(jié)點(diǎn)的具體布置如圖3所示。

圖3 虛擬靜態(tài)錨節(jié)點(diǎn)的布點(diǎn)方案

在上述布置方案中，人為的將定位區(qū)域劃分為中心地帶和邊緣地帶，如圖3所示線條圍成的區(qū)域劃為中心地帶{4≤x≤16，4≤y≤16}，其余區(qū)域?yàn)檫吘壍貛А７謩e對(duì)上述4種方案做了多次重復(fù)仿真實(shí)驗(yàn)，每種方案對(duì)應(yīng)若干個(gè)不同的權(quán)重系數(shù)值做仿真實(shí)驗(yàn)，每組計(jì)算441個(gè)(邊緣區(qū)域272個(gè)，中心區(qū)域169個(gè))未知節(jié)點(diǎn)定位誤差信息，取十組平均值作為最后結(jié)果。在驗(yàn)證VSAN算法是否能有效提高定位精度的同時(shí)，觀察權(quán)重系數(shù)n值的變化對(duì)加權(quán)質(zhì)心算法定位結(jié)果造成的影響，包括對(duì)區(qū)域整體定位誤差的影響、中心地帶定位誤差的影響、邊緣地帶定位誤差的影響。仿真結(jié)果如圖4、圖5所示。

圖4 不同n值下的整體定位誤差曲線

圖5 VSAN算法

根據(jù)仿真數(shù)據(jù)建立實(shí)驗(yàn)數(shù)據(jù)如表1所示。進(jìn)一步研究基于VSAN的加權(quán)質(zhì)心算法在同一權(quán)重系數(shù)下，定位區(qū)域中心地帶和邊緣地帶的定位特性，4種VSAN算法在不同區(qū)域得到的仿真圖如圖5所示。

表1 VSAN算法仿真數(shù)據(jù)

根據(jù)仿真數(shù)據(jù)建立實(shí)驗(yàn)數(shù)據(jù)如表2所示。

表2 VSAN算法在不同區(qū)域的仿真數(shù)據(jù)

3.1.3 仿真結(jié)果分析

由表2可知，0-VSAN算法在n=1.8時(shí)定位效果最好，誤差為2.01 m;4-VSAN算法在n=2.3時(shí)定位效果最好，誤差為1.68 m;12-VSAN算法在n=2.6時(shí)定位效果最好，誤差為1.60 m;17-VSAN算法在n=3.2時(shí)定位效果最好，誤差為1.55 m。3種“增設(shè)”了虛擬靜態(tài)錨節(jié)點(diǎn)的算法定位誤差相比0-VSAN 算法分別降低了 0.33 m、0.41 m、0.46 m，精度分別提高了 16.4%、20.4%、23.4%。說(shuō)明本文提出的算法能夠在不增加錨節(jié)點(diǎn)數(shù)量的前提下，達(dá)到實(shí)現(xiàn)提高定位精度的目標(biāo)。

上述4種算法在中心地帶能夠取得的最小的定位誤差分別為 1.47 m、1.53 m、1.48 m、1.43 m，定位誤差差別很小?！霸鲈O(shè)”虛擬靜態(tài)錨節(jié)點(diǎn)對(duì)中心地帶定位效果影響甚微。

上述4種算法在邊緣地帶能夠取得的最小的定位誤差分別為 2.35 m、1.75 m、1.51 m 和 1.61 m。4-VSAN算法、12-VSAN算法、17-VSAN算法相比0-VSAN算法在邊緣地帶的定位誤差分別減少了0.60 m、0.84 m 和0.74 m。由此可見(jiàn)，基于虛擬靜態(tài)錨節(jié)點(diǎn)的改進(jìn)定位算法實(shí)際上提高的是邊緣地帶的定位精度。

如表1所示，虛擬靜態(tài)錨節(jié)點(diǎn)越多，定位精度越高，但每次的增幅卻在逐漸減小。如圖4所示，4-VSAN算法的定位誤差相較于0-VSAN降低了0.33 m，12-VSAN算法相較于4-VSAN的定位誤差只降低了0.08 m，17-VSAN算法相較于12-VSAN定位誤差只降低了0.05 m?？梢灶A(yù)計(jì)，“增設(shè)”更多的虛擬靜態(tài)錨節(jié)點(diǎn)對(duì)定位精度的提高作用會(huì)越來(lái)越小，故對(duì)這種情況不再繼續(xù)研究。

3.1.4 權(quán)重系數(shù)特性分析

觀察圖5及表2可以總結(jié)出，隨著“增設(shè)”虛擬靜態(tài)錨節(jié)點(diǎn)數(shù)量的增多，VSAN定位算法權(quán)重系數(shù)的特性有一定的變化規(guī)律:①虛擬靜態(tài)錨節(jié)點(diǎn)越多，對(duì)應(yīng)算法的最優(yōu)權(quán)重系數(shù)n越大。0-VSAN對(duì)應(yīng)最優(yōu)n值為1.8，4-VSAN 最優(yōu) n 值為 2.3，12-VSAN 最優(yōu) n 值為2.6，17-VSAN對(duì)應(yīng)的最優(yōu)n值為3.2，這種對(duì)應(yīng)的變化趨勢(shì)絕對(duì)偶然。我們可以利用本文證明的式(6)～式(9)推導(dǎo)出的結(jié)論加以解釋:“增設(shè)”了虛擬靜態(tài)錨節(jié)點(diǎn)后，總的錨節(jié)點(diǎn)數(shù)量N變大，在權(quán)重系數(shù)n值不變的情況下，式(6)中分母變大、分子不變，結(jié)果是Pi，j(x，y)變小。由前文可知，對(duì)于距離未知節(jié)點(diǎn)最近的錨節(jié)點(diǎn)Bk(x，y)對(duì)最終定位結(jié)果Pi(x，y)的影響最大，所以Pi，k(x，y)的減小使得在原有最優(yōu)權(quán)重系數(shù)n不變的情況下得不到最優(yōu)的定位效果。根據(jù)式(8)和式(9)，可行的調(diào)整方法就是增大權(quán)重系數(shù)n的值，使得 Pi，k(x，y)變大，Pi，m(x，y)變小，從而再次改善定位效果。逐漸增大n值，當(dāng)定位誤差最小時(shí)便可確定此時(shí)對(duì)應(yīng)的n值為最優(yōu)權(quán)重系數(shù)，繼續(xù)增大n值，定位誤差反而會(huì)增大。②由表2可得到上述4種方案一個(gè)共同點(diǎn):邊緣地帶對(duì)應(yīng)的最優(yōu)權(quán)重系數(shù)n總是大于中心地帶對(duì)應(yīng)的最優(yōu)權(quán)重系數(shù)n。這種現(xiàn)象仍然可以由式(6)～式(9)來(lái)解釋:邊緣地帶為了取得較好的定位效果，就要相對(duì)性的增大n值，確保距離未知節(jié)點(diǎn)最近的錨節(jié)點(diǎn)能獲得足夠大的權(quán)重;而在中心地帶，各個(gè)錨節(jié)點(diǎn)到未知節(jié)點(diǎn)之間的距離差距不大，如果n值較大，就會(huì)使本來(lái)較小的距離差距過(guò)度放大，導(dǎo)致定位位置過(guò)于趨進(jìn)錨節(jié)點(diǎn)Bk(x，y)，中心地帶的未知節(jié)點(diǎn)就可能因此被定位在邊緣區(qū)域。

因此，對(duì)基于VSAN的加權(quán)質(zhì)心算法進(jìn)行下一步改進(jìn)的思路是在定位區(qū)域中心地帶和邊緣地帶分別對(duì)應(yīng)各自的最優(yōu)權(quán)重系數(shù)進(jìn)行定位計(jì)算。

3.2 VSAN算法實(shí)驗(yàn)

3.2.1 實(shí)驗(yàn)環(huán)境設(shè)置

為驗(yàn)證基于VSAN的定位算法在實(shí)際環(huán)境中的有效性，以12-VSAN算法為例(邊緣地帶定位誤差最小)，采用6個(gè)通信模塊為cc2510的傳感器節(jié)點(diǎn)組成小型無(wú)線傳感器網(wǎng)絡(luò)，用于進(jìn)行室內(nèi)定位實(shí)驗(yàn)。定位區(qū)域限定在重慶大學(xué)主教學(xué)樓裙樓一塊大小為10 m×10 m的平面區(qū)域。4個(gè)傳感器節(jié)點(diǎn)作為已知坐標(biāo)的錨節(jié)點(diǎn)，布置在定位區(qū)域的各個(gè)頂點(diǎn)處;1個(gè)節(jié)點(diǎn)作為待定位的未知節(jié)點(diǎn)，布置在定位區(qū)域內(nèi)某一點(diǎn)進(jìn)行定位;另外采用一個(gè)節(jié)點(diǎn)作為Sink節(jié)點(diǎn)與控制后臺(tái)連接，負(fù)責(zé)向錨節(jié)點(diǎn)和未知節(jié)點(diǎn)發(fā)送控制參數(shù)，并將未知節(jié)點(diǎn)定位信息通過(guò)串口線送到控制后臺(tái)進(jìn)行處理。實(shí)驗(yàn)步驟參見(jiàn)上節(jié)算法流程。錨節(jié)點(diǎn)的坐標(biāo)分別預(yù)設(shè)為 B1(0.0，0.0)、B2(0.0，10.0)、B3(10.0，10.0)、B4(10.0，0.0)。定位過(guò)程中每一組定位數(shù)據(jù)用0-VSAN和12-VSAN兩種算法分別計(jì)算定位坐標(biāo)。0-VSAN算法權(quán)重系數(shù)取值為1.8，12-VSAN算法權(quán)重系數(shù)取值為2.6，具體布置如圖6所示。

圖6 現(xiàn)場(chǎng)實(shí)驗(yàn)布置

3.2.2 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)數(shù)據(jù)經(jīng)統(tǒng)計(jì)后整理成表4和表5所示。

實(shí)驗(yàn)得到的12-VSAN算法的平均定位誤差是1.65 m，略大于仿真得到的平均定位誤差1.60 m;0-VSAN算法計(jì)算所得平均定位誤差為2.16 m，略大于仿真得到的定位誤差2.01 m。對(duì)此的解釋是:定位區(qū)域越大，定位誤差也就越大。考慮到仿真環(huán)節(jié)定位區(qū)域較大，實(shí)驗(yàn)環(huán)節(jié)定位區(qū)域較小，所以仿真結(jié)果和實(shí)驗(yàn)結(jié)果接近也是合理的。12-VSAN算法的平均定位誤差相較于0-VSAN算法減小了0.51 m。再一次說(shuō)明了基于VSAN的加權(quán)質(zhì)心定位算法的有效性。

涉及的相關(guān)定位算法比較如表6所示。

表4 0-VSAN算法實(shí)驗(yàn)數(shù)據(jù)

表5 12-VSAN算法實(shí)驗(yàn)數(shù)據(jù)

表6 算法比較

4 總結(jié)

本文結(jié)合余弦定理，利用原有的錨節(jié)點(diǎn)定位信息構(gòu)造出虛擬靜態(tài)錨節(jié)點(diǎn)VSAN參與定位。該算法繼承了加權(quán)質(zhì)心算法實(shí)現(xiàn)簡(jiǎn)單、復(fù)雜程度低的特點(diǎn)，在不增加錨節(jié)點(diǎn)布置數(shù)量的前提下提高了加權(quán)質(zhì)心算法的定位精度，在一定程度上解決了以往由于硬件成本過(guò)高而使得加權(quán)質(zhì)心定位算法難以在實(shí)際中應(yīng)用的難題。此外，對(duì)加權(quán)質(zhì)心算法進(jìn)行數(shù)學(xué)推導(dǎo)和分析，從導(dǎo)數(shù)的角度闡述了權(quán)重系數(shù)和RSSI測(cè)距對(duì)加權(quán)質(zhì)心算法的影響作用。仿真和實(shí)驗(yàn)結(jié)果表明，基于VSAN的加權(quán)質(zhì)心算法所需布置錨節(jié)點(diǎn)較少、定位精度較高，完全能夠應(yīng)用在工程實(shí)踐中。下一步的改進(jìn)思路是在定位區(qū)域中心地帶和邊緣地帶分別對(duì)應(yīng)各自的最優(yōu)權(quán)重系數(shù)進(jìn)行定位計(jì)算。

參考文獻(xiàn):

［1］吳曉平，談士力，胡軍國(guó).基于殘差修正法的無(wú)線傳感器網(wǎng)絡(luò)定位技術(shù)［J］.傳感技術(shù)學(xué)報(bào)，2012，25(7):1014－1018.

［2］鄧彬偉，黃光明.無(wú)線傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)輔助定位算法［J］.儀器儀表學(xué)報(bào)，2011，32(3):563－570.

［3］Rudafshni M，Datta S.Localization in Wireless Sensor Networks［C］//Information Processing in Sensor Networks(IPSN)，2007:51－60.

［4］Bahl P，Padmanabhan V N.RADAR:An in Building RF-Based User Location and Tracking System［C］//Proceedings of the IEEE Infocom 2000.Tel Aviv:IEEE Computer and Communications Societies，2000.775－784.

［5］Yi Shang，Ruml W，Ying Zhang.Localization from Mere Connectivity［C］//Mob Hoc’03，Annapolis，Maryland，USA，2003:201－210..

［6］李牧東，熊偉，梁青.基于人工蜂群改進(jìn)算法的無(wú)線傳感器網(wǎng)絡(luò)定位算法［J］.傳感技術(shù)學(xué)報(bào)，2013，26(2):241－245.

［7］王焱，單欣欣，姜偉.無(wú)線傳感網(wǎng)絡(luò)中移動(dòng)節(jié)點(diǎn)定位技術(shù)研究［J］.傳感技術(shù)學(xué)報(bào)，2011，24(9):1326－1330.

［8］許磊，石為人.一種無(wú)線傳感器網(wǎng)絡(luò)分步求精節(jié)點(diǎn)定位算法［J］.儀器儀表學(xué)報(bào)，2008，29(2):314－319.

［9］Alippi C，Vanini G.Wireless Sensor Networks and Radio Localization:A Metrological Analysis of the MICA2 Received Signal Strength Indicator［C］//Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks(LCN’04)，Italy，2004:16－18.

［10］Yi Shang，Ruml W，Ying Zhang.Localization from Mere Connectivity［C］//Mob Hoc’03，Annapolis，Maryland，USA，2003:201－210..

［11］陳維克，李文鋒，首珩.基于RSSI的無(wú)線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法［J］.武漢理工大學(xué)學(xué)報(bào)，2006，20(12):2695－2700.

［12］詹杰，劉宏立，劉述鋼，等.基于RSSI的動(dòng)態(tài)權(quán)重定位算法研究［J］.電子學(xué)報(bào)，2011，39(1):82－88.

［13］Lim C B，Kang S H，Cho H H.An Enhanced Indoor Localization Algorithm Based on IEEE 802.11 WLAN Using RSSI and Multiple Parameters［C］//2010 Fifth International Conference on Systems and Networks Communications.2010:238－242.