移動(dòng)社會(huì)網(wǎng)絡(luò)中基于社區(qū)的消息轉(zhuǎn)發(fā)技術(shù)

陳志鳴，陳安邦

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院、軟件學(xué)院、網(wǎng)絡(luò)空間安全學(xué)院，江蘇 南京 210023)

0 引 言

延遲容忍網(wǎng)絡(luò)(delay tolerant network，DTN)是一種具有挑戰(zhàn)性的網(wǎng)絡(luò)，其中通信設(shè)備之間的聯(lián)系是間歇的。因此，源和目的地之間的端到端路徑很少存在。在延遲容忍網(wǎng)絡(luò)中，節(jié)點(diǎn)通常具有高度移動(dòng)性，并且經(jīng)常移出節(jié)點(diǎn)的范圍，導(dǎo)致整個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)之間只能暫時(shí)處于連接狀態(tài)[1]。

移動(dòng)社會(huì)網(wǎng)絡(luò)(mobile social networks，MSN)由移動(dòng)用戶(hù)組成，移動(dòng)用戶(hù)可以采用短距離通信模式以低成本交換消息，比如多媒體等較大文件[2]。這種移動(dòng)社會(huì)網(wǎng)絡(luò)可以被視為一種特殊的延遲容忍網(wǎng)絡(luò)。

由于固有的間歇性連接，消息轉(zhuǎn)發(fā)是該網(wǎng)絡(luò)最具挑戰(zhàn)性的方面之一。在文中，節(jié)點(diǎn)中心性和運(yùn)動(dòng)方向的理論被用來(lái)解決這個(gè)特定問(wèn)題。提出了一種新穎的轉(zhuǎn)發(fā)策略，即混合消息轉(zhuǎn)發(fā)(mixed message forwarding，MMF)，利用邊界投遞箱(boundarybox)特殊設(shè)施來(lái)減少傳輸延遲。

1 相關(guān)工作

早期提出的Epidemic[3]不加選擇地向網(wǎng)絡(luò)直接擴(kuò)散信息，具有最高的傳輸率和交付時(shí)間，但也付出了最高的傳輸成本。為了降低傳輸成本，一些移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)算法利用各種社會(huì)性質(zhì)的度量來(lái)選擇中繼節(jié)點(diǎn)，典型的有SimBet[4]、Bubble RAP[5]和Friendship[6]。SimBet使用相似性和中介中心性度量來(lái)確定具有更好傳遞性的中繼節(jié)點(diǎn)。類(lèi)似地，Bubble RAP使用中心性和社區(qū)來(lái)做出轉(zhuǎn)發(fā)決策，F(xiàn)riendship通過(guò)引入節(jié)點(diǎn)之間友誼質(zhì)量的度量來(lái)衡量節(jié)點(diǎn)之間的關(guān)系強(qiáng)弱。

Zhang Huijuan等在文獻(xiàn)[7]中提出的協(xié)議擴(kuò)展了Kim等的工作[8]，這個(gè)協(xié)議另外添加了端點(diǎn)偏向擴(kuò)展的自我中介中心性的使用?；诮佑|頻率的方法(CFBA)和基于接觸持續(xù)時(shí)間的方法(CDBA)[9]都使用基于聯(lián)系持續(xù)時(shí)間的k-clique方法將節(jié)點(diǎn)分成社區(qū)，并使用中心性(表示網(wǎng)絡(luò)連接性的度量)來(lái)選擇中繼節(jié)點(diǎn)。基于社交的單一副本路由SBSCR[9]是一種基于社區(qū)的路由機(jī)制，其中路由決策是基于社交的效用(SBU)來(lái)考慮相似性和友誼值。Chen和Lou[10]提出的兩種路由，預(yù)期相遇路由(EER)和社區(qū)感知路由(CAR)，是使用了基于節(jié)點(diǎn)之間的交互歷史確定的度量。IRS[11]是一種基于激勵(lì)的路由策略。在這種方法中，節(jié)點(diǎn)可以參與并獲得獎(jiǎng)勵(lì)以犧牲它們的自私。Choksatid等提出協(xié)議SEd[12]對(duì)Epidemic路由方案進(jìn)行了改進(jìn)。由Igarashi等[13]提出的使用名為社區(qū)和中心性的參數(shù)控制每個(gè)節(jié)點(diǎn)的消息轉(zhuǎn)發(fā)。ICMPF[14]利用多跳MSN中的網(wǎng)絡(luò)節(jié)點(diǎn)的各種自私行為，是一種激勵(lì)型的多拷貝分組轉(zhuǎn)發(fā)協(xié)議。FCNS[15]是一種模糊路由轉(zhuǎn)發(fā)算法，利用了移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)中的綜合節(jié)點(diǎn)相似性(移動(dòng)和社會(huì)相似性)來(lái)決定節(jié)點(diǎn)的傳輸。

