汪晶明， 王青山， 沈 進(jìn)， 劉 靜， 時(shí)寬凱

（合肥工業(yè)大學(xué) 數(shù)學(xué)學(xué)院，安徽 合肥 230009）

0 引 言

延遲容忍網(wǎng)絡(luò)（delay tolerant network，DTN）又稱容遲網(wǎng)絡(luò)，是指一類特殊的無線網(wǎng)絡(luò)，主要應(yīng)用于海洋監(jiān)測、衛(wèi)星通信［1］、汽車網(wǎng)絡(luò)［2］、移動社交網(wǎng)絡(luò)［3］、軍事網(wǎng)絡(luò)［4］及偏遠(yuǎn)地區(qū)通信等領(lǐng)域。在該網(wǎng)絡(luò)中端到端的路徑通常很難建立，所以網(wǎng)絡(luò)中的消息傳播具有很大的延時(shí)。但在容遲網(wǎng)絡(luò)中，由于節(jié)點(diǎn)運(yùn)動的不確定性和節(jié)點(diǎn)的密度不同造成網(wǎng)絡(luò)一般不存在端到端的路徑，因此傳統(tǒng)的無線網(wǎng)絡(luò)算法已經(jīng)不適用于容遲網(wǎng)絡(luò)。

移動社交網(wǎng)絡(luò)（mobile social networks，MSNets）是容遲網(wǎng)絡(luò)中的一種，也是近年來研究的一個(gè)熱點(diǎn)問題。在移動社交網(wǎng)絡(luò)中，即使沒有網(wǎng)絡(luò)基礎(chǔ)設(shè)施或端到端的連接，也能通過用戶移動的相互作用，從而達(dá)到網(wǎng)絡(luò)服務(wù)的目的，該網(wǎng)絡(luò)不需要一些網(wǎng)絡(luò)基礎(chǔ)設(shè)施，因此可用于廣域傳感器網(wǎng)絡(luò)中［5－6］等關(guān)鍵領(lǐng)域。移動社交網(wǎng)絡(luò)可視為一種具有社會意識的容遲網(wǎng)絡(luò)，隨著智能手機(jī)、車載移動終端等多種移動設(shè)備的普及以及傳感網(wǎng)絡(luò)技術(shù)的廣泛應(yīng)用，移動社交網(wǎng)絡(luò)已經(jīng)開始得到更多人的關(guān)注。

移動社交網(wǎng)絡(luò)中，節(jié)點(diǎn)移動與其他節(jié)點(diǎn)相遇而形成通信機(jī)會，消息隨著節(jié)點(diǎn)的移動而傳播，在節(jié)點(diǎn)之間轉(zhuǎn)發(fā)從而實(shí)現(xiàn)傳輸。由于數(shù)據(jù)傳播具有間歇性和不確定性，因此設(shè)計(jì)一種高效的轉(zhuǎn)發(fā)算法是實(shí)現(xiàn)數(shù)據(jù)傳輸?shù)年P(guān)鍵。近年來，國內(nèi)外相關(guān)研究人員已經(jīng)對社交網(wǎng)絡(luò)的轉(zhuǎn)發(fā)算法進(jìn)行了大量的研究，并取得了一定的成果。從實(shí)際的跟蹤文件中發(fā)現(xiàn)，在移動社交網(wǎng)絡(luò)中，用戶通常會有幾個(gè)經(jīng)常有規(guī)律移動的區(qū)域，根據(jù)該規(guī)律本文建立了社區(qū)網(wǎng)絡(luò)模型。

目前較為經(jīng)典的轉(zhuǎn)發(fā)算法有基于復(fù)制、基于效用以及基于社會屬性的轉(zhuǎn)發(fā)算法?；趶?fù)制的轉(zhuǎn)發(fā)算法是在傳輸信息時(shí)產(chǎn)生多份拷貝信息，通過增加網(wǎng)絡(luò)中消息拷貝數(shù)目來提高數(shù)據(jù)傳輸率，如Epidemic算法［7］和自我限制的傳染性轉(zhuǎn)發(fā)算法［8］?；谛в玫霓D(zhuǎn)發(fā)算法利用網(wǎng)絡(luò)中節(jié)點(diǎn)的狀態(tài)信息來決定節(jié)點(diǎn)相遇時(shí)是否轉(zhuǎn)發(fā)消息，建立一個(gè)預(yù)測函數(shù)來估計(jì)節(jié)點(diǎn)的效用，節(jié)點(diǎn)的效用越高，遇到目的節(jié)點(diǎn)的概率越高，如概率路由（probabilistie routing）算法［9］和基于搜索聚焦（seek and focus）的轉(zhuǎn)發(fā)算法［10］。基于社會屬性的轉(zhuǎn)發(fā)算法根據(jù)節(jié)點(diǎn)的社會屬性（影響力、價(jià)值及能力等）來選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)，如Label算法［11］和基于信任為基礎(chǔ)的路由轉(zhuǎn)發(fā)算法［12］。

