利用非精確參數的移動互聯網業務感知多目標優化QoS路由算法

2014-01-16 08:04:20戴慧珺趙季紅

西安交通大學學報 2014年2期

關鍵詞：模型

戴慧珺，曲樺，趙季紅，2

（1.西安交通大學電子與信息工程學院，710049，西安；2.西安郵電大學通信工程系，710061，西安）

移動互聯網是以固定核心網為傳輸、無線接入為主的互聯網絡服務［1］。基于 M-Internet（Moble-Internet）的應用催生了許多新業務［2］，使得基于移動終端的移動互聯網服務質量保證技術（Quantity of Service，QoS）面臨巨大挑戰。目前可行的技術方案是使用網絡虛擬技術來屏蔽多個物理網絡的差異，利用覆蓋網和動態智能路由技術進行跨域傳輸的流量控制和帶寬保障［3］。虛擬覆蓋網不改變物理網絡基礎架構，從應用層優化業務QoS，在網絡擴容受限的條件下，QoS路由可在路徑選擇時實現全局資源利用和負載的最優化［4］，因此，覆蓋網結合QoS路由算法有利于解決移動互聯網絡中端到端QoS問題。

QoS路由作為通信網絡技術領域的核心問題之一，應用背景由Internet、IP網絡［5-6］發展到P2P網絡、無線傳感網絡［7］和 Ad-Hoc、MANET 網絡［8］，算法主要有 QUEST［9］、PBSP［5］。上述研究采用的方法包括建立多約束多目標QoS優化模型［10-11］，根據近似算法得到解集，或者使用啟發式算法，諸如智能蟻群來實現網絡狀態的QoS認知［12-13］等。在實際的動態網絡環境中，網絡節點所能獲得的各節點和鏈路狀態（特別是無線鏈路狀態）信息并不是精確的［14-15］。常見方案是根據多目標優化理論重新建立網絡模型，給出相應求解機制和實施方案從而設計網絡［16-17］。移動互聯網具有異構融合網絡的特點，在應用層上采用覆蓋網全局路由方法可以提高業務的QoS［18］，但覆蓋網高度抽象和信息匯聚的特性導致相應節點獲取的QoS參數具有不精確性，因此QoS路由必須結合非精確網絡狀態信息和業務感知來執行。

本文針對移動互聯網應用背景，根據網絡非精確參數特點，采用多目標優化理論來建立多QoS目標決策模型；利用覆蓋網這一虛擬平臺，對業務進行感知和匹配獲得相應業務類型以及QoS需求，針對多個QoS參數的特點，結合概率和隸屬度函數獲得該多目標優化模型的解集。實驗結果表明，該算法所選擇的路徑在各項QoS目標都滿足的情況下，可有效減小時間開銷，提高網絡資源利用率和QoS滿意率，從而優化資源配置調度。

1 多QoS目標優化模型

設網絡G＜V，E＞，其中V=｛v1，v2，…，vm｝為節點集合，E=｛e1，e2，…，en｝為鏈路集合，設s∈V為源節點，d∈｛V-｛s｝｝為目的節點，則p（s，d）=（s，v1，v2，…，vi，d）為源節點s到目的節點d 的一條路由路徑。

定義1 多目標優化模型在限定約束下，最小化和最大化需同時滿足的模型可以表示為

式中：x=［x1，x2，…，xD］為 D 維決策變量；y為目標函數；N為優化目標總數；fn（x）為第n個子目標函數；g（x）為K項不等式約束條件；h（x）為M 項等式約束條件，約束條件構成了可行域；xd-min和xd-max為向量搜索的上、下限。

定義2 理想點求解設多目標最優化問題的可行域為D，如果對?x∈D，都滿足F（x＊）＜F（x），則稱x＊為D的多目標絕對最優解，絕對最優解構成解集合，解集存在一個理想點fix＊，滿足

理想點求多目標優化的方法是在解空間內找到一點作為確定的解，該點與理想點距離最近，距離遠近的評價應用了泛函中距離的概念。

定義3 隸屬度函數設給定論域X，存在集合A，元素x∈X，元素x到A 的任一映射μA（x），μA：X→R，x→μA（x），μA（x）為元素x對集合A 的隸屬度函數。

