File Download
There are no files associated with this item.
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: The scheduling and energy complexity of strong connectivity in ultra-wideband networks
Title | The scheduling and energy complexity of strong connectivity in ultra-wideband networks |
---|---|
Authors | |
Keywords | Ad hoc and sensor networks Energy complexity Interference control Interference models Scheduling complexity Ultra-wideband |
Issue Date | 2006 |
Citation | Acm Mswim 2006 - Proceedings Of The 9Th Acm Symposium On Modeling, Analysis And Simulation Of Wireless And Mobile Systems, 2006, v. 2006, p. 282-290 How to Cite? |
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(log4 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/w) · log3 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 · 2n). We also prove the upper bound of the energy complexity in narrowband networks to be O(n2 · 2na), 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. Copyright 2006 ACM. |
Persistent Identifier | http://hdl.handle.net/10722/93180 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Hua, QS | en_HK |
dc.contributor.author | Lau, FCM | en_HK |
dc.date.accessioned | 2010-09-25T14:53:19Z | - |
dc.date.available | 2010-09-25T14:53:19Z | - |
dc.date.issued | 2006 | en_HK |
dc.identifier.citation | Acm Mswim 2006 - Proceedings Of The 9Th Acm Symposium On Modeling, Analysis And Simulation Of Wireless And Mobile Systems, 2006, v. 2006, p. 282-290 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/93180 | - |
dc.description.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(log4 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/w) · log3 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 · 2n). We also prove the upper bound of the energy complexity in narrowband networks to be O(n2 · 2na), 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. Copyright 2006 ACM. | en_HK |
dc.language | eng | en_HK |
dc.relation.ispartof | ACM MSWiM 2006 - Proceedings of the 9th ACM Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems | en_HK |
dc.subject | Ad hoc and sensor networks | en_HK |
dc.subject | Energy complexity | en_HK |
dc.subject | Interference control | en_HK |
dc.subject | Interference models | en_HK |
dc.subject | Scheduling complexity | en_HK |
dc.subject | Ultra-wideband | en_HK |
dc.title | The scheduling and energy complexity of strong connectivity in ultra-wideband networks | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Lau, FCM:fcmlau@cs.hku.hk | en_HK |
dc.identifier.authority | Lau, FCM=rp00221 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.scopus | eid_2-s2.0-33750907928 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-33750907928&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 2006 | en_HK |
dc.identifier.spage | 282 | en_HK |
dc.identifier.epage | 290 | en_HK |
dc.identifier.scopusauthorid | Hua, QS=15060090400 | en_HK |
dc.identifier.scopusauthorid | Lau, FCM=7102749723 | en_HK |