Cross-layer Design for Wireless Mesh Networks with Advanced Physical and Network Layer Techniques.
PhD thesis, Concordia University.
Cross-layer optimization is an essential tool for designing wireless network protocols. We present a cross-layer optimization framework for wireless networks where at each node, various smart antenna techniques such as beam-forming, spatial division multiple access and spatial division multiplexing are employed. These techniques provide interference suppression, capability for simultaneous communication with several nodes and transmission with higher data rates, respectively. By
integrating different combinations of these multi-antenna techniques in physical layer with various constraints from MAC and network layers, three Mixed Integer Linear
Programming models are presented to minimize the scheduling period. Since these optimization problems are combinatorially complex, the optimal solution is approached by a Column Generation (CG) decomposition method. Our numerical results show that the resulted directive, multiple access and multiplexing gains combined
with scheduling, effectively increase both the spatial reuse and the capacity of the links and therefore enhance the achievable system throughput.
The introduced cross-layer approach is also extended to consider heterogeneous networks where we present a multi-criteria optimization framework to model the design problem with an objective of jointly minimizing the cost of deployment and the scheduling period. Our results reveal the significant benefits of this joint design method.
We also investigate the achievable performance gain that network coding (with opportunistic listening) when combined with Successive Interference Cancellation (SIC) brings to a multi-hop wireless network. We develop a cross-layer formulation in which SIC enables concurrent receptions from multiple transmitters and network coding reduces the transmission time-slot for minimizing the scheduling time. To solve this combinatorially complex non-linear problem, we decompose it to two linear sub-problems; namely opportunistic network coding aware routing, and scheduling
sub-problems. Our results affirm our expectation for a remarkable performance improvement when both techniques are jointly used.
Further, we develop an optimization model for combining SIC with power control (PC). Our model optimally adjusts the transmission power of nodes to avoid interference on unintended receivers and properly embraces undesired interference through SIC. Therefore, it provides a balance between usage of PC and SIC at the transmitting and receiving sides, respectively. Our results show considerable
throughput improvement in dense and heavily loaded networks.
|Divisions:||Concordia University > Faculty of Engineering and Computer Science > Electrical and Computer Engineering|
|Item Type:||Thesis (PhD)|
|Degree Name:||Ph. D.|
|Program:||Electrical and Computer Engineering|
|Date:||4 August 2012|
|Thesis Supervisor(s):||Shayan, Yousef and Assi, Chadi|
|Keywords:||Cross-layer design, optimization, column generation, path-based routing, link-based routing, scheduling, successive interference cancellation, power control, network coding, opportunistic listening, smart antennas, multiple antennas, beam-forming, spatial division multiple access, spatial division multiplexing, multi-packet reception, SINR interference model|
|Deposited On:||31 Oct 2012 12:16|
|Last Modified:||05 Nov 2016 02:21|
References: 802.11n challenge. Technical report, Layland Consulting and Joanie M.Wexler & Associates and Webtorials, March 2009.
 R. Ahlswede, Ning Cai, S.-Y.R. Li, and R.W. Yeung. Network information flow. Information Theory, IEEE Transactions on, 46(4):1204 –1216, jul 2000.
 P.D. Alexander, M.C. Reed, J.A. Asenstorfer, and C.B. Schlegel. Iterative multiuser interference reduction: turbo cdma. Communications, IEEE Transactions on, 47(7):1008–1014, jul 1999.
 H.M. Almasaeid and A.E. Kamal. Assisted-multicast scheduling in wireless cognitive mesh networks. In Communications (ICC), 2010 IEEE International Conference on, pages 1 –5, may 2010.
 J.G. Andrews. Interference cancellation for cellular systems: a contemporary overview. Wireless Communications, IEEE, 12(2):19 – 29, april 2005.
 Emre Telat Ar and I. Emre Telatar. Capacity of multi-antenna gaussian channels. European Transactions on Telecommunications, 10:585–595, 1999.
 A. Argyriou. Cross-layer and cooperative opportunistic network coding in wireless ad hoc networks. Vehicular Technology, IEEE Transactions on, 59(2):803–812, feb. 2010.
 T. Hahn B. Mumey, Jian Tang. Algorithmic aspects of communications in multihop wireless networks with mimo links. In IEEE Proceedings ICC, pages 1–6, May 2010.
 S. Barghi, H. Jafarkhani, and H. Yousefi’zadeh. Mimo-assisted mpr-aware mac design for asynchronous wlans. Networking, IEEE/ACM Transactions on, 19(6):1652 –1665, dec. 2011.
 R. Bhatia and Li Li. Throughput optimization of wireless mesh networks with mimo links. INFOCOM 2007. IEEE, pages 2326–2330, May 2007.
 Ezio Biglieri, Robert Calderbank, Anthony Constantinides, Andrea Goldsmith, and H. Vincent Poor. MIMO Wireless Communications. Cambridge University Press, 2007.
 Sanjit Biswas and Robert Morris. Exor: opportunistic multi-hop routing for wireless networks. In SIGCOMM '05: Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, volume 35, pages 133–144, New York, NY, USA, October 2005. ACM Press.
 Patrik Bj¨orklund, Peter V¨arbrand, and Di Yuan. A column generation method for spatial tdma scheduling in ad hoc networks. Ad Hoc Networks, 2(4):405-418, 2004.
 J. Blomer and N. Jindal. Transmission capacity of wireless ad hoc networks: Successive interference cancellation vs. joint detection. In Communications, ICC '09. IEEE International Conference on, pages 1 –5, june 2009.
 Yih-Hao Lin Bongyong Song and R.L. Cruz. Weighted max-min fair beamforming, power control, and scheduling for a miso downlink. IEEE Transac tions on Wireless Communications, 7(2):464–469, 2008.
 Stephen Boyd and Jacob Mattingley. Branch and bound methods, 2003.
 Min Cao, Xiaodong Wang, Seung-Jun Kim, and M. Madihian. Multi-hop wireless backhaul networks: a cross-layer design paradigm. Selected Areas in Communications, IEEE Journal on, 25(4):738–748, May 2007.
 G.D. Celik, G. Zussman, W.F. Khan, and E. Modiano. Mac for networks with multipacket reception capability and spatially distributed nodes. Mobile Computing, IEEE Transactions on, 9(2):226 –240, feb. 2010.
 Biao Chen and M.J. Gans. Mimo communications in ad hoc networks. In Vehicular Technology Conference, 2005. VTC 2005-Spring. 2005 IEEE 61st, volume 4, pages 2434–2438 Vol. 4, 2005.
 H. Chen, F. Yu, H.C.B. Chan, and V.C.M. Leung. A novel multiple access scheme over multi-packet reception channels for wireless multimedia networks. Wireless Communications, IEEE Transactions on, 6(4):1501 –1511, april 2007.
 Wei Chen, K.B. Letaief, and Zhigang Cao. A cross layer method for interference cancellation and network coding in wireless networks. In Communications, 2006. ICC '06. IEEE International Conference on, volume 8, pages 3693 –3698, june 2006.
 Bow-Nan Cheng, M. Yuksel, and S. Kalyanaraman. Orthogonal rendezvous routing protocol for wireless mesh networks. Networking, IEEE/ACM Transactions on, 17(2):542–555, April 2009.
 Mung Chiang, S.H. Low, A.R. Calderbank, and J.C. Doyle. Layering as optimization decomposition: A mathematical theory of network architectures. Proceedings of the IEEE, 95(1):255 –312, jan. 2007.
 R.R. Choudhury and N. Vaidya. Mac-layer capture: A problem in wireless mesh networks using beamforming antennas. Sensor, Mesh and Ad Hoc Communications and Networks, 2007. SECON '07. 4th Annual IEEE Communications Society Conference on, pages 401–410, June 2007.
 Shan Chu and Xin Wang. Opportunistic and cooperative spatial multiplexing in mimo ad hoc networks. In MobiHoc '08, pages 63–72. ACM, 2008.
 V. Chv´atal. Linear Programming. Series of Books in the Mathematical Sciences. W.H. Freeman, 1983.
 J. Cloud, L.M. Zeger, and M. Medard. Mac centered cooperation - synergistic design of network coding, multi-packet reception, and improved fairness to increase network throughput. Selected Areas in Communications, IEEE Journal