由于大多數固定網絡存在方向對稱性，因此基于核心骨干網的覆蓋網可以被模型化為無向網絡［19］。業務要求是約束，同時，QoS路由還應達到減小傳輸代價及提高業務滿意率等多個目標，因此多目標優化可用來作為本文算法的理論模型。

2 業務感知模型

常見業務根據應用層不同服務分為語音業務、IPTV、E-mail等，每類業務有大致的QoS要求，例如VoIP業務，要求最小帶寬大于8KB／s，端到端時延最大不超過100ms，誤幀率小于1%［20］。當該業務在UMTS網絡傳輸時，其幀被打上實時會話類業務標簽，路由器解析該類業務時可獲得相應的QoS要求。

業務感知的作用是識別并還原網絡分組所屬的業務類型，包括P2P、視頻、音頻等。本文設計一種識別速度較快且識別精度合適的感知模型，把感知結果作為多目標QoS優化模型的約束條件輸入。模型結構如圖1所示。

圖1 業務感知模型

在該模型中，業務首先進入端口識別模塊，按照常見端口映射表識別，如表1所示，業務與端口數據源進行比對，識別成功則給出業務類型；未識別則進入特征碼識別模塊，特征碼用于識別相應協議的關鍵字信息和P2P特征。特征碼匹配根據特征庫采用了快速字符串匹配，能提高深度包探測方法的精度。

表1 常見端口映射表

該模塊通過在網絡中對數據包的截獲將數據包還原為相應業務，如感知結果為VoIP業務，則得到業務帶寬Bpath≥8KB／s，端到端時延Dpath≤100ms，誤幀率Lpath≤0.01。

3 QoS參數處理

QoS路由算法包括收集處理網絡QoS狀態和尋找合適路徑兩部分［21］。

3.1 參數分類

從數據處理角度，QoS參數可分為可加性、可乘性和瓶頸參數。可加性參數表示路徑參數為路徑上鏈路參數的累加值，例如，時延Dpath=∑Dlink。可乘性參數表示路徑參數為路徑上所有鏈路參數的乘性值，例如，丟包率1-Lpath=∏（1-Llink）。瓶頸類參數表示路徑參數為路徑上所有鏈路參數的最小值，例如，帶寬Bpath=min［Blink］，根據分類可以獲得從鏈路參數到路徑參數的計算方法。不同參數采用不同隸屬度函數處理，能夠全面考慮不同類型參數對鏈路性能的影響。

3.2 不精確參數處理

單次測量和非精確值的網絡狀態將影響路由算法的性能，導致網絡負載能力惡化，例如丟包率和阻塞率的上升等。相關研究中，一些算法根據參數所在的區間進行彈性處理，取其邊界值［22］；另一些結合參數分布函數和統計特性采用概率方法進行處理［23］。不精確參數給QoS路由算法帶來的問題是網絡鏈路更新策略、網絡拓撲和鏈路代價函數對QoS路由帶來的影響［24］。本文算法綜合概率方法和隸屬度預處理非精確參數，根據多目標QoS方程尋路獲得優化路徑。

覆蓋網 QoS參數xi（i=1，2，…，n）多次測量值服從正態分布，以帶寬參數為例，某條鏈路的帶寬參數Bi，i∈（1，…，n），其測量值服從正態分布 N（μ，σ2），根據n次帶寬測量結果，其帶寬值為…，，其極大似然函數為

3.3 構建隸屬度矩陣

由3.2節得到QoS參數計算值用于構建隸屬度矩陣，作為非精確QoS參數處理的最后一步，也是多目標QoS模型求解的第一步，隸屬度矩陣可以對多種屬性多個維度的QoS參數進行均質化。隸屬度方法和數據的歸一化相比，更側重多量綱的數據本質屬性和統一處理。使用隸屬度矩陣，輸入是多個QoS參數列表，輸出是根據QoS約束獲得的優選序列。

將業務需求等約束條件作為濾波進行轉換。根據單個目標的隸屬度公式，其構造為

多目標模型中的QoS參數有m個，根據3.2節其鏈路狀態信息可表示為向量xi=（ˉB，ˉD，ˉL，ˉJ，…），每個向量經過隸屬度轉換，形成μ（xi），μ（xi）=（x′B，x′D，x′L，x′J，…），評價指標共有n個，進行隸屬度轉換后，可構建m×n隸屬度矩陣μ

