基于改進人工魚群算法的稀疏系統估計

張思 厲丹

摘要：稀疏系統估計問題近年來受到了廣泛的關注，本文以水聲通信信道為背景，提出了一種新穎的人工魚群算法，用于估計受多普勒效應影響的稀疏水聲信道。在水聲通信系統中，多普勒效應導致的通信信號在時間上的擴展或壓縮，同時水面和水底的反射使得水聲信道呈現多擴展多時延特點，因而水聲信道通常被建模為多擴展多時延信道，呈現較強的稀疏性。利用該特性，水聲信道的估計可進一步簡化為每一條路徑的參數估計（多普勒擴展因子，時延和幅度）?；诖?，正交匹配追蹤算法在水聲信道估計中得到了廣泛的應用，但其估計精度的提升依賴于字典的大小，因而估計的高精度以高復雜度為代價。為了解決這個問題，本文提出了改進人工魚群算法，以迭代的形式進行多徑參數的估計，迭代結束時根據人工魚位置信息估計時變信道參數，重構目標信號，直至剩余信號能量小于設定閾值。仿真實驗表明，所提算法具有較高的估計精度和較快的收斂速度，并具有比正交匹配追蹤算法更低的復雜度。

關鍵詞：稀疏系統估計;人工魚群算法;水聲信道

中圖分類號：TP393

文獻標識碼：A

文章編號：1009-3044（2020）04-0183-03

收稿日期：2019-10-15

基金項目：徐州市科技計劃項目（KC18011）

作者簡介：張思（1997—），女，安徽廣德人，本科;厲丹（1981—），女，江蘇徐州人，副教授，博士，主要研究方向為大數據云計算。

Artificial Fish Swarm Algorithm-Based Sparse System Estimation

ZHANG Si，LI Dan

（Information and Electrical Engineering College，Xuzhou Institute of Technology，Xuzhou 22 1000，China）

Abstract：In recent years，the sparse system estimation has received extensive attention.In the background of underwater acoustic （UWA）communication，we propose a novel artificial fish swarm algorithm and apply it into the estimation of Doppler-distorted sparse underwater acoustic channel in this paper.In UW A communication，the Doppler effects lead to the signal scaling or compressing in the time-domain，while extensive reflections from the surface and bottom of the ocean contribute to the multi-scale multi-lag （MSML）char-acteristic of the UWA channel，which thus can be modelled as MSML channel，being strongly sparse.exploiting this nature，the estima-tion of UWA channel can be further simplified by estimating the parameters for each path （Doppler scale factor，delay and amplitude）.Based on this，orthogonal matching pursuit （OMP）algorithm has been widely used.But the estimation accuracy of OMP depends on the size of the dictionary and finer resolution requires higher computational complexity.To address this issue，we propose the improved arti-ficial fish swarm algorithm （IAFSA），proceeding in an iterative manner，and obtaining the parameters for each path from the position of fish at the end of iteration to reconstruct the desired signal.The iteration continues until the residual signal energy is lower than the threshold.The simulation results show that IAFSA can obtain high estimation accuracy as well as fast convergence speed，and outper-forms OMP algorithm in terms of computational complexity.

Key words：Sparse System Estimation;Artificial Fish Swarm Algorithm;Underwater Acoustic Channel

水聲信道呈現的明顯多普勒效應和嚴重的多徑傳播特點給高速率水聲通信帶來了極大的挑戰。在水下通信系統中，聲波的傳播速度僅為1500m/s，遠低于陸地無線通信中電磁波的傳播速度（3x10*m/s），因而收發端移動等帶來的多普勒效應更加顯著，具有時變特性，因此，信道呈現嚴重的時間選擇性。對于時變信道，可以近似認為在較短的時間內，信道是線性變化的，因此可以將多普勒效應建模為多普勒擴展因子，其表現為引起信號在時域上的擴展或壓縮[1]。而水下環境中的大量反射和折射使得多徑干擾嚴重，即較大的多徑擴展，造成長時延和嚴重的符號間干擾。為了充分利用信道特點，精確的信道建模具有十分重要的意義。

