機會社交網絡中基于時變興趣社區的查詢消息路由算法

畢俊蕾，李致遠

（1.江蘇大學信息化中心，江蘇 鎮江 212013；2.江蘇大學計算機科學與通信工程學院，江蘇 鎮江 212013；3.江蘇大學新一代信息技術產業研究院，江蘇 鎮江 212013）

1 引言

機會社交網絡（OSN,opportunistic social networking）是一種新型的移動社交網絡[1]。與基于移動通信網絡（如3G、4G 等）的在線移動社交應用不同[2]，OSN 網絡中節點是利用短距離無線通信技術（如Wi-Fi、藍牙等）進行機會式多跳通信。OSN在應用過程中所面臨的重要問題之一是查詢消息路由算法的研究。查詢消息路由算法的設計目標是高效地發送查詢消息到目的節點（即能提供請求響應的節點）。本文將現有的查詢消息路由方法分為兩類：擴散式查詢路由方法[3-4]和基于社會特性查詢的路由方法[5-13]。

擴散式查詢消息路由方法[3]最早出現在連接易中斷的無線網絡中，當該方法應用到OSN 環境時，需要每個節點攜帶一張消息列表。當2 個節點相遇時，相互交換各自的消息列表。節點對比對方的消息列表后，相互交換自身所沒有的消息數據。顯然，擴散式查詢消息路由方法可以獲得最優的查詢成功率，但其指數級增加的消息副本數量使該方法的可擴展性較差。基于社會特性的查詢消息路由方法是利用相遇歷史頻度高或中心度高的節點幫助進行查詢消息轉發[5]。此外，為了提高查詢算法的可擴展性，社會化社區結構和理論也常被采用。事實上，相同興趣社區內部的節點較社區外部的節點有更高的相遇概率，然而，這種方案存在的問題在于實際應用中所構造邏輯社會社區中節點間的邏輯連接關系與物理網絡中節點間的物理連接關系不匹配，這種拓撲適配現象會導致查詢消息無法及時到達目的節點。

為了解決上述查詢路由方法中存在的各種局限性，本文提出了基于時變興趣社區的查詢消息路由算法（TIMER,time-variant interest community based query message routing algorithm），主要工作如下。

1)對2 個知名的移動社交網絡數據集進行了分析，發現移動節點在時間和空間上的關聯性和規律性。

2)在1)的基礎上，提出了時變興趣社區模型，并描述了時變興趣社區的建立過程。

3)在2)提出的時變興趣社區結構上，設計了時間復雜度為O(nlogn)查詢消息路由算法，并對算法的性能進行了評估。

2 相關工作

本節主要對擴散式查詢消息路由算法和基于社會特性的查詢消息路由算法的原理進行描述，并分析其優缺點。

1)擴散式查詢消息路由算法

文獻[3]首次在部分連通的Ad Hoc 網絡中提出擴散式查詢消息路由算法Epidemic。Epidemic 算法利用節點的移動來傳遞消息數據，即當節點相遇時，它們將自身攜帶的消息數據傳送給對方。Epidemic 算法通過消息快速復制的方式將查詢消息擴散到全網，一定程度上保證了消息的投遞成功率，但同時也造成了消息副本拷貝的泛濫，致使OSN 網絡資源利用率降低，查詢消息的中途丟失率增加。針對Epidemic 算法的不足，SW（Spray&Wait）路由算法有效地控制了網絡中消息副本的數量[4]。其原理如下。設S發送消息m給目的節點D，算法的輸入是消息在網絡中的最大副本數L。當S遇到節點G時，就轉發消息m給G，并將最大副本數L減1。如果G為目的節點，則消息投遞成功，此次路由結束；如果G中繼節點，則重復上述過程，直到消息傳遞到目的節點為止。Binary SW 算法是SW算法的改進版本，它的原理是每次將消息傳遞給G時，將自身的最大副本數降低為，而G的副本數同樣設為，直到將查詢消息傳遞給目的節點為止。SW 算法的問題在于副本數L的設置，副本數L設置較大則會存在Epidemic 算法的問題，若設置較小，則會降低消息的投遞成功率，增大投遞的時延。

