2015年12月17日 星期四

Cickd 註解

今天要來記錄一下clickd的語法
因為太難了...要做個紀錄
以下是我們可以看到clickd中的code
#!/bin/sh 

# Copyright (c) 2006, Roberto Riggio
#
# All rights reserved.
# 
# Redistribution and use in source and binary forms, with or without 
# modification, are permitted provided that the following conditions    
# are met:
# 
#   - Redistributions of source code must retain the above copyright 
#     notice, this list of conditions and the following disclaimer.
#   - Redistributions in binary form must reproduce the above copyright 
#     notice, this list of conditions and the following disclaimer in 
#     the documentation and/or other materials provided with the 
#     distribution.
#   - Neither the name of the CREATE-NET nor the names of its 
#     contributors may be used to endorse or promote products derived 
#     from this software without specific prior written permission.
# 
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
# EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
# PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
# PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
# LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
# NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

PATH=/usr/local/sbin:/usr/local/bin:/sbin:/bin:/usr/sbin:/usr/bin:./
DAEMON=click => 可執行檔
HELPER=click_config =>由click_config產生腳本
NAME=clickd

MODE="11g"
CHANNEL="2412"
DEV="moni0"

PROFILE="bulk"
LS="fcfs"
METRIC="wcett" => 有hop-count與wcett,這是route機制
RC="minstrel" => 有static與minstrel,這是Rate Control機制

CLICK_FILE=/var/run/$NAME.click
PID_FILE=/var/run/$NAME.pid
LOG_FILE=/var/log/$NAME.log 

test -x "$(which $DAEMON)" || exit 0
test -x "$(which $HELPER)" || exit 0

case "$1" in
  start)

 echo "Starting $NAME"

 if which wlanconfig > /dev/null 2>&1; then  => > /dev/null 2>&1表示說不Print在螢幕上
  PHY="wifi0"
  WLANCONFIG=$(which wlanconfig)
  [ ! -f "$WLANCONFIG" ] && {
   echo "Couldn't find wlanconfig";
   exit 1; 
  }
  $WLANCONFIG $DEV destroy 2> /dev/null
  $WLANCONFIG $DEV create wlandev $PHY wlanmode monitor > /dev/null 2>&1 || {
   echo "Couldn't create monitor device on $PHY";
   exit 1; 
  }
  echo '803' >  /proc/sys/net/$DEV/dev_type
  /sbin/iwpriv $DEV mode $MODE
 elif which iw > /dev/null 2>&1; then
  PHY="phy0"
  IW=$(which iw)
  [ ! -f "$IW" ] && {
   echo "Couldn't find iw";
   exit 1; 
  }
  $IW dev $DEV del > /dev/null 2>&1
  $IW phy $PHY interface add $DEV type monitor > /dev/null 2>&1 || {
   echo "Couldn't create monitor device on $PHY";
   exit 1; 
  }
 else
  echo "Couldn't find neither iw or wlanconfig";
  exit 1
 fi

 /sbin/iwconfig $DEV channel ${CHANNEL}M
 /sbin/ifconfig $DEV mtu 1900
 /sbin/ifconfig $DEV txqueuelen 5
 /sbin/ifconfig $DEV up
 /sbin/modprobe tun > /dev/null 2>&1 =>載入Module (包製多NIC)

 # extract the bottom three octects to use as IP =>查網卡卡號,可直接設SUFFIX成0.0.0.1
 MAC=$(/sbin/ifconfig $DEV 2>&1 | sed -n 's/^.*HWaddr \([0-9A-Za-z\-]*\).*/\1/p' | sed -e 's/\-/:/g' | cut -c1-17)
 HI=$(echo $MAC | sed -n 's/.*:.*:.*:\([0-9A-Za-z:]*\):.*:.*.*/\1/p')
 MID=$(echo $MAC | sed -n 's/.*:.*:.*:.*:\([0-9A-Za-z:]*\):.*.*/\1/p')
 LOW=$(echo $MAC | sed -n 's/.*:.*:.*:.*:.*:\([0-9A-Za-z:]*\).*/\1/p')
 SUFFIX=$((0x$HI)).$((0x$MID)).$((0x$LOW))

 XR_IFNAME="wing-mesh"
 XR_IP="6.$SUFFIX"
 XR_NM="255.0.0.0"
 XR_PERIOD="36000"
 XR_TAU="360000"

 $HELPER -p $PROFILE -r $RC -s $LS -l $METRIC -m $MODE -c $CHANNEL -n $DEV -a $MAC -d \
  | sed -e "s/__XR_IFNAME__/$XR_IFNAME/g" \
  | sed -e "s/__XR_IP__/$XR_IP/g" \
  | sed -e "s/__XR_NM__/$XR_NM/g" \
  | sed -e "s/__XR_PERIOD__/$XR_PERIOD/g" \
  | sed -e "s/__XR_TAU__/$XR_TAU/g" > $CLICK_FILE

 $DAEMON $CLICK_FILE > $LOG_FILE 2>&1 &

 sleep 2
 if ! pidof $DAEMON > /dev/null 2>&1; then
  echo "Unable to start click. Check log for more information."
  exit 1
 fi

 pidof $DAEMON > $PID_FILE

 ;;
  stop)
 echo "Stopping $NAME"

 if which wlanconfig > /dev/null 2>&1; then
  WLANCONFIG=$(which wlanconfig)
  [ ! -f "$WLANCONFIG" ] && {
   echo "Couldn't find wlanconfig";
   exit 1; 
  }
  $WLANCONFIG $DEV destroy > /dev/null 2>&1
 elif which iw > /dev/null 2>&1; then
  IW=$(which iw)
  [ ! -f "$IW" ] && {
   echo "Couldn't find iw";
   exit 1; 
  }
  $IW dev $DEV del > /dev/null 2>&1
 else
  exit 1
 fi
 [ -f $PID_FILE ] && {
  kill -9 $(cat $PID_FILE)
  [ -f $PID_FILE ] && rm $PID_FILE
 }
 [ -f $CLICK_FILE ] && rm $CLICK_FILE
 [ -f $LOG_FILE ] && rm $LOG_FILE
 ;;
  restart|force-reload)
 $0 stop
 sleep 1
 $0 start
 ;;
  *)
 echo "Usage: $NAME {start|stop|restart}" >&2
 exit 1
 ;;
