Umeå universitets logga

Communicating over a wireless channel poses many unique challenges not found in wired communication because of the special characteristics of the wireless channel. The capacity in a wireless network is typically scarce as a result of the limited bandwidth and many distinct phenomenons, like attenuation and interference, that work destructively on the received signals.

The Medium Access Control (MAC) layer is responsible for sharing this limited resource among the users. This allocation problem should be handled by considering the Quality of Service (QoS) requirements of each user as to maximize the utility. Efficient MAC algorithms are crucial in minimizing collisions between transmissions and thus achieving high utilization of the channel.

This thesis focuses on conflict resolution and service differentiation algorithms for wireless local area networks, where there is no central control of the channel and each sender independently contends for access.

In part I, we study three approaches to improve the IEEE 802.11(e) standards with focus on QoS. In the first approach, utility functions are considered, that model application preferences, to achieve service differentiation and maximize the aggregated utility. We provide algorithms for two subsidiary problems that arise from the maximization problem, and show that a near--optimal solution is found. In the second approach a collision detection algorithm for multicast transmissions is proposed, that increases the reliability for multicast compared to the protected unicast traffic. The third approach is an improved MAC algorithm for the QoS standard IEEE 802.11e. The improved algorithm outperforms the standard and achieves close to optimal performance for large number of scenarios, which significantly reduces the need of adjusting the contention parameters.

In part II, we focus on channel bursting protocols that use noise bursts to resolve channel conflicts. These protocols is capable of achieving very low collision probability. We propose two new bursting protocols, that achieve very high channel utilization, and show that the bursting technique has good fairness properties and provides efficient support for service differentiation. We also show that it is possible to reduce the number of bursts without loosing performance.

In part III, the optimal backoff distribution that minimizes the collision probability is derived. We then propose a heuristic backoff distribution with similar properties that yields high channel utilization. An extension for service differentiation is provided where the sizes of the backoff windows are adjusted.

I avhandlingen beskrivs ett hypotetiskt system som kan användas av mobila användare, bland andra taxichaufförer, som exempelvis vill följa en viktig fotbollsmatch. Flera faktorer ställer till problem: Ibland står bilen still och föraren har inget annat att tänka på än matchen. Ibland kör denne runt med en kund som inte vill bli störd av matchen. Dessutom kan det vara svårt att titta på rörliga bilder och köra bil samtidigt. I och med att bilen körs runt har man också olika bra anslutning till Internet vid olika tillfällen – det kan variera mellan inget alls, en dålig GSM/GPRS förbindelse (8 kbps) och en snabb WLAN anslutning (100 Mbps).

I avhandlingen presenteras en tre-lagers modell som kan användas för att beskriva den här typen av applikationers kvalitet. Modellen delas in i tre lager: nätverk, applikation och användare/använding. Det sistnämnda lagret ligger utanför det tekniska systemet och definieras av att det är där de verkliga informationsutbytet sker. På applikationsnivån samlas data in, packas och packas upp i samband med nätverkstransport och visas sedan för användaren. Det är också här som eventuell interaktion sker med användaren. Nätverkslagret är ansvarigt för ändamålsenlig transport av data.

De tre lagren är ömsesidigt beroende av varandra. Dålig prestanda på ettlager påverkar de andra lagren och tvärtom. Tre studier har genomförts av hur problem på nätverkslagret i form av begränsad bandbredd och hög fördöjning påverkar användarna.

Låg bandbredd ger låg videokvalitet vilket inte uppskattas av användarnamnen genom att skifta till animeringar som fungerar med lägre bandbredd kan man ändå få användarna nöjda. Om användarna måste välja mellandålig videokvalitet och animeringar väljer de som ser sig som fotbollskunniga det förstnämnda och de som ser sig som okunniga men dock fotbollsfans väljer det sistnämnda.

Men i en annan studie där användarna spelade bluffstopp mot varandra över ett datanätverk fick vi ett annat resultat. Där var det negativt med högre videokvalitet (bilder per sekund). En förklaring kan vara att användarna distraherades mer av högre bildfrekvens.

I den tredje studien studerades vad som händer i Pong om man läggerin fördröjningar i spelet. Sedan tidigare visste man att det blir svårare attspela med fördröjningar – särskilt om man inte märker dem. Vi ställde ossfrågan om man kan kompensera för dem genom att informera användarna om dem. Det visade sig att användare som får information med i vårtfall en prediktiv visning lättare anpassar sin mentala insats till uppgiftens svårighetsgrad.

