《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 通信與網(wǎng)絡(luò) > 設(shè)計(jì)應(yīng)用 > 基于協(xié)作中繼的高吞吐量機(jī)會網(wǎng)絡(luò)路由算法
基于協(xié)作中繼的高吞吐量機(jī)會網(wǎng)絡(luò)路由算法
2017年電子技術(shù)應(yīng)用第5期
任 智,,王中永,張 勇
重慶郵電大學(xué) 移動通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室,,重慶400065
摘要: 基于Barter機(jī)制的機(jī)會網(wǎng)絡(luò)路由算法在數(shù)據(jù)分組交易過程中存在的僵局問題,,導(dǎo)致網(wǎng)絡(luò)吞吐量降低,為此,,提出一種基于協(xié)作中繼的路由算法(Routing Algorithm based on Cooperative Relays,,RACR),,在Barter機(jī)制中采用協(xié)作中繼機(jī)制,引入多方交易激活數(shù)據(jù)分組的單向傳遞,,同時(shí)優(yōu)化分組刪除的判定條件,,對分組交易僵局問題加以有效解決,從而提高網(wǎng)絡(luò)吞吐量,,降低數(shù)據(jù)分組端到端時(shí)延。仿真結(jié)果表明,,與現(xiàn)有的Barter路由算法和DT(Direct Transmission) 路由算法相比,,RACR路由算法的網(wǎng)絡(luò)吞吐量提高了7.9%以上,分組平均端到端時(shí)延則至少降低了8.5%,。
中圖分類號: TN92,;TP393.04
文獻(xiàn)標(biāo)識碼: A
DOI:10.16157/j.issn.0258-7998.2017.05.030
中文引用格式: 任智,王中永,,張勇. 基于協(xié)作中繼的高吞吐量機(jī)會網(wǎng)絡(luò)路由算法[J].電子技術(shù)應(yīng)用,,2017,43(5):123-126.
英文引用格式: Ren Zhi,Wang Zhongyong,,Zhang Yong. A high-throughput routing algorithm for opportunistic networks based on cooperative relays[J].Application of Electronic Technique,2017,,43(5):123-126.
A high-throughput routing algorithm for opportunistic networks based on cooperative relays
Ren Zhi,,Wang Zhongyong,,Zhang Yong
Chongqing Key Lab of Mobile Communication Technology,,Chongqing University of Posts and Telecommunications,, Chongqing 400065,China
Abstract: To address the trading deadlock problem in exchanging data packets of Barter routing algorithm for opportunistic networks, a new routing algorithm based on cooperative relays, RACR, is proposed. RACR introduces cooperative relays strategy in the message exchange process, brings in multi-player trade to invoke unidirectional transmission of data packets, and optimizes the judgment of packet deleting, so that it can effectively solve the deadlock problem in message exchange process, which improves the network throughput and reduces the data packets end-to-end delay. Theoretical analysis and simulation results show that RACR can improve network throughput by 7.9%, and the decrease in the average end-to-end delay is more than 8.5%, as compared to Barter routing algorithm and Direct Transmission(DT) routing algorithm.
Key words : opportunistic networks;Barter,;game theory,;cooperative relays,;routing algorithms

