黃嘉玲 李建波 李 英

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

1 引言

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

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

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

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

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

2 ARASR算法

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

圖1 ARASR流程圖

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

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

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

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

2.2 節(jié)點有效傳輸能力計算

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

圖2 節(jié)點活躍時間示意圖

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

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

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

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

2.3 消息副本控制機制

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

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

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

2.4 ARASR算法實現(xiàn)

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

3.1 仿真環(huán)境

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

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

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

3.2 仿真結(jié)果分析

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

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

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

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

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

3.2.2 改變消息生存時間

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

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

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

3.2.3 改變消息生成時間間隔

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

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

4 結(jié)語

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