2024年第十四届MathorCup高校数学建模挑战赛

A题 移动通信网络中PCI规划问题

原题再现：

  物理小区识别码(PCI)规划是移动通信网络中下行链路层上，对各覆盖小区编号进行合理配置，以避免PCI冲突、PCI混淆以及PCI模3干扰等现象。PCI规划对于减少物理层的小区间互相干扰(ICI)，增加物理下行控制信道(PDCCH)的吞吐量有着重要的作用，尤其是对于基站小区覆盖边缘的用户和发生信号切换的用户，能有效地降低信号干扰，提升用户的体验。
  在一个移动通信系统中，PCI的数量是十分有限的，但实际网络中小区的数量巨大，因此必须对PCI进行复用，这就带来了PCI资源的合理复用配置的问题。错误的PCI配置方式会显著地增加下行网络的ICI，从而会严重影响网络质量。为了降低ICI，在进行PCI规划时需要综合地考虑同频邻区之间的三种场景：PCI冲突、PCI混淆以及PCI模3干扰。
  在无线通信系统中，如果小区i的主控连接的设备同时可以接收到小区j的信号，则称小区j为小区i的邻区。如果小区j与小区i的频点相同，则小区j是小区i的同频邻区。如果小区i的某主控连接设备接收到小区i的信号强度pi与邻区j的信号强度pj的差小于等于给定门限δ，即pi-pj≤δ，则称小区j为小区i的重叠覆盖邻区。
  PCI冲突发生在主控小区和其同频邻区分配了相同的PCI的情况下，如图1所示，小区1和它的一个同频邻小区2被分配了相同的PCI值A，此时便会发生PCI冲突。应被小区1连接的用户设备可能会错误地连接到小区2，但小区1才是真正要连接的目标小区。由于对于用户设备来说很难有效地区分场强相差不大的小区1和小区2的信号，错误的连接判断最终会导致无线信号服务的中断，最终导致下行网络资源的错误分配。

  PCI 混淆通常发生在一个主控小区的两个或者多个同频邻区之间，如图 2 所示。设小区 1 的两个邻小区 2 和 3 被分配了相同的 PCI 值 B，当小区 1 中的用户由于移动等原因需要切换连接到小区 2 时，由于小区 2 和小区 3 的 PCI 相同，用户很可能错误的切换到小区 3。PCI 混淆会导致下行网络中的用户在进行服务切换时的信号中断和资源的错误分配。

  PCI 模 3 干扰发生在主控小区和其同频重叠覆盖邻区分配的 PCI 模 3
相同的情况下，如图 3 所示，小区 1 和它的一个同频重叠覆盖邻小区 2 被分配了模 3 相同的 PCI 值（例如小区 1 分配的 PCI 是 1，小区 2 分配的 PCI是 7，则小区 1 和 2 的 PCI 模 3 的值相同，都是 1），此时便会发生 PCI 模3 干扰。当 PCI 模 3 干扰现象发生时，由于小区 1 和小区 2 的参考信号的相互叠加，用户设备接收的信号质量会明显的下降，同时这种现象会造成CQI的错误评估和下行网络的延迟。

  PCI规划问题的目标就是，给每个小区分配PCI，使网络中的PCI冲突、混淆和模3干扰的尽量的少。

  实际网络中，表示PCI冲突混淆和模3干扰数量的方式有很多，可以
