基于隨機森林的鏈路質量預測

劉琳嵐，高聲榮，舒堅

（1. 南昌航空大學信息工程學院，江西 南昌 330063；2. 南昌航空大學軟件學院，江西 南昌 330063）

1 引言

無線傳感器網絡（WSN, wireless sensor network）是一種由各種具有感知能力、計算能力和通信能力的廉價微型傳感器節點通過無線通信的方式以自組織形式構成的網絡[1]。由于被監測區域的復雜性和不確定性[2]，如果數據分組在低質量鏈路上進行傳輸，當節點之間進行通信時就容易丟失數據，從而引發消息重傳，雖有重傳機制保證數據分組的完整性，但這易導致傳輸效率的下降和能耗的增加。通過鏈路質量預測選擇高質量鏈路進行通信，不僅可以保障數據的可靠傳輸，還可以降低節點的能耗，延長網絡壽命。因此，降低節點能耗、提高能源利用率的關鍵在于提高節點間通信效率。

在通信過程中，準確的鏈路質量預測是保證上層協議（數據鏈路層的MAC協議、網絡層的路由協議、網絡管理層的拓撲控制等）性能的基礎，對路由協議的設計者而言至關重要[3]。因此，建立一個良好的WSN鏈路質量預測機制，進而動態地調整路由協議，保證數據正確傳輸顯得十分必要[4]。本文研究鏈路質量預測方法，為上層路由選擇提供參考。

2 相關研究

無線傳感器網絡由于節點移動、多徑衰落、噪聲和干擾等因素影響導致無線鏈路動態變化，實時、準確的鏈路質量預測面臨巨大挑戰，吸引了國內外學者的廣泛關注和深入研究。目前，主要有基于鏈路特性、基于概率估計理論和基于智能學習的方法。

2.1 基于鏈路特性的方法

此類方法主要是采用硬件參數接收信號強度指示（RSSI, received signal strength indicator）、鏈路質量指示（LQI, link quality indicator）、信噪比（SNR,signal to noise ratio）對鏈路質量進行預測。文獻[5]使用一種幀計數器 meter，能夠在低功率無線傳感器網絡中實現精確和實時的鏈路評估，當存在信道競爭和共存干擾時，使用分布式輕量級方法統計損壞的數據幀數，并將其應用到 4-Bit評估器中，實驗結果表明，該方法能夠提高鏈路質量評估的準確性和實時性。文獻[6]為了解決輸電檢測系統中對上層通信網絡的鏈路質量問題，通過分析WSN的網絡特征，同時依據跳數、網絡環境，在路由建立階段選擇最優下一跳節點。文獻[7]提出了一種簡單、準確、低成本的鏈路質量估計技術，適用于資源受限的WSN場景，并通過卡爾曼濾波和模糊邏輯優化了低成本下RSSI和LQI對鏈路質量的影響，最后在鍋爐廠的實驗場景中，以2種不同的速率實現流式傳輸，實驗結果表明，該方法以較小時延為代價實現了無差錯傳輸。文獻[8]提出了一種綜合性的鏈路質量度量方法——三角度量（Triangle），利用幾何學的方法，結合分組接收率（PRR, packet reception rate）、LQI和SNR信息來衡量鏈路質量，能通過較少的鏈路探測分組快速且可靠地評估鏈路質量。

2.2 基于概率估計理論的方法

此類方法主要是通過發送大量的探測分組，計算接收端的分組接收率。文獻[9]基于常用的對數正態路徑損耗模型，將由 SNR表征的無線鏈路質量分解為具有不同特性的2個部分：時變非線性部分和非平穩隨機部分。通過對這2個部分的分別處理，提出了一種新的鏈路質量估計方法——WNN-LQE，獲得鏈路質量的置信區間。文獻[10]將指數加權移動平均（EWMA, exponentially weighted moving average）數學模型應用到鏈路質量評估中，解決數據分組傳輸速率的不穩定問題，實驗結果表明，通過在EWMA模型中建立相關參數，可以調節評估結果的靈敏性和穩定性，以達到特定環境下的要求。文獻[11]中的 4-Bit采用期望傳輸次數（ETX,expected transmission count）作為指標的評估器，使用 4-Bit刻畫物理層、鏈路層和網絡層的狀況，選擇RSSI、LQI指標，同時考慮了鏈路的非對稱性，實驗結果表明，該評估方法可以在大幅度減少能量消耗的同時提高準確性。然而，重傳數據分組數并未將信道質量與平穩性考慮在內。

2.3 基于智能學習的方法

