Deadline Constraints Broadcasting in Wireless Network

Deadline Constraints Broadcasting in Wireless Network

Geetha

IV Sem M.Tech Student, Dept. Of CS & E, Adichunchanagiri Institute of Technology Chikmagalur, India

Darshan L. M.

Asst. Prof., Dept. Of CS & E, Adichunchanagiri Institute Of Technology, Chikmagalur, India

Abstract There is rising insist for using wireless networks for systems that generate packets with firm packet delay timing constraints. In addition to delay timing constraints, systems also has various traffic patterns and requires a guarantees on throughputs of packets that are delivered within their delay timing constraints. Furthermore, a device for serving delay- constrained traffic needs to consider the variable nature of wireless links, which may differ from point to point. We study a model that considers the application requirements on traffic patterns, delay timing constraints, throughput requirements and wireless limitations, including the variable nature of wireless links and the lack of feedback information. Based on this model, we develop a general framework for designing feasibility- optimal broadcasting policies for base station that applies to systems with various network coding mechanisms. For systems without network coding, we propose a simple, greedy online scheduling policy. We also propose online policies for systems with XOR coding and systems with linear coding. To understand whether per-transmission feedback is useful, we first develop a feasibility-optimal scheduling policy for systems where the base station has per-transmission feedbacks. We then compare the performance of this policy against a policy without feedback information through simulations.

Index Termsbroadcast, delay constraints, network coding, wireless networks.

1. INTRODUCTION

   The emergence of wireless technologies and mobile devices are anticipated that there will be growing need for using wireless networks for serving delay-constrained flows. Delay-constrained flows have a strict per-packet delay time bound on each packet they generate, and packets are not useful if they are delivered after their delay time bounds, where a base station is broadcasting a number of delay- constrained flows to its wireless nodes.

   One major problem for broadcasting traffic in wireless networks is wireless links are usually unreliable, and their qualities differ from point to point. The common solution to guarantee reliable deliveries over unreliable links is Automatic Repeat Request (ARQ), where clients provides feedback information to the base station after each transmission using either acknowledgments (ACKs) or negative acknowledgments (NACKs). However, gathering feedback information from each client increases with the size

   of the network, using ARQ for wireless broadcasting can affect significantly the delay and thus it is not scalable. Therefore, it is not required to collect feedback information in wireless broadcasting network.

   The capacity of wireless broadcasting over unreliable links can be increased by employing network coding. However, very little research has been conducted on using network coding for delay-constrained traffic. In particular, schemes that require the base station to obtain feedback information frequently are not practical except for small-sized networks.

   The adequate condition for scheduling the policy is to be feasibility-optimal among all the policies that can be engaged by a wireless system using an arbitrary network coding mechanism. Thus, designing the scheduling policies for a particular system can be condensed to finding a policy that satisfies the all conditions.

   The general structure by evaluating three different kinds of systems are one that does not uses network coding, one that uses XOR coding, and a third that uses linear coding. For the systems without network coding, we introduce a greedy online scheduling policy. This policy is proved to be feasibility-optimal using the general principles.

