不均勻布置傳感器網(wǎng)絡(luò)定位優(yōu)化算法

溫龍飛，崔靈果，張百海，金雪

(北京理工大學(xué) 自動(dòng)化學(xué)院，北京100081)

0 引言

傳感器網(wǎng)絡(luò)節(jié)點(diǎn)是融傳感器、控制器和通信裝置于一體，集傳感與驅(qū)動(dòng)控制能力、計(jì)算能力、通信能力于一身的嵌入式系統(tǒng)。由這些微型傳感器構(gòu)成的無線傳感器網(wǎng)絡(luò)能夠協(xié)作地感知、采集和處理網(wǎng)絡(luò)區(qū)域里監(jiān)測(cè)對(duì)象的信息并最終發(fā)送到應(yīng)用終端。無線傳感器網(wǎng)絡(luò)的發(fā)展引起了全世界的廣泛關(guān)注，它同時(shí)是物聯(lián)網(wǎng)體系架構(gòu)中的重要組成部分[1]。

節(jié)點(diǎn)定位技術(shù)是傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一。不含位置信息的感知數(shù)據(jù)是沒有任何實(shí)際意義的。比如，當(dāng)有火災(zāi)警報(bào)出現(xiàn)時(shí)，相應(yīng)的傳感器節(jié)點(diǎn)必須能夠提供發(fā)生火情的現(xiàn)場(chǎng)位置，以便有關(guān)人員及時(shí)采取應(yīng)對(duì)方案，避免災(zāi)情擴(kuò)大。

目前，許多國內(nèi)外針對(duì)傳感器網(wǎng)絡(luò)的定位算法只有在網(wǎng)絡(luò)中節(jié)點(diǎn)的分布比較均勻時(shí)才能獲得較高的定位精度，在不均勻布置的傳感器網(wǎng)絡(luò)中定位精度較低。例如經(jīng)典的DV－h(huán)op 算法[2]和MDS－MAP算法[3]，由于節(jié)點(diǎn)布置不均勻，導(dǎo)致節(jié)點(diǎn)間的距離估計(jì)誤差較大，定位效果不理想。而實(shí)際上，由于監(jiān)測(cè)區(qū)域地形限制(湖泊或山脈等)或節(jié)點(diǎn)自身能量耗盡等問題都有可能造成網(wǎng)絡(luò)中節(jié)點(diǎn)的不均勻布置。因此，研究不均勻布置傳感器網(wǎng)絡(luò)的定位算法有著重要的實(shí)際意義。

1 多維定標(biāo)技術(shù)及定位

多維定標(biāo)(MDS)技術(shù)[4]是一種源自心理測(cè)量學(xué)和精神物理學(xué)的數(shù)據(jù)分析技術(shù)，該技術(shù)常用于信息可視化處理或探索性數(shù)據(jù)分析，現(xiàn)已被廣泛應(yīng)用于多個(gè)領(lǐng)域。

在傳感器網(wǎng)絡(luò)定位中，運(yùn)用MDS 技術(shù)實(shí)際上是通過節(jié)點(diǎn)間的距離矩陣推導(dǎo)出相對(duì)位置信息的一種方法。

假設(shè)Xm×n為n 個(gè)節(jié)點(diǎn)的空間坐標(biāo)矩陣，其中矩陣X 的每行表示一個(gè)節(jié)點(diǎn)的m 維坐標(biāo)，即X(i，:)為第i 個(gè)節(jié)點(diǎn)在m 維空間的坐標(biāo)。假設(shè)D(2)(X)為節(jié)點(diǎn)間歐氏距離的平方構(gòu)成的矩陣，則有

經(jīng)推導(dǎo)可知，對(duì)矩陣進(jìn)行雙重中心化處理可化簡(jiǎn)得到矩陣B，即在(1)式兩邊乘以矩陣J =I －n－111T以及因子－1/2，有

再對(duì)矩陣B 進(jìn)行特征值分解，

可得到坐標(biāo)矩陣

式中:Q 為矩陣B 的特征向量按列排列組成的矩陣;Λ 為對(duì)角矩陣。

此時(shí)得到的X 為各研究對(duì)象在n 維空間中的相對(duì)坐標(biāo)，因此還需利用降維技術(shù)來得到其在m 維空間的節(jié)點(diǎn)相對(duì)坐標(biāo)。最后將相對(duì)坐標(biāo)通過錨節(jié)點(diǎn)位置信息轉(zhuǎn)化為絕對(duì)坐標(biāo)即可完成定位。另外，由于MDS 技術(shù)的目的是使距離矩陣D 逼近所提供的相似性矩陣P，因此在實(shí)際應(yīng)用中用P(2)代替矩陣D(2)(X).

