基于多參數服務質量的多點中繼選擇算法

邵慧瑩，李劍鋒，2

（1.中國計量學院 經濟與管理學院，浙江 杭州310018；2.上海理工大學 管理學院，上海200093）

0 引 言

針對優化鏈路狀態路由 （optimized link state routing，OLSR）協議［1］中的多點中繼 （multipoint relays，MPR）選擇算法［2］問題，國內外眾多學者和研究機構進行了大量、廣泛而深入的研究，提出一些多點中繼選擇算法［3］。傳統多點中繼選擇算法通過從其鄰居節點中選擇多個中繼節點建立進行路由路徑，它們均沒有全面考慮服務質量 （QOS）參數，如節點飽和度、鏈路穩定性和帶寬等，建立的數據路由并非最優，而且魯棒性比較差［4，5］。為此，文獻 ［6］提出一種采用遺傳算法選擇最小MPR 集的多點中繼選擇算法；文獻 ［7］提出一種基于節點剩余能量的多點中繼選擇算法；文獻 ［8］提出一種基于多參數QoS的多點中繼選擇算法，一定程度上解決傳統多點中繼選擇算法存在的不足。

為提高移動自組織網絡 （mobile ad hoc network，MANET）的服務質量，提出一種基于多參數服務質量的多點中繼選擇算法 （QoS－MPR），并通過仿真對比實驗測試算法的有效性和優越性。實驗結果表明，本文算法減少了網絡丟包率和平均延時，能夠獲得比較理想的數據傳輸路由。

1 標準OLSR 協議的MPR選擇機制

OLSR 協議是一種在經典鏈路狀態 （link state，LS）基礎上發展起來的、適合于MANET 的路由協議，通過根據最小跳數建立分組轉發的最短路徑［10］。多點中繼（MPR）是OLSR 協議的核心，選擇性泛洪廣播信息，其主要目的是減少相同控制信息的重復轉發次數，防止廣播風暴現象出現，從而降低廣播分組的數量。對于MANET 中的任意一個節點，其鄰居節點可以劃分為兩類：MPR 節點和非MPR 節點，非MPR 節點不能轉發控制信息，而MPR節點不僅可以處理控制信息，而且可以轉發控制信息，第一個節點從鄰居節點中選擇MPR 節點，組成MPR 節點集，MPR 集可以覆蓋其全部的兩跳節點，OLSR 協議通過MPR 節點集將數據轉發到目的節點，因此MPR 節點集越小，OLSR 協議的性能越好，MPR 選擇性泛洪方式如圖1所示［11］。

圖1 MPR 選擇性泛洪方式

2 多參數服務質量的多點中繼選擇算法

2.1 QoS的參數選擇

QoS參數的選擇直接影響算法的復雜度和效率，本文選擇的QoS參數主要包括端到端的延時、帶寬、節點的飽和率、鏈路穩定性、丟包率等。

（1）端到端延時。端到端延時是指數據包從源節點S到目標節點D 的時間延遲，其計算公式為

式中：T（i）——節點i的傳輸時延；k——路由上的節點數，Tp（i）——節點i的處理時延。

在多點中繼選擇算法工作過程中，考慮到信號自身的傳輸時延，因此有

式中：Tprop（S，D）——信號自身的傳輸時延。

（2）網絡帶寬。網絡帶寬是一個非常重要的QoS參數，其描述數據鏈路為數據包提供的傳輸速率，帶寬越高，可以傳輸的數據量就越大，節點S 和D 之間的帶寬定義如下

式中：mess＿size——接收數據包的大小；Tmess（i，j）——接收該數據包的延時。

