李云鵬

（沈陽工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院,沈陽 110870）

1 引言

無線傳感器網(wǎng)絡(luò)定位算法根據(jù)其定位原理可以分為兩類[1]:基于測距的（range-based）定位算法和非基于測距的（range-free）定位算法.基于測距的定位算法,先通過測距技術(shù)獲得節(jié)點之間的距離或角度信息,再使用三邊測量法、三角測量法或最大似然估計法等估算節(jié)點位置,主要算法有TOA[2],TDOA[3],AOA[4]以及RSSI算法[5].非基于測距的算法則無需測量節(jié)點間距離和角度等信息,而是利用節(jié)點間連通度及鄰居關(guān)系實現(xiàn)定位,主要算法有Centroid算法[6]、DV-HOP算法[7]、Amorphous算法[8]以及APIT算法[9].

2 APIT算法

基于測距的算法雖然可以取得精度較高的定位結(jié)果,但該類算法對節(jié)點硬件要求較高,并且需要產(chǎn)生大量的計算和通信開銷,不適合大規(guī)模應(yīng)用.非基于測距的算法在成本、功耗等方面具有明顯優(yōu)勢,對硬件要求也不高,精度足夠滿足大部分應(yīng)用場景,性價比較高.相對于其他非基于測距的算法,APIT算法具有較高的定位精度,以及通信開銷小等優(yōu)點,具有很強的適用性.

2.1 APIT算法原理

APIT算法原理如圖1所示,未知節(jié)點從它的通訊范圍內(nèi)所有的錨節(jié)點中任意選擇3個組成三角形,通過與其他錨節(jié)進(jìn)行節(jié)點信息交換對比來測試該未知節(jié)點是否在三角形中,重復(fù)此測試直到窮盡所有可取的三角形組合,計算包含未知節(jié)點的所有三角形的重疊區(qū)域,將重疊區(qū)域的質(zhì)心作為未知節(jié)點的估計位置[9].

圖1 APIT算法原理圖

APIT算法在尋找重疊區(qū)域時采用網(wǎng)格掃描法[10],即將定位區(qū)域平均分割成正方形網(wǎng)格并給每個網(wǎng)格一個計數(shù)器,若未知節(jié)點在三角形內(nèi)部,則三角形掃到的網(wǎng)格的計數(shù)器加1,反之則減1,最終將計數(shù)器數(shù)值最大的區(qū)域的質(zhì)心作為未知節(jié)點的估計位置.

2.2 APIT算法不足及分析

一方面,APIT算法雖然與其他非基于測距的算法相比定位精度較高,但仍有較大提高空間; 另一方面,APIT算法相比其他算法有著相對低覆蓋率,這也是APIT算法另一個研究重點.

APIT算法定位精度的不足,主要源于在網(wǎng)格掃描法.在網(wǎng)格掃描法中被三角形掃描到的區(qū)域無論大小,都同樣計數(shù)器加1,致使一大一小區(qū)域?qū)Y(jié)果的影響相同.此外,未知節(jié)點在三角形外時,存在被誤判在三角形內(nèi)的可能[11],從而使估計位置產(chǎn)生較大偏差,定位精度下降.

APIT算法定位覆蓋率的不足,主要源于其算法本身.APIT算法需要未知節(jié)點通訊范圍內(nèi)存在3個及以上錨節(jié)點才能進(jìn)行定位,然而在隨機分布的傳感器網(wǎng)絡(luò)中,錨節(jié)點可能在局部密度不足,致使未知節(jié)點通訊范圍內(nèi)錨節(jié)點不足3個,從而無法進(jìn)行定位,最終導(dǎo)致定位覆蓋率不足[12].

3 APIT與遺傳算法混合定位

由于上述兩點問題的存在,造成了APIT算法定位精度與定位覆蓋率的不足,為克服此問題,本文提出了一種APIT算法與遺傳算法混合定位算法.

3.1 三角形比較分割

針對APIT算法定位精度不足的問題,本算法在經(jīng)典APIT算法的網(wǎng)格掃描法部分,引入三角形比較分割[13]以提高精度.在△ABC內(nèi),并且邊BC>AC>AB,過A點作BC垂線于D,即可知∠CDP的大小,若∠CDP小于90°,則未知節(jié)點在△ACD內(nèi),反之,則在△ABD內(nèi),如圖2所示.

圖2 三角形比較分割原理圖

多次應(yīng)用此判斷,并將所在三角形最長與網(wǎng)格邊長比較,直至最長邊長度小于網(wǎng)格邊長,比較分割結(jié)束,具體過程如下:

（1）通過點A、B、C坐標(biāo)計算出點D坐標(biāo);

（2）通過RSSI計算出AP、BP、CP長度;

（3）利用余弦定理與距離公式可計算:

（4）若∠CDP小于90°,則未知節(jié)點在△ACD內(nèi),反之,則在△ABD內(nèi).

（5）將未知節(jié)點所在三角形邊長進(jìn)行排序,令最長邊為BC,最短邊為AB,第三邊為AC.若BC大于網(wǎng)格邊長,重復(fù)步驟（1）-（4）,反之,則結(jié)束分割.

3.2 遺傳算法定位

遺傳算法[14]是一種借鑒生物界自然選擇和自然遺傳機制的隨機搜索算法.作為一種優(yōu)化算法,遺傳算法不依賴于梯度信息,而是通過模擬自然進(jìn)化過程來搜索最優(yōu)解,具有很好的全局搜優(yōu)特性.遺傳算法不僅可拓展性高,便于與其他算法組合優(yōu)化,在數(shù)學(xué)上也易于實現(xiàn),其目標(biāo)函數(shù)的定義域可以為任意集合且不會受到連續(xù)可微的約束,這種特點使得遺傳算法非常適合求解定位問題[15].

