黃一航，江 虹，韓 賓

（西南科技大學(xué)信息工程學(xué)院，四川綿陽 621010）

（*通信作者電子郵箱491938847@qq.com）

0 引言

信息通信技術(shù)的快速發(fā)展，特別是5G時代帶來了通信頻率的提高、室內(nèi)基站以及智能天線等技術(shù)的應(yīng)用，使得對預(yù)測電磁波傳播的精確性有了更高的要求。

射線跟蹤（Ray Tracing，RT）算法是基于幾何光學(xué)理論、幾何繞射理論和電磁理論的確定性預(yù)測模型［1］，廣泛應(yīng)用于電磁傳播仿真中。傳統(tǒng)的射線跟蹤算法在復(fù)雜的密閉三維環(huán)境模型下應(yīng)用［2］能夠提高算法精確性，但是成倍增加的無用求交次數(shù)會導(dǎo)致計算效率大幅度降低［3］。因此，業(yè)界一直在尋求如何大幅度降低無用交點的求解次數(shù)，以在保證射線跟蹤算法精確性的同時能提高運算的效率。

1 射線跟蹤算法工作機制

射線跟蹤算法是通過模擬電磁波的傳播路徑，來確定多徑信道在發(fā)射與接收機之間傳播過程中所有可能存在的路徑［4］?；舅枷胧菍脑袋c輻射出的電磁波模擬為一條條射線，電磁在各自獨立的射線管［5］內(nèi)傳播。依次沿著各條射線路徑進行跟蹤，判斷射線是否碰到物體表面或者被接收點所接收。若射線遇到障礙物會發(fā)生反射、透射、繞射和散射現(xiàn)象，根據(jù)幾何光學(xué)理論和一致性繞射原理［6］計算出各空間傳播機制發(fā)生后的場強。跟蹤射線直到場強衰減到預(yù)設(shè)閾值［7］，停止對本條射線跟蹤。求得到達接收點的所有射線后，使用矢量疊加的方法計算出輻射源傳遞到目標(biāo)位置的信號值。

在目標(biāo)接收點處的總場強（單位：V/m）可表示為：

其中：接收點處矢量合并后的總輻射場強用Etotal表示；l為射線路徑總條數(shù)；Ei為第i條射線路徑末場的矢量場強。矢量場強Ei由式（2）［8］計算：

其中：Einc是射線在第一個反射、繞射或透射節(jié)點處的矢量輻射場；n為出現(xiàn)反射的總次數(shù)；Rh是在第h次反射時的并矢反射系數(shù)；m為出現(xiàn)繞射的總次數(shù)；Df是在第f次繞射時的并矢繞射系數(shù)；u為出現(xiàn)透射的總次數(shù)；Tt是在第t次透射時的并矢透射系數(shù)；As是經(jīng)過反射透射或繞射后的擴散因子；rq是跟蹤的射線的第q個傳播節(jié)點到第q+1 個節(jié)點的距離，q為跟蹤的信道總的空間傳播機制節(jié)點數(shù)。

計算出終點場強Etotal后，接收點處的接收功率Pr可由式（3）［9］計算：

其中：Pt為發(fā)射天線輻射功率；Gt和Gr分別為發(fā)射天線和接收天線增益；λ為由電磁波頻率計算出的發(fā)射天線工作波長；E0為發(fā)射點處初始電場強度。

由以上理論分析可知，影響射線跟蹤算法預(yù)測精度和計算效率的因素主要有以下方面：

1）射線源發(fā)射的射線數(shù)量和射線之間的角度，決定了算法的預(yù)測精度。理論上發(fā)射間隔越小、跟蹤的射線數(shù)量越多以及射線之間分布得越均勻，模擬電磁波傳播的仿真算法就會越精確。本文使用相同大小正方形無縫覆蓋單位球面的方式建立發(fā)射源［10］。

其中：（Vx，Vy，Vz）是需要跟蹤的射線方向向量vt；Δθ是相鄰射線間的角度，遍歷n和m值即可得到所有射線的方向。因此間隔角度直接決定了射線源發(fā)射的射線數(shù)量。

因為跟蹤一條完整的射線需要多次遍歷所有的三維環(huán)境數(shù)據(jù)，所以當(dāng)跟蹤的射線數(shù)量越多，功率預(yù)測值雖然會更精確，但也將導(dǎo)致算法運行時長大幅增加。

