王思琦，劉 江，2，3，蔡伯根，王 劍，2，3

(1.北京交通大學(xué) 電子信息工程學(xué)院，北京 100044；2.北京交通大學(xué) 智慧高鐵系統(tǒng)前沿科學(xué)中心，北京 100044；3.北京市軌道交通電磁兼容與衛(wèi)星導(dǎo)航工程技術(shù)研究中心，北京 100044；4.北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，北京 100044)

隨著列控系統(tǒng)自主化、智能化的不斷發(fā)展,引入新技術(shù)、新方法提高列車運(yùn)行效率、減少軌旁設(shè)備、降低線路建設(shè)成本和維護(hù)工作量,是我國(guó)新型列控系統(tǒng)(Chinese Train Control System-New, CTCS-N)和歐盟下一代列控系統(tǒng)(Next Generation Train Control, NGTC)的核心發(fā)展方向[1-2]。列車的自主定位是新型列控系統(tǒng)的一項(xiàng)基礎(chǔ)性關(guān)鍵技術(shù),引入全球?qū)Ш叫l(wèi)星系統(tǒng)(Global Navigation Satellite System, GNSS)提供全天候、實(shí)時(shí)、精確的列車定位,已成為當(dāng)前新型列控系統(tǒng)的重要研究?jī)?nèi)容之一[3]。

為實(shí)現(xiàn)列控系統(tǒng)低成本、高可靠的運(yùn)營(yíng)需求,在引入衛(wèi)星定位的同時(shí)有效降低其對(duì)既有系統(tǒng)的異化程度,國(guó)際鐵路聯(lián)盟于2005年提出了基于衛(wèi)星定位實(shí)現(xiàn)虛擬應(yīng)答器(Virtual Balise, VB)的概念,旨在采用與歐洲列車控制系統(tǒng)(European Train Control System, ETCS)規(guī)范相兼容的虛擬應(yīng)答器接口代替實(shí)體應(yīng)答器向車載設(shè)備發(fā)送報(bào)文信息,從而減少對(duì)軌旁實(shí)體應(yīng)答器的需求,降低實(shí)體應(yīng)答器所導(dǎo)致的維護(hù)工作量和運(yùn)營(yíng)成本,為將衛(wèi)星定位引入列控系統(tǒng)提供了一種重要的互操作化接入形式。然而,基于衛(wèi)星定位的虛擬應(yīng)答器技術(shù)要達(dá)到期望的功能與性能,對(duì)虛擬應(yīng)答器所在位置的導(dǎo)航衛(wèi)星信號(hào)觀測(cè)質(zhì)量提出了一定要求,即設(shè)置虛擬應(yīng)答器位置的衛(wèi)星觀測(cè)條件需足以達(dá)到所需的定位性能水平。考慮鐵路運(yùn)行環(huán)境的復(fù)雜性,線路上各處的衛(wèi)星觀測(cè)條件不一,如何令虛擬應(yīng)答器在線路上的“布設(shè)”充分保障導(dǎo)航衛(wèi)星可見(jiàn)性及觀測(cè)質(zhì)量,已成為決定虛擬應(yīng)答器實(shí)施效用水平的一項(xiàng)關(guān)鍵因素?，F(xiàn)有關(guān)于虛擬應(yīng)答器的研究多集中在VB與ATP列控系統(tǒng)的接口方法[4]、VB捕獲方法[5]、VB安全風(fēng)險(xiǎn)分析[6]等,虛擬應(yīng)答器的布局目前尚無(wú)統(tǒng)一方案。若參照實(shí)體應(yīng)答器采用等間距布設(shè)方案[7],尚缺乏對(duì)虛擬應(yīng)答器可用性的有效考慮。歐盟ERSAT-GGC[8-10]計(jì)劃率先針對(duì)ETCS-3級(jí)系統(tǒng)提出VB布局優(yōu)化的思想,采用威脅監(jiān)測(cè)技術(shù)輔助虛擬應(yīng)答器的邏輯位置布局,避免因外部環(huán)境(如電磁干擾與欺騙攻擊等)引起虛擬應(yīng)答器定位出現(xiàn)無(wú)界位置誤差,但其在虛擬應(yīng)答器候選位置的考量中著重關(guān)注外部的侵入性因素,對(duì)候選位置的信號(hào)觀測(cè)質(zhì)量尚未形成全面衡量,且還未形成一套完整的量化方案。

基于上述現(xiàn)狀,本文提出一種基于局域定位場(chǎng)景聚類的虛擬應(yīng)答器布局優(yōu)化方法,從鐵路沿線環(huán)境遮擋情況角度出發(fā),提取列車往復(fù)運(yùn)行中積累的衛(wèi)星定位歷史數(shù)據(jù),重構(gòu)沿線的可見(jiàn)天空輪廓,采用基于DTW距離度量的DBSCAN聚類算法確定軌道片場(chǎng)景,引入?yún)^(qū)段延拓思想劃分開(kāi)闊、受限、極端等不同區(qū)段類型,并利用改進(jìn)的遺傳算法對(duì)受限區(qū)段的VB布設(shè)方案進(jìn)行優(yōu)化。研究中利用現(xiàn)場(chǎng)試驗(yàn)數(shù)據(jù)對(duì)所提出的方法進(jìn)行了驗(yàn)證和分析,體現(xiàn)該方法對(duì)實(shí)際線路中VB的布設(shè)效用和重要意義。

1 虛擬應(yīng)答器工作原理

