Cross Layer Design With Multi Packet Reception Mac And Network Coding In Multi Hop Networks

A cross-layer design approach is proposed that can be used to optimize the cooperative use of multi-packet reception (MPR) and network coding. A simple and intuitive model is constructed for the behavior of an opportunistic network coding scheme called COPE proposed by Katti et. al., MPR, the 802.11 MAC, and their combination. The model is then applied to key small canonical topology components and their larger counterparts. The results obtained from this model match the available experimental results with fidelity. Using this model, fairness allocation by the 802.11 MAC is shown to significantly impede performance and cause non-monotonic saturation behaviors; hence, a new MAC approach is devised that not only substantially improves throughput by providing monotonic saturation but provides fairness to flows of information rather than to nodes. Using this improved MAC, it is shown that cooperation between network coding and MPR achieves super-additive gains of up to 6.3 times that of routing alone with the standard 802.11 MAC. Furthermore, the model is extended to analyze the improved MAC's asymptotic, delay, and throughput behaviors. Finally, it is shown that although network performance is reduced under substantial asymmetry or limited implementation of MPR to a central/bottleneck node, there are some important practical cases, even under these conditions, where MPR, network coding, and their combination provide significant gains.

Network coding is an innovative idea to boost the capacity of wireless networks. However, there are not enough analytical studies on throughput and end-to-end delay of network coding in multi-hop wireless mesh network that incorporates the specifications of IEEE 802.11 Distributed Coordination Function. In this dissertation, we utilize queuing theory to propose an analytical framework for bidirectional unicast flows in multi-hop wireless mesh networks. We study the throughput and end-to-end delay of inter-flow network coding under the IEEE 802.11 standard with CSMA/CA random access and exponential back-o↵ time considering clock freezing and virtual carrier sensing, and formulate several parameters such as the probability of successful transmission in terms of bit error rate and collision probability, waiting time of packets at nodes, and retransmission mechanism. Our model uses a multi-class queuing network with stable queues, where coded packets have a non-preemptive higher priority over native packets, and forwarding of native packets is not delayed if no coding opportunities are available. The accuracy of our analytical model is verified using computer simulations. Furthermore, while inter-flow network coding is proposed to help wireless networks approach the maximum capacity, the majority of research conducted in this area is yet to fully utilize the broadcast nature of wireless networks, and to perform e↵ectively under poor channel quality. This vulnerability is mostly caused by assuming fixed route between the source and destination that every packet should travel through. This assumption not only limits coding opportunities, but can also cause bu↵er overflow at some specific intermediate nodes. Although some studies considered scattering of the flows dynamically in the network, they still face some limitations. This dissertation explains pros and cons of some prominent research in network coding and proposes a Flexible and Opportunistic Network Coding scheme (FlexONC) as a solution to such issues. Moreover, this research discovers that the conditions used in previous studies to combine packets of di↵erent flows are overly optimistic and would a↵ect the network performance adversarially. Therefore, we provide a more accurate set of rules for packet encoding. The experimental results show that FlexONC outperforms previous methods especially in networks with high bit error rates, by better utilizing redundant packets permeating the network, and benefiting from precise coding conditions.

Abstract: We investigate the problem of designing delay-aware joint flow control, routing, and scheduling policies in general multi-hop networks for maximizing network utilization. We intend to improve end-to-end delay performance of general multi-hop networks at no cost of long term throughput degradation. Since the end-to-end delay performance has a complex dependence on the high-order statistics of cross-layer algorithms, earlier optimization-based design methodologies that optimize the long term network utilization are not immediately well-suited for delay-aware design. This motivates us in this work to develop a novel design framework and alternative methods that take advantage of several unexploited design choices in the routing and the scheduling strategy spaces. In particular, we propose a multi-layer algorithm architecture for multi-purpose joint policy design and operation. We reveal and exploit a crucial characteristic of back-pressure-type controllers that enables us to develop a novel link rate allocation strategy that not only optimizes long-term network utilization, but also yields loop free multi-path routes between each source-destination pair. Moreover, we propose a regulated scheduling strategy, based on a token-based service discipline, for shaping the per-hop delay distribution to obtain highly desirable end-to-end delay performance. We establish that our joint flow control, routing, and scheduling policy achieves loop-free routes and optimal network utilization. Our extensive numerical studies support our theoretical results, and further show that our joint design leads to substantial end-to-end delay performance improvements in multi-hop networks compared to earlier solutions.

