基于信用激勵(lì)機(jī)制的移動(dòng)網(wǎng)絡(luò)路由優(yōu)化研究

葛偉倫

(安徽財(cái)貿(mào)職業(yè)學(xué)院 云桂信息學(xué)院, 安徽 合肥 230601)

為了提高數(shù)據(jù)傳輸?shù)男剩苿?dòng)網(wǎng)絡(luò)中的節(jié)點(diǎn)使用“存儲(chǔ)—攜帶—轉(zhuǎn)發(fā)”方式轉(zhuǎn)發(fā)數(shù)據(jù)。隨著移動(dòng)設(shè)備、WiFi和藍(lán)牙技術(shù)的普及，許多研究人員開始對(duì)具有社交屬性的移動(dòng)網(wǎng)絡(luò)進(jìn)行研究，并提出了許多基于社會(huì)關(guān)系的路由策略。大多數(shù)的路由策略均假設(shè)移動(dòng)用戶愿意為其他用戶進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，但實(shí)際上移動(dòng)用戶通常采用自私的行為來節(jié)省有限的資源或保護(hù)他們的私人信息。自私有兩種形式：個(gè)人自私和社會(huì)自私[1]。具有個(gè)人自私性節(jié)點(diǎn)對(duì)所有其他節(jié)點(diǎn)具有同樣的自私性，而具有社會(huì)自私的節(jié)點(diǎn)則傾向于基于他們的社會(huì)關(guān)系向他人提供服務(wù)。研究者們提出各種路由方案來分別解決移動(dòng)網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)人自私性[2-4]和社會(huì)自私性[5-6]問題。本文從博弈論角度出發(fā)，提出了一種新型基于信用激勵(lì)機(jī)制的路由策略，同時(shí)解決了移動(dòng)網(wǎng)絡(luò)節(jié)點(diǎn)的個(gè)人自私性和社會(huì)自私性問題，從而提高移動(dòng)網(wǎng)絡(luò)的性能。

1 系統(tǒng)模型

本文將兩個(gè)自私節(jié)點(diǎn)之間的數(shù)據(jù)傳輸建模為一個(gè)Rubinstein-Stahl討價(jià)還價(jià)過程[7]。假設(shè)擁有數(shù)據(jù)的節(jié)點(diǎn)是買方，用B表示，為買方轉(zhuǎn)發(fā)數(shù)據(jù)的中繼節(jié)點(diǎn)則是賣方，用S表示。由于網(wǎng)絡(luò)中的節(jié)點(diǎn)是自私的，買方和賣方均都想追求最大利益。在移動(dòng)網(wǎng)絡(luò)中，有限的節(jié)點(diǎn)資源(如緩存和能量)、不良的節(jié)點(diǎn)社會(huì)關(guān)系等都可能會(huì)影響節(jié)點(diǎn)之間協(xié)作。這些因素可能造成了節(jié)點(diǎn)的自私性，使自私的節(jié)點(diǎn)不為其他節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)。假設(shè)每個(gè)節(jié)點(diǎn)都擁有虛擬貨幣，虛擬貨幣可以適當(dāng)?shù)卮碳す?jié)點(diǎn)進(jìn)行合作。移動(dòng)網(wǎng)絡(luò)存在一個(gè)控制節(jié)點(diǎn)作為虛擬貨幣的管理中心，移動(dòng)網(wǎng)絡(luò)中的節(jié)點(diǎn)需要在貨幣管理中心注冊(cè)賬號(hào)。當(dāng)兩個(gè)節(jié)點(diǎn)使用虛擬貨幣完成交易后，賣方節(jié)點(diǎn)會(huì)將具有數(shù)字簽名的收據(jù)提交到貨幣管理中心。當(dāng)目的地收到數(shù)據(jù)后，貨幣管理中心將清算該交易。中繼節(jié)點(diǎn)為其他節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)，它們會(huì)獲得一定數(shù)量的虛擬貨幣作為回報(bào)；當(dāng)中繼節(jié)點(diǎn)具有足夠的虛擬貨幣時(shí)，也可以支付其他節(jié)點(diǎn)為其轉(zhuǎn)發(fā)數(shù)據(jù)。所有節(jié)點(diǎn)都試圖通過轉(zhuǎn)發(fā)來自其他節(jié)點(diǎn)的消息來獲得虛擬貨幣。假設(shè)網(wǎng)絡(luò)中有兩種節(jié)點(diǎn)：正常(合作)節(jié)點(diǎn)和自私節(jié)點(diǎn)。其中，自私節(jié)點(diǎn)不是惡意節(jié)點(diǎn)，不會(huì)刪除、偽造和篡改數(shù)據(jù)。

