In the past few years Wireless Mesh Networks (WMNs) have developed as a promising technology to provide flexible and low-cost broadband network services. The Expected Transmission Count (ETX) routing metric has been put forward recently as an advanced routing metric to provide high QoS for static WMNs. Most previous research in this area suggests that ETX outperforms other routing metrics in throughput and efficiency. However, it has been determined that ETX is not immune to load sensitivity and route oscillations in a single radio environment. Route oscillations refer to the situation where packet transmission switches between two or more routes due to congestion. This has the effect of degrading performance of the network, as the routing protocol may select a non optimal path. In this thesis we avoided the route oscillation problem by forcing data transmission on fixed routes. This can be implemented in the AODV (Ad hoc On-demand Distance Vector) protocol by disabling both error messages and periodic updating messages (the HELLO scheme). However, a critical factor for our approach is that ETX must determine a high quality initial route in AODV. This thesis investigates whether the ETX metric improves initial route selection in AODV compared to the HOPS metric in two representative client-server applications: the Traffic Control Network (TCN) and the Video Stream (VS) network. We evaluate the ETX and HOPS metrics in a range of scenarios which possess different link qualities and different traffic loads. We find the ETX metric greatly improves initial route selection in AODV compared to the HOPS in the network in which only single flow exists. For networks in which there are multiple simultaneous flows, ETX behaves similar to HOPS in initial route selection. Based on these results, we find the solution of route stabilization to route oscillations in the context of ETX is only useful in the single flow case. To address this problem, we propose a modified solution of repeatedly broadcasting RREQ (Route Request) packets. Simulation results show that our modified solution allows ETX to be useful in the initial route selection in both single flow and multiple simultaneous flows cases.

In the past few years Wireless Mesh Networks (WMNs) have developed as a promising technology to provide flexible and low-cost broadband network services. The Expected Transmission Count (ETX) routing metric has been put forward recently as an advanced routing metric to provide high QoS for static WMNs. Most previous research in this area suggests that ETX outperforms other routing metrics in throughput and efficiency. However, it has been determined that ETX is not immune to load sensitivity and route oscillations in a single radio environment. Route oscillations refer to the situation where packet transmission switches between two or more routes due to congestion. This has the effect of degrading performance of the network, as the routing protocol may select a non optimal path. In this thesis we avoided the route oscillation problem by forcing data transmission on fixed routes. This can be implemented in the AODV (Ad hoc On-demand Distance Vector) protocol by disabling both error messages and periodic updating messages (the HELLO scheme). However, a critical factor for our approach is that ETX must determine a high quality initial route in AODV. This thesis investigates whether the ETX metric improves initial route selection in AODV compared to the HOPS metric in two representative client-server applications: the Traffic Control Network (TCN) and the Video Stream (VS) network. We evaluate the ETX and HOPS metrics in a range of scenarios which possess different link qualities and different traffic loads. We find the ETX metric greatly improves initial route selection in AODV compared to the HOPS in the network in which only single flow exists. For networks in which there are multiple simultaneous flows, ETX behaves similar to HOPS in initial route selection. Based on these results, we find the solution of route stabilization to route oscillations in the context of ETX is only useful in the single flow case. To address this problem, we propose a modified solution of repeatedly broadcasting RREQ (Route Request) packets. Simulation results show that our modified solution allows ETX to be useful in the initial route selection in both single flow and multiple simultaneous flows cases.

<p>Wireless mesh networks are widely used for various communication purposes and are often deployed in a broad range of outdoor applications. In cases where the deployment area is outside the reach of fixed infrastructure, energy efficient operation of the mesh nodes is very important. Many approaches have been explored to find energy efficient network solutions for these types of scenarios. This thesisproposes power saving mechanisms where the mesh network nodes opportunistically access coexistent vehicular networks. This is referred to as Opportunistic Vehicle Assisted Ferrying (OVAF). The history of using moving particles for message carrying can be found in research on intermittently connected networks. However, this approachhas never been considered with fully connected networks. Two different models are presented to model the OVAFmechanism: \textbf{a}. \emph{A flow based model}, and \textbf{b}. \emph{Apacket based model}. For each model an analytic lower bound isobtained by formulating a linear integer optimization with differentcost functions. Heuristics, which simplify the complexity of theproblem, are then developed for eachmodel. Arriving vehicles and generated packets are also modeled asrandom processes under various scenarios using different parameters.Results are presented which demonstrate the superiority of the OVAFrouting method compared to conventional multihop forwarding (Up to $60\%$increase in energy saving).</p> / Master of Applied Science (MASc)

