畢俊蕾，李致遠(yuǎn)

（1.江蘇大學(xué)信息化中心，江蘇 鎮(zhèn)江 212013；2.江蘇大學(xué)計(jì)算機(jī)科學(xué)與通信工程學(xué)院，江蘇 鎮(zhèn)江 212013；3.江蘇大學(xué)新一代信息技術(shù)產(chǎn)業(yè)研究院，江蘇 鎮(zhèn)江 212013）

1 引言

機(jī)會(huì)社交網(wǎng)絡(luò)（OSN,opportunistic social networking）是一種新型的移動(dòng)社交網(wǎng)絡(luò)[1]。與基于移動(dòng)通信網(wǎng)絡(luò)（如3G、4G 等）的在線(xiàn)移動(dòng)社交應(yīng)用不同[2]，OSN 網(wǎng)絡(luò)中節(jié)點(diǎn)是利用短距離無(wú)線(xiàn)通信技術(shù)（如Wi-Fi、藍(lán)牙等）進(jìn)行機(jī)會(huì)式多跳通信。OSN在應(yīng)用過(guò)程中所面臨的重要問(wèn)題之一是查詢(xún)消息路由算法的研究。查詢(xún)消息路由算法的設(shè)計(jì)目標(biāo)是高效地發(fā)送查詢(xún)消息到目的節(jié)點(diǎn)（即能提供請(qǐng)求響應(yīng)的節(jié)點(diǎn)）。本文將現(xiàn)有的查詢(xún)消息路由方法分為兩類(lèi)：擴(kuò)散式查詢(xún)路由方法[3-4]和基于社會(huì)特性查詢(xún)的路由方法[5-13]。

擴(kuò)散式查詢(xún)消息路由方法[3]最早出現(xiàn)在連接易中斷的無(wú)線(xiàn)網(wǎng)絡(luò)中，當(dāng)該方法應(yīng)用到OSN 環(huán)境時(shí)，需要每個(gè)節(jié)點(diǎn)攜帶一張消息列表。當(dāng)2 個(gè)節(jié)點(diǎn)相遇時(shí)，相互交換各自的消息列表。節(jié)點(diǎn)對(duì)比對(duì)方的消息列表后，相互交換自身所沒(méi)有的消息數(shù)據(jù)。顯然，擴(kuò)散式查詢(xún)消息路由方法可以獲得最優(yōu)的查詢(xún)成功率，但其指數(shù)級(jí)增加的消息副本數(shù)量使該方法的可擴(kuò)展性較差?；谏鐣?huì)特性的查詢(xún)消息路由方法是利用相遇歷史頻度高或中心度高的節(jié)點(diǎn)幫助進(jìn)行查詢(xún)消息轉(zhuǎn)發(fā)[5]。此外，為了提高查詢(xún)算法的可擴(kuò)展性，社會(huì)化社區(qū)結(jié)構(gòu)和理論也常被采用。事實(shí)上，相同興趣社區(qū)內(nèi)部的節(jié)點(diǎn)較社區(qū)外部的節(jié)點(diǎn)有更高的相遇概率，然而，這種方案存在的問(wèn)題在于實(shí)際應(yīng)用中所構(gòu)造邏輯社會(huì)社區(qū)中節(jié)點(diǎn)間的邏輯連接關(guān)系與物理網(wǎng)絡(luò)中節(jié)點(diǎn)間的物理連接關(guān)系不匹配，這種拓?fù)溥m配現(xiàn)象會(huì)導(dǎo)致查詢(xún)消息無(wú)法及時(shí)到達(dá)目的節(jié)點(diǎn)。

為了解決上述查詢(xún)路由方法中存在的各種局限性，本文提出了基于時(shí)變興趣社區(qū)的查詢(xún)消息路由算法（TIMER,time-variant interest community based query message routing algorithm），主要工作如下。

1)對(duì)2 個(gè)知名的移動(dòng)社交網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行了分析，發(fā)現(xiàn)移動(dòng)節(jié)點(diǎn)在時(shí)間和空間上的關(guān)聯(lián)性和規(guī)律性。

2)在1)的基礎(chǔ)上，提出了時(shí)變興趣社區(qū)模型，并描述了時(shí)變興趣社區(qū)的建立過(guò)程。

3)在2)提出的時(shí)變興趣社區(qū)結(jié)構(gòu)上，設(shè)計(jì)了時(shí)間復(fù)雜度為O(nlogn)查詢(xún)消息路由算法，并對(duì)算法的性能進(jìn)行了評(píng)估。

2 相關(guān)工作

本節(jié)主要對(duì)擴(kuò)散式查詢(xún)消息路由算法和基于社會(huì)特性的查詢(xún)消息路由算法的原理進(jìn)行描述，并分析其優(yōu)缺點(diǎn)。

1)擴(kuò)散式查詢(xún)消息路由算法

