一种异构网络多协议并行数据分发方法

刘建航 武万萍 王树庆 李世宝 张玉成

①(中国石油大学(华东)计算机与通信工程学院 青岛 266580)

②(中国科学院智能农业机械装备工程实验室 北京 100190)

1 引言

Gartner的研究报告[1]指出，无线连接物联网设备的数量将在2020年之前达到200亿台，多种无线通信技术共存将带动异构无线设备通信的发展。近些年的研究成果[2，3]已经实现了异构无线设备(如Wi-Fi和ZigBee设备)之间的直接通信，如Chi等人[3]提出的并行多协议通信(Parallel Multi-protocol Communication， PMC)技术，通过物理层调制Wi-Fi节点在发送数据时可以用部分子载波捎带传输Zig-Bee数据，从而解决信道争用所带来的资源浪费等方面的问题。由于异构网络节点通信能力不同，通过捎带传输，Wi-Fi[4]可以一跳将数据分发到多个ZigBee[5]节点，这种方式大幅降低了ZigBee网络数据分发中多跳传输的传播时延。然而由于能量受限，ZigBee节点占空比往往低于10%，这意味着超过90%的时间ZigBee节点处于休眠状态。因此，如何规划Wi-Fi节点的传输方案，使其能保证数据分发的可靠性的同时兼顾传输时延和传输效率，是目前急需解决的问题。

文献[6]使用特殊的前导来协调异构设备。Chebrolu等人[7]和Zhang等人[8]通过检测Wi-Fi数据包的数据包长度，实现了Wi-Fi到ZigBee的通信。文献[9]提出使用Wi-Fi系统的信道状态信息(Channel State Information， CSI)启用低功耗蓝牙(Bluetooth Low Energy， BLE)到Wi-Fi的传输。Kim等人[10]提出了一种通用且透明的跨技术通信框架FreeBee，这个通信框架可以在Wi-Fi，ZigBee和蓝牙3种流行的无线技术之间实现直接单播和跨技术的频道广播。Chi等人[11]通过使用常规数据包来支持Wi-Fi和Zig-Bee设备之间的通信。以上的研究工作是关于包层次的跨技术通信，其吞吐量一般来说都很低。

为了提高吞吐量，Li等人[2]首先提出第1个基于仿真的跨技术通信 (Cross-Technology Communication， CTC)，实现了从Wi-Fi到ZigBee的单向通信，通过物理层的仿真，能够使CTC的吞吐量达到理论最大值，但由于WEBee利用Wi-Fi的有效负载传递ZigBee信号，导致了原有的Wi-Fi数据遭到破坏，在传送ZigBee数据的同时不能传输Wi-Fi数据，频率利用率较低。Chi等人[3]对文献[2]进行改进，它探索了在单一Wi-Fi通道内对异构物联网无线电进行多协议并行通信的可能性，从而显著提高频谱利用率。本文在此基础上提出了基于多协议并行数据传输的数据分发方法。但是不管对于PMC还是WEBee，都只是实现了数据的下行传输，即从Wi-Fi端到ZigBee端或是从混合信号发送端到传统的ZigBee与Wi-Fi的接收端，并不能够实现数据的上行传输。另外，在前期工作[12]中，利用喷泉码实现无反馈的可靠传输，这保证了异构网络进行数据分发的可靠性。马彬等人[13]在密集异构蜂窝网络和无线局域网络构成的超密集异构无线网络中，变速移动的车辆终端会面临更加频繁地切换，导致用户服务质量(Quality of Service， QoS)变差。然而我们的工作只异构无线设备(如Wi-Fi和ZigBee设备)之间的直接通信，复杂度低。Zhang等人[14]考虑了面向多信道异步占空比网络的广播问题，提出了一个基于多信道的高效广播协议，该协议可以获得较低的延迟和较高的数据成功传输率。针对低占空比传感网中的最小延迟广播问题，文献[15]提出了一个新颖的冲突容忍调度策略，该策略通过允许在非关键节点上的冲突来加快在关键节点上的广播进程，从而进一步提供了降低广播延迟的机会。Jiang等人[16]通过采用一个基于概率且完全分布式的广播机制实现了低占空比传感网中的数据分发，并且通过理论和实验证明了该广播机制具有较低的延迟和较高的能量效率。

上述研究工作大部分集中在研究传感器网络中广播延迟问题，研究成果应用于异构网络数据分发会导致传输时延较长、传输效率低等问题。基于上述问题，本文建立了一个基于异构网络的多协议并行数据分发模型，提出权衡延迟和能耗的损失函数，通过对该函数中权衡系数的自适应调节优化发送端传输方法，从而在保证数据分发的可靠传输的基础上，满足不同应用对于延迟和能耗方面的需求。

