WSN 中角度和距離結合的無信標節點定位算法的設計?

張 拓，蔣 健，姚海峰，錢升港，毛科技，何文秀，趙永標?

(1.浙江工業大學計算機科學與技術學院，浙江 杭州 310023；2.浙江省信息安全標準化技術委員會，浙江 杭州 310000；3.紹興市越城區消防救援大隊，浙江 紹興 312000；4.浙江工業大學之江學院，浙江 紹興 312030)

無線傳感器網絡(Wireless Sensor Networks，WSN)中節點的部署通常隨機性較強且數量龐大，較難實現精準的節點定位[1]。然而在現實應用場景下，節點感知到的數據若缺失了位置信息，其利用價值會大幅降低。只有明確節點所在位置，才能將感知數據與位置信息關聯，實現高效的感知[2]。因此，節點定位是無線傳感網絡的重要的支撐技術之一。由于節點所在位置的隨機性以及其位置信息的重要性，實現節點的精準定位是無線傳感器網絡部署落地的關鍵。例如實際應用中節點需要通過飛行設備直接拋散在特定區域，其位置分布隨機性較強且無法預先獲取[3－4]。又如當節點部署的區域危險性較大，人類無法進入，或是敵對區域[5－6]。此外，在許多應用中，位置信息對傳感器的監測工作非常重要，如火災、地質勘測等等。因此，在現實場景中獲取節點位置信息實現定位對WSN 具有重要意義[7－8]。

WSN 的定位方式可以分為有信標節點的定位方式和無信標節點的定位方式[9－10]。有信標節點的定位方式，即在WSN 中必須存在有一些節點通過某種方式，已經知道其具體坐標，例如利用全球定位系統。利用已知實際坐標位置的節點，其他節點就可以根據這些已知信標節點，進而估算出其他節點的坐標。無信標節點的定位方式，所得到的坐標系統可能僅為一相對于該WSN 之間的相對坐標系的位置與方位，然而這樣的相對位置信息，足以吻合對象監測、同步、乃至信號傳遞等無線傳感器的應用項目上，進一步，如果能夠在這樣的網絡環境中獲取到3組以上的真實坐標系中的位置信息，可輕易將該網絡定位系統轉換為實體坐標系統。

無信標節點的定位方式，在近幾年逐漸受到重視，正如前所述，雖然由此算法所估測出的節點坐標并非處于絕對坐標系統之上，然而透過某些已知絕對位置的節點坐標，即可輕易將其轉換為絕對坐標系統，即可大幅度提升在應用上的彈性。在以往所提出的有關于此類算法中，大多是以測量距離的方式，以進行定位的動作。雖然量測距離的裝置成本較為低廉，然而由于量測裝置本身的先天性因素，距離量測一般具有較大的測量誤差，因此將影響到最后的定位結果。

因此，本文提出一種結合角度和距離測量的方法，在無需額外的信標節點存在之下，利用分布式定位方式，以逐步逼近式的方式來實現節點定位，同時對于同步中的節點進行比例式的調整，如此可縮小最后的定位誤差范圍，避免因少部分可能出現的較大測量誤差而影響到整體的定位結果。實驗結果表明，該方式在估算坐標誤差上，可大幅優于其他同類型之不使用信標節點作為參考的定位方式。

1 相關研究

近幾年以來陸續有人提出數種無信標節點定位算法，例如文獻[11]提出的節點分布式定位算法，通過特定算法選取了5 個基準節點作為信標構建了一個新的坐標系，在新的坐標系中定位其他未知節點，在較低成本情況下實現了大規模的節點定位。文獻[12]提出了一種虛擬信標節點定位算法，在普通節點中選取5 個虛擬信標構建坐標系，利用三邊測量法進一步確定未知節點位置。文獻[13]在聚類基礎上提出一種無信標節點定位算法，該方法通過創建聚類，將節點的能量、連接程度以及三角不等式的幾何極限定理這三個要素進行融合，減小了無信標定位中經常出現的累計誤差，在能耗與定位精度上取得了較好的平衡。

文獻[14]的定位方式是將所有的節點都利用監測其與周圍節點的位置關系，分別建立出屬于該節點的坐標系統。之后再結合每一個節點之坐標系統，逐步將所有節點的坐標系統合并，以建構一個總體之坐標系。還有很多相關的研究成果如文獻[15－18]等。總的來講，在以往所提出的有關于此類之算法中，大多是以測量距離的方式，以進行定位的動作。雖然測量距離的裝置成本較為低廉，然而由于測量裝置本身的先天性因素，距離測量一般具有較大的誤差，因此影響到最后的定位精度。

