結合極大似然距離估計的MDS-MAP節(jié)點定位算法*

李津蓉，王萬良，介　婧，姚信威

（1.浙江工業(yè)大學計算機科學與技術學院，杭州310023；2.浙江科技學院自動化與電氣工程學院，杭州310023）

結合極大似然距離估計的MDS-MAP節(jié)點定位算法*

李津蓉1，2，王萬良1*，介婧2，姚信威1

（1.浙江工業(yè)大學計算機科學與技術學院，杭州310023；2.浙江科技學院自動化與電氣工程學院，杭州310023）

基于多維定標的定位算法通常利用節(jié)點間的最短路徑長度代替歐式距離構建距離矩陣，當網絡拓撲結構不規(guī)則時，會導致較大的定位誤差。針對這一問題，提出了一種結合極大似然距離估計和多維定標的節(jié)點定位算法MDS-MAP（MLE）。算法將待測節(jié)點的一跳鄰居節(jié)點信息作為極大似然方法的輸入，利用與鄰居節(jié)點的距離信息計算待測節(jié)點的相對坐標，然后根據已知錨節(jié)點的坐標，將所有節(jié)點的相對坐標映射為絕對坐標。實驗結果表明，針對規(guī)則網絡和不規(guī)則網絡，MDS-MAP （MLE）算法均可取得較好的定位精度，且當網絡連通度在一定范圍內變化時，定位誤差可保持在較低的穩(wěn)定區(qū)間內。

無線傳感網絡；定位算法；多維定標；極大似然方法

EEACC:7230doi:10.3969/j.issn.1004-1699.2016.04.018

無線傳感器網絡中的節(jié)點定位機制是指依靠有限的位置已知節(jié)點，確定布設區(qū)域內其它節(jié)點的位置，建立各個傳感器節(jié)點間的二維或三維空間關系。高密度的傳感器節(jié)點通過近距離感知物理世界，為分析計算系統(tǒng)提供具有較高準確性和實時性的信息。而在大多數情況下，只有結合準確的位置信息，傳感器所獲得的數據才有實際的應用價值，如目標定位與跟蹤、險情監(jiān)測、環(huán)境勘查等［1］。

基于多維定標MDS（Multi Dimensional Scaling）的節(jié)點定位算法MDS-MAP［2-4］由于其所需錨節(jié)點的數目少，且可在基于測距和無需測距兩種情況下使用，近年來成為節(jié)點定位技術的研究熱點。但由于MDS-MAP算法利用網絡節(jié)點間的最短距離近似歐式距離，導致網絡的距離矩陣不準確，特別是當網絡拓撲結構不規(guī)則或網絡中存在通信空洞時，由于節(jié)點間的最短路徑距離與實際的歐式距離差距較大，導致最終節(jié)點定位結果的誤差難以接受［5］。

針對MDS-MAP所存在的問題，Shang提出了分布式MDS算法MDS-MAP（P）［6］，這種方法首先將兩跳之內的鄰居節(jié)點利用MDS算法獲得局部地圖，然后利用貪婪算法對局部地圖進行融合得到所有節(jié)點的相對坐標，最后利用坐標已知的錨節(jié)點將各節(jié)點的相對坐標映射為絕對坐標。在此基礎之上，一系列基于網絡分簇的MDS-MAP算法［7-11］被提出，這類算法的基本思想是首先將網絡節(jié)點基于某種策略分成若干“簇”，各個簇頭節(jié)點利用局部信息對簇內節(jié)點進行定位，再將簇內地圖通過融合算法構成全局地圖。這類算法利用局部路徑信息對節(jié)點進行定位，避免了遠距離節(jié)點間的最短路徑距離與歐式距離的較大誤差，因此定位精度較高。但這類算法通常存在以下問題: 1）分簇算法較復雜，且簇的劃分對后續(xù)算法的運行效率及定位精度有較大影響；2）局部地圖的融合過程開銷較大，且會出現(xiàn)誤差累積問題。

