無線傳感器網絡下線性支持向量機分布式協同訓練方法研究

及歆榮侯翠琴侯義斌*

①(北京工業大學嵌入式軟件與系統研究所 北京 100124)

②(河北工程大學信息與電氣工程學院 邯鄲 056038)

無線傳感器網絡下線性支持向量機分布式協同訓練方法研究

及歆榮①②侯翠琴①侯義斌*①

①(北京工業大學嵌入式軟件與系統研究所 北京 100124)

②(河北工程大學信息與電氣工程學院 邯鄲 056038)

針對無線傳感器網絡中分散在各節點上的訓練數據傳輸到數據融合中心集中訓練支持向量機(Support Vector Machine, SVM)時存在的高通信代價和高能量消耗問題，該文研究了僅依靠相鄰節點間的相互協作，在網內分布式協同訓練線性SVM的方法。首先，在各節點分類器決策變量與集中式分類器決策變量相一致的約束下，對集中式SVM訓練問題進行等價分解，然后利用增廣拉格朗日乘子法，對分解后的SVM問題進行求解和推導，進而提出基于全局平均一致性的線性SVM分布式訓練算法(Average Consensus based Distributed Supported Vector Machine, AC-DSVM)；為了降低AC-DSVM算法中全局平均一致性的通信開銷，利用相鄰節點間的局部平均一致性近似全局平均一致性，提出基于一次全局平均一致性的線性SVM分布式訓練算法(Once Average Consensus based Distributed Supported Vector Machine, 1-AC-DSVM)。仿真實驗結果表明，與已有算法相比，AC-DSVM算法的迭代次數和數據傳輸量略高，但其能夠完全收斂到集中式訓練結果；1-AC-DSVM算法具有較好的收斂性，而且在收斂速度和數據傳輸量上也表現出顯著優勢。

無線傳感器網絡；支持向量機；分布式學習；增廣拉格朗日乘子法；平均一致性

1 引言

在無線傳感器網絡(Wireless Sensor Network,WSN)的眾多應用中，對監測到的信息進行分類是最重要也是最基礎的一項任務[1,2]。支持向量機(Support Vector Machine, SVM)作為一款性能非常出色的分類器，因其堅實的理論基礎和良好的分類效果，在WSN中得到了越來越廣泛的應用[3-5]。然而，在WSN中，SVM的訓練數據都分散在各個傳感器節點上，僅依靠單個節點上的數據訓練效果較差；而通過多跳路由將所有訓練數據傳輸到數據融合中心進行集中式訓練，需要占用大量的帶寬、消耗大量的能量，這與WSN節點上能源替換代價非常高甚至不可替換、帶寬資源非常有限相沖突，同時也容易使數據中心周圍的節點成為整個系統的瓶頸。針對上述問題，通過相鄰節點間的相互協作，在網內分布式協同訓練SVM的方法研究，近年來引起越來越多研究者的關注。

在SVM分布式協同訓練的相關研究中，專門針對WSN的特性提出訓練SVM的算法比較少。其中，文獻[6,7]針對WSN的特性，提出了以在相鄰節點間傳輸支持向量的協作方式，每個節點使用局部訓練樣本和從鄰居節點發送過來的支持向量進行增量訓練，將全部節點訓練完后得到的支持向量集合作為集中式訓練結果的近似。由于該算法對每個節點的增量訓練只進行一次，所以訓練結果收斂性差，而且當支持向量規模很大時，通信代價仍然會很大。文獻[8,9]提出了基于一致性約束的分布式線性SVM的訓練算法MoM-DSVM，該算法在相鄰節點決策變量相等的約束下，利用并行優化技術，以在相鄰節點間傳遞少量決策結果的方式，經過多次迭代來實現各節點訓練結果的一致。由于僅依靠相鄰節點間的一致性約束，該算法存在收斂速度慢和收斂性差等缺點。此外，為了解決SVM在大規模數據或分布式數據上的訓練問題，學者們提出了許多并行或分布式訓練SVM的算法[10-12]，但這些算法沒有考慮WSN資源受限的特性，不適于WSN應用。

