在占空比无线传感器网络中寻找多约束路径的算法

Algorithms for Finding Multi-Constrained Paths in Duty-Cycle Wireless Sensor Networks

摘要: 占空比无线传感器网络已广泛应用于入侵检测、地震活动监测和一些偏远地区中。在自然传输环境中，需要对数据传输的时延、能量消耗和跳数进行优化。基于这一要求，本文研究了占空比无线传感器网络(DC-WSN)中的NP完全问题：多约束路径问题。我们将提出网络中关于多重约束条件下从源点到汇聚点的数据传输路由构建的多项式时间算法。

Abstract: The duty-cycle wireless sensor network has been widely used in the intrusion detection, monitoring of seismic activity and some remote areas. After an event occurs, the delay, energy consumption and number of hops of data transmission should be constrained. Based on this requirement, in this paper, we deal with the NP-complete problem: multi-constrained path problem in the duty-cycle wireless sensor network (DC-WSN). We will propose a polynomial time algorithm to design a source-to-sink data delivery rout under multi-stringent constraints.

1. 引言

无线传感器网络(WSN)在智能交通、环境监测、军事等领域有着广泛的应用。WSNs的主要功能之一是，事件发生后，网络中的传感器需要将感知到的实时数据传输到指定的收集器，即汇聚节点。

由于传感器采用的是电池供电，因此能效一直是研究的热点之一。因此，近十年来，低占空比网络 [1] [2] [3] [4] [5] 被认为是最关键的节能技术。在这种网络中，每个传感器节点按照一个无限二进制串的工作计划，周期性地在唤醒和休眠状态之间切换，其中1和0分别表示激活状态和休眠状态。一个节点只有在被唤醒时才能接收到数据包，并且可以在任何时间传输数据包。延迟主要是端到端延迟 [6]，即从事件发生的时间到接收器接收到关于该事件的数据包的时间的延迟。例如，给定从源节点到汇聚节点的路径P，由于活动/休眠调度，每个转发节点必须等待它的下一跳邻居节点苏醒来接收数据。对于一些对延迟敏感的应用，特别是军事监测和火灾报警，这种延迟应该受到限制。P的通信成本 [3] [7] [8] 包含距离、能量消耗、传输次数(或跳数)等。对于路径P的每一跳，如果希望到达终点的进度(距离)尽可能大，则可以减少跳数和P的长度。但是，由于各节点的唤醒调度，最大进程可能会导致某些跳长时间等待。然后，需要对延迟、成本等进行约束。

我们的贡献：

1) 研究了具有一般拓扑结构的DC-WSNs中的多约束路径 [9] [10] 问题。此外，在本文同时考虑的各种约束中，任意一对节点之间的传输延迟可以与DC-WSNs的时间扩展图 [11] 的构造相结合。

2) 重点讨论了在时间展开图中选择的路径与原始网络中所需要的非循环路径之间的关系。

然后，结合多约束路径问题，在第三节提出了一种多项式时间算法。

2. 术语与网络模型

假设无线传感器网络具有 $n$ 个点 $v_1,v_2,\cdots ,v_n$，随机分布在 $m$ 维欧几里得立方体中。对于任意节点 $v_i$，定义 $v_i$ 的通信范围，记为 $D_i$，是一个以 $v_i$ 为中心，半径为 $r$ 的 $m$ 维球。如果 $v_j$ 在通信范围 $D_i$ 内，则 $v_j$ 是 $v_i$ 的邻居， $v_i$ 可以选择 $v_j$ 作为它的下一跳节点。同时， $v_i$ 也在通信范围 $D_j$ 中。

网络可以用无向图 $G=\left(V\left(G\right),E\left(G\right)\right)$ 表示。 $V\left(G\right)=\left\{v_1,v_2,\cdots ,v_n\right\}$ 是节点集， $E\left(G\right)$ 是称为边的不同节点的无序对的集合。对于任意两个节点 $v_i,v_j\in V\left(G\right)$，边 $v_i{v}_j\in E\left(G\right)$，当且仅当这两个节点之间的距离不大于 $r$。对于任意点 $v\in V\left(G\right)$，设 $N_G\left(v\right)=\left\{u:vu\in E\left(G\right)\right\}$。如果网络为DC-WSN，则每个节点 $v_i\in V\left(G\right)$ 都有自己的工作调度 $\left(v_i^1,v_i^2,\cdots ,v_i^T\right)$，其中， $v_i^t\in \left\{0,1\right\}$ 为 $v_i$ 在时间 $t$ 期间的状态，T为工作周期。

