李秉鍵, 鄭力明

(1.嘉應(yīng)學(xué)院 計算機學(xué)院, 廣東 梅州 514015; 2.暨南大學(xué) 信息科學(xué)技術(shù)學(xué)院， 廣州 510632)

一種局部模式的RGB差值序列交叉區(qū)域取樣節(jié)點定位算法

李秉鍵1,2, 鄭力明2

(1.嘉應(yīng)學(xué)院 計算機學(xué)院, 廣東 梅州 514015; 2.暨南大學(xué) 信息科學(xué)技術(shù)學(xué)院， 廣州 510632)

鑒于當(dāng)前無線傳感器網(wǎng)絡(luò)(WSN)移動節(jié)點定位技術(shù)中存在的實時性差和定位不準確的問題，設(shè)計了一種交疊區(qū)域采樣模式的WSN移動節(jié)點定位算法OASM_MNL(overlapping area sampling mode of mobile node localization);該算法通過獲取的信號在能夠直接和移動節(jié)點通信的信標節(jié)點的信號交疊區(qū)域里面進行局部采樣；通過距離比例因子對平均跳距進行權(quán)值化，優(yōu)化了CDL中跳距的計算公式；通過RGB差值序列對樣本點濾波，在此基礎(chǔ)上把差值序列絕對值作為加權(quán)標準，計算出移動節(jié)點的坐標;仿真結(jié)果表明，與E-CDL、MCL等常見的移動節(jié)點定位算法相比，新算法定位誤差降低幅度超過33%，定位效果良好。

節(jié)點定位；交疊區(qū)域；局部采樣；RGB差值序列

0 引言

近年來，基于無線傳感器網(wǎng)絡(luò)的移動節(jié)點定位系統(tǒng)逐漸得到普及推廣，在諸多方面發(fā)揮出重要的作用，例如在監(jiān)測動物、監(jiān)護患者等方面[1-2]?，F(xiàn)實生活中，對于節(jié)點來說，其能量與計算能力并非為無限的[3]，同時還面臨諸多噪聲的干擾，正是上述的一系列原因，使得移動定位過程中很難獲得相對較高的精度[4]?，F(xiàn)階段WSN移動節(jié)點定位引起廣大專家學(xué)者的廣泛關(guān)注[5-6]。有學(xué)者[7]在研究過程中闡明了(Monte Carlo Localization,MCL)算法，此后業(yè)界人士設(shè)計出一些優(yōu)化的算法[8]，其中包括MA-MCL[9]，這個方法主要是通過移動輔助節(jié)點來進行處理，MCB[10]構(gòu)建起相應(yīng)的采樣盒子，通過這種方法來使收斂提速，此外還有MSL[11]等。

CDL(color-theory based dynamic localization)方法主要是以非測距為基礎(chǔ)[12]，通過廣播信息構(gòu)建位置數(shù)據(jù)庫，在此基礎(chǔ)上對其中位置點的RGB序列值進行求解。對于MCL類移動節(jié)點定位算法來說，其一方面必須對上述兩方面信息進行傳輸，另一方面也必須對移動節(jié)點的Vmax進行估算，在這里其運動信息并非已知的，正是這方面的原因，這一方面會導(dǎo)致誤差，另一方面還需要較高的運算開銷。而對于CDL法來說，其屬于集中式的，同時非常易于進行，所以在那些具備固定管理中心的情景非常適合。其具有以下幾方面優(yōu)點：計算開銷相對較低，誤差較小[12-13]。對比來說，盡管CDL的精度高于MCL，然而其中依舊存在不足之處[13-14]。這些方法在求解平均跳距的時候，均沒有分析信標節(jié)點在不同信號強度條件下需要分配相應(yīng)的權(quán)值，另一方面位置點區(qū)域相對較大，所以它們的定位精度仍然需要加以改善。

