張光華，龐少博，楊耀紅，陳振國

（1. 西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071；2. 河北科技大學(xué)信息科學(xué)與工程學(xué)院，河北 石家莊 050000；3. 華北科技學(xué)院河北省物聯(lián)網(wǎng)數(shù)據(jù)采集與處理工程技術(shù)研究中心，河北 三河 065201）

機(jī)會網(wǎng)絡(luò)下基于信任機(jī)制的改進(jìn)Epidemic算法

張光華1,2，龐少博2，楊耀紅2，陳振國3

（1. 西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071；2. 河北科技大學(xué)信息科學(xué)與工程學(xué)院，河北 石家莊 050000；3. 華北科技學(xué)院河北省物聯(lián)網(wǎng)數(shù)據(jù)采集與處理工程技術(shù)研究中心，河北 三河 065201）

針對Epidemic算法導(dǎo)致機(jī)會網(wǎng)絡(luò)擁塞引發(fā)的路由可靠性問題，提出一種基于信任機(jī)制的改進(jìn)Epidemic算法。通過構(gòu)建節(jié)點(diǎn)之間的信任機(jī)制，提供具有足夠可信度的節(jié)點(diǎn)作為消息的下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，使消息進(jìn)行有限規(guī)模的泛洪傳播。仿真實(shí)驗(yàn)結(jié)果和分析表明，改進(jìn)后的Epidemic算法避免了泛洪機(jī)制引發(fā)的網(wǎng)絡(luò)擁塞問題，并且在路由可靠性和傳輸性能上有一定的提高。

機(jī)會網(wǎng)絡(luò)；網(wǎng)絡(luò)擁塞；信任機(jī)制；Epidemic算法

1 引言

微型計(jì)算機(jī)和智能傳感器技術(shù)的發(fā)展推動著網(wǎng)絡(luò)形態(tài)的轉(zhuǎn)變，為擺脫只有建立端到端的通信路徑才能實(shí)現(xiàn)網(wǎng)絡(luò)通信的制約，提出了機(jī)會網(wǎng)絡(luò)[1,2]（opportunistic network）的概念。機(jī)會網(wǎng)絡(luò)屬于間歇式連通網(wǎng)絡(luò)，通信節(jié)點(diǎn)使用“存儲?攜帶?轉(zhuǎn)發(fā)”的路由模式，通過節(jié)點(diǎn)移動帶來的相遇機(jī)會逐跳實(shí)現(xiàn)通信，具有間接性連通、傳輸延遲大、錯(cuò)誤率高等特點(diǎn)。機(jī)會網(wǎng)絡(luò)降低了對通信基礎(chǔ)設(shè)施的依賴，目前廣泛應(yīng)用在手持設(shè)備組網(wǎng)、物聯(lián)網(wǎng)下的車載網(wǎng)絡(luò)[3]等方面。機(jī)會網(wǎng)絡(luò)中的關(guān)鍵技術(shù)有節(jié)點(diǎn)移動建模、網(wǎng)絡(luò)內(nèi)信息處理和路由算法[4]等。其中，最為經(jīng)典的一種機(jī)會路由算法是Epidemic算法[5]，該算法基于泛洪機(jī)制，消息源節(jié)點(diǎn)將數(shù)據(jù)分組復(fù)制給與之相遇的每一個(gè)節(jié)點(diǎn)，以“傳染病”的傳播方式將消息接力傳遞至目的節(jié)點(diǎn)。Epidemic算法在理論上具有最大傳輸成功率和最小傳輸延遲，但在無限泛洪策略下，數(shù)據(jù)間不斷發(fā)生碰撞搶奪有限的資源反而降低了機(jī)會網(wǎng)絡(luò)的傳輸性能。本文在Epidemic算法的基礎(chǔ)上，通過構(gòu)建機(jī)會路由的信任機(jī)制，為節(jié)點(diǎn)如何選擇可靠的下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)提供方法，控制Epidemic算法進(jìn)行有限度的泛洪傳播，從而優(yōu)化機(jī)會路由傳輸性能，提高機(jī)會路由可靠性。

2 相關(guān)工作

