樂光學(xué) ，駱 丹 ，劉建生 ，李明明

（1.嘉興學(xué)院數(shù)理與信息工程學(xué)院 嘉興 314001；2.江西理工大學(xué)理學(xué)院 贛州 341000）

無(wú)線 mesh網(wǎng)絡(luò)（wireless mesh network,WMN）由 mesh路由和mesh終端組成，具有自組織、自配置、靈活多跳、移動(dòng)等特點(diǎn)[1,2]，是目前比較公認(rèn)的無(wú)線接入網(wǎng)絡(luò)技術(shù)之一。無(wú)線mesh網(wǎng)絡(luò)中存在大量的移動(dòng)終端，而流媒體技術(shù)是當(dāng)今互聯(lián)網(wǎng)承載的主要業(yè)務(wù)之一，對(duì)帶寬具有較高要求。根據(jù)艾瑞網(wǎng)、ComScore和 CNNIC[3～5]數(shù)據(jù)顯示，到 2013年12月為止，中國(guó)網(wǎng)民數(shù)量達(dá)到6.18億人，手機(jī)網(wǎng)民規(guī)模超過5億人(占整體比例81.0%)，其中網(wǎng)絡(luò)音樂和網(wǎng)絡(luò)視頻的網(wǎng)民使用率分別為73.4%和69.3%，流媒體占據(jù)比例較大且有遞增趨勢(shì)。然而手機(jī)終端的儲(chǔ)蓄電池、內(nèi)存等設(shè)置限制了節(jié)點(diǎn)的在線時(shí)長(zhǎng)和帶寬節(jié)點(diǎn)的頻繁加入與離開以及大規(guī)模節(jié)點(diǎn)的訪問必然會(huì)影響網(wǎng)絡(luò)暢通。此外，網(wǎng)絡(luò)中并非每個(gè)節(jié)點(diǎn)都遵循“平等互惠，友好共處”理念，當(dāng)搭便車（free riding）節(jié)點(diǎn)規(guī)模過大、占用帶寬過多時(shí)，將嚴(yán)重影響無(wú)線mesh網(wǎng)絡(luò)的性能。

Adar E和Huberman B A對(duì)Gnutella上的流量測(cè)量結(jié)果[6]顯示，被監(jiān)測(cè)的33335個(gè)節(jié)點(diǎn)中有將近22000個(gè)節(jié)點(diǎn)不共享文件，其比例接近66%；1667個(gè)節(jié)點(diǎn)（占5%）共享了2182087個(gè)文件（占所有文件的70%），極少數(shù)的節(jié)點(diǎn)承擔(dān)了大部分的回應(yīng)請(qǐng)求，筆者將這種行為稱為搭便車。參考文獻(xiàn)[7]將該數(shù)據(jù)與參考文獻(xiàn)[8]中的數(shù)據(jù)進(jìn)行對(duì)比發(fā)現(xiàn)，該系統(tǒng)中的搭便車現(xiàn)象已經(jīng)存在了5年，不但沒有得到減緩反而更加嚴(yán)重。

本文從節(jié)點(diǎn)搭便車抑制出發(fā)，提出了一種平滑無(wú)線mesh網(wǎng)絡(luò)中節(jié)點(diǎn)流量過載將造成擁塞的算法，其特點(diǎn)如下。

·無(wú)線mesh網(wǎng)絡(luò)擁塞判定:為了避免資源分享節(jié)點(diǎn)造成擁塞，需要對(duì)節(jié)點(diǎn)擁塞狀況進(jìn)行預(yù)判定。當(dāng)造成擁塞不能滿足全部節(jié)點(diǎn)請(qǐng)求時(shí)，優(yōu)先滿足貢獻(xiàn)值高的節(jié)點(diǎn)，抑制貢獻(xiàn)值低的搭便車節(jié)點(diǎn)。

·分等級(jí)的獎(jiǎng)罰策略:根據(jù)無(wú)線mesh網(wǎng)絡(luò)中節(jié)點(diǎn)貢獻(xiàn)能力的差異，將節(jié)點(diǎn)分為4類——超級(jí)節(jié)點(diǎn)、熱心節(jié)點(diǎn)（EN）、普通節(jié)點(diǎn)和搭便車節(jié)點(diǎn)，通過判定節(jié)點(diǎn)類型給予不同程度的獎(jiǎng)罰。

2 國(guó)內(nèi)外研究現(xiàn)狀

1965年美國(guó)經(jīng)濟(jì)學(xué)家曼柯·奧爾遜在《集體行動(dòng)的邏輯:公共利益和團(tuán)體理論》[9]中首次提出了“搭便車”概念。2000年Adar E等人將此概念用于對(duì)計(jì)算機(jī)領(lǐng)域中節(jié)點(diǎn)行為的描述，其代表作[6]的發(fā)表引起了計(jì)算機(jī)領(lǐng)域研究者們的關(guān)注，通過對(duì)節(jié)點(diǎn)的在線時(shí)長(zhǎng)、帶寬等行為特征進(jìn)行分析，提出相對(duì)應(yīng)的搭便車抑制機(jī)制。

最初研究者們對(duì)節(jié)點(diǎn)的類型并未加以區(qū)分，在研究過程中發(fā)現(xiàn)節(jié)點(diǎn)的貢獻(xiàn)能力具有差異性，好的分類能更貼近網(wǎng)絡(luò)的實(shí)際狀況，表1對(duì)現(xiàn)有參考文獻(xiàn)的節(jié)點(diǎn)分類進(jìn)行了簡(jiǎn)要統(tǒng)計(jì)。

