一種面向無線傳感器網(wǎng)絡(luò)的分布式定位算法

晁旭，申曉紅，白衛(wèi)崗

（西北工業(yè)大學(xué) 航海學(xué)院，陜西 西安 710072）

隨著微機(jī)電系統(tǒng)技術(shù)、數(shù)字電子學(xué)和無線通信技術(shù)的進(jìn)步，促進(jìn)了廉價(jià)、多功能的網(wǎng)絡(luò)傳感器結(jié)點(diǎn)的快速發(fā)展，使得無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）能夠廣泛應(yīng)用于軍事和民用領(lǐng)域[1-2]。而WSN中的大多數(shù)應(yīng)用（如軍事目標(biāo)監(jiān)測、森林火災(zāi)監(jiān)控）都需要網(wǎng)絡(luò)中節(jié)點(diǎn)的地理位置信息，從而獲知信息來源的準(zhǔn)確位置。此外，利用節(jié)點(diǎn)位置信息可以設(shè)計(jì)路由算法以提高路由效率等。所以，節(jié)點(diǎn)自定位問題已成為WSN的一個(gè)重要研究方向。

目前已經(jīng)提出了很多節(jié)點(diǎn)自定位算法，而由于水下環(huán)境的特殊性，陸上無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位算法在水下受到了一定的使用限制。在水下環(huán)境中，電磁波和光波衰減嚴(yán)重，節(jié)點(diǎn)需采用聲波進(jìn)行通信，節(jié)點(diǎn)無法通過接收GPS信號來獲取精確的地理位置信息，從而無法生成整體絕對坐標(biāo)系。為了滿足水下無線傳感器網(wǎng)絡(luò)在軍事應(yīng)用等對節(jié)點(diǎn)定位的高精度的要求，筆者提出一種分布式無信標(biāo)節(jié)點(diǎn)的相對定位算法。

該算法適用于節(jié)點(diǎn)布放在水下環(huán)境中的WSN，節(jié)點(diǎn)無法生成絕對坐標(biāo)。首先，節(jié)點(diǎn)間通過 TOA（Time of Arrival）[3]測距技術(shù)獲取節(jié)點(diǎn)間的相對距離信息；然后網(wǎng)絡(luò)節(jié)點(diǎn)利用最高節(jié)點(diǎn)度分簇算法[7]分簇，并分別在簇內(nèi)計(jì)算節(jié)點(diǎn)局部坐標(biāo)；最后，各簇間進(jìn)行合并以統(tǒng)一坐標(biāo)，形成整體相對坐標(biāo)系統(tǒng)。為了提高定位精度，該算法采用經(jīng)典度量多維尺度分析技術(shù)計(jì)算簇內(nèi)相對坐標(biāo)，有效地減少了由于測量距離誤差所帶來的坐標(biāo)估計(jì)誤差。通過實(shí)驗(yàn)仿真表明，與同類算法相比，該定位算法提高了約10%的節(jié)點(diǎn)自定位精度。

1 相關(guān)工作

當(dāng)前典型相對定位算法有MAP-Growing[4]和SDGPSN[5]等。

MAP-Growing算法首先通過計(jì)算相對坐標(biāo)下非線性關(guān)系的3個(gè)鄰居節(jié)點(diǎn)的位置從而建立初始局部坐標(biāo)系，并向外廣播坐標(biāo)信息；然后計(jì)算與此3點(diǎn)相鄰的節(jié)點(diǎn)坐標(biāo)，如此反復(fù)計(jì)算其余相鄰節(jié)點(diǎn)的坐標(biāo)直至所有節(jié)點(diǎn)被定位。該算法對拓?fù)浣Y(jié)構(gòu)適應(yīng)性很強(qiáng)，節(jié)點(diǎn)定位覆蓋率高。該算法使用經(jīng)過計(jì)算得到坐標(biāo)的點(diǎn)協(xié)助定位會造成較大的誤差累積。

SDGPSN算法分3步：首先，每個(gè)節(jié)點(diǎn)運(yùn)行一個(gè)隨機(jī)的定時(shí)器，時(shí)間一到，未收到鄰居節(jié)點(diǎn)消息的節(jié)點(diǎn)自舉為簇頭并發(fā)布簇頭消息，收到的節(jié)點(diǎn)為簇成員；其次，簇頭以自身為坐標(biāo)原點(diǎn)建立局部坐標(biāo)系；最后，相鄰簇通過邊界節(jié)點(diǎn)合并成全局坐標(biāo)系。該算法在分簇階段，簇個(gè)數(shù)過多，使后期存在較大的通信量和計(jì)算量；在簇內(nèi)坐標(biāo)計(jì)算階段，使用三邊定位方法的定位誤差較大。