2)基于社會特性的查詢消息路由算法

基于社會特性的查詢消息路由算法思想是利用節點間歷史交互信息對未來的節點行為進行預測。這類路由算法中的代表性算法包括PRoPHET（probabilistic routing protocol using history of encounters and transitivity）[5]、SimBet（similarity and betweenness centrality）[6]和ICR（interest community routing）[7]。PRoPHET 通過節點間的歷史相遇信息來估計傳輸概率，它使用傳輸預測值P(a,b)作為節點a和b的路由度量，表示將消息從節點a傳遞到節點b的成功概率。若目標節點為d，節點a與b相遇，僅當P(b,d)≥P(a,d)時，節點a才將消息轉發給節點b。SimBet 路由節點的社會性度量是由節點相似性和局部介數中心性加權求和得到的。其中，節點相似性表示當前節點與目的節點的共同鄰居數，共同鄰居數越高，節點間的相似性越大；局部介數中心性則反映了節點在網絡中重要程度，節點介數越大作為中繼轉發時成功的概率越高。當節點b的SimBet 值大于節點a的SimBet 值時，節點a將消息傳遞給節點b。ICR 研究了節點的興趣，給出了節點的興趣相似度計算模型，將興趣相似的節點組成興趣社區，然后在社區內和社區間分別設計了消息路由算法。評估結果顯示社區組織結構確實可以有效地提高消息路由的性能。然而，PRoPHET、SimBet 和ICR 理論模型和實驗評估都是基于節點的隨機運動展開，忽略了節點行為在時間和空間上的關聯關系，模型的性能受制于節點移動的隨機性，從而使節點相遇所需的等待時延仍比較高。

3 移動用戶行為時空規律性和關聯性分析

本文研究的機會社交網絡運行的場景是在學術機構、辦公場所等區域，這些場景下的科研人員及其他工作人員構建起了本文研究的機會社交網絡。為了研究上述場景下節點的行為特征、分析節點的行為規律，選取了與上述物理場景相近的2 個代表性數據集——copelabs/usense[14]和 upb/hyccups[15]進行統計分析。copelabs/usense 數據集是以人們日常活動為周期（一個周期時長24 h），參與的移動節點數為72 個，采集終端為三星Galaxy S3 智能手機，數據采集和預處理軟件是安裝在智能手機上的應用軟件NSense，節點的組網采用無線Ad Hoc 方式（Wi-Fi 和藍牙），節點的活動范圍是辦公區域（實驗室和會議討論區）、休閑娛樂區域及家中，數據采集的時間間隔為1 min，數據收集時間總時長為50 h。upb/hyccups 數據集來源于布加勒斯特理工大學校園內，參與的移動節點數為78個，采集的終端采用Android 智能手機（Android系統版本號分別是4.2 和5.1）數據收集應用軟件為基于Wi-Fi 的AllJoyn 框架，數據采集的時間間隔為5 min，數據收集時長為63 d。

圖1～圖3 分別展示了24 h 內用戶在時間和空間維度上的關聯和規律性，數據來自于文獻[14]。圖中橫坐標表示用戶ID，縱坐標表示一天時長，即24 h。圖1 是用戶在辦公區域的在線時間數據統計結果。如圖1 所示，大多數節點的工作時間為8:00～18:00，少部分節點的工作時間為晚上和下午2 個時段，這和科研人員的作息是相關的。圖2 表示的是節點在休閑娛樂區域的在線時間統計結果，從圖中不難發現，大多數節點在白天時段的休息時間為12:00～13:00 或18:00～22:00，其中，中午休息時間較短，通常為1 h，少數節點選擇在凌晨活動。圖3 為節點在家中出現的時間，大多數節點在家中時間為00:00～8:00。

綜上所述，對于8:00～17:30 大多數節點出現在辦公區域，如會議室和辦公討論區。對于晚上時間段，部分節點選擇在辦公區域，部分節點選擇在家中，部分節點選擇去休閑娛樂區域，其逗留時間比較靈活，有長有短，依賴于節點的生活作息習慣。