無(wú)線mesh網(wǎng)絡(luò)中存在大量的移動(dòng)用戶，當(dāng)電池耗盡時(shí)不得不退出網(wǎng)絡(luò)，在線時(shí)長(zhǎng)較短；移動(dòng)設(shè)備的CPU計(jì)算性能較低、內(nèi)存較小。節(jié)點(diǎn)加入網(wǎng)絡(luò)獲取所需的資源后立刻退出網(wǎng)絡(luò)，一定程度上充當(dāng)著搭便車節(jié)點(diǎn)角色。不少研究者在對(duì)節(jié)點(diǎn)的貢獻(xiàn)度計(jì)算時(shí)加入帶寬數(shù)字特征，減小節(jié)點(diǎn)貢獻(xiàn)值受物理接入方式局限性的影響，更具公平性。參考文獻(xiàn)[14]對(duì)文件的數(shù)量、大小以及被下載的次數(shù)等文件特性設(shè)定有效函數(shù)，參考文獻(xiàn)[15]認(rèn)為網(wǎng)絡(luò)具有異構(gòu)性，節(jié)點(diǎn)提供服務(wù)的能力本身就存在顯著差異，在其基礎(chǔ)之上加入了節(jié)點(diǎn)所能提供的最大帶寬，減小節(jié)點(diǎn)貢獻(xiàn)值受物理接入方式局限性的影響。參考文獻(xiàn)[16]對(duì)參考文獻(xiàn)[15]中的帶寬因素更具體化，從節(jié)點(diǎn)的內(nèi)存大小、CPU主頻、帶寬以及硬盤容量等因素綜合考慮節(jié)點(diǎn)的物理配置值。

表1 節(jié)點(diǎn)類型分類統(tǒng)計(jì)

[17]的結(jié)果顯示在線時(shí)長(zhǎng)達(dá)2 h及以上的節(jié)點(diǎn)，其中只有20%的節(jié)點(diǎn)其在線時(shí)長(zhǎng)可達(dá)到24 h，參考文獻(xiàn)[18]顯示在Maze系統(tǒng)中普通用戶在線時(shí)長(zhǎng)為2.89 h，而搭便車者相對(duì)較短，大約為1.15 h，參考文獻(xiàn)[14]表明當(dāng)系統(tǒng)生命周期增加到10倍壽命時(shí)，搭便車行為可以得到有效控制。

參考文獻(xiàn) [19]將信任值分為直接信任值和間接信任值，利用加權(quán)平均法計(jì)算節(jié)點(diǎn)信任值。參考文獻(xiàn)[12]提出了一種基于超級(jí)節(jié)點(diǎn)的信任模型，該模型中以興趣相似的節(jié)點(diǎn)聚成簇，節(jié)點(diǎn)之間的信任關(guān)系被劃分為3類:超級(jí)節(jié)點(diǎn)—超級(jí)節(jié)點(diǎn)、超級(jí)節(jié)點(diǎn)—普通節(jié)點(diǎn)、普通節(jié)點(diǎn)—普通節(jié)點(diǎn)，并對(duì)不同情況設(shè)置信任模型。參考文獻(xiàn)[13]中根據(jù)節(jié)點(diǎn)的信譽(yù)值大小將信譽(yù)值設(shè)定為3個(gè)等級(jí):L等級(jí)、N等級(jí)、H等級(jí)，當(dāng)采取搭便車時(shí)它們的懲罰力度依次減小。該文中以節(jié)點(diǎn)交互前的信譽(yù)等級(jí)、本次交互活動(dòng)中所采取的策略、節(jié)點(diǎn)的懲罰因子等為依據(jù)對(duì)節(jié)點(diǎn)i進(jìn)行懲罰。參考文獻(xiàn)[20]通過分析異構(gòu)無(wú)線網(wǎng)絡(luò)中移動(dòng)用戶的收益、花費(fèi)以及時(shí)延開銷等因素，提出了基于Stackelberg博弈的分布式定價(jià)和資源分配算法，并證明了移動(dòng)用戶間的非合作博弈存在納什均衡點(diǎn)。

參考文獻(xiàn)[21]對(duì)無(wú)線mesh網(wǎng)絡(luò)中大量的移動(dòng)終端用戶之間的非合作交流進(jìn)行研究，允許任意數(shù)量的終端參與到當(dāng)?shù)氐慕换ブ?，擴(kuò)展了演化博弈的框架；并通過演化博弈模型研究WCDMA （wideband code-division multiple-access）無(wú)線環(huán)境下的大量非合作的移動(dòng)節(jié)點(diǎn)之間的交互。參考文獻(xiàn)[22]針對(duì)無(wú)線mesh網(wǎng)絡(luò)中搭便車節(jié)點(diǎn)通過調(diào)整路由協(xié)議最小化其負(fù)載逃避監(jiān)測(cè)的行為，提出了一種基于局部觀測(cè)信息交互的自適應(yīng)在線算法。參考文獻(xiàn) [2]認(rèn)為WMN（wireless mesh network）和P2P視頻都是新興研究方向，可以利用研究WMN來(lái)提升P2P視頻性能，通過對(duì)初始解決方案和提議解決方案進(jìn)行比較，結(jié)果顯示后者的復(fù)制內(nèi)容和流量都有所降低，性能更佳。參考文獻(xiàn)[23]提出了針對(duì)搭便車行為的新算法——Give-to-Get，將媒體文件分割成小塊，節(jié)點(diǎn)需上傳已有的小塊從而從其他節(jié)點(diǎn)處獲取其余的小塊，而搭便車節(jié)點(diǎn)只能在系統(tǒng)空閑時(shí)才能獲取媒體數(shù)據(jù)。參考文獻(xiàn)[24]中提出了一種基于文件復(fù)制的對(duì)等網(wǎng)絡(luò)中的搭便車激勵(lì)機(jī)制——FRWBBA（file replication and workload balancing based approach）。根據(jù)節(jié)點(diǎn)狀態(tài)變量與過載閾值比較，判斷是否過載，當(dāng)超過閾值時(shí)，將過載節(jié)點(diǎn)上的文件轉(zhuǎn)移到鄰近的搭便車節(jié)點(diǎn)上；反之則認(rèn)為網(wǎng)絡(luò)暢通，允許搭便車節(jié)點(diǎn)的存在。然而實(shí)際中網(wǎng)絡(luò)具有異構(gòu)性，再加上流技術(shù)的實(shí)時(shí)性、流式、文件較大等特性，對(duì)于流媒體文件和普通的文本文件不加以區(qū)分采用文件復(fù)制的策略方式在進(jìn)行流媒體文件貢獻(xiàn)時(shí)不宜采用，會(huì)降低網(wǎng)絡(luò)的性能。

