一種基于多維標度的分簇迭代無線傳感器網(wǎng)絡定位算法

林吉+李暉

摘要：本文提出了一種基于多維標度技術的分簇迭代定位算法LC-MDS。首先，在網(wǎng)絡中選取一個可定位簇，在簇內應用MDS技術，實現(xiàn)局部網(wǎng)絡中未知節(jié)點定位，然后將定位后的節(jié)點升級為偽錨節(jié)點，配合其他錨節(jié)點，進行迭代運算，直到網(wǎng)絡所有節(jié)點都成功定位。本文算法解決了因MDS距離矩陣過于龐大而導致的的計算繁瑣問題，定位精度優(yōu)于傳統(tǒng)算法MDS-MAP。

關鍵詞：多維標度；分簇迭代；無線傳感器網(wǎng)絡

中圖分類號：TN929.5 文獻標識碼：A 文章編號：1007-9416（2017）01-0125-02

在無線傳感器網(wǎng)絡中，傳感器節(jié)點多是被飛機、大炮等方式隨機拋灑至目標監(jiān)測區(qū)域，節(jié)點自組成網(wǎng)，除了少數(shù)配備GPS模塊的錨節(jié)點可獲取自身的地理位置信息外，其他節(jié)點的地理位置未知。然而，無論是實現(xiàn)環(huán)境監(jiān)測、目標跟蹤等應用，確定觸發(fā)事件消息的來源，即節(jié)點定位是無線傳感器網(wǎng)絡應用實現(xiàn)的基礎前提[1]。目前，以多維標度技術為核心的的定位算法MDS-MAP，僅利用節(jié)點的關聯(lián)信息和少量的錨節(jié)點位置信息，就可同時對多點定位，然而，MDS-MAP采用集中式其計算方法，計算復雜，通信代價高，能耗較大，本文針對問題提出改進算法LC-MDS。本文組織如下：第1節(jié)介紹相關研究工作，第2節(jié)詳細介紹LC-MDS算法，第3節(jié)進行仿真分析，并總結全文。

1 相關研究工作

1.1 經(jīng)典多維標度技術

多維標度（簡稱MDS）是一種將數(shù)據(jù)關系表示成幾何圖形加以研究的數(shù)據(jù)分析技術[2]，在無線傳感器網(wǎng)絡中，可利用它計算節(jié)點的相對坐標。MDS生成節(jié)點的相對坐標的具體實現(xiàn)方法如下：已知n個傳感器節(jié)點的坐標：X={x1，x2，..，xn}，和它們間n維對稱距離矩陣：D=[dij]n×n，1≤i≤n， 1≤j≤n。首先，計算距離平方相似度矩陣D（2）=[D2]，求矩陣D（2）的雙中心形式：H=-（1/2）JD（2）J，其中J=I-e*eT/n，e=（1）1×n，I=[1]n×n。然后，提取H的前k個特征值并從小到大排列成對角矩陣：Uk=diag（λ1，λ2，…，λk），對應的k個特征向量構成：Vk=[e1，e2，…，ek]，那么，H=UkVkUkT，H還可以表示成：H=XXT。最后，將關于H的這兩個表達式聯(lián)立計算，可得到這n個節(jié)點在k維空間的坐標解：Xk=VkLk1/2，其中Lk1/2為k個特征值構成的對角陣的開平方。

1.2 絕對坐標變換原理

使用多維技術計算出節(jié)點相對坐標后，要利用分布式定位方法把相對位置對齊到物理位置，對齊過程包括移動、旋轉和坐標反射，在二維情況中，至少需要三個位置已知的節(jié)點，這些傳感器節(jié)點可以是錨節(jié)點，也可以是通過計算獲知自身物理位置的節(jié)點，通過確定三個位置已知的節(jié)點從相對位置到物理位置的轉換規(guī)律[3]，可以將其他節(jié)點對齊到物理位置，如圖1所示：節(jié)點1、2、3、4、5為物理位置，其中1、2、3為錨節(jié)點。1、2、3、4、5為相對坐標位置，通過把1、2、3對其到物理位置1、2、3，節(jié)點4、5也可以對齊到物理位置。

2 LC-MDS算法

設一個二維無線傳感器網(wǎng)絡由m+n個節(jié)點構成，其中錨節(jié)點集合為A={ax}，x=1-->m，未知節(jié)點集合為U={uy}，y=1-->n，每個節(jié)點擁有唯一的ID，信號功率發(fā)射半徑為R，節(jié)點i通信范圍內的其他節(jié)點稱為節(jié)點i的鄰節(jié)點，記為集合Ni。

2.1 拓撲感知

通過節(jié)點間的信息交換可以實現(xiàn)節(jié)點對周圍的拓撲環(huán)境的感知，流程如下：

（1）源節(jié)點洪泛查詢分組。分組內容包括消息源節(jié)點序號S_ID，跳數(shù)值H，初始化為0，當前轉發(fā)節(jié)點F_ID，初始化為null。（2）鄰節(jié)點收到該分組，同時查詢本是否存在該分組，若不存在，保存該分組，并繼續(xù)轉發(fā)。若存在，將H+1，再與本地記錄的跳數(shù)值比較：大于，丟棄該分組；小于，替換本地記錄；等于，對比F_ID：若相同，丟棄該分組，若不同，保存該分組。（3）節(jié)點融合本地的已保存分組，提取路由節(jié)點的序號，跳數(shù)和個數(shù)信息，并將這些信息廣播。

2.2 分簇迭代

遍歷錨節(jié)點信息，尋找任意3個錨節(jié)點的共同鄰居節(jié)點ui，若存在，將ui及其鄰居節(jié)點作為簇成員，將這3個錨節(jié)點中具有最小ID的錨節(jié)點作為簇首；若不存，則尋找兩個錨節(jié)點的共同鄰居節(jié)點uj，再選取第三個錨節(jié)點使得它到這兩個錨節(jié)點的距離和最短，簇首和簇成員的選擇方法同上。簇首和簇成員構成局部網(wǎng)絡簇。分簇后，簇首利用MDS算法將簇內節(jié)點映射到相對位置，再根據(jù)簇內錨節(jié)點的已知物理坐標和映射規(guī)律，將未知節(jié)點對齊到物理位置。已定位的未知節(jié)點升級為偽錨節(jié)點，重復以上步驟，直到整個網(wǎng)絡節(jié)點都成功定位。

3 算法仿真與分析

定義定位誤差為：，在matlab仿真平臺下， 在100m×100m的方形區(qū)域里，隨機產(chǎn)生100個節(jié)點，其中錨節(jié)個數(shù)m=10，定位誤差曲線見圖2所示：定位精度隨著通信半徑的增大提高，后趨于穩(wěn)定，相比于MDS-MAP算法，對本文算法可將精度提高9%左右。計算復雜度由O（n3）下降到 kO（p3），其中k為網(wǎng)絡分簇的個數(shù)，p為平均簇內的節(jié)點個數(shù)，p遠小于n。

參考文獻

[1]彭宇，王丹.無線傳感器網(wǎng)絡定位技術綜述[J].電子測量與儀器學報，2011， 25（5）：389-399.

[2]王博.無線傳感器網(wǎng)絡基于多維標度定位算法的研究[D].沈陽：遼寧大學，2014.

[3]屈劍鋒，郭茂耘.一種基于錨節(jié)點分簇的傳感器網(wǎng)絡節(jié)點定位方法[J].計算機應用研究，2011（9）：3470-3473.