曹昌磊，陳志達，龔小宇，洪年祥

1. 紹興市上虞區(qū)自然資源監(jiān)測中心，紹興 312300；

2. 浙江省測繪科學(xué)技術(shù)研究院，杭州 310012

1 引 言

室內(nèi)定位是一項對全球?qū)Ш叫l(wèi)星系統(tǒng)在遮蔽地區(qū)的補充導(dǎo)航定位技術(shù)，為辦公大樓、超市和室內(nèi)外過渡區(qū)域的位置服務(wù)提供了極大的便利（薛偉蓮等，2020)。室內(nèi)定位主要采用無線通信、基站定位、慣導(dǎo)測量和影像導(dǎo)航等方式，而基站定位方式具有信號傳輸距離遠、精度高和可行性高等優(yōu)點，在多種場景中能發(fā)揮出獨特優(yōu)勢。因此，傳感器基站定位方式在城鎮(zhèn)火災(zāi)、地震和倒塌等多種室內(nèi)災(zāi)害場景下的應(yīng)急導(dǎo)航問題處理中獲得了廣泛應(yīng)用（黃瑞貞，2020；施志榮，2019；孫公德等，2017)。

精度衰減因子（dilution of precision，DOP)是評估導(dǎo)航定位精度高低的關(guān)鍵參數(shù)，表示測量誤差與定位精度的相對幾何關(guān)系。當(dāng)DOP 值較大時，組網(wǎng)強度較低，表示在該區(qū)域使用傳感器定位技術(shù)得到的位置精度較低。由于在利用偽距進行空間定位中，需要三個方向位置信息才能確定點位坐標(biāo)（不對接收器的鐘差進行估計)，同時需要多余觀測量提高計算成果的精度，因此，通常需要4 個以上的基站觀測數(shù)據(jù)才能完成空間定位。根據(jù)定位區(qū)域的環(huán)境特征，以及信號的連續(xù)、可靠、多重覆蓋和探測空間最大化特點，優(yōu)化傳統(tǒng)單因子靜態(tài)組網(wǎng)，建立兼顧多因子動態(tài)組網(wǎng)技術(shù)，縮短組網(wǎng)時間并改善綜合定位精度。已有研究多集中在物流倉庫、地下綜采面和辦公大樓等不同場景下的基站組網(wǎng)方式，分析在對應(yīng)區(qū)域中的DOP 分布情況，討論基站幾何布設(shè)對定位誤差的影響（何琦敏和王堅，2017；王寧等，2020；楊燈等，2020)。但這些布設(shè)方案過于理想化，僅考慮單個因素DOP 的誤差影響，忽略信號連續(xù)和重疊等多因素作用。其中，這些因素導(dǎo)致基站組網(wǎng)優(yōu)化本質(zhì)上是一個組合優(yōu)化問題。因此，在實際組網(wǎng)過程中，上述方法通常難以滿足最優(yōu)布設(shè)基站要求。

近些年，有不少研究提出使用遺傳算法優(yōu)化基站組網(wǎng)布設(shè)，對傳統(tǒng)的布設(shè)方案進行優(yōu)化（何琦敏等，2017；Wang 等，2022；周宇泰等，2022)。遺傳算法是一種全局尋優(yōu)算法，最早由美國科學(xué)家John Holland 在20 世紀70 年代提出，由于算法的全局搜索能力和穩(wěn)健性特點，在解決較為復(fù)雜的組合優(yōu)化問題上能夠較快地獲得優(yōu)化結(jié)果（劉修宇等，2021；緱慧娟和楊成龍，2020)。然而，這些方法中沒有考慮信號的通信距離與覆蓋區(qū)域的幾何關(guān)系及相關(guān)的應(yīng)急條件。因此，本文以改進的自適應(yīng)遺傳算法對基站組網(wǎng)進行優(yōu)化，綜合考慮信號的連續(xù)、可靠、多重覆蓋和探測空間最大化特征，分析優(yōu)化方案后的組網(wǎng)強度，為應(yīng)急救援等情況下的定位組網(wǎng)提供參考依據(jù)。

2 組網(wǎng)部署方法

按照觀測模式分類，使用定位傳感器觀測數(shù)據(jù)進行導(dǎo)航定位的方式主要有雙向測距（two way ranging, TWR)模式、時間到達（time of arrival，TOA)模式和時間到達差（time difference of arrival，TDOA)模式。其中，TOA 算法具有精度較高、定位收斂和基站構(gòu)建簡單優(yōu)勢，因此，常用于基站測距定位的實踐應(yīng)用。

