基于興趣社區(qū)的高效路由與緩存管理算法

任智，王坤龍，李秀峰

?

基于興趣社區(qū)的高效路由與緩存管理算法

任智，王坤龍，李秀峰

（重慶郵電大學(xué)移動通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065）

針對現(xiàn)有BEEINFO算法中存在控制消息冗余、未考慮節(jié)點(diǎn)多鄰居消息轉(zhuǎn)發(fā)和對緩存中消息管理不合理的問題，提出了一種基于興趣社區(qū)的高效路由與緩存管理算法——ERCMAON。該算法通過精簡控制消息，增加對節(jié)點(diǎn)多鄰居情形的路由設(shè)計(jì)，降低了系統(tǒng)開銷和消息轉(zhuǎn)發(fā)時(shí)延；同時(shí)，通過優(yōu)化節(jié)點(diǎn)緩存管理機(jī)制，降低了有用信息被刪除的概率，從而可以提高消息的投遞成功率。通過與現(xiàn)有的BEEINFO、Epidemic和ProPHET算法進(jìn)行仿真驗(yàn)證，結(jié)果表明，與BEEINFO算法相比，ERCMAON投遞成功率至少提高2.0%，數(shù)據(jù)投遞開銷和歸一化控制開銷分別降低至少9.7%和1.7%，同時(shí)消息傳輸時(shí)延至少降低2.4%。

機(jī)會網(wǎng)絡(luò)；社區(qū)；高效；緩存管理；路由算法

1 引言

機(jī)會網(wǎng)絡(luò)的研究最初來源于早期的延遲容忍網(wǎng)絡(luò)，在消息轉(zhuǎn)發(fā)過程中，源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間不一定存在完整的路徑，但隨著時(shí)間的推移，節(jié)點(diǎn)移動帶來的相遇機(jī)會可以實(shí)現(xiàn)消息的轉(zhuǎn)發(fā)，機(jī)會網(wǎng)絡(luò)就是通過節(jié)點(diǎn)的相遇機(jī)會來實(shí)現(xiàn)網(wǎng)絡(luò)節(jié)點(diǎn)之間的通信[1-2]。具有相同興趣的人（如同學(xué)或同事）通常會聚在一起討論并分享他們的興趣，他們經(jīng)常聯(lián)系并組成一個(gè)社區(qū)。人所攜帶的智能設(shè)備（如手機(jī)）作為網(wǎng)絡(luò)節(jié)點(diǎn)，因此也具有社會屬性，通常用不同的標(biāo)簽標(biāo)記以表示其類別。此外，不同興趣節(jié)點(diǎn)會生成大量不同的數(shù)據(jù)，利用不同的數(shù)據(jù)類別代表節(jié)點(diǎn)的興趣對節(jié)點(diǎn)社區(qū)進(jìn)行劃分?？紤]節(jié)點(diǎn)之間社區(qū)關(guān)系的機(jī)會網(wǎng)絡(luò)稱為基于社區(qū)的機(jī)會網(wǎng)絡(luò)，虛擬社區(qū)和社會連接是其中最常用的概念。同時(shí)，考慮節(jié)點(diǎn)的社區(qū)因素幫助消息路由和轉(zhuǎn)發(fā)也是基于社區(qū)的機(jī)會網(wǎng)絡(luò)區(qū)分于其他類型網(wǎng)絡(luò)最重要的特征。

由于社區(qū)網(wǎng)絡(luò)中節(jié)點(diǎn)需要經(jīng)常與其他節(jié)點(diǎn)相互進(jìn)行消息轉(zhuǎn)發(fā)，對節(jié)點(diǎn)的能量消耗較大；同時(shí)，社區(qū)網(wǎng)絡(luò)中為了提高數(shù)據(jù)的到達(dá)率，采用多副本的數(shù)據(jù)傳輸形式，導(dǎo)致對節(jié)點(diǎn)緩存占用較大。為節(jié)約節(jié)點(diǎn)緩存與能耗，本文將對社區(qū)網(wǎng)絡(luò)中的冗余開銷以及緩存管理進(jìn)行優(yōu)化，降低網(wǎng)絡(luò)的系統(tǒng)能耗與開銷，提高社區(qū)網(wǎng)絡(luò)性能。

2 相關(guān)工作

基于社區(qū)的機(jī)會網(wǎng)絡(luò)的路由算法是在機(jī)會網(wǎng)絡(luò)的經(jīng)典路由算法下發(fā)展起來的，主要有以下一些路由算法。

Epidemic[3]算法是采用泛洪的方式將消息轉(zhuǎn)發(fā)給每個(gè)相遇節(jié)點(diǎn)，直至消息到達(dá)目的節(jié)點(diǎn)。該方式使網(wǎng)絡(luò)中的消息副本數(shù)過多，增大了整個(gè)網(wǎng)絡(luò)的開銷。ProPHET[4]算法通過交換概要向量和預(yù)測概率矢量判斷對方節(jié)點(diǎn)與目的節(jié)點(diǎn)的相遇概率，攜帶消息的節(jié)點(diǎn)將消息轉(zhuǎn)發(fā)給與目的節(jié)點(diǎn)相遇概率更高的相遇節(jié)點(diǎn)，大大地降低了網(wǎng)絡(luò)中該消息的副本數(shù)。

