楊晉生，胡自勝，陳為剛

（天津大學(xué)電子信息工程學(xué)院 天津300072）

1 引言

射線跟蹤是一種高效的電波傳播特性分析方法，能精確預(yù)測城市微蜂窩以及室內(nèi)場景的場強(qiáng)覆蓋，有效分析多徑強(qiáng)度、到達(dá)角、離開角和時(shí)延等重要的信道特性參數(shù)。近幾年，射線跟蹤已廣泛應(yīng)用于電波傳播預(yù)測、無線網(wǎng)絡(luò)規(guī)劃以及無線定位等方面[1～3]。然而射線跟蹤方法的實(shí)現(xiàn)需要場景的三維矢量數(shù)據(jù)庫，并且計(jì)算復(fù)雜度高。

場景數(shù)據(jù)庫是射線跟蹤計(jì)算的基礎(chǔ)?，F(xiàn)有的三維場景建模方法很多，如基于二維GIS（geographic information system，地理信息系統(tǒng)）的三維建模，該方法雖經(jīng)濟(jì)有效，但精度不高；基于影像的三維建模，該方法精度高，但成本較高，自動(dòng)化建模難度較大；基于激光掃描系統(tǒng)的三維建模，該方法數(shù)據(jù)獲取速度快，實(shí)時(shí)性強(qiáng)，但后期處理工作量很大；CAD三維建模，該方法所需設(shè)備簡單，適合小區(qū)域建模，模型逼真，但工作量大[4]。建立可見元數(shù)據(jù)庫能減少參與射線跟蹤計(jì)算的面和劈的數(shù)量，是降低射線跟蹤計(jì)算復(fù)雜度的有效方法。在三維空間內(nèi)求解可見元復(fù)雜度較高，參考文獻(xiàn)[5]使用掃描線算法通過對場景進(jìn)行水平掃描和垂直掃描來求解可見元，需要進(jìn)行大量線面求交運(yùn)算，計(jì)算復(fù)雜度較高；參考文獻(xiàn)[6]的透視投影法通過空間分區(qū)和投影將三維幾何問題轉(zhuǎn)化到二維平面上處理，降低了復(fù)雜度，但未考慮室內(nèi)場景建模。

本文針對上述問題，提出了一種適用于城市微蜂窩和室內(nèi)場景的三維矢量數(shù)據(jù)庫建立方法。本文研究小區(qū)域場景建模，并且射線跟蹤模型需要的是場景的幾何信息和電磁信息，場景的紋理、光照等信息可以忽略，提出簡化的三維CAD建模方法來獲取城市微蜂窩和室內(nèi)三維場景數(shù)據(jù)庫。為了降低射線跟蹤計(jì)算復(fù)雜度，進(jìn)一步提出了一種適用于室外和室內(nèi)場景的修正透視投影算法來建立三維可見元數(shù)據(jù)庫。基于上述方法對城市微蜂窩和室內(nèi)場景進(jìn)行建模分析表明，提出的方法能有效降低射線跟蹤信道建模方法的計(jì)算復(fù)雜度。

2 射線跟蹤原理

本文研究的射線跟蹤模型是基于反向射線跟蹤方法，根據(jù)幾何光學(xué)原理、GTD （geometrical theory of diffraction，幾何繞射理論）以及 UTD（uniform theory of diffraction，一致性繞射理論），結(jié)合仿真場景三維矢量數(shù)據(jù)庫，考慮電波的反射、繞射以及散射等機(jī)制，追蹤源點(diǎn)（發(fā)射天線）和場點(diǎn)（接收天線）之間的有效射線。

由反向射線跟蹤方法可知，利用射線跟蹤方法進(jìn)行信道建模首先需要三維場景數(shù)據(jù)庫，包括場景內(nèi)對象的幾何信息和電磁特性信息。對場景數(shù)據(jù)庫中所有的面和劈，基于鏡像法原理和GTD計(jì)算出有效的反射點(diǎn)和繞射點(diǎn)。根據(jù)不同傳播模式（直射、反射、繞射以及反射繞射的組合）依次連接源點(diǎn)、反射點(diǎn)/繞射點(diǎn)、場點(diǎn)，若所得的射線與場景中的面均無交點(diǎn)，則完成了對該射線的跟蹤。從上述射線跟蹤的過程中可知，直接使用場景數(shù)據(jù)庫的計(jì)算復(fù)雜度是難以接受的。因此，可以通過建立源點(diǎn)和場點(diǎn)關(guān)于場景的三維可見元數(shù)據(jù)庫來減少參與計(jì)算的面和劈的數(shù)量，提高計(jì)算效率。

