基于超限快速決策樹的無線多媒體傳感器網(wǎng)絡(luò)路由優(yōu)化方法

劉 松

(安徽商貿(mào)職業(yè)技術(shù)學院電子商務(wù)學院,蕪湖 241000)

無線多媒體傳感器網(wǎng)絡(luò)(WMSNs)可有效感知視頻圖像等多媒體信息,具有精度高、數(shù)據(jù)傳輸量大、可靠性高等優(yōu)勢[1],普遍應(yīng)用于環(huán)境檢測、交通監(jiān)控等領(lǐng)域[2]。由于WMSNs在輸出過程中存在網(wǎng)絡(luò)時延、時延抖動與能量失衡的問題[3],導致多媒體數(shù)據(jù)流傳輸質(zhì)量下降。因此,研究一種優(yōu)質(zhì)的WMSNs路由優(yōu)化方法具有重要意義。相關(guān)文獻對此進行了很多探討,并取得了一定成果。文獻[4]提出基于改進蟻群算法的無線傳感器網(wǎng)絡(luò)路由方法,通過偽隨機比例規(guī)則優(yōu)化狀態(tài)轉(zhuǎn)移函數(shù)改進蟻群算法,優(yōu)化路由的角度信息的相關(guān)參數(shù),并計算相應(yīng)距離,避免路由的無關(guān)路徑,以及節(jié)點能量的浪費,最后通過更新信息素優(yōu)化路由路徑。該方法可以提升節(jié)點的均衡程度,但節(jié)點能量消耗較多,無法有效降低路由能耗,存在一定局限性。文獻[5]提出一種能量與路徑約束的無線傳感網(wǎng)絡(luò)路由優(yōu)化,針對網(wǎng)絡(luò)路由中單一路徑問題,通過均衡網(wǎng)絡(luò)負載均衡節(jié)點和能源因素,構(gòu)建高速的傳輸路徑,并根據(jù)能量因子保證能量的合理分布,完成優(yōu)化研究。該方法降低了節(jié)點路由中所需要的能耗,但路由路徑單一,并未全面解決該問題,存在優(yōu)化效果較差的問題。針對上述方法中存在路徑單一、能耗較高的問題,本文提出基于超限快速決策樹的無線多媒體傳感器網(wǎng)絡(luò)路由優(yōu)化方法,以滿足WMSNs路由優(yōu)化需求,確定關(guān)鍵參數(shù),以關(guān)鍵變量為超限快速學習機輸入值,利用學習機訓練輸出路由優(yōu)化結(jié)果,完成網(wǎng)絡(luò)路由優(yōu)化。

1 WMSNs路由優(yōu)化方法

1.1 WMSNs路由模型

為實現(xiàn)無線多媒體傳感器網(wǎng)絡(luò)路由優(yōu)化,首先構(gòu)建路由模型,確定路由變量的參數(shù)。模型構(gòu)建時,將全部節(jié)點任意均勻分布在X×Y區(qū)域內(nèi)。其中,不同節(jié)點的信號覆蓋以r為半徑的圓形區(qū)域范圍內(nèi)。各節(jié)點有且僅有一個編號[6],同時,不同節(jié)點可分別經(jīng)由GPS等定位技術(shù)和信息交換技術(shù)確定自身所處區(qū)域坐標和鄰居節(jié)點、sink節(jié)點的區(qū)域坐標。通過數(shù)學形式化語言表示W(wǎng)MSNs路由,表示為G(V,H,W)

其中,式(1)為設(shè)置節(jié)點的有限集合,式(2)為目標鏈路組合,式(3)代表所有節(jié)點的屬性值,v i和v m分別表示編號為i的節(jié)點和sink節(jié)點,,代表sink節(jié)點,v i和v j在處于相互傳輸范圍內(nèi),H ＝V×V,各鏈路(vi,v j) ∈H均包含一組屬性值。δ代表鏈路標記,δtd,δdj,δlp,δer,δtr分別代表td、dJ、lp、er、tr屬性下的鏈路。

若(xi,y i) 和(xj,y j) 分別表示節(jié)點v i和v j的區(qū)域坐標,d ij為兩者間的距離

在G(V,H,W) 內(nèi),利用式(5)描述可獲取節(jié)點v i的鄰居節(jié)點集

其中,Z i表示鄰居節(jié)點集,r代表以避免數(shù)據(jù)包向sink節(jié)點傳輸過程產(chǎn)生的循環(huán)路徑[7],此時以F i表示節(jié)點v i的前向鄰居節(jié)點集

