Computer Engineering and Intelligent Systems ISSN 2222-1719 (Paper) ISSN 2222-2863 (Online) Vol 2, No.

4, 2011

www.iiste.org

Congestion Control for Wireless Ad-Hoc Networks

Kartheek Kumar Reddy Department of CSE, VITS-SET, Karimnagar,JNTUH,Hyderabad, AP, INDIA kartheek.aedavelli@gmail.com Rajmohmmad Department of CSE, VITS-SET, Karimnagar,JNTUH,Hyderabad, AP, INDIA raaz.mohd@gmail.com Abstract We study joint design of end-to-end congestion control and Per-link medium access control (MAC) in ad-hoc networks. In the current scenario wireless communication is emerging the world. Wireless Ad Hoc networks demands for higher intermediate node supports for long-range communication. Wireless Ad Hoc network is an emerging communication approach. Ad Hoc networks are usually defined as an autonomous system of nodes connected by wireless links and communicating in a multi-hop fashion. The wireless ad-hoc networks are for easy of deployment without centralized administration or fixed infrastructure, to achieve the goal of less interference communication. In wireless Ad-hoc network the connections between the wireless links are not fixed but dependent on channel conditions as well as the specific medium access control (MAC). The channel medium and transmission links are affected by the interference, delay, and buffer overflow these may cause the network congestion. To avoid network congestion various congestion control methods were developed in past but they were performed less control of end-to-end congestion and less in per link connection control. To overcome the above problems and to improve the resource allocation an efficient method has to be developed. Keywords: Ad-hoc networks, random access, wireless networks, congestion control 1. INTRODUCTION AD-HOC wireless networks are usually defined as an autonomous system of nodes connected by wireless links and communicating in a multi-hop fashion. The benefits of ad-hoc networks are ease of deployment thereby enabling an inexpensive way to achieve the goal of ubiquitous communications. One of the fundamental tasks that an ad hoc network should often perform is congestion control. Congestion control is the mechanism by which the network bandwidth is distributed across multiple end-to-end connections. Its main objective is to limit the delay and buffer overflow caused by network congestion and provide tradeoffs between efficient and fair resource allocation. Congestion is an unwanted situation and is disastrous for a data transmission system as it manifests itself as depletion of resources that are critical to the operation of the system. These resources can be CPU, buffer space, bandwidth etc.. congestion control makes sure that the system is running at its rated capacity, even with the worst case overload situations. Doing this enables optimal usage of resources for all the nodes in the system with a measurable quality-of- service (QOS). In ad hoc wireless networks the link capacities are elastic. Most routing schemes for ad hoc networks select paths that minimize hop count, but it leads to congestion at some region, while other regions are not fully utilized. To use the wireless spectrum more efficiently, multiple paths based on the pattern of traffic demand and interference among links should be considered. Wireless channel is a shared medium and interference limited. Link is only a logical concept and links are correlated due to the interference with each other. In wireless network flows can compete even if they dont share a wireless link in their paths. Thus, in ad hoc wireless networks the contention relations between link-layer flows provide fundamental constraints for resource allocation. In wireless networks the joint design of congestion and media access control is naturally formulated using the network utility maximization framework considering the new constraints that arise from channel contention. In wire line networks with fixed capacities, congestion control is implemented at the transport layer and is often designed separately from functions of other layers. Useful mathematical models and tools based on convex optimization and control theory have been developed, which cast congestion control algorithms as decentralized primal-dual schemes to solve network utility maximization problems.

55

Computer Engineering and Intelligent Systems ISSN 2222-1719 (Paper) ISSN 2222-2863 (Online) Vol 2, No.4, 2011

www.iiste.org

