姚建盛 劉艷玲

摘 要：針對(duì)當(dāng)前機(jī)會(huì)網(wǎng)絡(luò)數(shù)據(jù)分發(fā)協(xié)議面向的主要是單源多宿數(shù)據(jù)分發(fā)模型的問題，提出了一種多源多宿機(jī)會(huì)網(wǎng)絡(luò)數(shù)據(jù)分發(fā)模型，設(shè)計(jì)了一種興趣和編碼感知（ICA，interest-and coding-aware）的機(jī)會(huì)網(wǎng)絡(luò)數(shù)據(jù)分發(fā)協(xié)議。首先，由中繼節(jié)點(diǎn)將滿足同一興趣的不同數(shù)據(jù)源進(jìn)行流間隨機(jī)線性網(wǎng)絡(luò)編碼后轉(zhuǎn)發(fā);其次，擁有相同興趣的節(jié)點(diǎn)彼此交換興趣編碼數(shù)據(jù)，當(dāng)節(jié)點(diǎn)收到足夠多的滿足同一興趣的線性無關(guān)編碼包時(shí)，解碼得到多個(gè)感興趣的原始數(shù)據(jù);最后，對(duì)多源多宿機(jī)會(huì)網(wǎng)絡(luò)數(shù)據(jù)分發(fā)進(jìn)行了ONE仿真。結(jié)果表明，和基于ER的多源多宿數(shù)據(jù)分發(fā)相比，ICA能通過較小的緩存、網(wǎng)絡(luò)帶寬和網(wǎng)絡(luò)負(fù)載獲得較低的分發(fā)時(shí)延。研究結(jié)果可為機(jī)會(huì)網(wǎng)絡(luò)中的網(wǎng)絡(luò)數(shù)據(jù)分發(fā)機(jī)制提供一種可行、高效的解決方案。

關(guān)鍵詞：計(jì)算機(jī)網(wǎng)絡(luò);機(jī)會(huì)網(wǎng)絡(luò);多源多宿數(shù)據(jù)分發(fā);流間隨機(jī)線性網(wǎng)絡(luò)編碼;興趣

中圖分類號(hào)：TP393 ? 文獻(xiàn)標(biāo)識(shí)碼：A ? doi：10.7535/hbkd.2020yx01004

Abstract：Aiming at the currently problem that data dissemination protocols in opportunistic networks are mainly based on single-source and multi-destination model， a multi-source and multi-destination data dissemination model for opportunistic networks is proposed， and an interest-and coding-aware （ICA） data dissemination protocol is designed.First， relays encode the different data flows which satisfy the same interest via inter-flow random linear network coding and then forward them. Second， nodes sharing the same interest exchange their interest coding data with each other. Once receiving enough independent coding packets which satisfy the same interest， the nodes decode the coding packets and obtain the original interest data. At last， ONE simulation is conducted for the multi-source and multi-destination data dissemination. The result shows that compared with the data dissemination protocol based on ER， ICA can obtain lower delay while consuming fewer buffers， less network bandwidth and network cost. The research result provides a feasible and efficient solution for opportunistic networks data dissemination mechanism.

Keywords：computer network; opportunistic networks; multi-source and multi-destination data dissemination; inter-flow random linear network coding; interest

機(jī)會(huì)網(wǎng)絡(luò)[1-2]能實(shí)現(xiàn)不存在完整通信鏈路的源節(jié)點(diǎn)和目的節(jié)點(diǎn)間的通信，對(duì)IoT和普適計(jì)算有重要意義。在機(jī)會(huì)網(wǎng)絡(luò)的許多實(shí)際應(yīng)用中，如廣告發(fā)布、新聞傳播和環(huán)境通告等，數(shù)據(jù)沒有明確的目的地址，無法使用路由技術(shù)，而是通過數(shù)據(jù)分發(fā)實(shí)現(xiàn)這種以內(nèi)容為中心的網(wǎng)絡(luò)通信[3-5]。數(shù)據(jù)分發(fā)在時(shí)間、空間和控制流上完全解耦了數(shù)據(jù)生產(chǎn)者和消費(fèi)者，更加適合間歇性連接的機(jī)會(huì)網(wǎng)絡(luò)，成為機(jī)會(huì)網(wǎng)絡(luò)當(dāng)前的一個(gè)研究熱點(diǎn)。

現(xiàn)有機(jī)會(huì)網(wǎng)絡(luò)數(shù)據(jù)分發(fā)主要基于單源多宿SSMD （single-source and multi-destination）數(shù)據(jù)分發(fā)模型[4，6-7]，即1個(gè)數(shù)據(jù)可以存在多個(gè)節(jié)點(diǎn)興趣，但1個(gè)節(jié)點(diǎn)興趣只有1個(gè)匹配數(shù)據(jù)。然而在一些機(jī)會(huì)網(wǎng)絡(luò)數(shù)據(jù)分發(fā)場(chǎng)景中，存在多源多宿（multi-source and multi-destination，MSMD）數(shù)據(jù)分發(fā)情況。例如，針對(duì)同一場(chǎng)交通事故或同一區(qū)域的環(huán)境狀態(tài)，由于不同節(jié)點(diǎn)觀察角度或位置不同導(dǎo)致其反饋的信息可能不一致;另外關(guān)注同一事件的多個(gè)興趣節(jié)點(diǎn)也往往需要從不同角度了解該事件。于是出現(xiàn)一種將多個(gè)相似或相關(guān)的數(shù)據(jù)分發(fā)給一組興趣相似或相同的節(jié)點(diǎn)情況，為此定義了一種基于模糊匹配的MSMD機(jī)會(huì)網(wǎng)絡(luò)數(shù)據(jù)分發(fā)模型。