虛擬應(yīng)答器本質(zhì)上是一套車載列控系統(tǒng)的軟件模塊,包括定位單元模塊(Locator Unit Module, LUM)、安全判別模塊(Safety Qualifier Module, SQM)和虛擬應(yīng)答器模塊(VB Module, VBM),它通過(guò)衛(wèi)星定位接收機(jī)等設(shè)備獲取列車的實(shí)時(shí)位置、速度等信息,將該位置與預(yù)設(shè)在軌道上的下一虛擬應(yīng)答器(Next Virtual Balise, NVB)的位置進(jìn)行匹配,即VB捕獲過(guò)程,從而確定列車經(jīng)過(guò)參考點(diǎn)(即NVB)的時(shí)刻,提取預(yù)先存儲(chǔ)在虛擬應(yīng)答器報(bào)文數(shù)據(jù)庫(kù)中的報(bào)文信息傳輸至列車自動(dòng)超速防護(hù)(Automatic Train Protection, ATP)系統(tǒng)。列車在兩個(gè)連續(xù)的VB之間運(yùn)行時(shí),由輪軸測(cè)速測(cè)距提供與最近相關(guān)虛擬應(yīng)答器(Last Relevant Virtual Balise, LRVB)的相對(duì)位置信息,實(shí)現(xiàn)列車定位。圖1為VB工作原理。

圖1 虛擬應(yīng)答器工作原理

在VB選址布局方面,歐洲鐵路研究所(European Rail Research Institute, ERRI)于2005年發(fā)布一系列虛擬應(yīng)答器功能規(guī)范[11-13],明確表示虛擬應(yīng)答器的布設(shè)要實(shí)現(xiàn)以下目的:

(1)提高列車在VB之間的定位精度(連續(xù)兩個(gè)VB的距離越小,則最大定位誤差減小的概率越大)。

(2)VB應(yīng)布設(shè)在衛(wèi)星星座可見(jiàn)性較高的軌道位置,使衛(wèi)星定位可用性、精確性和完好性得到最佳利用(不需要等間距沿軌道布設(shè))。

(3)應(yīng)避免將VB布設(shè)在實(shí)體應(yīng)答器附近,避免信號(hào)之間的干擾。

最簡(jiǎn)單的VB選址布局參照實(shí)體應(yīng)答器的布局方式,然而,實(shí)體應(yīng)答器的布局方式不需考慮應(yīng)答器待布設(shè)位置的衛(wèi)星信號(hào)觀測(cè)質(zhì)量,對(duì)于擬布設(shè)VB的候選位置,如果因其局部地形環(huán)境等因素導(dǎo)致衛(wèi)星信號(hào)觀測(cè)質(zhì)量不佳,可能使所實(shí)現(xiàn)的衛(wèi)星定位性能不足以支撐高精度VB捕獲,VB報(bào)文的激勵(lì)無(wú)法達(dá)到預(yù)期的效果。圖2為線路VB候選位置三種可能的衛(wèi)星觀測(cè)情況。

圖2 虛擬應(yīng)答器候選位置觀測(cè)質(zhì)量示意

由圖2可知,不同線路環(huán)境下衛(wèi)星觀測(cè)質(zhì)量可能存在顯著差異,當(dāng)列車處于全遮擋線路,如隧道、橋梁、帶頂棚車站等,衛(wèi)星信號(hào)被完全遮擋,衛(wèi)星定位不可用,故該情況不適宜布設(shè)VB,應(yīng)根據(jù)線路實(shí)際情況布設(shè)實(shí)體應(yīng)答器;當(dāng)列車運(yùn)行線路環(huán)境為路塹、山脈、叢林等區(qū)域時(shí),衛(wèi)星信號(hào)極易受到遮擋,衛(wèi)星定位接收機(jī)僅能接收部分衛(wèi)星信號(hào),且信號(hào)反射可能較常出現(xiàn),則衛(wèi)星定位性能會(huì)隨之劣化,故而,VB應(yīng)布設(shè)在上述線路區(qū)段中局部衛(wèi)星觀測(cè)質(zhì)量較佳的位置;當(dāng)列車運(yùn)行線路周圍環(huán)境較為開(kāi)闊、遮擋較少時(shí),衛(wèi)星可見(jiàn)性好,定位性能易于得到保障,可采用相對(duì)直接的布局策略,如等間隔布設(shè)VB方式?；谝陨戏治?本文首先從目標(biāo)線路的局域定位場(chǎng)景特征劃分入手,為最終確定VB布局策略提供依據(jù)。

2 局域定位場(chǎng)景聚類策略

2.1 鐵路沿線局域定位場(chǎng)景

鐵路線路地域跨度大,沿線環(huán)境復(fù)雜多變,衛(wèi)星信號(hào)極易受到外界環(huán)境不同程度的遮擋,導(dǎo)致衛(wèi)星定位性能存在較大的差異。局域定位場(chǎng)景是衛(wèi)星定位接收機(jī)天線周邊局部范圍內(nèi)的地形環(huán)境(如山谷、樹(shù)林、路塹、隧道等)所致衛(wèi)星信號(hào)傳播及接收特性的一種分類與描述,直接反映了衛(wèi)星信號(hào)觀測(cè)環(huán)境中信號(hào)受到遮擋等影響的程度,且不同定位場(chǎng)景下衛(wèi)星定位性能存在差異?？梢?jiàn)天空輪廓(天空遮擋的邊界)作為局域定位場(chǎng)景的一種精細(xì)描述,可以用于局域定位場(chǎng)景辨識(shí),評(píng)價(jià)不同區(qū)域衛(wèi)星定位性能。衛(wèi)星天空?qǐng)D描述了特定線路關(guān)鍵點(diǎn)上空的衛(wèi)星分布情況,根據(jù)衛(wèi)星分布特性,可以重構(gòu)可見(jiàn)天空輪廓。繪制天空?qǐng)D需要兩個(gè)參數(shù):衛(wèi)星仰角和方位角,其中,衛(wèi)星仰角反映了衛(wèi)星信號(hào)的質(zhì)量,一般來(lái)說(shuō),衛(wèi)星仰角越高,受線路周邊障礙物遮擋和反射的可能性越小,衛(wèi)星信號(hào)質(zhì)量越高。衛(wèi)星仰角也被廣泛用于GNSS定位過(guò)程中相關(guān)權(quán)重的確定,是區(qū)分視距(Line of Sight, LoS)、非視距(Non Line of Sight, NLoS)信號(hào)的重要特征指標(biāo)。圖3顯示了鐵路沿線部分典型環(huán)境場(chǎng)景及其可見(jiàn)天空輪廓,天空?qǐng)D中陰影部分代表被遮擋的天空,紅色線條即為可見(jiàn)天空輪廓,表示區(qū)域四周環(huán)境遮擋的細(xì)節(jié)。

