Optimizing the number and location of routers in wireless mesh networks

Dissertation

To receive a Master's degree

Information Technology Engineering - Computer Networks

Abstract

Wireless mesh networks include mesh routers and mesh clients, which mesh routers form the backbone of the mesh network with the least mobility. Routers and clients in the mesh network access the Internet through the gateway. Today, wireless mesh networks provide wireless services in a wide range of applications, at personal, local, university campuses and urban areas. One of the main challenges in wireless mesh network design is determining the location of mesh routers in the network. In fact, determining the location of mesh routers in building a wireless mesh network is the first step in ensuring optimal performance in the network. A basic problem in the placement of mesh routers is to find the number of routers required by the mesh in order to meet the criteria required by this network. In this thesis, an innovative method using genetic algorithm is proposed to find the number of routers and their optimal position. The proposed method can provide the necessary criteria of this network effectively. The results indicate the acceptable efficiency of this method. The simulation results show that the proposed algorithm is better than similar methods in terms of the number of routers and the amount of coverage space corresponding to it.

Keywords: wireless mesh network, location determination of routers, coverage, connection, genetic algorithm.

1 Chapter 1 Introduction to wireless mesh networks

In this chapter, an introduction about wireless mesh networks, their applications and characteristics will be presented, then the topic selected in This thesis and its importance are reviewed. At the end, the structure of the thesis is defined.

(Images are available in the main file)

The initial implementations of wireless networks based on the IEEE 802.11 standard consist of several BSS[2]. Inside each BSS there is a station called access point (AP[3]) which is used to access the wired structure, BSSs are connected through Ethernet LANs (wired structure) or access the Internet. As shown in Figure 1-1, there are two base stations and an access point is placed in each. Such networks are single-stage networks [4] with fixed architecture, which have low flexibility and high implementation cost. In order to ensure the mobility of nodes and the multistep [5] of the network, ad hoc mobile networks [6] were created that form the unstructured state. In this case, the stations are connected without any central coordinator such as an access point or a distribution system (wired structure) and the nodes are completely autonomous (Figure 2-1) [1].

(images are available in the main file) Mobile networks are not suitable for many applications because as mobility and multi-hop are required, Internet access and integration with other networks are also required. Therefore, the structured mode [7] and the unstructured mode have been combined and created a new type of multi-step network called wireless mesh. Wireless mesh network is a network consisting of several nodes that are connected wirelessly, and as the name suggests, there is a communication path between all nodes directly or indirectly. Each node not only acts as a host [8] but also acts as a router and sends packets to other nodes that may not be in the transmission range [9] of the destination node. Figure 1-3 shows an overview of the mesh network (pictures are available in the main file) A wireless mesh network is a self-managing network [10] with automatic adjustment [11] in which the nodes automatically establish and maintain communication among themselves. This feature has created many advantages such as low cost, easy network maintenance, robustness and providing reliable service for wireless mesh networks. Nodes such as (desktop, laptop, PDA, etc.) are equipped with wireless network cards and are directly connected to the mesh network [1]..     Customers without a wireless card access the mesh network by connecting to wireless mesh routers, for example, with Ethernet. Therefore, wireless mesh networks help users to be active anytime and anywhere. In addition to the capabilities of the gateway [12] in mesh routers, it is possible to integrate the wireless mesh network with existing wireless networks such as sensors [13], Wi-Fi, Wi-MAX, Wi-Media and so on. gives As a result, through an integrated mesh network, users within the mesh network can use the services available in other networks. Wireless mesh networks for a large number of applications such as home networking. are used [1].

In the following sections, wireless mesh networks are introduced from different aspects.

1-2 Mesh network architecture

Wireless mesh network includes two types of nodes: 1-router and 2-user.

A wireless mesh router, in addition to routing capabilities like previous wireless networks, includes additional routing capabilities to set up and provide mesh networking. To further improve the mesh network, a mesh router is usually equipped with several wireless interfaces [14] that are based on different or the same wireless access technologies. Compared to previous routers, a mesh router can achieve the same coverage with less transmission capability through multi-hop communication. Despite this, wireless mesh routers and previous routers are built on the same hardware platform. Mesh routers can be built based on embedded computer systems or based on multipurpose computer systems [15]. Mesh users also have enough capability for mesh networking and therefore can work as a router. Although there are no gate or bridge functions in these nodes. Also, mesh clients usually have only one interface. Hardware and software platforms are easier to build for mesh users than routers. Mesh applications have more variety of products than routers and can be desktop, laptop, PDA and so on. to be 

Wireless mesh network architecture is classified into three main groups:

Structured backbone network [17]: This type of wireless mesh network includes mesh routers and creates an infrastructure for users to connect to them. This model can use several types of radio technology that mostly use IEEE 802.11.     Mesh routers create autonomous and self-healing [18] links between themselves. With the ability to be a gateway, mesh routers can connect to the Internet. This application creates a backbone for traditional clients and allows the integration of the wireless mesh network with existing wireless networks. Through the gateway capability in mesh routers, traditional Ethernet-mediated clients can connect to mesh routers through Ethernet links. For clients with similar radio technologies, they can communicate directly with mesh routers (Figure 1-4). This category is the most commonly used type of mesh networks. For example, neighbor communication networks [19] can use this model. Mesh routers are placed on the roof of houses and are used as an access point for users inside the house. Usually, two types of radios are used in routers: 1- for backbone communication and 2- for user communication.

 Mesh backbone communication can be established by using many limited communication techniques, such as directional antennas [2].

(Images are available in the main file)

Network: This user method creates communication among user devices. In this type of architecture, client nodes form a real network to perform routing and configure capabilities such as creating applications for clients, so the mesh router is not used for this type (Figure 5-1). In this architecture, a packet goes through several steps (multiple nodes) to reach the destination node. This method usually uses one type of radio for devices. In addition, requirements for end users increase compared to the first model because in some applications, end users must perform additional functions such as routing and automatic adjustment.