基于线性规划的无线传感器网络中最大生存时间路由问题的建模与列生成算法求解示例
字数 6079 2025-12-16 17:41:42

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

题目描述

假设我们有一个无线传感器网络，其中包含一个汇聚节点（Sink）和多个传感器节点。每个传感器节点在单位时间内会产生一定量的数据（数据生成率），并且需要通过多跳路由将数据发送到汇聚节点。网络中的每条无线链路都有能量消耗约束，每个传感器节点的电池能量有限。目标是找到一个路由方案，使得整个网络的生存时间（即直到第一个传感器节点能量耗尽的时间）最大化。

为了将这个问题转化为线性规划问题，我们引入一个时间缩放因子 \(T\) \)，表示网络的生存时间。目标是在不超过每个节点能量限制的条件下，最大化 \(T\) \)。由于路由方案涉及多路径流分配，因此这是一个多商品流问题（每个传感器到汇聚节点可视为一种商品），但所有商品共享节点的能量约束。这个模型通常被称为“最大生存时间路由问题”。

已知信息：

  • 网络拓扑：有向图 \(G = (V, E)\) \)，其中 \(V\) 是节点集合，\(E\) 是链路集合。节点 \(0\) 是汇聚节点。
  • 每个传感器节点 \(i \in V \setminus \{0\}\) 在单位时间内生成 \(r_i\) 比特数据。
  • 节点 \(i\) 的初始电池能量为 \(E_i\) \)。
  • 在链路上传输单位比特数据所消耗的能量为：发送能耗 \(e_{ij}^{tx}\) 和接收能耗 \(e_{ij}^{rx}\)（通常接收能耗与发送节点无关，但为简化，可合并为链路能耗系数 \(c_{ij}\) \)。
  • 目标：最大化网络生存时间 \(T\)。

解题过程

我们将问题分为三步：

  1. 建立线性规划模型（主问题）。
  2. 解释为什么直接求解主问题规模太大，从而引入列生成。
  3. 描述列生成的过程，包括定价子问题的构造与求解。

第一步：建立线性规划模型（主问题）

一种常见建模思路是：将生存时间 \(T\) 视为变量，网络中的总数据流由每个节点的数据生成率乘以 \(T\) 得到。但更精细的建模是考虑“流量”与“能量”的平衡。

变量定义：

  • 对于每个节点 \(i\) 和每条出边 \((i,j) \in E\) \)，定义 \(f_{ij}\) 表示从节点 \(i\) 经过边 \((i,j)\) 发送的数据速率（比特/秒）。
  • 对于每个节点 \(i\)，流入数据（包括自身生成的数据）必须等于流出数据（流量守恒）：

\[\sum_{(j,i) \in E} f_{ji} + r_i = \sum_{(i,j) \in E} f_{ij}, \quad \forall i \neq 0 \]

注意，对于汇聚节点 \(0\)，只有流入，没有流出，即 \(\sum_{(j,0) \in E} f_{j0} = \sum_{i \neq 0} r_i\)（总数据必须到达汇聚节点）。

能量约束：
节点 \(i\) 在生存时间 \(T\) 内的总能耗不能超过其电池能量 \(E_i\)。能耗来自发送和接收：

  • 发送能耗：\(\sum_{j: (i,j) \in E} c_{ij} f_{ij} T\)
  • 接收能耗：\(\sum_{j: (j,i) \in E} c_{ji}^{rx} f_{ji} T\)（假设接收单位比特能耗为常数 \(c^{rx}\)）。

为简化，我们常将发送和接收能耗合并到链路上，即节点 \(i\) 在边 \((i,j)\) 上传输单位比特总能耗为 \(e_{ij}\)（包括发送和接收方的能耗分配），但更准确的是分别约束。这里采用合并模型：设 \(e_{ij}\) 是节点 \(i\) 在边 \((i,j)\) 上传输单位比特所消耗的能量（包括发送和可能的部分接收开销，具体取决于建模细节）。则节点 \(i\) 的总能耗为：

\[\sum_{j: (i,j) \in E} e_{ij} f_{ij} T \leq E_i, \quad \forall i \]

（这里假设接收能耗被分摊到发送节点，是常见简化。）

目标：最大化 \(T\)。

完整线性规划模型：

