馬慶功，劉冉冉

(1.常州大學 信息中心，江蘇 常州 213000；2.常州劉國鈞高等職業(yè)技術學校，江蘇 常州 213000)

無線傳感器網(wǎng)絡是21世紀最重要的信息獲取和處理技術之一，能夠廣泛的應用在智能交通、國防軍事和空間探索等許多領域．節(jié)點自定位技術是無線傳感器網(wǎng)絡的主要支撐技術之一，節(jié)點自身的準確定位是提供監(jiān)測信息事件位置信息的前提，而沒有位置信息的監(jiān)測信息是毫無意義的[1]．

1 DV-Distance定位算法

1.1 DV-Distance定位算法介紹

美國路特葛斯大學(Rutgers University)的Dragos Niculescu等人利用GPS定位的原理和距離矢量路由提出了一系列分布式定位算法，因為是在自組織網(wǎng)絡下研究得到的，因此將它們合稱為自組織定位系統(tǒng)(ad hoc positioning system，APS)[2-4]．這里面包含了以下幾種算法：DV-Coordinate、DV-Hop、DV-Radial、DV-Distance、DV-Bearing和DV-Euclidean．為了降低對節(jié)點的性能要求，Badri Nath等人提出了DV-Distance定位算法，這個算法比DV-Hop定位算法對節(jié)點的要求更低，節(jié)點不用存儲網(wǎng)絡中每個節(jié)點的位置信息，這樣就降低了節(jié)點間的通信量，所以節(jié)省了節(jié)點的大量工作能量，使節(jié)點有了更長的生存周期．缺點是它需要直接測量節(jié)點之間的距離，導致這個定位算法對距離的敏感性要求高，誤差很大[5-7]．

本文中所研究的DV-Distance算法的定位主要分以下兩個步驟進行：(1)確定信標節(jié)點與所有未知節(jié)點之間的跳段距離.兩個節(jié)點之間的跳段總數(shù)稱為跳數(shù)，各個跳段的距離之和稱為兩個節(jié)點之間的跳段距離．根據(jù)距離矢量交換協(xié)議的基本理論，所謂信標節(jié)點是指通過GPS能獲取自身物理坐標，它只向其通信半徑內(nèi)的所有鄰居節(jié)點傳播其位置信息，即跳數(shù)和跳段距離．位置確定過程如下：首先初始化信標節(jié)點與未知節(jié)點的跳數(shù)及跳段距離為0，比較同一個參考節(jié)點的跳數(shù)后，各接收節(jié)點保留其中跳數(shù)最小的分組，將跳數(shù)加1并累加與各個參考節(jié)點之間的跳段距離，轉(zhuǎn)發(fā)給其他未知節(jié)點．此方法避免了定位過程中無限循環(huán)的廣播信息，并能夠記錄下無線傳感器網(wǎng)絡中所有已知節(jié)點到鄰居節(jié)點的累計跳段距離和最小跳數(shù)．(2)確定未知節(jié)點的位置.通過上述第(1)步確定的各已知節(jié)點到鄰居節(jié)點的累計跳段距離，并將其作為有效距離利用三邊測量法確定出未知節(jié)點的坐標位置，如式(1)所示．

(1)

DV-Distance定位算法采用RSSI技術，利用接收信號強度的值以及傳統(tǒng)的路徑損耗傳播模型計算出各個節(jié)點間的距離，并進一步確定未知節(jié)點和信標節(jié)點間的跳段距離，將其作為有效距離，利用距離矢量路由算法傳播未知節(jié)點與信標節(jié)點之間的累計距離．當獲取三個以上有效距離后，利用三邊測量法進一步求出未知節(jié)點的坐標．

(2)

1.2 DV-Distance定位算法的分析

DV-Distance的算法優(yōu)點[8]：(1)因為采用RSSI測距技術測定每一跳的距離，所以每跳不必距離相等；(2)該算法所需的無線傳感器網(wǎng)絡簡單、可升級，且算法較為健壯；(3)算法對節(jié)點的要求比較低，節(jié)點不用儲存網(wǎng)絡中各個節(jié)點的位置信息，減少了節(jié)點之間因為通信而消耗的能量；(4)通過修正因子可以大大提高定位的精度．

DV-Distance定位算法自身存在著一定的缺陷[9]，它的缺點有：(1)RSSI測距技術受環(huán)境影響較為嚴重，溫度不同，有無障礙物、傳播模式不同、各節(jié)點的實際距離不同都給測量帶來較大的精確度差異；(2)DV-Distance定位算法將未知節(jié)點與信標節(jié)點之間的折線距離作為有效距離，當存在多個跳段或某個跳段距離過大時，該算法所確定出的有效距離就會存在較大的誤差；(3)因為在網(wǎng)絡中使用了RSSI測距技術，所以節(jié)點內(nèi)需要有測量信號強度的模塊，這使得設備造價較為昂貴．

