黃嘉玲 李建波 李 英

（青島大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 青島 266071）

1 引言

容遲網(wǎng)絡(luò)（Delay Tolerant Network，DTN）最初是為星際網(wǎng)絡(luò)（InterPlanetary Network，IPN）通信而提出來的，其主要目標(biāo)是針對時(shí)延長、鏈路連接間歇性等特點(diǎn)的網(wǎng)絡(luò)，進(jìn)行互聯(lián)和互操作［1］。現(xiàn)在，IPN的研究者將其架構(gòu)應(yīng)用在其他的挑戰(zhàn)性網(wǎng)絡(luò)中，如移動(dòng)社交網(wǎng)絡(luò)（MSNs）［2～3］、車載自組網(wǎng)絡(luò)［4～5］、軍事網(wǎng)絡(luò)［6］等。移動(dòng)社交網(wǎng)絡(luò)作為容遲網(wǎng)絡(luò)應(yīng)用中的一種，一直是國內(nèi)外研究的主要趨勢，隨著移動(dòng)智能終端的迅速發(fā)展和普及，社交網(wǎng)絡(luò)已將其業(yè)務(wù)擴(kuò)展到移動(dòng)終端，其主要由無線便攜式設(shè)備形成，例如由人類攜帶的iPad、PDA、智能手機(jī)等。由于節(jié)點(diǎn)的隨機(jī)移動(dòng)性，任何兩個(gè)節(jié)點(diǎn)之間不存在持久連接，因此數(shù)據(jù)傳輸通常采用“存儲(chǔ)—攜帶—轉(zhuǎn)發(fā)”通信模式：節(jié)點(diǎn)向相遇節(jié)點(diǎn)發(fā)送消息，接收消息的節(jié)點(diǎn)攜帶該消息直到遇到可發(fā)送的其他節(jié)點(diǎn)，以便該消息到達(dá)目的節(jié)點(diǎn)，這是MSNs中數(shù)據(jù)傳輸和路由的基本原理。但從源節(jié)點(diǎn)到目的地的路徑是間歇性連接的，導(dǎo)致常規(guī)路由協(xié)議通常不適用，因此路由成為MSNs中極具挑戰(zhàn)性的一個(gè)問題［7］。

早期 Vahdat和 Becker提出了 Epidemic［8］算法，一種針對在間歇性連接網(wǎng)絡(luò)中進(jìn)行的路由協(xié)議，該算法是最簡單的復(fù)制路由協(xié)議。每個(gè)用戶維護(hù)一個(gè)數(shù)據(jù)隊(duì)列，當(dāng)兩個(gè)用戶相遇時(shí)只傳輸對方?jīng)]有存儲(chǔ)的數(shù)據(jù)，顯然Epidemic Routing在路由算法中具有較高的數(shù)據(jù)傳輸成功率，但是這種不受限制的復(fù)制消息策略也帶來了極大的網(wǎng)絡(luò)開銷。為了克服Epidemic算法帶來的過量副本問題，T.Spyropoulos等人提出了經(jīng)典的 Spray and Wait算法［9］，首先，在Spray階段該算法將復(fù)制副本折半傳輸給所有相遇鄰居節(jié)點(diǎn)來改進(jìn)傳統(tǒng)傳輸機(jī)制；其次，在消息副本僅剩一個(gè)時(shí)候，進(jìn)入等待階段，此時(shí)節(jié)點(diǎn)僅將消息傳遞于目的節(jié)點(diǎn)。Lindgren等［10］使用節(jié)點(diǎn)相遇和傳輸?shù)臍v史數(shù)據(jù)，計(jì)算節(jié)點(diǎn)之間的轉(zhuǎn)發(fā)概率，并提出了基于轉(zhuǎn)發(fā)概率的路由協(xié)議Prophet。在文獻(xiàn)［11］中，普通節(jié)點(diǎn)采用隨機(jī)運(yùn)動(dòng)，輪渡節(jié)點(diǎn)協(xié)助普通節(jié)點(diǎn)沿著恒定路徑傳遞消息。這解決了傳統(tǒng)DTN中的許多問題，但輪渡節(jié)點(diǎn)的路徑選擇對研究人員來說仍然是一個(gè)難題。因此這激發(fā)了DTN中社交網(wǎng)絡(luò)［12］應(yīng)用的想法。