3 搭便車抑制策略分析與建模

3.1 模型分析

無(wú)線mesh網(wǎng)絡(luò)中節(jié)點(diǎn)帶寬有限，對(duì)于流媒體共享節(jié)點(diǎn)，在未過載情況下，盡可能地滿足所有用戶節(jié)點(diǎn)的服務(wù)請(qǐng)求；反之，當(dāng)網(wǎng)絡(luò)中用戶請(qǐng)求繁多而網(wǎng)絡(luò)資源不足時(shí)，將會(huì)造成節(jié)點(diǎn)擁塞，嚴(yán)重影響用戶之間的資源傳輸交互，降低網(wǎng)絡(luò)的性能；傳輸?shù)牧鲿承灾苯佑绊懹脩魧?duì)該網(wǎng)絡(luò)的興趣，倘若一個(gè)熱心節(jié)點(diǎn)因過載而宕機(jī)離開網(wǎng)絡(luò)，將會(huì)使得網(wǎng)絡(luò)的資源急劇下降，嚴(yán)重影響用戶對(duì)系統(tǒng)的興趣，使得更多的節(jié)點(diǎn)退出，造成馬太效應(yīng)，導(dǎo)致系統(tǒng)資源變得越來(lái)越匱乏，從而造成系統(tǒng)快速崩潰。對(duì)此，首先需要對(duì)網(wǎng)絡(luò)的擁塞程度進(jìn)行判斷:

·當(dāng)網(wǎng)絡(luò)資源充足時(shí)，允許一定數(shù)量的搭便車節(jié)點(diǎn)的信息請(qǐng)求，盡可能地滿足用戶需求；

·當(dāng)網(wǎng)絡(luò)資源缺乏時(shí)，根據(jù)請(qǐng)求節(jié)點(diǎn)貢獻(xiàn)度的高低給予回應(yīng)，一定程度上抑制搭便車節(jié)點(diǎn)行為。

此外，網(wǎng)絡(luò)中節(jié)點(diǎn)的貢獻(xiàn)能力以及參與網(wǎng)絡(luò)活動(dòng)的積極性具有明顯差異，為了體現(xiàn)貢獻(xiàn)節(jié)點(diǎn)的優(yōu)越以及引導(dǎo)節(jié)點(diǎn)積極為網(wǎng)絡(luò)做貢獻(xiàn)，提出了分等級(jí)的獎(jiǎng)罰機(jī)制，主要思路如下。

·對(duì)于不同類型節(jié)點(diǎn):當(dāng)節(jié)點(diǎn)采取搭便車策略時(shí)，根據(jù)節(jié)點(diǎn)為網(wǎng)絡(luò)做貢獻(xiàn)的程度將受到不同程度的獎(jiǎng)勵(lì)/懲罰，如同樣采取搭便車策略時(shí)，熱心節(jié)點(diǎn)受到的懲比搭便車節(jié)點(diǎn)低。

·對(duì)于同類型節(jié)點(diǎn):節(jié)點(diǎn)的獎(jiǎng)罰機(jī)制屬于“罰大于獎(jiǎng)”，同一節(jié)點(diǎn)在采取搭便車策略時(shí)受到的懲罰要大于采取貢獻(xiàn)策略獲得的獎(jiǎng)勵(lì)，呈現(xiàn)“升慢降快”的過程。

3.2 算法描述

參考文獻(xiàn)[24]提出了基于文件復(fù)制與負(fù)載均衡的算法——FRWBBA，通過設(shè)定過載閾值判定監(jiān)測(cè)節(jié)點(diǎn)的狀態(tài)是否過載造成擁塞，而無(wú)線mesh網(wǎng)絡(luò)中流媒體文件較大，需占用一定的帶寬，文件復(fù)制轉(zhuǎn)移過載負(fù)載不適合用于流媒體文件；參考文獻(xiàn)[23,25]對(duì)網(wǎng)絡(luò)中視頻播放時(shí)如何處理搭便車行為，提出了應(yīng)對(duì)策略，其中參考文獻(xiàn)[23]針對(duì)多用戶請(qǐng)求流媒體文件在資源空閑時(shí)允許搭便車，反之只允許搭便車節(jié)點(diǎn)在系統(tǒng)空閑時(shí)才能獲取流媒體數(shù)據(jù)。為了更好地完成用戶信息交互，本文結(jié)合上述參考文獻(xiàn)對(duì)網(wǎng)絡(luò)擁塞進(jìn)行預(yù)測(cè)，在維持網(wǎng)絡(luò)暢通的同時(shí)，也在一定程度上抑制了網(wǎng)絡(luò)中搭便車節(jié)點(diǎn)行為。

假設(shè):

當(dāng)節(jié)點(diǎn)集N訪問節(jié)點(diǎn)peer，節(jié)點(diǎn)peer根據(jù)自身負(fù)載能力（WLmaxi-workloadi（t））對(duì)節(jié)點(diǎn)集給予回應(yīng)。若節(jié)點(diǎn) peer本身過載則拒絕資源訪問，反之則根據(jù)訪問節(jié)點(diǎn)j在t時(shí)刻 attribute P（j，t）貢獻(xiàn)能力給予訪問，算法如下。

其中，workloadi（t）表示節(jié)點(diǎn)i與j訪問帶來(lái)的負(fù)載量。通過如上算法確定最大目標(biāo)節(jié)點(diǎn)集BTNS，進(jìn)行流媒體資源共享。

4 基于分等級(jí)獎(jiǎng)罰機(jī)制的搭便車應(yīng)對(duì)策略

4.1 分等級(jí)的獎(jiǎng)罰策略模型

實(shí)際的網(wǎng)絡(luò)中節(jié)點(diǎn)的貢獻(xiàn)能力具有較大差異，對(duì)此，本文通過節(jié)點(diǎn)的文件上傳下載收益Ufile以及在線時(shí)長(zhǎng)收益Uonline判定節(jié)點(diǎn)的類型，判定效用函數(shù)如下:

