 Open Access
 Total Downloads : 380
 Authors : Mr.D.Anantha Reddy, Mr.T.P.Shekhar, Mr.V.Chakradhar, Mr.M.Chalapathi Rao
 Paper ID : IJERTV1IS7267
 Volume & Issue : Volume 01, Issue 07 (September 2012)
 Published (First Online): 25092012
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Improving throughput in MultiHop Wireless Networks Using Greedy Partitioning Alogrithm
Mr.D.ANANTHA REDDY Mr.T.P.SHEKHAR Mr.V.CHAKRADHAR Mr.M.CHALAPATHI RAO
Student, M.Tech(CS) Assoc. Prof Student, M.Tech(CSE) Assoc. Prof. SCCE, KNR SCCE,KNR VCE2 KNR VCE2 KNR
1 Sree Chaitanya College Of Engineering
2. Vaageswari College Of Engineering
ABSTRACT
In multicast networks we can distribute the data packet of information to several systems instead of having to send that packet once for every destination. By this 5, 10, or 100 machines can receive the same packet, bandwidth is conserved. Also, when you use multicasting to send a packet, you don't need to know the address of everyone who wants to receive the multicast; instead, you simply "broadcast" it for anyone who is interested.
We mainly focuses on delay performance of a multihop wireless network in which the routes between sourcedestination pairs are fixed. We develop a new queue grouping technique to handle the complex correlations of the service process resulting from the multihop nature of the flows and their mutual sharing of the wireless medium. We present the system called clique is a special wireless system. The lower bound analysis provides useful insights into the design and analysis of optimal or nearly optimal scheduling policies.

802.11n is an addition to the 802.11 family of standards. The goal of 802.11n is to increase wireless local area network (WLAN) speed A smart antenna is a digital wireless communications antenna system that takes advantage of diversity effect at the source

Long Term Evolution (LTE) is a 4G wireless broadband technology developed by the Third Generation Partnership Project (3GPP)

SISO (single input, single output) refers to a wireless communications system in which one antenna is used at the source

