物聯網中壓縮感知算法的云加速方法

張永平，張功萱，朱昭萌

(南京理工大學計算機科學與工程學院 南京 210094)

物聯網(Internet of things，IoT)是物物相連的網絡[1]，它通常配置了為數眾多的數據采集設備，這些設備時刻都在產生著大量的采集數據。海量采集數據的存在嚴重影響了物聯網的性能，研究“邊采樣邊壓縮”的采樣方法已成為物聯網應用的一個重要前提。壓縮感知(compressed sensing，CS)[2]就是一種將數據采集和壓縮同時完成的新型采樣方法，可以在對信號采樣的同時丟棄冗余信息，從而降低采集的數據量。

在壓縮感知理論中，信號的重構是通過求解數值優化問題實現的，算法計算復雜度很高。如利用著名的壓縮感知算法——BP(basis pursuit)算法重構信號時，當原始信號的長度為8 192時，重構操作的計算規模相當于求解一個8 192′262 144的線性規劃問題[3]。算法的高計算復雜度會對其應用帶來較為不利的影響，快速壓縮感知方法的研究一直都是該領域的一個熱點。

在物聯網數據采集和處理中引入壓縮感知方法，會減少采集的數據量、降低通信負擔，但同時也會帶來計算量的增加，這對物聯網來說是非常不利的(特別是對實時性要求較高的物聯網)。為了加速壓縮感知算法，在物聯網環境中，云計算技術[4]是一個很好的選擇。云可以方便地利用網絡中已有的計算資源來加速算法，這對物聯網(特別是私有物聯網)有著巨大的吸引力。此外，多核CPU/多CPU[5]和GPGPU(general purpose GPU)[6]并行計算也是很有效的加速方法，物聯網中常存在一些這樣的高性能計算設備。綜上所述，研究以云計算技術為基礎，綜合使用多種加速方法，充分利用物聯網中各種計算資源加速壓縮感知算法非常有意義。

1 壓縮感知理論

壓縮感知[7-8]方法可以在某些基框架下用遠少于Nyquist定理規定的測量值表示稀疏的或可壓縮的信號，并在需要時能夠從這些較少的測量值中重構原始信號。

一般地，根據稀疏表示理論，可假設信號sn′1(為了說明的簡便，假設信號是一維的)有某個稀疏表示θ(θ是可壓縮的)：

式中，Ψn×n是s的稀疏變換基。然后利用觀測矩陣Φm×n(mn)對系數θ進行壓縮：

這里的Φ是特別設計的，它必須與Ψ線性無關；原始信號s與觀測數據y之間的壓縮比為n:m。

獲得s的優化近似解?，式(3)是一個凸優化問題，可以利用優化方法來求解。

2 云加速方案

優化算法的計算復雜度一般都很高，通常壓縮感知方法中的信號的重構時間很長。本節研究利用云技術加速壓縮感知算法的設計方案。

2.1 方案設計

云計算技術可以通過網絡為用戶分配計算資源、提供按需服務，以達到用戶滿意的加速效果。OpenStack是一個流行的云服務框架，易于實現并具有良好的可擴展性，可以部署、運行于標準的硬件平臺。壓縮感知算法的云加速方案就是基于OpenStack架構的，它可以利用云平臺為用戶提供適量的計算資源加速Python語言[9]編寫的算法。云加速方案之所以面向Python語言，一是因為Python語言功能足夠強大，二是因為OpenStack本身是用Python語言開發的。

在云加速方案中，采集的數據通常以壓縮的形式存在。當用戶要求重構信號時，計算復雜度不高的一般代碼將在本地執行，而計算復雜度較高的重構算法將被自動遷移到云端；在云端，云平臺根據用戶的要求(如需要計算資源數量、算法運行時間的限制等)提供適量的計算資源，以實現算法的加速服務，并返回最終結果。計算的結果可以是重構的原始信號，也可以是根據重構的信號獲得的一些結論。

