TDoA 定位盲區(qū)分析與節(jié)點部署策略研究

趙越，李贊，李冰，郝本建

（1.西安電子科技大學通信工程學院，陜西 西安 710071；2.中國人民解放軍31007 部隊，北京 100000）

0 引言

無線傳感器網(wǎng)絡（WSN,wireless sensor network）能夠實現(xiàn)對覆蓋區(qū)域內非合作信號源的感知、識別、定位等功能[1]。非合作信號源的定位一般包含2 個步驟：定位參數(shù)估計和信號源位置解算[2]。具體來說，各個傳感器節(jié)點將采集的信號原始數(shù)據(jù)回傳至融合處理中心，后者從多組接收信號數(shù)據(jù)中提取出關于信號源位置的定位參數(shù)。在此基礎上，融合處理中心根據(jù)定位參數(shù)和各個傳感器節(jié)點自身的準確空間位置信息，構建信號源位置信息關聯(lián)方程組并求解。常用的定位參數(shù)包括到達時間（ToA,time of arrival）、到達時間差（TDoA,time difference of arrival）、到達頻率差（FDoA,frequency difference of arrival）、到達角度（AoA,angle of arrival）等[3-5]。

在基于接收信號參數(shù)測量實現(xiàn)信號源定位的WSN 中，信號源的空間位置是根據(jù)定位參數(shù)及傳感器節(jié)點自身位置計算得到的。因此，WSN 對信號源的定位精度取決于各個傳感器節(jié)點的接收信噪比、WSN 相對于信號源的空間幾何構型、WSN的系統(tǒng)誤差（包括節(jié)點位置誤差、時鐘同步誤差等）[6]。接收信噪比受信號源的輻射強度、信號傳輸距離、傳感器節(jié)點感知能力等多種因素影響，它直接決定了WSN 對定位參數(shù)的估計精度。WSN和信號源所構成的空間幾何構型決定了WSN 對信號源的空間辨識度，并由此決定了信號源位置關聯(lián)信息。系統(tǒng)誤差影響了定位參數(shù)與真實信號源位置的關聯(lián)準確度，可等效為定位參數(shù)估計誤差和傳感器節(jié)點自誤差，繼而在位置解算時產生定位誤差。

在定位精度的影響因素中，通過增強節(jié)點感知能力或物理空間上靠近信號源，可以提升各傳感器節(jié)點的接收信噪比；通過標校站輔助或系統(tǒng)誤差統(tǒng)計數(shù)據(jù)，可以消除系統(tǒng)誤差。然而，空間幾何構型是由位置未知的信號源與WSN 中各節(jié)點的位置共同決定的[7]。當WSN 與信號源所構成的空間幾何構型較好時，WSN 對信號源的空間辨識度較大，能夠提供的空間域信息較多；反之，能夠提供的空域信息較少，導致定位精度嚴重惡化，產生定位盲區(qū)。需要說明的是，無線定位中盲區(qū)與無線通信中盲區(qū)的產生原因是不同的，前者是由于傳感器網(wǎng)絡對信號源的定位幾何構型惡化或消失，而無法區(qū)分目標的空間位置，與接收信噪比沒有直接關系；后者則是由基站覆蓋區(qū)域、障礙物遮擋、通信網(wǎng)絡擁塞、信號頻段特性等因素造成用戶接收情況惡化，進而影響通信服務質量[8-10]。

國內外學者對定位盲區(qū)進行了闡述與分析[11-15]。文獻[11]提出TDoA 與FDoA 聯(lián)合定位算法，并在仿真算法性能時發(fā)現(xiàn)，當信號源位于定位節(jié)點連線方向時無法準確定位。文獻[12]對TDoA 與FDoA 定位場景中的定位精度分布進行了分析，并定義了定位有效區(qū)域與定位無效區(qū)域（即定位盲區(qū)）。為了解決TDoA 與FDoA 定位場景中的定位盲區(qū)問題，文獻[13]提出引入AoA 作為輔助定位信息的思路及相應算法。文獻[11]論證了利用TDoA 和FDoA 實現(xiàn)信號源定位時的克拉美羅下界（CRLB,Cramer-Rao lower bound）等高線與僅利用TDoA 定位時的CRLB 等高線具有相同的分布，即TDoA 定位中在定位節(jié)點連線方向存在定位盲區(qū)。在基于TDoA 的二維定位場景中，文獻[14]研究了定位節(jié)點分布對定位精度的影響。在基于TDoA 的三維定位場景中，文獻[15]研究了基線長度、基線角度、傳感器節(jié)點高程、傳感器平面等多種因素對覆蓋區(qū)域定位精度分布的影響，并通過仿真分析得出了定位盲區(qū)所在的分布區(qū)域。此外，文獻[16]論證了在基于AoA 的定位場景中，當定位節(jié)點相對于信號源位于同一方向時，交叉定位結果將急劇惡化并產生定位盲區(qū)。