圖3 典型環(huán)境場(chǎng)景及可見(jiàn)天空輪廓示意

因此,根據(jù)鐵路沿線的可見(jiàn)天空輪廓,對(duì)鐵路沿線局域定位場(chǎng)景進(jìn)行聚類與判別,將遮擋程度相似的場(chǎng)景進(jìn)行整合,依此確定不同區(qū)段是否適合布設(shè)VB以及宜采取的布設(shè)策略,從而實(shí)現(xiàn)全線VB選址布局。

2.2 聚類策略

定位場(chǎng)景聚類算法具體實(shí)施可分為以下7個(gè)步驟。

Step1數(shù)據(jù)準(zhǔn)備。從衛(wèi)星定位接收機(jī)原始數(shù)據(jù)中提取導(dǎo)航衛(wèi)星觀測(cè)信息,所涉及原始數(shù)據(jù)如表1所示。根據(jù)軌道電子地圖將鐵路沿線等間隔分割為若干軌道片segi,根據(jù)接收機(jī)解算的列車經(jīng)度、緯度信息確定每個(gè)軌道片的歷史導(dǎo)航衛(wèi)星觀測(cè)信息。

Step2剔除無(wú)效可見(jiàn)衛(wèi)星?？紤]部分不可見(jiàn)衛(wèi)星信號(hào)易受多徑效應(yīng)的影響,被衛(wèi)星定位接收機(jī)當(dāng)成可見(jiàn)衛(wèi)星信號(hào)接收并參與定位解算,從而降低了線路環(huán)境特征描述的準(zhǔn)確性。設(shè)置衛(wèi)星仰角閾值Tβ和衛(wèi)星信噪比閾值TSNR,剔除無(wú)效可見(jiàn)衛(wèi)星。

Step3選擇邊界衛(wèi)星。邊界衛(wèi)星即接近可見(jiàn)天空輪廓的可見(jiàn)衛(wèi)星。將方位角等間隔劃分為若干個(gè)區(qū)域,在每個(gè)區(qū)域選擇可見(jiàn)衛(wèi)星最低仰角β,仰角屬于[β,β+Bβ]區(qū)間的所有可見(jiàn)衛(wèi)星組成該方位角的邊界衛(wèi)星,其中,Bβ為確定邊界衛(wèi)星的仰角帶寬。

Step4曲線擬合。根據(jù)邊界衛(wèi)星,采用光滑樣條函數(shù)擬合可見(jiàn)天空輪廓,得到參數(shù)化邊界

( 1 )

Step5計(jì)算天空可見(jiàn)度。天空可見(jiàn)度Vis表示天空?qǐng)D中無(wú)遮擋天空所占的比例,為后續(xù)VB布局優(yōu)化方法提供部分?jǐn)?shù)據(jù)。

( 2 )

Step6曲線約簡(jiǎn)。若僅采用Step4所得序列進(jìn)行聚類,會(huì)面臨顯著的相似度計(jì)算復(fù)雜性,故而采用Douglas-Peucker(DP)算法對(duì)可見(jiàn)天空輪廓進(jìn)行約簡(jiǎn),得到約簡(jiǎn)邊界特征,以簡(jiǎn)化聚類相似性計(jì)算。

算法首先在待處理曲線的首尾之間虛連接一條直線,計(jì)算所有中間點(diǎn)與直線的距離;然后,尋找最大距離值Dmax,將該值與約簡(jiǎn)閾值TDP進(jìn)行比較:若Dmax

Step7場(chǎng)景聚類。約簡(jiǎn)后邊界特征已變成不等長(zhǎng)序列,采用動(dòng)態(tài)時(shí)間規(guī)劃(Dynamic Time Warping, DTW)算法計(jì)算不等長(zhǎng)序列的相似性,用于具有噪聲的基于密度的聚類方法(Density-Based Spatial Clustering of Applications with Noise, DBSCAN)。

DTW算法通過(guò)對(duì)序列進(jìn)行拉伸或壓縮計(jì)算兩個(gè)序列的“最小”距離,計(jì)算式為

γi,j=d1i,2j+min(γi-1,j,γi,j-1,γi-1,j-1)

( 3 )

式中:γi,j為序列的動(dòng)態(tài)時(shí)間規(guī)劃距離;d1i,2j為樣本點(diǎn)之間的歐式距離。