通過(guò)分析以上方法，筆者認(rèn)為移動(dòng)社會(huì)網(wǎng)絡(luò)中的轉(zhuǎn)發(fā)算法主要存在消息投遞率低、傳輸延遲高的問(wèn)題。還有就是中心性度量如何改進(jìn)，以及在某個(gè)社區(qū)內(nèi)(小范圍)和各個(gè)社區(qū)間(大范圍)資源消耗權(quán)衡的問(wèn)題。基于此，文中改進(jìn)了中心性度量，并且在某個(gè)社區(qū)內(nèi)和各個(gè)社區(qū)間采用不同的轉(zhuǎn)發(fā)方法。

2 MMF概述

為了解決這些問(wèn)題，文中提出了一種基于社區(qū)的機(jī)會(huì)網(wǎng)絡(luò)算法MMF。MMF算法分為四個(gè)部分：內(nèi)轉(zhuǎn)發(fā)，外轉(zhuǎn)發(fā)，漫游和獲取，如圖1所示。

圖1 算法模型

(1)社區(qū)內(nèi)轉(zhuǎn)發(fā)階段，節(jié)點(diǎn)在源節(jié)點(diǎn)所屬的社區(qū)中傳輸消息，直到節(jié)點(diǎn)遇到邊界投遞箱。節(jié)點(diǎn)更傾向于將消息發(fā)送到邊界投遞箱。

(2)社區(qū)外轉(zhuǎn)發(fā)階段，當(dāng)邊界投遞箱接收到消息拷貝時(shí)，它將消息傳播到其傳輸區(qū)域內(nèi)鄰近社區(qū)的節(jié)點(diǎn)。

(3)在漫游階段，節(jié)點(diǎn)優(yōu)先將消息轉(zhuǎn)發(fā)給邊界投遞箱。使用基于節(jié)點(diǎn)移動(dòng)方向的多拷貝方法將信息擴(kuò)散到其他社區(qū)。

(4)在消息獲取階段，目的節(jié)點(diǎn)將從任何首次遇到的攜帶消息的設(shè)備提取消息。攜帶消息的設(shè)備可以是節(jié)點(diǎn)或邊界投遞箱。

在上述方案中，四個(gè)階段不一定遵循順序，該順序由源節(jié)點(diǎn)和目的節(jié)點(diǎn)位置確定。源節(jié)點(diǎn)和目的節(jié)點(diǎn)在一個(gè)社區(qū)中，因此可以直接進(jìn)入第四部分?；蛘撸绻繕?biāo)位于源節(jié)點(diǎn)的社區(qū)附近，則不會(huì)執(zhí)行第三階段。

3 MMF算法

本節(jié)將詳細(xì)介紹MMF算法。文中僅關(guān)注消息傳輸，只要每個(gè)攜帶消息的設(shè)備有足夠的緩存空間且鏈路具有足夠的帶寬，它就可以發(fā)送消息。此外，任何兩個(gè)節(jié)點(diǎn)之間以及節(jié)點(diǎn)和邊界投遞箱之間的通信時(shí)間是獨(dú)立的。

3.1 內(nèi)轉(zhuǎn)發(fā)階段

中心效用值可用于衡量節(jié)點(diǎn)在消息傳輸中的重要性。文中定義的中心效用值由兩個(gè)參數(shù)組成，即節(jié)點(diǎn)轉(zhuǎn)發(fā)消息的數(shù)量和鄰居節(jié)點(diǎn)更新數(shù)。中心效用值計(jì)算如下：

節(jié)點(diǎn)j在某一時(shí)隙的轉(zhuǎn)發(fā)消息的數(shù)量標(biāo)準(zhǔn)化計(jì)算方法如下：

(1)

(2)

其中，vj(t)是當(dāng)前時(shí)隙的鄰居節(jié)點(diǎn)集合；vj(told)是前一個(gè)時(shí)隙的鄰居節(jié)點(diǎn)集合。