然而，現(xiàn)有文獻對定位盲區(qū)的分析仍然具有局限性。當定位節(jié)點相對于信號源的空間幾何構型確定時，現(xiàn)有文獻通過仿真結果證明了定位盲區(qū)的存在，并簡要分析了定位盲區(qū)的出現(xiàn)區(qū)域，但未從數(shù)學角度深入剖析定位盲區(qū)的產生原因，也未能給出判斷及預測定位盲區(qū)所出現(xiàn)區(qū)域的方法。此外，現(xiàn)有文獻并未闡述當測量矩陣滿秩時定位盲區(qū)的產生條件以及出現(xiàn)區(qū)域。

定位節(jié)點部署策略是定位網(wǎng)絡空間幾何構型優(yōu)化的主要技術手段?，F(xiàn)有文獻大多針對單一信號源進行定位節(jié)點部署策略研究，在已知信號源準確位置的前提下，給出最優(yōu)的節(jié)點部署策略。文獻[17]研究了二維TDoA 定位場景中最優(yōu)的節(jié)點部署策略，從CRLB 對定位節(jié)點方位角的駐點入手，推導出等角度陣列（UAA,uniform angular array）是使信號源CRLB 最小的部署方案。Yang等[18-20]研究了TDoA 定位中的傳感器節(jié)點部署策略，推導證明了針對單一信號源的最優(yōu)部署方式是UAA，并提出存在部署區(qū)域約束時定位精度最優(yōu)化的節(jié)點部署策略。

在研究面向整個覆蓋區(qū)域的WSN 節(jié)點部署策略時，現(xiàn)有針對單信號源的部署策略不再適用。文獻[15]仿真分析了當傳感器所在平面與信號源方向成不同夾角時定位盲區(qū)的分布區(qū)域，并提出應盡可能使信號源位于傳感器所在平面中心點的法線方向，然而，該文只是粗略地給出了避免定位盲區(qū)時應具有的條件，未能給出最優(yōu)的部署方案。文獻[21]提出定位精度門限的概念，并將WSN 覆蓋區(qū)域中定位精度優(yōu)于該門限的區(qū)域視為有效定位區(qū)域。繼而將最大化有效定位區(qū)域為優(yōu)化目標，通過仿真分析生成若干組具有不同構型的定位網(wǎng)絡，尋求使有效定位區(qū)域面積最大的一組定位節(jié)點。然而，該文只分析了有限的定位節(jié)點構型組合，未能給出最優(yōu)的定位節(jié)點部署方案。

本文以基于TDoA 定位參數(shù)的二維WSN 為基本場景，開展TDoA 定位盲區(qū)分析與節(jié)點部署策略研究。首先，從定位誤差的理論界限CRLB的角度出發(fā)，對定位盲區(qū)的產生原因進行了剖析。其次，分析了TDoA 測量誤差、WSN 相對于信號源的空間幾何構型等不同因素對定位盲區(qū)的影響。再次，提出了平均CRLB 作為衡量WSN 覆蓋區(qū)域定位精度的表征方式；在此基礎上，以平均CRLB 為目標函數(shù)，構建了傳感器節(jié)點部署優(yōu)化問題，并提出了基于定位盲區(qū)預判斷的遺傳算法對其求解。最后，計算機仿真驗證了單信號源定位時CRLB 的性質；驗證了定位盲區(qū)與信號源相對于傳感器節(jié)點的方向向量有關，且會出現(xiàn)在滿秩測量矩陣的場景中；驗證了所提節(jié)點部署算法對于WSN 覆蓋區(qū)域的定位精度優(yōu)于3 種基準算法。

1 TDoA 定位場景及定位精度衡量參數(shù)

1.1 二維TDoA 定位場景

基于無線傳感器網(wǎng)絡實現(xiàn)非合作信號源定位場景如圖1 所示。WSN 包含M(M≥3)個節(jié)點，節(jié)點位置坐標的集合為{s1,s2,…,sM}T，其中，,?i=1,2,…,M。U為WSN 的覆蓋區(qū)域。在U內存在一個信號輻射源，其位置坐標為。從WSN 的角度來說，該信號源是非合作的，即WSN 無法掌握該信號源的先驗信息，例如信號輻射時刻、信號參數(shù)特征、歷史運動軌跡等。因此，WSN 采用基于TDoA 參數(shù)的定位方式，不需要與非合作信號源進行交互即可實現(xiàn)對其位置估計。

圖1 非合作信號源定位場景示意

假設信號源和無線傳感器節(jié)點之間為直射路徑，則信號源所輻射的無線電波傳播至第i個傳感器節(jié)點的時間為

其中，c為無線電波的傳播速度，為向量的2 范數(shù)運算。