DBSCAN算法是一種典型的基于密度的無(wú)監(jiān)督聚類算法,該聚類算法可以有效識(shí)別邊界特征中的噪聲場(chǎng)景,其聚類結(jié)果主要取決于領(lǐng)域半徑ε和領(lǐng)域密度閾值MinPts,參數(shù)取值不同,其聚類簇?cái)?shù)、簇內(nèi)和簇間性能存在較大差異。該算法首先根據(jù)給定參數(shù)找出所有核心對(duì)象,然后,以任一核心對(duì)象為出發(fā)點(diǎn),找出由其密度可達(dá)的樣本生成聚類簇,直到所有核心對(duì)象均被訪問(wèn)過(guò)為止。表2為本文所提場(chǎng)景聚類算法的偽代碼以及預(yù)期結(jié)果的可視化。

表2 場(chǎng)景聚類算法

3 虛擬應(yīng)答器布局優(yōu)化方法

3.1 布設(shè)策略

定位場(chǎng)景聚類策略將鐵路沿線衛(wèi)星定位場(chǎng)景分為無(wú)遮擋場(chǎng)景、輕度遮擋場(chǎng)景、重度遮擋場(chǎng)景、全遮擋場(chǎng)景等局域類別,不同局域定位場(chǎng)景衛(wèi)星定位性能存在顯著差異。由于鐵路沿線衛(wèi)星定位場(chǎng)景復(fù)雜多變,部分線路區(qū)域定位場(chǎng)景頻繁轉(zhuǎn)換,單一場(chǎng)景特征覆蓋的線路長(zhǎng)度有限,較難確定VB的位置,為進(jìn)一步簡(jiǎn)化VB的布局方法,采用區(qū)段延拓思想,將以上多種定位場(chǎng)景進(jìn)行組合,延拓后分為開(kāi)闊、受限、極端共三類區(qū)段,在不同類區(qū)段結(jié)合現(xiàn)有虛擬應(yīng)答器和實(shí)體應(yīng)答器布設(shè)原則選用不同的虛擬應(yīng)答器布局策略。

(1)開(kāi)闊區(qū)段:多數(shù)為無(wú)遮擋場(chǎng)景,存在少數(shù)部分遮擋場(chǎng)景,衛(wèi)星定位性能較為穩(wěn)定,在該類區(qū)段采用等間隔均勻布設(shè)VB的策略;

(2)受限區(qū)段:由部分遮擋場(chǎng)景和無(wú)遮擋場(chǎng)景組成,在該類區(qū)段定位場(chǎng)景頻繁交換,衛(wèi)星定位性能存在較大的波動(dòng),可采用基于改進(jìn)遺傳算法的VB布局優(yōu)化方法,選擇衛(wèi)星定位性能優(yōu)越的位置布設(shè)VB;

(3)極端區(qū)段:多由全遮擋場(chǎng)景和部分遮擋場(chǎng)景組成,衛(wèi)星信號(hào)遮擋嚴(yán)重,在該類區(qū)段將不布設(shè)VB。

為確定三類區(qū)段的長(zhǎng)度,使得區(qū)段長(zhǎng)度足以滿足相應(yīng)布設(shè)策略的最低要求,且實(shí)現(xiàn)不同類區(qū)段對(duì)區(qū)段內(nèi)場(chǎng)景交換頻數(shù)(區(qū)段內(nèi)相鄰軌道片的局域定位場(chǎng)景不一致的次數(shù))的要求,按如下方式實(shí)施區(qū)段延拓:

首先,合并相鄰定位場(chǎng)景一致的軌道片,確定場(chǎng)景長(zhǎng)度。

然后,根據(jù)全線不同定位場(chǎng)景的天空可見(jiàn)度統(tǒng)計(jì)結(jié)果,確定不同類型局域定位場(chǎng)景的衛(wèi)星信號(hào)遮擋程度。將定位場(chǎng)景按相應(yīng)天空可見(jiàn)度均值進(jìn)行降序排序,設(shè)置場(chǎng)景最大交換頻數(shù)Fmax和待合并定位場(chǎng)景長(zhǎng)度上限值Lmax,根據(jù)定位場(chǎng)景排序結(jié)果逐一進(jìn)行場(chǎng)景合并,得到至少包含兩種不同類型定位場(chǎng)景的混合場(chǎng)景,經(jīng)過(guò)合并的混合場(chǎng)景將不再進(jìn)行二次合并。

最后,設(shè)置區(qū)段內(nèi)任一類型定位場(chǎng)景總長(zhǎng)度占區(qū)段長(zhǎng)度的百分比閾值R,默認(rèn)天空可見(jiàn)度最低的混合場(chǎng)景為極端區(qū)段,以極端區(qū)段作為部分區(qū)段分界線,結(jié)合閾值R確定其余兩類區(qū)段。

在上述方案確保能夠確定目標(biāo)線路不同類別區(qū)段的劃分后,整體VB布設(shè)的關(guān)鍵問(wèn)題即為受限區(qū)段的VB布局優(yōu)化策略。

3.2 受限區(qū)段優(yōu)選策略

本文提出一種基于改進(jìn)遺傳算法的VB布局優(yōu)化方法,提取列車往復(fù)運(yùn)行積累的歷史運(yùn)行數(shù)據(jù),統(tǒng)計(jì)區(qū)段軌道片衛(wèi)星觀測(cè)質(zhì)量指標(biāo),如表3所示,結(jié)合現(xiàn)有應(yīng)答器布設(shè)原則,采用改進(jìn)的單目標(biāo)遺傳算法確定受限區(qū)段VB最佳布設(shè)方案。

表3 衛(wèi)星觀測(cè)質(zhì)量指標(biāo)

3.2.1 目標(biāo)函數(shù)的確定

