容遲網(wǎng)絡(luò)路由算法

容遲網(wǎng)絡(luò)中路由算法摘要：容遲網(wǎng)絡(luò)的主要目標(biāo)是支持具有鏈路間歇性連通、時(shí)延大、錯(cuò)誤率高等通信特征的不同網(wǎng)絡(luò)的互聯(lián)和互操作；由于節(jié)點(diǎn)移動(dòng)性、鏈路間歇連通、網(wǎng)絡(luò)頻繁割裂等特點(diǎn)，容遲網(wǎng)絡(luò)中的源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間在多數(shù)情景下不存在一條連通路徑，因此節(jié)點(diǎn)采用“存儲(chǔ)攜帶轉(zhuǎn)發(fā)”的路由模式。數(shù)據(jù)轉(zhuǎn)發(fā)算法是移動(dòng)容遲網(wǎng)絡(luò)研究的一個(gè)重要方面。相比傳統(tǒng)無(wú)線傳感器網(wǎng)絡(luò)的路由算法，移動(dòng)容遲網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)發(fā)算法不僅要提高網(wǎng)絡(luò)節(jié)點(diǎn)的能量效率、延長(zhǎng)網(wǎng)絡(luò)生存期，對(duì)如何提高消息傳輸成功率、降低消息傳輸時(shí)延與通信開(kāi)銷的研究則更加具有實(shí)際意義?，F(xiàn)有的移動(dòng)容遲網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)算法大致可分為：基于消息復(fù)制的轉(zhuǎn)發(fā)算法、基于歷史信息的轉(zhuǎn)發(fā)算法、基于先驗(yàn)知識(shí)的轉(zhuǎn)發(fā)算法、基礎(chǔ)設(shè)施輔助的轉(zhuǎn)發(fā)算法和基于社會(huì)網(wǎng)絡(luò)的轉(zhuǎn)發(fā)算法。關(guān)鍵詞容遲網(wǎng)絡(luò)；社會(huì)網(wǎng)絡(luò)；路由協(xié)議；數(shù)據(jù)分發(fā)；優(yōu)化算法容遲網(wǎng)絡(luò)(DelayTolerantNetworks,DTNs)是近年來(lái)無(wú)線網(wǎng)絡(luò)領(lǐng)域內(nèi)的一個(gè)研究熱點(diǎn)，泛指部署在極端環(huán)境下由于節(jié)點(diǎn)的移動(dòng)或者能量調(diào)度等原因而導(dǎo)致節(jié)點(diǎn)間只能間歇性進(jìn)行通倍甚至長(zhǎng)時(shí)間處于中斷狀態(tài)的一類網(wǎng)絡(luò)[1-3]。其概念起源于星際網(wǎng)絡(luò)(InterplanetaryInternet,IPN),與傳統(tǒng)通信網(wǎng)絡(luò)模型相比，移動(dòng)容遲網(wǎng)絡(luò)具有網(wǎng)絡(luò)間歇性連通、節(jié)點(diǎn)資源受限、傳播時(shí)延高等特點(diǎn)。DTN作為未來(lái)互聯(lián)網(wǎng)絡(luò)發(fā)展的一個(gè)新方向，在環(huán)境監(jiān)測(cè)、交通管理、水下探測(cè)和發(fā)展中國(guó)家偏遠(yuǎn)地區(qū)網(wǎng)絡(luò)基礎(chǔ)建設(shè)具有廣泛的應(yīng)用前景和實(shí)用價(jià)值。如何做出正確高效的路由選擇一直是無(wú)線網(wǎng)絡(luò)領(lǐng)域內(nèi)的關(guān)鍵技術(shù)和主要研究課題，然而傳統(tǒng)的基于的路由協(xié)議、移動(dòng)網(wǎng)絡(luò)和無(wú)線傳感網(wǎng)絡(luò)的路由協(xié)議均很難在容遲網(wǎng)絡(luò)中工作。一方面，與傳統(tǒng)通信網(wǎng)絡(luò)模型不同，移動(dòng)容遲網(wǎng)絡(luò)中不存在穩(wěn)定可靠的端到端鏈路，使得現(xiàn)有的基于端到端連通性假設(shè)的無(wú)線傳感器網(wǎng)絡(luò)路由算法不能適用于該網(wǎng)絡(luò)環(huán)境。另一方面，相對(duì)于傳統(tǒng)的無(wú)線傳感器網(wǎng)絡(luò)路算法，移動(dòng)容遲網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)算法不僅需要綜合考慮如何提高網(wǎng)絡(luò)節(jié)點(diǎn)的能量效率延長(zhǎng)網(wǎng)絡(luò)生存期，研究如何提高消息傳輸成功率、降低消息傳輸延遲與通信開(kāi)銷則具有更加實(shí)際的意義。目前，移動(dòng)容遲網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)發(fā)算法大致可分為以下幾種方式：基于消息復(fù)制的轉(zhuǎn)發(fā)算法、基于歷史信息的轉(zhuǎn)發(fā)算法、基于先驗(yàn)知識(shí)的轉(zhuǎn)發(fā)算法、基礎(chǔ)設(shè)施輔助的轉(zhuǎn)發(fā)算法和基于社會(huì)網(wǎng)絡(luò)的轉(zhuǎn)發(fā)算法。容遲網(wǎng)絡(luò)概述1.1容遲網(wǎng)絡(luò)起源上世紀(jì)九十年代，美國(guó)國(guó)家航空航天局(NationalAeronauticsandSpaceAdministration,NASA)等研究機(jī)構(gòu)在美國(guó)國(guó)防部高級(jí)研究計(jì)劃署(DefenseAdvancedResearchProjectsAgency,DARPA)的支持下開(kāi)始了對(duì)星際互聯(lián)網(wǎng)(InterplanetaryInternet,IPN)的研究。IPN的基本思想是讓深空通信(DeepSpaceCommunications)中的不同節(jié)點(diǎn)(如地面站與航天器)之間像Internet上的主機(jī)一樣進(jìn)行通信。然而行星自轉(zhuǎn)與航天器運(yùn)動(dòng)導(dǎo)致了通信鏈路的間歇性連通，使得基于端到端連通性假設(shè)的Internet協(xié)議不能直接應(yīng)用于IPN。面對(duì)深空通信中遇到的高時(shí)延與網(wǎng)絡(luò)斷開(kāi)等問(wèn)題，研究人員逐漸認(rèn)識(shí)到了IPN環(huán)境與傳統(tǒng)Internet環(huán)境的主要區(qū)別是網(wǎng)絡(luò)協(xié)議須容遲容斷(Delay/Disruption-tolerant)。隨著IPN研究的開(kāi)展，互聯(lián)網(wǎng)研究任務(wù)組(InternetResearchTaskForce,IRTF)成立了星際互聯(lián)網(wǎng)研究組(InterplanetaryInternetResearchGroup,IPNRG)，為相關(guān)的研究工作提供支持。隨后，由互聯(lián)網(wǎng)研究專家VintonCerf等人提出了最初的IPN體系結(jié)構(gòu)，用于解決深空通信中的高時(shí)延與丟包問(wèn)題。隨著IPN相關(guān)研究的不斷深入,IPNRG于2002年提出了改進(jìn)的IPN架構(gòu)，并描述了將所提出的IPN體系結(jié)構(gòu)應(yīng)用于更具一般性的容遲容斷網(wǎng)絡(luò)環(huán)境(Delay/Disruption-TolerantNetworks,DTN)的結(jié)構(gòu)設(shè)計(jì)中。隨后，容遲網(wǎng)絡(luò)研究組(Delay-TolerantNetworkingResearchGroup,DTNRG)在IPNRG的支持下成立，并致力于受限網(wǎng)絡(luò)體系結(jié)構(gòu)研究與網(wǎng)絡(luò)協(xié)議設(shè)計(jì)。與此同時(shí)，針對(duì)如何將IPN的設(shè)計(jì)思想應(yīng)用與其他受限網(wǎng)絡(luò)環(huán)境的研究也受到了研究者們?cè)絹?lái)越多的重視。2003年,KevinFall針對(duì)異構(gòu)網(wǎng)絡(luò)互聯(lián)問(wèn)題提出了基于“束”(Bundle)的DTN體系結(jié)構(gòu)［4］，。隨著針對(duì)受限網(wǎng)絡(luò)環(huán)境的應(yīng)用場(chǎng)景逐漸增多［5,6］，相關(guān)的研究工作涉及到了DTN的方方面面，包括體系結(jié)構(gòu)設(shè)計(jì)、轉(zhuǎn)發(fā)算法設(shè)計(jì)、安全問(wèn)題以及可靠性驗(yàn)證等等。1.2容遲網(wǎng)絡(luò)的特點(diǎn)相比傳統(tǒng)的基于TCP/IP協(xié)議族的互聯(lián)網(wǎng)，容遲網(wǎng)絡(luò)有以下幾個(gè)特點(diǎn)［7］：)網(wǎng)絡(luò)節(jié)點(diǎn)移動(dòng)性容遲網(wǎng)絡(luò)中各節(jié)點(diǎn)的工作方式不依賴于網(wǎng)絡(luò)基礎(chǔ)設(shè)施，并且在移動(dòng)容遲網(wǎng)絡(luò)中不存在通信范圍足以覆蓋整個(gè)網(wǎng)絡(luò)的特殊節(jié)點(diǎn)。網(wǎng)絡(luò)中各節(jié)點(diǎn)能夠按照預(yù)先指定的或者完全隨機(jī)的路徑在網(wǎng)絡(luò)中移動(dòng)，并利用移動(dòng)帶來(lái)的通信機(jī)會(huì)進(jìn)行通信。當(dāng)節(jié)點(diǎn)相遇時(shí)，即移動(dòng)進(jìn)入到彼此的通信范圍之后，消息將在有限的相遇時(shí)間內(nèi)在相遇的節(jié)點(diǎn)之間進(jìn)行轉(zhuǎn)發(fā)。通過(guò)這種方式，消息將最終逐跳地由源節(jié)點(diǎn)發(fā)送至目的節(jié)點(diǎn)。因此網(wǎng)絡(luò)節(jié)點(diǎn)的移動(dòng)性是容遲網(wǎng)絡(luò)的主要特點(diǎn)。尤其對(duì)于某些特定的網(wǎng)絡(luò)場(chǎng)景(例如利用由人攜帶的手持設(shè)備進(jìn)行分布式組網(wǎng))，人的移動(dòng)將直接影響到網(wǎng)絡(luò)節(jié)點(diǎn)間的相遇間隔時(shí)間、相遇持續(xù)時(shí)間以及相遇頻率等，并進(jìn)而影響到數(shù)據(jù)轉(zhuǎn)發(fā)算法的設(shè)計(jì)。)高時(shí)延與低帶寬容遲網(wǎng)絡(luò)的端到端時(shí)延指的是消息從源節(jié)點(diǎn)發(fā)送到目的節(jié)點(diǎn)經(jīng)過(guò)的端到端傳輸路徑上的每一跳傳輸時(shí)延的總和。其中，每一跳傳輸時(shí)延又包括消息通過(guò)該鏈路時(shí)的發(fā)送時(shí)間、傳播時(shí)間、排隊(duì)時(shí)間和處理時(shí)間。在移動(dòng)容遲網(wǎng)絡(luò)中，節(jié)點(diǎn)移動(dòng)導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的不斷變化以及網(wǎng)絡(luò)的間歇性連通，也使得消息在發(fā)送至下一跳節(jié)點(diǎn)之前需要經(jīng)過(guò)很長(zhǎng)的排隊(duì)時(shí)間，從而產(chǎn)生了較高的時(shí)延。另一方面，網(wǎng)絡(luò)節(jié)點(diǎn)的移動(dòng)性也決定了在移動(dòng)容遲網(wǎng)絡(luò)環(huán)境中適宜采用無(wú)線通信技術(shù)，而受限于無(wú)線信道的物理特性以及無(wú)線信號(hào)的干擾衰減等因素，節(jié)點(diǎn)之間的網(wǎng)絡(luò)帶寬通常比較低。網(wǎng)絡(luò)間歇性連通在容遲網(wǎng)絡(luò)中，節(jié)點(diǎn)的頻繁移動(dòng)導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不斷變化。當(dāng)節(jié)點(diǎn)移動(dòng)超出彼此的通信范圍時(shí)，節(jié)點(diǎn)間的無(wú)線通信鏈路即被中斷。網(wǎng)絡(luò)中各節(jié)點(diǎn)之間通信鏈路的中斷往往會(huì)導(dǎo)致整個(gè)網(wǎng)絡(luò)被劃分為多個(gè)互不連通的區(qū)域，從而導(dǎo)致源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間通常不存在穩(wěn)定可靠的端到端鏈路。對(duì)于因節(jié)點(diǎn)移動(dòng)而產(chǎn)生的網(wǎng)絡(luò)間歇性連通情況，有的可以提前預(yù)測(cè)(如IPN中的鏈路通斷)，而有的難以進(jìn)行預(yù)測(cè)(如PSN中設(shè)備攜帶者之間的相遇)。另外，移動(dòng)容遲網(wǎng)絡(luò)中節(jié)點(diǎn)的休眠或失效也會(huì)導(dǎo)致網(wǎng)絡(luò)的間歇性連通。網(wǎng)絡(luò)節(jié)點(diǎn)自組性容遲網(wǎng)絡(luò)是對(duì)等式網(wǎng)絡(luò)，即網(wǎng)絡(luò)中的所有節(jié)點(diǎn)地位平等，因而具有自組織的特性。一方面，移動(dòng)容遲網(wǎng)絡(luò)能夠提供不依賴于基礎(chǔ)設(shè)施的網(wǎng)絡(luò)服務(wù)，網(wǎng)絡(luò)節(jié)點(diǎn)間互相作為消息轉(zhuǎn)發(fā)的載體；另一方面，網(wǎng)絡(luò)中節(jié)點(diǎn)的加入或離開(kāi)不會(huì)影響到整個(gè)網(wǎng)絡(luò)的正常運(yùn)行，從而提高了網(wǎng)絡(luò)的生存能力；再者，網(wǎng)絡(luò)中各節(jié)點(diǎn)之間通過(guò)分布式算法進(jìn)行控制與協(xié)作，共同對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行構(gòu)建和管理。網(wǎng)絡(luò)節(jié)點(diǎn)資源有限容遲網(wǎng)絡(luò)中的各網(wǎng)絡(luò)節(jié)點(diǎn)僅具備有限的存儲(chǔ)與計(jì)算能力。同時(shí)，移動(dòng)容遲網(wǎng)絡(luò)特殊的應(yīng)用環(huán)境(如戰(zhàn)場(chǎng)環(huán)境、水下環(huán)境等)限制了網(wǎng)絡(luò)節(jié)點(diǎn)的體積和重量，從而間接地限制了網(wǎng)絡(luò)節(jié)點(diǎn)的資源。這一特點(diǎn)使得如何更加有效地利用有限的節(jié)點(diǎn)資源并且提高消息傳輸成功率，成為了移動(dòng)容遲網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)算法設(shè)計(jì)中需要考慮的一個(gè)主要方面。容遲網(wǎng)絡(luò)路由算法容遲網(wǎng)絡(luò)的路由算法通?？煞譃槲宸N不同類型，包括：基于消息復(fù)制的(Replication-based)路由算法、基于歷史信息的(History-based)路由算法、基于先驗(yàn)知識(shí)的(Knowledge-based)路由算法、基礎(chǔ)設(shè)施輔助的(Infrastructure-assisted)路由算法和基于社會(huì)網(wǎng)絡(luò)的(Social-based)路由算法?；谙?fù)制的路由算法基于消息復(fù)制的路由算法(Replication-basedforwardingalgorithm)包括傳染路由方式(EpidemicRouting)和控制洪泛方式(ControlledFlooding)o傳染路由是最簡(jiǎn)單的移動(dòng)容遲網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)算法［8］，其思想是通過(guò)源節(jié)點(diǎn)向相遇節(jié)點(diǎn)發(fā)送消息副本，再由相遇節(jié)點(diǎn)重復(fù)該過(guò)程將消息副本發(fā)送至更多節(jié)點(diǎn)，最終將該消息傳播到整個(gè)網(wǎng)絡(luò)從而送達(dá)目的節(jié)點(diǎn)。這種轉(zhuǎn)發(fā)方式的優(yōu)點(diǎn)在于能夠達(dá)到較高的消息傳輸成功率，但同時(shí)也具有明顯的缺點(diǎn)。隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量的增多，大量的消息副本將耗盡網(wǎng)絡(luò)中各節(jié)點(diǎn)的資源，因此該算法不具有可擴(kuò)展性。針對(duì)傳染路由的缺點(diǎn)，多種限制消息副本數(shù)的轉(zhuǎn)發(fā)算法被相繼提出。這類算法被稱為控制洪泛方式的轉(zhuǎn)發(fā)算法。例如在文獻(xiàn)［9］中，作者提出了四種用于限制消息副本數(shù)的機(jī)制用于降低節(jié)點(diǎn)的資源消耗(如限制消息可被轉(zhuǎn)發(fā)的最大跳數(shù))，然而該算法的缺點(diǎn)是增大了消息傳輸時(shí)延。噴射等待路由算法(Sprayandwait)算法和噴射焦點(diǎn)路由算法(Sprayandfocus)［1(都將路由算法分為兩階段且第一階段稱為噴灑(Spray):在網(wǎng)絡(luò)中產(chǎn)生固定數(shù)目數(shù)據(jù)包拷貝進(jìn)行傳播，第二階段分別為等待(Wait)和焦點(diǎn)(Focus),在等待階段攜帶數(shù)據(jù)包的節(jié)點(diǎn)對(duì)除碰到目的節(jié)點(diǎn)外不再傳播數(shù)據(jù)包，在焦點(diǎn)階段攜帶數(shù)據(jù)包的節(jié)點(diǎn)對(duì)除碰到目的節(jié)點(diǎn)或者碰到效用值比本節(jié)點(diǎn)高的節(jié)點(diǎn)外不再傳播數(shù)據(jù)包，這兩個(gè)算法可以控制網(wǎng)絡(luò)中數(shù)據(jù)包副本數(shù)量基于歷史信息的路由算法不同于基于消息復(fù)制的路由算法，基于歷史信息的數(shù)據(jù)路由算法(History-basedforwardingalgorithm)利用網(wǎng)絡(luò)中各節(jié)點(diǎn)之間的相遇歷史記錄或者節(jié)點(diǎn)間的相遇概率為下一跳節(jié)點(diǎn)的選擇提供依據(jù)。在文獻(xiàn)［11］中提出的PROPHET(ProbabilisticRoutingProtocol)算法是比較有代表性的基于歷史信息的移動(dòng)容遲網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)算法。該算法基于節(jié)點(diǎn)非隨機(jī)移動(dòng)的假設(shè)，即經(jīng)常經(jīng)過(guò)同一區(qū)域的節(jié)點(diǎn)將來(lái)再次經(jīng)過(guò)該區(qū)域的概率較高。網(wǎng)絡(luò)中各節(jié)點(diǎn)預(yù)先計(jì)算與其他節(jié)點(diǎn)相遇的概率并在節(jié)點(diǎn)相遇時(shí)對(duì)該信息進(jìn)行交換，然后利用相遇概率的傳遞性將消息轉(zhuǎn)發(fā)給具有更大概率與目標(biāo)節(jié)點(diǎn)相遇的節(jié)點(diǎn)。MV(MeetingsandVisits)算法［12,13］通過(guò)學(xué)習(xí)網(wǎng)絡(luò)中節(jié)點(diǎn)的移動(dòng)模式(MobilityPattern),即節(jié)點(diǎn)之間相遇的概率以及節(jié)點(diǎn)經(jīng)過(guò)特定區(qū)域的概率，將消息轉(zhuǎn)發(fā)給分發(fā)概率更高的節(jié)點(diǎn)。MaxProp算法［14］在MV算法的基礎(chǔ)上進(jìn)行了擴(kuò)展，利用基于節(jié)點(diǎn)間相遇歷史記錄的路徑可能性(PathLikelihood)進(jìn)行消息轉(zhuǎn)發(fā)決策。MaxProp算法還通過(guò)在網(wǎng)絡(luò)中散播ACK消息來(lái)移除網(wǎng)絡(luò)中的過(guò)期消息，從而降低了網(wǎng)絡(luò)中各節(jié)點(diǎn)的資源消耗。基于先驗(yàn)知識(shí)的路由算法基于先驗(yàn)知識(shí)的數(shù)據(jù)路由算法(Knowledge-basedforwardingalgorithm)是指在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、節(jié)點(diǎn)相遇時(shí)間或節(jié)點(diǎn)移動(dòng)軌跡等信息部分已知或者全部已知的條件下進(jìn)行轉(zhuǎn)發(fā)決策的方式。在文獻(xiàn)［15］中提出了基于先驗(yàn)知識(shí)(如鏈路統(tǒng)計(jì)信息、節(jié)點(diǎn)間連接信息、節(jié)點(diǎn)緩沖隊(duì)列占用信息、通信需求信息等)的單副本轉(zhuǎn)發(fā)算法，將路由問(wèn)題轉(zhuǎn)化為多重貨物流問(wèn)題。并且，作者通過(guò)給定不同條件的先驗(yàn)知識(shí)對(duì)轉(zhuǎn)發(fā)算法的性能進(jìn)行比較，得出了以下結(jié)論：給定的先驗(yàn)知識(shí)越多，消息的傳輸時(shí)延就越短。文獻(xiàn)［16］對(duì)容遲網(wǎng)絡(luò)中的多播(Multicast)問(wèn)題進(jìn)行了研究，得出了與之類似的結(jié)論：即使只給出部分先驗(yàn)信息，基于多播的路由算法仍然能夠達(dá)到較好的性能。但同時(shí)也指出了對(duì)于基于多播的數(shù)據(jù)轉(zhuǎn)發(fā)算法，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的先驗(yàn)信息極為重要。在文獻(xiàn)［17］中，作者將鏈路狀態(tài)路由(LinkStateRouting)用于容遲網(wǎng)絡(luò)環(huán)境中，針對(duì)偏遠(yuǎn)地區(qū)網(wǎng)絡(luò)接入的應(yīng)用場(chǎng)景提出了基于先驗(yàn)知識(shí)的路由算法,并且利用已知的往返于各村莊的車輛運(yùn)行時(shí)刻信息對(duì)消息轉(zhuǎn)發(fā)進(jìn)行決策。文獻(xiàn)［18］中提出了CAR(Context-AwareRouting)路由協(xié)議。該協(xié)議將消息的同步和異步發(fā)送機(jī)制相結(jié)合，當(dāng)與目的節(jié)點(diǎn)之間存在完整的端到端路徑時(shí)，使用原有路由協(xié)議進(jìn)行消息轉(zhuǎn)發(fā)；而當(dāng)與目的節(jié)點(diǎn)之間不存在完整的端到端路徑時(shí)，節(jié)點(diǎn)利用上下文信息(如節(jié)點(diǎn)位置、移動(dòng)模式、節(jié)點(diǎn)能量等)計(jì)算其效用值，然后采用卡爾曼濾波的方法對(duì)效用值進(jìn)行預(yù)測(cè)，并將消息轉(zhuǎn)發(fā)給效用值較高的節(jié)點(diǎn)。文獻(xiàn)［19］通過(guò)增加時(shí)間維度構(gòu)造空時(shí)(Space-Time)路由表，提出了一種在節(jié)點(diǎn)移動(dòng)模式確定的情況下的空時(shí)圖(Space-TimeGraph)路由框架。與傳統(tǒng)的基于下一跳的路由表不同，空時(shí)路由表記錄了目標(biāo)地址和消息到達(dá)時(shí)間點(diǎn)。該路由框架利用動(dòng)態(tài)規(guī)劃和類似于Dijkstra最短路徑的算法求解不同節(jié)點(diǎn)之間的最短路徑，從而最小化端到端的消息傳輸時(shí)延。基礎(chǔ)設(shè)施輔助的路由算法基礎(chǔ)設(shè)施輔助的路由算法(Infrastructure-assistedforwardingalgorithm)是指通過(guò)在容遲網(wǎng)絡(luò)中添加特殊節(jié)點(diǎn)并且控制特殊節(jié)點(diǎn)的移動(dòng)軌跡從而進(jìn)行消息轉(zhuǎn)發(fā)的方式。文獻(xiàn)［20］通過(guò)在稀疏網(wǎng)絡(luò)環(huán)境中引入移動(dòng)節(jié)點(diǎn)(MULE)來(lái)進(jìn)行數(shù)據(jù)收集，并以單跳或多跳的方式將數(shù)據(jù)轉(zhuǎn)發(fā)到接入骨干網(wǎng)的AP節(jié)點(diǎn)。與之類似，文獻(xiàn)［21］提出了MF(MessageFerry)消息擺渡路由。該方式利用主動(dòng)移動(dòng)的Ferry節(jié)點(diǎn)在稀疏網(wǎng)絡(luò)環(huán)境中進(jìn)行消息傳輸，即源節(jié)點(diǎn)先將消息發(fā)送至Ferry節(jié)點(diǎn)，然后由Ferry節(jié)點(diǎn)在移動(dòng)過(guò)程中將消息轉(zhuǎn)發(fā)至目的節(jié)點(diǎn)。文獻(xiàn)［22］針對(duì)網(wǎng)絡(luò)中的普通節(jié)點(diǎn)與Ferry節(jié)點(diǎn)之間無(wú)法協(xié)作的問(wèn)題，提出了OPWP(OptimizedWay-Points)優(yōu)化路線點(diǎn)的路由算法，通過(guò)對(duì)Ferry節(jié)點(diǎn)的移動(dòng)進(jìn)行優(yōu)化，縮短Ferry節(jié)點(diǎn)的等待時(shí)間。針對(duì)Ferry節(jié)點(diǎn)失效而導(dǎo)致系統(tǒng)癱瘓的問(wèn)題，文獻(xiàn)［23］提出了包含多個(gè)Ferry節(jié)點(diǎn)的系統(tǒng)。由于規(guī)劃Ferry節(jié)點(diǎn)的移動(dòng)軌跡在實(shí)際應(yīng)用環(huán)境中通常難以實(shí)現(xiàn)，因而這種轉(zhuǎn)發(fā)方式的應(yīng)用范圍比較有限?；谏鐣?huì)網(wǎng)絡(luò)的路由算法基于社會(huì)網(wǎng)絡(luò)的路由算法(Social-basedforwardingalgorithm)是指利用人的移動(dòng)性與社會(huì)性輔助進(jìn)行消息轉(zhuǎn)發(fā)的方式。在由手持設(shè)備組成的容遲網(wǎng)絡(luò)環(huán)境中，設(shè)備隨著人的移動(dòng)而移動(dòng)。因此人的移動(dòng)性、人與人之間相遇的間隔時(shí)間與頻率等因素直接影響到消息傳輸?shù)某晒β逝c時(shí)延。設(shè)計(jì)基于社會(huì)網(wǎng)絡(luò)的轉(zhuǎn)發(fā)算法首先需要對(duì)人與人之間的相遇規(guī)律進(jìn)行分析。文獻(xiàn)［24］通過(guò)對(duì)大量的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分析，得出了人與人之間的相遇間隔時(shí)間服從冪律分布的結(jié)論，并且指出由于相遇間隔時(shí)間的分布不存在有限的均值，已有的移動(dòng)容遲網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)算法均無(wú)法達(dá)到有限的消息傳輸時(shí)延。針對(duì)該結(jié)論，文獻(xiàn)［25］指出了人所攜帶的網(wǎng)絡(luò)節(jié)點(diǎn)之間的相遇間隔時(shí)間在一定時(shí)間閾值內(nèi)服從冪律分布，而超過(guò)該閾值則服從指數(shù)分布在基于社會(huì)網(wǎng)絡(luò)的路由算法中，節(jié)點(diǎn)間的社團(tuán)結(jié)構(gòu)(Community)】26】與中心度(Centrality)［27］是兩個(gè)非常重要的概念。一方面，社團(tuán)結(jié)構(gòu)是對(duì)設(shè)備攜帶者之間聯(lián)系緊密程度的映射，并且具有長(zhǎng)期穩(wěn)定的特點(diǎn)。由于屬于同一社團(tuán)的各節(jié)點(diǎn)之間彼此相遇(Contact)的概率較高，當(dāng)源節(jié)點(diǎn)向目的節(jié)點(diǎn)發(fā)送消息時(shí)，選擇與目的節(jié)點(diǎn)屬于同一社團(tuán)的成員節(jié)點(diǎn)進(jìn)行消息轉(zhuǎn)發(fā)有助于提高消息傳輸成功率。另一方面，節(jié)點(diǎn)中心度是對(duì)節(jié)點(diǎn)在網(wǎng)絡(luò)中活躍程度的度量，并且具有多種不同的計(jì)算方法［27］。比如，在節(jié)點(diǎn)關(guān)系圖(SocialGraph)中，對(duì)經(jīng)過(guò)各節(jié)點(diǎn)的最短路徑條數(shù)進(jìn)行計(jì)數(shù)，以此作為節(jié)點(diǎn)的介數(shù)中心度(BetweennessCentrality)。在基于社會(huì)網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)發(fā)算法中，通常選擇具有較高中心度的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)進(jìn)行消息轉(zhuǎn)發(fā)。容遲網(wǎng)絡(luò)的自組織特性決定了網(wǎng)絡(luò)中各節(jié)點(diǎn)只能獲得局部的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)或部分節(jié)點(diǎn)之間的關(guān)系，因此只能通過(guò)分布式算法進(jìn)行社團(tuán)檢測(cè)。文獻(xiàn)［28］中提出了三個(gè)分布式社團(tuán)檢測(cè)算法(SIMPLE算法,k-CLIQUE算法和MODULARITY算法)。這三個(gè)算法均需要預(yù)先指定節(jié)點(diǎn)間的累計(jì)相遇持續(xù)時(shí)間的閾值，將累計(jì)相遇持續(xù)時(shí)間大于該閾值的節(jié)點(diǎn)加入到各節(jié)點(diǎn)的朋友集合(FamiliarSet)中，然后通過(guò)在節(jié)點(diǎn)相遇時(shí)比較各自朋友集合的相似性等方法進(jìn)行社團(tuán)檢測(cè)。由于需要預(yù)先指定累積相遇持續(xù)時(shí)間的閾值并且該閾值隨應(yīng)用場(chǎng)景的不同而變化，因此文獻(xiàn)［28］中提出的三個(gè)分布式社團(tuán)檢測(cè)算法具有一定的局限性。文獻(xiàn)［29］中提出的SHARC算法采用另一種方式進(jìn)行分布式社團(tuán)檢測(cè)。網(wǎng)絡(luò)中的各節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播自己的社團(tuán)標(biāo)簽，并通過(guò)計(jì)算與鄰居節(jié)點(diǎn)社團(tuán)標(biāo)簽的相似性來(lái)進(jìn)行社團(tuán)檢測(cè)。該算法的優(yōu)點(diǎn)是可被用于動(dòng)態(tài)社團(tuán)檢測(cè)。然后由于廣播標(biāo)簽引入了較大的通信代價(jià)，使得該算法不適用于對(duì)節(jié)點(diǎn)能耗要求較高的應(yīng)用場(chǎng)景之中。目前，已經(jīng)有多種不同類型的基于社會(huì)網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)發(fā)算法被提出?？紤]到屬于同一社團(tuán)的成員節(jié)點(diǎn)之間相遇的概率較大，選擇目的節(jié)點(diǎn)的社團(tuán)成員節(jié)點(diǎn)進(jìn)行消息轉(zhuǎn)發(fā)很自然地成為了最基本的基于社會(huì)網(wǎng)絡(luò)的轉(zhuǎn)發(fā)方式，如文獻(xiàn)［30］中提出的Label算法。該算法中，消息被轉(zhuǎn)發(fā)至與目的節(jié)點(diǎn)具有相同社團(tuán)標(biāo)簽(Label)的中繼節(jié)點(diǎn)。文獻(xiàn)［31］中提出的SimBet算法利用了介數(shù)中心度(BetweennessCentrality)和相似度(Similarity)來(lái)估計(jì)各節(jié)點(diǎn)向特定節(jié)點(diǎn)轉(zhuǎn)發(fā)消息的效用值。在該算法中，介數(shù)中心度指的是經(jīng)過(guò)各節(jié)點(diǎn)的最短路徑條數(shù)，而相似度指的是節(jié)點(diǎn)之間共同的鄰居節(jié)點(diǎn)的比例。文獻(xiàn) ［32］中提出了SPM(SocialPressuresMetric)度量方法和基于朋友關(guān)系的路由算法(FriendshipBasedRouting)。該算法將消息轉(zhuǎn)發(fā)給目的節(jié)點(diǎn)屬于同一社團(tuán)(FriendshipCommunity)的節(jié)點(diǎn)或者與目的節(jié)點(diǎn)有著更強(qiáng)的朋友關(guān)系的節(jié)點(diǎn)。與之類似，文獻(xiàn)［32］中利用節(jié)點(diǎn)相遇記錄計(jì)算節(jié)點(diǎn)相似度，提出了基于社團(tuán)的傳染轉(zhuǎn)發(fā)算法(Community-basedEpidemicForwardingAlgorithm)。文獻(xiàn)［33］提出了基于全局中心度(GlobalCentrality)與本地中心度(LocalCentrality)的Bubblerap轉(zhuǎn)發(fā)算法。全局中心度較高意味著與目的節(jié)點(diǎn)的社團(tuán)成員節(jié)點(diǎn)的相遇概率較高，而本地中心度較高則意味著與目的節(jié)點(diǎn)的相遇概率較高。在Bubblerap算法中，消息在送達(dá)目的節(jié)點(diǎn)的社團(tuán)成員節(jié)點(diǎn)之前將沿著全局中心度增大的方向轉(zhuǎn)發(fā)。而當(dāng)消息被轉(zhuǎn)發(fā)至目的節(jié)點(diǎn)的社團(tuán)成員節(jié)點(diǎn)之后，將沿著本地中心度增大的方向轉(zhuǎn)發(fā)，從而最終被發(fā)送至目的節(jié)點(diǎn)。此外，文獻(xiàn)［34］提出了針對(duì)發(fā)布/訂閱(Publish/Subscribe)模式的SocialCast路由算法，該算法將消息轉(zhuǎn)發(fā)過(guò)程分為興趣分發(fā)、中繼選擇和消息發(fā)布3個(gè)階段。在興趣分發(fā)階段，各節(jié)點(diǎn)向一跳以內(nèi)的鄰居節(jié)點(diǎn)廣播其興趣；在中繼選擇階段，節(jié)點(diǎn)通過(guò)卡爾曼濾波的方法計(jì)算對(duì)轉(zhuǎn)發(fā)特定興趣消息的效用值，并選擇具有最大效用值的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)；在消息分發(fā)階段，節(jié)點(diǎn)將消息轉(zhuǎn)發(fā)到對(duì)該消息感興趣節(jié)點(diǎn)或者最佳的中繼節(jié)點(diǎn)。容遲網(wǎng)絡(luò)的應(yīng)用場(chǎng)景目前，容遲網(wǎng)絡(luò)的應(yīng)用場(chǎng)景不斷增多，如戰(zhàn)場(chǎng)通信(MilitaryCommunications)手持設(shè)備網(wǎng)絡(luò)(PocketSwitchedNetworks)、野生動(dòng)物追蹤(WildlifeTracking)、偏遠(yuǎn)地區(qū)網(wǎng)絡(luò)接入(OpportunisticNetworkinginDevelopingAreas)、車載網(wǎng)絡(luò)(VehicularNetworks)以及水下傳感器網(wǎng)絡(luò)(UnderwaterSensorNetworks)等。戰(zhàn)場(chǎng)通信在戰(zhàn)場(chǎng)環(huán)境中，傳統(tǒng)的集中式通信網(wǎng)絡(luò)架構(gòu)由于網(wǎng)絡(luò)基礎(chǔ)設(shè)施容易受到干擾和破壞因而生存能力較差。通信網(wǎng)絡(luò)的生存能力對(duì)于戰(zhàn)場(chǎng)指揮、協(xié)同作戰(zhàn)等極為重要，因此采用分布式組網(wǎng)方式動(dòng)態(tài)地組建戰(zhàn)場(chǎng)通信網(wǎng)絡(luò)則較為適宜。目前，作戰(zhàn)人員和車輛通常配備有無(wú)線通信設(shè)備，這些設(shè)備為分布式組網(wǎng)提供了硬件基礎(chǔ)。另外在戰(zhàn)場(chǎng)環(huán)境中，作戰(zhàn)人員和車輛的移動(dòng)會(huì)造成網(wǎng)絡(luò)拓?fù)涞念l繁變化，并且復(fù)雜的地形和障礙物等因素也會(huì)造成通信鏈路的中斷和網(wǎng)絡(luò)的間歇性連通，因而戰(zhàn)場(chǎng)通信網(wǎng)絡(luò)具備了移動(dòng)容遲網(wǎng)絡(luò)的主要特點(diǎn)。2）手持設(shè)備網(wǎng)絡(luò)隨著智能手機(jī)、平板電腦等手持設(shè)備的大量普及，利用這些設(shè)備進(jìn)行分布式組網(wǎng)并提供不依賴于網(wǎng)絡(luò)基礎(chǔ)設(shè)施的網(wǎng)絡(luò)服務(wù)具有廣闊的應(yīng)用前景。英國(guó)劍橋大學(xué)與英特爾研究院提出了手持設(shè)備網(wǎng)絡(luò)（PocketSwitchedNetworks,PSN）［79］的概念。在PSN中，網(wǎng)絡(luò)節(jié)點(diǎn)即人隨身攜帶的手持設(shè)備。這些設(shè)備隨著人的移動(dòng)而移動(dòng)，并且利用節(jié)點(diǎn)相遇帶來(lái)的通信機(jī)會(huì)進(jìn)行通信。3） 野生動(dòng)物追蹤由于野生動(dòng)物特殊的生活環(huán)境與習(xí)性，人類難以近距離進(jìn)行觀察與研究。因此，人們采用在動(dòng)物身上安裝傳感器的方法對(duì)其進(jìn)行追蹤，并且利用傳感器采集到的數(shù)據(jù)對(duì)動(dòng)物的習(xí)性進(jìn)行分析。由普林斯頓大學(xué)設(shè)計(jì)的ZebraNet［35是專門用于追蹤非洲野生斑馬的容遲網(wǎng)絡(luò)應(yīng)用系統(tǒng)。該系統(tǒng)由安裝于斑馬頸部的無(wú)線傳感器節(jié)點(diǎn)和移動(dòng)基站組成。無(wú)線傳感器節(jié)點(diǎn)負(fù)責(zé)收集斑馬的移動(dòng)數(shù)據(jù)，并在斑馬相遇時(shí)進(jìn)行數(shù)據(jù)交換。移動(dòng)基站則由研究人員攜帶，并在定期穿越追蹤區(qū)域時(shí)對(duì)各無(wú)線傳感器節(jié)點(diǎn)上存儲(chǔ)的數(shù)據(jù)進(jìn)行收集。4） 偏遠(yuǎn)地區(qū)網(wǎng)絡(luò)接入現(xiàn)階段，發(fā)展中國(guó)家或偏遠(yuǎn)地區(qū)由于網(wǎng)絡(luò)基礎(chǔ)設(shè)施部署不足而無(wú)法接入到互聯(lián)網(wǎng)。如何為這些國(guó)家或地區(qū)提供價(jià)格低廉的互聯(lián)網(wǎng)接入方案，成為了容遲網(wǎng)絡(luò)研究的一個(gè)實(shí)際問(wèn)題。5） 車載網(wǎng)絡(luò)目前，具有Wi-Fi或藍(lán)牙等短距無(wú)線通信能力的車輛正在逐漸增多，針對(duì)車輛間無(wú)線組網(wǎng)的研究工作也隨之展開(kāi)。車輛在道路上行駛的速度存在差異，并且不同道路上車輛的密度也存在差異，導(dǎo)致該網(wǎng)絡(luò)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不斷變化、網(wǎng)絡(luò)間歇性連通。并且，消息在不同車輛間傳輸將會(huì)累積較大的時(shí)延，從而形成了一個(gè)典型的移動(dòng)容遲網(wǎng)絡(luò)環(huán)境。6） 水下傳感器網(wǎng)絡(luò)海洋環(huán)境監(jiān)測(cè)通過(guò)在海洋中部署一定數(shù)量的傳感器節(jié)點(diǎn)進(jìn)行觀測(cè)數(shù)據(jù)的采集并且根據(jù)實(shí)際需求采用不同的傳輸手段將數(shù)據(jù)傳回岸上基站進(jìn)行存儲(chǔ)與處理。隨著人們對(duì)海洋資源需求的逐漸增多，利用水下傳感器網(wǎng)絡(luò)組建立體海洋觀測(cè)網(wǎng)絡(luò)的研究已逐漸展開(kāi)。參考文獻(xiàn)SpypopoulousT,RaisRN,TurlettiT,etal.Routingfordisruptiontolerantnetworks:taxonomyanddesign[J].WirelessNetworks,2010,16(8):2349-2370.王欣.容遲網(wǎng)絡(luò)中基于復(fù)制策略的單播路由算法研究 [J].電子設(shè)計(jì)工程，2013,21(6):24-26.⑶楊振國(guó)，資源受限的延遲容忍網(wǎng)絡(luò)路由調(diào)度問(wèn)題研究[D].[S.I.]:中國(guó)科學(xué)技術(shù)大學(xué),2012.2006FallK.ADelay-TolerantNetworkArchitectureforChallengedInternets[C].Proceedingsofthe2003ACMSIGCOMM,pp.27-34.JuangP, Oki H,WangY,MartonosiM,PehL.SandRubenstein D.I. Energy-efficientcomputing for wildlifetracking:DesigntradeoffsandearlyexperienceswithZebraNet[C].Proceedingsofthe10thinternationalconferenceonArchitecturalsupportforprogramminglanguagesandoperatingsystems,96-107,2002.PentlandA,FletcherR,andHassonA.DakNet:RethinkingConnectivityinDevelopingNations[J].IEEEComputer,37(1),pp.78-83,2004.FallK,FarrellS.DTN:AnArchitecturalRetrospective[J].IEEEJournalonSelectedAreasinCommunications,2008,26(5):828—836.VahdatAandBeckerD.Epidemicroutingforpartiallyconnectedadhocnetworks.TechnicalReportCS-200006,DukeUniversity,2000.HarrasK.A,AlmerothK.CandBelding-royerE.M.DelayTolerantMobileNetworks(DTMNs):ControlledFloodingSchemesinSparseMobileNetworks[C].Proceedingsofthe4thInternationalIFIP-TC6NetworkingConference,pp.1180-1192,2005.SpyropoulosT,PsounisK,RaghavendraC.S.SprayandWait:AnEfficientRoutingSchemeforIntermittentlyConnectedMobileNetworks[C].Proceedingsofthe2005ACMSIGCOMMworkshoponDelay-tolerantNetworking(WDTN'05),pp.252-259,2005.LindgrenA,DoriaAandSchelnO.ProbabilisticRoutinginIntermittentlyConnectedNetworks[C].ProceedingsoftheSIGMOBILEMobileComputingandCommunicationReview,7(3):19-20,2004.BurnsB,BrockOandLevineBN.MVroutingandcapacitybuildingindisruptiontolerantnetworks[C].Proceedingsofthe2005INFOCOM,pp.398-408,2005.BurnsB,BrockOandLevineBN.Autonomousenhancementofdisruptiontolerantnetworks[C].Proceedingsofthe2006IEEEInternationalConferenceonRoboticsandAutomation,pp.2105-2110,2006.BurgessJ,GallagherB,JensenDandLevineB.N.MaxProp:RoutingforVehicle-BasedDisruption-TolerantNetworks[C].Proceedingsofthe25thIEEEInternationalConferenceonComputerCommunications,pp.1-11,2006.JainS,FallK,PatraR.RoutinginaDelayTolerantNetwork[C].ProceedingsoftheSIGCOMM'04,pp.145-158,2004.ZhaoW,AmmarM,ZeguraE.Multicastingindelaytolerantnetworks:Semanticmodelsandroutingalgorithms[C].Proceedingsofthe2005ACMSIGCOMMworkshoponDelay-tolerantnetworking(WDTN'05),pp.268-275,2005.

[17]DemmerDeveloping

Networked[18]MusolesifordelayDandFallK.DTLSR:DelayTolerantRoutingforRegions[C].Proceedingsofthe[17]DemmerDeveloping

Networked[18]MusolesifordelayM,MascoloC.CAR:Context-Awareadaptiveroutingtolerantmobilenetworks[J].IEEETransactiononMobileComputing,2009,8(2):246-260.MeruguS,AmmarM,ZeguraE.Routinginspaceandtimeinnetworkswithpredictablemobility.TechnicalReport,GIT-CC-04-07,GeorgiaTechCollegeofComputing,2004.ShahRC,RoyS,JainS,BrunetteW.DataMULEs:Modelingandanalysisofathree-tierarchitectureforsparsesensornetworks[C].ProceedingsoftheIEEESNPAworkshop,pp.30-41,2003.ZhaoW,AmmarM,ZeguraE.Amessageferryingapproachfordatadeliveryinsparsemobileadhocnetworks[C].Proceedingsofthe2004ACMMobihoc,pp.187-198,2004.ZhaoW,AmmarM,ZeguraE.Controllingthemobilityofmultipledatatransportferriesinadelay-tolerantnetwork[C].Proceedingsofthe2005INFOCOM,pp.1407-1418,2005.ChaintreauA,HuiP,CrowcroftJ,DiotC,GassRandScottJ.ImpactofHumanMobilityonOpportunisticForwardingAlgorithms[J].IEEETransactionsonMobileComputing,vol.6,no.6,pp.606-620,2007.KaragiannisT,BoudecJ-Y.L,andVojnoviM.Powerlawandexponentialdecayofintercontacttimesbetweenmobiledevices[C].Proceedingsofthe13thannualACMinternationalconferenceonMobilecomputingandnetworking,pp.183-194,2007.NewmanM.E.J.Modularityandcommunitystructureinnetworks[J].NationalAcademyofSciences,vol.103,no.23,pp.8577,2006.FreemanL.C.Asetofmeasuringcentralitybasedonbetweenness[J].Sociometry,vol.40,pp.35-41,1977.HuiP, Yoneki E, ChanSandCrowcroftJ.Distributedcommunitydetection indelaytolerantnetworks[C].Proceedingsofthe2ndACM/IEEEinternationalworkshoponMobilityintheevolvinginternetarchitecture(MobiArch'07),pp:1-8,2007.HerbietG.-HandBouvryP.SHARC: Community-basedpartitioningformobileadhocnetworksusingneighborhoodsimilarity[C].Proceedingsofthe2010IEEEInternationalSymposiumonWo