混合式移動社會網絡及消息分發機制綜述

孔 靚， 賈美娟， 邵國強

(大慶師范學院 計算機科學與信息技術學院， 黑龍江 大慶 163712)

引言

移動社會網絡(Mobile Social Networks，MSNs)已經滲透到現代社會的各個領域，從滴滴打車，到微信交友，再到淘寶購物，無不昭示出其與人類生活的相互依賴和深度融合。混合式移動社會網絡(Hybrid Mobile Social Networks，HMSNs)代表著MSNs在復雜環境下的發展趨勢，具備移動網絡與社會網絡、集中式拓撲與分布式拓撲、直接鏈路與機會鏈路共存下的結構互補優勢，無論是美國、日本等發達國家的戰略立項，還是具體的消息分發機制研究中，都是當前該領域關注的重點[1]。因此，本文針對MSNs及HMSNs這2種社會網絡的特性及關系擬做出全面分析比較，并對相應的消息分發方法的優缺點進行詳細剖析，最后提出未來的研究方向。基于此，本文可給出研究內容論述如下。

1 傳統MSNs

MSNs是傳統社交網絡在移動網絡領域的應用和延伸[2]，自提出以來，形成了集中式、分布式和混合式3種典型模式。其中，集中式的消息分發依靠基礎網絡結構和中心服務器完成，網絡拓撲結構簡單，消息分發策略單一；分布式的消息分發借助移動節點之間的相互通信完成，無需中心服務器的支持，部署靈活方便。

在網絡基礎設施的支撐下，集中式MSNs可提供高質量的移動社交服務，無需移動用戶和中心服務器在物理位置上保持關聯，但是卻無法避免這種客戶服務器模式的性能瓶頸和單點失效問題。Gupta等人[3]早在2009年就著手這一領域的研究嘗試，并提出了MoBiSoC中間件平臺，致力于為User-centric和Place-centric這2類服務提供統一的解決方案。

2 混合式移動社會網絡HMSNs

文獻[1]明確指出MSNs的發展趨勢是將集中式和分布式兩者進行融合，使其兼具集中式和分布式的優點，在受限的網絡資源環境下具有潛在的應用價值[2]，即HMSNs的概念雛形，其典型結構如圖1所示。

HMSNs不但是集中式和分布式MSNs在體系結構上的結合，而且是端到端和機會轉發2種消息分發機制的融合。與集中式MSNs相比，HMSNs的結構靈活且部署方便；與分布式MSNs相比，HMSNs既可以在移動節點間直接指派消息分發，又可以借助潛在的中心結構來保障消息分發能力，因而在復雜環境下具有重要的應用價值。然而，HMSNs還存在著高度動態的網絡拓撲結構、難以控制的消息分發過程、有限能力的連接機會等問題，嚴重阻礙了HMSNs的實用化進程[4]。

圖1 HMSNs概念結構

文獻[1]對傳統MSNs和HMSNs的特點進行了歸納，研究結果可詳見表1。

表1 傳統的MSNs和HMSNs的對比分析

3 消息分發方法

在MSNs環境下，如何實現高效的消息分發始終是本領域的熱點和難點問題。傳統方法大都基于位置信息，如GPSR、MV、Mobyspace、Locus等[5]，當前研究多是從社會屬性、消息內容等方面探討展開；在網絡連通能力受限的環境下，常采用主動機制和混合拓撲來提升消息分發效率[6]。本文將從社會網絡、消息內容、主動機制和混合拓撲4個方面來梳理MSNs消息分發方法。研究詳情可分述如下。

3.1 基于社會網絡分析的消息分發

3.1.1 研究分析綜述

文獻[5]根據節點的中心度、相似度等社會屬性選擇中繼節點，在全局網絡拓撲和節點歷史活動數據的基礎上，將具有相近社會屬性的節點劃分到同一社區，進而將消息分發問題轉化為社區間和社區內的選路問題。Bubble Rap[7]通過分析節點社會特性和實際移動軌跡來構建社會關系圖，然后根據節點的全局等級和本地等級選擇下一跳節點。

傳統的社區劃分需要全局網絡信息和節點歷史行為數據，難以適用于分布式MSNs或者HMSNs的消息分發。在分布式的探測方法中，每個節點通過探測鄰居節點來構建局部社交地圖，根據節點間的相遇頻度和關系密切程度構建局部社區結構。文獻[8]通過聯系頻度和聯系時長生成高質量社會圖，支持社區結構的分布式探測，并識別社區間的橋節點和社區重疊關系。文獻[9]采用時間聯系圖模型來分析網絡動態特征，將社會性和聯系圖進行關聯，在用戶中心度和消息分發角色間建立了強關聯關系，便于對消息分發的效率進行測量和分析。

