王瑞錦，黃耀東，徐志遠，秦志光

(1. 電子科技大學(xué)信息與軟件工程學(xué)院 成都 611731; 2. 電子科技大學(xué)計算機科學(xué)與工程學(xué)院 成都 611731)

復(fù)雜山體表面?zhèn)鞲衅骶W(wǎng)絡(luò)定位算法

王瑞錦1，黃耀東2，徐志遠2，秦志光1

(1. 電子科技大學(xué)信息與軟件工程學(xué)院 成都 611731; 2. 電子科技大學(xué)計算機科學(xué)與工程學(xué)院 成都 611731)

存在障礙物的復(fù)雜3D凹/凸不平表面網(wǎng)絡(luò)中錨節(jié)點部署難且成本高的問題是一個挑戰(zhàn)。針對這個問題，該文提出了一種新的基于網(wǎng)絡(luò)拓撲分形的三角劃分定位算法3DT-ST。該算法僅利用網(wǎng)絡(luò)連通特性和特殊節(jié)點，進行三角劃分和建模，在每一個三角區(qū)域上采用MDS-MAP方法建立起局部的相對位置地圖，再通過整合每個三角子區(qū)域，建立起整個傳感器網(wǎng)絡(luò)的全局位置地圖。實驗結(jié)果表明，3DT-ST算法與目前使用的SV方法相比，定位精度提高，定位誤差降低明顯，且定位過程無需錨節(jié)點和迭代，僅通過節(jié)點間的連通性進行定位，提高了定位的精度、降低了計算開銷的同時節(jié)省了部署成本。

復(fù)雜環(huán)境下的定位問題; 特殊節(jié)點識別; 三角劃分無線; 傳感器網(wǎng)絡(luò)

定位技術(shù)是無線傳感器網(wǎng)絡(luò)(wireless sensor networks, WSNs)的關(guān)鍵支撐技術(shù)之一，WSN的信息采集和傳輸、目標(biāo)跟蹤、信息管理和基于地理位置的路由等許多應(yīng)用中都需要準確的節(jié)點位置信息作為保障和支撐[1-4]。一般而言，沒有位置信息的節(jié)點數(shù)據(jù)是毫無意義的。在實際應(yīng)用環(huán)境中，節(jié)點通常被隨機部署到復(fù)雜3D環(huán)境(如山體表面、海底或空中)。尤其是在山體表面環(huán)境中，地形可能會造成節(jié)點間連通性低、通信受阻等問題。因此，如何才能在不規(guī)則的復(fù)雜3D環(huán)境中實現(xiàn)高精度、低能耗的節(jié)點定位，成為了研究的重點[5-8]。

WSN節(jié)點定位的方法有很多。目前討論熱點是如何在減小網(wǎng)絡(luò)配置的同時，提高定位算法的實用性[1,3,5,8]，比如無需錨節(jié)點的定位方法，僅僅通過節(jié)點間的連通性信息進行定位，在構(gòu)建網(wǎng)絡(luò)的過程中不用考慮可能所需錨節(jié)點的部署，這樣有效地減少了網(wǎng)絡(luò)的配置成本。同時，3D環(huán)境下網(wǎng)絡(luò)條件更復(fù)雜，環(huán)境影響因素多，尤其是山體表面的定位，其應(yīng)用廣泛，但地形的限制破壞了理想網(wǎng)絡(luò)中的諸多特性，傳統(tǒng)的2D算法不能應(yīng)對復(fù)雜的新環(huán)境。

本文針對大規(guī)模復(fù)雜3D山體表面WSN的特性，提出一種尋找特殊節(jié)點并進行三角劃分的定位算法：

1) 提出了一種新的尋找特殊節(jié)點，采用全局最短路徑樹中各節(jié)點的子樹，尋找節(jié)點特征的方法來尋找特殊節(jié)點，通過多次泛洪統(tǒng)計節(jié)點渡口度來判斷是否為渡口節(jié)點，并通過渡口節(jié)點的連接性導(dǎo)出特殊渡口節(jié)點；2) 利用計算出的特殊渡口節(jié)點，采用德勞內(nèi)三角化方法，將網(wǎng)絡(luò)劃分成獨立、規(guī)則、平整三角區(qū)域，減少基于RSSI測距的誤差；3) 在每一個三角區(qū)域上采用MDS-MAP算法對節(jié)點進行局部定位，在不使用錨節(jié)點的條件下使其能夠在平整的三角子區(qū)域中準確確定傳感器的相對位置。最后并將拆分成多個相對平整的三角子區(qū)域合并起來，從而確定整個網(wǎng)絡(luò)中節(jié)點位置信息。

