基于线性规划的无线传感器网络中最大生存时间路由问题的建模与Dantzig-Wolfe分解算法求解示例

字数 8829 2025-12-17 11:11:10

基于线性规划的无线传感器网络中最大生存时间路由问题的建模与Dantzig-Wolfe分解算法求解示例

题目描述

在无线传感器网络中，一组传感器节点（包括一个汇聚节点Sink）被部署在监控区域。每个传感器节点i具有有限的初始能量E_i。这些节点需要周期性地采集数据，并通过多跳无线通信将数据传输到汇聚节点。每次发送或接收一个数据单元都会消耗能量。我们的目标是规划从每个传感器到汇聚节点的数据传输路径（即路由方案），使得整个网络的生存时间最大化。网络生存时间通常定义为：在能量耗尽导致第一个传感器节点失效之前，网络能够持续正常工作的轮数（例如，每轮每个传感器产生一个数据包）。本题目要求使用Dantzig-Wolfe分解算法求解此问题，以应对大规模网络场景。

核心挑战：直接为所有可能的路径（指数级别）建立线性规划模型是困难的。Dantzig-Wolfe分解可以将原问题分解为一个主问题（Master Problem, MP）和若干个子问题（Subproblems, SP）。主问题负责从每个节点的候选路径集合中挑选最优路径组合，以最大化网络生存时间T；每个子问题则为单个节点生成具有“最佳性价比”（即能量消耗与对主问题目标贡献之比）的新路径，供主问题选择。

前提假设：

网络拓扑已知，且是连通的。
节点i发送一个单位数据到邻居节点j的能耗为e_tx(i,j)，从任何节点接收一个单位数据的能耗为e_rx（通常为常数）。
每轮每个源节点i产生一个单位的数据包。
数据转发遵循流量守恒，且路径是有向的（最终指向汇聚节点）。
目标是最大化生存时间T，T是连续变量。

解题过程

步骤1：建立原始线性规划模型

我们首先建立一个紧凑的线性规划模型，但此模型包含大量与路径相关的变量，直接求解困难。

决策变量：

\(T\)：网络生存时间（连续变量）。
\(f_{ij} \geq 0\)：在每轮数据传输中，从节点i到节点j的平均数据流（单位：数据包/轮）。

参数：

\(E_i\)：节点i的初始能量。
\(e_{tx}(i,j)\)：节点i发送一个单位数据到节点j的能耗。
\(e_{rx}\)：节点接收一个单位数据的能耗。
\(S\)：汇聚节点（sink）的编号。对于S，我们不定义能量约束，认为其能量无限。
\(N\)：所有传感器节点的集合（不包括S）。
\(N(i)\)：节点i的邻居节点集合。

目标函数：
最大化网络生存时间T。

约束条件：

能量约束：对于每个传感器节点i (\(i \in N\))，在整个生存时间T内的总能耗不能超过其初始能量。
- 能耗包括：发送能耗 (\(\sum_{j \in N(i)} e_{tx}(i,j) f_{ij} T\)) 和接收能耗 (\(\sum_{k: i \in N(k)} e_{rx} f_{ki} T\))。
- 约束为：\((\sum_{j \in N(i)} e_{tx}(i,j) f_{ij} + \sum_{k: i \in N(k)} e_{rx} f_{ki}) T \leq E_i\)。
流量守恒约束：对于每个传感器节点i (\(i \in N\))，每轮产生的数据（1单位）加上从其他节点接收的数据，必须等于它发送出去的数据。
- \(1 + \sum_{k: i \in N(k)} f_{ki} = \sum_{j \in N(i)} f_{ij}, \quad \forall i \in N\)。
- 注意：对于Sink节点S，其只有入流，没有出流，即\(\sum_{k: S \in N(k)} f_{kS} = \sum_{i \in N} 1\)（所有节点的数据最终汇聚于此），但此约束通常已隐含在其他节点的流量守恒中。
非负约束： \(f_{ij} \geq 0, T \geq 0\)。

这是一个线性规划，但它的约束（1）是非线性的（\(f_{ij} T\)）。我们可以通过变量替换将其线性化。

线性化：令 \(g_{ij} = f_{ij} T\)。则 \(g_{ij}\) 表示在整个生存时间T内，从节点i到节点j传输的总数据量。

重写模型（原始模型P）：

\[\begin{aligned} \text{(P) } \max \quad & T \\ \text{s.t.} \quad & \sum_{j \in N(i)} e_{tx}(i,j) g_{ij} + \sum_{k: i \in N(k)} e_{rx} g_{ki} \leq E_i, \quad \forall i \in N \quad &(1) \\ & 1 \cdot T + \sum_{k: i \in N(k)} g_{ki} = \sum_{j \in N(i)} g_{ij}, \quad \forall i \in N \quad &(2) \\ & g_{ij} \geq 0, \quad T \geq 0 \quad &(3) \end{aligned} \]