Label[5]算法基于節(jié)點(diǎn)的興趣屬性將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分到不同社區(qū)，給不同興趣的節(jié)點(diǎn)分配不同的label（標(biāo)簽），擁有相同label的節(jié)點(diǎn)屬于同一社區(qū)。Bubble Rap[6]算法綜合考慮了節(jié)點(diǎn)的中心度和社區(qū)結(jié)構(gòu)來提高消息的傳輸效率，每個(gè)節(jié)點(diǎn)至少有一個(gè)label，相同label的節(jié)點(diǎn)屬于同一個(gè)社區(qū)。消息總是向中心度高的節(jié)點(diǎn)轉(zhuǎn)發(fā)，但消息匯聚在中心度高的節(jié)點(diǎn)的緩存中，有可能會造成消息的擁塞或者節(jié)點(diǎn)因能量消耗過快而死亡。STBID[7]算法提出一種節(jié)點(diǎn)間社會連接強(qiáng)度的計(jì)算機(jī)制，不同社會連接強(qiáng)度的節(jié)點(diǎn)分配具有不同的用于發(fā)送數(shù)據(jù)的令牌個(gè)數(shù)。SROR[8]算法和TDFSON[9]算法提供了節(jié)點(diǎn)社會關(guān)系的計(jì)算方法，用于在數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)選擇最優(yōu)的轉(zhuǎn)發(fā)節(jié)點(diǎn)。PaSS[10]算法利用計(jì)算節(jié)點(diǎn)間的社會相似度以及位置相似度選擇合適的下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)實(shí)現(xiàn)數(shù)據(jù)傳輸。EEMF[11]算法綜合考慮了節(jié)點(diǎn)的剩余能量與社會相似性進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。

BEEINFO算法[12]是一種人工蜂群算法，它的設(shè)計(jì)來源于SAN（socially-aware networking）框架下的基于興趣的轉(zhuǎn)發(fā)機(jī)制。BEEINFO算法利用移動節(jié)點(diǎn)的社會屬性、移動規(guī)律和學(xué)習(xí)能力來探測動態(tài)環(huán)境的密度和社會連接度。此外，它通過個(gè)體興趣對社區(qū)進(jìn)行分類，興趣信息雖然非常小，卻足以預(yù)測社區(qū)密度和社區(qū)連接度，同時(shí)也能節(jié)約緩存和能耗等資源。

消息丟棄算法[13]主要包括頭部丟棄策略、尾部丟棄策略和隨機(jī)丟棄策略。即當(dāng)緩沖區(qū)將要溢出時(shí)，從緩沖區(qū)的頭部、尾部隨機(jī)刪除緩沖區(qū)的消息。緩存替換算法[14]描述了BEEINFO在緩存不足情況下的操作：在社區(qū)間轉(zhuǎn)發(fā)階段，要發(fā)送到源社區(qū)外的消息將會被替換。對于這些消息，根據(jù)源節(jié)點(diǎn)記錄的不同目的社區(qū)的密度大小進(jìn)一步?jīng)Q定替換的順序：低密度的消息會被優(yōu)先替換，如果密度相同，則替換較老的消息。在社區(qū)內(nèi)轉(zhuǎn)發(fā)階段，即源節(jié)點(diǎn)和目的節(jié)點(diǎn)在同一社區(qū)，則源節(jié)點(diǎn)根據(jù)目的節(jié)點(diǎn)的社會連接度決定替換順序，目的社會連接度最低的消息最先被替換；如果社會連接度相同，則替換最老的消息。CABM[15]算法與緩存替代算法類似，同樣對消息目的節(jié)點(diǎn)與本節(jié)點(diǎn)的社區(qū)緊密程度對緩存中的消息優(yōu)先級進(jìn)行排序。

通過對BEEINFO算法的深入研究，發(fā)現(xiàn)BEEINFO算法中存在控制消息冗余、未考慮節(jié)點(diǎn)多鄰居消息轉(zhuǎn)發(fā)問題和對緩存中消息管理不合理的問題。為解決以上問題，提出了一種面向機(jī)會網(wǎng)絡(luò)基于興趣社區(qū)的高效路由與緩存管理算法——ERCMAON（an efficient routing and cache management algorithm based on interest-community for opportunity network），該算法通過精簡以及合并控制消息減少了冗余的控制開銷，同時(shí)增加對節(jié)點(diǎn)多鄰居情形的路由設(shè)計(jì)，降低了兩兩通信帶來的系統(tǒng)開銷和消息轉(zhuǎn)發(fā)時(shí)延；同時(shí)，基于消息的轉(zhuǎn)發(fā)次數(shù)優(yōu)化節(jié)點(diǎn)緩存管理機(jī)制，降低了有用信息被刪除的概率，從而可以提高消息的投遞成功率。并從理論分析和仿真驗(yàn)證了所提算法的性能。

3 系統(tǒng)模型與問題描述

3.1 系統(tǒng)模型

定義1 （移動模型）機(jī)會網(wǎng)絡(luò)中的節(jié)點(diǎn)具有一定的社會性，其運(yùn)動并不是完全隨機(jī)的，經(jīng)常相遇的節(jié)點(diǎn)之間有一個(gè)較高的接觸概率，在未來相遇的可能性也較大。

定義2 （社區(qū)密度[12]）表示節(jié)點(diǎn)到對應(yīng)社區(qū)熟悉度。假設(shè)在時(shí)間內(nèi)，節(jié)點(diǎn)遇到的社區(qū)內(nèi)節(jié)點(diǎn)的次數(shù)為，則當(dāng)前時(shí)刻的社區(qū)密度計(jì)算式為式（1），而式（2）是對該社區(qū)未來密度的預(yù)測。

其中，是社區(qū)密度的預(yù)測因子（常量），表明過去密度信息對現(xiàn)在密度信息的影響權(quán)重。社區(qū)的密度會隨著時(shí)間衰減，計(jì)算式為：

其中，是衰退指數(shù)（常量），是距離上次更新的時(shí)間間隔。式（1）用于在非同社區(qū)節(jié)點(diǎn)相遇時(shí)，更新到彼此社區(qū)的密度信息，式（3）用于距離上次更新時(shí)間后，再次更新到對應(yīng)社區(qū)的密度信息，式（2）用于預(yù)測未來Δ后到對應(yīng)社區(qū)的密度信息。

定義3 （社會連接度[13]）用來表示相同社區(qū)（興趣）的節(jié)點(diǎn)之間社會關(guān)系的強(qiáng)弱。節(jié)點(diǎn)的社會連接度信息只能在社區(qū)內(nèi)部發(fā)揮作用，社會連接度計(jì)算公式如式（4）所示，而式（5）是對未來社會連接度的預(yù)測。