隸屬度矩陣可以作為多目標模型的輸入，對模型進行求解。在給定n個QoS參量后，該矩陣可利用每個參量的權值，通過模糊綜合評價等方法對QoS路徑進行排序。

4 多目標QoS路由尋路

4.1 構建多目標QoS方程

根據本文第2節業務感知模型，獲得傳輸業務QoS約束g（x）≤0，要求業務的時延和丟包率在一定范圍內，同時需盡可能最小化傳輸代價min（f1（epath，vpath）），和最大化資源利用率 max（f2（epath，vpath），f3（epath，vvpath））。f2和f3是資源利用函數，可理解為網絡剩余帶寬和剩余計算能力等資源。

式中：xpath=｛epath，vpath｝。在網絡G＜V，E＞中，邊為E=｛ei｝，節點為V=｛vi｝，測量獲得ei的各個QoS指標值，根據3.2節不精確參數處理，得到ei=。根據3.1節，得到鏈路參數到路徑參數的計算過程。

4.2 理想點法解方程

根據4.1節的式（6）可以建立方程組。式（6）中，最大化maxF（xi）表示剩余資源的最大化，意味著占用資源最小化，max（F（xi））=F-min（ˉF（xi））。求解以最小化為優化目標的方程min（F（xi）），獲得解f1x＊；相應地，求解以最大化為優化目標的方程max（F（x））得到解f2x＊。

根據定義2理想點法求解方程組，首先分別求各個方程的解，然后根據多個解構成的解空間搜索可行路徑的排序，找距離解空間距離最短的點。

5 仿真實驗

5.1 仿真參數

本算法的仿真實現通過omnet仿真工具結合Matlab輸出驗證分析。oment模擬網絡資源和業務場景得到業務發生的仿真數據。具體仿真環境和參數如下。

本文選取對業務QoS區分較大、對用戶QoE（Quantity of Experience）影響較大的節點計算能力、鏈路帶寬、時延和丟包率這4個參數作為本實驗具體參數，記為xi=（ˉC，ˉB，ˉD，ˉL）。

仿真環境基于覆蓋網，根據omnet仿真工具繪制，使用多個智能路由器（服務器）節點結合普通路由器，在不指定物理位置的情況下生成隨機網絡。提取概率為30%的智能節點獲得覆蓋網拓撲，其智能節點數范圍是［0，200］，采用臨近鄰接法（即兩個覆蓋節點之間的鏈路不存在其他覆蓋節點）構造覆蓋鏈路。鏈路參數根據網絡agent的監測獲得測量值。無向鏈路帶寬范圍為［0，10］MB／s，延時為［50，1 000］ms；每個節點計算能力為［0，500］。業務請求達到一定速率，服從泊松分布，服務請求的源節點和目的結點隨機指定；被接收服務的服務時間服從指數分布，時間小于200s。網絡拓撲結構如圖2所示。

圖2 網絡拓撲結構

5.2 實驗過程

仿真中和本文算法進行性能比較的算法是PB-SP和OSPF兩種算法，QUEST算法等經典算法和本算法優化目標不一致。PBSP算法將鏈路帶寬作為主要因素執行最短路徑算法，OSPF算法運行在本覆蓋網拓撲上，代價和帶寬成反比。本文從全網優化性能、算法運行時間開銷和資源優化等若干方面進行評價。

根據5.1節的仿真參數，考慮單次仿真結合多次隨機仿真作為測試基本數據。定義QoS滿意率為全網性能指標，QoS滿意率為被接受的業務數除以到達的業務數。圖3是單次仿真執行一段時間后本文算法和PBSP算法QoS滿意率的對比。OSPF不考慮除帶寬之外的QoS約束，因此不做QoS滿意率的統計和比較。

圖3 兩種算法的QoS滿意率曲線對比

當網絡處于飽和狀態時，新業務到達，網絡拒絕處理，此階段內的QoS滿意率降到最低為0；直到網內業務結束，釋放資源，QoS滿意率將上升到最高。PBSP算法是線性加權多約束的方法，加權了鏈路QoS指標，而本文算法結合了業務感知利用理想點解來解該多目標QoS模型，兼顧鏈路和節點的性能。因此，同樣的網絡環境下，本文算法QoS滿意率稍高于PBSP算法。

