预置最小阻塞概率节点的波长转换器的放置方法

摘要

本发明提出了一种预置最小阻塞概率节点的波长转换器的放置方法，该方法包含理论预置和启发式算法协调两部分，先理论计算预选部分节点作为可转换波长候选节点，然后利用仿真实验对多个波长可转换节点的整体性能进行优化的策略解决稀疏波长转换光网络中的波长转换器放置问题。同时，波长转换节点采用节点共享结构，使用的波长转换器均是全范围波长转换器，以保证在相同阻塞率性能要求下需要的波长转换器数量最少。该方法综合了理论分析高效性与仿真实验通用性的优点、避免了理论假设的片面性，同时发挥了理论的指导作用，有针对有目的地仿真修正，降低了单独仿真实验进行穷举搜索的复杂度，实现了速度和质量的均衡。

说明书

技术领域

本发明属于通信领域，主要涉及光纤网络技术中在节点如何放置波长转换器等内容。尤其是一种应用于稀疏节点波长转换型网络的，利用理论模型对单个节点放置波长转换器所带来的优化性能进行预筛选，利用仿真实验对放置波长转换器的所有节点整体性能评估以确定最终的放置方案的方法。

背景技术

波长路由网络能提供很高的光网络资源利用率，是下一代网络建设的一种非常有吸引力的技术。在这种网络中，两个波长路由器通过建立一条光通路进行通信。在一条光通路上，各条链路都要分配统一的波长，这就是波长一致性约束。由于波长信道的有限性和波长一致性约束，一些链接请求可能得不到满足而导致阻塞。为了缓解因为波长一致性带来的阻塞，一种有效的方法就是使用波长转换器。

波长转换器大致分为全范围波长转换和受限范围波长转换，前者对任意输入波长均可转换成任意输出波长，后者仅对某范围内波长进行相互转换。波长可转换网络按其波长转换器的分布和种类不同大致可以分四种：完全波长转换、稀疏节点波长转换、稀疏节点部分波长转换和部分波长转换，其分类方法如图3所示。

在稀疏波长转换网络中，波长转换器如何放置才能使网络阻塞率尽可能低，成为目前业界研究的热点和焦点。研究方法大致分为两种：基于理论模型的优化算法和基于仿真实验的优化算法。两种算法各有利弊，基于理论模型算法可以充分利用概率论随机过程等先进预测方法，建立完善的理论模型，但是在实际操作过程中往往需要假设大量的参数，因此参数设置的科学性将很大程度上影响模型的分析结果的合理性；基于仿真实验的优化算法，有相当广泛的通用性，又不局限于某种特殊的数学模型，但如果没有良好的预选策略，穷举搜索将带来大量重复的运算工作，不利于大规模网络的规划建设和网络的升级。

发明内容

本发明的目的在于针对GMPLS(通用多协议标志交换协议)稀疏波长转换光网络中的波长转换器放置问题，结合当前理论算法和仿真算法两种不同的解决思路，提出了一种利用理论预选和仿真协调相结合的启发式放置算法，以解决现有技术中单独使用理论分析带来的假设局限性和单独使用仿真试验带来的穷举搜索复杂性等问题。

本发明包含理论预置和启发式算法协调两部分，利用理论与仿真相结合的方法，提出先理论计算预选部分节点作为可转换波长候选节点，然后利用仿真实验对多个波长可转换节点的整体性能进行优化的策略解决稀疏波长转换光网络中的波长转换器放置问题。启发式算法技术方案的具体步骤如下，

第一步，候选节点是没有配备波长转换的节点，对于每一个候选节点，首先假设配备有一个全范围波长转换器，根据现有技术中对于单个节点波长可转换网络的阻塞率的计算方法计算出相应的全网的业务阻塞率；

第二步，如果给定W个波长转换器，把所有节点分为两个集合，一个为可变波长节点集合C，由第一步计算中阻塞率最低的前W个节点组成，另一个是非可变波长节点集合NC，由其余节点组成，两个集合中的节点均按理论阻塞率从小到大排序；

第三步，对集合C中的所有节点放置全范围波长转换器，仿真实验得出初始化集合C多个节点波长转换前提下网络的整体阻塞率性能；

第四步，把集合C第W位的节点替换成NC集合中第1位的节点，重复第三步，对理论计算的集合C进行实验修正，统计网络阻塞率；

第五步，按照第四步，把集合C的最后一个节点与集合NC中第2，3，……节点替换，重复第三步，统计网络整体阻塞率性能，至所有节点替换完成；

第六步，比较步骤第四步和第五步的阻塞率性能，选择最优的W个节点放置波长转换器。

至此，完成了波长转换器的放置。

需要说明的是本发明中的波长转换节点采用的是节点共享结构，即只转换需要转换的波长，不需要转换的波长直接进入复用器复用后输出。同时，为了使该种节点共享结构在相同阻塞率性能要求下需要的波长转换器数量最少，本发明中使用的波长转换器均是全范围波长转换器，即任意一输入波长可转换为任意一输出波长。

