鄭 凱，裘 君，童應(yīng)楠，虞 鋒

(1.江西理工大學(xué) 電氣工程與自動化學(xué)院，江西 贛州 341411；2.浙大寧波理工學(xué)院 信息科學(xué)與工程學(xué)院，浙江 寧波 315100；3.寧波瓦薩智能科技有限公司，浙江 寧波 315100)

0 引言

伴隨著智能制造時代的到來,基于室內(nèi)定位技術(shù)的服務(wù)深入到人們生活的方方面面。相較于傳統(tǒng)的無線技術(shù)如紅外線定位[1]、超聲波定位[2]、藍牙定位[3]、WiFi定位[4]、射頻識別技術(shù)[5]和Zigbee技術(shù)[6]等,超寬帶技術(shù)(Ultra-Wide Band, UWB)因其自身具有的高傳輸速率、高帶寬、低功耗和強抗干擾性的特性,被廣泛應(yīng)用在物流生產(chǎn)線、辦公室和居家等場景[7]。

基于UWB的定位技術(shù)分為時間參數(shù)和非時間參數(shù)2種:基于時間參數(shù)的定位技術(shù)有TOA[8]、TDOA[9];基于非時間參數(shù)的定位技術(shù)有AOA[10]、RSSI[11]?；跍y距的傳統(tǒng)定位算法利用TOA和TDOA測得相關(guān)距離信息,通過傳統(tǒng)的三邊測量法、極大似然估計法、Chan算法[12]和Taylor級數(shù)展開法[13]來估計待定位物體的坐標。

三邊測量算法原理簡單,測出基站到標簽的距離,以3個基站為圓心畫圓找到交點即為定位點,計算量小、計算速度快。實際情況下,由于測距的隨機誤差和非視距誤差的存在,作出的3個圓實際無法相交于一點[14],導(dǎo)致出現(xiàn)較大誤差。對比傳統(tǒng)的定位算法,智能優(yōu)化算法尋求在求解時間和求解速度上的平衡,但是不能保證最終結(jié)果是最優(yōu)解,有可能會陷入局部最優(yōu)解,因此將智能算法的改進應(yīng)用于室內(nèi)定位成為了當(dāng)今研究的熱點。如何改善部分智能算法的收斂速度和精度成為了值得關(guān)注的問題。

文獻[15]提出了基于該改進鴿群算法的無線傳感器網(wǎng)絡(luò)定位方法,在鴿群算法中引入自適應(yīng)調(diào)整機制,在種群分組過程中融入隨機游走機制,使定位算法具有較高的定位精度和較快的收斂速度。劉雙等[16]提出了一種基于黃金正弦與Sigmoid連續(xù)化海鷗優(yōu)化算法,提高了算法的尋優(yōu)能力和后期收斂速度。將基于RSSI的定位精度大幅度提升。田洪舟等[17]提出了一種改進樽海鞘算法的優(yōu)化DV-Hop算法,在種群初始化時利用混沌映射,更新追隨者位置引入精英,同時采用淘汰者個體產(chǎn)生較優(yōu)個體,使得該算法比傳統(tǒng)DV-Hop算法及其他算法具有更好的定位能力。

本文提出了利用自適應(yīng)調(diào)整測距值的改進蛇優(yōu)化(Snake Optimization,SO)算法來提升非視距誤差所帶來的定位誤差。首先對基站測得的測距值進行自適應(yīng)調(diào)整。將測距得到的值代入用于SO算法的適應(yīng)度函數(shù)。對SO算法初始化種群初期引入sine混沌映射,提高種群的分布的均勻性。在雌性個體和雄性個性位置更新以后對其更新位置進行正弦余弦算法(Sine and Cosine Algorithm, SCA)優(yōu)化,提高算法收斂速度。實驗結(jié)果表明,相較于傳統(tǒng)算法和傳統(tǒng)智能優(yōu)化算法,改進算法具有較高的定位精度和收斂效率。

1 傳統(tǒng)室內(nèi)定位方法與改進

1.1 傳統(tǒng)三邊測量算法