大量實驗結果表明[2]，接收端的信號是來自不同路徑信號的疊加，而每一條路徑具有不同的時延，能量和多普勒因子，因此，水聲信道通常被建模為多擴展多時延信道，并廣泛應用于實際通信系統[1]。該模型將每一條路徑 參數化為多普勒因子，時延和幅度。然而，由于嚴重的多徑擴展，水聲信道大量多徑的存在給計算帶來了挑戰。為了克服該缺點，很多研究充分利，用水聲信道的稀疏特性，即，大部分能量集中在主要的幾條路徑上，所以，僅有少量的路徑參數需要估計。這在很大程度上降低了計算的復雜度，相應的，很多基于壓縮感知的稀疏估計算法得到了應用[4-7]。

這些算法大致可以分為兩類：動態規劃類如匹配追蹤算法;線性規劃類如基追蹤算法?；粉櫵惴ㄝ^高的復雜度限制了其在實際中的應用，因此，我們主要關注匹配追蹤算法及其改進算法。在文獻[4]中，匹配追蹤算法被應用于迭代地估計不同路徑的多普勒因子，在每一次迭代中，選擇字典中與剩余信號相關性最大的列，并更新剩余信號用于下一次迭代。在此算法的基礎上，對剩余信號進行正交化，即得到正交匹配追蹤算法，如[5]，正交匹配追蹤算法具有更快的收斂速度和更好的估計精度。隨后又有一些改進算法提出，如針對自適應估計路徑數的稀疏自適應匹配追蹤[6]和自適應變步長匹配追蹤[7]。

匹配追蹤算法及其改進算法的主要缺點在于其估計精度依賴于字典的規模，為了保證較高的估計精度，字典的列數可能會變得很大。在水聲信道估計問題中，由于信道的時延和多普勒擴展跨度較大，往往需要建立很大規模的本地字典。為了克服這個問題，我們提出一種改進的人工魚群算法，用于稀疏水聲信道估計。人工魚群算法是智能算法的一種，其能夠利用魚群之間的競爭和合作快速找到問題的最優解[8]。實驗表明，該算法在保持較低的復雜度的同時可獲得較高的估計精度。

1 信道模型

多擴展多時延信道模型可以表示為：

其中，L是信道抽頭數，Al（t）是第l條路徑的時變信道幅值，在較短的時間內，如一幀符號時間，可以假設為常數。τ1和al分別是第l條路徑的時延和多普勒因子，8（·）是沖擊響應函數，定義為：

s（t）表示發射信號，相應的接收信號r（t）可以寫成：

其中w（t）是加性噪聲?？紤]到水聲信道的稀疏特性，（1）式中只有少數抽頭系數非零，即接收信號r（t）只是有限個發送信號s（t）的時延-擴展版本的疊加。所以，信道估計的復雜度大大減小。

2 改進人工魚群算法

2.1 人工魚群算法簡介

人工魚群算法（artificial fish swarm algorithm，AFSA）是一種基于人工智能的算法，包括模擬人群的捕食，聚群和跟蹤行為來進行優化問題的求解。

令X。表示人工魚p的位置：

其中P為魚群大小，N為位置維數。相應的，位置X。對應的適應度值為：

f（.）函數根據具體的問題目標而定。定義兩條人工魚Xp

和Xq之間的距離為：

人工魚群的基本行為包括：

1）捕食：假設人工魚p的當前位置為X，其在視覺范圍內隨機選擇位置X，，如果y，》y，則該人工魚向位置X。移動一步，即

其中△是步長，這個過程將重復I次直到有一個X。滿足要求;否則，該人工魚將在視野范圍內隨機選取一點。

2）聚群：令X。為人工魚p的位置，其視野內有Q個同伴，如果Q》 0，計算這Q個同伴的中心位置：