用路测数据点的情况，也可以对整个城市进行栅格化用所有栅格的情况，这些方法中，网优部门最常用的就是测量报告（MR）数据。MR数据是UE设备在通信过程中定时上报的报告，每条MR数据中，主要包括UE通信时接入的主控小区及接收到的邻区信息以及相应的信号强度值。由于测量报告是定间隔时间上报，因此MR数据的分布情况基本可以反映业务量的分布情况。同时，由于MR数据在时间和空间上的全面性，因此用MR数据的冲突、混淆和模3干扰的数量，来反映网络中的PCI指标，是比较准确的。

  基于MR数据的PCI规划问题具体为：给定N个小区，遍历这些小区的全部MR数据，生成3个N×N的矩阵，分别为：
  ● 冲突矩阵A=[a_ij]_N×N，其中若小区i和j同频，则a_ij的值为小区i为主控，j为邻区的MR数量，否则a_ij的值为0。
  ● 混淆矩阵B=[b_ij]_N×N，其中若小区i和j同频，则b_ij的值为小区i和j同时为另一个小区k的邻区的MR数量，否则b_ij的值为0。
  ● 干扰矩阵C=[c_ij]_N×N，其中若小区i和j同频，则c_ij的值为小区i为主控，j为i的重叠覆盖邻区的MR数量，否则c_ij的值为0。若小区i和j分配相同的PCI值，则冲突数增加a_ij，混淆数增加b_ij+b_ji，如果小区i和j分配的PCI模3的值相同，则模3干扰数增加c_ij+c_ji。实际网络中，总共可分配的PCI是0到1007共1008个。根据附件提供的数据，对某区域中2067个小区进行PCI规划。

  问题1：给这2067个小区重新分配PCI，使得这2067个小区之间的冲突MR数、混淆MR数和模3干扰MR数的总和最少。

  问题2：考虑冲突、混淆和干扰的不同优先级，给这2067个小区重新分配PCI，也是考虑这2067个小区之间的冲突、混淆和模3干扰。首先保证冲突的MR数降到最低，在此基础上保证混淆的MR数降到最低，最后尽量降低模3干扰的MR数。实际网络中，给这2067个小区重新分配PCI，会对这些小区以外的一些距离较近的小区产生影响，也就是这些小区和外围小区之间会产生冲突、混淆和模3干扰的MR数的变化。

  问题3：给这2067个小区重新分配PCI，使得所有可能被影响到的小区间的冲突MR数、混淆MR数和模3干扰MR数的总和最少。

  问题4：考虑冲突、混淆和干扰的不同优先级，给这2067个小区重新分配PCI，也是考虑所有可能被影响到的小区间的冲突、混淆和模3干扰。首先保证冲突的MR数降到最低，在此基础上保证混淆的MR数降到最低，最后尽量降低模3干扰的MR数。

整体求解过程概述(摘要)

  5G 技术的深化与发展显著提升了通信速度，这种高速通信体验为人们的日常生活和工作带来了极大的便利。PCI是网络中用来标识每个物理小区的数字，它是基站配置的一部分，PCI的选择与规划对网络性能有着重要影响。不合理的PCI分配方案会导致用户设备发生信号干扰、网络拥塞、切换到错误小区等问题。考虑到PCI在无线通信中的重要作用，6G作为未来的通信技术很有可能还会继续沿用，而对于数量有限的PCI码，不可避免地会被不同小区重复使用，因此解决这类问题对提高用户上网体验具有十分重大的现实意义。
  本文对待解决的PCI 规划分配的四种问题，均使用模因算法作为主体框架，它是一种结合基于种群的全局搜索和局部搜索的优化技术。在种群的进化中，我们使用基于K-锦标赛的选择方案，通过两种交叉算子，分别为二进制匹配交叉和两点交叉，以及一个变异算子来帮助种群在前中期的快速收敛。并以拉马克进化方式使用我们针对此类问题设计的四个启发式的局部搜索算子对个体进行改进，拉马克进化的思想是后天获取的特征可以遗传给下一代，本算法中体现的是经过四个局部搜索算子改进后的个体，可以参与种群的进化中，这有助于将优质PCI分配方案的特征传递给下一代，同时我们还使用精英策略，这将进一步提升模型的搜索性能。在具体实现上，我们以Visual Studio Code 为主要软件编程求解，在四个待求解问题上取得优异的效果。
  针对问题一：构建以最小化待优化小区之间的总PCI冲突MR数、混淆MR数、模3 干扰MR数之和为目标函数的单目标规划模型，并建立相关约束条件。通过上述进化算法框架对目标函数进行优化，经过一定次数的迭代后，我们找到了目标函数值为26833855 的解，并且到最后还有持续降低的趋势，具体收敛过程如图3-10，体现算法模型具备强大的搜索能力。事实上在四个问题所提供的数据上，我们大约都是给计算机1到2小时左右运行得出的结果，通过相关曲线可以明显看出，模型在算法后期仍然具有求得更优质解的能力，这是因为我们在模型中通过各种优质的局部搜索算子与基于种群的全局搜索，它们在邻域空间上形成互补关系，在一定次数后总是存在几率跳出当前的局部最小值，从而向全局最优值更进一步。
  针对问题二：我们将模型优化过程分为三个阶段，第一阶段以最小化冲突MR数为目标函数。第二阶段以最小化混淆 MR 数为目标函数，并新增关于冲突 MR 数的约束，即优化过程中保存冲突MR数不大于第一阶段结束时的最小值。第三阶段实现模3干扰MR数的优化，类似的，以前两个阶段的结果作为约束条件进行优化。在三个阶段的优化中，均使用固定的模因算法模型，体现模型在不同场景下的适应性。在一定迭代次数后，我们的模型将冲突MR数和混淆MR数都优化到0，模 3干扰MR数为28079222，并还在持续降低，并非模型所能找到的极限最优解，具体收敛过程如图4-2。
  针对问题三：问题三考虑的是所有小区的冲突MR数、混淆MR数以及干扰MR数。由于问题的高度相似性，因此我们在问题一的基础上修改了目标函数设计的部分的算法，即可适用于问题三直接求解。我们同样在随机一次实验上，将目标函数值优化到31374770，且目标函数曲线仍然在持续下降，继续给予时间将获得更优质的解，如图51。
  针对问题四：类似的，我们对模型的只需要在问题二的基础上，修改目标函数计算部分的极少量相关算法代码，即可实现问题求解。在一定迭代次数后，我们的模型同样将冲突MR数和混淆MR数都优化到了最优的0，另外模3干扰MR数为31531882，如图6-1。

