Capacity of Ad Hoc Wireless Networks - Junyang Li , Charles Blake , Douglas S.J. De Couto , Hu lmm Lee , Robert Morris

Capacity of Ad Hoc Wireless Networks

1.Introduction:

    因為空間頻譜的再利用，可預期Ad Hoc 網路的總容量可增大到覆蓋該區域面積。然而，ad hoc的路由機制需要節點間的合作來相互傳送其他node的封包，這樣使得每個node不只受限於raw channel capacity還有遠方node帶來的forwarding load，這嚴重影響了ad hoc的路由路徑。

    根據Gupta 和 Kumar的分析，total one hop的capacity約等於O(n*n^(1/2))，每個節點的end-to-end throughput約等於O(1/n(^1/2))，n為節點個數，所以當節點數不斷的增加，throughput會接近"0"，這是因為這簡單的分析省略了用來判斷是否有任何影響特定單一節點的網路吞吐量常數。

    因為限制容量的因素，ad hoc傾向於使用low data rate。本篇paper中使用Interaction between ad hoc forwarding and 802.11MAC和impact of communication來了解應用在實際網路的可行性。

2. 802.11Background

    To reduce collisions caused by hidden terminals [1] in the network, 802.11 uses a four-way RTS/CTS/Data/Ack exchange.
RTS/CTS 機制是基於CSMA/CA 協定上，所提出改善隱藏節點問題的機制。 原本CSMA/CA機制資料的傳送，僅需用到Data 及 ACK，發送端傳Data，接收端收到後回覆ACK。 而啟用RTS/CTS 機制後，則是發送端先送RTS 提出請求，接收端回覆CTS，前兩步驟用意就是在確認傳輸用通道，及通知週遭節點 Freeze Backoff time，用意就是避免碰撞及干擾。 完成後發送端才傳送Data，接收端回ACK。 
    Each node uses these times to update its “network allocation vector” (NAV). The NAV value indicates the amount of time remaining before the network will become available.

NAV是避免其他站台傳給正在傳送中的兩台站台，RTS/CTS是無法避免COLLISION，因為還是有可能會同時多台同時送RTS/CTS而發生RTS/CTS COLLISION ，RTS/CTS是很小的所以發生碰撞比傳送中的資料(DATA封包>>RTS/CTS)發生碰撞還要省時間NAV是避=免傳送中的兩台站台的範圍內的其他站在暫停去送，DATA給正在傳送中的站台

3.MAC interactions

本篇paper使用的ns模擬器data rate為2M bps，傳輸有效範圍為200m，干擾範圍為550m，節點之間距離為200m。

Single Cell Capacity:

每個節點都是src，隨機選一個dst傳送，因為2-node的狀況下沒有其他node的干擾，capacity可達到最大，因RTS/CTS,header的影響，最大的吞吐量約等於1.7Mbps。

Capacity of a Chain of Nodes:

因不能同時接收/傳送，node1、2與node1、3不可同時傳送，只有node1、4可以同時傳送，這使得chain utilization只有1/3，又因為傳輸範圍<干擾範圍，node4的資料傳輸會干擾到node1、2的RTS/CTS，所以chain utilization降為1/4，實際模擬最大的吞吐量為4.1Mbps約等於1/4。但是，當chain夠長的時候，offered load increase > optimum，吞吐量會急速下降到1/7，這是因為chain中間的node受到的干擾比第一個node還大，沒辦法跟上第一個node傳來的data，導致吞吐量的下降。

Capacity of a Regular Lattice Network:

左圖為horizontal，每個node流量從左到右，每當第三條chain激活時，其垂直干擾可能達到550m，在iner-flow的影響下，每個flow的吞吐量會降至1/12；右圖為horizontal and vertical，每個node的流量為左到右，上到下，每個node都有一個Queue，這會讓node再傳送水平封包時會失去傳送垂直封包的機會，增加的back-off使得吞吐量下降，根據模擬出的結果，其吞吐量比預期的還低。

Random Traffic in a Random Layout:

node隨機均勻分布，每個node都是src並隨機挑選dst點然後計算最短路徑，因不規則的放置node導致浪費空間，進而浪費容量，隨機選擇dst也導致更多的packet通過網路的中心部分，使得整體的capacity由中心來控制，然而，Lattice的分布是相對勻稱的。

4.Scaling Ad Hoc Network:

比較一個大型的網路capacity與node的loading，估計bandwidth使每個node可預測自己的traffic。

one-hop capacity取決於整個網路的頻寬再利用量，在固定射頻範圍R，空間再利用率與網路實際面積成正比，假設node密度為d，網路實際面積為A，n為node數，A=n/d，整個網路的capacity為C，可得C = kA=k*n/d，封包hop數L/R，封包速率V，所以C<n*V*L/R。

得

可知路徑長度增加，每個節點的Badwidth也會增加，所以這對ad hoc網路擴充性有很大的影響。

Random traffic pattern:

假設每個node的機率皆相同，且個別的節點capacity可達到O(1/n^(1/2))，固定的傳輸範圍，獨立網路大小，且網路增大時預設路徑長度也固定，使每個node的capacity都固定。

5.Conclusion:

當網路增大時，802.11 MAC interaction forwarding對capacity及node的scalability是有影響的，而在long chain中，因greedy sender導致吞吐量下降，所以發現在traffic pattern中隨機流量分布模式可以使得每個node的capacity接近理論值O(1/n(^1/2))