摘 要：為了克服煤礦井下復(fù)雜環(huán)境對超寬帶（UWB）定位系統(tǒng)基站布設(shè)的影響，本研究引入了一種創(chuàng)新的自然啟發(fā)式元啟發(fā)算法——星鴉優(yōu)化算法（NOA），旨在優(yōu)化UWB定位系統(tǒng)的基站布局。本文以UWB基站布設(shè)的區(qū)域覆蓋率作為優(yōu)化的目標(biāo)函數(shù)，并通過NOA的迭代過程，尋求最優(yōu)的基站布局方案。仿真試驗表明，NOA的收斂精度和收斂速度很高。研究結(jié)果表明，NOA在井下復(fù)雜環(huán)境中的UWB定位系統(tǒng)中的應(yīng)用潛力很大，為進(jìn)一步測試實際環(huán)境和算法優(yōu)化提供了理論基礎(chǔ)和實踐指導(dǎo)。

關(guān)鍵詞：UWB定位技術(shù)；星鴉優(yōu)化算法；基站布設(shè)；煤礦井下；區(qū)域覆蓋率

中圖分類號：TN 914" " " " " 文獻(xiàn)標(biāo)志碼：A

隨著國家對煤礦安全和智能化建設(shè)的重視，煤礦井下定位系統(tǒng)面臨新挑戰(zhàn)，須在復(fù)雜的電磁干擾、多徑和陰影效應(yīng)環(huán)境中實現(xiàn)高準(zhǔn)確性和高時效性定位[1]。傳統(tǒng)的射頻識別（RFID）、Wi-Fi、紫蜂無線通信網(wǎng)絡(luò)（ZigBee）和藍(lán)牙等技術(shù)在適應(yīng)性、抗干擾性和傳輸距離等方面存在不足，難以滿足高精度需求。超寬帶（Ultra Wide Band，UWB）技術(shù)以其優(yōu)越的抗干擾性和穿透能力，能夠在井下復(fù)雜環(huán)境中進(jìn)行高精度定位。然而，井下環(huán)境的復(fù)雜性對定位系統(tǒng)的設(shè)計和實施提出了挑戰(zhàn)，特別是在基站布設(shè)優(yōu)化方面。在煤礦井下環(huán)境中，布設(shè)UWB基站對定位精度有顯著影響[2]?；静荚O(shè)不當(dāng)會導(dǎo)致定位誤差增大，影響救援和監(jiān)測工作的效果。因此，研究和開發(fā)一種高效的基站布設(shè)優(yōu)化方法十分重要。本文提出了一種新型基站布設(shè)優(yōu)化方法，將星鴉優(yōu)化算法（Nutcracker Optimization Algorithm，NOA）應(yīng)用于煤礦井下UWB定位系統(tǒng)。NOA是一種自然啟發(fā)式元啟發(fā)算法，其靈感來自克拉克的星鴉尋找食物的行為模式。本文利用NOA解決井下環(huán)境中的UWB基站布設(shè)問題，提高定位系統(tǒng)的精度和覆蓋效率。

1 超寬帶定位技術(shù)

1.1 UWB技術(shù)的基本原理

UWB技術(shù)是一種使用極寬頻帶傳輸電磁波的通信方式。UWB的主要特點是其頻帶寬度通常超過500 MHz，載波中心頻率gt;2.5 GHz。這種特點賦予UWB多個優(yōu)勢，例如數(shù)據(jù)傳輸率高、功耗低以及穿透能力良好。UWB定位技術(shù)主要根據(jù)電磁信號的時間延遲測量來確定目標(biāo)位置。與傳統(tǒng)的窄帶信號相比，UWB信號脈沖寬度短，時間分辨率高，定位系統(tǒng)精度更高。

1.2 UWB定位算法

