基于加權(quán)和RSSI測距的DV?Hop定位算法

吳之舟，張玲華

（南京郵電大學(xué)通信與信息工程學(xué)院，南京 210023）

引 言

無線傳感器網(wǎng)絡(luò)（Wireless sensor network，WSN）拓展了人類與物理世界的交互方式，是近20年通信技術(shù)發(fā)展的一個(gè)新研究領(lǐng)域，基于其成本低、功耗低和環(huán)境要求低的優(yōu)點(diǎn)，在工業(yè)、農(nóng)業(yè)和商業(yè)中都有著廣泛的應(yīng)用。在這個(gè)巨大的無線網(wǎng)絡(luò)中，可以說沒有節(jié)點(diǎn)定位就沒有傳感器網(wǎng)絡(luò)。因此，在組成WSN的各種技術(shù)中，定位技術(shù)是最關(guān)鍵技術(shù)之一［1］。

定位算法分為基于測距和非測距兩類［2］，基于測距的定位算法主要有到達(dá)時(shí)間（Time of arrival，TOA）、到達(dá)時(shí)間差（Time difference on arrival，TDOA）和接收信號(hào)強(qiáng)度（Received signal strength indica?tor，RSSI）等。其中TOA和TDOA是以獲得測量距離為前提的算法，具有相對較高的定位精度，但是對硬件的要求很高，成本高并且受到測距技術(shù)的限制。而RSSI算法是通過節(jié)點(diǎn)間的信號(hào)強(qiáng)度來估算未知節(jié)點(diǎn)，因此它無須額外硬件開銷，但是在信號(hào)傳播中對環(huán)境、地形因素要求較高，定位精度受到信道衰弱、多徑效應(yīng)的影響較大。相比之下，非測距定位算法是利用節(jié)點(diǎn)間估計(jì)距離來計(jì)算未知節(jié)點(diǎn)，主要 算 法 有 質(zhì) 心 算 法、近 似 三 角 形 內(nèi) 點(diǎn) 測 試 法（Approximate point?in?triangulation test，APIT）及DV?Hop［3］等。非測距方法的成本和功耗低，但是定位誤差大，這兩類定位算法可以說各有優(yōu)缺點(diǎn)。因此，眾多學(xué)者針對DV?Hop定位算法展開研究并取得了一些理論成果。文獻(xiàn)［4］通過定義理想跳數(shù)、偏差系數(shù)和修正因子來改進(jìn)跳數(shù)，在一種全新的極值更新方式的基礎(chǔ)上提出了改進(jìn)粒子群算法，并用于計(jì)算未知節(jié)點(diǎn)坐標(biāo)，有效提高了定位精度。文獻(xiàn)［5］借助劃分多個(gè)通信半徑的方法來優(yōu)化平均跳距，并利用模擬退火算法來降低定位誤差。文獻(xiàn)［6］在DV?Hop算法改進(jìn)中引入了RSSI技術(shù)，通過對數(shù)?常態(tài)分布模型來定義錨節(jié)點(diǎn)的平均跳距誤差，使得錨節(jié)點(diǎn)和未知節(jié)點(diǎn)間估算距離更精確，這種改進(jìn)方法可以在不增加硬件損耗的基礎(chǔ)上有效提高定位精度，但在算法中依然存在改進(jìn)的余地。

本文改進(jìn)了傳統(tǒng)DV?Hop［4］算法的3個(gè)步驟：首先利用多通信半徑的方法修正最小跳數(shù)，對計(jì)算出的平均跳距進(jìn)行加權(quán)歸一化處理；然后用RSSI測得的距離與歐氏距離的差定義每個(gè)錨節(jié)點(diǎn)的平均跳距誤差，乘以跳數(shù)后，再加上加權(quán)后的估計(jì)距離，使得未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的估計(jì)距離誤差更?。蛔詈蟛捎眉訖?quán)最小二乘法估算未知節(jié)點(diǎn)坐標(biāo)。研究表明，改進(jìn)后的算法精度較高，有效減少了定位誤差，并且在節(jié)點(diǎn)數(shù)量較少時(shí)依然能發(fā)揮良好作用。

1 傳統(tǒng)DV?Hop算法

1.1 具體步驟

DV?Hop算法的起源是距離矢量路由協(xié)議［5］，它的定位過程分為3步。

