機會移動社交網絡中基于群組構造的數據分發機制

李 婕 洪 韜 王興偉 黃 敏 郭 靜

1(東北大學計算機科學與工程學院 沈陽 110819) 2(東北大學信息科學與工程學院 沈陽 110819)

隨著移動互聯網的迅速發展，人們通過移動智能終端獲取大量各種形式的網絡資源，而目前移動設備接入互聯網的形式主要是通過基站，這樣就大大增加了基站的流量負載，同時也增加了通信運營商對基站設備資金和技術的投入.在基礎設施部署困難或者不完善的場景中，移動設備之間的通信就變得極為困難.針對以上問題，一些特殊的網絡已被提出，如無線傳感器網絡、移動自組織網絡[1]等.機會移動社交網絡(opportunistic mobile social networks, OMSNs)[2]作為結合網絡節點移動屬性和社會屬性的特殊移動自組織網絡，能夠很好地契合特殊場景下的網絡環境，卸載部分基站的流量負載，近年來機會移動社交網絡成為研究學者們關注的熱點.

機會移動社交網絡利用網絡節點的移動性帶來的接觸機會實現近距離的無線數據傳輸，其具有非持續性連接、時延長、能耗大等網絡傳輸特性，使機會移動社交網絡的應用得到一定程度的限制，目前機會移動社交網絡的研究面臨的挑戰性問題有：如何尋找到一條中斷容忍、低時延、低能耗的數據傳輸路徑；如何充分利用節點的移動性和社會性特征提高網絡性能；如何避免節點自私性而增強網絡整體性能.針對這些挑戰性問題，本文提出了基于群組構造的數據分發機制(data dissemination mechanism based on group structure, DDMGS)，該機制主要有4方面貢獻：

1) 充分挖掘機會移動社交網絡中節點的移動特性和社會關系特性，確定節點重要性、興趣相似度和通信關系緊密度，構建節點關系度量模型；

2) 由于基于位置關系的拓撲結構具有周期穩定性，基于興趣關系的拓撲結構具有長期穩定性，而基于通信關系的拓撲結構具有動態性，因此依據這3種行為屬性關系構成的網絡拓撲特征設計了3種群組構造算法；

3) 基于不同的行為屬性關系構成的群組結構設計了數據分發機制，引入節點緩存區管理機制提高傳輸性能，引入合作博弈理論來規避節點的自私行為，降低傳輸能耗，促進節點協作，提高整體網絡性能；

4) 驗證并評估了DDMGS的性能，與機會移動社交網絡中的主要數據傳輸算法在消息傳輸成功率、平均傳輸時延、平均跳數、數據分發開銷比率等性能評價指標上進行了對比和分析，驗證了DDMGS的有效性.

1 相關工作

目前，數據分發機制按照消息傳輸方式的不同大致分為四大類：基于洪泛的數據分發機制[3-6]、基于上下文感知的數據分發機制[7-9]、基于編碼的數據分發機制[10]、基于群組的數據分發機制[11-14].由于機會移動社交網絡的節點具有社會屬性并且會自然地形成各種群組，所以充分利用節點的社會特性便成了機會移動社交網絡的重要研究內容之一.文獻[11-12]分別提出了經典的數據分發機制SimBet和Bubble Rap，這2種算法均考慮到節點的社會性.隨后很多基于群組的數據分發機制相繼被提出.文獻[13]考慮到機會移動社交網絡拓撲的動態性，提出在機會移動社交網絡中存在一個嵌套的核心外圍層次結構(nested core periphery hierarchy, NCPH)，即加權度大的一些節點組成網絡核心，同時網絡周邊由加權度小且不活躍的一些節點組成，當外圍節點被迭代移除時，NCPH仍被保留，并利用網絡的這種特征提出一種上下路由協議，即路由分為上傳階段和下載階段，該路由協議在數據傳送延遲和比率方面實現了優越的性能，并且具有較低的轉發成本.文獻[14]中作者提出一種基于社區和社交性的組播數據分發機制，引入動態社交特征的概念來捕獲節點的動態連接行為，考慮了更多的節點之間的社會關系，采用社區結構來為每個節點選擇最佳的中繼節點從而提高多播機制的性能.該文中提出了2種基于社區和社交性的多播算法：第1種是基于社區及社會特征的組播算法Multi-CSDO(community and social feature-based multicast involving destination nodes only)，它只涉及到社區發現中的目標節點；第2種被稱為Multi-CSDR(community and social feature-based multicast involving destination nodes and relay candidates)，它涉及社區發現中的目標節點和候選中繼節點.文獻[15]關注于群組的移動性和群組外形，提出一種算法可以根據若干移動設備的移動性以及它們所組成的外形高概率地判斷這些移動設備是否是屬于一個群組.文獻[16]是有關D2D通信的研究，它通過判斷某一設備進組是否會提升本組吞吐量來進行設備篩選，完成群組構造，提升了D2D通信的吞吐量等性能指標.文獻[17] 考慮OMSNs 中節點間存在周期性相遇的特點設計了基于節點周期性相遇的數據分發機制，并通過實驗對比驗證了相對于傳統DTN路由機制在數據分發成功率上的提升.

