周成綱，饒國勇

(1.紹興職業(yè)技術(shù)學(xué)院,浙江 紹興 312000； 2.景德鎮(zhèn)學(xué)院 信息工程系，江西 景德鎮(zhèn) 333000)

?

基于改進(jìn)的質(zhì)心定位的LSSVR算法的設(shè)計(jì)

周成綱1，饒國勇2

(1.紹興職業(yè)技術(shù)學(xué)院,浙江 紹興 312000； 2.景德鎮(zhèn)學(xué)院 信息工程系，江西 景德鎮(zhèn) 333000)

針對無線傳感中基于質(zhì)心算法的節(jié)點(diǎn)定位存在誤差比較大,算法效率低的缺點(diǎn),提出了一種基于加權(quán)的LSSVR的節(jié)點(diǎn)定位算法；首先,對未知節(jié)點(diǎn)構(gòu)建節(jié)點(diǎn)序列相關(guān)度,采用Kendall的Tau指標(biāo)來估計(jì)未知節(jié)點(diǎn)的位置,提高了未知節(jié)點(diǎn)的定位精度,其次引入了LSSVR概念,構(gòu)建改進(jìn)質(zhì)心算法的LSSVR定位模型,降低了噪聲影響,大幅度提高定位精度；仿真實(shí)驗(yàn)表明該算法與基本的LSSVR算法在定位精度上有了明顯的提高,在錨節(jié)點(diǎn),未知節(jié)點(diǎn)所占比例不斷增大的情況下該算法定位精度具有很大的提高,降低了算法的計(jì)算復(fù)雜度,具有較高的應(yīng)用價(jià)值。

無線傳感; 序列相關(guān)度; LSSVR; 節(jié)點(diǎn)定位

0 引言

節(jié)點(diǎn)定位一直以來都是無線傳感網(wǎng)中的研究熱點(diǎn),主要包括兩個(gè)方面:距離有關(guān)定位算法和距離無關(guān)定位算法。前者主要依靠錨節(jié)點(diǎn)和未知節(jié)點(diǎn)之間直接距離進(jìn)行定位，后者是通過節(jié)點(diǎn)的估算來進(jìn)行定位,其中質(zhì)心算法是一種計(jì)算簡單,消耗硬件能量低的距離無關(guān)定位算法,其缺點(diǎn)是定位誤差比較大[1],楊新宇[2]提出了一種利用信號強(qiáng)度比值的加權(quán)質(zhì)心定位算法.其定位精度可提高5.12%～11.23%;趙棟棟[3]提出了根據(jù)跳數(shù)對錨節(jié)點(diǎn)組成的三角形多次求解質(zhì)心,取得了比較好的定位效果;呂振[4]提出利用了信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)之間距離的倒數(shù)之和作為信標(biāo)節(jié)點(diǎn)的權(quán)值來實(shí)現(xiàn)對未知節(jié)點(diǎn)的定位；劉玉軍[5]提出多信標(biāo)節(jié)點(diǎn)質(zhì)心定位修正算法,通過該算法計(jì)算得到多組未知節(jié)點(diǎn)估計(jì)坐標(biāo),并在此基礎(chǔ)上利用質(zhì)心定位修正算法計(jì)算節(jié)點(diǎn)坐標(biāo)修正值; 施偉[6]提出一種基于接收信號強(qiáng)度(RSSI)的改進(jìn)加權(quán)質(zhì)心定位算法;王緩緩[7]提出用初次質(zhì)心定位結(jié)果來取代未知節(jié)點(diǎn)通信半徑內(nèi)距未知節(jié)點(diǎn)最遠(yuǎn)的錨節(jié)點(diǎn),采用二次定位來減小由于錨節(jié)點(diǎn)導(dǎo)致未知節(jié)點(diǎn)的估計(jì)位置的情況;王振朝[8]提出在該算法中采用節(jié)點(diǎn)距離倒數(shù)之和代替距離和的倒數(shù)作為權(quán)值,該算法具有一定的有效性。

本文在質(zhì)心算法上構(gòu)建節(jié)點(diǎn)序列相關(guān)度,通過Tau指標(biāo)來求解未知節(jié)點(diǎn)的估計(jì)位置,其次引入了LSSSVR,構(gòu)建質(zhì)心定位算法的LSSVR定位模型。

