徐 斌，季 敏，譚國平

（河海大學(xué) 計算機與信息學(xué)院 通信與信息系統(tǒng)研究所，江蘇南京 210098）

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

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

1 TCP Vegas、WCC-NCRM協(xié)議機制

1.1 TCP Vegas擁塞控制

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

介紹如下：

1.1.1 慢啟動階段

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

表1 TCP Vegas機制的參數(shù)設(shè)置Tab.1 The parameter setting of TCP Vegas mechanism

1.1.2 擁塞避免階段

TCPVegas擁塞窗口調(diào)整機制的目的就是將緩存數(shù)據(jù)維持在兩個門限值之內(nèi)，以維持整個網(wǎng)絡(luò)穩(wěn)定。TCPVegas擁塞窗口調(diào)整機制算法如式（1）。

當(dāng)Diff＞β時，意味著數(shù)據(jù)傳輸速率太快，表明網(wǎng)絡(luò)開始發(fā)生擁塞，此時減小w的值來減緩數(shù)據(jù)傳送的速率。反之，當(dāng)Diff＜α?xí)r，應(yīng)該加大w的值以增加數(shù)據(jù)傳送的速率。若α＜Diff＜β時，表示網(wǎng)絡(luò)使用率比較穩(wěn)定，此時不需要調(diào)整擁塞窗口的大小。

1.1.3 超時重傳階段

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

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

1.2 WCC-NCRM的算法處理機制

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

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

1.2.1 發(fā)送節(jié)點處理機制

1）發(fā)送端發(fā)送窗口內(nèi)數(shù)據(jù)的發(fā)送處理流程

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

當(dāng)網(wǎng)絡(luò)層接收應(yīng)用層傳輸來的數(shù)據(jù)包時，首先通過UID（唯一標(biāo)示符）將數(shù)據(jù)包進行分塊，本文中編碼塊長度定義為BLOCK_SIZE，即BLOCK_SIZE個數(shù)據(jù)包組成一個block。每個block的分組塊序號可由式（2）得到：

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

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

2）接收到反饋消息后發(fā)送窗口調(diào)整流程

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

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

1.2.2 中間節(jié)點處理機制

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

1.2.3 接收節(jié)點處理機制

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

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

2 性能分析

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

此移動模型下的仿真仍然設(shè)置在單個多播組中，業(yè)務(wù)傳輸負載分別設(shè)為 5、7.5、10、12.5、15、17.5、20、22.5（kb/s），接受節(jié)點個數(shù)為20個，節(jié)點的移動速度為15 m/s，并取NCRM和WCC-NCRM的BLOCK_SIZE均為4。限于篇幅，文中只討論業(yè)務(wù)傳輸負載變化情況下，NCRM和WCC-NCRM的性能對比，其他場景下有著類似的性能。為確保仿真結(jié)果的可信度，每組仿真參數(shù)在移動模型下都會生成8個多播仿真場景，然后在每個仿真場景下分別進行10次仿真，最終通過計算平均值，得出在隨機路徑點移動模型中關(guān)于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所示，當(dāng)傳輸負載大于7.5 kb/s且小于20 kb/s時，在WCC-NCRM協(xié)議下的分組投遞率將明顯高于NCRM的，說明本優(yōu)化協(xié)議改善了在傳輸負載相對增大范圍內(nèi)的網(wǎng)絡(luò)擁塞現(xiàn)象，并且提升了分組投遞率，提高了網(wǎng)絡(luò)資源的利用率。但隨著傳輸負載逐漸增大時，在WCC-NCRM和NCRM協(xié)議下，mesh網(wǎng)中各節(jié)點的編碼、解碼速度都將不及數(shù)據(jù)包的傳輸速度，網(wǎng)絡(luò)出現(xiàn)擁塞現(xiàn)象，從而造成丟包率的增大，引起分組投遞率的急劇下降。

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

3 結(jié)束語

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

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

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

[2]譚國平，倪新洋，季敏，等.一種基于網(wǎng)絡(luò)編碼的移動自組網(wǎng)實時多播協(xié)議[J].微電子學(xué)與計算機，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]譚國平，季敏，倪新洋，等.網(wǎng)絡(luò)編碼VS.存儲轉(zhuǎn)發(fā)：移動自組網(wǎng)中實時多播機制仿真研究[J].成都信息工程學(xué)院學(xué)報，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].計算機工程與設(shè)計，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]李鵬，陳元琰，羅曉署.無線異構(gòu)網(wǎng)絡(luò)環(huán)境中基于擁塞狀態(tài)區(qū)分的TCPVegas改進算法[J].計算機應(yīng)用，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網(wǎng)絡(luò)復(fù)雜統(tǒng)計特性[J].北京航空航天大學(xué)學(xué)報，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網(wǎng)絡(luò)模擬和協(xié)議仿真[M].北京：人民郵電出版社，2010.