2 系统模型和问题描述

2.1 网络模型与假设

不失一般性地，本文假设所有节点随机分布在一个圆形区域内，发送节点是一个异构网络设备[3]，其在发送Wi-Fi数据的同时，利用64个子载波中的7个子载波捎带传输ZigBee数据。发送节点位于圆形区域的中心(数据分发模型)，并且本文用G=(V，E)来表示异构网络的拓扑结构。其中， V表示包含1个发送节点和多个ZigBee节点的节点集合， E表示发送节点到ZigBee节点的链路集合。此外，本文将时间划分为若干个大小相等的时间单元，每个时间单元长度的设置能够完成所有数据包的收发操作。作为时间度量的基本单元，每个时间单元要么处于睡眠状态，要么处于苏醒状态。

本文还做了如下的一些基本假设：(1)假设异构网络中仅存在Wi-Fi和ZigBee两种设备，且除了实验本身设备之间的相互影响以外，不考虑其他设备所造成的影响。(2)所有的ZigBee设备都工作在占空比可调的低占空比模式下，每个ZigBee节点在加入工作的网络之前，其占空比以及唤醒时间都被发送节点所知。事实上，这是因为ZigBee节点的占空比和开始工作的时间都是人为可控的。考虑最差的情况下，ZigBee的本地时钟发生偏移时，可以发送一个数据包到发送节点。一方面，这一数据包所包含的数据量很小，可以视为一个控制包，不会影响系统的可靠性；另一方面，这种校准操作进行的频率也不会太频繁，所以这种假设也是合理的。(3)每个ZigBee节点的链路上的最高丢包率是已知的。

2.2 问题阐述

在本文中，由假设(2)所有的ZigBee节点都工作在低占空比模式下，每个节点独立地确定自己的工作情况。具体地说，在一个异构网络中，包含1个发送节点以及4个ZigBee节点。在不考虑占空比和数据包个数的情况下，该网络可以抽象成图1所示的矩阵。在图1中1表示该节点处于苏醒状态，0表示该节点处于睡眠状态。对于发送节点来说，如果想要尽可能地覆盖所有的ZigBee节点，即考虑时延最短，可以选择t1，t2，t3，t4作为发送时间。而如果考虑最小的功耗，也就是最少的发送次数，可以直接选择 t7时刻进行数据发送。尽管从时延或者能量损耗单方面来考虑，问题有最优解；但是对于大多数实际应用而言，往往关注的是延迟和能耗的权衡，这就意味着发送节点的发送时刻可以选择t3，t4，t5或者t1，t2，t6或者其他更多的选项，显然这没有最优解，属于NP-Hard问题。

3 算法设计

由于发送次数与系统的能量损耗成正比，发送节点发送得越频繁，系统的整体能量损耗就越高。为了更好地衡量分发算法的性能，本文引入新的损失函数来权衡能量和系统损耗，基于定义的损失函数，提出了基于延迟的数据分发方法。并证明了利用该方法所计算得到的系统损失函数为最小值。在此基础上，利用动态规划的思想设计算法来实现该数据分发方法的求解过程。

图1 网络矩阵图

3.1 损失函数

给定一个网络拓扑G=(V，E)，可以定义如式(1)的系统损失函数

其中，COST(G)表示网络的整体代价，Δdelay表示系统的整体时延，S.T.表示发送次数，σ 表示一个权衡系数，用来衡量系统损失中在发送端完成广播任务时是低时延优先还是低发送次数优先。

3.2 损失函数参数

发送节点每次唤醒并发送 d 个喷泉码所需要的能量主要包括射频能量和处理喷泉码数据包的能量。可以定义如式(2)的能量

图2 时序图

为了确保两个工作时刻相同的ZigBee节点，所收到喷泉码个数接近阈值的一个优先作为不进行时延的节点(即保证了节点能够以最小的时延接收到足够的喷泉码来进行解码)，本文定义第i个节点的时延校正系数

其中，S.T.表示发送节点进行发送的次数，更进一步，也就是ZigBee节点不进行延迟发送的ZigBee的个数。

3.3 损失函数最优值