實驗顯示，DV-Distance定位算法的定位精度為20%(網(wǎng)絡平均連通度為9，信標節(jié)點比例為10%，測距誤差小于10%)，但隨著測距誤差的增大，DV-Distance算法的定位誤差也將急劇增大[10-11]．

2 算法仿真與結果分析

2.1 基本算法與流程

本算法利用MATLAB進行仿真分析，具體流程如下:第一步,設置初始量，布置了一個范圍為100×100的區(qū)域，其中隨機的布置了200個無線傳感器節(jié)點，這兩百個節(jié)點中的信標節(jié)點數(shù)量可以進行更改，同時設定了節(jié)點通信半徑．第二步，從第一個信標節(jié)點開始，找到在該信標節(jié)點的通信半徑內(nèi)的所有未知節(jié)點，并記錄這些與信標節(jié)點相距只有一跳的未知節(jié)點，然后再通過剛剛得到的與信標節(jié)點相距一跳的節(jié)點尋找跳數(shù)為二的未知節(jié)點，依次進行下去完成關于未知節(jié)點的跳數(shù)矩陣．第三步，通過跳數(shù)矩陣，利用RSSI技術的測距模型，計算出未知節(jié)點與信標節(jié)點的距離．第四步，當未知節(jié)點獲得與三個或更多信標節(jié)點的距離后，使用最小二乘法的方法計算出未知節(jié)點的位置．第五步，將計算出的節(jié)點位置以及系統(tǒng)初始化的節(jié)點位置同時表示在同一張圖上，并計算其平均誤差以及測距精度．

2.2 仿真結果與分析

2.2.1 不同信標節(jié)點密度時的仿真結果及分析

在仿真中，對無線傳感器網(wǎng)絡的設置是范圍為100×100 m，共有200個無線傳感器節(jié)點，信標節(jié)點的密度分別為20%、30%時，通信半徑設定為20 m．圖1即為仿真出的節(jié)點分布圖，圖中用*來表示信標節(jié)點的位置，用o來表示未知節(jié)點的位置．

為了更好的研究DV-Distance算法，利用MATLAB進一步描繪出節(jié)點之間的鄰居節(jié)點圖，即節(jié)點之間的通信連接圖．如圖2所示，節(jié)點之間的通信以連線的模式來表示，通過該圖可以較為清楚的了解節(jié)點之間的通信傳輸．

為了較為清楚的看出仿真算法的定位效果，將定位后的節(jié)點分布圖再次顯示出來，如圖3所示，并用線連接了未知節(jié)點的實際位置與定位測算位置，可以較為定量的看出節(jié)點定位的誤差是否存在很大的波動．

(a) 信標節(jié)點密度20%時的節(jié)點分布 (b) 信標節(jié)點密度30%時的節(jié)點分布

圖1節(jié)點分布圖

(a) 信標節(jié)點密度20%時節(jié)點間鄰居關系圖 (b) 信標節(jié)點密度30%時節(jié)點間鄰居關系圖

圖2節(jié)點間鄰居關系圖

(a) 信標節(jié)點密度20%時的定位誤差圖 (b) 信標節(jié)點密度30%時的定位誤差圖

圖3仿真的定位誤差圖

信標節(jié)點密度20%時共有160個未知節(jié)點，其中有25個未知節(jié)點的位置無法測算，其定位誤差為0.34605．信標節(jié)點密度30%時共有140個是未知節(jié)點，仿真實現(xiàn)定位時共有9個不能被定位的未知節(jié)點．本次仿真的定位誤差為0.29747．

通過多次仿真比較，增加信標節(jié)點的密度，可以減少定位算法的定位誤差，同時可以減少無法定位的未知節(jié)點的數(shù)目．但是增加信標節(jié)點的密度，等同于增加信標節(jié)點的數(shù)量，信標節(jié)點含有GPS裝置，而且通常信標節(jié)點擁有更好的通信能力和更持久的能量供應，這就導致信標節(jié)點的費用遠高于普通節(jié)點．增加信標節(jié)點的數(shù)量，提高定位精度的同時，帶來的是費用的增加，如何平衡這兩者，則要視具體情況而定．

2.2.2 GPS存在誤差時的仿真結果及分析

通過文獻可知，我們之所以能夠知道信標節(jié)點的位置，是因為信標節(jié)點內(nèi)預先布置了GPS定位裝置，但是通常情況下，GPS裝置自身也存在一定的定位誤差，在上面的仿真中，并沒有考慮到GPS自身的定位誤差．對此進行改進，在前面的仿真基礎中加入GPS自身的定位誤差，設定定位誤差為3%，當信標節(jié)點密度為20%，所得的節(jié)點分布圖、鄰居關系圖及定位誤差圖分別如圖4～7所示．

