| 双层无线传感网络的3连通近似算法 |
| |
| 引用本文： | 陈光亭,李茹雪,丁蔚.双层无线传感网络的3连通近似算法[J].计算机工程与应用,2011,47(13):95-97. |
| |
| 作者姓名： | 陈光亭 李茹雪 丁蔚 |
| |
| 作者单位： | 杭州电子科技大学,运筹与控制研究所,杭州,310018 |
| |
| 摘 要： | 主要研究双层无线传感网络模型，即数据信息流只能在传感器和中继器或中继器和中继器之间传输，而不能在传感器之间传输。近似算法基于两个子问题：k圆盘覆盖问题和单层传感网络的k连通问题，而后在部分中继器周围设置“等六边形”结构的中继器点，最终达到整个网络的3-连通水平。该算法的最终性能比为8α+β，其中α为k圆盘覆盖近似算法的性能比，β为单层传感网络的k连通近似算法的性能比。
|
| 关 键 词： | 3连通 圆盘覆盖 双层无线传感网络 中继器 传感器 |
| 修稿时间： | |
Approximation algorithm for 3-connectivity in wireless sensor networks |
| |
| 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. |
| |
| Authors: | CHEN Guangting LI Ruxue DING Wei |
| |
| Affiliation: | Institute of Operations Research and Control Sciences,Hangzhou Dianzi University,Hangzhou 310018,China |
| |
| Abstract: | The two-tiered wireless sensor network is a network that data can only be transmitted between relay nodes or sen-sor nodes and relay nodes,and there is no data stream between sensor nodes.An approximation algorithm is proposed basedon two foundational works：The k-disk cover problem and the single-tiered 3-connectivity relay node placement problem,witha special structure,called＂hexagon＂,to keep 3-connectivity for the network.The performance ratio is 8α＋β,where α is theperformance ratio of approximation algorithm for the k-disk cover problem,and β is the performance ratio of approximationalgorithm for the single-tiered 3-connectivity relay node placement problem |
| |
| Keywords: | 3-connectivity disk-cover two-tier Wireless Sensor Network（WSN） relay node sensor node |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