esac

exit 0

2015年12月14日 星期一

無線隨意網路路由協定 (Routing Protocols for MANET)---DSR&AODV&TORA

無線隨意網路路由協定 (Routing Protocols for MANET)

8.1 無線隨意網路簡介 

8.2 主動式路由策略 

8.3 回應式路由策略 

8.4 主動式與回應式路由之比較

8.5 位置輔助路由 (location-based routing)策略 

8.6 結語

8.3 回應式路由策略

回應式(reactive)路由又稱On-demand routing (經需求路由)
主動式(路由表) vs. 回應式 ->8.4
回應式路由只尋找與維護有需要的路由
主動式路由則不論需要與否所有路由均須維護
回應式路由
優點: 省去一些不必要的路由維護
             適合偶發訊務(traffic)且一但發生則有大量的訊務;通訊只涉及少 數節點
缺點: 首次尋找耗時較多時間做路徑尋找造成封包延遲

回應式路由例子:
            動態來源路由 (Dynamic Source Routing , DSR)
            隨意依需求距離向量路由(Ad hoc On-demand Distance Vector, AODV) 
            臨時排序路由演算法 (Temporally Ordered Routing Algorithm, TORA)

回應式路由協定 –DSR(Dynamic Source Routing)

來源路由(Source routing)的基本精神:
1.封包的整個路由在來源地(source)已決定並置放在該節點的路由快取貯存區 (route cache) 
2.路由路徑資訊在封包標頭中;中繼節點按此資訊傳送封包。 

(要到的目地地無路由時) 啟動路由探索程序(Route discovery procedure):
1.由節點送出路由請求(route request, RREQ)封包來啟動
2.中繼節點收到RREQ時,若收過此封包則丟棄,不然就更新封包內部資訊後繼續廣播此RREQ封包 

當此封包到達目的地或中繼節點的route cache中有目的地節點資訊時則回覆路由回應(Route Reply, RREP)封包
RREP封包利用來源路由(Source routing)的策略回傳至來源節點

當來源節點收到RREP封包後可開始傳輸資料封包 


路由錯誤(Route Error, RERR)封包 : 
1.在DSR協定中,當連結失敗 (即傳送封包給下一站時遇到 失敗)則會產生”路由錯誤(RERR)”封包送回並告知來源地
2.沿途的節點會把該路由資訊清除 
3.當來源地收到REER封包後會重新啟動路由探索程序找替代路徑 

