基于SDN網絡環境感知的智能路由算法

趙季紅，張夢雪，喬琳琳，張文娟，盧立偉

1.西安郵電大學 通信與信息工程學院，西安 710121

2.西安交通大學 電子信息工程學院，西安 710049

隨著通信網絡技術的發展，網絡中接入的通信設備越來越多[1-3]，因此網絡環境信息也越來越豐富和多樣，網絡環境中包含著大量與用戶緊密相關的各種信息，比如包括用戶的興趣愛好、移動屬性和身份信息等等[4-6]，如何有效地分析并利用這些網絡中的環境信息來提高網絡的性能，讓網絡更加智能地服務于人們將會成為網絡研究的熱點。

研究關于如何提高網絡性能的傳統軟件定義網絡（software defined network，SDN）路由算法已有很多[7]。但是面對復雜多樣的網絡環境，傳統的SDN路由算法在提高網絡性能的同時并未分析和結合網絡中的環境信息，比如文獻[8]提出了一種基于遺傳算法的自適應SDN路由算法（adaptive SDN routing algorithm based on genetic algorithm，ASRAGA），該算法通過對交叉和編譯操作進行條件約束，來降低網絡開銷和優化網絡性能；文獻[9]提出了一種基于SDN緩存和流轉發算法的端到端的延遲最小化聯合規則，制定了一個受流守恒和緩存容量等約束的端到端延遲最小化問題，并用K-最短路徑（K-shorted path，KSP）算法、Kuhn-Munkres算法和拉格朗日對偶法依次求解；文獻[10]提出一種基于分段路由的SDN路由算法，通過對路徑值的綜合評價制定策略，用以節省路徑代價和緩解網絡擁塞；文獻[11]提出一種基于優先級的SDN動態多路徑（priority-based dynamic multi-path routing，PDMR）路由算法，以此提高資源的利用率和滿足嚴格的QOS要求；文獻[12]提出一種遺傳蟻群（genetic ant colony，GAC）路由算法，該算法結合了遺傳算法和蟻群算法的優點，充分利用正反饋縮短搜索時間從而快速找到最優路徑。

關于結合網絡環境信息的路由算法的研究也有一些，比如文獻[13]中提出了一種SFQ（social features based quota）路由算法，該算法利用節點的社交屬性來確定每個節點的配額，在該方法中，與目標節點擁有更多共同屬性的節點獲得更多的數據復制配額；文獻[14]提出一種SSR（social similiry-based routing）算法，節點在緩沖區記錄相遇的社會重要性，當兩個節點接觸時，采用動態扭曲算法來計算兩個節點的社會重要序列相似度，最后與目的節點社會重要序列相似度最大的節點作為下一跳中繼節點；文獻[15]提出一種社區感知轉發算法，該算法利用節點在不同周期的接觸方式的相似性劃分社區，通過訓練隱藏半馬爾可夫（hidden semi-Markov model，HSMM）來計算節點在社區之間轉移概率，并把轉移概率最大的節點作為下一跳中繼節點；文獻[16]提出一種基于用戶興趣選擇合作節點的傳輸機制，在通信過程中，該算法計算節點之間偏好的匹配度，選擇匹配度最高的節點作為中繼節點傳輸數據。文獻[13-16]中的算法都只考慮了一種網絡環境因素，沒有考慮更多的網絡環境因素，而網絡中還有很多其他的環境因素，因此不能夠找到更合適的中繼節點。合適中繼節點的選擇在提高數據轉發效率和網絡性能方面起著至關重要的作用，而且這些算法也沒有結合SDN，SDN將轉發與控制進行分離，不僅能夠動態地掌握全局網絡視圖，還可以實現邏輯集中式和可編程控制，在網絡開發和網絡管理方面帶來便利[17]。

針對以上情況，提出一種基于SDN網絡環境感知的智能路由算法（intelligent routing algorithm for SDN network environment awareness，SNEA-IR）。該算法的主要貢獻有：（1）根據人們活動的周期性，在時間上劃分周期和時期。（2）融合網絡環境中的社交屬性因素和移動屬性因素來計算節點與目標節點的相遇可能性，并利用BP神經網絡根據所得到的相遇可能性預測下一個時期的相遇可能性。（3）通過不斷地尋找更合適的中繼節點完成尋路過程。（4）最后通過仿真結果驗證所提算法能有效提高數據傳輸率，減少延遲和傳輸跳數。