當(dāng)人類參與網(wǎng)絡(luò)活動(dòng)時(shí)，移動(dòng)節(jié)點(diǎn)的行為表現(xiàn)出一定的社會(huì)關(guān)系與屬性。一些研究［13］表明，節(jié)點(diǎn)之間的社會(huì)關(guān)系與屬性對節(jié)點(diǎn)相遇事件有著重要影響，有助于減少路由開銷和提高數(shù)據(jù)傳輸?shù)某晒β?。因此，許多研究人員充分利用節(jié)點(diǎn)的社會(huì)屬性來設(shè)計(jì)數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制，并取得了良好的效果。從長遠(yuǎn)來看，基于節(jié)點(diǎn)間社會(huì)關(guān)系的數(shù)據(jù)傳輸機(jī)制比其他轉(zhuǎn)發(fā)模式更穩(wěn)定［13］。

在基于社會(huì)屬性的路由算法中，關(guān)鍵點(diǎn)在于發(fā)現(xiàn)和測量節(jié)點(diǎn)之間的社會(huì)關(guān)系，這取決于對節(jié)點(diǎn)相遇歷史數(shù)據(jù)的分析［14～15］。許多研究使用歷史數(shù)據(jù)來預(yù)測節(jié)點(diǎn)相遇概率，從而設(shè)計(jì)出最佳的消息轉(zhuǎn)發(fā)算法。SimBet［16］借鑒社交網(wǎng)絡(luò)的想法，基于節(jié)點(diǎn)社會(huì)相似性、中介性和聯(lián)系強(qiáng)度分析到達(dá)目的地的路徑，提高了交付率和時(shí)間。在文獻(xiàn)［17～18］中，作者利用機(jī)會(huì)主義和預(yù)期接觸節(jié)點(diǎn)等效用函數(shù)決定是否將消息轉(zhuǎn)發(fā)給機(jī)會(huì)接觸的節(jié)點(diǎn)或預(yù)期接觸的節(jié)點(diǎn)，該算法利用節(jié)點(diǎn)屬性評估其消息傳遞的有效性。Bubble Rap［19］通過對社交網(wǎng)絡(luò)的理解，利用節(jié)點(diǎn)的中心性來確保消息成功傳遞。在整個(gè)網(wǎng)絡(luò)和局部社區(qū)為每個(gè)節(jié)點(diǎn)分別設(shè)定兩個(gè)索引等級：全局等級（Global Rankness）和局部等級（Local Rank?ness）。發(fā)送消息時(shí)，節(jié)點(diǎn)重復(fù)將消息傳遞于網(wǎng)絡(luò)中全局等級更高的節(jié)點(diǎn)直到遇到目標(biāo)節(jié)點(diǎn)社區(qū)節(jié)點(diǎn)。在目標(biāo)節(jié)點(diǎn)所在的社區(qū)中，該消息進(jìn)一步被轉(zhuǎn)發(fā)到具有更高局部等級的節(jié)點(diǎn)，直至到達(dá)目的節(jié)點(diǎn)。但該路由方法并未考慮如果目標(biāo)節(jié)點(diǎn)屬于全局中心性較低社區(qū)的可能性，因此該路由方法容易造成較長延遲。