2.1 TOA 定位原理簡述

TOA 是一種通過測量終端至基站之間的信號傳輸距離推測終端位置的定位方法，根據(jù)基站發(fā)送至終端接收電磁波信號的傳輸時間計算兩點之間距離，建立基站與終端距離的觀測方程。對于終端的空間位置共三個未知參數(shù)，因此接收到至少3 個基站的信號數(shù)據(jù)，即可實現(xiàn)空間定位。根據(jù)最小二乘準(zhǔn)則和間接平差原理可知（劉大杰等，2003)：

式中，P為觀測值權(quán)陣，由于觀測值均為相對獨立，因此，可設(shè)為單位陣；x為待求參數(shù)的估計值；B為x的雅可比矩陣；f為殘差項；Qxx為待求參數(shù)的協(xié)因數(shù)陣；Q為觀測值協(xié)因數(shù)陣，滿足P=Q-1。由此，可得到x的協(xié)因數(shù)陣Qxx。假設(shè)定位傳感器的測距單位中誤差為δ0，即有x的方差陣為Dxx=δ0Qxx。

2.2 精度衰減因子

用于估計二維平面的精度可用HDOP 表示：

用于估計高程方向的精度可用VDOP 表示：

用于估計三維空間的精度可用PDOP 表示：

式中，xσ、yσ、zσ為坐標(biāo)在三個方向上的誤差；0σ為傳感器測距中誤差。假定信號在傳輸過程中的定位傳感器單位測距誤差保持不變，DOP 將由基站和終端位置的幾何關(guān)系確定，是一個無量綱值。式(2)～式(4)表明，當(dāng)待求坐標(biāo)協(xié)因數(shù)陣上的對角線元素值較大時，DOP 較大，表示點位的定位精度較差。因此，根據(jù)HDOP、VDOP 和PDOP 值所代表的區(qū)域二維、高程和三維精度，從而可評估最終組網(wǎng)的穩(wěn)健性。

2.3 基站組網(wǎng)的基本準(zhǔn)則

在一個已知的封閉空間中，基站數(shù)量和部署形式（矩形、星形和菱形)將直接影響空間定位精度。由于實際室場景中存在較為密集的人流和物體，同時需要考慮封閉空間的幾何構(gòu)造，因此，需要通過分析多種部署方案的實驗結(jié)果，選擇最佳的布設(shè)方案以達到相應(yīng)的定位要求?；镜男盘杺鬏斁嚯x通常有限，為保證信號持續(xù)傳輸，必須保證信號的連續(xù)性。由于采用傳感器定位技術(shù)進行定位需要同時接收多個基站的信號，因此，基站的布設(shè)方式應(yīng)滿足一定的區(qū)域重疊。為了進一步擴大研究區(qū)域的范圍，應(yīng)使用一定數(shù)量的基站以保證定位區(qū)域最大化。此外，為了保證連續(xù)跟蹤的終端目標(biāo)精度達到相應(yīng)要求，避免錯誤定位，要求組網(wǎng)方式具有一定可靠性。綜上，基站組網(wǎng)的布設(shè)方式需要滿足信號連續(xù)性、多重信號覆蓋、責(zé)任區(qū)域最大化、可靠性原則（陳秉試，2021)。由于基站的部署受到上述幾種因素的影響，因此，基站的部署優(yōu)化問題是一種組合優(yōu)化問題。針對每一種組網(wǎng)準(zhǔn)則，應(yīng)滿足如下特點。

1)信號連續(xù)性

假定基站的最大通信距離為d，基站至終端的距離為l，為了確?；灸軌蜻B續(xù)接收無線信號完成定位工作，要求l＜d。

2)多重信號覆蓋

假定所有的基站數(shù)量為k，完成定位工作的最少接收基站數(shù)為N0：

3)可靠性

假定任務(wù)要求點位的DOP 閾值為FDOP，為了保證精度達到要求，即有待定點DOP＜FDOP。

4)探測區(qū)域最大化

網(wǎng)絡(luò)的覆蓋范圍直接影響區(qū)域的嚴密程度和探測能力。在保證覆蓋層數(shù)的條件下，同時滿足覆蓋區(qū)域盡量最大。