其中，η∈[0，1]，為常數(shù)定值。根據(jù)貢獻(xiàn)能力高低將節(jié)點(diǎn)類型分為4類，具體如下。

·超級(jí)節(jié)點(diǎn):無(wú)線mesh網(wǎng)絡(luò)中的mesh路由。

·熱心節(jié)點(diǎn):節(jié)點(diǎn)的Uup（上傳收益）＞Udown（下載收益），節(jié)點(diǎn)類型判定效用函數(shù)值Utype＞Mhigh。

·普通節(jié)點(diǎn):節(jié)點(diǎn)類型判定效用函數(shù)值Utype＞Mlow，即效用函數(shù)值為 Utype∈[Mlow，Mhigh]。

·搭便車節(jié)點(diǎn):節(jié)點(diǎn)只下載不上傳或者上傳收益很小，即 Utype

其中，Mhigh、Mlow為常數(shù)定值。通過判別節(jié)點(diǎn)類型，對(duì)不同類型的節(jié)點(diǎn)采取分等級(jí)的搭便車獎(jiǎng)罰機(jī)制策略，將受到的獎(jiǎng)勵(lì)/懲罰 Hi（p,k）分為 4 個(gè)等級(jí)。

（1）p={超級(jí)節(jié)點(diǎn)、熱心節(jié)點(diǎn)、普通節(jié)點(diǎn)、搭便車節(jié)點(diǎn)}；k={獎(jiǎng)勵(lì)、懲罰}。

（2）Hi（p,k）∈[0，1]。

（3）不同類型節(jié)點(diǎn)時(shí)，分為如下兩種情況。

·當(dāng) k=獎(jiǎng)勵(lì)時(shí)，貢獻(xiàn)值越高，Hi（p,k）值越大，即 Hi(超級(jí)節(jié)點(diǎn),獎(jiǎng)勵(lì))>Hi(熱心節(jié)點(diǎn)，獎(jiǎng)勵(lì))>Hi(普通節(jié)點(diǎn)，獎(jiǎng)勵(lì))>Hi(搭便車節(jié)點(diǎn)，獎(jiǎng)勵(lì))。

·當(dāng) k=懲罰時(shí)，搭便車程度越大，Hi（p,k）值越大，即Hi（(超級(jí)節(jié)點(diǎn),懲罰)

（4）同類型節(jié)點(diǎn)時(shí):當(dāng) p 一定時(shí)，Hi（p,獎(jiǎng)勵(lì)）

根據(jù)上述描述做如下定義:超級(jí)節(jié)點(diǎn)（p=1）、熱心節(jié)點(diǎn)（p=2）、普通節(jié)點(diǎn)（p=3）和搭便車節(jié)點(diǎn)（p=4）；p=1,2,3,4 且k表示節(jié)點(diǎn)受到獎(jiǎng)勵(lì)（k=1）或懲罰（k=2），定義如下。

定義1 當(dāng)節(jié)點(diǎn)類型為p時(shí)，對(duì)應(yīng)的獎(jiǎng)罰系數(shù)Hi（p，k)為:

其中，m表示交易中搭便車的次數(shù)，即交易過程中只下載不上傳的次數(shù)；n表示交易總次數(shù)。當(dāng)節(jié)點(diǎn)的策略行為一定，即一定時(shí)，有以下兩種情況。

（1）不同類型節(jié)點(diǎn)時(shí)，分為兩種情況。

·當(dāng) k=1時(shí) ，k一定，p 值越小，Hi（p,k）值越大 ，即 Hi（4,1）

·當(dāng) k=2 時(shí)，k一定，p 值越大，Hi（p,k）值越大，即Hi（1,2）

（2）同類型節(jié)點(diǎn)時(shí)，有:

因此，同類節(jié)點(diǎn)的獎(jiǎng)罰機(jī)制屬于“罰大于獎(jiǎng)”，同一節(jié)點(diǎn)在采取搭便車策略時(shí)受到的懲罰要大于采取貢獻(xiàn)策略獲得的獎(jiǎng)勵(lì)，呈現(xiàn)“升慢降快”的過程。

節(jié)點(diǎn)的貢獻(xiàn)值直接影響節(jié)點(diǎn)享受網(wǎng)絡(luò)資源能力，受歡迎度較高的文件下載需要更高的貢獻(xiàn)度，而且采用分等級(jí)的獎(jiǎng)罰機(jī)制，搭便車節(jié)點(diǎn)在采取搭便車策略時(shí)受到的懲罰也更大，一定程度上可以抑制節(jié)點(diǎn)的搭便車行為，減少網(wǎng)絡(luò)中的搭便車節(jié)點(diǎn)，使網(wǎng)絡(luò)環(huán)境更優(yōu)化。

4.2 節(jié)點(diǎn)交易信任度計(jì)算

無(wú)線mesh網(wǎng)絡(luò)中節(jié)點(diǎn)的交易信任度計(jì)算是一個(gè)迭代的過程，根據(jù)節(jié)點(diǎn)的記錄日志計(jì)算節(jié)點(diǎn)的直接、間接信任，然后通過歷史交易獲取節(jié)點(diǎn)的交易信譽(yù)度，最后綜合考慮節(jié)點(diǎn)peer是否值得信任。下面首先對(duì)節(jié)點(diǎn)的交易信任度進(jìn)行定義。

定義 2 假設(shè)節(jié)點(diǎn)peer與訪問節(jié)點(diǎn)i之間的信任度為Rip，訪問節(jié)點(diǎn)peer之間的信任度為Rij，則與peer之間的局部信任度R為:

通過式（3）獲取節(jié)點(diǎn)的直接信任度Rdirect和間接信任度Rindirect，本文采用加權(quán)平均法[19]計(jì)算節(jié)點(diǎn)peer的信任值Tr，計(jì)算式如下:

根據(jù)EigenTrust算法[19]，描述節(jié)點(diǎn)的信任函數(shù)為:

其中，χ是一個(gè)0～1之間的常數(shù)系數(shù)，表示節(jié)點(diǎn)i依賴本次交易信任的程度，當(dāng)χ=1時(shí)表示節(jié)點(diǎn)的信任值只跟本次計(jì)算有關(guān)，與以往的交易情況無(wú)關(guān)。

參考文獻(xiàn)[13]采用貝葉斯算法 Ci=（m+1）/（m+n+1）計(jì)算節(jié)點(diǎn)的交易信譽(yù)值，本文對(duì)此進(jìn)行改進(jìn)，在考慮節(jié)點(diǎn)的歷史交易情況的同時(shí)，加入了節(jié)點(diǎn)i在t和t+1時(shí)刻的行為信任值，計(jì)算式如下:

首次交易時(shí)，節(jié)點(diǎn)i的信譽(yù)值為1，有利于新節(jié)點(diǎn)的加入；隨著時(shí)間的推移，節(jié)點(diǎn)采取搭便車的次數(shù)越多，信譽(yù)值就越??；γ（t）表示節(jié)點(diǎn)t-1時(shí)刻和t時(shí)刻行為獲取的信任度系數(shù)，SFR表示采取搭便車策略，SC表示采取貢獻(xiàn)策略，本文中設(shè)定見表2。

表2 節(jié)點(diǎn)前后兩次交易行為的信任度系數(shù)γ（t）

定義 3 節(jié)點(diǎn)peer的交易信任度計(jì)算式如下:

其中，ψ是一個(gè)常數(shù)系數(shù)，表示節(jié)點(diǎn)peer的交易信任值對(duì)上一次交易的依賴度。δ是一個(gè)常數(shù)系數(shù)，等同于近期交易與歷史交易的偏重權(quán)值。節(jié)點(diǎn)的交易信任度越高，表示該節(jié)點(diǎn)任性度越高，搭便車的程度越低。通過計(jì)算節(jié)點(diǎn)的交易信任度選擇合適的交易對(duì)象，交互過程中更能展現(xiàn)交易的友好性。

4.3 貢獻(xiàn)度計(jì)算

參考文獻(xiàn)[17]顯示我國(guó)1/3的節(jié)點(diǎn)的生命周期基本低于一天。在此基礎(chǔ)進(jìn)行假設(shè):當(dāng)節(jié)點(diǎn)的在線時(shí)長(zhǎng)超過1天時(shí)，認(rèn)為該節(jié)點(diǎn)搭便車的幾率較小，由在線時(shí)長(zhǎng)online帶來(lái)的收益較高，那么節(jié)點(diǎn)的在線時(shí)長(zhǎng)收益值計(jì)算式為:

當(dāng)節(jié)點(diǎn)的在線時(shí)長(zhǎng)小于24 h時(shí)，收益值取值范圍為（0,1），online越小，則節(jié)點(diǎn)在線時(shí)長(zhǎng)收益值就越??；當(dāng)online趨向于24 h時(shí)，在線時(shí)長(zhǎng)收益趨向于1。當(dāng)節(jié)點(diǎn)的在線時(shí)長(zhǎng)超過24 h時(shí)，則認(rèn)為該節(jié)點(diǎn)采取搭便車策略的幾率較小，設(shè)置固定值為1。

參考文獻(xiàn)[16]通過節(jié)點(diǎn)i的上傳/下載的文件大小、次數(shù)等因素設(shè)定其收入值函數(shù)，尤其是限制下載速度來(lái)抑制網(wǎng)絡(luò)中的搭便車節(jié)點(diǎn)行為。本文在此基礎(chǔ)之上對(duì)此進(jìn)行改進(jìn)，設(shè)定了分等級(jí)的獎(jiǎng)罰機(jī)制，對(duì)不同類型的節(jié)點(diǎn)實(shí)行不同程度的獎(jiǎng)罰力度。

定義4 t時(shí)刻，節(jié)點(diǎn)i通過文件的上傳和下載參與網(wǎng)絡(luò)中資源的共享，獲取的文件上傳下載收益Ufile（i，t）為:

其中，Uup和Udown分別表示節(jié)點(diǎn)的上傳和下載收益函數(shù)；popular（fj）表示文件 fj的受歡迎度，取值范圍為[0,1]，數(shù)值越大表示共享的文件受歡迎程度越高、價(jià)值越大。反之，數(shù)值為 0則表示該文件是毫無(wú)價(jià)值的垃圾文件；Hi（p,1）,Hi（p,2）分別表示節(jié)點(diǎn)類型為p的節(jié)點(diǎn)在上傳和下載時(shí)對(duì)應(yīng)的獎(jiǎng)罰度；size表示文件的大??；count表示文件被上傳/下載的次數(shù)，其中 count_down（fj）=1，表示文件一旦下載即保存，只需一次下載即可；speed表示節(jié)點(diǎn)i的上傳/下載速度，初設(shè)定為:該節(jié)點(diǎn)在該時(shí)刻的最大下載速度/節(jié)點(diǎn)類型，該設(shè)定可以用于限制網(wǎng)絡(luò)中的搭便車行為，當(dāng)節(jié)點(diǎn)下載速度慢時(shí)則需要耗費(fèi)更長(zhǎng)的下載時(shí)間，從而延長(zhǎng)其在線時(shí)長(zhǎng)。

根據(jù)節(jié)點(diǎn)的在線時(shí)長(zhǎng)收益、上傳收益與下載收益可以判定節(jié)點(diǎn)類型p。

定義5 節(jié)點(diǎn)i在t時(shí)刻的效用函數(shù)如下:

其中，常數(shù)α表示對(duì)前一次效用計(jì)算的依賴度；Rtt表示節(jié)點(diǎn)i在t時(shí)刻的時(shí)延。

定義6 網(wǎng)絡(luò)接入方式具有異構(gòu)性，為了更具公平性，加入節(jié)點(diǎn) i在 t時(shí)刻的帶寬 BW（i，t），此時(shí)節(jié)點(diǎn) i的貢獻(xiàn)度函數(shù)為:

節(jié)點(diǎn)的效用函數(shù)值與其物理配置值成比值關(guān)系，那些盡全力貢獻(xiàn)卻因物理配置低導(dǎo)致不公平現(xiàn)象得到了合理的處理，同時(shí)也一定程度上克制了利用自身優(yōu)勢(shì)“低貢獻(xiàn)高收入”的行為。

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

5.1 仿真環(huán)境

本文通過對(duì)源節(jié)點(diǎn)進(jìn)行周期監(jiān)測(cè)，根據(jù)其負(fù)載能力最大程度地滿足節(jié)點(diǎn)的需求，本實(shí)驗(yàn)的網(wǎng)絡(luò)環(huán)境為:節(jié)點(diǎn)總數(shù)為200個(gè)，設(shè)置Mhigh=0.7、Mlow=0.4。此外仿真實(shí)驗(yàn)開始時(shí)，設(shè)定網(wǎng)絡(luò)中4類節(jié)點(diǎn)的數(shù)量比為:超級(jí)節(jié)點(diǎn)∶熱心節(jié)點(diǎn)∶普通節(jié)點(diǎn)∶搭便車節(jié)點(diǎn)=0.5∶2.5∶3∶4。

根據(jù)上述假設(shè)，4類節(jié)點(diǎn)信息見表3。

表3 4類節(jié)點(diǎn)信息

5.2 擁塞繁數(shù)ω

本實(shí)驗(yàn)通過仿真驗(yàn)證不同擁塞系數(shù)ω時(shí)的負(fù)載比率、未滿足節(jié)點(diǎn)數(shù)量比率和獲得下載權(quán)限的節(jié)點(diǎn)數(shù)量比率。仿真期間，節(jié)點(diǎn)的數(shù)量與節(jié)點(diǎn)的選擇具有隨機(jī)性，為了顯現(xiàn)實(shí)驗(yàn)結(jié)果的可比性，不同擁塞系數(shù)對(duì)應(yīng)每個(gè)周期的下載請(qǐng)求節(jié)點(diǎn)一致，監(jiān)測(cè)周期為12 h，每個(gè)采樣周期為0.5 h，每次有n個(gè)節(jié)點(diǎn)進(jìn)行訪問，獲取節(jié)點(diǎn)的負(fù)載值，并記錄每個(gè)周期內(nèi)獲得下載權(quán)限的節(jié)點(diǎn)數(shù)以及未獲取下載權(quán)限的節(jié)點(diǎn)數(shù)量，針對(duì)不同的ω時(shí)，每個(gè)周期下載請(qǐng)求節(jié)點(diǎn)具有一致性。仿真結(jié)果如圖1和圖2所示。

圖1 源節(jié)點(diǎn)在不同擁塞系數(shù)的負(fù)載比率

圖2 源節(jié)點(diǎn)在不同擁塞系數(shù)的節(jié)點(diǎn)數(shù)量比率

從圖1和圖 2中可以看出:

·擁塞系數(shù)ω越大，源節(jié)點(diǎn)的負(fù)載比率相對(duì)越大，未滿足需求的節(jié)點(diǎn)數(shù)比率相對(duì)較小，例如ω=0.5時(shí)，源節(jié)點(diǎn)的負(fù)載比率較低，幾乎沒有節(jié)點(diǎn)可以獲得其資源的下載權(quán)限，不能很好地滿足節(jié)點(diǎn)的下載需求；

·當(dāng)ω=0.9、ω=1時(shí)，源節(jié)點(diǎn)的負(fù)載比率較高，未滿足節(jié)點(diǎn)的數(shù)量比率較低，充分展現(xiàn)了資源的共享；

·從圖1中的ω=1可以看出，源節(jié)點(diǎn)的負(fù)載比率有好幾次接近1，即將近100%地貢獻(xiàn)其帶寬，對(duì)源節(jié)點(diǎn)自身而言這種情況不現(xiàn)實(shí)，也容易造成自身?yè)砣?，因而本文中?duì)于ω的初設(shè)定為0.9，即充分利用源節(jié)點(diǎn)的資源又保障其負(fù)載不過載。

5.3 源節(jié)點(diǎn)各信息比率

通過選定一個(gè)熱心節(jié)點(diǎn)作為源節(jié)點(diǎn)，對(duì)其采用以擁塞判定為前提的搭便車抑制策略，周期監(jiān)測(cè)結(jié)果顯示如圖3所示。

圖3 源節(jié)點(diǎn)各信息比率

從圖3中可以看出:

·仿真開始時(shí)，源節(jié)點(diǎn)以最大程度地滿足所有節(jié)點(diǎn)的信息請(qǐng)求（滿足節(jié)點(diǎn)數(shù)比率=1，未滿足節(jié)點(diǎn)數(shù)比率=0）；

·隨著時(shí)間的進(jìn)行，由于節(jié)點(diǎn)一直處于負(fù)載飽和狀態(tài)，后期的源節(jié)點(diǎn)比率接近設(shè)定的最大限 （ω·WLmaxi），滿足節(jié)點(diǎn)數(shù)比率接近于0，未滿足節(jié)點(diǎn)數(shù)比率接近于1，在資源未得到釋放前不能再滿足更多的節(jié)點(diǎn)；

·當(dāng)源節(jié)點(diǎn)資源釋放時(shí)，如圖中7.5 h時(shí)，有空余資源以最大程度給予下載，滿足其余節(jié)點(diǎn)的需求；

·此外，圖中源節(jié)點(diǎn)的負(fù)載比率從未超過1甚至0.9，保障了源節(jié)點(diǎn)的帶寬，避免了因請(qǐng)求多超出其負(fù)載能力而造成擁塞甚至宕機(jī)的潛在風(fēng)險(xiǎn)，維護(hù)了網(wǎng)絡(luò)的良好環(huán)境。

5.4 下載列表中節(jié)點(diǎn)類型數(shù)量統(tǒng)計(jì)

本次仿真實(shí)驗(yàn)中對(duì)源節(jié)點(diǎn)下載列表中不同類型的節(jié)點(diǎn)數(shù)量進(jìn)行研究，通過周期監(jiān)測(cè)記錄源節(jié)點(diǎn)下載列表的節(jié)點(diǎn)信息，然后對(duì)下載列表中的全部節(jié)點(diǎn)、正在下載的節(jié)點(diǎn)以及本次監(jiān)測(cè)中剛獲得下載權(quán)限的節(jié)點(diǎn)進(jìn)行數(shù)量統(tǒng)計(jì)，結(jié)果見表4。