基于MDS 技術(shù)的定位算法可以在基于測(cè)距和不基于測(cè)距[5]兩種情況下運(yùn)行，對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行相對(duì)定位和絕對(duì)定位，且該算法可利用較少錨節(jié)點(diǎn)得到較高精度的定位結(jié)果。但是，由上述公式推導(dǎo)可知，MDS 在取得相對(duì)坐標(biāo)之前并沒有用到錨節(jié)點(diǎn)的任何信息，錨節(jié)點(diǎn)信息利用不充分。除此之外，該方法仍存在如下問題:在基于MDS 技術(shù)的定位算法中，通常使用節(jié)點(diǎn)間的最短路徑來代替節(jié)點(diǎn)間的歐氏距離。當(dāng)節(jié)點(diǎn)均勻分布在傳感區(qū)域中時(shí)，如圖1(a)所示，節(jié)點(diǎn)間的最短路徑與真實(shí)直線距離相差不大;但是，當(dāng)節(jié)點(diǎn)間距離較遠(yuǎn)，或者中間經(jīng)過網(wǎng)絡(luò)中的空洞時(shí)，如圖1(b)所示，利用最短路徑對(duì)節(jié)點(diǎn)間的直線距離進(jìn)行估計(jì)將產(chǎn)生很大誤差，導(dǎo)致定位結(jié)果十分不理想。因此基于MDS 技術(shù)的定位算法并不適用于不均勻布置的傳感器網(wǎng)絡(luò)，適應(yīng)性較差。

圖1 MDS 距離估計(jì)示意圖Fig.1 MDS distance estimation

針對(duì)上述問題，本文提出了一種距離優(yōu)化的MDS(MDS－DO)定位算法。

2 距離優(yōu)化數(shù)學(xué)模型

按照REP 方法[6]，利用網(wǎng)絡(luò)中節(jié)點(diǎn)間的幾何關(guān)系來計(jì)算相距較遠(yuǎn)的兩節(jié)點(diǎn)間的距離值，從而修正由于采用最短路徑所帶來的過大距離估計(jì)。網(wǎng)絡(luò)中的空洞可分為兩種情況，分析如下。

2.1 與空洞交于一點(diǎn)

這種情況下，路徑與網(wǎng)絡(luò)中的一個(gè)空洞H 相交且僅交于一點(diǎn)。如圖2 所示。

圖2 最短路徑與空洞交于一點(diǎn)Fig.2 The shortest path and the hole cross at a point

節(jié)點(diǎn)s 和節(jié)點(diǎn)t 與網(wǎng)絡(luò)中的空洞H 相交于節(jié)點(diǎn)o.節(jié)點(diǎn)o 是空洞H 邊界上的節(jié)點(diǎn)，對(duì)其進(jìn)行標(biāo)記。由于空洞H 的存在，節(jié)點(diǎn)s 和節(jié)點(diǎn)t 之間的最短路徑Pst分別被節(jié)點(diǎn)o 割成so 和ot 兩段。假設(shè)|so| =d1，|ot| =d2，那么在三角形△sot 中，根據(jù)余弦定理有

則待求兩點(diǎn)間的距離可以表示為

為了求取線段so 和ot 之間的夾角α，以最短路徑和空洞H 的交點(diǎn)o 為圓心，選取合適的r 為半徑做一個(gè)接近于圓形的虛擬空洞，并對(duì)該空洞進(jìn)行與o 相同的標(biāo)記。這個(gè)虛擬空洞的圓心，也就是交點(diǎn)o被稱為“焦點(diǎn)”。此時(shí)，節(jié)點(diǎn)s 和節(jié)點(diǎn)t 之間的最短路徑則變成圍繞擴(kuò)大后空洞的曲線sabt.如圖2 所示，新的最短路徑可以分成三部分:直線段sa，弧段ab 以及直線段bt.將這三部分的長(zhǎng)度分別記為，則由幾何關(guān)系可得

因此，根據(jù)兩條最短路徑Pst和所包含的距離信息，結(jié)合(6)式和(7)式可以計(jì)算出節(jié)點(diǎn)s 和節(jié)點(diǎn)t 之間較為準(zhǔn)確的距離值dst.

2.2 與空洞交于一段

這種情況下，路徑與網(wǎng)絡(luò)中的一個(gè)空洞H 相交于一段。如圖3 所示，節(jié)點(diǎn)s 與節(jié)點(diǎn)t 與空洞H 相交于ab 段。

圖3 最短路徑與空洞交于一段Fig.3 The shortest path and the hole cross in a segment