0 引言

    機(jī)會網(wǎng)絡(luò)[1-2]是一種不需要在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間存在完整鏈路、利用節(jié)點(diǎn)移動帶來的相遇機(jī)會實(shí)現(xiàn)通信的時(shí)延和分裂可容忍的無線自組織網(wǎng)絡(luò),,在軍事,、災(zāi)難救助以及偏遠(yuǎn)野外地區(qū)等領(lǐng)域有著廣泛的應(yīng)用。目前,,機(jī)會網(wǎng)絡(luò)的研究是基于節(jié)點(diǎn)具有良好的協(xié)作性,,然而,由于機(jī)會網(wǎng)絡(luò)中節(jié)點(diǎn)的資源有限,,為節(jié)約資源,,節(jié)點(diǎn)都存在一定的自私性,,自私節(jié)點(diǎn)通常會拒絕為其他節(jié)點(diǎn)轉(zhuǎn)發(fā)消息,這種自私行為勢必會嚴(yán)重影響機(jī)會網(wǎng)絡(luò)正常的路由和數(shù)據(jù)轉(zhuǎn)發(fā)功能,,從而導(dǎo)致網(wǎng)絡(luò)性能退化,。

    目前,國內(nèi)外對于含自私節(jié)點(diǎn)的機(jī)會網(wǎng)絡(luò)的研究已經(jīng)取得了一些成果,,人們提出了各種激勵(lì)機(jī)制來激勵(lì)節(jié)點(diǎn)協(xié)作[3-7],,尤其是近年來越來越多地采用了經(jīng)濟(jì)學(xué)方法中的博弈理論[4-6]?;贐arter機(jī)制的算法是一類典型的基于博弈論的機(jī)會網(wǎng)絡(luò)路由算法,,該算法基于互惠機(jī)制,博弈雙方互相交換彼此感興趣或者具有潛在價(jià)值的消息,。BUTTYAN L等[4]提出了Barter機(jī)制,,主要用于激勵(lì)網(wǎng)絡(luò)中自私節(jié)點(diǎn)對自己不感興趣分組的“存儲-攜帶-轉(zhuǎn)發(fā)”。LIN C S等[5]提出了基于Barter機(jī)制的針對對等網(wǎng)絡(luò)(P2P)流媒體系統(tǒng)中自私節(jié)點(diǎn)的機(jī)制,。ZHANG C等[6]結(jié)合信譽(yù)機(jī)制中虛擬貨幣交易的特點(diǎn)改進(jìn)了原始Barter機(jī)制,,提出了一種全新的激勵(lì)范式C4,,但未考慮分布式網(wǎng)絡(luò)中節(jié)點(diǎn)的自私性,。由上可知,,現(xiàn)有基于Barter機(jī)制的路由算法仍然是僅考慮兩兩節(jié)點(diǎn)間進(jìn)行的交易,未考慮分組交易存在的僵局問題,,有進(jìn)一步改善的需要,。

    本研究基于上述研究成果,,并在文獻(xiàn)[4]的基礎(chǔ)上,,提出了一種全新的角度——基于協(xié)作中繼的博弈模型,對歸一化時(shí)間內(nèi)的機(jī)會網(wǎng)絡(luò)吞吐量及時(shí)延進(jìn)行了分析,,仿真實(shí)驗(yàn)證實(shí)了本模型的有效性,。

1 網(wǎng)絡(luò)模型與問題描述

1.1 系統(tǒng)描述

    設(shè)任一含自私節(jié)點(diǎn)的機(jī)會網(wǎng)絡(luò)中,,自私節(jié)點(diǎn)只轉(zhuǎn)發(fā)自己感興趣的數(shù)據(jù)分組,。BUTTYAN L等[4]提出任何分組都有其潛在價(jià)值,當(dāng)前不感興趣的分組將來可用來交換感興趣的分組,。在Barter機(jī)制中,,節(jié)點(diǎn)感興趣的分組初始價(jià)值量為1,不感興趣的分組初始價(jià)值量是自身采取的博弈策略Si={S1,,S2,,…,Sm}(0<Si<1),。部分變量定義如表1所示,。

tx5-b1.gif

