代码分发协议中的自适应机制研究

顾俊卿，施伟斌，余俊男，荣佳乐

（上海理工大学 光电信息与计算机工程学院，上海 200093）

0 引言

无线传感器网络（Wireless Sensor Networks，WSN）末梢拥有数以万计可以感知和检查外部世界的传感器，可通过无线通信的方式形成自组织网络，现已广泛应用于智能电网、环境监测、医疗护理等领域［1-4］。近年来，传统WSN技术与云计算技术的结合［5］使其应用场景更加丰富。为应对现实场景中多变的需求，通过多跳自组织网络远程将新版本代码从源节点分发到其他节点成为WSN 领域的一个重要课题。由于大规模部署的节点依靠干电池供电，为提高能量效率和延长网络寿命，需研究如何以最小的能量及时间消耗实现可靠的代码分发。

1 相关研究

数字喷泉码是一种前向纠错码，因其具有轻量化的编解码算法，现已被广泛应用于WSN 中的批量数据传输［6］。例如，文献［7］提出的SYNAPSE++是一种基于喷泉码的代码分发协议，采用混合自动重传请求机制；文献［8］在喷泉码的基础上提出一种加权在线喷泉码，结合缓存占有率和已发送的编码符号来估计恢复率，以此调整后续编码符号的度；文献［9］提出一种基于在线喷泉码的无线广播方案，通过接收节点的反馈信息更新编码符号度；文献［10-11］分别通过生成最小化差异补丁和使用网络编码的方式减少重编程过程中耗费的能量；文献［12-13］分别提出基于自适应广播半径和链路质量的自适应代码分发机制；文献［14］设计了一种提前唤醒路由协议，路由路径中的节点可以在节点发送数据包之前被唤醒。

WSN 所处的环境中通常存在与其共享2.4 GHz 频段的其他无线设备，这种共存会导致WSN 中的数据传输受到干扰，因此当信道饱和导致系统性能下降时，通常采用跳频或扩频抗干扰技术改善。例如，文献［15］提出一种基于接收信号强度的无线传感器网络跳频通信机制；文献［16］将传感器节点与认知无线电节点结合起来，利用许可信道将传感器数据路由到汇点，提高了网络吞吐量；文献［17］提出的HM-MAC 协议在邻居节点间根据信号与干扰加噪声比建立空闲信道表，并筛选出最优数据信道集合以供选择；文献［18］将通信信道分为普通信道和数据信道，节点通过在普通信道侦听邻居节点所发送的清除消息中包含的信道信息确定空闲的数据信道编号。然而，上述方法应用于代码分发会产生大量与邻居节点的通信开销，且会增加原有代码分发协议的复杂度。

为提高抗信道干扰能力，本文提出一种基于喷泉码的代码分发协议自适应机制。在文献［19］方法的基础上对动态冗余机制进行改进，并添加多信道机制。实验结果表明，在存在干扰的环境中，通过增加自适应机制可使通信量以及分发时间明显减少。

2 冗余长度自适应调整

SYNAPSE++中的喷泉码编码包冗余长度为固定值，只有在特定信道条件下（对应丢包率为q）才具有最小通信量。当信道质量下降，丢包率明显高于q时，接收节点解码成功率显著降低，需要通过大量增量传输（重新发送数据分块）实现成功解码，导致通信量上升、节点能耗增加。因此，以下将分析动态冗余长度条件下的数据通信量，并给出根据丢包率选取最佳冗余长度的方法。

2.1 动态冗余长度条件下的数据通信量分析

为适应动态变化的信道条件，每轮分发前接收节点计算上一轮分发的丢包率，据此选取最佳编码包冗余长度δo以获得最小通信量，并将δo反馈给sink 节点，sink 节点选取δo中的最大值作为下一轮分发的冗余长度，以此增加链路质量较差节点的解码成功率。不同丢包率q对应的最佳冗余长度将通过以下公式推导以及仿真得到。

2.1.1 首轮分发传输数据量的期望值

设一轮分发中数据分块的源数据包数量为K个，δ为可变的冗余长度，F（1）为首轮解码成功的概率均值估计。P｛X=i｝=C（K+R，i）（1-q）iqK+R-i为接收到i个编码包的概率，q为丢包率，Ψ（i）为首轮接收到i个编码包后解码成功的概率，此处的Ψ（i）以及以下部分的Ψ 函数均按照SYNAPSE++协议的编解码算法［7］通过仿真得到近似值。