文獻(xiàn)[3]首次在部分連通的Ad Hoc 網(wǎng)絡(luò)中提出擴(kuò)散式查詢(xún)消息路由算法Epidemic。Epidemic 算法利用節(jié)點(diǎn)的移動(dòng)來(lái)傳遞消息數(shù)據(jù)，即當(dāng)節(jié)點(diǎn)相遇時(shí)，它們將自身攜帶的消息數(shù)據(jù)傳送給對(duì)方。Epidemic 算法通過(guò)消息快速?gòu)?fù)制的方式將查詢(xún)消息擴(kuò)散到全網(wǎng)，一定程度上保證了消息的投遞成功率，但同時(shí)也造成了消息副本拷貝的泛濫，致使OSN 網(wǎng)絡(luò)資源利用率降低，查詢(xún)消息的中途丟失率增加。針對(duì)Epidemic 算法的不足，SW（Spray&Wait）路由算法有效地控制了網(wǎng)絡(luò)中消息副本的數(shù)量[4]。其原理如下。設(shè)S發(fā)送消息m給目的節(jié)點(diǎn)D，算法的輸入是消息在網(wǎng)絡(luò)中的最大副本數(shù)L。當(dāng)S遇到節(jié)點(diǎn)G時(shí)，就轉(zhuǎn)發(fā)消息m給G，并將最大副本數(shù)L減1。如果G為目的節(jié)點(diǎn)，則消息投遞成功，此次路由結(jié)束；如果G中繼節(jié)點(diǎn)，則重復(fù)上述過(guò)程，直到消息傳遞到目的節(jié)點(diǎn)為止。Binary SW 算法是SW算法的改進(jìn)版本，它的原理是每次將消息傳遞給G時(shí)，將自身的最大副本數(shù)降低為，而G的副本數(shù)同樣設(shè)為，直到將查詢(xún)消息傳遞給目的節(jié)點(diǎn)為止。SW 算法的問(wèn)題在于副本數(shù)L的設(shè)置，副本數(shù)L設(shè)置較大則會(huì)存在Epidemic 算法的問(wèn)題，若設(shè)置較小，則會(huì)降低消息的投遞成功率，增大投遞的時(shí)延。

2)基于社會(huì)特性的查詢(xún)消息路由算法

基于社會(huì)特性的查詢(xún)消息路由算法思想是利用節(jié)點(diǎn)間歷史交互信息對(duì)未來(lái)的節(jié)點(diǎn)行為進(jìn)行預(yù)測(cè)。這類(lèi)路由算法中的代表性算法包括PRoPHET（probabilistic routing protocol using history of encounters and transitivity）[5]、SimBet（similarity and betweenness centrality）[6]和ICR（interest community routing）[7]。PRoPHET 通過(guò)節(jié)點(diǎn)間的歷史相遇信息來(lái)估計(jì)傳輸概率，它使用傳輸預(yù)測(cè)值P(a,b)作為節(jié)點(diǎn)a和b的路由度量，表示將消息從節(jié)點(diǎn)a傳遞到節(jié)點(diǎn)b的成功概率。若目標(biāo)節(jié)點(diǎn)為d，節(jié)點(diǎn)a與b相遇，僅當(dāng)P(b,d)≥P(a,d)時(shí)，節(jié)點(diǎn)a才將消息轉(zhuǎn)發(fā)給節(jié)點(diǎn)b。SimBet 路由節(jié)點(diǎn)的社會(huì)性度量是由節(jié)點(diǎn)相似性和局部介數(shù)中心性加權(quán)求和得到的。其中，節(jié)點(diǎn)相似性表示當(dāng)前節(jié)點(diǎn)與目的節(jié)點(diǎn)的共同鄰居數(shù)，共同鄰居數(shù)越高，節(jié)點(diǎn)間的相似性越大；局部介數(shù)中心性則反映了節(jié)點(diǎn)在網(wǎng)絡(luò)中重要程度，節(jié)點(diǎn)介數(shù)越大作為中繼轉(zhuǎn)發(fā)時(shí)成功的概率越高。當(dāng)節(jié)點(diǎn)b的SimBet 值大于節(jié)點(diǎn)a的SimBet 值時(shí)，節(jié)點(diǎn)a將消息傳遞給節(jié)點(diǎn)b。ICR 研究了節(jié)點(diǎn)的興趣，給出了節(jié)點(diǎn)的興趣相似度計(jì)算模型，將興趣相似的節(jié)點(diǎn)組成興趣社區(qū)，然后在社區(qū)內(nèi)和社區(qū)間分別設(shè)計(jì)了消息路由算法。評(píng)估結(jié)果顯示社區(qū)組織結(jié)構(gòu)確實(shí)可以有效地提高消息路由的性能。然而，PRoPHET、SimBet 和ICR 理論模型和實(shí)驗(yàn)評(píng)估都是基于節(jié)點(diǎn)的隨機(jī)運(yùn)動(dòng)展開(kāi)，忽略了節(jié)點(diǎn)行為在時(shí)間和空間上的關(guān)聯(lián)關(guān)系，模型的性能受制于節(jié)點(diǎn)移動(dòng)的隨機(jī)性，從而使節(jié)點(diǎn)相遇所需的等待時(shí)延仍比較高。

3 移動(dòng)用戶(hù)行為時(shí)空規(guī)律性和關(guān)聯(lián)性分析