定义2.1. ( [11] )图 $G$ 中的路径是一个序列 $\langle u_0,u_1,\cdots ,u_m\rangle$，使得 $u_i{u}_{i+1}\in E\left(G\right)$ 是相邻节点并且 $u_i\ne u_j$ 对于任意不相同的 $i,j\in \left\{0,1,\cdots ,m\right\}$。

定义2.2. 在占空比图中，给定序列 $W=\langle u_0,u_1,\cdots ,u_m\rangle$，设 $t_i$ 为转发节点 $u_i$ 的数据接收时间， $i=0,1,\cdots ,m$。那么 $W$ 是可行漫步当且仅当以下两个条件成立时。

1) $u_i$ 和 $u_{i+1}$ 是相邻节点；

2) 对于 $W$ 中的每个边 $u_i{u}_{i+1}$，数据包可以在 $t_i$ 时间之前成功地从 $u_i$ 传送到 $t_{i+1}$，在 $t_{i+1}$ 时间被 $u_{i+1}$ 接收。

而且，如果 $u_i\ne u_j$ 对于任意不同的 $i,j\in \left\{0,1,\cdots ,m\right\}$，则 $W$ 称为可行路径。

为了便于描述，我们考虑了 $G:w_i:E\left(G\right)\to R_0^{+}$ 的3个边权函数， $i=1,2,3$，其中 $w_1\left(v_i{v}_j\right)$ 是数据包在 $G$ 中通过边 $v_i{v}_j$ 时所经历的延迟。如果 $\langle v_i,v_j\rangle$ 是可行路径， $v_i$ 和 $v_j$ 接收数据的次数分别为 $\alpha$ 和 $\beta$，则 $\beta -\alpha \ge w_1\left(v_i{v}_j\right)$。给定一个数据传输可行路径 $P=\langle u_0,u_1,\cdots ,u_k\rangle$，设每个节点 $u_i$ 的接收时间为 $t_i$。设 $w_i\left(P\right)={\displaystyle \underset{j=0}{\overset{k-1}{\sum }}{w}_i}\left(u_j{u}_{j+1}\right)$， $i=1,2,3$，并且 $W_1\left(P\right)=t_k-t_0$。

DC-WSN中的多约束路径问题(WSN)表示为DC-MCP $\left(G,s,t,w_1,w_2,w_3,c_1,c_2,c_3\right)$ (MCP $\left(G,s,t,w_1,w_2,w_3,c_1,c_2,c_3\right)$ )，为求出一条从 $s$ 到 $t$ 的可行路径 $P$，使得 $W_1\left(P\right)\le c_1$ (即 $w_1\le c_1$ )， $w_2\left(P\right)\le c_2$， $w_3\left(P\right)\le c_3$。如果存在这样的路径，则该路径是DC-MCP $\left(G,s,t,w_1,w_2,w_3,c_1,c_2,c_3\right)$ (MCP $\left(G,s,t,w_1,w_2,w_3,c_1,c_2,c_3\right)$ )。然后，本文的主要问题是找到DC-MCP $\left(G,s,t,w_1,w_2,w_3,c_1,c_2,c_3\right)$ 的解。接下来，我们将分两步提出一个针对这个问题的多项式时间算法。

2.1. 具有三个权值函数的时间扩展图

设两个节点 $s$ 和 $t$ 分别为源点和汇点。在 [11] 中，Gu等人将图 $G$ 建模为时间扩展图。结合上面的三个权值函数 $w_1$， $w_2$ 和 $w_3$，按以下步骤得到一个时间扩展有向图 $G_1$ ：

1) 设 $d=\lceil c_1\rceil$。 $G_1$ 的点集为 $V\left(G_1\right)=\left\{v_i\left[t\right]:v_i\in V,1\le t\le d\right\}\cup \left\{t_0\left[0\right]\right\}$。

2) $G_1$ 的有向边集为

$\begin{array}{l}E\left(G_1\right)=\left\{\left(t\left[i\right],t_0\left[0\right]\right):1\le i\le d\right\}\cup \{\left(v_i\left[x\right],v_j\left[y\right]\right):v_i{v}_j\in E\left(G\right),1\le x<y\le d,y-x\ge \lceil w_1\left(v_i{v}_j\right)\rceil ,\\ v_j^y=1并且对于任意的z\in \left[x+1,y-1\right],v_j^z=0或者z-x<\lceil w_1\left(v_i{v}_j\right)\rceil \}.\end{array}$

