基于編碼機(jī)會路由的高效無線Mesh網(wǎng)絡(luò)傳輸技術(shù).pdf

1、作為一種低成本、高覆蓋范圍且方便部署的Internet接入方案，無線Mesh網(wǎng)絡(luò)通常需要承載大量高吞吐率、高可靠的應(yīng)用業(yè)務(wù)。但無線傳輸?shù)囊族e性、信道質(zhì)量的時變性，以及Mesh網(wǎng)絡(luò)的多跳轉(zhuǎn)發(fā)架構(gòu)，均導(dǎo)致該網(wǎng)絡(luò)容易遭受吞吐有限、可靠性低下等問題。
　　機(jī)會路由和網(wǎng)絡(luò)編碼是解決這一問題的有力工具。機(jī)會路由利用無線廣播所帶來的多用戶分集優(yōu)勢，每個旁聽到報文的節(jié)點(diǎn)都有機(jī)會承擔(dān)轉(zhuǎn)發(fā)任務(wù)，從而提高一次傳輸?shù)某晒Ω怕?。網(wǎng)絡(luò)編碼則容許網(wǎng)絡(luò)中間節(jié)點(diǎn)對

2、接收到的報文進(jìn)行混合編碼，以便有效地利用公共鏈路，提高系統(tǒng)吞吐。而且，若隨機(jī)選取編碼系數(shù)（即隨機(jī)網(wǎng)絡(luò)編碼），還能獲得無比率糾刪碼的良好特性。結(jié)合二者優(yōu)勢，編碼機(jī)會路由(Network Coding-based OpportunisticRouting，簡稱NCOR)應(yīng)運(yùn)而生，成為一種在鏈路有損的無線Mesh網(wǎng)絡(luò)中提供高吞吐率、可靠傳輸?shù)挠行Х桨?。本論文旨在研究NCOR的關(guān)鍵設(shè)計因素，并圍繞其“機(jī)會傳輸”和“網(wǎng)絡(luò)編碼”特性，提出新的算法和

3、協(xié)議，為無線Mesh網(wǎng)絡(luò)提供高效、公平的高吞吐率可靠傳輸服務(wù)。研究內(nèi)容和成果包括以下三個層次。
　　1.在網(wǎng)絡(luò)層，研究了最小成本NCOR路由構(gòu)建問題。與傳統(tǒng)路由不同，給定源目節(jié)點(diǎn)，NCOR不用預(yù)先指定明確的轉(zhuǎn)發(fā)路徑，只需要選擇哪些節(jié)點(diǎn)參與機(jī)會轉(zhuǎn)發(fā)。參與節(jié)點(diǎn)通過廣播鏈路連接形成網(wǎng)狀傳輸路徑，每個節(jié)點(diǎn)獨(dú)立地執(zhí)行隨機(jī)網(wǎng)絡(luò)編碼并將編碼報文廣播到下游節(jié)點(diǎn)，因而節(jié)點(diǎn)之間的轉(zhuǎn)發(fā)任務(wù)分配也會直接影響傳輸效率。因此，如何選擇候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集合(Can

4、didate Forwarder Set，簡稱CFS)，以及如何在這些節(jié)點(diǎn)之間分配轉(zhuǎn)發(fā)任務(wù)，是實際部署NCOR時所要面臨的基本問題。現(xiàn)有工作通常獨(dú)立地處理這兩個問題，難以保證整體最優(yōu)性。本論文擴(kuò)展傳統(tǒng)的最優(yōu)路由概念，將這兩個問題融合在一個最小成本框架(MIC-NCOR)中，聯(lián)合求解最佳的CFS和轉(zhuǎn)發(fā)任務(wù)分配。在MIC-NCOR的最優(yōu)子結(jié)構(gòu)的基礎(chǔ)上，根據(jù)動態(tài)規(guī)劃思想，推導(dǎo)出能夠完全分布式實現(xiàn)的MIC-NCOR算法，并給予嚴(yán)格的正確性證明。

