基于室內(nèi)動(dòng)靜結(jié)合分割的射線跟蹤加速方法

黃一航，江 虹，韓 賓

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

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

0 引言

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

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

1 射線跟蹤算法工作機(jī)制

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

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

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

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

計(jì)算出終點(diǎn)場(chǎng)強(qiáng)Etotal后，接收點(diǎn)處的接收功率Pr可由式（3）［9］計(jì)算：

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

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

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

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

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

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

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

反射向量vRe由式（6）計(jì)算：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 方法分析

2.4.1 時(shí)間復(fù)雜度

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

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

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

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

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

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

2.4.2 空間復(fù)雜度

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

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

3.1 驗(yàn)證改進(jìn)算法精確度

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

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

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

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

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

3.2 驗(yàn)證改進(jìn)算法高效性

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

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

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

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

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

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

圖9 仿真時(shí)間波動(dòng)圖Fig.9 Fluctuation graph of simulation time

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

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

2）無(wú)分割的傳統(tǒng)射線跟蹤算法因?yàn)樾枰櫟纳渚€數(shù)量確定，且每次對(duì)碰撞點(diǎn)的檢索都是檢索全區(qū)域，所以在該情況下A、B、C三個(gè)基站點(diǎn)的求交次數(shù)相同。但由于三個(gè)基站所處的位置不同，所以經(jīng)過(guò)的路徑不會(huì)相同，算法運(yùn)行的總時(shí)間會(huì)有一定差異。

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

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

當(dāng)然，在減少算法計(jì)算時(shí)間的同時(shí)也需要保證計(jì)算的精度。對(duì)本文的三維射線跟蹤加速方法，因?yàn)樯渚€與物體的相交點(diǎn)并不會(huì)發(fā)生改變，所以算法的精確度不會(huì)受到影響。

3.3 實(shí)驗(yàn)分析

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

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