MISO (multiple input, single output) is an antenna technology for wireless communications in which multiple antennas are used
SIMO (single input, multiple output) is an antenna technology for wireless communications in which multiple antennas are used
Multicast is communication between a single sender and multiple receivers on a network. Typical uses include the updating of mobile personnel from a home office and the periodic issuance of online newsletters. Together with anycast and unicast, multicast is one of the packet types in the Internet Protocol Version 6 (IPv6).
Multicast is supported through wireless data networks as part of the Cellular Digital Packet Data (CDPD) technology.
Multicast is also used for programming on the MBone, a system that allows users at highbandwidth points on the Internet to receive live video and sound programming. In addition to using a specific high bandwidth subset of the Internet, Mbone multicast also uses a protocol that allows signals to be encapsulated as TCP/IPpacket when passing through parts of the Internet that cannot handle the multicast protocol directly.
A large number of studies on multihop wireless networks have been devoted to system stability while maximizing metrics like throughput or utility. These metrics measure the performance of a system over a long timescale. For a large class of applications such as video or voice over IP, embedded network control and for system design; metrics like delay are of prime importance. The delay performance of wireless networks, however, has largely
been an open problem. This problem is notoriously difficult even in the context of wireline networks, primarily because of the complex interactions in the network (e.g., superposition, routing, departure, etc.) that make its analysis amenable only in very special cases like the product form networks.
The problem is further exacerbated by the mutual interference inherent in wireless networks which, complicates both the scheduling mechanisms and their analysis. Some novel analytical techniques to compute useful lower bound and delay estimates for wireless networks with singlehop traffic were developed in. However, the analysis is not directly applicable to multihop wireless network with multihop flows, due to the difficulty in characterizing the departure process at intermediate links.
The metric ofinterest in this paper is the systemwide average delay of a packet from the source to its corresponding destination. We present a new, systematic methodology to obtain a fundamental lower bound on the average packet delay in the system under any scheduling policy. Furthermore, we re engineer well known scheduling policies to achieve good delay performance vizaviz the lower bound.
We analyze a multihop wireless network with multiple sourcedestination pairs, given routing and traffic information. Each source injects packets in the network, which traverses through the network until it reaches the destination. For example, a
multihop wireless network with three flows is shown in Fig. 1. The exogenous arrival processes AI (t), AII (t) and AIII (t) correspond to the number of packets injected in the system at time t. A packet is queued at each node in its path where it waits for an opportunity to be transmitted. Since the transmission medium is shared, concurrent transmissions can interfere with each others transmissions. The set of links that do not cause interference with each other can be scheduled simultaneously, and we call them activation vectors (matchings). We do not impose any a priori restriction on the set of allowed activation vectors, i.e., they can characterize any combinatorial interference model. For example, in a Khop interference model, the links scheduled simultaneously are separated by at least K hops. In the example show in Fig. 1, each link has unit capacity; i.e., at most one packet can be transmitted in a slot. For the above example, we assume a 1hop interference model.
The delay performance of any scheduling policy is primarily limited by the interference, which causes many bottlenecks to be formed in the network. We demonstrated the use of exclusive sets for the purpose of deriving lower bounds on delay for a wireless network with single hop traffic. We further generalize the typical notion of a bottleneck. In our terminology, we define a (K, X)bottleneck to be a set of links X such that no more than K of them can simultaneously transmit. Figure 1 shows (1, X) bottlenecks for a network under the 1 hop interference model. In this paper, we develop new analytical techniques that focus on the queuing due to the (K, X) bottlenecks. One of the techniques, which
we call the reduction technique, simplifies the analysis of the queuing upstream of a (K, X)bottleneck to the study of a single queue system with K servers as indicated in the figure. Furthermore, our analysis needs only the exogenous inputs to the system and thereby avoids the need to characterize departure processes on intermediate links in the network. For a large class of input traffic, the lower bound on the expected delay can be computed using only the statistics of the exogenous arrival processes and not their sample paths. To obtain a lower bound on the system wide average queuing delay, we analyze queuing in multiple bottlenecks by relaxing the interference constraints in the system. Our relaxation approach is novel and leads to nontrivial lower bounds.
For a (K,X)bottleneck in the system, at any time T 0, the sum of the queue lengths SX in X, under any scheduling policy is no smaller than that of the reduced system, i.e., QX(T) SX(T). Proof: We prove the above theorem using the principle of mahematical induction. Base Case: The theorem holds true for T = 0, since the system is initially empty. Induction hypothesis: Assume that the theorem holds at a
time T = t, i.e., QX(t) SX(t).
Induction Step: The following two cases arise.
Case 1: QX(t) K
QX(t + 1) = QX(t) K + AX(t)
SX(t) K + AX(t)
SX(t) IX(t) + AX(t)
= SX(t + 1).
Case 2: QX(t) < K.
Using Eq. (III.11), we have the following, QX(t + 1) = AX(t)
SX(t) IX(t) + AX(t)
= SX(t + 1).
Hence, the theorem is holds for T = t + 1.
Thus by the principle of mathematical induction, the theorem holds for all T.
Multihop wireless network with multiple sourcedestination pairs, given routing and traffic information. Each source injects packets in the network, which traverses through the network until it reaches the destination.
The delay performance of wireless networks, however, has largely been an open problem. This problem is notoriously difficult even in the context of wireline networks, primarily because of the complex interactions in the network (e.g., superposition, routing, departure, etc.) that make its analysis amenable only in very special cases like the product form networks. The problem is further exacerbated by the mutual interference inherent in wireless networks which,
complicates both the scheduling mechanisms and their analysis. Some novel analytical techniques to compute useful lower bound and delay estimates for wireless networks with singlehop traffic were developed . However, the analysis is not directly applicable to multihop wireless network with multihop flows, due to the difficulty in characterizing the departure process at intermediate links.

The backpressure policy may lead to large delays since the backlogs are progressively larger from the destination to the source. The packets are routed only from a longer queue to a shorter queue and certain links may have to remain idle until this condition is met. Hence, it is likely that all the queues upstream of a bottleneck will grow long leading to larger delays. A common observation of the optimal policies for the clique and the tandem network is that increasing the priority of packets which are close to the destination reduces the delay.


Start with a vector of link prices.

Obtain the tra_c injected into the network by each source (congestion control and routing problem).

Obtain the schedule with maximum aggregate price (scheduling problem).

Update prices (price updation) and go to Step 2.
It is wellknown that when the stepsizes in the price updation algorithm are chosen
appropriately, the lgorithm given above converges to the optimal solution of the primal problem within certain range [2].
Clique network with interference constraints such that only one pair of nodes can communicate at given time.
The general research on the delay analysis of scheduling policies has progressed in the following main directions:

Heavy traffic regime using fluid models:
Fluid models have typically been used to either establish the stability of the system or to study the workload process in the heavy traffic rÃ©gime. The maximumpressure policy (similar to the backpressure policy) minimizes the workload process for a stochastic processing network in the heavy traffic regime when processor splitting is allowed.

