移动P2P中多次网络编码反馈调节方案

张国印，樊旭，高伟，王向辉

(哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨150001)

随着无线通信技术的迅速发展和移动终端处理能力的逐渐增强，为满足日益增大的移动网络信息服务需求，出现了结合移动网络环境与P2P系统的移动对等网络(mobile peer-to-peer network，MP2P)［1］。移动网络具有网络拓扑结构不断变化及节点自身资源受限的特点，如何实现高效、稳定的数据分发成为MP2P网络领域的重要研究内容［2］.

多跳网络拓扑结构与异步分块数据分发机制可有效抵制MP2P网络节点的快速移动与频繁的加入退出所带来的数据块分布不断变化［3］。异步分块数据分发方案无须在源节点与接收节点间建立直接连接，源节点只需将数据片段缓存给中间节点，接收节点再从中间节点下载请求的数据。但数据分块在降低网络扰动带来负面影响的同时也带来稀缺数据问题。

随机网络编码中，中间节点不仅可以进行存储转发操作还可以用随机生成的编码向量对收到的数据进行线性组合，随机网络编码最大化了有向无环网络中组播会话的网络信息流速率［4］。由于编码过程混合了不同数据流使数据间差异变小，因此网络编码技术在提高网络吞吐量的同时又可以改善稀缺数据带来的负面影响，已被广泛的应用于移动网络或P2P系统中［5-7］。王蕾等将改进的部分网络编码方案应用于无线传感器网络中用来提高网络效率并减少能量消耗［5］;GUO B等提出了多跳网络中节点的编码条件，并以此找出信源和信宿节点之间的潜在路径和潜在网络编码机会［6］。LI Baochun等的研究表明在P2P系统中应用网络编码会对网络各方面性能均有提升［7］。

移动P2P拓扑的不断变化增加了下载节点的请求次数，现有的移动网络采用完全的网络编码方案对数据进行单次编码，每一次网络编码操作均将多个源数据块编码成一个编码块，因此单次编码不可避免地减少了流经编码节点的线性无关数据的数量，所以在移动P2P这种高动态网络环境中会增加网络延迟。在移动对等网络分层的网络结构的基础上提出了一种多次网络编码反馈调节(feedback adjustment for multiple network coding，FAMNC)数据传输方案。

1 多次网络编码

1.1 网络编码过程

设单源组播网络用有向无环图G=(V，E)表示，其中V为节点集，E⊆V×V×Z为有向边集。s∈V为源节点，T⊂V为宿点集，T={t1，t2，…，tN}。节点v∈V的输入信道集为ΓIn(v)={d:head(d)=v}，输出信道集为ΓOut(v)={e:tail(e)=v}，其中d，e∈E。

在P2P文件分发系统中，源节点将大小为F字节的文件广播给每一个参与节点。源节点在广播前将文件分割成M块，每块的大小为k=F/Mbyte。参与文件分发的节点被随机的组织成一个对等覆盖网进行数据块交换。每个节点与周围一定数量的节点建立连接，称这些节点为邻居。假设每个节点建立连接的邻居节点数满足统一分布，并可以随着时间改变。数据传输只发生在节点与其邻居节点之间。

应用基于分段的网络编码中，初始的M个数据块被划分成G段，每段包含m块，称为段大小。仅对段内数据块应用随机线性网络编码。假设第i段有原始块，那么从这个段得到的一个编码块b是在有限域GF(2q)上的线性组合。编码操作并不限于源节点，如果一个节点(包括源节点)有第i段中的l(l≤m)个编码块，当这个节点向其他节点传输数据时，它在GF(2q)随机地选择一组数构成局部编码向量，并对它所拥有的第i段内的所有数据块进行编码，生成大小仍为k字节的编码块x，x=编码原始数据块生成x的全局编码向量嵌在每一个编码块的头部。只要一个节点收到第i段中的m个线性无关的编码块，便可利用高斯消去法将第i段解码。

1.2 多次网络编码

下载节点所接收到的同一段内线性无关的编码块的数量决定了节点能否对该段解码，邻居节点间交换编码块的速度决定了节点的下载时间。为增加编码机会，编码节点在进行编码操作之前会进行等待，只有在节点缓存区数据量满足一定条件时才会进行编码。等待编码的过程对已有数据进行重复编码提供了机会，为了增加编码节点下游网络中数据量，减少下载时间，所以在已有单次编码基础上提出多次网络编码。

