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

?

基于兩階段聚類的機會社會網(wǎng)絡(luò)路由算法

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

(哈爾濱工程大學(xué)計算機科學(xué)與技術(shù)學(xué)院 哈爾濱 150001)

為提升機會社會網(wǎng)絡(luò)路由過程中消息投遞率、降低消息平均時延，對其消息轉(zhuǎn)發(fā)過程進(jìn)行了研究，提出一種基于兩階段聚類分析的機會社會網(wǎng)絡(luò)路由算法。以分組路由策略為基礎(chǔ)，通過兩階段聚類分析方法降低簇劃分過程對節(jié)點資源的需求，并分別為簇內(nèi)/間消息設(shè)計轉(zhuǎn)發(fā)策略，優(yōu)化了消息轉(zhuǎn)發(fā)與中繼節(jié)點選取的過程。此外，在聚類分析的過程中引入事件鏈分析的方法，深入挖掘節(jié)點間的內(nèi)在社會關(guān)聯(lián)，提高簇劃分的準(zhǔn)確性。仿真結(jié)果表明，在大規(guī)模復(fù)雜網(wǎng)絡(luò)環(huán)境中該算法能夠提高投遞率5%～10%，降低投遞時延10%以上，而在資源不足的情況下也能夠獲得接近80%的投遞率。

事件鏈; 聚類; 機會社會網(wǎng)絡(luò); 路由; 社會網(wǎng)絡(luò)分析

機會網(wǎng)絡(luò)(opportunity network)[1]是移動自組織網(wǎng)絡(luò)的演化，是一種缺乏持續(xù)端到端連接的新型網(wǎng)絡(luò)體系結(jié)構(gòu)，利用節(jié)點移動帶來的相遇機會實現(xiàn)信息傳遞。由于缺乏持續(xù)穩(wěn)定的端到端路徑，且延遲較高，故機會網(wǎng)絡(luò)采用存儲-攜帶-轉(zhuǎn)發(fā)形式的路由協(xié)議[2]。近年來，隨著大量低成本、具有短距離無線通信能力的移動設(shè)備的廣泛應(yīng)用，以人為載體的移動設(shè)備通過相遇機會獲得數(shù)據(jù)交換的情況逐漸增多。這種趨勢使得在不具備基礎(chǔ)網(wǎng)絡(luò)設(shè)施的情況下，移動設(shè)備間通過自組織網(wǎng)絡(luò)形式實現(xiàn)大規(guī)模數(shù)據(jù)通信成為可能[3]。同時，由于人類活動具有社會性，在由人攜帶的移動設(shè)備組成的機會社會網(wǎng)絡(luò)中，節(jié)點的移動符合人類的社會活動規(guī)律[4]，使得上述機會網(wǎng)絡(luò)中節(jié)點的行為具有社會網(wǎng)絡(luò)的特征，被稱為機會社會網(wǎng)絡(luò)(opportunistic social networks, OSN)[5]。與機會網(wǎng)絡(luò)的傳統(tǒng)節(jié)點運動模型不同，人類的社會關(guān)系比較穩(wěn)定而且存在一定的依賴性，表現(xiàn)為節(jié)點的“聚集”現(xiàn)象[6]。在社會網(wǎng)絡(luò)中將這些有聚集趨勢的節(jié)點稱為“簇”，屬于同一簇的節(jié)點相遇概率高、持續(xù)時間長；而分屬不同簇的節(jié)點相遇概率較低、持續(xù)時間較短。在機會網(wǎng)絡(luò)環(huán)境中，節(jié)點數(shù)據(jù)的交換需要利用節(jié)點間的相遇機會完成，但真實的社會網(wǎng)絡(luò)通信中經(jīng)常體現(xiàn)“小世界”現(xiàn)象[7-8]。因此，探索人類活動的社會關(guān)系能夠使機會社會網(wǎng)絡(luò)路由協(xié)議具有更高實用性和有效性。

