基于改進的質心定位的LSSVR算法的設計

周成綱，饒國勇

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

?

基于改進的質心定位的LSSVR算法的設計

周成綱1，饒國勇2

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

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

無線傳感; 序列相關度; LSSVR; 節(jié)點定位

0 引言

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

本文在質心算法上構建節(jié)點序列相關度,通過Tau指標來求解未知節(jié)點的估計位置,其次引入了LSSSVR,構建質心定位算法的LSSVR定位模型。

1 質心定位算法簡述

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

圖1 無線傳感網中節(jié)點和質心示意圖

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

(1)

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

(2)

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

2 改進的質心定位算法

2.1 節(jié)點間序列相關度

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

(3)

Kendall的Tau指標為:

(4)

其中:

(5)

(6)

(7)

(8)

2.2 序列加權的節(jié)點定位算法

(1)構建質心參考節(jié)點。由于未知節(jié)點的定位與多個錨節(jié)點的坐標所構成的質心節(jié)點的定位有關,因此,將錨節(jié)點組成的多邊形劃的頂點存儲在某一個數(shù)據數(shù)組中,整個數(shù)組記為質心參考點。

(2)參考點序列的建立。首先根據式(9)求出每一個多邊形的質心參考坐標(ηx,ηy),確定質心參考點的定位序列。

(9)

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

圖2 未知節(jié)點序列構建

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

(10)

3 基于質心定位的LSSSVR的定位算法

3.1 LSSVR誤差分析

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

3.2 基于質心定位的LSSVR模型的建立

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

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

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

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

圖3 基于改進的質心定位算法的LSSVR定位模型

4 仿真實驗

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

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

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

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

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

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

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

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

4.2 與其他定位算法的比較

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

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

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

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

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

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

5 結束語

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

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

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

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

[4] 呂 振,趙鵬飛.一種改進的無線傳感器網絡加權質心定位算法[J].計算機測量與控制,2013,21(4):1102-1104.

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

[6] 施 偉,高 軍.無線傳感器網絡中基于RSSI的改進加權質心定位算法[J].計算機應用與軟件,2015,32(12):68-70.

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

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

[9] 李兆斌,魏占禎,徐鳳麟,等. 無線傳感器網絡增強的質心定位算法及性能分析[J] .傳感技術學報,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。

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

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

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

1671-4598(2016)09-0224-03

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

TP3

A