1 質(zhì)心定位算法簡述

在無線傳感網(wǎng)質(zhì)心算法中,質(zhì)心是眾多的錨節(jié)點(diǎn)構(gòu)成的多邊形的幾何中心點(diǎn),其值是通過多邊形頂點(diǎn)的坐標(biāo)的平均值。如圖1所示,黑色實(shí)心表示錨節(jié)點(diǎn),空心節(jié)點(diǎn)表示待定位的節(jié)點(diǎn),G為錨節(jié)點(diǎn){A,B,C,D,E}構(gòu)成的質(zhì)心節(jié)點(diǎn)。

圖1 無線傳感網(wǎng)中節(jié)點(diǎn)和質(zhì)心示意圖

選取圖中的5個(gè)錨節(jié)點(diǎn),分別為A(x1,y1),B(x2,y2),C(x3,y3),D(x4,y4),E(x5,y5),這5個(gè)圖的形成的五邊形的質(zhì)心G(x,y)坐標(biāo)為:

(1)

質(zhì)心定位算法的原理:首先通過錨節(jié)點(diǎn)的組成的多邊形的區(qū)域計(jì)算質(zhì)心的坐標(biāo),然后以此來確定未知節(jié)點(diǎn)的位置。假設(shè)在某一段時(shí)間內(nèi),未知節(jié)點(diǎn)探測到與K個(gè)錨節(jié)點(diǎn)進(jìn)行信息通訊,將錨節(jié)點(diǎn)的坐標(biāo)表示為Anchorj(x,y)=(xj,yj),因此未知節(jié)點(diǎn)P(x,y)的坐標(biāo)為:

(2)

從式(2)中可以發(fā)現(xiàn)質(zhì)心算法優(yōu)點(diǎn)是設(shè)計(jì)簡單,容易實(shí)現(xiàn),缺點(diǎn)是未知節(jié)點(diǎn)的定位精度取決與周圍錨節(jié)點(diǎn)的分布密度,當(dāng)錨節(jié)點(diǎn)結(jié)構(gòu)均勻分布,則未知節(jié)點(diǎn)自身定位的精度就會越高,反之,則會降低,這說明未知節(jié)點(diǎn)的定位取決于質(zhì)心定位的精度。同時(shí)質(zhì)心算法的定位精度在一定程度上與無線傳感網(wǎng)中的錨節(jié)點(diǎn)數(shù)量有關(guān)。錨節(jié)點(diǎn)數(shù)量所占的比例越大,與未知節(jié)點(diǎn)能夠連通的錨節(jié)點(diǎn)就越多,因此,質(zhì)心算法估計(jì)的位置就越接近未知節(jié)點(diǎn)的真實(shí)位置[9]。文獻(xiàn)[10]提出在錨節(jié)點(diǎn)密度低的區(qū)域增加錨節(jié)點(diǎn)數(shù)量,以此提高定位的精度。

2 改進(jìn)的質(zhì)心定位算法

2.1 節(jié)點(diǎn)間序列相關(guān)度

根據(jù)錨節(jié)點(diǎn)與未知節(jié)點(diǎn)在定位上具有的某種關(guān)系,本文采用Kendall的Tau指標(biāo)來進(jìn)行節(jié)點(diǎn)定位之間的相關(guān)度的說明,設(shè)定兩個(gè)定位序列S={s1,s2,…,sn}和T={t1,t2,…,tn},那么Kendall階次相關(guān)系數(shù)為:

(3)

Kendall的Tau指標(biāo)為:

(4)

其中:

(5)

(6)

(7)

(8)

2.2 序列加權(quán)的節(jié)點(diǎn)定位算法

(1)構(gòu)建質(zhì)心參考節(jié)點(diǎn)。由于未知節(jié)點(diǎn)的定位與多個(gè)錨節(jié)點(diǎn)的坐標(biāo)所構(gòu)成的質(zhì)心節(jié)點(diǎn)的定位有關(guān),因此,將錨節(jié)點(diǎn)組成的多邊形劃的頂點(diǎn)存儲在某一個(gè)數(shù)據(jù)數(shù)組中,整個(gè)數(shù)組記為質(zhì)心參考點(diǎn)。

