無線傳感器網絡中一種基于連通性的非測距定位算法*

徐磊磊， 徐保國

(江南大學 輕工過程先進控制教育部重點實驗室,江蘇 無錫 214122)

?

計算與測試

無線傳感器網絡中一種基于連通性的非測距定位算法*

徐磊磊， 徐保國

(江南大學 輕工過程先進控制教育部重點實驗室,江蘇 無錫 214122)

摘要:針對傳統非基于測距的定位算法僅用二進制數評估連接與否而沒有基于單純的連通性導致定位誤差增加的問題，基于1跳內相鄰節點間距離的遠近關系，提出了一種調整特征距離(CSD)算法。作為一個透明的支撐層，只需較少額外成本。仿真實驗表明: 嵌入CSD后的定位算法可以有效提高定位精度。

關鍵詞：無線傳感器網絡； 非測距定位； 調整特征距離

0引言

無線傳感器網絡(wireless sensor networks，WSNs)是一種新型信息感知、收集和處理技術，其應用能否成功實施的關鍵是節點提供的位置信息是否準確[1]。目前的定位算法主要分為：基于測距的定位算法和無需測距的定位算法[2]。基于測距的解決方案需要在每個節點上添加額外硬件，不適合大規模系統[3]。一些基于無線路由協議的非測距算法如APIT[4],DV-Hop,MDS-MAP,Amorphous等相繼被提出，這些算法通常用最小跳數表示相對距離[5]。在這些系統中，只有少數錨節點需要提供絕對坐標[6]，這大大降低了系統成本。

然而,僅僅基于連通性本身不能充分利用局部鄰域信息。傳統的定位方法僅由二進制數1或0評估連接與否而沒有基于單純的連通性，從而導致定位精度降低。為解決該問題，本文提出了利用網絡中的有序節點序列作為高維特征值，從而獲取1跳相鄰節點之間的相對距離的一種非測距方法。作為一個透明的支撐層，可以有效提高一些以連通度為基礎的定位系統精度，同時需要的額外成本較低。

1調整特征距離算法設計

1.1特征距離

對于任意的節點μi，在1跳范圍內，根據接收信號強度值降序排列所有鄰居節點，把自身加入其中作為第一個元素，形成一個有序節點序列，作為節點的高維特征(high-dimensional signature)值，記為Si。任意節點μi的Si是唯一的，它包含連通性和距離的遠近信息。 圖 1說明了網絡的連通性，每個節點生成一個有序節點序列，從自身開始，包含所有1跳范圍內的鄰居節點并按接收信號強度降序排列。在理想的情況下，距離值會隨之增加。

如果節點um和un在特征值Si和Sj順序顛倒，亦即這對節點在Si和Sj發生翻轉。兩個特征值間通常有三種類型的翻轉：1)顯式翻轉;2)隱式翻轉;3)可能翻轉。

如果節點對um和un同時出現在特征值Si和Sj中，很容易判斷其是否發生了翻轉，這類翻轉稱之為顯式翻轉。

圖1　鄰節點排序Fig 1　Neighbor nodes ordering

一般來說，節點對{um,un}出現在Si中，但在Sj中um和un均未出現，不能確定在Sj中節點對{um,un}是否發生了翻轉，稱為可能翻轉。

通過以上說明，定義Si和Sj之間的特征距離(signaturedistance，SD)如下：

SD(Si,Sj)等于顯式翻轉數目Fe(Si,Sj)加上隱式翻轉Fi(Si,Sj)加上0.5倍的可能翻轉Fp(Si,Sj)，即

SD(Si,Sj)=Fe(Si,Sj)+Fi(Si,Sj)+0.5Fp(Si,Sj).

(1)

下面給出計算SD的算法。

算法1SD的計算

Input:Si,Sj

Output:SD(Si,Sj)

1)Si=sort(Si)

2)Sj=sort(Sj)

7)SD(Si,Sj)=Fe+i+Fp×0.5

通過觀察有以下發現：

觀察1：一個節點對從Si到Sj翻轉{um,un}?{un,um}表明線段L(ui,uj)與垂直平分線B(um,un)相交。如S2包含節點對{1,3}，而在S3中翻轉為{3,1}，從節點2到節點3的線段需要經過垂直平分線B(1,3)。

觀察2：SD(Si,Sj)等于從ui到uj沿著線段L(ui,uj)所相交的平分線的數目。

