無(wú)線傳感器網(wǎng)絡(luò)中定位技術(shù)的研究*

鹿建銀，王華本

(安徽新華學(xué)院)

0 引言

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)是近年來(lái)一個(gè)熱點(diǎn)研究領(lǐng)域，其中傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)也越來(lái)越受到人們的關(guān)注，這是因?yàn)閭鞲衅骶W(wǎng)絡(luò)的大量應(yīng)用都依賴于節(jié)點(diǎn)的位置信息，應(yīng)用在軍事領(lǐng)域，如對(duì)敵方坦克、步兵等各種軍事力量進(jìn)行定位和跟蹤，以便做出相應(yīng)決策;在智能醫(yī)療中，實(shí)現(xiàn)資源共享、互相協(xié)作、臨床診斷等;可對(duì)山體、河流等監(jiān)控對(duì)象，通過(guò)采集監(jiān)控對(duì)象微觀變化，為研究人員提供可靠的研究信息，如保護(hù)黃山迎客松，用監(jiān)測(cè)迎客松周圍環(huán)境的光照、濕度、風(fēng)速、雨雪感知和土壤水分等信息;此外，無(wú)線傳感器網(wǎng)絡(luò)在零售、物流、食品、建筑、電網(wǎng)、家居、交通［1-2］等行業(yè)，也有著廣泛的應(yīng)用.因此，研究無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)具有重要意義.

1 經(jīng)典無(wú)線傳感器網(wǎng)絡(luò)定位技術(shù)研究

全球定位技術(shù):70年代，由美國(guó)海陸空三軍聯(lián)合研制的全球定位系統(tǒng)(Global Positioning System，GPS)［3］，由24 顆人造衛(wèi)星組成，到 1993年共耗資300億美金，定位精度可達(dá)到15 m以內(nèi)，覆蓋范圍達(dá)到地球表面的98%，但是為網(wǎng)絡(luò)中所有節(jié)點(diǎn)都安裝 GPS設(shè)備，會(huì)受到成本、功耗、擴(kuò)展性等問(wèn)題的限制，甚至在某些場(chǎng)合如室內(nèi)幾乎無(wú)法實(shí)現(xiàn).局部定位算法:基于RFID［4-5］技術(shù)，由于設(shè)備識(shí)別的傳輸距離有限，主要用于物流、物品跟蹤、人員登記等領(lǐng)域.WiFi定位算法，類似于Zigbee定位技術(shù)，但是相對(duì)于Zigbee，WiFi的突出優(yōu)勢(shì)在于數(shù)據(jù)傳輸速率更快，更易互聯(lián)，較易實(shí)現(xiàn)交互性.超寬帶(Ultra-Wideband，UWB)［6］是一種無(wú)載波通信技術(shù)，穿透能夠強(qiáng)，最終的定位精度能夠達(dá)到厘米級(jí)別，但目前技術(shù)尚不成熟.測(cè)距定位算法:主要有接收信號(hào)強(qiáng)度 (Received Signal Strength Indicator，RSSI)算法、到達(dá)時(shí)間 (Time of Arrival，TOA)算法、到達(dá)角度(Angle of Arrival，AOA)算法、到達(dá)時(shí)間差(Time Difference of Arrival，TDOA)算法等.測(cè)距定位機(jī)制由于借助節(jié)點(diǎn)之間的距離或者角度信息，通常定位精度相對(duì)較高，但同時(shí)也要求硬件支撐.非測(cè)距算法:由南加州大學(xué)Nirupama Bulusu等提出的一種基于網(wǎng)絡(luò)連通性的質(zhì)心算法(Weighted Centroid)，該算法僅能實(shí)現(xiàn)粗粒度的定位，且要求有較高的錨節(jié)點(diǎn)密度才能實(shí)現(xiàn)精確定位.由弗吉尼亞大學(xué)He等人提出的近似三角形內(nèi)點(diǎn)測(cè)試(Approximate Point-In-Triangulation Test，APIT)定位算法，定位精度相對(duì)較高，但需要較高的錨節(jié)點(diǎn)密度和較高的節(jié)點(diǎn)密度.哥倫比亞大學(xué)Shang Yi等人提出的基于多維標(biāo)度(Multidimensional Scaling，MDS)定位算法，用迭代優(yōu)化來(lái)提高定位精度等.非測(cè)距定位受環(huán)境影響較小，硬件成本低，適合于大規(guī)模網(wǎng)絡(luò)［7-8］.