3) 定义两个权值函数： $w^j:E\to R^{+}$， $j=2,3$，如下所示： $w^2\left(\left(t\left[i\right],t_0\left[0\right]\right)\right)=w^3\left(\left(t\left[i\right],t_0\left[0\right]\right)\right)=0$。对于任何的 $\left(v_i\left[t\right],v_j\left[t^{\prime }\right]\right)\in E\left(G_1-t_0\left[0\right]\right)$， $w^j\left(\left(v_i\left[t\right],v_j\left[t^{\prime }\right]\right)\right)=w_j\left(v_i{v}_j\right)$ 对于 $j=2,3$。

设 ${G^{\prime }}_1=G_1-t_0\left[0\right]$， $N_{G^{\prime }}^{+}\left(v\right)=\left\{u:\left(v,u\right)\in E\left(G^{\prime }\right)\right\}$，其中 $v\in V\left(G^{\prime }\right)$。那么以下两个观察结果是显而易见的。

观察2.3. 对于任意点 $v_i\left[t\right]\in V\left({G^{\prime }}_1\right),\left|N_{{G^{\prime }}_1}^{+}\left(v_i\left[t\right]\right)\right|\le \left|N_G\left(v_i\right)\right|$。

观察2.4. 对于图中任意的 $v_i\left[t\right]v_j\left[t^{\prime }\right]$ -路 $P$， $t^{\prime }-t\le d-1=\lceil c_1\rceil -1<c_1$。

给定图 $G_1$ 中的路 $P=\langle v_{a_1}\left[t_{a_1}\right],v_{a_2}\left[t_{a_2}\right],\cdots ,v_{a_k}\left[t_{a_k}\right]\rangle$， $P\left[v_{a_i}\left[t_{a_i}\right],v_{a_j}\left[t_{a_j}\right]\right]$ $\left(i<j\right)$ 表示 $\langle v_{a_i}\left[t_{a_i}\right],v_{a_{i+1}}\left[t_{a_{i+1}}\right],\cdots ,v_{a_j}\left[t_{a_j}\right]\rangle$ 的子路。如果 $t_0\left[0\right]\in V\left(P\right)$，则 $t_0=v_{a_k}$， $0=t_{a_k}$。设 $\tilde{P}=\langle v_{a_1},v_{a_2},\cdots ,v_{a_k}\rangle -t_0$， $\tilde{P}$ 中 $v_{a_i}$ 的数据接收时间是 $t_{a_i}$。

观察2.5. $\tilde{P}$ 是图 $G$ 中的一条可行路。

证明：通过图 $G_1$ 的构造，对每一个 $\left(v_{a_i}\left[t_{a_i}\right],v_{a_{i+1}}\left[t_{a_{i+1}}\right]\right)\in E\left(P\right)$，我们有 $v_{a_i}{v}_{a_{i+1}}\in E\left(G\right)$， $t_{a_{i+1}}-t_{a_i}\ge \lceil w_1\left(v_{a_i}{v}_{a_{i+1}}\right)\rceil$ 并且 $v_{a_{i+1}}$ 在 $t_{a_{i+1}}$ 时刻唤醒。所以对任意 $v_{a_i}{v}_{a_{i+1}}\in E\left(\tilde{P}\right)$，转发点 $v_{a_i}$ 能够在 $t_{a_{i+1}}$ 时刻之前把数据包传递到点 $v_{a_{i+1}}$，并且 $v_{a_{i+1}}$ 能够在 $t_{a_{i+1}}$ 时刻成功接收该数据包。

观察2.5表明 $\tilde{P}$ 是可行的漫步，因此 $W_1\left(\tilde{P}\right)=t_{a_k}-t_{a_1}$。另外，如果我们假设存在两个整数 $x,y\in \left\{1,2,\cdots ,k\right\}$ 满足 $a_x=a_y$，那么定义2.2表明了 $\tilde{P}$ 不是G的可行路径。将 $G_1$ 的定义与观察2.4和2.5结合起来，可以立即得到以下结果。

