基于CC2510 的DV-Hop 定位算法的改進(jìn)*

裴菊靜，王經(jīng)卓，許紅艷

(1.中國礦業(yè)大學(xué) 信息與電氣工程學(xué)院，江蘇 徐州221116;2.淮海工學(xué)院 電子工程學(xué)院，江蘇 連云港222005)

0 引 言

無線傳感器網(wǎng)絡(luò)是是由大量未知節(jié)點(diǎn)隨機(jī)部署形成的自組織網(wǎng)絡(luò)。由于這些未知節(jié)點(diǎn)的位置是未知的，如果要采集、處理未知節(jié)點(diǎn)的信息，必須要知道它們的位置，因此，定位技術(shù)是無線傳感器網(wǎng)絡(luò)現(xiàn)在研究的重點(diǎn)。

在定位算法中根據(jù)定位過程是否需要測量節(jié)點(diǎn)之間的實(shí)際距離，把定位算法分為無需測距(range－free)的定位算法和基于測距［1］(range－based)的定位算法。前者不需要測量節(jié)點(diǎn)間的實(shí)際距離，而是利用節(jié)點(diǎn)間的估計(jì)距離計(jì)算節(jié)點(diǎn)間的實(shí)際距離，后者需要測量相鄰節(jié)點(diǎn)間的實(shí)際距離來計(jì)算未知節(jié)點(diǎn)的位置。基于測距的定位算法雖然定位精度較高，但它并不適用于低功耗、低成本的應(yīng)用領(lǐng)域。距離無關(guān)的定位算法精度較低，但能滿足大部分無線傳感器網(wǎng)絡(luò)的要求，因此，在實(shí)際應(yīng)用中普遍使用。常用的無需測距的定位算法有質(zhì)心定位算法、DV－Hop 算法、MDS－MAP 算法、Bounding－Box 定位算法、近似三角形內(nèi)點(diǎn)測試法(APIT)等。

1 DV-Hop 和改進(jìn)的算法

1.1 DV－Hop 算法

DV－Hop［2］算法是由 Niculescu 和 Nath 提出來的，它的基本思想是通過運(yùn)用節(jié)點(diǎn)間的跳數(shù)和每跳的距離來估計(jì)節(jié)點(diǎn)間的實(shí)際距離。具體算法分為3 個(gè)步驟:1)使用經(jīng)典的距離矢量交換協(xié)議，信標(biāo)節(jié)點(diǎn)發(fā)送自己的位置信息和跳數(shù)，是所有節(jié)點(diǎn)獲得信標(biāo)節(jié)點(diǎn)的最小跳數(shù);2)信標(biāo)節(jié)點(diǎn)根據(jù)自身記錄的其他信標(biāo)節(jié)點(diǎn)的位置和跳數(shù)根據(jù)公式計(jì)算平均每跳距離，則未知節(jié)點(diǎn)可以計(jì)算到相對應(yīng)的信標(biāo)節(jié)點(diǎn)之間的距離;3)當(dāng)未知節(jié)點(diǎn)收到不小于3 個(gè)到信標(biāo)節(jié)點(diǎn)的距離時(shí)，可以根據(jù)三邊定位或最小二乘法計(jì)算自身坐標(biāo)

式中 ci為平均每跳距離;(xi，yi)，(xj，yj)為錨節(jié)點(diǎn) i 和 j的坐標(biāo)，hi為跳數(shù)。

1.2 改進(jìn)的算法

Chipcon 公司的CC2510 芯片是一種內(nèi)嵌8051 單片機(jī)的低功耗的芯片，內(nèi)部具有無線定位引擎，它的定位功能是基于接收信號強(qiáng)度指示(RSSI)測距［3］。在RSSI 定位過程中，未知節(jié)點(diǎn)根據(jù)接收到的信號強(qiáng)度值計(jì)算信號的傳播損耗，根據(jù)對應(yīng)的傳播模型可以將傳播損耗轉(zhuǎn)換成距離。未知節(jié)點(diǎn)可以把自己獲得的坐標(biāo)和RSSI 值傳送到CC2510 組成的定位模塊，然后由內(nèi)部的定位引擎計(jì)算得到自身坐標(biāo)。在改進(jìn)的算法中，用CC2510 設(shè)計(jì)硬件節(jié)點(diǎn)［4］。

在DV－Hop 算法的第一階段中要用到洪泛法，使節(jié)點(diǎn)能量開銷很大，在估算未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)之間跳數(shù)時(shí)，當(dāng)跳數(shù)為1 跳時(shí)，可以直接通過RSSI 測距法來計(jì)算1 跳距離，這樣會降低整個(gè)網(wǎng)絡(luò)的功耗和減小定位誤差。在第二階段中，信標(biāo)節(jié)點(diǎn)廣播自己的位置信息，未知節(jié)點(diǎn)收到不小于3個(gè)信標(biāo)節(jié)點(diǎn)的位置信息時(shí)，通過RSSI 測距法［5］的信號強(qiáng)度值選取離自己最近的3 個(gè)信標(biāo)節(jié)點(diǎn)存入自己的數(shù)據(jù)包，當(dāng)信標(biāo)節(jié)點(diǎn)繼續(xù)發(fā)送信息，未知節(jié)點(diǎn)從接收到的信息中比較，當(dāng)RSSI 值大于自己存儲的數(shù)據(jù)時(shí)，則存入數(shù)據(jù)包;否則，丟棄。然后選取3 個(gè)最大RSSI 值的信標(biāo)節(jié)點(diǎn)計(jì)算平均每跳距離。在第三階段當(dāng)用三邊測量計(jì)算自身坐標(biāo)時(shí)，未知節(jié)點(diǎn)就用第二階段獲得的3 個(gè)信標(biāo)節(jié)點(diǎn)計(jì)算。

