MigrationPathStatus.py

# -*- coding: utf-8 -*-
import networkx as nx
import NetworkModel
import random
import numpy as np
from scipy.optimize import linear_sum_assignment
from sklearn.model_selection import train_test_split
from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import accuracy_score
import pickle


class MigrationStatus:
    def __init__(self, NodeName_pre, NodeName_after, MigCost, MigTime_pre, MigTime_after):
        self.NodeName_pre = NodeName_pre  # 迁移前的点
        self.NodeName_after = NodeName_after
        self.MigCost = MigCost  # S的迁移成本
        self.MigTime_pre = MigTime_pre  # S的迁移前的时延
        self.MigTime_after = MigTime_after  # S的迁移后的时延
        self.MigTime_decrease = MigTime_pre - MigTime_after
        self.priority = self.MigTime_decrease / self.MigCost


def get_adjacent_points(G, node, max_weight):
    """
    选出目标点相邻点中权值小于max_weight的点
    :param G:
    :param node:
    :param max_weight:
    :return:
    """
    adjacent_nodes = G.adj[node]  # 获取与节点相邻的节点
    result = []
    for n in adjacent_nodes:
        weight = G.get_edge_data(node, n)['weight']  # 获取边的权值
        if weight < max_weight:
            result.append(n)
    return result


def bvnf_sort(G, vnf_0, bvnf_set):
    """
    把bvnf_set中的点按照到vnf_0的权值的进行从小到大的排序
    :param G: 无向加权图G
    :param vnf_0: 主vnf所在位置
    :param bvnf_set: bvnf所在位置
    :return f_sorted:bvnf_set按照vnf_0的权值经过从小到大排序后的列表
    """

    f_sorted = sorted(bvnf_set, key=lambda x: G.get_edge_data(int(vnf_0), int(x))['weight'])

    return f_sorted


def migration_status(G, r, aim, case):
    """

    :param G: 代表边缘网络的无向加权图G
    :param r: 用户的请求r
    :param aim: 用户将要迁移到的节点
    :return s: 可选的迁移选项的集合
    """
    # vnf_loc = r.F[0]
    # 将bvnf按离主实例迁移后位置的权值从小到大排序
    bvnf_sorted = bvnf_sort(G, aim, r.F[1:])

    # 获取离aim最远的bvnf的边的权值
    max_range = G.get_edge_data(aim, bvnf_sorted[-1])["weight"]
    # print("max_range:", max_range)

    # 选择出到点aim的边的权值小于max_range的点（不包括已经部署了bvnf的点）
    adjacent_nodes = get_adjacent_points(G, aim, max_range)
    # print("离目标点距离小于max的点:", adjacent_nodes)
    not_migration_loc = r.F[1:]
    not_migration_loc.append(aim)
    bvnf_mig_loc = [x for x in adjacent_nodes if x not in not_migration_loc]  # bvnf可以迁移的位置

    if case == 1:
        # 随机算法 速度快，并没有考虑迁移成本（即最小化总迁移成本），随机算法判断无解的，的KM算法可能可以求解，反过来不行
        s = RandomAlgorithm(G, aim, bvnf_sorted, bvnf_mig_loc)
    if case == 2:
        # 动态规划，KM算法 求解速度慢（中小规模问题下很出色，正好适用于本场景），一定是最优解，KM算法判断无解的一定无解
        s = Kuhn_Munkres_improvement(G, aim, bvnf_sorted, bvnf_mig_loc)
    if case == 3:
        # 机器学习算法，速度较快，考虑了迁移成本，但并不一定（概率）是最优解，有解的不一定能判断出有解，
        # 只有当bvnf和可以迁移的点的位置多的时候，才适合用，当点的数量少的时候得出的结果可能不尽人意。
        s = AI_learning(G, aim, bvnf_sorted, bvnf_mig_loc)
    if case == 4:
        # vnf迁移后，重部署所有vnf备份到临近的节点上
        # 只有当bvnf和可以迁移的点的位置多的时候，才适合用，当点的数量少的时候得出的结果可能不尽人意。
        s = All_BVNF_Redeployment(G, aim, bvnf_sorted, bvnf_mig_loc)

    if case == 5:
        # KM算法改：旨在优先满足时延的情况下再最小化成本，2是优先最小化成本，不一定时延最小
        s = Kuhn_Munkres_improvement_change(G, aim, bvnf_sorted, bvnf_mig_loc)

    return s

    # return max_range


