基于廣義逆非負矩陣分解的無線傳感器網絡節能通信

仵博1, 2, 3，吳敏1, 2

(1.中南大學 信息科學與工程學院，湖南 長沙 410083；2. 先進控制與智能自動化湖南省工程實驗室，湖南 長沙，410083；3. 深圳職業技術學院 教育技術與信息中心，廣東 深圳，518055)

無線傳感器網絡(WSN)是由隨機分布的集成有傳感器、數據處理單元和通信單元的微小節點通過自組織方式構成的無線網絡。WSN具有廉價性、自組織性、動態性和高容錯性等優點，在軍事領域、醫療保健、環境監控和減災救災等領域得到廣泛應用[1]。WSN傳感器節點能量通常由電池供給，且難以及時補充。因此，如何高效使用能量來最大化網絡生命周期是傳感器網絡面臨的重大挑戰[2]。WSN能量消耗主要用于傳感器感知、通信和數據處理。研究表明：傳感器節點的能量消耗主要集中在通信上，傳感器結點通信所消耗的能量占整個傳感器生命周期內能量的 80%以上。因此，有效降低傳感器節點通信能量消耗是最大化 WSN生命周期的關鍵。通信能耗主要發生在傳感器接收、發送和空閑3種狀態下，通信能耗降低方法主要3類。一類是對WSN通信協議的改進來降低通信能耗[3-5]，延長WSN的生命周期。但是，該類算法缺乏泛化能力，局限于特定的應用。一類算法是根據傳感器所處環境的特征，采用部分可觀察馬爾可夫決策過程(POMDP)建模能量消耗與服務質量[6-7]，從而實現能耗與網絡性能的優化平衡。但是，該算法針對POMDP近似最優值求解存在“維數災”問題，只能針對小規模 WSN系統，在大規模或者連續狀態下，算法無法實現實時收斂。一類算法通過是壓縮原始高維通信數據空間到低維空間，從而實現降低傳輸能耗的目的[8-9]，該類算法具有模型無關性，泛化能力較強。但是，現有算法降維過程復雜，實時性不高。針對目前算法的優缺點，本文提出一種基于廣義逆非負矩陣分解(giNMF)的無線傳感器網絡能量高效通信算法。在采用非負矩陣分解(NMF)降維之前，先采用廣義逆分解技術(本文采用奇異值分解(SVD))對原始通信數據矩陣進行初始化操作，從而避免 NMF隨機初始化帶來的矩陣分解不確定性問題，然后，采用 NMF對奇異值分解后的特征空間進行降維。

1 非負矩陣分解

在實際的應用環境中，傳感器傳輸的信息往往具有高維稀疏性，傳輸這些高維稀疏信息消耗大量的傳感器能量。從認知心理學的理論可知，大腦對外界只會處理其中的“有意義”數據，而對其他數據“視而不見”，即高維信息空間往往可以由低維空間來本質表示。因此，建立傳感器的高維數據到低維“有意義”數據的映射，傳感器僅傳輸降維后的數據，將會大大降低通信能耗。

非負矩陣分解方法[10]是將原高維矩陣分解成為 2個低維非負矩陣的積，其原理如圖1所示。

圖1 非負矩陣分解原理示意圖Fig. 1 diagram of nonnegative matrix factorization

給定一個m×n的矩陣 X = [ xi,j]m×n∈Rm×n代表m個變量n個特征值。NMF的目標是找到2個非負矩陣和最小化目標函數Ω。Ω是D(U||V)的損失函數，D為Kullback-Leibler(KL)散度，r＜＜m，r＜＜n，U＞0，V＞0。

其中： Y = [ y ]= U · VT，如果X=Y，D(U||V)為0。i, j由于 U和 V 2個矩陣有且僅只有一個具有凸特性，因此，很難設計一個使目標函數全局最小的算法。Lee和Seung[10]證明利用式(2)和(3)可以使目標函數局部最小。

非負矩陣分解是處理高維數據集的重要方法，并在模式識別、信號處理、數據聚類和計算機安全等方面得到應用[11]。但是，非負矩陣分解還有一些缺點：(1) 對于大規模數據，計算NMF十分耗時，造成它無法在實時系統中應用[12]；(2) 特征空間 r的維數無法預測，因此尋找一個最優的 r比較困難；(3) 無法求解全局最優，分解因子U和V的初始化是隨機的，造成每次分解的結果不確定。

2 廣義逆非負矩陣分解的通信數據壓縮算法

基于非負矩陣分解存在的問題，利用廣義逆的快速轉換特性[11,13]，提出一種基于廣義逆非負矩陣分解算法，并將該算法應用于無線傳感器網絡傳輸信息壓縮，實現能量高效通信。

2.1 廣義逆矩陣構建