（3）節點發送飽和度。由于MANET 采用TDMA 制式的通信方式，在一個周期內，每一點發送的數據流大小有限，當一個節點待發數據包排隊的時間過長，這就表示該節點處于飽和狀態，如果該節點被選擇作為MPR 節點，那么導致網絡數據包轉發嚴重滯后，對整個網絡的吞吐量產生不利影響。相關研究結果表明，靠近網絡中心的節點轉發大流量數據的概率要高于其它節點，其網絡負載必然越大，易出現網絡擁塞現象，數據包丟失的概率增加［12］。在MANET，不可避免出現數據包排隊現象，而OLSR 協議發送的任何消息都有一個有效時間（Vtime），當Vtime＝0時，則該消息無效而被丟棄，根據OLSR 協議的這種特性，通過每個節點的待發數據包大小來判斷該節點是否飽和。根據文獻 ［13］，鏈路的飽和率PRsat可以根據節點的飽和率計算得到，具體計算公式如下

式中：Psat——節點的飽和率。

（4）鏈路穩定性。在MANET 過程中，由于節點的可移動性，網絡拓撲結構具有動態變化特點，從而導致數據的鏈路極不穩定，但在極短時間，網絡拓撲結構相對固定，因此鏈路具有一定的穩定性。鏈路質量變化主要由于節點的發射功率變化引起的，因此可以根據歷史鏈路狀態對鏈路穩定性進行評價。MANET 的鏈路穩定性評價指標主要包括兩部分：本地鏈路穩定估值 （local stability，LS）和鄰居鏈路穩定估值 （neighbor stability，NS）。定義一個穩定向量函數為

式中：R＿Power——接收信號功率。

當SS（d，tk）小于零時，表示MANET 的鏈路質量變差，S、D 兩者相隔比較遠，不然S、D 兩者相互靠近。在tk＋1時刻，本地鏈路穩定估值 （LS）計算公式如下

式中：l＝1，2，…，k。

LS 的值越小，表示節點S 和點D 之間相對靜止，兩者之間的間隔變化不大，位置比較固定，相反，兩者之間的運動變化比較頻繁，兩者之間的間隔變化比較大。

在tk＋1時刻，鄰居鏈路穩定估值 （NS）計算公式如下

LS 的值越小，表示節點S 的鄰居節點相對靜止，位置比較固定，相反，節點之間的運動變化比較頻繁。

在tk＋1時刻，節點S 和D 的鏈路穩定性計算公式如下

式中：α、β——LS 和NS 的權值，且有α＋β＝1。

TR（S，D，tk）值越小，表明源節點S 和D 的相對運動頻率較低，鏈路穩定性較好，鏈路質量較高，TR（S，D，tk）越大，表明節點S 和D 的運動變化很頻繁，鏈路越不穩定，鏈路質量比較低。

（5）丟包率。丟包率指由于節點移動等因素的干擾，數據包在網絡傳輸過程中數據包丟失的百分比率。設源節點S發送的數據包為Totalsent，那么丟包率的計算公式如下

綜合上述可知，任意一個時刻的網絡性能，必須考慮多個QoS參數的綜合影響，因此本文根據端到端延時、帶寬、節點發送飽和度和鏈路穩定性概率、丟包率構建多參數的QoS性能評價函數，具體計算公式為

式中：a，b，c，d，e——權重，且有a＋b＋c＋d＋e＝1。

2.2 QoS－MPR的工作流程

QoS－MPR算法不僅考慮鄰居節點的覆蓋范圍，還考慮節點的多參數的QoS，QoS－MPR 算法的工作步驟具體如下：

（1）清空節點P 的MPR節點集合，即有MPR（P）＝φ。

（2）計算P 節點的二跳鄰居節點 （N2（p））數量。

（3）將P 節點的鄰居節點集合中可以達到N2（p）的節點合并到MPR（P）中，并刪除N2（p）中相應的節點。

（4）在N2（p）中，如果有節點沒有被MPR（P）中節點所覆蓋，則進行如下處理：

1）根據多參數QoS對N2（p）中的節點進行降序排列；

2）選擇多參數QoS最大的節點i，如果該節點可以覆蓋到N2（p）中節點，則將其合并到MPR（P）中，并將其從N2（p）中刪除；

