延遲容忍網絡中基于地點偏好的社會感知多播路由協議設計

陳家旭,唐亞哲,胡成臣,王換招

(西安交通大學計算機科學與技術系,710049,西安)

延遲容忍網絡中基于地點偏好的社會感知多播路由協議設計

陳家旭,唐亞哲,胡成臣,王換招

(西安交通大學計算機科學與技術系,710049,西安)

根據延遲容忍網絡中人類運動體現出的地點偏好特征,提出了一個社會感知路由協議,并采用了點到社區的多播方式。相應地設計了節點分布式地獲取社區及其地理位置的方法,其中的分布式社區檢測算法獨立于路由協議,并具有靈活、準確的特征。協議以文中發掘出的新的社會感知量——地點偏好為中心,將消息不斷地向目的社區所在的地理位置推進,在消息抵達社區成員節點之后利用社區結構所蘊含的強社會關系在社區內部繼續傳送消息,并激活消息復制機制。本協議基于社會網絡分析,從地理位置的角度準確預測節點運動從而進行路由。實驗結果表明:本協議與兩個未采用地點偏好的社會感知路由協議相比,在不增加協議開銷的情況下提升了至少10%的發包成功率;在社區及其地理位置已知的場景下具有更好的性能,在保持最高的發包成功率的同時縮減了50%以上的開銷。

延遲容忍網絡;地點偏好;社會感知;社區

在延遲容忍網絡中,由于缺乏端到端鏈路,路由協議通常采用存儲-攜帶-轉發的傳輸模式,即借助節點運動造成的相遇來完成消息的傳輸。當前延遲容忍網絡的場景大多是由人類攜帶的移動通信設備所組成,理解人類運動并加以利用可以有效提升路由協議的性能。人們喜歡訪問對其具有吸引力的少數幾個地點[1],并在這些地點停留較長時間。人們對于這些地點的頻繁訪問和較長時間的停留在本文中被稱為地點偏好。地點偏好是造成人類運動的接觸間隔時間呈冪律-指數分布的根本原因[2],因此在路由協議設計中把握人類運動中地點偏好的特點,可以更準確地預測到節點之間的相遇,從而提升協議性能。

當前對延遲容忍網絡路由協議的研究[3-8]雖然也注意到了理解人類運動的重要性,但地點偏好的特征從未得到發掘與應用。本文針對此問題,圍繞地點偏好并基于社區結構來設計路由協議。社區是社會網絡中的重要概念,在由人類組成的延遲容忍網絡中,具有相同興趣的人們以極大的可能性共存于相近的地理位置,從而彼此之間產生較多的相遇而形成社區[8]。上述地理位置相當于對社區成員有較大的吸引力,地點偏好特征依然存在。容易看出,處于同一社區的人更容易彼此碰面,反之,擁有一定程度的社會關系的人群才會形成社區。因此,社區內消息的傳輸將比全網范圍內消息傳輸更加便利。此外,社區的概念非常有利于在路由協議的設計中采用多播傳輸的模式,與單播傳輸模式相比,多播傳輸可明顯提高消息傳輸效率。本協議即采用了點到社區的多播方式。協議的原理是將消息不斷地向目的社區所對應的地理位置推進,由于社區的所有成員都是消息的目的節點,因此理論上可以提升協議的發包成功率,然而為得到此地理位置信息,會產生額外的開銷,表現在需要先得到網絡的社區結構,并由各社區成員所偏好訪問的地點坐標近似估算出社區對應的地理位置。本文將k-clique社區檢測算法[9]分布化,設計了相匹配的控制信息交換策略,根據這些信息分布式地估算出社區對應的地理位置,從而能夠達到與未采用地點偏好的社會感知協議相比,在減少或不增加協議開銷的基礎上提高協議的發包成功率。在社區及其地理位置已知的場景下,本協議將不用進行額外的控制信息交換而直接使用社區偏好地點的地理位置信息,可以在提升發包成功率的同時顯著降低協議開銷。

