基于元胞遗传算法的无线传感器网络生存的应用

作者简介：段谟意(1964-),男,江西都昌人,学士,副教授,主要研究方向：网络可靠性、信
0引言
　　生存性是在随机破坏下系统的可靠性。生存性主要反映随机性破坏和网络拓扑结构对系统可靠性的影响。这里，随机性破坏是指系统部件因为自然老化等因素而造成的自然失效。随着通信网络的快速发展，网络的可靠性已日益受到来自多个方面的关注和重视［1］。网络生存性作为衡量网络可靠性的重要指标，是指当网络中的链路和节点遭受攻击或发生随机失效时，网络维持其基本通信功能的能力。目前，网络生存性的研究主要集中在拓扑结构、路由策略和链路容量的优化设计等方面，国内外学者亦对此开展了大量研究。冯冬芹等［1］为了提高工业无线传感器网络的可靠性和可用性,使其能够长期自治地正常工作,提出了基于簇头冗余的工业无线传感器网络分簇路由算法。马闯等［2］为了在无线传感器网络可靠性研究中对故障检测等容错机制进行准确评价和量化分析, 提出了一种具有高覆盖度特点的网络层次化故障模型。段谟意［3］ 通过建立克隆变异和克隆交叉操作规则,并结合模拟退火接受准则来获得退火温度趋于零时的最优解。赵攀等［4］通过建立生存性的评价指标,同时针对失效状态下的到达流量进行小波变换,并利用混合蛙跳优化小波系数,以此获得最佳网络剩余流量。朱晓娟等［5］从可靠性评估和可靠的数据传输技术两个方面介绍了近年来的研究成果,对这些成果进行了分类、比较,并进一步展望了在未来无线传感器网络可靠性的研究方向。何明等［6］从拓扑生成、拓扑愈合及拓扑优化三个方面论述了移动无线传感器网络的拓扑动态演化性，但是这些优化思想只是考虑了如何提高生存性技术本身的性能，却并未从网络模型和网络状态进行量化研究，为此对提高网络生存性的作用亦将十分有限。
　　针对上述存在的问题，本文首先结合网络权重和最短路径数分布定义了网络生存性指标，而且通过元胞遗传算法建立了等效最短路径数的计算方法，同时又通过仿真实验深入研究了影响该指标的重要因素。
　　1网络生存性定义
　　在网络通信过程中，节点之间一般以某条最短路径进行传输，跳数越多的路径其可靠性越差，生存性也就越差。但网络通信却可能受到外界因素影响，进而造成链路或者节点失效，此时若节点之间存在多条最短路径，在某条最短路径失效后则依然可以通过其它最短路径传输数据。所以，节点之间的最短路径数对于网络生存性研究即具有高度重要且必要的作用。本文即结合最短路径数和网络权重分布来对网络生存性进行研究。
　　假设存在一n个节点的全连通网络G(V, E)，其中的V表示点集，E表示边集。根据文献［7］的研究成果，节点i和j之间跳数小于等于r的值m(r)的计算公式则可表示为：
　　m(r)=∑rk=1(n-2)!(n-k-1)!(1)
　　 而节点i和j之间跳数最少的路径即称为最短路径，此时对应的跳数则为最短路长。如果节点i和j之间存在k条最短路长lij，那么可将其转化为等效最短路径数kij，具体公式为：
　　kij=km(lij)(2)
　　此时，如果G为全连通网络，则kij=1。由理论来讲，全连通网络的生存性最优，但是出于成本等因素考虑，实际过程中却很少采用这种形式。由此可知，在非全连通网络中，0
　s1=2∑n-1i=1∑nj=i+1Kijn(n-1)(3)
　　解析公式（3）可知，该评价指标仅仅基于等效最短路径数来考虑网络拓扑结构的影响，但由于实际链路带宽等因素的不同作用，将导致每条链路上传输的单位业务流也各不相同，因此对链路的权重因素也加以考虑，即显得尤为重要。假设两相邻节点i和j之间的链路eij上对应的权重为ωij，那么该权重对于网络生存性的影响s2为：
　　s2=α1Bij+βCij(4)第3期段谟意，等：基于元胞遗传算法的无线传感器网络生存性研究智能计算机与应用第4卷
　　其中，Bij为节点i和j之间的传输业务流大小，Cij为节点i和j之间的剩余带宽，α和β为比例系数，且α+β=1。
　　 基于以上两点，本文将等效最短路径数和网络权重综合起来加以考虑，即重新定义网络生存性的评价指标s：
　　s=s1ηs2θ=(2∑n-1i=1∑nj=i+1Kijn(n-1))η(α1Cij+βBij)θ(5)
　　 其中，η和θ分别为(0, 1)之间的常系数，可用于度量等效最短路径数和网络权重对网络生存性的影响程度。
　　 针对上述评价指标，本文采用元胞遗传算法来对等效最短路径数进行研究。元胞遗传算法是结合遗传算法和元胞自动机，使用元胞自动机的演化规则来替换遗传算法的进化策略。其思想是：遗传个体受到周围邻居影响和殖民侵入，自然就会具有与邻居相似的多样性。为保持向邻居学习与殖民之间的平衡, 元胞遗传算法则随之而成为了解决复杂问题的一种有效方法，藉此可以有效地减少计算最短路径数的复杂度。
　　 结合元胞遗传算法，本文提出如下网络生存性算法（Survivability Algorithm Based on Cellular Genetic，CGA），算法流程描述如下：
　　 Step1：初始化网络以及相关参数，并将网络节点视作元胞，确定种群、元胞空间和元胞个体状态；
　　 Step2：选择某一元胞为中心元胞，并从邻域内选择出最优元胞个体作为父体，用于产生下一代个体；
　　 Step3：将选取的父体与中心元胞进行交叉、变异操作，产生下一代个体，作为辅助种群；
　　 Step4：根据元胞演化规则，确定下一代个体在下一时刻的状态；
　　 Step5：计算当前的等效最短路径数，与最优解进行比较，如果当前解优于最优解，则用当前解替换最优解；
　　 Step6：若当前种群中每一个元胞个体操作完成，则采用辅助种群替换当前种群，跳转到Step 2；
　　 Step7：判断当前种群是否已经达到最大并且已经搜索到最优解，如果是则结束搜索，跳转到Step 8，否则跳转到Step 2；
　　 Step8：输出当前最优解，获得等效最短路径数；
　　 Step9：根据式(5)获得网络生存性的评价指标。
　　2数学仿真
　　针对上述提出的网络生存性算法CGA，此处将给出数学仿真。首先，在OPNET中建立如图1的网络拓扑结构。并且初始化元胞遗传算法参数相应地设置为：链路容量20Mbps，延时12ms，各节点缓存大小为600 packets，数据包均为900Byte，权重分配系数α和β分别0.35和0.65。为了验证 本文提出的CGA算法有效性，这里将与基于免疫规划的模拟退火算法（Simulated Annealing algorithm based on Immune Programming，SAIP）进行比较分析。SAIP算法仅仅考虑了最短路径数，却没有考虑权重对网络生存性的影响。将这两种算法在OPNET中仿真800s时长，获得最后相对稳定的100s结果进行比较，仿真结果如图2所示。从图2可以看出，本文提出的CGA算法性能要优于SAIP算法，算法精度较SAIP提高了5.64%。
　　图1网络拓扑结构图
　　Fig.1The network simulation topology
　　其次，本文分析不同权重系数θ下，减少网络节点数后网络生存性的变化情况。同样，定义减少的节点数与网络中总节点数为节点剔除比，在图3中显示了节点剔除比与网络生存性之间的关系。从图3可以看出，随着节点剔除比的增加，网络生存性整体上呈现出下降趋势。在节点剔除比较小时，θ=0.6对应曲线的网络生存性要优于θ=0.4的曲线，而节点剔除较大时情况却发生了变化，θ=0.4所对应曲线的网络生存性则优于θ=0.6的曲线。分析其原因在于，当网络结构遭到较小破坏时（节点失效数目较少），权重的变化比网络结构变化受到的影响要小。而在后期，由于失效节点的数目增多，流量减少的程度则迅速增加，权重受到影响程度也随之加大，使得状态发生突变。
　　图2网络生存性比较
　　Fig.2The comparison of network survivability
　　图3网络生存性与节点剔除比的关系
　　Fig.3The relationship between network
　　survivability and node removed ratio
　　这里还要对CGA算法的影响因素进行深入分析。将网络生存性评价指标I中的网络权重系数θ作为研究对象，分析在不同的网络权重系数θ下的网络生存性的变化情况，结果如图4所示。从图4的整体情况上来看，θ=0.6对应曲线的网络生存性在仿真初期要优于θ=0.4的曲线，但是在仿真后期则要劣于θ=0.4这条曲线。这就说明在仿真初期，权重系数θ越大，对应的网络生存性越好，而在后期网络生存性权重系数θ越小，对应的网络生存性则会越好。
　　图4不同网络权重系数下网络生存性比较
　　Fig.4The comparison of network survivability
　　in different network weight factor
　　3结束语
　　本文结合元胞遗传算法提出了一种新的网络生存性刻画方法。该方法结合最短路径数和网络权重分布建立生存性评价指标，并且通过定义元胞演化规则和选择、交叉、变异操作来模拟元胞状态的变化，以此反映网络生存性的优劣。同时，本文将提出的CGA算法与SAIP算法进行仿真分析，说明了该方法的有效性，并且深入分析了网络生存性的影响因素。在后续研究中，可以考虑利用元胞蚁群、人工免疫等算法，针对网络生存性和有效性进行建模，以此形成一套比较完整的网络可靠性评价指标。
　　参考文献：
　　［1］冯冬芹,李光辉,全剑敏,等.基于簇头冗余的无线传感器网络可靠性研究［J］.浙江大学学报(工学版),2009(5):849-854.
　　［2］马闯,刘宏伟,左德承,等.无线传感器网络的层次化故障模型［J］.清华大学学报(自然科学版),2011(S1):3002-3005.
　　［3］段谟意.基于免疫克隆模拟退火算法的网络生存性研究［J］.计算机工程与设计,2012(12): 1008-1012.
　　［4］赵攀,魏正曦,张弘.网络生存性计算方法以及性能评价［J］.计算机应用,2013(10):998-1002.
　　［5］朱晓娟,陆阳,邱述威,等.无线传感器网络数据传输可靠性研究综述［J］.计算机科学,2013(9):1120-1124.
　　［6］何明,梁文辉,陈国华,等.水下移动无线传感器网络拓扑［J］.控制与决策,2013(12):3004-3007. 息安全；