基于均衡分簇的無線傳感器網絡壓縮數據收集

喬建華，張雪英

(1.太原理工大學信息工程學院，太原030024; 2.太原科技大學電子信息工程學院，太原030024)(*通信作者電子郵箱tyzhangxy@163.com)

0 引言

無線傳感器網絡(Wireless Sensor Network，WSN)的首要制約因素就是能源問題，如何降低能耗是WSN需要重點考慮的問題。WSN中大部分能量消耗在通信部分，在發送和接收狀態下能耗最大。將壓縮感知(Compressed Sensing，CS)理論應用在WSN的數據收集中，可以大大減少傳送數據量，從而降低能耗，延長網絡壽命。

Bajwa等［1］最早將CS理論應用于無線傳感器網絡的數據采集。文獻［2］闡述了基于CS的WSN數據采集的實現過程，指出CS具有普適的采樣和分散的編碼的特征，并給出了從網絡節點到融合中心通過無線方式傳送隨機投影值的兩種方法:直傳式和路由中轉式。

文獻［3］首次提出大規模 WSN的壓縮數據收集(Compressive Data Gathering，CDG)方案，不再采用文獻［2］的每個節點各自傳送的方式，而是由匯聚節點(Sink)得到所有讀數的加權和。CDG的示意圖如圖1所示。

圖1 多跳路由的壓縮數據收集示意圖Fig.1 Schematic diagram of compressive data gathering in a multi-hop routing

CDG基于CS理論，對M×N 維測量矩陣的每一行系數在N個傳感器節點上進行投影，每個節點有M個投影系數{ Φi，j}Mi=1，然后與本地采集的數據進行加權傳輸。例如傳感器節點s1將它的采集數據d1和投影系數1的乘積v1傳送給下一個節點s2，s2將它的d2和投影系數2的乘積v2再加上v1傳給下一個節點s3，沿路由不斷進行下去，最后Sink得到一個加權和測量值。每個節點經過M次傳送后，Sink就能得到M個測量值。然后利用重構算法得到原始信號?；贑S的壓縮數據收集將Sink所需的N個采樣值轉化為收集M(M N)個本地采樣值的加權和。減少了傳輸的數據量，降低了能耗，延長了網絡壽命。因此，該收集方案成為多跳路由收集的基本方案。

如果測量矩陣是稀疏隨機投影矩陣，則每行系數會出現若干0，與節點采樣值的乘積也為0，這時無需進行傳輸，因此對于稀疏測量矩陣，只需要傳送非0系數對應的節點的加權結果。所以，隨機投影傳輸的數據量更少，從而更加延長了網絡壽命。Haupt等［4］最早就指出一個相對較小的信號的隨機投影數可以包含其大部分顯著的信息;因此，如果一個信號在某些正交基上是可壓縮的，則可以非常精確地從隨機投影得到重建，因而，稀疏隨機矩陣成為CS在WSN中應用的首選矩陣。文獻［5］利用稀疏隨機矩陣降低通信成本來恢復在信道衰落下由WSN觀測的稀疏信號，但重點研究的是信號恢復所需的測量次數。文獻［6］提出了一種大規模WSN的自適應稀疏隨機投影算法，主要考慮隨機投影的稀疏性對均方誤差和系統時延的影響，以更好地實現均方誤差和系統延遲之間的權衡。文獻［7］利用稀疏隨機測量矩陣的優點來減少能量消耗，提出基于簇的加權壓縮數據采集方法，采用最小生成樹投影來減少能量消耗，減少傳感器節點數。但是僅針對空間相關的數據收集，也沒有考慮收集器的最優位置。文獻［8］綜述了基于CS的WSN壓縮數據收集的不同方法。這些文獻都用到了稀疏隨機投影矩陣，但都沒有說明采集數據的具體收集過程。

