Mathematical Modeling

2025年火花杯A题思路

"数学建模国赛训练"

Posted by Summer on August 15, 2025

题目解读

本题的题目类型是:

  • 多源多汇网络流问题
  • 动态优化（时间维度上动态调整策略）
  • 组合优化（路径选择、时隙分配中选择最优组合）
  • 多目标优化（丢包率、平均时延按权重分配）
  • 资源分配（多重约束条件）

因此, 我们的目标是

  1. 规划路径，将数据流上传至移动信号接受车
  2. 优化整体丢包率 ($1-\frac{\sum\limits_i q_i}{Q_{\text total}}$，$\sum\limits_iq_i$ 表示移动信号车接受到的总流量，$Q_{\text total}$表示全部数据量流量) $\rightarrow$ 传感器同时接收的数据流有限、小车覆盖范围内的带宽总和有限
  3. 优化时延 (传输平均时延$\frac 1F\sum\limits_i t_i$，$t_i$表示数据流$f_i$总的传输时间间隔）$\rightarrow$ 传输路径经过传感器（节点）数尽可能少
  4. 其它

关键内容

Mesh 网络（Mesh Network）

补充资料：Mesh 网络是一种特殊的网络拓扑结构，其核心特点是网络中的 节点 （如设备、路由器、传感器等）可以互相连接、协同通信，形成一个多路径、自组织、自修复的分布式网络。Mesh 网络 没有严格的 “中心节点” ，每个节点既可以作为数据的 发送 / 接收端 ，也可以作为 中继节 点转发其他节点的数据。

  • M*N网络
  • 节点为传感器(x,y)
  • 每个传感器在不同时刻接受到数据流，且 无法存储
  • 每个传感器可能在任意时间生成一个数据流

数据流传输途径

  1. 相邻传感器传递
    约束条件：Mesh网络传输容量$B_{\text sensor}$， 时延$t_{\text sensor}$
  2. 传感器传向移动信号接受车（字太多了，以下简称小车）
    约束条件：小车覆盖范围、小车传输带宽$b(t)$

数据流传输模型

概念

时隙：“时隙”（Time Slot）核心含义是将时间分割成固定长度的 “时间片段”，用于有序地分配资源、传输数据或调度任务。时隙是时间轴上的一段固定时长的间隔，类似于时间被 “切分成” 多个等长的 “小格子”。每个格子（时隙）被分配给特定的任务、设备或信号，确保在共享时间资源时不会发生冲突，实现有序高效的调度。

e.g.无线传感器网络、工业物联网（IIoT）中，多个设备通过预设的时隙轮流发送数据，例如 ZigBee 协议的 MAC 层采用时隙 ALOHA 或 CSMA/CA 结合时隙调度，减少碰撞。

带宽：带宽指在单位时间内，通信链路或设备能够传输的数据量，即数据传输速率
单位：Mb/s,Mbps(兆比特每秒) 后面的数据单位竟然没有统一？

P.S. 前面传输容量$B_{\text sensor}$的单位也是Mbps

符号

  • $f$ 数据流
  • $t_{\text start}$ 时刻
  • $s$ 总数据量
  • $B_{\text receive}$ 某辆小车接受带宽最大值
传输路径（关键）

$f$在$t_{\text start}$时在传感器 ($x_1$,$y_1$) 处产生，先传输到小车覆盖范围内的传感器上，再传输到小车上。

符号表示： ($x_1$,$y_1$) $\rightarrow$ ($x_2$,$y_2$) $\rightarrow$ ……$\rightarrow$ ($x_i$,$y_i$) $\rightarrow$ 第$i$辆小车

分析(这里进一步细化)
  • $B_{\text sensor}$限制传感器间的传输速率，$B_{\text receive}$限制小车覆盖范围内传感器的带宽（传输速率）总和
  • 数据流$f$需要分散来降低丢包率

题目数据分析

  • Flow总数：$F$=1800 条 （$20303$）
  • 每条流量传输的总数据为：10 Mb

  • 每条流量传输的速率为： 5 Mb/s
    因此两个传感器间的传输时间是2s（不算时延）

  • 传感器每30秒会产生一条流，产生时间为 𝑡, 𝑡+30, 𝑡+60，其中 𝑡=0（𝑁为偶数） 或15（𝑁为奇数）
    偶数行传感器在0s,30s,60s产生一条数据流，奇数行传感器在15s,45s,75s产生一条数据流

  • 传感器之间传输容量：𝐵𝑠𝑒𝑛𝑠𝑜𝑟= 10 Mbps
    即一个传感器可以同时接收来自两个不同传感器的数据流

  • 传感器之间每跳传输时延：𝑡𝑠𝑒𝑛𝑠𝑜𝑟= 50 ms
  • 传感器到移动信号接收车的传输时延：50 ms
    传播总时间是传输时间加每次时延总和
  • 移动信号接收车的最大接收带宽和 𝐵𝑟𝑒𝑐𝑒𝑖𝑣𝑒=100 Mbps

数学建模

先将问题拆解：

1. 考虑只有一辆小车，M=20，N=2（以$y1=5$,$y2=6$两条直线上的点为例）

  • 此时Flow总数$ F =2023=120$
  • 小车（中心）的运动方程$F(t)$（此辆小车从最左侧节点处开始运动）：
    假设每个传感器之间的距离为单位1，建立平面直角坐标系，左下角传感器的坐标为$(1，1)$，右上角为$(20，30)$
    将小车视为质点坐标为 $(F(t),5.5)$ ,则小车中心的运动满足函数$F(t)=\frac{19}{100}t$
    补充信息：在移动信号接收车移动过程中如果下一个传感器的带宽大于最末的传感器，则进行接收车连接区域向前移动一格。(if $b(t+\phi_{m+3}) > b(t+\phi_m$),then覆盖范围前进一格，而不是小车的位置！！！)
    由于$T=90s <100s$，只考虑单程

  • 带宽函数$b(t,m)$：
    单链路最大带宽设置为B=20Mbps (单条链路：定义为Mesh 网络中相邻两个传感器节点之间的连接通道，传输容量为10Mbps)
    初始相位 $\phi=5+int(\frac t3)-m$,其中m为传感器所在的列编号，int为取整
    （太难打了，手写了）
    可以考虑用Python画一个b(t,m)的三维立体图像。这样可以直观的看出在t秒时传感器带宽的值。

  • 偶数行传感器在0s,30s,60s产生一条数据流，奇数行传感器在15s,45s,75s产生一条数据流

2. 考虑只有一辆小车，M=20，N=10（小车在y方向上分布较均匀）

需要考虑最小时延

  • 把时延看作成本
  • 第一种思路是使用最小成本算法
  • 第二种思路可能是一种优化，使用序贯缩减算法ADSSP（我发的文献里的第4章内容），也算是一个启发式算法
    现在觉得这个算法还是有较大可行性的，目标（总时延最小）和我们的目标（平均时延最小）基本一致，唯一需要改动的是额外考虑没有按时到达的数据流（应该加个判断条件就好了）

    需要考虑最小丢包率

  • 对于暂时无法上传的数据流，先通过 Mesh 网络在覆盖区附近的节点 “暂存转发”（非存储，实时流动），等待移动接收车到达覆盖范围且带宽较高的时刻再上传。
  • 对同一时刻产生的数据流进行分组（即下面说的聚类）
  • 将一条数据流里的数据分不同的路径传递（这个不确定）

3. 考虑三辆小车，M=20，N=30

  • 需要考虑数据流的路径规划，这里初步考虑使用聚类算法（具体内容在我发的文献的第3章），即根据传感器到三辆小车的距离将传感器分为三个聚类，这个划分是动态变化的、和时间相关的函数（每秒更新）。划分完聚类后，再沿用情况2的路径规划方法（路径每秒更新）。
    P.S. 在对题目数据进行具体分析之前，无法排除存在大部分传感器距离某个小车最近的情况，为了保证带宽分配合理，即题目要求的数据流$f$需要分散来降低丢包率，暂且将划分依据决策变量由 {0,1} 扩展为 [0,1] 。决策变量优化的另一个原因是可以确保聚类结果中簇内聚类对象聚合度的最优性，但是具体怎么划分决策变量的数值目前还不确定。（等把前两个问题解决了再解决这个问题） P.P.S 不确定这个方法可不可行，主要是它给的模型结果是迭代出来的，聚类中心会通过上一次的解更新，不符合预期。我想的是小车的中心作为聚类中心，可能得改进一下。

最小成本流问题

一、最小成本流模型的核心建模要素

1. 节点定义
  • 源节点：所有产生数据流的传感器节点。文档中数据流总数为1800条，每条数据流在时刻$t_{start}$接入某传感器$(x,y)$，这些传感器即为流量的初始源点。
  • 中转节点：Mesh网络中未产生数据流但参与转发的传感器节点（坐标((x,y))，(1≤x≤20,1≤y≤30)，）。
  • 汇节点：3辆移动信号接收车。每辆接收车覆盖特定行传感器（如(y=5-6、15-16、25-26)，），作为数据流的最终汇聚点。
  • 超级源与超级汇（可选，用于多源多汇转换）：虚拟一个“超级源节点”连接所有数据流源点，虚拟一个“超级汇节点”连接3辆接收车，简化多源多汇求解（）。
2. 边的定义与参数
3. 流量需求
  • 每条数据流总数据量为10 Mb，传输速率固定为5 Mb/s，因此每条流需在2个连续时间片（每秒传输5 Mb）内完成传输。
  • 所有数据流的总流量需求需满足：超级源流出的总流量=所有数据流的总数据量（1800×10 Mb），最终通过超级汇流入（确保流量守恒）。
4. 动态建模适配

文档要求调度以秒为粒度更新路径，因此模型需按时间片拆分（$T=90$秒共90个时间片），每个时间片$k$的模型参数动态更新：

  • 传感器到接收车的实时带宽$b(\phi+k)$（基于10秒周期函数，）；
  • 传感器间链路的剩余容量（上一时间片已用带宽需从10 Mbps中扣除）；
  • 移动接收车的剩余接收带宽（上一时间片已用带宽需从100 Mbps中扣除）。

二、模型求解步骤

1. 算法选择

采用** successive shortest augmenting path 算法**（ successive shortest path algorithm），该算法通过反复寻找从源到汇的“最短成本路径”（最小时延路径）并分配流量，直至满足所有需求，适配文档中“最小化总时延”的目标（）。

2. 求解流程（按时间片迭代）

以单个时间片$k$为例，步骤如下：

  1. 初始化网络状态：输入当前时间片的链路剩余容量、接收车剩余带宽、实时上传带宽$b(\phi+k)$。
  2. 构建当前时间片的最小成本流网络：基于上述节点、边和动态参数，生成有向图模型。
  3. 分配流量：对当前活跃数据流（未传输完成的流），用算法寻找从源传感器到接收车的最短时延路径（成本最小路径），每条流分配5 Mb/s的流量（确保不超过链路和接收车容量）。
  4. 更新状态与验证：记录当前时间片的流量分配结果（路径、速率），更新链路和接收车的已用带宽；验证是否满足容量约束（如单链路总速率≤10 Mbps，），若超限则回溯调整路径。
  5. 迭代至下一时间片：将当前状态传递至$k+1$时间片，重复步骤1-4，直至所有数据流传输完成（90秒内）。
3. 关键约束保障
  • 流量分配时强制检查：单条传感器间链路的总速率≤10 Mbps，单辆接收车总接收速率≤100 Mbps，避免丢包；
  • 路径输出需包含具体传感器坐标序列（如$(x_1,y_1) \to (x_2,y_2) \to \cdots \to$接收车），满足文档可视化要求（）。

算法设计

初始化（t=0之前）

  1. 创建网络图：构建一个 $20 \times 30$ 的网格图 $G=(V, E)$，边容量为 $B_{sensor}=10$ Mbps。
  2. 实例化数据流：创建3600个最小单位数据流（5Mb）对象，包含 FlowID, StartTime, StartNode, CurrentNode, Size (5Mb), Rate (5Mbps), Status (初始为0), TotalDelay (初始为0)。
  3. 实例化移动接收车：创建3个接收车对象，设定其 CarID, CoverageRows 和初始位置。

主循环：for t = 0 to 89 (每秒执行一次)

步骤 1：系统状态更新

  1. 激活新数据流：检查当前时间 t 是否为数据流生成时间点（0, 15, 30, 45, 60, 75）。若是，将对应传感器生成的数据流状态 Status 置为1（激活），并设置其 CurrentNode 为 StartNode。
  2. 更新接收车位置：根据文档中的移动规则（比较 $x_{pos}$ 和 $x_{pos}+3$ 列的带宽），更新每辆车的覆盖范围 CurrentCoverageNodes。
  3. 更新端口带宽：对于所有18个被覆盖的传感器（接收端口），使用公式 $b(\phi+t)$（其中 $\phi = 5 + \text{int}(t/3) - m$）重新计算其瞬时上传带宽。
  4. 更新流时延：所有 Status 为1的数据流，其 TotalDelay 增加1秒。

步骤 2：优化的数据流分配与路由

2.1. 目标确定（数据流到接收端口的分配）

  1. 识别参与者：获取当前所有 Status 为1的活动数据流列表 $F_{active}$ 和18个接收端口列表 $P$。
  2. 构建成本矩阵：对于每个流 $f \in F_{active}$ 和每个端口 $p \in P$，计算分配成本： \(Cost(f, p) = w_d \cdot D(f, p) + w_b \cdot \frac{5 \text{ Mbps}}{b_p(t)}\) （建议 $w_d=0.4, w_b=0.6$）
  3. 初始贪心分配：为每个流 $f$ 初步分配到使其 $Cost(f, p)$ 最小的端口 $p^*$。记录此分配关系。
  4. 负载均衡迭代优化： a. 计算每辆车 $c$ 的总需求带宽 $L_c = \sum_{f \to c} 5 \text{ Mbps}$。 b. 循环（设置最大迭代次数，如10次，或直到无变化）： i. 找到负载最重的过载车 $c_{over}$（即 $L_c > B_{receive}$ 且 $L_c$ 最大）。如果不存在过载车，则跳出循环。 ii. 在所有分配给 $c_{over}$ 的流中，找到分配成本 $Cost(f, p)$ 最高的流 $f_{migrate}$。 iii. 为 $f_{migrate}$ 在所有欠载（$L_c < B_{receive}$）或负载最轻的车 $c_{under}$ 的端口中，寻找一个新的最优端口 $p_{new}$（使其分配成本 $Cost(f_{migrate}, p_{new})$ 最小）。 iv. 如果找到了 $p_{new}$，则将 $f_{migrate}$ 重新分配给 $p_{new}$，并更新 $c_{over}$ 和 $c_{under}$ 的负载 $L_c$。否则，将 $f_{migrate}$ 标记为本轮不可迁移，尝试下一个成本最高的流。
  5. 最终分配：迭代结束后，当前的数据流分配关系被最终确定。对于每个流 $f$，其 TargetNode 被设置为它最终被分配到的端口坐标。

2.2. 路径规划与传输模拟

  1. 逐跳转发：对于每个活动数据流 $f$： a. 如果 f.CurrentNode 等于 f.TargetNode（已到达目标端口）： i. 检查目标端口所在的接收车 $c$ 的剩余接收带宽 $B_{receive_remaining}$。 ii. 检查目标端口自身的瞬时上传带宽 $b_p(t)$。 iii. 如果 $B_{receive_remaining} \ge 5$ Mbps 且 $b_p(t) \ge 5$ Mbps，则该流上传成功。将流的 Status 置为-1（完成），从车的 $B_{receive_remaining}$ 中扣除5 Mbps。时延 TotalDelay 不再增加。 iv. 否则，上传失败（丢包），该流在本时间步原地不动，等待下一秒的机会。 b. 如果 f.CurrentNode 不等于 f.TargetNode（在途）： i. 计算从 f.CurrentNode 到相邻节点的下一跳，使其离 f.TargetNode 的曼哈顿距离最近。 ii. 检查该跳连接链路的剩余容量 $B_{sensor_remaining}$。 iii. 如果 $B_{sensor_remaining} \ge 5$ Mbps，则移动成功。更新 f.CurrentNode 为下一跳节点，并从链路容量中扣除5 Mbps。 iv. 否则，移动失败（拥塞），该流在本时间步原地不动。

步骤 3：模拟结束与评估

  1. 重置临时状态：在进入下一个时间步 t+1 之前，重置所有链路的剩余容量为 $B_{sensor}$ 和所有车辆的剩余接收带宽为 $B_{receive}$。
  2. 循环终止：当 t=90 时，模拟结束。
  3. 计算最终指标：
    • 总接收数据量 $\Sigma q_i$：统计所有 Status 为-1的数据流大小之和。
    • 丢包率：$1 - \frac{\Sigma q_i}{Q_{total}}$。
    • 平均传输时延：计算所有 Status 为-1的数据流的 TotalDelay 的平均值。
CATALOG
    FEATURED TAGS
    Meta Machine Learning Mathematical Modeling
    FRIENDS