因此，研究者將研究的重點逐漸轉(zhuǎn)移到網(wǎng)絡(luò)節(jié)點關(guān)系對路由性能的影響上[9]，以解決傳統(tǒng)機會路由算法不適用大規(guī)模、復(fù)雜網(wǎng)絡(luò)的問題[10]。文獻(xiàn)[11]將分層路由技術(shù)引入到機會網(wǎng)絡(luò)中，提出一種基于分層的機會路由機制。文獻(xiàn)[12]采用基于連接的最大直徑方式，文獻(xiàn)[13]通過在線統(tǒng)計節(jié)點相遇概率的方式，為節(jié)點的簇劃分以及信息交換和路由提供基礎(chǔ)。另外，文獻(xiàn)[14]依據(jù)小世界理論將活躍的中間節(jié)點定義為橋節(jié)點，通過橋節(jié)點有效的降低消息投遞過程的傳遞次數(shù)。文獻(xiàn)[15]針對PSN，引入中心度和社區(qū)的概念，運用社會學(xué)的相關(guān)理論優(yōu)化路由策略。文獻(xiàn)[16]將社會距離作為選取消息傳遞目標(biāo)的度量，同時為降低動態(tài)社區(qū)劃分方法的計算壓力，引入靜態(tài)的社會關(guān)系圖。

本文以聚類思想為基礎(chǔ)，借鑒現(xiàn)有路由算法的優(yōu)點，針對現(xiàn)有基于聚類的路由方法普遍存在的計算資源需求大、聚類結(jié)果不準(zhǔn)確等問題，提出了一種基于兩階段聚類分析的機會社會網(wǎng)絡(luò)路由算法。該方法依據(jù)節(jié)點的社會屬性，對其進(jìn)行聚類分析，將關(guān)系密切、接觸頻繁的節(jié)點劃分到同一簇中，對簇內(nèi)/簇間消息采用不同的轉(zhuǎn)發(fā)策略，以達(dá)到提高路由效率和降低網(wǎng)絡(luò)流量的效果。同時，為降低聚類分析對網(wǎng)絡(luò)計算資源的占用，該過程采用基于相遇統(tǒng)計的簡單聚類和基于數(shù)據(jù)交換的層次聚類兩階段完成。第一階段聚類分析對計算能力要求較低，能夠保障低計算資源網(wǎng)絡(luò)環(huán)境下的基本路由需求；第二階段聚類分析在計算資源充足的節(jié)點上進(jìn)行，能夠提升聚類結(jié)果的準(zhǔn)確性，有效提高路由效率。

1 兩階段聚類算法

將物理或抽象對象的集合分成由類似對象組成的多個類的過程被稱為聚類，由聚類所生成的簇是一組數(shù)據(jù)對象的集合。路由算法中，將移動節(jié)點作為聚類分析的對象，由聚類所生成的簇是一組節(jié)點的集合，這些節(jié)點與同一簇中的節(jié)點彼此關(guān)系緊密、相遇頻繁，與其他簇中的節(jié)點聯(lián)系較少。通常情況下，聚類算法需要依據(jù)一定規(guī)則反復(fù)迭代至算法收斂，這一過程需要消耗大量計算資源。機會社會網(wǎng)絡(luò)中節(jié)點的計算能力與資源的分散分布的結(jié)構(gòu)不能滿足常規(guī)聚類算法的需求，因此在路由算法采用基于事件觸發(fā)的聚類模式。第一階段基于相遇統(tǒng)計的簡單聚類設(shè)定節(jié)點相遇為聚類算法的觸發(fā)事件，節(jié)點相遇時交換相遇列表并更新聚類信息；第二階段基于數(shù)據(jù)交換的層次聚類設(shè)定節(jié)點交互為聚類算法的觸發(fā)事件，僅在節(jié)點間有消息傳遞時才進(jìn)行聚類信息的更新。

1.1 基于相遇概率統(tǒng)計的第一階段聚類算法

機會社會網(wǎng)絡(luò)中節(jié)點間不存在穩(wěn)定的端到端連接，因此需要利用節(jié)點相遇的歷史信息估算節(jié)點相遇概率，并以此作為網(wǎng)絡(luò)拓?fù)涞拇致悦枋?。對于擁有個節(jié)點的機會社會網(wǎng)絡(luò)，節(jié)點相遇矩陣是一個概率矩陣，其中第行第列的元素是節(jié)點和節(jié)點的相遇概率，代表對兩節(jié)點在未來一段時間內(nèi)相遇概率的預(yù)測。節(jié)點相遇概率按照規(guī)定的周期更新，更新規(guī)則應(yīng)滿足如下條件：如果在上一更新周期內(nèi)節(jié)點與節(jié)點相遇，相遇概率相應(yīng)增大；反之，減小。據(jù)此提出節(jié)點間相遇概率公式：

