兴趣和编码感知机会网络多源多宿数据分发

姚建盛 刘艳玲

摘 要：针对当前机会网络数据分发协议面向的主要是单源多宿数据分发模型的问题，提出了一种多源多宿机会网络数据分发模型，设计了一种兴趣和编码感知（ICA，interest-and coding-aware）的机会网络数据分发协议。首先，由中继节点将满足同一兴趣的不同数据源进行流间随机线性网络编码后转发;其次，拥有相同兴趣的节点彼此交换兴趣编码数据，当节点收到足够多的满足同一兴趣的线性无关编码包时，解码得到多个感兴趣的原始数据;最后，对多源多宿机会网络数据分发进行了ONE仿真。结果表明，和基于ER的多源多宿数据分发相比，ICA能通过较小的缓存、网络带宽和网络负载获得较低的分发时延。研究结果可为机会网络中的网络数据分发机制提供一种可行、高效的解决方案。

关键词：计算机网络;机会网络;多源多宿数据分发;流间随机线性网络编码;兴趣

中图分类号：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

机会网络[1-2]能实现不存在完整通信链路的源节点和目的节点间的通信，对IoT和普适计算有重要意義。在机会网络的许多实际应用中，如广告发布、新闻传播和环境通告等，数据没有明确的目的地址，无法使用路由技术，而是通过数据分发实现这种以内容为中心的网络通信[3-5]。数据分发在时间、空间和控制流上完全解耦了数据生产者和消费者，更加适合间歇性连接的机会网络，成为机会网络当前的一个研究热点。

现有机会网络数据分发主要基于单源多宿SSMD （single-source and multi-destination）数据分发模型[4，6-7]，即1个数据可以存在多个节点兴趣，但1个节点兴趣只有1个匹配数据。然而在一些机会网络数据分发场景中，存在多源多宿（multi-source and multi-destination，MSMD）数据分发情况。例如，针对同一场交通事故或同一区域的环境状态，由于不同节点观察角度或位置不同导致其反馈的信息可能不一致;另外关注同一事件的多个兴趣节点也往往需要从不同角度了解该事件。于是出现一种将多个相似或相关的数据分发给一组兴趣相似或相同的节点情况，为此定义了一种基于模糊匹配的MSMD机会网络数据分发模型。

MSMD数据分发在同等条件下一般比SSMD数据分发产生更大的数据流量，因而面临更大挑战。比如在SSMD数据分发中，为提高投递率和减小时延常采用多副本多路径传输技术[3]。然而MSMD数据分发却不能直接应用该技术，因为多副本多路径传输会进一步增加网络流量，可能会导致中继节点因缓存溢出或带宽不足而降低数据分发性能，因此提高MSMD数据分发性能的关键是压缩数据流量以缓解对中继节点缓存和带宽的需求。

当前压缩网络流量的一种有效方法是网络编码技术[9-10]，该技术允许网络中间节点编码，推翻了独立比特不能再被压缩的经典理论，有效提高了网络吞吐量，在无线网络通信中已有大量研究[11]。SSMD机会网络数据分发主要基于随机线性网络编码（RLNC， random liner network coding）[12]，并且是作为流内网络编码使用[13]，文献[14]认为贪婪复制阻碍流间网络编码获益，而事实上流间网络编码更适合压缩数据流量，提高网络吞吐量[15-16]。典型的流間网络编码是机会网络编码（ONC， opportunistic network coding）[17]，然而在节点稀疏情况下ONC的编码机会很小而且并不适合MSMD数据分发场景[18-19]。为此本文将RLNC当作流间网络编码使用，提出一种兴趣和编码感知（ICA， interest- and coding-aware）的机会网络MSMD数据分发方法。仿真实验证明，和基于ER[20]的MSMD数据分发相比，ICA通过较小的缓存、网络带宽和网络负载能获得较低的分发时延。

1 MSMD数据分发模型

机会网络MSMD数据分发系统就是以机会网络为通信基础，将系统发布的多个相似数据从多个源节点转发给多个兴趣相似的目的节点，可用二元组（M，Gt）表示。M是系统发布数据（不包括控制消息等）的集合，M={M1，M2，…，Mn}，其中Mi（i=1，2，…，n）是一组相似或相关数据的集合。数据可能来自于Internet，如天气信息、股票信息和新闻等，也可能由节点生成，如照片、本地交通状况和环境信息等。为简化系统设计，假定相似数据大小一致。Gt是机会网络动态链接图，Gt=（Vt，Et），其中Vt和Et分别是t时刻移动节点集合和节点间连接链路集合，系统假设节点集合在系统运行过程中保持不变恒为V，由于节点移动、无线链路不稳定等原因，节点间链路Et随时间变化而改变。为描述MSMD数据分发模型，给出如下相关概念。