No / Wireless local area networks (WLANs) have risen in popularity for in-car networking systems that are designed to make driving safer. Wireless mesh networks (WMNs) are widely deployed to expand the coverage of high-speed WLANs and to support last-mile connectivity for mobile users anytime and anywhere at low cost. Many recent measurement studies have shown that the traffic arrival process in wireless networks exhibits the bursty and correlated nature. A new analytical model is developed in this paper as a cost-effective performance tool to investigate the quality-of-service (QoS) of the WMN that interconnects multiple WLANs in the presence of bursty and correlated traffic. After validating its accuracy via extensive simulation experiments, the analytical model is then used to investigate the performance of the hybrid wireless networks.

We address several problems that arise in a multihop wireless mesh network. First, we study the problem of joint congestion control, routing and MAC layer scheduling. We formulate the problem as an aggregate utility maximization problem and apply duality theory to decompose the problem into two sub-problems, namely, network layer congestion control and routing problem, and MAC layer scheduling problem. Given the link “prices", the source adjusts its rate based on the cost of the least-cost path to the destination, and sends traffic to the destination along the least-cost path, while link scheduling is carried out based on link prices. Optimal link scheduling for a wireless network is known to be NP-hard. We explore the use of a known centralized greedy heuristic, and develop a distributed algorithm that can schedule independent links based on local information. While the link scheduling algorithm above is for a given set of link prices, the solution to our problem depends on the sequence of price vectors generated by the price update algorithm. This leads us to study convergence issues related to the price update algorithm. Next, we develop a practical protocol which maximizes aggregate utility in a wireless mesh network. We simulate our protocol using Qualnet 4.5 and compare the result with a baseline protocol that uses IEEE 802.11 for link scheduling and AODV for routing. Our proposed protocol requires the durations of slots and subslots to be defined. We develop an approach in which given a single cell wireless mesh network using IEEE 802.11 as a reliable message delivery mechanism, one can find upper and lower bounds on the durations of slots. We employ stochastic ordering to compare distributions of random variables and using some properties of stochastic ordering along with the central limit theorem, we devise a way to compute the above mentioned bounds on the durations. In the second part, we shift our focus to model delays incurred by application packets sent over a WLAN. In this section we model the WLAN as a Random Polling System. The packet arrival process at each node i is assumed to be a stationary and independent increment random process with mean ai and second moment a(2)i . The packet lengths at node i are assumed to be i.i.d random variables Pi with finite mean and second moment. Utilizing available results, we obtain expressions for mean packet delay. Extensive simulations are conducted to verify the analytical results.