針對已有研究中存在的通信代價高、收斂性差和收斂速度慢等問題，本文致力于研究在不依賴數據融合中心的WSN中，僅依靠相鄰節點間的相互協作，在各節點分類器決策變量與集中式分類器決策變量相一致的約束下，利用分布式優化方法，對分布式訓練線性SVM的問題進行求解和推導。基于此，提出了基于平均一致性的分布式線性SVM訓練算法AC-DSVM和改進算法1-AC-DSVM(once Average Consensus based Distributed SVM)。仿真實驗從收斂性、收斂速度和通信代價3個方面對提出的兩個算法進行實驗驗證，并與已有算法進行對比分析。

2 分布式線性SVM協同訓練

2.1 問題描述

考慮一個由J個節點構成的WSN。為了清楚表達WSN節點間的相鄰關系，使用無向圖G={V,E}對其進行表示，其中，V表示WSN中J個節點的集合，E代表相鄰節點間邊的集合，節點J的所有鄰居節點用集合Bj表示。此外，假定圖G是連通的，即圖中的任意兩個節點之間至少存在一條路徑，也就是圖中不存在孤立節點。為了方便表述節點上的訓練樣本，每個節點j∈J上的訓練樣本都用一個訓練樣本集Sj:={(xjn,yjn):n=1,2,???,Nj}來表示，其中xjn∈Rp是訓練樣本的特征向量，p是特征向量維數，yjn∈Y:={-1,1}是訓練樣本對應的分類標簽，Nj是訓練樣本的數量。本文針對線性SVM訓練的問題，研究在WSN下，僅依賴相鄰節點間的相互協作，在網內分布式協同訓練SVM的方法。

2.2 線性SVM訓練問題的分解和推導

SVM的訓練問題可以歸結為求解一個受約束的凸二次規劃問題[13]。在WSN中，訓練樣本都分散在各個傳感器節點上，而且不同傳感器節點上的訓練樣本個數有可能不同。因此，本研究采用了文獻[14]中給出的與訓練樣本數量相關的二次規劃問題形式。線性SVM問題使用此形式的表示如式(1)：

在式(1)中，W和b分別表示要求解的最優分類超平面的權向量和閾值。ix和iy對應的是第i個訓練樣本的特征向量和類別標簽。iξ和C分別表示松弛變量和懲罰因子，是對個別離群點訓練樣本進行間隔放松和施加懲罰，iξ是一個未知量，而 C是一個給定值。N表示訓練樣本的個數。

假定分散在各個傳感器節點上的訓練樣本都可以集中起來進行SVM訓練，此時，線性SVM訓練問題對應的凸二次規劃問題形式如式(2)：

式(2)是由J組分散的訓練樣本構成的集中式訓練對應的凸二次規劃問題形式，和同樣訓練樣本條件下不分組情況下的表示形式式(1)是完全一致的。為了有利于SVM訓練在各節點上進行，將式(2)變換為等價的易于分解的形式[15]，如式(3)：

其中，W*和b*是式(2)中集中式訓練時要求解的權向量和閾值，而Wj和bj是節點j上要求解的權向量和閾值。式(2)和式(3)的等價是通過等式約束Wj=W*, bj=b*來保證的。式(3)的分解形式對應到每個節點j上，即每個節點j上求解的二次規劃問題形式，如式(4)：

為求解在每個節點上如式(4)的優化問題，利用增廣拉格朗日方法對等式約束Wj=W*(因為bj或b*的結果是由Wj和W*計算得到的)構建增廣拉格朗日函數[16,17]，如式(5)：

其中，由Wj-W*構成的二次項是增廣拉格朗日方法中用以保證原目標函數的嚴格凸性[15]。pj(t )是等式約束Wj=W*上的拉格朗日乘子系數，c(t)是一個大于零的常數。對式(5)問題的求解，使用乘子方法[15,16]，該方法采用乘子pj(t+1)的迭代形式，如式(6)所示。其中，W*(t+1)是集中式訓練結果的權向量，是一個公共的耦合變量，即在每個節點j上都存在該變量，為此，我們基于當變量Wj(t +1)的值越接近W*(t+1)時pj(t +1)的結果應該趨近0的事實，利用pj(t+1)的迭代形式，對各節點得到的局部結果Wj(t), pj(t)求平均來得到W*(t+1)的迭代形式，如式(7)所示。當W*(t+1)的值確定后，各個節點就可以對式(5)的優化問題進行求解，從而求出Wj(t+1)，如式(8)所示。這樣，對于式(5)問題的求解可以根據式(6)-式(8)的迭代形式進行求解。