定义1 频道：频道是系统预定义的主题，记为C，频道的集合记为Ω，即Ω={C1，C2，…，Cs}，s是系统预定义频道数。

定义2 数据属性： 数据属性是由数据发布者标记的数据和预定义频道的相关程度。数据m的属性记为Am，Am=[p1 p2  … ps]，其中pi（0≤pi≤1）是概率值，表示数据m和频道Ci的相关程度。

定义3 节点兴趣： 节点兴趣是节点对系统预定义频道感兴趣程度。节点v的兴趣记为Iv，Iv=[p1 p2 … ps]，其中pi（0≤pi≤1）是概率值，描述节点v对频道Ci的兴趣程度。

定义4 兴趣度：节点v对数据m的兴趣度记为Iv→m，是节点v的兴趣向量Iv和数据m的属性向量Am的相似度，即Iv→m=sim（Iv，Am）。当相似度Iv→m≥δI （δI是兴趣度阈值）时，称节点v对数据m感兴趣。这里的相似向量不仅夹角比较小，而且长度也相近，因此相似度公式为sim（α，β）=∑（αi-）·（βi-）∑（αi-）2·∑（βi-）2 。（1）  定义5 相似数据：如果数据i和j的属性相似度sim（Ai，Aj）≥δm（δm是数据属性相似度阈值），则称数据i和j为相似数据。

定义6 兴趣组：如果节点u和v的兴趣相似度sim（Iu，Iv）≥δn（δn是兴趣相似度阈值），则称节点u和v在同一兴趣组，为简化系统设计，假定兴趣组内节点兴趣相同。

针对一组相似数据集合Mi，机会网络MSMD数据分发模型如图1所示。节点集合V=VP∪VS∪VR，其中VP={P1，P2，…，Pi}是Mi的发布节点集合，发布节点是数据的生产者，不知道谁需要数据，只是将其注入到网络;VS={S1，S2，…，Sj}是Mi的订阅节点集合，即兴趣组，订阅节点是数据的消费者，不知道数据在哪，只是向网络表达自己的订阅兴趣;VR={R1，R2，…，Rk}是Mi的中继节点集合，负责将数据从生产者转发到消费者。订阅节点和发布节点也可参与数据转发，1个节点可以同时是不同相似数据集合的生产者、消费者和中继者。当|Mi|和|VP|为1时，即只有1个相似数据和1个发布节点，MSMD数据分发变成SSMD数据分发。

2 兴趣和编码感知MSMD数据分发

首先给出机会网络环境下兴趣和编码感知MSMD数据分发的基本思想和面临的问题，然后设计相关数据结构和编码、解码算法。

2.1 基本思想

SSMD数据分发一般通过多副本多路径技术提高数据分发性能，但为了减少网络负载，一般采用限制副本数，假设有n个订阅节点，以Binary Spray[21]方式分发1个数据，副本限制数为C（C≥n），则分发路径是如图2 a）所示的以发布节点为根的二叉树，最终网络中存在C个副本，当所有订阅节点都得到1个副本时完成数据分发。而对于有k个相似数据的MSMD数据分发，如果采用类似方法，则需要k棵与图2 a）相似的二叉树，最终网络中存在C×k个数据，每个订阅节点需要得到k个不同的数据副本。但实际上k个二叉树是有交集的，如图2 b）所示，数据m1和数据mk在分发过程中的某一时段同时经过节点v，如果节点v将2个不同数据流编码成1个数据后再转发，则压缩了数据流量，节省了网络带宽和存储空间，避免了因资源不足而导致数据分发的性能降低。ICA的基本思想就是将来自不同数据流的相似数据看作同一个数据流的不同片段进行RLNC，然后在网络中转发，当目的节点收到k个线性无关RLNC包时，解码得到k个相似的原始兴趣数据，ICA的数据分发路径如图2 c）所示是一个网状结构。

2.2 数据结构

为实现兴趣和编码感知MSMD数据分发，下面给出数据、兴趣的格式和节点缓存的数据结构。

系统发布数据有两类：原始数据和编码数据。为统一编码操作，设置一致的数据包格式，部分数据包头字段为{idm，ml，gv，Am，data}。其中idm是数据m的标识。ml是编码数据中所包含原始数据的id向量。gv是和ml对应的全局编码系数向量，如果是原始数据，则ml=[idm]，gv=[1]。Am是数据m的属性向量，m是原始数据由源节点初始化Am;如果m是编码数据，则由缓存该编码数据的节点重新设置Am。data是数据内容字段，为简化算法设计，假定数据字段长度相同，但在实际环境中规定数据最大长度，如果数据长度不够，则用相同bit位填充。