由此可以看出：在機會移動社交網絡中考慮節點的社會屬性和群組結構能夠有效地提高數據分發效率.但目前的研究存在不足有：沒有考慮節點的多方面社會屬性，例如沒有充分考慮節點的移動軌跡對數據傳輸的影響；并且未考慮由節點不同的社會關系構成的網絡拓撲是有區別的，所以導致群組結構單一，群組劃分與實際情況差距較大；未考慮由于節點自身的資源受限而出現的自私行為.因此，本文提出的基于群組構造的數據分發機制，根據節點的移動性特征、節點重要性、節點間興趣相似度和節點間通信關系緊密度等多維社會屬性設計了不同的群組構造機制，并引入合作博弈理論，加強節點之間的協作，通過與傳統路由機制的對比實驗論證了本文所提出的數據分發機制的可行性和有效性.

2 網絡模型

由于機會移動社交網絡的拓撲結構是動態變化的，所以每個時刻網絡的拓撲都是不同的，為了對節點移動模型進行直觀的描述，本文將機會移動社交網絡某時刻的“快照”作為網絡模型.將機會移動社交網絡中的用戶抽象為節點，其在網絡中可以自由移動；節點可以選擇和其通信范圍內的任意節點進行通信，或者拒絕通信；由于節點的能量存儲和緩存空間都是有限的，所以網絡在某一時刻會存在拒絕轉發數據的節點；節點之間采用Bluetooth，WiFi直連通信等近距離通信方式進行數據傳輸，節點只有處于相互通信范圍內時才能進行通信，本文假設各節點通信半徑相同.用戶間的聯系抽象為邊，即將網絡建模為圖G(V,E)，其中V={v1,v2,…,vn}表示用戶的標識集合，E={e1,e2,…,el}表示用戶間的關系.如圖1所示，如果2節點間存在興趣或者通信等關系，則2節點間存在1條無向邊，邊上的權重w(i,j)代表節點i和j之間某種關系的緊密程度.

Fig. 1 Topology of the opportunistic mobile social network圖1 機會移動社交網絡拓撲

3 算法設計

本文根據戶節點的位置關系、興趣和通信關系等移動特征和社會特征對節點重要性、興趣相似度和通信關系緊密度進行定義和建立度量模型，基于3種節點關系度量對節點進行群組構造.在構造群組基礎上，利用節點的群組屬性，對節點之間的合作博弈建模，引入緩存管理機制，設計基于群組結構的數據分發機制.

3.1 基于位置關系的群組構造方法

1) 移動模型

