傳感網(wǎng)中不規(guī)則復(fù)雜3D平面定位策略研究*

李澤軍, 陳 敏?

(1．湖南大學(xué) 信息與工程學(xué)院,湖南 長沙 410082；2．湖南工學(xué)院 計(jì)算機(jī)科學(xué)與信息學(xué)院, 湖南 衡陽 421002)

傳感網(wǎng)中不規(guī)則復(fù)雜3D平面定位策略研究*

李澤軍1,2, 陳 敏1,2?

(1．湖南大學(xué) 信息與工程學(xué)院,湖南 長沙 410082；2．湖南工學(xué)院 計(jì)算機(jī)科學(xué)與信息學(xué)院, 湖南 衡陽 421002)

針對具有障礙物的復(fù)雜3D平面定位誤差大以及能耗高的問題，如何進(jìn)行未知節(jié)點(diǎn)的定位，提出了一種具有障礙物的不規(guī)則復(fù)雜3D平面定位策略，該策略將復(fù)雜三維平面劃分為水平邏輯層并標(biāo)記節(jié)點(diǎn)的所屬層，然后在具有障礙物的水平層進(jìn)行子區(qū)域的劃分及合并，最后利用大氣壓傳感器測距進(jìn)行計(jì)算未知節(jié)點(diǎn)的坐標(biāo)從而得到3D復(fù)雜平面的定位.通過與最新SV定位機(jī)制及COLA定位機(jī)制在定位誤差及能耗進(jìn)行綜合仿真實(shí)驗(yàn)對比，本文的定位策略3D-CCD平均定位誤差比SV少了5%，比COLA的平均定位誤差少8%以上，定位精度上比SV和COLA提高了6.5%以上，及在能耗上比SV和COLA減少了2.7%左右.因此該定位策略(3D-CCD)在解決復(fù)雜不規(guī)則圖形的不確定節(jié)點(diǎn)具有較大的優(yōu)越性.

定位誤差；邏輯層；子區(qū)域；定位機(jī)制

復(fù)雜環(huán)境下的定位機(jī)制大多數(shù)都是基于2D網(wǎng)絡(luò)拓?fù)洵h(huán)境，導(dǎo)致節(jié)點(diǎn)路徑估算產(chǎn)生較大的誤差以及誤差難以控制、傳感器節(jié)點(diǎn)能耗大等諸多因素.如：ACDL經(jīng)典方法采用2D定位機(jī)制解決復(fù)雜網(wǎng)絡(luò)定位問題，該方法設(shè)定一臨界點(diǎn)，傳感器節(jié)點(diǎn)利用鄰居節(jié)點(diǎn)的通信來判定凹凸表面，并將復(fù)雜表面劃分為幾個(gè)子區(qū)域，節(jié)點(diǎn)通過MDS建立節(jié)點(diǎn)的相對位置.最后利用相對位置建立全局2D平面圖.這樣方法過度臨界值的選擇，當(dāng)復(fù)雜不平表面無臨界值時(shí)，該策略將導(dǎo)致失敗，另外該定位方法對邊界噪音比較敏感.目前，學(xué)者們嘗試從2D平面擴(kuò)展到3D平面，其主要采用的定位方法有兩種，一是通過將3D復(fù)雜平面映射到2D平面來定位其坐標(biāo)[1,2].二是采用特殊裝置來測量凹凸平面的高度值和拋錨節(jié)點(diǎn)的距離[3].上述方法對于簡單的3D表面定位具有較高的精確度，但對于復(fù)雜表面以及具有較大凸高時(shí)，其定位誤差明顯增大和定位不明確.而SV(Single-Value)根據(jù)不同節(jié)點(diǎn)映射到不同2D平面上且平面的點(diǎn)具有唯一性.然后根據(jù)二維平面來定位三維平面.一定程度上解決了較簡單的3D平面節(jié)點(diǎn)重疊問題[4].但SV的代價(jià)較高，對于不規(guī)則三維平面也將導(dǎo)致節(jié)點(diǎn)重疊現(xiàn)象.COLA定位機(jī)制[5]采用移動錨節(jié)點(diǎn)來定位三維平面，該方法的精確度較高，但對于復(fù)雜3D的平面，由于錨節(jié)點(diǎn)的不斷移動產(chǎn)生大量的誤差值，難以適用大規(guī)模3D平面定位.

1 復(fù)雜3D平面的分層機(jī)制及相關(guān)定義