不失一般性，將節(jié)點s1視為測量TDoA 時的參考節(jié)點，則信號源的輻射信號傳播至第i個節(jié)點和參考節(jié)點的真實時間差為

考慮高斯加性噪聲的TDoA 測量模型，通過接收信號相關運算測量得到的信號源的TDoA 為

其中，為TDoA 測量值，ni1服從均值為零、方差為的高斯分布。

定義TDoA 測量值集合和測量誤差的集合分別為

其中，n服從均值為零、協(xié)方差矩陣為的高斯分布，d ing{x}表示將向量x作為對角元素的矩陣。

1.2 單信號源定位精度衡量參數(shù)

信號源的位置解算過程就是按照某一準則從TDoA 測量值中估計出信號源的位置坐標，并盡可能地使其接近其真實位置u。作為任何無偏估計的方差下界，基于信息理論的CRLB 在定位問題中被廣泛地作為定位精度的衡量參數(shù)，CRLB 定義為費希爾信息矩陣（FIM,Fisher information matrix）的逆矩陣[4]。

在基于TDoA 的定位場景中，利用τ? 對信號源位置u進行估計時的CRLB 為

其中，C(u)為CRLB，J(u)=HQ-1HT為FIM。矩陣H取決于信號源u和WSN 中各節(jié)點的空間位置關系，其每一列是TDoA 真值（標量）對于信號源真實位置（列向量）的導數(shù)，具體表達式為

其中，di1,x、di1,y分別為向量di1的橫、縱坐標。由于C(u)是J(u)的逆矩陣，根據(jù) FIM 的行列式det(J(u))與伴隨矩陣J*(u)可進一步得到C(u)的表達式，即

進一步地，可得TDoA 定位場景中信號源位置估計的CRLB 的跡為

根據(jù)式(4)～式(10)，可以得到以下關于CRLB的若干性質。

性質1當TDoA 誤差的方差恒定時，CRLB與信號源到各節(jié)點的距離無關。

證明在式(5)中，若矩陣Q恒定，則CRLB 只與矩陣H有關。根據(jù)式(6)中矩陣H的表達式可知，H僅與信號源到達各節(jié)點的方向向量有關，而與信號源和各節(jié)點的距離無關。此外，根據(jù)式(10)也可以得到相同結論。證畢。

性質2在TDoA 定位中，將任一節(jié)點視為參考節(jié)點對CRLB 沒有影響。

證明性質2 的證明可參考文獻[4]，該文獻分析了TDoA 和FDoA 聯(lián)合定位場景中參考節(jié)點選擇的無關性。需要說明的是，若融合處理中心準確已知各節(jié)點的接收信噪比，那么參考節(jié)點和其他節(jié)點測量得到的TDoA誤差分布特性是可計算得到的[6]，當改變參考節(jié)點時，CRLB 是不變的。證畢。

2 定位盲區(qū)存在性及影響因素分析

定義1若WSN 對某一信號源的CRLB 趨于無窮大，則稱信號源所處的空間位置為WSN 的定位盲點。

定義2在WSN 的覆蓋區(qū)域內，全部定位盲點的集合稱為WSN 的定位盲區(qū)。

由式(10)可知，WSN 相對于信號源的空間幾何構型影響著定位精度衡量參數(shù)CRLB。當幾何構型較好時，CRLB 較小，WSN 可實現(xiàn)對信號源的精確定位；反之，CRLB 較大甚至趨于無窮，WSN 對信號源的定位誤差極大，甚至失效，此時認為該信號源所處位置位于WSN 的定位盲區(qū)內。

定理1在基于TDoA 的二維定位場景中，若傳感器節(jié)點相對于信號源的方向向量組中，不同向量的個數(shù)不大于2，則信號源所處位置為WSN 的定位盲點。從數(shù)學表達式的角度來說，信號源u相對于全部傳感器節(jié)點{s1,s2,…,sM}的方向向量為{d1,d2,…,dM}，若{d1,d2,…,dM}滿足以下任意一種情況時，WSN 對于該信號源的CRLB 不存在。

情況1 所對應的定位幾何構型是全部M個節(jié)點和信號源共線，且均位于信號源的同一側。情況2 表示存在2 個不同方向向量，而其余方向向量均等于其中之一，所對應的定位幾何構型是全部M個節(jié)點均位于相對于信號源的2 個不同的方向向量上。

證明根據(jù)柯西-施瓦茨不等式的一般形式可知，式(10)的分母是非負的，即

當柯西-施瓦茨不等式中等號成立的充要條件滿足時，式(10)的分母為零，tr(C(u))不存在，產生定位盲區(qū)。式(11)取等號的充要條件為

下面討論式(12)成立的條件。

2) 若di1≠0 且d21,…d(i-1)1,d(i+1)1,…,dM1=0，則式(12)成立，此時方向向量d1,d2,d i-1,di+1…,dM均相等，且與di1不相等，所對應的定位幾何構型是除si外其余傳感器節(jié)點和信號源共線，且信號源位于這些節(jié)點的一側，如圖2(b)所示。

