WSN中基于壓縮感知的分簇數(shù)據(jù)收集算法

張 蕾,崔娟娟,李晶晶

(揚(yáng)州大學(xué)廣陵學(xué)院機(jī)械電子工程系,江蘇 揚(yáng)州 225000)

0 引 言

隨著信息技術(shù)的發(fā)展，無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)已經(jīng)普遍應(yīng)用于軍事、農(nóng)業(yè)、醫(yī)療衛(wèi)生、家居服務(wù)、環(huán)境監(jiān)測等諸多領(lǐng)域[1]。WSN是由若干成本較低、計算和通信能力以及自身能量有限的傳感器節(jié)點(diǎn)根據(jù)特定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)組成。網(wǎng)絡(luò)中節(jié)點(diǎn)的能耗問題是設(shè)計無線傳感器網(wǎng)絡(luò)的關(guān)鍵問題[2]。

WSN分簇算法的提出有效地降低了網(wǎng)絡(luò)的能量消耗,均衡了網(wǎng)絡(luò)的能量負(fù)載。Heinzelman[3]于2000年提出了LEACH算法，LEACH算法是經(jīng)典的分簇路由算法，它通過等概率地隨機(jī)選舉簇頭節(jié)點(diǎn)，來均衡網(wǎng)絡(luò)的能量負(fù)載。然而，LEACH算法中簇頭節(jié)點(diǎn)的選擇沒有考慮節(jié)點(diǎn)能量和距離等因素[4]，簇結(jié)構(gòu)和簇頭節(jié)點(diǎn)的分布很不均勻，那些剩余能量少或者遠(yuǎn)離基站Sink的節(jié)點(diǎn)仍會被選為簇頭節(jié)點(diǎn)，這將導(dǎo)致大量的節(jié)點(diǎn)在數(shù)據(jù)傳輸?shù)倪^程中過早地死亡，從而縮短了網(wǎng)絡(luò)的運(yùn)行周期。

針對LEACH算法的缺陷，國內(nèi)外專家對其進(jìn)行了研究和改進(jìn)。LEACH-C[3]、HEED[6]、DEEC[7]等經(jīng)典的分簇路由算法相繼被提出。這些算法考慮了節(jié)點(diǎn)的剩余能量和距離信息，解決了LEACH算法隨機(jī)選舉簇頭節(jié)點(diǎn)的問題[8-9]。然而，這些算法分成的簇結(jié)構(gòu)分布不均勻，網(wǎng)絡(luò)中能量的消耗也不均勻。聚類算法能夠根據(jù)數(shù)據(jù)之間的相似性對大量的數(shù)據(jù)進(jìn)行分類，與WSN中的分簇算法思想類似。因此，國內(nèi)外很多學(xué)者將聚類算法應(yīng)用到WSN的分簇過程中[10]。其中，應(yīng)用最廣泛的聚類分析算法是K-means聚類算法。文獻(xiàn)[11-14]均在網(wǎng)絡(luò)分簇階段采用了K-means聚類算法，基于節(jié)點(diǎn)的剩余能量和距離信息競選簇頭節(jié)點(diǎn)，既保證了簇結(jié)構(gòu)和簇頭節(jié)點(diǎn)分布的均勻性，又均衡了網(wǎng)絡(luò)的能量消耗，延長了網(wǎng)絡(luò)的運(yùn)行周期。

為了降低WSN的數(shù)據(jù)傳輸量，很多學(xué)者將壓縮感知算法(Compressed Sensing, CS)應(yīng)用于WSN的數(shù)據(jù)收集[15-16]。對于稀疏信號或者在變換基空間上可壓縮的信號，CS理論可以通過遠(yuǎn)低于奈奎斯特頻率的方式對信號進(jìn)行采樣,并且能夠精準(zhǔn)地恢復(fù)出原始信號。CS技術(shù)在采集數(shù)據(jù)的同時實(shí)現(xiàn)了數(shù)據(jù)的壓縮，降低了數(shù)據(jù)的冗余度，大大減少了數(shù)據(jù)通信量，延長了網(wǎng)絡(luò)的生命周期[17]。