1 相關(guān)研究

針對不同的應(yīng)用環(huán)境，學(xué)者們已經(jīng)提出了多種3D定位算法，文獻[9]提出了一個新穎的飛行移動錨節(jié)點定位算法。利用在飛機上配備了GPS接收器的錨節(jié)點，當(dāng)飛行錨節(jié)點飛過傳感空間時廣播自己的位置信息。

文獻[10-11]提出的定位算法是基于2D模型的，為了解決3D環(huán)境定位問題，通常是將3D平面節(jié)點映射到2D平面，再采用平面定位算法進行節(jié)點定位[12]。但這種嘗試性的擴展給定位算法復(fù)雜性也顯著增加。

多維尺度(MDS)算法[13]及其改進的MDSMAP[14]也能夠很好地適應(yīng)2D模型的定位。但擴展到復(fù)雜環(huán)境時就會出現(xiàn)模型失用等問題。

文獻[15]提出的定位算法CATL，其核心是找出節(jié)點之間最短路徑的跳數(shù)偏離真正的歐氏距離的凹口節(jié)點。算法性能依賴于錨節(jié)點的正確部署，在網(wǎng)絡(luò)節(jié)點數(shù)量較大的情況下計算開銷不穩(wěn)定，網(wǎng)絡(luò)的均勻程度也對該算法的效果有一定的影響。

文獻[16]提出的SV算法能實現(xiàn)定位3D表面節(jié)點。該算法將3D表面的節(jié)點映射到2D面后計算出節(jié)點的坐標(biāo)，再利用氣壓傳感器還原節(jié)點的高度信息。該方法僅適用于規(guī)則的3D網(wǎng)絡(luò)，當(dāng)考慮復(fù)雜3D山體表面，由于地形原因會出現(xiàn)映射重復(fù)的情況，這將直接導(dǎo)致節(jié)點定位率下降。此外，網(wǎng)絡(luò)在進行三角劃分的時候粒度過細，將增大迭代計算的開銷。

ACDL[17]是一種基于凸面分解的定位方法。該算法是以邊界凹節(jié)點作為劃分依據(jù)，并沒有利用全局的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，因此易受到邊界噪聲的影響，并且該算法不適用于大規(guī)模傳感器網(wǎng)絡(luò)。

本文作者針對復(fù)雜山體表面網(wǎng)絡(luò)特性也曾提出了相應(yīng)的算法3D-CCD[18]，對該問題進行了嘗試性解決，但采用傳統(tǒng)的基于路標(biāo)節(jié)點的劃分方法[15]劃分區(qū)域，往往劃分的平面凸度很高。

2 3 DT-ST算法的設(shè)計

根據(jù)復(fù)雜3D凹/凸不平表面網(wǎng)絡(luò)的拓撲特性，利用節(jié)點間聯(lián)通性特征，按照如下的步驟設(shè)計算法。

2.1 特殊渡口節(jié)點的尋找