3) 若di1≠ 0且d21,…d(i-1)1,d(i+1)1,…,dM1=di1，則式(12)成立，此時除d1外，全部方向向量均與di相等，所對應的定位幾何構型是除參考節(jié)點s1外其余傳感器節(jié)點和信號源共線，且信號源位于這些節(jié)點的一側，如圖2(c)所示。

圖2 定位盲區(qū)產生條件的示意

4) 若di1≠ 0,dj1≠0,i≠j，則不存在λ使式(12)成立。

證畢。

推論1在二維TDoA 定位場景中，當傳感器節(jié)點排列為線形陣列時，節(jié)點所在直線為定位盲區(qū)；當存在一個傳感器節(jié)點與其余節(jié)點不共線時，傳感器節(jié)點包圍的區(qū)域內不存在定位盲點，包圍區(qū)域一定不是定位盲區(qū)。

證明當傳感器節(jié)點排列為線形陣列時，若信號源位于傳感器節(jié)點連線在某一側的延伸線上，則定理1 中的情況1 成立，該位置為定位盲點；若信號源位于傳感器節(jié)點之間，則定理1 中的情況2 成立，該位置為定位盲點。綜上，當傳感器節(jié)點排列為線形陣列時，節(jié)點所在直線為定位盲區(qū)。

另一方面，當存在一個傳感器節(jié)點與其余節(jié)點不共線時，節(jié)點包圍區(qū)域內的任意一點（即使在任意2 個傳感器節(jié)點的連線上）相對于全部傳感器節(jié)點的相同方向向量個數(shù)都嚴格大于2，因此包圍區(qū)域內不存在定位盲點。證畢。

推論2TDoA 測量誤差的強度并不影響定位盲區(qū)的存在，以及定位盲區(qū)所處的空間位置。

證明定理1 闡述的2 種定位盲點存在情況均與TDoA 測量誤差的強度無關，只與WSN 相對于信號源的空間幾何構型有關。因此，即使TDoA 定位誤差的方差逐漸變小，也依然存在定位盲區(qū)，且所處空間位置不變。證畢。

推論3在3 個傳感器節(jié)點構成的WSN 中，定位盲區(qū)存在于任意2 個傳感器節(jié)點連線的外側。

證明當僅存在3 個傳感器節(jié)點且不共線時，根據(jù)推論1，傳感器節(jié)點內側包圍區(qū)域一定不是定位盲區(qū)。然而，當信號源位于任意2 個傳感器節(jié)點的外側連線上時，定理1 的情況2 滿足，外側連線對應的區(qū)域為定位盲區(qū)。證畢。

根據(jù)定理1 及相關推論，可以定性分析WSN 覆蓋區(qū)域中的定位盲區(qū)，繼而指導WSN 的部署方案、定位盲區(qū)的補盲方案、信號源定位結果的置信度評估等。具體來說，在典型場景中部署WSN 時，應使定位盲區(qū)遠離重點監(jiān)測區(qū)域及目標信號源，從而保證定位精度。其次，借鑒無線通信中的微蜂窩、直放站等補盲方式，以定理1 為理論支撐，通過部署額外的節(jié)點可消除定位盲區(qū)。最后，在信號源定位過程中，若連續(xù)定位結果在區(qū)域內劇烈跳變，且多個定位點處于WSN 的定位盲區(qū)內，則定位結果的置信度較差。

推論4對于某一定位網(wǎng)絡和信號源形成的矩陣H，若該矩陣的秩小于空間維度，該信號源處于定位盲區(qū)。

證明對于定理1 中的情況1，矩陣H的列向量全部為零向量，此時該矩陣的秩為0；對于定理1中的情況2，矩陣H的全部列向量是平行的（考慮存在零向量的情形），如圖2(b)和圖2(c)所示，此時，該矩陣的秩為1。因此，若矩陣H的秩小于空間維度，該信號源處于定位盲區(qū)。證畢。

3 基于平均CRLB 的傳感器節(jié)點部署算法

定位盲區(qū)的產生與WSN 的部署方式緊密相關，一旦出現(xiàn)定位盲區(qū)，WSN 所覆蓋區(qū)域的平均定位精度將急劇惡化。因此，面向重點監(jiān)測區(qū)域部署WSN 時，應以避免定位盲區(qū)為首要目標。本節(jié)首先提出區(qū)域定位精度的衡量參數(shù)，并以此為基礎構建節(jié)點部署優(yōu)化問題，提出基于定位盲區(qū)預判斷的遺傳算法進行求解。

3.1 區(qū)域定位精度衡量參數(shù)