In the NUM framework, each end-user (or source) has its utility function and link bandwidths are allocated so that network utility (i.e., the sum of all users utilities) is maximized. A utility function can be interpreted as the level of satisfaction attained by a user as a function of resource allocation. Efficiency of resource allocation algorithms can thus be measured by the achieved network utility. 2. MODELING AND PRELIMINARIES We consider an ad hoc wireless network represented by an undirected graph G = (N,L), where N is the set of nodes and L is the set of logical links. Each source node s has its utility function Us(xs), which is a function of its transmitting data rate xs[0,) and we assume it is continuously differentiable, increasing, and strictly concave. For its communication, each source uses a subset L(s) of links. Let Lout(n) denote the set of outgoing links from node n, and Lin(n) the set of incoming links to node n. We define S as the set of all sources and S(l) as the subset of sources that are traversing link l. We assume static topology (the nodes are in a fixed position). Also, each link has finite capacity cl when it is active, i.e. we implicitly assume that the wireless channel is fixed or some underlying mechanism masks the channel variation. Wireless transmissions are interference-limited. All links transmit at rate cl for the duration they hold the channel. Assume that each node cannot transmit or receive simultaneously, and can transmit to or receive from at most one adjacent node at a time. Since each node has a limited transmission range, contention among links for the shared medium is location-dependent. Spatial reuse is possible only when links are sufficiently far apart. Define two types of sets, LI (n) and NI (l), to capture the location dependent contention relations, where LI (n) is the set of links whose receptions are affected adversely by the transmission of node n, excluding outgoing links from node n, and NI (l) is the set of nodes whose transmission fail the reception of link l, excluding the transmit node of link l. Also note that lLI(n) if and only if nNI(l). Time is slotted in intervals of equal unit length and the i-th slot refers to the time interval [i, i + 1), where i = 0, 1. . . i.e., transmission attempts of each node occur at discrete time instances i. In this a MAC protocol is developed based on random access with probabilistic (re-)transmissions. At the beginning of a slot, each node n transmits data with probability qn. When it determines to transmit data, it selects one of its outgoing links lLout(n) with probability pl/qn, where pl is the link persistence probability;

(1)Where link throughputs given p and q, since the term is the probability that a packet is transmitted over link l and successfully received by its receiver. The problem formulation in (1) entails congestion control at the network layer (finding x), and contention control at the MAC layer (finding p and q). The two layers are coupled through the first constraint in (1), which asserts that for each link l, the aggregate source rate does not exceed the link throughput. The transport layer source rates and the MAC layer transmission probabilities should be jointly optimized to maximize the aggregate source utility. Due to the first constraint, (1) is in general a non-convex and non-separable problem, which is difficult to optimize over both x and p, q in a distributed way directly. Under certain conditions, it can be transformed into a convex one by taking the logarithm on both sides of the first constraint and replacing the rate variables by their logarithmic counterparts, i.e., Zs = log(xs). This yields a new constraint

although it is a convex function.

56

Computer Engineering and Intelligent Systems ISSN 2222-1719 (Paper) ISSN 2222-2863 (Online) Vol 2, No.4, 2011

www.iiste.org

We introduce a set of new variable (3) where each ls can be interpreted as the fraction of the overall traffic on link l contributed by source s

(4) Lemma 1: If gs(xs) < 0, then Us (Zs) is a strictly concave function of Zs.

(5) Given that the condition of Lemma 1 is satisfied, problem (4) is indeed a convex problem, and all log rates are decoupled, enabling the dual decomposition. To proceed, we apply duality theory and associate Lagrange multipliers. Let us define the Lagrangian function

And the dual problem to (4) is D: minD().

(8)

The maximization in (7) for a given can be decomposed into three sub problems: One at each source and the other two at each node. The source sub problem is (9) If we interpret the Lagrange multiplier ls as the price per unit of log bandwidth charged by link l to source s, then the source strategy is to maximize its net benefit Us (Zs) s Zs, since s zs is just the sum bandwidth cost charged by all links on its path if source s transmits at log rate zs. Since Us (Zs) is strictly concave over Zs, a unique maximize exists.

57

Computer Engineering and Intelligent Systems ISSN 2222-1719 (Paper) ISSN 2222-2863 (Online) Vol 2, No.4, 2011

www.iiste.org

The other two subproblems at each node n for every outgoing link l Lout(n) are, respectively

Proposition 2: Given , the () solving problem (10) is (for node n and link l Lout(n))

Now we are ready to solve the dual problem (8) using a projected sub gradient method. At each node n for Lout(n) and S(l), the outgoing link prices for sources involved are adjusted as follows

Where [a]+ := max{0, a} and (t) > 0 is a step size. + denotes the projection onto the set + of non-negative real numbers. According to Dan skins theorem, we have

Substituting (16) into (15), we obtain the following adjustment rule for link l Lout(n) at each node n