2. REVIEW OF LITERATURE

   1. H. Gangammanavar and A. Eryilmaz, Dynamic coding and rate-control for serving deadline-constrained traffic over fading channels, in 2010. In this paper, the optimal coding strategies for the network broadcasting delay- constrained flows, their works require the base station to obtain feedback information from clients frequently, and thus may not be scalable.

      The problem of optimal dynamic coding and rate- control for broadcasting deadline-constrained traffic is with average delivery ratio constraints over time-varying wireless channels. In particular, we propose and analyze a novel policy that utilizes a combination of pricing and finite- horizon dynamic programming strategies to jointly optimize the operation of the following two components: A dynamic rate allocation policy, which manages the incoming traffic flow rates so as to maximize their weighted sum; And a

      dynamic coding window selection policy, which satisfies the flows individual delivery ratio requirements. An important cellular downlink is the scenario with and without network coding capabilities to study its behavior under various conditions. Our simulations reveal that the dynamic coding strategy outperforms the optimal static coding strategy by opportunistically exploiting the statistical variations in the arrival and channel processes.

      An optimal rate control and coding operation for deadline constrained traffic over time varying wireless channels. A model was developed for a general communication system with heterogeneous delivery ratio requirements and priorities of different deadline constrained flows. A novel algorithm operating at different timescales was presented that combines dynamic pricing to determine the incoming flow rates and finite horizon dynamic programming for coding operations. The developed generic algorithm is also applied to the important scenario of cellular broadcast over erasure channels with random network coding. Simulations corroborate our results and also show the effect of various system parameters and application requirements.

   2. P. Gopala and H. E. Gamal, On the throughput- delay tradeoff in cellular multicast, in 2005. In this paper, tradeoff between the throughput, time delay the broadcasting. They have only studied the scaling laws of average delay, and thus their results are not applicable to scenarios where strict per-packet delay bounds are required. A adaptation of cross layer design approach for analyzing the throughput-delay tradeoff of the multicast channel in a single cell system. To, illustrate the main ideas, the single group case, i.e., pure multicast, where a common information stream is requested by all the users.

   Consider three classes of scheduling algorithms with, progressively increasing complexity. 1. The first class strives for minimum complexity by restoring to a static scheduling strategy along with the memory less decoding. Our analysis for this class of scheduling algorithms reveals the existence of the static scheduling policy that achieves the optimal scaling law of the throughput at the expense of a delay that increases exponentially with the number of users.

   1. The second scheduling policy resorts to a higher complexity incremental redundancy encoding/decoding strategy to achieve a superior throughput-delay tradeoff. 3. The third and most complex, scheduling strategy benefits from the cooperation between the different users to minimize the delay while achieving the optimal scaling law of the throughput.

      In particular, the proposed cooperative multicast strategy is shown to simultaneously achieve the optimal scaling aw of the both throughput and delay. Then, we generalize the scheduling algorithm to exploit the multi- group diversity available when different information streams are requested by different subsets of the potential gains of equipping the base station with multi-transmit antennas and present simulation results that validate theoretical claims.

      A cross layer design approach to shed more light on the throughput-delay tradeoff, in the cellular multicast channel. Towards this end, three classws of scheduling algorithms with progressively increasing complexity, and

      analysed the throughput-delay tradeoff achieved by each cases.

      The class of low comlexity static scheduling schemes with memoryless decoding. A special case of this scheduling strategy, i.e., the median user scheduler, achieves the optimal scaling law of the throughput at the expense of an exponentially increased delay with the number of users. An incremental redundancy multicast scheme that achieves a superior throughput-delay tradeoff, at the expense of increased encoding/decoding complexity.

      Further proposed cooperational scheme that achieves the optimal scaling laws of both throughput and delay at the expense of the high RF and computational comlpexity. The generalized schemes to the multi-group scenerio and characterized their ability to exploit the multi- group diversity offered by the wireless channel. Finally sented simulation result that establish the accuracy of the predictions of asymptotic analysis in systems with low to moderate number of users.

   2. W.-L. Yeow, A. T. Hoang, and C.-K. Tham, Minimizing delay for multicast-streaming in wireless networks with network coding, in 2009. In this paper, minimizing delay for broadcast flows by using network coding mechanism. Recent works show that the integration of layered media multicast with network coding can significantly improve the throughput of media distribution over the networks where there are a large number of receivers with heterogeneous reception capacities.

      However, because of stringent bandwidth and delay requirements arising in the applications of media delivery over bandwidth limited networks, it is very important to support guaranteed bandwidth and delay requirements for the receivers. Different from all the related works on increasing the throughput, this paper the problem of minimizing the transmission delay in layered multicast using network coding while supporting the guaranteed bandwidth requirements of the receivers. In this paper, the mathematical formulation for the problem, and then because the problem is NP-hard, we give an effective heuristic approach, which achieves low transmission delay with high bandwidth, to solve it.

      The simulation results demonstrate that our heuristic approach can greatly reduce the transmission delay while supporting high bandwidth requirements in layered multicast with network coding. This paper has proposed a framework for optimizing transmission delay in layered media multicast using network coding while making sure that the high bandwidth requirements of the receivers are guaranteed. In this paper, we have formulated the problem into a mathematical programming. Due to the NP-hardness of the problem, we then have proposed an effective heuristic approach MDLNC to efficiently solute the problem. The simulations conducted have shown that MDLNC can significantly improve the transmission delay while guaranteeing high bandwidth simultaneously in layered multicast with network coding.

   3. A. Albanese, J. Blomer, J. Edmonds, M. Luby, and M. Sudan, Priority encoding transmission in Nov. 1996. In this paper, the Priority Encoding Transmission (PET),

   offers the different reliability for different packets. This approach requires computing the priority of packets in advance.

   A new method is introduced for sending messages over loss packet-based networks. When a message is to be transmitted, the user specifies a priority value for each part of the message. Based on, the priorities, the system to receivers. The priority value of each part of the message determines the fraction of encoding packets sufficient to recover that part. Thus, even if some of the encoding packets are lost reroute, each receiver is still able to recover the parts of the message for which a sufficient fraction of the encoding packets are received.

   In many multi-media applications, long message are to be transmitted in real-time across multiple network links. A message is not sent as one unit, but broken into packets that are sent through the medium. Bit corruption may occur in packet due to transmission, but these can be handled on a link-by-link basis using error correcting techniques. Thus, assume that packets are indivisible units that arrive intact if they arrive at all. Once the packets are sent, some of the packets may arrive promptly, but arbitrary subsets of packets may lose or delayed beyond the point of usefulness due to global conditions in the network such as congestion, buffer overflows and other causes. This is here after call media with this property loss media. At some point in time, the receiver cannot wait for packets any longer and must recover as much of the original message as possible from the packets received.

   Scope of The Deadline Constraints Broadcasting in Wireless Network :

   • To design various traffic pattern for different types of systems.

   • To achieve the efficient throughput.

   • To deliver the large amount of packets within the delay bound.