MSMD數(shù)據(jù)分發(fā)在同等條件下一般比SSMD數(shù)據(jù)分發(fā)產(chǎn)生更大的數(shù)據(jù)流量，因而面臨更大挑戰(zhàn)。比如在SSMD數(shù)據(jù)分發(fā)中，為提高投遞率和減小時(shí)延常采用多副本多路徑傳輸技術(shù)[3]。然而MSMD數(shù)據(jù)分發(fā)卻不能直接應(yīng)用該技術(shù)，因?yàn)槎喔北径嗦窂絺鬏敃?huì)進(jìn)一步增加網(wǎng)絡(luò)流量，可能會(huì)導(dǎo)致中繼節(jié)點(diǎn)因緩存溢出或帶寬不足而降低數(shù)據(jù)分發(fā)性能，因此提高M(jìn)SMD數(shù)據(jù)分發(fā)性能的關(guān)鍵是壓縮數(shù)據(jù)流量以緩解對(duì)中繼節(jié)點(diǎn)緩存和帶寬的需求。

當(dāng)前壓縮網(wǎng)絡(luò)流量的一種有效方法是網(wǎng)絡(luò)編碼技術(shù)[9-10]，該技術(shù)允許網(wǎng)絡(luò)中間節(jié)點(diǎn)編碼，推翻了獨(dú)立比特不能再被壓縮的經(jīng)典理論，有效提高了網(wǎng)絡(luò)吞吐量，在無線網(wǎng)絡(luò)通信中已有大量研究[11]。SSMD機(jī)會(huì)網(wǎng)絡(luò)數(shù)據(jù)分發(fā)主要基于隨機(jī)線性網(wǎng)絡(luò)編碼（RLNC， random liner network coding）[12]，并且是作為流內(nèi)網(wǎng)絡(luò)編碼使用[13]，文獻(xiàn)[14]認(rèn)為貪婪復(fù)制阻礙流間網(wǎng)絡(luò)編碼獲益，而事實(shí)上流間網(wǎng)絡(luò)編碼更適合壓縮數(shù)據(jù)流量，提高網(wǎng)絡(luò)吞吐量[15-16]。典型的流間網(wǎng)絡(luò)編碼是機(jī)會(huì)網(wǎng)絡(luò)編碼（ONC， opportunistic network coding）[17]，然而在節(jié)點(diǎn)稀疏情況下ONC的編碼機(jī)會(huì)很小而且并不適合MSMD數(shù)據(jù)分發(fā)場(chǎng)景[18-19]。為此本文將RLNC當(dāng)作流間網(wǎng)絡(luò)編碼使用，提出一種興趣和編碼感知（ICA， interest- and coding-aware）的機(jī)會(huì)網(wǎng)絡(luò)MSMD數(shù)據(jù)分發(fā)方法。仿真實(shí)驗(yàn)證明，和基于ER[20]的MSMD數(shù)據(jù)分發(fā)相比，ICA通過較小的緩存、網(wǎng)絡(luò)帶寬和網(wǎng)絡(luò)負(fù)載能獲得較低的分發(fā)時(shí)延。

1 MSMD數(shù)據(jù)分發(fā)模型

機(jī)會(huì)網(wǎng)絡(luò)MSMD數(shù)據(jù)分發(fā)系統(tǒng)就是以機(jī)會(huì)網(wǎng)絡(luò)為通信基礎(chǔ)，將系統(tǒng)發(fā)布的多個(gè)相似數(shù)據(jù)從多個(gè)源節(jié)點(diǎn)轉(zhuǎn)發(fā)給多個(gè)興趣相似的目的節(jié)點(diǎn)，可用二元組（M，Gt）表示。M是系統(tǒng)發(fā)布數(shù)據(jù)（不包括控制消息等）的集合，M={M1，M2，…，Mn}，其中Mi（i=1，2，…，n）是一組相似或相關(guān)數(shù)據(jù)的集合。數(shù)據(jù)可能來自于Internet，如天氣信息、股票信息和新聞等，也可能由節(jié)點(diǎn)生成，如照片、本地交通狀況和環(huán)境信息等。為簡(jiǎn)化系統(tǒng)設(shè)計(jì)，假定相似數(shù)據(jù)大小一致。Gt是機(jī)會(huì)網(wǎng)絡(luò)動(dòng)態(tài)鏈接圖，Gt=（Vt，Et），其中Vt和Et分別是t時(shí)刻移動(dòng)節(jié)點(diǎn)集合和節(jié)點(diǎn)間連接鏈路集合，系統(tǒng)假設(shè)節(jié)點(diǎn)集合在系統(tǒng)運(yùn)行過程中保持不變恒為V，由于節(jié)點(diǎn)移動(dòng)、無線鏈路不穩(wěn)定等原因，節(jié)點(diǎn)間鏈路Et隨時(shí)間變化而改變。為描述MSMD數(shù)據(jù)分發(fā)模型，給出如下相關(guān)概念。

