李 鵬
(長江大學 計算機科學學院,湖北 荊州 434023)
無線傳感器網(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é)點的位置更精確。
在傳感器網(wǎng)絡(luò)節(jié)點定位中,節(jié)點分為信標節(jié)點和未知節(jié)點,信標節(jié)點是未知節(jié)點的參考點,信標節(jié)點數(shù)量比未知節(jié)點要少,信標節(jié)點可通過GPS定位裝置來確定自己的準確位置,而未知節(jié)點通過和鄰近的信標節(jié)點或者是已經(jīng)確定位置的未知節(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)
無線傳感器網(wǎng)絡(luò)定位系統(tǒng)算法很多,常用的衡量定位能力的標準有定位精度,定位精度是指定位系統(tǒng)提供的位置信息的精確程度,是評價定位能力的最關(guān)鍵的標準,精度越高,技術(shù)要求也越高。除此之外,還有覆蓋范圍、信標節(jié)點密度、節(jié)點密度、容錯性和魯棒性以及功耗等。
基于距離的定位機制(Range-based)分為3個階段:第1階段為測距階段;第2階段為定位階段;第3階段是修正階段,對第2階段計算得到的未知節(jié)點的坐標精確化,減少誤差。基于距離的定位算法通常有:基于接收信號強度指示算法RSSI、到達時間方法TOA、到達時間差方法TDOA、到達角度方法AOA等。
基于距離的定位算法可以精確定位未知節(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é)點的位置也更精確,定位效果良好。
粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法是模擬鳥類捕食行為的群體智能算法,由美國電氣工程師Eberhart和社會心理學家Kennedy于1995年提出[7]。粒子群優(yōu)化算法是一種全局優(yōu)化算法,源于對鳥群群體運動行為的研究。PSO算法容易實現(xiàn),要調(diào)整的參數(shù)少,廣泛應(yīng)用于各種領(lǐng)域。
粒子群優(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)解。
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é)點自身的位置。
本文使用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%左右。
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