本文基于上述研究，綜合考慮了網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)據(jù)的時空相關(guān)性，提出一種將K-means均衡分簇與CS理論相結(jié)合的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集算法。該算法首先采用K-means算法對WSN進(jìn)行均衡分簇，根據(jù)簇內(nèi)節(jié)點(diǎn)的剩余能量和位置信息選取簇頭節(jié)點(diǎn)。各簇頭節(jié)點(diǎn)使用CS理論對采樣的數(shù)據(jù)進(jìn)行數(shù)據(jù)融合，并通過多跳路由的方式傳送給基站Sink節(jié)點(diǎn)。Sink節(jié)點(diǎn)使用OMP算法對收集的數(shù)據(jù)進(jìn)行精準(zhǔn)重構(gòu)。經(jīng)仿真實(shí)驗(yàn)表明，該算法有效地減少了網(wǎng)絡(luò)的數(shù)據(jù)通信量，降低了壓縮感知過程中所需要的觀測量，均衡了WSN的能量消耗并延長了網(wǎng)絡(luò)壽命。

1 基于K-means均衡分簇算法

本文提出的基于K-means均衡分簇算法是以輪循環(huán)方式進(jìn)行的，只在第一輪采用K-means聚類算法劃分網(wǎng)絡(luò)成簇，此后的每一輪網(wǎng)絡(luò)的簇結(jié)構(gòu)都是固定的[11]。第一輪分為簇形成階段、簇頭競選階段和數(shù)據(jù)傳輸階段，其他每一輪分為簇頭競選階段和數(shù)據(jù)傳輸階段[12]。簇頭的選舉需要綜合考慮節(jié)點(diǎn)自身的能量、節(jié)點(diǎn)到簇內(nèi)其他各節(jié)點(diǎn)的距離、節(jié)點(diǎn)與基站的距離。本文采用參量值r來衡量每個傳感器節(jié)點(diǎn)，每一輪簇內(nèi)r值最大的節(jié)點(diǎn)當(dāng)選簇頭節(jié)點(diǎn)。參量值r的計算公式如下：

(1)

其中，Ei為節(jié)點(diǎn)i的能量，dsi為節(jié)點(diǎn)i到基站Sink節(jié)點(diǎn)的距離，dki為節(jié)點(diǎn)i與簇內(nèi)其他各節(jié)點(diǎn)的距離，cn為簇內(nèi)節(jié)點(diǎn)數(shù)。α為網(wǎng)絡(luò)系數(shù)，取值范圍為(0,1)。α值根據(jù)經(jīng)驗(yàn)選擇，值越小則簇首更新頻率越慢。

無線傳感器網(wǎng)絡(luò)分簇數(shù)的確定通常需要考慮網(wǎng)絡(luò)的能量損耗模型。本文的能量損耗模型是基于文獻(xiàn)[18]和文獻(xiàn)[19]實(shí)現(xiàn)的。該能量損耗模型由發(fā)送電路的能耗、信號放大器的能耗和接收電路的能耗構(gòu)成。設(shè)發(fā)送L比特數(shù)據(jù)，發(fā)送過程中消耗的能量如式(2)：

(2)

接收L比特數(shù)據(jù)的過程中消耗的能量如式(3)：

ERx=Eelec×L

(3)

其中，Eelec是發(fā)送或接收單位比特數(shù)據(jù)的能耗，Efs是自由空間衰落模型的能量系數(shù)，Emp是多路徑衰落模型的能量系數(shù)，D為傳輸?shù)木嚯x。Dc是一個常量，表示距離的臨界值。當(dāng)傳輸距離D小于Dc時采用自由空間衰落模型，否則采用多路徑衰落模型。

根據(jù)文獻(xiàn)[12]和文獻(xiàn)[20]可得到無線傳感器網(wǎng)絡(luò)分簇數(shù)k的最優(yōu)值為：

(4)

其中，n表示網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目，M表示正方形網(wǎng)絡(luò)區(qū)域的邊長，dmean表示節(jié)點(diǎn)到基站的平均距離。

2 WSN中壓縮感知算法概述

2.1 壓縮感知算法

壓縮感知理論指出：如果信號是稀疏的或者在變換基空間上稀疏，壓縮感知技術(shù)可以通過遠(yuǎn)低于奈奎斯特頻率的方式對信號進(jìn)行采樣,并且能夠精確地重構(gòu)出原始信號[21]。假設(shè)原始信號為X=[x1,x2,…,xN]T∈RN，在N×N維變換基矩陣Ψ下是稀疏的，則原始信號X可以表示為：

X=Ψθ

(5)