引理2.6. 给定MCP $\left(G_1,s\left[1\right],t_0\left[0\right],w^2,w^3,c_2,c_3\right)$ 的一个解 $P$，如果 $\tilde{P}$ 是图G中的一条可行路，则 $\tilde{P}$ 是DC-MCP $\left(G,s,t,w_1,w_2,w_3,c_1,c_2,c_3\right)$ 的一个解。

2.2. 创建一个新的权值函数

根据引理2.6，它足以找到MCP $\left(G_1,s\left[1\right],t_0\left[0\right],w^2,w^3,c_2,c_3\right)$ 的一个解 $P$ 使得 $\tilde{P}$ 是图 $G$ 中的一条可行路，则 $\tilde{P}$ 是原问题所需路径。现在，我们需要使用Chen [9] 等人提出的一个新的边权函数，用 $w$ 表示这个函数，定义为 $w:E\left(G_1\right)\to N^{+}$，其中 $N^{+}$ 是正整数集。给定一个正整数 $x$，对每一个 $\left(u,v\right)\in E\left(G_1\right)$， $w\left(\left(u,v\right)\right)=\lceil \frac{w^3\left(\left(u,v\right)\right)\cdot x}{c_3}\rceil$。

在下文中，根据如下定理我们将考虑MCP $\left(G_1,s\left[1\right],t_0\left[0\right],w^2,w,c_2,x\right)$。

定理2.7. [9] MCP $\left(G_1,s\left[1\right],t_0\left[0\right],w^2,w,c_2,x\right)$ 的解也一定是MCP $\left(G_1,s\left[1\right],t_0\left[0\right],w^2,w^3,c_2,c_3\right)$ 的解。

根据定理2.7，只要求解MCP $\left(G_1,s\left[1\right],t_0\left[0\right],w^2,w,c,x\right)$，就可以得到一个解 $P$，使 $\tilde{P}$ 是可行路径。进一步地，我们也希望 $W_1\left(\tilde{P}\right)$ 在 $w^2\left(P\right)\le c_2$ 和 $w\left(P\right)\le x$ 的约束下尽可能小。这个问题的算法将在第三节讨论。

3. 多项式时间路由算法

在本节中，基于用于MCP多约束路径问题的扩展Dijkstra最短路径算法 [9]，提出了一种用于DC-MCP的多项式时间算法。首先，我们考虑初始化阶段。

每个节点 $v_i\left[t\right]$ 的 $d\left(v_i\left[t\right],k\right)$ 在 $w$ -权值为 $k$ 的约束下，对 $w^2$ -权值的最小化起着重要作用。

集合 $Q$ 包含节点之间所有可能的对和 $w$ -权值。在下面，我们会找到一个图 $G_1$ 中的 $s\left[1\right]t_0\left[0\right]$ -路 $P$ 满足 $W_1\left(\tilde{P}\right)$ 是在 $w^2\left(P\right)\le c_2$ 和 $w\left(P\right)\le x$ 约束下的最小值。

此外，最小化 $w^2\left(P\right)$ 和 $w\left(P\right)$ 也是必要的。例如图1，考虑展开图 $G_1$ 对应到图 $G$。设 $c_1=5$， $c_2=c_3=x=4$。注意，图 $G_1$ 中存在一条路 $P=\langle v_1\left[1\right],v_2\left[2\right],v_1\left[4\right],v_3\left[5\right],t_0\left[0\right]\rangle$， $W_1\left(\tilde{P}\right)=4<c_1$， $w^2\left(P\right)=4\le c_2$ 和 $w\left(P\right)=4\le x$。显然，由于工作进度的安排t为 $\left(00001\right)$，故从s到t， $\tilde{P}$ 有最小的延时。然而，因为 $v_1\left[1\right]$， $v_1\left[4\right]\in V\left(P\right)$，所以 $\tilde{P}$ 不是图G中的一条st-可行路，此外，对于路 $P^{\prime }=\langle v_1\left[1\right],v_3\left[5\right],t_0\left[0\right]\rangle$， $W_1\left(\widetilde{P^{\prime }}\right)=W_1\left(\tilde{P}\right)$， $w^2\left(P^{\prime }\right)=2<w^2\left(P\right)$ 和 $w\left(P^{\prime }\right)=2<w\left(P\right)$， $\widetilde{P^{\prime }}$ 是一条可行路。

Figure 1. An undirected graph $G=\left(V\left(G\right),E\left(G\right)\right)$ with three weight functions w₁, w₂ and w₃, where $V\left(G\right)=\left\{v_1,v_2,v_3\right\}$ and $E\left(G\right)=\left\{v_1{v}_2,v_1{v}_3\right\}$