\[\begin{aligned} \max \quad & T \\ \text{s.t.} \quad & \sum_{(j,i) \in E} f_{ji} + r_i = \sum_{(i,j) \in E} f_{ij}, \quad \forall i \neq 0, \\ & \sum_{j: (i,j) \in E} e_{ij} f_{ij} T \leq E_i, \quad \forall i, \\ & f_{ij} \geq 0, \quad \forall (i,j) \in E, \\ & T \geq 0. \end{aligned} \]

这是一个非线性规划（因为约束中包含 \(f_{ij} T\) 乘积项）。但我们可以通过变量替换将其线性化。

线性化技巧：
令 \(x_{ij} = f_{ij} T\)，表示在生存时间 \(T\) 内通过边 \((i,j)\) 传输的总数据量（比特）。则：

\[\begin{aligned} \max \quad & T \\ \text{s.t.} \quad & \sum_{(j,i) \in E} x_{ji} + r_i T = \sum_{(i,j) \in E} x_{ij}, \quad \forall i \neq 0, \\ & \sum_{j: (i,j) \in E} e_{ij} x_{ij} \leq E_i, \quad \forall i, \\ & x_{ij} \geq 0, \quad \forall (i,j) \in E, \\ & T \geq 0. \end{aligned} \]

这是关于变量 \(T\) 和 \(x_{ij}\) 的线性规划。注意流量守恒约束现在是关于总数据量的平衡。

第二步：问题规模与列生成的动机

上述模型是线性规划，可以直接求解。但若网络规模很大（数百节点），变量数为 \(|E| + 1\)，约束数为 \(|V| + |V|\)（流量守恒和能量约束），仍然可解。
然而，在实际中，我们可能希望考虑多路径路由的多样性，即允许每个传感器到汇聚节点有多条路径，而每条路径对应一种“路由模式”。如果我们为每个可能的路径都引入一个变量，变量数会爆炸（路径数量是指数级的）。

列生成思路：
我们不显式列出所有路径，而是将主问题建模为：选择一组从各传感器到汇聚节点的路径以及分配流量，使得能量约束满足，且最大化 \(T\)。
更具体地，对每个传感器 \(s\)（产生数据 \(r_s\)），我们考虑其所有可能到汇聚节点的路径集合 \(P_s\)。对于路径 \(p \in P_s\)，定义变量 \(y_p\) 表示沿该路径输送的数据速率（比特/秒），满足 \(\sum_{p \in P_s} y_p = r_s\)。
但这样变量数太多，无法全部列出。列生成可以动态生成有潜力的路径（即变量）。

第三步：列生成的具体步骤

（1）主问题（限制主问题 Restricted Master Problem, RMP）

初始时，我们只选取每个传感器 \(s\) 的少数几条路径（例如最短路径）构成初始的路径集合 \(\bar{P}_s\)。RMP 如下：

变量：

  • \(T\)：生存时间。
  • 对于每个传感器 \(s\) 和当前路径集合 \(p \in \bar{P}_s\)，变量 \(y_p \geq 0\) 表示沿路径 \(p\) 的数据速率。

约束：

  • 流量分配约束：对每个传感器 \(s\)，

\[ \sum_{p \in \bar{P}_s} y_p = r_s T. \]

（注意：\(y_p\) 是速率，乘以 \(T\) 才是总数据量。但为了与能量约束对齐，我们也可将能量约束中的累积能耗表示为 \(\sum_{p: (i,j) \in p} e_{ij} y_p T\) 。更常见的做法是令 \(z_p = y_p T\) 为路径 \(p\) 上传输的总数据量，则主问题变为关于 \(z_p\) 和 \(T\) 的线性规划。）

实际上，我们采用与前面线性化类似的形式：定义 \(z_p = y_p T\) 为路径 \(p\) 上传输的总数据量。则：

\[\begin{aligned} \max \quad & T \\ \text{s.t.} \quad & \sum_{p \in \bar{P}_s} z_p = r_s T, \quad \forall s \neq 0, \\ & \sum_{s} \sum_{p \in \bar{P}_s: (i,j) \in p} e_{ij} z_p \leq E_i, \quad \forall i, \\ & z_p \geq 0, \quad \forall p \in \bigcup_s \bar{P}_s, \\ & T \geq 0. \end{aligned} \]

这里第一个约束保证了传感器 \(s\) 的所有路径传输的总数据量等于其总生成数据 \(r_s T\)；第二个约束是节点能量约束，对每个节点 \(i\)，累计能耗（对所有经过 \(i\) 的路径上从 \(i\) 发出的边的能耗求和）不超过 \(E_i\)。

（2）对偶变量与定价子问题（Pricing Subproblem）

设主问题的约束对应的对偶变量为：

  • 对每个传感器 \(s\) 的流量分配约束，对偶变量为 \(\pi_s\)（无符号限制，因为等式约束）。
  • 对每个节点 \(i\) 的能量约束，对偶变量为 \(\mu_i \geq 0\)（不等式约束）。

主问题的目标函数系数：\(T\) 的系数为 1，\(z_p\) 的系数为 0。

现在考虑为某个传感器 \(s\) 添加一条新路径 \(p\)（即添加新的变量 \(z_p\)）。这个新变量在目标函数中的系数为 0，在约束中的系数为：

  • 在传感器 \(s\) 的流量分配约束中系数为 1。
  • 在节点 \(i\) 的能量约束中，系数为 \(e_{ij}\) 如果路径 \(p\) 包含从 \(i\) 到 \(j\) 的边（即路径经过节点 \(i\) 并消耗其能量）。

因此，新变量 \(z_p\) 在主问题中的检验数（reduced cost）为：

\[\bar{c}_p = 0 - \left( \pi_s \cdot 1 + \sum_{(i,j) \in p} e_{ij} \mu_i \right) = - \left( \pi_s + \sum_{(i,j) \in p} e_{ij} \mu_i \right). \]

为了使当前解最优，需要所有变量的检验数非负（因为主问题是最大化问题）。因此，若存在某个传感器 \(s\) 和路径 \(p\)，使得：

\[\pi_s + \sum_{(i,j) \in p} e_{ij} \mu_i < 0, \]

则添加该路径对应的变量可以改进目标函数。

于是，定价子问题是：对每个传感器 \(s\)，在给定节点能耗权重 \(\mu_i \geq 0\) 的情况下，寻找从 \(s\) 到汇聚节点 0 的路径 \(p\)，使得路径成本 \(\sum_{(i,j) \in p} e_{ij} \mu_i\) 最小。设最小成本为 \(\zeta_s\)。如果 \(\pi_s + \zeta_s < 0\)，则对应传感器 \(s\) 的最优路径可以加入主问题。

子问题的求解：
由于 \(e_{ij} \mu_i\) 是边 \((i,j)\) 的权重，子问题是一个最短路问题（从 \(s\) 到 0 的最小权重路径）。可以用 Dijkstra 算法求解。

第四步：列生成算法流程

  1. 初始化：为每个传感器 \(s\) 选择一条初始路径（如能量最省路径或最短跳数路径），构成初始的 RMP。
  2. 循环直到所有检验数非负：
    • 求解当前 RMP，得到最优解 \(T^*\) 和对偶变量 \(\pi_s, \mu_i\)。
    • 对每个传感器 \(s\)：
      • 以 \(e_{ij} \mu_i\) 为边权重，计算从 \(s\) 到汇聚节点 0 的最短路径 \(p_s^*\) 及其权重 \(\zeta_s\)。
      • 如果 \(\pi_s + \zeta_s < 0\)（即检验数为负），则将路径 \(p_s^*\) 加入 RMP（添加新变量 \(z_{p_s^*}\)）。
    • 如果没有找到负检验数的路径，算法终止；当前解即为最优。
  3. 输出最优的生存时间 \(T^*\) 以及对应的路径流量分配 \(z_p^*\)。

第五步：结果解读

最终得到的线性规划最优解给出了最大生存时间 \(T^*\) 以及每条路径上传输的总数据量 \(z_p^*\)。由于 \(z_p = y_p T\)，可以换算成数据速率 \(y_p = z_p / T\)。这个路由方案保证了在时间 \(T^*\) 内，没有节点能耗尽能量，并且所有传感器数据都能送达汇聚节点。

注意：

  • 上述模型假设数据可以被分割到多条路径（多路径路由），这是合理的，因为数据流可以按速率分割。
  • 如果要求单路径路由，则需要整数约束，此时列生成需嵌入分支定价（Branch and Price）框架，这里不展开。

小结

本例展示了如何用线性规划和列生成求解无线传感器网络的最大生存时间路由问题。关键步骤包括：

  1. 将原问题建模为带有乘积项的优化问题，并通过变量替换线性化。
  2. 将路由选择转化为基于路径的模型，并用列生成动态生成路径。
  3. 定价子问题转化为最短路问题，高效求解。

这种方法能处理大规模网络，避免枚举所有路径，是列生成在通信网络优化中的典型应用。