on, 30(2):341 –349, february 2012.
 Jason Cloud, Linda Zeger, and Muriel M´edard. Co-designing multi-packet reception, network coding, and mac using a simple predictive model. CoRR, abs/1101.5779, 2011.
 V. Corvino, L. Giupponi, A. Perez Neira, V. Tralli, and R. Verdone. Crosslayer radio resource allocation: The journey so far and the road ahead. In Cross Layer Design, 2009. IWCLD '09. Second International Workshop on, pages 1–6, 2009.
 CPLEX. Using the CPLEX Callable Library. CPLEX Optimization Inc., 9.1.3 edition, 2005.
 J. Crichigno, M.Y. Wu, and W. Shu. Throughput optimization in wireless networks with multi-packet reception and directional antennas. In Wireless Communications and Networking Conference, 2009. WCNC 2009. IEEE, pages 1–6, april 2009.
 Abhik K. Das, Sriram Vishwanath, Syed Ali Jafar, and Athina Markopoulou.
Network coding for multiple unicasts: An interference alignment approach.
CoRR, abs/1008.0235, 2010.
 E. W. Dijkstra. A note on two problems in connexion with graphs. NU-
MERISCHE MATHEMATIK, 1(1):269–271, 1959.
 Matthias Ehrgott. Multicriteria Optimization. Springer, 2nd edition, 2005.
 J. El-Najjar, H.M.K. AlAzemi, and C. Assi. On the interplay between spatial