在OMSNs中，節點的移動模型影響節點在數據傳輸過程中的時延和成功率等性能.目前為止，經典的隨機移動模型，由于其節點的速度和移動方向都是隨機的，不太適用于機會移動社交網絡.文獻[18]提出了一種基于校園社區的移動模型(campus based mobility model, CBMM)，該模型分析了用戶的日常行為特征，重點關注節點之間的間隔聯系時間和聯系時長的分布，很好地呈現了節點的社會特征.本文將該移動模型與基于地圖最短路徑的移動模型(shortest-path map based movement, SPMBM)結合，給出基于地圖的工作移動模型(map based working day movement, MBWDM).

2) 節點重要性度量

人們的移動不是隨機的，而是有規律的，并且活動范圍相對固定，例如上班族工作日規律地從家到公司，大學生在校園內按課程表作息活動，公交車每天總是在同一條路線上行駛，出租車司機總喜歡去客流量多的地方載客等.在機會移動社交網絡中，我們將節點的相遇定義為2個節點移動至對方的通信范圍內.只有相遇的節點才能進行通信，所以節點在機會網絡中所處的位置決定了其承擔通信任務的重要性.當用戶節點處于聚集節點較多的位置時，能檢測到較多節點發出的消息，那么該用戶節點可以作為其他節點的中繼節點進行數據的轉發；反之，當其處于節點稀疏的位置時，能檢測到的用戶信息較少，能夠承擔通信任務的重要性減弱.因此，我們根據節點接收到的信號量來定義節點的重要性.

定義1.節點的重要性.節點在單位時間內接收到的檢測信號量，表示為

(1)

其中，signal(τ,i)是節點i在時刻τ檢測到的信號數量.

3) 基于位置因素的群組構造方法

在本群組構造發方法中，基于節點的移動軌跡，確定節點之間的位置關系，在同一時間片內處于相同或相近的地理位置時，節點相遇的機會大，從而更容易形成以地理位置為特征的群組結構，由于節點的移動具有周期性規律，因此基于位置屬性的群組具有周期穩定性，其構造方法分為2個階段：引導階段和演化階段.

算法1.基于節點位置關系的群組構造算法.

1) 引導階段

輸入：n個節點;

輸出：m個群組.

① 選擇節點重要性較大的前m個節點作為初始節點，每個節點有一個唯一的群組ID號，假設群組的ID號為1～m；

② 在所有節點的移動過程中，將沒有群組歸屬節點加入到與其首次相遇的節點所屬的群組中，直到每個節點都有其唯一的群組ID號.

2) 演化階段

輸入：n個節點、m個群組;

輸出：每個節點所屬的群組ID號.

① 在節點移動過程中，每個節點對自己與其他節點的相遇次數進行計數，將此信息保存在節點的隸屬參數APS中，節點i的APS表示為

APS=(aps1i,aps2i,…,apsmi)，

其中，apsji表示節點i和群組Cj中節點的相遇次數；

3.2 基于興趣的群組構造方法

興趣是節點具有的重要社會屬性之一，也是相對穩定的行為屬性之一，因此基于用戶興趣相似度的網絡拓撲結構具有相對長期穩定性.本文設計了一種適用于靜態拓撲結構的基于興趣的群組構造算法，該算法將具有相同或相似的興趣愛好的用戶進行聚類，得到一種按興趣劃分的群組結構，當用戶請求感興趣的內容時，請求消息將在其所屬群組內進行轉發與傳播，使請求成功率得到極大的提高.

1) 興趣相似度度量

本文用興趣相似度來度量用戶之間在興趣愛好方面的相似程度.移動節點的興趣資源都會以文件的形式存儲在移動設備，我們采用文檔聚類技術對存儲在節點中的數據進行聚類來模仿節點的興趣.文檔fi的文件向量即節點的興趣矩陣表示為

其中，tk表示關鍵字，關鍵字可以是音樂、電影、體育、經濟等等;witk表示關鍵字相應的權重，witk的計算過程為

witk=1+lnntk，

(2)

其中，ntk表示關鍵字tk出現的次數.為了將witk的范圍控制在[0,1]之間，其標準化為

(3)

定義2.興趣相似度.節點i和節點j興趣向量中相同的關鍵字以及對應的權重為

(4)

