基于壓縮感知理論的WSNs時序信號分段壓縮算法*

劉洲洲，徐繼良，韓　瑩，王曉柱（.西安航空學(xué)院，西安70077；.空軍西安飛行學(xué)院第五訓(xùn)練旅，四川南充6700；.中國電子進出口總公司，北京0006）

?

基于壓縮感知理論的WSNs時序信號分段壓縮算法*

劉洲洲1，徐繼良2，韓瑩3，王曉柱1
（1.西安航空學(xué)院，西安710077；2.空軍西安飛行學(xué)院第五訓(xùn)練旅，四川南充637100；3.中國電子進出口總公司，北京100036）

摘要：針對壓縮感知理論（CS）應(yīng)用在無線傳感器網(wǎng)絡(luò)中時序信號在傳輸過程存在壓縮比率低、通信能耗高等問題，提出了一種時序信號分段壓縮算法來解決在信號稀疏度未知及高稀疏度條件下，壓縮感知數(shù)據(jù)重構(gòu)算法中存在的重構(gòu)效率低，重構(gòu)精度差，影響網(wǎng)絡(luò)生命周期的問題。該算法將采集數(shù)據(jù)中非零元素個數(shù)作為分段依據(jù)，通過減少段內(nèi)非零元素組合數(shù)量來提高信號重構(gòu)精度，同時利用了壓縮感知理論特性實現(xiàn)了對信號的高壓縮率。實驗結(jié)果表明，在以混沌量子免疫克隆重構(gòu)（Q-CSDR）算法為重構(gòu)算法、在信號盲稀疏度及稀疏度高于40的條件下，能夠以大于0.4的壓縮比率對信號進行壓縮，其重構(gòu)信號的均方誤差小于0.01，能夠延長網(wǎng)絡(luò)壽命2倍左右。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；壓縮感知理論；時序信號；稀疏度；壓縮比率

時序信號即為普通時域內(nèi)的信號，其幅值按照時間先后順序依次排列。受能量所限，無線傳感器網(wǎng)絡(luò)通常采集和傳輸?shù)男盘栆詴r序信號為主，如何對時序信號進行壓縮和高效率傳輸，是目前無線傳感器網(wǎng)絡(luò)節(jié)約通信能耗、延長網(wǎng)絡(luò)壽命的主要研究方向。

目前，無線傳感器網(wǎng)絡(luò)領(lǐng)域中已有較多的壓縮算法，分布式小波壓縮算法［1- 2］DWC（Distributed Wavelet Compression）將圖像壓縮方式引入數(shù)據(jù)壓縮算法中并進行了一定的改動。DWC算法具有壓縮性能好，壓縮誤差小等優(yōu)點，但其缺點在于算法復(fù)雜度高、計算能耗代價大，且奇偶節(jié)點之間的大量通信會造成無線傳感器節(jié)點計算能耗過大而縮短網(wǎng)絡(luò)壽命。分段線性化壓縮算法［3-4］SDT（Swing?ing Door Trending）具有算法簡單、計算能耗低、計算速度快的優(yōu)點，能夠很好的應(yīng)用于無線傳感器網(wǎng)絡(luò)節(jié)點工作，但分段線性化壓縮算法的缺點在于壓縮比較小。利用各數(shù)據(jù)點間的線性關(guān)系進行分段數(shù)據(jù)壓縮的SDT算法在傳統(tǒng)文物監(jiān)測系統(tǒng)中性能較好的原因是因為數(shù)據(jù)變化幅度較小、變化速度較慢。而在信號幅度變化大、變化速率快的文物入侵偵測過程中分段線性化壓縮算法的性能受到很大影響。

壓縮感知理論［5-7］是近幾年來數(shù)據(jù)和信號處理的研究熱點之一，目前在無線傳感器網(wǎng)絡(luò)中得到了廣泛的應(yīng)用。壓縮感知理論突破了奈奎斯特采樣定理及香農(nóng)理論的限制性，能夠以遠小于經(jīng)典采樣方法獲取的數(shù)據(jù)量回復(fù)出高質(zhì)量的原始信號。數(shù)據(jù)重構(gòu)算法是壓縮感知過程中一個重要的環(huán)節(jié)，其關(guān)鍵問題在于如何從已知的低維數(shù)據(jù)中最大程度的恢復(fù)出高維數(shù)據(jù)。目前已有的壓縮感知數(shù)據(jù)重構(gòu)算法包括梯度投影算法［］、正交匹配算法［］、正則化正交匹配算法［10］、基追蹤法［］和基于混沌量子免疫克隆算法的數(shù)據(jù)重構(gòu)算法Q-CSDR［］。

