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

張淯舒，王慧強(qiáng)，馮光升，呂宏武，溫秀秀

?

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

張淯舒，王慧強(qiáng)，馮光升，呂宏武，溫秀秀

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

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

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

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

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

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

1 兩階段聚類算法

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

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

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

(3)

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

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

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

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

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

(8)

等價(jià)于：

(10)

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

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

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

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

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

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

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

(14)

3 性能分析

3.1 仿真環(huán)境

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

在仿真過程中，節(jié)點(diǎn)按照一定概率產(chǎn)生目的地址隨機(jī)的數(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作為對(duì)比算法。在參數(shù)選擇上，除特別列出的專有參數(shù)采用算法的慣用取值外，其余參數(shù)與本文算法相同。

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

1) 投遞率與投遞時(shí)延

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

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

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

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

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

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

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

圖1 算法投遞率與投遞時(shí)延變化趨勢(shì)

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ā)效率的變化趨勢(shì)。

從圖中可以看出，本文算法轉(zhuǎn)發(fā)效率最高，接近0.3，即消息從產(chǎn)生到送達(dá)目的節(jié)點(diǎn)平均需要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é)點(diǎn)緩存較少，能夠有效節(jié)省網(wǎng)絡(luò)資源，提高網(wǎng)絡(luò)的利用率。

3) 算法效率

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

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

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

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

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

圖3 計(jì)算能力對(duì)算法的影響

4 結(jié)束語(yǔ)

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

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

[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] 熊永平, 孫利民, 牛建偉, 等. 機(jī)會(huì)網(wǎng)絡(luò)[J]. 軟件學(xué)報(bào), 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] 徐佳, 李千目, 張宏, 等. 機(jī)會(huì)網(wǎng)絡(luò)中的自適應(yīng)噴霧路由及其性能評(píng)估[J]. 計(jì)算機(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ū)機(jī)會(huì)網(wǎng)絡(luò)的消息傳輸算法[J]. 計(jì)算機(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] 王慧強(qiáng), 胡海婧, 朱金美, 等. 面向DTN感染路由協(xié)議的緩存管理算法[J]. 電子科技大學(xué)學(xué)報(bào), 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] 聶旭云, 楊炎, 劉夢(mèng)娟, 等. 基于節(jié)點(diǎn)能力模型的容遲網(wǎng)絡(luò)路由算法[J]. 電子科技大學(xué)學(xué)報(bào), 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é)點(diǎn)運(yùn)動(dòng)預(yù)測(cè)的社會(huì)性DTN高效路由[J]. 計(jì)算機(jī)學(xué)報(bào), 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] 鄭嘯, 羅軍舟, 曹玖新, 等. 面向機(jī)會(huì)社會(huì)網(wǎng)絡(luò)的服務(wù)廣告分發(fā)機(jī)制[J]. 計(jì)算機(jī)學(xué)報(bào), 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

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

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