In this thesis we deal with the application of Network Coding to guarantee the Quality of Service (QoS) for wireless multi-hop networks. Since the medium is shared, wireless networks suffer from the negative interference impact on the bandwidth. It is thus interesting to propose a Network Coding based approach that takes into account this interference during the routing process. In this context, we first propose an algorithm minimizing the interference impact for unicast flows while respecting their required bandwidth. Then, we combine it with Network Coding to increase the number of admitted flows and with Topology Control to still improve the interference management. We show by simulation the benefit of combining the three fields: Network Coding, interference consideration and Topology Control. We also deal with delay management for multicast flows and use the Generation-Based Network Coding (GBNC) that combines the packets per blocks. Most of the works on GBNC consider a fixed generation size. Because of the network state variations, the delay of decoding and recovering a block of packets can vary accordingly degrading the QoS. To solve this problem, we propose a network-and content-aware method that adjusts the generation size dynamically to respect a certain decoding delay. We also enhance it to overcome the issue of acknowledgement loss. We then propose to apply our approach in a Home Area Network for Live TV and video streaming. Our solution provides QoS and Quality of Experience for the end user with no additional equipment. Finally, we focus on a more theoretical work in which we present a new Butterfly-based network for multi-source multi-destination flows. We characterize the source node buffer size using the queuing theory and show that it matches the simulation results.

Doctoral Thesis / Dissertation from the year 2016 in the subject Computer Science - Miscellaneous, grade: 16, , language: English, abstract: In this thesis, we have modified AODV routing protocol by incorporating link prediction algorithm using a proposed link prediction model. This algorithm predicts the link availability time and even before the link breaks; either it repairs the route locally or sends information to the source nodes to enable them to initiate a new route search well in time. This algorithm improves the quality of service of the network. Simulation results show that AODV routing algorithm with link availability model performs better than the existing AODV. Advances in wireless technology and hand-held computing devices have brought revolution in the area of mobile communication. The increasing mobility of humans across the globe generated demand for infrastructure-less and quickly deployable mobile networks. Such networks are referred to as Mobile Adhoc Networks (MANET). Usually, nodes in a MANET also act as a router while being is free to roam while communicating each others. Adhoc networks are suited for use in situations where infrastructure is unavailable or to deploy one is not cost-effective. Frequent changes in network topology due to mobility and limited battery power of the mobile devices are the key challenges in the adhoc networks. The depletion of power source may cause early unavailability of nodes and thus links in the network. The mobility of nodes will also causes frequent routes breaks and adversely affects the required performance for the applications. Availability of a route in future mainly depends on the availability of links between the nodes forming the route. Therefore, it is important to predict the future availability of a link that is currently available. We have proposed an analytical model for link prediction using Newton divided difference method. This link availability algorithm is incorporated in AODV routing algorithm (AODVLP) to evaluate the performance of AODV routing protocol using the metrics viz. delivery rate, average end-to-end delay, average RTS collisions per node and route failure. In the existing AODV protocol, packets are routed until a link in the existing path fails. This results in degradation of quality of service of network in terms of end-to-end delay and delivery ratio.

Abstract: "Wireless systems for industry have mostly used cellular-phone-style radio links, using point-to-point or point-to-multipoint transmission. Past research has indicated that these network architectures are not suitable for several industrial applications because of their rigid structure, meticulous planning requirements, and dropped signals. In contrast, wireless mesh networks are multi-hop systems in which devices assist each other in transmitting packets through the network, and they provide a reliable, flexible system that can be extended to thousands of devices. Some inherent advantages with mesh networks are scalability, non line-of-sight communications, high data rates, and low-cost deployment. Mesh networks have been deployed by MIT researchers and a few companies on a small scale. Mesh networks have not been deployed widely, in part because of some fundamental problems with the current protocols with regards to QoS support and scalability. To meet these requirements, the MAC protocol should be able to guarantee near constant capacity for networks of different sizes, and the routing protocol should perform admission control. Current CSMA-based MAC protocols have been shown to perform inadequately in terms of throughput and scalability in multi-hop deployments. The key problem with using protocols like IEEE 802.11 is that the link throughput is affected severely due to the exposed terminal problem, uncoordinated contentions, and wasteful backoffs. With the 802.11 MAC protocol, our results show that the capacity falls to about 1/10th for a chain and below 1/20th for a grid with horizontal constant bit rate flows. We have developed the WisperNet MAC and routing protocols, which provide end-to-end QoS guarantees over a multi-hop mesh network. By exploiting the topology information and the fact that fixed wireless nodes separated by 3 hops or more can transmit simultaneously, we eliminate collisions and maximize network utilization. The WisperNet routing protocol performs admission control. We show that the WisperNet MAC protocol can guarantee up to 9 times more capacity than IEEE 802.11, and this capacity remains nearly constant as the network grows. Also included is a performance analysis of different routing policies, and their effect on network utilization."