摘要
给出了一种求满足传输量要求的时间和成本约束下网络的所有极小状态(下界点集)的简单方法.讨论了基于下界点集合的可靠度的容斥原理公式,直接应用容斥原理公式会有很多相互抵消的项.如果所有的数据通过k条不相交的极小路径同时传输,只需讨论r-1项和r(1<r≤k)项组合相消情况(假设k小于下界点数),其他组合项的相消情况也能确定.最后给出了确定相消项的算法.利用所给算法使可靠度的计算公式得到大大简化.
A simple method was proposed to generate all minimal system states fulfilling the demand, time, and budget constraints (all lower boundary points). Inclusion-exclusion formula with the lower boundary points was discussed. There are many cancelling terms in the direct expansion of the probability of a union of events, so an algorithm was proposed to determine the canceling terms. All data were supposed to be transmitted through k disjoint minimal paths simultaneously. It was pointed out that if all the pairs of canceling terms that unions of r-1 terms and r terms( 1 〈 r〈~k) were found out, the canceling terms of other unions in inclusion-exclusion formula could be determined. The reliability formula was greatly simplified by using the proposed algorithm.
出处
《东北大学学报(自然科学版)》
EI
CAS
CSCD
北大核心
2013年第11期1537-1541,共5页
Journal of Northeastern University(Natural Science)
基金
国家自然科学基金资助项目(51034002)
辽宁省自然科学基金资助项目(201202074)
关键词
时间约束
成本约束
随机流网络
容斥原理公式
可靠度
time constraint
cost constraint
stochastic-flow network
inclusion-exclusionformula
reliability