【導(dǎo)讀】數(shù)據(jù)壓縮技術(shù)是提高無線數(shù)據(jù)傳輸速度的有效措施之一。近年來出現(xiàn)的壓縮感知理論則不受制于奈奎斯

　　

【正文】 代價(jià)達(dá)到了更加快速重構(gòu)的目的。 （ MP）和正交匹配追蹤（ OMP）算法來求解優(yōu)化問題重構(gòu)信號(hào)，大大提高了計(jì)算的速度，且易于實(shí)現(xiàn)。樹形匹配追蹤（ TMP）算法是 2020年 Chinh La 和 Minh 。該方法針對(duì) BP、 MP和 OMP方法沒有考慮信號(hào)的多尺度分解時(shí)稀疏信號(hào)在各子帶位置的關(guān)系，將稀疏系數(shù)的樹型結(jié)構(gòu)加以利用，進(jìn)一步提升了重構(gòu)信號(hào)的精度和求解的速 度。匹配追蹤類算法都是基于貪婪迭代算法，以多于 BP算法需要的采樣數(shù)目換取計(jì)算復(fù)雜度的降低。例如 OMP算法，需要 cKM?，)ln(2 Nc?個(gè)采樣點(diǎn)數(shù)才能以較高的概率恢復(fù)信號(hào)，信號(hào)重構(gòu)的計(jì)算復(fù) 雜度為)( 2NKO。 2020年 Donoho等人提出了分段正交匹配追蹤（ StOMP， stagewise OMP）算法。它將 OMP進(jìn)行一定程度的簡化，以逼近精度為代價(jià)進(jìn)一步提高了計(jì)算速度（計(jì)算復(fù)雜度為 O(N)），更加適合于求解大規(guī)模問題。 E. Hale， W. Yin基于分裂算子和同倫算子提出了求解最小 1范數(shù)大規(guī)模問題的方法，適合于糾錯(cuò)編碼、磁共振成像、 NMR波譜研究等領(lǐng)域的大規(guī)模問題求解。 在上述各種方法中，觀測矩陣中的所有值都非零，這樣信號(hào)采樣過程的計(jì)算量是O(MN)，在大規(guī)模的數(shù)據(jù)面前，這個(gè)量級(jí)還是非常大的。因此一類利用稀疏矩陣作為觀測矩陣進(jìn)行采樣的方法出現(xiàn)了。 Graham Cormode等人，提出利用分組測試和隨機(jī)子集選取來估計(jì)稀疏信號(hào)的非零系數(shù)的位置和取值，該方法需要的采樣數(shù)為 )log(2NKOM?，信號(hào)重構(gòu)的計(jì)算復(fù)雜度為)log( 2NKO，得到重構(gòu)信號(hào)的速度更快。 Gilbert等人在 2020 年 4 月提出了鏈?zhǔn)阶粉櫍?CP， Chaining Pursuit）方法來恢復(fù)可壓 縮信號(hào)。利用)log( 2NKO個(gè)采樣觀測重構(gòu)信號(hào)，需要計(jì)算量為 )loglog(22 KNKO，該方法對(duì)特別稀疏信號(hào)的恢復(fù)計(jì)算性能較高，但當(dāng)信號(hào)的稀疏度減少，需要的采樣點(diǎn)數(shù)會(huì)迅速增加，甚至超過信號(hào)本身的長度，這就失去了壓縮采樣的意義。 總之，目前為止出現(xiàn)的重構(gòu)算法都可歸入以下三大類： （ 1）貪婪追蹤算法：這類方法是通過每次迭代時(shí)選擇一個(gè)局部最優(yōu)解來逐步逼近原始信號(hào)。這些算法包括 MP算法， OMP算法，分段 OMP算法（ StOMP）和正則化 OMP（ ROMP）算法。 （ 2）凸松弛法：這類方法通過將非凸問題轉(zhuǎn)化為凸問題求解找到信號(hào)的逼近， 如 BP算法，內(nèi)點(diǎn)法，梯 度投影方法和迭代閾值法。 （ 3）組合算法：這類方法要求信號(hào)的采樣支持通過分組測試快速重建，如傅 立葉采樣，鏈?zhǔn)阶粉櫤?HHS追蹤等。 總之，每種算法都有其固有的缺點(diǎn)。凸松弛法重構(gòu)信號(hào)所需的觀測次數(shù)最少， 但往往計(jì)算負(fù)擔(dān)很重。貪婪追蹤算法在運(yùn)行時(shí)間和采樣效率上都位于另兩種算法 之間。 由上面的分析可知，重構(gòu)算法和所需的觀測次數(shù)密切相關(guān)，當(dāng)前，壓縮感知 理論的信號(hào)重構(gòu)問題的研究主要集中在如何構(gòu)造穩(wěn)定的、計(jì)算復(fù)雜度較低的、對(duì) 觀測數(shù)量要求較少的重構(gòu)算法來精確地恢復(fù)原信號(hào)。 壓縮感知優(yōu)勢及不足 相對(duì)于傳統(tǒng)的 信息處理方式，壓縮感知理論毫無疑問是具有優(yōu)勢的，這體現(xiàn)在以 下幾個(gè)方面： （ 1）采集數(shù)據(jù)的時(shí)候只需要采集一部分?jǐn)?shù)據(jù)（包含了原信號(hào)的全局信息），一開始就可以傳輸長度較短的信號(hào)。這樣做的好處就是將信號(hào)壓縮這一端的過程簡單化，而將復(fù)雜的部分交給數(shù)據(jù)還原的這一端來做。這種優(yōu)勢在醫(yī)學(xué)圖像領(lǐng)域體現(xiàn)的愈為明顯，因?yàn)椴杉瘮?shù)據(jù)的過程往往是對(duì)病人帶來很大麻煩甚至身體傷害的過程。以 X 光斷層掃描為例，眾所周知 ， X 光輻射會(huì)對(duì)病人造成身體損害，而壓縮感知的特點(diǎn)使得我們可以用比經(jīng)典少得多的輻射劑量來進(jìn)行數(shù)據(jù)采集，這在醫(yī)學(xué)上的意義 是不言而喻的。 （ 2）由于直接感知壓縮后的數(shù)據(jù)，所以不受奈奎斯特采樣定律的局限，降低了對(duì)采樣系統(tǒng)硬件設(shè)備的要求，這對(duì)于寬帶信號(hào)非常實(shí)用。 （ 3）具有抗干擾能力。由于感知到的測量值中的任何一項(xiàng)都是重要的，或者說不重要的， 所以如果測量值丟失了其中的某幾項(xiàng)，仍然可以完美重構(gòu)信號(hào)。 當(dāng)然，目前的壓縮感知理論還不是特別完善， 尚存在一些問題需要研究，在這里將列出其中幾個(gè)問題： （ 1）實(shí)際應(yīng)用領(lǐng)域中，測量到的數(shù)據(jù)可能無法包含信號(hào)的全局信息，例如最傳統(tǒng)的攝像問題，每個(gè)感光器件所感知到的只是一小塊圖像而不是什么全 局信息。 （ 2）感知到的測量值的長度一般是重要分量長度的 4倍，才能近乎完美地重構(gòu)。 （ 3）重構(gòu)算法是 NP 問題。即使將 0范數(shù)轉(zhuǎn)化為 1 范數(shù)，由于不可微性（ indifferentiable），算法的計(jì)算復(fù)雜度仍然很高。而且，目前的重構(gòu)算法對(duì)含噪信號(hào)或者采樣過程中引入噪聲的信號(hào)重構(gòu)效果不夠理想。 （ 4）壓縮感知理論是采用非自適應(yīng)線性投影來保持信號(hào)的原始結(jié)構(gòu)，不夠靈活，需要研究自適應(yīng)傳感技術(shù)，根據(jù)不同的信號(hào)類型采用不同的數(shù)據(jù)采樣和重構(gòu)策略。 壓縮感知在傳感網(wǎng)中的觀測方式 之前已經(jīng)提及將壓縮感知運(yùn) 用到傳感網(wǎng)中，即在節(jié)點(diǎn)處得到觀測值數(shù)據(jù)并傳給sink節(jié)點(diǎn)（或者融合中心）。現(xiàn)在將分別講述壓縮感知在傳感網(wǎng)中的兩種觀測方式。 （ 1） 第一種：模擬通信方式 模擬通信，即傳輸?shù)臏y量值是模擬數(shù)據(jù)，具體步驟如下（假設(shè)有個(gè)傳感節(jié)點(diǎn)）： 1)對(duì)于個(gè)節(jié)點(diǎn)而言，每一個(gè)節(jié)點(diǎn)都要利用其節(jié)點(diǎn)網(wǎng)絡(luò)地址（或者編號(hào)）作為產(chǎn)生偽隨機(jī)的種子（ seed），得到隨機(jī)投影矢量 }{1,kijiA ?的個(gè) K元素。 sink節(jié)點(diǎn)在知道種子和節(jié)點(diǎn)在網(wǎng)絡(luò)中的地址后，也能夠很容易的為每個(gè)傳感節(jié)點(diǎn) j(j=1,...,n)重建出隨即矢量 }{ 1, kijiA ? 2)）編號(hào)為 j的傳感節(jié)點(diǎn)將所感知數(shù)據(jù) jx 與 , }{1,kijiA ?相乘得到個(gè)元組 （式 ） 所有的節(jié)點(diǎn)在 k個(gè)時(shí)隙內(nèi)（次傳輸）連貫的將相應(yīng)的 jV 以模擬方式傳至融合 中心。由于無線電波的累加性質(zhì)，在 k次傳輸后 sink節(jié)點(diǎn)最終得到的接收信號(hào)為 ?? ????nj j Axvy 1 ?? （式 ） 其中ω為通信過程中產(chǎn)生的噪聲。 以上步驟是以完全分散的形式將感知數(shù)據(jù)的 k個(gè)隨機(jī)投影在 k次傳輸中傳給 sink節(jié)點(diǎn)。 （ 2） 第二種：數(shù)字通信方式 數(shù)字通信方式，即傳輸?shù)臏y量值是量化后的值。這種方式可以達(dá)到同樣的目的。假設(shè)節(jié)點(diǎn)能夠進(jìn)行本地通信，并能建立一條路由，從而與某個(gè)確定的簇頭節(jié)點(diǎn)之間形成生成樹。具體步驟如下： 1）首先傳感 節(jié)點(diǎn)能夠計(jì)算測量值 kijjiji XAV 1, }{ ?? ； 2）然后這些測量值可以經(jīng)過聚合在簇頭節(jié)點(diǎn)得到所有測量值 V=Ax，然后對(duì)這些值進(jìn)行編碼傳至 sink節(jié)點(diǎn)。 這兩種方法主要的不同就在于第一種方式不需要復(fù)雜的路由信息。但考慮到數(shù)字通信的抗噪聲能力強(qiáng)，遠(yuǎn)距離傳輸能保證信號(hào)質(zhì)量，在本文中將選取第二種方式。 第 3 章 壓縮感知理論應(yīng)用概述 壓縮傳感理論帶來了傳統(tǒng)信號(hào)采樣理論的變革，而且具有很廣闊的應(yīng)用前景和場合。現(xiàn)有的應(yīng)用主要包括壓縮感知成像、模擬 信息的轉(zhuǎn)換、生物傳感等方面。 壓縮成像 運(yùn)用壓縮感知原理，美國 RICE大學(xué)已經(jīng)成功研制了“單像素”壓縮數(shù)碼照相機(jī)，設(shè)計(jì)的原理是首先通過光路系統(tǒng)將成像目標(biāo)投影到一個(gè)數(shù)字微鏡器件上，然后其反射光由透鏡聚焦到單個(gè)光敏二極管上，光敏二極管兩端的電壓值即為一個(gè)測量值 y，將此投影操作重復(fù) M次，得到測量向量 y，然后用最小全變分算法構(gòu)建的數(shù)字信號(hào)處理器重構(gòu)原始圖像 f。數(shù)字微鏡器件由數(shù)字電壓信號(hào)控制微鏡片的機(jī)械運(yùn)動(dòng)以實(shí)現(xiàn)對(duì)入射光線的調(diào)整，相當(dāng)于隨機(jī)觀測矩陣 Φ。由于該相機(jī)直接獲取的是 M次隨機(jī)線性測量值，而不是獲取原始信 號(hào)的 N (M N)個(gè)像素值，為低像素相機(jī)拍攝高質(zhì)量的圖像提供了可能。而且壓縮感知技術(shù)也可以應(yīng)用于雷達(dá)成像領(lǐng)域，與傳統(tǒng)雷達(dá)成像技術(shù)相比，壓縮感知雷達(dá)成像主要實(shí)現(xiàn)了兩個(gè)重要改進(jìn)：在接收端省去了脈沖壓縮匹配濾波器；同時(shí)因?yàn)楸荛_了對(duì)原始信號(hào)的直接采樣，降低了接收端對(duì)模數(shù)轉(zhuǎn)換器件帶寬的要求。設(shè)計(jì)的重點(diǎn)由傳統(tǒng)的設(shè)計(jì)昂貴的接收端硬件轉(zhuǎn)化成為設(shè)計(jì)新穎可靠的信號(hào)恢復(fù)算法，從而簡化了雷達(dá)成像系統(tǒng)。 Bhattacharya等人將壓縮感知理論應(yīng)用到合成孔徑雷達(dá)圖像數(shù)據(jù)獲取上，從而解決了海量數(shù)據(jù)的采集和存儲(chǔ)問題，顯著降低了衛(wèi)星 圖像處理的計(jì)算代價(jià)。另外，壓縮傳感技術(shù)也可以應(yīng)用于醫(yī)學(xué)成像領(lǐng)域，如稀疏核磁共振成像、壓縮感知三維磁共振波譜成像等等。 模擬信息轉(zhuǎn)換 對(duì)于帶寬非常高的信號(hào)，比如雷達(dá)和通信信號(hào)處理系統(tǒng)涉及的射頻信號(hào)，根據(jù)奈奎斯特定理，要獲得完整的信號(hào)信息，所采用的模數(shù)轉(zhuǎn)換器必須具有很高的采樣頻率。然而由于傳感器及轉(zhuǎn)換硬件性能的限制，獲得的信號(hào)的帶寬要遠(yuǎn)遠(yuǎn)低于實(shí)際信號(hào)的帶寬，存在較大的信息的丟失。對(duì)此 Kriolos等人設(shè)計(jì)了基于壓縮感知理論的模擬 /信息轉(zhuǎn)換器，利用壓縮感知理論中測量信息可以得到完整信號(hào)的原理。首先獲得原始 信號(hào)的線性測量，再利用后端數(shù)字信號(hào)處理器重構(gòu)原始信號(hào)或者直接計(jì)算原始信號(hào)的統(tǒng)計(jì) 數(shù)據(jù)等信息。 Laska等人進(jìn)一步發(fā)展了基于隨機(jī)采樣系統(tǒng)的模擬 /信息轉(zhuǎn)換器，并給出了隨機(jī)抽樣系統(tǒng)的兩種實(shí)現(xiàn)模型：第一種模型采用多個(gè)并行低采樣率的模數(shù)轉(zhuǎn)換器，每個(gè)模數(shù)轉(zhuǎn)換器之間有等間隔的位移，通過隨機(jī)控制來自不同的模數(shù)轉(zhuǎn)換器的采樣，實(shí)現(xiàn)隨機(jī)采樣。然而這種方法卻需要多個(gè)模數(shù)轉(zhuǎn)換芯片，每個(gè)芯片利用率不太高。第二種模型采用一組電容和數(shù)字控制換向器隨機(jī)采樣，該系統(tǒng)只需要一個(gè)模數(shù)轉(zhuǎn)換芯片即可。 生物傳感 生物傳感中的傳統(tǒng) DNA芯片能平行 測量多個(gè)有機(jī)體，但是只能識(shí)別有限種類的有機(jī)體， Sheikh等人運(yùn)用壓縮感知和群組檢測原理設(shè)計(jì)的壓縮感知 DNA芯片克服了這個(gè)缺點(diǎn)，壓縮感知 DNA芯片中的每個(gè)探測點(diǎn)都能識(shí)別一組目標(biāo)，從而明顯減少了所需探測點(diǎn)數(shù)量。此外，基于生物體基因序列稀疏特性， Sheikh等驗(yàn)證了可以通過置信傳播的方法實(shí)現(xiàn)壓縮感知 DNA芯片中的信號(hào)重構(gòu)。 除此之外，壓縮感知理論還被應(yīng)用于信號(hào)的檢測分類、數(shù)據(jù)的通信、無線傳感器網(wǎng)絡(luò)應(yīng)用和地球物理數(shù)據(jù)的分析等眾多的領(lǐng)域。 本章小結(jié) 本章詳細(xì)描述了壓縮感知理論基本框架。壓縮感知理論是一個(gè)非常 簡單有效的信號(hào)采集協(xié)議，它以較低采樣速率和獨(dú)立于信號(hào)的采樣方式采樣信號(hào)，然后又用強(qiáng)大的計(jì)算能力從看上去不完整的觀測集合中重構(gòu)原信號(hào)。對(duì)壓縮感知理論實(shí)現(xiàn)的兩個(gè)前提要求 ——信號(hào)稀疏性及觀測矩陣和稀疏表示基之間滿足不相干性進(jìn)行了詳細(xì)的論述，著重介紹了信號(hào)稀疏變換、觀測矩陣設(shè)計(jì)和重構(gòu)算法三個(gè)方面的最新研究進(jìn)展情況。 壓縮感知理論是近幾年剛剛興起的理論，但卻展現(xiàn)了強(qiáng)大的生命力引起了廣泛的關(guān)注，下面我們將對(duì)該理論的歷史和發(fā)展歷程做出介紹。 第 4章 CS 在無線傳感網(wǎng)中的應(yīng)用 前文我們已經(jīng)對(duì)壓縮感知（ CS）理論做了叫詳細(xì)的介紹，下面我將介紹將壓縮感知應(yīng)用于無線傳感的優(yōu)勢以及采用 OMP 算法，實(shí)現(xiàn)對(duì)一維信號(hào)和二維信號(hào)圖像的CS 重構(gòu)。 研究背景 前面緒論中已經(jīng)提到無線傳感網(wǎng)中的一些感知數(shù)據(jù)具有時(shí)間相關(guān)性和空間相關(guān)性，利用這種數(shù)據(jù)特點(diǎn)，人們可以對(duì)感知數(shù)據(jù)進(jìn)行了壓縮處理。下面將介紹已有的基于相關(guān)性的數(shù)據(jù)壓縮技術(shù)，并闡明利用 CS 壓縮數(shù)據(jù)的優(yōu)勢。 基于感知數(shù)據(jù)相關(guān)性的壓縮 利用傳感數(shù)據(jù)間的時(shí)間相關(guān)性，文獻(xiàn) [13]提出了節(jié)省一個(gè)傳感器節(jié)點(diǎn)內(nèi)存和計(jì)算資源的無損壓縮算法。利用傳感數(shù)據(jù)間（相鄰傳感器節(jié)點(diǎn) 在同一時(shí)刻所采集的數(shù)據(jù)之間）的空間相關(guān)性，文獻(xiàn) [17]提出了在多層架構(gòu)中，運(yùn)用多重主成分分析法（ Multiple Principal Component Analysis, MPCA）去除了普通節(jié)點(diǎn)間的數(shù)據(jù)相關(guān)性以及相鄰簇頭節(jié)點(diǎn)主成分之間的相關(guān)性，而文獻(xiàn) [26]則將近年提出壓縮感知算法運(yùn)用到基于分簇的傳感網(wǎng)數(shù)據(jù)壓縮中，降低了傳輸能耗。文獻(xiàn) [33]在時(shí)域和空間域提出了多分辨率和查詢（ Multiresolution Compression and Query, MCQ）架構(gòu)，用離散余弦變換和差分編碼技術(shù)來降低數(shù) 據(jù)冗余度，延長網(wǎng)絡(luò)壽命。但是這些算法并沒有綜合考慮時(shí)間相關(guān)性和空間相關(guān)性，文獻(xiàn) [46]將融合了這兩種相關(guān)性的分布式信源編碼運(yùn)用到傳感網(wǎng)的數(shù)據(jù)壓縮中。在一些分布式編碼算法中，需要進(jìn)行傳感器節(jié)點(diǎn)間的信息交換，傳輸這些信息需要消耗能量，因此，文獻(xiàn) [13,22]提出了基于聯(lián)合稀疏模型的分布式壓縮感知算法，既采用了兩種相關(guān)性，又不需要傳感器節(jié)點(diǎn)之間交換信息，而且能夠大大降低所需要傳輸?shù)臏y量值的數(shù)目，在此基礎(chǔ)上，文獻(xiàn) [21]還利用貝爾實(shí)驗(yàn)室所采集的實(shí)際數(shù)據(jù)進(jìn)行了仿真驗(yàn)證。另外文獻(xiàn) [26]在分布式架構(gòu)的基礎(chǔ)上利用小波提升 算法來壓縮數(shù)據(jù)，而文獻(xiàn) [23]則優(yōu)化了簇內(nèi)信息的交換，此外，文獻(xiàn) [25]也都各自闡述了相應(yīng)的數(shù)據(jù)壓縮技術(shù)。 傳統(tǒng)壓縮重構(gòu)方法 信號(hào)壓縮一般是通過改變信號(hào)的表示方式來實(shí)現(xiàn)的，所以壓縮和編碼也是分不開的。信號(hào)壓縮的分類方法根據(jù)不同的原理大致可以分為兩種。首先根據(jù)編碼的原理和處理的空間域的不同可以將圖像壓縮方法分為在空間域和變換域編碼表示這兩大類。 （ 1）空間域處理方法 空間域處理方法是指直接在圖像所在的空間對(duì)圖