Joint routing and topology formation in multihop UWB networks

doi:10.1109/JSAC.2005.863864

	Joint routing and topology formation in multihop UWB networks
	Wu, Q ; Xiong, YQ ; Zhang, Q ; Guo, ZH ; Xia, XG ; Li, ZC
	2006-04-01
发表期刊	IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS
ISSN	0733-8716
卷号	24 期号:4 页码:843-849
摘要	This paper addresses the throughput optimization problem in multihop ultra-wideband (UWB) networks by jointly considering network topology formation and routing. Given a spatial distribution of UWB devices and traffic requirement, we want to form piconets and select paths to maximize the network throughput. Although there have been several works considering the problem of selecting paths to achieve the optimal throughput in multihop wireless networks, to the best of our knowledge, none of them takes the topology formation into the consideration. In this paper, we use Boolean matrices to model role assignment in UWB networks and formulate the throughput optimization problem as a nonlinear programming (NLP) problem. Since the throughput optimization problem is NP-hard, we give an upper bound of the optimal throughput by relaxing some constraints and using pseudo-Boolean optimization to linearize the NLP. We prove that the solution of the upper bound is at most three times of the optimal throughput. Based on the topology formed by solving the upper bound, we formulate a lower bound of the optimal throughput as a linear programming problem and use column generation to solve the lower bound. Numerical results show that the lower bound is very close to the upper bound. Simulation results demonstrate the effectiveness of the scheme.
关键词	cross-layer design multihop networks piconet routing topology formation ultra-wideband (UWB)
DOI	10.1109/JSAC.2005.863864
收录类别	SCI
语种	英语
WOS研究方向	Engineering ; Telecommunications
WOS类目	Engineering, Electrical & Electronic ; Telecommunications
WOS记录号	WOS:000236775900020
出版者	IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
引用统计	被引频次：6[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/10388
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Wu, Q
作者单位	1.Beijing Samsung Telecom R&D Ctr, Beijing 100081, Peoples R China 2.Microsoft Res Asia, Beijing 100080, Peoples R China 3.Hong Kong Univ Sci & Technol, Dept Comp Sci, Kowloon, Hong Kong, Peoples R China 4.Lenovo Corp Res & Dev, Beijing 100085, Peoples R China 5.Univ Delaware, Dept Elect & Comp Engn, Newark, DE 19711 USA 6.Chinese Acad Sci, Inst Comp Technol, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Wu, Q,Xiong, YQ,Zhang, Q,et al. Joint routing and topology formation in multihop UWB networks[J]. IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS,2006,24(4):843-849.
APA	Wu, Q,Xiong, YQ,Zhang, Q,Guo, ZH,Xia, XG,&Li, ZC.(2006).Joint routing and topology formation in multihop UWB networks.IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS,24(4),843-849.
MLA	Wu, Q,et al."Joint routing and topology formation in multihop UWB networks".IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 24.4(2006):843-849.