基于廣義逆非負矩陣分解的無線傳感器網(wǎng)絡節(jié)能通信

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

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

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

1 非負矩陣分解

在實際的應用環(huán)境中，傳感器傳輸?shù)男畔⑼哂懈呔S稀疏性，傳輸這些高維稀疏信息消耗大量的傳感器能量。從認知心理學的理論可知，大腦對外界只會處理其中的“有意義”數(shù)據(jù)，而對其他數(shù)據(jù)“視而不見”，即高維信息空間往往可以由低維空間來本質(zhì)表示。因此，建立傳感器的高維數(shù)據(jù)到低維“有意義”數(shù)據(jù)的映射，傳感器僅傳輸降維后的數(shù)據(jù)，將會大大降低通信能耗。

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

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

給定一個m×n的矩陣 X = [ xi,j]m×n∈Rm×n代表m個變量n個特征值。NMF的目標是找到2個非負矩陣和最小化目標函數(shù)Ω。Ω是D(U||V)的損失函數(shù)，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個矩陣有且僅只有一個具有凸特性，因此，很難設計一個使目標函數(shù)全局最小的算法。Lee和Seung[10]證明利用式(2)和(3)可以使目標函數(shù)局部最小。

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

2 廣義逆非負矩陣分解的通信數(shù)據(jù)壓縮算法

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

2.1 廣義逆矩陣構建

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

其中：X*為X的共軛轉(zhuǎn)置矩陣。

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

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

2.2 特征空間變換

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

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

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

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

2.3 廣義逆非負矩陣分解的通信數(shù)據(jù)壓縮算法

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

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

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

輸入：原始通信數(shù)據(jù)矩陣X ∈ Rm×n

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

// 奇異值分解操作

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

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

// NMF降維操作

Step 5：當誤差約束條件或者時間約束條件滿足時，算法終止；否則，循環(huán)執(zhí)行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直到循環(huán)條件滿足，這2步是NMF降維算法，由于經(jīng)過廣義逆分解，所以 NMF降維的規(guī)模大大降低，采用乘法更新法則可以很快求解出最終的降維結果。giNMF算法的時間復雜度為O(Nr2)，空間復雜度為O(Nr)。

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

3 仿真實驗

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

圖2 數(shù)據(jù)壓縮工作原理Fig. 2 Operating principle of data compression

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

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

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

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

3.1 降維效果分析

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

3.2 通信能耗分析

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

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

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

3.3 網(wǎng)絡生命周期分析

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

圖5 網(wǎng)絡生命周期對比實驗Fig. 5 Comparison on network lifetime

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

4 結論

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

(2) 分別從降維效果、通信能耗、網(wǎng)絡生命周期3個角度進行對比分析。仿真實驗結果表明：giNMF算法能夠?qū)νㄐ艛?shù)據(jù)進行有效壓縮，從而降低通信能耗，延長網(wǎng)絡生命周期，達到節(jié)能的目的。

[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.