對復(fù)雜3D平面進(jìn)行邏輯水平分層，其分層示意圖如圖1所示．利用大氣壓傳感器得到節(jié)點(diǎn)高度，在得到所有節(jié)點(diǎn)的高度后，就可以得到3D平面的最大高度(hh)和最小高度(hl)，若分為L層，當(dāng)每層的節(jié)點(diǎn)數(shù)相同時(shí)，則可以計(jì)算每層的高度為(hh-hl)/l，但在實(shí)際情況下，每層的節(jié)點(diǎn)數(shù)不一致，為保證每層的節(jié)點(diǎn)數(shù)一致，采用提高層的高度來保證節(jié)點(diǎn)數(shù)相同并進(jìn)行標(biāo)記節(jié)點(diǎn)屬于哪一層.

(1)

其中ρ為大于0的常數(shù)(通常設(shè)為1)，其值為節(jié)點(diǎn)跳數(shù)與歐氏距離之比例因子.

圖1 復(fù)雜凹凸平面的水平劃分

圖2 凹凸節(jié)點(diǎn)映射關(guān)系

2 復(fù)雜平面凹凸節(jié)點(diǎn)和邊界節(jié)點(diǎn)的判別

圖3 凹凸復(fù)雜平面存在障礙物示意圖

凹凸節(jié)點(diǎn)判別算法描述

輸入：設(shè)定傳感器節(jié)點(diǎn)p

輸出：凹凸節(jié)點(diǎn)判別標(biāo)識

Step 1 Nodepobtains its neighborsESk(p) withinkhops

Step 5 flagconver←true

Step 6 else

Step 7 flagconver←false

Step 8 endif

3 凹/凸層的分解

為減少算法的迭代次數(shù)以及算法的開銷，通過節(jié)點(diǎn)凹/凸度將縱深區(qū)域分解成多個(gè)子區(qū)域?qū)?依據(jù)凹凸節(jié)點(diǎn)算法可以將分層后的凹凸節(jié)點(diǎn)度計(jì)算出來，這里分層的依據(jù)是最大凹凸度的節(jié)點(diǎn).下面詳細(xì)闡述其分解凹凸層的方法.

3.1 以凹凸節(jié)點(diǎn)度構(gòu)建子區(qū)域

由于子區(qū)域中可能存在障礙物記為hole，因此分為2種情況：

2)當(dāng)子區(qū)域存在障礙物時(shí)，圖4表示存在多個(gè)障礙物，這里以2個(gè)障礙物為例進(jìn)行說明.S={s1,s2,s3,s4,s5}，錨節(jié)點(diǎn)為s1,s5.

圖4 區(qū)域平面存在障礙物

計(jì)算區(qū)域存在hole1和hole2兩個(gè)障礙物的最短路徑時(shí)，由于錨節(jié)點(diǎn)為s1,s5會形成完全圖G，將圖G劃分為若干個(gè)子區(qū)域，則障礙物只可能存在于子區(qū)域內(nèi).為減少障礙物對定位精度的影響，這里采用避障方式進(jìn)行處理．其處理步驟如下．

步驟1：計(jì)算并標(biāo)記錨節(jié)點(diǎn)之間所有節(jié)點(diǎn)的最短路徑，其標(biāo)記方法為如節(jié)點(diǎn)s2,s5記為PS2S3.

步驟2：含有障礙物的邊界節(jié)點(diǎn)發(fā)送廣播以確定最近節(jié)點(diǎn)的最短路徑.

步驟3：障礙物坐標(biāo)可依據(jù)錨節(jié)點(diǎn)坐標(biāo)和步驟2進(jìn)行計(jì)算，如圖4中，通過步驟1和步驟2分別標(biāo)記和確定3條最短路徑(即s1s4,s3s5及s4s5)并計(jì)算路徑交點(diǎn)s4，s5，s45，這樣就能得出障礙物1(hole1)屬于s4s5s45子區(qū)域.同理可計(jì)算其余障礙物的歸屬.

步驟4：依據(jù)障礙物位置及障礙物歸屬的子區(qū)域，若hole?Δsisjsk，則規(guī)定約束條件si,sj,sk不能同屬于一個(gè)子區(qū)域.根據(jù)此約束條件遍歷所有子區(qū)域錨節(jié)點(diǎn).若錨節(jié)點(diǎn)不屬于同一子區(qū)域，將錨節(jié)點(diǎn)加入禁忌隊(duì)列中.在錨節(jié)點(diǎn)遍歷中，為減少算法復(fù)雜度，優(yōu)先采用最短路徑算法.