圖1 節點在辦公區域的時段統計

圖2 節點在休閑娛樂區的時段統計

圖3 節點在家中的時段統計

圖4 和圖5 分別展示了布加勒斯特理工大學校區內節點的興趣及其演變過程，數據來自于文獻[15]。圖4 中的橫坐標和縱坐標均表示用戶ID。當用戶屬于朋友關系且屬于同一個興趣組時，標記為1，即圖中的圓點。經過統計，發現從數據采集開始到數據采集結束，因為興趣相同而成為朋友關系的比例增加了32.4%。圖5 是圖4 節點關系的演變，每一個點表示移動用戶，每一條邊表示節點之間的關系。有著共同興趣的用戶更傾向于加入同興趣的社區，并成為朋友關系，之后會相互共享彼此感興趣的信息和資源。通過興趣聚類，可以有效地提高查詢消息分發的效率。

圖4 節點間興趣關系統計結果

圖5 節點興趣關系圖演變

綜合以上實驗結果發現，移動節點的擁有者賦予了移動節點在興趣維度上的關聯關系。本文的消息路由算法研究更加關注節點的行為規律性，這對消息路由算法的中繼節點選擇起到了關鍵作用。同時表明移動節點在時間、空間和興趣維度上具有一定的關聯和規律性。這些關聯和規律性便于引導本文有效地構造時變興趣社區，并設計出高效的查詢消息路由方法。

4 基于時變模型的查詢消息路由算法

4.1 TIMER 路由算法概述

TIMER 路由算法在高校校園的物理場景中的應用，如圖6 所示，圖中圓內的數字表示節點標號，Ci表示i類興趣社區。其中，圖6(a)為高校校園物理場景，包含圖書館、實驗室、餐廳和宿舍，具體見4.3 節；圖6(b)為利用節點在時間維度上的規律性所構建的三類興趣社區結構，具體見4.2 節；圖6(c)為利用節點在時空維度上的關聯性所構建的時變興趣社區。中間的三角形區域為本文所設計的查詢消息路由算法，它是基于上述興趣社區拓撲結構的，具體見4.4 節。

圖6 基于時變模型的查詢路由算法實現原理

4.2 基于社會親密度的興趣社區的構建

首先給出社會親密度的定義。節點間的社會親密度包含了節點的連接時間、等待時間及通信頻率。由于網絡中部分節點有直接聯系、部分節點沒有直接聯系，將社會親密度分為直接社會親密度和間接社會親密度。

定義1直接社會親密度是節點i與j之間平均間隔聯系時間的倒數，其表達式如式(1)所示。它的物理意義是2 個節點等待下一次相遇的時間越短，說明它們之間的社會親密度越高。

其中，λij表示節點i與j之間的直接社會親密度，Tij表示節點i與j之間的平均間隔聯系時間，fij(t)表示時刻t之后2個節點下一次相遇所需等待時間的函數，k表示節點在[0,T]的時間范圍內聯系的頻率。

定義2間接社會親密度是節點i與j通過其他節點w進行聯系，它們之間的平均間隔聯系時間的倒數，其表達式如式(2)所示。

其中，w表示節點i與j之間的中繼聯絡節點，kiw表示節點i與w之間的聯系頻率，kwj表示節點w與j之間的聯系頻率，fiw(t)表示時刻t之后節點i與w下一次相遇所需等待時間的函數，fwj(t)表示時刻t之后節點w與j下一次相遇所需等待時間的函數。

設網絡中有n個節點，基于節點的通信歷史數據，節點ni根據定義1 和定義2 計算與其他節點的社會親密度，從而得到字節的矩陣M用來存儲網絡中節點間的社會親密度數值。之后，將M作為社會親密度數值矩陣的輸入，使用K-means 聚類算法[16-17]（K=3）得到圖6(b)所示的興趣社區。其中Cg表示第g類興趣社區，Cr表示第r類興趣社區，Cy表示第y類興趣社區。之后，根據圖8-1 中物理連接關系重組興趣社區，得到Cg1、Cg2、Cr1、Cr2、Cr3、Cy1和Cy2。