文獻［9－10］提出了一種采用隨機投影的壓縮數據收集方法，即在網絡中隨機選擇M個節點稱為投影節點以收集M個加權和。投影節點相當于簇頭，測量矩陣Φ的每一行非0元素對應的節點分配給一個投影節點。每個投影節點通過最小生成樹路由收集相應這一行數據的加權和，并發送給Sink，從而完成全部數據收集，形成M個測量值。該方案存在的一個主要問題就是投影節點的選擇是根據M/N的概率隨機選出的。由于其隨機性，選出的投影節點無任何規律可言，不能保證選擇出位置合適、能量較高、數量精確的理想的投影節點。但顯然，投影節點在網絡中的位置會影響聚合算法的效率。其次，由于測量矩陣每行的非0系數的位置也是隨機的，一組遠近不等的節點將加權和傳送到位置不定的投影節點，這樣的網絡耗能勢必會很不均衡。而且由非0節點到投影節點通過樹結構建立路由，開銷也較大，另外也沒有說明在網絡運行過程中出現節點死亡后的情形。

針對隨機選擇投影節點產生的問題，本文提出均衡投影節點的壓縮數據收集方法。根據WSN節點分布是否均勻提出基于空間位置和基于節點分布密度的均衡分簇法，然后再進行壓縮數據收集，并通過與隨機投影節點方法的比較，驗證了本文方法能夠有效平衡網絡能耗、延長網絡壽命。

1 均衡分簇原理

1.1 壓縮感知基本理論

壓縮感知［11－12］理論指出［13］:對于稀疏信號或可壓縮信號，可以以遠低于Nyquist頻率的采樣頻率對數據采樣，然后通過非線性重建算法完美地重建信號。設N維信號x，在某N×N維的稀疏變換矩陣Ψ下可以表示為:

其中:θ是K稀疏的N×1的列向量，即θ中只有K個非零項，且K N。然后在M×N維測量矩陣(或稱投影矩陣、觀測矩陣)Φ下投影，得M個觀測值y，且M N，即:

其中:T稱為傳感矩陣;y為M×1的列向量，即為測量值。

壓縮感知理論指出，式(2)存在確定解的充分條件是T滿足有限等距性質(Restricted Isometry Property，RIP)［14］，即存在δ∈(0，1)使得全部K稀疏信號θ均滿足:

則可以通過求解以下凸優化問題得到重建信號^θ［12－13］:

式(4)可以采用基追蹤或貪婪算法等方法重構原始信號^x。

1.2 均衡分簇原理

根據CS理論，設測量矩陣Φ是M×N維的矩陣，x為N×1維的列向量，則有:

其中:Xj是將N個x分成L段的各分段，每段長度設為Nj(j=1，2，…，L);每個Φj為M × Nj(j=1，2，…，L) 維矩陣。這樣，每段x就可以稱為一個簇，每個簇可以選擇一個投影節點作為簇頭。簇頭收集每個簇的數據傳到Sink，Sink將所有簇的數

從式(5)可以看出，對于N個節點xj(j=1，2，…，N)，可以將Φ中每行與x乘加的結果一次算出來，得M個測量值。也可以把N個節點分段來處理，假設將N個節點分成L段，每段可以是不同的點數量。測量矩陣Φ，也可以對應分成L塊，每塊為M行的矩陣，列數與對應x各分段的點數相等。每個分塊矩陣與對應的x的每段相乘便得到M×1的列向量，然后L個列向量再進行相加，得M個測量值。用公式表示為:據對應相加，就得到了最終的測量值。用這個測量值及傳感矩陣，就可以進行數據重構。若只對某些區域感興趣，也可以只取其中某些段，由于測量矩陣具有隨機性，部分隨機矩陣仍滿足RIP，仍可恢復信號，由于測量比增加，會得到更高的重構性能。

在每個分段選擇一個投影節點，可使投影節點分布均衡;而且，依據一定條件來選擇，可以選出能量較高，位置更優越的投影節點。本文根據網絡節點分布是否均勻，提出了兩種均衡分簇的方法。

2 基于空間位置的均衡分簇法