從網(wǎng)絡(luò)的任意一個節(jié)點發(fā)出一則消息，通過這個消息的傳播獲得了一棵全局最短路徑樹。如果網(wǎng)絡(luò)中的節(jié)點是各向均勻的，則任意一個節(jié)點周圍的節(jié)點分布是均勻的，信息向各個方向傳播的概率是相等的，所獲得的最短路徑樹也是均勻的。然而，由于凹/凸不平地形的限制，信號的傳播會受到障礙物等阻擋。為了將信號傳遍整個網(wǎng)絡(luò)，當(dāng)消息從一座山傳播到另一座山時，就很可能經(jīng)過在山谷的節(jié)點；從山的一側(cè)翻越到另一側(cè)，很可能經(jīng)過山脊的節(jié)點。這樣，3D凹/凸不平表面網(wǎng)絡(luò)的平衡就會被破壞，信息從山谷和山脊到達的節(jié)點更多，信息經(jīng)過山谷和山脊的可能性更大，也就是說網(wǎng)絡(luò)不是同構(gòu)的而是異構(gòu)的。如果僅僅通過子樹節(jié)點的數(shù)量來計算是不合適的，因為信息是從一個點發(fā)出的具有孤立性。同時，從山谷和山脊傳播出去的信息在很短的幾個跳數(shù)內(nèi)就能展開到一個平面，覆蓋很多的節(jié)點。因而，可以利用該性質(zhì)來判斷山谷和山脊節(jié)點。將3D凹/凸不平表面網(wǎng)絡(luò)中大量信息的山谷節(jié)點和山脊節(jié)點稱為“渡口節(jié)點”(port nodes)。一個節(jié)點可能是渡口節(jié)點的衡量標(biāo)準稱為渡口度(port degree, PDi)?？梢酝ㄟ^PDi的值判斷一個節(jié)點是否是渡口節(jié)點。進而，根據(jù)渡口節(jié)點的連接，可以得到其中在山谷點和山脊點的渡口節(jié)點為特殊渡口節(jié)點，利用這些特殊渡口節(jié)點(special port node, SPN)進行3D凹/凸不平表面網(wǎng)絡(luò)的三角劃分，就能得到較為平整山體平面表面結(jié)構(gòu)。

選擇已經(jīng)找到的路標(biāo)節(jié)點(SPN)。每個路標(biāo)節(jié)點異步泛洪，發(fā)送一個信息，并構(gòu)建全局最短路徑樹。這個信息帶有一個跳數(shù)的基數(shù)，所以每個路標(biāo)節(jié)點能夠通過這個信息知道自己在這棵樹中處于哪一層。如果某個路標(biāo)節(jié)點是第一次從一個確定的泛洪中收到一個消息，那么它就將這個消息的發(fā)送者當(dāng)做它的父節(jié)點，并且回復(fù)一個確認消息。若一個節(jié)點p在一段確定的時間內(nèi)收到了來自上一節(jié)點的信息并將信息轉(zhuǎn)發(fā)，但沒有收到過下一節(jié)點確認信息，它就將視自己為葉子節(jié)點。從葉子節(jié)點開始，依此向上回送一個報告給這棵樹，報告自己的層數(shù)。

由于判斷渡口節(jié)點最重要的是節(jié)點層數(shù)和節(jié)點數(shù)量的關(guān)系，使用影響因子來表示每個子節(jié)點對父節(jié)點的影響。節(jié)點對p其k級父節(jié)點的影響因子：

然后，計算每個節(jié)點的綜合影響因子，節(jié)點p的綜合影響因子為：

式中，{qp,1,qp,2,,qp,m}是節(jié)點p子樹上大于3層的所有節(jié)點；N代表節(jié)點p子樹上大于3層的所有節(jié)點數(shù)目。在每一次節(jié)點泛洪和在一定跳數(shù)h范圍內(nèi)，其子樹影響的綜合影響因子IAff(p)達到一個預(yù)定閾值TreeThres點時，渡口度PD(p)的值增加1。

在每一次路標(biāo)節(jié)點泛洪中，從所有已完成識別的葉子節(jié)點開始，向其父節(jié)點發(fā)送信息。父節(jié)點收到信息后，計算和統(tǒng)計所有的孩子節(jié)點，將他們的層數(shù)加1，并計算自己的綜合影響因子IAff(p)，再將自己和所有孩子的層數(shù)信息發(fā)送到其父節(jié)點。當(dāng)信息到達點p時，使用k跳以內(nèi)的結(jié)果計算自己的綜合影響因子。若p點綜合影響因子IAff(p)達到閾值TreeThres，則其渡口度PD(p)的值增加1。完成10%的節(jié)點一次異步泛洪后，如果PD(p)值達到某一閾值CountThres，則p點即為渡口節(jié)點。圖2中的★是渡口節(jié)點，●是普通節(jié)點。