為克服移動(dòng)社交網(wǎng)絡(luò)中源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間連通路徑不穩(wěn)定的情況，本文提出了一種基于社交關(guān)系的自適應(yīng)路由算法（ARASR）。受移動(dòng)社交網(wǎng)絡(luò)中人類社會(huì)行為的啟發(fā)，我們針對移動(dòng)用戶經(jīng)常傳遞消息于社交關(guān)系密切的用戶，提出了目標(biāo)區(qū)域加權(quán)中心度和有效傳輸能力，并根據(jù)副本的數(shù)量選擇不同策略傳輸數(shù)據(jù)。其中，目標(biāo)區(qū)域加權(quán)中心度主要針對目的區(qū)域節(jié)點(diǎn)，具有較大目標(biāo)區(qū)域加權(quán)中心度的節(jié)點(diǎn)遇到目的社區(qū)中節(jié)點(diǎn)的頻率也越高，而有效傳輸能力通過節(jié)點(diǎn)活躍度和節(jié)點(diǎn)轉(zhuǎn)發(fā)意愿度定義。該算法一方面考慮當(dāng)攜帶消息節(jié)點(diǎn)副本數(shù)量僅剩一個(gè)時(shí)，為將消息盡可能傳遞到目的節(jié)點(diǎn)區(qū)域，ARASR算法選擇用戶與目標(biāo)區(qū)域加權(quán)中心度較高的節(jié)點(diǎn)實(shí)現(xiàn)消息傳輸，提高消息到達(dá)目的區(qū)域可能性。另一方面，當(dāng)消息副本大于一個(gè)時(shí)，由于有效傳輸能力能夠反映節(jié)點(diǎn)在社區(qū)間與其他節(jié)點(diǎn)的交互情況，因此根據(jù)有效傳輸能力自適應(yīng)地平衡每對節(jié)點(diǎn)之間的消息副本的數(shù)量，允許具有較高傳輸能力的用戶可獲得更多消息副本促進(jìn)消息有效傳播，提高數(shù)據(jù)傳輸率。

2 ARASR算法

本節(jié)將主要介紹ARASR算法中提出的節(jié)點(diǎn)有效傳輸能力以及目標(biāo)區(qū)域加權(quán)中心度的計(jì)算，并詳細(xì)解釋如何通過節(jié)點(diǎn)活躍度以及節(jié)點(diǎn)轉(zhuǎn)發(fā)意愿度評估節(jié)點(diǎn)的有效傳輸能力，最后說明如何實(shí)現(xiàn)消息副本控制機(jī)制。算法實(shí)現(xiàn)具體流程如圖1所示，其中Vd表示目的節(jié)點(diǎn)，與傳統(tǒng)路由算法不同的是，我們首先判斷攜帶消息節(jié)點(diǎn)與目的節(jié)點(diǎn)是否屬于同一社區(qū)，如果屬于同一社區(qū)，則將消息直接傳遞給目標(biāo)節(jié)點(diǎn)。其次，根據(jù)判定消息副本數(shù)量是否大于1選擇不同策略確定中繼節(jié)點(diǎn)，加速消息傳播到目標(biāo)節(jié)點(diǎn)區(qū)域。因此ARASR算法的主要工作是在第二部分路由策略的選擇，根據(jù)所提出的兩種指標(biāo)（目標(biāo)區(qū)域加權(quán)中心度和有效傳輸能力）選擇下一跳節(jié)點(diǎn)，并自適應(yīng)的調(diào)整每對節(jié)點(diǎn)之間的消息副本數(shù)量，該方法不僅有助于盡可能快地傳播消息副本，而且還能確保與目標(biāo)區(qū)域接觸頻繁的節(jié)點(diǎn)可以攜帶更多的消息副本。

圖1 ARASR流程圖

2.1 目標(biāo)區(qū)域加權(quán)中心度

由于本文的主要工作是在移動(dòng)社交網(wǎng)絡(luò)背景下設(shè)計(jì)路由方法提高信息投遞率，并不主要探討社區(qū)劃分算法，因此本文根據(jù)現(xiàn)有算法中針對沒有明確社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)環(huán)境提出的社區(qū)檢測算法［20～21］，將節(jié)點(diǎn)輕松劃分到不同社區(qū)，并且假設(shè)網(wǎng)絡(luò)中源節(jié)點(diǎn)已知目的節(jié)點(diǎn)所在區(qū)域。

為權(quán)衡多社區(qū)內(nèi)節(jié)點(diǎn)的中心度，提出針對目的社區(qū)的目標(biāo)區(qū)域加權(quán)中心度。眾所周知，網(wǎng)絡(luò)中任意一對節(jié)點(diǎn)Vi與Vj之間的相遇時(shí)間間隔遵循具有參數(shù)的指數(shù)分布［22］，換句話說，其他節(jié)點(diǎn)Vj到達(dá)給定節(jié)點(diǎn) Vi的到達(dá)率遵循泊松過程。因此，是每對節(jié)點(diǎn)Vi和Vj之間的接觸頻率，值越大，Vi和Vj相遇的頻率越高。由此可得，節(jié)點(diǎn)Vi遇到其他節(jié)點(diǎn)來自子集Z?V的相遇時(shí)間間隔也遵循指數(shù)分布，即鑒于以上考慮，節(jié)點(diǎn)Vi與其他節(jié)點(diǎn)來自目標(biāo)社區(qū)D的相遇時(shí)間間隔通過加權(quán)中心度定義如式（1）所示：