Stochastic Bounds using Lyapunov drifts:
This method is developed and is used to derive upper bounds on the average queue length for these systems. However, these results are order results and provide only a
limited characterization of the delay of the system. For example, the maximal matching policies achieve O(1) delay for networks with singlehop traffic when the input load is in the reduced capacity region. This analysis however, has not been extended to the multihop traffic case, because of the lack of an analogous Lyapunov function for thebackpressure policy.

Large Deviations: Large deviation results for cellular and multihop systems with single hop traffic have been to estimate the decay rate of the queueoverflow probability. Similar analysis is much more difficult for the multihop wireless network considered here, due to the complex interactions between the arrival, service, and backlog process.

A scheduler must satisfy the following properties.

Ensure high throughput: This is important because if the scheduling policy does not guarantee high throughput then the delay may become infinite under heavy loading.

Allocate resources equitably: The network resources must be shared among the flows so as not to starve some of the flows. Also, noninterfering links in the network have to be scheduled such that certain links are not starved for service. Starvation leads to an increase in the average delay in the system.
The above properties are difficult to achieve; given the dynamics of the network and the lack of apriori information of the packet arrival process. In the light of the previous work we choose to investigate the backpressure policy with fixed routing. The backpressure policy has been widely used to develop solutions for a variety of problems in the context of wireless networks and the importance of studying the trade offs in stability, delay, and complexity of these solutions is now being realized by the research community. This policy tries to maintain the queues corresponding to each flow in decreasing order of size from the source to the destination. This is achieved by using the value of differential backlog (difference of backlogs at the two ends of a link) as the weight for the link and scheduling the matching with the highest weight. As a result, the policy is throughput optimal. Henceforth, we shall refer to this policy as only the backpressure policy. We first study the delay optimal policy for a clique network.

S. Deering, Host extensions for IP multicasting, Stanford Univ., Stanford,
CA, Tech. Memo. RFC1112, Jan. 1989.

R. H. Gau, Z. J. Haas, and B. Krishnamachari, On multicast flow control
for heterogeneous receivers, IEEE/ACM Trans. Netw., vol. 10, no. 1,
pp. 86101, Feb. 2002.

L. Roberts, Rate based algorithm for point to multipoint ABR service,
inATM Forum Contribution 940772, Sep. 1994.

K. Y. Siu and H. Y. Tzeng, On maxmin fair congestion control for
multicast ABR services in ATM, IEEE J. Sel. Areas Commun., vol. 15,
no. 3, pp. 545556, Apr. 1997.

H. Saito, K. Kawashima, H. Kitazume, A. Koike,M. Ishizuka, and A. Abe,
Performance issues in public ABR service, IEEE Commun.Mag.,
vol. 34, no. 11, pp. 4048, Nov. 1996.

H. Dupuis and B. Hajek. A simple formula for mean multiplexing delay
forindependent regenerative sources. Queueing Systems Theory and
Applications, 16:195239, 1994.

A. Feldmann, N. Kammenhuber, O. Maennel, B. Maggs, R. D. Prisco,
and R. Sundaram. A methodology for estimating interdomain web traffic
demand. In IMC, 2004.

L. Georgiadis, M. J. Neely, and L. Tassiulas.Resource Allocation and
CrossLayer Control in Wireless Networks, Foundations and Trends in
Networking, volume 1.Now Publishers, 2006.

G. R. Gupta. Delay Efficient Control Policies for Wireless Networks.
Ph.D. Dissertation, Purdue University, 2009.

G. R. Gupta, S. Sanghavi, and N. B. Shroff. Node weighted scheduling.
SIGMETRICSPerformance09, June 2009.

G. R. Gupta, S. Sanghavi, and N. B. Shroff. Workload optimality in
switches without arrivals. MAthematical performance Modeling and
Analysis Workshop, June 2009.

G. R. Gupta and N. B. Shroff. Delay analysis for wireless networks with
single hop traffic and general interferene constraints. IEEE Transactions
on Networking, 18:393 405, April 2010.

I. Ilog. Solver cplex, 2007. http://www.ilog.com/products/cplex/.

S. Jagabathula and D. Shah. Optimal delay scheduling in networks with
arbitrary constraints. In ACM SIGMETRIC/Performance, June 2008.

K. Jain, J. Padhye, V. Padmanabhan, and L. Qiu.
Impact of interference
on multihop wireless network performance. In
MOBICOM, 2003.

T. Ji, E. Athanasopoulou, and R. Srikant. Counter examples to the
optimality of mwsalpha policies for scheduling in generalized switches.
preprint, 2009.

I. Keslassy and N. McKeown. Analysis of scheduling algorithms that
provide 100% throughput in inputqueued switches. In 39th Annual
Allerton Conference on Communication, Control, and Computing. Monticello,
Illinois, October 2001.