定義λ為擁擠度因子，如果yc/Q》λy，，則人工魚p將會向X。移動一步;否則，將執行覓食行為。若Q=0人工魚也將執行覓食行為。

3）追尾：人工魚p的視野范圍內有Q個同伴，如果Q》0，找到具有最大適應度值y，的同伴X。。若y，/Q>λyp，人工魚p將向X。移動一步，若y，/Q≤λyp或者Q=0，人工魚p將執行覓食行為。

2.2 改進人工魚群算法與信道參數估計

令每一條魚的位置表示一條路徑的多普勒因子和時延，{a，r}=，r（t）為接收信號，s（t）為訓練序列，路徑XP的信號可以表示為s*（t），適應度值為：

該值即估計的路徑幅度：f（Xp）=Ax。因此，經典的人工魚群算法可以直接應用于單路徑信道參數值估計，然而，對于多時延多擴展信道，接收信號是來自于多條不同參數的路徑信號的疊加組合，經典人工魚群算法不再適用。

基于匹配追蹤算法的迭代思想，本文提出改進的人工魚群算法（IAFSA），迭代的進行多徑參數的估計，具體算法如下：

輸入：發射信號向量s;接收信號向量r;路徑數L;閾值ε。

初始化：

設置剩余信號r。=r，擁擠度因子λ，視野范圍D，步長△，嘗.試次數I，最大子迭代次數k。，設置l=1。

迭代：

1在問題空間內隨機初始化魚群位置X。（p=1，…，P），計算相應的適應度值y。（p=1，…，P），并將最優適應度值you及其對應的位置Xo記錄到公告板中。

2.設置計數器k=1。

3.執行聚群和追尾行為，更新人工魚位置。

4.計算相應的適應度值并更新公告板。

5.當k>hm/2時，如果公告板保持不變且yopt>e，將一半的魚位置調整為Xopt。

6.設置k=h+1，并調整步長為△=（1，）A，跳轉到步驟3循環執行，直至k>hmx。

7.從公告板選擇最優位置Xopt作為路徑l的時延和多普勒因子估計值，得到相應的時延-多普勒訓練序列st，和最優適應度值yopt作為路徑l的幅度估計值At，更新剩余信號：re=re-Atst

8.如果l=L，停止迭代;否則，l=l + 1，跳至步驟1.

輸出：估計參數對{A，a，i}h=1。

注：路徑數L可以在信號同步階段獲得;閾值ε根據接收端所能夠檢測到的信號能量值來設定。

3 實驗結果

我們使用計算機仿真驗證所提算法的性能，并與正交匹配追蹤（OMP）算法的性能進行比較。信道采用文獻[3]中的參數：路徑數L=10，各路徑信號的到達時間隨機分布在0-25ms。歸一化路徑幅值均勻分布，多普勒擴展因子隨機分布在[1，1.02]。用長度為511的偽隨機序列作訓練序列，且用二進制相移鍵控調制。載波頻率為10kHz，采樣率為20kHz。

對于OMP算法，所構造的字典多普勒因子分辨率為1x10-4，時延分辨率為0.1 ms，多普勒擴展為0.02，時延擴展為25 ms，這也是IAFSA的問題空間。IAFSA 的參數設置為：魚群大小為50，擁擠度因子為0.3，視野范圍為[0.005，1.0ms]，初始步長為0.2，最大子迭代次數等于10，最大嘗試次數等于10，閾值ε=0.2。

圖1—圖3給出了不同信道條件下，多普勒擴展因子估計的歸一化均方誤差（NMSE）時延估計誤差和剩余信號能量比隨信噪比（SNR）的變化而變化的仿真曲線，并與OMP算法做了比較。

圖1顯示，IAFSA在多普勒因子的估計精度上優于OMP算法。OMP算法的估計精度取決于字典的規模，而IAFSA能夠在子迭代中動態調整步長值，以減小估計誤差，同時，在搜索的最后階段，大量人工魚集中于最優值附近，也保證了得到更精確的搜索值。

