周 林，雒 芳，楊龍頻

(1.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065；2.北京醫(yī)院，北京 100730)

一種基于虛擬墻的射線跟蹤法

周 林1，雒 芳1，楊龍頻2

(1.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065；2.北京醫(yī)院，北京 100730)

針對(duì)現(xiàn)有射線跟蹤算法效率低下的問(wèn)題，利用虛擬源思想，設(shè)計(jì)了一種基于虛擬墻的射線跟蹤算法。首先，通過(guò)將處于同一平面的墻面合并為“虛擬墻”，降低了算法搜索過(guò)程中墻面的遍歷次數(shù)。在此基礎(chǔ)上，通過(guò)設(shè)計(jì)“透光區(qū)”、“光扇區(qū)”等有效性判決條件，完成節(jié)點(diǎn)有效性的判決，避免了無(wú)效節(jié)點(diǎn)的混入，減少了計(jì)算復(fù)雜度。最后，利用深度優(yōu)先搜索算法完成虛擬源樹(shù)狀結(jié)構(gòu)的建立，無(wú)須重復(fù)遍歷即可獲得發(fā)射點(diǎn)到接收點(diǎn)的全部有效路徑。仿真結(jié)果表明，該算法路徑損耗的預(yù)測(cè)精度隨著樹(shù)遍歷深度的增加而提高，同時(shí)降低了算法復(fù)雜度。

射線跟蹤；虛擬墻；深度優(yōu)先；遍歷

近年來(lái)，隨著移動(dòng)通信技術(shù)和通信業(yè)務(wù)的快速發(fā)展，通信頻譜資源越來(lái)越緊缺，微蜂窩、微微蜂窩系統(tǒng)采用頻率復(fù)用[1]技術(shù)降低了基站發(fā)射功率，提高了頻率利用率，得到了廣泛應(yīng)用。在微蜂窩系統(tǒng)下，原有的無(wú)線電波大區(qū)傳播模型不再適用，基于幾何光學(xué)(GTO)和一致繞射理論(UTD)[2]的射線跟蹤法是一種運(yùn)用于微小區(qū)環(huán)境的無(wú)線電波傳播特性預(yù)測(cè)技術(shù)[3-4]。

目前，射線跟蹤法的研究可分為兩類：正向射線跟蹤法和反向射線跟蹤法。正向射線跟蹤法采用發(fā)射角量化將發(fā)射射線從無(wú)窮轉(zhuǎn)換成有限多，通過(guò)追蹤每一根射線的路徑，并判斷其能否到達(dá)接收方，以獲得最終有效路徑，但是需要在接收點(diǎn)設(shè)置接收球進(jìn)行接收測(cè)試，發(fā)射角量化間隔和接收球半徑大小都會(huì)影響接收誤差，從而使算法的精度受到影響。反向射線跟蹤法利用幾何光學(xué)的鏡像原理求發(fā)射源的多級(jí)鏡像點(diǎn)，得到鏡像樹(shù)，然后從接收點(diǎn)出發(fā)，根據(jù)幾何光學(xué)原理，反向追蹤每一條能從源點(diǎn)到達(dá)場(chǎng)點(diǎn)的路徑，能夠模擬所有可達(dá)的射線路徑，得到了廣泛應(yīng)用和研究[5-7]。但是，在街道等現(xiàn)實(shí)建筑物場(chǎng)景中，多個(gè)墻面往往處于同一水平面上，墻面的鏡像點(diǎn)是相同的，無(wú)須重復(fù)搜索，上述反向射線跟蹤算法沒(méi)有考慮這種普遍情況下墻面的重復(fù)搜索問(wèn)題，造成了算法復(fù)雜度的增大。針對(duì)這一問(wèn)題，本文設(shè)計(jì)了一種基于虛擬墻的射線跟蹤算法，通過(guò)將多個(gè)墻面合并為“虛擬墻”進(jìn)行統(tǒng)一搜索，降低了墻面的遍歷次數(shù)。通過(guò)設(shè)計(jì)透光區(qū)和光扇區(qū)輔助完成節(jié)點(diǎn)有效性的判決。在此基礎(chǔ)上，利用深度優(yōu)先搜索算法，完成虛擬源樹(shù)狀結(jié)構(gòu)的建立，獲得所有有效路徑，提高了已有射線跟蹤模型的效率。