1 分布式社區檢測

文獻[9]中提出了采用k-clique社區檢測算法從社會網絡中發現社區,然而運行k-clique需要全網的接觸時長矩陣。本節介紹采用控制包輔助的方式來幫助各節點在本地搜集全局相關信息,從而實現分布式的k-clique社區檢測算法。

節點n在本地保存它與全部節點的接觸時長Dn,它所知道的全網所有節點的接觸時長矩陣Mn以及用來存儲社區檢測結果的Rn。當節點n遇到其他節點(例如節點i)時,彼此交換控制信息。節點n產生的控制信息包含節點id和Mn。在節點n產生控制信息之前,用最新的Dn信息去更新本地的Mn,以保證所交換的接觸時長矩陣中含有當前節點的最新接觸時長信息。在節點n收到對方的控制信息后,用本地的Mn與收到的Mi中每一個元素的較大值來更新本地的Mn。節點n通過與其他節點不斷地進行控制信息交換來保證本地的Mn含有它所能得到的盡可能準確的全網接觸時長信息,以便隨時在本地執行k-clique社區檢測算法,具體的偽代碼如下。

for alld∈Mn

ifd>=Tththen∥Tth為接觸時長的權重閾值

d=1

else

d=0

end if

end for

在Mn中找到所有大小為k的完全子圖(k-clique)

for allk-clique ∈Mn

Rn←k-clique

if ?k′-clique s.t.(k′-clique中的節點數量) ∩ (Rn里任意一個大小為k的完全子圖中的節點數量)=k-1 then

Rn←(在k′-clique中但不在此大小為k的完全子圖中的節點)

end if

end for

刪除Rn中重復的社區

雖然k-clique社區檢測算法復雜度較大,但在應用于較少節點組成的實驗場景中時(100人以下,例如文獻[3]中用來運行k-clique的若干實際場景)并非大規模網絡,因此暫不考慮算法復雜度帶來的影響。

執行k-clique所需信息已存于節點本地,且隨網絡運行不斷更新,因此本文算法具有靈活性,即可以在任何時間運行并多次運行。本文算法檢測結果的準確性將通過把本文算法對人類真實運動數據[10]的檢測結果與原k-clique算法及Hui等在文獻[11]中提出的另一種分布式k-clique社區檢測算法的檢測結果進行對比驗證。使用Jaccard指數來描述兩個社區結構(Γj和Γi)的相似性,即

(1)

式中:Γi是社區i的成員集合,|Γi|為集合Γi的勢,值為Γi中成員的數量。這里Γi為原k-clique社區檢測算法檢測出的社區,Γj則是被評估的分布式k-clique社區檢測算法所檢測出的社區。對于通過原k-clique算法所檢測到的規模最大的社區內的所有成員,均用本文提出的分布式k-clique算法與文獻[11]中的分布式k-clique算法分別對自己所在社區進行檢測,并將結果與原k-clique社區檢測算法進行比較并計算出Jaccard指數,如圖1所示。檢測中采用的運動數據[10]是2006年INFOCOM會議采集到的,包括了78個攜帶移動通信設備的與會者在3天的相遇情況。3個k-clique算法參數取值相同,即k=4,接觸時長的權重閾值為10ks。

圖1 兩種分布式k-clique社區檢測算法的對比

圖1中,橫坐標代表此圖所示社區的成員節點id,為原k-clique算法的檢測結果。縱坐標分別是本文提出的分布式k-clique算法及文獻[11]提出的分布式k-clique算法與原k-clique算法之間的Jaccard指數。由圖1可見,本文所設計的分布式k-clique社區檢測算法,在節點檢測自己所在社區的情況下,基本上可以得到與原k-clique社區檢測算法完全一致的結果。這是因為社區內節點相遇頻繁,能夠及時并準確地更新社區內成員的接觸信息。文獻[11]中的分布式算法顯示出與原k-clique算法較明顯的偏差。