到達(dá)時間差（Time Difference of Arrival， TDOA）是一種廣泛應(yīng)用于UWB定位系統(tǒng)的方法。TDOA基于從不同基站接收的信號時間差來確定目標(biāo)位置。具體來說，至少需要3個基站來形成一個TDOA定位系統(tǒng)。每個基站測量信號到達(dá)時間，并將這些信息發(fā)送至中央處理器，如圖1所示。圖1有3個基站，基站一作為基準(zhǔn)基站且已知3個基站的坐標(biāo)位置，（x1，y1）、（x2，y2）和（x3，y3）分別為基站一、基站二、基站三的位置坐標(biāo)；（x，y）為所求標(biāo)簽點的未知位置坐標(biāo)。計算信號從目標(biāo)到達(dá)每個基站的時間差，再根據(jù)距離差構(gòu)建雙曲線方程，如公式（1）、公式（2）所示。

（1）

（2）

式中：di為標(biāo)簽與第i個基站的距離，i=1，2，3，...，n；D21為標(biāo)簽到第二個參考基站與基站一之間的距離差值；D31為標(biāo)簽到第三個參考基站與基站一之間的距離差值；T1、T2和T3分別為標(biāo)簽的電磁波信號到達(dá)基站一、基站二和基站三的參考時間；c為電磁波的傳播速度。利用Chan算法求解該非線性方程組就可以得到標(biāo)簽坐標(biāo)位置（x，y）的數(shù)值。

1.3 煤礦井下環(huán)境對定位系統(tǒng)的影響

煤礦井下環(huán)境給UWB系統(tǒng)帶來了多重挑戰(zhàn)。井下封閉空間以及物理障礙（例如巖石、煤層和支撐結(jié)構(gòu)）導(dǎo)致信號反射和衰減，影響定位精度。UWB信號具有高頻特性，盡管UWB的高時間分辨率有助于抵抗多徑干擾，但是井下環(huán)境的顯著多徑效應(yīng)（反射、衍射和散射）影響了定位精度，井下電氣設(shè)備產(chǎn)生的電磁噪聲也可能干擾UWB信號。因此，UWB技術(shù)理論上適用于井下定位，其實際應(yīng)用須考慮這些井下特有因素。在UWB定位系統(tǒng)的設(shè)計中，優(yōu)化基站布設(shè)和信號處理至關(guān)重要，以保證其在特殊環(huán)境下的性能。

2 NOA算法

2.1 算法描述

NOA是由Mohamed Abdel-Basset 等[3]在2023年提出的一種新型的自然啟發(fā)式元啟發(fā)算法，其靈感來自克拉克星鴉的行為模式。克拉克星鴉以其獨特的食物尋找和儲藏策略而聞名。這種策略包括在廣闊區(qū)域內(nèi)尋找食物并將其儲存于地面不同的位置，以備不時之需。NOA將這種行為模式抽象化并應(yīng)用于解決復(fù)雜的優(yōu)化問題。

NOA的核心思想是通過模擬星鴉在不同季節(jié)的行為來尋找全局最優(yōu)解。在夏季和秋季，星鴉將食物儲藏于不同地點，這相當(dāng)于在解空間中探索多個潛在的解決方案。在冬季和春季，星鴉通過回憶以前儲藏食物的地點來尋找食物，這相當(dāng)于在已探索的解空間中尋找最優(yōu)解。

2.2 算法設(shè)計

在NOA中，筆者基于上述2個主要行為來模擬星鴉的行為，主要包括以下2種策略。1）覓食和儲存策略（Foraging and storage strategy）。2）緩存搜索和找回策略（Cache-search and recovery strategy）。在2種策略中，星鴉種群均存在勘探（Exploration）和開發(fā)（Exploitation）行為，即每種策略又包括2種不同的種群行為。

2.2.1 種群初始化

與大部分智能優(yōu)化算法一樣，NOA的種群初始化也是在問題的搜索空間中隨機產(chǎn)生星鴉個體。假設(shè)種群規(guī)模為 N，問題維度為 D，那么初始化過程如公式（3）所示。

=（-）·+ （3）

式中：為第t代星鴉個體的第j維變量；i為基站個數(shù)，i=1，2，…，N；j為像素點個數(shù)，j=1，2，…，D；、分別為第j維變量的上界和下界；為[0，1]的隨機向量。

2.2.2 覓食和儲存策略

一群星鴉尋找食物的儲存空間，以松樹種子為代表，星鴉將發(fā)現(xiàn)的松樹種子儲存在適當(dāng)?shù)馁A藏處，該機制可分為覓食和儲存2個主要階段。

