Relay Node Placement in Wireless Sensor Networks
|
A wireless sensor network consists of many low-cost, low-power sensor nodes, which can perform sensing, simple computation, and transmission of sensed information. Long distance transmission by sensor nodes is not energy efficient since energy consumption is a superlinear function of the transmission distance. One approach to prolonging network lifetime while preserving network connectivity is to deploy a small number of costly, but more powerful, relay nodes whose main task is communication with other sensor or relay nodes. In this paper, we assume that sensor nodes have communication range r> 0, while relay nodes have communication range R\geq r, and we study two versions of relay node placement problems. In the first version, we want to deploy the minimum number of relay nodes so that, between each pair of sensor nodes, there is a connecting path consisting of relay and/or sensor nodes. In the second version, we want to deploy the minimum number of relay nodes so that, between each pair of sensor nodes, there is a connecting path consisting solely of relay nodes. We present a polynomial time 7-approximation algorithm for the first problem and a polynomial time (5 + \epsilon){\hbox{-}}\rm approximation algorithm for the second problem, where \epsilon> 0 can be any given constant.
[1] 134 I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless Sensor Networks: A Survey,” Computer Networks J., vol. 38, pp. 393-422, 2002.
[2] D. Chen, D.Z. Du, X.D. Hu, G. Lin, L. Wang, and G. Xue, “Approximations for Steiner Trees with Minimum Number of Steiner Points,” J. Global Optimization, vol. 18, pp. 17-33, 2000.
[3] X. Cheng, D.Z. Du, L. Wang, and B. Xu, “Relay Sensor Placement in Wireless Sensor Networks,” ACM/Springer J. Wireless Networks, to appear, http://www.seas.gwu.edu/~cheng/Publication relay.pdf.
[4] X. Cheng, B. Narahari, R. Simha, M.X. Cheng, and D. Liu, “Strong Minimum Energy Topology in Wireless Sensor Networks: NP-Completeness and Heuristics,” IEEE Trans. Mobile Computing, vol. 2, pp. 248-256, 2003.
[5] T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, second ed. MIT Press and McGraw-Hill, 2001.
[6] D. Estrin, R. Govindan, J. Heidemann, and S. Kumar, “Next Century Challenges: Scalable Coordination in Sensor Networks,” Proc. ACM MobiCom '99, pp. 263-270, 1999.
[7] R.J. Fowler, M.S. Paterson, and S.L. Tanimoto, “Optimal Packing and Covering in the Plane Are NP-Complete,” Information Processing Letters, vol. 12, pp. 133-137, 1981.
[8] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., 1979.
[9] B. Hao, J. Tang, and G. Xue, “Fault-Tolerant Relay Node Placement in Wireless Sensor Networks: Formulation and Approximation,” Proc. IEEE Workshop High Performance Switching and Routing (HPSR '04), pp. 246-250, 2004.
[10] Y.T. Hou, Y. Shi, and H.D. Sherali, “Rate Allocation in Wireless Sensor Networks with Network Lifetime Requirement,” Proc. ACM MobiHoc '04, pp. 67-77, 2004.
[11] B. Karp and H. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,” Proc. ACM MobiCom '00, pp. 243-254, 2000.
[12] D.S. Hochbaum and W. Maass, “Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI,” J. ACM, vol. 32, pp. 130-136, 1985.
[13] Q. Li, J. Aslam, and D. Rus, “Online Power-Aware Routing in Wireless Ad-Hoc Networks,” Proc. ACM MobiCom '01, pp. 97-107, 2001.
[14] G. Lin and G. Xue, “Steiner Tree Problem with Minimum Number of Steiner Points and Bounded Edge-Length,” Information Processing Letters, vol. 69, pp. 53-57, 1999.
[15] E. Lloyd, R. Liu, M. Marathe, R. Ramanathan, and S.S. Ravi, “Algorithmic Aspects of Topology Control Problems for Ad-Hoc Networks,” Proc. ACM MobiHoc '02, pp. 123-134, 2002.
[16] J. Pan, Y.T. Hou, L. Cai, Y. Shi, and S.X. Shen, “Topology Control for Wireless Sensor Networks,” Proc. ACM MobiCom '03, pp. 286-299, 2003.
[17] M.I. Shamos and D. Hoey, “Closest-Point Problems,” Proc. Ann. Symp. IEEE Foundation of Computer Science (FOCS '75), pp. 151-162, 1975.
[18] A. Srinivas and E. Modiano, “Minimum Energy Disjoint Path Routing in Wireless Ad-Hoc Networks,” Proc. ACM MobiCom '03, pp. 122-133, 2003.
[19] J. Tang, B. Hao, and A. Sen, “Relay Node Placement in Large Scale Wireless Sensor Networks,” Computer Comm., vol. 29, pp. 490-501, 2006.
Index Terms:
Relay node placement, wireless sensor networks, approximation algorithms.
Citation:
Errol L. Lloyd, Guoliang Xue, "Relay Node Placement in Wireless Sensor Networks," IEEE Transactions on Computers, vol. 56, no. 1, pp. 134-138, Jan. 2007, doi:10.1109/TC.2007.18
PURCHASE ARTICLE: $19
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb