第4期 梁俊斌，等：带时延约束的连通目标覆盖最大化生命周期问题 ·321· DCCTC问题就是在保证目标被完全覆盖的前提下， Height(T(r))≤H,1≤i≤x. 如何通过调度节点的工作/睡眠状态，均衡节点的网 定理1 HLMCT问题是NP-Complete的. 络消耗，从而最大化网络生命周期.其中，目标被完 证明因为MCT问题[)是假设限高H=o时 全覆盖指所有的目标均在至少一个节点的感知半径 HLMCT的一个特例，MSC问题)是假设限高H=1 内：延时约束则是目标点的数据通过工作节点的单 时HLMCT的一个特例.根据约束策略1s],因为 跳或者多跳在不超过△时间内送到Sik, MCT问题和MSC问题是NP-Complete的，所以 定义2覆盖树问题(MCT). HLMCT也是NP-Complete的.证毕. 给定一个有向图G=(V,E)和节点的初始能量 E。(s),通过找到一系列的树T(T1),T(T2),, 2时延约束的连通目标覆盖启发式算法 T(T,)和它们的操作时间T1,T2,…,T,使得网络生 本文设计了一个加权通信的限高覆盖树贪婪算 命周期L最大化 height-limited communication weighted greedy 将问题数学化表示为 cover,.HLCWGC)来解决HLMCT问题. 2.1 HLCWGC算法描述 max L HLCWGC只需要输入网络的基本参数S、P、R sL2E(s,T(,)）≤E,(),YseS 和操作时间τ，经过计算即可输出一系列高度受限 =1 的覆盖树T,T2,…,T 用T(r)=(S,(r)US,(r),E(r))表示在操作 为了便于描述，首先定义需要用到的一些符号： 时间τ内构建的高度受限的树.T(τ)的特性如下： S,为存活节点集合，S,为存活节点中能覆盖目标的 1)树根是Sik节点：2)树的叶子是负责采样的节 节点集合，P,为能被节点s覆盖的目标集合，0，为 点：3)每个目标至少与一个叶子节点相连 节点在HLMWCT算法中的路径权值，W(s)为节点s 在T()中，每个节点的能量消耗模型[)为 的贡献，s∈S,R(s,T)为在树T中节点s到Sink R E(s,T(T))= 的路径，R(s,T)=〈s,s1,…,R〉； [e,B(r)+emB(r),s∈S,(r)ands使S,(r): (e +e,)B(T)D(s,T(T)),sS,(T)and s eS,(T); R(s,T)为R(s,T)中除了源点s和终点RHLC e,B(r）+eaB(r）t WGC算法的描述如下： 1)S=S,S,=☑，x=1: (e+e,)B(T)D(s,T(T)),s E S,(T)ns,(T); 2)for eachs∈S; 0,s年S.(）ands主S.(r). 3)E,(s)=E(s): 式中：T(r)代表在操作时间r内构建的一棵树， B(?)代表在操作时间？内节点采集到的数据包的 4)ifP,≠☑，S,=S,U{s};end if; 5)end for 数量：e,和e,分别表示感知和传输1bit数据的能耗， 6)while U,esP,=P and S,≠☑， em表示节点发送能量，eam=e=e,+b·d份，其中节 7)phase 1: 点s:是发送节点，s是接收节点，d是s:和s之间的距 8)for each link(si,s)wj=exEo(s)/E,(s;); 离，a表示路径衰减因子，e,和b是常量；D(s,T(r))》 end for 表示节点s在T(r)中的后代节点数 9)Build a tree with HLSPT algorithm 定义3限高的覆盖树问题(height limited max- 10)phase 2: imum cover tree problem,HLMCT). 11)S=0,P'=☑，T=☑，T.=T; 给定一个有向图G=(V,E)、最大树高H和节 12 while P'≠P, 点的初始能量E。(s),通过找到一系列高度限定为 13)Find a sensor s'with max profit W(s) H的树T(x1),T(r2),,T(r)和它们的操作时间 T1、T2,…,T使得网络的生命周期L最大 14)S.=S.Us,P'=P'UP,.; 问题数学化表示为： l5)for each s∈R(s°，T) maxL=立： 16)0,=w,+(em+e,)B(r）×w,/E,(s) i=1 17)end for st.∑E(s,T(:)≤E(s),HseS: 18)end while 19)phase 3:ＤＣＣＴＣ 问题就是在保证目标被完全覆盖的前提下， 如何通过调度节点的工作／ 睡眠状态，均衡节点的网 络消耗，从而最大化网络生命周期．其中，目标被完 全覆盖指所有的目标均在至少一个节点的感知半径 内；延时约束则是目标点的数据通过工作节点的单 跳或者多跳在不超过 Δ 时间内送到 Ｓｉｎｋ． 定义 ２ 覆盖树问题［９］ （ＭＣＴ）． 给定一个有向图 Ｇ ＝ （Ｖ，Ｅ）和节点的初始能量 Ｅ０（ ｓ），通过找到一系列的树 Ｔ （ τ１ ）， Ｔ （ τ２ ），．．．， Ｔ（τｘ）和它们的操作时间 τ１ ，τ２ ，…，τｘ 使得网络生 命周期 Ｌ 最大化． 将问题数学化表示为 ｍａｘ Ｌ ＝ ∑ ｘ ｉ ＝ １ τｉ； ｓ．ｔ．∑ ｘ ｉ ＝ １ Ｅ（ｓ，Ｔ（τｉ）） ≤ Ｅ０（ｓ），∀ｓ ∈ Ｓ． 用 Ｔ（τ）＝ （ Ｓｓ（ τ）∪Ｓｒ（ τ），Ｅ（ τ））表示在操作 时间 τ 内构建的高度受限的树．Ｔ（ τ） 的特性如下： １）树根是 Ｓｉｎｋ 节点；２） 树的叶子是负责采样的节 点；３）每个目标至少与一个叶子节点相连． 在 Ｔ（τ）中，每个节点的能量消耗模型［９］为 Ｅ（ｓ，Ｔ（τ）） ＝ ｅｓＢ（τ） ＋ ｅｔｒａｎｓＢ（τ）， ｓ ∈Ｓｓ（τ） ａｎｄ ｓ ∉Ｓｒ（τ）； （ｅｔｒａｎｓ ＋ ｅｒ）Ｂ（τ）Ｄ（ｓ，Ｔ（τ））， ｓ ∉Ｓｓ（τ） ａｎｄ ｓ ∈Ｓｒ（τ）； ｅｓＢ（τ） ＋ ｅｔｒａｎｓＢ（τ） ＋ （ｅｔｒａｎｓ ＋ ｅｒ）Ｂ（τ）Ｄ（ｓ，Ｔ（τ））， ｓ ∈Ｓｓ（τ） ∩Ｓｒ（τ）； ０， ｓ ∉Ｓｓ（τ） ａｎｄ ｓ ∉Ｓｒ（τ）． ì î í ï ï ïï ï ï ï 式中：Ｔ（ τ） 代表在操作时间 τ 内构建的一棵树， Ｂ（τ）代表在操作时间 τ 内节点采集到的数据包的 数量；ｅｓ 和 ｅｒ 分别表示感知和传输１ ｂｉｔ数据的能耗， ｅｔｒａｎｓ表示节点发送能量，ｅｔｒａｎｓ ＝ ｅ ｔ ｉｊ ＝ ｅｔ ＋ｂ·ｄ α ｉｊ，其中节 点 ｓｉ是发送节点，ｓｊ是接收节点，ｄｉｊ是 ｓｉ和 ｓｊ之间的距 离，α 表示路径衰减因子，ｅｔ和 ｂ 是常量；Ｄ（ｓ，Ｔ（τ）） 表示节点 ｓ 在 Ｔ（τ）中的后代节点数． 定义 ３ 限高的覆盖树问题（ｈｅｉｇｈｔ ｌｉｍｉｔｅｄ ｍａｘ⁃ ｉｍｕｍ ｃｏｖｅｒ ｔｒｅｅ ｐｒｏｂｌｅｍ，ＨＬＭＣＴ）． 给定一个有向图 Ｇ ＝ （Ｖ，Ｅ）、最大树高 Ｈ 和节 点的初始能量 Ｅ０ （ ｓ），通过找到一系列高度限定为 Ｈ 的树 Ｔ（τ１ ），Ｔ（ τ２ ），．．．，Ｔ（ τｘ）和它们的操作时间 τ１ 、τ２ ，…，τｘ 使得网络的生命周期 Ｌ 最大． 问题数学化表示为： ｍａｘ Ｌ ＝ ∑ ｘ ｉ ＝ １ τｉ； ｓ．ｔ． ∑ ｘ ｉ ＝ １ Ｅ（ｓ，Ｔ（τｉ）） ≤ Ｅ０（ｓ），∀ｓ ∈ Ｓ； Ｈｅｉｇｈｔ（Ｔ（τｉ）） ≤ Ｈ，１ ≤ ｉ ≤ ｘ． 定理 １ ＨＬＭＣＴ 问题是 ＮＰ⁃Ｃｏｍｐｌｅｔｅ 的． 证明 因为 ＭＣＴ 问题［９］ 是假设限高 Ｈ ＝ ¥时 ＨＬＭＣＴ 的一个特例，ＭＳＣ 问题［５］ 是假设限高 Ｈ ＝ １ 时 ＨＬＭＣＴ 的一个特例． 根据约束策 略［１ ５ ］ ， 因 为 ＭＣＴ 问 题 和 ＭＳＣ 问 题 是 ＮＰ⁃Ｃｏｍｐｌｅｔｅ 的， 所 以 ＨＬＭＣＴ 也是 ＮＰ⁃Ｃｏｍｐｌｅｔｅ 的．证毕． ２ 时延约束的连通目标覆盖启发式算法 本文设计了一个加权通信的限高覆盖树贪婪算 法 （ ｈｅｉｇｈｔ⁃ｌｉｍｉｔｅｄ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｗｅｉｇｈｔｅｄ ｇｒｅｅｄｙ ｃｏｖｅｒ， ＨＬＣＷＧＣ）来解决 ＨＬＭＣＴ 问题． ２．１ ＨＬＣＷＧＣ 算法描述 ＨＬＣＷＧＣ 只需要输入网络的基本参数 Ｓ、Ｐ、Ｒ 和操作时间 τ，经过计算即可输出一系列高度受限 的覆盖树 Ｔ１ ，Ｔ２ ，…，Ｔｘ ． 为了便于描述，首先定义需要用到的一些符号： Ｓｌ 为存活节点集合，Ｓｓ 为存活节点中能覆盖目标的 节点集合，Ｐｓ 为能被节点 ｓ 覆盖的目标集合，ｗｓ 为 节点在 ＨＬＭＷＣＴ 算法中的路径权值，Ｗ（ｓ）为节点 ｓ 的贡献，ｓ∈Ｓｓ，Ｒ（ｓ，Ｔ）为在树 Ｔ 中节点 ｓ 到 Ｓｉｎｋ Ｒ 的路径，Ｒ（ｓ，Ｔ）＝ 〈ｓ， ｓ１ ，…，Ｒ〉； Ｒ － （ｓ，Ｔ）为 Ｒ（ｓ，Ｔ）中除了源点 ｓ 和终点 Ｒ．ＨＬＣ⁃ ＷＧＣ 算法的描述如下： １）Ｓｌ ＝ Ｓ，Ｓｓ ＝∅，ｘ ＝ １； ２）ｆｏｒ ｅａｃｈ ｓ∈Ｓｌ； ３）Ｅｒ（ｓ）＝ Ｅ０（ｓ）； ４）ｉｆ Ｐｓ≠∅，Ｓｓ ＝ Ｓｓ∪｛ｓ｝；ｅｎｄ ｉｆ； ５）ｅｎｄ ｆｏｒ ６）ｗｈｉｌｅ ∪ｓ∈ＳＰｓ ＝Ｐ ａｎｄ Ｓｌ≠∅， ７）ｐｈａｓｅ １： ８）ｆｏｒ ｅａｃｈ ｌｉｎｋ（ ｓｉ，ｓｊ ） ｗｉｊ ＝ ｅ ｔ ｉｊ ×Ｅ０ （ ｓｉ ） ／ Ｅｒ（ ｓｉ ）； ｅｎｄ ｆｏｒ ９）Ｂｕｉｌｄ ａ ｔｒｅｅ ｗｉｔｈ ＨＬＳＰＴ ａｌｇｏｒｉｔｈｍ １０） ｐｈａｓｅ ２： １１）Ｓ ＇ ｓ ＝∅，Ｐ′＝∅，Ｔｘ ＝∅，τｘ ＝ τ； １２ ｗｈｉｌｅ Ｐ′≠Ｐ， １３）Ｆｉｎｄ ａ ｓｅｎｓｏｒ ｓ ∗ ｗｉｔｈ ｍａｘ ｐｒｏｆｉｔ Ｗ（ｓ ∗ ） １４）Ｓ ＇ ｓ ＝ Ｓ ＇ ｓ∪｛ｓ ∗ ｝， Ｐ ＇ ＝Ｐ ＇∪Ｐｓ∗ ； １５）ｆｏｒ ｅａｃｈ ｓ∈Ｒ － （ｓ ∗ ，Ｔｘ） １６） ｗｓ ＝ｗｓ ＋（ｅｔｒａｎｓ ＋ｅｒ）Ｂ（τ）×ｗｓ ／ Ｅｒ（ｓ） １７）ｅｎｄ ｆｏｒ １８）ｅｎｄ ｗｈｉｌｅ １９）ｐｈａｓｅ ３： 第 ４ 期 梁俊斌，等：带时延约束的连通目标覆盖最大化生命周期问题 ·３２１·