本站小編為你精心準備了機會網(wǎng)絡(luò)中的緩存路由算法參考范文，愿這些范文能點燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

摘要：機會網(wǎng)絡(luò)是一種通過節(jié)點移動建立通信鏈路的無線自組織網(wǎng)絡(luò)，一般通過消息復(fù)制的路由策略傳遞信息。但該方式將導(dǎo)致鏈路中存在大量消息副本，對節(jié)點緩存形成巨大壓力，造成網(wǎng)絡(luò)擁塞。針對該情況，結(jié)合Prophet算法，充分考慮節(jié)點緩存對鏈路狀態(tài)及傳輸概率的影響，設(shè)計限制消息最大副本數(shù)量與及時刪除節(jié)點緩存中不必要數(shù)據(jù)包的緩存管理機制，同時在Prophet算法中考慮了緩存比因素。仿真結(jié)果表明，該算法可以有效提高消息投遞率，降低網(wǎng)絡(luò)消耗。

關(guān)鍵詞：機會網(wǎng)絡(luò)；Prophet算法；緩存區(qū)管理；擁塞控制

引言

如何在不需要提前建立端到端鏈路的情況下，利用設(shè)備的移動性快速形成自組織網(wǎng)絡(luò)，達到在網(wǎng)絡(luò)中進行消息傳遞的目標，是目前無線自組織網(wǎng)絡(luò)研究中的熱點。在緊急情況下，經(jīng)常會遇到原有鏈路被破壞，需要通過現(xiàn)有設(shè)備建立一條新鏈路的情況，如何在該情況下進行有效的數(shù)據(jù)傳輸是目前需要解決的一個難題。為此，研究人員結(jié)合MANET（MobileandAdHocNetwork）與DTN［1］（Delay-toler⁃antNetwork）的特點，提出機會網(wǎng)路（OpportunisticNetwork）的概念［2］。機會網(wǎng)絡(luò)是一種不需要源節(jié)點與目的節(jié)點之間存在一條完整鏈路，而是通過節(jié)點移動過程中形成的相遇機會建立通信的自組織網(wǎng)絡(luò)。機會網(wǎng)絡(luò)相對于傳統(tǒng)網(wǎng)絡(luò)表現(xiàn)出更好的適應(yīng)性，更加符合自組織網(wǎng)絡(luò)的要求，因此近年來引起國內(nèi)外研究者的廣泛關(guān)注，并開展了大量應(yīng)用研究，如在災(zāi)難發(fā)生的緊急狀況下構(gòu)建自組織網(wǎng)絡(luò)［3］，以及可用于觀察海洋生物種群［4］與監(jiān)察自然環(huán)境下放牧系統(tǒng)［5］的移動自組織網(wǎng)絡(luò)等。由于機會網(wǎng)絡(luò)是以“存儲—攜帶—轉(zhuǎn)發(fā)”的路由機制模式開展工作的，在該模式下要求網(wǎng)絡(luò)提供節(jié)點的可靠性保證，節(jié)點在未選取好下一跳轉(zhuǎn)發(fā)節(jié)點時，中間節(jié)點不能丟棄數(shù)據(jù)［6-7］。當網(wǎng)絡(luò)中的大量數(shù)據(jù)需要被傳輸時，節(jié)點的緩存利用率較高，易造成網(wǎng)絡(luò)擁塞，影響數(shù)據(jù)正常傳輸。因此，在機會網(wǎng)絡(luò)中，擁塞控制是保證網(wǎng)絡(luò)穩(wěn)定性與可靠性的關(guān)鍵因素。機會網(wǎng)絡(luò)中針對擁塞控制情況有以下兩種解決方法：①限制消息副本數(shù)量，避免生成不必要的數(shù)據(jù)包。消息在鏈路中一般采用消息復(fù)制方式傳輸給下一跳節(jié)點，對于未對消息副本進行合理控制的路由算法而言，在消息傳輸過程中，網(wǎng)絡(luò)中會存在大量消息副本，因而極大地影響了網(wǎng)絡(luò)性能［7］。針對該問題，文獻［8］、［9］提出限制消息副本數(shù)量的路由機制，以減少因生成大量不必要數(shù)據(jù)包對網(wǎng)絡(luò)造成的壓力；②及時刪除不必要的數(shù)據(jù)包。當網(wǎng)絡(luò)中的數(shù)據(jù)包已傳輸成功或不需要傳輸時，數(shù)據(jù)包若還滯留在節(jié)點緩存中，易造成節(jié)點緩存溢出，不僅導(dǎo)致數(shù)據(jù)無法得到及時傳輸，更極大地浪費了網(wǎng)絡(luò)資源。因此，針對不必要的數(shù)據(jù)包，可以使用DLR、DL、DOA、DY等刪包方式進行處理［9-10］。為避免網(wǎng)絡(luò)出現(xiàn)擁塞狀況，保證網(wǎng)絡(luò)即使在高吞吐量的環(huán)境中也能正常傳輸數(shù)據(jù)是本文的研究重點。Prophet（ProbabilisticRoutingProtocolUsingHistoryofEncountersandTransitivity）算法通過比較節(jié)點之間的相遇概率，選擇是否將消息轉(zhuǎn)發(fā)給中間節(jié)點。該工作機制可大幅減少網(wǎng)絡(luò)中的副本數(shù)量，但還沒有完全考慮到消息副本數(shù)量對節(jié)點緩存的影響。本文結(jié)合Prophet算法特點，提出控制消息副本數(shù)量以及考慮節(jié)點剩余緩存以避免擁塞的機制，從而有效提高消息投遞率。

