论文研究-基于网格的分布式能量有效无线传感器网络.pdf

所需积分/C币:10 2019-07-22 21:24:08 665KB .PDF
收藏 收藏
举报

网络的覆盖和连通性是无线传感器网络(WSN)的基本问题。为了组建一个健壮网络,并解决现有算法在传感器节点的通信半径小于两倍感知半径情况下不能实现分布式运行的问题,提出一种基于网格的分布式k覆盖多连通节点部署算法。该算法将监控区域划分为网格,各网格根据节点的剩余能量和覆盖贡献度等计算出优先级,各网格分布地使用贪婪算法迭代地选择优先级高的节点转为活跃状态直到网格达到k覆盖,整个网络达到多连通。理论分析表明,该分布式算法能够组建一个k覆盖多连通的能量有效利用的无线传感器网络。
2468 计算机应用研究 第31卷 格(边界网格至少有两个邻居网格),所以,步骤a)结束时基本盖度和连通性的要求下,考虑了节点对网终覆盖贡献度,从而 所有网格都至少有两个节点转为活跃状态,步骤a)b)主要是减少了活跃状态节点数目。 步骤a)花费时间,为0(A2) 算法步骤c)d)中各网格是分布执行的,主要为计算节点 1.6 的覆盖贞献度,吋间复杂度为O(N)。 本算法的时间复杂度为O(N2) 08 2.2.2连通性分析 06 0.4 定义5重连通图3。在图G中,若朋除顶点v以及相 2 本文算法鲁CCn 0 关的边后,图G的一个连通分量分割为两个或两个以上的连 覆盖度 通分量,则称顶点为该图的个关节点。个没有关节点的 囹2不同覆盖度本文算法与CCP算法活跃节点数对比 连通图称为重连通图。 图3是本文算法在不同通信半径下各覆盖度下的活跃节 在重连通图中,任意一对顶点之间至少存在两条路径即点数目。由图3可知通信半径相同时,覆盖度越高活跃状态 删去某个顶点及其相关各边后也不破坏图的迕通性 数越多;相同的覆盖度,随着通信半径的增大,活臥状态的 定理1在两个重连通图G1和C2的两对不同顶点间加节点数减少。这说明通信半径变大时,为了满足连通性转为 上边,形成的图G3仍然是重连通图。如图1所示,图G和G2活跃状态的节点数变少;覆盖度越大,曲线变化趋势越小。这 均为重连通图,在分别属于G1和G2的两对节点对〈3,5〉〈4,说明覆盖度较大时,活跃节点数越多,当通信半径变小时,为了 8)之间加上边后组成的图G仍为重连通图。 保证连通性而增加的活跃节点数越少。 图4为不同覆盖度时本文算法和CCP算法网络寿命的对 比。图4中本文算法在不同覆盖度下,网络寿命长于CCP算 法,并且覆盖度越高,网络的寿命越短。 图1重连通图 证明图G1=(V,E)和G2=(V,E)都为重连通图,G 不文算法CCP 和G2之同不同的两对顶点间添加边。不失一般性,假设1 08 80 a2∈V,b1,b2=V,添加两条边(a1,b1)和〈a2,b2)后形成图G3。 04 40 假设G3不是重连通图,根据重连通图定义,那么G2必然02 =2-h=3+k=4一%=5 20 存在关节点。由于G1和G2为重连通图,所以G3的关节点只 253035404550 覆盖度 会出现在a1、a2、b1、b2中。若a1、b1中一个顶点及其相关边被 图3不同通信半径对 图4不同覆盖度 删除,C1和G2之间可以由边〈a2,b2)连通,G3仍为连通图,所 活节点数的影响 焖络寿命对比 以a1、b1不是关节点。同理,若a2、b2中一个顶点被删除,G1 和G之问可以由边〈a1,b)连通,a,、b,也不是关节点。所以4结束语 G3不存在关节点,与假设矛盾。所以G3为重连通图 本文针对无线传感器网络在随札高密度部署且传感器节 本算法中,以活跃状态节点为顶点,通信范围内的节点之点的通信半径小于两倍感知半径情况下,提出种基于网格的 间都存在一条边所形成的图。由于同一树格中的节点都可相分布式k覆盖多连通节点部署算法。仿真实验表明,本文算法 连通,所以每个网格可以看成是个重连通图。每个网格与在保证网络的覆盖度和连通性的同时,能有效减少活跃状态的 邻居网格至少有两条不同的边。所以,整个网络中活跃节点组节点数目、延长网络的寿命。理论分析表明,本文算法部署的 成的图为重连通图.即任意两个节点之间至少冇在两条路径。网络节点达到多连通。 所以网终达到多连通。 参考文献 3实验仿真 [Il]毛莺池,梁奕,周晓峰,一种能量异构自适应的无线传感器网络覆 盖控制协议[J].计算机科学,2009),36(5):39. 为了验证本文算法的性能,本文将在 MATLAB7.0上对算[2 XING G, WANG X, ZHANG Y,eal. Integrated coverage and conned 法进行仿真就不同覆盖度下活跃状态节点数和CCP算法进 tivity configuration for energy conservation in sensor networks 行比较、不同连通半径对活跃节点数目的影响、CCP算法对 ACM Trans on Sensor Networks, 2005, 1(1): 36-72 比不同覆盖度下的网络寿命。仿真环境是一个400m×400m131 XING Xiao-fei, WANG Guo-jun, WU Jie,etal. lare region-ard 的正方形区域,区域中随机播撒2000个节点,感知半径为 coverage and connectivity probability model in wireless sensor net works[ C]//Proc of the 5th International Conference on Collaborative =25)m 图2为不同的覆盖度下活跃状态节点数与CCP算法的对 Computing. Washington DC: IEEE Computer Society, 2009 比,节点的通信半径设定为R=40m。随着网络覆盖度的提 [4 YUN L.i-qill, BAI Xiat-le, XUAN Dony, et uL. Pallern mul:alion in wireless sensor deployment[ J|. IEEE/ ACM Trans on Networking 高,网络中活跃节点数明显增加。通过与CCP协议的对比可 以看出,使用本文算法的网络中处于活跃状态的节点数目明显[5]YuML, MAMOULIS N. Aggrcgatc ncarcst neighbor qucrics in road 比使用CCP协议的网络活跃节点的数目少。覆盖度为3时, networks[ J]. IEEE Trans on Knowledge and Data Engineering 两种算法下活跃节点数量相差不大,随着覆盖度的提高,两老 005,17(6):820-833 的活跃节点数目差距变大。这说明本文算法在保证网络的覆 (下转第2472页) 2472 计算机应用研究 第31卷 的接过程仅与能量消耗有关,而与现有的能量存储无关。能力有限。然而,最大化网络ERR算法在所有的情况下均表 与之形成对比,最人化网终ERR算法使得网络中各HeNB现出更优越的性能.因为该算法保证了HeNB之间的公平性, 的EDR相差不大,且相对较小。尤其需要注意的是,在最小从而充分利用了所有HeNB的能量存储。 化最大EDR方面,最大化网络ERR算法相比基于贪婪算法 的方法,有高达50%的性能优化。总之,文中提出的算法不4结束语 仪降低了每个HNB的ED,而且保证了HeNB之间的公 平性。 本文首先将能量供应持续性问题建模为一个网络范围内 算法在 Femtocell /E存时间上的性能比较如图3所示。从的优化问题并同时考虑D的性能和公半性。提出了最大 化网络ER算法以解决这个优化问题,该算法结合了物埋层 图中可以推断,在开始阶段,总用户数并不是很人,这时最人化的 网络ERR算法在很大程度上可以扩展和稳定网络的生存时 的功率分配技术和MMC层的接人控制技术。仿真结果表明文 中所提算法在改善网络牛存时间以及提高山可再生能源供能 问。另外,由于 Femtocell阃络的生存时问由HeNB中最大的 FDR决定,最大化网络FRR算法在这个阶段可以达到的网络的用户数方面都具有优越的性能。 生存时间比基于贪婪算法的方法多出大于半个小时的时间。参考文献 当总用户数超过300时,两种算法的生存时间的性能都很差,[1] HAN Cong-zheng, HARROLD T, ARMOUR S,eml. Green radio 这是因为HeNB的能量存储能力有限,而非EDR之间的不公 radio techniques to enable energy efficient wireless networks [ 1] 平性。 IEEE Communications Magazine Special Issue on Green Ra dio Communications, 2010, 49(6): 46-55 0.9 4a于算法的方法要25中“学 最大亿网终ERR算法 [2宋杰,李甜甜,闫振兴,等.一种云计算环境下的能效模型和度量 方法[J].软件学报,2012,23(2):200-214 0.6 ,少,,c [3ˉ张法, ANTA A F,王林,等、网络能量系统模型及能效算法[J] 1 计算机学报,212,22(3):603-615. 0.2 皇0.5最大化络ER算法 基于贪婪算的方 [4 MCLAUGHLIN S, GRANT PM, THOMPSON JS, et al. Techniques 2468ll214161820 050100150200250300350 总用户数 for improving ccllular radio basc station cncrgy cfficicncy[ J].IEEE HeNB标号 图2EDR比较(K=20,M=80) 图3生存时向的比较 Communications Magazine, 2011, 18(5): 10-17 [5宋杰,侯泓颖,王智,等.云计算环境下改进的能效度量模型[J] 1f-0-.00.0-a-: 0.9 浙江大学学报:工学版,2013,47(1):44-52. 壬0.8 [6甘已斌,曾灿,李开,等.电子商务下的信任网络构造与优化[J] 计算机学报,2012,35(1):27-37 04 [7ˉ谢和平,同海鹰,左德承,等.无线传感器网络能量优亿与建模技 术综述[J].计算机科学,2012,39(10):15-20 5C100150200250300350 「8]查肇祥,张金芑,刘捷,等.LR- WPAN Mesh网络双能效优化设 总用户数 计[冂].计算机工程,2013,39(4):123-127 图4用户数的比较 [9] HAN Tao, ANSARI N. ICE: intelligent ccll BrEathing to optimize 图4显示了两种算法在接入到由可再生能源供能的 the utilization of green energy[ J]. IEEE Communications Letters HeNB用广数方面的性能。随着总用户薮的增加,网络中的 2012,16(6):866-869 HeNB将不能服务所有的用户,此时未被服务的用户就会接入[10 I CHEN HoII-chun, FU Huai-Iei,INP,mm. energy- Aware irans 到由格点能量供能的宏基站。两种算法下,由可再生能源供能 mission scheduling in mobile sensor networks C]//Proc of IEEE 的用户比例具有相似的向下趋热,这是因为HeNB的能量存储 Global telecuunicalions conference 2011. 1-5 (上接第2468页) [6 CARDEIM, WU J. Energy-efficient coverage problems in wireless Ad Proc of Military Communications Conference. 2006: 23-25 hoc sensor networks[ J]. Journal of Computer Communications [11 TIAN D, GEORGANAS N D. A coverage-preserving node scheduling on Sensor Networks, 2006, 29(4): 413-420 scheme for large wireless sensor network[ C]//Proc of the 1st ACM [7] ANTHONY S, YE Y. On solving coverage problems in a wireless sen- Workshop on Wireless Sensor Networks and Applications. 2002: 32 sor network using voronoi diagrams C]//Proc of the lst Work Shop on Internet and Network Economics. 2005. 584-593 [12] ZHANG H, HOU J C. Maintaining sensing coverage and connectivity [8 WANG X, XING G, ZHANG Y, et al. Intcgratcd coverage and con- in largc sensor nctworks[ J]. Ad Hoc Wireless Sensor Network nectivity configuration in wireless sensor networks[ C]//Proc of the 2005,1(1-2):89-124 Isl ACM Inlernalional Cainferenr'e on Emberded Nel worked Sensor [13 SANTOSH K, TEN H L. On h-tveraye in d mostly sleeping sensor Systcms.2003:28-39. nctwork[J]. Wireless Networks, 2008, 14(3): 277-294 [9]闰中江,沈中,常义林,等.非迮通无线传感器网络的最少传感器[14] LIU Zheng, ZHAO Wei-guo, WANG Jing,eta. Energy conserving 节点部北京署[J.北京邙电大学学报,2011,34(5):15-18。 based k-coverage algorith de ireless sensor networks JI I 10] VUCT, GAO S, DESHMLKH W P, et al. Distributed energy-efficient Electrical Review, 2012(1): 74-78 scheduling approach for k- coverage in wireless sensor networks[C]∥[15]杨洪.因论常用算法选鏑[M].北京:中国铁路出版社,1988

...展开详情
试读 4P 论文研究-基于网格的分布式能量有效无线传感器网络.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    img
    • 至尊王者

      成功上传501个资源即可获取

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    论文研究-基于网格的分布式能量有效无线传感器网络.pdf 10积分/C币 立即下载
    1/4
    论文研究-基于网格的分布式能量有效无线传感器网络.pdf第1页
    论文研究-基于网格的分布式能量有效无线传感器网络.pdf第2页

    试读已结束,剩余2页未读...

    10积分/C币 立即下载 >