此處，我們基于前人提出的CDL類算法，進行適當(dāng)?shù)膬?yōu)化：(1)優(yōu)化了移動與信標節(jié)點間跳距的求解方程，賦予平均跳距相應(yīng)的權(quán)值，同時還引入距離比例因子，求解獲得的跳距值準確度有所提升，最終使得信標節(jié)點的使用率有所提高。通過實驗我們發(fā)現(xiàn)，通過該算法能夠降低誤差；(2)構(gòu)建實時數(shù)據(jù)庫，具體來說，也就是在任意離散時間間隔t范圍內(nèi)對RGB數(shù)據(jù)庫進行實時更新，這樣能夠充分確保定位的時效性；(3)引入局部采樣濾波理論，通過獲取到的信號，在通信范圍之內(nèi)的信號區(qū)中進行采樣，在很大程度上降低了采樣區(qū)間，同時還從理論方面進行闡述。

1 CDL算法與E-CDL算法關(guān)鍵問題分析

前者主要基于DV-Hop[6]與顏色理論[12-13]，具體來說，通過DV-Hop來進行求解，同時利用RGB與HSV(hue,saturation,value)的經(jīng)典轉(zhuǎn)換法[15]，來求解位置點與移動節(jié)點的RGB序列值，最終完成相應(yīng)的定位工作。在這里，按照顏色理論，各個顏色依次能夠通過用RGB與HSV兩個方面來描述，各個顏色能夠利用紅、綠、藍的融合來實現(xiàn)[12]。圖1展示了以CDL算法為基礎(chǔ)的移動節(jié)點定位示意圖，與大部分WSN移動定位系統(tǒng)大致相當(dāng)[16]，運動的時候，移動節(jié)點接收信標與普通節(jié)點傳輸?shù)奶卣餍盘?，依次求解最小與平均跳距，在此基礎(chǔ)上通過多跳方法把信息運輸至管理中心與匯聚節(jié)點，最終求解出移動節(jié)點的坐標。

(1)

圖1 CDL系統(tǒng)框圖

(2)

(3)

(4)

(5)

(6)

在此基礎(chǔ)上，把位置點的坐標與RGB序列值輸送至database里面，從其中搜索位置點(其和Li具有一樣的RGB序列值)，在此基礎(chǔ)上，定義它的坐標是Li在t時刻的坐標。

E-CDL法主要是基于CDL法而形成的一種方法，在各單位時間內(nèi)使信標節(jié)點任意移動R(通信半徑)，然后求解信標節(jié)點間的真實距離與跳距的比值β，利用這種方式來對路徑進行估計，通過研究發(fā)現(xiàn)，定位過程中在平均跳距為7βR/9時，可以獲得相對偏小的誤差[13]。然而對E-CDL法來說，信標節(jié)點隨機移動的同時還必須獲取其動態(tài)的坐標數(shù)據(jù)，正是這一個方面的原因，使得硬件的要求有所提升，同時很難實現(xiàn)。綜上所述，不管CDL或者E-CDL，兩種方法主要是用來處理優(yōu)化路徑與平均跳距等方面，未曾充分分析通信半徑大小存在差異的信標節(jié)點功能的區(qū)別，尤其是未分析由于位置點分配區(qū)域太高所導(dǎo)致的額外的計算開銷、相對較差的實時性等方面，但是上述環(huán)節(jié)恰恰是決定精度的重要因子。所以，我們在研究過程中通過采樣濾波理論，通過信號來降低采樣區(qū)域，使其精度有所改善，并且還對各種類型的信標節(jié)點依次求解距離因子和平均跳距，在此基礎(chǔ)上實施相應(yīng)的加權(quán)處理，通過這種方法來對移動節(jié)點的跳距進行修正。然后隨時對RGB數(shù)據(jù)庫進行更新，設(shè)置相應(yīng)的閾值，利用這種方式對樣本點進行濾波處理，從而獲得相對準確的坐標信息。

2 優(yōu)化的OASM_MNL算法

2.1 平均跳距的優(yōu)化

