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

李津蓉，王萬(wàn)良，介　婧，姚信威

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

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

李津蓉1，2，王萬(wàn)良1*，介婧2，姚信威1

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

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

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

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

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

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

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

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

1　MDS-MAP（MLE）算法

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

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

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

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

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

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

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

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

2　實(shí)驗(yàn)研究及性能分析

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

2.1算法流程示例

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

圖1　示例網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及一跳鄰居子網(wǎng)

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

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

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

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

2.2性能分析及比較

為了進(jìn)一步分析MDS-MAP（MLE）算法的性能，將其與經(jīng)典MDS-MAP算法分別在規(guī)則網(wǎng)絡(luò)和不規(guī)則網(wǎng)絡(luò)連接環(huán)境下進(jìn)行比較。算法性能通過(guò)待測(cè)節(jié)點(diǎn)定位的最大誤差、最小誤差、平均誤差和運(yùn)行時(shí)間進(jìn)行評(píng)估。在1 000 m×1 000 m的方形區(qū)域內(nèi)隨機(jī)部署200個(gè)節(jié)點(diǎn)，其中20個(gè)錨節(jié)點(diǎn)，節(jié)點(diǎn)通信半徑為200 m，測(cè)距誤差為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é)點(diǎn)間的路徑距離與歐式距離的偏差較大，導(dǎo)致MDSMAP算法的定位結(jié)果非常不準(zhǔn)確，而MDS-MAP （MLE）算法成功避免了這一問(wèn)題，定位效果較好。兩種算法的性能指標(biāo)如表1所示。

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

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

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

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

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

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

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

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

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

3　結(jié)論

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

［1］ 于海斌，梁煒，曾鵬.智能無(wú)線傳感器網(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)化的多維標(biāo)度節(jié)點(diǎn)定位算法［J］.傳感技術(shù)學(xué)報(bào)，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é)報(bào)，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ú)線傳感器網(wǎng)絡(luò)定位算法［J］.電子科技大學(xué)學(xué)報(bào)，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］劉健苗，許新忠，黃書(shū)廣，等.改進(jìn)的分布式無(wú)線傳感器網(wǎng)絡(luò)多維標(biāo)度定位算法［J］.傳感技術(shù)學(xué)報(bào)，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極大似然估計(jì)定位算法的分析與實(shí)現(xiàn)［J］.吉林大學(xué)學(xué)報(bào)（理學(xué)版），2014，52（3）:557-660.

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

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

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

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

項(xiàng)目來(lái)源:國(guó)家自然科學(xué)基金項(xiàng)目（61379123）；國(guó)家自然科學(xué)基金項(xiàng)目（61402414）；浙江省自然科學(xué)基金項(xiàng)目（LQ14F050002）

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