此類方法主要采用機器學習[12]和模式匹配等智能學習方法進行建模。文獻[13]采用一種基于支持向量機的多分類鏈路質量評估機制，選擇 RSSI和LQI作為評估參數，根據PRR將鏈路質量分為5個等級，該模型可以使用較少數量的探測數據分組準確地估計出當前的鏈路質量。文獻[14]使用一種基于模式匹配的方法來預測鏈路質量變化，將鏈路的SNR值存儲到鄰居節點，以獲得SNR的時間序列，當需要對鏈路的未來狀態進行預測時，節點使用互相關函數查找過去與當前時刻相匹配的SNR，但文中只使用了SNR來度量鏈路質量，并不能反映出鏈路的真實情況，且實驗只與線性預測模型進行對比，也不能很好地反映出模型的性能。

上述研究為解決鏈路質量預測問題提供了相關的經驗和思路。其中，基于鏈路特性的方法主要是使用物理層參數預測鏈路質量，其所需的參數獲取簡單，可以直接從節點中讀取，但節點本身存在校準誤差；基于概率估計理論的方法需要發送大量的探測分組，對鏈路的長期度量較為準確，但對鏈路的短期變化不敏感；基于智能學習的方法通過數據驅動能夠挖掘出數據之間潛在的特征，是未來研究的一個趨勢。

本文采用無監督聚類高斯混合模型（GMM,Gaussian mixed model）劃分鏈路質量等級，作為鏈路質量的評價指標；采用零相位分量分析（ZCA,zero-phase component analysis）白化方法對數據進行預處理，去除樣本間的相關性；應用隨機森林分類（RFC, random forest classifier）算法評估鏈路質量等級；通過鏈路質量的時序信息，應用隨機森林回歸（RFR, random forest regression）算法預測下一時刻的鏈路質量等級。

3 鏈路質量等級的劃分

根據不同距離下鏈路PRR分布的不同，將鏈路的通信范圍劃分為3個不同的區域，分別為連通區、過渡區和不連通區。傳統方法中評判鏈路質量的優劣是通過計算PRR值，而不同的文獻中劃分的等級數不同，劃分等級的標準也不同。本文應用 GMM無監督聚類方法，將PRR值劃分為5個等級，等級劃分的標準由GMM學習得到。

GMM 根據高斯概率密度函數來判斷樣本是否屬于該高斯模型，每個高斯模型都對應著一種類別，通過樣本的輸入計算出概率密度，與設定好的閾值相比較，從而確定樣本所屬的類別。由于GMM具有多個模型，劃分更為精細，適用于多類別的劃分。樣本集的高斯混合分布和概率密度函數分別為

其中，式(1)為高斯混合分布，該分布由k個混合高斯模型組成，jΣ為協方差矩陣，ui為第i個高斯模型均值向量，jα為混合系數，且式(2)為第j個高斯模型的概率密度函數。

似然函數的求解采用最大期望（EM, expectation maximum）算法進行迭代，具體的步驟如下。

