Keywords
|
| load, energy, table-driven, on-demand, congestion, delay |
INTRODUCTION
|
| WMN is a communication network made up of radio nodes arranged in mesh topology. A mesh topology is the one in which every node has a connection to every other node in a network coverage area. There are two types of mesh topologies: complete or full mesh and partial mesh[1]. In Complete or Full Mesh Topology every node in the coverage area is connected to every other node in the network. It provides the greater amount of redundancy. Hence in the event that if any one of those nodes fails, the network traffic can be directed to any of the other nodes that have a route to the destination. Full wireless mesh is difficult to achieve on a large scale using Mesh Routers (MR); however, small-scale area like offices or small campus may be ideal. In Partial mesh topology some nodes are connected to every other node in the network, but others are only connected to two or more nodes in the network. Hence it provides less redundancy than full mesh topology. It is commonly found in either small or large scale networks or for fulfilling the last mile connection to a full meshed backbone. |
| Wireless Mesh Networks often consists of mesh clients, mesh routers and gateways. Mesh Clients (MC) are the enduser devices such as laptops, PDAs, smart phones, etc, that can be used for accessing the applications like email, VoIP, game, location detection, etc. through the network. These devices are mobile but have limited power and routing capability and it may or may not be connected to the network. The topology in the mesh network is changed frequently because the mobile nodes are dynamically connected with each other[1]. WMN has a more planned configuration and may be deployed to provide dynamic and cost effective connectivity over a certain geographic area. The Mesh Routers are static in nature and it forwards the network traffic between Mesh Clients and gateways. Transmission power consumption is low for multi-hop communication network. In addition to that, the Medium Access Control (MAC) protocol in a mesh router supports multiple-channels and multiple interfaces to provide scalability in a multi-hop mesh environment. Gateways may or may not be directly connected to the wired network ie) Internet[2]. |
| WMN is primarily appropriate for impenetrable areas where creating wired network buildings or areas is difficult, disaster recovery etc. WMNs will greatly help the users to be available on-line anywhere at any time by connecting to mesh routers [3]. Furthermore, the mesh routers have the functionality to connect WMNs with various existing wireless networks such as wireless sensor networks, cellular, adhoc networks, wireless-fidelity (Wi-Fi) and worldwide interoperability for microwave access (WiMAX)[1]. |
| The traditional ad-hoc routing protocols can also be used in WMN. These protocols are classified into two types such as proactive (table-driven) and reactive (on-demand). In proactive protocols[4] [6] each node maintains a routing table, which contains routes to all the other nodes in the network. The routes are found and stored even if they are not needed. The number of tasks is carried out to maintain the recent routing information but it increases the considerable overhead and bandwidth consumption in the network. Destination Sequenced Distance Vector (DSDV) [7][5] routing protocol is an example for proactive routing protocol. |
| Reactive protocols[7] take a indolent approach to routing. In contrast to table-driven routing protocols all up-to-date routes are not maintained at every node, instead the routes are created as and when required. When a source wants to send messages to a destination, it invokes the route discovery mechanism to find the route to the destination. It sends the RREQ and RREP packets in the network. The route remains valid until the destination is reachable or until the route is no longer needed. This approach is not suitable for operations that require immediate route availability as there is a delay for finding a route. Adhoc On Demand Distance Vector (AODV)[8] routing protocol is an example for reactive routing protocol. |
| The routing protocol performs the process of finding out the route from the source to the destination. The main aim of the routing process is to provide reliable transmission for ensuring the quality of service (QoS) in the network. The efficient route construction for transmitting the packets from the source to the destination is one way of providing QoS to the users in the network. The efficient route can be constructed by considering the nodes with certain constraints. Several routing protocols are available in adhoc networks; however, these protocols cannot be used directly in WMN due to their varying traffic patterns, gateway functionalities and its bandwidth requirements. The existing adhoc routing protocols constructs the route based on minimum hop count. This default route construction process is not assured that will always lead to quick and successful delivery of packets to the destination. Sometimes the node failure, congestion, link breakage and inefficient utilization of bandwidth may be occurred. The above difficulties may be overcome by constructing a route based on quality metrics such as energy, queue length, link quality, bandwidth, etc. This paper discusses the energy based and queue based routing algorithms and protocols which have been proposed by various researchers in the area of WMN. |
FEATURES OF WIRELESS MESH NETWORK
|
| The following are the various features[9] of WMN. |
| Self healing and Self Configuring: WMNs are flexible in network architecture and are not dependent on the implementation and the protocols. The main features of WMN such as self healing and self configuring enhances the performance of the network further. Due to the self healing feature of WMN, it automatically finds the fastest and reliable path when the nodes lose their connectivity and blocked in the network. The self-configuring feature can easily add new nodes, remove or relocate existing nodes to or from the network without human intervention. Hence, because of these features, the end users demand can be fulfilled and the network set-up time and maintenance cost can be reduced. |
| Low Utilization Cost: Mesh routers are wireless and static; they have the facility to service in multi-hop environments. In large areas, the uses of wireless routers are cheaper when compared to single hop router with wired connection. In general wired connections are more expensive to install and maintain. The deployment of WMN leads to low operation cost due to faster installation and maintenance. |
| Better Reliability: In WMN, the packets are transmitted from source to destination through multiple paths. The multiple paths are used as alternate paths in case of failure. The alternate paths are preferred to minimize the bottleneck in congested area of the network. Using multiple paths, the traffic loads can be balanced in the network. Load balancing and minimizing the bottleneck through alternate path can considerably increase the network reliability in WMN. |
| Scalability: In traditional wireless networks once the number of nodes increases, the performance decreases. However in WMNs once the number of nodes increases, the performance also increases by providing alternate routes. Due to the scalability feature, the mesh networks can handle hundreds or thousands of nodes. By adding more routers, the network can get rid of the weak signals and dead zones. |
| Interoperability: WMN has a feature of hybrid multi-point to multi-point architecture which is well-suited with existing standards of Cellular, WiMAX, Wi-Fi, Zigbee, Bluetooth, Sensor, MANET, Vehicular, etc. Thus it is more attractive for incremental deployment and reuse of existing infrastructures. All the above existing standards can be configured with a WMN and communicate with each other through wireless mesh backbone. |
| NLOS Configuration: They are very useful in Non-Line-of-Sight (NLoS) network configurations where wireless signals are intermittently blocked by the highest buildings. For example, in an amusement park a Ferris wheel seldom blocks the signal from a wireless access point. |
| Network Capacity: WMN supports the feature of Multiple Channels and Multiple Interfaces. The routers in the mesh network are provided with multiple interfaces which increases the throughput and capacity of the network considerably [10]. In infrastructure-based wireless networks, multiple channels are incorporated by assigning different channels to adjacent mesh routers to minimize interference |
ARCHITECTURE OF WMN
|
| Depending upon the deployment configuration, WMNs can be categorized into the following three types [3]: Client, Infrastructure and Hybrid WMN. |
| A. Client Wireless Mesh Network |
| The Client mesh network offers peer-to-peer connection among the client devices. The devices are usually has a single radio. An important aspect of this type of WMN is that the network consists of fully mobile devices without a wireless backbone. Thus, it forms a conventional adhoc network. The client nodes form the real network to perform routing and self-configuration functionalities. |
| B. Infrastructure Wireless Mesh Network |
| In infrastructure WMN, the mesh routers provide an end-end connectivity to mesh clients and form a high bandwidth wireless backbone. This type of WMN can be formed by using the different types of radio technologies in addition to IEEE 802.11 technologies. The conventional clients can directly communicate with the mesh routers if both have the same type of radio technology. Otherwise, the clients can communicate with the mesh routers only through their base stations which have Ethernet connections. The mesh routers with the gateway feature can be connected to the Internet. This approach incorporates the WMNs with existing wireless networks. The mesh routers are static in nature provide the features of self-healing and self-configuring functionality among the links themselves. |
| C. Hybrid Wireless Mesh Network |
| Hybrid Wireless Mesh Network is an elegant version of WMN. As the name indicates it is a blend of Infrastructure and Client WMN and its architecture is shown in Fig.1. The Mesh Routers form a Mesh backbone infrastructure while the Mesh Clients involve in the routing and forwarding of packets. The The Mesh clients can access the network through mesh routers and they can directly communicate with other networks such as Wi-Fi, WiMAX, cellular, and sensor networks. The routing facility of clients offer enhanced connectivity and coverage within WMNs. |
| The Mesh clients are mobile devices such as cell phones, laptops, PDA etc which usually run on batteries while the mesh routers and gateways are static nodes. The mesh backbone connected to Internet through Gateway is a wired connection whereas the other connections between Mesh Clients and Mesh Routers in the network are wireless connections. The Mesh Routers are connected to each other to share its information. The Internet connection is an optional one. The Mesh Clients and Mesh Routers are connected in a multihop fashion. Each Mesh Router and Mesh Client are connected to more than one Mesh Router and Mesh Client, so that if a Mesh Router or Mesh Client in the network fails, it automatically finds an alternate path for sending data to the destination. |
LOAD AND ENERGY BASED ROUTING ALGORITHMS AND PROTOCOLS IN WMN
|
| A. Load Aware Routing Approaches |
| Galvez, J. J. et al[12] proposed a distributed load-balancing protocol(GWLB), where gateways coordinate to reroute traffic flows from congested gateways to free gateways. In other words, it reroutes the traffic from congested to uncongested domains by achieving better capacity utilization and higher network throughput. In this distributed scheme where gateways coordinate and exchange information about their associated nodes and their demands. For that purpose, the mesh network is divided into domains; each domain can be defined as set of sinks served by gateway in which it receives internet traffic. Each domain is assigned with a specific capacity and it is compared against the load in the particular domain. The load is represented as the demands of the sinks. If the load exceeds the tolerable capacity then the domain is considered as overloaded. To avoid the overloaded domain or congestion, the proposed protocol reroutes the traffic. This scheme does not require any computation at mesh routers and it achieves improvement in scenarios with load imbalance over shortest path routing. |
| Li Hongkun et al[13] studied the selection of a path with the minimum cost in terms of expected end-to-end delay (EED) in a multi-radio multi-channel wireless mesh network. The new EED metric takes the transmission delay as well as the queuing delay of the buffer due to MAC layer. In addition to minimizing the end-to-end delay, the EED metric implicitly provided load balancing routing. They developed a generic approach to compute the multi-radio achievable bandwidth (MRAB) for a path taking the impact of inter-/intra-flow interference and space/channel diversity into consideration. A practical scenario is considered in which an end-to-end path may consist of both multi-radio hops and single-radio hops with multiple channels which they do not interfere with each other but the interference problem exist within the same channel. They developed a sub-path based iterative approach to model the complex interactions among inter-flow interference, intra-flow interference and simultaneous transmission due to space and channel diversity. The MRAB is combined with the EDD to form the metric weighted end-end delay (WEED). This metric better capture the effect of interference and channel diversity. This work also proposed a distributed WEED based routing protocol for MR-MC wireless networks. |
| Choi, K. W et al[14] proposed a load-aware routing scheme for wireless mesh networks (WMNs). This load-aware routing scheme can balance the load and thus enhance the overall network capacity. This routing scheme maximizes the degree of user satisfaction using the dual decomposition method. In this proposed scheme, for maintaining the load control, the entire network is divided into multiple clusters. A cluster head of each cluster estimates the traffic load of its own cluster. When the estimated load gets higher, the cluster head increases the routing metrics of all the routes passing through that particular cluster. Based on the routing metrics, the traffic takes a diversion to avoid overloaded areas and achieves global load balancing. This proposed scheme need an uninterrupted adaptation of the link costs to the traffic load, which may lead to instabilities and link/node failures[15]. |
| Al-Kharasani et al[16] proposed a load balancing routing algorithm which provides the load balancing for multi-radio mesh networks using a routing metric which captures the differences in transmission rates, packet loss ratio, traffic load and intra/inter flow interferences. In this proposed scheme, the router has the ability to transfer packets to a destination. This means that the routers send the first packet to the destination through the first path, the second packet for the same destination through the second path and so on. Furthermore, load balancing guarantees equal load across all links. However, there is a possibility to arrive the packets at the destination in out of order because differential delay may exist within the network [17]. Thus this proposed scheme overcomes the problem by determining the least used interface by looking the route table. This process ensures the equal utilization of all the links in the network. In addition to that, it solved the capacity problem by improving the capacity of the network and it helps to distribute the traffic load for resource utilization. |
| Capdehourat.G et al[18] considered a particular scenario: a planned WMN in which, all bidirectional point-to-point links do not interfere with each other. It means that either all backhaul links use different channels or links in the same channel are in different collision domains. This assumption also implies that it has already defined the network topology and also declared how to use them. It uses the congestion function which is sum of all links of the mean queue length. They proposed an algorithm for dynamic multipath forwarding in a WMN. The algorithm enables the load balancing and the network to operate at the minimum average congestion. The proposed framework also allowed to solve the gateway selection problem in a WMN. This was achieved by learning the average queue length function from measurements of each link and applying an optimization method in order to reach the minimum average queue length in the network. The proper evolution and convergence of the proposed method was verified by packet-level simulations in a simple topology. |
B. Energy Aware Routing Approaches
|
| Aron et al[19] presented a distributed topology control algorithm by considering the problem of topology control in a hybrid WMN of heterogeneous wireless devices with varying maximum transmission ranges. The distributed topology control algorithm calculates the optimal transmission power to maintain network connectivity, to reduce the transmission power to cover only the nearest neighbours and to extend the network lifetime. The algorithm takes decision based on the locally gathered Information and it scales well for large WMNs. The execution consists of three phases. In phase 1, it establishes the accessible neighbourhood topology, in phase 2, it constructs the minimum-energy Local topology view and in phase 3, it determines the Transmission power. This three phased topology control algorithm is executed distributively per node. A node uses only the locally available information to determine the nodes that should be its logical neighbours at any given time. The objective of this algorithm is to develop a minimum-energy distributed topology control which ensures a reduction in the amount of energy consumed per node during transmissions and without loss of connectivity. |
| Panagiotis Kokkinos et al[20] proposed a class of novel energy-efficient multi-cost routing algorithms for wireless mesh networks and evaluate their performance. In multi-cost routing, a vector of cost parameters such as hop count, residual energy and transmission power of a node i on link(i,j) is assigned to each network link, from which the cost vectors of candidate paths are calculated using appropriate operators. These parameters are combined in various optimization functions for selecting the optimal path. The performance of proposed energy-aware multi-cost routing algorithms is evaluated under two models such as network evaluation model and dynamic one-to-one communication model. In the network evaluation model, the network starts with a number of packets that have to be transmitted and an amount of energy per node and the objective is to transmit the packets in the smallest number of steps or transmit as many packets as possible before the energy is depleted. In the dynamic one-to-one communication model, new data packets are generated continuously and nodes are capable of recharging their energy periodically over an infinite time horizon for achieving maximum steady-state throughput, the packet delay and the energy consumption. The performance results showed that the energy-aware multi-cost routing algorithm increases the lifetime of the network and provides better overall network performance than the other approaches. |
| Awad et al [21] proposed a cross-layer algorithm to minimize the end-to-end transmission energy subject to a packet delay deadline constraint. The optimal transmission energy, rates and the optimal route are computed to minimize the end-to-end total transmission energy in a delay constraint wireless mesh network. The assumption of a cross-layer optimization framework is proposed, with the constraint of all successfully received packets must have their end-to-end delay which is smaller than their corresponding delay deadline. Different control parameters are optimized across the protocol layers such as network and physical layers in the proposed algorithm. It was considered as an exhaustive search algorithm for the determination of the optimized-mesh network parameters. These parameters were used as the path selection parameters in the network layer, the modulation and the transmission energy in the physical layer. In addition to the optimal solution, a suboptimum solution is also proposed by dividing the network into small subnetworks. For each path in the subnetwork, all the cross-layer parameters and the optimum route are calculated by searching through all the paths in the subnetwork. |
| Prakash, T. N. S. S., et al[22] proposed a Energy Draining Rate Based (ERDB) routing model by modifying the existing AODV protocol. This proposed ERDB-AODV protocol chooses the next relay traffic by considering the remaining battery capacity and the energy draining rate of the node. In this proposed model, remaining energy and energy draining rate is included as an additional metric for the selection of a path including the hop count metric. The primary factor for path selection is hop count and secondary factor is remaining energy of node and its energy draining rate. The nodes with high energy draining rate and low energy capacity should be avoided for relaying traffic to increase network life time. These two aspects may take long path to reach destination but it will assure successful data transfer without node failure. |
| Capone A. et al[23] combined the flexibility of WMN with the need for optimizing energy consumption reduction by giving an optimization framework for network management which considers the trade-off between the network energy needs and the daily variations of the demand. The minimum energy is carried out by switching off unnecessary network resources, namely Base stations and the links connecting them. It also provided an optimization framework based on mathematical programming which considers traffic demands for a set of time intervals and manages the energy consumption of the network with the goal of making it relative to the load. They created an instance generator to evaluate the model and compared them with other modeling variations. This proposed work shown great energy savings when guaranteeing the smooth operation of the wireless network. This greater savings can be achieved by relaxing the all-over covering constraints by carefully re-assigning only the active traffic points to the most appropriate active base stations. |
| Antonio et al [24] proposed a novel routing algorithm for 802.11 based wireless mesh networks called Energy and Throughput-aware Routing (ETR). The design objectives of this proposed algorithm(ETR) are to provide traffic flows with throughput guarantees and to minimize the overall energy consumption in the mesh network. The proposed routing algorithm targets a network owned by an operator and depends on a centralized entity implementing resource allocation and admission control mechanisms. It builds on a liberalized model of the capacity region of IEEE 802.11 DCF, which provides an accurate model of the set of feasible allocations at a low computational flexibility, thus supporting the execution of optimization algorithms in a timely manner. The main tasks of this algorithm are, using the novel way to represent the capacity region of the set of stations sharing the wireless medium, design a novel routing algorithm for wireless mesh networks which admit as many users as possible to the network with throughput guarantees and extends the algorithm to minimize the energy consumed by the network. Table 1 shows the summary of load and energy based routing in WMN. |
CONCLUSION AND FUTURE WORK
|
| The research contributions discussed above suggested various routing metrics, algorithms and protocols for the route construction process of WMN. They carried out the routing process based mainly on energy or queue length to balance load, energy consumption, reduce end-end delay and increase throughput etc. Among these, some of them have been proposed only for balancing the load among the network whereas some other has been proposed for energy consumption of the network. From the literature survey, it is observed that, the research contributions had focused either on node’s energy or queue length during the routing process. Although load based or energy based routing approaches discussed above performed well individually in WMN, the better performance can be achieved by combining the energy and queue length factors for the route construction in WMN. Hence, this thesis focuses the route construction process in WMN based on both energy and queue length factors to improve the network performance and to avoid the difficulties such as node failure as well as congestion and delay in the network. |
| |
Tables at a glance
|
 |
