基于线性规划的无线传感器网络中最大化网络寿命的分布式路由优化建模与列生成算法求解示例
字数 6051 2025-12-22 15:36:05

基于线性规划的无线传感器网络中最大化网络寿命的分布式路由优化建模与列生成算法求解示例

我将为您详细讲解一个线性规划在无线传感器网络（WSN）优化中的应用问题：如何通过优化路由决策，最大化整个网络的生存时间（直到第一个节点因能量耗尽而死亡的时间）。这个问题是无线传感器网络资源管理的核心问题之一，通常可以建模为线性规划，并利用列生成算法高效求解。

1. 问题背景与描述

想象一个由多个电池供电的传感器节点构成的无线网络。这些节点负责监测环境（如温度、湿度），并将感知数据通过多跳无线通信的方式，最终汇聚到一个中心节点（称为“汇聚点”或“Sink”）。由于节点能量有限，不合理的路由会导致某些节点因转发数据过多而过早耗尽能量，造成网络分割或覆盖空洞。

核心目标： 找到一组从每个源节点到汇聚点的数据流传输路径，使得在所有节点初始能量有限的约束下，整个网络的存活时间最大化。这里的“网络存活时间”通常定义为：从网络开始运行，到第一个节点能量耗尽所经历的时间。

关键挑战： 这是一个组合优化问题，可能的路径数量随网络规模呈指数级增长。直接为所有可能的路径建立变量是计算上不可行的。列生成算法正是为解决这类“变量极多”的线性规划问题而设计的。

2. 问题建模（主问题 - Master Problem）

首先，我们建立线性规划模型，也称为主问题。

定义：

  • 网络： 建模为一个有向图 \(G = (N, A)\)，其中 \(N\) 是节点集合（包括汇聚点 \(t\)），\(A\) 是无线链路集合。
  • 数据： 每个传感器节点 \(i\) （不包括汇聚点）有一个固定的数据生成速率 \(g_i\)（比特/秒）。
  • 能量： 每个节点 \(i\) 有一个初始电池能量 \(E_i\)（焦耳）。
  • 能耗模型： 节点能耗主要来自无线通信。
    • 发送能耗： 节点 \(i\) 向其邻居节点 \(j\) 发送1比特数据，消耗的能量为 \(e_{ij}^{tx}\)，通常与传输距离的 \(\alpha\) 次方成正比（\(\alpha \ge 2\)）。
    • 接收能耗： 节点 \(j\) 从节点 \(i\) 接收1比特数据，消耗的能量为 \(e^{rx}\)（通常为常数）。
  • 生存时间： 我们的目标是最大化一个变量 \(T\)，代表网络存活时间。
  • 决策变量： 我们不直接为每条边定义流量，而是采用列生成的经典思路。我们为每个源节点（数据生成节点）定义一系列可能的路由模式（Routing Pattern）或路径 \(p \in P_i\)，其中 \(P_i\) 是节点 \(i\) 所有可能到达汇聚点的路径的集合。这个集合通常非常大。
    • \(x_{i,p}\)： 在生存时间 \(T\) 内，源节点 \(i\) 采用路径 \(p\) 传输的数据总量（比特）。注意，这里 \(x_{i,p}\) 与 \(T\) 相关，表示在总时间 \(T\) 内的总流量。

目标函数：

\[\max \, T \]

目标很直接，最大化生存时间。

约束条件：

  1. 流量守恒/需求满足约束： 对于每个源节点 \(i\)，在时间 \(T\) 内生成的总数据量必须被发送出去，并最终到达汇聚点。即，分配到所有路径上的总流量，必须等于它的总生成量。

