基于興趣匹配的機會社會網絡消息分發機制

張淯舒　王慧強　馮光升　呂宏武

(哈爾濱工程大學計算機科學與技術學院　哈爾濱　150001)(zhangyushu@hrbeu.edu.cn)

?

基于興趣匹配的機會社會網絡消息分發機制

張淯舒王慧強馮光升呂宏武

(哈爾濱工程大學計算機科學與技術學院哈爾濱150001)(zhangyushu@hrbeu.edu.cn)

摘要機會社會網絡(opportunistic social networks)能夠利用節點移動創造的相遇機會，在缺乏持續端到端連接的網絡中，為用戶提供穩定的消息分發途徑，但在消息分發效率以及用戶體驗方面存在不足.為提高消息分發系統的性能、改善網絡用戶體驗，提出一種基于節點興趣匹配的機會社會網絡分發機制.通過引入混合結構的機會社會網絡分發系統解決網絡拓撲信息獲取不全與節點計算能力不足的問題；從節點行為規律與興趣愛好2方面對網絡進行分析，并提出一種用于復雜關系數據分析的聯合聚類方法；針對用戶需求，設計消息屬性與節點興趣匹配優先的消息分發策略.仿真結果表明，該機制能夠在投遞率、投遞時延、緩存占用率等方面提升網絡性能，且具有較高的分發效率、覆蓋率與興趣匹配度.

關鍵詞機會網絡；消息分發；聯合聚類；興趣匹配；擁塞控制

機會社會網絡(opportunistic social networks)[1-2]是移動自組織網絡的演化，是社交網絡向線下實體化轉變的一種形式，能夠在缺乏持續、穩定端到端連接的環境中，通過節點移動帶來的相遇機會實現信息傳遞，可以更好地應對無線環境中需要面對的間歇性連接、大延遲、高錯誤率等通信特征.作為移動互聯網絡的一種有效接入方式，采用“存儲-攜帶-轉發”形式路由協議的機會網絡，能夠極大地拓展移動互聯網絡的覆蓋范圍，使得在缺乏網絡基礎設施的環境中實現信息的分發與檢索成為可能.社交網絡分析方法的引入，提高了網絡拓撲感知、社區劃分與節點行為預測的準確性，有助于網絡性能的增強與用戶體驗的提升，然而不斷擴大的網絡規模以及隨之而來的節點與信息數量的急劇增加，使其分析系統與方法都面臨著數據收集與處理的壓力.

機會網絡的特殊路由方式已被廣泛應用于校園網絡、手持交換網絡和車載網絡等移動網絡環境中.隨著機會網絡應用的增加，作為路由研究拓展與延伸的消息分發機制也受到越來越多的關注.與傳統網絡中數據分發屬于應用層功能不同，機會網絡的消息分發與其路由機制密不可分，機會路由的多副本特性使得消息分發在其傳遞過程中得以實現.然而，在實際使用的過程中，為保證消息傳輸的成功率，網絡中會存在大量重復的消息副本，使得消息分發過程極大地占用網絡存儲資源，成為造成網絡擁塞的主要原因.在機會社會網絡這種典型的資源受限網絡中，節點行為由用戶設置的策略決定，如果節點有限的存儲資源被過多的無關消息占用，會導致用戶在網絡協助策略的設置上趨于自私，進而影響整個網絡的性能.針對機會網絡中節點自私行為的問題，雖然有多種懲罰機制被提出，但是懲罰機制不能解決產生自私行為的根本問題，即使能提高網絡整體表現，也無法改善單一用戶的服務體驗.

Kayastha等人在文獻[2]中對移動社會網絡相關研究做了深入總結與分析，將其體系結構分為中心式、分布式與混合式3種.其中，中心式結構的網絡中設備通過移動網絡、WIFI等方式直接與核心網絡連接，節點能夠連接到豐富的信息與計算資源，但會受到無線接入范圍的限制；分布式結構的網絡中節點以自組織方式組網，雖然其拓撲結構具有極強的魯棒性，不依賴基礎通信設施，但缺乏豐富的內容；混合式結構的網絡能夠繼承上述2種結構的優點，雖然節點不能時刻與核心網絡連接，一般情況下與其他節點通過自組織方式建立連接，但能夠通過移動獲得與核心網絡連接的機會，更符合實際生活中使用場景的特點.然而，現有機會社會網絡的相關研究大多面向分布式體系結構，實際使用效果不可避免地受到節點信息獲取不全與計算能力不足的影響，缺乏應對大規模網絡及其產生的大數據分析需求等挑戰的能力.可見，構建混合式結構的機會社會網絡是在保持網絡結構靈活性的基礎上，應對網絡規模增大的可行方法.

