一種面向無線傳感器網絡的分布式定位算法

晁旭，申曉紅，白衛崗

（西北工業大學 航海學院，陜西 西安 710072）

隨著微機電系統技術、數字電子學和無線通信技術的進步，促進了廉價、多功能的網絡傳感器結點的快速發展，使得無線傳感器網絡（Wireless Sensor Network，WSN）能夠廣泛應用于軍事和民用領域[1-2]。而WSN中的大多數應用（如軍事目標監測、森林火災監控）都需要網絡中節點的地理位置信息，從而獲知信息來源的準確位置。此外，利用節點位置信息可以設計路由算法以提高路由效率等。所以，節點自定位問題已成為WSN的一個重要研究方向。

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

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

1 相關工作

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

MAP-Growing算法首先通過計算相對坐標下非線性關系的3個鄰居節點的位置從而建立初始局部坐標系，并向外廣播坐標信息；然后計算與此3點相鄰的節點坐標，如此反復計算其余相鄰節點的坐標直至所有節點被定位。該算法對拓撲結構適應性很強，節點定位覆蓋率高。該算法使用經過計算得到坐標的點協助定位會造成較大的誤差累積。

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

2 DARL算法

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

2.1 分簇階段

算法開始時，每個節點廣播其ID，節點通過鄰節點發來的信息計算鄰節點到自身的距離，收到信息的鄰節點將節點的距離信息和ID記錄下來，同時根據其他節點的廣播信息更新自身鄰節點列表。在所有節點發送一遍信息后，每個節點會獲知所有一跳鄰節點ID和距離。節點一跳鄰節點的數目即為該節點的連通度。

然后，節點廣播其連通度、鄰節點ID和距離。節點在獲得所有鄰節點連通度后，連通度最大的節點成為簇頭，其自身ID即為簇頭ID，并發布成簇信息，當度數相同時則選擇ID最小的節點作為簇頭。收到信息的節點記錄下簇頭ID，并成為該節點的從節點。

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

2.2 局部坐標系的建立

當分簇完成完成以后，則要計算簇內節點相對坐標。本定位算法采用經典度量MDS[6]技術。由簇頭負責收集節點間距離信息，以自身為原點計算包含所有簇成員坐標的局部坐標系。

算法簡要描述如下：

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

2）使用各節點間距離矩陣[Dij]構建相異性矩陣[Pij]，即[Dij]=[Pij]；

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

①計算距離矩陣的平方矩陣D2；

②計算矩陣J=I-e·eT/n，其中I為單位矩陣，n為節點數量，e=[1，1，…1]T

④奇異值分解：H=UVUT：

對于第5步，由于生成的是二維坐標，所以取矩陣U的前2列構成矩陣U2，選取大于零的前2個特征值構成V2，即可得到各節點相對位置的坐標矩陣。

為了進行坐標系合并，對得到的坐標矩陣進行平移，將簇頭的坐標化為（0，0）。

4）簇頭廣播各節點的坐標。

2.3 全局坐標系的建立

當網內各簇均建立局部相對坐標系后，公共邊界節點發布自身所在簇的所有ID信息。當相鄰簇之間有兩個或兩個以上公共邊界節點時，便開始合并，合并方向為ID較大的簇向ID較小的簇合并。重復這個過程，直至所有簇都合完成。

簇間坐標轉換示意圖如圖1所示。簇間坐標轉換要求簇間至少有兩個以上的公共邊界點，i、k為簇頭原點，j、l為兩簇的公共邊界點，實線表示兩節點間可以進行測距即距離已知，虛線表示兩節點間不能進行測距即距離未知。可通過四邊形計算公式得出i、k之間的距離[4]。

圖1 簇間坐標轉換示意圖Fig.1 Coordinate transformation diagram between clusters

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

令 θ=θ1+θ2，dik由下式計算：

通過計算，可得出節點k在i簇坐標系中的相對坐標以及以i為原點的坐標系中的向量。對于k中任意從節點m，坐標轉換可以通過計算向量獲得m點在以i為原點的坐標系中的坐標。依此即可將k所在簇的節點坐標轉化為i節點所在簇的節點坐標，從而實現簇間的坐標變換，建立全局相對坐標系。

2.4 算法估計精度分析

1）map-growing算法使用遞進式的坐標計算方式，使得測距誤差不斷的累積，而本算法利用分簇思想，將網絡分成大大小小的幾個簇，可以降低測距誤差的累積；

2）SDGPSN算法在簇內坐標計算使用的是三邊定位法，本算法使用MDS定位方法可以改善定位精度。

3 仿真實驗與結果分析

本實驗采用MATLAB對文中提出的定位算法進行了仿真計算。仿真環境為一定面積內的矩形場景，并隨機分布一定數量的網絡節點，以節點間的距離作為節點實際距離，然后再在節點實際距離上加入均值為0、方差為σ2的隨機高斯噪聲e（作為測量誤差）作為節點間的測量距離參數。

文中假設網絡節點分簇已經完成。首先，在長寬各為150 m的矩形區域內隨機分別布放一定數量的20～100個節點，令節點有效通信距離r=100，噪聲方差σ2為1時，分別對DARL和SDGPSN方法各進行50次的仿真實驗，并進行定位誤差平均統計，實驗結果如圖2所示。然后，在長寬各為100 m的矩形區域內隨機分布60個節點，通信距離r=80，噪聲方差σ2按步長0.5取1～3，分別對兩種方法進行50次仿真實驗，實驗結果如圖3所示。

圖2 定位誤差與節點數量關系圖Fig.2 Relationship chart between positioning error and the number of node

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

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

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

4 結 論

文中主要以水下應用為背景，提出了一種分布式無信標節點的相對定位算法。通過實驗仿真計算，驗證了該定位算法的合理性，同時與同類算法相比提高了定位精度，為水下事件位置報告、目標跟蹤、地理路由等應用提供了有力的技術支持。

[1]孫殿東，朱悅.無線傳感器網絡及應用研究[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]關亮，張開龍，李同松.無線傳感器網絡（WSN）定位系統設計[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網絡技術[M].北京：人民郵電出版社，2005.