移動社會網(wǎng)絡(luò)中基于社會感知的數(shù)據(jù)轉(zhuǎn)發(fā)算法

鄧 敏，徐 方，熊曾剛，葉從歡，夏洪星

(湖北工程學院 計算機與信息科學學院，湖北 孝感 432000)

0 引 言

移動社會網(wǎng)絡(luò)[1](mobile social networks，MSNs)為用戶提供方便靈活的網(wǎng)絡(luò)服務(wù)，能廣泛應(yīng)用于智慧城市、車載網(wǎng)絡(luò)、應(yīng)急救援和健康醫(yī)療等領(lǐng)域[2]。然而，移動社會網(wǎng)絡(luò)中的節(jié)點通常是稀疏的，并且節(jié)點之間的鏈路頻繁變化，經(jīng)常不存在端到端的通路，傳統(tǒng)移動自組網(wǎng)中使用的轉(zhuǎn)發(fā)數(shù)據(jù)的方式不再適用。因而研究高效的移動社會網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)算法是當前亟待解決的難題。

移動社會網(wǎng)絡(luò)中的節(jié)點為人們攜帶的智能移動設(shè)備，因而人們的社會關(guān)系極大地影響著節(jié)點的移動行為[3]。PRoPHET算法[4]通過統(tǒng)計網(wǎng)絡(luò)節(jié)點之間相互接觸的信息預(yù)測節(jié)點未來移動的規(guī)律。社群是社會網(wǎng)絡(luò)的重要屬性之一，具有共同社會屬性和興趣的人們通常會組成一個群體，稱之為社群，相比于社群之間成員的社會交往，群體內(nèi)部成員的社會交往會更加頻繁。為了在不同的社群之間轉(zhuǎn)發(fā)數(shù)據(jù)，可以使用社群間的活躍節(jié)點作為社群之間數(shù)據(jù)傳輸?shù)臉蛄骸Ｆ渌^知名的基于社群的路由協(xié)議還有：SGBR[5]、CAOR[6]等。

攜帶者的社會關(guān)系極大影響著網(wǎng)絡(luò)中節(jié)點的相遇情況，利用這些信息的優(yōu)點在于它更能適應(yīng)現(xiàn)實世界。dLife[7]利用設(shè)備攜帶者日?；顒拥囊?guī)律幫助提高路由的效率。根據(jù)接觸時間的持續(xù)情況，該路由協(xié)議關(guān)注不同層次的社會交往的軌跡。通過觀察節(jié)點的日?；顒宇A(yù)測節(jié)點每天在不同時段與其它節(jié)點的相遇情況，dLife充分利用這些社會交往規(guī)律進行路由決策。HiBOp[8]路由算法的主要思想是尋找與已知目的節(jié)點的上下文屬性匹配程度不斷增高的中間節(jié)點。一個節(jié)點與目的節(jié)點的匹配程度越高，意味著該節(jié)點與目的節(jié)點的相似度越高。其它較為知名的基于社會關(guān)系統(tǒng)的數(shù)據(jù)轉(zhuǎn)發(fā)算法還有Fresh[9]、SMART[10]和HSFR[11]等。

以上分析表明，在移動社會網(wǎng)絡(luò)中利用社會屬性感知的方法有利于提高數(shù)據(jù)轉(zhuǎn)發(fā)的性能。本文提出了一種基于社會感知的數(shù)據(jù)轉(zhuǎn)發(fā)算法(EncoCent)，利用節(jié)點攜帶者的社會上下文信息計算節(jié)點之間的社會相似度，利用社會網(wǎng)絡(luò)計算節(jié)點的介數(shù)中心度。如果數(shù)據(jù)發(fā)送節(jié)點不知道數(shù)據(jù)目的節(jié)點的位置，則數(shù)據(jù)被轉(zhuǎn)發(fā)到中心度高的節(jié)點，從而有更多機會找到適合的中繼節(jié)點，并有利于數(shù)據(jù)被高效的發(fā)送到目的節(jié)點。本文將利用兩種社會屬性來提高網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)的性能，EncoCent結(jié)合社會相似度和介數(shù)中心度獲得節(jié)點的社交強度和其在社會網(wǎng)絡(luò)中的重要性，利用這些信息發(fā)送節(jié)點可以找到最優(yōu)中繼節(jié)點，從而提高數(shù)據(jù)轉(zhuǎn)發(fā)的效率。