如圖4所示，與OSPF、PBSP算法相比，本文算法時間開銷較大，時間復雜度較大，PBSP算法和OSPF算法時間復雜度一致，而OSPF算法的時間開銷較小。

圖4 3種算法時間開銷對比

圖5 為兩種算法選取的若干條路徑鏈路的資源占用率對比，對比參量為帶寬占用百分比，兩種算法在傳送數據量相等的情況下，由于選用不同路徑，其帶寬占用率不同。本文算法充分考慮了資源優化問題，因此在13條路徑上資源占用率在35%和65%之間，而PBSP算法的資源占用率最大接近80%，可見其選路過程沒有刻意回避帶寬資源有限的路徑，容易造成鏈路的局部擁塞。

圖5 兩種算法資源占用率對比

以一定的置信區間增加overlay節點，圖6為OSPF算法與本文算法執行時間對比。當節點數較少，OSPF算法時間開銷明顯小于本文算法，隨著節點數目增加到一定程度時，本文算法的時間增長小于OSPF算法。原因是本文算法執行多目標模型求解的計算過程在網絡規模較小時，其時間開銷非常明顯，當節點數目增多時，理想點法能夠減少QoS路由的部分計算量，而OSPF算法隨著節點數目增多，處理計算量增長較快。因此，中型以上規模的網絡中，本文算法的時間性能較傳統算法更好。

圖6 算法時間開銷與覆蓋網節點數目的關系

6 結論

基于覆蓋網的虛擬化方法解決應用層的業務問題是移動互聯網的一個重要的研究手段。QoS路由技術研究了如何在約束條件下滿足業務流的QoS需求，并在路徑選擇上實現了全局資源利用和負載的最優化。多目標優化模型是本文QoS路由的基本模型，在業務感知的條件下實現業務約束的輸入，在多量綱的基礎上盡可能實現多個目標的優化。為體現算法的優點，與傳統最短路徑算法和經典覆蓋網QoS路由算法進行多方面比較，從網絡整體性能和時間開銷代價上表明，算法在某種程度上能夠實現在完成約束的同時又能夠優化資源配置，實現業務的QoS保障。

［1］羅軍舟，吳文甲，楊明.移動互聯網：終端，網絡與服務［J］.計算機學報，2011，34（11）：2029-2051.

LUO Junzhou，WU Wenjia，YANG Ming.Mobile internet：terminal devices，networks and services ［J］.Chinese Journal of Computers，2011，34（11）：2029-2051.

［2］ KIM H W，CHAN H C，GUPTA S.Value-based adoption of mobile internet：an empirical investigation［J］.Decision Support Systems，2007，43（1）：111-126.

［3］ DUAN Zhenhai，ZHANG Zhili，HOU Y T.Service overlay networks：SLAs，QoS，and bandwidth provisioning［C］∥Proceedings of the 10th IEEE International Conference on Network Protocols.Piscataway，NJ，USA：IEEE，2002：870-883.

［4］ RAO Ruan，WANG Ruchuan.Multi-path QoS routing using genetic algorithm for LEO satellite networks［J］.Computer and Microelectronics，2011，20（1）：17-20.

［5］ XUE Guoliang，ZHANG Weiyi，TANG Jian，et al.Polynomial time approximation algorithms for multiconstrained QoS routing ［J］.IEEE／ACM Transactions on Networking，2008，16（3）：656-669.

［6］ LI Zhi，MOHAPATRA P.QRON：QoS-aware routing in overlay networks［J］.IEEE Journal on Selected Areas in Communications，2004，22（1）：29-40.

［7］馬震遠，周杰，陳楚，等.一種分段測量保證QoS約束的任播通信模型［J］.西安交通大學學報，2010，44（2）：44-49.

MA Zhenyuan，ZHOU Jie，CHEN Chu，et al.An anycast communication model with QoS constraints based on segmental measurement［J］.Journal of Xi’an Jiaotong University，2010，44（2）：44-49.

