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

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

引言

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

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

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

1.1 射線跟蹤法基本思想

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

在接收點(diǎn)出的場(chǎng)強(qiáng)（單位：dB）可表示為：

式（1）中n為到達(dá)接受點(diǎn)的射線數(shù)量，Ei為第i條到達(dá)接受點(diǎn)射線的場(chǎng)強(qiáng)矢量。Ei由下式計(jì)算：

1.2 影響射線跟蹤法的因素

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

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

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

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

2 地形分區(qū)

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

2.1 地形的組成

本文所采用的地形是由數(shù)字高程模型（DEM）轉(zhuǎn)化而成的地形文件，它采用了三角網(wǎng)格剖分技術(shù)，將地形面由多個(gè)三角面組成近似表示。之所以采用三角剖分技術(shù)，是因?yàn)槿瞧史旨夹g(shù)是眾多技術(shù)中最科學(xué)的表達(dá)方式之一，也是最常用的一種技術(shù)。由于我們只能獲取DEM數(shù)據(jù)文件，因此要轉(zhuǎn)化成三角網(wǎng)格地形面需要一定的算法提取高程值進(jìn)行三角面構(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ù)是以點(diǎn)矩陣的形式存儲(chǔ)的，在文件中存儲(chǔ)的順序是從Pt1點(diǎn)開始將每一列映射到文件中的一行數(shù)據(jù)。文件中的第一行會(huì)存儲(chǔ)一些關(guān)于該地形的信息，比如說西南角和東北角坐標(biāo)（經(jīng)緯度），數(shù)據(jù)的行數(shù)和列數(shù)，間隔秒數(shù)等。在圖1中可以看出DEM數(shù)據(jù)X和Y方向的采樣點(diǎn)間隔為3秒（約70米，不同地區(qū)長(zhǎng)度不同），形成一個(gè)三秒網(wǎng)格。文件中除了第一行外，其余全部由采樣點(diǎn)相對(duì)應(yīng)的高程值組成。

2.1.2 地形的構(gòu)造

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

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

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

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

根據(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)勢(shì)，表示該轉(zhuǎn)換過程的有效性。

2.2 地形的分區(qū)

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

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

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

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

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

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

圖2 三角面組織形式

圖3 地形顯示

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

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

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

3.1 多線程概念

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

1）多線程技術(shù)使程序的響應(yīng)速度更快 ,因?yàn)橛脩艚缑婵梢栽谶M(jìn)行其它工作的同時(shí)一直處于活動(dòng)狀態(tài)；

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

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

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

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

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

圖4

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

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

另外還有研究意義的是電場(chǎng)強(qiáng)度的幅值，可由公式（8）得到

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

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

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

4 仿真分析

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

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

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

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

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

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

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

當(dāng)然，提高計(jì)算速度的同時(shí)也要保證計(jì)算的精度，不過在本算法中并不會(huì)影響到精度，因?yàn)閮煞N方法中射線與地形相交的點(diǎn)并不會(huì)發(fā)生改變，那么就不會(huì)影響下一次射線的計(jì)算，所以精度并沒有受到影響。

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

5 結(jié)論

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

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

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