Link Allocation Scheduling with Service Provisioning Approach in Wireless Mesh Networks

Electrical-Telecommunications Engineering Master Thesis

Abstract

Wireless mesh networks are one of the technologies of interest for creating next generation wireless networks. Because these networks can provide users with a wide coverage area and high capacity with low power consumption and low cost due to less path loss and also reducing the effect of the shadowing factor, which is due to their multi-step feature. In contrast to these advantages, these networks face the problem of not being easily expandable. Because the traffic that is relayed by multiple interfaces needs more bandwidth, it will suffer more delay and therefore the quality of service will decrease. Increasing the distance of relays in order to reduce their number will also reduce the speed of links. An increase in the number of network users also leads to more collisions and as a result, a further decrease in throughput. An increase in the area covered by the network will result in a drop in throughput and an increase in delay due to the need for more relays. Therefore, proper efficiency in a mesh network must be achieved by solving an optimization problem that includes effective factors (such as delay, throughput, etc.). Solving this type of problem in recent years as an NP-Hard problem has attracted a lot of attention in the field of problems related to wireless mesh networks. In this thesis, a new algorithm is presented to improve centralized scheduling and optimal allocation of time windows to network nodes, taking into account the reusability of the frequency space, the end-to-end delay guarantee performance of the user is presented. The algorithm proposed in this research for the approximate solution of the scheduling optimization problem is based on the genetic algorithm. The proposed algorithm has the ability to adapt to different parameters (such as efficiency, fairness, etc.) based on the operator's wishes. The result of the implementation confirms the improvement of the results compared to the previous methods. 1-1 Introduction, the perspective of wireless mesh networks The excessive prevalence of the Internet in today's communication world has been such that the high-speed wired access structures do not meet the needs of many areas. Cabling high-speed lines for all these service providers is very expensive and time-consuming. Today, new technologies [a1] have been introduced to replace these wired networks. These alternative networks are high-speed wireless networks that provide fast access to the Internet when the wired network structure is unable to meet the needs of users due to the high volume of applicants or old networks, and eliminate the additional costs associated with updating the cabling structure. Traditional wireless systems are often used for commercial purposes in places where high speed and accuracy are needed, and in personal cases or homes, cheap technology should be used. Now, technical advances have made this possible and created many opportunities for Internet service providers. Wireless Mesh Networks [1] (WMN) is one of the key and influential technologies during the next decade that will play a very important role [a2] in the future generations of wireless and mobile networks. With the help of these networks, the dream that has been in the minds of many users of various types of networks around the world for a long time is getting closer to being realized; And this dream is nothing but connecting to the network at any time, at any moment, with the utmost simplicity and the lowest cost.

These networks include mesh routers [a3] and also mesh users, where mesh routers have the least possible mobility and form the backbone of the WMN. They provide access to the network for both mesh users and normal users. Figure 1-1- Wireless mesh network The wireless mesh network is completely compatible with the structure of the wired network, and each transmitter provides access to the Internet for users connected to it and will act as a part of the network structure. Network traffic will pass through multiple [a4] relays, allowing different stations to connect even if they are out of network range. Wireless mesh networks are the most flexible and least expensive way to expand high-speed Internet services that can be used mainly for personal use.

Each wireless relay in this network is an element of the network structure and can transmit information.

Each wireless relay in this network is an element of the network structure and can deliver information from the wireless mesh network to the destination. This type of network eliminates the problems of obstacles in the radio environment and makes the network expandable very cheaply and conveniently, because in this structure each relay only needs to communicate with its adjacent relay. In case of any obstacle, the network traffic can be redirected to another relay, of course, without the need for any change in the location of the central radio to communicate with remote geographical locations. Since the area covered by each access point can be expanded around the obstacles, the number of access points is reduced. Wireless mesh networks have cheap expandable technology and are suitable for high-speed access in remote geographical areas. RoofNet [a5] is an example of these networks. This network usually includes a number of wireless access points that are installed on the windows and roofs of houses, and the information platforms of home computers are transmitted by wire to the antennas and are transferred from one antenna to another antenna to reach a gateway [2] of the Internet [a6]. (1-2)).

Figure 1-2- SS to BS traffic transmission through[a7] relays

One of the widely used standards that supports wireless mesh networks in its structure[a8] is the 802.16 standard with the brand name WiMAX[5]. This standard defines the transport media access control protocol for urban wireless networks. In this standard, arrangements have been made to support the quality of service, in terms of the quality of cabled access networks.  With the help of standard 802.16 mesh mode, it is possible to quickly provide reliable wireless connections with a coverage area much greater than the reachable radius in the physical layer. Therefore, the 802.16 standard mesh mode with MAC based on TDMA technology is a suitable solution for implementing wireless mesh networks. Wireless mesh networks are fixed multi-hop networks that are used to provide wireless access in a wide geographical area [1, 2, 3]. The main challenge in these networks is to provide high quality service to their users. By introducing a new MAC that uses TDMA technology, the 802.16 standard provides the ability to provide quality of service for these networks. 1-2 The necessity of guaranteeing quality of service, the main challenge in wireless mesh networks The rapid growth of wireless networks at the same time as the creation of new services has raised many diverse research topics in these networks. In the meantime, many of these issues are related to guaranteeing the quality of service. The becoming of data, audio and video transmission networks requires [a10] various services. In such an environment and in order to create a suitable network in which users' expectations are met satisfactorily, the control of network behavior in order to guarantee the quality of service of different users becomes particularly important. An important point that should not be left out of mind is the efficiency of network components and resources. Otherwise, the price and complexity of the equipment required to provide the service will not be acceptable.

In the early years, the Internet was mostly used to exchange information between network researchers. At that time [a11] electronic mail, file sending [6] and remote network access [7] were the main uses of the Internet. The expansion of demand caused major changes in the use of the Internet network. New applications such as audio-visual group conferences, strong search centers in the network, Internet telephone calls and electronic commerce have made the need to guarantee the quality of service inevitable. Currently, the provision of services in the Internet network is done in the form of "best [a12] effort[8]" in which there is no guarantee for the quality of the service provided. When a user accesses the network, some parts of the network may be so congested due to lack of proper timing in the use of resources that the traffic is not transmitted or delayed so much that it does not actually meet the user's needs. The characteristics of the discussed service are as follows:

The network does not reject any type of traffic when establishing a connection due to the lack of resources necessary to provide the service.