(2)參考點(diǎn)序列的建立。首先根據(jù)式(9)求出每一個(gè)多邊形的質(zhì)心參考坐標(biāo)(ηx,ηy),確定質(zhì)心參考點(diǎn)的定位序列。

(9)

(3)未知節(jié)點(diǎn)的定位序列構(gòu)建。通過與錨節(jié)點(diǎn)的距離遠(yuǎn)近得到未知節(jié)點(diǎn)的定位序列。在圖2中,(U1,U2,U3,U4)分別代表未知節(jié)點(diǎn),(A,B,C,D,E)分別代表錨節(jié)點(diǎn),每一個(gè)未知節(jié)點(diǎn)序列為Ui(X/y)中的X表示接收到來自各個(gè)錨節(jié)點(diǎn)的信號的次序,y表示未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間的距離,因此可以得到未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的序列等級。

圖2 未知節(jié)點(diǎn)序列構(gòu)建

(4)未知節(jié)點(diǎn)位置估計(jì)。未知節(jié)點(diǎn)通過序列S按照式(4)計(jì)算階數(shù)序列表T={T1,T2,…Tk}中所有序列的相關(guān)度,構(gòu)成每一個(gè)序列的集合(TN)。通過相關(guān)度在[-1,1]區(qū)間變換后的值作為權(quán)重,通過參考節(jié)點(diǎn)η進(jìn)行加權(quán)估算未知節(jié)點(diǎn)(x,y)的位置為:

(10)

3 基于質(zhì)心定位的LSSSVR的定位算法

3.1 LSSVR誤差分析

在理想的LSSVR模型中輸入的樣本是沒有噪聲干擾,因此得到的輸出樣本是也是非常精確的。但在實(shí)際環(huán)境中,LSSVR通過少量的訓(xùn)練樣本來獲得反應(yīng)未知節(jié)點(diǎn)的目標(biāo)定位的映射關(guān)系,由于噪聲的影響,LSSVR模型的輸入就存在一定的誤差,因此基于LSSVR的定位算法的誤差反映了模型的預(yù)測能力,誤差越小,精度就越高。

3.2 基于質(zhì)心定位的LSSVR模型的建立

為了進(jìn)一步降低誤差,本文在LSSVR模型上,改進(jìn)訓(xùn)練學(xué)習(xí)過程,將網(wǎng)格進(jìn)行劃分,以一定的步長來構(gòu)建以未知節(jié)點(diǎn)為中心的參考節(jié)點(diǎn)的密度,從而提高LSSVR模型的定位精度。通過公式(10)獲得未知節(jié)點(diǎn)的大概位置以及相應(yīng)的網(wǎng)格節(jié)點(diǎn)形成的訓(xùn)練樣本。模型建立步驟如下,流程如圖3所示。

4)定位模型的獲得: 將訓(xùn)練樣本Ux和Uy作為定位模型的輸入,獲得相應(yīng)的訓(xùn)練樣本的定位模型X-LSSVR,Y-LSSVR。

5)未知節(jié)點(diǎn)樣本:將校正后的未知節(jié)點(diǎn)S與錨節(jié)點(diǎn)Mi(i=1,2,…m)之間距離di,組成距離向量w=(d1,d2,…dM)。

6)未知節(jié)點(diǎn)定位:將距離向量w輸入到定位模型中,分別計(jì)算輸出值(x′,y′)。

圖3 基于改進(jìn)的質(zhì)心定位算法的LSSVR定位模型

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

本文選擇本實(shí)驗(yàn)選取100 m*100 m的空曠區(qū)域,選取30個(gè)節(jié)點(diǎn),其中10個(gè)節(jié)點(diǎn)為錨節(jié)點(diǎn),剩余的20個(gè)為未知節(jié)點(diǎn)。搭建計(jì)算機(jī)硬件平臺CPU為酷睿i3,4GDDR,500 G,軟件平臺采用Matable2010。為了進(jìn)一步驗(yàn)證本文算法具有的優(yōu)越性,將本文的算法與其他的質(zhì)心定位算法進(jìn)行比較。圖4為本文算法的定位效果。從圖中可以發(fā)現(xiàn)本文算法下的定位的精度有了明顯的提高,位置節(jié)點(diǎn)的實(shí)際未知與計(jì)算位置平均相差不大,有1～2個(gè)節(jié)點(diǎn)的出現(xiàn)的偏差不大,適合在多節(jié)點(diǎn)情況下的無線傳感節(jié)點(diǎn)定位中的應(yīng)用。