本文研究的機(jī)會(huì)社交網(wǎng)絡(luò)運(yùn)行的場(chǎng)景是在學(xué)術(shù)機(jī)構(gòu)、辦公場(chǎng)所等區(qū)域，這些場(chǎng)景下的科研人員及其他工作人員構(gòu)建起了本文研究的機(jī)會(huì)社交網(wǎng)絡(luò)。為了研究上述場(chǎng)景下節(jié)點(diǎn)的行為特征、分析節(jié)點(diǎn)的行為規(guī)律，選取了與上述物理場(chǎng)景相近的2 個(gè)代表性數(shù)據(jù)集——copelabs/usense[14]和 upb/hyccups[15]進(jìn)行統(tǒng)計(jì)分析。copelabs/usense 數(shù)據(jù)集是以人們?nèi)粘；顒?dòng)為周期（一個(gè)周期時(shí)長(zhǎng)24 h），參與的移動(dòng)節(jié)點(diǎn)數(shù)為72 個(gè)，采集終端為三星Galaxy S3 智能手機(jī)，數(shù)據(jù)采集和預(yù)處理軟件是安裝在智能手機(jī)上的應(yīng)用軟件NSense，節(jié)點(diǎn)的組網(wǎng)采用無(wú)線(xiàn)Ad Hoc 方式（Wi-Fi 和藍(lán)牙），節(jié)點(diǎn)的活動(dòng)范圍是辦公區(qū)域（實(shí)驗(yàn)室和會(huì)議討論區(qū)）、休閑娛樂(lè)區(qū)域及家中，數(shù)據(jù)采集的時(shí)間間隔為1 min，數(shù)據(jù)收集時(shí)間總時(shí)長(zhǎng)為50 h。upb/hyccups 數(shù)據(jù)集來(lái)源于布加勒斯特理工大學(xué)校園內(nèi)，參與的移動(dòng)節(jié)點(diǎn)數(shù)為78個(gè)，采集的終端采用Android 智能手機(jī)（Android系統(tǒng)版本號(hào)分別是4.2 和5.1）數(shù)據(jù)收集應(yīng)用軟件為基于Wi-Fi 的AllJoyn 框架，數(shù)據(jù)采集的時(shí)間間隔為5 min，數(shù)據(jù)收集時(shí)長(zhǎng)為63 d。

圖1～圖3 分別展示了24 h 內(nèi)用戶(hù)在時(shí)間和空間維度上的關(guān)聯(lián)和規(guī)律性，數(shù)據(jù)來(lái)自于文獻(xiàn)[14]。圖中橫坐標(biāo)表示用戶(hù)ID，縱坐標(biāo)表示一天時(shí)長(zhǎng)，即24 h。圖1 是用戶(hù)在辦公區(qū)域的在線(xiàn)時(shí)間數(shù)據(jù)統(tǒng)計(jì)結(jié)果。如圖1 所示，大多數(shù)節(jié)點(diǎn)的工作時(shí)間為8:00～18:00，少部分節(jié)點(diǎn)的工作時(shí)間為晚上和下午2 個(gè)時(shí)段，這和科研人員的作息是相關(guān)的。圖2 表示的是節(jié)點(diǎn)在休閑娛樂(lè)區(qū)域的在線(xiàn)時(shí)間統(tǒng)計(jì)結(jié)果，從圖中不難發(fā)現(xiàn)，大多數(shù)節(jié)點(diǎn)在白天時(shí)段的休息時(shí)間為12:00～13:00 或18:00～22:00，其中，中午休息時(shí)間較短，通常為1 h，少數(shù)節(jié)點(diǎn)選擇在凌晨活動(dòng)。圖3 為節(jié)點(diǎn)在家中出現(xiàn)的時(shí)間，大多數(shù)節(jié)點(diǎn)在家中時(shí)間為00:00～8:00。

綜上所述，對(duì)于8:00～17:30 大多數(shù)節(jié)點(diǎn)出現(xiàn)在辦公區(qū)域，如會(huì)議室和辦公討論區(qū)。對(duì)于晚上時(shí)間段，部分節(jié)點(diǎn)選擇在辦公區(qū)域，部分節(jié)點(diǎn)選擇在家中，部分節(jié)點(diǎn)選擇去休閑娛樂(lè)區(qū)域，其逗留時(shí)間比較靈活，有長(zhǎng)有短，依賴(lài)于節(jié)點(diǎn)的生活作息習(xí)慣。

圖1 節(jié)點(diǎn)在辦公區(qū)域的時(shí)段統(tǒng)計(jì)

圖2 節(jié)點(diǎn)在休閑娛樂(lè)區(qū)的時(shí)段統(tǒng)計(jì)

圖3 節(jié)點(diǎn)在家中的時(shí)段統(tǒng)計(jì)

圖4 和圖5 分別展示了布加勒斯特理工大學(xué)校區(qū)內(nèi)節(jié)點(diǎn)的興趣及其演變過(guò)程，數(shù)據(jù)來(lái)自于文獻(xiàn)[15]。圖4 中的橫坐標(biāo)和縱坐標(biāo)均表示用戶(hù)ID。當(dāng)用戶(hù)屬于朋友關(guān)系且屬于同一個(gè)興趣組時(shí)，標(biāo)記為1，即圖中的圓點(diǎn)。經(jīng)過(guò)統(tǒng)計(jì)，發(fā)現(xiàn)從數(shù)據(jù)采集開(kāi)始到數(shù)據(jù)采集結(jié)束，因?yàn)榕d趣相同而成為朋友關(guān)系的比例增加了32.4%。圖5 是圖4 節(jié)點(diǎn)關(guān)系的演變，每一個(gè)點(diǎn)表示移動(dòng)用戶(hù)，每一條邊表示節(jié)點(diǎn)之間的關(guān)系。有著共同興趣的用戶(hù)更傾向于加入同興趣的社區(qū)，并成為朋友關(guān)系，之后會(huì)相互共享彼此感興趣的信息和資源。通過(guò)興趣聚類(lèi)，可以有效地提高查詢(xún)消息分發(fā)的效率。