1相關(guān)工作

機會網(wǎng)絡(luò)中的節(jié)點是具有移動性，且不穩(wěn)定的，源節(jié)點與目的節(jié)點之間不存在一條已連接好的端到端的路徑，即使在鏈路斷開的情況下，也可以實現(xiàn)消息的逐跳轉(zhuǎn)發(fā)，并成功傳輸消息。因此，其可以看成是具有一般DTN網(wǎng)絡(luò)特征的無線自組織網(wǎng)絡(luò)，更加符合自組織網(wǎng)絡(luò)的需求［11-12］。目前，基本的機會路由算法可以分為兩大類［13］：基于復(fù)制的路由算法與基于效用的路由算法。基于復(fù)制的路由算法是通過復(fù)制消息副本傳輸數(shù)據(jù)，在網(wǎng)絡(luò)中形成多消息存儲的路由策略，典型路由算法有Epidemic算法等［9］；基于效用的路由算法是以一個效用值為衡量標準，為中間轉(zhuǎn)發(fā)節(jié)點的選取提供參考因素。本文討論的Prophet算法即是根據(jù)節(jié)點之間的轉(zhuǎn)發(fā)概率篩選節(jié)點，進行數(shù)據(jù)轉(zhuǎn)發(fā)［10］。在基于復(fù)制與基于效用的經(jīng)典算法中，未考慮到消息副本數(shù)量過多對節(jié)點緩存的影響，導(dǎo)致網(wǎng)路性能下降，因此具有一定局限性［11-12］。Prophet是一種基于概率轉(zhuǎn)發(fā)的路由算法，節(jié)點在選擇下一跳節(jié)點時會根據(jù)相遇概率傳輸消息，節(jié)點之間的概率在相遇時升高，分開時則隨著時間延長而降低。Prophet算法的工作機制是只要遇到比自己傳輸概率大的節(jié)點則會復(fù)制一個消息副本給對方。基于效用的轉(zhuǎn)發(fā)方式雖然在一定程度上控制了消息的轉(zhuǎn)發(fā)副本數(shù)，但還沒有減少不必要消息對節(jié)點緩存的影響。當節(jié)點接收新消息時，會判斷自己是否有足夠的緩存區(qū)，如果緩存區(qū)不夠，則根據(jù)消息在緩存區(qū)的時間長短刪除數(shù)據(jù)包，在緩存區(qū)中時間越長的數(shù)據(jù)包越容易被刪除。因此，需要設(shè)置一個消息的生存期時間以控制消息生命長短，以便于刪除不必要的數(shù)據(jù)包。傳統(tǒng)Prophet算法是通過比較相遇節(jié)點與目的節(jié)點的概率值決定是否將消息傳輸給相遇節(jié)點，假設(shè)a、b兩點相遇，a、b兩節(jié)點的概率值通過式（1）進行更新。式中，Pinit是預(yù)先設(shè)置的兩節(jié)點之間的初始概率，γ是老化因子，γ∈［0，1］，k表示距離上一次更新的時間長度。Prophet算法的概率還具有傳遞性，即a節(jié)點與b節(jié)點經(jīng)常接觸，b節(jié)點與c節(jié)點也經(jīng)常接觸，則節(jié)點b可作為節(jié)點a和節(jié)點c消息轉(zhuǎn)發(fā)的中間節(jié)點，節(jié)點a、b、c的傳遞概率可按照公式（3）進行更新。3）式中，β是一個常數(shù)，β∈（0，1），其決定了消息經(jīng)過中間節(jié)點傳遞后對整體數(shù)據(jù)傳輸成功概率的影響。雖然Prophet算法中概率的傳遞性可以有效減少數(shù)據(jù)廣播引起的擁塞現(xiàn)象，但一旦擁塞現(xiàn)象發(fā)生，會極大地影響算法性能。如圖1所示，若節(jié)點a、b與節(jié)點b、c都可以經(jīng)常保持連接，根據(jù)Prophet算法的傳遞性，b節(jié)點即可作為a、c節(jié)點傳輸鏈路上的中間節(jié)點，并保持較高的投遞率，但若b節(jié)點的緩存此時正處于擁塞狀態(tài)，a、c節(jié)點鏈路上的數(shù)據(jù)包則無法正常轉(zhuǎn)發(fā)。所以即使Prophet算法根據(jù)概率值的傳遞性選取了最好的中間轉(zhuǎn)發(fā)節(jié)點，但若未考慮到中間節(jié)點的緩存情況，則無法合理地發(fā)揮該算法優(yōu)點。如果此時a節(jié)點將消息轉(zhuǎn)發(fā)給b節(jié)點，該消息則會溢出，否則a節(jié)點只能將消息保存在本地中，等待下一個合適節(jié)點進行轉(zhuǎn)發(fā)。

