编码节点动态管理的间断连接无线网络数据转发机制

吴大鹏，楼芃雯，樊思龙，王汝言

（重庆邮电大学 宽带泛在接入技术研究所，重庆 400065）

1 引言

区别于传统移动自组织网络的数据转发机制，间断连接无线网络充分利用节点移动带来的相遇机会，以“存储—携带—转发”的模式逐跳实现数据转发，适用于节点稀疏、移动频繁及连接具有间断特性的应用环境[1,2]。

与其他无线网络类似，间断连接无线网络也具有资源有限性的特点，因此，数据转发机制是间断连接无线网络的关键技术之一。为了充分地利用有限的网络资源，研究人员提出了网络编码方法，解决了多源数据并行传输的问题，能够有效提高网络资源利用率[3]。按照此种方式，网络中所传输数据的总量不随网络规模和节点密度改变而发生变化，网络开销得到了有效的控制[4,5]。

针对间断连接无线网络的特点，国内外研究人员提出了多种基于网络编码的数据转发机制。文献[6,7]提出了基于擦除码的数据转发机制，此种机制需要预先获知整个网络中节点连接次数以确定转发块数，难以适用于动态性较强的间断连接无线网络。文献[8]分析了适用于间断连接无线网络的随机线性网络编码(RLC,random linear coding)机制，源节点以随机线性编码对数据进行融合后转发。此种机制无需预先获知相关网络参数，但数据转发过程需要所有节点具有编码和解码功能，极大地消耗了节点缓存和网络资源。文献[9]提出了编码数据冗余控制机制，源节点将多个数据融合，并利用二进制喷洒的方法转发，从一定程度上控制了编码数据的冗余程度，但网络中编码节点的规模依然较大。文献[10]提出了优先编码机制，其假定网络中存在多个优先级数据，节点由高到低逐级转发数据，并结合当前网络状态确认信息。此种机制并未对优先级数量与控制开销进行定量分析，且此种网络中的数据传输延时较大，确认信息所反映的网络状态准确程度难以保障。

相关研究结果表明，间断连接无线网络具有“大世界小世界”特性，其中的节点具有极强的社会属性[11,12]。根据节点之间社会关系的强度，可以将网络从逻辑上划分为多个社区，具有相同归属社区的节点社会关系强度较高、相遇频繁，反之，相遇次数较少，且网络中活跃度较高的节点经常游离在归属社区和其他社区之间。显然，上述相关机制并未考虑节点之间的社会属性，难以为数据合理地选择中继节点；此外，将网络编码方法应用于间断连接无线网络中的数据转发还需要考虑以下4个方面问题：1）除了具有普通节点的存储、携带、转发功能外，编码节点还需具备编（解）码功能，导致其成本增加；2）在数据处理过程中，编码节点的相关操作将增加数据的传输延时；3）数据转发过程中需要携带编码和解码操作相关信息，产生了额外的控制开销；4）编码节点需要执行较多的存储和计算操作，节点资源消耗严重。

针对节点的社会属性以及编码节点受限特性，本文提出一种编码节点数量动态管理的间断连接无线网络数据转发（DMCN,data forwarding mechanism based on coding nodes dynamical managing）机制。通过利用各社区节点数量的变化情况来自适应地管理节点的编码功能，进而，根据节点社会属性以及可用资源状态为所传输的数据合理地匹配中继节点，从而在有效降低网络资源开销的条件下，保障数据传输的可靠性，提高网络资源利用率。

2 编码节点动态管理方法

从逻辑功能角度来说，间断连接无线网络中的节点可以划分为普通节点和编码节点。编码节点除了具有普通节点的功能外，还具有数据处理功能，能够执行编码、解码相关操作。通过动态地估计各社区内节点数量，本文以最优化编码节点数量为原则管理各个社区中节点工作模式。

2.1 最优化编码节点数量

相关理论研究和实际测量表明，对于间断连接无线网络来说，在所有节点都执行编解码操作时，网络性能将严重恶化，根据当前网络规模及运行状态，编码节点数量存在最优值[13,14]。

对于间断连接无线网络的节点来说，成为编码节点需要具备充要条件如下。

1)节点所承载的多个数据流至少来自 2个或者2个以上的链路，且数据流经相同链路完成转发。

2)节点的输入数据流之和大于共享输出链路的传输容量 C，如式(1)所示，其中，fi为上一跳节点经不同链路所转发到本节点的数据流。

