任克強，莊放望（江西理工大學信息工程學院，江西贛州341000）

?

最短路徑距離矩陣修正的多維標度定位算法

任克強*，莊放望
（江西理工大學信息工程學院，江西贛州341000）

摘要：為了減小最短路徑距離矩陣與歐氏距離矩陣之間的差異，提高MDS-MAP（C）算法的節(jié)點定位精度，提出一種改進的多維標度節(jié)點定位算法。該算法對MDS-MAP（C）算法進行了以下改進：采用啟發(fā)式的搜索策略對最短路徑距離矩陣進行修正，以減少最短路徑距離矩陣與實際的歐氏距離矩陣之間的誤差；利用smacof算法迭代誤差函數代替SVD分解來求解節(jié)點的定位問題，以優(yōu)化和改善節(jié)點定位的求解過程。實驗結果表明，與MDS-MAP（C）算法相比，改進算法能夠減少最短路徑距離的誤差，有效提高節(jié)點的定位精度，并且對不規(guī)則網絡具有更好的適應性。

關鍵詞：無線傳感器網絡；最短路徑；MDS-MAP（C）算法；節(jié)點定位；多維標度；smacof算法

無線傳感器網絡WSN（Wireless Sensor Net?work）由大量部署在監(jiān)測區(qū)域內的廉價微型傳感器節(jié)點構成，它是一種自組織、分布式處理以及快速展開的無線網絡［1］。傳感器節(jié)點的位置信息對WSN的監(jiān)測活動極其重要，獲取準確的傳感器節(jié)點位置信息是WSN進行相關監(jiān)測以及傳感器節(jié)點進行下一步活動和決策的基礎［2］。WSN的節(jié)點定位算法按定位機制的不同可分為基于測距（Rangebased）的算法和測距無關（Range-free）的算法［3-4］。Range-based算法通過測量節(jié)點之間的距離或角度來實現定位，Range-free算法則無需測量節(jié)點之間的距離和角度信息，而是根據網絡的連通性等信息來實現定位［5］。Range-based的代表算法有基于到達時間TOA（Time of Arrival）的定位、基于到達時間差TDOA（Time Difference of Arrival）的定位、基于接收信號強度指示RSSI（Received Signal Strength Indi?cator）的定位以及基于到達角度AOA（Angle of Ar?rival）的定位等算法［6-8］。Range-free的代表算法有距離向量-跳段DV-hop（Distance Vector-hop）定位、凸規(guī)劃（Convex Optimization）定位以及多維標度MDS（Multidimensional Scaling）定位等算法［9-10］。

MDS是一種將多維空間中的研究對象簡化到低維空間中進行定位、分析和歸類，并且保持研究對象之間原有關系的多元數據分析技術。Shang Yi等人將MDS技術應用于WSN的節(jié)點定位，提出了MDSMAP算法［11］；該算法利用節(jié)點間的連通性或距離估計信息進行定位，將節(jié)點間最短路徑距離近似為節(jié)點間的歐氏距離，再利用MDS方法進行定位；當網絡拓撲不規(guī)則時，由于最短路徑距離與節(jié)點間實際的歐氏距離相差較大，嚴重影響算法的定位精度。為了解決最短路徑距離與節(jié)點間實際歐氏距離的差異性問題，國內外研究人員提出了不同的MDS-MAP算法改進和優(yōu)化方案。文獻［12］將網絡拓撲分解為多個局部地圖，再按分布式的計算模式對局部地圖進行MDSMAP定位，減少了最短路徑距離與節(jié)點間實際歐氏距離的誤差，但在Range-Free環(huán)境的定位精度依然不高。文獻［13］在生成相對地圖的過程中采用迭代更新的方式來改善定位性能，使其定位精度有了較大的提升，但計算復雜度較高，節(jié)點的能耗較大。文獻［14］采用距離矩陣重構的方式來替代最短路徑距離矩陣，并用奇異值分解SVD（Singular Value Decompo?sition）低秩近似的方法來求解距離矩陣。文獻［15］提出基于距離矩陣重構的WSN多維標度定位算法，利用節(jié)點間的相關信息對距離矩陣進行線性重構，然后使用經典MDS進行定位，取得了較好的定位精度。文獻［16］針對MDS-MAP在不均勻網絡中定位精度較低的問題，提出一種可用于不均勻網絡的節(jié)點定位算法，有效地減小了平均定位誤差。文獻［17］提出改進距離重構的三維節(jié)點定位算法，該算法利用MDS-MAP算法獲取節(jié)點之間相對的坐標，并采用精度更高的坐標映射方案對坐標轉換過程進行優(yōu)化，取得了較高的三維節(jié)點定位精度。