圖2顯示，當信噪比大于8dB時，兩種算法均趨于穩定且IAFSA獲得更低的時延估計誤差。該增益實際上來源于IAFSA在迭代的最后階段具有更小的搜索范圍。

同樣，圖3進一步從剩余信號能量比的角度比較了兩種算法，并將已知真實信道信息時的剩余信號能量比曲線作為最優估計對比。當信噪比大于2 dB時，IAFSA可以獲得約為2 dB的增益。

從仿真圖可見，本文所提算法的性能都明顯優于OMP算法。另一方面，在計算復雜度上：設訓練序列長度為K，對于OMP算法，字典中的列數為N=N。N，，為時延和多普勒網格數之積。因此，一次迭代的乘積運算為ρ=NK。對于信道1，N，=250，N。=200，因而N=5x10;對于信道2，N，=250，N。=100，因而N=2.5x10*。

而對于IAFSA，信道1和信道2中，每一次迭代包含的子迭代過程中，人工魚分別執行聚群和追尾行為，最差的情況下需要搜索21次，因而一次迭代的乘積運算為ρ=K.Pkm 21，即ρ=1X 10*?？梢?，所提算法的計算復雜度優于OMP算法。

4 結論

為了解決利用傳統匹配追蹤算法及其改進算法估計稀疏系統參數存在的計算復雜度高，估計精度受限于字典的大小的問題，本文提出了一種新穎的多普勒失真水聲信道估計方案，以迭代的方式分離多徑分量，并在子迭代中自適應的調整人工魚的位置和步長。與正交匹配追蹤算法相比，改進的人工魚群算法顯著降低了多擴展多時延信道的估計復雜度，且估計精度也有所提升。

參考文獻：

[1]Qu F Z，Wang Z D，Yang L Q，et al.A journey toward modeling

and resolving Doppler in underwater acoustic communications[J].IEEE Communications Magazine，2016，54（2）：49-55.

[2]Mason S F，Berger C R，Zhou S L，et al.Receiver comparisons

on an OFDM design for Doppler spread channels[C]/OCEANS2009-EUROPE，May 11-14，2009.Bremen，Germany.IEEE，2009：2201-2208.

[3]Daoud S，Chrayeb A.Using resampling to combat Doppler scaling in UWA channels with single-carrier modulation and fre-quency-domain equalization[J].IEEE Transactions on Vehicular Technology，2016，65（3）：1261-1270.

[4]Cotter S F，Rao B D.Sparse channel estimation via matching pursuit with application to equalization[J].IEEE Transactionson Communications，2002，50（3）：374-377.

Asilomar Conference on Signals，Systems and Computers，October26-29，2008.Pacific Grove，CA，USA.IEEE，2008：581-587.

[5] Tropp J A，Gilbert A C.Signal recovery from r ran dom measure ments via orthogonal matching pursuit[J ].IEEE Transactions on Information Theory，2007，53（12）：4655-4666.[LinkOut]

[6] Do T T，Gan L，Nguyen N，et al.Sparsity adaptive matching pursuit algorithm for practical compressed sensing[C]//2008 42nd Asilomar Conference on Signals，Systems and Computers，October 26-29，2008.Pacific Grove，CA，USA.IEEE，2008：581-587.

[7] Zhang Y，Venkatesan R，Dobre 0 A，et al.An adaptive matching pursuit algorithm for sparse channel estimation[C]//2015 IEEE W ireless Communications and Networking Conference （WCNC），March 9-12，2015.New Orleans，LA.IEEE，2015：626-630.

[8] Jiang M Y，Li C C，Yuan D F，et al.Multiuser detection Based on wa elet packet modulation and artificial fish swarm algorithm[C]//IET Conference on W ireless，Mobile and Sensor Networks 2007 （CCWMSN07），Shanghai，China.IEE，2007：117-120.

[通聯編輯：唐一東]