定義1 頻道：頻道是系統(tǒng)預(yù)定義的主題，記為C，頻道的集合記為Ω，即Ω={C1，C2，…，Cs}，s是系統(tǒng)預(yù)定義頻道數(shù)。

定義2 數(shù)據(jù)屬性： 數(shù)據(jù)屬性是由數(shù)據(jù)發(fā)布者標(biāo)記的數(shù)據(jù)和預(yù)定義頻道的相關(guān)程度。數(shù)據(jù)m的屬性記為Am，Am=[p1 p2 ?… ps]，其中pi（0≤pi≤1）是概率值，表示數(shù)據(jù)m和頻道Ci的相關(guān)程度。

定義3 節(jié)點(diǎn)興趣： 節(jié)點(diǎn)興趣是節(jié)點(diǎn)對(duì)系統(tǒng)預(yù)定義頻道感興趣程度。節(jié)點(diǎn)v的興趣記為Iv，Iv=[p1 p2 … ps]，其中pi（0≤pi≤1）是概率值，描述節(jié)點(diǎn)v對(duì)頻道Ci的興趣程度。

定義4 興趣度：節(jié)點(diǎn)v對(duì)數(shù)據(jù)m的興趣度記為Iv→m，是節(jié)點(diǎn)v的興趣向量Iv和數(shù)據(jù)m的屬性向量Am的相似度，即Iv→m=sim（Iv，Am）。當(dāng)相似度Iv→m≥δI （δI是興趣度閾值）時(shí)，稱節(jié)點(diǎn)v對(duì)數(shù)據(jù)m感興趣。這里的相似向量不僅夾角比較小，而且長(zhǎng)度也相近，因此相似度公式為sim（α，β）=∑（αi-）·（βi-）∑（αi-）2·∑（βi-）2 。（1） ?定義5 相似數(shù)據(jù)：如果數(shù)據(jù)i和j的屬性相似度sim（Ai，Aj）≥δm（δm是數(shù)據(jù)屬性相似度閾值），則稱數(shù)據(jù)i和j為相似數(shù)據(jù)。

定義6 興趣組：如果節(jié)點(diǎn)u和v的興趣相似度sim（Iu，Iv）≥δn（δn是興趣相似度閾值），則稱節(jié)點(diǎn)u和v在同一興趣組，為簡(jiǎn)化系統(tǒng)設(shè)計(jì)，假定興趣組內(nèi)節(jié)點(diǎn)興趣相同。

針對(duì)一組相似數(shù)據(jù)集合Mi，機(jī)會(huì)網(wǎng)絡(luò)MSMD數(shù)據(jù)分發(fā)模型如圖1所示。節(jié)點(diǎn)集合V=VP∪VS∪VR，其中VP={P1，P2，…，Pi}是Mi的發(fā)布節(jié)點(diǎn)集合，發(fā)布節(jié)點(diǎn)是數(shù)據(jù)的生產(chǎn)者，不知道誰需要數(shù)據(jù)，只是將其注入到網(wǎng)絡(luò);VS={S1，S2，…，Sj}是Mi的訂閱節(jié)點(diǎn)集合，即興趣組，訂閱節(jié)點(diǎn)是數(shù)據(jù)的消費(fèi)者，不知道數(shù)據(jù)在哪，只是向網(wǎng)絡(luò)表達(dá)自己的訂閱興趣;VR={R1，R2，…，Rk}是Mi的中繼節(jié)點(diǎn)集合，負(fù)責(zé)將數(shù)據(jù)從生產(chǎn)者轉(zhuǎn)發(fā)到消費(fèi)者。訂閱節(jié)點(diǎn)和發(fā)布節(jié)點(diǎn)也可參與數(shù)據(jù)轉(zhuǎn)發(fā)，1個(gè)節(jié)點(diǎn)可以同時(shí)是不同相似數(shù)據(jù)集合的生產(chǎn)者、消費(fèi)者和中繼者。當(dāng)|Mi|和|VP|為1時(shí)，即只有1個(gè)相似數(shù)據(jù)和1個(gè)發(fā)布節(jié)點(diǎn)，MSMD數(shù)據(jù)分發(fā)變成SSMD數(shù)據(jù)分發(fā)。

2 興趣和編碼感知MSMD數(shù)據(jù)分發(fā)

首先給出機(jī)會(huì)網(wǎng)絡(luò)環(huán)境下興趣和編碼感知MSMD數(shù)據(jù)分發(fā)的基本思想和面臨的問題，然后設(shè)計(jì)相關(guān)數(shù)據(jù)結(jié)構(gòu)和編碼、解碼算法。

2.1 基本思想