當前的數(shù)據(jù)重構(gòu)算法在信號具有低稀疏度條件下均有較好的重構(gòu)性能，而對于高稀疏度和稀疏度無法預(yù)估計的信號則會出現(xiàn)重構(gòu)精度差、算法性能陡然下降等問題。針對以上問題，筆者在分析了壓縮感知數(shù)據(jù)重構(gòu)算法的基礎(chǔ)上，提出了基于壓縮感知理論的時序信號分段壓縮算法CS-TSSC（Tim?ing Signal Subsection Compression）。該算法具有分段方法簡單、壓縮算法復(fù)雜度低等優(yōu)點，能夠明顯提高盲稀疏度及高稀疏度條件下信號的重構(gòu)精度。

1　問題分析

利用線性測量獲得的稀疏數(shù)據(jù)對原始信息進行重建，并在可能的條件下盡可能的保證重建精度，是壓縮感知框架中最為關(guān)鍵的操作之一。原始信號的重構(gòu)過程可以通過求解式（1）的逆問題可以得到，然后通過式（1）獲取原始信號X的重構(gòu)信號：

現(xiàn)有的重構(gòu)方法總體分為3類：

1.1l22范數(shù)最小化重構(gòu)

l2范數(shù)實際上就是最小二乘方案，是最經(jīng)典的數(shù)據(jù)重構(gòu)方式，用l2范數(shù)方法表示如式（2）所示：

其中對于向量X，其lp范數(shù)定義為式（3）：

l2范數(shù)的最小化重構(gòu)能夠便捷的取得解析解，其形式見式（4）：

這種方法從理論上來講僅涉及到違逆矩陣乘法等理論，十分簡便，但在計算過程中無法獲得稀疏解，得到的解析解具有較多的非零元素。因此這種方法實用性并不高。

1.2l0范數(shù)最小化重構(gòu)

l0范數(shù)解決了l2范數(shù)最小化問題中的解析解非零元素過多的問題，在求解欠定線性方程組的時候，最小化解中的非零元素個數(shù)。l0范數(shù)與常規(guī)范數(shù)不同，其值為向量中的非零元素的個數(shù)，例如，對于n-稀疏的信號c，其l0范數(shù)為n。因此l2范數(shù)的最優(yōu)化問題轉(zhuǎn)化為式（5）：

在實際重建過程中，一般會允許一定的誤差存在，因此式（5）也可以表示為式（6）：

式中，ε為極小常量值。這類問題的求解，都是數(shù)值不穩(wěn)定的NP-完全問題，求解時需要窮舉稀疏向量c中的非零元素位置的種可能的組合。

1.3l1范數(shù)最小化重構(gòu)

Candes等人指出，滿足M≥nlog2(N/n+1)條件的前提下，利用獨立同分布的高斯觀測矩陣可以將l0范數(shù)問題轉(zhuǎn)化為l1范數(shù)問題，并利用式（7）精確重構(gòu)稀疏信號，可以高概率逼近可壓縮信號：

上式在應(yīng)用時也會允許存在一定的誤差，求解時使用式（8）：

求解l1范數(shù)最小化方法將非凸問題轉(zhuǎn)化為凸規(guī)劃問題，求解過程更簡單。尋找最小l1的解空間可以表示為一個線性規(guī)劃問題。但是使用l1范數(shù)進行數(shù)據(jù)重構(gòu)存在著計算復(fù)雜度高的問題，其計算復(fù)雜度為O(N3)?，F(xiàn)有的壓縮感知數(shù)據(jù)重構(gòu)算法大多都是基于以上3種問題而來：其中OMP算法解決的是l0范數(shù)問題，其核心內(nèi)容是以貪婪算法結(jié)合迭代方式選取感知矩陣A的列向量，使得被選中的列向量與當前的殘差向量具有最大的相關(guān)度，然后從觀測量中減去相關(guān)量，重復(fù)這個過程直至達到已知稀疏度n。Q-CSDR算法解決的是l1范數(shù)問題，算法本質(zhì)上仍是一種貪婪算法，其核心內(nèi)容是利用量子免疫克隆算法的尋優(yōu)特性，將式（8）作為目標函數(shù)，利用量子理論生成隨即種群、利用免疫克隆理論實現(xiàn)種群更新，不斷地在種群中尋找最優(yōu)個體。