云加速方案需要解決兩個問題：代碼的遷移及并行化處理。將計算復雜度較高的代碼遷移到云端可以利用云環境中豐富的計算資源，而并行處理是云計算的前提。

2.2 算法遷移

云加速設計方案的算法遷移是基于函數的，它定義了一個“#remote”的標簽，如果某個函數被該標簽標記，則該函數將被自動遷移到云端執行。如下面代碼中的M ig函數。

一般地，函數的遷移有兩種實現方法：1) 將函數全部打包并發送；2) 將函數對象和變量序列化后打包并發送。第一種方法易于實現，但會發送很多冗余信息，增加數據傳輸負擔，這與引入壓縮感知方法的目的相背。第二種方法傳輸的數據量較少，但實現復雜，需要充分了解編程語言特性。云加速方案采用第二種方法來實現函數遷移，通過重寫用于序列化和反序列化的dumps和loads函數，實現了對Python語言編寫的函數遷移，比現有的序列化方法功能更加強大。

2.3 循環的并行化

如果一個循環可以并行處理[10]，就可以使多個操作同時向前推進，從而加快執行速度，但并非所有的循環都可以并行化。在云加速方案中定義了標簽“#parallelize”，只有被這個標簽標記的循環才會并行處理，如以下的for-循環將被并行化：

Python語言中，list模式提供了方便的創建列表的方法，而列表很容易實現并行化。云加速方案的并行化思想就是把循環語句轉化為list模式，通過設計的專門轉換接口，可以自動轉換標記了“#parallelize”標簽的循環語句。

在Python語言中，內嵌函數map常用來構造迭代，但其不適合于并行化，將其重寫為pmap函數。在pmap函數中定義了一個繼承list模式的新類，它使程序在迭代時不必等待本次迭代全部結束就可以繼續后面的迭代運算，從而實現并行化。

云加速方案是使用Python語言實現的，對Python語言實現的算法，只需要增加一些接口和標簽，就能自動并行化指定的循環并將標記的函數遷移到云端進行處理。

3 驗證算法及修改

3.1 選擇驗證算法

在壓縮感知理論中，信號重構通過求解數值優化問題實現。根據重構時所使用優化方法的不同，有不同的壓縮感知算法。云加速方案的驗證，主要使用了BP和OMP(orthogonal matching pursuit)兩種算法。BP算法[3]通過基追蹤優化方法獲得原始信號的全局最優逼近解，算法的重構精度較高，但執行速度較慢。OMP算法[11]通過在每次迭代時得到一個新的近似估計，不斷逼近原始信號，最終獲得原始信號的局部最優解，算法易于實現且執行速度較快，但重構精度一般。BP算法和OMP算法都是經典的壓縮感知算法，BP算法在實驗室應用較多，而在工程中OMP算法比較常用，很多壓縮感知算法都是從這兩個算法延伸而來的。

3.2 算法的修改

為了方便并行化及利用更多的計算資源，云加速方案驗證過程中處理的基本數據對象是m′n的信號采樣，重構函數(BP函數或OMP函數)的每次調用可以重構信號的一列。這樣，對于一個m′n的信號采樣，通過調用n次重構函數就可以獲得原始信號。為了減少相互之間的關聯性，將每次重構函數的調用均作為一次獨立操作，不考慮采樣數據列之間的關系。對于n′1、m′n′k等形式的采樣數據，如果需要使用本文方案，可以對數據做簡單處理轉為m′n形式。

由前面的描述可知，要利用云加速方案實現算法加速，需要為重構函數增添一些說明和注釋，主要就是“#remote”和“#parallelize”兩個標簽。添加兩個標簽后的BP算法和OMP的代碼形式為：

根據云加速方案的設計，當執行for-循環語句時，因前面有“#parallelize”標簽，系統將同時啟動n個進程，每個進程調用一次BP或OMP函數；而函數BP和OMP因前面存在“#remote”標簽，系統將自動收集函數相關信息并序列化，然后遷移到云端執行，利用在云端申請的計算資源加速算法。