图1. 具有三个权值函数w₁, w₂和w₃的无向图 $G=\left(V\left(G\right),E\left(G\right)\right)$，其中 $V\left(G\right)=\left\{v_1,v_2,v_3\right\}$， $E\left(G\right)=\left\{v_1{v}_2,v_1{v}_3\right\}$

初始化算法之后，对于 $G_1$ 中以 $v_i\left[t\right]=s\left[1\right]$ 和 $k=0$ 开头的所有边，我们使用Relax算法 [9]，如下所示。并且我们可以观察到，对于 $V\left(G\right)$ 中的任何 $v_i$，都存在一个近似于 $\delta \left(v_i\right)$ 的 $d\left(v_i\left[t\right],k\right)$，其中 $\delta \left(v_i\right)$ 是从 $s$ 到 $v_i$ 所有路径中 $w^2$ -权值小于 $x$ 的 $w$ -权值。

然后我们开发了一个构造时间展开图 $G_1$ 中 $s\left[1\right]t_0\left[0\right]$ -路 $P$ 的有效算法(见下面的DC-MCP算法)，并证明了路径 $\tilde{P}$ 是定理3.1中 $G$ 的可行路径。

通过DC-MCP算法，可以得到一个根为 $s\left[1\right]$ 的有向树 $T$。在步骤2~13中的if循环的每次迭代中，在if循环的 $T$ 中添加一条有向边(参见步骤7~9)。对任意 $v_i\left[t\right]\in V\left(T-s\left[1\right]\right)$， $T$ 中唯一的 $s\left[1\right]v_i\left[t\right]$ -路 $P_1$ 有 $s\left[1\right]$ 和 $v_i\left[t\right]$ 之间所有路径的最小 $w^2$ -权值。此外，该路径的 $w$ -权值不大于 $x$，并且在其 $w^2$ -权值最小时尽可能小。根据 $G_1$ 的定义，很容易得到 $W_1\left({\tilde{P}}_1\right)=t$。结合步骤15~16，我们得到了步骤17返回的路径 $P$，当 $P$ 是从 $s$ 到 $t$ 的最小 $w^2$ -权重路时， $W_1\left(\tilde{P}\right)$ 也是最小的。

设 $\left|V\left(G\right)\right|=n$， $\left|E\left(G\right)\right|=m$。 $\left|V\left({G^{\prime }}_1\right)\right|=dn$ 且 $\left|Q\right|=\left(x+1\right)\left|V\left({G^{\prime }}_1\right)\right|=\left(x+1\right)dn$。因为 $V\left(T\right)\subseteq V\left({G^{\prime }}_1\right)$，步骤2和步骤5需要 $O\left(2\left|V\left({G^{\prime }}_1\right)\right|\right)$ 时间复杂度。步骤3~4的时间复杂度是 $O\left(2\left|Q\right|\right)$。松弛算法需要 $O\left(1\right)$ 时间。根据观察2.3，for循环(11~12行)最多有 $\left|N_{{G^{\prime }}_1}^{+}\left(v_i\left[t\right]\right)\right|\le \left|N_G\left(v_i\right)\right|\le \left|E\left(G\right)\right|$ 次迭代，所以步骤11~12的时间复杂度是 $O\left(m\right)$。在2~13行中，每次执行if循环， $E\left({G^{\prime }}_1\right)\backslash E\left(T\right)$ 中的一条边将被加到集合 $T$ 中。最多有 $\left|E\left(T\right)\right|=\left|V\left(T\right)\right|-1<\left|V\left({G^{\prime }}_1\right)\right|$ 次迭代。所以，步骤2~13需要 $O\left(dn\left(2dn+2\left(x+1\right)dn+m\right)\right)=O\left(x{c}_1^2{n}^2+c_{1}mn\right)$ 时间。步骤15的时间复杂度为 $O\left(xd\right)$。因为 $\widetilde{P^{\prime }}$ 是图 $G$ 中的路(见定理3.1)，所以步骤16需要 $O\left(n\right)$ 次。因此，总时间复杂度为 $O\left(x{c}_1^2{n}^2+c_{1}mn\right)=O\left(x{c}_1^2{n}^2+c_1{n}^3\right)$。