3. ALGORITHM 1) Create a random network. 2) After creating a network, the distance between each node to all other nodes are found by using Euclidean distance method.

58

Computer Engineering and Intelligent Systems ISSN 2222-1719 (Paper) ISSN 2222-2863 (Online) Vol 2, No.4, 2011

www.iiste.org

d=sqrt ((x1-x2) ^2+(y1-y2)^2) 3) Find the neighbor list of each node is used. 4) The neighboring list in order to find the path between each source and destination using DSR routing protocol is implement. 5) Checks for the best optimal path from the various paths obtained in the evaluation of route. Algorithm at source s 6) Receives from the network the sum 7) Computes the new log rate using 8) Communicates the new log rate Zs(t + 1) to all links Algorithm at Node n: 9) Receives log rates Zs(t) from all sources s that go through the outgoing links of node n 10) Receives prices from the neighboring nodes n where 11) Calculates according to Proposition 2; 12) Computes new prices ls(t + 1) = [ls(t) + (t)(Zs((t))logcl log ls((t)) log pl ((t)) NI(l)log(1 qk((t)))]+. For each outgoing link communicates new Prices to all sources s S(l) that use link l and to all nodes in For the convergence and optimality of this distributed algorithm, have the following result. If the following condition is satisfied at the optimal dual solution * on ss path. of link prices in ss path;

And * denotes a minimize of the dual problem (8), then step sizes

exist to guarantee

The evolution of link persistence probabilities and link throughputs.

The joint control algorithm can be implemented as follows. Each link l (or its transmission node tl) updates its persistence probability pl(t), and concurrently, each source updates its data rate xs(t).To calculate the sub gradient in (6), each link needs information only from link k, kLI , i.e., from links whose transmissions are interfered from the transmission of link l, and those links are in the neighborhood of link l. To calculate the sub gradient in (7), each source needs information only from link l, lL(s), i.e., from links on its routing path. Hence, to perform the

59

Computer Engineering and Intelligent Systems ISSN 2222-1719 (Paper) ISSN 2222-2863 (Online) Vol 2, No.4, 2011

www.iiste.org

algorithm, each source and link need only local information through limited message passing and the algorithm can be implemented in a distributed way. At the transmitter node of each link to update the persistence probability of that link, and does not need to be passed among the nodes. There is no need to explicitly pass around the values of persistence probabilities

4. Conclusion We studied the joint design of congestion and contention control for wireless ad hoc networks. While the original problem is non-convex and coupled, provided a decoupled and dual-decomposable convex formulation, based on which sub gradient-based cross-layer algorithms were derived to solve the dual problem in a distributed fashion for non-logarithmic utilities. These algorithms decompose vertically in two layers, the network layer where sources adjust their end-to-end rates, and the MAC layer where links update persistence probabilities. These two layers interact and are coordinated through link prices. We used random network topology in wireless ad hoc network. 5. References Yingqun Y, and Georgios B. Giannakis, Cross-Layer Congestion and Contention Control for Wireless Ad Hoc Networks. S. Boyd and L. Vandenberghe, Convex Optimization. New York: Cambridge University Press, 2003. L. Bui, A. Eryilmaz, R. Srikant, and X. Wu, Joint asynchronous congestion control and distributed scheduling for multi-hop wireless networks, . L. Chen, S. H. Low, M. Chiang, and J. C. Doyle, Jointly optimal congestion control, routing, and scheduling for wireless ad hoc networks, . L. Chen, S. H. Low, and J. C. Doyle, Joint congestion control and media access control design for ad hoc wireless networks, in Proc. IEEE INFOCOM, Mar. 2005. X. Lin and N. B. Shroff, Joint rate control and scheduling in multi-hop wireless networks. S. H. Low and D. E. Lapsley, Optimization flow control, I: Basic algorithm and convergence, IEEE/ACM Trans. Networking, vol. 7,no. 6, pp. 861874, Dec. 1999. N. Z. Shor, Minimization Methods for Non-Differentiable Functions. NewYork:Springer-Verlag, 1985. R. Srikant, The Mathematics of Internet Congestion Control. Berlin: Birkhauser, 2004. X. Wang and K. Kar, Cross-layer rate control for end-to-end proportional fairness in wireless networks with random access, in Proc. ACM Mobie Ad-Hoc,

60