| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
ASCENT: Adaptive Self-Configuring sEnsor Networks Topologies
July 2004 (vol. 3 no. 3)
pp. 272-285
Advances in microsensor and radio technology will enable small but smart sensors to be deployed for a wide range of environmental monitoring applications. The low per-node cost will allow these wireless networks of sensors and actuators to be densely distributed. The nodes in these dense networks will coordinate to perform the distributed sensing and actuation tasks. Moreover, as described in this paper, the nodes can also coordinate to exploit the redundancy provided by high density so as to extend overall system lifetime. The large number of nodes deployed in these systems will preclude manual configuration, and the environmental dynamics will preclude design-time preconfiguration. Therefore, nodes will have to self-configure to establish a topology that provides communication under stringent energy constraints. ASCENT builds on the notion that, as density increases, only a subset of the nodes are necessary to establish a routing forwarding backbone. In ASCENT, each node assesses its connectivity and adapts its participation in the multihop network topology based on the measured operating region. This paper motivates and describes the ASCENT algorithm and presents analysis, simulation, and experimental measurements. We show that the system achieves linear increase in energy savings as a function of the density and the convergence time required in case of node failures while still providing adequate connectivity.
[1] 272 K.M. Alzoubi, P.-J. Wan, and O. Frieder, Message-Optimal Connected-Dominating-Set Construction for Routing in Mobile Ad Hoc Networks Proc. Third ACM Int'l Symp. Mobile Ad Hoc Networking and Computing (MobiHoc), June 2002.[2] B. Badrinath, J. Scholtz, M. Srivastava, K. Mills, and V. Stanford, IEEE Personal Comm., special issue on smart spaces and environments, K. Soolins, ed., Oct. 2000.[3] J. Broch, D.A. Maltz, D.B. Johnson, Y. Hu, and J. Jetcheva, A Performance Comparison of Multihop Wireless Ad Hoc Network Routing Protocols Proc. Fourth Ann. ACM/IEEE Int'l Conf. Mobile Computing and Networking (MobiCom '98), pp. 85-97, Oct. 1998.[4] A. Cerpa, N. Busek, and D. Estrin, SCALE: A Tool for Simple Connectivity Assessment in Lossy Environments Technical Report CENS Technical Report 0021, Center for Embedded Networked Sensing, Univ. of California, Los Angeles, Sept. 2003.[5] A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton, and J. Zhao, Habitat Monitoring: Application Driver for Wireless Communications Technology Proc. SIGCOMM Workshop Comm. in Latin America and the Carribean, Apr. 2001.[6] B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris, Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks Proc. Seventh Ann. ACM/IEEE Int'l Conf. Mobile Computing and Networking (MobiCom), pp. 85-96, July 2001.[7] D. Estrin, R. Govindan, J. Heidemann, and S. Kumar, Next Century Challenges: Scalable Coordination in Sensor Networks Proc. Fifth Ann. ACM/IEEE Int'l Conf. Mobile Computing and Networking (MobiCom), pp. 263-270, Aug. 1999.[8] Comm. ACM, special issue on embedding the internet, D. Estrin, R. Govindan, and J. Heidemann, eds., vol. 43, no. 5, May 2000.[9] S. Floyd, V. Jacobson, C.-G. Liu, S. McCanne, and L. Zhang, A Reliable Multicast Framework for Light-Weight Sessions and Application Level Framing Proc. ACM Special Interest Group on Data Comm. (SIGCOMM), pp. 342-356, Aug. 1995.[10] D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. Wicker, Complex Behavior at Scale: An Experimental Study of Low-Power Wireless Sensor Networks Technical Report UCLA CSD-TR 02-0013, Center for Embedded Networked Sensing, Univ. of California, Los Angeles, and Intel Research Lab, Univ. of California, Berkeley, Feb. 2002.[11] J. Gao, L.J. Guibas, J. Hershburger, L. Zhang, and A. Zhu, Geometric Spanner for Routing in Mobile Networks Proc. Second ACM Symp. Mobile Ad Hoc Networking and Computing (MobiHoc 01), pp. 45-55, Oct. 2001.[12] J. Gao, L.J. Guibas, J. Hershburger, L. Zhang, and A. Zhu, Discrete and Computational Geometry Proc. Second ACM Symp. Mobile Ad Hoc Networking and Computing (MobiHoc 01), vol. 30, no. 1, pp. 45-65, 2003.[13] L. Girod, J. Elson, A. Cerpa, N. Ramanathan, T. Stathopoulos, and D. Estrin, Emstar: A Software Environment for Developing and Deploying Wireless Sensor Networks Proc. 2004 USENIX Technical Conf., June-July 2004.[14] C. Intanagonwiwat, R. Govindan, and D. Estrin, Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks Proc. Sixth Ann. ACM/IEEE Int'l Conf. Mobile Computing and Networking (MobiCom), Aug. 2000.[15] V. Jacobson, Congestion Avoidance and Control Proc. ACM Special Interest Group on Data Comm. (SIGCOMM), pp. 314-329, Aug. 1988.[16] D.B. Johnson and D.A. Maltz, Dynamic Source Routing in Ad Hoc Wireless Networks Mobile Computing, T. Imielinski and H. Korth, eds., pp. 153-181, 1996.[17] Q. Li and D. Rus, Sending Messages to Disconnected Users in Disconnected Ad Hoc Mobile Networks Proc. Sixth Ann. ACM/IEEE Int'l Conf. Mobile Computing and Networking (MobiCom), pp. 44-55, Aug. 2000.[18] R. Metcalfe and D. Boggs, Ethernet: Distributed Packet Switching for Local Computer Networks Comm. ACM, pp. 395-404, July 1976.[19] RFM Monolithics, Tr1000 Low Power Radio System http://www.rfm.com/products/datatr1000.pdf , 2003.[20] V. Park and S. Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks Proc. 18th Ann. Joint Conf. IEEE Computer and Comm. Soc. (INFOCOM), pp. 1405-1414, Apr. 1997.[21] C. Perkins and E. Royer, Ad Hoc on Demand Distance Vector (AODV) Routing Proc. Second IEEE Workshop Mobile Computing Systems and Applications, pp. 90-100, Feb. 1999.[22] G. Pottie and W. Kaiser, Embedding the Internet: Wireless Integrated Network Sensors Comm. ACM, vol. 43, no. 5, pp. 51-58, May 2000.[23] B. Prabhakar, E. Uysal-Biyikoglu, and A.E. Gamal, Energy-Efficient Transmission over a Wireless Link Via Lazy Packet Scheduling Proc. 20th Ann. Joint Conf. IEEE Computer and Comm. Soc. (INFOCOM), pp. 386-394, Apr. 2001.[24] R. Ramanathan and R. Rosales-Hain, Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment Proc. 19th Ann. Joint Conf. IEEE Computer and Comm. Soc. (INFOCOM), pp. 404-413, Mar. 2000.[25] H. Schulzrinne, S. Casner, R. Frederick, and V. Jacobson, RTP: A Transport Protocol for Real Time Applications Request for Comments (RFC 1889), Jan. 1996.[26] C. Schurgers, V. Tsiatsis, and M. Srivastava, "STEM Topology Management for Efficient Sensor Networks," to be published in Proc. IEEE Aerospace Conf., IEEE CS Press, Los Alamitos, Calif., 2002.[27] K. Sohrabi and G. Pottie, Performance of a Novel Self-Organization Protocol for Wireless Ad Hoc Sensor Networks Proc. IEEE Vehicular Technology Conf., Sept. 2000.[28] M. Stemm and R. Katz, Measuring and Reducing Energy Consumption of Network Interfaces in Hand-Held Devices IEICE Trans. Comm., vol. 80, no. 8, pp. 1125-1131, Aug. 1997.[29] Y. Wang and X.-Y. Li, Geometric Spanners for Wireless Ad Hoc Networks Proc. 22nd Int'l Conf. Distributed Computing Systems (ICDCS 2002), July 2002.[30] A. Woo, T. Tong, and D. Culler, Taming the Underlying Challenges of Reliable Multihop Routing in Sensor Networks Proc. First ACM Sensys Conf., pp. 14-27, Nov. 2003.[31] Y. Xu, J. Heidemann, and D. Estrin, Geography-Informed Energy Conservation for Ad Hoc Routing Proc. Seventh Ann. ACM/IEEE Int'l Conf. Mobile Computing and Networking (MobiCom), pp. 70-84, July 2001.[32] W. Ye, J. Heidemann, and D. Estrin, “An Energy-Efficient MAC Protocol for Wireless Sensor Networks,” IEEE Infocom '02, June 2002.[33] Y.J. Zhao and R. Govindan, Understanding Packet Delivery Performance in Dense Wireless Sensor Networks Proc. First ACM Sensys Conf., Nov. 2003.[34] R. Zheng, J.C. Hou, and L. Sha, Asynchronous Wakeup for Ad Hoc Networks ACM Int'l Symp. Mobile Ad Hoc Networking and Computing, June 2003.
Index Terms:
Wireless sensor networks, adaptive topology, topology control, energy conservation.
Citation:
Alberto Cerpa, Deborah Estrin, "ASCENT: Adaptive Self-Configuring sEnsor Networks Topologies," IEEE Transactions on Mobile Computing, vol. 3, no. 3, pp. 272-285, July 2004, doi:10.1109/TMC.2004.16
