Distributed Congestion Control Algorithm Strategy To Avoid Congestion in Wireless Ad Hoc Network

Distributed Congestion Control Algorithm Strategy To Avoid Congestion in Wireless Ad Hoc Network

Mrs. Mrunalini Gavfale Mrs. Sandhya Tanpure Prof. Manoj M. Dongre

Department of EXTC Department of EXTC Department of EXTC

R. A. I. T.,

R. A. I. T

1. A. I. T

   Nerul,Navi Mumbai. Nerul,Navi Mumbai Nerul,Navi Mumbai

   Abstract—A wireless ad hoc network is a collection of wireless nodes that can dynamically self-organize into an arbitrary and temporary topology to form a network without necessarily using any pre-existing infrastructure. Congestion control is a key problem in ad-hoc networks. Network congestion has a severe impact on the throughput, routing and lifespan, etc. of a network. This paper, starting from the traffic flow of a wireless Ad Hoc network, put forwards the congestion control model and the neighboring links. Based on this model, it also raises congestion and the optimization algorithm CCAD. CCAD, with the end-to-end traffic flow as its study object and adopting rate-based end-to-end congestion control strategy, tried to avoid congestion in links and network. A congestion control mechanism is adopted at the nodes,links by calculating utility of links and complete path over multiple iterations by using CCAD algorithm and hence the routing congestion control is also completed there. The simulated experiment result shows that the proposed congestion control model and algorithm fit in with the properties of Ad Hoc network and can rapidly respond to the network congestion changes so that it can stabilize the flow rate and make the congestion avoided.

   Keywords: Wireless Ad Hoc Network, congestion control, CCAD, utility.

   1. INTRODUCTION

Wireless Ad Hoc network, with shared wireless channel to transmit messages, faces complicated wireless transmission environment, which will bring in a series of new problems, especially with routing, congestion being one of the problems. Generally speaking, for wireless Ad Hoc network, the calculation of the congestion control of one certain link should not just be based on the congestion of the link itself, instead, it should respond according to the general congestion message that interrupts the link. Therefore, to solve the routing congestion which might come up with the Ad Hoc network, the following issues should be taken into consideration: the intrinsic properties of wireless multiple-hop links; the time varying of network topology;dynamic end users. Most of the present congestion control schemes under modern

control theory adopt rate-based closed-loop control. CHING[1] put forwards the joint optimization algorithm of TCP and power control according to the power changes in the physical layer. CHEN.L.[2] put forwards the joint optimization algorithm of congestion control and MAC. However, wireless multiple-hop linkage, the intrinsic properties of wireless Ad Hoc network, is not considered in the above mentioned algorithms. Though it is improved in the document [3], there is still insufficient consideration for the mobility of the nodes and the time-varying of topology. One of the important properties of Ad Hoc network is the changes of the parameters and the topology structure, which is unpredictable and has non-ignorable impact. According to the intrinsic property of wireless multiple-hop link, for complicated system with dynamic end users, the time varying topology, from the view of modern control theory, would prefer an optimization mechanism of predictive control theory [4, 5]. With consideration of wireless Ad Hoc network bandwidth resources distribution and node behavior characteristics, a relevant model is established to reflect by the price signals whether the resources are free or busy. Then with the most economical resources to implement the task, the balance between supply and demand and congestion control in the entire system are realized. Based on the above procedure, a related resolution mechanism is put forward to achieve effective utilization of bandwidth resources and control of congestion.

1. Game Theory-Based Congestion Control Model

   It is a popular in recent year to solve the resources distribution, flow control and load balancing problems of distributed system through economics-based approach. However, the present research mostly focuses on the wired network environment [6]. Even some are situated in wireless packet network, they are confined to wireless local area network and single-hop network [7].

2. Link Resources Price-bidding Game Model

   Suppose there are N nodes (or links) in the wireless Ad Hoc network competing for network resources, there is a performance function fi and an expected initial performance, supposed as 0 for convenience sake, for every user i (i[1,…,N]) . The definition of every performance function is within a subset RN, called set X and is the strategy combination of the game for N users. With regard to the distribution of network link resources, X is represented by the vector space of link distribution rate of users. Problems simplified, the nodes can be spontaneously renewed according to the actual situation. According to game theory [8], if every function fi (iN) is injective within X, the set of trading solutions will be exclusive. Therefore, there is an exclusive trading solution of Nash Equilibrium within space X.