3. METHODOLOGY

   Deadline Constraints Broadcasting in Wireless Network, where the Base station will broadcast the arrival of packets using different types of systems like greedy scheduler, pair-wise XOR, linear coding and feedback scheduler to the particular nodes.

   Designing the feasibility-optimal policies under any schedule space, since the base station does not have feedback information from clients, it cannot know the actual timely- throughput received by each client for each flow.

   However, with the knowledge of channel reliabilities, the base station can estimate the timely-throughputs by calculating the probability that a client obtains the packet of a flow in each interval.

   The indicator function that client actually receives the packet from flow in the interval under some policy. A random variable value is not known to the server.

   The history of all packet arrivals of all the flows up to and including time, with the conditional expectation taken under the broadcast policy used by the base station. Since the probability of successful reception of a packet by a client

   depends only on the number of times that a packet is broadcast and conditionally independent of everything else, it follows that is the conditional probability estimate made by the base station, of whether a packet of flow is successfully delivered to client in that interval, based on its actions in that interval.

   Fig 1: Architecture diagram for the Deadline Constraints Broadcasting in Wireless Network

   The random variables are bounded for all the former is the actual long-term timely-throughput of client on flow, while the latter is the asymptotic estimate made by the base station. The martingale stability theorem, define the expected delivery debt for each client and flow. The difference between many number of packets flow that is should have been delivered to client to fulfill its timely-throughput requirement, and the expected number of packets of flow that are delivered to client as estimated by the base station.

   A system is fulfilled by a policy, where we provide a sufficient condition for a policy to be feasibility-optimal, similar to that used by where unicast flows are considered. Let a nonnegative function depending only on, the set of all events in the system up to and including time. Suppose there exist positive constants, and a stochastic process also adapted. Let be the set of flows that generate packets in the interval. A base sation policy that maximizes for all, among all policies under its schedule space, is feasibility-optimal for its schedule space. Consider a strictly feasible system with timely-throughput requirements.

   There exists a positive number and a stationary randomized scheduling policy, which chooses a schedule randomly from the schedule space, based on the packet arrivals at the beginning of this interval and independent of the system history before this interval, fulfills the same system with timely-throughput requirements. Since the packet generations in each interval as an irreducible finite- state Markov chain and is a stationary randomized policy, there exists a large enough positive number such that the expected average timely-throughputs under in any consecutive intervals is larger than positive constant and is

   bounded by the employed policy. Thus, is feasibility-optimal, provides an avenue for designing scheduling policies.

   The scheduling policies for the base station:

   1. A sufficient condition for a scheduling policy to be feasibility-optimal among all policies that can be employed by a wireless system using an arbitrary network coding mechanism. Thus, designing scheduling policies for a particular system can be reduced to finding a policy that satisfies the sufficient condition.

   2. By evaluating three different kinds of systems: one that does not employ network coding, one that uses XOR coding, and a third that employs linear coding.

   3. For systems without network coding, greedy online scheduling policy is designed.

   4. Online policies for systems with XOR coding and systems with linear coding, proves the feasibility- optimal for their respective systems, under mild restrictions.

   Algorithm 1: Greedy Algorithm

   1: Number flows as 1, 2, 3,….., n 2: for to do i=1to n do

   3:ti <-1

   4:m<- nN,di,n(k)+pn

   5: end for

   6: for =1toT do 7:i<-arg maxjsk mj 8:ti<-ti+1

   9: m<- nN,di,n(k)+pn(1- pn)ti-1 10: end for

   11: for i=1 to n do

   12: for =1 to ti do

   13: broadcast the packet from flow i 14: end for

   15: for nN do

   16:d i,n(k+1)<- d i,n(k)+q i,n-[1-(1-pbi,n) t i] 17: end for

   18: end for