定理3.1. 假设 $P$ 为DC-MCP算法得到的路径。则没有点 $v\in V\left(G\right)$ 使得 $v\left[t\right],v\left[t_1\right]\in V\left(P\right)$，其中 $t,t_1\in \left[1,d\right]$。

证明：反证法。假设 $u\left[t\right]$ 是路 $P$ 的最后一个点使得存在 $u\left[t_1\right]\in V\left(P\right)$， $t_1<t$。设 $t\left[a\right]$ 是 $t_0\left[0\right]$ 在路 $P$ 中的前一个点，其中 $a\in \left[1,d\right]$。要注意的是 $w^2\left(\left(t\left[a\right],t_0\left[0\right]\right)\right)=0$。故 $w^2\left(P\right)=w^2\left(P^{\prime }\right)$，其中 $P^{\prime }=P-\left(t\left[a\right],t_0\left[0\right]\right)$。设 $P_1=P\left[u\left[t\right],t\left[a\right]\right]$ 和 ${\tilde{P}}_1=\langle u=u_0,u_1,\cdots ,u_{m-1},u_m=t\rangle$。

根据 $\tilde{P}$ 的存在性，如果 $d$ 尽可能的大，沿着路径 $\tilde{P}$，对于任意 ${t^{\prime }}_0\in \left[1,d\right]$ 存在 $1<{t^{\prime }}_0<{t^{\prime }}_1<\cdots <{t^{\prime }}_m\le d$ 使得 $P_2\left({t^{\prime }}_0\right)=\langle u_0\left[{t^{\prime }}_0\right],u_1\left[{t^{\prime }}_1\right],u_2\left[{t^{\prime }}_2\right],\dots ,u_m\left[{t^{\prime }}_m\right]\rangle$ 是图 $G_1$ 上的路， $w^2\left(P_2\left[{t^{\prime }}_0\right]\right)=w^2\left(P_1\right)$， $w\left(P_2\left[{t^{\prime }}_0\right]\right)=w\left(P_1\right)$。假设当 ${t^{\prime }}_0=t_1$ 时 ${t^{\prime }}_m=b$。则 $P_3=P\left[s\left[1\right],u\left[t_1\right]\right]+P_2\left(t_1\right)$ 是一条 $s\left[1\right]t\left[b\right]$ -路，

$w^2\left(P_3\right)=w^2\left(P\left[s\left[1\right],u\left[t_1\right]\right]\right)+w^2\left(P_2\left(t_1\right)\right)=w^2\left(P\left[s\left[1\right],u\left[t_1\right]\right]\right)+w^2\left(P_1\right)<w^2\left(P\right)\le c_2$ . (3.1)

同样地，

$w\left(P_3\right)<w\left(P\right)\le x$ . (3.2)

根据第15步，对任意 $a^{\prime }<a$ 和 $k\in \left[0,x\right]$，有 $t^{a^{\prime }}=0$ 或者 $d\left(t\left[a^{\prime }\right],k\right)>c_2$。因此， $b\in \left[a,d\right]$。目前， $P_1$ 是一条 $u\left[t\right]t\left[a\right]$ -路， $P_2\left(t_1\right)$ 是一条 $u\left[t_1\right]t\left[b\right]$ -路。

情况1. $b=a$。

在这种情况下， $P_3$ 是 $G_1$ 中一条 $s\left[1\right]t\left[a\right]$ -路。根据公式(3.1)、(3.2)和DC-MCP算法的3~8步可知，与P相比， $P_3$ 是一个更好的选择，所以P不在集合T中。矛盾。

情况2. $b>a$。

注意 $t_1<t$， $b>a$ 和 ${\tilde{P}}_1={\tilde{P}}_2\left(t_1\right)$，可以看出路径 $P_1$ 和 $P_2\left(t_1\right)$ 之间至少有一个交集。

情况2.1. $P_1$ 和 $P_2\left(t_1\right)$ 至少有一个公共节点。

因为 $b>a$，我们能够选择 $u_i{u}_{i+1}\in E\left({\tilde{P}}_1\right)$ 使得 $\left(u_i\left[t_2\right],u_{i+1}\left[t_3\right]\right)\in E\left(P_1\right)$ 和 $\left(u_i\left[t_2\right],u_{i+1}\left[t_4\right]\right)\in E\left(P_2\left(t_1\right)\right)$，其中 $t_2<t_3<t_4$。则 $u_i^{t_2}=u_{i+1}^{t_3}=u_{i+1}^{t_4}=1$。将此与 $E\left(G_1\right)$ 的定义结合起来，我们有 $\left(u_i\left[t_2\right],u_{i+1}\left[t_4\right]\right)\in E\left(P_2\left(t_1\right)\right),$ $\lceil w_1\left(u_i,u_{i+1}\right)\rceil >t_3-t_2$。