DSR使用來源路由(Source routing)及路由快取貯存區 (route cache)策略有下列優點
1.避免路由迴圈的產生(Routing Loop free) 
2.RREQ與RREP皆有整個路由路徑資訊
3.各節點可記錄路由 路徑資訊於route cache 
4.加速封包傳輸  RREQ與RREP皆有路由路徑資訊
5.可以有多條路由路徑
6.增加可靠性 (reliability)

回應式路由協定 –AODV(Ad-hoc On-Demand Distance Vector Routing)

AODV:使用如同DSR的路由探索使用RREQ與RREP 廣播機制找尋路徑。
採用不同機制維護路由資訊: 使用傳統路由表 (目地、下一、跳躍數) 。
AODV捨棄 source routing而依靠著中繼節點機動地建立的路由表項 目(route table entries)。 

AODV 使用:
             1.DSDV的目的地序列編號演算法
                           距離向量 
                           序列編號 
             2.使用計時器(timer)保持路由新鮮。

回應式 (on-demand)產生路由:不在路由路徑(selected path)上的節點不需保有路由資訊與交換路由資訊。

目標:降低廣播經常費用(overhead)與傳輸延遲

對每一目的地路由表有一列資訊包含 :
<destination addr , next-hop addr , destination sequence number , life tine>
• 目的地 
• 下一節點 
• 量度 (metric) : 跳躍數 (hop count) 
• 目的地序號 (Sequence number) 
• 路由表項目過期時間[計時器]:被用過即重置,否則expire掉
• 來源節點廣播RREQ封包
• 中繼節點轉送至目的地節點
• 目的地節點以<broadcastID,src-address>來分辨RREQ 封包;且當收到第一個RREQ 封包時回應RREP封包



AODV-Route Discovery:

1.先檢查table->Yes 送
2.No->Source送RREQ
RREQ封包內容:<source IP addr , source current sequence number , destination IP addr , destination seq number>
封包也有Broadcast ID number(src 給)
所以當有Broadcast ID and Source IP addr就可以知道具唯一性。


Reverse Route Entry:

當node收到RREQ,會在route table建立一個reverse route entry
格式:<Source IP Address , Source seq. number , number of hops to source node , IP address of node from which RREQ was received>
使用這個reverse route entry去送RREP回Source,本身entry也具Life Time

RREP格式: <IP addr of source and destination>

If RREP sent by destination:
<current seq# of destination , hop-count= 0 , life-tine>


If sent by intermediate node
<destination seq number , hop-count=its distance to destination , its value of the life-tine>

When a node received a RREP means it can set up a forward path entry
<IP addr of destination , IP addr of node from which tje entry arrived , hop-count to destination , life-time>

When a node received multiple RREP 
- only forwards the first RREP
- May forward another RREP if that has greater destination seq number or a smaller hop-count
- Rest are discarded


NOTE:若Table中可以找到一個entry且Seq, number >= RREQ那可以直接送去destination
否則繼續轉送RREQ並增加hop-count

回應式路由協定 –TORA(:Temporally Ordered Routing Algorithm)

TORA : 為一回應式路由協定

路由探索程序:算出多條通往目的地之路徑->目的地導向的有向無迴圈圖(directed acyclic graph, DAG*) 
NOTE:*無線隨意網 路可被視為無方向的圖 (undirected graph) 但TORA將此圖的邊(edges)給與方向:朝向目的地節點。 

每個節點會記錄至任一目的地的距離又稱高度值。 封包送往目的地依其高度值遞減如水往下流。 

如何建立高度值:使用詢問(query) /更新(update) 機制 
當一節點嘗試送出封包時會發出詢問(Query)封包, 該封包廣播至整個網路直到目的地或有至目的地路 由的節點。接著此點會回覆更新(update)封包(包含自 己高度資訊)。
當其它結點收到更新(update)封包後…會更新其高度 值。
各節點的高度值建立成功,形成一以目的地導向的DAG 
當連結失敗時,節點發現它的高度值為局部最小時;則 會將其高度值提高並發出更新(update)封包


8.4 主動式與回應式路由之比較



定義:流量密度/差異(traffic diversity) ?[流量分布的情 形]
低流量密度:集中於網路的少數節點
高流量密度:平均分散於網路的每個節點

回應式路由能適應不同流量密度(較適合低流量密度); 路徑非最佳,主動式路由則不受流量密度所影響。
高流量密度:路由負擔相當但:回應式路由->次佳路徑; 主動式路由->最佳路徑 
低流量密度:回應式路由->表現較佳 
->混合式路由(ZRP)