其中，λ是接觸頻率（在每個(gè)時(shí)間窗口內(nèi)，節(jié)點(diǎn)與的相遇次數(shù)），d是接觸時(shí)間（在每個(gè)時(shí)間窗口內(nèi)節(jié)點(diǎn)與的接觸總時(shí)間），是預(yù)測因子（常量）。社會連接度也會隨著時(shí)間衰減，如式（6）所示。

式（4）用于在同社區(qū)節(jié)點(diǎn)相遇時(shí)，更新彼此的社會連接度信息，式（6）用于距離上次更新時(shí)間后，再次更新與對應(yīng)節(jié)點(diǎn)的社會連接度信息，式（5）用于預(yù)測未來Δ后與對應(yīng)節(jié)點(diǎn)的社會連接度信息。

3.2 問題描述

通過研究發(fā)現(xiàn)，現(xiàn)有以 BEEINFO 算法為代表的基于興趣劃分的社區(qū)網(wǎng)絡(luò)存在以下3個(gè)問題。

（1）控制消息存在冗余

BEEINFO算法節(jié)點(diǎn)相遇后的交互過程如圖1所示，兩個(gè)節(jié)點(diǎn)相遇，相互交換社區(qū)信息I和消息摘要列表Lm后，根據(jù)相遇節(jié)點(diǎn)是否同社區(qū)交換社區(qū)密度信息Density和社會連接度信息SocTie，再根據(jù)對方節(jié)點(diǎn)的密度信息或社會連接度信息，比較與對方節(jié)點(diǎn)消息列表中各消息目的地址的社會關(guān)系強(qiáng)度，然后向?qū)Ψ焦?jié)點(diǎn)提出請求（REQ），最后發(fā)送對方節(jié)點(diǎn)所請求的消息。研究發(fā)現(xiàn)該算法存在冗余的控制消息，當(dāng)前節(jié)點(diǎn)接收到對方節(jié)點(diǎn)的密度信息或社會連接度信息，可以判斷出對方將要請求的數(shù)據(jù)分組，因此不用等待對方請求，可以直接發(fā)送數(shù)據(jù)，同時(shí)，后發(fā)送I+Lm消息的節(jié)點(diǎn)可以將I+Lm消息和社區(qū)密度或社會連接度消息合并傳輸。

圖1 節(jié)點(diǎn)相遇后的交互過程

（2）節(jié)點(diǎn)多鄰居問題

BEEINFO算法中只研究了兩節(jié)點(diǎn)的相遇情況，考慮實(shí)際情況中，多個(gè)節(jié)點(diǎn)同時(shí)相遇的情形經(jīng)常發(fā)生，如圖2所示。

如果簡單地將兩節(jié)點(diǎn)的消息轉(zhuǎn)發(fā)過程應(yīng)用到多節(jié)點(diǎn)相遇的消息轉(zhuǎn)發(fā)過程中，會帶來不必要的冗余開銷；當(dāng)多鄰居彼此不在通信范圍內(nèi)，但彼此都有消息需要對方轉(zhuǎn)發(fā)時(shí)，本節(jié)點(diǎn)可以充當(dāng)中繼節(jié)點(diǎn)加快消息的轉(zhuǎn)發(fā)，因此多鄰居情形有必要考慮。

圖2 節(jié)點(diǎn)多鄰居情形

（3）緩存管理

原BEEINFO算法為了更高效地傳輸數(shù)據(jù)，只考慮當(dāng)前節(jié)點(diǎn)和目的節(jié)點(diǎn)的關(guān)系，把緩存中的消息根據(jù)轉(zhuǎn)發(fā)的優(yōu)先級按從高到低的順序排列，當(dāng)緩存不足時(shí)根據(jù)消息轉(zhuǎn)發(fā)優(yōu)先級相反的順序刪除緩存消息。但是該機(jī)制沒有考慮網(wǎng)絡(luò)中消息的副本個(gè)數(shù)，只存在唯一副本的消息如果被刪除則會影響網(wǎng)絡(luò)性能，被轉(zhuǎn)發(fā)過的消息原則上其重要程度應(yīng)當(dāng)降低。

4 ECMAON

針對以上所述的3個(gè)問題，本文提出了ERCMAON，ERCMAON通過增加節(jié)點(diǎn)多鄰居的消息轉(zhuǎn)發(fā)策略、精簡冗余的控制消息和改進(jìn)節(jié)點(diǎn)間的緩存管理機(jī)制，提高消息轉(zhuǎn)發(fā)效率。

4.1 ECMAON新機(jī)制

（1）精簡控制消息