因为 $\left(u_i\left[t_2\right],u_{i+1}\left[t_3\right]\right)\in E\left(P_1\right)$， $\lceil w_1\left(u_i,u_{i+1}\right)\rceil \le t_3-t_2$，故产生矛盾。

情况2.2. $P_1$ 和 $P_2\left(t_1\right)$ 没有公共节点。

现在存在 $u_i{u}_{i+1}\in E\left({\tilde{P}}_1\right)$ 满足 $\left(u_i\left[t_5\right],u_{i+1}\left[t_6\right]\right)\in E\left(P_2\left(t_1\right)\right)$ 和 $\left(u_i\left[t_7\right],u_{i+1}\left[t_8\right]\right)\in E\left(P_1\right)$，其中 $t_5<t_7<t_8<t_6$。根据 $E\left(G_1\right)$ 的定义， $u_i^{t_5}=u_{i+1}^{t_6}=u_i^{t_7}=u_{i+1}^{t_8}=1$。在此基础上，因为 $\left(u_i\left[t_5\right],u_{i+1}\left[t_6\right]\right)\in E\left(G_1\right)$，我们有 $\lceil w_1\left(u_i{u}_{i+1}\right)\rceil >t_8-t_5>t_8-t_7$。

Since $\left(u_i\left[t_7\right],u_{i+1}\left[t_8\right]\right)\in E\left(P_1\right),$ $\lceil w_1\left(u_i{u}_{i+1}\right)\rceil \le t_8-t_7$，故产生矛盾。

定理3.2. 如果P是通过DC-MCP算法获得的路，则 $\tilde{P}$ 是LDC-MCP $\left(G,s,t,w_1,w_2,w_3,c_1,c_2,c_3\right)$ 的一个解。

证明：因为P是通过DC-MCP算法获得的路，很容易看出 $w\left(P\right)\le x$。从第15步开始， $W_1\left(\tilde{P}\right)$ 是在 $w^2\left(P\right)\le c_2$ 限制下的所有 $s\left[1\right]t_0\left[0\right]$ -路中权值最小的。所以 $P$ 是MCP $\left(G_1,s\left[1\right],t_0\left[0\right],w^2,w,c_2,x\right)$ 的一个解。根据定理2.7，P也是MCP $\left(G_1,s\left[1\right],t_0\left[0\right],w^2,w^3,c_2,c_3\right)$ 的一个解。另外，观察2.5和定理3.1表明了 $\tilde{P}$ 是图G中的一条可行路。因此，根据引理2.6， $\tilde{P}$ 是DC-MCP $\left(G,s,t,w_1,w_2,w_3,c_1,c_2,c_3\right)$ 的一个解。

4. 结论

摘要研究了占空比无线传感器网络(DC-WSN)环境中的多约束路径问题。该问题形式化为DC-MCP $\left(G,s,t,w_i,c_i\right)$，当 $i=3$ 时，只需多项式时间即可求解。根据DC-WSN定义图G。将G与所有节点的工作进度相结合，构造了一个具有两个权函数的时间展开图 $G_1$。然后将问题DC-MCP $\left(G,s,t,w_1,w_2,w_3,c_1,c_2,c_3\right)$ 替换为另一个MCP $\left(G_1,s\left[1\right],t_0\left[0\right],w^2,w^3,c_2,c_3\right)$，可以化简为问题MCP $\left(G_1,s\left[1\right],t_0\left[0\right],w^2,w,c_2,x\right)$。在 [9] 中扩展的Dijkstra算法的基础上，利用DC-MCP算法在多项式时间上求出MCP $\left(G_1,s\left[1\right],t_0\left[0\right],w^2,w,c,x\right)$ 的一个解P。另外，由P得到的路径 $\tilde{P}\subseteq G$ 没有循环，是原问题的一个解。

为了进一步讨论，我们将尝试将我们的工作与k-不相交路径问题、数据收集问题和其他复杂的变体结合起来。

基金项目

山西省自然科学基金201801D221193。

NOTES

^*通讯作者。