SSMD數(shù)據(jù)分發(fā)一般通過多副本多路徑技術(shù)提高數(shù)據(jù)分發(fā)性能，但為了減少網(wǎng)絡(luò)負(fù)載，一般采用限制副本數(shù)，假設(shè)有n個(gè)訂閱節(jié)點(diǎn)，以Binary Spray[21]方式分發(fā)1個(gè)數(shù)據(jù)，副本限制數(shù)為C（C≥n），則分發(fā)路徑是如圖2 a）所示的以發(fā)布節(jié)點(diǎn)為根的二叉樹，最終網(wǎng)絡(luò)中存在C個(gè)副本，當(dāng)所有訂閱節(jié)點(diǎn)都得到1個(gè)副本時(shí)完成數(shù)據(jù)分發(fā)。而對(duì)于有k個(gè)相似數(shù)據(jù)的MSMD數(shù)據(jù)分發(fā)，如果采用類似方法，則需要k棵與圖2 a）相似的二叉樹，最終網(wǎng)絡(luò)中存在C×k個(gè)數(shù)據(jù)，每個(gè)訂閱節(jié)點(diǎn)需要得到k個(gè)不同的數(shù)據(jù)副本。但實(shí)際上k個(gè)二叉樹是有交集的，如圖2 b）所示，數(shù)據(jù)m1和數(shù)據(jù)mk在分發(fā)過程中的某一時(shí)段同時(shí)經(jīng)過節(jié)點(diǎn)v，如果節(jié)點(diǎn)v將2個(gè)不同數(shù)據(jù)流編碼成1個(gè)數(shù)據(jù)后再轉(zhuǎn)發(fā)，則壓縮了數(shù)據(jù)流量，節(jié)省了網(wǎng)絡(luò)帶寬和存儲(chǔ)空間，避免了因資源不足而導(dǎo)致數(shù)據(jù)分發(fā)的性能降低。ICA的基本思想就是將來自不同數(shù)據(jù)流的相似數(shù)據(jù)看作同一個(gè)數(shù)據(jù)流的不同片段進(jìn)行RLNC，然后在網(wǎng)絡(luò)中轉(zhuǎn)發(fā)，當(dāng)目的節(jié)點(diǎn)收到k個(gè)線性無關(guān)RLNC包時(shí)，解碼得到k個(gè)相似的原始興趣數(shù)據(jù)，ICA的數(shù)據(jù)分發(fā)路徑如圖2 c）所示是一個(gè)網(wǎng)狀結(jié)構(gòu)。

2.2 數(shù)據(jù)結(jié)構(gòu)

為實(shí)現(xiàn)興趣和編碼感知MSMD數(shù)據(jù)分發(fā)，下面給出數(shù)據(jù)、興趣的格式和節(jié)點(diǎn)緩存的數(shù)據(jù)結(jié)構(gòu)。

系統(tǒng)發(fā)布數(shù)據(jù)有兩類：原始數(shù)據(jù)和編碼數(shù)據(jù)。為統(tǒng)一編碼操作，設(shè)置一致的數(shù)據(jù)包格式，部分?jǐn)?shù)據(jù)包頭字段為{idm，ml，gv，Am，data}。其中idm是數(shù)據(jù)m的標(biāo)識(shí)。ml是編碼數(shù)據(jù)中所包含原始數(shù)據(jù)的id向量。gv是和ml對(duì)應(yīng)的全局編碼系數(shù)向量，如果是原始數(shù)據(jù)，則ml=[idm]，gv=[1]。Am是數(shù)據(jù)m的屬性向量，m是原始數(shù)據(jù)由源節(jié)點(diǎn)初始化Am;如果m是編碼數(shù)據(jù)，則由緩存該編碼數(shù)據(jù)的節(jié)點(diǎn)重新設(shè)置Am。data是數(shù)據(jù)內(nèi)容字段，為簡(jiǎn)化算法設(shè)計(jì)，假定數(shù)據(jù)字段長(zhǎng)度相同，但在實(shí)際環(huán)境中規(guī)定數(shù)據(jù)最大長(zhǎng)度，如果數(shù)據(jù)長(zhǎng)度不夠，則用相同bit位填充。

本文考慮兩類節(jié)點(diǎn)興趣：臨時(shí)興趣和長(zhǎng)期興趣。如對(duì)某路段當(dāng)前交通狀態(tài)的查詢興趣是臨時(shí)興趣，而對(duì)某一股票、天氣或新聞的訂閱可能是長(zhǎng)期興趣且具有一定周期性。節(jié)點(diǎn)興趣數(shù)據(jù)結(jié)構(gòu)為{idv，Iv，ts，te，θ}，其中idv是訂閱節(jié)點(diǎn)v的id;Iv是節(jié)點(diǎn)v的興趣向量;ts和te分別是興趣訂閱的開始時(shí)間和結(jié)束時(shí)間;θ代表節(jié)點(diǎn)興趣類型，當(dāng)θ=0時(shí)則興趣是臨時(shí)興趣，當(dāng)θ>0時(shí)則興趣是長(zhǎng)期興趣，此時(shí)θ表示編碼周期。節(jié)點(diǎn)一旦生成，興趣便通過gossip方式向網(wǎng)絡(luò)表達(dá)。