近年來無線網狀網路(Wireless Mesh Networks)備受矚目，無線網狀網路繼承原有的ad hoc networks的特性並提供階層式及多網卡的網路存取架構。在multi-hop networks下，傳輸功率的控制和網路路由的選擇是重要的議題，因為不同的傳輸功率產生不同的網路拓墣連結性和干擾。此外，在不同網路卡間的路由選擇也會產生不同程度的intra/inter-flow 干擾。這些特性對網路效能有密切的影響，過去相關的路由協定設計也大多未同時考量傳輸功率控制與多網路卡的特性。 在這篇論文中，我們提出了跨網路協定層的路由協定，稱作M2iRi2，同時考量傳輸功率的控制並將Intra/Inter-flow的干擾導入到路由路徑的選擇。節點上的網路卡在物理層(Physical layer) 計算目前對潛在可容忍的新增干擾，並將此訊息送到網路層(Network layer)和鄰居節點作交換。透過此資訊的交換，在路由發現時控制路由請求封包的傳輸功率，當路由建立後，封包根據路由表的記載，選擇所對應的路由路徑和傳輸功率。經由NS-2模擬結果顯示，我們所提出的跨網路協定層路由協定可同時兼顧網路的吞吐量和平均點對點的延遲。 / In recent years, WMNs (Wireless Mesh Networks) technologies have received significant attentions. WMNs not only accede to the advantages of ad hoc networks but also provide hierarchical multi-interface architecture. Transmission power control and routing path selections are critical issues in the past researches of multi-hop networks. Variable transmission power levels lead to different network connectivity and interference. Further, routing path selections among different radio interfaces will also produce different intra/inter-flow interference. These features tightly affect the network performance. Most of the related works on routing protocol design do not consider transmission power control and multi-interface environment simultaneously. In this thesis, we proposed a cross-layer routing protocol called M2iRi2 which coordinates transmission power control and intra/inter-flow interference considerations as routing metrics. Each radio interface calculates the potential tolerable added transmission interference in the physical layer. When the route discovery starts, the M2iRi2 will adopt the appropriate power level to evaluate each interface quality along paths. The simulation results demonstrate that our protocol can enhance both network throughput and end-to-end delay.

無線網狀網路(WMNs)為目前熱門的廣域無線網路接取技術。使用者可以透過WMNs隨時在各處使用即時影音播放的服務。相較於傳統的主從式架構，低成本且容易建置的點對點架構更適用於影音串流的應用；在進行即時影音播放的時候，影音播放的品質便為相當重要的目標。因為多媒體應用服務對於延遲及網路傳輸效能相當敏感，且WMNs的傳輸過程中常會面臨同頻道干擾的問題而使得傳輸的效能銳減，當每個網路節點都具有多張無線網路卡時，如何善用WMNs多頻道傳輸的特性提升效能更是顯得特別重要。在本篇論文中，我們利用WMNs多頻道傳輸的特性進行多媒體群播傳輸，參考史坦納樹的概念來改善現有的MAODV路由演算法，以傳輸品質較佳的鏈結改良原本尋找最小跳躍數路徑的方式，建立兩棵完全互斥的群播樹作為點對點傳輸的骨幹網路，並以MDC的概念將影像串流編碼成兩份獨立的子串流分別經由不同的群播樹傳輸。經實驗評估，我們的方法在網路負載較高的環境下能有效的降低延遲並提高整體系統的效能。 / In WMNs, users can enjoy the real-time video streaming service anytime and anywhere through the services. Compared to the client/server model, P2P approaches is more suitable for video streaming applications because of its low cost and easy deployment. But when using the real-time multimedia service in WMNs, the multimedia applications are very sensitive to delay time and the performance of packets transmission. And the performance is significantly influenced by the co-channel interference, so that it is important to know how to transmit by multi-channel to enhance the performance. In our approach, we choose the better quality links for routing instead of the minimum hop-count path in MAODV. Then we distribute the video streaming to receivers by multicast in multi-channel WMNs, and refer to the Steiner tree concept to modify the MAODV routing protocol to construct two disjoint multicast trees as the backbone for the P2P structure. Therefore, we can adopt the MDC scheme to encode the video into two independent sub-streams and transmit separately along these trees. Experiment results show that in higher network traffic load environment, our scheme is more effective to reduce the latency and improve overall system performance.

