Achieving optimal transmission throughput in data networks in a multi-hop wireless networks is fundamental but hard problem. The situation is aggravated when nodes are mobile. Further, multi-rate system make the analysis of throughput more complicated. In mobile scenario, link may break or be created as nodes are moving within communication range. Route Discovery' which is to find the optimal route and transmission schedule is an important issue. Route discovery entails some cost; so one would not like to initiate discovery too often. On the other hand, not discovering reasonably often entails the risk of being stuck with a suboptimal route and or schedule, which hurts end-to-end throughput. The implementation of the routing decision problem in one dimensional mobile ad hoc network as Markov decision process problem is already is discussed in the paper [1]. A heuristic based on threshold policy is discussed in the same paper without giving a way to find the threshold. In this paper, we suggested a rule for setting the threshold, given the parameters of the system. We also point out that our results remain valid in a slightly different mobility model; this model is a first step towards an open' network in which existing relay nodes can leave and or new relay nodes can join the network.
used linear programming approach to characterize networks with interference, @cite_6 . They used a conflict graph to model constraints on simultaneous transmissions. In the paper @cite_2 , both approximation algorithms that solve both the end-to-end flow routing problem and link scheduling problem near optimal are proposed. In the paper @cite_10 , it is shown that the problem of solving the optimal scheduling given the concurrency constraints to maximize network throughput, is NP-hard.
@cite_10 @cite_6 @cite_2
2038603123 2435603672
We consider the problem of throughput-optimal scheduling in wireless networks subject to interference constraints. We model the interference using a family of K -hop interference models. We define a K-hop interference model as one for which no two links within K hops can successfully transmit at the same time (Note that IEEE 802.11 DCF corresponds to a 2-hop interference model.) .For a given K, a throughput-optimal scheduler needs to solve a maximum weighted matching problem subject to the K-hop interference constraints. For K=1, the resulting problem is the classical Maximum Weighted Matching problem, that can be solved in polynomial time. However, we show that for K>1,the resulting problems are NP-Hard and cannot be approximated within a factor that grows polynomially with the number of nodes. Interestingly, we show that for specific kinds of graphs, that can be used to model the underlying connectivity graph of a wide range of wireless networks, the resulting problems admit polynomial time approximation schemes. We also show that a simple greedy matching algorithm provides a constant factor approximation to the scheduling problem for all K in this case. We then show that under a setting with single-hop traffic and no rate control, the maximal scheduling policy considered in recent related works can achieve a constant fraction of the capacity region for networks whose connectivity graph can be represented using one of the above classes of graphs. These results are encouraging as they suggest that one can develop distributed algorithms to achieve near optimal throughput in case of a wide range of wireless networks. In this paper, we propose a cross-layer scheduling algorithm that achieves a throughput “ e-close” to the optimal throughput in multihop wireless networks with a tradeoff of O([1 (e)]) in average end-to-end delay guarantees. The algorithm guarantees finite buffer sizes and aims to solve a joint congestion control, routing, and scheduling problem in a multihop wireless network while satisfying per-flow average end-to-end delay constraints and minimum data rate requirements. This problem has been solved for both backlogged as well as arbitrary arrival rate systems. Moreover, we discuss the design of a class of low-complexity suboptimal algorithms, effects of delayed feedback on the optimal algorithm, and extensions of the proposed algorithm to different interference models with arbitrary link capacities. We consider the problem of designing an online scheduling scheme for a multi-hop wireless packet network with arbitrary topology and operating under arbitrary scheduling constraints. The objective is to design a scheme that achieves high throughput and low delay simultaneously. We propose a scheduling scheme that - for networks operating under primary interference constraints - guarantees a per-flow end-to-end packet delay bound of 5dj (1-ρj), at a factor 5 loss of throughput, where dj is the path length (number of hops) of flow j and ρj is the effective loading along the route of flow j. Clearly, dj is a universal lower bound on end-to-end packet delay for flow j. Thus, our result is essentially optimal. To the best of our knowledge, our result is the first one to show that it is possible to achieve a per-flow end-to-end delay bound of O(# of hops) in a constrained network. Designing such a scheme comprises two related subproblems: Global Scheduling and Local Scheduling. Global Scheduling involves determining the set of links that will be simultaneously active, without violating the scheduling constraints. While local scheduling involves determining the packets that will be transferred across active edges. We design a local scheduling scheme by adapting the Preemptive Last-In-First-Out (PL) scheme, applied for quasi-reversible continuous time networks, to an unconstrained discrete-time network. A global scheduling scheme will be obtained by using stable marriage algorithms to emulate the unconstrained network with the constrained wireless network. Our scheme can be easily extended to a network operating under general scheduling constraints, such as secondary interference constraints, with the same delay bound and a loss of throughput that depends on scheduling constraints through an intriguing "sub-graph covering" property. Cognitive radio networks (CRNs) have the potential to utilize spectrum efficiently and are positioned to be the core technology for the next-generation multihop wireless networks. An important problem for such networks is its capacity. We study this problem for CRNs in the SINR (signal-to-interference-and-noise-ratio) model, which is considered to be a better characterization of interference (but also more difficult to analyze) than disk graph model. The main difficulties of this problem are two-fold. First, SINR is a nonconvex function of transmission powers; an optimization problem in the SINR model is usually a nonconvex program and NP-hard in general. Second, in the SINR model, scheduling feasibility and the maximum allowed flow rate on each link are determined by SINR at the physical layer. To maximize capacity, it is essential to follow a cross-layer approach, but joint optimization at physical (power control), link (scheduling), and network (flow routing) layers with the SINR function is inherently difficult. In this paper, we give a mathematical characterization of the joint relationship among these layers. We devise a solution procedure that provides a (1- ) optimal solution to this complex problem, where is the required accuracy. Our theoretical result offers a performance benchmark for any other algorithms developed for practical implementation. Using numerical results, we demonstrate the efficacy of the solution procedure and offer quantitative understanding on the interaction of power control, scheduling, and flow routing in a CRN. In this paper, we propose a cross-layer scheduling algorithm that achieves a throughput "epsilon-close" to the optimal throughput in multi-hop wireless networks with a tradeoff of O(1 epsilon) in delay guarantees. The algorithm aims to solve a joint congestion control, routing, and scheduling problem in a multi-hop wireless network while satisfying per-flow average end-to-end delay guarantees and minimum data rate requirements. This problem has been solved for both backlogged as well as arbitrary arrival rate systems. Moreover, we discuss the design of a class of low-complexity suboptimal algorithms, the effects of delayed feedback on the optimal algorithm, and the extensions of the proposed algorithm to different interference models with arbitrary link capacities. In this paper, a concurrent transmission scheduling algorithm is proposed to enhance the resource utilization efficiency for multi-Gbps millimeter-wave (mmWave) networks. Specifically, we exploit spatial-time division multiple access (STDMA) to improve the system throughput by allowing both non-interfering and interfering links to transmit concurrently, considering the high propagation loss at mmWave band and the utilization of directional antenna. Concurrent transmission scheduling in mmWave networks is formulated as an optimization model to maximize the number of flows scheduled in the network such that the quality of service (QoS) requirement of each flow is satisfied. We further decompose the optimization problem and propose a flip-based heuristic scheduling algorithm with low computational complexity to solve the problem. Extensive simulations demonstrate that the proposed algorithm can significantly improve the network performance in terms of network throughput and the number of supported flows. In a wireless network, a sophisticated algorithm is required to schedule simultaneous wireless transmissions while satisfying interference constraint that two neighboring nodes can not transmit simultaneously. The scheduling algorithm need to be excellent in performance while being simple and distributed so as to be implementable. The result of Tassiulas and Ephremides (1992) imply that the algorithm, scheduling transmissions of nodes in the 'maximum weight independent set' (MWIS) of network graph, is throughput optimal. However, algorithmically the problem of finding MWIS is known to be NP-hard and hard to approximate. This raises the following questions: is it even possible to obtain throughput optimal simple, distributed scheduling algorithm? if yes, is it possible to minimize delay of such an algorithm? Motivated by these questions, we first provide a distributed throughput optimal algorithm for any network topology. However, this algorithm may induce exponentially large delay. To overcome this, we present an order optimal delay algorithm for any non-expanding network topology. Networks deployed in geographic area, like wireless networks, are likely to be of this type. Our algorithm is based on a novel distributed graph partitioning scheme which may be of interest in its own right. Our algorithm for non-expanding graph takes O (n) total message exchanges or O(l) message exchanges per node to compute a schedule. Multichannel communication in a wireless mesh network with routers having multiple radio interfaces significantly enhances the network capacity. Efficient channel assignment and routing is critical for realization of optimal throughput in such networks. In this paper, we investigate the problem of finding the largest number of links that can be activated simultaneously in a wireless mesh network subject to interference, radio and connectivity constraints. Our goal is to activate all such links and we present an interference aware channel assignment algorithm that realizes this goal. We show that the Link Interference Graph created by utilizing a frequently used interference model gives rise to a special class of graphs, known as overlapping double-disk (ODD) graphs. We prove that the Maximum Independent Set computation problem is NP-complete for this special class of graphs. We provide a Polynomial Time Approximation Scheme (PTAS) for computation of the Maximum Independent Set of an ODD graph. We use this PTAS to develop a channel assignment algorithm for a multiradio multichannel Wireless Mesh Network. We evaluate the performance of our channel assignment algorithm by comparing it with the optimal solution obtained by solving an integer linear program. Experimental results demonstrate that our channel assignment algorithm produces near optimal solution in almost all instances of the problem. In this paper, we address the scheduling problem in wireless ad hoc networks by exploiting the computational advantage that comes when such scheduling problems can be represented by claw-free conflict graphs where we consider a wireless broadcast medium. It is possible to formulate a scheduling problem of network coded flows as finding maximum weighted independent set (MWIS) in the conflict graph of the network. Finding MWIS of a general graph is NP-hard leading to an NP-hard complexity of scheduling. In a claw-free conflict graph, MWIS can be found in polynomial time leading to a throughput-optimal scheduling. We show that the conflict graph of certain wireless ad hoc networks are claw-free. In order to obtain claw-free conflict graphs in general networks, we suggest introducing additional conflicts (edges) while keeping the decrease in MWIS size minimal. To this end, we introduce an iterative optimization problem to decide where to introduce edges and investigate its efficient implementation. Besides, we exemplify some physical modifications to manipulate the conflict graph of a network and also propose a mixed scheduling strategy for specific networks. We conclude that claw breaking method by adding extra edges can perform nearly optimal under the necessary assumptions. This paper investigates the optimal rate allocation problem with end-to-end delay constraints in multi-hop wireless networks. We introduce Virtual Link Capacity Margin (VLCM), which is the gap between the schedulable link capacity and the maximum allowable flow rate over a link, for link delay control. We formulate the problem as a utility maximization framework with two sets of constraints: 1) capacity and schedulability constraints and 2) end-to-end delay constraints. By dual decomposition of the original optimization problem, we present a control algorithm that jointly tunes the flow rates and VLCMs, through a double-price scheme derived with regard to the constraints: the link congestion price reflecting the traffic load of a link, and the flow delay price reflecting the margin between the average packet delay and the delay requirement of a flow. We prove that the algorithm converges to a global optimum where the aggregate network utility defined over the flow rate set is maximized, while the delay constraints are satisfied. A key feature of our algorithm is it does not rely on a specific traffic model. The algorithm is implemented distributedly via joint wireless link scheduling and congestion control. Simulation results show that our algorithm outperforms heuristic rate allocation algorithms while satisfying the end-to-end delay constraints. One of the major challenges in wireless networking is how to optimize the link scheduling decisions under interference constraints. Recently, a few algorithms have been introduced to address the problem. However, solving the problem to optimality for general wireless interference models is known to be NP-hard. The research community is currently focusing on finding simpler suboptimal scheduling algorithms and on characterizing the algorithm performance. In this paper, we address the performance of a specific scheduling policy called Longest Queue First (LQF), which has gained significant recognition lately due to its simplicity and high efficiency in empirical studies. There has been a sequence of studies characterizing the guaranteed performance of the LQF schedule, culminating at the construction of the σ-local pooling concept by In this paper, we refine the notion of σ-local pooling and use the refinement to capture a larger region of guaranteed performance. Long-distance multi-hop wireless networks have been used in recent years to provide connectivity to rural areas. The salient features of such networks include TDMA channel access, nodes with multiple radios, and point-to-point long-distance wireless links established using high-gain directional antennas mounted on high towers. It has been demonstrated previously that in such network architectures, nodes can transmit concurrently on multiple radios, as well as receive concurrently on multiple radios. However, concurrent transmission on one radio, and reception on another radio causes interference. Under this scheduling constraint, given a set of source-destination demand rates, we consider the problem of satisfying the maximum fraction of each demand (also called the maximum concurrent flow problem). We give a novel joint routing and scheduling scheme for this problem, based on linear programming and graph coloring. We analyze our algorithm theoretically and prove that at least 50 of a satisfiable set of demands is satisfied by our algorithm for most practical networks (with maximum node degree at most 5). Recent advances in multi-radio multi-channel transmission technology have the potential of substantially improving the system capacity in multi-hop wireless networks. While previous work has primarily focused on the link level protocol design, in this paper we investigate the achievable performance gain, by jointly optimizing routing and scheduling in a multi-radio multichannel multi-hop network. We formulate the optimization under a deterministic model, and we seek to minimize overall system activation time in use to satisfy given end-to-end traffic demands subjected to the multi-access interference among neighboring transmissions and the radio interface constraint at each node. The exact solution to such an optimization problem is prohibitively complex due to the combinatorial complexity, particularly with the deployment of multi-radio and multi-channel. We develop a column generation based approach to solve this problem, which decomposes the original problem into sub-problems and solves them iteratively. Numerical results are given, and discussions as well as insights into the performance aspects for multi-radio multichannel deployment are provided. Since the unlicensed 60 GHz band has the extensively wide continuous spectrum and its corresponding millimeter-wave signal has high directivity gain, the 60 GHz band is a good option for the broadband wireless mesh networks. This paper focuses on link scheduling and routing over the 60 GHz multi-channel wireless mesh networks, where each mesh router has multiple radios and multiple directional antennas. We formulate a linear programming based framework, which incorporates multi-channel and multi-radio, directional antenna, and 60 GHz millimeter-wave communications, to model the network throughput of the directional antenna based 60 GHz mesh networks. Under this framework, we derive the solution to the problem of maximizing the network throughput subject to the fairness constraint and the directional-antenna based wireless channel interference constraint. Then, we design a heuristic joint link scheduling and routing scheme which aims at approximately attaining the optimal solution to the joint optimization problem under our proposed framework. We conduct extensive simulations to validate and evaluate our proposed scheme. Millimeter wave (mm-wave) frequencies provide orders of magnitude larger spectrum than current cellular allocations and allow usage of high dimensional antenna arrays for exploiting beamforming and spatial multiplexing. This paper addresses the problem of joint scheduling and radio resource allocation optimization in mm-wave heterogeneous networks where mm-wave small cells are densely deployed underlying the conventional homogeneous macro cells. Furthermore, mm-wave small cells operate in time division duplexing mode and share the same spectrum and air-interface for backhaul and access links. The scheme proposed in this paper can significantly enhance network throughput by exploiting space-division multiple access, i.e., allowing non-conflicting flows to be transmitted simultaneously. The optimization problem of maximizing network throughput is formulated as a mixed integer nonlinear programming problem. To find a practical solution, this is decomposed into three steps: concurrent transmission scheduling, time resource allocation, and power allocation. A maximum independent set based algorithm is developed for concurrent transmission scheduling to improve resource utilization efficiency with low computational complexity. Through extensive simulations, we demonstrate that the proposed algorithm achieves significant gain over benchmark schemes in terms of user throughput. Epidemic routing has been proposed as a robust transmission scheme for sparse mobile ad hoc networks. Under the assumption of no contention, epidemic routing has the minimum end-to-end delay amongst all the routing schemes proposed for such networks. The assumption of no contention was justified by arguing that since the network is sparse, there will be very few simultaneous transmissions. Some recent papers have shown through simulations that this argument is not correct and that contention cannot be ignored while analyzing the performance of routing schemes, even in sparse networks.Incorporating contention in the analysis has always been a hard problem and hence its effect has been studied mostly through simulations only. In this paper, we find analytical expressions for the delay performance of epidemic routing with contention. We include all the three main manifestations of contention, namely (i) the finite bandwidth of the link which limits the number of packets two nodes can exchange, (ii) the scheduling of transmissions between nearby nodes which is needed to avoid excessive interference, and (iii) the interference from transmissions outside the scheduling area. The accuracy of the analysis is verified via simulations. The question of providing throughput guarantees through distributed scheduling, which has remained an open problem for some time, is addressed in this paper. It is shown that a simple distributed scheduling strategy, maximal scheduling, attains a guaranteed fraction of the maximum throughput region in arbitrary wireless networks. The guaranteed fraction depends on the ldquointerference degreerdquo of the network, which is the maximum number of transmitter-receiver pairs that interfere with any given transmitter-receiver pair in the network and do not interfere with each other. Depending on the nature of communication, the transmission powers and the propagation models, the guaranteed fraction can be lower-bounded by the maximum link degrees in the underlying topology, or even by constants that are independent of the topology. The guarantees are tight in that they cannot be improved any further with maximal scheduling. The results can be generalized to end-to-end multihop sessions. Finally, enhancements to maximal scheduling that can guarantee fairness of rate allocation among different sessions, are discussed. This paper considers the problem of determining the achievable rates in multi-hop wireless networks. We consider the problem of jointly routing the flows and scheduling transmissions to achieve a given rate vector. We develop tight necessary and sufficient conditions for the achievability of the rate vector. We develop efficient and easy to implement Fully Polynomial Time Approximation Schemes for solving the routing problem. The scheduling problem is a solved as a graph edge-coloring problem. We show that this approach guarantees that the solution obtained is within 67 of the optimal solution in the worst case and, in practice, is typically within about 80 of the optimal solution. The approach that we use is quite flexible and is a promising method to handle more sophisticated interference conditions, multiple channels, multiple antennas, and routing with diversity requirements. A comprehensive study of the problem of scheduling broadcast transmissions in a multihop, mobile packet radio network is provided that is based on throughput optimization subject to freedom from interference. It is shown that the problem is NP complete. A centralized algorithm that runs in polynomial time and results in efficient (maximal) schedules is proposed. A distributed algorithm that achieves the same schedules is then proposed. The algorithm results in a maximal broadcasting zone in every slot. > Abstract— We consider wireless networks with interference constraints. The network consists of a set of links and a set of users who generate packets that traverse these links. Each user is associated with a route consisting of a sequence of links. The links are subject to the usual interference constraints: (i) if link l interferes with link k, then link k also interferes with link l, and (ii) two links that interfere with each other cannot transmit simultaneously. The interference set of a link is defined to be the set of links that interfere with the link, along with the link itself. A greedy scheduler is one which selects an arbitrary set of links to transmit subject only to the interference constraint. We use a traffic regulator at each link along the route of each flow which shapes the traffic of the flow. We prove that the network is queue-length stable under any maximal greedy scheduling policy provided that the total arrival rate in the interference set of each link is less than one.