相比拓?fù)浞€(wěn)定的網(wǎng)絡(luò)模式，機(jī)會網(wǎng)絡(luò)路由算法面臨更大的挑戰(zhàn)。按照路由算法是否需要借助額外信息輔助可將路由算法分為零信息型和信息輔助型[6]。Epidemic算法屬于基于復(fù)制策略的零信息型數(shù)據(jù)轉(zhuǎn)發(fā)策略，這種路由算法設(shè)計(jì)思路直觀、易于實(shí)現(xiàn)，但也存在路由開銷大、可擴(kuò)展性較差等問題。在Epidemic算法基礎(chǔ)上衍生了大量的其他算法，文獻(xiàn)[7]提出一種具備自停止策略的Epidemic算法，分析網(wǎng)絡(luò)節(jié)點(diǎn)的移動模型和同步時(shí)間模型，避免數(shù)據(jù)分組抵達(dá)目的節(jié)點(diǎn)后仍然在網(wǎng)絡(luò)中蔓延，提高路由算法的效率并節(jié)約路由開銷。文獻(xiàn)[8]提出一種通過時(shí)延約束對節(jié)點(diǎn)數(shù)據(jù)分發(fā)進(jìn)行調(diào)度控制的策略，在節(jié)點(diǎn)狀態(tài)滿足最大時(shí)延要求的同時(shí)最大限度地減小能量消耗，并通過數(shù)學(xué)手段做進(jìn)一步分析，在相同時(shí)延要求下節(jié)省能量。文獻(xiàn)[9]通過優(yōu)化節(jié)點(diǎn)的緩存，在最佳的持續(xù)時(shí)間內(nèi)將消息轉(zhuǎn)發(fā)至另一節(jié)點(diǎn)，降低網(wǎng)絡(luò)負(fù)擔(dān)，提高路由算法的性能。文獻(xiàn)[10]使用馬爾可夫鏈分析Epidemic路由在一維稀疏雙線性ad hoc網(wǎng)絡(luò)中的應(yīng)用，減少消息時(shí)延和復(fù)制數(shù)量，佐證路由算法的正確性。文獻(xiàn)[11]提出一種具備自適應(yīng)調(diào)整的n-Epidemic路由協(xié)議，監(jiān)測節(jié)點(diǎn)周圍環(huán)境的能量水平確定復(fù)制數(shù)量，即參數(shù)n，通過能量水平進(jìn)行自適應(yīng)調(diào)整，降低網(wǎng)絡(luò)能耗延長網(wǎng)絡(luò)使用壽命。文獻(xiàn)[12]對延遲容忍網(wǎng)絡(luò)中Epidemic路由算法進(jìn)行能量消耗上的改進(jìn)，基于能量感知的方法優(yōu)化路由策略的能量消耗，節(jié)省路由開銷。文獻(xiàn)[13]提出一種有限傳染的數(shù)據(jù)分發(fā)機(jī)制，對網(wǎng)絡(luò)中的數(shù)據(jù)副本進(jìn)行控制，并在此基礎(chǔ)上提出一種能量平衡方案以提高網(wǎng)絡(luò)效率。文獻(xiàn)[14]提出DTN網(wǎng)絡(luò)中最佳能量感知的Epidemic路由，通過對能量的感知改善路由策略的性能，節(jié)省路由開銷。

以上工作將零信息型的Epidemic算法轉(zhuǎn)化為信息輔助型路由算法。文獻(xiàn)[7～11]通過引入調(diào)度控制策略，控制消息復(fù)制數(shù)量，避免網(wǎng)絡(luò)擁塞，但是引入這些策略后機(jī)會路由被人為地進(jìn)行了控制，忽視了機(jī)會網(wǎng)絡(luò)中節(jié)點(diǎn)的自主選擇性。文獻(xiàn)[12～14]通過感知周圍其他節(jié)點(diǎn)的能量，進(jìn)行相應(yīng)的調(diào)整，降低網(wǎng)絡(luò)能耗，但僅通過能量感知的方式關(guān)注節(jié)點(diǎn)的能量情況，不能全面地評價(jià)節(jié)點(diǎn)的轉(zhuǎn)發(fā)能力和路由性能。因此，這些工作不能達(dá)到簡單有效地改進(jìn)Epidemic算法的目的。本文提出一種基于信任機(jī)制的改進(jìn)Epidemic算法，通過建立信任機(jī)制，簡單有效地區(qū)分網(wǎng)絡(luò)中節(jié)點(diǎn)屬性，為消息如何選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)提供依據(jù)，避免泛洪策略引發(fā)的網(wǎng)絡(luò)擁塞，提高路由算法的傳輸性能，增加路由算法的可靠性。

