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

任智，王坤龍，李秀峰

?

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

任智，王坤龍，李秀峰

（重慶郵電大學移動通信技術(shù)重慶市重點實驗室，重慶 400065）

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

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

1 引言

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

3.1 系統(tǒng)模型

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

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

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

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

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

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

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

3.2 問題描述

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

（1）控制消息存在冗余

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

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

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

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

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

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

（3）緩存管理

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

4 ECMAON

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

4.1 ECMAON新機制

（1）精簡控制消息

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

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

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

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

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

（3）改進緩存管理機制

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

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

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

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

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

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

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

4.2 ECMAON的操作

ERCMAON的操作過程如下。

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

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

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

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

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

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

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

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

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

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

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;

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

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ā)送給相遇者

相遇者運行9~16行的相同進程

else if N>1

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

每個相遇者都運行4~8行的相同進程

A運行9~16行的相同進程

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

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

每個相遇者運行9~16行的相同進程

節(jié)點A在必要時中繼它收到的消息

end if

5 ERCMAON仿真驗證及分析

本文利用ONE仿真平臺對ERCMAON的相關(guā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個社區(qū)，社區(qū)中包含兩類移動節(jié)點：行人和公交車。并設(shè)置其對應(yīng)的移動速度、通信半徑和消息傳輸速率。以節(jié)點緩存大小為變量，研究在節(jié)點緩存大小不同時下各算法的性能。仿真中設(shè)置的具體參數(shù)見表1。

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

5.2.1 消息投遞成功率

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

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

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

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

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

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

圖6 投遞成功率對比

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

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

5.2.3 歸一化控制開銷

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

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

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

圖8 歸一化控制開銷對比

5.2.4 傳輸時延

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

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

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

圖9 消息傳輸時延對比

6 結(jié)束語

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

[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?），男，博士后，重慶郵電大學移動通信技術(shù)重慶市重點實驗室教授、博士生導師，主要研究方向為寬帶自組網(wǎng)與無線通信。

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

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

2017?11?23；

2018?04?16

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

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