其中，列向量θ只有少量的非零元素。稀疏矩陣Ψ一般為固定的正交基矩陣，比如傅里葉變換矩陣、離散余弦變換矩陣和離散小波變換矩陣等[22]。

Y=ΦX=ΦΨθ=Θθ

(6)

其中,Θ稱為傳感矩陣，Θ=ΦΨ。目前常用的測量矩陣Φ有隨機(jī)高斯矩陣、伯努利隨機(jī)測量矩陣、托普利茲矩陣、正交測量矩陣等。

由于信號X在變換基上是稀疏的，而且傳感矩陣Θ滿足RIP性質(zhì)。基于以上2個原則，重構(gòu)原始信號成為可能。信號重構(gòu)算法主要分為凸優(yōu)化算法和貪婪迭代算法2類[23]。

2.2 基于時空相關(guān)性的壓縮感知算法

無線傳感器網(wǎng)絡(luò)在監(jiān)測區(qū)域內(nèi)部署了大量的傳感器節(jié)點(diǎn)并連續(xù)采樣。因此，同一傳感器節(jié)點(diǎn)在相鄰時刻所采集的數(shù)據(jù)存在時間冗余，同一節(jié)點(diǎn)與相鄰節(jié)點(diǎn)在相同時刻所采集的數(shù)據(jù)之間存在空間冗余。由于無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)據(jù)在時間和空間上存在一定的相關(guān)性，為了降低數(shù)據(jù)之間的冗余度，更好地壓縮數(shù)據(jù)，本文對壓縮感知算法中的稀疏基進(jìn)行了改進(jìn)[24-25]，具體如下:

假定無線傳感器網(wǎng)絡(luò)中某個簇內(nèi)布置了N個傳感器，在某段時間內(nèi)每個節(jié)點(diǎn)采集K個數(shù)據(jù)。第i個節(jié)點(diǎn)采集到的數(shù)據(jù)可以表示為：

Di=[di1,di2,…,diK]T

(7)

那么，這段時間內(nèi)簇首節(jié)點(diǎn)收集到的數(shù)據(jù)可以表示為：

本底資料為2013年國家下發(fā)的1∶250 000 DLG數(shù)據(jù)，更新資料為2017年更新完成的云南省1∶50 000 DLG數(shù)據(jù)庫[1]。

(8)

在第j時刻，簇首節(jié)點(diǎn)收集到的數(shù)據(jù)可以表示為：

Xj=[d1j,d2j,…,dNj]

(9)

(10)

其中，D∈RK×N,C∈RN×N。

用特征值分解方法求矩陣C的特征向量P，將特征向量P作為稀疏基Ψ。這段時間內(nèi)任意時刻簇頭節(jié)點(diǎn)收集到的原始數(shù)據(jù)都采用同一稀疏基。由文獻(xiàn)[25]和文獻(xiàn)[26]可知，協(xié)方差矩陣可以衡量矩陣維度之間的關(guān)系。所以，矩陣C可以度量網(wǎng)絡(luò)中不同節(jié)點(diǎn)數(shù)據(jù)之間的相關(guān)性。將協(xié)方差矩陣C對應(yīng)的特征向量作為稀疏基，去除節(jié)點(diǎn)數(shù)據(jù)之間的相關(guān)性，降低數(shù)據(jù)的冗余度。

本文采用隨機(jī)高斯矩陣作為測量矩陣Φ，觀測向量Y=ΦX。壓縮感知算法的壓縮率定義為ρ=N/M，N為原始數(shù)據(jù)X的維數(shù)，M為觀測向量Y的維數(shù)。

WSN中各個簇頭節(jié)點(diǎn)采用基于時空相關(guān)性的壓縮感知技術(shù)對收集到的數(shù)據(jù)進(jìn)行壓縮并傳至基站Sink節(jié)點(diǎn)，由基站對收集到的數(shù)據(jù)進(jìn)行精確重構(gòu)[27]。本文選擇OMP算法作為信號重構(gòu)算法，詳細(xì)描述如算法1所示。

算法1OMP算法

輸入：傳感矩陣Θ，觀測向量Y，迭代次數(shù)K

輸出：信號稀疏表示系數(shù)θ

Step1初始化設(shè)殘差R0=Y，迭代次數(shù)t=1，索引集合Λ為空集。

Step2計算殘差與傳感矩陣Θ的列Θj的內(nèi)積，找出最大內(nèi)積值對應(yīng)的索引λt，即：

