International Journal of Scientific & Engineering Research, Volume 5, Issue 9, September-2014 575

ISSN 2229-5518

Efficient Adaptive Routing Packet Transmission in Wireless Networks P. V. S. Srinivas1, D. Naga Swetha2

Abstract— Adaptive Routing is the progression of locating a clear path from a source point to a destination point across a network of nodes that could amend at any point. Mostly, Adaptive Routing algorithms make sure that data packets can move from one point in the network to another, even if one or more nodes in between are unavailable. To overcome the poor delay performance and complexities arise while implementing, a new and efficient adaptive routing algorithm has been developed. Here, to reduce the delays significantly, extra link activation is used by ignoring network coding. Every node maintains a counters set for scheduling the components of the algorithm with the help of probabilistic routing table. This algorithm assures less complexity and efficient adaptive routing.

Index terms—Adaptive Routing, Extra-Link Activation, Scheduling, Probabilistic Splitting, Probabilistic routing.

—————————— ——————————


Wireless Communication rebellion is bringing primary changes to data networking, telecommunication and is building integrated networks a reality. By freeing the user from the cord, personal communications networks, wireless LANs, mobile radio networks and cellular systems, harbour the promise of fully distributed mobile computing and communications, anytime, anywhere. Focusing on the networking and user aspects of the field, wireless networks provides a global form for archival value contributions documenting these fast growing areas of interest. Availability, cost, reliability, security, speed, scalability and topology can be considered as important characteristics in network design. Several Adaptive Routing protocols have been developed for different purposes. Like, (IS-IS) protocol is designed to route data through large networks namely Internet backbones. The (RIP) is exceptional for small distance transport. With deterministic adaptive routing strategies good quality results can be achieved [1]. Here, in this paper, we deal with the high delay and
queuing convolution issues. Due to routing loops the
routing algorithm leads to poor delay performance and to overcome this drawback a new algorithm designed which has much superior performance and low implementation complexity. By throughput- optimal routing, the number

P.V.S. Srinivas1 is presently serving as Professor & Head in the Department of Computer Science and Engineering at TKR College of Engineering & Technology, Hyderabad, India.

D. Naga Swetha2 is currently pursuing her masters degree program in

the Department of Computer Science and Engineering at TKR College of

Engineering & Technology, Hyderabad, India.

of hops taken by packet in the network can be
minimized[11]. A new concept named as Shadow Queues used here to decouple routing and scheduling in the network with the help of probabilistic routing tables. To update a probabilistic routing table a shadow network is used. The same shadow network, with back-pressure algorithm, is used to activate transmissions between nodes. However, first, actual transmissions send packets from first-in–first-out (FIFO) per-link queues, and second, potentially more links are activated, in addition to those activated by the shadow algorithm.[2]The major difference between the previous and present enhanced back-pressure algorithm is performing partial decoupling of shadow backpressure and real packet transmission allows us to activate more links. This difference results in good delay performance. The proposed algorithm is applicable to wire line and wireless networks.


By the way of specified in back pressure based adaptive routing algorithms that each packet is directed along a feasibly improved path, in addition such algorithms characteristically effect in deprived interval concert and associate high application complexity. The outmoded process groups the scheduling and routing functions well-balanced and conserves a queue for every target at each node. Consequently the number of targets can be as hefty as the number of nodes, this each-target queue up constraint can be relatively hefty for practical
implementation in a network. On every link, the

IJSER © 2014

International Journal of Scientific & Engineering Research, Volume 5, Issue 9, September-2014 576

ISSN 2229-5518