相遇節(jié)點(diǎn)在交互I+Lm列表消息時(shí)，后發(fā)送I+Lm列表消息的節(jié)點(diǎn)在發(fā)送消息前，先根據(jù)對方節(jié)點(diǎn)的社區(qū)信息I更新記錄的到對方社區(qū)的密度信息（update density，相遇節(jié)點(diǎn)不同社區(qū)）或本社區(qū)的社會連接度信息（update SocTie，相遇節(jié)點(diǎn)同社區(qū)），計(jì)算雙方節(jié)點(diǎn)與消息列表Lm中每個(gè)消息目的節(jié)點(diǎn)的社會連接度（同社區(qū)時(shí)）或到消息目的節(jié)點(diǎn)的社區(qū)密度（不同社區(qū)時(shí)），若本節(jié)點(diǎn)及對方節(jié)點(diǎn)都與消息的目的節(jié)點(diǎn)位于不同社區(qū)，但對方節(jié)點(diǎn)到目的節(jié)點(diǎn)的社區(qū)密度高于本節(jié)點(diǎn)，或者對方節(jié)點(diǎn)與消息的目的節(jié)點(diǎn)位于同社區(qū)而本節(jié)點(diǎn)與目的節(jié)點(diǎn)位于不同社區(qū)，或者本節(jié)點(diǎn)及對方節(jié)點(diǎn)都與消息的目的節(jié)點(diǎn)位于同社區(qū)，但對方節(jié)點(diǎn)到目的節(jié)點(diǎn)的社會連接度高于本節(jié)點(diǎn)，這3種情形均可以表明對方節(jié)點(diǎn)與本節(jié)點(diǎn)相比，有更高的概率與消息的目的節(jié)點(diǎn)相遇，因此將列表中對應(yīng)的消息直接發(fā)送給對方節(jié)點(diǎn)，減少了對方節(jié)點(diǎn)進(jìn)行信息請求所帶來的開銷。然后根據(jù)對方節(jié)點(diǎn)的消息列表Lm，從本節(jié)點(diǎn)消息列表中去除對方列表中存在的消息，減少發(fā)送I+Lm列表的長度以降低開銷，同時(shí)在發(fā)送本節(jié)點(diǎn)的I+Lm列表時(shí)，當(dāng)I+Lm列表與本節(jié)點(diǎn)到其他社區(qū)的密度信息和到本社區(qū)其他節(jié)點(diǎn)的社會連接度信息總長度不超過數(shù)據(jù)分組中數(shù)據(jù)部分的最大長度時(shí)，將更新到其他社區(qū)的密度信息和到本社區(qū)其他節(jié)點(diǎn)的社會連接度信息加入消息后面一起發(fā)送，減少單獨(dú)發(fā)送密度信息和社會連接度信息引起的冗余開銷，改進(jìn)后的交互過程如圖3所示。

圖3 節(jié)點(diǎn)相遇后新交互的過程

（2）增加多鄰居消息轉(zhuǎn)發(fā)

針對多節(jié)點(diǎn)相遇問題，不失一般性，以3個(gè)節(jié)點(diǎn)為例，在節(jié)點(diǎn)發(fā)現(xiàn)階段，節(jié)點(diǎn)A接收到節(jié)點(diǎn)B和節(jié)點(diǎn)C的hello消息，得知B、C同時(shí)在節(jié)點(diǎn)A的通信范圍內(nèi)，此時(shí)節(jié)點(diǎn)A通過廣播發(fā)送自身的I+Lm列表消息，節(jié)點(diǎn)B、C接收到節(jié)點(diǎn)A的I+Lm列表消息后，更新記錄的到對方社區(qū)的密度信息或本社區(qū)的社會連接度信息，再向A發(fā)送本節(jié)點(diǎn)的I+Lm+密度或社會連接度消息，節(jié)點(diǎn)A在收到節(jié)點(diǎn)B、C的I+Lm+密度或社會連接度消息后，計(jì)算節(jié)點(diǎn)B、C及本節(jié)點(diǎn)消息列表Lm中每個(gè)消息目的節(jié)點(diǎn)的社會連接度（同社區(qū)時(shí)）或消息目的節(jié)點(diǎn)的社區(qū)密度（不同社區(qū)時(shí)），通過與消息目的節(jié)點(diǎn)的社區(qū)關(guān)系以及社會連接度和社區(qū)密度信息判斷與目的節(jié)點(diǎn)的相遇概率，若節(jié)點(diǎn)B、C與目的節(jié)點(diǎn)的相遇概率更高，則將列表中對應(yīng)的消息直接發(fā)送給節(jié)點(diǎn)B或C。其次，節(jié)點(diǎn)A在接收到節(jié)點(diǎn)B、C的I+Lm+密度或社會連接度消息后，提取節(jié)點(diǎn)B、C到各個(gè)社區(qū)的社區(qū)密度及社會連接度，在通過廣播發(fā)送自身密度或社會連接度消息時(shí)，密度或社會連接度消息中到每個(gè)社區(qū)的密度值及社會連接度取3個(gè)節(jié)點(diǎn)的最大值（若節(jié)點(diǎn)C中消息m的目的節(jié)點(diǎn)所在社區(qū)為5，節(jié)點(diǎn)A、B、C所在社區(qū)為1、2、3，并且節(jié)點(diǎn)A、B、C到社區(qū)5的密度分別為5、10、7，則節(jié)點(diǎn)A在發(fā)送自身密度或社會連接度消息時(shí)將到社區(qū)5的密度值寫成10，此時(shí)節(jié)點(diǎn)C會將消息m轉(zhuǎn)發(fā)給A，然后節(jié)點(diǎn)A再將消息m轉(zhuǎn)發(fā)給節(jié)點(diǎn)B，加速了消息的轉(zhuǎn)發(fā)）。節(jié)點(diǎn)B、C收到節(jié)點(diǎn)A的密度或社會連接度消息后，將需要轉(zhuǎn)發(fā)的消息轉(zhuǎn)發(fā)給節(jié)點(diǎn)A，節(jié)點(diǎn)A收到節(jié)點(diǎn)B、C轉(zhuǎn)發(fā)的消息后，提取出需要轉(zhuǎn)發(fā)的消息再轉(zhuǎn)發(fā)給對應(yīng)節(jié)點(diǎn)B和C。具體交互流程如圖4所示。

圖4 多節(jié)點(diǎn)消息交互過程

（3）改進(jìn)緩存管理機(jī)制

改進(jìn)的緩存管理機(jī)制優(yōu)先考慮消息在網(wǎng)絡(luò)中的唯一性，即節(jié)點(diǎn)自身產(chǎn)生并且還未轉(zhuǎn)發(fā)過的消息具有最高的優(yōu)先級。然后考慮節(jié)點(diǎn)與消息目的節(jié)點(diǎn)的社會關(guān)系，社會關(guān)系越強(qiáng)其對應(yīng)的消息的緩存優(yōu)先級越高，最后考慮當(dāng)前節(jié)點(diǎn)對消息的轉(zhuǎn)發(fā)次數(shù)，轉(zhuǎn)發(fā)次數(shù)越少，消息優(yōu)先級越高，具體的消息轉(zhuǎn)發(fā)優(yōu)先級的順序如下：

