張永平，張功萱，朱昭萌

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

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

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

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

1 壓縮感知理論

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

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

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

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

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

2 云加速方案

優(yōu)化算法的計算復(fù)雜度一般都很高，通常壓縮感知方法中的信號的重構(gòu)時間很長。本節(jié)研究利用云技術(shù)加速壓縮感知算法的設(shè)計方案。

2.1 方案設(shè)計

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

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

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

2.2 算法遷移

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

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

2.3 循環(huán)的并行化

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

Python語言中，list模式提供了方便的創(chuàng)建列表的方法，而列表很容易實現(xiàn)并行化。云加速方案的并行化思想就是把循環(huán)語句轉(zhuǎn)化為list模式，通過設(shè)計的專門轉(zhuǎn)換接口，可以自動轉(zhuǎn)換標(biāo)記了“#parallelize”標(biāo)簽的循環(huán)語句。

在Python語言中，內(nèi)嵌函數(shù)map常用來構(gòu)造迭代，但其不適合于并行化，將其重寫為pmap函數(shù)。在pmap函數(shù)中定義了一個繼承l(wèi)ist模式的新類，它使程序在迭代時不必等待本次迭代全部結(jié)束就可以繼續(xù)后面的迭代運(yùn)算，從而實現(xiàn)并行化。

云加速方案是使用Python語言實現(xiàn)的，對Python語言實現(xiàn)的算法，只需要增加一些接口和標(biāo)簽，就能自動并行化指定的循環(huán)并將標(biāo)記的函數(shù)遷移到云端進(jìn)行處理。

3 驗證算法及修改

3.1 選擇驗證算法

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

3.2 算法的修改

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

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

根據(jù)云加速方案的設(shè)計，當(dāng)執(zhí)行for-循環(huán)語句時，因前面有“#parallelize”標(biāo)簽，系統(tǒng)將同時啟動n個進(jìn)程，每個進(jìn)程調(diào)用一次BP或OMP函數(shù)；而函數(shù)BP和OMP因前面存在“#remote”標(biāo)簽，系統(tǒng)將自動收集函數(shù)相關(guān)信息并序列化，然后遷移到云端執(zhí)行，利用在云端申請的計算資源加速算法。

4 實驗和分析

4.1 實驗環(huán)境

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

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

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

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

4.2 正確性驗證

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

表1 本地和云端重構(gòu)圖像PSNR比較

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

圖2 BP算法的云端重構(gòu)效果

圖3 OMP算法的云端重構(gòu)效果

4.3 加速效果驗證

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

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

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

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

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

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

5 物聯(lián)網(wǎng)中云加速方案的應(yīng)用

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

通過4.2和4.3節(jié)的實驗可知，云加速方案可以正確地重構(gòu)原始信號、并極大地提高重構(gòu)算法的執(zhí)行速度。但云加速方案設(shè)定每個計算資源是單CPU，在方便實現(xiàn)的同時沒有考慮物聯(lián)網(wǎng)中計算資源的多樣性。

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

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

5.2 物聯(lián)網(wǎng)中基于云的混合加速方案

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

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

圖6 引入壓縮感知后的物聯(lián)網(wǎng)混合加速理論框架

圖7 混合加速框架重構(gòu)壓縮感知的理論流程圖

5.3 混合加速方案的重構(gòu)流程

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

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

6 結(jié) 論

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

[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系統(tǒng)稀疏信道估計方法[J]. 電子科技大學(xué)學(xué)報,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.

編 輯 漆 蓉