延迟容忍移动传感器网络(DTMSN, delay tolerant mobile sensor networks)^[1]利用延迟容忍网络^[2]数据传输技术实现不连通传感器节点间的通信, 对物联网和普适计算有重要意义.尽管传感网的主要功能是收集数据, 但广播仍是其一种基本而重要的数据传输方式^[3].当前DTMSN的广播传输机制主要基于直接传输^[4]、基于洪泛^[4]和传染病^[5]等.杨奎武等^[6-7]基于随机线性网络编码(RLNC, random linear network coding)提出了广播传输机制(NBT, netcoding-based broadcast transmission scheme)^[6]和高效广播传输机制(NEBT, netcoding-based efficient broadcast transmission scheme)^[7].笔者鉴于机会网络编码(ONC, opportunistic network coding)能有效提高网络吞吐量, 结合RLNC和ONC提出一种基于流内与流间网络编码的高效DTMSN广播传输机制I²NCBT (intra-flow and inter-flow network coding broadcast transmission)；为降低开销, 提出一种基于二进制位运算的ONC包构建算法.理论分析和仿真实验证明, I²NCBT比NBT和NEBT能进一步减小广播时延和网络负载.

1 基于流内与流间网络编码的广播

I²NCBT在不同时机和不同位置使用不同编码技术, 共同完成汇聚节点向传感器节点广播数据的任务, 本节分别介绍基于2种编码技术的广播, 并定性分析I²NCBT的开销.

1.1 基于RLNC的广播

在I²NCBT中, 当汇聚节点生成原始广播数据时, 首先依据数据大小将其分成L个批次数据段, 然后再将每个批次数据段X等分成m个原始数据, 即X=[X₁ X₂ … X_m]^T, 其中X_i对应伽罗瓦域GF(2^K)上的一个n维向量[x_i1 x_i2 … x_in].当有转发机会时, 汇聚节点随机选取编码向量g_i=[g_i1 g_i2 … g_im] (g_ij∈GF(2^K)), 并按式(1) 得到编码包Y_i, 然后将Y_i转发给通信范围内的传感器节点.

$\begin{array}{c} {\mathit{\boldsymbol{Y}}_i} = {\mathit{\boldsymbol{g}}_i}\mathit{\boldsymbol{X}} = [{y_{i1}}{y_{i2}} \ldots {\rm{ }}{y_{in}}]\\ ({y_{ik}} = \sum\limits_{j = 1}^m {} {g_{ij}}{\mathit{\boldsymbol{X}}_{jk}},{\rm{ }}k = 1,{\rm{ }}2,{\rm{ }} \ldots ,{\rm{ }}n) \end{array}$

(1)

汇聚节点向网络中注入h(h≥m)个线性无关的同一批次数据编码包, 但只有经过Sink节点的传感器节点能收到部分编码包, 然后传感器节点间通过ONC获得同一批次数据的不同编码包.当传感器节点收到任意m个编码包组成的向量Y=[Y₁ Y₂ … Y_m]时, 若其对应的编码矩阵G=[g₁ g₂ … g_m]满秩, 则根据式(2) 解码得出原始数据X.

${\mathit{\boldsymbol{X}}^{\rm{T}}} = {\mathit{\boldsymbol{G}}^{ - 1}}{\mathit{\boldsymbol{Y}}^{\rm{T}}}$

(2)

1.2 基于ONC的广播

首先对比NBT、NEBT和I²NCBT中节点在交换数据时的不同策略, 得出ONC的优势, 然后基于二进制位运算提出优化的ONC包构建算法.

1) ONC收益示例

依据NEBT中节点广播收益的定义^[7]给出节点编码收益定义.假设在没有通信差错的情况下, 节点编码收益是指节点采用ONC方式向其通信范围内其他节点传输广播数据时比其采用单播方式节省的通信开销的量. 2种收益的大小都是用节省传输数据的数量来衡量, 广播收益和编码收益分别用π_B和π_C表示.假设汇聚节点发送同一批次数据的8个线性无关编码包a~h, 传感器节点A、B、C和D分别得到如图 1所示的数据, 示例中节点B和C具体收益如表 1所示.

在表 1中, →表示单播, $ \Rightarrow $表示广播.以节点B为例, 在NBT中需要分别向节点C和D各单播3次和2次数据, 其中数据h是重复转发的；在NEBT中通过广播数据h, 节省一次数据传输, π_B =1；在I²NCBT中通过ONC将数据d和g异或后广播, 又节省一次数据传输, π_C=2.同理, 节点C在NEBT中广播收益π_B =2；在I²NCBT中编码收益π_C =3.

2) 构建ONC编码包

构建ONC编码包是利用ONC实现广播的关键, 目前主要使用散列搜索算法.然而, 该方法存在不合理之处, 并且复杂度较高.为此基于二进制位运算提出一种优化的构建ONC包的算法, 既节省存储空间又具有较低的复杂度.首先描述相关数据结构, 然后设计构建ONC包算法.