其中，Y(tk,tl)=1，僅當tk=tl時，否則為0，其中L為興趣文檔長度常量.

2) 基于興趣的群組構造方法

團(clique)[19]的概念被引入到該群則構造算法中.

定義3.團. 團體的一個子集形成一個團，該團由3個或更多個成員組成，每個成員都與團的其他所有成員具有對稱關系.

基于興趣的群組構建算法分為3個步驟：團的構造、互相重合團的融合以及孤立節點的歸屬.

1) 團的構造.對于網絡拓撲G，遍歷所有的節點，對每一個節點V找出它對應的所有相連節點的集合Vn.判斷該節點集合是否可以滿足完全圖的條件，如果可以，則將該節點集合連同節點V就可看作本網絡拓撲中的一個團.

2) 團的融合.如果團K和團L擁有共同節點，則首先判斷團K和團L的大小.如果團L較小，則判斷去除團K和團L的共同節點，剩余節點是否仍然成團，如果仍然成團則將團L拆分為更小的團,如果不成團，則將團L直接加入到團K中;如果團K和團L節點數目相同，則根據先前提出的興趣相似度判斷共同節點應屬于哪個團，而剩下節點的歸屬問題和團L較小時的情況相同.

3) 孤立節點的歸屬.在網絡拓撲G中，經過團的構造和融合，如果還存在孤立的節點，則根據孤立節點與它相連的團的興趣相似度的大小，把這些孤立節點歸屬到不同的團中.

算法2.基于興趣的群組構造算法.

輸入：具有n個節點、m條邊的興趣關系網絡G(V,E,w)，邊權值的閾值γ；

輸出：群組集合GS.

① 初始化群組集合GS←?；

② FORV中每一個頂點vdo

③ 找到v的所有相鄰頂點，記作集合Vn；

④ IFVn=?

⑤ CONTINUE；

⑥ END IF

⑧ IF {{v}+Vn}?GS

⑨GS←{{v}+Vn}；

⑩ CONTINUE；

3.3 基于通信關系的群組構造方法

在移動用戶的通信行為中，通話時間和通話次數是最能直接表達通信關系緊密程度的度量指標.但是，通信關系緊密度又是一個隨社會關系變化的量，因為人們在社會中的身份或地位發生了變化，會導致與其他人的通信關系發生變化，這種變化或增強或減弱人們之間的通信關系，所以本文考慮隨時間變化的通信關系的衰減度.在計算通信關系緊密度時需要對時間進行周期劃分，并且通過分析節點在網絡中的重要程度，以及節點之間的周期通信關系和衰減函數計算得到通信關系緊密度.

1) 通信關系緊密度度量

定義4.社交中心性(social centrality).社交中心性代表了網絡中節點的相對重要程度，我們采用Freeman[20]的度中心性來計算社交中心性.節點A的社交中心性可以定義為

(5)

其中，dAB(τ)=1當且僅當節點A和節點B在時刻τ有通信行為，N是網絡中節點的個數.

定義5.衰減函數(decay).衰減函數取決于節點在社交網絡中的重要程度以及與其他節點的社交時間，當2個節點才開始建立通信關系且2個節點的社交性強時，其關系衰減度較小.衰減函數的計算為

(6)

其中，τ是節點A和節點B有通信行為的時刻，T是周期.可以看出，當通信行為發生時刻越近，且社交中心性越大時，衰減函數的值越大.

定義6.通信關系(communication relationship).周期通信關系代表一個周期內節點之間通話時間和通話次數的關系，其計算公式為

(7)

其中，v(A,B,T)，vt(A,B,T)表示在周期T內用戶A和B的通話時間、通話次數，v(A,T)，vt(A,T)和v(B,T)，vt(B,T)分別表示在周期T內用戶A和用戶B的總通話時間、總通話次數.

定義7.通信關系緊密度(communication tight-ness).綜合衰減函數和周期通信關系得到通信關系緊密度，表示為

(8)

