GLOBALLY AWARE ROUTING IN MULTI-HOP WIRELESS NETWORKS: A FORMULATION AND ANALYSIS

被引:0
作者
Kolar, Vinay [1 ]
Abu-Ghazaleh, Nael B. [1 ]
机构
[1] SUNY Binghamton, Dept Comp Sci, Binghamton, NY 13902 USA
关键词
Multi-hop wireless networks; interference; routing; optimization;
D O I
10.1142/S0219265908002242
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Routing in multi-hop wireless networks is typically greedy, with every connection attempting to establish a path with the smallest number of hops. However, interference plays a major role in limiting the capacity of such networks. While recent protocols have attempted to account for interference, they do so reactively and without coordination. Approaches that coordinate routing to account for mutual interference achieve better performance than traditional approaches. Modeling routing with interference constraints is a complex non-linear optimization problem. We approach the problem using a Multi Commodity flow (MCF) formulation. We analyze the interaction of multiple routes and propose effective objective functions which attempt to maximize interference separation while limiting path inflation. We also show that the pattern of interference experienced by a link plays an important role in defining capacity. The model is directly useful in traffic engineering, provisioning and QoS admission control for mesh networks. In addition, it provides a tool for analyzing effective operation in MHWN providing insight into developing effective distributed protocols for them. We evaluate the formulation against routes obtained using a conventional routing algorithm under several scenarios and show that better performance is achieved in terms of throughput, goodput, and end-to-end delay.
引用
收藏
页码:205 / 230
页数:26
相关论文
共 28 条
[1]  
Ahuja R. K., 1993, NETWORK FLOWS
[2]  
[Anonymous], MOBICOM
[3]  
Bertsimas D., 1997, INTRO LINEAR OPTIMIZ
[4]  
BOORSTYN RR, 1987, IEEE T COMMUNICATION
[5]  
Chiang M., 2007, P IEEE
[6]  
CRUZ RL, 2003, INFOCOM
[7]  
Draves R., 2004, SIGCOMM
[8]  
Garetto M., 2005, P 11 ANN INT C MOB C, P200, DOI DOI 10.1145/1080829.1080851.
[9]  
Garetto M, 2006, IEEE INFOCOM SER, P1287
[10]  
Garey M.R., 1979, COMPUTERS INTRACTABI