針對節點分布密度均勻的網絡，提出基于空間位置的均衡分簇法。為了使投影節點分布均勻，將監測區域劃分成大小相等的網格，在每個網格內選舉性能最優的節點作為投影節點。然后投影節點收集所在簇的加權和數據，再傳送到Sink。具體的實施過程如下。

1)選擇第一輪的投影節點及成簇:

a)確定分簇數量及網格數。

b)以相同尺寸劃分整個監測區域為所計算的網格數。

c)在每個網格選擇網格中心周圍位置且能量較高的節點作投影節點。

d)發送投影節點信息給每個網格的投影節點。

e)每個傳感器節點依據距離最近(跳步最少)選擇它相應的投影節點。

2)在一輪簇建立以后，就可以進行數據收集了，簇內數據通過傳感節點經路由傳送到簇內投影節點。全部簇的投影節點所收集數據經一定路由傳至匯聚節點，再將其對應相加，就是全部測量值，然后通過重構就可以恢復原始數據。

3)接著就可以進行下一輪投影節點的選擇和新簇的建立，其過程為:

a)簇內節點將其剩余能量值傳送給投影節點。

b)投影節點選擇簇中心能量較大者作為新投影節點。c)每個原來的投影節點將其信息傳給新投影節點。d)每個傳感節點尋找它的新投影節點，形成新簇。

2.1 簇頭數目的確定

由于能量問題是WSN中路由算法需要考慮的首要問題，本文采用了簡化的網絡信道損耗模型［15］，如圖2所示。

圖2 信道損耗模型Fig.2 Channel loss model

假設有N個傳感器節點隨機分布在半徑為R的區域內，其中簇頭個數為h，則簇頭節點的平均覆蓋面積為πR2/h。假設簇頭節點每跳的傳輸距離為D，每個簇頭的能量消耗在三方面:接收所有簇成員的信息、融合這些數據、把融合后的信息傳送給Sink節點［16］。則在一幀中簇頭節點消耗的能量為:

其中:k為每個數據的信息位數;Eelect為每比特數據在發射電路或接收電路中所消耗的能量;EDA為數據融合的消耗;Efs為耗散能量，與所采用的傳輸信號模型有關，為自由空間傳輸常數;D是簇頭節點發送數據的距離。

假設簇內傳感器節點離簇頭的距離不超過自由空間模型的臨界值［16］，則一個非簇頭節點的能量消耗為:

發送一幀中一個簇的能量消耗為:

在R區域每個簇發送一幀(忽略數據轉發的能量消耗)的總能量消耗為:

由式(9)～(11)整理化簡得:

對Etotal求導，得到最優簇頭數為:

若設定監測區域大小為100 m×100 m的空間，部署有100個傳感器節點，每跳的傳輸距離D為槡50 2 m，半徑R設為方形區域的半邊長50 m，則根據式(13)得h≈17。為方便計可將區域劃分為16個網格。

2.2 節點的網格坐標

空間投影節點均衡劃分通過網格來實現，首先考慮節點分布密度恒定的場合。一個網格選擇一個投影節點，因此100 m×100 m的區域劃分成4×4的16個網格，如圖3所示，鄰近網格內的節點都可以互相傳輸信息，并且呈對角線分布的兩個網格在對角線的兩端的節點都在通信范圍內。設這些網格的邊長是d，節點可以傳輸的最遠距離是Rs，則兩個節點之間互相傳輸信息的距離是Rs≤ 2d。

圖3 節點分布密度均勻的網格劃分Fig.3 Grid partition with uniform node distribution density

在劃分好的網格下，首先要確定節點的網格坐標。假設Sink位于區域中心，根據節點地理位置計算其在區域內的網格坐標:

其中:Tx表示節點的網格橫坐標;Ty表示節點的網格縱坐標;S(i).xd和S(i).yd分別表示節點本身的橫坐標和縱坐標;Xm和Ym是監測區域的長和寬;L1是區域長度的等分數;L2是區域寬度的等分數;floor(x)表示不大于x的整數。網格坐標一樣的節點視為一組。例如在圖3中，根據式(14)可得每個節點所屬網格的坐標，并給每個網格設置一個編號，分別對應從1到16。

