New version page

Sufficient Rate Constraints for QoS Flows in Ad-Hoc Networks

Upgrade to remove ads

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

Sufficient Rate Constraints for QoS Flows in Ad-Hoc NetworksRajarshi Gupta, John Musacchio and Jean WalrandUniversity of California, Berkeley{guptar, musacchj,wlr}@eecs.berkeley.edu∗AbstractThe capacity of an arbitrary ad-hoc network is difficult toestimate due to interference between the links. We use aconflict graph that models this interference relationship todetermine if a set of flow rates can be accommodated. Us-ing the cliques (complete subgraphs) of the conflict graph,we derive constraints that are sufficient for a set of flowrates to be feasible, yet are guaranteed to be within a con-stant bound of the optimal. We also compute an alter-nate set of sufficient constraints that can be easily derivedfrom the rows of the matrix representation of the conflictgraph. These two sets of constraints are particularly use-ful because their construction and verification may be dis-tributed across the nodes of a network. We also extend thead-hoc network model to incorporate variations in the in-terference range, and obstructions in the network.Keywords: Ad-Hoc Networks, Graph Theory, QoS1 IntroductionDetermining the capacity of an arbitrary ad-hoc networkis difficult because neighboring links using the same chan-nel interfere, and the interference relationships betweenall of the links in a network can be quite complex.Several researchers interested in the capacity of ad-hoc networks have modelled the ad-hoc network usingrandomized models, and evaluated asymptotic bounds onthe capacity. Other work has addressed the question ofwhether a given flow vector is feasible on a particular ad-hoc network, where “feasible” means that a global sched-uler with access to all the information in the network∗This work was supported by the Defense Advanced ResearchProject Agency under Grant N66001-00-C-8062.could find a link scheduling policy that would achieve thedesired rates. In this work, we are also interested in meth-ods for determining whether a flow vector is feasible, butwe are particularly interested in methods that are suitablefor distributed control in an ad-hoc network.As in [1] and [2], we make use of a “conflict graph”that models the interference relationships between the dif-ferent links of a network. Every link in the connectivitygraph G = (V, E) is represented by a node in the conflictgraph CG = (VC, EC). Two nodes in CG are connectedby an edge if the nodes correspond to links in G that in-terfere. In Fig. 1, we show an example of a connectivitygraph in which the interference between links is markedusing dotted lines. The corresponding conflict graph isshown on the right. The authors of [1, 2] show that a setof necessary and sufficient conditions to whether a set offlows is feasible is found by a computationally expensiveprocess of finding all of the independent sets of the con-flict graph, and then writing constraints in terms of theindependent sets. (We review the details of the “indepen-dent set” method, as we call it, in Sec. 2.2.)Because the independent set constraints are computa-tionally expensive and require global information, theyare not suitable to be used in a distributed scheme. Wetherefore look to find a different set of conditions that canbe computed in a distributed way and that are at least suf-ficient, though perhaps not necessary, for a flow vector tobe feasible.One such set of constraints we refer to are the “row”constraints, because they are derived by using the rowsof the matrix representation of the conflict graph. Whilethey are sufficient conditions that are relatively easy tocompute, they are much more restrictive than is necessaryin many cases.This motivates us to develop a different set of sufficient123145ACBEDinterferenceECDBAConnectivity Graph Conflict GraphFigure 1: Example of a connectivity graph with its conflictgraphconditions using cliques (complete subgraphs) of the con-flict graph. While previous work [2] has used cliquesto find necessary conditions for a set of flow rates to befeasible, we find sufficient conditions. We refer to oursufficient clique constraints as “scaled” clique constraintsbecause they are constructed by modifying the necessaryclique constraints by a constant scaling factor. Unlike therow constraints, the scaled clique constraints are within aconstant bounded factor of being necessary; a factor thatis independent of the structure of the network, or the flowson it.One potential drawback of a scheme based on cliquesis that the number of cliques in a graph can grow expo-nentially with the number of nodes. However, we discussa technique for identifying approximate cliques that canbe implemented distributedly, and that grows only poly-nomially with the number of nodes. We discuss how thesufficiency of the clique constraints is maintained whenusing this approximation.At first, we model the nodes having a constant inter-ference range, and utilize the resulting unit disk structure(defined in Sec. 4.4) of the graph. However, to considermore realistic ad-hoc network scenarios, we augment thenetwork model to allow for variances in the interferencerange, and evaluate its effect on the scaling factor. Wealso incorporate obstructions in the network, and extendthe proof of sufficiency to include this.Finally, we attempt to validate our theoreticalconstraint-based approach by simulating various ad-hocnetworks, and comparing the achieved rates in the sim-ulation to the theoretical limits predicted by our model.The results are encouraging at first sight, as the networksappear to satisfy our constraint-based approach. However,a deeper study reveals that in some cases, large inefficien-cies in the underlying MAC protocol may be the primarycause for the limited throughput achieved; our constraintsare satisfied as a corollary of this effect. We concludethat the constraint-based framework presented here be-comes universally practicable only when used in conjunc-tion with an efficient MAC protocol.This paper does not try to present a new architectureto achieve QoS in ad-hoc networks. What we proposeis a theoretical framework that allows us to answer ques-tions about the feasibility of a specific set of flows on anarbitrary ad-hoc network. However, this framework mayindeed be used as tools to develop new and improved pro-tocols for QoS routing in ad-hoc networks, as we discussin Sec. 9.The rest of the paper is organized as follows. In Sec. 2,we describe the related work in the


Download Sufficient Rate Constraints for QoS Flows in Ad-Hoc Networks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Sufficient Rate Constraints for QoS Flows in Ad-Hoc Networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Sufficient Rate Constraints for QoS Flows in Ad-Hoc Networks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?