以上多個(gè)衛(wèi)星觀測(cè)質(zhì)量指標(biāo)綜合反映了各軌道片衛(wèi)星定位整體性能,結(jié)合多個(gè)衛(wèi)星觀測(cè)質(zhì)量指標(biāo)確定受限區(qū)段VB最佳布設(shè)方案是一個(gè)多目標(biāo)優(yōu)化問(wèn)題,為簡(jiǎn)化尋優(yōu)過(guò)程,采用逼近理想解法(Technique for Order Preference by Similarity to Ideal Solution, TOPSIS)將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)變?yōu)閱文繕?biāo)優(yōu)化問(wèn)題,通過(guò)構(gòu)建理想最優(yōu)指標(biāo)集和理想最劣指標(biāo)集,計(jì)算目標(biāo)指標(biāo)與理想指標(biāo)集的距離,獲得目標(biāo)與理想解的貼合度,將多目標(biāo)(衛(wèi)星觀測(cè)質(zhì)量指標(biāo))優(yōu)化問(wèn)題轉(zhuǎn)為單目標(biāo)(貼合度)優(yōu)化問(wèn)題。

3.2.2 約束條件的確定

在充分考慮衛(wèi)星定位性能的前提下,VB布設(shè)密度也是需要考慮的因素。VB布設(shè)距離較近時(shí),在衛(wèi)星定位接收機(jī)輸出頻率一定的情況下,相鄰列車定位位置可能經(jīng)過(guò)多個(gè)VB,增加VB漏捕獲風(fēng)險(xiǎn),且用于VB捕獲觸發(fā)報(bào)文傳輸時(shí)間將大大減小,限制了VB捕獲功能的有效實(shí)現(xiàn);VB布設(shè)距離較遠(yuǎn)時(shí),列車在連續(xù)兩個(gè)VB之間運(yùn)行中,隨著輪軸測(cè)速測(cè)距誤差的積累,列車定位誤差水平可能因未得到及時(shí)校正而超過(guò)限定,無(wú)法滿足列控系統(tǒng)需求。因此,結(jié)合現(xiàn)有實(shí)體應(yīng)答器布設(shè)原則,確定VB最大布設(shè)間隔dmax和最小布設(shè)間隔dmin,作為遺傳算法求解的距離約束條件,其數(shù)學(xué)函數(shù)模型可表示為

( 4 )

s.t.So≤si≤SD

?idmin≤|si+1-si|≤dmax

式中:n為區(qū)段布設(shè)虛擬應(yīng)答器的數(shù)量;So為區(qū)段起始里程;SD為區(qū)段終止里程;si表示布設(shè)第i個(gè)虛擬應(yīng)答器的里程;c(si)為布設(shè)位置的貼合度。

3.2.3 函數(shù)模型求解

遺傳算法(Genetic Algorithm, GA)是模擬自然界生物進(jìn)化機(jī)制解決搜索問(wèn)題的一種通用算法,該算法廣泛應(yīng)用于單目標(biāo)優(yōu)化和多目標(biāo)優(yōu)化領(lǐng)域。但是,該算法存在收斂速度慢、局部搜索能力較差等問(wèn)題,本文引入帶有學(xué)習(xí)能力的麻雀搜索算子通過(guò)引導(dǎo)變異算子的變異方向,增加遺傳算法的局部搜索能力。

麻雀搜索算法(Sparrow Search Algorithm, SSA)是由Xue和Shen[14]于2020年提出的一種新穎的群體智能優(yōu)化算法,受麻雀的覓食行為和反捕食行為的啟發(fā)而提出,算法具有尋優(yōu)能力強(qiáng)、收斂速度快等優(yōu)點(diǎn),其搜索過(guò)程分為探索者位置更新、跟隨者位置更新以及反捕食行為。

探索者用于提供覓食區(qū)域和方向,其更新過(guò)程為

( 5 )

式中:X=[x1x2…xn]為麻雀位置,n為麻雀總數(shù);itermax為最大迭代次數(shù);i為迭代次數(shù);?為[0,1]內(nèi)的隨機(jī)數(shù);Q為服從正態(tài)分布的隨機(jī)數(shù);L為元素全為1的矩陣;R2(R2∈[0,1])和ST(ST∈[0.5,1])分別為預(yù)警值和安全值。

跟隨者監(jiān)視探索者隨時(shí)爭(zhēng)奪食物,其更新過(guò)程為

( 6 )

當(dāng)麻雀意識(shí)到危險(xiǎn)時(shí),會(huì)做出反捕食行為,其更新過(guò)程為

( 7 )

式中:fi為適應(yīng)度值;fg、fw分別為當(dāng)前最優(yōu)、最差適應(yīng)度值;K為[-1,1]內(nèi)的隨機(jī)數(shù);ε為避免分母為0的常數(shù)。

本文基于改進(jìn)的遺傳算法通過(guò)編碼、種群初始化、選擇算子、交叉算子、變異算子、麻雀算子以及保留策略共7個(gè)步驟,快速求取受限區(qū)段虛擬應(yīng)答器布局優(yōu)化問(wèn)題的最佳布設(shè)方案,具體實(shí)施步驟如下:

Step1編碼。針對(duì)虛擬應(yīng)答器位置的一維里程屬性,采取實(shí)數(shù)編碼方式。一個(gè)染色體代表受限區(qū)段一種可行的VB布設(shè)方案,染色體上的基因代表VB擬選位置,基因數(shù)量可變,以實(shí)現(xiàn)VB布設(shè)數(shù)量的優(yōu)化。

Step2種群初始化。初始化種群的分布對(duì)算法求解的全局收斂性具有較大的影響,為確保初始種群的隨機(jī)性,采用滿足距離約束的隨機(jī)生成方法產(chǎn)生個(gè)體。

Step3選擇算子。采用二進(jìn)制錦標(biāo)賽機(jī)制選擇父種群的兩個(gè)個(gè)體作為雙親,即從種群中隨機(jī)選擇兩個(gè)個(gè)體,選擇適應(yīng)度值較高的個(gè)體進(jìn)行遺傳操作。

