The scheduling and energy complexity of strong connectivity in ultra-wideband networks

ABSTRACT

Recently Moscibroda and Wattenhofer came up with the notion of scheduling complexity to capture the minimum amount of time to successfully schedule all the transmission requests under the physical SINR model. Their algorithm featuring a non-linear power assignment can schedule strongly connected transmissions in narrowband networks with O(log⁴ n) timeslots. In this paper, we first generalize this result to ultra-wideband networks. We show the strong connectivity scheduling complexity in UWB networks to be O(log (n/m)∙log³ n), where m is the processing gain. Secondly, we show that both of these polylogarithmic scheduling complexity results are gained at the expense of exponential energy complexity with lower bound ω(n∙2ⁿ). We also prove the upper bound of the energy complexity in narrowband networks to beO(n²∙2^nα), and for UWB networks, this upper bound can be reduced by a processing gain factor.On the other hand, we show that improving the scheduling complexity through arbitrary power control has its limitations, and that different power assignment strategies have different impacts on the protocol interference models, which was often neglected in the design of wireless scheduling algorithms. Compared with narrowband networks, although the effect of aggregate interferences in UWB networks is greatly reduced, we demonstrate that the constant and linear power assignments in UWB networks are still inefficient in the worst case with respect to the scheduling complexity (Ω(n/m), which suggests there is a need for a better arbitrary power assignment.Our analyses shed new light on the design of the power assignment scheme and the performance analysis of the wireless scheduling algorithms. In energy-constrained wireless networks, a tradeoff between the scheduling complexity and energy complexity is a practical consideration. Our results in this paper can be directly applied to other spread-spectrum networks including DS-CDMA and FH-CDMA.

REFERENCES

• 1: H. Balakrishnan, C. Barrett, V. S. Anil Kumar, M. Marathe, and S. Thite. The distance 2-matching problem and its relationship to the MAC layer capacity of ad-hoc wireless networks. IEEE J. Selected Areas in Communications, 22(6):1069--1079, August 2004.
• 2: A. Behzad and I. Rubin. On the performance of graph-based scheduling algorithms for packet radio networks. In Proc. of IEEE Global Telecommunications Conference (GLOBECOM), 6:3432--3436, San Francisco, December 2003.
• 3: Gurashish Brar , Douglas M. Blough , Paolo Santi, Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161092]
• 4: F. Cuomo, C. Martello, A. Baiocchi and F. Capriotti. Radio resource sharing for ad-hoc networking with UWB. IEEE Journal on Selected Areas in Communications, 20(9):1722--1732, December 2002.
• 5: Matthias Grossglauser , David N. C. Tse, Mobility increases the capacity of ad hoc wireless networks, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.477-486, August 2002 [doi>10.1109/TNET.2002.801403]
• 6: Piyush Gupta and P. R. Kumar. The capacity of wireless networks. IEEE Transactions on Information Theory, 46(2):388--404, 2000.
• 7: Friedhelm Meyer auf de Heide , Christian Schindelhauer , Klaus Volbert , Matthias Grünewald, Energy, congestion and dilation in radio networks, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564910]
• 8: Kamal Jain , Jitendra Padhye , Venkata N. Padmanabhan , Lili Qiu, Impact of interference on multi-hop wireless network performance, Wireless Networks, v.11 n.4, p.471-487, July 2005 [doi>10.1007/s11276-005-1769-9]
• 9: S. Koskie and Z. Gajic. Signal-to-interference-based power control for wireless networks: a survey, 1992-2005. Dynamics of Continuous, Discrete and Impulsive Systems B: Applications and Algorithms, 13(2):187--220, 2006.
• 10: T. Moscibroda and R. Wattenhofer. The complexity of connectivity in wireless networks. In Proc. 25th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Barcelona, Spain, April 2006.
• 11: Thomas Moscibroda , Roger Wattenhofer , Aaron Zollinger, Topology control meets SINR:: the scheduling complexity of arbitrary topologies, Proceedings of the seventh ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132939]
• 12: R.C. Qiu, H. Liu, and X. Shen. Ultra-wideband for multiple-access communications. IEEE Communications Magazine, 43(2):80--87, Feb. 2005.
• 13: B. Radunovic and J.-Y. Le Boudec. Optimal power control, scheduling and routing in UWB Networks. IEEE Journal on Selected Areas in Communications, 22(7):1252--1270, Sept. 2004.
• 14: S. Schmid and R. Wattenhofer. Algorithmic models for sensor networks. In Proc. 14th International Workshop on Parallel and Distributed Real-Time Systems (WPDRTS), Island of Rhodes, Greece, April 2006.
• 15: Arunabha Sen , Mark L. Huson, A new model for scheduling packet radio networks, Wireless Networks, v.3 n.1, p.71-82, March 1997 [doi>10.1023/A:1019128411323]
• 16: R. Wattenhofer. MACbeth: The three witches of media access theory . In 1st IEEE International Workshop on Foundation and Algorithms for Wireless Networking (FAWN), Pisa, Italy, March 2006.
• 17: M. Z. Win and R. A. Scholtz. Ultra-wide bandwidth time-hopping spread-spectrum impulse radio for wireless multiple-access communications. IEEE Transactions on Communications, 48(4):679--691,2000
• 18: Xiangying Yang , Gustavo de Veciana, Inducing spatial clustering in MAC contention for spread spectrum ad hoc networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062706]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations; Sequencing and scheduling

General Terms:
Algorithms, Performance, Theory

Keywords:
ad hoc and sensor networks, energy complexity, interference control, interference models, scheduling complexity, ultra-wideband