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

王瑞錦，黃耀東，徐志遠(yuǎn)，秦志光

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

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

王瑞錦1，黃耀東2，徐志遠(yuǎn)2，秦志光1

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

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

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

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

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

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

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

1 相關(guān)研究

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

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

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

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

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

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

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

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

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

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

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

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

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

然后，計(jì)算每個(gè)節(jié)點(diǎn)的綜合影響因子，節(jié)點(diǎn)p的綜合影響因子為：

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

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

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

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

算法 1 Find SPN node//尋找特殊渡口節(jié)點(diǎn)(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é)點(diǎn)連起來(lái)形成德勞內(nèi)三角形。圖3展示了根據(jù)SPN進(jìn)行三角化的結(jié)果。從圖中可以看出，劃分出的三角子網(wǎng)平整，規(guī)則，能夠體現(xiàn)復(fù)雜山體表面的特征，并且能夠較好地覆蓋復(fù)雜山體表面區(qū)域。

2.3 獲取局部相對(duì)位置

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

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

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

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

2.4 建立全局地理位置

根據(jù)文獻(xiàn)[6]，本文采用網(wǎng)絡(luò)的鄰接約束圖ACG[19]。每個(gè)點(diǎn)i代表一個(gè)三角子區(qū)域 Subi，如果Subi和 Subi是鄰近的兩個(gè)子區(qū)域，則 i,j也是鄰居節(jié)點(diǎn)。定義 di為與 Subi三角網(wǎng)相鄰的區(qū)域的數(shù)量，稱為 Subi的度。每個(gè)節(jié)點(diǎn) i賦權(quán)重 wi， wi值為三角網(wǎng) Subi中的節(jié)點(diǎn)數(shù)量， nij表示公共線段上的節(jié)點(diǎn)個(gè)數(shù)。然后按照下列算法建立全局地圖，三角網(wǎng) Subi中節(jié)點(diǎn)的坐標(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)，兩個(gè)相鄰的三角網(wǎng)被合并，直到所有三角網(wǎng)合并成一個(gè)大的區(qū)域后停止算法，輸出為全局地圖，完成全網(wǎng)絡(luò)的節(jié)點(diǎn)定位。

3 實(shí)驗(yàn)及性能評(píng)估

本節(jié)通過(guò)實(shí)驗(yàn)對(duì)本文提出的3DT-ST算法，從節(jié)點(diǎn)密度、定位誤差和計(jì)算能耗等方面來(lái)驗(yàn)證方法的可行性和魯棒性，并與最新的SV和MDS-MAP定位算法進(jìn)行性能分析對(duì)比。

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

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

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

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

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

3.2 定位率

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

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

3.3 定位誤差

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

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

3.4 計(jì)算負(fù)荷量

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

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

4 結(jié) 論

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

[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ú)線傳感器網(wǎng)絡(luò)分簇路由協(xié)議分析[J]. 電子科技大學(xué)學(xué)報(bào), 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] 王瑞錦, 秦志光, 包紅來(lái), 等. 基于三角劃分的復(fù)雜3D山體表面定位算法[J]. 計(jì)算機(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

國(guó)家自然科學(xué)基金(60903157) ；四川省科技廳計(jì)劃項(xiàng)目(2015JY0178)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金(ZYGX2014J051，ZYGX2011J066)

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