聯合無線網絡編碼與TCP Vegas的多播協議優化研究

徐 斌，季 敏，譚國平

（河海大學 計算機與信息學院 通信與信息系統研究所，江蘇南京 210098）

目前已經存在多種移動自組網多播協議，而網絡編碼機制的出現打破了原基于存儲轉發協議性能的局面。由文獻[1]可知，采用網絡編碼的多播協議可達到最大流最小割定理的上限。而文獻[2-3]中所講述的實時多播路由協NCRM（Network Coding based Real-Time Multicast），不但減少了網絡中數據包的轉發次數，而且降低了節點能耗，更加改善了網絡的吞吐量。但當接受節點數受限，業務傳輸負載增加時，NCRM的節點的編碼、解碼速度將不及數據包傳輸的速度，不可避免的出現網絡擁塞現象，既造成丟包率的急劇增大，也使得系統的總開銷急劇增加。

因此文中借鑒了TCPVegas擁塞機制的思想，在NCRM的基礎上實現了一種基于窗口擁塞控制機制的多播路由優化機制 WCC-NCRM （Window-based Congestion Control-NCRM）。將TCPVegas擁塞控制的思想融入實時多播路由協議NCRM中，不但使網絡中的數據包數量控制在一定的水平，以避免網絡沖突加大，也盡可能平滑的處理數據分組的丟失。當業務傳輸負載增大時，既保證了高于NCRM的分組投遞率，也顯著降低了系統的總開銷，從而彌補了NCRM的缺陷，提高了多播業務可靠性。

1 TCP Vegas、WCC-NCRM協議機制

1.1 TCP Vegas擁塞控制

L.S.Brakmo等人在1994年提出了一種基于時延rtt（round-trip time）的擁塞控制機制TCPVegas[4]。該算法核心通過觀察回路往返時間rtt的變化來估計網絡擁塞狀況，借助rtt找出期望的傳輸率Ep和真實傳輸率Ap之間的差異值Diff來調整擁塞窗口進而調整數據的發送速率，以提高吞吐量、降低分組丟失率，更多的相見文獻[5]。TCPVegas擁塞控制算法主要分為慢啟動階段、擁塞避免階段、超時重傳階段，TCPVegas機制的參數設置如表1所示，各階段。

介紹如下：

1.1.1 慢啟動階段

為防止TCP連接啟動時向網絡中傳輸過多的數據包，而導致TCP傳輸成功率的急劇下降，因此采用慢啟動的方式。TCP連接建立時設定一個初始值為w擁塞窗口，其參數值為w=（α+β）/2，參數 α 和 β 作為窗口調整基準的門限值[6]（經驗值分別設為1和3）。當發送節點收到第一個數據包反饋消息ACK的rtt時，并不調整擁塞窗口大小，并將此時的rtt設定為basertt。當大約經過兩個rtt后才將窗口大小增加一倍。若當TCPVegas根據Diff檢測到網絡擁塞時，此時進入擁塞避免階段。

表1 TCP Vegas機制的參數設置Tab.1 The parameter setting of TCP Vegas mechanism

1.1.2 擁塞避免階段

TCPVegas擁塞窗口調整機制的目的就是將緩存數據維持在兩個門限值之內，以維持整個網絡穩定。TCPVegas擁塞窗口調整機制算法如式（1）。

當Diff＞β時，意味著數據傳輸速率太快，表明網絡開始發生擁塞，此時減小w的值來減緩數據傳送的速率。反之，當Diff＜α時，應該加大w的值以增加數據傳送的速率。若α＜Diff＜β時，表示網絡使用率比較穩定，此時不需要調整擁塞窗口的大小。

1.1.3 超時重傳階段

為使Vegas能夠及時的重傳丟失的分組，Vegas摒棄了以往所采用的要收到3個重復ACK后才進行的重傳策略，而是在收到了1個或者2個重復的ACK后，就啟動重傳機制，此種機制顯著提升了TCP應對分組丟失的響應速度。

現今的網絡通信中，流量控制和擁塞控制主要是基于TCP協議，其核心思想是采用了數據包的滑動傳輸窗口思想，而窗口的大小決定于反饋消息，Vegas的優點在于擁塞機制的觸發只與rtt的變化有關，而與包的具體傳輸時延無關，能夠較好的預測網絡帶寬的使用情況。