(3)

根據(jù)機會社會網(wǎng)絡(luò)的特性，分簇算法基于節(jié)點的相遇事件觸發(fā)。當(dāng)節(jié)點與節(jié)點相遇時，通過計算相應(yīng)的節(jié)點與簇間相遇概率以及簇與簇間的相遇概率，確定簇的劃分與節(jié)點的加入/退出操作。

1.2 基于事件鏈分析的第二階段聚類算法

在動態(tài)網(wǎng)絡(luò)分析算法中，將兩個或兩個以上的節(jié)點之間發(fā)生的連接稱為事件，機會網(wǎng)絡(luò)中將節(jié)點間通信定義為事件。通常情況下，機會社會網(wǎng)絡(luò)中節(jié)點的活動都帶有明顯的社會性，事件的發(fā)生大多具有明顯的周期性規(guī)律，因此能夠形成具有緊密時間、空間關(guān)聯(lián)事件集合?？梢哉J(rèn)為屬于同一簇的節(jié)點間的鏈接往往具有明顯、穩(wěn)定的時空關(guān)聯(lián)，將這類事件集合稱為事件鏈。事件與事件鏈?zhǔn)枪?jié)點間內(nèi)在關(guān)聯(lián)和社會性的具體體現(xiàn)，利用機會社會網(wǎng)絡(luò)的這一特點，對其進(jìn)行基于事件鏈的深度聚類分析，能夠更精確地確定簇成員，剔除無用節(jié)點，進(jìn)一步提高路由算法的效率。

機會社會網(wǎng)絡(luò)中事件間的聯(lián)系與事件發(fā)生的位置有關(guān)，距離較近的事件間產(chǎn)生聯(lián)系并組成事件序列的概率較大，相反距離較遠(yuǎn)的事件間產(chǎn)生聯(lián)系的概率較小。事件有多個節(jié)點之間的連接產(chǎn)生，因此事件發(fā)生的位置為包含參與事件各個節(jié)點的區(qū)域，一般用事件的中心點和半徑表示。事件的中心點坐標(biāo)記為，根據(jù)式(4)進(jìn)行計算。

為適應(yīng)機會社會網(wǎng)絡(luò)中事件聯(lián)系的多樣性，對式(5)做出兩點改動。首先假設(shè)事件與其他事件產(chǎn)生聯(lián)系的能力各不相同。用半徑表示事件的這種能力。越大，事件能夠與越多的事件接觸并取得聯(lián)系。一般認(rèn)為事件包含的節(jié)點越多越容易與其他事件產(chǎn)生聯(lián)系，定義包含節(jié)點數(shù)為的事件的半徑為。其中為參數(shù)，與公式應(yīng)用的環(huán)境有關(guān)。常數(shù)1為確保半徑非零。

(8)

等價于：

(10)

2 基于中心度的分簇消息轉(zhuǎn)發(fā)機制

經(jīng)過兩階段聚類分析，整個網(wǎng)絡(luò)被分割成為若干簇，每個簇可以看作一個規(guī)模較小的機會社會網(wǎng)絡(luò)。聚類分析中分簇決策的依據(jù)是節(jié)點間的內(nèi)在聯(lián)系，所以同簇節(jié)點的關(guān)系緊密、相遇概率較高，而分屬不同簇節(jié)點的關(guān)系松散、相遇概率較低。因此按照消息攜帶節(jié)點和目標(biāo)節(jié)點是否屬于同一個簇，可以將機會社會網(wǎng)絡(luò)中消息轉(zhuǎn)發(fā)分成兩種情況，消息攜帶節(jié)點與目標(biāo)節(jié)點屬于同一個簇的稱為簇內(nèi)消息轉(zhuǎn)發(fā)，屬于不同簇的稱為簇間消息轉(zhuǎn)發(fā)。為提高路由協(xié)議的效率，需要針對這兩種情況中節(jié)點間關(guān)系的特點，分別提出相適應(yīng)的策略。

2.1 簇內(nèi)消息轉(zhuǎn)發(fā)策略