節(jié)點(diǎn)Vi與目標(biāo)節(jié)點(diǎn)所在區(qū)域D內(nèi)節(jié)點(diǎn)的參數(shù)λVi，D越大表示目標(biāo)區(qū)域加權(quán)中心度越高。因此，具有較大目標(biāo)區(qū)域加權(quán)中心度的節(jié)點(diǎn)遇到目的社區(qū)中節(jié)點(diǎn)的頻率越高。

2.2 節(jié)點(diǎn)有效傳輸能力計(jì)算

本節(jié)根據(jù)節(jié)點(diǎn)活躍度（Activeness Degree）和節(jié)點(diǎn)轉(zhuǎn)發(fā)意愿度評估節(jié)點(diǎn)的有效傳輸能力，這是由于節(jié)點(diǎn)活躍度可以有效反映當(dāng)前節(jié)點(diǎn)在移動(dòng)社交網(wǎng)絡(luò)中的受歡迎程度，而節(jié)點(diǎn)的轉(zhuǎn)發(fā)意愿度能夠體現(xiàn)節(jié)點(diǎn)在網(wǎng)絡(luò)中的合群性。

圖2 節(jié)點(diǎn)活躍時(shí)間示意圖

因此，為評估節(jié)點(diǎn)活躍度我們分別計(jì)算了節(jié)點(diǎn)在不同時(shí)間段里的相遇次數(shù)：總時(shí)間段tnow-t_initial以及最近時(shí)間段tnow-t1，如圖2所示。由于總時(shí)間里的平均相遇數(shù)能夠反映整個(gè)過程中節(jié)點(diǎn)大體的活動(dòng)狀態(tài)，而最近一段時(shí)間內(nèi)的平均相遇次數(shù)能夠反映當(dāng)前節(jié)點(diǎn)狀態(tài)。所以在計(jì)算節(jié)點(diǎn)活躍度時(shí)，為避免忽略節(jié)點(diǎn)長時(shí)間里的活動(dòng)起伏和當(dāng)前活動(dòng)行為，本文將兩個(gè)時(shí)間段相結(jié)合定義節(jié)點(diǎn)活躍性。節(jié)點(diǎn)活躍度ADVi計(jì)算公式如式（2）所示。

其 中 ，EVi，Vj表示一對節(jié)點(diǎn)的接觸次數(shù)，表示最近時(shí)間段內(nèi)與其他節(jié)點(diǎn)的平均相遇次數(shù)，表示總時(shí)間內(nèi)與其他節(jié)點(diǎn)的平均相遇次數(shù)，參數(shù)?為初始化常量，用于反映節(jié)點(diǎn)活動(dòng)中兩段時(shí)間的權(quán)重。

移動(dòng)社交網(wǎng)絡(luò)中，活躍度更高的節(jié)點(diǎn)接觸其他節(jié)點(diǎn)的概率越高，則更有可能將消息副本擴(kuò)散到網(wǎng)絡(luò)中，但節(jié)點(diǎn)轉(zhuǎn)發(fā)意愿度同樣不可忽略。本文通過式（3）使用節(jié)點(diǎn)的出度定義轉(zhuǎn)發(fā)意愿度，其定義如下：

種子節(jié)點(diǎn)的選擇不但要考慮節(jié)點(diǎn)在網(wǎng)絡(luò)中與其他節(jié)點(diǎn)的連接緊密程度，也要考慮節(jié)點(diǎn)是否可以有效傳遞消息。為了加速消息傳遞到目的區(qū)域D，最終通過結(jié)合節(jié)點(diǎn)活躍度和節(jié)點(diǎn)轉(zhuǎn)發(fā)意愿程度評估節(jié)點(diǎn)Vi的有效傳輸能力QVi，由式（4）表示。

2.3 消息副本控制機(jī)制

