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

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

（北京郵電大學 電子工程學院，北京 100876）

引言

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

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

1 射線跟蹤理論基礎

1.1 射線跟蹤法基本思想

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

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

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

1.2 影響射線跟蹤法的因素

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

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

3）當射線碰到地形面時，將會發生反射或繞射現象，此時反射及繞射系數的經度對射線跟蹤法的運算效率也會產生影響。

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

2 地形分區

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

2.1 地形的組成

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

2.1.1 DEM數據解析

在構造地形面之前，我們必須提取DEM中的高程數據，因此我們必須了解DEM中數據的組織形式。

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

圖1 DEM Data Organization

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

2.1.2 地形的構造

根據DEM數據存儲的規律我們可以輕松的編程提取到高程值和地形坐標范圍，但是如何存儲這些數據使它們能夠便利的構成三角面？

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

式中phi為緯度，theta為經度。

對應圖1數據的三角面的組織形式如圖2所示，一個三秒網格對應兩個三角面。

根據上述的三角面的組織形式，地形就可以從DEM中轉化出來。本文在C++編程環境下調用OpenSG圖形開發標準庫開發出顯示界面，地形顯示效果如圖3所示。

圖3表明，通過DEM轉換出來的ter文件可以通過OpenSG開發的界面近似的顯示出地形的態勢，表示該轉換過程的有效性。

2.2 地形的分區

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

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

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

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

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

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

圖2 三角面組織形式

圖3 地形顯示

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

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

3 多線程技術的使用

3.1 多線程概念

多線程是指從軟件或者硬件上實現多個線程迸發執行的技術。具有多線程能力的計算機因有硬件支持而能夠在同一時間執行多于一個執行緒，進而提升整體處理性能。多線程處理可以同時運行多個線程。由于多線程應用程序將程序劃分成多個獨立的任務,因此可以在以下方面顯著提高性能:

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

2）當前沒有進行處理的任務時可以將處理器時間讓給其它任務；

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

4）可以隨時停止任務；

5）可以分別設置各個任務的優先級以優化性能。

3.2 多線程的實現

圖4

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

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

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

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

部分實現代碼如下：

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

4 仿真分析

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

比較結果如表1所示。

從表1中可以得到以下結論：

1）改進方法需要計算相交的面數比傳統方法所需要的面數少，當地形總三角面數越多越明顯。

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

3）當地形三角面較少時，兩種方法計算時間上沒有太大的差距，而隨著三角面數量增多這種差距就明顯了。

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

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

表1 傳統方法與加速方法仿真所需求交面數和使用時間比較

5 結論

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

[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] 袁正午，黎意超，李林，沐維. 基于動態分區的射線跟蹤加速方法[J].計算機工程與應用, 2010, 46（27): P 77-79.

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