2 DARL算法

筆者提出一種分布式無信標(biāo)節(jié)點(diǎn)的相對定位算法（DARL）。算法假設(shè)：1）節(jié)點(diǎn)間距離通過TOA技術(shù)測得，該方法要求各節(jié)點(diǎn)間時(shí)鐘同步，通過計(jì)算聲波傳播的時(shí)間來估計(jì)距離；2）節(jié)點(diǎn)隨機(jī)分布在一個(gè)二維平面內(nèi)，各節(jié)點(diǎn)結(jié)構(gòu)相同，通信半徑R相等，單跳通信；3）節(jié)點(diǎn)ID唯一，最小的為 0，用于全局坐標(biāo)生成階段。算法分為3個(gè)階段：分簇階段，局部坐標(biāo)系建立階段和全局坐標(biāo)系建立階段。

2.1 分簇階段

算法開始時(shí)，每個(gè)節(jié)點(diǎn)廣播其ID，節(jié)點(diǎn)通過鄰節(jié)點(diǎn)發(fā)來的信息計(jì)算鄰節(jié)點(diǎn)到自身的距離，收到信息的鄰節(jié)點(diǎn)將節(jié)點(diǎn)的距離信息和ID記錄下來，同時(shí)根據(jù)其他節(jié)點(diǎn)的廣播信息更新自身鄰節(jié)點(diǎn)列表。在所有節(jié)點(diǎn)發(fā)送一遍信息后，每個(gè)節(jié)點(diǎn)會獲知所有一跳鄰節(jié)點(diǎn)ID和距離。節(jié)點(diǎn)一跳鄰節(jié)點(diǎn)的數(shù)目即為該節(jié)點(diǎn)的連通度。

然后，節(jié)點(diǎn)廣播其連通度、鄰節(jié)點(diǎn)ID和距離。節(jié)點(diǎn)在獲得所有鄰節(jié)點(diǎn)連通度后，連通度最大的節(jié)點(diǎn)成為簇頭，其自身ID即為簇頭ID，并發(fā)布成簇信息，當(dāng)度數(shù)相同時(shí)則選擇ID最小的節(jié)點(diǎn)作為簇頭。收到信息的節(jié)點(diǎn)記錄下簇頭ID，并成為該節(jié)點(diǎn)的從節(jié)點(diǎn)。

由于在最后簇的合并階段，需要簇和簇之間有至少兩個(gè)公共邊界節(jié)點(diǎn)，因此需要對分簇進(jìn)行優(yōu)化。初次分簇完成以后，公共邊界節(jié)點(diǎn)向簇頭廣播消息，如果相鄰簇之間只有一個(gè)公共節(jié)點(diǎn)，則以這個(gè)公共節(jié)點(diǎn)為簇頭，其一跳鄰節(jié)點(diǎn)為從節(jié)點(diǎn)。

2.2 局部坐標(biāo)系的建立

當(dāng)分簇完成完成以后，則要計(jì)算簇內(nèi)節(jié)點(diǎn)相對坐標(biāo)。本定位算法采用經(jīng)典度量MDS[6]技術(shù)。由簇頭負(fù)責(zé)收集節(jié)點(diǎn)間距離信息，以自身為原點(diǎn)計(jì)算包含所有簇成員坐標(biāo)的局部坐標(biāo)系。

算法簡要描述如下：

1）簇頭收集各從節(jié)點(diǎn)間距信息，包括從節(jié)點(diǎn)間的直測距離，如果從節(jié)點(diǎn)之間距離不可直接獲得，則使用最短路徑法求出節(jié)點(diǎn)之間距離，構(gòu)成距離矩陣[Dij]；

2）使用各節(jié)點(diǎn)間距離矩陣[Dij]構(gòu)建相異性矩陣[Pij]，即[Dij]=[Pij]；

3）對距離矩陣[Dij]使用經(jīng)典MDS算法。其過程分以下5個(gè)步驟：

①計(jì)算距離矩陣的平方矩陣D2；

