基于地形分區(qū)的射線跟蹤法加速方法的研究

李朋朋，陳亞洲，石 丹，高攸綱

（北京郵電大學(xué) 電子工程學(xué)院，北京 100876）

引言

隨著現(xiàn)代信息技術(shù)的快速發(fā)展，武器裝備信息化的程度不斷提高，大量的電子信息裝備使得開放的戰(zhàn)場空間中的電磁信號非常密集，形成了極為復(fù)雜的電磁環(huán)境，無線電傳播的環(huán)境越來越復(fù)雜。精確預(yù)測電波傳播特性在戰(zhàn)場信息化上顯得尤為重要。

射線跟蹤法是在幾何光學(xué)理論、幾何繞射理論和一致繞射理論基礎(chǔ)上發(fā)展起來的，為獲得有用的仿真結(jié)果提供了精確的特定點方法，被廣泛應(yīng)用于電磁環(huán)境仿真中[1-3]。然而傳統(tǒng)的射線跟蹤法雖然能夠適應(yīng)復(fù)雜環(huán)境的電波預(yù)測，但是計算量巨大導(dǎo)致計算效率降低，因此提高射線跟蹤法的計算效率成為大量學(xué)者的研究重點。在開放的地理環(huán)境中主要考慮的是射線與地面求交點的運算時間消耗，該部分耗時最大，針對這樣的問題，本文提出一種減少射線與地面相交點個數(shù)的算法，同時在計算機程序中使用多線程技術(shù)來提高射線跟蹤法的計算效率。

1 射線跟蹤理論基礎(chǔ)

1.1 射線跟蹤法基本思想

射線跟蹤法的基本思想是將從源點輻射出的電磁波看作一條條射線，能量在各自獨立的射線管內(nèi)傳播。對每一條射線的傳播進行追蹤，直到射線到達目標(biāo)點或射線能量低于需要考慮限度時，在這過程中計算出射線的能量，求得所有到達場點的射線后，采用矢量疊加的方法得出輻射源的影響[4]。射線在傳播過程中，遇到障礙物時發(fā)生反射或繞射，根據(jù)鏡面反射原理和一致性繞射原理計算出反射點和繞射點處的場強。射線的場強衰減到預(yù)先設(shè)置的閾值后，放棄跟蹤本條射線，繼續(xù)跟蹤下一條射線。可見射線跟蹤過程是一個復(fù)雜的遞歸過程。

在接收點出的場強（單位：dB）可表示為：

式（1）中n為到達接受點的射線數(shù)量，Ei為第i條到達接受點射線的場強矢量。Ei由下式計算：

1.2 影響射線跟蹤法的因素

1）輻射源發(fā)射的射線數(shù)目，它決定了需要跟蹤的射線數(shù)目，計算發(fā)射射線數(shù)目的公式是n=2π/φ，其中φ為發(fā)射張角，因此發(fā)射張角的大小直接影響射線跟蹤法的運算效率。

2）地形環(huán)境的復(fù)雜程度決定了射線求交運算的運算次數(shù)，從而影響射線跟蹤法的運算效率。

3）當(dāng)射線碰到地形面時，將會發(fā)生反射或繞射現(xiàn)象，此時反射及繞射系數(shù)的經(jīng)度對射線跟蹤法的運算效率也會產(chǎn)生影響。

在上述的因素中，發(fā)射張角是固定不變的，即輻射源發(fā)射的射線數(shù)目通常是不變的，而反射及繞射系數(shù)也是固定不變的，因此地形復(fù)雜程度就決定了發(fā)射點及繞射點所需要的求交運算次數(shù)。地形越復(fù)雜，需要的求交運算的次數(shù)越多，并且大多數(shù)求交運算是需要舍棄的無用運算。因此，大量無用的求交運算就是影響射線跟蹤法運算效率的主要因素[6-7]。

2 地形分區(qū)