def All_BVNF_Redeployment(G, aim, bvnf_sorted, bvnf_mig_loc):
    """
    每次vnf迁移后重部署所有VNF备份到临近节点，目前的通用方法，备份恢复时延最小，但成本最高
    :param G: 无向加权图
    :param aim: vnf迁移到的点
    :param bvnf_sorted: VNF的备份迁移前的位置
    :param bvnf_mig_loc: vnf的备份可以迁移到的点的位置
    :return s:
    """
    # 1. 计算bvnf_sorted中节点的个数
    num_bvnf = len(bvnf_sorted)

    # 2. 在aim的临近节点中，找出离aim最近的对应个数的点
    neighbors = [n for n in G.neighbors(aim) if n != aim]  # 获取aim的邻近节点并过滤掉aim自身
    neighbor_distances = [(neighbor, G[aim][neighbor]['weight']) for neighbor in neighbors]  # 获取邻居及其权重

    # 按照权重排序，权重越小越近
    sorted_neighbors = sorted(neighbor_distances, key=lambda x: x[1])

    # 3. 将找到的点保存在集合bvnf_mig中
    bvnf_mig = set(neighbor for neighbor, _ in sorted_neighbors[:num_bvnf])  # 取最近的num_bvnf个点
    matches = []
    for q in bvnf_mig:
        matches.append((aim, q))

    # 处理各个算法的输出格式一致
    s = []
    for i in matches:
        MigCost = Migration_Cost(G, i)

        MigTime_pre = G.get_edge_data(aim, i[0])['weight']  # 获取边的权值
        # print("MigTime_pre:", MigTime_pre)
        MigTime_after = G.get_edge_data(aim, i[1])['weight']  # 获取边的权值
        # print("MigTime_after:", MigTime_after)
        s.append(MigrationStatus(i[0], i[1], MigCost, MigTime_pre, MigTime_after))

    return s


def AI_learning(G, aim, bvnf_sorted, bvnf_mig_loc):
    """

    :param G:
    :param aim:
    :param bvnf_sorted:
    :param bvnf_mig_loc:
    :return:
    """
    s = []

    # 从文件model.pkl中加载模型对象
    with open('model.pkl', 'rb') as f:
        clf = pickle.load(f)

    # 标记数组是否被选取完
    usedA = [False] * len(bvnf_sorted)  # 需要迁移的bvnf的点位
    usedB = [False] * len(bvnf_mig_loc)  # 可以迁移到的bvnf的点位

    while not all(usedA) and not all(usedB):
        x_test = []
        # 从A中随机选取一个数
        indexA = random.randint(0, len(bvnf_sorted) - 1)
        while usedA[indexA]:
            indexA = random.randint(0, len(bvnf_sorted) - 1)
        numA = bvnf_sorted[indexA]
        usedA[indexA] = True

        # 从B中随机选取一个数
        indexB = random.randint(0, len(bvnf_mig_loc) - 1)
        while usedB[indexB]:
            indexB = random.randint(0, len(bvnf_mig_loc) - 1)
        numB = bvnf_mig_loc[indexB]
        usedB[indexB] = True

        # 输出选取的数
        # print(numA, numB)
        MigCost = Migration_Cost(G, (numA, numB))
        MigTime_pre = G.get_edge_data(aim, numA)['weight']  # 获取边的权值
        MigTime_after = G.get_edge_data(aim, numB)['weight']  # 获取边的权值

        MigTime_decrease = MigTime_pre - MigTime_after
        priority = MigTime_decrease / MigCost

        if MigTime_pre > MigTime_after:
            # 机器学习算法在此处进行二元分类器，判断该点是否该被添加到s中
            x_test.append([MigTime_pre, MigTime_after, priority])
            # 使用加载回来的模型，进行预测等操作
            y_pred = clf.predict(x_test)
            print("y_pred:", y_pred)
            if y_pred == 1:
                s.append(MigrationStatus(numA, numB, MigCost, MigTime_pre, MigTime_after))
            else:
                # 否则不选择，复原两点的选择状态
                usedA[indexA] = False
                # usedB[indexB] = False

        else:
            # 否则不选择，复原两点的选择状态
            usedA[indexA] = False
            # usedB[indexB] = False

    return s