algorithm allocates a weight to every probable target that is called back pressure [2]. This feature stops further blocking nodes that remain earlier blocked, as a result provided that the adaptivity of the algorithm in contrast, can be useful in wired network only [3]. The back- pressure over a link should be positive that is contained in the selected schedule to transmit the packets over a link and this queue managing constraint possibly will be an excessive overhead for a huge network.
The constancy of a queuing network through
dependent servers is reflected. The dependence amongst the servers is achieved by defining their subsets which can be activated concurrently. The performance measure of a scheduling strategy is characterized by its constancy region, that is, the set of routes of arrival and facility rates for which the system is constant[2]. A strategy is achieved which is finest, in the sense that its constancy region is considered where it is a superset of every other scheduling policy region. The performance of the network is considered for arrival rates that lie exterior to the constancy region and the effects of the outcomes in certain forms of concurrent database and parallel processing systems are discussed. Multihop radio networks offer a stimulus for considering this system, where the problem of scheduling the server stimulation under the restraints carried out by the dependence amongst servers is considered.
The network abides of power controlled nodes which can be transmitted through wireless links along adaptive transmission rates. The packets access the system at every node randomly and remain within output queues to reach the target in the network. We set up the capacity region of all rate matrices (λij ) that the system can steadily support[11]. Here, (λij ) represent the rate of traffic induced at node ‘i’ and intended for node ‘j’. The dynamic routing and power allocation intended for a wireless network policy is developed with time changing channels which stabilize the system. It yields defined average delay covenant, at any time the input rates are within this capacity region [4]. We subsequently relate this control algorithm to an ad-hoc wireless network where channel changes are owed to user mobility, and its performance is correlated with the Grossglauser-Tse relay model. Such performance influence for common arrival and channel state process, despite processes are anonymous to the network controller.
The back-pressure algorithm is considered as a most eminent favourable algorithm but its delay concert
possibly will be relatively poor, even when the traffic load is not nearest to network capacity because of two reasons. Primary, every node has to sustain a sovereign queue for every asset in the network in addition only one queue is provided at a point. Secondary, this algorithm possibly will route a few packets across very long routes. The elucidation for multi-rate multicast is based on scheduling virtual traffic that moves in reverse direction from targets to origin. This shadow scheduling algorithm can also be used to manage setbacks in wireless networks [3]. In this paper, we specify elucidation to consign the above issues and decrease the complication of the queuing data structures which is maintained at every node in the case of a fixed-routing network scenario where the route of each flow is selected upon arrival [2].


Fig 1: System Architecture

3.1 Efficient Adaptive Routing Packet Transmission In the traditional methodology, a queue for each destination has to be maintained by every node. Every pair of nodes is communicated along a path connecting them and with this approach more number of queues has to be maintained. To overcome this snag, that is maintaining a queue for every destination, a queue for every neighbour, called a real queue is maintained by every node. By this, maintaining the number of queues at each node will be less when we compare it with traditional approach. Along with these real queues at each node, a counter is maintained called as Shadow Queue at the destination[11]. It is easier to maintain the counters at each node but the link activation has to be

decided to route packets to the neighbour queues.
Here are the algorithms made the Efficient Adaptive Routing Packet Transmission in an effective way.

A) M-Back-Pressure Algorithm: The shadow queues

are modernized based on the crusade of fabricated

IJSER © 2014

International Journal of Scientific & Engineering Research, Volume 5, Issue 9, September-2014 577

ISSN 2229-5518

entities as an interchange of control messages for the purposes of routing and schedule called shadow packets in the network. Same as like real packets, the shadow packets arrive from outside the network and eventually exit the network and runs on the shadow queuing system with an arrival rate marginally larger than the real external arrival rate of packets [5]. The shadow queue is basically a counter that is incremented by 1 upon a shadow packet arrival and decremented by 1 upon a departure and there is no necessity to implicate in any
queuing data structure at each node. The algorithm track
on the shadow queues is used to stimulate the links that are triggered to serve packets to a specific destination.

B) Joint Adaptive Routing Algorithm:

1) Probabilistic Splitting Algorithm: Based on the probabilistic routing table, the next hop of the packet will be taken by the probabilistic splitting algorithm. It signifies the number of potential shadow packets “transferred” from node to node intended for whose previous hop is during time-slot [6]. The packet emanates from an external flow that is funded by shadow traffic point-to-point transmission as well as shadow traffic broadcast transmission.


