Главная страница
Навигация по странице:

  • Цель работы

  • Выполнение работы

  • Дополнительное задание

  • ПРИЛОЖЕНИЕ А Листинг программы

  • ПРИЛОЖЕНИЕ Б Листинг дополнительного задания

  • Отчет защищен с оценкой преподаватель ассистент


    Скачать 232.29 Kb.
    НазваниеОтчет защищен с оценкой преподаватель ассистент
    Дата07.02.2023
    Размер232.29 Kb.
    Формат файлаdocx
    Имя файлаLR3.docx
    ТипОтчет
    #924823

    ГУАП

    КАФЕДРА № 41

    ОТЧЕТ
    ЗАЩИЩЕН С ОЦЕНКОЙ

    ПРЕПОДАВАТЕЛЬ

    ассистент










    Н. В. Апанасенко

    должность, уч. степень, звание




    подпись, дата




    инициалы, фамилия




    ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ

    АНАЛИЗ РАБОТЫ ЭЛЕМЕНТАРНОЙ СИСТЕМЫ МНОЖЕСТВЕННОГО ДОСТУПА НА ОСНОВЕ АППАРАТА МАРКОВСКИХ ПРОЦЕССОВ

    по курсу: ВЫЧИСЛИТЕЛЬНЫЕ СЕТИ, СИСТЕМЫ И ТЕЛЕКОММУНИКАЦИИ







    РАБОТУ ВЫПОЛНИЛ

    СТУДЕНТ ГР. №

    4017










    А.А. Леонтьева










    подпись, дата




    инициалы, фамилия


    Санкт-Петербург 2022

    Цель работы: анализ работы элементарной системы множественного доступа. Оценка среднего количества абонентов, находящихся в системе.

    Краткие теоретические сведения:

    Вероятности переходов из одного состояния в другое:

    1. Вероятность перехода из состояния «ноль» в произвольное состояние j.

    Переход из состояния 0 в состояние j может произойти, только когда количество абонентов, у которых появилось сообщение будет равно j, то есть . Так как распределено по закону Пуассона получаем:



    2. Вероятность перехода из i-го состояния в i-1.

    Событие перехода из состояния i в состояние i-1 означает, что новых абонентов не появилось, и один абонент передал сообщение. То есть и :



    Вероятность «успеха» (один абонент передавал, остальные не передавали), определяется как:



    Вероятность отсутствия новых абонентов определяется как:



    3. Вероятность остаться в состоянии i.

    Переход из состояния i в i. может произойти в случае, если один абонент передал сообщение, и один новый абонент появился, или если новых абонентов не было, и ни один не передал:



    Вероятность того, что ни один абонент не передал сообщение определяется как:



    4. Вероятность перехода из состояния i в состояние j.

    Переход из состояния i в j может произойти в случае, если один абонент передал сообщение и появились (j-i+1) абонентов, или если ни один не передал сообщение и появились (j-i) абонентов. Вероятность данного события определяется как:



    Используя описанные выше вероятности переходов из одного состояния в другое, можно сформировать систему усеченных линейных уравнений, для фиксированного значения :


    Решая данную систему усеченных линейных алгебраических уравнений (количество уравнений K), для фиксированного , можно получить вектор стационарного распределения, каждое из значений означает вероятность того, что в системе находится i абонентов.

    Тогда оценить среднее количество абонентов, находящихся в системе множественного доступа можно как:

    ,

    где .

    Выполнение работы

    Код программы представлен в приложении А.

    Создана матрица переходных состояний для 10 слотов и λ=0.05 (рисунок 1).



    Рисунок 1 - Матрица переходных состояний

    Найдены коэффициенты перед pi, после чего решена система линейных уравнений (рисунок 2).



    Рисунок 2 – Решение системы линейных уравнений

    Высчитано среднее количество абонентов (рисунок 3).



    Рисунок 3 – Среднее количество абонентов

    Построены графики зависимости среднего количества абонентов от значения входного потока. На этой же системе координат построен график из первой лабораторной работы (рисунок 4-7).



    Рисунок 4 – График зависимости среднего количества абонентов от значения входного потока для 10 слотов



    Рисунок 5 – График зависимости среднего количества абонентов от значения входного потока для 50 слотов


    Рисунок 6 – График зависимости среднего количества абонентов от значения входного потока для 100 слотов



    Рисунок 6 – График зависимости среднего количества абонентов от значения входного потока для 1000 слотов

    При значении входного потока от среднее количество абонентов линейно возрастает, так как вероятность появления пользователя в слоте тоже линейно возрастает. После значения 0,35 графики расходятся.
    Дополнительное задание

    Листинг дополнительного задания представлен в приложении Б.

    Написать критерий Смирного-Колмогорова для одной выборки, которая является нормальным распределением и сортирована вставкой.
    ВыводЯ изучила способы нахождения стационарного распределения Марковской цепи с конечным числом состояний и получила навыки моделирования Марковских цепей.

    Сделан вывод, что от среднее количество абонентов линейно возрастает, так как вероятность появления пользователя в слоте тоже линейно возрастает.

    ПРИЛОЖЕНИЕ А

    Листинг программы

    import numpy as np

    import matplotlib.pyplot as plt

    import math

    import random

    from random import randint

    from scipy.stats import poisson

    from scipy.stats import binom
    l = 0 #интенсивность входного потока

    lambd_list = []

    for i in range(10):

      l += 0.05

      lambd_list.append(l)

    k = 100000 # количество слотов

    P_come_lambda = [] # количество абонентов, которое пришло в слот

    for i in range(len(lambd_list)):

      P_come_lambda.append(np.random.poisson(lambd_list[i],k))

    print(P_come_lambda)

    N_beginning=[[0 for i in range(k)] for j in range(len(lambd_list))] # количества абонентов в началах слотов для всех лямбд

    N_final=[[0 for i in range(k)] for j in range(len(lambd_list))] # количества абонентов в концах слотов для всех лямбд

    for j in range(len(lambd_list)): 

      for i in range(k): # заполнение количеств абонентов для одной лямбды

        Rk=0 # количество передающих абонентов

        if N_beginning[j][i]!=0:

          Rk=np.random.binomial(N_beginning[j][i],1/N_beginning[j][i],1)

        Indicator = 0 

        if(Rk==1):

          Indicator=1

        N_final[j][i] = N_beginning[j][i]+P_come_lambda[j][i]-Indicator

        if(i
            N_beginning[j][i+1]=N_final[j][i]

    N_avg = [[] for i in range(len(lambd_list))] # массив средних значений количеств абонентов для каждой лямбды

    for i in range(len(lambd_list)): # подсчёт средних количеств абонентов

      N_avg[i] = sum(N_final[i])/k

      print(N_avg[i])

    k=10 # количество слотов

    # матрица переходных состояний

    P_come_lambda = [[[[] for j in range(k)] for i in range(k)] for l in range(len(lambd_list))] # количество абонентов, которое пришло в слоте k для каждой лямбды

    for l in range(len(lambd_list)):

      for i in range(k): #состояние, в которое осуществляется переход

        for j in range(k): #состояние, из которого осуществляется переход

          if i==0 and j<2: # для переходов в состояние П0

           K=0

           P_come_lambda[l][i][j]=poisson.pmf(k=K, mu=lambd_list[l])

          elif j==0 or j==1: # для переходов из состояний П0 и П1

            K=i

            P_come_lambda[l][i][j]=lambd_list[l] ** (K) * math.e ** -lambd_list[l] / math.factorial(K)

          elif j==i+1: # для переходов из состояния i в состояние i-1

            K=0

            P_come_lambda[l][i][j] = lambd_list[l] ** (K) * math.e ** -lambd_list[l] / math.factorial(K) * (math.factorial(j) / math.factorial(j-1)) * (1/j) *(1-1/j) ** (j-1)

          elif j
            K=i-j+1

            P_come_lambda[l][i][j] = lambd_list[l] ** (K) * math.e ** -lambd_list[l] / math.factorial(K) * (math.factorial(j) / math.factorial(j-1)) * (1/j) *(1-1/j) ** (j-1)

            K=i-j # ни 1 абонент не передал сообщение

            P_come_lambda[l][i][j]+=lambd_list[l] ** (K) * math.e ** -lambd_list[l] / math.factorial(K) * (1 - math.factorial(j) / math.factorial(j-1) * (1/j) *(1-1/j) ** (j-1))

          elif j==i: # для переходов из состояния i в состояние i

            K=1 # 1 абонент передал сообщение, а 1 абонент пришёл

            P_come_lambda[l][i][j] = lambd_list[l] ** (K) * math.e ** -lambd_list[l] / math.factorial(K) * (math.factorial(j) / math.factorial(j-1)) * (1/j) *(1-1/j) ** (j-1)

            K=0 # ни 1 абонент не передал сообщение и никто не пришёл

            P_come_lambda[l][i][j] += lambd_list[l] ** (K) * math.e ** -lambd_list[l] / math.factorial(K) * (1 - math.factorial(j) / math.factorial(j-1) * (1/j) *(1-1/j) ** (j-1))

          else:

            P_come_lambda[l][i][j]=0

    print(P_come_lambda[0])

    for i in range(k):

      print(P_come_lambda[0][i])

    # для создания коэффициентов перед П отнимаем 1 от Пi,i

    for l in range(len(lambd_list)): #для каждой лямбды

      for i in range(k): #для каждого уравнения

        for j in range(k): # номер слагаемого с П

          if i==j:

            P_come_lambda[l][i][j]-=1

    print(P_come_lambda[0])

    # замена последнего уравнения условием нормировки

    for l in range(len(lambd_list)): #для каждой лямбды

      for i in range(k): #для каждого уравнения

        for j in range(k): # номер слагаемого с П

          if i==k-1:

            P_come_lambda[l][i][j]=1

    # заполнение правой части системы уравнений

    v_last=[[[] for i in range(k)] for l in range(len(lambd_list))]

    for l in range(len(lambd_list)):

      for i in range(k):

        v_last[l][i]=0

        if i==k-1:

            v_last[l][i]=1

    print(v_last[0])

    final=[]

    for l in range(len(lambd_list)):

      final.append(np.linalg.solve(P_come_lambda[l],v_last[l]))

    print(final[0])

    #среднее количество абонентов

    N_avg1 = [[] for l in range(len(lambd_list))]

    for l in range(len(lambd_list)):

      summ = 0

      for j in range(k):

        summ+=final[l][j]*j

        N_avg1[l]=summ

      print(N_avg1[l])

    fig = plt.figure() # построения графика зависимости N от λ

    ax = fig.add_subplot(111)

    ax.set_ylim(0, 10) # ограничение среднего количества абонентов до 20

    ax.set_ylabel("Среднее количество абонентов в системе, N")

    ax.set_xlabel("Интенсивность входного потока (λ)")

    ax.plot(lambd_list,N_avg1, label='Решением систем уравнений')

    ax.plot(lambd_list,N_avg, label='Подсчет кол-ва абонентов в слоте k')

    plt.legend()

    plt.grid()

    k=50

    from scipy.stats import poisson

    from scipy.stats import binom

    P_come_lambda = [[[[] for j in range(k)] for i in range(k)] for l in range(len(lambd_list))] # количество абонентов, которое пришло в слоте k

    for l in range(len(lambd_list)):

      for i in range(k): #для каждого уравнения, состояние, в которое осуществляется переход

        for j in range(k): # номер слагаемого с П; состояние, из которого осуществляется переход

          if i==0 and j<2: #верно

           K=0

           P_come_lambda[l][i][j]=poisson.pmf(k=K, mu=lambd_list[l])

          elif j==0 or j==1: #верно

            K=i

            P_come_lambda[l][i][j]=lambd_list[l] ** (K) * math.e ** -lambd_list[l] / math.factorial(K)

          elif j==i+1:

            K=0

            P_come_lambda[l][i][j] = lambd_list[l] ** (K) * math.e ** -lambd_list[l] / math.factorial(K) * (math.factorial(j) / math.factorial(j-1)) * (1/j) *(1-1/j) ** (j-1)

          elif j
            K=i-j+1

            P_come_lambda[l][i][j] = lambd_list[l] ** (K) * math.e ** -lambd_list[l] / math.factorial(K) * (math.factorial(j) / math.factorial(j-1)) * (1/j) *(1-1/j) ** (j-1)

            K=i-j # ни 1 абонент не передал сообщение

            P_come_lambda[l][i][j]+=lambd_list[l] ** (K) * math.e ** -lambd_list[l] / math.factorial(K) * (1 - math.factorial(j) / math.factorial(j-1) * (1/j) *(1-1/j) ** (j-1))

          elif j==i:

            K=1 # 1 абонент передал сообщение, а 1 абонент пришёл

            P_come_lambda[l][i][j] = lambd_list[l] ** (K) * math.e ** -lambd_list[l] / math.factorial(K) * (math.factorial(j) / math.factorial(j-1)) * (1/j) *(1-1/j) ** (j-1)

            K=0 # ни 1 абонент не передал сообщение и никто не пришёл

            P_come_lambda[l][i][j] += lambd_list[l] ** (K) * math.e ** -lambd_list[l] / math.factorial(K) * (1 - math.factorial(j) / math.factorial(j-1) * (1/j) *(1-1/j) ** (j-1))

          else:

            P_come_lambda[l][i][j]=0
    for l in range(len(lambd_list)): #для каждой лямбды

      for i in range(k): #для каждого уравнения

        for j in range(k): # номер слагаемого с П

          if i==j:

            P_come_lambda[l][i][j]-=1
    for l in range(len(lambd_list)): #для каждой лямбды

      for i in range(k): #для каждого уравнения

        for j in range(k): # номер слагаемого с П

          if i==k-1:

            P_come_lambda[l][i][j]=1
    v_last=[[[] for i in range(k)] for l in range(len(lambd_list))]

    for l in range(len(lambd_list)):

      for i in range(k):

        v_last[l][i]=0

        if i==k-1:

            v_last[l][i]=1
    final=[]

    for l in range(len(lambd_list)):

      final.append(np.linalg.solve(P_come_lambda[l],v_last[l]))
    #среднее количество абонентов

    N_avg2 = [[] for l in range(len(lambd_list))]

    for l in range(len(lambd_list)):

      summ = 0

      for j in range(k):

        summ+=final[l][j]*j

        N_avg2[l]=summ

      print(N_avg2[l])

    fig = plt.figure() # построения графика зависимости N от λ

    ax = fig.add_subplot(111)

    ax.set_ylim(0, 10) # ограничение среднего количества абонентов до 20

    ax.set_ylabel("Среднее количество абонентов в системе, N")

    ax.set_xlabel("Интенсивность входного потока (λ)")

    ax.plot(lambd_list,N_avg2, label='Решением систем уравнений')

    ax.plot(lambd_list,N_avg, label='Подсчет кол-ва абонентов в слоте k')

    plt.legend()

    plt.grid()

    k=100

    from scipy.stats import poisson

    from scipy.stats import binom

    P_come_lambda = [[[[] for j in range(k)] for i in range(k)] for l in range(len(lambd_list))] # количество абонентов, которое пришло в слоте k

    for l in range(len(lambd_list)):

      for i in range(k): #для каждого уравнения, состояние, в которое осуществляется переход

        for j in range(k): # номер слагаемого с П; состояние, из которого осуществляется переход

          if i==0 and j<2: #верно

           K=0

           P_come_lambda[l][i][j]=poisson.pmf(k=K, mu=lambd_list[l])

          elif j==0 or j==1: #верно

            K=i

            P_come_lambda[l][i][j]=lambd_list[l] ** (K) * math.e ** -lambd_list[l] / math.factorial(K)

          elif j==i+1:

            K=0

            P_come_lambda[l][i][j] = lambd_list[l] ** (K) * math.e ** -lambd_list[l] / math.factorial(K) * (math.factorial(j) / math.factorial(j-1)) * (1/j) *(1-1/j) ** (j-1)

          elif j
            K=i-j+1

            P_come_lambda[l][i][j] = lambd_list[l] ** (K) * math.e ** -lambd_list[l] / math.factorial(K) * (math.factorial(j) / math.factorial(j-1)) * (1/j) *(1-1/j) ** (j-1)

            K=i-j # ни 1 абонент не передал сообщение

            P_come_lambda[l][i][j]+=lambd_list[l] ** (K) * math.e ** -lambd_list[l] / math.factorial(K) * (1 - math.factorial(j) / math.factorial(j-1) * (1/j) *(1-1/j) ** (j-1))

          elif j==i:

            K=1 # 1 абонент передал сообщение, а 1 абонент пришёл

            P_come_lambda[l][i][j] = lambd_list[l] ** (K) * math.e ** -lambd_list[l] / math.factorial(K) * (math.factorial(j) / math.factorial(j-1)) * (1/j) *(1-1/j) ** (j-1)

            K=0 # ни 1 абонент не передал сообщение и никто не пришёл

            P_come_lambda[l][i][j] += lambd_list[l] ** (K) * math.e ** -lambd_list[l] / math.factorial(K) * (1 - math.factorial(j) / math.factorial(j-1) * (1/j) *(1-1/j) ** (j-1))

          else:

            P_come_lambda[l][i][j]=0
    for l in range(len(lambd_list)): #для каждой лямбды

      for i in range(k): #для каждого уравнения

        for j in range(k): # номер слагаемого с П

          if i==j:

            P_come_lambda[l][i][j]-=1
    for l in range(len(lambd_list)): #для каждой лямбды

      for i in range(k): #для каждого уравнения

        for j in range(k): # номер слагаемого с П

          if i==k-1:

            P_come_lambda[l][i][j]=1
    v_last=[[[] for i in range(k)] for l in range(len(lambd_list))]

    for l in range(len(lambd_list)):

      for i in range(k):

        v_last[l][i]=0

        if i==k-1:

            v_last[l][i]=1
    final=[]

    for l in range(len(lambd_list)):

      final.append(np.linalg.solve(P_come_lambda[l],v_last[l]))
    #среднее количество абонентов

    N_avg3 = [[] for l in range(len(lambd_list))]

    for l in range(len(lambd_list)):

      summ = 0

      for j in range(k):

        summ+=final[l][j]*j

        N_avg3[l]=summ

      print(N_avg3[l])

    fig = plt.figure() # построения графика зависимости N от λ

    ax = fig.add_subplot(111)

    ax.set_ylim(0, 10) # ограничение среднего количества абонентов до 20

    ax.set_ylabel("Среднее количество абонентов в системе, N")

    ax.set_xlabel("Интенсивность входного потока (λ)")

    ax.plot(lambd_list,N_avg3, label='Решением систем уравнений')

    ax.plot(lambd_list,N_avg, label='Подсчет кол-ва абонентов в слоте k')

    plt.legend()

    plt.grid()

    k=1000

    from scipy.stats import poisson

    from scipy.stats import binom

    P_come_lambda = [[[[] for j in range(k)] for i in range(k)] for l in range(len(lambd_list))] # количество абонентов, которое пришло в слоте k

    for l in range(len(lambd_list)):

      for i in range(k): #для каждого уравнения, состояние, в которое осуществляется переход

        for j in range(k): # номер слагаемого с П; состояние, из которого осуществляется переход

          if i==0 and j<2: #верно

           K=0

           P_come_lambda[l][i][j]=poisson.pmf(k=K, mu=lambd_list[l])

          elif j==0 or j==1: #верно

            K=i

            P_come_lambda[l][i][j]=poisson.pmf(k=K, mu=lambd_list[l])

          elif j==i+1:

            K=0

            P_come_lambda[l][i][j] = poisson.pmf(k=K, mu=lambd_list[l]) * (j) * (1/j) *(1-1/j) ** (j-1)

          elif j
            K=i-j+1

            P_come_lambda[l][i][j] = poisson.pmf(k=K, mu=lambd_list[l]) * (j) * (1/j) *(1-1/j) ** (j-1)

            K=i-j # ни 1 абонент не передал сообщение

            P_come_lambda[l][i][j]+=poisson.pmf(k=K, mu=lambd_list[l]) * (1 - j * (1/j) *(1-1/j) ** (j-1))

          elif j==i:

            K=1 # 1 абонент передал сообщение, а 1 абонент пришёл

            P_come_lambda[l][i][j] = poisson.pmf(k=K, mu=lambd_list[l]) * (j) * (1/j) *(1-1/j) ** (j-1)

            K=0 # ни 1 абонент не передал сообщение и никто не пришёл

            P_come_lambda[l][i][j] += poisson.pmf(k=K, mu=lambd_list[l]) * (1 - j * (1/j) *(1-1/j) ** (j-1))

          else:

            P_come_lambda[l][i][j]=0
    for l in range(len(lambd_list)): #для каждой лямбды

      for i in range(k): #для каждого уравнения

        for j in range(k): # номер слагаемого с П

          if i==j:

            P_come_lambda[l][i][j]-=1
    for l in range(len(lambd_list)): #для каждой лямбды

      for i in range(k): #для каждого уравнения

        for j in range(k): # номер слагаемого с П

          if i==k-1:

            P_come_lambda[l][i][j]=1
    v_last=[[[] for i in range(k)] for l in range(len(lambd_list))]

    for l in range(len(lambd_list)):

      for i in range(k):

        v_last[l][i]=0

        if i==k-1:

            v_last[l][i]=1

    print(v_last[0])
    final=[]

    for l in range(len(lambd_list)):

      final.append(np.linalg.solve(P_come_lambda[l],v_last[l]))
    #среднее количество абонентов

    N_avg4 = [[] for l in range(len(lambd_list))]

    for l in range(len(lambd_list)):

      summ = 0

      for j in range(k):

        summ+=final[l][j]*j

        N_avg4[l]=summ

      print(N_avg4[l])

    fig = plt.figure() # построения графика зависимости N от λ

    ax = fig.add_subplot(111)

    ax.set_ylabel("Среднее количество абонентов в системе, N")

    ax.set_xlabel("Интенсивность входного потока (λ)")

    ax.plot(lambd_list,N_avg4,  label='Решением систем уравнений')

    ax.plot(lambd_list,N_avg, label='Подсчет кол-ва абонентов в слоте k')

    plt.legend()

    plt.grid()

    plt.ylim([0, 50])
    ПРИЛОЖЕНИЕ Б

    Листинг дополнительного задания

    import math
    import matplotlib.pyplot as plt
    import numpy as np
    from scipy.stats import norm
    # вычисление эмпирической функции
    # sample - массив значений, y - аргумент функции
    def empirical_distribution(sample, y):
    counter = 0
    for x in sample:
    if x < y:
    counter += 1
    return counter / len(sample)


    def generate_normal(mu, sigma, size):
    # сортировка вставкой
    def insertion_sort(a):
    for i in range(1, len(a)):
    value = a[i] # временная переменная для сравнения чисел
    j = i - 1
    while j >= 0 and value < a[j]:
    a[j + 1] = a[j]
    j -= 1
    a[j + 1] = value
    return a

    a = np.random.normal(loc=mu, scale=sigma, size=size)
    return insertion_sort(a)


    def kolmogorov_check(real, mu, sigma):
    empirical_real = {}
    empirical_teor = {}
    D = 0
    step = 0.1
    x = mu - 3*sigma #правило трех сигм
    right = mu + 3*sigma
    while x < right:
    # считаем эмпирическую функцию для реального распределения (для выборки)
    emp_r = empirical_distribution(real, x)
    empirical_real[x] = emp_r
    # считаем для теоретического
    emp_t = norm.cdf(x, mu, sigma)
    empirical_teor[x] = emp_t
    dif = abs(emp_r - emp_t)
    if dif > D:
    D = dif
    x += step
    x = right
    # выполняем алгоритм ещё раз для правой границы (так как она не вошла при рассчёте в цикле)
    # считаем эмпирическую функцию для реального распределения (для выборки)
    emp_r = empirical_distribution(real, x)
    empirical_real[x] = emp_r
    # считаем для теоретического
    emp_t = norm.cdf(x, mu, sigma)
    empirical_teor[x] = emp_t
    dif = abs(emp_r - emp_t)
    if dif > D:
    D = dif
    return D, empirical_real, empirical_teor


    def draw_empirical(real: dict, teor: dict):
    plt.figure()
    plt.plot(real.keys(), real.values(), color='green', label='real empirical function')
    plt.plot(teor.keys(), teor.values(), color='red', label='teor function')
    plt.legend()
    plt.show()
    return


    if __name__ == '__main__':
    # параметры нормального распределения
    # мат ожидание
    m = 10
    # ско
    sigma = 1
    # дисперсия
    dsp = sigma * sigma
    # размер выборки
    size = 100
    # генерируем выборку с нормальным распределением
    real_array = generate_normal(m, sigma, size)
    D, emp_real, emp_teor = kolmogorov_check(real_array, m, sigma)
    print(D)
    draw_empirical(emp_real, emp_teor)


    написать администратору сайта