射線跟蹤技術的一種加速算法

周曉平 譚鳳杰 柳朝陽 鄒 澎

(1.鄭州大學信息工程學院，河南 鄭州 450052； 2.鄭州大學數學系，河南 鄭州 450052)

引 言

電波傳播的準確預測對微蜂窩無線網絡規劃、設計和優化、基站選址和架設高度的選定、無線定位等都起著非常重要的作用，因而成為現代移動通信技術研究的熱點之一.預測模型主要分為兩類：統計模型和確定性模型.統計模型是經過對大量的測量數據進行統計分析得出的經驗公式.一方面測量需要耗費大量的人力、物力和財力，另一方面由于微小區、微微小區等的出現，使不同小區之間的統計相似性消失，致使統計模型失效.確定性模型主要有射線跟蹤、時域有限差分、MEI等方法.其中射線跟蹤法根據幾何光學理論和一致性繞射理論，跟蹤直射線、反射線、繞射線等，尋找出收發之間所有的射線路徑.然后，根據電波傳播理論可以計算出每條射線的幅度、相位、延遲和極化等參數，并將通過各路徑傳來的電波進行矢量疊加就可以確定接收到的場強.

相對于FDTD算法，射線跟蹤技術計算量較小，相對于MEI算法射線跟蹤技術能進行三維計算，并且能考慮地形、地貌、地物等實際因素的影響，模擬多徑傳播路徑，進行矢量疊加，故本文采用射線跟蹤技術進行微小區電波傳播預測.對于復雜的建筑物環境，直接遍歷求解射線與面、劈、頂點的交點時，計算量極大，需要采用合適的射線跟蹤加速算法.近年來，國內外學者提出的主要的加速算法有二元空間分區[1]、空間體積分區[1,3-4]和角度的z緩存區[5](angular z-buffer，AZB)、鏡像法[6-7,9]、并行計算模型[8-11]等加速算法.

角度z緩存區算法的基本思路是把源或等效源所看見的空間分成角域，把角域所包含的多面體面儲存在該角域中，并且按照它們與源或等效源的距離遠近進行排序，對于進入該角域的射線，按照距離遠近順序進行與多面體面相交測試，若存在合理的交點，就不需再與排在其后的多面體面做相交測試，這樣就可以減少必須做的相交測試數量.但是，這種算法是在空間內進行分區，并且當遇到反射等效源及繞射等效源時必須重新分區，同時在處理繞射問題時需要運用射線基坐標系，導致編程實現時比較復雜并且計算量也比較大，限制了跟蹤速度的提高.

本文對AZB進行一些改進，對多面體在投影平面(地面上)內進行二維分區，在三維空間內進行跟蹤，采用比背面采集算法計算量小的算法來排除被多面體自身遮擋的面、棱，及采用一種新算法對多面體進行排序.最后運用此改進算法，給出了微小區電波傳播預測實例，并將預測結果與實測結果進行比較，一致性良好，證明了該算法的可行性.

1 射線跟蹤角度緩存區改進算法

下面從輻射空間分區、拋棄自身遮擋的面及棱、前后排序、垂直平面內遮擋測試、水平棱繞射線跟蹤等算法入手，對傳統的角度緩存區算法進行一些改進，使其更易于程序實現，計算量更小，運算速度更快.城市中的建筑物大多數為平頂的多面體，故認為所討論的繞射棱都垂直于或平行于地面.

下文中多面體指建筑物，輻射源指廣義輻射源，即包括真實輻射源和等效輻射源，接收點指廣義接收點，即包括真實接收點和等效接收點.射線跟蹤過程中某次反射點或繞射點是上一級輻射源(包括等效輻射源)的等效接收點，同時也是下一次反射、繞射的等效輻射源.

1.1 基本方法

一輻射源位于空間中某點，以輻射源在地平面上的投影O為坐標原點，x、y坐標軸位于地平面上，以多面體的高度方向為z軸，建立直角坐標系O(x，y，z).則接收點的投影及空間中的多面體的底面均在xoy平面內.

1.1.1 基于平面內斜率角的射線搜索算法

