第4期 梁俊斌，等：带时延约束的连通目标覆盖最大化生命周期问题 ·325· 35 -CWGC 2001:472-476. ·-HLCWGC 30 -HLMSC-EWARE [4]CARDEI M,DU Dingzhu.Improving wireless sensor net- HLMSC-SPT work lifetime through power aware organization[J].Wire- 25 less Networks,2005,11(3):333-340. 20 [5]CARDEI M,THAI M T,LI Yingshu,et al.Energy-efficient 15 target coverage in wireless sensor networks[C]//24th IEEE International Conference on Computer Communications(IN- 10 F0C0M).Miami,USA,2005:1976-1984. [6]CARDEI M,WU Jie,LU Mingming,et al.Maximum net- work lifetime in wireless sensor networks with adjustable 0 40 60 80100120140 sensing ranges[C]//IEEE International Conference of Wire- 节点数量 less and Mobile Computing,Networking and Communica- (b)最大网络延迟 tions WiMob).Montreal,Canada,2005:1-5. 图5网络时延约束为5时算法比较 [7]LU Mingming,WU Jie,CARDEI M,et al.Energy-efficient Fig.5 Comparison when the delay of network is 5 connected coverage of discrete targets in wireless sensor ne- 从图4和图5中可以看到在网络时延约束为 torks[C]//International Conference of Computer Networks and Mobile Computing (ICCNMC).Zhangjiajie,China, 10和5的情况下，HLCWGC算法生成的生命周期都 2005:137-147. 要比HLMSC-EWARE和HLMSC-SPT要好，在网络 [8]ZHAO Qun,GURUSAMY M.Lifetime maximization using 最大延时方面CWGC算法的最大延时相对于其他 observation time scheduling in multi-hop sensor networks 算法而言是十分巨大的，HLCWGC和HLMSC- [C]//IEEE/CreateNet International Workshop on Broad- EWARE的网络最大延时差不多，HLMSC-SPT的延 band Advanced Sensor Networks BroadNets )Boston, 时最小，但是它的网络生命周期也是最小的. USA,2005:1-5. [9]ZHAO Qun,GURUSAMY M.Lifetime maximization for 4 结束语 connected target coverage in wireless sensor networks[J]. IEEE/ACM Transactions on Networking,2008,16(6): 针对时延敏感的无线传感器网络应用，提出了带 1378-1391. 时延约束的连通目标覆盖问题本文首先将带时延约束 [10]LI Deying,CAO Jiannong,LIU Ming,et al.K-connected 的连通目标覆盖问题建模成限高的最大覆盖树问题， target coverage problem in wireless sensor networks[J]. 然后证明了限高的最大覆盖树问题是NP-Complete的， Lecture Notes in Computer Science,2007,46(1):20-31. 最后设计了一种快速的启发式算法HLCWGC来解决 [11]WU Lidong,DU Hongwei,WU Weili,et al.Approxima- tions for minimum connected sensor cover C]//32nd 限高的最大覆盖树问题.仿真结果表明，HLCWGC能在 IEEE International Conference on Computer Communica- 保证覆盖的前提下，获得比已有算法更长的网络生命 tions(INFOCOM).Turin,Italy,2013:1424-1432 周期未来的工作将考虑网络的容错性及更高目标覆盖 [12]GU Yu,LIU Hengchang,ZHAO Baohua.Target coverage 程度等，使得网络满足时延约束的前提下网络的生命 with QoS requirements in wireless sensor networks[C]// 周期最大。 IEEE International Conference on Intelligent Pervasive Computing(IPC).Jeju Island,Korea,2007:35-38. 参考文献： [13]BOUKERCHE A.PAZZI R.ARAUJO R.A fast and relia- ble protocol for wireless sensor networks in critical condi- [1]任丰原，黄海宁，林闯.无线传感器网络[J].软件学报， tions monitoring applications[C]//7th ACM International 2003,14(7):1282-1291. Symposium on Modeling,Analysis and Simulation of Wire- REN Fengyuan,HUANG Haining,LIN Chuang.Wireless less and Mobile Systems MSWiM).Venice,Italy,2004: sensor networks J].Journal of Software,2003,14(7): 157-164. 1282-1291. [14]YU Zuoming,TENG Jin,LI Xinfeng.On wireless network [2]崔莉，鞠海玲，苗勇，等.无线传感器网络研究进展[J] coverage in bounded areas[C]//32nd IEEE International 计算机研究与发展，2005,42(1)：163174. Conference on Computer Communications INFOCOM). CUI Li,JU Hailing,MIAO Yong,et al.Overview of wire- Turin,aly,2013:1752-1760. less sensor networks[J].Journal of Computer Research and [15]AREY M R,JOHNSON D S.Computers and intractability: Development,2005,42(1):163-174. a guide to the theory of NP-Completeness[M].New York: [3]SLIJEPCEVIC S,POTKONJAK M.Power efficient organiza- W.H.Freeman,1979:210-216. tion of wireless sensor networks C]//IEEE International [16]CHANG J H,TASSIULAS L.Maximum lifetime routing in Conference of Communications ICC).Beijing,China, wireless sensor networks[J].IEEE/ACM Transactions on（ｂ）最大网络延迟 图 ５ 网络时延约束为 ５ 时算法比较 Ｆｉｇ．５ Ｃｏｍｐａｒｉｓｏｎ ｗｈｅｎ ｔｈｅ ｄｅｌａｙ ｏｆ ｎｅｔｗｏｒｋ ｉｓ ５ 从图 ４ 和图 ５ 中可以看到在网络时延约束为 １０ 和 ５ 的情况下，ＨＬＣＷＧＣ 算法生成的生命周期都 要比 ＨＬＭＳＣ⁃ＥＷＡＲＥ 和 ＨＬＭＳＣ⁃ＳＰＴ 要好，在网络 最大延时方面 ＣＷＧＣ 算法的最大延时相对于其他 算 法 而 言 是 十 分 巨 大 的， ＨＬＣＷＧＣ 和 ＨＬＭＳＣ⁃ ＥＷＡＲＥ 的网络最大延时差不多，ＨＬＭＳＣ⁃ＳＰＴ 的延 时最小，但是它的网络生命周期也是最小的． ４ 结束语 针对时延敏感的无线传感器网络应用，提出了带 时延约束的连通目标覆盖问题．本文首先将带时延约束 的连通目标覆盖问题建模成限高的最大覆盖树问题， 然后证明了限高的最大覆盖树问题是 ＮＰ⁃Ｃｏｍｐｌｅｔｅ 的， 最后设计了一种快速的启发式算法 ＨＬＣＷＧＣ 来解决 限高的最大覆盖树问题．仿真结果表明，ＨＬＣＷＧＣ 能在 保证覆盖的前提下，获得比已有算法更长的网络生命 周期．未来的工作将考虑网络的容错性及更高目标覆盖 程度等，使得网络满足时延约束的前提下网络的生命 周期最大． 参考文献： ［１］任丰原，黄海宁，林闯． 无线传感器网络［ Ｊ］． 软件学报， ２００３， １４（７）： １２８２⁃１２９１． ＲＥＮ Ｆｅｎｇｙｕａｎ， ＨＵＡＮＧ Ｈａｉｎｉｎｇ， ＬＩＮ Ｃｈｕａｎｇ． Ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｓｏｆｔｗａｒｅ， ２００３， １４ （ ７）： １２８２⁃１２９１． ［２］崔莉，鞠海玲，苗勇，等． 无线传感器网络研究进展［ Ｊ］． 计算机研究与发展， ２００５， ４２ （１）： １６３⁃１７４． ＣＵＩ Ｌｉ， ＪＵ Ｈａｉｌｉｎｇ， ＭＩＡＯ Ｙｏｎｇ， ｅｔ ａｌ． Ｏｖｅｒｖｉｅｗ ｏｆ ｗｉｒｅ⁃ ｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ， ２００５， ４２ （１）： １６３⁃１７４． ［３］ＳＬＩＪＥＰＣＥＶＩＣ Ｓ， ＰＯＴＫＯＮＪＡＫ Ｍ． Ｐｏｗｅｒ ｅｆｆｉｃｉｅｎｔ ｏｒｇａｎｉｚａ⁃ ｔｉｏｎ ｏｆ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ［ Ｃ］ ／ ／ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｆ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ （ ＩＣＣ ）． Ｂｅｉｊｉｎｇ， Ｃｈｉｎａ， ２００１： ４７２⁃４７６． ［４］ ＣＡＲＤＥＩ Ｍ， ＤＵ Ｄｉｎｇｚｈｕ． Ｉｍｐｒｏｖｉｎｇ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔ⁃ ｗｏｒｋ ｌｉｆｅｔｉｍｅ ｔｈｒｏｕｇｈ ｐｏｗｅｒ ａｗａｒｅ ｏｒｇａｎｉｚａｔｉｏｎ ［ Ｊ］． Ｗｉｒｅ⁃ ｌｅｓｓ Ｎｅｔｗｏｒｋｓ， ２００５， １１（３）： ３３３⁃３４０． ［５］ＣＡＲＤＥＩ Ｍ， ＴＨＡＩ Ｍ Ｔ， ＬＩ Ｙｉｎｇｓｈｕ， ｅｔ ａｌ． Ｅｎｅｒｇｙ⁃ｅｆｆｉｃｉｅｎｔ ｔａｒｇｅｔ ｃｏｖｅｒａｇｅ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｃ］ ／ ／ ２４ｔｈ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ（ ＩＮ⁃ ＦＯＣＯＭ）． Ｍｉａｍｉ， ＵＳＡ， ２００５： １９７６⁃１９８４． ［６］ＣＡＲＤＥＩ Ｍ， ＷＵ Ｊｉｅ， ＬＵ Ｍｉｎｇｍｉｎｇ， ｅｔ ａｌ． Ｍａｘｉｍｕｍ ｎｅｔ⁃ ｗｏｒｋ ｌｉｆｅｔｉｍｅ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ｗｉｔｈ ａｄｊｕｓｔａｂｌｅ ｓｅｎｓｉｎｇ ｒａｎｇｅｓ［Ｃ］ ／ ／ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｆ Ｗｉｒｅ⁃ ｌｅｓｓ ａｎｄ Ｍｏｂｉｌｅ Ｃｏｍｐｕｔｉｎｇ， Ｎｅｔｗｏｒｋｉｎｇ ａｎｄ Ｃｏｍｍｕｎｉｃａ⁃ ｔｉｏｎｓ （ＷｉＭｏｂ）． Ｍｏｎｔｒｅａｌ， Ｃａｎａｄａ， ２００５： １⁃５． ［７］ＬＵ Ｍｉｎｇｍｉｎｇ， ＷＵ Ｊｉｅ， ＣＡＲＤＥＩ Ｍ， ｅｔ ａｌ． Ｅｎｅｒｇｙ⁃ｅｆｆｉｃｉｅｎｔ ｃｏｎｎｅｃｔｅｄ ｃｏｖｅｒａｇｅ ｏｆ ｄｉｓｃｒｅｔｅ ｔａｒｇｅｔｓ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅ⁃ ｔｏｒｋｓ［ Ｃ］ ／ ／ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｎｅｔｗｏｒｋｓ ａｎｄ Ｍｏｂｉｌｅ Ｃｏｍｐｕｔｉｎｇ （ ＩＣＣＮＭＣ）． Ｚｈａｎｇｊｉａｊｉｅ， Ｃｈｉｎａ， ２００５： １３７⁃１４７． ［８］ ＺＨＡＯ Ｑｕｎ， ＧＵＲＵＳＡＭＹ Ｍ． Ｌｉｆｅｔｉｍｅ ｍａｘｉｍｉｚａｔｉｏｎ ｕｓｉｎｇ ｏｂｓｅｒｖａｔｉｏｎ ｔｉｍｅ ｓｃｈｅｄｕｌｉｎｇ ｉｎ ｍｕｌｔｉ⁃ｈｏｐ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ［Ｃ］ ／ ／ ＩＥＥＥ／ ＣｒｅａｔｅＮｅｔ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｂｒｏａｄ⁃ ｂａｎｄ Ａｄｖａｎｃｅｄ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ （ ＢｒｏａｄＮｅｔｓ ）． Ｂｏｓｔｏｎ， ＵＳＡ， ２００５： １⁃５． ［ ９］ ＺＨＡＯ Ｑｕｎ， ＧＵＲＵＳＡＭＹ Ｍ． Ｌｉｆｅｔｉｍｅ ｍａｘｉｍｉｚａｔｉｏｎ ｆｏｒ ｃｏｎｎｅｃｔｅｄ ｔａｒｇｅｔ ｃｏｖｅｒａｇｅ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［ Ｊ］． ＩＥＥＥ／ ＡＣＭ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｎｅｔｗｏｒｋｉｎｇ， ２００８， １６ （ ６）： １３７８⁃１３９１． ［１０］ＬＩ Ｄｅｙｉｎｇ， ＣＡＯ Ｊｉａｎｎｏｎｇ， ＬＩＵ Ｍｉｎｇ， ｅｔ ａｌ． Ｋ⁃ｃｏｎｎｅｃｔｅｄ ｔａｒｇｅｔ ｃｏｖｅｒａｇｅ ｐｒｏｂｌｅｍ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ［ Ｊ］． Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， ２００７， ４６（１）： ２０⁃３１． ［１１］ＷＵ Ｌｉｄｏｎｇ， ＤＵ Ｈｏｎｇｗｅｉ， ＷＵ Ｗｅｉｌｉ， ｅｔ ａｌ． Ａｐｐｒｏｘｉｍａ⁃ ｔｉｏｎｓ ｆｏｒ ｍｉｎｉｍｕｍ ｃｏｎｎｅｃｔｅｄ ｓｅｎｓｏｒ ｃｏｖｅｒ ［ Ｃ ］ ／ ／ ３２ｎｄ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａ⁃ ｔｉｏｎｓ（ＩＮＦＯＣＯＭ）． Ｔｕｒｉｎ， Ｉｔａｌｙ， ２０１３： １４２４⁃１４３２． ［１２］ＧＵ Ｙｕ， ＬＩＵ Ｈｅｎｇｃｈａｎｇ， ＺＨＡＯ Ｂａｏｈｕａ． Ｔａｒｇｅｔ ｃｏｖｅｒａｇｅ ｗｉｔｈ ＱｏＳ ｒｅｑｕｉｒｅｍｅｎｔｓ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［ Ｃ］ ／ ／ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｐｅｒｖａｓｉｖｅ Ｃｏｍｐｕｔｉｎｇ（ＩＰＣ）． Ｊｅｊｕ Ｉｓｌａｎｄ， Ｋｏｒｅａ， ２００７： ３５⁃３８． ［１３］ＢＯＵＫＥＲＣＨＥ Ａ， ＰＡＺＺＩ Ｒ， ＡＲＡＵＪＯ Ｒ． Ａ ｆａｓｔ ａｎｄ ｒｅｌｉａ⁃ ｂｌｅ ｐｒｏｔｏｃｏｌ ｆｏｒ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ｉｎ ｃｒｉｔｉｃａｌ ｃｏｎｄｉ⁃ ｔｉｏｎｓ ｍｏｎｉｔｏｒｉｎｇ ａｐｐｌｉｃａｔｉｏｎｓ［Ｃ］ ／ ／ ７ｔｈ ＡＣＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｍｏｄｅｌｉｎｇ， Ａｎａｌｙｓｉｓ ａｎｄ Ｓｉｍｕｌａｔｉｏｎ ｏｆ Ｗｉｒｅ⁃ ｌｅｓｓ ａｎｄ Ｍｏｂｉｌｅ Ｓｙｓｔｅｍｓ （ＭＳＷｉＭ）． Ｖｅｎｉｃｅ， Ｉｔａｌｙ， ２００４： １５７⁃１６４． ［１４］ＹＵ Ｚｕｏｍｉｎｇ， ＴＥＮＧ Ｊｉｎ， ＬＩ Ｘｉｎｆｅｎｇ． Ｏｎ ｗｉｒｅｌｅｓｓ ｎｅｔｗｏｒｋ ｃｏｖｅｒａｇｅ ｉｎ ｂｏｕｎｄｅｄ ａｒｅａｓ［ Ｃ］ ／ ／ ３２ｎｄ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ （ ＩＮＦＯＣＯＭ ）． Ｔｕｒｉｎ， Ｉｔａｌｙ， ２０１３： １７５２⁃１７６０． ［１５］ＡＲＥＹ Ｍ Ｒ， ＪＯＨＮＳＯＮ Ｄ Ｓ． Ｃｏｍｐｕｔｅｒｓ ａｎｄ ｉｎｔｒａｃｔａｂｉｌｉｔｙ： ａ ｇｕｉｄｅ ｔｏ ｔｈｅ ｔｈｅｏｒｙ ｏｆ ＮＰ⁃Ｃｏｍｐｌｅｔｅｎｅｓｓ［Ｍ］． Ｎｅｗ Ｙｏｒｋ： Ｗ．Ｈ．Ｆｒｅｅｍａｎ， １９７９： ２１０⁃２１６． ［１６］ＣＨＡＮＧ Ｊ Ｈ， ＴＡＳＳＩＵＬＡＳ Ｌ． Ｍａｘｉｍｕｍ ｌｉｆｅｔｉｍｅ ｒｏｕｔｉｎｇ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［ Ｊ］． ＩＥＥＥ／ ＡＣＭ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ 第 ４ 期 梁俊斌，等：带时延约束的连通目标覆盖最大化生命周期问题 ·３２５·