通過圖2可知，得到的渡口節(jié)點沿著山頂向山腳排列，把網(wǎng)絡(luò)沿山脊劃分成兩部分，有利于平面的定位和方便進行三角化，以此來擴大平面的面積，減少計算開銷和部署開銷。還要對渡口節(jié)點進行一些篩選，保留盡可能靠近山頂和山腳的節(jié)點，稱為特殊渡口節(jié)點(SPN)。

為了獲取SPN，首先渡口節(jié)點之間在一跳以內(nèi)進行異步通信，一次發(fā)送連接請求，在一跳以內(nèi)的其他渡口節(jié)點收到后，就返回ACK，建立一個連接?？芍⒘艘粋€連接的節(jié)點位于劃分線的端頭處，建立了大于等于3個連接的節(jié)點位于劃分線的交點處。這些節(jié)點有著顯著的地理特征，分布在山頂山腳，因此，可以有效地找到接近于山腳和山頂?shù)腟PN。但節(jié)點還會出現(xiàn)聚集現(xiàn)象，即在一跳以內(nèi)可能有很多渡口節(jié)點。為了避免這種情況，在建立節(jié)點連接的同時建立并查集，即在一跳以內(nèi)的特殊節(jié)點放在一個并查集內(nèi)。最后，從每個并查集內(nèi)選擇PD()p最大的節(jié)點，這樣選擇出來的節(jié)點就是SPN。

算法 1 Find SPN node//尋找特殊渡口節(jié)點(SPN)

Initialize for all pi.count==0,pi.unionfind=i

for allpianpjwherePD(pi)>CountThres and PD(pj)>CountThres

if piand pjcan connect

pi.count ++

pj.count ++

end if

end for

for all PD(pi)>CountThres where

pi.count≤1 or pi.count≥3

for all PD(pj)>CountThres where

pj.count≤1 or pj.count≥3

if pjand pjcan connect

pi.unionfind=pj.unionfind

unionfind max.i =findmax(PD(pi))in unionfind.i

end if

end for

end for

2.2 三角網(wǎng)劃分網(wǎng)絡(luò)建模

3DT-ST算法中把SPN節(jié)點連起來形成德勞內(nèi)三角形。圖3展示了根據(jù)SPN進行三角化的結(jié)果。從圖中可以看出，劃分出的三角子網(wǎng)平整，規(guī)則，能夠體現(xiàn)復(fù)雜山體表面的特征，并且能夠較好地覆蓋復(fù)雜山體表面區(qū)域。

2.3 獲取局部相對位置

經(jīng)過上面步驟，得到 n個已劃分的三角子區(qū)域{Sub1,Sub2,,Subn}。再對每個子區(qū)域 Subi使用MDS-MAP算法進行定位。

設(shè)三角網(wǎng)子區(qū)域 Subi中的節(jié)點個數(shù)為ni，當(dāng)開始定位算法后，啟動節(jié)點的信號能量強度指示(RSSI)模塊，采用最短路徑搜索算法，計算整個網(wǎng)絡(luò)中兩兩節(jié)點之間的距離，形成距離矩陣。再將得到的距離矩陣作為輸入，并以三角子區(qū)域頂點作為協(xié)調(diào)者，使用MDS算法建立局部相對位置。

對于一個三角網(wǎng)子區(qū)域 Subi中的 ni×ni距離矩陣 Di，MDS算法先計算內(nèi)積矩陣其中I為n維單位矩陣，e為全1向量。然后將Bi對角化表示為Bi=XXT=UVU?1，其中

最后，矩陣中最大的兩個或者3個特征值所對應(yīng)的特征向量即是節(jié)點在二維或三維中的相對坐標(biāo)矩陣 X。

2.4 建立全局地理位置

根據(jù)文獻[6]，本文采用網(wǎng)絡(luò)的鄰接約束圖ACG[19]。每個點i代表一個三角子區(qū)域 Subi，如果Subi和 Subi是鄰近的兩個子區(qū)域，則 i,j也是鄰居節(jié)點。定義 di為與 Subi三角網(wǎng)相鄰的區(qū)域的數(shù)量，稱為 Subi的度。每個節(jié)點 i賦權(quán)重 wi， wi值為三角網(wǎng) Subi中的節(jié)點數(shù)量， nij表示公共線段上的節(jié)點個數(shù)。然后按照下列算法建立全局地圖，三角網(wǎng) Subi中節(jié)點的坐標(biāo)將轉(zhuǎn)換到 Subi的坐標(biāo)系統(tǒng)中。