圖4 節(jié)點(diǎn)間興趣關(guān)系統(tǒng)計(jì)結(jié)果

圖5 節(jié)點(diǎn)興趣關(guān)系圖演變

綜合以上實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，移動(dòng)節(jié)點(diǎn)的擁有者賦予了移動(dòng)節(jié)點(diǎn)在興趣維度上的關(guān)聯(lián)關(guān)系。本文的消息路由算法研究更加關(guān)注節(jié)點(diǎn)的行為規(guī)律性，這對(duì)消息路由算法的中繼節(jié)點(diǎn)選擇起到了關(guān)鍵作用。同時(shí)表明移動(dòng)節(jié)點(diǎn)在時(shí)間、空間和興趣維度上具有一定的關(guān)聯(lián)和規(guī)律性。這些關(guān)聯(lián)和規(guī)律性便于引導(dǎo)本文有效地構(gòu)造時(shí)變興趣社區(qū)，并設(shè)計(jì)出高效的查詢(xún)消息路由方法。

4 基于時(shí)變模型的查詢(xún)消息路由算法

4.1 TIMER 路由算法概述

TIMER 路由算法在高校校園的物理場(chǎng)景中的應(yīng)用，如圖6 所示，圖中圓內(nèi)的數(shù)字表示節(jié)點(diǎn)標(biāo)號(hào)，Ci表示i類(lèi)興趣社區(qū)。其中，圖6(a)為高校校園物理場(chǎng)景，包含圖書(shū)館、實(shí)驗(yàn)室、餐廳和宿舍，具體見(jiàn)4.3 節(jié)；圖6(b)為利用節(jié)點(diǎn)在時(shí)間維度上的規(guī)律性所構(gòu)建的三類(lèi)興趣社區(qū)結(jié)構(gòu)，具體見(jiàn)4.2 節(jié)；圖6(c)為利用節(jié)點(diǎn)在時(shí)空維度上的關(guān)聯(lián)性所構(gòu)建的時(shí)變興趣社區(qū)。中間的三角形區(qū)域?yàn)楸疚乃O(shè)計(jì)的查詢(xún)消息路由算法，它是基于上述興趣社區(qū)拓?fù)浣Y(jié)構(gòu)的，具體見(jiàn)4.4 節(jié)。

圖6 基于時(shí)變模型的查詢(xún)路由算法實(shí)現(xiàn)原理

4.2 基于社會(huì)親密度的興趣社區(qū)的構(gòu)建

首先給出社會(huì)親密度的定義。節(jié)點(diǎn)間的社會(huì)親密度包含了節(jié)點(diǎn)的連接時(shí)間、等待時(shí)間及通信頻率。由于網(wǎng)絡(luò)中部分節(jié)點(diǎn)有直接聯(lián)系、部分節(jié)點(diǎn)沒(méi)有直接聯(lián)系，將社會(huì)親密度分為直接社會(huì)親密度和間接社會(huì)親密度。

定義1直接社會(huì)親密度是節(jié)點(diǎn)i與j之間平均間隔聯(lián)系時(shí)間的倒數(shù)，其表達(dá)式如式(1)所示。它的物理意義是2 個(gè)節(jié)點(diǎn)等待下一次相遇的時(shí)間越短，說(shuō)明它們之間的社會(huì)親密度越高。

其中，λij表示節(jié)點(diǎn)i與j之間的直接社會(huì)親密度，Tij表示節(jié)點(diǎn)i與j之間的平均間隔聯(lián)系時(shí)間，fij(t)表示時(shí)刻t之后2個(gè)節(jié)點(diǎn)下一次相遇所需等待時(shí)間的函數(shù)，k表示節(jié)點(diǎn)在[0,T]的時(shí)間范圍內(nèi)聯(lián)系的頻率。

定義2間接社會(huì)親密度是節(jié)點(diǎn)i與j通過(guò)其他節(jié)點(diǎn)w進(jìn)行聯(lián)系，它們之間的平均間隔聯(lián)系時(shí)間的倒數(shù)，其表達(dá)式如式(2)所示。

其中，w表示節(jié)點(diǎn)i與j之間的中繼聯(lián)絡(luò)節(jié)點(diǎn)，kiw表示節(jié)點(diǎn)i與w之間的聯(lián)系頻率，kwj表示節(jié)點(diǎn)w與j之間的聯(lián)系頻率，fiw(t)表示時(shí)刻t之后節(jié)點(diǎn)i與w下一次相遇所需等待時(shí)間的函數(shù)，fwj(t)表示時(shí)刻t之后節(jié)點(diǎn)w與j下一次相遇所需等待時(shí)間的函數(shù)。