1 系統(tǒng)型模

1.1 社會相似性建模

研究表明[12]，具有相同興趣傾向和相似社會特征的人們?nèi)菀紫嗑墼谝黄稹８鶕?jù)這一規(guī)律，我們?yōu)槊總€節(jié)點設(shè)計了一個社會屬性表，用于比較節(jié)點之間的社會相似性。通過社會相似性比較，可以找到更適合的中繼節(jié)點，利用這些中繼節(jié)點高效地把消息傳遞到目的節(jié)點。

(1)社會屬性表

本文使用社會屬性表描述節(jié)點攜帶者的社會上下文信息，這些信息主要包含設(shè)備攜帶者的信息(姓名、住址、工作單位、愛好等)，由社會屬性ei與對應(yīng)的取值vi組成，考慮到便于比較和隱私保護方面的因素，我們采用哈希函數(shù)對屬性和值進行了處理，哈希函數(shù)H(ei,vi)采用MD5算法實現(xiàn)，并且把函數(shù)生成哈希值存入對應(yīng)的社會屬性表中。如表1所示，社會屬性表由成對的屬性(evidence)、值(value)、哈希值H(ei,vi)組成。

表1 社會屬性表

表2描述了節(jié)點的社會屬性表，每個節(jié)點具有相同的表項且按順序排列，根據(jù)實際的應(yīng)用場景賦予社會屬性相應(yīng)的權(quán)重以體現(xiàn)該屬性的重要性。

表2 社會屬性表舉例

(2)社會相似性計算

當兩個節(jié)點相遇時，它們可以互相交換信息，并且假設(shè)網(wǎng)絡(luò)中的節(jié)點都是無私的，愿意為其它節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)。通過匹配節(jié)點的屬性表，可以計算兩個節(jié)點的社會相似性。節(jié)點N的社會屬性表中的屬性(evidence)和對應(yīng)值(value) 的集合記為N(e,v)；目的節(jié)點D的屬性表中成對的屬性和值的集合記為D(e,v)；節(jié)點N和目的節(jié)點D的屬性值的交集記為M(e,v)，如式(1)所示

M(e,v)=N(e,v)∩D(e,v)

(1)

定義1 社會相似性度量：社會相似性度量是度量節(jié)點N與目的節(jié)點D的社會屬性相似程度，表示為EncoSimN(D)，如式(2)所示。

網(wǎng)絡(luò)中每個節(jié)點存在一個含有屬性和對應(yīng)取值的社會屬性表，節(jié)點N和目的節(jié)點D之間的社會相似性計算，可以通過匹配兩個節(jié)點的社會屬性表來實現(xiàn)。社會相似性計算主要利用社會屬性表(見表1)中的數(shù)據(jù)和屬性的權(quán)值。本文設(shè)M(e,v)中屬性權(quán)值Wm權(quán)的集合為W，目的節(jié)點D(e,v)中屬性權(quán)值Wm節(jié)的集合為WD。則節(jié)點N和目的節(jié)點D之間的社會相似性EncoSimN(D)的計算方法如式(2)如下

(2)

則節(jié)點N相比于節(jié)點V，投遞一個消息到目的節(jié)點D的社會相似性效用值EncoUtilN如式(3)所示

(3)

1.2 介數(shù)中心度建模

社會網(wǎng)絡(luò)中一個節(jié)點的中心度表明該節(jié)點在社群中與其它節(jié)點聯(lián)系的緊密程度。在分析一個節(jié)點在社會網(wǎng)絡(luò)中所扮演的角色時，中心度是一個很有價值的度量。中心度也可以應(yīng)用于其它類型的網(wǎng)絡(luò)，包括引文網(wǎng)絡(luò)、計算機網(wǎng)絡(luò)和生物網(wǎng)絡(luò)。中心性度包含：度中心度(degree centra-lity)、介數(shù)中心度(betweenness centrality)和接近中心度(closeness centrality)。