定義3若信號源隨機出現(xiàn)在WSN 的覆蓋區(qū)域U中，其位置坐標服從概率密度函數(shù)f(u)，則WSN 對于信號源的平均CRLB 為

其中，積分區(qū)間是u∈U。如式(10)所示，C(u)與u呈高度非線性關系，難以直接給出平均 CRLB的表達式。因而，本文采用離散形式逼近平均CRLB。

定義4在覆蓋區(qū)域U中，按照概率密度函數(shù)f(u) 隨機生成N個信號源，即{u1,u2,…,uN}，則平均CRLB 可近似為

其中，pi是信號源出現(xiàn)在第i個位置時的概率，均勻分布時。當N→∞時，

說明如下。1) 覆蓋區(qū)域的定位精度還可以使用定位中斷概率來衡量，類似于文獻[21]提出的有效定位區(qū)域的概念。然而，平均定位精度更適合于衡量存在定位盲區(qū)時的區(qū)域定位精度，這是因為中斷概率中的定位精度閾值難以合理設定。2) 對于非合作信號源，其出現(xiàn)在WSN 覆蓋區(qū)域的概率密度函數(shù)是未知的，此時假設f(u) 為均勻分布是合理的。3)C(u)與信號源位置u和傳感器節(jié)點的位置{s1,s2,…,sM}有關，而(u)與按照隨機變量u概率密度函數(shù)隨機產生的N個采樣點位置{u1,u2,…,uN}和傳感器節(jié)點的位置{s1,s2,…,sM}有關。

3.2 節(jié)點部署優(yōu)化問題構建與分析

在傳感器節(jié)點部署時，需要提前規(guī)劃各個傳感器節(jié)點的部署位置，從而實現(xiàn)對WSN 覆蓋區(qū)域內潛在信號源的最優(yōu)定位精度。本文以平均CRLB 為目標函數(shù)，構建約束優(yōu)化問題為

需要說明的是，針對單一信號源的節(jié)點部署方式，文獻[17]已證明均勻角度部署是最優(yōu)的。而在優(yōu)化問題 P1中，目標函數(shù)是整個區(qū)域內隨機選取采樣點后計算得到的平均CRLB，因此該優(yōu)化問題的最優(yōu)解應該是使區(qū)域平均定位精度最好的一種部署方式。

由式(10)可知，WSN 對單個信號源的CRLB 是關于傳感器節(jié)點空間位置向量的非凸函數(shù)。進一步地，在式(15)中，目標函數(shù)C～(u)的表達式關于待求解變量也呈現(xiàn)出非凸性質。因而，想要直接求解優(yōu)化問題 P1較為困難。

3.3 直接遺傳算法和基于定位盲區(qū)預判斷的遺傳算法

遺傳算法是一種較成熟的進化算法，在資源分配、網(wǎng)絡規(guī)劃等領域的大量非線性和非凸的優(yōu)化問題中被廣泛應用[22-24]。遺傳算法的核心思想來源于達爾文的生物進化論，通過模擬生物進化過程中的自然選擇、種群繁殖、基因突變，利用“種群”的不斷進化和淘汰，最終實現(xiàn)優(yōu)勢個體的保留和劣勢個體的移除[25]。

3.3.1 直接遺傳算法

本節(jié)采用遺傳算法直接求解優(yōu)化問題 P1，將目標函數(shù)、決策變量映射為遺傳算法的基本元素，具體如下。

環(huán)境適應度。優(yōu)化問題中的約束條件僅包括傳感器節(jié)點的定義域，無其他約束條件，因此環(huán)境適應度函數(shù)可直接選取目標函數(shù)，即，其中δ是使分母不為零的極小自然數(shù)。

下面給出利用遺傳算法求解優(yōu)化問題 P1的主要步驟。

步驟3采用聯(lián)賽選擇算法或輪盤賭選擇算法對當前種群進行選擇，盡可能保留適應度函數(shù)較大的個體，并拋棄適應度函數(shù)較小的個體。聯(lián)賽選擇算法的思想是隨機挑選k個個體進行競爭，適應性最好的將獲得遺傳權。輪盤賭選擇算法的思想是將適應度與選擇概率聯(lián)系起來，個體被選中的概率與其適應度大小成正比。

步驟4利用基因重組的思想，產生現(xiàn)有種群中個體的后代，使個體數(shù)量恢復到Np。例如，對于個體和，其后代可按照獲得，其中，l服從均勻分布U(0,1)，⊙為向量的Schur 積。

步驟5利用基因突變思想，對種群中一定比例的個體的染色體進行隨機變化?；蛲蛔兛杀ＷC種群的多樣性，避免算法陷入局部最優(yōu)解。

步驟6判斷迭代次數(shù)是否達到預設值，若達到預設值則算法結束，返回當前最優(yōu)解；否則返回步驟2，且迭代次數(shù)加1。

3.3.2 基于定位盲區(qū)預判斷的遺傳算法

