胡 淼，陶正蘇

（上海交通大學(xué) 電子信息與電氣工程學(xué)院，上海 200240）

無線傳感器網(wǎng)絡(luò)是將大量傳感器隨機(jī)布設(shè)到某一目標(biāo)區(qū)域，以無線的方式進(jìn)行通信，并將采集到的數(shù)據(jù)在全網(wǎng)中進(jìn)行傳輸，以實現(xiàn)對目標(biāo)區(qū)域的監(jiān)測。傳感器的位置信息對監(jiān)測活動至關(guān)重要，沒有位置信息的的監(jiān)測消息往往是沒有意義的，而且無線傳感器網(wǎng)絡(luò)中的許多路由協(xié)議和運(yùn)用都是在位置信息已知的前提下設(shè)計的，因此傳感器的定位是傳感器網(wǎng)路的關(guān)鍵技術(shù)之一。

無線傳感器網(wǎng)絡(luò)定位技術(shù)有許多種，大致可以分為基于距離定位和距離無關(guān)定位兩類?；诰嚯x的定位主要是通過測量傳感器節(jié)點之間的距離或角度實現(xiàn)對未知節(jié)點的定位，TOA、TDOA、RSSI和AOA等是常見的基于距離的定位算法，這類定位算法對收發(fā)節(jié)點間的時間性有嚴(yán)格要求，對硬件條件要求較高，但定位精度相對較高；距離無關(guān)定位利用網(wǎng)絡(luò)內(nèi)部連通性來實現(xiàn)對未知節(jié)點定位，質(zhì)心算法、DV-Hop、Amorphous和APIT等是常見的距離無關(guān)算法。其中，DV-Hop算法具有易實現(xiàn)，對硬件要求低等特點。但是，錨節(jié)點分布不均的情況下，DV-Hop具有較大的定位誤差，針對DV-Hop的這一缺陷，提出了一種基于可移動錨節(jié)點的DV-Hop定位算法，并通過仿真實驗對兩種算法性能進(jìn)行比較。

1 DV-Hop算法及其改進(jìn)

1.1 DV-Hop算法

Niculescu等人首次在文獻(xiàn)中提出了DV-Hop定位算法，類似傳統(tǒng)網(wǎng)絡(luò)中的距離向量路由機(jī)制，DV-Hop定位過程可以分為3個步驟：

第1步，計算未知節(jié)點與每錨節(jié)點的最小跳數(shù)。

錨節(jié)點向鄰居節(jié)點廣播自身位置信息分組，其中包括跳數(shù)字段，初始化為0。接收節(jié)點只記錄到每個錨節(jié)點最小跳數(shù)，并將跳數(shù)字段加1轉(zhuǎn)發(fā)給鄰居節(jié)點。由此，所有節(jié)點記錄下到每個錨節(jié)點的最小跳數(shù)。

第2步，計算錨節(jié)點與信標(biāo)節(jié)點的實際跳段距離。

每個錨節(jié)點根據(jù)第一步中其他錨節(jié)點的位置信息和相距跳數(shù)，利用公式（1）估算平均每條距離：

其中（xi，yi），（xj，yj）是錨節(jié)點 i， j的坐標(biāo)，hj是錨節(jié)點 i與 j的之間的跳數(shù)。錨節(jié)點再將計算的每跳平均距離用帶有生存字段的分組廣播到全網(wǎng)中，未知節(jié)點只記錄收到的第一個每條平均距離，并轉(zhuǎn)發(fā)給鄰居節(jié)點。未知節(jié)點根據(jù)記錄的每跳平均距離以及第一步當(dāng)中的跳數(shù)計算到每個錨節(jié)點之間的跳段距離。

第3步，未知節(jié)點根據(jù)到各個錨節(jié)點的跳段距離值，利用三邊測量法或極大似然估計法計算未知節(jié)點的坐標(biāo)。

當(dāng)所有錨節(jié)點到未知節(jié)點P的距離d已知時，可按式（2）進(jìn)行計算:

可由式（2）可得線性方程組：

對式（3）使用標(biāo)準(zhǔn)的最小均方誤差估計方法可以得到節(jié)點的坐標(biāo)為：

1.2 基于移動錨節(jié)點DV-Hop算法