簇內(nèi)的消息轉(zhuǎn)發(fā)策略采用改進(jìn)的Spray and Wait路由算法，消息在中間節(jié)點傳遞的過程中副本配額的分配比例依據(jù)各節(jié)點與目的節(jié)點的相遇概率決定。當(dāng)源節(jié)點有消息需要發(fā)送到目的節(jié)點時，如果節(jié)點與節(jié)點屬于同一個簇，則節(jié)點首先確定消息的副本配額為，即在簇中最多存在個消息的副本。在消息轉(zhuǎn)發(fā)過程中，當(dāng)攜帶消息的中間節(jié)點(副本配額為)與節(jié)點相遇時，節(jié)點將份副本轉(zhuǎn)發(fā)給節(jié)點。其中：

2.2 簇間消息轉(zhuǎn)發(fā)策略

在社會網(wǎng)絡(luò)中，中心度高的節(jié)點不僅與同簇節(jié)點關(guān)系緊密，與部分異簇節(jié)點間也有較高的相遇概率。這類節(jié)點能夠成為不同簇節(jié)點之間聯(lián)系的橋梁，充分利用可以有效提高簇間消息轉(zhuǎn)發(fā)效率。節(jié)點中心度的一般測量式為：

由于機會社會網(wǎng)絡(luò)中，節(jié)點中心度測量只能涉及與其相連(有相遇歷史)的節(jié)點，具有局域性，因此可將式(13)簡化為：

(14)

3 性能分析

3.1 仿真環(huán)境

本文利用MATLAB平臺對MIT Reality Trace數(shù)據(jù)集[18]進(jìn)行基于事件驅(qū)動的仿真。MIT Reality Trace共包括94個節(jié)點，近110 K條接觸記錄。節(jié)點間的接觸間隔基本符合指數(shù)分布，同時存在明顯社會特征。

在仿真過程中，節(jié)點按照一定概率產(chǎn)生目的地址隨機的數(shù)據(jù)包。數(shù)據(jù)包大小在[1,100] kB區(qū)間均勻分布。數(shù)據(jù)集的前1/4數(shù)據(jù)作為仿真的預(yù)熱，以使聚類算法的分簇結(jié)果達(dá)到穩(wěn)定狀態(tài)，仿真結(jié)果從數(shù)據(jù)集的后3/4部分仿真中獲得。

選取PRoPHET、Clustering和BUBBLE作為對比算法。在參數(shù)選擇上，除特別列出的專有參數(shù)采用算法的慣用取值外，其余參數(shù)與本文算法相同。

3.2 仿真結(jié)果及分析

1) 投遞率與投遞時延

投遞率與投遞時延是機會社會網(wǎng)絡(luò)較為重要的評價標(biāo)準(zhǔn)，其中投遞率是指成功送達(dá)目的節(jié)點的消息數(shù)在所有產(chǎn)生的消息中所占的比例，投遞時延是指消息從源節(jié)點產(chǎn)生到送達(dá)目的節(jié)點所需時間的平均值。結(jié)合應(yīng)用環(huán)境特點和算法特性，本文針對網(wǎng)絡(luò)運行時間的變化對協(xié)議性能的影響進(jìn)行仿真。

圖1a表示仿真過程中投遞率隨接觸次數(shù)增加的變化趨勢。實驗中將每個消息的生存時間(TTL)設(shè)定為9個月，并且不限制節(jié)點的緩存大小，即在仿真過程中不會出現(xiàn)報文被丟棄的情況。在仿真開始階段PRoPHET的投遞率迅速上升，較早地達(dá)到了穩(wěn)定狀態(tài)。其他算法的投遞率逐漸上升，在中期達(dá)到穩(wěn)定狀態(tài)。最終本文算法投遞率最高，而PRoPHET投遞率最低，Clustering和BUBBLE投遞率基本相當(dāng)。

PRoPHET基于歷史相遇記錄預(yù)測未來一段時間的節(jié)點相遇概率，所需要的信息少，使用的分析方法簡單，因此能在仿真過程中較早地達(dá)到穩(wěn)定階段，但最終投遞率不如其他算法?；诰垲惙治龅腃lustering和基于社區(qū)的BUBBLE的核心都是將節(jié)點劃分成為較小的集合，降低網(wǎng)絡(luò)節(jié)點間關(guān)系的復(fù)雜性。仿真過程中此類算法需要較長的預(yù)熱過程，在收集足夠的信息使得聚類分析或社區(qū)劃分穩(wěn)定后，算法的投遞率會達(dá)到較高的水平。本文算法在聚類分析的基礎(chǔ)上，利用社會分析學(xué)中事件鏈理論深入探索節(jié)點間的內(nèi)在聯(lián)系，因此相對于其他算法獲得了更高的投遞率。

