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

(北京理工大學 自動化學院，北京100081)

0 引言

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

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

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

1 多維定標技術及定位

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

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

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

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

再對矩陣B 進行特征值分解，

可得到坐標矩陣

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

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

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

圖1 MDS 距離估計示意圖Fig.1 MDS distance estimation

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

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

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

2.1 與空洞交于一點

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

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

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

則待求兩點間的距離可以表示為

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

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

2.2 與空洞交于一段

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

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

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

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

式中:

3 MDS-DO 算法

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

算法步驟具體描述如下:

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

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

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

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

②節(jié)點間的最短路徑只有一個點是為標記節(jié)點，則按照2.1 節(jié)中介紹的方式構建虛擬空洞。

③節(jié)點間的最短路徑包含多個標記節(jié)點，按照2.2 節(jié)中介紹的方式構建虛擬空洞。

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

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

6)當完成所有需要重新計算的節(jié)點距離估算后，對更新后的距離矩陣應用MDS 技術，就可以定位全網(wǎng)節(jié)點的位置坐標。

整個算法的流程圖如圖4 所示。

4 仿真分析

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

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

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

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

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

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

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

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

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

5 結論

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

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

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

References)

[1]孫利民，李建中，陳渝.無線傳感器網(wǎng)絡[M].北京:清華大學出版社，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.