機(jī)會網(wǎng)絡(luò)研究進(jìn)展

王慧強(qiáng)，張淯舒，呂宏武，朱金美

(哈爾濱工程大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱150001)

0 引言

隨著無線通信技術(shù)的飛速發(fā)展與移動智能設(shè)備的廣泛普及，人們迫切希望能夠隨時隨地從互聯(lián)網(wǎng)獲取信息與服務(wù)。移動互聯(lián)網(wǎng)應(yīng)運(yùn)而生，并迅速成為網(wǎng)絡(luò)通信領(lǐng)域的熱門研究方向。然而，受到網(wǎng)絡(luò)基礎(chǔ)設(shè)施與使用環(huán)境等因素限制，采用傳統(tǒng)的無線接入方式往往不能滿足用戶的使用需求。機(jī)會網(wǎng)絡(luò)［1］的出現(xiàn)為無線網(wǎng)絡(luò)提供了一種全新的接入模式，使得在缺少網(wǎng)絡(luò)基礎(chǔ)設(shè)施的環(huán)境中接入互聯(lián)網(wǎng)成為可能，極大地拓展了移動互聯(lián)網(wǎng)的覆蓋范圍，為新型移動應(yīng)用的出現(xiàn)提供了條件。

機(jī)會網(wǎng)絡(luò)是一種面向缺乏持續(xù)端到端連接的網(wǎng)絡(luò)環(huán)境，利用節(jié)點(diǎn)移動帶來的相遇機(jī)會完成信息傳遞的無線自組織網(wǎng)絡(luò)，其部分概念源自延遲容忍網(wǎng)絡(luò)(Delay Tolerant Network，DTN)［2］的研究。DTN 最初的研究可追溯到上個世紀(jì)，為應(yīng)對深空探測的需求，NASA 于1998年開始了針對具有長延遲、多終端以及周期性連接等特征的深空網(wǎng)絡(luò)的研究，其目的是使地面與深空探測器間的數(shù)據(jù)通信能夠像地面節(jié)點(diǎn)之間通信一樣方便。該研究項(xiàng)目逐漸發(fā)展成為Internet 的IPNSIG 與IETF 的DTNRG 兩個工作組。其中，IPNSIG的研究主要針對深空網(wǎng)絡(luò)展開;而DTNRG 由于沒有可以進(jìn)行試驗(yàn)的星際網(wǎng)絡(luò)，將研究的重點(diǎn)轉(zhuǎn)向如何將DTN 的概念運(yùn)用到地面網(wǎng)絡(luò)中。另外，DARPA 于2004年提出了中斷容忍網(wǎng)絡(luò)(Disruption Tolerant Network)的概念，也簡稱為DTN，一般認(rèn)為兩者為同一概念的不同表述。

本文立足于機(jī)會社會網(wǎng)絡(luò)技術(shù)，在充分總結(jié)現(xiàn)有研究成果的基礎(chǔ)上，首先對機(jī)會網(wǎng)絡(luò)的概念、模型等內(nèi)容作簡單介紹，然后總結(jié)該領(lǐng)域中的熱點(diǎn)研究問題，最后對其發(fā)展方向進(jìn)行了展望。

1 機(jī)會網(wǎng)絡(luò)

