Self-management in chaotic wireless deployments

隨著無線通訊技術的進步，越來越多的AP被建立起來，而這些AP通常都是被隨意的設立，因此在沒有有善規劃下，會造成以下兩個問題:

Unplanned

由於，每一個人或公司組織在設立AP時，都是隨意設立，所以會造成有些區域密度過高，在使用相同頻段下，會造就出不好的網路環境。

Unmanaged

這個議題主要在探討parameter的，例如SSID，channel，以及較複雜的問題，包含AP個數的布置，還有power control。

(1)    首先此篇作者在美國城市中，大範圍的對APs做量測，發現到許多區域已經出現如chaotic deployment的網路形態。

A. Deployment Density

下表示從Place Lab database，所整理出來的資料，包含US的六個城市。(AP degree，表示有多少AP在它的干擾範圍。)

由上表和左圖可以發現高密度的802.11 hardware deployment已經開始出現 ，而且可以預期未來這樣的網路型態會增加的非常快速。

B. 802.11Usage: Channels

上表是Channel的份佈，可以用來觀察user of AP是否有善的管理他們的network，表中發現Channel 6的使用率最多，而non-overlapping的channel(1,11)，只有14%，所以這些AP當初的設置可能沒有考慮去minimize interference。

(2)    對Chaotic deployment做模擬量測:

在20-node的拓墣底下做模擬量測，底下左圖是用來做為優化的sub-topology。

(b) 8-node topology

(a) 20-node topology

上圖是在每個AP的Client為"1"的情況下，ap間的巨來會影響整體的吞吐量。tpf和http之間也會影響彼此的performance

當有channel配置管理時可以發現整體的吞吐量達到步錯的提升，不過可以發現stretch=1和stretch=2還是有一段差距。

當client增加，可以發現ftp和http的performance都會因ap增加而降低，可以看到stretch=1和stretch=10的performance差距很大。

當有channel管理配置，和power control可以發現performace達到很高的提升，stretch=1和strech=10幾乎一樣，所以power control是非常必要的。

(3)    TRANSMISSION POWER AND RATE SELECTION:

Power and Rate Selection Algorithm

ARF: 如果連續成功n次收到ACK，代表channel的狀況良好，可以繼續提高data rate，如果連續失敗m次，代表channel狀況不好，降低data rate，在這裡作者將m設為6，n設為4。

ERF(Estimated Rate Fallback):混合上述兩種方法的rate selection Algorithms，首先測量channel SNR，ERF 再選擇SNR可以維持的最高data rate，因為有可能會發生測量不準的關係 ，當所測出的SNR剛好低於rate decision boundary 一點，系統會在幾次傳輸成功後，rate再調回到下一個  level ，當SNR剛好高於rate decision boundary 一點，系統會在幾次傳輸失敗後，再調回去上一個Level。

PERF(Power-controlled Estimated Rate Fallback ):一開始跟前頁講的一樣，選擇SNR可以維持的highest data rate，如果EstimatedSNR還高於所需的SNR一些量(power margin)，就可以降低transit power rate，直到EstimatedSNR=decisionSNR+ power margin。在Unlimited的情況下，victim的throughput在ARF和ERF幾乎的零，原因在於，victim可以sense到aggressor，因為aggressor的transit power較高，但aggressor無法sense到victim，導致aggressor無止盡的增加他的rate，而victim則為了避免碰撞，所以就會降低他傳送的慾望，造成極低的throughput。而在PERF下， aggressor因為利他的心態下，我在某個rate，盡可能的降低transit power，讓兩組pairs可以獨立運作，而不相干擾。因此可以達到好的效果。

EARC: Enhanced Adaptation of Link Rate and Contention Window for IEEE 802.11 Multi-Rate Wireless Networks

這篇paper，是在探討如何於傳輸的過程中，讓Network可以自己調整Link Rate 和Contention Window，以達到較好的傳輸效率，以EARC(Enhanced Adaptation of Link Rate and Window)字面上來看，就是強化ARC Protocol，修正這個Protocol裡 的一些缺失，讓整體的throughput可以得到提升。

首先來討論之前的一些rate-adaptive schemes:

(1)  rate-adaptive schemes: open-loop and closed-loop approaches:

一般在 rate-adaptive schemes，有兩類方式open-loop以及 closed-loop:

Open-loop:只依靠ACK訊息，來做相對應的調整。

a.      Auto-rate Fallback (ARF)

它是以收到ACK的資訊來做為調整rate的依據，在Sender成功連續收到10次的ACK，Sender 就會調高send rate，而在兩次傳輸的失敗後，sender就會調降send rate。雖然這個方法實作上很簡單，但是卻無法在stable 或是 fluctuated 的Network達到好的效果，在穩定的狀態下，rate 會被不斷的提高，而在SINR無法容忍下，就會造成不必要的collision，而在fluctuated的狀態下，因為環境變動太快速，會造成rate的調整無法做及時的回應。

