Topology Aware Channel Assignment in Single-radio Stub Wireless Mesh Networks

FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO Departamento de Engenharia Electrotécnica e de Computadores Topology Aware Channel Assignment in Single-radio Stub Wireless Mesh Networks Tânia Cláudia dos Santos Pinto Calçada Dissertação submetida para satisfação parcial dos requisitos do grau de doutor em Engenharia Electrotécnica e de Computadores Dissertação realizada sob a supervisão do Professor Doutor Manuel Alberto Pereira Ricardo, do Departamento de Engenharia Electrotécnica e de Computadores da Faculdade de Engenharia da Universidade do Porto Porto, Agosto de 2012 Abstract Stub Wireless Mesh Networks (WMN) are multi-hop networks composed by wireless routers and connected to an infra-structured network through a set of gateway nodes. Stub WMN have multiple applications such as extending Internet coverage, providing last mile smart grid networks, or deploying wireless infrastructure for surveillance purposes. These applications of WMN have different requirements regarding throughput, delay and equipment costs. If the cost of the equipment is a relevant requirement, the number of wireless interface cards may have to be limited to assist the reduction of the cost, however, the capacity of the network must be addressed. Radio interference causes a reduction of the WMN capacity and of its performance but the usage of multiple channels may help mitigating this problem. This work addresses the problem of channel assignment in stub WMN using the CSMA/CA access method and formed by multiple gateways, and by nodes having a single radio interface available to form the WMN. The problem consists in centrally deciding in which channel each WMN node shall operate so that the WMN becomes connected and the network performance is optimal. We argue that the problem can be solved by using solely the network topology information, instead of using also traffic information as done by state of the art works. In order to prove this claim a large set of experiments were conducted involving the simulation of thousands of network topologies. The main contribution of this thesis is a centralized joint routing and channel assignment algorithm for single-radio WMN (TILIA) used to improve the performance of single-radio WMN using multiple channels. We improve the performance of multi-channel WMN by controlling solely the channel in which each node operates. This performance gain is obtained by enhancing the gateway neighborhood, in particular by increasing its size and avoiding hidden nodes on links around the gateway, while keeping the load balanced between channels. TILIA uses a breadth-first tree growing technique but, instead of growing a single tree, TILIA grows a forest of trees each of which rooted at a different gateway and operating on a different radio channel. i Resumo As stub WMN são redes de múltiplos saltos compostas por routers sem fios ligados a uma rede infraestruturada através de um conjunto de portais. As stub WMN têm várias aplicações, tais como a extensão de cobertura da Internet sem fios, a parte de acesso de redes elétricas inteligentes, ou infraestrutura sem fios para sistemas de vigilância. Estas aplicações para stub WMN têm diferentes requisitos no que toca a custos de equipamento, tempos de resposta e débitos suportados. Se o custo do equipamento for requisito relevante, o número de interfaces de rede sem fios poderá ser limitado para promover a redução de custos, mesmo assim, a capacidade da rede deve ser considerada. As rádio-interferências provocam uma redução da capacidade e do desempenho das stub WMN, mas o uso de múltiplos canais rádio pode ajudar a atenuar este problema. Este trabalho aborda o problema da atribuição de canais em stub WMN que utilizam CSMA/CA como método de acesso e que são formadas por vários portais e por nós dispondo de apenas uma interface de rede sem fios para formar a stub WMN. O problema consiste em decidir centralmente em que canal rádio deve funcionar cada nó da rede de modo a que a stub WMN se mantenha ligada e que tenha um desempenho ótimo. Defendemos que o problema pode ser resolvido usando apenas as informações de topologia de rede, em vez de usar também as informações de tráfego como tem sido feito por trabalhos existentes no estado da arte. Para provar esta afirmação foi realizado um grande conjunto de experiências envolvendo a simulação de milhares de topologias de rede. A principal contribuição desta tese é um algoritmo centralizado de estabelecimento de rotas e de atribuição de canais rádio para stub WMN (TILIA) destinado a melhorar o desempenho das stub WMN que usam múltiplos canais e uma única interface de rede sem fios em cada nó. Melhoramos o desempenho das stub WMN controlando apenas o canal em que cada nó opera. Este ganho no desempenho é obtido através do melhoramento da vizinhança dos portais, em particular através do aumento do número de nós nessa vizinhança e evitando nós escondidos nas ligações em torno dos portais, enquanto se mantém a carga equilibrada entre os canais. O TILIA usa a técnica de procura em largura para formação de árvores em grafos mas em vez de formar uma única árvore, o TILIA forma uma floresta de árvores enraizadas em cada um dos portais e funcionando em diferentes canais rádio. iii Acknowledgements First and foremost I would like to than my advisor Prof. Manuel Ricardo. I has been an honor be his student. I appreciate all his contributions of time, ideas, and funding to make my work productive and stimulating. The joy and enthusiasm he has for research was contagious and motivational for me, even during tough times in the PhD pursuit. Throughout all the difficulties I had, Prof. Manuel Ricardo was always understanding and guided me with patience, humanity, kindness and wisdom. I am also thankful to INESC TEC, where I have been extremely lucky to reside for the past nine years and interact with such brilliant and insightful researchers. I truly enjoyed working with many people at INESC TEC and I would like to thank them for their support and friendship and also for the interesting discussions we had about so many different topics and in particular about the work in this dissertation (in alphabetical order): Ana Viana, António Pinto, Bruno Marques, Carlos Pinho, Fernando Pereira, Filipe Abrantes, Filipe Ribeiro, Filipe Sousa, Filipe Teixeira, Gustavo Carneiro, Gustavo Martins, Helder Fontes, Hermes del Monego, Jaime Cardoso, Jaime Dias, Mohammad Abdellatif, Jorge Mamede, Prof. José Ruela, Nuno Salta (“requiescat in pace”), Paula Viana, Pedro Fortuna, Pedro Pinto, Pedro Silva, Renata Rodrigues, Ricardo Duarte, Ricardo Morla, Rui Campos, Saravanan Kandasamy. Apologies to anyone I forget. Thanks to Faculdade de Engenharia da Universidade do Porto for providing excellent education and accepting me as student. This work was funded by the Portuguese government through Fundação para a Ciência e Tecnologia grant SFRH / BD/13444/2003 and by SitMe project from QREN–ON.2 program. On a more personal note, I would like to leave a warm word of thanks to my family and friends for their encouragement and moral support. To my mother, Filomena, for her patience and wisdom, and for being my foundation stone; to my father and grand parents for all their love; they transmitted to me the love of learning. To my sister Safira for her love, admiration and support. To my parents-in-law for their readiness and support. My beloved husband, Victor Calçada, and my wonderful children Maria, Sofia and Miguel deserve very special loving words, for being such incredible and kind human beings, who stood by my side and coped with my moody behavior during the writing of my thesis in the last months and suffering with those absences during the weekends and evenings of the last year. This journey would have been much harder without them in my life. Tânia Pinto Calçada v “Life is like riding a bicycle. To keep your balance you must keep moving.” Albert Einstein vii xiv LIST OF FIGURES 3.2 The channel assignment scheme used in A1 minimizes the number of hops to the gateway. The scheme used in A2 aims to reduce the number of contending neighbors. In the single channel scheme, A-SCh, the two gateways and the rest of the nodes are on the same channel. ......................... 48 3.3 (a) per-hop throughput (b) end-to-end throughput and (c) topology metrics of two dual-channel and one single channel assignment schemes presented on Figure 3.2. The 90% confidence intervals of the throughputs and topology metrics are also shown. . . . . . . 49 3.4 Amount of data transmissions on the networks of scenarios of Figure 3.2 when each node is generating a flow of 3 Mbit/s to a destination on the Internet. The white and black centers of each node represent the gateway used to forward the packets to the Internet. The face color of a node represents the amount of data frames that were successfully sent by that node. 52 3.5 Packets generated by sources (1) dropped in the queue by source nodes, (2) dropped in the queue by intermediate nodes, (3) dropped after exceeding the maximum retransmission retries limit, or (4) delivered to the final destination. . . . . . . . . . . . . . . . . . . 53 3.6 After a RTS message is sent, the following may happen (1) RTS is not received, (2) RTS is successfully received but the receiver does not answer with CTS, (3) RTS is followed by a CTS and then a data frame is sent which is not received, or (4) the RTS/CTS and the DATA/ACK pairs are successfully exchanged. . . 55 3.7 Amount of collisions on the networks of scenarios of Figure 3.2 when each node is generating a flow of 3 Mbit/s to a destination on the Internet. The white and black centers of each node represent the gateway used to forward the packets to the Internet. The face color of a node represents the amount of collisions perceived by that node. . . . . . . . . . . . . . . . . . 56 3.8 The network topology, end-to-end throughput with 90% confidence intervals and topology metrics of a reduced version of scenarios on Figure 3.2, where nodes on positions 2, 4, 6, 9, 11, 27, 29, 32, 34 and 36 (refer to Figure 3.1) were removed. . . . . . . . . . . . . . . 58 LIST OF FIGURES xv 3.9 Network topology when carrier sense range is 550 m using the same channel schemes of Figure 3.2. When the carrier sense range enables the gateways to sense each other’s transmissions, the single channel scenario (Scenario C-Sch) performance is lower than the Scenario A-Sch. The decrease and increase respectively of hidden nodes from Scenario A1 to Scenario C1 and A2 to C2 justifies the increase and decrease on the end-to-end throughput. . . . . . . . . . . . . . . 60 3.10 Network topology, end-to-end throughputs with 90% confidence intervals and topology metrics when gateways are deployed in positions 15 and 21 on the center ofthenetwork. ..................... 62 3.11 In the topology of(a), (b) is the if-graph, (c) is the tc-graph, (d) is the rc-graph, and (e) represents the hidden links. The 1st ring edges on these graphs represented as red strong lines. . . . . . . . . . . . . . . 63 3.12 Channel assignment schemes with few full connected nodes on the neighborhood of the gateway. End-toend throughputs with 90% confidence intervals and topology metrics are also presented. . . . . . . . . . . 64 3.13 Channel assignment schemes with few nodes on the neighborhood of the gateway, all hidden from each other. End-to-end throughputs with 90% confidence intervals and topology metrics are also presented. . . 66 3.14 Comparison of the end-to-end throughputs of networks of Scenarios E4, E3 of Figure 3.12 and Scenario A3ofFigure3.13..................... 68 3.15 Amount of collisions on the networks of scenarios E4, E3 and A3 when each node is generating a flow of 3 Mbit/s to a destination on the Internet. The white and black centers of each node represent the gateway used to forward the packets to the Internet. The face color of a node represents the amount of collisions perceived by that node. . . . . . . . . . . . . . . . . . 69 4.1 Methodology adopted in this study. The five stages are the random network topology generation, the network simulation, the measurement of simulation results, the generation of the data mining model and the sensitivity analysis. . . . . . . . . . . . . . . . . 76 4.2 Examples of generated random network topologies.The lines between nodes represent wireless connectivity between them. Nodes in different colors are in a differentchannel. ..................... 77 xvi LIST OF FIGURES 4.3 Example of a SVM and regression using the -insensitive tube............................ 80 4.4 Histograms of performance metrics. . . . . . . . . . . 83 4.5 Histograms of topology metrics. . . . . . . . . . . . . 87 4.6 Sample topology used to show the calculation of topology metrics of a network; the square node F is the networksink. ...................... 88 4.7 Throughput models. . . . . . . . . . . . . . . . . . . 92 4.8 Fairness models. . . . . . . . . . . . . . . . . . . . . . 98 4.9 Delay models. . . . . . . . . . . . . . . . . . . . . . . 100 4.10 Join probability function plot of delay and throughput. ...........................102 5.1 Sample network and shortest path spanning forest that illustrate the models used in this work. In the network presented in (a), solid lines represent links in the network, and dashed lines represent flows. (b) is a shortest path spanning forest Sof the network in (a). ...........................110 5.2 For the network represented in Figure 5.1, (a) is the tc-graph, (b) is the rc-graph, (c) is the if-graph, and (d) represents the hidden graph. . . . . . . . . . . . . 117 5.3 Illustration of the trade-off between minimizing the total load and have load balancing. . . . . . . . . . . 128 5.4 Performance comparison between TILIA and the stateof-the-art channel assignment strategies under TCP andUDPtraffic. ....................138 5.5 The mean data rate supported by each type of experiment for a given percentage of losses for experiments with TCP and UDP traffic. . . . . . . . . . . . . . . 140 5.6 Delay and packet loss results with different ratios of downlink and uplink UDP traffic. . . . . . . . . . . . 141 5.7 Accuracy of the network topology metric tmet. . . . 142 List of Tables 3.1 Parameter values used in ns-2.29 simulations of networks with lattice topology. . . . . . . . . . . . . . . 46 3.2 Total end-to-end throughput of the network is higher on scenarios A1 and A2 than in with B1 and B2. . . 57 4.1 Parameters used in ns-2.29 simulations of the random network topologies. . . . . . . . . . . . . . . . . . . . 78 4.2 Values of correlation between network topology metric and network performance metrics obtained on simulation results. . . . . . . . . . . . . . . . . . . . . 91 5.1 Notations used on the problem formalization. . . . . 108 5.2 Loads for the network and forests presented in Figures 5.3(a), 5.3(b), and 5.3(c). . . . . . . . . . . . . . 128 5.3 Parameters used in ns-2.29 simulations of network topologies resultant from channel assignment with TILIA and other strategies. . . . . . . . . . . . . . . 135 xvii Chapter 1 Introduction This thesis is framed in the general field of wireless networks, in particular those networks operating based on the IEEE 802.11 standard [1]. With the fast growth of the Internet and the increasing demand for network connectivity anywhere and anytime, wireless access networks based on the IEEE 802.11 standard are assuming a prominent role. IEEE 802.11 access points are being massively deployed around the world in organization buildings, cities, homes, and vehicles, as a mean to provide wireless Internet access to people using laptops, mobile phones, and to other devices such as smart meters, vehicles, cameras, sensors, or industrial equipment. However, IEEE 802.11 has a limited radio range. The coverage of large geographical areas with this technology can only be achieved by deploying a large number of Access Points (APs). If wires are used to connect the APs to the infrastructure, the deployment of large IEEE 802.11 networks can be expensive and complex and, in some cases, it can even be impossible to execute due to the construction works required. Wireless Mesh Networks (WMN) is one of the key technologies that will dominate wireless networking in the next decade [2]. WMN will help to realize the Always Best Connected [3] concept with simplicity and low cost. Their wireless multi-hop nature and their capability for self-organization significantly reduces the complexity of network deployment and maintenance and helps reducing the 1 2Introduction operational costs. The multi-hop term refers to the fact that data from a source needs to travel through several other intermediate nodes, via wireless links, before it reaches the destination. There are multiple definitions of WMNs. For R. Bruno et al. in [4], WMN are built on a mix of fixed and mobile nodes interconnected via wireless links to form a multi-hop ad hoc network that extends wired infra-structured networks, coexisting with them. For Akyildiz et al. [2], a WMN consists of mesh routers and mesh clients, where mesh routers have minimal mobility and form the backbone of WMNs that provides network access for both mesh and conventional clients. In this thesis, a WMN is assumed to be a stub WMN which is composed by a set of fixed wireless routers multi-hop connected to each other, and some of these wireless routers are also wired connected to the infra-structured network acting as gateway nodes. Early WMNs can be traced back to the DARPA Packet Radio Network (PRNet) project in 1972 [5] and to Mobile Ad-hoc Networks (MANETs) [6]. After almost a decade of research into ad hoc networking, MANET technology had not yet affected the way of using wireless networks because most of the ongoing research on mobile ad hoc networks was driven by either Departments of Defense requirements (large-scale military applications with thousands of ad hoc nodes) or specialized civilian applications (disaster recovery, planetary exploration, etc) [4]. To turn MANETs into a commodity, some changes to the original MANET definition were required. By relaxing one of the main constraints of MANETs, “the network is made of user’s devices only and no infrastructure exists,” the research community moved to a more pragmatic “opportunistic ad hoc networking” in which multi-hop ad hoc networks are not isolated self-configured networks, but rather emerge as a flexible and low-cost extension of wired infrastructure networks, coexisting with them [7, 8, 9]. WMNs are the new class of networks that emerged from this view in the early years of the 21 century [10]. Current research challenges on WMNs address all the layers of the communications stack and study the critical factors of WMN design including the following [2] : (1) to improve the WMN capacity using novel radio techniques on the physical layer or through cross-layer solutions that explore the existence of multiple channels; 1.1 Problem characterization 3 (2) to improve the scalability of WMNs by redesigning scalable protocols from the Medium Access Control (MAC) to the application layers; (3) to provide security on WMNs by adapting existing security schemes designed for single hop or for ad-hoc networks; (4) to integrate WMNs with existing networks by supporting legacy nodes and providing network management using new tools that easy their deployment and maintenance. WMN have a wide range of applications [2]: broadband home networking, community and neighborhood networking, enterprise networking, metropolitan area networks, transportation systems, building automation, health and medical systems, security surveillance systems, spontaneous (Emergency and Disaster) networking, and P2P communications. These applications have different constraints regarding costs, capacity, reliability, security, ease of use, and interoperability with legacy systems. 1.1 Problem characterization 1.1.1 Motivation This work addresses three scenarios where WMN can be used: extend the Internet coverage, form the last mile of smart grid networks, and form the last mile of surveillance systems. In these scenarios, there are a set of gateways connected with wires to a infra-structured network, a set of WMN nodes that connect to the gateways through multiple wireless links, and a set of devices that are receiving or generating data flows towards the infra-structured network and that are connected to the WMN nodes through a single hop. Internet coverage extension to areas where infra-structured connections to IEEE 802.11 access points are difficult to deploy or expensive. When providing coverage to homes or to rural areas on developing countries, the deployment cost is a relevant constraint and a low cost solution should be envisioned. WMNs can be used to achieve this goal as represented in Fig. 1.1 which is similar to the scenario addressed by IEEE 802.11s [1]. In this scenario, WMN nodes named Mesh Access Points (MAPs) are expected to have two 4Introduction wireless cards with independent radio interfaces running the standard MAC 802.11 protocol. One radio interface operates as an access point giving Internet access to end-users which may be people or smart objects; the other radio interface is used to interconnect the MAP to others MAPs in order to form a multi-hop wireless network. WMNs connect to the infra-structured wire network via special nodes acting as gateways to the Internet. Internet Figure 1.1: WMN scenario deployed to extend Internet access. Last mile smart grid networks aim to connect thousands of smart meters installed in homes and business places to a distribution point of gas, electrical energy or watter suppliers. In order to provide national wide deployment, thousands of distribution points must be equipped and, therefore, a low cost solution should be envisioned. WMNs can be used to meet this goal as represented in Fig. 1.2. In this scenario WMN nodes are expected to have two wireless cards with independent radio interfaces running the standard MAC 802.11 protocol. One radio interface operates as an access point to connect the smart meters to the smart grid. The second radio interface is used to interconnect the WMN node to other WMN nodes in order to form a multi-hop wireless network. Special nodes located at the supplier distribution points act as gateways to connect the WMN to the supplier infrastructure. Last mile surveillance systems aim to connect hundreds of cameras or other sensors installed in buildings or parking lots to the security office. The usage of wires on this scenario can be costly 1.1 Problem characterization 5 Smart grid smart meters Figure 1.2: WMN used as the last mile of smart grid networks. and complex. WMNs can be used to achieve this goal as represented in Fig. 1.3. In this scenario, WMN nodes are expected to have attached a couple of cameras and one radio interface card running the standard MAC 802.11 protocol. Each WMN node connects to other WMN nodes on the neighborhood through the radio card, forming a multi-hop network. It is assumed that this WMN is connected to multiple gateways which are aggregation points located at each corridor, hall, or floor wired connected to the security office. Security office Figure 1.3: WMN used as the last mile of surveillance systems. The three scenarios highlighted above have two main constraints in common: the demand for broadband which must be distributed fairly to all the nodes involved, and the low cost of the WMN node. The demand for fair broadband is obvious on the Internet coverage extension scenario. In this case, the number of users accessing the Internet through each gateway is assumed to be around a few tens as in the mesh networks defined by the IEEE 802.11s standard Chapter 2 Wireless networks based on CSMA/CA This chapter introduces existing work related to CSMA/CA based wireless networks. In the first part of the chapter ( Section 2.1, Section 2.2, and Section 2.3) we describe the operation of the medium access control protocols of the IEEE 802.11 standard focusing on the CSMA/CA; we also identify the studies that establish the boundaries of capacity of WMNs and the interference models that are used in these studies. In the second part of the chapter (Section 2.4), we present a survey of existing channel assignment methods, particularly those addressing single-radio WMNs; we classify these methods according to their requirements and mode of operation. In the third part of the chapter (Section 2.5), we present a survey that characterizes the relevant topology characteristics of WMNs that can be related to the network performance. Section 2.6 summarizes the chapter. 2.1 IEEE 802.11 medium access control protocols A wireless channel is a broadcast medium. When a node transmits a packet onto the radio channel, the packet reaches all the nodes in the 13 14 Wireless networks based on CSMA/CA transmission range of the sender. If a node receives multiple packets on the same channel at the same time, it cannot properly decode the packets because of interference. In this case, we say that packets have “collided” at the receiver. The major goal of wireless MAC is to ensure that when a node is transmitting, all other interfering nodes are silent. IEEE 802.11 specifies two MAC protocols: the Point Coordination Function (PCF) and the Distributed Coordination Function (DCF) [1]. PCF can only work in infra-structured networks. DCF is the MAC protocol of interest for this work, and it is based on the Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) access method. The basic idea of CSMA/CA to check whether the channel is busy or idle before transmitting a packet. A node implementing CSMA/CA listens to the channel and measures the signal level on the channel. The node transmits a packet only when the signal level on the channel is sufficiently low for a given time duration, implicitly assuming that no other transmission is taking place in the region. CSMA/CA blocks a node from initiating a transmission if another nearby node is transmitting and in its basic form it does not address the well-known hidden terminal problem. Consider the scenario in Figure 2.1(a). When node A is transmitting a packet to node B, node C may not sense the channel as busy. Thus, node C can start transmitting a packet, which results in a collision at node B as shown in Figure 2.1(b) The hidden terminal problem can be particially avoided by let a node reserving the channel before transmitting a packet. This 4-way handshake mechanism is illustrated in Figure 2.2 where a station can reserve the medium for a period of time using the control frames RTS (Request-To-Send), CTS (Clear-To-Send). In topology of Figure 2.1(a), suppose node A has a packet to send to B. Before transmitting the data packet, node A sends RTS to B, which contains the duration of time node A needs to reserve. When node B receives RTS, it replies back by sending a CTS packet, which also includes the duration of time the channel needs to be reserved. All other nodes that receive RTS or CTS defer transmission for the duration specified in the packets. Each node maintains the Network 2.1 IEEE 802.11 medium access control protocols 15 A CB (a) A B C data data data receive data data collision (b) Figure 2.1: The hidden terminal problem. (a) Topology consisting of tree nodes. (b) The time sequence leading to a collision. Allocation Vector (NAV) variable, which records the duration of time the node must defer its transmission. When node C receives CTS from B, it sets up its NAV according to the duration specified in the CTS packet. After exchanging RTS and CTS, node A sends the data frame to node B, and B replies with ACK (Acknowledgement) packet so that node A knows the packet has been successfully received at node B. The effectiveness of the 4-way handshake mechanism is based on the assumption that hidden nodes are within transmission range of receivers. Xu et al. in [34] prove using analytic models that in multi-hop networks, such an assumption cannot hold due to the fact that power needed for interrupting a packet reception is much lower than that of delivering a packet successfully. Thus, the “virtual carrier sensing” implemented by 4-way handshake mechanism cannot prevent all interference as we expect in theory. Physical carrier sensing can complement this in some degree. However, since interference happens at receivers, while physical carrier sensing is detecting transmitters, physical carrier sensing cannot help much, 16 Wireless networks based on CSMA/CA RTS CTS ack ack A B C CTS defer transmission data data data receive data Figure 2.2: Time sequence diagram of the 4-way handshaking mechanism of DCF. unless a very large carrier sensing range is adopted. Similar conclusions were found in [35] using simulation experiments. 2.2 Capacity of wireless networks 2.2.1 General multi-hop wireless networks Gupta and Kumar studied the asymptotic transport capacity in general wireless multi-hop networks [13]. This analysis is based on the assumptions that communications are one-to-one within the wireless network, and sources and destinations are randomly or arbitrarily (optimally) chosen. They show that, if the nodes are randomly placed and the destinations are randomly chosen, then the achievable throughput per node is bounded by ΘW/qnlog(n), where W is the transmission capacity, nis the number of nodes in the network and Θrepresents the asymptotic notation1. They also provide results for arbitrary (optimal) node placement and communication patterns. In this case, the achievable per node throughput become Θ(W/√n). Grossglauser et al. [36] extend the work of Gupta and Kumar [13] and show that the capacity can be improved by the mobility of the nodes which can reduce the number of hops between the 1f(n)∈Θ(g(n)) : fis bounded both above and below by gasymptotically 2.2 Capacity of wireless networks 17 source and the destination and in turn reduce the contention in the network. Further improvements on the obtained capacity bounds can be obtained by introducing relay nodes which do not generate traffic but act as routers to deliver data to the destination as shown by Gastpar et al. [37]. In these configurations, when the number of nodes goes to infinity, a network throughput of O(logn)can be obtained, where Orepresents the asymptotic notation2. 2.2.2 Stub wireless mesh networks Different from traditional ad-hoc network, nodes in stub WMN forward their traffic to gateways, creating hot-spots at gateways. Jun and Sichitiu [38] show that available throughput increases with increase in number of network gateways while available capacity at each node is as low as O(1/n). Per-node throughput of O(1/n)is also achievable in WLANs but it is empirically observed that WMNs achieve a throughput which is often lesser than WLANs. The analysis in [38] is not limited to a specific MAC, but the result can be applied to IEEE 802.11. The concept of bottleneck collision domain is introduced there by defining it as the geographical area of the network that enables an upper bound on the amount of data that can be transmitted in the network. Pathak and Dutta [39] show that WMNs achieve per-node throughput of O(1/δn)where δis a factor dependent on hop-radius of the network and it converges to 3 for large WMNs. It is shown that in case of multiple gateways, increasing power levels of nodes is more cost-effective because it results into increased throughput with fewer number of gateways. For arbitrary networks where node locations and traffic patterns can be controlled, each interface capable of selecting appropriate transmission power, Kyasanur and Vaidya [11] prove that there is a loss of network capacity when the number of interfaces per node is smaller than the number of channels. In random networks where, node locations and traffic patterns are random, it is shown that 2f(n)∈O(g(n)) : fis bounded above by g(up to constant factor) asymptotically 18 Wireless networks based on CSMA/CA one single interface is sufficient for utilizing multiple channels as long as the number of channels is scaled to O(logn)and each channel has bandwidth of W/c. Bhandari and Vaidya of [40] extend the work in [11] to multi-channel networks with channel switching constraints. They study connectivity and capacity of a wireless network comprising nrandomly deployed nodes, equipped with a single interface each, when there are c=O(logn)channels of equal bandwidth W/c are available; it considers adjacent channel assignment and the random channel assignment. In adjacent assignment, a node may switch between fadjacent channels, but the adjacent channel block is randomly assigned; in such case, per-flow capacity of ΘWrf cnlogncan be achieved. In random assignment, a node can switch between fixed random subset of fchannels; in such case, per-flow capacity is OWrPrnd nlognand ΩWrf cnlogn, where Prnd = 1 −Qf−1 i=0 1−f c−i, and Ωrepresents the asymptotic notation3. Scenarios where traffic is mostly generated towards gateway nodes result in many-to-one communications. The capacity of wireless networks in many-to-one scenarios for the Wireless Sensor Networks (WSN) applications was studied by Duarte-Melo et al [41]. The trivial upper bound per node is presented as W/n which can be achieved when the gateway is 100% busy in receiving, equipped with a single radio and shared by nsource nodes each of which generating the same amount of data. They further show the circumstances under which this bound is achievable. For instance it is achieved when all the sources can transmit directly to the gateway node. On the other hand, if each source cannot directly communicate with the gateway, such that the communication takes place on a multi-hop network, the upper ground may or may not be achieved depending on the transmission and interference ranges of the nodes. These ranges affect the reuse possibilities of the medium and the transmitting schedules. 3f(n)∈Ω(g(n)) : fis bounded below by g(up to constant factor) asymptotically 2.3 Interference models 19 2.3 Interference models One of the major challenges of improving the capacity of wireless networks is tractable yet realistic consideration of interference. Wireless medium is a shared, broadcast medium. When simultaneous transmissions are performed on the same channel in the same spatial domain, all the unwanted transmissions can be seen as interference. If the transmissions do not interfere with each other, simultaneous transmissions can take place. A collision occurs if the received signal is too weak compared to the interfering signals. The nature and impact of interference is unpredictable and challenges the design of wireless networks. Researchers have proposed several interference models. We discuss the most important ones. Protocol interference model [13] defines that communication between nodes aand bresults in collision-free data reception at node bif no other node within a certain interference range from bis transmitting simultaneously. This model has been further extended to consider link layer reliability using acknowledgments in which interference range of node ais also considered for interference. This is often referred as disk model (or double disk model) where interference is assumed to be a binary phenomena developed in certain fixed distance from the source and the destination of any active link. The Interference range of a node is often assumed to be a constant times larger than its communication range. The advantage of the protocol interference model is that it enables the use of simple graph-coloring based scheduling algorithms. The performance of the protocol interference model is analyzed in [42]. This study indicates that the model does not always provide a comprehensive view of reality due to the aggregate effect of interference in wireless networks. The model can also be pessimistic in the sense that two nearby communications that could take place together with a tolerable level of interference are considered to be not possible. The real behavior of complete 802.11 DCF is captured in [43] where the 20 Wireless networks based on CSMA/CA 4-way handshake mechanism is considered but, its application results in NP hard problems. Physical interference model [13] defines that communication between nodes aand bresults in collision-free data reception at node bif SINR (Signal to Interference plus Noise Ratio) at node bis above a certain threshold β. If Pba is the signal power received at node bfrom a, a packet from node ais successfully received at node bif and only if Pba N+Pi∈IPbi ≥β, where Iis a set of nodes simultaneously transmitting and N is the background noise. Physical interference model is richer than the protocol model because it can capture the interference from multiple simultaneous senders, yet it introduces more complexity on the protocol design. The impact of the physical interference model on the achievable capacity in CSMA/CA based wireless multihop networks is studied in [44]. This study shows that wireless networks designed with the physical interference model can surpass theoretically achievable performance of solutions using the protocol interference model. k-hop interference model [45] defines that no two links within k hops can successfully transmit at the same time. IEEE 802.11 DCF corresponds to a 2-hop interference model. For a given k, a throughput-optimal scheduler needs to solve a maximum weighted matching problem subject to the k-hop interference constraints. The authors [45] show that for k > 1, the resulting problems are NP-Hard and cannot be approximated within a factor that grows polynomially with the number of nodes The above mentioned interference models can be further generalized by representing the interference relationship of links using a conflict graph. In a conflict graph, every link in the network is represented as a vertex and two vertex share an edge if and only if the corresponding edges interfere with each other. Depending on interference model, the resultant conflict graph can be undirected (protocol model or k-hop interference model) or directed (physical interference model). 2.4 Multi-channel WMNs 21 2.4 Multi-channel WMNs We consider to use multiple channels to reduce the effects of interference on the capacity of WMNs. The use of multi-channel communication in multi-hop networks is a research topic for over 30 years, particularly in PRNet [46, 47], in WMN [15, 48, 49, 50, 51] and in WSN [14, 52]. Kyasanur et al. [11] and Kodialam et al. [12], study the capacity of multi-channel WMNs by extending the analysis of Gupta and Kumar [13], that we discussed in Section 2.2. They investigate the impact of the number of channels and the number of radio interfaces on the network capacity by studying the relationship between them. They show that, even if the number of interfaces is smaller than the number of available channels, multi-channel communication can enhance the network’s capacity. The objective of most of the assignment strategies for WMNs studied in the past few years ([14, 15]) was to minimize the overall network interference which is calculated based on topology and traffic information. Most of the approaches address the scenario of WMNs with multi-radio nodes ([53, 16, 17, 18]) which are not suitable for the single-radio scenario we aim to address. In the next sub-sections, we survey the existing protocols on channel assignment and multi-channel MAC protocols for WMN focusing on the case of single-radio WMNs. We classify the protocols according to the channel assignment methods: static assignment and dynamic assignment. In dynamic approaches, nodes can dynamically switch their interfaces from one channel to another between successive data transmissions. Considering the operation principle of the coordination mechanisms, dynamic approaches for single-radio networks can be classified into Receiver-fixed [46, 20], Dedicated Control Channel [54, 55], Frequency Hopping [56, 57, 21, 58], and Split Phase [20, 19, 59, 60]. In static assignment approaches, channels are assigned to radios for permanent use on a per-flow [22, 23] or percomponent basis [24]. 28 Wireless networks based on CSMA/CA A C D E F data source data sink B (a) Chain network topology with a single flow RTS/CTS CTS data1 ack ack RTS/CTS CTS data1 ack RTS RTS/CTS CTS data1 ack 1 s t time slot 2 n d time slot 3 r d time slot A B C D E RTS 4 t h time slot F RTS/CTS CTS data1 ack RTS RTS/CTS CTS data1 ack ack (b) Frame transmission when carrier sense range is equal to the receiving range. RTS/CTS CTS data1 ack ack RTS/CTS CTS data1 ack RTS RTS/CTS CTS data1 ack 1 s t time slot 2 n d time slot 3 r d time slot A B C D E RTS 4 t h time slot F RTS/CTS CTS data1 ack RTS RTS NAV is set on B. B does not reply to RTS. RTS/CTS CTS data1 ack ack 5 t h time slot RTS/CTS data1 ack RTS (c) Frame transmission when carrier sense range is the double of receiving range Figure 2.3: Scenario and message sequence charts used to derive the maximum achievable data rate for a single flow on a chain topology. If 3 hops are involved, the final data rate of the network is not expected to be more than 1/3of the channel capacity. This capacity upper bound can be derived from the message sequence chart shown in Figure 2.3, considering an ideal scheduling. Figure 2.3(b) shows a message sequence chart of a multi-hop communication when the carrier sense range is equal to the receiving range. On the first time slot the first frame is transmitted from Node A to Node B. On the second time slot, while Node B forwards 2.5 Topology characteristics 29 the frame to Node C, Node A senses the medium as being busy and defers the transmission of the second frame. On the third time slot, Node C transmits the frame to Node D. At the same slot Node A senses the medium as free and sends a RTS, but Node B senses the medium as busy and does not respond with CTS. On the fourth time slot two simultaneous communications are possible, Node D transmits the first frame to Node E and Node A transmits the second frame to Node B. This example shows that each hop can only transmit every 3 other time slot, leading the network throughput to 1/3of the channel capacity, independently of the chain length. Figure 2.3(c) shows the same scenario when the carrier sense range that is the double of the receiving range. In this case, the second packet is transmitted on the fifth time slot as, until then, Node B senses the medium occupied and does not respond to the RTS message. This leads to a network throughput that is 1/4of the channel capacity. For a non ideal scheduling, a throughput of 1/5of channel data rate has been reported in [62] when the carrier sense range doubles the receiving range. In [63], simulation results shown that the chain network throughput is 1/7of the single-hop throughput for this network topology. For chain networks such as those represented in Figure 2.3(a) it is possible to demonstrate that the length of the chain does not affect the maximum achievable throughput when a single flow is using the network; however, when several sources are used, the length of the chain influences the maximum achievable throughput. The concept of bottleneck collision domain is introduced by [38] (see Section 2.2) enables the derivation of the impact the mean number of hops Hhas in a given network, when all nodes are sources of flows with the same packet rate of λpacket/s destined to a common sink. The mean number of hops Htraversed by a packet in the network of Figure 2.4(a) is given by Eq. 2.1, where Nindicates the number of nodes in the network. H=1 N N X n=1 n= (N+1)/2(2.1) The bottleneck collision domain of the network of Figure 2.4(a) is 30 Wireless networks based on CSMA/CA λ λ(N−5)∙λN∙λ(N−2)∙λ ….. (N−1)∙λ(N−3)∙λ(N−4)∙λ λλλλλλλ 123456N-1N GW (a) Chain Topology with Nflows 3 5.5 Hop Count Average ( H) 1/3 1/4 1/5 Normalized Maximum Network Throughput (T/W) (b) Maximum network throughput Tas a function of mean hop count Hfor a given channel data rate W Figure 2.4: Chain topology with Nhops and the throughput upper bound for this topology. the collision domain of link 2-3 composed by links {GW-1, 1-2, 2-3, 3-4, 4-5} [38]. Each collision domain has to forward the sum of the traffic of its links. In this case, the collision domain of link 2-3 has to forward λ·[(N−4)+(N−3)+(N−2)+(N−1)+N] = λ·(5N−10). The collision domain cannot forward more traffic than the channel data rate W, what means that W≥λ·(5N−10). Therefore, the maximum throughput available for each node is λmax =W/(5N− 10) and the maximum network throughput Tis given by Eq. 2.2, where N= 2H−1comes from Eq. 2.1. T≤Nλmax ≤N·W 5N−10 =W(2H−1) 5(2H−1)−10 =W(2H−1) 10H−15 (2.2) Figure 2.4(b) represents a plot of Eq. 2.2. The global throughput Tdecreases with the mean number of hops on a chain but it is lower bounded by W/5. 2.5 Topology characteristics 31 Let us consider now topology of Figure 2.5(a), that combine a chain of Ncnodes and a star of N−Ncnodes. When Nc= 0 the network has star topology (Figure 2.5(f)); when Nc=N−1the network is a chain topology (Figure 2.5(b)). All the topologies present the same number of nodes N= 8 but different mean hop count H. In this case, the mean hop Count His given by Eq. 2.3, where the first addend refers to the Ncnodes on the chain part of the network, and the second addend refers to the N−Ncnodes on the star part of the network. H=PNc n=1 n+[(N−Nc)·(Nc+1)] N =(Nc+1)(N−Nc/2) N(2.3) When Nc≤4, all links are on the same collision domain [38]; the traffic on this collision domain is the traffic on links on the star part of the network given by λ(N−Nc)and the traffic on the chain part of the network given by λPNc−1 n=0 (N−n). The collision domain cannot transport more traffic than the channel data rate W, as presented by Eq. 2.4 W≥λ(N−Nc)+λ Nc−1 X n=0 (N−n) ≥λN (Nc+1)(N−Nc/2) N), Nc≤4(2.4) By using Hfrom Eq. 2.3 in Eq. 2.4 it is possible to obtain W≥ λNH for Nc≤4. Therefore, the maximum throughput available for each node is λmax =W/(NH)and the upper bound of network throughput T=Nλmax is given by Eq. 2.5. T≤W H, Nc≤4(2.5) When Nc>4, the bottleneck collision domain on star-chain networks of Figure 2.5 is the collision domain of link 2-3 composed by links {GW-1, 1-2, 2-3, 3-4, 4-5} [38]. Each collision domain has to forward the sum of the traffic of its links. In this case, the collision domain of link 2-3 has to forward λ·[(N−4)+(N−3)+(N− 2)+ (N−1)+ N] = λ·(5N−10). The collision domain cannot for- 32 Wireless networks based on CSMA/CA λ N∙λ(N−2)∙λ(N−1)∙λ(N−3)∙λ(N−Nc)∙λ λλλ 1234Nc ….. λ Nc+1 λ λ N N−1 λ λ ….. GW (a) Star chain topology with Nflows λ λ3λ8λ6λ7λ5λ4λ λλλλλλλ 12345678 GW 2λ (b) Nc= 7,H= 4.5 λ 8λ6λ7λ5λ4λ λλλ 12345 λ 6 λ λ 8 7 λ λ ….. GW (c) Nc= 5,H= 4.125 5λ λ λ λ λ λ 8λ 7λ λ 13 λ λ λ λ6 7 8 5 GW λ 4 λ 6λ 2 (d) Nc= 4,H= 3.75 λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ 5 6 2 7 3 8 4 8λ 1GW (e) Nc= 1,H= 1.875 λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ 4 5 1 6 2 7 3 λ 8 GW (f) Nc= 0,H= 1 012345 Mean Hop Count ( H) 1 1/2 1/3 1/5 Normalized Maximum Network Throughput (T/W) Nc=0 Nc=1 Nc=2 Nc=3 Nc=4 Nc=5 Nc=7 (g) Maximum network throughput Tas a function of mean hop count Hfor a given channel data rate W Figure 2.5: Topologies combining a chain of Ncnodes and a star of N−Ncnodes and the upper bound of the throughput this topology as a function of the mean hop count. 2.5 Topology characteristics 33 ward more traffic than the channel data rate W, what means that W≥λ·(5N−10). Therefore, the maximum throughput available for each node is λmax =W/(5N−10) and the upper bound of network throughput T=N·λmax is given by Eq. 2.6. T≤WN 5N−10, Nc>4(2.6) The maximum achievable throughput given by Eq. 2.5 and Eq. 2.6 is represented in the lower part of Figure 2.5 as a function of Hfor N=∞; this graph shows that, for these topologies, the maximum achievable throughput Ttends to the inverse of H. However, Tdoes not always vary with H; for H≥5, which corresponds to Nc≥4, T is fixed to W/5. Therefore, the inference of the maximum achievable throughput is not possible for a generic network by just knowing H. 2.5.1.1 Discussion Two simple topologies were studied relating the mean hop count and an upper bound of the network throughput calculated as in [38]. In both examples, it was shown that when the mean hop count is not too small, i.e. H > 6, the influence of the mean hop count on network throughput is negligible. In [13] the authors proved that the amount of traffic λgenerated by each node that can be transmitted through the network is inversely proportional to the mean number of hops Hof the network. The number of MAC transmissions generated by each flow is given by Hλ. With a total number of Nnodes, the total offered traffic becomes Tn=HλN. In ideal conditions, the offered traffic has to be served by Nnodes each capable of transmitting W, thus HλN ≤NW. An upper bound of the throughput per node is λmax =W/H. However, a closer upper bound can be found if constraints such as spacial concurrency were introduced. 2.5.2 Neighbor node density Neighbor node density is defined as the mean number of nodes in the carrier sensing range of each node in the network. Assuming a CSMA/CA MAC, the higher the number of active nodes is 34 Wireless networks based on CSMA/CA in a region the less will be the throughput per node due to contention. Consider the network topology on Figure 2.6 containing N= 6 nodes. The lines represent links between nodes; if a line is not represented between two nodes, these nodes cannot sense each other’s transmissions. Each node generates a data flow destined to Node F which is the gateway of this network. Data is transmitted through the paths defined by the links represented by lines with arrows. The neighbor node density dis calculated as the mean number of neighbors a node has. In this case we have nodes A, B, E and F with 2 neighbors, and nodes C and D with 3 neighbors, thus the neighbor node density for Figure 2.6 is d= [(4×2)+ (2×3)]/6nodes= 2.33. A C E B D F Figure 2.6: Sample topology used to discuss the topology metrics of a network. Assuming the protocol interference model, the throughput λobtainable by a node is shown [13] to decrease with the increase of the neighbor node density and given by λ= ΘW/(√nlogn)[13] where Wis the channel capacity and nis the number of nodes in the network. Consider now the topologies of Figure 2.7, all of them containing N= 12 nodes. The lines represent wireless links between nodes; if a line is not represented between two nodes, these nodes cannot sense each other’s transmissions. Each node generates a data flow of λ packet/s destined to the gateway. Data is transmitted through the paths defined by the links represented by lines with arrows. Paths are the same on all topologies, therefore the mean hop count is H= 2.5for the 9 topologies presented. The label of a link indicates the amount of traffic transported by that link. Stronger lines indicates the bottleneck collision domains calculated as in [38]. The neighbor node density dis calculated as the mean number of neighbors a node has in the network. Each topology presents a different neighbor set for each node by adding new links to the base 2.5 Topology characteristics 35 4λ 3λ 4λ 4λ λ λ λ2λ 2λ 2λ3λ 3λ GW (a) d= 1.75 4λ 3λ 4λ 4λ λ λ λ2λ 2λ 2λ3λ 3λ GW (b) d= 1,92 4λ 4λ λ 3λ λ λ2λ 2λ 2λ3λ 3λ 4λGW (c) d= 2.08 4λ 4λ λ 3λ λ λ2λ 2λ 2λ3λ 3λ 4λGW (d) d= 2.25 4λ 4λ λ 3λ λ λ2λ 2λ 2λ3λ 3λ 4λGW (e) d= 2.42 GW 4λ 4λ λ 3λ λ λ2λ 2λ 2λ3λ 3λ 4λ A E I B F J C G K D H L (f) d= 2.75 4λ 4λ λ 3λ λ λ2λ 2λ 2λ3λ 3λ 4λGW (g) d= 2.92 4λ 4λ λ 3λ λ λ2λ 2λ 2λ3λ 3λ 4λGW (h) d= 3.08 λ λ λ 4λ 4λ 3λ 2λ 2λ 2λ3λ 3λ 4λGW (i) d= 3.75 2.0 2.5 3.0 3.5 4.0 Neighbor Node Density ( d) 12/22 12/23 12/24 12/25 12/26 12/27 12/28 12/29 12/30 Normalized Maximum Network Throughput (T/W) (a) (b) (c) (d) (e) (f) (g) (h) (i) (j) Figure 2.7: Throughput upper bound of a set of scenarios plotted as a function of the neighbour node density of those scenarios. network topology of Figure 2.7(a), thus originating different node densities. The maximum achievable throughput for these scenarios is calculated according to the model presented in [38] described earlier. The link found as the bottleneck collision domain of each topology is represented by a red strong line and the links not belonging to that collision domain are represented in gray. For instance, the bottleneck collision domain of the network on Figure 2.7(f) is the col- 36 Wireless networks based on CSMA/CA lision domain of the link G-H composed by links {D-GW, H-GW, L-GW, C-D, G-H, K-L, B-C, F-G, J-K, E-F} [38]. This collision domain has to forward the sum of the traffic of its links which is (4+4+4+3+3+3+2+2+2+1)λ= 28λ. The collision domain cannot forward more traffic than the channel data rate Wwhat implies that 28λ≤W. Therefore, the maximum throughput available to each node is λmax =W/28 and the maximum network throughput is T=Nλmax = 12W/28, considering that N= 12. The maximum achievable throughputs of topologies represented in Figure 2.7(a) to Figure 2.7(i) are plotted in Figure 2.7(j) as a function of the calculated neighbor node density d. This graph shows that, for these topologies, the maximum achievable throughput T tends to be the inverse of d. However, Tdoes not always vary with d. As shown by these topologies, in general it is difficult to infer maximum achievable throughput by just knowing the neighbor node density d. In [64], Kuo et al. prove that the throughput of a node λis asymptotically defined as a function f(d)of node density dgiven by Eq. 2.7, where cis a constant, and represented in Figure 2.8. λ= Θ(f(d)), f(d) = 1−(d−1e−d/c) d(2.7) 12345 Neighbor Node density ( d) 0.2 0.3 0.4 Function of the same order of Node Throughput - f(d) f(d) = 1−(d−1e−d/c) d Figure 2.8: Asymptotic boundary function of per node throughput vs neighbor node density as presented by Kuo et al. Kuo et al. in [64] argue that f(d)is a trade-off between hop progress on the numerator and contention on the denominator. The numerator 1−(d−1e−d/c)shows that the throughput increases with the neighbor node density; when a node has a large number of neighbors, the probability that the next node on the multi-hop path is 2.5 Topology characteristics 37 closer to the destination increases, and so does the hop progress. As a result, a large neighbor node density dleads to a smaller path hop count for each flow, which in turn reduces the traffic to be relayed by the network. The denominator shows that a large neighbor node density also introduces more contentions in the access to the wireless channel by the nodes in the receiving range. When dis small, the hop progress is more important than the contention effect; when dgrows, the contention dominates. The study in [64] does not consider collisions caused by hidden nodes nor simultaneous transmissions both highly related with neighbor node density. The works reported in [65, 66, 67] address these problems. Packet collisions due to simultaneous transmissions are expected to increase with the increase of neighbor node density since it is more likely that two or more nodes of a neighborhood transmit at the same time slot. However, collisions due to hidden nodes can decrease when the neighbor node density increases since the number of hidden nodes can also decrease, what implies that for some topologies the throughput can increase when neighbor node density is high. 2.5.3 Hidden nodes The hidden node problem is partially solved by the RTS/CTS mechanism of IEEE 802.11 on wireless local area networks. However in multi-hop networks it is proved [68] that hidden mesh nodes cause severe problems on network performance even when the RTS/CTS mechanism is used, since it does not solve the mesh hidden node problem and it increases the network overhead, leading to performance degradation. For a given topology, the mean number of hidden nodes can be measured by averaging the number of hidden nodes of each active link in the network. The number of hidden nodes of a link is the number of neighbors of the link’s receiver that are not neighbors of the link’s transmitter. For instance, on Figure 2.6 there are 5 active links, which are the links used to transmit data, represented by arrows. Node D is hidden from link A-B, C and F are hidden from B-D, F is hidden from C-E, E is hidden from D-F, and D is 44 Identification of relevant topology metrics discusses the impact of the mean hop count metric on the network throughput. Section 3.4 describes the impact that the neighbor node density and the gateways position have on the network throughput using a single channel scenario. Section 3.5 investigates the impact that topology metrics related to the gateway neighborhood have on throughput. Section 3.6 presents a summary of this study. 3.1 Methodology We investigate the impact of the topology of a network on its performance, by means of extensive simulation analysis. We defined a lattice topology and simulated 18 dual-channel arbitrary deployments. The 18 arbitrary channel assignment scenarios were applied to a 36 node network displaced in a 6x6 lattice topology disposed in an area of 1000 m×1000 m, as represented on Figure 3.1. The number inside a circle identifies the node. The lines represent wireless link layer connectivity; horizontal and vertical links (e.g. 1-2 or 1-7) measure 176 m and diagonal links (e.g. 1-8) measure 249 m. On figures of next sections (Figure 3.2 to Figure 3.13), the squares represent the gateways that have a wired connection to the Internet. Dark circles in these figures represent nodes configured on a channel, and light circles represent nodes on an orthogonal channel; these two networks are interconnected through their gateways. 12 5 3 15 18 16 6 4 9 8 1 13 142 7 1711 24 22 23 21 29 27 30 36 34 35 33 20 19 26 25 32 31 2810 Figure 3.1: 6x6 lattice used to study the impact of topology characteristics on the network throughput. 3.1 Methodology 45 The two channel assignment schemes A1 and A2 represented in Figure 3.2, along with a single channel scenario (A-SCh), were used as the base scenarios to study the impact of the topology characteristics on network throughput. Scenarios B1 and B2 of Figure 3.8, based on A1 and A2 but with fewer nodes, were simulated to study the effect of hop count. Scenarios C1, C2 and C-SCh of Figure 3.9, based on A1 and A2 with larger carrier sensing range, were used to study the neighbor node density. Scenarios D1, D2 and D-SCh of Figure 3.10, based on A1, A2 and A-SCh with gateways positioned on the center of the network, were used to understand the impact of the gateways position. Scenarios E1, E2, E3 and E4 of Figure 3.12 and scenarios A3, A4 and A5 of Figure 3.13 were used to study the impact of the gateway neighborhood in terms of neighbor node density and hidden nodes. 3.1.1 Simulator parameters The parameters used in simulation are presented on the Table 5.3. The simulation tool ns-2 was used with two-ray propagation model in the physical layer, and MAC DCF 802.11 in the link layer. The Hybrid Wireless Mesh Protocol (HWMP) [1, 71] was used to establish routes since it is defined in the IEEE standard to WMNs [72]. RTS/CTS handshake was also used and the Carrier Sense Threshold (CSThresh) was configured to guarantee a carrier sensing range of 350 m. 3.1.2 Traffic flows Each node generates a User Datagram Protocol (UDP) flow towards the gateway, so 17 flows were simulated on each channel on all scenarios except the single channel scenario with 34 flows on a single channel, and scenarios B1 and B2 which have 13 flows on each channel. A set of simulations was carried out. In each simulation all flows generated the same bit rate. Flow’s bit rates from 10kbit/s to 7.5Mbit/s were used. Flow packets are generated by a Poisson process without bursts, characterized by exponentially distributed 46 Identification of relevant topology metrics Parameter Value Propagation Model Two ray ground Channel data rate 11 Mbit/s Receiving Threshold -70.2 dBm, 350 m Node distance 176 m Main flow packet size 1500 bytes RTS/CTS ON Max. retransmission retries 7 Routing protocol HWMP Flow source type Poisson (UDP) WarmUp flow packet size 256 byte WarmUp flow data rate 10 packet/s Simulation runs 10 Table 3.1: Parameter values used in ns-2.29 simulations of networks with lattice topology. inter-arrival times. Poisson process was selected to avoid simultaneity problems caused by other simpler approaches such as Constant Bit Rate (CBR). All flows are configured with similar parameters, which are fixed for each simulation; each simulation was run with 10 different seeds. Simulations run for 60 seconds, what may imply the generation of 37500 packets. During the first 3 seconds there are no data flows; this period is used to allow the HWMP routing protocol to execute the proactive tree building functionality; in this phase a route to one of the gateways is added to each node as described in the proactive Path Request (PREQ) mechanism [1]. The expiration period of routes and routing messages are set to be larger than the simulation run. This option avoids the exchange of routing messages during the main flows simulation which cause avoidable overhead and also avoids the hop count shift problem described in [73]. Between second 3 and second 4 the warm up flow takes place between each node and the gateway; this flow enables the Address Resolution Protocol (ARP) tables of each node to be filled. On second 5, the main flows start and go on until second 50. The last 10 seconds of each simulation are used to enable packets to be 3.1 Methodology 47 dequeued. 3.1.3 Queuing model Preliminary experiences with the topologies of Figure 3.2 showed that the simulated scenarios exhibited serious fairness problems; for medium to high loads, only the nodes directly connected to the gateway could transmit their packets to the destination. This problem occurred because the queue of each node started to be filled by packets originated by the node’s flow, and the packets received by downstream neighbors were dropped because there were no available buffers on the queue. This is an well identified and solved problem in the literature, as described in [74] and then in [75]. In our study a solution based on [75] was used where each node shares evenly the available queue among all the flows that are being forwarded by a node, including the node’s flow. In practice, a different queue was created for each flow and these queues were served by a single server using a round robin strategy. Using this approach we could guarantee that all flows have the same chance to transmit their packets at each hop of the path and we could focus on the main objective of the study which consists in analyzing the impact of topology characteristics on the network throughput. The queue size used in this study was 50 packets. So a node forwarding N−1flows plus its own generated flow, is able to accommodate N×50 packets. The Nqueues are, as said, served in round robin. In order to guarantee that these values do not affect the simulation results, we carried out simulations with smaller queue size (3 packets) and with infinite queues (200000 packets); results obtained showed that the queue size does not affect the network throughput. 3.1.4 Measuring network metrics To calculate the network topology and performance metrics, the two sub-networks resultant from the channel assignment are treated as a single network. The metrics aggregate the performance and the topology characteristics of all nodes in the network, independently 48 Identification of relevant topology metrics of the channel each node is configured in. Metrics are calculated by analyzing the trace files generated by ns-2 using python scripts and the graphs presented were created using matplotlib python library. The performance metrics considered are the per-hop throughput and the end-to-end throughput. The per-hop throughput is defined as the mean bit rate of each data link in the network and is calculated as the total number of MAC frames successfully transmitted on the links of the network divided by the number of active links on the network which is 34 in these scenarios; non acknowledged frames are not considered. The end-to-end throughput of the network is defined as the sum of the bit rate received by the two gateways, divided by the number of sources of the network which is 34, except for scenarios B1 and B2. 3.2 Basic scenarios Scenario A-SCh Scenario A1 Scenario A2 Figure 3.2: The channel assignment scheme used in A1 minimizes the number of hops to the gateway. The scheme used in A2 aims to reduce the number of contending neighbors. In the single channel scheme, A-SCh, the two gateways and the rest of the nodes are on the same channel. Figure 3.3 shows the throughput and topology characteristics of the two scenarios represented in Figure 3.2, and compares it with a third scenario (Scenario A-SCh) where all nodes and gateways of Figure 3.1 work in a common channel. Figure 3.3(a) presents the per-hop throughput. For each source node debit, Figure 3.3(b) presents the mean of end-to-end throughput and the 90% confidence interval calculated using the results of the 10 simulations runs. Topology characteristics of these scenarios are presented on 3.2 Basic scenarios 49 Figure 3.3(c), and they were calculated as explained on Chapter 2; the 90% confidence intervals of the topology metrics are also shown and indicate that the values shown are very accurate. The results on Figure 3.3 are compared with results from simulations with variants of scenarios A1 and A2 and discussed in the following subsections. 0.01 0.1 1 10 Source node debit (Mbit/s) 0.00 0.25 0.50 0.75 Per-hop throughput (Mbit/s) Scenario A-SCh Scenario A1 Scenario A2 (a) 0.01 0.1 1 10 Source node debit (Mbit/s) 0 50 100 150 200 Throughput (kbit/s) Scenario A-SCh Scenario A1 Scenario A2 (b) Mean Hop Count Neigh Node Density Mean Hidden Nodes missratio (x10) 0 1 2 3 4 5 6 7 Topology Metrics Scenario A-SCh Scenario A1 Scenario A2 (c) Figure 3.3: (a) per-hop throughput (b) end-to-end throughput and (c) topology metrics of two dual-channel and one single channel assignment schemes presented on Figure 3.2. The 90% confidence intervals of the throughputs and topology metrics are also shown. 50 Identification of relevant topology metrics 3.2.1 Impact of traffic conditions Estimate network capacity IEEE 802.11’s theoretical data rate for each gateway is 11Mbit/s, but more than 50% [76] of it is used in overhead, leaving 5.5Mbit/s per gateway available to transmit packets from 34 flows. The maximum mean data rate for each flow is 5.5Mbit/s×2gateways/ 34nodes = 323kbit/s. Considering that each frame is forwarded through multiple hops until it reaches the gateway, the maximum achievable end-to-end throughput is even lower. Therefore, it is expectable that a considerable amount of frames are lost when the sources debit is above 0.3Mbit/s. Low load traffic conditions Low load traffic conditions are assumed when each source generates less than 120kbit/s. In these conditions every channel assignment scheme, including the single channel, presents the same end-to-end throughput results. In low load traffic conditions, all the packets are delivered to the destination without noticeable losses, independently of the scenario used; Figure 3.3(b) proves this by showing that for debits below 120kbit/s, the end-to-end throughput is equal to the source debits. The perhop throughput graph of Figure 3.3(a) shows that the number of MAC transmissions in these conditions correspond to the number of packets received by the gateways multiplied by the number of hops of the paths followed by packets whose values are shown in Figure 3.3(c). The mean path length in Scenario A1 and in single channel scenario is 1.7, while Scenario A2 has a mean path length of 2.41. When the throughput is 120 kbit/s, which occurs when the individual source debit is 120 kbit/s, the amount of data generated by each flow along its path is 1.7×120kbit/s = 200kbit/s in the case of Scenario A1, and 2.41×120kbit/s = 290kbit/s for Scenario A2. High traffic load conditions When the traffic load is higher than 120kbit/s, the end-to-end throughput starts growing slowly, in opposition to the linear growing for low loads. The networks start to lose packets and the differences of performance between the 3.2 Basic scenarios 51 topologies start to be evident. When each individual source generates more than 3Mbit/s, the end-to-end throughput stops growing indicating that the network is near its saturation point. 3.2.2 End-to-end and per-hop throughputs Figure 3.3(b) shows that the maximum end-to-end throughput of Scenario A2 is 127kbit/s for the offered load of 190kbit/s, what suggests the existence of an optimum offered load; the existence of an optimum offered load was also reported in [62] and [63]. For Scenario A1, the end-to-end throughput increases even when it starts to lose significant amounts of data (when each node source debit is higher than 300kbit/s), and it continues to grow with increasing amounts of offered load until it reaches a saturation value of 170kbit/s. The inefficiency of Scenario A2 for high loads is caused by hidden nodes which cause collisions. Despite the mean number of hidden nodes in Scenario A2 being lower than in the other scenarios, as shown by Figure 3.3(c), the neighbor node density is also lower indicating that most of the neighbors are hidden from each other, as revealed by the miss ratio of Scenario A2, which is higher than in Scenario A1. The per-hop throughput shown in Figure 3.3(a) increases with the offered load until reaches the saturation. The saturation values are 520 kbit/s, 800 kbit/s and 460 kbit/s respectively for scenarios A1, A2 and A-SCh. Scenario A2 presents the highest per-hop throughput. There are two reasons for that: 1) the large value of the mean hop count of Scenario A2 observed on Figure 3.3(c); 2) the low neighbor node density on the topology of Scenario A2. 3.2.3 Node density impact on per-hop throughput The per-hop throughput can be easily correlated with the neighbor node density for scenarios A1 and A2 on Figure 3.2. High node density results on low number of frames successfully delivered to the MAC receivers as also shown in Figure 2.7. However, Scenario A2 has high per-hop throughput but low end-to-end throughput which 52 Identification of relevant topology metrics represents the amount of packets actually delivered to the final destination. This apparent contradiction indicates that a substantial part of the frames are lost before reaching the final destination. It is expectable that frames are lost when debits are higher than 0.3 Mbit/s since all flows are destined to the gateway which is the network bottleneck. Scenario A1 Scenario A2 0.0 0.2 0.4 0.6 0.9 1.1 1.3 1.6 1.8 2.0 2.3 MAC sucessfull transmissions (Mbit/s) Figure 3.4: Amount of data transmissions on the networks of scenarios of Figure 3.2 when each node is generating a flow of 3 Mbit/s to a destination on the Internet. The white and black centers of each node represent the gateway used to forward the packets to the Internet. The face color of a node represents the amount of data frames that were successfully sent by that node. Figure 3.4 shows the number of successful MAC transmissions when each node generates a traffic flow of 3 Mbit/s. This load corresponds to the saturation point of Figure 3.3(a). Nodes on the boundary of the network tend to acquire the channel and transmit much more packets than the other nodes on the path towards the gateway. The boundary nodes on both scenarios have few contending neighbors and the CSMA nature of IEEE 802.11 MAC protocol allows them to get the opportunity to transmit more often than subsequent nodes on the path to the gateways which have more contending neighbors. Border nodes transmit more MAC frames then interior nodes despite interior nodes have more frames to transmit, because they have to transmit their own frames and forward the frames coming from downstream neighbors. This effect makes the network inefficient because the packets that were transmitted 3.2 Basic scenarios 53 in the first hops are then dropped near the gateway. Border nodes transmit more MAC frames on Scenario A2 than in Scenario A1 because Scenario A2 has an higher difference between the number of neighbors on border and interior nodes. This is why Scenario A2 is more inefficient than Scenario A1, what confirms the results on Figure 3.3(b). 3.2.4 Analysis of generated packets In our scenarios, the sources generate more packets than those that can be transported by the network. There are four possible destinies for a generated packet: 1) the packet is dropped by the source node because its queue is full; 2) the packet is dropped in an intermediate node because that queue is full if the medium around is congested; 3) the packet is dropped because the maximum number of retries defined by the IEEE 802.11 MAC is exceeded; 4) the packet succeeds if it reaches the gateway. Figure 3.5 quantifies these destinies for Scenario A1 and Scenario A2 of Figure 3.2. 102103104 Source node debit (kbit/s) 102 103 104 Packets generated by sources (kbit/s) Scenario A1 102103104 Source node debit (kbit/s) Scenario A2 Packets dropped in the queue of source nodes Packets dropped in the queue of intermediate nodes Packets dropped for exceeding maximum retry limit Packets delivered to final destination Figure 3.5: Packets generated by sources (1) dropped in the queue by source nodes, (2) dropped in the queue by intermediate nodes, (3) dropped after exceeding the maximum retransmission retries limit, or (4) delivered to the final destination. 60 Identification of relevant topology metrics Scenario C-SCh Scenario C1 Scenario C2 0.01 0.1 1 10 Source node debit (Mbit/s) 0 50 100 150 200 250 Throughput (kbit/s) Scenario A-SCh-350m Scenario A1-350m Scenario A2-350m Scenario C-SCh-550m Scenario C1-550m Scenario C2-550m Mean Hop Count Neigh Node Density Mean Hidden Nodes missratio (x10) 0 5 10 15 Topology Metrics Scenario A-SCh-350m Scenario A1-350m Scenario A2-350m Scenario C-SCh-550m Scenario C1-550m Scenario C2-550m Figure 3.9: Network topology when carrier sense range is 550 m using the same channel schemes of Figure 3.2. When the carrier sense range enables the gateways to sense each other’s transmissions, the single channel scenario (Scenario C-Sch) performance is lower than the Scenario A-Sch. The decrease and increase respectively of hidden nodes from Scenario A1 to Scenario C1 and A2 to C2 justifies the increase and decrease on the end-to-end throughput. 3.5 Gateway neighborhood 61 3.4.2 Gateways position In order to confirm that single channel scenarios, where gateways are placed on the communication range of each other, present worst results than when two channels are used, a new experiment was carried out. The gateways were deployed in positions 15 and 21 (refer to Figure 3.1), as shown in Figure 3.10. The networks of Scenarios D were subjected to the same tests and loads described before. The achieved end-to-end throughputs with the correspondent 90% confidence intervals and the topology metrics are also shown in Figure 3.10. The end-to-end throughput for single channel scenario with centered gateways, Scenario D-Sch on Figure 3.10, is less than half of the end-to-end throughput obtained when the gateways are out of the communication range of each other (Scenario A-Sch on Figure 3.3(b)). In Scenario D-Sch it is possible to have different routing paths on each simulation run. Different routing paths turns out in different miss ratios as shown by the wider confidence interval of miss ratios on Scenario D-Sch presented in the topology metrics graph on Figure 3.10. These variations on miss ratio leads to variations on the end-to-end throughput as shown by the wider confidence intervals of end-to-end throughputs of Scenario D-Sch when compared with Scenario D1 and Scenario D2. 3.5 Gateway neighborhood In a scenario where a WMN is used to extend Internet access, we foresee that gateway position has a great impact on performance of the wireless network. A gateway at a central position leads to short paths; a gateway deployed at the edge of the WMN may lead to a small number of contending nodes around it. In order to characterize the position of the gateway we introduce the concept of ring. The nth ring is the set of nodes located n hops away from the gateway as defined in [77]. The 1st ring seems to be of particular interest, since its nodes share the bottleneck of the network, which is the wireless channel around the gateway. The neighbor node density around the gateway can be measured by 62 Identification of relevant topology metrics Scenario D-SCh Scenario D1 Scenario D2 0.01 0.1 1 10 Source node debit (Mbit/s) 0 50 100 150 200 250 Throughput (kbit/s) Scenario D-SCh Scenario D1 Scenario D2 Mean Hop Count Neigh Node Density Mean Hidden Nodes missratio (x10) 0 1 2 3 4 5 6 7 Topology Metrics Scenario D-SCh Scenario D1 Scenario D2 Figure 3.10: Network topology, end-to-end throughputs with 90% confidence intervals and topology metrics when gateways are deployed in positions 15 and 21 on the center of the network. simply checking the size of the 1st ring, which is the number of nodes at one hop distance to and from the gateway. The hidden nodes of the 1st ring can either be measured by calculating the mean number of hidden nodes of 1st ring links or by calculating the miss ratio of the 1st ring. The 1st ring links are the links between the 1st ring nodes and the gateway. Recall the set of graphs that capture the physical interferences and the carrier sensing constraints between links in a network: ifgraph, tc-graph, and rc-graph described in Section 2.5.3. The 1st ring miss ratio is calculated using IFR1,TCR1and RCR1which 3.5 Gateway neighborhood 63 are respectively the set of edges on if-graph, tc-graph and rc-graph which affect the gateway, as given by Eq. 3.1 missratioR1=NHNR1 |IFR1∪RCR1|(3.1) where NHNR1=TCR1∩(IFR1∪RCR1)is the number of links hidden from 1st ring links. For the network on Figure 3.11(a), the IFR1, TCR1,RCR1, and HNR1are the bold red edges in the graphs of Figure 3.11, |IFR1∪RCR1|= 7 and |HNR1|= 1 thus miss ratioR1= 1/7=0.14. A C E B D F (a) Network graph DF BD EF AB CE (b) if-graph DF BD EF CE AB (c) tc-graph DF BD EF AB CE (d) rc-graph DF AB BD EF CE (e) hidden links Figure 3.11: In the topology of(a), (b) is the if-graph, (c) is the tc-graph, (d) is the rc-graph, and (e) represents the hidden links. The 1st ring edges on these graphs represented as red strong lines. 3.5.1 Size of the gateway neighborhood In order to understand the impact of the characteristics of a gateway neighborhood, scenarios E1, E2, E3 and E4 were simulated. These scenarios, on Figure 3.12, show channel assignment schemes with 1, 2 and 3 nodes around the gateway. Scenarios E1 and E4 are, respectively, based on Scenarios A2 and A1 presented in Figure 3.2, moving the gateways to the corners of the lattice. Scenarios E2 and E3 are variants of Scenario E1 where the gateway neighborhood was modified to get respectively 2 and 3 nodes around the gateway. The networks of Figure 3.12 were offered the same traffic and tests described earlier. The networks end-to-end throughputs with 64 Identification of relevant topology metrics Scenario E1 Scenario E2 Scenario E3 Scenario E4 0.01 0.1 1 10 Source node debit (Mbit/s) 0 50 100 150 200 250 300 Throughput (kbit/s) Scenario E1 Scenario E2 Scenario E3 Scenario E4 MeanHop Count Neigh Node Density Mean Hidden Nodes missratio (x10) 1st Ring missratio (x10) 1st Ring Hidden Nodes 1st Ring Size 0 1 2 3 4 5 6 Topology Metrics Scenario E1 Scenario E2 Scenario E3 Scenario E4 Figure 3.12: Channel assignment schemes with few full connected nodes on the neighborhood of the gateway. End-to-end throughputs with 90% confidence intervals and topology metrics are also presented. 90% confidence intervals and the topology metrics are also presented in Figure 3.12. Results in Figure 3.12 show that end-to-end throughput depends on the 1st ring size which is the neighbor node density around the gateway. The higher is the 1st ring size, the higher is the end-to-end 3.5 Gateway neighborhood 65 throughput obtained. Also, the mean hop count and the miss ratio shown in the topology metrics graph of Figure 3.12 present an inverse relationship with the observed end-to-end throughputs shown in the end-to-end throughputs graph; in this case the higher is the hop count and miss ratio the lower are the end-to-end throughputs obtained. The end-to-end throughput obtained in Scenario E3 and Scenario E4 are similar. Curiously, most of these two topologies metrics are different, except the size of the 1st ring. This observation enable us to conclude that the size of the 1st ring may have a great importance on the performance of the network. From the 4 channel assignment schemes tested, Scenario E3 and Scenario E4 present the highest end-to-end throughput. In fact, the 290kbit/s achieved is near the maximal theoretical end-to-end throughput for a 34 flows destined to 2 gateways when the channel data rate is 11Mbit/s, which is 323kbit/s as explained above. All the scenarios reaching near the maximum end-to-end throughput, have similar 1st ring topology characteristics: three full connected nodes around the gateway. 3.5.2 Hidden nodes on the gateway neighborhood In order to verify the impact of 1st ring hidden nodes and 1st ring miss ratio on the network performance, the scenarios of Figure 3.13 were also tested. Scenarios A3, A4 and A5 are variants of Scenario A2, previously presented in Figure 3.2, where size of 1st ring becomes respectively 3, 2 and 1. On these scenarios, all 1st ring nodes are hidden from each other in order to verify the importance of 1st ring size in the presence of hidden nodes around the gateway. The networks on Figure 3.13 were offered to the same traffic and tests described earlier. The networks end-to-end throughputs and the topology metrics are also presented in Figure 3.13; the correspondent confidence intervals were omitted in order to simplify the figure, but are of the same order as those represented in Figure 3.12. In opposition to what was observed in Figure 3.12, for Scenarios A2, A3, A4 and A5 the end-to-end throughput decreases with the 66 Identification of relevant topology metrics Scenario A2 Scenario A3 Scenario A4 Scenario A5 0.01 0.1 1 10 Source node debit (Mbit/s) 0 50 100 150 200 Throughput (kbit/s) Scenario A2 Scenario A3 Scenario A4 Scenario A5 MeanHop Count Neigh Node Density Mean Hidden Nodes missratio (x10) 1st Ring missratio (x10) 1st Ring Hidden Nodes 1st Ring Size 0 1 2 3 4 5 6 Topology Metrics Scenario A2 Scenario A3 Scenario A4 Scenario A5 Figure 3.13: Channel assignment schemes with few nodes on the neighborhood of the gateway, all hidden from each other. End-toend throughputs with 90% confidence intervals and topology metrics are also presented. increase of the size of the 1st ring size, as shown in Figure 3.13. However, on scenarios of Figure 3.13, the number of hidden nodes around 3.5 Gateway neighborhood 67 the gateway increases with the increase of 1st ring size. Based on that, we conclude that the number of hidden nodes on the 1st ring influences more the network performance than the size of the 1st ring. The miss ratioR1is the miss ratio calculated considering only the links hidden from 1st ring links, as defined in Section 2.5. The miss ratioR1shown in the topology metrics graph of Figure 3.13 are clearly related with the end-to-end throughput also shown in that figure. The miss ratioR1of Scenarios A2, A3 and A4 have small differences between them, while the miss ratioR1of Scenario A5 is much smaller. Notably, this relationships are also present between the end-to-end throughputs of Scenarios A2, A3, A4 and A5 on Figure 3.13. Scenario A5 has the best performance presented in Figure 3.13 because it has a single node on the 1st ring and therefore does not have nodes hidden from this single link to the gateway. However, the end-to-end throughput of Scenario A5 does not reach the maximum achievable end-to-end throughput observed at Scenarios E3 and E4 on Figure 3.12 because a single link of Scenario A2 is not able to make hay of channel capacity as the three 1st ring links of Scenarios E3 and E4. Having three nodes on the 1st ring that cannot hear each other, as on Scenario A3, causes a great amount of collisions between them causing inefficiency on the network bottleneck which is the gateway neighborhood. On the contrary, when there are three nodes on the 1st ring that can hear each other, the medium around the gateway is used more efficiently, leading to better network end-to-end throughputs as shown by Figure 3.14. The amount of collisions on Scenarios E4, E3 and A3 are shown on Figure 3.15. Scenarios E4 and E3 present less collisions around the gateway than Scenario A3. The amount of collisions and consequent network inefficiency is related to the number of hidden nodes on the 1st ring. The inefficiency around the gateway has high impact in the network end-to-end throughput, since it is the network bottleneck. 68 Identification of relevant topology metrics 0.01 0.1 1 10 Source node debit (Mbit/s) 0 50 100 150 200 250 300 Throughput (kbit/s) Scenario E4 Scenario E3 Scenario A3 Figure 3.14: Comparison of the end-to-end throughputs of networks of Scenarios E4, E3 of Figure 3.12 and Scenario A3 of Figure 3.13. 3.6 Summary In this chapter we clarify which network topology characteristics are relevant to improve network performance and which metrics can be used quantify these characteristics. We consider this characterization fundamental for designing a quasi-static channel assignment algorithm for single-radio WMNs and, to the best of our knowledge, it is new. The impact of the topology of a network on its performance was estimated by means of extensive simulation analysis. We defined a set of experiments with 18 arbitrary channel assignment scenarios in a 6x6 lattice topology network. At each experiment each node generates a UDP flow towards the gateway, all flows have the same bit rate. Flow’s bit rates from 10kbit/s to 7.5Mbit/s were used. The performance metrics considered are the per-hop throughput and the end-to-end throughput. To calculate the network topology and performance metrics, the two sub-networks resultant from the channel assignment are treated as a single network. Metrics are calculated by analyzing the trace files generated by ns-2 using python scripts. Two channel assignment schemes were applied to the 36 node lattice network and were used as the basis for this study together with a single channel scenario, where the 36 nodes share the same channel. While the channel assignment scheme used in Scenario A1 minimizes the mean hop count, the scheme used in Scenario A2 aims to reduce the neighbor node density. Scenario A-Sch is the single channel scenario. Scenario A2 was found to have a higher per-hop throughput but a lower end-to-end throughput when compared to 3.6 Summary 69 Scenario E4 Scenario E3 Scenario A3 0 14 29 43 58 73 87 102 116 131 146 collisions (pkts/s) Figure 3.15: Amount of collisions on the networks of scenarios E4, E3 and A3 when each node is generating a flow of 3 Mbit/s to a destination on the Internet. The white and black centers of each node represent the gateway used to forward the packets to the Internet. The face color of a node represents the amount of collisions perceived by that node. Scenario A1. The inefficiency of Scenario A2 is caused by the hidden nodes which cause collisions. The per-hop throughput can be easily correlated with the neighbor node density of a network; higher node density results on lower number of frames successfully delivered. We simulated two new scenarios, Scenario B1 and Scenario B2, which are variants of Scenario A1 and Scenario A2 where a set of nodes were removed from both basic scenarios in order to get similar mean hop count but maintain the rest of the topology metrics. The simulation results on this new scenarios show that, in these cases, the mean hop count has low impact on the end-to-end throughput. The three new scenarios Scenario C1, C2, and C-Sch, are variants of the basic scenarios in which we increased the carrier sense range. The three new scenarios Scenario D1, D2, and D-Sch, are variants of the basic scenarios in which we repositioned the gateways to central positions. The simulation results of these scenarios show that neighbor node density does not have impact on the endto-end-throughput. In order to understand the impact of the characteristics of a gateway neighborhood we simulated a set of scenarios E1, E2 and E3 which differ from each other by the number of nodes around the 76 Ranking of topology metrics Random topology generator ns-2 Network simulation ns-2 Measure network topology and performance python script Data mining model generator R/rminer Sensitivity analysis R/rminer Figure 4.1: Methodology adopted in this study. The five stages are the random network topology generation, the network simulation, the measurement of simulation results, the generation of the data mining model and the sensitivity analysis. 4.2.1 Random network generation A tcl script was included in ns-2 [93] to generate 3500 network topologies. Each network has 36 nodes, including the gateways, spread in a area of 1000 m×1000 m. The position of each node, defined by its (x,y) coordinates, was generated using two independent uniform distributions. Random positions locating two nodes at a distance smaller than 50 m are rejected and another position is generated. After generating the 36 positions, the connectivity of the network is verified. If a node does not have at least one neighbor located at a distance less than RXThreshold = 350m, meaning that the node is isolated, the network is rejected and a new network is generated. The first two generated positions are selected to be the gateways. Different radio channels are assigned to each gateway. Two channel assignment strategies were applied to nodes on each topology. In the first assignment strategy, the channel assigned to each node is generated using a random variable using a uniform distribution. If in the generated scheme there are at least one isolated node, the network is rejected and a new network is generated. In the second assignment strategy, the channel whose gateway is closer was assigned to each node. For doing that, first all nodes are configured in the same channel, and the gateways broadcast advertisement messages through the network using the Proactive PREQ mechanism defined by IEEE 802.11s [1]. Using the advertisement messages received, nodes select the closer gateway or the gateway that sent the first advertisement received by the node if both are at the same distance. Then, different channels are assigned to each gateway and the channel assigned to each node is the same as the chosen gateway. 4.2 Methodology 77 Fig. 4.2 represents two instances of the generated networks; the lines between nodes represent wireless connectivity between them. Figure 4.2: Examples of generated random network topologies.The lines between nodes represent wireless connectivity between them. Nodes in different colors are in a different channel. 4.2.2 Network simulation Each WMN node, except the gateways, generates a traffic flow whose packets are generated by a Poisson process; these packets are UDP and are destined to a node in the Internet through the serving gateway. Simultaneously, a node outside the mesh network generates a similar flow destined to each node in the network, except the gateways. All flows are configured with similar parameters, which are fixed for each simulation. The IEEE 802.11 data rate used in this study is 54 Mbit/s, but the overhead of lower layers of the communication stack is about 50% [94], leaving 27Mbit/s per gateway available to transmit packets from 34 nodes. The maximum data rate per flow is 794kbit/s = (27Mbit/s ×2gateways)/34nodes/2flows. Considering that each frame is forwarded through multiple hops until it reaches the gateway, the maximum achievable end-to-end throughput is even lower. Therefore, it is expectable that a considerable amount of frames are lost when the sources debit is above 700kbit/s. We used flows with a data rate of 480 kbit/s to test the networks with low loads and flows with a data rate of 4.8 Mbit/s to test the 78 Ranking of topology metrics networks with high loads which is a saturation situation. Each generated network was simulated four times using ns-2.29; with the two data rates and with 2 different seeds. The parameters used in simulation are presented on Table 5.3. The simulation tool ns-2 was used with two-ray propagation model in the physical layer, MAC DCF 802.11 in the link layer, and the HWMP [1] was used to establish routes. Parameter Value Propagation Model two ray ground Channel data rate 54 Mbit/s RX Threshold -70.2 dBm, 350 m Node distance 176 m Packet size 1500 bytes sources debit 4.8 Mbit/s or 480 kbit/s RTS/CTS ON Routing HWMP Source type Poisson (UDP) WarmUp 10 packet/s ×256 byte Simulation runs 2 Table 4.1: Parameters used in ns-2.29 simulations of the random network topologies. The duration of each simulation was configured to give time to generate 104packets on each flow; the exact duration depends on the flow data rate. During the first 3 seconds there are no data flows; this period is used to allow the HWMP routing protocol to execute the proactive tree building functionality; in this phase a route to one of the gateways is added to each node as described in the the Proactive PREQ mechanism [1]; the reverse path is also created. Between second 3 and second 10 the warm up flow takes place between each node and the gateway; this flow enables the ARP tables of each node to be filled. Warm up flows are not considered to calculate the network performance metrics. 4.2 Methodology 79 4.2.3 Measurement of network topology and network performance In order to calculate the metrics of network topology and network performance, the two sub-networks resultant from the channel assignment are are either treated separately or as a single network. The metrics are calculated per sub-network when resume the performance of topology of nodes sharing a channel; in this case the two sub-networks are treated separately. The metrics are calculated on the global network when they aggregate the performance and the topology information of all nodes in the network. The metrics are calculated using python scripts that process the simulation trace files provided by ns-2. The performance and topology metrics considered to this study are detailed in Section 4.3 and Section 4.4. 4.2.4 Data mining model In our work we use a data mining approach, where each network performance metric is modeled as a regression function, as given by the SVM algorithm, that is dependent of the several topology metrics. The main idea of the SVM is to transform the input data into a high-dimensional feature space by using a nonlinear mapping φ. For regression, the ε-insensitive cost function is commonly used [86], which sets a tube around the residuals, being the tiny errors within this tube discarded (Figure 4.3). Then, the SVM finds the best hyperplane within the feature space: ˆy=w0+ m X i=1 wiφi(x)(4.1) where ˆyis the predicted value, wiare the weights (set by the SVM training algorithm), mis the number of support vectors (set by the ε-insensitive tube) and xis a vector with the input variables. The φtransformation (which is not explicitly known), depends on the adopted kernel function. The Gaussian kernel is the most popular one, presenting less parameters than other kernels, and thus 80 Ranking of topology metrics support vectors +ε −ε 0 0+ε−ε Figure 4.3: Example of a SVM and regression using the -insensitive tube. it is adopted in this work: k(x,x0) = e−γ×kx−x0k2 ,γ > 0(4.2) Under this setup, performance of the regression is affected by three parameters: γis the parameter of the kernel, Cis a complexity penalty parameter, and εis the width of a ε-insensitive zone. To reduce the search space, the last two values will be set using the heuristics proposed in [95]: C= 3 (for a standardized output) and ε= ˆσ/√N, where ˆσ= 1.5/N ×PN i=1(yi−ˆyl)2and ˆylis the value predicted by a 3-nearest neighbor algorithm. To optimize the most relevant SVM hyper-parameter (γ), we adopted a grid search under the range {2−15,2−13,...,23}, and an internal (i.e. over the training data) 3-fold cross validation was used to select the best γvalue (i.e. that produces the lowest absolute deviation error on the validation data produced by the 3-fold scheme) [78]. After setting γ, the SVM was retrained with all training data. In order to evaluate the performance of the SVM predictions, we considered two popular regression metrics: Mean Absolute Error (MAD), and Coefficient of determination (R2). Let ydenote the target value, ˆythe predicted value, yand ˆythe mean of these variables. Then: MAD =PN i=1 |yi−ˆyi|/N R2= 1−PN i=1 (yi−ˆyi)2/PN i=1 (yi−y)2 (4.3) 4.2 Methodology 81 Lower values of MAD and R2values close to the unit value correspond to a higher predictive capacity. To get robust estimates of the predictive performances of the SVM model, we applied 5 runs of an external (i.e. over all data) 5-fold cross validation, in a total of 25 SVM trainings for each tested configuration. The predictive errors (i.e. MAD and R2) shown in this work are reported in terms for the mean values of these runs and computed over the test (i.e. unseen) data defined by the 5-fold procedure. All experiments reported were implemented using the rminer library of the R tool [96]. 4.2.5 Sensitivity analysis Another important data mining goal is related with descriptive knowledge, i.e. if it is possible to extract useful understandable knowledge from the data-driven models. In this application domain, this issue is handled by using the fitted SVM data mining models to estimate the impact of topology metrics on the wireless network performance. Despite the high complexity the SVM models (due to the nonlinear kernel transformation), it is still possible to extract knowledge in terms of input variable importance and Variable Effect Characteristic (VEC) curves by using a 1-D sensitivity analysis [92]. This sensitivity analysis works by successively holding all inputs to their average values except one input, which is varied through its range of values in order to observe its effect on the target responses. The higher the variance observed in the responses, the higher is the importance of the input variable. Thus, the set of input variables can be ranked according to the variance measure of the sensitivity responses. In addition, during this 1-D sensitivity analysis, the average effect of an all probed individual input levels on the model predictions can be stored. By using such data, it is possible to plot the respective VEC curve, which gives a visual and easy to read information about the average impact of a given input variable in the fitted model. 82 Ranking of topology metrics 4.3 Network performance metrics Network performance can be characterized using measures such as throughput, delay and packet loss. In our study we focus on node throughput and delay. First we want to maximize the average node throughput. Second, we want to maximize fairness among node’s throughput, to be sure that each mesh node offers an effective connection of its stations to the infra-structured network. Third, we want to minimize the end-to-end delay experienced by packets transmitted to and from the mesh nodes and the infra-structured network. These metrics are defined below. The present section defines the performance metrics considered to this study and characterizes the metrics obtained on the simulations carried out. The set of 28000 experiments (7000 topologies ×2 seeds ×2 data rates) was studied statistically considering that each of the metrics is a random variable and the measures taken from the simulation are samples of those variables. The probability density function (PDF) of each network performance metric is shown in Fig. 4.4 for simulations with low and high loads calculated per sub-network or over the global network. The mean value and standard deviation of the performance metrics of the samples are represented in graphics as µand σrespectively. 4.3.1 Throughput The throughput is defined as the sum of the bit rate received by destinations. Formally, the throughput TAmeasured on channel A is given in bits per second by Eq. 4.4 where TRX iis the number of packets received by node i,TTX iis the number of packets received by the gateway sent by node i, and Lis the packet length given in bits. TA=P(TRX i+TTX i)L duration of simulation (4.4) The histogram of the throughput is presented in Figure 4.4(a), 4.4(d), 4.4(g), and 4.4(j) for simulations with low and high loads calculated per sub-network or over the global network. When the network is low loaded, the achieved network throughput is also low; 4.3 Network performance metrics 83 4 8 12 16 (a) Throughput (Mbit/s) on per sub-network; low load 0.0 1.5 3.0 4.5 Frequency ×103 µ=10.0 σ=2.0 45 60 75 90 (b) Fairness (%) on per sub-network; low load 0.0 0.6 1.2 1.8 Frequency ×104 µ=94.9 σ=6.5 0.0 0.8 1.6 2.4 (c) Delay (s) on per sub-network; low load 0.0 2.5 5.0 7.5 Frequency ×103 µ=0.46 σ=0.34 0 6 12 18 (d) Throughput (Mbit/s) on per sub-network; high load 0.0 1.5 3.0 4.5 Frequency ×103 µ=11.7 σ=4.1 25 50 75 100 (e) Fairness (%) on per sub-network; high load 0.0 1.5 3.0 4.5 Frequency ×103 µ=43.5 σ=18.4 0.0 0.8 1.6 2.4 (f) Delay (s) on per sub-network; high load 0.0 0.4 0.8 1.2 Frequency ×104 µ=0.26 σ=0.16 10 15 20 25 (g) Throughput (Mbit/s) on global network; low load 0.0 0.8 1.6 2.4 Frequency ×103 µ=20.0 σ=2.9 45 60 75 90 (h) Fairness (%) on global network; low load 0.0 1.5 3.0 4.5 Frequency ×103 µ=90.9 σ=7.2 0.0 0.5 1.0 1.5 (i) Delay (s) on global network; low load 0.0 1.5 3.0 4.5 Frequency ×103 µ=0.43 σ=0.18 8 16 24 32 (j) Throughput (Mbit/s) on global network; high load 0.0 0.8 1.6 2.4 Frequency ×103 µ=23.5 σ=4.9 25 50 75 100 (k) Fairness (%) on global network; high load 0.0 1.5 3.0 4.5 Frequency ×103 µ=34.4 σ=9.3 0.150.300.450.60 (l) Delay (s) on global network; high load 0.0 1.5 3.0 4.5 Frequency ×103 µ=0.22 σ=0.07 Figure 4.4: Histograms of performance metrics. this is shown by comparing Figure 4.4(a) with Figure 4.4(d), and Figure 4.4(g) with Figure 4.4(j). Experiments with high source load data rates show a wider histogram and larger standard deviation (4.1 Mbit/s for per subnetwork and 4.9 Mbit/s for global network) when compared with low source load data rates (2.0 Mbit/s for per sub-network and 2.9 Mbit/s for global network) meaning more uncertainty in the throughput results when the network is saturated. Throughput results for the global network are about the double of those calculated per sub-networks since the number of flows considered is also the double. This is the reason why the mean values 84 Ranking of topology metrics of throughput global network measures (20.0 Mbit/s for low source load data rates and 23.5 Mbit/s for high source load data rates) are the double of the mean values of throughput sub-network measures (10.0 Mbit/s for low source load data rates and 11.7 Mbit/s for high source load data rates). Despite the standard deviation of the throughput in global network measures (2.9 Mbit/s for low source load data rates and 4.9 Mbit/s for high source load data rates) is higher than the standard deviation of throughput sub-network (2.0 Mbit/s for low source load data rates and 4.1 Mbit/s for high source load data rates), it is not the double. This is why global network throughput present a narrowest histogram when compared with per sub-network. 4.3.2 Fairness The measure of the fairness of the achieved throughput among flows in the network or in the sub-network is estimated using the Jain Index [97]. Eq. 4.5 shows how fairness is calculated, where Tiis the sum of TRX iand TTX i. The fairness Jis independent of scale, applies to any number of nodes and is bounded between 0 and 1, where J= 1 indicate a totally fair network. J=(PTi)2 nPT2 i (4.5) The histogram of the fairness is presented in Figure 4.4(b), 4.4(e), 4.4(h), and 4.4(k) for simulations with low and high loads calculated per sub-network or over the both sub-networks. Figure 4.4(e) and 4.4(k) show that when 34×2 flows (download plus upload flow per node) of 4.8 Mbit/s are inserted in the network, it gets saturated because fairness is low. Nodes that are not in the neighborhood of the gateways have more difficulty to transmit their packets through long multi-hop routes and low values of fairness are achieved by most of the experiments. Figure 4.4(b) shows that when the flow data rate is low, the fairness is high (around 100%) in most experiences, showing that all nodes in each sub-network have similar chances of transmitting their 4.4 Network topology metrics 85 packets because the network is not saturated. With these load conditions, the fairness measured using the throughput achieved by all nodes in the network is lower when compared with per sub-network fairness, as shown by Figure 4.4(h); the two sub-networks of each scenario typically have different topological characteristics, mostly the number of nodes per sub-network, and even if the bandwidth is evenly distributed among the nodes in a sub-network, the achieved per node throughput on each sub-network is different, resulting in lower fairness. 4.3.3 Delay The delay is calculated as the mean time elapsed between the creation of a packet and its reception by the final destination. Lost packets are not considered. The histogram of the delay is presented in Figure 4.4(c), 4.4(f), 4.4(i), and 4.4(l) for simulations with low and high loads calculated per sub-network or over the both sub-networks. When the flow data rate is high (Figure 4.4(f) and 4.4(l)), most packets to and from nodes that are not in the gateway neighborhood are lost. Therefore most of the packets considered to calculate the delay, which are those successfully delivered to their destinations, have to be forwarded through less hops when compared with the low data rate scenarios leading to lower delays when compared with low traffic load conditions. Overall network delay is the weighted mean of delays of packets delivered in both sub-networks, therefore the overall network and per sub-network delays have a similar mean; the standard deviation is lower. 4.4 Network topology metrics The topology of each network is summarized by a set of metrics identified in Chapter 3 that includes mean hop count, neighbor node density, number of nodes in the gateway neighborhood, the miss ratio of the overall network, and the miss ratio on the gateway neighborhood. The number of nodes using each radio channel is an important characteristic when the channel assignment is applied 92 Ranking of topology metrics 0.0 0.1 0.2 0.3 0.4 (a) per sub-ntwk; low load MAD = 0.42; R2= 0.92 No. of nodes Mean hop count Neighbor node density 1st ring size Miss ratio 1st Ring missratio 0.0 0.1 0.2 0.3 0.4 (b) per sub-ntwk; high load MAD = 1.27; R2= 0.82 No. of nodes Mean hop count Neighbor node density 1st ring size Miss ratio 1st Ring missratio 0.0 0.2 0.4 0.6 (c) global ntwk; low load MAD = 0.71; R2= 0.9 No. of nodes diff. Mean hop count Neighbor node density 1st ring size Miss ratio 1st Ring missratio 0.0 0.2 0.4 0.6 0.8 (d) global ntwk; high load MAD = 2.16; R2= 0.68 No. of nodes diff. Mean hop count Neighbor node density 1st ring size Miss ratio 1st Ring missratio 10 20 30 (a1) No. of nodes diff. 5 10 15 Throughput (Mbit/s) 05101520253035 0 1 2 3 4 5 6 10 20 30 (b1) No. of nodes diff. 6 12 18 05101520253035 0 2 4 6 8 10 12 14 0 5 10 (c1) No. of nodes diff. 12 18 24 02468101214 0.0 0.5 1.0 1.5 2.0 0 5 10 (d1) No. of nodes diff. 10 20 30 02468101214 0 1 2 3 4 5 6 7 2345 (a2) Mean hop count 5 10 15 Throughput (Mbit/s) 2.02.53.03.54.04.55.05.5 0 1 2 3 4 5 6 2345 (b2) Mean hop count 6 12 18 2.02.53.03.54.04.55.05.5 0 2 4 6 8 10 12 14 16 18 345 (c2) Mean hop count 12 18 24 2.02.53.03.54.04.55.0 0.0 0.5 1.0 1.5 2.0 3 4 (d2) Mean hop count 10 20 30 2.02.53.03.54.04.55.0 0 1 2 3 4 5 369 (a3) Neighbor node density 5 10 15 Throughput (Mbit/s) 12345678910 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 369 (b3) Neighbor node density 6 12 18 12345678910 0 2 4 6 8 10 12 4.5 6.0 7.5 (c3) Neighbor node density 12 18 24 3456789 0.0 0.5 1.0 1.5 2.0 4.5 6.0 7.5 (d3) Neighbor node density 10 20 30 3456789 0 1 2 3 4 5 6 7 4 8 12 (a4) 1st ring size 5 10 15 Throughput (Mbit/s) 024681012 0 2 4 6 8 10 4 8 12 (b4) 1st ring size 6 12 18 024681012 0 10 20 30 40 50 60 70 2.5 5.0 7.5 (c4) 1st ring size 12 18 24 12345678 0.0 0.5 1.0 1.5 2.0 2.5 5.0 7.5 (d4) 1st ring size 10 20 30 12345678 0 2 4 6 8 10 12 0.0 0.1 0.2 (a5) Miss ratio 5 10 15 Throughput (Mbit/s) 0.000.050.100.150.200.250.30 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 0.0 0.1 0.2 (b5) Miss ratio 6 12 18 0.000.050.100.150.200.250.30 0 2 4 6 8 10 12 14 16 0.15 0.20 (c5) Miss ratio 12 18 24 0.120.140.160.180.200.220.240.26 0.0 0.5 1.0 1.5 2.0 0.15 0.20 (d5) Miss ratio 10 20 30 0.120.140.160.180.200.220.240.26 0 1 2 3 4 5 6 7 8 0.00 0.15 0.30 (a6) 1st Ring missratio 5 10 15 Throughput (Mbit/s) 0.000.050.100.150.200.250.300.350.400.45 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 0.00 0.15 0.30 (b6) 1st Ring missratio 6 12 18 0.000.050.100.150.200.250.300.350.400.45 0 5 10 15 20 25 0.1 0.2 0.3 (c6) 1st Ring missratio 12 18 24 0.050.100.150.200.250.300.350.40 0.0 0.5 1.0 1.5 2.0 0.1 0.2 0.3 (d6) 1st Ring missratio 10 20 30 0.050.100.150.200.250.300.350.40 0 1 2 3 4 5 6 7 Figure 4.7: Throughput models. 4.5 Data mining models results 93 The miss ratio on the overall network, 1st ring miss ratio metric and neighbor node density have importances below 0.1 and are considered to have no impact on this model output. Figure 4.7(b) shows that for the measures taken per sub-network, when the network has high traffic loads, the mean hop count and number of nodes difference metrics are also important to the throughput model with importances of 0.31 and 0.20. The miss ratio on the overall network, 1st ring miss ratio metric and neighbor node density have importances below 0.1 and are considered to have no impact on this model output. Figure 4.7(c) shows that for the measures taken over the global network, when the network has low traffic loads, the mean hop count and the number of nodes difference metrics are also important to the throughput model with importances of 0.31 and 0.15 respectively. The miss ratio on the overall network, 1st ring miss ratio and neighbor node density have importances below 0.1 and are considered to have no impact on this model output. Figure 4.7(d) shows that for the measures taken over the global network, when the network has high traffic loads, the 1st ring miss ratio metrics are also important to the throughput model with importance of 0.17. The mean hop count, neighbor node density, miss ratio on the overall network, and number of nodes difference metrics have importances below 0.1 and are considered to have no impact on this model output. 4.5.1.1 Number of nodes Figures 4.7(a1), 4.7(b1), 4.7(c1) and 4.7(d1) represent the joint probability density function graphs and the VEC curves of the number of nodes in the network and the throughput obtained for data rates of 480 kbit/s and 4.8 Mbit/s calculated per sub-network and over the global network. The joint probability density function graph on these figures show that highest throughputs were obtained by scenarios with equal number of nodes in each channel. The VEC curve in Figure 4.7(a1) shows that, when the network is low loaded and the metrics are taken per sub-network, a low number of nodes results in low throughput. If the network is not 94 Ranking of topology metrics saturated, all traffic generated is delivered; if the sub-network has a low number of nodes, less traffic is generated and the throughput is low. However, the VEC curve in Figure 4.7(c1) shows that, when the network is low loaded and the metrics are taken over the global network, the highest throughputs were obtained by scenarios with equal number of nodes in each channel. When the two sub-networks on a same network have an unbalanced number of nodes, one of the sub-networks may obtain a high throughput, but the throughput of the global network is low. The VEC curve in Figure 4.7(b1) shows that, when the network is high loaded and the metrics are taken per sub-network, a low number of nodes results in high throughput. The network is more saturated if there is more traffic in the network; if the sub-network has a low number of nodes, less traffic is generated, the sub-network is less saturated (less collisions) and the throughput is high. The VEC curve in Figure 4.7(d1) shows that, when the network is high loaded and the metrics are taken over the global network, the number of nodes has a low impact on the obtainable network throughput because the slight gain in having a sub-network with less nodes and therefore with high throughput, is canceled by the high saturated sub-network that has more nodes. 4.5.1.2 Mean hop count Figures 4.7(a2), 4.7(b2), 4.7(c2) and 4.7(d2) represent the joint probability density function graphs and the VEC curves of the mean hop count in the network and the throughput obtained for data rates of 480 kbit/s and 4.8 Mbit/s calculated per sub-network and over the global network. The joint probability density function graph on figures 4.7(a2) and 4.7(c2) show that, when the network is low loaded, the throughput and the mean hop count of the network have an almost linear inverse relationship meaning that networks with higher mean hop count obtain lower throughputs. VEC curves on these figures show the same result. Higher throughputs are obtained when nodes in the network are closer to the gateway (low mean hop count). That 4.5 Data mining models results 95 result was expectable because data packets have to be forwarded less times in the mesh network until they reach the final destination. The joint probability density function graph on figures 4.7(b2) and 4.7(d2) show that, when the network is high loaded, the throughput and the mean hop count of the network continue to be inversely related despite having a less clear relation. With this traffic conditions, only nodes on the gateway neighborhood can transmit and receive packets as shown in [28] and by the low values of fairness shown in Figure 4.4(h), therefore the hop count of nodes that are not directly connected to the gateway is less important. For high loaded networks the impact of the mean hop count on the throughput when metrics are taken per sub-network is much higher than when metrics are taken over the global network as shown by figures 4.7(b) and 4.7(d) and by the VEC curves on figures 4.7(b2) and 4.7(d2). 4.5.1.3 Neighbor node density Figures 4.7(a3), 4.7(b3), 4.7(c3) and 4.7(d3) represent the joint probability density function graphs and the VEC curves of the neighbor node density in the network and the performance metrics obtained for data rates of 480 kbit/s and 4.8 Mbit/s calculated per sub-network and over the global network. The flat VEC curves, the joint probability density function graphs, and the low correlation between throughput and neighbor node density shown in Table 4.2 show that neighbor node density has a low impact on the network throughput. 4.5.1.4 Size of 1st ring Figure 4.7(a4), 4.7(b4), 4.7(c4) and 4.7(d4) represent the joint probability density function graphs and the VEC curves of the size of 1st ring in the network and the throughput obtained for data rates of 480 kbit/s and 4.8 Mbit/s calculated per sub-network and over the global network. The joint probability density function graphs and the high values of correlation between the size of first ring and the throughput in Table 4.2 shows that the throughput and the size of 1st ring of networks have an almost linear relationship. 96 Ranking of topology metrics The VEC curves for throughput models are presented as a white line in Figure 4.7(a4), 4.7(b4), 4.7(c4) and 4.7(d4). VEC curves show that high values of throughput are obtained when more nodes are in the neighborhood of the gateways (size of 1st ring), but the relationship between the two metrics is not linear when the network is high loaded. When a large number of nodes are directly connected to the gateway, there are two effects that contribute to increase the throughput: (1) data packets have to be forwarded only once in the mesh network until they reach the final destination, what means that less radio resources are used, leaving more opportunities to other packets to be transmitted; (2) the gateway can manage well the radio resources using the carrier sense and RTS/CTS, thus reducing the number of collisions. 4.5.1.5 Miss ratio Figures 4.7(a5), 4.7(b5), 4.7(c5) and 4.7(d5) represent the joint probability density function graphs and the VEC curves of the miss ratio of the network and the throughput obtained for data rates of 480 kbit/s and 4.8 Mbit/s calculated per sub-network and over the global network. The flat VEC curves, the joint probability density function graphs, and the low correlation between throughput and miss ratio shown in Table 4.2 show that miss ratio has a low impact on the network throughput. 4.5.1.6 1st ring miss ratio Figures 4.7(a6), 4.7(b6), 4.7(c6) and 4.7(d6) represent the joint probability density function graphs and the VEC curves of the 1st ring miss ratio of the network and the throughput obtained for data rates of 480 kbit/s and 4.8 Mbit/s calculated per sub-network and over the global network. The joint probability density function graphs in these figures show that low 1st ring miss ratio topologies results in high network throughputs. The flat VEC curves on figures 4.7(a6), 4.7(b6) and 4.7(c6) show that for low loaded situations, the 1st ring miss ratio has a low impact on the network throughput. The joint probability density 4.5 Data mining models results 97 function graphs on the same figures show that an inverse relation exists between the 1st ring miss ratio and the throughput; however, the other topology metrics were considered to have more impact on the throughput model resulting in flat VEC curves. The VEC curve in Figure 4.7(d6) shows that, when the network is high loaded and global network metrics are considered, low 1st ring miss ratio have a high impact on the network throughput. When the network is high loaded, there are more collisions [28], in those situations the existence of more hidden nodes around the gateway, which are given by the 1st ring miss ratio, increase the occurrence of collisions on the bottleneck of the network reducing the throughput. 4.5.2 Model for fairness Figures 4.8(a), 4.8(b), 4.8(c) and 4.8(d) show the importance graphs for the fairness models obtained for data rates of 480 kbit/s and 4.8 Mbit/s calculated per sub-network and over the global network. Figure 4.8(a) shows that for measures taken per sub-network, when the network has low traffic loads, the number of nodes and the mean hop count are the most important metrics in the fairness model with importances of 0.45 and 0.36 respectively. The miss ratio on the overall network, 1st ring miss ratio, the neighbor node density, and the 1st ring size have importances below 0.1 and are considered to have no impact on this model output. Figure 4.8(b) shows that for the measures taken per sub-network, when the network has high traffic loads, the number of nodes is the most important metric with an importance of 0.37. The 1st ring size and the mean hop count metrics are also important to the fairness model both with importance of 0.20. The miss ratio on the overall network has an importance of 0.12. The 1st ring miss ratio and neighbor node density have importances below 0.1 and are considered to have no impact on this model output. Figure 4.8(c) shows that for measures taken over the global network, when the network has low traffic loads, the mean hop count and the number of nodes difference are the most important metrics to fairness model with importances of 0.43 and 0.42 respectively. The miss ratio on the overall network, 1st ring miss ratio metric, 98 Ranking of topology metrics 0.0 0.2 0.4 0.6 (a) per sub-ntwk; low load MAD = 2.17; R2= 0.7 No. of nodes Mean hop count Neighbor node density 1st ring size Miss ratio 1st Ring missratio 0.0 0.1 0.2 0.3 0.4 (b) per sub-ntwk; high load MAD = 9.36; R2= 0.48 No. of nodes Mean hop count Neighbor node density 1st ring size Miss ratio 1st Ring missratio 0.0 0.1 0.2 0.3 0.4 0.5 (c) global ntwk; low load MAD = 2.66; R2= 0.75 No. of nodes diff. Mean hop count Neighbor node density 1st ring size Miss ratio 1st Ring missratio 0.0 0.2 0.4 0.6 0.8 (d) global ntwk; high load MAD = 5.52; R2= 0.3 No. of nodes diff. Mean hop count Neighbor node density 1st ring size Miss ratio 1st Ring missratio 10 20 30 (a1) No. of nodes diff. 60 80 100 Fairness (%) 05101520253035 0.0 0.5 1.0 1.5 2.0 10 20 30 (b1) No. of nodes diff. 30 60 90 05101520253035 0 5 10 15 20 25 30 35 0 5 10 (c1) No. of nodes diff. 60 75 90 02468101214 0.0 0.2 0.4 0.6 0.8 1.0 0 5 10 (d1) No. of nodes diff. 25 50 75 02468101214 0 2 4 6 8 10 12 14 16 2345 (a2) Mean hop count 60 80 100 Fairness (%) 2.02.53.03.54.04.55.05.5 0.0 0.5 1.0 1.5 2.0 2345 (b2) Mean hop count 30 60 90 2.02.53.03.54.04.55.05.5 0 5 10 15 20 25 30 345 (c2) Mean hop count 60 75 90 2.02.53.03.54.04.55.0 0.0 0.2 0.4 0.6 0.8 1.0 3 4 (d2) Mean hop count 25 50 75 2.02.53.03.54.04.55.0 0 1 2 3 4 5 6 7 8 9 369 (a3) Neighbor node density 60 80 100 Fairness (%) 12345678910 0.0 0.5 1.0 1.5 2.0 369 (b3) Neighbor node density 30 60 90 12345678910 0 5 10 15 20 25 30 35 4.5 6.0 7.5 (c3) Neighbor node density 60 75 90 3456789 0.0 0.2 0.4 0.6 0.8 1.0 4.5 6.0 7.5 (d3) Neighbor node density 25 50 75 3456789 0 2 4 6 8 10 12 4 8 12 (a4) 1st ring size 50 75 100 Fairness (%) 024681012 0.0 0.5 1.0 1.5 2.0 2.5 3.0 4 8 12 (b4) 1st ring size 30 60 90 024681012 0 50 100 150 200 250 2.5 5.0 7.5 (c4) 1st ring size 60 75 90 12345678 0.0 0.2 0.4 0.6 0.8 1.0 2.5 5.0 7.5 (d4) 1st ring size 25 50 75 12345678 0 2 4 6 8 10 12 14 16 0.0 0.1 0.2 (a5) Miss ratio 60 80 100 Fairness (%) 0.000.050.100.150.200.250.30 0.0 0.5 1.0 1.5 2.0 0.0 0.1 0.2 (b5) Miss ratio 30 60 90 0.000.050.100.150.200.250.30 0 5 10 15 20 25 30 35 40 45 0.15 0.20 (c5) Miss ratio 60 75 90 0.120.140.160.180.200.220.240.26 0.0 0.2 0.4 0.6 0.8 1.0 0.15 0.20 (d5) Miss ratio 25 50 75 0.120.140.160.180.200.220.240.26 0 1 2 3 4 5 6 7 8 9 0.00 0.15 0.30 (a6) 1st Ring missratio 60 80 100 Fairness (%) 0.000.050.100.150.200.250.300.350.400.45 0.0 0.5 1.0 1.5 2.0 0.00 0.15 0.30 (b6) 1st Ring missratio 30 60 90 0.000.050.100.150.200.250.300.350.400.45 0 5 10 15 20 25 30 35 40 0.1 0.2 0.3 (c6) 1st Ring missratio 60 75 90 0.050.100.150.200.250.300.350.40 0.0 0.2 0.4 0.6 0.8 1.0 0.1 0.2 0.3 (d6) 1st Ring missratio 25 50 75 0.050.100.150.200.250.300.350.40 0 2 4 6 8 10 12 14 16 18 Figure 4.8: Fairness models. 4.5 Data mining models results 99 the 1st ring size, and the neighbor node density have importances below 0.1 and are considered to have no impact on this model output. Figure 4.8(d) shows that for the measures taken over the global network, when the network has high traffic loads, the 1st ring size is the most important metric for the fairness model with an importance of 0.67. All the other metrics have importances below 0.1 and are considered to have no impact on this model output. Under these traffic load conditions, the network becomes saturated and only nodes on the neighborhood of the gateway are able to transmit and receive their packets. When more nodes are around the gateway, the network becomes more fair, as shown in Figure 4.8(d1). On unsaturated mesh networks, all nodes are able to transmit and receive their packets, therefore fairness is close to 100% in most of the cases. However, if an unbalanced number of nodes exist in sub-networks using different channels, the overall network becomes unfair as shown in figures 4.8(a1) and 4.8(c1). The same applies when several nodes are more than 4 hops away from the gateway as shown in figures 4.8(a2) and 4.8(c2). Fairness models have high errors when compared with the throughput and delay models. This is because the considered topology metrics do not have a great impact on the network fairness as can be seen by the flat shape of VEC curves. These curves show that even the topology metrics with more importance imply a small variability on the output of the model. This shows that fairness is a very unpredictable performance metric in wireless mesh networks mostly when high traffic loads are involved. 4.5.3 Model for delay Figure 4.9(a), Figure 4.9(b), Figure 4.9(c) and Figure 4.9(d) show the importance graphs for the delay models obtained for data rates of 480 kbit/s and 4.8 Mbit/s calculated per sub-network and over the global network. Figure 4.9(a) shows that for the measures taken per sub-network, when the network has low traffic loads, the number of nodes is most important metric in the delay model with an importance of 0.59. 100 Ranking of topology metrics 0.0 0.2 0.4 0.6 (a) per sub-ntwk; low load MAD = 0.07; R2= 0.9 No. of nodes Mean hop count Neighbor node density 1st ring size Miss ratio 1st Ring missratio 0.0 0.1 0.2 0.3 (b) per sub-ntwk; high load MAD = 0.05; R2= 0.76 No. of nodes Mean hop count Neighbor node density 1st ring size Miss ratio 1st Ring missratio 0.0 0.1 0.2 0.3 0.4 0.5 (c) global ntwk; low load MAD = 0.06; R2= 0.83 No. of nodes diff. Mean hop count Neighbor node density 1st ring size Miss ratio 1st Ring missratio 0.0 0.2 0.4 0.6 (d) global ntwk; high load MAD = 0.03; R2= 0.68 No. of nodes diff. Mean hop count Neighbor node density 1st ring size Miss ratio 1st Ring missratio 10 20 30 (a1) No. of nodes diff. 0.0 0.6 1.2 Delay (s) 05101520253035 0 100 200 300 400 500 600 700 800 10 20 30 (b1) No. of nodes diff. 0.0 0.4 0.8 05101520253035 0 50 100 150 200 0 5 10 (c1) No. of nodes diff. 0.3 0.6 0.9 02468101214 0 20 40 60 80 100 120 140 0 5 10 (d1) No. of nodes diff. 0.1 0.2 0.3 0.4 02468101214 0 5 10 15 20 25 30 2345 (a2) Mean hop count 0.0 0.6 1.2 Delay (s) 2.02.53.03.54.04.55.05.5 0 100 200 300 400 500 600 700 800 900 2345 (b2) Mean hop count 0.0 0.4 0.8 2.02.53.03.54.04.55.05.5 0 50 100 150 200 250 3 4 (c2) Mean hop count 0.3 0.6 0.9 2.02.53.03.54.04.55.0 0 20 40 60 80 100 3 4 (d2) Mean hop count 0.1 0.2 0.3 0.4 2.02.53.03.54.04.55.0 0 2 4 6 8 10 12 14 16 18 369 (a3) Neighbor node density 0.0 0.6 1.2 Delay (s) 12345678910 0 100 200 300 400 500 600 369 (b3) Neighbor node density 0.0 0.4 0.8 12345678910 0 20 40 60 80 100 120 4.5 6.0 7.5 (c3) Neighbor node density 0.3 0.6 0.9 3456789 0 5 10 15 20 25 30 4.5 6.0 7.5 (d3) Neighbor node density 0.1 0.2 0.3 0.4 3456789 0 2 4 6 8 10 12 14 16 4 8 12 (a4) 1st ring size 0.0 0.6 1.2 Delay (s) 024681012 0 100 200 300 400 500 600 700 800 4 8 12 (b4) 1st ring size 0.0 0.4 0.8 024681012 0 50 100 150 200 250 300 2.5 5.0 7.5 (c4) 1st ring size 0.3 0.6 0.9 12345678 0 10 20 30 40 50 60 2.5 5.0 7.5 (d4) 1st ring size 0.1 0.2 0.3 0.4 12345678 0 2 4 6 8 10 12 14 16 18 0.0 0.1 0.2 (a5) Miss ratio 0.0 0.6 1.2 Delay (s) 0.000.050.100.150.200.250.30 0 100 200 300 400 500 600 700 800 0.0 0.1 0.2 (b5) Miss ratio 0.0 0.4 0.8 0.000.050.100.150.200.250.30 0 20 40 60 80 100 120 140 0.15 0.20 (c5) Miss ratio 0.3 0.6 0.9 0.120.140.160.180.200.220.240.26 0 5 10 15 20 25 30 35 0.15 0.20 (d5) Miss ratio 0.1 0.2 0.3 0.4 0.120.140.160.180.200.220.240.26 0 2 4 6 8 10 12 14 16 18 0.00 0.15 0.30 (a6) 1st Ring missratio 0.0 0.6 1.2 Delay (s) 0.000.050.100.150.200.250.300.350.400.45 0 100 200 300 400 500 600 700 800 900 0.00 0.15 0.30 (b6) 1st Ring missratio 0.0 0.4 0.8 0.000.050.100.150.200.250.300.350.400.45 0 20 40 60 80 100 120 140 160 180 0.1 0.2 0.3 (c6) 1st Ring missratio 0.3 0.6 0.9 0.050.100.150.200.250.300.35 0 10 20 30 40 50 0.1 0.2 0.3 (d6) 1st Ring missratio 0.1 0.2 0.3 0.4 0.050.100.150.200.250.300.35 0 5 10 15 20 Figure 4.9: Delay models. 4.5 Data mining models results 101 The mean hop count and the 1st ring size are also important metrics to the delay model with importances of 0.27 and 0.11 respectively. The miss ratio on the overall network, 1st ring miss ratio, and the neighbor node density have importances below 0.1 and are considered to have no impact on this model output. Figure 4.9(b) shows that for the measures taken per sub-network, when the network has high traffic loads, the number of nodes and the 1st ring size are the most important metrics both with importances of 0.24. The mean hop count is also important to the delay model both with an importance of 0.19. The 1st ring miss ratio and neighbor node density have importances below 0.1 and are considered to have no impact on this model output. Figure 4.9(c) shows that for measures taken over the global network, when the network has low traffic loads, the mean hop count and the 1st ring size are the most important metrics to delay model with importances of 0.45 and 0.37 respectively. The number of nodes is also important to the delay model with an importance of 0.15. The miss ratio on the overall network, 1st ring miss ratio, and the neighbor node density have importances below 0.1 and are considered to have no impact on this model output. Figure 4.9(d) shows that for the measures taken over the global network, when the network has high traffic loads, the 1st ring size is the most important metric for the delay model with an importance of 0.59. The 1st ring miss ratio is also important to the delay model with an importance of 0.33. The other topology metrics have importances below 0.1 and are considered to have no impact on this model output. Under these traffic load conditions, the network becomes saturated and only nodes on the neighborhood of the gateway are able to transmit and receive their packets. When more nodes are around the gateway, most of the packets are transmitted over a single hop resulting in low delay, as shown in Figure 4.9(d4). If the miss ratio on the 1st ring is low then there are less collisions on the gateway neighborhood which causes less retransmissions and the delay is low, as shown in Figure 4.9(d6). Delay and throughput are related performance metrics as shown by the join probability function plot on Fig. 4.10. Low throughputs occur when the delay is high; when packets take more time to reach 108 Topology Aware Channel Assignment Notation Description N(V,E)network graph Vset {u,v,a,b,...}of nodes in the network Eset of links in the network dist(u,v)is the Euclidean distance between uand v %radio receiving and interfering range κnumber of gateways in G Gset of gateways {g1,g2,...,gκ}on the WMN Vfamily of disjoint node subsets of V Vgisubset of Vin which nodes use gateway gi d(u,v)length of the shortest path between vand u ˆ G(v)set of the closest gateways of node v ˆ dvhop distance to the closest gateways of node v P(v)candidate parents of v S(V,ES)shortest path spanning forest of N ESset of links in the forest S Tgi(Vgi,Egi)tree in Srooted in gateway gi Tg,u(Vgi,u,Egi,u)subtree of Tgrooted at node u ch(v)channel assigned to node v λ= 1 traffic generated by each node t(euv)traffic carried the link euv in both directions lS(gi)load of the tree rooted at gateway gi ˆ l(gi)minimum load of the tree rooted at gateway gi ˆ lminimum load on the network lS(v)load of the subtree Tg,u rooted at node v R1Nset of nodes on gateways neighborhood (1st ring) R1N giset of unassigned nodes on the neighborhood of gi R1S giset of assigned nodes on the neighborhood of gi VHset of links in the network (same as E) H(VH,EH)hidden links graph of the network N HR1(VH,ER1 H)1st ring hidden graph M(eab)set of links that are hidden from link eab ∈EH,S m(eab)miss ratio of link eab ∈EH,S mmiss ratio of the network mR1miss ratio of the gateways neighborhood Table 5.1: Notations used on the problem formalization. 5.1 Notation and models 109 5.1.1 Network, interference and traffic model We consider a WMN with fixed located wireless nodes, which are equipped with a single-radio interface. We model the network as a simple graph N(V,E)where Vis the set of nodes in the network, Eis the set of wireless links where E={euv :u,v ∈V∧ dist(u,v)≤%},dist(u,v)is the Euclidean distance between uand v, and %is the radio receiving range. euv represents a link from node uto node v. Nodes uand vare neighbors if euv ∈E. There are κ=|G|gateway nodes which are simultaneously connected to the infra-structured network through a wired network interface and to the WMN through a single-radio wireless interface, where G= {g1,g2,...,gκ} ⊂ V. Each node v∈V\Gcommunicates with the infra-structured network through a single gateway gi∈G. In a network Nthere is at least a family of sets V={Vgi:gi∈G}, where Vgi⊂Vis a set of nodes using a gateway giincluding the gateway gi, where \ gi∈G Vgi=∅and [ gi∈G Vgi=V The distance d(u,v)is defined as the number of edges in the shortest path between uand v. For each node v∈V, it is possible to characterize the set of closest gateways ˆ G(v)defined in Eq. 5.1, where ˆ dv=min({d(v,gj) : gj∈G})is the hop distance between node vand the closest gateways. ˆ G(v) = {gi:d(v,gi) = ˆ dv∧gi∈G}(5.1) If vimmediately precedes node uon the shortest path between uand a gateway gi∈ˆ G(u), then the node vis the parent of uon this path. The children of vare all nodes whose path to the gateway include node v. For each node u∈Vit is possible to define the set of candidate parents P(u)given by Eq. 5.2, which is the set of nodes that are parents of node uon all possible shortest paths between u and each of the gateways gi∈ˆ G(u) P(u) = {v:euv ∈E∧ˆ dv=ˆ du−1∧gi∈ˆ G(u)}(5.2) We assume that communication flows in the stub WMN exist between each node v∈V\Gand one of its closest gateways gi∈ˆ G(v)or 110 Topology Aware Channel Assignment vice-versa. We also assume that the path used by an upstream flow includes exactly the same nodes as the path used by downstream flows; therefore, each node uses its parent as next hop to forward data to the gateway and expects to receive data from the gateway through the same parent. Consider the network in Figure 5.1(a). The path of the upstream flow between node n4and the gateway g1is the ordered list (n4,n3,n2,g1)and the path of the downstream flow is the ordered list (g1,n2,n3,n4), which includes the same set of nodes; in this example, node n3is the parent of node n4. The paths used by these flows form a shortest path spanning forest Sof N, where S(V,ES) = Si∈GTi, and Tiis a shortest path spanning tree of the subgraph of Nthat contains all the vertexes v∈Vgicommunicating through gi. The forest of the flows on the network shown in Figure 5.1(a) is represented in Figure 5.1(b). Each tree Ti(Vgi,Egi)is rooted at a gateway gi∈G. The edge set ESis the disjoint union of the edges set Egi⊂Eof each tree Ti. We define Tgi,v(VTgi,v ,ETgi,v ) as the subtree of tree Tgiwith root at node v, where VTgi,v contains the node vand its children. Figure 5.1(b) highlights the tree Tg2,n6, in this case, VTg2,n6={n6,n7,n8} n3 n2n4 n6 g1 n5 g2 n8 n7 n1 (a) Network N g2 n2 n6 n3 n7 n4 g1 n8 n5 Tg2,n6 n1 (b) Forest Sof N Figure 5.1: Sample network and shortest path spanning forest that illustrate the models used in this work. In the network presented in (a), solid lines represent links in the network, and dashed lines represent flows. (b) is a shortest path spanning forest Sof the network in (a). When at least one node has multiple gateways at minimum distance, there are multiple vertex set families V, each capable of creat- 5.1 Notation and models 111 ing a different shortest path spanning forest. SViis a shortest path spanning forest of Nthat uses the vertex set family Vi. When a node vis assigned to a tree Tgithat do not correspond to a gateway in its set of closest gateways, gi/∈ˆ G(v), the spanning forest resultant from this assignment is not shortest path. Multiple channels will be used to improve the network capacity. There are κchannels available in the network, as many as the number of gateways and trees in the spanning forest. We assume orthogonal radio channels that do not interfere with each other. A static and unique channel is assigned to each gateway gi∈G. Due to this (gateway,channel)unique static assignment, the terms gateway and channel will be used interchangeably throughout this chapter; for clarity we assume that Gis also the set of available channels. Each node v∈Vin the network has its unique radio interface configured on a single channel gi. This assignment is static or quasi-static since it is expected to be changed only when there are significant changes to the network topology. Two nodes uand vcan successfully communicate if ch(u) = ch(v), where ch(v)is the radio channel assigned to node v. When a node vis assigned to channel ch(v) = githe flows of node vtraverse gateway gi∈G. Communications between two wireless nodes through a wireless link will interfere with other communication links in the network due to the broadcast nature of wireless links. Interference is caused by active nodes on the vicinity of both the sender or the receiver of a link. The interference model [13] [43] defines the set of pairs of links in a network that interfere with each other. We assume the interference model as a binary interference model where two links either interfere or not. 5.1.2 Load model As mentioned earlier, we assume that a traffic flow in the network is generated by a gateway gi∈Gand consumed by a node v∈V\G, or vice-versa. We also assume that each node generates and receives a mean bit rate of λ=λd+λubit/s, where λdis the bit rate of the downstream flow generated by the gateway towards a node v, and λuis the bit rate of upstream flow generated by node vtowards the 112 Topology Aware Channel Assignment gateway. We assume that all nodes vgenerate and receive the same amount of traffic λ. This uniform traffic assumption is reasonable on stub WMN of mesh access points (MAPs) since the amount of clients is expected to be statistically the same among the MAPs over the time. Only the links e∈EScarry traffic. We define t(euv) = t(evu)as the traffic carried by the upstream link between uand vplus the traffic carried by the downstream link between vand u, where vis the parent of u. The traffic t(euv)is the traffic generated by uand by all the children of u. In fact, t(euv) = |Vgi,u|λ, where Vgi,u is the set of vertexes of the subtree Tgi,u containing uand its children. In the sample topology presented in Figure 5.1(b), t(en6n5) = |Vg2,n6|λ= 3λ. We assume that nodes are placed dense enough so that most of the paths to the closest gateway are short in terms of number of hops, such as 3 or 4 hops; similar assumptions are made by other works [22]. Thus, there is little chance of spatial reuse within a route tree. When the depth of a route tree becomes large, spatial reuse must be considered to the load estimation, but we consider it as topic for future work. The traffic generated by or to node v∈Vwill be transmitted through d(v,gi)hops inside the WMN until it reaches the destination (gifor upstream, and vfor downstream). Therefore the load imposed to the tree rooted at giby a node vis λd(v,gi)and the total load on the tree rooted at gateway giis λPv∈Vgid(v,gi). Since we assume λ, the mean bit rate, is a constant value and equal for all nodes, we can ignore this factor and let the load on a channel lS(gi) be completely defined by the relationships between links, nodes and gateways on the network Nas given in Eq. 5.3. Note that lS(gi) depends on the family Viused to form S, thus lS(gi) = X v∈Vgi d(v,gi)(5.3) The minimum load on the tree rooted at gican be defined as ˆ l(gi) = P{ˆ dv:gi∈ˆ G(v),∀v∈Vgi}. The minimum total load in the network is the sum of the minimum load on all trees in the network 5.1 Notation and models 113 given by Eq. 5.4. ˆ l=X gi∈G   X v∈Vgi ˆ dv  =X v∈V ˆ dv(5.4) Generalizing, we can obtain the load of the subtree rooted at any node v∈Vby considering that each node has to forward its traffic and also its children traffic; therefore the total load on the subtree Tg,v ⊂Srooted at vis lS(v)given by Eq. 5.5. lS(v) = X a∈VTk,v d(a,v)(5.5) 5.1.3 1st ring - gateway neighborhood We define the 1st ring of a network R1Nin Eq. 5.6 as the set of nodes directly connected to at least one of the gateways, including the gateways; R1Nis also called gateways neighborhood of a WMN. R1N={v:v∈V∧d(v,gi)≤1,∀gi∈G}(5.6) The 1st ring of a gateway R1N gi={v:v∈V∧d(v,gi)≤1}is the set of nodes directly connected to giincluding gi, where Sgi∈GR1N gi= R1N. Note that Sgi,gj∈GR1N gi∩R1N gj≥0, since one or more nodes v∈Vmay belong to the 1st ring of multiple gateways. On the sample network of Figure 5.1(a), R1N g1={g1,n2,n5},R1N g2= {g2,n5}, and R1N={g1,g2,n2,n5}. When channels are assigned to nodes and a shortest path spanning forest Sof Nis formed, we can define the assigned 1st ring of a gateway R1S giin Eq. 5.7 as the set of nodes directly connected to gateway giwhich are assigned to the channel correspondent to gi. In this case, Sgi,gj∈GR1S gi∩R1S gj= 0 since after assignment a node vdoes not belong to multiple trees. On the sample network of Figure 5.1(b), R1S g1={g1,n2}and R1S g2={g2,n5}. R1S gi={v:v∈Vgi∧d(v,gi)≤1}(5.7) The connectivity degree of a gateway is the number of nodes directly connected to gateway giand consequently assigned to the 114 Topology Aware Channel Assignment channel correspondent to gi(|R1S gi|). 5.1.4 Hidden nodes The hidden node problem is defined in [65] using a set of graphs that capture the interferences and the carrier sensing constraints between links in a network: if-graph, tc-graph, and rc-graph. These graphs are defined over the vertex set VH, where VH={euv :euv ∈E}. Please note that an edge in Ebecomes a vertex in the hidden node model described in this section. On this discussion about the hidden node problem we consider directional links, therefore euv 6=evu and the set VHcan be used to reason about bi-directional flows. The if-graph captures the physical interference constraints; an s-graph edge between vertex 1 and vertex 2 indicates that, in order to prevent future collisions, link 1 must be capable of forewarning link 2 not to transmit after link 1 initiates a transmission. The tc-graph models the transmitter-side carrier-sensing; an edge in tc-graph between vertex euv and vertex eab means that euv can and will forewarn eab not to transmit when euv is transmitting. The rc-graph models the receiver-side carrier-sensing; an edge in rc-graph between vertex euv and vertex eab indicates that node bwill ignore node atransmission when node balready senses a transmission on link euv. All links euv ∈Eare considered to create the edges in s-graph, tc-graph, and rc-graph, however links operating on different channels or not carrying traffic are unable to interfere with others. It is possible to obtain the hidden graph H(VH,EH), where EH= TC ∩(IF ∪RC)and IF and RC are respectively the set of edges on s-graph and rc-graph, and TC represents the set of edges that are not on the tc-graph. If a tc-edge does not exist from euv to eab, a transmission on euv will not be sensed by node a. But if a rc-edge or a if-edge exists between euv and eab, it indicates that node bwill ignore node atransmission when node bsenses a transmission on euv (rc-edge), or that there is physical interference from link 1 to link 2 (if-edge). In both cases, node awill interpret it as a collision and we can say that euv is hidden from eab. The 1st ring hidden graph HR1(VH,ER1 H)is the graph formed by all vertices VHon the hidden graph Hand the edges ER1 H, defined in Eq. 5.8, which are edges 5.1 Notation and models 115 between the links hidden from links on the gateway neighborhood, ER1 H={(euv,eab):(euv,eab)∈EH∧euv ∈VR1 H}(5.8) where VR1 Hin Eq. 5.9 is the set of links on the gateway neighborhood. VR1 H,S ={euv :euv ∈VH∧(u∈G∨v∈G)}(5.9) After the channel assignment, we assume that only links euv ∈ES are carrying data flows. In that case, the vertex set of if-graph, tc-graph, rc-graph and hidden links graphs is VH,S, where VH,S = {euv :euv ∈ES}. The interference of other links eab ∈E\ESis insignificant because they are either unfeasible if ch(a)6=ch(b)or do not carry traffic if ch(a) = ch(b). After the channel assignment, the set of edges in the if-graph, tc-graph, rc-graph, and hidden links graphs are respectively IFS,TCS,RCS, and EH,S; in this case, edges (euv,eab)between links operating on different channels ch(u) = ch(v)6=ch(a) = ch(b)do not interfere with each other and are not included in IFS,TCS,RCS, and EH,S. We define M(eab)in Eq. 5.10 as the set of vertexes in VH,S that are hidden from link eab. M(eab)={euv : (euv,eab)∈EH,S ∧eab,euv ∈VH,S}(5.10) The miss ratio m(eab)given by Eq. 5.11 is a measure of the hidden node problem on a link eab, where I(eab) = {euv : (euv,eab)∈(IFS∪ RCS)∧eab,euv ∈VH,S}is the set of links that interfere with link eab. m(eab) = |M(eab)| |I(eab)|(5.11) The network wide miss ratio m=|EH,S|/|IFS∪RCS|is a measure of the hidden node problem on the overall network. The miss ratio on the gateways neighborhood mR1given by Eq. 5.12, is a measure of the hidden node problem on links to and from the gateways, where ER1 H,S is the set of edges that correspond to links hidden from links on the gateway neighborhood after the channel assignment, IFR1 Sand RCR1 Sare respectively the sets of edges on if-graph and rc-graph that affect links on the gateway neighborhood, 116 Topology Aware Channel Assignment ER1 His given by Eq. 5.8, and VR1 His given by Eq. 5.9. mR1=ER1 H,S |IFR1 S∪RCR1 S|(5.12) ER1 H,S ={(euv,eab):(euv,eab)∈ER1 H∧euv,eab ∈EH,S} IFR1 S={(euv,eab):(euv,eab)∈IFS∧euv ∈VR1 H} RCR1 S={(euv,eab):(euv,eab)∈RCS∧euv ∈VR1 H} For the network of Figure 5.1(a), the tc-graph, rc-graph, if-graph, and hidden links graph are presented respectively in Figure 5.2(a), Figure 5.2(b), Figure 5.2(c), and Figure 5.2(d). On the hidden graph (Figure 5.2(d)) an arrow from link euv towards link eab means that euv is hidden from eab. Edges on ER1 H,TCR1and RCR1which correspond to 1st ring are highlighted in red. In the graphs of Figure 5.2 we assume the protocol interference model of IEEE 802.11 [43], where the transmission range and interference range are equal and RTS and CTS control messages are used. After the channel assignment represented in Figure 5.1(b), the links en5g1,eg1n5,en6n2, en2n6,en6n4, and en4n6are unfeasible because their endpoints are assigned to different channels, therefore they are not considered to calculate the miss ratio and are represented in light gray in the graphs of Figure 5.2. Despite ch(n1) = ch(n3)in the forest Srepresented in Figure 5.1(b), the links en1n3and en3n1do not belong to ESbecause they do not carry data flows; the interference of these links on links belonging to the forest Sis inexistent and they are not considered to calculate the miss ratio and are also represented in light gray in the graphs of Figure 5.2. However, if links en1n3and en3n1do not exist in the network represented in Figure 5.1(a), the hidden graph would include more edges, and for instance, links en4n3and en3n4 would become hidden from en1n2. Edges between links operating on different channels are also represented in light gray because they do not interfere with each other after the channel assignment and are not considered to calculate the miss ratio. 5.1 Notation and models 117 g2n5 n5n6 n5g1 g1n2 g1n5 n6n8 n6n2 n6n7n6n4 n6n5 n8n6 n2n3 n2n1 n5g2 n4n3 n2g1 n7n6 n4n6 n2n6 n3n1 n3n4 n1n3 n3n2 n1n2 (a) tc-graph g2n5 n5n6 n4n6 n8n6 n2n6n5g1 g1n5 n2g1 n7n6 n6n5 n5g2 n3n2 n3n4 g1n2 n6n8 n6n2 n1n3 n6n7n6n4 n2n1 n3n1 n4n3 n2n3 n1n2 (b) rc-graph g2n5 n5n6 n4n6 n8n6 n2n6n5g1 g1n2 g1n5 n2g1 n6n8 n6n2 n7n6 n6n7n6n4 n6n5 n2n1 n5g2 n3n2 n3n4 n4n3 n1n2 n3n1n1n3 n2n3 (c) if-graph g2n5 n4n6 n8n6 n2n6 n2g1 n7n6 n5n6 g1n2 g1n5 n1n3 n2n3 n5g1 n2n1 n4n3 n5g2 n3n2 n3n1 n6n2 n6n4n1n2 n3n4 n6n8 n6n7 n6n5 (d) hidden graph Figure 5.2: For the network represented in Figure 5.1, (a) is the tc-graph, (b) is the rc-graph, (c) is the if-graph, and (d) represents the hidden graph. 124 Topology Aware Channel Assignment without causing a simultaneous worsening in at least one other criterion. Three out of the four objective functions are NP-hard problems. Therefore, finding each of the Pareto set solutions is not possible in polynomial time. 5.3 TILIA algorithm In this section we present TILIA, a centralized algorithm for solving the channel assignment problem. Centralized algorithms are very useful in managed WMNs, and a natural solution for stub WMNs, where there is a set of gateways owned by a central entity such as a telecom operator. Centralized approaches have been proposed in recent works [15]. TILIA aims at assigning channels to nodes and defines paths for WMN nodes optimizing topology metrics by the order of importance found on our previous studies [26, 27] discussed in Section 5.2.1. TILIA uses a breadth-first tree growing technique, but instead of growing a single tree, TILIA grows a forest S=Si∈GTiof κtrees rooted at each gateway gi∈G. All the trees grow simultaneously and their union spans the network. TILIA solves more than the channel assignment problem; the tree growing technique also (1) enables the selection of paths between each node and the gateway that has minimum number of hops and hidden nodes, and (2) it helps finding balanced 1st ring sizes. Nodes in the network are assigned to the least used channel and, within that channel, to the least used parent who forwards the traffic towards the gateway. When different channels and parents are equally loaded, the tie-break is made in two stages: first by the distance to the gateway, and then by the number of hidden nodes. 5.3.1 Algorithm description TILIA is introduced in Algorithm 1. The TILIA input is the network graph Nof a WMN and the set of gateways G. The outcome of the algorithm is a spanning forest Sof N. The trees Tgiof a forest Sare initialized with the gateways gi∈G, and Xis initialized as an empty set of forests. The function TiliaMainCycle() is 5.3 TILIA algorithm 125 the core of TILIA algorithm. The output of TiliaMainCycle() may provide one or more forests which are stored in X. When the racing rules established for assigning channels to nodes on the gateway neighborhood result on a tie, this function is called recursively to exploit alternative forests. The BestForest() function selects the forest in Xthat has the topology characteristics that fits better the channel assignment problem defined in Eq. 5.13, Eq. 5.14, Eq. 5.15, and Eq. 5.16. Algorithm 1 TILIA algorithm Require: N(V,E),G Ensure: spanning forest S=Si∈GTiwith roots in G Initialize trees Tgi⊂Sas vertex gi∈G Initialize Xas an empty set of forests TiliaMainCycle(N,S,X) return S:= BestForest(X) In the TiliaMainCycle() function, described in Algorithm 2 each node is visited once. The next node vto be visited is selected by the NextV ertex() function. For the selected node v, the function BestChannels() returns a set C⊂G(Eq. 5.1) of closest gateways to node vthat currently have the minimum load. The function BestParents() selects the set Pof best parents of node v. Finally, the forest Sand the set of selected forests Xare updated in the UpdateForest() function. Algorithm 2 TiliaMainCycle(N,S,X) 1: while VS6=Vdo 2: v:= NextV ertex(N,S) 3: C:= BestChannels(N,S,v) 4: P:= BestParents(N,S,v,C) 5: UpdateForest(N,S,X,v,P) 6: end while 5.3.2 Select the next node to be visited The NextV ertex() function, in Algorithm 3, selects the next node to be visited. Nodes are visited in increasing order of (1) hop count, (2) available nearby channels, (3) available nearby parents, and (4) hidden nodes on links to those parents. 126 Topology Aware Channel Assignment NextV ertex() starts by visiting the nodes that are closer to the gateways. This strategy avoids loops and allows a better control on the gateway neighborhood which is the network bottleneck. Algorithm 3 NextV ertex(N,S) 1: F:= {v: (euv ∈E)∧(u∈VS)∧(v /∈VS)} 2: minhc := min({ˆ dv:v∈F}) 3: X={v: (v∈F)∧(ˆ dv=minhc)} 4: mingw := min({|ˆ G(v)|,∀v∈X}) 5: Y:= {v: (v∈X)∧(|ˆ G(v)|=mingw)} 6: minP:= min({|P(v)|:v∈Y}) 7: Z:= {v: (v∈Y)∧(|P(v)|=minP)} 8: M0(v) = Sp∈P(v)M(epv),∀v∈Z 9: minhidden := min({|M0(v)|,∀v∈Z}) 10: A:= {v: (v∈Z)∧(|M0(v)|=minhidden)} 11: Let rbe one node from Aselected randomly 12: return r The next node to be assigned is selected from F⊂Vof the frontier nodes of the forest Sbeing grown from the network N. A frontier node v∈Fis a node in the network v∈Vthat has not yet been added to the set of nodes VSin the forest, but has at least a neighbor u:euv,evu ∈Ethat was previously included in VS. The minimum distance minhc of a closest frontier node v∈Fto a gateway is calculated in line 2. Then, the set nodes Fis cropped to the subset X(line 3), containing the nodes with smallest hop count to the closest gateway. The cardinal of the set of the closest gateways of each node ˆ G(v) (Eq. 5.1) is calculated in line 4 as the minimum number of channels mingw available on each frontier node v∈X. The set Y, found in line 5, is a subset of Xhaving the smallest number of nearby channels mingw. The minimum number of candidate parents minP of each frontier node v∈Yis calculated in line 6. The set Z(line 7) is a subset of Yin which nodes have the smallest number of candidate parents given by P(v)defined in Eq. 5.2. At line 8, we obtain for each node v∈Zthe set M0(v)of hidden links as the union of the sets of links M(epv)(Eq. 5.10) that are hidden from the link between nodes v∈Zand each of their candidate parents p∈P(v). The minimum cardinality minhidden among the sets of links hidden from a node is calculated in line 9. Finally, the 5.3 TILIA algorithm 127 set A, found in line 10, is a subset of Zin which nodes have the smallest number minhidden of links hidden from links to the candidate parents . It is common to have |A|≈1because each node v∈A has to satisfy the four conditions described above. If more than a node is eligible, then it is selected randomly. 5.3.3 Select channels and parents The function BestChannels() shown in Algorithm 4 selects the candidate less loaded channels to be assigned to the node vreturned by NextV ertex() function. The set of nearby channels Cnear is found at line 1. The set Cnear contains the channels that were previously assigned to all neighbors of v, instead of considering only the channels correspondent to the set of closer gateways of vgiven by ˆ G(v). At line 2, we calculate the minimum load minlwhich is the load lS(gi)(Eq. 5.3) of the less loaded tree Tgi⊂S. At line 3, BestChannels() returns a set containing all nearby channels that carry exactly minlload. Algorithm 4 BestChannels(N,S,v) 1: Let Cnear := {ch(u) : evu ∈ES∨euv ∈ES} 2: Let minl:= min({lS(gi) : gi∈Cnear}) 3: return {gi∈Cnear :lS(gi) = minl} By considering the channels of all the neighbors of v, including those nodes u /∈P(v), the paths between vand the gateway are enabled to have more hops than the optimum distance ˆ dv, what means that the total load on the forest may be higher than the minimum load ˆ lof the network. In some scenarios this relaxation may be useful to guarantee load balancing between channels. Consider for instance the topology represented in the Figure 5.3(a), with 25 nodes including 2 gateways. The distance of each node to the closest gateways is presented in the first line of Table 5.2 and the minimum load for this network ˆ l=43. By assigning nodes to channels in order to get the minimum load and the best possible load balance, we obtain the forest in Figure 5.3(b); this channel assignment has obvious low load balance since the load on gateway g1 (l(g1) = 15) is much smaller than the load on gateway g2(l(g2) = 28), 128 Topology Aware Channel Assignment as shown in the second line of Table 5.2. Another channel assignment scheme could be the forest represented in Figure 5.3(c); this channel assignment has non optimal total load l(g1)+l(g2) = 45 >ˆ l= 43, but the load balance between channels is near optimal since l(g1)≈l(g2) (3rd line of Table 5.2). k lc gg1 g2 d mh jb f a e i u v w t s p q r o n (a) Network topology before channel assignment. k lc gg1 g2 d mh jb f a e i u v w t s p q r o n (b) Forest that minimizes the total load. k lc gg1 g2 d mh jb f a e i u v w t s p q r o n (c) Forest that maximizes the load balancing. Figure 5.3: Illustration of the trade-off between minimizing the total load and have load balancing. Figure Load from each node l(g1)l(g2)Total load b c d f g h k l m a e i j p q r n t u v w o s 5.3(a) 1 2 3 2 3 - - ˆ l=43 5.3(b) 1 2 3 2 3 15 28 43 5.3(c) 1 2 3 3 4 22 23 45 Table 5.2: Loads for the network and forests presented in Figures 5.3(a), 5.3(b), and 5.3(c). The function BestParents() shown in Algorithm 5 selects the best parent uof node vby considering three conditions: minimum distance to the gateway, minimum load, and minimum number of hidden nodes. The BestParents() function returns a set Pof parents, if multiple parents are equally good on the gateway neighborhood, considering the hop count, the load, and the hidden nodes. In line 1 we obtain the set of candidate parents Pall of node v which are the parents that are operating on the channels on set C returned by BestChannels(). In line 2 we calculate the ring of the candidate parent that is closer to its gateway. In line 3 we obtain the set of candidate parents Pring that are at ring hops from their 5.3 TILIA algorithm 129 gateways. At line 4, we calculate the minimum load minload among candidate parents. In line 5 the set of candidate parents is cropped to Pload keeping only the candidate parents that have the minimum load minload. In line 6 the minimum miss ratio minmis calculated; for all links between vand each candidate parent u∈Pload, we calculate the link miss ratio as given by Eq. 5.11, minmbeing the minimum value found. In line 7 we obtain the final set of candidate parents Pcandidates that present less problems with hidden nodes, that is, those whose miss ratio of links between vand each parent u∈Pcandidates is minm. Algorithm 5 BestParents(N,S,v,C) 1: Pall := {u: (ch(u)∈C)∧(euv ∈V)} 2: ring := min({d(u,ch(u)) : u∈Pall}) 3: Pring := {u∈X:d(u,ch(u)) = ring} 4: minload := min({lS(u) : u∈Pring}) 5: Pload := {u∈Pring :lS(u) = minload} 6: minm:= min({m(euv) : u∈Pload}) 7: Pcandidates := {u∈Pload :m(u) = z} 8: if |Pcandidates|= 1 then 9: return P:= Pcandidates 10: end if 11: if ring > 1then 12: p:= node on Pcandidates selected randomly 13: return P:= {p} 14: else 15: return P:= Pcandidates 16: end if It is common to have |Pcandidates|≈1because each node v∈ Pcandidates has to satisfy the tree conditions described above. When |Pcandidates|= 1, the BestParents() function returns Pcandidates as shown in lines 8 and 9. If multiple candidate parents are found, the returned candidate parent set depends of the distance to the gateway of the nodes being assigned. The channel assignment on the gateway neighborhood should be done carefully since (1) the topology of this part of the network has a great impact on the performance of the network [26, 27], and (2) it affects the output forest dramatically. If the parents on the Pcandidates set are located beyond the 1st ring (line 11), the BestParents() function returns one random element of Pcandidates as shown in lines 12 and 13. If the 130 Topology Aware Channel Assignment parents on the Pcandidates set are gateways or are located on the 1st ring (line 14), the BestParents() function returns the Pcandidates set with all its elements as shown in line 15. 5.3.4 UpdateForest() and recursiveness After the selection of the best parent of our node v, the function UpdateForest(), shown in Algorithm 6, is called in order to update the forest Sthat is being built on the TiliaMainCycle(). Node v is added to VSand the edge euv is added to ESon line 2, where uis the first element of P(line 1) and Pis the set returned by the BestParents() function. When appending vcauses VSto be complete (line 3), i.e. containing all nodes in the network N, then the spanning forest Sis appended to the set of forests Xin line 4. Algorithm 6 UpdateForest(N,S,X,v,P) 1: Let u:= first element of set P 2: Append vto VSand edge euv to the tree Tch(u)⊂S 3: if VS=Vthen 4: Append Sto the set of forests X 5: end if 6: for all other p∈Pdo 7: Initialize S0:= S 8: Delete euv from the tree T0 ch(p)⊂S0 9: Append epv to the tree T0 ch(p)⊂S0 10: if VS0=Vthen 11: Append S0to the forests set X 12: else 13: TiliaMainCycle(N,S0,X) 14: end if 15: end for If the BestParents() function returns a set Pwith multiple parents, we start to grow a new forest S0for each candidate parent p∈P(line 6). Each new forest S0is a clone of the forest Sgrown so far (line 7). The forests Sand each of the new forests S0, are distinguishable only by the edge that links node vto the forest (lines 8 and 9). Here again, if VS0is complete (line 10) then the spanning forest S0 is also appended to the set of forests X(line 11). It is not expectable that VS0is complete in this situation, because the BestParents() 5.3 TILIA algorithm 131 function returns a set Pwith multiple parents only on the gateway neighborhood and it is expectable that there are nodes on the network farther from the gateways; this line was added to the algorithm to keep it robust. If S0is not yet complete when appending v (line 12), then the TiliaMainCycle() is called (line 13) to continue growing the forest S0recently cloned from S. Calling the TiliaMainCycle() inside the UpdateForest(), which in turn is called inside TiliaMainCycle(), transforms the later in a recursive function. However, the recursiveness is used only to overcome ties on the assignment of nodes on the gateway neighborhood. Assigning first the nodes with less channel and parent options (NextV ertex function) avoids most of the ties because nodes that have connectivity through a single channel are assigned first and their contribution on the channel load is taken into account when assigning nodes that are equally distant to several gateways. By avoiding ties, the recursiveness is also avoided and the complexity of TILIA reduced. 5.3.5 Select the best forest The BestForest() function shown on Algorithm 7 returns the forest that better fits as a solution to our channel assignment problem. Each forest S∈X is evaluated using the composed topology metric tmet defined as θin Eq. 5.17 (lines 1 and 2). The forest with highest tmet is returned by BestForest() as the solution for the network N (line 4). Algorithm 7 BestForest(X) 1: for all S∈X do 2: Calculate tmet for forest S 3: end for 4: return forest Swith highest tmet tmet has five components corresponding to measures of (1) the total load θlgiven by Eq. 5.18, (2) the load balancing between trees in different channels θlb given by Eq. 5.19, (3) the total number of nodes on the 1st ring θr1given by Eq. 5.20, (4) the balance between the size of 1st ring around each gateway θr1bgiven by Eq. 5.21, and (5) the 1st ring miss ratio θmgiven by Eq. 5.22. The highest values 132 Topology Aware Channel Assignment of each of the components tmet are found on the forest Sthat better fits our channel assignment problem formulated earlier. All components of tmet (Eq. 5.18 to Eq. 5.22) are in the interval ]0,1]. θ=klθl+klbθLb +kr1θr1+kr1bθr1b+kmθm(5.17) θl=ˆ l Pgi∈GlS(gi)(5.18) θlb =Pgi∈Gl(gi)2 |G|Pgi∈Gl(gi)2(5.19) θr1=Pgi∈G|R1S gi| |R1N|(5.20) θr1b=Pgi∈G|R1S gi|2 |G|Pgi∈G|R1S gi|2(5.21) θm= (1−mR1)(5.22) The total load component θl, on Eq. 5.18, is the ratio between the minimum load ˆ lof the network Ngiven by Eq. 5.4 and the sum of loads lS(gi)(Eq. 5.3) of trees in the forest S. In the best case θl= 1, which occurs when the load on the forest Sequals the minimum load ˆ l; if the load on the forest Sis much higher than ˆ l, then θlapproaches 0. The load balancing component θlb, in Eq. 5.19, is calculated using the by Jain fairness index [97], and represents how fair load is distributed among channels. In the best case θlb =1, which occurs when the load on trees of the forest Sis equally distributed; if the loads on trees of the forest Shave significant differences, then θlb approaches 0. The total number of nodes on the 1st ring component θr1, in Eq. 5.20, is the ratio between the sum of the connectivity degree of the trees in the forest S, and the cardinal of the set R1Nof nodes neighbors to gateways in the original network N. In the best case θr1= 1, which occurs when all nodes in the neighborhood of gateways of the original network are assigned to one of their closest gateways; if several nodes are assigned to channels correspondent to 5.4 Evaluation 133 gateways that originally were not on their neighborhood, then θr1 approaches 0. The 1st ring balance component θr1b, in Eq. 5.21, is calculated using the Jain fairness index and measures how fair are distributed the 1st ring nodes among the gateways. In the best case θr1b= 1, which occurs when the sizes of the 1st ring of each of the trees in the forest Sare equally distributed; if the 1st ring sizes of trees in forest Shave significant differences, then θr1bapproaches 0. The 1st ring miss ratio component θm, in Eq. 5.22, measures the hidden node problem on the gateways neighborhood using the miss ratio defined in Eq. 5.12. In the best case, θm= 1 which occurs when the number of hidden nodes in the gateways neighborhood is 0 and the 1st ring miss ratio is 0; if there is a substantial number of hidden nodes in the gateways neighborhood, when compared to links that interfere with each other on the 1st ring, then the 1st ring miss ratio becomes higher and θmapproaches 0. We introduced weights on the calculation of topology metric θ, because it may be difficult to find a forest Sthat maximizes all components. Each of the components contribute with different weights (kl,klb,kr1,kr1b,km) to the topology metric θaccording to the impact these topology characteristic have on the network performance studied in previously published work [27]. We propose for our algorithm kl= 0.5,klb = 0.15,kr1= 0.1,kr1b= 0.1and km= 0.15. These values were found to be optimal to the set of 200 scenarios in which we tested TILIA. 5.4 Evaluation In this section, we evaluate TILIA. Our experiments try to answer two questions: (1) What are the performance gains of the TILIA channel assignment algorithm when compared with state-of-the-art approaches under TCP and UDP traffic? (2) How accurate is the topology metric tmet to predict the performance of a WMN?