2 路由協議設計

有了分布式k-clique社區檢測算法,還需要設計相匹配的控制信息交換策略,才能使各節點根據交換所得信息分布式地估算出社區對應的地理位置,從而基于地點偏好實現路由協議。分布式k-clique算法和控制信息交換策略雖然在功能上有所區分,但實際上可以由同樣的控制包攜帶,而分布式社區地理位置生成算法也是緊跟在分布式k-clique之后,在各節點本地執行,因此這兩個功能可以在同一模塊中實現。節點n只需在本地同時保存最常訪問的若干地點的坐標及其概率的數據結構Cn以及它所知道的所有節點的Cx(x為任意節點)信息的矩陣Fn,在與其他節點相遇而進行控制信息交換時,將Cn附在它產生的控制信息中。在收到節點i發來的控制信息之后,將Fn中每一個節點的最常訪問地點的坐標及概率進行更新,將Fi與Fn中對應節點的地點偏好信息按照權重重新排序,保留權重最大的若干個。

在節點n進行完分布式k-clique算法之后,根據所檢測到的各社區的所有成員的Cy(y為社區成員節點id)信息(從Fn中讀取),取Cy中各熱點的加權平均值近似地作為該社區在地理上的位置,其中權重值為對應的節點訪問該熱點的概率。至此,節點n能夠大致估算出網絡中存在的社區及每個社區對應的地理位置所在。估算此地理位置的偽代碼如下。

for allRn中的社區

for all 此社區的成員節點

L←Fn中這些節點對應信息的加權平均值

end for

end for

在上述準備工作的基礎上,可以設計并實現基于地點偏好的路由協議,協議在兩節點相遇時生效。為使用消息的目的社區對應的地理位置(以L表示)信息來實現地點偏好的設計,相遇的兩節點應先交換Landmark Vector控制信息。節點n產生的Landmark Vector包括了節點id;節點n下一次停止運動所在的地點dest(n);節點n在從當前位置到dest(n)的運動中所能到達的與L的最近距離distance(n,L);節點n所處的社區標簽com(n);以及對于n緩存中的每一個消息m的id及其目的社區標簽label(m)。當兩個節點相遇時,它們首先銷毀各自緩存中所有超出生存時間的消息,然后交換Landmark Vector。對于兩個節點緩存中的每一個消息,如果對方節點是此消息的目的節點并且尚未收到過此消息,那么應將此消息復制給對方(留副本),收到該消息的節點將此消息id記錄到已收到消息的id集合中并投遞到(不留副本)之上的應用層,然后根據協議選擇當前消息下一跳的中繼節點。

協議采用了點到社區的多播方式,即目的社區的所有成員都是消息的目的節點。消息在生成的時候會標記上其目的社區的標簽label(m),以此來協助節點辨別是否應接收該消息。同時,節點n在本地對自己所在社區的標簽以com(n)表示。通過這種方式,節點可以判斷自己是否應該接收某消息。協議主體思想的偽代碼如下:

if com(i)=label(m) and com(j)=label(m) then

copy(m)

end if

if com(i)=label(m) and com(j)≠label(m) then

new_carrier(m)←i

end if

if com(i)≠label(m) and com(j)=label(m) then

new_carrier(m)←j

end if

if com(i)≠label(m) and com(j)≠label(m) then

if distance(i,L)

new_carrier(m)←i

end if

if distance(i,L)>distance(j,L) then

new_carrier(m)←j

end if

end if

其中copy(m)代表將消息m從當前的攜帶者復制到另一個節點中,而new_carrier(m)代表此次相遇后消息m新的攜帶者,即另一方不應再攜帶m。