\[ \sum_{p \in P_i} x_{i,p} = g_i \cdot T, \quad \forall i \in N \setminus \{t\} \]

  1. 能量约束： 对于每个节点 \(k\)，在时间 \(T\) 内，其发送和接收数据消耗的总能量，不能超过其初始能量 \(E_k\)。
    • 节点 \(k\) 作为发送方，消耗的能量是：它通过每条出边 \((k, j)\) 发送的总比特数乘以发送单位比特的能耗 \(e_{kj}^{tx}\)。总发送比特数等于所有源节点 \(i\) 的、且经过边 \((k,j)\) 的路径 \(p\) 所分配的流量 \(x_{i,p}\) 之和。
    • 节点 \(k\) 作为接收方，消耗的能量是：它通过每条入边 \((i, k)\) 接收的总比特数乘以接收单位比特的能耗 \(e^{rx}\)。
    • 为了简洁，我们引入一个指示系数 \(a_{i,p}^{(k,j)}\)：
      • 如果源节点 \(i\) 的路径 \(p\) 包含链路 \((k, j)\)，则 \(a_{i,p}^{(k,j)} = 1\)，否则为 0。
    • 同样，引入系数 \(b_{i,p}^{(i,k)}\) 表示路径 \(p\) 是否包含链路 \((i, k)\)（即节点 \(k\) 是否作为接收方）。
    • 能量约束可以写为：

\[ \sum_{i \in N\setminus\{t\}} \sum_{p \in P_i} \left( \sum_{j: (k,j) \in A} a_{i,p}^{(k,j)} e_{kj}^{tx} + \sum_{i: (i,k) \in A} b_{i,p}^{(i,k)} e^{rx} \right) x_{i,p} \le E_k, \quad \forall k \in N \]

*   这个约束确保了在生存期 $ T $ 内，没有节点的能量会耗尽。**因为 $ T $ 是我们最大化的目标，这个约束保证了“第一个节点能量耗尽的时刻”被最大化。**
  1. 非负约束：

\[ T \ge 0, \quad x_{i,p} \ge 0, \quad \forall i, \forall p \in P_i \]

主问题模型总结：
我们的模型是一个包含变量 \(T\) 和 \(x_{i,p}\) 的线性规划。目标函数是线性的，约束条件也都是线性的。但问题在于，变量 \(x_{i,p}\) 的数量是天文数字（所有节点到汇聚点的所有可能路径）。我们无法显式地列出所有变量来求解。这正是列生成算法大显身手的地方。

3. 解题过程：列生成算法（Column Generation）

列生成算法的核心思想是：开始时，我们只考虑主问题的一个小子集（例如，每个节点只有一条非常短的路径，如最短跳数路径）。我们求解这个简化后的问题（称为限制主问题， RMP）。然后，我们通过求解一个或多个定价子问题（Pricing Subproblem） 来判断是否还有“好”的列（新的路径）可以加入RMP，以改善当前解（即增大 \(T\)）。这个过程迭代进行，直到找不到能改善目标的列为止。

步骤详解：

步骤1：初始化 - 构建限制主问题（RMP）
我们为每个源节点 \(i\) 初始构造一个小的、可行的路径集合 \(P_i^0\)。最简单的方法是为每个节点找一条到汇聚点的最短路径（例如，最小跳数路径或最小能量路径）。用这些初始路径集合 \(\{P_i^0\}\) 代替原来巨大的 \(\{P_i\}\)，建立初始的RMP。此时RMP只有很少的变量 \(x_{i,p}\)。

步骤2：求解限制主问题（RMP）
使用线性规划求解器（如单纯形法）求解当前的RMP。求解后，我们得到：

  • 当前最优解 \(T^*\) 和 \(x_{i,p}^*\)。
  • 更重要的是，我们得到对偶变量的值。
    • 对每个流量守恒约束（公式1），会有一个对偶变量 \(\pi_i\)。
    • 对每个能量约束（公式2），会有一个对偶变量 \(\lambda_k\) （\(\lambda_k \ge 0\)）。

步骤3：定价子问题 - 寻找“有负检验数”的新列
在单纯形法中，判断一个非基变量（对应一条未在RMP中的路径 \(p’\)）是否应该进入基，取决于它的检验数（Reduced Cost）。对于最大化问题，如果检验数为正，引入该变量能改善目标函数。