第1步計(jì)算最小跳數(shù)［6］。在規(guī)定區(qū)域內(nèi)隨機(jī)不規(guī)則部署所有節(jié)點(diǎn)，信標(biāo)節(jié)點(diǎn)通過信息廣播的方式發(fā)送數(shù)據(jù)包給相鄰節(jié)點(diǎn)，相鄰節(jié)點(diǎn)比較多個(gè)跳數(shù)信息后記錄最小跳數(shù)。

第2步估算節(jié)點(diǎn)間距離。根據(jù)錨節(jié)點(diǎn)間最小跳數(shù)和坐標(biāo)，估算出平均跳距為

式中：(xi，yi)為錨節(jié)點(diǎn)i的坐標(biāo)；hiu為錨節(jié)點(diǎn)i和u間的最小跳數(shù)。

估算未知節(jié)點(diǎn)j到錨節(jié)點(diǎn)i的距離為

第3步最大似然估計(jì)法求節(jié)點(diǎn)坐標(biāo)。由式（2）可得

式中dn為未知節(jié)點(diǎn)(x，y)與錨節(jié)點(diǎn)間的歐式距離。

在進(jìn)行相減后，對線性方程組用矩陣表示為

式中

式中：矩陣A為實(shí)矩陣；矩陣X為未知節(jié)點(diǎn)坐標(biāo)矩陣；ATA可逆，因此由式（3）轉(zhuǎn)化的線性方程組總是有解的，可以解得矩陣X。

1.2 DV?Hop算法誤差分析

（1）最小跳數(shù)存在誤差。節(jié)點(diǎn)在網(wǎng)絡(luò)中的分布是隨機(jī)且不規(guī)則的。因此在某一個(gè)錨節(jié)點(diǎn)的一個(gè)通信半徑所圍成的圓形區(qū)域內(nèi)，節(jié)點(diǎn)間距離一般是隨機(jī)的，即距離不等。按照傳統(tǒng)DV?Hop算法來計(jì)算跳數(shù)時(shí)，節(jié)點(diǎn)間跳數(shù)相同，但是距離不等，導(dǎo)致誤差出現(xiàn)。因此為了降低誤差，應(yīng)該采用劃分多個(gè)通信半徑的方法，而不能直接地將跳數(shù)值記為1跳。

（2）平均跳距［7?8］存在誤差。因?yàn)楣?jié)點(diǎn)是隨機(jī)分布的，所以形成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不規(guī)則，2個(gè)節(jié)點(diǎn)需要經(jīng)過多跳且非直線路徑才能夠?qū)崿F(xiàn)通信。這種情況下，根據(jù)傳統(tǒng)DV?Hop算法估計(jì)出的平均跳距小于真實(shí)跳距，造成定位精度降低。為了盡量修正誤差，本文使用了加權(quán)平均跳距和RSSI測距修正估計(jì)距離的方法來減小誤差。加權(quán)方法不會(huì)增加時(shí)間復(fù)雜度，而RSSI測距有著硬件成本低的特點(diǎn)，比較適合使用。

（3）坐標(biāo)估算存在誤差。DV?Hop算法中選擇使用的計(jì)算方法，如三邊測量法和最大似然估計(jì)法［9?10］等傳統(tǒng)算法會(huì)加大定位誤差。而文獻(xiàn)中的一些智能優(yōu)化算法，如粒子群算法、模擬退火算法等，雖然能取得更好的定位精度，但提高了算法復(fù)雜度和節(jié)點(diǎn)能耗，故本文采用加權(quán)最小二乘法，在不增加復(fù)雜度的前提下優(yōu)化定位精度。

2 改進(jìn)算法

2.1 多通信半徑優(yōu)化最小跳數(shù)

為了節(jié)約計(jì)算成本，本文劃分了4個(gè)通信半徑［11］，即將通信半徑R劃為4等分。網(wǎng)絡(luò)中的錨節(jié)點(diǎn)通過泛洪的方式分為4次廣播錨節(jié)點(diǎn)自身的坐標(biāo)，這4次廣播分別以通信半徑為0.25 R、0.5 R、0.75 R和R進(jìn)行。

第1次廣播，錨節(jié)點(diǎn)以0.25 R為通信半徑向相鄰節(jié)點(diǎn)發(fā)送分組信息，此時(shí)相鄰節(jié)點(diǎn)記錄最小跳數(shù)為0.25，并且停止信息轉(zhuǎn)發(fā)，以減小通信開銷。第2、3和4次廣播，通信半徑和最小跳數(shù)都以0.25單位為間隔遞增，多次重復(fù)操作，最終網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)就能獲得最小跳數(shù)。設(shè)相鄰節(jié)點(diǎn)的實(shí)際距離為d，節(jié)點(diǎn)間的跳數(shù)hij為