3. The Transfer of Pricing Game Problems

   Lemma 1 Suppose mapping g: X R1* is concave, h = ln(g( )) : R1 R will be concave. Moreover, if g is injective, h will be a strictly concave mapping. Based on Lemma 1, the link resources price game problem can be transferred into the optimal equivalent problem [8].

   The formalized description of the problem of game theory- based congestion is as follows:

   t [ti, ti + ti],i =1,2,……..

   ( ti is the time period which is as short as possible).Suppose the network parameters and structure of Ad Hoc network within t remain unchanged, the following conclusion is valid within this time period. For account convenience, the time symbol t of all the time variable

   fairness [6]. According to the above analysis, the aim of the problem of congestion control is to maximize the overall utility of all the source ends. i.e.

   max ln( xs ) s S

   xs here refers to the transmission rate of source end s .In the form, xs objective function of the divided time span of control congestion, the overall utility of all the maximized source ends. The other two formulas are the restraint conditions of the problem: formula (b) certifies that the cumulative rate of the information transmission flow of all the wireless links with the interference set is no bigger than the channel capacity Ce so as to avoid congestion, and formula © restrains the maximum sending rate Ms of the nodes. The constant Ms > 0 means that the maximum sending rate of the nodes depends on the actual network environment.

1. DISTRIBUTED CONGESTION CONTROL ALGORITHM-CCAD

Since wireless Ad Hoc network does not have a central controller, to solve the above mentioned divided time span problem of wireless Ad Hoc network congestion control, duality-based distributed congestion control Lagrange duality-based distributed congestion control algorithm CCAD is put forward here. The fundamental idea of the algorithm is to build a link interference set- based pricing game frame and measure the link congestion with the total price of the link interference set. Through the pricing game mechanism, a solution to the problem of divided time span for congestion control can be worked out by adopting correponding price coordination algorithm put forward by using Lagrange duality. For this, a multiplier vector P is brought in, formula:

parameters is omitted in the coming text. Suppose the wireless Ad Hoc network model is(V,E) , the endpoint V is called set of nodes while the side E is called the set of links. The transmission capacity of wireless link e is Ce. S

L(,

P)= –

= – )

= {1, 2, s} is the information flow set of shared network resources (every piece of information flow-related information has been got through routing).Information flow sS is composed of source node s, receiving terminal t, certain number of intermediate nodes and wireless links. If a information flow s S starts from source node s and arrives at the target after wireless link set E(s) E, it is called an end-to-end multiple-hop information flow, and the its transmission on certain wireless link is called information sub-flow. S(e)={s Se E(s)} is an information sub-flow set passing wireless link e . Each source end has a corresponding monotone increasing, strictly concave, second-order continuous, differentiable and utility function Us (xs ) , xs being the transmission rate of the source end s .The utility function in this paper is U(x) = ln xs , which is a logarithmic utility function and xs will be a monotonic increasing function accordingly and the second derivative is smaller than 0, that is to say, the marginal utility decreases progressively. Therefore, it can satisfy the demand of elastic working and achieve overall

In formula (3), pe is the Lagrange multiplication factor

of the original solving problem as well as the implicit cost related to link e , which is called shadow price in economics. It denotes the marginal cost of the unit rate of flow s when it goes through link e and is called link shadow price. The shadow price pe has a double function: it provides basis for detecting network cost consumption for increasing capacity of any given network capacity; it also determines the value when the network capacity changes by changing into congestion and working as the signal of network capacity expansion means that the bandwidth cost of flow s when it is transmitted at a rate of xs . ps is the overall price that s costs in its using of all links, that is,the overall path congestion price.

Suppose in formula (3) is

B , Ps) )- Ps

presents the gains of source end sending flow s (the difference between the utility gained and the cost

paid).Therefore, the optimization is to adjust the flow rate to the optimal value with the maximization of each source ends own gains B as the objective then,

(P) = ln-1(ps) =min {max {ln-1(jE(s) eISj pe), 0}

MS} (5)

According to formula (5), the optimal objective will be achieved through distributed algorithm to make the algorithm localized, which will greatly reduce the complexity of algorithm and the communication cost, only if the source end gets ps , the path price of the sending flow in formula (4) .Now to find the solution Pe to the duality problem through gradient project algorithm [10], the adjustment direction of the link shadow price in negative gradient direction of objective function.

