基于量子遗传算法的无线传感器网络QoS路由选择算法研究 第8页
复的LS分组，说明它已从其他的路径接收到了该分组，则丢弃该分组；如果LS分组的序号小于以前曾受到的来自同一发送者的LS分组序号，说明该分组时一个过时的LS分组，则丢弃该分组。为了避免序号冲突问题，序号采用较长的位数，如32位，序号以232为模，循环周期为232。
③ 链路状态信息以软状态方式保存在路由器中，路由器定期地（如每隔1秒钟）检查它所记录的LS分组的生存期，并减1。如果一个LS分组的的生存期减至0，并删除来自该LS分组的链路状态信息。这样就避免了无效的或出错的链路状态信息长期占据路由器的存储空间。
这样，一个路由器所测量的链路状态信息通过上述的传递机制发布给网络中所有的路由器。每个路由器用接收到的LS分组来建立和更新期路由表。
④ 计算网络最短路径。各个路由器在建立路由表后，可采用Dijkstra算法计算到达目的节点的最短路径，并按照路径转发数据分组。
3.2 基于遗传算法的最短路径问题方案
最短路径选择是静态路由选择算法中一种重要的路由选择算法。一些传统的最短路径（Shortest Path，SP）搜索算法：宽度优先搜索算法、Dijkstra算法、Bellman-Ford算法等，它们在有基础设施的无线网络和有线网络方面在多项式时间内能较好地解决最短路径问题，但在实时通信环境、高动态的拓扑结构比较复杂时，其计算复杂度增加，计算时间也相应增加。因为遗传算法在处理传统优化算法难于解决的复杂和非线性问题的优势，用遗传算法来求解最短路径问题得到广泛的研究。Chang Wook Ahn提出了一种新型的最短路径搜索算法，利用遗传算法来处理最短路径问题的解决方案[23]。
3.2.1 网络模型
在研究路由问题时，一个网络可表示成一个加权图 ，其中V表示节点集，E表示连接节点的通信链路集。即无向图G由一组点V ={1，2，…， }和一组连接 中节点的边 组成。 为链路 的代价，代价矩阵为 ＝[ ]。从节点 到 的路径是 中的一个边序列 ， ，… ， 。路径中没有一个节点出现的次数多于2。路径也可以用一个节点序列 等价表示。
令S表示路径的初始节点，D表示路径的终节点，Iij是如下定义的指示变量：
最短路径问题可以表示为：             (3-4)
其中约束条件(3-2)和(3-3)共同确保除节点S和D外的任何一个节点，不存在或只有两条相邻的边，约束条件(3-4)确保节点S和D是路径的端点。
3.2.2 编码
 在标准遗传算法中，如何将问题的解转换为编码表达的染色体是遗传算法的关键问题。在该算法中，遗传算法的染色体由一系列的整数队列组成，即基于路径表示的编码方法，该方法是一种最自然、最简单的表示方法[23]。该方法要求每个个体的染色体编码中不允许有重复的基因码，也就是说要满足任一个节点在路径中只能访问一次的约束。染色体的第一位置总是路径的源节点，最后一个位置是目的节点，染色体的长度是变化的，但不可能超过最大长度N（N为网络的节点数）。染色体编码即为从源节点到目的节点的队列组成，该信息在实时路由协议是容易获取和维护的。如从源节点S到目的节点D的一个染色体编码为{S,N1,N2, … ,Nk, D}，如图3.3所示。
 图3.3 路由路径的编码表示
其中l表示染色体的长度。染色体编码的第一位置基因（节点）是源节点，第二位置基因是从与源节点连接的其它节点中随机选择或启发式选择。选择的节点从结构信息库中删除，以避免重复选择。这个过程重复下去，直至到达目的节点。
3.2.3 适应度函数
由于遗传算法在进化搜索中基本不利用外部信息，仅以适度函数为依据，利用种群中每个个体的适度值来进行搜索，因此适度函数直接影响到遗传算法的收敛速度以及能否找到全局最优解。在最短路径路由选择问题中，适应度函数的主要功能是寻找最优路径，即时延或耗费最少的路径。因此，适应度函数定义如下：
               （3-5）
其中fi和li分别表示种群中第i条染色体的适应度和长度；gi(j)表示第i条染色体的第j个节点，C表示代价矩阵。适应度是路径选择的惟一标准。适应度值越高，路径时延（或耗费）越小。
3.2.4 选择
选择或复制操作的目的是为了从当前群体中选出优良的个体，是它们有机会作为父代为下一代繁殖子孙。判断个体优良与否的准则就是各自的适应度值。显然这一操作是借用了达尔文适者生存的进化原则，即个体适应度越高，其被选择的机会就越多。选择方式一般有轮盘赌、排序选择和联赛选择方法。
 Chang Wook Ahn采用的是联赛选择方法，其基本原理是，从当前种群中任意选取2个个体，比较这2个个体的适应度值，保留适应度值大的个体，并且保证同一个体只被选择一次。联赛选择的优势是保证了当代种群中的最优个体能遗传到下一代种群中，这样增加了全局最优解被选中的概率。
3.2.5 交叉 
交叉操作是指按一定概率随机从亲代群体中选择两个个体，随机将两个亲代个体的部分结构相互交换，生成两个新的子代个体。交叉操作产生的两个子代个体，都包含两个亲代个体的遗传基因，但与亲代个体不同。因此，交叉操作能
提高遗传算法的搜索能力，在适当选择策略下，通过交叉操作可提高向全局最优解的收敛程度。
在该算法中，交叉不同于传统的单点交叉，两个染色体选择一个公共的基因(节点)作为交叉点，交叉点不依赖于节点在路径中的位置，当有两个以上的公共的节点时，只需选择其中之一作为交叉点,通常选择第一个公共点进行交叉[20]。
如图3.4，父代染色体为：Path1 = {S,N1,N2,N4,N5,D},Path2 = {S,N2,N3,N5,N6,N7,D}。节点N2和N5是两个公共节点，则可以选择N2和N5中的任一节点作为交叉点。若选择N2作为交叉点，则交叉后的子代染色体为：
Path1 = {S,N1,N2,N3,N5, N6,N7,D}, Path2 = {S,N2,N4,N5 ,D}。
图3.4 交叉操作的处理过程
 在交叉操作中，有可能产生的子代染色体中包含环路，如图3.5。因此，在交叉之后，要检查路径是否存在环路，若存在则删除路径中的环路。如图3.5中，交叉操作后获得的新路径为：Path1 = {S,N2,N3,N1,N2,N4,D}，其中包含环路{N2,N3,N1,N2}。因此路径Path1为失效路径，应删除路径中的环路。删除环路后的路径为：Path1 = {S,N2,N4,D}。

上一页  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]  ... 下一页  >>