1.2 機(jī)會網(wǎng)絡(luò)的博弈模型

    含自私節(jié)點(diǎn)的機(jī)會網(wǎng)絡(luò)中節(jié)點(diǎn)具有自私而有理性的特點(diǎn),在模型方面與傳統(tǒng)的機(jī)會網(wǎng)絡(luò)有所不同,,故作出如下定義,。

    定義1 博弈模型:機(jī)會網(wǎng)絡(luò)的博弈模型為G=[V,{Si},,{πi}],;其中,節(jié)點(diǎn)集合V={v1,,v2,,…,vn},,n>1,,即為博弈參與者;策略集合Si={S1,,S2,,…,Sm},,1≤m≤n(n-1),,表示節(jié)點(diǎn)對自己不感興趣分組與感興趣分組的比值;收益函數(shù)?仔i(S1,,S2,,…,Sm)表示網(wǎng)絡(luò)中參與者采取策略后網(wǎng)絡(luò)的實(shí)際吞吐量,。

    定義2 數(shù)據(jù)分組屬性:含自私節(jié)點(diǎn)的機(jī)會網(wǎng)絡(luò)中,,數(shù)據(jù)分組主要有兩種屬性:分組興趣屬性ζ(0<ζ<<1)與分組價(jià)值折扣屬性(見式(3))。

    定義3 實(shí)際吞吐量模型:實(shí)際吞吐量Gi(0≤Gi(t)≤1)是節(jié)點(diǎn)i在每個(gè)歸一化時(shí)間內(nèi)成功傳遞分組獲得的累計(jì)價(jià)值,,節(jié)點(diǎn)i的該值可以在一個(gè)理想的情況下表示為:

tx5-gs1-2.gif

tx5-gs3-5.gif

    在RACR中,,博弈參與者的收益只依賴于其選擇的博弈策略,且博弈參與者在其策略空間中選取惟一確定的策略進(jìn)行博弈,,因此,,這個(gè)博弈有對稱的純策略均衡解,。

    綜上分析可知,不難判斷一個(gè)策略組合{s′}是否是納什均衡,。對任意參與者i(i∈V),,若i采取背叛策略能夠獲得更多的收益,則{s′}不是納什均衡,。由于參與者具有相同的收益函數(shù),,若{s′}是參與者i的最優(yōu)策略,則{s′}也是其他參與者的最優(yōu)策略,。

1.3 問題描述

    (1)僵局問題:由于交易的公平性要求,,分組交換由可交換數(shù)目小的一方?jīng)Q定,進(jìn)行等量交換,。若一個(gè)節(jié)點(diǎn)有分組需要轉(zhuǎn)發(fā),,對方節(jié)點(diǎn)無該節(jié)點(diǎn)需要的分組或無足夠分組與前者交換,將導(dǎo)致網(wǎng)絡(luò)陷入僵局,,造成網(wǎng)絡(luò)等待時(shí)延,,稱之為“僵局問題”。

    (2)現(xiàn)有的Barter機(jī)制在數(shù)據(jù)分組交易過程中存在冗余交互操作,。

    (3)根據(jù)現(xiàn)有Barter機(jī)制,,價(jià)值量達(dá)到某一閾值的消息就簡單丟棄,然而,,這樣很可能刪除即將到達(dá)目的地址的分組,,增大了消息傳輸時(shí)延。

2 RACR算法

    本文提出一種基于協(xié)作中繼的高吞吐量機(jī)會網(wǎng)絡(luò)路由算法——RACR,。RACR算法采用引入?yún)f(xié)作中繼節(jié)點(diǎn)的轉(zhuǎn)發(fā)方式,,對分組交易僵局問題加以有效解決,并重新設(shè)計(jì)滿足協(xié)作中繼的分組交易過程,,引入多方交易以激活數(shù)據(jù)分組的單向傳遞,,從而削減數(shù)據(jù)分組傳遞次數(shù)。同時(shí),,對價(jià)值量小于閾值的分組先判斷其目的地址是否是鄰居節(jié)點(diǎn),,從而提高分組傳送成功率,降低數(shù)據(jù)分組傳輸時(shí)延,。

2.1 RACR算法新機(jī)制