现在模型(P)是一个标准的线性规划。然而，它的变量\(g_{ij}\)数量与链路数成正比，在直接求解时没有问题。但我们引入Dantzig-Wolfe分解的目的是为了展示如何处理当路由路径需要满足某种复杂结构（此处是树或路径结构）时的分解方法，并为大规模问题提供一种列生成求解思路。因此，我们将对模型(P)进行重构。

步骤2：构造适合Dantzig-Wolfe分解的模型（路径流模型）

我们为每个源节点i考虑从其到汇聚节点S的所有可能路径的集合 \(P_i\)。设路径 \(p \in P_i\)。

定义决策变量：

\(T\)：网络生存时间。
\(x_{ip} \geq 0\)：在每轮传输中，节点i分配到路径p上的数据流比例（可以理解为，节点i将其产生的1个数据包，拆分给不同的路径p传输）。显然，对于每个i，有 \(\sum_{p \in P_i} x_{ip} = 1\)。

参数：

\(c^p_{ij}\)：如果路径p经过有向链路(i,j)，则值为1，否则为0。
\(E_i\)：节点i的初始能量。

能量消耗分析：

节点i在路径p上发送一个单位数据产生的能耗为：\(\sum_{j} e_{tx}(i,j) c^p_{ij}\)。
节点i在路径p上接收一个单位数据产生的能耗为：\(e_{rx} \times\) (以i为终点的、属于路径p的链路数量)。
更一般地，我们可以定义路径p对节点i的能量消耗系数为 \(a^p_i = \sum_{j} e_{tx}(i,j) c^p_{ij} + e_{rx} \times \text{(路径p中以i为终点的链路数)}\)。

模型（路径流模型PF）：

\[\begin{aligned} \text{(PF) } \max \quad & T \\ \text{s.t.} \quad & \sum_{i \in N} \sum_{p \in P_i} a^p_i x_{ip} T \leq E_i, \quad \forall i \in N \quad &(\text{能量约束}) \\ & \sum_{p \in P_i} x_{ip} = 1, \quad \forall i \in N \quad &(\text{流量分配约束}) \\ & x_{ip} \geq 0, \quad T \geq 0 \end{aligned} \]

同样，通过变量替换 \(y_{ip} = x_{ip} T\)，我们得到线性模型：

\[\begin{aligned} \text{(MP) } \max \quad & T \\ \text{s.t.} \quad & \sum_{i \in N} \sum_{p \in P_i} a^p_i y_{ip} \leq E_i, \quad \forall i \in N \quad &(\text{耦合约束}) \\ & \sum_{p \in P_i} y_{ip} = T, \quad \forall i \in N \quad &(\text{凸组合约束}) \\ & y_{ip} \geq 0, \quad T \geq 0 \end{aligned} \]

模型(MP)是Dantzig-Wolfe分解的主问题（Master Problem）的标准形式。它有两个特点：

耦合约束：每个节点的能量约束，涉及所有源节点i的所有路径变量 \(y_{ip}\)。
独立约束（也称凸组合约束或分割约束）：对于每个源节点i，其路径变量 \(y_{ip}\) 的和等于T。这些约束是相互独立的，每个i对应一个独立的子结构。

步骤3：应用Dantzig-Wolfe分解

Dantzig-Wolfe分解的核心思想是：主问题(MP)的可行域可以表示为多个有界多面体（每个对应一个子问题）的凸组合，再加上一个“代表公共资源”的变量（这里是T）的倍乘。但更常见的处理方式是列生成（Column Generation），它是实现Dantzig-Wolfe分解的一种高效方法。

我们将(MP)的凸组合约束 \(\sum_{p \in P_i} y_{ip} = T\) 视为：变量 \(y_{ip}\) 构成了关于T的一个凸组合。这意味着我们可以将 \(y_{ip}\) 表示为 \(T \cdot \lambda_{ip}\)，其中 \(\lambda_{ip} \geq 0\) 且 \(\sum_{p \in P_i} \lambda_{ip} = 1\)。代入(MP)：

\[\begin{aligned} \max \quad & T \\ \text{s.t.} \quad & \sum_{i \in N} \sum_{p \in P_i} a^p_i (T \lambda_{ip}) \leq E_i, \quad \forall i \in N \\ & \sum_{p \in P_i} \lambda_{ip} = 1, \quad \forall i \in N \\ & \lambda_{ip} \geq 0, \quad T \geq 0 \end{aligned} \]

整理得：