針對以上算法不足，本文提出一種結合極大似然距離估計的MDS-MAP節(jié)點定位算法MDS-MAP （MLE）。MDS-MAP（MLE）算法首先利用MDS方法對一個一跳連接子網（即子網內各個節(jié)點均為一跳鄰居關系）內的所有節(jié)點進行定位；然后利用極大似然方法對子網外的其余節(jié)點進行定位，逐步擴散子網直至覆蓋整個網絡。仿真實驗表明，針對規(guī)則網絡和不規(guī)則網絡，該算法均可取得較好的定位精度。

1　MDS-MAP（MLE）算法

為了避免經典MDS-MAP算法中利用節(jié)點間的最短路徑距離近似歐式距離所造成的計算誤差，MDS-MAP（MLE）算法的基本思想是首先僅利用一跳鄰居間的距離信息進行節(jié)點定位，然后將已定位的節(jié)點作為極大似然算法［12-13］中的錨節(jié)點，對相鄰節(jié)點進行定位；逐步擴大已定位節(jié)點的范圍，直至覆蓋整個網絡。

假設自組織網絡內共有N個傳感器節(jié)點，節(jié)點集合記為V，對應的坐標向量為X=［X1，X2，…，XN］T，其中Xi=（xi，yi），（i=1，…，N）表示第i個節(jié)點的坐標。MDS-MAP（MLE）算法步驟如下:

Step 1根據網絡連通情況，構建全網鄰接矩陣A（N×N），若節(jié)點i與j為一跳鄰居關系，則矩陣元素aij=1，否則aij=0。

Step 2在全局網絡中找到一跳鄰居子網。這相當于在全局網絡所對應的無向圖G中找到一個全連接子圖，這通常被稱為最大團問題MCP（Maximum Clique Problem），是一NP完全問題，需要使用相應的優(yōu)化策略搜索最優(yōu)解。但在我們的實際應用中只需要找到一個全連接子圖即可，而并不要求為最大子圖，因此為了簡化算法，我們采用以下策略:①在鄰接矩陣A中刪除鄰居最少的節(jié)點所對應的行和列，得到矩陣A′；②檢查矩陣A′是否為全1矩陣，是則退出循環(huán)；否則，令A=A′，回到步驟①）。當以上算法結束時，A′中所有行（或列）所對應節(jié)點的集合記為VCLOSED，其中所有節(jié)點為全連接關系，構成了1跳鄰居子網，網絡中的其余節(jié)點集合記為VOPEN，即VOPEN=V-VCLOSED。

Step 3計算1跳鄰居子網中所有節(jié)點的相對坐標。由于VCLOSED中所有節(jié)點均為一跳鄰居關系，因此直接利用測距方法所獲得的節(jié)點距離測量值構建節(jié)點距離矩陣，并利用MDS方法計算VCLOSED中所有節(jié)點的相對坐標值。

Step 4根據全網鄰接矩陣A，在VOPEN中找到一個節(jié)點v，要求集合VCLOSED中與v構成一跳鄰居關系的節(jié)點數大于等于3，假設節(jié)點集合｛v1，v2，…，vm｝?VCLOSED，且v1，v2，…，vm與節(jié)點v均為一跳鄰居關系，由于在Step 3中已通過MDS方法計算得到v1，v2，…，vm的坐標，因此可利用極大似然方法計算節(jié)點v的坐標，記錄節(jié)點v的坐標，并將節(jié)點v從VOPEN集合轉移到VCLOSED集合，即VOPEN=VOPEN-v，VCLOSED=VCLOSED?v。

Step 5重復Step 4，直至集合VOPEN=?，此時VCLOSED集合包含了網絡中的所有節(jié)點，且已計算獲得所有節(jié)點的相對坐標矩陣

Step 6利用坐標已知的錨節(jié)點，將VCLOSED集合中節(jié)點的相對坐標矩陣轉換為絕對坐標矩陣

2　實驗研究及性能分析

為了測試MDS-MAP（MLE）算法對自組織傳感器網絡中節(jié)點的定位性能，我們在Matlab2012b環(huán)境下分別對規(guī)則網絡和不規(guī)則網絡中的節(jié)點定位進行了仿真實驗。