針對混合式機會社會網絡的結構特性，本文提出一種基于興趣匹配的機會網絡分發機制.該機制具有的優點可以概括3個方面：

1) 與面向分布式結構的機會社會網絡研究相比，混合式結構的網絡節點能夠利用與核心網絡連接的機會，同步各自收集的網絡拓撲信息，以此解決離散分布的節點信息獲取不完整的問題；

2) 利用核心網絡的計算能力，可以設計相對復雜的網絡拓撲與節點關系分析算法，對節點行為、興趣與消息屬性進行聯合聚類分析，使聯系緊密且興趣相近的節點聚集為簇，提高分析結果對網絡描述的準確性；

3) 在消息分發過程中，優先選擇與消息屬性相符的節點作為中間節點，提高消息屬性與節點興趣的匹配度，降低無關消息對節點資源的占用，從而提升網絡中消息分發系統的用戶體驗.

此外，設計了一種基于消息密度的擁塞控制機制，控制副本數量在合理區間，既不影響分發效率，又不給網絡制造過高的壓力.實驗表明本文提出的消息分發機制不僅能夠提高消息投遞率、減少投遞時延、降低緩存占用率，而且能夠有效地提高消息分發的效率、提升消息分發服務的用戶體驗.

1相關工作

機會網絡的概念最早由Pelusi等人[1]提出，其中許多概念都來源于Fall在文獻[3]中提出的延遲容忍網絡(delay tolerant network, DTN).隨后，大量針對機會網絡的路由算法被提出，這些算法大多從消息復制與拓撲預測2個方面增強機會網絡的路由表現.Epidemic算法與Spray and Wait算法通過增加消息在副本中的數量的方式提高路由效率，而Seek and Focus，PRoPHET，MaxProp算法則通過預測選擇投遞成功率較高的節點.

此外，更多的較為復雜的基于拓撲預測方法被相繼提出.Whitbeck等人[4]采用基于連接的最大直徑方式；Dang等人[5]通過在線統計節點相遇概率的方式，為節點的簇劃分以及信息交換和路由提供基礎；另外，Hui等人[6]針對口袋交換網絡(pocket switched network, PSN)，引入中心度和社區的概念，運用社會學的相關理論優化路由策略；Jahanbakhsh等人[7]將社會距離作為選取消息轉發目標的度量，同時為降低動態社區劃分方法的計算壓力，引入靜態的社會關系圖.

Fig. 1　Hybrid opportunistic network architecture.圖1　機會網絡混合式結構

作為路由算法的擴展與延伸，機會網絡消息分發獲得了越來越多的關注.Lenders等人[8]采用了基于發布訂閱模式的內容分發架構，在沒有基礎設施支持的情況下，首次實現移動無線節點間的消息共享.Yoneki等人[9]首次引入社交關系的信息，提出了基于社交感知的內容發布訂閱系統.Ros等人[10]提出一種利用局部周期性的信標消息構造節點的連通支配集，并對支配集內節點進行廣播的分發方法.

隨著研究的深入，人們發現在機會網絡環境中廣泛存在的自私節點能夠對網絡性能造成極大的影響.因此，設計機會網絡環境的激勵機制成為新的挑戰.Lu等人[11]提出了一種由消息源節點制定獎勵策略的機制，能夠實現了機會網絡中隱私敏感數據的安全、高效分發.Sugiyama等人[12]提出一種基于懸賞規則的消息分發傳遞機制，節點在發送消息時聲明參與消息傳遞節點的總獎勵額度，中間節點利用自身剩余資源換取相應獎勵.Ning等人[13]提出一種自私性驅動的消息分發激勵策略，中間節點能夠通過參與消息傳遞獲取虛擬支票，并兌換相應的報酬.Valerio等人[14]利用認知方法設計了一種可擴展的機會網絡消息分發機制，主要通過節點的歷史活動分析與隨機選擇相結合的方式決定消息復制的方式.Vingelmann等人[15]討論了網絡編碼在機會網絡消息分發中的應用，并分析了不同編碼方式在多種應用場景中的實際表現情況.Wang等人[16]設計了蜂窩網絡與機會網絡相結合的信息分發系統，利用機會離線通信方式極大地降低了蜂窩網絡的數據流量.