间断连接无线网络以分布式方式运行，网络拓扑状态动态改变，通常采用随机图模型对网络性能进行分析，将网络中的节点抽象为随机图中的端点，节点之间的链路抽象为连接随机图中各个端点的边。给定随机图模型下，最大网络信息流流经某条边的概率如定理1所示[13]，节点间的当前连接为编码连接的概率如定理2所示，进而，可以获知编码节点数量与当前网络规模之间的关系。

定理1 在随机图 G=(V,E)中，V为网络节点集合，E为所有在网络中可能出现的边集合（即网络可能出现的连接情况）。|V|=n为集合中的节点数量，当n足够大，且对于任意满足条件的ε，存在式(2)所描述的关系，其中，p(p＞0)为任意两节点存在连接的概率。

在满足式(2)中ε的条件下，最大网络信息流流经某条边（即存在连接时）的概率Pe满足式(3)关系，其中，p(p＞0)为任意两节点存在连接的概率。

可见，当网络规模足够大时，任何连接均以较低的概率成为最大网络信息流路径，即当网络中节点数量较多时，节点成为编码节点的可能性较低，因此，在间断连接无线网络中，只需要在一部分节点上执行编码操作，即编码节点数量存在最优解。

网络中的编码连接是指多源数据在节点上编码后的输出连接，也就是说编码节点的数量不会超过编码连接的数量，因此节点成为编码节点的概率Pen也满足上式。同时Pen与当前网络规模即该网络节点总数n存在如下关系

可知，节点成为编码节点的概率 Pen与网络规模呈线性关系

假设关于x的2个函数f(x)和g(x)存在如下关系

那么这2个函数f(x)和g(x)存在近似线性关系

从而，可知当前网络规模与所需要的编码节点数量Ncoding之间的关系如下

综上所述，根据定理1和定理2可以获知最大网络信息流流经某条边的概率以及节点间当前连接为编码连接的概率，通过对式(4)求极限，并应用无穷小定理，可以得到如下结论：网络所需编码节点数量与网络规模呈近似线性关系；此外，通过分析及实际测量可以验证，网络所需编码节点数量可以控制在较小的范围之内，具体的最优解情况在后面的仿真部分给出。

2.2 编码节点选取

间断连接无线网络中，节点按照彼此的关系强度，从逻辑上组成多个社区，社区内部成员节点关系相对稳定，且具有幂率特征[14]，即一小部分节点活跃程度较高，具有较强的连通性。可见，选择此类节点作为编码节点，执行编解码操作，并为编码后的数据合理地选择中继节点，将有效地提升网络性能，降低资源开销。

如前所述，编码节点需存储来自不同节点的数据，进而以相应的编码方式实现数据融合。显然，相比于普通节点，编码节点的可用资源状态至关重要，因此，节点可用资源也是编码节点选择过程中的重要衡量指标，其定义如式(11)所示，其中，mi为节点i的可用缓存，MBi为节点本地缓存容量。

综合考虑连通率以及缓存可用率2个方面的因素，节点的编码权重估计方法如式(12)所示。

权重因子满足式(13)的约束条件

按照上述方法，网络中的节点以分布式的方式估计自身的编码权重。当与所归属社区的中心节点（CN,central node）相遇之后，节点将编码权重数值估计结果发送给社区中心节点，为编码节点的动态管理提供依据。为了使所提出机制具有较好的可扩展性，在充分利用节点社会属性以及可用资源的基础上，本文采用随机线性网络编码方法对数据进行融合处理，根据接收到的数据和编码系数矩阵，相关节点可以完成对原始数据的恢复。

2.3 动态管理机制

如前所述，准确地获知当前网络中的节点状态是编码节点动态管理机制的关键。通常，社区中心节点在社区间按一定速率和轨迹进行移动，且到达各个社区之后随机停留一段时间。此类节点的重要程度较高，其将以较高的概率与各社区内部节点相遇。在社区内部运动和停留的时间段内，利用社区中心节点的高活跃度可获得较全面的网络状态信息，其中包括当前社区节点数量、编码权重等，将计算出的节点权重值按降序排列，形成编码节点备选集合。社区中心节点根据式(9)估计当前网络状态下的编码节点数量最优值，从而在编码节点备选集合选取合适数量的编码节点，在社区编码节点列表中保存。中心节点所需要保存的信息如表1所示。

表1 社区中心节点保存的信息

社区内各中心节点在运动过程中不断感知当前网络状态，并更新信息表中的相关表项。编码节点列表中的相关信息以权重值为主要参数，按照降序进行排列，且以标志比特Flag表示该节点在当前网络状态下的工作模式，Flag=1表示节点当前具有编码功能，Flag=0表示节点当前为普通节点。

3 数据转发策略

按照所提出的编码节点动态管理机制，中心节点可根据当前网络状态以及节点状态确定最优编码节点数量，进而，利用所选择的编码节点，对数据进行融合与转发处理，可见，为了达到有效控制开销并可靠传输数据的目的，数据转发过程中的中继节点选择至关重要。

如前所述，网络中的节点主要包含3种类型，分别为普通节点集合 A={a1,a2,…,an}、社区中心节点集合B={b1,b2,…,bn}、编码节点集合 C={c1,c2,…,cn}。对应于上述3种类型节点，其携带数据的转发策略也需分别进行考虑：1)普通数据，即普通节点所携带的数据；2)编码融合数据，即编码节点所携带的数据；3)切换数据，即节点在当前时刻具有编码功能，下一时刻为普通节点，依然滞留在缓存中的未完成传输的编码融合数据。在社区中心节点完成编码节点的选取后，普通节点集合A完成对普通数据的转发，编码节点集合C完成对收发数据处理和已编码数据的转发，当集合C中部分元素转换到A集合中时，完成特殊数据的转发，具体转发步骤如下。

步骤1 更新时间tupdate内，依式（12）所示编码节点选取标准，按编码节点权重值iω对各社区内节点进行排序，构建编码节点备选集合，同时根据社区中心节点所获知的节点数量，按式（9）的最优编码节点数量原则，选择备选集合中权重较大的节点作为编码节点。

步骤2 普通数据转发：若普通节点ai所携带数据 Mi为原始数据，且DgroupId≠ai_groupId，则表明原始数据Mi的目的节点所属社区不在当前社区，那么当ai在下一时刻相遇的节点属于集合 C={c1,c2,… cn}，则将 Mi转发给该节点；若 DgroupId=ai_groupId，则表明原始数据已到达目的节点所属社区，为达到减小延时同时充分利用网络资源的目的，该数据在本社区内进行快速转发，其中，DgroupId为Mi的目的节点所属社区Id，ai_groupId为ai所属社区Id。

步骤3 融合数据转发：按目的节点所属社区的groupId，编码节点ci将接收到的Mi进行编码。若在下一时刻遇到社区标识groupId相同的编码节点ci’，即编码融合数据到达目的社区时，则将该编码融合数据转发。若ci’存储足够数量的编码数据后就将该批数据解码，然后在本社区内洪泛，直到解码后数据到达目的节点。

步骤4 切换数据转发：网络状态的变化将可能导致部分编码节点丧失编码功能，但编码融合数据依然在节点本地缓存。当状态转换的节点遇到新的编码节点之后，优先转发已编码数据，然后再执行普通节点的功能。

步骤5 各节点依次重复上述步骤，直至全部数据完成转发。

图1为所提出机制的流程，其中，n为社区节点数量，随着网络中各个节点之间的状态信息交互，ni和Ncoding的数值以动态的方式完成更新。

图1 DMCN机制流程

4 数值结果分析

本部分采用 ONE(opportunistic network environment)仿真平台[15]验证所提出机制的有效性，并与其他经典数据转发机制在生存时间和缓存有限的条件下进行比较，其中，性能指标包括成功投递率、平均延时和路由开销 3个方面，具体仿真场景的参数设置如表2所示。本文选取 α1=0.65、α2=0.35、β=0.3。

此处的α1与α2是编码节点选取的影响因子，β是最优化编码节点数量的影响因子，本文应用的网络模型是社区环境，如前所述，根据社区模型的节点移动特性，在编码节点选取时节点连通性的重要程度较大，因此对网络性能要求不同的场景下，需根据节点活跃程度及自身能耗这两方面设定α1与α2的取值。参数β值的选取是NP完全问题，按照本文给出的推导证明过程，β值的选取受当前时刻网络中节点数量的影响。在社区模型下，节点自由出入各个社区，那么根据一定时间内各社区节点数量变化情况，本文经过多次仿真后最终设定。因此针对不同网络场景，需依据网络的实时情况来选取理想的β值。