2.1算法流程示例

首先，以一個規(guī)則網絡為例，說明算法的運行流程。在1 000 m×1 000 m正方形網絡區(qū)域內隨機部署200個節(jié)點，其中錨節(jié)點數量為40個，其余為待測節(jié)點，錨節(jié)點和待測節(jié)點的位置均為隨機，測距誤差為0。經算法Step 2，可在全局網絡的中部找到一個包含14個節(jié)點的一跳鄰居子網，子網內的任意兩節(jié)點均為一跳鄰居關系。網絡布局及子網連接如圖1所示，其中，黑色實心圓點表示錨節(jié)點，空心圓點表示待測節(jié)點，節(jié)點間的連線表示節(jié)點為一跳鄰居關系。此時，子網內的所有節(jié)點構成了集合VCLOSED，其余節(jié)點構成集合VOPEN。對VCLOSED集合中的節(jié)點利用MDS算法得到它們的相對坐標，之后即可根據Step 4進行迭代，在集合VOPEN中尋找與VCLOSED子網連接度大于3的一跳鄰居節(jié)點，利用極大似然方法計算它的相對坐標，并將其加入VCLOSED集合。圖2給出了第一次迭代、和最后一次迭代時，VCLOSED集合中節(jié)點相對坐標，其中“黑色□”表示新加入的節(jié)點，黑色虛線表示新加入節(jié)點與VCLOSED集合中節(jié)點的一跳鄰居關系。

圖1　示例網絡拓撲結構及一跳鄰居子網

圖2　MDS-MAP（MLE）算法迭代結果（相對定位）

最終，網絡中所有節(jié)點定位結果如圖3所示，圖中每個節(jié)點連接的線段末端為節(jié)點實際坐標位置，即線段越長，則定位誤差越大。節(jié)點i的定位誤差δi記為

其中，R表示節(jié)點的通信半徑。實際上此次實驗中節(jié)點的平均誤差僅為1.0×10-4，因此圖中的線段近似于一點。

圖3　MDS-MAP（MLE）算法的定位結果

2.2性能分析及比較

為了進一步分析MDS-MAP（MLE）算法的性能，將其與經典MDS-MAP算法分別在規(guī)則網絡和不規(guī)則網絡連接環(huán)境下進行比較。算法性能通過待測節(jié)點定位的最大誤差、最小誤差、平均誤差和運行時間進行評估。在1 000 m×1 000 m的方形區(qū)域內隨機部署200個節(jié)點，其中20個錨節(jié)點，節(jié)點通信半徑為200 m，測距誤差為5%。圖4（a）為網絡規(guī)則連接情況，圖4（b）為C形網絡連接情況。

圖4　網絡連接圖

MDS-MAP算法和MDS-MAP（MLE）算法的定位結果如圖5和圖6所示，從圖5和圖6可以看出，MDS-MAP（MLE）算法的定位精度明顯高于MDSMAP，尤其是在不規(guī)則連接的網絡中，由于節(jié)點間的路徑距離與歐式距離的偏差較大，導致MDSMAP算法的定位結果非常不準確，而MDS-MAP （MLE）算法成功避免了這一問題，定位效果較好。兩種算法的性能指標如表1所示。

圖5　兩種算法對規(guī)則網絡中節(jié)點的定位結果比較

圖6　兩種算法對C形網絡中節(jié)點的定位結果比較

表1　兩種算法對節(jié)點定位的性能比較

當網絡中的節(jié)點數量或節(jié)點通信半徑變化時，均會影響網絡連通度，進而對定位算法的結果產生影響，為此我們在不同的網絡連通度下，對兩種算法分別在規(guī)則網絡和不規(guī)則網絡中的定位誤差進行了比較，比較結果如圖7所示。