在直接遺傳算法中，決策變量是WSN 中各節(jié)點的空間位置坐標，因此每個染色體χ中包含2M個未知標量；此外，在遺傳算法的迭代過程中，種群在整個定義域內進行更新。因此，直接遺傳算法具有較大的運算復雜度，且只能求解得到優(yōu)化問題 P1的近似最優(yōu)解。

根據(jù)推論1，若信號源處于WSN 的部署范圍S內，傳感器節(jié)點應盡可能地部署在該區(qū)域的外部邊界，且盡可能地避免多個傳感器節(jié)點共線，由此可避免定位盲區(qū)，降低區(qū)域的平均定位誤差。因此，若S為凸集，可以將 P1中的決策變量修改為

其中，θi表示第i個傳感器節(jié)點相對于S內任一參考坐標原點（例如s0）的方位角，即

由于S為凸集，則方位角與位置坐標可一一對應，可以將節(jié)點部署優(yōu)化問題改寫為 P2，即

在 P2中，將 {θ1,θ2,…,θM}所對應的位置坐標約束在部署區(qū)域的外部邊界，這樣的約束條件設置內在地避免了定位盲區(qū)的產生，從而保證了區(qū)域的平均定位精度，因此優(yōu)化問題 P2的解可進一步逼近最優(yōu)節(jié)點部署方案。

為了對比算法復雜度，本文給出如下定義。定義算法在單個個體迭代中花費的時間為tf=tfitness+tselection+tcrossover+tmutation，其中，tfitness表示計算環(huán)境適應度函數(shù)的時間成本，tselection、tcrossover、tmutation分別表示執(zhí)行選擇、重組、突變的時間成本。定義可允許的最大進化迭代次數(shù)為Lmax，則遺傳算法的時間復雜度為ttotal=LmaxN p tf[22]，其中，Np為種群中的個體數(shù)量且已在3.3.1 節(jié)給出。需要說明的是，在所關注的優(yōu)化問題 P1和 P2中，決策變量維度分別為2M和M，而在進行環(huán)境適應度函數(shù)計算時，仍然把各節(jié)點的角度信息轉換為二維坐標進行計算，因此所提算法與直接遺傳算法的tfitness+tselection是近似相同的；由于tcrossover+tmutation和決策變量的維度有直接關系，因此所提算法的這部分時間成本更低。綜上，在求解節(jié)點部署優(yōu)化問題時，所提基于定位盲區(qū)預判斷的遺傳算法的時間復雜度比直接遺傳算法稍具優(yōu)勢。

4 仿真驗證與分析

本節(jié)通過計算機仿真，驗證單信號源CRLB 的相關性質、驗證與分析定位盲區(qū)的存在區(qū)域、對比不同傳感器節(jié)點部署算法的性能。本節(jié)仿真所采用的仿真平臺是安裝于Intel(R) Core(TM) i9-9900K CPU @ 3.60 GHz 計算機的MATLAB R2021a 軟件。

需要說明的是，針對單信號源CRLB 性質驗證的主要目的是闡述測量誤差給定時，定位幾何構型對定位精度的影響；針對區(qū)域CRLB 性質驗證的主要目的是給出定位盲區(qū)的出現(xiàn)區(qū)域，并說明與蒙特卡羅實驗結果的一致性；針對傳感器節(jié)點部署的仿真分析是為了說明所提算法的優(yōu)勢。

4.1 單信號源CRLB 性質驗證

構建存在單信號源的二維定位場景，其中，信號源的位置坐標為u= [0,0]T，有M=5個傳感器節(jié)點，位置坐標分別為s1= [300,100]T,s2=[400,150]T,s3= [300,500]T,s4= [350,200]T,s5=[ -100,-1 00]T。設這組傳感器節(jié)點為 WSN1。在 WSN1的基礎上，將傳感器節(jié)點s1,s3,s5的位置坐標相對于信號源向外擴展，生成 WSN2={ks1,s2,ks3,s4,ks5}。在本節(jié)的仿真中，k=1.2。與 WSN2相比，WSN1傳感器節(jié)點相對信號源的方向向量未發(fā)生變化，而部分傳感器節(jié)點與信號源的距離變大了。

單信號源定位場景中Root CRLB 和均方根誤差（RMSE,root mean squared error）的仿真結果如表1所示，其中，RMSE 是由200 次蒙特卡羅仿真得到的。CRLB 為均方誤差（MSE）的理論下界，Root CRLB（即CRLB 的平方根值）為RMSE 的理論下界。由表1可知，當WSN中任一節(jié)點作為參考節(jié)點且TDoA測量誤差協(xié)方差矩陣已知時，更換參考節(jié)點并不影響該WSN 對信號源的CRLB，RMSE 也近似相等。此外，當TDoA 測量誤差的協(xié)方差矩陣不變且WSN 中部分傳感器節(jié)點沿著信號源與傳感器節(jié)點所在射線（需要保證方向向量不變）移動時，WSN 對信號源的CRLB 不變，RMSE 近似相等。