1 系統模型

如圖1描述了載體節點下一跳中繼節點的選擇以及這兩個節點之間數據的發送過程。本文的應用場景是在一個城市中，節點是攜帶移動設備的人。定義城市中每個區都部署有一個SDN控制器，每個SDN控制器內都部署有SNEA-IR算法和BP神經網絡。根據節點活動的周期性，在時間上劃分周期和時期，每個時期又分為狀態收集階段、狀態發送階段和數據發送階段。

圖1 系統模型Fig.1 System model

中繼節點的選擇以及載體節點與中繼節點之間數據的發送具體過程如下：在狀態收集階段，載體節點通過相遇收集其他節點的狀態信息，在這里假設源節點了解目標節點的狀態信息。在狀態發送階段，載體節點把收集到的狀態信息和目標節點的狀態信息發送給SDN控制器，SDN控制器計算節點與目標節點之間當前時期的相遇可能性，然后利用BP神經網絡根據節點與目標節點的以往周期和當前時期的相遇可能性預測下一時期的相遇可能性，SDN控制器選擇出與目標節點下一時期相遇可能性最大的節點作為載體節點的中繼節點，并將中繼節點的ID發送給載體節點。在數據發送階段，載體節點根據中繼節點ID將數據和目標節點的狀態信息發送給中繼節點。

每個中繼節點都重復這三個階段直到將數據發送給目標節點為止。

1.1 周期和時期的劃分

在日常生活中，人們的活動具有周期性的趨勢，在節點的移動中，把每一周作為一個周期（歷史參數），把每一周劃分為很多時期（當前參數）。周期和時期劃分模型如圖2所示，假定是節點與目標節點當前的相遇可能性，那么是節點與目標節點的歷史相遇可能性是節點與目標節點的下一時期的相遇可能性。

圖2 周期和時期劃分Fig.2 Periods division

1.2 狀態表的建立和收集

定義每個節點都有一個狀態表，里面包含自己的社交屬性信息和移動屬性信息。用Statez=(Md z,αz,Listz)表示載體節點z的狀態表，Md z代表z的移動屬性信息，αz里面包含z的社交屬性特征向量，Listz是z與其他節點相遇建立的狀態序列，當z與其他節點相遇時，就會把與之相遇的節點的狀態表添加到自己的Listz里面。Listz表示如下：

Statea、Stateb、Stateq分別表示與n1相遇的節點a、節點b和節點q的狀態表。αz=(A z,B z,…,Y z)，其中A z,B z,…,Y z分別代表z不同屬性的特征子向量，例如A z=(a1,a2,a3,a4)是興趣子向量，a1、a2、a3、a4代表不同的興趣可以分別表示為籃球、看電影、學習和聽音樂。如果z的興趣只喜歡打籃球那么A z=(1,0,0,0)。

1.3 社交屬性相似度的計算

節點z和目標節點d之間的興趣子向量的相似度可以表示為：

z和d之間的社交屬性相似度可以表示為：

ω1,ω2,…,ωy是z和d的不同屬性子向量的權重值，利用改進的熵值評價方法計算節點之間不同子向量的權重值，給出權重矩陣G如下：

其中，x ij表示第i個節點的第j個子向量，即節點i的第j個社交屬性值，將節點i的第j個社交屬性的貢獻值可以量化為：

定義Qj為所有節點第j個屬性值的總貢獻值，所有節點的第j個社交屬性的總貢獻值可以量化為：

Qj的取值范圍為[0，1]。當所有節點第j個社交屬性的貢獻值趨于相等時，Qj等于1。

因此可以利用貢獻值的差異來確定社交屬性子向量的權值，定義ci為每個節點第j個社交屬性的貢獻一致性程度，即ci=1-Qj。

因此可以根據對應的貢獻水平來確定子向量的權重，第j個社交屬性子向量相似度的權值ωj可以表示為：

調整后的權重值可以表示為：

1.4 移動屬性相似度的計算

通常情況下，兩個節點的移動屬性越相似，這兩個節點之間相遇的可能性就越高，成功轉發消息的概率也就越高。根據這一理論，所提算法可以將節點的移動屬性用時間點和通信區域的位置(t1,l1),(t2,l2),…,(tu,lu)來表示，其中t為時間點，l為通信域。