步驟5：依據(jù)步驟1和4對3D復(fù)雜平面進(jìn)行子區(qū)域劃分.

3.2 確立新根節(jié)點(diǎn)子區(qū)域

3.3 合并子區(qū)域及構(gòu)建層區(qū)域

在進(jìn)行子區(qū)域的建立時(shí)采用廣播的方式進(jìn)行信息傳遞，導(dǎo)致在層區(qū)域內(nèi)形成若干個(gè)子區(qū)域并且子區(qū)域可能產(chǎn)生重疊現(xiàn)象.若節(jié)點(diǎn)p接收多個(gè)構(gòu)建子區(qū)域信息時(shí)，以第一時(shí)間收到的信息作為標(biāo)記加入到該子區(qū)域中，其余消息將被丟棄.否則若子區(qū)域標(biāo)記不相同則合并兩個(gè)子區(qū)域直到合并消息不存在.

復(fù)雜凹凸平面的分解與子區(qū)域的合并算法描述如下：

Algorithm:convex/concave decomposition

Input:Set of convex/concave node degree

Output: Set of convex/concave sub-regions

Step 1:Set SID=NULL

Step 2:for each sensor nodes pi

Step 3:if then

Step 4:Choose pi as RootNode

Step 5:end if

Step 6:end for

Step 7:if no such node exits then

Step 8:Choose the node p(closest to the middle floor) as RootNode

Step 9: end if

Step 10: if and exits Hole

Step 11:for each anchor sensor Si in region S

Step 12: for each anchor sensor Sj in region S

Step 13:shortest path

Step 14:end for

Step 15:end for

Step 16: for each sensor pi

Step 17: mark pi=smsn

Step 18:end for

Step 19: for each boundary sensor bi of Hole

Step 20: bi sends Message _in

Step 21:mark the nearest node pi and the shortest

Step 22: end for

Step 23:if exits , , then

Step 24:hole

Step 25:add sa,sb,sc to prohibition queue

Step 26:end if

Step 27:end if

Step 28:for each sensor nodes Pi

Step 29:if then

Step 30:RootNode sent Message _in to pi

Step 31:if pi:SID=NULL and pi prohibition_quenu then

Step 32:set pi:SID=Message_in

Step 33:else Merge the two sub-regions

Step 34:end if

Step 35:else choose pi as new RootNode

Step 36:end for

4 復(fù)雜平面定位與計(jì)算

在復(fù)雜3D平面定位計(jì)算中主要考慮模型構(gòu)建差生的誤差以及定位方法和過程.傳感器節(jié)點(diǎn)在進(jìn)行通信時(shí)其物理層的傳播模式可以任意，其公式為[7,8]：

(2)

由于3D平面的模型比較復(fù)雜，這里采用地形平面誤差[9](terrain plane error)記為TPE進(jìn)行修正，其公式如下：

(3)

式中zi,zei分別為傳感器節(jié)點(diǎn)p實(shí)際坐標(biāo)與測量值坐標(biāo).為減少人為測距對模型的影響，這里采用誤差修正模型抑制.其修正模型如下：

(4)

Δq=k1e+k2．

(5)

通過第三節(jié)分層子區(qū)域后，利用三角形三邊進(jìn)行傳感器節(jié)點(diǎn)定位，如可根據(jù)錨節(jié)點(diǎn)p1，p2，p3來定位節(jié)點(diǎn)i.h1表示節(jié)點(diǎn)i的高度，hp1,hp2,hp3分別為三個(gè)錨節(jié)點(diǎn)高度，其與i的斜線距離用x1,x2,x3表示.則映射到平面的距離用r1,r2,r3表示，可以通過以下計(jì)算r1,r2,r3.

(6)

由公式(6)可以轉(zhuǎn)化公式為：

通過求解方程組可得到：

2x(x2-x1)+2y(y2-y1)=D1,2；

2x(x3-x1)+2y(y3-y1)=D1,3．

(8)

則未知節(jié)點(diǎn)i坐標(biāo)(x,y)的計(jì)算公式如下：

(9)

(10)

公式(9)和(10)中的D以及p1,2和p1，3的計(jì)算如下：

(11)

(12)

(13)