2.3 簇頭選舉及成簇

在每個網格中，先根據每個節點的剩余能量和該節點到數據收集中心的距離來選擇簇頭。簇頭選擇節點競爭半徑較大的。競爭半徑公式為:

其中:b是(0，1)范圍的一個隨機數字，保證結果在一定范圍內;dmax表示該網格內節點與Sink最遠的距離;dmin表示該網格內節點與Sink最近的距離;dbs表示當前節點到Sink的距離;E0表示節點初始能量;Ed表示節點能否傳輸信息的臨界能量;S(i).E表示節點當前所擁有的能量;D表示最大的傳感半徑。競爭半徑考慮了節點的剩余能量以及該節點與Sink的距離兩個方面，競爭半徑大的節點當選簇頭對這個網格內的所有節點是最有利的。

在每個網格中，將該網格中的每個節點計算出來的競爭半徑進行比較，將競爭半徑最大的節點選為簇頭。所有網格內都選出一個簇頭之后，整個網絡中的除簇頭以外的其他節點找到與之距離最近的簇頭，向其發送要加入該簇頭所創建簇的請求，簇頭收到距離它較近的節點發來的加入簇請求之后，要向這些節點發送同意其加入簇的信息。等所有節點都有了歸屬的簇之后，就組成了無線傳感器網絡。

2.4 仿真研究

仿真實驗中，先對WSN和傳感器節點作如下的假設:

1)Sink節點位置固定在區域中央;

2)傳感器節點都是靜止的;

3)傳感器節點不能獲知其自身的位置信息;

4)簇頭融合單位數據消耗的能量相同;

5)網絡中單位面積的區域需要檢測的數據量相同;

6)每個節點的覆蓋面積相同;

7)無線信道對稱。

對基于空間位置的均衡分簇法，并假設傳感器節點均勻分布在監測區域。仿真參數如見表1所示。

表1 仿真相關參數Tab.1 Simulation related parameters

圖4(a)是節點均勻網絡基于位置方法選舉的簇頭和成簇效果，可以看出，通過網格劃分，節點分布密度均勻的網絡簇頭選舉也很均勻。圖4(b)所示為該網絡在300輪時的節點分布和成簇情況，圓點為死亡的節點。可見在網絡運行過程中的成簇仍然是均衡的，每個網格選擇一個投影節點。

基于位置和基于隨機投影節點的兩種方法的剩余節點數的比較如圖5所示。

由圖5可以看出:在網絡開始運行階段，基于位置分簇的效果要差一些，死亡節點出現比較早，剩余節點數較少，但不影響網絡運行;當運行到剩余節點數為80%的時候，基于隨機投影的死亡節點迅速增加，并很快超過了基于位置分簇的死亡節點數，剩余節點數迅速降低:在385輪時剩余節點數由20點瞬間將為0，網絡癱瘓，但此輪時基于位置分簇的網絡仍有近40%的節點存活，網絡仍能運行。以剩余節點數為20點時作為網絡正常運行的臨界點來考慮，低于20點網絡無法聯通，基于位置分簇的網絡比基于隨機投影節點分簇的網絡生存期延長了約35%。

圖5 基于位置和隨機分簇的節點均勻WSN的剩余節點數比較Fig.5 Comparison of remaining nodes of WSN with node even distribution based on location and random clustering

3 基于節點分布密度的均衡分簇法

針對節點分布不均的WSN，每個網格的節點數量多少不等，如果采用第2章的基于位置的分簇法在每個網格選擇一個投影節點，節點少的網格的投影節點能量會很快耗盡，為了適應節點不均的網絡，本文提出基于節點密度的均衡分簇法。

3.1 基于分布密度的均衡分簇