［8］ GULATI M K，KUMAR K.QoS routing protocols for mobile ad hoc networks：a survey［J］.International Journal of Wireless and Mobile Computing，2012，5（2）：107-118.

［9］ GU Xiaohui，NAHRSTEDT K，CHANG R N，et al.QoS-assured service composition in managed service overlay networks［C］∥Proceedings of the 23rd International Conference on Distributed Computing Systems.Piscataway，NJ，USA：IEEE，2003：194-201.

［10］XUE Guoliang，SEN A，ZHANG Weiyi，et al.Finding apath subject to many additive QoS constraints［J］.IEEE／ACM Transactions on Networking，2007，15（1）：201-211.

［11］MISRA S，XUE Guoliang，YANG Dejun.Polynomial time approximations for multi-path routing with bandwidth and delay constraints［C］∥Proceedings of the 2009International Conference on Computer Communications.Piscataway，NJ，USA：IEEE，2009：558-566.

［12］亓晉，張順頤，孫雁飛，等.基于自主蟻群算法的認知網絡多約束QoS路由算法［J］.南京郵電大學學報：自然科學版，2012，32（6）：86-91.

QI Jin，ZHANG Shunyi，SUN Yanfei，et al.Cognitive networks multi-constraint QoS routing algorithm based on ant colony algorithm ［J］.Journal of Nanjing University of Posts and Telecommunications：Natural Science，2012，32（6）：89-91.

［13］曹雪松，胡瑞敏，王朝萍.覆蓋網絡中一種公平負載均衡QoS路由算法［J］.計算機學報，2011，34（9）：1650-1659.

CAO Xuesong，HU Ruimin，WANG Zhaoping.A fair load balancing QoS ［J］.Chinese Journal of Computers，2011，34（9）：1650-1659.

［14］GUERIN R A，ORDA A.QoS routing in networks with inaccurate information：theory and algorithms［J］.IEEE／ACM Transactions on Networking，1999，7（3）：350-364.

［15］ MASIP-BRUIN X，MARIN-TORDERA E，YANNUZZI M，et al.Reducing the effects of routing inaccuracy by means of prediction and an innovative linkstate cost［J］.IEEE Communications Letters，2010，14（5）：492-494.

［16］CUI Xunxue，LIN Chuang，WEI Yaya.A multiobjective model for QoS multicast routing based on genetic algorithm ［C］∥Proceedings of the 23rd International Conference on Computer Networks and Mobile Computing.Piscataway，NJ，USA：IEEE，2003：49-53.

［17］CHEN Lei，HEINZELMAN W B.QoS-aware routing based on bandwidth estimation for mobile ad hoc networks［J］.IEEE Journal on Selected Areas in Communications，2005，23（3）：561-572.

［18］唐明董，張國清，楊景，等.互聯網可擴展路由［J］.軟件學報，2010，21（10）：2524-2541.

TANG Mingdong，ZHANG Guoqing，YANG Jing，et al.Scalable routing for the internet ［J］.Journal of Software，2010，21（10）：2524-2541.

［19］李偉，徐正全，楊鑄.應用于移動互聯網的Peer-to-Peer關鍵技術［J］.軟件學報，2009，20（8）：2199-2213.

LI Wei，XU Zhengquan，YANG Zhu.Peer-to-Peer key technologies in mobile internet ［J］.Journal of Software，2009，20（8）：2199-2213.

［20］HANDLEY M，SCHOOLER E，SCHULZRINNE H，et al.Session initiation protocol［S］∥Proposed Internet Standard.New York，USA：ACM，1997：2540-2543.

［21］林闖，李寅，萬劍雄.計算機網絡服務質量優化方法研究綜述［J］.計算機學報，2011，34（1）：1-14.

LIN Chuang，LI Yin，WAN Jianxiong.Optimization approaches for QoS in computer networks：a survey［J］.Chinese Journal of Computers，2011，34（11）：1-14.

［22］SU Zhou，OGURO M，OKADA Y，et al.Overlay tree construction to distribute layered streaming by application layer multicast ［J］.IEEE Transactions on Consumer Electronics，2010，56（3）：1957-1962.