與傳統(tǒng)的面向連接的無線網(wǎng)絡(luò)不同，機(jī)會網(wǎng)絡(luò)是一種針對間歇性連接、延遲大、錯誤率高等無線通信特征設(shè)計的新型無線網(wǎng)絡(luò)，能在缺乏端到端連接的網(wǎng)絡(luò)環(huán)境中完成信息傳遞［3］。機(jī)會網(wǎng)絡(luò)采用“存儲—攜帶—轉(zhuǎn)發(fā)”模式的路由協(xié)議，消息在傳遞過程中需要經(jīng)過各中間節(jié)點(diǎn)的存儲與攜帶，并等待合適的下一跳節(jié)點(diǎn)出現(xiàn)。機(jī)會網(wǎng)絡(luò)中消息的傳遞過程如圖1所示。節(jié)點(diǎn)S 中產(chǎn)生了一個目的節(jié)點(diǎn)為D 的消息M，在t1 時刻，節(jié)點(diǎn)S 僅能夠與節(jié)點(diǎn)1、2 建立無線連接，并選擇把消息M 傳遞給節(jié)點(diǎn)1。在t2 時刻，經(jīng)過一段時間的移動，節(jié)點(diǎn)1 攜帶消息M 與節(jié)點(diǎn)3 相遇，并將消息M 傳遞給節(jié)點(diǎn)3。最后，在t3 時刻，攜帶消息M 的節(jié)點(diǎn)3 與目的節(jié)點(diǎn)D 相遇，將消息M 傳遞給節(jié)點(diǎn)D，完成了消息M 的整個傳遞過程。從圖1中可以看出，在消息M 的傳遞過程中，始終不存在一條連接源節(jié)點(diǎn)S 與目的節(jié)點(diǎn)D 的無線鏈路，因此傳統(tǒng)的基于連接的無線網(wǎng)絡(luò)不能有效地完成消息的傳遞，而機(jī)會網(wǎng)絡(luò)利用節(jié)點(diǎn)移動創(chuàng)造的相遇機(jī)會為消息建立了有效的傳遞路徑。

圖1 機(jī)會網(wǎng)絡(luò)消息傳遞

機(jī)會網(wǎng)絡(luò)的實(shí)質(zhì)是一種通用的面向消息的覆蓋層網(wǎng)絡(luò)體系結(jié)構(gòu)，在端到端應(yīng)用與底層網(wǎng)絡(luò)協(xié)議之間設(shè)置機(jī)會網(wǎng)絡(luò)組件，為無線網(wǎng)絡(luò)提供針對異構(gòu)、大延遲以及間歇式連接網(wǎng)絡(luò)環(huán)境的通信能力。其體系結(jié)構(gòu)如圖2所示。其中，機(jī)會網(wǎng)絡(luò)相關(guān)組件為網(wǎng)絡(luò)提供虛擬消息交換、命名與尋址、路由與轉(zhuǎn)發(fā)、安全保障與QoS 等機(jī)制［4］。

圖2 機(jī)會網(wǎng)絡(luò)體系結(jié)構(gòu)

2 節(jié)點(diǎn)移動模型

節(jié)點(diǎn)移動模型通過相應(yīng)的算法與規(guī)則描述節(jié)點(diǎn)位置、速度與移動方向等運(yùn)動信息。節(jié)點(diǎn)的移動性通常來說是對無線網(wǎng)絡(luò)的挑戰(zhàn)，但對于機(jī)會網(wǎng)絡(luò)則是一種機(jī)遇。傳統(tǒng)的無線網(wǎng)絡(luò)協(xié)議普遍采用屏蔽底層節(jié)點(diǎn)運(yùn)動的設(shè)計模式，而機(jī)會網(wǎng)絡(luò)的特點(diǎn)使得對節(jié)點(diǎn)移動的研究成為其協(xié)議設(shè)計的一部分。節(jié)點(diǎn)移動模型主要包括隨機(jī)移動模型、基于人類行為的移動模型與基于統(tǒng)計的真實(shí)移動模型三種［5］。

隨機(jī)移動模型是一種獨(dú)立同分布的理論移動模型，其中隨機(jī)路點(diǎn)移動模型(Random Way Point，RWP)［6］、隨機(jī)游走移動模型(Random Walk，RW)和隨機(jī)方向移動模型(Random Direction，RD)［7］是三種比較經(jīng)典的模型。在RWP 模型中，節(jié)點(diǎn)隨機(jī)選擇一個目的點(diǎn)，并以恒定的速度向該點(diǎn)運(yùn)動，到達(dá)后停止一段時間再選擇下一個目的點(diǎn)。在RW 模型中，節(jié)點(diǎn)通過隨機(jī)選擇運(yùn)動方向與速度決定移動路徑。在RD 模型中，節(jié)點(diǎn)隨機(jī)選取移動方向并以恒定速度運(yùn)動，當(dāng)節(jié)點(diǎn)到達(dá)仿真區(qū)域邊緣時停止一段時間，再重新選擇移動方向。

