Abstract
Motivated by application to wireless sensor networks, we study the following problem. We are given a set S of wireless sensor nodes, given as a set of points in the two-dimensional plane, and real numbers 0 < r ≤ R. We must place a minimum-size set Q of wireless relay nodes in the two dimensional plane to connect S, where connectivity is explained formally next. The nodes of S can communicate to nodes within distance r, and the relay nodes of Q can communicate within distance R. Once the nodes of Q are placed, they together with S induce an undirected graph G = (V,E) defined as follows: V = S ∪ Q, and \(E = \{ uv | u,v \in Q \mbox{ and } ||u,v|| \leq R \} \cup \{ xu | x \in S \mbox{ and } u \in (Q \cup S) \mbox{ and } ||u,x|| \leq r\}\), where ||u,v|| denotes the Euclidean distance from u to v. G must be connected.
It was shown in [1] that an algorithm based on Minimum Spanning Tree achieves approximation ratio 7. We improve the analysis of this algorithm to 6, and propose a post-processing heuristic called Post-Order Greedy to practically improve the performance of the approximation algorithms. Experiments on random instances give Post-Order Greedy applied after Minimum Spanning Tree an average improvement of up to 23%. Applying Post-Order Greedy after an optimum Steiner Tree algorithm results in another circa 6% improvement considering the same instances.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Lloyd, E.L., Xue, G.: Relay node placement in wireless sensor networks. IEEE Transactions on Computers 56(1), 134–138 (2007)
Cheng, X., Du, D.Z., Wang, L., Xu, B.: Relay sensor placement in wireless sensor networks. ACM Wireless Networks (January 2007)
Lin, G., Xue, G.: Steiner tree problem with minimum number of steiner points and bounded edge-length. Information Processing Letters 69, 53–57 (1999)
Chen, D., Du, D.Z., Hu, X., Lin, G., Wang, L., Xu, G.: Approximation for steiner trees with minimum number of steiner points. Journal of Global Optimization 18, 17–33 (2000)
Măndoiu, I.I., Zelikovsky, A.Z.: A note on the mst heuristic for bounded edge-length steiner trees with minimum number of steiner points. Inf. Process. Lett. 75(4), 165–167 (2000)
Tang, J., Hao, B., Sen, A.: Relay node placement in large scale wireless sensor networks. Computer Communications 29, 490–501 (2006)
Liu, H., Wan, P.J., Jia, X.: Fault tolerant relay node placement in wireless sensor networks. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, Springer, Heidelberg (2005)
Wang, Q., Takahara, G., Hassanein, H., Xu, K.: On relay node placement and locally optimal traffic allocation in heterogeneous wireless sensor networks. In: IEEE Conference on Local Computer Networks (LCN 2005) (2005)
Wang, Q., Xu, K., Takahara, G., Hassanein, H.: Locally optimally relay node placement in heterogeneous wireless sensor networks. IEEE GlobeCom, 3549–3553 (2005)
Kashyap, A., Khuller, S., Shayman, M.: Relay placement for higher order connectivity in wireless sensor networks. In: INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, pp. 1–12 (April 2006)
Khuller, S., Raghavachari, B.: Improved approximation algorithms for uniform connectivity problems. Journal of Algorithms 21, 433–450 (1996)
Zhang, W., Xue, G., Misra, S.: Fault-tolerant relay node placement in wireless sensor networks: Problems and algorithms. In: INFOCOM 2007. 26th IEEE International Conference on Computer Communications. Proceedings, pp. 1649–1657 (May 2007)
Han, X., Cao, X., Lloyd, E., Shen, C.C.: Fault-tolerant relay node placement in heterogeneous wireless sensor networks. In: INFOCOM 2007. 26th IEEE International Conference on Computer Communications. Proceedings, pp. 1667–1675 (May 2007)
Zelikovsky, A.: An 11/6-approximation algorithm for the network Steiner problem. Algorithmica 9, 463–470 (1993)
Borchers, A., Du, D.Z.: The k-steiner ratio in graphs. SIAM Journal on Computing 26(3), 857–869 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Călinescu, G., Tongngam, S. (2008). Relay Nodes in Wireless Sensor Networks. In: Li, Y., Huynh, D.T., Das, S.K., Du, DZ. (eds) Wireless Algorithms, Systems, and Applications. WASA 2008. Lecture Notes in Computer Science, vol 5258. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-88582-5_28
Download citation
DOI: https://doi.org/10.1007/978-3-540-88582-5_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-88581-8
Online ISBN: 978-3-540-88582-5
eBook Packages: Computer ScienceComputer Science (R0)