基於雙層遞歸神經網絡的應用層組播樹構建方法

2023-07-23 01:44:41

專利名稱：基於雙層遞歸神經網絡的應用層組播樹構建方法
技術領域：
本發明是針對基於代理伺服器的覆蓋網絡上的應用層組播樹構建算法的研究，主要研 究如何基於改進的雙層遞歸神經網絡模型來求解應用層組播路由，涉及到覆蓋網絡、神經 網絡模型、組播路由算法等技術領域。
背景技術：
組播在當今網際網路應用，如視頻會議、在線點播、交互遊戲中佔有很重要的地位。 而網絡層的組播解決方案由於其對網絡設備的協議依賴性影響了其在全網範圍內的布署實 施。與之對應的是在網際網路上構建虛擬的覆蓋網絡(overlay network)並基於這種網絡提 供的應用層組播解決方案，正由於其部署簡單、對網絡設備沒有特殊要求而得到更多關注。 從體系結構上來看，目前的覆蓋網絡主要分為兩類基於代理伺服器(proxy-based)的覆 蓋網絡和基於端主機的(end-host based)的覆蓋網絡一也就是我們平時所指的P2P網絡。 由於代理伺服器擁有比端主機更優的性能、更好的穩定性，因此基於代理伺服器的解決方 案與基於端主機的方案相比具有更髙的帶寬利用率、更少的端到端時延和更高的可靠性。
目前針對基於代理伺服器的覆蓋網絡的組播路由求解方案主要有啟發式路由算法和 神經網絡求解算法兩大類。本文重點研究基於神經網絡模型求解受限應用層組播路由問題。
現有的最優路由神經網絡求解方案主要存在以下的局限性 第一、 主要是針對單播最優路由的求解。
第二、 在單播路由的求解過程中無法引入限制條件，尤其是不等量限制條件。
第三、 所用的神經元數量較多，如由Ali-Kamount提出的著名的H叩field神經網絡其
所需要的神經元數等於網絡中節點數的平方。 由上可見，採用傳統的神經網絡模型很難得到一種受限的應用層組播樹求解方案。因 此，必須另闢蹊徑。