網(wǎng)絡(luò)中一個節(jié)點的中心度是衡量該節(jié)點在網(wǎng)絡(luò)結(jié)構(gòu)上的重要性。通常情況下，中央節(jié)點有很強的連接其它網(wǎng)絡(luò)成員的能力。介數(shù)中心度用于測量指定節(jié)點位于網(wǎng)絡(luò)圖中其它節(jié)點“中間”的程度，在各種中心度的測量中，其計算最為復(fù)雜。介數(shù)中心度定義為網(wǎng)絡(luò)中包含指定節(jié)點的最短路徑點所有最短路徑的比例。因此介數(shù)中心度較高的節(jié)點可以或多或少地控制其它節(jié)點之間的數(shù)據(jù)交換。在移動社會網(wǎng)絡(luò)中，我們認為有較高介數(shù)中心度的節(jié)點可以促進網(wǎng)絡(luò)中其它節(jié)點之間的通信。介數(shù)中心度的計算方法如式(4)所示

(4)

式中：gjk是網(wǎng)絡(luò)中連接節(jié)點pj和pk的最短路徑長度，gjk(pi)是網(wǎng)絡(luò)中連接節(jié)點pj和pk并且經(jīng)過節(jié)點pi的最短路徑長度。介數(shù)中心度可以用于測量一個節(jié)點在網(wǎng)絡(luò)中其它節(jié)點鏈路上的橋接程度，衡量該節(jié)點對網(wǎng)絡(luò)中信息流通的控制程度。具有較高介數(shù)中心度的節(jié)點，能夠促進網(wǎng)絡(luò)中節(jié)點間的通信，適合于被選作數(shù)據(jù)轉(zhuǎn)發(fā)的中繼節(jié)點。較高介數(shù)中心度的節(jié)點的橋接作用可以用于社群之間的通信，可以有效連接不同的社群。

在網(wǎng)絡(luò)規(guī)模很大時介數(shù)中心度變得難以計算，因為需要完整的網(wǎng)絡(luò)拓撲知識。因此，我們引入自我網(wǎng)絡(luò)(ego networks)的概念。在沒有完整網(wǎng)絡(luò)拓撲信息的情況下，自我網(wǎng)絡(luò)分析可以利用個體節(jié)點的本地鄰居進行計算，利用自我網(wǎng)絡(luò)替代移動社會網(wǎng)絡(luò)，進行介數(shù)中心度計算是一種高效的，誤差可接受的方法。文獻[13]中Marsden詳細地描述了利用自我網(wǎng)絡(luò)計算介數(shù)中數(shù)度的方法，本文在下一節(jié)中采用了其計算方法。

1.3 轉(zhuǎn)發(fā)效用值計算

轉(zhuǎn)發(fā)效用值由社會相似性效用和介數(shù)中心度效用組成，采用歸一化的權(quán)重來體現(xiàn)這兩個因素的重要性。在移動社會網(wǎng)絡(luò)中進行數(shù)據(jù)轉(zhuǎn)發(fā)時，中繼節(jié)點的選擇是一個多目標決策的問題，通常希望選擇的節(jié)點在投遞消息給目的節(jié)點時具有最大效用值。在給目的節(jié)點D投遞消息時，節(jié)點N的社會相似性效用(EncoUtilN)計算方法如式(3)所示。在計算介數(shù)中心度效用時，采用上面提到的文獻[14]中的方法計算的社會網(wǎng)絡(luò)的介數(shù)中心性，節(jié)點N的介數(shù)中心度記為CentN。在投遞消息到目的節(jié)點D時，在節(jié)點N的介數(shù)中心度效用可以用如式(5)表示，其中節(jié)點V為網(wǎng)絡(luò)中的相遇節(jié)點

(5)

轉(zhuǎn)發(fā)效用值EncoCent(N)由兩部分組成，分別是社會相似性效用EncoUtilN和介數(shù)中心度效用CentUtilN，計算方法如式(6)所示，根據(jù)實際情況，通過參數(shù)α和β來調(diào)整兩部分對轉(zhuǎn)發(fā)效用的影響，且α+β=1

EncoCent(N)=αEncoUtilN(D)+βCentUtilN

(6)