2.1.1 協(xié)作中繼

    RACR算法針對現(xiàn)有Barter路由算法分組交易過程中的交易僵局問題,,引入?yún)f(xié)作中繼機(jī)制加以解決??紤]如下網(wǎng)絡(luò)場景:假設(shè)節(jié)點(diǎn)u,、v已完成兩兩之間的交易或節(jié)點(diǎn)u、v不存在相應(yīng)的分組交易,若節(jié)點(diǎn)v仍有節(jié)點(diǎn)u需要而不能與之交易的分組,。同時(shí),,節(jié)點(diǎn)u、v收到共同的鄰居節(jié)點(diǎn)w廣播的目的地址為v的分組索引,,若節(jié)點(diǎn)w在節(jié)點(diǎn)v與w、u與w兩兩交易完成后,,節(jié)點(diǎn)u,、v根據(jù)節(jié)點(diǎn)w的分組索引計(jì)算發(fā)現(xiàn)節(jié)點(diǎn)w仍有節(jié)點(diǎn)v需要的分組,同時(shí)節(jié)點(diǎn)u也有節(jié)點(diǎn)w需要的分組,。

    協(xié)作中繼節(jié)點(diǎn)的選取思路為:當(dāng)網(wǎng)絡(luò)出現(xiàn)上述情況時(shí),,如圖1(a)所示,根據(jù)Barter算法的原理,,消息交易將陷入僵局,。圖1(b)表示RACR算法的分組交易示意圖,如果網(wǎng)絡(luò)出現(xiàn)上述情況,,則節(jié)點(diǎn)w將會向節(jié)點(diǎn)v發(fā)送一個(gè)額外分組,,節(jié)點(diǎn)v收到節(jié)點(diǎn)w發(fā)送的額外分組后會給節(jié)點(diǎn)u發(fā)送一個(gè)額外分組。最后,,節(jié)點(diǎn)u給節(jié)點(diǎn)w需要的一個(gè)額外的分組,。若存在能滿足以上描述條件的節(jié)點(diǎn),即是協(xié)作中繼節(jié)點(diǎn),。

tx5-t1.gif

2.1.2 分組傳遞次數(shù)削減

    RACR算法引入多方交易以激活數(shù)據(jù)分組的單向傳遞,,對數(shù)據(jù)分組的傳遞次數(shù)進(jìn)行削減??紤]如下網(wǎng)絡(luò)場景:節(jié)點(diǎn)u,、v和w在同一通信范圍內(nèi),節(jié)點(diǎn)u需要通過節(jié)點(diǎn)v交易獲取節(jié)點(diǎn)v中的分組,,節(jié)點(diǎn)v需要獲取節(jié)點(diǎn)u中的分組用來交換節(jié)點(diǎn)w中的分組,,同時(shí)節(jié)點(diǎn)u也有節(jié)點(diǎn)w需要的分組。

    分組傳遞次數(shù)削減思路為:當(dāng)網(wǎng)絡(luò)出現(xiàn)上述情況時(shí),,如圖1(a)所示,,在Barter路由算法中,中間節(jié)點(diǎn)v進(jìn)行一次分組交換需要收,、發(fā)2個(gè)分組才能完成交易,。如圖1(b)所示,在RACR算法中,,首先發(fā)現(xiàn)節(jié)點(diǎn)間存在上述關(guān)系的節(jié)點(diǎn)向需要自身數(shù)據(jù)分組的節(jié)點(diǎn)發(fā)送一個(gè)數(shù)據(jù)分組,,收到該額外分組的理性節(jié)點(diǎn)進(jìn)行相同的操作,最后完成一個(gè)公平的交易。則RACR算法的中間節(jié)點(diǎn)v僅需要收,、發(fā)1個(gè)分組,,從而實(shí)現(xiàn)分組傳遞次數(shù)的削減,減少數(shù)據(jù)分組的冗余交互操作,。

