skip to main content
10.1145/1127777.1127784acmconferencesArticle/Chapter ViewAbstractPublication PagescpsweekConference Proceedingsconference-collections
Article

Global connectivity from local geometric constraints for sensor networks with various wireless footprints

Published: 19 April 2006 Publication History

Abstract

Adaptive power topology control (APTC) is a local algorithm for constructing a one-parameter family of θ-graphs, where each node increases power until it has a neighbor in every θ sector around it.We show it is possible to use such a local geometric θ-constraint to ensure full network connectivity, and consider tradeoffs between assumptions about the wireless footprint and constraints on the boundary nodes. In particular, we show that if the boundary nodes can communicate with neighboring boundary nodes and all interior nodes satisfy a θI π constraint, we can guarantee connectivity for any arbitrary wireless footprint. If we relax the boundary assumption and instead impose a θB < 3π/2 constraint on the boundary nodes, together with the θI < π constraint on interior nodes, we can guarantee full network connectivity using only a "weak-monotonicity" footprint assumption. The weak-monotonicity model, introduced herein, is much less restrictive than the disk model of coverage and captures aspects of the spatial correlations inherent in signal propagation and noise. We show that under the idealized disk model of coverage, APTC constructs graphs that are sparse. Finally, we show that if the wireless footprint has sufficiently small "eccentricity", then there is some θ for which greedy geometric routing always succeeds.

References

[1]
R. Wattenhofer, L. Li, P. Bahl, and Y. Wang. Distributed topology control for power efficient operation in multihop wireless ad hoc networks. In Proceedings of IEEE INFOCOM, 2001.
[2]
L. Li, J. Y. Halpern, P. Bahl, Yi-Min Wang, and R. Wattenhofer. Analysis of a cone-based topology control algorithm for wireless multi-hop networks. In Proceedings of the ACM Symposium on Principles of Distributed Computing, 2001.
[3]
R. M. D'Souza, S. Ramanathan, and D. Temple Lang. Measuring performance of ad hoc networks using timescales for information flow. In Proceedings of IEEE INFOCOM, 2003.
[4]
C. Perkins and E. Royer. Ad-hoc on-demand distance vector routing. In MILCOM '97 panel on Ad Hoc Networks, 1997.
[5]
S. Poduri, S. Pattem, B. Krishnamachari, and G. Sukhatme. Controlled deployments of sensor networks. In Press, 2006.
[6]
R. Wattenhofer and A. Zollinger. XTC: A practical topology control algorithm for ad-hoc networks. In Proceedings of the 18th International Parallel and Distributed Processing Symposium, 2004.
[7]
M. Penrose. Random Geometric Graphs. Oxford Studies in Probability. Oxford University Press, 2003.
[8]
D. Ganesan, D. Estrin, A. Woo, D. Culler, B. Krishnamachari, and S. Wicker. Complex behavior at scale: An experimental study of low-power wireless sensor networks. TR UCLA/CSD-TR 02-0013, 2002.
[9]
B. Karp and H. T. Kung. GPSR: greedy perimeter stateless routing for wireless networks. In Proc. 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom), 2000.
[10]
L. Girod and D. Estrin. Robust range estimation using acoutic and multimodal sensing. In Proceedings of the IEEE/RSJ Intl Conf on Intelligent Robots and Systems (IROS), 2001.
[11]
IEEE Community LAN MAN Standards community Wireless LAN medium access control (MAC) and physical layer (PHY) specif., 1997.
[12]
A. Cerpa and D. Estrin. Ascent: adaptive self-configuring sensor network topologies. IEEE Transations Journal on Mobile Computing, Special Issue on Mission-Oriented Sensor Networks, 3(3):272--285, 2004.
[13]
G.G. Finn. Routing and addressing problems in large metropolitan-scale internetworks. Technical report, 1987.
[14]
G. Toussaint. The relative neighborhood graph of a finite planer set. Pattern Recognition, 12(4):261--268, 1980.
[15]
K. Gabriel and R.Sokal. A new statistical approach to geographic variation analysis. Systematic Zoology, 18:259--278, 1969.
[16]
Q. Fang, J. Gao, and L. J. Guibas. Locating and bypassing routing holes in sensor networks. In Proceedings of IEEE INFOCOM, 2004.

Cited By

View all
  • (2011)Undirected connectivity of sparse Yao graphsProceedings of the 7th ACM ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing10.1145/1998476.1998482(25-32)Online publication date: 9-Jun-2011
  • (2010)Opportunity-Based Topology Control in Wireless Sensor NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2009.5721:3(405-416)Online publication date: 1-Mar-2010
  • (2009)Using Local Geometry for Tunable Topology Control in Sensor NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2008.958:2(218-230)Online publication date: 1-Feb-2009
  • Show More Cited By

Index Terms

  1. Global connectivity from local geometric constraints for sensor networks with various wireless footprints

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      IPSN '06: Proceedings of the 5th international conference on Information processing in sensor networks
      April 2006
      514 pages
      ISBN:1595933344
      DOI:10.1145/1127777
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 19 April 2006

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. ad hoc networks
      2. adaptive power
      3. connectivity
      4. graph theory
      5. self-organization
      6. topology control

      Qualifiers

      • Article

      Conference

      IPSN06
      Sponsor:

      Acceptance Rates

      Overall Acceptance Rate 143 of 593 submissions, 24%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)4
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 15 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2011)Undirected connectivity of sparse Yao graphsProceedings of the 7th ACM ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing10.1145/1998476.1998482(25-32)Online publication date: 9-Jun-2011
      • (2010)Opportunity-Based Topology Control in Wireless Sensor NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2009.5721:3(405-416)Online publication date: 1-Mar-2010
      • (2009)Using Local Geometry for Tunable Topology Control in Sensor NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2008.958:2(218-230)Online publication date: 1-Feb-2009
      • (2009)A Generalized Probabilistic Topology Control for Wireless Sensor NetworksIEEE INFOCOM 200910.1109/INFCOM.2009.5062230(2776-2780)Online publication date: Apr-2009
      • (2008)Opportunity-Based Topology Control in Wireless Sensor NetworksProceedings of the 2008 The 28th International Conference on Distributed Computing Systems10.1109/ICDCS.2008.91(421-428)Online publication date: 17-Jun-2008
      • (2008)Improved footprint modeling for wireless sensor networks2008 IEEE Antennas and Propagation Society International Symposium10.1109/APS.2008.4619020(1-4)Online publication date: Jul-2008
      • (2007)Efficient Distributed Topology Control in 3-Dimensional Wireless Networks2007 4th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks10.1109/SAHCN.2007.4292821(91-100)Online publication date: Jun-2007

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media