① 数据结构.编码构建表(CBT, coding-built table)是一维数组, 数组长度为节点当前拥有的消息数M, 数组元素是结构体{Msg, Val, Num}.其中, Msg是数据；Val是二进制位串, 长度为节点邻居数, 令w_ij是第i个数据的Val值的第j个值, w_ij∈{0, 1}, 则Val生成过程是传感器节点周期性探测邻居节点数据列表l(l仅包含数据的ID), 如果邻居节点N_j已经拥有数据P_i则w_ij=0, 反之w_ij=1；Num记录Val中1的个数, 即需要该数据包的邻居数. 图 2是CBT的一个示例.

② 构建ONC包.在传统散列搜索算法中, 首先依据一个类似Val组成的M×N矩阵计算数据P_i的散列值 ${\rho _i} = \sum\limits_{j = 1}^M {} {2^{j - 1}}{w_{ij}}({\rho _i} \in [0,{\rm{ }}{2^{M - 1}}])$ , 然后构建有序的散列表, 最后计算当前散列值的邻域.散列值ρ_n(n=1, 2, …, M)的邻域 $U = \left\{ {\sum\limits_{j = 1}^N {} {2^{j - 1}}{\lambda _j}} \right\}$ , 其中λ_j∈{0, 1}, ∃λ_j≠0 s.t. j∈{1, 2, …, N} and ∀b_i^j=0, b_i^j(1≤i≤n)是ρ_i的第j比特.该算法优先选择散列值最大的数据编码不一定是最优的, 而应该优先选择被更多邻居节点需要的数据包编码, 如图 2所示, 数据P₇和P₄对应的散列值分别为16 (10000) 和9 (01001), 虽然16>9, 但从二进制值看, P₄被更多邻居需要, 优先编码能获得更大效益.其次, 算法构建的邻域中很多元素在散列表中并未出现, 如图 2所示的例子中, 散列值17, 其邻域U={12, 10, 8, 6, 4, 2}, 而数据的散列值没有12、10和6等元素, 因此没有必要计算邻域中所有元素.为此提出一种基于二进制位运算构建ONC包算法, 如算法1所示.

算法1  构建ONC编码包

SelMsgBits=0, ONCPkts=0;

for (i=1; i < M; i++)

  j=CBT[i~M]中Num最大的元素的下标；

  交换CBT[i]和CBT[j]；

  if (SelMsgBits & CBT[i].Val)==0 then

    SelMsgBits |= CBT [i].Val；

    ONCPkts⊕= CBT [i].Msg；

  end if

end for

算法1的输入是编码构建表CBT[M], 输出是ONC包ONCPkts, 初始值为0. SelMsgBits是二进制串, 用来存储所选数据Val值按位或的结果, 串长度是节点的邻居数.为优化性能, 算法每次从CBT表剩余元素中选择Num值最大的数据进行编码判断.如果SelMsgBits & CBT[i]. Val!=0, 则意味着ONCPkts中已经包含节点v(v∈V, V是需要数据P_i的邻居节点集)需要的一个数据, 再将P_i编入ONCPkts中, 节点v将无法解码；否则, 编码该数据.如图 2所示, 首先选择P₂, SelMsgBits=10001, 再选择P₄时, SelMsgBits & CBT^[4]. Val!=0, 放弃编码, 如此按算法1得ONCPkts=P₂⊕P₆⊕P₃⊕P₁.

1.3 算法开销

本节定性分析NBT、NEBT和I²NCBT的存储开销和计算开销.

1) 存储开销

假设E(M)和E(N)分别是节点数据队列长度和邻居节点数的数学期望, C是I²NCBT和其他2种算法相比的额外存储开销, C的值取决于CBT表中Val和Num的长度和个数. Val是二进制位串, 长度为E(N)；Num也可以用二进制存储, 最大值为Val的长度, 因此Num的长度为 ${\left\lceil {\lg \left( {E\left( N \right) + 1} \right)} \right\rceil }$ ；CBT表元素数为E(M), 则

$C = E\left( M \right)\left( {E\left( N \right) + \left\lceil {\lg \left( {E\left( N \right) + 1} \right)} \right\rceil } \right)$

(3)

由于C是二进制位的个数, 因此即便是最坏情况下, E(M)和E(N)的上限为系统中存在的所有数据数量和除节点自身以外的所有节点数, I²NCBT的空间开销也是一个可以接受的值.

2) 计算开销

3个算法的RLNC广播部分的时间复杂度相同, 因此重点分析和比较编码包在传感器节点间传输时的时间开销. I²NCBT的时间开销主要由生成CBT表和构建ONC包2部分组成.设前者时间复杂度为A₁(见式(4)), 后者的时间复杂度为A₂.

${A_1} = O({\left( {E\left( M \right)} \right)^2}E\left( N \right))$

(4)

事实上, 节点在NBT和NEBT中交换编码包时的时间复杂度和I²NCBT的A₁相同. NBT通过传染病路由(ER, epidemic routing)扩散编码包, 每次只和一个节点通信, 需要将数据列表中所有数据和相遇节点的数据列表比较, 其时间复杂度为O((E(M))²), 当和N个节点相遇时其时间复杂度为A₁. NEBT通过广播机制扩散编码包, 也需要遍历自己的数据队列和每个邻居节点的数据队列, 其时间复杂度也为A₁.