2 影響節(jié)點(diǎn)自私性的因素

(1)

其中，α1、α2是權(quán)重，并有α1+α2=1。

由于存在不同的社交關(guān)系，節(jié)點(diǎn)之間存在不同的信任關(guān)系，可能會(huì)表現(xiàn)出社交自私性。本文根據(jù)歷史信息來刻畫節(jié)點(diǎn)的社會(huì)關(guān)系，如節(jié)點(diǎn)間的接觸頻率、接觸時(shí)間、接觸規(guī)律以及社會(huì)相似性。社會(huì)相似性可以反映兩個(gè)節(jié)點(diǎn)之間的相似程度。節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的信任關(guān)系Si,j可以利用以下的公式來計(jì)算：

(2)

其中，φ是權(quán)重，F(xiàn)Si,j是節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的社會(huì)壓力參數(shù)，SSi,j是節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的社會(huì)相似性。FSi,j是能夠反映出節(jié)點(diǎn)之間關(guān)系的密切性，包括了接觸的頻率、持續(xù)的時(shí)間和規(guī)律，計(jì)算的方式如下所示：

(3)

其中，r(t)是在時(shí)刻t之后，節(jié)點(diǎn)i和節(jié)點(diǎn)j相遇后剩余的時(shí)間。SSi,j是節(jié)點(diǎn)i和節(jié)點(diǎn)j的社會(huì)相似性，計(jì)算方式如下：

(4)

其中，NumofNeii,j是節(jié)點(diǎn)i和節(jié)點(diǎn)j共同鄰居的數(shù)量，NumofNeii是節(jié)點(diǎn)i鄰居的數(shù)量，NumofNeij是節(jié)點(diǎn)j鄰居的數(shù)量。

3 信用激勵(lì)路由優(yōu)化

3.1 路由優(yōu)化的Rubinstein-Stahl 討價(jià)還價(jià)模型

買方B想以最低的價(jià)格購買賣方的服務(wù)，但也需要會(huì)考慮很多因素。首先，購買者應(yīng)該考慮數(shù)據(jù)對(duì)價(jià)格的影響，比如數(shù)據(jù)的大小、數(shù)據(jù)的剩余時(shí)間(TTL)。然后，買方應(yīng)考慮節(jié)點(diǎn)的剩余資源和持有的貨幣。因此，對(duì)于數(shù)據(jù)p，買方B在t時(shí)刻的開價(jià)可以表示為：

(5)

(6)

(7)

3.2 路由優(yōu)化策略設(shè)計(jì)