然而在以往基于社會屬性的轉(zhuǎn)發(fā)算法［13］中只考慮了單個(gè)節(jié)點(diǎn)的社會屬性，對通過多個(gè)節(jié)點(diǎn)共同作用得到的社會屬性考慮很少，本文主要通過2個(gè)節(jié)點(diǎn)共同形成的社會屬性以及節(jié)點(diǎn)的相似度和活躍度的數(shù)據(jù)概念，提出一種基于節(jié)點(diǎn)相似度和活躍度的數(shù)據(jù)轉(zhuǎn)發(fā)算法（data forwarding algorithm based on the similarity and activity of nodes，DASA）。通過仿真實(shí)驗(yàn)，與Epidemic算法和Label算法以及Greedy Total算法［14］進(jìn)行比較，得出本文提出的算法可提高數(shù)據(jù)的傳遞率，同時(shí)能夠大大降低網(wǎng)絡(luò)資源的消耗。

1 網(wǎng)絡(luò)模型建立

社區(qū)定義為一些成員通過直接聯(lián)系或一些中間個(gè)體間接聯(lián)系而形成的一個(gè)群體。通常一個(gè)社區(qū)中的成員有一些共同的社會屬性，如共同的愛好、相似的社會功能。比如在同一個(gè)俱樂部的成員有相同的愛好，相互交流的機(jī)會比較多，從而會形成一個(gè)社區(qū)；在公司中，同一個(gè)辦公室的員工彼此交流比較頻繁，就會形成一個(gè)群體。從以往的跟蹤數(shù)據(jù)中發(fā)現(xiàn)，在移動社交網(wǎng)絡(luò)中，人們的移動具有一定的規(guī)律性，從而通常會形成若干個(gè)社區(qū)。

定義1 對一個(gè)群體用戶根據(jù)他們的興趣愛好和地理定位，他們相互聯(lián)系的區(qū)域定義為一個(gè)社區(qū)。社區(qū)網(wǎng)絡(luò)可表示為：

其中，ci（1≤i≤J）為第i個(gè)社區(qū)；C為社區(qū)網(wǎng)絡(luò)。

由于地理位置和人們的興趣愛好等原因，一個(gè)社區(qū)網(wǎng)絡(luò)會形成了不同的社區(qū)，其劃分如圖1所示。

圖1 社區(qū)網(wǎng)絡(luò)劃分

本文將時(shí)間t分割成若干個(gè)很小的等長時(shí)間段t＝｛t1，t2，…｝。為了表示出社區(qū)網(wǎng)絡(luò)在時(shí)間段ti的狀態(tài)，本文使用該時(shí)間段內(nèi)各社區(qū)上所有節(jié)點(diǎn)的集合來表示在時(shí)間段ti社區(qū)網(wǎng)絡(luò)的狀態(tài)，具體如下：

其中，cti，k（1≤k≤J）為在ti時(shí)間段社區(qū)ck中節(jié)點(diǎn)的集合；Cti為網(wǎng)絡(luò)節(jié)點(diǎn)在ti時(shí)間段的一個(gè)劃分，具體實(shí)例，如圖2所示。

圖2 ti時(shí)間段社區(qū)網(wǎng)絡(luò)狀態(tài)

在圖2中，ti時(shí)間段社區(qū)c1、c2、c3、c4中節(jié)點(diǎn)集合分別為：

則在ti時(shí)間段社區(qū)網(wǎng)絡(luò)的狀態(tài)為：

2 DASA算法

DASA算法以節(jié)點(diǎn)的相似度和活躍度為基礎(chǔ)，運(yùn)用節(jié)點(diǎn)運(yùn)動所遇到的節(jié)點(diǎn)個(gè)數(shù)和鄰居分別對節(jié)點(diǎn)的活躍度和相似度進(jìn)行建模計(jì)算。通過對轉(zhuǎn)發(fā)條件和拷貝數(shù)目的控制，達(dá)到提高消息傳遞率，降低網(wǎng)絡(luò)資源消耗的目的。