其中，式(8)中Wj∈Pj,Pj表示式(5)中的約束條件；各個節點上對Wj(t +1)的求解，利用拉格朗日對偶理論[13]，構建拉格朗日函數，如式(9)：

其中，jnλ和jnμ為拉格朗日乘子，對偶問題形式如式(10)所示。

在式(11)中， Aj=YjXj,Yj是節點j上的所有訓練樣本的標簽列向量，而Xj是對應的所有訓練樣本的特征向量構成的特征矩陣；uj=(1+c(t ))Ip+1, Ip+1是+1p維的單位矩陣。jλ是由該節點上所有訓練樣本的jnλ構成的列向量，是未知的。將式(11)，式(12)，式(13)的結果代入式(10)的目標函數中，可以得到如式(14)所示的目標函數：

這樣，式(10)中的對偶問題可以簡化為：

在式(15)的優化問題中，因只含有一個列變量λj，可以利用傳統的二次規劃問題進行求解。當求解得到λj后，利用式(11)，就可以求出每個節點上的Wj(t+1)。至此，WSN中線性SVM分布式協同訓練問題可以按照式(7)、式(15)、式(11)、式(6)的順序進行迭代求解。

2.3 分布式線性SVM協同訓練算法

上述線性SVM訓練的推導形式式(7)中，公共變量W*(t+1)需要計算所有節點得到的局部訓練結果Wj(t )和pj(t )的平均值，即各節點進行一次局部訓練后就需要對訓練結果Wj(t )和pj(t)進行一次全局平均(簡稱“平均一致性”)。因每次迭代都是基于平均一致性來進行訓練，所以可以保證各節點能夠收斂到比較優的訓練結果，而且也可以加快各節點的局部收斂速度。為此，提出了基于平均一致性的分布式線性SVM訓練算法(Average Consensus based Distributed Supported Vector Machine, AC-DSVM )，具體描述如表1所示。

在AC-DSVM算法中，每迭代一次就要進行一次平均一致性的計算。然而，在WSN無數據融合中心或特殊節點的情況下，只依靠相鄰節點間的協作來實現全局平均一致性，會大大增加網絡的通信開銷。為了使AC-DSVM算法的思想能在無數據融合中心的WSN中有效應用，降低節點間通信代價，對其進行了改進。將AC-DSVM算法中的平均一致性思想應用在相鄰節點間，即在鄰居節點間進行訓練結果的局部平均一致性，以此作為對全局平均一致性的近似，進行各節點的局部訓練，直到各個節點的訓練結果局部收斂。然后通過一次全局的平均一致性計算，得到最優訓練結果的近似解。基于此想法，提出了基于一次平均一致性的分布式線性SVM訓練算法(Once Average Consensus based Distributed Supported Vector Machine, 1-ACDSVM)，具體描述如表2所示。

表1 AC-DSVM算法

表2 1-AC-DSVM算法

在上述兩個算法中，都需要求全局平均一致性。但是，在WSN中僅通過相鄰節點間的相互協作對各節點上數據求平均一致性，至今還沒有成熟統一的方法[17,18]。為此，本研究使用最簡單的洪泛方法[17]來實現全局平均一致性，其思想是各節點將自己的訓練結果和其鄰居節點傳遞過來的最新訓練結果保存到本地，并將新接收到的訓練結果轉發給其它鄰居節點，在經過與網絡結構相關的固定迭代次數后，各節點可以得到網絡中其它所有節點的數據，從而求得全局平均一致。

3 實驗及結果分析

本文以一個由30個節點構成的WSN網絡為例，使用模擬數據和UCI數據集進行了實驗。以集中式C-SVM訓練結果為基準，對AC-DSVM算法，1-AC-DSVM算法和文獻[8]中的MoM-DSVM算法從訓練結果收斂性、收斂速度和數據傳輸量3個方面進行了對比實驗。

3.1 模擬數據實驗