2Prophet算法改進

雖然Prophet算法根據(jù)概率效用值選擇轉(zhuǎn)發(fā)節(jié)點的工作機制已在一定程度上減輕了網(wǎng)絡(luò)中的擁塞情況，但仍未考慮節(jié)點緩存對算法性能的影響。機會網(wǎng)絡(luò)是一個以“存儲—攜帶—轉(zhuǎn)發(fā)”模式工作的自組織網(wǎng)絡(luò)，一個節(jié)點如果處于鏈路中的關(guān)鍵位置，則其需要轉(zhuǎn)發(fā)的消息越多，而消息數(shù)量及大小與該節(jié)點緩存情況密切相關(guān)。如果節(jié)點緩存情況可以得到有效管理，則會提高消息傳輸?shù)某晒β省Ｔ诰W(wǎng)絡(luò)中，消息數(shù)量及大小都是隨機的，但節(jié)點緩存卻是固定的，只有對節(jié)點緩存情況進行有效控制，才能保證后續(xù)消息得到正常轉(zhuǎn)發(fā)［11］。

2.1節(jié)點緩存比

本文不僅針對節(jié)點緩存提出了有效的管理機制，還添加了緩存比效用因素，即算法在基于相遇概率選擇轉(zhuǎn)發(fā)節(jié)點基礎(chǔ)上，同時考慮了節(jié)點緩存情況，選擇轉(zhuǎn)發(fā)成功率較高與緩存壓力較小的節(jié)點作為轉(zhuǎn)發(fā)節(jié)點。該方法能更加有效地避免擁塞現(xiàn)象產(chǎn)生，增加數(shù)據(jù)包投遞率。節(jié)點緩存比定義如下：式中，mi表示消息數(shù)量，Si表示消息大小，Btotal表示節(jié)點緩存大小。

2.2節(jié)點緩存管理機制

本文提出的控制節(jié)點緩存數(shù)據(jù)包數(shù)量的管理機制主要包括以下兩方面：（1）限制消息在傳輸過程中的最大副本數(shù)。由于Prophet算法在傳輸消息時是通過復(fù)制消息副本的方式工作的，沒有限制消息的最大副本數(shù)，當消息在網(wǎng)絡(luò)中傳遞且數(shù)量足夠多時，可以推測該消息已成功傳輸，此時再復(fù)制該消息副本無疑將給網(wǎng)絡(luò)帶來更大壓力。因此，為每一個消息設(shè)置最大副本數(shù)量，當達到該上限時則停止復(fù)制消息，可以減少網(wǎng)絡(luò)冗余。（2）及時刪除已傳輸成功的消息。已傳輸成功的數(shù)據(jù)包在網(wǎng)絡(luò)中是無用的，并且會極大地占用緩存。其不一定是長期滯留在緩存中的老數(shù)據(jù)包，也可能是新包傳輸成功，但未被及時刪除。及時刪除已傳輸成功的數(shù)據(jù)包可以有效改善緩存情況，減少資源浪費。

3路由算法設(shè)計

本文提出的改進Prophet算法的核心思想在于控制節(jié)點緩存區(qū)，包括限制消息最大副本數(shù)目與及時刪除網(wǎng)絡(luò)中不必要的數(shù)據(jù)包。針對以上兩點操作可以有效降低緩存區(qū)壓力，保證節(jié)點不會因緩存區(qū)溢出導(dǎo)致消息無法正常傳輸。在此基礎(chǔ)之上，Prophet算法在選擇轉(zhuǎn)發(fā)節(jié)點時進一步考慮了緩存比因素，其改進算法步驟如下：（1）a、b節(jié)點通過移動進入彼此通信范圍，建立連接。（2）兩節(jié)點交換彼此在本地保存的與鏈路中其它節(jié)點的傳遞概率。（3）根據(jù)式（2）計算節(jié)點a、b的傳遞概率，并考慮此時節(jié)點b緩存比Rb的情況。（4）節(jié)點a中有傳輸?shù)侥康墓?jié)點s的消息，但該消息并不存在于節(jié)點b中，此時比較P（a，s）與P（b，s）*Rb大小，若P（a，s）<P（b，s）*Rb，則說明b節(jié)點傳輸成功率更高，選擇復(fù)制該消息副本給節(jié)點b，反之則不復(fù)制。