Step3更新索引集Λ和原子集Θt，令Λt=Λt-1∪{λt}，將與殘差內(nèi)積最大的值所對應(yīng)的傳感矩陣Θ的列Θj并入原子集Θt，令Θt=[Θt,Θj]。

Step4計算Y=Θtθt的最小二乘解：

3 仿真實(shí)驗(yàn)和結(jié)果分析

本章對本文提出的算法進(jìn)行仿真實(shí)驗(yàn)，并與其他幾種算法進(jìn)行比較。本文采用網(wǎng)絡(luò)的數(shù)據(jù)通信量和信號重構(gòu)時的效果作為評估標(biāo)準(zhǔn)。

3.1 網(wǎng)絡(luò)通信量比較

3.1.1 仿真參數(shù)

本節(jié)通過仿真實(shí)驗(yàn)對不同數(shù)據(jù)收集算法進(jìn)行比較，采用無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)通信量作為評估算法的標(biāo)準(zhǔn)。在用于對比的數(shù)據(jù)收集算法中，LEACH with CS算法采用LEACH算法對網(wǎng)絡(luò)分簇，在簇首節(jié)點(diǎn)采用本文提出的基于時空相關(guān)性的壓縮感知算法融合數(shù)據(jù)；HEED with CS算法采用HEED算法對網(wǎng)絡(luò)分簇，在簇首節(jié)點(diǎn)采用本文提出的基于時空相關(guān)性的壓縮感知算法融合數(shù)據(jù)；Clustering without CS算法采用了與本文相同的分簇結(jié)構(gòu)，但在簇首節(jié)點(diǎn)沒有使用CS算法；LEACH without CS算法采用了LEACH算法對網(wǎng)絡(luò)分簇，但沒有使用CS算法。

假設(shè)傳感器網(wǎng)絡(luò)的分布區(qū)域?yàn)橐粋€100×100的正方形區(qū)域?；維ink節(jié)點(diǎn)的坐標(biāo)為(0,0)。傳感器節(jié)點(diǎn)個數(shù)從400～1600，以200為每步的增量。每個節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)包數(shù)為5。壓縮率分別設(shè)置為5、10、15。為了保證實(shí)驗(yàn)的準(zhǔn)確性，采用30次隨機(jī)拓?fù)浞抡娼Y(jié)果的平均值作為實(shí)驗(yàn)結(jié)果[28]。

3.1.2 實(shí)驗(yàn)結(jié)果分析

在不同的壓縮率下，隨著傳感器節(jié)點(diǎn)個數(shù)的增加，將本文算法與其他4種數(shù)據(jù)收集算法在網(wǎng)絡(luò)通信量方面的變換進(jìn)行了比較。圖1(a)是壓縮率為5時，各算法對應(yīng)的網(wǎng)絡(luò)通信量。圖1(b)是壓縮率為10時，各算法對應(yīng)的網(wǎng)絡(luò)通信量。圖1(c)是壓縮率為15時，各算法對應(yīng)的網(wǎng)絡(luò)通信量。

(a) 壓縮率為5

(b) 壓縮率為10

(c) 壓縮率為15

由圖1可知，隨著無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)的增加，對應(yīng)的網(wǎng)絡(luò)通信量也在增加。由于LEACH without CS算法和Clustering without CS算法在簇頭節(jié)點(diǎn)沒有使用CS算法對數(shù)據(jù)進(jìn)行融合,本文提出的算法對應(yīng)的網(wǎng)絡(luò)通信量是遠(yuǎn)遠(yuǎn)小于這2種算法對應(yīng)的網(wǎng)絡(luò)通信量的。根據(jù)前文對CS理論的分析可知，這樣的結(jié)果是必然的。同時，由圖1可知，本文提出的算法對應(yīng)的網(wǎng)絡(luò)通信量也是小于HEED with CS算法對應(yīng)的網(wǎng)絡(luò)通信量的。