有限的存儲空間、計算能力與能量等私有資源被大量應用于處理與用戶無關的信息，是產生自私節點的主要原因.現有的機會網絡分發機制的研究大多以分發效率、覆蓋率等宏觀指標衡量分發算法的性能，沒有考慮分發過程中用戶體驗的優劣，容易引起用戶趨向于選擇較為自私的網絡協作策略.而對自私節點的處理上，也大都采用基于獎勵懲罰的激勵機制，雖然提高了網絡的整體性能，但單個節點的用戶體驗并沒有提升.另外，現有機會網絡分發機制的研究多數是建立在分布式網絡結構上，分發算法在實際使用中會受到拓撲信息獲取不全、節點計算能力低下等因素的限制，難以準確地預測網絡拓撲的變化趨勢，會對消息分發效果造成嚴重影響.

2問題描述

機會社會網絡的混合式結構模型如圖1所示.機會社會網絡由多種無線手持設備組成，通常情況下，各節點采用自組織方式組網，不依靠基礎通信設施接入核心網絡.通過自身移動，節點不僅能夠與其他節點相遇并進行信息交換，還能夠獲得周期性地接入核心網絡的機會.利用與核心網絡的連接機會，節點將自身收集的網絡拓撲信息與用戶興趣同步到核心網絡進行分析，并從核心網絡接受返回的分析結果.同時，核心網絡也利用這種間歇性的連接向網絡注入消息分發任務.

網絡的全局拓撲信息是消息分發的基礎，而機會社會網絡節點的移動性使得網絡不具備穩定的拓撲結構，通常情況下其拓撲結構利用其節點間的關聯關系與社區劃分等方式描述.本文中，節點分別存儲自身收集的局部拓撲信息與核心網絡返回的全局拓撲信息.其中，局部拓撲信息由節點間的歷史相遇記錄表示，作為對相應節點在未來一段時間內相遇概率的預測，在相遇時節點分別更新該信息；全局拓撲信息由節點行為與興趣聯合聚類結果表示，以各節點收集的局部拓撲信息為基礎，當節點獲得與核心網絡連接的機會時，上傳近期收集的局部拓撲與節點興趣信息供其分析，并從核心網絡同步最新全局拓撲信息.

在機會社會網絡分發系統中共包含m個節點，用集合U表示，n種消息類型，用集合V表示.消息評分可以記作(ui,vj,rij)，表示用戶ui對消息類型vj的評分為rij；相遇統計可以記作(ui,uj,pij)，表示用戶ui與用戶uj的相遇概率為pij.核心網絡收集并合并各節點上傳的消息評分列表與相遇統計列表，構造節點與消息類型的聯合特征矩陣A與節點相似矩陣W.其中，A=[aij]m×n，aij對應消息評分(ui,vj,rij)；W=[wij]m×m，wij對應相遇統計(ui,uj,pij).核心網絡根據A與W對節點與消息屬性構成的二元關系U×V所對應的矩陣Z進行聯合聚類分析，并獲得聚類結果(ρ,γ)，其中(ρ,γ)表示一組映射關系：

ρ:{1,2,…,m}|→{1,2,…,k}，

γ:{1,2,…,n}|→{1,2,…,l}.

3基于聯合聚類的節點興趣與行為分析方法

利用核心網絡對節點興趣與行為進行分析，與傳統的分布式分析方法相比，能夠有效地避免由節點計算能力較弱與信息獲取不全導致的結果不準確問題.網絡優化問題一般可以從路徑選擇與消息屬性2方面考慮，而機會網絡可以將通過節點移動創造的相遇機會當作通信鏈路使用，因而可以通過分析節點行為規律與消息屬性的聯系提高網絡消息分發的效率.本文利用聯合聚類方法同時從節點興趣與行為2個方面探索網絡行為特征，所得到的聚類分析結果能夠作為消息分發決策的基礎.

一般情況下，聯合聚類通常用于分析圖2所示的普通二元關系U×V，通過對U與V的聯合特征矩陣A的處理與分析，獲得聚類結果(ρ,γ).然而，在機會網絡中除了節點興趣與消息類型的關系外，節點相互聯系的緊密程度也對消息分發效果具有重要的影響.因此，機會網絡中節點與消息的關系是如圖3所示的復雜二元關系，由(U×V,U×U)表示，