2.1.3 分組刪除判定優(yōu)化

    原始Barter路由算法中,,節(jié)點(diǎn)對價(jià)值小于分組刪除閾值的數(shù)據(jù)分組采取簡單的丟棄策略。然而,,雖然刪除的分組價(jià)值量小,,但很有可能即將到達(dá)分組的目的節(jié)點(diǎn)。在RACR算法中,,節(jié)點(diǎn)對價(jià)值量低于刪除閾值的分組,,首先判斷該分組的目的地址是否為該節(jié)點(diǎn)的鄰居節(jié)點(diǎn),若是則發(fā)起新的分組交易,,否則直接刪除該分組,。這樣在不影響網(wǎng)絡(luò)開銷的前提下,提高網(wǎng)絡(luò)吞吐量,,同時(shí)降低傳輸時(shí)延,。

2.2 RACR算法操作

    RACR算法主要操作步驟如下:

    (1)節(jié)點(diǎn)u、v相遇,,按Barter機(jī)制兩兩之間交易完畢,。此時(shí),若節(jié)點(diǎn)v仍有節(jié)點(diǎn)u需要而不能與之交易的分組,,則進(jìn)行步驟(2),,否則結(jié)束;

    (2)節(jié)點(diǎn)u,、v收到公共鄰居節(jié)點(diǎn)w發(fā)送的分組索引,,根據(jù)節(jié)點(diǎn)w的分組索引計(jì)算判斷節(jié)點(diǎn)w是否符合協(xié)作中繼節(jié)點(diǎn)的要求。若符合,,則進(jìn)行步驟(3),,否則結(jié)束;

    (3)若節(jié)點(diǎn)u通過計(jì)算,,最先獲知協(xié)作中繼節(jié)點(diǎn)w的參與情況,。節(jié)點(diǎn)u向節(jié)點(diǎn)w發(fā)送一個(gè)節(jié)點(diǎn)w需要的分組,節(jié)點(diǎn)w收到u發(fā)送的分組后,,立即向節(jié)點(diǎn)v發(fā)送一個(gè)節(jié)點(diǎn)v需要的分組,。同理,節(jié)點(diǎn)v向節(jié)點(diǎn)u發(fā)送一個(gè)u需要的分組,。

3 仿真

3.1 仿真環(huán)境

    本文使用OPNET軟件作為仿真平臺,,選取Barter算法[4]和DT算法[8]作為比較對象,,在相同仿真條件下分析比較它們的網(wǎng)絡(luò)吞吐量、時(shí)延等性能,。主要仿真參數(shù)設(shè)置如表2所示,。

tx5-b2.gif

3.2 仿真結(jié)果及分析

    (1)歸一化網(wǎng)絡(luò)吞吐量

    由圖2可知,與DT算法和Barter算法相比,,RACR算法在網(wǎng)絡(luò)吞吐量上提高了7.9%以上,。主要原因是:①采用協(xié)作中繼機(jī)制,從而選取合適的協(xié)作中繼節(jié)點(diǎn),,對分組交易僵局問題加以有效解決,;②對價(jià)值量小于刪除閾值的分組首先判斷其目的地址是否為鄰居節(jié)點(diǎn),若是則發(fā)起新的分組交易,,從而提高網(wǎng)絡(luò)吞吐量。

tx5-t2.gif

    (2)分組平均端到端時(shí)延

    由圖3可知,,RACR算法的分組平均端到端時(shí)延低于DT和Barter算法,。主要原因是:①RACR算法通過引入?yún)f(xié)作中繼節(jié)點(diǎn),解決了交易的僵局問題,,有效地減少網(wǎng)絡(luò)等待時(shí)延,;②分組傳遞次數(shù)削減機(jī)制通過引入多方交易以激活數(shù)據(jù)分組的單向傳遞,從而加快數(shù)據(jù)分組的交換,,縮短數(shù)據(jù)分組交換的時(shí)延,。