觀察3：在大致均勻平分線密度下，鄰節點ui到uj沿線段L(ui,uj)所相交的平分線數目近似正比于兩節點的實際距離，記為PD(ui,uj)。這里平分線密度定義為單位距離線的條數。圖 2列出了沿著線段所經過的平分線的個數和兩個節點的距離?？梢钥吹?，一個線段通過平分線的數目大致正比于線段的長度，即兩個節點之間的實際距離。

圖2　實際距離與平分線個數的比較Fig 2　Comparison of actual distance with number of bisector

由上述3個觀察得到一個啟發性的規則：兩個鄰居節點ui和uj的SD近似正比于它們的實際距離，即

SD(Si,Sj)∝PD(ui,uj).

(2)

SD在1跳范圍內近似反映了節點遠近關系，可將SD作為相對距離。某些情況下，SD可能會不滿足觀察3，下面提出一種更加健壯的相對距離，即調整的SD(correctionSD，CSD)去解決這一問題。

1.2CSD的設計

1.2.1SD調整的原因

如圖3(a)所示，節點1較近的區域具有較高的平分線密度，節點2和3附近區域密度較低，這種微觀層面的觀察結果顯示，SD調整需要考慮具體節點周圍區域的平分線密度。在宏觀層面上，相同的實際距離對應的SD可能不同，這取決于領域的大小。如圖3(b)節點ui和uj之間實際距離w，當它們有兩個大圓所示的1跳廣播范圍時，SD(ui,uj)要記入B(v,c)，而以小圓廣播時，不計算B(v,c)，因此,兩個SD(ui,uj)的值不相等。

圖3　CSD的原因示意圖Fig 3　Diagram of reason of CSD

1.2.2調控因子的推導

對于節點ui和uj鄰區域所有節點K=|Si∪Sj|，可以產生nB=K(K-1)/2條平分線，根據文獻[7]的餅分割理論nB條平分線將平面分割成nR個小區域

(3)

節點ui和uj鄰域面積記為S，各小區域期望面積和期望直徑記為E[sR]和E[dR]

(4)

其中,α是由小區域的形狀建模確定的常數因子。

如圖4假設線段L(ui,uj)與NB(ui,uj)條平分線相交，則線段L(ui,uj)經過NB(ui,uj)-1個小區域，加入兩端殘差(每邊算作半個區域)中，得到一個近似

PD(ui,uj)≈NB(ui,uj)·E[dR].

(5)

圖4　垂直平分線和小區域Fig 4　Perpendicular bisector and small regions

SD(ui,uj)近似為線段L(ui,uj)經過的平分線的數量，即SD(ui,uj)≈NB(ui,uj)，所以

PD(ui,uj)≈SD(Si,Sj)·E[dR]

(6)

對于均勻隨機分布，節點在一個區域中的預期數量是與區域大小呈正比，即E[k]=φ·S,其中,φ是節點分布密度，由于nB=K(K-1)/2，式(6)可以改寫為

(7)

(8)

2嵌入CSD算法設計

2.1支撐層設計

CSD的設計可以在定位算法中作為支撐層，用沿著兩個節點線段間的最小累積CSD代替最小跳數作為所估計的相對距離。對于1跳內的鄰節點ui和uj，兩節點間的累積CSD為CSD(ui,uj)。對于非相鄰節點ui和uj，累積CSD為沿ui和uj之間經過的相鄰節點的CSD值之和。

基于連通度的非測距定位算法如MDS-MAP，DV-Hop，無需修改原始算法的主要設計。具體而言，MDS-MAP中距離矩陣的最小跳數替換為累積CSD值。同樣，DV-Hop將最小跳數替換為累積RSD值，1單位CSD值為

(9)

2.2算法復雜度

嵌入CSD后的定位算法值只增加較少的開銷，算法CSD的計算復雜度為O(KlgK)。其中,K為網絡中所有特征值序列中的最大長度，通常K?n，n為網絡中所有節點的個數?？紤]到其他計算組件的復雜性，如MDS對矩陣分解步驟復雜度O(n3)，增加的開銷很少。通信方面，唯一的額外開銷是相鄰節點間的特征值信息交換。特征值非常短，可以在網絡初始化階段傳遞消息。因此，嵌入CSD后的算法并不影響它的可擴展性。

3仿真與結果分析

3.1錨節點數目的影響