粒子更新速度加上虛擬力的調整后粒子速度能夠及時調整,避免了陷入局部最優,既具有較好的全局搜索能力,又具有較好的局部搜索能力。

4.3 基于時變特性的動態興趣社區構建

假設興趣社區在3 個時間狀態之間相互轉換，這3個時間狀態分別是初始狀態、遷移狀態和空狀態（Null）。具有時變特性的動態興趣社區構建過程如下。首先定義2 個狀態矩陣T和S，如式(3)所示。

其中，T表示社區的狀態轉移時間矩陣，矩陣中的元素tij表示社區從狀態i到狀態j的轉移時間；S是布爾矩陣，表示社區是否遷移成功。當α-tij≥0時，S中的元素為1，其物理意義為社區從狀態i成功地遷移到了狀態j；否則，為0，其物理意義是社區仍然滯留在狀態i。

那么，在α單位時間（單位時間可以是小時等）之后，社區從狀態i到狀態j的轉移概率如式(4)所示。

其中，pij表示社區從狀態i到狀態j的轉移概率，的數值從S中獲得。

在α單位時間（單位時間可以是小時等）之后，社區從狀態i經過狀態r到狀態j的轉移概率如式(5)所示。

綜上，可以得到社區的狀態轉移概率的表達式如式(6)所示。

基于時變特性的興趣社區遷移如圖7 所示。在10:00 時，在實驗室構建了專業技術社區，在圖書館和宿舍分別構建了學習社區和綜合性社區，餐廳無社區形成。在12:00 時，學生和教職工進入餐廳，此時，綜合性社區在餐廳形成，之前2 h 所構建的興趣社區解散后進入空狀態。在22:00 時，學生和教職工回到宿舍休息，綜合性社區在宿舍區形成，之前的興趣社區解散后轉入安防社區，該社區用于保護公共財產安全。

4.4 基于動態興趣社區的查詢路由算法

基于興趣社區的查詢路由算法TIMER 包括興趣社區間的查詢和興趣社區內的查詢。興趣社區內的查詢采用經典的Binary SW 算法。下面重點闡述基于節點移動軌跡相似度的興趣社區間查詢算法。

定義3當前位置。節點i的當前位置用(xi,yi,ti)表示，其中ix和yi分別表示節點i的經緯度坐標，ti表示當前的時刻。

定義4滯留時間和滯留區域

滯留時間Tp等于(tl-ts)，其中ts為節點進入某區域的時間，tl為節點離開某區域的時間。

滯留區域為節點在滯留時間Tp內的活動范圍max{d(p,q)}。其中，p(xi,yi,ti)為節點在ti(ts≤ti≤tl)時刻的位置，q(xj,yj,tj)為節點在tj(ts≤tj≤tl)的位置，d(p,q)表示p、q兩點之間的歐幾里得距離。

定義5移動軌跡

節點的移動軌跡是由節點所經過的滯留位置所組成，如式(7)和式(8)所示。

其中,Tr表示節點的移動軌跡；Ai為節點所經過的滯留區域i；Tp(i)為節點在區域Ai的滯留時間；δi為權重，表示區域Ai對節點i的重要性；ηi表示節點訪問區域Ai的頻度。

圖7 基于時變特性的興趣社區遷移示意

接下來，按照區域對節點的重要性更新節點的移動軌跡序列。2 個節點移動軌跡中所包含的相同滯留區域越多，表明2 個節點的興趣度越相近，將興趣度相近且頻繁游離于不同興趣社區的節點作為大使節點輔助消息轉發。基于節點移動軌跡相似度的興趣社區間查詢算法如算法1 所示。

算法1 的執行如圖8 所示，興趣社區1 中的請求節點R在其查詢消息無響應時，找到2 個大使節點N1和N2。之后，通過比較與大使節點N1和N2的移動軌跡相似度后發現自身與節點N2的移動軌跡相似度更高，于是將查詢消息發送給大使節點N2，N2將查詢消息攜帶到興趣社區3 中，采用Binary SW 算法進行轉發，最終查詢消息達到了響應節點H。