ZRP為一混合式路由協定。
一節點的區域(Zone):半徑(= hop counts) 內的所有節點。
邊緣節點(Border node):半徑上的所有節點。
Zone內使用連結狀態(link state)的主動式路由協定
 Zone間使用回應式路由協定的路由探索程序,其路由 請求封包只送往邊緣節點直到目的地的邊緣節點後回 覆。 


回應式路由 在路由探索(route discovery)造成較 長的延遲  不適用於對延遲 敏感(delay sensitive)和極短暫的應用(如問答) 





無線隨意網路路由協定 (Routing Protocols for MANET)----DSDV

無線隨意網路路由協定 (Routing Protocols for MANET)

8.1 無線隨意網路簡介 
8.2 主動式路由策略 
8.3 回應式路由策略 
8.4 主動式與回應式路由之比較
8.5 位置輔助路由 (location-based routing)策略 
8.6 結語

8.1 無線隨意網路

特性:

1.移動性(影響路由)
2.多點跳躍(multi-hop)
3.自我組態(self-configuration):node可以決定自己的參數[IP、路由表、位置]
4.可延伸性
5.安全性

無線隨意網路可隨時隨地可建立,無固定基礎架構,不需事先規劃與佈置;由自我(self)組態而 自動(auto)組織而成,成員可隨時加入或離開,通訊方法:單播(uni-cast),群播 (multi-cast)。
大型的隨意(Ad-Hoc)網路封包傳輸須中繼站轉播 -->多點跳躍 (multi-hop) --> 路由(routing) ) 
[不同於(802.11)中定義的IBSS屬 單點跳躍(one-hop)可直接溝通無中繼站轉播,故無路由問題]
而單播(uni-cast)]路由策略又分以下四種:
1.主動式 (proactive):事先建立 (又稱 table-driven) [8.2] 
2.回應式 (reactive):只尋找與維護有需要的路由 [8.3] 
3.位置輔助 (Location-based):利用節點的位置資訊 [8.4] 
4.混合式 (Hybrid):主動式及回應式的混合[8.5]

8.2 主動式(proactive)路由策略


(無線隨意網路)主動式路由可分為:
距離向量 (Distance Vector, DV)法:記錄自己到網路中所 有節點的距離及要往該節點路由的下一個節點(向量)。 節點間交換距離向量(DV)資訊,從而計算出自己到各節 點的最佳路由。

連結狀態 (Link State)法:記錄自己的連結狀態。節點間 交換連結狀態,從而計算出自己到各節點的最佳路由。

距離向量(DV)不適用於隨意網路 (ad-hoc networks) ,因為網路連結失敗造成 路由迴圈 (Routing Loops)產生跳躍數無限 (Count to Infinity),所以須要另找協定避免上述問題 ,
ex:目的地序列距離向量 (Destination-Sequenced Distance-Vector, DSDV) 協定


距離向量(Distance-Vector)路由協定


DSDV 協定:

DSDV是基於傳統Bellman-Ford路由選擇演算法所 改良而發展出來的,是一個以路由表(routing table)為基礎的通訊協定。 故每一個行動節點必須儲存一張路由表。須紀錄所有與該節點可能進行連結節點的距離。除給自己節點一個序列編號外,路由表內的每筆紀錄 同時還包含了一個目的地序列編號(destination sequence number):用來判斷路徑的新舊,以避免迴路的產生。

當網路拓樸變動比較不頻繁時,並不需要將路由表的所有資料進行交換。DSDV在每個節點內再加了一個table,用來記錄其路由表從上次交換至今所更改的部分。如果更改很多[或定期地],就進行全部資料的交 換,稱為全路由更新 (full routing update);如果 改變很少,就只針對改變部分交換,稱為累加式路由更新 (incremental routing update)

特性:

保有距離向量 (Distance Vector)的簡易性 
1.保證無迴路 ->路由表內新增一表項目 (Table Entry):目的地序列編號 (Destination Sequence Number) 
3.對拓樸改變反應迅速??? 
       ->當路由表有顯著改變;立即做路由廣告(route advertisement)。 
       ->但對未穩定路由(unstable routes)採等待策略;而不立即做路由廣告 (damping             fluctuations) 

路由選取:


更新資訊與路由表比較: 
1. 選取目的地的序號 (destination sequence number) 較高的路由 (保證使用來自目 的地的最新資訊) 
2. 當目的地的序號一樣時,選取量度(Metric) [=至目的地的hop counts]較佳的路由