該策略決定了消息在傳輸過程中每一跳的中繼節點。可見在本協議中,“消息目的社區的成員節點”比“地點偏好”有更高的優先級。因為“消息目的社區的成員節點”意味著該節點與非社區成員節點相比,有更大的可能性遇到目的社區的其他成員節點。僅當相遇的兩節點都不屬于消息目的社區的成員節點時,協議才依照“地點偏好”選擇消息的下一跳中繼節點,即由兩節點中在當前運動階段可以到達更接近L的節點來攜帶消息。這樣的設計原理可保證將消息不斷地向其目的社區所在的地理位置推進,直到其中一個目的節點收到此消息。之后由此節點攜帶消息,并在遇到同樣屬于目的社區的節點時激活消息的復制機制(上述偽代碼的第2行),以加快消息的傳播。

3 模擬及性能評估

本節對上一節所提出的路由協議進行了編程實現,并與兩個未使用地點偏好的社會感知路由協議SocialCast[8]和SGBR[7]進行了性能對比。其中SocialCast采用的是發布/訂閱架構的多播模式,假設了社區與興趣之間的一一映射關系,因此SocialCast可以直接采用本文所定義的點到社區的多播模式。SGBR雖然采用了單播的方式,但由于各個消息獨立選擇路由,將SGBR擴展為本文中的點到社區的多播模式不會影響SGBR的性能。

采用開銷和發包成功率兩個量來衡量路由協議的性能。開銷指成功發送一個數據包所需要的代價,表征了路由協議的效率,計算式為c=(Rc+Dd)/Rd,其中Rc為收到的控制包數,Dd為生成的數據包副本數,Rd為收到的數據包數。發包成功率是指發送出的數據包被成功接收的概率,衡量了路由協議的有效性,計算式為p=Rd/Gd,其中Gd為生成的數據包數。

模擬中使用SWIM[1]來刻畫節點運動,因為SWIM是一個優秀的人類運動模型,表現在其能夠重現與實際人類運動相匹配的統計量,例如接觸間隔時間、接觸時長和接觸數量;能夠還原指定網絡場景下的社區結構;能夠用來準確預測路由協議在真實場景下的性能[1]。網絡區域為5 km×5 km,其中有100個節點,每個節點的傳輸半徑為250m,保證了稀疏的節點密度從而形成延遲容忍網絡的環境。SWIM的相關系數取值為0.25,停止時間服從[10s,1 440s]范圍內斜率為1.45的冪律分布,運動時間為10s。模擬時間設置為3d(259 200s)。

為防止SWIM生成不明確的社會關系,節點的家并非在網絡區域上隨機平均選取。在100個節點中隨機選擇20個節點,令它們的家相距較近,從而這些節點中的大部分將屬于同一社區,且此社區的規模為20左右。為給SWIM模型以充分的時間來形成穩定的社區結構,在第200ks時,系統進行k-clique社區檢測算法,之后賦給規模最大的社區一個標簽。在第200ks時,各節點執行分布式k-clique社區檢測算法。Δt之后,網絡中開始產生數據包。其中Δt設為較小的值即可,并不影響結果。發包持續時間為1 ks,發包間隔為60s,與文獻[8]中相同,隨機選擇半數的節點為發包者,包中附有標記著目的社區的標簽,該社區的所有成員都將是接收者。由于發包節點是從所有節點之中隨機選取,目的節點也主要是由初始被設置為離家較近的隨機選擇的20個節點中的大部分組成,因此這樣設定可以保證包的源節點到目的節點之間的一種隨機的社會關系,而不會影響到協議的性能。k-clique算法的k取值為4,接觸時長的權重閾值為60ks。假設所有節點緩存足夠大。實驗在用C++編寫的離散事件模擬器中運行。