Pe(k+1)=max{0,Pe(k)-d(p(k)} pe(k+1)=max{0,pe(k)-(Ce-jE(s)eISjxs(k))} (6)

Here, k is the time of the iteration; is the step length,and P(k) is the shadow price of No. k iteration.

Suppose CIe (k) is the congestion signal of link e in no. k

iteration, the following formula will be adopted:

p e(k+1)= max{0, pe (k)-(Ce – jE(s) eISj xs(k))}

1. Utility calculated as,

   US=maxln(xs)

2. Then the above procedure repeats.

1. SIMULATION AND ANALYSIS

   The performance of routing congestion control algorithm will be studied next, the performance and response time of CCAD solution being the main focus. The network model is shown in fig.1

   There are 30 nodes distributed at random in a plane of [0,1]×[0,1], and suppose direct communication can happen to any two nodes who are less than 0.25 away from each other. The interference set of link e is composed of the links.

   CIe(k)=

   0 0

   1 others (7)

   Fig 1. The Ad Hoc network

   From the above two formulas, we can see that the supply and demand of bandwidth is implied in duality gradient project algorithm.

   The algorithm of CCAD can be described as follows:

   1. For the rate of flow s of the starting node s,choose proper xs.

   2. The initial link price pe of the link e and the congestion and the congestion signaling information CIe.

   3. Node s and wireless link e aquire rate and congestion signaling information from all the links of wireless link interference set.

   4. In cycle k, source end s works out new sending flow according to,

      xs(P)= ln-1(ps)=min{max{ln-1(jE(s)eISjpe),0} MS}

   5. Flow s sends updated rate information to all competing flows following the sending path during the one hop.

   6. Before going to next cycle algorithm updated link congestion price pe for each link e by equation

   There are three substates in the network shown in figure 1.Each having four message flows (S1,S2,S3,S4) marked respectively as Red,Blue,Yellow,Green colors. Here the CCAD algorithm calculated the utility values for each message flow. Analysis of the algorithm is done over utility values of three substates for 20 iterations.

   Table 1: Utility of three substates at 20th iteration

   		flow 1	flow 2	flow 3	flow 4
   Utility	Substate 1	5.63	5.74	5.66	5.7
   Utility	Substate 2	5.7	5.94	5.88	5.97
   Utility	Substate 3	6.15	6.31	6.22	6.47

   Table 2: Average Total Utility

   		Iteration 20
   Substate 1	Average Total Utility	22.39
   Substate 2	Average Total Utility	23.27
   Substate 3	Average Total Utility	22.38

   The utility for the three substates are shown in Table I These values are calculated for 20 iterations. As shown from the table as iterations are increased up to 20, utility of the links increases. From Table III, average total utility of

   20 iterations. This show the increased variations in the utility values when iterations are increased. Hence to minimize the congestion in the ad hoc networks iterations for calculating utility values are increased.

   From the above calculations it can be easier to decide to change the data transmission path or route on the links which are having highest utility. In this paper, links are having more congestions are analyzed on the basis of link price transmission rate and utility is calculated using the CCAD algorithm, and the corresponding route is diverted on the link having highest utility.

   Graph shows variations in utility of 20

   Substate 1: 20 Iterations

   Substate 2: 20 Iterations

   Substate 3: 20 Iterations

   Fig 2: Graphs of three substates for 20 iterations

2. CONCLUSION

In this paper, distributed congestion control approach is applied for the wireless ad-hoc network. Using the approach, utility of the any network can be increase efficiently.

CCAD algorithm helps in finding exact utility of the network on the basis of link price of the network. Therefore, the solution of this congestion control algorithm shall meet the expectation and its spontaneous respond to the dynamic changes of the network is satisfactory, which can keep the conestion under control so as to improve the network function.

REFERENCES

1. BAO Xiao-an,XU Wei-qiang,WU Tie-jun, Optimal Congestion Control Algorithm for Ad hoc Networks, Journal of University of Electronic Science and Technology of China, 2005,vol.36(2),pp. 250- 253(In Chinese).

2. Rawlings JB, Tutorial overview of model predictive control. IEEE Control Systems Magazine, 2000, vol.20 (3), pp.38-52.

3. Xu WQ, Wu TJ, Wang YM, Zhang YH, Chen JM, Adaptive congestion control strategy for multirate multicast sessions in ad hoc networks. Journal of Software, 2008, vol.19 (3), pp.769-778(In Chinese).

4. F.Kelly, A.Maulloo, and D.Tan.Rate control in communication networks: Shadow Prices, Proportional fairness and stability. Journal of the Operational Research Society, 1998, 49(3):237-252.

5. Y.Qiu, P.Marbach. Bandwidth Allocation in Ad-Hoc Networks: A Price-Based approach, Proc.of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM, 2003), March.2003, pp.111-117.

6. ZANGE Li,ZOU Jin,A Wireless Ad Hoc Network Congestion Control Algorithm based on Game Theory Inernational conference on Fuure Computer Science and application, Published in 2011 IEEE.

[7]T.Alpcan and T.Baser, A game theoretic approach to decision and analysis in network intrusion detection,îinProc. Of the 42nd IEEE Conference on Decision and Control, Maui, HI, December 2003

1. R.Gibbons, Game Theory for Applied Economics, New Jersey: Princeton University Press, 1992.

2. Chen Baolin, The optimization theory and algorithms, "Beijing: Tsinghua University Press, 1998(In Chinese).

3. D P Bertsekas, J N Tsitsiklis, Parallel and distributed computation, New Jersey: Prentice -Hall, 1989.

[11]H. Yaiche, R. R. Mazumdar, and C. Rosenberg, A game theoretic framework for bandwidth allocation and pricing in broadband networks, IEEE/ACM Transactions on Networking, vol. 8,pp. 667 678, October 2000.

[12]K.-WLye and J.Wing, ìGame strategies in network security, î in Foundations of Computer Security WOrkshop in FLoC02, Copen- hagen, Denmark, July 2002