ARASR算法通過每對接觸節(jié)點(diǎn)之間定義的度量指標(biāo)進(jìn)行不對稱分配消息副本數(shù)量。由于網(wǎng)絡(luò)中節(jié)點(diǎn)內(nèi)存大小固定，經(jīng)常存在一部分節(jié)點(diǎn)不能快速有效傳遞消息。因此我們考慮針對不同節(jié)點(diǎn)分配不同數(shù)量的消息副本，即將攜帶消息節(jié)點(diǎn)Vi與相遇節(jié)點(diǎn)Vj的副本數(shù)量利用式（5）進(jìn)行分配，該方法有效減少了丟包率并且提高消息的投遞概率。

時(shí)選擇Vj作為下一跳中繼節(jié)點(diǎn)并根據(jù)節(jié)點(diǎn)有效傳輸能力重新分配副本數(shù)量。最后，節(jié)點(diǎn)Vi將分配的消息副本發(fā)送到相應(yīng)節(jié)點(diǎn)后并更新自身的副本數(shù)量如式（6）所示。

當(dāng)副本數(shù)量超過一個(gè)的節(jié)點(diǎn)仍將不對稱的分發(fā)消息副本，直到該節(jié)點(diǎn)遇到目的節(jié)點(diǎn)或僅剩一個(gè)消息副本。該方案有助于縮短消息在整個(gè)網(wǎng)絡(luò)中傳播的時(shí)間。

2.4 ARASR算法實(shí)現(xiàn)

本節(jié)將主要介紹ARASR路由算法的實(shí)現(xiàn)，根據(jù)現(xiàn)有的社區(qū)檢測算法，我們假設(shè)網(wǎng)絡(luò)中源節(jié)點(diǎn)已知目的節(jié)點(diǎn)所在區(qū)域，并且消息m的副本的初始數(shù)量為固定值h。綜合上述方案，我們最終實(shí)現(xiàn)ARASR算法，其具體算法實(shí)現(xiàn)策略見算法1。算法1 ARASR路由算法

input：

n：current node

v：encounter node

d：destination node

m：message carried by n

Num_n：number of copies of n

if n∈D then

n forwards m to d，finishes the transmission

else

when n encounters v

for（Num_n＞1）

if（Qv＞Qn）then

n forwards the calculated number of message m that v

could be assigned

else

n still carries the replica of message m

for（Num_n ≤ 1）

if Wv＞W(wǎng)nthen

n forwards a copy of m to v

3 仿真實(shí)驗(yàn)

3.1 仿真環(huán)境

本節(jié)采用ONE仿真模擬器（Opportunistic Net?work Environment）［23］仿 真 評 估 ARASR 算法 的性能，并同時(shí)加入Prophet、Epidemic和First Contact算法與本文提出算法比較，F(xiàn)irst Contact路由協(xié)議只考慮消息在一跳范圍內(nèi)時(shí)進(jìn)行轉(zhuǎn)發(fā)消息，Epidemic路由協(xié)議通過簡單復(fù)制方法將消息分發(fā)給每個(gè)可能遇到的節(jié)點(diǎn)，Prophet算法在相遇節(jié)點(diǎn)中權(quán)衡轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)概率更高的節(jié)點(diǎn)投遞消息。

為模擬現(xiàn)實(shí)生活中移動(dòng)社交網(wǎng)絡(luò)場景，本文選取Helsinki City作為仿真場景進(jìn)行實(shí)驗(yàn)，該模型更能體現(xiàn)人類真實(shí)社會(huì)的交互情況。赫爾辛基城市場景的網(wǎng)絡(luò)覆蓋范圍設(shè)定為4500×3400m2，其中包括126個(gè)移動(dòng)節(jié)點(diǎn)被分為80個(gè)運(yùn)動(dòng)速度為0.5m/s～1.5m/s的行人，6個(gè)7m/s～10m/s的電車以及 40個(gè)2.7m/s～13.9m/s的汽車，緩存區(qū)大小設(shè)置足夠大，因此消息不會(huì)由于緩存區(qū)過早耗盡而丟失。通訊設(shè)備使用傳輸速度和半徑分別為250KBps和20m的藍(lán)牙設(shè)備作為標(biāo)準(zhǔn)。為考慮到MSNs間歇性連接和頻繁斷開的特性，我們設(shè)置每條消息的默認(rèn)生存周期設(shè)定為2個(gè)小時(shí)，默認(rèn)時(shí)間間隔為30s。在這次模擬實(shí)驗(yàn)中，我們使用四種評估指標(biāo)來評估算法的性能，即投遞率、網(wǎng)絡(luò)負(fù)載率、平均時(shí)延和平均跳數(shù)，并且通過改變緩存空間大小，消息生成時(shí)間間隔和消息的生存時(shí)間來查看這些度量的變化。仿真結(jié)果表明，我們提出的方案顯著提高了路由性能，表1總結(jié)了模擬中使用的其他仿真參數(shù)。