模型假设：

  假设1、各小区的频点不变
  假设2、各小区的相对位置和形状不变
  假设3、在模型中上传MR信息的用户设备UE所在位置不变
  假设4、用户设备UE能及时且准确无误地上传相应MR信息
  假设5、通信网络内不发生任何会影响模型计算的设备故障
  假设6、MR数据与时间无关
  假设7、重新分配PCI码后，MR数据不变
  假设8、每个小区都必须且只能分配一个PCI值

问题分析：

  问题一的分析
  问题一所描述的是一个带约束的单目标组合优化问题，它要求我们给 2067 个小区设计PCI分配方案，使得小区之间产生的PCI冲突MR数、PCI混淆MR数、以及PCI模3干扰MR数之和最少，可以将冲突MR数、混淆MR数和模3干扰MR数之和直接作为目标函数进行优化。在大规模优化问题上，以动态规划、整数规划等为代表的精确算法难以高效求解，启发式或元启发式算法是解决PCI规划问题的较好选择，基于问题解空间的庞大性，设计了一种多模因的模因算法模型来实现此问题，能够很好的做到全局搜索，同时又具备强大的局部求精能力。

  问题二的分析
  问题二要求我们考虑冲突、混淆、干扰的优先级，需要的是找到一种PCI分配方案，使得冲突MR数达到最小，冲突MR数达到最优的情况下让混淆MR数尽可能小，并且不破坏冲突MR数、混淆MR数最优的前提下最后再优化模3干扰MR数。与第一题的区别在于目标函数的不同，从问题一的单目标优化转变为多目标优化。 在此我们构建一个多层优化模型，PCI分配方案为一个解，首先设计第一个目标函数计算最优的冲突MR数，记录当前的PCI分配方案；在此基础上，设计第二个目标函数，让冲突MR数不再增大的约束下，对PCI分配方案进行更新，尝试找到满足约束条件下的更优解，使得混淆MR数尽可能小，并记录当前最优的PCI分配方案；最后再通过第三个目标函数计算PCI模3干扰的MR数，扰动当前解，找到一个不增加前两个目标函数值情况下使得模3干扰MR数降到最小的解。由此将一个带约束的多层优化问题转化为三个带约束的单目标优化问题，便于高效求解。 所设计的多个模因算子在三个目标函数下发挥的性能不完全相同，我们的优化模型可以灵活的调整不同算子的权重来契合三个目标函数，在这种分层优化模式下模型可以发挥更出色的性能。

  问题三的分析
  问题三是问题一的扩展，更加符合现实的网络结构，它要求我们考虑附件一中其他小区的情况。在调整给定2067个小区PCI分配方案后，不仅有可能改变这些小区内的PCI 冲突、混淆和模3干扰的状态，而且可能与它们相邻的小区之间发生冲突MR数、混淆MR数和模3干扰MR数的变化。本题只需要在问题一的模型基础上略微修改对PCI 分配方案的评价函数即可。

  问题四的分析
  同样的，问题四在问题二的基础上，额外考虑了其他小区的情况，求解思路仍然是分层级去优化，与问题三类似地，本题只需要在问题二的基础上，调整对PCI分配方案的评价函数模块即可。

模型的建立与求解整体论文缩略图

全部论文请见下方“ 只会建模 QQ名片” 点击QQ名片即可

部分程序代码：