2）空間內(nèi)物體的數(shù)量與環(huán)境復(fù)雜程度決定了求交點運算次數(shù)的多寡。跟蹤某一射線的基本步驟，是將該射線與檢索范圍內(nèi)所有的物體表面進行求交點計算，找到交點坐標(biāo)后再計算出相應(yīng)的反射向量。因此跟蹤的射線為了找到一個正確的碰撞點需要進行多次求交計算以預(yù)先找到多個交點坐標(biāo)，而在這些交點中只有距起點Pstart最近的碰撞點是有效的碰撞點Pc和反射向量。即信號在傳播過程中第一個碰撞到的障礙物交點是有效的，其余的求交點計算都是無用的運算。有效交點坐標(biāo)Pc可以由式（5）計算得到：

其中：D是根據(jù)相似三角原理計算得到的射線起點Pstart到交點之間的距離；v是射線起點與三維面內(nèi)任意一點的向量；vt是跟蹤射線的方向向量；n是三維面的法向量。

反射向量vRe由式（6）計算：

在整個射線跟蹤算法運算中，只有能被接收點接收，且在射線傳播路徑中碰撞到正確三維表面的求交點計算才是有效計算，其余的交點計算都是無用運算。所以大量無用求交點運算導(dǎo)致了較低的計算效率。

在上述影響因素中，一般在達到精度要求后射線的間隔角大小是固定不變的，即發(fā)射源發(fā)射的射線數(shù)量通常不變。因此環(huán)境復(fù)雜程度（障礙物分布情況）主要決定了求交運算的次數(shù)。而隨著環(huán)境復(fù)雜度的提高，無用求交運算次數(shù)所占的比例會大幅度增加。所以，減少算法中大量的無用求交運算是提高計算效率的主要途徑。

2 基于三維空間分割的加速方法

在傳統(tǒng)的射線跟蹤算法中，正在跟蹤的射線向量需要與環(huán)境模型內(nèi)所有物體的三維表面進行求交點的運算［11］。隨著環(huán)境復(fù)雜度的提高，繞射發(fā)生次數(shù)隨之增加，使得算法需要跟蹤更多的射線。并且環(huán)境復(fù)雜度和總射線數(shù)量的提高都會使得算法求交運算的次數(shù)大幅提升。

為此，文獻［12］中提出了一種基于動態(tài)分區(qū)的射線跟蹤加速方法。該方法根據(jù)環(huán)境模型內(nèi)的障礙物分布情況動態(tài)劃分區(qū)域，可減少射線與建筑物求交點次數(shù)；但是該方法只考慮了二維模型，不適合三維環(huán)境模型。因此，文獻［13］中提出了使用正向發(fā)射與反向鏡像混合的方法對原始射線跟蹤算法進行改進；但該加速方法只是單純改進了算法的計算方式，沒有考慮到環(huán)境復(fù)雜度提高對算法計算效率的負增益。

因此，本文提出了基于靜態(tài)空間分割與動態(tài)空間分割相結(jié)合的方法對三維環(huán)境模型進行空間分割，旨在大幅減少求交運算次數(shù)，有效提高算法的計算效率。

2.1 靜態(tài)三維空間分割的加速方法

對三維環(huán)境模型進行靜態(tài)空間分割，是將一個大區(qū)域平均劃分為多個小分區(qū)以分攤區(qū)域中物體的數(shù)量，形成n級區(qū)域分割方式：一級分割將大區(qū)域平均劃分為四部分；二級分割是將已經(jīng)分割后的區(qū)域再次平均劃分；后續(xù)的高級分割以此類推。射線跟蹤每次只在射線當(dāng)前所在分區(qū)Nold中檢索碰撞點，若在該分區(qū)沒有碰撞點，則射線離開當(dāng)前分區(qū)Nold進入到下一個分區(qū)Nnew，并在Nnew內(nèi)繼續(xù)檢索碰撞點，直到跟蹤的射線到達接收位置或信號衰落權(quán)重超過預(yù)設(shè)閾值為止。如圖1所示為空間分割方法流程。