為了保證待探測區(qū)域中的DOP 值整體表現(xiàn)較小，定位盲點個數(shù)達到最少的目標(biāo)，滿足相關(guān)部門對不同區(qū)域的精度設(shè)計要求。通過一定數(shù)量的基站，并將基站分布在區(qū)域周圍，達到上述條件要求，可建立相應(yīng)的目標(biāo)函數(shù)并對其量化：

式中，m為不同區(qū)域的類型數(shù)目；ni為選取的有限區(qū)域點（用于計算整體DOP)數(shù)量；ki為區(qū)域差異性引起DOPj的權(quán)重系數(shù)（重點定位區(qū)域系數(shù)比一般定位區(qū)域系數(shù)大)；num(DOPi＞FDOP)為指定區(qū)域i中的盲點數(shù)量（即盲點面積)，即區(qū)域內(nèi)大于FDOP的點數(shù)（DOP 值較大時，定位精度低)；wi為對應(yīng)的num(DOPi＞FDOP)權(quán)重系數(shù)。

3 基于改進的自適應(yīng)遺傳算法基站部署

通過基站的組網(wǎng)部署原理可知，優(yōu)化基站網(wǎng)絡(luò)的性能需要實現(xiàn)目標(biāo)函數(shù)式（6)達到最小完成，本質(zhì)上是一種組合優(yōu)化問題（劉永信等，2021)。目前解決組合優(yōu)化問題的算法主要有多項式時間算法（曲明等，2022)、近似算法（廖玉婕，2022)、啟發(fā)式搜索算法（梅志虎和唐志波，2023)和遺傳算法（楊雄和吳東，2021)等。多項式時間算法、近似算法和啟發(fā)式算法普遍存在枚舉數(shù)量過多、時間效率低、算法計算復(fù)雜度高和與最優(yōu)解的偏差較大等問題（但開和段隆振，2022；李豪等，2023；鄢倫等，2023)。遺傳算法是一種高度并行、隨機且具備自適應(yīng)能力的迭代方法，能夠有效避免陷入局部最優(yōu)，最大化縮短與最優(yōu)結(jié)果的差距（李作山等，2019；文傳奇等，2023；方占萍等，2023)。但傳統(tǒng)遺傳算法也存在對初始解與遺傳算子設(shè)計依賴性和局部收斂性等缺點。為了克服上述問題，本文采用改進的自適應(yīng)遺傳算法用于基站組網(wǎng)方案設(shè)計。算法需要對基站的位置坐標(biāo)進行編碼，經(jīng)過種群配對與迭代計算后，提取最佳基站坐標(biāo)解集。具體方法為，首先，需要分析定位區(qū)域的空間環(huán)境條件，作為參數(shù)的輸入源，以多種常用的組網(wǎng)方式（菱形或方形布設(shè)等)形成初步方案；其次，結(jié)合改良圈算法優(yōu)化初步方案，求得初始方案適應(yīng)度，并選擇改良后的基站方案開始進行迭代運算；最后，基于改進的自適應(yīng)遺傳算法生產(chǎn)新的子代解集，并對子代解集進行適應(yīng)度優(yōu)化，提高算法解算效率。如圖1 所示。

圖1 基于改進的自適應(yīng)遺傳算法基站部署方案Fig.1 Base station deployment plan based on improved adaptive genetic algorithm

1)染色體編碼

在使用遺傳算法時，需要先將解算空間的具體參數(shù)轉(zhuǎn)換為染色體表示，也稱為編碼。編碼方式主要有二進制編碼法、實數(shù)編碼法、排列編碼法和復(fù)數(shù)編碼法等方式。在滿足完備性、健全性和非冗余性的前提下，二進制編碼結(jié)構(gòu)簡單，且便于遺傳和變異操作，在遺傳算法中應(yīng)用最廣。因此，本文采用二進制編碼方式開展后續(xù)研究工作。

2)種群的初代優(yōu)化

遺傳算法的解空間主要由種群數(shù)目確定，而初始種群決定了算法的初始解及收斂效率。為了保證取得最優(yōu)解，初始種群應(yīng)具有一定的規(guī)模，需要避免由于大規(guī)模搜索空間引起的遺傳算法收斂時間過長的問題。同時，初始種群的優(yōu)劣也直接影響到結(jié)果的準(zhǔn)確性和算法效率。本文采用Hamilton 改良圈算法（薛慧和許苗峰，2020)對初始種群進行優(yōu)化，以獲得較好的父代。