路由協議中包與其副本的總數r在本文提出的協議中設置為4,在SocialCast中設置為5,而在SGBR中設置為32。本協議并不依賴于復制機制,故取3個協議中的最小值,由于采用了平均分配副本數量的機制(即相遇雙方節點在復制包的時候各持有半數的包副本,因此r需設置為2的冪次方),故r取值為4。SocialCast對復制機制的依賴性次之,同時為避免SocialCast與本協議對比時由于r值過小的原因而對協議性能造成的影響,故r取略大于4的值。SGBR較依賴復制機制并采用了平均分配副本數量的機制,從而r設為較大值32(即25)。SocialCast中的其他參數如ωcdc、ωcol、λ和ε(參數定義見文獻[8])都取了與文獻[8]中相同的值。同樣地,SGBR中的其他參數如α、γ、Cth和Dth(參數定義見文獻[7])也都取了與文獻[7]中相同的值。對于每個實驗數據,取20次運行結果的平均值,其中每次運行都采用了不同的隨機數種子。協議性能對比結果如圖2、圖3所示。

圖2 3個路由協議的開銷

圖3 3個路由協議的發包成功率

雖然延遲容忍網絡中消息傳遞對運動的依賴性導致Rd直接受節點運動的影響,但是在運動模型及參數都確定的情況下,可以認為Rd是運動模型的無關變量。然而,協議對Rd卻可產生較大影響。假設在不考慮生存時間的情況下數據包到達目的節點的平均延遲為d,協議的參數中將數據包的生存時間設置為H,那么Rd與H和d的關系如下:當H≤d時,大部分數據包在還沒有到達端到端延遲期望值的情況下就已經因為到達生存時間而被銷毀,這將導致很低的Rd值。從H>d開始,Rd值將顯著增加,但當H增加到一定程度之后,社區中相對可達的節點都已經收到了數據包,Rd值隨H的增幅又將變緩慢,因而開銷c=(Rc+Dd)/Rd≈Rc/Rd在一定范圍內呈現出如圖2所示的與Rd大致成反比的關系。同理,發包成功率p=Rd/Gd中,Gd在模擬參數指定的情況下為常量,因此p與Rd成正比。結合Rd與H的關系,即有圖3所描述的發包成功率隨生存時間的變化情況。

前述場景中社區對應的地理位置為未知信息,并通過節點交換控制信息分布式地獲得。實際上,在其他場景,例如人們熟悉的環境中,社區及其對應的地理位置為已知信息,不再需要分布式社區檢測與控制信息交換,本協議的開銷可以大大降低,從而相對于其他協議體現出更明顯的優勢。作者同樣進行了這種場景下的模擬,即將運動模型從SWIM換成HCMM[12]再次觀測3個協議的性能。HCMM刻畫了社區及對應地理位置已知的網絡環境,設置模擬時間為28 800s,發包時間為3～4 ks,運動速度服從1～6 m/s的平均分布,停止時間為10s,網絡中社區數量為4,本協議中包不再采用復制機制,其他參數均與上述場景相同。限于篇幅,此處并未給出具體圖示,然而模擬結果表明在不需要主動獲得社區及所對應的地理位置的場景下,與SocialCast及SGBR相比,本協議可以在保持最高發包成功率的基礎上縮減協議開銷達50%以上。

4 結 論

針對延遲容忍網絡中人類運動的地點偏好特征,提出了一個社會感知多播路由協議。協議將消息逐漸向目的社區所在的地理位置傳送,當到達其中一個目的節點后,利用社區之間的強社會關系,由此節點一直攜帶并激活復制機制,以便于其他目的節點收到消息。實驗結果表明,與兩個未采用地點偏好的社會感知路由協議相比,本協議在不增加開銷的情況下提升了發包成功率,而在無需主動獲得社區地理位置信息的場景中,可在保持最高發包成功率的同時大幅降低開銷。

[1] KOSTA S,MEI A,STEFA J.Large-scale synthetic social mobile networks with SWIM [J].IEEE Transactions on Mobile Computing,2014,13(1): 116-129.

[2] MAITI R R,MALLYA A,GANGULY N.Characterizing Mobility Models for Human Movement [J/OL].(2013-02-19) [2013-10-15].http:∥web.engr.illinois.edu/～amallya2/trial/aCleanerWebsite/files/MobilityModel_CHANTS.pdf.