1) 角扇區內多面體的搜索：設輻射源輻射空間內的第i個多面體底面的頂點與坐標原點的連線的最大、最小斜率分別為αi，max、αi，min，根據所有多面體的斜率將xoy平面分成若干個角扇區，盡量保證角扇區內的多面體的完整性，設第j個角扇區邊線的斜率角為βj，max、βj，min.通過比較αi，max、αi，min和βj，max、βj，min的關系可以判斷出某角扇區內包含的多面體.為了將不含多面體的角形區域排除掉，角扇區不一定相等.

2) 自身遮擋面、棱的判斷：某反射面的法線向量用km表示，反射面輻射空間中的某多面體面的法線向量用kn表示，如果km·kn≥0，則該多面體面被多面體自身遮擋，否則，該面可以被源照射到，要搜尋的反射點和繞射點都位于該面及其棱上.通過這種方法可以拋棄多面體自身遮擋的面及棱，至少可以減小三分之一的計算量.

入射波能照射到的面和其上平行于地面及垂直于地面的棱為有效面、棱.

3) 排序算法：對于角扇區內多面體m與多面體n，設多面體m底面頂點與坐標原點之間連線斜率最大的連線OAm，max對應的角度為αm，max，斜率最小的連線OBm，min對應的角度為αm，min.對于多面體n有OAn，max、αn，max，OBn，min，αn，min.對于接收點，αm，max=αm，min，點Am，max與Bm，min重合.

如果αn，max≥αm，max，αm，min≥αn，min，則求出連線An，maxBn，min與連線OAm，max(或OBm，min)的交點C到源點O的距離dOC及dOBm，max(或dOBm，min).如果dOC≥dOAm，max(dOBm，min)，則多面體m比多面體n離源近，否則多面體n離源近.

如果αn，max≥αm，max，αn，min≥αm，min，則求出點Am，max和Bn，min到源點O的距離dOAm，max和dOBn，min，如果dOBn，min≥dOAm，max，則多面體m離源近，反之，多面體n離源近.

否則，兩多面體之間無關，不需排序.

1.1.2 輻射源與接收點之間射線的遮擋測試

在接收點所在的角扇區中，對排列在輻射源與接收點之間的多面體，按照從前往后的順序，首先在xoy平面內找到某多面體上可能遮擋射線的多面體面，然后僅對此面在垂直平面內做遮擋測試.具體算法是：對于某多面體，如果輻射源投影和接收點投影之間連線的斜率不在某多面體面投影的兩個端點與輻射源投影之間連線的斜率之間，則該多面體面不遮擋輻射源到接收點之間的射線，否則該多面體面可能遮擋射線，只需對這種多面體面做遮擋測試，這樣至少可以減小一半的計算量.

求可能遮擋射線的多面體面與射線的交點，如果交點不在該多面體面內，則該多面體面沒有擋住射線，繼續對下一個多面體面進行判斷；如果交點在該多面體面內，則該多面體擋住了射線，拋棄該射線.只要有一個多面體面擋住了射線，則排在該多面體后面的多面體無需再做遮擋測試.這樣可以更進一步減少計算量.如果輻射源與接收點之間的建筑物都沒有擋住射線，則該射線有效.

1.2 直射線、反射線、繞射線的跟蹤

1.2.1 直射線、一次入射線、地面反射線的跟蹤

直射線、一次入射線的輻射源為發射天線，輻射區域為全空間，直射線的接收點為接收天線，入射線的接收點在多面體面或棱上.應用1.1.1的算法搜索有效反射面、繞射棱，并將其存入數據庫中.

1) 對于直射線:找到接收天線所在的角扇區，根據1.1.2的算法對排列在發射天線與接收天線之間的多面體按順序進行遮擋測試，如果沒有多面體擋住直射線，則直射線有效.

2) 對于入射線:該數據庫供一次反射線、繞射線跟蹤使用.

3) 對于地面反射線:找到接收天線所在的角扇區，根據鏡像原理，求出地面反射點，首先判斷地面反射點是否在該角扇區內的某多面體底面內，如果在，則地面反射點無效，否則根據1.1.2的算法對排列在發射天線與地面反射點間的多面體依次進行入射線、反射線遮擋測試，如果沒有多面體擋住射線，則地面反射有效.

