Abstract
We consider the broadcasting problem in sensor networks where the nodes have no prior knowledge of their neighborhood. That is, to preserve power and bandwidth, no beacons or ’hello’ messages are sent. We describe several Area based Beaconless Broadcasting Algorithms (ABBAs). In 2D, upon receiving the packet, each node calculates the ratio P of its perimeter, along the circle of transmission radius, that is not covered by this and previous transmissions of the same packet. The node then sets or updates its timeout to be inversely proportional to P. We also consider an alternative random timeout function. If the perimeter becomes fully covered, the node cancels retransmissions. The protocol is reliable, assuming an ideal MAC layer. We also describe three 3D ABBAs, one of them being reliable, each with two choices of timeouts.These three protocols are based on covering three projections, covering particular points on intersection circles, and covering intersection points of three spheres. Our protocols are the first reliable broadcasting protocols, other than blind flooding. We compare 2D ABBAs with two other existing beaconless protocols, BPS and Geoflood, showing its superiority. We also consider a MAC layer with collisions and show that all of our methods still remain very robust, showing high delivery ratio during the broadcast.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arango, J., Degermark, M., Efrat, A., Pink, S.: An Efficient Flooding Algorithm for Ad-hoc Networks. In: Proceedings of the 2nd Workshop on Modeling and Optimizations in Mobile Ad Hoc and Wireless Networks (WiOpt 2004) (March 2004)
Bergonovo, F., Capone, A., Cesana, M., Fratta, L., Coletti, L., Moretti, L., Riato, N.: Inter-vehicles communication: A new frontier of ad hoc networking. In: Proc. Medhoc, Tunisia (June 2003)
Durresi, A., Paruchuri, V.K., Iyengar, S.S., Kannan, R.: Optimized Broadcast Protocol for Sensor Networks. IEEE transactions on Computers 54(8) (August 2005)
Heissenttel, M., Braun, T., Wlchli, M., Bernoulli, T.: Broadcasting in Wireless Multihop Networks with the Dynamic Forwarding Delay Concept, Technical Report, IAM-04-010, University of Bern, Switzerland (December 2004)
Heissenbuttel, M., Braun, T., Wlchli, M., Bernoulli, T.: Optimized Stateless Broadcasting in Wireless Multi-hop Networks. In: IEEE Infocom (Infocom 2006), Barcelona, Spain, April 23–29 (2006)
Ingelrest, F., Simplot-Ryl, D., Stojmenovic, I.: Energy-efficient broadcasting in wireless mobile ad hoc networks. In: Cardei, M., Cardei, I., Du, D.-Z. (eds.) Resource Management in Wireless Networking, pp. 543–582. Springer, Heidelberg (2005)
Kim, D., Maxemchuk, N.F.: A comparison of flooding and random routing in mobile ad hoc network. In: 3rd New York Metro Area Networking Workshop (September 2003)
Li, X.Y., Stojmenovic, I.: Broadcasting and topology control in wireless ad hoc networks. In: Boukerche, A. (ed.) Handbook of Algorithms for Wireless Networking and Mobile Computing, ch. 11, pp. 239–264. Chapman & Hall/CRC (2006)
Ni, S.Y., Tseng, Y.C., Chen, Y.S., Sheu, J.P.: The broadcast storm problem in a mobile ad hoc network. In: Proc. MOBICOM, Seattle, pp. 151–162 (August 1999)
Simplot-Ryl, D., Stojmenovic, I., Wu, J.: Energy efficient backbone construction, broadcasting, and area coverage in sensor networks. In: Stojmenovic, I. (ed.) Handbook of Sensor Networks: Algorithms and Architectures, pp. 343–379. Wiley, Chichester (2005)
Stojmenovic, I., Seddigh, M., Zunic, J.: Dominating sets and neighbor elimination based broadcasting algorithms in wireless networks. IEEE Trans. on Parallel and Distributed Systems 13(1), 14–25 (2002)
Zhang, H., Hou, J.C.: Maintaining sensing coverage and connectivity in large sensor networks. Ad Hoc & Sensor Wireless Networks: An International Journal 1(1–2), 89–124
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ovalle-Martínez, F.J., Nayak, A., Stojmenović, I., Carle, J., Simplot-Ryl, D. (2006). Area Based Beaconless Reliable Broadcasting in Sensor Networks. In: Nikoletseas, S.E., Rolim, J.D.P. (eds) Algorithmic Aspects of Wireless Sensor Networks. ALGOSENSORS 2006. Lecture Notes in Computer Science, vol 4240. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11963271_13
Download citation
DOI: https://doi.org/10.1007/11963271_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69085-6
Online ISBN: 978-3-540-69087-0
eBook Packages: Computer ScienceComputer Science (R0)