星形网络上的最可靠广播源问题.pdfVIP

第34卷第 1期 杭 州 电子 科 技 大学 学报 Vo1．34。No．1 2014年 1月 Journal of Hangzhou Dianzi University Jan．2014 doi：10．3969／j．issn．1001—9146．2014．01—013 星形网络上的最可靠广播源 问题 周 瑜 ，陈光亭 (杭州电子科技大学理学院，浙江 杭州310018) 摘要：不可靠网络上最可靠广播源问题是网络可靠性问题的一种。该文讨论了星形网络中最可靠 广播源问题与最可靠双广播源问题，并针对这两个问题分别给出了两个多项式时间算法。 关键词：最可靠广播源；可达概率；择优概率 中图分类号：TN711．6 文献标识码 ：A 文章编号：1001—9146(2014)01—0057—03 0 引 言 最可靠广播源(MostReliableSource，MRS)问题是网络可靠性问题的一种。一般网络上的MRS 问题 属于#P—hard问题 。但是，在一些特殊的网络中，MRS问题存在多项式算法。树上的MRS 问题存在一 个平方算法 以及一个线性 算法；系列平行图上的MRS问题存在一个线性算法 ；圈树中的MRS 问题 存在一个平方算法 。本文主要讨论了星形网络中的最可靠广播源问题以及最可靠双广播源问题(2—M0st RelibaleSources，2MRS)，并分别针对这两个问题的两种不同模型给出了相应的多项式时间算法。 1 定义与符号 令G=(V，E，P，Q)表示星形网络，其中，V表示顶点集合，E表示边集合，P={(p+()，P一())lv∈ V}表示G中每个节点的发送概率与接收概率构成的点对集合，Q{q(，)：(u，v)∈E}表示G中每条边的 工作概率集合。不妨设V={1，2，…，n，n+1}，其中节点n+1表示星形图的中心。令Pr(“，)表示信息从 结点u成功传递至结点v的概率。不妨称Pr(，)为可达概率。特殊地，Vu，v∈V，(u，v)∈E，Pr(，)= P+(u)q(U，3／)p一()，口(11,，)=q(3／，11,)，Pr(11,，XI)=1。在G中，MRS 问题的两种模型如下： E『[u]=∑Pr(，，) … lmax{E[u】]：u】∈V} JM『[u·]=m2nPr~ut， …，，】、 m【ax{E[U1]：U1∈V} 进一步地，令F(XI1，XI2；)=max{Pr(1，)，Pr(M2，口)}，其中ul，u2，v∈E。不妨称F(1，M2；)为择 优概率。2MRS问题的两种模型如下： fE[u。，u]=∑ (，；) … 1 ， max{E[Ul，U2]：U1，U2∈V，u1≠U2} -fM[u·，uz]vEvF(“·12,2；) …，，、 m【ax{M[u1，u2]：u1，u2∈V，u1≠U2} 特殊地，令G=(V，E，P，Q)表示无向加权星形图，其中lVI=n+1。不妨设V={1，2，…，n，n+1}，其 中节点n+1表示星形图的中心。 收稿 日期：2012—12—18 作者简介：周瑜 (1985一)，男，山西山阴人，在读研究生，组合优化 58 杭 州 电子 科 技 大 学 学 报 2014年 2 星形网络中的MRS问题 首先，对于