reuse and network coding in wireless networks. Wireless Communications,
IEEE Transactions on, 10(2):560 –569, february 2011.
 G. J. Foschini. Layered space-time architecture for wireless communication in
a fading environment when using multi-element antennas. Bell Labs Tech. J.,
pages 41–59, 1996.
 G. J. Foschini and M. J. Gans. On limits of wireless communications in a
fading environment when using multiple antennas. Wirel. Pers. Commun.,
 J. J. Garcia-Luna-Aceves, Hamid R. Sadjadpour, and Zheng Wang. Challenges:
Towards truly scalable ad hoc networks. MobiCom ’07. ACM, 2007.
 A. Ghosh, D.R. Wolter, J.G. Andrews, and R. Chen. Broadband wireless
access with wimax/802.16: current performance benchmarks and future potential.
Communications Magazine, IEEE, 43(2):129 –136, feb. 2005.
 A. Gkelias, F. Boccardi, C.H. Liu, and K.K. Leung. Mimo routing with qos
provisioning. In Wireless Pervasive Computing, 2008. ISWPC 2008. 3rd In-
ternational Symposium on, pages 46–50, May 2008.
 A. Gkelias and K. K. Leung. Wireless Mesh Networks Architecture and Pro-
tocols, chapter 11, pages 277–307. Springer, 2008.
 Andrea Goldsmith. Wireless Communications. Cambridge Univ. Press, 2006.
 Shyamnath Gollakota, Samuel David Perli, and Dina Katabi. Interference
alignment and cancellation. SIGCOMM Comput. Commun. Rev., 39(4):159–
 A. Grant. Joint decoding and channel estimation for linear mimo channels.
Wireless Communications and Networking Conference, 2000. WCNC. 2000
IEEE, 3:1009–1012 vol.3, 2000.
 Hongyu Gu and Chenyang Yang. Throughput analysis of peer-to-peer uwb
asynchronous cdma networks. In Vehicular Technology Conference, 2006.
VTC-2006 Fall. 2006 IEEE 64th, pages 1 –5, sept. 2006.
 V. C. Gungor, E. Natalizio, P. Pace, and S. Avallone. Wireless Mesh Networks
Architecture and Protocols, chapter 1. Springer, 2008.
 P. Gupta and P.R. Kumar. The capacity of wireless networks. Information
Theory, IEEE Transactions on, 46(2):388–404, Mar 2000.
 Piyush Gupta, Student Member, and P. R. Kumar. The capacity of wireless
networks. IEEE Transactions on Information Theory, 46:388–404, 2000.
 Daniel Halperin, Thomas Anderson, and DavidWetherall. Taking the sting out
of carrier sense: interference cancellation for wireless lans. In In Proceedings of
the 14th ACM international conference on Mobile computing and networking,
 B. Hamdaoui and P. Ramanathan. A cross-layer admission control framework