對大區(qū)域進行空間分割后，檢索碰撞點的算法將不需要和大區(qū)域內(nèi)所有的物體表面進行求交點運算，只需在當(dāng)前射線所在的小分區(qū)中進行碰撞檢索，這樣可以大幅度減少跟蹤一條射線所需檢索的碰撞點的次數(shù)。

因此，正確判斷射線當(dāng)前所在的分區(qū)，是靜態(tài)空間分割方法的關(guān)鍵。如式（7）所示：

其中：Nold為射線當(dāng)前所在的分區(qū)序號；Nnew為射線將要進入的分區(qū)序號；n為空間分割等級；Pc為射線碰撞點坐標(biāo)；x和y是射線三維方向向量中的x值與y值。

圖1 空間分割方法流程Fig.1 Method flow of space segmentation algorithm

當(dāng)射線的碰撞點Pc在分區(qū)的邊界上時，可根據(jù)式（7）計算得出射線下一次范圍檢索的正確分區(qū)序號。

理論上對空間分割得越細，求交點運算計算量減少得越多，算法的效率也會越高。但是每細分一次區(qū)域不可避免會增加8 條分區(qū)的邊界面，且一個三維物體通常為6 個表面，因此，當(dāng)一個小分區(qū)中包含物體的表面數(shù)量少于等于6 條時就不能再細分區(qū)域。

圖2（a）是沒有進行空間分割加速的無線傳播三維建模俯視圖，使用的是原始射線跟蹤算法對傳播過程進行跟蹤仿真。內(nèi)部矩形部分是三維環(huán)境中各物體的三維模型俯視圖，內(nèi)部線條是跟蹤算法跟蹤到的能從信號發(fā)射端到接收端的無線三維信道模型，該模型可以作為后續(xù)對改進加速方法模型精確度的對比驗證模型。圖2（b）是靜態(tài)一級空間分割的三維俯視效果圖，使用一級射線跟蹤加速方法對無線信道進行跟蹤。在同一個三維環(huán)境模型下和圖2（a）的原始跟蹤算法作對比驗證，可以看出兩張俯視效果圖中無線信道三維模型的數(shù)量和布局都一致，所以各級的靜態(tài)加速方法沒有降低算法的精確性。

圖2 環(huán)境空間分割俯視圖Fig.2 Vertical views of environmental space division

2.2 動態(tài)結(jié)合靜態(tài)的三維空間分割的加速方法

在三維環(huán)境下，雖然單獨使用靜態(tài)空間分割可以大幅提高計算效率。但在某些特殊情況下，靜態(tài)分割方法提升算法效率的作用會失效。如圖3 所示，當(dāng)跟蹤射線的相鄰兩個碰撞點間橫跨了多個小分區(qū)時，由于算法會遍歷橫跨的各小分區(qū)中所有的物體面，所以無用求交運算的比例將逐漸接近傳統(tǒng)的射線跟蹤算法，使得在該情況下算法的計算效率并沒有獲得提高。

圖3 射線一次性穿越多個小分區(qū)情況Fig.3 Ray traversing multiple small divisions at once

因為射線跟蹤是在三維環(huán)境中進行，所以上述特殊情況發(fā)生的原因大概率是跟蹤射線的該段傳播高度過高，超越了其所在小分區(qū)物體的最高高度，不能在小分區(qū)內(nèi)形成碰撞點。所以兩個相鄰碰撞點之間可能將跨越多個分區(qū)。

為了改善以上問題，本文在靜態(tài)空間分割的基礎(chǔ)上設(shè)計了一種基于高度劃分的動靜結(jié)合分割方法。實際密閉環(huán)境下的障礙物都會有一個最高高度，所以可以根據(jù)如下方式設(shè)計動靜結(jié)合的空間分割，以進一步提高算法效率：

1）原始三維環(huán)境區(qū)域內(nèi)所有物體高度的集合為h，則根據(jù)式（8）動態(tài)空間分割的閾值hd應(yīng)是該區(qū)域內(nèi)最高物體的高度值。

2）假設(shè)密閉空間高度為H，將整個三維環(huán)境模型根據(jù)分割閾值hd動態(tài)分割為上下兩部分：上半部分空間合并劃分為一整塊空白區(qū)域；下半部分空間依舊使用靜態(tài)空間分割的方式劃分區(qū)域。