路由表範例





新節點加入:



無迴路,無跳躍數無限:






降低路由表的波動:

對每一個特殊目的地,保留關於最先到來的路由最佳路由的到來的時間長度的資料。
依據這資料,决定延遲廣告 (可能將很快改變的) 路由 ,因而降低路由表的波動 (damping (抑制/降低) fluctuations )。通常為了減少相同序號編號之路由廣告的重播的數量 會延遲可能不穩定之路由廣告 。

何謂路由表的波動 :

路由表A中的項目D:[D, Q, 14, D-100] 
D 廣播序列編號 D-102  A 由P 收到D 的更新廣播:(D, 15, D-102) 
路由表A中的項目D:[D, P, 15, D-102] A 必須立即散播(propagate)此路由。
A 由Q收到D 的更新廣播:(D, 14, D-102)
路由表A中的項目D:[D, Q, 14, D-102] A 必須立即散播(propagate)此路由。
若不立即散播由P 收到的D 之更新廣播而延遲一 段時間,也許只要散播由Q 收到的D 之更新廣播 這可能發生在每一次在點D或其他節點做它的 更新廣播後導致在網路 上多餘的路由廣告,即 所謂波動 (fluctuations)。

如何緩和路由表波動:

於個別的表格上記錄上一次的決定時 間(Settling Time)與決定時間的平均。 [ 一個序列编号的第一個路由到來與最 佳的路由到來的時間間隔叫做決定時 間 (Settling Time)。]
當一個較新的特定序列编号的第一個 路由到來時,節點A仍然必須更新它的 路由表;但是它會等待一段時間才將 它散播。建議的等待時間約為平均決 定時間的兩倍。
在大型網路中像這的波動可以被降低 以避免多餘的廣告,因而節省了頻寬。

連結狀態(link-state)路由協定:


多重傳遞點(Multipoint Relay, MPR)概念:

1.單點跳躍 (1-hop):節點A 與節點B能直接相互通訊時,我 們稱A與B為(直接) [單點跳躍 (1-hop)]鄰居;又稱A到B或 B到A為單點跳躍(1-hop) 。[單向通訊vs.雙向通訊???]

2.覆蓋:節點B與節點A為一單點跳躍的關係;我們可以說 節點B為節點A (或節點A為節點B)所覆蓋。 

3.兩點跳躍 (2-hop):節點A與節點B及節點B與節點C皆為單 點跳躍(1-hop)的關係;但節點A與節點C無單點跳躍(1- hop)的關係時->節點A與節點C為一兩點跳躍(2-hop)的關係。又稱節點A為節點C[或節點C為節點A]的兩點跳躍(2- hop)鄰居

4.在節點A的單點跳躍 (1-hop)鄰居內選出一組特殊節 點;稱這些節點集合為”多重傳遞點” (Multipoint Relay, MPR)。
這些特殊節點要愈少愈好且滿足:節點A選出的MPR集合要能覆蓋節點A的所有兩點跳躍(2- hop)鄰居。PS:此最佳化問題為一NP-hard的問題




























2015年11月23日 星期一

Self-management in chaotic wireless deployments

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

Unplanned

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

Unmanaged

這個議題主要在探討parameter的,例如SSIDchannel,以及較複雜的問題,包含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-overlappingchannel(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設為6n設為4
ERF(Estimated Rate Fallback):混合上述兩種方法的rate selection Algorithms,首先測量channel SNRERF 再選擇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 marginUnlimited的情況下,victimthroughputARFERF幾乎的零,原因在於,victim可以senseaggressor,因為aggressortransit power較高,但aggressor無法sensevictim,導致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次的ACKSender 就會調高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 collisionsSender就會增加它的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 EtxErx代表接收端的energy level,而Etx代表在傳送端的energy level,如果兩者不相同代表networkasymmetric     
,如果>0,代表接收端的contenting station較多,必須要放大CW,以減少競爭,相反則縮小CW,鼓勵Sender傳輸。調整方式定義於圖二。

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


以及
      
圖二
綜合以上,如果Sender發現Receiver在不同的energy levelsender就先保留CW的調整,先做data rate的調整,將send rate調整至Erx level下的rate,如果兩邊的ErxEtx在相同energy level,再依Ediff對CW做相對應的調整。
 
       



(2)  simulation
a. Symmetric Environment



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


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