国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

基于改進DV-Hop算法的無線傳感器網(wǎng)絡(luò)定位研究*

2014-08-08 06:25:28
關(guān)鍵詞:信標粒子無線

李 鵬

(長江大學 計算機科學學院,湖北 荊州 434023)

0 引 言

無線傳感器網(wǎng)絡(luò)是由部署在監(jiān)測區(qū)域內(nèi)大量的具有計算和通信能力的微型傳感器節(jié)點組成,通過無線通信的方式形成一個多跳的自組織的網(wǎng)絡(luò)系統(tǒng)[1],其作用是利用傳感器來監(jiān)測、收集、處理信息數(shù)據(jù),傳感器的無線收發(fā)裝置將數(shù)據(jù)通過無線通信傳輸。傳感器節(jié)點的定位是無線傳感器網(wǎng)絡(luò)的基本功能。根據(jù)是否需要測量實際節(jié)點間的距離,把無線傳感器網(wǎng)絡(luò)定位算法分為兩類:基于距離的定位算法(Range-based)和距離無關(guān)的定位算法(Range-free)[2]?;诰嚯x的定位算法共同特點是需要測量相鄰節(jié)點間的絕對距離或方位,并通過測量的絕對距離和方位來計算未知節(jié)點的位置;距離無關(guān)的定位算法則不需要測量節(jié)點間的絕對距離或方位,而是要得到節(jié)點間的估計距離,然后利用估計距離計算節(jié)點位置。

距離無關(guān)的定位算法通常有DV-Hop算法、質(zhì)心算法、APIT算法等經(jīng)典算法[3]。其中DV-Hop算法使用每跳平均距離乘以跳段數(shù)來計算節(jié)點間距離,對網(wǎng)絡(luò)節(jié)點的硬件設(shè)備要求低,部署簡單,實現(xiàn)起來比較簡易,缺點是節(jié)點間的跳段距離是估算出來的,用節(jié)點間的跳段距離代替節(jié)點間的實際直線距離是不精確的,存在誤差[4]。在分析了傳統(tǒng)DV-Hop算法特點的基礎(chǔ)上,提出了一種改進的DV-Hop算法,主要思想是利用粒子群優(yōu)化算法對DV-Hop算法中的每跳平均距離誤差函數(shù)進行優(yōu)化,從而精確了節(jié)點間的跳段距離,達到了對DV-Hop算法校正的目的,通過三邊測量法計算出的未知節(jié)點的位置更精確。

1 無線傳感器網(wǎng)絡(luò)定位技術(shù)

1.1 定位技術(shù)基本概念

在傳感器網(wǎng)絡(luò)節(jié)點定位中,節(jié)點分為信標節(jié)點和未知節(jié)點,信標節(jié)點是未知節(jié)點的參考點,信標節(jié)點數(shù)量比未知節(jié)點要少,信標節(jié)點可通過GPS定位裝置來確定自己的準確位置,而未知節(jié)點通過和鄰近的信標節(jié)點或者是已經(jīng)確定位置的未知節(jié)點進行通信,來確定自己的位置。

1.2 測量節(jié)點位置基本方法

圖1 三邊測量法圖示

計算節(jié)點位置的方法有三邊測量法、三角測量法、極大似然估計法。在此主要介紹三邊測量法[5],三邊測量法是未知節(jié)點接收到3個以上信標節(jié)點的位置信息后(以3個信標節(jié)點為例),就可以得到未知節(jié)點到3個信標節(jié)點的距離,然后可以算出未知節(jié)點的坐標,三邊測量法圖示如圖1所示。假設(shè)已知3個信標節(jié)點A、B、C的坐標分別為(xA,yA)、(xB,yB)、(xC,yC),未知節(jié)點的坐標為(x,y),未知節(jié)點到3個信標節(jié)點的距離分別為dA,dB,dC,則:

(1)

通過式(1)可得到未知節(jié)點D的坐標為

(2)

1.3 定位性能評價標準

無線傳感器網(wǎng)絡(luò)定位系統(tǒng)算法很多,常用的衡量定位能力的標準有定位精度,定位精度是指定位系統(tǒng)提供的位置信息的精確程度,是評價定位能力的最關(guān)鍵的標準,精度越高,技術(shù)要求也越高。除此之外,還有覆蓋范圍、信標節(jié)點密度、節(jié)點密度、容錯性和魯棒性以及功耗等。

2 定位算法分析

2.1 基于距離的定位算法

