diff options
Diffstat (limited to 'osdf/optimizers/pciopt/solver')
| -rw-r--r-- | osdf/optimizers/pciopt/solver/min_confusion.mzn | 37 | ||||
| -rw-r--r-- | osdf/optimizers/pciopt/solver/no_conflicts_no_confusion.mzn | 26 | ||||
| -rw-r--r-- | osdf/optimizers/pciopt/solver/optimizer.py | 74 |
3 files changed, 72 insertions, 65 deletions
diff --git a/osdf/optimizers/pciopt/solver/min_confusion.mzn b/osdf/optimizers/pciopt/solver/min_confusion.mzn index 803f914..ff56c18 100644 --- a/osdf/optimizers/pciopt/solver/min_confusion.mzn +++ b/osdf/optimizers/pciopt/solver/min_confusion.mzn @@ -15,6 +15,7 @@ % % ------------------------------------------------------------------------- % + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Parameters and its assertions %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -27,21 +28,21 @@ int: NUM_PCIS; % Number of edges between neighbor nodes. There is a edge (i,j) if and only % if nodes i and j are neighbors, i.e., an user equipment (UE) can make -% handoff between i and j. Such edges are used to avoid **CONFLICTS**, i.e., +% handoff between i and j. Such edges are used to avoid **COLLISION**, i.e., % to guarantee that nodes i and j have different PCIs. -int: NUM_CONFLICT_EDGES; +int: NUM_NEIGHBORS; % Each line represents an edge between direct neighbors as defined before. -array[1..NUM_CONFLICT_EDGES, 1..2] of int: CONFLICT_EDGES; +array[1..NUM_NEIGHBORS, 1..2] of int: NEIGHBORS; % Number of undirect neighbor pairs (j, k) such that both j and k are direct -% neighbors of node i, i.e., (j, k) exits if and only if exists (i, j) and +% neighbors of node i, i.e., (j, k) exits if and only if exists (i, j) and % (i, k). Nodes (i, k) can generate "confunsions" in the network if they have % the same PCI. Such edges are used to avoid/minimize **CONFUSIONS**. -int: NUM_CONFUSION_EDGES; +int: NUM_SECOND_LEVEL_NEIGHBORS; % Each line represents an edge between undirect neighbors as defined before. -array[1..NUM_CONFUSION_EDGES, 1..2] of int: CONFUSION_EDGES; +array[1..NUM_SECOND_LEVEL_NEIGHBORS, 1..2] of int: SECOND_LEVEL_NEIGHBORS; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Decision variables @@ -54,10 +55,10 @@ array[0..NUM_NODES-1] of var 0..NUM_PCIS-1: pci; % Constraints %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% Direct neighbors must have different PCIs for avoid **CONFLICTS**. -constraint -forall(i in 1..NUM_CONFLICT_EDGES)( - pci[CONFLICT_EDGES[i, 1]] != pci[CONFLICT_EDGES[i, 2]] +% Direct neighbors must have different PCIs for avoid **COLLISION**. +constraint +forall(i in 1..NUM_NEIGHBORS)( + pci[NEIGHBORS[i, 1]] != pci[NEIGHBORS[i, 2]] ); %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -66,8 +67,9 @@ forall(i in 1..NUM_CONFLICT_EDGES)( % Total number of confusions. var int: total_confusions = - sum([bool2int(pci[CONFUSION_EDGES[i, 1]] == pci[CONFUSION_EDGES[i, 2]]) - | i in 1..NUM_CONFUSION_EDGES]); + sum([bool2int(pci[SECOND_LEVEL_NEIGHBORS[i, 1]] == + pci[SECOND_LEVEL_NEIGHBORS[i, 2]]) + | i in 1..NUM_SECOND_LEVEL_NEIGHBORS]); % Minimize the total number of confusions. solve :: int_search(pci, smallest, indomain_min, complete) @@ -78,18 +80,19 @@ minimize total_confusions; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% output -["PCI assigment"] ++ +["PCI assigment"] ++ ["\nnode,pci"] ++ [ "\n" ++ show(node) ++ "," ++ show(pci[node]) | node in 0..NUM_NODES-1 ] ++ -["\n\nConfusions"] ++ +["\n\nConfusions"] ++ ["\nTotal confusions: " ++ show(total_confusions)] ++ ["\nConfusion pairs"] ++ [ - "\n" ++ show(CONFUSION_EDGES[i, 1]) ++ "," ++ show(CONFUSION_EDGES[i, 2]) -| i in 1..NUM_CONFUSION_EDGES where - fix(pci[CONFUSION_EDGES[i, 1]] == pci[CONFUSION_EDGES[i, 2]]) + "\n" ++ show(SECOND_LEVEL_NEIGHBORS[i, 1]) ++ "," ++ + show(SECOND_LEVEL_NEIGHBORS[i, 2]) +| i in 1..NUM_SECOND_LEVEL_NEIGHBORS where + fix(pci[SECOND_LEVEL_NEIGHBORS[i, 1]] == pci[SECOND_LEVEL_NEIGHBORS[i, 2]]) ] diff --git a/osdf/optimizers/pciopt/solver/no_conflicts_no_confusion.mzn b/osdf/optimizers/pciopt/solver/no_conflicts_no_confusion.mzn index 19fabb9..0a9b3e3 100644 --- a/osdf/optimizers/pciopt/solver/no_conflicts_no_confusion.mzn +++ b/osdf/optimizers/pciopt/solver/no_conflicts_no_confusion.mzn @@ -28,21 +28,21 @@ int: NUM_PCIS; % Number of edges between neighbor nodes. There is a edge (i,j) if and only % if nodes i and j are neighbors, i.e., an user equipment (UE) can make -% handoff between i and j. Such edges are used to avoid **CONFLICTS**, i.e., +% handoff between i and j. Such edges are used to avoid **COLLISIONS**, i.e., % to guarantee that nodes i and j have different PCIs. -int: NUM_CONFLICT_EDGES; +int: NUM_NEIGHBORS; % Each line represents an edge between direct neighbors as defined before. -array[1..NUM_CONFLICT_EDGES, 1..2] of int: CONFLICT_EDGES; +array[1..NUM_NEIGHBORS, 1..2] of int: NEIGHBORS; % Number of undirect neighbor pairs (j, k) such that both j and k are direct -% neighbors of node i, i.e., (j, k) exits if and only if exists (i, j) and +% neighbors of node i, i.e., (j, k) exits if and only if exists (i, j) and % (i, k). Nodes (i, k) can generate "confunsions" in the network if they have % the same PCI. Such edges are used to avoid/minimize **CONFUSIONS**. -int: NUM_CONFUSION_EDGES; +int: NUM_SECOND_LEVEL_NEIGHBORS; % Each line represents an edge between undirect neighbors as defined before. -array[1..NUM_CONFUSION_EDGES, 1..2] of int: CONFUSION_EDGES; +array[1..NUM_SECOND_LEVEL_NEIGHBORS, 1..2] of int: SECOND_LEVEL_NEIGHBORS; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Decision variables @@ -55,16 +55,16 @@ array[0..NUM_NODES-1] of var 0..NUM_PCIS-1: pci; % Constraints %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% Direct neighbors must have different PCIs for avoid **CONFLICTS**. -constraint -forall(i in 1..NUM_CONFLICT_EDGES)( - pci[CONFLICT_EDGES[i, 1]] != pci[CONFLICT_EDGES[i, 2]] +% Direct neighbors must have different PCIs for avoid **COLLISION**. +constraint +forall(i in 1..NUM_NEIGHBORS)( + pci[NEIGHBORS[i, 1]] != pci[NEIGHBORS[i, 2]] ); % Undirect neighbors must have different PCIs for avoid **CONFUSIONS**. -constraint -forall(i in 1..NUM_CONFUSION_EDGES)( - pci[CONFUSION_EDGES[i, 1]] != pci[CONFUSION_EDGES[i, 2]] +constraint +forall(i in 1..NUM_SECOND_LEVEL_NEIGHBORS)( + pci[SECOND_LEVEL_NEIGHBORS[i, 1]] != pci[SECOND_LEVEL_NEIGHBORS[i, 2]] ); %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% diff --git a/osdf/optimizers/pciopt/solver/optimizer.py b/osdf/optimizers/pciopt/solver/optimizer.py index e9fcb0d..91e693c 100644 --- a/osdf/optimizers/pciopt/solver/optimizer.py +++ b/osdf/optimizers/pciopt/solver/optimizer.py @@ -17,66 +17,70 @@ # import itertools - import os + import pymzn -from osdf.logging.osdf_logging import debug_log from .pci_utils import get_id BASE_DIR = os.path.dirname(__file__) MZN_FILE_NAME = os.path.join(BASE_DIR, 'no_conflicts_no_confusion.mzn') -def pci_optimize(cell_id, network_cell_info, cell_info_list): - debug_log.debug("Cell ID {} ".format(cell_id)) - dzn_data = {} - dzn_data['NUM_NODES'] = len(cell_info_list) - dzn_data['NUM_PCIS'] = len(cell_info_list) +def pci_optimize(network_cell_info, cell_info_list): + neighbor_edges = get_neighbor_list(network_cell_info) + second_level_edges = get_second_level_neighbor(network_cell_info) + dzn_data = { + 'NUM_NODES': len(cell_info_list), + 'NUM_PCIS': len(cell_info_list), + 'NUM_NEIGHBORS': len(neighbor_edges), + 'NEIGHBORS': get_list(neighbor_edges), + 'NUM_SECOND_LEVEL_NEIGHBORS': len(second_level_edges), + 'SECOND_LEVEL_NEIGHBORS': get_list(second_level_edges) + } - conflict_edges = get_conflict_edges(cell_id, network_cell_info) + return solve(dzn_data) - dzn_data['NUM_CONFLICT_EDGES'] = len(conflict_edges) - dzn_data['CONFLICT_EDGES'] = conflict_edges - confusion_edges = get_confusion_edges(cell_id, network_cell_info) +def get_list(edge_list): + array_list = [] + for s in edge_list: + array_list.append([s[0], s[1]]) + return sorted(array_list) - dzn_data['NUM_CONFUSION_EDGES'] = len(confusion_edges) - dzn_data['CONFUSION_EDGES'] = confusion_edges - - return solve(dzn_data) def solve(dzn_data): return pymzn.minizinc(MZN_FILE_NAME, data=dzn_data) -def get_conflict_edges(cell_id, network_cell_info): - conflict_edges = [] +def get_neighbor_list(network_cell_info): + neighbor_list = set() for cell in network_cell_info['cell_list']: - - if cell_id == cell['cell_id']: - add_to_conflict_edges(network_cell_info, cell, conflict_edges) - return conflict_edges + add_to_neighbor_list(network_cell_info, cell, neighbor_list) + return neighbor_list -def add_to_conflict_edges(network_cell_info, cell, conflict_edges): - cell_id = cell['cell_id'] +def add_to_neighbor_list(network_cell_info, cell, neighbor_list): for nbr in cell.get('nbr_list', []): - conflict_edges.append([get_id(network_cell_info, cell_id), get_id(network_cell_info, nbr['cellId'])]) - + host_id = cell['id'] + nbr_id = get_id(network_cell_info, nbr['cellId']) + if host_id != nbr_id: + entry = sorted([host_id, nbr_id]) + neighbor_list.add((entry[0], entry[1])) -def get_confusion_edges(cell_id, network_cell_info): - confusion_edges = [] +def get_second_level_neighbor(network_cell_info): + second_neighbor_list = set() for cell in network_cell_info['cell_list']: - if cell_id == cell['cell_id']: - return add_to_confusion_edges(network_cell_info, cell) - return confusion_edges + comb_list = build_second_level_list(network_cell_info, cell) + for comb in comb_list: + s = sorted(comb) + second_neighbor_list.add((s[0], s[1])) + return sorted(second_neighbor_list) -def add_to_confusion_edges(network_cell_info, cell): - cell_id = cell['cell_id'] - nbr_list = [] +def build_second_level_list(network_cell_info, cell): + second_nbr_list = [] for nbr in cell.get('nbr_list', []): - nbr_list.append(get_id(network_cell_info, nbr['cellId'])) - return [list(elem) for elem in list(itertools.combinations(nbr_list, 2))] + second_nbr_list.append(get_id(network_cell_info, nbr['cellId'])) + return [list(elem) for elem in list(itertools.combinations(second_nbr_list, 2))] |