4 實驗和分析

4.1 實驗環境

云加速方案的驗證環境可以分為本地和云端兩部分。在本地使用的是PC機，性能參數為Intel(R)Core(TM) 2 Duo 雙核處理器(E4600，2.4 GHz)、2 GB內存、64位、10/100 Mb/s網卡，運行Windows 7操作系統。在云端搭建了OpenStack IaaS平臺，它管理一個服務器集群，每個刀片服務器性能參數為Intel Xeon四核處理器(2 GHz)、24 GB內存、64位、1 000 Mb/s網卡，運行Ubuntu服務器版操作系統。

圖1 云加速方案資源申請示意圖

在云加速方案中，將云端的計算資源設計為VM實例，每個實例都是相同的，包括1CPU和512 MB RAM。當申請計算資源時，以VM實例為基本單位，每次可以根據用戶需求申請一個或多個實例。圖1是申請計算資源時的請求頁面，左側“Flavor”選項可以指定計算資源類型，其中的“tiny 1 VCPU/0 GB Disk/512 MB Ram”即為壓縮感知云加速方案設計的實例；“Instance Count”選項是申請計算資源的數量，這需要用戶指定；右側的“Project Quotas”選項中列出了當前用戶可申請使用的計算資源總數。

為了驗證云加速方案，本文設計了兩組實驗，分別用于驗證方案的正確性和加速效果。在這兩組實驗中，資源的分配只能在用戶啟動重構算法時自行指定，即用戶需要指明申請的計算資源的數量。在以后的工作中可以考慮由用戶設定信號的重構條件(如用戶指定算法執行時間的限制)，系統分配符合用戶條件的計算資源數量的方法。

4.2 正確性驗證

在云加速方案的設計中，將算法從本地遷移到云端執行，取消了采樣數據的列相關性，本組實驗是為了驗證這些改動并不會影響重構效果。實驗中選取了圖像處理理論常用的3個標準測試圖像Lena.bmp(人物)、Peppers.bmp(自然景色)和Finger.bmp(指紋)，對比其分別在云端和本地重構的效果，如表1和圖2、圖3所示。

表1 本地和云端重構圖像PSNR比較

從表1可以看出，BP算法的重構精度要優于OMP算法，但這兩種重構算法的本地執行和云端執行對重構圖像的信噪比(power signal to noise ratio，PSNR)影響不大，一些細微的差別可能僅是因為重構時使用的隨機觀測矩陣不同造成的。從圖2、圖3可知，BP和OMP算法在云端重構的信號的視覺效果是可以接受的。需要進一步說明的是，3個圖像Lena.bmp、Peppers.bmp、Finger.bmp的重構效果有一定的差別，Lena.bmp的重構效果最好、Finger.bmp最差，這不是云加速方案的原因，而是壓縮感知算法本身對平滑圖像重構能力更好造成的。

圖2 BP算法的云端重構效果

圖3 OMP算法的云端重構效果

4.3 加速效果驗證

本組實驗將用于測試云加速方案對壓縮感知算法的加速效果，對重構算法的所有實驗分兩種情況。

1) 使用256′256大小的人物圖像Lena.bmp測試計算資源數量不同時的加速效果，這里申請的計算資源數量從1～16，每一個計算資源數量在不同時間段總計執行100次，求出平均的計算時間和加速比。

2) 在相同的計算資源數量下，分別測試方案對大小為128′128、256′256、512′512、1 024′1 024的Lena.bmp人物圖像的加速效果，這里比較了1個、2個、4個、8個和16個計算資源的情況。測試結果如圖4(BP算法)和圖5(OMP算法)所示，圖中“本地”的意思是直接將算法放在一個計算資源上執行，而不需要序列化和代碼遷移的過程。

