第4期 梁俊斌，等：带时延约束的连通目标覆盖最大化生命周期问题 ·323· 盖所有的目标.算法首先给每个节点s赋予一个权 Sink的最小跳数. 值Profit(s): 算法28)~40)行，每个在仿Dijkstra算法运行 I P-PO P I 后仍然为“offtree'”状态的节点，启发式地寻找一条 Profit(s)=- 满足限高的最小加权路径到达Sik,并更改相应节 式中：IP.-P∩P1代表处于节点s的感知范围而没 点的路径权值.其中算法29)~36)行，“offtree”状态 有被覆盖的那些目标的集合，心，是节点s的权值，即 的节点寻找一条满足限高的最小加权路径，并将路 R(s,T)中所有边权值之和.然后算法始终选取用于 径上的节点push到一个堆栈中.算法37)~39)行， 最大权值的节点(13)来覆盖目标直到所有的目标 更改新路径上新加进节点的权值」 都已经被覆盖为止.当某个节点s被选中作为采样 节点后，那么R(s,T)上的节点将更新它们的路径权 3仿真实验与结果分析 值（算法16）行). 在仿真实验中，将HLCWGC算法与其他3种算 在第3阶段，算法将选中的叶子节点以及(s, 法CWGC、HLMSC-EWARE、HLMSC-SPT进行比较， T)加入树T中，同时根据能量模型更新这些节点的 CWGC不考虑延时的约束，与HLCWGC算法一样， 能量 采用贪婪策略选取节点，但是生成网络骨干的方法 2.2限高的最小权值树构造算法(HLSPT)描述 算法输入的是经过规则1处理的图G,输出的 与HLCWGC不同.HLMSC_SPT中源节点采样到数 是一棵最小权值树T.其中该树T是以Sik为根，以 据都通过最小路径传输到Sik,但是采取一种贪婪 图G中所有的有效传感器节点作为它的子孙 策略[)选取源节点.HLMSC-EWARE是考虑延时约 算法1)~4)行是算法的初始化过程，对每个节 束后的MSC算法，使用贪婪策略[)选取源节点，但 点u初始化了它在树T中的层次Level(u)、父亲节 是采取HLSPT算法生成的限高加权树传输数据.在 点dad(u)、节点的路径权值W(u)、节点的最小跳 网络最大时延和网络生命周期2个评价标准下评估 数hops(u)、节点在树中的状态Status(u)、节点在最 算法HLCWGC、CWGC、HLMSC-EWARE、HLMSC- 小跳数算法中的父亲dad1(u). SPT R 假设每个节点的能量初始为20J,各种参数设 置为e,=50n/bit、b=100pJ/m、a=4、e,= 150nJ/bit、e,=150nJ/bit;数据的采样频率为 10kB/s6].节点的感知半径为R,=20m,传输半径 为R。=40m.假设网络生命周期上界为Lp,其大小 可以采用枚举的方法来获取.所有节点随机地散布 在100mxl00m的区域内，Sink节点位于区域的中心. 图1限高树的示例 实验1测量HLCWGC算法与r的关系.固定 Fig.I Illustration of a height-limited tree 网络中传感器节点数为60，目标数为20，取r= 算法5)~l6)行仿照Dijkstra算法，构造一棵限 0.1%、0.2%、0.4%、0.6%、0.8%、1%Lp时，设置网络 高的最小权值树，但是这棵树并不是图G的生成 时延上限H为20和10时，得到的结果绘制成图2. 树，因为部分节点虽然在离Sik跳数比较近，但是 8x10 +-H=20 在仿Dijkstra算法中却不会被选中.比如：在图1中， *-H=10 节点d虽然可以两跳路径(d,r,R)到达R,但是它的 路径权值要大于路径〈d,S,…,S,R)的权值，所以 d不会被加入到路径〈d,r,R〉中.由于树高的限制， 可能(d,S,…,S,R)超过了高度限制，所以d也不 0.02 0.040.060.080.10 能加入到(S,…,S,R)构成路径(d,S,…,S,R） tLin 算法17)~27)行使用了一个数据结构队列Q 图2 HLCWGC算法生命周期与x的关系 来对图G进行层遍历，用dad1(u)表示在节点u在 Fig.2 The relationship of HLCWGC algorithm's life time with 层遍历中的父亲节点，hops(u)表示节点u距离盖所有的目标．算法首先给每个节点 ｓ 赋予一个权 值 Ｐｒｏｆｉｔ（ｓ）： Ｐｒｏｆｉｔ（ｓ） ＝ ｜ Ｐｓ － Ｐｓ ∩ Ｐ ＇ ｜ ｗｓ ． 式中： ｜ Ｐｓ －Ｐｓ∩Ｐ ＇ ｜代表处于节点 ｓ 的感知范围而没 有被覆盖的那些目标的集合，ｗｓ 是节点 ｓ 的权值，即 Ｒ（ｓ，Ｔ）中所有边权值之和．然后算法始终选取用于 最大权值的节点（１３）来覆盖目标直到所有的目标 都已经被覆盖为止．当某个节点 ｓ 被选中作为采样 节点后，那么 Ｒ － （ｓ，Ｔ）上的节点将更新它们的路径权 值（算法 １６）行）． 在第 ３ 阶段，算法将选中的叶子节点以及 Ｒ － （ｓ， Ｔ）加入树 Ｔ 中，同时根据能量模型更新这些节点的 能量． ２．２ 限高的最小权值树构造算法（ＨＬＳＰＴ）描述 算法输入的是经过规则 １ 处理的图 Ｇ，输出的 是一棵最小权值树 Ｔ．其中该树 Ｔ 是以 Ｓｉｎｋ 为根，以 图 Ｇ 中所有的有效传感器节点作为它的子孙． 算法 １） ～４）行是算法的初始化过程，对每个节 点 ｕ 初始化了它在树 Ｔ 中的层次 Ｌｅｖｅｌ（ｕ）、父亲节 点 ｄａｄ（ｕ）、节点的路径权值 Ｗ（ ｕ）、节点的最小跳 数 ｈｏｐｓ（ｕ）、节点在树中的状态 Ｓｔａｔｕｓ（ｕ）、节点在最 小跳数算法中的父亲 ｄａｄ１（ｕ）． 图 １ 限高树的示例 Ｆｉｇ．１ Ｉｌｌｕｓｔｒａｔｉｏｎ ｏｆ ａ ｈｅｉｇｈｔ⁃ｌｉｍｉｔｅｄ ｔｒｅｅ 算法 ５） ～１６）行仿照 Ｄｉｊｋｓｔｒａ 算法，构造一棵限 高的最小权值树，但是这棵树并不是图 Ｇ 的生成 树，因为部分节点虽然在离 Ｓｉｎｋ 跳数比较近，但是 在仿 Ｄｉｊｋｓｔｒａ 算法中却不会被选中．比如：在图 １ 中， 节点 ｄ 虽然可以两跳路径〈ｄ，ｒ，Ｒ〉到达 Ｒ，但是它的 路径权值要大于路径〈ｄ，Ｓｊ，…，Ｓｉ，Ｒ〉的权值，所以 ｄ 不会被加入到路径〈 ｄ，ｒ，Ｒ〉中．由于树高的限制， 可能〈 ｄ ，Ｓｊ，…，Ｓｉ，Ｒ〉超过了高度限制，所以 ｄ 也不 能加入到〈Ｓｊ，…，Ｓｉ，Ｒ〉构成路径〈ｄ，Ｓｊ，…，Ｓｉ，Ｒ 〉． 算法 １７） ～ ２７） 行使用了一个数据结构队列 Ｑ 来对图 Ｇ 进行层遍历，用 ｄａｄ１（ ｕ）表示在节点 ｕ 在 层遍历中的父亲节点， ｈｏｐｓ （ ｕ） 表示节点 ｕ 距离 Ｓｉｎｋ 的最小跳数． 算法 ２８） ～ ４０） 行，每个在仿 Ｄｉｊｋｓｔｒａ 算法运行 后仍然为“ ｏｆｆｔｒｅｅ” 状态的节点，启发式地寻找一条 满足限高的最小加权路径到达 Ｓｉｎｋ，并更改相应节 点的路径权值．其中算法 ２９） ～ ３６）行，“ ｏｆｆｔｒｅｅ”状态 的节点寻找一条满足限高的最小加权路径，并将路 径上的节点 ｐｕｓｈ 到一个堆栈中．算法 ３７） ～ ３９）行， 更改新路径上新加进节点的权值． ３ 仿真实验与结果分析 在仿真实验中，将 ＨＬＣＷＧＣ 算法与其他 ３ 种算 法 ＣＷＧＣ、ＨＬＭＳＣ⁃ＥＷＡＲＥ、ＨＬＭＳＣ⁃ＳＰＴ 进行比较． ＣＷＧＣ 不考虑延时的约束，与 ＨＬＣＷＧＣ 算法一样， 采用贪婪策略选取节点，但是生成网络骨干的方法 与 ＨＬＣＷＧＣ 不同．ＨＬＭＳＣ＿ＳＰＴ 中源节点采样到数 据都通过最小路径传输到 Ｓｉｎｋ，但是采取一种贪婪 策略［５］选取源节点．ＨＬＭＳＣ⁃ＥＷＡＲＥ 是考虑延时约 束后的 ＭＳＣ 算法，使用贪婪策略［５］ 选取源节点，但 是采取 ＨＬＳＰＴ 算法生成的限高加权树传输数据．在 网络最大时延和网络生命周期 ２ 个评价标准下评估 算 法 ＨＬＣＷＧＣ、 ＣＷＧＣ、 ＨＬＭＳＣ⁃ＥＷＡＲＥ、 ＨＬＭＳＣ⁃ ＳＰＴ． 假设每个节点的能量初始为 ２０ Ｊ， 各种参数设 置为 ｅｔ ＝ ５０ ｎＪ／ ｂｉｔ、 ｂ ＝ １００ ｐＪ／ ｍ ４ 、 α ＝ ４、 ｅｒ ＝ １５０ ｎＪ／ ｂｉｔ、 ｅｓ ＝ １５０ ｎＪ／ ｂｉｔ； 数 据 的 采 样 频 率 为 １０ ｋＢ ／ ｓ ［ １６ ］ ．节点的感知半径为 Ｒｓ ＝ ２０ ｍ，传输半径 为 Ｒｃ ＝ ４０ ｍ．假设网络生命周期上界为 ＬＬＰ ，其大小 可以采用枚举的方法来获取．所有节点随机地散布 在 １００ ｍ×１００ ｍ 的区域内，Ｓｉｎｋ 节点位于区域的中心． 实验 １ 测量 ＨＬＣＷＧＣ 算法与 τ 的关系．固定 网络中传感器节点数为 ６０， 目标数为 ２０， 取 τ ＝ ０．１％、０．２％、０．４％、０．６％、０．８％、１％ＬＬＰ时，设置网络 时延上限 Ｈ 为 ２０ 和 １０ 时，得到的结果绘制成图 ２． 图 ２ ＨＬＣＷＧＣ 算法生命周期与 τ 的关系 Ｆｉｇ．２ Ｔｈｅ ｒｅｌａｔｉｏｎｓｈｉｐ ｏｆ ＨＬＣＷＧＣ ａｌｇｏｒｉｔｈｍ’ ｓ ｌｉｆｅ⁃ ｔｉｍｅ ｗｉｔｈ τ 第 ４ 期 梁俊斌，等：带时延约束的连通目标覆盖最大化生命周期问题 ·３２３·