Step4交叉算子。采用單點(diǎn)交叉,隨機(jī)產(chǎn)生交叉點(diǎn)。實(shí)行交叉時(shí),由于VB布設(shè)距離約束,需對(duì)新產(chǎn)生的個(gè)體進(jìn)行部分VB位置修正。

Step5變異算子。根據(jù)變異概率對(duì)種群中選定個(gè)體的某些基因座上的基因值進(jìn)行變動(dòng),產(chǎn)生新的個(gè)體。本文采用多點(diǎn)變異方法,確定待變異的基因。

Step6麻雀算子。麻雀算子用于輔助引導(dǎo)個(gè)體朝著局部最優(yōu)解的方向變異,根據(jù)VB布設(shè)距離約束確定變異基因的可活動(dòng)范圍,采用麻雀算子在該范圍內(nèi)進(jìn)行局部尋優(yōu),確定基因位置。

Step7保留策略。通過(guò)比較父代和子代的個(gè)體適應(yīng)度值,保留適應(yīng)度值較高的個(gè)體,避免優(yōu)秀的個(gè)體在進(jìn)化過(guò)程中遭遇淘汰,且保留個(gè)體不重復(fù)以增加種群的多樣性。

3.3 方法總結(jié)

上述基于局域定位場(chǎng)景聚類的虛擬應(yīng)答器布局優(yōu)化方法可以通過(guò)圖4所示的處理流程對(duì)VB布局優(yōu)化方法進(jìn)行總結(jié)。

圖4 基于局域定位場(chǎng)景聚類的虛擬應(yīng)答器布局優(yōu)化方法

本文所提出的VB布局優(yōu)化方法從衛(wèi)星信號(hào)遮擋情況出發(fā),充分利用了衛(wèi)星定位的可用性、精確性和完好性,且結(jié)合現(xiàn)有虛擬應(yīng)答器和實(shí)體應(yīng)答器布設(shè)原則,不是簡(jiǎn)單的將VB等間距布設(shè)在軌道線路上,而是適應(yīng)其應(yīng)用需求形成了定制化方案。

總結(jié)來(lái)看,本文所提出的方法具有以下特點(diǎn):

(1)在VB布局優(yōu)化過(guò)程中由于引入了鐵路沿線衛(wèi)星定位場(chǎng)景聚類方法,能夠根據(jù)定位場(chǎng)景確定區(qū)段衛(wèi)星定位性能,采用不同的VB布設(shè)策略,簡(jiǎn)化了列車運(yùn)行全線VB的布設(shè)。

(2)基于改進(jìn)遺傳算法的VB布局優(yōu)化方法,首次將VB布設(shè)問(wèn)題轉(zhuǎn)為數(shù)學(xué)函數(shù)尋優(yōu)問(wèn)題,使用反映衛(wèi)星定位性能的衛(wèi)星觀測(cè)質(zhì)量指標(biāo)建立目標(biāo)函數(shù),現(xiàn)有VB布設(shè)原則作為約束條件,使用改進(jìn)的遺傳算法求解VB最佳布設(shè)位置。

(3)在采用遺傳算法求解VB布設(shè)優(yōu)化問(wèn)題時(shí),引入了TOPSIS算法實(shí)現(xiàn)目標(biāo)函數(shù)的轉(zhuǎn)換,降低了算法求解的復(fù)雜度,提高了求解效率;引入了麻雀算子改進(jìn)標(biāo)準(zhǔn)遺傳算法,提高了算法收斂速度和局部尋優(yōu)能力。

4 驗(yàn)證與分析

4.1 實(shí)驗(yàn)線路及數(shù)據(jù)準(zhǔn)備

本文采用2018年8、9月在京沈高鐵(朝陽(yáng)—沈陽(yáng)西段)現(xiàn)場(chǎng)采集的衛(wèi)星定位數(shù)據(jù)對(duì)所提出的VB布設(shè)方法進(jìn)行驗(yàn)證分析。試驗(yàn)線路途徑朝陽(yáng)、北票、烏蘭木圖、阜新、黑山北、新民北、沈陽(yáng)西7個(gè)車站,存在隧道15座,鐵路沿線環(huán)境具有明顯的多樣性。列車運(yùn)行線路見(jiàn)圖5。

圖5 京沈線列車運(yùn)行線路

列車在線路上運(yùn)行時(shí),其定位模式包括單GPS、單BDS以及GPS和BDS組合定位,為確保數(shù)據(jù)充足,避免因樣本不足導(dǎo)致軌道片誤分類的情況發(fā)生,本次仿真實(shí)驗(yàn)疊加了三種定位模式(多天、多趟列車往返數(shù)據(jù)),共有364 611條觀測(cè)信息。根據(jù)線路軌道電子地圖數(shù)據(jù),以10 m為間隔進(jìn)行等間隔劃分軌道片,共劃分為25 087個(gè)軌道片。利用以上數(shù)據(jù),按照本文所述方法進(jìn)行虛擬應(yīng)答器選址布局設(shè)計(jì),并從場(chǎng)景聚類和布局優(yōu)化兩個(gè)方面進(jìn)行具體分析。

4.2 場(chǎng)景聚類方法驗(yàn)證