本小節(jié)詳細(xì)地闡述了基于信用激勵(lì)機(jī)制的移動(dòng)網(wǎng)絡(luò)路由優(yōu)化策略。為了保證數(shù)據(jù)傳輸?shù)某晒β什⒐?jié)約網(wǎng)絡(luò)資源，路由策略會(huì)采用有限的多拷貝方式。當(dāng)數(shù)據(jù)源Src想要將數(shù)據(jù)包p發(fā)送到目的地Des時(shí)，數(shù)據(jù)源會(huì)創(chuàng)建有限數(shù)量的數(shù)據(jù)包p副本，并將一個(gè)副本轉(zhuǎn)發(fā)給Src的中繼節(jié)點(diǎn)j。當(dāng)中繼節(jié)點(diǎn)在轉(zhuǎn)發(fā)數(shù)據(jù)包p的副本時(shí)，該節(jié)點(diǎn)會(huì)采用單一復(fù)制方案，并刪除該副本。假設(shè)節(jié)點(diǎn)i需要轉(zhuǎn)發(fā)數(shù)據(jù)包p到目的地Des，當(dāng)節(jié)點(diǎn)i和j相遇，節(jié)點(diǎn)i首先確定節(jié)點(diǎn)j是否為數(shù)據(jù)包p的目的地，如果是，則節(jié)點(diǎn)i轉(zhuǎn)發(fā)數(shù)據(jù)包p到節(jié)點(diǎn)j；否則，節(jié)點(diǎn)i會(huì)通過探測包確定節(jié)點(diǎn)j是否有較高歷史概率達(dá)到目的地。如果節(jié)點(diǎn)j比當(dāng)前節(jié)點(diǎn)i具有更高的概率遇到Des，那么節(jié)點(diǎn)i將與節(jié)點(diǎn)j開始進(jìn)行協(xié)商，從而激勵(lì)自私節(jié)點(diǎn)j轉(zhuǎn)發(fā)數(shù)據(jù)包p；否則，節(jié)點(diǎn)i將繼續(xù)攜帶數(shù)據(jù)包p，并繼續(xù)尋找新的中繼節(jié)點(diǎn)。雙方開始協(xié)商時(shí)，節(jié)點(diǎn)i將請(qǐng)求信息發(fā)送到節(jié)點(diǎn)j。節(jié)點(diǎn)j是一個(gè)自私的中繼節(jié)點(diǎn)，向節(jié)點(diǎn)i出售自己的轉(zhuǎn)發(fā)服務(wù)。當(dāng)節(jié)點(diǎn)j接收到請(qǐng)求信息后，它首先使用公式(2)計(jì)算兩個(gè)節(jié)點(diǎn)之間的社會(huì)關(guān)系。然后，節(jié)點(diǎn)j計(jì)算傳輸信息的價(jià)格。如果賣方j(luò)的價(jià)格高于買方i的價(jià)格，協(xié)商將結(jié)束，節(jié)點(diǎn)j不會(huì)為節(jié)點(diǎn)i轉(zhuǎn)發(fā)數(shù)據(jù)包p。否則，節(jié)點(diǎn)j計(jì)算(xj,xi)和uj,m(xj)的值，然后將其開價(jià)、折扣因子發(fā)送給節(jié)點(diǎn)i。如果節(jié)點(diǎn)i的效用值ui,m(xi)是正數(shù)，節(jié)點(diǎn)i會(huì)將數(shù)據(jù)包p轉(zhuǎn)發(fā)給節(jié)點(diǎn)j；否則，則繼續(xù)下一輪討價(jià)還價(jià)。如果討價(jià)還價(jià)的次數(shù)比閾值高，雙方就會(huì)結(jié)束協(xié)商。當(dāng)雙方完成交易時(shí)，他們將持有這次交易的數(shù)字簽名收據(jù)。節(jié)點(diǎn)將在連接到互聯(lián)網(wǎng)時(shí)會(huì)將此收據(jù)提交給貨幣管理中心。如果目的地Des接收到數(shù)據(jù)包p，它會(huì)發(fā)送確認(rèn)信息給貨幣管理中心，貨幣管理中心將根據(jù)數(shù)字簽名的收據(jù)為每個(gè)中繼節(jié)點(diǎn)支付貨幣。

4 性能評(píng)估