節(jié)點(diǎn)j在某一時(shí)隙的鄰居節(jié)點(diǎn)更新數(shù)標(biāo)準(zhǔn)化計(jì)算方法如下：

(3)

節(jié)點(diǎn)具有更高的u和v值，更有可能遇到目地節(jié)點(diǎn)。所以通過(guò)以下公式組合這兩個(gè)參數(shù)來(lái)定義節(jié)點(diǎn)j的中心效用值：

Uj=αv+βu

(4)

其中，α，β是設(shè)置的權(quán)重。

當(dāng)節(jié)點(diǎn)接收到鄰居節(jié)點(diǎn)的中心效用值Uj時(shí)，該節(jié)點(diǎn)將它的值與最大值進(jìn)行比較。如果此節(jié)點(diǎn)的值較低，則它會(huì)將消息轉(zhuǎn)發(fā)到具有中心效用值的節(jié)點(diǎn)。

3.2 擴(kuò)散階段

在傳播階段，當(dāng)邊界投遞箱接收到某個(gè)節(jié)點(diǎn)發(fā)送的消息副本時(shí)，邊界投遞箱將消息副本擴(kuò)散給其他沒(méi)有消息的節(jié)點(diǎn)，而這些節(jié)點(diǎn)在發(fā)送該副本節(jié)點(diǎn)所屬的社區(qū)之外。

3.3 漫游階段

|cosθ|=

(5)

其中，k≤1。

3.4 獲取階段

在提取階段，目的節(jié)點(diǎn)只是在遇到攜帶消息者時(shí)獲取消息。這個(gè)消息攜帶者可能處于源節(jié)點(diǎn)社區(qū)內(nèi)轉(zhuǎn)發(fā)階段，外轉(zhuǎn)發(fā)階段或者漫游階段。最糟糕的情況是，數(shù)據(jù)包被擴(kuò)散到每個(gè)社區(qū)，目的節(jié)點(diǎn)才獲取到消息。

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

4.1 算法的比較

文中只關(guān)注移動(dòng)社會(huì)網(wǎng)絡(luò)中的轉(zhuǎn)發(fā)算法。為了進(jìn)行公平的性能比較，將文中算法與現(xiàn)有的零知識(shí)多拷貝路由算法進(jìn)行比較：Epidemic、Prophet和HS。

算法Epidemic、Prophet和HS都是通過(guò)復(fù)制傳遞消息的。Prophet算法是一種基于效用的多拷貝路由算法。HS算法中數(shù)據(jù)包攜帶者采用二分法將副本分割給遇到的節(jié)點(diǎn)或投遞箱。

4.2 參數(shù)設(shè)置

文中模擬的場(chǎng)景相對(duì)較大，節(jié)點(diǎn)隨機(jī)移動(dòng)，節(jié)點(diǎn)的初始位置也是隨機(jī)生成的。邊界投遞箱在初始化時(shí)生成并具有固定位置。另外，可以根據(jù)需要改變參數(shù)值，以便觀察每個(gè)參數(shù)值對(duì)結(jié)果的影響，得出最優(yōu)結(jié)果，有利于與其他算法進(jìn)行比較，評(píng)估算法的優(yōu)缺點(diǎn)。

文中模型的場(chǎng)景是一個(gè)矩形。為了簡(jiǎn)化模擬，將場(chǎng)景的長(zhǎng)度和寬度設(shè)置為相同。節(jié)點(diǎn)的傳輸半徑設(shè)置為15，社區(qū)數(shù)量固定為9。實(shí)驗(yàn)大致分為三個(gè)：平均投遞率的比較，平均傳輸時(shí)間的比較和MMF算法中余弦值對(duì)平均傳輸時(shí)間的影響。在第一個(gè)實(shí)驗(yàn)中，四種算法的社區(qū)長(zhǎng)度和寬度D被設(shè)置為50,60和70，然后進(jìn)行比較。在第二個(gè)實(shí)驗(yàn)中，四種算法中的節(jié)點(diǎn)數(shù)N被設(shè)置為1 000,2 000和3 000，然后進(jìn)行比較。評(píng)估參數(shù)如表1所示。

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

在此模擬中評(píng)估的指標(biāo)是平均投遞率和平均傳輸時(shí)間。平均投遞率是成功交付數(shù)量與消息總數(shù)之比，平均傳輸時(shí)間是第一個(gè)副本到達(dá)目的地的傳遞時(shí)間。