E（C1）为传输数据量的期望值，其中NB为分块数量，编码包中的数据量为X字节。

2.1.2 增量传输后传输数据量的期望值

当首轮分发解码失败后，需要增量传输使得节点接收到足够数量的编码包后才能解码成功。两轮内成功解码的概率均值为：

增量传输后，接收的数据量超出数据缓存大小B，超出的数据会覆盖缓存内的数据，意味着冗余长度的错误估计会导致非必要的通信开销。为此，本文采用按需分发策略，发送节点根据丢包率和缓存空间容量确定每次分发的数据包长度。Θ（x）为丢包率q条件下增量编码包长度的估计。表示为：

式（5）、式（6）分别为增量传输的编码包数量期望值以及两轮传输数据量的期望值。表示为：

当产生第二轮增量传输后，3 轮传输内解码成功的概率均值估计为：

式（8）、式（9）分别为第二轮增量传输的编码包数量期望值以及3轮传输数据量的期望值。表示为：

当存在n个节点时，经过r轮分发能够成功解码的概率为F（r）n，则在第r轮成功解码的概率为F（r）n-F（r-1）n，r≥1。令F（0）=0，在整个分发过程中，传输数据量C的期望值近似为：

2.2 最佳冗余长度选取

为得到不同冗余长度通信量随丢包率变化的规律，并确定特定信道条件下使数据通信量最小的最佳冗余长度，本文利用上述公式进行了仿真，结果见图1。可以看出，不同冗余长度δ在不同信道条件下的性能有所差异，当丢包率由0 开始逐渐增大时，较小的δ对应的数据通信量快速增加，而较大的δ对应的数据通信量随丢包率变化得比较缓慢。当丢包率增大到一定程度时，较小的δ对应的数据通信量随着丢包率的增加逐渐趋于近似线性变化，而较大的δ对应的数据通信量随丢包率变化的斜率逐渐增大。

Fig.1 Simulation result图1 仿真结果

图2 为丢包率p∈（0，0.3］时的最佳冗余长度δo，当p∈（0.2，0.3］，δo不再上升，维持在18 后又快速下降至2。这是由于受到缓存空间大小的限制，无法再提供更大的冗余长度，若不考虑缓存空间，则δo应有持续上升的趋势。

Fig.2 The optimal redundancy length图2 最佳冗余长度

2.3 动态冗余长度机制实现

现有代码分发协议SYNAPSE++采用ADV、REQ、DATA 3 种消息类型，一轮分发的时间被分为3 个固定时隙分别收发这3 种消息。发送节点通过广播ADV 消息告知邻居节点当前已有的数据分块信息，邻居节点接收到ADV消息后向其申请某一数据分块，发送节点将数据分块编码后发出。为能根据当前信道质量自适应调整冗余长度，接收节点将根据上一轮传输计算实时丢包率，据此选取最佳冗余长度δo，并添加于REQ 消息中反馈给发送节点。发送节点统计所有邻居节点REQ 消息中的δo，取其中的最大值以提高链路质量较差节点的解码成功率，进而减少增量传输，提高分发效率。

3 多信道机制

当WSN 遭受严重信道干扰，例如丢包率大于15%时，采用冗余长度的自适应调整机制仍然会产生大量冗余编码包的传输，并且分发时间也会显著增加，因此在抗干扰能力上具有一定的局限性。为此，本文进一步提出代码分发的多信道机制，将通信信道分为控制信道和数据信道，当受到严重干扰时，通过更换数据信道避免持续的增量传输。

3.1 外部干扰与WSN信道配置

由于WSN 与其他无线设备共同工作于2.4 GHz 频段，该频段下存在ZigBee、WIFI、Bluetooth 等多个标准，因此WSN 易受到采用这些标准的无线设备的干扰，其中最为典型的干扰来自WLAN 设备［20］。本节主要讨论WSN 如何有效避免来自WLAN 的干扰。

