基于量子遗传算法的无线传感器网络QoS路由选择算法研究 第11页
参数、乘性度量参数和凹性度量参数。
假设路径p包含n条链路 ，f(li)是链路i的参数值，f(p)是路径p的参数值，各种度量参数特性定义[25]如下：
加性度量参数： ，即构成这条路径所有链路QoS值的和(如跳数、时延、成本、链路长度等)；
乘性度量参数： ，即构成这条路径所有链路QoS值的积(如误差率、丢包率、链路利用率等)；
凹性度量参数： ，即构成这条路径所有链路QoS值中最小者(如时延等)。
度量参数选择提供了保证QoS的路由选择规则，按照这些规则和获得的网络状态信息，就可以进行有QoS保证的路由选择。路由选择过程中首先要考虑的是如何选择路径和确保业务流按照所选路径发送。目前，路由选择的方法大多采用改进的Dijkstra算法或改进的Bellman-Ford算法。路由选择可以由业务源节点独自完成，也可以由网络中的多个节点协同完成。由源节点独立完成的路由选择称为源路由，由多个节点协同完成的称为分布式路由。
4.2 基于量子遗传算法的QoS路由选择算法方案
4.2.1 QoS路由问题网络模型
随着移动网络、全光纤网络等高性能网络技术的发展，计算机网络将是一种
能提供视频点播、视频电话和多媒体会议等多媒体应用服务的集成服务网络。人们发现传统的“尽力而为”的数据传输无法满足网络的正常运行。为了保证网络服务质量，路由选择不再仅仅里“可达”和“最短路径”为衡量标准，而是希望根据多个QoS约束的尺度来选择可行的路由以满足应用所需的时延、带宽、时延抖动和包丢失率等要求[26]。研究表明，多个性能限制的QoS路由问题是NP完全问题，因此怎样能有效地支持服务质量(QoS)是当前网络领域研究的热点。针对多约束QoS路由问题的求解，现今并没有有效的近似算法，一般采用启发式算法求解，如遗传算法[27]、模拟退火[28]、蚁群算法[29]、免疫算法[30]等。文献[31]采用遗传算法来求解QoS路由问题。
在满足带宽及时延的基本要求下，消耗尽可能少的网络资源，并使网络负载尽量均匀分布。在宽带网络中，带宽和时延是两个重要的参数。带宽表示网络的通信线路所能传输数据的能力。一条路径的带宽是指这条路径上所有链路剩余带宽的最小值，称为瓶颈带宽。时延是指数据从网络的一端传送到另一端所需的时间。时延包括传输时延、传播时延、处理时延和排队时延。这里主要考虑传输时延。显然，对于一个业务量来说，所占用的网络资源越少越好。同时，还要保证网络负荷的均衡分布，有利于避免链路饱和，降低发生拥塞的可能性。另外，负载的均匀分布也会保证低的排队延迟和低的缓冲区溢出率。衡量负载均衡程度的指标可以采用链路利用率的方差。方差越小，负载分布越均衡。
在研究路由问题时，一个网络可表示成一个加权图 ，其中V表示节点集，E表示连接节点的通信链路集。即无向图G由一组点V ={1，2，…， }和一组连接 中节点的边 组成。设 为源节点， 为目的节点，任意一条路径 表示由源节点 到目的节点 的路径。 是如下定义的指示变量：
                              （4-1）
则路径 的瓶颈带宽 和时延 分别为
其中 为节点 和节点 之间链路的可用带宽， 为节点 和节点 之间链路的传输时延。资源消耗函数定义为：对于一条所选路径，一个业务流占用的网络资源为沿途各链路为该路径预留资源的总和与该业务流占用该路径的时间的乘积。设所选路径 消耗的网络资源为 [31]，则
              （4-4）
其中 为网络中传输的业务要求的带宽， 为路径 的条数。由上式可以看出，资源消耗与所选路径 的跳数和时延有关，跳数越少、时延越小的路径消耗的网络资源越少。由此，资源消耗函数 的最小化体现了最小跳数和最小时延的优化准则。
负载分布情况可以用接入新的连接后对原有链路可用带宽的影响来衡量。节点 和节点 间链路的利用率 为
                                        （4-5）
其中 为网络中传输的业务要求的带宽， 为节点 和节点 之间链路的可用带宽。路径的可用带宽越大，该路径的安全性就越好。若 接近于 ，说明节点 和节点 之间链路可用带宽与业务所要求带宽接近，因此选择该链路不安全。而且如果该链路接受某一条路径的请求之后，就无法再接纳其他经过该链路的连接请求了。若 远远大于 ，说明节点 和节点 之间链路可用带宽比较大，这条路径比较安全，接纳某一路径请求之后不会影响接纳新的连接请求。所以负载应该尽量分布在空闲的链路上，以达到整个网络的负载均衡。一条路径上负载分布的均衡程度可用该路径上链路利用率的方差来衡量。令 为 的均值，则                                    （4-6）
那么，链路利用率的方差 为                              （4-7）
QoS路由问题的优化目标就是要选择一条路径 ，且 满足
                                      （4-8）
该问题属于多目标优化问题，在多数情况，无法保证 和 均取得最小值。因此，构造优化目标函数为[31]
                               （4-9）
其中， 和 是正实数，且 和 选择合适，使得函数 中 和 占大致相等的比例。
4.2.2 基于量子遗传算法的QoS路由选择算法参数设计
由于需要满足QoS约束条件，我们对QGA算法的主要参数进行如下设计：
（1）判断链路eij的带宽B(eij)是否满足所需带宽B，若B(eij)< B，则把链路设为不可达链路，从而使计算机网络拓扑结构发现变化。
（2）问题描述。量子染色体的表示和测量过程都和前面QGA的描述相同。
（3）种群初始化：量子染色体中量子比特基因数由计算机网络的节点数N和任意节点的邻接点数K共同确定。初始种群中的量子染色体的Qubit基因均初始化为 ，这意味着一个染色体所表达的是其全部可能状态的等概率叠加，使种群具有更好的多样性特征，以有效客服早熟收敛。
（4）适应度函数的选取：适应度函数是用来评估每个染色体的好坏，并且是非负的。适应度函数设为：（4-10）
（5）量子变异：考虑到程序实现的简单化，采用量子旋转门调整策略。
（6）终止条件：给定遗传操作代数G，当算法迭代次数达到G时终止。

 << 上一页  [11] [12] [13] [14] [15] [16] [17] [18] 下一页