三邊測量法是一種先測得3個參考基站和待定位標簽之間的距離,再通過幾何學(xué)方法計算標簽位置的方法。

三邊測量法實現(xiàn)簡單但是總體來說定位精度不高。測距本身存在隨機誤差;非視距誤差的影響,會造成該算法誤差變大。提高測距精度會加大成本 ,需要增加基站數(shù)量,雖然能在一定程度上減小誤差[17],但最終效果有限。

1.2 自適應(yīng)改進測距值法

三邊測量算法原理簡單、實現(xiàn)快速,但是由于非視距誤差的存在,導(dǎo)致以基站為圓心的圓無法相交于一個點上,出現(xiàn)圓相交的區(qū)域過大的現(xiàn)象,如圖1所示。為解決上述情況,本文引入一種自適應(yīng)三邊定位測距值修正方法[18],并對其修改,能夠有效縮小相交區(qū)域。

圖1 實際相交區(qū)域過大Fig.1 Too large for actual intersection area

(1)選擇基站

因非視距誤差因素的影響,基站誤差有大有小。室內(nèi)設(shè)置3個基站,每次選3個基站,按序號選出不平行的n組,先根據(jù)標簽的位置找出3個測量距離移動標簽距離誤差最小的基站,再對選出的基站進行自適應(yīng)調(diào)整。

(2)進行自適應(yīng)調(diào)整算法

每組選出的3個基站,作為三邊測量法的基站。設(shè)置基站圓交點間距離的上限,對圖1中的測量距離進行自適應(yīng)調(diào)整。

① 算出基站與基站間的距離,得到基站B1與基站B2之間距離d12,同理計算出基站1和基站3間距離d13以及d23;

② 判斷2基站為圓心的圓之間的位置:若(ra1+ra2)≥d12,則表明基站1和基站2作的圓為相切或是相交;如果(ra1+ra2)

③ 判斷基站為圓心的圓的位置關(guān)系:若2圓相交,求出2圓交點,然后得到第3個圓的圓心到2個交點之間的距離,將最小的距離保留下來記作r。若半徑ra3>r,那么3個圓之間存在公共區(qū)域,即3圓有相交區(qū)域;

④ 根據(jù)判斷系數(shù)來判斷2圓位置,若B1和B2中的(ra1+ra2)/d12>1.2,則這2個基站之間的距離遠大于實際測距值,需要調(diào)整。同時,對比圓B1和B3中(ra1+ra3)/d13以及B2和B3中(ra2+ra3)/d23。選取比值較大的2個圓的半徑調(diào)整,選出2個圓中距離差較大的那個圓的半徑進行修正。在第一次調(diào)整之后,計算出2個圓之間交點距離,判斷是否小于交點間距的0.9倍,如果小于此數(shù)值,則停止遞推;否則繼續(xù)進行調(diào)整,直到交點距離小于目標距離差。

2 SO算法的應(yīng)用

2.1 原始SO算法

受啟發(fā)于蛇奇特的交配行為, 2022年Fatma A和Hussien A G提出了SO算法[19]。

蛇的雄性和雌性交配行為的發(fā)生受到某些因素的影響。若是氣溫低、食物充足,那么蛇發(fā)生交配行為;否則蛇只會去尋找食物或者吃已有的食物?；诖薙O的搜索過程分為2個階段:探索和開發(fā)。蛇種群在搜索空間隨機初始化以后,會被平分為雄性和雌性2組。雄性和雌性的數(shù)量分別表示為:

(1)

Nf=N-Nm,

(2)

式中:N為種群總數(shù),Nm為雄性個體,Nf為雌性個體。從每組中找出最好個體然后得到最佳雄性和最佳雌性以及食物的位置,分別記為fbest,m,fbest,f和ffood。溫度定義如下:

(3)

式中:t為當(dāng)前迭代次數(shù),T為最大迭代次數(shù)。食物數(shù)量定義為:

(4)

式中:c1為常數(shù),取0.5。

探索階段描述了寒冷地區(qū)環(huán)境因素和食物,此時蛇不會在周圍尋找食物。如果Q

Xi,m(f)(t+1)=Xrand,m(f)(t)±c2×Am(f)×

((Xmax-Xmin)×rand)+Xmin,

(5)

式中:Xi,m(f)表示雄性或是雌性個體,rand是[0,1]的隨機數(shù),c2取0.05,Am(f)是雄性或是雌性尋找食物的能力。

(6)

式中:frand,m(f)為隨機選擇的雄雌個體位置Xrand,m(f)的適應(yīng)度值,fi,m(f)為雌雄種群中第i個個體位置Xi,m(f)的適應(yīng)度值。

開發(fā)階段時有食物,即Q>Threshold。若temperature>Threshold(Threshold=0.6),氣溫高,只會尋找食物,位置更新公式為:

Xi,j(t+1)=Xfood±c3×Temp×rand×

(Xfood-Xi,j(t)),

(7)

式中:Xi,j(t)為個體位置,Xfood為蛇個體的最佳位置,c3取2。

若temperature

戰(zhàn)斗模式下的位置更新公式:

Xi,m(f)(t+1)=Xi,m(f)(t)±c3×FM(F)×rand×

(Q×Xbest,f(m)-Xi,m(f)(t)),

(8)

式中:Xbest,f(m)為雌(雄)組最佳位置,FM(F)為雄性或雌性戰(zhàn)斗能力。

(9)

式中:fbest,f(m)為雌雄最佳個體的適應(yīng)度值,fi為當(dāng)前蛇個體的適應(yīng)度值。

交配模式下僅需將Xbest,f(m)換成Xi,f(m)即第i個雌性或雄性個體的位置,FM(F)替換為Mm(f),表示雄性和雌性的交配能力,計算如下:

(10)

若蛇卵孵化,選擇適應(yīng)度最差的雄性和雌性替換它們的位置,表示為:

Xworst,m(f)=Xmin+rand×(Xmax-Xmin)。

(11)

2.2 改進SO算法

2.2.1 改進sine混沌映射種群初始化

通常群體智能算法使用隨機方法產(chǎn)生初始種群,但此種方式可能會使個體位置分布不均,從而導(dǎo)致部分個體遠離較優(yōu)位置。

混沌現(xiàn)象是指確定的宏觀非線性系統(tǒng)在一定條件下呈現(xiàn)的不可預(yù)測隨機現(xiàn)象,其對初始值異常敏感,即初始情況下任意的微小變動都會造成之后的非線性變化?；煦缧蛄幸蚱浔闅v性、隨機性和不確定性能夠產(chǎn)生分布更加均勻的種群個體,提高算法的尋優(yōu)能力。

原始sine混沌映射產(chǎn)生的一維序列在相空間中分布并不均勻,處于混沌狀態(tài)的參數(shù)空間相對較窄,基于此,文獻[20]提出了一種改進的sine映射方法,用2個控制參數(shù)來計算序列數(shù),其混沌特性要好于原始的sine混沌映射序列,如下所示:

(12)

將改進的sine映射應(yīng)用到SO算法的種群初始化中,首先產(chǎn)生混沌映射初始迭代點:

X(1)=lb+rand×(ub-lb)。

(13)

根據(jù)目標優(yōu)化問題的具體條件,將式(12)改寫為:

(14)

式中:ub、lb分別為變量的上界和下界,rand為隨機生成的0～1的隨機數(shù),di、ei為控制參數(shù),wi+1為迭代序列值即為蛇種群中的位置。

對改進后的sine混沌映射進行模擬仿真,得到在不同μ值下的混沌映射分布,如圖2所示。

(a)Sine混沌分布 μ=0.99

(b)改進的sine混沌分布 μ=0.99

原始的sine混沌映射在μ=0.99已經(jīng)進入了混沌狀態(tài),但是本文改進的sine混沌映射在μ相同時的分布狀態(tài)明顯要比初始sine混沌映射更加均勻,遍歷性更好,有利于蛇種群初期的種群初始化。

2.2.2 改進SCA優(yōu)化