3 信任機(jī)制

Epidemic算法采用泛洪的轉(zhuǎn)發(fā)方式傳遞消息，攜帶消息的源節(jié)點(diǎn)將消息復(fù)制給其遇到的每一個(gè)中間節(jié)點(diǎn)，中間節(jié)點(diǎn)無條件地接收并轉(zhuǎn)發(fā)這些數(shù)據(jù)分組。中間節(jié)點(diǎn)因其自身剩余存儲空間和能量的限制，具備的轉(zhuǎn)發(fā)能力不盡相同，一些重要程度不高的消息占據(jù)節(jié)點(diǎn)的存儲空間，消耗節(jié)點(diǎn)的能量，阻礙重要消息的傳遞，降低了網(wǎng)絡(luò)的使用效率。理論情況下，增加攜帶數(shù)據(jù)分組的節(jié)點(diǎn)數(shù)量，可以有效地增加與消息目的節(jié)點(diǎn)相遇的機(jī)會，提高消息的傳輸成功率。而實(shí)際情況下，使用Epidemic算法不能使節(jié)點(diǎn)充分利用自身資源進(jìn)行有效的數(shù)據(jù)分組轉(zhuǎn)發(fā)，導(dǎo)致自身資源浪費(fèi)的同時(shí)，影響機(jī)會網(wǎng)絡(luò)的通暢。為避免網(wǎng)絡(luò)擁塞導(dǎo)致的路由傳輸性能下降，在路由算法中引入一種交易機(jī)制，為消息源節(jié)點(diǎn)選擇可信度較高的下一跳節(jié)點(diǎn)提供方法，為區(qū)別Epidemic算法，本文提出的基于交易機(jī)制的改進(jìn)Epidemic算法命名為r-Epidemic算法。

3.1 相關(guān)定義

機(jī)會路由不具備穩(wěn)定的拓?fù)浣Y(jié)構(gòu)，消息傳至目的節(jié)點(diǎn)前并不清楚完整的傳輸路徑。在這種傳輸特性下，綜合影響機(jī)會路由傳輸性能的因素，制定了一種交易機(jī)制。將機(jī)會網(wǎng)絡(luò)中消息的傳遞過程虛擬為商品的交易過程，首先由消息的發(fā)起者即源節(jié)點(diǎn)對消息進(jìn)行定價(jià)，具有充足購買能力的中間節(jié)點(diǎn)獲得轉(zhuǎn)發(fā)消息的機(jī)會，攜帶消息繼續(xù)進(jìn)行移動，獲得消息的中間節(jié)點(diǎn)可繼續(xù)對消息進(jìn)行定價(jià)，獲得更多的收益和轉(zhuǎn)發(fā)機(jī)會。以下對交易機(jī)制中出現(xiàn)的概念和計(jì)算方法進(jìn)行定義。

定義1 將機(jī)會網(wǎng)絡(luò)中消息的傳遞過程虛擬為商品交易過程，將消息虛擬為具有交易價(jià)值的商品，定義信任值為虛擬交易中的貨幣，信任值是度量消息價(jià)值的唯一依據(jù)，信任值為可數(shù)常數(shù)，且可能出現(xiàn)負(fù)數(shù)，節(jié)點(diǎn)信譽(yù)值范圍不做限制，并賦予節(jié)點(diǎn)初始信任值為100。

