双层无线传感网络的3连通近似算法

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (13): 95-97.

双层无线传感网络的3连通近似算法

陈光亭，李茹雪，丁蔚

杭州电子科技大学运筹与控制研究所，杭州 310018

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-05-01 发布日期:2011-05-01

Approximation algorithm for 3-connectivity in wireless sensor networks

CHEN Guangting，LI Ruxue，DING Wei

Institute of Operations Research and Control Sciences，Hangzhou Dianzi University，Hangzhou 310018，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-05-01 Published:2011-05-01

摘要/Abstract

摘要： 主要研究双层无线传感网络模型，即数据信息流只能在传感器和中继器或中继器和中继器之间传输，而不能在传感器之间传输。近似算法基于两个子问题：k圆盘覆盖问题和单层传感网络的k连通问题，而后在部分中继器周围设置“等六边形”结构的中继器点，最终达到整个网络的3-连通水平。该算法的最终性能比为8α+β，其中α为k圆盘覆盖近似算法的性能比，β为单层传感网络的k连通近似算法的性能比。

关键词: 3连通, 圆盘覆盖, 双层无线传感网络, 中继器, 传感器

Abstract: The two-tiered wireless sensor network is a network that data can only be transmitted between relay nodes or sensor nodes and relay nodes，and there is no data stream between sensor nodes.An approximation algorithm is proposed based on two foundational works：The k-disk cover problem and the single-tiered 3-connectivity relay node placement problem，with a special structure，called “hexagon”，to keep 3-connectivity for the network.The performance ratio is 8α+β，where α is the performance ratio of approximation algorithm for the k-disk cover problem，and β is the performance ratio of approximation algorithm for the single-tiered 3-connectivity relay node placement problem.

Key words: 3-connectivity, disk-cover, two-tier Wireless Sensor Network（WSN）, relay node, sensor node

陈光亭，李茹雪，丁蔚. 双层无线传感网络的3连通近似算法[J]. 计算机工程与应用, 2011, 47(13): 95-97.

CHEN Guangting，LI Ruxue，DING Wei. Approximation algorithm for 3-connectivity in wireless sensor networks[J]. Computer Engineering and Applications, 2011, 47(13): 95-97.

[1]	成怡，郝密密. 改进深度强化学习的室内移动机器人路径规划[J]. 计算机工程与应用, 2021, 57(21): 256-262.
[2]	王一凡，鲁慧民，高若然，李阳. 手指静脉图像感兴趣区域提取研究综述[J]. 计算机工程与应用, 2021, 57(13): 34-42.
[3]	巩俊辉，胡晓辉，杜永文. 基于演化博弈的最优防御策略选取研究[J]. 计算机工程与应用, 2021, 57(13): 116-123.
[4]	孙泽宇，董汉磊，苏艳超，徐琛，聂雅琳，李传锋. 传感网中基于能量有效的多参数数据重构方法[J]. 计算机工程与应用, 2021, 57(11): 103-110.
[5]	龚本灿，周峰，陈鹏，任东. 基于路径质量的无线传感网路由协议[J]. 计算机工程与应用, 2020, 56(6): 99-104.
[6]	彭春燕，杜秀娟. 水声传感器网络基于深度信息的安全路由协议[J]. 计算机工程与应用, 2020, 56(2): 76-81.
[7]	刘明芹，张晓光，徐桂云，李宗周. 单机器人SLAM技术的发展及相关主流技术综述[J]. 计算机工程与应用, 2020, 56(18): 25-35.
[8]	郑祖朋，汪祖民，彭杨，季长清，秦静. 能量采集传感器网络中MAC协议研究综述[J]. 计算机工程与应用, 2020, 56(15): 24-29.
[9]	刘安睿劼，王耀力. 基于轮式机器人的实时3D栅格地图构建[J]. 计算机工程与应用, 2020, 56(13): 164-171.
[10]	韩雨涝. 非并行二分法的覆盖空洞修复算法[J]. 计算机工程与应用, 2020, 56(12): 87-92.
[11]	杨飞跃，陶洋. 时空协作的WSNs节点异常检测算法[J]. 计算机工程与应用, 2019, 55(7): 127-131.
[12]	朱瑞金，龚雪娇，唐波. 分布式混合压缩感知无线传感器网络数据收集[J]. 计算机工程与应用, 2019, 55(6): 73-80.
[13]	吴会会1，高淑萍1，彭弘铭2，赵怡1. 自适应模糊[C]均值聚类的数据融合算法[J]. 计算机工程与应用, 2019, 55(5): 26-35.
[14]	郑朝鑫1，2，董晨1，3，贺国荣1，3，陈荣忠1，3，熊子奇1，3. 基于改进粒子群算法的动态3D实时建模技术[J]. 计算机工程与应用, 2019, 55(5): 65-71.
[15]	乔冉，闫江毓，唐良瑞. 基于多维高斯的无线传感器网络定位算法[J]. 计算机工程与应用, 2019, 55(23): 99-104.