張 蕾,崔娟娟,李晶晶

(揚州大學廣陵學院機械電子工程系,江蘇 揚州 225000)

0 引 言

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

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

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

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

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

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

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

(1)

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

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

(2)

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

ERx=Eelec×L

(3)

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

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

(4)

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

2 WSN中壓縮感知算法概述

2.1 壓縮感知算法

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

X=Ψθ

(5)

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

Y=ΦX=ΦΨθ=Θθ

(6)

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

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

2.2 基于時空相關性的壓縮感知算法

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

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

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

(7)

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

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

(8)

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

Xj=[d1j,d2j,…,dNj]

(9)

(10)

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

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

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

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

算法1OMP算法

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

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

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

Step2計算殘差與傳感矩陣Θ的列Θj的內積，找出最大內積值對應的索引λt，即：

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

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

3 仿真實驗和結果分析

本章對本文提出的算法進行仿真實驗，并與其他幾種算法進行比較。本文采用網絡的數(shù)據通信量和信號重構時的效果作為評估標準。

3.1 網絡通信量比較

3.1.1 仿真參數(shù)

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

假設傳感器網絡的分布區(qū)域為一個100×100的正方形區(qū)域?；維ink節(jié)點的坐標為(0,0)。傳感器節(jié)點個數(shù)從400～1600，以200為每步的增量。每個節(jié)點傳輸?shù)臄?shù)據包數(shù)為5。壓縮率分別設置為5、10、15。為了保證實驗的準確性，采用30次隨機拓撲仿真結果的平均值作為實驗結果[28]。

3.1.2 實驗結果分析

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

(a) 壓縮率為5

(b) 壓縮率為10

(c) 壓縮率為15

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

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

3.2 信號重構效果比較

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

(11)

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

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

圖2 不同算法的重構效果

4 結束語

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