def Kuhn_Munkres_improvement(G, aim, bvnf_sorted, bvnf_mig_loc):
    """
    对Kuhn_Munkres算法进行改进，首先通过判断node1迁移到node2是否会导致时延增加，是的话将边的权值设置为无穷大。
    :param G: 无向加权图
    :param aim: vnf迁移到的点
    :param bvnf_sorted: 可以进行迁移的bvnf的点位置
    :param bvnf_mig_loc: 可以迁移到的点的位置
    :return:
    """

    """
    print("aim:", aim)
    print("bvnf_sorted:", bvnf_sorted)
    for i in bvnf_sorted:
        print(i, "：", G.get_edge_data(aim, i)['weight'])
    print("bvnf_mig_loc", bvnf_mig_loc)
    for i in bvnf_mig_loc:
        print(i, "：", G.get_edge_data(aim, i)['weight'])
    # 计算每两个点之间的距离
    """
    all_point = bvnf_sorted + bvnf_mig_loc  # 所有可能迁移到（包括不需要迁移的点位）

    # 创建一个列表，包含每个点和对应的 i_dis（权重）
    point_dis_pairs = []
    for i in all_point:
        # 获取点 i 到 aim 的边权重 i_dis
        i_dis = G.get_edge_data(aim, i)['weight']
        # 将每个点和它的 i_dis 作为元组添加到列表中
        point_dis_pairs.append((i, i_dis))

    # 根据 i_dis 从小到大排序
    sorted_points = sorted(point_dis_pairs, key=lambda x: x[1])

    # 提取排序后的点列表（只要点的部分）
    sorted_all_point = [point for point, dis in sorted_points]

    # 打印排序后的点
    # print(sorted_all_point)


    # 根据BVNF位置到潜在的BVNF迁移位置的迁移的权重矩阵
    dist_matrix = []
    for node1 in bvnf_sorted:
        row = []
        for node2 in bvnf_mig_loc:
            # 如果node2到aim的距离大于node1到aim的距离，就把权值设置为很大的数
            if G.get_edge_data(aim, node2)['weight'] > G.get_edge_data(aim, node1)['weight']:
                row.append(1000)
            else:
                row.append(G.get_edge_data(node1, node2)['weight'])

        dist_matrix.append(row)

    # 进行匹配，组合优化中的任务分配问题
    # 最小权重匹配问题的函数，其时间复杂度为O(n^3)。其中，n 是指每个维度上的最大值
    row_idx, col_idx = linear_sum_assignment(dist_matrix)

    # 构造匹配结果
    matches = []
    for row, col in zip(row_idx, col_idx):
        matches.append((bvnf_sorted[row], bvnf_mig_loc[col]))

    # 处理各个算法的输出格式一致
    s = []
    for i in matches:
        MigCost = Migration_Cost(G, i)
        MigTime_pre = G.get_edge_data(aim, i[0])['weight']  # 获取边的权值
        MigTime_after = G.get_edge_data(aim, i[1])['weight']  # 获取边的权值
        s.append(MigrationStatus(i[0], i[1], MigCost, MigTime_pre, MigTime_after))

    return s

def Kuhn_Munkres_improvement_change(G, aim, bvnf_sorted, bvnf_mig_loc):
    """
    对Kuhn_Munkres算法进行改进，首先通过判断node1迁移到node2是否会导致时延增加，是的话将边的权值设置为无穷大。
    :param G: 无向加权图
    :param aim: vnf迁移到的点
    :param bvnf_sorted: 可以进行迁移的bvnf的点位置
    :param bvnf_mig_loc: 可以迁移到的点的位置
    :return:
    """

    """
    print("aim:", aim)
    print("bvnf_sorted:", bvnf_sorted)
    for i in bvnf_sorted:
        print(i, "：", G.get_edge_data(aim, i)['weight'])
    print("bvnf_mig_loc", bvnf_mig_loc)
    for i in bvnf_mig_loc:
        print(i, "：", G.get_edge_data(aim, i)['weight'])
    # 计算每两个点之间的距离
    """

    all_point = bvnf_sorted + bvnf_mig_loc  # 所有可能迁移到（包括不需要迁移的点位）

    # 创建一个列表，包含每个点和对应的 i_dis（权重）
    point_dis_pairs = []
    for i in all_point:
        # 获取点 i 到 aim 的边权重 i_dis
        i_dis = G.get_edge_data(aim, i)['weight']
        # 将每个点和它的 i_dis 作为元组添加到列表中
        point_dis_pairs.append((i, i_dis))

    # 根据 i_dis 从小到大排序
    sorted_points = sorted(point_dis_pairs, key=lambda x: x[1])

    # 提取排序后的点列表（只要点的部分）
    sorted_all_point = [point for point, dis in sorted_points]

    # 打印排序后的点
    # print(sorted_all_point)


    bvnf_sorted_set = set(bvnf_sorted)
    sorted_all_point_set = set(sorted_all_point[0:len(bvnf_sorted)])
    # print(sorted_all_point_set)
    # 计算 bvnf_sorted 中但不在 sorted_all_point 中的点
    missing_points = bvnf_sorted_set - sorted_all_point_set
    # 将差集转换回列表并打印结果
    bvnf_sorted = list(missing_points)
    # print("在 bvnf_sorted 中但不在 sorted_all_point 中的点:", bvnf_sorted)

    # 将两个列表转换为集合
    bvnf_mig_loc_set = set(bvnf_mig_loc)
    # 计算同时在 bvnf_mig_loc 和 sorted_all_point 中的点（交集）
    common_points = bvnf_mig_loc_set & sorted_all_point_set
    # 将交集转换回列表并打印结果
    bvnf_mig_loc = list(common_points)
    # print("同时在 bvnf_mig_loc 和 sorted_all_point 中的点:", bvnf_mig_loc)


    # 根据BVNF位置到潜在的BVNF迁移位置的迁移的权重矩阵
    dist_matrix = []
    for node1 in bvnf_sorted:
        row = []
        for node2 in bvnf_mig_loc:
            # 如果node2到aim的距离大于node1到aim的距离，就把权值设置为很大的数
            if G.get_edge_data(aim, node2)['weight'] > G.get_edge_data(aim, node1)['weight']:
                row.append(1000)
            else:
                row.append(G.get_edge_data(node1, node2)['weight'])

        dist_matrix.append(row)

    # 进行匹配，组合优化中的任务分配问题
    # 最小权重匹配问题的函数，其时间复杂度为O(n^3)。其中，n 是指每个维度上的最大值
    row_idx, col_idx = linear_sum_assignment(dist_matrix)

    # 构造匹配结果
    matches = []
    for row, col in zip(row_idx, col_idx):
        matches.append((bvnf_sorted[row], bvnf_mig_loc[col]))

    # 处理各个算法的输出格式一致
    s = []
    for i in matches:
        MigCost = Migration_Cost(G, i)
        MigTime_pre = G.get_edge_data(aim, i[0])['weight']  # 获取边的权值
        MigTime_after = G.get_edge_data(aim, i[1])['weight']  # 获取边的权值
        s.append(MigrationStatus(i[0], i[1], MigCost, MigTime_pre, MigTime_after))

    return s

