法律状态公告日
法律状态信息
法律状态
2016-12-21
未缴年费专利权终止 IPC(主分类):H04L12/701 授权公告日:20150325 终止日期:20151027 申请日:20121027
专利权的终止
2015-03-25
授权
授权
2013-06-26
实质审查的生效 IPC(主分类):H04W16/10 申请日:20121027
实质审查的生效
2013-05-29
公开
公开
技术领域
本发明属于无线网络技术领域,涉及一种认知无线Mesh网络中以高可靠与低延迟为目标的分布式路由与频谱分配方法。
背景技术
认知无线电(cognitive radio, CR)技术可以有效提高频谱资源的利用率,以及缓解无线通信系统频谱缺乏的问题。认知无线Mesh网络(cognitive wireless mesh network, CWMN)是结合了CR的无线Mesh网络,具有智能的无线频谱资源共享能力和重配置能力,每个Mesh节点都使用CR技术,对于每个配备CR的Mesh节点(CR-Mesh路由器、CR-Mesh网关、CR-Mesh终端),能够感知主系统中未使用的频谱,并动态地接入到这些可用的频谱。
本发明主要考虑CR-Mesh节点已经获得可用信道条件下的以高可靠与低延迟为目标的分布式路由与频谱分配方法。
在认知无线Mesh网络环境中,CR-Mesh节点动态的接入主用户(primary users, PU)未使用的频谱,由于PU占用授权信道的随机性,因此,不仅CR-Mesh节点感知的可用信道集合存在异构,而且各感知的可用信道本身也存在异构,各信道本身的异构特性主要包括信道延迟、信道稳定度、以及信道使用概率等,其中,信道稳定度、以及信道使用概率等属于信道的使用特性,主要由PU的行为、以及CR-Mesh节点所处的位置决定。
由于各CR-Mesh节点可用信道具有异构性,CWMN中构造的路由路径由于PU占有授权信道而被迫中断,针对这种情况,本发明提出一种CWMN中高可靠、低端到端延迟的基于动态规划策略的分布式路由路径构建方法。经查阅相关文献,未见有关针对认知无线Mesh网络中基于动态规划的以高可靠与低延迟为目标的分布式路由与频谱分配问题的报道。
鉴于以上考虑,本发明提供了一种认知无线Mesh网络中基于动态规划的以高可靠与低延迟为目标的分布式路由与频谱分配方法。
发明内容
本发明所要解决的技术问题是提供一种认知无线Mesh网络中基于动态规划的高可靠与低延迟分布式路由与频谱分配方法,通过有效的构造路由路径与频谱分配,达到提高路由路径可靠度和降低路径端到端延迟的目标。
发明的技术解决方案如下:
我们将静止的CR-Mesh节点组成的CWMN建模为一个无向图 ,其中表示CR-Mesh节点的集合,其中表示CR-Mesh网关节点集合,表示CR-Mesh路由器节点集合,表示CR-Mesh终端节点集合。表示链接两个能相互通信的CR-Mesh节点的无线链路的集合,两个CR-Mesh节点能相互通信的前提是两个CR-Mesh节点必须至少具有一个相同的可用信道,并且满足通信距离的约束,以及认知射频接口数约束。当前网络环境,可用信道的集合,信道的延迟用表示,一般情况下,不同信道具有不同的延迟,即,。每个节点都有一个感知的可用信道集合。每个节点均存在一个通信距离和一个干扰距离,本发明。
认知无线Mesh网络中基于动态规划的高可靠低延迟的分布式路由路径构造与频谱分配问题即:无线业务数据从CR-Mesh网关节点流行CR-Mesh终端节点,即给定无线业务,其中表示CR-Mesh网关节点,即为源点,表示CR-Mesh终端节点,即为目的节点,其目标是构造从到的高可靠低延迟路由路径,具体体现在,对于路由路径中所有无线链路分配的信道,最大化其可靠度,最小化其端到端延迟。
表示给无线链路分配的信道为,表示没有给无线链路分配信道。所有节点采用半双工方式工作,存在一个公共控制通道(common control channel,CCC)用于各CR-Mesh节点之间传递控制信息。
本发明构造路由路径与频谱分配的目标是最大化路由路径中所有无线链路分配的信道的可靠度,以及最小化其端到端延迟。
本发明提出的基于动态规划的高可靠、低延迟的分布式路由路径构造与频谱分配方法的步骤如下:
⒈计算所有CR-Mesh节点的状态信息,以及其可用信道的效用值,主要包括CR-Mesh节点的与其相邻节点的相同可用信道集合,各可用信道的使用特性,以及具有相同可用信道集合的邻居节点集合,具体包含以下步骤。
ⅰ)所有CR-Mesh节点对其感知的信道集合,计算其所有可用信道的使用特性,包括信道的使用概率和稳定度,即,计算 ,,。
使用概率的计算原理是:表示节点感知的信道被PU使用的概率。节点从开始统计信道是否被授权PU使用,每次使用固定检测时间周期,表示信道被授权PU使用,表示信道没有被授权PU使用,表示到目前为止,节点已经检测了个时间周期,表示个时间周期中,信道被授权PU使用的次数。
稳定度的计算原理是:表示节点感知的信道由“空闲”状态变成“使用”状态的次数占总检测时间周期的比例。表示信道从到,是否由变成,即信道是否由“空闲”状态变成“使用”状态,表示信道由“空闲”状态变成“使用”状态,其他情况,由“空闲”变“空闲”状态,“使用”变“空闲”状态,“使用”变“使用”状态,都记。其中(令),表示个检测时间周期中信道由“空闲”状态变成“使用”状态的总次数。
ⅱ)所有节点通过公共控制通道(CCC)向其相邻节点发送感知的可用信道集合,以及各可用信道使用特性值,包括信道的使用概率和稳定度,即,发送,以及,发送一个三元组(,,)。其中,节点的相邻节点表示通信距离范围之内的节点,不同于ⅳ)中求解的的邻居节点。
ⅲ)所有节点计算其与相邻节点的相同可用信道集合,以及各相同可用信道的使用特性,表示节点和节点相同可用信道集合,即。节点和节点相同可用信道的使用概率,和相同可用信道的稳定度,分别取节点和节点的使用概率和的最大值,和稳定度和的最小值,即,。
ⅳ)所有节点计算其邻居节点集合,即,。其中表示节点和节点之间的物理距离小于通信距离。表示节点和节点之间至少存在一个相同的可用信道。
⒉计算CR-Mesh网关节点到所有CR-Mesh路由器节点和CR-Mesh终端节点的层次,因为相对于不同的CR-Mesh网关节点来说,CR-Mesh路由器和终端节点所处的层次是不同的。对于CR-Mesh网关、路由器和终端节点,其处理流程是不一样的,下面分别说明其包含的步骤。
网关节点,其处理流程如下:
ⅰ)对所有CR-Mesh网关节点,,表示所有的网关节点都设置为0层。
ⅱ)对所有CR-Mesh网关节点,通过公共控制通道(CCC)广播一个消息,其中表示网关的层为0。
路由器节点,其处理流程如下:
ⅰ)对所有CR-Mesh路由器节点,初始化,表示相对于网关来说,节点所处的层次。初始化所有网关节点到节点的层次为无穷大,即,,。
ⅱ)对所有CR-Mesh路由器节点,当收到一个的消息时,判断是否大于,如果,则,否则,不改变。
ⅲ)对所有CR-Mesh路由器节点,广播一个消息,其中。
终端节点,其处理流程如下:
ⅰ)对所有CR-Mesh终端节点,初始化,表示相对于网关来说,节点所处的层次。初始化所有网关节点到节点的层次为无穷大,即,,。
ⅱ)对所有CR-Mesh终端节点,当收到一个的消息时,判断是否大于,如果,则,否则,不改变。
⒊计算所有CR-Mesh节点的父亲节点的集合和儿子节点的集合,因为相对于不同的CR-Mesh网关节点来说,CR-Mesh路由器和终端节点所处的父亲和儿子节点集合是不同的。具体包含以下步骤:
ⅰ) 对所有CR-Mesh节点,针对每个网关节点,使用公共控制通道(CCC)广播一个消息给其所有的邻居节点集合中的所有节点,共广播个消息,。消息表示从网关节点到节点的层次为,其中,为之前计算的相对于网关来说,节点所处的层次。
ⅱ) 对所有CR-Mesh节点,当收到一个消息时,比较与消息中的值之间的关系,如果,则=,表示相对于网关来说,节点的父亲节点集合,如果,则=,表示相对于网关来说,节点的儿子节点集合。
⒋计算所有节点与其儿子节点之间的无线链路预分配某信道之后的权值。
对所有CR-Mesh节点,计算无线链路预分配信道之后的权值,其中是相对于网关节点来说,节点的儿子节点,即,。由于的值与网关节点无关,因此的计算公式中不于标明网关节点,的计算公示为: ,。
其中,与分别表示节点和节点之间相同可用信道的使用概率和稳定度,表示信道的延迟,表示当前网络环境中,所有信道的最大延迟。
除以的目的是为了将延迟归一化。权值函数包含了本发明追求的目标:高的路径可靠度,低的端到端延迟,表示可靠度,表示延迟,由于我们希望的值越小越好,因此在中,对可靠度取倒数。对无线业务构造的路由路径,要想获得高可靠度、低延迟的路由路径,需要尽量使得路径经过的每一条无线链路具有高可靠度、低的端到端延迟。
⒌基于动态规划(Dynamic Programming, DP)策略采用分布式方式构建从源点到目的节点的高可靠、低延迟的路由路径,为无线业务,其中表示CR-Mesh网关节点,即为源点,表示CR-Mesh终端节点,即为目的节点。对于CR-Mesh网关、路由器和终端节点,其工作流程是不一样的,下面分别说明其包含的步骤。
终端节点,其处理流程如下:
ⅰ)计算终端节点到自己使用信道的路径最小权值总和,即,其计算公式为: 。
ⅱ)对终端节点的每一个父亲节点,构造并发送一个消息,含义是:当网关节点是,终端节点是的情况下,终端节点发送给的控制消息。
其中表示到的路径最小权值总和。表示到其儿子节点所使用的信道,表示取最小值时,与相连的儿子节点,其值分别是:
,表示最小权值总和为0;
,由于没有儿子节点,即表示没有给其分配信道;
,表示节点没有儿子节点。
路由器节点,其处理流程如下:
ⅰ) 当路由器节点接收到其儿子节点的消息的时候,对节点的每一个可用信道(),计算节点与其儿子节点之间的无线链路分配信道的情况下,路由器节点到终端节点的路径最小权值总和,即,其计算公式为:。
其中,表示无线链路预分配信道之后的权值,表示相对于网关,的所有儿子节点,表示到的最小权值总和,其中表示到其儿子节点使用的信道,即。
公式的含义为:对于,寻找最小的值。
ⅱ)对路由器节点的每一个可用信道(),计算取最小值时的儿子节点,以及与其儿子节点使用信道。其计算公式为:(,) 。
ⅲ)对路由器节点的每一个可用信道(),保存一个三元组,其中表示信道,表示计算取最小值时的儿子节点,表示节点到其儿子节点使用的信道。,,。
ⅳ) 对路由器节点的每一个可用信道(),构造一个消息,给的每一个父亲节点发送一个消息。
的含义是:当网关节点是,终端节点是的情况下,节点发送给的控制消息,其中表示到的路径权值总和,表示到其儿子节点所使用的信道,表示取最小值时,与相连的儿子节点,其值分别是:
表示经过其儿子节点到终端节点是的权值总和;
,表示与其儿子节点之间的无线链路分配的信道;
,表示取最小值时,与相连的儿子节点。
网关节点,其处理流程如下:
ⅰ) 当网关节点接收到其儿子节点的消息的时候,网关节点计算其到终端节点的路径最小权值总和,即,其计算公式为: 。
其中,表示无线链路预分配信道之后的权值,表示相对于网关,的所有儿子节点,表示到其儿子节点使用信道的情况下,到的路径权值总和。
公式的含义为:对于,寻找最小的值。
ⅱ)计算的路径中与相连接的节点,无线链路分配的信道,以及与其儿子节点使用信道,其计算公式为:(,,)。
其中,表示取得最小值时选择的的儿子节点,表示取得最小值时无线链路选择使用的信道,表示取得最小值时,到其儿子节点使用信道。表示计算取得最小值时选择的的儿子节点,以及与儿子节点之间使用的信道。
⒍给构造的路由路径中的所有无线链路分配信道。
ⅰ)网关节点根据公式(,,)获得取得最优值的儿子节点, 与其儿子节点使用的信道,以及到其儿子节点使用信道,即。
ⅱ)网关节点给节点儿子节点发送一个控制消息,其中表示到其儿子节点使用信道。 其中。
ⅲ)路由器节点收到其父亲节点的消息之后,在本地的三元组中寻找与消息中的相等的三元组,即。
ⅳ) 节点到其儿子节点之间的无线链路分配信道,即,路由器节点给其儿子节点发送一个控制消息,其中表示到其儿子节点使用信道,。
有益效果:
本发明解决了认知无线Mesh网络中以高可靠与低延迟为目标的分布式路由路径构造与频谱分配问题,不仅分布式构造路由路径,并且还可以到达构建的路由路径具有高可靠度、低端到端延迟的目标。
下面结合附图对本发明作进一步的详细描述。
附图说明
图1是本发明认知无线Mesh网络模型的示意图;
图2是本发明基于DP的分布式组播路由与频谱分配的流程图;
图3是本发明计算节的状态信息与可用信道效用值的流程图;
图4是本发明CR-Mesh路由器R3感知的信道被PU占用图;
图5是本发明计算CR-Mesh网关节点到CR-Mesh节点层次的流程图;
图6是本发明基于DP的分布式组播路由路径构造的流程图;
图7是本发明给构造的路由路径分配信道的流程图;
具体实施方式
以下将结合附图和具体实施例对本发明做进一步详细说明:
实施例1:
本实施例中,图1所示为认知无线Mesh网络模型的示意图,分布着21个CR-Mesh节点(其中包括2个CR-Mesh网关节点,G1和G2,14个CR-Mesh路由器节点, ,5个CR-Mesh终端节点,)。图中R3{2,4,5}/4表示CR-Mesh路由器节点R3 感知的可用信道为{2,4,5},可用的射频接口数为4,即K3=3,I3=3。其他CR-Mesh节点的感知的可用信道集合以及具有的射频接口数如图1所示。5个可用信道的延迟分别是Dy={25,10,15,20,16},单位为ms。
本发明构造组播树与频谱分配的目标是构造具有高可靠与低延迟的路由路径。
图2所示为本发明提出的基于DP的分布式组播路由与频谱分配的流程图,步骤如下:
S1-1计算所有CR-Mesh节点的状态信息,以及其可用信道的效用值,主要包括CR-Mesh节点的与其相邻节点的相同可用信道集合,各可用信道的使用特性,以及具有相同可用信道集合的邻居节点集合,流程图如图3所示,具体包含以下步骤:
S2-1所有CR-Mesh节点对其感知的信道集合,计算其所有可用信道的使用特性,包括信道的使用概率和稳定度,即,计算 ,,。
其中,CR-Mesh路由器R3感知的信道被PU占用图如图4所示,其使用概率和稳定度的计算如下。
,,,,; ,,;=3;
=0.4;=0.7。
,,,;,,,;=4;
=0.4;=0.6。
,,;,,;=4;
=0.3;=0.7。
所有CR-Mesh节点的使用概率和稳定度的计算方法与R3一样,只是由于各CR-Mesh节点的位置不同,以及PU占用信道的方式不同而已。其中G1、R2、R3、R4、R7、R10和C4感知的信道的使用概率和稳定度如下所示。
对G1而言,P1(G1)=0.6, P2(G1)=0.4,P4(G1)=0.8; S1(G1)=0.5, S2(G1)=0.7,S4(G1) =0.4。
对R2而言,P2(R2)=0.6, P3(R2)=0.8,P4(R2)=0.4;S2(R2)=0.5, S3(R2)=0.6,S4(R2)=0.6。
对R3而言,P2(R3)=0.4, P3(R3)=0.4,P5(R3)=0.3;S2(R3)=0.7, S3(R3)=0.6,S5(R3)=0.7。
对R4而言,P1(R4)=0.5, P2(R4)=0.8,P3(R4)=0.4;P1(R4)=0.6, P2(R4)=0.3,P3(R4)= 0.8。
对R7而言,P1(R7)=0.6, P2(R7)=0.5,P3(R7)=0.3, P5(R7)=0.4;S1(R7)=0.4, S2(R7)=0.5,
S3(R7)=0.8, S5(R7)=0.7。
对R10而言,P2(R10)=0.5,P3(R10)=0.6,P5(R10)=0.3;S2(R10)=0.7, S3(R10)=0.4,S5(R10)=0.6。
对C4而言,P2(C4)=0.3, P5(C4)=0.5;S2(C4)=0.9, S5(C4)=0.6。
S2-2所有节点通过公共控制通道(CCC)向其相邻节点发送感知的可用信道集合,以及各可用信道使用特性值,包括信道的使用概率和稳定度,即,发送,以及,发送一个三元组(,,)。其中,节点的相邻节点表示通信距离范围之内的节点,不同于ⅳ)中求解的的邻居节点。
S2-3所有节点计算其与相邻节点的相同可用信道集合,以及各相同可用信道的使用特性,表示节点和节点相同可用信道集合,即。节点和节点相同可用信道的使用概率,和相同可用信道的稳定度,分别取节点和节点的使用概率和的最大值,和稳定度和的最小值,即,。
其中,={2},={2,4},={2,3},={2,3},={2,3,5},={2,3,5},={2,5};在相同可用信道的使用概率和稳定度如下所示。
对(G1,R3)而言,Pn2(G1,R3)=0.4;Sn2(G1,R3)=0.7。
对(G1,R2)而言,Pn2(G1,R2)=0.6,Pn4(G1,R2)=0.8;Sn2(G1,R2)=0.5,Sn4(G1,R2)=0.4。
对(R2,R3)而言,Pn2(R2,R3)=0.6,Pn3(R2,R3)=0.8;Sn2(R2,R3)=0.5,Sn3(R2,R3)=0.6。
对(R3,R4)而言,Pn2(R3,R4)=0.8,Pn3(R3,R4)=0.4;Sn2(R3,R4)=0.3,Sn3(R3,R4)=0.6。
对(R3,R7)而言,Pn2(R3,R7)=0.5,Pn3(R3,R7)=0.4,Pn5(R3,R7)=0.4;Sn2(R3,R7)=0.5,
Sn3(R3,R7)=0.6,Sn5(R3,R7)=0.7。
对(R7,R10)而言,Pn2(R7,R10)=0.5,Pn3(R7,R10)=0.6,Pn5(R7,R10)=0.4;Sn2(R7,R10)=0.5,
Sn3(R7,R10)=0.4,Sn5(R7,R10)=0.6。
对(R10,C4)而言,Pn2(R10,C4)=0.5,Pn5(R10,C4)=0.5;Sn2(R10,C4)=0.7,Sn5(R10,C4)=0.6。
S2-4所有节点计算其邻居节点集合,即,。其中表示节点和节点之间的物理距离小于通信距离。表示节点和节点之间至少存在一个相同的可用信道。
S1-2计算CR-Mesh网关节点到所有CR-Mesh路由器节点和CR-Mesh终端节点的层次,因为相对于不同的CR-Mesh网关节点来说,CR-Mesh路由器和终端节点所处的层次是不同的。对于CR-Mesh网关、路由器和终端节点,其处理流程是不一样的,流程图如图5所示,下面分别说明其包含的步骤。
网关节点,其处理流程如下:
S3-1对所有CR-Mesh网关节点,,表示所有的网关节点都设置为0层。
其中,,。
S3-2对所有CR-Mesh网关节点,通过公共控制通道(CCC)广播一个消息,其中表示网关的层为0。
路由器节点,其处理流程如下:
S4-1对所有CR-Mesh路由器节点,初始化,表示相对于网关来说,节点所处的层次。初始化所有网关节点到节点的层次为无穷大,即,,。
对而言,初始化,。
S4-2对所有CR-Mesh路由器节点,当收到一个的消息时,判断是否大于,如果,则,否则,不改变。
S4-3对所有CR-Mesh路由器节点,广播一个消息,其中。
终端节点,其处理流程如下:
S5-1对所有CR-Mesh终端节点,初始化,表示相对于网关来说,节点所处的层次。初始化所有网关节点到节点的层次为无穷大,即,,。
对而言,初始化,。
S5-2对所有CR-Mesh终端节点,当收到一个的消息时,判断是否大于,如果,则,否则,不改变。
经过上述步骤之后,相对G1和G2而言,R2、R3、R4、R7、R10和C4的层次如下所示。
对R2而言,L(G1,R2)=1,L(G2,R2)=3。
对R3而言,L(G1,R3)=1,L(G2,R3)=2。
对R4而言,L(G1,R4)=2,L(G2,R4)=1。
对R7而言,L(G1,R7)=2,L(G2,R7)=2。
对R10而言,L(G1,R10)=3,L(G2,R10)=3。
对C4而言,L(G1,C4)=4,L(G2,C4)=4。
S1-3计算所有CR-Mesh节点的父亲节点的集合和儿子节点的集合,因为相对于不同的CR-Mesh网关节点来说,CR-Mesh路由器和终端节点所处的父亲和儿子节点集合是不同的。具体包含以下步骤:
S6-1对所有CR-Mesh节点,针对每个网关节点,使用公共控制通道(CCC)广播一个消息给其所有的邻居节点集合中的所有节点,共广播个消息,。消息表示从网关节点到节点的层次为,其中,为之前计算的相对于网关来说,节点所处的层次。
S6-2对所有CR-Mesh节点,当收到一个的消息时,比较与消息中的值之间的关系,如果,则=,pre(gj,vq)表示相对于网关gj来说,节点vq的父亲节点集合,如果,则=,chi(gj,vq)表示相对于网关gj来说,节点的儿子节点集合。
经过上述步骤之后,相对G1而言,R2、R3、R4、R7、R10和C4的父亲节点和儿子节点集合如下所示。
对G1而言,pre(G1,G1)={};chi(G1,G1)={ R2, R3}。
对R2而言,pre(G1,R2)={G1};chi(G1,G1)={ R2, R3}。
对R3而言,pre(G1,R3)={G1};chi(G1,R3)={R7}。
对R4而言,pre(G1,R4)={ R3};chi(G1,R4)={R8}。
对R7而言,pre(G1,R7)={ R3};chi(G1,R7)={R10}。
对R10而言,pre(G1,R10)={ R7};chi(G1,R10)={C4}。
对C4而言,pre(G1,C4)={ R10};chi(G1,C4)={}。
S1-4计算所有节点与其儿子节点之间的无线链路预分配某信道之后的权值。
对所有CR-Mesh节点,计算无线链路预分配信道之后的权值,其中是相对于网关节点来说,节点的儿子节点,即,。由于的值与网关节点无关,因此的计算公式中不于标明网关节点,的计算公示为:,。
经过计算,节点和节点之间预分配信道之后的权值如下所示。
对(G1,R3)而言,
f2(G1,R3)=(Pn2(G1,R3)/Sn2(G1,R3)) *(Dy2/Max{Dyk|k∈K})=(0.4/0.7)*(10/25) =0.229。
对(G1,R2)而言,
f2(G1,R2)=(Pn2(G1,R2)/Sn2(G1,R2)) *(Dy2/Max{Dyk|k∈K})=(0.6/0.5)*(10/25) =0.48。
f4(G1,R2)=(Pn4(G1,R2)/Sn4(G1,R2)) *(Dy4/Max{Dyk|k∈K})=(0.8/0.4)*(20/25) =1.6。
对(R2,R3)而言,
f2(R2,R3)=(Pn2(R2,R3)/Sn2(R2,R3)) *(Dy2/Max{Dyk|k∈K})=(0.6/0.5)*(10/25) =0.48。
f3(R2,R3)=(Pn3(R2,R3)/Sn3(R2,R3)) *(Dy3/Max{Dyk|k∈K})=(0.8/0.6)*(15/25) =0.8。
对(R3,R4)而言,
f2(R3,R4)=(Pn2(R3,R4)/Sn2(R3,R4)) *(Dy2/Max{Dyk|k∈K})=(0.8/0.3)*(10/25) =1.1。
f3(R3,R4)=(Pn3(R3,R4)/Sn3(R3,R4)) *(Dy3/Max{Dyk|k∈K})=(0.4/0.6)*(15/25) =0.4。
对(R3,R7)而言,
f2(R3,R7)=(Pn2(R3,R7)/Sn2(R3,R7)) *(Dy2/Max{Dyk|k∈K})=(0.5/0.5)*(10/25) =0.4。
f3(R3,R7)=(Pn3(R3,R7)/Sn3(R3,R7)) *(Dy3/Max{Dyk|k∈K})=(0.4/0.6)*(15/25) =0.4。
f5(R3,R7)=(Pn5(R3,R7)/Sn5(R3,R7)) *(Dy5/Max{Dyk|k∈K})=(0.4/0.7)*(16/25) =0.366。
对(R7,R10)而言,
f2(R7,R10)=(Pn2(R7,R10)/Sn2(R7,R10)) *(Dy2/Max{Dyk|k∈K})=(0.5/0.5)*(10/25) =0.4。
f3(R7,R10)=(Pn3(R7,R10)/Sn3(R7,R10)) *(Dy3/Max{Dyk|k∈K})=(0.6/0.4)*(15/25) =0.9。
f5(R7,R10)=(Pn5(R7,R10)/Sn5(R7,R10)) *(Dy5/Max{Dyk|k∈K})=(0.4/0.6)*(16/25) =0.427。
对(R10,C4)而言,
f2(R10,C4)=(Pn2(R10,C4)/Sn2(R10,C4)) *(Dy2/Max{Dyk|k∈K})=(0.5/0.7)*(10/25) =0.286。
f5(R10,C4)=(Pn5(R10,C4)/Sn5(R10,C4)) *(Dy5/Max{Dyk|k∈K})=(0.5/0.6)*(16/25) =0.533。
S1-5基于动态规划(Dynamic Programming, DP)策略采用分布式方式构建从源点到目的节点的高可靠、低延迟的路由路径,为无线业务,其中表示CR-Mesh网关节点,即为源点,表示CR-Mesh终端节点,即为目的节点。对于CR-Mesh网关、路由器和终端节点,其工作流程是不一样的,流程图如图6所示,下面分别说明其包含的步骤。
终端节点,其处理流程如下:
S7-1计算终端节点到自己使用信道的路径最小权值总和,即,其计算公式为: 。
即,。
S7-2对终端节点的每一个父亲节点,构造并发送一个消息,含义是:当网关节点是,终端节点是的情况下,终端节点发送给的控制消息。
其中表示到的路径最小权值总和。表示到其儿子节点所使用的信道,表示取最小值时,与相连的儿子节点,其值分别是:
,表示最小权值总和为0;
,由于没有儿子节点,即表示没有给其分配信道;
,表示节点没有儿子节点。
即给其父亲节点发送一个消息。
路由器节点,其处理流程如下:
S8-1当路由器节点接收到其儿子节点的消息的时候,对节点的每一个可用信道(),计算节点与其儿子节点之间的无线链路分配信道的情况下,路由器节点到终端节点的路径最小权值总和,即,其计算公式为:。
对而言,当其收到的时候,计算和。
即==0.286;
==0.533。
对而言,当其收到的时候,计算、和。
即==0.4+0.533=0.933;
==0.9+0.286=1.186;
==0.427+0.286=0.713。
对而言,当其收到的时候,计算、和。
即==0.4+0.713=1.113;
==0.4+0.713=1.113;
==0.366+0.933=1.299。
S8-2对路由器节点的每一个可用信道(),计算取最小值时的儿子节点,以及与其儿子节点使用信道。其计算公式为:(,) 。
对而言,对于可用信道2,取最小值时的儿子节点为,与其儿子节点使用信道为信道0。
对而言,对于可用信道5,取最小值时的儿子节点为,与其儿子节点使用信道为信道0。
对而言,对于可用信道2,取最小值时的儿子节点为,与其儿子节点使用信道为5。
对而言,对于可用信道3,取最小值时的儿子节点为,与其儿子节点使用信道为信道2。
对而言,对于可用信道5,取最小值时的儿子节点为,与其儿子节点使用信道为信道2。
对而言,对于可用信道2,取最小值时的儿子节点为,与其儿子节点使用信道为信道5。
对而言,对于可用信道3,取最小值时的儿子节点为,与其儿子节点使用信道为信道5。
对而言,对于可用信道5,取最小值时的儿子节点为,与其儿子节点使用信道为信道2。
S8-3对路由器节点的每一个可用信道(),保存一个三元组,其中表示信道,表示计算取最小值时的儿子节点,表示节点到其儿子节点使用的信道。,,。
对而言,保存和。
对而言,保存、和。
对而言,保存、和。
S8-4对路由器节点的每一个可用信道(),构造一个消息,给的每一个父亲节点发送一个消息。的含义是:当网关节点是,终端节点是的情况下,节点发送给的控制消息。
其中表示到的路径权值总和,表示到其儿子节点所使用的信道,表示取最小值时,与相连的儿子节点,其值分别是:
表示经过其儿子节点到终端节点是的权值总和;
,表示与其儿子节点之间的无线链路分配的信道;
,表示取最小值时,与相连的儿子节点。
对而言,给其父亲节点发送一个消息。
对而言,给其父亲节点发送一个消息。
对而言,给其父亲节点发送一个消息。
网关节点,其处理流程如下:
S9-1当网关节点接收到其儿子节点的消息的时候,网关节点计算其到终端节点的路径最小权值总和,即,其计算公式为:。
对而言,计算。
即
=Min{0.229+1.113, 0.229+1.299}=1.342。
S9-2计算的路径中与相连接的节点,无线链路分配的信道,以及与其儿子节点使用信道,其计算公式为:(,,) 。
对而言,对于可用信道2,取最小值时的儿子节点为,分配的信道为信道2,与其儿子节点使用信道为信道3。
S1-6给构造的路由路径中的所有无线链路分配信道,流程图如图7所示,。
S10-1网关节点根据公式(,,)获得取得最优值的儿子节点, 与其儿子节点使用的信道,以及到其儿子节点使用信道,即。
即。
S10-2网关节点给节点儿子节点发送一个控制消息,其中表示到其儿子节点使用信道。 其中。
对而言,给儿子节点发送消息,。
S10-3路由器节点收到其父亲节点的消息之后,在本地的三元组中寻找消息中的相等的三元组,即。
对而言,找到匹配的三元组。
对而言,找到匹配的三元组。
对而言,找到匹配的三元组。
S10-4节点到其儿子节点之间的无线链路分配信道,即,路由器节点给其儿子节点发送一个控制消息,其中表示到其儿子节点使用信道,。
对而言,,给儿子节点发送控制消息,其中。
对而言,,给儿子节点发送控制消息,其中。
对而言,,给儿子节点发送控制消息,其中。
最后,得到无线组播业务以高可靠与低延迟为目标的路由路径,即。表示CR-Mesh网关节点到分配信道2,CR-Mesh路由器节点到分配信道3,CR-Mesh路由器节点到分配信道5,CR-Mesh路由器节点到分配信道2。
机译: 分布式架构路由器中基于工作流的路由的设备和方法
机译: 分布式架构路由器中基于工作流的路由的设备和方法
机译: 分布式路由器以及在分布式路由器中传输控制消息的方法