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

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: Li Li , Joseph Y. Halpern , Paramvir Bahl , Yi-Min Wang , Roger Wattenhofer, Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.264-273, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384043]
• 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: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 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: Alberto Cerpa , Deborah Estrin, ASCENT: Adaptive Self-Configuring sEnsor Networks Topologies, IEEE Transactions on Mobile Computing, v.3 n.3, p.272-285, July 2004 [doi>10.1109/TMC.2004.16]
• 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.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

General Terms:
Algorithms, Design, Theory

Keywords:
ad hoc networks, adaptive power, connectivity, graph theory, self-organization, topology control