定義2 消息的價(jià)值分為初始價(jià)值和二次價(jià)值，源節(jié)點(diǎn)對消息進(jìn)行初始定價(jià)，定價(jià)依據(jù)是消息的重要程度；其他中間節(jié)點(diǎn)可對消息進(jìn)行二次定價(jià)，二次定價(jià)的目的是為了避免攜帶消息的中間節(jié)點(diǎn)不能與目的節(jié)點(diǎn)相遇而導(dǎo)致自身價(jià)值的損失。

定義3 影響消息傳遞價(jià)值的主要因素是消息的剩余生存時(shí)間Tr，消息的生存周期Tmax由源節(jié)點(diǎn)確定，當(dāng)Tr=Tmax時(shí)消息具有最大的傳遞價(jià)值，隨著Tr的減少，消息的傳遞價(jià)值也減小。

定義4 影響中間節(jié)點(diǎn)轉(zhuǎn)發(fā)消息的主要因素為節(jié)點(diǎn)剩余存儲空間Sr和剩余能量Er，剩余存儲空間Sr影響節(jié)點(diǎn)能否正常復(fù)制轉(zhuǎn)發(fā)消息，剩余能量影響節(jié)點(diǎn)可轉(zhuǎn)發(fā)次數(shù)，兩者共同決定了節(jié)點(diǎn)在消息傳輸過程中獲得的價(jià)值。

以上幾個(gè)定義規(guī)定了影響消息價(jià)值和節(jié)點(diǎn)獲益的因素，為信任機(jī)制的構(gòu)建提供了前提條件，在通過構(gòu)建信任機(jī)制改進(jìn)Epidemic算法的研究中，構(gòu)建信任機(jī)制的核心算法是關(guān)鍵，以下定義信任機(jī)制中的相關(guān)算法。

定義5 使用字母V代表消息的價(jià)值，消息的初始定價(jià)Vout如式(1)所示。

二次定價(jià)與初始定價(jià)的唯一區(qū)別是引入了消息剩余生存時(shí)間的影響，二次定價(jià)一般發(fā)生在中間節(jié)點(diǎn)成功買入消息一段時(shí)間后仍未與消息目的節(jié)點(diǎn)相遇的情況，中間節(jié)點(diǎn)需要主動降低消息的價(jià)值，即節(jié)點(diǎn)降低轉(zhuǎn)發(fā)消息的價(jià)值門檻，使更多的節(jié)點(diǎn)參與消息轉(zhuǎn)發(fā)中，增加消息與目的節(jié)點(diǎn)相遇的概率，避免自身的信任值損失。

3.2 工作流程

r-Epidemic算法沿用原Epidemic算法采用泛洪機(jī)制的相關(guān)特點(diǎn)，引入了可受信任的交易機(jī)制對泛洪進(jìn)行約束，在特定范圍內(nèi)進(jìn)行有限度的泛洪，避免數(shù)據(jù)碰撞導(dǎo)致網(wǎng)絡(luò)擁塞，降低機(jī)會路由的開銷，增加數(shù)據(jù)傳輸效率，提高機(jī)會網(wǎng)絡(luò)的頑健性。r-Epidemic算法工作流程如圖1所示。

圖1 r-Epidemic算法消息轉(zhuǎn)發(fā)流程

4 博弈分析