Fig. 2　Common binary relation.圖2　普通二元關系

Fig. 3　Complex binary relation.圖3　復雜二元關系

分別對應U與V的聯合特征矩陣A以及U的相似矩陣W.為解決該問題，提出一種面向復雜二元關系數據的聯合聚類方法.下面先分別從特征矩陣A與相似矩陣W角度分析聚類質量的評價方法，提出興趣匹配與節點距離的度量方法，再給出聯合聚類的簡要流程.

3.1興趣匹配度量方法

在信息學中，對于二元關系U×V來說，聯合聚類理論上就是要尋找特定的(ρ*,γ*)，近似滿足：

(1)

其中，I(U;V)代表U與V的交互信息，能夠利用U與V的特征矩陣A通過某種形式表示.選取平方歐氏距離作為度量標準，即dφ(a1,a2)=(a1-a2)2，其中φ(a)=a2.顯然dφ滿足：

dφ(a1,a2)=φ(a1)-φ(a2)-a1-a2,φ(a2),

(2)

(3)

(4)

(5)

(6)

將式(3)代入可得：

(7)

(8)

(9)

(10)

(11)

(12)

(13)

3.2節點距離度量方法

相似矩陣W由各節點提供的相遇概率統計記錄(ui,uj,pij)組成，其中pij根據節點相遇情況以給定的時間間隔T為周期更新.如果在時間T內，節點i與節點j相遇，則pij更新為

(15)

其中，β∈(0,1)是相遇概率的衰減指數.

由pij的統計過程可知，wij值越大，節點i與節點j相遇概率越大、距離越小.因此，可以將節點i與節點j的距離d(ui,uj)定義為

(16)

對于相似關系U×U，聚類ρ的目標是最小化相同聚類樣本之間的聚類、最大化不同聚類樣本之間的距離，可以表示為

(17)

其中，當節點i與節點j屬于相同聚類時，ωij=1；否則，ωij=0.由此可得，聚類ρ的目標可表示為

(18)

3.3聯合聚類分析算法

聯合聚類結果(ρ,γ)可通過交替更新ρ與γ獲得，簡要流程如圖4所示，詳細算法在第5節給出.其中，ρ與γ的更新原則是使得更新后的聚類結果具有較高的聚類質量.

Fig. 4　Process of co-clustering.圖4　聯合聚類流程

4消息分發與緩存控制策略

4.1目標區域劃分

(19)

4.2消息轉發規則

當攜帶消息M的節點ui與節點uj相遇時，按照節點ui與節點uj是否屬于DM可分為4種情況：

1)ui∈DM，uj∈DM.屬于相同聚類的節點具有相似的興趣，區域DM中節點具有較大的幾率對消息M感興趣，因此在區域DM中消息轉發按照Epidemic算法方式進行.

4.3擁塞控制機制

機會網絡通常采用具有洪泛性質的消息分發策略，通過增加消息在網絡中副本數量的方法，提高消息分發效率.然而，網絡中消息副本數量過多會使節點緩存壓力增大，引起網絡擁塞現象；而消息副本數量過少又會影響網絡通信效率.針對上述問題提出一種基于消息密度的擁塞控制機制，使網絡中消息副本數量控制在合理范圍內.

該機制針對節點臨近區域中消息副本的密度，只考慮節點最近相遇的L個節點攜帶該消息的情況，能夠避免由于特定消息過量復制導致的網絡區域性擁塞現象.然而，由于不考慮當前節點緩存的剩余情況，該方法只能夠間接緩解由節點緩存溢出造成的網絡擁塞現象.

在消息分發過程中，節點u為其緩存中的消息Mj(j=1,2,…,N)分別設置長度為L的隊列Qj，Qj由二元組(ui,flagi)構成，表示與節點u相遇的最近L個節點的ID及其是否攜帶消息Mj，如果ui不攜帶消息Mj記為flagi=0，否則記為flagi=1.當節點u與u′相遇時，先將(u′,01)加入Qj隊尾.如果Qj中存在包含u′的項，則刪除該項；如果Qj中沒有包含u′的項且隊列長度超過L，則刪除Qj中隊首項；否則不對Qj進行操作.定義消息Mj的濃度CMj為：

(20)

當收集到足夠信息估算Mj密度后，即Mj對應的隊列Qj長度達到L后，節點按周期T檢查緩存中消息濃度：