節(jié)點(diǎn)緩存分成兩部分：中繼緩存Br和目的緩存Bd，前者用來幫助其他節(jié)點(diǎn)緩存數(shù)據(jù)，后者用來緩存自己的興趣數(shù)據(jù)。

中繼緩存是興趣感知緩存，每個(gè)緩存空間數(shù)據(jù)結(jié)構(gòu)為{idb， Ib， p， packet， k}。其中idb是中繼緩存b的標(biāo)識(shí);Ib是中繼緩存b感知興趣的數(shù)據(jù)結(jié)構(gòu)，Ib={I， ts， te， θ}，I是某一興趣組的興趣向量，如果sim（I，Am）≥δI，則節(jié)點(diǎn)將數(shù)據(jù)m和緩存b中的數(shù)據(jù)進(jìn)行RLNC后存儲(chǔ)在緩存b，ts，te和θ分別是I的訂閱開始時(shí)間、結(jié)束時(shí)間和興趣類型參數(shù);p是當(dāng)前節(jié)點(diǎn)與興趣為I的興趣組中節(jié)點(diǎn)相遇概率的最大值，為提高緩存效率，只有當(dāng)p>pth（pth是相遇概率閾值）時(shí)節(jié)點(diǎn)才為I初始化緩存，其中p按照文獻(xiàn)[22]中的公式計(jì)算，具有累加性、衰減性和傳遞性;packet是b中編碼數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，packet={idm， ml， gv，data};k決定緩存策略，依據(jù)θ設(shè)定。

當(dāng)θ=0時(shí)，I是臨時(shí)興趣，此時(shí)k=0，中繼節(jié)點(diǎn)將興趣訂閱期內(nèi)[ts，te]遇到的匹配興趣數(shù)據(jù)一起編碼，然后轉(zhuǎn)發(fā)給興趣節(jié)點(diǎn)。但是由于部分原始消息生成時(shí)間臨近興趣訂閱截止時(shí)間te，而可能導(dǎo)致興趣節(jié)點(diǎn)在te之前無法收集足夠多的線性無關(guān)編碼數(shù)據(jù)而解碼失敗，實(shí)際中設(shè)置常量d（系統(tǒng)依據(jù)消息分發(fā)時(shí)延上限值設(shè)定），中繼節(jié)點(diǎn)將數(shù)據(jù)生成時(shí)間t∈[ts，te-d]的數(shù)據(jù)一起編碼。

當(dāng)θ>0時(shí)，I是長(zhǎng)期興趣，此時(shí)則不適合將訂閱期內(nèi)的所有消息一起編碼。原因之一是這樣可能會(huì)因?yàn)榫幋a向量太大而導(dǎo)致解碼困難，極端情況下，如果是永久興趣，且不斷有新數(shù)據(jù)注入編碼包，則可能導(dǎo)致目的節(jié)點(diǎn)一直無法解碼;另外，第一個(gè)生成的消息可能也要等到最后一個(gè)編碼包到達(dá)后才能解碼，這就增加了早期興趣數(shù)據(jù)的分發(fā)時(shí)延。因此，針對(duì)長(zhǎng)期興趣采用如圖3所示的周期性編碼策略，此時(shí)θ表示編碼周期，由訂閱節(jié)點(diǎn)設(shè)定，k（k∈Z+）記錄當(dāng)前編碼周期數(shù)，初始值為[（t-ts）/θ]，t是當(dāng)前時(shí)間。在每個(gè)編碼周期中采取和臨時(shí)興趣相似的編碼方法，不同編碼周期內(nèi)對(duì)式（4）所示的時(shí)間段內(nèi)生成的數(shù)據(jù)編碼。周期性編碼后每一時(shí)間段的編碼向量不會(huì)太大，而且消息也能及時(shí)到達(dá)訂閱節(jié)點(diǎn)。

目的緩存用來存儲(chǔ)自己感興趣的編碼數(shù)據(jù)，當(dāng)收到足夠多的線性無關(guān)編碼數(shù)據(jù)后解碼得到原始興趣數(shù)據(jù)。但是由于中繼節(jié)點(diǎn)分布式編碼，目的節(jié)點(diǎn)收到的每個(gè)編碼包所包含的原始消息個(gè)數(shù)和順序很難一致，這為解碼帶來很大挑戰(zhàn)。為此，每個(gè)節(jié)點(diǎn)的目的緩存設(shè)置一個(gè)全局?jǐn)?shù)據(jù)結(jié)構(gòu)gml，作為統(tǒng)一的目的緩存數(shù)據(jù)的ml字段，以方便目的節(jié)點(diǎn)解碼。gml是原始消息id向量，初始值為空，按照編碼數(shù)據(jù)到來順序及其包含原始數(shù)據(jù)的順序動(dòng)態(tài)生成。由于存在全局ml字段，每個(gè)目的緩存的數(shù)據(jù)結(jié)構(gòu)為{idm，gv′，data}，其中idm 是編碼數(shù)據(jù)id，gv′是依據(jù)節(jié)點(diǎn)gml調(diào)整后的全局編碼向量，data是數(shù)據(jù)內(nèi)容。

