基于分层网络拓扑实现分布式的近似理想LT编码的方法

摘要

本发明公开一种基于分层网络拓扑实现分布式的近似理想LT编码的方法：（1）源端把k个数据包广播给各基站；（2）各基站随机选取一个数据包向各第一层中继节点进行广播；（3）各第一层中继节点随机选取一个接收到的数据包：若其已接收过此新数据包或其缓存已满，则丢弃，否则将此新数据包存于缓存中；（4）当各第一层中继节点的缓存中有≥R个数据包时，各第一层中继节点随机选择其中d个数据包异或，并向各第二层中继节点广播异或后的数据包，同时在缓存中删除这d个数据包；（5）各第二层中继节点随机选择两个数据包异或或选取其中一个向接收端发送；（6）接收端对接收到的数据包解码。若成功解码，则结束编码；否则，返回执行步骤（2）。

主权项

1.一种基于分层网络拓扑实现分布式的近似理想LT编码的方法，其特征是：所述分层网络拓扑包括一个源端，一个以上基站、一个以上第一层中继节点、一个以上第二层中继节点和一个接收端；对所述分层网络进行分布式的近似理想LT码编码包括如下步骤：（1）源端把需要发送的k个大小相同的数据包广播给各个基站，其中k>0；（2）各基站把收到的k个数据包进行编号，然后各基站从k个数据包中随机选择一个数据包向各第一层中继节点进行广播；（3）各第一层中继节点判断缓存中是否存在已接收数据包，若不存在，则从接收到的新数据包中随机选择由其中一个基站所发送的新数据包存到缓存中；若存在，则将接收到的新数据包与缓存中的所述已接收数据包进行比对，若第一层中继节点已接收过此新数据包或者其缓存已被占满，则丢弃此新数据包；否则，将此新数据包存储于其缓存中；（4）当每一个第一层中继节点的缓存中所存储的数据包的个数≥R时，则以概率p选择弱化度分布Ω(d)或以概率1‐p选择弱化度分布u’(d)，各第一层中继节点再从各自的缓存中随机选择d个数据包进行异或，并且，根据所选择的弱化度分布是Ω(d)还是u’(d)，在异或后的数据包头部中置相应的标志位进行相应标示；然后各第一层中继节点向各第二层中继节点广播异或后的数据包，同时在缓存中删除这d个数据包；其中，$R=\frac{k}{c·\ln (k/\delta )·\sqrt{k}}---\left(1\right)$$u\left(d\right)=\left\{\begin{array}{cc}0,& d=1\\ \frac{\rho \left(d\right)+\tau \left(d\right)}{{\beta }^{\text{'}}},& 2\le d\le R-1\\ \frac{\rho \left(d\right)}{{\beta }^{\text{'}}},& R\le d\le k\end{array}---\left(3\right)\right.$$\rho \left(d\right)=\left\{\begin{array}{cc}1/k,& d=1\\ 1/\left(d(d-1)\right),& 2\le d\le k\end{array}\right.---\left(5\right)$$\beta ={\Sigma }_{d=1}^k(\rho \left(d\right)+\tau \left(d\right))---\left(7\right)$${\beta }^{\text{'}}={\Sigma }_{d=2}^k\rho \left(d\right)+{\Sigma }_{d=2}^{R-1}\tau \left(d\right)---\left(8\right)$$p=\sqrt{\frac{{\beta }^{\text{'}}}{\beta }}---\left(9\right)$以上各式中，δ是预设当接收端收到个数据包后解码失败的概率，δ≤1，c是大于0的常数，d表示度数，0<d≤k；（5）各第二层中继节点在接收到的数据包中随机选择两个数据包，若所选择的两个数据包的弱化度分布都是Ω(d)，则将该两个数据包进行异或后再向接收端发送；若所选择的两个数据包中的其中一个的弱化度分布是Ω(d)，另一个的弱化度分布是u’(d)，则选择弱化度分布是u’(d)的数据包向接收端发送；若所选择的两个数据包的弱化度分布都是u’(d)，则随机选择其中一个数据包向接收端发送；（6）接收端将从第二层中继节点接收到的数据包进行解码，若成功解码，则通知源端结束编码过程；否则，返回执行步骤（2）。