图3为WSN信道与WLAN信道示意图。WSN信道的带宽为2 MHz，中心频率间隔为5 MHz；参照IEEE802.11n［21］标准，WLAN 信道常用带宽为20 MHz。在2.4～2.483 5 GHz 频率范围内，WSN 的11-25 信道与WLAN 的1-13 信道重叠，WLAN 的14 信道在中国并未授权使用，且WLAN 的13 信道中心频率为2 472 MHz，对中心频率为2 480 MHz 的26信道干扰较小［22］，因此WSN 的26信道具有较高的可靠性。

Fig.3 WSN channels and WLAN channels图3 WSN信道与WLAN信道示意图

分发协议的多信道机制采用固定控制信道结合可切换数据信道的方式，将26 信道作为控制信道，用于传输ADV、REQ 信息；11-25 信道作为可用的数据收发信道，数据收发阶段结束后从数据信道切换回控制信道。假设当前WSN 的数据信道为n，受到工作于同一频段的WLAN 设备Xs 的干扰，导致传输效率显著下降时，则切换至n+4，跳出Xs 当前信道的频率覆盖范围。为提高信道利用率并降低多信道协议的复杂度，数据信道将以WLAN 信道的带宽为间隔在11-25 信道循环切换。例如，当数据信道为11 信道，数据的收发受到工作于信道1 的WLAN 设备干扰时，则数据信道切换至15 信道避免干扰；若依旧存在较强干扰，则继续更换数据信道。以上针对WLAN 信道所设计的多信道机制可使WSN 有效避开WLAN 干扰。

3.2 更换数据信道的条件

确定更换信道的条件需综合考虑通信量、分发时间和系统存储空间的限制。随着丢包率的上升，通信量和分发时间相应增加。图4 为分发时间随丢包率变化的情况，可以看出当丢包率大于10%时，分发时间随丢包率上升的斜率明显增大。系统数据存储器的空间限制了冗余包数量的最大值，因此本文将更换数据信道的条件设置为丢包率p≥0.14，对应于通信量增加超过50%（相对于p=0 时），即当连续两轮传输的丢包率皆超过阈值（14%）且后一轮的丢包率高于前一轮时，则切换数据信道。例如，设某一接收节点第n轮分发的丢包率为PLRn（n≥1），n+1 轮分发的丢包率为PLRn+1，当PLRn+1>PLRn>14%时，接收节点将REQ 消息负载中的信道切换标志位，sink 节点接收到REQ 消息后将广播新的数据信道编号，并切换至该信道进行第n+2 轮的分发。

Fig.4 Mean of dissemination time corresponding to packet lost rate图4 分发时间均值随丢包率变化的情况

3.3 多信道分发协议

基于上述原理，本文设计了一种多信道代码分发协议（Dynamic Redundancy and Multi-channel，DRD&MCN），并在TinyOS 中实现了该协议。为实现网络在控制信道与数据信道间的切换，增加消息类型SW，该消息负载的内容为需切换的信道编号。多信道的代码分发过程如图5所示。

Fig.5 Multi-channel code distribution process图5 多信道代码分发过程

接收节点完成编码包的接收后，计算上一轮图5 分发的丢包率并完成信道决策，置位或复位REQ 消息的信道切换标志位，sink 节点统计收到的REQ 消息后，广播SW 消息使接收节点切换至指定数据信道接收DATA 包。为保证接收节点能及时切换回控制信道接收ADV 消息，获取其中的时间戳，完成与sink 节点的时间同步。传输完成后，sink 节点再次广播SW 消息切换回控制信道，若未收到SW消息，则会在数据传输阶段结束后切换回控制信道。

4 实验结果与分析

4.1 动态冗余机制在实际环境中的性能

实验采用以CC2430 为核心的硬件平台运行SYNAPSE++以及改进后的代码分发协议，CC2531 作为侦听节点侦听WSN 信道中的消息包。实验环境为上海理工大学光电大楼9 楼的办公区域，平面示意见图6。分别将sink节点、侦听节点以及5 个接收节点布置于该环境中，由一台路由器以及两台PC 机组成WLAN。

Fig.6 Sketch map of experimental environment图6 实验环境平面示意图