其中，XAB(τ)=1當且僅當節點A和節點B在時刻τ有通信行為，或τ=T時；否則XAB(τ)=0.CR(A,B,T)是上個周期的周期通信關系，這里我們使用上個周期的周期通信關系來計算本周期的通信關系緊密度.

本文采用增量式的動態群組構造算法，即計算本周期的群組結構時是基于上個周期的群組結構進行調整，避免重復計算.

2) 基于通信關系的群組構造算法

① 群組核.群組內部存在的穩定群組核心節點或群組核心節點的集合稱為群組核，群組核之間沒有重疊部分.

② 單獨節點.度為0的節點集合.

③ 邊緣節點.群組核以及單獨節點外的節點或節點集合稱為邊緣節點.邊緣節點之間可能存在一條或多條邊，但是它們不能形成群組核或加入到已存在的其他群組核中.

④ 移動群組.移動網絡中一組內部緊密聯系的用戶群稱為移動群組.移動群組由群組核和滿足條件的邊緣節點組成.

⑤ 節點與群組的相似度.節點與群組的相似度是判斷節點是否可以加入該群組的條件，本文對余弦相似度進行改進，可以計算有權網絡中節點與群組的相似度，即：

(9)

其中，N(u)代表節點u的鄰接節點集合，N(K)代表群組K的節點集合，N(u)∩N(K)是節點u的鄰接節點集合與群組K的節點集合的交集.

⑥G(V,E,w).G表示有權無向圖，V是G中節點的集合，E是G中邊的集合，w(u,v)表示E中邊(u,v)的權重.

Gt(Vt,Et,wt)：時間片t的網絡圖快照.

C1,C2,…,Ct,…：隨時間變化的群組結構.

⑦ ΔG. ΔG表示圖增量，有4種情況:節點加入、節點移除、邊加入、邊移除.

算法3.基于通信關系的群組構造算法.

1) 初始群組構造

輸入：通信關系網絡圖G(V,E,w)、邊介數閾值α、節點度閾值d；

① 對網絡進行預處理，設定度為d的閾值，選出度高于d的節點；

② 采用設定邊介數閾值的GN算法，將從②中得到的少量節點中挖掘出群組核；

③ 遍歷網絡中除群組核外的其他節點，計算這些節點與群組核的相似度，將該節點歸入到與之相似度最大的群組核中，對沒有與群組核直接相連的節點，則計算與其相連的移動群組的相似度，將其加入到與之相似度最大的群組中；

④ 進一步對③結果進行優化，遍歷所有其他節點，計算節點與群組相似度，如果發現節點所歸屬的群組不是與其相似度最大的群組，則重新將其劃分到正確的群組中，得到最終的群組結構.

2) 每個時間片群組的動態變化執行算法

輸入：網絡拓撲圖快照Gt(Vt,Et,wt)、圖增量ΔG.

輸出：時間片t+1的網絡群組結構Ct+1.

① 當新節點加入時，有2種情況：如果是單獨節點，則將該節點單獨劃分為一個群組；如果是邊緣節點，則根據該邊緣節點與其相連移動群組的相似度，并將其加入到相似度值為最大的一個移動群組中.

② 當舊節點移除時，有2種情況：如果移除的節點是單獨節點，則保持原有的群組結構；如果移除的節點是邊緣節點，那么該節點的移除將影響其相鄰節點的歸屬群組，這是個連鎖反應，所以需要迭代計算其所影響到的節點，直到所有被影響的節點處于穩定的狀態.

③ 當新的邊加入時，有2種情況：如果新加入的邊的2個頂點位于同一個群組，則保持原群組結構；如果新加入的邊的2個頂點位于不同的群組，則重新計算這2個節點與其相連群組的相似度，將其劃分到相似度最大的群組.

④ 當舊的邊移除時，有2種情況：如果舊的邊的2個頂點位于不同的群組，則保持原群組結構；如果舊的邊的2個頂點位于同一個群組，則重新計算這2個節點與其相連群組的相似度，將其劃分到相似度最大的群組.

3) 算法復雜性分析