圖1b表示仿真過程中投遞時延隨接觸次數(shù)增加的變化趨勢。仿真開始階段，各個算法投遞時延較小。隨仿真進(jìn)程推進(jìn)，投遞時延逐漸增加，直到仿真進(jìn)行到50 K條記錄后趨于平穩(wěn)。由圖中可以看出，在各算法的投遞時延達(dá)到穩(wěn)定后，PRoPHET的投遞時延最大，Clustering其次，BUBBLE稍好于Clustering，而本文算法獲得了最低的投遞時延。

PRoPHET只考慮節(jié)點間的相遇概率，不具備分析節(jié)點間相互關(guān)系的能力，不能給出優(yōu)化的消息傳遞路徑，因此具有最高的投遞時延。Clustering與BUBBLE通過聚類分析與社區(qū)劃分能夠區(qū)分節(jié)點間關(guān)系的疏密，減少傳遞過程中的轉(zhuǎn)發(fā)次數(shù)，因此獲得相對較低的傳遞時延。BUBBLE因為引入了中心度的概念，有效利用中心度高的活躍節(jié)點傳遞消息，所以投遞時延優(yōu)于Clustering。本文算法采用事件鏈分析方法，充分利用節(jié)點間的內(nèi)在聯(lián)系，降低了消息無效轉(zhuǎn)發(fā)的幾率，因此獲得了最低的投遞時延。

a. 相遇次數(shù)對投遞率的影響

b. 相遇次數(shù)對投遞時延的影響

圖1 算法投遞率與投遞時延變化趨勢

2) 轉(zhuǎn)發(fā)效率

轉(zhuǎn)發(fā)效率是成功遞交的消息數(shù)與網(wǎng)絡(luò)中消息轉(zhuǎn)發(fā)總次數(shù)的比值。轉(zhuǎn)發(fā)效率能夠體現(xiàn)路由算法的優(yōu)化程度，具有較高轉(zhuǎn)發(fā)效率的算法能夠在網(wǎng)絡(luò)狀態(tài)相同的情況下成功送達(dá)更多的消息，獲得較高投遞率。圖2表示仿真過程中算法轉(zhuǎn)發(fā)效率的變化趨勢。

從圖中可以看出，本文算法轉(zhuǎn)發(fā)效率最高，接近0.3，即消息從產(chǎn)生到送達(dá)目的節(jié)點平均需要3～4次傳遞。而Clustering與BUBBLE轉(zhuǎn)發(fā)效率均低于0.25，消息成功送達(dá)需4次以上的傳遞。表現(xiàn)最差的PRoPHET的轉(zhuǎn)發(fā)效率在0.15以下，平均消耗7次以上轉(zhuǎn)發(fā)才能將消息送達(dá)。通過分析可知，本文提出的算法在投遞率相同的情況下轉(zhuǎn)發(fā)次數(shù)少于其他算法，因而產(chǎn)生的副本數(shù)量、占用的節(jié)點緩存較少，能夠有效節(jié)省網(wǎng)絡(luò)資源，提高網(wǎng)絡(luò)的利用率。

3) 算法效率

受到網(wǎng)絡(luò)移動性的影響，機會社會網(wǎng)絡(luò)的節(jié)點通常計算能力較弱，進(jìn)而制約了路由算法在實際使用中的效果。本文算法在節(jié)點分析階段采用兩階段聚類設(shè)計，第一階段聚類算法設(shè)計簡潔，占用計算資源少，能確保算法的基本效率要求，而第二階段聚類分析，能夠有效提高路由效率。在節(jié)點計算能力較弱的情況下，本文算法可放棄第二階段聚類過程。本組實驗中本文算法只執(zhí)行第一階段的聚類分析，圖3a表示實驗中本文算法與PRoPHET、SW的投遞率變化趨勢。從圖中可以看出，在計算資源不足的情況下本文算法依然獲得了最高的投遞率。