若CMj∈[0,18)，則表示網絡中消息Mj濃度較低，Mj處于分發初期或末期，將Mj標記為休眠狀態，等待下一周期.如果CMj連續2個周期都低于18，則將Mj刪除，否則重新激活Mj.

若CMj∈[18,12]，則表示網絡中消息Mj濃度正常，Mj正處于分發狀態，因此應保存Mj.

若CMj∈(12,1]，則表示網絡中消息Mj濃度過高，Mj的分發基本完成，因此應將Mj刪除以避免擁塞現象產生.

5機會社會網絡消息分發系統

針對混合式結構機會社會網絡的特點，設計如圖5所示的機會社會網絡分發系統，將網絡拓撲信息的收集與分析過程分離.

Fig. 5　Message dissemination system.圖5　消息分發系統

其中，核心網絡對網絡拓撲信息進行整合與分析，節點在移動過程中收集網絡拓撲信息，并實現消息分發與擁塞控制的功能.

核心網絡中，處理U與V間復雜二元關系Z=(U×V,U×U)的改進聯合聚類分析的實現方法描述如算法1所示:

算法1. 改進聯合聚類算法.

輸入: 矩陣A和矩陣W;

輸出: (ρ*,γ*).

① 初始化(ρ,γ);

③ 計算AU,AV;

④ repeat

⑥ 更新行聚類;

⑦ fori=1 tomdo

wij)2];

⑨ end for

Aρ(i)-Aj+Ah)2;

算法1的運行時間與矩陣A和W中非零元素的個數Wglod以及行列2個維度的聚類變換操作時間分別線性相關，根據文獻[18]的相關分析，其算法復雜度可以表示為O(Wglod+mkl+nkl).一般情況下，Wglod遠大于m與n，而m與n遠大于k與l，因此，相對于復雜度為O(m2n+n3)2的SVD聯合聚類算法與復雜度為O(Wglodk)的NNMF聯合聚類算法，算法1具有明顯的效率提升.

節點收集、同步網絡拓撲信息，以及實現消息分發與擁塞控制等功能的實現方法描述如算法2所示:

算法2. 消息分發算法.

輸入: 節點u;

輸出:M,CM.

① 等待與X連接的機會;

② ifX是核心網

③ 上傳(ui,vj,rij)和(ui,uj,pij);

④ 下載(ρ,γ);

⑤ else ifX是移動節點u′

⑥ 為每個M更新(ui,uj,pij)和Q;

⑦ Part A:

⑧ for 緩存中的M

⑩ 發送M到u′;

在節點緩存空間有限且隊列Q長度恒定的條件下，算法2可在常數時間內運行完成，因此其時間復雜度為O(1)，不會對節點造成額外的計算壓力.

6實驗與分析

6.1仿真平臺與數據集

本文利用MATLAB平臺對MIT Human Dynamics Lab提供的Social Evolution數據集[19]進行基于事件驅動的仿真.Social Evolution數據集通過移動電話收集信息，記錄了同一公寓中80名學生長達8個月的活動規律與交互信息.參與者由30名大一學生、20名大二學生、10名大三學生、10名大四學生與10名研究生組成，均勻分布在公寓的1～4層.該數據集還記錄了參與者對11種類型多達1 500首音樂的評價與分享情況，參與者對音樂的評分為1～3分.參與者間的接觸間隔基本符合指數分布，同時存在明顯的社會特征.

在仿真過程中，網絡按照設定的速率產生消息分發請求，隨機選擇消息的源節點與其包含的音樂類型，并在對該類型音樂評分在2以上的節點中隨機選擇目的節點.數據包大小在[10 KB,100 KB]區間均勻分布，消息的TTL設定為1周，節點的緩存大小為20 MB.將數據集的前30%記錄作為仿真的預熱，使得各算法對網絡的分析達到穩定狀態，實驗結果從對數據集的后70%記錄的仿真中獲得.

6.2對比算法介紹

Epidemic算法是一種采用洪泛策略的機會網絡路由算法.在理想情況下，該方法能夠獲得較為理想的投遞率與投遞時延，但會對網絡造成較大的壓力.然而，實際應用的過程中由于網絡節點緩存通常較小，效果往往不理想.

Spray and Wait算法是一種限定副本數量的路由算法，通過限定網絡中消息副本總數，降低消息分發對網絡的壓力.該算法適應性強，能夠在多種網絡環境中提供較為理想的路由性能.

