An optimisation approach to improve the throughput in wireless mesh networks through network coding

Thesis (M.Ing. (Computer and Electronical Engineering))--North-West University, Potchefstroom Campus, 2012.In this study, the effect of implementing Network Coding on the aggregated throughput in Wireless Mesh Networks, was examined. Wireless Mesh Networks (WMNs) are multiple hop wireless networks, where routing through any node is possible. The implication of this characteristic, is that messages flow across the points where it would have been terminated in conventional wireless networks. User nodes in conventional wireless networks only transmit and receive messages from an Access Point (AP), and discard any messages not intended for them. The result is an increase in the volume of network traffic through the links of WMNs. Additionally, the dense collection of multiple RF signals propagating through a shared wireless medium, contributes to the situation where the links become saturated at levels below their capacity. The need exists to examine methods that will improve the utilisation of the shared wireless medium in WMNs. Network Coding is a coding and decoding technique at the network level of the OSI stack, aimed to improve the boundaries of saturated links. The technique implies that the bandwidth is simultaneously shared amongst separate message flows, by combining these flows at common intermediate nodes. The number of transmissions needed to convey information through the network, is decreased by Network Coding. The result is in an improvement of the aggregated throughput. The research approach followed in this dissertation, includes the development of a model that investigates the aggregated throughput performance of WMNs. The scenario of the model, followed a typical example of indoors WMN implementations. Therefore, the physical environment representation of the network elements, included an indoors log–distance path loss channel model, to account for the different effects such as: power absorption through walls; and shadowing. Network functionality in the model was represented through a network flow programming problem. The problem was concerned with determining the optimal amount of flow represented through the links of the WMN, subject to constraints pertaining to the link capacities and mass balance at each node. The functional requirements of the model stated that multiple concurrent sessions were to be represented. This condition implied that the network flow problem had to be a multi–commodity network flow problem. Additionally, the model requirements stated that each session of flow should remain on a single path. This condition implied that the network flow problem had to be an integer programming problem. Therefore, the network flow programming problem of the model was considered mathematically equivalent to a multi–commodity integer programming problem. The complexity of multi–commodity integer programming problems is NP–hard. A heuristic solving method, Simulated Annealing, was implemented to solve the goal function represented by the network flow programming problem of the model. The findings from this research provide evidence that the implementation of Network Coding in WMNs, nearly doubles the level of the calculated aggregated throughput values. The magnitude of this throughput increase, can be further improved by additional manipulation of the network traffic dispersion. This is achieved by utilising link–state methods, rather than distance vector methods, to establish paths for the sessions of flow, present in the WMNs.Master