一种基于凸包收敛算法的组播策略路由方案

摘要

一种基于凸包收敛算法的组播策略路由方案，首先将无线数据中心中参加组播的节点抽象成为一张随机分布的图，每个节点的行为均会反馈信息给控制中心并且接收来自控制中心的命令；其次，将数据中心节点的行为信息抽象成为一簇数据集，最后，在控制中心以凸包收敛算法计算出每个饱和节点的权重，然后根据各个节点的权重决策下一步广播数据的节点以及其广播速率，本发明以饱和节点到所有参与组播的外围节点的传输方向作为优先方向，组播在整体上倾向于使得外围节点先达到饱和，因为当所有外围节点完全接收完数据后，其所包围的内部节点自然也会完全接收到所有数据，与其他算法，能够有效地降低组播传输的时延、提高组播的吞吐量和提高传输的鲁棒性。

主权项

一种基于凸包收敛算法的组播策略路由方案，其特征在于：首先，将无线数据中心中参加组播的节点抽象成为一张随机分布的图，每个节点的行为均会反馈信息给控制中心并且接收来自控制中心的命令；其次，将数据中心节点的行为信息抽象成为以下一簇数据集：G＝{g_i}——参与组播的节点集合，即目标节点集合，g_i是参与组播的节点，即目标节点；S＝{s_i}——已经接收到所有数据的节点集合，即饱和节点集合，s_i是接收到所有数据的节点，即饱和节点；F＝{f_i}——要广播数据的节点集合，其中要广播数据的节点必须是饱和节点，其中f_i是要广播数据的节点；R＝{r_i}——数据中心中可供节点发送的速率集合，r_i是可供节点发送的速率；N(f,r)——要广播数据的节点f以速率r所能传播到的节点集合；A＝{F,R,Δt}——在时间段Δt内，所有要广播数据的节点和其选择的广播速率的集合；p_i,j(r_i)——节点i向节点j以速率r_i传输数据，能够到达节点j的数据占节点i所传的所有数据的比率，记为收包率；最后，在控制中心以凸包收敛算法计算出每个饱和节点的权重E，然后根据各个节点的权重E决策下一步广播数据的节点以及其广播速率；所述凸包收敛算法过程如下：步骤(1)在所有参与组播的未饱和的目标节点集合Q中，找到包围Q的所有外围节点，具体包括:步骤(1.1)逐行扫描所有未饱和的目标节点的集合Q，把每一行中最左边和最后边的节点加入到集合Q₁中；步骤(1.2)逐列扫描集合Q₁中的节点，把每一列中最上方的点和最下方的节点加入到集合Q₂中；步骤(1.3)利用葛立恒扫描(Graham's Scan)凸包计算算法，最终得到当前时间内的能够包围所有参与组播的未饱和的目标节点的凸包节点；步骤(2)计算每一个饱和节点和所有凸包节点的方向矢量其中s(x_s,y_s)为该饱和节点坐标，为第i个凸包节点的坐标；步骤(3)计算每一个饱和节点以每个速率r_i向其所能广播的节点的方向向量其中s(x_s,y_s)为该饱和节点坐标，d(x_d,y_d)为其所能广播到的邻居节点坐标；步骤(4)计算在上的投影与收包率的乘积，再除以目标节点的饱和度，得到邻居节点在一个凸包方向上的权重v(s,d,r,q_i)，该步骤中，凸包方向指饱和节点到凸包节点的方向，目标节点指饱和节点的所有未饱和邻居节点；$v(s,d,r,q_i)=\left(p_{i,j}\right(r)/(1-D\left(d\right)\left)\right)gmax\{{\alpha }_i\left(d\right)\overrightarrow{D}(s,d)\times {\beta }_i\times \overrightarrow{M_l},0\}$其中是目标节点与要发送数据的饱和节点，即源节点的单位方向向量，是源节点的一个凸包方向向量，如果与反向，即说明该目标节点不利于该外围节点优先接收到数据，则置v(s,d,r,q_i)＝0，p_i,j(r)是关于饱和节点i和目标节点j的距离的反比函数，距离越近，p_i,j(r)越大，反之越小，目标节点的优先级与其已经接收的数据成正比：其接受的数据越多，越容易成为饱和节点，越容易获得向其邻居节点发送数据的资格，α_i(d)为常数，作为平衡因子，一般取值10～15，β_i是饱和节点到所有凸包节点的最近距离；步骤(5)根据步骤(4)计算饱和节点的一个邻居节点在所有凸包方向上的权重之和其中Q*为所有凸包节点的集合；步骤(6)根据步骤(5)计算一个饱和节点所有邻居节点在所有凸包方向上的权重之和，记为饱和节点权重E，其中N(s,r)是未饱和节点s以速率r发送数据所覆盖的所有邻居节点的集合；步骤(7)根据步骤(6)，算出每一个饱和节点的权重，在任意两个饱和节点的干扰范围互相不重合的情况下，按照权重由大到小的顺序选择要发送数据的饱和节点和其发送速率，加入到A＝{F,R,Δt}中；步骤(8)控制中心根据步骤(7)所得到的集合A＝{F,R,Δt}向所有要发送数据的节点下发发送命令，所有受到命令的节点进行数据发送；步骤(9)所有受到命令的节点数据发送完毕后，按照步骤(2)～(8)继续选择下一步要广播的节点，直到所有参与组播的节点全部接收完数据为止。