4.1 不同生存时间下网络性能

为了更加全面地分析所提出机制的有效性，本文所选取的比较对象分别为基于洪泛的 Epidemic机制[10]、基于连接预测的Prophet机制[16]以及前面提到的RLC机制[8]（假设网络中各个节点均为编码节点）。各种机制在不同生存时间（TTL,time to live）下的性能如图2～图4所示。

表2 仿真参数设置

网络负载率直观地反映了数据传输过程所消耗的网络资源，图2描述了4种机制的网络负载率随TTL的变化情况，可见，网络负载率随TTL值的增加呈上升趋势，其主要原因在于间断连接无线网络中已成功投递的数据副本依然占用网络中的资源。数据在网络中生存时间的增加将导致新生成数据的可用缓存减少，节点相遇机会无法充分利用，数据转发过程的负载率也相应增加。DMCN机制将数据分批编码融合，在选定的编码节点间传递，减少了不必要的数据转发操作，有效地降低了负载率。从结果中可知，DMCN的负载率一直维持在40～60的较低范围内，且较之于其他3种机制负载率分别降低了59.6%、56.8%和64.5%。

图2 不同TTL下的网络负载率

成功投递率是衡量数据转发机制的重要指标之一。图3的结果表明，随着TTL值的增加，4种机制的成功投递率均呈现出逐渐下降的趋势。所提出的DMCN机制成功投递率始终在75%以上，性能较Epidemic提升8%，较Prophet提升17%，较RLC提高25%。其主要原因在于DMCN机制采用编码节点动态管理机制，根据当前网络状态使各社区始终保持最优的编码节点数量，同时有效地控制了编码系数矩阵的大小，即只对相同目的社区的数据进行融合，使得有限的网络资源得到了充分利用。

图3 不同TTL下的成功投递率

从图4可以看出，在生存时间小于220 min的情况下，本文所提出的 DMCN机制具有较低的传输延时，但此后其传输延时处于中等水平。其主要原因在于，编码节点数量的动态管理过程需要较多的统计和估算操作，且当编码节点变成普通节点时，所缓存的数据需要重新进行处理，需要耗费较多的时间。

图4 不同TTL下的平均传输延时

4.2 不同缓存下网络性能

图5～图7描述了不同缓存状态下，各种数据转发机制的性能，其中主要包括负载率、投递率和传输延时等3个方面。

图5 不同缓存下的负载率

图6 不同缓存下的成功投递率

图7 不同缓存下的平均传输延时

从图5可知，节点缓存容量对负载率影响较大，随着缓存容量的增加，各种机制的负载率均呈现出明显的下降趋势。显然，从图中可以看出 DMCN仍然保持在40～60较低的范围内，与其他3种机制相比，分别降低了66.3%、34.9%和62.8%。这是因为DMCN机制有效地控制了编码节点数量，进而限定融合数据在编码节点之间进行传递，此种方式有效地控制了数据传输过程的转发次数，同时在中继节点选择过程中充分地考虑了节点之间的社会属性，使得数据能够以较大的概率到达目的节点所属社区，减少了数据在社区间的转发，有效地增强了数据转发过程的针对性。

不同数据转发机制的投递率性能如图6所示，随着节点缓存容量的逐渐增加，4种机制的数据成功投递率也随之上升。但由于 DMCN机制所需要存储的状态信息多于其他三者，因此，在缓存小于9 MB时，其成功投递率略低，随着缓存的进一步增加，DMCN机制性能趋于稳定并优于其他3种机制，较其他 3种机制性能分别提升 7%、10%和22.3%。DMCN机制通过对编码节点进行动态管理，以确定所需编码节点及其数量，同时，节点按照本文所提出的规则对数据分类处理，编码融合数据只在编码节点间传输，部分普通数据在社区内快速转发，数据在转发过程中的协作节点选择更具有针对性，有效地提升了数据投递率。

图7描述了各种机制的延时性能。在缓存较小时，DMCN机制维持了较低的延时，但当缓存大于11 MB时，数据传输延时也随之增加。与不同TTL场景下的延时性能类似，DMCN中的编码节点需要对数据进行存储、编码和解码等相关操作，处理时间随数据量的增加而逐渐上升；此外，编码融合数据的转发过程需要耗费时间等待合适的中继节点，上述2个方面因素均直接导致了传输延时的增加。