A) Transmissions, Links and Schedules: On encompassing the traditional tactic, let us consider networks where network coding is used to improve the throughput. Routing governs the presence of coding prospects that are available in the network. In the projected design, the algorithm finds the right trade-off between using feasibly long routes to provide network coding prospects and the delay sustained by using long routes [7]. To facilitate network coding, the node has to remember from which a packet was received. The two kinds of network model, namely point-to-point transmissions and broadcast transmission. A schedule can be defined based on two categories of “links”: the point- to-point link which supports point-to-point transmission and the broadcast link that contains links and supports broadcast transmission. Here, in this network model, we allow broadcast transmission.

Fig 2: Comparison between Back-pressure algorithm and

Adaptive Routing algorithm
B) Maintenance of Counters set: Each node maintains a set of counters, which are called shadow queues, for each previous hop and each destination and for external flows destined for at node. Each node also maintains a real queue, denoted by, for each previous hop and each next- hop neighbor, and for external flows with their next hop [8]. The shadow queues at each node are notable by their previous hop and their destination, then only accepts the packets from previous hop with destination. The related rule should be trailed when packets are shattered from the shadow queue.

C) Exponential Averaging: By using the perception of

shadow queues, we partially decouple routing and scheduling. A shadow network is used to up-date a probabilistic routing table that packets use upon arrival at a node. The same shadow network, with back-pressure algorithm, is used to trigger transmissions amongst nodes[9]. First, actual transmissions send packets from first-in–first-out (FIFO) per-link queues, and second, potentially more links are stimulated, in addition to those actuated by the shadow algorithm.

D) Token Bucket Algorithm: Computing the average shadow rate and generating random numbers for routing packets may enact a computational overhead of routers, which should be evaded if possible. As an alternative, at each node, for each next-hop neighbor and each destination, sustain a token bucket. Here, our objective is to afford an intuition behind the token bucket algorithm. By working on the join-the-shortest-queue discipline, we assume that the token processes are stable subsequently the total arrival rate to the token buckets at a node is less than the total service rate and the arrivals[9]. Likewise, the token buckets will “hit 0” in a nonzero fraction of time-slots, except in some degenerate cases; this in turn means that the arrival rate of packets at the token bucket

must be less than the token generation rate because of

IJSER © 2014

International Journal of Scientific & Engineering Research, Volume 5, Issue 9, September-2014 578

ISSN 2229-5518

random processes[11]. The token-based algorithm is an approximation due to the occurrence of breaks for prolonged periods of time.

E) Extra Link Activation: Under the shadow back- pressure algorithm, only links with back-pressure greater than or equal to M can be activated. The stability theory confirms that this is adequate to condense the real queues. The delay performance is unacceptable as the parameter M was familiarized to dampen the use of unnecessarily long paths[10]. Stimulate further links beyond those actuated by the shadow back-pressure algorithm.

F) Choice of the Parameter: In a wireless network, the

capacity at a link is determined by the shadow scheduling algorithm[5]. This capacity is assured to be at least equal to the shadow arrival rate of real packets which is obviously smaller. The difference between the link capacity and arrival rate could be proportional to epsilon, that should be sufficiently large to ensure small delays while also sufficiently small to ensure that the capacity region is not moderated ominously.


First, we compare the performance of three algorithms: the traditional back-pressure algorithm, the basic shadow queue routing/scheduling algorithm without the extra link activation enhancement, and Efficient Adaptive Routing Packet Transmission. Without extra link activation, to ensure that the real arrival rate at each link is less than the link capacity delivered by the shadow algorithm, links with back-pressure less than will not be scheduled and thus can contribute to further delays.

Fig 3: Delay performance of Efficient Adaptive Routing

Packet Transmission and shortest path routing.
Because we exaggerate the shadow traffic and the throughput region of the algorithm without extra link
activation is smaller than the throughput region of the
traditional back-pressure algorithm. We also compare the delay performance of Efficient Adaptive Routing Packet Transmission with that of the shortest path routing for each pair of source and destination, we find a shortest path between them by using Dijkstra’s algorithm[11].

