葛偉倫

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

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

1 系統(tǒng)模型

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

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

(1)

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

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

(2)

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

(3)

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

(4)

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

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

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

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

(5)

(6)

(7)

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

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

4 性能評估

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

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

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

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

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

5 結(jié)論

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