定義u表示節點z與其他節點之間信息傳輸的次數，用CL(z,R)來表示節點z的移動屬性，那么CL(z,R)可以用下面公式來表示：

其中，R為移動社交網絡中通信區域的位置集，這就意味著，只有當節點z與通信區域R中的其他節點相接觸時，β(R,lw(z))的值為1。節點z和節點d之間的移動相似度可以表示為：

考慮到時間因素，定義△t為時間精度，它反映了同一時間內同一地理位置所有節點所占的比例。

定義SRz,d為節點z和目標節點d之間的相遇可能性，SRz,d的表示如下：

1.5 BP神經網絡預測模型

如圖3是BP神經網絡預測模型，將BP神經網絡部署在SDN控制器中，該BP神經網絡的當前輸入為節點與目標節點的當前時期的相遇可能性SRv，歷史輸入為節點與目標節點的歷史相遇可能性SRh，輸出為預測的節點與目標節點下一時期的相遇可能性SRp。

圖3 BP神經網絡預測模型Fig.3 BP neural network prediction model

H v和H h分別為當前輸入和歷史輸入的權重。

φ是激活函數，S是求和函數，S可以表示為：

SRp可以表示為：

Error是該BP神經網絡預測模型的最小誤差值，該BP神經網絡預測模型采用最速下降法來求Error，Error可以表示為：

其中SRatual是節點與目標節點實際的相遇可能性。

2 路由算法設計

本章主要描述了路由算法的設計過程。該算法數據轉發的關鍵在于在與載體節點相遇的節點集中找到最合適的中繼節點，合適的中繼節點的選擇不僅可以提高數據轉發的效率還可以提高整個網絡的性能。在前面分析中，提出了一種基于SDN網絡環境感知的智能路由算法（SNEA-IR），整個路由策略如算法1所示。

算法1 SNEA-IR路由策略

SDN控制器內部署BP神經網絡，并且定義在SDN控制器中有一個SAT表用于存放節點與目標節點當前時期的相遇可能性。在SDN控制器中計算節點與目標節點當前時期的相遇可能性，并利用BP神經網絡對節點與目標節點下一時期的相遇可能性進行預測，然后選出下一時期與目標節點相遇可能性最大的節點作為下一跳中繼節點，具體過程如子算法1所示。

子算法1中繼節點的選擇

在BP神經網絡中，使用最速下降法，通過反向傳播不斷逐層地調整權值和閾值，使得網絡的誤差平方和最小。BP神經網絡中節點與目標節點下一時期相遇可能性的預測如子算法2所示。

子算法2相遇可能性的預測

3 仿真與性能分析

3.1 實驗環境配置

本實驗使用IGEN[18]工具生成物理網絡拓撲，并通過Matlab進行仿真分析，在仿真過程中，源節點隨機生成數據包，并隨機選擇其目的節點，具體參數如表1所示。在實驗中，為了使模擬更加接近于人們的真實運動軌跡以及運動軌跡范圍內人們的聚集密度，設置通信區域的面積大小為3 000 m×3 000 m，并劃分為9個面積相等的區域，每個區域的面積為1 000 m×1 000 m，設置整個通信區域中總體模擬節點數量為600個。把每一周按小時劃分為168個時期，在仿真實驗中，狀態收集時長太短會影響載體節點尋找合適中繼節點的精準性，狀態收集時間太長則會增加整個數據發送過程的時延，只有當狀態收集時長為35 min時，數據的傳輸效率最高，因此將狀態收集時長設置為35 min。根據多次的仿真經驗，設置狀態發送階段時長范圍為0～15 min，數據發送階段的時長范圍為0～10 min，總的模擬時間為15 d。結合現實生活中人和車輛的正常移動速度，設置每個節點的移動速度為1～6 m/s。選取節點最重要的5個社交屬性特征作為節點的社交屬性子向量，這5個子向量分別是身份、家庭住址、工作地址、興趣和每個節點自身特征，每個社交屬性子向量里面包括4個特征關鍵詞。由于節點的活動具有周期性，節點之間下一時期的相遇可能性與它們的歷史相遇可能性具有更強的相關性，因此在BP神經網絡中設置歷史相遇可能性的權重值為0.6，當前相遇可能性的權重值為0.4。經過多次迭代，當學習率為0.3時BP神經網絡的訓練達到最優，所以將學習率設置為0.3。結合通信區域的總體模擬節點數量和實驗時間，每個載體節點在實驗時間范圍內可能遇到的其他節點的數量在0～600個，因此設置每個載體節點的訓練樣本為0～600個，根據移動設備在無線網絡和非無線網絡下實際的數據平均發送速率，將數據源的數據發送速率設置為6 Mbit/s。