由射線跟蹤法的過程可知，射線與地形發(fā)生碰撞后會反射和繞射，只有確定碰撞交點才能繼續(xù)跟蹤射線。在傳統(tǒng)的射線跟蹤法中，需要射線與地形面進行求交運算才能確定反射點或者繞射點，當(dāng)?shù)匦蚊姹容^復(fù)雜的時候，這種求交運算就會很費時，并且繞射點的增多將進一步增加射線的數(shù)量和求交運算的次數(shù)。本文提出對地形分區(qū)的思想，將減少求交運算的次數(shù)，提高計算的效率。

2.1 地形的組成

本文所采用的地形是由數(shù)字高程模型（DEM）轉(zhuǎn)化而成的地形文件，它采用了三角網(wǎng)格剖分技術(shù)，將地形面由多個三角面組成近似表示。之所以采用三角剖分技術(shù)，是因為三角剖分技術(shù)是眾多技術(shù)中最科學(xué)的表達方式之一，也是最常用的一種技術(shù)。由于我們只能獲取DEM數(shù)據(jù)文件，因此要轉(zhuǎn)化成三角網(wǎng)格地形面需要一定的算法提取高程值進行三角面構(gòu)造。

2.1.1 DEM數(shù)據(jù)解析

在構(gòu)造地形面之前，我們必須提取DEM中的高程數(shù)據(jù)，因此我們必須了解DEM中數(shù)據(jù)的組織形式。

通常我們能夠獲取到的DEM數(shù)據(jù)為1°×1°的格式，其數(shù)據(jù)組織方式如圖1。

圖1 DEM Data Organization

從圖1中可以看到數(shù)據(jù)是以點矩陣的形式存儲的，在文件中存儲的順序是從Pt1點開始將每一列映射到文件中的一行數(shù)據(jù)。文件中的第一行會存儲一些關(guān)于該地形的信息，比如說西南角和東北角坐標(biāo)（經(jīng)緯度），數(shù)據(jù)的行數(shù)和列數(shù)，間隔秒數(shù)等。在圖1中可以看出DEM數(shù)據(jù)X和Y方向的采樣點間隔為3秒（約70米，不同地區(qū)長度不同），形成一個三秒網(wǎng)格。文件中除了第一行外，其余全部由采樣點相對應(yīng)的高程值組成。

2.1.2 地形的構(gòu)造

根據(jù)DEM數(shù)據(jù)存儲的規(guī)律我們可以輕松的編程提取到高程值和地形坐標(biāo)范圍，但是如何存儲這些數(shù)據(jù)使它們能夠便利的構(gòu)成三角面？

在本文中設(shè)計了一種文件按照一定的格式來存儲這些數(shù)據(jù)，定義為ter文件。Ter文件中的數(shù)據(jù)按照一定的規(guī)律存儲，且要能夠表示出三角面的組成元素，即三個頂點坐標(biāo)，以和來標(biāo)記一個三角面，其中間存儲三個頂點的坐標(biāo)。在提取高程值的時候需要完成采樣點坐標(biāo)值的計算和轉(zhuǎn)換，由經(jīng)緯度坐標(biāo)轉(zhuǎn)換為笛卡爾坐標(biāo)，可以由公式得到。

式中phi為緯度，theta為經(jīng)度。

對應(yīng)圖1數(shù)據(jù)的三角面的組織形式如圖2所示，一個三秒網(wǎng)格對應(yīng)兩個三角面。

根據(jù)上述的三角面的組織形式，地形就可以從DEM中轉(zhuǎn)化出來。本文在C++編程環(huán)境下調(diào)用OpenSG圖形開發(fā)標(biāo)準(zhǔn)庫開發(fā)出顯示界面，地形顯示效果如圖3所示。

圖3表明，通過DEM轉(zhuǎn)換出來的ter文件可以通過OpenSG開發(fā)的界面近似的顯示出地形的態(tài)勢，表示該轉(zhuǎn)換過程的有效性。

2.2 地形的分區(qū)