2　基于壓縮感知理論的時序信號分段壓縮算法

2.1改進方法

從上述敘述可以看出，基于壓縮感知的數(shù)據(jù)重構(gòu)算法的本質(zhì)實際上是在不斷生成的種群中尋找原始信號。重構(gòu)算法的作用在于如何快速準確的尋找出重構(gòu)數(shù)據(jù)，其本質(zhì)上屬于NP-hard完全問題。當重構(gòu)信號的非零元素的位置組合數(shù)量過多時，解空間中的解數(shù)量巨大，造成了算法的復(fù)雜度過高，降低算法尋優(yōu)效率。下面對信號稀疏度已知以及盲稀疏度兩種情況分別進行分析。

在信號稀疏度已知的條件下，假設(shè)原始信號X長度為N，其稀疏度為K，其非零元素個數(shù)為N×K，則在對X進行重構(gòu)的過程中需要窮舉X中非零元素位置的種可能組合，設(shè)其幅值為均勻分布在［min，max］上，則根據(jù)概率論相關(guān)知識可知，其重建概率為如式（9）：

在盲稀疏度條件下，設(shè)原始信號X長度為N，則在重構(gòu)過程中需要對非零元素的分布組合及原始信號的稀疏度同時進行窮舉，其排列組合數(shù)量為，設(shè)其幅值為均勻分布在［min，max］上，則根據(jù)概率論相關(guān)知識可知，其重建概率為式（10）：

由式（9）、式（10）可以看出，隨著原始信號長度N的縮短，重構(gòu)過程中窮舉的組合數(shù)量越少，其原始信號的重構(gòu)概率更高。假設(shè)將原始信號劃分為n段進行壓縮，第i段的長度為Ni，當每段數(shù)據(jù)中的非零元素數(shù)量為K時，則原始信號的重建概率為式（11）：

當每段數(shù)據(jù)中的非零元素數(shù)量未知時，則原始信號的重建概率為式（12）：

將上述四個公式進行比較，可以看出在同等條件下，分段壓縮后的重構(gòu)概率明顯高于分段前的重構(gòu)概率。而在分段條件下，式（11）的重構(gòu)概率高于式（12）。由此可以看出，可以通過對原始數(shù)據(jù)進行分段壓縮以提高數(shù)據(jù)的重構(gòu)概率，在綜合考慮到盲稀疏度及稀疏度已知兩種條件下的數(shù)據(jù)壓縮及重構(gòu)特點，提出了基于壓縮感知理論的數(shù)據(jù)分段壓縮算法。

2.2算法步驟

CS-TSSC算法包括兩個信號分段及信號數(shù)據(jù)壓縮過程。分段的目的有兩個，一是為了減少重構(gòu)算法窮舉數(shù)量，提高原始信號的重構(gòu)概率，二是能夠通過分段方法將具有盲稀疏性的信號轉(zhuǎn)化為稀疏度可知的信號，即將求解式（12）的問題轉(zhuǎn)化為求解式（11）的問題。數(shù)據(jù)壓縮過程則是應(yīng)用壓縮感知理論，對每段數(shù)據(jù)進行分段壓縮，實現(xiàn)對時序信號的高比率壓縮，以此減少網(wǎng)絡(luò)通信能耗。

算法步驟如下所述：①參數(shù)初始化。包括當前段中非零元素個數(shù)temp，當前分段數(shù)i、最大分段數(shù)量fmax及分段閾值n。②信號分段。從原始信號第一位起，記錄當前數(shù)據(jù)段中非零元素的個數(shù)temp，當temp=n時，將其劃分為下一數(shù)據(jù)段的起始數(shù)據(jù)。將當前段數(shù)i加1，n置為0。③若當前分段數(shù)seg大于等于最大分段數(shù)量fmax時，轉(zhuǎn)入步驟4；否則轉(zhuǎn)回步驟2。④壓縮過程。將分段后的原始信號X={x1，x2，…，xfmax}進行分段壓縮，以形成壓縮后信號Y={Y1，Y2，…，Yfmax}，其中：