設(shè)網(wǎng)絡(luò)中有n個(gè)節(jié)點(diǎn)，基于節(jié)點(diǎn)的通信歷史數(shù)據(jù)，節(jié)點(diǎn)ni根據(jù)定義1 和定義2 計(jì)算與其他節(jié)點(diǎn)的社會(huì)親密度，從而得到字節(jié)的矩陣M用來(lái)存儲(chǔ)網(wǎng)絡(luò)中節(jié)點(diǎn)間的社會(huì)親密度數(shù)值。之后，將M作為社會(huì)親密度數(shù)值矩陣的輸入，使用K-means 聚類(lèi)算法[16-17]（K=3）得到圖6(b)所示的興趣社區(qū)。其中Cg表示第g類(lèi)興趣社區(qū)，Cr表示第r類(lèi)興趣社區(qū)，Cy表示第y類(lèi)興趣社區(qū)。之后，根據(jù)圖8-1 中物理連接關(guān)系重組興趣社區(qū)，得到Cg1、Cg2、Cr1、Cr2、Cr3、Cy1和Cy2。

粒子更新速度加上虛擬力的調(diào)整后粒子速度能夠及時(shí)調(diào)整,避免了陷入局部最優(yōu),既具有較好的全局搜索能力,又具有較好的局部搜索能力。

4.3 基于時(shí)變特性的動(dòng)態(tài)興趣社區(qū)構(gòu)建

假設(shè)興趣社區(qū)在3 個(gè)時(shí)間狀態(tài)之間相互轉(zhuǎn)換，這3個(gè)時(shí)間狀態(tài)分別是初始狀態(tài)、遷移狀態(tài)和空狀態(tài)（Null）。具有時(shí)變特性的動(dòng)態(tài)興趣社區(qū)構(gòu)建過(guò)程如下。首先定義2 個(gè)狀態(tài)矩陣T和S，如式(3)所示。

其中，T表示社區(qū)的狀態(tài)轉(zhuǎn)移時(shí)間矩陣，矩陣中的元素tij表示社區(qū)從狀態(tài)i到狀態(tài)j的轉(zhuǎn)移時(shí)間；S是布爾矩陣，表示社區(qū)是否遷移成功。當(dāng)α-tij≥0時(shí)，S中的元素為1，其物理意義為社區(qū)從狀態(tài)i成功地遷移到了狀態(tài)j；否則，為0，其物理意義是社區(qū)仍然滯留在狀態(tài)i。

那么，在α單位時(shí)間（單位時(shí)間可以是小時(shí)等）之后，社區(qū)從狀態(tài)i到狀態(tài)j的轉(zhuǎn)移概率如式(4)所示。

其中，pij表示社區(qū)從狀態(tài)i到狀態(tài)j的轉(zhuǎn)移概率，的數(shù)值從S中獲得。

在α單位時(shí)間（單位時(shí)間可以是小時(shí)等）之后，社區(qū)從狀態(tài)i經(jīng)過(guò)狀態(tài)r到狀態(tài)j的轉(zhuǎn)移概率如式(5)所示。

綜上，可以得到社區(qū)的狀態(tài)轉(zhuǎn)移概率的表達(dá)式如式(6)所示。

基于時(shí)變特性的興趣社區(qū)遷移如圖7 所示。在10:00 時(shí)，在實(shí)驗(yàn)室構(gòu)建了專(zhuān)業(yè)技術(shù)社區(qū)，在圖書(shū)館和宿舍分別構(gòu)建了學(xué)習(xí)社區(qū)和綜合性社區(qū)，餐廳無(wú)社區(qū)形成。在12:00 時(shí)，學(xué)生和教職工進(jìn)入餐廳，此時(shí)，綜合性社區(qū)在餐廳形成，之前2 h 所構(gòu)建的興趣社區(qū)解散后進(jìn)入空狀態(tài)。在22:00 時(shí)，學(xué)生和教職工回到宿舍休息，綜合性社區(qū)在宿舍區(qū)形成，之前的興趣社區(qū)解散后轉(zhuǎn)入安防社區(qū)，該社區(qū)用于保護(hù)公共財(cái)產(chǎn)安全。

4.4 基于動(dòng)態(tài)興趣社區(qū)的查詢(xún)路由算法

基于興趣社區(qū)的查詢(xún)路由算法TIMER 包括興趣社區(qū)間的查詢(xún)和興趣社區(qū)內(nèi)的查詢(xún)。興趣社區(qū)內(nèi)的查詢(xún)采用經(jīng)典的Binary SW 算法。下面重點(diǎn)闡述基于節(jié)點(diǎn)移動(dòng)軌跡相似度的興趣社區(qū)間查詢(xún)算法。

定義3當(dāng)前位置。節(jié)點(diǎn)i的當(dāng)前位置用(xi,yi,ti)表示，其中ix和yi分別表示節(jié)點(diǎn)i的經(jīng)緯度坐標(biāo)，ti表示當(dāng)前的時(shí)刻。

定義4滯留時(shí)間和滯留區(qū)域

滯留時(shí)間Tp等于(tl-ts)，其中ts為節(jié)點(diǎn)進(jìn)入某區(qū)域的時(shí)間，tl為節(jié)點(diǎn)離開(kāi)某區(qū)域的時(shí)間。

滯留區(qū)域?yàn)楣?jié)點(diǎn)在滯留時(shí)間Tp內(nèi)的活動(dòng)范圍max{d(p,q)}。其中，p(xi,yi,ti)為節(jié)點(diǎn)在ti(ts≤ti≤tl)時(shí)刻的位置，q(xj,yj,tj)為節(jié)點(diǎn)在tj(ts≤tj≤tl)的位置，d(p,q)表示p、q兩點(diǎn)之間的歐幾里得距離。