基于人類行為的移動模型能夠更好的模擬實(shí)際環(huán)境中節(jié)點(diǎn)的移動模式，主要包括基于地圖的移動模型(Map－Based Mobility，MBM)、工作日移動模型(Working Day Movement Model，WDM)［8］與基于社區(qū)的移動模型(Community Based Model，CBM)［9－11］。其中，MBM 模型將節(jié)點(diǎn)的移動軌跡限制在地圖中定義的道路上，同時提供隨機(jī)、最短路徑與規(guī)定路徑三種移動模式;WDM 是針對工作日設(shè)計的移動模型，能夠模仿生活中三種常見的場景，在家休息、在辦公室工作和與朋友外出;CBM 模型則考慮節(jié)點(diǎn)喜好與行為時變性，主要用于模擬攜帶移動節(jié)點(diǎn)的人類具有的社會特性。

基于統(tǒng)計的真實(shí)移動模型收集實(shí)際環(huán)境中的節(jié)點(diǎn)運(yùn)動軌跡。MIT 的Reality Mining 項(xiàng)目［12］在9 個月的時間里記錄了106 個智能藍(lán)牙設(shè)備的移動軌跡與相遇數(shù)據(jù);UCSD 的Wireless Topology Discovery 項(xiàng)目［13］在11 周的時間里記錄了300 個無線設(shè)備與Wi－Fi 接入點(diǎn)的相遇數(shù)據(jù);劍橋大學(xué)的Haggle 項(xiàng)目［14］記錄了校園中多個藍(lán)牙設(shè)備的相遇情況?；诮y(tǒng)計的真實(shí)移動模型能夠完美的描述人類的活動規(guī)律，然而數(shù)據(jù)的搜集往往需要耗費(fèi)大量的人力物力與時間。

3 消息轉(zhuǎn)發(fā)機(jī)制

機(jī)會網(wǎng)絡(luò)中節(jié)點(diǎn)運(yùn)動導(dǎo)致網(wǎng)絡(luò)拓?fù)洳粩嘧兓?，往往不存在完整的鏈路可供選擇，因此其路由決策可以簡化為消息轉(zhuǎn)發(fā)過程中下一跳節(jié)點(diǎn)的選擇與消息副本分配的問題。機(jī)會網(wǎng)絡(luò)的消息轉(zhuǎn)發(fā)機(jī)制可以多個角度進(jìn)行分類。從消息向網(wǎng)絡(luò)中注入的副本數(shù)量的角度可以將消息轉(zhuǎn)發(fā)機(jī)制分為基于轉(zhuǎn)發(fā)策略的轉(zhuǎn)發(fā)機(jī)制與基于復(fù)制策略的轉(zhuǎn)發(fā)機(jī)制。其中，采用基于轉(zhuǎn)發(fā)策略轉(zhuǎn)發(fā)機(jī)制的機(jī)會網(wǎng)絡(luò)中，每個消息存在一個副本，而采用基于復(fù)制策略轉(zhuǎn)發(fā)機(jī)制的機(jī)會網(wǎng)絡(luò)中，每個消息存在多個副本。從是否需要基礎(chǔ)設(shè)施的角度可以將消息轉(zhuǎn)發(fā)機(jī)制分為不依賴基礎(chǔ)設(shè)施的轉(zhuǎn)發(fā)機(jī)制與依賴基礎(chǔ)設(shè)施的轉(zhuǎn)發(fā)機(jī)制。其中，不依賴基礎(chǔ)設(shè)施的轉(zhuǎn)發(fā)機(jī)制包括基于傳播的轉(zhuǎn)發(fā)機(jī)制與基于上下文的轉(zhuǎn)發(fā)機(jī)制，而依賴基礎(chǔ)設(shè)施的轉(zhuǎn)發(fā)機(jī)制包括依賴固定基礎(chǔ)設(shè)施的轉(zhuǎn)發(fā)機(jī)制與依賴移動基礎(chǔ)設(shè)施的轉(zhuǎn)發(fā)機(jī)制。另外還可以按照轉(zhuǎn)發(fā)策略將消息轉(zhuǎn)發(fā)機(jī)制分為基于機(jī)會的轉(zhuǎn)發(fā)制作、基于預(yù)測的轉(zhuǎn)發(fā)機(jī)制與基于計劃的轉(zhuǎn)發(fā)機(jī)制［15］。其中，基于機(jī)會的轉(zhuǎn)發(fā)機(jī)制是最常見的形式，不判斷中間節(jié)點(diǎn)是否是最佳選擇，基于預(yù)測的轉(zhuǎn)發(fā)機(jī)制通過對歷史信息的分析來預(yù)測最佳的轉(zhuǎn)發(fā)節(jié)點(diǎn)，而基于計劃的轉(zhuǎn)發(fā)機(jī)制通過可自主移動的擺渡節(jié)點(diǎn)完成消息的轉(zhuǎn)發(fā)。