3 三維矢量數(shù)據(jù)庫的建立

3.1 三維場景數(shù)據(jù)庫建立方法

3.1.1 場景建模分析

建立三維場景數(shù)據(jù)庫首先需要對不同類型場景進(jìn)行建模分析，通過合理簡化降低建模復(fù)雜度。對于城市微蜂窩，一方面，相對于樹木、湖泊等，建筑物對電波傳播影響最大，因此建模過程中僅考慮建筑物；另一方面，隨著微小區(qū)范圍不斷縮小，建筑物高度不斷增高，天線的高度一般低于城市建筑的平均高度，建筑物頂面對電波傳播的影響較小，因此可將建筑物建模為直棱柱或者直棱柱的組合。對于室內(nèi)場景，可以認(rèn)為由兩部分組成：室內(nèi)物體和室內(nèi)6壁。室內(nèi)物體建模方法與微小區(qū)建筑物的建模方法相同；室內(nèi)6壁包括地面、天花板、墻壁以及墻壁上的門和窗戶等，可以將它們建模為帶有不同電磁參數(shù)的面。

3.1.2 場景三維CAD建模

基于簡化的三維CAD建模方法建立場景數(shù)據(jù)庫步驟如下。

（1）利用 CAD繪制三維場景，并存儲(chǔ)為 DXF（drawing exchange format，繪圖交換格式）文件。對于室外對象和室內(nèi)物體，繪制其底面多邊形以及一條側(cè)棱；室內(nèi)6壁單獨(dú)進(jìn)行繪制。對象的電磁特性信息可通過編輯面的屬性參數(shù)獲得。

（2）提取DXF文件數(shù)據(jù)，建立三維場景數(shù)據(jù)庫。按照步驟 （1）的繪圖方法，三維模型的幾何信息只包含于Header段和Entities段內(nèi)，所以建立室外場景數(shù)據(jù)庫時(shí)只需提取DXF文件中這兩段中數(shù)據(jù)。

3.1.3 場景數(shù)據(jù)庫的數(shù)據(jù)結(jié)構(gòu)

三維場景數(shù)據(jù)庫使用結(jié)構(gòu)體鏈表存儲(chǔ)建模場景詳細(xì)的幾何信息以及電磁信息。數(shù)據(jù)庫Objectdata中存儲(chǔ)的是場景中的對象，每個(gè)對象由該對象的基本信息（cube）以及子對象信息（face、edge、point）組成?；拘畔▽ο蟮拿?、劈以及頂點(diǎn)的總數(shù)；子對象信息包括這些幾何元素的位置坐標(biāo)、拓?fù)潢P(guān)系以及電磁參數(shù)（電導(dǎo)率、磁導(dǎo)率以及介電常數(shù)）。

3.2 三維可見元數(shù)據(jù)庫建立方法

可見面的求解是三維可見元數(shù)據(jù)庫建立的難點(diǎn)，可見劈可以由可見面得到。下面主要介紹給定視點(diǎn)關(guān)于場景的三維可見面提取方法。

3.2.1 三維可見面提取

[6]通過透視投影法將三維面投影到二維平面上進(jìn)行處理。該方法首先使用背面消隱算法剔除所有背向視點(diǎn)的面，然后對剩余的面進(jìn)行空間分區(qū)以及透視投影，接下來在投影平面內(nèi)使用掃描線算法得到這些二維面的遮擋關(guān)系，進(jìn)一步基于多邊形減法算法去除被遮擋的部分面，得到二維可見面，最后將其進(jìn)行逆透視投影即可得到所需的三維可見面。本文基于透視投影法，提出了一種三維空間分區(qū)算法；并且從降低射線跟蹤計(jì)算復(fù)雜度出發(fā)，修正了透視投影算法對地面以及室內(nèi)場景的處理。

（1）空間分區(qū)算法