Φi為每個分段信號對應(yīng)的觀測矩陣，從觀測矩陣字典中查找。由于節(jié)點本身的存儲空間及運算能力有限，筆者選擇了對存儲空間要求較小，運算復(fù)雜度較低的五種觀測矩陣，分別是Hadamard矩陣、稀疏隨機矩陣、Toeplitz矩陣、貝努利矩陣和高斯隨機矩陣。其中Hadamard矩陣、稀疏隨機矩陣和貝努利觀測矩陣無法保留原始信號的相應(yīng)特征，其數(shù)據(jù)重構(gòu)概率很低，無法滿足系統(tǒng)工作要求。Toeplitz觀測矩陣的數(shù)據(jù)恢復(fù)精度及數(shù)據(jù)恢復(fù)概率與高斯隨機矩陣相近，但在實驗過程中發(fā)現(xiàn)Toeplitz觀測矩陣通常會出現(xiàn)適應(yīng)度較差而恢復(fù)精度較好的情況，即性能不夠穩(wěn)定，相比之下優(yōu)先選用高斯隨機矩陣均衡性較好。

分段算法舉例說明：假設(shè)原始信號X為：0 0 0 1 1 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0，其原始信號長度為30，當n=2時，可劃分成六段數(shù)據(jù)：0 0 01 1 | 1 0 1 0 | 1 0 1 0 0 | 1 0 0 0 1 0 | 1 1 0 | 1 0 0 1 0 0 0

這種分段方法的特點是除第一段信號外，其余所有數(shù)據(jù)段的起始位均為非零元素，且無論原始信號的稀疏度是否可預(yù)測，其分段后的信號的稀疏度均為已知，因此信號的重構(gòu)概率大幅提高。表1列舉了信號分段前后非零元素位置的組合數(shù)量。

表1　分段前后非零元素位置組合數(shù)量

從表1的數(shù)據(jù)可以看出，在信號分段壓縮前，數(shù)據(jù)中非零元素的組合位置數(shù)量巨大，特別是在盲稀疏度的條件下，原始信號的組合數(shù)量可以達到10 的9次方之多，這也能夠解釋原始條件下信號重構(gòu)概率低、重構(gòu)精度差的原因。同時，從表1中也可以看出，分段壓縮后，原始信號的非零元素組合個數(shù)數(shù)量減少很多，其重構(gòu)概率大幅提高。

3　實驗結(jié)果分析

3.1實驗參數(shù)

實驗數(shù)據(jù)采集自秦始皇兵馬俑博物館K9901號石鎧甲展館旁。節(jié)點在其西南方向的樹林中呈5×5網(wǎng)狀排列，節(jié)點與通信基站直接通信組成星狀網(wǎng)絡(luò)。節(jié)點采集監(jiān)測現(xiàn)場的時序信號，在節(jié)點處運行CS-TSSC算法后，將數(shù)據(jù)傳輸至遠程終端服務(wù)器使用Q-CSDR算法進行數(shù)據(jù)重構(gòu)。在實驗中使用三個無線傳感器作為信號采集設(shè)備對監(jiān)測區(qū)域內(nèi)的微地震信號進行采集。采集到的信號在節(jié)點本地進行濾波、降噪等處理后，再通過分幀和壓縮后傳輸至遠端服務(wù)器。一個傳輸未壓縮信號，兩個傳輸壓縮信號。將三類數(shù)據(jù)導(dǎo)入計算機，通過MATLAB運行程序?qū)χ貥?gòu)的壓縮信號進行評估，同時監(jiān)測3個節(jié)點的工作時長。具體實驗參數(shù)見表2。

表2　實驗參數(shù)設(shè)置

3.2算法性能結(jié)果分析