以上公式的計(jì)算可以得出未知節(jié)點(diǎn)的坐標(biāo)，遍歷所有子區(qū)域內(nèi)的節(jié)點(diǎn)，得到整個(gè)復(fù)雜平面全局地圖.

5 實(shí)驗(yàn)參數(shù)設(shè)置及算法性能評估

試驗(yàn)中網(wǎng)絡(luò)3D復(fù)雜平面區(qū)域?yàn)? 000 m×1 000 m×500 m，采用Matlab進(jìn)行仿真，這里假設(shè)網(wǎng)絡(luò)為連通的，節(jié)點(diǎn)高度通過氣壓傳感器進(jìn)行測量其高度.傳感器節(jié)點(diǎn)數(shù)分別采用1 000,2 000,4 000并且隨機(jī)散播在整個(gè)復(fù)雜網(wǎng)絡(luò).通信半徑為100，節(jié)點(diǎn)跳數(shù)設(shè)為k=3，傳感器節(jié)點(diǎn)間歐式距離與節(jié)點(diǎn)跳數(shù)比例因子δ=0.4.

定位率：定位節(jié)點(diǎn)與整個(gè)節(jié)點(diǎn)之間的比值.

定位誤差：傳感器節(jié)點(diǎn)實(shí)際坐標(biāo)用(x,y,z)表示,估測坐標(biāo)用(xe,ye,ze)表示，傳感器節(jié)點(diǎn)通信半徑用R表示，相鄰節(jié)點(diǎn)距離用l表示，節(jié)點(diǎn)間實(shí)際距離用l′表示.則定位誤差和平均定位誤差可用以下公式進(jìn)行計(jì)算[10]：

(14)

(15)

信號強(qiáng)度：信號強(qiáng)度采用傳統(tǒng)信號強(qiáng)度公式計(jì)算：

pd=po-10×2×log10(f)-10×2×log10(d)+27.56

(16)

在實(shí)驗(yàn)中通過將凹凸復(fù)雜平面定位策略研究(Concave-convexcomplexplatdemonstration記為3D-CCD)與目前最新流行算法SV,COLA在定位率、平均定位誤差以及計(jì)算開銷方面進(jìn)行對比，以此來評價(jià)各算法的綜合性能.

從上述圖5,圖6和圖7可以看出:隨著測量距離的增大，各算法的定位率都有不同程度的下降，COLA下降的尤為明顯，而本文算法依然表現(xiàn)出較高的定位率.這是由于復(fù)雜3D平面具有障礙物的原因，導(dǎo)致分割的子區(qū)域更多的緣故.下面進(jìn)行平均誤差的仿真.

Measurement Error/%

Measurement Error/%

Measurement Error/%

Measurement Error/%

Measurement Error/%

Measurement Error/%

從圖8～10中的實(shí)驗(yàn)數(shù)據(jù)可以得出：當(dāng)測量距離增大也即測量誤差增大時(shí)，三種算法的定位精度都有所下降，并且三種算法算法的平均誤差都所有增加．但與SV及COLA算法對比，本文算法3D-CCD的平均誤差在節(jié)點(diǎn)數(shù)為1 000時(shí)比SV要低6.8%，比COLA算法要低13.6%，而在節(jié)點(diǎn)數(shù)增加到4 000時(shí)平均誤差比SV要低7.2%，比COLA算法要低14.7%.這是因?yàn)?D-CCD采用凹凸分層策略以及子區(qū)域合并策略來避免障礙物的原因.說明本文算法3D-CCD能準(zhǔn)確定位未知傳感器節(jié)點(diǎn)坐標(biāo)并且誤差與網(wǎng)絡(luò)模式無關(guān).下面進(jìn)行算法的開銷仿真.

節(jié)點(diǎn)數(shù)

圖11表示3D-CCD算法的開銷在不同測量誤差時(shí)都要比SV及COLA算法的開銷要小，這是由于3D-CCD采用的迭代次數(shù)少的緣故.

6 結(jié)束語

本文研究復(fù)雜3D平面的定位機(jī)制，該策略首先將復(fù)雜三維平面進(jìn)行邏輯水平分層，然后在水平層進(jìn)行子區(qū)域的劃分及合并處理，最后用大氣壓傳感器測距進(jìn)行計(jì)算未知節(jié)點(diǎn)的坐標(biāo)從而得到3D復(fù)雜平面的定位.該思路為不規(guī)則復(fù)雜三維平面提供了新的思路.該策略尤其適用于不確定節(jié)點(diǎn)的定位.