我们需要为每个源节点 \(i\) 检查，是否存在一条新的路径 \(p\) （不在当前 \(P_i^0\) 中），使得其对应的变量 \(x_{i,p}\) 的检验数为正。

根据线性规划对偶理论，检验数 \(\bar{c}_{i,p}\) 的计算公式为：

\[\bar{c}_{i,p} = (\text{原始成本系数}) - (\text{对偶约束左端系数})^T (\text{对偶变量}) \]

在我们的模型中：

  • 变量 \(x_{i,p}\) 在目标函数中的系数为0（因为目标函数只有 \(T\)）。注意：变量 \(x_{i,p}\) 不直接出现在目标函数中，但引入新的、更“高效”的路径可以通过能量约束间接允许我们增大 \(T\)。
  • 理解检验数的更好角度是：在单纯形法中，我们考虑主问题的另一种等价形式，将 \(T\) 视为由其他变量表达。一个更标准的方法是，将模型改写为标准形式，然后计算与每个 \(x_{i,p}\) 相关的检验数。这个检验数反映了将该路径引入方案，能为目标函数 \(T\) 带来的“单位净收益”。推导后，与路径 \(p\) 相关的检验数（对于源节点 \(i\) ）可以表示为：

\[\bar{c}_{i,p} = \pi_i - \sum_{(k,j) \in p} a_{i,p}^{(k,j)} e_{kj}^{tx} \lambda_k - \sum_{(i,k) \in p} b_{i,p}^{(i,k)} e^{rx} \lambda_k \]

  • 更直观的理解是：\(\pi_i\) 是节点 \(i\) 产生单位数据带来的“收益”，而后面的求和项是使用路径 \(p\) 传输节点 \(i\) 的单位数据，在路径上所有中间节点 \(k\) 上产生的“成本”（能耗乘以节点 \(k\) 的能量影子价格 \(\lambda_k\)）。如果 \(\bar{c}_{i,p} > 0\)，意味着使用这条新路径的“净收益”为正，引入它能提升目标。

因此，对于每个源节点 \(i\)，定价子问题就是在一个节点有权重的有向图（从 \(i\) 到汇聚点 \(t\) ）上，寻找一条路径 \(p\)，使得上述检验数 \(\bar{c}_{i,p}\) 最大化。

  • 图： 原网络图 \(G\)。
  • 边权重： 对于一条从 \(u\) 到 \(v\) 的边 \((u, v)\)：
    • 发送成本 = \(e_{uv}^{tx} \lambda_u\) （消耗发送节点 \(u\) 的能量）
    • 接收成本 = \(e^{rx} \lambda_v\) （消耗接收节点 \(v\) 的能量）
    • 边 \((u, v)\) 的总权重 = \(e_{uv}^{tx} \lambda_u + e^{rx} \lambda_v\)。
  • 子问题目标： 对于给定的源节点 \(i\)，找到一条从 \(i\) 到 \(t\) 的路径 \(p\)，使得路径的总权重 \(\sum_{(u,v) \in p} (e_{uv}^{tx} \lambda_u + e^{rx} \lambda_v)\) 最小。因为我们要最大化 \(\bar{c}_{i,p} = \pi_i - [路径总权重]\)，等价于最小化路径总权重。

步骤4：求解定价子问题并添加新列
对于每个源节点 \(i\)，我们求解一个最短路问题（因为边权非负，可以用Dijkstra算法）。得到从 \(i\) 到 \(t\) 的最小权重路径 \(p_i^*\) 及其权重 \(W_i^*\)。

  • 如果 \(\bar{c}_{i, p_i^*} = \pi_i - W_i^* > 0\)，那么这条路径 \(p_i^*\) 的检验数为正，将它（即对应的新变量 \(x_{i, p_i^*}\)）作为新列加入到RMP中。新列在约束矩阵中的系数，根据该路径经过的链路和节点，由公式1和公式2确定。
  • 我们遍历所有源节点 \(i\)，将所有检验数为正的路径对应的新列都加入RMP。