從圖1可以看出，信號的恢復(fù)精度實際上受壓縮比和數(shù)據(jù)段內(nèi)非零元素個數(shù)n影響較大，而受數(shù)據(jù)段長度影響較小。實驗結(jié)果如圖1所示。圖中第一行為傳感器采集到的原始時序信號，第二行為經(jīng)壓縮感知分段壓縮算法壓縮后，由Q-CSDR算法逐段恢復(fù)并組合成的重構(gòu)信號，第三行為重構(gòu)誤差，為原始信號與重構(gòu)信號的差值。

當n=2時，原始數(shù)據(jù)共分22段數(shù)據(jù)，信號壓縮比為200∶51，近乎達到4∶1?？紤]通信中，每個數(shù)據(jù)包需要額外增加2字節(jié)各段數(shù)據(jù)原長度及稀疏度、總段數(shù)、段序列號信息，因此實際數(shù)據(jù)壓縮比率為190∶400=0.475。重建信號的均方誤差小于0.01。

如圖2所示，當n=3時，原始數(shù)據(jù)共分15段數(shù)據(jù)，信號壓縮比為200∶59，約為3∶1?？紤]通信中，每個數(shù)據(jù)包需要額外增加2字節(jié)各段數(shù)據(jù)原長度和稀疏度信息，因此實際數(shù)據(jù)包長度壓縮比率為178∶400=0.445。重建信號的均方誤差為0.02。

如圖3所示，當n=4時，原始數(shù)據(jù)共分12段數(shù)據(jù)，信號壓縮比為200∶66，約為3.3∶1?？紤]通信中，每個數(shù)據(jù)包需要額外增加2字節(jié)各段數(shù)據(jù)原長度和稀疏度信息，因此實際數(shù)據(jù)包長度壓縮比率為180∶400=0.45。重建信號的均方誤差為0.2。

由上述實驗結(jié)果可以看出，分段閾值n越大恢復(fù)精度越低。從傳輸角度來看n越大分段數(shù)越少，產(chǎn)生的通信開銷越少，但數(shù)據(jù)重構(gòu)概率及精度越差，n越小則重構(gòu)概率越高、恢復(fù)精度越高。

圖1　n=2時的數(shù)據(jù)重構(gòu)結(jié)果

圖2　n=3時的數(shù)據(jù)重構(gòu)結(jié)果

圖3　n=4時的數(shù)據(jù)重構(gòu)結(jié)果

3.3不同稀疏度條件下實驗結(jié)果分析

筆者針對實驗過程中采集的25組長度為200的數(shù)據(jù)進行壓縮和重建，實驗結(jié)果如圖4所示［13］：

可以看出，數(shù)據(jù)恢復(fù)精度在不同稀疏度條件下都比較精確，性能穩(wěn)定；高稀疏度條件下的精度也較高，但是通信開銷和數(shù)據(jù)壓縮比增加了。n=2時的數(shù)據(jù)恢復(fù)精度最好，其壓縮比和n=3和n=4時相差不多，其通信開銷則高于后兩種分幀方式。此外，算法對稀疏度接近45的原始信號仍保持較高的重構(gòu)概率，減少了估計信號的非零元素排列可能帶來的影響。

3.4無線傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮算法對比

將CS-TSSC與分段線性化壓縮的改進算法IS?DT的數(shù)據(jù)恢復(fù)性能進行對比。SDT算法是一種直線趨勢化壓縮算法，算法對于給定的數(shù)據(jù)限定一個門限值E，并找出最長的直線趨勢，通過一條由起點和終點去頂?shù)闹本€來代替采集的一系列連續(xù)數(shù)據(jù)點。SDT算法現(xiàn)在起點數(shù)據(jù)垂直距離為門限值E的地方設(shè)置兩個“支點”。支點與后續(xù)的數(shù)據(jù)之間的連線稱為“門”。算法初始化時兩扇門均是關(guān)閉的。隨著更多的數(shù)據(jù)被采集進入數(shù)據(jù)序列，這兩扇門將根據(jù)實際情況進行打開或靜止操作，門的寬度是不固定的，且門一旦打開就不能關(guān)閉。當這兩扇門達到平行時，當前壓縮區(qū)間結(jié)束。將當前數(shù)據(jù)點的前一個點作為壓縮區(qū)間的重點，并開始新的一輪壓縮。SDT算法性能僅受門限值E影響，而門限值E的選取依賴于經(jīng)驗和實驗嘗試，且門限值一旦確定后在整個壓縮過程中不能改變，因此在信號數(shù)據(jù)劇烈波動的條件下壓縮效果并不理想。ISDT算法針對SDT算法的缺點進行了改進。ISDT算法能夠根據(jù)數(shù)據(jù)的波動情況實時、自適應(yīng)、連續(xù)的在一個區(qū)間內(nèi)調(diào)整其大小，使算法在壓縮過程中始終保持一種較好的壓縮狀態(tài)。ISDT算法根據(jù)某個數(shù)據(jù)點與其前后兩個數(shù)據(jù)點的差值之比作為判斷數(shù)據(jù)波動的依據(jù)，不斷根據(jù)公式對門限值E進行更新。