圖3b表示網(wǎng)絡(luò)中節(jié)點計算能力對本文路由消費效率的影響。為模仿計算資源受限的情況，圖中橫坐標(biāo)表示仿真中各節(jié)點進(jìn)行第二階段聚類分析的比例，縱坐標(biāo)表示算法的投遞率在計算資源受限情況下與正常情況下的比值。從圖中可以看出，當(dāng)網(wǎng)絡(luò)中節(jié)點的計算資源能夠滿足略高于40%的節(jié)點具有第二階段聚類分析能力時，本文算法的效率就能夠基本達(dá)到計算資源充足情況下的80%左右。

綜合上述實驗可知，在采用真實世界中人類移動軌跡的移動模型的仿真場景中，本文算法能夠提高機會社會網(wǎng)絡(luò)的路由能力，相比其他算法取得了較高的投遞率與較低的投遞時延，并且具有較高的轉(zhuǎn)發(fā)效率，節(jié)省了節(jié)點的緩存空間。

a. 計算能力不足時相遇次數(shù)對投遞率的影響

b. 二階段聚類比例對算法效率的影響

圖3 計算能力對算法的影響

4 結(jié)束語

本文通過對機會社會網(wǎng)絡(luò)特點的分析，提出了一種基于兩階段聚類分析的機會社會網(wǎng)絡(luò)路由算法，以解決機會社會網(wǎng)絡(luò)中網(wǎng)絡(luò)規(guī)模增大、節(jié)點計算資源匱乏引起的路由算法效率低下的問題。

根據(jù)機會網(wǎng)絡(luò)中節(jié)點在運動與交互過程中體現(xiàn)出的社會特性，采用聚類分析方法將網(wǎng)絡(luò)劃分成為若干規(guī)模較小的網(wǎng)絡(luò)，降低了網(wǎng)絡(luò)規(guī)模對路由算法效率的影響；聚類分析過程分為兩階段實現(xiàn)，減少了路由算法對節(jié)點計算資源的需求。實驗結(jié)果表明，在大規(guī)模復(fù)雜網(wǎng)絡(luò)環(huán)境中，本文算法能夠有效提供消息投遞率、降低投遞時延，同時能夠降低路由算法對網(wǎng)絡(luò)計算、存儲資源的消耗。

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

[2] 熊永平, 孫利民, 牛建偉, 等. 機會網(wǎng)絡(luò)[J]. 軟件學(xué)報, 2009, 20(1): 124-137.

XIONG Yong-ping, SUN Li-min, NIU Jian-wei, et al. Opportunistic networks[J]. Journal of Software, 2009, 20(1): 124-137.

[3] 徐佳, 李千目, 張宏, 等. 機會網(wǎng)絡(luò)中的自適應(yīng)噴霧路由及其性能評估[J]. 計算機研究與發(fā)展, 2015, 47(9): 1622-1632.

XU Jia, LI Qian-mu, ZHANG Hong, et al. Performance evaluation of adaptive spray routing for opportunistic networks[J]. Journal of Computer Research and Development, 2015, 47(9): 1622-1632.

[4] CONTI M, MORDACCHINI M, PASSARELLA A, et al. A semantic-based algorithm for data dissemination in opportunistic networks[C]//Self-Organizing Systems. Berlin Heidelberg: Springer, 2014: 14-26.

[5] PIETIL?NEN A K, DIOT C. Dissemination in opportunistic social networks: the role of temporal communities[C]// Proceedings of the Thirteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing. [S.l.]: ACM, 2012: 165-174.

[6] 牛建偉, 周興, 劉燕, 等. 一種基于社區(qū)機會網(wǎng)絡(luò)的消息傳輸算法[J]. 計算機研究與發(fā)展, 2015, 46(12): 2068- 2075.

NIU Jian-wei, ZHOU Xing, LIU Yan, el al. A message transmission scheme for community-based opportunistic network[J]. Journal of Computer Research and Development, 2015, 46(12): 2068-2075.

[7] 王慧強, 胡海婧, 朱金美, 等. 面向DTN感染路由協(xié)議的緩存管理算法[J]. 電子科技大學(xué)學(xué)報, 2015, 44(3): 403-409.

WANG Hui-qiang, HU Hai-jing, ZHU Jin-mei, et al. Message-period-based buffer management algorithm for Epidemic routing protocol of DTN[J]. Journal of University of Electronic Science and Technology of China, 2015, 44(3): 403-409.