由表4可知:

·第一次監(jiān)測(cè)時(shí)，節(jié)點(diǎn)的資源充足，滿足了所有節(jié)點(diǎn)的需求（總類型:0-0-0-1、本次新下載節(jié)點(diǎn):0-0-0-1）；

·第二次監(jiān)測(cè)時(shí)，由于新加入了0-2-0-1個(gè)節(jié)點(diǎn)，源節(jié)點(diǎn)又滿足了所有節(jié)點(diǎn)的請(qǐng)求；

·第3次監(jiān)測(cè)時(shí)，有0-0-3-0個(gè)節(jié)點(diǎn)請(qǐng)求，此時(shí)由于源節(jié)點(diǎn)負(fù)載飽和，不對(duì)它們的請(qǐng)求做出回應(yīng)，預(yù)防了源節(jié)點(diǎn)的過載情況；

·第11次監(jiān)測(cè)時(shí)節(jié)點(diǎn)仍然處于飽和狀態(tài)，而在第12次監(jiān)測(cè)時(shí)有節(jié)點(diǎn)下載完成釋放了源節(jié)點(diǎn)的資源空間，因而在第12次時(shí)又對(duì)節(jié)點(diǎn)的請(qǐng)求給予了回應(yīng)。

通過對(duì)以上結(jié)果進(jìn)行分析發(fā)現(xiàn):源節(jié)點(diǎn)在未能滿足所有節(jié)點(diǎn)的請(qǐng)求時(shí)，總是優(yōu)先滿足p值低的節(jié)點(diǎn) （p值表示節(jié)點(diǎn)類型，p值越低其貢獻(xiàn)值高），從而在避免造成網(wǎng)絡(luò)擁塞的同時(shí)，也在一定程度上抑制了貢獻(xiàn)值較低的搭便車節(jié)點(diǎn)的行為。

5.5 搭便車策略比較

為了驗(yàn)證基于網(wǎng)絡(luò)擁塞判定的搭便車抑制機(jī)制（overcoming free riding mechanism based on network congestion decision，OFRNC）的性能，本文將該策略與隨機(jī)下 載 （random download，RD）、先 到 先 下 載 （first come first download，F(xiàn)CFD）策略進(jìn)行比較。下面對(duì)3種策略在遇到同一批下載節(jié)點(diǎn)N={1,2,…c}請(qǐng)求時(shí)，源節(jié)點(diǎn)的負(fù)載比率進(jìn)行比較，首先對(duì)另外兩種策略未采用擁塞判定，然后對(duì)其加入擁塞判定，結(jié)果如圖4所示。

圖4（a）顯示第8次監(jiān)測(cè)時(shí)源節(jié)點(diǎn)的負(fù)載比率為1，即當(dāng)未采用擁塞判定時(shí)，源節(jié)點(diǎn)易造成因?yàn)樽陨砟芰Σ荒軡M足全部節(jié)點(diǎn)的需求而過載，嚴(yán)重的可能造成節(jié)點(diǎn)因行為受阻不暢通而宕機(jī)，而源節(jié)點(diǎn)為超級(jí)節(jié)點(diǎn)，該節(jié)點(diǎn)的離開將對(duì)網(wǎng)絡(luò)造成極大的損失。圖4（b）中的3種策略都采用擁塞判定為前提，從圖中可以看出，采用OFRNC策略的源節(jié)點(diǎn)比率相對(duì)較穩(wěn)定，而且負(fù)載比率較高，源節(jié)點(diǎn)在不造成過載的同時(shí)，盡自身最大程度地為網(wǎng)絡(luò)做貢獻(xiàn)。

表4 下載列表中不同類型節(jié)點(diǎn)數(shù)量統(tǒng)計(jì)

圖4 采用不同策略時(shí)源節(jié)點(diǎn)的負(fù)載比率

下面對(duì)3種策略都采用擁塞判定為前提，對(duì)每個(gè)周期內(nèi)未開始下載和該周期內(nèi)獲得下載權(quán)限的不同類型節(jié)點(diǎn)數(shù)量進(jìn)行統(tǒng)計(jì)，見表5。

從表5中可以看出:

·采用RD與FCFD策略時(shí)隨機(jī)獲得下載權(quán)限的節(jié)點(diǎn)類型，容易讓搭便車節(jié)點(diǎn)鉆空隙，即使在資源有限時(shí)還可以獲得下載權(quán)限，助長(zhǎng)了網(wǎng)絡(luò)中節(jié)點(diǎn)的搭便車行為；

·OFRNC策略按照節(jié)點(diǎn)類型分配優(yōu)先權(quán)，即超級(jí)節(jié)點(diǎn)>熱心節(jié)點(diǎn)>普通節(jié)點(diǎn)>搭便車節(jié)點(diǎn)，優(yōu)先滿足貢獻(xiàn)值高的節(jié)點(diǎn)，當(dāng)資源有限時(shí)，搭便車節(jié)點(diǎn)的行為受到了抑制，同時(shí)如果該類節(jié)點(diǎn)在資源有限時(shí)想獲得下載權(quán)限，必須通過為網(wǎng)絡(luò)做貢獻(xiàn)提高自身的貢獻(xiàn)值，既維護(hù)了網(wǎng)絡(luò)的暢通，又引導(dǎo)節(jié)點(diǎn)積極為網(wǎng)絡(luò)做貢獻(xiàn)，保障了網(wǎng)絡(luò)的良好環(huán)境。

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