傳統(tǒng)的射線跟蹤法要求計算出射線與碰撞面的反射點和繞射點才能繼續(xù)跟蹤射線路徑，由于輻射源位置及射線的方向性的不可知性，通常求射線與地形某個三角面的交點需要遍歷判斷整個地形的每個三角面與射線是否相交。若相交，判斷交點是否在三角面內(nèi)的過程，直到得到滿足條件的結(jié)果。然后從這些交點中求出射線方向的上離輻射源最近的一個交點即得到正確的結(jié)果。

雖然這種算法可以滿足需求并得到滿意的結(jié)果，但是其復(fù)雜度為O(N)，其中N為組成地形的三角面的個數(shù)。對于小的地形該算法可以滿足快速計算，但是對于由上十萬個三角面組成的大地形而言，該算法將耗時過長。另外程序需要計算上千條射線，因此該算法的計算量巨大，影響計算效率。

本文提出一種優(yōu)化求交點速度的算法，基本思想是通過研究射線的方向特性減少需要判斷是否相交的三角面的個數(shù)，從而減少計算的時間復(fù)雜度，達到提高計算速度的目的。具體的實現(xiàn)步驟如下：

1）已知輻射源的坐標(biāo)和輻射源發(fā)出的射線的方向向量。通過查找輻射源坐標(biāo)的位置，可以將地形分為四塊，如圖4(a)所示。

2）根據(jù)輻射源發(fā)射的射線的方向向量可以判斷射線將向某個方向射出，因此射線只與該方向區(qū)域內(nèi)的三角面有相遇的可能，如圖4(b)所顯示的區(qū)域。

3）再根據(jù)射線的X和Y向量形成的夾角進一步縮小射線可能經(jīng)過的三角面的范圍，如圖4(c)所顯示的區(qū)域。

圖2 三角面組織形式

圖3 地形顯示

4）由于輻射源處于地形面上，因此有一定的高度，根據(jù)射線方向向量的Z向量判斷射線是空間向上還是空間向下射出，由此再縮小可能相交的三角面的個數(shù)，只計算比輻射源高或低的三角面即可。

理論上經(jīng)過以上步驟可以將需要計算的三角面的個數(shù)平均減少至原算法的 ，從而將算法的計算效率提高至原算法的16倍。

3 多線程技術(shù)的使用

3.1 多線程概念

多線程是指從軟件或者硬件上實現(xiàn)多個線程迸發(fā)執(zhí)行的技術(shù)。具有多線程能力的計算機因有硬件支持而能夠在同一時間執(zhí)行多于一個執(zhí)行緒，進而提升整體處理性能。多線程處理可以同時運行多個線程。由于多線程應(yīng)用程序?qū)⒊绦騽澐殖啥鄠€獨立的任務(wù),因此可以在以下方面顯著提高性能:

1）多線程技術(shù)使程序的響應(yīng)速度更快 ,因為用戶界面可以在進行其它工作的同時一直處于活動狀態(tài)；

2）當(dāng)前沒有進行處理的任務(wù)時可以將處理器時間讓給其它任務(wù)；

3）占用大量處理時間的任務(wù)可以定期將處理器時間讓給其它任務(wù)；

4）可以隨時停止任務(wù)；

5）可以分別設(shè)置各個任務(wù)的優(yōu)先級以優(yōu)化性能。

3.2 多線程的實現(xiàn)

圖4

在復(fù)雜電磁環(huán)境中，往往存在著多個發(fā)射機與多個接收機。發(fā)射機之間的電磁干擾可忽略，接收機處的電場強度可由輻射源獨立產(chǎn)生的電場強度的疊加得到。

設(shè)有N個輻射源，每個輻射源Tn在接收機R處產(chǎn)生的電場為En，En在x、y、z方向上的分量分別為Enx、Eny、Enz。疊加后的總磁場為E,E在x、y、z方向上的分量分別為Ex、Ey、Ez,?？捎晒?5)-(7)得到疊加后接收機R處的電場。

另外還有研究意義的是電場強度的幅值，可由公式（8）得到

由公式可以得出，一個接收機接收到的由同一頻段所有發(fā)射機發(fā)射的電場強度的幅值的平方可以分解為該接收機接收到的每一個發(fā)射機的電場強度的實部之和與虛部之和的平方和。這就為多線程的使用提供了一定的理論基礎(chǔ)。