本文考虑两类节点兴趣：临时兴趣和长期兴趣。如对某路段当前交通状态的查询兴趣是临时兴趣，而对某一股票、天气或新闻的订阅可能是长期兴趣且具有一定周期性。节点兴趣数据结构为{idv，Iv，ts，te，θ}，其中idv是订阅节点v的id;Iv是节点v的兴趣向量;ts和te分别是兴趣订阅的开始时间和结束时间;θ代表节点兴趣类型，当θ=0时则兴趣是临时兴趣，当θ>0时则兴趣是长期兴趣，此时θ表示编码周期。节点一旦生成，興趣便通过gossip方式向网络表达。

节点缓存分成两部分：中继缓存Br和目的缓存Bd，前者用来帮助其他节点缓存数据，后者用来缓存自己的兴趣数据。

中继缓存是兴趣感知缓存，每个缓存空间数据结构为{idb， Ib， p， packet， k}。其中idb是中继缓存b的标识;Ib是中继缓存b感知兴趣的数据结构，Ib={I， ts， te， θ}，I是某一兴趣组的兴趣向量，如果sim（I，Am）≥δI，则节点将数据m和缓存b中的数据进行RLNC后存储在缓存b，ts，te和θ分别是I的订阅开始时间、结束时间和兴趣类型参数;p是当前节点与兴趣为I的兴趣组中节点相遇概率的最大值，为提高缓存效率，只有当p>pth（pth是相遇概率阈值）时节点才为I初始化缓存，其中p按照文献[22]中的公式计算，具有累加性、衰减性和传递性;packet是b中编码数据的数据结构，packet={idm， ml， gv，data};k决定缓存策略，依据θ设定。

当θ=0时，I是临时兴趣，此时k=0，中继节点将兴趣订阅期内[ts，te]遇到的匹配兴趣数据一起编码，然后转发给兴趣节点。但是由于部分原始消息生成时间临近兴趣订阅截止时间te，而可能导致兴趣节点在te之前无法收集足够多的线性无关编码数据而解码失败，实际中设置常量d（系统依据消息分发时延上限值设定），中继节点将数据生成时间t∈[ts，te-d]的数据一起编码。

当θ>0时，I是长期兴趣，此时则不适合将订阅期内的所有消息一起编码。原因之一是这样可能会因为编码向量太大而导致解码困难，极端情况下，如果是永久兴趣，且不断有新数据注入编码包，则可能导致目的节点一直无法解码;另外，第一个生成的消息可能也要等到最后一个编码包到达后才能解码，这就增加了早期兴趣数据的分发时延。因此，针对长期兴趣采用如图3所示的周期性编码策略，此时θ表示编码周期，由订阅节点设定，k（k∈Z+）记录当前编码周期数，初始值为[（t-ts）/θ]，t是当前时间。在每个编码周期中采取和临时兴趣相似的编码方法，不同编码周期内对式（4）所示的时间段内生成的数据编码。周期性编码后每一时间段的编码向量不会太大，而且消息也能及时到达订阅节点。

目的缓存用来存储自己感兴趣的编码数据，当收到足够多的线性无关编码数据后解码得到原始兴趣数据。但是由于中继节点分布式编码，目的节点收到的每个编码包所包含的原始消息个数和顺序很难一致，这为解码带来很大挑战。为此，每个节点的目的缓存设置一个全局数据结构gml，作为统一的目的缓存数据的ml字段，以方便目的节点解码。gml是原始消息id向量，初始值为空，按照编码数据到来顺序及其包含原始数据的顺序动态生成。由于存在全局ml字段，每个目的缓存的数据结构为{idm，gv′，data}，其中idm 是编码数据id，gv′是依据节点gml调整后的全局编码向量，data是数据内容。

2.3 算法设计

当节点u和v相遇，依据它们是否在同一兴趣组有两种不同的数据交换策略。如果它们不在同一兴趣组，则只交换Br中数据;如果它们在同一兴趣组，则先交换Bd中数据，如交换后它们仍然处于连接状态则再交换Br中数据，下面给出不同情况下的具体算法描述。

2.3.1 相遇节点兴趣相异

如果相遇节点u和v不在同一兴趣组，则它们交换各自Br中数据列表rl，rl={idm，gv，ml，Ib}，以下交互过程以节点u为例。

1）节点u收到v的rlv后，按2）中规则计算节点u缓存rlv中数据的效用，并生成中继缓存数据列表rlv′后执行3），其中rlv′中每个元素的结构体是{idm，idb，Um}，idm是将要缓存数据m的id;idb是m的缓存位置;Um是节点u缓存m的效用。