3）與靜態(tài)空間分割類似，實現(xiàn)該方法需要正確識別跟蹤的射線當(dāng)前所在的分區(qū)序號。如式（9）所示：

其中：Nnew為射線將要進入的分區(qū)序號；為射線碰撞點所在的高度；z為射線三維方向向量中高度值；u為上半部分分區(qū)序號；d為下半分區(qū)中某靜態(tài)小分區(qū)序號，根據(jù)后續(xù)遍歷法判斷射線具體進入的小分區(qū)。

動靜結(jié)合的分割方法可以最大限度地提高算法的計算效率。當(dāng)只有靜態(tài)空間分割時，跟蹤某些角度的射線時，檢索一個碰撞點可能一次會穿越多個小分區(qū)，如此造成的無用求交檢索也會較多，導(dǎo)致計算效率大幅降低。因此本文使用對高度的動態(tài)分割方法結(jié)合靜態(tài)的空間分割改進了算法的不足。如圖4 所示，上升的射線進入動態(tài)分割的上半分區(qū)，只需檢索一個上半分區(qū)便可替代原本靜態(tài)方法需要檢索的多個小分區(qū)，找到下一個碰撞點位置，大大減少了無用面與射線的求交運算次數(shù)。在圖4 的三維環(huán)境模型下，此加速方法的算法效率在靜態(tài)法已經(jīng)提升的基礎(chǔ)上還會有9.8%左右的提高。

圖4 靜態(tài)與動態(tài)空間分割Fig.4 Static and dynamic space divisions

2.3 分區(qū)實現(xiàn)

本文的空間分割方法使用了四叉樹的原理［14］。四叉樹是一棵重力平衡樹，通過對目標(biāo)根節(jié)點空間進行平均四分，直至滿足預(yù)測條件停止，最終形成一棵層次分明的樹?？臻g分割步驟如下：

1）對真實環(huán)境建立模型后，獲取環(huán)境模型的二維投影數(shù)據(jù)，通過坐標(biāo)平移，使投影數(shù)據(jù)中最小位置點置于坐標(biāo)原點，形成初始大區(qū)域。

2）檢索環(huán)境模型中所有物體的高度確定最大值，該值作為動態(tài)分割的動態(tài)閾值。

3）對動態(tài)分割后的下半部分區(qū)域做靜態(tài)空間分割。初始平均劃分為2×2排列的4個子分區(qū)并排序（如圖5所示），然后統(tǒng)計各分區(qū)中物體數(shù)量。

4）若子分區(qū)內(nèi)的物體總數(shù)大于預(yù)設(shè)閾值，則該子分區(qū)返回步驟3）繼續(xù)進行靜態(tài)分割，直到所有分區(qū)內(nèi)物體數(shù)量小于閾值。

5）動態(tài)與靜態(tài)空間分割完成后，判斷環(huán)境中每個物體分別所屬的小分區(qū)序號，采用遍歷法判斷。

上述空間分割方法實現(xiàn)的重要一步，是確定空間內(nèi)各物體所屬小分區(qū)，一旦出現(xiàn)位置誤判，最終計算所得的仿真結(jié)果將會和真實數(shù)據(jù)相去甚遠。本文使用遍歷法來精確判斷物體所在的小分區(qū)：物體棱邊的平面線段與分割邊界做交點計算判斷交點所在分區(qū)，若無交點則判斷線段在分割邊界的哪一側(cè)，進而確定物體所在小分區(qū)。

以圖5 所示的一級靜態(tài)分割為例，使用式（10）判斷物體的棱邊線段所屬的小分區(qū)，進而判斷物體所在的分區(qū)序號。N為線段所在的分區(qū)序號，X為指向坐標(biāo)x軸正方向的分割邊界單位向量，Y為指向坐標(biāo)y軸正方向的分割邊界單位向量，L為兩分割線交點指向棱邊線段上任意一點的方向向量。

更高級分區(qū)的相關(guān)判斷以及式（9）中d序號的確立沿用上述公式的衍生公式。

圖5 靜態(tài)空間分割排序示意圖Fig.5 Schematic diagram of sorting for static space division

2.4 方法分析

2.4.1 時間復(fù)雜度

根據(jù)上述加速方法實現(xiàn)流程，分析得到加速方法跟蹤一條射線的計算時長T由以下幾個部分構(gòu)成：1）時間T1，根據(jù)大環(huán)境中物體的分布情況動態(tài)分割區(qū)域，且將各物體的表面分配到各自所在小分區(qū)中的耗時；2）時間T2，信道射線跟蹤過程中與物體表面進行的求交點運算以及進一步計算射線入射、出射向量性質(zhì)的耗時；3）時間T3，跟蹤的射線穿越邊界時判斷進入的下個分區(qū)的耗時；4）時間T4，判斷跟蹤的射線是否能被接收區(qū)域接收的耗時；5）時間T5，計算接收區(qū)域信道傳播特性的耗時。則可知：

然而，由于需要跟蹤的射線數(shù)量龐大，加速方法是一個多層循環(huán)運算，且T1和T5只需一次計算即可得到結(jié)果，所以T1和T5在時間復(fù)雜度中所占的比例極小，可以忽略不計。

假設(shè)大環(huán)境中總的物體表面?zhèn)€數(shù)為n、動態(tài)分割出了g個小分區(qū)，即可知各個小分區(qū)中平均擁有的物體表面?zhèn)€數(shù)為n/g。因為T2中主要的運算是射線遍歷所在小分區(qū)中所有物體表面進行求交點等相關(guān)計算，若跟蹤一條射線與一個物體表面做相關(guān)計算耗時為k1，那么分區(qū)中一次求交點計算的耗時為(n/g) ×k1。假設(shè)檢索到一個射線碰撞點平均需要遍歷v個小分區(qū)，且一條射線從開始到停止跟蹤平均需要檢索m個碰撞點，則時間T2為：

T3中的主要運算是當(dāng)射線與分區(qū)中物體都沒有交點時，根據(jù)射線方向向量一次判斷進入的下一個分區(qū)。假設(shè)相關(guān)的操作耗時為k2，則時間T3為：

T4中的主要運算是每次檢索到碰撞點后，判斷射線是否能被接收區(qū)域所接收。假設(shè)相關(guān)的操作耗時為k3，則時間T4為：

相對于T3和T4，T2的耗時占了絕大部分時間，這首先是因為求交點等相關(guān)運算的計算過程復(fù)雜，而其他耗時部分的主要運算過程相對比較簡單，因此使得k1遠大于k2和k3；其次，則因為T2同時與大環(huán)境中總的物體表面?zhèn)€數(shù)n、發(fā)生一次空間傳播機制平均需要遍歷的分區(qū)個數(shù)v以及重復(fù)檢索空間傳播機制的次數(shù)m都相關(guān)，且物體表面?zhèn)€數(shù)n不與T3和T4相關(guān)，且其數(shù)值遠大于v和m的值。因此，可以忽略T3和T4，則加速方法的時間復(fù)雜度T可表示為：

2.4.2 空間復(fù)雜度

從加速方法的實現(xiàn)流程可知，加速方法的空間復(fù)雜度可以類似于時間復(fù)雜度，運算時的內(nèi)存占用絕大部分是跟蹤的射線與分區(qū)中的物體表面進行的求交點計算，且循環(huán)多個分區(qū)。因此，整個加速方法的空間復(fù)雜度S可表示為：

3 仿真與結(jié)果分析

3.1 驗證改進算法精確度

首先驗證改進算法相對于原始算法結(jié)果的精確性。改進算法可應(yīng)用在任意三維空間環(huán)境模型，且復(fù)雜度越高改進算法提升效率比越高。對如圖6 所示的AB路徑進行功率預(yù)測值的對比仿真，各射線跟蹤算法運行時原始數(shù)據(jù)都相同。本次驗證的環(huán)境模型為12 m×12 m×4 m 的立方體結(jié)構(gòu)，內(nèi)部有18 個障礙物模型：9 個高度為2 m 的障礙物模型與9 個高度為2.5 m 的障礙物模型，共有105個需要遍歷的物體表面。射線發(fā)射源發(fā)射頻率60 MHz，發(fā)射源與接收點均為全向天線［15］，發(fā)射源間隔角為1.8°可向四周不同方向均勻發(fā)射2 萬條射線，物體墻面介電常數(shù)為4.5［16］。起點A坐標(biāo)為（-5.5，3，1），止點B坐標(biāo)為（3.5，-3，1），總長約為10.8 m。在該路徑上有55 個預(yù)測仿真點，間隔為0.2 m。仿真使用Intel i7 處理器，8 GB內(nèi)存，Matlab仿真平臺。

