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

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

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

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

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

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

無線傳感網(wǎng)絡(luò)；定位算法；多維定標；極大似然方法

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

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

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

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

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

1　MDS-MAP（MLE）算法

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

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

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

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

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

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

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

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

2　實驗研究及性能分析

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

2.1算法流程示例

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

圖1　示例網(wǎng)絡(luò)拓撲結(jié)構(gòu)及一跳鄰居子網(wǎng)

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

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

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

圖3　MDS-MAP（MLE）算法的定位結(jié)果

2.2性能分析及比較

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

圖4　網(wǎng)絡(luò)連接圖

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

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

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

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

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

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

圖7　兩種算法在不同網(wǎng)絡(luò)連通度下的定位誤差比較

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

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

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

3　結(jié)論

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

［1］ 于海斌，梁煒，曾鵬.智能無線傳感器網(wǎng)絡(luò)系統(tǒng)［M］.第2版.北京:科學(xué)出版社，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］.傳感技術(shù)學(xué)報，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］.軟件學(xué)報，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］ 王勇，胡良梁，袁巢燕.基于密度分簇的無線傳感器網(wǎng)絡(luò)定位算法［J］.電子科技大學(xué)學(xué)報，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］劉健苗，許新忠，黃書廣，等.改進的分布式無線傳感器網(wǎng)絡(luò)多維標度定位算法［J］.傳感技術(shù)學(xué)報，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］.吉林大學(xué)學(xué)報（理學(xué)版），2014，52（3）:557-660.

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

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

介婧（1972-），女，博士（博士后），教授?，F(xiàn)為浙江科技學(xué)院自動化與電氣工程學(xué)院教師。主要研究方向包括智能控制、調(diào)度優(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

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

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