2 DV-Hop定位算法分析

2.1 DV-Hop定位算法原理

DV-Hop定位算法原理與距離向量路由算法的思想非常相似，其算法過(guò)程分為三個(gè)階段:第一階段，先使用典型的距離矢量交換協(xié)議，使網(wǎng)絡(luò)中所有節(jié)點(diǎn)獲取與錨節(jié)點(diǎn)的跳數(shù)值.

第一階段結(jié)束后，所有節(jié)點(diǎn)都會(huì)獲取一個(gè)到錨節(jié)點(diǎn)的最小跳數(shù)值.

第二階段，如式(1)所示:用hdi來(lái)計(jì)算錨節(jié)點(diǎn)i和周圍待測(cè)節(jié)點(diǎn)的距離.

式中(Xi，Yi)、(Xj，Yj)是錨節(jié)點(diǎn) i、j的坐標(biāo)值，h(i，j)是錨節(jié)點(diǎn)i與錨節(jié)點(diǎn)j之間的跳數(shù).第二階段結(jié)束后平均每跳距離的估算值可以計(jì)算出真實(shí)距離.

第三階段，當(dāng)待測(cè)節(jié)點(diǎn)獲得3個(gè)或更多錨節(jié)點(diǎn)的距離后，利用三邊測(cè)量法(或者極大似然法)計(jì)算其位置，如式(2)所示:

式(2)是計(jì)算某待測(cè)節(jié)點(diǎn)坐標(biāo)的二元二次方程組，理論上最少已知三個(gè)錨節(jié)點(diǎn)坐標(biāo)即可保證方程組能求出唯一一組解.

由式(2)得到的展開(kāi)式(3)如下:

將式(3)采用矩陣AX=b方式表示，推導(dǎo)出式(4):

最小方差矩陣估算待測(cè)節(jié)點(diǎn)的坐標(biāo)如式(5)所示:

2.2 改進(jìn)算法

2.2.1 最小均方誤差準(zhǔn)則

式(6)是基于無(wú)偏估計(jì)準(zhǔn)則計(jì)算平均每跳距離公式，即式(7)恒等于零.

式(7)中N表示錨節(jié)點(diǎn)個(gè)數(shù)，估計(jì)誤差均值為零，然而，根據(jù)參數(shù)估計(jì)理論，使用均方誤差比使用方差更合理.因此，提出基于最小均方誤差準(zhǔn)則來(lái)計(jì)算平均每跳距離，如式(8)所示:

2.2.2 錨節(jié)點(diǎn)選擇策略

如圖1所示，平面上任意三點(diǎn)組成的三角形，如果最長(zhǎng)邊用lmax，那么該邊所對(duì)應(yīng)的高則為最小的高用hmin表示.選擇hmin與lmax的比值來(lái)衡量三角形的共線程度，簡(jiǎn)稱共線度，并用DC表示，如式(10)表示:

圖1 三角形共線度示意圖

通過(guò)分析，共線度的取值范圍為［0，1］，并且共線度取值越小表示三點(diǎn)越接近共線程度:當(dāng)三點(diǎn)完全共線時(shí)，三角形退化，此時(shí)的共線度為0;當(dāng)是等邊三角形時(shí)，共線度值為1.在實(shí)際的錨節(jié)點(diǎn)選擇過(guò)程中，可以通過(guò)設(shè)定三角形共線度來(lái)約束錨節(jié)點(diǎn)之間的拓?fù)潢P(guān)系，過(guò)濾掉使定位誤差較大的節(jié)點(diǎn)，優(yōu)化通信范圍與跳距之間的關(guān)系，提高定位精度.