定義5移動(dòng)軌跡

節(jié)點(diǎn)的移動(dòng)軌跡是由節(jié)點(diǎn)所經(jīng)過(guò)的滯留位置所組成，如式(7)和式(8)所示。

其中,Tr表示節(jié)點(diǎn)的移動(dòng)軌跡；Ai為節(jié)點(diǎn)所經(jīng)過(guò)的滯留區(qū)域i；Tp(i)為節(jié)點(diǎn)在區(qū)域Ai的滯留時(shí)間；δi為權(quán)重，表示區(qū)域Ai對(duì)節(jié)點(diǎn)i的重要性；ηi表示節(jié)點(diǎn)訪(fǎng)問(wèn)區(qū)域Ai的頻度。

圖7 基于時(shí)變特性的興趣社區(qū)遷移示意

接下來(lái)，按照區(qū)域?qū)?jié)點(diǎn)的重要性更新節(jié)點(diǎn)的移動(dòng)軌跡序列。2 個(gè)節(jié)點(diǎn)移動(dòng)軌跡中所包含的相同滯留區(qū)域越多，表明2 個(gè)節(jié)點(diǎn)的興趣度越相近，將興趣度相近且頻繁游離于不同興趣社區(qū)的節(jié)點(diǎn)作為大使節(jié)點(diǎn)輔助消息轉(zhuǎn)發(fā)?；诠?jié)點(diǎn)移動(dòng)軌跡相似度的興趣社區(qū)間查詢(xún)算法如算法1 所示。

算法1 的執(zhí)行如圖8 所示，興趣社區(qū)1 中的請(qǐng)求節(jié)點(diǎn)R在其查詢(xún)消息無(wú)響應(yīng)時(shí)，找到2 個(gè)大使節(jié)點(diǎn)N1和N2。之后，通過(guò)比較與大使節(jié)點(diǎn)N1和N2的移動(dòng)軌跡相似度后發(fā)現(xiàn)自身與節(jié)點(diǎn)N2的移動(dòng)軌跡相似度更高，于是將查詢(xún)消息發(fā)送給大使節(jié)點(diǎn)N2，N2將查詢(xún)消息攜帶到興趣社區(qū)3 中，采用Binary SW 算法進(jìn)行轉(zhuǎn)發(fā)，最終查詢(xún)消息達(dá)到了響應(yīng)節(jié)點(diǎn)H。

算法1基于節(jié)點(diǎn)移動(dòng)軌跡相似度興趣社區(qū)間查詢(xún)路由算法

圖8 基于移動(dòng)軌跡相似度的查詢(xún)算法

TIMER 時(shí)間復(fù)雜度的分析如下。假設(shè)網(wǎng)絡(luò)場(chǎng)景中有m個(gè)位置，每個(gè)查詢(xún)節(jié)點(diǎn)產(chǎn)生L份查詢(xún)消息拷貝。社區(qū)內(nèi)部采用Binary SW 算法，該算法的時(shí)間復(fù)雜度為O(n+logL)，其中L是常數(shù)，因此Binary SW 算法時(shí)間復(fù)雜度為O(n)。算法1 中移動(dòng)軌跡生成和大使節(jié)點(diǎn)選擇代碼段的時(shí)間復(fù)雜度是O(mn)；請(qǐng)求節(jié)點(diǎn)計(jì)算最優(yōu)大使節(jié)點(diǎn)的最壞情況下時(shí)間復(fù)雜度為O(nlogn)。綜上，TIMER 的執(zhí)行時(shí)間復(fù)雜度為O(2mn+nlogn+n)。由于2mn+nlogn+n≤2(m+1)nlogn，而m是 常 數(shù)，因 此，TIMER的時(shí)間復(fù)雜度是O(nlogn)。

5 TIMER 性能評(píng)估

5.1 仿真環(huán)境和參數(shù)設(shè)置

本文選用隨機(jī)網(wǎng)絡(luò)仿真器ONE (opportunistic network environment)作為算法性能評(píng)估的仿真平臺(tái)。仿真場(chǎng)景地圖為江蘇大學(xué)校園一角，利用OPEN JUMP 采集相應(yīng)的節(jié)點(diǎn)移動(dòng)軌跡，在仿真程序中設(shè)定了4 個(gè)興趣社區(qū)，即嵌入式開(kāi)發(fā)興趣社區(qū)、電氣工程興趣社區(qū)、化學(xué)興趣社區(qū)和理學(xué)興趣社區(qū)。TIMER 評(píng)估的實(shí)驗(yàn)參數(shù)配置如表1 所示，仿真模擬場(chǎng)景如圖9 所示。

表1 實(shí)驗(yàn)參數(shù)配置

圖9 模擬仿真實(shí)驗(yàn)場(chǎng)景

5.2 實(shí)驗(yàn)結(jié)果分析

