高頻RCS預估中判別陰影區(qū)域的并行算法

張月園，劉志偉，張曉燕，劉穎婷，何 姍

高頻RCS預估中判別陰影區(qū)域的并行算法

*張月園1，劉志偉2,3，張曉燕2,3，劉穎婷2，何 姍2

(1. 華東交通大學國際學院，江西，南昌 330013；2. 華東交通大學信息工程學院，江西，南昌 330013；3. 毫米波國家重點實驗室，江蘇，南京 210096）

利用物理光學方法預估高頻雷達散射截面(RCS)時，需要判別目標表面的陰影區(qū)域。本文提出了一種基于樹型結(jié)構的多重陰影判別算法，將判斷面元是否被面元遮擋轉(zhuǎn)變?yōu)榕袛嗝嬖欠癖环纸M遮擋，極大地降低了計算復雜度。與此同時，引入并行技術，將基于樹型結(jié)構的多重陰影遮擋算法并行化，進一步節(jié)省計算時間。數(shù)值算例表明，基于樹型結(jié)構的多重陰影判別算法與傳統(tǒng)的陰影判別方法相比，在保證計算精度一致的前提下，計算效率更加高效。

電磁場；高頻散射；并行遮擋判別；計算電磁學；物理光學

高頻電磁散射是指電尺寸較大目標的電磁散射。作為雷達目標特性研究的重要手段，采用電磁散射理論高效分析高頻電磁散射及雷達散射截面，對雷達設計、目標識別、雷達成像等具有重要意義[1]。由于目標的電尺寸較大，采用矩量法(MoM: Method of Moment)[2-4]、有限元(FEM: Finite Element Method)[5-6]等數(shù)值方法計算電磁散射時，計算時間較長，內(nèi)存需求較大，難以實現(xiàn)高效仿真。然而，高頻電磁散射呈現(xiàn)一部分光學特性，因此可以利用光學特性進行近似，即采用物理光學(PO: Physical Optics)[7-8]方法實現(xiàn)電磁散射的高效求解。

不失一般性，假設三維目標表面用平面三角形建模，被剖分為個三角形面元。當采用物理光學方法計算高頻電磁散射時，由于每個面元上的感應電流和磁流只由入射電磁波決定，使得計算復雜度為()。因此，物理光學方法是預估高頻電磁散射的高效算法。但是目標表面并不是每個面元都存在感應電流和磁流。根據(jù)物理光學原理，目標表面僅有一部分被入射電磁波“照明”，剩下的部分即“陰影”區(qū)域[9]。被照明的區(qū)域存在感應電流和磁流，而陰影區(qū)域的感應電流和磁流為零。因此，在采用物理光學方法計算電磁散射時，首先需要判斷照明和陰影區(qū)域。當目標表面被剖分為許多個三角形面元時，傳統(tǒng)的判別方法是逐個判斷每個面元是否被其余面元遮擋。該判別過程計算復雜度為(2)。當三角形個數(shù)非常多，即目標非常大時，遮擋判別的時間將非常長，將嚴重影響物理光學方法對散射場的求解。

本文首先分析了傳統(tǒng)的遮擋判別方法，并在傳統(tǒng)方法基礎上，引入了樹型結(jié)構和并行技術，從根本上實現(xiàn)了遮擋判別的提速。為了驗證方法的正確性和高效性，本文利用新方法對飛機模型和坦克模型的遮擋關系進行了判別，并給出了相應的仿真結(jié)果。

1 高頻RCS預估中的陰影判別原理

目標電磁散射的高頻近似原理認為，目標被入射波照亮的部分會產(chǎn)生感應電流和磁流，目標未被入射波照亮的部分電流和磁流為零。因此，整個目標分為兩個區(qū)域，照明區(qū)和陰影區(qū)。高頻方法首先要把散射體模型的照明面和陰影面分離出來，該過程就是判別陰影面元。一個高效的自動判別算法既直接影響計算結(jié)果的精度，又可使計算過程更加快速。