部分實現(xiàn)代碼如下：

一般情況下，使用多線程技術(shù)提高的效率與cpu的核數(shù)有正比的關(guān)系，如cpu是N核處理器，那么使用多線程可以將計算效率提高近N倍。

4 仿真分析

為了驗證上述加速方法的有效性，選取多塊不同三角面?zhèn)€數(shù)的地形分別使用傳統(tǒng)射線跟蹤法和本文所提出的方法進行求交運算，比較兩種方法仿真所需要求交的面數(shù)和使用的時間。為了方便比較，我們均將反射源的點設(shè)置在地形的中心，進行200條不同方向射線的求交計算。使用的仿真平臺為Intel i5處理器，1G內(nèi)存，VS2010，OpenSG。

比較結(jié)果如表1所示。

從表1中可以得到以下結(jié)論：

1）改進方法需要計算相交的面數(shù)比傳統(tǒng)方法所需要的面數(shù)少，當(dāng)?shù)匦慰側(cè)敲鏀?shù)越多越明顯。

2）由于需要計算的相交的面數(shù)少，所以在計算時間上改進方法比傳統(tǒng)方法所需時間少。

3）當(dāng)?shù)匦稳敲孑^少時，兩種方法計算時間上沒有太大的差距，而隨著三角面數(shù)量增多這種差距就明顯了。

4）由于計算的面數(shù)與輻射源的位置有一定的關(guān)系，可能導(dǎo)致計算的時間與傳統(tǒng)方法有時相差不大，但是平均來說，改進方法所需的計算時間總是比傳統(tǒng)方法少，且地形越復(fù)雜越是明顯。

當(dāng)然，提高計算速度的同時也要保證計算的精度，不過在本算法中并不會影響到精度，因為兩種方法中射線與地形相交的點并不會發(fā)生改變，那么就不會影響下一次射線的計算，所以精度并沒有受到影響。

表1 傳統(tǒng)方法與加速方法仿真所需求交面數(shù)和使用時間比較

5 結(jié)論

本文根據(jù)分析射線的特性提出一種將地形分區(qū)的方法，該方法可以減少求交運算中需要運算的面的個數(shù)，從而減少了計算求交運算的時間；同時使用多線程技術(shù)提高計算機資源利用率，并在多核cpu下提高計算效率。仿真比較結(jié)果表明，該方法在復(fù)雜的地形中可以有效地減少計算量，降低計算的時間，提高了射線跟蹤法的計算效率，因此有一定研究意義。

[1] Torres R P, Valle L, Domingo M, Loredo S.An efficient raytracing method for radio propagation based on the modif ed BSP algorithm.Vehicular Technology Conference,1999.P 1967～1971.

[2] LIU Hai-tao, LI Bin-hong, XIE Yong, QI Dong-sheng. Parallel raytracing algorithm and its application for propagation prediction in urban micro cellular environments[J]. CHINESE JOURNAL OF RADIO SCIENCE ,2004,19(5):P 581～585.

[3] 劉斐. 電波傳播射線追蹤法的研究[J]. 信息與電腦,2011, 2, P160.

[4] Chen Shin-Hon, Jeng Shyh-kang.An SBR/Image approach for radio wave propagation indoor environments with metallic furniture[J].IEEE Transaction on Antennas and Propagation,1997,45（1）:P 98-106.

[5] Tan S Y, Tan H S. A microcelluar communications propagation model based on the uniform theory of diffraction and multiple image theory[J]. IEEE Transactions on Antennas and Propagation,1996,44（10）:P 1317-1326.

[6] 袁正午，黎意超，李林，沐維. 基于動態(tài)分區(qū)的射線跟蹤加速方法[J].計算機工程與應(yīng)用, 2010, 46（27): P 77-79.

[7] 董金梁,金榮洪,耿軍平,王偉. 改進射線跟蹤法效率的新方法[J].微波學(xué)報 2006, 22(6):P6-9.