第一階段勘探，如公式（4）、公式（5）所示。

（4）

（5）

第一階段開發(fā)，如公式（6）所示。

（6）

式中：為第t次迭代的一個新位置；為第t+1代第i個星鴉個體的最新位置；Xt i，j為第t代第i個星鴉個體的第j個位置；Xt m，j為當(dāng)前種群在第t次迭代中所有解的第j維均值；Xt A，j、Xt B，j和Xt C，j為從種群中隨機選擇的3個不同的星鴉個體，作為指標(biāo)探索高質(zhì)量的食物來源；Lj、Uj為第j維的上界和下界；γ為根據(jù)Levy飛行函數(shù)生成的隨機數(shù)；為當(dāng)前種群的最優(yōu)個體，、為從種群中隨機選擇的2個不同的星鴉個體；τ1、τ2和τ3，r1、r2和r3均為[0.1]的隨機數(shù)；τ4為一個服從正態(tài)分布的隨機數(shù)；τ5為一個Levy飛行函數(shù)生成的隨機數(shù)；μ為基于τ3、τ4和τ5生成的數(shù)；Tmax為最大迭代次數(shù)；t為當(dāng)前迭代次數(shù)；δ設(shè)為0.05；l為從1線性減至0的衰減因子，以提升算法的多樣性。

覓食與儲存策略的計算流程如圖2所示。

2.2.3 緩存搜索和找回策略

當(dāng)冬天來臨時，星鴉從覓食和貯藏模式轉(zhuǎn)變?yōu)樗褜ず突厥漳Ｊ?，開始尋覓它們之前儲存的食物。這個階段稱為第二次探索。星鴉使用空間記憶策略來定位它們的貯藏物。基于星鴉個體的 2 個參考點（Reference Points，RPs）進(jìn)行緩存搜索和找回策略。為了記住儲存食物的位置，星鴉選擇了2個參考點。2個參考點的計算過程如公式（7）～公式（10）所示。

（7）

（8）

（9）

（10）

式中：為當(dāng)前代t中第i個星鴉的第一個緩存參考點；為當(dāng)前代t中第i個星鴉的第二個緩存參考點；RP為一個隨機位位置；Prp為概率，其作用是確定在搜索空間內(nèi)全局探索其他區(qū)域的百分比；為優(yōu)化問題中第二維的上界；、分別為所求解參數(shù)的的上界和下界；θ為[0，π]的隨機弧度；為[0，1]的隨機向量；α為保證NOA定期收斂所確定的值。

最開始的參考位置可以根據(jù)公式（3）得到。如果星鴉不能找到第一個參考點RPti，1儲存的食物，那么它將通過第二個參考點RPti，2識別它。第一個參考點是通過更新相鄰區(qū)域內(nèi)的當(dāng)前位置來找到星鴉周圍隱藏的緩存來生成的，第二個參考點是通過在問題的搜索空間內(nèi)更新當(dāng)前解決方案來生成的，以幫助星鴉搜索儲藏的食物。

第二階段勘探，如公式（11）～公式（13）所示。

（11）

（12）

（13）

式中：Xt+1 i，j為第t+1代第i個星鴉個體的第j個位置；Xt best，t為第t次迭代中第j維的最佳位置；Xj c，t為從種群中隨機選擇的星鴉個體位置；Eq·（11）為記住了食物隱藏存儲位置的星鴉個體，返回公式（11）繼續(xù)迭代；Eq·（12）為沒有記住食物隱藏存儲位置的星鴉個體，返回公式（12）繼續(xù)迭代。

第二階段開發(fā)，如公式（14）～公式（16）所示。

（14）

（15）

（16）

式中：f（）為目標(biāo)函數(shù)f當(dāng)星鴉個體位于時的值；f（）