由圖1(a)可知，在壓縮率為5的情況下，當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)小于1200時，LEACH with CS算法對應(yīng)的網(wǎng)絡(luò)通信量少于本文提出的算法對應(yīng)的網(wǎng)絡(luò)通信量。當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)大于等于1200時，本文提出的算法對應(yīng)的網(wǎng)絡(luò)通信量更少。由圖1(b)可知，在壓縮率為10的情況下，當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)大于等于1000時，與LEACH with CS算法相比，本文提出的算法對應(yīng)的網(wǎng)絡(luò)通信量更少。同樣，由圖1(c)可知，在壓縮率為15的情況下，在節(jié)點(diǎn)數(shù)為400～1600的范圍內(nèi)，相較于LEACH with CS算法，本文提出的算法對應(yīng)的網(wǎng)絡(luò)通信量更少，效果更好。根據(jù)圖1可以總結(jié)出這樣2條結(jié)論：1)本文提出的算法更加適合節(jié)點(diǎn)數(shù)較多、規(guī)模較大的無線傳感器網(wǎng)絡(luò);2)壓縮率越大，相較于LEACH with CS算法，本文提出的算法對應(yīng)的網(wǎng)絡(luò)通信量更少，效果更好。同時，本文提出的算法采用K-means聚類算法對網(wǎng)絡(luò)分簇，簇頭節(jié)點(diǎn)的選舉考慮了節(jié)點(diǎn)的剩余能量和位置信息。相較于LEACH with CS算法和HEED with CS算法，本文提出的算法均衡了網(wǎng)絡(luò)能耗，算法的擴(kuò)展性更好，更加適合大型的無線傳感器網(wǎng)絡(luò)。

3.2 信號重構(gòu)效果比較

本節(jié)基于MATLAB平臺進(jìn)行仿真實(shí)驗(yàn)，仿真對象為意大利某城市二氧化氮濃度的數(shù)據(jù)，數(shù)據(jù)集來源于UCI機(jī)器學(xué)習(xí)網(wǎng)站。實(shí)驗(yàn)比較了以隨機(jī)高斯矩陣為測量矩陣、傅里葉變換矩陣為稀疏基、以O(shè)MP算法為信號重構(gòu)算法的壓縮感知算法(FFTCS)，以隨機(jī)高斯矩陣為測量矩陣、離散余弦變換矩陣為稀疏基、以O(shè)MP算法為信號重構(gòu)算法的壓縮感知算法(DCTCS)和本文提出的基于時空相關(guān)性的壓縮感知算法。主要比較的是這3種壓縮感知算法重構(gòu)所需要的測量值與重構(gòu)誤差之間的關(guān)系[29]。數(shù)據(jù)的重構(gòu)誤差可以定義為：

(11)

其中，X是原始數(shù)據(jù)，X′為重構(gòu)后的數(shù)據(jù)。

實(shí)驗(yàn)結(jié)果如圖2所示。隨著觀測值的增加，重構(gòu)誤差的值越來越小。以相對重構(gòu)誤差ε=O(10-15)為精確重構(gòu)的標(biāo)準(zhǔn)，由仿真結(jié)果可知，當(dāng)觀測值為60時，本文提出的基于時空相關(guān)性的壓縮感知算法已經(jīng)達(dá)到精確重構(gòu)的標(biāo)準(zhǔn)。然而，F(xiàn)FTCS算法和DCTCS算法，在觀測值為300的情況下，仍然沒有達(dá)到精確重構(gòu)的標(biāo)準(zhǔn)。當(dāng)觀測值為300時，F(xiàn)FTCS算法的重構(gòu)誤差約為0.128，DCTCS算法的重構(gòu)誤差約為0.134。在相同重構(gòu)誤差的情況下，相較于FFTCS算法和DCTCS算法，本文提出的算法所需要的觀測量更少。

圖2 不同算法的重構(gòu)效果

4 結(jié)束語

本文基于WSN中節(jié)點(diǎn)數(shù)據(jù)時空相關(guān)性的特點(diǎn)，提出了一種將K-means均衡分簇與CS理論相結(jié)合的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集算法。該算法采用K-means均衡分簇算法對網(wǎng)絡(luò)進(jìn)行分簇并選擇簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)采用CS理論采集數(shù)據(jù)，匯聚節(jié)點(diǎn)Sink采用OMP算法對收集到的數(shù)據(jù)進(jìn)行重構(gòu)。實(shí)驗(yàn)結(jié)果表明，相比于其他網(wǎng)絡(luò)數(shù)據(jù)收集算法，本文提出的方法的網(wǎng)絡(luò)通信量更低，擴(kuò)展性更好，更加適合大型的無線傳感器網(wǎng)絡(luò)；與傳統(tǒng)的壓縮感知算法相比，本文提出的基于時空相關(guān)性的壓縮感知算法降低了所需要的觀測量，重構(gòu)效果更好。