節(jié)點(diǎn)的相似度是指節(jié)點(diǎn)移動范圍和所遇節(jié)點(diǎn)的相似程度。在選擇節(jié)點(diǎn)轉(zhuǎn)發(fā)時(shí)，考慮到有些節(jié)點(diǎn)和攜帶數(shù)據(jù)包的節(jié)點(diǎn)相似，就不需要把包轉(zhuǎn)發(fā)給那些節(jié)點(diǎn)，從而提高了傳遞率，降低了拷貝數(shù)目。本文通過在一定時(shí)間內(nèi)節(jié)點(diǎn)所遇相同鄰居個(gè)數(shù)來計(jì)算相似度。

定義2 在一段時(shí)間內(nèi)節(jié)點(diǎn)i和j在相同社區(qū)內(nèi)碰到的共同節(jié)點(diǎn)個(gè)數(shù)與它們所遇節(jié)點(diǎn)總數(shù)的比值，稱為節(jié)點(diǎn)i和j的相似度，即

其中，K為遇到總的節(jié)點(diǎn)數(shù)目；k為在相同社區(qū)中所遇共同節(jié)點(diǎn)個(gè)數(shù)。

節(jié)點(diǎn)的活躍度是指節(jié)點(diǎn)活動能力的大小，活動能力是指在一定的時(shí)間內(nèi)所遇節(jié)點(diǎn)的數(shù)目。由于每個(gè)人的活動范圍和活動能力各不相同，活動能力越大則說明其移動的范圍越廣，接觸的節(jié)點(diǎn)越多，則傳輸?shù)侥康墓?jié)點(diǎn)的概率就比較大，這種活動能力稱為活躍度?；钴S度越大則說明能接觸的節(jié)點(diǎn)越多，因此能夠成功轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)的機(jī)會越大。

定義3 節(jié)點(diǎn)i的活躍度A（i）表示它的鄰居的個(gè)數(shù)。

當(dāng)兩節(jié)點(diǎn)i、j相遇時(shí)，節(jié)點(diǎn)i是否把包傳遞給節(jié)點(diǎn)j，取決于節(jié)點(diǎn)j的活躍度A（j）是否大于節(jié)點(diǎn)i的活躍度A（i），只有滿足該條件時(shí)才可能傳包。根據(jù)定義可知，節(jié)點(diǎn)i、j相遇時(shí)他們的鄰居個(gè)數(shù)是計(jì)算活躍度的指標(biāo)，記Si為節(jié)點(diǎn)i的鄰居集合，Sj為節(jié)點(diǎn)j的鄰居集合，節(jié)點(diǎn)i遇到節(jié)點(diǎn)j是否傳包的表達(dá)式如下：

其中，G（i，j）表示是否傳包情況，如果節(jié)點(diǎn)i可能傳包給節(jié)點(diǎn)j，則為1；否則為0。

本文設(shè)定一個(gè)相似度的閾值α，若節(jié)點(diǎn)i和節(jié)點(diǎn)j的相似度小于該閾值，可以選擇它作為待選節(jié)點(diǎn)，否則不轉(zhuǎn)發(fā)。考慮它們的活躍度，若節(jié)點(diǎn)j的活躍度大于節(jié)點(diǎn)i的活躍度，就直接轉(zhuǎn)發(fā)，相反不轉(zhuǎn)發(fā)。DASA算法的具體描述如下：

當(dāng)節(jié)點(diǎn)i遇到節(jié)點(diǎn)j，如果j是目的節(jié)點(diǎn)則直接轉(zhuǎn)發(fā)；如果不是，則根據(jù)節(jié)點(diǎn)間的相似度和活躍度來判斷是否轉(zhuǎn)發(fā)，有效選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)，可以提高傳輸?shù)某晒β剩档土司W(wǎng)絡(luò)資源的消耗。

3 模擬實(shí)驗(yàn)結(jié)果和分析

本文用C＋＋語言開發(fā)了一個(gè)模擬器來研究DASA算法、Epidemic算法、Label算法和Greedy Total算法在移動社交網(wǎng)絡(luò)中的性能。其中Greedy Total算法的主要思想是當(dāng)節(jié)點(diǎn)j遇到節(jié)點(diǎn)i時(shí)，如果節(jié)點(diǎn)j遇到的節(jié)點(diǎn)數(shù)目比節(jié)點(diǎn)i遇到的多，則把信息傳遞給j，反之則不傳。