針對最短路徑距離與節(jié)點之間實際歐氏距離的差異性問題，本文提出一種基于最短路徑距離矩陣修正的多維標度定位算法MDS-DMC（MDSDistance Matrix Correction），通過修正最短距離矩陣來逼近歐氏距離矩陣，以提高節(jié)點的定位精度。

1　多維標度定位算法

MDS-MAP（C）是一種基于經典MDS（Classical MDS，CMDS）的多維標度定位算法，該算法將各個節(jié)點視作一個實體元素，各節(jié)點之間的相似性用歐氏空間距離來表示，通過建立歐氏空間距離與相似性信息的線性映射關系后，就可在多維空間內獲得節(jié)點的分布。如果獲得的相似性信息與歐氏空間距離的差異不大，則利用CMDS就可得到各節(jié)點之間相對的位置空間分布。

令Pi，j為m維空間中i和j兩個點的相似性信息，通常等價于歐氏空間距離di，j，i點坐標為xi=(xi1，xi2，…，xim)，j點坐標為xj=(xj1，xj2，…，xjm)，則：

其中，e為元素全1的N×1維向量。

定義中心矩陣H=I-eeT/N（I為單位矩陣），對D進行雙中心化：

2　MDS-DMC算法

MDS-MAP（C）算法以節(jié)點之間的最短路徑距離替代歐氏空間距離，并采用SVD分解求解節(jié)點位置。在密集且分布均勻的網絡環(huán)境中，最短路徑距離可以近似歐氏空間距離；但在稀疏且分布不均的網絡環(huán)境中，最短路徑距離與歐氏空間距離的差異往往很大，此時兩者近似將產生較大的誤差。此外，當網絡規(guī)模很大時，采用SVD分解求解節(jié)點位置比較復雜且定位精度不高。本文針對這些問題，提出MDS-DMC算法，對MDS-MAP （C）算法進行了兩個方面的改進：①采用啟發(fā)式的搜索策略對最短距離矩陣進行修正，以減少最短距離矩陣與實際的歐氏距離矩陣之間的誤差；②使用smacof算法迭代誤差函數代替SVD分解來求解定位問題，以改善和優(yōu)化節(jié)點定位的求解過程。

2.1最短距離矩陣的修正

假定節(jié)點所能輻射范圍的通信半徑為R，A、C兩個節(jié)點之間的距離L無法直接獲取，如圖1所示。

如果用最短路徑算法求取的最短路徑距離來近似代替A、C節(jié)點之間的距離L，則有AC≈AB+BC，即L≈d1+d2。

很明顯，這種近似存在誤差。為了減少誤差，本文通過以下啟發(fā)式的搜索策略來修正最短距離矩陣。

根據余弦定理，有：

由上可得：

因此，通過以上方法修正最短距離矩陣，可以改善用最短距離矩陣近似歐氏距離矩陣產生的誤差。

2.2求解節(jié)點位置的改進

對于節(jié)點數目為N的網絡，使用SVD分解求解節(jié)點位置的復雜度為O(N3)，當節(jié)點規(guī)模很大時，一般采用迭代的方法代替SVD分解，以提高求解節(jié)點位置的效率。本文采用Metric MDS求解節(jié)點的位置，并利用smacof算法迭代誤差函數代替SVD方法求解節(jié)點的定位問題，以下簡稱為MDS-MAP （smacof）算法。

定義函數S作為估算距離與實際距離的誤差函數：

將式（10）展開得到：

將式（11）轉化成矩陣形式：