4實驗仿真與性能分析

4.1實驗仿真設(shè)置

本文使用仿真工具ONE［12］（OpportunisticNetworkEn⁃vironmentSimulator）對改進算法進行實驗分析及性能比較，驗證本文提出的改進算法是否可以有效改善網(wǎng)絡(luò)性能、解決擁塞情況。本文模擬了一些經(jīng)典場景下節(jié)點移動的消息傳遞情況，如學(xué)校、社區(qū)及工作區(qū)，這些場景的節(jié)點移動范圍都存在一定規(guī)律性，但節(jié)點移動速度和方向是隨機的。采用移動模型模擬這些移動場景，實驗參數(shù)如表1所示。在上述場景下，本文分別對原Prophet算法、改進后的Prophet算法和Epidemic算法從網(wǎng)絡(luò)性能的3個方面進行比較，分別是傳輸成功率、網(wǎng)絡(luò)開銷和傳輸延遲，比較在節(jié)點數(shù)量逐漸增加時網(wǎng)絡(luò)性能的差異。

4.2仿真結(jié)果與分析

本文對原Prophet算法、改進后的Prophet算法和Epi⁃demic算法在不同節(jié)點數(shù)量時表現(xiàn)出的網(wǎng)絡(luò)性能進行測試，仿真結(jié)果如圖2-圖4所示。在圖2中，隨著節(jié)點數(shù)量的增加，由于原Prophet算法和Epidemic是通過復(fù)制消息的方式在網(wǎng)絡(luò)中傳輸?shù)模?jié)點數(shù)量較多會增加節(jié)點之間的接觸概率，導(dǎo)致消息副本在網(wǎng)絡(luò)中的數(shù)量不斷增加。當緩存溢出時，消息則無法得到正常傳輸。改進后的Prophet算法考慮到了緩存情況，假設(shè)節(jié)點緩存已經(jīng)溢出，則該節(jié)點不會被選為下一跳節(jié)點，而是尋找其它適合的節(jié)點進行傳遞，使消息可以正常傳輸。在圖3中，隨著節(jié)點數(shù)量的增加，改進后的Prophet算法由于對緩存進行了管理，避免了消息在轉(zhuǎn)發(fā)時選擇緩存使用率高的節(jié)點，從而降低了算法開銷，所以其網(wǎng)絡(luò)開銷一直保持在一個較低水平。但其它兩個算法都是基于消息復(fù)制的路由算法，隨著網(wǎng)絡(luò)中消息副本的數(shù)量不斷增多，并且沒有解決節(jié)點緩存問題，因此易造成網(wǎng)絡(luò)擁塞，增加網(wǎng)絡(luò)開銷。在圖4中，改進Prophet算法在傳輸時間上多于其它兩種算法，主要因為改進Prophet算法控制了網(wǎng)絡(luò)中的消息副本數(shù)量，從而減少了與目的節(jié)點的相遇機會，在一定程度上也增加了消息傳輸?shù)侥康墓?jié)點的時間，所以傳輸過程中比其它兩個在網(wǎng)絡(luò)中消息副本較多的算法花費時間更多。還有一個原因是在沒有找到合適的轉(zhuǎn)發(fā)節(jié)點時，節(jié)點會將消息保存在本地，直到遇到合適的下一跳節(jié)點才開始傳輸，從而導(dǎo)致傳輸延遲。

5結(jié)語

本文分析了機會網(wǎng)絡(luò)中存在的消息冗余情況，提出了設(shè)置消息最大副本數(shù)量與及時刪除不必要數(shù)據(jù)包的節(jié)點緩存管理機制，并在Prophet算法基礎(chǔ)上考慮了緩存比因素，設(shè)計了一個考慮節(jié)點緩存的改進Prophet算法。仿真結(jié)果表明，在相同條件下，改進算法相比于原Prophet算法及Epidemic算法，具有更高的消息投遞率，可以有效防止網(wǎng)絡(luò)擁塞情況發(fā)生，提高網(wǎng)絡(luò)吞吐量。

作者：陳偉潔 單位：上海理工大學(xué)