ABSTRACT
The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed topology control algorithm. This algorithm, introduced in [16], does not assume that nodes have GPS information available; rather it depends only on directional information. Roughly speaking, the basic idea of the algorithm is that a node u transmits with the minimum power pu, α required to ensure that in every cone of degree α around u, there is some node that u can reach with power pu, α. We show that taking α = 5π/6 is a necessary and sufficient condition to guarantee that network connectivity is preserved. More precisely, if there is a path from s to t when every node communicates at maximum power then, if α ⪇ 5π/6, there is still a path in the smallest symmetric graph Gα containing all edges (u, v) such that u can communicate with v using power pu, α. On the other hand, if α > 5π/6, connectivity is not necessarily preserved. We also propose a set of optimizations that further reduce power consumption and prove that they retain network connectivity. Dynamic reconfiguration in the presence of failures and mobility is also discussed. Simulation results are presented to demonstrate the effectiveness of the algorithm and the optimizations.
- 1.A. Chandrakazan, R. Amirtharajah, S. H. Cho, J. Goodman, G. Konduri, J. Kulik, W. Rabiner, and A. Wang. Design considerations for distributed microsensor systems. In Proc. IEEE Custom Integrated Circuits Conference (CICC), pages 279-286, May 1999.Google ScholarCross Ref
- 2.L. P. Clare, G. J. Pottie, and J. R. Agre. Self-organizing distributed sensor networks. In Proc. SPIE Con}. on Unattended Ground Sensor Technologies and Applications, pages 229-237, April 1999.Google ScholarCross Ref
- 3.Y. Hassin and D. Peleg. Sparse communication networks and efficient routing in the plane. In Proc. 19th ACM Syrup. on Principles of Distributed Computing, pages 41-50, 2000. Google ScholarDigital Library
- 4.L. Hu. Topology control for multihop packet radio networks. IEEE Trans. on Communications, 41(10):1474 -1481, October 1993.Google ScholarCross Ref
- 5.J. W. Jaromczyk and G. T. Touesaint. Relative neighborhood graphs and their relatives. Proc. IEEE, 80:1502-1517, 1992.Google ScholarCross Ref
- 6.R. E. Kahn. The organization of computer resources into a packet radio network. IEEE Transactions on Communications, COM-25(1):169-178, January 1977.Google Scholar
- 7.J. M. Keil and C. A. Gutwin. Classes of graph which appraximate the complete Euclidean graph. Discrete and computational geometry, 7:13-28, 1992. Google ScholarDigital Library
- 8.K. Krizman, T. E. Biedks, and T.S. Rappaport. Wireless position location: fundamentals, implementation strategies, and source of error. In IEEE 47th Vehicular Technology Conference, pages 919-923, 1997.Google ScholarCross Ref
- 9.L. Li and J. Y. Halpern. Minimum energy mobile wireless networks revisited. In Proc. IEEE International Conference on Communications (ICC), June 2001.Google ScholarCross Ref
- 10.C. E. Perkins. Ad Hoc Networking. Addison-Wesley, Reading, MA, 2001. Google ScholarDigital Library
- 11.G. J. Pottie and W. J. Kaiser. Wireless integrated network sensors. Communications of the ACM, 43(5):51-58, May 2000. Google ScholarDigital Library
- 12.R. Ramanathan and R. Rosales-Hain. Topology control of multihop wireless networks using transmit power adjustment. In Proc. IEEE lnfocom 2000, pages 404-413, March 2000.Google ScholarCross Ref
- 13.T. S. Rappaport. Wireless communications: principles and practice. Prentice Hall, 1996. Google ScholarDigital Library
- 14.V. Rodoplu and T. H. Meng. Minimum energy mobile wireless networks. IEEE J. Selected Areas in Communications, 17(8):1333-1344, August 1999. Google ScholarDigital Library
- 15.G. Tonssaint. The relative neighborhood graph of a finite planar set. Pattern recognition, 12(4):261-268, 1980.Google ScholarCross Ref
- 16.R. Wattenhofer, L. Li, P. Bald, and Y. M. Wang. Distributed topology control for power efficient operation in multihop wireless ad hoc networks. In Proc. IEEE Infocom 2001, pages 1388-1397, April 2001.Google ScholarCross Ref
Index Terms
- Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks
Recommendations
A cone-based distributed topology-control algorithm for wireless multi-hop networks
The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed topology-control (CBTC) algorithm. This algorithm does not assume that ...
Fault-tolerant and 3-dimensional distributed topology control algorithms in wireless multi-hop networks
The topology of a multi-hop wireless network can be controlled by varying the transmission power at each node. The lifetime of such networks depends on battery power at each node. This paper presents a distributed fault-tolerant topology control ...
Comments