Research On The Technologies Of Network Coding In Wireless Network

Since its discovery,Network Coding(NC)is used in many areas,such as network security,routing,reliable transmission etc.In this thesis,the technologies of Network Coding in Wireless Network are researched,including optimization issues related to hardware accelerations,opportunistic routing and reliable transmission.This thesis presents the following research contributions to the theory and practice of Network Coding:(1)Implement SIMD based hardware acceleration of random linear network-coding.It is well known that RLNC may achieve the multicast capacity.However,the practicality of network coding has been questioned,due to its high computational complexity.This paper represents an attempt towards a high performance implementation of network coding.Our core idea of optimization is processing the row multiplications which take 99%of the coding/decoding time by searching previous built GF(28)product tables with vector using the SSE3 instruction PSHUFB.On a dual-core Intel T5500 1.66G PC,the encoding bandwidth of our implementations is able to reach 24.522 MB/second with 128 blocks of 4KB each,which is several times greater then other SIMD implementations.(2)Propose a well-designed light-weighted Negative ACKnowledgment(NACK)oriented reliable multicast protocol,which leverages the Network Coding based repair in its design.Feedback round algorithm is applied to optimize the repair processing for living stream.The algorithm allows receivers to send NACK in rounds and sender response repair requests immediately.So that the delay for waiting response from the sender is distributed to each round and "jitter" is prevented.Experiment results show that the payload throughput of our protocol is about 0.5 times greater than that of standard Internet protocol NORM with 128 blocks of 1KB each and 2Mbps maximum sending rate.(3)Analysis a dynamic framework of multiple multicast sessions with intra-session network coding in WMNs.According to this framework,we propose MulSrc which is a distributed heuristic algorithm of routing,rate allocation and flow control for the random scheduling wireless network.A notion of virtual packets,called "credits" is introduced.By allocating "credits" on each node,MulSrc decouples routing,rate allocation and flow control from real packet transmissions.New statistics of "credits" are also given in this thesis.Simulation results show that MulSrc can get better performance than that of Pacifier if there are multiple multicast sessions in the network.(4)We present an optimization framework that enables us to derive optimal flow control,routing,scheduling schemes,where network coding is used to ease the routing problem.One of our main contributions is to prove the asymptotic optimality of the primal-dual congestion controller derived from the optimization framework.A heuristic implementation of the algorithm,named MulPro,is given.A TCP-like rate control mechanism is applied to adjust the source upper layer rate to network conditions,which makes MulPro suitable for delay-sensitive but loss-tolerant applications.Simulation results show that,in the dense network with multi-flows,MulPro can achieve higher throughput,lower cost and greater utility compared to other protocols of the same genre.(5)Present an utility-based optimization framework that combines INC and XNC in wireless mesh network.A primal-dual congestion controller routing of the framework is given and the asymptotic optimality of it is proved.A heuristic algorithm,MiiCode,is derived.In MiiCode,INC is treated as a kind of particular XNC and the transmission of XNC packets is determinded by "code credit" backlogs on the forwarders.The nature of RLNC is also used to simplify the protocol design.The simulation results show that MiiCode can achieve better performance than COPE and is more adaptable to network topologies than MulPro.Moreover,MulSrc,MulPro and MiiCode are all opportunistic routings for WMNs that are always connected.They are implemented as shims between the IP and the 802.11 MAC layers and make use of the broadcast nature of wirless channel and space variety of ends to improve the throughtput.They do not use full recovery in reliable transmission,which make them apply to the delay-sensitive but loss-tolerant applications,such as living streams.