1 傳統(tǒng)的傳播模型建模過(guò)程

1.1 城市模型

無(wú)線電波傳播模型一般分為二維模型和三維模型兩種，本文研究的環(huán)境是城市微蜂窩環(huán)境，收發(fā)天線低于周圍環(huán)境建筑物的高度，可以忽略從建筑物頂部繞射到接收天線的射線[8-10]，因此這種情況下，射線跟蹤預(yù)測(cè)可以直接在城市的二維空間圖中進(jìn)行，從而只考慮兩種傳播機(jī)制：反射和繞射。本文選取的實(shí)例是加拿大渥太華市中心的核心俯視圖[11]，如圖1所示，建筑群被劃分為一定的“塊”，建筑物則被定義為“多邊形”，多邊形的“邊”代表建筑物的表面，多邊形的“頂點(diǎn)”則代表建筑物的拐角。這種簡(jiǎn)化了的市區(qū)平面圖大致反映出城市的主體結(jié)構(gòu)，利用它進(jìn)行射線跟蹤，可以得到較為準(zhǔn)確的路徑損耗。

圖1 渥太華市區(qū)部分區(qū)域二維視圖

1.2 基于虛擬源的射線跟蹤法

在對(duì)城市模型進(jìn)行建模的基礎(chǔ)上，射線跟蹤法能夠快速確定從發(fā)射節(jié)點(diǎn)到接收節(jié)點(diǎn)的所有傳播路徑。如圖2所示，首先，定義三類源，即發(fā)射源、鏡像源和繞射源。虛擬源包括鏡像源和繞射源。建立虛擬源樹(shù)結(jié)構(gòu)以及計(jì)算每個(gè)源的有效性[12]是該算法的關(guān)鍵。基于虛擬源的射線跟蹤算法的思想是：在射線跟蹤時(shí)，電波從源點(diǎn)出發(fā)，除直射波外，其他的射線都要經(jīng)過(guò)反射或繞射才能到達(dá)場(chǎng)點(diǎn)，所有傳播路徑都是墻面反射和邊緣繞射的組合。這個(gè)過(guò)程中，射線經(jīng)過(guò)的反射面和繞射邊緣可以用樹(shù)結(jié)構(gòu)圖來(lái)記錄。但是，基于虛擬源的射線跟蹤算法鏡像源的數(shù)目隨墻面?zhèn)€數(shù)呈冪指數(shù)增長(zhǎng)，這增加了鏡像源的遍歷次數(shù)，造成算法復(fù)雜度增大。

1.3 路徑損耗的計(jì)算

假設(shè)發(fā)射機(jī)天線是垂直放置的電偶極子，接收天線是具有垂直極化特性的天線，電磁波以球面波的形式向外傳播。

圖2 源類型示意圖

在實(shí)際應(yīng)用中，電波會(huì)遇到森林、山丘、地面、樓房等高大建筑物，絕大多數(shù)射線在到達(dá)接收點(diǎn)之前要經(jīng)過(guò)多次反射和繞射。射線到達(dá)接收點(diǎn)的電場(chǎng)強(qiáng)度用以下公式計(jì)算

(1)

(2)

2 基于虛擬源的射線跟蹤法加速算法

基于虛擬源的射線跟蹤算法復(fù)雜度較高，且反射源的數(shù)目隨墻面?zhèn)€數(shù)呈冪指數(shù)增長(zhǎng)的關(guān)系。本文從兩方面進(jìn)行了改進(jìn)：1)針對(duì)反射過(guò)程，利用“虛擬墻”概念，減少搜索墻面的個(gè)數(shù)，利用“透光區(qū)”、“光扇區(qū)”等概念輔助算法設(shè)計(jì)完成節(jié)點(diǎn)有效性的判決，避免了無(wú)效節(jié)點(diǎn)的混入，減少了計(jì)算復(fù)雜度；2)利用深度優(yōu)先的搜索算法，完成虛擬源樹(shù)狀結(jié)構(gòu)建立的同時(shí)，獲得有效路徑，無(wú)須再次遍歷，從而提高算法效率。

2.1 虛擬墻、透光區(qū)、光扇區(qū)的構(gòu)造

1)虛擬墻

