胡中棟，謝金偉

(江西理工大學(xué) 信息工程學(xué)院，江西 贛州341000)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)在智能生活、環(huán)境監(jiān)測、軍事偵察、災(zāi)難預(yù)防和生物統(tǒng)計(jì)等領(lǐng)域都有著廣泛使用。因帶有GPS 功能的無線傳感器的價(jià)格較高，所以，部署的傳感器有較大部分無法確定自己的位置，而無法確定位置的傳感器在大部分情況下不具有實(shí)際意義。隨著無線傳感器的廣泛使用，無線傳感器的定位便成為了研究的熱點(diǎn)。起初主要研究二維的無線傳感器的定位，文獻(xiàn)［1］總結(jié)了一些典型的二維定位算法。隨著應(yīng)用的要求越來越高，無線傳感器二維定位已無法滿足生產(chǎn)的需要，三維定位就成為了研究的熱點(diǎn)。有許多學(xué)者都提出了三維無線傳感器網(wǎng)絡(luò)定位算法，其中有些是二維定位的延伸，有些是專為三維定位而設(shè)計(jì)的算法。近似三角形內(nèi)點(diǎn)測試(APIT)算法是二維定位中常用的算法，在文獻(xiàn)［2］中APIT 算法被擴(kuò)展到了三維;Constrained 3D［3］算法是利用三角計(jì)算的方法，通過自身與錨節(jié)點(diǎn)之間的距離來推算自身的距離;戴桂蘭等人［4］將最小二乘法引入了球面三維定位中;江禹生等人［5］引入了位置估算偏差值，利用加權(quán)質(zhì)心算法進(jìn)行位置估算。

適應(yīng)山頭地形的無線傳感器網(wǎng)絡(luò)三維定位算法首先用三維DV-Hop 定位算法求出未知節(jié)點(diǎn)的初始位置P，然后，將P 點(diǎn)投影到山頭地形表面上，用該投影點(diǎn)代替原計(jì)算結(jié)果，較好地修正了計(jì)算結(jié)果，提高了無線傳感器網(wǎng)絡(luò)在山頭地形中的定位精度。

1 三維DV－Hop 定位算法

1.1 DV-Hop 算法

DV-Hop 算法是由Niculescu D 等人提出的，此算法利用了距離矢量路由原理來具體實(shí)現(xiàn)［6，7］。算法的具體步驟為:

1)計(jì)算無線傳感網(wǎng)絡(luò)中所有節(jié)點(diǎn)之間的最小跳數(shù)。

2)錨節(jié)點(diǎn)通過自身的位置和其與其他錨節(jié)點(diǎn)之間的位置計(jì)算出平均每跳距離。

3)未知節(jié)點(diǎn)通過到錨節(jié)點(diǎn)之間的最小跳數(shù)估算自己到所有錨節(jié)點(diǎn)的距離。

4)通過最小二乘法(極大似然估計(jì)法)或四邊測量法計(jì)算自身坐標(biāo)［8］。

最小二乘法求解方程組具體步驟如下［9］:

1)設(shè)未知節(jié)點(diǎn)的坐標(biāo)為(x，y，z)，由三維DV-Hop 算法可得到未知節(jié)點(diǎn)到n(n≥4)個(gè)錨節(jié)點(diǎn)的距離為d1，d2，…dn，且已知對(duì)應(yīng)錨節(jié)點(diǎn)的坐標(biāo)為(x1，y1，z1)，(x2，y2，z2)，…，(xn，yn，zn)。

2)由已知條件可以得到矛盾方程組［9］

其中

3)若矛盾方程組有解，則可得

龍?zhí)祝步形奶?，是傳統(tǒng)戲曲中扮演兵卒、夫役等群眾角色的統(tǒng)稱；由于所穿都是各色龍?zhí)滓嘛椂妹，F(xiàn)在大家將其引申為各類組織、團(tuán)體或班子中的邊緣角色或非主要角色。與龍?zhí)讓?duì)應(yīng)的是主角，主角光彩奪目，龍?zhí)拙惋@得黯然失色。

1.2 性能評(píng)價(jià)

用相對(duì)定位誤差來判斷定位算法的優(yōu)劣，具體計(jì)算方法為［10］:

若某個(gè)未知節(jié)點(diǎn)的估算坐標(biāo)為(xi，yi，zi)，實(shí)際坐標(biāo)為(ai，bi，ci)，則兩個(gè)坐標(biāo)的差距Δdi可表示為

相對(duì)定位誤差不僅與估算坐標(biāo)與實(shí)際坐標(biāo)之間的距離有關(guān)，還和無線傳感器節(jié)點(diǎn)的通信半徑R 有關(guān)，則無線傳感器網(wǎng)絡(luò)中n 個(gè)未知節(jié)點(diǎn)的平均定位誤差Δ 可表示為

2 適應(yīng)山頭地形的三維定位算法

為了方便投影操作，截取部分球體模擬山頭，如圖1 所示。H 表示山體的高度，可以看到，不同的H 值可以模擬不同坡度的山頭。

圖1 山頭模型Fig 1 Hilltop model

投影方法如圖2 所示，當(dāng)所估算的位置節(jié)點(diǎn)的坐標(biāo)位置在山體內(nèi)部，如圖2 中的A 點(diǎn)所示，過圓心O 點(diǎn)和A 點(diǎn)作直線 與山體交于B 點(diǎn)，B 點(diǎn)即為效正后的未知節(jié)點(diǎn)的坐標(biāo)點(diǎn)。若所估算的節(jié)點(diǎn)坐標(biāo)位置在山體外，如圖2 中C 點(diǎn)所示，作直線L2，則可得到投影效正后的未知節(jié)點(diǎn)的坐標(biāo)點(diǎn)為圖中的D 點(diǎn)。

圖2 投影方法Fig 2 Projection method

在如圖2 所示的坐標(biāo)系中，設(shè)圓的半徑為R，圓心在坐標(biāo)原點(diǎn)。設(shè)用三維DV-Hop 算法所求未知節(jié)點(diǎn)的坐標(biāo)為X=(a，b，c)，則可以得到過坐標(biāo)原點(diǎn)和X 點(diǎn)的直線L。由直線L 與圓方程聯(lián)立，且在z≥0 的條件下可求出唯一投影點(diǎn)X'，X'即為投影效正后的未知節(jié)點(diǎn)坐標(biāo)，具體方程式如下:

以坐標(biāo)原點(diǎn)為起點(diǎn)且過X 點(diǎn)的射線方程式為

半圓球的方程式為

3 仿真實(shí)驗(yàn)

采用Matlap 對(duì)本文設(shè)計(jì)的適應(yīng)地形的投影算法進(jìn)行了仿真實(shí)驗(yàn)。為了驗(yàn)證算法的有效性，實(shí)驗(yàn)分為山頭高度不同、信標(biāo)節(jié)點(diǎn)比例不同與節(jié)點(diǎn)總數(shù)不同三種情況進(jìn)行了對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)中圓半徑R 設(shè)為50 m，信標(biāo)節(jié)點(diǎn)的通信半徑設(shè)置為20 m，其它參數(shù)根據(jù)不同的情況進(jìn)行設(shè)置，節(jié)點(diǎn)隨機(jī)分布如圖3 所示。

圖3 傳感器節(jié)點(diǎn)隨機(jī)分布圖Fig 3 Randomly distributed map of sensor nodes

1)不同山頭高度的實(shí)驗(yàn)

實(shí)驗(yàn)中的無線傳感器總數(shù)為200，信標(biāo)節(jié)點(diǎn)數(shù)為20，占總節(jié)點(diǎn)數(shù)的10%。圖2 中的H 分別設(shè)置為20，25，30，35，40，45，50 m 的情況下進(jìn)行實(shí)驗(yàn)，對(duì)每種不同的山頭高度H均進(jìn)行100 次實(shí)驗(yàn)，每次實(shí)驗(yàn)的傳感器節(jié)點(diǎn)都是隨機(jī)分布的，實(shí)驗(yàn)結(jié)果如圖4 所示。

圖4 不同山頭高度的平均定位誤差Fig 4 Average localization error with different hilltop height

從圖4 可以看到經(jīng)過投影修正處理的定位精度有明顯的提高。在不同的山頭高度的情況下，典型的三維DV-Hop定位誤差為60%左右，在實(shí)際應(yīng)用中有較大的偏差，而經(jīng)過投影修正后的定位誤差僅為30%左右，較大幅度提高了節(jié)點(diǎn)定位精度。