1.2.2 反射線的跟蹤

有效反射面將空間分成了兩個區域，一個是輻射源所在的區域，另一個是輻射源鏡像所在的區域.連接輻射源對于一次有效反射面的鏡像的投影與該反射面投影的兩端點，則兩條連線與反射面的投影線之間的區域(輻射源所在的那一部分)就是反射面的角扇區，在此角扇區內的多面體能被反射射線照射到.

1) 一次有效反射：如果接收天線位于反射面的角扇區內，則根據鏡像原理，求出一次反射點，根據1.1.2的算法依次對入射線、反射線進行遮擋測試，如果都未被遮擋，則一次反射有效.

2) 一次反射線成為二次反射或繞射的入射線：應用1.1.1的算法確定一次反射能照射到的有效多面體面及棱，并存入數據庫中，成為二次反射、繞射的有效輻射源.供二次反射線、繞射線跟蹤使用.

1.2.3 繞射射線的跟蹤

1) 繞射棱的角扇區

對于垂直棱，將1.2.1中的有效垂直棱當作新的輻射源，他所在的多面體拐角的外角區域為其輻射空間，當外角超過90°時，將其劃分成幾個角扇區，否則角扇區就取為外角.

對于水平棱，如圖1所示，求出源到水平棱的垂足G1，根據垂足的位置，可以將繞射線所能照射到的多面體所在的區域，分成2種情況：

圖1 繞射線照射空間

② 如圖1(b)所示，垂足G1在水平棱兩端點之外，過離垂足G1近的端點A作垂直于水平棱AB的平面AA′CC′，該平面將全空間分為兩個區域.取端點A為等效輻射源，由Keller 錐體2可知，輻射區域為水平棱AB所在的區域，對該區域再分角扇區.

位于角扇區中的某多面體，如果xoy平面內的頂點都滿足km·kn≤0且高度低于該水平棱，則不能被繞射線照射到，否則多面體能被水平棱繞射線照射到，如圖1所示.把不能被照射到的多面體排除掉，可以進一步減小計算量.

2) 跟蹤射線

① 一次有效繞射：對于接收天線所在的角扇區，根據幾何繞射理論，求出一次繞射點，根據1.1.2的算法依次對入射線、繞射線進行遮擋測試，如果都未被遮擋，則一次繞射有效.

② 一次繞射線成為二次反射或繞射的入射線：應用1.1.1的算法確定一次繞射能照射到的有效多面體面及棱，并存入數據庫中，成為二次反射和繞射的有效輻射源.供二次反射線、繞射線跟蹤使用.

1.3 多次反射、繞射射線的跟蹤

與上述算法類似，可以找到兩次以上的反射面、繞射棱，追蹤到多次反射、多次繞射、及多次反射繞射的混合射線.

2 場強精確算法

尋找到所有的射線路徑之后，根據輻射理論、反射定理及幾何繞射理論，可以求得直射、反射及繞射場強.

移動通信基站天線的架設方式比較復雜，不但有三副天線而且帶有下傾角及±45°極化角.其他用途天線的架設可以看成是它的特例，所以以移動通信基站為例研究場強的精確算法.

為了精確計算場強，必須考慮發射天線的下傾角、極化、波在傳播過程中的極化面的改變等實際因素，由此需要建立以建筑物為參考的建筑物直角坐標系，以發射天線為參考的三個發射天線球面坐標系、直角坐標系，以射線為參考的若干個射線基坐標系[3].

算法思路是：對于遠區的接收點，一般認為發射天線輻射球面波，所以首先將入射場強由發射天線球坐標系轉換到發射天線直角坐標系，然后再變換到追蹤到的入射線的射線基坐標系，根據反射場強公式[5]、繞射場強公式[4]分別計算出反射射線基坐標系、繞射射線基坐標系下的反射場、繞射場，由于不同的射線路徑的射線基坐標方向不同，故需將場強再變換到發射天線直角坐標系，完成一副發射天線的場強合成，再將合場強轉換到建筑物直角坐標系，最終將三副天線的場強統一到建筑物直角坐標系進行合成.