1.2 WCC-NCRM的算法處理機制

借鑒TCPVegas擁塞控制機制的思想，在NCRM的基礎上實現了一種的基于窗口擁塞控制機制的多播路由優化協議WCC-NCRM。WCC-NCRM算法機制主要分為3個模塊：發送端處理模塊、中間節點處理模塊以及接收端處理模塊。其中發送端處理模塊又分為發送窗口內數據發送處理、接收到反饋消息后發送窗口調整處理這兩個部分，WCC-NCRM的擁塞控制的系統參數設置如下表2所示，其中特別注意的是發送窗口大小可以自適應調整，本文仿真分析中設置W初始大小為8，各模塊處理機制如下：

表2 WCC-NCRM擁塞控制參數表Tab.2 The parameter table of congestion control for WCC-NCRM

1.2.1 發送節點處理機制

1）發送端發送窗口內數據的發送處理流程

發送節點在發送數據包之前設定一個用于存儲分組塊序號block_id的發送窗口緩存和一個初始大小為INIT_WIN的發送窗口，該發送窗口的LOWER_ID（之后更新為發送端當前發送的分組塊號）初始化為1，UPPER_ID初始化為INIT_WIN-1。這里定義只有分組塊序列號滿足LOWER_ID＜block_id＜UPPER_ID時，才符合發送條件。

當網絡層接收應用層傳輸來的數據包時，首先通過UID（唯一標示符）將數據包進行分塊，本文中編碼塊長度定義為BLOCK_SIZE，即BLOCK_SIZE個數據包組成一個block。每個block的分組塊序號可由式（2）得到：

將得到的分組塊號存入該數據包包頭的block_id域中，隨之將處理完的數據包存入該發送節點的本地緩存中。當本地緩存中接收滿一個block_id的數據包時，首先將發送節點當前處理的分組塊號current_block_id設置為block_id，再將該block_id存入發送窗口緩存中。判斷該current_block_id是否小于UPPER_ID且大于LOWER_ID，如滿足此條件，則該分組塊獲得發送機會。此時，對存儲在發送節點本地緩存中的所屬于該分組塊的原始數據包進行初始網絡編碼，編碼完成后將相應的編碼向量存入WCC-NCRM包頭的編碼向量域中和編碼包一起傳輸。若current_block_id不符合發送窗口的發送條件，則不會對該分組塊進行初始編碼和發送操作，而在發送窗口中等待窗口調整完后再操作。

發送節點每發送完一個分組塊的所有初始編碼包后進行第一次窗口調整：發送窗口的LOWER_ID向上調整一次，UPPER_ID向上調整0.5個，即發兩次分組塊推動發送窗口前進一次。這是應對當網絡發生擁塞時，由于核心節點不能及發送反饋消息以調整發送窗口而造成的網絡癱瘓。經過以上操作后檢查發送窗口緩存是否為空，若不為空則將current_block_id設置為發送窗口緩存中序號最小的分組塊號，并且繼續進行上述操作，將發送窗口緩存中的所有符合發送條件的分組塊全部編碼并完成發送。

2）接收到反饋消息后發送窗口調整流程

發送端接收到反饋消息后先判定該反饋消息是否是首次收到的，若是首個反饋消息，則先根據反饋消息計算出該分組塊的一次往返時間rtt，并設定為basertt，同時將發送窗口的UPPER_ID向上調整2次。若不是首個反饋消息，則與TCPVegas的方法類似，首先計算出預期傳輸率和實際傳輸率之間的差異值diff。然后再根據diff的值來調整發送窗口的大小。與TCPVegas的方法不同的是，無論diff值為多少都會更新一次basertt，實時的更新basertt可以避免TCPVegas機制中的不公平資源分配問題。WCC-NCRM發送窗口調整機制可用式（3）表示。

如果diff小于0，則說明當前解碼的分組塊的往返時間要小于首次的數據包往返時間，因此更新basertt，此時不調整發送窗口大小。根據TCPVegas中所用的門限參數，若diff小于α，意味著分組傳輸速率較慢，網絡使用率低，因此將發送窗口的UPPER_ID向上調整4次，同時將此時的rtt設定為basertt；若diff大于β時，意味著傳送速率太快，表明網絡開始擁塞，因此將發送窗口的UPPER_ID向下調整1次，并將此時的rtt設定為basertt。最后若diff的值大于且小于時表示網絡使用率比較穩定，無需調整發送窗口大小。