本節(jié)將使用機(jī)會(huì)網(wǎng)絡(luò)環(huán)境模擬器[8]對(duì)所提出的基于信用激勵(lì)機(jī)制的移動(dòng)網(wǎng)絡(luò)路由優(yōu)化策略的性能進(jìn)行評(píng)估。在仿真實(shí)驗(yàn)中，設(shè)置權(quán)重α1=0.5，α2=0.5，φ=0.5，折扣因子γB=γS=0.8。數(shù)據(jù)包的大小服從U(50KB, 1024KB)的均勻分布，數(shù)據(jù)包產(chǎn)生的時(shí)間間隔為10秒，數(shù)據(jù)包的TTL服從U(30min, 300min)的均勻分布，節(jié)點(diǎn)的緩沖區(qū)大小服從U(1MB, 20MB)的均勻分布。將本文的基于信用激勵(lì)機(jī)制的路由策略與Epidemic[9]、Spray-and-Wait(SaW)[10]策略進(jìn)行對(duì)比。在移動(dòng)網(wǎng)絡(luò)中，節(jié)點(diǎn)的自私行為會(huì)影響路由策略的性能。本實(shí)驗(yàn)將網(wǎng)絡(luò)中自私節(jié)點(diǎn)的百分比從0%增加到80%，將節(jié)點(diǎn)的緩沖區(qū)大小設(shè)置為15MB，數(shù)據(jù)包的TTL設(shè)置為144min。圖1是交付率與網(wǎng)絡(luò)中自私節(jié)點(diǎn)比例的關(guān)系，交付率是指到達(dá)目的地的數(shù)據(jù)包數(shù)量與源節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)包數(shù)量的比率。從圖1可知，三種策略的交付率都隨著自私節(jié)點(diǎn)百分比的增加而下降。Epidemic策略和SaW策略具有更低的交付率,本文算法能實(shí)現(xiàn)最高的交付率。本文算法考慮了兩種自私性，有效地激勵(lì)了更多的自私節(jié)點(diǎn)參與合作。此外，本文算法采用有限的副本拷貝策略，可以節(jié)省有限的資源。

圖1交付率與自私節(jié)點(diǎn)比例的關(guān)系

圖2反映了路由策略的平均時(shí)延。隨著自私節(jié)點(diǎn)比例的增加，所有路由策略的平均時(shí)延將會(huì)增加，但Epidemic的增長卻很平穩(wěn)。Epidemic路由策略向所有的鄰居節(jié)點(diǎn)發(fā)送數(shù)據(jù)包，因此數(shù)據(jù)包會(huì)有更多的機(jī)會(huì)，并迅速地傳遞到目的地。與SaW策略相比，本文算法能獲得較小的時(shí)延。本文算法利用了討價(jià)討價(jià)的博弈模型，考慮了多種因素來激勵(lì)節(jié)點(diǎn)，有效地利用節(jié)點(diǎn)間的信任關(guān)系進(jìn)行數(shù)據(jù)傳輸，從而更快地將信息傳遞到目的地。

圖2平均時(shí)延與自私節(jié)點(diǎn)比例的關(guān)系圖3交付率x(1/平均時(shí)延)x吞吐量與自私節(jié)點(diǎn)比例的關(guān)系

圖3反映了策略的綜合性能指標(biāo)，即交付率×(1 /平均延遲)×吞吐量。該指標(biāo)反映了路由策略的總體性能，由圖3可知，本文算法在整體性能方面優(yōu)于其他協(xié)議。

5 結(jié)論

本文提出了一種基于信用激勵(lì)機(jī)制的路由優(yōu)化策略，考慮了節(jié)點(diǎn)的個(gè)人自私性和社會(huì)自私性，以提高移動(dòng)網(wǎng)絡(luò)的性能。本文路由優(yōu)化策略分為兩個(gè)過程：基于信用的激勵(lì)過程和路由轉(zhuǎn)發(fā)過程。在基于信用的激勵(lì)過程中，本文提出了一種新的基于討價(jià)還價(jià)博弈的方法，考慮了節(jié)點(diǎn)的資源利用率、節(jié)點(diǎn)間的信任度，從而鼓勵(lì)節(jié)點(diǎn)參與數(shù)據(jù)轉(zhuǎn)發(fā)。在路由過程中，利用了有限的副本拷貝方式以及信息激勵(lì)機(jī)制，使得自私節(jié)點(diǎn)能夠主動(dòng)地參與數(shù)據(jù)轉(zhuǎn)發(fā)。仿真結(jié)果表明，本文算法能夠獲得較好的綜合性能。在未來的工作中，我們將考慮在高速移動(dòng)和可靠的通信場景中基于信用激勵(lì)路由方案的效率。