前言：中文期刊網精心挑選了貪婪算法的基本原理范文供你參考和學習，希望我們的參考范文能激發你的文章創作靈感，歡迎閱讀。
貪婪算法的基本原理范文1
【關鍵詞】壓縮感知 非相參 正交匹配追蹤 欠采樣 信號重構
1 引言
通過查閱文獻及相關資料得知，當前雷達的工作頻段不斷地向高頻方向發展，大多數雷達工作在超短波及微波波段，其頻率范圍在30～300000兆赫，而傳統的Nyquist采樣定理規定信號的采樣率不得低于信號帶寬的2倍，并且工程實際應用中對于采樣率的選擇通常更高。因此，在Nyquist理論限制下，雷達數據無疑是極其龐大的，而這巨大的數據量中，有相當一部分其實是冗余的，這樣雷達信號的獲取、存儲、傳輸就成為了制約雷達技術發展的瓶頸之一。
目前，國內對于壓縮感知在雷達信號處理方面應用的研究大都集中在相參、高分辨、寬帶雷達信號上，誠然，相參高分辨雷達信號確實很需要壓縮處理，例如，文獻[3]研究的就是非合作寬帶脈沖壓縮雷達信號的壓縮感知處理；但是，比起相參雷達信號，非相參雷達信號其距離、速度模糊函數都具有更好的稀疏性[5]，也就是說，非相參雷達信號應該更適合應用壓縮感知處理，所以本文著重對這方面進行了研究。并且，在非雷達通信領域，壓縮感知的應用面也是極其廣泛的，理論一經提出，就在信息論、信號處理、圖像處理等領域受到高度關注。
本文運用一系列實驗數據驗證了，壓縮感知理論在非相參雷達脈沖信號的壓縮處理方面具有實際可行性，并且具有廣泛的應用前景。
2 壓縮感知理論
傳統的信號處理方法一般來說是先對信號進行奈奎斯特采樣，然后壓縮處理，這種處理方式毫無疑問的會造成很大的資源浪費。
根據壓縮感知理論，只要信號是可壓縮的或在某個變換域是稀疏的，那么就可以用一個與變換域不相關的測量矩陣將變換所得高維信號投影到一個低維空間上，然后通過求解一個優化問題就可以從這些少量的投影中以高概率重構出原信號，可以證明這樣的投影包含了重構信號的足夠信息；由此可以總結出壓縮感知的三要素：
2.1 稀疏基
一般可供選擇的稀疏基有小波基、DCT基、傅里葉變換基等。
2.2 觀測矩陣
一般可選擇的觀測矩陣有：高斯隨機矩陣、部分Fourier集、部分Hadamard集等；觀測矩陣必須滿足RIP性質。
2.3 信號重構算法
常用的重構方法主要有貪婪追蹤算法、凸松弛算法和組合算法這三大類。
綜上所述，壓縮感知處理的過程可以簡要描述為：首先找到與待處理信號匹配性最好的稀疏基（即待處理信號稀疏性最強的稀疏基），基于信號在其上的稀疏性或可壓縮性，設計出一個不相干且觀測維數M遠小于信號維數N的觀測矩陣，最后通過非線性優化重構算法重構出原始信號；這樣在存儲、傳輸過程中，可以使用壓縮觀測后的數據，從而極大地節約了存儲空間和傳輸速率。
3 實驗結果及分析
實驗所用信號來源于長江水面某處船舶監管系統雷達的監控，使用了其掃描一周所得的一幀的數據，是典型的非相參船舶雷達脈沖信號，經數據采集卡數字化處理后，得到原始的雷達數據，原圖中可以清楚的看到一座大橋和些許船只。
3.1 不同重構算法對于重構性能的影響
本文分別采用了子空間追蹤算法（SP）、迭代硬閾值算法（IHT）、貪婪基追蹤（GBP）和OMP等四種算法來進行對比實驗，壓縮比均為0.5，分別從重構性能和重構時間等兩方面進行對比根據實驗所得效果圖及實驗數據可以明顯地看出，在處理非相參雷達數據時，OMP算法無論是在峰值信噪比這種性能指標方面，還是在實際處理效果圖方面，都要明顯優于其余三種算法；而且在重構時間上來說，OMP算法的時間雖然略大于IHT算法，但鑒于IHT算法極差的重構效果，所以，綜合考慮來說，OMP算法無疑是最佳的選擇。
4 總結
壓縮感知是一種新穎且發展前景良好的信號處理方面的理論，它打破了傳統奈奎斯特采樣定理對于采樣率的束縛，極大地壓縮了采樣率和數據量，這對于通信行業來說是具有重大意義的。目前，壓縮感知理論在雷達方面的應用仍處于仿真驗證的初步階段，且大都集中于相參雷達信號的處理方面。本文首先簡要地介紹了壓縮感知的基本原理，然后著重驗證了其在非相參雷達脈沖信號處理方面的可行性，并且對于重構算法和稀疏基的選擇做出了實驗論證，從而體現了壓縮感知在雷達數據的采樣、存儲和傳輸方面的巨大潛力。但是，壓縮感知在雷達信號處理上的應用仍存在些許待研究的問題，例如：稀疏基和觀測矩陣的設計是否能夠具有更強的自適應性，重構算法能否進行簡化，中間的一些迭代步驟能否進行并行處理，畢竟，現有的重構算法的運算量都是巨大的。這些問題都有待解決。
參考文獻
[1]D L pressed sensing[J].IEEE Trans.on Information Theory，2006， 52（4）：1289-1306.
[2]E Cand s，J Romberg，Terence Tao. Robust uncertainty principles：Exact signal reconstruction from highly incomplete frequency information[J]. IEEE Trans.On Information Theory， 2006，52（2）：489-509.
[3]葉昊儒.相參雷達與非相參雷達的差異分析[J].現代電子技術，2010，03-017-03.
作者簡介
劉思宇，男，現為大連海事大學碩士研究生在讀。主要研究方向為壓縮感知在雷達信號處理方面的應用。
貪婪算法的基本原理范文2
Differential Evolution Algorithm to Size
the Optimization of Truss Structures
TANG He-sheng1, FAN De-wei1, WANG Zhao-liang1, XUE Song-tao1, 2
(1. Research Institute of Structural Engineering and Disaster Reduction, Tongji Univ, Shanghai 200092，China;
2. Dept of Architecture, Tohoku Institute of Technology, Sendai 982-8577, Japan)
Abstract:
This paper applied a DE strategy to solve the size optimization problems of truss structures with stress and displacement constraints. We presented the basic principle of the original DE algorithm in detail, and then introduced the mathematical model for truss optimization. Several classical problems were solved by using DE algorithm, and the results were compared with those using other optimization methods. Numerical examples have shown that the DE algorithm has good convergence and stability and can be applied to effectively size the optimization of truss structures.
Key words: structure; differential evolution;truss structures;size optimization
任何一個結構的設計方案，都可以用若干給定參數和一些設計變量xi (i＝1，2，…，n)來體現，而設計變量隨方案的改變而變［1］.所謂結構優化設計就是用力學和數學的方法，在可用域搜索目標函數最小(或最大)的所謂最優點，也就是最優設計方案.桁架結構優化設計根據設計變量的類型可分為3個層次：尺寸優化、形狀優化和拓撲優化.桁架結構尺寸優化即為在給定結構形式、材料和布局拓撲的情況下，優化各個桿件的截面尺寸，使結構總體質量最輕.
傳統的結構優化方法主要有力學準則法(OC)、數學規劃法(MP)等［2］.由于結構優化設計問題是一非凸的和多峰的問題，傳統的一些優化算法解決此類問題具有很大的局限性.而最近30多年發展的一些現代仿生智能優化算法，如遺傳算法、模擬退火、蟻群算法、PSO算法等在結構優化領域也得到了廣泛應用［3-6］，并成為人們研究的熱點.
微分演化 (Differential Evolution，DE)作為一種新穎的算法，自從1997年被Storn和Price引入以來［7］，在解決復雜優化問題上得到了很多關注.作為一種混合算法，DE的主要優點是算法簡單，它結合了遺傳算法的更大種群概念和進化算法的自適應變異以及采用了貪婪選擇策略.同時，DE算法用浮點語言取代了在許多傳統進化算法中的二進制語言，控制變量少，執行起來更簡單.這些特征使DE算法相比進化算法和遺傳算法魯棒性更好、收斂更快.研究表明，針對復雜的優化問題，DE算法相對于PSO算法和遺傳等其他算法具有更加精確、更快的收斂速度和較強的魯棒性的特點［8］.該算法已被應用于工程設計［9］、可靠度分析［10］、主動控制［11］問題，例如：三維車輛結構的優化［12］、渦輪的形狀優化［13］.
本文采用DE算法對平面桁架及空間桁架在單工況及多工況作用及多約束情況下進行尺寸優化設計.通過對典型桁架結構的優化并與相關文獻的結果進行對照，來評價該算法用于桁架優化的效果.
1 微分演化(DE)算法
一個包括n個參數的優化問題可以用一個n維的向量來描述，該向量可以表示為：xi=(xi1,xi2,…,xin)T∈S,i=1,2,3，…,NP.其中S∈Rn為優化問題的搜索空間；DE算法利用NP作為向量xi1每一代的個體數.類似于遺傳算法，DE算法通過變異、交叉和選擇過程實現種群的更新進化.具體過程如下.
1.1 變異過程
變異的目標是為了保證種群的多樣性，同時用合適的參數變化來指導已有的目標向量在合適的時間內達到一個更好的結果，從而保證搜索的魯棒性.
變異操作過程中，上一代的個體xi(G)，i=1，…，NP(其中G表示代數)， 根據不同的變異方式進行更新則得到第G+1子代向量vi(G+1）=(vi1(G+1),vi2(G+1),…,vin(G+1))T.本文采用Storn和Price ［7］推薦的DE/current-to-best/1/bin變異方式進行結構優化，該變異方式為 ：
v(G+1)i=x(G)i+F1(x(G)best－x(G)i)+
F(x(G)r1－x(G)r2).(1)
式中：x(G)best為算法第G代群體中適應值最小的個體；F和F1為變異常數，均為非負實數.它們的大小控制了變量間的差異，保證進化的進行.r1,r2分別為互不相同的整數，分別為從集合{1,2,…,i-1,i+1, …，NP}中隨機選出的向量編號.
1.2 交叉過程
與GA算法相似，DE算法中的個體經過變異后也進行交叉操作.對于群體中第G+1代經過變異過程后的向量個體vi(G+1)按照公式(2)進行交叉，產生新的個體：uij(G+1)=(ui1(G+1),ui2(G+1),…,u個體之間交叉的概率.
1.3 選擇過程
DE算法采用與GA算法不同的貪婪準則：通過比較由變異和交叉產生的子代個體和父代個體，選擇適應值好的變量，即如果父代個體適應值更優將繼續保留在群體中；否則，保留子代個體.選擇過程由式(3)表示：
x(G+1)i=u(G+1)i，if (f(u（G+1）i)
x(G)i，otherwise.(3)
通過對以上3個過程不斷重復迭代對種群進行進化，直到滿足算法停止條件，找到優化問題的最適解.
2 空間桁架結構優化
2.1 桁架結構尺寸優化的數學描述
2.1.1 設計變量
桁架結構的尺寸優化設計變量一般為桿件截面面積或截面特性參數.
2.2 基于DE算法的桁架結構尺寸優化程序
Step 1 輸入DE所需參數，如變異和交叉因子；初始化DE的種群，使第一代個體變量隨機在搜索空間中產生；it=1.
Step 2 進行結構分析，計算出每個個體所代表的設計變量對應的結構形態變量，如各桿件應力和節點位移.
Step 3 計算每個個體的評價函數值，對于違反約束的個體在其評價函數值加上一個非常大的常數罰值M，選出最優個體xbest.
Step 4 對每個個體根據式(1)進行變異操作，并且按照式(2)對每個個體(父代)以及變異個體進行交叉操作，得到新的個體(子代).
Step 5 計算各子代個體以及父代個體的適應值；按照式(3)選擇適應值好的作為下一代種群中的個體.
Step 6 計算每一個下一代的個體適應值，并找到最優的個體；如果新的最優個體的適應值比上一代xbest的適應值好，則更新xbest值，稱為當前最優個體.
Step 7 滿足算法終止條件，輸出最優個體xbest，以及最優個體的適應值，否則返回Step 2.
2.3 數值模擬與結果分析
用DE算法對幾個常用的桁架優化算例進行優化設計，以便與其他文獻進行比較，采用MATLAB編程.
例1 10桿平面桁架.求解該結構在應力和位移約束下的優化設計問題.優化目標為桁架結構質量最輕，選各桿的截面積為設計變量.各桿使用相同的材料，密度為2 768kg/m3，彈性模量為68 950 MPa，許用應力σ=±172.375 MPa，載荷P=444.822 kN，L=9.144 m.設計變量下限為64.516 mm2，上限為22 581 mm2，位移約束為各節點x,y方向的位移均不超過50.8 mm.結構如圖1所示.
為了分析算法的有效性，隨機運行5次優化程序，評價函數收斂曲線見圖2.取最好與最差結果，與其他文獻結果進行對比(見表1).
2.746注：質量欄的單位為kg，其余項單位為mm2.
隨機優化5次，迭代80次已經收斂，最優解為2 278.284，最差解為2 278.802，均值為2 278.632，標準方差為0.209.可以看出，DE算法得到的最好解與最差解均要優于所列文獻中的結果，證明了DE算法具有很強的尋優能力，同時5次優化結果的標準方差明顯小于其他方法，說明DE算法更加穩健.
例2 25-桿空間桁架(多工況).
25-桿空間桁架結構如圖3所示.該結構在多種研究結構優化算法時被提及討論，本文使用該結構作為算例便于與其他文獻進行比較分析.結構受2種荷載工況作用(見表2)，應力約束隨桿件組別而不同(見表3)，位移約束為各節點在x,y,z方向位移均不超過±88.9 mm.材料特性為E=68 950 MPa，ρ=2 768 kg/m3，L=635 mm.截面積范圍設為Amin =6.451 6 mm2，Amax =2 193.5 由圖3可見，70代已經收斂.DE隨機優化5次得到的最優解為247.155 8，最差解為247.160 1，均值為247.157，標準方差為0.001 8.由表4可以看出，DE算法的最好解與最差解均優于所列文獻最優結果，標準方差明顯小于其他算法.說明DE算法具有很好的收斂性能和極好的穩定性.
例3 72-桿件空間桁架 (多工況).圖5為4層72桿空間桁架結構及其節點、桿件編號方式.按對稱性將桿件分為16組(見表5).結構受兩個荷載工況的作用(見表6).材料特性為E=68 950 MPa，ρ=2 768 kg/m3，L=1 524 mm.約束條件為: 頂層節點沿x，y方向的最大位移不能超過6.35 mm，各桿最大允許應力［-172.375，172.375］ MPa.截面積范圍設為Amin=64.516 mm2，Amax =1 935.48 mm2.
由于設計變量為16維，變量維數高，而且為多工況共同作用，利用一般的優化算法對其進行優化時難度較大，利用DE則很容易解決該問題.從圖5可以看出，迭代100次時曲線已經收斂.從表5可知，DE算法最優解為172.228，最差解為172.287，二者均優于其他文獻所列結果，同時標準方差0.024說明算法具有很好的穩定性.
3 結 論
DE算法是一種新穎的基于種群混合進化算法，它結合了遺傳算法的更大種群概念和進化算法的自適應變異以及采用了貪婪選擇策略.本文將DE算法應用到3個典型桁架結構的優化問題，將得到的結果與其他文獻對比分析，結果表明DE算法收斂速度快，在滿足位移和應力約束條件下總能找到相對好的全局最優解，將DE算法應用于結構優化設計是可行的.
相對于其他算法而言，DE算法原理簡單，易于實現，特別是其初始參數設置簡單，算法魯棒性強.從對每個算例桁架隨機優化5次的結果可知，DE算法得到的最優值比GA，PSO，BB-BC等其他算法更加趨于最優解.同時5次最優解的標準方差明顯小于其他算法，驗證了DE算法的穩定性，說明了該算法適合于結構尺寸優化設計分析.
參考文獻
［1］ 王光遠. 結構優化設計［M］. 北京：高等教育出版社，1987:13-109.
WANG Guang-yuan. Structural optimization theory［M］. Beijing: Higher Education Press, 1987:13-109.(In Chinese)
［2］ 錢令希.工程結構優化設計［M］. 北京：水利電力出版社，1983:150-168.
QIAN Ling-xi.Structural optimization design［M］. Beijing: China Water Power Press, 1983:150-168. (In Chinese)
［3］ GALANTE M. Genetic algorithms as an approach to optimize real-world trusses ［J］. International Journal for Numerical Methods in Engineering, 1996,39(3): 361-382.
［4］ LAMBERTI L. An efficient simulated annealing algorithm for design optimization of truss structures ［J］. Computers & Structures,2008, 86: 1936-1953.
［5］ BLAND J A. Optimal structural design by ant colony optimization［J］.Engineering Optimization,2001,33(4):425-443.
［6］ LI L J, HUANG Z B, LIU F, et al. A heuristic particle swarm optimizer for optimization of pin connected structures［J］. Computers & Structures, 2007, 85(7/8): 340-349.
［7］ STORN R,PRICE K. Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces［J］. Journal of Global Optimization, 1997,11(4):341-359.
［8］ VESTERSTROM J, THOMSEN R. A comparative study of differential evolution, particle swarm optimization, and evolutionary algorithms on numerical benchmark problems［J］. Evolutionary Computation, 2004,2:1980-1987.
［9］ GONG Wen-yin, CAI Zhi-hua, ZHU Li. An efficient multi-objective differential evolution algorithm for engineering design［J］. Structural and Multidisciplinary Optimization,2009,4(2):137-157.
［10］COELH O, SANTOS L D. Reliability-redundancy optimization by means of a chaotic differential evolution approach［J］. Chaos Solitons Fractals, 2009,41(2):594-602.
［11］WU Zhi-feng, HUANG Hou-kuan, YANG Bei, et al. Amodified differential evolution algorithm with self-adaptive control parameters［C］//Proceedings of 3rd International Conference on Intelligent System and Knowledge Engineering. ISKE, 2008:524-527.
［12］VIAN A.CHEGURY F A. Differential evolution applied to the design of a three-dimensional vehicular structure［C］//Proceedings of the ASME International Design Engineering Technical Conferences and Computers and Information in Engineering Conference,2008,6(B):1321-1330.
［13］KARIN Z K. Shape optimization of turbine stage using adaptive range differential evolution and three-dimensional navier-stokes solver［C］//Proceedings of the 2nd IASTED International Conference on Computational Intelligence, 2006：212-217.
［14］CAMP C, PEZESHK S,CAO G. Optimized design of two-dimensional structures using a genetic algorithm［J］. Struct Eng,1998, 124(5): 551-559.
［15］SCHUTTE J J,GROENWOLD A A. Sizing design of truss structures using particle swarms［J］.Struct Multidiscip Optim,2003, 25:261-269.
［16］CAMP C V.Design of space trusses using big bang-big crunch optimization［J］. Journal of Structural Engineering,ASCE,2007,133(7): 999-1008.
貪婪算法的基本原理范文3
關鍵詞：邊界掃描技術；JTAG；邊界掃描設計
中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2011)24-6022-02
Fault Information Processing Test in Boundary Scan Technology Analysis
ZHU Xue-bin
(Guilin University of Electronic Technology, Guilin 541004, China)
Abstract: The boundary scan technology is a complete,standardized method of design fortestability, it provides a pair of elements on circuit board function, such as interconnection was tested with a unified plan,greatly improves thesystem efficiency testing. This paper introduces the boundary scan test principle, structure, discussed theapplication of boundary scan test technology.
Key words: boundary scan technology; JTAG; boundary scan design
集成電路的發展，特別是VLSI的出現和表面安裝工藝（SMT）的使用，使復雜的數字系統和A－SIC的測試變得越來越困難。鑒于此，聯合測試行動組（JTAG）致力于可測性設計方法――邊界掃描技術的標準化工作，并于1990年被IEEE接納，形成了IEEE 1149.1“測試存取口及邊界掃描設計”標準。JTAG標準通過邊界掃描技術使IC各管腳的可控制性和可觀察性達到了100％，支持從器件級直至系統級的測試。
1 邊界掃描技術的基本原理
邊界掃描技術的工作原理是：JTAG測試儀器使用一個四線測試接口，將測試數據以串行方式由TDI輸入到邊界掃描寄存器中，通過TMS發送測試控制命令，經TAP控制器控制邊界掃描單元完成測試數據的加載和響應數據的采集。最后，測試響應數據以串行掃描方式由TDO送出到JTAG測試儀器。JTAG測試儀器將捕獲到的響應數據與期望的響應進行比較，如果數據一致，則說明無故障存在。
邊界掃描測試總線由四個（另有一個TRST＊為可選）專用引腳組成：測試數據輸入（TestData In，TDI）、測試數據輸出（TestData Ou，t TDO）、測試模式選擇（TestMode Selec，t TMS）和測試時鐘（TestClock，TCK）。主要完成測試矢量輸入、測試相應輸出和測試控制。器件內邊界掃描結構主要由測試存取口（TestAccessPor，t TAP）、TAP控制器（TAPController）、指令寄存器（Instruction Register，IR）和測試數據寄存器（DataRegister，DR）等組成。
邊界掃描測試的所有操作都是經由測試訪問端口，在TAP控制器的統一管轄之下實現的。TAP控制器是一個16位有限狀態機，在TCK的上升沿時刻，TAP控制器利用TMS管腳的控制信號控制IC中的邊界掃描單元進行狀態轉換、測試數據的加載和測試響應數據的采集。測試指令和數據通過TDI輸入到測試邏輯，從TDI送入的數據在一定的周期（由指令或是測試數據寄存器決定）后將輸出至TDO。簡而言之，TAP提供了將指令／數據位流（bit stream）移位進入，或者移位出核心邏輯的機制。當其為指令位流時，用來選擇測試邏輯的哪個寄存器為有效。當其為測試數據位流時，用來傳送適當的激勵／響應到測試邏輯的當前有效組件中。
2 邊界掃描測試方法
應用邊界掃描技術，可實現器件間互連通路測試、器件和電路板的靜態功能測試和器件自測試。不同的測試在不同的工作方式下進行。這些工作方式可以通過加載相應指令到指令寄存器來選擇。
2.1 內測試（IN TEST）
內測試測試IC本身的邏輯功能，即測試電路板上集成電路芯片的內部故障。測試向量由TDI輸入，并通過掃描路徑移位將測試向量施加到芯片的核心邏輯輸入端，邊界掃描寄存器的輸出單元捕獲核心邏輯的輸出值即響應向量，根據輸入向量和輸出響應，就可以對電路板上各芯片的內部工作狀態做出測試分析。
在進行內測試時，通過邊界掃描測試總線發送自測試 “RUNBIST”命令，將芯片配置為自測試模式，自動完成測試矢量加載和測試響應分析，并通過邊界掃描測試總線輸出測試結果。
2.2 外測試方式（EXTEST）
外測試用于檢測各集成電路間連線以及板級互連故障，包括短路故障和斷路故障。此時邊界掃描寄存器把IC的內部邏輯與被測板上其他元件隔離開來。
器件間的互連通路測試是邊界掃描技術的基本測試類型之一?；痉椒椋簭幕ミB網絡一端的邊界掃描單元加載輸入值，發出外部測試“EXTEST”命令，然后通過互連網絡另一端的邊界掃描單元讀出響應值，根據輸入輸出結果即可判斷是否存在互連通路上的故障。
在電路板的測試中出現最頻繁的是斷路和短路故障，傳統的逐點檢查的方法既麻煩又費時，而通過邊界掃描技術的外部測試方式，把從TDO端輸出的邊界掃描寄存器的串行信號與正確的信號相比較，就可以方便有效地診斷出電路板引線及芯片引腳間的斷路和短路故障。這是邊界掃描技術一個非常顯著的優點。
2.3 采樣測試方式（SAMPLE／RELOAD）
采樣測試方式用于對一個正在運行的系統進行實時監控。當集成電路芯片處于正常工作狀態下，將其數據采樣下來，經掃描路徑送出來檢查系統的性能。
采樣測試在捕捉階段從輸入端并行輸入引腳的數據，為外測試做準備。輸入單元移出器件標識（ID Code）：選擇旁路寄存器，使數據在電路芯片間快速移位，可以觀察IC正常工作時輸入、輸出引腳的數據流。
此外還有多種測試指令，他們的存在和不斷擴充，使邊界掃描技術的應用得以拓展和延伸，為集成電路的測試提供有效方法。
3 邊界掃描鏈路的實現
3.1 掃描器件的設置
貪婪算法的基本原理范文4
（1.國防科學技術大學電子科學與工程學院，湖南長沙410073；2.中國94535部隊，江蘇徐州221000）
摘要：線陣三維SAR系統可實現對地面場景的三維成像，是近年來研究的熱點，但受載機平臺和實際條件的限制，其切航跡向分辨率難以提高。結合三維場景中的目標稀疏特征，提出了一種基于壓縮冗余采樣的線陣三維SAR超分辨成像方法。相比于匹配濾波成像方法，該方法需要較少的陣元數就可以進行超分辨成像，并且冗余基的采樣結構使成像位置更加精確，在抑制旁瓣的同時大大提高了切航跡向的分辨率。仿真實驗證明了算法的有效性。
關鍵詞 ：線陣三維SAR；壓縮感知；冗余采樣；三維成像
中圖分類號：TN911.7?34 文獻標識碼：A 文章編號：1004?373X（2015）16?0076?05
收稿日期：2015?04?20
基金項目：中國博士后科學基金（2014M562647）
0 引言
線陣三維SAR是一種典型的陣列SAR，工作于下視模式，其基本原理是在運動平臺上垂直于運動方向放置一個線性陣列天線，通過平臺運動合成虛擬面陣天線獲得面陣平面內的二維分辨率，并結合脈沖壓縮技術獲得雷達視線方向高分辨率，從而實現對觀測場景的三維成像[1]。線陣三維SAR 可以消除傳統機載側視SAR 成像時的陰影效應和頂底倒置現象，并且能解決二維SAR圖像的疊掩、透視縮短和陰影等失真問題，全方位地還原真實場景，更加客觀全面地反映地面信息[2]。然而，線陣三維SAR成像的難點在于機翼的結構和載荷限制了陣元的分布和數量，往往只能采用稀疏非等距天線進行布陣，此時陣元數不再滿足Nyquist 采樣率[3]，導致傳統的成像方法質量下降。
目前，大部分超分辨成像方法都是采用譜估計的技術，例如，旋轉不變子空間（ESPRIT）[4]算法和多信號分類方法（MUSIC）[5]等。但是，由于上述的譜估計方法必須滿足Nyquist 采樣率，因此不適用于稀疏非等距的天線布陣方式。
近年來，一種新興的壓縮感知（Compressed Sens?ing，CS）理論使得信息理解和獲取等方面發生了革命性的變化，引起了信號處理領域的研究熱潮[6?7]。CS 理論指出，只要信號是可壓縮的或在某個變換域是稀疏的，在滿足有限等距性質的條件下，就可以用一個與變換基不相關的觀測矩陣將變換所得的高維信號投影到一個低維空間上，然后通過求解一個優化問題就能重建原始信號[6]。CS理論突破了香農采樣定理的瓶頸，能夠有效地降低雷達成像系統的原始數據率，給線陣三維SAR超分辨成像帶來巨大變革。結合線陣三維SAR場景中目標的稀疏特征，本文提出了基于壓縮冗余采樣的線陣三維SAR 成像方法。相比傳統匹配濾波方法，減少了陣元數并大大提高了切航跡向分辨率。相比于傳統的CS適用的正交基，冗余基的結構提供了更多的采樣點，使成像結果更加精確。
1 壓縮感知基本理論
壓縮傳感理論指出，當信號在某個正交基函數下可稀疏表示或者可壓縮時，可以通過遠低于Nyquist采樣率的測量數據實現信號的重構。例如，信號x ∈ RN 在某正交基Ψ 下可以稀疏表示為如下的形式[8]：
式中：a 是信號x 在基Ψ 下的系數向量，并且只有K 個元素是非零的。
在CS 稀疏信號處理中，對信號x 的觀測是將x 投影到一組低維的測量矩陣Φ = [φ1 ] ,φ2 ,?,φN ∈ RM × N中，測量表達式為：
式中：矩陣Θ 稱為a 的測量矩陣。由于測量矩陣的維數M 小于信號x 的維數N ，這是一個病態線性的問題。文獻[9]指出如果矩陣Θ 滿足RIP性質和非相干性質，那么可以通過求解?1 范數下的最小化問題來求解向量a ：
求解上述問題可以采用貪婪遺傳算法、凸追蹤算法和組合算法等[10]。
2 線陣的三維SAR 成像模型
線陣三維SAR系統一般采用多輸入/多輸出（Multi?ple Input Multiple Output，MIMO）線陣，如圖1 所示，工作于下視模式，采用多發多收的陣列結構。其中，高度向是雷達波束照射方向；沿航跡向是載機的航行方向；切航跡向是機翼方向，即高度向和沿航跡向組成平面相垂直的方向[5]。
假設機翼上方向上安置N 個發射陣元，排布于機翼兩側，M 個接收陣元，其基于相位中心近似（PhaseCenter Approximation，PCA）原理[11]的等效陣列為均勻分布的收發共用T/R 的線陣，陣列中心位于原點，陣元數為NM ，間隔為d 。載機飛行高度為H ，沿x 軸以速度v 飛行，發射信號的中心頻率是f0。高頻激勵下，目標可采用Swerling模型，解調后的回波信號可表示為：
式中：?q 為第q 個目標的散射系數；t 表示快時間；u表示慢時間，rnq 是回波歷程，表示第n 個等效雷達陣元到第q 個點目標的距離。
在點目標位置(x ) q ,yq ,zq 確定的條件下，陣元的二維位置yn (u) = yn ,zn (u) = H 不隨u 的改變而變化，因此，對回波距離公式作泰勒展開，并約掉高次項，得到：
由圖1可知，線陣三維SAR相比于傳統二維SAR的區別是在機翼方向上布置了多個陣元。在成像處理方面，三維RD算法是對每個陣元的回波進行高度向和沿航跡向的壓縮處理，然后將等效個回波信號疊加后經過切航跡向聚焦而成[12]。各個方向上的壓縮過程都是與匹配函數相乘濾波的過程。切航跡向完成聚焦后，每一個方位?距離向單元的信號為：
3 成像算法
3.1 構造壓縮感知模型
對于傳統SAR 二維成像，其本質是三維真實場景投影到二維平面進行成像，因此在大多數情況下投影平面上的目標是不稀疏的。然而，線陣SAR 三維成像是直接對三維場景空間目標進行三維成像而不經過投影。由于大氣空間中不包含散射點，只有少數不同切航跡向的散射點存在于同一個方位向?距離向單元中，因此，在同一等高面上的目標點是稀疏的[13]，可以采用壓縮感知的算法進行超分辨成像。
根據式（6），經過切航跡向聚焦后的信號可以寫為矢量形式：
為零，方差為σ2 的高斯白噪聲。然而，由于機翼結構和載荷的限制，陣元之間不滿足等距排列，并且間距d 大于信號波長的一半。因此，為了降低硬件系統的成本并獲得更長的孔徑長度，采用稀疏非均勻陣列的方式采樣，這樣既可以減少天線陣元的個數，又可以降低旁瓣的影響[14]。稀疏非均勻陣列結構如圖2所示。
由圖2可知，稀疏非均勻陣列可以由均勻陣列在相應陣元位置的采樣M 行得到，相應的采樣矩陣為：
為了獲得良好的重構效果，只要重構個數滿足M ? O(Q log(N )) x Q ，便可進行精確重構。因此，稀疏非均勻陣列的信號模型可以改寫為：
時，就轉化成為等距陣列的信號模型。
根據式（3）的理論，可將上述問題轉化為求解?1 范數最優解的問題。本文選取正交匹配追蹤算法對信號進行優化重構，求出最優的稀疏解。
3.2 冗余結構采樣
事實上，解調信號經過壓縮之后可以視為許多正弦信號的疊加，并且是稀疏的。為了從較少的測量數據中求解最優信號，傳統的CS算法使用DFT基作為正交基，如式（8）中的a 。但一般來說，只有當散射點的位置與正交基決定的采樣點位置重合時，即：
才滿足求出最優的稀疏解的條件。然而，當散射點不落在采樣點的位置上時，即yq? ym ,ym = [y1 ] ,y2 ,?,yNx，成像結果使點目標落在與其最近的采樣點上，這樣會出現較大的誤差，成像效果受到很大的影響。
為了提高成像質量，采取冗余結構作為正交基。由于DFT是DTFT采樣得到的，對DFT進行插值，參照DTFT的結構[8]，得到更加密集的采樣點，使散射點落到采樣點的概率更大，這樣散射點的成像位置更加接近于真實值。
冗余因子可以表示為C = ρy df∈ N+ ，其中ρy 表示切航跡向的分辨率，即就是DFT基的空間采樣間隔；df表示冗余基的空間采樣間隔。那么，稀疏非均勻陣列的感知矩陣A 可以表示為：
式中Δ = 2π CNx 表示頻域采樣間隔。當C = 1 時，表示傳統的DFT 基結構。圖3 顯示了采用傳統DFT 基和冗余結構下的重構誤差對比圖。
4 仿真實驗
為了驗證本文提出基于壓縮冗余采樣的線陣三維SAR成像算法的性能，利用點目標仿真實驗進行分析。
仿真參數如表1所示。
根據以上的仿真數據，切航跡向的分辨率為：ρy = 10 m 。
為了研究冗余因子對超分辨成像效果的影響，從等距陣列中隨機抽取25%的陣元進行成像，圖4顯示的是冗余因子對切航跡向點擴展函數的影響。從圖中可以明顯看出，C = 10 的點擴展函數更加規整，但是主瓣寬度明顯增加。
圖5~圖7顯示的是點目標的三維成像結果，從圖像可以看出，RD算法產生了非常明顯的旁瓣，并且無法分開鄰近的目標點。當冗余因子為1時，壓縮感知也不能將鄰近的點目標分開。而當冗余因子為4時，壓縮感知算法不僅區分出了點目標，而且大大降低了旁瓣的影響。圖7給出了不同條件的噪聲對信號重構誤差的影響。從圖中可以看出，C = 1 和C = 2 的曲線基本上相同，說明冗余因子增加1對于壓縮感知的結果沒有太大的影響。而噪聲對C = 4 的誤差整體上小于C = 10 ，說明壓縮感知重構效果好壞和冗余因子的大小不成正比。通過點目標的實際位置可知，散射點正好全部落在C = 4定義的切航跡向采樣點上，所以使其重構誤差最小。不同噪聲對信號重構誤差的影響見圖8。
5 結語
針對線陣三維SAR陣元數量和分布受制于機翼長度和載荷的問題，本文采用了稀疏非等距陣元的排布方式，并闡述了一種基于冗余采樣壓縮感知的線陣三維SAR 超分辨成像方法。仿真實驗證明了該方法的有效性。相比于傳統的匹配濾波的方法，壓縮感知的方法對旁瓣進行了明顯的抑制。相比于傳統的正交基，冗余結構的正交基提供了更多的采樣點，提高了成像精度。本文提出的方法理論上不需要對原有系統進行較大的改進，通過冗余的方式可以得到較好的處理結果。然而較大的運算量是壓縮感知成像處理的缺點。但是隨著信號處理技術的發展，相信壓縮冗余采樣在線陣三維SAR超分辨成像領域有著廣闊的應用前景。
參考文獻
[1] 王斌，王彥平，洪文，等.線陣SAR三維成像分辨率分析[J].計算機仿真，2011，28（3）：282?286.
[2] WEI Shunjun，ZHANG Xiaoling，SHI Jun.“One?active”linear array SAR 3?D high resolution imaging via compressed sensing [C]// 2011 3rd International Asia?Pacific Conference on Synthetic Aperture Radar（APSAR）. Seoul，South Korea：IEEE，2011：1?4.
[3] ZHU Xiaoxiang，BAMLER Richard. Tomographic SAR inver?sion by L1?norm regularization?the compressive sensing approach [J]. IEEE Transactions on Geoscience and Remote Sensing，2010，48（10）：3839?3846.
[4] HALEY Colin. Talk about ESPRIT [J]. IEEE Transactions on Electronic and power，1986，32（5）：377?380.
[5] ZHANG Siqiang，ZHU Yutao，KUANG Gangyao. Imaging of downward?looking linear array three?dimensional SAR based on FFT ? MUSIC [J]. IEEE Geoscience and Remote Sensing Let?ters，2015，12（4）：885?889.
[6] LEE C P，ERTIN Emre，PARKER J T，et al. Sparsity and compressed sensing in radar imaging [J]. Proceedings of the IEEE，2010，98（6）：1006?1020.
[7] 韋順軍，張曉玲.基于壓縮傳感的線陣三維SAR成像方法研究[J].宇航學報.2011，32（11）：2403?2409.
[8] RAUHUT Holger， SCHNASS Karin， VANDERGHEYNST Pierre. Compressed sensing and redundant dictionaries [J]. IEEETransactions on Information Theory，2008，54（5）：2210?2219.
[9] ALESSANDRE Budillon，EVANGELISTA Annarita，SCHIRINZI Gilda. Three?dimensional SAR focusing from multipass signals using compressive sampling [J]. IEEE Transactions on Geosci?ence and Remote Sensing，2011，49（1）：488?499.
[10] TROPP J A，GILBERT A C. Sinal recovery from random mea?surements via orthogonal matching pursuit [J]. IEEE Transac?tions on Information Theory，2007，53（12）：4655?4666.
[11] 朱宇濤.多通道ISAR成像技術研究[D].長沙：國防科技大學，2011.
[12] 于春艷，謝亞楠，趙海蘭，等.基于新型陣列配置的機載MIMO?SAR下視三維成像性能研究[J].電子測量技術，2014，37（2）：64?69.
[13] WEI Shunjun，ZHANG Xiaoling，SHI Jun. Sparse reconstruc?tion for linear array SAR 3?D imaging based on Bayesian esti?mation [C]// 2011 IEEE CIE International Conference on Ra?dar（Radar）. Chengdu，China：IEEE CIE，2011，2：1522?1525.