對于節點分布密度不均的WSN，節點數較多的網格組成一個簇之后可以較好地進行節點與節點、節點與簇頭、簇頭與Sink的數據傳輸，還可以使收集同一種信息的部分節點進入休眠，節省能量消耗。而節點數較少的網格形成一個簇之后，簇頭只能在這幾個節點之間輪換，加快了該網格的能量消耗，使這些區域的節點過早地死亡，造成網絡耗能的不均衡。

節點分布密度的衡量通過網格來得到，網格內節點數量少的，說明密度小;反之說明密度大。因此首先進行網格內節點的調整，計算每個網格中的節點的數量。如果網格的節點的數量少于等于p，這些網格中的節點就被歸到節點數量大于p的其他鄰近網格。所有節點數量小于等于p的網格中的節點都歸到指定網格中之后，就形成了一個新的網格劃分格局。這樣，就可以避免節點不均衡的能量消耗，從而提高整個網絡的存活周期。接下來，就可進行簇頭選舉和形成簇。

3.2 仿真分析

仿真實驗中，對WSN和傳感器節點的假設同2.4節。對基于節點分布密度的均衡分簇法，并假設傳感器節點隨機非均勻分布在監測區域。為了研究比較，分別在兩個場景中進行了仿真，具體參數如表2所示。對場景2，監測區域大小為200 m×200 m的空間，部署有400個傳感器節點，傳感器節點的通信半徑D為槡50 2 m，監測區域半徑R相當于為100 m，則根據式(13)得h≈68。為仿真方便可將區域劃分為64個網格。

表2 仿真相關參數(場景1、場景2)Tab.2 Simulation related parameters(scene 1 and scene 2)

下面就用同樣節點布置的網絡來測試基于節點分布密度分簇法和文獻［9］采用隨機投影節點方法的性能。

場景1的基于節點分布密度均衡分簇法的成簇效果如圖6所示。圖6(a)是第一輪成簇的示意圖，可見節點密度小的網格，其節點進行了網格的重新分配，加入到了距離鄰近的簇，不再進行投影節點的選擇。圖6(b)是第300輪時的成簇效果，仍有約60%的節點存活，可見網絡仍然運行良好。

圖7(a)是文獻［9］采用隨機投影節點的方法，它的投影節點是隨機產生的，從中可以看出，投影節點的位置很隨機，形成的簇大小也不均衡。圖7(b)是其300輪時的成簇效果，比圖6(b)的節點數明顯減少，而且邊遠的節點大部分死亡，只有Sink附近的網絡在運行，信息的獲取已經失衡。

圖6 基于密度分簇的節點不均勻分布WSN的成簇特性(場景1)Fig.6 Clustering characteristics of WSN with node uneven distribution based on density clustering(scene 1)

本文方法和隨機投影節點方法的剩余節點數在場景1下的對比如圖8所示。從圖8可以看出，隨機投影節點方法的死亡節點出現比較晚，但節點死亡的速度下降比較快，在剩20個節點的時候驟然癱瘓。而基于節點密度分簇的方法的死亡節點數下降比較緩慢，使得網絡的運行時間增長，而且網絡也沒有突然終止。以剩余20個節點為網絡正常運行狀態的臨界值來考慮，隨機投影方法壽命接近400輪，基于密度分簇的網絡壽命約為550輪，基于密度分簇法的網絡生存期延長了約27%，而且在未癱瘓前，剩余節點數也較隨機投影方法的節點數多約20%，運行狀態優良。

另外由圖8與圖5比較可見，基于隨機投影節點方法在不同節點分布的網絡節點死亡的速度都比較快，在還有約20個存活節點數的時候，都會驟然癱瘓，而本文方法的死亡節點數下降都比較緩慢，網絡可以維持較長的時間。

對于場景2，應用基于密度分簇法和隨機投影節點法對同樣布置的非均勻節點進行分簇?；诠濣c密度分簇法的簇頭分布和成簇效果如圖9所示。同樣可見，節點數少的網格不再選擇投影節點，而是與鄰近網格合并形成一個簇，從而均衡了能耗。