from deap import algorithms, base, creator, tools# 1. 定义目标函数和个体编码
def evaluate(individual):# 计算冲突、混淆、模3干扰MR数return (sum(conflict_mr + confusion_mr + mod3_mr),)creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)# 2. 注册遗传操作
toolbox = base.Toolbox()
toolbox.register("attr_pci", random.randint, 0, 1007)
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_pci, n=小区数量)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)toolbox.register("mate", tools.cxTwoPoint)  # 两点交叉
toolbox.register("mutate", tools.mutUniformInt, low=0, up=1007, indpb=0.05)  # 均匀变异
toolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("evaluate", evaluate)import numpy as np
import random
import math
import timeclass PCIOptimizer:def __init__(self, N, PCI_range, A, B, C):self.N = Nself.PCI_range = PCI_rangeself.A = A  # 冲突矩阵self.B = B  # 混淆矩阵self.C = C  # 干扰矩阵# 预处理邻区关系self.conflict_edges = self._preprocess_edges(self.A)self.confusion_edges = self._preprocess_edges(self.B)self.interf_edges = self._preprocess_edges(self.C)def _preprocess_edges(self, matrix):"""将邻接矩阵转换为稀疏邻区列表"""edges = [[] for _ in range(self.N)]for i in range(self.N):for j in range(self.N):if i != j and matrix[i][j] > 0:edges[i].append( (j, matrix[i][j]) )return edgesdef _compute_initial_cost(self, pci):"""计算初始总代价"""total = 0# 冲突代价for i in range(self.N):for j, w in self.conflict_edges[i]:if pci[i] == pci[j]:total += w# 混淆代价for i in range(self.N):for j, w in self.confusion_edges[i]:if j > i and pci[i] == pci[j]:total += w  # 避免重复计算# 模3干扰for i in range(self.N):mod_i = pci[i] % 3for j, w in self.interf_edges[i]:if mod_i == (pci[j] % 3):total += wreturn totaldef _compute_delta(self, i, old_pci, new_pci, pci):"""计算单点变更的代价变化"""delta = 0# 冲突变化for j, w in self.conflict_edges[i]:if pci[j] == old_pci:delta -= wif pci[j] == new_pci:delta += w# 混淆变化for j, w in self.confusion_edges[i]:if pci[j] == old_pci:delta -= wif pci[j] == new_pci:delta += w# 模3干扰变化old_mod = old_pci % 3new_mod = new_pci % 3for j, w in self.interf_edges[i]:current_mod = pci[j] % 3if current_mod == old_mod:delta -= wif current_mod == new_mod:delta += wreturn deltadef optimize(self, max_iter=10000, temp=1000, cooling_rate=0.95):"""模拟退火优化"""current_pci = [random.randint(0, self.PCI_range-1) for _ in range(self.N)]current_cost = self._compute_initial_cost(current_pci)best_pci = current_pci.copy()best_cost = current_costfor step in range(max_iter):# 生成新解i = random.randint(0, self.N-1)old_val = current_pci[i]new_val = random.choice([x for x in range(self.PCI_range) if x != old_val])# 计算代价变化delta = self._compute_delta(i, old_val, new_val, current_pci)# 决定是否接受if delta < 0 or math.exp(-delta/(temp + 1e-6)) > random.random():current_pci[i] = new_valcurrent_cost += deltaif current_cost < best_cost:best_pci = current_pci.copy()best_cost = current_cost# 动态降温temp *= cooling_rate# 进度输出if step % 100 == 0:print(f"Iter {step}: Temp={temp:.2f}, Cost={best_cost}")return best_pci, best_cost# 数据加载函数
def load_matrix(file_path, N):matrix = np.zeros((N, N), dtype=int)with open(file_path, 'r') as f:for line in f:parts = line.strip().split()i = int(parts[0])j = int(parts[1])val = int(parts[2])matrix[i][j] = valreturn matrix# 参数设置
N = 2067
PCI_range = 1008
conflict_file = 'conflict.txt'
confusion_file = 'confusion.txt'
interf_file = 'interf.txt'# 加载数据
print("Loading matrices...")
A = load_matrix(conflict_file, N)
B = load_matrix(confusion_file, N)
C = load_matrix(interf_file, N)# 运行优化
optimizer = PCIOptimizer(N, PCI_range, A, B, C)
print("Starting optimization...")
start_time = time.time()
best_pci, best_cost = optimizer.optimize(max_iter=5000, temp=1000, cooling_rate=0.99)
print(f"Optimization completed in {time.time()-start_time:.2f}s")
print(f"Minimum total MR: {best_cost}")# 保存结果
with open('optimized_pci.txt', 'w') as f:for pci in best_pci:f.write(f"{pci}\n")
#### 全部论文请见下方“ 只会建模 QQ名片”  点击QQ名片即可