Реферат: Способ определения живучести связи (вероятности связности)
СПОСОБ ОПРЕДЕЛЕНИЯЖИВУЧЕСТИ.
Определениюживучести связи (вероятности связности) между двумя конкретными узлами сети iи jпосвящен целый ряд работ [1-5]. Однако расчет точного ее назначения сопряжен сбольшими вычислительными трудностями. Представляет интерес найти простой способопределения вероятности связности сети, который позволял бы оперативно ивручную проводить на стадии проектирования оценку различных вариантов ихпостроения.
Рассмотримсеть той же мостиковой структуры, что и в [1] (рис.1). Для простоты будемполагать вероятности исправного функционирования всех ребер сети одинаковыми иравными р, а неисправногофункционирования — равными q=1-p. Дляоценки живучести воспользуемся методом прямого перебора состояний элементовсети связи [5]. На основании биноминального закона вероятность пребывания сетисвязи в состоянии, когда iлюбых ребер сети отказали,<img src="/cache/referats/7467/image002.gif" v:shapes="_x0000_i1025"><img src="/cache/referats/7467/image004.gif" v:shapes="_x0000_i1026">биноминальный коэффициент; N – число ребер сети.
Например, для сети,изображенной на рис. 1, живучесть связи р13зависит от следующей
2
1
3
4 Рис № 1.
<img src="/cache/referats/7467/image005.gif" v:shapes="_x0000_s1029 _x0000_s1032 _x0000_s1026 _x0000_s1027 _x0000_s1028 _x0000_s1030 _x0000_s1031">совокупности независимых событий: исправногосостояния сети в целом – вероятность этого события равна р3;повреждения любого одного ребра сети – вероятность <img src="/cache/referats/7467/image007.gif" v:shapes="_x0000_i1027"> одновременного повреждениялюбых двух ребер сети, за исключением двух случаев, когда оба ребра подходят кузлу 1 или к узлу 3 – вероятность<img src="/cache/referats/7467/image009.gif" v:shapes="_x0000_i1028"> одновременногоповреждения трех ребер сети, подходящих к узлу 2 или 4 – вероятность 2р2q3.
Суммируявсе вероятности независимых событий, получаем искомое выражение :
<img src="/cache/referats/7467/image011.gif" v:shapes="_x0000_i1029">
что полностью совпадает полученными результатами в [1].
Аналагичнодля всех остальных пар узлов сети рис. № 1.
<img src="/cache/referats/7467/image013.gif" v:shapes="_x0000_i1030">
<img src="/cache/referats/7467/image015.gif" v:shapes="_x0000_i1031">
Из анализа видно, что
<img src="/cache/referats/7467/image017.gif" v:shapes="_x0000_i1032">
Связаннойсетью являются сеть, в которой любой из узлов соединен с остальными узламисети. Вероятность связанности сети рис. № 1
<img src="/cache/referats/7467/image019.gif" v:shapes="_x0000_i1033">
таккак эта сеть допускает все одиночные повреждения ребер и восемь двойныхповреждений ребер. Вероятность связности сети меньше или равна живучести связимежду любой парой узлов сети, в данном случае рс<р13.
Сточки зрения характеристики сети интерес представляют вероятность рс,минимальная рмин имаксимальная рмакс живучести связи между любой парой узлов сети исоотношения между ними. Для сети рис №1: рс< рмин=р13< р12=р14=р23=р34< р24 =рмакс.
Аналогично можно найти выражения длявероятности связности полносвязных сетей. Для сети с тремя вершинами (n=3)
<img src="/cache/referats/7467/image021.gif" v:shapes="_x0000_i1034"> (1)
для n=4;
<img src="/cache/referats/7467/image023.gif" v:shapes="_x0000_i1035"> (2)
для n=5;
<img src="/cache/referats/7467/image025.gif" v:shapes="_x0000_i1036"> (3)
для n=6;
<img src="/cache/referats/7467/image027.gif" v:shapes="_x0000_i1037"> (4)
Длярс при n=7….10 расчетные формулы не приводятся из-загромоздкости.
Вероятность связности для кольцевых сетей связи,т.е. сетей, у которых степень для каждой вершины равна 2 (степенью вершины dназываются число граней графа сети, инцидентных данной вершине [6]),
<img src="/cache/referats/7467/image029.gif" v:shapes="_x0000_i1038">
На рис 2 определена зависимость рсот р для кольцевых сетей при различных n.Из ее анализа видно, что вероятность связностикольцевых сетей падает с увеличениемчисла узлов сети при одних и тех же значениях р.
n=3
4
5
7
10
p
0 0,2 0,4 0,6 0,8
1
0,8
0,6
0,4
0,2
рс
<img src="/cache/referats/7467/image030.gif" v:shapes="_x0000_s1168 _x0000_s1153 _x0000_s1145 _x0000_s1088 _x0000_s1043 _x0000_s1033 _x0000_s1034 _x0000_s1035 _x0000_s1036 _x0000_s1037 _x0000_s1038 _x0000_s1039 _x0000_s1040 _x0000_s1041 _x0000_s1042 _x0000_s1044 _x0000_s1045 _x0000_s1046 _x0000_s1047 _x0000_s1048 _x0000_s1049 _x0000_s1050 _x0000_s1051 _x0000_s1052 _x0000_s1053 _x0000_s1054 _x0000_s1055 _x0000_s1056 _x0000_s1057 _x0000_s1058 _x0000_s1059 _x0000_s1060 _x0000_s1061 _x0000_s1062 _x0000_s1063 _x0000_s1064 _x0000_s1065 _x0000_s1066 _x0000_s1067 _x0000_s1068 _x0000_s1069 _x0000_s1070 _x0000_s1071 _x0000_s1072 _x0000_s1073 _x0000_s1074 _x0000_s1075 _x0000_s1076 _x0000_s1077 _x0000_s1078 _x0000_s1079 _x0000_s1080 _x0000_s1081 _x0000_s1082 _x0000_s1083 _x0000_s1084 _x0000_s1085 _x0000_s1086 _x0000_s1087 _x0000_s1089 _x0000_s1090 _x0000_s1091 _x0000_s1092 _x0000_s1093 _x0000_s1094 _x0000_s1095 _x0000_s1096 _x0000_s1097 _x0000_s1098 _x0000_s1099 _x0000_s1100 _x0000_s1101 _x0000_s1102 _x0000_s1103 _x0000_s1104 _x0000_s1105 _x0000_s1106 _x0000_s1107 _x0000_s1108 _x0000_s1109 _x0000_s1110 _x0000_s1111 _x0000_s1112 _x0000_s1113 _x0000_s1114 _x0000_s1115 _x0000_s1116 _x0000_s1117 _x0000_s1118 _x0000_s1119 _x0000_s1120 _x0000_s1121 _x0000_s1122 _x0000_s1123 _x0000_s1124 _x0000_s1125 _x0000_s1126 _x0000_s1127 _x0000_s1128 _x0000_s1129 _x0000_s1130 _x0000_s1131 _x0000_s1132 _x0000_s1133 _x0000_s1134 _x0000_s1135 _x0000_s1136 _x0000_s1137 _x0000_s1138 _x0000_s1139 _x0000_s1140 _x0000_s1141 _x0000_s1142 _x0000_s1143 _x0000_s1144 _x0000_s1146 _x0000_s1147 _x0000_s1148 _x0000_s1151 _x0000_s1152 _x0000_s1154 _x0000_s1155 _x0000_s1156 _x0000_s1157 _x0000_s1158 _x0000_s1159 _x0000_s1160 _x0000_s1161 _x0000_s1162 _x0000_s1163 _x0000_s1164 _x0000_s1165 _x0000_s1166 _x0000_s1167">Рис № 2.
а) б) в)
Рис 3
а) б) в)
Рис 4
<img src="/cache/referats/7467/image031.gif" v:shapes="_x0000_s1215 _x0000_s1214 _x0000_s1169 _x0000_s1170 _x0000_s1171 _x0000_s1172 _x0000_s1173 _x0000_s1174 _x0000_s1175 _x0000_s1178 _x0000_s1179 _x0000_s1188 _x0000_s1180 _x0000_s1181 _x0000_s1182 _x0000_s1183 _x0000_s1184 _x0000_s1185 _x0000_s1186 _x0000_s1187 _x0000_s1189 _x0000_s1190 _x0000_s1191 _x0000_s1192 _x0000_s1193 _x0000_s1194 _x0000_s1195 _x0000_s1196 _x0000_s1197 _x0000_s1198 _x0000_s1199 _x0000_s1200 _x0000_s1201 _x0000_s1202 _x0000_s1203 _x0000_s1204 _x0000_s1205 _x0000_s1206 _x0000_s1208 _x0000_s1209 _x0000_s1210 _x0000_s1211 _x0000_s1212 _x0000_s1213">Напрактике довольно редко встречаются полносвязные сети. Обычно бывают сети снебольшимистепенями вершин. Имеется большое семейство графов (так называемыхравнопрочных), в которых степень вершины d,число вершин nи общее число граней mсвязаны следующимсоотношением: d=2m/n (при n>2).
Напримердля шестиугольника (n=6) без резервирования связей можно построить четыреразличных графа с d=2, 3, 4, 5. Вероятности связности этих графовопределяется следующими выражениями:
Приd=2(рис. 3, а)
<img src="/cache/referats/7467/image033.gif" v:shapes="_x0000_i1039"> (5)
при d=3(рис. 3, б)
<img src="/cache/referats/7467/image035.gif" v:shapes="_x0000_i1040"> (6)
при d=4(рис. 3, в)
<img src="/cache/referats/7467/image037.gif" v:shapes="_x0000_i1041"> (7)
Приn=8можно построить шесть различных графов с d=2…..7; вероятностьсвязности этих графов определитсяследующими выражениями:
d=2(рис. 4, а)
<img src="/cache/referats/7467/image039.gif" v:shapes="_x0000_i1042"> (8)
d=3(рис. 4, б)
<img src="/cache/referats/7467/image041.gif" v:shapes="_x0000_i1043"> (9)
d=4(рис. 4, в)
<img src="/cache/referats/7467/image043.gif" v:shapes="_x0000_i1044">(10)
d=2
3
4
5
p
0 0,2 0,4 0,6 0,8 1
1
0,8
0,6
0,4
0,2
рс
Рис. 5
p
d=2
3
4
5
0 0,2 0,4 0,6 0,8 1
1
0,8
0,6
0,4
0,2
рс
Рис. 6
6
7
<img src="/cache/referats/7467/image044.gif" v:shapes="_x0000_s1362 _x0000_s1218 _x0000_s1219 _x0000_s1220 _x0000_s1221 _x0000_s1222 _x0000_s1223 _x0000_s1224 _x0000_s1225 _x0000_s1226 _x0000_s1227 _x0000_s1228 _x0000_s1229 _x0000_s1230 _x0000_s1231 _x0000_s1232 _x0000_s1233 _x0000_s1234 _x0000_s1235 _x0000_s1236 _x0000_s1237 _x0000_s1238 _x0000_s1239 _x0000_s1240 _x0000_s1241 _x0000_s1242 _x0000_s1243 _x0000_s1244 _x0000_s1245 _x0000_s1246 _x0000_s1247 _x0000_s1248 _x0000_s1249 _x0000_s1250 _x0000_s1251 _x0000_s1252 _x0000_s1253 _x0000_s1254 _x0000_s1255 _x0000_s1256 _x0000_s1257 _x0000_s1258 _x0000_s1259 _x0000_s1260 _x0000_s1261 _x0000_s1262 _x0000_s1263 _x0000_s1264 _x0000_s1265 _x0000_s1266 _x0000_s1267 _x0000_s1268 _x0000_s1269 _x0000_s1270 _x0000_s1271 _x0000_s1272 _x0000_s1273 _x0000_s1274 _x0000_s1275 _x0000_s1276 _x0000_s1277 _x0000_s1278 _x0000_s1279 _x0000_s1280 _x0000_s1281 _x0000_s1282 _x0000_s1283 _x0000_s1284 _x0000_s1285 _x0000_s1286 _x0000_s1287 _x0000_s1288 _x0000_s1289 _x0000_s1290 _x0000_s1291 _x0000_s1292 _x0000_s1293 _x0000_s1294 _x0000_s1295 _x0000_s1296 _x0000_s1297 _x0000_s1298 _x0000_s1299 _x0000_s1300 _x0000_s1301 _x0000_s1302 _x0000_s1303 _x0000_s1304 _x0000_s1305 _x0000_s1306 _x0000_s1307 _x0000_s1308 _x0000_s1309 _x0000_s1310 _x0000_s1311 _x0000_s1312 _x0000_s1313 _x0000_s1314 _x0000_s1315 _x0000_s1316 _x0000_s1317 _x0000_s1318 _x0000_s1319 _x0000_s1320 _x0000_s1321 _x0000_s1322 _x0000_s1323 _x0000_s1324 _x0000_s1325 _x0000_s1326 _x0000_s1327 _x0000_s1328 _x0000_s1329 _x0000_s1330 _x0000_s1331 _x0000_s1332 _x0000_s1334 _x0000_s1335 _x0000_s1336 _x0000_s1338 _x0000_s1339 _x0000_s1340 _x0000_s1346 _x0000_s1347 _x0000_s1348 _x0000_s1349 _x0000_s1351 _x0000_s1352 _x0000_s1354 _x0000_s1356 _x0000_s1357 _x0000_s1358 _x0000_s1359 _x0000_s1360 _x0000_s1361"> <img src="/cache/referats/7467/image045.gif" v:shapes="_x0000_s1485 _x0000_s1505 _x0000_s1364 _x0000_s1365 _x0000_s1366 _x0000_s1367 _x0000_s1368 _x0000_s1369 _x0000_s1370 _x0000_s1371 _x0000_s1372 _x0000_s1373 _x0000_s1374 _x0000_s1375 _x0000_s1376 _x0000_s1377 _x0000_s1378 _x0000_s1379 _x0000_s1380 _x0000_s1381 _x0000_s1382 _x0000_s1383 _x0000_s1384 _x0000_s1385 _x0000_s1386 _x0000_s1387 _x0000_s1388 _x0000_s1389 _x0000_s1390 _x0000_s1391 _x0000_s1392 _x0000_s1393 _x0000_s1394 _x0000_s1395 _x0000_s1396 _x0000_s1397 _x0000_s1398 _x0000_s1399 _x0000_s1400 _x0000_s1401 _x0000_s1402 _x0000_s1403 _x0000_s1404 _x0000_s1405 _x0000_s1406 _x0000_s1407 _x0000_s1408 _x0000_s1409 _x0000_s1410 _x0000_s1411 _x0000_s1412 _x0000_s1413 _x0000_s1414 _x0000_s1415 _x0000_s1416 _x0000_s1417 _x0000_s1418 _x0000_s1419 _x0000_s1420 _x0000_s1421 _x0000_s1422 _x0000_s1423 _x0000_s1424 _x0000_s1425 _x0000_s1426 _x0000_s1427 _x0000_s1428 _x0000_s1429 _x0000_s1430 _x0000_s1431 _x0000_s1432 _x0000_s1433 _x0000_s1434 _x0000_s1435 _x0000_s1436 _x0000_s1437 _x0000_s1438 _x0000_s1439 _x0000_s1440 _x0000_s1441 _x0000_s1442 _x0000_s1443 _x0000_s1444 _x0000_s1445 _x0000_s1446 _x0000_s1447 _x0000_s1448 _x0000_s1449 _x0000_s1450 _x0000_s1451 _x0000_s1452 _x0000_s1453 _x0000_s1454 _x0000_s1455 _x0000_s1456 _x0000_s1457 _x0000_s1458 _x0000_s1459 _x0000_s1460 _x0000_s1461 _x0000_s1462 _x0000_s1463 _x0000_s1464 _x0000_s1465 _x0000_s1466 _x0000_s1467 _x0000_s1468 _x0000_s1469 _x0000_s1470 _x0000_s1471 _x0000_s1472 _x0000_s1473 _x0000_s1474 _x0000_s1475 _x0000_s1476 _x0000_s1477 _x0000_s1478 _x0000_s1479 _x0000_s1480 _x0000_s1481 _x0000_s1482 _x0000_s1483 _x0000_s1484 _x0000_s1486 _x0000_s1487 _x0000_s1488 _x0000_s1489 _x0000_s1490 _x0000_s1491 _x0000_s1492 _x0000_s1493 _x0000_s1494 _x0000_s1495 _x0000_s1496 _x0000_s1497 _x0000_s1498 _x0000_s1499 _x0000_s1500 _x0000_s1501 _x0000_s1502 _x0000_s1503 _x0000_s1504">Расчетныеформулы для рс при d=5 и 6из-за громоздкости не приводятся.
Нарис 5 и 6 представлены зависимости вероятности связности сети с n=6, 8соответственно при различных d(сплошные линии),построенные по формулам (5) – (10). Из рисунков видно, что увеличениевероятности связности сети с увеличением dпри неизменном pобъясняется тем, что с увеличением dвозрастает разветвленностьсети связи.
Ксожалению, ловольно трудно получить аналитическое выражение для вероятностисвязности сети рассматренного семейство графов при различных d и n, за исключением полносвязных сетей с d = n – 1 [см.выражение (1) –(4)]. По этому целесобразно определять верхнюю груницу вероятности связностиграфов. Если граф связный, то в нем не может быть изолированных вершин. В этомслучае каждой вершине должна быть инцидента по крайней мере одна ветвь.
Пусть Ai – событие, когда не существуетнеповрежденных ветвей, инцидентных вершине i,p(Ai) – вероятность этого события; 1 – p(Ai)–вероятностьдополнительного события, когда существует по крайней мере одна целая ветвь,инцидентная вершине i, Поэтому вероятность того, что у всех вершин есть покрайне мере одна целая ветвь, т.е. есть связана, ограничена неравенством:
<img src="/cache/referats/7467/image047.gif" v:shapes="_x0000_i1045"> (11)
На рис. 5,6 представлены зависимости(11) для n=6, иd=2…..7(штриховые линии). Сравнение кривых показывает, что верхнюю границу вероятностисвязности сети, особенно при больших d.
Такимобразом, полученная простая верхняя оценка вероятности связности равнопрочныхсетей связи дает шорошее приближение к точному значению вероятности связностисети при больших значениях d.