\[\begin{aligned} \text{(DW-MP) } \max \quad & T \\ \text{s.t.} \quad & T \cdot \left( \sum_{p \in P_i} a^p_i \lambda_{ip} \right) \leq E_i, \quad \forall i \in N \quad (1) \\ & \sum_{p \in P_i} \lambda_{ip} = 1, \quad \forall i \in N \quad (2) \\ & \lambda_{ip} \geq 0, \quad T \geq 0 \end{aligned} \]

这是一个关于变量 \(T\) 和 \(\lambda_{ip}\) 的线性规划，但约束(1)仍然是 \(T\) 和 \(\lambda_{ip}\) 的乘积，是双线性的。为了将其转化为标准线性规划，我们进行如下变换：

令 \(z_i = T \cdot (\sum_{p \in P_i} a^p_i \lambda_{ip})\)。这个变换比较棘手。更标准的方法是固定T，然后求解一个线性规划子问题来检查给定T是否可行，然后通过二分搜索找到最大的T。这本质上是求解“给定生存时间T，是否存在可行的路由方案”，这是一个可行性问题。

另一种更优雅的列生成视角（直接处理MP模型）：

我们回到模型(MP)：

\[\begin{aligned} \max \quad & T \\ \text{s.t.} \quad & \sum_{i \in N} \sum_{p \in P_i} a^p_i y_{ip} \leq E_i, \quad \forall i \in N \quad (1) \\ & \sum_{p \in P_i} y_{ip} = T, \quad \forall i \in N \quad (2) \\ & y_{ip} \geq 0 \end{aligned} \]

我们采用列生成求解此线性规划(MP)。但(MP)的变量 \(y_{ip}\) 对于每个i有指数个（因为路径集合 \(P_i\) 是指数级的）。我们需要动态生成这些变量（即路径）。

步骤4：构造限制主问题（RMP）和定价子问题（SP）

4.1 限制主问题（Restricted Master Problem, RMP）
开始时，我们只为每个源节点i初始化一个小的、可行的路径集合 \(\overline{P_i} \subset P_i\)（例如，只包含一条最短路径）。RMP只使用这些路径对应的变量 \(y_{ip}\) (\(p \in \overline{P_i}\)) 进行求解。

RMP的线性规划模型与(MP)相同，只是将 \(P_i\) 替换为 \(\overline{P_i}\)。

求解RMP，我们会得到：

当前目标值 \(T^*\)。
约束(1)对应的对偶变量 \(\pi_i \leq 0\) （因为是不等式“≤”，通常标准化为 \(\pi_i \geq 0\)，但符号取决于定义。这里我们定义 \(\pi_i \geq 0\) 对应约束 \(\sum \dots \leq E_i\)）。
约束(2)对应的对偶变量 \(\sigma_i\) （自由变量）。

4.2 定价子问题（Pricing Subproblem, SP）或列生成子问题

列生成原理：检查是否存在不在当前RMP中的变量 \(y_{ip}\)（即新的路径 \(p \in P_i \setminus \overline{P_i}\)），其对应的简约成本（Reduced Cost）为负，从而将其加入RMP能改进目标值。

在最大化问题中，变量 \(y_{ip}\) 在目标函数中的系数为0（因为目标函数是T，不直接包含 \(y_{ip}\)）。我们需要计算变量 \(y_{ip}\) 的简约成本 \(rc_{ip}\)。

\[rc_{ip} = 0 - \left( \sum_{j \in N} \pi_j \cdot a^p_j \cdot \delta_{i}(j) + \sigma_i \cdot 1 \right) \]

其中，\(\delta_i(j)\) 是指标函数，当路径p是为源节点i生成时，其能量消耗系数 \(a^p_j\) 才与对偶变量 \(\pi_j\) 相乘。更准确地说，对于给定的源节点i，其路径p对节点j（可能是i自身或其他节点）的能量消耗系数是 \(a^p_{ij}\)（为了清晰，我们加上下标i）。但 \(a^p_{ij}\) 的定义依赖于路径p是否经过节点j以及节点j在路径中的角色（发送/接收）。

实际上，我们可以为每个源节点i构造一个独立的定价子问题(SP_i)。因为路径p只与一个特定的i关联。

对于给定的源节点i，变量 \(y_{ip}\) 在约束(1)和(2)中的系数向量是：

在约束(1)（能量约束）中：对于每个节点j，系数为 \(a^p_{ij}\)（路径p对节点j的能耗系数）。
在约束(2)（凸组合约束）中：在对应节点i的那个约束中，系数为1；在其他节点的凸组合约束中，系数为0。

因此，变量 \(y_{ip}\) 的简约成本为：

\[rc_{ip} = 0 - \left( \sum_{j \in N} \pi_j \cdot a^p_{ij} + \sigma_i \right) \]

为了判断是否需要将路径p加入RMP，我们需要检查是否存在某个i和某个路径 \(p \in P_i\)，使得 \(rc_{ip} < 0\)。由于i是离散的，我们可以对每个i求解一个最短路子问题。