2 算法設計

2.1 基本思想

本文提出一種結合角度以及距離量測的方式，在無信標節點存在之環境下，對無線傳感器網絡進行定位的算法。該定位方式可以將之區分為兩個階段:

第一個階段在所需定位的WSN 中，確定某一些節點作為信標節點，并利用樹的生成方式，分別以這些信標節點以作為樹的起點，各自向周邊延伸使節點之間以樹狀形態相互連結。

第二個階段樹的合并階段，將所生成的樹進行合并，以生成一個統一的樹結構，在樹的合并過程中，以樹的高度為基礎，當節點監測到其他非屬于和自身同一樹中的其他節點之時，則該兩個節點在取得溝通之后，會根據所設定的加權值，決定兩個節點之間的合并方向，直到所有的樹都合并。

在角度同步當中，首先統一所有節點的坐標軸方位，然后利用坐標軸方位，以進行距離同步作業，最后決定節點之間的相對應位置。由于同時利用方位與距離檢測，在節點定位時僅需檢測到一個已知坐標節點，即可完成定位，有效增加可被定位節點比率，比聚類SPA 算法的定位精度要高。

2.2 算法實現

在進行算法同步作業前，首先將對節點進行樹的形式建構，主要是增加同步的效率，使所有同步作業能夠確保同步的效率，避免有繞遠路徑同步的情形產生。具體步驟如下:

2.2.1 信標節點的選擇

待定位的WSN 系統中，為了要將節點之間以多個樹狀結構進行連結，首先選定數個節點作為信標節點，作為所生成樹的樹根節點。選擇方式為監測網絡中所有的節點，若該節點相對于周圍的鄰居節點，擁有較高的連結度，即將該節點選定為信標節點，如圖1 所示。

圖1 選定節點A 為信標節點

2.2.2 樹的構建

選定了信標節點后，將以這些信標節點作為樹的根節點，各自向外將其他的節點納入，連結形成一棵樹。樹的產生方式由每個信標節點各自生成，當一個節點被納入某一棵樹中并成為其中的一個節點時，即成為該樹的一部分，并以此節點繼續擴展連結其他未被該樹合并的節點，此樹的擴展動作一直持續到沒有其他的未被連結的節點存在于此樹任何節點的監測范圍。由于每棵樹未必同時生成，因此最后所產生的每棵樹的大小、節點數量未必一致，每棵樹之間無需溝通協調，可節省能耗。

2.2.3 樹的合并

若有一個節點中存在于多棵樹的通訊范圍以內，稱該節點為“邊界節點”，當兩棵樹要進行合并時，利用這些邊界節點進行互相溝通。一棵樹的合并擴展停止后，開始對其他樹進行合并，每個邊界節點，都試圖去搜尋其他邊界節點，當其搜尋到其他邊界節點且又不屬于同一樹時，這兩個節點會進行同步的準備動作，令此兩節點分別為A與B。此兩節點會根據其在該樹中的高度值，以及其被該樹合并至今所經歷過的時間，演算出加權值，如式(1)所示:

式中:L(A)為節點A位于該樹中的高度值，tNow與tA分別為合并請求的發生時間以及節點A初始生成的時間，α為預先估測之系數。W(A)為A節點此時所計算出之權重，加權值可模擬該樹生成所經過的時間。兩個節點之間會根據此加權值的大小以決定合并的方向，加權值較小的節點將會被加權值較大的節點合并后成為其子節點，同時也將脫離原先所隸屬之樹而加入較大加權值之樹中。

2.2.4 方位的同步

假設在WSN 開始部署時，每個節點預先載入一個坐標軸系統，這樣每個節點都擁有一個自識別的正北方向，該正北方向與實際之坐標系統存在有一偏差夾角，稱之為“航位方向”。方位同步的目的，是采用漸進式逐步調整的方式，逐漸逼近所有節點之間的坐標軸方位，最終所有的節點都有一個統一的坐標系統與方位。然后該網絡中任何節點取得了實際環境之坐標軸方位，即可調整航位方向，輕易地將坐標軸歸正為實際坐標軸方位。

在方位同步的操作中，由每一個被推舉出來的信標節點為起點，發起方位同步操作。若某一信標節點A擁有一子節點B，則該信標節點即可利用角度監測的方式，檢測出子節點B其相對于該自身坐標的角度。同時，子節點B也得同時測量其與父節點A之間的相對角度。