2)信標(biāo)節(jié)點(diǎn)比例不同的實(shí)驗(yàn)

實(shí)驗(yàn)中H 的值設(shè)定為35 m，傳感器總節(jié)點(diǎn)數(shù)設(shè)置為200，信標(biāo)節(jié)點(diǎn)的比例分別為5%，10%，15%，20%，25%，30%和35%進(jìn)行對(duì)比實(shí)驗(yàn)，對(duì)每種不同比例分別進(jìn)行100 次模擬實(shí)驗(yàn)，每次實(shí)驗(yàn)的傳感器節(jié)點(diǎn)分布都是隨機(jī)的，實(shí)驗(yàn)結(jié)果如圖5 所示。

由圖5 可知，不論是典型的三維DV-Hop 定位算法，還是投影改進(jìn)后的定位算法，隨著錨節(jié)點(diǎn)比例的增加，定位精度也相應(yīng)提高，當(dāng)錨節(jié)點(diǎn)比例增加到15%之后，精度便不再明顯提高，這可以為傳感器節(jié)點(diǎn)的合理部署提供參考。而經(jīng)過投影處理的定位誤差明顯減小，當(dāng)錨節(jié)點(diǎn)比例較合理時(shí)，定位誤差僅為30%左右。

3)傳感器節(jié)點(diǎn)數(shù)不同的實(shí)驗(yàn)

圖5 不同錨節(jié)點(diǎn)比例的平均定位誤差Fig 5 Average localization error with different anchor node proportion

實(shí)驗(yàn)中，H 的值設(shè)定為35 m，信標(biāo)節(jié)點(diǎn)的比例保持為10%不變，在傳感器節(jié)點(diǎn)總數(shù)分別為140，150，160，170，180，190，200 的情況下進(jìn)行對(duì)比實(shí)驗(yàn)，對(duì)每種不同傳感器節(jié)點(diǎn)總數(shù)分別進(jìn)行100 次實(shí)驗(yàn)，每次實(shí)驗(yàn)時(shí)傳感器節(jié)點(diǎn)分布都是隨機(jī)的，實(shí)驗(yàn)結(jié)果如圖6 所示。

圖6 不同節(jié)點(diǎn)總數(shù)的平均定位誤差Fig 6 Average localization error with different node numbers

通過實(shí)驗(yàn)可知，典型的三維DV-Hop 定位算法和經(jīng)過投影處理的定位算法都是總節(jié)點(diǎn)數(shù)越多，定位誤差越小。典型的三維DV-Hop 定位算法的定位誤差在65%左右，而經(jīng)過投影處理的定位算法的定位誤差僅為35%左右，當(dāng)節(jié)點(diǎn)數(shù)為200 時(shí)，定位誤差已經(jīng)小于30%。

4 結(jié) 論

在經(jīng)典的三維DV-Hop 的定位算法基礎(chǔ)上，應(yīng)用地形的特點(diǎn)，對(duì)經(jīng)典算法所求的結(jié)果進(jìn)行投影優(yōu)化，有效地利用了外部環(huán)境的特點(diǎn)。通過多角度的仿真對(duì)比實(shí)驗(yàn)證明:在不增加任何其他硬件設(shè)備的前提下，有效降低了定位誤差，提高了無線傳感器網(wǎng)絡(luò)非測距定位算法精度。本文所用的實(shí)例雖然有一定的局限性，但較好地體現(xiàn)了投影修正的思想，為下一步實(shí)際山區(qū)地形的無線傳感器節(jié)點(diǎn)定位研究奠定了基礎(chǔ)。

［1］ 王福豹，史 龍，任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法［J］.軟件學(xué)報(bào)，2005，16(5):857-868.

［2］ 劉玉恒，蒲菊華，赫 陽.無線傳感器網(wǎng)絡(luò)三維自身定位方法［J］.北京航天航空大學(xué)學(xué)報(bào)，2008，34(6):647-651.

［3］ Liang J L，Shao J，Xu Y，et al.Sensor network localization in constrained 3D spaces［C］∥Proc of IEEE International Conference on Mechatronics and Automation，Luoyang:IEEE，2006:49-54.