為了判別陰影區(qū)域，先將整個過程分為單重和多重兩類：如果某個面元僅僅是因為朝向，使得入射射線無法到達面元的外表面，從而被判斷為陰影面，則稱為該面元被單重遮擋；如果某個面元被判斷為陰影面，其原因是它面元擋在該面元與入射波之間，則稱該面元被多重遮擋。單重判別比較簡單，只需要利用面元的外法向量和入射波的方向矢量即可，如圖1(a)所示。

圖1 高頻散射中的遮擋：(a) 單重遮擋示意圖；(b) 多重遮擋示意圖

單重判別的運算過程簡單，運算速度快。但單重判別只能用于幾何體簡單的情況。

對于多重判別，計算過程比單重要復雜，一般在單重識別后，對剩余的照明面元再進行處理。多重判別的示意圖如圖1(b)所示，假定此時面元1、2、3和4在單重判別的過程中被識別為照明面，下面分析3的多重判別過程。首先從面元3的中點引出一條射線，方向為入射波方向的反方向，從而將問題轉(zhuǎn)化為分析該射線與其余面元是否有交點。依次判斷該射線與各個面元是否有交點，如果有，則面元3被判斷為陰影面；反之，面元3被判斷為照明面。由此可見，要分析每個面元的遮擋關系，就需要從每個面元引出射線，再判斷射線與所有的面元是否相交，當面元很多時計算量是巨大的。因此，研究快速算法非常必要。

2 基于樹型結(jié)構的多重遮擋判別方法

多重判斷的運算量主要集中在通過幾何關系求解射線與面元之間的交點。經(jīng)過單重判斷后，假設有個面元被判定為照明，則多重判別的運算過程需要求解2次交點。對于電大尺寸目標，面元特別多，則多重判別過程就特別緩慢。為了加速這個過程，可以引入八叉樹結(jié)構[10]。

2.1 基于樹型結(jié)構的多重遮擋判別算法

圖2 樹型分組結(jié)構

計算射線與面元的交點時，可以先計算射線與分組的交點；若射線與某個分組沒有交點，則該分組包含的所有面元都不會與該射線有交點；若射線與某個分組有交點，則依次計算該區(qū)域包含的所有面元與該射線的交點。通過這種分組的策略，大大降低了射線與面元求交的過程，提高了計算效率。對于更大規(guī)模的問題，可以通過多層的樹型結(jié)構來加速。即判斷出射線與某個分組有交點時，則進一步與該分組的子分組依次判斷，直到子分組為最細層的分組為止，再對分組中的面元進行判斷。其運算復雜度從傳統(tǒng)方法的(2)降為(log)，對于電大尺寸目標，計算效率得到極大地改善。

2.2 利用并行技術對算法加速

在利用樹型結(jié)構求解多重遮擋時，還可以引入并行計算技術。傳統(tǒng)的串行策略，每次判斷一條射線，個三角形單元，則需要判斷次。采用并行技術后，求解所有面元引出的射線與面元的交點可以同時進行。假設機器的計算單元有個，則每次可以同時判斷次射線。理論上的計算時間則將為原來的1 /，從而可以極大地節(jié)省計算時間。但由于并行效率不一定達到理想情況，實際的加速效果會比1 /要差一點。

3 數(shù)值算例

3.1 樹型遮擋判別算法的效率分析

下面用兩組數(shù)值算例來說明物理光學方法中遮擋算法的效率，模型分別是VFY-218和Tank，剖分的平面三角形面元個數(shù)分別是108600和335892。圖3和圖4分別給出了這兩個算例的判別結(jié)果，途中深色部分表示照明區(qū)域，而途中淺色部分表示陰影區(qū)域，紅色箭頭表示平面波的入射方向。從圖中可以看出，本文算法的正確性。表1給出了傳統(tǒng)算法與基于樹型結(jié)構的算法的計算時間，可以看出，引入樹型結(jié)構之后，算法的效率極大提高。但隨著樹型結(jié)構層數(shù)的不斷增加，計算時間先快速降低然后又升高，原因是分層數(shù)量不斷增加，射線與面元之間的交點計算時間不斷減少，但射線與子區(qū)域之間的交點計算時間逐漸增加，并逐漸成為計算的主要負擔。