如圖2 所示，若存在有某一節點A為信標節點，節點A有一子節點B。若節點A監測到與節點B之相對方向角為θAB，而節點B監測得節點A之相對方向角為θBA，則父節點A的調整方式為式(2):

圖2 節點A 與節點B 進行位置同步

式中:NA為節點A在進行方位調整前的方向角度，而－NA為同步時節點B調整的逆時針角度，θAB與θBA之范圍為0～2π，分別為節點A所監測節點B相對于其所存在的方位角度以及節點B所監測出之節點A相對它的方位角度，其分別有一個可能的角度量測誤差，分別為εAB與εBA，故經由節點所實際測量出來的角度量分別為εABθAB以及εBAθBA。SAB為該父節點同步操作下的調整比例，其值之設定為:

為節點A所擁有的子節點數量。同理，子節點B的調整方式為式(3):

此處的SBA＝1－SAB，其中，NB為方位調整前節點A的方向角度，而N′B－NB即為節點B在本次同步操作時所需調整的逆時針角度量，SBA為該子節點于此次同步操作下的調整比例，其值設定為:SBA＝1/(k×mi)，mi為父節點A所擁有的子節點數量，而k則為一常數值。

按這種方式，即可將節點A與B的方位角調整為圖3 所示，在節點A獲得定位結果之后，可繼續向其子節點(如節點B)，進行同步操作，方向同步的操作是連續的，即同步動作會一直持續，直到定位完成為止。

圖3 節點A 與節點B 角同步

2.2.5 距離同步

在父節點A監測其某一子節點B之相對之存在方位之后，則該兩個節點之間即可進行距離同步的測量與定位工作。距離同步無需和角度同步測量同時進行，即當節點A得知節點B之相對存在角度后，可將該相對方位信息儲存于該節點內的數據結構中，然后可協助進行距離同步時協助節點進行定位。

距離調整比例設定:在距離的調整定位上，也采用同步的概念，漸進式地調整所有節點的相對坐標位置，假設有一父節點A以及其子節點B存在于某一樹狀結構當中，令A:(xA，yA)、B:(xB，yB)為該兩節點在實際環境中坐標，而A′:(xA1，yA1)、B′:(xB1，yB1)則分別為該兩節點的坐標，則在父節點A當中，定義:fA，B＝vA，B(dA，B－rA，B)，其中:vA，B為父節點A于先前處理方位同步時所測量出相對于節點B所形成的方向單位向量，為先前經由角度測量暫存在節點A中，dA，B為節點A與節點B之間的距離，根據兩個節點個別的認知坐標所求出的距離值，故該值與實際該兩個節點之間存在測量誤差，即:dist(A，B)＋ε，其中ε為節點A測量其與子節點B之間的測量距離誤差，rA，B為節點A所監測到之兩點間之距離亦即為:dist(A，B)。

若節點A同時擁有數個子節點{B｜B∈child nodes ofA}，則父節點A利用上述方式，據以求出F＝∑(fA，B)。此F值即為該父節點相對于其各子節點之測量位置與原先估測距離的差距，由于考慮到避免一次完全的移動可能造成節點位置調整過于劇烈，因此以漸進式調整的方式，逐步調整節點的坐標位置。調整系數值k，配合該節點所擁有的子節點數mA，且令x′、y′ 分別為節點A原來自己的X軸與Y軸坐標，即得:

則:fAB＝(x″－x′，y″－y′)

則對于所有的子節點B:{B｜B∈child nodes ofA}，可以得到Total Force:F＝∑(fA，B)，根據此F向量值，可得出該次同步作業后節點A的坐標位置:

其中角度?為F相對于WSN 由角度同步所形成坐標系統的方向角，mA為節點A所連結的子節點個數。則最后更新后的節點A坐標A′:(x?，y?)。而對于所有的子節點B，可以由其與父節點之同步過程當中所得:

式中:ε為父節點A所監測出節點A與節點B之間距離測量誤差值，此ε值可調整比例值k一并由父節點A傳給它。得到更新后的子節點坐標B′:(x?，y?)。在某一子節點完成該節點坐標位置更新后，該節點即可繼續向其子節點進行坐標更新。

3 實驗與分析

本文實驗僅考慮在二維環境仿真，通過MATLAB實現仿真內容。仿真實驗基于以下假設:

①在每次仿真前，根據參數(節點密度、距離測量誤差、角度測量誤差、通信半徑)隨機生成一個網絡拓撲，節點的位置隨機生成，服從隨機分布；