其中，trace{?}為跡運算，代表矩陣的對角線元素之和；X是由所有節(jié)點組成的矩陣[x1，x2，…，xN]，XT是X的轉置；H為中心矩陣，H=I-eeT/N，I為單位矩陣；Ψ(X)是關于X的中心矩陣，其元素由式（13）組成：

采用smacof算法，定義輔助函數φ(X，Z)為：

每次迭代k，采用Z=Xk-1，由于φ(X，Z)的梯度函數為：

令梯度為0，可以得到：

根據矩陣H的特性，可以推導出X的迭代形式：

從而，節(jié)點的坐標可通過迭代的方式求得。

分析式(17)的迭代公式，求解該遞歸過程的復雜度為O(N2)，即節(jié)點坐標求解過程的復雜度為O(N2)；而執(zhí)行SVD分解求解節(jié)點位置的復雜度為O(N3)。因此，通過smacof算法可有效降低求解節(jié)點位置的復雜度。

圖1　最短距離矩陣修正示意圖

3　實驗結果及分析

為了測試MDS-DMC算法的改進效果，本文對MDS-MAP（C）算法、MDS-MAP（smacof）算法和MDSDMC算法進行了仿真比較實驗。實驗平臺：WIN?DOWS XP SP3+MATLAB 2009a。實驗環(huán)境與場景：矩形隨機網絡、C型隨機網絡；2-D平面L×L的區(qū)域內隨機分布300個節(jié)點，包括4個錨節(jié)點。實驗參數：未知節(jié)點通信半徑為r，錨節(jié)點通信半徑為R，并且r=R。

使用歸一化的平均定位誤差來評價實驗算法的性能：

其中，N為網絡節(jié)點個數，M為錨節(jié)點個數，r為未知節(jié)點通信半徑，xi為節(jié)點i實際位置，為節(jié)點i估計位置。

3.1理想傳輸模型下的定位

該實驗主要比較三種算法在理想傳輸模型的不同網絡拓撲下的性能。在實驗場景的兩種網絡拓撲下，隨機部署300個節(jié)點，在通信半徑為0.2 L的情況下，矩形網絡平均連通度為31.1，C型網絡平均連通度為34.6，分別用MDS-MAP（C）算法、MDS-MAP（smacof）算法和MDS-DMC算法進行定位。該實驗的節(jié)點分布以及定位誤差如圖2~圖4所示，圖中空心圓圈代表未知節(jié)點的坐標，實心圓圈代表錨節(jié)點的位置，線段代表定位誤差。

圖2　理想傳輸模型下的網絡分布

圖3　理想傳輸模型下矩形網絡的定位

圖4　理想傳輸模型下C形網絡的定位

由實驗結果可知，在矩形網絡中，MDS-MAP （C）算法的平均定位誤差為18.7%；MDS-MAP （smacof）算法的平均定位誤差有了的改善，為16.9%；而MDS-DMC算法的平均定位誤差僅為4.1%，有效的提高了定位的精度。在C型網絡中，由于不規(guī)則網絡的影響，出現了拓撲空洞的情況，最短路徑距離矩陣存在較大的誤差，導致MDSMAP（C）算法的平均定位誤差高達117.8%，而采用MDS-MAP（smacof）算法和MDS-DMC算法的平均定位誤差分別為95%和17%，MDS-DMC算法大幅度的減小了平均定位誤差。因此，在C型網絡中，MDS-DMC算法可以有效減少最短路徑距離的差異，改善定位性能，提高對不規(guī)則網絡的適應性。

3.2非理想傳輸模型下的定位

非理想傳輸模型的定位可用不規(guī)則的信號模型來模擬實際的環(huán)境，采用不規(guī)則度DOI（Degree of Irregular）表征錨節(jié)點的傳播信號在傳輸的過程中受到的影響，DOI值反映了錨節(jié)點信號廣播的不規(guī)則程度。該實驗主要比較三種算法在非理想傳輸模型的不同網絡拓撲下的性能，在實驗場景的兩種網絡拓撲下，隨機部署300個節(jié)點，在通信半徑為0.2L以及DOI為0.2的情況下，矩形網絡平均連通度為30.3，C型網絡平均連通度為35.9，分別用MDS-MAP（C）算法、MDS-MAP（smacof）算法和MDSDMC算法進行定位。該實驗的節(jié)點分布以及定位誤差如圖5~圖7所示。