[1]ZHAOY,WUH,JINM,etal.Localization in 3D surface sensor networks: Challenges and solutions[C]//The 31st Annual IEEE International Conference on Computer Communications (IEEE INFOCOM 2012)．Orlando, Florida,USA,2012:55-63.

[2] LIU Q,REN P,ZHOU Z. Three-dimensional accurate positioning algorithm based on wireless sensor networks[J].Journal of Computers, 2011, 6(12): 2582-2589.

[3] LIU C,JIANG H,ZENG L D.Unitary matrix pencil algorithm for range-based 3d localization of wireless sensor network nodes[J]. Journal of Networks, 2012, 7(9):1384-1390.

[4] 趙德鑫,李婷,黃芝平,等.無人潛航器舷側(cè)陣聲吶匹配場被動定位方法研究[J].湖南大學(xué)學(xué)報(bào)：自然科學(xué)版,2013,40(8):76-82.

ZHAO De-xin,LI Ting,HUANG Zhi-ping,etal.Matched-field source localization using the flank array of unmanned under water vehicle[J].Journal of Hunan University:Natural Sciences, 2013,40(8):76-82. (In Chinese)

[5] STOLERU R,HE T,MATHIHARAN S S,etal.Asymmetric event-driven node localization in wireless sensor networks[J]. Parallel and Distributed Systems, IEEE Transactions on, 2012,23(4): 634-642.

[6] 楊高波,吳瀟,張兆揚(yáng),等.基于過渡像素的視頻圖像文本檢測與定位[J]． 湖南大學(xué)學(xué)報(bào):自然科學(xué)版,2011,38(6):69-74.

YANG Gao-bo,WU Xiao,ZHANG Zhao-yang,etal.A transition pixels based text detection and localization for video images[J]. Journal of Hunan University:Natural Sciences, 2011,38(6):69-74.(In Chinese)

[7] CUI H,WANG Y.Four-mobile-beacon assisted localization in three-dimensional wireless sensor networks[J]. Computers & Electrical Engineering, 2012, 38(3): 652-661.

[8] WANG R J,QIN Z G.A weighted 3D localization algorithm based on partial hopsize in wireless sensor network[J]. International Journal of Advancementsin Computing Technology,2012, 4(9): 504-513.

[9] WANG Y,LIU Y,GUO Z.Three-dimensional ocean sensor networks: A survey[J]. Journal of Ocean University of China, 2012, 11(4): 436-450.

[10]王小平,羅軍,沈昌祥.無線傳感器網(wǎng)絡(luò)定位理論和算法[J].計(jì)算機(jī)研究與發(fā)展, 2011,48(3):353-363.

WANG Xiao-ping,LUO Jun,SHEN Chang-xiang. Theory and algorith mson localization in wireless sensor networks[J]. Journal of Computer Research and Development, 2011,48(3):353-363. (In Chinese)

The Study of Positioning Strategy of Irregular 3D Plane in Sensor Networks

LI Ze-jun1,2, CHEN Min1,2?

(1.College of Information Science and Engineering, Hunan Univ,Changsha, Hunan 410082, China;2.School of Computer and Information Science,Hunan Institute of Technology,Hengyang , Hunan 412002,China)

Considering the large positioning error and high energy consumption concerning irregular and complex 3D plane with obstacles, this paper put forward a new strategy to locate the unknown nodes. This policy divides the complex three-dimensional plane into different logic layers and labels each layer node it belongs to. Then, sub-regions are divided and merged in horizontal layers. Finally, the positioning of 3D complex plane is possible by calculating the location coordinate of unknown nodes after atmospheric pressure sensor ranging. Compared with SV and COLA, the 3D-CCD positioning strategy in the average positioning error is 5% less than SV and 8% less than COLA． Its positioning precision increases more than 6.5%， and the energy consumption reduces 2.7% than SV and COLA. The 3D-CCD has great advantages in terms of positioning error, accuracy and energy.

positioning error；logic layer；subdomain ；positioning mechanism

1674-2974(2015)08-0125-07

2014-10-12

國家自然科學(xué)基金資助項(xiàng)目(61472127) ，National Natural Science Foundation of China(61472127) ;湖南省自然科學(xué)基金資助項(xiàng)目 (13JJ9026)

李澤軍(1972-)，男,湖南常寧人，湖南大學(xué)博士生

?通訊聯(lián)系人，E-mail:9918428@qq.com

TP39

A