2.3 算法設(shè)計(jì)

當(dāng)節(jié)點(diǎn)u和v相遇，依據(jù)它們是否在同一興趣組有兩種不同的數(shù)據(jù)交換策略。如果它們不在同一興趣組，則只交換Br中數(shù)據(jù);如果它們?cè)谕慌d趣組，則先交換Bd中數(shù)據(jù)，如交換后它們?nèi)匀惶幱谶B接狀態(tài)則再交換Br中數(shù)據(jù)，下面給出不同情況下的具體算法描述。

2.3.1 相遇節(jié)點(diǎn)興趣相異

如果相遇節(jié)點(diǎn)u和v不在同一興趣組，則它們交換各自Br中數(shù)據(jù)列表rl，rl={idm，gv，ml，Ib}，以下交互過程以節(jié)點(diǎn)u為例。

1）節(jié)點(diǎn)u收到v的rlv后，按2）中規(guī)則計(jì)算節(jié)點(diǎn)u緩存rlv中數(shù)據(jù)的效用，并生成中繼緩存數(shù)據(jù)列表rlv′后執(zhí)行3），其中rlv′中每個(gè)元素的結(jié)構(gòu)體是{idm，idb，Um}，idm是將要緩存數(shù)據(jù)m的id;idb是m的緩存位置;Um是節(jié)點(diǎn)u緩存m的效用。

2）緩存效用的計(jì)算規(guī)則是節(jié)點(diǎn)優(yōu)先緩存自己感興趣的數(shù)據(jù)，如果數(shù)據(jù)m是節(jié)點(diǎn)u的興趣數(shù)據(jù)，則效用為1，idb=-1;否則按式（5）計(jì)算緩存效用，如果存在和數(shù)據(jù)m屬性相匹配的興趣緩存b，則idb=b.id，否則說明節(jié)點(diǎn)u未初始化對(duì)數(shù)據(jù)m感興趣的緩存，idb=-2。在式（5）中，p（0≤p≤1）是節(jié)點(diǎn)u和數(shù)據(jù)m興趣組中節(jié)點(diǎn)的相遇概率，p越大則緩存m效用越高;K是依據(jù)滿足一次訂閱數(shù)據(jù)個(gè)數(shù)的上限值設(shè)定的常量，使效用值落在區(qū)間（0，1）中;j是緩存b中編碼消息m′已經(jīng)包含原始數(shù)據(jù)個(gè)數(shù)，j=len（m′.ml），為提高中繼節(jié)點(diǎn)的轉(zhuǎn)發(fā)能力，優(yōu)先滿足j較小的緩存;i是數(shù)據(jù)m為緩存b帶來的不重復(fù)的原始數(shù)據(jù)個(gè)數(shù)，i=len（m.ml-（m.ml∩m′.ml）），同等條件下i越大效用越高。Um=p×K-jK×iK。（5） ?3）節(jié)點(diǎn)u依據(jù)rl′v生成向節(jié)點(diǎn)v的中繼請(qǐng)求數(shù)據(jù)列表rl″u，發(fā)送給節(jié)點(diǎn)v，rl″u僅包含將要緩存數(shù)據(jù)的id，并按效用從高到低排序。

4）節(jié)點(diǎn)v收到節(jié)點(diǎn)u的rl″u后，按照rl″u依次轉(zhuǎn)發(fā)數(shù)據(jù)，直到數(shù)據(jù)轉(zhuǎn)發(fā)完畢或鏈路斷開。

5）節(jié)點(diǎn)u收到v發(fā)送的數(shù)據(jù)m，m={idm，ml，gv，data}，按照rl′v中idb定位緩存位置b：當(dāng)idb=-1時(shí)，則存儲(chǔ)m到節(jié)點(diǎn)u的目的緩存Bd中;當(dāng)idb=-2時(shí)，如果Br中有空閑緩存，則為其初始化緩存空間，否則采取如下丟棄策略，設(shè)p1是節(jié)點(diǎn)u和數(shù)據(jù)m的興趣組節(jié)點(diǎn)相遇概率，p2是節(jié)點(diǎn)u和已緩存數(shù)據(jù)的興趣組相遇概率最小值，如果p1≤p2，丟棄數(shù)據(jù)m，否則刪除p2對(duì)應(yīng)緩存的內(nèi)容并存儲(chǔ)數(shù)據(jù)m;當(dāng)idb≥0時(shí)，按照算法1編碼數(shù)據(jù)m。

6）數(shù)據(jù)交換完畢，節(jié)點(diǎn)u刪除臨時(shí)數(shù)據(jù)結(jié)構(gòu)rl′v和rl″u。

算法1：中繼節(jié)點(diǎn)編碼算法

當(dāng)節(jié)點(diǎn)u收到數(shù)據(jù)m并存儲(chǔ)到緩存b時(shí)，設(shè)m′為緩存b中的數(shù)據(jù)packet，y用來存儲(chǔ)新的編碼數(shù)據(jù)。