3 計算實例及結果分析

根據前面所論述的算法，對兩個運營中的移動通信基站(GSM1800)周圍小區中的射線進行跟蹤及進行場強預測.由于所研究場景的占地面積較大，無法拍攝到全景圖，故文中只列出了場景示意圖.假設傳播環境為平坦地、建筑物的表面是光滑平面.計算中，建筑物εr=4.5，σ=0.025 S/m，地面εr=5，σ=0.002 S/m.將位于所討論環境中的建筑物及接收天線稱作目標，軟件采用Matlab實現，運算流程如圖2所示.

圖2 主程序流程圖

為了驗證算法的有效性，測試點應選擇在沒有汽車停放及基底場強小的地方.測量設備為SRM3000.

3.1 實例1-鄭州大學柳園22號樓頂的通信基站

該基站周邊建筑物均為四面體，如圖4所示，基站安裝在建筑物1的樓頂上，三副天線參數：發射功率20 W，增益18 dB，下傾角6°，極化±45°，架高35.1 m，第三副北偏東58°，距桅桿140 cm，第一副北偏西58°，距桅桿145 cm，第二副南偏東71°，距桅桿148 cm，接收點高1.03 m.測試頻率為1 839 MHz.

該基站的西北角300 m左右處有另一個基站，且兩個基站之間都是低矮建筑，致使本基站西北角附近基底場比較大，不能在此選點.在建筑物1的西、南、東、北方向各選10個點進行測量與計算，圖3示出40個點的預測場強與實測結果對比曲線，圖4示出其中四個測試點(第10、14、24、39點)的射線跟蹤路徑結果.

圖3 實例1-預測場強與實測結果的對比

(a) 10點坐標(-59，0，1.03)

(b) 14點坐標(-21，-21，5，1.03)

(c) 24點坐標(21，6，1.03)

(d) 39點坐標(-17，33，1.03)圖4 實例1-四個測試點的射線跟蹤結果

3.2 實例2-鄭州大學南校區圖書館周邊小區

該基站周圍建筑物1、4為12面體，2、3、5為6面體，如圖6所示，基站位于建筑物1樓頂，三副天線參數為：發射功率20 W，增益18 dB，下傾角8°，±45°極化，架高28 m，第一副正西，第二副東偏北60°，第三副東偏南60°，三副天線距桅桿均為35 cm，接收點高1.1 m.測試頻率為1 835 MHz.

該基站周邊環境比較復雜，距該基站300 m左右的北方、西南方各有一基站，導致這些方向基底場比較大，不能選點.且本基站周圍停放的大、小汽車較多，致使可選的測試點不多.在該基站東面、南面各選12個點進行測試與計算，圖5示出24個點的預測場強與實測結果對比曲線，圖6示出其中兩個測試點的射線跟蹤結果.

3.3 結果分析

每個觀察點都有很多射線到達，如圖4、6所示，有很多點沒有直射線到達，只有繞射線，如圖4(a)、(c)所示，計算場強與測試場強差別很小，說明多徑反射、多徑繞射對場強的貢獻很大，不可忽略.

很多觀察點沒有三次以上的反射線和繞射線到達，如圖4、圖6所示，說明三次以上的反射線和繞射線出現的可能性較小，并且經過多次反射、繞射衰減使其對場強的貢獻較小，可以忽略.

從圖3、圖5可以看出，實測值和計算值之間的誤差在0.06～4.9 dB之間，實例1標準誤差為2.834 6 dB，實例2標準誤差為3.588 dB，誤差較小，符合工程上的精度要求，說明運用該角度緩存區改進算法可以準確有效地預測小區環境中場強分布.

圖5 實例2-預測場強與實測結果的對比

(a) 1點坐標(-43.43，12.93，1.1)

(b) 14點坐標(11.97,-31.07,1.1)圖6 實例2-兩個測試點的射線跟蹤結果

為了驗證該算法的運算速度，運用傳統的角度緩存區算法對這兩個基站也進行了計算，結果表明改進算法的運算速度提高了1倍左右.