Les réseaux maillés sans fil (RMSF), grâce à leurs caractéristiques avantageuses, sont considérés comme une solution efficace pour le support des services de voix, vidéo et de données dans les réseaux de prochaine génération. Le standard IEEE 802.16-d a spécifié pour les RMSF, à travers son mode maillé, deux mécanismes de planifications de transmission de données; à savoir la planification centralisée et la planification distribuée. Dans ce travail, on a évalué le support de la qualité de service (QdS) du standard en se focalisant sur la planification distribuée. Les problèmes du système dans le support du trafic de voix ont été identifiés. Pour résoudre ces problèmes, on a proposé un protocole pour le support de VoIP (AVSP) en tant qu’extension au standard original pour permettre le support de QdS au VoIP. Nos résultats préliminaires de simulation montrent qu’AVSP offre une bonne amélioration au support de VoIP. / Wireless mesh networks (WMNs), because of their advantageous characteristics, are considered as an effective solution to support voice services, video and data in next generation networks. The IEEE 802.16-d specified for WMNs, through its mesh mode, two mechanisms of scheduling data transmissions; namely centralized scheduling and distributed scheduling. In this work, we evaluated the support of the quality of service (QoS) of the standard by focusing on distributed scheduling. System problems in the support of voice traffic have been identified. To solve these problems, we proposed a protocol for supporting VoIP, called Assisted VoIP Scheduling Protocol (AVSP), as an extension to the original standard to support high QoS to VoIP. Our preliminary simulation results show that AVSP provides a good improvement to support VoIP.

We study the problem of joint congestion control, routing and MAC layer scheduling in multi-hop wireless mesh networks, where the nodes in the network are subjected to energy expenditure rate constraints. As wireless scenario does not allow all the links to be active all the time, only a subset of given links can be active simultaneously. We model the inter-link interference using the link contention graph. All the nodes in the network are power-constrained and we model this constraint using energy expenditure rate matrix. Then we formulate the problem as a network utility maximization (NUM) problem. We notice that this is a convex optimization problem with affine constraints. We apply duality theory and decompose the problem into two sub-problems namely, network layer congestion control and routing problem, and MAC layer scheduling problem. The source adjusts its rate based on the cost of the least cost path to the destination where the cost of the path includes not only the prices of the links in it but also the prices associated with the nodes on the path. The MAC layer scheduling of the links is carried out based on the prices of the links. The optimal scheduler selects that set of non-interfering links, for which the sum of link prices is maximum. We study the effects of energy expenditure rate constraints of the nodes on the maximum possible network utility. It turns out that the dominant of the two constraints namely, the link capacity constraint and the node energy expenditure rate constraint affects the network utility most. Also we notice the fact that the energy expenditure rate constraints do not affect the nature of optimal link scheduling problem. Following this fact, we study the problem of distributed link scheduling. Optimal scheduling requires selecting independent set of maximum aggregate price, but this problem is known to be NP-hard. We first show that as long as scheduling policy selects the set of non-interfering links, it can not go unboundedly away from the optimal solution of network utility maximization problem. Then we proceed and evaluate a simple greedy scheduling algorithm. Analytical bounds on performance are provided and simulations indicate that the greedy heuristic performs well in practice.

Les réseaux maillés sans fil (RMSF), grâce à leurs caractéristiques avantageuses, sont considérés comme une solution efficace pour le support des services de voix, vidéo et de données dans les réseaux de prochaine génération. Le standard IEEE 802.16-d a spécifié pour les RMSF, à travers son mode maillé, deux mécanismes de planifications de transmission de données; à savoir la planification centralisée et la planification distribuée. Dans ce travail, on a évalué le support de la qualité de service (QdS) du standard en se focalisant sur la planification distribuée. Les problèmes du système dans le support du trafic de voix ont été identifiés. Pour résoudre ces problèmes, on a proposé un protocole pour le support de VoIP (AVSP) en tant qu’extension au standard original pour permettre le support de QdS au VoIP. Nos résultats préliminaires de simulation montrent qu’AVSP offre une bonne amélioration au support de VoIP. / Wireless mesh networks (WMNs), because of their advantageous characteristics, are considered as an effective solution to support voice services, video and data in next generation networks. The IEEE 802.16-d specified for WMNs, through its mesh mode, two mechanisms of scheduling data transmissions; namely centralized scheduling and distributed scheduling. In this work, we evaluated the support of the quality of service (QoS) of the standard by focusing on distributed scheduling. System problems in the support of voice traffic have been identified. To solve these problems, we proposed a protocol for supporting VoIP, called Assisted VoIP Scheduling Protocol (AVSP), as an extension to the original standard to support high QoS to VoIP. Our preliminary simulation results show that AVSP provides a good improvement to support VoIP.