2）缓存效用的计算规则是节点优先缓存自己感兴趣的数据，如果数据m是节点u的兴趣数据，则效用为1，idb=-1;否则按式（5）计算缓存效用，如果存在和数据m属性相匹配的兴趣缓存b，则idb=b.id，否则说明节点u未初始化对数据m感兴趣的缓存，idb=-2。在式（5）中，p（0≤p≤1）是节点u和数据m兴趣组中节点的相遇概率，p越大则缓存m效用越高;K是依据满足一次订阅数据个数的上限值设定的常量，使效用值落在区间（0，1）中;j是缓存b中编码消息m′已经包含原始数据个数，j=len（m′.ml），为提高中继节点的转发能力，优先满足j较小的缓存;i是数据m为缓存b带来的不重复的原始数据个数，i=len（m.ml-（m.ml∩m′.ml）），同等条件下i越大效用越高。Um=p×K-jK×iK。（5）  3）节点u依据rl′v生成向节点v的中继请求数据列表rl″u，发送给节点v，rl″u仅包含将要缓存数据的id，并按效用从高到低排序。

4）节点v收到节点u的rl″u后，按照rl″u依次转发数据，直到数据转发完毕或链路断开。

5）节点u收到v发送的数据m，m={idm，ml，gv，data}，按照rl′v中idb定位缓存位置b：当idb=-1时，则存储m到节点u的目的缓存Bd中;当idb=-2时，如果Br中有空闲缓存，则为其初始化缓存空间，否则采取如下丢弃策略，设p1是节点u和数据m的兴趣组节点相遇概率，p2是节点u和已缓存数据的兴趣组相遇概率最小值，如果p1≤p2，丢弃数据m，否则删除p2对应缓存的内容并存储数据m;当idb≥0时，按照算法1编码数据m。

6）数据交换完毕，节点u删除临时数据结构rl′v和rl″u。

算法1：中继节点编码算法

当节点u收到数据m并存储到缓存b时，设m′为缓存b中的数据packet，y用来存储新的编码数据。

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

y.data=a1*m′.data+a2*m.data  //计算新编码数据y，a1和a2是随机生成的编码系数

for（i=0; i

find= False

for （j=0; j

if m′.ml[i]==m.ml[j] then //如果m中存在和m′相同的原始数据

y.gv.append（a1*m′.gv[i]+a2*m.gv[j]） //合并全局编码向量和相应id

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

del m.ml[j]   //删除已合并的原始数据id和全局编码向量

del m.gv[j]

find=True

break

if not find then  //如果m中不存在和m′相同的原始数据

y.ml.append（m′.ml[i]）   //添加m′的全局编码向量和对应id到y中

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

u.gml.append（m′.ml[i]）   //节点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的数据包字段

由于编码分布式进行，每个编码消息所包含的原始消息及其编码向量的顺序是依据节点相遇过程随机生成的，因此算法1的关键是合并同類项。如节点对原始数据x1和x2编码，y1=a1x1+a2x2，则ml=[x1，x2]，gv=[a1，a2]，当节点收到编码包y2=b1x1+b2x2+b3x3时，编码y1和y2得到编码数据y= ay1+by2，则节点需要合并x1和x2对应的编码向量，y=（aa1+bb1）x1+（aa2+bb2）x2+bb3x3，即ml=[x1，x2，x3]，gv=[aa1+bb1，aa2+bb2，bb3]。

2.3.2 相遇节点兴趣相同

如果相遇节点u和v在同一兴趣组，则它们交换各自Bd中的数据列表dl，dl中元素仅是数据的id，以下过程以节点u为例。

1）节点u收到v的目的数据列表dlv后，去掉重复数据生成节点u向节点v的请求数据列表dl′u。

2）节点v收到节点u的dl′u后，按照dl′u依次转发数据，直到数据转发完毕或链路断开。

3）节点u收到数据m后按照算法2处理数据，m数据结构为{idm， gv，ml，data}，其中ml是发送节点v的gml，gv是和gml对应的全局编码向量。

4）在完成Bd数据交换后，如果节点u和v仍处于链接状态，则按照2.3.1流程交换Br中数据。

算法2：节点u收到兴趣数据m时的处理流程

y用来存储接收的消息， gml为节点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  //如果节点u接收过原始数据m.ml[i]

k=j   //k记录原始数据m.ml[i]的id在节点u的gml中的位置

find=True

break

if not find then  //如果节点u没有接收过原始数据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记录原始数据m.ml[i]的id在节点u的gml中的位置

y.gv[k]=m.gv[i]  //按照m.ml[i]在节点u的gml的位置设置对应编码向量

[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] 胡旭飛，许云峰.基于骨干度与网络编码的链路预测模型研究[J].河北工业科技， 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] 王练， 任治豪， 何利， 等.中继协作无线网络中不完美反馈下基于网络编码的重传方案[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] 姚建盛，马春光，袁琪， 等.基于流内与流间网络编码的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.