步骤5：迭代与终止

  1. 将新列加入RMP，形成新的RMP。
  2. 返回步骤2，重新求解更新后的RMP，得到新的对偶变量。
  3. 再次进入步骤3，求解新的定价子问题。
  4. 重复这个过程，直到在步骤4中，对于所有源节点 \(i\)，其定价子问题找到的最短路径的检验数 \(\bar{c}_{i, p_i^*} \le 0\)。这意味着没有能改善目标的新列了。根据单纯形法的最优性条件，此时RMP的解就是原始主问题的最优解。

步骤6：获取最终方案
算法终止后，最终的RMP解 \((T^*, x_{i,p}^*)\) 即为原问题的最优解。

  • \(T^*\) 是最大化的网络生存时间。
  • \(x_{i,p}^*\) 给出了每个源节点在不同路径上的总数据分配量。将其除以 \(T^*\)，可以得到每条路径上的数据流速率。这个速率分配方案，就是在给定能量约束下，能最大化网络持续运行时间的最优路由策略。

4. 总结与启示

  • 问题本质： 这是一个经典的多商品流（Multi-commodity Flow） 问题，每个源节点是一种商品。其线性规划模型变量极多，适合用列生成。
  • 列生成的优势： 我们不需要枚举所有可能的路径（指数级）。我们只需要在每次迭代中，利用当前对偶变量（能量价格）为每个源节点求解一个最短路问题（多项式时间），来生成“有潜力”的新路径。这极大地提高了求解效率。
  • 对偶变量的经济解释： 对偶变量 \(\lambda_k\) 可以解释为节点 \(k\) 的能量影子价格。定价子问题寻找的是，在考虑当前网络能量“价格”体系下，传输单位数据“成本”最低的路径。算法通过不断调整路径和价格，最终达到一个平衡状态，此时没有更“便宜”的路径可以进一步延长网络寿命。
  • 实际应用： 虽然这是一个集中式优化算法，但其思想可以启发分布式协议的设计。此外，此模型是许多WSN路由和生存期优化研究的基础，可以通过引入数据聚合、节点睡眠调度、移动Sink等元素进行扩展。