為目標(biāo)函數(shù)f當(dāng)位于參考點一時的值；f（）為目標(biāo)函數(shù)f當(dāng)位于參考點二時的值；Eq·（14）、Eq·（15）為如果滿足相應(yīng)條件則返回公式（14）、公式（15）進(jìn)行計算；公式（14）為指導(dǎo)NOA在第一個參考點周圍最有希望的位置，如果沒有得到預(yù)期結(jié)果，那么它將在其他區(qū)域繼續(xù)探索；公式（15）為指導(dǎo)NOA在第二個參考點周圍最有希望的位置，如果沒有得到預(yù)期結(jié)果，那么它將在其他區(qū)域繼續(xù)探索；公式（16）為第一個參考點與第二個參考點的探索行為之間的權(quán)衡。

緩存搜索和找回策略的計算流程如圖3所示。

2.3 基于NOA求解基站最優(yōu)布設(shè)

NOA求解最優(yōu)基站布設(shè)的具體步驟如下。步驟一是種群初始化。隨機生成初始基站位置，作為NOA中“星鴉”的初始位置集合。步驟二是食物儲藏（全局搜索）。模擬星鴉儲藏食物的行為，在解空間內(nèi)探索新的基站位置。步驟三是食物尋找（局部搜索）。模擬星鴉尋找食物的行為，根據(jù)已有的最優(yōu)解和其他星鴉的位置信息來更新當(dāng)前解。步驟四是適應(yīng)度評估。對每個個體基于目標(biāo)函數(shù)計算其適應(yīng)度值，以此確定每個個體的最佳適應(yīng)度以及整個種群中的最優(yōu)適應(yīng)度。步驟五是更新解集。根據(jù)適應(yīng)度評估結(jié)果，選擇性能更優(yōu)的基站布設(shè)作為新一輪迭代的候選解。步驟六是迭代過程。重復(fù)步驟二至步驟五，直到達(dá)到預(yù)定的迭代次數(shù)或解的質(zhì)量閾值。從迭代過程中選擇性能最優(yōu)的基站布設(shè)位置作為最終解。

由于其獨特的搜索策略和多目標(biāo)優(yōu)化能力，因此NOA非常適合應(yīng)用于煤礦井下UWB定位基站的布設(shè)優(yōu)化。由于NOA 具有多樣性和適應(yīng)復(fù)雜問題的特性，因此其可以在大規(guī)模解空間中找最優(yōu)解。，尤其是在井下這種復(fù)雜和動態(tài)變化的環(huán)境中。在平衡全局探索和局部開發(fā)方面，NOA提供了一種有效的方法來處理定位系統(tǒng)中的基站布設(shè)問題，特別是當(dāng)面對多個目標(biāo)和多種約束時。因此，NOA不僅適合理論研究，而且具有實際應(yīng)用于煤礦井下UWB定位系統(tǒng)優(yōu)化布設(shè)的潛力。隨著進(jìn)一步研究，NOA在煤礦井下安全和效率方面的應(yīng)用前景將更廣闊。

3 仿真試驗

3.1 基站布設(shè)優(yōu)化指標(biāo)

在UWB基站布設(shè)中，三維位置精度稀釋因子（PDOP）與區(qū)域覆蓋率是2個關(guān)鍵因素。根據(jù)PDOP衡量基站在空間中的相對布設(shè)對定位精度的影響。在定位系統(tǒng)中，目前普遍使用幾何精度稀釋因子（GDOP）衡量基站幾何布設(shè)對定位精度的影響程度[4]。在UWB定位系統(tǒng)中，基于TDOA信息的位置估計方法一般都校準(zhǔn)了時間偏移誤差，因此GDOP應(yīng)替換為PDOP。PDOP越小，基站幾何結(jié)構(gòu)分布越均勻，性能越好； PDOP 越大，基站幾何布設(shè)越差。當(dāng)PDOP較低時可以獲取更高的定位精度，當(dāng)PDOP﹤3時，說明基站幾何結(jié)構(gòu)較好。PDOP的計算過程如公式（17）所示。

（17）

式中：HDOP為水平分量精度因子；VDOP為垂直分量精度因子。

區(qū)域覆蓋率關(guān)注基站能覆蓋的空間范圍，保證整個目標(biāo)區(qū)域內(nèi)均有穩(wěn)定的信號覆蓋。目前已有許多研究關(guān)注PDOP對UWB基站布設(shè)優(yōu)化的影響，本文將重點利用NOA仿真試驗確定基站位置，保證基站信號能有效覆蓋整個目標(biāo)區(qū)域。