DV-Hop是一種典型的與距離無關(guān)定位算法，其誤差主要產(chǎn)生于利用錨節(jié)點計算出來的平均每跳距離來代替全局平均每跳距離，為減小誤差就要求錨節(jié)點能夠盡量均勻的分布在被測區(qū)域中，使錨節(jié)點平均每跳距離更接近全局平均每跳距離。針對這一特點，文獻(xiàn)[4]提出了一種基于可規(guī)律移動錨節(jié)點定位算法RRDV-Hop，RRDV-Hop利用一個規(guī)律移動的錨節(jié)點近似的構(gòu)建出N個均勻分布于網(wǎng)絡(luò)的錨節(jié)點，提高了定位精度。文中參考文獻(xiàn)[4]的思路，在假設(shè)所有的錨節(jié)點都有一定移動能力的基礎(chǔ)上，提出了基于移動錨節(jié)點DV-Hop定位算法 MAN-DV Hop（Mobile Anchor Node-DV Hop）。

MAN-DV Hop設(shè)定所有的錨節(jié)點都具有一定的移動能力，在所有節(jié)點隨機(jī)部署在監(jiān)測區(qū)域后，錨節(jié)點會與通信范圍內(nèi)的其他錨節(jié)點產(chǎn)生一種虛擬力（virtual force），而錨節(jié)點會根據(jù)虛擬力的大小及方向計算出自身位置的修正值，并移動到相應(yīng)位置，實現(xiàn)錨節(jié)點的重新部署，使所有的錨節(jié)點能夠均勻的分布于整個網(wǎng)絡(luò)當(dāng)中。然后MAN-DV Hop根據(jù)錨節(jié)點的新位置計算平均每跳距離，再完成未知節(jié)點的定位。

1.3 錨節(jié)點間虛擬力模型

為了使錨節(jié)點更均勻的分布于整個監(jiān)測區(qū)域，可假設(shè)相隔較近的錨節(jié)點間會產(chǎn)生一種虛擬力，使錨節(jié)點移動到合適位置，直到虛擬力弱化為0。在傳感器網(wǎng)絡(luò)中，節(jié)點見常構(gòu)建的虛擬力模型主要有4種。第1種虛擬力定義：

式（4）中dij表示錨節(jié)點i和j之間的距離，rc為節(jié)點通信半徑，當(dāng)兩個錨節(jié)點間的距離超過0.5rc時，錨節(jié)點間不在產(chǎn)生虛擬力。

參考電荷之間庫倫力模型，可以得到第2種虛擬力定義：

式（5）中 Qi，Qj原本表示兩個電荷所帶的電量 i，j而在傳感器網(wǎng)絡(luò)中可用，節(jié)點的網(wǎng)絡(luò)連通度來代替。

第3種虛擬力定義為：

式（6）中有兩個距離閾值rth與Rth，dij表示兩節(jié)點之間的距離，rth與Rth的變化將影響錨節(jié)點對監(jiān)測區(qū)域的覆蓋率。

第4種常見的虛擬力定義為：

式（7）中wA表示虛擬力的引力系數(shù)，wR表示虛擬力的斥力系數(shù)，利用wA，wR可調(diào)節(jié)錨節(jié)點重部署后的疏密度。文獻(xiàn)[5]分析了4種模型中各個參數(shù)對網(wǎng)絡(luò)覆蓋率的影響，MAN-DV Hop可根據(jù)不同節(jié)點分布情況選定不同的虛擬力模型。

當(dāng)錨節(jié)點受到通信范圍內(nèi)其他錨節(jié)點產(chǎn)生虛擬力后，由原位置（x0，y0）更新到新位置（xnew，ynew），轉(zhuǎn)化模型為：

式（8）中，Maxstep是傳感器節(jié)點的最大移動距離，F(xiàn)xy是作用于傳感器節(jié)點的虛擬力，F(xiàn)x，F(xiàn)y分別是虛擬力在X軸和Y軸方向上的分量，F(xiàn)th是設(shè)定的虛擬力閾值，當(dāng)兩個錨節(jié)點間的虛擬力絕對值小于閾值時，錨節(jié)點不發(fā)生移動。

1.4 虛擬力模型的選定