表1 單信號源定位場景中Root CRLB 和RMSE 的仿真結果

4.2 定位盲區(qū)仿真驗證與分析

在對定位盲區(qū)的理論分析中，本文將CRLB 視為定位精度的衡量指標，因為CRLB 能夠給出某一定位場景下WSN 對信號源定位精度的理論下界，即任何無偏估計定位算法的定位誤差均大于CRLB。本節(jié)引入定位解析算法，并設置蒙特卡羅實驗來計算定位解析算法的RMSE，通過與CRLB 進行對比分析來驗證基于CRLB 對定位盲區(qū)分析的準確性。

考慮一個包含M=5個傳感器節(jié)點的WSN，傳感器節(jié)點呈線形排列，位置坐標分別為。WSN 的覆蓋區(qū)域為正方形，即。將s1視為參考節(jié)點，設置TDoA 測量誤差的標準差為。當給定WSN 中各個傳感器節(jié)點的坐標后，對覆蓋區(qū)域U均勻采樣獲取若干采樣點，并計算每個采樣點的CRLB，便可繪制覆蓋區(qū)域內CRLB 分布等高線圖。WSN 中節(jié)點線性排列時Root CRLB 和RMSE 的分布等高線圖如圖3 所示。需要說明的是，節(jié)點線性排列導致文獻[4]算法產生奇異矩陣而失效。為了獲取RMSE，本節(jié)利用一階泰勒級數(shù)的方法[26]在真實信號源附近進行搜索。盡管如此，信號源真實位置作為初始點的泰勒展開法在絕對的定位盲點也無法獲取信號源位置估計值。此外，在仿真圖中，等高線所表示的定位精度單位為米，為避免文字重疊，圖中將定位誤差的單位省去，后續(xù)仿真圖中等高線的定位精度單位也并未標注。

根據(jù)圖3 可知，線形排列的WSN 所在直線為定位盲區(qū)，在該區(qū)域，CRLB 不存在，RMSE 無窮大。由WSN 所在直線的延長線兩側向WSN 所在直線的中垂線方向（[-5000,5 000]與[5 000,-5 000]連線的方向）移動，CRLB 逐漸變小，定位算法的RMSE 從“不存在”過渡為異常大。在中垂線方向，WSN 的定位精度最優(yōu)，絕大多區(qū)域定位精度在10 m 以下。

為了論證定理1 中情況2 的定位盲區(qū)，將WSN中的s5由[ -2 500,-2 500]T移動至[ -2 500,-2 500]T，WSN 中節(jié)點的排列不再是線形，此時Root CRLB和RMSE 的分布等高線圖如圖4 所示。由圖4 可知，1)s1至s4所在直線的外側仍為定位盲區(qū)，CRLB 不存在，RMSE 無窮大；2) 偏出的節(jié)點s5附近并不存在定位盲區(qū)；3) WSN 節(jié)點所包圍的區(qū)域內定位精度可達4 m，包圍區(qū)域內不存在盲點。圖4 的仿真結果與定理1 結論一致，結合圖3 與圖4 可證明推論1 的相關結論。

圖3 WSN 中節(jié)點線性排列時Root CRLB 和RMSE 的分布等高線圖

圖4 WSN 中一個節(jié)點偏出時Root CRLB 和RMSE 的分布等高線圖

進一步地，將WSN 中的s4由[ 2 500,2 500]T移動至[ 2 500,-2 500]T，此時WSN 相對于覆蓋區(qū)域內任意一點的不同方向向量個數(shù)均大于2，不滿足定理1中的情況2。WSN中2個節(jié)點偏出時Root CRLB和RMSE 的分布等高線圖如圖5 所示。由圖5 可知，WSN 覆蓋區(qū)域內不存在定位盲區(qū)，絕大多區(qū)域的定位精度在10 m 以下。圖5 的仿真結果證明了定理1 的正確性。

圖5 WSN 中2 個節(jié)點偏出時Root CRLB 和RMSE 的分布等高線圖

為了驗證推論2，本節(jié)選取圖4 中的WSN 部署方式，并設置4 組不同的TDoA 測量誤差標準差，即。TDoA 測量誤差的標準差變化時Root CRLB 的分布等高線圖如圖6 所示。由圖6 可知，TDoA 測量誤差的強度并不影響CRLB的等高線分布，只是在不同的等高線上定位誤差不同；當TDoA 測量誤差為對角矩陣時，定位精度與測量誤差的方差呈線性關系。需要說明的是，在研究無線定位網(wǎng)絡空間幾何構型的影響時，可將測量誤差歸一化，并采用定位精度幾何因子（GDOP,geometric dilution of precision）作為分析對象[7]。