for wireless ad-hoc networks using multiple antennas. Wireless Communica-
tions, IEEE Trans. on, 6(11):4014–4024, Nov. 2007.
 Bechir Hamdaoui and Kang G. Shin. Characterization and analysis of multihop
wireless mimo network throughput. In MobiHoc '07. ACM, 2007.
 Frederick S. Hillier and Gerald J. Lieberman. Introduction to Operations Re-
search. McGraw-Hill, 2005.
 Honglin Hu, Jijun Luo, and Xiaodong Zhang. Wireless Mesh Networking,
Architectures, Protocols and Standards, chapter 11. Auerbach Publication,
 M. Hu and J. Zhang. Mimo ad hoc networks: Medium access control, saturation
throughput and optimal hop distance. Communications and Networks,
(Special Issue on Mobile Ad Hoc networks):317–330, December 2004.
 Wei Lan Huang, K. Letaief, and Ying Jun Zhang. Cross-layer multi-packet
reception based medium access control and resource allocation for spacetime
coded mimo/ofdm. Wireless Communications, IEEE Transactions on,
7(9):3372 –3384, september 2008.
 T.E. Hunter and A. Nosratinia. Cooperation diversity through coding. Infor-
mation Theory, 2002. Proceedings. 2002 IEEE International Symposium on,
page 220, 2002.
 T.E. Hunter and A. Nosratinia. Diversity through coded cooperation. Wireless
Communications, IEEE Transactions on, 5(2):283 – 289, feb. 2006.
 A. Iyer, C. Rosenberg, and A. Karnik. What is the right model for wireless
channel interference? Wireless Communications, IEEE Transactions on,
8(5):2662 –2671, may 2009.
 Rias Muhamed Jeffrey G Andrews, Arunabha Ghosh. Fundamentals of
WiMAX: understanding broadband wireless networking. Prentice Hall PTR,
 Y. Thomas Hou Jia Liu, Yi Shi. A tractable and accurate cross-layer model for
multi-hop mimo networks. In IEEE Proceedings INFOCOM, pages 2348–2356,
 Canming Jiang, Yi Shi, Y. Thomas Hou, Sastry Kompella Wenjing Lou, and
Scott F. Midkiff. Squeezing the most out of interference: An optimization
framework for joint interference exploitation and avoidance. In INFOCOM,
2012 Proceedings IEEE, page 9, april 2012.
 Bj¨orn Johansson, Pablo Soldati, and Mikael Johansson. Mathematical decomposition
techniques for distributed cross-layer optimization of data networks.
IEEE Journal on Selected Areas in Communications, pages 1535–1547, 2006.
 M. Johansson and L. Xiao. Cross-layer optimization of wireless networks using
nonlinear column generation. Wireless Communications, IEEE Transactions
on, 5(2):435–445, Feb. 2006.
 Nathaniel M. Jones, Brooke Shrader, and Eytan Modiano. optimal routing
and scheduling for a simple network coding scheme. In INFOCOM, 2012
Proceedings IEEE, page 9, april 2012.
 Sachin Katti, Shyamnath Gollakota, and Dina Katabi. Embracing wireless
interference: analog network coding. SIGCOMM Comput. Commun. Rev.,
37(4):397–408, August 2007.
 Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel M´edard, and
Jon Crowcroft. Xors in the air: practical wireless network coding. IEEE/ACM
Trans. Netw., 16(3):497–510, June 2008.
 Seung-Jun Kim, Xiaodong Wang, and M. Madihian. Cross-layer design of
wireless multihop backhaul networks with multiantenna beamforming. Mobile
Computing, IEEE Transactions on, 6(11):1259–1269, Nov. 2007.
 S. Kompella, J.E. Wieselthier, and A. Ephremides. Revisiting the optimal
scheduling problem. In Information Sciences and Systems, 2008. CISS 2008.
42nd Annual Conference on, pages 492 –497, march 2008.
 U.C. Kozat, I. Koutsopoulos, and L. Tassiulas. A framework for cross-layer
design of energy-efficient communication with qos provisioning in multi-hop
wireless networks. In INFOCOM 2004. Twenty-third AnnualJoint Conference
of the IEEE Computer and Communications Societies, volume 2, pages 1446
– 1456 vol.2, march 2004.
 J. Nicholas Laneman. Distributed space-time coded protocols for exploiting