2.2 加權(quán)平均跳距

計(jì)算估計(jì)距離為

式中：Wi為錨節(jié)點(diǎn)i的權(quán)值；HopsizeAvgj為未知節(jié)點(diǎn)j的加權(quán)平均跳距；d1ij為未知節(jié)點(diǎn)j到錨節(jié)點(diǎn)i的估計(jì)距離。

2.3 RSSI測距修正估計(jì)距離

本文采用對數(shù)?常態(tài)分布模型［12?13］來計(jì)算傳播路徑損耗，有

式中：Pik為錨節(jié)點(diǎn)i和k之間的接收信號(hào)強(qiáng)度，單位為d B·m；d0為信號(hào)參考傳輸距離；P(d0)為接收信號(hào)強(qiáng)度，取d0=1 m；np為衰減指數(shù)，一般取2；dik為錨節(jié)點(diǎn)i和k的歐氏距離；Xσ為均值是0、方差是σ（本文取10）的高斯隨機(jī)分布，誤差可忽略。

在實(shí)際應(yīng)用中，可以通過多次獲取同一錨節(jié)點(diǎn)的信號(hào)，降低RSSI帶來的誤差。接收信號(hào)強(qiáng)度Pik與距離成反比。圖1為信號(hào)強(qiáng)度隨距離變化關(guān)系。

圖1 信號(hào)強(qiáng)度隨距離變化關(guān)系Fig.1 Relationship between signal strength and distance

由式（10）可推導(dǎo)出距離公式

求得錨節(jié)點(diǎn)i的平均跳距誤差ci和錨節(jié)點(diǎn)i和未知節(jié)點(diǎn)j的修正距離d2ij為

結(jié)合式（9，13），可得

式中：d2ij、dij為錨節(jié)點(diǎn)i和未知節(jié)點(diǎn)j的修正距離和估算距離。

2.4 加權(quán)最小二乘法

傳統(tǒng)最大似然估計(jì)法的矩陣B中的各項(xiàng)元素會(huì)產(chǎn)生定位誤差，這是由于各項(xiàng)元素的方差會(huì)隨著坐標(biāo)的變化而改變，即擾動(dòng)項(xiàng)的方差不全相等，為了消除異方差性，有效減小定位誤差，就需要采用加權(quán)二乘法代替最大似然估計(jì)法。

無線傳感器網(wǎng)絡(luò)通常資源有限，在提升定位精度的同時(shí)也要兼顧考慮算法的時(shí)間復(fù)雜度等其他因素。文獻(xiàn)［12］中的基于模擬退火的粒子群優(yōu)化算法（Simulated annealing particle swarm optimization al?gorithm，SAPSO）定位算法就是融合了改進(jìn)粒子群算法和模擬退火算法，通過犧牲算法復(fù)雜度來換取定位精度，雖然這種方法對定位精度有較大的提升，但對無線傳感器網(wǎng)絡(luò)有巨大負(fù)擔(dān)。根據(jù)文獻(xiàn)［14］的研究，相比于其他改進(jìn)算法，加權(quán)最小二乘法的時(shí)間復(fù)雜度與最大似然估計(jì)法近似相等并且能有效減小定位誤差，因此從時(shí)間復(fù)雜度和定位精度方面綜合考慮，就需要采用加權(quán)二乘法。

加權(quán)最小二乘法的原理是消除擾動(dòng)項(xiàng)方差的不相等，即對偏離程度較大的數(shù)據(jù)乘以較小的權(quán)值，而對偏離程度較小的數(shù)據(jù)乘以較大的權(quán)值，最終使各項(xiàng)數(shù)據(jù)方差可以近似相等。因此，采用文獻(xiàn)［9］中的改進(jìn)雙曲線定位算法模型可以實(shí)現(xiàn)更好的定位精度。

本文直接將式（3）展開，并且令D2=x2+y2，代入誤差項(xiàng)δi，得

將D、x和y看作未知數(shù)，將式（15）的線性方程組的形式轉(zhuǎn)變?yōu)榫仃囆问?/p>

3 仿真結(jié)果分析

3.1 算法的定位精度分析

本文基于MATLAB軟件進(jìn)行仿真實(shí)驗(yàn)，仿真環(huán)境為100 m×100 m的二維區(qū)域。為了減小隨機(jī)性帶來的定位誤差，仿真實(shí)驗(yàn)進(jìn)行200次，并取平均值。