圖6 用于驗證算法改進前后功率預(yù)測值的仿真路徑Fig.6 Simulation path for verifying power prediction values before and after algorithm improvement

圖6所示AB路徑上55個射線發(fā)射點，分別使用原始的射線跟蹤算法和改進算法之間做預(yù)測對比分析。從圖7 兩種算法的功率折線圖可以看出，原始跟蹤算法與改進跟蹤算法的折線圖幾乎重合。在同一個三維環(huán)境模型下，跟蹤路徑AB上各發(fā)射點發(fā)射出的模擬射線，使用改進算法的預(yù)測折線與使用原算法的預(yù)測折線差距非常小，僅在仿真位置39 位置處改進后的算法功率比原始算法高了0.03 dBm，偏差很小，誤差在合理范圍內(nèi)，可視為精確仿真。

由圖7 的折線圖可以驗證，改進后的跟蹤算法幾乎沒有降低原始算法的預(yù)測精確度。

圖7 在路徑AB上使用原算法和改進算法的功率預(yù)測值對比Fig.7 Comparison of power prediction values using original algorithm and improved algorithm on path AB

3.2 驗證改進算法高效性

在同一個三維環(huán)境模型下驗證射線跟蹤加速方法的高效性。選取圖8 中的A、B、C三個位置點作為發(fā)射基站位置，依次使用無空間分割的原始算法、靜態(tài)多級分割方法以及動靜結(jié)合分割的改進方法運行仿真。

圖8 改進算法高效性驗證的基站天線分布Fig.8 Distribution diagram of base station antennas for improved algorithm efficiency verification

在驗證對比中除了各空間分割方法不同以外，其余的所有初始數(shù)據(jù)、方法都相同。多次運行記錄不同跟蹤算法的總運行時間與總求交次數(shù)的數(shù)據(jù)，結(jié)果如表1所示。

表1 高效性對比驗證結(jié)果Tab.1 Efficiency comparison and verification results

因為射線跟蹤算法以及本文的加速方法都是電磁仿真中的確定性仿真模型，所以多次重復(fù)運行同一個加速方法，總求交次數(shù)固定不變，而總運算時間會因為電腦CPU 占用等一些客觀因素的影響發(fā)生波動。因此需要對總運算時間做多次仿真，計算均值。圖9 為多次運行原始算法與本文的加速方法對圖8 環(huán)境模型中A基站做信道仿真的總運算時間波動折線圖。

根據(jù)圖9 所示的時間折線圖計算可知，使用原始算法多次重復(fù)仿真后其算法運算時間均值時間為23.172 2 s、標(biāo)準(zhǔn)差為0.056 4 s；使用本文的加速方法的運算時間均值為8.953 8 s、標(biāo)準(zhǔn)差為0.055 5 s。對于不同射線跟蹤加速方法的標(biāo)準(zhǔn)差相差很小，因此客觀因素對仿真時長的影響程度都相同，后續(xù)驗證可使用多次仿真的時間均值來表示各射線跟蹤方法運算的總時間。

圖9 仿真時間波動圖Fig.9 Fluctuation graph of simulation time

比較分析得出以下結(jié)論：

1）動態(tài)與靜態(tài)結(jié)合的空間分割加速效果最優(yōu)，靜態(tài)空間分割次之，傳統(tǒng)的射線跟蹤算法計算效率最差。

2）無分割的傳統(tǒng)射線跟蹤算法因為需要跟蹤的射線數(shù)量確定，且每次對碰撞點的檢索都是檢索全區(qū)域，所以在該情況下A、B、C三個基站點的求交次數(shù)相同。但由于三個基站所處的位置不同，所以經(jīng)過的路徑不會相同，算法運行的總時間會有一定差異。

3）靜態(tài)空間分割若沒有依照環(huán)境密集度情況合理劃分，比如分割等級分的過高，算法的加速效果將變得不明顯，且反而有可能增加運算時間。而恰當(dāng)?shù)撵o態(tài)分割加速方法對比傳統(tǒng)算法，在當(dāng)前環(huán)境模型下的計算效率可以有61.4%以上的提高。