文獻(xiàn)[5]分析了4種虛擬力的參數(shù)對模型性能的影響，其中用來評定模型性能的指標(biāo)包括：覆蓋增加率，覆蓋效率，平均移動距離。模型一結(jié)構(gòu)簡單，且錨節(jié)點間的虛擬力只是斥力。當(dāng)節(jié)點的通信半徑較小時，MAN DV-hop選取模型一作為錨節(jié)點間的作用力，改善錨節(jié)點分布過于密集時的情況。當(dāng)錨節(jié)點通信半徑較大時，模型一中虛擬力大小與通信半徑成正比rc，錨節(jié)點間斥力過大，使計算的平均每跳距離偏離真實值。當(dāng)傳感器節(jié)點通信半徑較大時，網(wǎng)絡(luò)的平均每跳值Hopsize

式（9）中a，b為小于1的范圍系數(shù)。由此，綜合模型1、模型3、模型4MAN DV-hop構(gòu)建虛擬力模型：

式（10）表明，當(dāng)量錨節(jié)點間的距離時 dij∈（rth，Rth），MANDV Hop認(rèn)為此時錨節(jié)點間的距離分布是合理的，此時錨節(jié)點間不產(chǎn)生虛擬力作用 。當(dāng)錨節(jié)點間的距離dij∈（0，rth）∪（Rth，rc）時，MAN DV-Hop認(rèn)為節(jié)點間的距離過短或者過長，節(jié)點間產(chǎn)生虛擬力作用，且dij∈（0，rth）虛擬力為斥力，dij∈（Rth，rc）時，虛擬力為引力。 式（10）中 k1表示斥力系數(shù)系數(shù)，k2表示引力系數(shù)，用來控制虛擬力作用的強(qiáng)弱。

1.5 邊界條件

由于MAN-DV Hop設(shè)定錨節(jié)點具有一定的移動能力，并在虛擬力的作用下移動到新的位置。對于初始隨機(jī)分布在監(jiān)測區(qū)域邊界的錨節(jié)點，經(jīng)過移動后錨節(jié)點可能越過監(jiān)測區(qū)域的邊界或大部分通信范圍不在監(jiān)測區(qū)域內(nèi)。式（8）中設(shè)定了錨節(jié)點的最大移動距離Maxstep，若錨節(jié)點初始位置是（xo，yo），MAN-DV Hop 需判斷（xo±Maxstep，yo±Maxstep）是否處于監(jiān)測區(qū)域內(nèi)。MAN-DV Hop算法流程圖如圖1所示。

圖1 MAN DV-Hop定位算法流程圖Fig.1 Flow chart of MAN DV-Hop algorithm

2 仿真驗證

2.1 參數(shù)設(shè)置與誤差指標(biāo)

為了驗證MAN-DV Hop算法的性能，采用Matlab進(jìn)行仿真實驗。在仿真實驗中，假設(shè)所有節(jié)點都隨機(jī)分布在一個20 m×200 m的二維平面上，在該區(qū)域內(nèi)隨機(jī)放置200個節(jié)點，未知節(jié)點的通信半徑為rc，錨節(jié)點攜帶GPS定位設(shè)備，因此錨節(jié)點的坐標(biāo)位置是已知的，并且錨節(jié)點具有一定的移動能力。仿真通過計算未知節(jié)點的定位坐標(biāo)與實際坐標(biāo)之間的平均誤差與節(jié)點通信半徑的比值來評定定位精度的高低，節(jié)點平均定位誤差率：

式（11）中，erri表示節(jié)點i的定位誤差，un表示未知節(jié)點數(shù)量，rc表示節(jié)點的通信半徑，Error值越大，表示定位誤差越大，Error值越小，表示定位的精度越高。

2.2 算法仿真與分析

設(shè)定節(jié)點通信半徑rc=30 m，Maxstep=10 m，錨節(jié)點數(shù)量為30，此時MAN-DV Hop選定虛擬力模型一 ，仿真實驗中網(wǎng)絡(luò)節(jié)點初始分布圖如圖2所示。

圖2 節(jié)點分布圖Fig.2 Node distribution chart

錨節(jié)點重部署后的分布圖如圖3所示。

圖3 錨節(jié)點重構(gòu)分布圖Fig.3 Anchor node re-distribution chart