[3] HUI Pan,CROWCROFT J,YONEKI E.Bubble rap: social-based forwarding in delay-tolerant networks [J].IEEE Transactions on Mobile Computing,2011,10(11): 1576-1589.

[4] GAO Wei,CAO Guohong.User-centric data dissemination in disruption tolerant networks [C]∥Proceedings of the 30th Conference on Computer Communications.Piscataway,NJ,USA: IEEE,2011: 3119-3127.

[5] LI Feng,WU Jie.Mops: providing content-based service in disruption-tolerant networks [C]∥Proceedings of the 29th IEEE International Conference on Distributed Computing Systems.Piscataway,NJ,USA: IEEE,2009: 526-533.

[6] BULUT E,SZYMANSKI B K.Friendship based routing in delay tolerant mobile social networks [C]∥Proceedings of the Global Telecommunications Conference.Piscataway,NJ,USA: IEEE,2010: 1-5.

[7] ABDELKADER T,NAIK K,NAYAK A,et al.SGBR: a routing protocol for delay tolerant networks using social grouping [J].IEEE Transactions on Parallel and Distributed Systems,2013,24(12): 2472-2481.

[8] COSTA P,MASCOLO C,MUSOLESI M,et al.Socially-aware routing for publish-subscribe in delay-tolerant mobile ad hoc networks [J].IEEE Journal on Selected Areas in Communications,2008,26(5): 748-760.

[9] PALLA G,DERNYI I,FARKAS I,et al.Uncovering the overlapping community structure of complex networks in nature and society [J].Nature,2005,435(7043): 814-818.

[10]HUI Pan,SCOTT J,CHAINTREAU A.CRAWDAD metadata: cambridge/haggle/imote/infocom2006 [EB/OL].(2009-05-29) [2013-07-30].http:∥crawdad.cs.dartmouth.dartmouth.edu/cambridge/haggle/imote/infocom2006.

[11]HUI Pan,YONEKI E,CHAN S Y,et al.Distributed community detection in delay tolerant networks [C]∥Proceedings of the 2nd ACM/IEEE International Workshop on Mobility in the Evolving Internet Architecture.New York,USA: ACM,2007: 7.

[12]BOLDRINI C,PASSARELLA A.HCMM: modeling spatial and temporal properties of human mobility driven by users’ social relationships [J].Computer Communications,2010,33(9): 1056-1074.

(編輯 武紅江)

DesignofaSocial-AwareMulticastRoutingProtocolBasedonLocationPreferenceinDelayTolerantNetworks

CHEN Jiaxu,TANG Yazhe,HU Chengchen,WANG Huanzhao

(Department of Computer Science and Technology,Xi’an Jiaotong University,Xi’an 710049,China)

A social-aware routing protocol utilizing a ‘one-to-community’ multicast scheme is proposed.The protocol is based on the characteristics of location preference in human mobility in delay tolerant networks.A distributed method is designed to obtain the community structure and its geographical position,where the distributed community detection algorithm is independent of the routing protocol and has features of flexibility and accuracy.The protocol concentrates on the exploited social-aware metric,namely location preference,and forwards messages towards the geographical position of the destination community.Once the message arrives one of the destination nodes,strong social relations inside the destination community can be utilized to accelerate the message’s arrival at other destination nodes by means of duplicating replicas.The protocol accurately predicts node mobility in geography based on social network analysis.Simulation results given by comparing the proposed protocol with two existing social-aware routing protocols without using location preference show that the packet delivery ratio raises at least 10% without increasing the cost.It is also observed that the proposed protocol has better performance in the scenario where communities and their geographical positions are known.The cost reduces more than 50% while the packet delivery ratio is the highest.

delay tolerant networks; location preference; social-aware; community

2014-01-12。

陳家旭(1983—),男,博士生;胡成臣(通信作者),男,副教授。

國家自然科學基金資助項目(61170245)。

時間:2014-05-30

10.7652/xjtuxb201406003

TP393

:A

:0253-987X(2014)06-0013-06

網絡出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20140530.1615.003.html