徐磊磊， 徐保國

(江南大學(xué) 輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室,江蘇 無錫 214122)

?

計(jì)算與測試

無線傳感器網(wǎng)絡(luò)中一種基于連通性的非測距定位算法*

徐磊磊， 徐保國

(江南大學(xué) 輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室,江蘇 無錫 214122)

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

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)； 非測距定位； 調(diào)整特征距離

0引言

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

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

1調(diào)整特征距離算法設(shè)計(jì)

1.1特征距離

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

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

如果節(jié)點(diǎn)對um和un同時(shí)出現(xiàn)在特征值Si和Sj中，很容易判斷其是否發(fā)生了翻轉(zhuǎn)，這類翻轉(zhuǎn)稱之為顯式翻轉(zhuǎn)。

圖1　鄰節(jié)點(diǎn)排序Fig 1　Neighbor nodes ordering

一般來說，節(jié)點(diǎn)對{um,un}出現(xiàn)在Si中，但在Sj中um和un均未出現(xiàn)，不能確定在Sj中節(jié)點(diǎn)對{um,un}是否發(fā)生了翻轉(zhuǎn)，稱為可能翻轉(zhuǎn)。

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

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

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

(1)

下面給出計(jì)算SD的算法。

算法1SD的計(jì)算

Input:Si,Sj

Output:SD(Si,Sj)

1)Si=sort(Si)

2)Sj=sort(Sj)

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

通過觀察有以下發(fā)現(xiàn)：

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

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

觀察3：在大致均勻平分線密度下，鄰節(jié)點(diǎn)ui到uj沿線段L(ui,uj)所相交的平分線數(shù)目近似正比于兩節(jié)點(diǎn)的實(shí)際距離，記為PD(ui,uj)。這里平分線密度定義為單位距離線的條數(shù)。圖 2列出了沿著線段所經(jīng)過的平分線的個(gè)數(shù)和兩個(gè)節(jié)點(diǎn)的距離。可以看到，一個(gè)線段通過平分線的數(shù)目大致正比于線段的長度，即兩個(gè)節(jié)點(diǎn)之間的實(shí)際距離。

圖2　實(shí)際距離與平分線個(gè)數(shù)的比較Fig 2　Comparison of actual distance with number of bisector

由上述3個(gè)觀察得到一個(gè)啟發(fā)性的規(guī)則：兩個(gè)鄰居節(jié)點(diǎn)ui和uj的SD近似正比于它們的實(shí)際距離，即

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

(2)

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

1.2CSD的設(shè)計(jì)

1.2.1SD調(diào)整的原因

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

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

1.2.2調(diào)控因子的推導(dǎo)

對于節(jié)點(diǎn)ui和uj鄰區(qū)域所有節(jié)點(diǎn)K=|Si∪Sj|，可以產(chǎn)生nB=K(K-1)/2條平分線，根據(jù)文獻(xiàn)[7]的餅分割理論nB條平分線將平面分割成nR個(gè)小區(qū)域

(3)

節(jié)點(diǎn)ui和uj鄰域面積記為S，各小區(qū)域期望面積和期望直徑記為E[sR]和E[dR]

(4)

其中,α是由小區(qū)域的形狀建模確定的常數(shù)因子。

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

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

(5)

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

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

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

(6)

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

(7)

(8)

2嵌入CSD算法設(shè)計(jì)

2.1支撐層設(shè)計(jì)

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

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

(9)

2.2算法復(fù)雜度

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

3仿真與結(jié)果分析

3.1錨節(jié)點(diǎn)數(shù)目的影響

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

圖5　定位誤差隨錨節(jié)點(diǎn)數(shù)目變化曲線Fig 5　Curve of localization error change with numberof anchor nodes

3.2節(jié)點(diǎn)數(shù)目的影響

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

圖6　定位誤差隨節(jié)點(diǎn)數(shù)目變化曲線Fig 6　Curve of localization error change with number of nodes

3.3網(wǎng)絡(luò)大小的影響

實(shí)驗(yàn)以步長150 m增加正方形網(wǎng)絡(luò)區(qū)域邊長，網(wǎng)絡(luò)中的節(jié)點(diǎn)的數(shù)目成比例地增加，以保持相同的節(jié)點(diǎn)密度。錨節(jié)點(diǎn)數(shù)量保持恒定。

從圖 7曲線可以看出:1)應(yīng)用CSD的定位算法比原有算法具有更好的定位精度。2)由于錨節(jié)點(diǎn)數(shù)目沒有呈比例增加，在大型網(wǎng)絡(luò)中定位性能較差。3)基于MDS的算法比DV算法更適合于大規(guī)模網(wǎng)絡(luò)，這是因?yàn)镸DS為基礎(chǔ)的方法利用鄰近節(jié)點(diǎn)又利用到遠(yuǎn)程節(jié)點(diǎn)的估計(jì)距離，而DV更多地取決于到遠(yuǎn)程錨節(jié)點(diǎn)所估計(jì)的距離，在較大的網(wǎng)絡(luò)易誤差累積。

4結(jié)束語

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

圖7　定位誤差隨網(wǎng)絡(luò)大小變化曲線Fig 7　Curve of localization error change with network scales

參考文獻(xiàn):

[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]孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.

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

[4]王長征．湯文亮，徐燕.無線傳感器網(wǎng)絡(luò)中四面體三維質(zhì)心定位算法[J].傳感器與微系統(tǒng)，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-)，男，江蘇南通人，碩士研究生，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)定位。

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

文獻(xiàn)標(biāo)識(shí)碼：A

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

*基金項(xiàng)目：國家教育部博士點(diǎn)專項(xiàng)基金資助項(xiàng)目(20100093120007)；國家自然科學(xué)基金資助項(xiàng)目(61304264)

收稿日期：2015—03—17

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