表1 仿真參數(shù)設(shè)置

3.2 仿真結(jié)果分析

在這次模擬實(shí)驗(yàn)中，我們使用四種評估指標(biāo)來評估算法的性能，即投遞率、網(wǎng)絡(luò)負(fù)載率、平均時(shí)延和平均跳數(shù)，并且通過改變緩存空間大小，消息生成時(shí)間間隔和消息的生存時(shí)間來查看這些度量的變化。

3.2.1 改變節(jié)點(diǎn)緩存空間

我們通過不同路由方案在不同節(jié)點(diǎn)緩存空間大小下的性能比較得出，ARASR相比較其他三個(gè)算法在消息投遞率、平均時(shí)延、平均跳數(shù)等方面都取得明顯優(yōu)勢。這是由于ARASR算法充分考慮節(jié)點(diǎn)在移動(dòng)社交網(wǎng)絡(luò)中的社會(huì)屬性，根據(jù)目標(biāo)區(qū)域加權(quán)中心度和有效傳輸能力等指標(biāo)選擇下一跳中繼節(jié)點(diǎn)，減少了消息丟包的概率。圖3為節(jié)點(diǎn)緩沖區(qū)從4MB增加到18MB的模擬結(jié)果。

圖3 不同緩存空間下四種算法的性能表現(xiàn)

從結(jié)果可以看出，ARASR算法在各方面明顯優(yōu)于其他算法，與Prophet和Epidemic路由策略相比，ARASR的投遞率增加約29%和32%，平均時(shí)延分別降低約10%和15%。其中，Epidemic路由協(xié)議的網(wǎng)絡(luò)負(fù)載率最高，主要由于該算法沒有限制網(wǎng)絡(luò)中消息副本數(shù)量，從而造成網(wǎng)絡(luò)負(fù)擔(dān)嚴(yán)重，而本文提出的路由方法在最初就限定了副本數(shù)量，而且提出了副本控制機(jī)制，有效地限制了消息在網(wǎng)絡(luò)中的擴(kuò)散。由此可見本文提出的算法相比其他算法具有更好的表現(xiàn)。

3.2.2 改變消息生存時(shí)間

消息生存時(shí)間長短與緩存空間大小密切相關(guān)?，F(xiàn)實(shí)生活中每條消息都會(huì)受到消息生存時(shí)間TTL（Time to live）的限制，而隨著生存周期的延長，消息則會(huì)長時(shí)間活動(dòng)并占用大量緩存區(qū)空間。本次仿真模擬中設(shè)定消息生存周期從2小時(shí)增長到5.5小時(shí)，觀察TTL的變化對路由性能帶來的影響，其結(jié)果如圖4所示。

從圖中可以看出，Epidemic、Prophet算法隨著消息生存時(shí)間的增長投遞率逐漸下降，而具有自適應(yīng)副本分配的ARASR算法提供了最大傳輸率和最低平均跳數(shù)，并且ARASR的網(wǎng)絡(luò)負(fù)載率也遠(yuǎn)低于其余三種算法。這是由于隨著消息生存周期的增長導(dǎo)致節(jié)點(diǎn)緩存空間不足，而ARASR為避免緩存空間過度消耗，針對緩存空間內(nèi)消息副本數(shù)量不同采取不同的衡量指標(biāo)投遞消息，F(xiàn)irst Contact路由算法在網(wǎng)絡(luò)中轉(zhuǎn)發(fā)消息的副本數(shù)量僅有一個(gè)，所以投遞率呈現(xiàn)增長趨勢，但在其他方面表現(xiàn)遠(yuǎn)不如ARASR算法。因此結(jié)果顯示ARASR與Epidemic、Prophet算法在平均時(shí)延方面雖然基本持平，但各方面性能比其他算法更加優(yōu)秀。