空間分區(qū)的目的是將場景中的面按照以視點(diǎn)為中心的空間預(yù)劃分方法進(jìn)行切割，使得各個(gè)空間區(qū)域的面能夠在該區(qū)內(nèi)進(jìn)行透視投影。不同的空間劃分方法會(huì)影響透視投影算法的復(fù)雜度，本文使用空間6分區(qū)方法，如圖1(a)所示，以視點(diǎn)S為中心將空間劃分為6個(gè)區(qū)。接下來是將場景中的面經(jīng)過切割劃分到各個(gè)區(qū)域內(nèi)部。如果直接使用圖1(a)中的分區(qū)分界線（虛線所示）對面進(jìn)行求交，則會(huì)產(chǎn)生大量的線面求交運(yùn)算。因此，本文先將場景中的前向面的俯視圖由y=x和y=-x分割為4個(gè)區(qū)，然后分別對4個(gè)分區(qū)內(nèi)的面在z方向上分割為3個(gè)區(qū)。如圖1所示，圖1(b)中一個(gè)前向面A，向地面投影得到線段PQ；圖1(c)中將PQ在平面內(nèi)由B1、B2兩條邊界線進(jìn)行分區(qū)；圖1(d)中將平面分區(qū)結(jié)果還原至三維，由面SB1B2和面SB3B4切割面片PQMN，將其劃分到上、右和下3個(gè)分區(qū)內(nèi)。

圖1 空間6分區(qū)示意

（2）基于城市微小區(qū)場景的修正

對于城市微小區(qū)場景，一方面，天線高度一般低于建筑物平均高度，通過頂面反射到達(dá)接收點(diǎn)的射線貢獻(xiàn)非常小，因此可以忽略建筑物頂面；另一方面，如果對地面采取透視投影法，則會(huì)大大地增加參與計(jì)算的面的數(shù)量，從而增加計(jì)算復(fù)雜度，本文直接將地面加入到可見元數(shù)據(jù)庫中。

（3）基于室內(nèi)場景的修正

對于室內(nèi)場景，首先，室內(nèi)物體可以直接使用透視投影算法，但由于天線高度和室內(nèi)物體高度關(guān)系是不確定的，因此需要考慮室內(nèi)物體的頂面和底面；其次，對于視點(diǎn)，室內(nèi)6壁的面大部分是可見的，并且室內(nèi)6壁面數(shù)目一般少于使用透視投影法求解的可見面數(shù)，因此可直接將室內(nèi)6壁的面加入到三維可見面數(shù)據(jù)庫中。

3.2.2 可見元數(shù)據(jù)庫的數(shù)據(jù)結(jié)構(gòu)

三維可見元數(shù)據(jù)庫使用鏈表結(jié)構(gòu)將可見面數(shù)據(jù)和可見劈數(shù)據(jù)分開存儲(chǔ)。數(shù)據(jù)庫中的重要變量見表1。

表1中的面頂點(diǎn)性質(zhì)Vflag表示可見面的頂點(diǎn)是否為三維場景中對象的頂點(diǎn)，邊性質(zhì)Eflag是指該可見面的各邊是否為三維場景中對象的劈或劈的一部分，索引號(hào)Index為該可見元在三維場景數(shù)據(jù)庫中的位置。

表1 三維可見元數(shù)據(jù)庫變量說明

4 場景建模與仿真實(shí)驗(yàn)

基于上述三維矢量數(shù)據(jù)庫建立方法，本文分別對城市微小區(qū)和室內(nèi)場景進(jìn)行了建模，并計(jì)算了不同場景下給定視點(diǎn)的面可見比例Rf（可見元數(shù)據(jù)庫中面的數(shù)量與場景數(shù)據(jù)庫中面的數(shù)量之比）和劈可見比例Re（可見元數(shù)據(jù)庫中劈的數(shù)量與場景數(shù)據(jù)庫中劈的數(shù)量之比），最后分析了基于可見元數(shù)據(jù)庫的射線跟蹤計(jì)算復(fù)雜度。

4.1 城市微小區(qū)場景建模與仿真

圖2(a)是基于三維場景矢量數(shù)據(jù)庫建立方法得到的一個(gè)假想城市小區(qū)的三維場景模型。小區(qū)由16個(gè)底面不規(guī)則的直棱柱對象組成，面積為350 m×250 m，建筑對象的平均高度為70 m左右。圖2(a)中的陰影面即為以圖中圓點(diǎn)為視點(diǎn)的可見面，建筑物對象的頂面沒有加入可見面數(shù)據(jù)庫中。假設(shè)發(fā)射天線的位置坐標(biāo)為(210,120)，高度40 m；接收天線的位置坐標(biāo)為(90,210)，高度2 m?；谌S場景數(shù)據(jù)庫和三維可見元數(shù)據(jù)庫，通過射線跟蹤模型仿真得到發(fā)射天線和接收天線之間的射線如圖2(b)所示。

4.2 室內(nèi)場景建模與仿真