在實驗中使用的模擬數據是由2維隨機向量(X,Y)服從N(2,2,5,5,0)和N(22,2,5,5,0)隨機產生的兩類訓練樣本數據，每類訓練樣本個數均為600。將生成的訓練數據平均分配給WSN中的30個節點進行訓練。同時，為了研究不同網絡結構對算法訓練結果的影響，使用了鏈狀結構和連通度為0.0896的網絡結構進行了實驗。

3.1.1 訓練結果收斂性 從圖1和表3顯示的訓練結果可以看出，AC-DSVM算法和1-AC-DSVM算法得到最優決策分類線能夠很好地與集中式C-SVM算法的訓練結果相吻合，尤其是AC-DSVM算法的訓練結果和集中式C-SVM算法的訓練結果完全吻合；而MoM-DSVM算法得到最優決策分類線與集中式算法C-SVM的訓練結果吻合得不好，尤其是閾值b差異明顯。從表3還可以看出，不同網絡結構對算法AC-DSVM和1-AC-DSVM的訓練結果的收斂性影響不明顯，而對MoM-DSVM算法的收斂性略有影響。

表3 4種訓練算法得到的最優分類決策線的權向量和閾值

3.1.2 收斂速度 從圖2顯示的結果可以看出，兩種不同網絡結構下，算法AC-DSVM, 1-AC-DSVM和MoM-DSVM在網狀結構下收斂迭代次數，分別比鏈狀結構下收斂迭代次數少41.2%, 25.5%和52.6%。表明網絡結構對3種算法的收斂速度影響很明顯，網狀結構比鏈狀結構收斂快；從圖2還可以看出，在鏈狀結構下，AC-DSVM算法比MoM-DSVM的收斂迭代次數多33.7%; 1-AC-DSVM算法分別比AC-DSVM和MoM-DSVM的收斂迭代次數少89.2%和82.1%。在網狀結構下，AC-DSVM算法比MoM-DSVM的收斂迭代次數多65.6%; 1-ACDSVM算法分別比AC-DSVM和MoM- DSVM的收斂迭代次數少91.5%和88.6%。表明在兩種網絡結構下，AC-DSVM算法在收斂速度上明顯慢于MoM-DSVM算法，而1-AC-DSVM算法在收斂速度上要明顯快于算法AC-DSVM和MoM-DSVM。

3.1.3 數據傳輸量 從圖3顯示的結果可以看出，兩種不同網絡結構下，算法AC-DSVM和1-ACDSVM在網狀結構下數據傳輸量，分別比鏈狀結構下數據傳輸量多3.4%和2.6%，而算法MoM-DSVM在網狀結構下數據傳輸量比鏈狀結構下數據傳輸量少52.6%。表明算法AC-DSVM和1-AC-DSVM在數據傳輸量上受網絡結構影響不明顯，而算法MoM-DSVM在數據傳輸量上受網絡結構影響明顯；從圖3還可以看出，在鏈狀結構下，AC-DSVM算法比MoM-DSVM的數據傳輸量多70.2%，算法1-AC-DSVM分別比AC-DSVM和MoM-DSVM的數據傳輸量少92%和86.4%；在網狀結構下，ACDSVM算法比MoM-DSVM的數據傳輸量多271%，算法1-AC-DSVM分別比AC-DSVM和MoMDSVM的數據傳輸量少92.1%和70.8%。表明在兩種網絡結構下，AC-DSVM算法在數據傳輸量上明顯高于MoM-DSVM算法， 而1-AC-DSVM算法在數據傳輸量上明顯低于算法AC-DSVM和MoMDSVM。

3.2 UCI數據集實驗