本文設計3種群組構造算法：基于位置關系的群組構造算法采用動態的分布式群組構造算法、基于興趣的群組構造算法采用靜態社區劃分方法、基于通信關系的群組構造算法采用增量式動態群組構造算法，前兩種構造的群組相比基于通信關系的群組構造具有相對高的穩定性，算法復雜度低于增量式動態群組構造算法.

增量式動態群組構造算法認為網絡拓撲的變化是平滑的，當計算當前網絡的群組結構時，在上個時間片的群組結構上進行調整，所以計算速度加快，時間復雜度降低.該算法在同一個群組內增加邊和刪除不同群組之間的邊時，算法復雜度為O(1)；在不同群組之間增加邊和在同一個群組內刪除邊時，算法較復雜，最壞的情況下時間復雜度是O(n)，但群組的調整次數要小于節點個數n，所以一般情況下的時間復雜度小于O(n).

3.4 緩存區管理機制

在機會移動社交網絡中，消息傳輸采用的是“存儲-攜帶-轉發”的方式，而移動終端設備的緩存空間是有限的，為了減少網路開銷和緩存壓力，保證消息的交付率，需要對節點的緩存空間進行管理.

節點緩存空間的管理主要依據消息的優先級和生存期(time to live，TTL).根據節點之間群組重合度，為每個節點分配轉發消息的優先級，因為群組結構是動態變化的，所以在時段t群組重合度為

(10)

每個節點用一個隊列存儲消息列表，該列表記錄消息的基本信息，如消息ID號、消息優先級和TTL.當節點u接收消息時，對優先級是0的消息不存儲，對優先級不為0的消息，如果其緩存區足夠則直接存儲，如果其緩存區已滿需要遍歷消息列表刪除優先級低的消息，如果消息的優先級相同則刪除TTL較小的消息.節點每隔一段時間需要刪除TTL為0的消息，完成緩沖區的清理工作.

3.5 基于群組構造的數據分發機制

本文設計的基于群組構造的數據分發機制(data distribution mechanism based on group structure， DDMGS)采用單副本模型，在選擇下一跳節點時，不僅考慮節點所屬的群組之間的關系，還引入博弈論，促使節點協作轉發.

3.5.1 基于合作博弈的問題建模

1) 博弈模型的定義為

① 局中人N.N={1,2,…，n},表示機會移動社交網絡中的所有節點.

② 策略集合S.S={D,F}表示每個節點可以采取的行動集合，Si表示節點i的決策，Si=D表示拒絕，Si=F表示轉發.

③P.P={pij}表示節點i的支付函數.

2) 支付函數pij包含3部分：群組重合度、合作能力、聲譽度.

① 群組重合度

群組重合度θij(t)是節點之間的所屬群組的相似關系，重合度越高節點越相似，群組重合度θij(t)利用式(10)計算.

② 合作能力

合作能力φij(t)是關于電量的函數，定義為

(11)

其中，Eij(t)表示節點i和節點j之間在時段t轉發數據包所要花費的電量，Erem表示節點i或節點j的剩余電量.可以看出，電量隨著時間的流逝越來越低，節點的合作能力也越來越低.

③ 聲譽度

聲譽度φij(t)是用節點在某時間間隔t內的轉發消息數、產生消息數和接收消息數來度量，定義為

(12)

其中，Fij(t)表示節點i和節點j在時段t轉發的消息數，Gij(t)表示節點i和節點j在時段t產生的消息數，Rij(t)表示節點i和節點j在時段t接受的消息數.

節點i在時段t支付的表達式為

pij(t)=αθij(t)+βφij(t)+γφij(t)，

(13)

其中，α，β，γ是每部分的權系數，且α+β+γ=1，這些系數在實驗時可以調整.

3) 模型策略

對于任一節點，s(θij(t))=0并且s(φij(t))=0代表拒絕合作，s(θij(t))>0并且s(φij(t))>0代表合作.