算法1基于節點移動軌跡相似度興趣社區間查詢路由算法

圖8 基于移動軌跡相似度的查詢算法

TIMER 時間復雜度的分析如下。假設網絡場景中有m個位置，每個查詢節點產生L份查詢消息拷貝。社區內部采用Binary SW 算法，該算法的時間復雜度為O(n+logL)，其中L是常數，因此Binary SW 算法時間復雜度為O(n)。算法1 中移動軌跡生成和大使節點選擇代碼段的時間復雜度是O(mn)；請求節點計算最優大使節點的最壞情況下時間復雜度為O(nlogn)。綜上，TIMER 的執行時間復雜度為O(2mn+nlogn+n)。由于2mn+nlogn+n≤2(m+1)nlogn，而m是 常 數，因 此，TIMER的時間復雜度是O(nlogn)。

5 TIMER 性能評估

5.1 仿真環境和參數設置

本文選用隨機網絡仿真器ONE (opportunistic network environment)作為算法性能評估的仿真平臺。仿真場景地圖為江蘇大學校園一角，利用OPEN JUMP 采集相應的節點移動軌跡，在仿真程序中設定了4 個興趣社區，即嵌入式開發興趣社區、電氣工程興趣社區、化學興趣社區和理學興趣社區。TIMER 評估的實驗參數配置如表1 所示，仿真模擬場景如圖9 所示。

表1 實驗參數配置

圖9 模擬仿真實驗場景

5.2 實驗結果分析

在實驗評估中，將本文提出的TIMER 與同類型的查詢消息路由算法EPIDEMIC(EPIDEMIC routing for partially connected Ad Hoc network)[3]、PRoPHET(probabilistic routing protocol using history of encounters and transitivity)[5]和ICR(interest community routing for opportunistic network)[7]在消息投遞成功率、平均查詢時延、查詢消息的平均跳數和查詢成功的系統開銷這4 個方面進行比較，具體定義如下。

定義6消息投遞成功率是仿真期間成功傳輸的消息數占總消息數的比例。

定義7平均查詢時延是從消息產生到消息響應的平均時延。

定義8成功查詢的平均跳數是指從消息產生到消息響應所經過的平均節點數。

定義9查詢成功的系統開銷是指一次成功查詢所需要產生的查詢消息的平均副本數。

圖10～圖13 的橫坐標為交互次數，它指的是仿真期間節點所建立的連接數統計。本文將EPIDEMIC 方案作為性能評估的基準[5,7]。

1)消息投遞成功率

如圖10 所示，隨著交互次數的增多，EPIDEMIC、PRoPHET、ICR 和TIMER 這4 種算法的消息投遞成功率均逐漸增加，隨后趨于穩定。這是因為消息投遞成功率是建立在節點交互次數的基礎上，交互次數越多，投遞成功的概率就越高。盡管ICR 比PRoPHET的性能略好，但是與EPIDEMIC 的性能尚有差距。這是由于PRoPHET 為了控制系統中的消息副本數，采用了概率轉發，因此實際的投遞次數低于節點交互的次數。盡管ICR 采用了基于興趣社區的消息投遞方法，但是所構建的興趣社區是靜態的，無法適應移動網絡實際的變化。TIMER 提出了時變社區的概念，時變社區較好地適應了網絡拓撲的變化。此外，TIMER 也充分利用了節點的交互次數。TIMER 收斂后的消息投遞成功率在90%左右。

圖10 消息投遞成功率評估

圖11 平均查詢時延評估

2)平均查詢時延