y.init（） ? ? ? ? ? ?//初始化y={id， ml=[]，gv=[]，data=″″}，id是新消息的標(biāo)識(shí)

y.data=a1*m′.data+a2*m.data ?//計(jì)算新編碼數(shù)據(jù)y，a1和a2是隨機(jī)生成的編碼系數(shù)

for（i=0; i

find= False

for （j=0; j

if m′.ml[i]==m.ml[j] then //如果m中存在和m′相同的原始數(shù)據(jù)

y.gv.append（a1*m′.gv[i]+a2*m.gv[j]） //合并全局編碼向量和相應(yīng)id

y.ml.append（m′.ml[i]）

del m.ml[j] ? //刪除已合并的原始數(shù)據(jù)id和全局編碼向量

del m.gv[j]

find=True

break

if not find then ?//如果m中不存在和m′相同的原始數(shù)據(jù)

y.ml.append（m′.ml[i]） ? //添加m′的全局編碼向量和對(duì)應(yīng)id到y(tǒng)中

y.gv.append（a1*m′.gv[i]）

u.gml.append（m′.ml[i]） ? //節(jié)點(diǎn)u的gml新增m′的id

for（j=0;j

y.ml.append（m.ml[j]）

y.gv.append（a2*m.gv[j]）

b.packet.write（y） ?//將y寫入緩存b的數(shù)據(jù)包字段

由于編碼分布式進(jìn)行，每個(gè)編碼消息所包含的原始消息及其編碼向量的順序是依據(jù)節(jié)點(diǎn)相遇過程隨機(jī)生成的，因此算法1的關(guān)鍵是合并同類項(xiàng)。如節(jié)點(diǎn)對(duì)原始數(shù)據(jù)x1和x2編碼，y1=a1x1+a2x2，則ml=[x1，x2]，gv=[a1，a2]，當(dāng)節(jié)點(diǎn)收到編碼包y2=b1x1+b2x2+b3x3時(shí)，編碼y1和y2得到編碼數(shù)據(jù)y= ay1+by2，則節(jié)點(diǎn)需要合并x1和x2對(duì)應(yīng)的編碼向量，y=（aa1+bb1）x1+（aa2+bb2）x2+bb3x3，即ml=[x1，x2，x3]，gv=[aa1+bb1，aa2+bb2，bb3]。

2.3.2 相遇節(jié)點(diǎn)興趣相同

如果相遇節(jié)點(diǎn)u和v在同一興趣組，則它們交換各自Bd中的數(shù)據(jù)列表dl，dl中元素僅是數(shù)據(jù)的id，以下過程以節(jié)點(diǎn)u為例。

1）節(jié)點(diǎn)u收到v的目的數(shù)據(jù)列表dlv后，去掉重復(fù)數(shù)據(jù)生成節(jié)點(diǎn)u向節(jié)點(diǎn)v的請(qǐng)求數(shù)據(jù)列表dl′u。

2）節(jié)點(diǎn)v收到節(jié)點(diǎn)u的dl′u后，按照dl′u依次轉(zhuǎn)發(fā)數(shù)據(jù)，直到數(shù)據(jù)轉(zhuǎn)發(fā)完畢或鏈路斷開。

3）節(jié)點(diǎn)u收到數(shù)據(jù)m后按照算法2處理數(shù)據(jù)，m數(shù)據(jù)結(jié)構(gòu)為{idm， gv，ml，data}，其中ml是發(fā)送節(jié)點(diǎn)v的gml，gv是和gml對(duì)應(yīng)的全局編碼向量。

4）在完成Bd數(shù)據(jù)交換后，如果節(jié)點(diǎn)u和v仍處于鏈接狀態(tài)，則按照2.3.1流程交換Br中數(shù)據(jù)。

算法2：節(jié)點(diǎn)u收到興趣數(shù)據(jù)m時(shí)的處理流程

y用來存儲(chǔ)接收的消息， gml為節(jié)點(diǎn)u的全局接收消息列表gml。

y.init（m，len（u.gml）） //初始化y， n=len（u.gml）， y.id=m.id，y.data=y.data，y.gv=[0 0 … 0]n

for（i=0;i

if m.gv[i]==0 then ?//忽略編碼向量為0的元素

continue

find=False

k=0

for（j=0;j

if m.ml[i]==u.gml[j] then ?//如果節(jié)點(diǎn)u接收過原始數(shù)據(jù)m.ml[i]

k=j ? //k記錄原始數(shù)據(jù)m.ml[i]的id在節(jié)點(diǎn)u的gml中的位置

find=True

break

if not find then ?//如果節(jié)點(diǎn)u沒有接收過原始數(shù)據(jù)m.ml[i]

u.gml.append（m.ml[i]） ?//添加m.ml[i]到gml

y.gv.expend（1，0） ? //擴(kuò)充gv，在尾部增加一個(gè)值為0的元素

k=len（u.gml） ?//k記錄原始數(shù)據(jù)m.ml[i]的id在節(jié)點(diǎn)u的gml中的位置

y.gv[k]=m.gv[i] ?//按照m.ml[i]在節(jié)點(diǎn)u的gml的位置設(shè)置對(duì)應(yīng)編碼向量