下面對幾種典型的路由算法做簡要介紹:

Fist Contact［16］與Direct Delivery 算法都是基于轉(zhuǎn)發(fā)的策略的路由算法，在消息的傳遞過程中，網(wǎng)絡(luò)中只包含一個有效的消息副本。兩種算法的區(qū)別是:First Contact 算法將消息傳遞給遇到的第一個節(jié)點(diǎn)，而Direct Delivery 算法僅在與目的節(jié)點(diǎn)相遇時才將消息轉(zhuǎn)發(fā)出去。

Epidemic［17］算法是一種基于復(fù)制的路由算法，其本質(zhì)是一種洪泛算法，每個節(jié)點(diǎn)都將消息轉(zhuǎn)發(fā)給所遇到的所有節(jié)點(diǎn)。在緩存容量不受限制的情況下，該算法能夠最大限度的提高消息投遞率、降低網(wǎng)絡(luò)時延。其缺點(diǎn)是對網(wǎng)絡(luò)資源的需求過大。

Spray and Wait［18］算法也是一種基于洪泛策略的算法，節(jié)點(diǎn)在相遇時向?qū)Ψ綇?fù)制消息，與Epidemic 不同的是Spray and Wait 通過限定消息副本數(shù)量的方式避免洪泛現(xiàn)象的產(chǎn)生。Spray and Wait 算法分為Spray 與Wait 兩個階段。在Spray 階段，源節(jié)點(diǎn)向網(wǎng)絡(luò)中注入固定數(shù)目的消息副本，然后進(jìn)入Wait 階段，若消息副本在上一階段沒有被送達(dá)目標(biāo)節(jié)點(diǎn)，則攜帶消息的節(jié)點(diǎn)通過Direct Delivery 方式完成消息的傳遞。

PRoPHET［19］算法是一種基于預(yù)測的路由算法，該算法定義了一種預(yù)測節(jié)點(diǎn)間成功傳輸概率的方法。節(jié)點(diǎn)在相遇時更新傳輸預(yù)測值，并以此為依據(jù)決定是否轉(zhuǎn)發(fā)數(shù)據(jù)分組。

MaxProp［20］算法是一種基于調(diào)度策略的路由算法，其核心機(jī)制是節(jié)點(diǎn)維護(hù)的消息隊(duì)列，該隊(duì)列按照消息優(yōu)先級排序，并將其作為消息傳輸與丟棄的依據(jù)。其中，消息的優(yōu)先級主要由鏈路的歷史數(shù)據(jù)確定。

4 擁塞控制

與傳統(tǒng)IP 網(wǎng)絡(luò)不同，機(jī)會網(wǎng)絡(luò)適用的環(huán)境一般具有延遲長、抖動嚴(yán)重、間歇性連接、數(shù)據(jù)流非對稱以及資源受限等特征，傳統(tǒng)的擁塞控制機(jī)制不能達(dá)到理想的效果。同時，“存儲—攜帶—轉(zhuǎn)發(fā)”的路由模式也給機(jī)會網(wǎng)絡(luò)的擁塞控制帶來了新的挑戰(zhàn)。根據(jù)引起擁塞的資源不同，可以將機(jī)會網(wǎng)絡(luò)中出現(xiàn)的擁塞現(xiàn)象分為三種類型:節(jié)點(diǎn)級擁塞、鏈路級擁塞與區(qū)域級擁塞。

節(jié)點(diǎn)級擁塞是由于節(jié)點(diǎn)計算、通信或存儲等能力不足引起的，通常情況下表現(xiàn)為節(jié)點(diǎn)在與其他節(jié)點(diǎn)相遇的有限時間內(nèi)不能完成消息的處理、傳輸，或節(jié)點(diǎn)接收的消息超出其緩存容量而被迫丟棄部分消息。產(chǎn)生節(jié)點(diǎn)級擁塞的原因是節(jié)點(diǎn)能力不足，在不增加節(jié)點(diǎn)能力的條件下，可以通過設(shè)計合理的緩存管理策略，選擇成功投遞幾率較大的消息優(yōu)先處理，以達(dá)到整體上提升投遞率的目的。