轉(zhuǎn)發(fā)效用值為一種新的度量用于移動社會網(wǎng)絡(luò)中的中繼節(jié)點的選擇，該度量結(jié)合社會相似性和介數(shù)中心度，用于預(yù)測節(jié)點N把消息成功投遞到目的節(jié)點D的轉(zhuǎn)發(fā)效用。度量值EncoCent(N)越大，節(jié)點N越適合作為中繼節(jié)點。接下來本文將利用這個度量值設(shè)計高效的數(shù)據(jù)轉(zhuǎn)發(fā)算法。

2 EncoCent轉(zhuǎn)發(fā)算法

為提高移動社會網(wǎng)絡(luò)中的數(shù)據(jù)轉(zhuǎn)發(fā)效率，結(jié)合以上系統(tǒng)建模和轉(zhuǎn)發(fā)度量，本文設(shè)計了一種輕量級的基于社會感知的數(shù)據(jù)轉(zhuǎn)發(fā)算法EncoCent。

圖1描述了EncoCent數(shù)據(jù)轉(zhuǎn)發(fā)算法的數(shù)據(jù)轉(zhuǎn)發(fā)。圖中源節(jié)點S要把消息發(fā)送給目的節(jié)點D，由于當前網(wǎng)絡(luò)不存在節(jié)點S到節(jié)點D的完整通路，此時，節(jié)點S把消息轉(zhuǎn)發(fā)給中繼節(jié)點N，節(jié)點N經(jīng)過一段時間的移動后，又將信息發(fā)送下一中繼節(jié)點V，節(jié)點V經(jīng)過一段時間的移動后，與目的節(jié)點D相遇，最終將消息發(fā)送給節(jié)點D，完成數(shù)據(jù)投遞過程。在整個轉(zhuǎn)發(fā)過程中，如何選擇適合的中繼節(jié)點是算法要解決的關(guān)鍵問題。

圖1 EncoCent數(shù)據(jù)轉(zhuǎn)發(fā)

EncoCent的初始狀態(tài)為源節(jié)點S中存在發(fā)往目的節(jié)點D的數(shù)據(jù)，中間節(jié)點N、V緩存中有大量空閑空間，且存在滿足數(shù)據(jù)轉(zhuǎn)發(fā)的CPU資源，目的節(jié)點D有足夠大的空閑緩存空間接收相關(guān)數(shù)據(jù)。算法1描述了當節(jié)點N遇到節(jié)點V時，節(jié)點N的處理過程。接下來，我們分3個階段詳細說明節(jié)點N進行數(shù)據(jù)轉(zhuǎn)發(fā)的過程。

算法1： EncoCent Forwarding Algorithm (procedures onNwhen it meetsV)

(1)uponreception of Hello messagehfrom nodeVdo

(2)ifVis a new neighbour ofN

(3)ifmsgQueuehas messages for destinationV

(4) deliver the messages toV

(5) delete the messages inmsgQueue

(6)endif

(7) exchange Node profile(np) and Encounters vector(ev)

(8)endif

(9)

(10)uponreception ofnpandevfrom nodeVdo

(11) updateCentUtilN(D) andCentUtilV(D)

(12)foralldestinationD∈msgQueuedo

(13) calculateEncoUtilV(D)

(14) calculateEncoCent(N)

(15) calculateEncoCent(V)

(16)ifEncoCent(V)

(17) addDtomfQueue(messages forwarding queue)

(18)endfor

(19)forallmessages ∈mfQueuedo

(20) send the messages toV

(21) delete the messages inN’smsgQueue

(22)endfor

(23)

(24)uponreception of transfer messages from nodeVdo

(25) add the messages toN’smsgQueue

(26) calculateEncoUtilN(D)

(1)當節(jié)點N收到節(jié)點V發(fā)來的HELLO報文后，節(jié)點N驗證節(jié)點V是否是新的鄰居節(jié)點。如果是新鄰居節(jié)點，并且節(jié)點N的消息隊列msgQueue中有發(fā)往節(jié)點V的消息，則節(jié)點N將該消息發(fā)送給節(jié)點V并在消息隊列msgQueue中刪除這些消息。然后兩個節(jié)點交換社會屬性表(np)和相遇矢量(ev)，相遇矢量描述了該節(jié)點與其它節(jié)點的歷史接觸信息。