前文敘述了r-Epidemic算法的工作機(jī)制，現(xiàn)將非主要因素簡化并將交易過程轉(zhuǎn)化為一個(gè)博弈對局過程，依據(jù)博弈[15]三要素原則，博弈的參與人是路由中參與消息轉(zhuǎn)發(fā)的節(jié)點(diǎn)；供博弈參與人博弈的策略為能否滿足復(fù)制消息的條件并據(jù)此選擇是否參與消息轉(zhuǎn)發(fā)；博弈中參與者的支付即節(jié)點(diǎn)的信任值收益。消息傳輸過程中，節(jié)點(diǎn)不能同時(shí)了解其他節(jié)點(diǎn)的獲益情況，并根據(jù)與攜帶消息節(jié)點(diǎn)相遇的順序進(jìn)行序貫決策，因此節(jié)點(diǎn)間的博弈是不完全信息動態(tài)博弈。r-Epidemic算法中的序貫博弈可表示為一個(gè)以源節(jié)點(diǎn)為根節(jié)點(diǎn)的博弈樹，中間節(jié)點(diǎn)是樹中的決策節(jié)點(diǎn)，末端節(jié)點(diǎn)則是消息的目的節(jié)點(diǎn)。從根節(jié)點(diǎn)至末端節(jié)點(diǎn)構(gòu)成一條完整的路由，由于不是所有與源節(jié)點(diǎn)相遇的中間節(jié)點(diǎn)都能成功完成交易，故此時(shí)的博弈樹不能成為一棵滿樹。在r-Epidemic算法中定義了中間節(jié)點(diǎn)可進(jìn)行二次定價(jià)，因此樹中的中間節(jié)點(diǎn)可以成為新的根節(jié)點(diǎn)，即樹的一枝又可以看成一棵以攜帶消息的中間節(jié)點(diǎn)為根節(jié)點(diǎn)的新樹，成為博弈的子博弈。作為決策節(jié)點(diǎn)希望獲得更多的利益，損失利益會減少獲得轉(zhuǎn)發(fā)消息的機(jī)會，故決策節(jié)點(diǎn)會在自身能力范圍內(nèi)盡可能地參與競價(jià)獲取轉(zhuǎn)發(fā)機(jī)會，同時(shí)獲得轉(zhuǎn)發(fā)機(jī)會的節(jié)點(diǎn)也會花費(fèi)自身的價(jià)值儲備，因此也擔(dān)負(fù)價(jià)值損失的風(fēng)險(xiǎn)。為了規(guī)避風(fēng)險(xiǎn)決策節(jié)點(diǎn)，要創(chuàng)造更多的轉(zhuǎn)發(fā)機(jī)會，這就增加了機(jī)會路由傳輸?shù)某晒β省?/p>

在r-Epidemic算法中，節(jié)點(diǎn)在不同的條件下會獲得不同的收益，且與轉(zhuǎn)發(fā)的次數(shù)相關(guān)。利用消息的價(jià)值公式可以改寫節(jié)點(diǎn)在轉(zhuǎn)發(fā)過程中的收益總量Vin，如式(3)所示，式(3)中n代表中間節(jié)點(diǎn)轉(zhuǎn)發(fā)消息的次數(shù)，N代表最大的轉(zhuǎn)發(fā)次數(shù)。

節(jié)點(diǎn)的收益矩陣如表1所示。

表1 節(jié)點(diǎn)收益

相比未獲得轉(zhuǎn)發(fā)機(jī)會，中間節(jié)點(diǎn)在獲得轉(zhuǎn)發(fā)機(jī)會時(shí)收獲較多的收益，因此機(jī)會網(wǎng)絡(luò)中的節(jié)點(diǎn)具備的信任值成為決定節(jié)點(diǎn)生存和發(fā)展的必要條件，且在轉(zhuǎn)發(fā)價(jià)值較高的消息過程中可以收獲更多的收益，故節(jié)點(diǎn)會更傾向于轉(zhuǎn)發(fā)價(jià)值較高的消息，但是由于機(jī)會網(wǎng)絡(luò)節(jié)點(diǎn)移動的不確定性和r-Epidemic算法的交易規(guī)則，獲得轉(zhuǎn)發(fā)機(jī)會的節(jié)點(diǎn)也面臨利益損失的威脅，即高收益的同時(shí)也面臨高風(fēng)險(xiǎn)。因此，此時(shí)節(jié)點(diǎn)會出現(xiàn)不同的信任值情況，這為遴選不同信任值的節(jié)點(diǎn)作為消息的下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)提供了可能，同時(shí)由于源節(jié)點(diǎn)對轉(zhuǎn)發(fā)節(jié)點(diǎn)的信任值要求，不符合信任值要求的轉(zhuǎn)發(fā)節(jié)點(diǎn)被遺棄，同時(shí)被遺棄的轉(zhuǎn)發(fā)節(jié)點(diǎn)可以通過轉(zhuǎn)發(fā)信任值要求較低的消息積累自身的信任值儲備。這為消息有選擇地在有限范圍內(nèi)進(jìn)行受控的泛洪傳播提供了可能，這是r-Epidemic算法相比Epidemic算法有所優(yōu)化的地方，且這種方法簡單、易操作。