4. RESULT

   The proposed system consists of base station and its client nodes to broadcast the delay in the network where the base station may generate the flows as many it requires. By the feedback information from the clients the base station will calculates or determines the channel reliability, timely throughput to receive the packets with respect to time intervals. According to the feedback information the base station will uses the scheduling policies.

   There are mainly four policies, they are online greedy scheduling policy for the system which does not uses the network coding, online pair-wise XOR scheduling policy, online linear scheduling policy and feedback scheduling policy for the system which uses the network coding mechanism.

   Finally, we compare the performance of the network, with feedback information and without feedback information.

   Fig 2: Network establishment by the node

   Fig 2, shows the establishment of network where it has many nodes including the base station.

   Fig 3: Network establishment by identifying all its neighboring nodes

   Fig 3, shows the network establishment by identifying all its neighboring nodes. The base station has divided the time slot into many intervals, imagine in one interval one packet is generated many times to a particular node, in the same interval the node has to receive the packet or else the packet drop takes place. Alternatively, network coding compresses the schedule and enables the retransmission of the dropped packet.

   Meantime, the base station will calculate the weighted marginal delivery probability flow of the client node and reassume the timely throughput to receive the packet. And it uses the various scheduling policy to broadcast the delay in the network.

5. CONCLUSION

The optional usage of various network coding mechanisms, to design and develop scheduling policies for three different types of systems: one without network coding, one that employs pair wise XOR coding, and the other using linear coding is increasing the performance of the feasibility-optimal policy for systems without network coding. Thus, the network coding can increase the capacity of wireless networks for broadcasting delay-constrained flows.

REFERENCES

1. I-Hong Hou, Broadcasting Delay-Constrained Traffic Over Unreliable Wireless Links With Network Coding, in IEEE/ACM TRANSACTIONS ON NETWORKING.

2. H. Gangammanavar and A. Eryilmaz, Dynamic coding and rate-control for serving deadline- constrained, traffic over fading channels, in Proc. IEEE ISIT, 2010, pp. 17881792.

3. P. Gopala and H. E. Gamal, On the throughput-delay, tradeoff in cellular multicast, in Proc. Int. Conf. Wireless Netw., Commun, Mobile Comput., 2005, vol. 2, pp. 14011406.

4. W.-L.Yeow, A.T.Hoang, and C.-K. Tham, Minimizing delay for multicast-streaming in wireless networks with network coding, in Proc. IEEE INFOCOM, 2009, pp. 190198.

5. A. Albanese, J. Blomer, J. Edmonds, M. Luby, and M. Sudan, Priority encoding transmission, IEEE Trans. Inf. Theory, vol. 42, no. 6, pp. 17371744, Nov. 1996.