3)交叉與變異

改進的自適應(yīng)遺傳算法染色體交叉配對主要采用“門當(dāng)戶對”的方式進行，也就是根據(jù)樣本的適應(yīng)度大小確定種群優(yōu)劣排序，適應(yīng)度小的父本與適應(yīng)度小的父本交配，適應(yīng)度大的父本與適應(yīng)度大的父本交配。染色體交叉點的節(jié)點位置根據(jù)Logistic函數(shù)序列確定，在選定的父代樣本指定位置上完成上述交叉操作。

在算法實現(xiàn)中，可以預(yù)先指定交叉概率值Pj（0～1)。一般情況下，當(dāng)所有父本均存在交叉行為時，概率值為1，反之不發(fā)生則概率值為0，通常情況概率值較大。每一次實現(xiàn)交叉行為算法時，先產(chǎn)生一個區(qū)間大小為0～1 均勻分布的隨機數(shù)，當(dāng)概率值小于Pj時，則在對應(yīng)的序列點上進行交叉操作，反之則不進行操作。

此外，與交叉操作類似，在變異操作上可先從交叉后的個體中選擇變異個體，預(yù)先設(shè)定一個介于0～1 的變異概率值Pb，為了保證收斂過程平穩(wěn)進行，因此，通常變異概率較小，在規(guī)定父本的容量N的條件下，則發(fā)生變異體的個數(shù)Nb=Pb·N。

4)自適應(yīng)優(yōu)化

為了提升子代最優(yōu)解的質(zhì)量，減小局部最優(yōu)解的概率，可對遺傳變異概率進行自適應(yīng)改正，避免在變異函數(shù)時間序列大空間范圍內(nèi)進行搜索時陷入局部極值，因此，采用式（7)、式（8)進行修正：

式中，P j0、Pb0分別為設(shè)置的初代交叉和變異概率值；α、β分別為區(qū)間[0，1]的常數(shù)；fj、fb分別為父代交叉和變異樣本中的最大適應(yīng)度值；faver、fmax分別為全體樣本的平均和最大適應(yīng)度。使用遺傳算法自適應(yīng)函數(shù)式（6)計算目標(biāo)函數(shù)值（適應(yīng)度值為該值相反數(shù))，當(dāng)該值越大時，表示此時的個體適應(yīng)度越小，組網(wǎng)效果較差，反之組網(wǎng)效果較好。

4 模擬實驗與結(jié)果分析

4.1 模擬實驗參數(shù)預(yù)設(shè)值

本文以模擬仿真的多層球形體育館為例，假定球體的最底層圓直徑為200 m，共分為四類不同高度層的重點定位區(qū)域。其中，四類不同高度層的區(qū)域分別為0～5 m、5～10 m、10～15 m 和15～20 m，基站信號的最大傳輸距離為250 m?？紤]兩種基站布設(shè)方案：一是存在固定站（位于頂端)，其余為流動站（位于區(qū)域的外側(cè)地面)；二是均為流動站（位于區(qū)域的外側(cè)地面)。其中，地面站點的基站伸縮長度不高于2 m。圖2 為基站布設(shè)方案示意圖。

圖2 基站布設(shè)方案示意圖Fig.2 Base station deployment plan

改進的自適應(yīng)遺傳算法參數(shù)設(shè)置如下：初始樣本大小為N=50，初始交叉和變異概率值Pj0、Pb0分別為0.95 和0.1；在適應(yīng)度函數(shù)中，最大容忍的FDOP值為12，四個區(qū)域的DOP 加權(quán)值為k={1，2，3，4}，四個區(qū)域DOP 越值的加權(quán)值為w={1，2，3，4}，即隨著樓層高度增加，高層區(qū)域為重點定位區(qū)域。以各個流動基站坐標(biāo)為待求參數(shù)，進行編碼，設(shè)置迭代次數(shù)為50 次，基于組網(wǎng)部署基本準(zhǔn)則的整體目標(biāo)函數(shù)，即式（6)值小于10 或次數(shù)達到最大迭代次數(shù)即可停止運算，輸出最優(yōu)基站坐標(biāo)序列。

4.2 結(jié)果分析