3.2 覆蓋模型

假設(shè)煤礦井下巷道寬6 m，高4 m，長100 m，在井下空間布設(shè)4個基站，定義為B={B1，B2，B3，B4}，其中基站Bi的位置坐標(biāo)為{xi，yi，zi}（i=1，2，3，4）且每個基站具有相同的感知半徑r和通信半徑R。

已知基站Bi的感知范圍是一個以{xi，yi，zi}為中心，以 r 為半徑的封閉圓形區(qū)域。為了簡化計算，將該區(qū)域離散化為m×n個像素點，定義Dj={x1，y2，z3}（j=1，2，…，m×n），其位置坐標(biāo)即基站布設(shè)優(yōu)化位置目標(biāo)，如公式（18）所示。

（18）

式中：d（Bi，Dj）為像素點位置Dj與任一基站Bi之間的歐氏距離，如果存在d ≤ r，則定義該像素點已被信號覆蓋。

采用布爾測量模型作為基站感知模型[5]，定義像素點Dj被Bi感知的概率p（Bi，Dj），如公式（19）所示。

（19）

在該區(qū)域內(nèi)，任意一個像素點Dj能夠同時被多個基站Bi感知，則定義Dj的聯(lián)合感知概率p（B，Dj），如公式（20）所示。

（20）

已知區(qū)域UWB基站布設(shè)區(qū)域覆蓋率即傳感器節(jié)點集合B所覆蓋的像素點數(shù)與區(qū)域內(nèi)所有像素點總數(shù)的比值，其定義如公式（21）所示。

（21）

因此，將NOA應(yīng)用于UWB基站布設(shè)優(yōu)化的目標(biāo)函數(shù)為公式（21），并求解區(qū)域覆蓋率pcov最大值。

設(shè)置NOA相關(guān)參數(shù)如下，種群規(guī)模為30；最大迭代次數(shù)為100次；自變量維數(shù)為12；δ為0.05；Prp為0.2；Pa2為0.4。

3.3 仿真結(jié)果分析

通過NOA模擬仿真，經(jīng)過Matlab仿真的迭代次數(shù)如圖4所示，經(jīng)過100次迭代后，在約束條件內(nèi)得到最佳基站布設(shè)位置，如圖5所示。在此布設(shè)下，保證基站信號有效覆蓋整個目標(biāo)區(qū)域。

4 結(jié)語

本研究成功地應(yīng)用了NOA于UWB定位系統(tǒng)的基站布設(shè)優(yōu)化。通過仿真試驗，本文展示了NOA在提高定位精度和覆蓋范圍方面的顯著效果。使用NOA對基站布設(shè)進(jìn)行優(yōu)化，不僅提高了定位系統(tǒng)的整體性能，而且采用了高效的搜索策略，減少了計算時間和資源消耗。未來研究方向包括利用NOA合理配置基站以最小化位置精度稀釋因子，保證覆蓋整個目標(biāo)區(qū)域，在井下真實環(huán)境中進(jìn)行測試，進(jìn)一步優(yōu)化并改進(jìn)算法。

參考文獻(xiàn)

[1]張巖松.基于UWB 技術(shù)的煤礦井下人員精確定位系統(tǒng)研究[D].徐州：中國礦業(yè)大學(xué)，2021.

[2]楊誼.基于多傳感器融合的室內(nèi)外無縫定位技術(shù)研究[D].重慶：重慶郵電大學(xué)，2022.

[3]ABDEL-BASSET M，MOHAMED R，JAMEEL M，et al.

Nutcracker optimizer： A novel nature-inspired metaheuristic algorithm

for global optimization and engineering design problems[J].Knowledge-Based Systems，2023（262）：110248.

[4]楊帆.超寬帶室內(nèi)定位系統(tǒng)基站選擇方法的研究[D].桂林：桂林電子科技大學(xué)，2023.

[5]何慶，徐欽帥，魏康園.基于改進(jìn)正弦余弦算法的無線傳感器節(jié)點部署優(yōu)化[J].計算機應(yīng)用，2019，39（7）：2035-2043.