? 由節(jié)點(diǎn)自己產(chǎn)生且未轉(zhuǎn)發(fā)出去的消息優(yōu)先級最高；

? 消息的目的節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)同社區(qū)的消息，按當(dāng)前節(jié)點(diǎn)與消息目的節(jié)點(diǎn)之間的社會連接度排序，對應(yīng)社會連接度大的消息優(yōu)先級高；

? 消息目的節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)不同社區(qū)的消息，按當(dāng)前節(jié)點(diǎn)記錄的到目的社區(qū)的密度大小排列，對應(yīng)社區(qū)密度大的消息優(yōu)先級高；

? 當(dāng)前節(jié)點(diǎn)對自身產(chǎn)生的消息以及從其他節(jié)點(diǎn)接收到的消息，記錄每個(gè)消息本節(jié)點(diǎn)轉(zhuǎn)發(fā)過的次數(shù)，轉(zhuǎn)發(fā)次數(shù)越少，消息優(yōu)先級越高；

? 節(jié)點(diǎn)周期性地根據(jù)緩存列表中消息的變化情況調(diào)整列表順序，當(dāng)緩存不足時(shí)根據(jù)列表排序進(jìn)行有序的刪除操作。對應(yīng)的緩存消息優(yōu)先級示意如圖5所示。

圖5 緩存消息優(yōu)先級示意

4.2 ECMAON的操作

ERCMAON的操作過程如下。

步驟1 節(jié)點(diǎn)A在網(wǎng)絡(luò)中運(yùn)動，當(dāng)遇到其他節(jié)點(diǎn)并建立鄰居關(guān)系后，根據(jù)鄰居節(jié)點(diǎn)的不同個(gè)數(shù)，執(zhí)行不同操作，若相遇節(jié)點(diǎn)為1個(gè)，則向?qū)Ψ焦?jié)點(diǎn)發(fā)送自身興趣消息和攜帶消息的摘要信息，轉(zhuǎn)向步驟2；若相遇節(jié)點(diǎn)為多個(gè)，則向鄰居節(jié)點(diǎn)廣播自身興趣消息和攜帶消息的摘要信息，轉(zhuǎn)向步驟3。

步驟2 收到對方的興趣和消息摘要信息后，更新所記錄的社區(qū)密度信息和社會連接度信息，向?qū)Ψ桨l(fā)送本節(jié)點(diǎn)的I+Lm+密度或社會連接度消息，轉(zhuǎn)向步驟4。

步驟3 收到廣播的興趣和消息摘要信息后，更新所記錄的社區(qū)密度信息和社會連接度信息，向節(jié)點(diǎn)A發(fā)送本節(jié)點(diǎn)的I+Lm+密度或社會連接度消息，轉(zhuǎn)向步驟5。

步驟4 收到對方的I+Lm+密度或社會連接度消息，計(jì)算雙方節(jié)點(diǎn)與消息列表Lm中每個(gè)消息目的節(jié)點(diǎn)的社會連接度（同社區(qū)時(shí)）或消息目的節(jié)點(diǎn)的社區(qū)密度（不同社區(qū)），通過與消息目的節(jié)點(diǎn)的社區(qū)關(guān)系以及社會連接度和社區(qū)密度信息判斷與目的節(jié)點(diǎn)的相遇概率，若對方節(jié)點(diǎn)與目的節(jié)點(diǎn)的相遇概率更高，則將列表中對應(yīng)的消息直接發(fā)送給對方節(jié)點(diǎn)，然后向?qū)Ψ焦?jié)點(diǎn)發(fā)送本節(jié)點(diǎn)的密度或社會連接度消息，轉(zhuǎn)向步驟6。

步驟5 節(jié)點(diǎn)A計(jì)算鄰居節(jié)點(diǎn)（假設(shè)有兩個(gè)B、C）及本節(jié)點(diǎn)與自身消息列表Lm中每個(gè)消息目的節(jié)點(diǎn)的社會連接度（同社區(qū)時(shí)）或消息目的節(jié)點(diǎn)的社區(qū)密度（不同社區(qū)），通過與消息目的節(jié)點(diǎn)的社區(qū)關(guān)系以及社會連接度和社區(qū)密度信息判斷與目的節(jié)點(diǎn)的相遇概率，若節(jié)點(diǎn)B、C與目的節(jié)點(diǎn)的相遇概率更高，則將列表中對應(yīng)的消息直接發(fā)送給節(jié)點(diǎn)B或者C。其次，節(jié)點(diǎn)A在接收到節(jié)點(diǎn)B、C的I+Lm+密度或社會連接度消息后，提取節(jié)點(diǎn)B、C到各個(gè)社區(qū)的社區(qū)密度及社會連接度，在通過廣播發(fā)送自身密度或社會連接度消息時(shí)，密度或社會連接度消息中到每個(gè)社區(qū)的密度值及社會連接度取3個(gè)節(jié)點(diǎn)的最大值，轉(zhuǎn)向步驟7。

步驟6 收到節(jié)點(diǎn)A的I+Lm+密度或社會連接度消息后，執(zhí)行與步驟4相同的操作，轉(zhuǎn)發(fā)對應(yīng)消息。

步驟7 節(jié)點(diǎn)B、C收到節(jié)點(diǎn)A的I+Lm+密度或社會連接度消息后，計(jì)算本節(jié)點(diǎn)及節(jié)點(diǎn)A與消息列表Lm中每個(gè)消息目的節(jié)點(diǎn)的社會連接度（同社區(qū)時(shí)）或消息目的節(jié)點(diǎn)的社區(qū)密度（不同社區(qū)），通過與消息目的節(jié)點(diǎn)的社區(qū)關(guān)系以及社會連接度和社區(qū)密度信息判斷與目的節(jié)點(diǎn)的相遇概率，若節(jié)點(diǎn)A與目的節(jié)點(diǎn)的相遇概率更高，則將列表中對應(yīng)的消息直接發(fā)送給節(jié)點(diǎn)S，轉(zhuǎn)向步驟8。