3）在N2（p）中，如果仍然還有節點沒有被MPR（P）中的節點所覆蓋，則重復步驟 （4），繼續處理。

綜合上述可知，QoS－MPR 算法的工作流程如圖2所示。

MPR 算法與QoS－MPR 算法的對比結果如圖3 所示。從圖3可知，在MPR 算法中，節點C因為二跳節點覆蓋度最大，被選為中繼節點，但是節點C 與鄰居節點之間的鏈路質量不穩定，易出現節點擁塞、丟包現象；QoS－MPR 算法根據節點的QoS作為權值進行MPR 節點選擇，在選擇最優轉發鏈路的質量條件下，實現了二跳鄰居節點的全部覆蓋，性能得到了一定的提升。

圖2 QoS－MPR算法的工作流程

圖3 MPR 算法和QoS－MPR算法對比

2.3 改進的Dijkstra選路算法

在標準OLSR 路由協議中，Dijkstra選路算法通過路徑跳數作為權值選擇節點構建數據轉發的路由，屬于跳數最小路由選擇法，沒有全面考慮QoS參數，因此跳數最小的路由不一定是最優的數據路由［14］。為此，本文對Dijkstra選路算法進行改進，不僅考慮路徑跳數，而且還考慮節點的延時、帶寬、鏈路穩定性等因素對路徑的影響，因此點S 和D 之間的路由質量的評價數 （Path（S，D，i，t））定義如下

式中：Hop——路由上的跳數；i——S 和D 之間的一條路徑。

改進Dijkstra選路算法的工作流程如圖4所示。

圖4 改進Dijkstra選路算法的工作流程

3 仿真實驗

3.1 仿真場景

為測試基于QoS－MPR 算法的OLSR 協議 （以下簡稱改進OLSR 協議）性能，在Intel 4核2.9GHz的CPU，4 GRAM，Windows XP操作系統個人計算機上，采用Open＋＋軟件進行仿真測試。仿真場景參數設置見表1。采用標準OLSR 協議進行對照實驗，從延時、丟包數目以及TC分組數量等方面對它們的性能進行綜合分析。

表1 仿真場景參數

3.2 結果與分析

3.2.1 平均端到端延時性能對比

兩種OLSR協議的平均端到端延時仿真結果如圖5所示。從圖5可以清楚看出，相對于標準OLSR 協議，改進OLSR協議的平均端到端延時更小，這主要由于改進OLSR協議在MPR選擇和路由選擇過程中，綜合考慮了QoS參數的影響，選擇鏈路質量較好的路由進行數據轉發，數據包排隊時間減少，加快了數據轉發的速度，降低了平均端到端延時。

圖5 平均端到端延時比較

3.2.2 丟包數目對比

兩種OLSR 協議的網絡丟包數目的對比結果如圖6所示，從圖6可以明顯看出，改進的OLSR 協議丟包數目明顯要少于標準OLSR 協議，這主要是因為改進OLSR 協議充分考慮了節點的發送飽和度，減少數據包的排隊時間，在有效時間內，可以選擇最優的鏈路將數據包發送出去，降低網絡丟包數目，降低丟包概率。

圖6 網絡丟包數目對比

3.2.3 TC分組數量對比

兩種OLSR 協議的TC分組數量仿真結果如圖7所示。從圖7可知，相對于標準OLSR 協議，改進OLSR 協議的TC分組數量大幅度降低，這主要是因為TC 控制消息由MPR 節點廣播和轉發，由于引入多參數QoS評價指標選擇MPR 節點，減少MPR 節點集合的冗余節點和TC 分組轉發數量，提高了OLSR 協議的性能。

圖7 TC分組數量對比

4 結束語