[8] 聶旭云, 楊炎, 劉夢娟, 等. 基于節(jié)點能力模型的容遲網(wǎng)絡(luò)路由算法[J]. 電子科技大學(xué)學(xué)報, 2013, 42(6): 905-910.

NIE Xu-yun, YANG Yan, LIU Meng-juan, et al. Capability model based routing strategy in DTN[J]. Journal of University of Electronic Science and Technology of China, 2013, 42(6): 905-910.

[9] 張振京, 金志剛, 舒炎泰. 基于節(jié)點運動預(yù)測的社會性DTN高效路由[J]. 計算機學(xué)報, 2013, 36(3): 626-635.

ZHANG Zhen-jing, JIN Zhi-gang, SHU Yan-tai. Efficient routing in social DTN based on nedes’ movement prediction[J]. Chinese Journal of Computers, 2013, 36(3): 626-635.

[10] 鄭嘯, 羅軍舟, 曹玖新, 等. 面向機會社會網(wǎng)絡(luò)的服務(wù)廣告分發(fā)機制[J]. 計算機學(xué)報, 2012, 35(6): 1235-1248.

ZHENG Xiao, LUO Jun-zhou, CAO Jiu-xin, et al. Service advertisement dissemination in opportunistic social networks[J]. Chinese Journal of Computers, 2012, 35(6): 1235-1248.

[11] AHMED S, KANHERE S S. Cluster-based forwarding in delay tolerant public transport networks[C]//IEEE Conference on Local Computer Networks. [S.l.]: IEEE, 2007: 625-634.

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

[13] DANG H, WU H. Clustering and cluster-based routing protocol for delay-tolerant mobile networks[J]. IEEE Transactions on Wireless Communications, 2010, 9(6): 1874-1881.

[14] DALY E M, HAAHR M. Social network analysis for routing in disconnected delay-tolerant manets[C]// Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing. [S.l.]: ACM, 2007: 32-40.

[15] HUI P, CROWCROFT J, YONEKI E. Bubble rap: Social-based forwarding in delay-tolerant networks[J]. IEEE Transactions on Mobile Computing, 2011, 10(11): 1576-1589.

[16] JAHANBAKHSH K, SHOJA G C, KING V. Social-greedy: a socially-based greedy routing algorithm for delay tolerant networks[C]//Proceedings of the Second International Workshop on Mobile Opportunistic Networking. [S.l.]: ACM, 2010: 159-162.

[17] HOFF P D, RAFTERY A E, HANDCOCK M S. Latent space approaches to social network analysis[J]. Journal of the American Statistical Association, 2002, 97(460): 1090-1098.

[18] EAGLE N, PENTLAND A. Reality mining: Sensing complex social systems[J]. Personal and Ubiquitous Computing, 2006, 10(4): 255-268.

編 輯 蔣 曉

An Opportunistic Social Networks Routing Based on Two-Step Clustering

ZHANG Yu-shu, WANG Hui-qiang, FENG Guang-sheng, Lü Hong-wu, and WEN Xiu-xiu

(College of Computer Science and Technology, Harbin Engineering University Harbin 150001)

In order to increase the delivery rate and reduce the transmission delay of messages in the process of routing, an opportunistic social networks routing based on two-step clustering is presented. The method of two-step clustering is used to reduce the resource requirements for nodes, and different forwarding strategies are applied to inter-message and intra-message respectively, aiming to optimize the process of message forwarding and relay node choosing. Besides, the chain of events is used in clustering to analyze internal social relationship between nodes, which can improve the accuracy of clustering. Our evaluations show that the protocol can lead to a 5~10% increase in delivery ratio and a 10% at least decrease in delivery delay in large complex networks, and get about 80% of messages delivered in networks with insufficient resources of computing and storage.

chain of events; clustering; opportunistic social network; routing; social network analysis

TP393

A

10.3969/j.issn.1001-0548.2017.04.021

2016-01-21；

2016-12-15

國家自然科學(xué)基金(61370212, 61402127, 61502118)；教育部高等學(xué)校博士點基金優(yōu)先發(fā)展領(lǐng)域項目(20122304130002)；中央高?；究蒲袠I(yè)務(wù)費專項資金(HEUCF100601)

張淯舒(1986-)，男，博士生，主要從事機會社會網(wǎng)絡(luò)方面的研究.