2016年Mirjalili[21]提出了一種基于正弦余弦的新型元啟發(fā)式優(yōu)化算法,基于正余弦函數(shù)的性質(zhì),通過改變正余弦函數(shù)的振幅使初始隨機候選值朝最佳值內(nèi)外波動,來平衡算法的局部和全局尋優(yōu)能力。

在隨機產(chǎn)生初始化個體后,先計算各個體的適應(yīng)度值,找出最優(yōu)位置和最佳適應(yīng)度值。個體位置更新公式為:

(15)

式中:D=r3×X*-X(t),t為當(dāng)前迭代次數(shù),X*為上一輪更新的最優(yōu)解,r2～r4均為隨機數(shù),r2∈[0,2π],r3∈[0,2],r4∈[0,1],r1為線性遞減的控制參數(shù),它可以提供更大更廣的搜索空間。

(16)

式中:a為常數(shù),取2;tmax為最大迭代次數(shù)。

傳統(tǒng)SCA算法中,參數(shù)的設(shè)置過于簡單,如r1僅為一條截距為2的線性直線,對算法的探索和開發(fā)階段過渡效果有限,算法可能會提早陷入局部最優(yōu)解,所以對r1進行改進[22]:

(17)

利用正弦函數(shù)的性質(zhì),使控制參數(shù)r1局部震蕩,能夠進一步平衡尋優(yōu)能力。

為更加全面地利用個體位置信息,使個體當(dāng)前的位置對新位置的影響權(quán)重產(chǎn)生變化,添加動態(tài)的權(quán)重系數(shù)β為:

(18)

式中:b為優(yōu)化因子,服從參數(shù)為λ的指數(shù)分布,即b～E(λ),將λ設(shè)置為雄性或是雌性的蛇種群數(shù)N/2。迭代初期,β下降較為緩慢,此時個體位置對算法的干預(yù)有較大影響,以便全局搜索。后期β下降以減小個體的影響力,此時充分進行局部開發(fā),個體更新的公式為:

(19)

改進后的SCA作為蛇算法雌性雄性位置更新后的補充,得到新的更新過的位置,提升算法的尋優(yōu)能力。

2.2.3 結(jié)合自適應(yīng)測距值的SO算法

自適應(yīng)調(diào)整后的測距值作為改進SO算法的適應(yīng)度函數(shù)的參數(shù),設(shè)置適應(yīng)度函數(shù):

(20)

式中:xi、yi分別為每個基站的橫縱坐標,x、y分別為每個蛇個體的坐標,di為每個基站到標簽的距離,這里使用自適應(yīng)調(diào)整過的測距值。

2.2.4 改進SO算法的算法流程

綜上所述,本文提出基于UWB信號的改進SO算法室內(nèi)定位過程如圖3所示。

圖3 算法流程Fig.3 Flowchart of the algorithm

步驟1: 獲取基站到標簽的距離值,根據(jù)自適應(yīng)規(guī)則調(diào)整測距值,使3圓相交區(qū)域盡可能小。

步驟2: 設(shè)置蛇種群數(shù)量、最大迭代次數(shù),根據(jù)優(yōu)化的sine混沌映射初始化蛇的種群。

步驟3: 根據(jù)式(1)、式(2)將種群分為雄性與雌性2組,設(shè)置適應(yīng)度函數(shù),并計算相應(yīng)的適應(yīng)度,找當(dāng)前最佳雌雄個體。

步驟4: 根據(jù)式(3)、式(4)定義環(huán)境溫度Temp和食物數(shù)量Q。

步驟5:根據(jù)食物量Q的多少來判斷只尋找食物或戰(zhàn)斗和交配。如果Q<0.25,則尋找食物,根據(jù)式(5)更新蛇個體的位置。

步驟6: 若食物充足,Temp>0.6,只尋找食物和吃現(xiàn)有食物,根據(jù)式(7)更新位置。

步驟7: 根據(jù)模式隨機數(shù)rand判斷進入戰(zhàn)斗模式和交配模式,根據(jù)式(8)更新戰(zhàn)斗模式位置,用式(10)替換戰(zhàn)斗模式下的Am,將最佳個體替換成當(dāng)前個體,更新位置。如果卵孵化,選出最差個體,替換掉它們。