根據(jù)軌道片位置和定位信息確定每個(gè)軌道片的導(dǎo)航衛(wèi)星觀測(cè)信息,設(shè)置衛(wèi)星仰角閾值為5°、信噪比閾值為30 dB、邊界衛(wèi)星帶寬為10°,約簡(jiǎn)閾值為3°,確定可見(jiàn)衛(wèi)星和邊界衛(wèi)星,圖6(a)顯示了1號(hào)軌道片的所有可見(jiàn)衛(wèi)星、邊界衛(wèi)星以及擬合可見(jiàn)天空輪廓的情況,圖6(b)顯示了其邊界特征,可以看出,該軌道片周圍環(huán)境較為開(kāi)闊,能夠支持較高的衛(wèi)星定位性能水平,光滑樣條的擬合結(jié)果可以較好的描繪出軌道片上空可見(jiàn)輪廓的細(xì)節(jié),且僅使用12個(gè)邊界特征點(diǎn)便足以表示1號(hào)軌道片的可見(jiàn)天空輪廓,相比于約簡(jiǎn)前邊界特征,約簡(jiǎn)率達(dá)到96.6%。圖7顯示了全線天空可見(jiàn)度的分布情況,局部視圖中顯示了所選線路隧道出入口附近的可見(jiàn)天空輪廓。

圖6 1號(hào)軌道片衛(wèi)星天空?qǐng)D及其邊界特征

圖7 全線天空可見(jiàn)度

為定量分析約簡(jiǎn)算法在全部軌道片的約簡(jiǎn)情況,圖8給出了約簡(jiǎn)最大誤差Dmax和約簡(jiǎn)率的統(tǒng)計(jì)結(jié)果,可見(jiàn),所有軌道片的約簡(jiǎn)誤差的最大值均未超過(guò)預(yù)設(shè)的約簡(jiǎn)閾值,在衛(wèi)星信號(hào)全遮擋區(qū)域,可見(jiàn)天空輪廓約簡(jiǎn)為兩個(gè)邊界特征點(diǎn),約簡(jiǎn)率達(dá)到99.4%,且約簡(jiǎn)誤差保持在較低水平。

圖8 全線邊界特征的約簡(jiǎn)誤差和約簡(jiǎn)率

利用所得邊界特征,進(jìn)行基于DTW距離度量的場(chǎng)景聚類。圖9顯示了所選兩個(gè)軌道片的“最小距離”路徑,其中間圖形的顏色表示對(duì)應(yīng)序列位的距離,所選兩個(gè)軌道片的邊界特征長(zhǎng)度不等,通過(guò)特征序列匹配,得到其DTW距離為70.415 2°。

圖9 所選兩個(gè)軌道片的“最小距離”路徑示意

本文設(shè)置每類至少包含100個(gè)樣本,即DBSCAN算法的領(lǐng)域密度閾值MinPts為100,根據(jù)聚類算法內(nèi)部評(píng)價(jià)指標(biāo)確定領(lǐng)域半徑ε,所選指標(biāo)有緊密性(CP)、間隔性(SP)和戴維森堡丁指數(shù)(DBI),其中,CP是類內(nèi)每一樣本到類中心的平均距離,該值越小,類內(nèi)距離越近;SP是類中心的平均距離,該值越大,類間距離越遠(yuǎn);DBI計(jì)算任意兩類的類內(nèi)平均距離之和除以兩聚類中心距離的最大值,該值越小意味著類內(nèi)距離越小,同時(shí)類間距離越大。表4顯示了不同預(yù)設(shè)參數(shù)下評(píng)價(jià)指標(biāo)的統(tǒng)計(jì)結(jié)果,可見(jiàn),當(dāng)MinPts為100、ε取40時(shí),類內(nèi)距離較小,類間距離較大,綜合聚類性能較好,因此,確定ε為40,最佳聚類簇?cái)?shù)為3。

表4 聚類算法內(nèi)部評(píng)價(jià)指標(biāo)

圖10顯示了定位場(chǎng)景在線路上的分布情況,其中,場(chǎng)景1代表開(kāi)闊場(chǎng)景,場(chǎng)景2代表全遮擋場(chǎng)景,場(chǎng)景3代表部分遮擋場(chǎng)景。圖11為線路典型場(chǎng)景的邊界特征。存在橋梁遮擋的線路被識(shí)別為全遮擋場(chǎng)景,橋梁附近存在部分遮擋和開(kāi)闊場(chǎng)景的交替;存在叢林遮擋的線路被識(shí)別為開(kāi)闊場(chǎng)景或部分遮擋場(chǎng)景;存在隧道的線路被識(shí)別為全遮擋場(chǎng)景,在隧道出入口處由于隧道所在方向可能存在部分遮擋,被識(shí)別為部分遮擋場(chǎng)景或開(kāi)闊場(chǎng)景;存在路塹的線路部分,由于遮擋高度不同,存在部分遮擋場(chǎng)景和開(kāi)闊場(chǎng)景的交替,總體而言,算法聚類結(jié)果符合預(yù)期。表5顯示了各場(chǎng)景數(shù)量以及場(chǎng)景內(nèi)衛(wèi)星觀測(cè)質(zhì)量指標(biāo)的統(tǒng)計(jì)結(jié)果,其中,場(chǎng)景2為全遮擋區(qū)域,不存在衛(wèi)星觀測(cè)質(zhì)量指標(biāo),各場(chǎng)景之間具有較為明顯的差異。

表5 場(chǎng)景屬性統(tǒng)計(jì)

圖10 線路場(chǎng)景分布

4.3 布局優(yōu)化方法驗(yàn)證

根據(jù)多次試驗(yàn)以及對(duì)場(chǎng)景聚類結(jié)果的統(tǒng)計(jì),設(shè)置區(qū)段延拓參數(shù)Fmax為5、Lmax為1 000 m,進(jìn)行區(qū)段延拓,確定布設(shè)區(qū)段。圖12顯示了全線區(qū)段分布情況。全線共分為31個(gè)區(qū)段,其中,受限區(qū)段有6個(gè),累積長(zhǎng)度約為138.29 km。

