基于多參數(shù)服務(wù)質(zhì)量的多點(diǎn)中繼選擇算法

邵慧瑩，李劍鋒，2

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

0 引 言

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

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

1 標(biāo)準(zhǔn)OLSR 協(xié)議的MPR選擇機(jī)制

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

圖1 MPR 選擇性泛洪方式

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

2.1 QoS的參數(shù)選擇

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

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

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

在多點(diǎn)中繼選擇算法工作過(guò)程中，考慮到信號(hào)自身的傳輸時(shí)延，因此有

式中：Tprop（S，D）——信號(hào)自身的傳輸時(shí)延。

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

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

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

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

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

式中：R＿Power——接收信號(hào)功率。

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

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

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

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

LS 的值越小，表示節(jié)點(diǎn)S 的鄰居節(jié)點(diǎn)相對(duì)靜止，位置比較固定，相反，節(jié)點(diǎn)之間的運(yùn)動(dòng)變化比較頻繁。

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

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

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

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

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

式中：a，b，c，d，e——權(quán)重，且有a＋b＋c＋d＋e＝1。

2.2 QoS－MPR的工作流程

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

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

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

（3）將P 節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合中可以達(dá)到N2（p）的節(jié)點(diǎn)合并到MPR（P）中，并刪除N2（p）中相應(yīng)的節(jié)點(diǎn)。

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

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

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

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

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

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

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

圖3 MPR 算法和QoS－MPR算法對(duì)比

2.3 改進(jìn)的Dijkstra選路算法

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

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

改進(jìn)Dijkstra選路算法的工作流程如圖4所示。

圖4 改進(jìn)Dijkstra選路算法的工作流程

3 仿真實(shí)驗(yàn)

3.1 仿真場(chǎng)景

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

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

3.2 結(jié)果與分析

3.2.1 平均端到端延時(shí)性能對(duì)比

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

圖5 平均端到端延時(shí)比較

3.2.2 丟包數(shù)目對(duì)比

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

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

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

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

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

4 結(jié)束語(yǔ)

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

［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）.［蘭鵬，李二濤，何桂仙.基于改進(jìn)OLSR 路由協(xié)議mesh網(wǎng)絡(luò)的研究［J］.杭州電子科技大學(xué)學(xué)報(bào)，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ìn) ［J］.西南交通大學(xué)學(xué)報(bào)，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）. ［溫懷玉，羅光春.無(wú)線Mesh網(wǎng)絡(luò)鏈路認(rèn)知OLSR 路由協(xié)議 ［J］.電子科技大學(xué)學(xué)報(bào)，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é)點(diǎn)安全性研究［J］.計(jì)算機(jī)技術(shù)與發(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.