在實(shí)驗(yàn)評(píng)估中，將本文提出的TIMER 與同類(lèi)型的查詢(xún)消息路由算法EPIDEMIC(EPIDEMIC routing for partially connected Ad Hoc network)[3]、PRoPHET(probabilistic routing protocol using history of encounters and transitivity)[5]和ICR(interest community routing for opportunistic network)[7]在消息投遞成功率、平均查詢(xún)時(shí)延、查詢(xún)消息的平均跳數(shù)和查詢(xún)成功的系統(tǒng)開(kāi)銷(xiāo)這4 個(gè)方面進(jìn)行比較，具體定義如下。

定義6消息投遞成功率是仿真期間成功傳輸?shù)南?shù)占總消息數(shù)的比例。

定義7平均查詢(xún)時(shí)延是從消息產(chǎn)生到消息響應(yīng)的平均時(shí)延。

定義8成功查詢(xún)的平均跳數(shù)是指從消息產(chǎn)生到消息響應(yīng)所經(jīng)過(guò)的平均節(jié)點(diǎn)數(shù)。

定義9查詢(xún)成功的系統(tǒng)開(kāi)銷(xiāo)是指一次成功查詢(xún)所需要產(chǎn)生的查詢(xún)消息的平均副本數(shù)。

圖10～圖13 的橫坐標(biāo)為交互次數(shù)，它指的是仿真期間節(jié)點(diǎn)所建立的連接數(shù)統(tǒng)計(jì)。本文將EPIDEMIC 方案作為性能評(píng)估的基準(zhǔn)[5,7]。

1)消息投遞成功率

如圖10 所示，隨著交互次數(shù)的增多，EPIDEMIC、PRoPHET、ICR 和TIMER 這4 種算法的消息投遞成功率均逐漸增加，隨后趨于穩(wěn)定。這是因?yàn)橄⑼哆f成功率是建立在節(jié)點(diǎn)交互次數(shù)的基礎(chǔ)上，交互次數(shù)越多，投遞成功的概率就越高。盡管ICR 比PRoPHET的性能略好，但是與EPIDEMIC 的性能尚有差距。這是由于PRoPHET 為了控制系統(tǒng)中的消息副本數(shù)，采用了概率轉(zhuǎn)發(fā)，因此實(shí)際的投遞次數(shù)低于節(jié)點(diǎn)交互的次數(shù)。盡管ICR 采用了基于興趣社區(qū)的消息投遞方法，但是所構(gòu)建的興趣社區(qū)是靜態(tài)的，無(wú)法適應(yīng)移動(dòng)網(wǎng)絡(luò)實(shí)際的變化。TIMER 提出了時(shí)變社區(qū)的概念，時(shí)變社區(qū)較好地適應(yīng)了網(wǎng)絡(luò)拓?fù)涞淖兓?。此外，TIMER 也充分利用了節(jié)點(diǎn)的交互次數(shù)。TIMER 收斂后的消息投遞成功率在90%左右。

圖10 消息投遞成功率評(píng)估

圖11 平均查詢(xún)時(shí)延評(píng)估

2)平均查詢(xún)時(shí)延

平均查詢(xún)時(shí)延是消息路由算法設(shè)計(jì)的一個(gè)重要衡量指標(biāo)，這是因?yàn)槠骄樵?xún)時(shí)延越長(zhǎng)，查詢(xún)消息在網(wǎng)絡(luò)中的副本數(shù)越多，在節(jié)點(diǎn)緩存中存放的時(shí)間越長(zhǎng)。因此，降低平均查詢(xún)時(shí)間對(duì)消息路由算法而言是十分必要的。如圖11 所示，EPIDEMIC 的平均查詢(xún)時(shí)間最低，這是因?yàn)镋PIDEMIC 方法產(chǎn)生了多個(gè)查詢(xún)消息副本，平均查詢(xún)時(shí)延則是統(tǒng)計(jì)從消息產(chǎn)生到消息響應(yīng)的時(shí)間，因此實(shí)際上它是將多副本查詢(xún)消息中最短的查詢(xún)時(shí)間作為本次的查詢(xún)時(shí)延。TIMER 所構(gòu)建的時(shí)變社區(qū)是有效的，查詢(xún)節(jié)點(diǎn)總能通過(guò)一跳或多跳檢索到響應(yīng)節(jié)點(diǎn)。ICR 比TIMER的平均查詢(xún)時(shí)延要差，但是比PRoPHET 的平均查詢(xún)時(shí)延要好，這說(shuō)明PRoPHET 通過(guò)節(jié)點(diǎn)的歷史通信記錄進(jìn)行概率計(jì)算的方法盡管控制了消息副本數(shù)量的增長(zhǎng)，但是卻犧牲了節(jié)點(diǎn)的查詢(xún)時(shí)延，與EPIDEMIC方法相比，多了2 000 s 的時(shí)延。ICR 與EPIDEMIC相比，多了1 000 s 的時(shí)延。TIMER 與EPIDEMIC相比，僅多了幾十秒到百秒的時(shí)延。

3)成功查詢(xún)平均跳數(shù)