本发明的有益效果是：本发明以理论为依据，以仿真实验为手段，综合了理论分析高效性与仿真实验通用性的优点、避免了理论假设的片面性，同时发挥了理论的指导作用，有针对有目的地仿真修正，降低了单独仿真实验进行穷举搜索的复杂度，实现了速度和质量的均衡，在保证选择质量的同时有效地降低了时间复杂度。

附图说明

下面结合附图和实施例对发明做进一步说明。

图1本发明放置方法的启发式算法流程

图2波长可转换节点结构示意图

图3现有技术中不同种类波长转换器的分类

具体实施方式

下面以具体计算为例，说明如何使用本发明的方法计算节点的波长转换器放置问题。

首先，使用现有技术中对于单个节点波长可转换网络的阻塞率计算方法计算出全网的业务阻塞率。具体系统参数、假设以及计算过程如下：

假定网络有N个节点J根光纤链路。每个链路有W个波长依次从1到W标记。端到端链接请求到达率服从A^a的泊松分布，业务的保持时间服从指数分布，表征实际被成功建立的业务。

m_j表征链路j上的空闲波长数，{R_a⁽¹⁾，R_a⁽²⁾，L R_a^(Ma)}是对于源目节点对a预先计算出来的M_a条备选路由，本发明假定每一对源目节点对提供两条备选路由R_a⁽¹⁾，R_a⁽²⁾，并且其长度$h\left(R_a^{\left(1\right)}\right)<h\left(R_a^{\left(2\right)}\right),$显然，这两项假设可以很轻易地扩展为K条备选路径。只有当所有备选路径都被阻塞时，业务请求才被阻塞。B_Ra(t)表征路由R_a^(t)的阻塞概率。

步骤一，对于任意一源目节点对之间的业务请求，计算两条备选路径R_a⁽¹⁾，R_a⁽²⁾，令h(R_a⁽¹⁾)表征R_a⁽¹⁾的长度，假设$h\left(R_a^{\left(1\right)}\right)<h\left(R_a^{\left(2\right)}\right),$初始化令这两条链路的阻塞概率B_R为0，初始化选中每条链路的概率P_a⁽¹⁾，P_a⁽²⁾为1/2；

步骤二，使用等式(5)计算所有链路的业务到达率α_j，用等式(3)，(4)计算所有链路的链路j上m_j个波长可用的概率q_j(m)；