本文利用了墻壁“虛擬合并”的思想，將同一條直線上的墻壁被視為“相同”(如圖1中曲線所示)，而原先的墻僅僅是該“虛擬墻”的一個(gè)可達(dá)面。這是因?yàn)楣?jié)點(diǎn)關(guān)于這些墻壁的鏡像點(diǎn)都重合，無(wú)需重復(fù)搜素。如表1所示，合并后的虛擬墻面數(shù)比真實(shí)墻面減少了40%，大大減少了算法后續(xù)遍歷的復(fù)雜度。而在現(xiàn)實(shí)中的城市規(guī)劃布局中，街道建筑往往也具有這種平整性，因此虛擬墻的概念具有一定的應(yīng)用價(jià)值。虛擬墻雖然降低了墻面的遍歷次數(shù)，但也增加了無(wú)效節(jié)點(diǎn)的混入。本文通過(guò)引入透光區(qū)和光扇區(qū)，最大限度地抑制無(wú)效節(jié)點(diǎn)的混入。

表1 虛擬合并前后的墻壁數(shù)目對(duì)比

2)透光區(qū)

鏡像節(jié)點(diǎn)是源節(jié)點(diǎn)關(guān)于真實(shí)墻面對(duì)稱的虛擬源，其本身并不發(fā)出射線。如圖3所示，若源節(jié)點(diǎn)發(fā)出的射線被遮擋，則僅有部分墻面能夠收到光線，稱這部分區(qū)域?yàn)樵搲γ娴耐腹鈪^(qū)?？梢钥闯?種墻面面積之間的關(guān)系為：透光區(qū)≤真實(shí)墻≤虛擬墻。

圖3 概念示意圖

3)光扇區(qū)

虛擬源與其相應(yīng)透光區(qū)的連線掃過(guò)的區(qū)域，會(huì)形成如圖所示的扇區(qū)，稱其為光扇區(qū)。只有光扇區(qū)內(nèi)的墻面才有可能產(chǎn)生下一次反射。利用光扇區(qū)的這一特性，能夠進(jìn)一步減少遍歷墻面的個(gè)數(shù)。

2.2 虛擬源多叉樹(shù)的建立

本文通過(guò)構(gòu)造虛擬源多叉樹(shù)對(duì)可達(dá)路徑進(jìn)行搜索，并利用深度優(yōu)先算法進(jìn)行加速。射線跟蹤過(guò)程由反射過(guò)程和繞射過(guò)程級(jí)聯(lián)組成，在反射過(guò)程中，根據(jù)上述輔助概念，設(shè)計(jì)多叉樹(shù)下一級(jí)鏡像節(jié)點(diǎn)或繞射節(jié)點(diǎn)的有效性判決條件(加入樹(shù)的充要條件)。

鏡像節(jié)點(diǎn)加入樹(shù)的充要條件為：該節(jié)點(diǎn)對(duì)應(yīng)的虛擬墻(反射墻)中至少有一點(diǎn)處于透光區(qū)，且該點(diǎn)與虛擬源節(jié)點(diǎn)之間無(wú)遮攔物存在。

繞射節(jié)點(diǎn)加入樹(shù)的充要條件是繞射點(diǎn)在虛擬源相應(yīng)的光扇區(qū)內(nèi)，且繞射點(diǎn)與虛擬源之間無(wú)遮攔。

在繞射過(guò)程中，繞射節(jié)點(diǎn)和發(fā)射節(jié)點(diǎn)相同，均可向所有有效區(qū)域發(fā)射射線，如圖2所示，繞射源的有效區(qū)域?yàn)榻ㄖ锕战峭獾膮^(qū)域，因此當(dāng)繞射節(jié)點(diǎn)加入搜索樹(shù)之后，將繞射節(jié)點(diǎn)當(dāng)作發(fā)射源，搜索下一級(jí)有效節(jié)點(diǎn)。在此基礎(chǔ)上，如圖4所示，采用深度優(yōu)先算法，建立虛擬源多叉樹(shù)，樹(shù)的每一個(gè)分支代表一個(gè)路徑，若當(dāng)前路徑能夠到達(dá)接收節(jié)點(diǎn)，則為有效路徑。

2.3 改進(jìn)算法的實(shí)現(xiàn)步驟

加速算法的實(shí)現(xiàn)步驟如圖5所示，在傳統(tǒng)的射線跟蹤算法基礎(chǔ)上，加入改進(jìn)的節(jié)點(diǎn)有效性判決模塊，以此來(lái)加速搜索過(guò)程，節(jié)點(diǎn)有效性判決模塊包括鏡像節(jié)點(diǎn)有效性判決和繞射節(jié)點(diǎn)有效性判決。