②節點具備距離測量和角度測量能力，每次運行，所有的測試都隨機運行30 次取均值，以選取較為平均的結果；

③節點收發消息正常，但是存在由MAC 層引起的消息沖突和消息重傳，節點之間無障礙物，其通信模型采用自由空間電波傳播模型，即各節點具有同樣通信半徑R，且通信范呈理想圓形，在此有效距離內，兩個節點之間即可互相監測和通信。使用均勻的隨機分布方式，所有的節點，隨機分布于某一固定區域內。而每一個節點的有效監測范圍為R，在此有效距離之內，兩個節點之間可互相監測并通訊。

3.1 參數選擇

首先假設一個450×450 的二維環境當中，以隨機的方式均勻放置250 個傳感器于其內，每一個節點的有效通信半徑均為50。圖4 為節點分布圖，角度測量誤差固定在正負五度的范圍之內，距離測量誤差則是以變動標準差的方式，其誤差范圍為0～8，分別皆以標準差的方式呈現。由于同步調整比例是以｜Ft｜/kmt的方式，動態調整父節點之同步比例，因此，在此實驗當中，以不同的k值，有可能會分別找出其與測量誤差之間的關系，比較不同的k值和最后定位結果的關系。節點部署完畢，首先是進入樹的形成階段。圖5 為樹形成階段完成后樹的分布仿真圖。

圖4 節點分布圖

圖5 節點樹形成階段分布圖

樹形成階段過后便真正開始節點定位，先局部后全局，直到所有節點都獲得一個全局坐標系中的唯一坐標值。首先分析不同的參數選擇對定位誤差率的影響，以便確定參數的選擇。

3.2 距離測量誤差與定位誤差

首先，比較不同的距離測量誤差與定位誤差的關系。假設角度測量誤差的標準差μ2固定在5%。距離測量誤差則以變動標準差的方式，其誤差范圍為0～10。從圖6 中可以得出:隨著距離測量誤差的增大，定位誤差率也逐漸增大。變化不算明顯，0～10 內都可以滿足定位精度要求。

圖6 定位誤差率與測距誤差率的關聯

3.3 定位誤差率的比較

對本方法的定位誤差率進行實驗，距離測量誤差、角度測量誤差以及算法計算誤差是造成定位誤差的主要因素。從圖7 可得:①算法定位誤差隨節點節點密度增大而增加；②本方法相較于聚類SPA[19]在定位精度上有一定的提升。聚類SPA 算法與本方法對比精度提升更明顯，坡度更陡。二者在節點密度為0.8 至1.0 之間曲線相交，之后本方法的定位誤差率小于聚類SPA 算法，差距也慢慢明顯。在節點密度較小的時候，聚類SPA 算法的定位誤差率要小于本方法，主要原因是聚類SPA 算法定位節點少，且大部分圍繞在中心樹周邊，產生的誤差較小；隨著節點密度的增加，本方法的定位誤差率大幅度小于聚類SPA。

圖7 不同節點密度時定位誤差率比較

定位誤差產生的主要原因包括距離測量和角度測量誤差、坐標計算誤差、節點節點坐標更新過程誤差。定位誤差率與節點密度呈正相關，主要是由同步階段的誤差累加。若要減小此類誤差，通常需要減少更新迭代次數，即減少坐標節點數量計算的迭代次數，這正是本方法比聚類SPA 算法更有優勢的地方，從而有效地降低定位誤差率。

4 總結

節點定位技術是無線傳感器網絡中的研究熱點之一，也是無線傳感器網絡實際應用中重要的支撐技術之一。大多數的定位算法都是依賴少數信標節點來確定其他多數一般節點的位置，而信標節點的坐標信息，基本上是由全球衛星定位系統來提供。這種借助信標節點來定位的方法至少存在以下問題:一是信標節點不可能很多，支撐數量較大的節點部署情況下的定位較為困難；二是信標節點由于人為或環境因素，常常出現位置漂移，造成其他節點難以精確定位；三是當環境位于室內或是具有某種干擾時，信標節點本身運作就會發生困難，當然其他節點也就難以定位。所以本文提出了一種角度和距離結合的無信標節點WSN 定位算法。在無信標結點存在的情況下，利用樹結構分類及合并的思想，結合角度與距離的測量，進一步更新節點方位與坐標，從而實現節點在坐標系統中的精確定位。最后通過仿真實驗表明，在節點隨機分布并在一定的密度比例下，本文提出的算法在定位精度比聚類SPA 算法有明顯的提高。