1.2.2 中間節點處理機制

WCC-NCRM中間節點的處理過程與文獻[2]中的NCRM處理過程一致。當中間節點收到一個新的block的編碼包時，首先會檢查編碼包中是否含有新信息，如果包含新的信息，則會將此編碼包存儲到本地緩存中，如果沒有包含新信息則會丟掉該編碼包。針對每個分組塊，都會設定一個專門的定時器，其時長為BLOCK_TIMEOUT。當中間節點在此時長內收集到關于某分組塊的BLOCK_SIZE個編碼包時，則會直接對該分組塊進行二次編碼。同時將編碼后的新編碼包廣播給它的鄰居節點，以提高整個網絡的解碼成功率。反之，如果中間節點在BLOCK_TIMEOUT時長內并未收集夠關于某分組塊的足夠編碼包，它會向其鄰居節點請求冗余編碼包后再進行二次編碼。值得注意的是二次編碼的編碼包的個數是可以根據當前場景的網絡狀態自適應調整的。例如在網絡結構中節點密度較小的情況下，二次編碼時產生成較多的編碼包可以確保比較高的分組投遞率。

1.2.3 接收節點處理機制

核心節點解碼的成功率基本可以代表整個mesh網絡的解碼成功率，本機制除了利用發送節點調整發送窗口大小之外，主要是利用核心節點的反饋消息來調整發送窗口大小。如果核心節點收集夠關于某編碼塊的BLOCK_SIZE個線性無關的編碼包，則該接收節點便可以利用高斯消元法順利恢復出該編碼塊的原始數據包，同時生成一個反饋消息給發送節點，該反饋消息的序列號就是成功解碼的序列號。

其他節點對解碼的處理方式與核心節點一樣，在定時器超時前收集夠某編碼塊的BLOCK_SIZE個線性無關的編碼包，則可恢復出該編碼塊的原始數據。同時會對該編碼塊重新編碼并發送給下游節點繼續傳遞編碼包。若接收節點定時器超時前，未能收集夠關于某編碼塊的編碼包，則會向其鄰居節點請求冗余編碼包以完成解碼操作。

2 性能分析

為了更好的評估WCC-NCRM協議的性能，我們在NS2仿真平臺[8]上搭建了相應仿真環境。仿真參數設置如下：36個節點均勻分布在750 m×750 m的區域中；節點平均停留時間為0 s；移動模型采用隨機路徑點移動模型[7]（RWP）；節點信號覆蓋范圍為250 m，信道容量為2 Mbps。應用層采用單個數據包大小為512 byte的恒定比特數據流（CBR）來模擬多播業務；傳輸層采用用戶數據包協議（UDP）；網絡層分別采用NCRM和WCC-NCRM；仿真時間為30 s。

此移動模型下的仿真仍然設置在單個多播組中，業務傳輸負載分別設為 5、7.5、10、12.5、15、17.5、20、22.5（kb/s），接受節點個數為20個，節點的移動速度為15 m/s，并取NCRM和WCC-NCRM的BLOCK_SIZE均為4。限于篇幅，文中只討論業務傳輸負載變化情況下，NCRM和WCC-NCRM的性能對比，其他場景下有著類似的性能。為確保仿真結果的可信度，每組仿真參數在移動模型下都會生成8個多播仿真場景，然后在每個仿真場景下分別進行10次仿真，最終通過計算平均值，得出在隨機路徑點移動模型中關于WCC-NCRM和NCRM的分組投遞率及總開銷，仿真曲線如圖1和圖2所示。

圖1 RWP分組投遞率vs.傳輸負載Fig.1 RWPpack delivery ratio vs.traffic overload

圖2 RWP總開銷vs.傳輸負載Fig.2 RWPoverhead vs.traffic overload