其中,d js表示v j同sink節(jié)點間的距離,d is表示v i同sink節(jié)點間的距離。若v j為v i的前向鄰居節(jié)點,即可通過l′ij表示兩者間的鏈路,即同意由v i向v j搜索路徑,但拒絕由v j向v i搜索路徑。以N(V′,H′,W′)表示G(V,H,W) 的子圖,。N(V′,H′,W′) 即為WMSNs路由模型。

1.2 基于超限快速決策樹的路由優(yōu)化

針對構(gòu)建的WMSNs路由模型,采用超限快速決策樹對其參數(shù)進行有效的確定和優(yōu)化。

1.2.1 基于決策樹的特征變量選擇 作為多棵決策樹集成的學習算法,隨機森林算法既可實現(xiàn)目標分類,也可用于確定變量關(guān)鍵度[8]。隨機森林算法中,基于外帶網(wǎng)絡(luò)數(shù)據(jù)分類的變量分析算法使用最為普遍,該算法逐一對網(wǎng)絡(luò)數(shù)據(jù)內(nèi)的各變量增添相應(yīng)噪聲[9],當經(jīng)過決策樹的網(wǎng)絡(luò)數(shù)據(jù)準確度下降后,需要借助均值確定變量關(guān)鍵度。本文確定的特征變量中,影響無線多媒體傳感器網(wǎng)絡(luò)路由的參數(shù)包括:網(wǎng)絡(luò)傳輸帶寬、網(wǎng)絡(luò)延遲、延遲抖動以及丟包率,采用超限快速決策樹選擇關(guān)鍵參數(shù)。

(1)生成隨機森林。針對K個初始樣本,利用Bootstrap抽樣技術(shù)任意抽取K′個樣本?；贙′個樣本構(gòu)建決策樹c k(k＝1,2,…,p),剩余的K－K′個樣本構(gòu)建袋外數(shù)據(jù),oob代表袋外數(shù)據(jù)屬性,k表示數(shù)據(jù)數(shù)量。在決策樹各節(jié)點處抽取WMSNs路由質(zhì)量初始變量集的m個變量,計算不同變量內(nèi)的信息量,由m個變量內(nèi)確定一個分類性能最優(yōu)的變量實施節(jié)點分裂。

各決策樹自然生長時省略剪枝過程[10],重復(fù)以上過程p次,由此得到包含p棵決策樹的隨機森林為

(2)針對隨機森林內(nèi)的各決策樹s k,利用實施分類,并確定WMSNs路由樣本的分類正確率R k。

(3)以λl表示訓練基中各初始變量,逐一將隨機噪聲引入,λl,將新獲取的袋外數(shù)據(jù)表示為。利用不同s k對實施分類處理,同時確定WMSNs路由樣本的分類正確率。

(4)確定λl的關(guān)鍵度V I

通過隨機森林中遞歸特征消除算法確定變量關(guān)鍵度,同時以此為依據(jù)進行排序,由此利用遞歸特征消除算法確定關(guān)鍵變量[11]。隨機森林—遞歸特征消除算法流程如圖1所示。

圖1 隨機森林遞歸特征消除算法流程

在隨機森林—遞歸特征消除中,首先設(shè)置初始變量訓練數(shù)據(jù)集合

其中,ζ1,ζ2,…,ζn代表初始變量訓練數(shù)據(jù)集合中的組成因子。

確定訓練集合中變量的關(guān)鍵度

其中,v代表訓練集合中變量的關(guān)鍵度系數(shù)。

根據(jù)得到的確定的變量關(guān)鍵度,確定其是否符合終止條件,得到更新后的變量即為訓練的樣本

其中,t c代表更新的時間窗,g代表更新過程中的比例因子。

基于初始變量訓練數(shù)據(jù)集,通過隨機森林確定變量關(guān)鍵度且進行排序;逐次清除關(guān)鍵度最小變量,同時通過剩余變量再次測試隨機森林的分類準確性。依次迭代,確定各次分類準確率值,此時全部變量序列搜索完成。由此獲取全部關(guān)鍵度排序與對應(yīng)不同變量數(shù)量的分類準確率。

通過隨機森林遞歸特征消除算法在WMSNs路由質(zhì)量變量內(nèi)確定關(guān)鍵變量,既可降低輸入數(shù)據(jù)的維數(shù),又可提升分類結(jié)果準確率。WMSNs路由對傳輸速率、可靠性以及能量均衡等多項變量參數(shù)較為敏感,利用決策樹算法能夠在不同路由變量中選取出關(guān)鍵變量——傳輸速率、能量均衡,以其為優(yōu)化目標[12],構(gòu)建WMSNs路由多目標優(yōu)化函數(shù)。

