機會網絡研究進展

王慧強，張淯舒，呂宏武，朱金美

(哈爾濱工程大學 計算機科學與技術學院，黑龍江 哈爾濱150001)

0 引言

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

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

本文立足于機會社會網絡技術，在充分總結現有研究成果的基礎上，首先對機會網絡的概念、模型等內容作簡單介紹，然后總結該領域中的熱點研究問題，最后對其發展方向進行了展望。

1 機會網絡

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

圖1 機會網絡消息傳遞

機會網絡的實質是一種通用的面向消息的覆蓋層網絡體系結構，在端到端應用與底層網絡協議之間設置機會網絡組件，為無線網絡提供針對異構、大延遲以及間歇式連接網絡環境的通信能力。其體系結構如圖2所示。其中，機會網絡相關組件為網絡提供虛擬消息交換、命名與尋址、路由與轉發、安全保障與QoS 等機制［4］。

圖2 機會網絡體系結構

2 節點移動模型

節點移動模型通過相應的算法與規則描述節點位置、速度與移動方向等運動信息。節點的移動性通常來說是對無線網絡的挑戰，但對于機會網絡則是一種機遇。傳統的無線網絡協議普遍采用屏蔽底層節點運動的設計模式，而機會網絡的特點使得對節點移動的研究成為其協議設計的一部分。節點移動模型主要包括隨機移動模型、基于人類行為的移動模型與基于統計的真實移動模型三種［5］。

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

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

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

3 消息轉發機制

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

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

Fist Contact［16］與Direct Delivery 算法都是基于轉發的策略的路由算法，在消息的傳遞過程中，網絡中只包含一個有效的消息副本。兩種算法的區別是:First Contact 算法將消息傳遞給遇到的第一個節點，而Direct Delivery 算法僅在與目的節點相遇時才將消息轉發出去。

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

Spray and Wait［18］算法也是一種基于洪泛策略的算法，節點在相遇時向對方復制消息，與Epidemic 不同的是Spray and Wait 通過限定消息副本數量的方式避免洪泛現象的產生。Spray and Wait 算法分為Spray 與Wait 兩個階段。在Spray 階段，源節點向網絡中注入固定數目的消息副本，然后進入Wait 階段，若消息副本在上一階段沒有被送達目標節點，則攜帶消息的節點通過Direct Delivery 方式完成消息的傳遞。

PRoPHET［19］算法是一種基于預測的路由算法，該算法定義了一種預測節點間成功傳輸概率的方法。節點在相遇時更新傳輸預測值，并以此為依據決定是否轉發數據分組。

MaxProp［20］算法是一種基于調度策略的路由算法，其核心機制是節點維護的消息隊列，該隊列按照消息優先級排序，并將其作為消息傳輸與丟棄的依據。其中，消息的優先級主要由鏈路的歷史數據確定。

4 擁塞控制

與傳統IP 網絡不同，機會網絡適用的環境一般具有延遲長、抖動嚴重、間歇性連接、數據流非對稱以及資源受限等特征，傳統的擁塞控制機制不能達到理想的效果。同時，“存儲—攜帶—轉發”的路由模式也給機會網絡的擁塞控制帶來了新的挑戰。根據引起擁塞的資源不同，可以將機會網絡中出現的擁塞現象分為三種類型:節點級擁塞、鏈路級擁塞與區域級擁塞。

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

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

區域級擁塞是由網絡吞吐量不足引起的，通常表現為一個地理區域的流量過載。在不提高網絡容量條件下，為網絡提供有效的負載均衡策略，能夠在一定層度上緩解區域級擁塞的程度。

5 機會網絡面臨的挑戰

目前，盡管學術界對機會網絡的研究取得了一定的成果，但隨著機會網絡應用環境的不斷擴展，其自身發展與需求也呈現出了多樣化的趨勢。因此，未來機會網絡的研究將面臨高效、通用、安全與節能等方面的挑戰:

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

(2)機會網絡是一種典型的覆蓋網絡，設計通用的機會通信中間件能夠擴展機會網絡的使用范圍與應用場景。

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

(4)綠色節能是網絡研究的新方向，機會網絡中節點能量有限，為其設計高效節能的協議是機會網絡大規模部署的基礎。

另外，基于機會網絡的應用開發與部署也將成為未來重要的研究方向。

6 結 語

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

［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］.軟件學報，2009，20(1):124－137.

［4］林闖，董揚威，單志廣.基于DTN 的空間網絡互聯服務研究綜述［J］.計算機研究與發展，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－hop 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－hop 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，Fall 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.