文獻標(biāo)識碼: A
DOI:10.16157/j.issn.0258-7998.2017.05.030
中文引用格式: 任智,,王中永,張勇. 基于協(xié)作中繼的高吞吐量機會網(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.
0 引言
機會網(wǎng)絡(luò)[1-2]是一種不需要在源節(jié)點和目的節(jié)點之間存在完整鏈路、利用節(jié)點移動帶來的相遇機會實現(xiàn)通信的時延和分裂可容忍的無線自組織網(wǎng)絡(luò),,在軍事,、災(zāi)難救助以及偏遠野外地區(qū)等領(lǐng)域有著廣泛的應(yīng)用。目前,,機會網(wǎng)絡(luò)的研究是基于節(jié)點具有良好的協(xié)作性,,然而,由于機會網(wǎng)絡(luò)中節(jié)點的資源有限,,為節(jié)約資源,,節(jié)點都存在一定的自私性,自私節(jié)點通常會拒絕為其他節(jié)點轉(zhuǎn)發(fā)消息,,這種自私行為勢必會嚴(yán)重影響機會網(wǎng)絡(luò)正常的路由和數(shù)據(jù)轉(zhuǎn)發(fā)功能,,從而導(dǎo)致網(wǎng)絡(luò)性能退化。
目前,,國內(nèi)外對于含自私節(jié)點的機會網(wǎng)絡(luò)的研究已經(jīng)取得了一些成果,,人們提出了各種激勵機制來激勵節(jié)點協(xié)作[3-7],尤其是近年來越來越多地采用了經(jīng)濟學(xué)方法中的博弈理論[4-6],?;贐arter機制的算法是一類典型的基于博弈論的機會網(wǎng)絡(luò)路由算法,該算法基于互惠機制,,博弈雙方互相交換彼此感興趣或者具有潛在價值的消息,。BUTTYAN L等[4]提出了Barter機制,主要用于激勵網(wǎng)絡(luò)中自私節(jié)點對自己不感興趣分組的“存儲-攜帶-轉(zhuǎn)發(fā)”,。LIN C S等[5]提出了基于Barter機制的針對對等網(wǎng)絡(luò)(P2P)流媒體系統(tǒng)中自私節(jié)點的機制,。ZHANG C等[6]結(jié)合信譽機制中虛擬貨幣交易的特點改進了原始Barter機制,提出了一種全新的激勵范式C4,,但未考慮分布式網(wǎng)絡(luò)中節(jié)點的自私性,。由上可知,現(xiàn)有基于Barter機制的路由算法仍然是僅考慮兩兩節(jié)點間進行的交易,,未考慮分組交易存在的僵局問題,,有進一步改善的需要。
本研究基于上述研究成果,,并在文獻[4]的基礎(chǔ)上,,提出了一種全新的角度——基于協(xié)作中繼的博弈模型,對歸一化時間內(nèi)的機會網(wǎng)絡(luò)吞吐量及時延進行了分析,仿真實驗證實了本模型的有效性,。
1 網(wǎng)絡(luò)模型與問題描述
1.1 系統(tǒng)描述
設(shè)任一含自私節(jié)點的機會網(wǎng)絡(luò)中,,自私節(jié)點只轉(zhuǎn)發(fā)自己感興趣的數(shù)據(jù)分組。BUTTYAN L等[4]提出任何分組都有其潛在價值,,當(dāng)前不感興趣的分組將來可用來交換感興趣的分組,。在Barter機制中,節(jié)點感興趣的分組初始價值量為1,,不感興趣的分組初始價值量是自身采取的博弈策略Si={S1,,S2,…,,Sm}(0<Si<1),。部分變量定義如表1所示。
1.2 機會網(wǎng)絡(luò)的博弈模型
含自私節(jié)點的機會網(wǎng)絡(luò)中節(jié)點具有自私而有理性的特點,,在模型方面與傳統(tǒng)的機會網(wǎng)絡(luò)有所不同,,故作出如下定義。
定義1 博弈模型:機會網(wǎng)絡(luò)的博弈模型為G=[V,,{Si},,{πi}],;其中,,節(jié)點集合V={v1,v2,,…,,vn},n>1,,即為博弈參與者,;策略集合Si={S1,S2,,…,,Sm},1≤m≤n(n-1),,表示節(jié)點對自己不感興趣分組與感興趣分組的比值,;收益函數(shù)?仔i(S1,S2,,…,,Sm)表示網(wǎng)絡(luò)中參與者采取策略后網(wǎng)絡(luò)的實際吞吐量。
定義2 數(shù)據(jù)分組屬性:含自私節(jié)點的機會網(wǎng)絡(luò)中,,數(shù)據(jù)分組主要有兩種屬性:分組興趣屬性ζ(0<ζ<<1)與分組價值折扣屬性(見式(3)),。
定義3 實際吞吐量模型:實際吞吐量Gi(0≤Gi(t)≤1)是節(jié)點i在每個歸一化時間內(nèi)成功傳遞分組獲得的累計價值,節(jié)點i的該值可以在一個理想的情況下表示為:
在RACR中,博弈參與者的收益只依賴于其選擇的博弈策略,,且博弈參與者在其策略空間中選取惟一確定的策略進行博弈,,因此,這個博弈有對稱的純策略均衡解,。
綜上分析可知,,不難判斷一個策略組合{s′}是否是納什均衡。對任意參與者i(i∈V),,若i采取背叛策略能夠獲得更多的收益,,則{s′}不是納什均衡。由于參與者具有相同的收益函數(shù),,若{s′}是參與者i的最優(yōu)策略,,則{s′}也是其他參與者的最優(yōu)策略。
1.3 問題描述
(1)僵局問題:由于交易的公平性要求,,分組交換由可交換數(shù)目小的一方?jīng)Q定,,進行等量交換。若一個節(jié)點有分組需要轉(zhuǎn)發(fā),,對方節(jié)點無該節(jié)點需要的分組或無足夠分組與前者交換,,將導(dǎo)致網(wǎng)絡(luò)陷入僵局,造成網(wǎng)絡(luò)等待時延,,稱之為“僵局問題”,。
(2)現(xiàn)有的Barter機制在數(shù)據(jù)分組交易過程中存在冗余交互操作。
(3)根據(jù)現(xiàn)有Barter機制,,價值量達到某一閾值的消息就簡單丟棄,,然而,這樣很可能刪除即將到達目的地址的分組,,增大了消息傳輸時延,。
2 RACR算法
本文提出一種基于協(xié)作中繼的高吞吐量機會網(wǎng)絡(luò)路由算法——RACR。RACR算法采用引入?yún)f(xié)作中繼節(jié)點的轉(zhuǎn)發(fā)方式,,對分組交易僵局問題加以有效解決,,并重新設(shè)計滿足協(xié)作中繼的分組交易過程,引入多方交易以激活數(shù)據(jù)分組的單向傳遞,,從而削減數(shù)據(jù)分組傳遞次數(shù),。同時,對價值量小于閾值的分組先判斷其目的地址是否是鄰居節(jié)點,,從而提高分組傳送成功率,,降低數(shù)據(jù)分組傳輸時延。
2.1 RACR算法新機制
2.1.1 協(xié)作中繼
RACR算法針對現(xiàn)有Barter路由算法分組交易過程中的交易僵局問題,,引入?yún)f(xié)作中繼機制加以解決,??紤]如下網(wǎng)絡(luò)場景:假設(shè)節(jié)點u、v已完成兩兩之間的交易或節(jié)點u,、v不存在相應(yīng)的分組交易,,若節(jié)點v仍有節(jié)點u需要而不能與之交易的分組。同時,,節(jié)點u,、v收到共同的鄰居節(jié)點w廣播的目的地址為v的分組索引,若節(jié)點w在節(jié)點v與w,、u與w兩兩交易完成后,,節(jié)點u、v根據(jù)節(jié)點w的分組索引計算發(fā)現(xiàn)節(jié)點w仍有節(jié)點v需要的分組,,同時節(jié)點u也有節(jié)點w需要的分組,。
協(xié)作中繼節(jié)點的選取思路為:當(dāng)網(wǎng)絡(luò)出現(xiàn)上述情況時,如圖1(a)所示,,根據(jù)Barter算法的原理,,消息交易將陷入僵局。圖1(b)表示RACR算法的分組交易示意圖,,如果網(wǎng)絡(luò)出現(xiàn)上述情況,,則節(jié)點w將會向節(jié)點v發(fā)送一個額外分組,節(jié)點v收到節(jié)點w發(fā)送的額外分組后會給節(jié)點u發(fā)送一個額外分組,。最后,,節(jié)點u給節(jié)點w需要的一個額外的分組。若存在能滿足以上描述條件的節(jié)點,,即是協(xié)作中繼節(jié)點,。
2.1.2 分組傳遞次數(shù)削減
RACR算法引入多方交易以激活數(shù)據(jù)分組的單向傳遞,對數(shù)據(jù)分組的傳遞次數(shù)進行削減,。考慮如下網(wǎng)絡(luò)場景:節(jié)點u,、v和w在同一通信范圍內(nèi),,節(jié)點u需要通過節(jié)點v交易獲取節(jié)點v中的分組,節(jié)點v需要獲取節(jié)點u中的分組用來交換節(jié)點w中的分組,,同時節(jié)點u也有節(jié)點w需要的分組,。
分組傳遞次數(shù)削減思路為:當(dāng)網(wǎng)絡(luò)出現(xiàn)上述情況時,如圖1(a)所示,,在Barter路由算法中,,中間節(jié)點v進行一次分組交換需要收、發(fā)2個分組才能完成交易,。如圖1(b)所示,,在RACR算法中,首先發(fā)現(xiàn)節(jié)點間存在上述關(guān)系的節(jié)點向需要自身數(shù)據(jù)分組的節(jié)點發(fā)送一個數(shù)據(jù)分組,收到該額外分組的理性節(jié)點進行相同的操作,,最后完成一個公平的交易,。則RACR算法的中間節(jié)點v僅需要收、發(fā)1個分組,,從而實現(xiàn)分組傳遞次數(shù)的削減,,減少數(shù)據(jù)分組的冗余交互操作。
2.1.3 分組刪除判定優(yōu)化
原始Barter路由算法中,,節(jié)點對價值小于分組刪除閾值的數(shù)據(jù)分組采取簡單的丟棄策略,。然而,雖然刪除的分組價值量小,,但很有可能即將到達分組的目的節(jié)點,。在RACR算法中,節(jié)點對價值量低于刪除閾值的分組,,首先判斷該分組的目的地址是否為該節(jié)點的鄰居節(jié)點,,若是則發(fā)起新的分組交易,否則直接刪除該分組,。這樣在不影響網(wǎng)絡(luò)開銷的前提下,,提高網(wǎng)絡(luò)吞吐量,同時降低傳輸時延,。
2.2 RACR算法操作
RACR算法主要操作步驟如下:
(1)節(jié)點u,、v相遇,按Barter機制兩兩之間交易完畢,。此時,,若節(jié)點v仍有節(jié)點u需要而不能與之交易的分組,則進行步驟(2),,否則結(jié)束,;
(2)節(jié)點u、v收到公共鄰居節(jié)點w發(fā)送的分組索引,,根據(jù)節(jié)點w的分組索引計算判斷節(jié)點w是否符合協(xié)作中繼節(jié)點的要求,。若符合,則進行步驟(3),,否則結(jié)束,;
(3)若節(jié)點u通過計算,最先獲知協(xié)作中繼節(jié)點w的參與情況,。節(jié)點u向節(jié)點w發(fā)送一個節(jié)點w需要的分組,,節(jié)點w收到u發(fā)送的分組后,立即向節(jié)點v發(fā)送一個節(jié)點v需要的分組,。同理,,節(jié)點v向節(jié)點u發(fā)送一個u需要的分組,。
3 仿真
3.1 仿真環(huán)境
本文使用OPNET軟件作為仿真平臺,選取Barter算法[4]和DT算法[8]作為比較對象,,在相同仿真條件下分析比較它們的網(wǎng)絡(luò)吞吐量,、時延等性能。主要仿真參數(shù)設(shè)置如表2所示,。
3.2 仿真結(jié)果及分析
(1)歸一化網(wǎng)絡(luò)吞吐量
由圖2可知,,與DT算法和Barter算法相比,RACR算法在網(wǎng)絡(luò)吞吐量上提高了7.9%以上,。主要原因是:①采用協(xié)作中繼機制,,從而選取合適的協(xié)作中繼節(jié)點,對分組交易僵局問題加以有效解決,;②對價值量小于刪除閾值的分組首先判斷其目的地址是否為鄰居節(jié)點,,若是則發(fā)起新的分組交易,從而提高網(wǎng)絡(luò)吞吐量,。
(2)分組平均端到端時延
由圖3可知,,RACR算法的分組平均端到端時延低于DT和Barter算法。主要原因是:①RACR算法通過引入?yún)f(xié)作中繼節(jié)點,,解決了交易的僵局問題,,有效地減少網(wǎng)絡(luò)等待時延;②分組傳遞次數(shù)削減機制通過引入多方交易以激活數(shù)據(jù)分組的單向傳遞,,從而加快數(shù)據(jù)分組的交換,,縮短數(shù)據(jù)分組交換的時延。
(3)歸一化控制開銷
由圖4可知,,RACR算法能夠明顯減少歸一化控制開銷,。開銷減少的原因主要是RACR協(xié)議引入?yún)f(xié)作中繼節(jié)點,提高了消息的交付率,,減少了消息在網(wǎng)絡(luò)中的傳輸?shù)钠骄鴶?shù),。同時,優(yōu)化了分組交易機制,,削減了分組交換次數(shù),,減少了消息交易過程中的額外開銷,從而降低歸一化控制開銷,。
(4)分組傳送成功率
由圖5可知,與DT算法和Barter算法相比,,RACR算法顯著提高了分組傳送成功率,。主要原因是:①引入?yún)f(xié)作中繼節(jié)點,增加了分組交易機會,;②優(yōu)化分組刪除判定機制,,刪除緩存消息之前先判斷其目的地址是否是其鄰居節(jié)點,,若是則重新發(fā)起分組交易,從而提高了數(shù)據(jù)分組傳送成功率,。
4 結(jié)束語
本文通過深入研究博弈理論在含有自私節(jié)點的機會網(wǎng)絡(luò)的應(yīng)用,,提出了一種基于協(xié)作中繼的高吞吐量機會網(wǎng)絡(luò)路由算法RACR。RACR算法通過在Barter機制中采用協(xié)作中繼機制并引入多方交易以激活數(shù)據(jù)分組的單向傳遞,,同時優(yōu)化分組刪除的判定條件,。仿真結(jié)果顯示,與DT路由算法和Barter路由算法相比,,RACR算法能夠更加有效地促使含自私節(jié)點的機會網(wǎng)絡(luò)進行數(shù)據(jù)分組交易,,從而增加網(wǎng)絡(luò)吞吐量,降低數(shù)據(jù)分組端到端時延,。
參考文獻
[1] XIONG Y P,,SUN L M,NIU J W,,et al.Opportunistic networks[J].Journal of Software,,2009,20(1):124-137.
[2] 任智,,黃勇,,陳前斌.機會網(wǎng)絡(luò)路由協(xié)議[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] 劉期烈,,候鵬翔.機會網(wǎng)絡(luò)中激勵節(jié)點檢測策略研究[J].重慶郵電大學(xué)學(xué)報(自然科學(xué)報),,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ù)重慶市重點實驗室,重慶400065)