從上述描述可以看出，ISDT算法雖然壓縮性能較好，但是其壓縮過程是與數(shù)據(jù)采集過程緊密關(guān)系的，算法不僅要對門限值進行計算，還需要對門限值調(diào)整進行計算。這兩種算法對于數(shù)據(jù)幅度波動較小的條件下壓縮效果較好，但在數(shù)據(jù)波動劇烈的條件下數(shù)據(jù)的壓縮效果并不好，且由于門限值需要實時更新的緣故，其計算代價反而會增加。具體對比實驗結(jié)果如圖5所示。

圖4　不同稀疏度條件下的試驗結(jié)果

圖5　算法性能比較

可以看出，CS-TSSC算法的性能優(yōu)于對比算法算法，在各種壓縮比率條件下均能保持較為穩(wěn)定的均方誤差值，這是因為使用算法后信號重構(gòu)概率被提高的原因。n=3及n=4時算法在壓縮比率大于0.8的條件下性能反而不如ISDT算法。這是由于數(shù)據(jù)重構(gòu)算法特性影響的，量子克隆免疫算法在尋優(yōu)過程中容易陷入局部最優(yōu)解的原因。同時當壓縮比率小于0.2時，CS-TSSC算法的性能也會急劇下降，這主要是因為在數(shù)據(jù)壓縮過程中數(shù)據(jù)原始信息丟失過多造成的?？傮w來看，壓縮比率在0.2~0.8之間時，CS-TSSC的性能優(yōu)于其他兩類算法。

通過算法敘述及分段方式描述可以看出，分段壓縮算法僅針對時間序列信號有較好的效果，而對于圖像信號重構(gòu)則效果很差，其原因是因為圖像信號數(shù)據(jù)量大，分段過多會影響到算法運算速度，降低算法實用性、導(dǎo)致重構(gòu)算法性急劇降低。因此CSTSSC算法的缺點在于僅能適用于二維序列信號。

4　結(jié)論

將壓縮感知理論應(yīng)用于無線傳感器網(wǎng)絡(luò)應(yīng)用以降低網(wǎng)絡(luò)及節(jié)點通信能耗，延長網(wǎng)絡(luò)壽命。在分析了壓縮感知數(shù)據(jù)重構(gòu)原理的基礎(chǔ)上，提出了基于壓縮感知理論的時序信號分段壓縮算法CS-TSSC。該算法能夠克服壓縮感知理論在數(shù)據(jù)盲稀疏度及高稀疏度條件下重構(gòu)精度不高的問題，明顯提高了數(shù)據(jù)重構(gòu)概率。實驗結(jié)果表明，相對于現(xiàn)有的經(jīng)典壓縮算法，基于壓縮感知理論的數(shù)據(jù)壓縮方法具有計算復(fù)雜度低、計算代價小，壓縮比率高等特點。但是算法的缺點在于目前僅適用于二維序列信號，因此一些針對數(shù)據(jù)量大情況下的問題還需要進一步深入研究。

參考文獻：

［1］Rein S，Reisslein M. Performance Evaluation of the Fractional Wavelet Filter：A Low-Memory Image Wavelet Transform for Mul?timedia Sensor Networks［J］. IEEE Communications Survey & Tu?torials，2010，13（2）：291-306.

［2］Luo W H，Wang J L. Based on Hear Wavelet Adaptive Data Com?pression Method［J］. Computer Engineering，2010，36（16）：74-76.