圖4 本文算法定位仿真效果

4.1 與基本的LSSVR定位算法相比

將本文的算法與基本的LSSVR算法通過50次的蒙特卡洛計(jì)算,得到的結(jié)果如圖5所示,從圖中可以發(fā)現(xiàn)本文算法的平均誤差范圍在5.14%～8.27%,而基本的LSSVR算法的平均誤差范圍在8.18%～12.03%。本文算法相比與基本的LSSVR算法相比定位精度提高了15.29%～24.31%。這說明本文的算法在定位誤差方面具有更高的穩(wěn)定性和可靠性。

圖5 兩種算法的定位誤差比較

由于質(zhì)心定位過程中存在步長選擇和路徑損失兩個(gè)因素的影響,因此本文算法與基本LSSVR算法在這兩個(gè)方面進(jìn)行了對比,對比結(jié)果如表1～2所示。從表1中發(fā)現(xiàn),本文算法伴隨著步長的增加對定位誤差的影響小于基本的算法,這說明在條件允許的情況下步長的增加能夠提高訓(xùn)練網(wǎng)格的精度,從而能夠提高未知節(jié)點(diǎn)定位精度。從表2中發(fā)現(xiàn)伴隨著路徑損耗系數(shù)的增大,本文算法的定位誤差精度小于基本LSSVR算法平均3%,隨著路徑損失越大,定位誤差精度只差越明顯,這說明在同樣的路徑損耗下本文算法優(yōu)于基本LSSVR算法。

表1 步長對兩種算法定位誤差的影響

表2 路徑損失對兩種算法定位誤差的影響

4.2 與其他定位算法的比較

將本文算法與最新的誤差定位方面的算法進(jìn)行比較,通過與文獻(xiàn)[5],文獻(xiàn)[6]算法的比較來進(jìn)一步說明本文算法的優(yōu)點(diǎn)。

1)未知節(jié)點(diǎn)比例變化的定位誤差比較：

假定總節(jié)點(diǎn)的數(shù)目保持不變,伴隨著未知節(jié)點(diǎn)個(gè)數(shù)逐漸增多,本文算法,文獻(xiàn)[5]算法和文獻(xiàn)[6]算法的定位誤差變化曲線如圖6所示。從圖中得到,本文算法在未知節(jié)點(diǎn)數(shù)目相對較少的時(shí)候,定位誤差小于文獻(xiàn)[5]和文獻(xiàn)[6]算法,這主要是因?yàn)殡A次加權(quán)的過程中,構(gòu)建了參考節(jié)點(diǎn),導(dǎo)致誤差下降,伴隨著節(jié)點(diǎn)數(shù)目逐漸增多,本文算法的優(yōu)勢逐漸體現(xiàn)出來,即平均定位誤差明顯小于其他兩種算法。

圖6 不同未知節(jié)點(diǎn)數(shù)目下的3種算法定位誤差2)錨節(jié)點(diǎn)數(shù)目比例變化的定位性能比較：

假設(shè)總節(jié)點(diǎn)的個(gè)數(shù)不變,伴隨著錨節(jié)點(diǎn)個(gè)數(shù)的比率不斷變化, 本文算法,文獻(xiàn)[5]算法和文獻(xiàn)[6]算法的定位誤差變化曲線如圖7所示。從圖中發(fā)現(xiàn),3種算法在錨數(shù)目比較少的時(shí)候相差不是很大,這說明3種算法都能適合錨節(jié)點(diǎn)數(shù)目少的時(shí)候,但伴隨著錨節(jié)點(diǎn)的數(shù)目增多,3種算法的誤差逐漸拉大,文獻(xiàn)[5]和文獻(xiàn)[6]的算法圖像波動比較大,而本文算法的圖像平緩,這說明本文算法收到錨節(jié)點(diǎn)數(shù)量的影響不大。

圖7 不同錨節(jié)點(diǎn)個(gè)數(shù)的3種算法定位性能

5 結(jié)束語