圖3 VFY-218飛機的多重遮擋結(jié)果：(a) 頂部入射 (= 0°,= 0°)；(b) 側(cè)面入射 (= 90°,= 90°)

Fig.3 Result of VFY-218：(a) Illuminated from top (= 0°,= 0°)；(b) Illuminated from side (= 90°,= 90°)

圖4 Tank的多重遮擋結(jié)果：(a) 頂部入射 (θ = 0°, φ = 0°)；(b) 側(cè)面入射 (θ = 90°, φ = 90°)

表1 傳統(tǒng)多重遮擋方法和基于樹型結(jié)構的多重遮擋方法比較(時間：秒)

表2 串行方法與并行方法計算時間比較(時間：秒)

從表1中可以看出，基于樹形結(jié)構的快速遮擋算法，可以極大地改善計算效率。然而，對于單站RCS計算、雷達回波數(shù)據(jù)仿真等問題，需要反復地判別遮擋區(qū)域，使得有必要尋求更多地方法對遮擋判別進行加速。隨著計算機技術的發(fā)展，目前的PC機逐漸都是雙核或四核處理器，使得在PC機上能夠很容易實現(xiàn)并行算法。對于遮擋判別問題來說，由于每個面元的判別過程是獨立于其它面元的，不存在前后的因果關系。因此，可以在樹形結(jié)構加速的基礎上，采用并行處理技術，對遮擋判別再次加速。下面列出采用并行技術后，VFY-218和Tank的遮擋判別時間。

3.2 算法并行化后的效率分析

表2中列舉的樹形結(jié)構為3層時，是否采用并行技術判別遮擋的計算時間比較。當采用并行技術時，進程數(shù)的選取分別為2、4和8。當采用的并行技術后，從表2中可以看出遮擋判斷的時間顯著降低。然而，隨著進程數(shù)的不斷增加，時間并沒有按照反比的關系降低，原因是程序在執(zhí)行過程中還存在著進程之間的通信，浪費了少部分時間。

4 結(jié)論

本文提出了一種基于樹型結(jié)構的陰影區(qū)域識別方法，用于三維目標的高頻電磁散射計算。該方法將利用樹型分組結(jié)構將三維目標分為若干區(qū)域，從而將面元與面元之間的遮擋關系轉(zhuǎn)變?yōu)槊嬖c分組之間的遮擋關系。由于分組數(shù)目在數(shù)量級上遠小于面元數(shù)目，因此本文提出的遮擋識別方法與傳統(tǒng)方法相比，計算時間可以降低一個數(shù)量級。此外，本文還在樹型結(jié)構的基礎上，引入并行技術，在原有加速的效果上，再次減少計算量。樹型結(jié)構和并行技術的結(jié)合使用，使高頻電磁散射分析中的遮擋判別的計算量問題得到較好解決。飛機和坦克模型的數(shù)值算例也證明了本文提出的方法的正確性和高效性。

[1] Ascher U, Mattheij R, Russell R. Numerical Solution of Boundary Value Problems for Ordinary Differential Equations [M]. US: Prentice-Hall, 1988: 100-120.

[2] Harrington R. Field computation by moment methods [M]. Malabar, Fla.: R. E. Krieger, 1968: 100-120.

[3] Chew W, Jin J, Michielssen E. et al. Fast and Efficient Algorithms in Computational Electro- magnetics [M]. Boston, MA: Artech House, 2001: 100-120.

[4] 張曉燕, 李子, 江代力,等. 隨機粗糙面上電磁散射的高效迭代IEM計算[J]. 華東交通大學學報，2012, 25(3): 16-20.