定義1[13]對于有限維矩陣X，Penrose定義存在一個唯一的廣義逆矩陣?X 同時滿足：

其中：X*為X的共軛轉置矩陣。

定義2[13]令X∈Rm×n，存在2個正交矩陣U∈Rm×n和 V∈Rm×n，奇異值分解如下：

其中：Σ∈ Rm×n為對角矩陣：

2.2 特征空間變換

根據NMF分解原理可知， Xm×n= Um×r·Vr×n，其中，U為權重矩陣，V為基矩陣，特征空間變換過程為式(11)～(13)。

將式(11)兩邊同時乘以V的廣義逆矩陣?V ：

如果V的每行都是線性獨立的，則，?≈VVI，I為單位矩陣，式(12)可變換為：

通過以上變換步驟，可以很快地將原始輸入矩陣變換為權重特征空間。

2.3 廣義逆非負矩陣分解的通信數據壓縮算法

算法思想：首先對通信數據矩陣X進行廣義逆分解，初始化X，快速得到X的特征空間，然后，根據誤差約束條件或者時間約束條件，對廣義逆分解后的X進行 NMF降維，從而實現對原始通信數據的有效快速降維。

定義3 在KL散度函數中，需要評估X和UV之間的誤差，假設每步迭代導致一個ε誤差，這個誤差增加X和UV之間的距離，那么積累到步n時的誤差為：

算法 1：廣義逆非負矩陣分解的通信數據壓縮算法(giNMF)

輸入：原始通信數據矩陣X ∈ Rm×n

輸出：U∈Rm×n和V ∈ Rm×n

// 奇異值分解操作

Step 1：采用廣義逆奇異值分解方法，將X進行分解；

step 2：取X的前r個較大的奇異值σi及其對應的特征空間ui；

// NMF降維操作

Step 5：當誤差約束條件或者時間約束條件滿足時，算法終止；否則，循環執行Step 3和Step 4；

Step 6：輸出降維后的U和V。

由于在NMF降維算法中，分解因子U和V的初始化是隨機的，造成每次分解的結果不確定，有時甚至得到不正確或者不相關的分解結果。NMF算法的時間復雜度為 O(MNr)，空間復雜度為 O(MN)。giNMF算法采用廣義逆分解(算法Step 1和Step 2)，很快得到原始矩陣的特征空間，避免迭代求解分解因子操作。Step 3和Step 4計算極小值的U和V直到循環條件滿足，這2步是NMF降維算法，由于經過廣義逆分解，所以 NMF降維的規模大大降低，采用乘法更新法則可以很快求解出最終的降維結果。giNMF算法的時間復雜度為O(Nr2)，空間復雜度為O(Nr)。

算法giNMF具有通信模式無關性，無論是單跳還是多跳，對giNMF算法并無影響。因此，giNMF算法對通信數據降維具有較強的泛化能力，可以應用到任何模式、任何節點的通信數據傳輸中。

3 仿真實驗

本文的實驗對象為傳感器采集、發送和接收環境溫濕度的信息，傳感器采用Crossbow MICA2 Mote，拓撲結構為單跳模式。為降低能耗，傳感器往往采用采集多條信息集中發送方式，工作原理如圖2所示。

圖2 數據壓縮工作原理Fig. 2 Operating principle of data compression

傳輸N個M位長的包，通信總能耗為數據采集階段能耗、數據壓縮階段能耗、數據發送階段能耗與數據接收階段能耗之和。

根據文獻[14]可知，數據采集階段能耗Ea和數據壓縮階段能耗Ec遠遠小于發送和接收能耗，因此，在本文忽略 Ea和 Ec，只考慮 Es和 Er。根據文獻[15]，Es和Er計算如下：

其中，d為結點傳感器與簇首傳感器之間的距離。

本文分別從 3個角度進行實驗分析：(1) 與文獻[12]的lraNMF算法進行對比分析，比較giNMF算法的降維效果和耗時；(2) giNMF算法與LEACH算法的通信能耗對比分析；(3) giNMF算法與LEACH算法的網絡生命周期的對比分析。

3.1 降維效果分析

降維效果比較如圖3所示。根據圖3可見：本文giNMF降維算法比 lraNMF降維算法具有較高的效率，針對KL散度的收斂速度，giNMF算法更快。對于相同的KL散度，giNMF算法降到的維數最小；而對于相同的降維維數，KL散度最小，也即誤差最小。

3.2 通信能耗分析

假設接收和發送單位(bit)能耗為50 nJ/bit，傳輸數據矩陣M=2 000 bits，N=50。圖4所示為giNMF算法與LEACH算法的通信能耗對比實驗。從圖4可見：giNMF算法能耗要低于LEACH算法，LEACH算法平均通信能耗是 giNMF算法 2倍以上。從而得出giNMF降維算法能夠有效降低通信數據規模，去除通信數據的白噪聲，實現節能的目的。

