Title | ||
---|---|---|
Approximation algorithm for minimizing relay node placement in wireless sensor networks. |
Abstract | ||
---|---|---|
To eliminate the routing load unbalance among sensor nodes, one approach is to deploy a small number of powerful relay nodes
acting as routing nodes in wireless sensor networks, the major optimization objective of which is to minimize the number of
relay nodes required. In this paper, we prove that the relay node placement problem in a bounded plane is a P problem, but
its computational complexity in general case is quite great. From the geometric cover feature of the relay node placement
problem, an O(n
2 log n) time greedy approximation algorithm is proposed, where n is the number of sensor nodes. Particularly, at each stage of this algorithm’s iterative process, we first select a critical
node from uncovered sensor nodes, and then determine the location of relay node based on the principle of preferring to cover
the sensor node closer to the critical node, so as to prevent the emergence of isolated node. Experiment results indicate
that our proposed algorithm can generate a near optimum feasible relay node deployment in a very short time, and it outperforms
existing algorithms in terms of both the size of relay node deployment and the execution time. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1007/s11432-010-4092-8 | SCIENCE CHINA Information Sciences |
Keywords | Field | DocType |
SCHEMES | Sensor node,Relay channel,Approximation algorithm,Key distribution in wireless sensor networks,Mathematical optimization,Computer science,Computer network,Brooks–Iyengar algorithm,Greedy algorithm,Wireless sensor network,Relay | Journal |
Volume | Issue | ISSN |
53 | 11 | null |
Citations | PageRank | References |
2 | 0.37 | 11 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Kezhong Lu | 1 | 34 | 5.48 |
Chen Guoliang | 2 | 381 | 26.16 |
Yu-Hong Feng | 3 | 114 | 9.27 |
Guo Liu | 4 | 9 | 3.17 |
Rui Mao | 5 | 368 | 41.23 |