圖12 全線區(qū)段延拓所得分布結(jié)果

根據(jù)CTCS-3級(jí)列控系統(tǒng)應(yīng)答器應(yīng)用原則和區(qū)段延拓結(jié)果,在開(kāi)闊區(qū)段和極端區(qū)段采用等間隔1 500 m布設(shè)策略分別布設(shè)虛擬應(yīng)答器和實(shí)體應(yīng)答器,在受限區(qū)段采用優(yōu)化策略(最小布設(shè)間隔為200 m,最大布設(shè)間隔為1 500 m)確定布設(shè)方案?？紤]到相鄰區(qū)段的銜接部分,在不改變受限區(qū)段布設(shè)結(jié)果的情況下,以盡量減小布設(shè)數(shù)量且滿足布設(shè)距離要求為目標(biāo)調(diào)整臨近區(qū)段的相鄰應(yīng)答器位置,表6和圖13顯示了基于局域定位場(chǎng)景聚類的VB布局結(jié)果,全線共216個(gè)應(yīng)答器。

表6 全線應(yīng)答器布設(shè)結(jié)果統(tǒng)計(jì)

本文重點(diǎn)關(guān)注在受限區(qū)段基于改進(jìn)遺傳算法的VB布局優(yōu)化方法。設(shè)置種群規(guī)模pop=20,交叉概率為0.9、變異概率為0.1,迭代次數(shù)為250代,以第3個(gè)區(qū)段為例,該區(qū)段長(zhǎng)度為12.307 km,圖13局部視圖顯視了其線路上VB的布設(shè)情況。

圖14顯示了該區(qū)段所有軌道片的貼合度統(tǒng)計(jì)結(jié)果,區(qū)段的邊界是隧道的出入口附近,衛(wèi)星定位性能較差,其所在軌道片的衛(wèi)星觀測(cè)質(zhì)量指標(biāo)較差,貼合度較低,而中間部分軌道片遮擋程度較輕,其貼合度較大,但存在波動(dòng)。表7為布局優(yōu)化后該區(qū)段VB布設(shè)距離和布設(shè)位置貼合度的統(tǒng)計(jì)結(jié)果,可見(jiàn),VB布設(shè)距離均滿足要求,且布設(shè)位置的貼合度較高。

圖14 區(qū)段軌道片貼合度統(tǒng)計(jì)

為驗(yàn)證本文所提改進(jìn)遺傳算法在求解VB布局優(yōu)化問(wèn)題時(shí)的性能,選取標(biāo)準(zhǔn)遺傳算法(Simple Genetic Algorithm, SGA)和自適應(yīng)遺傳算法(Adaptive Genetic Algorithm, AGA)[15]進(jìn)行對(duì)比分析,三種算法設(shè)置相同的參數(shù)和初始種群。圖15和圖16分別顯示了三種算法在迭代到28次和250次,VB的分布情況。

圖15 第28次迭代

圖16 第250次迭代

由圖15和圖16可知,在第28次迭代時(shí),三種算法的虛擬應(yīng)答器布設(shè)數(shù)量和布設(shè)位置存在差異,在250次迭代后,三種算法的VB布設(shè)數(shù)量均已收斂,但布設(shè)位置仍存在差異,導(dǎo)致布設(shè)方案貼合度不同,體現(xiàn)了三種算法在尋優(yōu)能力方面的差異。圖17統(tǒng)計(jì)了迭代過(guò)程中虛擬應(yīng)答器數(shù)量以及方案貼合度均值,可見(jiàn),在收斂速度方面,本文所提方法的收斂速度最快,算法迭代28次后基本收斂,SGA和AGA算法收斂速度較慢;在尋優(yōu)能力方法,本文所提方法求解的VB布設(shè)方案貼合度均值最大,為0.905 6,SGA和AGA算法所求方案的貼合度均值較小?？傮w而言,本文所提出的方法在VB布局優(yōu)化方面優(yōu)于SGA和AGA算法。

5 結(jié)論

本文針對(duì)虛擬應(yīng)答器的布局需求,提出一種基于局域定位場(chǎng)景聚類的虛擬應(yīng)答器布局優(yōu)化方法,從鐵路沿線環(huán)境遮擋情況出發(fā),根據(jù)列車歷史定位數(shù)據(jù),重構(gòu)鐵路沿線衛(wèi)星可見(jiàn)天空輪廓,完成局域定位場(chǎng)景聚類方法;采用區(qū)段延拓思想確定VB布設(shè)區(qū)段,在受限區(qū)段,采用改進(jìn)的遺傳算法優(yōu)化VB布局。本文所述方法結(jié)合了現(xiàn)有應(yīng)答器布設(shè)原則,充分考慮了線路上候選VB位置的衛(wèi)星可見(jiàn)性特征,避免了因衛(wèi)星定位性能不足,引起VB捕獲誤差較大的風(fēng)險(xiǎn),相比沿線使用GNSS進(jìn)行連續(xù)定位的苛刻要求,只需保證VB布設(shè)位置的衛(wèi)星定位性能支撐條件,所提出的方法解決了VB功能實(shí)現(xiàn)的本質(zhì)能力保障問(wèn)題。

論文后續(xù)工作將進(jìn)一步關(guān)注線路衛(wèi)星定位性能的精細(xì)分類方法,引入多目標(biāo)優(yōu)化策略進(jìn)一步提高VB布局優(yōu)化能力,并結(jié)合實(shí)際數(shù)據(jù)測(cè)試檢驗(yàn)所提出的方法對(duì)VB捕獲判定與報(bào)文觸發(fā)時(shí)空性能的影響。