②計(jì)算矩陣J=I-e·eT/n，其中I為單位矩陣，n為節(jié)點(diǎn)數(shù)量，e=[1，1，…1]T

④奇異值分解：H=UVUT：

對于第5步，由于生成的是二維坐標(biāo)，所以取矩陣U的前2列構(gòu)成矩陣U2，選取大于零的前2個(gè)特征值構(gòu)成V2，即可得到各節(jié)點(diǎn)相對位置的坐標(biāo)矩陣。

為了進(jìn)行坐標(biāo)系合并，對得到的坐標(biāo)矩陣進(jìn)行平移，將簇頭的坐標(biāo)化為（0，0）。

4）簇頭廣播各節(jié)點(diǎn)的坐標(biāo)。

2.3 全局坐標(biāo)系的建立

當(dāng)網(wǎng)內(nèi)各簇均建立局部相對坐標(biāo)系后，公共邊界節(jié)點(diǎn)發(fā)布自身所在簇的所有ID信息。當(dāng)相鄰簇之間有兩個(gè)或兩個(gè)以上公共邊界節(jié)點(diǎn)時(shí)，便開始合并，合并方向?yàn)镮D較大的簇向ID較小的簇合并。重復(fù)這個(gè)過程，直至所有簇都合完成。

簇間坐標(biāo)轉(zhuǎn)換示意圖如圖1所示。簇間坐標(biāo)轉(zhuǎn)換要求簇間至少有兩個(gè)以上的公共邊界點(diǎn)，i、k為簇頭原點(diǎn)，j、l為兩簇的公共邊界點(diǎn)，實(shí)線表示兩節(jié)點(diǎn)間可以進(jìn)行測距即距離已知，虛線表示兩節(jié)點(diǎn)間不能進(jìn)行測距即距離未知?？赏ㄟ^四邊形計(jì)算公式得出i、k之間的距離[4]。

圖1 簇間坐標(biāo)轉(zhuǎn)換示意圖Fig.1 Coordinate transformation diagram between clusters

此處假設(shè) k 向 i轉(zhuǎn)換，在三角形 Δ（i，j，l）和 Δ（k，j，l）中，θ1，θ2，可以由下式得出：

令 θ=θ1+θ2，dik由下式計(jì)算：

通過計(jì)算，可得出節(jié)點(diǎn)k在i簇坐標(biāo)系中的相對坐標(biāo)以及以i為原點(diǎn)的坐標(biāo)系中的向量。對于k中任意從節(jié)點(diǎn)m，坐標(biāo)轉(zhuǎn)換可以通過計(jì)算向量獲得m點(diǎn)在以i為原點(diǎn)的坐標(biāo)系中的坐標(biāo)。依此即可將k所在簇的節(jié)點(diǎn)坐標(biāo)轉(zhuǎn)化為i節(jié)點(diǎn)所在簇的節(jié)點(diǎn)坐標(biāo)，從而實(shí)現(xiàn)簇間的坐標(biāo)變換，建立全局相對坐標(biāo)系。

2.4 算法估計(jì)精度分析

1）map-growing算法使用遞進(jìn)式的坐標(biāo)計(jì)算方式，使得測距誤差不斷的累積，而本算法利用分簇思想，將網(wǎng)絡(luò)分成大大小小的幾個(gè)簇，可以降低測距誤差的累積；

2）SDGPSN算法在簇內(nèi)坐標(biāo)計(jì)算使用的是三邊定位法，本算法使用MDS定位方法可以改善定位精度。

3 仿真實(shí)驗(yàn)與結(jié)果分析

本實(shí)驗(yàn)采用MATLAB對文中提出的定位算法進(jìn)行了仿真計(jì)算。仿真環(huán)境為一定面積內(nèi)的矩形場景，并隨機(jī)分布一定數(shù)量的網(wǎng)絡(luò)節(jié)點(diǎn)，以節(jié)點(diǎn)間的距離作為節(jié)點(diǎn)實(shí)際距離，然后再在節(jié)點(diǎn)實(shí)際距離上加入均值為0、方差為σ2的隨機(jī)高斯噪聲e（作為測量誤差）作為節(jié)點(diǎn)間的測量距離參數(shù)。