基于密度分簇法和隨機投影節點方法的剩余節點數在場景2下的對比如圖10所示。由圖10可以看出，基于隨機投影節點的方法的剩余節點數隨輪數增加迅速下降，同樣在剩20個節點時驟然為0，網絡停止運行。而本文方法在每輪的剩余節點數都比隨機分簇方法的多，在網絡運行中期，可以達到2倍左右的數量。而在隨機分簇網絡癱瘓后，本文的均衡分簇網絡仍可運行，壽命延長了約25%。

圖8 基于密度和隨機投影節點兩種分簇方法的剩余節點數對比(場景1)Fig.8 Comparison of remaining nodes based on two clustering methods based on density and random projection nodes(scene 1)

從圖5、圖8和圖10中本文方法與基于隨機投影節點方法的比較來看，在整個網絡的正常運行期間，相比隨機投影節點方法，本文方法的剩余節點數明顯較多，網絡運行時間長，運行狀態優良，耗能均衡。

圖9 基于節點密度分簇法的WSN簇頭分布和成簇效果(場景2)Fig.9 Cluster head distribution and clustering effect of WSN based on node density clustering method(scene 2)

圖10 基于密度和隨機投影節點兩種分簇方法的剩余節點數對比(場景2)Fig.10 Comparison of remaining nodes based on two clustering methods based on density and random projection nodes(scene 2)

3.3 均衡投影的壓縮數據收集

基于均衡投影的壓縮數據收集方法的具體實施環節包括以下幾點:

1)根據網絡參數，確定劃分網格的數量，并以此劃分網格。

2)均衡選擇投影節點并建簇。采用基于空間位置或節點密度的均衡分簇法，選擇投影節點，并以投影節點為中心建立一個簇。

3)M×N維測量矩陣的每行非零系數對應的節點統一編為一個號 S(S ∈ {1，2，…，M})。

4)根據CS理論，每個投影節點收集相同編號的節點的加權和并一跳或多跳傳給Sink。若是多跳傳輸，在傳輸過程中將相同編號的數據相加，再傳給Sink。

5)經過M次傳輸，Sink將收集的所有相同編號的數據相加，就可得M個測量值。應用重構算法，就可重構原始數據。

采用均衡分簇法，保證了投影節點的均衡分布，也均衡了網絡的整體能耗。由于采用了稀疏隨機投影矩陣，只需傳送非0節點的加權數據，使得整個網絡的能耗降低;而且，如果測量矩陣的每一列只有一個非0元素，這樣每一行的非0系數的節點互不干擾，就可以同時進行M個測量值的傳送，不必間隔時隙完成，這樣的傳送速度更快，實時性更強。

而且，基于網格的建簇較之一般的分簇方法并沒有增加開銷，由于劃分好了網格，只需要在網格中選擇出投影節點，就可以形成一個簇。由于網格內節點數量有限，所以投影節點的選擇比一般分簇的簇頭的選擇速度要快;而且對基于密度的均衡分簇，當網格內節點數少于某閾值就不需要選擇投影節點了，開銷更為減少。因此，本文建簇的方法更為節能。

4 結語

針對投影節點隨機選擇、位置不均衡的問題，本文提出了基于均衡投影的壓縮數據收集方法，并針對均勻分布節點WSN，提出基于空間位置的均衡分簇法，以大小相同的網格劃分來實現，保證了投影節點的位置均衡;針對不均勻節點分布WSN，提出基于節點密度的均衡分簇法，同時考慮了位置和密度因素，減少了孤立點的能耗，均衡了能量，延長了網絡壽命。通過與隨機投影節點方法的仿真比較，本文方法運行狀態優良，網絡生存期顯著延長。但對于非均勻WSN，按密度分簇的閾值需要根據實際應用中網絡規模、節點整體分布密度和應用需求等綜合因素來選擇，并需要先進行實驗和驗證。