1.无线传感器网络的数据包传输调度方法,其特征是,包括:
将多信道无线传感器网络进行虚拟化处理,将每一组真实节点、真实接口和真实信道虚拟化为一个元组节点;将一对相邻元组节点之间的链路虚拟化为元组链路;基于虚拟化后的元组节点和元组链路,构建虚拟网络场景;具体包括:如果元组节点(m,i,c)工作就意味着原始节点m使用接口i工作在信道c上,而(m,i,c)和(n,j,c)之间的元组链路工作就意味着在本时隙节点m使用接口i在信道c上向节点n发送数据,而节点n使用接口j在信道c上来接收数据,采用元组链路将元组节点进行连接;虚拟化后,网络中的元组链路构成的集合为L,元组节点构成的集合为N;
在虚拟网络场景中,假设共有S个元组数据源节点,每个元组数据源节点s到元组目的节点之间有I(s)条传输路径;定义 为路径指示变量,若元组数据源节点s的路径i经过元组链路l,则有 否则 假设As(n)表示在时隙n由元组数据源节点s产生的发往元组目的节点的数据包个数;As(n)是关于时隙独立同分布的,且均值为λs;[λ1,...,λS]构成输入负载向量;
元组链路是相邻元组节点之间的链路,只有一跳,路径是源节点到目的节点的传输路径,包括多跳;
定义时隙n到达链路l的数据包个数Al(n)为:
其中,Tsi(n)表示在时隙n中虚拟源数据节点s分配至路径i的数据包个数占As(n)的比例;当有数据包到达元组链路l时,依据“先进先出”原则排队,构成n时隙的元组链路的队列长度ql(n);令rl表示元组链路l的容量;根据调度策略的输出结果,指示变量 表示元组链路l在n时隙是否发送数据,若l被调度且ql(n)>0,则 否则,定义元组链路的队列更新表达式为:
其中,[]+为[0,+∞)上的投影,ql(n)表示构成n时隙的元组链路的队列长度,ql(n+1)表示构成n+1时隙的元组链路的队列长度,Al(n)表示时隙n到达链路l的数据包个数, 表示指示变量,rl表示元组链路l的容量,As(n)表示在时隙n由元组数据源节点s产生的发往元组目的节点的数据包个数, 为路径指示变量;
为每一条元组链路l定义一个干扰集εl,干扰集εl包含了所有可能对l产生干扰的元组链路;干扰集包含信道干扰和接口冲突的所有情况;假设干扰集εl中在同一时隙无干扰发送数据的元组链路的个数称为元组链路l的干扰度,那么将一个网络的整体干扰度定义为所有元组链路的干扰度的最大值,用符号K来表示;
假设当输入负载向量[λ1,...,λS]位于区域Ω内部时存在一个调度策略使得网络保持队列稳定状态,则称Ω为最大吞吐量容量区域;
采用多路径场景,最大吞吐量容量区域Ω定义为所有满足如下条件的输入负载[λ1,...,λS]组成的集合:其中,Λ为单路径环境下的最大容量区域;那么,如果一个调度策略实现的容量区域为kΩ,则称调度策略是吞吐量保证的,且吞吐量效率比为k,0<k≤1;
每对元组数据源节点到元组目的节点之间具有多条传输路径;
元组数据源节点生成待传输数据包,元组数据源节点根据数据流量分配机制,将待传输数据包分配给不同的传输路径;具体包括:在每一个时隙n内,当元组数据源节点s有数据包要发送时,先计算得到数据包分配比例向量:其中,向量 中的各元素表示元组数据源节点s向每条传输路径发送数据包的概率;
然后,元组数据源节点s在时隙n依概率Tsi(n)向路径i发送数据包;
所述数据包分配比例向量,具体计算过程包括:
其中,φs和ν均为正常数,解决公式(4)的问题之后,得到数据包分配比例向量每一条传输路径上的元组链路使用随机接入的调度策略,实现待传输数据包的分组转发,转发给下一跳元组节点,最终实现将待传输数据包转发给元组目的节点;具体包括:将时隙n的时间长度平均分割为两个部分:计算时隙和传输时隙;
将计算时隙进一步平均分为M个子时隙;
每条元组链路在M个子时隙中选择一个子时隙作为数据传输的起始时刻,具体包括:在每个时隙n,每条元组链路l在子时隙集合{1,...,M+1}中依概率对子时隙进行选择,概率的计算公式为:其中,Yl表示元组链路l选择的子时隙;
参数ψl的计算过程为:
其中,α=lnM;
采用一种基于元组的数学模型,将节点、接口、信道模型化为元组节点,并将一对元组节点之间的链路模型化为元组链路,使得多接口多信道网络虚拟化为单信道网络;当网络中元组数据源节点到元组目的节点有多条传输路径时,调度方案首先将每个时隙的数据流量分配至每条路径上,并在MAC调度阶段采用一种基于随机接入的调度策略来完成分组转发,所述调度策略为M‑Scheduler;
通过使用李雅普诺夫分析法,证明M‑Scheduler是吞吐量保证的;使用M‑Scheduler策略后,对于任意正常数μ>0,如果输入负载向量 满足那么网络系统能够保持队列稳定状态;
如果网络系统的干扰度为K,若 满足
则输入负载向量 位于最大吞吐量容量区域Ω的内部,且对每条元组链
路j均成立;当μ足够小且M足够大时,
即M‑Scheduler策略的吞吐量效率比接近1/K;即M‑Scheduler在 时保证网络系统的队列稳定状态,即它是吞吐量保证的;子时隙的数量M的值越大,M‑Scheduler的吞吐量效率比就越接近1/K;
所述M‑Scheduler策略采用的是分布式实现机制,不需要执行最大匹配过程,且不需要迭代运算,每条链路在每个时隙依概率自行选择数据发送时间戳。
2.如权利要求1所述的无线传感器网络的数据包传输调度方法,其特征是,所述方法还包括:若元组链路l选择了子时隙M+1,则元组链路l在当前时隙不发送数据;如果两条相互干扰的邻居元组链路选择了同一子时隙,那么两条相互干扰的邻居元组链路在当前时隙都不发送数据;如果元组链路l在准备发送数据时,监听到元组链路l所归属的干扰集中有其他元组链路正在工作,那么元组链路l将在当前时隙保持静默。
3.无线传感器网络的数据包传输调度系统,其特征是,包括:
虚拟化模块,其被配置为:将多信道无线传感器网络进行虚拟化处理,将每一组真实节点、真实接口和真实信道虚拟化为一个元组节点;将一对相邻元组节点之间的链路虚拟化为元组链路;基于虚拟化后的元组节点和元组链路,构建虚拟网络场景;具体包括:如果元组节点(m,i,c)工作就意味着原始节点m使用接口i工作在信道c上,而(m,i,c)和(n,j,c)之间的元组链路工作就意味着在本时隙节点m使用接口i在信道c上向节点n发送数据,而节点n使用接口j在信道c上来接收数据,采用元组链路将元组节点进行连接;虚拟化后,网络中的元组链路构成的集合为L,元组节点构成的集合为N;
在虚拟网络场景中,假设共有S个元组数据源节点,每个元组数据源节点s到元组目的节点之间有I(s)条传输路径;定义 为路径指示变量,若元组数据源节点s的路径i经过元组链路l,则有 否则 假设As(n)表示在时隙n由元组数据源节点s产生的发往元组目的节点的数据包个数;As(n)是关于时隙独立同分布的,且均值为λs;[λ1,...,λS]构成输入负载向量;
元组链路是相邻元组节点之间的链路,只有一跳,路径是源节点到目的节点的传输路径,包括多跳;
定义时隙n到达链路l的数据包个数Al(n)为:
其中,Tsi(n)表示在时隙n中虚拟源数据节点s分配至路径i的数据包个数占As(n)的比例;当有数据包到达元组链路l时,依据“先进先出”原则排队,构成n时隙的元组链路的队列长度ql(n);令rl表示元组链路l的容量;根据调度策略的输出结果,指示变量 表示元组链路l在n时隙是否发送数据,若l被调度且ql(n)>0,则 否则,定义元组链路的队列更新表达式为:
其中,[]+为[0,+∞)上的投影,ql(n)表示构成n时隙的元组链路的队列长度,ql(n+1)表示构成n+1时隙的元组链路的队列长度,Al(n)表示时隙n到达链路l的数据包个数, 表示指示变量,rl表示元组链路l的容量,As(n)表示在时隙n由元组数据源节点s产生的发往元组目的节点的数据包个数, 为路径指示变量;
为每一条元组链路l定义一个干扰集εl,干扰集εl包含了所有可能对l产生干扰的元组链路;干扰集包含信道干扰和接口冲突的所有情况;假设干扰集εl中在同一时隙无干扰发送数据的元组链路的个数称为元组链路l的干扰度,那么将一个网络的整体干扰度定义为所有元组链路的干扰度的最大值,用符号K来表示;
假设当输入负载向量[λ1,...,λS]位于区域Ω内部时存在一个调度策略使得网络保持队列稳定状态,则称Ω为最大吞吐量容量区域;
采用多路径场景,最大吞吐量容量区域Ω定义为所有满足如下条件的输入负载[λ1,...,λS]组成的集合:其中,Λ为单路径环境下的最大容量区域;那么,如果一个调度策略实现的容量区域为kΩ,则称调度策略是吞吐量保证的,且吞吐量效率比为k,0<k≤1;
路径分配模块,其被配置为:每对元组数据源节点到元组目的节点之间具有多条传输路径;
元组数据源节点生成待传输数据包,元组数据源节点根据数据流量分配机制,将待传输数据包分配给不同的传输路径;具体包括:在每一个时隙n内,当元组数据源节点s有数据包要发送时,先计算得到数据包分配比例向量:其中,向量 中的各元素表示元组数据源节点s向每条传输路径发送数据包的概率;
然后,元组数据源节点s在时隙n依概率Tsi(n)向路径i发送数据包;
所述数据包分配比例向量,具体计算过程包括:
其中,φs和ν均为正常数,解决公式(4)的问题之后,得到数据包分配比例向量分组转发模块,其被配置为:每一条传输路径上的元组链路使用随机接入的调度策略,实现待传输数据包的分组转发,转发给下一跳元组节点,最终实现将待传输数据包转发给元组目的节点;具体包括:将时隙n的时间长度平均分割为两个部分:计算时隙和传输时隙;
将计算时隙进一步平均分为M个子时隙;
每条元组链路在M个子时隙中选择一个子时隙作为数据传输的起始时刻,具体包括:在每个时隙n,每条元组链路l在子时隙集合{1,...,M+1}中依概率对子时隙进行选择,概率的计算公式为:其中,Yl表示元组链路l选择的子时隙;
参数ψl的计算过程为:
其中,α=lnM;
采用一种基于元组的数学模型,将节点、接口、信道模型化为元组节点,并将一对元组节点之间的链路模型化为元组链路,使得多接口多信道网络虚拟化为单信道网络;当网络中元组数据源节点到元组目的节点有多条传输路径时,调度方案首先将每个时隙的数据流量分配至每条路径上,并在MAC调度阶段采用一种基于随机接入的调度策略来完成分组转发,所述调度策略为M‑Scheduler;
通过使用李雅普诺夫分析法,证明M‑Scheduler是吞吐量保证的;使用M‑Scheduler策略后,对于任意正常数μ>0,如果输入负载向量 满足那么网络系统能够保持队列稳定状态;
如果网络系统的干扰度为K,若 满足
则输入负载向量 位于最大吞吐量容量区域Ω的内部,且对每条元组链
路j均成立;当μ足够小且M足够大时,
即M‑Scheduler策略的吞吐量效率比接近1/K;即M‑Scheduler在 时保证网络系统的队列稳定状态,即它是吞吐量保证的;子时隙的数量M的值越大,M‑Scheduler的吞吐量效率比就越接近1/K;
所述M‑Scheduler策略采用的是分布式实现机制,不需要执行最大匹配过程,且不需要迭代运算,每条链路在每个时隙依概率自行选择数据发送时间戳。