興趣和編碼感知機會網(wǎng)絡(luò)多源多宿數(shù)據(jù)分發(fā)

姚建盛 劉艷玲

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

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

中圖分類號：TP393 ? 文獻標識碼：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

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

現(xiàn)有機會網(wǎng)絡(luò)數(shù)據(jù)分發(fā)主要基于單源多宿SSMD （single-source and multi-destination）數(shù)據(jù)分發(fā)模型[4，6-7]，即1個數(shù)據(jù)可以存在多個節(jié)點興趣，但1個節(jié)點興趣只有1個匹配數(shù)據(jù)。然而在一些機會網(wǎng)絡(luò)數(shù)據(jù)分發(fā)場景中，存在多源多宿（multi-source and multi-destination，MSMD）數(shù)據(jù)分發(fā)情況。例如，針對同一場交通事故或同一區(qū)域的環(huán)境狀態(tài)，由于不同節(jié)點觀察角度或位置不同導致其反饋的信息可能不一致;另外關(guān)注同一事件的多個興趣節(jié)點也往往需要從不同角度了解該事件。于是出現(xiàn)一種將多個相似或相關(guān)的數(shù)據(jù)分發(fā)給一組興趣相似或相同的節(jié)點情況，為此定義了一種基于模糊匹配的MSMD機會網(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ù)[3]。然而MSMD數(shù)據(jù)分發(fā)卻不能直接應(yīng)用該技術(shù)，因為多副本多路徑傳輸會進一步增加網(wǎng)絡(luò)流量，可能會導致中繼節(jié)點因緩存溢出或帶寬不足而降低數(shù)據(jù)分發(fā)性能，因此提高MSMD數(shù)據(jù)分發(fā)性能的關(guān)鍵是壓縮數(shù)據(jù)流量以緩解對中繼節(jié)點緩存和帶寬的需求。

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

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

機會網(wǎng)絡(luò)MSMD數(shù)據(jù)分發(fā)系統(tǒng)就是以機會網(wǎng)絡(luò)為通信基礎(chǔ)，將系統(tǒng)發(fā)布的多個相似數(shù)據(jù)從多個源節(jié)點轉(zhuǎn)發(fā)給多個興趣相似的目的節(jié)點，可用二元組（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é)點生成，如照片、本地交通狀況和環(huán)境信息等。為簡化系統(tǒng)設(shè)計，假定相似數(shù)據(jù)大小一致。Gt是機會網(wǎng)絡(luò)動態(tài)鏈接圖，Gt=（Vt，Et），其中Vt和Et分別是t時刻移動節(jié)點集合和節(jié)點間連接鏈路集合，系統(tǒng)假設(shè)節(jié)點集合在系統(tǒng)運行過程中保持不變恒為V，由于節(jié)點移動、無線鏈路不穩(wěn)定等原因，節(jié)點間鏈路Et隨時間變化而改變。為描述MSMD數(shù)據(jù)分發(fā)模型，給出如下相關(guān)概念。

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

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

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

定義4 興趣度：節(jié)點v對數(shù)據(jù)m的興趣度記為Iv→m，是節(jié)點v的興趣向量Iv和數(shù)據(jù)m的屬性向量Am的相似度，即Iv→m=sim（Iv，Am）。當相似度Iv→m≥δI （δI是興趣度閾值）時，稱節(jié)點v對數(shù)據(jù)m感興趣。這里的相似向量不僅夾角比較小，而且長度也相近，因此相似度公式為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é)點u和v的興趣相似度sim（Iu，Iv）≥δn（δn是興趣相似度閾值），則稱節(jié)點u和v在同一興趣組，為簡化系統(tǒng)設(shè)計，假定興趣組內(nèi)節(jié)點興趣相同。

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

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

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

2.1 基本思想

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

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

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

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

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

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

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

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

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

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

2.3 算法設(shè)計

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

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

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

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

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

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

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

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

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

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

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

y.data=a1*m′.data+a2*m.data ?//計算新編碼數(shù)據(jù)y，a1和a2是隨機生成的編碼系數(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′的全局編碼向量和對應(yīng)id到y(tǒng)中

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

u.gml.append（m′.ml[i]） ? //節(jié)點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ù)節(jié)點相遇過程隨機生成的，因此算法1的關(guān)鍵是合并同類項。如節(jié)點對原始數(shù)據(jù)x1和x2編碼，y1=a1x1+a2x2，則ml=[x1，x2]，gv=[a1，a2]，當節(jié)點收到編碼包y2=b1x1+b2x2+b3x3時，編碼y1和y2得到編碼數(shù)據(jù)y= ay1+by2，則節(jié)點需要合并x1和x2對應(yīng)的編碼向量，y=（aa1+bb1）x1+（aa2+bb2）x2+bb3x3，即ml=[x1，x2，x3]，gv=[aa1+bb1，aa2+bb2，bb3]。

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

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

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

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

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

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

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

y用來存儲接收的消息， gml為節(jié)點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é)點u接收過原始數(shù)據(jù)m.ml[i]

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

find=True

break

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

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

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

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

y.gv[k]=m.gv[i] ?//按照m.ml[i]在節(jié)點u的gml的位置設(shè)置對應(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ò)編碼的鏈路預測模型研究[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].電子學報，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].北京郵電大學學報，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.