因此, 与NBT、NEBT相比, I²NCBT付出的额外计算开销为A₂, 即算法1的时间复杂度, A₂相当于对CBT[M]进行排序, 即

${A_2} = O\left( {\frac{{E\left( M \right)\left( {E\left( M \right) - 1} \right)}}{2}} \right){\rm{ }}$

(5)

和A₁相比, A₂的计算开销最坏情况下也小于A₁的一半 $\left( {{A_2} < \frac{{{A_1}}}{{2E\left( N \right)}}} \right)$ , 且节点密度越大, 优势越大.

2 仿真实验

基于ONE仿真器实现了DTMSN广播传输.仿真区域大小为100 m×100 m, 网络中有1个汇聚节点和N个传感器节点, 汇聚节点位于区域中心不动, 传感器节点遵循随机路点(RWP, random way-point)移动模型.汇聚节点生成广播数据, 服从参数为λ=0.05的Poisson分布, 网络带宽为2 Mbit/s, 其他仿真参数如表 2所示.

仿真实现了NBT、NEBT和I²NCBT, 并比较了平均广播时延和网络负载, 仿真结果如下.

1) 节点数对广播性能的影响(r=4m, h=8)

如图 3(a)所示, 随节点数增多3种算法的平均广播时延都呈下降趋势.因为区域大小不变, 则节点相遇机会随节点数增多而增大, 导致节点通信更加频繁, 加速了数据传播, 从而减小了广播时延.平均广播时延性能比较：NBT>NEBT>I²NCBT, 因为NEBT和I²NCBT都利用无线信道的广播特性, 节点密度越大, 通信范围内邻居节点数越多, 广播收益越大, 其中I²NCBT的机会网络编码进一步减少通信量, 加速数据传输, 减小广播时延.

图 3(b)显示随节点数增多, 一次广播平均转发编码包数(平均网络负载)也随之增大.因为每个节点都需要得到广播数据的副本, 所以节点数越多需要传输的数据包的数量也越多.网络负载比较结果：NBT>NEBT>I²NCBT.因为NBT是通过单播转发数据的, 所以网络负载受节点数影响较大, 而NEBT和I²NCBT通过广播减少网络负载, 节点密度越大广播性能越好, 其中I²NCBT利用机会网络编码进一步压缩广播数据, 从而减小网络负载.

2) 通信半径对广播性能的影响(N=50, h=8)

如图 4(a)所示, 节点通信半径越大传输时延越小.因为随着通信半径增加节点连通概率增大, 通信机会越多, 所以时延下降.广播时延性能比较结果：NBT>NEBT>I²NCBT.因为NEBT通过广播转发数据而加速数据传播, 而I²NCBT的机会网络编码能进一步加速数据传播, 所以时延较小.

从图 4(b)中得出, NBT的网络负载随节点半径增大而基本不变, 而NEBT和I²NCBT的网络负载随节点半径增大而减小.原因是NBT是基于Epidemic的转发机制, 是一对一的复制, 在节点总数不变时, 网络负载也基本不变. NEBT和I²NCBT利用无线信道的广播特性广播数据, 当通信半径增大时, 通信范围内的邻居节点增多, 极大地提高了广播效率, 有效减少网络负载, 其中I²NCBT的机会编码性能也随邻居数增加而进一步提高.

3) 参数h对广播性能的影响(N=50, r=4 m)

算法X_1(X代表NBT、NEBT或I²NCBT)中, 当传感器节点接收到m (m=8) 个不同编码包后不再接收新的编码包, 算法X_2则无此限制.

由图 5(a)可看出, 随着h的增大, 广播算法的时延都减小.因为h越大, 网络中同一批次不同编码包数越多, 传感器节点得到8个线性无关编码包的机会越大, 时延越小.其中X_2类算法优于X_1类算法, 原因是当节点能接收多于8的编码包时, 加速了编码包传输.

图 5(b)显示了参数h对网络负载的影响. NBT_1的网络负载受h影响不大, 而NEBT_1和I²NCBT_1的网络负载随h的增加而减小.因为每个节点最终接收的数据包固定, 网络中传输数据包总量也是固定的, NBT_1是单播传输, 所以网络负载基本不变, 但是h增大, 系统中不同编码包增多, 传感器节点之间数据相异概率增大, 广播和编码收益增加, 因此NEBT_1和I²NCBT_1的网络负载减小. X_2类算法不限制节点接收数据包数, 因此随h增大, 节点在广播完成之前收到不同编码包数增多, 导致网络负载增大.

3 结束语

面向DTMSN提出了I²NCBT机制.在I²NCBT中, 汇聚节点利用RLNC处理广播数据, 传感器节点之间利用ONC转发RLNC包, 并基于二进制位运算设计了高效ONC包构建算法.理论分析和仿真实验证明, I²NCBT不仅能减小网络负载而且进一步降低了广播时延.下一步工作将建立数学模型, 分析广播性能和其他网络参数, 如节点密度、半径和移动速度等之间的关系.