3.1.2 研究小結

基于社會屬性的消息分發需要考慮用戶間的社會關系來選擇中繼節點，這種機制通常需要預先探測社區結構；根據歷史數據形成的社區結構，難以兼顧社區演化性質且不利于擴展，分布式的社區探測又會產生嚴重的網絡資源消耗。更為突出的問題是，當新增移動節點或社會屬性時，極有可能對已建立的社區結構產生較大影響，導致現有方法難以取得理想的效果，甚至失效。

3.2 基于消息內容和節點興趣的消息分發

3.2.1 研究分析綜述

基于消息內容和節點興趣的消息分發方式主要依托發布/訂閱實現消息內容與節點興趣的匹配。文獻[10]提出了基于節點興趣的消息分發框架SocialCast，根據移動節點間的同嗜性(Homophily)定義了消息分發的效用函數，進而依據效用大小來選擇中繼節點。在文獻[11]所構建的發布/訂閱覆蓋網系統中，代理節點不但負責消息轉發，而且還需對節點間的發布/訂閱關系進行維護，在高度動態的環境下，網絡資源消耗較大。文獻[12]提出以內容為中心的消息分發模型，從目標函數選擇和頻譜特征分簇的角度來描述消息分發問題，采用隨機網絡編碼來充分利用網絡的冗余能力，以提高消息分發效率。文獻[13]考慮節點資源限制和消息歡迎度，提出以內容為中心的消息分發方法，目的是最大化消息交付率。為了分析消息歡迎度對分發效率的影響，文獻[14]建立了一個通用的分析框架模型，從而為這一類消息分發方法建立了理論依據。

3.2.2 研究小結

在消息分發中采用發布/訂閱模式使得消息源節點和目的節點具有解耦特性，從而在動態的網絡拓撲下具有較好的適應性；然而代理節點的失效將會造成節點間發布/訂閱關系的丟失，導致消息分發過程中斷。以內容為中心的消息分發機制需要在移動用戶和消息內容間建立關聯，且依賴于消息內容的快速、準確發現，導致消息分發效率難以提高[15]。

3.3 基于主動機制的消息分發

3.3.1 研究分析綜述

基于主動機制的消息分發是為了彌補MSNs中節點相遇概率較低、機會連接能力不足而采用的手段。在MSNs中，移動用戶的移動目的是為了完成某種社會任務，并不是為了將所攜帶的消息轉發出去。這種機會式消息分發的性能優劣性很大程度上取決于用戶的移動規律，也就是移動模型是否能夠準確預測移動用戶的活動規律。為了解決這個問題，在某些特定場景下已經提出了相應的主動式消息分發方法，然而由于缺乏社會屬性的考慮，導致消息分發效率并不理想[16]。

文獻[17]考慮了MSNs中真實用戶的移動情況，提出了一個基于消息擺渡策略的超級節點路由方案，從社會屬性的觀點來研究主動式消息分發。該方案將普通用戶的移動性建模為半馬爾科夫模型，而將超級用戶路由建模為凸優化和旅行商組合優化問題。在此基礎上，文獻[18]提出了基于地理特征和社會屬性相結合的超級節點路由策略，目標是優化MSNs中的數據廣播。該方案根據統計發現移動用戶在地理社區中的駐留時間具有冪律分布，因此將用戶移動模型建模為一個半馬爾科夫模型，計算出地理社區中用戶逗留時間的穩態概率分布，進而衡量每個地理社區的移動用戶密度。基于此，即研發設計了具有最小化時延或者最大化消息分發效率的靜態擺渡路由算法。

3.3.2 研究小結

主動式消息分發方法大都通過部署擺渡節點或者超級節點的形式設計實現[19]，雖然對普通節點的移動規則未做限制，但需要為普通節點的移動性進行建模，或者在全局上發現移動用戶的分布規律。

3.4 基于混合拓撲的消息分發

3.4.1 研究分析綜述

基于混合拓撲的消息分發大多是從多網共存、異構鏈路共存的角度開展研究，目的是利用混合拓撲實現流量分擔，降低中心網絡負載。