定义1 基于分段的网络编码中，编码节点v∈V随机生成k组局部编码向量m1，m2，…，mk，将已有的l个属于同一代的数据块，编码成k(2≤k＜l)个线性无关的编码块转发给下游节点的过程称为多次网络编码。

由定义1，编码节点v生成k组局部编码向量，对收到的数据进行多次编码，因此有

定理1 节点v的下游节点集Λout(v)中，若存在i(i＞2) 个节点v1，v2，…，vi满足c(vi)＜h，则节点v进行多次网络编码可减少转发次数。

证明:若存在节点vi∈Λout(v)，使得c(vi)＜h，则其上游节点必须多次转发数据vi才能达到解码条件，且转发次数不小于h－c(vi)。

不采用多次网络编码时，当Λout(v)中有i个节点满足c(vi)＜h时，其上游节点要转发次数 α∈

多次网络编码节点生成的编码块线性无关，因此转发 β=max{h－c(vi)}次可使vi达到解码条件，因此α＞β。

2 MNC反馈调节方案

2.1 编码节点模型

为实现不同网络状态下编码方案的转换，本文采用的编码节点模型如图1所示，该图所表示的是三输入单输出编码节点。图中实线代表数据传输链路，是上游节点发送给下游节点的通路。虚线代表控制信息链路，是超级节点与编码节点进行信息交换与调节控制的通路。3个数据缓存区b1、b2、b3分别存储对应输入链路发送来的数据块。用⊕表示网络编码操作，此处虽然用⊕表示操作但并不意味着必须使用异或方式进行编码，可使用任一种满足假设的编码方案。b0表示输出缓存，用于存储待发送的编码数据块。

图1 编码节点模型Fig.1 Model of encoding node

2.2 网络模型

网络拓扑结构是提高内容分发效率的基础，网络结构是否合理将会直接影响网络效率。常见P2P网络模型有3种:集中式P2P网络模型、纯P2P网络模型和分层式P2P网络模型。对具有高动态性的移动网络而言，松散的非结构化网络框架设计会降低信息传输的准确率;而结构化的框架设计又会因节点频繁的加入、离开导致巨大的路由更新开销。分层式P2P网络模型结合了前2种模型的优点，对整个移动P2P网络结构的设计和节点处理能力的分配都进行了优化。本文将移动网络中的节点划分为由超级节点层与普通节点层组成的2层网络，以超级节点为中心将网络划分为多个子网，各子网相对独立，当节点动态加入网络、完成下载或者能量耗尽动态离开网络时，只对其所在子网的路由表有影响，不会对其他子网产生影响。

用计算能力(C)、内存大小(M)、剩余能量(P)、在网时间(T)4项指标表示将节点的综合能力(A)，记A=α1C+α2M+α3P+α4T，其中。根据A值的大小将节点分为超级节点Si和普通节点层中的转发节点Oi与编码节点Ci。

超级节点负责子网内成员的管理和子网间的查询任务，在资源共享方面所有节点地位相同，超级节点上存储了同一子网内其他节点的信息，当请求在同子网节点间得不到响应时，发现算法会在超级节点之间转发请求，超级节点再将查询请求转发给适当的普通节点，这样在超级节点之间就构成了一个高速转发层。编码节点主要是对接收到的数据块进行编码，增加系统中编码块的分布，从而促进块的多样性，避免稀缺块问题。转发节点负责网络中数据的存储及转发。普通节点层不区分普通节点与编码节点，默认为普通节点为进行0次编码的编码节点，即超级节点调节普通节点的编码次数由0到多次。

当有新的节点动态加入网络时，可以先按请求资源的类型进行分类查找，即找到含有这类资源的最近的超级节点，然后加入该超级节点所管理的子网，并随即选择其邻居节点，超级节点也会根据新加入节点的信息更新其管理的路由表。当网络中的节点由于完成下载任务或者生存期耗尽而离开网络时，超级节点会通知其邻居节点，并更新其路由表。

2.3 反馈调节方案