本文令Xij(t)代表其他節點轉發本節點的消息給本節點帶來的收益，Cij(t)代表本節點為其他節點轉發消息所付出的代價，實質上Xij(t)來自節點合作后在聲譽上的收益，Cij(t)來自節點合作后電量的損失.根據博弈理論，當節點選擇合作時獲得的收益為Xij(t)-Cij(t)，節點拒絕合作時收益為-Xij(t),為激勵節點選擇合作，需要Xij(t)-Cij(t)>-Xij(t)，為了簡化實現，通過一次放縮，當Xij(t)-Cij(t)>0時能夠對節點進行一定的激勵.再一次放縮，當該節點此次合作的收益大于上次合作的收益時節點選擇合作，如式(13)所示，我們假定2個時間間隔的組重合度一樣，那么通過整理可以得到β，γ之間的關系以確保節點選擇合作，如式(14)所示.并且我們定義一個信譽度的閾值，并在仿真過程中隨時間提高該閾值的值，當上一跳節點的聲譽值低于該閾值，本節點將拒絕轉發上一跳的數據.這樣使得那些拒絕合作的節點逐漸從網絡中隔離出來，通過這樣的過程達到激勵節點合作的目的.

αθij(t)+βφij(t)+γφij(t)>
αθij(t-1)+βφij(t-1)+γφij(t-1) ，

(14)

(15)

3.5.2 基于群組構造的數據分發算法

本文設計的基于群組構造的數據分發機制(data dissemination mechanism based on group structure， DDMGS)采用單副本模型，在選擇下一跳節點時，不僅考慮節點所屬群組之間的關系，而且引入博弈論，促使節點協作轉發.具體的算法過程如算法4所示：

算法4.基于群組構造的數據分發機制.

輸入：網絡拓撲G(V,E)、節點i、聲譽度閾值l；

輸出：選擇的下一跳節點.

① 新節點i的信息：完成對消息的處理，清理緩存；

② IF 節點i的緩沖區沒有要轉發的消息

③ RETURN；

④ END IF

⑤ 查找緩沖區，獲得節點i中所有的消息列表messages；

⑥ FORmsg∈messages

⑦ IF 節點i的緩沖區中有能夠直接投遞給目的節點的消息

⑧ IF其上一跳節點j的聲譽度φj

⑨ ELSE

⑩ 將消息直接發送給相遇節點；

4 性能評價

本文仿真實現整個過程是基于機會網絡(opportunistic network environment, ONE)模擬器，在Eclipse平臺上采用Java語言編寫實現.

本文使用的仿真場景是ONE模擬器中的Helsinki城市街道的場景，一共有200個移動節點，其中行人節點個數是120個，小汽車節點個數是60個，公共汽車節點個數是20個，并使用ONE自帶的MBWDM和RWP移動模型去模擬這些節點的移動.

對ONE模擬器中的DTNHost類進行擴充，DTNHost類主要是對通信節點的描述，比如節點興趣向量的定義和節點電量的定義等.比如電量的設置，我們使用整數類型表示，行人節點的最大電量為100，小汽車節點的最大電量為500，公共汽車節點的最大電量為1 000，在節點初始化時這些節點的電量隨機取值，根據時間和數據的傳輸量更新節點的電量信息；而對于節點的興趣向量，為了仿真方便，在節點初始化時，每個節點生成一個包括音樂、電影和體育興趣點的興趣向量，每個興趣點的權值在0～1之間隨機生成.具體的參數設置如表1所示:

Table 1 The Setting of Simulation Parameter

本文在不同的消息產生時間間隔下，從消息傳輸成功率、平均傳輸時延、平均跳數和數據分發開銷比率4種性能指標上，將本文提出的基于群組構造的數據分發機制(DDMGS)與4種基準算法：Direct Delivery Routing路由算法、SimBet Routing路由算法、Prophet Routing路由算法和Epidemic路由算法進行對比.

1) 消息傳輸成功率

消息傳輸成功率是機會移動社交網絡性能評價中較為重要的一項指標，直接體現了數據分發機制性能的好壞.具體結果如圖2所示：