步驟8:處理更新后的位置,更新個體歷史最佳值。

步驟9: 根據(jù)式(19)改進的SCA對位置再次更新。

步驟10:更新個體歷史最佳值。

步驟11:再次更新全局最佳適應(yīng)度,更新食物位置。

步驟12:判斷是否達到迭代次數(shù),不滿足進入下一輪迭代;滿足則結(jié)束迭代并輸出最佳位置。

3 實驗與結(jié)果分析

本文采用將上述自適應(yīng)調(diào)整策略對測距值進行調(diào)整,再與采用了sine混沌映射和正余弦優(yōu)化的SO算法進行結(jié)合的方法,對待定物體的室內(nèi)位置進行計算。將基于自適應(yīng)調(diào)整測距值的MSSCASO(Modified Sine Mapping Sine Cosine Snake Optimization)定位算法分別與基于最小二乘法(LSM)的定位算法、基于Chan算法的定位算法和基于引入本文自適應(yīng)調(diào)整策略的Chan算法做比較。

3.1 室內(nèi)平面實驗

本文在實驗室下分別安置5個基站作為參考節(jié)點,基站所擺放的位置分別為(0,0)、 (2.525,0)、 (5.62,0)、(5.46,5.625)和 (0,5.625),高度為1.205 m的平面內(nèi)。標簽作為待測點,選取多個點放置,先進行距離測量再進行坐標解算。選取點和參考基站位置如圖4所示。

圖4 實驗室基站分布情況Fig.4 Distribution of lab bases

對每個待測定位點進行500次采樣,并對每個點的測距采樣結(jié)果取平均值。將測距值代入LSM、Chan法、改進后的Chan算法、原始SO算法以及本文算法進行對比。

圖5為每個待測點在改進的SO算法下的估計位置。圖6為8個目標點的各算法誤差對比。

圖5 待測點在改進SO算法下的估計位置Fig.5 Estimated positions of test points under improved SO algorithm

圖6 各算法的多點歐氏距離誤差Fig.6 Multiple-point Euclidean distance error for each algorithm

由圖6的歐氏距離誤差對比狀況來看,LSM的誤差位于最上方,最大的誤差接近0.4 m。基于3基站的Chan算法與LMS差距不大,基本重合。加入了自適應(yīng)調(diào)整策略的Chan算法精度有一定的提升。SO算法精度要好于前3種,基本徘徊在0.1～0.15 m。改進SO算法下的預(yù)測誤差線基本在0.1 m的位置以下,并且誤差線較為平穩(wěn),算法穩(wěn)定性好。

表1記錄了所有點在不同算法下的不同坐標軸方向上以及歐氏距離誤差,以及所有點的均方根誤差(Root Mean Squared Error,RMSE)。

表1 各點在不同算法下的誤差數(shù)據(jù)

從表1可以看到,LSM、Chan算法和改進Chan算法在X軸上的平均誤差在0.1 m左右。從Y軸上的平均誤差來看,修正Chan算法和本文算法最小分別為0.098 m和0.033 m,LSM最大達到 0.127 m。從歐式距離誤差來看,LSM和Chan算法平均為0.217 m,改進的Chan算法平均歐氏距離誤差為0.176 m,因為經(jīng)過自適應(yīng)調(diào)整策略和后,該算法在一定程度上消除了非視距因素帶來的影響。改進后的SO算法的平均誤差最小,為0.074 m。從歐式距離誤差和RMSE觀察,LSM和Chan算法的穩(wěn)定性最差,SO算法和本文MSSCASO算法穩(wěn)定性較好,分別為0.128 m和0.078 m。綜上所述,改進的SO定位算法,定位精度高、穩(wěn)定性高,滿足室內(nèi)定位的需求。

3.2 收斂速度分析