CDL主要基于DV-hop法而形成，其存在非常明顯的優(yōu)勢，例如所需要的成本相對較低、非常簡單等，然而需要注意的問題是，其誤差同樣相對偏大。對于DV-hop法來說，關(guān)于整個網(wǎng)絡(luò)里面的平均跳距，其中所有信標節(jié)點依次求解相應(yīng)的平均跳距，在此基礎(chǔ)上通過網(wǎng)絡(luò)進行廣播，Li將最早接到的平均跳距當(dāng)做該數(shù)值[6]。在進行定位的時候，每一信標節(jié)點的網(wǎng)絡(luò)與位置存在差異，單獨通過1個信標節(jié)點根本無法充分體現(xiàn)全網(wǎng)的平均跳距，正是這一個方面的原因，在充分考慮定位精度的基礎(chǔ)上，我們以Li與它t時刻通信半徑范圍內(nèi)的信標節(jié)點間的最小跳數(shù)的倒數(shù)，當(dāng)做其加權(quán)因子，在此基礎(chǔ)上求解t時Li的平均跳距，通過這種方法能夠在很大程度上降低平均跳距誤差偏高者的干擾。

(7)

(8)

(9)

2.2 距離比例因子

此處引入該定義，首先通過β來求解各信標節(jié)點的比例因子p，在此基礎(chǔ)上根據(jù)t時各信標節(jié)點對Li信號強弱的區(qū)別，利用p來對其和移動節(jié)點的跳距求解式進行修正。

(10)

第二步，計算公式(10)得出的全部pkj的均值，Ak求解其pk，具體如下所示：

(11)

(12)

2.3 采樣區(qū)域

(13)

定理1：設(shè)節(jié)點的1跳通信與定位區(qū)域的面積分別是與Q，那么當(dāng)樣本點密度相同時，在這種情況下對比過去的法來說，OASM_MNL的采樣運算量能夠減小倍。接下來，本文將對該定理進行證明，具體步驟如下所示。

假設(shè)OASM_MNL隨機采ω個樣，M*t是1，具有最大的采樣面積，其大小是πR2，這種情況下，具有最低的采樣密度，其大小是2/πR2，傳統(tǒng)的CDL法位置點密度是v/Q。當(dāng)樣本點密度與位置點隨機分配密度相等的時候，可以得出ω=vπR2/Q，這樣其運算量減少Q(mào)/πR2倍。當(dāng)，πR2>1的時候，在這種情況下，因采樣面積≤πR2，那么在確保樣本點密度相同的條件下，其運算量能夠繼續(xù)減小。圖3(b)展示了M*t=1時的采樣密度。在M*t>1的情況下，通過圖3(a)我們能夠看出，采樣區(qū)域面積在πR2以下，從而在很大程度上改善了采樣有效性與密度。

圖3 OASM_MNL的采樣區(qū)域與采樣密度

定理2：t時在1跳信標節(jié)點密度和采樣運算量相等條件下(當(dāng)M*t>1的時候)，隨之Li的1跳信標節(jié)點Ai,i=1,2,…,M*t最高間距愈發(fā)與2R接近，采樣區(qū)域面積逐漸降低；而Ai,i=1,2,…,M*t平均處于Li的通信圓周上的時候，在這種情況下Li處在整個采樣區(qū)域的最中間位置。接下來本文將對其進行證明，具體步驟如下所示：

設(shè)M*t=2，此處我們設(shè)定兩者依次是A1,A2，通過圖4(a)我們能夠看出，在這種情況下，采樣區(qū)域的面積是2個弓形面積的和，具體能夠通過幾何方法來進行求解：

(14)

2.4 濾波與加權(quán)求值

(15)

設(shè)通過該公式(15)將t時距Li相對偏近的ωt(ωt≤ω)個樣本點濾波出，j和Li的差值序列絕對值φij通過下面的公式進展計算：

(16)