Fig. 2 Message transmission success rate under different intervals of message generation圖2 不同消息產生間隔時間下的消息傳輸成功率

從圖2可以看出，Direct Delivery的消息傳輸成功率最低.而本文設計的算法DDMGS分析了節點的3種行為，并將這3種行為構成的網絡拓撲分別進行群組構造，當選擇下一跳節點時，利用所屬群組的重合度θij(t)來進行選擇，并且引進合作博弈理論來避免節點發生自私行為，為了提高整個網絡的收益促使節點之間合作從而極大提高消息交付率.SimBet，Prophet，Epidemic的消息傳輸成功率相差不大.

2) 平均端到端時延

由圖3可以看出，各算法的平均端到端時延都比較長，大概在5 000～7 000 s之間.Direct Delivery的延遲最長，這也是由機會移動社交網絡的特性和Direct Delivery的實現機制所導致的.Epidemic的路由時延最短，是因為其轉發機制的特點是遇到節點便轉發，所以數據包會比較快速地到達目的節點.Prophet的平均端到端時延略低于Direct Delivery的，但是也比其他算法要高，因為Prophet的平均跳數較高，所以時間主要消耗在節點對消息的處理上.本文設計的算法與SimBet算法的時延相差不大，兩者都是基于節點之間的社會關系，充分考慮了節點的行為屬性.

Fig. 3 Average end-to-end delay under differentintervals of message generation圖3 不同消息產生間隔時間下的平均端到端延遲

3) 平均跳數

通過平均跳數指標，可以直觀地看到消息路由所利用的中間媒介數量，具體結果如圖4所示：

Fig. 4 Average hop count under different intervals ofmessage generation圖4 不同消息產生間隔時間下的平均跳數

因為Direct Delivery的路由機制是消息生成節點遇到目的節點后直接交付，所以其跳數最少且始終為1，從圖4可以明顯看出.

Prophet的平均跳數最高，是因為Prophet在選擇下一跳節點時，根據其所有相遇節點為目的節點轉發的概率值，如果相遇節點為目的節點轉發的概率大于本節點，本節點就會選擇此相遇節點作為其下一跳節. Epidemic跳數要小一些，這是因為Epidemic是通過消息副本的擴散進行消息交付的，它的傳播速度更加迅速，其進行消息的擴散需要的跳數僅在2.7跳. SimBet在選擇下一跳節點時，會選擇節點中心度和相似度較高的節點作為下一跳，根據實驗SimBet 路由機制的平均跳數為3.7跳.

本文設計的DDMGS算法充分考慮了節點的移動軌跡行為、興趣行為和通信關系行為，所以在選擇下一跳節點時更具有目的性和針對性，其平均跳數接近Epidemic，為4.0跳.

4) 數據分發開銷比率

因為機會移動社交網絡中節點資源的有限性，所以數據分發開銷比率是機會移動社交網絡中最重要的性能評價指標之一，具體結果如圖5所示.在Direct Delivery中，消息的轉發就意味著交付給目的節點，所以其數據分發開銷比率恒為0.在Prophet中，從圖4和圖2可以看出：其平均跳數最高，而消息傳輸成功率與Epidemic和SimBet相比差不多，所以其數據分發開銷比率要高于Epidemic和SimBet.

Fig. 5 Data distribution overhead ratio under different intervals of message generation圖5 不同消息產生間隔時間下的數據分發開銷比率

5 結束語

本文在前人研究的基礎上，分別由用戶的移動軌跡、興趣愛好和通信關系對用戶進行群組構造，并在群組構造的基礎上設計數據分發機制.并考慮到節點會因為自身資源受限而出現的自私行為，引入合作博弈理論，加強節點之間的協作.

本文對所設計的數據分發機制進行了仿真實現，并對其性能進行了驗證.實驗結果表明：所設計的數據分發機制具有較好的性能，是可行且有效的.更好地利用用戶節點之間的社會關系來提高數據分發的性能，是我們下一步的研究和工作的重點.