分別使用PSO、MPSO、SO 以及本文算法MSSCASO進行400次迭代。如圖7所示,基于PSO和MPSO的定位算法在100次迭代前下降速度快,之后緩緩下降逐步接近最低適應(yīng)值,MPSO對PSO算法的慣性權(quán)重ω進行線性化處理,提高了PSO算法初期的全局搜索能力和后期的局部收斂能力。相比基于PSO算法的定位算法,基于SO算法的定位算法在初始適應(yīng)度值上就要小得多,這得益于SO算法的種群初始化分布較為均勻。在前10次迭代,基于SO算法和MSSCASO算法的適應(yīng)度值就已經(jīng)快速下降。相比原始的SO算法,改進的SO算法初始適應(yīng)度值更小,這是因為經(jīng)過優(yōu)化的sine混沌映射,使得初始化的蛇種群分布更加均勻?？梢钥吹?改進SO算法中引入了改進的SCA,提高了算法的局部尋優(yōu)能力,所以改進SO算法的迭代曲線始終位于初始SO算法的下方,提升了收斂性能。

圖7 算法效率Fig.7 The efficiency of algorithms

3.3 室內(nèi)立體定位實驗

在平面實驗的基礎(chǔ)上,將個別基站移至不同平面,使得各基站形成三維立體空間。基站的位置設(shè)置為(0,0,1.205)、(2.525,0,2.5)、 (5.62,0,1.205)、 (5.46,5.625,2.5)和 (0,5.625,1,205)。將基于改進SO算法的UWB室內(nèi)定位算法與基于LSM、基于PSO算法的室內(nèi)定位算法進行對比。

首先通過UWB傳感器測距,進行500次距離值采樣,對測距值取平均值,分別將得到的測距值代入LSM、PSO、SO算法以及本文的改進SO算法。將預(yù)測點與實際點的直線距離差作為定位誤差進行對比,如圖8～圖11所示。

圖8 基于LSM算法的定位結(jié)果Fig.8 Positioning results based on LSM algorithm

圖9 基于PSO算法的定位結(jié)果Fig.9 Positioning results based on PSO algorithm

圖10 基于SO算法的定位結(jié)果Fig.10 Positioning results based on SO algorithm

圖11 基于MSSCASO算法的定位結(jié)果Fig.11 Positioning results based on MSSCASO algorithm

表2列出了各算法下待定位標簽的估計歐氏距離差,基于LSM算法的UWB室內(nèi)定位,定位誤差達到了0.314 m,定位誤差較大,因為室內(nèi)環(huán)境較為復(fù)雜,非視距干擾多,對定位結(jié)果造成較大的干擾。基于PSO算法的定位結(jié)果,定位誤差為0.176 m?；谠糞O算法和基于改進SO算法的定位結(jié)果的歐氏誤差分別為0.148 m和0.118 m。后3種智能優(yōu)化算法相較于LSM明顯較高。基于SO和改進SO的定位算法相較于PSO算法,收斂速度更快、全局尋優(yōu)能力更強、定位精度更高。基于改進的SO定位算法在SO算法的基礎(chǔ)上對初始化種群過程進行混沌化,提高了初始種群分布的均勻性,更有利于全局尋優(yōu)。位置更新的過程中進行改進的SCA,提升了算法的尋優(yōu)能力。相較于基于PSO的定位算法和基于SO的定位算法,改進后的SO算法定位精度分別提高了32.95%和20.27%。

表2 立體定位下各算法的歐氏誤差

4 結(jié)束語

本文提出了基于MSSCASO算法的UWB室內(nèi)定位算法。在多點定位的二維平面定位實驗中,本文引入了一種自適應(yīng)的測距值修正法,并將修正后的測距值代入了改進的SO算法,定位精度良好,該算法的平均定位歐氏距離誤差為0.074 m,定位穩(wěn)定性好,RMSE為0.078 m。在單點的室內(nèi)立體定位算法中,LSM、PSO和SO算法的歐氏距離定位誤差分別為0.314、 0.176、0.148 m,本文提出的改進SO算法MSSCASO定位精度更高,為0.119 m,滿足室內(nèi)立體定位精度要求,驗證了相對于SO算法,引入改進的sine混沌映射和正余弦優(yōu)化算法,能夠有效改善優(yōu)化算法的局部與全局尋優(yōu)能力。