其中，OV(0)=0，表示当异构网络中不存在ZigBee接收节点时，发送节点不耗费能量，系统损失为0。另外，上述推导过程中，时延校正系数没有改变。这是因为时延校正系数只与ZigBee节点接收到的喷泉码数据包的个数和喷泉码解码的阈值是相关的，而上述推导过程是系统的一次完整的收发过程，ZigBee节点的收包个数并没有发生改变，所以对于这一过程，时延校正系数并没有发生改变。但是在完成这一过程以后，系统可能还存在未达到解码阈值的ZigBee节点，所以系统的收发过程并不能够结束，而是要重复，在进行后续的收发操作时，由于ZigBee节点所接收到的包个数发生了改变，所以对应的时延校正系数也发生了改变，需要重新计算各个节点的时延校正系数，然后对ZigBee节点的时延进行重新的校正排序，来确定接下来数据分发时所需要的ZigBee时延顺序序列。各个ZigBee节点的时延经过校正和排序以后，会生成一个不减的序列，在该序列中，时延最大的节点一定不会推迟到下一个周期去接收数据，所以，经过校正后时延最大的节点一定会在其工作时间接收数据，不会推迟数据的接收。

综上所述，表1详细地阐述了本文所提出的分发算法。假设集合 D里边的元素是需要进行延迟接收的ZigBee节点，集合I里边的元素是在其苏醒时正常接收数据的元素。

在该算法中，最后可以输出发送节点应该在哪个时间点进行数据的发送，并且规定了发送节点每次发送的数据包的大小Nsiend，表示第i次进行发送时发送的喷泉码包的个数。这一数值是可以根据ZigBee节点的占空比进行设置的，只要ZigBee在工作时间段内能够接收这个数据包即可。对于的取值大小，在后续的实验章节中会给出详细的分析。

4 性能分析

4.1 模型参数验证

为了验证模型的可靠性，下面针对所提损失函数模型中的两个参数进行研究，第1个参数是每次P发送节点发送的喷泉码数据包的个数 n，第2个参数是衡量时延和功耗的权衡系数σ。

首先对n进行研究，n 表示每次发送节点发送的喷泉码的数据包个数，由假设(2)，所有的ZigBee节点的工作状态都是稳定的，并且是低占空比的，即苏醒时间远远小于睡眠时间，保证了ZigBee节点的低功耗设计的初衷，另外为了尽可能地减少无用能量的损耗，假设发送节点发送的包都能够被ZigBee所接收，不会存在所有的ZigBee处于睡眠状态时，发送节点仍然在进行发包操作，这无疑会徒增功耗。所以在对 n进行赋值的时候，应该考虑到其与占空比的关系，要保证发送节点一次发送的数据包能够让ZigBee在一个工作周期内全部接收，即发送节点发送多少个喷泉码数据包，ZigBee在进行一个工作周期以后要满足+n。

表1 模型求解算法

图3所示，其中圆圈表示ZigBee节点，〈S，T〉数值对是对该ZigBee节点的描述。其中 S表示该ZigBee节点喷泉解码所需的阈值，可根据FCSA来获得； T表示该ZigBee节点的工作周期所属的时间单元。本次实验，将ZigBee的一个周期划归为20个时间单元。而各个ZigBee节点阈值是根据ZigBee节点离发送节点的远近设定的。在图3中，发送节点和各个ZigBee节点构成网络 G2。另外对图3中Zig-Bee数量和位置进行调整可以得到网络 G1。定义G1为

对 n 取不同的值，利用损失最小值计算方法，可以计算得到损失代价COST如图4所示。从图3和图4中可以看出， G2网络中ZigBee阈值最大的节点为ZigBee10，其解码阈值为150，工作所处的时间单元为4，而当 n 取值150及以上时，损失COST为固定值53，再随着 n值的增大，COST不会减小，已经达到网络的最小损失。但是随着 n值不断增大，PMC发送的喷泉码数据包并没有被所有的ZigBee节点所接收，导致网络功耗增加，而增加的这一部分功耗没有计算到COST损失函数里。另外从图中可以得知，当发包个数 n 为40左右时，COST下降趋势不明显，已经趋于稳定，所以在实际中， n的确定并不是一个固定的值，可以根据不同网络绘制n-COST图，选择合适的发包个数n ，进而确定ZigBee节点的占空比。

图3 G2仿真网络结构示意图

图4 最小损失COST与发包个数n关系图

4.2 数据分发方法性能分析及对比

