Resource Allocation and Scheduling in Wireless Mesh Networks by Keivan Ronasi B.Sc., Isfahan University of Technology, 2004 M.Sc., University of Tehran, 2007 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in The Faculty of Graduate Studies (Electrical and Computer Engineering) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) July 2012 c Keivan Ronasi, 2012 Abstract The unreliability of wireless mesh networks creates challenge in designing high performance wireless networks in terms of network throughput, end-to-end delay, and fairness provisioning. In this thesis, the goal is to improve the network performance in terms of these metrics. We explore several techniques such as multipath routing, channel coding, network coding, and interference alignment. We consider resource allocation both in terms of average data rate provisioning and scheduling policies in a time slot basis. First, we propose data rate and channel code rate allocation algorithms for networks with multiple paths to maximize the network throughput while all users can fairly exploit the network resources. We study the effect of adaptive and non-adaptive channel coding schemes. We also consider the end-to-end delay that each network flow experiences for data transmission. For that purpose, we formulate the problem of decreasing the end-to-end delay for network flows while improving the network throughput. Simulation results show that we can decrease the delay at the cost of a slight decrease in network throughput. We also formulate a data rate allocation problem in networks with network coding. Simulation results show that considering link reliabilities in the network coding design dramatically increases the network performance. Data rate allocation algorithms provide the average data rates at which the source must transmit data. They do not determine scheduling on a time slot basis. To address that, we consider transmission scheduling in wireless networks. We also compare the suggested algorithm with a centralized optimal data rate allocation algorithm to verify that ii Abstract our algorithm follows the optimal solution. Through simulations, we show that fairness provisioning leads to higher network performance. We show that the suggested algorithm outperforms the current algorithms in the literature in terms of both network throughput and fairness provisioning. Finally, we consider transmission scheduling in wireless multi-input multi-output (MIMO) systems. We formulate the problem of joint scheduling, interference alignment, and admission control in those networks and use Lyapunov stability theory to solve it. We also develop a heuristic approach to solve the problem in a semi-distributed manner. iii Preface Hereby, I declare that I am the first author of this thesis. Chapters 2-6 encompass work that has been published or is under review and they are co-authored by Dr. Vincent Wong and Dr. Sathish Gopalakrishnan who supervised me through this research. Chapters 2, 3, and 4 also include published work co-authored by Dr. Robert Schober and Dr. AmirHamed Mohsenian-Rad, who provided valuable comments for the works. The following publications are accomplished through this research. Journal Papers, Published • Keivan Ronasi, Amir-Hamed Mohsenian-Rad, Vincent W.S. Wong, Sathish Gopalakrishnan, and Robert Schober, “Delay-Throughput Enhancement in Wireless Networks With Multipath Routing and Channel Coding,” IEEE Trans. on Vehicular Technology, vol. 60, no. 3, pp. 1116-1123, Mar. 2011. • Keivan Ronasi, Amir-Hamed Mohsenian-Rad, Vincent W.S. Wong, Sathish Gopalakrishnan, and Robert Schober, “Optimal Data Transmission and Channel Code Rate Allocation in Multipath Wireless Networks,” IEEE Trans. on Vehicular Technology, vol. 60, no. 8, pp. 3963-3974, Oct. 2011. • Keivan Ronasi, Vincent W.S. Wong, and Sathish Gopalakrishnan, “Distributed Scheduling in Multihop Wireless Networks with Maxmin Fairness Provisioning,” IEEE Trans. on Wireless Communications, vol. 11, no. 5, pp. 1753-1763, May 2012. iv Preface Conference Papers, Published • Keivan Ronasi, Sathish Gopalakrishnan, and Vincent W.S. Wong, “Flow Starvation Mitigation for Wireless Mesh Networks,” in Proc. of IEEE Wireless Communications and Networking Conference (WCNC), Budapest, Hungary, April 2009. • Keivan Ronasi, Amir-Hamed Mohsenian-Rad, Vincent W.S. Wong, Sathish Gopalakrishnan, and Robert Schober, “Reliability-Based Rate Allocation in Wireless InterSession Network Coding Systems,” in Proc. of IEEE Global Communications Conference (Globecom), Honolulu, HI, December 2009. • Keivan Ronasi, Amir-Hamed Mohsenian-Rad, Vincent W.S. Wong, Sathish Gopalakrishnan, and Robert Schober, “Optimal Data Transmission and Channel Code Rate Allocation in Multi-Path Wireless Networks,” in Proc. of IEEE International Conference on Communications (ICC), Kyoto, Japan, June 2011. v Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi List of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xviii 1 Introduction 1.1 1.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Performance Attributes 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.2 Reliability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Techniques 1.2.1 Network Utility Maximization . . . . . . . . . . . . . . . . . . . . 5 1.2.2 Network Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.3 Channel Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.4 Multipath Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 vi Table of Contents 1.2.5 . . . . . . . . . . . . . . . . . . . . . . . . 8 Mathematical Background . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3.1 Convex Optimization . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3.2 Geometric Programming . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.3 Non-linear Mixed Integer Programming . . . . . . . . . . . . . . . 13 1.3.4 Generalized Benders Decomposition (GBD) . . . . . . . . . . . . . 14 1.4 Contributions and Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.5 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2 Optimal Data Transmission and Channel Code Rate Allocation . . . . 21 1.3 Interference Alignment 2.1 Introduction 2.2 System Model And Problem Formulation 2.3 2.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 . . . . . . . . . . . . . . . . . . 24 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2.1 System Model 2.2.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . 28 Optimal Transmission Rate and Channel Code Rate Allocation . . . . . . 29 2.3.1 Adaptive Channel Coding . . . . . . . . . . . . . . . . . . . . . . . 29 2.3.2 Non-adaptive Channel Coding . . . . . . . . . . . . . . . . . . . . 34 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.4.1 Multipath vs. Single-path Routing . . . . . . . . . . . . . . . . . . 37 2.4.2 Channel Coding vs. No Channel Coding . . . . . . . . . . . . . . . 38 2.4.3 Convergence Properties of Algorithm 2.1 . . . . . . . . . . . . . . . 39 2.4.4 Impact of Various Design and System Parameters . . . . . . . . . . 41 2.4.5 Adaptive vs. Non-adaptive Channel Coding . . . . . . . . . . . . . 42 2.4.6 The Effect of Dynamic Changes on the System Performance . . . . 45 2.4.7 The Effect of Mobility on the System Performance . . . . . . . . . 45 2.4.8 Impact of Fading . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 vii Table of Contents 2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Delay-Throughput Enhancement 49 . . . . . . . . . . . . . . . . . . . . . . . 51 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.1 Introduction 3.2 System Model 3.3 Delay-aware Optimal Data Rate and Coding Rate Allocation 3.4 Numerical Results 3.5 . . . . . . . 58 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4 Reliability-based Rate Allocation with Inter-session Network Coding 4.1 Introduction 4.2 System Model 69 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.2.1 Pair-wise Inter-session Network Coding . . . . . . . . . . . . . . . 71 4.2.2 Rate Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.2.3 Interference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.2.4 Link Failure 74 4.2.5 Network Utility Maximization Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.3 End-to-End Reliability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.4 Reliability-based Rate Allocation . . . . . . . . . . . . . . . . . . . . . . . 78 4.5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 5 Distributed Scheduling with Maxmin Fairness Provisioning . . . . . . 88 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5.1 Introduction 5.2 System Model 5.3 Decentralized and Stable Scheduling 5.4 Geometric Programming Formulation . . . . . . . . . . . . . . . . . . . . . 95 . . . . . . . . . . . . . . . . . . . . 106 viii Table of Contents 5.5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 6 Scheduling and Interference Alignment for MIMO Wireless Systems . 118 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 6.2 System Model 6.3 Problem Formulation 6.4 Scheduling and Interference Alignment Algorithm . . . . . . . . . . . . . . 129 6.5 Semi-Distributed Scheduling and Interference Alignment Algorithm . . . . 137 6.6 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 6.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 7 Conclusions and Future Work 7.1 Research Contributions 7.2 Suggestions for Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 146 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 . . . . . . . . . . . . . . . . . . . . . . . . . 148 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 ix List of Tables 3.1 The trade-off between the maximum delay and the minimum throughput in the network when channel coding is not being used. . . . . . . . . . . . . . 67 x List of Figures 2.1 An example downtown area with 25 access points (forming a wireless mesh infrastructure). The access point at the center serves as the gateway. There are 10 vehicles in the system, each one uses the nearest access point to connect to the Internet. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 27 A sample network topology with 20 nodes randomly located in a 5 × 5 grid. The network includes five sessions: 1 → 16, 3 → 13, 2 → 8, 14 → 17, and 6 → 20. There are 4, 2, 2, 1, and 3 routing paths available for these sessions, respectively. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 37 Comparison between the performance of adaptive channel coding in singlepath and multipath routing networks in terms of the achieved normalized minimum throughout. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 38 Comparison between the performance of multipath routing with and without per-link channel coding in terms of the achieved normalized minimum throughput among the end-to-end sessions, when the scale of the network increases and the number of nodes varies from 6 to 42. . . . . . . . . . . . 2.5 Convergence of Algorithm 2.1 with respect to solving problem (2.8). We can see that the algorithm converges after 50 iterations. . . . . . . . . . . . 2.6 40 40 The impact of the choice of design parameter Ne in approximation (2.12). The average optimality error decreases as Ne increases. It becomes almost zero for Ne > 12. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 xi List of Figures 2.7 The impact of choosing different coding block lengths T on the network performance for three different random topologies. We observe that the performance improves when the coding block length increases. . . . . . . . 43 2.8 Comparison between adaptive and non-adaptive channel coding. . . . . . . 43 2.9 Optimal non-adaptive code rate versus adaptive code rate distribution among all wireless links of the network topology in Fig. 2.2. . . . . . . . . . . . . 44 2.10 Convergence speed for Algorithm 2.1 in presence of dynamic changes in the network. We compare two cases where the previous solution is exploited and the case where the previous solution is ignored. Every 100 time slots: (a) five links are added and five links are removed, (b) a new pair of sourcedestination nodes is added, (c) a pair of source-destination node is removed, (d) a random pair is added and another random pair is removed. . . . . . . 46 2.11 The convergence of the algorithm is shown for different speeds. Recalculations occur every 5 seconds if needed. . . . . . . . . . . . . . . . . . . . . . 47 2.12 Performance of the algorithm is studied in the downtown area of Fig. 2.1 when vehicles move with different speeds. . . . . . . . . . . . . . . . . . . . 48 2.13 Performance trend in a fading channel for 50 channel snapshots. . . . . . . 49 3.1 A sample topology with five unicast multipath data sessions. Data sessions are (2 → 15), (7 → 18), (9 → 20), (12 → 23), and (3 → 25). These sessions have 6, 1, 2, 2, and 4 available paths, respectively. 3.2 . . . . . . . . . . . . . . 54 The average delay decreases as its importance weight in the objective function increases. Delay values are normalized over the corresponding values for which w = 0. We observe a decrease of almost 58% when w = 0.5. . . . 64 xii List of Figures 3.3 The normalized maximum delay among the users in the network decreases as the corresponding importance weight in the objective function increases. Delay values are normalized over the values corresponding to w = 0. We observe almost 37% decrease in the maximum delay in the network when w reaches 0.5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 65 The trade-off between the maximum delay and the minimum throughput in the network. We may move on the curve by tuning w, the delay importance weight. Delay and throughput are normalized over their corresponding values at w = 0. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Fairness index is shown for both problem (3.8) (aggregate utility maximization) and problem (3.9) (maxmin fairness). . . . . . . . . . . . . . . . . . . 3.6 66 66 Average maximum delay is shown when there is no guarantee on the maximum delay, there is a guarantee of 10 ms, and 20 ms. Since the guarantee is imposed on the upper bound of the delay, the delay may not reach the guaranteed value. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 67 (a) An example directed acyclic network graph with 6 nodes and 7 links. One data session exists between s1 and t1 and another one exists between s2 and t2 . (b) The corresponding (undirected) contention graph. . . . . . . 4.2 72 Aggregate network throughput in all 10 simulated topologies with and without reliability consideration when the utility functions are selected as Ui (x) = x for all i ∈ S. Taking reliability information into account increases the throughput by 36.2% on average, among all ten scenarios. . . . . . . . . . 84 xiii List of Figures 4.3 Comparison between our algorithm (with reliability consideration) and the rate allocation algorithm which does not use link reliability information: (a) Maximizing the aggregate network throughput. (b) Maximizing the aggregate network utility when the utility functions are logarithmic. . . . . 4.4 The impact of changing the utility parameter ψ on the achieved aggregate network utility with and without reliability consideration. . . . . . . . . . . 5.1 85 86 (a) Path k of flow f from node sf to node df which uses node n as a relay node is shown. It is shown that solid link 1 is active (µf1 k (t) = 1) while dotted links 2 and 3 are not active (µf2 k (t) = µf3 k (t) = 0) in that particular time slot t. Note that links 1 and 2 belong to the mentioned path (af1 k = af2 k = 1) but link 3 does not (af3 k = 0). (b) A relay node n is shown with its input link i and its output link o corresponding to the k th path of flow f . The corresponding packets are stored in Qfnk before they are sent. . . . . . . . . 5.2 93 The performance of the DisF algorithm is compared with the solution of centralized geometric programming problem. Each point represents the average performance obtained over 50 random topologies. The DisF algorithm follows the centralized approach as the number of flows increases. . . . . . 111 5.3 In a sample topology, fairness is provided under the DisF algorithm while some flows starve under the DisA algorithm that does not consider fairness. 112 5.4 The performance of DisF and DisA algorithms in regard of fairness provisioning. Each point represents the average value of the fairness index over 50 random topologies. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 5.5 The tradeoff between minimum throughput in the network (a) and aggregate throughput in the network (b) is shown under both DisF and DisA algorithms.113 xiv List of Figures 5.6 Performance of the network with channel coding is compared with the case in which channel coding is not being used. . . . . . . . . . . . . . . . . . . 114 5.7 The effect of increasing parameter V is shown on the minimum throughput (a). This is at the expense of increasing the congestion in the network (b). 5.8 115 DisF algorithm is compared with the utility-based approach in terms of fairness provisioning using Jain’s fairness index. It is shown that for large values of β, the utility-based approach has a better performance comparing with DisF algorithm. This is at the cost of a decrease in the minimum throughput. (Fig. 5.9) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 5.9 DisF algorithm is compared with the utility-based approach when different number of flows are using the network. It is shown that increasing β is at the cost of decreasing the minimum throughput. . . . . . . . . . . . . . . . 116 6.1 Network topology for wireless MIMO system with K users. . . . . . . . . . 121 6.2 Convergence of SIA algorithm is shown in one time slot when there are 5 and 10 users in the network. . . . . . . . . . . . . . . . . . . . . . . . . . . 141 6.3 The optimal value of problem (6.20) changes for both the SIA and SDSIA algorithms when interference leakage threshold ǫ and receiver threshold Pth change. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 6.4 The number of transmissions per user is shown when the number of users K increases. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 6.5 The average per user achievable data rate is shown when the number of users increases from 1 to 20. . . . . . . . . . . . . . . . . . . . . . . . . . . 144 xv List of Abbreviations ACK Acknowledgement AODV-BR Ad hoc On-demand Distance Vector with Backup Routing BEC Binary Erasure Channel BPSK Binary Phase Shift Keying CSMA Carrier Sense Multiple Access CSO Channel State Only DisA Distributed Aggregate DisF Distributed Fair DoF Degrees of Freedom FTP File Transfer Protocol GBD Generalized Benders Decomposition GMS Greedy Maximal Scheduling GP Geometric Programming HTTP Hypertext Transfer Protocol IA Interference Alignment LAN Local Area Network MAC Medium Access Control MAODV Multipath Ad hoc On-demand Distance Vector MIMO Multiple-Input Multiple-Output xvi List of Abbreviations MIP Mixed Integer Programming MP-DSR Multi-Path Dynamic Source Routing MSR Multipath Source Routing NUM Network Utility Maximization OA Outer Approximation SIA Scheduling and Interference Alignment P2P Peer-to-peer QoS Quality of Service SDSIA Semi-Distributed Scheduling and Interference Alignment SMR Split Multipath Routing SNR Signal-to-Noise Ratio TDMA Time Division Multiple Access WLAN Wireless Local Area Network WMN Wireless Mesh Network xvii Acknowledgments First of all, I want to express my deepest sense of gratitude to my supervisors Dr. Vincent Wong and Dr. Sathish Gopalakrishnan without whom this research would not be possible. I want to thank them for their continuous support, patience, technical and non-technical guidance that helped me accomplish this research. I also want to thank them for their understanding of the conditions and problems that I was involved with as a new international student. I want to declare my special thanks to Dr. Robert Schober and Dr. Amir Hamed Mohsenian-Rad for their enormous help, advice, and comments through my research. It was not possible to accomplish some parts without their very helpful advice. I am thankful to my friends Ahmad Ashouri, Saloome Motavas, Behnam Faraji, Sahar Edelkhani, Pedram Samadi, Vahid Shahmansouri, and Ehsan Vahedi for their always being supportive and accountable. I also want to thank Man Hon, Nina, Nazanin, Azadeh, Nassim, Anahita, Sadaf, Helia, Payman, Morteza, Ali, and all my other friends that definitely I cannot name them all here. Most importantly, I feel indebted to my great family, my father, my mother and my sister for their everlasting love, support, and protectivity not only in these last four years but also throughout my entire life. This work was supported by the Natural Sciences and Engineering Research Council (NSERC) of Canada. xviii Chapter 1 Introduction Recent technological advances in wireless communications, digital electronics, and radio frequency systems have placed wireless networks at the forefront of today’s data transmission systems. Wireless mesh networks are wireless systems in which no central infrastructure exists. In these networks, users (mesh nodes) send and receive data to and from the gateway(s) through possibly multiple hops. Having no central structure, mesh nodes are responsible for routing and relaying data to the destination nodes. This is in contrary to the existence of routers and access points in wired and infrastructure based wireless networks. Since network users are responsible for routing and relaying in the network wireless mesh networks are scalable. This means that increasing the number of users (mesh nodes) will not only maintain the performance of the network, but it may also improve it. That is because a higher number of nodes (resources) are available for data transmission. Moreover, because of not relying on infrastructure, wireless mesh networks are inexpensive and easy to deploy. This makes these networks suitable for certain applications such as disaster recovery support, urgent applications, and military missions. Wireless nature and the decentralized structure of the wireless mesh networks makes them exposed to unreliability. This means that at each instant of time, a packet may be corrupted because of node outages, weather conditions, and environmental obstacles. Unreliability degrades the performance of the network especially in applications of high quality of service (QoS) requirements such as multimedia and realtime applications. An1 Chapter 1. Introduction other issue in wireless networks is interference. In the absence of a central node managing data transmissions in the network, each node needs to use a distributed algorithm to schedule data transmissions such that no interference occurs among the wireless channels. Fairness provisioning, admission control, and end-to-end delay are other issues that affect the performance of wireless mesh networks. In this thesis, we study the performance improvement in wireless mesh networks. We develop rate allocation approaches, flow control algorithms, and scheduling policies such that the performance of the network in terms of network throughput and end-to-end delay improves while data transmissions remain reliable. We also consider fairness provisioning while achieving our goals. To this end, we use several techniques such as multipath routing, channel coding, network coding, and interference alignment. In this chapter, we first discuss the fairness and reliability in wireless networks. Then, we briefly summarize network utility maximization, network coding, channel coding, multipath routing, and interference alignment. After that, we describe the mathematical background that are used in this thesis. Finally, we itemize our contributions and describe the thesis organization at the end of this chapter. 1.1 1.1.1 Performance Attributes Fairness One important measure for network performance is fairness. Fairness provisioning in the network allows all users enjoy a fair portion of network resources according to their utility functions. Without considering fairness in a wireless network, some users may starve while the others over utilize the resources in the network. Starvation may have its origins in different layers such as medium access control (MAC) 2 Chapter 1. Introduction layer and transport layer. Shi et al. considered the starvation caused with a one-hop transmission for a two-hop transmission in [1]. They especially considered the case in which two users compete for the wireless channel with intially equal contention windows. After several failures when their contention windows are large enough, one of them gets successful in transmission and therefore it resets its contention window to the minimum default size. However, the contention window of the other one remains large and this leads the previously successful user to send its data more aggressively and makes the other one starve. Another origin of starvation is unfair data rate allocation. When the goal is maximizing the aggregate throughput of the network, sometimes it is promising to devote network resources completely to some particular users. This leads to starvation. One of the goals in this thesis is to avoid starvation due to data rate allocation and transmission scheduling. As an appropriate quantitative measure of network performance in terms of fairness provisioning, we use Jain’s fairness index [2]. Fairness provisioning in wireless networks has been considered [3–10]. Lin and Shroff considered the impact of imperfect scheduling on performance of the network [3]. Proportional fairness is provided in single hop wireless networks using token counter mechanisms [4]. Fairness provisioning is also studied using back-pressure combined with random access algorithms [5]. Fairness is provided in the cellular networks, where there is only one transmitter and all transmissions are one hop [6]. A distributed fair carrier sense multiple access (CSMA) algorithm is provided in [11] and its convergence under several practical assumptions is considered [12]. Fair power allocation for cooperative wireless networks is also considered [13]. 3 Chapter 1. Introduction 1.1.2 Reliability Unlike wired networks, links in wireless networks can be unreliable and prone to transmission error due to channel imperfections, background noise, environmental obstacles, weather conditions, and user mobility [14]. Unreliable links can degrade network performance particularly for applications with tight QoS requirements such as voice-over-IP and video streaming [15]. Therefore, it is crucial to develop efficient strategies in order to improve the reliability of data transmission in wireless networks [16]. The ability of a network to overcome failures can be characterized through three important measures [17]: First, the network ability to perform its designated tasks under certain conditions with guaranteed performance. Secondly, the ability of network to perform its tasks at any instance of time, and finally network’s ability to survive some network failures. In this thesis, we improve the reliability of the network as a combination of the three measures above. To study the reliability problem in wireless networks, reliability can be modeled and analyzed as a utility function over the nodes participating in the network. QoS requirements and constraints need to be jointly considered while optimizing network behavior. A good measure for reliability can be the fraction of packets that are successfully received by the receiver. Another measure may be the mean value of transmission efforts for each successful transmission [17, 18]. Markov process analysis is used to model and analyze the end-to-end data transmission in a wireless network, and the tradeoff between delay and reliability is investigated [19]. Data transmission reliability in wireless mesh networks is summarized [20]. Varshney et al. [21] considered reliability and survivability in infrastructure-oriented wireless networks and provided some reliability measures and modeling. Different approaches are used to make wireless networks more reliable. They include 4 Chapter 1. Introduction rate allocation [22, 23], channel coding [22], network coding [18, 24], and multipath routing [25–27]. Many rate allocation approaches are based on variations of the network utility maximization [28–32]. 1.2 1.2.1 Techniques Network Utility Maximization Following the work by Kelly et al. [33], network utility maximization (NUM) has been widely used as a framework to systematically devise resource allocation strategies that can enhance the network performance subject to various capacity and QoS constraints [22, 34–36]. Most resource allocation problems can be formulated as NUM problems. The utility function represents an objective that is to be maximized and the constraints model the different underlying network characteristics. The NUM approach has been applied in different problems, including energy minimization [37], congestion control [38], joint throughput maximization and power control [39], joint congestion and power control [34], MAC [40, 41] joint congestion and MAC control [35], and cross-layer optimization [42]. Other rate allocation approaches are also considered. In [43], a rate control protocol with rate mismatch and queue size feedback has been considered and a control theoretic analysis of the system has been provided. However, rate allocation approaches do not automatically result in a packet scheduling and transmission policy. 1.2.2 Network Coding One approach to increase the network capacity while improving the reliability of the network is network coding. Through network coding, each intermediate node combines the 5 Chapter 1. Introduction received codewords from different neighbor nodes and encodes them into new codewords. The combined code words are then sent to the next hop on the path. This continues until the destination node receives enough encoded codewords that it can decode them and obtain the original packets. Network coding can be performed by jointly encoding multiple packets either from the same source or from different sources. The former is called intra-session network coding [44] while the latter is called inter-session network coding [45]. Following the seminal paper by Ahlswede et al. [44], a rich body of work has focused on developing techniques to improve network performance using network coding. Reliability in intra-session network coding is studied by Lun et al. in [46]. Network coding has been shown as a promising approach in communication networking, particularly for maximizing capacity in wireless networks [47]. Other network coding design objectives include maximizing network lifetime [48], minimizing energy consumption [49], and maximizing the network throughput [50]. 1.2.3 Channel Coding Channel coding (cf. [22, 51]) is commonly used as a tool to leverage reliable transmissions over lossy wireless links. With channel coding, the transmitter node of each link encodes the transmitted packets by adding auxiliary or redundant bits, which can increase the distance among the codewords and decrease the packet error probability. The higher the number of redundant bits is, the lower is the probability that the packet is corrupted in the channel such that it cannot be decoded at the receiver. If the number of extra bits is the same across all links, then channel coding is non-adaptive. On the other hand, if we change the amount of redundant bits for each link based on its current state, then channel coding is adaptive. Adaptive channel coding may result in better performance compared to 6 Chapter 1. Introduction non-adaptive channel coding; however, it entails a higher complexity. In general, channel coding usually introduces a tradeoff between reliability and data transmission rate. In fact, by changing the code rate, i.e., the ratio of data bits to data plus redundant bits, we can change the data rate at which the information is transmitted over each wireless link. In particular, the code rate can be decreased in order to improve (reduce) the probability of error at the cost of having lower data rates. Similarly, we can increase the code rate to increase the transmission data rate, but at the cost of increasing the probability of error. Adaptive channel coding has been used in [22] to enhance the network reliability, when single-path routing is being used. The rate-reliability tradeoff introduced through channel coding is studied in [22, 36, 51, 52]. Channel coding schemes fall into two main types: block codes and convolutional codes. In convolutional codes, the encoded packets do not depend only to the latest data packets but also to the past encoded data. However, in block codes each codeword depends only to a number of latest data bits. Golay codes are an example for block codes. 1.2.4 Multipath Routing Multipath routing can be used to compensate for the data rate reduction due to channel coding. This is done by distributing the load over multiple routing paths. Multipath routing can provide fault tolerance against link failures and also achieve load balancing in order to better utilize the available network capacity [53–55]. Multipath routing brings two important advantages. One is that data can be sent from the source node with higher data rate than single-path routing because multiple paths (more resources) are being used simultaneously between the source node and the destination node. This gives the opportunity of using the network resources more efficiently. Second, having multiple paths available, we can push higher data transmission rate to the paths with higher reliability instead of 7 Chapter 1. Introduction having to use vulnerable paths with high probability of failure. This improves the reliability of the network by adjusting the data rates on different routing paths according to the state of wireless channels and other data flows in the network. The improvements lead to reducing network congestion, increasing throughput, and also higher energy efficiency [56]. The impact of multipath routing on energy consumption is examined in [57]. The effectiveness of multiple paths in meeting delay constraints is also studied in [58]. Multipath routing has been studied in wired networks [59] and wireless networks [25, 60] scenarios. Many standard protocols have been introduced for multipath routing in wireless networks such as ad hoc on-demand distance vector with backup routing (AODV-BR) [61], multipath source routing (MSR) [62], multipath dynamic source routing (MP-DSR) [63], split multipath routing (SMR) [64], multipath ad hoc on-demand distance vector (MAODV) [65], and the work in [66]. 1.2.5 Interference Alignment Multiple-input multiple-output (MIMO) wireless systems are wireless networks in which transmitters and receivers may have more than one antenna. They offer the possibility of spatial multiplexing of data streams in addition to time and frequency multiplexing. Spatial multiplexing leads to capacity increase linear to min(M, N), where M and N are the number of transmitter and receiver antennas, respectively [67]. The challenge in designing such MIMO systems, however, is in dealing with interference from concurrent signal transmissions. In such systems, wireless interference shows up among different sender antennas at each receiver. Interference alignment is among the several techniques which has been recently used to overcome this problem. When the interference is strong, the interfering signal can be decoded as well as the desired signal [68]. This may be at the cost of degradation in the users’ sending rates. On the 8 Chapter 1. Introduction other hand, in case the interference is very weak, it can be treated as noise. More recently, interference alignment [68] has been suggested for the cases when the strength of interference is comparable to the strength of the desired signal. Interference alignment techniques involve the use of suitable encoding and decoding matrices, at the transmitter and receiver respectively, such that at each receiver the interference caused by all undesired transmitters is projected onto a separate interference subspace. This permits the receiver to easily extract the desired signal from the corresponding interference-free subspace. Cadambe and Jafar have shown that while the per-user sum-rate for an K-user interference channel without interference alignment is 1 K log(SNR) + O(SNR), where SNR is the signal-to-noise ratio, the sum-rate per-user can be increased to 1 2 log(SNR) + O(SNR) with interference alignment [68]. Most of the work in the field of interference alignment is related to determining the maximum possible degrees of freedom (DoF) as well as studying its feasibility and achievability through finding optimal encoding and decoding matrices in a (M, N) system with K users (where K is as small as 2, 3) such that the interference is minimum at undesired receivers. The effectiveness of interference alignment in fully connected wireless networks with more than two users is considered [68, 69]. While global knowledge of channels is required in the work by Cadambe et al. [68], Gomadam et al. [70] provide a distributed approach using the reciprocity of wireless networks to make the local channel knowledge adequate. The achievability of high DoF in wireless networks when instantaneous channel state information is not available is studied [71]. The feasibility of interference alignment in MIMO systems has been considered in [72, 73] by relating the problem to the problem of determining the solvability of a multivariate polynomial system. In addition to interference alignment which aims at minimizing 9 Chapter 1. Introduction the interference strength projected outside the interference subspace, the work in [74] also minimizes the signal strength that is spilled inside the interference subspace. Interference alignment and cancellation in MIMO systems is shown in [75] to almost double the throughput of MIMO based wireless local area networks (WLANs). Interference alignment with the goal of achieving the maximum sum-rate has been considered in MIMO [76] and cognitive MIMO systems [77]. Interference alignment techniques have also been exploited for downlink cellular systems where channel state information exchange is not required across base stations of different cells [78]. Interference alignment has also been used to model and solve other problems such as network coding [79, 80]. 1.3 Mathematical Background In this section, we provide a brief discussion on mathematical background that is needed in this thesis. 1.3.1 Convex Optimization Before presenting the standard form of convex optimization problems [81], we first introduce some related concepts. Set X is convex if for any two points xi , xj ∈ X , the line segment connecting xi to xj is in set X as well. That is, we have θxi + (1 − θ)xj ∈ X for θ ∈ [0, 1]. Function f (x) : Rn → R is convex if dom f is a convex set and we have f (θxi + (1 − θ)xj ) ≤ θf (xi ) + (1 − θ)f (xj ) for θ ∈ [0, 1]. 10 Chapter 1. Introduction A convex optimization problem has the following standard form. minimize f0 (x) subject to fi (x) ≤ 0, i = 1, . . . , m, (1.1) hi (x) = 0, i = 1, . . . , p, where fi (x), i = 0, . . . , m, are convex functions, and hi (x) = aTi x − bi , i = 1, . . . , p, are affine functions. Problem (1.1) addresses the problem of finding the optimization variable x ∈ Rn such that • inequality constraints are satisfied. That is, fi (x) : Rn → R is less than or equal to zero for all i = 1, . . . , m, • equality constraints are satisfied. That is, aTi x = bi , for all i = 1, . . . , p, and • the objective function f0 (x) : Rn → R obtains its minimum value among all x ∈ Rn that satisfy the above constraints. A convex optimization problem can be solved through the dual method. The basic idea in the dual method is combining the weighted equality and inequality conditions with the objective function in a new function called Lagrangian. The Lagrangian of problem (1.1) is as follows. L(x, λ, ν) = f0 (x) + m i=1 λi fi (x) + p i=1 νi hi (x). (1.2) We refer to λ and ν as Lagrangian multipliers corresponding to inequality and equality constraints, respectively. We define the dual function g(λ, ν) : Rm × Rp → R as the infimum value of the Lagrangian function over x ∈ X , that is g(λ, ν) = inf x∈X L(x, λ, ν). (1.3) 11 Chapter 1. Introduction Note that for any λ 0, ν, g(λ, ν) yields a lower bound for the optimal value of problem (1.1). As opposed to primal problem (1.1), consider Lagrangian dual problem as follows. maximize g(λ, ν) subject to λ (1.4) 0. The optimal value of problem (1.4) yields the best lower bound for the optimal value of problem (1.1). Under the strong duality conditions, this lower bound equals to the optimal value of the primal problem. Note that for convex optimization problems, Slater’s condition is enough for strong duality [81, p. 226]. Slater’s condition requires the existence of at least one feasible point inside the feasible set of the primal problem. 1.3.2 Geometric Programming Geometric programming (GP) is a type of non-convex optimization problems that can be converted to convex optimization problem and be solved accordingly. We first dea(1) a(2) fine a monomial function m(x) : Rn++ → R as dx1 x2 a(n) . . . xn , where d > 0, and a(i) ∈ R, i = 1, 2, . . . , n. A posynomial is the summation of K monomials as in p(x) = K k=1 a (1) ak (2) x2 dk x1k a (n) . . . xnk . Now, we can introduce the standard form of GP problems [82] as minimize f0 (x) subject to fi (x) ≤ 1, i = 1, . . . , m, (1.5) hi (x) = 1, i = 1, . . . , p, where fi (x) = i i Ki i ak (1) ak (2) x2 k=1 dk x1 ai (1) ai (2) x2 hi (x) = di x1 ai (n) . . . xn ai (n) . . . xnk are posynomials for any i = 0, . . . , m, and are monomials for each i = 1, . . . , p. GP is not convex in its standard form. However, it can be converted to a convex problem by the logarithmic 12 Chapter 1. Introduction change of its all variables. Having yi = log xi , we have minimize K0 k=1 exp(b0k + a0k (1)y1 + . . . + a0k (n)yn ) subject to Ki k=1 exp(bik + aik (1)y1 + . . . + aik (n)yn ) ≤ 1, i = 1, . . . , m, exp(bi + ai (1)y1 + . . . + ai (n)yn ) = 1, (1.6) i = 1, . . . , p, where bik = log dik , for any i = 1 . . . m, k = 1, . . . , K i . We also have bi = log di , for any i = 1, . . . , p. Considering that the logarithmic function is an increasing function, we can take the logarithm of the objective function as well as the constraints and obtain a convex optimization problem. This is due to the fact that the log-sum-exp function is convex [83]. Therefore a GP can easily be solved by using the techniques to tackle convex optimization problems. 1.3.3 Non-linear Mixed Integer Programming Sometimes it is not possible to accept solutions in which some optimization variables are not integers. This happens for example when we are seeking for the optimal number of people working in a particular section or the optimal number of wireless links which are active in one particular time slot. Another important instance of this is in scheduling problems in which the scheduling variables must be equal to either 0 or 1, which corresponds to whether a link is off or on. Such problems must be formulated as integer programming problems. Note that in case there are both integer and non-integer variables in the problem, it is called a mixed-integer programming problem. The standard form of a mixed integer linear 13 Chapter 1. Introduction programming problem is as follows [84]. minimize N n=1 cn xn subject to N n=1 amn xn ≤ bm , m = 1, . . . , M, xn ≥ 0, n = 1, . . . , N, xi is integer, i ∈ I, (1.7) where I is a subset of the set of variables {n = 1, . . . , N}. In contrast with linear programming, it is not straightforward to solve integer programming problems when they are not linear, that is there exist non-linear functions of optimization variables as the objective function and/or constraints. Some methods are suggested for solving non-linear (mixed) integer programming problems such as Generalized Benders Decomposition (GBD) and Outer Approximation (OA) approaches. In the next section, we introduce the GBD method. 1.3.4 Generalized Benders Decomposition (GBD) Consider the following non-linear mixed integer programming problem. minimize x,y f (x, y) subject to hi (x, y) = 0, gi (x, y) ≤ 0, i = 1, . . . , m, i = 1, . . . , p, (1.8) x ∈ X ⊆ Rn , y ∈ Y = {0, 1}q , where X is a nonempty, and convex set, hi : Rn × Rq → R for i = 1, . . . , m, is a linear function for each fixed y ∈ Y , and f : Rn × Rq → R and gi : Rn × Rq → R for i = 1, . . . , p, are convex functions for each fixed y ∈ Y . We have also set Zy = {z = (z1 , . . . , zp ) ∈ 14 Chapter 1. Introduction Rp : hi (x, y) = 0, gj (x, y) ≤ zj , i = 1, . . . , m, j = 1, . . . , p, for some x ∈ X} is a closed set. Moreover, for each feasible y ∈ Y , we have either problem (1.8) has a finite solution and optimal Lagrangian multipliers vector, or problem (1.8) is unbounded. The GBD method [84] is an iterative algorithm. At each iteration, we formulate two problems: a primal problem, which yields an upper bound on the optimal value, and a master problem that yields a lower bound on the optimal value. The primal problem is formulated by fixing the integer variables in some particular point and solving problem (1.8) in that point. Consider the following primal problem at the k th iteration. minimize x f (x, yk ) subject to hi (x, yk ) = 0, i = 1, . . . , m, (1.9) gi (x, yk ) ≤ 0, i = 1, . . . , p, x ∈ X ⊆ Rn , where yk is a feasible point in set Y . Clearly, since the integer variables are fixed, the optimal value of problem (1.8) is always equal or better (smaller) than the optimal value of problem (1.9) and therefore, the primal problem provides an upper bound for the optimal value. In case problem (1.9) is infeasible for y = yk , we formulate a feasibility problem. Consider the l1 -minimization problem at iteration k. minimize x, β 0 p i=1 βi subject to hi (x, yk ) = 0, i = 1, . . . , m, (1.10) k gi (x, y ) ≤ βi , i = 1, . . . , p, x ∈ X ⊆ Rn . Let M and M′ denote the set of all iterations k such that the primal problems are feasible and infeasible, respectively. Using the solutions to the primal problems (1.9) and 15 Chapter 1. Introduction (1.10) in all previous iterations and the information on Lagrange multipliers, we formulate the master problem as follows: minimize µ,y µ subject to µ ≥ L1 (xk , y, λk , ν k ), ∀ k ∈ M, k k k (1.11) ′ 0 ≥ L2 (x , y, λ , ν ), ∀ k ∈ M , y ∈ Y = {0, 1}q , where L1 (x, y, λ, ν) = f (x, y) + λT h(x, y) + ν T g(x, y) and L2 (x, y, λ, ν) = λT h(x, y) + ν T g(x, y). The GBD method works as follows. At the first iteration, the primal problem (1.9) is solved in an initial point. The initial point must be chosen such that the first primal problem is feasible. Then, at each iteration, the master problem (1.11) is formulated using the information obtained in the solution of the previous primal and feasibility problems and a lower bound is provided. Then, the primal problem (1.9) is formulated by fixing y at the integer point obtained in the master problem and a new upper bound is obtained. In case the primal problem is infeasible, feasibility problem (1.10) is formulated instead. This continues until the upper bound and the lower bound obtained in the primal and master problems converge together. 1.4 Contributions and Results In this thesis, we aim to improve performance of wireless mesh networks under reliability constraints. Our contribution is to develop rate allocation algorithms, scheduling policies, and flow control solutions with the goal of improving the reliable throughput of the network. While achieving that goal, we also consider fairness provisioning. In the following, we describe our results and contributions in summary. 16 Chapter 1. Introduction • In Chapter 2, we consider unreliability of wireless networks due to varying channel conditions, especially when users are mobile. We formulate a joint max-min fair channel coding and end-to-end data rate allocation problem in multipath wireless networks. We maximize the minimum throughput available among the network users. To cope with the fast and frequent changes in dynamic environments such as wireless mesh networks in vehicular environments, we address both adaptive and non-adaptive channel coding scenarios. We also redesign the adaptive algorithm to use the available information related to the current optimal solution leading to a faster convergence. Unlike similar formulations in single-path routing networks, which involve solving either a convex optimization problem or problems that can be transformed into a convex optimization problem, in the multipath routing case we face an optimization problem that is non-convex and is usually difficult to solve. We tackle non-convexity by using function approximation and iterative techniques from signomial programming. Simulation results confirm that by using channel coding jointly with multipath routing, we can significantly improve end-to-end network performance, compared to the case when only one of them is used in the network. Non-adaptive channel coding is also shown to achieve high degree of optimality with much less complexity. • In Chapter 3, we consider delay in wireless networks with multipath routing and channel coding. We show that a combination of multipath routing and adaptive channel coding can improve throughput and reduce delay, and that it is possible to trade off delay for throughput and vice versa. This is in contrast to the general expectation that higher throughput can only be achieved with noticeable degradations in the end-to-end network delay. In this regard, we jointly formulate the end-to-end data rate allocation and adaptive channel coding (at the physical layer) within the 17 Chapter 1. Introduction general framework of network utility maximization (NUM). Depending on the choice of the objective function, we formulate two NUM problems: one aiming to maximize the aggregate network utility; another one aiming to maximize the minimum utility among the end-to-end flows in order to achieve fairness, which is of interest in certain vehicular network applications. Simulation results confirm that we can decrease the average delay significantly at the cost of a small decrease in throughput. This is achieved by maximizing the aggregate utility in the network when fairness is not the dominant concern. Furthermore, we also show that even when resource allocation is performed in order to provide fairness, we can still decrease the maximum end-to-end delay of the network at the cost of a slight decrease in the minimum throughput. • In Chapter 4, we focus on inter-session network coding, where multiple unicast sessions jointly participate in network coding. We consider multi-hop unicast sessions over unreliable links and propose a distributed end-to-end transmission rate adjustment mechanism to maximize the aggregate network utility by taking into account the wireless link reliability information. This includes an elaborate modeling of endto-end reliability. Simulation results show that by taking into account the reliability information, we can increase the network throughput by up to 100% for some network topologies. We can also increase the aggregate network utility significantly for various choices of utility functions. • In Chapter 5, we consider the setting of multihop wireless networks and develop an online flow control and scheduling algorithm for packet admission and link activation that achieves high aggregate throughput while providing different data flows with a fair share of network capacity. For fairness provisioning, we maximize the minimum throughput provided to flows in the network. We also develop an algorithm that does not consider fairness provisioning. To cope with different degrees of data reliability 18 Chapter 1. Introduction among the different links in the network, we use different channel code rates as appropriate. While we expect performance improvement using channel coding and multipath routing, the main contribution is a joint treatment of network stability, multipath routing and link-level reliability in meeting the overarching goal of maxmin fairness. We develop a decentralized, and hence practical, scheduling policy that addresses various concerns and demonstrate, via simulations, that it is competitive with respect to an optimal centralized rate allocator. We also evaluate the fairness provisioning under the proposed algorithm and show that channel coding improves the performance of the network significantly. Finally, we show through simulations that the proposed algorithm outperforms a class of existing approaches on fairness provisioning, which are developed based on utility maximization. • In Chapter 6, we study scheduling, interference alignment, and packet admission control in MIMO wireless systems with the goal of maximizing system throughput subject to stability constraints. We formulate the joint scheduling, packet admission control, and interference alignment problem as a stochastic network optimization problem and propose an efficient algorithm. In each time slot, the algorithm schedules some users to send data among many competing ones. It also determines the optimal encoding and decoding matrices for those selected users. Packet admission control is performed in each time slot. We also propose an efficient heuristic. Via simulation, we evaluate the performance of both the proposed optimal algorithm and heuristic under different number of users and showed that the heuristic follows the optimal central solution with some degree of sub-optimality. 19 Chapter 1. Introduction 1.5 Thesis Organization This thesis is organized as follows. We first develop an optimal data rate and channel code rate allocation algorithm in multipath routing wireless networks with channel coding in Chapter 2. The goal is to improve the reliability and throughput in the wireless mesh networks with fairness provisioning. In Chapter 3, we incorporate the end-to-end delay in the utility function of the problem solved in Chapter 2 and reformulate the problem of data and channel code rate allocation with the goal of decreasing the end-to-end delay for network flows. In Chapter 4, we use inter-session network coding for performance improvement and obtain the optimal data rate allocation for both routing paths and network coding schemes. To address the achievability of the rate allocation design obtained in Chapter 2, we consider transmission scheduling as well as flow control in a time slot based setting in Chapter 5. In Chapter 6, we study the problem of joint scheduling, interference alignment, and packet admission in MIMO systems. Finally, the thesis is concluded and some potential future work is introduced in Chapter 7. Each of the main chapters in this thesis is self-contained and included in separate journal articles or conference papers. A review of the related work is given for each chapter accordingly. The notations are defined separately for each chapter. 20 Chapter 2 Optimal Data Transmission and Channel Code Rate Allocation in Multipath Wireless Networks 2.1 Introduction As discussed in Chapter 1, multipath routing and channel coding are promising techniques for performance improvement in wireless mesh networks. In this chapter, our focus is to jointly use channel coding and multipath routing in an optimization-based framework to further improve reliability compared to using only channel coding or only multipath routing. We are interested in answering the following question: How shall we select the end-to-end data transmission rates over different paths and per-link channel code rates in order to achieve the optimal rate-reliability tradeoff in multipath wireless networks? Our main contribution is a solution to the fair resource allocation problem in networks that jointly employ multipath routing and link-specific channel coding. In this regard, our work is closely related to [22]. However, here we introduce three key extensions. First, Lee et al. in [22] assume that the links in the network are either wired or interferencefree wireless. On the contrary, here we have explicitly incorporated the impact of wireless interference. Second, unlike the system model in [22] which addresses only single-path 21 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation routing, here we consider the case where there are multiple end-to-end routing paths available across the network. Clearly, this includes single-path routing as a special case. Third, we formulate the problem such that the minimum throughput among the individual users is maximized. This leads to fairness provisioning which is of great importance in certain applications such as vehicular networks where vehicles frequently switch among stationary mesh nodes to receive connectivity. In this case, different mesh nodes must be provided with fair and consistent data rates. The aforementioned three extensions introduce several challenges in solving the formulated optimization problem and have not been addressed before. Those are due to various non-convexities that cannot be directly transformed into a convex optimization problem using the well-known logarithmic change of variables as in [22]. Although our proposed method is centralized, it may be used in vehicular network applications such as those in which stationary access points provide connectivity for the vehicles in their coverage zone. Moreover, it can shed light on how per-link channel coding can improve end-to-end performance in a multipath routing wireless network. The centralized solution may also be used as a benchmark for evaluating distributed approaches which may be developed in the future. To the best of our knowledge, rate allocation with the goal of fairness and reliability enhancement using multipath routing and channel coding has not been addressed in any prior work. The contributions of this chapter are as follows. • We formulate max-min fair resource allocation in multipath wireless networks employing channel coding as an optimization problem. Our system model includes both adaptive and non-adaptive channel coding. • We tackle the non-convexity of the formulated optimization problem in two steps. First, we use function approximations to reformulate the problem as a signomial programming problem (which is still non-convex). Next, we develop an iterative algo22 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation rithm to solve the signomial programming problem by solving a chain of tractable geometric programming problems. We introduce a non-adaptive channel coding scheme with much lower degree of complexity, which can find a sub-optimal solution. We design our algorithm such that it can quickly find the new solution, whenever there is a change in the network topology and the number of users. • To motivate the joint use of multipath routing and channel coding, we show through simulations that our proposed scheme significantly improves the network performance when compared to the case with multipath routing, but without channel coding. We also show that our joint scheme outperforms channel coding in single-path routing systems. • We investigate the convergence properties of the proposed algorithm as well as its efficiency. The latter is studied particularly by evaluating the impact of the approximations made in the derivation of the algorithm. • We compare the adaptive coding scheme with the non-adaptive coding scheme with less computational complexity. We evaluate the proposed algorithm in a dynamic vehicular environment where the data traffic pattern changes due to mobility. Finally, we study the effects of fading on the performance of the algorithm. The rest of this chapter is organized as follows. We present the system model and formulate the joint data rate and channel code rate allocation problem in Section 2.2. In Section 2.3, we reformulate the problem as a geometric programming problem and propose a reliability-based rate allocation algorithm to solve it. We also introduce a non-adaptive channel coding scheme as a sub-optimal solution with lower complexity. Simulation results are presented in Section 2.4. The chapter is summarized in Section 2.5. 23 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation 2.2 2.2.1 System Model And Problem Formulation System Model Consider an ad-hoc wireless network. We can model the network topology as a directed graph G(V, E), where V = {1, 2, . . . , V } is the set of nodes and E is the set of wireless links. Let I = {1, 2, . . . , I} denote the set of all unicast sessions in the network. For each session i ∈ I, the source and destination nodes are denoted by si and ti , respectively. Furthermore, we denote Ki = {1, 2, . . . , Ki } as the set of all available routing paths from source node si to destination node ti . For each session i ∈ I, each link e ∈ E, and each k ∈ Ki , we have aek i 1, = 0, if link e belongs to k th routing path for session i, (2.1) otherwise. We assume that static routing is used and the routing information is given a priori. For each session i ∈ I, let αik denote the data rate of source si on its k th routing path, k ∈ Ki . The aggregate transmission rate for session i is obtained as αik . (2.2) k∈Ki Since the packets are retransmitted whenever they are lost in the network, the effective receiving rate at destination node ti is the same as (2.2). Channel coding can improve reliability on lossy channels by adding redundant bits to the data packets transmitted. In this regard, we define Re as the code rate of link e ∈ E, i.e., the ratio of the data bits to data plus redundant bits. Notice that if no channel coding is performed, then Re = 1 as there will be no redundant bits in the packet. 24 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation Let R0e ≤ 1 denote the cut-off rate on wireless link e ∈ E. We assume that the rate Re of the adopted coding schemes (e.g., convolutional codes) is limited by the cutoff rate [85]. Given code rate Re ≤ R0e if random coding based on M -ary binary coded signals is used, we can bound the packet error probability on link e to be less than 2−T (R0e −Re ) as [22, 36, 52, 85]. Therefore, in the worst case, we have Pe = 1 − 2−T (R0e −Re ) , (2.3) where Pe is the successful packet transmission probability on link e and T is the coding block length. In general, the cut-off rate R0e depends on the signal-to-noise ratio (SNR) and the modulation scheme being used. For example, for a binary phase shift keying (BPSK) waveform [85], we have R0e = 1 − log2 (1 + e−γe ), (2.4) where γe denotes the SNR at the receiver node of wireless link e ∈ E. In particular, we have 2 γe = Γe × d−σ e × |fe | , ∀ e ∈ E, (2.5) where Γe depends only on the SNR at transmitter, de is the distance between the transmitter and receiver of link e, σ is the path loss exponent (e.g., between 2 and 5), and fe is the small-scale fading gain. Assuming re-transmission after a packet is lost in the network until reaching a successful transmission, each packet must be sent 1/Pe times on average over each link e. Given the source transmission rates α = (αik , ∀ i ∈ I, k ∈ Ki ), successful transmission probabilities P = (Pe , ∀ e ∈ E), and the link code rates R = (Re , ∀ e ∈ E), we can model the aggregate traffic load on link e ∈ E as ue = 1 Re Pe k aek i αi . (2.6) i∈I k∈Ki 25 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation From (2.6), the smaller the code rate Re , the more redundant data is added to the transmitted packets on link e ∈ E leading to more reliable transmission (i.e., transmission with lower error probability). However, this will be at the cost of increasing the traffic load on the link. We can model the mutual interference among the wireless links in a network by using a contention graph GC (VC , EC ). In the contention graph GC , the set of vertices VC represents the set of all wireless links E in the network graph G. There exists an edge between any two vertices in set VC if wireless links corresponding to two vertices mutually interfere with each other (i.e., the receiver node of one link is within the interference range of the sender node of the other link). Given the contention graph, each complete subgraph (i.e., a subgraph in which all vertices are connected to all other vertices) is called a clique. A maximal clique is then defined as a clique which is not a subgraph of any other clique [86]. Denote the set of all maximal cliques in contention graph GC by QC . Only one link among all the links corresponding to the vertices of a maximal clique Q ∈ QC can be active at a time. For the data link layer, we assume that time division multiple access (TDMA) is used. Let ce denote the nominal data rate of link e ∈ E. The ratio ue ce denotes the proportion of time at which link e ∈ E is active when it is used at data rate ce . It is required that e∈Q ue ≤ ν, ce ∀ Q ∈ QC , (2.7) where ν ∈ (0, 1] is called the clique capacity. Note that if ν = 1, then (2.7) is only a necessary constraint. It is shown that inequality (2.7) is a sufficient constraint when ν = 2/3 [87]. Note that we assume all clique information given. This can be achieved in a central manner having the complete information about the network topology. Distributed approaches can also be developed which are out of scope of this thesis. 26 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation Figure 2.1: An example downtown area with 25 access points (forming a wireless mesh infrastructure). The access point at the center serves as the gateway. There are 10 vehicles in the system, each one uses the nearest access point to connect to the Internet. Now we show how the provided modeling covers the vehicular environment. Consider Fig. 2.1 in which an example downtown area is shown. There is an access point in every other cross section and the one at the center of the area is denoted as the gateway. Access points correspond to nodes in set V. There is a wireless link e ∈ E between two adjacent access points. Vehicles move in the streets continuously. Each vehicle at each instant of time finds the nearest access point and connects to it to transmit data to the gateway. The access point i ∈ I which is connected to a vehicle, represents source node si for flow i. The gateway corresponds to destination node ti . During the time that vehicles move in the area the set of sources and thus the data traffic pattern changes. 27 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation 2.2.2 Problem Formulation Considering (2.2), (2.3), (2.6), and (2.7), the rate-reliability tradeoff can be explained as follows. For each link e ∈ E, by increasing the code rate Re we can reduce the traffic load per transmission on each link. Thus, higher transmission rates will be allowed with the same clique capacity. However, this is at the cost of less reliability and leads to more re-transmission attempts as in (2.6). On the other hand, by decreasing the code rate Re , we can reduce the error probability in (2.3) which leads to higher probability of successful transmission along each routing path. Therefore, we may select either higher transmission rates, but with more packets being prone to error, or lower transmission rates, but with higher percentage of correctly received packets. In this regard, the key question to be answered is: What transmission rates α and code rates R should be selected to achieve optimal performance? To answer the above question, we formulate the following optimization problem. Max-Min Fairness Problem: maximize α 0, 0≺R R0 αik minimum i∈I subject to e∈Q 1 Pe Re ce k∈Ki i∈I k∈Ki k aek i αi ≤ ν, ∀ Q ∈ Q, Pe = 1 − 2−T (R0e −Re ) , (2.8) ∀ e ∈ E, where R0 = (R0e , ∀ e ∈ E) denotes the vector of cut-off rates for all links in the network. The objective function in (2.8) is the minimum receiving rate among all sessions in the network, where for each session i ∈ I, the receiving rate is as in (2.2). By solving (2.8), we can find α and R such that the minimum throughput across all sessions is maximized. Notice that we could also maximize the aggregate network throughput. However, the aggregate network throughput maximization problem does not take into account any notion 28 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation of fairness as the objective is to maximize the total network throughput. As a result, the optimal solution may lead to starvation in some sessions. Max-min fairness solution avoids starving any of the sessions and balances the performance in the network. We will discuss solving problem (2.8) in Section 2.3. 2.3 Optimal Transmission Rate and Channel Code Rate Allocation 2.3.1 Adaptive Channel Coding In this section, we propose an iterative algorithm to solve the max-min fairness optimization problem to achieve optimal allocation of source transmission rates α as well as optimal channel code rates R in the network. In general, problem (2.8) is non-convex and difficult to solve. Note that the non-convexities in problem (2.8) come from the following three sources: (a) The minimum term in the objective function. (b) The exponential forms in the equality constraints with respect to error probabilities. (c) The fractional forms in the inequality constraints with respect to clique capacities. Most of these challenges are caused by the fact that, unlike many of the existing related work in the literature on rate-reliability tradeoff (e.g., in [22]), we take into account multipath routing and wireless interference. For example, if the network is wired such that no interference occurs among transmissions, then the clique capacity constraints would reduce to several linear link capacity constraints such that for each link e ∈ E we have 1 Pe Re ce i∈I k∈Ki k aek i αi ≤ 1 ⇒ i∈I k∈Ki k aek i αi ≤ Pe Re ce . (2.9) However, these techniques are not applicable where multipath routing is used and wireless 29 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation transmissions incur interference. In fact, we need to go through more elaborate steps in order to be able to solve problem (2.8) in the general case as will be explained in detail next. Recall that problem (2.8) is a non-convex optimization problem due to the three reasons listed earlier, where one of them is the exponential forms in the equality constraints with respect to error probabilities. We start by tackling this source of non-convexity. First, we replace this equality with an inequality. This does not degrade the performance of the algorithm because it overestimates the unreliability in the network. For notational simplicity, we rewrite the error probability (2.3) as Pe ≤ 1 − Xe exp (Le Re ) , ∀ e ∈ E, (2.10) where Xe = 2−T R0e , and Le = T ln 2. Recall that for each link e ∈ E, we have 0 < Re ≤ R0e . We use Taylor series expansion to write inequality (2.10) as P e ≤ 1 − Xe ∞ n=0 (Le Re )n , n! ∀ e ∈ E. (2.11) ∀ e ∈ E. (2.12) Clearly, for some bounded integer Ne ≫ 1, we have Pe ≤ 1 − Xe Ne −1 n=0 (Le Re )n , n! Unlike the exponential error probability model in (2.10), the model in (2.12) is in polynomial form. For (2.12) to approximate (2.11) accurately, we need Ne to be large enough such that (Le Re )Ne ≪ Ne !. We investigate the value of Ne necessary for obtaining a good approximation in Section 2.4.4. 30 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation By exploiting the worst-case packet error probability (2.12) in problem (2.8), we rewrite the max-min fairness problem as maximize α≻0, 0≺R R0 ,P ≻0 αik minimum i∈I subject to e∈Q i∈I k∈Ki k∈Ki k −1 −1 −1 aek i αi Pe Re ce ≤ ν, ∀ Q ∈ Q, Pe Xe + 1 − Xe 1 − Xe Ne −1 n=1 (2.13) (Le Re )n ≤ 1, ∀ e ∈ E. n! The objective in (2.13) is to maximize the utility of the transmission session with the minimum value. We can replace the minimum function in the objective function by introducing a new auxiliary variable t and a set of new constraints as minimize t>0, α≻0, 0≺R R0 ,P ≻0 subject to t≤ t−1 αik , ∀ i ∈ I, k∈Ki e∈Q i∈I k∈Ki k −1 −1 −1 aek i αi Pe Re ce ≤ ν, ∀ Q ∈ Q, Pe Xe + 1 − Xe 1 − Xe Ne −1 n=1 (2.14) (Le Re )n ≤ 1, ∀ e ∈ E. n! The objective function and constraints in problem (2.14) are signomials, i.e., polynomials with both positive and negative terms. Therefore, we can apply signomial programming techniques [82] to solve problem (2.14). Consider the first constraint in (2.14). We follow the signomial programming techniques [82] to approximate the polynomial on the right-hand side of this inequality, which is a function of only α, as a monomial, i.e., a polynomial with only one term and positive ˆ For a multiplier. This approximation can be performed around some initial point α. 31 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation parameter fs > 1, which is close to 1, we have k∈Ki αik ≈ α ˆ ik k∈Ki k∈Ki αik α ˆ ik α ˆ ki / k ′ ∈Ki ′ α ˆ ik′ ˆ s , fs α] ˆ , , ∀ α ∈ [α/f (2.15) ˆ s , fs α] ˆ is a small neighborhood around initial point α. ˆ The for any i ∈ I, where [α/f closer fs is to 1, the more accurate the approximation of (2.15) will be at the cost of slower ˆ i which convergence of the algorithm. For simplicity of notation, for any i ∈ I, we define Λ ˆ as only depends on the initial point α, ˆ −1 = Λ i α ˆ ik . (2.16) k∈Ki From (2.15) and (2.16), the first constraint can be approximated around the initial point ˆ as α ˆ it Λ k∈Ki αik α ˆ ik ˆi −α ˆ ki Λ ≤ 1, ∀ i ∈ I. (2.17) The above constraint is a posynomial, i.e., a polynomial with only positive terms. Replacing the first constraint in (2.14) with (2.17), the max-min fairness problem becomes minimize ˆ 0≺R R0 , P ≻0 ˆ s α fs α, t>0, α/f subject to ˆ it Λ 1 ν k∈Ki αik α ˆ ik e∈Q i∈I k∈Ki t−1 ˆi −α ˆ ki Λ ≤ 1, k −1 −1 aek i αi Re ce ≤ 1, Pe Xe + 1 − Xe 1 − Xe Ne −1 n=1 ∀ i ∈ I, ∀ Q ∈ Q, (2.18) (Le Re )n ≤ 1, ∀ e ∈ E. n! The above problem is a geometric program, which can be converted into a convex problem (cf. [82, 83]). Thus, problem (2.18) is a tractable optimization problem that can be solved 32 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation efficiently using convex programming techniques such as the interior point method [81]. We can solve the signomial programming problem (2.14) by iteratively solving (2.18). We now present Algorithm 2.1 to solve the max-min fairness problem in (2.8). Algorithm 2.1 starts by initializing various system parameters. The initial end-to-end transˆ are selected such that problem (2.18) is feasible. Several iterations are mission rates α performed, where in each iteration, we solve the geometric programming problem (2.18) in Line 5 by using the interior point method [81]. Given the optimal transmission rates ˆ i for any i ∈ I according to (2.16) and αopt in each iteration, we update parameters Λ correspondingly reformulate problem (2.18) to be solved again in the next iteration. The iterations continue until the optimal objective value topt which is obtained in the current iteration does not change compared to the optimal objective value told in the previous iteration. The convergence of the algorithm in each iteration is guaranteed since the interior point method is used [88]. The convergence of Algorithm 2.1 is also guaranteed [82, p. 115]. Algorithm 2.1 : Algorithm to solve max-min fair resource allocation problem (2.8). 1: Initialize fs , T , Ne , R0e , Xe , Le , ce , ν, and α ˆ ik for each e ∈ E, i ∈ I, and k ∈ Ki . 2: Set topt := −∞; ǫ := 10−5 . 3: repeat 4: told := topt . 5: Solve problem (2.18) to obtain αopt , Ropt , and topt . ˆ i as in (2.16) for each i ∈ I. ˆ := αopt and update Λ 6: Update α 7: until |topt − told | ≤ ǫ. 8: Optimal end-to-end data rates := αopt . 9: Optimal per-link code rates := Ropt . In case any change happens in the network (e.g., change in the network topology, the number of network users or the traffic pattern), the input parameters of the formulated problem are updated and the corresponding new solution is obtained. Clearly, this can be time consuming if the changes are very frequent. To cope with frequent changes in dynamic 33 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation environments, we modify the proposed algorithm such that it updates the last end-to-end ˆ for the new problem. This improves data rate vector αopt to obtain the new initial point α the convergence speed of the algorithm compared to the case where the existing solution is ignored and the problem is solved from scratch. The update process is to remove the entries for the users who left the network and also to add new entries for the new users who have just joined the network. The new entries must be chosen such that the problem remains feasible (i.e., small values must be chosen). In case of topology changes, the algorithm ˆ accordingly. As mentioned before, the algorithm is finds new routing paths and updates α executed in a central node (e.g., the gateway) and the required information (e.g., channel state information, location of users) is transferred through control messages. In case of the example vehicular network in Fig. 2.1, the problem is reformulated and solved in specific time instants in the gateway and the solution is passed on to the access points through control messages. We note that Algorithm 2.1 needs to be used to update the code rates as well as end-to-end data rates whenever new channel measurements are available, particularly in a fading or mobile environment. We will investigate the impact of our design in a fast fading environment in Section 2.4.8. Moreover, we will discuss non-adaptive channel coding in Section 2.3.2 for the case when parameters change faster than the time required for the algorithm to converge. 2.3.2 Non-adaptive Channel Coding In this section, we simplify the system model in Section 2.3.1 and assume that the channel code rate is fixed and is no longer an optimization variable in our design. That is, Re = R, ∀ e ∈ E. (2.19) 34 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation The impact of such an assumption is two-fold. First, it can simplify the clique capacity constraints in problem (2.8) as for each maximal clique Q ∈ Q, we have 1 Re Pe ce i∈I e∈Q k aek i αi = k∈Ki ⇒ 1 RP e∈Q aek i e∈Q i∈I k∈Ki ce i∈I k∈Ki αik aek i αk ≤ ν ce i (2.20) ≤ R P ν, which is simply a linear inequality constraint. Second, since we are adding the extra equality constraints into problem (2.8), any solution we achieve would be sub-optimal. In the non-adaptive channel coding case, the max-min fair resource allocation problem (2.8) is reformulated as maximize α≻0 αik minimum i∈I subject to k∈Ki aek i e∈Q i∈I k∈Ki ce (2.21) αik ≤ RP ν, ∀ Q ∈ Q, where P = 2T (R−R0 ) . By introducing an auxiliary variable t and considering the worst case for error probabilities, problem (2.21) becomes maximize α≻0, t t subject to t ≤ αik , k∈Ki e∈Q i∈I k∈Ki ∀ i ∈ I, aek i αk ≤ RP ν, ce i (2.22) ∀ Q ∈ Q, which is a linear programming problem. To find the best fixed code rate, we can solve problem (2.22) for different values of R ∈ [0, R0 ] and choose the solution with the highest objective value. With non-adaptive channel coding, we significantly decrease the computational complexity of solving the problem at some cost in performance. This can particularly 35 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation help in dynamic environments where there are frequent changes in the system parameters. 2.4 Performance Evaluation In this section, we assess the performance of our proposed joint channel coding and transmission data rate allocation algorithm (Algorithm 2.1). In our simulation model, we consider network topologies where V = |V| = m(m − 1) wireless nodes are positioned on an m × m square grid with randomly selected grid locations. As an example, for the network in Fig. 2.2, we have m = 5 and V = 20. The network includes m source and destination pairs, with potentially many available routing paths from the source node to the destination node. In Fig. 2.2, there are four available routing paths from source node 1 to destination node 16. They include: {(1, 2), (2, 3), (3, 8), (8, 11), (11, 16)}, {(1, 2), (2, 7), (7, 8), (8, 11), (11, 16)}, {(1, 6), (6, 7), (7, 8), (8, 11), (11, 16)}, and {(1, 6), (6, 10), (10, 14), (14, 15), (15, 16)}. Unless stated otherwise, the rest of the system parameters are selected as follows: T = 10, Ne = 15, fs = 1.1, R0e = 1, ν = 2 3 [87]. Without loss of generality, we choose the link capacity, ce for each link e ∈ E, to be equal to 1. Therefore, the transmission data rates, α, obtained in the optimal point can be interpreted as the vector of normalized transmission rates. If the algorithm is being executed for the first time, we set the initial data rates to be small, i.e., α ˆ ik = 0.01 for all i ∈ I and any k = 1, . . . , Ki , in order to guarantee a feasible starting point for Algorithm 2.1, as we already discussed in Section 2.3.1. Otherwise, in case of updating the current rate vector, we set the new entries for the new routing paths equal to 0.01. To solve the geometric programming problems, we use MOSEK [89]. 36 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation Figure 2.2: A sample network topology with 20 nodes randomly located in a 5 × 5 grid. The network includes five sessions: 1 → 16, 3 → 13, 2 → 8, 14 → 17, and 6 → 20. There are 4, 2, 2, 1, and 3 routing paths available for these sessions, respectively. 2.4.1 Multipath vs. Single-path Routing We first study the performance enhancement achieved by using multipath routing compared to single-path routing. In the latter case, each source only uses one (out of possibly several) of the available shortest paths to its corresponding destination. We compare our proposed algorithm with the one in [22], where both channel coding and transmission rate allocation is performed in a single-path routing system. By solving the max-min fair resource allocation problem (2.8) for the single-path routing (as in [22]) and also for the multipath routing cases (as in our proposed design), the optimal end-to-end data rates are obtained. Recall that the objective value in problem (2.8) is the minimum throughput among all five sessions. In Fig. 2.3, each point represents the averaged performance gain over 50 random topologies. We can see that the performance gain (i.e., the ratio of the averaged performance under multipath routing to the averaged performance under single-path routing) directly depends on the number of available (and 37 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation Normalized Minimum Throughput Among All Sessions 1.5 1.4 1.3 1.2 1.1 1 0.9 0.8 0.7 Multipath Routing Single−path Routing 0.6 0.5 2 2.2 2.4 2.6 2.8 3 Average Number of Paths for Each Session Figure 2.3: Comparison between the performance of adaptive channel coding in single-path and multipath routing networks in terms of the achieved normalized minimum throughout. used) routing paths. It monotonically increases as the number of available routing paths increases. This increase is due to the availability of additional paths, the algorithm can distribute the load to the paths which experience less interference. Therefore, the sending rates are increased. In this case, the minimum network throughput can be enhanced by 22% on average when the average number of paths for each session is only two. This enhancement increases to 40% when the average number of routing paths increases to three. This is because the algorithm can inject the packets into the paths experiencing less interference. 2.4.2 Channel Coding vs. No Channel Coding Next, we study how channel coding can improve the achieved network throughput in a multipath routing system. Since equality (2.3) models the worst case condition (i.e., provides upper bound on the error probability) and the error probability is equal to 1 in the absence of channel coding, we use the following exact successful packet transmission 38 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation probability model for BPSK modulation for the case without channel coding: Pe = 1 − Q( √ 2γe ) T , (2.23) where Q(.) denotes the Gaussian Q-function: Q(x) = √1 2π ∞ x 2 exp(− u2 )du, (2.24) and γe denotes the SNR at the receiver node of wireless link e ∈ E. For a received SNR equal to 3 dB, we have Pe = 0.4 for T = 40. Our comparison reveals the minimum achievable performance gain by the use of channel coding. This is because we use the exact Pe for the case without channel coding but a lower bound (worst case) for the case with channel coding. As shown in Fig. 2.4, a major performance gain can be achieved with channel coding. The achieved performance degrades in both cases when the size of the network increases. This is because as the number of users increases, the interference in the network increases. For the results in Fig. 2.4, each point represents the normalized throughput averaged over 50 randomly generated network topologies. 2.4.3 Convergence Properties of Algorithm 2.1 Recall that each iteration of Algorithm 2.1 includes a function approximation step and a geometric programming step. Considering the network topology in Fig. 2.2, the convergence of the objective value for problem (2.8), when Algorithm 2.1 is used, is shown in Fig. 2.5. The objective value for problem (2.8) is the minimum throughput among all sessions. From the results in Fig. 2.5, Algorithm 2.1 converges after around 50 iterations. Similar results can be obtained for other network topologies. 39 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation Normalized Minimum Throughput Among All Sessions 0.26 With Channel Coding Without Channel Coding 0.24 0.22 0.2 0.18 0.16 0.14 0.12 0.1 0.08 0.06 6 12 18 24 30 36 42 Number of Nodes V Figure 2.4: Comparison between the performance of multipath routing with and without per-link channel coding in terms of the achieved normalized minimum throughput among the end-to-end sessions, when the scale of the network increases and the number of nodes varies from 6 to 42. Normalized Minimum Throughput Among All Sessions 0.12 0.1 0.08 0.06 0.04 0.02 0 10 20 30 40 50 60 Iteration Number Figure 2.5: Convergence of Algorithm 2.1 with respect to solving problem (2.8). We can see that the algorithm converges after 50 iterations. 40 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation Optimality (Approximation) Error 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 2 4 6 8 10 12 14 16 18 20 Design Parameter Ne Figure 2.6: The impact of the choice of design parameter Ne in approximation (2.12). The average optimality error decreases as Ne increases. It becomes almost zero for Ne > 12. 2.4.4 Impact of Various Design and System Parameters Parameter Ne In Section 2.3, we use the approximation in (2.12) to convert problem (2.8) into a tractable geometric programming problem as in (2.13). We can improve the accuracy of the approximation in (2.12) by increasing the value of Ne . However, this would be at the cost of making problem (2.13) more complicated to solve. In this section we are interested in choosing Ne to obtain a reasonable accuracy with low computational complexity. Considering 50 random topologies, the simulation results, when Ne varies from 1 to 20, are shown in Fig. 2.6, where each point indicates the average optimality error observed for all 50 topologies. By obtaining the difference between the achieved network throughput at a particular choice of Ne and that at Ne = 20 (as the optimal throughput) and computing the ratio of this difference to the optimal throughput, we can define a measure for assessing the optimality error. Fig. 2.6 shows that the optimality error approaches zero when Ne is around 12 or higher. 41 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation Parameter fs Another approximation in Section 2.3 is the monomial approximation in (2.15). The ˆ approximation is made at each iteration within a close neighborhood of initial point α. The size of the neighborhood is denoted by design parameter fs . In general, although we can increase the speed of convergence by increasing the value of fs , it would be at the cost of a lower accuracy in the approximation. Considering such a tradeoff and based on our simulation results, we select fs = 1.1, for a relatively good performance in terms of approximation accuracy, with a fast convergence speed. Parameter T In general, when we increase the coding block length T for a given code rate, the probability of error decreases. This can be seen in (2.3). By increasing T , one can allocate a higher code rate to a wireless link, while achieving the same probability of error, i.e., the same reliability measure. On the other hand, the more reliable links let the algorithm allocate higher end-to-end data rates, leading to improved optimal objective values in problem (2.8). This is shown for three random network topologies in Fig. 2.7, where the coding block length T varies from 10 to 100. The minimum throughput in the network increases in all three topologies when the coding block length (and thus the reliability) increases. 2.4.5 Adaptive vs. Non-adaptive Channel Coding In this section, we show how choosing the code rate for each link individually (i.e., adaptive channel coding) can lead to different optimality and computational complexity results, compared to the case when channel coding is non-adaptive. Recall from Section 2.3.2 that in a non-adaptive channel coding scenario, we assume that all wireless links use the same code rate R as expressed in (2.19). In this case, for each fixed R, problem (2.8) becomes a 42 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation Normalized Minimum Throughput Among All Sessions 0.25 0.2 0.15 0.1 0.05 0 10 Topology Number 1 Topology Number 2 Topology Number 3 20 30 40 50 60 70 80 90 100 Coding Block Length T Figure 2.7: The impact of choosing different coding block lengths T on the network performance for three different random topologies. We observe that the performance improves when the coding block length increases. Normalized Minimum Throughput Among All Sessions 0.14 Adaptive Channel Coding Non−adaptive Channel Coding 0.12 0.1 0.08 0.06 0.04 0.02 0 0 0.2 0.4 0.6 0.8 1 Channel Code Rate R Figure 2.8: Comparison between adaptive and non-adaptive channel coding. 43 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation Code Rate on Link e, Re 1 Optimal Non−adaptive (Fixed) Code Rate Optimal Adaptive Code Rates for Each Link 0.9 0.8 0.7 0.6 0.5 0.4 2 4 6 8 10 12 14 16 18 20 22 24 Wireless Link Index Figure 2.9: Optimal non-adaptive code rate versus adaptive code rate distribution among all wireless links of the network topology in Fig. 2.2. linear programming problem. This can significantly reduce the computational complexity, but it may result in a loss in performance. Consider the network topology in Fig. 2.2. Here, we examine various choices of nonadaptive code rate R within the feasible range [0, R0 ]. We can see in Fig. 2.8 that by using non-adaptive channel coding, the highest throughput is achieved when the code rate on all links is equal to 0.74. At this point, we reach almost the optimal value that is achievable by using adaptive channel coding. It is also interesting to investigate the distribution of the optimal adaptive code rates of all wireless links, compared to the optimal non-adaptive code rate. We can see in Fig. 2.9 that in the adaptive channel coding case, the optimal code rates for various links can be significantly different. It is interesting to note that the code rates corresponding to the links which are not in any routing path (i.e., link 21) are chosen to be 1. Moreover, links which are used in many routing paths have code rates close to the corresponding non-adaptive channel code rate (0.74). 44 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation 2.4.6 The Effect of Dynamic Changes on the System Performance In this section, we study the effect of dynamic topology changes as well as changes in the number of network users on the network performance. As mentioned in Section 2.3.1, whenever the setting of the network changes, the algorithm solves the new problem by updating the last obtained end-to-end data rate vector, which is used as the new initial point for faster convergence. This may be beneficial especially in dynamic environments such as vehicular networks where the vehicles move constantly. Fig. 2.10 shows the convergence of the algorithm when changes happen in the network and compares it with the case when the algorithm does not use the available information related to the previous state of the network. In Fig. 2.10 (a), five randomly chosen links are added to and five random links are removed from the current topology every 100 time slots. In Fig. 2.10 (b), a new pair of source-destination nodes is added every 100 time slots while in Fig. 2.10 (c) a pair of source-destination node is removed from the network. Finally, in Fig. 2.10 (d), a randomly chosen pair is added and a randomly chosen pair is removed every 100 time slots. Fig. 2.10 shows that using the available information from the previous state of the network significantly increases the convergence speed of the algorithm. 2.4.7 The Effect of Mobility on the System Performance In this section, we study the effect of mobility in a vehicular network on the performance of our proposed design. In a vehicular network, users (i.e., vehicles) are always moving and in each instant, they connect to the nearest access point (a mesh node) for network provisioning. This results in dynamic changes in the traffic pattern which in turn leads to performance degradation in the system. The degree of performance reduction depends to the coverage area of the access points as well as the speed at which the vehicles move. 45 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation Using the Last Point Not Using the Last Point (a) Normalized Minimum Throughput Among All Sessions 0.2 0.1 0 0 200 400 600 800 1000 (b) 0.4 0.2 0 0 100 200 300 400 500 600 400 500 600 (c) 0.5 0 0 100 200 300 (d) 0.2 0.1 0 0 200 400 600 800 1000 Iteration Number Figure 2.10: Convergence speed for Algorithm 2.1 in presence of dynamic changes in the network. We compare two cases where the previous solution is exploited and the case where the previous solution is ignored. Every 100 time slots: (a) five links are added and five links are removed, (b) a new pair of source-destination nodes is added, (c) a pair of source-destination node is removed, (d) a random pair is added and another random pair is removed. Consider the example downtown area shown in Fig. 2.1. There are ten cars which move in random directions. In each instant, they connect to the nearest access point to communicate with the gateway. The network recalculates the optimal data rates and channel code rates every 5 seconds based on the most recent topology characteristics of the network. Clearly, the higher the speed of the vehicles, the larger will be the changes in the network. This can lead to a performance degradation. Fig. 2.11 shows the convergence of the adaptive scheme compared to the optimal value when the vehicles move with velocities of 20, 40, and 80 km/h. The rates are updated 100 times in a 500 second period. It is shown in Fig. 2.11 that the number of instants where the performance of the network deviates from the optimal solution increases when vehicles speed up. It is interesting that while the vehicles move in the area, the optimal solution does not change. This is because the destination for all data flows is the gateway and therefore there is a bottleneck around that node. Thus, although the source nodes change, the bottleneck remains and the achieved aggregate throughput remains unchanged. However, the allocated rates corresponding to 46 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation Optimal Value Proposed Algorithm Speed=20 km/h Normalized Minimum Throughput Among All Sessions 0.05 0 0 50 100 150 200 250 300 Speed=40 km/h 0.05 0 0 50 100 150 200 250 300 350 Speed=80 km/h 0.05 0 0 100 200 300 400 500 Iteration Number Figure 2.11: The convergence of the algorithm is shown for different speeds. Recalculations occur every 5 seconds if needed. different access points change such that the minimum throughput also remains optimal. The average minimum throughput of the network over 20 random scenarios is shown in Fig. 2.12 when the speed of the vehicles changes from 10 to 100 km/h. We observe that the average performance degrades when the speed increases under adaptive channel coding because more changes occur between two successive problem reformulation. However, the performance remains optimal under non-adaptive channel coding. This is because nonadaptive channel coding is less complex and converges faster to the final solution. 2.4.8 Impact of Fading Finally, we study the impact of fading on the system performance when Algorithm 2.1 is used. Recall from Section 2.3.1 that we can incorporate the impact of fading by separately solving problem (2.8) for each wireless channel realization with fading gains fe and corresponding cut-off rates as in (2.4) and (2.5). In this case, Algorithm 2.1 is invoked every time new channel measurement data becomes available. We refer to each channel measurement data as one channel snapshot. Simulation results for the network topology in Fig. 2.2 for 50 different channel snapshots 47 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation Adaptive Channel Coding Normalized Minimum Throughput Among All Sessions 0.05 Optimal Value Algorithm Performance 0.045 0.04 0.035 0.03 10 20 30 40 50 60 70 80 90 100 Non−adaptive Channel Coding 0.05 Optimal Value Algorithm Performance 0.045 0.04 0.035 0.03 10 20 30 40 50 60 70 80 90 100 Speed of Vehicles Figure 2.12: Performance of the algorithm is studied in the downtown area of Fig. 2.1 when vehicles move with different speeds. are shown in Fig. 2.13. In our simulation model, we generate the fading gains for each channel snapshot based on a random realization of the Rayleigh fading distribution. For the results in Fig. 2.13, we compare the performance of two design scenarios. The first design is an adaptive channel coding scheme based on the average fading information. That is, solving problem (2.8) only once by assuming that the fading gains take their average values within the Rayleigh fading distribution. On the other hand, in our second design, we solve problem (2.8) once for each channel snapshot. We can see that on average, the latter case (solid line) can improve the minimum throughput among all end-to-end sessions by a factor of 6 compared to the former one (dash line). The achieved performance improvement is at the cost of a significantly higher computational complexity due to the requirement of solving problem (2.8) for each snapshot, which may not always be desired in practice. The snapshots in which the minimum throughput among the sessions is zero denote the scenarios where there is at least one link in all paths of one session that has an instantaneous cutoff rate which is less than its assigned code rate. This does not happen if the code rates are updated according to the channel information in each snapshot. In summary, we showed that the adaptive channel coding approach converges to the op48 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation Normalized Minimum Throughput Among All Sessions 0.12 Code Rates Are Updated For Each Snapshot (Average −) Code Rates Are Not Updated For Each Snapshot (Average −−) 0.1 0.08 0.06 0.04 0.02 0 5 10 15 20 25 30 35 40 45 50 Channel Snapshot t Figure 2.13: Performance trend in a fading channel for 50 channel snapshots. timal solution in the presence of dynamic changes in the network due to channel variations and mobility. However, if the changes occur too frequently, the algorithm may fail to follow the changes fast enough and the performance degrades. On the other hand, we showed that non-adaptive channel coding is able to follow the dynamic changes and provides a high performance for the network without substantial sub-optimality. 2.5 Summary In this chapter, we considered the problem of jointly using per-link channel coding in wireless networks and multipath routing. In this regard, we focused on per-link channel code rate selection and end-to-end transmission data rate allocation and formulated a maxmin fairness optimization problem, which is of interest in vehicular network applications to offer fair and consistent data rates. Unlike the case of single-path routing, solving this problem in a multipath routing network is hard and involves non-convex programming. We tackled the non-convexity by using appropriate function approximations and iterative techniques from signomial programming. We proposed a novel code and data rate selection algorithm which uses the available information related to the latest optimal solution in 49 Chapter 2. Optimal Data Transmission and Channel Code Rate Allocation order to converge faster in highly changing conditions. Moreover, we studied different variations of our proposed per-link channel code rate selection and end-to-end data rate allocation algorithm in order to address both adaptive and non-adaptive channel coding and also the impact of fading. Simulation results confirm that by using channel coding jointly with multipath routing, we can significantly improve the end-to-end network performance compared to the case when only channel coding or only multipath routing is used. We also showed through simulations that as a sub-optimal approach with less complexity, nonadaptive channel coding achieves a high degree of optimality. Although our algorithm needs to be executed in a centralized manner, it can be applied in certain applications such as vehicular networks where stationary mesh nodes provide connectivity for moving vehicles. The centralized solution can also be used as a benchmark for distributed algorithms. 50 Chapter 3 Delay-Throughput Enhancement in Wireless Networks with Multipath Routing and Channel Coding 3.1 Introduction While most of multimedia applications have strict QoS requirements [90], the existing best-effort traffic delivery model cannot provide any service guarantee with respect to the minimum throughput and maximum delay of the end-to-end flows. Therefore, it is important to design wireless networks with high performance in regard of delay and throughput. We investigated the trade-off between reliability and throughput in achieving the highest possible effective throughput, which is the end-to-end throughput that the receiver is able to receive in Chapter 2 and [91]. We focused on multipath routing wireless systems, where adaptive channel coding is also performed at the physical layer. However, we did not address the issue of delay in Chapter 2. In this chapter, we explicitly incorporate delay in the utility of each session and propose a joint data rate and coding rate allocation algorithm that leads to maximizing the network aggregate utility across all sessions. Our work complements the existing results in the literature as follows. The recent work by O’Neill et al. [92] used NUM with adaptive modulation to determine the optimal sending rates 51 Chapter 3. Delay-Throughput Enhancement and transmit powers that maximize system performance. The trade-off between data rate, energy consumption, and delay is studied. However, O’Neill et al. did not incorporate delay into the utility function in their problem formulation [92] and the proposed design neither minimizes the delay nor provides a bound on end-to-end delay. On the other hand, Saad et al. [93] used the M/G/1 queueing model to estimate the delay as the summation of transmission delay and queueing delay. The same authors examined upper bounds on delay [94] but did not focus on delay reduction. In work by Kallitsis et al. [95], resources are allocated to maximize the throughput of the network and minimize the delay. Delay is modeled using network calculus and is incorporated directly into the utility function. Another research direction focuses on resource allocation to enhance the network performance by only minimizing the delay (e.g., Li et al. [38] and Kalyanasundaram et al. [96]). However, the impact of adaptive channel coding has not been considered in this context. On the other hand, channel coding is considered in [22]; but no analysis is performed related to delay. Finally, our problem is closely related to the recent work by Li et al. [51], which only addresses single-path routing within the context of wired networks or wireless networks with fixed capacity links. The contributions of this chapter can be summarized as follows: • We model a wireless network with several unicast data sessions, multiple routing paths for each session, and adaptive channel coding at the physical layer. To model the end-to-end delay, we use the average waiting time in an M/D/1 queueing system [97]. We then formulate the NUM problem of jointly finding optimal sending rates and code rates in the network to achieve the maximum network utility as a function of throughput and delay. • We formulate two optimization problems with and without fairness provisioning. In the former one, we aim to maximize the minimum utility in the network. In the latter 52 Chapter 3. Delay-Throughput Enhancement case, we maximize the overall utility of the network. Fair resource allocation is of particular interest in vehicular networks in which moving vehicles frequently switch among stationary access points. • To overcome the non-convexity due to channel coding, multipath routing, delay and reliability consideration, we introduce new variables, constraints, and approximations in the original problem and reformulate it as a series of tractable geometric programming problems [83]. • We develop an iterative algorithm to solve the formulated problem. To the best of our knowledge, there has been no prior work on jointly improving throughput and delay in a wireless multipath routing network with channel coding applied at the physical layer. • Simulation results for random topologies show that, when fairness is not a concern, we can decrease the average delay by 60% at the cost of only a marginal (< 0.1%) degradation in throughput. We also show that if fairness is addressed, we can decrease the maximum delay across the network by more than 35% with less than 12% decrease in minimum throughput. The system model and problem formulation are described in Section 3.2. The delay-aware optimal data rate and coding rate allocation approach is introduced in Section 3.3. The numerical results are shown in Section 3.4. The chapter is summarized in Section 3.5. 3.2 System Model A wireless network is modeled as a directed graph G(V, E), where V represents the set of nodes and E represents the set of wireless links, as it is shown in Fig. 3.1. For each unicast 53 Chapter 3. Delay-Throughput Enhancement Figure 3.1: A sample topology with five unicast multipath data sessions. Data sessions are (2 → 15), (7 → 18), (9 → 20), (12 → 23), and (3 → 25). These sessions have 6, 1, 2, 2, and 4 available paths, respectively. session i ∈ I, where I = {1, 2, . . . , I}, the source and destination nodes are denoted by si and ti , respectively. We define Ki , with Ki = |Ki |, as the set of all available routing paths from si to ti . Moreover, for each session i ∈ I, each k = 1, . . . , Ki , and each link e ∈ E, we define aek i = 1, 0, if link e ∈ k th routing path for session i, (3.1) otherwise. For each session i ∈ I, let αik denote the data rate at source si on its k th routing path, k = 1, . . . , Ki . Channel coding can improve the reliability over lossy wireless channels by adding redundant bits to data packets. For each link e ∈ E, we define Re as the link coding rate, i.e., the ratio of the number of data bits at the input of the encoder to the number of data plus redundant bits at the output. Notice that if channel coding is not performed on link e, then Re = 1. Given the data rates at the sources α = (αik , i ∈ I, k = 1, . . . , Ki ) 54 Chapter 3. Delay-Throughput Enhancement and the link coding rates R = (Re , e ∈ E), the aggregate traffic load on each link e ∈ E is ue = 1 Re i∈I Ki k=1 k aek i αi . The smaller the coding rate Re , the more redundant data is added to the transmitted packets on link e ∈ E leading to more reliable transmissions, i.e., transmissions with lower error probability. However, this will be at the cost of exposing the link to higher traffic. Let R0 = (R0e , e ∈ E), where R0e ≤ 1 is the cut-off rate on wireless link e ∈ E, that is an upper bound for the rate Re achievable with certain codes (e.g., convolutional codes) [85]. In general, the cut-off rate R0e depends on the received SNR and the modulation scheme being used. Given coding rate Re ≤ R0e , the error probability on link e can be modeled as [85] Pe = 2−T (R0e −Re ) , (3.2) where T is the coding block length. Based on the link failure model in (3.2), the probability that a packet is successfully transmitted along the k th routing path, k = 1, . . . , Ki for session i ∈ I is given by e∈E, aek i =1 (1 − Pe ) = e∈E 1 − aek i Pe . From the above equation, for each session i ∈ I, the aggregate effective throughput at destination ti becomes Ki k=1 αik e∈E 1 − aek i Pe . (3.3) To obtain the average end-to-end delay, we model each link as a single M/D/1 queue based on the Kleinrock independence approximation [97]. Here, we assume that the arrival rates in the source nodes follow a Poisson distribution. Since the transmission times over all links are deterministic, the number of arrivals for each queue in any time interval can be assumed to follow a Poisson distribution with rate Ki k aek i αi /L, λe = (3.4) i∈I k=1 55 Chapter 3. Delay-Throughput Enhancement where L is the packet length. From Little’s Theorem [97], the average waiting time for each queue e corresponding to link e ∈ E is given by δeQ L = i′ ∈I 2ce Re (ce Re − Ki′ k ′ =1 ′ ′ k aek i′ αi′ i′ ∈I Ki′ k ′ =1 ′ ′ k aek i′ αi′ ) , (3.5) where ce denotes the nominal data rate of link e ∈ E. By adding the waiting time and the transmission time δeT = L ce Re together, we have δe = δeQ + δeT for each link e ∈ E. Then, the average end-to-end delay for each path k = 1, . . . , Ki of session i ∈ I can be written as δik L = 2 e∈E aek i ce Re 2+ i′ ∈I ce Re − Ki′ k ′ =1 i′ ∈I ′ ′ k aek i′ α i′ Ki′ k ′ =1 ′ ′ k aek i′ α i′ . (3.6) To model the mutual interference among the wireless links in the network, we use the concept of contention graph. In the contention graph GC (VC , EC ) corresponding to network G(V, E), the set of vertices VC represents the set of all wireless links E in the network graph G. An edge connects any two vertices in set VC if the corresponding wireless links in the network graph mutually interfere with each other. That is, if the receiver node of one link is within the interference range of the sender node of the other link. Given the contention graph, each complete subgraph is called a clique. A maximal clique is a clique which is not a subgraph of any other clique [86]. We denote the set of all maximal cliques in GC by Q. In each instant, only one link among all members of a maximal clique Q ∈ Q can be active. The ratio ue ce denotes the portion of time that link e ∈ E is active when it is being used with data rate ue . It is required that ue e∈Q ce ≤ ν for each clique Q ∈ Q where ν ∈ (0, 1] is called the clique capacity. Note that ν = 1 is a necessary constraint on the clique capacity. It may not always be possible to find feasible schedules that achieve a clique capacity of ν = 1. Shannon showed that ν = 2 3 is a sufficient condition on the clique capacity in order to obtain a feasible schedule for the links in the clique [87]. 56 Chapter 3. Delay-Throughput Enhancement We formulate the problem of jointly allocating coding rates and sending data rates such that the utility of the network be maximized. The utility of each session i ∈ I is defined as Ki Ki Ui (α, R) = (1 − w) αik k=1 e∈E 1− aek i Pe −w δik , (3.7) k=1 where δik is as in (3.6). Here, the utility of session i is a weighted trade-off between the session’s aggregate effective throughput and its average delay. It is a trade-off because it can be increased by either increasing the throughput or decreasing the delay. We can tune the importance of delay by changing its weight, w. By increasing w, we move on the trade-off curve towards decreasing delay at the cost of decreasing the throughput. We define the utility of the network as either the summation of all utilities of data sessions i ∈ I, or just the one with the minimum value. Maximizing the Aggregate Utility of the Network This problem is formulated as Ki Ki maximize α 0, 0≺R R0 subject to (1 − w) αik i∈I k=1 Ki k aek i αi e∈Q i∈I k=1 δik ≤ δimax , e∈E 1 − aek i Pe − w Re−1 c−1 e ≤ ν, δik i∈I k=1 Q ∈ Q, i ∈ I, k = 1, . . . , Ki , (3.8) where δimax is the maximum delay that can be tolerated for each path of session i ∈ I. The set of constraints declare that the portion of time that all links in a maximal clique are active must be less than the clique capacity. The expressions for Pe and δik are as in (3.2) and (3.6), respectively. 57 Chapter 3. Delay-Throughput Enhancement Maximizing the Minimum Utility of the Network This problem is formulated as Ki Ki maximize min(1 − w) α 0, 0≺R R0 i∈I αik k=1 e∈E 1− aek i Pe −w δik k=1 Ki subject to e∈Q i∈I k=1 k −1 −1 aek i αi Re ce ≤ ν, δik ≤ δimax , Q ∈ Q, (3.9) i ∈ I, k = 1, . . . , Ki . Unlike (3.8), here the design addresses the notion of maxmin fairness among sessions. 3.3 Delay-aware Optimal Data Rate and Coding Rate Allocation The optimization problem in (3.8) is non-convex and non-separable due to the product forms in the objective function with respect to the effective throughput, the fractional forms in the first set of constraints and in the delay constraints in (3.6), the exponential forms in the objective function with respect to error probabilities, the non-separability of reliability and throughput due to multipath routing, and the coupling across variables because of delay constraints and channel coding. Most of the above properties are due to the fact that we consider multipath routing and wireless interference. For example, if we assume there is no interference, which is true for wired networks, the clique capacity constraints would reduce to linear link capacity constraints for any link e ∈ E: 1 Re ce Ki Ki aek i i∈I k=1 αik ≤ 1, ⇒ i∈I k=1 k aek i αi − Re ce ≤ 0. (3.10) 58 Chapter 3. Delay-Throughput Enhancement We can also show that the non-convexity due to the product forms in the objective function can be resolved if there is only a single routing path for each session [22]. However, all sources of complexity remain in place when multipath routing is used and wireless transmissions are subject to interference. In the following, we use various techniques to overcome the complexity of the problem formulation and convert problem (3.8) into a convex problem. Consider the exponential form of Pe in (3.2). For notational simplicity, we can rewrite (3.2) as Pe = Xe exp (Z Re ) for each link e ∈ E, where Xe = 2−T R0e and Z = T ln 2. We ∞ (Z Re )n . n=0 n! can use Taylor series expansion and rewrite the above equation as Pe = Xe Clearly, for some bounded integer Ne ≫ 1, we can approximate Pe as Xe Ne (Z Re )n n=0 n! for each link e ∈ E. We investigate the value of Ne necessary for obtaining a good approximation through simulation. If the error probabilities Pe are small, we can rewrite the receiving rates in each session as Ki Ki αik k=1 e∈E 1− aek i Pe ≈ αik k=1 1− aek i Pe . (3.11) e∈E Due to the polynomial forms in the objective function and the constraints, we can solve problem (3.8) by using geometric programming techniques. In this respect, using the approximated value for Pe , we replace (3.11) in the objective function of problem (3.8) and introduce variable t such that t is a lower-bound for the objective function. That is, Ki t + (1 − w) i∈I k=1 Ne n αik aek i Xe (ZRe ) +w n! e∈E n=0 Ki Ki i∈I k=1 δik ≤ (1 − w) αik . (3.12) i∈I k=1 Then, we follow the signomial programming techniques [83] to approximate the polynomial in the right-hand side of (3.12), which is only a function of α, as a monomial, i.e., a polynomial with only one term and positive multiplier. This approximation can be done 59 Chapter 3. Delay-Throughput Enhancement ˆ For a parameter fs > 1, which is close to 1, we have around some initial point α. Ki′ i∈I k=1 Ki Ki Ki αik ≈ α ˆ ik i∈I k=1 i∈I k=1 αik α ˆ ik α ˆ ki / ′ i′ ∈I k ′ =1 α ˆ ik′ (3.13) ˆ s , fs α] ˆ , , ∀ α ∈ [α/f ˆ s , fs α] ˆ is a small neighborhood around initial point α. ˆ For notational convewhere [α/f ˆ which only depends on the initial point α, ˆ −1 = ˆ as Λ nience, we define Λ, i∈I Ki ˆ ik k=1 α . ˆ as Then inequality (3.12) can be approximated around the initial point α Ki ˆ Λ 1−w t + (1 − w) Ne i∈I k=1 e∈E n=0 n αik aek i Xe (Z Re ) +w n! Ki Ki δik i∈I k=1 i∈I k=1 αik α ˆ ik ˆ −α ˆ ki Λ ≤ 1. (3.14) The above constraint is a posynomial, i.e., a polynomial with only positive terms. Posynomials are the building blocks in geometric programming [83]. By minimizing t−1 , we maximize the objective function in (3.8). To tackle the fractional forms in the delay constraints, we can write (3.6) in an inequality form L δik ≥ 2 e∈E aek i 2 + ce Re Ki′ ′ ′ k aek i′ α i′ i′ ∈I k ′ =1 ce Re − Ki′ ek ′ i′ a α i′ ∈I k ′ =1 k′ i′ . (3.15) for each i ∈ I, k = 1, . . . , Ki . It can be shown that (3.15) is always satisfied with equality for the optimal solution. This can be proved by contradiction. Assume that (3.15) is not satisfied with equality in the optimal solution for some i and k. Note that δik is not lower bounded in any other set of constraints. Therefore, we can decrease δik such that the corresponding constraint is satisfied with equality. This leads to further increasing the value of the objective function by choosing a solution different than the optimal solution 60 Chapter 3. Delay-Throughput Enhancement which is a contradiction. That is, it is an active inequality constraint. For each link e ∈ E, we introduce new variables Ye such that K ′ ′ i −1 k Ye−1 ′ αi′ Re aek + ≤ 1, i′ ce c e ′ ′ i ∈I k =1 ∀ e ∈ E. (3.16) We can show that (3.15) is satisfied if (3.16) holds and we have δik L ≥ 2 aek i e∈E Ye 2 + ce Re i′ ∈I Ki′ k ′ =1 ce Re2 ′ ′ k aek i′ αi′ ∀ i ∈ I, k = 1, . . . , Ki . , (3.17) Similarly, we can show that (3.16) and (3.17) are always satisfied with equality for the optimal solution. By introducing t as in (3.14) and adding constraints (3.16), and (3.17) to the constraints of problem (3.8), it is equivalent to the problem (3.18) in which the objective is to minimize t−1 which is equal to maximizing t where t is declared to be a lower bound for the network utility function in the first set of constraints. The second set of constraints declare the capacity constraints and the third and fourth set are active constraints (3.17) and (3.16), respectively. The last set of constraints guarantees all end-to-end delays to be bounded: minimize ˆ 0≺R R0 ,δ≻0,Y ≻0 ˆ s α fs α, t>0,α/f t−1 subject to Ki ˆ Λ 1−w t + (1 − w) n αik aek i Xe (ZRe ) n! i∈I k=1 e∈E n=0 Ki αik k δi α ˆ ik i∈I k=1 i∈I k=1 Ki +w Ne ˆ −α ˆ ki Λ ≤ 1, 61 Chapter 3. Delay-Throughput Enhancement 1 ν Ki e∈Q i∈I k=1 L 2 e∈E k −1 −1 aek i αi Re ce ≤ 1, aek i (2Re−1 + Re−2 Ye ce ∀ Q ∈ Q, Ki′ ′ ′ k k aek i′ αi′ )δi −1 i′ ∈I k ′ =1 ≤ 1, ∀ i ∈ I, k = 1, . . . , Ki , Ye−1 + ce Ki′ ′ i′ ∈I k ′ =1 ′ −1 k aek i′ Re αi′ ≤ 1, δik ≤ δimax , ∀e ∈ E, (3.18) ∀ i ∈ I, k = 1, . . . , Ki . Problem (3.18) is a standard geometric programming problem that can be converted into a convex optimization problem [83] and can be solved around an initial point. It has been shown that iteratively solving (3.18) converges to the optimal solution of problem (3.8) [83]. In each iteration, (3.18) is initialized with the optimal solution of the problem corresponding to the last iteration. As discussed, we may move on the throughput-delay trade-off curve by tuning the delay importance weight w. w must be chosen such that the objective function in problem (3.8) remains positive. Similarly, we can convert problem (3.9) into a convex optimization problem. Compared to solving problem (3.8), there are two differences. First, variable t is introduced such that Ki t ≤ (1 − w) Ne αik k=1 1− aek i Xe e∈E K i (Z Re )n − w δik , ∀ i ∈ I. n! n=0 k=1 (3.19) As in the earlier case, we use signomial techniques to convert (3.19) into a constraint in the standard form of geometric programming problems. By applying a similar technique 62 Chapter 3. Delay-Throughput Enhancement in (3.13) this time to Ki k=1 Ki Ne ˆi Λ 1−w αik , we can rewrite (3.19) as K i n αik aek i Xe (Z Re ) +w δik t + (1 − w) n! k=1 k=1 e∈E n=0 Ki k=1 αik α ˆ ik ˆi −α ˆ ki Λ ≤ 1, ∀ i ∈ I, (3.20) ˆ −1 = ( where Λ i Ki ˆ ik ). k=1 α Second, inequalities (3.16) and (3.17) may not be active anymore and so inequality (3.15) may not be satisfied with equality. In this case, we are in fact dealing with the upper bounds of the average end-to-end delay in the objective function. In this way, the performance of the network is better than what we would expect from the obtained solution in terms of average delay since the upper bounds on the average delay are used in the objective function. The rest of the formulation is the same as the one in (3.18). Again, w must be chosen such that the objective function in problem (3.9) remains positive. 3.4 Numerical Results In this section, we numerically solve problem (3.8) to determine the optimal sending and coding rates such that the utility of the network (i.e., the trade-off between the aggregate effective throughput and the average delay) is maximized. We show that maximizing the aggregate network utility leads to higher benefits in the throughput-delay trade-off (i.e., we obtain lower delays at the cost of lower decrease in throughput), compared to the case of maximizing the minimum utility in the network. In the former case, no fairness is achieved and some sessions may be starved. Therefore, we also solve problem (3.9) to determine the sending rates and coding rates such that the minimum utility of the network is maximized. We show that at the cost of loosing some gain in the throughput-delay trade-off we can provide fairness among all sessions. In our set of simulations, we use T = 10, L = 8000 bits, ce = 11 Mbps, Ne = 15, fs = 1.1, R0e = 1, and ν = 2 3 [87]. The proper values for 63 Normalized Average Delay of the Network Chapter 3. Delay-Throughput Enhancement 1 w=0 0.9 0.8 w = 0.0000125 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 Delay Importance Weight w Figure 3.2: The average delay decreases as its importance weight in the objective function increases. Delay values are normalized over the corresponding values for which w = 0. We observe a decrease of almost 58% when w = 0.5. parameters Ne and fs are obtained from simulations. We solve problem (3.8) for different values of w in a feasible range across 50 different random topologies. Each random topology is a 5 × 5 grid topology for which 20 nodes are placed in random locations. Five pairs of nodes are randomly selected as the source and destination pairs. We observe that by considering the delay in the objective function, even with a small weight, we can decrease the average delay by 37% compared to the case with no delay consideration (Fig. 3.2). We also note that by further increasing the importance weight of delay in the objective function the average delay decreases by 58%. The more a link is utilized, the higher will be the queuing delays for that link. Therefore, decreasing the average delay leads to the use of the intermediate links at a lower rate that in turn leads to a slight decrease (0.1%) in aggregate throughput. This confirms the delay-throughput trade-off. We can also see that by decreasing the throughput by a small amount, the delay decreases dramatically at the starting point. This is because delay is an exponential function of the utilization rate. Maximizing the total throughput usually requires sacrificing fairness among sessions. That is, some sessions may starve while some other sessions use the network with a higher throughput. For instance after solving problem (3.8) for a sample topology, we observe 64 Normalized Maximum Delay in the Network Chapter 3. Delay-Throughput Enhancement 1 w=0 0.9 w = 0.0000125 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 Delay Importance Weight w Figure 3.3: The normalized maximum delay among the users in the network decreases as the corresponding importance weight in the objective function increases. Delay values are normalized over the values corresponding to w = 0. We observe almost 37% decrease in the maximum delay in the network when w reaches 0.5. that sessions 1 and 3 use the network at a rate of 2 Mbps while sessions 2 and 5 starve and session 4 sends data at a rate of 4.5 Mbps. To provide fairness among sessions, we solve problem (3.9) to maximize the minimum utility across sessions for different feasible choices of parameter w and for 50 randomly selected topologies. Maximizing the minimum utility of the network, we expect that there will be no session with starvation. We can see that the normalized maximum end-to-end delay in the network among all routing paths decreases by almost 5% on average when we consider the delay only by a very small weight (Fig. 3.3). We can further decrease the delay by 37% when w increases. Again, there exists a trade-off between the maximum end-to-end delay of the network and the aggregate throughput of the session with the minimum aggregate throughput in Fig. 3.4. By tracing the graph starting from the upper right corner (w = 0) to the lower-left corner (w = 0.5), we gain a 37% improvement in the maximum delay at a cost of a slight decrease at only 11% in the minimum throughput when we are in proper points of the curve. We use Jain’s fairness index to quantitatively measure the fairness of the throughput attained among different unicast sessions. Let Ψ denote Jain’s fairness index. We have Ψ= ( |I| xi )2 2, i∈I xi i∈I where xi denotes the total effective throughput of flow i ∈ I from (3.3). 65 Chapter 3. Delay-Throughput Enhancement Normalized Minimum Throughput in the Network 1 w=0 0.98 w = 0.11 0.96 w = 0.27 0.94 0.92 w = 0.5 0.9 0.88 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 Normalized Maximum Delay in the Network Figure 3.4: The trade-off between the maximum delay and the minimum throughput in the network. We may move on the curve by tuning w, the delay importance weight. Delay and throughput are normalized over their corresponding values at w = 0. 1 0.9 Fairness Index ψ 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 Maxmin Fairness Aggregate Utility Maximization 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 Delay Importance Weight w Figure 3.5: Fairness index is shown for both problem (3.8) (aggregate utility maximization) and problem (3.9) (maxmin fairness). We can see in Fig. 3.5 that fairness is improved when the resource allocation is based on the solution of problem (3.9). By now, we considered the normalized values of delay over their value when w = 0 (delay is not considered). It is interesting to see how the average maximum delays in the network change under different delay guarantees. We solve problem (3.9) without considering the last set of constraints (delay guarantee constraints), and also when δimax is 10 ms and 20 ms for all i ∈ I (Fig. 3.6). We can see that the delay is guaranteed to be less than δimax . 66 Chapter 3. Delay-Throughput Enhancement Maximum Delay in the Network (ms) 16 Without delay guarantee Maximum delay of 20 ms Maximum delay of 10 ms 15 14 13 12 11 10 9 8 7 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 Delay Importance Weight w Figure 3.6: Average maximum delay is shown when there is no guarantee on the maximum delay, there is a guarantee of 10 ms, and 20 ms. Since the guarantee is imposed on the upper bound of the delay, the delay may not reach the guaranteed value. As mentioned earlier, the decrease in delay is gained at the cost of decreasing the utility of the links which in turn leads to a decrease in the overall throughput. This throughput degradation can be compensated for by using channel coding. To determine the effect of channel coding, we consider the throughput-delay trade-off in a network in which channel coding is not performed and we study how this can affect the network performance. We assume a packet error rate of 30% at each link and solve problem (3.9) without channel coding to show how it affects the performance. By increasing the weight of delay, we can only decrease the maximum delay by around 3% at the cost of 22% decrease in minimum throughput in Table 3.1. w varies in its feasible range. This shows how performance degrades when channel coding is not used and reveals the importance of channel coding. Table 3.1: The trade-off between the maximum delay and the minimum throughput in the network when channel coding is not being used. w Normalized Maximum Delay Normalized Minimum Throughput 0 0.3 1 0.97 1 0.78 67 Chapter 3. Delay-Throughput Enhancement 3.5 Summary In this chapter, we considered the trade-off between decreasing the end-to-end delay and increasing the aggregate throughput in wireless networks with channel coding and showed that a noticeable enhancement across both design goals is feasible if a combination of multipath routing and adaptive channel coding are employed. We jointly formulated the end-to-end data rate allocation and adaptive channel coding within the general framework of network utility maximization (NUM) under two variations. The first problem is formulated for maximization of the aggregate network utility, i.e., the overall system performance. The second problem is formulated for maximization of the minimum utility among the end-to-end flows to achieve fairness. Due to non-convexities such as in product terms and fractional terms in the objective function and the constraints, the formulated optimization problems are non-convex and non-separable, and difficult to solve. Nevertheless, we introduced an algorithm that can solve the two NUM problems with low computational complexity. Through our simulation studies, we note that, in many cases, significant improvement in end-to-end delay can be obtained with marginal decrease in aggregate throughput, suggesting that satisfying stringent delay requirements can be achieved if multipath routing and adaptive channel coding are employed. The fair resource allocation aspect of our proposed design is of interest in vehicular networks where multiple vehicles share an access point in order to obtain connectivity to the Internet. The centralized solution that we have proposed in this chapter can particularly be used in the case when the stationary access point provides connectivity for all vehicles that it serves. It can also serve as a benchmark for distributed algorithms which are to be developed in future. Nevertheless, a distributed algorithm can support much broader ranges of application types. 68 Chapter 4 Reliability-based Rate Allocation in Wireless Inter-session Network Coding Systems 4.1 Introduction In Chapters 2 and 3, we developed rate allocation algorithms with channel coding and multipath routing to improve the performance of the network. In this chapter, we focus on inter-session network coding for multiple unicast sessions in a wireless network. The target applications are ones that require reliable data transfer (e.g., HTTP, FTP, P2P traffic) in multi-hop wireless mesh networks. Our objective is to increase the network utility and the end-to-end reliability of data transmissions by proper allocation of routing and inter-session network coding rates for each data source in the network. For this purpose, we use the failure probability of intermediate links to calculate the reliability (i.e., the probability that data is successfully received) of various routing and network coding paths. Given the calculated reliability information, we maximize the effective aggregate network throughput by choosing the optimal rate allocation for network coding paths. We use the network utility maximization framework developed by Kelly et al. [33]. To the best of our knowledge, there has been no prior work on improving the end-to-end reliability in an 69 Chapter 4. Reliability-based Rate Allocation with Inter-session Network Coding inter-session network coding system among unicast sessions. The contributions of this chapter are as follows: • We develop a recursive algorithm to calculate end-to-end reliability, i.e., the probability of correctly delivering a packet, over each routing and network coding path. This allows us to mathematically model the effective throughput for each unicast session in the network. • We formulate a network utility maximization problem for unreliable inter-session network coding systems. This problem formulation takes into account the network topology, mutual interference among wireless links, session utility functions, and link reliability information. • We propose a distributed algorithm to solve the formulated network utility maximization problem using the proximal method and gradient projection. • Simulation results show that by taking into account the reliability information, the aggregate network throughput can be increased by up to 100% while the aggregate network utility is also improved significantly. Unlike intra-session network coding, there is no dominant coding scheme for intersession network coding. Our inter-session network coding scheme is similar to the scheme by Khreishah et al. [50] for wired networks. We, however, extend that model [50] to the wireless networking case by representing wireless capacity using the contention graph. Our proposed approach is based on cooperation among all network users. Game theoretic analysis of inter-session network coding with non-cooperative users is also studied in [98]. The rest of this chapter is organized as follows. The system model is described in Section 4.2. Our algorithm to calculate end-to-end reliability is presented in Section 4.3. We solve the considered network utility maximization problem in Section 4.4 using a distributed 70 Chapter 4. Reliability-based Rate Allocation with Inter-session Network Coding algorithm. Simulation results are presented in Section 4.5. A summary is given in Section 4.6. 4.2 System Model Consider a wireless network modeled as a directed acyclic graph G(V, E), where V is the set of all nodes in the network and E is the set of all wireless links. We denote e = (u, v) ∈ E if and only if d(u, v) ≤ dT , where d(u, v) is the Euclidean distance between nodes u and v, and dT denotes the maximum transmission range. Let S = {1, 2, . . . , S} denote the set of all unicast sessions in the network. Each session i ∈ S is denoted by a tuple (si , ti ), where si and ti denote the source node and the destination node of session i, respectively. 4.2.1 Pair-wise Inter-session Network Coding Following the inter-session network coding model in [45], we model the network graph (i) (i) (i) G(V, E) as a superposition of S routing subgraphs Gr (Vr , Er ) for all i ∈ S and S(S −1) (i,j) (i,j) (i,j) pairwise inter-session network coding subgraphs Gnc (Vnc , Enc ) for all i, j ∈ S such that (i) i = j. For each session i ∈ S, routing subgraph Gr includes all routing paths from source (i) node si to destination node ti . We define Pr as the set of all routing paths Psiti in (i) graph Gr , where Psi ti denotes a path from source si to destination ti . We also define (i) (i) (i) Nr = |Pr |. Furthermore, for each k = 1, . . . , Nr , we define ǫek i = 1 if link e belongs to the k th routing path of session i; otherwise, ǫek i = 0. (i,j) For any two sessions i, j ∈ S, we define Pnc (i,j) in graph Gnc as the set of all triples {Psi ti , Psj tj , Psj ti } such that at most two of the three paths Psiti , Psj tj , and Psj ti share the (i,j) same link. We define Nnc (i,j) = |Pnc |. For a pair of sessions i and j, we construct subgraph (i,j) lm lm th Glm triple path in Pnc ij (Vij , Eij ) by the union of the l (j,i) and the mth triple path in Pnc . The graphs Glm ij can be used to implement inter-session network coding (cf. [45, 50]) as we 71 Chapter 4. Reliability-based Rate Allocation with Inter-session Network Coding (a) (b) Figure 4.1: (a) An example directed acyclic network graph with 6 nodes and 7 links. One data session exists between s1 and t1 and another one exists between s2 and t2 . (b) The corresponding (undirected) contention graph. explain in the following example. Consider the network in Fig. 4.1(a), where V = {s1 , s2 , v1 , v2 , t1 , t2 } and E = {e1 , e2 , e3 , e4 , e5 , e6 , e7 }. This network topology is sometimes referred to as the butterfly network [45, 47–50]. We can see that there is only one routing path from s1 to t1 in Fig. 4.1(a), denoted by (e1 e4 e7 ). Similarly, there is only one routing path from s2 to t2 , denoted by (1) (e2 e4 e6 ). Therefore, sets Pr (1,2) other hand, set Pnc (2,1) Pnc (2) and Pr (1) (2) have only one member and Nr = Nr = 1. On the has one member, denoted by triple {e1 e4 e7 , e2 e4 e6 , e5 }. Similarly, set (1,2) has one member, denoted by triple {e2 e4 e6 , e1 e4 e7 , e3 }. Therefore, Nnc (2,1) = Nnc = 1. 11 Furthermore, graph G11 12 = G21 = G. To implement network coding, node v1 jointly encodes packets it receives from source nodes s1 and s2 . The encoded packets are then transmitted to receiver nodes t1 and t2 via node v2 . Node t1 can decode the received packets using the remedy data it receives from node s2 over side link e5 . Similarly, node t2 can decode the received packets using the remedy data it receives from node s1 over side link e3 . Notice that encoding packets at node v1 reduces the required bandwidth on links e4 , e6 and e7 , leading to an increase in network throughput. In a general network, the network coding scheme can be constructed by using the add-up and reset scheme [45]. Here, we assume that the network coding graphs are predetermined. 72 Chapter 4. Reliability-based Rate Allocation with Inter-session Network Coding 4.2.2 Rate Allocation For each session i ∈ S, let αik denote the data rate of source si on the k th routing path in (i) (i) lm subgraph Gr for k = 1, . . . , Nr . Also let αij denote the rate of source si on network (i,j) coding subgraph Glm ij for l = 1, . . . , Nnc (j,i) and m = 1, . . . , Nnc , where j ∈ S\{i}. Clearly, lm ml we must have αij = αji . The aggregate sending rate of source si is obtained as (i) Nr k=1 αik + (i,j) j∈S,j=i Nnc l=1 (j,i) Nnc m=1 lm αij . (4.1) Notice that since the wireless links are prone to error, the effective receiving rate at the destination node ti can be different from the above sending rate at source node si . We will investigate this issue in detail in Sections 4.2.4 and 4.3. Given the sending rates, we can also model the aggregate traffic load on each wireless link e ∈ E as [50]: ue = i∈S (i,j) (i) Nnc Nr (j,i) Nnc k ǫek i αi + k=1 j>i l=1 m=1 lm αij max{Hijel , Hjiem }, (4.2) where Hijel = 1 if link e belongs to at least one path in the lth triple {Psi ti , Psj tj , Psj ti } (i,j) 11 of set Pnc ; otherwise, Hijel = 0. For the network in Fig. 4.1(a), ue1 = ue7 = α11 + α12 , 11 11 11 ue2 = ue6 = α21 + α12 , ue3 = ue5 = α12 , and ue4 = α11 + α21 + α12 . 4.2.3 Interference In a wireless network, where some of the links can interfere with each other, mutual interference can be modeled using a contention graph G′ (V ′ , E ′ ). In a contention graph G′ , the set of vertices V ′ represents the set of all wireless links E in the network graph G. There exists an edge between any two vertices in set V ′ if the wireless links corresponding to the 73 Chapter 4. Reliability-based Rate Allocation with Inter-session Network Coding two vertices mutually interfere with each other. That is, if the receiver of one link is within the interference range of the sender of the other link. Given the contention graph, each complete subgraph, i.e., a subgraph in which all vertices are connected, is called a clique. A maximal clique is defined as a clique which is not a subgraph of any other clique. We denote the set of all maximal cliques in contention graph G′ by Q. Each maximal clique is denoted by Qn ∈ Q for n = 1, . . . , |Q|. Only one link among all the links corresponding to the vertices of a maximal clique can be active at a time. Let ce denote the nominal data rate of link e ∈ E. The ratio ue ce denotes the portion of time that each link e ∈ E would be active. It is required that ue e∈Qn ce ≤ γ, (4.3) ∀Qn ∈ Q, where γ ∈ (0, 1] is called the clique capacity. It is common practice to select γ = 2 3 [87]. For the network in Fig. 4.1(a), the corresponding contention graph is shown in Fig. 4.1(b). We can see that the contention graph includes three maximal cliques. They impose three constraints. For instance, clique Q1 = {e1 , e2 , e4 , e6 , e7 } requires that u1 + uc22 + uc44 + uc66 + uc77 c1 ≤ γ. 4.2.4 Link Failure In practice, since the wireless channel between any two neighboring nodes u and v is not perfect due to environmental obstacles and background noise, each link e = (u, v) may have a probability of failure pe ∈ [0, 1] with which packets sent by node u are corrupted and not received by receiver node v correctly. We model the wireless channels as binary erasure channels (BEC) [99, p. 187] and assume that data packets transmitted on link e are received successfully at the receiver node with probability 1 − pe . The failure probability vector of all links in the network p = (pe , e ∈ E) is assumed to be known through measurements 74 Chapter 4. Reliability-based Rate Allocation with Inter-session Network Coding (e.g., by probe transmissions). Given the link failure probability vector p, we can further obtain the end-to-end failure probability for each routed or network coded packet. For each session i ∈ S, let Pik denote the end-to-end reliability (i.e., 1 minus failure probability) for a packet that is routed over (i) the k th routing path, where k = 1, . . . , Nr . Furthermore, for each pair of sessions i, j ∈ S, let Pijlm denote the end-to-end reliability for a network coded packet that is transmitted over network coding subgraph Glm ij . The aggregate receiving rate at destination ti is obtained as (i) Nr k=1 αik Pik + (i,j) Nnc l=1 j∈S,j=i (j,i) Nnc m=1 lm lm αij Pij . (4.4) We will discuss in detail how the end-to-end reliability can be calculated in Section 4.3. 4.2.5 Network Utility Maximization Formulation (i) lm for all i, j ∈ S, all k = 1, . . . , Nr , all Let us concatenate all sending rates αik and αij (i,j) (j,i) l = 1, . . . , Nnc , and all m = 1, . . . , Nnc and denote the resulting vector as α. The network utility maximization problem for unreliable wireless networks with inter-session network coding among multiple unicast sessions can be formulated as max α 0 subject to i∈S Ui e∈Qn (i,j) (i) Nnc Nr (j,i) Nnc αik Pik + k=1 ue ≤ γ, ce lm ml αij = αji , j∈S,j=i l=1 m=1 lm lm αij Pij ∀ Qn ∈ Q ∀ i, j ∈ S, i = j (i,j) (j,i) l = 1, . . . , Nnc , m = 1, . . . , Nnc , (4.5) where ue for each e ∈ E is as in (4.2), and for each session i ∈ S, Ui (·) denotes a strictly concave and increasing utility function. For example, utility functions can be logarithmic. In that case, the utility maximization problem (4.5) becomes a proportionally fair resource 75 Chapter 4. Reliability-based Rate Allocation with Inter-session Network Coding allocation problem [100]. Also notice that if Ui (x) = x, then problem (4.5) reduces to a throughput maximization problem. 4.3 End-to-End Reliability Recall from Section 4.2.4 that the aggregate receiving rate of data at receiver node ti for each i ∈ S is as in (4.4), where Pik and Pijlm are end-to-end reliabilities for all routing and network coding paths for session i. In this section, we develop an algorithm to obtain these end-to-end reliability measures. (i) (i) For each session i ∈ S, consider the k th routing path in graph Gr for k = 1, . . . , Nr . The probability that data is transmitted successfully along this path can be obtained as Pik = ek e∈Er ǫi (1 − pe ) . (4.6) For the network in Fig. 4.1(a), we have P11 = (1 − pe1 )(1 − pe4 )(1 − pe7 ) and P21 = (1 − pe2 )(1 − pe4 )(1 − pe6 ). Obtaining the end-to-end reliability of pairwise inter-session network coding paths is more complex due to the overlapping among different paths and the fact that an encoded packet is successfully received only if the corresponding remedy data is also received successfully. To explain our model, let us consider the example network in Fig. 4.1(a). Node t1 can successfully receive some data in a network coding setting if and only if all of the following three conditions hold: (a) Intermediate node v1 successfully receives the data packets from both source nodes s1 and s2 over links e1 and e2 , respectively. This happens with probability (1 − pe1 )(1 − pe2 ). (b) The encoded packet is successfully received by node t1 over links e4 and e7 . This happens with probability (1 − pe4 )(1 − pe7 ). (c) The remedy packet, corresponding to the data packet, is successfully received by node t1 over link e5 . 76 Chapter 4. Reliability-based Rate Allocation with Inter-session Network Coding This happens with probability (1 − pe5 ). Therefore, we have 11 P12 = (1−pe5 )(1−pe4 )(1−pe7 )(1−pe1 )(1−pe2 ). (4.7) Similarly, we can show that 11 P21 = (1 − pe3 )(1 − pe4 )(1 − pe6 )(1 − pe1 )(1 − pe2 ). (4.8) To generalize the idea to an arbitrary network, recall that for each pair i, j ∈ S, any (i,j) (j,i) m = 1, . . . , Nnc , and any l = 1, . . . , Nnc , inter-session network coding subgraph Glm ij is con(i,j) (j,i) structed as the union of the mth triple path in Pnc and the lth triple path in Pnc . Given lm Glm ij , let ϕv denote the probability that node v ∈ Vij receives an original/encoded/remedy packet correctly. For the simplicity of exposition, we define ϕsi = ϕsj = 1, since the source nodes si and sj have the correct data with probability one. For the network in Fig. 4.1(a), ϕv1 = (1 − pe1 ) × ϕs1 (1 − pe2 )ϕs2 , ϕv2 = (1 − pe4 )ϕv1 , and ϕt1 = (1 − pe7 )ϕv2 × (1 − pe5 )ϕs2 . We can see that there is a recursive relationship on failure probabilities of neighboring nodes. This observation motivates our end-to-end reliability calculation for inter-session network coding algorithm in Algorithm 4.1. For each node v ∈ Vijlm , let in(v) denote the set of in-neighbors (i.e., neighbors with incoming links) of node v in graph Glm ij . Notice that in(v) ⊆ Vijlm \{v}. For each node u ∈ in(v), the directed wireless link from node u to node v is denoted by e = (u, v). In this case, ϕv = u∈in(v) (1 − pe=(u,v) )ϕu . (4.9) Algorithm 4.1 can be used to obtain end-to-end reliability for any arbitrary inter-session network coding subgraph. 77 Chapter 4. Reliability-based Rate Allocation with Inter-session Network Coding Algorithm 4.1 End-to-end reliability calculation for inter-session network coding between (i,j) (j,i) sessions i ∈ S and j ∈ S\{i}, executed for any l = 1, . . . , Nnc and m = 1, . . . , Nnc . lm 1: Set ϕsi = ϕsj = 1, ϕv = −1 for all v ∈ Vij \{si , sj }. 2: while ϕti = −1 do 3: Find node v ∈ Vijlm \{si , sj } such that ϕv = −1 and ϕu = −1 for all neighboring nodes u ∈ in(v). 4: Set ϕv = u∈in(v) (1 − pe=(u,v) )ϕu . 5: end while 6: Pijlm = ϕti 4.4 Reliability-based Rate Allocation In this section, we propose a distributed rate allocation algorithm to solve the network utility maximization problem in (4.5). We define Fijelm = 1 2 max{Hijel , Hjiem } for notational simplicity. In that case, for each clique Qn ∈ Q, where n = 1, . . . , |Q|, the clique constraint in (4.3) becomes e∈Qn i∈S (i) Nr k=1 ǫek i ce (i,j) Nnc αik + j=i l=1 Fijelm lm αij ≤ γ. c e m=1 (j,i) Nnc (4.10) Next, we notice that although the objective function in problem (4.5) is concave, it is not strictly concave due to the linear terms inside each utility function. Thus, problem (4.5) may have multiple optimal solutions. This can pose some difficulties if we require a distributed scheme to solve the optimization problem at hand. To overcome this problem, we use the proximal method [101]: we add some extra terms to the objective function to 78 Chapter 4. Reliability-based Rate Allocation with Inter-session Network Coding make it strictly concave. Then problem (4.5) becomes max α,β 0 i∈S (i,j) (i) Nnc Nr Ui αik Pik + k=1 j=i (j,i) Nnc l=1 (i) Nr m=1 lm lm αij Pij N (i,j) N (j,i) nc nc ai k bi lm − (αi − βik )2 − (αij − βijlm )2 2 2 i∈S k=1 i∈S j=i l=1 m=1 (i) (j,i) (i,j) Nr Nnc Nnc ek Fijelm lm ǫ i k αi + αij ≤ γ, ∀ Qn ∈ Q subject to c c e e j>i l=1 m=1 e∈Q i∈S k=1 (4.11) n lm ml αij = αji , ∀ i, j ∈ S, i = j (i,j) (j,i) l = 1, . . . , Nnc , m = 1, . . . , Nnc , (i,j) where βik and βijlm are auxiliary variables introduced for all i, j ∈ S, l = 1, . . . , Nnc , and (j,i) any m = 1, . . . , Nnc . On the other hand, ai and bi are arbitrary positive coefficients. lm Notice that if βik = αik and βijlm = αij , then the objective function in problem (4.11) reduces to the original objective function in problem (4.5). For notational simplicity, (i) (i,j) we concatenate all βik and βijlm for all i, j ∈ S, k = 1, . . . , Nr , l = 1, . . . , Nnc , and (j,i) m = 1, . . . , Nnc , and denote the resulting vector by β. To solve the modified problem (4.11) via a distributed scheme, we use duality theory [81] and obtain the dual Lagrangian function as L(α, λ, ν, β) = Bi (α, λ, ν, β) + i∈S λn γ (4.12) Qn ∈Q 79 Chapter 4. Reliability-based Rate Allocation with Inter-session Network Coding where Bi (α, λ, ν, β) = Ui ai − 2 (i,j) (i) Nnc Nr αik Pik + j=i l=1 βik )2 bi − 2 k=1 (αik k=1 − (i) − Qn ∈Q e∈Qn k=1 Nnc j=i Qn ∈Q e∈Qn j=i (i,j) (j,i) Nnc l=1 m=1 lm (αij − βijlm )2 ǫek i α k λn ce i (i,j) Nnc (j,i) Nnc lm αij Nnc − m=1 lm lm αij Pij (i,j) (i) Nr Nr − (j,i) Nnc l=1 m=1 (j,i) Fijelm λn ce (i,j) Nnc Nnc (j,i) Nnc ml lm νji αij , lm νijlm αij + j>i l=1 m=1 j<i l=1 m=1 and λ and ν are vectors of Lagrange multipliers corresponding to clique capacity constraints and equality constraints, respectively. Notice that for each clique constraint ue e∈Qn ce ≤ γ, where n = 1, . . . , |Q|, the corresponding Lagrange multiplier is denoted by λn . On the (i,j) lm ml other hand, for each equality constraint αij = αji , where i, j ∈ S, l = 1, . . . , Nnc , and (j,i) m = 1, . . . , Nnc , the corresponding Lagrange multiplier is denoted by νijlm . The dual problem of the primal problem in (4.11) can be obtained as minimize Γ(λ, ν), λ 0,ν where Γ(λ, ν) = maxα 0 L(α, λ, ν, β). (4.13) In dual problem (4.13), the variables are the La- grange multipliers. Problem (4.13) can be solved using the gradient projection method [81]. Notice that since primal problem (4.11) is convex and its constraints are linear, strong duality holds [81, p. 226]. Thus, by solving the dual problem (4.13), the optimal solution of the primal problem (4.11) is readily obtained. However, we want to solve the original network utility maximization problem (4.5). We now explain how the solution to the problem 80 Chapter 4. Reliability-based Rate Allocation with Inter-session Network Coding (4.5) can be obtained. Our proposed distributed algorithm to identify the optimal data rates includes two sub-algorithms which are executed iteratively and alternatively. The first iterative subalgorithm is based on the gradient method which is executed in shorter intervals. This sub-algorithm is used to update the dual variables λ and ν and the primal variables α. On the other hand, the second iterative sub-algorithm is based on the proximal method which is executed in larger intervals. This sub-algorithm is used to update the auxiliary variables β. In our iterative distributed algorithm, the first sub-algorithm forms the inner loop, while the second sub-algorithm forms the outer loop. First Sub-algorithm At each time t = 1, . . . , T , where T denotes the network operation time, source node si for each session i ∈ S updates its data rates individually as αi (t + 1) = argmaxαi 0 Bi (αi , λ(t), ν(t), βi (t)) (4.14) where αi denotes the vector of all transmission rates of session i. Given the new data rates, then for each n such that Qn ∈ Q, for n = 1, . . . , |Q|, dual variable λn is updated as λn (t + 1) =λn (t) + δn (i,j) Nnc i∈S e∈Qn (j,i) Nnc (i) Nr k=1 lm αij (t + 1) + j=i l=1 m=1 ǫek i αik (t + 1) ce + Fijelm ce (4.15) −γ , 81 Chapter 4. Reliability-based Rate Allocation with Inter-session Network Coding where δn is a small constant step size. Furthermore, for each i, j ∈ S, such that j > i, and (i,j) for any l = 1, . . . , Nnc (j,i) and any m = 1, . . . , Nnc , the dual variable νijlm is updated as lm ml νijlm (t + 1) = νijlm (t) + σijlm (αij (t + 1) − αji (t + 1)), (4.16) where σijlm is a small constant step size. Notice that the update equations in (4.15) and (4.16) are based on applying the gradient method to convex problem (4.13). The convergence of (4.14) in our first sub-algorithm follows from the descent lemma [102, p. 639]. In particular, we can show that the first sub-algorithm converges if the following sufficient condition holds: n:Qn ∈Q e∈Qn (i,j) (i) Nnc Nr (j,i) Nnc ǫek + i i∈S k=1 i∈S j=i < 2 min{a1 , . . . , aS , b1 , . . . bS }. l=1 m=1 (Fijelm)2 max δn + max σijlm n:Qn ∈Q i,j>i,l,m (4.17) The key idea is to show that our proposed (joint) distributed algorithm forms a pseudocontraction mapping [102, p. 182]. Details are omitted here for brevity. We notice that for any arbitrary network topology and any arbitrary choice of system parameters, we can always select step sizes δn and σijlm small enough such that the strict inequality in (4.17) holds. Second Sub-algorithm At larger intervals, i.e., large enough such that the first sub-algorithm converges within each interval, the second sub-algorithm simply sets β(t + 1) = α(t). (4.18) 82 Chapter 4. Reliability-based Rate Allocation with Inter-session Network Coding After that, the first sub-algorithm is again triggered, but this time based on the new values of β. We continue alternate operation of the two sub-algorithms until the joint algorithm converges. The convergence is always guaranteed [102, p.232]. Next, we show that the joint algorithm formed by update equations (4.14)-(4.18) results in optimal rate allocation. In this regard, we notice that after convergence of the algorithm, we would have β = α. In that case, the objective value in problem (4.11) reduces to the objective value in problem (4.5) as all the additional terms will become zero. Thus, the obtained data rates, which form the optimal solution to the primal problem (4.11), are also the optimal data rates with respect to the original network utility maximization problem (4.5). Similar to other distributed algorithms in which the problem is decomposed and solved by different nodes, our approach also needs message passing among different nodes. 4.5 Performance Evaluation In this section, we assess the performance of our proposed reliability-based rate allocation algorithm and compare it with the rate allocation algorithm in [50] which does not consider link reliability. In particular, we evaluate how the performance improves if we take into account reliability information. In this regard, we simulate ten different randomly generated wireless topologies. Each topology is randomly selected to include between 10 to 15 wireless nodes. Since, our proposed scheme involves solving a convex optimization problem, it has polynomial complexity and can be implemented in practical systems and larger topologies. In the first experiment, we assume that the utility functions are selected to maximize the network throughput. That is, Ui (x) = x for all i ∈ S. In each topology, one or two links are selected randomly as unreliable links. The failure probability of unreliable links is chosen to be 0.5. This implies that half of the packets transmitted over the unreliable 83 Chapter 4. Reliability-based Rate Allocation with Inter-session Network Coding 0.9 With Reliability Consideration Without Reliability Consideration Aggregate Network Throughput 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 1 2 3 4 5 6 7 Topology Number 8 9 10 Figure 4.2: Aggregate network throughput in all 10 simulated topologies with and without reliability consideration when the utility functions are selected as Ui (x) = x for all i ∈ S. Taking reliability information into account increases the throughput by 36.2% on average, among all ten scenarios. links experience transmission errors and are not received correctly. Simulation results are shown in Fig. 4.2. We can see that reliability considerations can significantly increase the network throughput. Notice that the exact performance gain differs among the topologies. This particularly depends on which link is selected as unreliable link in each topology. For example, the performance is improved by more than 100% for the case of topology 8 while the performance gain is negligible for topology 7. For the latter case, the low performance gain is due to the fact that the selected unreliable link does not carry any significant traffic load in an optimal design, even if it is assumed to be reliable. Therefore, its unreliability does not affect the network performance significantly. On average, among all 10 simulated topologies, accounting for reliability information increases the throughput by 36.2%. Next, we study the impact of changes in the link failure probability. We assume that the failure probability of the unreliable links vary from 0 to 0.5. The former case indicates having reliable links, while the latter case indicates having unreliable links which lose half of the packets. Regarding the choice of utility functions, we consider the two important cases of maximizing the throughput and achieving proportional fairness. For the latter 84 Chapter 4. Reliability-based Rate Allocation with Inter-session Network Coding (a) Aggregate Network Throughput 0.9 With Reliability Consideration Without Reliability consideration 0.85 0.8 0.75 0.7 0.65 0.6 0.55 0.5 0.45 0.4 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 Failure Probability (b) Aggregate Network Utility −6 With Reliability Consideration Without Reliability consideration −6.5 −7 −7.5 −8 −8.5 −9 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 Failure Probability Figure 4.3: Comparison between our algorithm (with reliability consideration) and the rate allocation algorithm which does not use link reliability information: (a) Maximizing the aggregate network throughput. (b) Maximizing the aggregate network utility when the utility functions are logarithmic. case, the utility functions are selected to be logarithmic. Simulation results for the case of topology number 1 are shown in Fig. 4.3. Results for other topologies are similar. We can see that as the link failure probability increases, it becomes more important to take into account the reliability information. From the results in Fig. 4.3(a), if the link failure probability is 0.5, then reliability consideration can increase the throughput by 50%. From the results in Fig. 4.3(b), if the link failure probability is 0.5, then reliability consideration can increase the network utility by 18.4%. Finally, we assess the impact of the choice of utility function on the achieved performance gain. To this end, we consider the following important class of utility functions 85 Chapter 4. Reliability-based Rate Allocation with Inter-session Network Coding 200 With Reliability Consideration Without Reliability consideration Aggregate Network Utility 0 −200 −400 −600 −800 −1000 −1200 −1400 −1600 0 1 2 3 4 5 6 7 8 9 10 ψ Figure 4.4: The impact of changing the utility parameter ψ on the achieved aggregate network utility with and without reliability consideration. [100]: log x, ψ = 1, Ui (x) = x1−ψ , ψ = 1, 1−ψ (4.19) where ψ > 0 is a utility parameter. Simulation results for the case of the first topology when ψ varies from 0 to 10, and the link failure probability is chosen to be 0.5, are shown in Fig. 4.4. Results for the remaining topologies are similar. We can see that reliability consideration always improves the performance for any choice of utility parameter ψ. 4.6 Summary In this chapter, we considered the problem of allocating data rates for all sources in a wireless inter-session network coding system. We focused on a scenario where some of the wireless links are not reliable, i.e., have non-zero failure probability. Using a simple algorithm, we calculated the end-to-end reliability measures of all network coding paths in the network. We then formulated a network utility maximization problem, where the objective function is the sum of the utility functions of all data sessions. We also proposed a distributed iterative algorithm to solve the formulated optimization problem. We proved 86 Chapter 4. Reliability-based Rate Allocation with Inter-session Network Coding the optimality and convergence of our algorithm. Simulation results showed that it is essential to consider link reliability to achieve high throughput. In our evaluations, the network throughput is increased by 36.2% on average with up to 100% performance gain for some scenarios. The proposed scheme also significantly improves aggregate network utility for various choices of utility functions. 87 Chapter 5 Distributed Scheduling in Multihop Wireless Networks with Maxmin Fairness Provisioning 5.1 Introduction In Chapters 2, 3, and 4, we studied rate allocation problems with the goal of improving the network performance in terms of achieving both high throughput and fairness. While the previous results provide an upper bound for performance of the network, they do not address the achievability of the proposed rate allocation solutions through transmission scheduling policies. In this chapter, we consider transmission scheduling in unreliable wireless networks. The network is said to be stable if every node only has a finite number of packets queued for transmission. Stability is subject to the condition that the data transmission rates lie within the network capacity region, i.e., it is feasible to transmit all packets with bounded delay. However, wireless links have limited capacity and may interfere with each other. The variation of the link capacity and network traffic can have an impact on the stability of the network. Another aspect is that wireless links are not as reliable as wired connections, and data packets may be corrupted during transmission. Moreover, without careful resource allocation strategy, certain users may be starved for 88 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning network access whereas others may receive an unfairly large share of the available network bandwidth (e.g., see [1]). This latter aspect relates to fairness. We propose to address such problems through a stable and decentralized scheduling mechanism that allocates resources such that wireless links do not interfere with each other and fairness is provided while maintaining a high network throughput. We shall begin with a discussion of the key ideas and highlight our main contributions. Using a slotted notion of time, we consider link scheduling to determine the active links in each time slot. Lyapunov stability theory has been used to construct stable and optimal decentralized scheduling policies [103]. Lyapunov techniques have also been extended to provide delay guarantee [104]. They are also applicable to throughput maximization [105] and energy minimization in single hop [106] and multihop [107] networks. A utility optimal algorithm with delay consideration using the shortest paths is also developed in [108]. Throughput optimal scheduling in ad hoc networks, which is an NP-hard problem [109], has often been reduced to a rate allocation problem, which only provides an upper bound on the rates that a network can support. Near optimal scheduling algorithms for mobile ad hoc networks have been proposed in [110]. However, fairness is not considered in the above mentioned work. Fairness provisioning has been considered in literature (see Section 1.1.1). However, fairness is provided with maximizing the summation of utility functions corresponding to the individual flows such as in [8]. Our approach is different from all of the above in that the minimum throughput of the network is directly maximized to provide maxmin notion of fairness instead of considering utility functions for different users. We achieve this by using Lyapunov stability theory and constructing virtual queues. In this chapter, we take the advantage of two opportunities offered by multihop networks. First, we employ multiple paths for data flows from the source to the destination. 89 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning Second, we utilize different channel code rates at different links to compensate for variations in link reliability. Our work differs from the previous work in the literature in several aspects. While most of the NUM problems determine the average sending rates [38, 42] at which the objective function is maximized, we propose an efficient scheduling and link activation policy. Our work is also novel because in the related work on fair scheduling [3–8], fairness is improved by maximizing the utility function while we directly maximize the minimum throughput in the network. We will show how this improves the network performance. Maxmin fair scheduling is considered in one hop networks with multi-radio receivers [10]. Optimal maxmin transmission and forwarding rates for sensor networks are studied in [111]. A maxmin fair scheduling policy for one hop multiple-input and multiple-output (MIMO) networks is also considered [112]. Our work is different from the above as we propose a distributed scheduling policy and consider multihop networks with single radio and therefore interference effects are incorporated. In addition, the optimality is analytically proved. While some papers considered channel coding to improve the network throughput [22], no previous work has considered both multipath routing and channel coding in the joint problem of code rate assignment, flow control and decentralized scheduling to achieve maxmin fairness in wireless networks. The main contributions of this chapter are as follows: • We propose a decentralized online scheduling and flow control algorithm, which we call DisF, that aims to provide fairness for each flow by maximizing the minimum throughput in a multihop wireless network. We integrate the use of multipath routing and link-dependent channel code rates in our solution approach to utilize resources better and improve reliability. While we do improve link reliability by using appropriate channel coding, we also assume the use of link-level acknowledgments and 90 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning retransmissions when a node is unable to decode a packet. We demonstrate stability of the proposed algorithm by applying the Lyapunov stability theory. • We develop an optimal centralized rate allocation method using geometric programming, which provides an upper bound on the performance of any decentralized scheduling policy. • We study the performance of DisF and optimal centralized algorithms through simulations over multiple random topologies. We show that the DisF algorithm ensures stability, whenever feasible, and that its performance is comparable to that of the centralized optimal solution. We also compare DisF with Lyapunov stability-based algorithms, which do not consider fairness in their design. Next, we show that the use of different channel code rates can improve the performance of the network. We also compare DisF with a class of existing approaches which use utility functions to provide maxmin fairness through simulations [8]. This chapter is organized as follows. The system model is described in Section 5.2. The decentralized stable algorithm is developed in Section 5.3. The centralized approach is formulated as a geometric programming problem and it is solved in Section 5.4. In Section 5.5, the algorithm is evaluated through simulations and the chapter is summarized in Section 5.6. 5.2 System Model We model the wireless network with a graph G(N , E), where N represents the set of N = |N | wireless nodes and E denotes the set of directed wireless links. Link e = (m, n) ∈ E connects two nodes m, n ∈ N if and only if node n is in the transmission range of node m. We use the notations e and (m, n) interchangeably. The set of data flows is denoted by F 91 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning and the number of data flows is denoted by F = |F |. The set of source nodes is denoted by S. Data transmission between a source sf ∈ S and the destination df of flow f ∈ F can be relayed through multiple hops. We use multipath routing for data transmission. The set Kf contains Kf = |Kf | routing paths for flow f ∈ F . For each link e ∈ E, path k ∈ Kf , and flow f ∈ F , we define afe k = 1 if link e belongs to the k th routing path for flow f , and afe k = 0, otherwise. For any node n ∈ N , each data flow f ∈ F , and any path k ∈ Kf , let ifnk and ofnk ∈ E be the input and output links to and from node n on path k of flow f , respectively. Whenever the context is clear, we remove the indices n, f, k and denote the input and output links with i and o, respectively (see Fig. 5.1). A slotted notion of time is used with time slots t ∈ {1, 2, . . .}. We denote the value of time-varying parameters at the beginning of each time slot t with the index t. We use the same parameter without the index t to denote its average value over all time slots. At each intermediate node n ∈ N , we assume a separate queue for any path k ∈ Kf of flow f ∈ F . The number of data bits corresponding to path k for flow f , stored in node n is denoted as Qfnk (t). We assume Qfdfk (t) = 0, ∀ t, k ∈ Kf , f ∈ F since the received bits are transfered to the upper layers at the destination node df . We incorporate all the queue backlogs in the vector Q(t) = (Qfnk (t), ∀ n ∈ N , k ∈ Kf , f ∈ F ). We use link-dependent channel code rates to counter channel variations and improve network reliability. Each source node or intermediate node n ∈ N for any flow encodes data bits by adding redundant bits and transmitting the resultant codeword of length g. Hereafter, we assume each packet consists of one codeword and we use the terms packet and codeword interchangeably. We define the code rate Re (t) as the ratio of the data bits to the total transmitted bits (data plus redundant bits) on link e ∈ E. We concatenate code rates for all links e ∈ E in vector R(t) = (Re (t), ∀ e ∈ E). The smaller the code rate 92 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning Figure 5.1: (a) Path k of flow f from node sf to node df which uses node n as a relay node is shown. It is shown that solid link 1 is active (µf1 k (t) = 1) while dotted links 2 and 3 are not active (µf2 k (t) = µf3 k (t) = 0) in that particular time slot t. Note that links 1 and 2 belong to the mentioned path (af1 k = af2 k = 1) but link 3 does not (af3 k = 0). (b) A relay node n is shown with its input link i and its output link o corresponding to the k th path of flow f . The corresponding packets are stored in Qfnk before they are sent. Re (t), the greater number of redundant bits is added, and the higher the reliability is. The reliability is gained at the cost of increased network traffic. When Re (t) is equal to one, channel coding is not used on link e. We use R0e ≤ 1 to denote the cut-off rate of wireless link e ∈ E. The cut-off rate is a channel parameter to which the rate of the adopted coding scheme is always limited [85]. In general, R0e depends on the particular modulation scheme which is being used and also the signal-to-noise ratio (SNR) in the receiver node. For example, for a binary phase shift keying (BPSK) waveform [85], we have R0e = 1 − log2 (1 + e−γe ), where γe denotes the SNR at the receiver node of wireless link e ∈ E. When γe is relatively large, R0e is close to 1. Given Re (t) ≤ R0e for e ∈ E, we have Pe (t) ≥ 1 − 2−g(R0e −Re (t)) , (5.1) 93 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning where Pe (t) is the probability that a codeword of length g is received correctly on link e with rate Re (t) [85, pp. 392-397]. The vector P (t) = (Pe (t), ∀ e ∈ E) represents the successful probabilities on all links e ∈ E. For the rest of this chapter, we consider the worst case in which inequality (5.1) is satisfied with equality. For each transmission on link e ∈ E, we define ρe (t) = 1 if the packet is transmitted successfully and ρe (t) = 0 otherwise. We have ρe (t) = 1 with the probability of Pe (t). We define ρ(t) = (ρe (t), e ∈ E) as the channel state at time slot t. As mentioned above, a codeword may be corrupted with probability 1 − Pe (t) through a transmission on link e ∈ E. The receiver at link e sends a link-level acknowledgement (ACK) to the transmitter if the packet is received correctly. The transmitter retransmits the packet if no ACK is received within a predefined time period. Retransmissions ensure that packets admitted to the network will be received at their corresponding destination nodes. This is at the cost of increased network load. We denote the number of data bits which are admitted to the path k ∈ Kf of flow f ∈ F at the beginning of time slot t as αfk (t). The vector α(t) = (αfk (t), ∀ k ∈ Kf , f ∈ F ). Suppose all admissions are upper bounded (i.e., αfk (t) ≤ αmax ). We assume that all source nodes are backlogged (i.e., each source node has at least αmax data bits available to send over each of its routing paths at any time slot). We define the capacity region Λ as the closure of the set of all sending rate vectors α (considering all possible routing and scheduling policies), for which the network is stable, that is Λ= α|α 0, lim sup t→∞ 1 t t−1 E{Qfnk (τ )} < M τ =0 k∈Kf , f ∈F , n∈N where M is a finite number. Note that α = lim 1t t→∞ t−1 τ =0 , (5.2) α(τ ) is the time average value of α(t). 94 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning Two links e1 , e2 ∈ E mutually interfere with each other if and only if the receiver of one link is in the transmission range of the sender of the other. At each time slot t, only one wireless link may be active among those wireless links which are in mutual interference with each other. We define µfe k (t) = 1 if link e is active in data transmission for the k th routing path of flow f at time slot t, and µfe k (t) = 0 otherwise. We define ce as the number of bits that can be transmitted by link e ∈ E in each time slot t. ce contains data bits as well as redundant bits due to channel coding. A small section of the modeled network is depicted in Fig. 5.1. 5.3 Decentralized and Stable Scheduling In this section, we tackle the problem of online flow control and scheduling for wireless links. We address maxmin fairness provisioning by maximizing the minimum throughput in the network. Our goal is to solve the following problem maximize min αf f ∈F (5.3) subject to α ∈ Λ. The goal in problem (5.3) is to admit new packets and schedule the transmissions such that the minimum sending rate αf = k∈Kf αfk over all flows f ∈ F is maximized and all queues in the network remain stable, that is the number of bits stored in any queue is bounded. Note that data bits are removed from the queue of the sender node only after it has received an ACK from the receiver. Therefore, if the queues are stable, the sending rate of each flow is the same as its throughput at the corresponding destination. To enhance the minimum throughput of the network, we need to introduce a decision parameter λ(t) and a set of virtual queues Zf (t), ∀ f ∈ F . We denote Z(t) = (Zf (t), ∀ f ∈ 95 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning F ). For each virtual queue Zf (t) for flow f at each time slot t, we set k∈Kf αfk (t) as the service rate and λ(t) as the input rate. Then, we have the following update equation: Zf (t + 1) ≤ max Zf (t) − k∈Kf αfk (t), 0 + λ(t). (5.4) Suppose λ(t) is upper bounded (i.e., λ(t) ≤ λmax for any time slot t) and its time average λ = limt→∞ t−1 τ =0 E{λ(τ )} t exists. We will show later that burstiness in the network increases when λmax increases. The stability of each virtual queue Zf implies that the time average of its input rate is less than or equal to that of its service rate. That is λ≤ where αfk = limt→∞ t−1 τ =0 E{αkf (τ )} t k∈Kf αfk , (5.5) is the time average value of αfk (t). Therefore, if all virtual queues are stable, maximizing the time average value of λ(t) is equivalent to maximizing the minimum throughput among all data flows in the network. The goal is to maximize the time average value of λ(t) such that both real queues (which store the data bits) and virtual queues remain stable. We now present some aspects of Lyapunov stability theory [103] that are useful for developing our scheduling algorithm. Let Lyapunov function L(Θ(t)) be a non-negative function of any queue vector Θ(t). We define the Lyapunov drift △(Θ(t)) E{L(Θ(t + 1)) − L(Θ(t)) | Θ(t)}. Proposition 5.1 (Lyapunov Optimization [103]) Let u(t) be a utility function and B > 0, ǫ > 0, and V > 0 be constants such that for all time slots t and queue vector Θ(t) = 96 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning (Θq (t) | q ∈ ∐ = {1, 2, . . . , |∐|}), we have △(Θ(t)) − V E{u(t) | Θ(t)} ≤ B − ǫ q∈∐ Θq (t) − V u∗ , (5.6) where u∗ is a target value for utility function u(t), then we have uinf ≥ u∗ − B/V, 1 lim sup t→∞ t where uinf = limt→∞ inf 1 t t−1 τ =0 q∈∐ E{Θq (τ )} ≤ t−1 τ =0 E{u(τ )} B + V (usup − u∗ ) , ǫ and usup = limt→∞ sup 1t t−1 τ =0 E{u(τ )}. The proof of the proposition can be found in [103, pp. 82-84]. Note that the expectation is over random parameters such as channel states and possibly randomized scheduling policies. Let u(t) = λ(t). We concatenate the backlog queues and virtual queues in the vector Θ(t) = (Q(t), Z(t)). Proposition 5.1 states that if condition (5.6) holds under a scheduling algorithm, then all the queues in Θ(t) are stable and λ will be at most B/V away from the target value λ∗ . Stability of virtual queues Z ensures that λ is always less than or equal to the minimum throughput of the network. By increasing V , we can get closer to the target value at the cost of a linear increase in the congestion in the network. Next, we obtain △(Θ(t)) for any time slot t. We define L(Θ(t)) = n∈N , k∈Kf , f ∈F 2 Zf2 (t) Qfnk (t) + . 2 2 f ∈F (5.7) We assume that scheduled transmissions occur at the beginning of each time slot. For an 97 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning intermediate relay node n ∈ N , n = sf , any path k ∈ Kf and flow f ∈ F , we have Qfnk (t + 1) ≤ Qfnk (t) − min[Qfnk (t), co Ro (t)]µfo k (t)ρo (t) + ci Ri (t)µfi k (t)ρi (t) = max[Qfnk (t) − co Ro (t)µfo k (t)ρo (t), Qfnk (t)(1 − µfo k (t)ρo (t))] (5.8) + ci Ri (t)µfi k (t)ρi (t). For source node sf ∈ S, f ∈ F and k ∈ Kf , we have Qfsfk (t + 1) ≤ Qfsfk (t) − min[Qfsfk (t), co Ro (t)]µfo k (t)ρo (t) + αfk (t) = max[Qfsfk (t) − co Ro (t)µfo k (t)ρo (t), Qfsfk (t)(1 − µfo k (t)ρo (t))] + αfk (t). (5.9) Lemma 5.1 For any ρ ∈ {0, 1}, U, R, and µ ∈ {0, 1} we have max[U − Rµρ, U(1 − µρ)] ≤ max[U − Rµ, 0] + Rµ(1 − ρ). (5.10) Proof Let µ be equal to one. We verify the inequality in both cases when U ≥ R and when U < R separately. If U ≥ R, then we have U(1 − ρ) < U − Rρ and both sides of (5.10) are equal to U − Rρ. On the other hand, if we have U < R, the left hand side of (5.10) is U(1 − ρ) and the right hand side is R(1 − ρ) and the inequality is verified. In the case where µ = 0, inequality (5.10) states that U ≤ max[U, 0], which is true. Considering (5.8) and using Lemma 5.1, for a relay node n ∈ N , n = sf , k ∈ Kf , and f ∈ F , we have Qfnk (t + 1) ≤ max[Qfnk (t) − co Ro (t)µfo k (t), 0] + co Ro (t)µfo k (t)(1 − ρo (t)) + ci Ri (t)µfi k (t)ρi (t). (5.11) 98 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning Considering (5.9) and Lemma 5.1, for any source node sf ∈ S, k ∈ Kf , f ∈ F , we have Qfsfk (t + 1) ≤ max[Qfsfk (t) − co Ro (t)µfo k (t), 0] + co Ro (t)µfo k (t)(1 − ρo (t)) + αfk (t). (5.12) We now introduce two lemmas to simplify (5.11) and (5.12). Lemma 5.2 can be found in [103]. Lemma 5.2 ([103]) For any positive U1 , U2 , η, and ν, if we have U1 ≤ max[U2 −η, 0]+ν, then U12 ≤ U22 + η 2 + ν 2 − 2U2 (η − ν). (5.13) Proof If U2 > η, then we have U1 ≤ U2 − η + ν. By squaring both sides of this inequality and adding the positive value of 2νη to the right hand side of the inequality, (5.13) is verified. If U2 < η, then we have U12 ≤ ν 2 . Since η 2 + U22 − 2U2 (η − ν) ≥ 0, we can add it to the right hand side of the above and inequality (5.13) is verified. Lemma 5.3 For positive U1 , U2 , O, I, ρ, and ρ′ ≤ 1 if U1 ≤ max[U2 −O, 0]+O(1−ρ′ )+Iρ, then U12 ≤ U22 + B − 2U2 (Oρ′ − Iρ), where B = O 2 + ρ2 I 2 + O 2(1 − ρ′ )2 + 2ρ(1 − ρ′ )OI. Proof We proved in Lemma 5.2 that for positive values of U1 , U2 , η, and ν if U1 ≤ max[U2 − η, 0] + ν, then we have U12 ≤ U22 + η 2 + ν 2 − 2U2 (η − ν). By substituting η = O and ν = O(1 − ρ′ ) + Iρ, Lemma 5.3 is proven. Using Lemma 5.3 and inequalities (5.11) and (5.12), for any k ∈ Kf and f ∈ F , we 99 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning have Qfnk (t + 1)2 ≤ Qfnk (t)2 + Bnf k (t) − 2Qfnk (t)(co Ro (t)µfo k (t)ρo (t) − ci Ri (t)µfi k (t)ρi (t)), (5.14) for any intermediate relay node n ∈ N (n = sf ) where Bnf k (t) = c2o Ro (t)2 µfo k (t)2 + ρi (t)2 c2i Ri (t)2 µfi k (t)2 + c2o Ro (t)2 µfo k (t)2 (1 − ρo (t))2 + 2ρi (t)(1 − ρo (t))co Ro (t)µfo k (t)ci Ri (t)µfi k (t). Similarly, for source node sf , we have Qfsfk (t + 1)2 ≤ Qfsfk (t)2 + Bsffk − 2Qfsfk (t)(co Ro (t)µfo k (t)ρo (t) − αfk (t)), (5.15) where Bsffk (t) = c2o Ro (t)2 µfo k (t)2 + αfk (t)2 + c2o Ro (t)2 µfo k (t)2 (1 − ρo (t))2 + 2(1 − ρo (t))co Ro (t)µfo k (t)αfk (t). From Lemma 5.2 and inequality (5.4), for each virtual queue Zf , f ∈ F , we have Zf2 (t + 1) ≤ Zf2 (t) + k∈Kf αfk (t) 2 + λ2 (t) − 2Zf (t) k∈Kf αfk (t) − λ(t) . (5.16) Now, we can write △Θ(t) − V E{λ(t) | Θ(t)} as △(Θ(t)) − V E{λ(t) | Θ(t)} = E{L(Θ(t + 1)) − L(Θ(t)) | Θ(t)} − V E{λ(t) | Θ(t)} 100 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning ≤ B− Qfsfk (t)E{co Ro (t)µfo k (t)ρo (t) − αfk (t) | Θ(t)} k∈Kf ,f ∈F + n=sf − Zf (t)E f ∈F k∈Kf Qfnk (t)E{co Ro (t)µfo k (t)ρo (t) − ci Ri (t)µfi k (t)ρi (t) | Θ(t)} αfk (t) − λ(t) | Θ(t) where B = BQ + BZ , and BQ = 5NF max Kf f ∈F − V E{λ(t) | Θ(t)}, 2 max αmax , max c2e /2, e∈E (5.17) (5.18) 2 BZ = F αmax max Kf f ∈F + λ2max /2. Inequality (5.17) holds under any adopted scheduling algorithm. Note that the expected values are taken over the random channel state probabilities. Let λ∗ be the optimal value for λ which can be achieved by an algorithm such that all backlog and virtual queues remain stable. Since the corresponding sending rates are stably supported by the network, there exist link data rates for all wireless links that support data transmission in the network. These data rates can be achieved with a possibly randomized channel state-only algorithm X . This is proved by projection of link data rates in different time-varying channel states and then expressing each projection as the convex combination of corresponding independent sets. Further details can be found in [105]. Assume that Algorithm X determines the decision parameters (λ(t), Re (t), µfe k (t), and αfk (t) for all e ∈ E, k ∈ Kf , and f ∈ F ) at the beginning of each time slot t such that λ achieves the optimal value λ∗ , virtual queues are stable (i.e., λ < k∈Kf αfk for any f ∈ F ) and backlog 101 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning queues are also stable. Note that Algorithm X is a channel state-only algorithm which makes the decisions only based on the observed channel states at each time slot. Therefore, it needs a priori knowledge on channel states. The stability of backlog queues implies that under Algorithm X , for an intermediate relay node n ∈ N and n = sf , we have E{co Ro (t) µfo k (t)ρo (t) | Θ(t)} > E{ci Ri (t)µfi k (t)ρi (t) | Θ(t)}. (5.19) For any source node sf , f ∈ F , we have E{co Ro (t)µfo k (t)ρo (t) | Θ(t)} > E{αfk (t) | Θ(t)}. (5.20) The stability of virtual queues implies that E{λ(t) | Θ(t)} < E k∈Kf (5.21) αfk (t) | Θ(t) , for all f ∈ F . Then, from (5.17), there exists ǫ > 0 such that △(Θ(t)) − V E{λ(t) | Θ(t)} ≤ B − ǫ n∈N ,k∈Kf ,f ∈F Qfnk (t) + f ∈F Zf (t) − V λ∗ , (5.22) under Algorithm X , where B = BQ + BZ as in (5.18). Note that here the expectation is taken over different random channel states and different randomized decisions. We now present the distributed fair (DisF) algorithm for maximizing the minimum throughput in a multihop network with channel coding and multipath routing. The goal of the algorithm is to select the decision parameters λ(t), Re (t), αfk (t) and µfe k (t) for all 102 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning e = (ne , n′e ) ∈ E, k ∈ Kf , and f ∈ F , such that f ∈F k∈Kf αfk (t) Zf (t) − Qfsfk (t) + + λ(t) V − f ∈F f ∈F k∈Kf e∈E afe k ce Re (t)µfe k (t) Qfnke (t) − Qfnk′ (t) Pe (t) e Zf (t) , (5.23) is maximized over all available decision parameters at each time slot t. Before we present the algorithm in detail, we analyze the performance of the algorithm in Theorem 5.1. Theorem 5.1 Let Algorithm DisF be an algorithm that maximizes (5.23) over all available decision parameters at each time slot t. Then, it is throughput-optimal. That is, it stabilizes the network if any other algorithm can do so and the minimum throughput in the network is at most B/V away from the optimal value. Proof Algorithm DisF maximizes (5.23), which can be rewritten as f ∈F k∈Kf Qfsfk (t) co Ro (t)µfo k (t)Po (t) − αfk (t) + n=sf + f ∈F Zf (t) Qfnk (t) co Ro (t)µfo k (t)Po (t) − ci Ri (t)µfi k (t)Pi (t) k∈Kf (5.24) αfk (t) − λ(t) + V λ(t). Recall from Section 5.2 that for any node n ∈ N , each data flow f ∈ F , and any path k ∈ Kf , ifnk and ofnk ∈ E denote the input and output links to and from node n on path k of flow f , respectively. We remove the indices n, f, k and denote the input and output links with i and o in (5.24), respectively. Recall that inequality (5.17) holds under any algorithm including the DisF algorithm. By maximizing (5.24) at each time slot t, we minimize the upper bound on △(Θ(t)) − V E{λ(t) | Θ(t)} (right hand side of (5.17)) over 103 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning its value under any other algorithm including Algorithm X , that is on the right hand side of (5.22). Then, under the DisF algorithm, we have △(Θ(t)) − V E{λ(t) | Θ(t)} ≤ B − ǫ n∈N , k∈Kf , f ∈F Qfnk (t) − ǫ f ∈F Zf (t) − V λ∗ . (5.25) This is the condition of Proposition 5.1. We must note that while maximizing (5.23) over all possibilities leads to an optimal solution, it is an NP-hard problem in wireless networks due to interference constraints [113]. In order to solve this problem in a distributed manner and in reasonable time (compared to the introduced delay and channel variation time due to channel fluctuations), we use the greedy maximal scheduling (GMS) policy. GMS is sub-optimal and may be implemented in a distributed manner. It has been shown in[114] that its efficiency ratio is at least 1/2 in the 1-hop interference model. In other words, GMS can achieve at least half of the throughput achieved by the optimal policy. Algorithm 5.1 shows the DisF algorithm which aims at maximizing (5.23) at any time slot t in a decentralized manner. This algorithm has several phases that are performed at the beginning of each time slot t. Flow Control Each source node sf checks the backlog queue Qfsfk (t) for each path k ∈ Kf of flow f . If Qfsfk (t) ≤ Zf (t), sf schedules αmax new data bits for flow f to be admitted to the corresponding path (i.e., sets αfk (t) to be equal to αmax ) (Lines 2-9). Scheduling The candidate set is initialized with all links that have data to send. Each link e = (n, n′ ) ∈ E, sets its weight we equal to the maximum value of Qfnk (t) − Qfnk′ (t) over all paths k ∈ Kf 104 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning Algorithm 5.1 Distributed fair (DisF) algorithm for maximizing the minimum throughput among the entire users in the network, executed at the beginning of each time slot t. The algorithm is initiated with Z(0) = 0 at t = 0. 1: Initialization: Assign values for αmax , λmax , V . 2: Set α(t) = 0. 3: for each source sf ∈ S, f ∈ F do 4: for each k ∈ Kf do fk 5: if Qsf (t) ≤ Zf (t) then 6: sf sets αkf (t) = αmax . 7: end if 8: end for 9: end for 10: Initiate candidate set C of all links that have data to send. 11: for each link e = (n, n′ ) ∈ C do 12: Set we = max(Qfnk (t) − Qfnk′ (t)). 13: Set f,k ∗ ∗ (fe , ke ) = arg max(Qfnk (t) − Qfnk′ (t)) f,k 14: end for 15: while C is not empty do 16: Set e∗ = arg max we . 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: e∈C fe∗∗ ke∗∗ (t) = µe∗ 1. Set Find Re∗ (t) by solving 2−g(R0e∗ −Re∗ (t)) = 1+R ∗1(t)g ln 2 . e Remove e∗ and all links that interfere with e∗ from the candidate set C. end while for each source sf ∈ S, f ∈ F do if f ∈F Zf (t) ≤ V then Set λ(t) = λmax . else Set λ(t) = 0. end if end for for each source sf ∈ S, f ∈ F do Zf (t + 1) = max Zf (t) − k∈Kf αkf (t), 0 + λ(t). 30: Update the other sources with Zf (t + 1) through control messages. 31: end for 29: 105 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning and flows f ∈ F that use that link. Then the link with the maximum weight is selected to transmit data for the corresponding path and flow, it is removed from the candidate set and all links which interfere with that link are also removed from the set. This process continues until no link remains in the candidate set (Lines 10-20). The scheduling process (lines 15-20) can be implemented in a distributed manner by making modifications to the MAC parameters. This is done in [113] by varying contention window parameters CWmin and CWmax for links to transmit more or less aggressively according to their weights we . Code Rate Allocation For each scheduled link e, the optimal code rate that maximizes Re (t)(1 − 2−g(R0e −Re (t)) ) is determined by solving 2−g(R0e −Re (t)) = 1 1+Re (t)g ln 2 (Line 18). In case of any change in the wireless environment, Re (t) is determined according to the new available updates for R0e . Fairness Provisioning The source node of each data flow f ∈ F sets λ(t) = λmax if f ∈F Zf (t) ≤ V , and sets λ(t) = 0 otherwise (Lines 21-27). Virtual queues are updated according to (5.4) (Line 28-31). The value of virtual queues at each time slot is transmitted between the source nodes through control messages. Next, the scheduled links transmit their packets and new data bits are admitted in the source node queues. 5.4 Geometric Programming Formulation In this section, we provide a benchmark for performance of the decentralized scheduling algorithm for evaluation purposes. We formulate the problem of code rate and sending rate allocation as a NUM problem and describe a centralized solution approach. We assume multiple paths are available for data flows. We also allow channel coding to improve the 106 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning reliability and use retransmissions in case of any data loss. In this section, we do not consider scheduling. The slotted notion of time is not considered and the variables are time average values. Recall that the sending rate for the k th path of flow f ∈ F is αfk . Channel coding is performed on link e ∈ E at a rate of Re . Thus, link e must transmit packets for path k ∈ Kf of flow f ∈ F with a rate of αfk /Re if all transmissions are successful. Since the probability of a successful transmission is Pe , each transmission is completed within 1/Pe attempts on average where Pe = 1 − 2−g(R0e −Re ) in the worst case. We have ufe k = afe k αfk , Re Pe (5.26) where ufe k is the data rate at which link e is being used to transmit data for the k th path of flow f ∈ F . We can express the usage of wireless link e ∈ E as afe k ue = f ∈F k∈Kf αfk Re Pef k . (5.27) To model the interference in the network, we use a contention graph GC (NC , EC ). The set of vertices NC represents the set of wireless links in graph G. There is a link between each two vertices if and only if the corresponding links in graph G interfere with each other. Each complete subgraph in graph GC is called a clique and a maximal clique ω is one that is not a subset of a larger clique. We define Ω as the set of all maximal cliques in the network. It is necessary for successful transmissions that the summation of link usages over all links in each maximal clique be less than the capacity of the clique ζω . This is a necessary condition for successful transmission and leads to an upper bound on the network performance. Now, we can write the problem of fair sending rate and code rate allocation in a 107 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning multihop wireless network to maximize the minimum throughput as maximize α,R,σ σ subject to σ ≤ k∈Kf αfk , afe k ∀ f ∈ F, αfk Re Pe ≤ ζω , ∀ ω ∈ Ω, Pe ≤ 1 − 2−g(R0e −Re ) , ∀ e ∈ E, e∈ω f ∈F k∈Kf (5.28) α ≻ 0, 0 ≺ R ≺ R0 . In problem (5.28), the objective is to maximize the throughput of the flow with the minimum value. The second set of constraints satisfies the necessary condition for successful transmissions and leads to an upper bound on the performance. Since retransmissions due to packet loss are taken into account in the second set of constraints, the total number of admitted packets will be received at the destination. Therefore, by maximizing the sending rate of any flow, the received throughput is also maximized. The objective function in problem (5.28) and the left hand side of the second set of constraints are posynomials (i.e., polynomials with positive terms). The first set of constraints has signomials (i.e., polynomials with both positive and negative terms) on the left hand side. Therefore, we can apply signomial programming techniques [82] to solve this problem. In this regard, we need to approximate the right hand side of the first set of constraints with a monomial around an initial point α ˆ. For a parameter b > 1 very close to 1, we have k∈Kf ˆ −1 = where Λ f k∈Kf ˆ −1 αfk ≈ Λ f k∈Kf αfk α ˆ fk ˆf α ˆ kf Λ ˆ bα] ˆ , , ∀ α ∈ [α/b, (5.29) α ˆ fk . Finally, we tackle the third set of constraints in (5.28). We can approximate the exponential term using the Taylor series expansion and rewrite the 108 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning constraint as Pe ≤ 1 − X1e ∞ (X2 Re )n , n! n=0 (5.30) where X1e = 2−gR0e and X2 = g ln 2. For large Me , we have Pe ≤ 1 − X1e Me −1 n=0 (X2 Re )n . n! (5.31) Me must be large enough such that (X2 Re )Me ≪ Me ! and can be found through simulations. Now, we can rewrite problem (5.28) in the standard form of geometric programming problems as minimize σ,α,R,P σ −1 ˆfσ subject to Λ (α ˆ fk αfk ˆf −1 α ˆ kf Λ ) k∈Kf e∈ω f ∈F k∈Kf α ∀ f ∈ F, afe k αfk Re −1 Pe −1 ≤ ζω , X1e Pe + 1 − X1e 1 − X1e ˆ α/b ≤ 1, Me −1 n=1 ∀ ω ∈ Ω, (5.32) n (X2 Re ) ≤ 1, n! ∀ e ∈ E, ˆ bα, σ > 0, 0 ≺ R ≺ R0 , P ≻ 0. The above problem is a geometric programming problem that can be solved iteratively using the interior-point method [82]. In each iteration, we use the solution obtained in the previous iteration as the new initial point α ˆ and use the approximation in (5.29) around that point. We use the solution of this problem as a benchmark for evaluating the DisF algorithm. 109 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning 5.5 Performance Evaluation In this section, we evaluate our proposed algorithm through simulations. For simulations, we use Matlab. First, we compare the performance of the DisF algorithm with the centralized approach obtained through solving geometric programming problem. Then, we study fairness provisioning in the network. For that purpose, we quantitatively measure fairness under the DisF algorithm in several random topologies and compare it with a Lyapunovbased algorithm in which the fairness is not considered. Here, we call that algorithm as DisA algorithm. The goal in DisA algorithm is to maximize the aggregate throughput of the network (i.e., f,k in the network (i.e., minf αfk ) while DisF algorithm maximizes the minimum throughput k αfk ). We also show how fairness is provided at the cost of degrading the aggregate throughput in the network. We show the effect of channel coding on the network performance by comparing with the case when channel coding is not used. Moreover, we study the effect of algorithm parameter V on the obtained performance of the DisF algorithm. Finally, we compare the proposed approach with the distributed utility-based approach presented in [8]. We compare the minimum throughput under the DisF algorithm with the minimum throughput obtained through solving the geometric programming problem (5.28). We run the simulations for both approaches in topologies with 30 nodes. The number of flows varies between 2 and 10. In this set of simulations, we set αmax = 2, λmax = 10, V = 50, and ce = 10 bits for all links e ∈ E. This is because the MOSEK software [89] that we used to solve the geometric programming problem cannot solve the problem when ce and consequently Me (see (5.31)) grows. We run the simulations on 50 random topologies. The DisF algorithm follows the optimal solution as the number of flows in the network grows (Fig. 5.2). Increasing the number of flows leads to higher load on the network and causes a degradation in the minimum throughput in the network for both approaches. 110 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning Minimum Throughput in the Network [bits per slot] 2.5 Centralized GP Approach DisF Algorithm 2 1.5 1 0.5 0 2 3 4 5 6 7 8 9 10 Number of Flows in the Network Figure 5.2: The performance of the DisF algorithm is compared with the solution of centralized geometric programming problem. Each point represents the average performance obtained over 50 random topologies. The DisF algorithm follows the centralized approach as the number of flows increases. Hereafter, we set parameters αmax = 1000, λmax = 5000, V = 250000, and ce = 5000 bits for all links e ∈ E. Next, we study the max-min fair (DisF) algorithm in regards of fairness provisioning. We run both DisF and DisA algorithms in a sample network topology (Fig. 2.2) with 20 nodes and 5 data flows. We observe that the achieved throughput, for the sample topology, is distributed fairly under the DisF algorithm while this is not the case for the DisA algorithm (see Fig. 5.3). We also study the fairness provisioning quantitatively on several random topologies. We use the Jain’s fairness index [2], to measure the fairness among network users. The fairness index ψ = ( f ∈F αf )2 , |F | f ∈F α2f where αf = k∈Kf αfk denotes the throughput of flow f ∈ F . For the results in Fig. 5.3, we have ψ = 0.97 under DisF algorithm while ψ decreases to 0.41 under DisA algorithm. Using the DisF algorithm in several random topologies, the fairness index is always higher than 0.95 while that of DisA algorithm degrades to 0.55 when the number of flows is equal to 10 (see Fig. 5.4). Improving the minimum throughput in the network is at the cost of degrading the 111 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning 5000 DisF Algorithm DisA Algorithm Flow Throughput in the Network [bits per slot] 4500 4000 3500 3000 2500 2000 1500 1000 500 0 1 2 3 4 5 Data Flow f Figure 5.3: In a sample topology, fairness is provided under the DisF algorithm while some flows starve under the DisA algorithm that does not consider fairness. 1 0.95 Fairness Index ψ 0.9 0.85 0.8 0.75 0.7 0.65 0.6 0.55 0.5 2 DisF Algorithm DisA Algorithm 3 4 5 6 7 8 9 10 Number of Flows in the Network Figure 5.4: The performance of DisF and DisA algorithms in regard of fairness provisioning. Each point represents the average value of the fairness index over 50 random topologies. 112 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning Minimum Throughput [bits per slot] (a) 1500 DisF Algorithm DisA Algorithm 1000 500 0 2 3 4 5 6 7 8 9 10 9 10 Number of Flows in the Network Aggregate Throughput [bits per slot] (b) 15000 DisF Algorithm DisA Algorithm 10000 5000 0 2 3 4 5 6 7 8 Number of Flows in the Network Figure 5.5: The tradeoff between minimum throughput in the network (a) and aggregate throughput in the network (b) is shown under both DisF and DisA algorithms. aggregate throughput which is achievable with the entire users in the network. Fig. 5.5 shows the tradeoff between the minimum throughput and aggregate throughput of the network. It is shown that the minimum throughput (and also the fairness) is improved via DisF algorithm (Fig. 5.5 (a)). However, that is gained at the cost of degrading the aggregate throughput of the network (Fig. 5.5 (b)). Next, we study the effect of channel coding on the performance of the DisF algorithm. The average performance of the algorithm is shown in Fig. 5.6 when channel coding is used in the network and it is compared with the case that channel coding is not used. Each point in Fig. 5.6 represents the average value over 50 random topologies. In this set of simulations, we assume the probability at which a packet is transmitted successfully over a wireless link to be 0.8 if channel coding is not used. We observe that the minimum throughput increases by 28% when the number of flows is 10. In Fig. 5.7, we study the effect of varying parameter V on both the minimum throughput and the delay in the network under the DisF algorithm. We used the total backlog in 113 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning Minimum Throughput in the Network [bits per slot] 1200 With Channel Coding Without Channel Coding 1000 800 600 400 200 28% increase 0 2 3 4 5 6 7 8 9 10 Number of Flows in the Network Figure 5.6: Performance of the network with channel coding is compared with the case in which channel coding is not being used. the network as a measure of the delay. Each point in Fig. 5.7 represents the average performance of the algorithm for 50 random topologies with 20 nodes and 5 data flows. We vary V from 0 to 50000 and it is shown that the minimum throughput in the network increases with increasing V at the expense of a linear increase of delay in the network. Finally, we compare our approach with the one introduced in [8] as an example of a class of approaches that use utility functions to provide different notions of fairness including maxmin fairness. This is comparing to our proposed method which directly pushes the minimum throughput up instead of using utility functions. In [8], the problem of maximizing the aggregate network utility for all flows in the network was considered as maximizing f uβf (αf ) subject to α ∈ Λ, where uβf (x) is the utility function (i.e., uβf (x) = x1−β /(1 − β), β = 1, and uβf (x) = log x, β = 1). It was shown that by increasing β in the above utility functions, the performance of the network converges to maxmin fairness provisioning. The two algorithms are compared in Figs. 5.8 and 5.9 regarding the minimum throughput they provide for network users and fairness provisioning. Each point represents the average of simulation results in 50 random topologies. To make the comparison fair, 114 Minimum Throughput in the Network [bits per slot] Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning (a) 1000 800 600 400 200 0 5,000 10,000 15,000 20,000 25,000 30,000 35,000 40,000 45,000 50,000 V Total Backlog in the Network [bits] (b) 800,000 600,000 400,000 200,000 0 0 5,000 10,000 15,000 20,000 25,000 30,000 35,000 40,000 45,000 50,000 V Figure 5.7: The effect of increasing parameter V is shown on the minimum throughput (a). This is at the expense of increasing the congestion in the network (b). we assume wireless links are completely reliable. We do not employ multipath routing and channel coding in the network. Parameter β for the utility function is chosen to be 0, 1, and 100 which is for aggregate throughput maximization, proportional fairness, and maxmin fairness, respectively. It is verified (Fig. 5.8) that the fairness index is improved under DisF algorithm compared with the utility-based algorithm when β = 0 and 1. The fairness index of the utility-based algorithm improves when β increases but at the cost of the dramatic decrease in the minimum achieved throughput (Fig. 5.9). 5.6 Summary In this chapter, we studied fairness provisioning in multihop wireless networks. We developed an online decentralized algorithm to schedule new data packet admission and packet transmissions such that the minimum throughput of the network is maximized. We consid115 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning β = 100 1 0.98 Fairness Index ψ 0.96 0.94 β=1 0.92 0.9 0.88 0.86 0.84 β=0 DisF Algorithm Utility−based Algorithm 0.82 0.8 2 3 4 5 6 7 8 9 10 Number of Flows in the Network Figure 5.8: DisF algorithm is compared with the utility-based approach in terms of fairness provisioning using Jain’s fairness index. It is shown that for large values of β, the utilitybased approach has a better performance comparing with DisF algorithm. This is at the cost of a decrease in the minimum throughput. (Fig. 5.9) Minimum Throughput in the Network [bits per slot] 1000 DisF Algorithm Utility−based Algorithm 900 800 700 β=0 600 500 400 β=1 300 200 100 0 2 β = 100 3 4 5 6 7 8 9 10 Number of Flows in the Network Figure 5.9: DisF algorithm is compared with the utility-based approach when different number of flows are using the network. It is shown that increasing β is at the cost of decreasing the minimum throughput. 116 Chapter 5. Distributed Scheduling with Maxmin Fairness Provisioning ered networks with multipath routing and channel coding. We studied the performance of the algorithm analytically. Through simulations, we showed that the proposed algorithm followed the optimal centralized approach with under control degree of sub-optimality. We also showed that the proposed algorithm improves the performance of the network regarding fairness comparing to the other approaches which ignore fairness provisioning. Moreover, we showed the effectiveness of channel coding on the performance of the network. Finally, we showed through simulations that our proposed approach has a better performance in terms of fairness provisioning comparing to the class of utility-based approaches. Since the proposed algorithm determines the scheduling at each time slot, it can adapt to the dynamic changes of the wireless environment. 117 Chapter 6 Throughput-Optimal Scheduling and Interference Alignment for MIMO Wireless Systems 6.1 Introduction In this chapter, we study the use of interference alignment techniques for transmission scheduling in wireless MIMO systems with the goal of improving the network performance. Multiple antennas can be used for data transmission between the mesh nodes and the end users and also between the mesh nodes and the gateway. The current work in interference alignment (see Section 1.2.5) provides signal design for interference wireless networks with K users, when K is relatively small, by minimizing the interference leakage at each receiver. Therefore, in each transmission time all users are scheduled to transmit. However, while in a network with many users it may be impractical for the entire users to transmit simultaneously even employing interference alignment techniques, there is not enough attention to scheduling the data transmissions in such network settings. Packet admission control is also not considered in that body of work. The main issue that needs to be considered in designing any network scheduling algorithm is stability and to this end we apply Lyapunov stability theory. The framework 118 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems of Lyapunov stability theory has been used to establish stable, distributed, scheduling policies [103] for throughput maximization [105, 115] and energy minimization in single hop [106] and multihop [107] networks. However, to the best of our knowledge, there is no prior work on using interference alignment to improve the effective network capacity via Lyapunov stability theory. For interference alignment to be practical, one would need to determine a scheduling policy and an appropriate signal design (i.e., encoding and decoding matrices) such that the interference caused by undesired signals at each receiver is minimized. Signal design depends on the channel conditions and the particular set of users scheduled for transmission at that time instant. In addition, new data packets must be admitted from the upper layer by the users subject to network stability considerations. The contributions of this chapter are as follows: • We formulate a joint scheduling, signal design, and packet admission control problem with the goal of maximizing the aggregate network throughput and ensuring stability. We also propose a centralized scheduling and interference alignment (SIA) algorithm to solve the problem. • Using Lyapunov stability theory, we transform the problem into a nonlinear mixedinteger programming (MIP) problem with non-convex constraints for each time slot. In the problem formulation, we incorporate interference alignment to construct necessary conditions for minimizing the interference. • We transform the problem with non-convex constraints into a nonlinear MIP with convex constraints using the coordinate ascent method and semidefinite programming (SDP) techniques. For solving the MIP problem, we propose an algorithm that is based on the generalized Benders decomposition (GBD) method. 119 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems • We propose a semi-distributed scheduling and interference alignment (SDSIA) algorithm, which is heuristic and has lower computational complexity than SIA. • Through simulation, we show that SIA converges to the solution after a few iterations. We also show that SDSIA, although suboptimal, has a similar performance as SIA. In addition, we determine the impact of the joint use of interference alignment and scheduling on the network throughput by comparing the performance of the proposed algorithm with two other approaches: (a) an interference alignment (IA) algorithm which employs interference alignment techniques without scheduling and (b) greedy maximal scheduling (GMS) which uses scheduling techniques without interference alignment. This chapter is organized as follows: The system model is presented in Section 6.2. The joint scheduling, packet admission control, and signal design problem is formulated in Section 6.3. In Section 6.4, we solve the formulated problem using the GBD method. A semi-distributed heuristic is provided in Section 6.5. Simulation results are presented in Section 6.6, and the chapter is concluded in Section 6.7. 6.2 System Model Consider a single-hop MIMO wireless network. Each link, together with its dedicated transmitter and receiver nodes, is called a user. Let K = {1, . . . , K} denote the set of users. We assume that each user’s receiver node can hear every other user’s transmissions. Time is divided into equal-length slots. Let T = {0, 1, . . . , T − 1} denote the set of time slots. For each user k ∈ K, we introduce a scheduling variable ρk (t) ∈ {0, 1} such that ρk (t) = 1 if user k transmits data in time slot t, and ρk (t) = 0 otherwise. We assume that a user can send at most one data packet in each time slot. 120 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems Figure 6.1: Network topology for wireless MIMO system with K users. Consider the network topology shown in Fig. 6.1. User k has Mk antennas at the transmitter node and Nk antennas at the receiver node. At each time slot t, if user k is scheduled to transmit, it prepares a data packet xk (t) as a vector of symbols of size dk . Then, the transmitter node of user k encodes the data packet with an encoding matrix Vk (t) ∈ CMk ×dk , where C denotes the set of complex numbers, and transmits the encoded Mk × 1 vector over its Mk antennas. For two users k, l ∈ K, the wireless channel between the transmitter node of user k and the receiver node of user l is modeled by matrix Hlk (t) of size Nl × Mk . At the receiver node of user l, the packet is received as an Nl × 1 vector and is decoded using decoding matrix Ul (t) ∈ CNl ×dl . The decoded data packet yl (t) at time slot t can be represented as ρk (t)U∗l (t)Hlk (t)Vk (t)xk (t) + U∗l (t)nl (t), yl (t) = (6.1) k∈K where matrix U∗l (t) is the conjugate transpose of Ul (t) and nl (t) is the additive white Gaussian noise (AWGN) at the receiver node of user l. Interference alignment techniques aim at minimizing the projection of the interfering signal within the interference-free subspace of the receiver. For ideal interference align- 121 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems ment, we need to determine the encoding matrices V1 (t), . . . , VK (t) and decoding matrices U1 (t), . . . , UK (t) such that for each user l there is zero interference from other users k ∈ K (k = l) projected into the interference-free subspace of the receiver node of user l, and the desired signal is received through a full rank channel matrix, i.e., U∗l (t)Hlk (t)Vk (t) = 0, ∀ k, l ∈ K, k = l, (6.2) ∀ k ∈ K. (6.3) rank(U∗k (t)Hkk (t)Vk (t)) = dk , Note that (6.2) and (6.3) are the interference alignment feasibility conditions [70]. However, complete suppression of interference at the receiver may not be practical. Let Il (t) = k∈K, k=l Ilk (t) denote the total interference leakage for any user l ∈ K, where Ilk (t) = 1 tr (U∗l (t)Hlk (t)Vk (t)Vk∗ (t)H∗lk (t)Ul (t)) dk (6.4) denotes the interference leaked by the transmitter of user k at the receiver of user l [70], and tr(·) denotes the trace of a matrix. Thus, at each time slot t, we aim to keep Il (t) for any scheduled user l ∈ K below a user specified threshold ǫ. That is, ρl (t)Il (t) ≤ ǫ. (6.5) For scheduled user k, the received signal should be larger than the receiver threshold Pth . That is, Ikk (t) ≥ Pth ρk (t), ∀ k ∈ K. (6.6) Equations (6.5) and (6.6) ensure that the interference from undesired signals is sufficiently suppressed at each receiver node l. On the other hand, if the corresponding transmitter 122 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems k is scheduled to transmit, the desired signal is sufficiently strong. To ensure error-free decoding at the receivers, Pth and ǫ have to be properly chosen. Note that Il (t) in (6.5) is the summation of the interference received at receiver l from all transmitters including those not scheduled at time slot t (ρk (t) = 0). Therefore, for (6.5) to be satisfied, we require elements of the encoding matrices for not scheduled users as well. Including non-scheduled users has no effect on the final solution.1 Each user’s transmitter node performs admission control and maintains a backlog queue. Let Qk (t) denote the number of packets that are waiting to be sent in the backlog queue of user k at time slot t. Let αk (t) denote the number of packets that are admitted into the queue backlog of user k by the upper layer at time slot t. We assume that the number of admitted packets in each time slot is bounded by a constant αmax . That is, αk (t) ≤ αmax , for all k ∈ K. The backlog at the transmitter node of user k, Qk (t), can be modeled as a queue with arrival process αk (t) and service process ρk (t). That is, Qk (t + 1) ≤ max{Qk (t) − ρk (t), 0} + αk (t), ∀ k ∈ K. (6.7) We use the notion of strong stability [116]. The network is strongly stable if lim sup T →∞ 1 T t∈T k∈K E{Qk (t)} < ∞. (6.8) The expectation is taken over all possible channel states. If the network is stable, then the admission rate, αk (t) at each transmitter node of user k ∈ K is also the throughput at the 1 Note that we can avoid the involvement of the encoding matrices of not scheduled users by adding the term ρk (t) in the expression of Il (t). However, this formulation does not lead to a tractable problem. On the other hand, it can be easily shown that the optimal solutions for both formulations are the same regarding the variables of scheduled users. The obtained solution for the variables of users that are not scheduled can be ignored. 123 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems corresponding receiver node. The average throughput for user k ∈ K in T time slots is α ¯k = 1 T E{αk (t)}. (6.9) t∈T The aggregate network throughput is α ¯k = α ¯= k∈K where α(t) = k∈K 1 T E{αk (t)} = t∈T k∈K 1 T E{α(t)}, (6.10) t∈T αk (t) denotes the total number of packets that are admitted by the upper layer at time slot t. Finally, we define Π as the set of all admission rates α ¯ = (α ¯1, . . . , α ¯ K ) that satisfy the inequality in (6.8). That is, the network is stable when α ¯ ∈ Π. 6.3 Problem Formulation We now present the joint scheduling, admission control, and signal design problem formulation. The goal is to maximize the aggregate throughput of the network such that all queues remain stable. The optimization problem can be formulated as follows: maximize α(t), ρ(t), U(t), V(t), t∈T subject to α ¯ α ¯ ∈ Π, k ∈ K, Ikk (t) ≥ Pth ρk (t), k ∈ K, t ∈ T ρk (t)Ik (t) ≤ ǫ, k ∈ K, t ∈ T ρk (t) ∈ {0, 1}, k ∈ K, t ∈ T (6.11) 0 ≤ αk (t) ≤ αmax , k ∈ K, t ∈ T where α(t) = (α1 (t), . . . , αK (t)) denotes the vector of admitted packets at time slot t, 124 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems ρ(t) = (ρ1 (t), . . . , ρK (t)) denotes the scheduling vector, and U(t) and V(t) denote the set of all matrices Uk (t) and Vk (t) for k ∈ K, respectively. In problem (6.11), the objective function is the aggregate network throughput over all time slots. The first constraint is the network stability constraint and ensures that the obtained solution leads to a stable network. The second and third constraints ensure the scheduling variables as well as the encoding and decoding matrices are selected such that the admitted data packets can be transmitted successfully. Note that Pth and ǫ are not independenet. They must be chosen such that the signal to interference plus noise ratio is greater than a threshold Γth , that is Pth /(ǫ + σn2 ) ≥ Γth . Instead of solving problem (6.11) to obtain the solutions for all time slots, we decompose this problem into multiple problems, one for each time slot. The solution to each problem gives suitable values for the variables in that particular time slot. We formulate the problems such that their solutions lead to the solution of problem (6.11). For this purpose, we first present some preliminaries. We begin by summarizing some aspects of Lyapunov stability theory. Let the Lyapunov function L(Q(t)) be a non-negative function of a vector Q(t) = (Q1 (t), . . . , QK (t)). The Lyapunov drift is defined as ∆(Q(t)) E{L(Q(t + 1)) − L(Q(t)) | Q(t)}. Proposition 6.1 (Lyapunov Optimization [103]) Let α(t) be the utility function at time t, and A > 0, ε > 0, and Z > 0 be constants such that for all time slots t and queue vectors Q(t), we have ∆(Q(t)) − ZE{α(t) | Q(t)} ≤ A − ε k∈K Qk (t) − Zα∗ , (6.12) where α∗ can be any target value for utility function α(t). Then, we have αinf ≥ α∗ − A/Z, (6.13) 125 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems lim sup T →∞ where αinf = limT →∞ inf 1 T 1 T t∈T k∈K t∈T E{Qk (t)} ≤ A + Z(αsup − α∗ ) , ε E{α(t)} and αsup = limT →∞ sup T1 t∈T E{α(t)}. The proof of the proposition can be found in [103, pp. 82-84]. Proposition 6.1 implies that by satisfying inequality (6.12) at each time slot t, we can approach the target point α∗ while the queue backlogs remain stable. Note that the larger the parameter Z, the closer we can get to α∗ . This is at the expense of a linear increase in the aggregate queue backlog. Consider Lyapunov function L(Q(t)) = (1/2) k∈K Q2k (t). Before calculating the Lyapunov drift, we state the following lemma. Lemma 6.1 For any positive Q1 , Q2 , ρ, and α, if Q1 ≤ max[Q2 − ρ, 0] + α, then Q21 ≤ Q22 + ρ2 + α2 − 2Q2 (ρ − α). (6.14) The proof can be found in [103, 116]. According to Lemma 6.1 and inequality (6.7), we have Q2k (t + 1) ≤ Q2k (t) + ρ2k (t) + αk2 (t) − 2Qk (t)(ρk (t) − αk (t)), (6.15) for all k ∈ K. Thus, we can write ∆(Q(t)) − ZE{α(t) | Q(t)} = E{L(Q(t + 1)) − L(Q(t)) | Q(t)} − ZE{α(t) | Q(t)} ≤ Amax − k∈K E{Qk (t)(ρk (t) − αk (t)) | Q(t)} − ZE k∈K αk (t) | Q(t) , (6.16) 2 where Amax = K(1 + αmax )/2. Note that inequality (6.16) holds for any algorithm. Now, we present the SIA algorithm. In each time slot t, SIA selects the admission vector α(t), scheduling vector ρ(t), encoding and decoding matrices V(t) and U(t), such 126 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems that the following problem is solved: maximize α(t), ρ(t), U(t), V(t) subject to k∈K (Qk (t)ρk (t) + αk (t)(Z − Qk (t))) Ikk (t) ≥ Pth ρk (t), k ∈ K, ρk (t)Ik (t) ≤ ǫ, k ∈ K, ρk (t) ∈ {0, 1}, k ∈ K, 0 ≤ αk (t) ≤ αmax , (6.17) k ∈ K. Maximizing the objective function of problem (6.17) is equivalent to minimizing the righ hand side of (6.16). The first set of constraints ensures that the desired signal is received at the receiver if the corresponding user is scheduled for transmission. The second set of constraints implies that the interference produced by the other users in the interference free subspace of any receiver which is scheduled for receiving data is suppressed. In Theorem 6.1, we explain why solving problem (6.17) leads to the optimal solution of problem (6.11). Theorem 6.1 Let the SIA algorithm solve problem (6.17) in each time slot t. Then, SIA is throughput-optimal.2 The throughput α ¯ is at most Amax /Z away from the optimal value α∗ . Before proceeding to the proof, we note that a channel state-only (CSO) algorithm is an algorithm which makes (possibly random) decisions based on only the observed state of the channels. CSO algorithms require global knowledge of the channel state. Proof Suppose there exists a channel state-only (CSO) algorithm which determines ρ(t), Vk (t) and Uk (t) for k ∈ K, and α(t) for all t ∈ T , such that the network is stable and the 2 Throughput optimality means that the algorithm can provide a larger aggregate throughput than any other algorithm while maintaining stability [117]. 127 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems network throughput is equal to the optimal value α∗ . Since the network is stable, we have stable queues at all transmitters and therefore an ε > 0 can be found such that E{ρk (t) | Q(t)} > E{αk (t) | Q(t)} + ε, ∀ k ∈ K. (6.18) From (6.16) and (6.18), for the CSO algorithm, we have ∆(Q(t)) − ZE{α(t) | Q(t)} ≤ Amax − ε k∈K Qk (t) − Zα∗ . (6.19) Recall that (6.16) is true for any algorithm including SIA. The SIA algorithm selects the variables which solve problem (6.17). Maximizing the objective function in problem (6.17) in all time slots is equivalent to minimizing the right hand side of (6.16). Thus, for SIA, the right hand side of inequality (6.16) is smaller than its value for any other algorithm including the CSO algorithm which in turn is smaller than the right hand side of (6.19). Therefore, we obtain (6.19) also for the SIA algorithm. This is the necessary condition (6.12) in Proposition 6.1 and leads to (6.13). Therefore, SIA can support any target value for the aggregate throughput α∗ that can be achieved with any CSO algorithm. Note that Theorem 6.1 assumes that α∗ is an achievable throughput, which implies that there exists a CSO algorithm that achieves throughput α∗ . In fact, the theorem states that the SIA algorithm is able to achieve any target throughput α∗ that is feasible. Clearly, the maximum feasible throughput is the optimal value. Note that we can maximize the second term in the objective function in problem (6.17) independent of the first term by setting αk (t) = αmax whenever Qk (t) ≤ Z, and αk (t) = 0 otherwise (∀ k ∈ K). Thus, we have the 128 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems following problem: maximize ρ(t), U (t), V (t) subject to Qk (t)ρk (t) k∈K Ikk (t) ≥ Pth ρk (t), k ∈ K, ρk (t)Ik (t) ≤ ǫ, k ∈ K, ρk (t) ∈ {0, 1}, k ∈ K. (6.20) In problem (6.20), the objective is to maximize the number of scheduled users where each user is weighted with its corresponding queue backlog. 6.4 Scheduling and Interference Alignment (SIA) Algorithm Problem (6.20) is a nonlinear mixed integer programming (MIP) problem with nonlinear constraints. The multiplicative terms in Ilk (t) make the problem hard to solve. We use several techniques to convert problem (6.20) into simpler problems that can be solved efficiently. Using those techniques may result in a sub-optimality in the obtained solution. First, to deal with the multiplicative terms Ul (t) and Vk (t) in Ilk (t), we use the coordinate ascent method [118] and solve problem (6.20) iteratively by solving two separate problems at the transmitter and receiver sides. The new problems are still non-convex. Then, we use semidefinite programming (SDP) techniques to convert each problem into a linear MIP problem. Finally, we use generalized Benders decomposition (GBD) to solve the formulated MIPs. For the reminder of the discussion, we assume data packet xk (t) to be a scalar, that is dk = 1 for all users k ∈ K. This means at each time slot, each scheduled transmitter sends a single symbol stream. Using the coordinate ascent method [118], problem (6.20) can be separated into problems at the transmitter and receiver side, respectively. At each side, the signal design 129 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems parameters related to the other side are considered as given input parameters. Since the problem is non-convex, this may lead to a sub-optimal solution. The problem at the transmitter side is maximize ρ(t),V (t) Qk (t)ρk (t) k∈K subject to Vk∗ (t)Fkk (t)Vk (t) ≥ Pth ρk (t), ρl (t) k∈K, k=l ∀ k ∈ K, Vk∗ (t)Flk (t)Vk (t) ≤ ǫ, ∀ l ∈ K, ρk (t) ∈ {0, 1}, (6.21) ∀ k ∈ K, where Flk (t) = H∗lk (t)Ul (t)U∗l (t)Hlk (t). The objective function in problem (6.21) is linear in ρk (t). It can be shown that Vk∗ (t)Fkk (t)Vk (t) is convex in Vk (t) for each k ∈ K.3 Therefore, the second set of constraints is convex while the first set is non-convex. To deal with the non-convexity in the first set of constraints, we use Lemma 6.2. Lemma 6.2 For any vector a ∈ CN and matrix B ∈ CN ×N , we have a∗ Ba = tr(BA), where A = aa∗ . Proof The lemma is proved by simply expanding both sides of the equality. We rewrite Vk∗ (t)Flk (t)Vk (t) as tr(Flk (t)Wk (t)), where Wk (t) = Vk (t)Vk∗ (t). Note that for this to be true, we need Wk (t) to be a rank one matrix, ∀ k ∈ K. Let W(t) denote the set of all Wk (t), ∀ k ∈ K. We also modify the second set of constraints in problem (6.21) to separate admission 3 The convexity can be proved by verifying that the corresponding Hessian is positive semidefinite. 130 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems variables ρ(t) from the other variables. Problem (6.21) can be transformed as maximize ρ(t),W (t) k∈K Qk (t)ρk (t) subject to tr(Fkk (t)Wk (t)) ≥ Pth ρk (t), k∈K, k=l tr(Flk (t)Wk (t)) ≤ ǫ + B(1 − ρl (t)), ∀ k ∈ K, ∀ l ∈ K, ρk (t) ∈ {0, 1}, ∀ k ∈ K, rank(Wk (t)) = 1, ∀ k ∈ K. (6.22) In problem (6.22), the objective function and the first two constraints are linear. However, the rank constraint makes the problem non-convex. The positive constant B is chosen large enough, and therefore, the second set of constraints has to be satisfied only if ρl (t) = 1. Nevertheless, (6.22) is a computationally-demanding nonlinear mixed integer optimization problem. Similarly, the receiver-side problem can be formulated as maximize ρ(t), X(t) k∈K Qk (t)ρk (t) subject to tr(Gkk (t)Xk (t)) ≥ Pth ρk (t), k∈K, k=l tr(Glk (t)Xl (t)) ≤ ǫ + B(1 − ρl (t)), ∀ k ∈ K, ∀ l ∈ K, ρk (t) ∈ {0, 1}, ∀ k ∈ K, rank(Xk (t)) = 1, ∀ k ∈ K. (6.23) where Glk (t) = Hlk (t)Vk (t)Vk∗ (t)H∗lk (t) and Xk (t) = Uk (t)U∗k (t) for ∀ k, l ∈ K. To solve the nonlinear mixed-integer optimization problem (6.22), we use the GBD method [84]. We decompose the problem into two problems: a primal problem and a master problem. The primal problem is a relaxed SDP problem which is a convex optimization problem with the encoding vectors V(t) as variables when the other variables are fixed 131 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems and it yields an upper bound for the final solution. The master problem is an MIP with binary variables ρ(t) when the other variables are fixed and it yields a lower bound for the solution. We iteratively solve primal and master problems until their solutions converge. In this subsection, since we are discussing the solution of problem (6.22) in one particular time slot t, for ease of notation, we drop the time index t. Primal problem (mth iteration) The input parameters (i.e., constants) include ρ(m) (obtained from the master problem in the mth iteration). The primal problem is as follows: minimize W − (m) Qk ρk k∈K (m) ∀ k ∈ K, subject to tr(Fkk Wk ) ≥ Pth ρk , (m) k∈K, k=l Wk tr(Flk Wk ) ≤ ǫ + B(1 − ρl ), (6.24) ∀ l ∈ K, ∀ k ∈ K. 0, In problem (6.24), the objective function is a constant. The two sets of constraints are linear in Wk . Problem (6.24) is a standard form SDP and it can be solved by using a convex optimization solver such as CVX [119]. Note that in problem (6.24), the rank constraint rank(Wk ) = 1, ∀ k ∈ K, is relaxed. Having solved the primal problem, we use eigendecomposition to obtain a rank-one approximation of the obtained solutions Wk . Thus, √ (m) Vk = γk qk , where γk is the largest eigenvalue of matrix Wk and qk is the corresponding eigenvector. Note that the rank-one approximation leads to a sub-optimal solution. From k(m) the solver, the corresponding Lagrange multipliers, λ(m) = {λ1 l(m) , λ2 , ∀ k, l ∈ K}, for the first and second set of constraints in problem (6.24) can also be obtained. The solution to primal problem W(m) is used as an input to formulate the master problems for the next iterations. 132 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems Given the input parameters ρ(m) , if problem (6.24) is infeasible, then we formulate an l1 -minimization problem (6.25) as in [84] and use its corresponding solution V(m) to continue to the master problems in the next iterations. βk1 + βk2 minimize 1 2 W 0, β , β k∈K (m) subject to tr(Fkk Wk ) + βk1 ≥ Pth ρk , ∀ k ∈ K, (m) k∈K, k=l tr(Flk Wk ) ≤ βl2 + ǫ + B(1 − ρl βk1 , βk2 ≥ 0, ), (6.25) ∀ l ∈ K, ∀k ∈ K. Problem (6.25) is an SDP problem and is always feasible. Similar to (6.24), the correspondk(m) ing Lagrange multipliers λ1 l(m) , λ2 , ∀ k, l ∈ K, can be obtained. We define M and M′ as the set of all iteration numbers at which the primal problem is feasible and infeasible, respectively. Note that similar to (6.24), in (6.25) the rank constraint rank(Wk ) = 1, ∀ k ∈ K, is relaxed. Therefore, we use a similar technique to find a rank-one approximation on the obtained solutions Wk . Master problem (mth iteration) The input parameters are V(n) and λ(n) (obtained from the primal problem), where vector k(n) λ(n) is a concatenation of λ1 minimize µ, ρ k(n) , λ2 , for k ∈ K, n ∈ M ∪ M′ . The master problem is µ subject to µ ≥ Λ ρ, V(n) , λ(n) , n ∈ M, (6.26) 0 ≥ Λ′ ρ, V(n) , λ(n) , n ∈ M′ , 133 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems where Λ′ ρ, V(n), λ(n) k(n) = λ1 k∈K (n)∗ (Pth ρk − Vk (n)∗ l(n) Vk λ2 + l∈K k∈K, k=l (n) Fkk Vk ) (n) Flk Vk − (ǫ + B(1 − ρl )) , (6.27) for all n = 1, . . . , m − 1, and Λ ρ, V(n) , λ(n) = − Qk ρk + Λ′ ρ, V(n) , λ(n) , (6.28) k∈K for all n ∈ M. Problem (6.26) is an MIP that can be solved by an integer program solver such as MOSEK [89]. GBD algorithm By weak duality [81, p. 225], in each iteration m, the solution of the master problem (6.26), µ(m) , is a lower bound for the optimum of problem (6.22). Moreover, in each iteration, the master problem has one additional constraint compared to the one formulated in the previous iteration and therefore, its optimum is equal to or greater than that of the previous iteration. Thus, the lower bounds on problem (6.22) achieved through solving the master problem in each iteration are non-decreasing. Since the integer variables are fixed in primal problem (6.24), its optimal value is always equal or worse (greater) than the optimal value of problem (6.22). Therefore, it provides an upper bound for the optimal value of problem (6.22). However, the order of the obtained upper bounds may be non-decreasing. We set the upper bound in each iteration equal to the minimum of all upper bounds achieved by that iteration. We solve master problem (6.26) in each iteration and then solve primal problem (6.24) given the optimal solution of the master problem. Since problem (6.22) 134 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems is always feasible, monotonicity of the obtained upper bounds and lower bounds causes the GBD algorithm to converge to the solution. The GBD method solves problem (6.22) Algorithm 6.1 Generalized Benders decomposition (GBD) method. 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: Initialization: ρ(1) , M := ∅, M′ := ∅, and m := 1. Obtain V(m) , λ(m) by solving primal problem (6.24). M := M ∪ {m}. f lag := 1. while f lag = 0 do Set m := m + 1. Solve master problem (6.26) and obtain ρ(m) , and the mth lower bound (LB (m) ). Solve primal problem (6.24) and obtain V(m) , λ(m) , and the mth upper bound (U B (m) ). if problem (6.24) is infeasible then Solve problem (6.25) and obtain V(m) , λ(m) , and U B (m) . M′ := M′ ∪ {m}. else M := M ∪ {m}. end if if |LB (m) − U B (m) | ≤ ξ then f lag := 0. end if end while as shown in Algorithm 6.1. After initialization, in the first iteration, the primal problem (6.24) is solved given the initial ρ(1) (lines 1-2). The only condition for ρ(1) is that problem (6.24) must be feasible at the initial point. Since scheduling only one user to transmit is always possible, the corresponding binary point creates a feasible primal problem and can be used as an initial point. In the mth iteration (m > 1), master problem (6.26) is formulated using V(n) , λ(n) for n ∈ M ∪ M′ (line 7) and the mth lower bound µ(m) is obtained. Then, the optimal solution of master problem (6.26), ρ(m) , is used to formulate the primal problem (6.24) and V(m) is obtained as well as the mth upper bound (line 8). If problem (6.24) is not feasible, l1 -minimization problem (6.25) is solved, V(m) and the mth upper bound are obtained and the iteration number is stored in M′ (lines 9-11). If problem (6.24) is feasible, the iteration number is stored in M (line 13). In iteration m when the difference between the mth lower bound and the mth upper bound is less than a 135 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems threshold ξ, the solution is obtained and is equal to V(m) , ρ(m) (lines 15-17). The SIA algorithm is presented in Algorithm 6.2. It is initialized with encoding and decoding matrices V(0) (t), U(0) (t) (line 1). For each user k ∈ K, if the queue backlog Qk (t) is less than Z, αmax packets are admitted (lines 2-6). In iteration n > 0, Problem (6.22) is formulated using U(n−1) (t) as input and the optimal solution V(n) (t) and ρ(n) (t) is obtained (line 11). Then, using V(n) (t) as given, problem (6.23) is formulated and the optimal solution U(n) (t) is obtained (line 12). If the difference between the current solution and the previous solution is less than η, then the obtained solution is equal to V(n) (t), U(n) (t), and ρ(n) (t) (lines 13-15). Algorithm 6.2 Efficient scheduling and interference alignment (SIA) algorithm. SIA is run at each time slot t, and takes the queue backlogs Q(t) and the channel state information as inputs. It is initialized with Z, η, αmax , Pth , and ǫ. 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: Initialization U(0) (t), V(0) (t), and α(t) := 0. for each k ∈ K do if Qk (t) ≤ Z then αk (t) := αmax . end if end for n := 0. Set f lag := 1. while f lag = 0 do Set n := n + 1. Formulate problem (6.22) using U(n−1) (t) and solve it with GBD (Algorithm 6.1) to obtain V(n) (t), ρ(n) (t). Formulate problem (6.23) using V(n) (t) and solve it with GBD (similar to Algorithm 6.1) to obtain U(n) (t), ρ(n) (t). (n−1) (n) (n−1) (n) (n−1) (n) (t)|) ≤ η then (t)|| + |ρk (t) − ρk (t)|| + ||Uk (t) − Uk if k∈K (||Vk (t) − Vk f lag := 0. \\ The algorithm is converged. end if end while 136 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems 6.5 Semi-Distributed Scheduling and Interference Alignment (SDSIA) Algorithm The SIA algorithm presented in the previous section can determine an efficient solution, but it has a high computational complexity. In this section, we propose a semi-distributed scheduling and interference alignment algorithm. The proposed SDSIA algorithm has two parts. The first part is shown in Algorithm 6.3. It is executed at each time slot and has three phases. 1) Transmission scheduling (lines 2-6, 24-27): The candidate set S is the set of all users which have at least one packet to send. Then, the user k ′ with the largest number of packets in its queue backlog is considered as a scheduled user (ρk′ (t) = 1). The chosen user is removed from the candidate set. The optimum signal design is obtained and its feasibility is checked regarding the first two sets of constraints in problem (6.20) through signal design and feasibility check phases. If the scheduled set is not feasible, then the most recently added user is removed from the scheduled set (i.e., ρk′ (t) = 0). The above process is repeated until the candidate set is empty. 2) Signal design (lines 7-17): When there is only one user to be scheduled, its corresponding matrix Ul (t) is set equal to a preset value U0 (t). For the case when more than one user is scheduled, the signal design is obtained based on interference alignment techniques. The goal is to minimize the interference leakage Il (t) at all receivers whose corresponding transmitters are scheduled to transmit in time slot t. Therefore, we need to set the columns of matrix Ul (t) equal to the vectors spanning the subspace with the least interference [70]. At each receiver l with ρl (t) = 1, we determine Hlk (t)Vk (t)Vk∗ (t)H∗lk (t). El (t) = (6.29) k∈K,k=l, ρk (t)=1 137 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems We set Ul (t)= El (t) dl , where El (t) dl is a matrix consisting of the eigenvectors of matrix El (t) corresponding to its dl smallest eigenvalues. Those vectors span the subspace with the least interference. Algorithm 6.3 Semi-distributed scheduling and interference alignment (SDSIA) algorithm. SDSIA is run at each time slot t, and takes the queue backlogs Q(t), and channel state information as input. It is initialized with αmax , Z, Pth , ǫ, and preset decoding matrix U0 (t). 1: Initialization: Set ρ(t) = 0, V(t). 2: Initialize candidate set S of all users that have data to send. 3: while S = ∅ do 4: Set k′ := arg max Qk (t). k∈S 5: Set ρk′ (t) := 1. 6: S := S\{k′ }. 7: for each {l ∈ K | ρl (t) = 1} do 8: El (t) := [0]Nl ×Nl . 9: for each {k ∈ K | k = l, ρk (t) = 1} do 10: El (t) := El (t) + Hlk (t)Vk (t)Vk∗ (t)H∗lk (t). 11: end for 12: if k∈K ρk (t) = 1 then 13: Ul (t) := U0 (t). 14: else 15: Ul (t) := El (t) dl . 16: end if 17: end for 18: feasibility := 1. 19: for each {l ∈ K | ρl (t) = 1} do 20: if (Ill (t) < Pth ) || (Il (t) > ǫ) then 21: Set feasibility := 0. 22: end if 23: end for 24: if feasibility = 1 then 25: ρk′ (t) := 0. 26: end if 27: end while 3) Feasibility check (lines 18-23): In each iteration, having obtained the scheduled set of users and the signal design V(t) and U(t), the feasibility of the design is checked based on the interference alignment requirements. If the desired signal strength is higher than 138 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems Pth at all receivers (i.e., the first set of constraints in problem (6.20) is satisfied), and the interference strength is also less than threshold ǫ (the second set of constraints in (6.20) is satisfied), then the design is feasible. To be able to implement the signal design and feasibility check phases in a semidistributed manner, we have to run the algorithm in both transmitters and receivers in a receiver-based manner. That is, at the transmitters a similar algorithm as at the receivers is executed using channel reciprocity. At each time slot t, Algorithm 6.3 is first run at the receivers where the encoding matrices V(t) are set equal to an initial value and decoding matrices U(t) as well as ρ(t) are obtained. At the transmitters, using channel reciprocity and the obtained results for U(t), we set ← ∗ Hkl (t) = Hlk (t), ← Vk (t) = Uk (t), ∀ k, l ∈ K, (6.30) ∀ k ∈ K. (6.31) ← We use (.) to denote the corresponding variables when the algorithm is run at the transmitter. Then, the algorithm is run at the transmitters in a similar way as at the receivers ← and encoding matrices V(t) are obtained by finding U(t). Signal design matrices U(t) and ← V(t) and the obtained schedule ρ (t) are then used for data transmission. In the transmission scheduling phase, we use the greedy maximal scheduling (GMS) policy [114] to maximize the first term in the objective function of (6.17) in a semi-distributed manner. GMS is sub-optimal and may be implemented in a distributed manner. It has been shown in [114] that in the 1-hop interference model, GMS can achieve at least half of the throughput achieved by the optimal policy. We refer to SDSIA as semi-distributed because the information related to the queue backlogs, encoding matrices, and design fea- 139 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems sibility must be passed between users via control messages. Then, each phase will be performed at each user in a distributed manner. The second part of SDSIA (i.e., admission control) is performed in a distributed manner in each transmitter. Each user k ∈ K checks if the number of packets waiting to be sent in its queue Qk (t) is less than design parameter Z. In this case, it admits αmax packets into the queue. 6.6 Performance Evaluation We now present the simulation results of the SIA algorithm as well as the heuristic SDSIA algorithm. First, we show the convergence of the SIA algorithm in one time slot. Then, we show how the SDSIA algorithm follows the SIA algorithm when the algorithm parameters Pth and ǫ and the number of users K change. Finally, we compare our heuristic SDSIA algorithm with two other approaches: (i) an approach that is based only on interference alignment but without greedy scheduling and (ii) an approach that uses GMS but not interference alignment. We run the simulations for the network topology shown in Fig. 6.1. We assume that the channel coefficients in matrices Hlk (t), ∀ k, l ∈ K, follow a complex Gaussian distribution. In our simulations, we set the number of antennas at both transmitters and receivers to be equal to two. dk is set to be one. We verify the convergence of the SIA algorithm in one particular time slot and for one particular channel realization. Fig. 6.2 shows the optimum of primal problem (6.24), (6.25), and master problem (6.26) in a network with 5 and 10 users. The algorithm is run in a time slot at which all users have 50 packets in their backlog queues. As shown in Fig. 6.2, for the case of K = 5, after five iterations the lower bound and upper bound converge to the value of −150 which corresponds to the solution allowing users 1, 3, and 5 to send their packets. The number of iterations increases with the number of users in the 140 Optimum of primal problem and master problem Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems 0 −100 −200 −300 −400 Upper Bound, optimum of primal problem (K=5) −500 Lower Bound, optimum of master problem (K=5) −600 Upper Bound, optimum of primal problem (K=10) Lower Bound, optimum of master problem (K=10) −700 5 10 15 20 25 30 35 40 45 50 55 60 65 70 Iterations, m Figure 6.2: Convergence of SIA algorithm is shown in one time slot when there are 5 and 10 users in the network. network. For K = 10, the algorithm converges to the value of −300 after 62 iterations and schedules users 1, 3, 5, 6, 8, and 10. Note that if the primal problem (6.24) is infeasible in one iteration, the upper bound gets the value of the last feasible primal problem in that iteration. We observe that the optimum for the master problem is non-decreasing. Fig. 6.3 shows the optimum of problem (6.20) in one time slot for the SIA and SDSIA algorithms when interference leakage threshold ǫ increases from 0 to 100. During the increase of ǫ, we also increase the receiver threshold Pth to keep the signal to interference ratio constant. We set the number of users to be five and, in that particular time slot, each user has 50 data packets to send. We run the SDSIA algorithm 2000 times for the same channel realization to make the results independent of the random behaviour of the SDSIA algorithm. We also run the simulations for both algorithms for 100 different channel realizations. We know that when ǫ increases, it is easier to satisfy the second set of constraints in problem (6.20) leading to an increase in the optimum value. However, the increase in the interference leakage threshold increases the interference in the receivers. Therefore, 141 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems 200 SIA algorithm SDSIA algorithm The optimum of problem (20) 180 160 140 120 100 80 60 40 20 0 0 10 20 30 40 50 ǫ 60 70 80 90 100 Figure 6.3: The optimal value of problem (6.20) changes for both the SIA and SDSIA algorithms when interference leakage threshold ǫ and receiver threshold Pth change. we need to increase the receiver threshold Pth to maintain the signal to interference ratio constant which makes it harder to satisfy the first constraint in problem (6.20). This causes a decrease in the optimum value. The results in Fig. 6.3 show that the optimal value of problem (6.20) first increases when ǫ increases to an optimal value after which the effect of increasing Pth dominates and the optimal value of problem (6.20) decreases. It is shown that the SIA algorithm achieves up to 0.77 transmissions per user (the objective function is 194) when ǫ = 5. We can also see that the heuristic SDSIA algorithm finds solutions that are within 85% of optimality. Fig. 6.4 shows the average number of transmissions per user in one particular time slot when the number of users changes. The complexity of the SIA algorithm increases with the number of users. Thus, we consider no more than 10 users for this part of our study. Again, consider a time slot in which each user has 50 data packets to send. We choose Pth = 10 and ǫ = 1 for this set of simulations. We see that for both approaches, the number of transmissions per user decreases when the number of users increases. We also observe that the SDSIA algorithm is at least within 70% (90% on average) of optimality. 142 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems Number of transmissions per user 1 SIA algorithm SDSIA algorithm 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 1 2 3 4 5 6 7 8 9 10 Number of users K Figure 6.4: The number of transmissions per user is shown when the number of users K increases. To highlight the effect of the two separate techniques employed in the SDSIA algorithm (interference alignment and greedy maximal scheduling), in Fig. 6.5 we compare the heuristic with two other algorithms in a wireless MIMO system. The IA algorithm uses interference alignment and all users transmit in each time slot (no GMS). The GMS algorithm uses greedy maximal scheduling (no interference alignment). We set Pth = 10, ǫ = 1, and all backlog queues are initially empty. We vary the number of users from 1 to 15. Each simulation run is for 1000 time slots. Each data point in Fig. 6.5 shows the average data rate achievable for each user R = 1 K age over several simulation runs. Rl = U∗l (t)Hll Vl (t)Vl∗(t)H∗ll (t)Ul (t)(1dl ×dl + l∈K 1 T k=l Rl using each approach and is the aver- t∈T Rl (t), where Rl (t) = log2 det(1dl ×dl + U∗l (t)Hlk Vk (t)Vk∗ (t)H∗lk (t)Ul (t))−1 ), is the data rate of user l in time slot t. We can see that for all approaches, the average achievable data rate decreases when the number of users increases. Clearly, for one user we have the same performance for all algorithms. When the number of users is two, GMS’s performance is decreased to half. This is because the data rate Rl (t) is constant in GMS and 143 Average (per user) achievable data rate Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems 50 SDSIA algorithm GMS algorithm IA algorithm 45 40 35 30 25 20 15 10 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Number of users K Figure 6.5: The average per user achievable data rate is shown when the number of users increases from 1 to 20. therefore, it cannot schedule both users at the same time using the same rate. However, interference alignment techniques are able to allow both users to transmit with lower rate and therefore, SDSIA and IA’s performances are the same and better than that of GMS. When the number of users increases, the IA algorithm which schedules all users to transmit in each time slot, has the highest number of transmitted packets per user. However, the interference created by the transmitting users decreases the average data rate. The SDSIA algorithm which employs both interference alignment and scheduling outperforms the other two approaches. 6.7 Summary In this chapter, we considered efficient joint scheduling, packet admission control, and interference alignment in wireless MIMO systems with many users. We formulated the corresponding optimization problem as a nonlinear mixed integer programming problem with non-convex constraints and used a sequence of mathematical tools to solve the problem. 144 Chapter 6. Scheduling and Interference Alignment for MIMO Wireless Systems We also developed a heuristic algorithm, which is computationally efficient. In addition, in our simulation studies, we observed that the heuristic is within 90% of optimality on average. We showed through simulations that our approach can dramatically improve the network performance when compared with systems that employ either only interference alignment or only scheduling. The presented work suggests, in essence, that network performance can be improved by considering interference alignment and scheduling decisions in a common framework. 145 Chapter 7 Conclusions and Future Work In this chapter, we summarize the results and highlight the contributions of this thesis. We also suggest several topics for future work. 7.1 Research Contributions • In Chapter 2, we considered data rate and channel code rate allocation in wireless networks with multipath routing and channel coding. We formulated a network utility maximization problem with the goal of improving network fairness with unreliable links. We considered both adaptive and non-adaptive coding schemes. We also developed our rate allocation algorithm such that it can adapt with fast changes in the network due to varying channel conditions and mobility. We studied the effects of fast fading on the performance of our algorithm. • In Chapter 3, we considered the end-to-end delay for network data flows. For this purpose, we incorporated the end-to-end delay in the network utility function and solved the problem of data rate and channel code rate allocation with the goal of decreasing the delay in the network. We considered both maximizing the aggregate network utility and maximizing the minimum network utility through which the concept of fairness is considered. We showed through simulations that we can decrease the average delay in the network at the cost of a slight decrease in network throughput. 146 Chapter 7. Conclusions and Future Work • In Chapter 4, we formulated the problem of data rate allocation for routing paths as well as network coding paths for a wireless network with unreliable links. We showed via simulations that considering the reliability of wireless links in our rate allocation problem leads to better performance compared to the case when reliability is not considered. This becomes more important when fairness is important to be provided. • In Chapter 5, we considered the achievability of our data rate allocation schemes by providing a transmission scheduling and packet admission algorithm for wireless mesh networks. We verified that our algorithm follows the performance of a centralized data rate allocation algorithm. We also compared fairness provisioning under our proposed algorithm with that under similar algorithms that ignore fairness to observe the effects of fairness provisioning in network performance. Finally, we compared the performance of the algorithm with a class of fair algorithms that are based on maximizing the network utility function. • In Chapter 6, we formulated the joint problem of interference alignment, admission control, and transmission scheduling in MIMO systems. The formulated problem is a non-linear mixed-integer programming problem and therefore, hard to solve. We used several techniques to break this problem into one convex optimization problem and one mixed-integer programming problem and solved it through Benders decomposition method. We also developed a heuristic approach with much less degrees of complexity to solve the problem in a semi-distributed manner. We showed through simulations that the heuristic follows the optimal central solution with some degree of sub-optimality. We also showed that using both scheduling techniques and interference alignment techniques, we gained better performance comparing with the case when one of them is being used. 147 Chapter 7. Conclusions and Future Work 7.2 Suggestions for Future Work In the following, we consider several interesting possibilities for extension of the current work. 1. Delay-optimal transmission scheduling: In Chapter 3, we studied optimal rate allocation problems with the goal of maximizing the network utility when both throughput and end-to-end delay were incorporated in the utility function of each flow. The remaining question would be: “How can we achieve those optimal data rates in a distributed manner?” An interesting future work is to use stochastic optimization to design transmission scheduling, admission control algorithms, and channel code rate allocations to improve the performance of the network in terms of both the network throughput and the end-to-end delay. 2. Transmission scheduling with network coding: The performance of the network is improved via network coding. An interesting future work is to use Lyapunov techniques to develop transmission scheduling and admission control algorithms in wireless networks in which intersession network coding is enabled. In such network settings, the weight of each wireless link for data transmission would depend not only on the data backlog of that particular link, but also on the backlog of the other link which is going to participate in the network coding scheme. This extra dependency creates new challenges to be solved. 3. Interference alignment in multihop networks: Interference alignment techniques can also be used in multihop wireless networks with multiple antennas. Another future work is to use stability theory and Lyapunov techniques for transmission scheduling and encoding and decoding matrices design. In such network settings, the goal is to improve the number of simultaneous transmissions and thus the network 148 Chapter 7. Conclusions and Future Work throughput. 4. Heuristic approaches for interference alignment: The main challenge of using interference alignment in MIMO systems is that interference alignment is computationally hard. It requires significant processing capability to compute schedules and encoding and decoding matrices at each time slot. One direction could be the investigation of effective heuristics. 149 Bibliography [1] J. Shi, O. Gurewitz, V. Mancuso, J. Camp, and E. W. Knightly, “Measurement and modeling of the origins of starvation in congestion controlled mesh networks,” in Proc. of IEEE Infocom, Phoenix, AZ, Apr. 2008. [2] R. Jain, W. Hawe, and D. Chiu, “A quantitative measure of fairness and discrimination for resource allocation in shared computer systems,” DEC Research Report DEC-TR-301, Sept. 1984. [3] X. Lin and N. B. Shroff, “The impact of imperfect scheduling on cross-layer congestion control in wireless networks,” IEEE/ACM Trans. on Networking, vol. 14, no. 2, pp. 302–315, Apr. 2006. [4] M. Andrews, L. Qian, and A. Stolyar, “Optimal utility based multi-user throughput allocation subject to throughput constraints,” in Proc. of IEEE Infocom, Miami, FL, Mar. 2005. [5] J. Liu, A. Stolyar, M. Chiang, and H. V. Poor, “Queue back-pressure random access in multihop wireless networks: Optimality and stability,” IEEE Trans. on Information Theory, vol. 55, no. 9, pp. 4087–4098, Sept. 2009. [6] A. Eryilmaz and R. Srikant, “Fair resource allocation in wireless networks using queue-length-based scheduling and congestion control,” IEEE/ACM Trans. on Networking, vol. 15, no. 6, pp. 1333–1344, Dec. 2007. [7] ——, “Joint congestion control, routing, and MAC for stability and fairness in wireless networks,” IEEE J. Select. Areas Commun., vol. 24, no. 8, pp. 1514–1524, Aug. 2006. [8] M. J. Neely, E. Modiano, and C. Li, “Fairness and optimal stochastic control for heterogeneous networks,” IEEE/ACM Trans. on Networking, vol. 16, no. 2, pp. 396– 409, Apr. 2008. [9] S. Sarkar and L. Tassiulas, “Fair distributed congestion control in multirate multicast networks,” IEEE/ACM Trans. on Networking, vol. 13, no. 1, pp. 121–133, Feb. 2005. [10] L. Tassiulas and S. Sarkar, “Maxmin fair scheduling in wireless ad hoc networks,” IEEE J. Select. Areas Commun., vol. 23, no. 1, pp. 163–173, Jan. 2005. 150 Bibliography [11] L. Jiang and J. Walrand, “A distributed CSMA algorithm for throughput and utility maximization in wireless networks,” IEEE/ACM Trans. on Networking, vol. 18, no. 3, pp. 960–972, June 2010. [12] ——, “Approaching throughput-optimality in distributed CSMA scheduling algorithms with collisions,” IEEE/ACM Trans. on Networking, vol. 1, no. 1, p. 1, Apr. 2010. [13] D. Wang, X. Wang, and X. Cai, “Optimal power control for multi-user relay networks over fading channels,” IEEE Trans. on Wireless Communications, vol. 10, no. 1, pp. 199–207, Jan. 2011. [14] C. B. R. Estrello, G. H. Valdez, and F. A. C. Perez, “System-level analysis of mobile cellular networks considering link unreliability,” IEEE Trans. on Vehicular Technology, vol. 58, no. 2, pp. 926–940, Feb. 2009. [15] B. Wang, Z. He, and Y. Sun, “Distributed rate allocation and performance optimization for video communication over mesh networks,” in Proc. of ICIP, San Antonio, TX, Sept. 2007. [16] A. Beljadid, A. S. Hafid, and A. Gendreau, “Design of wireless mesh networks: Expansion and reliability studies,” in Proc. of IEEE Globecom, New Orleans, LA, Dec. 2008. [17] A. P. Snow, U. Varshney, and A. D. Malloy, “Reliability and survivability of wireless and mobile networks,” IEEE Computer Mag., vol. 33, pp. 49–55, July 2000. [18] M. Ghaderi, D. Towsley, and J. Kurose, “Reliability gain of network coding in lossy wireless networks,” in Proc. of IEEE Infocom, Phoenix, AZ, Apr. 2008. [19] T. Issariyakul, E. Hossain, and A. S. Alfa, “End-to-end batch transmission in a multihop and multirate wireless network: Latency, reliability, and throughput analysis,” IEEE Trans. on Mobile Computing, vol. 5, pp. 1143–1155, Sept. 2006. [20] A. Willig and H. Karl, “Data transport reliability in wireless sensor networks. A survey of issues and solutions,” PIK Journal, vol. 28, pp. 86–92, June 2005. [21] U. Varshney, A. P. Snow, and A. D. Malloy, “Measuring the reliability and survivability of infrastructure-oriented wireless networks,” in Proc. of IEEE Local Computer Networks, Tampa, FL, Nov. 2001. [22] J. W. Lee, M. Chiang, and A. R. Calderbank, “Price-based distributed algorithms for rate-reliability based tradeoff in network utility maximization,” IEEE J. Select. Areas Commun., vol. 24, pp. 962–976, May 2006. 151 Bibliography [23] Q. Gao, J. Zhang, and S. V. Hanly, “Cross-layer rate control in wireless networks with lossy links: Leaky-pipe flow, effective network utility maximization and hopby-hop algorithms,” IEEE Trans. on Wireless Communications, vol. 8, no. 6, pp. 3068–3076, June 2009. [24] D. S. Lun, M. M´edard, R. Koetter, and M. Effros, “On coding for reliable communication over packet networks,” Physical Communication, vol. 1, no. 1, pp. 3–20, Mar. 2008. [25] Z. Ye, S. V. Krishnamurthy, and S. K. Tripathi, “A framework for reliable routing in mobile ad hoc networks,” in Proc. of IEEE Infocom, San Francisco, CA, Apr. 2003. [26] Y. Fan, J. Zhang, and X. Shen, “Mobility-aware multi-path forwarding scheme for wireless mesh networks,” in Proc. of IEEE WCNC, Las Vegas, NV, Apr. 2008. [27] S. Dulman, T. Nieberg, J. Wu, and P. Havinga, “Trade-off between traffic overhead and reliability in multipath routing for wireless sensor networks,” in Proc. of IEEE WCNC, New Orleans, LA, Mar. 2003. [28] J. Huang, Z. Li, M. Chiang, and A. K. Katsaggelos, “Joint source adaptation and resource allocation for multi-user wireless video streaming,” IEEE Trans. on Circuits and Systems for Video Technology,, vol. 18, no. 5, pp. 582–595, May 2008. [29] D. O’Neill, A. Goldsmith, and S. Boyd, “Wireless network utility maximization,” in Proc. of MILCOM, San Diego, CA, Nov. 2008. [30] Y. Lin and V. W. S. Wong, “Adaptive tuning of MIMO-enabled 802.11e WLANs with network utility maximization,” in Proc. of IEEE WCNC, Las Vegas, NV, Apr. 2008. [31] D. O’Neill, A. Goldsmith, and S. Boyd, “Optimizing adaptive modulation in wireless networks via utility maximization,” in Proc. of IEEE ICC, Beijing, China, May 2008. [32] D. O’Neill, E. Akuiyibo, S. Boyd, and A. Goldsmith, “Optimizing adaptive modulation in wireless networks via multi-period network utility maximization,” in Proc. of IEEE ICC, Cape Town, South Africa, May 2010. [33] F. P. Kelly, A. K. Maulloo, and D. K. H. Tan, “Rate control for communication networks: Shadow prices, proportional fairness and stability,” Journal of Operations Research Society, vol. 49, pp. 237–252, Mar. 1998. [34] M. Chiang, “Balancing transport and physical layers in wireless multihop networks: Jointly optimal congestion control and power control,” IEEE J. Select. Areas Commun., vol. 23, pp. 104–116, Jan. 2005. 152 Bibliography [35] L. Chen, S. H. Low, and J. C. Doyle, “Joint congestion control and media access control design for ad hoc wireless networks,” in Proc. of IEEE Infocom, Miami, FL, Mar. 2005. [36] D. O’Neill, B. S. Thian, A. Goldsmith, and S. Boyd, “Wireless NUM: Rate and reliability tradeoffs in random environment,” in Proc. of IEEE WCNC, Budapest, Hungary, Apr. 2009. [37] M. Andrews, A. F. Anta, L. Zhang, and W. Zhao, “Routing for energy minimization in the speed scaling model,” in Proc. of IEEE Infocom, San Diego, CA, Mar. 2010. [38] Y. Li, M. Chiang, and A. R. Calderbank, “Congestion control in networks with delay sensitive traffic,” in Proc. of IEEE Globecom, Washington, DC, Nov. 2007. [39] E. Jorswieck, H. Boche, and S. Naik, “Energy-aware utility regions: Multiple access pareto boundary,” IEEE Trans. on Wireless Communications, vol. 9, no. 7, pp. 2216–2226, July 2008. [40] K. Kar, S. Sarkar, and L. Tassiulas, “Achieving proportional fairness using local information in ALOHA networks,” IEEE Trans. on Automatic Control, vol. 49, pp. 1858–1862, Oct. 2004. [41] J. W. Lee, M. Chiang, and A. R. Calderbank, “Utility-optimal medium access control: Reverse and forward engineering,” in Proc. of IEEE Infocom, Barcelona, Spain, Apr. 2006. [42] A. H. Mohsenian-Rad and V. W. S. Wong, “Cross-layer fair bandwidth sharing for multi-channel wireless mesh networks,” IEEE Trans. on Wireless Communications, vol. 7, no. 9, pp. 3436–3445, Sept. 2008. [43] T. Voice and G. Raina, “Stability analysis of a max-min fair rate control protocol (RCP) in a small buffer regime,” IEEE Trans. on Automatic Control, vol. 54, no. 8, pp. 1908–1913, Aug. 2009. [44] R. Ahlswede, N. Cai, S. Y. R. Li, and R. W. Yeung, “Network information flow,” IEEE Trans. on Information Theory, vol. 46, pp. 1204–1216, July 2000. [45] C. C. Wang and N. B. Shroff, “Beyond the butterfly- A graph-theoretic characterization of the feasibility of network coding with two simple unicast sessions,” in Proc. of IEEE ISIT, Nice, France, June 2007. [46] D. Lun, N. Ratnakar, M. Medard, R. Koetter, D. Karger, T. Ho, E. Ahmed, and F. Zhao, “Minimum-cost multicast over coded packet networks,” IEEE Trans. on Information Theory, vol. 52, pp. 2608–2623, June 2006. 153 Bibliography [47] S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft, “XORs in the air: Practical wireless network coding,” in Proc. of ACM SIGCOMM, Pisa, Italy, Sept. 2006. [48] V. Shah-Mansouri and V. W. S. Wong, “Maximum-lifetime coding subgraph for multicast traffic in wireless sensor networks,” in Proc. of IEEE Globecom, New Orleans, LA, Dec. 2008. [49] T. Cui, L. Chen, and T. Ho, “Energy efficient opportunistic network coding for wireless networks,” in Proc. of IEEE Infocom, Phoenix, AZ, Apr. 2008. [50] A. Khreishah, C. C. Wang, and N. B. Shroff, “Optimization based rate control for communication networks with inter-session network coding,” in Proc. of IEEE Infocom, Phoenix, AZ, Apr. 2008. [51] Y. Li, M. Chiang, A. R. Calderbank, and S. N. Diggavi, “Optimal rate-reliabilitydelay tradeoff in networks with composite links,” IEEE Trans. on Communications, vol. 57, pp. 1390–1401, May 2009. [52] J. W. Lee, M. Chiang, and A. R. Calderbank, “Distributed algorithms for optimal rate-reliability tradeoff in networks,” in Proc. of IEEE ISIT, Adelaide, Australia, Sept. 2005. [53] S. Huang and B. Mukherjee, “Adaptive reliable multi-path provisioning in WDM mesh networks,” in Proc. of IEEE ICC, Beijing, China, May 2008. [54] H. Ma, D. Fayek, and P. H. Ho, “Availability-constrained multipath protection in backbone networks with double-link failure,” in Proc. of IEEE ICC, Beiging, China, May 2008. [55] V. Bui, W. Zhu, A. Botta, and A. Pescape, “An MDP-based approach for multipath data transmission over wireless networks,” in Proc. of IEEE ICC, Beijing, China, May 2008. [56] B. Yahya and J. B. Othman, “REER: Robust and energy efficient multipath routing protocol for wireless sensor networks,” in Proc. of IEEE Globecom, Honolulu, HI, Dec. 2009. [57] D. Quintas and V. Friderikos, “Energy efficient relaying within a cell: Multi path versus shortest path routing,” in Proc. of IEEE Infocom, San Diego, CA, Mar. 2010. [58] S. Misra, G. Xue, and D. Yang, “Polynomial time approximations for multi-path routing with bandwidth and delay constraints,” in Proc. of IEEE Infocom, Rio De Janeiro, Brazil, Apr. 2009. 154 Bibliography [59] I. Cidon, R. Rom, and Y. Shavitt, “Analysis of multi-path routing,” IEEE/ACM Trans. on Networking, vol. 6, pp. 885–896, Dec. 1999. [60] A. Nasipuri and R. Castaneda, “Performance of multipath routing for on-demand protocols in mobile ad hoc networks,” ACM Journal on Mobile Networks and Applications., vol. 6, pp. 339–349, Aug. 2001. [61] S. J. Lee and M. Gerla, “AODV-BR: Backup routing in ad hoc networks,” in Proc. of IEEE WCNC, Chicago, IL, Sept. 2000. [62] L. Wang, L. Zhang, Y. Shu, and M. Dong, “Multipath source routing in wireless ad hoc networks,” in Proc. of Canadian Conference on Electrical and Computer Engineering, Halifax, NS, May 2000. [63] R. Leung, J. Liu, E. Poon, A. L. C. Chan, and B. Li, “MP-DSR: A QoS-aware multipath dynamic source routing protocol for wireless ad-hoc networks,” in Proc. of LCN, Tampa, FL, Nov. 2001. [64] S. J. Lee and M. Gerla, “Split multipath routing with maximally disjoint paths in ad hoc networks,” in Proc. of ICC, Beijing, China, May 2001. [65] M. K. Marina and S. R. Das, “On-demand multipath distance vector routing in ad hoc networks,” in Proc. of ICNP, Riverside, CA, Nov. 2001. [66] D. Ganesan, R. Govindan, S. Shenker, and D. Estrin, “Highly-resilient, energyefficient multipath routing in wireless sensor networks,” ACM SIGMOBILE Mobile Computing and Communications Review, vol. 5, no. 4, pp. 10–24, Oct. 2001. [67] S. A. Jafar and M. J. Fakhereddin, “Degrees of freedom for the MIMO interference channel,” IEEE Trans. on Information Theory, vol. 53, no. 7, pp. 2637 –2642, July 2007. [68] V. R. Cadambe and S. A. Jafar, “Interference alignment and degrees of freedom of the K-user interference channel,” IEEE Trans. on Information Theory, vol. 54, no. 8, pp. 3425–3441, Aug. 2008. [69] B. Nazer, M. Gastpar, S. A. Jafar, and S. Vishwanath, “Ergodic interference alignment,” in Proc. of IEEE ISIT, Seoul, Korea, July 2009. [70] K. Gomadam, V. R. Cadambe, and S. A. Jafar, “Approaching the capacity of wireless networks through distributed interference alignment,” in Proc. of IEEE Globecom, New Orleans, LA, Dec. 2008. [71] H. Maleki, S. A. Jafar, and S. Shamai, “Retrospective interference alignment,” in Proc. of IEEE ISIT, Saint-Petersburg, Russia, Aug. 2011. 155 Bibliography [72] C. M. Yetis, G. Tiangao, S. A. Jafar, and A. H. Kayran, “On feasibility of interference alignment in MIMO interference networks,” IEEE Trans. on Signal Processing, vol. 58, no. 9, pp. 4771–4782, Sept. 2010. [73] ——, “Feasibility conditions for interference alignment,” in Proc. of IEEE Globecom, Honolulu, HI, Dec. 2009. [74] K. R. Kumar and X. Feng, “An iterative algorithm for joint signal and interference alignment,” in Proc. of IEEE ISIT, Austin, TX, June 2010. [75] S. Gollakota, A. D. Perli, and D. Katabi, “Interference alignment and cancellation,” in Proc. of ACM SIGCOMM, Barcelona, Spain, Aug. 2009. [76] I. Santamaria, O. Gonzalez, R. W. Heath, and S. W. Peters, “Maximum sum-rate interference alignment algorithms for MIMO channels,” in Proc. of IEEE Globecom, Miami, FL, Dec. 2010. [77] H. S. Dhillon and R. M. Buehrer, “On the maximum sum-rate of cognitive MIMO interference channels,” in Proc. of MILCOM, San Jose, CA, Nov. 2010. [78] C. Suh, M. Ho, and D. Tse, “Downlink interference alignment,” IEEE Trans. on Communications, vol. 59, no. 9, pp. 2616–2626, Sept. 2011. [79] K. A. Das, S. Vishwanath, S. A. Jafar, and A. Markopoulou, “Network coding for multiple unicasts: An interference alignment approach,” in Proc. of IEEE ISIT, Austin, TX, June 2010. [80] A. Ramakrishnan, A. Das, H. Maleki, A. Markopoulou, S. A. Jafar, and S. Vishwanath, “Network coding for three unicast sessions: Interference alignment approaches,” in Proc. of Allerton Conf. on Communication, Control, and Computing, Monticello, IL, Oct. 2010. [81] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004. [82] S. Boyd, S. J. Kim, L. Vandenberghe, and A. Hassibi, A Tutorial on Geometric Programming. Springer Science and Business Media, 2007. [83] M. Chiang, Geometric Programming for Communication Systems. Foundations and Trends in Networking, 2005. [84] C. A. Floudas, Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications. Oxford University Press, 1995. [85] J. G. Proakis, Digital Communications. 4th edition, New York: McGraw-Hill, 2001. 156 Bibliography [86] R. Gupta and J. Walrand, “Approximating maximal cliques in ad-hoc networks,” in Proc. of IEEE PIMRC, Barcelona, Spain, Sept. 2004. [87] C. Shannon, “A theorem on coloring the lines in the network,” J. Math. Phys., vol. 28, pp. 148–151, Sept. 1949. [88] Y. Nesterov and A. Nemirovsky, Interior point polynomial algorithms in convex programming. SIAM, 1994. [89] “MOSEK software.” [Online]. Available: http://www.mosek.com [90] D. Ren, Y. T. H. Li, and S. H. G. Chan, “Fast-mesh: A low-delay high-bandwidth mesh for peer-to-peer live streaming,” IEEE Trans. on Multimedia, vol. 11, no. 8, pp. 1446 –1456, Dec. 2009. [91] K. Ronasi, A. H. Mohsenian-Rad, V. W. S. Wong, S. Gopalakrishnan, and R. Schober, “Optimal data and channel code rate allocation in wireless networks with multi-path routing,” in Proc. of IEEE ICC, Kyoto, Japan, June 2011. [92] D. ONeill, A. J. Goldsmith, and S. Boyd, “Cross-layer design with adaptive modulation: Delay, rate, and energy tradeoffs,” in Proc. of IEEE Globecom, New Orleans, LA, Dec. 2008. [93] M. Saad, A. Leon-Garcia, and W. Yu, “Optimal network rate allocation under endto-end quality-of-service requirements,” IEEE Trans. on Network and Service Management, vol. 4, pp. 40–49, Dec. 2007. [94] M. Saad, A. L. Garcia, and W. Yu, “Delay constrained optimal resource utilization of wireless networks for distributed control systems,” IEEE Communications Letter, vol. 12, pp. 289–291, Apr. 2008. [95] M. G. Kallitsis, R. D. Callaway, M. Devetsikiotis, and G. Michailidis, “Distributed and dynamic resource allocation for delay sensitive network services,” in Proc. of IEEE Globecom, New Orleans, LA, Dec. 2008. [96] S. Kalyanasundaram, E. K. P. Chong, and N. B. Shroff, “Optimal resource allocation in multi-class networks with user-specified utility functions,” Comput. Networks, vol. 38, pp. 613–630, Apr. 2002. [97] D. Bertsekas and R. Gallager, Data Networks, 2nd Edition. Prentice Hall, 1992. [98] A. Mohsenian-Rad, J. Huang, V. Wong, S. Jaggi, and R. Schober, “Game-theoretical analysis of inter-session network coding,” in Proc. of IEEE ICC, Dresden, Germany, June 2009. [99] T. M. Cover and J. A. Thomas, Elements of Information Theory. Wiley-Interscience, 1999. 157 Bibliography [100] J. Mo and J. Walrand, “Fair end-to-end window-based congestion control,” IEEE/ACM Trans. on Net., vol. 8, pp. 556–567, Oct. 2000. [101] D. P. Bertsekas, Nonlinear Programming, second edition. Athena Scientific, 1999. [102] D. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical methods. Athena Scientific, 1997. [103] L. Georgiadis, M. J. Neely, and L. Tassiulas, Resource Allocation and Cross Layer Control in Wireless Networks,. Foundations and Trends in Networking, 2006. [104] M. J. Neely, “Delay-based network utility maximization,” in Proc. of IEEE Infocom, San Diego, CA, Mar. 2010. [105] M. J. Neely, E. Modiano, and C. E. Rohrs, “Dynamic power allocation and routing for time-varying wireless networks,” IEEE J. Select. Areas Commun., vol. 23, no. 1, pp. 89–103, Jan. 2005. [106] C. P. Li and M. J. Neely, “Energy-optimal scheduling with dynamic channel acquisition in wireless downlinks,” IEEE Trans. on Mobile Computing, vol. 9, no. 4, pp. 527–539, Apr. 2010. [107] L. Lin, X. Lin, and N. B. Shroff, “Low-complexity and distributed energy minimization in multihop wireless networks,” IEEE/ACM Trans. on Networking, vol. 18, no. 2, pp. 501–514, Apr. 2010. [108] L. Bui, R. Srikant, and A. Stolyar, “Novel architectures and algorithms for delay reduction in back-pressure scheduling and routing,” in Proc. of IEEE Infocom, Rio de Janeiro, Brazil, Apr. 2009. [109] L. Chen, S. H. Low, J. C. Doyle, and M. Chiang, “Cross layer congestion control, routing and scheduling design in ad hoc wireless networks,” in Proc. of IEEE Infocom, Barcelona, Spain, Apr. 2006. [110] L. Ying and S. Shakkottai, “Scheduling in mobile ad hoc networks with topology and channel-state uncertainty,” in Proc. of IEEE Infocom, Rio de Janeiro, Brazil, Apr. 2009. [111] S. Chen, Y. Fang, and Y. Xia, “Lexicographic maxmin fairness for data collection in wireless sensor networks,” IEEE Trans. on Mobile Computing, vol. 6, no. 7, pp. 762–776, July 2007. [112] H. Shirani-Mehr, G. Caire, and M. J. Neely, “MIMO downlink scheduling with nonperfect channel state knowledge,” IEEE Trans. on Communications, vol. 58, no. 7, pp. 2055–2066, July 2010. 158 Bibliography [113] J. Ryu, V. Bhargava, N. Paine, and S. Shakkottai, “Back-pressure routing and rate control for ICNs,” in Proc. of ACM MobiCom, Chicago, IL, Sept. 2010. [114] C. Joo, X. Lin, and N. B. Shroff, “Understanding the capacity region of the greedy maximal scheduling algorithm in multihop wireless networks,” in Proc. of IEEE Infocom, Phoenix, AZ, Apr. 2008. [115] K. Ronasi, V. W. S. Wong, S. Gopalakrishnan, and R. Schober, “Distributed scheduling in multihop wireless networks with maxmin fairness provisioning,” IEEE Trans. on Wireless Communications, vol. 11, pp. 1753–1763, May 2012. [116] M. J. Neely, Stochastic Network Optimization with Application to Communication and Queueing Systems. Morgan and Claypool, 2010. [117] K. Jagannathan, M. Markakis, E. Modiano, and J. N. Tsitsiklis, “Throughput optimal scheduling in the presence of heavy-tailed traffic,” in Proc. of Allerton Conf. on Communication, Control, and Computing, Monticello, IL, Oct. 2010. [118] D. P. Bertsekas and J. N. Tsitsiklis, Parallel And Distributed Computation: Numerical Methods. Prentice Hall, 1989. [119] M. Grant and S. Boyd, “CVX: Matlab software for disciplined convex programming, version 1.21,” http://cvxr.com/cvx, Apr. 2011. 159
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Resource allocation and scheduling in wireless mesh...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Resource allocation and scheduling in wireless mesh networks Ronasi, Keivan 2012
pdf
Page Metadata
Item Metadata
Title | Resource allocation and scheduling in wireless mesh networks |
Creator |
Ronasi, Keivan |
Publisher | University of British Columbia |
Date Issued | 2012 |
Description | The unreliability of wireless mesh networks creates challenge in designing high performance wireless networks in terms of network throughput, end-to-end delay, and fairness provisioning. In this thesis, the goal is to improve the network performance in terms of these metrics. We explore several techniques such as multipath routing, channel coding, network coding, and interference alignment. We consider resource allocation both in terms of average data rate provisioning and scheduling policies in a time slot basis. First, we propose data rate and channel code rate allocation algorithms for networks with multiple paths to maximize the network throughput while all users can fairly exploit the network resources. We study the effect of adaptive and non-adaptive channel coding schemes. We also consider the end-to-end delay that each network flow experiences for data transmission. For that purpose, we formulate the problem of decreasing the end-to-end delay for network flows while improving the network throughput. Simulation results show that we can decrease the delay at the cost of a slight decrease in network throughput. We also formulate a data rate allocation problem in networks with network coding. Simulation results show that considering link reliabilities in the network coding design dramatically increases the network performance. Data rate allocation algorithms provide the average data rates at which the source must transmit data. They do not determine scheduling on a time slot basis. To address that, we consider transmission scheduling in wireless networks. We also compare the suggested algorithm with a centralized optimal data rate allocation algorithm to verify that our algorithm follows the optimal solution. Through simulations, we show that fairness provisioning leads to higher network performance. We show that the suggested algorithm outperforms the current algorithms in the literature in terms of both network throughput and fairness provisioning. Finally, we consider transmission scheduling in wireless multi-input multi-output (MIMO) systems. We formulate the problem of joint scheduling, interference alignment, and admission control in those networks and use Lyapunov stability theory to solve it. We also develop a heuristic approach to solve the problem in a semi-distributed manner. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2012-07-18 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
IsShownAt | 10.14288/1.0072888 |
URI | http://hdl.handle.net/2429/42751 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2012-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2012_fall_ronasi_keivan.pdf [ 1.29MB ]
- Metadata
- JSON: 24-1.0072888.json
- JSON-LD: 24-1.0072888-ld.json
- RDF/XML (Pretty): 24-1.0072888-rdf.xml
- RDF/JSON: 24-1.0072888-rdf.json
- Turtle: 24-1.0072888-turtle.txt
- N-Triples: 24-1.0072888-rdf-ntriples.txt
- Original Record: 24-1.0072888-source.json
- Full Text
- 24-1.0072888-fulltext.txt
- Citation
- 24-1.0072888.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0072888/manifest