鏈路級擁塞是由無線信道資源不足引起的，通常情況下表現(xiàn)為多個節(jié)點(diǎn)持續(xù)競爭使用無線信道，產(chǎn)生訪問沖突現(xiàn)象，極大的降低了鏈路的利用率，從而影響網(wǎng)絡(luò)吞吐量。產(chǎn)生鏈路級擁塞的原因是節(jié)點(diǎn)缺乏高效信道感知與動態(tài)頻譜接入的能力，可通過引入認(rèn)知無線電的相關(guān)研究內(nèi)容，為機(jī)會網(wǎng)絡(luò)提供智能的頻譜感知、分配與接入能力。

區(qū)域級擁塞是由網(wǎng)絡(luò)吞吐量不足引起的，通常表現(xiàn)為一個地理區(qū)域的流量過載。在不提高網(wǎng)絡(luò)容量條件下，為網(wǎng)絡(luò)提供有效的負(fù)載均衡策略，能夠在一定層度上緩解區(qū)域級擁塞的程度。

5 機(jī)會網(wǎng)絡(luò)面臨的挑戰(zhàn)

目前，盡管學(xué)術(shù)界對機(jī)會網(wǎng)絡(luò)的研究取得了一定的成果，但隨著機(jī)會網(wǎng)絡(luò)應(yīng)用環(huán)境的不斷擴(kuò)展，其自身發(fā)展與需求也呈現(xiàn)出了多樣化的趨勢。因此，未來機(jī)會網(wǎng)絡(luò)的研究將面臨高效、通用、安全與節(jié)能等方面的挑戰(zhàn):

(1)設(shè)計高效的機(jī)會網(wǎng)絡(luò)路由算法一直是機(jī)會網(wǎng)絡(luò)研究的熱點(diǎn)問題。如何利用社會網(wǎng)絡(luò)分析理論提高機(jī)會網(wǎng)絡(luò)路由效率將成為機(jī)會網(wǎng)絡(luò)路由設(shè)計的重要方向。

(2)機(jī)會網(wǎng)絡(luò)是一種典型的覆蓋網(wǎng)絡(luò)，設(shè)計通用的機(jī)會通信中間件能夠擴(kuò)展機(jī)會網(wǎng)絡(luò)的使用范圍與應(yīng)用場景。

(3)與傳統(tǒng)無線網(wǎng)絡(luò)一樣，機(jī)會網(wǎng)絡(luò)也面臨著各種安全威脅，而機(jī)會網(wǎng)絡(luò)的特殊性又使得常規(guī)的安全機(jī)制不能達(dá)到理想的防范效果。因此，適用于機(jī)會網(wǎng)絡(luò)的安全保障機(jī)制必將成為研究的熱點(diǎn)問題。

(4)綠色節(jié)能是網(wǎng)絡(luò)研究的新方向，機(jī)會網(wǎng)絡(luò)中節(jié)點(diǎn)能量有限，為其設(shè)計高效節(jié)能的協(xié)議是機(jī)會網(wǎng)絡(luò)大規(guī)模部署的基礎(chǔ)。

另外，基于機(jī)會網(wǎng)絡(luò)的應(yīng)用開發(fā)與部署也將成為未來重要的研究方向。

6 結(jié) 語

機(jī)會網(wǎng)絡(luò)是一種面向缺乏端到端連接通信環(huán)境的移動自組織網(wǎng)絡(luò)，能夠在缺乏網(wǎng)絡(luò)基礎(chǔ)設(shè)施的條件下，為用戶提供移動互聯(lián)網(wǎng)的接入能力。本文從概念、結(jié)構(gòu)、節(jié)點(diǎn)運(yùn)動模型、消息傳遞機(jī)制以及擁塞控制幾方面對機(jī)會網(wǎng)絡(luò)作了簡要介紹，并對未來可能存在的挑戰(zhàn)進(jìn)行了展望。從中可以看出，雖然機(jī)會網(wǎng)絡(luò)的相關(guān)研究已經(jīng)取得了一定的成就，但還有很多問題需要進(jìn)一步研究。期望通過對現(xiàn)有機(jī)會網(wǎng)絡(luò)研究成果的總結(jié)與分析，為本領(lǐng)域研究人員的深入研究探明方向。