步骤三：使用公式(6)，公式(11)-(14)计算所有段的当m_j个波长在链路j上可用时，段R_a^(t，k)有i个波长可用的概率u_i(m_j；R_a^(t，k))和段R_a^(t，k)有i个波长可用的概率u(R_a^(t，k)，用公式(8)-(10)计算P_a⁽¹⁾，P_a⁽²⁾

步骤四，用公式(7)计算所有路由的B_R。如果新计算出来的B_R值与以前的值有重复，则停止计算，否则转到步骤二迭代

步骤五，利用公式(1)和(2)计算网络总的业务阻塞率。

上述计算全网业务阻塞率的过程中使用到的符号、等式及公式如下：

R_a⁽¹⁾，R_a⁽²⁾：对于任一源目节点对计算两条路径分离的路由备选

B_Ra(t)：表征路由R_a^(t)的阻塞概率

q_j(m_j)：链路j上m_j个波长可用的概率

h(R_a⁽¹⁾)：R_a⁽¹⁾路由的长度

P_a⁽¹⁾，P_a⁽²⁾：业务请求建路选择在第1/2条路由上的概率

u_i(m_j；R_a^(t，k))：m_j个波长在链路j上可用时，段R_a^(t，k)有i个波长可用的概率

u_i(R_a^(t，k))：段R_a^(t，k)有i个波长可用的概率

α_j：业务到达率

β(j，R)：链路路由入口矩阵，$\beta (j,R)=\left(\begin{array}{c}1,j\in R\\ 0,j\notin R\end{array}\right)$

$P=\frac{{\Sigma }_a(A^a-\overline{A^a})}{{\Sigma }_a{A}^a}---\left(1\right)$

$\overline{A^a}=A^a(1-\underset{t=1}{\overset{2}{\Pi }}{B}_{R_a^{\left(t\right)}})---\left(2\right)$

$q_j\left(m_j\right)=P(X_j=m_j)=\frac{{\Pi }_{i=1}^{m_j}(W-i+1)}{{\alpha }_j^{m_j}}P(X_j=0)---\left(3\right)$

$q_j\left(0\right)=P(X_j=0)={[1+\underset{m_j=1}{\overset{W}{\Sigma }}\frac{{\Pi }_{i=1}^{m_j}(W-i+1)}{{\alpha }_j^{m_j}}]}^{-1}---\left(4\right)$

${\alpha }_j(1-q_j\left(0\right))=\underset{a}{\Sigma }{A}^a(P_a^{\left(1\right)}\beta (j,R_a^{\left(1\right)})+P_a^{\left(2\right)}\beta (j,R_a^{\left(2\right)}))---\left(5\right)$

$u_i\left(R_a^{(t,k)}\right)=\underset{m_j=i}{\overset{W}{\Sigma }}{q}_j\left(m_j\right)u_i(m_j;R_a^{(t,k)})---\left(6\right)$

$B_{R_a^{\left(t\right)}}=1-\underset{k=1}{\overset{w_a^t+1}{\Pi }}[1-u_0\left(R_a^{(t,k)}\right)]---\left(7\right)$

$Q_{R_a^{\left(t\right)}}\left(i\right)=\mathrm{Pr}(F\left(R_a^{\left(t\right)}\right)=i)$

$=\mathrm{Pr}(\underset{k\in \{1,L{w}_a^{\left(t\right)}+1\}}{\min }\left(f\left(R_a^{(t,k)}\right)\right)=i)---\left(8\right)$

$=\underset{m=1}{\overset{w_a^{\left(t\right)}+1}{\Sigma }}[\underset{j=1}{\overset{m-1}{\Pi }}\left(\underset{k=i+1}{\overset{W}{\Sigma }}{u}_k\left(R_a^{(t,j)}\right)\right)·u_i\left(R_a^{(t,j)}\right)·\underset{j=m+1}{\overset{w_a^{\left(t\right)}+1}{\Pi }}(\underset{k=i}{\overset{W}{\Sigma }}{u}_k\left(R_a^{(t,j)}\right))]$

$P_a^{\left(1\right)}=\underset{i=1}{\overset{W}{\Sigma }}\left[Q_{R_a^{\left(1\right)}}\left(i\right)\underset{j=0}{\overset{\Phi \left(i\right)}{\Sigma }}{Q}_{R_a^{\left(2\right)}}\left(j\right)\right],\Phi \left(i\right)=\left[\sqrt{\frac{h\left(R_a^{\left(2\right)}\right)}{h\left(R_a^{\left(1\right)}\right)}·i}\right]---\left(9\right)$

$P_a^{\left(2\right)}=\underset{i=1}{\overset{W}{\Sigma }}\left[Q_{R_a^{\left(2\right)}}\left(i\right)\underset{j=0}{\overset{\theta \left(i\right)}{\Sigma }}{Q}_{R_a^{\left(1\right)}}\left(j\right)\right],\theta \left(i\right)=\left[\sqrt{\frac{h\left(R_a^{\left(2\right)}\right)}{h\left(R_a^{\left(1\right)}\right)}·i}\right]---\left(10\right)$

$u_i(m_j;R_a^{(t,k)})=\underset{m_{j_1}=0}{\overset{W}{\Sigma }}\underset{m_{j_2}=0}{\overset{W}{\Sigma }}L\underset{m_{j_{h-1}}=0}{\overset{W}{\Sigma }}\{\underset{l=1}{\overset{h-1}{\Pi }}{q}_{j_i\left(m_{j_i}\right)}\times p_i^h(m_j,m_{j_1},L{m}_{j_{h-1}})\}---\left(11\right)$

${P_i}^n(m_{j_1},L,m_{j_n})=\underset{k=0}{\overset{W}{\Sigma }}{p}_i^2(k,m_{j_n})p_k^{n-1}(m_{j_1},L,m_{j_{n-1}})---\left(12\right)$

其次，如图1所示根据给定的W个波长转换器，理论计算各个节点如果加上全范围波长转换后的网络业务阻塞率；把所有节点划为两个集合，一个为候选波长变换节点集合C，一个为非波长变换节点集合NC；候选波长变换节点集合C由理论阻塞率最小的W个节点组成，剩余节点为非波长变换节点；对C集合中的每个节点配置全范围波长转换器，仿真统计全网业务的阻塞率；将C集合中的最后一个候选节点依次替换为NC集合中的某点，仿真统计全网业务阻塞率，直至替换完成。

最后，根据上述结果选取阻塞率性能最优的组合进行波长转换器的放置。

本发明中使用的波长转换器均是全范围波长转换器，即任意一输入波长可转换为任意一输出波长，波长转换节点采用节点共享结构，即只转换需要转换的波长，不需要转换的波长直接进入复用器复用后输出。如图2的节点结构示意图所示，该种节点共享结构在相同阻塞率性能要求下需要的全范围波长转换器数量最少。

另外，本发明采用NS2仿真平台开发了一个产生上述算法的软件流量产生器，从而保证理论设计和软件仿真的一致性。

需要注意的是，尽管本发明已参照具体实施方式进行描述和举例说明，并且在具体实施方式中给出了本发明方法的具体计算过程。但是并不意味着本发明限于这些描述的实施方式。本领域技术人员可以从中衍生出许多不同的变体，它们都将覆盖于本发明权利要求的真实精神和范围中。