Det är alltså inte bara möjligt utan ibland också önskvärt att utnyttja en lägre bandbredd från användarens perspektiv. Med det sagt finns det ändå i långt fler situationer där det är bättre med bättre nätverksprestanda. Pongspelet var roligare med lägre delay. Videon uppfattades som bättre medhögre bandbredd i den förstnämnda studien.

Multicast, där ett paket skickas till flera användare i stället för att de skafå varsin, identiska paket, är ett viktigt verktyg för att få bättre prestanda i videoapplikationer. Tyvärr är det inbyggda stödet för multicast i den viktiga IEEE 802.11 standardfamiljen för trådlösa nätverk mycket outvecklat. Ettstort problem är att det inte går att veta om ett paket har kommit fram eller om det har försvunnit i en, mycket trolig, krock.

Vi har vidareutvecklat och anpassat en föga känd krockdetektionsmekanism från 80-talet för använding i IEEE 802.11 nätverk. Den anpassade algoritmen kallar vi EMCD vilket är en förkortning för ‘‘Early Multicast Collision Detection’’ eller tidig krockupptäckt för multicast. Vi har presenterat en nysannolikhetsbaserad modell för att beräkna algoritmens prestanda undermaximal belastning. Modellen som har verifierats genom simuleringar kanäven användas för att beräkna optimala parametrar för algoritmen. Algoritmen har visats kraftigt reducera risken för oupptäckta kollisioner och reducerar den tid som går åt för dem.

EMCD-algoritmen inspirerade till att utveckla en ytterligare algoritm som inte bara kan upptäcka utan också undvika kollisioner: PREMA som står för ‘‘Prioritized Repeated Eliminations Multiple Access’’ eller prioriterad kanal-åtkomst med upprepade eliminationer. Det finns två viktiga skillnader mellanhur de fungerar. I EMCD bygger kollisionsdetektionen på rektangelfördelade slumptal och en enda upptäcktsomgång. I PREMA används i stället geometriskt fördelade slumptal och upprepade omgångar. Effekten blir att man med stor säkerhet får en enda vinnare. även för PREMA presenteras en sannolikhetskalkylsbaserad prestandaanalys för maxlastfallet vilken stöds av simuleringar.

Samma formler kan användas för att approximativt skatta prestanda i EY-NPMA som är en närliggande algoritm. Den var tänkt att använda i Hiperlan/1; en standard som aldrig fick något kommersiellt genombrott. Använder man den modell som vi presenterar i avhandlingens sista studiekan man med ganska god noggrannhet beräkna optimala parametrar för EY-NPMA med en beräkningsinsats O(mY S) mot O(mES×mY S) för tidigare kända algoritmer.

Imagine a taxi driver wanting to watch a football game while working. Events in the game cannot be predetermined, the driver's available attentional resources vary and network connections change from non-existing to excellent, so it will be necessary to develop a viewing application that can adapt to circumstances. This thesis presents a system model and sketches a framework for design and run time adaptations. The model has three layers: user/usage, application and network.

Quality of service metrics are proposed for each layer. A particular emphasis is placed on the difference between the user/usage layer and the application layer. Satisfaction at the former means a job well done, a match played to your liking etc. Satisfaction at the latter means good picture quality, nice colours etc. The thesis continues by identifying and describing elements required to build the system used by the taxi driver.

Three studies are presented where either bandwidth or delay are varied at the network level. Video is better the higher the bandwidth; animations can be used as a complement. They are shown to be better than low quality video but worse than high quality video for watching a football game. Better video in the form of higher frame rates turned out to be worse for playing a card game over the Internet. A possible explanation is the distraction experienced when the image is updated constantly.

Another result of our studies is that users can adapt their mental effort to the actual load when given feedback on the network delay affecting a computer game.

The results mentioned above show that it is possible to compensate for poor network performance. For the user, improved network performance is generally more satisfactory.

Early multicast collision detection is a method for improved multicast performance in high load IEEE 802.11 networks. Prioritised repeated eliminations multiple access is a method for multicast and other traffic which can be used alone or in an IEEE 802.11 network. Probabilistic performance analysis and simulations show that both protocols drastically reduce the time spent in collisions and improve throughput compared to IEEE 802.11. Some of the formulae are applied to EY-NPMA as well; they are used to estimate performance and to estimate optimal operating parameters more efficiently than with previously known methods.