從圖7可以看出，MDS-MAP算法的定位誤差會隨著連通度的提高明顯下降，而MDS-MAP（MLE）算法的定位誤差則保持一個穩(wěn)定的較低水平。分析兩種算法的工作原理，可知其原因如下:MDS-MAP算法的定位誤差主要來自于節(jié)點間的最短路徑距離與歐式距離的偏差，當連通度較低時，由于任意兩節(jié)點間的連通路徑數量較少，使得所選出的最短路徑長度與兩節(jié)點的歐式距離有很大偏差，導致定位誤差較大，而當網絡連通度提高時，節(jié)點的最短路徑長度與歐式距離接近，使得定位誤差顯著降低。MDS-MAP （MLE）算法的定位誤差主要由節(jié)點的測距誤差所導致，網絡連通度的提高可以增加待測節(jié)點的鄰居數量，若測距誤差滿足高斯分布，使用極大似然算法計算待測節(jié)點的相對坐標時，可以更好地消除測距誤差的影響。但當測距誤差不是很顯著時（小于5%），鄰居節(jié)點數量的增加對定位誤差的消除不會產生明顯作用。因此，對于MDS-MAP（MLE）算法而言，只要待測節(jié)點的已知鄰居數量滿足算法要求，即可在一定范圍的網絡連通度內保持較低的定位誤差水平。

圖7　兩種算法在不同網絡連通度下的定位誤差比較

由于網絡節(jié)點間的測量距離是獲得節(jié)點相對坐標的唯一依據，因此測距誤差會對定位結果產生嚴重影響。為此，在實驗中考慮了測量誤差為通信距離的0～20%范圍內，并假設測量誤差滿足正態(tài)分布，對MDS-MAP（MLE）和MDS-MAP的定位誤差進行了比較，比較結果如圖8所示。

圖8　兩種算法在不同測量誤差下的定位誤差比較

由圖8可以看出，當測距誤差上升時，MDS-MAP （MLE）與MDS-MAP算法定位誤差的增長趨勢基本一致，無明顯的誤差積累現(xiàn)象，這實際上得益于測距誤差為正態(tài)分布的假設。由于在MDS-MAP（MLE）算法的每次迭代過程中，使用極大似然算法對未知節(jié)點進行定位時，利用了多個鄰居節(jié)點與未知節(jié)點的距離信息，測距誤差在一定程度上相互抵消，可獲得較為準確的定位結果。但如果測距誤差不滿足正態(tài)分布，或用于定位的鄰居節(jié)點數量較少時，則會產生較嚴重的誤差累積現(xiàn)象，在這種情況下，如何進一步提高算法的容錯性還需進行更為深入的研究。

3　結論

本文提出了一種基于極大似然方法估計節(jié)點間歐式距離的無線傳感器網絡多維定標自定位算法MDS-MAP（MLE），該算法避免了經典MDS-MAP算法中利用最短路徑近似歐式距離所導致的誤差。仿真實驗表明，MDS-MAP（MLE）算法在規(guī)則網絡和不規(guī)則網絡中均可獲得較高的定位精度，且當網絡連通度在一定范圍內變化時，定位誤差可保持在一個相對穩(wěn)定的低水平區(qū)間之內。但MDS-MAP （MLE）算法仍屬于集中式定位算法，且計算速度與MDS-MAP算法相比無明顯優(yōu)勢，在此方面需做進一步的深入研究。

［1］ 于海斌，梁煒，曾鵬.智能無線傳感器網絡系統(tǒng)［M］.第2版.北京:科學出版社，2013.

［2］ Amin K，Oh S.Robust Localization from Incomplete Local Information［J］.IEEE-ACM Transactions on Networking，2013 21（4）: 1131-1144.

［3］ 劉政.基于粒子群優(yōu)化的多維標度節(jié)點定位算法［J］.傳感技術學報，2015，28（8）:1228-1232.

［4］ Amar A，Wang Y Y，Leus G，et al.Extending the Classical Multidimensional Scaling Algorithm Given Partial Pairwise Distance Measurements［J］.IEEE Signal Processing Letters，2010，17（5）: 473-476.

［5］ 明良，趙剛，謝桂海，等.面向智能空間的位置感知算法研究［J］.軟件學報，2009，20（3）:671-681.