Clustering算法是一種基于聚類分析的機會網絡路由算法，該算法根據節點的歷史相遇信息為節點劃分所屬簇，并為關系緊密的簇選定網關節點.該算法能夠利用聚類分析結果優化消息轉發的路徑選擇過程.

6.3仿真結果及分析

下面將本文算法與對比算法在投遞率、投遞時延、緩存占用率、分發效率、分發覆蓋率以及節點匹配度6個方面進行比較.

1) 投遞率

Fig. 6　Comparison of delivery ratio.圖6　投遞率的比較

投遞率是指網絡中成功送達目的節點的消息數在消息總數中所占的比例.從圖6可以看出，Epidemic算法與Spray and Wait算法投遞率較低，Clustering算法與本文算法相對獲得了較高的投遞率.Epidemic算法采用復制策略，通過增加消息分發中間節點數量的方式提高消息的投遞率，這使得網絡中存在大量重復的消息副本.在實驗中，由于節點的緩存空間有限，不能滿足Epidemic算法的需求，當網絡中同時存在多個消息分發任務時，極易引起節點緩存的溢出，進而導致還未成功送達的消息被丟棄，造成網絡在投遞率上表現較差.Spray and Wait算法也采用復制策略，但由于具有副本數量的控制機制，相對Epidemic算法獲得了較高的投遞率.與上述算法相比，Clustering算法與本文算法采用轉發策略，限制副本的數量并對節點間的關聯關系進行分析，在中間節點的選擇上具有一定的針對性，因此更容易將消息送達目的節點.其中，本文算法由于采用了線上分析的機制，能獲得較完整、準確的網絡拓撲信息，因此獲得了最高的投遞率.

2) 投遞時延

投遞時延是指消息從產生到最終被送達目的節點所經歷的時間.從圖7可以看出，投遞時延的結果與投遞率相似.投遞時延能夠體現消息傳遞過程中路徑選擇的優化能力，選擇正確的中間節點不僅能夠獲得較高的投遞率，同時也能獲得較低的投遞時延.

Fig. 7　Comparison of delivery delay.圖7　投遞時延的比較

3) 緩存占用率

Fig. 8　Comparison of cache usage.圖8　緩存占用率的比較

緩存占用率是指網絡中消息副本占所有節點緩存的比例.從圖8可以看出，由于Epidemic算法不限制副本數量，網絡的平均緩存占用率達到了90%以上，造成大量節點的緩存溢出，嚴重影響了網絡性能；Spray and Wait算法雖然限制了副本的數量，但也是通過復制的方法完成消息的分發，也有較高緩存占用率；Clustering算法與本方算法通過收集的網絡信息對網絡拓撲進行分析，因此可以在保持高投遞率的前提下減少網絡中消息副本的數量，降低緩存占用率.本方算法設計了相應的擁塞控制機制，在仿真中獲得了最低的緩存占用率.

4) 分發效率

分發效率是指成功分發的消息數與網絡中消息轉發總次數的比值.分發效率能夠體現出消息分發算法的優化程度，具有較高分發效率的消息分發算法能夠在網絡擁塞狀態相同的情況下將更多的消息成功地送達相應的節點.從圖9可以看出，本文算法擁有最高的分發效率，接近0.4，即表示利用本文算法平均經過2～3次傳遞就能將消息送達目的節點；Clustering算法也擁有較高的分發效率，但受到分析方法與網絡信息獲取方式的影響，略低于本文算法；Epidemic算法與Spray and Wait算法分發效率較差，其中Spray and Wait算法大約需要5次傳遞將消息送達目的節點，而Epidemic算法需要將近7次傳遞才能完成.由此可以看出，本文提出的算法在投遞率相同的情況下轉發次數少于其他算法，因而產生的副本數量、占用的節點緩存較少，能夠有效節省網絡資源，提高網絡的利用率.

Fig. 9　Comparison of dissemination efficiency.圖9　分發效率的比較

5) 分發覆蓋率

分發覆蓋率是指消息的目標群體中收到消息的節點數占群體總數的比例.在實驗中，將對消息所包含音樂類型的評分在2以上的個體作為其目標群體.從圖10可以看出，Clustering算法與本方算法具有較高的分發覆蓋率.與本文算法不同，Clustering算法只對節點間的相互聯系進行分析，消息在聯系緊密的節點中相互傳遞的機會較多，而這種節點往往具有相似的興趣，使得其分發覆蓋率相對另外2種算法高很多.而本文算法從節點與消息2個維度進行分析，因此在目標群體的判斷上更為精確，在分發覆蓋率上較Clustering算法表現出了一定的優勢.