(2)當節(jié)點N收到節(jié)點V的社會屬性表(np)和相遇矢量(ev)后，相遇矢量(ev)用于更新介數(shù)中心度效用值，計算方法見式(5)；對于消息隊列msgQueue中所有消息的目地節(jié)點D，計算節(jié)點V到節(jié)點D之間的社會相似性效用值，計算方法見式(3)，最后計算轉(zhuǎn)發(fā)效用值EncoCent，如式(6)所示。如果節(jié)點V的轉(zhuǎn)發(fā)效用高于節(jié)點N的轉(zhuǎn)發(fā)效用，則把目的節(jié)點為D的消息添加到消息轉(zhuǎn)發(fā)隊列(mfQueue)，然后將該隊列中的所有消息發(fā)送給節(jié)點V，并刪除節(jié)點N消息隊列中的相應(yīng)消息。

(3)當節(jié)點N收到節(jié)點V發(fā)送過來的消息后，消息被存入節(jié)點N的消息隊列msgQueue，然后根據(jù)該消息的目的節(jié)點信息，分別計算介數(shù)中心度效用值和社會相似性效用值并緩存在節(jié)點中。

基于以上算法的設(shè)計原則，本算法的關(guān)鍵任務(wù)是為路由的每一跳選擇最佳轉(zhuǎn)發(fā)節(jié)點，從而為移動社會網(wǎng)絡(luò)的分布是數(shù)據(jù)轉(zhuǎn)發(fā)決策提供支持。

3 性能評估

為了評估EncoCent算法的性能，我們進行了大量的仿真實驗，并將仿真實驗結(jié)果與dLife、Fresh、Prophet這3種著名算法進行了比較分析。進行對比分析的4種算法都利用了網(wǎng)絡(luò)節(jié)點的社會上下文信息，并且通過單拷貝的方式轉(zhuǎn)發(fā)消息，從而使得對比分析更有說服力。

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

仿真實驗采用移動社會網(wǎng)絡(luò)和機會網(wǎng)絡(luò)中廣泛使用的ONE(opportunistic network environment)仿真平臺[14]。為了使用仿真環(huán)境盡可以地接近真實場景，本文采用MIT實際數(shù)據(jù)集[15]作為網(wǎng)絡(luò)節(jié)點移動的軌跡數(shù)據(jù)。MIT實際數(shù)據(jù)集(MIT reality data)反映了MIT校園內(nèi)移動節(jié)點的接觸軌跡。該數(shù)據(jù)集中的節(jié)點是由97個MIT的學生和職員組成，他們每個人攜帶型號為Nokia 6600的智能手機，這97個節(jié)點在校園內(nèi)活動形成了一個移動社會網(wǎng)絡(luò)。該數(shù)據(jù)集收集了連續(xù)9個月的節(jié)點接觸情況的監(jiān)測數(shù)據(jù)，節(jié)點之間利用藍牙技術(shù)進行通信。

為了簡化問題的分析，我們假設(shè)每個節(jié)點內(nèi)存在社會屬性表和對應(yīng)的權(quán)重集合，在本文中并不討論如何獲取這些信息。本文認為在該場景中效用值EncoUtilN和效用值CentUtilN具有同等重要的作用，因此將α和β的值均設(shè)為0.5。其它仿真參數(shù)見表3。

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

每個仿真實驗運行30次，然后分別收集統(tǒng)計數(shù)據(jù)，取平均值。在對各算法的實驗數(shù)據(jù)進行統(tǒng)計分析時，我們采用如下統(tǒng)計量：投遞比率(delivery ratio)、投遞開銷(delivery cost)、路由效率(routing efficiency)，和平均時延(average latency)。投遞比率是成功到達目的節(jié)點的數(shù)據(jù)分組數(shù)與總共生成數(shù)據(jù)分組數(shù)的比值；投遞開銷是未成功投遞的消息副本總數(shù)與成功投遞到目的節(jié)點的消息總數(shù)的比值；路由效率是投遞比率與投遞開銷的比值；平均時延是數(shù)據(jù)分組被創(chuàng)建到成功到達目的節(jié)點的平時時間。

3.2 仿真結(jié)果分析