b.     Adaptive Thresholds (AT)

AT是用來修正ARF的缺失，它會測量link-layer的狀態，來設計一個Adaptive Threshold，這個值會在contending station增加時，抑制send rate的下降，而在contending station減少時，抑制send rate的提升。這樣的設計對於ARF來說，有效的改善了a部分說討論到的缺失。

Closed-loop: 結合其他訊息(EX:SINR,collision)來做相對應調整。

a.     ARF with COLLIE (AC)  

AC也是用來修正ARF的缺失，它會對link-layer的狀態做診斷，分析封包遺失的原因，如果是weak signal的話，Sender就會降低send rate，而如果是link-layer collisions，Sender就會增加它的contention window。主要弊端在於它需要額外的診斷資訊加至每一個封包，因此造成了較大的overhead。

b.     Receiver-based Auto-rate (RBAR)

   RBAR是根據receiver所估測到的channel quality來調整data rate，由RTS/CTS   

   handshaking mechanism來告知sender。利用RTS取得RSSI的資訊，選擇適當

   的data rate，再利用CTS告知sender做相對的調整。

c.      Adaptation of Link Rate and Contention Window (ARC)

結合了Contention Window，利用Cal´i’s approximation methods，找出optCW，假設發生傳輸失敗(成功)，如果CW>optCW(CW<optCW)就減少(增加)CW，否則減少(增加)data rate。不過因為在open-loop nature，必須在歷經幾次失敗後，才可到達穩定的狀態，而且它只能在symmetric networking，才有好的效果。

(2) EARC: Enhanced Adaptation of Link Rate and Contention

   EARC是屬於closed-loop approach，主要針對ARC的一些弱點作修正，(1)不能及時的調整出適當的data rate，(2)以及 在asymmetric下無法達到好的效果。(1)Rate Selection Reference

  這邊Rate的選擇是使用rate selection reference (RSR) table(圖一)，在每一個接收端的energy level都設定一個合適的data rate，此篇作者通過各種實驗的佐證下，證實這些設定確實時最合適的。相對於ARC，這個方式可以更快找到合適的Rate。

　

　　

　　圖一

(2) Erx,Etx, Ediff

為了考量到asymmetric，這篇paper定義了Erx and Etx，Erx代表接收端的energy level，而Etx代表在傳送端的energy level，如果兩者不相同代表network屬asymmetric。     

，如果>0，代表接收端的contenting station較多，必須要放大ＣＷ，以減少競爭，相反則縮小ＣＷ，鼓勵Sender傳輸。調整方式定義於圖二。

EARC CW Flag是加在header上，如果=0，EARC CW Flag設為０，告訴Sender CW不用做調整，否，則EARC CW Flag設為１，告訴Sender依圖二的方式來調整CW。至於b1b2b3，可以由以下兩式決定：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

以及

　　　　　　

圖二

綜合以上，如果Sender發現Receiver在不同的energy　level，sender就先保留ＣＷ的調整，先做data rate的調整，將send rate調整至Erx level下的rate，如果兩邊的Erx、Etx在相同energy level，再依Ediff對ＣＷ做相對應的調整。

　

　　　　　　　

(2)  simulation

a. Symmetric Environment

    　　　　　    Result(1)　　　　　　　　　　　　　　　　　　　　　　　　　

　　　 Symmetric Environment　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　

在200*200 nodes的Symmetric Environment模擬結果下，如圖(Symmetric Environment)，可以發現EARC有最好的Throughput(如圖Result(1))，其次是ARC，而最差的是只利用BEB機制的Protocol。EARC以及ARC，都是聯合CW和Data rate的調整找出最合適的狀態，由結果可以發現這樣的做法確實可以達到好的Throughput。而因為是在Symmetric Environment的環境下，所以EARC和ARC的Throughput差異不大。

b. Asymmetric Environment

　　                    

Asymmetric Environment  　　　　　　　　　　　　　　   　Result(2)

在Asymmetric Environment下，就可以發現ARC的弱點-無法在Asymmetric Environment有好的傳輸效率，因為這個Protocol本身就沒有考慮Asymmetric的情況，只由sender端來決定調整的內容。以上的結果，我可以發現有結合CW的adjustment，可以有效穩定rate的變動，如果medium congestion level 可以由CW的adjustment來降低，我們就不需要去調整rate，反過來，如果medium可以忍受更多inteference，我們就可以縮小CW，製造更傳輸的機會。