圖4 虛擬源樹(shù)示意圖

圖5 改進(jìn)算法的流程圖

3 仿真分析

選取圖1所示的建筑物街道模型，分別設(shè)置發(fā)射點(diǎn)坐標(biāo)為(300，230)，接收點(diǎn)坐標(biāo)設(shè)置為(500，200)，對(duì)所提加速算法進(jìn)行仿真。圖6顯示了存在最多7次反射和最多2次繞射的全部路徑，圖7和圖8顯示路徑是圖6的子集。觀察發(fā)現(xiàn)圖7中射線條數(shù)明顯少于圖8，并且圖6射線主要是通過(guò)繞射實(shí)現(xiàn)，由此可判斷當(dāng)發(fā)射節(jié)點(diǎn)和源節(jié)點(diǎn)不存在直射路徑時(shí)，射線主要通過(guò)繞射才能到達(dá)接收節(jié)點(diǎn)。

由于無(wú)線電波在傳輸過(guò)程中，會(huì)隨傳輸距離的增大、反射繞射次數(shù)的增多而衰減，為了限定仿真規(guī)模，本文設(shè)置當(dāng)只有反射時(shí)，最多存在7次發(fā)射；當(dāng)既有反射又有繞射時(shí)，最多存在3次反射和1次繞射。按照文獻(xiàn)[14]所示的無(wú)線電波路徑損耗、反射、繞射衰減模型，設(shè)置無(wú)線電波頻率為1GHz，墻面的相對(duì)介電常數(shù)為9、電導(dǎo)率為0.1S/m，地面的相對(duì)介電常數(shù)為15，電導(dǎo)率為7S/m。固定發(fā)射點(diǎn)位置為(500，220)，分別對(duì)圖9所示的接收點(diǎn)位置的接收信號(hào)強(qiáng)度進(jìn)行仿真計(jì)算。

圖6 最多7次反射和最多2次繞射的全部路徑

圖7 最多2次反射和最多1次繞射的全部路徑

圖8 最多1次反射和最多2次繞射的全部路徑

圖9 接收點(diǎn)坐標(biāo)設(shè)置圖

如圖10所示，仿真1中限定最大反射次數(shù)為4，最大繞射次數(shù)為1來(lái)計(jì)算各接收點(diǎn)處路徑損耗；仿真2限定最大反射次數(shù)為7，最大繞射次數(shù)為3。仿真規(guī)模隨可允許的發(fā)射和繞射次數(shù)增加而增大，此時(shí)仿真的精度也隨之提高，仿真結(jié)果接近實(shí)際測(cè)量值。并且路徑損耗隨接收點(diǎn)的位置改變而改變，當(dāng)接收點(diǎn)被建筑物遮擋較多時(shí)，路徑衰減較大，當(dāng)接收點(diǎn)被建筑物遮擋較多時(shí)，路徑衰減較小。在路口位置，由于存在豐富的繞射環(huán)境，路徑衰減相對(duì)較小。因此，為了增大基站的覆蓋范圍，可以將基站布設(shè)在路口位置。

圖10 圖9中各接收點(diǎn)位置的路徑損耗仿真圖

4 小結(jié)

本文針對(duì)射線跟蹤法復(fù)雜度高的問(wèn)題，利用虛擬墻合并方法、“透光區(qū)”、“光扇區(qū)”等輔助判決概念，減少了節(jié)點(diǎn)有效性判決中墻面的遍歷次數(shù)。利用深度優(yōu)先的搜索算法完成虛擬源樹(shù)狀結(jié)構(gòu)的建立，提高了基于虛擬源的射線跟蹤模型的預(yù)測(cè)效率。仿真結(jié)果表明，算法路徑損耗的預(yù)測(cè)精度隨著樹(shù)遍歷深度的增加而提高，能夠用于任何復(fù)雜的傳播環(huán)境。

[1]曹鵬，彭華，張金成.頻率選擇性衰落信道下OFDM子載波數(shù)盲估計(jì)[J].電視技術(shù)，2011，35(3)：67-70.

[2]賀之莉，黃鍇，蔣曉博，等.一種穩(wěn)定高效的NURBS建模MOM-PO法[J].西安電子科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，39(3)：56-61.