使用改進的自適應(yīng)遺傳算法對兩種布設(shè)方案的基站部署進行優(yōu)化。下表為兩種方案和改變基站數(shù)量后，各層的平均HDOP、VDOP 和PDOP，以及適應(yīng)度函數(shù)值，如表1 所示。

表1 改進的自適應(yīng)遺傳算法運算結(jié)果Tab.1 Calculation results of improved adaptive genetic algorithm

由表1 可知，設(shè)立的固定站點能夠有效減小VDOP 和PDOP，改善在高程方向的精度，不使用固定站的情況下，兩者的HDOP 基本相當(dāng)。同時，隨著基站數(shù)量增加，終端觀測條件得到一定改善，當(dāng)基站數(shù)量從4 個增加到7 個時，在固定站方案中，HDOP、VDOP 和PDOP 分別減小20.4%、27.4%、35.9%，49.0%、56.5%、59.4%，47.1%、54.5%、57.8%；在無固定站方案中，HDOP、VDOP 和PDOP分別減小了13.1%、22.5%、29.5%，13.7%、26.5%、40.4%，13.7%、26.5%、40.4%。此外，隨著高度增加，VDOP 和PDOP 呈現(xiàn)增減趨勢，在固定站方案中，VDOP 和PDOP 呈現(xiàn)增大的趨勢，隨著基站數(shù)量增加后，這種趨勢不明顯；在無固定站方案中，VDOP 和PDOP 呈現(xiàn)減小的趨勢。分析出現(xiàn)上述情況的原因主要是，在固定站方案中，由于基站數(shù)目增加后，觀測條件得到了極大的改善，即使在惡劣的網(wǎng)絡(luò)結(jié)構(gòu)條件下，仍然能夠保持較高的精度；而針對無固定站方案中，由于所有站點位于地面，此時低層的空間高度角基本趨于0°，整體觀測條件較差，隨著高度增加，高度角的改善使得位于高層的觀測條件達到最佳。

綜上所述，基站數(shù)量由4 到5 時，組網(wǎng)效果顯著提升，而繼續(xù)增加基站數(shù)量后，DOP 值沒有明顯降低，因此，在兼顧基站成本情況下，選擇5 個基站更加符合大多數(shù)的工程定位應(yīng)用需求。為了進一步分析組網(wǎng)方式的空間位置精度分布特征，以組網(wǎng)綜合情況最佳的5 個基站（具備固定站)方案為例，繪制了分層的PDOP 等值線圖，如圖3 所示。

圖3 5 個基站布設(shè)方案的PDOP 空間分布Fig.3 Spatial distribution of PDOP for 5 base station deployment plans

隨著樓層增加，PDOP 整體呈現(xiàn)減小趨勢，分布由單一中心區(qū)域PDOP 最小對稱結(jié)構(gòu)變?yōu)槎嘀行淖钚〗Y(jié)構(gòu)，在考慮整體定位范圍前提下，重點兼顧高樓層定位區(qū)域的精度。因此，在解決組網(wǎng)定位中的基站布設(shè)問題時，需要綜合考慮固定站與底部流動站和定位區(qū)域高度的關(guān)系，保證應(yīng)急情況下作業(yè)人員進入室內(nèi)搜救路線設(shè)計安排。

5 結(jié) 論

本文介紹了定位傳感器組網(wǎng)部署的優(yōu)化方案原理與設(shè)計，以模擬的多層球形體育館仿真實驗為例，利用改進的自適應(yīng)遺傳算法對基站組網(wǎng)設(shè)計進行優(yōu)化。分別討論有固定基站和無固定基站的組網(wǎng)部署方式的DOP 分布，分析了基站數(shù)量對基站組網(wǎng)的性能影響。結(jié)果表明，在建筑物頂端設(shè)立固定站能夠有效改善VDOP 和PDOP，針對一般的二維定位可不需設(shè)立固定站，采用無固定站的方式具有較好的平面定位性能；隨著基站數(shù)量的增加，DOP值得到一定程度的改善，但改進效果越來越不明顯。因此，在達到定位條件的情況下，可以綜合考慮基站組網(wǎng)的成本，減少基站的數(shù)量，在使用4 個流動站和1 個固定站的方案下，可以使最終的綜合效益達到最高，同時定位精度可向重點定位區(qū)域方向傾斜，為相關(guān)的組網(wǎng)布設(shè)提供參考依據(jù)。