Abstract
Data gathering is a fundamental operation in wireless sensor networks in which data packets generated at sensor nodes are to be collected at a base station. In this paper we suppose that each sensor is equipped with an half–duplex interface; hence, a node cannot receive and transmit at the same time. Moreover, each node is equipped with omnidirectional antennas allowing the transmission over distance R. The network is a multi-hop wireless network and the time is slotted so that one–hop transmission of one data item consumes one time slot. We model the network with a graph where the vertices represent the nodes and two nodes are connected if they are in the transmission/interference range of each other. Due to interferences a collision happens at a node if two or more of its neighbors try to transmit at the same time. Furthermore we suppose that an intermediate node should forward a message as soon as it receives it. We give an optimal collision free gathering schedule for tree networks whenever each node has at least one data packet to send.
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
Bermond, J.-C., Corrêa, R., Yu, M.: Gathering algorithms on paths under interference constraints. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds.) CIAC 2006. LNCS, vol. 3998, pp. 115–126. Springer, Heidelberg (2006)
Bermond, J.-C., Gargano, L., Rescigno, A.: Gathering with Minimum Delay in Sensor Networks, INRIA TR (2008), http://hal.inria.fr/inria-00256896/fr/
Bermond, J.-C., Galtier, J., Klasing, R., Morales, N., Pérennes, S.: Hardness and approximation of gathering in static radio networks. Parallel Processing Letters 16(2), 165–183 (2006)
Bermond, J.-C., Peters, J.: Efficient gathering in radio grids with interference. In: AlgoTel 2005, pp. 103–106, Presqu’île de Giens (2005)
Bermond, J.-C., Yu, M.: Optimal gathering algorithms in multi-hop radio tree-networks with interferences (manuscript, 2008)
Bertin, P., Bresse, J.-F., Le Sage, B.: Accès haut débit en zone rurale: une solution ”ad hoc”. France Telecom R&D 22, 16–18 (2005)
Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., Stougie, L.: An Approximation Algorithm for the Wireless Gathering Problem. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol. 4059. Springer, Heidelberg (2006)
Chong, C.-Y., Kumar, S.P.: Sensor networks: Evolution, opportunities, and challenges. Proc. of the IEEE 91(8), 1247–1256 (2003)
Coleri, S., Varaiya, P.: Energy Efficient Routing with Delay Guarantee for Sensor Networks. Wireless Networks (to appear)
Dasgupta, K., Kukreja, M., Kalpakis, K.: Topology-aware placement and role assignment for energy-efficient information gathering in sensor networks. In: Proc. IEEE ISCC 2003, pp. 341–348 (2003)
Falck, E., Floreen, P., Kaski, P., Kohonen, J., Orponen, J.P.: Balanced data gathering in Energy-constrained sensor networks. In: Nikoletseas, S.E., Rolim, J.D.P. (eds.) ALGOSENSORS 2004. LNCS, vol. 3121, pp. 59–70. Springer, Heidelberg (2004)
Florens, C., Franceschetti, M., McEliece, R.J.: Lower Bounds on Data Collection Time in Sensory Networks. IEEE J. on Sel. Ar. in Com. 22(6), 1110–1120 (2004)
Ganesan, D., Cristescu, R., Beferull-Lozano, B.: Power-efficient sensor placement and transmission structure for data gathering under distortion constraints. In: IPSN 2004, pp. 142–150 (2004)
Gargano, L.: Time Optimal Gathering in Sensor Networks. In: Prencipe, G., Zaks, S. (eds.) SIROCCO 2007. LNCS, vol. 4474, pp. 7–10. Springer, Heidelberg (2007)
Gargano, L., Rescigno, A.A.: Optimally Fast Data Gathering in Sensor Networks. In: Královič, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 399–411. Springer, Heidelberg (2006)
Gupta, H., Navda, V., Das, S.R., Chowdhary, V.: Efficient gathering of correlated data in sensor networks. In: Proc. of ACM MobiHoc 2005, pp. 402–413 (2005)
Gasieniec, L., Potapov, I.: Gossiping with Unit Messages in Known Radio Networks. In: IFIP TCS 2002, pp. 193–205 (2002)
Ho, B., Prasanna, V.K.: Constrained flow optimization with application to data gathering in sensor networks. In: Nikoletseas, S.E., Rolim, J.D.P. (eds.) ALGOSENSORS 2004. LNCS, vol. 3121, pp. 187–200. Springer, Heidelberg (2004)
Intanagonwiwat, C., Govindan, R., Estrin, D., Heidemann, J., Silva, F.: Directed diffusion for wireless sensor networking. IEEE/ACM Trans. Netw. 11(1), 2–16 (2003)
Krishnamachari, B., Estrin, D., Wicker, S.: Modeling data-centric routing in wireless sensor networks. In: Proc. of IEEE INFOCOM (2002)
Lindsey, S., Raghavendra, C.: Pegasis: Power-efficient gathering in sensor wireless networks. In: Proc. of IEEE Aerospace Conference (2002)
Lindsey, S., Raghavendra, C., Sivalingam, K.M.: Data gathering algorithms in sensor networks using energy metrics. IEEE Trans. on Par. and Distr. Sys. 13(9), 924–935 (2002)
Padmanabh, K., Roy, R.: Multicommodoty flow fased maximum lifetime routing in wireless sensor network. In: Proc. of IEEE ICPADS 2006, pp. 187–194 (2006)
Shen, C., Srisathapornphat, C., Jaikaeo, C.: Sensor information networking architecture and applications. IEEE Personal Communications, 52–59 (2001)
Yu, Y., Krishnamachari, B., Prasanna, V.: Energy-latency tradeoffs for data gathering in wireless sensor networks. In: Proc. of IEEE INFOCOM 2004 (2004)
Zhu, X., Tang, B., Gupta, H.: Delay efficient data gathering in sensor networks. In: Jia, X., Wu, J., He, Y. (eds.) MSN 2005. LNCS, vol. 3794, pp. 380–389. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bermond, JC., Gargano, L., Rescigno, A.A. (2008). Gathering with Minimum Delay in Tree Sensor Networks. In: Shvartsman, A.A., Felber, P. (eds) Structural Information and Communication Complexity. SIROCCO 2008. Lecture Notes in Computer Science, vol 5058. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69355-0_22
Download citation
DOI: https://doi.org/10.1007/978-3-540-69355-0_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69326-0
Online ISBN: 978-3-540-69355-0
eBook Packages: Computer ScienceComputer Science (R0)