×

Cross-layer optimization in ultra wideband networks. (English) Zbl 1127.90397

Summary: Ultra wideband (UWB) network brings both chance and challenge to personal area wireless communications. Compared with other IEEE 802 small range wireless protocols (such as WLAN and Bluetooth), UWB has both extremely high bandwidth (up to 480 Mbps) and low radiation. Moreover, the structured MAC layer of UWB is the fundamental difference to WLAN. The top one is that only when two UWB devices belong to the same piconet can they communicate with each other directly, which means that we must jointly consider topology formation and routing when deploying UWB networks because the interaction between routing and topology formation makes separate optimization ineffective. This paper tries to optimize UWB network from a cross-layer point of view. Specifically, given device spatial distribution and traffic requirement, we want to form piconets and determine routing jointly, to maximize the overall throughput. We formulate the problem of joint optimization to mixed-integer programming and give a practical lower bound that is very close to the theoretical upper bound in our simulation. Furthermore, our lower bound is much better than an algorithm that only considers topology formation in UWB networks.

MSC:

90C11 Mixed integer programming
68M10 Network design and communication in computer systems
90B10 Deterministic network models in operations research
Full Text: DOI

References:

[1] Boros E, Hammer P L. Pseudo-Boolean optimization. Discrete Appl Math, 2002, 123(1–3): 155–225 · Zbl 1076.90032 · doi:10.1016/S0166-218X(01)00341-9
[2] Basagni S, Bruno R, Mambrini G, et al. Comparative performance evaluation of scatternet formation protocols for networks of Bluetooth devices. ACM Wirel Networks, 2004, 10: 197–213 · doi:10.1023/B:WINE.0000013083.41155.fa
[3] Gong M X, Midkiff S F, Buehrer R M. A new piconet formation algorithm for UWB ad hoc networks. In: IEEE Conference on Ultra Wideband Systems and Technologies, Reston, VA, Nov. 2003, 180–184
[4] Gupta P, Kumar P R. The capacity of wireless networks. IEEE Trans Inform Theory, 2000, 46(2): 388–404 · Zbl 0991.90511 · doi:10.1109/18.825799
[5] Li J, Blake C, Douglas S J, et al. Capacity of Ad Hoc Wireless Networks. In: ACM Mobicom’01, Rome, Italy, 2001, 61–69
[6] Jain K, Padhye J, Padmanabhan V N, et al. Impact of interference on multi-hop wireless network performance. In: ACM Mobicom’03, San Diego, CA, USA, Sep. 2003, 66–80
[7] Kodialam M, Nandagopal T. Characterizing achievable rates in multi-hop wireless networks: The joint routing and scheduling problem. In: ACM Mobicom’03, San Diego, CA, USA, Sep. 2003, 42–54
[8] Zussman G, Segall A. Capacity assignment in bluetooth scatternets – Optimal and heuristic algorithms. Mobile Networks Appl, 2004, 9: 49–61 · doi:10.1023/A:1027321806934
[9] Raniwala A, Gopalan K, Chiueh T. Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks. ACM SIGMOBILE Mobile Comput Commun Review (MC2R), 2004, 8(2): 50–65 · doi:10.1145/997122.997130
[10] Radunovic B, Le Boudec J-Y. Optimal power control, scheduling, and routing in UWB networks. IEEE J Selected Areas Commun, 2004, 22(7): 1252–1270 · doi:10.1109/JSAC.2004.829343
[11] Feige U, Kilian J. Zero knowledge and the chromatic number. J Comput Syst Sci, 1998, 57(2): 187–199 · Zbl 0921.68089 · doi:10.1006/jcss.1998.1587
[12] Mehrotra A, Trick M A. A column generation approach for graph coloring, INFORMS. J Comput, 1996, 8(4): 344–354 · Zbl 0884.90144
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.