表1 實驗配置參數Table 1 Experimental configuration parameters

3.2 性能分析

本節將所提算法SNEA-IR與SFQ[13]算法和SSR[14]算法進行了對比，SFQ算法利用節點的社交屬性來確定每個節點的配額，在該算法中與目標節點擁有更多公共屬性的節點獲得更多的數據復制配額。在SSR算法中節點在緩沖區記錄相遇的社會重要性，當兩個節點接觸時，采用動態扭曲算法來計算兩個節點的社會重要序列相似度。最后將數據包轉發到與目的節點社會行為最相似的中繼節點。本節從數據傳輸率、數據傳輸跳數和數據傳輸時延三個方面來評估算法的性能，并驗證所提算法的有效性。

（1）數據傳輸速率變化比較

圖4是數據傳輸速率的比較，從圖中可以看出在第1天三個算法的數據傳輸率相差不大，隨著時間的增加，三種算法的傳輸率都有所增加，但最終都趨于穩定。在第15天，SNEA-IR算法的數據傳輸率達到73%，SSR算法55%，SFQ算法33%。SNEA-IR算法的數據傳輸率要遠高于其他兩種算法是因為SNEA-IR算法根據節點與目標節點以往周期和當前時期的相遇可能性來預測下一時期的相遇可能性，提高了中繼節點尋找的精準性，并且隨著時間的增加，載體節點接觸到的其他節點越來越多，BP神經網絡的訓練樣本也越來越多，BP神經網絡預測結果與實際結果的誤差會降低到一定的范圍，端到端之間的數據傳輸就會更加高效和穩定。

圖4 數據傳輸率Fig.4 Data transfer rate

（2）數據傳輸跳數比較

圖5是三種算法數據傳輸跳數的比較，從圖中可以看出，SNEA-IR算法在剛開始時數據傳輸跳數低于SFQ算法和SSR算法，隨著時間的推移，SNEA-IR算法數據傳輸跳數的增長速率也遠遠低于SFQ和SSR兩種算法。在實驗結束時，SNEA-IR算法的傳輸跳數比SFQ算法少26跳，比SSR算法少18跳。因為在節點相似度的計算上SFQ算法和SSR算法只考慮了單一的網絡環境因素，而SNEA-IR算法考慮了社交屬性因素和移動屬性兩種網絡環境因素。因此SFQ算法和SSR算法相比SNEA-IR算法不能找到更合適的下一跳中繼節點，所以它們的傳輸跳數較多。

圖5 數據傳輸跳數Fig.5 Number of data transfer hops

（3）傳輸時延變化比較

圖6說明了這三種算法的傳輸時延，三種算法的傳輸時延都隨著仿真時間的增加逐漸降低，并最終趨于穩定。在實驗結束時，SNEA-IR算法的時延比SFQ算法低332 s，比SSR算法低251 s。由于SFQ算法和SSR算法相比于SNEA-IR算法在傳輸跳數上更多，所以它們的傳輸時延也更大。

圖6 傳輸時延Fig.6 Transmission delay

4 結束語

本文提出了一種基于SDN網絡環境感知的智能路由算法，該算法相比傳統SDN路由算法融合網絡環境中節點的社交屬性和移動屬性兩種因素，并且該算法考慮了節點與目標節點的以往周期和當前時期的兩種相遇可能性與節點未來時期相遇可能性之間關聯，并進行了預測。該算法與文中所提其他結合網絡環境因素的路由算法相比該算法能夠找到更加合適的中繼節點，并且提高了數據傳輸率，降低了端到端時延和傳輸跳數。該算法在考慮網絡環境中的因素時考慮了社交屬性和移動屬性兩個因素，而網絡環境中還有其他因素，下一步工作是繼續尋找并添加其他網絡環境因素來進一步優化算法，使算法性能再有所提升。