仿真結果顯示，定位時共有4個不能被定位的未知節(jié)點，定位誤差為0.3584．通過多次仿真實驗可知，由于GPS裝置自身的定位誤差被帶入了仿真測算中，導致了仿真的定位的誤差增大，可見GPS誤差的能夠影響到DV-Distance算法的定位精度．

圖4節(jié)點分布圖(GPS存在誤差)圖5鄰居關系圖(GPS存在誤差)

圖6定位誤差圖(GPS存在誤差)圖7節(jié)點分布圖(存在障礙物)

2.2.3 存在障礙物時的仿真結果及分析

在實際的監(jiān)測情況里，往往有可能存在著障礙物，因為無線傳感器網(wǎng)絡的通信方式是無線通信，這些障礙物會對節(jié)點間的通信造成影響，甚至有可能阻礙到節(jié)點間的通信.為了使仿真更接近真實情況，對程序進行了改動，模擬出如圖8的具有障礙物的監(jiān)測區(qū)域．在信標節(jié)點密度為30%時，所得的節(jié)點分布圖、鄰居關系圖及定位誤差圖分別如圖8～11所示．

仿真結果顯示，共有9個不能被定位的未知節(jié)點，定位誤差為0.33062．進一步分析圖8，由于存在障礙物，使得處在障礙物上下方的未知節(jié)點與信標節(jié)點之間的跳數(shù)變得較大，跳數(shù)變大將影響到距離的計算值，這樣會導致定位的誤差增大．

對上述信標節(jié)點密度為20%，以及節(jié)點密度為30%在無GPS誤差、GPS定位誤差為3%和存在障礙物共四種情況下進行多次實驗，將所得出的誤差值利用二維圖進行繪制，以此來分析算法定位的性能．由圖10可以看出，信標節(jié)點密度為30%的網(wǎng)絡的定位略優(yōu)于信標節(jié)點密度為20%的情況．而綜合分析圖10以及圖11之后，可以看出在障礙物存在的情況下，定位的誤差是最大的，而當GPS有誤差時，其定位效果就不如GPS無誤差的情況．

圖8鄰居關系圖(存在障礙物)圖9定位誤差圖(存在障礙物)

圖10誤差分析(1)圖11誤差分析(2)

3 結論

本文介紹了用于無線傳感器網(wǎng)絡的定位算法，著重研究了基于DV-Distance的定位算法，闡述了其原理，并對DV-Distance定位算法在不同信標節(jié)點密度、GPS存在誤差及有障礙物情況下分別進行仿真分析．結果表明增加信標節(jié)點的密度，可以減少定位算法的定位誤差，但會增加成本，而當存在障礙物時定位誤差最大．

[1]萬潤澤，雷建軍. 無線傳感器網(wǎng)絡密鑰管理方案比較研究[J]. 吉林師范大學學報(自然科學版),2013,34(3):104～107.

[2]Niculescu D,Nath B. Ad-Hoc positioning systems (APS) [C]. GLOBECOM 2001,San Antonio. New York: IEEE Press,2001,5: 2926～2931.

[3]李潔鴻，謝 睿，陳向東，等.改進的無線傳感器網(wǎng)絡DV-Distance定位算法 [J].通信技術，2012，45(3)：52～54.

[4]Niculescu D,Nath B. DV based positioning in ad hoc networks[J]. Journal of Telecommunication Systems,2003,22(1):267～280.

[5]于海斌，曾 鵬，梁 斡．智能無線傳感器網(wǎng)絡系統(tǒng)[M]. 北京: 科學出版社,2006.

[6]王福豹，史 龍，任豐原.無線傳感器網(wǎng)絡中的自身定位系統(tǒng)和算法[J].軟件學報,2005,16(5)：857～868.

[7]He T,Huang C,Blum B M,et al. Range-free localization and its impact on large scale sensor networks [J]. ACM Trans. Embedded Computing and System,2005,4(4): 877～906.

[8]Patwari N,Ash J N,Kyperountas S,et al. Locating the nodes: cooperative localization in wireless sensor networks [J]. IEEE Signal Process,2005,22(4): 54～69.

[9]R Want,A Hopper,V Falcao,J Gibbon. The action badge location system ACM Transactions on Information System [J].1992,10 (1): 91～102.

[10]J Robet,D Gregory. The smart floor: A mechanism for natural user identification and tracking[C]. In Proceedings of the 2000 Conference on Human Factors in Computing System(CHI 2000),The Hage,Netherlands,ACM Press,2000,4: 275～276.

[11]A Cerpa and D Estrin. Ascent: Adaptive self-configuring sensor network topologies,Technical Report C'SD-TR 01-009[D].University of California,Los Angeles,Computer Science department,2001.