定价子问题(SP_i)的形式化：
对于每个源节点i，我们希望找到一个从i到汇聚节点S的路径p，使得其“费用” \(c_p = \sum_{j \in N} \pi_j \cdot a^p_{ij}\) 最小。

回忆 \(a^p_{ij}\) 是路径p对节点j的能量消耗系数。它由路径p经过的链路决定：

如果路径p包含有向边 (j, k)，则节点j发送数据，消耗 \(e_{tx}(j,k)\)。
如果路径p包含有向边 (k, j)，则节点j接收数据，消耗 \(e_{rx}\)。

因此，对于给定的节点j，其费用系数是路径p中所有与j相关的链路能耗的加权和，权重是对偶变量 \(\pi_j\)。

我们可以将费用 \(c_p\) 分配到路径p的每条边上。考虑一条有向边 (u, v)：

它消耗节点u的发送能耗 \(e_{tx}(u,v)\)，权重是 \(\pi_u\)，贡献费用：\(\pi_u \cdot e_{tx}(u,v)\)。
它消耗节点v的接收能耗 \(e_{rx}\)，权重是 \(\pi_v\)，贡献费用：\(\pi_v \cdot e_{rx}\)。

所以，边 (u, v) 的“长度”或“费用”可以定义为：

\[w(u,v) = \pi_u \cdot e_{tx}(u,v) + \pi_v \cdot e_{rx} \]

那么，对于源节点i，路径p的总费用 \(c_p = \sum_{(u,v) \in p} w(u,v)\)。

因此，定价子问题(SP_i) 就转化为：在给定边权 \(w(u,v)\) 的网络上，为源节点i找到一条从i到汇聚节点S的最短路（即费用最小的路径）。

步骤5：列生成算法流程

初始化：为每个源节点i构造一个初始路径集合 \(\overline{P_i}\)（例如，使用最短跳数路径或能量最省路径）。构建初始RMP。
求解RMP：求解当前的限制主问题（线性规划），得到最优解 \((T^*, y_{ip}^*)\) 以及对偶变量值 \(\pi_j^*\) (≥0) 和 \(\sigma_i^*\)。
定价（列生成）：
- 对于每个源节点i：
  - 利用当前对偶变量 \(\pi_j^*\)，计算所有边的权重 \(w(u,v) = \pi_u^* \cdot e_{tx}(u,v) + \pi_v^* \cdot e_{rx}\)。
  - 运行最短路算法（如Dijkstra算法），找到从i到S的费用最小的路径 \(p^*_i\) 及其费用 \(c_{p^*_i}\)。
- 对于每个i，计算简约成本：\(rc_{ip^*_i} = - (c_{p^*_i} + \sigma_i^*)\)。
- 如果对于所有 i，都有 \(rc_{ip^*_i} \geq 0\)，则没有能改进目标的新列，当前RMP的解就是原问题(MP)的最优解，算法终止。
- 否则，选取那些 \(rc_{ip^*_i} < 0\) 的源节点i，将其对应的新路径 \(p^*_i\) 加入其路径集合 \(\overline{P_i}\)，并添加新的变量 \(y_{ip^*_i}\) 到RMP中。
迭代：返回步骤2。

收敛性：由于每次迭代至少添加一条新路径（列），而可能的路径数量虽然多但是有限（在无环假设下），算法会在有限步内终止，找到原问题(MP)的最优解。

步骤6：获得最终解与解释

当列生成算法终止时，我们得到了RMP（此时等价于完整的MP）的最优解 \(T^*\) 和 \(y_{ip}^*\)。

最大生存时间：\(T^*\) 就是网络在最优路由策略下能达到的最大生存时间（轮数）。
最优路由方案：对于每个源节点i，其每轮的数据流分配比例为 \(x_{ip}^* = y_{ip}^* / T^*\)。这意味着节点i在每轮将其产生的1个单位数据，按比例 \(x_{ip}^*\) 分配给在最终RMP中出现的各条路径p。如果 \(x_{ip}^*\) 是分数，则可以实现一种流量分割（多路径路由）。如果要求单一路径，可以在得到MP的最优解后，再进行整数化处理（例如，分支定价），但会引入组合复杂性。

核心思想总结：
Dantzig-Wolfe分解/列生成将大规模线性规划分解为一个小规模的主问题（负责协调资源分配和流量比例）和多个独立的子问题（为每个源节点生成具有最佳“费用-效益”比的路径）。主问题通过对偶变量为子问题中的边赋予权重，子问题通过求解最短路来“试探”能否生成能改善主问题目标的新列。这种分解特别适合于具有可分离结构且每个子结构（此处是单个源节点的路由选择）的可行集（所有路径）易于描述但数量庞大的优化问题。