[3]SONG H B，WANG H G，HONG K，et al.A novel source localization scheme based on unitary esprit and city electronic maps in urban environments[J].Progress In Electromagnetics Research，2009(94)：243-262.

[4]王利東.三維城市環(huán)境下電波場(chǎng)強(qiáng)預(yù)測(cè)加速模型研究[D].長(zhǎng)沙：湖南科技大學(xué)，2012.

[5]廖斌，趙昵麗，朱守正.基于虛擬源樹(shù)的射線跟蹤算法的研究[J].華東師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2008(3)：103-108.

[6]李朝奎，王利東，李擁，等.一種利用鏡像理論的射線跟蹤改進(jìn)算法[J].武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2012，37(7)：784-788.

[7]劉忠玉，郭立新，種稚萌，等.城市微蜂窩環(huán)境下一種改進(jìn)的射線跟蹤預(yù)測(cè)模型[J].西安電子科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，41(2)：137-143.

[8]YACKOSKI J，AZIMI-SADJADI B，NAMAZI A，et al.Mobile network performance evaluation using the radio frequency network channel emulation simulation tool(RFnest?)[C]//Proc.19th annual international conference on Mobile computing & networking.[S.l.]：ACM Press，2013：155-158.[9]ZHANG Z B，GUO L，LIU Z Y.An improved algorithm of reverse ray tracing for radio propagation prediction in urban[C]//Proc.IEEE International Conference on Microwave Technology & Computational Electromagnetics (ICMTCE) .[S.l.]：IEEE Press，2011：346-349.

[10]SON H W，MYUNG N H.A deterministic ray tube method for microcellular wave propagation prediction model[J].IEEE Trans. Antennas and Propagation，1999，47(8)：1344-1350.

[11]TAN S Y，TAN H S.Propagation model for microcellular communications applied to path loss measurements in Ottawa city streets[J].IEEE Trans.Vehicular Technology，1995，44(2)：313-317.

[12]顧曉龍，章文勛，云正清，等.利用可見(jiàn)性概念改進(jìn)基于鏡像原理的射線追蹤法[J].電波科學(xué)學(xué)報(bào)，2001，16(4)：464-467.

[13]GMELIN M，KREUZINGER J，PFEFFER M，et al.Agent-based distributed computing with jmessengers[M].Innovative Internet Computing Systems：Springer Berlin Heidelberg，2001.

[14]吳劍鋒，曹偉.用于微蜂窩電波傳播預(yù)測(cè)的二維射線跟蹤模型[J].南京郵電學(xué)院學(xué)報(bào)，2001，21(2)：45-51.

周 林(1963— )，碩士生導(dǎo)師，主要研究方向無(wú)線通信、計(jì)算機(jī)網(wǎng)絡(luò)、物聯(lián)網(wǎng)開(kāi)發(fā)等；

雒 芳(1987— )，女，碩士生，主研無(wú)線信道。

責(zé)任編輯：許 盈

Ray Tracing Algorithm Based on Virtual Wall

ZHOU Lin1, LUO Fang1, YANG Longpin2

(1.DepartmentofCommunicationandInformationEngineering,ChongqingUniversityofPostsandTelecommunications,Chongqing400065,China;2.BeijingHospital,Beijing100730)

Aiming at the low efficiency problem of the existing ray tracing algorithm, using the idea of virtual source, a ray tracing algorithm based on the virtual wall is designed.Firstly, walls in the same plane are merged into a "virtual wall" to reduce the traversal times of walls in the search process.Secondly, in order to avoid the interfusion of the invalid nodes and reduce the computational complexity, the assisted judgment conditions such as "the photic zone", "light sector" are designed to accomplish the validity judgement of the nodes.Finally, the depth-first search algorithm is used to complete the establishment of virtual source tree structure, avoiding the repeated traversal in the search process of all effective paths.The simulation results show that the prediction accuracy of path loss increases with the depth of the tree as well as the computational complexity of the proposed algorithm is reduced.

ray tracing; virtual wall; depth-first; traversal

【本文獻(xiàn)信息】周林，雒芳.一種基于虛擬墻的射線跟蹤法[J].電視技術(shù),2015，39(3).

國(guó)家自然科學(xué)基金項(xiàng)目(61171190)

TN915；TP301.6

A

10.16280/j.videoe.2015.03.035

2014-09-05