Fabian Kuhn
ABSTRACT
A newly deployed multi-hop radio network is unstructured and lacks a reliable and efficient communication scheme. In this paper, we take a step towards analyzing the problems existing during the initialization phase of ad hoc and sensor networks. Particularly, we model the network as a multi-hop quasi unit disk graph and allow nodes to wake up asynchronously at any time. Further, nodes do not feature a reliable collision detection mechanism, and they have only limited knowledge about the network topology. We show that even for this restricted model, a good clustering can be computed efficiently. Our algorithm efficiently computes an asymptotically optimal clustering. Based on this algorithm, we describe a protocol for quickly establishing synchronized sleep and listen schedule between nodes within a cluster. Additionally, we provide simulation results in a variety of settings.
- I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. Wireless Sensor Networks: A Survey. Computer Networks Journal, 38(4):393--422, 2002. Google Scholar
Digital Library
- K. Alzoubi, P.-J. Wan, and O. Frieder. Message-Optimal Connected Dominating Sets in Mobile Ad Hoc Networks. In Proc. of the 3rd ACM Int. Symposium on Mobile Ad Hoc Networking and Computing (MobiHOC), pages 157--164, EPFL Lausanne, Switzerland, 2002. Google ScholarDigital Library
- D. J. Baker and A. Ephremides. The Architectural Organization of a Mobile Radio Network via a Distributed Algorithm. IEEE Transactions on Communications, COM-29(11):1694--1701, 1981.Google Scholar
- R. Bar-Yehuda, O. Goldreich, and A. Itai. On the Time-Complexity of Broadcast in Radio Networks: an Exponential Gap between Determinism and Randomization. In Proc. 6th ACM Symp. on Principles of Distributed Computing (PODC), pages 98--108, 1987. Google ScholarDigital Library
- L. Barriere, P. Fraigniaud, and L. Narayanan. Robust Position-Based Routing in Wireless Ad Hoc Networks with Unstable Transmission Ranges. In Proc. 5th Int. workshop on Discrete algorithms and methods for mobile computing and communications, pages 19--27, 2001. Google ScholarDigital Library
- S. Basagni. Distributed Clustering for Ad Hoc Networks. In Proceedings of the IEEE International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN), pages 310--315, 1999. Google ScholarDigital Library
- M. Chatterjee, S. K. Das, and D. Turgut. An On-Demand Weighted Clustering Algorithm (WCA) for Ad-Hoc Networks. In Proceedings of IEEE GLOBECOM 2000, pages 1697--1701. ACM Press, 2000.Google ScholarCross Ref
- J. Deng and Z. Haas. Dual Busy Tone Multiple Access (DBTMA): A New Medium Access Control for Packet Radio Networks. In Proceedings of IEEE ICUPC, volume 1, pages 973--977, 1998.Google ScholarCross Ref
- Y. M. E. Kushilevitz. An Ω(D log (N/D)) Lower Bound for Broadcast in Radio Networks. SIAM Journal on Computing, 27:702--712, 1998. Google ScholarDigital Library
- U. Feige. A Threshold of ln n for Approximating Set Cover. Journal of the ACM (JACM), 45(4):634--652, 1998. Google ScholarDigital Library
- J. Gao, L. Guibas, J. Hershberger, L. Zhang, and A. Zhu. Discrete Mobile Centers. In Proc. 17th Symposium on Computational Geometry (SCG), pages 188--196. ACM Press, 2001. Google ScholarDigital Library
- M. R. Garey and D. S. Johnson. Computers and Intractability, A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979. Google ScholarDigital Library
- L. Gasieniec, A. Pelc, and D. Peleg. The wakeup problem in synchronous broadcast systems (extended abstract). In Proceedings of the 19th ACM symposium on Principles of Distributed Computing (PODC), pages 113--121, 2000. Google ScholarDigital Library
- M. Gerla and J. Tsai. Multicluster, mobile, multimedia radio network. ACM/Baltzer Journal of Wireless Networks, 1(3):255--265, 1995. Google ScholarDigital Library
- W. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-Efficient Communication Protocol for Wireless Microsensor Networks. In Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, pages 3005--3014, 2000. Google ScholarDigital Library
- H. B. Hunt, III, M. V. Marathe, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz, and R. E. Stearns. NC-Approximation Schemes for NP- and PSPACE-hard Problems for Geometric Graphs. Journal of Algorithms, 26(2):238--274, 1998. Google ScholarDigital Library
- L. Jia, R. Rajaraman, and R. Suel. An Efficient Distributed Algorithm for Constructing Small Dominating Sets. In Proc. of the 20th ACM Symposium on Principles of Distributed Computing (PODC), pages 33--42, 2001.Google Scholar
- T. Jurdzinski and G. Stachowiak. Probabilistic Algorithms for the Wakeup Problem in Single-Hop Radio Networks. In Proceedings of 13th Annual International Symposium on Algorithms and Computation (ISAAC), volume 2518 of Lecture Notes in Computer Science, pages 535--549, 2002. Google ScholarDigital Library
- R. M. Karp. Reducibility Among Combinatorial Problems. In Proc. of a Symposium on the Complexity of Computer Computations, pages 85--103, 1972.Google ScholarCross Ref
- R. Kershner. The number of circles covering a set. American Journal of Mathematics, 62, 1939.Google Scholar
- F. Kuhn, T. Moscibroda, and R. Wattenhofer. Radio Network Clustering from Scratch. In Proceedings of the 12th Annual European Symposium on Algorithms (ESA), 2004.Google ScholarCross Ref
- F. Kuhn, T. Moscibroda, and R. Wattenhofer. What Cannot be Computed Locally! In Proceedings of the 23rd ACM Symposium on the Principles of Distributed Computing (PODC), 2004. Google ScholarDigital Library
- F. Kuhn and R. Wattenhofer. Constant-Time Distributed Dominating Set Approximation. In Proceedings of 22^nd$ ACM Int. Symposium on the Principles of Distributed Computing (PODC), pages 25--32, 2003. Google ScholarDigital Library
- F. Kuhn, R. Wattenhofer, and A. Zollinger. Ad-hoc Networks Beyond Unit Disk Graphs. In Proceedings of the 2003 Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), pages 69--78. ACM Press, 2003. Google ScholarDigital Library
- S. Kutten and D. Peleg. Fast Distributed Construction of Small k-Dominating Sets and Applications. Journal of Algorithms, 28:40--66, 1998. Google ScholarDigital Library
- K. Nakano and S. Olariu. Energy-Efficient Initialization Protocols for Single-Hop Radio Networks with no Collision Detection. IEEE Transactions on Parallel and Distributed Systems, 11(8), 2000. Google ScholarDigital Library
- V. Rajendran, K. Obraczka, and J. J. Garcia-Luna-Aceves. Energy-efficient collision-free medium access control for wireless sensor networks. In Proceedings of the 1^st$ International Conference on Embedded Networked Sensor Systems (SenSys), pages 181--192. ACM Press, 2003. Google ScholarDigital Library
- L. G. Roberts. Aloha Packet System with and without Slots and Capture. ACM SIGCOMM, Computer Communication Review, 5(2):28--42, 1975. Google ScholarDigital Library
- J. Sharony. An architecture for mobile radio networks with dynamically changing topology using virtual subnets. Mobile Networks and Applications, 1(1):75--86, 1996. Google ScholarDigital Library
- P. Sinha, R. Sivakumar, and V. Bharghavan. Enhancing Ad Hoc Routing with Dynamic Virtual Infrastructures. In IEEE Conference on Computer Communications (INFOCOM), pages 1763--1772, 2001.Google Scholar
- F. A. Tobagi and L. Kleinrock. Packet Switching in Radio Channels: Part II - The Hidden Terminal Problem in Carrier Sense Multiple Access and the Busy Tone Solution. COM-23(12):1417--1433, 1975.Google Scholar
- P. Wan, K. Alzoubi, and O. Frieder. Distributed construction of connected dominating set in wireless ad hoc networks. In Proceedings of INFOCOM, 2002.Google Scholar
- Y. Wang and X.-Y. Li. Geometric Spanners for Wireless Ad Hoc Networks. In Proc. of the 22^nd$ Int. Conf. on Distributed Computing Systems (ICDCS), 2002. Google ScholarDigital Library
- A. Woo and D.-E. Culler. A transmission control scheme for media access in sensor networks. In Proc. 7th Int. Conf. on Mobile Computing and Networking (MOBICOM), pages 221--235. ACM Press, 2001. Google ScholarDigital Library
- J. Wu and H. Li. On Calculating Connected Dominating Set for Efficient Routing in Ad Hoc Wireless Networks. In Proc. of the 3^rd$ Int. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), pages 7--14, 1999. Google ScholarDigital Library
- W. Ye, J. Heidemann, and D. Estrin. An Energy-Efficient MAC protocol for Wireless Sensor Networks. In Proceedings of IEEE INFOCOM, pages 1567--1576, New York, NY, USA, June 2002.Google Scholar
Index Terms
- Initializing newly deployed ad hoc and sensor networks
Recommendations
Performance evaluation of routing protocols in vehicular ad-hoc networks
This paper presents a reactive location routing algorithm that uses cluster-based flooding for Vehicular Ad-hoc Networks (VANET). We compare both position-based and non-position-based routing strategies in typical urban and motorway traffic scenarios. A ...
A weight-based clustering multicast routing protocol for mobile ad hoc networks
In mobile ad hoc networks, the mobile nodes can move arbitrarily without any centralised management mechanism. The topology of these networks can be very dynamic due to the mobility of mobile nodes. Under such changeable network topology, multicasting ...
A Distributed Virtual Backbone Development Scheme for Ad-Hoc Wireless Networks
The virtual backbone is an approach for solving routing problems in ad-hoc wireless networks. The virtual backbone approach features low latency, moderate routing overhead and is a hybrid scheme that uses the table-driven and on-demand routing ...
Comments