Linear Time Approximation Algorithms for the Relay Node Placement Problem in Wireless Sensor Networks with Hexagon Tessellation
Joint Authors
Chang, Chi-Yu
Chen, Po-Ying
Chen, Chi-Chang
Source
Issue
Vol. 2015, Issue 2015 (31 Dec. 2015), pp.1-12, 12 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2015-05-03
Country of Publication
Egypt
No. of Pages
12
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Chen, Chi-Chang& Chang, Chi-Yu& Chen, Po-Ying. 2015. Linear Time Approximation Algorithms for the Relay Node Placement Problem in Wireless Sensor Networks with Hexagon Tessellation. Journal of Sensors،Vol. 2015, no. 2015, pp.1-12.
https://search.emarefa.net/detail/BIM-1070153
Modern Language Association (MLA)
Chen, Chi-Chang…[et al.]. Linear Time Approximation Algorithms for the Relay Node Placement Problem in Wireless Sensor Networks with Hexagon Tessellation. Journal of Sensors No. 2015 (2015), pp.1-12.
https://search.emarefa.net/detail/BIM-1070153
American Medical Association (AMA)
Chen, Chi-Chang& Chang, Chi-Yu& Chen, Po-Ying. Linear Time Approximation Algorithms for the Relay Node Placement Problem in Wireless Sensor Networks with Hexagon Tessellation. Journal of Sensors. 2015. Vol. 2015, no. 2015, pp.1-12.
https://search.emarefa.net/detail/BIM-1070153
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1070153