李云鵬

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

1 引言

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

2 APIT算法

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

2.1 APIT算法原理

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

圖1 APIT算法原理圖

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

2.2 APIT算法不足及分析

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

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

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

3 APIT與遺傳算法混合定位

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

3.1 三角形比較分割

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

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

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

（1）通過(guò)點(diǎn)A、B、C坐標(biāo)計(jì)算出點(diǎn)D坐標(biāo);

（2）通過(guò)RSSI計(jì)算出AP、BP、CP長(zhǎng)度;

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

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

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

3.2 遺傳算法定位

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

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

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

圖3 遺傳算法定位原理圖

遺傳算法定位具體過(guò)程如下:

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

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

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

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

4 仿真及分析

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

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

4.2 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

圖7 APIT算法定位誤差圖

圖8 本文算法定位誤差圖

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

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

圖9 定位誤差對(duì)比圖

圖10 定位覆蓋率對(duì)比圖

5 結(jié)論與展望

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