改進(jìn)的算法降低了第一階段洪泛法的能量損耗，當(dāng)距離為1 跳距離時(shí)直接用測得的RSSI 求出距離。還可以減小第二階段求平均每條距離帶來的誤差，因?yàn)槲粗?jié)點(diǎn)計(jì)算距離時(shí)不再統(tǒng)一用固定的平均每跳距離，而是根據(jù)自身儲存的信息選取合適的信標(biāo)節(jié)點(diǎn)來計(jì)算。改進(jìn)的算法流程［6］如圖 1。

圖1 改進(jìn)算法的流程圖Fig 1 Flow chart of improved algorithm

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

為了驗(yàn)證上述改進(jìn)算法的有效性，用CC2510 設(shè)計(jì)的節(jié)點(diǎn)硬件進(jìn)行了模擬實(shí)驗(yàn)，并且對定位算法進(jìn)行了Matlab 仿真［7］，在100 m×100 m 的正方形區(qū)域隨機(jī)部署100 個(gè)節(jié)點(diǎn)，其中，信標(biāo)節(jié)點(diǎn)為10 個(gè)，通信半徑為50 m。圖2 和圖3 分別為節(jié)點(diǎn)的隨機(jī)分布和未知節(jié)點(diǎn)的定位誤差，實(shí)驗(yàn)結(jié)果可以得到定位誤差降低到20%左右，證明了本算法可以適當(dāng)減小定位誤差。

圖2 節(jié)點(diǎn)的分布Fig 2 Distribution of nodes

圖3 節(jié)點(diǎn)的定位誤差Fig 3 Localization error of nodes

通過改變信標(biāo)節(jié)點(diǎn)的數(shù)目，再次驗(yàn)證算法的精確度，測量改進(jìn)算法的誤差和原來的算法相比較得到圖4。從圖中可以看出:隨著信標(biāo)節(jié)點(diǎn)的增加，定位誤差逐漸減小，并且改進(jìn)后的DV－Hop 算法對于信標(biāo)節(jié)點(diǎn)的變化具有較好的穩(wěn)定性［8］。

圖4 改進(jìn)算法前后的定位誤差圖Fig 4 Localization error diagram before and after the algorithm is improved

3 結(jié) 論

針對DV－Hop 算法的特點(diǎn)，本文提出了基于 CC2510 定位引擎的RSSI 測距技術(shù)的改進(jìn)的定位算法，在第一階段當(dāng)跳數(shù)為1 時(shí)，直接采用RSSI 測距，減少了第二階段的能量開銷，降低了誤差，在第二階段采用RSSI 測距技術(shù)選取合適的信標(biāo)節(jié)點(diǎn)求平均每跳距離，并且在三邊測量求未知節(jié)點(diǎn)的坐標(biāo)時(shí)，可以參照第二階段選取的信標(biāo)節(jié)點(diǎn)。仿真結(jié)果表明:改進(jìn)的定位算法比傳統(tǒng)的DV－Hop 顯示出了優(yōu)越的性能，且定位的精度得到提高。

［1］ 王汝傳，孫力娟.無線傳感器網(wǎng)絡(luò)技術(shù)及其應(yīng)用［M］.北京:人民郵電出社，2011.

［2］ 劉文遠(yuǎn)，王恩爽，陳子軍.無線傳感器網(wǎng)絡(luò)中DV－Hop 定位算法的改進(jìn)［J］.小型微型計(jì)算機(jī)系統(tǒng)，2011，6(6):1072 －1073.

［3］ Wu Lingfei，Meng Qinghu，Liang Huawei.A collinearity－based localization algorithm for wireless sensor networks［J］.Chinese Journal of Sensors and Actuators，2009，22(5):722 －727.

［4］ Yang Zheng，Liu Yunhao.Quality of trilateration:Confidencebased iterative localization［J］.IEEE Transactions on Parallel and Distributed Systems，2009，99(2):631 － 640.

［5］ Huw W，Qin H B，Huang H Y.A mobile beacon－based method for wireless sensor networks localization［C］//Proceedings of The 11th IEEE International Conference on Communication Technology，2008:1 －4.

［6］ 史洪宇，燕 莎.WSNs 中一種改進(jìn)的DV－Hop 節(jié)點(diǎn)定位算法電光與控制［J］.電光與控制，2011，18(4):93 －95.

［7］ Wu Xiaobing，Chen Guihai，Das S K.The energy hole problem of non－uniform sensor distribution［J］.Chinese Journal of Computers，2008，31(2):253 －261.

［8］ Chen H，Kaoru S，Deng P，et al.An improved DV－Hop localization algorithm with reduced node location error for wireless sensor networks［J］.Communications and Computer Sciences，2008，91(8):2232 －2236.