［1］Pelusi L，Passarella A，Conti M.Opportunistic networking:data forwarding in disconnected mobile ad hoc networks［J］.Communications Magazine，IEEE，2006，44(11):134－141.

［2］Fall K.A delay－tolerant network architecture for challenged internets［C］//Proceedings of the 2003 conference on Applications，technologies，architectures，and protocols for computer communications.ACM，2003:27－34.

［3］熊永平，孫利民，牛建偉，等.機(jī)會網(wǎng)絡(luò)［J］.軟件學(xué)報，2009，20(1):124－137.

［4］林闖，董揚(yáng)威，單志廣.基于DTN 的空間網(wǎng)絡(luò)互聯(lián)服務(wù)研究綜述［J］.計算機(jī)研究與發(fā)展，2014，51(5):931－943.

［5］Ker nen A，Ott J，Krkkinen T.The ONE simulator for DTN protocol evaluation［C］//Proceedings of the 2nd international conference on simulation tools and techniques.ICST (Institute for Computer Sciences，Social－Informatics and Telecommunications Engineering)，2009:55.

［6］Broch J，Maltz D A，Johnson D B，et al.A performance comparison of multi－h(huán)op wireless ad hoc network routing protocols［C］//Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking.ACM，1998:85－97.

［7］Bettstetter C.Mobility modeling in wireless networks:categorization，smooth movement，and border effects［J］.ACM SIGMOBILE Mobile Computing and Communications Review，2001，5(3):55－66.

［8］Ekman F，Kernen A，Karvo J，et al.Working day movement model［C］//Proceedings of the 1st ACM SIGMOBILE workshop on Mobility models.ACM，2008:33－40.

［9］Musolesi M，Mascolo C.A community based mobility model for ad hoc network research［C］//Proceedings of the 2nd international workshop on Multi－h(huán)op ad hoc networks:from theory to reality.ACM，2006:31－38.

［10］Spyropoulos T，Psounis K，Raghavendra C S.Performance analysis of mobility－assisted routing［C］//Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing.ACM，2006:49－60.

［11］Hsu W，Spyropoulos T，Psounis K，et al.Modeling time－variant user mobility in wireless mobile networks［C］//INFOCOM 2007.26th IEEE International Conference on Computer Communications.IEEE.IEEE，2007:758－766.

［12］Eagle N，Pentland A.Reality mining:sensing complex social systems［J］.Personal and ubiquitous computing，2006，10(4):255－268.

［13］UCSD.Wireless topology discovery project，［EB/OL］.http://sysnet.ucsd.edu/wtd/wtd.html.

［14］Diot C，et al.Haggle project.［EB/OL］.http://www.haggleproject.org.

［15］Tang L，Zheng Q，Liu J，et al.SMART:A selective controlled－flooding routing for delay tolerant networks［C］//Broadband Communications，Networks and Systems，2007.BROADNETS 2007.Fourth International Conference on.IEEE，2007:356－365.

［16］Jain S，F(xiàn)all K，Patra R.Routing in a delay tolerant network［M］.ACM，2004.

［17］Vahdat A，Becker D.Epidemic routing for partially connected ad hoc networks［R］.Technical Report CS－200006，Duke University，2000.

［18］Spyropoulos T，Psounis K，Raghavendra C S.Spray and wait:an efficient routing scheme for intermittently connected mobile networks［C］//Proceedings of the 2005 ACM SIGCOMM workshop on Delay－tolerant networking.ACM，2005:252－259.

［19］Marfia G，Pau G，De Sena E，et al.Evaluating vehicle network strategies for downtown Portland:opportunistic infrastructure and the importance of realistic mobility models［C］//Proceedings of the 1st international MobiSys workshop on Mobile opportunistic networking.ACM，2007:47－51.

［20］Burgess J，Gallagher B，Jensen D，et al.MaxProp:Routing for Vehicle－Based Disruption－Tolerant Networks［C］//INFOCOM.2006，6:1－11.