5、仿真結(jié)果表明，論文提出的成本模型能更準(zhǔn)確反映NCOR路徑的實際傳輸成本，且MIC-NCOR算法相比現(xiàn)有的啟發(fā)式方法有顯著的性能增益。
　　2.在MAC層，研究了機(jī)會廣播信道接入問題。NCOR的網(wǎng)狀路徑由廣播鏈路拼接而成，因此廣播MAC的表現(xiàn)對于發(fā)揮多用戶分集優(yōu)勢、進(jìn)而提高NCOR的整體性能有重要影響。而NCOR的編碼機(jī)會轉(zhuǎn)發(fā)特性也為廣播MAC的設(shè)計帶來了更多的靈活性:首先，在機(jī)會轉(zhuǎn)發(fā)機(jī)制下，不需要等待所有廣播鄰居進(jìn)入就緒（準(zhǔn)備好接

6、收）狀態(tài)。越多的鄰居就緒，廣播信道的多用戶分集優(yōu)勢就越顯著（機(jī)會轉(zhuǎn)發(fā)的交付概率越高），但同時引入的接入延遲也會更大，因此，需要在接入延遲和廣播信道的交付能力之間做出權(quán)衡。其次，隨機(jī)網(wǎng)絡(luò)編碼的糾刪能力也免除了對MAC的可靠性要求。據(jù)此，我們提出以最大化平均有效速率為目標(biāo)的機(jī)會廣播信道接入問題，并使用最優(yōu)停止理論推導(dǎo)出具有簡單閾值形式的信道接入策略N*。在此基礎(chǔ)上，通過簡單擴(kuò)展IEEE802.11 DCF，設(shè)計出執(zhí)行N*策略的機(jī)會廣播信道接

7、入控制協(xié)議O-BCast。仿真結(jié)果表明，O-BCast能夠顯著提高NCOR的端到端吞吐率，而且具有網(wǎng)絡(luò)負(fù)載自適應(yīng)的良好特性。
　　3.在傳輸層，研究了NCOR的擁塞控制問題。無線Mesh網(wǎng)絡(luò)由多用戶共享，需要承載大量突發(fā)性的高吞吐率業(yè)務(wù)，需要擁塞控制機(jī)制來保證NCOR高效、公平的運(yùn)作。NCOR的傳輸路徑呈網(wǎng)狀，在高負(fù)載、高丟包率的無線Mesh網(wǎng)絡(luò)中，如果仍然依賴聚合層次的端到端擁塞控制方法(如TCP)，容易造成網(wǎng)絡(luò)資源利用不充分和

8、擁塞響應(yīng)滯后等問題。因此，論文基于逐跳控制思想，設(shè)計了全新的NCOR擁塞控制協(xié)議HCC。HCC精確衡量節(jié)點(diǎn)的擁塞程度，并以公平性為原則計算各個業(yè)務(wù)流的擁塞反饋。當(dāng)接收到來自網(wǎng)狀路徑上多個下游鄰居的差異化擁塞反饋時，采用折中策略進(jìn)行速率調(diào)整:若所有擁塞反饋均指示要求增速或降速，節(jié)點(diǎn)按照所有反饋的均值調(diào)整報文發(fā)送速率;若部分反饋要求降速、部分要求增速，節(jié)點(diǎn)維持發(fā)送速率不變而由下游鄰居調(diào)整各自的接收速率。這種策略既能夠有效減輕擁塞節(jié)點(diǎn)的負(fù)載，

9、又能充分利用網(wǎng)狀路徑中輕載節(jié)點(diǎn)的轉(zhuǎn)發(fā)能力以發(fā)揮NCOR的機(jī)會傳輸優(yōu)勢。仿真實驗顯示，在高負(fù)載高丟包率的無線Mesh網(wǎng)絡(luò)中，HCC相比端到端方法在吞吐、傳輸成本、延時以及公平性等方面具有顯著的性能優(yōu)勢。
　　基于上述三方面的建模優(yōu)化和協(xié)議設(shè)計工作，論文最后設(shè)計了一個完整的NCOR系統(tǒng)。仿真實驗表明，在三者共同作用下，該NCOR系統(tǒng)的性能相比獨(dú)自作用時得到進(jìn)一步提升。本工作對于理解和應(yīng)用NCOR這種新型的傳輸機(jī)制，具有重要的理論意義和