如圖1所示，當傳輸負載大于7.5 kb/s且小于20 kb/s時，在WCC-NCRM協議下的分組投遞率將明顯高于NCRM的，說明本優化協議改善了在傳輸負載相對增大范圍內的網絡擁塞現象，并且提升了分組投遞率，提高了網絡資源的利用率。但隨著傳輸負載逐漸增大時，在WCC-NCRM和NCRM協議下，mesh網中各節點的編碼、解碼速度都將不及數據包的傳輸速度，網絡出現擁塞現象，從而造成丟包率的增大，引起分組投遞率的急劇下降。

如圖2所示，因采用WCC-NCRM協議后，網絡擁塞現象得到改善，系統丟包率平滑下降，mesh網中的節點將減少請求資源的操作，從而導致了其數據包轉發次數的下降，以至于WCC-NCRM協議下的系統總開銷將遠小于NCRM協議下的系統總開銷。但隨著傳輸負載的增大，因節點不能及時成功的解碼，mesh網中的節點將更多的處于請求資源操作中，從而導致了數據包轉發次數的增多，以至于兩種機制下的系統總開銷都會有所上升。

3 結束語

文中提出了一種可靠的基于TCP-Vegas擁塞控制的多播路由優化機制WCC-NCRM，將TCP-Vegas擁塞控制算法思想融入NCRM中，實現了在業務傳輸負載增大的情況下，緩解網絡擁塞狀況，提高網絡資源利用率，既維持較低的系統總開銷，又保持了較高的分組投遞率，提升了整個系統的可靠性。

由于WCC-NCRM機制中的關鍵因數rtt對整個系統起著決定性作用，如何消除rtt對WCC-NCRM的性能影響，更好的提高機制的總體性能，有著重要研究意義。下一階段會對rtt進行改進以減少因rtt抖動造成的WCC-NCRM性能的下降，最終得到一種最優的基于窗口擁塞控制的多播路由優化方案。

[1]Ahlsw ede R，Cai N.Network information flow[J].IEEE Trans.Inform.Theory，2000，6（4）:1204-1216.

[2]譚國平，倪新洋，季敏，等.一種基于網絡編碼的移動自組網實時多播協議[J].微電子學與計算機，2011，28（8）:12-14.TAN Guo-pin，NI Xin-yang，JI Min，et al.NCRM:A network coding based on real-time multicast protocol in mobile Adhoc networks[J].Microelectronics and Computer，2011，28（8）:12-14.

[3]譚國平，季敏，倪新洋，等.網絡編碼VS.存儲轉發：移動自組網中實時多播機制仿真研究[J].成都信息工程學院學報，2011，26（3）：298-303.TAN Guo-pin，JI Min，NI Xin-yang，et al.Network coding vs store-and-forwarding:simulation studies on real-time multicast mechanisms in Ad-hoc networks[J].Journal of Chengdu University of Information Technology，2011，26（3）:298-303.

[4]Brakmo L S，Maney S W.Peterson L L.TCP Vegas:new techniques for congestion detection and avoidance[C].Proceedings of ACM SIGCOMM94，1994 24-35.

[5]劉國柱，高文娟.基于TCPReno和TCPVegas擁塞控制性能研究[J].計算機工程與設計，2011，32（2）:434-437.LU Guo-zhu，GAO Wen-juan.Research of congestion control performance based on TCPReno and TCPvegas[J].Computer Engineering and Design，2011，32（2）:434-437.

[6]李鵬，陳元琰，羅曉署.無線異構網絡環境中基于擁塞狀態區分的TCPVegas改進算法[J].計算機應用，2010，30（2）:309-311.LI Peng，CHEN Yuan-yan，LUO Xiao-shu.TCP Vegas-P:enhanced TCP Vegas congestion control algorithm based on congestion status differentiation over wireless heterogeneous network[J].Journal of Computer Applications， 2010，30（2）:309-311.

[7]童超，龍翔，高小鵬.基于隨機路徑點模型的Ad hoc網絡復雜統計特性[J].北京航空航天大學學報，2008，34（10）1236-1242.TONG Chao，LONG Xiang，GAO Xiao-peng.Complexity statistical characteristics for Ad-hoc networks based on random way point model[J].Journal of Beijing University of Aeronautics and Astronautics，2008，34（10）1236-1242.

[8]黃化吉，馮德力.NS網絡模擬和協議仿真[M].北京：人民郵電出版社，2010.