從圖 5可以看出：隨著錨節點增多，所有方法的定位精度均獲得了提高。CSD嵌入比增加錨節點數目更有效，尤其是在增加到8個錨節點后曲線變得平坦。嵌入CSD后DV-Hop定位誤差降低約30 %，MDS-MAP下降約10 %。

圖5　定位誤差隨錨節點數目變化曲線Fig 5　Curve of localization error change with numberof anchor nodes

3.2節點數目的影響

實驗將節點數目從100個增加至400個。圖 6表明:1)應用CSD的算法相對于原算法有更好的定位性能。2)DV算法在節點數目從100增加到200并沒有太多提高了系統的定位精度。這是由于在這個階段，較高的節點密度有助于估算平均跳距。節點增加到200個后平均跳距很難進一步提高，而更多節點都被映射到相同的估計位置，增加了錯誤統計。3)對于 MDS算法，更高的節點密度帶來較小的定位誤差。

圖6　定位誤差隨節點數目變化曲線Fig 6　Curve of localization error change with number of nodes

3.3網絡大小的影響

實驗以步長150 m增加正方形網絡區域邊長，網絡中的節點的數目成比例地增加，以保持相同的節點密度。錨節點數量保持恒定。

從圖 7曲線可以看出:1)應用CSD的定位算法比原有算法具有更好的定位精度。2)由于錨節點數目沒有呈比例增加，在大型網絡中定位性能較差。3)基于MDS的算法比DV算法更適合于大規模網絡，這是因為MDS為基礎的方法利用鄰近節點又利用到遠程節點的估計距離，而DV更多地取決于到遠程錨節點所估計的距離，在較大的網絡易誤差累積。

4結束語

本文提出了一種基于連通度獲得相對距離的非測距定位算法。作為一個透明的支撐層，CSD可以方便地嵌入到許多基于連通性的定位算法中如DV-HOP，MDS-MAP算法中，增加開銷較小，大大提高定位精度，CSD具有很好的魯棒性，適用大規模網絡。

圖7　定位誤差隨網絡大小變化曲線Fig 7　Curve of localization error change with network scales

參考文獻:

[1]Akyildiz I F,Weilian S,Sankarasubramaniam Y,et al.A survey on sensor networks[J].IEEE Communications Magazine,2002,40(8):102-114.

[2]孫利民，李建中，陳渝，等.無線傳感器網絡[M].北京：清華大學出版社，2005.

[3]Cullar D,Estrin D,Strvastava M.Overview of sensor network[J].Computer,2004,37(8):41-49.

[4]王長征．湯文亮，徐燕.無線傳感器網絡中四面體三維質心定位算法[J].傳感器與微系統，2012,31(8)：141-146.

[5]Jia Z X,Wu C D,Zhang Y Z,et al.Distributed grid location estimation scheme based on euclidean distance[C]∥IEEE the 3rd Conference on Industrial Electronics and Applications,2008:1128-1132.

[6]Joo G L,Rao S V.A grid-based location estimation scheme using hop counts for multi-hop wireless sensor networks [C]∥International Workshop on Wireless Ad-Hoc Networks,2004:330-334.

[7]Bery M De,Cheong O,Van Krevald M,et al.Computational geometry:Algorithms and applications[M].3rd ed.Berlin:Springer-Verlag,2008.

徐磊磊(1989-)，男，江蘇南通人，碩士研究生，主要研究方向為無線傳感器網絡定位。

A range-free localization algorithm for WSNs based on connectivity*

XU Lei-lei， XU Bao-guo

(Key Laboratory of Advanced Process Control for Light Industry,Ministry of Education，Jiangnan University，Wuxi 214122，China)

Abstract:Aiming at the problem that the traditional positioning method uses binary number to evaluate connectivity instead of pure connectivity,which results in increasing of positioning error.A range-free localization algorithm named correction signature distance(CSD) algonthm based on distance between adjacent nodes within 1 hop is proposed.As a transparent support layer,it only needs less extra cost.Simulation results show that the localization algorithms embedded by CSD can effectively improve positioning precision.

Key words:wireless sensor networks (WSNs); range-free localization; correction signature distance(CSD)

作者簡介:

中圖分類號：TP 393

文獻標識碼：A

文章編號：1000—9787(2016)01—0127—04

*基金項目：國家教育部博士點專項基金資助項目(20100093120007)；國家自然科學基金資助項目(61304264)

收稿日期：2015—03—17

DOI:10.13873/J.1000—9787(2016)01—0127—04