5 仿真實(shí)驗(yàn)與結(jié)果分析

通過對r-Epidemic算法的博弈分析，相比基于泛洪機(jī)制的Epidemic算法，r-Epidemic算法通過以虛擬交易為基礎(chǔ)的信任機(jī)制，為消息如何選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)提供了方法，控制消息進(jìn)行有限度的泛洪傳播，這在減少機(jī)會網(wǎng)絡(luò)的路由開銷、提高機(jī)會路由的傳輸效率、增加機(jī)會網(wǎng)絡(luò)的可靠性上是有幫助的。在仿真實(shí)驗(yàn)部分采用機(jī)會網(wǎng)絡(luò)常用的ONE平臺[16]，模擬攜帶有智能傳輸設(shè)備的各型車輛行駛于城市中的場景，通過不同算法在傳輸成功率、傳輸時(shí)延、路由開銷上的差別進(jìn)行定量分析。同時(shí)，選取了經(jīng)典的Epidemic、Direct Delivery和First Contact等算法與r-Epidemic算法進(jìn)行性能上的對比，仿真界面如圖2所示。

圖2 仿真界面

仿真實(shí)驗(yàn)中設(shè)置的參數(shù)如表2所示。

表2 相關(guān)參數(shù)

5.1 路由開銷

路由開銷是在一定時(shí)間內(nèi)節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)分組的數(shù)量，路由的開銷越高，則網(wǎng)絡(luò)中數(shù)據(jù)分組數(shù)量越多，數(shù)據(jù)分組發(fā)生碰撞的機(jī)會越大，消耗的節(jié)點(diǎn)能量越多。路由開銷大會影響機(jī)會路由的傳輸流暢性，引發(fā)網(wǎng)絡(luò)擁塞，增加網(wǎng)絡(luò)運(yùn)行壓力。Epidemic算法最致命的弊端即路由開銷過大導(dǎo)致的網(wǎng)絡(luò)擁塞，r-Epidemic算法改進(jìn)的最主要目的就是在相對不損耗過多傳輸成功率的前提下降低機(jī)會路由的開銷，幾種算法在路由開銷上的對比如圖3所示。

圖3 路由開銷對比

相比基于泛洪機(jī)制的Epidemic算法的路由開銷，r-Epidemic算法的路由開銷有明顯下降，但仍然高于其他幾種算法，這是因?yàn)閞-Epidemic算法并未完全拋棄泛洪機(jī)制，而是對原Epidemic算法的優(yōu)化，控制節(jié)點(diǎn)進(jìn)行有限的泛洪傳播。在當(dāng)前情況下，由于路由開銷過大引發(fā)網(wǎng)絡(luò)擁塞的概率已降低40%左右。

5.2 傳輸時(shí)延

傳輸時(shí)延是數(shù)據(jù)分組從源節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)所需的時(shí)間，傳輸時(shí)延越小則路由的傳輸效率越高，縮小傳輸時(shí)延可以提高消息的時(shí)效性，同時(shí)可以釋放資源用于其他消息傳輸，提高機(jī)會網(wǎng)絡(luò)的使用效率，幾種路由算法傳輸時(shí)延上的對比如圖4所示。

圖4 傳輸時(shí)延對比

r-Epidemic算法的傳輸時(shí)延高于Epidemic算法10%左右，但兩者都低于其他路由算法，相比于Epidemic算法，r-Epidemic算法在降低40%的路由開銷的同時(shí)，傳輸時(shí)延提高了10%。而且，當(dāng)仿真實(shí)驗(yàn)在理想情況下進(jìn)行，并不能完全仿真泛洪傳播條件下引發(fā)網(wǎng)絡(luò)擁塞對傳輸時(shí)延的影響，因此r-Epidemic算法在傳輸時(shí)延這一性能指標(biāo)上是可以被接受的。

5.3 傳輸成功率