4.3 仿真結(jié)果和分析

通過(guò)四組仿真實(shí)驗(yàn)來(lái)評(píng)估算法的各項(xiàng)參數(shù)對(duì)性能的影響。在第一組模擬中，將四種算法的社區(qū)長(zhǎng)寬D依次設(shè)置為50，60和70，同時(shí)設(shè)置N=2 000，θ=0.5。在第二組模擬中，將四種算法的節(jié)點(diǎn)數(shù)量N依次設(shè)置為1 000，2 000和3 000，同時(shí)設(shè)置D=50，θ=0.5。為了更加具體地觀察各個(gè)算法之間的差別，在這兩組實(shí)驗(yàn)中將依次在t=240，t=600，t=6 000的條件下觀察各個(gè)算法的走向，如圖3和4所示。

圖3顯示，隨著社區(qū)長(zhǎng)度和寬度的增加，四種算法的平均投遞率隨之降低。相反，HS算法在D=70時(shí)具有最差的平均投遞率。Prophet的概率選擇機(jī)制導(dǎo)

(a)t=240

(b)t=600

(c)t=6 000 圖3 平均投遞率的比較

致消息不斷接近目的節(jié)點(diǎn)，但由于Prophet僅依靠節(jié)點(diǎn)轉(zhuǎn)發(fā)消息，因此它的性能相對(duì)較低。MMF主要是由于邊界投遞箱的外部轉(zhuǎn)發(fā)功能，使得消息能夠快速傳播到其他社區(qū)，因此它的性能優(yōu)于上述兩種算法。Epidemic的消息數(shù)量和轉(zhuǎn)發(fā)節(jié)點(diǎn)數(shù)量不受限制，因此在小情況下擴(kuò)散速度非?？欤S著整個(gè)場(chǎng)景變大，擴(kuò)頻消息需要更多的傳輸時(shí)間。

(a)t=240

(b)t=600

(c)t=6 000 圖4 平均傳輸時(shí)間的比較

接下來(lái)還進(jìn)行了三組模擬，以便根據(jù)平均傳輸時(shí)間來(lái)評(píng)估上述算法的性能。圖4中的結(jié)果表明，隨著節(jié)點(diǎn)數(shù)量的增加，平均傳輸時(shí)間都有減少。在t=240和t=600時(shí)，Prophet在n=1 000時(shí)具有最長(zhǎng)的傳輸時(shí)間。當(dāng)t=6 000時(shí)，HS的傳輸時(shí)間大于其他三種算法。總的來(lái)說(shuō)，t越長(zhǎng)，HS越不穩(wěn)定。因?yàn)檫吔缤哆f箱在HS中的作用只是在社區(qū)中傳播消息，所以社區(qū)之間的消息傳播僅依賴(lài)于進(jìn)出社區(qū)的節(jié)點(diǎn)，因此節(jié)點(diǎn)的數(shù)量對(duì)它有很大的影響。而在MMF中，因?yàn)檫吔缤哆f箱的外轉(zhuǎn)發(fā)和漫游功能，消息可以快速傳播到其他社區(qū)，因此除了Epidemic之外，它在三種算法中的平均傳輸時(shí)間更短。

圖5 MMF角度余弦值對(duì)平均傳輸時(shí)間的影響

接下來(lái)研究MMF在漫游階段使用的角度余弦值K的變化對(duì)平均傳輸時(shí)間的影響。設(shè)置N=2 000，D=50，t=240。如圖5所示，比較了在K=0.1，K=0.5，K=0.8和K=1時(shí)的平均傳輸時(shí)間。結(jié)果表明，K越接近1，平均傳輸時(shí)間越小，但這將導(dǎo)致大量拷貝，不必要的能量消耗和無(wú)用的帶寬占用。

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

研究了一個(gè)特殊的移動(dòng)社交網(wǎng)絡(luò)，其中運(yùn)行場(chǎng)景包括一些節(jié)點(diǎn)，社區(qū)和邊界投遞箱，并提出一種零知識(shí)多拷貝路由算法MMF。MMF為邊界投遞箱設(shè)置了更高的優(yōu)先級(jí)，以幫助快速傳播信息。理論分析和仿真結(jié)果表明，邊界投遞箱在信息傳播過(guò)程中起著重要作用。通過(guò)使用邊界投遞箱，MMF取得了比現(xiàn)有的幾種零知識(shí)MSN路由算法更好的性能。