文中假設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)分簇已經(jīng)完成。首先，在長寬各為150 m的矩形區(qū)域內(nèi)隨機(jī)分別布放一定數(shù)量的20～100個(gè)節(jié)點(diǎn)，令節(jié)點(diǎn)有效通信距離r=100，噪聲方差σ2為1時(shí)，分別對DARL和SDGPSN方法各進(jìn)行50次的仿真實(shí)驗(yàn)，并進(jìn)行定位誤差平均統(tǒng)計(jì)，實(shí)驗(yàn)結(jié)果如圖2所示。然后，在長寬各為100 m的矩形區(qū)域內(nèi)隨機(jī)分布60個(gè)節(jié)點(diǎn)，通信距離r=80，噪聲方差σ2按步長0.5取1～3，分別對兩種方法進(jìn)行50次仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖3所示。

圖2 定位誤差與節(jié)點(diǎn)數(shù)量關(guān)系圖Fig.2 Relationship chart between positioning error and the number of node

圖3 定位誤差與噪聲方差關(guān)系圖Fig.3 Relationship chart between positioning error and noise variance

從圖2中可以看出，文中算法的定位精度比SDGPSN算法有顯著提高，并且沒有因?yàn)楣?jié)點(diǎn)增多而導(dǎo)致誤差的累積。主要原因是SDGPSN算法在局部坐標(biāo)生成階段只使用了三邊定位法，沒有使節(jié)點(diǎn)間的測距誤差得到控制。而本算法使用經(jīng)典度量MDS技術(shù)計(jì)算局部坐標(biāo)，該技術(shù)能有效地利用多余的節(jié)點(diǎn)間距信息來減少計(jì)算誤差，并且分簇后，簇內(nèi)節(jié)點(diǎn)之間最多有兩跳通信距離，降低了最短路徑誤差，進(jìn)一步降低了MDS技術(shù)的方法誤差。

從圖3中可以看出，節(jié)點(diǎn)數(shù)量一定時(shí)，隨著噪聲的增大，兩種方法的定位誤差都有所增大，但是相比SDGPSN算法，本算法的誤差增幅較小，這說明測距誤差對本算法的影響較小，算法穩(wěn)定性好。

4 結(jié) 論

文中主要以水下應(yīng)用為背景，提出了一種分布式無信標(biāo)節(jié)點(diǎn)的相對定位算法。通過實(shí)驗(yàn)仿真計(jì)算，驗(yàn)證了該定位算法的合理性，同時(shí)與同類算法相比提高了定位精度，為水下事件位置報(bào)告、目標(biāo)跟蹤、地理路由等應(yīng)用提供了有力的技術(shù)支持。

[1]孫殿東，朱悅.無線傳感器網(wǎng)絡(luò)及應(yīng)用研究[J].電子設(shè)計(jì)工程，2010，18（5）：90-91.

SUN Dian-dong，ZHU Yue.Research of wireless sensor networks and its applications [J].Electronic Design Engineering，2010，18（5）：90-91.

[2]關(guān)亮，張開龍，李同松.無線傳感器網(wǎng)絡(luò)（WSN）定位系統(tǒng)設(shè)計(jì)[J].電子設(shè)計(jì)工程，2010，18（5）：84-86.

GUAN Liang，ZHANG Kai-long，LI Tong-song.Design of WSN location system[J].Electronic Design Engineering，2010，18（5）：84-86.

[3]Girod L，Estrin D.Robust range estimation using acoustic and multimodal sensing[C]//Proc IEEE/RSJ Int’l Conf Intelligent Robots and Systems（IROS’01），2001（3）：1312-1320.

[4]LI Xiao-li，SHI Hong-chi，Yi Shang.A MAP-growing localization algorithm for Ad hoc wireless sensor networks[C]//Proc.of the 10th ICPADS.Newport Beach，USA：[s.n.]，2004.

[5]Iyengar.R，Sikdar.B Scalable and distributed GPS-free positioning for sensor networks[C]//Proceedings of IEEE International Conference on Communications.An-chorage：IEEE Press，2003（1）：338-342.

[6]Shang Y，Ruml W.Localization from mere connectivity[C]//Proceedings of the 4th ACM International Symposium on Mobile Ad-hoc Networking and Computing.Annapolis， 2003：201-212.

[7]鄭少仁，王海濤，趙志峰，等.Ad Hoc網(wǎng)絡(luò)技術(shù)[M].北京：人民郵電出版社，2005.