步驟8 節(jié)點(diǎn)A收到節(jié)點(diǎn)B、C轉(zhuǎn)發(fā)的消息后，提取出需要轉(zhuǎn)發(fā)的消息再轉(zhuǎn)發(fā)給對應(yīng)節(jié)點(diǎn)B和C。

每次操作前，判斷當(dāng)前節(jié)點(diǎn)的緩存空間是否已滿，如果緩存已滿，則按照ERCMAON緩存管理機(jī)制處理。

該算法的偽代碼描述如下，其中表示鄰居節(jié)點(diǎn)個(gè)數(shù)，I表示節(jié)點(diǎn)的社區(qū)屬性，L表示節(jié)點(diǎn)所攜帶的消息列表，D,d和S,d表示節(jié)點(diǎn)與目的節(jié)點(diǎn)的社區(qū)密度及社會連接度，M,j表示節(jié)點(diǎn)的第個(gè)消息。

When node A encounters other nodes

if==1

then A unicasts(IA+LmA) to the encounter

the encounter updates DEand SEafter receiving (IA+LmA)

for(=1;

for(=1;

準(zhǔn)確搜集氣象信息是實(shí)現(xiàn)氣象預(yù)報(bào)準(zhǔn)確率提高的基礎(chǔ)。因此，必須加強(qiáng)對地面綜合氣象觀測的建設(shè)。在建設(shè)過程中，應(yīng)該將氣象預(yù)測作為建設(shè)目的和中心任務(wù)，利用最新技術(shù)協(xié)調(diào)各方力量，實(shí)現(xiàn)綜合氣象觀測能力的提高。在對相關(guān)體系進(jìn)行建設(shè)的過程中，氣象工作人員必須熟悉氣象知識和當(dāng)?shù)貧庀髼l件。氣象信息搜集應(yīng)嚴(yán)格依據(jù)相關(guān)規(guī)范，對于搜集到的氣象信息，要綜合匯總分析，運(yùn)用專業(yè)軟件進(jìn)行計(jì)算，以提高結(jié)果的準(zhǔn)確性。

if(MA,i== ME,j) deletes it from the LmE;

then sends (IE+LmE+E/E) to A

A updatesAandAafter receiving (IE+LmE+E/E)

for(=1;

for(=1;

if(MA,I== ME,j) deletes it from the LmA;

A calculatesE,d,E,d,A,d,A,d

||(IA!=ID && IE!=ID&&E,d>A,d))

A把MA,i發(fā)送給相遇者

then A把(DA/SA)發(fā)送給相遇者

相遇者運(yùn)行9~16行的相同進(jìn)程

else if N>1

then A把(IA+LmA)廣播給所有相遇者

每個(gè)相遇者都運(yùn)行4~8行的相同進(jìn)程

A運(yùn)行9~16行的相同進(jìn)程

A將DA / SA重置為自身與其所有相遇者之間的最高值

then把(DA/SA)廣播給所有相遇者

每個(gè)相遇者運(yùn)行9~16行的相同進(jìn)程

節(jié)點(diǎn)A在必要時(shí)中繼它收到的消息

end if

5 ERCMAON仿真驗(yàn)證及分析

本文利用ONE仿真平臺對ERCMAON的相關(guān)性能進(jìn)行仿真驗(yàn)證，并與BEEINFO、Epidemic和ProPHET算法對比相關(guān)性能的優(yōu)劣。

5.1 網(wǎng)絡(luò)場景及參數(shù)設(shè)置

仿真采用的場景為ONE中提供的default_ scenario，區(qū)域面積為4 500 m×3 400 m，并將該區(qū)域劃分為6個(gè)社區(qū)，社區(qū)中包含兩類移動節(jié)點(diǎn)：行人和公交車。并設(shè)置其對應(yīng)的移動速度、通信半徑和消息傳輸速率。以節(jié)點(diǎn)緩存大小為變量，研究在節(jié)點(diǎn)緩存大小不同時(shí)下各算法的性能。仿真中設(shè)置的具體參數(shù)見表1。

5.2 仿真結(jié)果及分析

5.2.1 消息投遞成功率

消息投遞成功率指源節(jié)點(diǎn)的消息成功轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)的數(shù)目占所有源節(jié)點(diǎn)產(chǎn)生的消息總量的百分比，計(jì)算式為：

其中，N表示成功轉(zhuǎn)發(fā)的數(shù)據(jù)分組的數(shù)目，N表示所有源節(jié)點(diǎn)生成的消息總量。

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

投遞成功率對比如圖6所示，由圖6可知，ERCMAON比BEEINFO算法及另外兩種算法的投遞成功率至少高2.0%，其原因是：節(jié)點(diǎn)交互過程中的冗余控制開銷減少，使得消息在相遇節(jié)點(diǎn)間的傳輸加快，在緩存大小一定時(shí)，消息的傳送成功率會因此提高；節(jié)點(diǎn)多鄰居情形下，中間節(jié)點(diǎn)可以作為中繼節(jié)點(diǎn)協(xié)助其他不在通信范圍內(nèi)的鄰居節(jié)點(diǎn)進(jìn)行消息的轉(zhuǎn)發(fā)，可以提高消息的傳送成功率；優(yōu)化的緩存管理機(jī)制保證網(wǎng)絡(luò)中唯一副本的消息可以在網(wǎng)絡(luò)優(yōu)先轉(zhuǎn)發(fā)，不會因?yàn)榕c目的節(jié)點(diǎn)之間的社會連接強(qiáng)度低就被刪除，網(wǎng)絡(luò)整體的投遞成功率會提高；同時(shí)社會關(guān)系強(qiáng)度代表著節(jié)點(diǎn)間的熟悉度和消息的可達(dá)率，利用社會關(guān)系強(qiáng)度進(jìn)行緩存排序，有利于提高消息的可達(dá)率和整個(gè)網(wǎng)絡(luò)的傳遞成功率。