針對標準OLSR 協議的MPR 選擇算法的不足，提出一種基于多參數服務質量的多點中繼選擇算法，將延時，帶寬等QoS參數引入到MPR 選擇和路由選擇算法中，最后采用仿真實驗測試其性能。實驗結果表明，相對于標準OLSR協議，基于QoS－MPR算法的OLSR 協議可以更好地選擇MPR 節點集合，減少了MPR 集合中的節點冗余，大幅度減少數據轉發的平均端到端延時延和丟包數目，選擇質量更優的數據鏈路，提高了數據轉發的成功率，具有更高的實際應用價值。

［1］Santhi G，Nachiappam A.A survey of QoS routing protocols for mobile ad hoc networks ［J］.International Journal of Computer Science ＆Information Technology，2010，2 （4）：125－132.

［2］Narangerei Dashbyamba，Ceiimuge Wu，Satoshi Ohzahata，et al.An improvement of OLSR using fuzzy logic based MPR selection ［C］／／Network Operations and Management Symposium，2013：1－6.

［3］LAN Peng，LI Ertao，HE Guixian.Research of mesh network based on the improved OLSR routing protocol ［J］.Journal of Hangzhou Dianzi University，2013，33 （4）：54－57 （in Chinese）.［蘭鵬，李二濤，何桂仙.基于改進OLSR 路由協議mesh網絡的研究［J］.杭州電子科技大學學報，2013，33 （4）：54－57.］

［4］Toutouh J，Alba E.Multi－objective OLSR optimization for VANETs［C］／／IEEE 8th International Conference on Wireless and Mobile Computing，Networking and Communications，2012：571－578.

［5］Boushaba A，Benabbou A，Benabbou R.Optimization on OLSR protocol for reducing topology control packets［C］／／IEEE International Conference on Multimedia Computing and Systems，2012：539－544.

［6］GAO Yu，ZENG Huashen，ZHANG Hong.Improvement of multipath routing algorithm based on OLSR and source routing［J］.Journal of Southwest Jiaotong University，2010，45 （3）：424－429 （in Chinese）.［高雨，曾華燊，張洪.基于OLSR 和源路由的多徑路由算法的改進 ［J］.西南交通大學學報，2010，45 （3）：424－429.］

［7］Kots A，Kumar M.The fuzzy based QMPR selection for OLSR routing protocol［J］.Wireless Network，2014，20 （1）：1－10.

［8］WEN Huaiyu，LUO Guangchun.Link cognitive－based OLSR routing protocol for wireless Mesh networks ［J］.Journal of University of Electronic Science and Technology of China，2011，40 （2）：303－307 （in Chinese）. ［溫懷玉，羅光春.無線Mesh網絡鏈路認知OLSR 路由協議 ［J］.電子科技大學學報，2011，40 （2）：303－307.］

［9］ZHANG Dengyin，WANG Zhenxing.Security study of MPR nodes in OLSR routing protocol ［J］.Computer Technology and Development，2011，21 （12）：142－144 （in Chinese）.［張登銀，王振興.OLSR 路由協議中MPR 節點安全性研究［J］.計算機技術與發展，2011，21 （12）：142－144.］

［10］Belhassen M，Belghith AM.Performance evaluation of a cartography enhanced OLSR for mobile multi－hop ad hoc networks［C］／／IEEE Wireless Advanced，2011：149－155.

［11］Mcauley A，Sinkar K，Kant L.Tuning of reinforcement learning parameters applied to OLSR using a cognitive network design tool［C］／／IEEE Wireless Communications and Networking Conference，2012：2786－2791.

［12］Cervera G，Barbeau M，Kranakis E.QoS and security in link state routing protocols for MANETs ［J］.Wireless Days，2013：22 （7）：1－6.

［13］Zhichao M，Weibo Y，Dawei N.The position－aware routing protocol for pre－handoff on OLSR in vehicular networks［C］／／IEEE International Conference on intelligent System Design and Engineering Application，2012：1156－1159.

［14］Sondi P，Gantsou D，Lecomte S.A multiple－metric QoSaware implementation of the optimized link state routing protocol［J］.Communication Networks and Distributed Systems，2014，12 （4）：381－400.