圖3 降維效果比較Fig. 3 Comparison on compression effectiveness

圖4 通信能耗對比實驗Fig. 4 Comparison on communication energy consumption

3.3 網絡生命周期分析

模擬實驗環境為一個100 m×100 m的區域，監控環境的溫濕度信息，傳感器節點數量N=100，傳感器節點與簇首之間采用單跳通信，傳感器節點的白噪音服從高斯分布 N(0，2.25)，每個傳感器結點的初始值為0.5 J，比較對象為文獻[15]中的LEACH算法。評價無線傳感器網絡溫濕度監控系統的重要指標是系統生命周期，生命周期越長，系統越好。從圖5可見：采用giNMF算法的系統生命周期比LEACH算法的系統生命周期要提高50%左右。

圖5 網絡生命周期對比實驗Fig. 5 Comparison on network lifetime

圖5所示為giNMF算法和LEACH算法的網絡生存時間進行比較，圖5顯示了網絡中存活節點的變化情況，隨著死亡節點數目增多，節點死亡速度均出現加快的趨勢。LEACH算法最早出現死亡節點，giNMF約在1 000輪出現第1個死亡節點。LEACH算法在1 300輪左右網絡節點全部死亡，giNMF在1 800輪左右節點全部死亡，本文算法網絡生命周期最長。比較結果表明：本文算法能夠有效地延長網絡生存時間。

4 結論

(1) 提出一種基于廣義逆非負矩陣分解的無線傳感器網絡節能通信算法，有效降低通信數據量，從而實現能耗降低。該算法特點是：具有較強的泛化能力，具備通信協議無關性，因此，具有廣泛的應用范圍；高維數據壓縮準確、誤差低，壓縮后的數據能夠真實描述原始狀態，具備降維不失真性。

(2) 分別從降維效果、通信能耗、網絡生命周期3個角度進行對比分析。仿真實驗結果表明：giNMF算法能夠對通信數據進行有效壓縮，從而降低通信能耗，延長網絡生命周期，達到節能的目的。

[1] Mottola L, Picco G P. Programming wireless sensor networks:fundamental concepts and state of the art[J]. ACM Computing Surveys, 2011, 43(3): 19-24.

[2] Srivastava N. Challenges of next-generation wireless sensor networks and its impact on society[J]. Journal of Telecommunication, 2010, 1(1): 128-133.

[3] Keeler H P, Taylor P G. A model framework for greedy routing in a sensor network with a stochastic power scheme[J]. ACM Transactions on Sensor Networks, 2011, 7(4): 34-37.

[4] Veeravalli V V, Varshney P K. Distributed inference in wireless sensor networks[J]. Philosophical transactions of the Royal Society A, 2012, 370(1958): 100-117.

[5] WANG Tian, WANG Guojun, GUO Minyi, et al.Hash-area-based data dissemination protocol in wireless sensor networks[J]. J Cent South Univ Technol, 2008, 15(3): 392-398.

[6] Fuemmeler J A, Atia G, Veeravalli V V. Sleep control for tracking in sensor networks[J]. IEEE Transactions on Signal Processing, 2011, 59(9): 4354-4366.

[7] Han J A, Jeon W S, Jeong D G. Energy-efficient channel management scheme for cognitive radio sensor networks[J].IEEE Transactions on Vehicular Technology, 2011, 60(4):1905-1910.

[8] Varshney K R, Willsky A S. Linear dimensionality reduction for margin-based classification: High-dimensional data and sensor networks[J]. IEEE Transactions on Signal Processing, 2011,59(6): 2496-2512.

[9] Hu W Z, Hao Y, Huang L. Multidimensional data reduction based on compressed sensing for sensor network[M]//Zhang Y.Future Wireless Networks and Information Systems. Heidelberg:Springer, 2012: 721-728.

[10] Lee D D, Seung H S. Learning the parts of objects by non-negative matrix factorization[J]. Nature, 1999, 401:788-791.

[11] Kromer P, Platos J, Snasel V. Fast dimension reduction based on NMF[C]//Proceedings of the 5th International Conference on Advances in Computation and Intelligence. Heidelberg: Springer,2010: 424-433.

[12] Zhou G, Cichocki A, Xie S. Fast nonnegative matrix/tensor factorization based on low-rank approximation[J]. IEEE Transactions on Signal Processing, 2012, 60(6): 2928-2940.

[13] Ben I A, Greville T N E. Generalized inverses: theory and applications[M]. Heidelberg: Springer, 2003: 182-224.

[14] Wang A Y. Low Power RF Transceiver Modeling and Design for Wireless Sensors Network[D]. Boston: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science, 2005: 55-77.

[15] Heinzelman W R, Chandrakasan A, Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Hawaii:IEEE Press, 2000: 3005-3014.