基于问询机制的支配集网络编码算法

黄庆东, 梁　帅, 刘伟刚, 李　莎

(西安邮电大学 通信与信息工程学院， 陕西 西安 710121)

网络编码技术应用于无线传感网络，能够降低网络能耗、改善负载均衡，通过给中间节点赋予数据编码能力，使中间节点接收到数据后，将多条数据流融合编码后一次性发送，减少数据流发送次数[1]。传统的路由技术结合网络编码，能够在一定程度上改善网络性能，但是其编码需要满足一定的编码条件，自然存在的编码机会较少，导致网络编码利用率不高，限制了网络编码的性能增益[2]。如何有效地增加编码机会来提升网络性能，是当前研究的热点。

COPE(opportunistic overhearing and encoded broadcast)编码机制[3]，利用无线设备的侦听机制来判断编码机会，但消耗较多的节点存储空间[4]。编码感知路由(distributed coding aware routing,DCAR)[5]协议将路由发现和机会编码结合，编码范围扩展到多跳，但只能处理两条数据流，且会出现错误编码，带来不必要的重传[6]。文献[7]中提出了利用自适应时延来等待匹配编码分组的到达，但这种等待有时具有一定的盲目性，影响执行效率[8]。

连通支配集是一种常用来构建虚拟骨干网的算法，其使得网络中任意两点的通信总可以通过连通支配集来进行，在减少路由开销，降低能耗，提高全网广播效率方面具有优良特性[9]。文献[10]提出了支配集网络编码算法(network coding over connected dominating set, NCDS)，利用支配集使数据流汇聚的特点来弥补普通网络中编码机会缺失的问题，但编码只在发送节点自身发送队列进行，未考虑邻居节点发送队列状态，且算法未考虑单次编码数据流个数问题。直观上讲，单次编码的数据流个数越多，可获得的频带利用率和吞吐量更高[11]。本文拟在NCDS算法基础上，提出一种基于问询的支配集网络编码算法，在数据发送之前，询问邻居节点的信息状态，使得邻居节点发送队列中满足编码条件的数据包汇聚至发送节点处，编码后一并发出，进而增加编码机会和提升单次编码数据流个数。

1　支配集网络编码

1.1　网络编码原理

网络编码的基本原理，见图1。

(a) 传统的存储转发模式

(b) 网络编码方式

图1中各个节点间通过有向链路来连接，可用有向图来描述该网络，其中实线表示实际链路，虚线表示侦听链路。信源节点S1、S2分别通过中间节点R向信宿节点D1、D2发送数据包(或者看作是比特流)P1、P2，各节点之间满足

(1)

其中，N(r)、N(D1)、N(D2)分别代表节点R、D1、D2的邻居节点集。

图1(a)按照传统的存储转发模式实现传输，R在接收到S1、S2发送来的P1、P2数据包后，需分别花费2个时隙将P1、P2分别转发给D1、D2，即完成一次完整的信息的传输将需要花费4个时隙。在网络编码中，如图1(b)所示，R节点接收到P1、P2后，对P1、P2做模二和运算得到P1⊕P2，R将P1⊕P2一并发出。由于信宿节点D2已经通过S1→D2链路获得P1，因此D2可以通过P1和P1⊕P2的模二和得到P2，同理D1可以通过P2和P1⊕P2得到P1。这样整个传输过程在3个时隙完成，节约1个时隙[8]。

如果在某一节点处能够执行编码的概率越大或次数越多，该节点处具有更多的编码机会。每一个节点会维护一个数据包缓存队列，该缓存队列把节点接收和发送的数据包缓存一定时间，当一个节点接收一个由k个数据包编码组成的编码包，节点会通过本地的缓存队列检查其是否拥有编码包中的第k-1个数据包，如果有，则可以通过已有的这k-1个数据包把所需的数据包解析出来[3]。

1.2　NCDS算法

NCDS算法将网络编码应用于由连通支配集生成的虚拟骨干网中，以解决在正常网络中编码机会缺失问题。支配集中的网络编码模型，见图2。

图2　支配集中的网络编码模型

图2为16个节点的网络，C,F,I,K,J是由连通支配集算法产生的支配集节点，C↔F↔I↔K↔J构成虚拟骨干路径，支配集节点起到构建整个网络路由通道的作用，其汇聚数据，增加数据的流通量，进而增大编码机会[10]。

