针对随机网络可靠性的递归重要性分层抽样方法

对随机网络可靠性估计的抽样方法

----递归重要性和分层抽样AsimplerecursiveimportanceandstratifiedsamplingschemeforstochasticnetworkreliabilityestimationWei-NingYang*,Wei-LingShih,JihChunYeh指导老师：徐光伟学生：杨延彬

时间：2015/06目录问题提出一研究现状二算法设计三性能评估四总结五2一、问题提出研究背景

大多数计算机通信系统可以被当做随机网络模型，其网络的可靠性经常作为系统性能的一个衡量标准。但是由于网络的复杂性，分析模型和数值评估是不可行的，因为随着网络复杂性的增长，其可靠性的计算代价过高。问题提出计算机仿真是评估网络可靠性的一个可行的替代选择，但由于计算机仿真依赖于试验统计，所以需要解决仿真过程中的抽样误差。原始的蒙特卡洛抽样是活的网络可靠性估计的基本技术，但是对于可靠性比较好的网络，需要进行大量的实验才可以活的比较明显的结果。为了缓解这种限制，出现了很多技术来缩减评估的方差又不用增加样本容量。3二、研究现状4大多数的方差缩减技术是通过人工地诱导输出回应之间的相关性或者检索输入变量和输出回应之间固有的相关性来提高统计的有效性。原始的蒙特卡洛方法是获得网络可靠性的最基本仿真技术，但是对于可靠性比较高的网络，需要非常多的实验才可以获得比较明显的结果；Kumamotoetal.引进了一种诱导副本之间的负相关性的匕首抽样设计来改进原始的蒙特卡洛估计；konaketal.使用块抽样来改进匕首抽样方法；Rubinstein&Samorodnitsky通过运用公共随机数和对偶变量技术来诱导副本之间的相关性；karp&Luby使用系统的失败集的知识来充分利用其内部固有的相关性来改进可靠性评估；Easton&Wong提出了一种顺序结构和destruction技术，其可以充分利用抽样序列的排列属性并保证减小可靠性估计的方差；Elperinetal.提出了一种将边缘排列空间分区并在数值上计算考虑到边缘排列的条件网络可靠性的排列蒙特卡洛方法。Elperinetal.在评估高可靠性网络的可二、研究现状5靠性时使用一个归并进程来构造条件蒙特卡洛估计；Cristian使用分层抽样，充分利用输出回应和用来将输入空间划分为可管理的更小的空间的分层变量之间的相关性来估计去故障覆盖的可能性。

方差缩减技术除了人工诱导或者利用其内部固有的相关性之外，重要性抽样方法通过强调抽样轨迹来增强器统计有效性。对于稀有事件的仿真，重要性抽样技术是最有潜力实现将方差缩减几个数量级的技术。Fishman&Shaw第一次使用分解程序将状态机分成可操作集、失败集和不确定集，并将所有的抽样工作分配给不确定集中。Cancela&Khadiri基于连接到目的结点的状态将网络递归的划分为几个子网，并对明显失败的子网不分配任何的抽样工作，虽然每一阶段节约的抽样工作是有限的，但是累积的抽样节约可以明显的缩减方差。Cancela&Khadiri又进一步使用了串并联缩减技术来缩减子网的大小。他们有通过避免相同的多余计算，使得执行时间明显减小。（续）三、算法设计6问题描述对于一个无向的通信网络，由节点集V，m条链接集E，目的节点集K。如果在K中的所有节点都是可链接的，那么网络G就是K-connected。如果网络G是K-connected，那么其对应的系统就是认为是可以工作的，我们的目标就是估计系统可以工作的概率。网络G的各个操作是相互独立的并被认为是随机的出现故障。令，是相互独立的伯努利随机变量且第i条链接是可以工作的其他i=1,2,…,m令是第i条链接可以工作的概率。三、算法设计7代表状态向量，其对应的系统回应是：如果状态为X的网络G是K-connected,其他。那么其对应的系统可靠性为：其中其他三、算法设计8简单抽样由于随着m的增大，对于R(G)的穷举计算是不可行的，因此可以用根据X对应的f(X)对状态集进行抽样来估计R(G)。n为样本容量。对应的可靠性估计为：对应的方差：重要性抽样对于一个普通的网络，在目的节点中任意的挑选一个，在E中存在个链接：，根据这个链接将网络G划分为+1个子网，子网是链接不能正常工作，而可以正常工作。是这个链接都不能工作的子网，很明显和是相互排斥的。然后将所有的n个抽样工作分配给，而中不用做任何抽样。三、算法设计9令，j=2,3,…,然后将n个样本按照比例额分配给各个子网，子网对应的样本良好为