在圖4、圖5所示的柱狀圖中，第1列描述算法的執行時間，對比兩個柱狀圖，BP算法的執行時間遠遠大于OMP算法，這與OMP算法的計算復雜度小于BP算法是相符的。從圖中可以看到，當申請的計算資源數量從1～16不斷增加時，BP和OMP兩個重構算法的執行時間都逐漸減少，而加速比(柱狀圖的第2列)逐漸增加，即加速效果越來越好。柱狀圖的第2～5列描述不同數量計算資源的加速比，它隨著計算資源數量的增加而不斷增加。當申請的計算資源數量相同時，加速比通常隨著信號的增大而逐漸增加，這是因為當信號尺寸比較小時，系統的額外耗費在執行時間中所占的比例比較大。

圖4 云加速方案對BP算法的加速效果

圖5 云加速方案對OMP算法的加速效果

5 物聯網中云加速方案的應用

5.1 多核/多CPU、GPGPU加速和云加速

通過4.2和4.3節的實驗可知，云加速方案可以正確地重構原始信號、并極大地提高重構算法的執行速度。但云加速方案設定每個計算資源是單CPU，在方便實現的同時沒有考慮物聯網中計算資源的多樣性。

事實上，在物聯網中同樣會存在一些高性能計算資源，如多核/多CPU和GPGPU等系統或設備，而當前硬件設備價格的不斷下降為高性能計算設備的增加帶來了福音。通常申請一個這樣的高性能計算設備，就能為算法帶來很好的加速效果。

多核/多CPU方法實現簡單，僅需要對算法做一些簡單的并行化處理就可以實現算法加速；不需要遠距離傳輸數據，節省了額外耗費；而且設備計算能力利用率比較高，加速能力強。GPGPU系統的計算核心數量都很大，可以同時啟動更多的線程，平均每個核心的花費較低。如NVIDIA Tesla C2050就擁有448個核心，理論上可同時運行448個線程。文獻[12-13]分別研究多核/多CPU和GPGPU并行加速的方法，獲得了一些實驗數據，發現在云加速方案中引入多核/多CPU和GPGPU可以帶來加速效果的進一步提升，同時可以為方案提供的服務帶來多樣性，為云加速方案走出實驗室帶來極大的好處。

5.2 物聯網中基于云的混合加速方案

多核/多CPU方法實現簡單、資源利用率高，GPGPU系統的計算資源眾多，云技術能夠很好地利用現有計算資源、提高資源利用率，這使得它在需要更多計算資源時不用追加投資購買新的軟硬件資源。如果能結合3種加速方法的優點，可以獲得更好的實用效果，既獲取更好的加速效果，又節省資金。圖6設計了一個結合3種加速方法的壓縮感知算法加速框架，基于物聯網環境的該框架以云加速方案為基礎，可以結合多核/多CPU和GPGPU加速方法，充分利用物聯網中的已有計算資源加速壓縮感知算法。

在圖6中，假設傳感器支持壓縮感知方法，為了獲取連入網絡中物體的實時信息，這些傳感器將不斷地產生以壓縮形式保存的采集數據。一般情況下，這些數據通過無線網絡被發送到數據存儲中心保存。當有用戶申請使用某些采樣數據時，這些數據將被重構為原始信號。為了提高算法的重構速度，系統將會根據用戶提出的計算條件分配相應的計算資源加速重構算法。這里的計算條件，可以是用戶申請的計算資源數量，也可以是用戶所提出的重構信號的條件，如重構時間限制等。分配給用戶的計算資源可能是一些PC機，如果用戶的需求比較緊急，也可以提供計算能力比較強的高性能計算設備，如接入網絡的多核/多CPU或GPGPU計算資源。

圖6 引入壓縮感知后的物聯網混合加速理論框架

圖7 混合加速框架重構壓縮感知的理論流程圖

5.3 混合加速方案的重構流程