圖3(a)是基于室內(nèi)場景建模方法得到的模型。該室內(nèi)場景模型包括6個(gè)室內(nèi)物體對象和8個(gè)室內(nèi)6壁面對象，底面為15 m×3.5 m，高度為3.5 m。圖3(a)中的陰影面即為以圖中圓點(diǎn)為視點(diǎn)的可見面，其中室內(nèi)物體可見的頂面和底面均加入到可見面數(shù)據(jù)庫中。假設(shè)發(fā)射天線的位置坐標(biāo)為(4,1.5)，高度2 m；接收天線的位置坐標(biāo)為(12,0.8)，高度1.5 m?；谑覂?nèi)三維矢量數(shù)據(jù)庫，通過射線跟蹤模型計(jì)算得到從發(fā)射天線經(jīng)歷一次反射加一次繞射到達(dá)接收天線的射線，如圖3(b)所示。

圖2 城市微蜂窩場景建模及仿真

圖3 室內(nèi)場景建模及仿真

4.3 射線跟蹤計(jì)算復(fù)雜度分析

由于射線跟蹤模型計(jì)算復(fù)雜度取決于用于計(jì)算的面和劈的數(shù)量，因此通過計(jì)算不同場景下的Rf和Re可以分析射線跟蹤模型的計(jì)算復(fù)雜度。本文針對3個(gè)城市微小區(qū)場景以及1個(gè)室內(nèi)場景，每個(gè)場景隨機(jī)給定5個(gè)視點(diǎn)，得到的平均Rf和平均Re見表2。從表2中可以看出：不論是城市微小區(qū)還是室內(nèi)場景，基于修正的透視投影法能夠較大地降低參與射線跟蹤計(jì)算的面和劈的數(shù)量。

為了進(jìn)一步分析三維可見元數(shù)據(jù)庫對射線跟蹤算法計(jì)算復(fù)雜度的改善，本文基于VC 6.0平臺(tái)，比較了上述場景在建立三維可見元數(shù)據(jù)庫前后的情況下仿真100個(gè)場點(diǎn)所需的時(shí)間Tv與Tc，并計(jì)算了時(shí)間復(fù)雜度之比Rt=Tv/Tc。從表2中可見，通過建立三維可見元數(shù)據(jù)庫，可以較大地降低射線跟蹤計(jì)算復(fù)雜度。

表2 不同場景下計(jì)算復(fù)雜度分析

5 結(jié)束語

本文通過分析室外場景與室內(nèi)場景的特點(diǎn)，提出了一種適用于城市微小區(qū)以及室內(nèi)場景三維矢量數(shù)據(jù)庫建立方法。首先通過簡化的CAD建模方法快速地建立簡化場景的三維模型和場景數(shù)據(jù)庫；然后基于改進(jìn)的透視投影算法有效地建立關(guān)于視點(diǎn)的三維可見元數(shù)據(jù)庫。仿真結(jié)果表明，本文提出的方法能有效地應(yīng)用于三維射線跟蹤模型中數(shù)據(jù)庫的建立，降低計(jì)算復(fù)雜度。在下一步的研究中將建立具有不同幾何精度的矢量數(shù)據(jù)庫并分析幾何精度對射線跟蹤模型分析電磁特性參數(shù)的影響。

參考文獻(xiàn)

1 Liang G,Bertoni H L.A new approach to 3-D ray tracing for propagation prediction in cities.IEEE Transactions on Antennas and Propagation,1998,46(6):853～863

2 Zhengqing Yun,Sungkyun Lim,Iskander M F.An integrated method of ray tracing and genetic algorithm for optimizing coverage in indoor wireless networks.Antennas and Wireless Propagation Letters,2008(7):145～148

3 Jacob M,Schon S,Weinbach U,et al.Ray tracing supported precision evaluation for GPS indoor positioning.Proceedings of Workshop on Positioning,Navigation and Communication,Hannover,Germany:IEEE Press,2009:15～22

4 Ran Chen.The developmentof3D city modeland its applications in urban planning.Proceedings of 19th International Conference on Geoinformatics.Shanghai,China:IEEE Press,2011:1～5

5 Aguado Agelet F,Formella A,Hernando Rabanos J M,et al.Efficient ray-tracing acceleration techniques for radio propagation modeling. IEEE Transactions on Vehicular Technology,2000,49(6):2 089～2 104

6 Maurer J,Drumm O,Didascalou D.A novel approach in the determination of visible surfaces in 3D vector geometries for ray-optical wave propagation modeling.Proceedings of IEEE Vehicular Technology Conference,Tokyo,Japan:IEEE Press,2000:1 651～1 655