按照2.1 節(jié)中的思路，同樣以a、b 為圓心，做虛擬空洞，節(jié)點(diǎn)s 和節(jié)點(diǎn)t 之間的最短路徑則變成圍繞擴(kuò)大后空洞的曲線sa1a2b1b2t.根據(jù)圖3 中的幾何關(guān)系，可以得到角度α 和β 如下:

那么待求的節(jié)點(diǎn)間距離dst= |st|就可以通過下式得到:

式中:

3 MDS-DO 算法

本文提出的MDS－DO 定位改進(jìn)算法主要由以下6 個(gè)步驟:1)探尋網(wǎng)絡(luò)中空洞的邊界節(jié)點(diǎn)并做標(biāo)記;2)計(jì)算兩兩節(jié)點(diǎn)間的最短路徑，構(gòu)成距離矩陣;3)建立虛擬空洞;4)根據(jù)需要計(jì)算節(jié)點(diǎn)間的虛擬最短路徑;5)重新計(jì)算節(jié)點(diǎn)間的歐式距離，更新距離矩陣;6)對(duì)距離矩陣應(yīng)用MDS 技術(shù)定位網(wǎng)絡(luò)中的未知節(jié)點(diǎn)。

算法步驟具體描述如下:

1)已有較好的邊界探尋算法完全可以完成第一步的探尋工作[7]。因此，算法重點(diǎn)討論如何利用節(jié)點(diǎn)間的幾何關(guān)系計(jì)算其距離。故假設(shè)網(wǎng)絡(luò)中空洞的邊界節(jié)點(diǎn)是已知的，已對(duì)邊界節(jié)點(diǎn)進(jìn)行標(biāo)記。

2)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)可利用Floyd 算法或者Dijkstra 算法計(jì)算其與其他節(jié)點(diǎn)間的最短路徑，并構(gòu)建距離矩陣。

3)當(dāng)距離矩陣構(gòu)建完成后，對(duì)于網(wǎng)絡(luò)中兩兩節(jié)點(diǎn)之間的距離，按照如下原則判斷是否需要構(gòu)建虛擬空洞:

①節(jié)點(diǎn)間的最短路徑中不含有標(biāo)記節(jié)點(diǎn)。這種情況說明節(jié)點(diǎn)間的連線并不穿過空洞，因此可直接用最短路徑值估計(jì)二者的歐氏距離。

②節(jié)點(diǎn)間的最短路徑只有一個(gè)點(diǎn)是為標(biāo)記節(jié)點(diǎn)，則按照2.1 節(jié)中介紹的方式構(gòu)建虛擬空洞。

③節(jié)點(diǎn)間的最短路徑包含多個(gè)標(biāo)記節(jié)點(diǎn)，按照2.2 節(jié)中介紹的方式構(gòu)建虛擬空洞。

4)完成虛擬空洞的建立后，將重新計(jì)算這兩個(gè)節(jié)點(diǎn)之間的最短路徑，即虛擬最短路徑。至此，估算節(jié)點(diǎn)間歐氏距離所需的所有直線段距離值和沿虛擬空洞邊界的弧段值均已經(jīng)求得。

5)利用節(jié)點(diǎn)的原始最短路徑和虛擬最短路徑，按照(6)式～(9)式就可以估算遠(yuǎn)距離節(jié)點(diǎn)間的真實(shí)距離值。此距離值更新距離矩陣，并取消該過程中建立的虛擬空洞。

6)當(dāng)完成所有需要重新計(jì)算的節(jié)點(diǎn)距離估算后，對(duì)更新后的距離矩陣應(yīng)用MDS 技術(shù)，就可以定位全網(wǎng)節(jié)點(diǎn)的位置坐標(biāo)。

整個(gè)算法的流程圖如圖4 所示。

4 仿真分析

選取區(qū)域大小為10 m ×10 m，網(wǎng)絡(luò)形狀為半C型網(wǎng)絡(luò)，通信半徑為0.5 m，測(cè)距誤差設(shè)定為5%.在Matlab 環(huán)境下對(duì)MDS－DO 算法進(jìn)行仿真，并與MDS－MAP 算法以及DV－h(huán)op 算法進(jìn)行比較。

在不同的節(jié)點(diǎn)數(shù)量以及連通度下，根據(jù)MDSDO 算法，建立虛擬空洞。如圖5 所示。

由圖5 可見，隨著節(jié)點(diǎn)數(shù)量及連通度的增加，最短路徑更加接近節(jié)點(diǎn)間的真實(shí)距離，虛擬空洞的邊界節(jié)點(diǎn)所形成的形狀更加接近圓形，故計(jì)算出優(yōu)化后的距離矩陣更加精確。表1 列出了不同節(jié)點(diǎn)數(shù)量及連通度下所有節(jié)點(diǎn)之間距離估計(jì)誤差率(距離估計(jì)誤差/真實(shí)距離)的平均值。可以看出隨著節(jié)點(diǎn)數(shù)量的增多，MDS－MAP 算法以及MDS－DO 算法的距離估計(jì)誤差均得到減小。然而，MDS－DO 算法在各種情況下的誤差都遠(yuǎn)遠(yuǎn)小于MDS－MAP 算法。