采用歸一化定位誤差在不同總節(jié)點(diǎn)個(gè)數(shù)、通信半徑和錨節(jié)點(diǎn)密度的情況下比較算法定位性能，對比結(jié)果如圖2~4所示。平均定位誤差（Average positioning error，APE）計(jì)算公式［13］為

式中：M為未知節(jié)點(diǎn)個(gè)數(shù)；R代表通信半徑；(xi，yi)為節(jié)點(diǎn)的真實(shí)坐標(biāo)；(x'i，y'i)為節(jié)點(diǎn)的估計(jì)坐標(biāo)。

圖2~4中：Improved algorithm代表本文改進(jìn)算法；DV?hop代表傳統(tǒng)DV?Hop算法；DV?hop2代表文獻(xiàn)［14］中通過加權(quán)最小二乘法優(yōu)化的算法；DV?hop3代表文獻(xiàn)［15］中提出的IDV?Hop+WH算法，它的改進(jìn)基于平均修正系數(shù)和加權(quán)雙曲線定位算法。

圖2（a）給出了在錨節(jié)點(diǎn)占比為20%，通信半徑為25 m，總節(jié)點(diǎn)個(gè)數(shù)以20為間隔從60增加至200的環(huán)境下4種算法的平均定位誤差的變化；圖2（b）給出了在錨節(jié)點(diǎn)占比為15%，通信半徑為30 m，總節(jié)點(diǎn)個(gè)數(shù)以20為間隔從60增加至200的環(huán)境下4種算法的平均定位誤差的變化。由圖2可知，4種算法的平均定位誤差都與節(jié)點(diǎn)總數(shù)成反比，但I(xiàn)mproved algorithm的定位誤差一直穩(wěn)定最小。在總節(jié)點(diǎn)個(gè)數(shù)為60時(shí)，Improved algorithm算法的定位誤差相對于DV?hop降低了0.17~0.18，相對于DV?hop2降低了0.11~0.15，相對于DV?hop3降低了0.02~0.06。由此可見，本文改進(jìn)算法在節(jié)點(diǎn)數(shù)量比較少的區(qū)域中仍然可以保持較好的定位精度。圖3（a）給出了在總節(jié)點(diǎn)個(gè)數(shù)為100，通信半徑為25 m，錨節(jié)點(diǎn)密度以0.05為間隔從0.1增加至0.45的環(huán)境下4種算法的平均定位誤差的變化；圖3（b）給出了在總節(jié)點(diǎn)個(gè)數(shù)為80，通信半徑為30 m，錨節(jié)點(diǎn)密度以0.05為間隔從0.1增加至0.45的環(huán)境下4種算法的平均定位誤差的變化。由圖3可知，當(dāng)錨節(jié)點(diǎn)密度增加時(shí)，4種算法的平均定位誤差都在降低，但I(xiàn)mproved algorithm算法的工作效果始終是最佳的。Improved algorithm算法的定位誤差相對于DV?hop降低了0.17~0.19，相對于DV?hop2降低了0.1~0.12，相對于DV?hop3降低了0.02~0.09，Improved algorithm算法曲線相對于其他3種算法更平滑一些，可以看出本文改進(jìn)算法具有良好的穩(wěn)定性。

圖2 不同總節(jié)點(diǎn)個(gè)數(shù)情況下算法性能比較Fig.2 Performance comparison with different numbers of total nodes

圖3 不同錨節(jié)點(diǎn)密度情況下算法性能比較Fig.3 Performance comparison with different anchor node densities

圖4（a）給出了在總節(jié)點(diǎn)個(gè)數(shù)為100，錨節(jié)點(diǎn)密度為20%，通信半徑以5 m為間隔從15 m增加至50 m的環(huán)境下4種算法的平均定位誤差的變化；圖4（b）給出了在總節(jié)點(diǎn)個(gè)數(shù)為120，錨節(jié)點(diǎn)密度為10%，通信半徑以5 m為間隔從15 m增加至50 m的環(huán)境下4種算法的平均定位誤差的變化。由圖4可知，盡管4種算法的定位誤差隨著網(wǎng)絡(luò)連通性的提高而降低，但是Improved algorithm算法的誤差始終低于其他兩個(gè)改進(jìn)算法，并且在趨于穩(wěn)定時(shí)，改進(jìn)算法的誤差比傳統(tǒng)算法減少約50%。由此可見，在通信半徑大于35 m后，誤差曲線近似水平，本文改進(jìn)算法定位性能更好。