[5] Chen R, Yung E, Chan C. et al. Application of SSOR preconditioned conjugate gradient algorithm to edge-FEM for 3-dimensional full wave Electromagnetic boundary value problems [J]. IEEE Trans. MTT., 2002, 50(4): 1165-1172, 2002.

[6] Chen R, Ping X, Yung E. Application of Diagonally Perturbed Incomplete Factorization Preconditioned CG Algorithms for Edge FEM Analysis of Helemholtz Equations [J]. IEEE Trans. AP., 2006, 54(5): 1064-1068.

[7] Knott E. A progression of high-frequency RCS prediction technique [J]. IEEE Proceedings, 1985, 73(2): 252-264.

[8] 劉志偉, 張月園, 陳嘉琪,等. 移變模式雙站SAR信號模型及電磁仿真研究[J]. 華東交通大學學報，2012, 25(1): 24-29.

[9] F. Saez de Adana, Gonzalez I, Gutierrez O, et al. Asymptotic method for analysis of RCS of arbitrary targets composed by dielectric and / or magnetic matericals [J]. IEE Proc. Radar Sonar Navig., 2003, 150(5): 375-378.

[10] Liu Z, Ding D, Chen R. Octree based technique for fast analyzing shadowing relationship of complex target [C]. APMC, Hongkong, China. 2008.

[11] Lu C, Chew W. Fast algorithm for solving hybrid integral equations [J]. IEE Proceedings-H, 1993, 140(6): 455-460.

[12] Song J, Chew W. Multilevel fast-multipole algorithm for solving combined field integral equations of electromagnetic scattering [J]. Micro. Opt. Tech. Lett., 1995, 10(10): 14-19.

PARALLELED MULTIPLE SHADOW RECOGNITION ALGORITHM FOR EVALUATION OF HIGH FREQUENCY RCS

*ZHANG Yue-yuan1, LIU Zhi-wei2,3, ZHANG Xiao-yan2,3, LIU Ying-ting2, HE Shan2

(1. International School, East China Jiaotong University, Nanchang, Nanchang, Jiangxi 330013, China;2. School of Information Engineering, East China Jiaotong University, Nanchang, Jiangxi 330013, China;3. State Key Laboratory of Millimeter Wave, Southeast University, Nanjing, Jiangsu 210096, China)

Using physical optics method to evaluate high frequency radar cross section (RCS), the shadow recognition is required and time consuming. A tree structure based method is proposed for multiple shadow recognition. Judging whether a facet is obstructed by another facet is replaced by judging whether a facet is obstructed by another sub-group. The computational complexity is able to be reduced greatly by this method. Furthermore, the parallel technique is introduced. The computation time can be saved by the paralleled tree-base multiple shadow recognition algorithms. Numerical results demonstrate that the proposed method is more efficient than traditional method.

electromagnetic field; high frequency scattering; paralleled shadow recognize; computational electromagnetic; physical optics

O441.4

A

10.3969/j.issn.1674-8085.2013.04.009

1674-8085(2013)04-0041-05

2013-05-15；

2013-05-26

國家自然科學基金項目(61261005)；毫米波國家重點實驗室 (K201326)；江西省科技廳青年基金項目 (20122BAB211018)；江西省教育廳青年基金項目(GJJ13321)

*張月園(1981-)，女，浙江金華人，講師，碩士，主要從事計算機應用技術研究 (Email: aney0360_cn@sina.com);

劉志偉(1982-)，男，江西南昌人，講師，博士，主要從事計算電磁學研究 (Email: zwliu1982@hotmail.com);

張曉燕(1979-)，女，云南楚雄人，副教授，博士，主要從事計算電磁學研究 (Email: xy_zhang3129@sina.com);

劉穎婷(1988-)，女，湖南冷水江人，碩士生，主要從事計算電磁學研究 (Email: yingtingmm@163.com);

何 姍(1989-)，女，安徽安慶人，碩士生，主要從事計算電磁學研究 (Email: lucky-shan@163.com).