Fig. 10　Comparison of coverage rate.圖10　覆蓋率的比較

6) 節點匹配度

節點匹配度是指節點緩存中與節點興趣相匹配的消息所占空間與總的緩存占用空間的比值.該指標能夠反映用戶對消息分發算法的滿意程度，是決定用戶是否積極參加網絡協助的重要因素.從圖11可以看出，本文算法獲得了最高的節點匹配度.Epidemic，Spray and Wait，Clustering算法都沒有考慮節點匹配度的概念，使得在消息傳遞的過程中，各節點大量處理與自身不感興趣的消息，極大地消耗了節點有限的計算、存儲資源，容易使節點轉變為自私節點.而在本文算法中，節點緩存中大部分消息都是節點感興趣的，因此能夠提高節點參與網絡協助的積極性.

Fig. 11　Comparison of matching rate.圖11　匹配率的比較

7結論

機會社會網絡是一種資源受限的特殊網絡環境，如何有效利用有限的網絡通信、存儲與計算資源對提高網絡性能有重要意義.針對現有機會社會網絡分發方法存在的問題，本文提出一種基于興趣匹配的機會社會網絡分發機制.通過構建混合結構的消息分發系統，利用核心網絡較強的計算能力同時從節點行為規律與興趣愛好2個方面分析網絡拓撲變化規律與節點間關聯關系，不僅避免了單個節點所面臨的信息獲取不完整與計算能力不足的問題，還提高了網絡拓撲預測的準確性.同時，節點興趣匹配優先的分發策略也從根本上保證了用戶參與網絡協助的積極性.仿真實驗表明，與現有方法相比，本文提出的消息分發機制能夠有效地改善網絡性能，提高消息分發系統的性能.

本文下一步的工作主要有：優化節點相遇概率統計的方法，以及探索節點移動規律對消息分發效率的影響.

參考文獻

[1]Pelusi L, Passarella A, Conti M. Opportunistic networking: Data forwarding in disconnected mobile ad hoc networks[J]. Communications Magazine, 2006, 44(11): 134-141

[2]Kayastha N, Niyato D, Wang P, et al. Applications, architectures, and protocol design issues for mobile social networks: A survey[J]. Proceedings of the IEEE, 2011, 99(12): 2130-2158

[3]Fall K. A delay-tolerant network architecture for challenged Internets[C] //Proc of the 2003 Conf on Applications, Technologies, Architectures, and Protocols for Computer Communications. New York: ACM, 2003: 27-34

[4]Whitbeck J, Conan V. HYMAD: Hybrid DTN-MANET routing for dense and highly dynamic wireless networks[J]. Computer Communications, 2010, 33(13): 1483-1492

[5]Dang Ha, Wu Hongyi. Clustering and cluster-based routing protocol for delay-tolerant mobile networks[J]. IEEE Trans on Wireless Communications, 2010, 9(6): 1874-1881

[6]Hui Pan, Crowcroft J, Yoneki E. Bubble rap: Social-based forwarding in delay-tolerant networks[J]. IEEE Trans on Mobile Computing, 2011, 10(11): 1576-1589

[7]Jahanbakhsh K, Shoja G C, King V. Social-greedy: A socially-based greedy routing algorithm for delay tolerant networks[C] //Proc of the 2nd Int Workshop on Mobile Opportunistic Networking. New York: ACM, 2010: 159-162

[8]Lenders V, Karlsson G, May M. Wireless ad hoc podcasting[C] //Proc of IEEE SECON 2007. Piscataway, NJ: IEEE, 2007: 273-283

[9]Yoneki E, Hui Pan, Chan Shuyan, et al. A socio-aware overlay for publish/subscribe communication in delay tolerant networks[C] //Proc of the 10th ACM Symp on Modeling, Analysis, and Simulation of Wireless and Mobile Systems. New York: ACM, 2007: 225-234

[10]Ros F J, Ruiz P M, Stojmenovic I. Acknowledgment-based broadcast protocol for reliable and efficient data dissemination in vehicular ad hoc networks[J]. IEEE Trans on Mobile Computing, 2012, 11(1): 33-46