Fig 4: Packet delay performance without network coding

Fig 5: Comparison of probabilistic splitting and token bucket algorithms

Efficient Adaptive Routing Packet Transmission can obtain similar delay performance as the shortest-path routing at light traffic[9]. A wireline network does not capture the scheduling aspects inherent to wireless networks. In the case of wireless networks, even with extra link activation, to confirm stability even when the arrival rates are within the capacity region. Extra link activation can be used to decrease delays significantly for especially in light traffic region.


In this paper, Efficient Adaptive Routing Packet Transmission routes the packets most probably on shortest hops and decouples routing and scheduling using a probabilistic splitting algorithm based on shadow queues. This can be maintained with the help of probabilistic routing table which slowly changes over

IJSER © 2014

International Journal of Scientific & Engineering Research, Volume 5, Issue 9, September-2014 579

ISSN 2229-5518

time. Efficient Adaptive Routing Packet Transmission provides efficient throughput and delays are reduced by extra link activation methodology.
We extend our approach to consider networks where network coding is used to increase throughput. This type of network coding reduces the number of transmissions. By enhancing the algorithm features, we can find the right trade-off between using possibly long routes to provide network coding opportunities delay incurred by using long routes. We can also allow broadcast transmission in our wireless network model, the total broadcast rate at which packets are scheduled.


[1] L.Tassiulas and A. Ephremides, “Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks,” IEEE Trans. Autom. Control, vol. 37, no. 12, pp. 1936–1948, Dec. 1992.
[2] M. J. Neely, E. Modiano, and C. E. Rohrs, “Dynamic power allocation and routing for time varying wireless networks,” IEEE J. Sel. Areas Commun., vol. 23, no. 1, pp. 89–103, Jan. 2005.
[3] L. Bui, R. Srikant, and A. L. Stolyar, “Novel architectures and algorithms for delay reduction in back-pressure scheduling and routing,” in Proc. IEEE INFOCOM Mini-Conf., Apr. 2009, pp.
[4] H. Seferoglu, A. Markopoulou, and U. Kozat, “Network coding-aware rate control and scheduling in wireless networks,” in Proc. ICME Special Session Netw. Coding Multimedia Streaming, Cancun, Mexico, Jun. 2009, pp. 1496–1499.
[5] S. B. S. Sengupta and S. Rayanchu, “An analysis
of wireless network coding for unicast sessions:
The case for coding-aware routing,” in Proc. IEEE INFOCOM, Anchorage, AK, May 2007, pp. 1028–
[6] A. Dimakis and J. Walrand, “Sufficient conditions for stability of longest-queue-first scheduling: Second-order properties using fluid limits,” Adv. Appl. Probab., vol. 38, no. 2, Jun.
[7] S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft, “XORs in the air: Practical wireless network coding,” Comput. Commun. Rev., vol. 36, pp. 243–254, 2006
[8] A. Brzezinski, G. Zussman, and E. Modiano,
“Enabling distributed throughput maximization in wireless mesh networks: A partitioning approach,” in Proc. ACM Mobicom, Sep. 2006, pp.
[9] T. Ho and H. Viswanathan, “Dynamic algorithms for multicast with intra-session network coding,” IEEE Trans. Inf. Theory, vol. 55, no. 2, pp. 797–815, Feb. 2009.
[10] X. Lin and N. B. Shroff, “Joint rate control and
scheduling in multihop wireless networks,” in

Proc. 43rd IEEE Conf. Decision Control, Dec. 14–17,

2004, vol. 2, pp. 1484–1489.
[11] Srinivas MRSP, P.V.S. Srinivas “Efficient Power Allocation Strategy based Cooperative Network” American Journal of Engineering Research, vol. 2
Issue 9, ISSN(E): 2320-0847, ISSN(P): 2320-0936,
pp. 100-102.

IJSER © 2014