[3] SOBIN C C， RAYCHOUDHURY V， MARFIA G， et al. A survey of routing and data dissemination in delay tolerant networks[J]. Journal of Network and Computer Applications， 2016， 67： 128-146.

[4] YU Sui， ZHANG Licheng， LI Lixia， et al. An efficient interest-aware data dissemination approach in opportunistic networks[J]. Procedia Computer Science， 2019， 147： 394-399.

[5] HAN S， LEE K， CHOI H H， et al. BiPAD： Binomial point process based energy-aware data dissemination in opportunistic D2D networks[J]. Energies， 2018， 11（8）： 2073.

[6] LIU Yang， WU Hongyi， XIA Yuanqing， et al. Optimal online data dissemination for resource constrained mobile opportunistic networks[J]. IEEE Transactions on Vehicular Technology， 2017， 66（6）：5301-5315.

[7] CHEN Daoliang， LIU Linfeng， WU Jiagao， et al. A region type-based data dissemination method for mobile opportunistic networks[C]//2018 IEEE 18th International Conference on Communication Technology （ICCT）. Chongqing： IEEE， 2018： 297-301.

[8] CIOBANU R I， MARIN R C， DOBRE C， et al. Interest-awareness in data dissemination for opportunistic networks[J]. Ad Hoc Networks， 2015， 25： 330-345.

[9] AHLSWEDE R， CAI N， LI S Y R， et al. Network information flow[J]. IEEE Transactions on Information Theory， 2000， 46（4）： 1204-1216.

[10] 胡旭飛，許云峰.基于骨干度與網(wǎng)絡(luò)編碼的鏈路預(yù)測(cè)模型研究[J].河北工業(yè)科技， 2019，36（5）：310-313.

HU Xufei， XU Yunfeng. Research on link prediction model based on backbone degree and network coding[J]. Hebei Journal of Industrial Science and Technology， 2019，36（5）：310-313.

[11] 王練， 任治豪， 何利， 等.中繼協(xié)作無線網(wǎng)絡(luò)中不完美反饋下基于網(wǎng)絡(luò)編碼的重傳方案[J].電子學(xué)報(bào)，2019，47（4）：818-825.

WANG Lian， REN Zhihao， HE Li， et al. Retransmission scheme based on network coding for relay-assisted wireless network with imperfect feedback[J]. Acta Electronica Sinica， 2019， 47（4）：818-825.

[12] HO T， MEDARD M， KOETTER R， et al. A random linear network coding approach to multicast[J]. IEEE Transactions on Information Theory， 2006， 52（10）： 4413-4430.

[13] 姚建盛，馬春光，袁琪， 等.基于流內(nèi)與流間網(wǎng)絡(luò)編碼的DTMSN廣播傳輸機(jī)制[J].北京郵電大學(xué)學(xué)報(bào)，2017，40（5）：18-23.

YAO Jiansheng， MA Chunguang， YUAN Qi， et al. A broadcast transmission scheme for DTMSN based on intra-flow and inter-flow network coding[J]. Journal of Beijing University of Posts and Telecommunications， 2017， 40（5）：18-23.

[14] RHAIEM O B， CHAARI L. Information transmission based on network coding over wireless networks： A survey [J]. Telecommunication Systems， 2017，65： 551-565.

[15] ZENG Deze， GUO Song， HU Jiankun. Reliable bulk-data dissemination in delay tolerant networks[J]. IEEE Transactions on Parallel and Distributed Systems， 2014， 25（8）：2180-2189.

[16] YANG Qin， YANG Weilong， PENG Lei. Inter-session network coding with clustering routing in wireless delay tolerant networks[C]//2019 20th Asia-Pacific Network Operations and Management Symposium. Matsue： IEEE， 2019： 1-4.

[17] KATTI S， RAHUL H， HU W J， et al. XORs in the air： Practical wireless network coding[J]. IEEE/ACM Transactions on Networking， 2008， 16（3）： 497-510.

[18] KAFAIE S， CHEN Y Z， DOBRE O A， et al. Joint inter-flow network coding and opportunistic routing in multi-hop wireless mesh networks： A comprehensive survey[J]. IEEE Communications Surveys & Tutorials， 2018， 20（2）：1014-1035.

[19] YAO Jiansheng， MA Chunguang， WU Peng， et al. An opportunistic network coding routing for opportunistic networks[J]. International Journal of Parallel Programming， 2017， 45：157-171.

[20] VAHDAT A， BECKER D. Epidemic Routing for Partially Connected Ad Hoc Networks[R]. Durham： Duke University， 2000.

[21] SPYROPOULOS T， PSOUNIS K， RAGHAVENDRA C. Efficient routing in intermittently connected mobile networks： The multiple-copy case[J]. IEEE/ACM Transactions on Networking， 2008， 16（1）： 77-90.

[22] LINDGREN A， DORIA A， SCHELN O. Probabilistic routing in intermittently connected networks[C]// SAPIR：International Workshop on Service Assurance with Partial and Intermittent Resources. Fortaleza：[s.n.]，2004： 239-254.