［6］ Shang Y，Ruml W.Improved MDS-based Location［C］//Proc of the 23rd Conf of the IEEE Communications Society，2004:2640-2651.

［7］ Shon M，Jo M，Choo H.An Interactive Cluster-Based MDS Localization Scheme for Multimedia Information in Wireless Sensor Networks［J］.Computer Communications，2012，35（15）:1921-1929.

［8］ 王勇，胡良梁，袁巢燕.基于密度分簇的無線傳感器網絡定位算法［J］.電子科技大學學報，2013，43（3）:406-409.

［9］ Shon M，Choi W，Choo H，et al.A Cluster-Based MDS Scheme for Range-Free Localization in Wireless Sensor Networks［C］//Cyber-Enabled Distributed Computing and Knowledge Discovery（CyberC），2010 International Conference，2010:42-47.

［10］Sert S A，Bagci H，Yazici A，et al.MOFCA:Multi-Objective Fuzzy Clustering Algorithm for Wireless Sensor Networks［J］.Applied Soft Computing，2015，30:151-165.

［11］劉健苗，許新忠，黃書廣，等.改進的分布式無線傳感器網絡多維標度定位算法［J］.傳感技術學報，2014，27（5）:692-697.

［12］Weiss A J，Picard J S.Network Localization with Biased Range Measurements［J］.IEEE Transactions on Wireless Communications，2008，7（1）:298-304.

［13］鐘麗鴻，胡成全，金京姬.基于RSSI極大似然估計定位算法的分析與實現(xiàn)［J］.吉林大學學報（理學版），2014，52（3）:557-660.

李津蓉（1977-），女，天津市人，博士，副教授?，F(xiàn)為浙江科技學院自動化與電氣工程學院教師，浙江工業(yè)大學計算機科學與技術學院博士后，主要研究方向包括:無線傳感器網絡，機器學習、智能計算等；

王萬良（1957-），男，江蘇高郵人，博士，教授，現(xiàn)為浙江工業(yè)大學計算機科學與技術學院院長，主要研究方向包括:計算機控制與智能自動化、網絡化控制與遠程監(jiān)控、復雜系統(tǒng)的智能調度與優(yōu)化控制、無線網絡與物聯(lián)網等；

介婧（1972-），女，博士（博士后），教授?，F(xiàn)為浙江科技學院自動化與電氣工程學院教師。主要研究方向包括智能控制、調度優(yōu)化、智能系統(tǒng)及檢測裝備，群智能及機器人。

Localization Algorithm for Wireless Sensor Networks Based on MDS-MAP Integrated with Maximum Likelihood Estimating*

LI Jinrong1，2，WANG Wanliang1*，JIE Jing2，YAO Xinwei1
（1.College of Computer Science&Technology，Zhejiang University of Technology，Hangzhou 310023，China；2.School of Automation and Electric Engineering，Zhejiang University of Science&Technology，Hangzhou 3100233，China）

The multidimensional scaling（MDS）positioning algorithms of wireless sensor networks usually use the length of shortest path in lieu of the Euclidean distance between two nodes to build the distance matrix，which may result in large positioning errors，especially when the network topology is irregular.To solve this problem，a new localization algorithm MDS-MAP（MLE）was proposed in this work，in which the MDS-MAP method and Maximum Likelihood Estimating was combined.The information coming from the 1-hop neighbors are deemed as the input of the maximum likelihood method to estimate the relative coordinate of the tested node.And this process will iterate until all unknown nodes'relative coordinate are estimated.And then the global map can be transformed to an absolute map based on the absolute positions of anchors.Simulation results shows that the MDS-MAP（MLE）algorithm can get high positioning precision，either for regular or irregular network.In addition，the positioning errors can stay relatively constant at a low level when the network connectivity vary within a certain range.

wireless sensor networks；localization algorithm；multidimensional scaling；maximum likelihood 6210Q

TP393

A

1004-1699（2016）04-0572-06

項目來源:國家自然科學基金項目（61379123）；國家自然科學基金項目（61402414）；浙江省自然科學基金項目（LQ14F050002）

2015-11-29修改日期:2016-01-07