成功查詢(xún)的平均跳數(shù)與平均查詢(xún)時(shí)延都是評(píng)估算法性能的指標(biāo)，這2 個(gè)評(píng)估指標(biāo)很相近，所不同的是查詢(xún)時(shí)延表示的是數(shù)據(jù)的傳輸時(shí)間，而平均跳數(shù)是一次成功查詢(xún)跳過(guò)的節(jié)點(diǎn)數(shù)。如圖12 所示，這個(gè)實(shí)驗(yàn)結(jié)果和上面評(píng)估的平均查詢(xún)時(shí)延結(jié)果是一致的。EPIDEMIC 方法一次成功查詢(xún)所需的平均跳數(shù)是2.28，TIMER 算法一次成功查詢(xún)所需的平均跳數(shù)是2.68，ICR 算法一次成功查詢(xún)所需的平均跳數(shù)是4.25，PRoPHET方法一次成功查詢(xún)所需的平均跳數(shù)是5.24。需要說(shuō)明的是，在交互次數(shù)低于5×105時(shí)，平均跳數(shù)會(huì)增加，這種情況發(fā)生在網(wǎng)絡(luò)中節(jié)點(diǎn)所處的位置比較分散，此時(shí)節(jié)點(diǎn)只能通過(guò)移動(dòng)尋找未來(lái)與其他節(jié)點(diǎn)相遇的機(jī)會(huì)，從而增加投遞成功的機(jī)率。

圖12 成功查詢(xún)的平均跳數(shù)對(duì)比

4)查詢(xún)成功的系統(tǒng)開(kāi)銷(xiāo)

各種消息路由算法一次成功查詢(xún)所需要產(chǎn)生的副本數(shù)，如圖13 所示。EPIDEMIC 方法的副本數(shù)最高，達(dá)到了平均使用23 條副本消息才能完成一次成功查詢(xún)。其他幾種消息路由算法都有針對(duì)性地控制了查詢(xún)消息副本的數(shù)量，基本控制在5 條副本以下。TIMER 算法所需要的查詢(xún)副本數(shù)最低，基本通過(guò)2～3 條消息副本就可以發(fā)現(xiàn)資源響應(yīng)節(jié)點(diǎn)。這就表明本文提出的TIMER 算法在控制消息副本數(shù)增長(zhǎng)方面效果最好。

綜合對(duì)以上性能指標(biāo)的實(shí)驗(yàn)評(píng)估，表明TIMER算法所構(gòu)建的興趣社區(qū)是有效的，節(jié)點(diǎn)基本上在興趣社區(qū)內(nèi)就可以發(fā)現(xiàn)請(qǐng)求響應(yīng)節(jié)點(diǎn)。即使社區(qū)內(nèi)不存在請(qǐng)求響應(yīng)節(jié)點(diǎn)，請(qǐng)求消息也可通過(guò)最優(yōu)的大使節(jié)點(diǎn)將查詢(xún)消息傳遞給當(dāng)前興趣社區(qū)之外的請(qǐng)求響應(yīng)節(jié)點(diǎn)。因此，TIMER 算法具有一定的可擴(kuò)展性，適當(dāng)?shù)財(cái)U(kuò)大了搜索范圍，提高了查詢(xún)消息轉(zhuǎn)發(fā)的成功率。

圖13 成功查詢(xún)所需的系統(tǒng)開(kāi)銷(xiāo)評(píng)估

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

本文以高校校園為應(yīng)用場(chǎng)景，研究校園環(huán)境下的機(jī)會(huì)社交網(wǎng)絡(luò)，并在此基礎(chǔ)上提出一種基于時(shí)變興趣社區(qū)的查詢(xún)消息路由算法TIMER。本文對(duì)與科研工作場(chǎng)景相關(guān)的2 個(gè)重要移動(dòng)社交數(shù)據(jù)集(copelabs/usense 和upb/hyccups)進(jìn)行了分析，通過(guò)分析發(fā)現(xiàn)這些移動(dòng)節(jié)點(diǎn)具有一定的時(shí)空關(guān)聯(lián)性和規(guī)律性。基于這一發(fā)現(xiàn)，本文提出了基于社會(huì)親密度的興趣社區(qū)構(gòu)建方法和時(shí)變興趣社區(qū)模型，并在此基礎(chǔ)上給出了社區(qū)內(nèi)和社區(qū)間的查詢(xún)路由算法。對(duì)算法的理論分析表明，TIMER 算法的時(shí)間復(fù)雜度為O(nlogn)。在仿真實(shí)驗(yàn)平臺(tái)上，將TIMER 算法與同類(lèi)算法在消息投遞成功率、平均查詢(xún)時(shí)延、成功查詢(xún)平均跳數(shù)和查詢(xún)成功的系統(tǒng)開(kāi)銷(xiāo)四方面進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明TIMER算法完成一次成功查詢(xún)所需的查詢(xún)時(shí)延、平均跳數(shù)、平均跳數(shù)低于PRoPHET 和ICR 查詢(xún)消息路由算法，消息投遞成功率和可擴(kuò)展性?xún)?yōu)于PRoPHET 和ICR 查詢(xún)消息路由算法，與基準(zhǔn)算法EPIDEMIC 在數(shù)值上接近。然而，本文提出的TIMER 算法在查詢(xún)消息副本數(shù)上要明顯優(yōu)于基準(zhǔn)算法EPIDEMIC。綜上，TIMER算法在網(wǎng)絡(luò)規(guī)模和消息傳播數(shù)據(jù)量增大時(shí)各方面綜合表現(xiàn)是最優(yōu)的。下一步工作是針對(duì)機(jī)會(huì)社交網(wǎng)絡(luò)中存在自私節(jié)點(diǎn)情況下的消息路由算法研究。