Design and implementation of resource allocation algorithms in wireless networks

Abstract

Efficient management of available resources in wireless networks is directly relatedwith the optimisation of network performance and as a result is actively investigatedby the research community in the field of wireless networks. In this thesis, we studyresource allocation algorithms in wireless networks, considering the resources of networkusers, the utilised spectrum and the amount of energy that is being consumedin different phase of network operation. The common research approach that has beenfollowed across all the development phases of our work, is based on the design andimplementation of the proposed algorithms in real wireless devices , in order to assessperformance under realistic environments and provide for direct comparison withexisting standards.We start by studying user association algorithms, which assign at assigning networkterminals to the available access points and more specifically focused on wireless networksthat are compatible with the IEEE 802.11 protocol, commonly known as Wi-Fi.The existing protocol defines a rather simple association policy, based on which eachterminal is associated with the access point from which it has received the strongestsignal during the scanning process. This rather simplistic association policy has beenshown in the literature that is not able to result in assignments that maximize throughputperformance, as it does not take into account factors that affect the performance of802.11 compatible networks. We briefly mention the contention between neighboringnodes for use of the wireless medium, the number of already already associated witheach access point terminals along with the network load they result in, and the interferencethat is generated by transmissions taking place in other networks. Our work hasresulted in the design of a novel distributed algorithm that jointly considers the abovefactors and leads to assignments that maximize the throughput of each individual tervii minal. Comparative study between the implemented mechanism and the 802.11 basedapproach, in realistic experiments and under varying network load has shown significantthroughput improvement (65 %). We also observed the distribution of throughputbetween terminals to be almost equal contrary to the performance of 802.11, whichbenefits only a subset of terminals that are located close to under-loaded access points.As a next step, we extended the proposed mechanism by taking into account notonly the individual user performance, but the overall network throughput as well. Inorder to evaluate the performance of the proposed algorithms, we conducted severalsets of experiments and experimentally validated the superiority of the proposed algorithmscontrary to the 802.11 based approach. Finally, we studied user associationmechanisms the consider performance under combined topologies, consisting of bothwireless and wired parts. Study of implemented algorithms was conducted in combinedwired and wireless network infrastructure and showed the benefits that can beoffered by association mechanisms that take into account metrics able to characterizeend user performance in combined topologies .In the context of assigning the spectrum of operation in wireless networks, we studiedmechanisms that select the operational frequency in order to avoid congested bandsand bands that experience strong levels of interference from neighboring transmitters.According to the current standard, configuration of operational frequency is executed atthe access points by selecting the frequency that provides the minimum received powerfrom neighboring networks. Existing commercial implementations that are based onthe standard policy statically configure the frequency of operation, once during thedevice startup and come in contrast with the dynamic nature of the wireless medium.Aiming at improving the overall throughput of wireless networks, we proposed a novelmechanism that considers measurements collected at the acceess point along with measurementsthat have been gathered by adjacent stations. The proposed approach avoidsfrequency configurations that benefit only the local environment of the Base Station, asthe operating frequency is selected based on combination of measurements that havebeen collected by all network nodes. An important advantage of the proposed schemeis also the ability of classifying the levels of network traffic in real time, thus resulting inefficient avoidance of congested frequencies. Moreover, since the proposed mechanismis applied dynamically, any changes in the wireless environment are immediately identifiedand consequently result in reconfiguration of the operating frequency. Having implementedthe proposed mechanism in real wireless devices, we conducted extensiverealistic experiments that proved the superiority of the proposed scheme compared tothe standard policy, in terms of overall network throughput.Next, we proceeded by extensively studying the influence of interference effects onthe throughput of wireless networks and by designing mechanisms able to detect eachtype of interference. We also studied the influence of interference phenomena in the repeatabilityof wireless experiments. Based on the obtained results, we developed mechanismsable to characterize the stability of experimental conditions and consequently thevalidity of experimental results. The ultimate goal of these activities has been the developmentof the AGILE spectrum adaptation system that is able to adapt to the prevailingconditions under varying types of interference, in uncoordinated 802.11 WLANs. Thekey novelty of our approach is that identification of under-utilised spectrum fragmentswas able to take advantage of hardware inherent in the PHY-layer of standard OFDM receivercircuits. AGILE satisfied all the design requirements that uncoordinated networkdeployments specify - distributed operation, interoperability with existing standards,simple implementation and minimal protocol overhead. Through the implementationof our approach on commercial 802.11n chipsets and its detailed experimental evaluation,we showcased its feasibility and moreover quantified the obtained throughputperformance and energy efficiency benefits. To the best of our knowledge, AGILE systemwas the first to enable dynamic spectrum adaptation in uncoordinated WLANdeployments and provide for direct implementation on off-the-self equipment.The next part of our work is related with the energy efficient operation of wirelesscommunication networks, which may result in significant waste of energy, both due tothe rapid increase in carried data traffic as well as due to their inefficient in terms ofenergy mode of operation. Researchers working on designing energy efficient protocolsare traditionally based on the use of models to estimate the amount of consumed energy.However, due to the proved inability of models to evaluate the energy consumption ofcomplex networks, the development of research tools able to monitor the consumptionof wireless devices accurately and in real time becomes a necessity. Having extensivelystudied the related literature, we identified a large gap in the available experimentalinfrastructure that can support the research community. Towards filling the identifiedgap, we developed a prototype electronic device, of particularly low cost, which enablesdetailed analysis of the energy consumed by distributed wireless devices in real time.As our next step, we integrated the initial version of the developed device into an operationalframework ready to be incorporated into networking testbeds. The upgradedversion of the device has been used towards evaluating the consumption of wirelesscommunication networks under realistic scenarios and quantified the impact of exogenousfactors ( eg. interference, contention for channel use) on energy consumption, thusexperimentally validating the inability of applying models in complex topologies. Thedeveloped platform has also been used to compare the energy efficiency of the 802.11protocol with the upgraded version of 802.11n, which study showed that the latest protocol version is able to offer reduction of consumption per unit of transmitted information(bit), in the order of 75 % . The detailed findings of the above study providedguidelines for the design of energy efficient wireless protocols.