5 结束语

为了充分利用有限的网络资源，本文提出了一种最优编码节点数量计算方法，进而设计了编码节点动态管理的间断连接无线网络数据转发机制。充分利用节点之间的社会属性，节点分布式地获知当前网络状态，并动态地调整编码节点的数量，进而对数据进行分批编码融合。与传统的机制相比，所提出的机制不仅减少了网络资源开销，同时，有效地提高了数据传输过程中的可靠性，改善了网络资源利用率。

[1]THRASYVOULOS S,RAO N,BIN R,et al. Routing for disruption tolerant networks: taxonomy and design[J]. Wireless Network,2010,(16):2349-2370.

[2]苏金树,胡乔林,赵宝康. 容延容断网络路由技术[J]. 软件学报,2010,21(1):120-124.SU J S,HU Q L,ZHAO B K. Routing techniques on delay/disruption tolerant networks[J]. Journal of Software,2010,21(1): 120-124.

[3]TRACEY H,DESMOND S L. Network Coding: an Introduction[M].Cambridge University Press,2007.

[4]KATTI S,RAHUL H,HU W,et al. XORs in the air: practical wireless network coding[J]. Proceedings of ACM SIGCOMM,2006,36(4):497-510.

[5]邓文君,杨真,杨震. 一种新的无线mesh网络编码算法[J]. 重庆邮电大学学报(自然科学版),2010,22(2): 156-158.DENG W J,YANG Z,YANG Z. A new algorithm for wireless mesh networks coding[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition),2010,22(2): 156-158.

[6]WANG Y,JAIN S,MARTONOSI M,et al. Erasure coding based routing for opportunistic networks[A]. Proceedings of ACM SIGCOMM Workshop on Delay Tolerant Networking (WDTN)[C]. Philadelphia,USA,2005. 229-236.

[7]LING C,CHEN Y. A hybrid routing approach for opportunistic networks[A]. Proceedings of the SIGCOMM Workshop on Challenged networks [C]. Pisa,Italy,2006. 213-220.

[8]ZHANG X L,NEGLIA G,KUROSE J,et al. On the benefits of random linear coding for unicast applications in disruption tolerant networks[A]. Proceedings of the 4th Modeling and Optimization in Mobile,Ad Hoc and Wireless Networks[C]. Boston,MA,2006. 1-7.

[9]YUNFENG L,BAOCHUN L,BEN L,et al. Efficient network coded data transmissions in disruption tolerant networks[A]. The 27th Conference on Computer Communications[C]. Phoenix AZ,2008. 1508-1516.

[10]YUNFENG L,BAOCHUN L,BEN L,et al. Stochastic analysis of network coding in epidemic routing[J]. IEEE Selected Areas in Communications,2008,26(5): 794-808.

[11]PAN H,JON C,EIKO Y. BUBBLE Rap: socail-based forwarding in delay tolerant networks[A]. The ACM International Symposium on Mobile Ad Hoc Networking and Computing[C]. Hong Kong,China,2008. 241-250.

[12]SHABBIR A,SALIL S,KANHERE,et al. HUBCODE: hub-based forwarding using network coding in delay tolerant networks[A]. Proceedings of the 12th ACM International Conference on Modeling Analysis and Simulation of Wireless and Mobile Systems[C]. Tenerife Canary Islands,Spain,2009. 288-296.

[13]JINGYAO Z,PINGYI F,BEN L. Network coding for efficient multicast routing in wireless ad-hoc networks[J]. IEEE Transactions on Communications,2008,56(4):598-607.

[14]HUI P,CHAINTREAU A,SCOTT J,et al. Packet switched networks and human mobility in conference environments[A]. Proceedings of the 2005 ACM SIGCOMM Workshop on Delay Tolerant Networking[C]. Philadelphia,USA,2005.244-251.

[15]KERÄNEN A,OTT J,KÄRKKÄINEN T. The ONE simulator for DTN protocol evaluation[A]. The 2nd International Conference on Simulation Tools and Techniques[C]. Rome,Italy,2009. 1-10.

[16]JINGFENG X,JIANSHENG L,YUANDA C,et al. Advanced PROPHET routing in delay tolerant network[A]. International Conference on Communication Software and Networks[C]. Macau,China,2009. 411 - 413.