3 仿真結(jié)果及分析

該課題的仿真環(huán)境是WINDOWS XP操作系統(tǒng)，JDK6.0版本，仿真軟件OMNeT++4.1，通信半徑為100;測(cè)試區(qū)域?yàn)橐粋€(gè)800×500的平面，30個(gè)節(jié)點(diǎn)隨機(jī)分布在該區(qū)域內(nèi).仿真了相對(duì)定位誤差，平均定位誤差兩種情況.在仿真過(guò)程中，為了不失一般性，DV-Hop定位誤差和改進(jìn)算法后的定位誤差，皆取同一分布，結(jié)果取5次仿真結(jié)果的平均值.

圖2 相對(duì)定位誤差示意圖

從圖2相對(duì)定位誤差示意圖中可以看出，在相同的通信半徑和錨節(jié)點(diǎn)比例下，改進(jìn)算法的節(jié)點(diǎn)相對(duì)定位誤差減小.由圖3平均定位誤差示意圖可知，在相同通信半徑和相同錨節(jié)點(diǎn)比例的情況下，改進(jìn)算法節(jié)點(diǎn)定位均方差優(yōu)于DV-HOP算法.

圖3 平均定位誤差示意圖

4 總結(jié)與展望

針對(duì)DV-HOP定位算法的定位精度不高的局限性，提出了一種改進(jìn)算法，該算法在距離估計(jì)和定位計(jì)算兩方面進(jìn)行改進(jìn)，并通過(guò)改進(jìn)錨節(jié)點(diǎn)選擇策略，優(yōu)化網(wǎng)絡(luò)拓?fù)浣Y(jié)果，調(diào)整通信范圍和跳數(shù)之間的關(guān)系.仿真結(jié)果表明在不同的通信范圍和參考節(jié)點(diǎn)比例下改進(jìn)方法有效地減少了節(jié)點(diǎn)定位誤差.

在后期的工作中研究算法在提高定位精度的同時(shí)，考慮如何減少節(jié)點(diǎn)的通信量和計(jì)算量，從而最大程度地延長(zhǎng)網(wǎng)絡(luò)的壽命和提高算法的實(shí)用價(jià)值.

［1］ 崔麗，劉強(qiáng)，李棟.物聯(lián)網(wǎng)系統(tǒng)及核心設(shè)備［J］.中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊，2010(4):18-22.

［2］ Guo Zhongwen，Guo Ying，Hong Feng，et al.“Perpendicular Intersection:Locating Wireless Sensors with Mobile Beacon”.29th IEEE Real-Time Systems Symposium RTSS，2008.93-102.

［3］ 張明華.基于WLAN室內(nèi)定位技術(shù)研究［D］.上海交通大學(xué)，2009:50-56.

［4］ 李德仁，龔健雅，邵振峰.從數(shù)字地球到智慧地球［J］.武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2010，35(2):127-132.

［5］ Wang F，Liu S，Liu P.Complex RFID event processing［J］.The VLDB Journal，2009，18，913-931.

［6］ Wu D，Bao L，Du M，et al.Design and Evaluation of Localization Protocols and Algorithms in Wireless Sensor Networks Using UWB.Performance［C］.Computing and Communications Conference(IPCCC)，Austin，Texas，USA，7-9 Dec，2008:18-25.

［7］ Shen Mingyu，Zhang Yin.DV-HOP localization algorithm based on improved average hop distance and estimate of distance［J］.Application Research of Computers，2011，28(2):648-650.

［8］ Wang Xinsheng，Zhao Yanjing，Li Haitao.Improved study based on DV-HOP localization algorithm［J］.Computer Science，2011，38(2):76-78.