基于线性规划的无线传感器网络中最大化网络寿命的分布式路由优化建模与列生成算法求解示例 我将为您详细讲解一个线性规划在无线传感器网络（WSN）优化中的应用问题： 如何通过优化路由决策，最大化整个网络的生存时间（直到第一个节点因能量耗尽而死亡的时间） 。这个问题是无线传感器网络资源管理的核心问题之一，通常可以建模为线性规划，并利用列生成算法高效求解。 1. 问题背景与描述 想象一个由多个电池供电的传感器节点构成的无线网络。这些节点负责监测环境（如温度、湿度），并将感知数据通过多跳无线通信的方式，最终汇聚到一个中心节点（称为“汇聚点”或“Sink”）。由于节点能量有限，不合理的路由会导致某些节点因转发数据过多而过早耗尽能量，造成网络分割或覆盖空洞。 核心目标 ： 找到一组从每个源节点到汇聚点的 数据流传输路径 ，使得在所有节点初始能量有限的约束下，整个网络的 存活时间 最大化。这里的“网络存活时间”通常定义为：从网络开始运行，到 第一个节点能量耗尽 所经历的时间。 关键挑战 ： 这是一个组合优化问题，可能的路径数量随网络规模呈指数级增长。直接为所有可能的路径建立变量是计算上不可行的。列生成算法正是为解决这类“变量极多”的线性规划问题而设计的。 2. 问题建模（主问题 - Master Problem） 首先，我们建立线性规划模型，也称为 主问题 。 定义 ： 网络 ： 建模为一个有向图 \( G = (N, A) \)，其中 \( N \) 是节点集合（包括汇聚点 \( t \)），\( A \) 是无线链路集合。 数据 ： 每个传感器节点 \( i \) （不包括汇聚点）有一个固定的 数据生成速率 \( g_ i \)（比特/秒）。 能量 ： 每个节点 \( i \) 有一个 初始电池能量 \( E_ i \)（焦耳）。 能耗模型 ： 节点能耗主要来自无线通信。 发送能耗 ： 节点 \( i \) 向其邻居节点 \( j \) 发送1比特数据，消耗的能量为 \( e_ {ij}^{tx} \)，通常与传输距离的 \( \alpha \) 次方成正比（\( \alpha \ge 2 \)）。 接收能耗 ： 节点 \( j \) 从节点 \( i \) 接收1比特数据，消耗的能量为 \( e^{rx} \)（通常为常数）。 生存时间 ： 我们的目标是最大化一个变量 \( T \)，代表网络存活时间。 决策变量 ： 我们不直接为每条边定义流量，而是采用 列生成 的经典思路。我们为每个源节点（数据生成节点）定义一系列可能的 路由模式 （Routing Pattern）或 路径 \( p \in P_ i \)，其中 \( P_ i \) 是节点 \( i \) 所有可能到达汇聚点的路径的集合。这个集合通常非常大。 \( x_ {i,p} \)： 在生存时间 \( T \) 内，源节点 \( i \) 采用路径 \( p \) 传输的数据总量（比特）。注意，这里 \( x_ {i,p} \) 与 \( T \) 相关，表示在总时间 \( T \) 内的总流量。 目标函数 ： \[ \max \, T \] 目标很直接，最大化生存时间。 约束条件 ： 流量守恒/需求满足约束 ： 对于每个源节点 \( i \)，在时间 \( T \) 内生成的总数据量必须被发送出去，并最终到达汇聚点。即，分配到所有路径上的总流量，必须等于它的总生成量。 \[ \sum_ {p \in P_ i} x_ {i,p} = g_ i \cdot T, \quad \forall i \in N \setminus \{t\} \] 能量约束 ： 对于每个节点 \( k \)，在时间 \( T \) 内，其发送和接收数据消耗的总能量，不能超过其初始能量 \( E_ k \)。 节点 \( k \) 作为发送方，消耗的能量是：它通过每条出边 \( (k, j) \) 发送的总比特数乘以发送单位比特的能耗 \( e_ {kj}^{tx} \)。总发送比特数等于所有源节点 \( i \) 的、且经过边 \( (k,j) \) 的路径 \( p \) 所分配的流量 \( x_ {i,p} \) 之和。 节点 \( k \) 作为接收方，消耗的能量是：它通过每条入边 \( (i, k) \) 接收的总比特数乘以接收单位比特的能耗 \( e^{rx} \)。 为了简洁，我们引入一个指示系数 \( a_ {i,p}^{(k,j)} \)： 如果源节点 \( i \) 的路径 \( p \) 包含链路 \( (k, j) \)，则 \( a_ {i,p}^{(k,j)} = 1 \)，否则为 0。 同样，引入系数 \( b_ {i,p}^{(i,k)} \) 表示路径 \( p \) 是否包含链路 \( (i, k) \)（即节点 \( k \) 是否作为接收方）。 能量约束可以写为： \[ \sum_ {i \in N\setminus\{t\}} \sum_ {p \in P_ i} \left( \sum_ {j: (k,j) \in A} a_ {i,p}^{(k,j)} e_ {kj}^{tx} + \sum_ {i: (i,k) \in A} b_ {i,p}^{(i,k)} e^{rx} \right) x_ {i,p} \le E_ k, \quad \forall k \in N \] 这个约束确保了在生存期 \( T \) 内，没有节点的能量会耗尽。 因为 \( T \) 是我们最大化的目标，这个约束保证了“第一个节点能量耗尽的时刻”被最大化。 非负约束 ： \[ T \ge 0, \quad x_ {i,p} \ge 0, \quad \forall i, \forall p \in P_ i \] 主问题模型总结 ： 我们的模型是一个包含变量 \( T \) 和 \( x_ {i,p} \) 的 线性规划 。目标函数是线性的，约束条件也都是线性的。但问题在于，变量 \( x_ {i,p} \) 的数量是天文数字（所有节点到汇聚点的所有可能路径）。我们无法显式地列出所有变量来求解。这正是列生成算法大显身手的地方。 3. 解题过程：列生成算法（Column Generation） 列生成算法的核心思想是：开始时，我们只考虑主问题的一个小子集（例如，每个节点只有一条非常短的路径，如最短跳数路径）。我们求解这个简化后的问题（称为 限制主问题， RMP ）。然后，我们通过求解一个或多个 定价子问题（Pricing Subproblem） 来判断是否还有“好”的列（新的路径）可以加入RMP，以改善当前解（即增大 \( T \)）。这个过程迭代进行，直到找不到能改善目标的列为止。 步骤详解 ： 步骤1：初始化 - 构建限制主问题（RMP） 我们为每个源节点 \( i \) 初始构造一个小的、可行的路径集合 \( P_ i^0 \)。最简单的方法是为每个节点找一条到汇聚点的最短路径（例如，最小跳数路径或最小能量路径）。用这些初始路径集合 \( \{P_ i^0\} \) 代替原来巨大的 \( \{P_ i\} \)，建立初始的RMP。此时RMP只有很少的变量 \( x_ {i,p} \)。 步骤2：求解限制主问题（RMP） 使用线性规划求解器（如单纯形法）求解当前的RMP。求解后，我们得到： 当前最优解 \( T^* \) 和 \( x_ {i,p}^* \)。 更重要的是，我们得到 对偶变量 的值。 对每个 流量守恒约束 （公式1），会有一个对偶变量 \( \pi_ i \)。 对每个 能量约束 （公式2），会有一个对偶变量 \( \lambda_ k \) （\( \lambda_ k \ge 0 \)）。 步骤3：定价子问题 - 寻找“有负检验数”的新列 在单纯形法中，判断一个非基变量（对应一条未在RMP中的路径 \( p’ \)）是否应该进入基，取决于它的 检验数（Reduced Cost） 。对于最大化问题，如果检验数为正，引入该变量能改善目标函数。 我们需要为每个源节点 \( i \) 检查，是否存在一条新的路径 \( p \) （不在当前 \( P_ i^0 \) 中），使得其对应的变量 \( x_ {i,p} \) 的检验数为正。 根据线性规划对偶理论，检验数 \( \bar{c} {i,p} \) 的计算公式为： \[ \bar{c} {i,p} = (\text{原始成本系数}) - (\text{对偶约束左端系数})^T (\text{对偶变量}) \] 在我们的模型中： 变量 \( x_ {i,p} \) 在目标函数中的系数为0（因为目标函数只有 \( T \)）。 注意 ：变量 \( x_ {i,p} \) 不直接出现在目标函数中，但引入新的、更“高效”的路径可以通过能量约束间接允许我们增大 \( T \)。 理解检验数的更好角度是：在单纯形法中，我们考虑主问题的另一种等价形式，将 \( T \) 视为由其他变量表达。一个更标准的方法是，将模型改写为标准形式，然后计算与每个 \( x_ {i,p} \) 相关的检验数。这个检验数反映了将该路径引入方案，能为目标函数 \( T \) 带来的“单位净收益”。推导后，与路径 \( p \) 相关的检验数（对于源节点 \( i \) ）可以表示为： \[ \bar{c} {i,p} = \pi_ i - \sum {(k,j) \in p} a_ {i,p}^{(k,j)} e_ {kj}^{tx} \lambda_ k - \sum_ {(i,k) \in p} b_ {i,p}^{(i,k)} e^{rx} \lambda_ k \] 更直观的理解是：\( \pi_ i \) 是节点 \( i \) 产生单位数据带来的“收益”，而后面的求和项是使用路径 \( p \) 传输节点 \( i \) 的单位数据，在路径上所有中间节点 \( k \) 上产生的“成本”（能耗乘以节点 \( k \) 的能量影子价格 \( \lambda_ k \)）。如果 \( \bar{c}_ {i,p} > 0 \)，意味着使用这条新路径的“净收益”为正，引入它能提升目标。 因此，对于每个源节点 \( i \)，定价子问题就是在一个节点有权重的有向图（从 \( i \) 到汇聚点 \( t \) ）上，寻找一条路径 \( p \)，使得上述检验数 \( \bar{c}_ {i,p} \) 最大化。 图 ： 原网络图 \( G \)。 边权重 ： 对于一条从 \( u \) 到 \( v \) 的边 \( (u, v) \)： 发送成本 = \( e_ {uv}^{tx} \lambda_ u \) （消耗发送节点 \( u \) 的能量） 接收成本 = \( e^{rx} \lambda_ v \) （消耗接收节点 \( v \) 的能量） 边 \( (u, v) \) 的 总权重 = \( e_ {uv}^{tx} \lambda_ u + e^{rx} \lambda_ v \)。 子问题目标 ： 对于给定的源节点 \( i \)，找到一条从 \( i \) 到 \( t \) 的路径 \( p \)，使得路径的总权重 \( \sum_ {(u,v) \in p} (e_ {uv}^{tx} \lambda_ u + e^{rx} \lambda_ v) \) 最小 。因为我们要最大化 \( \bar{c}_ {i,p} = \pi_ i - [ 路径总权重 ] \)，等价于最小化路径总权重。 步骤4：求解定价子问题并添加新列 对于每个源节点 \( i \)，我们求解一个 最短路问题 （因为边权非负，可以用Dijkstra算法）。得到从 \( i \) 到 \( t \) 的最小权重路径 \( p_ i^* \) 及其权重 \( W_ i^* \)。 如果 \( \bar{c} {i, p_ i^ } = \pi_ i - W_ i^ > 0 \)，那么这条路径 \( p_ i^* \) 的检验数为正，将它（即对应的新变量 \( x {i, p_ i^* } \)）作为新列加入到RMP中。新列在约束矩阵中的系数，根据该路径经过的链路和节点，由公式1和公式2确定。 我们遍历所有源节点 \( i \)，将所有检验数为正的路径对应的新列都加入RMP。 步骤5：迭代与终止 将新列加入RMP，形成新的RMP。 返回 步骤2 ，重新求解更新后的RMP，得到新的对偶变量。 再次进入 步骤3 ，求解新的定价子问题。 重复这个过程，直到在 步骤4 中， 对于所有源节点 \( i \)，其定价子问题找到的最短路径的检验数 \( \bar{c}_ {i, p_ i^* } \le 0 \) 。这意味着没有能改善目标的新列了。根据单纯形法的最优性条件，此时RMP的解就是 原始主问题的最优解 。 步骤6：获取最终方案 算法终止后，最终的RMP解 \( (T^ , x_ {i,p}^ ) \) 即为原问题的最优解。 \( T^* \) 是最大化的网络生存时间。 \( x_ {i,p}^* \) 给出了每个源节点在不同路径上的 总数据分配量 。将其除以 \( T^* \)，可以得到每条路径上的 数据流速率 。这个速率分配方案，就是在给定能量约束下，能最大化网络持续运行时间的 最优路由策略 。 4. 总结与启示 问题本质 ： 这是一个经典的 多商品流（Multi-commodity Flow） 问题，每个源节点是一种商品。其线性规划模型变量极多，适合用列生成。 列生成的优势 ： 我们不需要枚举所有可能的路径（指数级）。我们只需要在每次迭代中，利用当前对偶变量（能量价格）为每个源节点求解一个最短路问题（多项式时间），来生成“有潜力”的新路径。这极大地提高了求解效率。 对偶变量的经济解释 ： 对偶变量 \( \lambda_ k \) 可以解释为节点 \( k \) 的 能量影子价格 。定价子问题寻找的是，在考虑当前网络能量“价格”体系下，传输单位数据“成本”最低的路径。算法通过不断调整路径和价格，最终达到一个平衡状态，此时没有更“便宜”的路径可以进一步延长网络寿命。 实际应用 ： 虽然这是一个集中式优化算法，但其思想可以启发分布式协议的设计。此外，此模型是许多WSN路由和生存期优化研究的基础，可以通过引入数据聚合、节点睡眠调度、移动Sink等元素进行扩展。