圖6 TDoA 測量誤差的標準差變化時Root CRLB 的分布等高線圖

當WSN 僅保留3 個節(jié)點，且呈等邊三角形式分布時，WSN 覆蓋區(qū)域的Root CRLB 和RMSE 的分布等高線圖如圖7 所示。需要說明的是，三節(jié)點TDoA 定位場景的RMSE 是利用文獻[27]中所提出的算法，結合一階泰勒展開法獲得的。由圖7 可知，在任意2 個節(jié)點的外側，存在定位盲區(qū)，不存在CRLB，RMSE 無窮大；在節(jié)點包圍區(qū)域的內部，不存在定位盲點，這與推論3 是一致的。

圖7 WSN 僅包含3 個節(jié)點時Root CRLB 和RMSE 的分布等高線圖

4.3 傳感器節(jié)點部署算法驗證與分析

由圖3～圖5 可知，當傳感器節(jié)點部署方式發(fā)生變化時，覆蓋區(qū)域內定位精度的等高線也在發(fā)生變化。本節(jié)通過仿真分析的形式，研究覆蓋區(qū)域平均CRLB 最小化的傳感器節(jié)點部署算法。

考慮存在M=5個節(jié)點的WSN，假設其部署區(qū)域與覆蓋區(qū)域相同，即S==[ -5 000,-5 000]T×[ 5 000,5 000]T。假設不考慮傳感器節(jié)點的通信距離與覆蓋范圍約束，并設置TDoA 測量誤差的標準差為。

為了驗證所提的基于定位盲區(qū)預判斷的遺傳算法，本節(jié)設計了3 個對比算法：均勻角度部署算法、區(qū)域頂點部署算法、直接遺傳算法。均勻角度部署算法以覆蓋區(qū)域為中心，將全部傳感器節(jié)點部署于。區(qū)域頂點部署算法將4 個傳感器節(jié)點部署于覆蓋區(qū)域的4 個頂點，另外一個位于覆蓋區(qū)域的中心。直接遺傳算法如3.3.1 節(jié)所述，將傳感器節(jié)點的空間位置作為決策變量，在覆蓋區(qū)域S中迭代搜尋，獲取使平均CRLB 最小的節(jié)點部署方案。

4 種節(jié)點部署算法對覆蓋區(qū)域定位的性能對比如圖8 所示。由圖8(a)可知，所提基于定位盲區(qū)預判斷的遺傳算法能夠獲得最小的平均Root CRLB，對應的節(jié)點部署方案能實現(xiàn)覆蓋區(qū)域內信號源的最優(yōu)定位精度。當 TDoA 測量誤差的方差為時，所提算法對于區(qū)域的平均定位精度比均勻角度部署算法提高了33.92%，比區(qū)域頂點部署算法提高了13.74%，比直接遺傳算法提高了9.65%。

圖8 4 種節(jié)點部署算法對覆蓋區(qū)域定位的性能對比

圖8(b)中時間復雜度由算法的運行時間反映。直接遺傳算法和所提基于定位盲區(qū)預判斷的遺傳算法中均設置種群規(guī)模為100，最大迭代次數(shù)為200 次，算法終止條件為目標的迭代增量。由圖8(b)可知，隨著可部署的傳感器節(jié)點個數(shù)的增加，2 種算法可獲得的平均Root CRLB 都在逐漸變小，這表示部署更多的傳感器節(jié)點可提升覆蓋區(qū)域內目標的定位精度。其次，基于定位盲區(qū)預判斷的遺傳算法運算時間小于直接遺傳算法，這是因為直接遺傳算法在定義域內進行全域搜索，且決策變量維度較高，而所提算法只在部署區(qū)域的邊界進行迭代搜索，且決策變量維度較低，因而時間復雜度也較低。

圖9 典型TDoA 測量誤差下4 種節(jié)點部署算法對區(qū)域定位時平均Root CRLB 分布等高線圖

5 結束語

本文針對TDoA 為定位參數(shù)的WSN，從單信號源定位精度CRLB 入手，探討了傳感器節(jié)點與信號源的方向向量對CRLB 的影響，給出了定位盲區(qū)產生的充分條件，并分析了TDoA 測量誤差、傳感器節(jié)點排列方式等多種因素對定位盲區(qū)的影響。在此基礎上，構建了傳感器節(jié)點部署問題，并提出了基于定位盲區(qū)預判斷的遺傳算法來求解。仿真表明，所提算法相較于區(qū)域頂點部署、均勻角度部署、直接遺傳算法，可將定位精度大幅提升。本文提出的定位盲區(qū)研究方法對已部署網(wǎng)絡的定位性能分析具有參考意義，所提節(jié)點部署方案對待部署網(wǎng)絡的定位盲區(qū)出現(xiàn)區(qū)域具有指導意義，具有廣泛的應用前景。