機會網絡下基于信任機制的改進Epidemic算法

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

（1. 西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室，陜西 西安 710071；2. 河北科技大學信息科學與工程學院，河北 石家莊 050000；3. 華北科技學院河北省物聯網數據采集與處理工程技術研究中心，河北 三河 065201）

機會網絡下基于信任機制的改進Epidemic算法

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

（1. 西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室，陜西 西安 710071；2. 河北科技大學信息科學與工程學院，河北 石家莊 050000；3. 華北科技學院河北省物聯網數據采集與處理工程技術研究中心，河北 三河 065201）

針對Epidemic算法導致機會網絡擁塞引發的路由可靠性問題，提出一種基于信任機制的改進Epidemic算法。通過構建節點之間的信任機制，提供具有足夠可信度的節點作為消息的下一跳轉發節點，使消息進行有限規模的泛洪傳播。仿真實驗結果和分析表明，改進后的Epidemic算法避免了泛洪機制引發的網絡擁塞問題，并且在路由可靠性和傳輸性能上有一定的提高。

機會網絡；網絡擁塞；信任機制；Epidemic算法

1 引言

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

2 相關工作

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

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

3 信任機制

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

3.1 相關定義

機會路由不具備穩定的拓撲結構，消息傳至目的節點前并不清楚完整的傳輸路徑。在這種傳輸特性下，綜合影響機會路由傳輸性能的因素，制定了一種交易機制。將機會網絡中消息的傳遞過程虛擬為商品的交易過程，首先由消息的發起者即源節點對消息進行定價，具有充足購買能力的中間節點獲得轉發消息的機會，攜帶消息繼續進行移動，獲得消息的中間節點可繼續對消息進行定價，獲得更多的收益和轉發機會。以下對交易機制中出現的概念和計算方法進行定義。

定義1 將機會網絡中消息的傳遞過程虛擬為商品交易過程，將消息虛擬為具有交易價值的商品，定義信任值為虛擬交易中的貨幣，信任值是度量消息價值的唯一依據，信任值為可數常數，且可能出現負數，節點信譽值范圍不做限制，并賦予節點初始信任值為100。

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

定義3 影響消息傳遞價值的主要因素是消息的剩余生存時間Tr，消息的生存周期Tmax由源節點確定，當Tr=Tmax時消息具有最大的傳遞價值，隨著Tr的減少，消息的傳遞價值也減小。

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

以上幾個定義規定了影響消息價值和節點獲益的因素，為信任機制的構建提供了前提條件，在通過構建信任機制改進Epidemic算法的研究中，構建信任機制的核心算法是關鍵，以下定義信任機制中的相關算法。

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

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

3.2 工作流程

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

圖1 r-Epidemic算法消息轉發流程

4 博弈分析

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

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

節點的收益矩陣如表1所示。

表1 節點收益

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

5 仿真實驗與結果分析

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

圖2 仿真界面

仿真實驗中設置的參數如表2所示。

表2 相關參數

5.1 路由開銷

路由開銷是在一定時間內節點轉發的數據分組的數量，路由的開銷越高，則網絡中數據分組數量越多，數據分組發生碰撞的機會越大，消耗的節點能量越多。路由開銷大會影響機會路由的傳輸流暢性，引發網絡擁塞，增加網絡運行壓力。Epidemic算法最致命的弊端即路由開銷過大導致的網絡擁塞，r-Epidemic算法改進的最主要目的就是在相對不損耗過多傳輸成功率的前提下降低機會路由的開銷，幾種算法在路由開銷上的對比如圖3所示。

圖3 路由開銷對比

相比基于泛洪機制的Epidemic算法的路由開銷，r-Epidemic算法的路由開銷有明顯下降，但仍然高于其他幾種算法，這是因為r-Epidemic算法并未完全拋棄泛洪機制，而是對原Epidemic算法的優化，控制節點進行有限的泛洪傳播。在當前情況下，由于路由開銷過大引發網絡擁塞的概率已降低40%左右。

5.2 傳輸時延

傳輸時延是數據分組從源節點到達目的節點所需的時間，傳輸時延越小則路由的傳輸效率越高，縮小傳輸時延可以提高消息的時效性，同時可以釋放資源用于其他消息傳輸，提高機會網絡的使用效率，幾種路由算法傳輸時延上的對比如圖4所示。

圖4 傳輸時延對比

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

5.3 傳輸成功率

傳輸成功率指在一定時間內成功到達目的節點的數據分組總數和源節點發出的需傳輸數據分組總數之比，傳輸成功率是確定路由模型正確轉發數據分組到目的節點的重要指標，是評價路由算法性能的最重要因素，幾種算法在傳輸成功率上的對比如圖5所示。

隨著節點數量的增多，r-Epidemic算法的傳輸成功率趨于穩定在50%左右，在機會網絡特殊的傳輸方式下屬于較高水平，相比于Epidemic算法有很大的提升。節點數量越多，由Epidemic算法導致的網絡擁塞現象越嚴重，對傳輸成功率的影響越大。

圖5 傳輸成功率對比

綜合r-Epidemic算法和Epidemic算法在上述3項性能指標上的對比，對原有Epidemic算法優化后的r-Epidemic算法，仍然延續了泛洪機制的一些特點，但是相比于Epidemic算法，r-Epidemic算法在路由開銷上降低了40%，在傳輸時延上增加了10%，同時在傳輸成功率上有較大的提升。因此，引入信任機制的r-Epidemic算法在整體的路由性能上相比于原Epidemic算法有較大的改進，相比極端的路由算法在性能上做了一定的折中，傳輸性能更加穩定和可靠，規避了路由可能出現的安全風險。

6 結束語

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

[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-），男，河北石家莊人，博士，河北科技大學副教授，主要研究方向為網絡與信息安全。

龐少博（1992-），男，河北承德人，河北科技大學碩士生，主要研究方向為網絡與信息安全。

楊耀紅（1992-），女，河北邢臺人，河北科技大學碩士生，主要研究方向為網絡與信息安全。

陳振國（1976-），男，山東冠縣人，博士，華北科技學院副教授，主要研究方向為物聯網安全。

2017-05-21；

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

國家自然科學基金資助項目（No.61572255）；中國博士后科學基金資助項目（No.2015M582622）；河北省高等學校科學技術研究資助項目（No.YQ2014036, No.QN2017062）；河北省科學技術研究與發展計劃基金資助項目（No.15210338, No.15210703）