圖中o表示未知節(jié)點，*表示錨節(jié)點。比較圖2，圖3可得錨節(jié)分布變化情況。通過計算，初始分布時的網(wǎng)絡(luò)平均聯(lián)通度為12.29，網(wǎng)絡(luò)的鄰居錨節(jié)點平均數(shù)目為1.775。當(dāng)錨節(jié)重部署后，網(wǎng)絡(luò)的平均連通度為12.5，網(wǎng)絡(luò)的鄰居錨節(jié)點平均數(shù)目為1.92。當(dāng)錨節(jié)點通信半徑rc=50 m時，虛擬力模型設(shè)定為二，k1-k2=10，Rth=0.8rc，rth=0.2rc初始分布時的網(wǎng)絡(luò)平均聯(lián)通度為29.93，網(wǎng)絡(luò)的鄰居錨節(jié)點平均數(shù)目為4.2。當(dāng)錨節(jié)重部署后，網(wǎng)絡(luò)的平均連通度為30.53，網(wǎng)絡(luò)的鄰居錨節(jié)點平均數(shù)目為4.585。結(jié)果表明傳感器節(jié)點在經(jīng)過網(wǎng)絡(luò)初始隨機(jī)部署后，錨節(jié)點發(fā)生移動重部署后，錨節(jié)點的分布情況趨于均勻。

設(shè)定節(jié)點通信半徑rc由30 m變化到60 m，步長為5 m。Rth=0.8rc，rth=5 m，Maxstep=10 m，k1-k2=5 節(jié)點平均定位誤差變化情況：

圖4 平均定位誤差對比圖Fig.4 Average location error chart

設(shè)定通信半徑rc=30 m，錨節(jié)點比例由10%變化到60%，步長為5%時，平均定位誤差的變化情況：

圖5 平均定位誤差對比圖Fig.5 Average location error chart

由圖4，圖5可知，在相同的網(wǎng)絡(luò)條件下，MAN-DV Hop具有更高的定位精度。

3 結(jié) 論

文章在DV-Hop定位算法的基礎(chǔ)上，設(shè)定錨節(jié)點具有一定的移動能力，通過構(gòu)建錨節(jié)點間的虛擬力來使其移動，使錨節(jié)點更均勻的分布于整個網(wǎng)絡(luò)，從而提高了DV-hop定位算法 的定位精度。仿真結(jié)果表明，相同條件下，隨機(jī)分布的網(wǎng)絡(luò)中，與DV-hop算法相比，MAN DV-hop算法降低了平均定位誤差，并且定位精度更穩(wěn)定。

[1]孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.

[2]Niculescu D，Nath B.DV based positioning in Ad hoc networks[J].Telecommunication Systems，2003（22）：267-280.

[3]Bulusu N，Heidemann J，Estrin D.GPS-less low cost outdoor location for very small devices[J]. IEEE Personal Communications，2000，7（5）：28-34.

[4]李瑞雪，房至一，儀婷婷.基于可規(guī)律性移動錨節(jié)點和接收信號強(qiáng)度指示器的改進(jìn)DV-Hop定位算法及其性能分析[J].吉林大學(xué)學(xué)報，2011，41（2）：435-441.LI Rui-xue，F(xiàn)ANG Zhi-yi，YI Ting-ting.Improved DV-Hop localization algorithm based on regularly moving anchor（RMAN）and received signal strength indicator （RSSI）and its performance analysis[J].Journal of Jilin University，2011，41（2）：435-441.

[5]任孝平，蔡自興，任清雄.四種虛擬力模型在傳感器網(wǎng)絡(luò)覆蓋中的性能分析[J].信息與控制，2010，39（4）：441-445.REN Xiao-ping，CAI Zi-xing，REN Qing-xiong.Performance analysis four virtual force models used for coverage algorithm of wireless sensor networks[J].Information and Control，2010，39（4）：411-445.

[6]王雪，王晟，馬俊杰.無線傳感網(wǎng)絡(luò)的虛擬力導(dǎo)向微粒群優(yōu)化策略[J].電子學(xué)報，2007，35（11）：2038-2044.WANG Xue，WANG Sheng，MA Jun-jie.Dynamic sensor deployment strategy based on virtual forcev directed particle swarm optimization in wireless sensor networks[J].Acta Electronica Sinica，2007，35（11）：2038-2044.