def Migration_Cost(G, i):
    """

    :param G: 无向加权图
    :param i: （u，v）  i[0]=u:迁移前的点位,i[1]=v:迁移后的点位
    :return:
    """
    r_fi = 1
    delta_fi = 0

    l_uv = G.get_edge_data(i[0], i[1])['weight']

    alpha_a = 1
    alpha_b = 1
    alpha_c = 0.5

    c_i = alpha_a + alpha_b * alpha_c ** l_uv

    beta_a = 1
    beta_b = 1
    beta_c = 0.5

    d_u = beta_a + beta_b * beta_c ** 0.9

    d_v = beta_a + beta_b * beta_c ** 0.9

    # MigCost = r_fi * c_i - delta_fi * (d_v - d_u)
    MigCost = r_fi * l_uv - delta_fi * (d_v - d_u)
    # print("迁移路径", i, "上的迁移成本是：", MigCost)
    if MigCost < 0:
        print("migcost<0")

    return MigCost


def RandomAlgorithm(G, aim, bvnf_sorted, bvnf_mig_loc):
    """
    从bvnf_mig_loc中随机选取每一个bvnf的迁移位置
    :param G: 无向加权图
    :param aim: 主vnf迁移到的位置
    :param bvnf_sorted: 需要迁移的bvnf的点位
    :param bvnf_mig_loc: 可以迁移到的bvnf的点位
    :return:
    """
    s = []
    # 标记数组是否被选取完
    usedA = [False] * len(bvnf_sorted)  # 需要迁移的bvnf的点位
    usedB = [False] * len(bvnf_mig_loc)  # 可以迁移到的bvnf的点位

    while not all(usedA) and not all(usedB):
        # 从A中随机选取一个数
        indexA = random.randint(0, len(bvnf_sorted) - 1)
        while usedA[indexA]:
            indexA = random.randint(0, len(bvnf_sorted) - 1)
        numA = bvnf_sorted[indexA]
        usedA[indexA] = True

        # 从B中随机选取一个数
        indexB = random.randint(0, len(bvnf_mig_loc) - 1)
        while usedB[indexB]:
            indexB = random.randint(0, len(bvnf_mig_loc) - 1)
        numB = bvnf_mig_loc[indexB]
        usedB[indexB] = True

        # 输出选取的数
        # print(numA, numB)
        MigCost = Migration_Cost(G, (numA, numB))
        MigTime_pre = G.get_edge_data(aim, numA)['weight']  # 获取边的权值
        MigTime_after = G.get_edge_data(aim, numB)['weight']  # 获取边的权值
        if MigTime_pre > MigTime_after:
            # 机器学习算法在此处进行二元分类器，判断该点是否该被添加到s中
            s.append(MigrationStatus(numA, numB, MigCost, MigTime_pre, MigTime_after))
        else:
            # 否则不选择，复原两点的选择状态
            usedB[indexB] = False

    return s


if __name__ == '__main__':
    # 读取文件
    G = nx.read_graphml("my_graph.graphml")
    G = NetworkModel.dijkstra(G)
    NetworkModel.ShowGraph(G)
    r = NetworkModel.UserRequests(['0', '1', '2'], 4, 1)
    # 测试
    s = migration_status(G, r, '4')

    print(s[1].MigTime_pre)
    print(s[1].MigTime_after)