。递归重要性抽样如果仅仅对网络G是用这种重要性抽样，而对于子网仍使用原始的抽样方法估计其可靠性，那么整个网络G的可靠性R(G)可以表示为：三、算法设计10其对应的方差为：针对子网中的不可确定网络，可以看作为一单独普通的网络，并对其使用重要性抽样方法评估其可靠性，那么整个网络G的可靠性为：这种重要性抽样方法被递归的应用到每一个子网上，直到子网的状态是确定的（failed或者K-connected）。对于高可靠性的网络而言，虽然在明显失败的网络中没有浪费抽样工作的效益不很明显，但是在递归工作中的累计效果可已达到明显的方差缩减效果。三、算法设计11预分配由于分层抽样需要在每一层内进行抽样，那么当网络处于确定状态，或者抽样预算不足以在每一不确定子网对应的普通网络中进行抽样时，会造成分成抽样方法的停止。因此对于每一个不确定的子网进行预分配两个“抽样名额“，并使用我们提出的重要性分层抽样方案来估计网络的可靠性。预分配不仅可以对方差进行估计，同时可以推迟递归分层抽样进程的终止，因此增强了分层的有效性。串并联缩减

当进行递归重要性分层抽样时，使用Cacela&Khadir提出的串并联缩减技术来简化网络，以此来增强计算的有效性。串联缩减技术是指，当某一普通节点的度为2时，可以用一个连接代替原来链接次普通节点的两条链接，其成功的概率是原来两条链接成功的概率之积，并移除该普通节点；并联缩减技术是指，当出现两条平行的链接，用一条链接代替原来的两条链接，其成功的概率为原来两条链接至少有一条链接正常的概率。三、算法设计12重要性抽样算法（ImportanceSampling，IS）AlgorithmIS() 1.检测递归的终止条件：

（a）如果是那么就直接返回。

（b）如果是那么将加到上，将

加到上并返回。 2.对网络进行串并联简化操作。 3.在中任意选择一个目的节点，依据链接到选择的目的节点的b条链

接的状态将网络划分为子网和目标集。 4.令 5.将抽样样本按照比例分配给b个子网。 6.对于每一个子网调用IS()。

三、算法设计13重要性分层抽样算法（ImportanceandstratifiedSampling，IS+ST）AlgorithmIS+ST()： 1.检测递归的终止条件：

（a）如果是那么就直接返回。

（b）如果是那么将加到上。 2.对网络进行串并联简化操作。 3.在中任意选择一个目的节点，依据链接到选择的目的节点的b条链

接的状态将网络划分为子网和目标集。 4.令

下面是经判断抽样任务是否足够预分配，如果不够那么就调用重要性抽样

方法，否则则递归调用重要性分层抽样方法。三、算法设计14重要性分层抽样算法（续）

5.如果{

那么调用IS()

同时将增加到，将增加到}

否则{

令

并对每一个子网调用IS+ST()}。重要性分层抽样算法的调初始用过程1.设置全局变量和。2.调用IS+ST()。3.报告网络的可靠性

和相应的标准差。四、性能评估15方差分析对于最初的网络G划分的个子网，对于每一个子网来说，其可靠性为，对应的伯努利状态的方差为

。令。由于是明显失败的子网，所以对应有。那么整个网络的可靠性为使用原始抽样方法对R(G)进行估计的方差为：重要性抽样四、性能评估16考虑不将抽样工作浪费在明显失败的子网那么网络G的可靠性估计为：那么用原始的抽样方法对的估计为：其中：其对应的方差：四、性能评估17分层抽样

分层抽样中网路的可靠性估计为：对应的方差为：其中：四、性能评估18由于可得，对于重要性抽样方法可靠性估计为：对应方差：四、性能评估19重要性分层抽样类似的，重要性分层抽样方法的重要性估计为：其对应的方差为：四、性能评估20递归应用当重要性抽样的思想被递归的运用在划分后求子网可靠性时，对应的方差：类似的对于两层的重要性分层抽样来说，子网页使用分层抽样，对应的方差：由于所以方差相对减小。四、性能评估21实验分析两种实验模型如右图：一共20个结点，30条链接，其中源节点1和汇点20作为目的节点。所有链接可以工作的概率分别设置为p=0.50,0.90,0.99和0.999进行仿真实验。四、性能评估22如右图：一共36个结点，60条链接，其中四个角的结点作为目的节点。所有链接可以工作的概率分别设置为p=0.50,0.90,0.99和0.999进行仿真实验。四、性能评估23预分配的影响四、性能评估24基于上述实验的结果可以得到如下结论：IS+ST和IS+ST0都是无偏的。IS+ST比IS+ST0统计上更加有效，随着链接的可正常运行概率的增长，预分配对方差的缩减更明显，因为未预分配的方法在分层抽样时可能导致分层进程很快结束。而预分配进程在分配抽样工作时事先对每一个子网预分配2个抽样指标，因此使得方法可以更进一步的分层来检索分层的统计有效性。

在计算时间上两种方法之间没有明显差别，但有些时候预分配方法的分层进程检索子网可能会导致计算时间上比未预分配方法的花费的代价要高。四、性能评估25其他方法比较（IS+ST，IS，