本文選擇了Infocom 06的節(jié)點(diǎn)［15］移動軌跡作為節(jié)點(diǎn)移動模式，共設(shè)置了98個(gè)節(jié)點(diǎn)，其中有20個(gè)AP（不動節(jié)點(diǎn)），每個(gè)AP分別放置在20個(gè)不同的社區(qū)內(nèi)。隨機(jī)產(chǎn)生了200對源節(jié)點(diǎn)和目的節(jié)點(diǎn)通信，為了簡單起見，假設(shè)每對源節(jié)點(diǎn)向目的節(jié)點(diǎn)發(fā)送1個(gè)數(shù)據(jù)包。DASA算法初始時(shí)在源節(jié)點(diǎn)處產(chǎn)生的數(shù)據(jù)包數(shù)量L設(shè)置為200。本文主要比較以下3個(gè)方面的性能：

（1）消息的傳遞率。即目的節(jié)點(diǎn)成功收到消息與源節(jié)點(diǎn)產(chǎn)生消息數(shù)目的比值。

（2）平均延遲。即成功傳送的消息中，消息到達(dá)目的節(jié)點(diǎn)的時(shí)間與消息從源節(jié)點(diǎn)產(chǎn)生的時(shí)間差的平均值。

（3）拷貝數(shù)目。即整個(gè)網(wǎng)絡(luò)中復(fù)制轉(zhuǎn)發(fā)的消息數(shù)目。

通過改變DASA算法中源節(jié)點(diǎn)初始數(shù)據(jù)包數(shù)量L來評價(jià)4種算法性能，實(shí)驗(yàn)結(jié)果如圖3所示。

在圖3a中，隨著數(shù)據(jù)包數(shù)量L的增加，4種算法的傳遞率均減小，這是由于隨著包數(shù)目的增多，算法的性能更加穩(wěn)定。同時(shí)可以看出，DASA算法略差于Epidemic算法和Greedy Total算法，但是優(yōu)于Label算法。

由圖3b可以看出，隨著數(shù)據(jù)包數(shù)量L的增加，4種算法的平均延遲都有所增加，DASA算法的平均延遲雖然比Epidemic算法、Label算法和Greedy Total算法略差，但其傳遞率和拷貝數(shù)目均優(yōu)于Label算法。

由圖3c可看出，DASA算法的拷貝數(shù)目比Epidemic算法、Label算法和Greedy Total算法的拷貝數(shù)目少很多，相對于Epidemic算法最多能少73.21%，對于Label算法最多能少54.08%，對于Greedy Total算法最多能少47.21%，其主要原因是由于DASA算法具有在較高的傳遞率下，通過選擇性地選擇下一節(jié)點(diǎn)，可減少拷貝數(shù)目。

通過將算法中數(shù)據(jù)包的生存時(shí)間（time to live，TTL）從12～44h來評價(jià)4種算法性能，實(shí)驗(yàn)結(jié)果如圖4所示。

在圖4a中，隨著TTL時(shí)間的增加，4種算法的傳遞率均有所增加，這是由于隨著包存活時(shí)間的增長，使得轉(zhuǎn)發(fā)成功的概率變大，傳遞率有所增加，可以看出4種算法的變化趨勢基本相同。DASA算法的傳遞率略低于Epidemic算法和Greedy Total算法，但優(yōu)于Label算法，最多能高3.89%。

由圖4b可以看出，隨著TTL時(shí)間的增加，4種算法的平均延遲都有所增加，并且增加的趨勢和幅度都基本相同。

由圖4c可以看出，隨著TTL時(shí)間的推移，拷貝數(shù)目變化很小，因此TTL對拷貝數(shù)目的影響不大。DASA算法的拷貝數(shù)目明顯比Epidemic算法和Label算法的拷貝數(shù)目少很多，最多比Epidemic算法少73.14%，比 Label算法少54.61%，比Greedy Total算法少46.21%。

圖3 源節(jié)點(diǎn)初始數(shù)據(jù)包的個(gè)數(shù)對算法的影響

圖4 TTL對算法的影響

改變DASA算法中相似度的閾值來測試算法的性能，實(shí)驗(yàn)結(jié)果如圖5所示。

由圖5a可看出，隨著相似度值的增大，DASA算法傳遞率逐漸增高，通過算法設(shè)計(jì)可知，相似度的閾值越高，就有更多的節(jié)點(diǎn)可以滿足相似度這一限制條件，則參與傳播數(shù)據(jù)的節(jié)點(diǎn)增多導(dǎo)致傳遞率明顯升高。由圖5b可以看出，隨著相似度的增加，算法的平均延遲有所增加。由圖5c可看出，增大相似度的值意味著有更多的節(jié)點(diǎn)選擇，使拷貝副本隨之增加。