通過上面的兩個公式我們能夠得知，值愈發(fā)減小，與兩者的距離愈小。所以求解坐標信息的過程中，兼顧到數(shù)值，進行了加權(quán)歸一化。

(17)

(18)

圖4 采樣區(qū)域與采樣密度

2.5 算法步驟

OASM_MNL涉及到的運算非常集中，都通過管理中心來完成，能夠?qū)崟r定位若干移動節(jié)點，OASM_MNL算法描述如下所示。

1)初始化，管理中心對其中全部{Ak},k=1,2,…,M的坐標及相互之間的最小跳數(shù)進行記錄，在此基礎(chǔ)上，提供RGB序列值，按照公式(7)，(10)以及(11)求解各個平均跳距與p，然后將其存儲于database里面；

OASM_MNL算法：

(1)randomarrangement area;

=rand(3,M),k=1,2,...M

{For k=1:M

x=R*cos(alpha)+a;

y=R*sin(alpha)+b;

rand(ω) and store the coordinates

(5) calculate the {RGB} of mobile nodes and samples

{For j=1:ω(|Ri-Rj|<μR&&|Gi-Gj|<μG)

&&|Bi-Bj|<μB}

{For j=1:ω(|Ri-Rj|<μR&&|Gi-Gj|<μG

&&|Bi-Bj|<μB)}

5)通過公式(1)至(6)來求解時t與Li每一樣本點之間的RGB差值序列，在此基礎(chǔ)上，將結(jié)果存儲至database里面，同時通過公式(15)來實施濾波處理；

第六步 結(jié)合公式(17)與(18)，來求解t時Li的坐標。

3 仿真實驗及結(jié)果

此處，我們通過Matlab7.11來開展仿真測試，在方形(100 m×100 m)中設(shè)置定位區(qū)域，通過 Random Waypoint(R W)[17-18]模型，自由選擇移動節(jié)點的速度與終點。在其中隨機布設(shè)160個傳感器節(jié)點，里面包括16個信標節(jié)點，自由分配50個位置點。此處假定全部節(jié)點滿足R=10 m，也就是它們的傳輸模型是幾何圓形[12]，移動節(jié)點的速度處于區(qū)間[0,Vman]之內(nèi)，其中，Vman=10 m/s而方向則處于[0,2π]區(qū)間中。相鄰時間間隔都是5 s。當(dāng)其達到終點以后，我們在每隔5 s取幾個不同的點，依次計算獲得每一點的定位誤差。有關(guān)學(xué)者[12]在研究過程中發(fā)現(xiàn)，伴隨其速度的不斷改變，RW模型無法獲得較為穩(wěn)定的誤差，鑒于這一個方面的原因，我們適當(dāng)?shù)貎?yōu)化了RW模型，規(guī)定了其速度的區(qū)間，此處主要通過優(yōu)化后的RW模型[12]。單一移動節(jié)點在t時的誤差LE如下所示：

(19)

圖5是μ取各個數(shù)值時候的誤差，按照Matlab仿真測試能夠得知，μ處于[0.0011，1.0020]范圍的時候，進行濾波處理之后能夠得到相對較多的樣本點數(shù)，同時處于[0.0012，1.0015]范圍的時候，誤差相對穩(wěn)定。當(dāng)μ=0.0011的時候，具有最低的誤差，鑒于這一個方面的原因，此處將其定做0.0011。

圖5 不同的μ值比較圖