針對基礎蜂窩網絡與Ad Hoc的共存，文獻[4]提出了一種視頻分發方案，將網關節點的選擇問題、網關到終端的路由問題以及視頻適配問題進行了形式化描述，然后采用貪婪算法獲得近似優化解。文獻[20]提出了一個混合式消息分發方法MobiTribe，支持智能手機自主形成MSNs以達成流量分擔的目的需求。這種方法能夠通過低代價連接提供持續可用消息，而不會對通信費用和電池能量產生過多的損耗。在MobiTribe的基礎上，文獻[11]提出通過“Always-On”網絡基礎設施將消息內容復制到智能終端，然后通過機會式通信在終端之間進行消息分發，以彌補單一機會式消息分發所帶來的高時延問題。文獻[21]首先研究了蜂窩網絡和DTN的集成方法，然后使用“存儲-攜帶-轉發”的模式進行消息分發，最大化消息交付率和最小化蜂窩網絡接入的花費。另外，文獻[22-23]將機會網絡和D2D(Device to Device)通信相結合，提出了一個基于SNSs(Social Network Services)的流量卸載框架TOSS，用戶通過機會式連接在局部區域內分享消息。

針對車載自組織網絡中直接連接和間歇性連接共存的情況，文獻[24]提出了一個適用于高速路場景的混合式消息分發協議HyDi(Hybrid Data Dissemination Protocol)。在間歇性連接時，采用“存儲-攜帶-轉發”的方式進行消息分發；而當存在穩定的直接連接時，采用廣播抑制策略以避免鏈路層的競爭。為了在具有社區結構的網絡中實現高效的消息分發，文獻[16]提出了一個混合消息分發方案，在社區Ad Hoc子網內可做到直接消息分發處理，而在其它部分采用機會式通信；該方案還在社區內選擇一個頭節點直接參與消息分發策略的選擇，以提升消息分發效率。

3.4.2 研究小結

雖然混合拓撲下的消息分發研究剛剛興起，但已經在數據流量分擔、選路能力提升等方面呈現出明顯優勢[25]。然而，現有研究還缺乏混合動態拓撲的統一建模和描述機制，不能充分利用混合拓撲的互補特性來提升消息分發能力，也不利于系統的擴展和應用。

4 研究現狀總結及未來展望

MSNs的發展趨勢揭示出了人類社會關系與無線移動通信的深度融合，利用其承載消息分發任務已成為一種必然需求。然而在特定環境下，如遇突發災難，傳統MSNs將無法滿足消息分發效率的要求。HMSNs不但具備移動網絡與社會網絡、集中式拓撲與分布式拓撲、直接鏈路與機會鏈路等共存下的結構互補優勢，而且還存在可利用的網絡狀態弱反饋能力，這種特性使HMSNs在突發災難環境下具有承載消息分發的潛在優勢，已經引起了國內外學者的高度關注[26]。然而，由于資源受限、連接受限、移動受限等因素，導致現有的消息分發方法存在如下具體問題亟需得到解決：

(1) 消息冗余、矛盾現象嚴重。消息內容來源于移動節點對突發災難事件的感知，然而受環境因素、資源狀態和拓撲結構的影響，缺少建立節點間關聯感知的有效機制，既無法保障低冗余的消息生成，也極有可能產生相互矛盾的消息內容，直接影響到消息分發的效率，甚至導致網絡狀態惡化。

(2) 消息分發選路的效率較低。HMSNs涵蓋移動網絡與社會網絡、集中式與分布式結構以及直接連接與機會連接3個層次的混合特性，在突發災難環境下，現有方法難以快速地發現網絡中存在的可用路徑，導致選路效率難以滿足實際要求。

(3) 消息分發控制機制的自適應性較差。現有方法主要依據確定性的全局狀態來優化節點行為，而在突發災難環境下難以獲得網絡狀態的確定性反饋，導致移動節點無法選擇優化的消息分發策略，網絡資源浪費現象嚴重，網絡效用較低。

MSNs在國內的研究已經日趨深入，在機會路由、節點激勵、消息傳輸、安全信任等方面取得了豐碩成果[9，10，12，14，15，25]，極大地推動了MSNs的研究進展，樹立了中國在該領域的國際學術聲譽。同時，從研究現狀可以看出，HMSNs在突發災難環境下具有潛在的應用價值，美國、日本等國家已將這一領域研究提升到國家戰略層面。據此，未來對該方面的研究應將緊密圍繞突發災難環境下資源受限、連接受限、移動受限等典型特征，利用HMSNs的結構互補和網絡狀態弱反饋優勢，從消息生成、快速選路和分發控制3個環節突破影響消息分發效率的關鍵問題，滿足極端環境下的設計應用目標。

5 結束語

本文對移動社會網絡MSNs及混合式移動社會網絡HMSNs進行對比分析，闡述2種社會網絡的研究現狀，及對應的消息分發機制存在的問題：目前的研究方法效果不理想，甚至失效；以內容為中心的消息分發機制可能導致較低的消息分發效率；主動式消息分發方法缺乏混合動態拓撲的統一建模和描述機制，不能充分利用混合拓撲的互補特性來提升消息分發能力，也不利于系統的擴展和應用。根據當前研究存在的問題，文章最后提出未來的研究方向。