圖5 相似度閾值對DASA算法的影響

4 結(jié)束語

本文研究了在移動社交網(wǎng)絡(luò)中節(jié)點(diǎn)間信息的轉(zhuǎn)發(fā)機(jī)制，根據(jù)用戶移動的一般規(guī)律性，建立網(wǎng)絡(luò)社區(qū)模型，并給出了節(jié)點(diǎn)的相似度和活躍度的概念，提出了一種基于節(jié)點(diǎn)相似度和活躍度的數(shù)據(jù)轉(zhuǎn)發(fā)算法（DASA）。實(shí)驗(yàn)結(jié)果表明，DASA算法與Epidemic算法、Label算法和Greedy Total算法相比，明顯地減少了網(wǎng)絡(luò)拷貝數(shù)目，降低了網(wǎng)絡(luò)開銷，同時(shí)在傳遞率方面優(yōu)于Label算法。

［1］ Caini C，F(xiàn)irrincieli R.Application of contact graph routing to LEO satellite DTN communications［C］／／2012IEEE International Conference on Communications（ICC）.Ottawa，ON：IEEE Press，2012：3301－3305.

［2］ Zhang L，Peng L，Zhang Y，et al.Urban bus transport network optimization from complex network［C］／／2012Proceedings of International Conference on Modelling，Identification ＆ Control（ICMIC）.Wuhan，Hubei，China：IEEE Press，2012：1159－1164.

［3］ Zhao P，Zhao J，Wang W.Division of mobile social network based on user behavior［C］／／2013International Conference on Wavelet Analysis and Pattern Recognition （ICWAPR）.Tianjin：IEEE Press，2013：148－152.

［4］ Tauil M，kant L，McAuley A，et al.Capacity estimation and waveform assignment in military networks［C］／／MILCOM 2012，Military Communications Conference.Orlando，F(xiàn)L：IEEE Press，2012：1－6.

［5］ Said H，Guimaraes M，Al Mutawa N，et al.Forensics and war－driving on unsecured wireless network［C］／／2011International Conference for Internet Technology and Secured Transactions（ICITST）.Abu Dhabi：IEEE Press，2011：19－24.

［6］ Shen Jian，Moh S，Chung I，et al.Buffer scheme optimization of epidemic routing in delay tolerant networks［J］.Journal of Communications and Networks，2014，16：656－666.

［7］ Vahdat A，Becker D.Epidemic routing for partially connected ad hoc networks［EB／OL］.（2014－02－05）.http：／／citeseerx.ist.psu.edu／viewdoc／download？doi＝10.1.1.160.5495＆rep＝rep1＆type＝pdf.

［8］ Ramanathan R，Hansen R，Basu P，et al.Prioritized epidemic routing for opportunistic networks［C］／／Proceedings of the 1st International MobiSys Workshop on Mobile Opportunistic Networking，2007：1－5.

［9］ Yin L，Lu H，Cao Y.Probabilistic delay routing for delay tolerant networks［C］／／10th International Conference on Advanced Communication Technology.Gangwon－Do：IEEE Press，2008：191－195.

［10］ Spyropoulos T，Psounis K，Raghavendra C.Efficient routing in intermittently connected mobile networks：the single－copy case［J］.IEEE／ACM Transactions on Networking，2008，16：63－76.

［11］ Pan H，Crowcroft J.How small labels create big improvements［C］／／Fifth Annual IEEE international Conference.White Plains：IEEE Press，2007：65－70.

［12］ Liu Y，Li L，Li Z，et al.Trust－based optimized routing scheme in mobile social networks［C］／／2013International Conference on Communications，Circuits and Systems（ICCCAS）.Chengdu：IEEE Press，2013：87－90.

［13］ Tang J，Kim S.Theme－based mobile social network system［C］／／Dependable，Autonomic and Secure Computing（DASC），2011Ninth International Conference on.IEEE，2011：1089－1095.

［14］ Erramill V，Chaintreau A，Crovella M，et al.Diversity of forwarding paths in pocket switched networks［C］／／IMC’07，Proceedings of the 2007ACM SIGCOMM Internet Measurement Conference，2007.doi＝10.1.1.72.6472.

［15］ Scott J，Gass R，Crowcroft J，et al.CRAWDAD data set cambridge／haggle［EB／OL］.（2009－05－29）.http：／／crawdad.cs.dartmouth.edu／haggle.