tx5-t3.gif

    (3)歸一化控制開銷

    由圖4可知,RACR算法能夠明顯減少歸一化控制開銷,。開銷減少的原因主要是RACR協(xié)議引入?yún)f(xié)作中繼節(jié)點(diǎn),,提高了消息的交付率,減少了消息在網(wǎng)絡(luò)中的傳輸?shù)钠骄鴶?shù),。同時(shí),,優(yōu)化了分組交易機(jī)制,削減了分組交換次數(shù),,減少了消息交易過程中的額外開銷,,從而降低歸一化控制開銷。

tx5-t4.gif

    (4)分組傳送成功率

    由圖5可知,,與DT算法和Barter算法相比,,RACR算法顯著提高了分組傳送成功率。主要原因是:①引入?yún)f(xié)作中繼節(jié)點(diǎn),,增加了分組交易機(jī)會,;②優(yōu)化分組刪除判定機(jī)制,刪除緩存消息之前先判斷其目的地址是否是其鄰居節(jié)點(diǎn),,若是則重新發(fā)起分組交易,,從而提高了數(shù)據(jù)分組傳送成功率。

tx5-t5.gif

4 結(jié)束語

    本文通過深入研究博弈理論在含有自私節(jié)點(diǎn)的機(jī)會網(wǎng)絡(luò)的應(yīng)用,提出了一種基于協(xié)作中繼的高吞吐量機(jī)會網(wǎng)絡(luò)路由算法RACR,。RACR算法通過在Barter機(jī)制中采用協(xié)作中繼機(jī)制并引入多方交易以激活數(shù)據(jù)分組的單向傳遞,,同時(shí)優(yōu)化分組刪除的判定條件。仿真結(jié)果顯示,,與DT路由算法和Barter路由算法相比,,RACR算法能夠更加有效地促使含自私節(jié)點(diǎn)的機(jī)會網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)分組交易,從而增加網(wǎng)絡(luò)吞吐量,,降低數(shù)據(jù)分組端到端時(shí)延,。

參考文獻(xiàn)

[1] XIONG Y P,SUN L M,,NIU J W,,et al.Opportunistic networks[J].Journal of Software,2009,,20(1):124-137.

[2] 任智,,黃勇,陳前斌.機(jī)會網(wǎng)絡(luò)路由協(xié)議[J].計(jì)算機(jī)應(yīng)用,,2010,,30(3):723-728.

[3] WU F,CHEN T,,ZHONG S,,et al.A game-theoretic approach to stimulate cooperation for probabilistic routing in opportunistic networks[J].IEEE Transactions on Wireless Communications,2013,,12(4):1573-1583.

[4] BUTTYAN L,,DORA L,F(xiàn)ELEGYHAZI M,,et al.Barter trade improves message delivery in opportunistic networks[J].Ad Hoc Networks,,2010,8(1):1-14.

[5] LIN C S,,CHENG Y C.A Barter-based incentive mechanism for peer-to-peer media streaming[C].The 13th IEEE International Symposium on Consumer Electronics.Kyoto:IEEE Press,,2009:871-875.

[6] ZHANG C,ZHU X,,SONG Y,,et al.C4:A new paradigm for providing incentives in multi-hop wireless networks[C].INFOCOM,2011 Proceedings IEEE.Shanghai:IEEE Press,,2011:918-926.

[7] 劉期烈,,候鵬翔.機(jī)會網(wǎng)絡(luò)中激勵(lì)節(jié)點(diǎn)檢測策略研究[J].重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)報(bào)),2015,,27(2):266-272.

[8] SPYROPOULOS T,,PSOUNIS K,,RAGHAVENDRA C S.Efficient routing in intermittently connected mobile networks:the single-copy case[J].IEEE/ACM Transactions on Networking,2008,,16(1):63-76.



作者信息:

任  智,,王中永,張  勇 

(重慶郵電大學(xué) 移動通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室,,重慶400065)

此內(nèi)容為AET網(wǎng)站原創(chuàng),,未經(jīng)授權(quán)禁止轉(zhuǎn)載。