［3］Bristol E H. Swinging Door Trending：Adaptive Trending Record?ing［C］//National Conference Proceeding. Sydney：ISA 1990：749-753.

［4］王舉，房鼎益，陳曉江，等.文物監(jiān)測中無線傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮算法［J］.西安電子科技大學(xué)學(xué)報（自然科學(xué)版），2012，39 （1）：157-162.

［5］葉新榮，朱衛(wèi)平，張愛清，等. OFDM系統(tǒng)選擇性慢衰落信道的壓縮感知估計［J］.電子與信息學(xué)報，2015，37（1）：169-174.

［6］鄭仕鏈，楊小牛.用于調(diào)制寬帶轉(zhuǎn)換器壓縮頻譜感知的重構(gòu)失敗判定方法［J］.電子與信息學(xué)報，2015，37（1）：236-240.

［7］劉洲洲，王福豹.基于離散螢火蟲壓縮感知重構(gòu)的無線傳感器網(wǎng)絡(luò)多目標定位［J］.光學(xué)精密工程，2014，22（7）：1904-1911.

［8］Figueiredo M，Nowak R，and Wright S. Gradient Projection for Sparse Reconstruction：Application to Compressed Sensing and Other Inverse Problems［J］. IEEE Journal of Selected Topics in Signal Processing，2007，1（4）：586-597.

［9］軒春青，軒志偉，陳保立.基于最小二乘與粒子群算法的壓力傳感器動態(tài)補償方法［J］.傳感技術(shù)學(xué)報，2014，27（10）：1363-1367.

［10］高偉，趙博，周廣濤.基于帶約束人工蜂群算法和平均Haus?dorff距離的重力匹配方法［J］.傳感技術(shù)學(xué)報，2014，27（1）：74-78.

［11］Needell D，Tropp J A. CoSaMP：Iterative Signal Recovery from In?complete and Inaccurate Samples［J］. ACM Technical Report 2008-01，California Institute of Technology，Pasadena，2008（7）：93-100.

［12］王娟，李飛.一種基于實數(shù)編碼的量子克隆免疫算法［J］.計算機工程，2012，38（18）：133-136.

［13］祁浩，劉洲洲.基于量子免疫克隆的壓縮感知數(shù)據(jù)重構(gòu)算法［J］.微處理機，2014，35（5）：34-39.

劉洲洲（1981-），男，山西運城人，博士研究生，講師，2004、2007年于西北工業(yè)大學(xué)獲得學(xué)士、碩士學(xué)位，主要從事無線傳感器網(wǎng)絡(luò)方面的研究，liuzhou?zhou8192@126.com。

Multidimensional Scaling Localization Algorithm Based on the Shortest Path Matrix Correction

REN Keqiang*，ZHUANG Fangwang
（School of Information Engineering，Jiangxi University of Science and Technology，Ganzhou Jiangxi 341000，China）

Abstract：In order to reduce the difference between the shortest path distance matrix and Euclidean distance ma?trix，an improved algorithm of multidimensional scaling node localization was proposed to enhance the node localiza?tion accuracy of MDS-MAP（C）algorithm. The algorithm made some improvements on MDS-MAP（C）algorithm. The shortest path distance matrix was corrected by using heuristic search strategy，so as to reduce the error between the shortest path distance matrix and the actual Euclidean distance matrix. Then smacof algorithm iterative error func?tion instead of singular value decomposition（SVD）was utilized to solve the problem of node localization，which could optimize and improve the solving process of node localization. The experimental results show that compared with MDS-MAP（C）algorithm，the improved algorithm can reduce the error of the shortest path distance，effectively improve the node localization accuracy，and it has better adaptability to the irregular network.

Key words：wireless sensor network；the shortest path；MDS-MAP（C）algorithm；node localization；multidimension?al scaling；smacof algorithm

doi：EEACC：6150P10.3969/j.issn.1004-1699.2016.01.022

收稿日期：2015-03-30修改日期：2015-10-21

中圖分類號：TP393

文獻標識碼：A

文章編號：1004-1699（2016）01-0122-07

項目來源：國家自然科學(xué)基金項目（61103242，61401499）