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

周 林，雒 芳，楊龍頻

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

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

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

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

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

射線跟蹤；虛擬墻；深度優先；遍歷

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

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

1 傳統的傳播模型建模過程

1.1 城市模型

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

圖1 渥太華市區部分區域二維視圖

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

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

1.3 路徑損耗的計算

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

圖2 源類型示意圖

在實際應用中，電波會遇到森林、山丘、地面、樓房等高大建筑物，絕大多數射線在到達接收點之前要經過多次反射和繞射。射線到達接收點的電場強度用以下公式計算

(1)

(2)

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

基于虛擬源的射線跟蹤算法復雜度較高，且反射源的數目隨墻面個數呈冪指數增長的關系。本文從兩方面進行了改進：1)針對反射過程，利用“虛擬墻”概念，減少搜索墻面的個數，利用“透光區”、“光扇區”等概念輔助算法設計完成節點有效性的判決，避免了無效節點的混入，減少了計算復雜度；2)利用深度優先的搜索算法，完成虛擬源樹狀結構建立的同時，獲得有效路徑，無須再次遍歷，從而提高算法效率。

2.1 虛擬墻、透光區、光扇區的構造

1)虛擬墻

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

表1 虛擬合并前后的墻壁數目對比

2)透光區

鏡像節點是源節點關于真實墻面對稱的虛擬源，其本身并不發出射線。如圖3所示，若源節點發出的射線被遮擋，則僅有部分墻面能夠收到光線，稱這部分區域為該墻面的透光區。可以看出3種墻面面積之間的關系為：透光區≤真實墻≤虛擬墻。

圖3 概念示意圖

3)光扇區

虛擬源與其相應透光區的連線掃過的區域，會形成如圖所示的扇區，稱其為光扇區。只有光扇區內的墻面才有可能產生下一次反射。利用光扇區的這一特性，能夠進一步減少遍歷墻面的個數。

2.2 虛擬源多叉樹的建立

本文通過構造虛擬源多叉樹對可達路徑進行搜索，并利用深度優先算法進行加速。射線跟蹤過程由反射過程和繞射過程級聯組成，在反射過程中，根據上述輔助概念，設計多叉樹下一級鏡像節點或繞射節點的有效性判決條件(加入樹的充要條件)。

鏡像節點加入樹的充要條件為：該節點對應的虛擬墻(反射墻)中至少有一點處于透光區，且該點與虛擬源節點之間無遮攔物存在。

繞射節點加入樹的充要條件是繞射點在虛擬源相應的光扇區內，且繞射點與虛擬源之間無遮攔。

在繞射過程中，繞射節點和發射節點相同，均可向所有有效區域發射射線，如圖2所示，繞射源的有效區域為建筑物拐角外的區域，因此當繞射節點加入搜索樹之后，將繞射節點當作發射源，搜索下一級有效節點。在此基礎上，如圖4所示，采用深度優先算法，建立虛擬源多叉樹，樹的每一個分支代表一個路徑，若當前路徑能夠到達接收節點，則為有效路徑。

2.3 改進算法的實現步驟

加速算法的實現步驟如圖5所示，在傳統的射線跟蹤算法基礎上，加入改進的節點有效性判決模塊，以此來加速搜索過程，節點有效性判決模塊包括鏡像節點有效性判決和繞射節點有效性判決。

圖4 虛擬源樹示意圖

圖5 改進算法的流程圖

3 仿真分析

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

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

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

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

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

圖9 接收點坐標設置圖

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

圖10 圖9中各接收點位置的路徑損耗仿真圖

4 小結

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

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

[2]賀之莉，黃鍇，蔣曉博，等.一種穩定高效的NURBS建模MOM-PO法[J].西安電子科技大學學報：自然科學版，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]王利東.三維城市環境下電波場強預測加速模型研究[D].長沙：湖南科技大學，2012.

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

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

[7]劉忠玉，郭立新，種稚萌，等.城市微蜂窩環境下一種改進的射線跟蹤預測模型[J].西安電子科技大學學報：自然科學版，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]顧曉龍，章文勛，云正清，等.利用可見性概念改進基于鏡像原理的射線追蹤法[J].電波科學學報，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]吳劍鋒，曹偉.用于微蜂窩電波傳播預測的二維射線跟蹤模型[J].南京郵電學院學報，2001，21(2)：45-51.

周 林(1963— )，碩士生導師，主要研究方向無線通信、計算機網絡、物聯網開發等；

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

責任編輯：許 盈

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

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

國家自然科學基金項目(61171190)

TN915；TP301.6

A

10.16280/j.videoe.2015.03.035

2014-09-05