［23］AN Jing，PANGALOS P，AGHVAMI A H.Fuzzy non-dominance multipath link-state routing framework for network routing management with inaccurate information［C］∥Proceedings of the 2012IEEE Globecom Workshops.Piscataway，NJ，USA：IEEE，2012：886-890.

［24］SANGUANKOTCHAKORN T，PERERA N.Hybrid multi-constrained optimal path QoS routing with inaccurate link state［C］∥Proceedings of the 2010 9th International Conference on Networks.Piscataway，NJ，USA：IEEE，2010：321-326.

［本刊相關文獻鏈接］

陳家旭，唐亞哲，寧京宣，等.移動自組網中節點興趣導向的人類運動模型.2013，（12）：110-115.［doi：10.7652／xjtuxb 2013 12019］

陳秀真，李生紅，凌屹東，等.面向拒絕服務攻擊的多標簽IP返回追蹤新方法.2013，（10）：13-17.［doi：10.7652／xjtuxb 201310003］

李強，秦濤，管曉宏，等.對稱性的起因：非業務性網絡流量新特性的挖掘與探索.2013，（8）：19-25.［doi：10.7652／xjtuxb 201308004］

杜友田，辛剛，鄭慶華.融合異構信息的網絡視頻在線半監督分類方法.2013，（7）：96-101.［doi：10.7652／xjtuxb201307 018］

林軍，倪宏，孫鵬，等.一種服務質量可信的按需服務組合方法.2013，46（4）：112-117.［doi：10.7652／xjtuxb201304019］

曹步清，李兵，劉建勛.一種服務質量可信的按需服務組合方法.2013，（2）：131-138.［doi：10.7652／xjtuxb201302022］

夏秦，王志文，盧柯.入侵檢測系統利用信息熵檢測網絡攻擊的方法.2013，（2）：14-19.［doi：10.7652／xjtuxb201302003］

陳國強，王宇平.采用離散粒子群算法的復雜網絡重疊社團檢測.2013，（1）：107-113.［doi：10.7652／xjtuxb201301021］

李曉艷，張海林，郭超平，等.一種異步的認知無線電網絡跳頻算法.2012，46（12）：30-35.［doi：10.7652／xjtuxb201212 006］

劉陽，馮志勇，尉志清，等.Nakagami-m信道下認知中繼網絡的中斷概率上界閉式解模型.2012，46（10）：95-100.［doi：10.7652／xjtuxb201210017］

宋婧，叢犁，葛建華，等.雙層網絡中一種協作博弈的動態資源分配方法.2012，46（10）：89-94.［doi：10.7652／xjtuxb2012 10016］

杜文超，陳庶樵，胡宇翔.面向網絡流的自適應正則表達式分組匹配算法.2012，46（8）：49-53.［doi：10.7652／xjtuxb2012 08009］

梁慶偉，姚道遠，鞏思亮.一種保障時延能量高效的無線傳感器網絡路由協議.2012，46（6）：48-52.［doi：10.7652／xjtuxb 201206009］

李彬，王文杰，殷勤業，等.無線傳感器網絡節點協作的節能路由傳輸.2012，46（6）：1-6.［doi：10.7652／xjtuxb201206001］

陳衡，錢德沛，伍衛國，等.傳感器網絡基于鄰居信息量化的能量平衡路由.2012，46（4）：1-6.［doi：10.7652／xjtuxb2012 04001］

劉逵，劉三陽，馮海林.雙信道無線傳感器網絡移動代理路由算法.2012，46（02）：113-118.［doi：10.7652／xjtuxb201202 019］

任浩，王勁林，尤佳莉.一種高效的對等網絡流媒體數據調度算法.2011，45（6）：20-26.［doi：10.7652／xjtuxb201106004］

楊文靜，楊新宇，董翅勇.移動Ad Hoc網絡中提高路由穩定性的動態備份多徑路由.2010，44（12）：16-21.［doi：10.7652／xjtuxb201012004］

翟社平，魏娟麗，李增智.利用服務質量參數值預測的 Web服務選擇方法.2010，44（6）：57-61.［doi：10.7652／xjtuxb 201006011］

劉剛，崔剛，劉宏偉，等.面向移動節點不確定性特征的自組網路由協議.2010，44（6）：46-50.［doi：10.7652／xjtuxb2010 06009］