在传统的网络数据分发中，SPIN协议[17]是比较常用的数据分发协议，SPIN协议是一种以数据为中心的自适应路由协议，该协议能够避免由于节点间重复地收发大量的冗余信息所造成的能源浪费。SPIN作为多跳的广播数据分发协议有自己独特的优势，但是在异构网络中却存在着不足。图5表示在单跳范围内进行数据分发的示意图。图5中过程表示发送节点向ZigBee节点发送ADV数据包，询问该ZigBee节点是否要接收数据包，如果ZigBee节点需要接收数据包，则会进行②过程ZigBee向发送节点发送REQ确认包，最后发送节点会向ZigBee节点发送数据。图中进行②过程时，ZigBee节点需要向发送节点发送REQ的确认信息包，如果ZigBee的发送功率不足以支撑将数据包发送给发送节点时，可以采用多跳方式传输，这里为了方便后续讨论，将多跳传输所需的时间统一归纳到过程②所需的时间中。

本文使用提出的COST损失函数模型来衡量采用SPIN协议的网络进行数据分发时能量损耗和时延的关系。为了更好地对比，需要对COST函数模型中时延的定义进行调整，即某个ZigBee节点的时延用=(fixed)+(v)来计算，这样能够更好地对比SPIN协议下网络的损失，同样地，在衡量本文所提延迟分发方法进行数据分发时的损失时也许需要使用此种时延定义方式。

图5 SPIN协议网络图

在G1网络下进行实验，可以得到图6(a)中所示的结果图。图6(a)中横坐标表示发送节点每次发送的喷泉码数据包个数，纵坐标表示系统的整体损失代价值。为了更方便地观察，将图6(a)中部分放大，如图6(b)所示。从图6的两幅图中可以看出，对时延进行校正的情况下，采用本文所提延迟数据分发方法所产生的系统损失整体上都低于采用SPIN方法所产生的系统损失。另外从图7中可以看出这一规律不管对时延进行校正或者不校正时都成立。利用相同的分析方法，在 G2网络下进行实验，可以得到图7中的结果，同样符合上述规律。损失函数COST主要衡量了时延和能量损耗两个方面，通过系数 σ来权衡。当σ 参数变大时，在系统损失模型中能量损耗占的比重就会增加，其中，发送节点启动发送的次数与能量损耗是直接相关的，由于延迟数据分发算法中，发送节点发送数据的次数又直接与非延迟节点的个数相关。在SPIN协议进行数据分发时，能量损耗直接与发送节点启动发送的次数相关。所以当σ发生变化时，SPIN协议和延迟分发算法对能耗的敏感度不同，当 σ变小时，能耗因素影响的损失计算模型中的比重降低，这时系统总的损失可能出现SPIN协议比本文提出的方法要小的情况。这是由于在进行延迟时会引入新的延迟变量，而如果当 σ足够大时，这一新引入的变量就会被能耗因素所淡化，但是如果 σ变小时，新引入的延迟变量对系统的整体损失影响会变大。

图6 G1网络中不同数据分发方法下的损失图

图7 G2网络中不同数据分发方法下的损失图

图8 低权衡系数下G2网路中不同数据分发方法下的损失图

图8中描述的是当σ=10时，两种不同的方法所对应的最小损失值。从图8中可以看出，时延经过校正时，对 σ的变化感知得更加明显。本文所提方法与SPIN方法进行比较时，可以看出虽然本文所提方法在低σ时最小损失值略大于SPIN方法，但是可以近似忽略不计。所以，在低 σ情况下，本文所提方法性能与SPIN算法相近，但是当σ较大时，本文所提方法有明显的优势。

综上所述，采用本文所提延迟数据分发方法可以有效地降低异构网络中同时考虑时延和能量损耗两种情况下的系统损失。

5 结束语

为了更好地规划Wi-Fi节点的传输方案，本文在异构网络下定义了一个新的系统损失函数衡量系统的时延和能耗，通过对该函数中权衡系数的自适应调节可以使其刻画各种需求的数据传输。此外，为了配合喷泉码的特点，在时延中加入与喷泉码数据包个数相关的校正系数，从而使其能够更好地衡量利用喷泉码传输数据的系统损耗。基于系统损耗函数，本文提出了一种利用信标控制的延迟接收数据包的分发策略。这一分发方法，允许ZigBee在异构网络中选择合适的时机接收数据。发送节点通过发送持续时间很短的控制包信息来告知接收节点就近选择合适的时隙来接收数据，从而在系统层面降低了整体的时延和能量损耗。更进一步地，本文证明了损失函数的合理性，然后根据动态规划的思想，推导出系统的整体能量损耗和时延的最优值。最后，实验结果验证了本文的方法相比较于传统方法更具优越性。