Abstract
Given a set of sensors, the strong minimum energy topology (SMET) problem is to assign transmit power to each sensor such that the resulting topology containing only bidirectional links is strongly connected and the total energy of all the nodes is minimized. The SMET problem is known to be NP-hard. Currently available sensors in the market support a finite set of transmission ranges. So we consider the k-Distinct-SMET problem, where only k transmission power levels are used. We prove that the k-Distinct-SMET problem is NP-complete for k ≥ 3. However, on the positive side, we show that the 2-Distinct-SMET problem can be solved in polynomial time. The energy cost of transmitting a bit is higher than the cost of computation, and hence it may be advantageous to organize the sensors into clusters and form a hierarchical structure. This motivated the study of k -Distinct- r Strong Minimum Energy Hierarchical Topology ( k -Distinct- r SMEHT) problem: Given a sensor network consisting of n sensors, and integers k and r, assign transmit powers to all sensors out of the k distinct power levels such that (i) the graph induced using only the bi-directional links is connected, (ii) at most r sensors are connected to two or more sensors by a bidirectional link and (iii) the sum of the transmit powers of all the sensors is minimum. We Propose a \(\frac{r+1}{2}\)- approximation algorithm for the k-Distinct-rSMEHT problem for any fixed r and arbitrary k.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Aneja, Y.P., Bari, A., Jaekel, A., Chandrasekaran, R., Nair, K.P.K.: Minimum energy strong bidirectional topology for ad hoc wireless sensor networks. In: IEEE International Conference on Communications, ICC 2009, pp. 1–5. IEEE (2009)
Carmi, P., Katz, M.J.: Power assignment in radio networks with two power levels. Algorithmica 47(2), 183–201 (2007)
Cheng, X., Narahari, B., Simha, R., Cheng, M.X., Liu, D.: Strong minimum energy topology in wireless sensor networks: Np-completeness and heuristics. IEEE Transactions on Mobile Computing 2(3), 248–256 (2003)
Fuchs, B.: On the hardness of range assignment problems. Networks 52(4), 183–195 (2008)
Panda, B.S., Pushparaj Shetty, D.: An incremental power greedy heuristic for strong minimum energy topology in wireless sensor networks. In: Natarajan, R., Ojo, A. (eds.) ICDCIT 2011. LNCS, vol. 6536, pp. 187–196. Springer, Heidelberg (2011)
Panda, B.S., Pushparaj Shetty, D.: A local search based approximation algorithm for strong minimum energy topology problem in wireless sensor networks. In: Hota, C., Srimani, P.K. (eds.) ICDCIT 2013. LNCS, vol. 7753, pp. 398–409. Springer, Heidelberg (2013)
Panda, B.S., Pushparaj Shetty, D.: Strong minimum energy 2-hop rooted topology for hierarchical wireless sensor networks. Journal of Combinatorial Optimization, 1–18 (2013), http://dx.doi.org/10.1007/s10878-013-9683-z
Santi, P.: Topology Control in Wireless Ad Hoc and Sensor Networks. John Wiley & Sons Ltd (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Panda, B.S., Shetty, D.P., Pandey, A. (2015). k-Distinct Strong Minimum Energy Topology Problem in Wireless Sensor Networks. In: Natarajan, R., Barua, G., Patra, M.R. (eds) Distributed Computing and Internet Technology. ICDCIT 2015. Lecture Notes in Computer Science, vol 8956. Springer, Cham. https://doi.org/10.1007/978-3-319-14977-6_13
Download citation
DOI: https://doi.org/10.1007/978-3-319-14977-6_13
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-14976-9
Online ISBN: 978-3-319-14977-6
eBook Packages: Computer ScienceComputer Science (R0)