算法 2 Global Map Establishment

while The number of Sub regions is larger than one do

For every two adjacent

subsections Subiand Subj

if dj

Subi=Subi∪Subj

dj=di+dj?1, wi=wi+wj?nij

end if

end for

end while

每一次轉(zhuǎn)換坐標(biāo)，兩個相鄰的三角網(wǎng)被合并，直到所有三角網(wǎng)合并成一個大的區(qū)域后停止算法，輸出為全局地圖，完成全網(wǎng)絡(luò)的節(jié)點定位。

3 實驗及性能評估

本節(jié)通過實驗對本文提出的3DT-ST算法，從節(jié)點密度、定位誤差和計算能耗等方面來驗證方法的可行性和魯棒性，并與最新的SV和MDS-MAP定位算法進行性能分析對比。

3.1 實驗參數(shù)設(shè)置

選取圖1所示的山體模型。模型的大小長寬1 000 m× 1 000 m，地形落差100 m左右。節(jié)點部署采用的是均勻隨機的傳感器部署方式，并且保證整個網(wǎng)絡(luò)盡可能連通的。在100 000 m2的范圍內(nèi)部署1 000～4 000個節(jié)點。由于算法需要測量節(jié)點之間的距離，因此可能會造成測量誤差。假設(shè)測量誤差的變化范圍是從0%到20%。節(jié)點一跳的范圍為50 m之內(nèi)。

經(jīng)過多次實驗認為，在 TreeThres4=和CountThres30=時，能夠有效地尋找到渡口節(jié)點，且這些節(jié)點的幾何特性較為明顯的出現(xiàn)連接山頂和山腳的傾向。在實驗數(shù)據(jù)中，均采用了上面的取值。由于部署并非十分密集，認為跳數(shù)范圍為k無窮大。

定位誤差：為節(jié)點的實際位置和預(yù)測位置之間的歐幾里得距離。其中，(x,y,z)是節(jié)點的實際坐標(biāo)，(xe,ye,ze)是節(jié)點的估測坐標(biāo)。定義為：

地形模型誤差：zi是節(jié)點的實際坐標(biāo)位置，zei是節(jié)點的測量位置。定義如下：

3.2 定位率

圖4所示的是3DT-ST算法和SV算法、MDS-MAP算法的定位率結(jié)果對比圖。

實驗結(jié)果表明，在測距誤差較大時，部署節(jié)點數(shù)量分別為1 000、2 000、4 000時，3DT-ST算法和最新SV算法的定位率大致相當(dāng)，比MDS-MAP的定位率高出很多。

3.3 定位誤差

圖5展示了在復(fù)雜3D凹/凸不平表面網(wǎng)絡(luò)中3DT-ST算法和SV算法、MDS-MAP算法平均定位誤差的比較情況。由于MDS-MAP算法在擴展到3D復(fù)雜網(wǎng)絡(luò)中時本身存在很大的誤差，所以簡單的將MDS-MAP算法升級使用到復(fù)雜3D凹/凸不平表面網(wǎng)絡(luò)中是不可取的。

結(jié)果顯示，3DT-ST算法在測距誤差較大時，依然能得到更有意義的效果。3DT-ST算法定位率上有較大的優(yōu)勢，在測距誤差為5%，部署節(jié)點數(shù)量分別為1 000、2 000、4 000時，相比SV算法平均定位誤差分別減小80.6%、86.3%和81.6%。從而可以得出，3DT-ST算法定位誤差與網(wǎng)絡(luò)的節(jié)點數(shù)沒有直接的關(guān)系。從實驗結(jié)果可以看出，由于3DT-ST算法經(jīng)過特殊節(jié)點選取和三角劃分策略的設(shè)計，所得的平面化效果較好，對測量誤差有一定的容錯能力，在測距誤差逐漸增大的時候，對定位精度的影響較小。同時，在測量時由于節(jié)點部署和選擇泛洪節(jié)點的隨機性，得到的結(jié)果也具有一定的隨機性，采用了多次測量的平均值。這說明3DT-ST算法具有較強的健壯性。

3.4 計算負荷量

圖6展示了在不同情況下3DT-ST的計算時間。測試的計算機使用的是奔騰 G620處理器，4 G內(nèi)存，32位Windows操作系統(tǒng)和 Matlab2012b。針對1 000、1 500、2 000、4 000個節(jié)點進行測試。取3次測試的平均數(shù)，得到的結(jié)果如圖6所示。

以計算時間為標(biāo)準，橫坐標(biāo)為節(jié)點個數(shù)，縱坐標(biāo)為計算機負荷量，單位為s。實驗結(jié)果顯示，隨著網(wǎng)絡(luò)規(guī)模的增大，計算的時間隨之增加，這是由于在節(jié)點數(shù)更多的情況下，需要耗費更多的能量去計算各個節(jié)點之間的距離。但是僅從計算的消耗量來看，3DT-ST的計算負荷在一個可以接受的范圍內(nèi)，并且適合于大規(guī)模復(fù)雜環(huán)境下的WSN應(yīng)用。和其他一些算法(如CATL算法和SV算法等)相比，本文提出的3DT-ST算法不需要迭代，避免了因迭代次數(shù)不夠而帶來的誤差，同時避免了在大規(guī)模復(fù)雜網(wǎng)絡(luò)上，隨著迭代次數(shù)增加而計算負荷量(計算開銷)顯著增加的問題。

4 結(jié) 論

3DT-ST算法不需要配備任何復(fù)雜的硬件傳感器(如氣壓傳感器等)，且定位過程中無需錨節(jié)點的，僅靠網(wǎng)絡(luò)的連通性和特殊節(jié)點來定位，節(jié)點只需要感知到通信半徑內(nèi)的其他節(jié)點，對硬件要求低，不易受環(huán)境影響，這樣大大降低了網(wǎng)絡(luò)的部署成本。同時，3DT-ST算法在定位過程中不需要迭代過程，在復(fù)雜山體表面上能有效地降低計算開銷并得到較好的定位效果。

[1] SAHU P K, WU E H K, SAHOO J, et al. RSSI trend based localization for wireless sensor networks[J]. Sensor Journal, IEEE, 2013, 13(8): 3115-3123.

[2] HE T, HUANG C, BLUM B M, et al. Range-free localization schemes for large scale sensor networks[C]// Proceedings of the 9th annual international conference on mobile computing and networking. [S.l.]: ACM, 2003: 81-95.

[3] 王瑞錦, 秦志光, 王佳昊. 無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議分析[J]. 電子科技大學(xué)學(xué)報, 2013, 42(3): 400-405. WANG Rui-jin, QIN Zhi-guang, WANG Jia-hao. Analysis of wireless sensor network cluter routing protocol[J]. Journal of University of Electronic Science and Technology of China, 2013, 42(3): 400-405.

[4] ZHOU H, WU H, JIN M. A robust boundary detection algorithm based on connectivity only for 3D wireless sensor networks[C]//INFOCOM, 2012 Proceedings IEEE. [S.l.]: IEEE, 2012: 1602-1610.

[5] WANG J, HUANG L, LI X, et al. A collaborative localization scheme from connectivity in wireless sensor networks[C]//Wired/Wireless Internet Communications. Berlin, Heidelberg: Springer, 2008: 213-223.

[6] 王瑞錦, 秦志光, 包紅來, 等. 基于三角劃分的復(fù)雜3D山體表面定位算法[J]. 計算機應(yīng)用研究, 2013, 30(9): 2823-2826. WANG Rui-jin, QIN Zhi-guang, BAO Hong-lai, et al. Triangulation-based localization algorithm over complex 3D terrains[J]. Application Research of Computer, 2013, 30(9): 2823-2826.

[7] WANG Rui-jin, QIN Zhi-guang, ZHANG Y, et al. A weighted 3D localization algorithm based on partial HopSize in wireless sensor network[J]. International Journal of Advancements in Computing Technology, 2012, 4(17): 110-120.

