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

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

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

?

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

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

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

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

關鍵詞機會網絡；消息分發(fā)；聯(lián)合聚類；興趣匹配；擁塞控制

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

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

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

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

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

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

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

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

1相關工作

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

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

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

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

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

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

2問題描述

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

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

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

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

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

3基于聯(lián)合聚類的節(jié)點興趣與行為分析方法

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

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

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

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

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

3.1興趣匹配度量方法

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

(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節(jié)點距離度量方法

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

(15)

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

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

(16)

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

(17)

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

(18)

3.3聯(lián)合聚類分析算法

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

Fig. 4　Process of co-clustering.圖4　聯(lián)合聚類流程

4消息分發(fā)與緩存控制策略

4.1目標區(qū)域劃分

(19)

4.2消息轉發(fā)規(guī)則

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

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

4.3擁塞控制機制

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

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

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

(20)

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

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

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

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

5機會社會網絡消息分發(fā)系統(tǒng)

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

Fig. 5　Message dissemination system.圖5　消息分發(fā)系統(tǒng)

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

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

算法1. 改進聯(lián)合聚類算法.

輸入: 矩陣A和矩陣W;

輸出: (ρ*,γ*).

① 初始化(ρ,γ);

③ 計算AU,AV;

④ repeat

⑥ 更新行聚類;

⑦ fori=1 tomdo

wij)2];

⑨ end for

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

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

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

算法2. 消息分發(fā)算法.

輸入: 節(jié)點u;

輸出:M,CM.

① 等待與X連接的機會;

② ifX是核心網

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

④ 下載(ρ,γ);

⑤ else ifX是移動節(jié)點u′

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

⑦ Part A:

⑧ for 緩存中的M

⑩ 發(fā)送M到u′;

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

6實驗與分析

6.1仿真平臺與數(shù)據集

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

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

6.2對比算法介紹

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

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

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

6.3仿真結果及分析

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

1) 投遞率

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

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

2) 投遞時延

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

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

3) 緩存占用率

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

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

4) 分發(fā)效率

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

Fig. 9　Comparison of dissemination efficiency.圖9　分發(fā)效率的比較

5) 分發(fā)覆蓋率

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

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

6) 節(jié)點匹配度

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

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

7結論

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

本文下一步的工作主要有：優(yōu)化節(jié)點相遇概率統(tǒng)計的方法，以及探索節(jié)點移動規(guī)律對消息分發(fā)效率的影響.

參考文獻

[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);中央高校基本科研業(yè)務費專項資金項目(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).