針對APIT算法定位覆蓋率不足的問題,本算法引入遺傳算法對未知節(jié)點進(jìn)行定位[12],即當(dāng)未知節(jié)點通訊范圍內(nèi)錨節(jié)點個數(shù)為2時,在以兩個錨節(jié)點為圓心,以通訊范圍為半徑作圓,在兩圓相交處用遺傳算法求解未知節(jié)點,確定目標(biāo)函數(shù),使未知節(jié)點到錨節(jié)點的真實距離與測量距離的絕對誤差最小,將未知節(jié)點的求解轉(zhuǎn)換為求解有約束條件的二元二次方程.

其中,δ為設(shè)定的誤差閾值,其原理如圖3所示.

圖3 遺傳算法定位原理圖

遺傳算法定位具體過程如下:

（1）在兩圓相交的陰影區(qū)域內(nèi)隨機采集N個樣本作為初始種群,N個樣本的平均坐標(biāo)作為初始位置,根據(jù)適應(yīng)度函數(shù)Fi確定每個樣本 Ai的適應(yīng)度,并記錄最優(yōu)個體.

（2）將初始種群中任意一個個體替換為最優(yōu)個體,再兩兩隨機配對,按照一定概率進(jìn)行交叉操作產(chǎn)生新的個體.其中,隨機數(shù)α∈（0,1）.

（4）若達(dá)到預(yù)設(shè)最大迭代次數(shù),則輸出最優(yōu)解并結(jié)束,否則轉(zhuǎn)到步驟（2）.

本文最大迭代次數(shù)設(shè)置為40.

4 仿真及分析

4.1 實驗環(huán)境及參數(shù)設(shè)置

本次實驗使用Matlab 2016b對算法進(jìn)行仿真.在1000 m×1000 m的正方形區(qū)域內(nèi),隨機分布300個節(jié)點,其中60個為錨節(jié)點,240個為盲節(jié)點,節(jié)點通訊距離為200 m,由此組成一個無線傳感器網(wǎng)絡(luò)進(jìn)行定位仿真.遺傳算法部分,初始種群為400個,交叉概率為0.9,變異概率為0.02.

4.2 實驗結(jié)果及分析

圖4為本文算法在上述仿真環(huán)境下,實驗結(jié)果與迭代次數(shù)的關(guān)系.

圖4 實驗結(jié)果與迭代次數(shù)關(guān)系圖

由圖4可知,本文算法在迭代40次后,實驗誤差逐漸趨近于0,達(dá)到理想狀態(tài),以此確定遺傳算法結(jié)束條件為最大迭代次數(shù)40次,并將此條件應(yīng)用于后續(xù)仿真.

圖5、圖6分別為經(jīng)典APIT算法與本文算法節(jié)點分布圖.其中,紅色*表示錨節(jié)點的位置,藍(lán)色○表示未知節(jié)點的實際位置.分布圖將未知節(jié)點的實際位置與估計位置用線段相連,用線段的長短來體現(xiàn)未知節(jié)點的定位誤差,沒有用線段連接的黑色○為無法定位的節(jié)點.

圖5 APIT算法定位節(jié)點分布圖

圖6 本文算法定位節(jié)點分布圖

圖7、圖8分別為經(jīng)典APIT算法與本文算法仿真的誤差結(jié)果圖.在實驗中,未知節(jié)點實際位置與估計位置的歐氏距離與通訊半徑的比值被定義為誤差,無法定位的節(jié)點數(shù)量與未知節(jié)點總數(shù)量的比值被定義為盲點率.

圖7 APIT算法定位誤差圖

圖8 本文算法定位誤差圖

將兩種算法分別仿真100次,取平均值作為算法結(jié)果,經(jīng)典APIT算法的誤差為32.41%,盲點率為7.24%;本文提出的混合算法誤差為10.79%,盲點率2.37%.結(jié)果表明,本文提出的混合算法相較于經(jīng)典APIT算法定位精度提高21.62%,覆蓋率提高4.87%.

文獻(xiàn)[16]提出了一種基于改進(jìn)差分進(jìn)化的定位算法,即DEDV-Hop定位算法,文獻(xiàn)[9]提出了一種基于虛擬節(jié)點的定位算法,即EVN-APIT定位算法.圖9、圖10分別為在100 m×100 m區(qū)域內(nèi),總節(jié)點個數(shù)為100個,錨節(jié)點個數(shù)從5提升至40時,幾種算法的誤差對比圖與覆蓋率對比圖,對比結(jié)果顯示,本算法相較于所比較算法均有不同程度優(yōu)勢.

圖9 定位誤差對比圖

圖10 定位覆蓋率對比圖

5 結(jié)論與展望

本文提出一種基于APIT的無線傳感器網(wǎng)絡(luò)混合定位算法.算法分為兩個部分:當(dāng)盲節(jié)點通訊范圍內(nèi)錨節(jié)點數(shù)量大于等于3個時,通過用比較分割法優(yōu)化過的APIT算法定位; 當(dāng)盲節(jié)點通訊范圍內(nèi)錨節(jié)點數(shù)量等于2個時,通過遺傳算法進(jìn)行定位.仿真實驗結(jié)果驗證了算法的可行性與有效性,本文算法相較于APIT算法在定位精度與覆蓋率上均有不同程度提高.