圖6　非理想傳輸模型下矩形網絡的定位

圖7　非理想傳輸模型下C形網絡的定位

由實驗結果可知，在非理想傳輸模型的矩形網絡中，MDS-MAP（C）算法、MDS-MAP（smacof）算法以及MDS-DMC算法的平均定位誤差分別為20.7%、17.4%和8.1%，MDS-DMC算法的定位性能有了明顯的改善。而在非理想傳輸模型的C型網絡中，由于最短路徑距離矩陣差異的影響不同，MDS-MAP （C）算法、MDS-MAP（smacof）算法以及MDS-DMC算法的平均定位誤差分別為118%、107%和18.1%，MDS-DMC算法定位性能的提升更為顯著。因此，MDS-DMC算法能夠較穩(wěn)定的適應非理想傳輸模型的節(jié)點定位，提高不規(guī)則網絡的節(jié)點定位精度。

3.3不同連通度的定位誤差

該實驗主要比較三種算法在不同通信半徑和連通度下的性能。在實驗場景的兩種網絡拓撲下，隨機部署300個節(jié)點，節(jié)點通信半徑r分別取0.125L、0.15L、0.175L、0.2L、0.225L和0.25L時，矩形網絡的連通度分別為13.6、18.7、25.1、31.1、38.0和48.3，C型網絡的連通度分別為16.5、22.8、29.1、38.2、45.1和51.3。實驗結果如圖8所示。

從圖8可以看出，MDS-DMC算法在不同連通度的定位性能均優(yōu)于MDS-MAP（C）算法，在連通度較低的情況下，MDS-DMC算法的定位精度有了明顯的提高，特別是在C型網絡中，定位精度的提高幅度更大。因此，與MDS-MAP（C）算法相比，MDS-DMC算法在不規(guī)則網絡拓撲下有更好的適應性，在WSN的定位應用中具有明顯的優(yōu)勢。

圖8　不同連通度的歸一化平均定位誤差比較

4　結論

①針對MDS-MAP（C）算法中的距離矩陣問題，提出MDS-DMC算法。該算法采用啟發(fā)式搜索的最短路徑距離修正策略來減小最短路徑距離與實際歐氏距離之間的誤差，有效地提高了節(jié)點的定位精度和對不規(guī)則網絡的適應性；引入smacof算法迭代誤差函數取替SVD分解來優(yōu)化節(jié)點定位的求解過程，進一步提升了算法的性能。

②在理想傳輸模型、非理想傳輸模型以及不同傳輸半徑和連通度的算法仿真對比實驗中，MDSDMC算法均表現出比MDS-MAP（C）算法更加優(yōu)異的性能，進而驗證了改進方法是正確和有效的。

③減小最短路徑距離與實際歐氏距離之間的誤差是提高多維標度節(jié)點定位算法性能的有效途徑之一。如何進一步減小距離矩陣之間的差異是后續(xù)重點的研究工作。

參考文獻：

［1］Liu Qiang，Huang Xiaohong，Leng Supeng，et al. Deployment Strategy of Wireless Sensor Networks for Internet of Things［J］. China Communications，2011，8（8）：111-120.

［2］侯洪濤，周鴻偉，李群，等.衛(wèi)星導航系統(tǒng)接收傳感器網絡的攻擊檢測研究［J］.系統(tǒng)工程與電子技術，2014，36（6）：1195-1200.

［3］王福豹，史龍，任豐原.無線傳感器網絡中的自身定位系統(tǒng)和算法［J］.軟件學報，2005，16（5）：857-868.

［4］張亞明，史浩山，劉燕，等.不對稱鏈路環(huán)境下的WSN節(jié)點定位算法［J］.傳感技術學報，2014，27（3）：320-326.