圖4 MDS－DO 算法流程Fig.4 MDS－DO flow chart

圖5 不同節(jié)點(diǎn)數(shù)量及連通度下虛擬空洞Fig.5 Virtual holes in the case of different node quantities and connectivity

表1 距離估計(jì)平均誤差率Tab.1 Average error rate of distance estimation

仿真節(jié)點(diǎn)數(shù)量為816、錨節(jié)點(diǎn)數(shù)量為5 時(shí)，MDSMAP 算法與MDS－DO 算法的最終定位情況如圖6所示。橫、縱軸表示監(jiān)測(cè)區(qū)域10 m ×10 m，可以看出，MDS－DO 算法的定位效果得到顯著提高。

圖6 MDS－MAP 與MDS－DO 算法定位效果比較Fig.6 Comparison of location performances

在不均勻布置的半C 型網(wǎng)絡(luò)中，仿真錨節(jié)點(diǎn)數(shù)量為5、不同節(jié)點(diǎn)數(shù)量及連通度的情況下，對(duì)MDSMAP 算法、DV－h(huán)op 算法以及MDS－DO 算法的平均定位誤差進(jìn)行了對(duì)比。如圖7 所示，橫軸選取了不同的節(jié)點(diǎn)數(shù)量及連通度，縱軸表示節(jié)點(diǎn)定位誤差，在節(jié)點(diǎn)數(shù)量及連通度較高的情況下，MDS－DO 算法定位優(yōu)勢(shì)更明顯，平均定位誤差相對(duì)于MDS－MAP 算法降低了約90%.

5 結(jié)論

本文針對(duì)不均勻布置傳感器網(wǎng)絡(luò)提出了一種距離優(yōu)化的MDS－DO 定位算法。該算法首先在空洞邊界的關(guān)鍵節(jié)點(diǎn)附近做虛擬空洞并計(jì)算虛擬最短路徑，根據(jù)幾何關(guān)系對(duì)距離矩陣進(jìn)行優(yōu)化，使得節(jié)點(diǎn)間距離信息更接近真實(shí)值，然后應(yīng)用MDS 技術(shù)進(jìn)行定位。

圖7 不同節(jié)點(diǎn)數(shù)量以及連通度下平均定位誤差比較Fig.7 Comparison of average location errors in the case of different node quantities and connectivity

仿真結(jié)果表明，同樣的監(jiān)測(cè)區(qū)域內(nèi)，在不同節(jié)點(diǎn)數(shù)量及連通度的情況下，MDS－DO 算法都能完成對(duì)節(jié)點(diǎn)間距離矩陣的精確估計(jì)，進(jìn)而在節(jié)點(diǎn)不均勻布置的網(wǎng)絡(luò)中取得了較好的定位效果。同時(shí)，MDSDO 算法的定位誤差明顯低于DV－h(huán)op 算法以及MDS－MAP 算法，在節(jié)點(diǎn)密度及連通度較高的情況下更加體現(xiàn)出其優(yōu)越性。

References)

[1]孫利民，李建中，陳渝.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社，2005.SUN Li－min，LI Jian－zhong，CHEN Yu.Wireless sensor networks[M].Beijing:Tsinghua University Press，2005.(in Chinese)

[2]Bulusu N，Heidemann J，Estrin D.GPS－less low cost outdoor localization for very small devices[J].IEEE Personal Communications，2000，7(5):28 －34.

[3]Shang Y，Ruml W，Zhang K，F(xiàn)romherz M.Localization from mere connectivity[C]∥Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc).Annapolis，MD，United States:ACM，2003:201 －212.

[4]Mao G Q，Baris F.Localization algorithms and strategies for wireless sensor networks[M].New York:Information Science Reference，2009.

[5]Vijayanth V，Wong V.Ordinal MDS－based localization for wireless sensor networks[C]∥IEEE Vehicular Technology Conference.Piscataway，NJ，USA:IEEE，2006:2514 －2518.

[6]Li M，Liu Y H.Rendered path:range－free localization in anisotropic sensor networks with holes[J].IEEE Transaction on Networking，2010，1(18):320 －332.

[7]Wang Y，Gao J，Joseph S B M.Boundary recognition in sensor networks by topological methods[C]∥Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc).Los Angeles，CA，United States:ACM，2006:122－133.