圖6對OASM_MNL法和其他方法的誤差進行比較分析，此處信標節(jié)點密度用Sd指代示。假設(shè)仿真區(qū)大小是Q，R范圍內(nèi)的信標節(jié)點數(shù)是n1，在這種情況下，那么Sd=(μR2)n1/Q。此處我們將Sd的范圍定于0.5～4.0內(nèi)，取16～128個信標節(jié)點。通過研究我們發(fā)現(xiàn)，伴隨Sd的逐漸提高，MCL,CDL,E-CDL與OASM_MNL法的誤差均不斷下降，但是而OASM_MNL的誤差最初改變明顯，最終進入相對穩(wěn)定的狀態(tài)，同時明顯比其他方法低。Sd不斷提高的時候，MCL可以接到相對較多信標節(jié)點的信息，以此將進行過濾，所以能夠減小誤差。CDL與E-CDL由于信標節(jié)點提高，使得附近節(jié)點能夠得到相對有效的信息，最終提高了精度。OASM_MNL當(dāng)Sd在[0.5,1.0]范圍時與E-CDL沒有很大的差異，由于這個時候具有相對偏少的信標節(jié)點，OASM_MNL并未體現(xiàn)出突出的效果。而伴隨Sd的不斷提高，OASM_MNL誤差明顯減小，對比來說，其比其他方法減小幅度大33%。通過圖7我們能夠得知，伴隨選擇采樣點數(shù)目的不斷提高，OASM_MNL的誤差快速減小，不存在平緩的特點。由于OASM_MNL選擇的采樣區(qū)域足夠小，正是這一個方面的原因，樣本點愈發(fā)提高，那么和移動節(jié)點接近的數(shù)目同樣將會提高。通過圖7我們能夠發(fā)現(xiàn)，樣本點為時1 000，這個時候的誤差與0.10R相近。

圖6 信標節(jié)點密度與定位誤差

圖7 樣本點個數(shù)與定位誤差

圖8主要描述了不同方法的誤差分布直方圖。此處Sd=10,Vmax。T是50，重復(fù)測試過程中，OASM_MNL方法有70%的誤差在0.3R以下，沒有誤差在0.5R以上的結(jié)果，但其他方法的誤差都在0.3R以上。誤差明顯較高。

圖8 4種算法的誤差分布圖

圖9對比了OASM_MNL和E-CDL兩者的誤差，通過分析發(fā)現(xiàn)，平均跳距權(quán)值化處于之后，在很大程度上降低了誤差，同時相對穩(wěn)定。測試過程中，取值如下：Sd=10,Vmax=R。圖10是CDL,E-CDL,OASM_MNL的仿真圖，此處我們在方形(20m×20m)中設(shè)置仿真區(qū)域。CDL與E-CDL主要以通信區(qū)間中的信標節(jié)點來進行，所以，圖10(a)與(b)中把3個信標節(jié)點任意分配于若干移動節(jié)點的通信區(qū)域之中，但是在OASM_MNL里面以1跳信標節(jié)點來進行選擇，所以將其設(shè)定于移動節(jié)點周圍，然后進行測試且繪圖。通過圖10(a),10(b),10(c)我們能夠得知差距依次是4.76 m,3.17 m,1.17 m，其中，圖10(c)具有最好的效果。

圖9 E_CDL和OASM_MNL的定位誤差分析

4 結(jié)語

綜上所述，此處闡明優(yōu)化的OASM_MNL算法，其無須新配置硬件，定位準確、實時性相對較好。通過實驗發(fā)現(xiàn)，該算法在定位若干目標的時候具有相對不錯的效果，其弊端是當(dāng)Sd相對較小時誤差減小效果不理想，同時開銷減小幅度不理想，

圖10 3種算法實際效果比較圖

這一個方法是今后需要深入研究的問題。

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

[2] 石曉偉,張會清,鄧貴華. 基于BP神經(jīng)網(wǎng)絡(luò)的距離損耗模型室內(nèi)定位算法研究[J]. 計算機測量與控制,2012,20(17):1944-1947

[3]許曉榮,姚英彪,包建榮，等. 認知 WSN 中基于能量有效性自適應(yīng)觀測的梯度投影稀疏重構(gòu)方法[J]. 電子與信息學(xué)報，2014, 36(1): 27-33.

[4]葉 苗，王宇平. 基于變方差概率模型和進化計算的 WSN 定位算法[J]. 軟件學(xué)報，2013，24(4): 859-872.