cooperative diversity in wireless networks. IEEE Trans. Inform. Theory,
 J. Nicholas Laneman, David N. C. Tse, and Gregory W. Wornell. Cooperative
diversity in wireless networks: efficient protocols and outage behavior. IEEE
Trans. Inform. Theory, 50:3062–3080, 2004.
 J.N. Laneman, G.W. Wornell, and D.N.C. Tse. An efficient protocol for realizing
cooperative diversity in wireless networks. page 294, 2001.
 Markus Leitner and G¨unther R. Raidl. Lagrangian decomposition, metaheuristics,
and hybrid approaches for the design of the last mile in fiber optic networks.
In Hybrid Metaheuristics 2008, volume 5296 of LNCS, pages 158–174. Springer, 2008.
 Kai Li and Xiaodong Wang. Cross-layer design of wireless mesh networks with
network coding. Mobile Computing, IEEE Transactions on, 7(11):1363 –1373,
 Xin Li, Yimin Zhang, and Moeness G. Amin. Node throughput analysis of
decentralized wireless networks using multibeam antennas in multipath environments.
Wirel. Pers. Commun., 50(4):447–456, September 2009.
 Xiaojun Lin, N.B. Shroff, and R. Srikant. A tutorial on cross-layer optimization
in wireless networks. Selected Areas in Communications, IEEE Journal on,
24(8):1452 –1463, aug. 2006.
 Yih-Hao Lin, T. Javidi, R.L. Cruz, and L.B. Milstein. Distributed link scheduling,
power control and routing for multi-hop wireless mimo networks. ACSSC
'06., pages 122–126, 2006.
 Jia Liu, Y.T. Hou, Yi Shi, and H. Sherali. Cross-layer optimization for mimobased
wireless ad hoc networks: Routing, power allocation, and bandwidth
allocation. Selec.Areas in Comm.,IEEE Jour. on, Aug. 2008.
 Jia-Liang Lu, P. Vandenhove, Wei Shu, and Min-YouWu. Enhancing throughput
in wireless multi-hop network with multiple packet reception. In Commu-
nications (ICC), 2011 IEEE International Conference on, pages 1 –5, june
 Marco E. L¨ubbecke and Jacques Desrosiers. Selected topics in column generation.
Oper. Res., 53(6):1007–1023, November 2005.
 Chun-Pong Luk, Wing-Cheong Lau, and On-Ching Yue. An analysis of opportunistic routing in wireless mesh network. In Communications, 2008. ICC'08. IEEE International Conference on, pages 2877–2883, 2008.
 Chunbo Luo, Yu Gong, and Fu-Chun Zheng. Interference cancellation in twopath
successive relay system with network coding. In Personal Indoor and
Mobile Radio Communications (PIMRC), 2010 IEEE 21st International Sym-
posium on, pages 465 –469, sept. 2010.
 Jun Luo, C. Rosenberg, and A. Girard. Engineering wireless mesh networks:
Joint scheduling, routing, power control, and rate adaptation. Networking,
IEEE/ACM Transactions on, 18(5):1387 –1400, oct. 2010.
 Shaohe Lv, Xiaodong Wang, and Xingming Zhou. Scheduling under sinr
model in ad hoc networks with successive interference cancellation. In Global
Telecommunications Conference (GLOBECOM 2010), 2010 IEEE, pages 1 –5,
 Shaohe Lv, Weihua Zhuang, Xiaodong Wang, Chi Liu, and Xingming Zhou.
Maximizing capacity in the sinr model in wireless networks with successive
interference cancellation. In Communications (ICC), 2011 IEEE International
Conference on, pages 1 –6, june 2011.
 Shaohe Lv, Weihua Zhuang, Xiaodong Wang, and Xingming Zhou. Link
scheduling in wireless networks with successive interference cancellation. Com-
puter Networks, 55(13):2929 – 2941, 2011.
 Shaohe Lv, Weihua Zhuang, Xiaodong Wang, and Xingming Zhou. Scheduling
in wireless ad hoc networks with successive interference cancellation. In
INFOCOM, 2011 Proceedings IEEE, pages 1287 –1295, april 2011.
 George Mavrotas. Effective implementation of the ϵ-constraint method in
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access
Repository Staff Only: item control page