[發明專利]一種基于蜂群算法的自組織QoS路由方法無效
| 申請號： | 200910010202.3 | 申請日： | 2009-01-21 |
| 公開（公告）號： | CN101478802A | 公開（公告）日： | 2009-07-08 |
| 發明（設計）人： | 王興偉;易秀雙;郭磊;王宇;溫占考;王衛東;董明;陳強;付遙 | 申請（專利權）人： | 東北大學 |
| 主分類號： | H04W40/02 | 分類號： | H04W40/02 |
| 代理公司： | 沈陽東大專利代理有限公司 | 代理人： | 梁 焱 |
| 地址： | 110004遼寧省*** | 國省代碼： | 遼寧;21 |
| 權利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關鍵詞： | 一種 基于 蜂群 算法 組織 qos 路由 方法 | ||
1.一種基于蜂群算法的自組織QoS路由方法，按如下步驟：
步驟A：接收到鄰居路由器發送的數據報文；
步驟B：根據數據報文的目的地址是否為單播地址判斷報文類型是否為單播報文；
其特征在于：根據步驟B是單播報文，則執行步驟C，否則執行步驟G；
步驟C：進入單播建模的QoS路由方法；
步驟D：初始化路由器寄存器，發送前向蜂群agent尋路，調用蜂群算法，其中agent負責收集記錄當前網絡狀態信息；
步驟E：考查路徑評價值Jpath，找到符合用戶請求的路徑；
步驟F：轉到步驟K；
步驟G：進入組播建模的QoS路由方法，給定組播請求：R(vs，vd，Δbwd，Δdld，Δjtd，Δlsd，pd)，為其構造一棵組播樹，其中vs代表源節點，vd代表目的節點，Δbwd代表帶寬需求約束區間，Δdld代表延遲需求約束區間，Δjtd代表延遲抖動需求約束區間，Δlsd代表出錯率需求區間，pd代表用戶愿付費用上限；
步驟H：初始化路由器寄存器，構建組播樹；
步驟I：組播樹費用分攤；
在形成組播樹以后，由于所選邊是選用用戶共用的，所以資費也理所應當由選用用戶共同分擔，分攤的原則是：用戶獨自占用該條路徑所需付的費用越高則用戶在組播樹付費中分攤的部分越大，
設定源節點到每一個組成員的路徑所需付費的集合為：
Wp＝{pay1，pay2，...，payn-1，payn}式中payn為每一個組成員的路徑所需付費，n＝1，2，…，N，N屬于自然數，則第i個組成員vi所需分攤的組播樹費用比例為：
式中i∈n，k∈n；
步驟J：計算組播樹評價值JT，找出符合用戶請求的路徑；
步驟K：根據計算出的符合用戶請求的路徑將數據報文轉發到下一跳路由器；
所述的步驟D中調用蜂群算法包括：
步驟D1：初始化路由器寄存器，設置最大迭代次數TIN，設置已迭代次數IN＝0，設定每次迭代發送蜜蜂agent數量BN，已發送的蜜蜂agent數量bn＝0，路徑評價值Jpath＝∞，?可行路徑為空，初始化網絡，將網絡劃分為若干個的域，每一個區域就是一個搜索域，規定每個搜索域內有一個代表節點，域內ip地址最小的節點被選舉為代表節點，如果該節點失效，則選舉下一個具有較大一些的ip地址的節點作為代表節點，凡是從代表節點出發在給定跳數內到達的節點均屬于同一個搜索域；
步驟D2：在源節點判斷目的節點是否屬于源節點的搜索帶，如果是，則設定發送短距離蜜蜂，如果不是，則設定發送長距離蜜蜂，如果不知道，則設定長、短距離蜜蜂各占一半比例發送；
步驟D3：IN←IN+1，源節點以間隔Δt發出BN個蜜蜂agent，每發送一個agent就bn←bn+1，初始化每一個蜜蜂agent，其中：蜜蜂agent序號seq＝bn；
步驟D4：前向agent記錄路徑，將經歷過的節點保存起來，同時記錄有關的網絡狀態信息，前向蜜蜂agent在源節點被發出后，在網絡中的每一個經過的節點按下面步驟執行行為；
步驟D41：判斷當前蜜蜂agent跳數是否超限，如果是，則蜜蜂agent死亡；
步驟D42：如果源節點和目的節點不在同一個域內，則探路蜜蜂agent先以目的節點所在域代表節點為目的節點進行探路；當到達該域代表節點后，再以實際目的節點為目的節點進行探路；
步驟D43：如果當前節點的直接下一跳節點有本次路由目的節點，則考察與該節點之間的邊是否滿足用戶請求約束，如滿足，則蜜蜂agent跳轉到目的節點，轉到步驟D46；
步驟D44：在當前節點實現小世界邊；
步驟D45：在當前節點進行下一跳選擇；
步驟D451：在當前節點，將路由總次數計數器增加1；
步驟D452：實現小世界行為；
步驟D453：如果下一跳選擇成功返回，則蜜蜂agent前行至該節點；
步驟D454：如果下一跳選擇失敗，蜜蜂agent死亡；
步驟D46：前向蜜蜂agent任務完成；
步驟D5：當前向agent到達目的節點時，觸發產生一個繼承前向agent相關信息的后向agent，后向agent沿著原路徑的信息，從目的節點反向到達源節點，同時更新路由表中的信息；
步驟D51：在目的節點，根據前向蜜蜂agent信息，根據公式?UUP為路徑或組播樹上的用戶效用，UNP則為網絡提供商效用，計算路徑評價值JP，并賦予生成的?后向agent，其中，αup，αnp是對用戶的傾斜權值，0＜αup，αnp＜1，αup+αnp＝1，將前向蜜蜂agent找到的路徑賦予后向蜜蜂agent；
步驟D52：對于長距離蜜蜂，在未反向飛到目的節點所在域的代表節點以前，更新IFZ路由表，在飛過目的節點所在域代表節點之后，還要更新IFR路由表；
步驟D53：后向agent按保存的路徑信息，反向跳到上游節點，然后更新IFZ或IFR表；在當前節點，蜜蜂將路由成功次數計數器增加1，如果蜜蜂agent在當前節點引入了小世界邊，則更新小世界邊表；
步驟D54：判斷后向蜜蜂agent是否到達源節點，如果未到達，則跳轉至步驟D53；
步驟D55：將后向蜜蜂agent攜帶路徑的評價值和當前路徑評價值進行比較，如果agent攜帶路徑的評價值小于當前路徑評價值，則將新路徑保存為當前可行路徑；
步驟D56：后向agent任務完成，調用蜂群算法結束；
所述的步驟D44在當前節點實現小世界邊包括：
步驟D441：判斷當前agent是否正在使用小世界邊，如果是，則直接取出小世界邊作為下一跳節點；否則，跳轉至步驟D443；
步驟D442：判斷該下一跳節點能否滿足用戶請求約束，如果能，蜜蜂agent選擇該節點作為下一跳節點，保存當前節點與該節點之間邊的QoS信息和成本信息，蜜蜂agent在當前節點行為結束，然后前行至該下一跳節點；否則，蜜蜂agent死亡；
步驟D443：考察蜜蜂agent的序列號，判斷該agent是否為本次迭代發送中的最后一個，如果不是，則跳轉至步驟D45；
步驟D444：考察當前節點小世界邊表，是否存在到達目的節點的小世界邊，如果不存在，則跳轉至步驟D45；
步驟D445：將小世界邊存入蜜蜂agent，并設置蜜蜂agent使用小世界邊，然后蜜蜂agent記錄該節點地址，跳轉至D441；
所述的步驟D452實現小世界行為包括：
如果蜜蜂agent的序列號為偶數，則隨機選擇下一跳節點；否則，進行計算選擇下一跳，計算對應邊的用戶滿意度值計算公式：?式中，αbw、αdl、αjt和αls分別為各QoS參數的權重系數，αbw、αdl、αjt、αls∈[0，1]，且αbw+αdl+αjt+αls＝1，Wl是位于0和1之間的數值，gbwl表示帶寬滿意度、gdll表示延時滿意度、gjtl表示延時抖動滿意度、glsl代表出錯率滿意度，計算第i個節點的路由成功率：?式中rcs是成功路由次數計數器，rct是節點總路由次數計數器，當節點被采用到一次路由中去時，rct就增1，而當該次路由成功后，rcs就增1，為保證時效性，rcs、rct值每隔一定周期Δtrc就清零；計算第i個節點與本次路由目的地址的相近度：將32位地址從左向右逐位掃描比較二進制位，如果相同就繼續掃描，如果不同就結束，記錄相同的位數Mik，則相近度?Mik代表兩個32位的ip地址做二進制比較，位數相同的個數，取值范圍在0-32之間，計算下一條選擇概率：proj＝Pij×Wj×Ij×Vj，其中：Pij為當前節點信息素表中對應Nj的信息素濃度，Wj表示節點j的用戶滿意度值、Ij表示節點j的路由成功率、Vj表示節點j的相近度，根據proj，選出對應proj值最大的下一跳節點作為下一跳選擇；
所述的步驟E考查路徑評價值Jpath，找到符合用戶請求的路徑包括：
步驟E1：在源節點等待一段時間Δt后，考查路徑評價值Jpath；
步驟E2：如果Jpath＜∞，則算法成功找到符合用戶請求的路徑，在源節點將當前保留路徑加入小世界表，轉至步驟K；
步驟E3：如果Jpath＝∞，則判斷IN是否小于TIN，如果是，則轉至步驟D3，否則路由失敗；
所述的步驟H初始化路由器寄存器，構建組播樹包括：
步驟H1：初始化路由器寄存器，設置迭代次數CN，已迭代次數cn＝0，組播樹評價值Jtree＝∞，當前可行組播樹為空；
步驟H2：將所有組成員按帶寬請求由大到小排列，設定待處理組成員集合W＝{v1，v2，...，vn-1，vn}，vn為待處理組成員，n＝1，2，…，N，N屬于自然數，已處理組成員集合A＝Φ，可行路徑集合P＝Φ，其中Φ為空集合；
步驟H3：取vd∈W，利用基于螞蟻網絡的單播路由算法，由vs向vd尋找一條滿足成員vd請求約束的可行路徑pd，如果未找到，則此次構建組播樹失敗，跳轉到步驟J3；
步驟H4：將節點vd從W刪除，并加入A；
步驟H5：檢查可行路徑pd上是否含有位于W中的組成員，如果沒有，則跳轉到步驟H7；?
步驟H6：如果pd上含有位于W中的組成員，判斷這些組成員的請求約束能否在pd得到滿足，將能被滿足的節點從W刪除，并加入A；
步驟H7：將可行路徑pd加入集合P；
步驟H8：若集合W不為空，則跳轉到步驟H1；
步驟H9：將可行路徑中P中的路徑拼成一棵組播樹，在成樹的過程中，每個組成員的請求約束都要被滿足，并且不能出現環，否則，此次構建組播樹失敗，跳轉至步驟J3；
所述的步驟J計算組播樹評價值JT，找出當前可行組播樹包括：
步驟J1：根據公式計算組播樹評價值JT；
步驟J2：如果JT＜Jtree，Jtree為當前可行組播樹的評價值，則用計算得到的組播樹代替當前可行組播樹，Jtree＝JT；
步驟J3：cn←cn+1，cn表示已迭代次數，若cn＜CN，跳轉到步驟H；
步驟J4：判斷Jtree＜∞是否成立，如果成立，則算法成功，否則算法失敗。?
該專利技術資料僅供研究查看技術是否侵權等信息，商用須獲得專利權人授權。該專利全部權利屬于東北大學，未經東北大學許可，擅自商用是侵權行為。如果您想購買此專利、獲得商業授權和技術合作，請聯系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/200910010202.3/1.html，轉載請聲明來源鉆瓜專利網。