[5]王 潔，王洪玉，高慶華，等. 一種適用于移動傳感器網(wǎng)絡(luò)的增強型蒙特卡羅定位跟蹤算法[J]. 電子與信息學(xué)報，2010，32(4): 864-868.

[6] Liu Y, Luo X Y, Long C Z, et al. Improved DV-hop localization algorithm based on the ratio of distance and path length[J]. Journal of Information & Computational Science, 2012, 9(7): 1875-1882.

[7]Hu L, Evan D. Localization for mobile sensor networks[A]. Tenth International Conference on Mobile Computing and Networking (MobiCom’04)[C]. Philadelphia, Pennsylvania, USA, 2004, 9: 45-57.

[8]Yang J, Chen Y Y, Trapper W, et al. Detection and localization of multiple spoofing attackers in wireless networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(1): 44-58.

[9] Teng G D, Zheng K G, Dong W. MA-MCL: Mobile assisted Monte Carlo localization for wireless sensor networks[J]. International Journal of Distributed Sensor Networks, 2011, 4: 1-8.

[10] Baggio A and Langendoen K. Monte Carlo localization for mobile wireless sensor networks[J]. Ad Hoc Networks, 2008, 6(5): 718-733.

[11] 張士庚，曾英佩，陳力軍，等. 移動傳感器網(wǎng)絡(luò)中定位算法的性能評測[J]. 軟件學(xué)報，2011, 22(7): 1579-1611.

[12] Chang T J, Wang K C, Hsieh Y L. A color-theory-based energy efficient routing algorithm for mobile wireless sensor networks[J]. Computer Networks, 2008,52(3): 531-541.

[13] Shee S H, Chang T C, Wang K C, et al. Efficient color-theory-based dynamic localization for mobile wireless sensor networks[J]. Wireless Personal Communications, 2011, 59(2): 375-396.

[14] Wu H B, Deng M S, Xiao L L, et al. Cosine Theorem-based DV-Hop localization algorithm in wireless sensor networks[J]. Information Technology Journal, 2011,10(2): 239-245.

[15] Vishnevsky E. RGB to HSV & HSV to RGB[OL]. http://www.cs.rit.edu/～ncs/color/t_convert.html, 2013.

[16] 王 潔，王洪玉，高慶華，等. 基于信號特征序列的粒子濾波跟蹤算法[J]. 電子學(xué)報，2010，38(10): 2297-2301.

[17] Wang T, Low C P. Evaluating inter-arrival time in general random waypoint mobility mode[J]. Ad Hoc Networks, 2012, 11(1): 124-137.

A Local Cross Region of RGB Difference Sequence Sampling WSN Localization Algorithm

Li Bingjian1,2, Zheng Liming2

(1.Department of Computer Science, Jiaying University, Meizhou 514015,China;2.College of Information Science and Technology, Jinan University, Guangzhou 510632,China)

Aiming at the problem that the real time difference and location of the mobile node localization technology in wireless sensor networks (WSN), this paper proposes a new method of WSN mobile node localization algorithm based on overlapping area sampling mode of mobile node localization. In this algorithm, the signal is obtained by using the signal in the signal intersection area of the beacon node, and the average hop distance is calculated by using the distance scale factor. The calculation formula of the jump distance in CDL is optimized; The RGB difference sequence is used to filter the sample point, and the absolute value of the difference sequence is used as the weighted standard to calculate the coordinates of the mobile node. Simulation results show that compared with common mobile node localization algorithm such as E-CDL and MCL, the positioning error of the new algorithm is reduced by more than 33%, its positioning performance is good.

node localization; cross overlap area; local sampling; RGB difference sequence

2015-12-20；

2016-02-15。

李秉鍵(1976-)，男，碩士，實驗師，主要從事無線傳感器網(wǎng)絡(luò)和物聯(lián)網(wǎng)方向的研究。

1671-4598(2016)07-0195-05

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

TP393 文獻標識碼：A