[8] CHACZKO Z, KLEMPOUS R, NIKODEM J, et al. Methods of sensors localization in wireless sensor networks[C]//14th Annual IEEE International Conference and Work-shops on the En-gineering of Computer-Based Systems, 2007. [S.l.]: IEEE, 2007: 145-152.

[9] ZHANG L, ZHOU X, CHENG Q. Landscape-3D: a robust localization scheme for sensor networks over complex 3D terrains[C]//31st IEEE Conference on Local Computer Networks. [S.l.]: IEEE, 2006: 239-246.

[10] NICULESCU D, NATH B. DV based positioning in Ad hoc networks[J]. Telecommunication Systems, 2003, 22(1-4): 267-280.

[11] WANG R J, ZHANG B, SHEN Y, et al. PHDV-Hop: a more accurate DV-Hop positioning algorithm in WSN[J]. International Journal of Digital Content Technology & its Applications, 2012, 6(13): 89-97.

[12] WANG R J, QIN Z G, ZHANG Y, et al. A weighted 3D localization algorithm based on partial HopSize in wireless sensor network[J]. International Journal of Advancements in Computing Technology, 2012, 4(17): 504-513.

[13] SHANG Y, RUML W. Improved MDS-based localization [C]//INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies. [S.l.]: IEEE, 2004: 2640-2651.

[14] AHMED A A, SHI H, SHANG Y. Sharp: a new approach to relative localization in wireless sensor net-works[C]// 25th IEEE International Conference on Distributed Computing Systems Workshops, 2005. [S.l.]: IEEE, 2005: 892-898.

[15] TAN G, JIANG H, ZHANG S, et al. Connectivity-based and anchor-free localization in large-scale 2d/3d sensor networks[J]. ACM Transactions on Sensor Networks (TOSN), 2013, 10(1): 6-7.

[16] ZHAO Y, WU H, JIN M, et al. Localization in 3D surface sensor networks: Challenges and solutions[C]//INFOCOM, 2012 Proceedings IEEE. [S.l.]: IEEE, 2012: 55-63.

[17] LIU W, WANG D, JIANG H, et al. Approximate convex decomposition based localization in wireless sensor net-works[C]//INFOCOM, 2012 Proceedings IEEE. [S.l.]: IEEE, 2012: 1853-1861.

[18] WANG R J, BAO H L, CHEN D J, et al. 3D-CCD: a novel 3D localization algorithm based on concave/convex decomposition and layering scheme in WSNs[J]. Ad hoc & Sensor Wireless Networks, 2014, 23: 235-254.

編 輯 蔣 曉

Localization Algorithm in Wireless Sensor Networks Over Complex Terrains

WANG Rui-jin1, HUANG Yao-dong2, XU Zhi-yuan2, and QIN Zhi-guang1
(1. School of Information and Software Engineering , University of Electronic Science and Technology of China Chengdu 611731;2. School of Computer Science and Engineering, University of Electronic Science and Technology of China Chengdu 611731)

In order to solve the problem that it is expensive and difficult to deploy anchor nodes on three-dimension(3D) complex concave/convex surface, a new triangulation localization algorithm (called 3DT-ST) which is based anchor free and applies to complex 3D terrain is presented. 3DT-ST only utilizes network connection and special nodes (SPN) to triangulate and model. It establishes local relative maps in every triangle areas, then combine triangle together to get global map of the network. Experiments show that when comparing with SV, 3DT-ST reduces the localization error clear, and localization is an iteration-free process with only the information of network connection. It improves the localization accuracy, lowers the localization error, and saves the cost of network deploying as well. It provides a new method on energy saving localization research over complex networks.

complex environment localization; special node identification; triangulation division; wireless sensor networks

TP309.3

A

10.3969/j.issn.1001-0548.2015.03.020

2013 ? 12 ? 15；

2014 ? 03 ? 20

國家自然科學(xué)基金(60903157) ；四川省科技廳計劃項目(2015JY0178)；中央高校基本科研業(yè)務(wù)費專項資金(ZYGX2014J051，ZYGX2011J066)

王瑞錦(1980 ? )，男，博士，主要從事無線傳感網(wǎng)、信息安全、量子安全等方面的研究.