NCDS算法由两步组成，第一步构建连通支配集，第二步在连通支配集中应用网络编码。在虚拟骨干网构建完成后，当节点J发送信息时，对自己的发送队列执行机会编码，将满足编码条件的数据尽可能多地编码后发送，数据包会被J的所有邻居节点收到，当节点K接收到来自J的数据包后，首先对收到的信息根据是否为编码包进行解码操作选择，然后将待转发的数据存入发送队列。利用支配集网络，一方面可以降低网络节点间不必要的信息交互，提高网络效率，节约频带资源；另一方面为网络编码提供更多的编码机会，提升网络效率[12]。

2　基于问询的支配集编码

为了进一步增加编码机会，在NCDS算法基础上，提出一种基于问询的支配集编码算法。该算法通过修改802.11MAC协议控制信息帧格式，使其携带待发送数据信息，来问询邻居节点是否有能够一起编码的数据，如果有，则先接收邻居节点的可编码数据，然后再编码发送；如果没有，则直接编码发送。

无线网络环境中，信息交互的信道为公共的，有效、有序的信息传输需要媒体接入协议(multiple access control protocol, MAC)，载波侦听多路访问/冲突避免(carrier sense multiple access with collision detection, CSMA/CA)协议一个简单的信息交互过程，见图3。

图3　CSMA/CA MAC协议信息交互示意

图3中，发送节点A首先发送请求发送帧(request to send, RTS)来请求发送，接收节点B收到RTS帧后对A回应允许发送帧(clear to send, CTS)允许发送，然后A向B发送数据信息，在B接收成功后对A回应确认帧(acknowledge, ACK)[13]。

2.1　RTSCP帧格式

为有效地利用信息交互过程中的控制帧，设计了编码包请求发送帧(request to send coding packet, RTSCP)，有可编码数据帧(have coding packet, HCP)和无可编码数据帧(no coding packet, NCP)，用于问询过程中节点间的信息交互。802.11协议中RTS格式[14]，见图4。

图4　802.11协议RTS帧格式

图4中，请求发送帧RTS包含有帧控制域、帧交换所需时间长度、两个地址域和帧校验域。其目的为让邻居节点在信息发送期间进行避让，避免信息碰撞。RTSCP帧为节点发起问询的控制帧，格式如图5所示。

图5　RTSCP帧格式

图5中，去掉了接收地址，加入1字节的数据信息个数，在发送地址后加入n×16字节的数据包信息，以携带待发送数据信息，其中n为所携带数据信息的个数。

2.2　HCP与NCP帧格式

802.11协议中CTS帧格式[14]，如图6所示。

图6　802.11协议CTS帧格式

图6中，允许发送帧CTS包含有帧控制域、帧交换所需时间长度、地址域和帧校验域。

改进算法中的HCP帧为节点收到RTSCP帧后，当自身有能与问询信息可编码的数据时，回应问询的帧格式。加入1字节数据包个数位和n×16字节数据包信息，如图7所示。

图7　HCP帧格式

改进算法中NCP帧为节点收到RTSCP帧后，当自身没有能与问询信息可编码的数据时，回应问询的帧格式，如图8所示。

图8　NCP帧格式

2.3　节点队列可编码数据筛选过程

每一个节点的发送队列格式，如图9所示。

图9　节点发送队列格式

图9中，S(i)、P(i)、N(i)、D(i)分别表示队列中第i(i=1,2,…)条数据的源节点、上一跳节点、下一跳节点、目的节点。

用E{a,b}=1表示节点a与节点b互为邻居节点，若队列中第i条数据与第j条数据满足

(2)

则第i条数据与第j条数据能够进行网络编码。

若A为某一支配集节点，A的发送队列为QA，QA(k)为队列AA中第k个数据，定义Apre为A的预编码队列，Apre(k)代表队列中第k条数据。QB为某一节点B的发送队列。队列的可编码数据筛选分为两种情况，第一种为发送节点在自身发送队列中筛选，过程如下。

步骤1QA(1)为QA中第一个数据，将QA(1)加入Apre中；

步骤2判断QA(2)与QA(1)是否满足式(2)条件，如果满足则将QA(2)加入到Apre中；

步骤3对于QA(j)，当Apre中不止一条数据时，若QA(j)与Apre中每一条数据满足式(2)，则将QA(j)加入Apre中，遍历整个QA队列，直至队尾。

第二种为已经收到一个来自邻居节点的可编码队列，通过筛选自身发送队列，使符合网络编码的数据能够有更多的机会进行编码。假定节点B已经收到来自节点A的Apre，将其存储为Bpre，筛选过程为:

对于节点B发送队列第j条数据QB(j)，若QB(j)与Bpre中每一条数据满足式(2)，则将QB(j)筛选补充入Bpre，遍历整个QB队列所有数据进行筛选，直至队尾，最终形成一个新的可编码队列Bpre。

2.4　问询过程

支配集中的网络编码模型的一个局部区域示例，如图10所示。

图10　支配集中的网络编码模型的局部区域

图10中，节点A为某一支配集节点，节点B∈N(A)，C为普通节点，B为另一支配集节点，此时A即将发送数据包p，节点A先通过控制信息问询邻居节点是否有能够和p编码的数据，如果有，则A优先接收能够与p编码的数据，而后一并编码发出，增加在A节点处的编码机会和单次编码数据个数。问询过程，见图11。

图11　问询过程

步骤1A首先执行2.3节描述的第一种队列可编码数据筛选，获取到Apre，将Apre写入到RTSCP的n×16字节数据包信息位置，并发送RTSCP发起问询；

步骤2邻居节点B收到RTSCP后，通过解析RTSCP帧，可获知Apre，存储为Bpre；

步骤3B先从自己的发送队列中筛选出下一跳为A的数据，对筛选后队列中的某条数据QB(i)，B可通过路由表获得QB(i)到达节点A后的下一跳节点，记为TN(i)，然后节点B对QB(i)进行转换

(3)

步骤5A如果未收到HCP，则A直接将队列Apre中数据进行整体模二和后获得的单条网络编码数据进行广播发送；如果收到有HCP，则回应CTS并等待对方发送；

步骤6收到CTS的节点B，将能够与Apre进行编码的数据Bresp发送给A；

3　仿真及结果分析

为了验证改进算法的性能，利用Matlab在相同条件下仿真文献[10]中NCDS算法和提出的改进算法的性能。仿真分别在10个随机网络拓扑结构中进行，每个拓扑由1×1的单位区域内随机分布的12个节点组成，并利用文献[15]支配集构建算法构建出网络的连通支配集，每一个网络拓扑进行500次发送测试，每次发送测试发送节点随机选择，数据流源节点和目的节点随机选择，每个节点随机0—5条发送缓存数据。

仿真分别对比了NCDS和改进算法中编码效益、编码利用率和编码量。由于拓扑结构随机生成，差异性较大，所以仿真结果显示出不规则的大小浮动。

(1) 编码效益

编码效益为多次发送测试中利用编码所减少的数据流传输个数。编码效益

其中，c(n)为第n次发送的数据流个数(编码或不编码)。编码效益的测试结果，见图12。

图12　编码效益

如图12所示，在减少编码次数方面改进算法较NCDS算法提升28.3%～56%。这是因为NCDS算法在发送数据时直接在发送队列中筛选出符合编码的数据后编码发送，没有考虑邻居节点的数据缓存状态，损失一部分编码机会，而改进算法在筛选出可编码数据后问询邻居节点，优先接收邻居中能够一起编码的数据，一方面增大了编码机会，另一方面增加了编码的数据量，因此在编码效益方面改进算法较NCDS算法有所提升。

(2) 编码利用率

编码利用率为所有发送测试中能够利用编码的发送次数。编码利用率

其中，b(n)为第n次发送是否利用编码，是为1，否为0，编码利用率的测试结果，见图13。

图13　编码利用率

图13显示，在编码利用率方面，改进算法较NCDS算法提升17%～33.8%。这是因为改进算法在发送之前问询了周围邻居节点的发送缓存状态，本来不能够编码的数据，在接收邻居的可编码数据后，变为可编码数据，因此增加了能够利用编码的发送次数。

(3) 编码量

编码量为所有发送测试中平均单次编码的数据流个数。编码量

其中，c(n)为第n次发送的数据流个数(编码或不编码)。编码量的测试结果，见图14。

图14　编码量

图14显示，在单次编码的数据流个数方面，改进算法较NCDS算法提高27%～35%。这是因为改进算法在筛选出可编码队列后问询邻居节点，使邻居节点可编码的数据补充入了筛选好的队列，增大了可编码队列长度，因此增加了单次编码的数据流个数。

4　结语

基于文献[10]的NCDS算法，提出了基于问询的支配集网络编码的改进方法，借助于现有MAC协议的信息帧交换，引入了新的信息帧格式，使得节点在信息发送之前能够询问周围邻居节点的数据情况，以获取更多的编码机会。仿真的结果表明，该算法较NCDS算法，增加编码效益28.3%～56%，可提升编码利用率17%～33.8%，增加单次编码的数据流个数27%～35%。