圖4 不同消息生存期下四種算法的性能表現(xiàn)

3.2.3 改變消息生成時(shí)間間隔

圖5 不同消息生成時(shí)間間隔下四種算法的性能表現(xiàn)

圖5 描述在Helsinki City模型中不同消息生成時(shí)間間隔對四種路由算法的性能影響結(jié)果，可以觀察到ARASR穩(wěn)定運(yùn)行。我們設(shè)置消息生存時(shí)間間隔以10s為增量增加到90s，從圖5的結(jié)果來看，ARASR在消息投遞率、開銷率、平均時(shí)延和平均跳數(shù)等方面表現(xiàn)都優(yōu)于對比的其他三種算法，進(jìn)一步證明我們提出的路由算法可以提高網(wǎng)絡(luò)傳輸性能。由于隨著消息生成時(shí)間間隔的增長，移動(dòng)社交網(wǎng)絡(luò)中生成大量消息，可以看出除First Contact算法以外其他算法的網(wǎng)絡(luò)負(fù)載率呈上升趨勢，但First Contact算法消息投遞率始終低于0.4，原因在于該路由方法雖然是基于轉(zhuǎn)發(fā)路由策略中的代表算法之一，但攜帶消息的源節(jié)點(diǎn)隨機(jī)選擇任意鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)消息，并且副本數(shù)量只有一個(gè)，從而造成傳輸延遲長且投遞率低。Prophet算法雖然根據(jù)與目標(biāo)節(jié)點(diǎn)的接觸概率選擇中繼節(jié)點(diǎn)，但并未考慮節(jié)點(diǎn)轉(zhuǎn)發(fā)意愿度等社會(huì)屬性，因此不可避免產(chǎn)生較高負(fù)載率。從圖5可以明顯看出ARASR和Prophet算法的平均跳數(shù)和時(shí)延一直保持最低，這是因?yàn)槠溆嗨惴]有對中繼節(jié)點(diǎn)的性能進(jìn)行評估，從而導(dǎo)致盲目選擇下一跳節(jié)點(diǎn)增加了傳輸時(shí)延和跳數(shù)。而ARASR的網(wǎng)絡(luò)負(fù)載只有Epidemic和Prophet算法的24%、34%。簡而言之，所提出的方法顯著提高了在移動(dòng)社交網(wǎng)絡(luò)上的路由性能，并且利用多種衡量指標(biāo)篩選下一跳節(jié)點(diǎn)進(jìn)行消息傳遞，綜合各方面表現(xiàn)優(yōu)于其他算法。

4 結(jié)語

在本文中，我們提出了一種針對移動(dòng)社交網(wǎng)絡(luò)的自適應(yīng)路由協(xié)議ARASR，根據(jù)節(jié)點(diǎn)攜帶消息副本數(shù)量的不同，通過分析路由中兩個(gè)關(guān)鍵屬性解決優(yōu)化問題，分別是有效傳輸能力和目標(biāo)區(qū)域加權(quán)中心度。為優(yōu)化選擇中繼節(jié)點(diǎn)，ARASR在社交網(wǎng)絡(luò)場景中引入節(jié)點(diǎn)加權(quán)中心度，利用任何節(jié)點(diǎn)對之間的接觸時(shí)間間隔遵循指數(shù)分布來評估節(jié)點(diǎn)與目標(biāo)社區(qū)間的關(guān)系。此外，基于有效傳輸能力提出了消息副本控制機(jī)制，避免網(wǎng)絡(luò)中生成過多冗余消息。最后我們將本文提出的算法在ONE模擬器上進(jìn)行評估，并通過Helsinki City模型的廣泛仿真演示了ARASR算法如何顯著優(yōu)于Prophet、Epidemic和First Contact路由算法。對于路由算法來說，較低的路由開銷可以減少中繼消息的數(shù)量和不必要的緩存空間占用，并且提高節(jié)點(diǎn)的有效投遞率，而ARASR實(shí)現(xiàn)了較低的路由開銷并在消息傳輸率方面表現(xiàn)優(yōu)異，更加適用于MSNs中的消息傳輸。未來工作將集中在進(jìn)一步降低開銷率增加ARASR的投遞，并考慮通過額外約束條件來優(yōu)化下一跳中繼節(jié)點(diǎn)的選擇。