平均查詢時延是消息路由算法設計的一個重要衡量指標，這是因為平均查詢時延越長，查詢消息在網絡中的副本數越多，在節點緩存中存放的時間越長。因此，降低平均查詢時間對消息路由算法而言是十分必要的。如圖11 所示，EPIDEMIC 的平均查詢時間最低，這是因為EPIDEMIC 方法產生了多個查詢消息副本，平均查詢時延則是統計從消息產生到消息響應的時間，因此實際上它是將多副本查詢消息中最短的查詢時間作為本次的查詢時延。TIMER 所構建的時變社區是有效的，查詢節點總能通過一跳或多跳檢索到響應節點。ICR 比TIMER的平均查詢時延要差，但是比PRoPHET 的平均查詢時延要好，這說明PRoPHET 通過節點的歷史通信記錄進行概率計算的方法盡管控制了消息副本數量的增長，但是卻犧牲了節點的查詢時延，與EPIDEMIC方法相比，多了2 000 s 的時延。ICR 與EPIDEMIC相比，多了1 000 s 的時延。TIMER 與EPIDEMIC相比，僅多了幾十秒到百秒的時延。

3)成功查詢平均跳數

成功查詢的平均跳數與平均查詢時延都是評估算法性能的指標，這2 個評估指標很相近，所不同的是查詢時延表示的是數據的傳輸時間，而平均跳數是一次成功查詢跳過的節點數。如圖12 所示，這個實驗結果和上面評估的平均查詢時延結果是一致的。EPIDEMIC 方法一次成功查詢所需的平均跳數是2.28，TIMER 算法一次成功查詢所需的平均跳數是2.68，ICR 算法一次成功查詢所需的平均跳數是4.25，PRoPHET方法一次成功查詢所需的平均跳數是5.24。需要說明的是，在交互次數低于5×105時，平均跳數會增加，這種情況發生在網絡中節點所處的位置比較分散，此時節點只能通過移動尋找未來與其他節點相遇的機會，從而增加投遞成功的機率。

圖12 成功查詢的平均跳數對比

4)查詢成功的系統開銷

各種消息路由算法一次成功查詢所需要產生的副本數，如圖13 所示。EPIDEMIC 方法的副本數最高，達到了平均使用23 條副本消息才能完成一次成功查詢。其他幾種消息路由算法都有針對性地控制了查詢消息副本的數量，基本控制在5 條副本以下。TIMER 算法所需要的查詢副本數最低，基本通過2～3 條消息副本就可以發現資源響應節點。這就表明本文提出的TIMER 算法在控制消息副本數增長方面效果最好。

綜合對以上性能指標的實驗評估，表明TIMER算法所構建的興趣社區是有效的，節點基本上在興趣社區內就可以發現請求響應節點。即使社區內不存在請求響應節點，請求消息也可通過最優的大使節點將查詢消息傳遞給當前興趣社區之外的請求響應節點。因此，TIMER 算法具有一定的可擴展性，適當地擴大了搜索范圍，提高了查詢消息轉發的成功率。

圖13 成功查詢所需的系統開銷評估

6 結束語

本文以高校校園為應用場景，研究校園環境下的機會社交網絡，并在此基礎上提出一種基于時變興趣社區的查詢消息路由算法TIMER。本文對與科研工作場景相關的2 個重要移動社交數據集(copelabs/usense 和upb/hyccups)進行了分析，通過分析發現這些移動節點具有一定的時空關聯性和規律性。基于這一發現，本文提出了基于社會親密度的興趣社區構建方法和時變興趣社區模型，并在此基礎上給出了社區內和社區間的查詢路由算法。對算法的理論分析表明，TIMER 算法的時間復雜度為O(nlogn)。在仿真實驗平臺上，將TIMER 算法與同類算法在消息投遞成功率、平均查詢時延、成功查詢平均跳數和查詢成功的系統開銷四方面進行比較，實驗結果表明TIMER算法完成一次成功查詢所需的查詢時延、平均跳數、平均跳數低于PRoPHET 和ICR 查詢消息路由算法，消息投遞成功率和可擴展性優于PRoPHET 和ICR 查詢消息路由算法，與基準算法EPIDEMIC 在數值上接近。然而，本文提出的TIMER 算法在查詢消息副本數上要明顯優于基準算法EPIDEMIC。綜上，TIMER算法在網絡規模和消息傳播數據量增大時各方面綜合表現是最優的。下一步工作是針對機會社交網絡中存在自私節點情況下的消息路由算法研究。