圖4 不同通信半徑情況下算法性能比較Fig.4 Performance comparison with different transmission radius

3.2 RSSI測距技術(shù)的影響分析

根據(jù)RSSI對數(shù)?常態(tài)分布模型，在同一通信半徑下，每個(gè)錨節(jié)點(diǎn)的平均跳距誤差近似一致，因此采用對平均跳距誤差ci求均值的方法來確定在不同通信半徑下的RSSI測距技術(shù)性能，平均跳距誤差均值（Average hop?distance error，AHde）計(jì)算公式為

式中：N代表總節(jié)點(diǎn)個(gè)數(shù)；M代表仿真區(qū)域中未知節(jié)點(diǎn)個(gè)數(shù)；ci為錨節(jié)點(diǎn)i的平均跳距誤差。

圖5（a）給出了在總節(jié)點(diǎn)個(gè)數(shù)為100，錨節(jié)點(diǎn)密度為20%，通信半徑以5 m為間隔從15 m增加至55 m的環(huán)境下，本文改進(jìn)算法Improved algorithm在不同通信半徑下的平均跳距誤差均值A(chǔ)Hde變化。由圖5（a）可得，在通信半徑增大的過程中，平均跳距誤差和通信半徑近似成正比例關(guān)系，即通信半徑越大，跳距誤差也越大。

圖5（b）給出了在總節(jié)點(diǎn)個(gè)數(shù)為100，錨節(jié)點(diǎn)密度為20%，通信半徑以5 m為間隔從15 m增加至55 m的環(huán)境下，Nonerssi算法和Improved algorithm算法的平均定位誤差的變化，其中前者是不采用RSSI測距的本文改進(jìn)算法。由圖5（b）可知，當(dāng)通信半徑為15~35 m之間時(shí)，兩種算法的定位誤差近似一致；當(dāng)通信半徑調(diào)整到大于35 m之后，Improved algorithm算法的定位誤差下降趨勢逐漸平緩但依然在降低，并且始終低于Nonerssi算法。也就是說，通信半徑在超過35 m之后，RSSI測距技術(shù)修正平均跳距的效果更為突出。

圖5 跳距誤差和定位誤差隨通信半徑變化關(guān)系Fig.5 Relationship between hop error and positioning error with communication radius

3.3 時(shí)間復(fù)雜度分析

設(shè)隨機(jī)分布的總節(jié)點(diǎn)個(gè)數(shù)為n，則傳統(tǒng)DV?Hop算法中，利用最小二乘法計(jì)算未知節(jié)點(diǎn)坐標(biāo)的時(shí)間復(fù)雜度為O(n4)。本文改進(jìn)算法的時(shí)間復(fù)雜度在傳統(tǒng)算法的基礎(chǔ)上增加了O(n)，這是因?yàn)樵诜抡嬷行枰脤?shù)?常態(tài)分布模型來模擬接收信號(hào)強(qiáng)度RSSI，因此利用RSSI測距技術(shù)造成了較大的時(shí)間復(fù)雜度。但是在實(shí)際中幾乎所有的節(jié)點(diǎn)都具有接收信號(hào)強(qiáng)度RSSI的功能，可直接獲得RSSI值，因此時(shí)間復(fù)雜度增加不大，但定位精度得到了較好的改善。

4 結(jié)束語

為了改進(jìn)傳統(tǒng)DV?Hop算法的3個(gè)步驟存在的誤差問題，首先利用多通信半徑細(xì)化節(jié)點(diǎn)間的跳數(shù)，再采用RSSI測距和加權(quán)歸一化優(yōu)化跳距，最后采用加權(quán)最小二乘法修正誤差項(xiàng)的異方差性。通過仿真結(jié)果表明，本文改進(jìn)算法Improved algorithm相比于傳統(tǒng)DV?Hop算法、DV?hop2、DV?hop3的定位精度提升了約53%、31%和12%，改進(jìn)算法的定位精度有明顯提高；在總節(jié)點(diǎn)數(shù)較少時(shí)依然能有效定位，有著良好的穩(wěn)定性；沒有消耗時(shí)間復(fù)雜度來提升定位精度，時(shí)間復(fù)雜度與傳統(tǒng)算法相差不大。然而，本文算法依然存在可以改進(jìn)的內(nèi)容，比如考慮在三維空間內(nèi)通信過程受障礙物的影響等問題，所以下一步將拓展到三維空間中進(jìn)行研究。