为验证“2.3”节仿真的可靠性，在实验室随机的信道环境中进行实验，分别选取不同冗余长度进行3 次实验，实测值与仿真值比较见图7，其中曲线图与柱状图分别为不同分块冗余长度对应的平均传输数据量和丢包率。可以看出，实测数值与仿真值较为接近，验证了理论分析的正确性。

Fig.7 Comparison of experiment and simulation results图7 实测值与仿真值比较

设置代码分发协议工作在与WLAN 信道频段重叠的WSN 信道上进行，通过iperf［23］控 制WLAN 中UDP（User Datagram Protocol）流的带宽以对WSN 产生不同程度干扰。在相同实验条件下分别测试SYNAPSE++协议以及添加自适应动态冗余长度机制的代码分发协议（Dynamic Redundancy，DRD），从总通信量大小以及分发时间两个方面考察两者在不同强度信道干扰下的性能，将分发过程的平均丢包率作为信道干扰强度的度量值。图8、图9 分别为总通信量和分发时间的比较结果。可以看出，随着丢包率的上升，动态冗余机制使通信量与分发时间显著减少，当丢包率p∈（0.10，0.15］时，通信量与分发时间分别平均减少了20.45%和37.39%。DRD 协议根据实时计算的丢包率以及剩余缓存容量选择最佳编码包冗余长度，因此即使存在信道干扰也能以相对较少的冗余开销提升接收节点的解码成功率，避免过多的增量传输，提升了分发效率。

Fig.8 Comparison of traffic图8 总通信量比较

Fig.9 Comparison of dissemation time图9 分发时间比较

当信道环境恶劣时，DRD 协议会通过使接收节点向发送节点申请更多冗余编码包的方式抵抗信道干扰，但这同样会导致通信量大幅上升，分发效率降低。如图9 和图10所示，当丢包率p∈（0.15，0.20］时，DRD 协议相比SYNAPSE++减少了14.78%的通信量，分发时间减少了6.39%，但相比丢包率p∈（0，0.03］的情况，通信量增加了84.09%，分发时间增加了189.88%。可见在丢包率过高时，动态冗余机制性能有所下降。

Fig.10 Comparison of code dissemination traffic图10 总通信量比较

4.2 多信道机制在实际环境中的性能

为考察结合动态冗余与多信道机制的代码分发协议DRD&MCN 的性能，在图6 实验环境中进行测试。使用4台PC 与两台路由器组成两个WLAN，以此对WSN 的11-22 信道形成干扰。如图10 和图11 所示，当丢包率p∈（0，0.10］时，DRD&MCN 与DRD 的总通信量相差不超过6.98%，分发时间相差不超过16.09%。由于分发过程平均丢包率未超过设定阈值，引起信道切换的次数较少，动态冗余机制在抵抗信道干扰中起主要作用，两者总通信量与分发时间差距较小。当丢包率p∈（0.10，0.25］时，此时超过了预设阈值，因此数据信道通过3 次更换从11 信道切换至空闲的23 信道，DRD&MCN 相较DRD 和SYNAPSE++总通信量平均分别减少了42.58%和53.08%，分发时间平均分别减少了59.89%和64.05%。由于23 信道未受到干扰，因此切换至该信道后，总通信量和分发时间较为稳定，且显著少于另外两种协议，说明多信道机制可有效避免在受干扰严重的信道中持续进行数据分发的情况。

Fig.11 Comparison of dissemation time图11 分发时间比较

5 结语

本文对代码分发协议的自适应机制进行研究，提出一种动态冗余长度与多信道机制相结合的方法，根据受干扰程度分别采用动态冗余机制和多信道机制减小干扰影响。实验结果表明，在存在干扰的条件下，与现有分发协议相比，本文方法可使通信量与分发时间显著减少，有效提高了分发效率，有利于延长WSN 的生存时间。

动态冗余机制的原理是通过计算上一轮传输的丢包率选取最佳编码包冗余长度，虽然当前节点成功解码该轮传输的编码包，但是之后发送节点还为其他节点提供了数轮增量传输，即当前节点计算的丢包率反映的并不是当前时刻的信道状况，这会导致选择的冗余长度并不匹配当前链路质量，进而造成不必要的增量传输。后续可考虑建立不同丢包率下的通信参数数据集，通过机器学习算法建立模型估计链路质量。该方法不需要探测包，具有更高的实时性。