傳輸成功率指在一定時(shí)間內(nèi)成功到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)分組總數(shù)和源節(jié)點(diǎn)發(fā)出的需傳輸數(shù)據(jù)分組總數(shù)之比，傳輸成功率是確定路由模型正確轉(zhuǎn)發(fā)數(shù)據(jù)分組到目的節(jié)點(diǎn)的重要指標(biāo)，是評價(jià)路由算法性能的最重要因素，幾種算法在傳輸成功率上的對比如圖5所示。

隨著節(jié)點(diǎn)數(shù)量的增多，r-Epidemic算法的傳輸成功率趨于穩(wěn)定在50%左右，在機(jī)會網(wǎng)絡(luò)特殊的傳輸方式下屬于較高水平，相比于Epidemic算法有很大的提升。節(jié)點(diǎn)數(shù)量越多，由Epidemic算法導(dǎo)致的網(wǎng)絡(luò)擁塞現(xiàn)象越嚴(yán)重，對傳輸成功率的影響越大。

圖5 傳輸成功率對比

綜合r-Epidemic算法和Epidemic算法在上述3項(xiàng)性能指標(biāo)上的對比，對原有Epidemic算法優(yōu)化后的r-Epidemic算法，仍然延續(xù)了泛洪機(jī)制的一些特點(diǎn)，但是相比于Epidemic算法，r-Epidemic算法在路由開銷上降低了40%，在傳輸時(shí)延上增加了10%，同時(shí)在傳輸成功率上有較大的提升。因此，引入信任機(jī)制的r-Epidemic算法在整體的路由性能上相比于原Epidemic算法有較大的改進(jìn)，相比極端的路由算法在性能上做了一定的折中，傳輸性能更加穩(wěn)定和可靠，規(guī)避了路由可能出現(xiàn)的安全風(fēng)險(xiǎn)。

6 結(jié)束語

結(jié)合機(jī)會網(wǎng)絡(luò)的特點(diǎn)，本文提出一種Epidemic算法的改進(jìn)方案。將消息的傳輸過程虛擬為商品交易過程，使消息成為具有交易價(jià)值的商品，具有足夠購買能力的節(jié)點(diǎn)才能獲取消息轉(zhuǎn)發(fā)機(jī)會，為機(jī)會路由如何選擇轉(zhuǎn)發(fā)時(shí)機(jī)和下一跳節(jié)點(diǎn)提供了方法，并控制消息進(jìn)行有限度的泛洪傳播。實(shí)驗(yàn)結(jié)果表明，優(yōu)化后的r-Epidemic算法整體的路由性能和可靠性要明顯優(yōu)于原算法。

[1] PELUSI L, PASSARELLA A, CONTI M. Opportunistic networking: data forwarding in disconnected mobile ad hoc networks[J]. Communications Magazine, 2006, 44(11):134-141.

[2] BOLDRINI C, LEE K, ?NEN M, et al. Opportunistic networks[J]. Computer Communications, 2014, 48(14):1-4.

[3] WU Q W,LIU Q Z,ZHANG L, et al. A trusted routing protocol based on GeoDTN plus Nav in VANET[J]. China Communications, 2014, 11(s2):166-174.

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

[5] TEERAPONG C, WORRAWAT N, SUMET P. An efficient spreading epidemic routing for delay-tolerant network[C]//The 13th IEEE Annual Consumer Communications & Networking Conference (CCNC). 2016:473-476.

[6] MA H D, YUAN P Y, ZHAO D. Research progress on routing problem in mobile opportunistic networks[J]. Journal of Software, 2015, 26(3): 600-616.

[7] CHEN Z S, CHEN C. Self-stopping epidemic routing in cooperative wireless mobile sensor networks[C]//The IEEE 12th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob). 2016:1-7.

[8] HEEJUNG B, JUNGMIN S. Node scheduling control inspired by epidemic theory for data dissemination in wireless sensor-actuator networks with delay constraints[J].IEEE Transactions on Wireless Communications,2016,15(3): 1794-1807.

[9] AHMED E O, KHALID R, MOHAMED E K, et al. Optimal content caching for epidemic routing in delay tolerant networks[C]// International Conference on Wireless Networks and Mobile Communications (WINCOM). 2016:220-224.