基于距離的定位機制(Range-based)分為3個階段:第1階段為測距階段;第2階段為定位階段;第3階段是修正階段,對第2階段計算得到的未知節(jié)點的坐標精確化,減少誤差。基于距離的定位算法通常有:基于接收信號強度指示算法RSSI、到達時間方法TOA、到達時間差方法TDOA、到達角度方法AOA等。

2.2 距離無關(guān)的定位算法

基于距離的定位算法可以精確定位未知節(jié)點的坐標,但是對無線傳感器節(jié)點的硬件要求很高,導(dǎo)致無線傳感器節(jié)點的硬件開銷大、能耗高,因此人們提出了距離無關(guān)的定位技術(shù)。距離無關(guān)的定位技術(shù)不需要測量節(jié)點間的絕對距離或角度信息,只需網(wǎng)絡(luò)連通性等約束來實現(xiàn)節(jié)點的定位,降低了無線傳感器節(jié)點的硬件開銷,但定位誤差會相應(yīng)的增加。距離無關(guān)的定位算法通常有質(zhì)心算法、DV-Hop算法、APIT算法等經(jīng)典算法,在此主要介紹DV-Hop算法。DV-Hop算法(距離向量-跳段)[6]定位過程如下:

首先,計算未知節(jié)點與每個信標節(jié)點之間的最小跳段數(shù)量,網(wǎng)絡(luò)中信標節(jié)點通過距離矢量交換協(xié)議發(fā)送一個廣播分組,將該信標節(jié)點的位置信息和跳數(shù)廣播到整個網(wǎng)絡(luò),廣播分組包括該信標節(jié)點號、坐標位置(xi,yi),以及跳數(shù),跳數(shù)初始化為0。當節(jié)點接收到該信標節(jié)點的廣播分組后對比自己的數(shù)據(jù)表的跳數(shù)和該分組的跳數(shù),如果該分組跳數(shù)小于本節(jié)點數(shù)據(jù)表內(nèi)的跳數(shù),則用分組的跳數(shù)代替節(jié)點的跳數(shù),將跳數(shù)加1,并且廣播該分組,如果該分組的跳數(shù)大于本節(jié)點數(shù)據(jù)表內(nèi)的跳數(shù),則丟棄該分組,而且不廣播該分組。這樣,所有的未知節(jié)點都能獲得與所有信標節(jié)點之間的最小跳數(shù)。

然后,計算未知節(jié)點與信標節(jié)點的距離。每個信標節(jié)點根據(jù)記錄的其他信標節(jié)點的位置信息和跳數(shù),利用式(3)估算出每跳平均距離

(3)

其中,(xi,yi),(xj,yj)是信標節(jié)點i,j的坐標,hj是信標節(jié)點i與j(j≠i)之間的跳數(shù)。然后信標節(jié)點將計算的每跳平均距離廣播到網(wǎng)絡(luò)中,未知節(jié)點記錄接收到的第一個每跳平均距離,并將分組轉(zhuǎn)發(fā)給鄰居節(jié)點,未知節(jié)點接收到每跳平均距離HopSizei后,根據(jù)記錄的自己與信標節(jié)點之間的跳數(shù)h,通過HopSizei×h計算未知節(jié)點到每個信標節(jié)點的跳段距離。

最后,利用三邊測量法或極大似然估計法計算未知節(jié)點自身位置。未知節(jié)點與各信標節(jié)點之間的跳段距離可以計算出,再利用三邊測量法或極大似然估計法計算節(jié)點自身位置坐標。

DV-Hop算法中每跳平均距離是估算出來的,節(jié)點間的跳段距離通過每跳平均距離計算得到,所以用節(jié)點間的跳段距離代替節(jié)點間的實際直線距離是不精確的,存在誤差。在近期一些相關(guān)研究中,研究者對DV-Hop算法提出了改進,提高了定位精度。本文提出通過粒子群優(yōu)化算法優(yōu)化每跳平均距離誤差函數(shù),使得未知節(jié)點與信標節(jié)點之間的跳段距離更加精確,通過三邊測量法計算得到的未知節(jié)點的位置也更精確,定位效果良好。

3 粒子群優(yōu)化算法改進DV-Hop算法

粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法是模擬鳥類捕食行為的群體智能算法,由美國電氣工程師Eberhart和社會心理學家Kennedy于1995年提出[7]。粒子群優(yōu)化算法是一種全局優(yōu)化算法,源于對鳥群群體運動行為的研究。PSO算法容易實現(xiàn),要調(diào)整的參數(shù)少,廣泛應(yīng)用于各種領(lǐng)域。

3.1 粒子群優(yōu)化算法

粒子群優(yōu)化算法的數(shù)學描述[8]:粒子群算法中每個個體就是一個“粒子”,代表一個潛在的解,在一個D維目標搜索空間中,每個粒子是空間內(nèi)的一個點,設(shè)有n個代表潛在的解的粒子組成一個群,粒子i(i=1,2,…,n)的D維位置矢量zi=(zi1,zi2,…,ziD),zi的適應(yīng)值用來衡量粒子位置的優(yōu)劣,zi當前的適應(yīng)值由預(yù)先設(shè)定的適應(yīng)值函數(shù)計算得到,粒子的飛行速度vi=(vi1,vi2,…,viD),即粒子的移動距離,記pi為粒子迄今為止搜索到的最優(yōu)位置,pi=(pi1,pi2,…,piD),記pg為整個粒子群迄今為止搜索到的最優(yōu)位置,pg=(pg1,pg2,…,pgD)。每次迭代中,粒子根據(jù)以下式子更新速度和位置:

(4)

(5)

其中,i=1,2,…,n;d=1,2,…,D,k是迭代次數(shù),r1和r2是[0,1]之間的隨機數(shù),用來保持群體的多樣性,c1和c2是學習因子,粒子通過不斷學習,最后找出pg就是全局最優(yōu)解。

3.2 粒子群算法改進DV-Hop算法過程

DV-Hop算法通過每跳平均距離乘以未知節(jié)點與信標節(jié)點間的跳數(shù)來計算未知節(jié)點到信標節(jié)點的距離,這個距離與實際直線距離是有誤差的,通過三邊測量法得到的坐標也是有誤差的,通過粒子群優(yōu)化算法校正DV-Hop算法中估算得到的每跳平均距離,從而使得未知節(jié)點到信標節(jié)點間的跳段距離更加精確,然后利用三邊測量法得到未知節(jié)點的坐標,DV-Hop算法改進過程如下:

(1) 通過信息廣播過程計算未知節(jié)點與每個信標節(jié)點之間的最小跳數(shù)h;

(2) 通過粒子群優(yōu)化算法優(yōu)化每跳平均距離誤差函數(shù),得到優(yōu)化后的每跳平均距離,計算出未知節(jié)點與信標節(jié)點的跳段距離d。首先利用式(3)得到已知信標節(jié)點間每跳平均距離HopSizei,設(shè)未知節(jié)點與信標節(jié)點間實際每跳平均距離為HopSizer,則誤差函數(shù)δ=|HopSizer-HopSizei|,利用粒子群優(yōu)化算法對誤差函數(shù)進行優(yōu)化,利用式(4)和式(5)更新粒子的位置和速度,設(shè)置適當?shù)倪m應(yīng)值,達到迭代的次數(shù)停止運算,找出最優(yōu)解,得到校正后的每跳平均距離HopSizea,然后通過HopSizea×h得到未知節(jié)點與信標節(jié)點間的跳段距離d;

(3) 通過第二步得到了經(jīng)過粒子群優(yōu)化算法校正的跳段距離d,利用三邊測量法計算未知節(jié)點自身的位置。

4 仿真實驗

本文使用Matlab進行仿真實驗,設(shè)置100 m×100 m的二維仿真環(huán)境,采用隨機分布信標節(jié)點和未知節(jié)點的方式,分成固定信標節(jié)點數(shù)量、改變節(jié)點總數(shù)和固定節(jié)點總數(shù)、改變信標節(jié)點數(shù)量以及改變節(jié)點通信半徑等3種情況進行仿真實驗,通過仿真實驗分析定位誤差的多少來對比本算法與傳統(tǒng)DV-Hop定位算法。

圖2 不同節(jié)點數(shù)的定位誤差曲線

圖3 不同信標節(jié)點數(shù)的定位誤差曲線

圖4 不同節(jié)點通信半徑的定位誤差曲線

(1) 100 m×100 m區(qū)域內(nèi),設(shè)置30個信標節(jié)點,節(jié)點總數(shù)分別為50、100、150、200、250、300、350時仿真情況如圖2所示,定位誤差隨著節(jié)點數(shù)的增大而下降,通過粒子群優(yōu)化算法改進的DV-Hop定位算法的定位誤差率比傳統(tǒng)DV-Hop定位算法的低。

(2) 100 m×100 m區(qū)域內(nèi),設(shè)置節(jié)點總數(shù)300個,信標節(jié)點數(shù)量為10、15、20、25、30、35時仿真情況如圖3所示,定位誤差隨著信標節(jié)點數(shù)的增大而下降,通過粒子群優(yōu)化算法改進的DV-Hop定位算法的定位誤差率比傳統(tǒng)DV-Hop定位算法的低。

(3) 100 m×100 m區(qū)域內(nèi),設(shè)置節(jié)點總數(shù)300個,信標節(jié)點占10%,節(jié)點通信半徑R從10 m到30 m遞增,節(jié)點通信半徑與平均定位誤差的關(guān)系如圖4所示,從圖4中可以看出,本文的改進DV-Hop算法優(yōu)越于傳統(tǒng)的DV-Hop算法,當節(jié)點的通信半徑達到30 m時,平均定位誤差下降到20%左右。

5 結(jié)束語

DV-Hop算法不需要測量節(jié)點間的絕對距離和方位,節(jié)點的硬件要求低,開銷小,適合大規(guī)模布置,受環(huán)境因素影響小,適合復(fù)雜的監(jiān)測環(huán)境,但是DV-Hop算法定位精度較差,本文采用粒子群優(yōu)化算法對DV-Hop算法進行了改進,實驗表明,提高了定位精度。

參考文獻:

[1] 張俊霞, 汪煬, 李善亮. 基于無線傳感器網(wǎng)絡(luò)的定位系統(tǒng)設(shè)計[J]. 計算機工程與應(yīng)用, 2008, 44(17):67-70

[2] 白鳳娥, 姜曉榮, 牟匯慧. 無線傳感器網(wǎng)絡(luò)DV-Hop定位算法的研究[J]. 計算機與數(shù)字工程, 2010, 38(3):34-36

[3] 王汝傳, 孫力娟. 無線傳感器網(wǎng)絡(luò)技術(shù)及其應(yīng)用[M]. 北京:人民郵電出版社, 2011:74-76

[4] 孫利民, 李建中, 陳渝,等. 無線傳感器網(wǎng)絡(luò)[M]. 北京:清華大學出版社, 2005:140-142

[5] 彭力. 無線傳感器網(wǎng)絡(luò)技術(shù)[M]. 北京:冶金工業(yè)出版社, 2011:73-75

[6] 趙靈鍇, 洪志全. 基于無線傳感器網(wǎng)絡(luò)的DV-Hop定位算法的改進[J]. 計算機應(yīng)用, 2011, 31(5):1189-1192

[7] KENNEDY J, EBERHART R. Particle swarm optimization[C]. Proceedings of the IEEE International Conference on Neural Networks, 1995:1942-1948

[8] 陳星舟, 廖明宏, 林建華. 基于粒子群優(yōu)化的無線傳感器網(wǎng)絡(luò)節(jié)點定位改進[J]. 計算機應(yīng)用, 2010, 30(7):1736-1738

[9] 毛會瓊, 陳世海, 范建國, 等. 基于無線傳感器網(wǎng)絡(luò)的環(huán)境監(jiān)測系統(tǒng)的設(shè)計[J]. 工礦自動化, 2009(8):119-121

[10] 王曉樂, 徐家品. 基于粒子群優(yōu)化算法的WSNs節(jié)點定位研究[J]. 計算機應(yīng)用, 2009, 29(02):494-495

猜你喜歡
信標粒子無線
《無線互聯(lián)科技》征稿詞(2021)
無線追蹤3
基于ARM的無線WiFi插排的設(shè)計
電子制作(2018年23期)2018-12-26 01:01:08
基于粒子群優(yōu)化的橋式起重機模糊PID控制
RFID電子信標在車-地聯(lián)動控制系統(tǒng)中的應(yīng)用
基于粒子群優(yōu)化極點配置的空燃比輸出反饋控制
ADF7021-N在無線尋呼發(fā)射系統(tǒng)中的應(yīng)用
電子制作(2016年15期)2017-01-15 13:39:03
基于信標的多Agent系統(tǒng)的移動位置研究
無姿態(tài)補償?shù)乃滦艠私^對位置傳遞研究
水道港口(2015年1期)2015-02-06 01:25:45
基于Matlab的α粒子的散射實驗?zāi)M
物理與工程(2014年4期)2014-02-27 11:23:08
三穗县| 额济纳旗| 三亚市| 潮安县| 盱眙县| 合水县| 宾阳县| 监利县| 和田市| 潮安县| 龙州县| 林芝县| 东乌珠穆沁旗| 中方县| 曲水县| 拜城县| 祁连县| 土默特左旗| 文山县| 宜章县| 吉水县| 漳平市| 新民市| 台南市| 宕昌县| 丰都县| 建湖县| 蒙自县| 闽侯县| 合阳县| 宁德市| 灵寿县| 罗源县| 辉县市| 大荔县| 宽甸| 巴林右旗| 长垣县| 张家港市| 常熟市| 盐山县|