基于线性规划的无线传感器网络中最大生存时间路由问题的建模与列生成算法求解示例 题目描述 假设我们有一个无线传感器网络，其中包含一个汇聚节点（Sink）和多个传感器节点。每个传感器节点在单位时间内会产生一定量的数据（数据生成率），并且需要通过多跳路由将数据发送到汇聚节点。网络中的每条无线链路都有能量消耗约束，每个传感器节点的电池能量有限。目标是找到一个路由方案，使得整个网络的生存时间（即直到第一个传感器节点能量耗尽的时间）最大化。 为了将这个问题转化为线性规划问题，我们引入一个时间缩放因子 \( T \) \)，表示网络的生存时间。目标是在不超过每个节点能量限制的条件下，最大化 \( T \) \)。由于路由方案涉及多路径流分配，因此这是一个多商品流问题（每个传感器到汇聚节点可视为一种商品），但所有商品共享节点的能量约束。这个模型通常被称为“最大生存时间路由问题”。 已知信息 ： 网络拓扑：有向图 \( G = (V, E) \) \)，其中 \( V \) 是节点集合，\( E \) 是链路集合。节点 \( 0 \) 是汇聚节点。 每个传感器节点 \( i \in V \setminus \{0\} \) 在单位时间内生成 \( r_ i \) 比特数据。 节点 \( i \) 的初始电池能量为 \( E_ i \) \)。 在链路上传输单位比特数据所消耗的能量为：发送能耗 \( e_ {ij}^{tx} \) 和接收能耗 \( e_ {ij}^{rx} \)（通常接收能耗与发送节点无关，但为简化，可合并为链路能耗系数 \( c_ {ij} \) \)。 目标：最大化网络生存时间 \( T \)。 解题过程 我们将问题分为三步： 建立线性规划模型（主问题）。 解释为什么直接求解主问题规模太大，从而引入列生成。 描述列生成的过程，包括定价子问题的构造与求解。 第一步：建立线性规划模型（主问题） 一种常见建模思路是：将生存时间 \( T \) 视为变量，网络中的总数据流由每个节点的数据生成率乘以 \( T \) 得到。但更精细的建模是考虑“流量”与“能量”的平衡。 变量定义 ： 对于每个节点 \( i \) 和每条出边 \( (i,j) \in E \) \)，定义 \( f_ {ij} \) 表示从节点 \( i \) 经过边 \( (i,j) \) 发送的数据速率（比特/秒）。 对于每个节点 \( i \)，流入数据（包括自身生成的数据）必须等于流出数据（流量守恒）： \[ \sum_ {(j,i) \in E} f_ {ji} + r_ i = \sum_ {(i,j) \in E} f_ {ij}, \quad \forall i \neq 0 \] 注意，对于汇聚节点 \( 0 \)，只有流入，没有流出，即 \( \sum_ {(j,0) \in E} f_ {j0} = \sum_ {i \neq 0} r_ i \)（总数据必须到达汇聚节点）。 能量约束 ： 节点 \( i \) 在生存时间 \( T \) 内的总能耗不能超过其电池能量 \( E_ i \)。能耗来自发送和接收： 发送能耗：\( \sum_ {j: (i,j) \in E} c_ {ij} f_ {ij} T \) 接收能耗：\( \sum_ {j: (j,i) \in E} c_ {ji}^{rx} f_ {ji} T \)（假设接收单位比特能耗为常数 \( c^{rx} \)）。 为简化，我们常将发送和接收能耗合并到链路上，即节点 \( i \) 在边 \( (i,j) \) 上传输单位比特总能耗为 \( e_ {ij} \)（包括发送和接收方的能耗分配），但更准确的是分别约束。这里采用合并模型：设 \( e_ {ij} \) 是节点 \( i \) 在边 \( (i,j) \) 上传输单位比特所消耗的能量（包括发送和可能的部分接收开销，具体取决于建模细节）。则节点 \( i \) 的总能耗为： \[ \sum_ {j: (i,j) \in E} e_ {ij} f_ {ij} T \leq E_ i, \quad \forall i \] （这里假设接收能耗被分摊到发送节点，是常见简化。） 目标 ：最大化 \( T \)。 完整线性规划模型 ： \[ \begin{aligned} \max \quad & T \\ \text{s.t.} \quad & \sum_ {(j,i) \in E} f_ {ji} + r_ i = \sum_ {(i,j) \in E} f_ {ij}, \quad \forall i \neq 0, \\ & \sum_ {j: (i,j) \in E} e_ {ij} f_ {ij} T \leq E_ i, \quad \forall i, \\ & f_ {ij} \geq 0, \quad \forall (i,j) \in E, \\ & T \geq 0. \end{aligned} \] 这是一个非线性规划（因为约束中包含 \( f_ {ij} T \) 乘积项）。但我们可以通过变量替换将其线性化。 线性化技巧 ： 令 \( x_ {ij} = f_ {ij} T \)，表示在生存时间 \( T \) 内通过边 \( (i,j) \) 传输的总数据量（比特）。则： \[ \begin{aligned} \max \quad & T \\ \text{s.t.} \quad & \sum_ {(j,i) \in E} x_ {ji} + r_ i T = \sum_ {(i,j) \in E} x_ {ij}, \quad \forall i \neq 0, \\ & \sum_ {j: (i,j) \in E} e_ {ij} x_ {ij} \leq E_ i, \quad \forall i, \\ & x_ {ij} \geq 0, \quad \forall (i,j) \in E, \\ & T \geq 0. \end{aligned} \] 这是关于变量 \( T \) 和 \( x_ {ij} \) 的线性规划。注意流量守恒约束现在是关于总数据量的平衡。 第二步：问题规模与列生成的动机 上述模型是线性规划，可以直接求解。但若网络规模很大（数百节点），变量数为 \( |E| + 1 \)，约束数为 \( |V| + |V| \)（流量守恒和能量约束），仍然可解。 然而，在实际中，我们可能希望考虑 多路径路由的多样性 ，即允许每个传感器到汇聚节点有多条路径，而每条路径对应一种“路由模式”。如果我们为每个可能的路径都引入一个变量，变量数会爆炸（路径数量是指数级的）。 列生成思路 ： 我们不显式列出所有路径，而是将主问题建模为：选择一组从各传感器到汇聚节点的路径以及分配流量，使得能量约束满足，且最大化 \( T \)。 更具体地，对每个传感器 \( s \)（产生数据 \( r_ s \)），我们考虑其所有可能到汇聚节点的路径集合 \( P_ s \)。对于路径 \( p \in P_ s \)，定义变量 \( y_ p \) 表示沿该路径输送的数据速率（比特/秒），满足 \( \sum_ {p \in P_ s} y_ p = r_ s \)。 但这样变量数太多，无法全部列出。列生成可以动态生成有潜力的路径（即变量）。 第三步：列生成的具体步骤 （1）主问题（限制主问题 Restricted Master Problem, RMP） 初始时，我们只选取每个传感器 \( s \) 的少数几条路径（例如最短路径）构成初始的路径集合 \( \bar{P}_ s \)。RMP 如下： 变量 ： \( T \)：生存时间。 对于每个传感器 \( s \) 和当前路径集合 \( p \in \bar{P}_ s \)，变量 \( y_ p \geq 0 \) 表示沿路径 \( p \) 的数据速率。 约束 ： 流量分配约束：对每个传感器 \( s \)， \[ \sum_ {p \in \bar{P} s} y_ p = r_ s T. \] （注意：\( y_ p \) 是速率，乘以 \( T \) 才是总数据量。但为了与能量约束对齐，我们也可将能量约束中的累积能耗表示为 \( \sum {p: (i,j) \in p} e_ {ij} y_ p T \) 。更常见的做法是令 \( z_ p = y_ p T \) 为路径 \( p \) 上传输的总数据量，则主问题变为关于 \( z_ p \) 和 \( T \) 的线性规划。） 实际上，我们采用与前面线性化类似的形式：定义 \( z_ p = y_ p T \) 为路径 \( p \) 上传输的总数据量。则： \[ \begin{aligned} \max \quad & T \\ \text{s.t.} \quad & \sum_ {p \in \bar{P} s} z_ p = r_ s T, \quad \forall s \neq 0, \\ & \sum {s} \sum_ {p \in \bar{P} s: (i,j) \in p} e {ij} z_ p \leq E_ i, \quad \forall i, \\ & z_ p \geq 0, \quad \forall p \in \bigcup_ s \bar{P}_ s, \\ & T \geq 0. \end{aligned} \] 这里第一个约束保证了传感器 \( s \) 的所有路径传输的总数据量等于其总生成数据 \( r_ s T \)；第二个约束是节点能量约束，对每个节点 \( i \)，累计能耗（对所有经过 \( i \) 的路径上从 \( i \) 发出的边的能耗求和）不超过 \( E_ i \)。 （2）对偶变量与定价子问题（Pricing Subproblem） 设主问题的约束对应的对偶变量为： 对每个传感器 \( s \) 的流量分配约束，对偶变量为 \( \pi_ s \)（无符号限制，因为等式约束）。 对每个节点 \( i \) 的能量约束，对偶变量为 \( \mu_ i \geq 0 \)（不等式约束）。 主问题的目标函数系数：\( T \) 的系数为 1，\( z_ p \) 的系数为 0。 现在考虑为某个传感器 \( s \) 添加一条新路径 \( p \)（即添加新的变量 \( z_ p \)）。这个新变量在目标函数中的系数为 0，在约束中的系数为： 在传感器 \( s \) 的流量分配约束中系数为 1。 在节点 \( i \) 的能量约束中，系数为 \( e_ {ij} \) 如果路径 \( p \) 包含从 \( i \) 到 \( j \) 的边（即路径经过节点 \( i \) 并消耗其能量）。 因此，新变量 \( z_ p \) 在主问题中的 检验数 （reduced cost）为： \[ \bar{c} p = 0 - \left( \pi_ s \cdot 1 + \sum {(i,j) \in p} e_ {ij} \mu_ i \right) = - \left( \pi_ s + \sum_ {(i,j) \in p} e_ {ij} \mu_ i \right). \] 为了使当前解最优，需要所有变量的检验数非负（因为主问题是最大化问题）。因此，若存在某个传感器 \( s \) 和路径 \( p \)，使得： \[ \pi_ s + \sum_ {(i,j) \in p} e_ {ij} \mu_ i < 0, \] 则添加该路径对应的变量可以改进目标函数。 于是， 定价子问题 是：对每个传感器 \( s \)，在给定节点能耗权重 \( \mu_ i \geq 0 \) 的情况下，寻找从 \( s \) 到汇聚节点 0 的路径 \( p \)，使得路径成本 \( \sum_ {(i,j) \in p} e_ {ij} \mu_ i \) 最小。设最小成本为 \( \zeta_ s \)。如果 \( \pi_ s + \zeta_ s < 0 \)，则对应传感器 \( s \) 的最优路径可以加入主问题。 子问题的求解 ： 由于 \( e_ {ij} \mu_ i \) 是边 \( (i,j) \) 的权重，子问题是一个 最短路问题 （从 \( s \) 到 0 的最小权重路径）。可以用 Dijkstra 算法求解。 第四步：列生成算法流程 初始化 ：为每个传感器 \( s \) 选择一条初始路径（如能量最省路径或最短跳数路径），构成初始的 RMP。 循环 直到所有检验数非负： 求解当前 RMP，得到最优解 \( T^* \) 和对偶变量 \( \pi_ s, \mu_ i \)。 对每个传感器 \( s \)： 以 \( e_ {ij} \mu_ i \) 为边权重，计算从 \( s \) 到汇聚节点 0 的最短路径 \( p_ s^* \) 及其权重 \( \zeta_ s \)。 如果 \( \pi_ s + \zeta_ s < 0 \)（即检验数为负），则将路径 \( p_ s^* \) 加入 RMP（添加新变量 \( z_ {p_ s^* } \)）。 如果没有找到负检验数的路径，算法终止；当前解即为最优。 输出最优的生存时间 \( T^* \) 以及对应的路径流量分配 \( z_ p^* \)。 第五步：结果解读 最终得到的线性规划最优解给出了最大生存时间 \( T^* \) 以及每条路径上传输的总数据量 \( z_ p^* \)。由于 \( z_ p = y_ p T \)，可以换算成数据速率 \( y_ p = z_ p / T \)。这个路由方案保证了在时间 \( T^* \) 内，没有节点能耗尽能量，并且所有传感器数据都能送达汇聚节点。 注意 ： 上述模型假设数据可以被分割到多条路径（多路径路由），这是合理的，因为数据流可以按速率分割。 如果要求单路径路由，则需要整数约束，此时列生成需嵌入分支定价（Branch and Price）框架，这里不展开。 小结 本例展示了如何用线性规划和列生成求解无线传感器网络的最大生存时间路由问题。关键步骤包括： 将原问题建模为带有乘积项的优化问题，并通过变量替换线性化。 将路由选择转化为基于路径的模型，并用列生成动态生成路径。 定价子问题转化为最短路问题，高效求解。 这种方法能处理大规模网络，避免枚举所有路径，是列生成在通信网络优化中的典型应用。