(1)傳輸速率。節(jié)點v i在香農(nóng)定理標準下,以上限傳輸速率向其前向鄰居v j傳輸數(shù)據(jù)包,傳輸速率的主要影響因素為信噪比SNR。以SNRij表示l′ij的SNR 值,得

其中,w ij和d ij分別表示同v i、v j具有相關(guān)性的常數(shù)和兩者間的距離長度,ξ、χi和π分別表示天線增益、v i的發(fā)射信號功率和網(wǎng)絡(luò)內(nèi)噪聲信號功率。以表示l′ij的信道傳輸速率上限,計算過程為

其中,表示l′ij的帶寬,?ij表示信道傳輸速率的固定值。

由整體網(wǎng)絡(luò)角度分析,路徑Pkm的傳輸速率上限受l′ij傳輸速率下限直接影響,由此得到鏈路容量的最優(yōu)化目標函數(shù)maxC

根據(jù)式(14)得到路徑傳輸速率的最優(yōu)化目標函數(shù)maxf i(x)

(2)能量均衡。網(wǎng)絡(luò)路由中節(jié)點運動時需要的能量是實現(xiàn)優(yōu)化的重要部分。因此,本文對其中的節(jié)點能量進行均衡。節(jié)點能量消耗[13]包括發(fā)射端與接收端運行時的耗損。以防止部分節(jié)點能量消耗過高造成WMSNs能量缺失,在數(shù)據(jù)包傳輸過程中需充分降低并均衡節(jié)點能耗。發(fā)射端與接收端能量消耗計算過程

其中,γ和φ分別表示數(shù)據(jù)包長度和1 bit數(shù)據(jù)包傳輸所消耗的能量,表示發(fā)射端能量消耗,表示接收端能量消耗,ρ表示能量確實比例。

得到發(fā)射端的能耗同d ij間成正比例相關(guān)[14]?；诮档凸?jié)點能耗實現(xiàn)節(jié)點能耗均衡的角度分析,節(jié)點路由區(qū)域中存在能量浪費的問題,此時,構(gòu)建能量均衡的最優(yōu)化目標函數(shù)為

基于上述描述,能夠得到多目標路由優(yōu)化函數(shù)

根據(jù)上述確定的路由關(guān)鍵參數(shù)變量,將關(guān)鍵變量作為超限快速學習機的輸入,通過超限快速學習機訓練,得到WMSNs路由優(yōu)化結(jié)果。在無線多媒體傳感器網(wǎng)絡(luò)路由優(yōu)化中,確定關(guān)鍵參數(shù)之后通過超限快速學習機訓練,得到的最終的優(yōu)化輸出結(jié)果。

1.2.2 超限快速學習機 作為單隱層前饋神經(jīng)網(wǎng)絡(luò)的求解算法,超限快速學習機以學習效率快、參數(shù)設(shè)置簡單等優(yōu)勢,在各領(lǐng)域中普遍使用[15-16]。本文將路由關(guān)鍵參數(shù)輸入超限快速學習機中,以實現(xiàn)路由的優(yōu)化。

若學習機內(nèi)包含N個隨機樣本(Xi,t i),其中X i＝[X i1,X i2,…,X in]T＝R n,t i＝t[i1,t i2,…,t im]T＝R m。利用式(13)表示包含L個隱層節(jié)點的單隱層神經(jīng)網(wǎng)絡(luò)為

其中,βi和λ x() 分別表示輸出權(quán)重和集合函數(shù),W i和b i分別表示輸入權(quán)重和第i個隱層的偏置。單隱層神經(jīng)網(wǎng)絡(luò)學習以輸出誤差最低為學習目標

其中,U和T分別表示隱層接待輸出的期望輸出。

在超限學習機內(nèi),若W i與b i被隨機確定,即得到了唯一路由值,確定輸出權(quán)重,完成路由優(yōu)化。

2 實驗分析

2.1 實驗方案

為驗證本文構(gòu)建優(yōu)化方法的實際應(yīng)用效果,實驗中設(shè)置WMSNs路由節(jié)點數(shù)據(jù),其節(jié)點部署如圖2所示。傳感器節(jié)點均勻分布式在150 m×150 m 區(qū)域內(nèi),節(jié)點數(shù)量為400個。其中,源節(jié)點數(shù)量為2個,處于網(wǎng)絡(luò)邊緣區(qū)域(矩形區(qū)域),sink節(jié)點數(shù)量為2個,處于網(wǎng)絡(luò)中心區(qū)域(三角形區(qū)域)。在確定若干條路徑后,模擬傳輸10 000個數(shù)據(jù)。實驗從變量選擇與能量消耗方面驗證本文方法的性能。

