Linear Time Approximation Algorithms for the Relay Node Placement Problem in Wireless Sensor Networks with Hexagon Tessellation

NCUTIR > College of Electrical Engineering and Computer Science > Department of Electronic Engineering > 【電子工程系所】期刊論文 > Item 987654321/5891

Please use this identifier to cite or link to this item: http://ir.lib.ncut.edu.tw/handle/987654321/5891

Title:	Linear Time Approximation Algorithms for the Relay Node Placement Problem in Wireless Sensor Networks with Hexagon Tessellation
Authors:	Chi-Chang Chen, Chi-Yu Chang, and Po-Ying Chen
Contributors:	圖書館
Date:	2015
Issue Date:	2016-10-17 10:47:55 (UTC+8)
Abstract:	The relay node placement problem in wireless sensor network (WSN) aims at deploying the minimum number of relay nodes over the network so that each sensor can communicate with at least one relay node. When the deployed relay nodes are homogeneous and their communication ranges are circular, one way to solve the WSN relay node placement problem is to solve the minimum geometric disk cover (MGDC) problem first and place the relay nodes at the centers of the covering disks and then, if necessary, deploy additional relay nodes to meet the connection requirement of relay nodes. It is known that the MGDC problem is NP-complete. A novel linear time approximation algorithm for the MGDC problem is proposed, which identifies covering disks using the regular hexagon tessellation of the plane with bounded area. The approximation ratio of the proposed algorithm is (5+ε), where 0<ε≦15 . Experimental results show that the worst case is rare, and on average the proposed algorithm uses less than 1.7 times the optimal disks of the MGDC problem. In cases where quick deployment is necessary, this study provides a fast 7-approximation algorithm which uses on average less than twice the optimal number of relay nodes in the simulation.
Relation:	Journal of Sensors Volume 2015, Article ID 565983, 12 pages
Appears in Collections:	[Department of Electronic Engineering] 【電子工程系所】期刊論文

Files in This Item:

File	Description	Size	Format
Linear Time Approximation Algorithms for the Relay Node Placement Problem in Wireless Sensor Networks with Hexagon Tessellation.pdf		1828Kb	Adobe PDF	1622	View/Open

View Licence

Loading...