5.2.2 數(shù)據(jù)投遞開銷

數(shù)據(jù)投遞開銷指將數(shù)據(jù)分組成功傳輸?shù)侥康墓?jié)點(diǎn)所需消耗的通信開銷（為完成數(shù)據(jù)消息順利傳輸?shù)侥康墓?jié)點(diǎn)，網(wǎng)絡(luò)中需要傳輸?shù)目偙忍財(cái)?shù)，包括數(shù)據(jù)消息和控制消息（即在數(shù)據(jù)轉(zhuǎn)發(fā)前的其他進(jìn)行交互的消息，包括hello消息、社區(qū)屬性與消息摘要列表消息、社區(qū)密度或社會連接度消息、請求消息）的比特總數(shù)。

圖6 投遞成功率對比

數(shù)據(jù)投遞開銷對比如圖7所示，由圖7可知，ERCMAON比BEEINFO及其他兩種算法的數(shù)據(jù)投遞開銷至少低9.7%，其原因是：ERCMAON減少了節(jié)點(diǎn)交互過程中的冗余控制開銷；在節(jié)點(diǎn)多鄰居節(jié)點(diǎn)情形下，利用廣播發(fā)送控制消息減少了分別發(fā)送的控制開銷；被轉(zhuǎn)發(fā)過的消息因已經(jīng)轉(zhuǎn)發(fā)到了更合適的節(jié)點(diǎn)，所以該消息的投遞成功率不會受到很大的影響，把該類消息的緩存優(yōu)先級降低之后，當(dāng)緩存不足時(shí)，優(yōu)先刪除轉(zhuǎn)發(fā)過的消息可以減少不必要的轉(zhuǎn)發(fā)開銷。

圖7 數(shù)據(jù)投遞開銷對比

5.2.3 歸一化控制開銷

歸一化控制開銷指網(wǎng)絡(luò)中消息成功送達(dá)目的節(jié)點(diǎn)過程中，控制消息的總比特?cái)?shù)占整個(gè)網(wǎng)絡(luò)中傳輸?shù)目偙忍財(cái)?shù)（即控制消息與數(shù)據(jù)消息比特?cái)?shù)總和）的比例?？刂崎_銷可以衡量所提算法的效率，可以反映出將數(shù)據(jù)分組成功傳輸?shù)侥康墓?jié)點(diǎn)所需消耗的通信開銷占比，其計(jì)算式如下：

其中，N表示所有節(jié)點(diǎn)產(chǎn)生的控制分組開銷總量，N表示被目的節(jié)點(diǎn)接收到的數(shù)據(jù)分組開銷總量。

歸一化控制開銷對比如圖8所示，由圖8可知，ERCMAON比BEEINFO至少低1.7%的歸一化控制開銷。其原因是：ERCMAON算法減少了節(jié)點(diǎn)交互過程中的冗余控制開銷，使得消息的總體控制開銷降低，由于在ERCMAON中消息的成功率增加，所以歸一化控制開銷也得到降低；在節(jié)點(diǎn)多鄰居節(jié)點(diǎn)情形下，利用廣播發(fā)送控制消息減少了分別發(fā)送的控制開銷，同時(shí)中間節(jié)點(diǎn)作為中繼節(jié)點(diǎn)時(shí)可以加快消息的轉(zhuǎn)發(fā)速率和投遞成功率，因此對應(yīng)的歸一化控制開銷得到降低；采用ERCMAON的節(jié)點(diǎn)對緩存中的消息重新排序，轉(zhuǎn)發(fā)過的節(jié)點(diǎn)的重要程度降低，轉(zhuǎn)發(fā)過的消息優(yōu)先被刪除，這樣既提高了消息的整體投遞率，又減少了傳送到目的社區(qū)的消息在目的社區(qū)外的傳遞。

圖8 歸一化控制開銷對比

5.2.4 傳輸時(shí)延

傳輸時(shí)延反映成功傳輸一個(gè)數(shù)據(jù)分組到目的節(jié)點(diǎn)所需要的平均時(shí)間，其計(jì)算式如下：

其中，表示目的節(jié)點(diǎn)接收到的數(shù)據(jù)分組的數(shù)目，T表示數(shù)據(jù)分組的時(shí)延。

消息傳輸時(shí)延對比如圖9所示，由圖9可以看出，ERCMAON、BEEINFO算法的傳輸時(shí)延比Epidemic和ProPHET算法的傳輸時(shí)延高，其主要原因是Epidemic和ProPHET算法對消息轉(zhuǎn)發(fā)的限制更少，網(wǎng)絡(luò)中消息副本更多，攜帶消息的節(jié)點(diǎn)在更短時(shí)間內(nèi)成功投遞消息的可能性更高。ERCMAON的傳輸時(shí)延比BEEINFO算法至少要低2.4%，其原因是：ERCMAON減少了節(jié)點(diǎn)交互過程中的冗余控制開銷，消息在相遇節(jié)點(diǎn)間傳輸?shù)酶欤辉诠?jié)點(diǎn)多鄰居情形下，消息經(jīng)中間節(jié)點(diǎn)中繼時(shí)可以明顯降低消息的傳輸時(shí)延。

圖9 消息傳輸時(shí)延對比

6 結(jié)束語

本文提出了一種基于興趣社區(qū)的高效路由與緩存管理路由算法——ERCMAON，該算法通過合并控制消息、優(yōu)化緩存管理以及節(jié)點(diǎn)多鄰居情形的路由設(shè)計(jì)，降低了系統(tǒng)開銷并增強(qiáng)了消息傳輸成功率。但是，目前的研究是假設(shè)節(jié)點(diǎn)入網(wǎng)前已分配有唯一且固定的興趣（社區(qū)），對于社區(qū)的劃分并未詳細(xì)探究，未來將針對節(jié)點(diǎn)的社區(qū)劃分進(jìn)行研究，同時(shí)設(shè)計(jì)單一節(jié)點(diǎn)同屬多個(gè)社區(qū)情形的路由機(jī)制。