發明內容
技術問題本發明的目的是提出一種基於雙層遞歸神經網絡的應用層組播樹構建方法， 在保證組播路由的最優的同時，滿足應用的限制條件，並儘可能地減少求解過程中使用的 神經元數量，以改善方案的擴展性。 ，
技術方案本發明提出了一種求解受限組播路由的神經網絡模型，如附圖1所示。從 圖中可以看出，模型由到各個組播組成員的神經元矩陣組成。這些矩陣中包括三種類型的 神經元獨立變量神經元、非獨立變量神經元和LP型神經元。其中獨立變量神經元和非獨 立變量神經元對應覆蓋網絡對應的有向圖的邊，這些神經元變量的輸出對應於路由求解問 題的解。輸出為l表示在最終的路由中被選中，否則未被選中。在每個神經元矩陣中通過LP 型神經元的引入保證了組播限制條件的滿足。而通過神經元矩陣之間的連接則保證了最
3終組播路由的最優。
這裡需要定義幾個本文用到的術語。
Kirchoff限制條件若將路徑;v上的各支路決策變量的取值1看作是該支路上有單 位電流通過，取值0看作是零電流，則根據Kirchoff電流定律可知，組成一條有效路徑的 各支路決策變量應滿足下式的約束關係。由於該約束條件來自於Kirchoff電流定律，因此 我們也把它稱為Kirchoff約束條件，它的存在保證了解的有效性。
j=[a').](/=/,■ , _/=/,■ ,
其中
fi如果支路y與節點/關聯，且它的方向背離該節點； w = 如果支路y與節點/關聯，且它的方向指向該節點； Lo如果支路y與節點z'不關聯。
(P代表一個n-l階的向量，形式如下
A = 4 — 1 z' = d 0其它
獨立變量神經元將計算路徑的各決策變量看作是支路電流變量，由網絡理論可知， 連支電流變量是獨立的，而樹支電流變量不獨立，可由連支電流變量來表示。 獨立變量神經元的選取過程如下
(1) 在有向圖中任取一棵樹，並將樹支的編號取為其對應的樹支變量V屍 [vp v2,…,v"-!]T是非獨立的。
(2) 餘下的支路為連支，編號為" W,相對應的連支變量V,-[Vn， V +1， ...，Vm]T
為獨立變量。
在我們定義的神經網絡模型中，每個神經元矩陣中的獨立變量神經元和非獨立變.量神 經元的輸出決定了最終選擇的路由。而非獨立變量神經元依據確定的關係與獨立變量神經 元線性相關。因此路由的求解主要與獨立變量神經元相關。我們模型中的獨立變量神經元
仍然採用的是Hopfield型的神經元，Hopfield網絡理論的核心思想認為網絡從高能狀態 轉移到最小能量狀態，則達到收斂，獲得穩定的解，完成網絡功能。用Hopfield網絡模型 解決優化問題時，權矩陣W己知，目的是求取最大能量E的穩定狀態。為此，必須將待優化 的問題映射到網絡的相應於優化問題可能解的特定組態上，再構造一待優化問題的能量函 數。通過將能量函數和費用函數相比較，求出能量函數中權值和偏流，並以此去調整相應 的反饋權值和偏置，進行迭代計算，直到系統收斂到穩定狀態為止。，後將所得到的穩定 狀態變換為實際優化問題的解。
因此本模型的關鍵是能量函數的定義，我們的能量函數的形式如下
式中第一項保證了所求路徑的費用最小。其中保證了任意一條被選中鏈路的費用在最終的組播路由中只被計算一次。
第二項保證了<€{0, 1}時(/=1,2，...,W)最小。即最終的解只有兩種狀態被選中對 應l，未被選中對應0。
第三項pK。rfz保證了節點限制條件(如連接度限制條件)的滿足，其中A"是模型 中引入的LP型的神經元的傳遞函數，其形式如下
" (15)
W力的取值只在節點限制條件得到滿足時才為零，其餘情況下都大於零。
對上式求導，並由著名的負梯度公式可得獨立變量神經元的運動方程如下
塒 一 況* i一"^f
—a(化3 —6v,2 +2v,) —a乞 .,(4v,3 —6v,2 +2v,) —Ay c, — Af "(.) ,c廣M^)，
乂=| j=i
基於雙層遞歸神經網絡的應用層組播樹構建方法具體包括
a. 各組播組成員把它所知道的鏈路信息，包括鏈路時延、費用、彼此間的連接關係 發送給主節點
b. 主節點根據這些連接關係得到一個全網的拓撲，並把時延及費用與拓撲中的相應邊 關聯起來；
c.主節點針對前文的神經網絡的微分方程採用四階龍格一庫塔法求解，計算時間的步 長At-l(T5s,輸出收斂精度Av40—5，即當前後兩次計算的解之差小於10—5時，就認為解己 求出，轉第f步向各組播成員輸出結果；
d. 採用兩次收斂的過程，首先考慮偏置項Ii,使神經網絡的狀態在最短路徑和度限制
要求收斂到指定的精度由於需要滿足連接度限制的條件，採用一種在循環過程中自適應 地修改參數的方法；每個神經元有一個不同的a^+'值，其中a:對應不同的神經元矩陣，j 為循環次數。在收斂過程中， 一旦時延限制條件得不到滿足，就改變組成那條非法路徑的 鏈路的費用參數，通過神經元的動態性，它們最終將構建一條滿足限制條件的路由；
e. 在二次收斂時，把偏置項L置O，從而讓狀態變量收斂於0或1;
f. 在解穩定後，主節點把對應取值為1的計算結果通知給相應的組播成員節點，當對
應邊取1時，表示該邊將參與到組播數據的傳送中；各組播成員根據收到的數據設置自己 的組播轉發表。
有益效果通過基於改進的雙層遞歸網絡模型得出的組播路由求解方案，能夠解決以 下問題
5利用了雙層遞歸網絡模型引入的基爾霍夫(Kirchoff)限制保證了解的有效性；
(1) 建立了對應於每個組播組成員的神經元矩陣並通過矩陣之間的互聯保證了組 播路由的最優；
(2) 在每個神經元矩陣中引入了線性編程(Linear Programmable:LP)型神經元 從而保證了節點連接度限制條件的滿足。


圖1是本發明的原理圖。
具體實施例方式
提髙所得路徑的準確率與最終結果變量收斂於0或1是矛盾的，但這兩個因素在運動 方程中的作用是相互分離的，費用參數和限制條件僅表現在神經網絡的偏置項即力中。因 此，我們在具體實施過程中採取如下措施先考慮偏置項/,，使神經網絡的狀態在最短路 徑和時延限制要求收斂到一定的精度，然後再將偏置項力置0，從而讓狀態變量收斂於0 或1。即神經網絡的收斂經過兩個階段。在第一個收斂階段中，由於需要滿足連接度限制 的條件，採用一種在循環過程中自適應地修改參數的方法。每個神經元)t具有不同的/9/值，
在收斂過程中， 一旦限制條件t sgn(v，) S A得不到滿足，就使用
/^+1=/^(1+^)改變組成非法路徑的鏈路的權重係數，通過神經元方程的運動，它 們最終將構建一條滿足條件的路由。
式中A 代表神經元矩陣;t中的第/個神經元在第y'次循環過程中的取值。係數/ 和在循環開始時的取值較小以發現一條最小費用路徑，係數A:的取值與前兩者相比要大 一些，但也不能設置得過大，以防止收斂過程進行得過快，不利於所有矩陣之間的協作。
基於雙層遞歸神經網絡的應用層組播樹構建方法具體包括
a. 各組播組成員把它所知道的鏈路信息，包括鏈路時延、費用、彼此間的連接關係 發送給主節點；
b. 主節點根據這些連接關係得到一個全網的拓撲，並把時延及費用與拓撲中的相應邊 關聯起來；
c.主節點針對前文的神經網絡的微分方程採用四階龍格一庫塔法求解，計算時間的步 長At-10—5s,輸出收斂精度Av-l(T5，即當前後兩次計算的解之差小於10—5時，就認為解己 求出，轉第f步向各組播成員輸出結果；
d. 採用兩次收斂的過程，首先考慮偏置項L，使神經網絡的狀態在最短路徑和度限制 要求收斂到指定的精度由於需要滿足連接度限制的條件，採用一種在循環過程中自適應 地修改參數的方法；每個神經元有一個不同的^ +1值，其中/fc對應不同的神經元矩陣，y 為循環次數。在收斂過程中， 一旦時延限制條件得不到滿足，就改變組成那條非法路徑的 鏈路的費用參數，通過神經元的動態性，它們最終將構建一條滿足限制條件的路由；
e. 在二次收斂時，把偏置項I,置O,從而讓狀態變量收斂於O或l;
f. 在解穩定後，主節點把對應取值為1的計算結果通知給相應的組播成員節點，當對 應邊取1時，表示該邊將參與到組播數據的傳送中各組播成員根據收到的數據設置自己的組播轉發表。
運動方程中各項係數的選擇是一項很困難的任務，係數選擇不好會造成最終解的不可 用。雙層遞歸NN的可變係數只有三個。第一個係數是電容附，w越小，時間常數越小， 狀態收斂越快。另一方面，加過分小時，不能保證足夠時間搜索最優值，使計算誤差增大， 甚至無解。第二個係數是比例係數"，它影響路徑計算的精度。w越小，路徑費用項在能量 函數中的份額越小，可能增大神經網絡計算得到的路徑與最短路徑的誤差。"越大，神經網 絡計算得到的路徑越接近最短路徑。但過大時會影響神經網絡收斂於0或1。第三個係數/ 同第二個參數n類似，它同樣影響路徑計算的精度。/越小，連接度限制條件在能量函數中 佔的比例越小，計算出來的路徑可能不能滿足節點的連接度限制條件；/越大，計算所得的 路徑能滿足度限制條件，但同時也會影響神經網絡的收斂。
經過多次模擬實驗，在各邊費用值取l-3之間，ff7、"、/的取值範圍分別在(0.001，0.02)、 (4.5,13.5)、 (7.5,22.5)之間為宜。
權利要求
1. 一種基於雙層遞歸神經網絡的應用層組播樹構建方法，其特徵在於該方法具體包括a. 各組播組成員把它所知道的鏈路信息，包括鏈路時延、費用、彼此間的連接關係發送給主節點；b. 主節點根據這些連接關係得到一個全網的拓撲，並把時延及費用與拓撲中的相應邊關聯起來；c. 主節點針對前文的神經網絡的微分方程採用四階龍格—庫塔法求解，計算時間的步長Δt＝10-5s，輸出收斂精度Δv＝10-5，即當前後兩次計算的解之差小於10-5時，就認為解已求出，轉第f步向各組播成員輸出結果；d. 採用兩次收斂的過程，首先考慮偏置項I1，使神經網絡的狀態在最短路徑和度限制要求收斂到指定的精度由於需要滿足連接度限制的條件，採用一種在循環過程中自適應地修改參數的方法；每個神經元有一個不同的值，其中k對應不同的神經元矩陣，j為循環次數；在收斂過程中，一旦時延限制條件得不到滿足，就改變組成那條非法路徑的鏈路的費用參數，通過神經元的動態性，它們最終將構建一條滿足限制條件的路由；e. 在二次收斂時，把偏置項I1置0，從而讓狀態變量收斂於0或1；f. 在解穩定後，主節點把對應取值為1的計算結果通知給相應的組播成員節點，當對應邊取1時，表示該邊將參與到組播數據的傳送中；各組播成員根據收到的數據設置自己的組播轉發表。
全文摘要
基於雙層遞歸神經網絡的應用層組播樹構建方法，通過能量函數所對應的神經元運動方程求出相應的神經元的權值及偏流，並以此去調整相應的反饋權值和偏置，進行迭代計算，直到系統收斂到穩定狀態為止。在穩定狀態下神經元變量的輸出即為實際優化問題的解。本方法中仍然採用Hopfield神經網絡模型求解最優化問題的思想，但在此基礎上加入雙層遞歸神經網絡模型中的Kirchoff限制條件提高了解的合法性；加入了LP型非線性編程神經元，保證了路由求解過程中限制條件的滿足；同時通過求解單播路由的神經元矩陣之間相對應神經元的關聯保證了最終的組播路由的最優。
文檔編號H04L12/56GK101488913SQ20081024391
公開日2009年7月22日 申請日期2008年12月10日 優先權日2008年12月10日
發明者劉世棟, 張順頤, 攀 王 申請人:南京郵電大學