邵慧瑩，李劍鋒，2

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

0 引 言

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

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

1 標準OLSR 協(xié)議的MPR選擇機制

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

圖1 MPR 選擇性泛洪方式

2 多參數(shù)服務質(zhì)量的多點中繼選擇算法

2.1 QoS的參數(shù)選擇

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

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

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

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

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

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

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

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

式中：Psat——節(jié)點的飽和率。

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

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

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

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

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

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

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

在tk＋1時刻，節(jié)點S 和D 的鏈路穩(wěn)定性計算公式如下

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

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

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

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

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

2.2 QoS－MPR的工作流程

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

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

（2）計算P 節(jié)點的二跳鄰居節(jié)點 （N2（p））數(shù)量。

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

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

1）根據(jù)多參數(shù)QoS對N2（p）中的節(jié)點進行降序排列；

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

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

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

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

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

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

2.3 改進的Dijkstra選路算法

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

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

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

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

3 仿真實驗

3.1 仿真場景

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

表1 仿真場景參數(shù)

3.2 結(jié)果與分析

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

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

圖5 平均端到端延時比較

3.2.2 丟包數(shù)目對比

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

圖6 網(wǎng)絡丟包數(shù)目對比

3.2.3 TC分組數(shù)量對比

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

圖7 TC分組數(shù)量對比

4 結(jié)束語

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

［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 路由協(xié)議mesh網(wǎng)絡的研究［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網(wǎng)絡鏈路認知OLSR 路由協(xié)議 ［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 路由協(xié)議中MPR 節(jié)點安全性研究［J］.計算機技術與發(fā)展，2011，21 （12）：142－144.］

［10］Belhassen M，Belghith AM.Performance evaluation of a cartography enhanced OLSR for mobile multi－h(huán)op 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－h(huán)andoff 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.