[1] STAVROULAKI V, TSAGKARIS K, LOGOTHETIS M, et al. Opportunistic networks[J]. IEEE Vehicular Technology Magazine, 2011, 6(3): 52-59.

[2] HOSSMANN T, NOMIKOS G, SPYROPOULOS T, et al. Collection and analysis of multi-dimensional network data for opportunistic networking research[J]. Computer Communications, 2012, 35(13): 1613-1625.

[3] VAHDAT A, BECKER D. Epidemic routing for partially-connected Ad Hoc networks[J]. Master Thesis, 2000.

[4] LINDGREN A, DORIA A. Probabilistic routing in intermittently connected networks[J]. ACM Sigmobile Mobile Computing & Communications Review, 2004, 7(3): 239-254.

[5] MEI A, MORABITO G, SANTI P, et al. Social-aware stateless forwarding in pocket switched networks[C]//2011 IEEE INFOCOM, April 10-15, 2011, Shanghai, China. Piscataway: IEEE Press, 2011: 251-255.

[6] PAN H, CROWCROFT J, EIKO Y. BUBBLE rap: social-based forwarding in delay-tolerant networks[J]. IEEE Transactions on Mobile Computing, 2010, 10(11): 1576-1589.

[7] WANG Y, WU J. Social-tie-based information dissemination in mobile opportunistic social networks[C]//2013 IEEE 14th International Symposium and Workshops on aWorld of Wireless, Mobile and Multimedia Networks (WoWMoM), June 4-7, 2013, Madrid, Spain. Piscataway: IEEE Press, 2013: 1-6.

[8] WONG G, JIA X. A novel socially-aware opportunistic routing algorithm in mobile social networks[C]//International Conference on Computing, Networking and Communications, Jan 28-31, 2013, San Diego, USA. Piscataway: IEEE Press, 2013: 514-518.

[9] BECKER C, SCHLINGA S, FISCHER S. Trustful data forwarding in social opportunistic networks[C]//Ubiquitous Intelligence and Computing, Dec 18-21, 2013, Vietri, Italy. Piscataway: IEEE Press, 2013: 430-437.

[10] JANG K, LEE J, KIM S K, et al. An adaptive routing algorithm considering position and social similarities in an opportunistic network[J]. Wireless Networks, 2016, 22(5): 1537-1551.

[11] ZHANG S, WANG X, YAO M, et al. Community-based message transmission with energy efficient in opportunistic networks[C]//International Conference on Web Information Systems Engineering, November 16-18, Zhangjiajie, China. Berlin: Springer Press, 2016: 411-423.

[12] LI J, LIU L, XIA F. BEEINFO: data forwarding based on interest and swarm intelligence for socially-aware networking[C]//International Conference on Mobile Computing & Networking, September 30-October 4, 2013, Miami, USA. New York: ACM Press, 2013: 175-178.

[13] ERRAMILLI V, CROVELLA M. Forwarding in opportunistic networks with resource constraints[C]//The 3rd ACM Workshop on Challenged Networks, September 15-15, 2008, San Francisco, USA. New York: ACM Press, 2008: 41-48.

[14] XIA F, LIU L, LI J, et al. BEEINFO: interest-based forwarding using artificial bee colony for socially aware networking[J]. IEEE Transactions on Vehicular Technology, 2015, 64(3): 1188-1200.

[15] ZHOU J, LIN Y, ZHOU S, et al. Community-based adaptive buffer management strategy in opportunistic network[C]//International Conference on Security, Privacy and Anonymity in Computation, Communication and Storage, November 16-18, 2016, Zhangjiajie, China. Berlin: Springer Press, 2016: 16-25.

An efficient routing and cache management algorithm based on interest-community for opportunity networks

REN Zhi, WANG Kunlong, LI Xiufeng

Chongqing Key Lab of Mobile Communication Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China

Aiming at the problem of control message redundancy existing in BEEINFO algorithm, unconsidered node multi-neighbor message forwarding problem and unreasonable management of message in cache, an efficient routing and cache management algorithm named ERCMAON which based on community of interest was proposed. The message forwarding delay was reduced by streamlining control messages, increasing the route design for multiple-neighbor nodes. At the same time, by optimizing the node cache management mechanism, the probability of deleting useful information was reduced, which could improve the success rate of message delivery. Simulation results show thatcompared with the BEEINFO algorithm, the delivery success rate of ERCMAON algorithm increases by at least 2.0%, the data delivery overhead and the normalized control overhead reduces by at least 9.7% and 1.7% respectively. At the same time, the message transmission delay reduces at least 2.4%.

opportunity network, community, efficient, cache management, routing algorithm

TP393.4

A

10.11959/j.issn.1000?0801.2018160

任智（1971?），男，博士后，重慶郵電大學(xué)移動通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室教授、博士生導(dǎo)師，主要研究方向?yàn)閷拵ё越M網(wǎng)與無線通信。

王坤龍（1993?），男，重慶郵電大學(xué)移動通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室碩士生，主要研究方向?yàn)槲锫?lián)網(wǎng)理論技術(shù)及無線MAC協(xié)議。

李秀峰（1991?），男，重慶郵電大學(xué)移動通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室碩士生，主要研究方向?yàn)闄C(jī)會網(wǎng)絡(luò)路由算法。

2017?11?23；

2018?04?16

國家自然科學(xué)基金資助項(xiàng)目（No.61379159）；長江學(xué)者和創(chuàng)新團(tuán)隊(duì)發(fā)展計(jì)劃基金資助項(xiàng)目（No.IRT1299）

The National Natural Science Foundation of China (No.61379159), Program for Changjiang Scholars and Innovative Research Team in University (No.IRT1299)