為了驗證算法AC-DSVM和1-AC-DSVM對實際訓練樣本數據的有效性，使用UCI數據庫中的Wine數據集進行實驗。因Wine數據集的樣本數據是13維的高維數據，訓練得到的最優分類超平面不易平面表現，所以本實驗只對13維權向量的分量及閾值的收斂過程和收斂結果進行顯示。本文選取了13維權向量的分量w1, w3, w5和閾值b在算法AC-DSVM, 1-AC-DSVM, C-SVM和MoM-DSVM下的收斂過程和收斂結果進行顯示，如圖4(a)-4(d)。從圖4中各子圖的顯示結果可以看出，算法AC- DSVM和1-AC-DSVM可以近似收斂到集中式的訓練結果，算法AC-DSVM收斂過程中呈現的階梯狀收斂趨勢的水平方向和算法1-AC-DSVM收斂過程中最后的直接跳變反映了平均一致性算法的運行；從圖4中各子圖的顯示結果還可以看出，與算法MoM-DSVM相比， 算法AC-DSVM的收斂速度稍慢，而算法1-AC-DSVM明顯快于算法ACDSVM和MoM-DSVM。

4 結束語

圖1 兩類訓練樣本和4種訓練算法得到的最優分類決策線

圖2 兩種網絡結構下3種 算法的迭代次數

圖3 兩種網絡結構下3種 算法的數據傳輸量

圖4 Wine數據集下4種算法的收斂過程和收斂結果

本文在各節點局部分類器決策變量與集中式決策變量相一致的約束下，利用分布式優化方法，研究了僅依靠相鄰節點間的相互協作，在網內分布式協同訓練線性SVM的方法，提出了基于平均一致性的分布式線性SVM訓練算法AC-DSVM和改進算法1-AC-DSVM。仿真實驗結果表明：與算法MoM-DSVM相比，AC-DSVM算法雖然在收斂速度和數據傳輸量方面較差，但其可以準確地收斂到集中式訓練結果；1-AC-DSVM算法具有較好收斂性，而且在收斂速度和數據傳輸量上也表現出了顯著優勢。此外，不同網絡結構對兩個算法在收斂性和數據傳輸量上的影響不明顯，對收斂速度影響較明顯。1-AC-DSVM算法因其良好的性能為WSN下SVM分布式協同訓練提供了一種非常有效的方法。由于SVM的優勢在于解決非線性問題，因此筆者進一步的研究工作是將提出的算法擴展到非線性問題的求解上。

[1] 呂方旭, 張金成, 郭相科, 等. 基于WSN的戰場聲目標多特征聯合智能分類識別[J]. 科學技術與工程, 2013, 13(35): 10713-10721.

Lü Fang-xu, Zhang Jin-cheng, Guo Xiang-ke, et al.. The acoustic target in battlefield intelligent classification and identification with multi-features in WSN[J]. Science Technology and Engineering, 2013, 13(35): 10713-10721.

[2] Taghvaeeyan S and Rajamani R. Portable roadside sensors for vehicle counting, classification, and speed measurement[J]. IEEE Transactions on Intelligent Transportation Systems, 2014, 15(1): 73-83.

[3] Shahid N, Naqvi I H, and Bin Qaisar S B. Quarter-sphere SVM: attribute and spatio-temporal correlations based outlier & event detection in wireless sensor networks[C]. IEEE Wireless Communication and Networking Conference: Mobile and Wireless Networks, Paris, 2012: 2048-2053.

[4] 劉倩, 崔晨, 周杭霞. 改進型SVM多類分類算法在無線傳感器網絡中的應用[J]. 中國計量學院學報, 2013, 24(3): 298-303.

Liu Qian, Cui Chen, and Zhou Hang-xia. Application of a modified SVM multi-class classification algorithm in wireless sensor networks[J]. Journal of China University of Metrology, 2013, 24(3): 298-303.

[5] Raj A B, Ramesh M V, Kulkarni R V, et al.. Security enhancement in wireless sensor networks using machine learning[C]. IEEE 14th International Conference on High Performance Computing and Communications, Liverpool, 2012: 1264-1269.

[6] Flouri K, Beferull-Lozano B, and Tsakalides P. Optimal gossip algorithm for distributed consensus SVM training in wireless sensor networks[C]. Proceedings of the 16th International Conference on Digital Signal Processing (DSP′09), Heraklion, 2009: 886-891.

[7] Flouri K, Beferull-Lozano B, and Tsakalides P. Training a support-vector machine-based classifier in distributed sensor networks[C]. Proceedings of 14th European Signal Processing Conference, Florence, 2006: 1-5.

[8] Forero P A, Cano A, and Giannakis G B. Consensus-based distributed linear support vector machines[C]. Proceedings of the International Conference on Information Processing in Sensor Networks, Stockholm, 2010: 35-46.