| Table 1 |
|
| |
Figures at a glance
|
 |
| Figure 1 |
|
| |
References
|
- http://en.wikipedia.org/wiki/Wireless_mesh_network
- MojtabaSeyedzadegan, Mohamed Othman, BorhanuddinMohd Ali and ShamalaSubramaniam, Wireless Mesh Networks: WMN Overview, WMN Architecture, International Conference on Communication Engineering and Networks,IPCSIT vol.19, IACSIT Press, Singapore, 2011.
- Akyildiz and X. Wang, “A Survey on Wireless Mesh Networks, IEEE Communications Magazine, vol. 43, no. 9, pp. S23–S30, 2005.
- http://en.wikipedia.org/wiki/List_of_ad_hoc_routing_protocols
- Destination-Sequenced Distance Vector routing, http://en.wikipedia.org/ wiki/Destination-Sequenced_Distance_Vector_routing
- Subir Kumar Sarkar, T.G. Basavaraju, C. Puttamadappa, Ad Hoc Mobile Wireless Networks: Principles, Protocols and Applications, CRC Press, Oct-2007.
- Charles E. Perkins and Praveen Bhagwat, “Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers”, in: Proceedings. of ACM SIGCOMM ’94 Symposium on Communication, Architectures and Protocols, pp. 234–244, 1994.
- C.E. Perkins & E.M. Royer, Adhoc On-Demand Distance Vector Routing, Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, LA, pp. 90-100, February 1999.
- http://en.wikibooks.org/wiki/Wireless_Mesh_Networks/Mesh_network_basics
- Yumei Liu, Lili Guo, Huizhu Ma, Tao Jiang , Energy efficient on demand multipath routing protocol for multi-hop adhoc networks, Proceedings of ISSSTA-08, IEEE 10th International symposium on Spread spectrum and applications, Bologna, Italy, pp-592-597, 2008.
- http://backup.daintree.net/downloads/whitepapers/mesh-networking.pdf, What’s so good about mesh networks?
- Gálvez, J. J., Ruiz, P. M., &Skarmeta, A. F. , A distributed algorithm for gateway load-balancing in wireless mesh networks. In Wireless Days, WD'08.1st IFIP pp. 1-5, IEEE, 2008.
- Hongkun Li, Yu Cheng, Chi Zhou, Weihua Zhuang, Minimizing End-to-End Delay: A Novel Routing Metric for Multi-Radio Wireless Mesh Networks, INFOCOM 2009, IEEE, pp:46 – 54, ISSN :0743-166X, 2009.
- Choi, K. W., Jeon, W. S., &Jeong, D. G., Efficient load-aware routing scheme for wireless mesh networks. Mobile Computing, IEEE Transactions on,9(9), pp. 1293-1307, 2010.
- DI STASI, G. I. O. V. A. N. N. I., Design, analysis and evaluation of routing and channel assignment algorithms for wireless mesh networks, 2011.
- Al-Kharasani, N. M., &Zukarnain, Z. A., Performance evaluation of routing with load-balancing in multi-radio wireless mesh networks. Int. J. Digit. Content Technol. Appl, 5, pp. 64-71, 2011.
- Yang, Y., Wang, J., &Kravets, R, "Load-balanced routing for mesh networks," ACM SIGMOBILE Mobile Computing and Communications Review, vol. 10, No. 4, pp. 3-5, 2006.
- Capdehourat, G., Larroca, F., &Belzarena, P., Minimum queue length load-balancing in planned Wireless Mesh Networks.In Wireless Communication Systems (ISWCS), International Symposium, IEEE, pp. 781-785, 2012.
- Aron, F. O., Olwal, T. O., Kurien, A., &Odhiambo, M. O., Distributed topology control algorithm to conserve energy in heterogeneous wireless mesh networks, 2008.
- Kokkinos, P., Papageorgiou, C., &Varvarigos, E., Multi-cost routing for energy and capacity constrained wireless mesh networks. Wireless communications and Mobile Computing, 2011.
- Awad, A., Nasr, O. A., &Khairy, M. M, Energy-aware routing for delay-sensitive applications over wireless multihop mesh networks.In Wireless Communications and Mobile Computing Conference (IWCMC), 2011 7th International, pp. 1075-1080, IEEE, 2011.
- Prakash, T. N. S. S., &Krinkin, K. Energy Draining Rate Based-AODV Routing in Wireless Mesh Network, In 12th FRUCT conference, ISSN2305-7254, pp..279-289, 2012
- Capone, A., Malandra, F., &Sansò, B, Energy savings in wireless mesh networks in a time-variable context.Mobile Networks and Applications, 17(2), pp. 298-311, 2012.
- Antonio De La Oliva a, Albert Banchs A.B. Pablo Serrano, Throughput and energy-aware routing for 802.11 based mesh networks, Elsevier, Computer communications 2012.
|
Menu