由于忽略了樹木、線桿、停放的汽車、自行車等、建筑物表面的粗糙度等引起的繞射與散射、及電參數的近似等，使實測值與計算值有微小的誤差.

4 結 論

本文基于平面內直線斜率對廣義輻射源輻射空間進行分區、對廣義輻射源與廣義接收點之間的建筑物進行前后排序、對被建筑物自身遮擋和建筑物之間互相遮擋的面及棱做出判斷等，從而實現對傳統的角度緩存區算法的改進.在場強的計算中也考慮了天線架設的實際因素.運用本文算法對兩個通信基站環境中的場強進行了計算，同時用傳統的角度緩存區算法也進行了計算，結果顯示，本文提出的改進算法運算速度提高了一倍.另外對環境中的場強也進行了測量，測量結果與計算結果誤差小于5 dB，說明該算法可以搜索到天線到接收機之間所有的傳播路徑，而且運算效率較高.本文所開發的軟件可以運用于電磁環境測評.

[1] 吳志忠.移動通信無線電波傳播[M].北京:人民郵電出版社，2002．

[2] 汪茂光.幾何繞射理論[M].西安:西安電子科技大學出版社，1985．

[3] 程 勇，吳劍鋒，曹 偉.一種用于移動系統場強預測的準三維射線跟蹤模型[J].電波科學學報，2002，17(2)：15l-159．

CHENG Yong，WU Jianfeng，CAO Wei.A quasi 3-D ray-tracingmodel for field prediction in mobile systems[J].Chinese Journal of Radio Science，2002，17(2)：151-159.(in Chinese)

[4] 楊晉生，胡自勝，陳為剛.射線跟蹤中三維矢量數據庫建立方法[J].電信科學，2012，28(2)：110-114．

YANG Jinsheng，HU Zisheng，CHEB Weigang.A method of building 3D vector database for ray tracing[J].Telecommunications Science，2012，28(2)：110-114.

[5] CATEDRA M F，PEREZ J，SAEZ DE ADANA F，et al.Efficient ray-tracing techniques for three-dimensional analyses of propagation in mobile communications：application to picocell and microell scenarios[J].IEEE Antennas and Propagation Magazine，1998，40(2)：15-27．

[6] 袁正午，楊青宏，沐 維.一種改進的鏡像射線跟蹤方法[J].計算機工程，2012，38(3)：60-62．

YUAN Zhengwu，YANG Qinghong，mu Wei.improved image ray tracking method[J].Computer Engineering，2012，38(3)：60-62.(in Chinese)

[7] 袁正午.移動通信系統終端射線跟蹤定位理論與方法[M].北京:電子工業出版社，2007．

[8] 王利東，李朝奎，陶建軍，等.基于.NET Remoting的射線跟蹤并行計算模型[J].計算機應用，2011，31(10)：2603-2605．

WANG Lidong，LI Chaokui，TAO Jianjun，et al.Parallel ray tracing model based on NET remoting[J].Journal of Computer Application，2011，31(10):2603-2605.(in Chinese)

[9] ATHANAILEAS T E，ATHANASIADOU G E，TSOULOS G V，et a1.Parallel radio-wave propagation modeling with image-based ray tracing techniques[J].Parallel Computing，2010，36(12)：679-695．

[10] 劉海濤，黎濱洪，謝 勇.并行射線跟蹤算法及其在城市電波預測的應用[J].電波科學學報，2004，19(5)：581-585．

LIU Haitao LI Binhong, XIE Yong，et a1.Parallel ray-tracing algorithm and its application for propagation prediction in urban microceilular environments[J].Chinese Journal of Radio Science，2004，19(5)：581-585.(in Chinese)

[11] 楊錦輝，張 文.一種基于三維射線彈跳法的并行電磁傳播預測算法[J].裝備指揮技術學院學報，2010，21(6)：91-96．

YANG Jinhui，ZHANG Wen.A new parallel radio propagation prediction algorithm based on 3D SBR technique[J].Journal of the Academy of Equipment Command & Technology，2010，21(6)：91-96.(in Chinese)