[9] Forero P A, Cano A, and Giannakis G B. Consensus-based distributed support vector machines[J]. Journal of Machine Learning Research, 2010, 11(May): 1663-1707.

[10] Lu Y, Roychowdhury V, and Vandenberghe L. Distributed parallel support vector machines in strongly connected networks[J]. IEEE Transactions on Neural Networks, 2008, 19(7): 1167-1178.

[11] Wang Dong-li, Li Jian-xun, and Zhou Yan. Support vector machine for distributed classification: a dynamic consensus approach[C]. IEEE/SP 15th Workshop on Statistical Signal Processing, Wales, 2009: 753-756.

[12] Kim Woo-jin, Yoo Jae-hyun, and Kim H J. Multi-target tracking using distributed SVM training over wireless sensor networks[C]. IEEE International Conference on Robotics and Automation, Saint Paul, 2012: 2439-2444.

[13] Shawe T J and Cristianini N. An Introduction to Support Vector Machines and Other Kernel-based Learning Methods [M]. New York: Cambridge University Press, 2000: 121-130.

[14] Scholkopf B and Smola A J. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond [M]. New York: The MIT Press, 2002: 204-205.

[15] Bertsekas D P and Tsitsiklis J N. Parallel and Distributed Computation: Numerical Methods[M]. Massachusetts: Athena Scientific, 1997: 243-247.

[16] Boyd S, Parikh N, and Chu E. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends in Machine Learning, 2011, 3(1): 1-122.

[17] Sardellitti S, Giona M, and Barbarossa S. Fast distributed average consensus algorithms based on advection-diffusion processes[J]. IEEE Transactions on Signal Processing, 2010, 58(2): 826-842.

[18] Sardellitti S, Barbarossa S, and Swami A. Average consensus with minimum energy consumption: optimal topology and power allocation[C]. Proceedings of the European Signal Processing Conference (EUSIPCO 2010), Aalborg, 2010: 189-193.

及歆榮： 女，1978年生，博士生，研究方向為無線傳感器網絡、分布式機器學習.

侯翠琴： 女，1983年生，博士，研究方向為無線傳感器網絡、分布式機器學習.

侯義斌： 男，1952年生，教授，博士生導師，主要研究方向為物聯網接入技術、新型人機交互技術、嵌入式軟件與系統.

Research on the Distributed Training Method for Linear SVM in WSN

Ji Xin-rong①②Hou Cui-qin①Hou Yi-bin①

①(Embedded Software and Systems Institute, Beijing University of Technology, Beijing 100124, China)
②(School of Information and Electrical Engineering, Hebei University of Engineering, Handan 056038, China)

In Wireless Sensor Network (WSN), transferring all training samples distributed across different nodes to a centralized fusion center for training Support Vector Machine (SVM) significantly increases the communication overhead and energy consumption. Therefore, this paper studies the distributed training approach for linear SVM through the collaboration of neighboring nodes within the networks. First, the centralized linear SVM problem is cast as the solution of coupled decentralized convex optimization sub-problems with consensus constraints on the classifier parameters. Second, the distributed linear SVM problem is solved and derived using the augmented Lagrange multipliers method, and a novel distributed training algorithm, called Average Consensus based Distributed Supported Vector Machine (AC-DSVM), is proposed. To decrease the communication overhead of global average consensus, an improved distributed training algorithm, named Once Average Consensus based Distributed Supported Vector Machine (1-AC-DSVM), is presented, which is only based on once global average consensus. Simulation results show that compared with existing algorithms, AC-DSVM has slightly higher iterations and data traffic, but can converge to the centralized training results; 1-AC-DSVM not only has better convergence, but also has remarkable advantage in convergence speed and data traffic.

Wireless Sensor Network (WSN); Support Vector Machine (SVM); Distributed learning; Augmented Lagrange multiplier method; Average consensus

TP393; TP181

A

1009-5896(2015)03-0708-07

10.11999/JEIT140408

2014-03-27 收到，2014-07-07改回

國家自然科學基金青年基金(61203377)資助課題

*通信作者：侯義斌 yhou@bjut.edu.cn