本文提出了無(wú)線mesh網(wǎng)絡(luò)中對(duì)搭便車節(jié)點(diǎn)行為的抑制策略，通過判定節(jié)點(diǎn)是否會(huì)造成擁塞，優(yōu)先滿足貢獻(xiàn)值高的節(jié)點(diǎn)，從而抑制搭便車節(jié)點(diǎn)只能在資源空閑時(shí)才能獲得下載權(quán)限。通過對(duì)節(jié)點(diǎn)進(jìn)行周期檢測(cè)，結(jié)果顯示超載的風(fēng)險(xiǎn)率明顯減小；此外，將該策略與RD與FCFD策略進(jìn)行比較，實(shí)驗(yàn)結(jié)果顯示OFRNC策略在資源不足時(shí)大幅度減少了獲得下載權(quán)限的搭便車節(jié)點(diǎn)數(shù)量，一定程度上抑制了網(wǎng)絡(luò)中節(jié)點(diǎn)的搭便車行為。終端設(shè)備的內(nèi)存、容量、主頻等配置直接影響節(jié)點(diǎn)的貢獻(xiàn)能力，本文對(duì)此并未進(jìn)行深入擴(kuò)展。此外，本文采用MATLAB軟件進(jìn)行仿真，實(shí)驗(yàn)結(jié)果數(shù)據(jù)不免與實(shí)際情況有出入。今后將對(duì)這兩點(diǎn)進(jìn)行更深入的研究，提出更合理、實(shí)踐性更強(qiáng)的搭便車應(yīng)對(duì)策略。

表5 3種策略中節(jié)點(diǎn)類型統(tǒng)計(jì)

參考文獻(xiàn)

1 仵國(guó)鋒.認(rèn)知無(wú)線mesh網(wǎng)絡(luò)若干關(guān)鍵技術(shù)研究.解放軍信息工程大學(xué)博士學(xué)位論文，2011

2 Salta N,Morla R,Ricardo M.Improving P2P video streaming in wireless mesh networks.Proceedings of 2010 the 9th IFIP Annual Mediterranean Ad Hoc Networking Workshop(Med-Hoc-Net),Juan Les Pins,France,June 2010:23～25

3 艾瑞咨詢.2014年1月網(wǎng)絡(luò)視頻收視數(shù)據(jù)發(fā)布.http://news.iresearch.cn/zt/228461.shtml#,2014-03-28

4 ComScore.2014年1月美國(guó)在線視頻網(wǎng)站排名.http://www.199it.com/archives/197664.html,2014-03-26

5 CNNIC.第33次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告.北京:中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心,2014

6 Adar E,Huberman B A.Free riding on Gnutella.First Monday,2000,5(10):32～35

7 余一嬌,金海.對(duì)等網(wǎng)絡(luò)中的搭便車行為分析與抑制機(jī)制綜述.計(jì)算機(jī)學(xué)報(bào),2008(1):1～15

8 Hughes D,Coulson G,Walkerdine J.Free riding on Gnutella revisited:the bell tolls?IEEE Distributed Systems Online,2005,6(6):1～18

9 搭便車.http://baike.baidu.com/view/574903.htm，2012

10 Anceaume E,Gradinariu M,Ravoajia A.Incentive for P2P fair resource sharing.Proceedings of the 5th IEEE International Conference on Peer-to-Peer Computing,Konstanz,Germany,2005:253～260

11 陳才.針對(duì)節(jié)點(diǎn)自私性的對(duì)等網(wǎng)絡(luò)激勵(lì)機(jī)制技術(shù)研究.北京郵電大學(xué)博士學(xué)位論文,2010

12 田春岐,江建慧,胡治國(guó)等.一種基于聚集超級(jí)節(jié)點(diǎn)的P2P網(wǎng)絡(luò)信任模型.計(jì)算機(jī)學(xué)報(bào),2010(2):345～355

13 李文嬌.P2P網(wǎng)絡(luò)搭便車行為抑制方法研究.鄭州大學(xué)碩士學(xué)位論文,2011

14 Ramaswamy L,Liu L.Free riding:a new challenge to peer-to-peer file sharing systems.Proceedings of the 36th Hawaii International Conference on System Sciences,Hawaii,USA,2003:220～229

15 Ma R T B,Lee C M,Lui J C S,et al.Incentive P2P network:a protocol to encourage information sharing and contribution.ACM SIGMETRICS Performance Evaluation Review,2003,31(2):23～25

16 劉建輝,王君,冀常鵬等.P2P中應(yīng)用平衡機(jī)制抑制搭便車行為的研究.計(jì)算機(jī)科學(xué),2013(7):36～39

17 Steiner M,En-Najjary T,Biersack E W.Long term study of peer behavior in the KAD DHT.IEEE/ACM Transactions on Networking,2009,17(6):1371～1384

18 Moon J,Cho Y.A point-based inventive system to prevent free-riding on P2P network environments.Proceedings of ICCSA,Santander,Spain,2011:462～471

19 李勇軍,代亞非.對(duì)等網(wǎng)絡(luò)信任機(jī)制研究.計(jì)算機(jī)學(xué)報(bào),2010(3):390～405

20 姜永,陳山枝,胡博.異構(gòu)無(wú)線網(wǎng)絡(luò)中基于Stackelberg博弈的分布式定價(jià)和資源分配算法.通信學(xué)報(bào),2013(1):61～68

21 Tembine H,Altman E,ElAzouzi R,et al.Evolutionary games in wireless networks.IEEE Transactions on Systems,Man,and Cybernetics,Part B:Cybernetics,2010,40(3):634～646

22 Wang B,Soltani S,Shaprio J K,et al.Distributed detection of selfish routing in wireless mesh networks.Technical Report-MSU-CSE-06-19, Department of Computer Science and Engineering,Michigan State University,2008

23 Mol J J D,Pouwelse J A,Meulpolder M,et al.Give-to-get:an algorithm for P2P video-on-demand.Proceedings of Multimedia Computing and Networking(MMCN),San Jose,CA,USA,2008

24 余一嬌.基于文件復(fù)制的對(duì)等網(wǎng)絡(luò)搭便車抑制技術(shù)研究.華中科技大學(xué)博士學(xué)位論文,2009

25 Mol J J D,Pouwelse J A,Meulpolder M,et al.Give-to-get:free-riding resilient video-on-demand in P2P systems.Proceedings of International Society for Optics and Photonics,San Diego,California,USA,2008