Research On Key Technologies For Opportunistic Routing In Multi-radio Multi-channel Wireless Mesh Networks

Wireless mesh networks(WMNs)are dynamically self-organized and self-configured multi-hop wireless networks,which has many advantages,such as easy network maintenance,low up-front cost,robustness,reliable service coverage,etc.It provides economical internet access services and has been applicated in home networking,community networking,enterprise networking,building automation and wireless city etc.WMNs become the key field of the future wireless networks.But the complex network flow distribution and the severe co-channel interference would lead to large performance degradation.Opportunistic Routing(OR)has been recently proposed as a radically new paradigm,which involves multiple forwarding candidates to relay packets by taking advantage of the broadcast nature and multi-user diversity of the wireless medium where different nodes receiving the same packet are independent.Compared with Traditional Routing(TR),OR is more suitable for the unreliable wireless link,and can increase the reliability of packet transmissions and evidently improve the end to end throughput of WMNs.However,the existing OR ignores the distribution of flows,and rarely exploits the Multi-Radio and Multi-Channel resources to mitigate the co-channel interferences.They only limitedly increase the transmission throughput of WMNs.Thus,this dissertation focuses on the two problems and the main works are as follows:(1)At present,the OR doesn't take account of the traffic load,therefore some nodes may be overloaded while the others may not,leading to network performance decline.The opportunities routing for Multi-flow is described as a convex optimization problem.In order to solve the problem,by combining primal-dual and sub-gradient methods,a fully distributed joint candidate node selection and rate allocation Opportunities Routing for the Multi-flow algorithm(ORMf)is proposed.ORMf allocates the flow rate iteratively and rate allocation decides the candidate node selection of opportunities routing.The simulation results show that ORMf algorithm improves 33.4%,27.9%in aggregative throughput,decreases 127%and 21.3%in total delay comparing with ETX and EAX.(2)In order to validate the advantage of OR in Multi-Radio Multi-Channel WMNs,we propose a Simple Channel Assignment for Opportunistic Routing(SCAOR),which exploits common channel assignment and flow based channel selection algorithm.In this algorithm,all nodes collect the state of interference in the neighbor range and the channel with minimum interference is selected for each flow.We implement the SCOAR in a fully distributed manner.The simulation result shows that,compared with OR in single-radio single-channel WMNs,our OR can promote throughput evidently,specifically 87.11%and 100.3%in grid and tree WMNs respectively.OR can achieve a comparable or even better performance as TR with less radio resource.(3)OR route metric design in MRMC-WMNs is very challenging.One way to design the metric is directly using the single channel OR metric which ignores the channel diversity,such as EAX,EATT.The other way to design OR metric is based on current multi-channel route metrics which cannot exploit the resource of multiple candidate forwarders for OR,such as WCETT,SIM,MIC.Therefore,both above solutions can't select suitable route for OR in MRMC-WMNs.We propose a new route metric--Multi-channel Expected Anypath Transmission Time(MEATT),which considers the channel diversity and multiple candidate forwarders for OR.Based on the new metric,a distributed algorithm named Channel Aware Opportunistic Routing(CAOR)is proposed.The simulation results show that MEATT/CAOR improves 1.14 and 1.53 times of average throughput than EATT,MIC respectively.The average delay of MEATT/CAOR is 17%and 40%lower than those of EATT,MIC.(4)The existing channel assignments aren't designed for OR.Directly using the existing channel assignment leads to decreasing the number of candidate forwarders and the performance of OR.According to OR with one-to-more transmission mode,the Candidate Forwarder Set based Channel Assignment(CFSCA)for OR is proposed.Firstly,according to the candidate forwarders selected by routing,we bound the sender node and its candidate forwarders as a Candidate Forwarder Set.Then we calculate the interference among all the Candidate Forwarder Sets.Then the channel assignment for OR is described as a minimum Candidate Forwarder Set interference optimization problem,which must obey the constraints of the channel number of Candidate Forwarder Set and the number of radio interfaces.The evaluation results show that CFSCA improves 25.2%,10%,19%of the aggregative throughput than random,uniform and tradition channel assignment,respectively.(5)Only few work studies OR in Multi-Radio Multi-Channel wireless network,while these studies either select opportunistic route given channel assignment is settled,or assign channel to nodes based on selected opportunistic routing,which separate the interdependency of opportunistic routing and channel assignment,and can hardly achieve good performance.By concurrently considering opportunistic routing and channel assignment,we formulate the joint problem of opportunistic routing and channel assignment as a mixed integer programming(MIP)problem which is NP-hard.To solve the problem,we propose a heuristic iterative algorithm named Joint Opportunistic Routing and Channel Assignment(JORCA)which can exploit both multi-user diversity and channel resource.In JORCA,we start with an initial estimation of the link capacity without regard to the link expected load,and then iterate over routing and channel assignment steps until the bandwidth allocated to each link matches its expected load as closely as it can reach.The simulation results demonstrate that,comparing with the two existing solutions of opportunistic routing selection and channel assignment,our JORCA improves 44%and 15.5%in total throughput,decreases 127%and JORCA improves 44%and 15.5%in total throughput,decreases 127%and 21.3%in total delay.In summary,this dissertation exploits multi-radio multi-channel resource and studies the OR to improve the performance of WMNs,to satisfy the high bandwidth service needs of wireless users in WMNs.