步驟 1 初始化高斯混合分布的模型參數{(αj,

步驟2 E步：依據當前模型參數，計算PRRi各混合成分的后驗概率，即

步驟4 重復步驟2和步驟3，直到每一個高斯分布的均值和方差收斂，再將樣本劃入相應的等級中。

4 鏈路質量評估

采用 ZCA白化方法去除冗余樣本，采用Bootstrap重抽樣方法生成不同的數據集；對數據集進行訓練，生成多棵鏈路質量決策樹，組合構成RFC模型，評估鏈路質量。

4.1 樣本數據預處理

傳感器節點收集到的物理層數據（RSSI、LOI、SNR）和鏈路層數據（PRR）之間存在著相關性。文獻[15]指出，PRR較高的鏈路中，其RSSI也較高的概率為95%，RSSI與PRR是相關的；文獻[16]指出，LQI與PRR具有較強的相關性，由LQI可以估計PRR值。由于樣本數據各特征之間存在著相關性，若直接將樣本數據用于訓練會存在冗余現象，因此本節采用白化的方法降低樣本數據之間的相關性，經白化處理后的數據特征之間相關性降低，且所有特征具有相同的方差。

常用的白化處理方法包括主成分分析（PCA,principal component analysis）白化和ZCA白化。PCA白化是將數據進行 PCA處理，使處理后數據的協方差矩陣為單位矩陣；ZCA白化是在PCA白化的基礎上進行一個選擇操作，通過將 PCA處理后的旋轉矩陣左乘特征矩陣，將數據旋轉回去，保留數據的所有特征，使 ZCA白化后的數據更接近原始數據，ZCA白化的具體步驟如下。

步驟1 計算數據集的協方差矩陣Σ為

其中，m為數據集樣本的個數，(i)x 為物理層參數特征組成的向量。

步驟2 求出數據集的協方差矩陣Σ后，計算出協方差矩陣Σ的特征向量，按列排放組成矩陣U，即

其中，u1是最大的特征值對應的特征向量，n是特征的個數，特征值越大，代表著該特征包含的信息越多。

步驟3 將向量u組成新基，得到數據集旋轉后的結果xrot為

步驟4 對數據集進行PCA白化，如式(11)所示。經 PCA白化后，數據所有特征具有相同的方差，其中，iλ是xrot協方差矩陣中對角元素的值。

步驟5 將PCA處理后的旋轉矩陣左乘特征矩陣，得到ZCA白化，如式(12)所示。ZCA白化保留了數據的所有特征，使 ZCA白化后的數據更加接近原始數據。

4.2 構建評估模型

上述獲得的樣本空間中，應用 ZCA白化去除了樣本之間的相關性，并用GMM無監督聚類算法得到了鏈路質量等級。由于鏈路質量是由多個因素共同決定的，而鏈路質量等級能夠很好地反映出鏈路的好壞，通過鏈路質量等級的確定可以實現鏈路質量的評估。因此，鏈路質量評估是根據多個因素確定鏈路質量等級的，其實質就是一個多分類問題。本文利用RFC算法在分類問題上的優勢，且不容易出現過擬合的特點，構建鏈路質量評估模型。首先通過Bootstrap重抽樣方法構建不同的數據集，對每一個數據集分別訓練生成鏈路質量決策樹，然后對決策樹的結果進行組合投票產生最優分類，最終得到鏈路質量等級。模型將鏈路物理層的參數組成的向量作為輸入，將評估出來的鏈路質量等級值作為輸出，輸入向量 I nputi的組成為

在生成決策樹的過程中，由于采用 Bootstrap重抽樣方法從原始數據中抽取訓練集，有63%的數據會被重復抽取，而37%的數據從未抽取，未抽取的數據叫作袋外數據（OOB, out of bag）。用OOB來檢驗決策樹的分類效果，得到的誤差為袋外數據誤差（OOBE, out of bag error）[17]。袋外數據誤差用于計算決策樹的平均誤分率，可以得到 OOB誤差估計。將w棵決策樹的誤差估計值取平均，可以得到隨機森林的泛化誤差估計值，OOBE越小，隨機森林算法的分類性能越好。

RFC通過構造訓練集之間的差異增加分類模型間的差異性，從而提高組合模型的泛化能力。通過w輪訓練，得到w棵決策樹分類模型序列最后組合成一個多分類模型系統。基于RFC的評估模型，最終的輸出結果采用投票方式產生。

其中，H(x)表示組合分類模型；hi(x)表示第i棵決策樹分類模型；Y表示輸出變量，即鏈路質量等級值；I(?)表示示性函數。

5 鏈路質量預測

采用RFR算法對各個實際場景構建模型，建模過程如圖1所示。

圖1 基于隨機森林回歸算法的鏈路質量預測過程

利用 Bootstrap方法從訓練樣本集Sk(k=1,… ,n)中進行w次抽樣，組成w個樣本子集，每個子集中的元素都不完全相同，對每個樣本子集分別構建回歸樹，并在測試集中對模型進行預測，預測結果需要w棵回歸樹共同決定。

5.1 樣本集的構建

RFC評估模型的輸出為鏈路質量等級值lv = { lv1, lv2,… ,l vn}，其中，lvn為第n個時刻評估模型輸出的等級值。利用滑動窗口將lv變換成樣本集，其中，為預測模型的輸入，yk= l vk+n-1為標簽值，k為樣本集的序號，n為滑動窗口的大小，窗口的滑動步長為1。

5.2 回歸樹生成

回歸樹的生成就是遞歸地構建二叉樹的過程，對回歸樹采用平方誤差最小化原則，利用分類與回歸樹（CART, classification and regression tree）中的回歸樹算法生成一棵回歸樹，共生成w棵回歸樹，從而形成“森林”。為了保證回歸樹的多樣性，降低樹之間的相似性，從而保證隨機森林模型不容易產生過擬合問題。在回歸樹的構建過程中，從M個影響鏈路質量等級的特征中隨機選取m個作為隨機特征變量，用來構建回歸樹，m在模型中是一個超參數，對最終的結果有一定的影響。隨機森林中回歸樹數量w也是模型的一個超參數，超參數之間的組合會對最終的預測效果產生重要的影響。在不同的實驗場景中，最優組合也是不同的，根據經驗值所構建的隨機森林并不適合每個實驗場景。因此，本文采用網格搜索算法對超參數進行優化，網格搜索算法將會遍歷所有變量可能的取值，計算出每種可能性對應的目標值，從而選出變量最優的組合。回歸樹生成算法如算法1所示。

算法1 回歸樹生成算法

輸入 訓練數據集D

輸出 回歸樹f(x)

步驟1 選擇最優切分變量j與切分點s，求解

步驟 2 用選定的(j,s)劃分區域并確定相應的輸出值為

步驟3 繼續對2個子區域調用步驟1和步驟2，直到子區域不能繼續劃分，生成葉子節點。

步驟 4 將輸入空間劃分為M個區域R1,R2,… ,RM，生成回歸樹為

5.3 預測階段

當w棵回歸樹模型構建完成后，采用測試集數據對鏈路質量進行預測。將測試集中的6個物理層參數作為鏈路質量預測模型的輸入，分別為得到各回歸樹模型預測的等級序列。基于RFR算法的預測模型最終輸出的鏈路質量等級值是各回歸樹模型的均值。

其中，Yk為鏈路質量組合預測模型，fi(xk)為第i棵回歸樹預測模型。

5.4 模型評價

本文采用五折交叉驗證法將樣本數據集劃分為5個大小相似的子集，每個子集在劃分的過程中保持數據分布的一致性。在訓練過程中，將4個子集的并集作為訓練集，剩下的作為測試集，進行 5次訓練，對5次預測的結果取均值作為最終的預測結果。采用均方誤差（MSE, mean square error）評價預測模型的優劣，即

其中，lvk為模型的預測值，yk為測試集中的真實值。MSE越小，模型的預測值與真實值的差異越小，模型的性能越好。

6 實驗設計與分析

在數據收集過程中，選用美國 Crossbow公司的Telos B節點，并采用如圖2所示的無線傳感器網絡鏈路質量測試平臺對收集到的數據進行分析，數據的預處理和模型的構建通過使用服務器上的Python平臺實現。

圖2 無線傳感器網絡鏈路質量測試平臺

6.1 實驗參數設置與數據收集

實驗場景的設置主要從 WSN的常用場景出發，考慮了在真實的環境中可能會遇到的干擾，例如無線電波、障礙物、鄰近信道等。因此本文設定了4個實驗場景，有校園廣場、校園室內走廊、校園小樹林和校園停車場，具體的實驗場景分別如圖3～圖6所示，在每個場景都部署了一個小型的星型WSN網絡。其中，校園廣場、校園小樹林和校園停車場部署了9個節點，一個為Sink節點，8個為感知節點；校園室內走廊部署了 5個節點，一個為 Sink節點，4個為感知節點；節點間距均為10 m。校園廣場、校園小樹林和校園停車場按照如圖7所示的星型網絡部署實驗節點，校園室內走廊按照如圖8所示的位置部署實驗節點，實驗參數設置如表1所示。

圖3 校園廣場實驗場景

圖4 校園室內走廊實驗場景

圖5 校園小樹林實驗場景

圖6 校園停車場實驗場景

圖7 星型網絡部署

圖8 室內走廊部署

表1 實驗參數設置

6.2 實驗結果分析

為了保證數據的多樣性與可靠性，本文通過連續幾天的測量獲得不同場景下的PRR，其部分結果分別如圖9～圖12所示。

圖9 校園廣場節點1的PRR

圖10 校園室內走廊節點2的PRR

圖11 校園小樹林4個節點的PRR

圖12 校園停車場節點6的PRR

校園廣場場景中比較空曠且干擾源較少，在相同的距離下鏈路整體表現近似，因此選用節點1描述該場景的鏈路質量。由圖9可知，校園廣場實驗場景的PRR大部分都在0.8以上，鏈路質量處于較高水平，且穩定性較好，這是由于廣場比較空曠且干擾源較少。選用節點2描述校園室內走廊場景的鏈路質量，由圖10可知，在0～25 s鏈路呈現較高的波動性和突發性，之后鏈路趨于平穩，這是因為該時段有人員的走動對鏈路產生了干擾。由圖 11可知，鏈路質量整體波動較大，節點7和節點8的PRR在0.1～0.5之間波動，鏈路質量處于較差水平，這是因為該場景中的主要干擾源是樹木，且分布無規律，容易產生干擾，節點 1和節點 2距離 Sink節點的距離相同，但處于不同的方向，其PRR也呈現出不同的波動情況，這是由于不同方向上樹木的遮擋情況不同。選用節點6描述校園停車場場景的鏈路質量，由圖12可知，鏈路的PRR在0～0.9之間波動，鏈路有著較大的波動性和突發性，這是因為該場景中有建筑物和車輛的遮擋，且時常有車輛進出停車場，車輛上移動設備所產生的無線信號會對鏈路產生干擾。

為了進一步驗證RFR模型的預測性能，在4種實驗場景下，將RFR模型與EWMA模型、Triangle模型、支持向量回歸機（SVR, support vector regression）模型和線性回歸（LR, linear regression）模型進行對比，其中，EWMA和Triangle為傳統學習方法，LR和SVR為常見的機器學習方法。各個場景下的預測值與真實值的對比分別如圖 13～圖 16所示，從圖13、圖14和圖16可知，鏈路大部分時間都是處于1、2等級鏈路，鏈路質量較好，5個模型都能預測出鏈路的狀況，但是當鏈路發生突變時，RFR模型能夠預測出鏈路的突變情況，模型的準確性較好；從圖15可知，此時的鏈路主要是在4、5等級波動，鏈路質量較差，但 RFR模型仍能捕捉到鏈路的變化，模型的準確性好，并能夠適應環境的變化。

圖13 校園廣場的實驗預測結果

圖14 校園室內走廊的實驗預測結果

圖15 校園小樹林的實驗預測結果

圖16 校園停車場的實驗預測結果

為進一步精確對比預測模型的預測效果，計算了預測模型在不同實驗場景下的MSE，其結果如表2所示。

表2 4種實驗場景下的MSE

由表2可知，在4種實驗場景中，EWMA模型的MSE最大，有著較大的預測誤差，Triangle模型和 EWMA模型的預測效果均不如機器學習模型。校園停車場、校園室內走廊和校園廣場實驗場景中，RFR模型的預測性能均明顯優于EWMA模型、Triangle模型、SVR模型和LR模型，其中，校園室內走廊和校園廣場是較為穩定的實驗場景，Triangle模型、SVR模型和LR模型均具有較高的預測準確性，但是在校園停車場實驗場景中，由于車輛的運動和車載無線設備的干擾，鏈路出現了一定程度的波動，且呈現出突發性，導致SVR模型和LR模型的預測效果均不理想，但RFR模型卻能及時地預測出鏈路的波動情況，有著更好的抗干擾能力。和其他場景相比，校園廣場和校園室內走廊場景中 RFR模型的MSE均較小，取得了較好的預測效果，尤其是在校園廣場場景中，RFR模型的 MSE最小，其預測效果優于校園室內走廊場景。這是因為在校園室內走廊中，會有人員來回走動，對鏈路造成干擾，導致鏈路不穩定。在校園小樹林場景中，由于受到樹木的直接遮擋和多徑效應的影響，鏈路質量處于較差的水平，相比其他3個實驗場景，各預測模型的預測誤差均有增加，但RFR模型的MSE最小，有著更好的預測效果。

在不同的時間段設計了4種實驗場景，通過收集不同干擾源下的鏈路質量測試模型性能。實驗結果表明，RFR預測模型在4種場景中表現良好，均有較高的預測準確性，體現出模型擁有良好的泛化能力。

在校園廣場實驗場景中驗證模型的預測時間，5個模型的平均預測時間如表3所示。

表3 5個模型的平均預測時間

由表3可知，EWMA模型的預測時間最小，其為傳統模型，計算量最少。RFR模型通過構造多棵回歸樹，保證了模型的預測準確性，但并未大量增加平均預測時間，和 SVR模型處于一個量級上，就鏈路質量預測問題而言，增加的時間處于可接受范圍。

7 結束語

本文采用GMM劃分鏈路質量等級，用于評價鏈路質量；運用ZCA白化去除樣本之間的冗余性，經白化處理后的數據之間相關性較低，且所有特征具有相同的方差；基于 RFC構建鏈路質量評估模型，使用Bootstrap重抽樣方法生成不同的數據集，訓練后生成多棵鏈路質量決策樹，組合構成RFC模型；通過鏈路質量的時序信息，應用RFR構建預測模型，預測下一時刻的鏈路質量等級，采用 MSE評價預測模型的優劣。4種真實實驗場景中的預測結果表明，與 EWMA模型、Triangle模型、SVR模型和LR模型相比，RFR模型具有較高的預測準確性和較良好的泛化性能。