4）使用靜態(tài)與動態(tài)空間分割相結(jié)合的加速方法對比只使用靜態(tài)空間分割的算法，在當(dāng)前環(huán)境模型下的計算效率在已經(jīng)提升的基礎(chǔ)上還會有9.8%左右的提高。

當(dāng)然，在減少算法計算時間的同時也需要保證計算的精度。對本文的三維射線跟蹤加速方法，因為射線與物體的相交點并不會發(fā)生改變，所以算法的精確度不會受到影響。

3.3 實驗分析

使用本文中動態(tài)結(jié)合靜態(tài)空間分割的射線跟蹤加速方法與文獻［12］中提出的改進算法作性能對比分析，都使用圖8所示的三維環(huán)境模型以及A、B、C三個坐標(biāo)源點作為發(fā)射基站位置，且其余仿真參數(shù)都相同。對比結(jié)果如表2所示。

表2 本文的射線跟蹤加速方法與文獻［12］算法對比Tab.2 Comparison between the proposed ray tracing acceleration method and algorithm in literature［12］

根據(jù)上述結(jié)論比較分析后可知，本文使用的加速方法相對于文獻［12］算法在提升射線跟蹤算法運算效率方面有更好的加速指標(biāo)，進一步減少了使用射線跟蹤算法對無線信道傳播仿真的時間。因此，本文的加速方法是一種更快速的仿真算法。

仿真驗證其他的如圖10 所示簡單三維環(huán)境模型，依次使用原始算法、靜態(tài)分割方法以及動靜結(jié)合分割的方法運行仿真，各完整運行50次后得到的平均運算時間數(shù)據(jù)如表3所示。根據(jù)動靜結(jié)合加速方法的空間分割規(guī)則，該模型只能做基本的一次分割，不能再繼續(xù)深入劃分。

圖10 簡單三維環(huán)境模型Fig.10 Simple 3D environment model

表3 最小加速效果驗證結(jié)果Tab.3 Verification results of minimum acceleration effect

從表3可得出以下結(jié)論：

1）動態(tài)與靜態(tài)結(jié)合的空間分割加速效果最優(yōu)，靜態(tài)空間分割次之，傳統(tǒng)的射線跟蹤算法計算效率最差。

2）使用靜態(tài)空間分割的射線跟蹤加速方法對比原始算法計算效率提高了50.2%；而使用靜態(tài)與動態(tài)空間分割結(jié)合的加速方法對比只使用靜態(tài)空間分割的方法，計算效率在已經(jīng)提高的基礎(chǔ)上還能提升8.9%。

3）和3.2 節(jié)中表1 的結(jié)論數(shù)據(jù)對比分析可以驗證，三維環(huán)境越復(fù)雜動靜結(jié)合的加速算法提升計算效率的比例也會越高。

上述結(jié)果表明本文所提出的改進算法不僅可以大幅度地提高原始算法的計算效率，而且?guī)缀鯖]有降低算法的預(yù)測精度。驗證了改進算法的高效性，也很好地改善了射線跟蹤算法模型中預(yù)測精度與計算效率之間的矛盾。

4 結(jié)語

本文使用射線跟蹤算法對空間環(huán)境中無線信號的傳播進行信道仿真與三維建模，并且分析了原始射線跟蹤算法在仿真計算過程中將產(chǎn)生大量的無用求交運算，導(dǎo)致計算效率過低的問題。因此，本文根據(jù)原始算法的不足之處，提出了一種提高計算效率的射線跟蹤加速方法。該方法結(jié)合了動態(tài)空間分割與靜態(tài)空間分割的方法，減少了跟蹤計算過程中的無用求交點次數(shù)，提高了射線跟蹤算法計算效率，降低了算法仿真運算時間。這能為電磁環(huán)境的實時仿真計算提供解決方法，是一種實用的射線跟蹤加速方法。

然而，本文設(shè)計的射線跟蹤改進加速方法有局限性，僅考慮了從減少求交次數(shù)的方面來減少仿真的運行時長。后續(xù)可以嘗試，在保證算法精確性的前提下動態(tài)減少射線發(fā)射端需要跟蹤的射線管數(shù)量，以達到加速射線跟蹤仿真計算的目的。