基于线性规划的无线传感器网络中最大生存时间路由问题的建模与Dantzig-Wolfe分解算法求解示例题目描述在无线传感器网络中，一组传感器节点（包括一个汇聚节点Sink）被部署在监控区域。每个传感器节点i具有有限的初始能量E_ i。这些节点需要周期性地采集数据，并通过多跳无线通信将数据传输到汇聚节点。每次发送或接收一个数据单元都会消耗能量。我们的目标是规划从每个传感器到汇聚节点的数据传输路径（即路由方案），使得整个网络的生存时间最大化。网络生存时间通常定义为：在能量耗尽导致第一个传感器节点失效之前，网络能够持续正常工作的轮数（例如，每轮每个传感器产生一个数据包）。本题目要求使用Dantzig-Wolfe分解算法求解此问题，以应对大规模网络场景。核心挑战：直接为所有可能的路径（指数级别）建立线性规划模型是困难的。Dantzig-Wolfe分解可以将原问题分解为一个主问题（Master Problem, MP）和若干个子问题（Subproblems, SP）。主问题负责从每个节点的候选路径集合中挑选最优路径组合，以最大化网络生存时间T；每个子问题则为单个节点生成具有“最佳性价比”（即能量消耗与对主问题目标贡献之比）的新路径，供主问题选择。前提假设：网络拓扑已知，且是连通的。节点i发送一个单位数据到邻居节点j的能耗为e_ tx(i,j)，从任何节点接收一个单位数据的能耗为e_ rx（通常为常数）。每轮每个源节点i产生一个单位的数据包。数据转发遵循流量守恒，且路径是有向的（最终指向汇聚节点）。目标是最大化生存时间T，T是连续变量。解题过程步骤1：建立原始线性规划模型我们首先建立一个紧凑的线性规划模型，但此模型包含大量与路径相关的变量，直接求解困难。决策变量： \(T\)：网络生存时间（连续变量）。 \(f_ {ij} \geq 0\)：在每轮数据传输中，从节点i到节点j的平均数据流（单位：数据包/轮）。参数： \(E_ i\)：节点i的初始能量。 \(e_ {tx}(i,j)\)：节点i发送一个单位数据到节点j的能耗。 \(e_ {rx}\)：节点接收一个单位数据的能耗。 \(S\)：汇聚节点（sink）的编号。对于S，我们不定义能量约束，认为其能量无限。 \(N\)：所有传感器节点的集合（不包括S）。 \(N(i)\)：节点i的邻居节点集合。目标函数：最大化网络生存时间T。约束条件：能量约束：对于每个传感器节点i (\(i \in N\))，在整个生存时间T内的总能耗不能超过其初始能量。能耗包括：发送能耗 (\(\sum_ {j \in N(i)} e_ {tx}(i,j) f_ {ij} T\)) 和接收能耗 (\(\sum_ {k: i \in N(k)} e_ {rx} f_ {ki} T\))。约束为：\((\sum_ {j \in N(i)} e_ {tx}(i,j) f_ {ij} + \sum_ {k: i \in N(k)} e_ {rx} f_ {ki}) T \leq E_ i\)。流量守恒约束：对于每个传感器节点i (\(i \in N\))，每轮产生的数据（1单位）加上从其他节点接收的数据，必须等于它发送出去的数据。 \(1 + \sum_ {k: i \in N(k)} f_ {ki} = \sum_ {j \in N(i)} f_ {ij}, \quad \forall i \in N\)。注意：对于Sink节点S，其只有入流，没有出流，即\(\sum_ {k: S \in N(k)} f_ {kS} = \sum_ {i \in N} 1\)（所有节点的数据最终汇聚于此），但此约束通常已隐含在其他节点的流量守恒中。非负约束： \(f_ {ij} \geq 0, T \geq 0\)。这是一个线性规划，但它的约束（1）是非线性的（\(f_ {ij} T\)）。我们可以通过变量替换将其线性化。线性化：令 \(g_ {ij} = f_ {ij} T\)。则 \(g_ {ij}\) 表示在整个生存时间T内，从节点i到节点j传输的总数据量。重写模型（原始模型P）： \[ \begin{aligned} \text{(P) } \max \quad & T \\ \text{s.t.} \quad & \sum_ {j \in N(i)} e_ {tx}(i,j) g_ {ij} + \sum_ {k: i \in N(k)} e_ {rx} g_ {ki} \leq E_ i, \quad \forall i \in N \quad &(1) \\ & 1 \cdot T + \sum_ {k: i \in N(k)} g_ {ki} = \sum_ {j \in N(i)} g_ {ij}, \quad \forall i \in N \quad &(2) \\ & g_ {ij} \geq 0, \quad T \geq 0 \quad &(3) \end{aligned} \] 现在模型(P)是一个标准的线性规划。然而，它的变量\(g_ {ij}\)数量与链路数成正比，在直接求解时没有问题。但我们引入Dantzig-Wolfe分解的目的是为了展示如何处理当路由路径需要满足某种复杂结构（此处是树或路径结构）时的分解方法，并为大规模问题提供一种列生成求解思路。因此，我们将对模型(P)进行重构。步骤2：构造适合Dantzig-Wolfe分解的模型（路径流模型）我们为每个源节点i 考虑从其到汇聚节点S的所有可能路径的集合 \(P_ i\)。设路径 \(p \in P_ i\)。定义决策变量： \(T\)：网络生存时间。 \(x_ {ip} \geq 0\)：在每轮传输中，节点i分配到路径p上的数据流比例（可以理解为，节点i将其产生的1个数据包，拆分给不同的路径p传输）。显然，对于每个i，有 \(\sum_ {p \in P_ i} x_ {ip} = 1\)。参数： \(c^p_ {ij}\)：如果路径p经过有向链路(i,j)，则值为1，否则为0。 \(E_ i\)：节点i的初始能量。能量消耗分析：节点i在路径p上发送一个单位数据产生的能耗为：\(\sum_ {j} e_ {tx}(i,j) c^p_ {ij}\)。节点i在路径p上接收一个单位数据产生的能耗为：\(e_ {rx} \times\) (以i为终点的、属于路径p的链路数量)。更一般地，我们可以定义路径p对节点i的能量消耗系数为 \(a^p_ i = \sum_ {j} e_ {tx}(i,j) c^p_ {ij} + e_ {rx} \times \text{(路径p中以i为终点的链路数)}\)。模型（路径流模型PF）： \[ \begin{aligned} \text{(PF) } \max \quad & T \\ \text{s.t.} \quad & \sum_ {i \in N} \sum_ {p \in P_ i} a^p_ i x_ {ip} T \leq E_ i, \quad \forall i \in N \quad &(\text{能量约束}) \\ & \sum_ {p \in P_ i} x_ {ip} = 1, \quad \forall i \in N \quad &(\text{流量分配约束}) \\ & x_ {ip} \geq 0, \quad T \geq 0 \end{aligned} \] 同样，通过变量替换 \(y_ {ip} = x_ {ip} T\)，我们得到线性模型： \[ \begin{aligned} \text{(MP) } \max \quad & T \\ \text{s.t.} \quad & \sum_ {i \in N} \sum_ {p \in P_ i} a^p_ i y_ {ip} \leq E_ i, \quad \forall i \in N \quad &(\text{耦合约束}) \\ & \sum_ {p \in P_ i} y_ {ip} = T, \quad \forall i \in N \quad &(\text{凸组合约束}) \\ & y_ {ip} \geq 0, \quad T \geq 0 \end{aligned} \] 模型(MP)是Dantzig-Wolfe分解的主问题（Master Problem）的标准形式。它有两个特点：耦合约束：每个节点的能量约束，涉及所有源节点i的所有路径变量 \(y_ {ip}\)。独立约束（也称凸组合约束或分割约束）：对于每个源节点i，其路径变量 \(y_ {ip}\) 的和等于T。这些约束是相互独立的，每个i对应一个独立的子结构。步骤3：应用Dantzig-Wolfe分解 Dantzig-Wolfe分解的核心思想是：主问题(MP)的可行域可以表示为多个有界多面体（每个对应一个子问题）的凸组合，再加上一个“代表公共资源”的变量（这里是T）的倍乘。但更常见的处理方式是列生成（Column Generation），它是实现Dantzig-Wolfe分解的一种高效方法。我们将(MP)的凸组合约束 \(\sum_ {p \in P_ i} y_ {ip} = T\) 视为：变量 \(y_ {ip}\) 构成了关于T的一个凸组合。这意味着我们可以将 \(y_ {ip}\) 表示为 \(T \cdot \lambda_ {ip}\)，其中 \(\lambda_ {ip} \geq 0\) 且 \(\sum_ {p \in P_ i} \lambda_ {ip} = 1\)。代入(MP)： \[ \begin{aligned} \max \quad & T \\ \text{s.t.} \quad & \sum_ {i \in N} \sum_ {p \in P_ i} a^p_ i (T \lambda_ {ip}) \leq E_ i, \quad \forall i \in N \\ & \sum_ {p \in P_ i} \lambda_ {ip} = 1, \quad \forall i \in N \\ & \lambda_ {ip} \geq 0, \quad T \geq 0 \end{aligned} \] 整理得： \[ \begin{aligned} \text{(DW-MP) } \max \quad & T \\ \text{s.t.} \quad & T \cdot \left( \sum_ {p \in P_ i} a^p_ i \lambda_ {ip} \right) \leq E_ i, \quad \forall i \in N \quad (1) \\ & \sum_ {p \in P_ i} \lambda_ {ip} = 1, \quad \forall i \in N \quad (2) \\ & \lambda_ {ip} \geq 0, \quad T \geq 0 \end{aligned} \] 这是一个关于变量 \(T\) 和 \(\lambda_ {ip}\) 的线性规划，但约束(1)仍然是 \(T\) 和 \(\lambda_ {ip}\) 的乘积，是双线性的。为了将其转化为标准线性规划，我们进行如下变换：令 \(z_ i = T \cdot (\sum_ {p \in P_ i} a^p_ i \lambda_ {ip})\)。这个变换比较棘手。更标准的方法是固定T ，然后求解一个线性规划子问题来检查给定T是否可行，然后通过二分搜索找到最大的T。这本质上是求解“给定生存时间T，是否存在可行的路由方案”，这是一个可行性问题。另一种更优雅的列生成视角（直接处理MP模型）：我们回到模型(MP)： \[ \begin{aligned} \max \quad & T \\ \text{s.t.} \quad & \sum_ {i \in N} \sum_ {p \in P_ i} a^p_ i y_ {ip} \leq E_ i, \quad \forall i \in N \quad (1) \\ & \sum_ {p \in P_ i} y_ {ip} = T, \quad \forall i \in N \quad (2) \\ & y_ {ip} \geq 0 \end{aligned} \] 我们采用列生成求解此线性规划(MP)。但(MP)的变量 \(y_ {ip}\) 对于每个i有指数个（因为路径集合 \(P_ i\) 是指数级的）。我们需要动态生成这些变量（即路径）。步骤4：构造限制主问题（RMP）和定价子问题（SP） 4.1 限制主问题（Restricted Master Problem, RMP）开始时，我们只为每个源节点i初始化一个小的、可行的路径集合 \(\overline{P_ i} \subset P_ i\)（例如，只包含一条最短路径）。RMP只使用这些路径对应的变量 \(y_ {ip}\) (\(p \in \overline{P_ i}\)) 进行求解。 RMP的线性规划模型与(MP)相同，只是将 \(P_ i\) 替换为 \(\overline{P_ i}\)。求解RMP，我们会得到：当前目标值 \(T^* \)。约束(1)对应的对偶变量 \(\pi_ i \leq 0\) （因为是不等式“≤”，通常标准化为 \(\pi_ i \geq 0\)，但符号取决于定义。这里我们定义 \(\pi_ i \geq 0\) 对应约束 \(\sum \dots \leq E_ i\)）。约束(2)对应的对偶变量 \(\sigma_ i\) （自由变量）。 4.2 定价子问题（Pricing Subproblem, SP）或列生成子问题列生成原理：检查是否存在不在当前RMP中的变量 \(y_ {ip}\)（即新的路径 \(p \in P_ i \setminus \overline{P_ i}\)），其对应的简约成本（Reduced Cost）为负，从而将其加入RMP能改进目标值。在最大化问题中，变量 \(y_ {ip}\) 在目标函数中的系数为0（因为目标函数是T，不直接包含 \(y_ {ip}\)）。我们需要计算变量 \(y_ {ip}\) 的简约成本 \(rc_ {ip}\)。 \[ rc_ {ip} = 0 - \left( \sum_ {j \in N} \pi_ j \cdot a^p_ j \cdot \delta_ {i}(j) + \sigma_ i \cdot 1 \right) \] 其中，\(\delta_ i(j)\) 是指标函数，当路径p是为源节点i生成时，其能量消耗系数 \(a^p_ j\) 才与对偶变量 \(\pi_ j\) 相乘。更准确地说，对于给定的源节点i，其路径p对节点j（可能是i自身或其他节点）的能量消耗系数是 \(a^p_ {ij}\)（为了清晰，我们加上下标i）。但 \(a^p_ {ij}\) 的定义依赖于路径p是否经过节点j以及节点j在路径中的角色（发送/接收）。实际上，我们可以为每个源节点i 构造一个独立的定价子问题(SP_ i)。因为路径p只与一个特定的i关联。对于给定的源节点i，变量 \(y_ {ip}\) 在约束(1)和(2)中的系数向量是：在约束(1)（能量约束）中：对于每个节点j，系数为 \(a^p_ {ij}\)（路径p对节点j的能耗系数）。在约束(2)（凸组合约束）中：在对应节点i的那个约束中，系数为1；在其他节点的凸组合约束中，系数为0。因此，变量 \(y_ {ip}\) 的简约成本为： \[ rc_ {ip} = 0 - \left( \sum_ {j \in N} \pi_ j \cdot a^p_ {ij} + \sigma_ i \right) \] 为了判断是否需要将路径p加入RMP，我们需要检查是否存在某个i和某个路径 \(p \in P_ i\)，使得 \(rc_ {ip} < 0\)。由于i是离散的，我们可以对每个i求解一个最短路子问题。定价子问题(SP_ i)的形式化：对于每个源节点i，我们希望找到一个从i到汇聚节点S的路径p，使得其“费用” \(c_ p = \sum_ {j \in N} \pi_ j \cdot a^p_ {ij}\) 最小。回忆 \(a^p_ {ij}\) 是路径p对节点j的能量消耗系数。它由路径p经过的链路决定：如果路径p包含有向边 (j, k)，则节点j发送数据，消耗 \(e_ {tx}(j,k)\)。如果路径p包含有向边 (k, j)，则节点j接收数据，消耗 \(e_ {rx}\)。因此，对于给定的节点j，其费用系数是路径p中所有与j相关的链路能耗的加权和，权重是对偶变量 \(\pi_ j\)。我们可以将费用 \(c_ p\) 分配到路径p的每条边上。考虑一条有向边 (u, v)：它消耗节点u的发送能耗 \(e_ {tx}(u,v)\)，权重是 \(\pi_ u\)，贡献费用：\(\pi_ u \cdot e_ {tx}(u,v)\)。它消耗节点v的接收能耗 \(e_ {rx}\)，权重是 \(\pi_ v\)，贡献费用：\(\pi_ v \cdot e_ {rx}\)。所以，边 (u, v) 的“长度”或“费用”可以定义为： \[ w(u,v) = \pi_ u \cdot e_ {tx}(u,v) + \pi_ v \cdot e_ {rx} \] 那么，对于源节点i，路径p的总费用 \(c_ p = \sum_ {(u,v) \in p} w(u,v)\)。因此，定价子问题(SP_ i) 就转化为：在给定边权 \(w(u,v)\) 的网络上，为源节点i找到一条从i到汇聚节点S的最短路（即费用最小的路径）。步骤5：列生成算法流程初始化：为每个源节点i构造一个初始路径集合 \(\overline{P_ i}\)（例如，使用最短跳数路径或能量最省路径）。构建初始RMP。求解RMP ：求解当前的限制主问题（线性规划），得到最优解 \((T^ , y_ {ip}^ )\) 以及对偶变量值 \(\pi_ j^ \) (≥0) 和 \(\sigma_ i^ \)。定价（列生成）：对于每个源节点i：利用当前对偶变量 \(\pi_ j^ \)，计算所有边的权重 \(w(u,v) = \pi_ u^ \cdot e_ {tx}(u,v) + \pi_ v^* \cdot e_ {rx}\)。运行最短路算法（如Dijkstra算法），找到从i到S的费用最小的路径 \(p^ i\) 及其费用 \(c {p^ _ i}\)。对于每个i，计算简约成本：\(rc_ {ip^ i} = - (c {p^ _ i} + \sigma_ i^* )\)。如果对于所有 i，都有 \(rc_ {ip^* _ i} \geq 0\)，则没有能改进目标的新列，当前RMP的解就是原问题(MP)的最优解，算法终止。否则，选取那些 \(rc_ {ip^ _ i} < 0\) 的源节点i，将其对应的新路径 \(p^ i\) 加入其路径集合 \(\overline{P_ i}\)，并添加新的变量 \(y {ip^* _ i}\) 到RMP中。迭代：返回步骤2。收敛性：由于每次迭代至少添加一条新路径（列），而可能的路径数量虽然多但是有限（在无环假设下），算法会在有限步内终止，找到原问题(MP)的最优解。步骤6：获得最终解与解释当列生成算法终止时，我们得到了RMP（此时等价于完整的MP）的最优解 \(T^ \) 和 \(y_ {ip}^ \)。最大生存时间：\(T^* \) 就是网络在最优路由策略下能达到的最大生存时间（轮数）。最优路由方案：对于每个源节点i，其每轮的数据流分配比例为 \(x_ {ip}^* = y_ {ip}^* / T^ \)。这意味着节点i在每轮将其产生的1个单位数据，按比例 \(x_ {ip}^ \) 分配给在最终RMP中出现的各条路径p。如果 \(x_ {ip}^* \) 是分数，则可以实现一种流量分割（多路径路由）。如果要求单一路径，可以在得到MP的最优解后，再进行整数化处理（例如，分支定价），但会引入组合复杂性。核心思想总结： Dantzig-Wolfe分解/列生成将大规模线性规划分解为一个小规模的主问题（负责协调资源分配和流量比例）和多个独立的子问题（为每个源节点生成具有最佳“费用-效益”比的路径）。主问题通过对偶变量为子问题中的边赋予权重，子问题通过求解最短路来“试探”能否生成能改善主问题目标的新列。这种分解特别适合于具有可分离结构且每个子结构（此处是单个源节点的路由选择）的可行集（所有路径）易于描述但数量庞大的优化问题。