［5］劉瑜，衣曉，何友.基于分治求精的無線傳感器網絡節(jié)點定位算法［J］.系統(tǒng)工程與電子技術，2012，34（9）：1906-1913.

［6］錢志鴻，王義君.面向物聯(lián)網的無線傳感器網絡綜述［J］.電子與信息學報，2013，35（1）：215-227.

［7］Park J W，Park D H，Lee C. Angle and Ranging Based Localiza?tion Method for ad hoc Network［J］. The Journal of Supercomput?ing，2013，64（2）：507-521.

［8］袁鑫，吳曉平，王國英.線性最小二乘法的RSSI定位精確計算方法［J］.傳感技術學報，2014，27（10）：1412-1417.

［9］彭宇，王丹.無線傳感器網絡定位技術綜述［J］.電子測量與儀器學報，2011，25（5）：389-399.

［10］Macagnano D，de Abreu G. Algebraic Approach for Robust Local?ization with Heterogeneous Information［J］. IEEE Transactions on Wireless Communication，2013，12（10）：5334-5345.

［11］Shang Y，Ruml W，Zhang Y，et al. Localization from Mere Connec?tivity［C］//Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York：ACM Press，2003：201-212.

［12］Shang Y，Ruml W. Improved MDS-based localization［C］// Twen?ty-Third Annual Joint Conference of the IEEE Computer and Com?munications Societies. Washington：IEEE Press，2004：2640-2651.

［13］Vivekanandan V，Wong V W S. Ordinal MDS-Based Localisation for Wireless Sensor Networks［J］. International Journal of Sensor Networks，2006，1（3）：169-178.

［14］Regalia P A，Wang J. On Distance Reconstruction for Sensor Net?Work Localization［C］// Proceedings of 2010 IEEE International Conference on Acoustics Speech and Signal Processing，Washing? ton：IEEE Press，2010：2866-2869.

［15］黃亮，王福豹，段渭軍，等.基于距離重構的無線傳感器網絡多維定標定位算法［J］.傳感技術學報，2013，26（9）：1284-1287.

［16］溫龍飛，崔靈果，張百海，等.不均勻布置傳感器網絡定位優(yōu)化算法［J］.兵工學報，2013，34（05）：639-643.

［17］張亞杰，段渭軍，王福豹，等.改進的距離重構三維定位算法［J］.傳感技術學報，2014，27（12）：1681-1686.

任克強（1959-），男，教授，碩士研究生導師，主要研究方向為嵌入式系統(tǒng)、無線傳感器網絡等，jxrenkeqiang@163.com；

莊放望（1988-），男，碩士研究生，主要研究方向為無線傳感器網絡。

A Preliminary Study of Zanthoxylurn Bungeanum Maxim Varieties Discriminating by Computer Vision*

WU Lili*，XING Yuqing，ZHENG Baozhou，LIN Aiying
（College of Sciences，Henan Agricultural University，Zhengzhou 450002，China）

Abstract：Zanthoxylurn Bungeanum Maxim is a kind of important ingredients for cooking and traditional Chinese medicine. In this paper，the computer vision technology was introduced to discriminate the varieties of Zanthoxylurn Bungeanum Maxim rapdily. The Zanthoxylurn Bungeanum Maxim image of six categories were obtained by the com?puter vision hardware device，and the total number of images was 90，of which 60 were used as training samples and 30 as test samples. The 10 feature parameters of color and texture features were extracted from all the samples，which were identified by the probabilistic neural network. The correct recognition rate was 93.33%. The discrimination method of Zanthoxylurn Bungeanum Maxim varieties by computer vision can quickly and accurately extract the char?acteristic data of the Zanthoxylurn Bungeanum Maxim samples，which lays the technical foundation for batch sorting. Key words：computer vision；color feature；texture feature；probabilistic neural network；Zanthoxylurn Bungeanum Maxim

doi：EEACC：6135;7230G10.3969/j.issn.1004-1699.2016.01.023

收稿日期：2015-08-06修改日期：2015-10-20

中圖分類號：TP393

文獻標識碼：A

文章編號：1004-1699（2016）01-0129-07