圖2 WMSNs節(jié)點部署

2.2 實驗結(jié)果分析

2.2.1 路由優(yōu)化測試結(jié)果分析 實驗中,本文方法由WMSNs內(nèi)路由初始變量內(nèi)確定關(guān)鍵變量。每次清除關(guān)鍵度排序,在最后一位變量后需再次確定分類準確性。分類準確性同變量數(shù)量間的相關(guān)性如圖3所示?？芍?在變量數(shù)量為9的條件下,即為初始變量集。在非關(guān)鍵變量被逐一清除后,分類準確率在整體上表現(xiàn)為逐漸上升的趨勢;變量數(shù)量降至2～3個時,得到的準確率最高,達到98%以上。變量數(shù)量繼續(xù)下降,達到1個時,分類準確率顯著下降,降至93%以下,這是由于變量的過度清除導致關(guān)鍵變量被刪除。由此說明本文方法具有較高的分類精度,能夠得到合適的科學變量數(shù)量,提升最終路由優(yōu)化效果。

圖3 分類準確率與變量數(shù)量間的相關(guān)性分析

采用本文方法優(yōu)化網(wǎng)絡(luò)路由,得到源節(jié)點同sink節(jié)點之間的最優(yōu)路由,結(jié)果如圖4所示。本文方法可確保源節(jié)點存在一個以上目標節(jié)點,且能夠得到最優(yōu)數(shù)據(jù)傳輸路徑,確保實驗對象數(shù)據(jù)傳輸速率最優(yōu),且達到整體能量消耗最低。

圖4 路由優(yōu)化結(jié)果

2.2.2 能量測試 為進一步驗證本文方法的應(yīng)用性能,對比文獻[4]中基于改進蟻群算法的無線傳感器網(wǎng)絡(luò)路由方法和文獻[5]中基于能量與路徑約束的路由優(yōu)化方法,路由優(yōu)化結(jié)果的能量消耗如圖5所示。

圖5 能量消耗對比

在源節(jié)點傳輸?shù)臄?shù)據(jù)包數(shù)量較少(低于300)的條件下,三種方法的在路由優(yōu)化過程中的能量消耗差異較小,均低于150 J。隨著源節(jié)點傳輸數(shù)據(jù)包數(shù)量的提升,三種方法能量消耗逐漸提升,文獻[4]的方法在傳輸數(shù)據(jù)包數(shù)量低于600時,能量消耗低于本文方法,文獻[5]的路由優(yōu)化方法在數(shù)據(jù)包數(shù)量高于600后,能量消耗顯著提升?？芍?本文方法的能量消耗最低。

WMSNs內(nèi)節(jié)點能耗均衡程度可通過節(jié)點剩余能量方差描述,采用三種方法優(yōu)化實驗對象內(nèi)路由節(jié)點的剩余能量,所得結(jié)果見表1。在實驗對象內(nèi)源節(jié)點與sink節(jié)點數(shù)量逐漸提升的條件下,三種方法路由優(yōu)化時實驗對象節(jié)點剩余能量方差均呈現(xiàn)逐漸提升趨勢,但采用本文方法優(yōu)化條件下,實驗對象節(jié)點剩余能量的方差明顯偏小,這表示本文方法在路由優(yōu)化過程中的能耗更加均衡。

表1 剩余能量方差對比

3 結(jié)論

本文提出基于超限快速決策樹的無線多媒體傳感器網(wǎng)絡(luò)路由優(yōu)化方法,通過確定傳感器網(wǎng)絡(luò)路由中的參數(shù),借助決策樹算法確定路由中關(guān)鍵影響參數(shù),將關(guān)鍵參數(shù)作為最終優(yōu)化值輸入超限快速學習機,完成研究目的。實驗驗證了本文方法所選的關(guān)鍵參數(shù)能夠完成路由優(yōu)化,有效提升了數(shù)據(jù)傳輸速率,且降低了能量消耗。本文設(shè)計方法雖然在現(xiàn)階段能夠有效降低無線多媒體傳感器網(wǎng)絡(luò)路由的能耗,但在復(fù)雜的網(wǎng)絡(luò)傳輸過程中,其參數(shù)始終變化,如何使優(yōu)化的關(guān)鍵參數(shù)保持穩(wěn)定是未來研究中的重點問題。