在相同的仿真環(huán)境下，本文將EncoCent算法與其它3種經(jīng)典的相關(guān)算法進行了對比實驗。實驗中，假設(shè)每個節(jié)點有足夠大的存儲空間來存儲需要轉(zhuǎn)發(fā)的消息，節(jié)點之間的帶寬足夠大使得節(jié)點相遇時足以完成數(shù)據(jù)的交換。圖2描述了4種算法隨時間變化時投遞比率的變化情況，EncoCent算法表現(xiàn)較好，緊次于投遞比率最高的Fresh算法，在第20天時投遞比較達到76%。Prophet算法在投遞比率方面表現(xiàn)最差。

從圖3可以看出，本文提出的EncoCent算法具有最小的平均投遞開銷。相比于dLife算法減少了約20%的投遞開銷。由于Prophet算法需要處理大量的歷史相遇信息，因而其投遞開銷最大。雖然在4種算法中，F(xiàn)resh算法擁有最高的投遞比率，但是該算法在投遞開銷方面卻表現(xiàn)較差。

圖2 投遞比率

圖3 投遞開銷

圖4描述了4種算法的路由效率，從圖上可以看出，EncoCent算法具有最高的路由效率，分別比dLife，F(xiàn)resh和Prophet算法提高了15%，78%和124%。這是因為，EncoCent算法在進行中繼節(jié)點選擇時，不僅考慮了節(jié)點攜帶者的社會相似性對節(jié)點移動的影響，而且還充分利用了節(jié)點介數(shù)中心度在數(shù)據(jù)轉(zhuǎn)發(fā)的橋梁作用。其它算法只考慮了某個單一方面的因素，因而只是在網(wǎng)絡(luò)性能的某個統(tǒng)計量方面有較好的表現(xiàn)。

圖4 路由效率

圖5描述了隨著仿真時間的變化，網(wǎng)絡(luò)平均時延的變化情況。從圖中可以看出在4種算法中，F(xiàn)resh算法具有最高的平均時延，可能是因為其僅僅是利用了網(wǎng)絡(luò)節(jié)點間相遇的歷史信息，而沒利用節(jié)點的社會上下文信息，從而導(dǎo)致算法的自適應(yīng)性不夠。相比于Prophet算法，dLife和EncoCent的平均時延分別減少了16.6%和19.7%。這是因為dLife和EncoCent算法在選擇中繼節(jié)點時都利用了節(jié)點攜帶者之間的社會關(guān)系，因而在平時的時延方面表現(xiàn)更好。

圖5 平均時延

本文提出的算法在數(shù)據(jù)轉(zhuǎn)發(fā)過程中充分考慮網(wǎng)絡(luò)節(jié)點攜帶者的社會上下文信息，通過研究節(jié)點的社會屬性，掌握網(wǎng)絡(luò)節(jié)點的移動規(guī)律，對這些移動規(guī)律的應(yīng)用，能大大提高數(shù)據(jù)分組的投遞效率。為了使用數(shù)據(jù)能盡快地，高效地送到目地節(jié)點，EncoCent算法充分利用了社會相似性和介數(shù)中心度兩個因素選擇最優(yōu)中繼節(jié)點。經(jīng)過上述的仿真實驗和數(shù)據(jù)分析，驗證了EncoCent算法的有效性。

4 結(jié)束語

在移動社會網(wǎng)絡(luò)中，節(jié)點攜帶者的社會上下文信息對于輔助網(wǎng)絡(luò)中的數(shù)據(jù)轉(zhuǎn)發(fā)具有非常重要的意義。本文提出的EncoCent算法結(jié)合社會相似性效用和介數(shù)中心度效用分別獲取節(jié)點間的社交強度和中心性，基于這兩個因素本文提出了一種數(shù)據(jù)轉(zhuǎn)發(fā)度量EncoCent，為最優(yōu)中繼節(jié)點的選擇提供理論依據(jù)。最后本文采用ONE仿真平臺進行了大量的仿真實驗和分析，驗證本文提出的算法的有效性和優(yōu)越性。本文的研究能促進移動社會網(wǎng)絡(luò)中數(shù)據(jù)轉(zhuǎn)發(fā)的效率與智能化，并為以人為中心的智能網(wǎng)絡(luò)和普適計算的研究提供理論參考和技術(shù)支持。