移动P2P网络中的编码节点不能及时获得邻居节点的详细情况，所以无法确定恰当的编码次数。过多或过少的编码次数都会因增加能量消耗或增加转发次数而降低网络效率。为使编码节点选择适当的编码次数，采用反馈机制对节点的编码状态进行即时调节。编码节点与接收节点将运行情况反馈给超级节点，超级节点做出判断，对编码节点所采用的编码方案进行调整，保证整个系统处于最优状态。编码节点数据处理流程如图2所示。此外，转发节点和编码节点之间的转化与节点编码次数是由超级节点触发的，超级节点会周期性的检查子网内节点的状态，当数据分发效率较低时，就会选择性能较强的普通节点转化为编码节点。

定义2 网络中编码节点v执行编码操作次数与收到的数据块总数的比值称为该节点的编码容忍率，记为，全局编码容忍率则记为

图2 编码节点信息处理流程Fig.2 Data processing flow of encoding node

定义3 网络中下载节点成功下载网络中数据块的次数与请求下载数据块总数的比值称为成功请求率，记为

定理2 成功请求率与编码容忍率成负相关。

证明:节点成功接收到的数据块总量由发送次数与接收节点数量决定，即

由式(1)、(3)可以得出:

由式(2)、(4)可以得出:

由式(5)可以得出结论:在其他条件不变的情况下，编码容忍率降低则网络的成功请求率升高，反之，编码容忍率升高则网络的成功请求率降低。

定理3 采用负反馈调节机制可以使成功请求率D在阈值D0附近一个狭小范围内变动，且当D=D0时，方案传输延迟最低。

证明:基于FAMNC的循环性，当网络中成功请求率D≥D0时，将减少编码次数。一旦成功请求率D≤D0时，将增加编码次数。循环执行一段时间后，网络中块的分布将达到相对稳定且均衡的状态，成功请求率D在阈值D0附近一个狭小范围内变动，并且全网转发次数最少。

下面证明当D=D0时，方案传输延迟最低。在数据分发系统中采用网络编码方法，方案传输延迟包括请求延迟与编码延迟2部分。

请求延迟为分发率的函数DR=f(D)且，编码延迟为编码容忍率的函数DC=g(R)且，根据定理2可知

因此，随着网络中编码次数的增加，成功请求率D会得到提高，反之成功请求会降低。而网络编码次数的增加会带来更多的传输延迟，因此随着成功请求率D的提高，传输延迟也会增加。

根据定理2、3可以构建负反馈模型。调节功能因子T设计为

反馈调节的多次网络编码策略可具体描述如下:

1)设成功请求率理想阈值为D0。

2)初始状态下，全部节点均处于单次编码状态，则可以根据式(2)计算网络中的成功请求率D。

当实际成功请求率较低时即D≤D0，此时，网络中数据请求成功率过低。子网内接收数据量较多且没有进行多次编码节点将被超级节点开启多次编码功能，超级节点增加子网内节点的编码次数，子网内线性响应请求数据量升高，网络的成功请求率将升高。

当实际成功请求率较高时即D≥D0，此时，网络中节点编码次数过高。超级节点降低子网内编码次数过多节点的编码次数，网络的成功请求率将降低。

3 仿真实验与结果分析

为验证本文提出的方案在移动P2P中的性能，通过Matlab实现了一个由离散事件驱动的实验环境并与分段网络编码方案和基准方案泛洪(flooding)方案进行性能比较。3种方案均采用同步方式运行，通过最常用的统计数据分发所需的周期数的方法来评价不同方案的下载时间。只对比方案的数据分发效率而不考虑其他代价是不全面的，因此本文进一步比较了不同方案所产生的能量消耗。

3.1 数据分发效率

3种方案均在网络层进行操作，因此忽略链路层和物理层的实现细节，覆盖层为分层的移动P2P。节点数定为200。节点移动模型为 Random Waypoint［8］。部分实验参数如表1所示。

本文提出的FAMNC方案，与NC方案与Flooding方案的数据分发时间对比曲线如图3所示。

从图3可知，3种方案数据分发进度基本保持线性增长趋势。Flooding方案初期效率明显，中期稳定，后期速度有放缓趋势。FAMNC在整个数据分发过程基本保持一定分发速率，网络扰动对其影响不大;最终完成数据分发的时间比Flooding方案稍长。NC方案一开始就明显慢于Flooding方案与FAMNC方案，在数据分发完成50%后又受网络扰动影响，分发效率再次减缓。

表1 仿真参数Table 1 Simulation parameters

图3 数据分发效率对比Fig.3 Data distribution rate comparison

3.2 能量消耗