針對無線傳感定位中的質(zhì)心定位算法存在的不足,首先采用了序列加權(quán)的概念對未知節(jié)點(diǎn)的定位方法進(jìn)行了改進(jìn),其次,引入LSSVR概念對改進(jìn)后的節(jié)點(diǎn)定位的精度進(jìn)一步改進(jìn)。仿真實(shí)驗(yàn)說明本文算法與基本的LSSVR算法相比誤差明顯減低,通過與其他算法在錨節(jié)點(diǎn),未知節(jié)點(diǎn)比例方面的定位誤差相比有了顯著的降低。

[1] 何艷麗.無線傳感器網(wǎng)絡(luò)質(zhì)心定位算法研究[J].計(jì)算機(jī)仿真,2011,28(5):163-166.

[2] 楊新宇,孔慶茹,戴湘軍.一種改進(jìn)的加權(quán)質(zhì)心定位算法[J].西安交通大學(xué)學(xué)報(bào),2010,44(8):1-3.

[3] 趙棟棟,趙菊敏,李燈熬.基于質(zhì)心迭代的DV-Hop定位改進(jìn)算法[J].計(jì)算機(jī)測量與控制,2013,21(10):2764-2766.

[4] 呂 振,趙鵬飛.一種改進(jìn)的無線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法[J].計(jì)算機(jī)測量與控制,2013,21(4):1102-1104.

[5] 劉玉軍,蔡 猛,高立恒.基于RSSI測距的傳感器節(jié)點(diǎn)質(zhì)心定位修正算法[J].計(jì)算機(jī)測量與控制,2014,22(9):2860-2862.

[6] 施 偉,高 軍.無線傳感器網(wǎng)絡(luò)中基于RSSI的改進(jìn)加權(quán)質(zhì)心定位算法[J].計(jì)算機(jī)應(yīng)用與軟件,2015,32(12):68-70.

[7] 王緩緩,邱建文.基于區(qū)域分割的二次質(zhì)心定位算法[J].2015,32(4):279-281.

[8] 王振朝,張 琦,張 峰.基于RSSI測距的改進(jìn)加權(quán)質(zhì)心定位算法[J].電測與儀表,2014,51(21):63-66.

[9] 李兆斌,魏占禎,徐鳳麟,等. 無線傳感器網(wǎng)絡(luò)增強(qiáng)的質(zhì)心定位算法及性能分析[J] .傳感技術(shù)學(xué)報(bào),2009,22 (4):1247-1250.

[10] Bulusu B,Heidemann J, Estrin D. Denstiny adaptive algorithms for beacon placement in wireless sensor networks[A]. In:Proceedings of IEEE ICDES[C]. Mesa, AZ,USA, IEEE Press,2001,489-498.

Design of LSSVR Location Algorithm based on Improved Centroid Location

Zhou Chenggang1,Rao Guoyong2

(1.Shaoxing Vocational&Technical College, Shaoxing 312000,China；2.Jingdezhen University Information technology department,Jingdezhen 333000,China)

Aiming at centroid algorithm’s setback of big errors and low efficiency in node positioning in wireless sensing, a weighted-based LSSVR node positioning algorithm is proposed. First of all, the place of unknown nodes is estimated by establishing node sequence correlation with Kendall’s Tau index, which has improved the positioning accuracy of unknown nodes. Secondly, LSSVR is introduced and LSSVR positioning model of improved centroid location algorithm is constructed to reduce the influence of noise. Simulation experiment shows that compared with basic LSSVR algorithm, this algorithm has significantly improved its positioning accuracy, and with the increasing proportion of anchor nodes and unknown nodes, positioning accuracy of the algorithm has been significantly improved, which has reduced its computational complexity, so this algorithm has relatively high application value.

wireless sensing; serial correlation, LSSVR, node location

2016-03-31；

2016-05-05。

浙江省教育廳科研項(xiàng)目(Y201534919);浙江省訪問學(xué)者項(xiàng)目;浙江省教育技術(shù)研究規(guī)劃課題(JB129)。

周成綱(1977-),男,講師,碩士,主要從事物聯(lián)網(wǎng)應(yīng)用,移動互聯(lián)方向的研究。

饒國勇(1976-)，男，江西省景德鎮(zhèn)市人，副教授，碩士研究生，主要從事物聯(lián)網(wǎng)技術(shù)、云計(jì)算技術(shù)、網(wǎng)絡(luò)安全方向的研究。

1671-4598(2016)09-0224-03

10.16526/j.cnki.11-4762/tp.2016.09.062

TP3

A