可以預期，在物聯網環境中，建立基于云的混合加速框架，能夠更加充分地利用物聯網中的計算資源，為壓縮感知算法提供更好的加速效果，但是這樣會使系統中的計算資源類型變得復雜，不利于計算資源的分配。為此，需要重新設計計算資源的分配方法及算法流程，圖7所示是設計的混合加速方案流程圖。

通過圖7的流程圖可知，當用戶申請計算資源時，可以直接指定需要的計算資源，也可以提出重構信號的條件由系統分配。分配計算資源時，如果有必要可以使用高性能計算設備，但需使用一些輔助方法，這些方法在文獻[12-13]中已有介紹。

6 結 論

本文將壓縮感知方法引入物聯網的數據采集和處理，設計并實現了一個利用云技術加速壓縮感知算法的方案。該方案可以加速Python程序，通過一些定義的標簽和重寫的Python語言內嵌函數，自動地將用Python語言寫的算法遷移到云端執行，利用云資源加速算法。為了充分利用物聯網中現有的計算資源，在將壓縮感知算法的云加速方案搭建于物聯網時，提出了基于云加速方案，使用多核/多CPU或GPGPU加速方法的混合加速理論框架，以期能夠在利用壓縮感知方法減少物聯網中的采集數據規模的同時，獲得更快的算法執行速度。當前，混合加速框架還處于理論設計階段，接下來將研究其實現方法，以檢驗方案的可行性、實用性。

[1] ASHTON K. That ‘Internet of Things’ thing[EB/OL].[2012-12-01]. http://www. rfidjournal. com/articles/view?4986.

[2] ELDAR Y C, KUTYNIOK G. Compressed sensing: Theory and applications[M]. Cambridge: UK, Cambridge University Press, 2012.

[3] CHEN S S, DONOHO D L, SAUNDERS M A. Atomic decomposition by basis pursuit[J]. Siam Review, 2001,43(1): 129-159.

[4] ARMBRUST M, FOX A, GRIFFITH R, et al. A view of cloud computing[J]. Communications of the ACM, 2010,53(4): 50-58.

[5] PACHECO P. An introduction to parallel programming[M].San Francisco, USA: Morgan Kaufmann Publishers, 2011.

[6] SANDERS J, KANDROT E. CUDA by example: an introduction to general-purpose GPU programming[M].Boston: USA, Addison-Wesley Publishers, 2010.

[7] 王妮娜, 桂冠, 蘇泳濤, 等. 基于壓縮感知的M IMOOFDM系統稀疏信道估計方法[J]. 電子科技大學學報,2013, 42(1): 58-62.

WANG Ni-na, GUI Guan, SU Yong-tao, et al. Compressive sensing-based sparse channel estimation method for M IMO-OFDM systems[J]. Journal of University of Electronic Science and Technology of China, 2013, 42(1):58-62.

[8] CANDES E J, WAKIN M B. An introduction to compressive sampling[J]. IEEE Signal Processing Magazine,2008, 25(2): 21-30.

[9] CAI X, LANGTANGEN H P, MOE H. On the performance of the Python programming language for serial and parallel scientific computations[J]. Scientific Programming, 2005,13(1): 31-56.

[10] ALMASI G S, GOTTLIEB A. Highly parallel computing[M]. Redwood, USA: Benjam in-Cumm ings Publishers Co, Inc, 1989.

[11] TROPP J, GILBERT A. Signal recovery from random measurements via orthogonal matching pursuit[J]. IEEE Transactions on Information Theory, 2007, 53(12): 4655-4666.

[12] ZHANG Yong-ping, ZHNAG Gong-xuan, ZHU Zhaomeng, et al. Study on parallel compressed sensing for mass data in Internet of Things[C]//PDPTA’12. Las Vegas:CSREA Press, 2012: 571-576.

[13] YADAV K, M IYYAL A, ANSAR M A, et al. Parallel implementation of compressed sensing algorithm on CUDA-GPU[J]. International Journal of Computer Science and Information Security, 2011, 9(3): 112-119.

編 輯 漆 蓉