本节通过统计来比较3种方案所带来的能量消耗。设定节点发送功率为0.6 W，接收0.2 W，编码功率为0.05 W［9-10］，其余实验参数与表1参数值相同。参量消耗对比图如图4所示。

图4 能量消耗对比Fig.4 Energy consumption comparison

从图4可知，3种方案所带来的能量消耗差异明显。NC方案能量消耗前期增长缓慢，稳定状态能量消耗较低。FAMNC方案前期增长迅速，并以较大的波动稳定在均值，比NC方案略低处。Flooding方案快速达到稳定状态，以较小的波动在高能量消耗状态进行数据分发。

3.3 实验分析

综合对比数据分发率与能量消耗2个方面的实验结果可以看出，FAMNC方案在移动P2P数据分发中表现出了良好的性能。以低于Flooding方案15%左右的能量消耗达到了相接近的数据分发效率。由于FAMNC是在网络编码的基础上进行的改进，使数据块间的线性相关概率极低，保证了每次转发的有效性。而Flooding方案的转发方式使邻居节点间存储了大量的线性相关的数据块，导致后期无法进行有效的数据交换。

此外，FAMNC方案的数据分发效率与能量消耗两个指标均优于NC方案。NC方案中编码节点没有根据网络状态做出相应的调节，而是以固定的方式进行单次编码，浪费了为下游节点提供更多数据的机会，降低了网络整体的数据分发速度。

4 结束语

为提高移动对等网数据分发效率，提出了FAMNC数据分发方案。该方案通过超级节点分析反馈信息，实现对编码节点的调控。实验结果表明，在相同的网络环境，FAMNC方案的数据分发效率明优于NC方案，接近了Flooding方案的分发效率。FAMNC的能量消耗始终低于Flooding方案，并略优于现有NC方案。在以后的研究中，需要考虑编码节点间的配合以减少重复编码现象，进一步降低能量消耗。

［1］欧中洪，宋美娜，战晓苏，等.移动对等网关键技术［J］.软件学报，2008，19(2):404-418.OU Zhonghong，SONG Meina，ZHAN Xiaosu，et al.Key techniques for mobile peer-to-peer networks［J］.Journal of Software，2008，19(2):404-418.

［2］李伟，徐正全，杨铸.应用于移动互联网的peer-to-peer关键技术［J］.软件学报，2009，20(8):2199-2213.LI Wei，XU Zhengquan，YANG Zhu.Peer-to-peer key technologies in mobile internet［J］.Journal of Software，2009，20(8):2199-2213.

［3］贾美娟，郭方方，王慧强，等.分层超级节点的MP2P资源分发［J］.哈尔滨工程大学学报，2012，33(10):1278-1282.JIA Meijuan，GUO Fangfang，WANG Huiqiang，et al.MP2P resource distribution of a layered super node［J］.Journal of Harbin Engineering University，2012，33(10):1278-1282.

［4］HO T，MEDARD M，SHI J，et al.On randomized network coding［C］//41st Annu Allerton Conf Communication，Control，and Computing.Monticello，USA，2005:1-10.

［5］王蕾，张国印，马春光，等.传感网络中以能量为中心的部分网络编码方案［J］.北京邮电大学学报，2012，35(4):107-111.WANG Lei，ZHANG Guoyin，MA Ghunguang，et al.Partial network coding scheme based on energy in WSN［J］.Journal of Beijing University of Posts and Telecommunications，2012，35(4):107-111.

［6］GOU B，LI H.Analysis of general network coding conditions and design of a free-ride orienter routing mertid［J］.IEEE Transactions on Vehicular Technology，2011，60(4):1714-1727.

［7］LI Baochun，NIU Di.Random network coding in peer-topeer networks:from theory to practice［J］.Proceedings of the IEEE，2011，99(3):513-523.

［8］JOHNSON D B，MALTZ D A.Dynamic source routing in Ad Hoc wireless networks［J］.Mobile Computing，1996，353:153-181.

［9］TAI H T，CHONG E T，SEI P L.Maximum energy level Ad Hoc distance vector scheme for energy efficient Ad Hoc networks routing［C］//IEEE 9th Malaysia International Conference on Communications.Kuala Lumpur，Malaysia，2009:423-428.

［10］XIAO Keyin，ZHANG Yide，FENG Gang，et al.eCOPE:energy efficient network coding scheme in multi-rate wireless networks［C］//IEEE Wireless Communications and Networking Conference.Shanghai，China，2013:18-23.