[10] SUN H F, SONG L L. Performance analysis of epidemic routing in 1-d linear sparse VANETs[J]. IEEE Communications Letters, 2016, 20(10): 2087-2090.

[11] ZHANG F, WANG X M, LIN Y G, et al. Adaptive adjustments of n-Epidemic routing protocol for opportunistic networks[C]//2015 IEEE International Conference on Progress in Informatics and Computing (PIC). 2015:487-491.

[12] BHED B B. Improving energy consumption of epidemic routing in delay tolerant networks[C]//The 10th International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing (IMIS). 2016:278-283.

[13] GUO D, CHENG G, ZHANG Y, et al. Data distribution mechanism over opportunistic networks with limited epidemic[J]. China Communications,2015,12(6): 154-163.

[14] SOHEIL E, KHOUZANI M, SASWATI S,et al. Optimal energy-aware epidemic routing in DTNs[J].Transactions on Automatic Control, 2015, 60(6): 1554-1569.

[15] ZHANG Y X, HE J S, ZHAO B, et al. A privacy protection model base on game theory[J]. Chinese Journal of Computers, 2016, 39(3): 615-627.

[16] TETSUYA O,DONALD E, EVJOLA S, et al. A simulation system based on one and SUMO simulators: performance evaluation of direct delivery, epidemic and energy aware epidemic DTN protocols[C]//The 18th International Conference on Network-Based Information Systems. 2015: 418-423.

Improved Epidemic algorithm based on trust mechanism in opportunistic networks

ZHANG Guang-hua1,2, PANG Shao-bo2, YANG Yao-hong2, CHEN Zhen-guo3

（1. State Key Laboratory of Integrated Services Networks, Xidian University, Xi’an 710071, China; 2. College of Information Science and Engineering, Hebei University of Science and Technology, Shijiazhuang 050000, China; 3. Hebei Engineering Technology Research Center for IOT Data Acquisition & Processing, North China Institute of Science and Technology, Sanhe 065201, China)

Aiming at the problem of routing reliability caused by Epidemic algorithm, an improved Epidemic algorithm based on trust mechanism was proposed. Through the establishment of trust mechanism between nodes, this mechanism can provide sufficient trusted nodes as the next hop node of message forwarding, and can promote that the Epidemic algorithm performs the limited scope of flooding under the constraint of trust mechanism. Simulation results and analysis show that the improved Epidemic algorithm can avoid the network congestion caused by flooding mechanism, and the reliability of routing and transmission performance are improved to some extent.

opportunistic network, network congestion, trust mechanism, Epidemic algorithm

s: The National Natural Science Foundation of China (No.61572255), The China Postdoctoral Science Foundation (No.2015M582622), The University Scientific Research Foundation of Hebei Province (No.YQ2014036, No.QN2017062), The Technology Research and Development Program of Hebei Province (No.15210338, No.15210703)

TP393

A

10.11959/j.issn.2096-109x.2017.00187

張光華（1979-），男，河北石家莊人，博士，河北科技大學(xué)副教授，主要研究方向?yàn)榫W(wǎng)絡(luò)與信息安全。

龐少博（1992-），男，河北承德人，河北科技大學(xué)碩士生，主要研究方向?yàn)榫W(wǎng)絡(luò)與信息安全。

楊耀紅（1992-），女，河北邢臺人，河北科技大學(xué)碩士生，主要研究方向?yàn)榫W(wǎng)絡(luò)與信息安全。

陳振國（1976-），男，山東冠縣人，博士，華北科技學(xué)院副教授，主要研究方向?yàn)槲锫?lián)網(wǎng)安全。

2017-05-21；

2017-07-02。通信作者：張光華，xian_softwure@163.com

國家自然科學(xué)基金資助項(xiàng)目（No.61572255）；中國博士后科學(xué)基金資助項(xiàng)目（No.2015M582622）；河北省高等學(xué)校科學(xué)技術(shù)研究資助項(xiàng)目（No.YQ2014036, No.QN2017062）；河北省科學(xué)技術(shù)研究與發(fā)展計(jì)劃基金資助項(xiàng)目（No.15210338, No.15210703）