[11]Lu Rongxing, Lin Xiaodong, Shi Zhiguo, et al. IPAD: An incentive and privacy-aware data dissemination scheme in opportunistic networks[C] //Proc of IEEE INFOCOM 2013. Piscataway, NJ: IEEE, 2013: 445-449

[12]Sugiyama K, Kubo T, Tagami A, et al. Incentive mechanism for DTN-based message delivery services[C] //Proc of Global Communications Conf. Piscataway, NJ: IEEE, 2013: 3108-3113

[13]Ning Ting, Yang Zhipeng, Wu Hongyi, et al. Self-interest-driven incentives for ad dissemination in autonomous mobile social networks[C] //Proc of IEEE INFOCOM 2013. Piscataway, NJ: IEEE, 2013: 2310-2318

[14]Valerio L, Passarella A, Conti M, et al. Scalable data dissemination in opportunistic networks through cognitive methods[J]. Pervasive and Mobile Computing, 2015, 16: 115-135

[15]Vingelmann P, Heide J, Pedersen M V, et al. All-to-all data dissemination with network coding in dynamic MANETs[J]. Computer Networks, 2014, 74: 34-47

[16]Wang Xiaofei, Chen Min, Han Zhu, et al. Toss: Traffic offloading by social network service-based opportunistic sharing in mobile social networks[C] //Proc of IEEE INFOCOM 2014. Piscataway, NJ: IEEE, 2014: 2346-2354

[17]Banerjee A, Merugu S, Dhillon I S, et al. Clustering with Bregman divergences[J]. The Journal of Machine Learning Research, 2005, 6: 1705-1749

[18]Banerjee A, Dhillon I, Ghosh J, et al. A generalized maximum entropy approach to Bregman co-clustering and

matrix approximation[C] //Proc of the 10th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2004: 509-514

[19]Madan A, Cebrian M, Moturu S, et al. Sensing the “health state” of a community[J]. IEEE Pervasive Computing, 2012, 11(4): 36-45

Zhang Yushu, born in 1986. PhD candidate. His research interests include mobile networks and network security.

Wang Huiqiang, born in 1960. Professor and PhD supervisor. Senior member of China Computer Federation. His current research interests include cognitive networks, autonomic computing and next generation network.

Feng Guangsheng, born in 1980. PhD and lecturer. Member of China Computer Federation. His current research interests include QoS assurance of cognitive networks.

Lü Hongwu, born in 1983. PhD and lecturer. His current research interests include optimization and configuration of wireless networks resource.

Message Dissemination Based on Interest Matching for Opportunistic Social Networks

Zhang Yushu, Wang Huiqiang, Feng Guangsheng, and Lü Hongwu

(CollegeofComputerScienceandTechnology,HarbinEngineeringUniversity,Harbin150001)

AbstractOpportunistic social networks can provide message dissemination service through encounters created by nodes’ movement in intermittently connected or completely disconnected wireless networks, but there are still some shortcomings in message dissemination efficiency and user experience. In order to promote the performance of dissemination system and improve the user experience, an opportunistic social network message dissemination mechanism based on node interest matching is proposed. A kind of opportunistic social networks with hybrid architecture is introduced to avoid problems such as incomplete information of network topology and low computing ability of nodes. Considering the fact that node behaviors and interests can both affect the performance of dissemination, the analytical method designed takes both of them as reference factors, and an improved co-clustering algorithm for data with complex relationship is proposed. In addition, the interest matching rate for nodes is used to show what percentage of buffer is occupied by the useful messages to user, and a novel message dissemination strategy is proposed to raise the rate. Simulation results show that the proposed scheme can both improve the capability of opportunistic social networks in terms of delivery rate, latency and buffer usage, and promote the performance of message dissemination systems in terms of efficiency, coverage rate and interest matching rate.

Key wordsopportunistic network; message dissemination; co-clustering; interest matching; congestion control

收稿日期：2014-12-23；修回日期：2015-04-16

基金項目：國家自然科學基金項目(61370212,61402127,61502118);高等學校博士學科點專項科研基金項目(20122304130002);中央高校基本科研業務費專項資金項目(HEUCFZ1213,HEUCF100601)

中圖法分類號TP393

This work was supported by the National Natural Science Foundation of China (61370212,61402127,61502118), Research Fund for the Doctoral Program of Higher Education of China (20122304130002), and the Fundamental Research Funds for the Central Universities (HEUCFZ1213,HEUCF100601).